Multi-Task Offloading via Graph Neural Networks in Heterogeneous
  Multi-access Edge Computing
In the rapidly evolving field of Heterogeneous Multi-access Edge Computing
(HMEC), efficient task offloading plays a pivotal role in optimizing system
throughput and resource utilization. However, existing task offloading methods
often fall short of adequately modeling the dependency topology relationships
between offloaded tasks, which limits their effectiveness in capturing the
complex interdependencies of task features. To address this limitation, we
propose a task offloading mechanism based on Graph Neural Networks (GNN). Our
modeling approach takes into account factors such as task characteristics,
network conditions, and available resources at the edge, and embeds these
captured features into the graph structure. By utilizing GNNs, our mechanism
can capture and analyze the intricate relationships between task features,
enabling a more comprehensive understanding of the underlying dependency
topology. Through extensive evaluations in heterogeneous networks, our proposed
algorithm improves 18.6\%-53.8\% over greedy and approximate algorithms in
optimizing system throughput and resource utilization. Our experiments showcase
the advantage of considering the intricate interplay of task features using
GNN-based modeling.
Mulei Ma
# Multi-Task Offloading via Graph Neural Networks in Heterogeneous Multi-access Edge Computing

###### Abstract

In the rapidly evolving field of Heterogeneous Multi-access Edge Computing (HMEC), efficient task offloading plays a pivotal role in optimizing system throughput and resource utilization. However, existing task offloading methods often fall short of adequately modeling the dependency topology relationships between offloaded tasks, which limits their effectiveness in capturing the complex interdependencies of task features. To address this limitation, we propose a task offloading mechanism based on Graph Neural Networks (GNN). Our modeling approach takes into account factors such as task characteristics, network conditions, and available resources at the edge, and embeds these captured features into the graph structure. By utilizing GNNs, our mechanism can capture and analyze the intricate relationships between task features, enabling a more comprehensive understanding of the underlying dependency topology. Through extensive evaluations in heterogeneous networks, our proposed algorithm improves 18.6%-53.8% over greedy and approximate algorithms in optimizing system throughput and resource utilization. Our experiments showcase the advantage of considering the intricate interplay of task features using GNN-based modeling.

 Task Offloading, Graph Neural Network, Multi-access Edge Computing, Heterogeneous Network

## I Introduction

Edge computing refers to the decentralized infrastructure that brings computation and data storage closer to the network edge, reducing latency and improving response times for end-users [1]. Task offloading in edge scenes has become an essential technique in the field of edge computing, involving the distribution of computationally intensive tasks from resource-constrained devices to edge servers or cloud platforms, leveraging their computational capabilities and proximity to the data source [2]. By offloading tasks to edge servers, the computational burden on these devices is alleviated, enabling them to focus on tasks that are better suited for local execution. Furthermore, compared to cloud computing, offloading tasks to edge servers can significantly reduce latency and response times. Scholars in the field have recognized the potential benefits of task offloading in edge scenes. They emphasize that efficient task offloading strategies can lead to improved user experiences, real-time responsiveness, and reduced energy consumption for resource-constrained devices [3, 4]. However, some challenges need to be addressed to fully realize the potential of task offloading in edge environments.

One of the challenges is to generate reasonable strategies that take into account various factors such as task characteristics, network conditions, and the availability of resources at the edge. The decision of whether to offload a task and where to offload it requires careful consideration and optimization algorithms. The commonly used solution currently is to use heuristic algorithms to generate computing offloading strategies, including genetic algorithms, simulated annealing algorithms, ant colony algorithms, and so on [5, 6]. But these algorithms may fall into local optima and require manual adjustment of algorithm parameters to achieve better results. There is also a lot of research work using game theory to simulate the offloading cooperation between users and service providers, and design corresponding auction algorithms [7, 8]. But it assumes that all players are rational, meaning they will always adopt the optimal strategy, which is difficult to guarantee in real scenarios. In addition, reinforcement learning has also been introduced into the computational offloading decision-making process, allowing agents to take offloading actions through environmental feedback [9, 10]. Unfortunately, researchers have found that some models are difficult to converge and find the optimal solution accurately.

With the development of Graph Neural Networks (GNNs) in recent years, GNNs have become a powerful model widely used in graph data analysis [11]. GNN can effectively process graph data with complex structures, which enables it to apply to many fields. In the domain of task offloading, GNNs offer advantages that make them well-suited for addressing the challenges of efficient offloading strategies in edge scenes. One key motivation for employing GNNs in task offloading is their ability to leverage the inherent graph structure that underlies many real-world scenarios. In the context of edge scenes, the relationships between tasks, devices, and edge servers can often be represented as a graph, where nodes represent tasks or devices, and edges represent the dependencies or relationships between them [12]. By utilizing GNNs, it becomes possible to exploit the structural information encoded in the graph to make informed offloading decisions. Moreover, GNNs can adaptively update their representations as the graph evolves, allowing them to adapt to dynamic changes in task requirements, network conditions, or the availability of edge resources. This adaptability is crucial in edge scenes where the availability and characteristics of edge servers may vary dynamically. GNNs can continuously learn and update their models based on the evolving graph, enabling more flexible and responsive offloading decisions.
The primary research objectives of this study are to address the challenges associated with efficient offloading decisions in edge environments, by utilizing GNNs. And leverage the inherent graph structure of edge scenes to improve resource utilization and reduce latency. Firstly, we propose a framework that models the tasks that users need to offload into a graph structure. Secondly, we apply the Graph Convolutional Network (GCN) to the offloading graph. We have defined a training method for GCN, which uses a graph state transfer method to generate offloading strategies, allowing for the integration of contextual information and dependencies. This approach has the potential to enhance the decision-making process, considering task characteristics, network conditions, and available edge resources. Finally, we conduct a comprehensive evaluation of the GCN-based offloading strategies in edge scenarios. Through extensive simulations and performance analysis, we assess the effectiveness of the proposed framework in terms of system throughput and resource utilization optimization. Compared with various methods, the GCN strategy can effectively improve the system processing efficiency. Our contribution points can be summarized as follows:

1. We have designed a modeling approach to convert the task to be offloaded into a graph structure. This method will generate inherent graph structures based on task attributes and adapt to dynamic changes. This design will advance the understanding of utilizing graph based neural networks for optimizing task offloading in edge scenes
2. We propose a framework to explore the potential of GCN for task offloading in edge scenarios. GCN provides a means to incorporate complex contextual information and dependencies into offloading decisions, leading to improved system performance and enhanced resource utilization.
3. Our experiment shows that GCN exhibits promising results in graph related tasks, indicating their potential effectiveness in the field of task offloading. Compared with baselines, GCN achieves better system throughput and resource utilization.

## II Related Work

### _Overview of existing approaches to task offloading in edge scenes_

In task offloading, it is important to consider the heterogeneity of MEC (Mult-access Edge Computing) servers. This heterogeneity refers to variations in computational capabilities, storage capacities, and communication capabilities among MEC servers. Researchers have explored different approaches to address these challenges and optimize the performance of edge computing systems. This section provides an overview of some existing approaches and their contributions. Y. Tu _et al._[13] optimized task transmission in fog computing networks through numerical methods, balancing the costs of local computing, offloading, and discarding, and achieving a low complexity offloading algorithm. However, although numerical methods can accurately find the optimal solution, they overlook the dynamic perception of the scene. S. Yang _et al._[14] proposed a multi-round sequential combination auction mechanism considering the heterogeneous Internet of Vehicles scenario, and modeled the matching problem as a grouped knapsack problem. However, the strategy generation of game theory algorithms generally requires a lot of computing resources and time. The above literature indicate that researchers have recognized that the heterogeneity of MEC servers poses additional challenges in resource allocation and task scheduling, and have proposed solutions to efficiently utilize the available resources while appropriate approaches are still needed to generate offloading decisions.

### _Discussion of GNN-based strategies in edge computing_

GNNs have shown great potential in capturing and leveraging the inherent graph structures present in edge computing environments. By representing the relationships between tasks, edge devices, and cloud servers as a graph, GNNs enable efficient decision-making and resource allocation in task offloading scenarios. Several studies have demonstrated the effectiveness of GNN-based strategies in achieving better performance metrics, such as reduced latency, improved energy efficiency, and enhanced user experience. Work [15, 16, 17] combines GNN and reinforcement learning to apply to edge scenes. Their common approach is to use GNN for scene modeling, and then use reinforcement learning algorithms to generate offloading strategies. K. Li _et al._[18] proposes a reinforcement learning framework based on depth maps for unmanned aerial vehicle systems, which reduces the loss rate of aerial task transmission. However, there is currently a lack of work utilizing GNN to capture the spatial dependencies among tasks, and effective literature references are scarce. And it lacks the graph representation allowance for real-time updates and adjustments based on changing heterogeneous network conditions and resource availability.

## III System Overview

In this section, we consider a general multi cell heterogeneous network. This network consists of multiple randomly distributed heterogeneous edge servers ES, each with varying computing and communication capabilities. For the convenience of description and analysis, we consider a quasi static network scenario, where time is divided into time slots of the same size, and the resource allocation and network conditions in each time slot are considered static and invariant. Within each time slot, the user device UD is waiting for offloaded tasks to be generated. To complete the task response within strict delay requirements, the task will be transferred to the nearby high computing power ES for processing, i.e. task offloading. In any specific time slot, each ES has two states: idle and busy. It should be pointed out that we stipulate that ES can calculate up to one task. If there are already tasks being executed in the current ES, subsequent tasks will be placed in the waiting queue. We assume that in the time slot \(\tau\), the ES set is \(S\) and the set of tasks to be offloaded is \(N\). Each
task is represented by a binary \((z,c)\). Where \(z\)represents the task size, in bits, \(c\) represents the computational amount of the task, in CPU revolutions per second.

### _Communication model_

In terms of communication, the system is based on the OFDMA protocol. The entire frequency band is divided into multiple subcarriers, which is in line with most current wireless standards. Communication devices occupying different subcarriers do not generate interference, and interference mainly comes from inter cell interference. The Signal Interference plus Noise Ratio (SINR) of task \(n\in N\) can be expressed as:

\[\mathrm{SINR}_{n}=\frac{h_{ns}p_{n}}{\sigma_{n}^{2}} \tag{1}\]

\[\sigma_{n}^{2}=\sigma^{2}+\sum_{m\in I^{k}\setminus\{n\}}p_{n}h_{ns}. \tag{2}\]

where \(h_{ns}\) denotes the communication gain between UD and ES \(s\) during the offloading process. \(p_{n}\) denotes the communication power of UD. \(\sigma_{n}^{2}\) denotes the transmission noise of task \(n\), and \(\sigma^{2}\) denotes the background noise. The subcarrier number is denoted by \(k\in K\), while \(I^{k}\) denotes the set of tasks that occupy subcarrier \(k\) transmissions. Next, we denote the transmission rates of tasks \(n\) and ES \(s\) by \(r_{n}\).

\[r_{n}=B_{k}\log_{2}\left(1+\mathrm{SINR}_{n}\right), \tag{3}\]

where \(B_{k}\) denotes the bandwidth of subcarrier \(k\). Then the task transmission time \(t_{n}^{tran}\) can be expressed as:

\[t_{n}^{tran}=\frac{z_{n}}{r_{n}}, \tag{4}\]

### _Computation model_

Computationally, the computation time \(t_{n}^{comp}\) for task \(n\) can be expressed by dividing the computational demand by the computational power of the ES, both of which can be expressed in terms of CPU revolutions, as follows:

\[t_{n}^{comp}=\frac{c_{n}}{f_{n}} \tag{5}\]

where \(f_{s}\) is the node computation rate, i.e., the CPU clock frequency (CPU revolutions/sec). We set the ES to serve only one task per time slot, and subsequent arrivals cannot be executed immediately. Moreover, we assume that the ES starts processing the task only when all data transfers are completed. Therefore, we use \(t_{n}^{start}\) to denote the time when the task to be offloaded starts transferring. The time when the task processing is completed \(t_{n}^{end}\) can be expressed as:

\[t_{n}^{end}=t_{n}^{start}+t_{n}^{tran}+t_{n}^{comp} \tag{6}\]

Fig. 1 shows an example where multiple tasks are offloaded to the ES cluster via a wireless network. The size and arithmetic requirements vary from task to task. The right side of Fig. 1 shows typical task arrival times and execution times for selected specific ES and communication scenarios.

## IV Training Process for Generating Offloading Decision Using GCN

In this section, we will delve into the training process for generating offloading decisions using GCN.

### _Node and edge features_

Our modeling approach obtains the ability to capture the spatial and temporal dependencies among tasks. First, we represent the tasks to be offloaded as nodes in the graph. The edges represent the contextual relationships between tasks and are mainly affected by features such as ES arithmetic power, network conditions, task size, and arithmetic demand. When there is a temporal conflict between task executions, edges are generated as connections between corresponding nodes in the graph.

As an example, the three nodes on the left side of Fig. 2 represent task 3, task 5, and task 6. A comparison with Fig. 1 shows that all three tasks have execution time conflicts (marked by red dashed lines). Therefore, all three are connected by edges in Fig. 2 to indicate the dependencies among the tasks. The graph generated based on the execution of all tasks is shown on the right side of Fig. 2. Furthermore, GCN-based approaches facilitate dynamic and adaptive task offloading. The graph representation allows for real-time updates and adjustments based on changing network conditions and resource availability.

Fig. 1: Cluster operation occupies workload.

Fig. 2: Cluster operation occupies workload.
### _GCN-based offloading decision_

Quadratic Unconstrained Binary Optimization (QUBO) is a mathematical form for solving optimization problems. QUBO can encode offloading problems with the Hamiltonian form. For computational offloading problems, the offloading decision between a particular UD \(n\) and ES \(s\) can be represented by a binary variable x. The offloading decision between The \(x=1\) means that an offloading mapping is formed between the two, while x=0 does not hold. We input the offloading Hamiltonian into the QUBO solver and obtain the decision \(x\). We set \(V_{s}\) to be the set of tasks offloaded to ES s. \(E_{s}\) denotes the set of all edges connected to nodes in \(V_{s}\). \(\delta\) is a constant and denotes the penalty parameter. The modeling approach from Schuetz, M.J.A [19], offloading strategy can be formulated in Hamiltonian as:

\[H_{s}=-|V_{s}|+\delta|E_{s}|,s\in S \tag{7}\]

The GCN passes node features to adjacent nodes through the adjacency matrix through the message passing mechanism, i.e., the feature vector \(X_{i}\) of node \(i\) is passed to the feature vector of the node adjacent to it through the adjacency matrix \(A\), and this process can be expressed by the following equation:

\[M^{(l+1)}=\sigma_{R}\left(\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}} M^{(l)}W^{(l)}\right), \tag{8}\]

where \(M^{l}\) denotes the feature matrix of the _lth_ layer and \(W^{l}\) denotes the weight matrix of the _lth_ layer. \(\hat{A}=A+I\) is the adjacency matrix \(A\) plus the matrix after self-connection. \(D\) is the diagonal matrix, where \(\hat{D}_{ii}=\sum_{j}\hat{A}_{ij}\). \(\sigma_{R}\) denotes the use of the ReLU activation function.

We refer to the unsupervised learning method in [19]. GCN can build multilayer networks by stacking multiple graph convolutional layers. The output feature vector of each layer can be used as the input feature vector of the next layer, thus enabling the information to be passed and updated layer by layer. A fully connected layer and a softmax activation function are added to the feature vector of the last layer to achieve this. The output vector of the last layer represents the probability that each node belongs to each class.

The proposed research presents a multi-task offloading framework based on GCN. The framework aims to optimize the decision-making process for offloading tasks in a heterogeneous network environment. The algorithmic steps for computing the offloading decisions are outlined in Algorithm 1. The first step involves the initialization of the GCN parameters. These parameters are crucial for the subsequent decision-making process. Subsequently, the algorithm starts monitoring various network parameters, namely network bandwidth \(B_{k}\), ES computing power \(f_{s}\), and channel gain between the UD and ES \(h_{ns}\). These parameters are essential for determining the feasibility and efficiency of offloading tasks.

```
1: GCN parameter initialization.
2: Monitoring the network bandwidth, ES computing power, and channel gain of UD and ES as \(B_{k}\), \(f_{s}\) and \(h_{ns}\), \(n\in N,s\in S\).
3:for\(s\in S\)do
4: Collect the tasks to be offloaded in the system and compose a waiting list
5:for episode number t in 1,2,...T do
6: Calculate the transfer delay \(t_{n}^{tran}\) and computing delay \(t_{n}^{comp}\) of task n to s, \(n\in N\).
7: Determine the task execution context based on the task arrival schedule.
8: Generate task graph \(G\) based on task execution schedules.
9: Input \(G\) into GCN to generate the offloading decision.
10: Remove the task corresponding to the selected offloaded node from the waiting list.
11:endfor
12:endfor
```

**Algorithm 1** Multi-Task Offloading Framework Based on GCN

The algorithm then proceeds to iterate over each server \(s\) in the set of servers \(S\). Within each server iteration, the algorithm collects the tasks that need to be offloaded in the system and composes a waiting list. This waiting list represents the pool of tasks available for offloading. For each episode (indexed by \(t\)) within the predetermined number of episodes \(T\), the algorithm performs the following steps. Firstly, it calculates the transfer delay \(t_{n}^{tran}\) and computing delay \(t_{n}^{comp}\) for each task \(n\) to the selected server \(s\). These delays capture the time required for transferring data and executing computations, respectively. Next, the algorithm determines the task execution context based on the task arrival schedule. This step ensures that tasks are executed in the correct order and timeframe.

To enable the decision-making process, the algorithm generates a task graph \(G\) based on the task execution schedules. This graph serves as the input to the GCN model. By utilizing the GCN, the algorithm generates the optimal offloading decision for each task. The decision indicates whether a task should be offloaded or executed locally. Finally, the algorithm removes the task corresponding to the selected offloaded node from the waiting list, as it has been successfully offloaded and processed. The entire process repeats for each server in the set \(S\), ensuring that all tasks are considered for offloading. The algorithm terminates once it completes the iteration over all servers and episodes, providing a comprehensive offloading decision for each task in the system.

## V Experimental and Model Evaluation

Next, we will evaluate the performance of the GCN-based computational offloading algorithm through experiments. We consider a multi-cell system with heterogeneous ES in each cell center. Each ES not only has abundant communication resources but also has powerful computing power. We assume that there are a total of 6 ES in the network, and their computing power is randomly selected at [0.6, 0.8, 1.0, 1.2] GHz. The
scenario is based on the OFDMA protocol, with a bandwidth of 5 MHz and channel noise of -117dBm. Considering the diversity of user devices, we set the communication power of the device to be selected from [0.3, 0.5, 0.7] W. Each offloading task size and computing power requirement are randomly selected from the [800, 4000] KB and \([3000,6000]*10^{6}\) cycles, respectively. In addition, to better reflect the algorithm performance, we have implemented the following baseline:

* _GCN-based Offloading Algorithm_ (**GCNOA**): Our proposed algorithm. Use GCN to generate offloading policies based on task attribute graphs.
* _Branch and Bound for Offloading Algorithm_ (**BBOA**): The branch-and-bound algorithm traverses all possible solutions recursively while using pruning strategies to exclude invalid solutions. The branch-and-bound algorithm can achieve exponential time complexity in the worst case.
* _Approximation Strategy for Offloading Algorithm_ (**ASOA**): Approximation algorithms match tasks and nodes according to heuristic rules in pursuit of maximizing offloading performance. It can find an approximate optimal solution with high efficiency, providing a way to trade off time and solution quality.
* _Greedy Strategy for Offloading Algorithm_ (**GSOA**): In the greedy policy, pending offload tasks are offloaded to the nearest ES based on network conditions to maximize system performance.

### _Servers workload status_

Fig. 3 shows the actual workload situation of the server cluster. There are a total of 6 ES in the scene, and the number of uninstalled tasks is 200. In Fig. 1, the horizontal axis represents the time frame, and the vertical axis represents the server ID. The first 400 time frames are captured in Fig. 3 for display. The different colored line segments represent the time taken by the offloading task to occupy the corresponding server resources. Each server has tasks to process most of the time, and the less idle time, the higher the resource utilization rate. Specifically, the resource utilization rates from server 1 to server 6 are 78.2%, 73.3%, 72.7%, 73.7%, 68.2%, and 65.9%, respectively. Therefore, our proposed GCN algorithm can achieve efficient task scheduling and reasonable allocation of server cluster resources.

Fig. 4: System throughput.

Fig. 5: Server resource utilization rate.

Fig. 3: Cluster operation occupies workload.
### _System throughput & resource occupancy_

Fig. 4 shows the changes in system throughput under different task densities. The x-axis in the image represents the number of tasks to be offloaded, while the y-axis represents the system throughput. The blue, green, purple, and red in the figure represent the GCNOA, BBOA, ASOA, and GSOA algorithms, respectively. The common feature of the four curves shows that as the number of tasks to be offloaded increases, the overall system throughput shows an upward trend. The curves corresponding to the ASOA and GSOA algorithms are the lowest. This indicates that greed and approximation strategy are prone to falling into local optima, making performance difficult to guarantee. Relatively speaking, the GCNOA algorithm has achieved the performance of BBOA, with similar performance between the two. In addition, GCNOA achieved higher system throughput compared to other baselines. Specifically, when the number of tasks is 120, the throughput of GCNOA is improved by 23.5% and 50.0% compared to ASOA and GSOA algorithms, respectively.

Next, we will analyze the resource utilization rate of the system. To describe the resource utilization of different algorithms, we expanded the number of tasks to the range of [50-250]. In Fig. 5, as the number of tasks increases, the overall resource utilization rate of the offloading algorithm in the fourth section shows an upward trend. Among them, GSOA and ASOA have poor performance and significant curve fluctuations. This indicates that the greedy and approximation algorithms are not stable enough to find the global optimal solution. Our proposed GCNOA can approach BBOA in resource utilization. This indicates that GCN can effectively generate efficient and robust offloading strategies. Specifically, when the number of tasks is 100 and 200, the resource utilization rate of GCNOA is 18.6%, 53.8%, 22.1%, and 44.9% higher than that of ASOA and GSOA.

## VI Conclusion

In this study, we addressed the limitations of existing task offloading methods in modeling the dependency topology relationships between offloaded tasks within the context of HMEC. We introduced a novel task offloading mechanism based on GCN that effectively captures the complex interdependencies of task features. the motivation for utilizing GCNs in task offloading stems from their ability to leverage the graph structure inherent in edge scenes, capture complex relationships, propagate information, and adapt to dynamic changes. By harnessing the power of GCNs, task offloading strategies can benefit from improved decision-making, enhanced resource utilization, and optimized performance in edge environments. By considering task characteristics, network conditions, and available edge resources, we embedded these features into a graph structure and utilized GCNs to analyze the integrated relationships.

Our extensive evaluations in heterogeneous networks have demonstrated the superiority of our proposed algorithms, resulting in significant improvements in system throughput and resource utilization. Compared with the greedy and approximate algorithms, our proposed algorithm improves the system throughput by 23.5%-50.0% and resource utilization by 18.6%-53.8%. These findings strongly support the notion that considering the integrated interplay of task features through GCN-based modeling is crucial for achieving optimal offloading decisions. We believe that our findings will inspire further exploration and refinement of GCN applications in edge networks, ultimately leading to more efficient and intelligent computing offloading solutions in heterogeneous edge computing environments.
