# TPD: Temporal and Positional Computation Offloading with Dynamic and Dependent Tasks

Authors: Mingzhi Wang; Tao Wu; Xiaochen Fan; Penghao Sun; Yuben Qu; Panlong Yang
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

With the rapid development of wireless communication technologies and the proliferation of the urban Internet of Things (IoT), the paradigm of mobile computing has been shifting from centralized clouds to edge networks. As an enabling paradigm for computation-intensive and latency-sensitive computation tasks, mobile edge computing (MEC) can provide in-proximity computing services for resource-constrained IoT devices. Nevertheless, it remains challenging to optimize computation offloading from IoT devices to heterogeneous edge servers, considering complex intertask dependency, limited bandwidth, and dynamic networks. In this paper, we address the above challenges in MEC with TPD, that is, temporal and positional computation offloading with dynamic-dependent tasks. In particular, we investigate channel interference and intertask dependency by considering the position and moment of computation offloading simultaneously. We define a novel criterion for assessing the criticality of each task, and we identify the critical path based on a directed acyclic graph of all tasks. Furthermore, we propose an online algorithm for finding the optimal computation offloading strategy with intertask dependency and adjusting the strategy in real-time when facing dynamic tasks. Extensive simulation results show that our algorithm reduces significantly the time to complete all tasks by 30–60% in different scenarios and takes less time to adjust the offloading strategy in dynamic MEC systems.


---

## Body

## 1. Introduction

With the rapid development of wireless communication technologies and the pervasive use of the urban Internet of Things (IoT), IoT devices have become deeply integrated into daily life [1]. At the same time, the rapid increase in the number of IoT devices has brought new challenges in processing the massive amount of IoT data [2]. With constrained computing resources and limited battery capacity, IoT devices are facing rapid energy drains as a result of processing computation-intensive tasks [3, 4]. While some initial efforts have been made to solve such problems by leveraging centralized cloud computing, the long communication distance and unstable network connection can cause unacceptable delays to end users [5, 6]. To tackle this issue, mobile edge computing (MEC) has emerged as a promising computing paradigm for providing highly responsive computing services with low latency [7–10]. By offloading computation tasks to edge servers, IoT devices incur fewer costs than they would if processing these tasks locally or remotely at cloud data centers [11].Nevertheless, applications on IoT devices are highly diverse, and there can be intertask dependency in many computation tasks offloaded to MEC [12]. For instance, Figure 1(a) shows an access control system for MEC. When a user wants to enter, they must swipe their card and pass facial recognition. The card reader generates the ID card recognition task, whereupon the camera takes user pictures and then generates the feature extraction task. When the latter is completed, the camera then generates the data analysis task to analyze the results of the feature extraction task. Intuitively, the door opens only after the data analysis and ID card recognition tasks have been processed successfully. The arrows in Figure 1(a) show the dependencies among the three computation tasks. Therefore, we must find an optimal offloading strategy for all three tasks. Suppose that there are two edge servers, i.e., edge server 1 and edge server 2, and that edge server 2 has greater computing capability and larger channel bandwidth than those of edge server 1. Correspondingly, the three tasks executed on the edge servers will generate different uploading delays and computation delays, as shown in Table 1. Note that there will be channel interference when tasks are uploaded simultaneously, which will cause longer delays than expected. Specifically, we carefully consider the following two issues of computation offloading with intertask dependency in MEC.Figure 1
A simple example of an access control system.
(a)
Schematic of access control system(b)
First type of offloading positions(c)
Second type of offloading positions(d)
Tasks uploaded simultaneously(e)
Tasks uploaded separatelyTable 1
Delays of three tasks on different servers.
Feature extractionData analysisID card recognitionUploading onS1 (separated)6 ms6 ms4 msUploading onS1 (synchronous)8 ms8 ms5 msComputing onS17 ms6 ms5 msUploading onS2 (separated)5 ms5 ms3 msUploading onS2 (synchronous)7 ms7 ms4 msComputing onS26 ms5 ms4 msOffloading position: the first step is to find the optimal offloading positions for the three tasks. Here, we have produced two different types of offloading positions for tasks. With the first type (Figure 1(b)), the ID card recognition task is offloaded to edge server 2 and its total delay is 3+4=7 ms. We assume that the feature extraction and data analysis tasks are uploaded simultaneously, so that the total delay is 8+7+6=21 ms (data analysis must wait for feature extraction to complete). In this case, the door opens after 21 ms. As can be seen, both the feature extraction and data analysis tasks determine the delay of door opening. However, if we offload both the feature extraction and data analysis tasks to edge server 2 (Figure 1(c)), then the total delay is reduced to 18 ms. Therefore, it is essential to consider task dependencies when seeking desirable offloading positions.Offloading moment: if the feature extraction and data analysis tasks are offloaded simultaneously to edge server 2 at 0 ms (Figure 1(d)), then there is channel interference and the uploading delay of the two tasks becomes 7 ms. Consequently, the door opens after 18 ms. However, if we set the offloading moment of the data analysis task as 6 ms (Figure 1(e)), then channel interference is avoided and the overall uploading delay is reduced to 5 ms. Finally, the door opening time is advanced to 16 ms. By introducing this example, we show that the offloading moment also has considerable impact on task processing in mobile computation offloading.Existing solutions for mobile computation offloading are focused mainly on reducing task response delays, and generally, they offload all computation tasks to MEC and then make optimized adjustments to the edge servers. However, as the above observation cases show, the potential intertask dependency and channel contention will cause significant processing delays in MEC systems with thousands or even millions of IoT devices. Herein, we study the problem of TPD, that is, temporal and positional computation offloading with dynamic-dependent tasks in MEC. In particular, we investigate computation offloading in MEC considering both intertask dependencies and offloading moments. We also address the dynamics of mobile edge networks, where new tasks are involved continuously in computation offloading. Formally, we aim to solve the following three critical challenges.(i)
How to find the optimal offloading positions of tasks under dependency restrictions: with more tasks, the dependencies among them become very complicated. Therefore, a challenge is how to find the optimal offloading position for each task under such complicated dependency restrictions(ii)
How to calculate the offloading moments of tasks to avoid channel interference: the execution and upload delays of tasks are affected by various factors such as channel quality and the computation capabilities of the edge servers. Therefore, it is difficult to estimate these delays, thereby posing the challenge of how to calculate the offloading moments of tasks to reduce channel interference(iii)
How to reduce the time overhead of updating the offloading strategy in real time: in a dynamic MEC system, IoT devices generate new tasks frequently, and the offloading strategy must also be updated frequently. However, doing so incurs a time overhead, so another challenge is how to update the offloading strategy in real timeTo overcome the above challenges, we propose an online offloading algorithm known as the critical task first (CTF) algorithm. Combined with the idea of the critical path, the CTF algorithm marks the criticality of tasks based on their dependencies and decides the offloading positions of tasks according to their criticality. When IoT devices generate new tasks in the MEC system, the CTF algorithm can update the offloading strategy in real time with minimal time overhead. The main contributions in this paper are summarized as follows:(i)
We not only decide the offloading positions and execution order of tasks but also calculate the offloading moment of each task to reduce channel interference and uploading delay(ii)
Considering the dependencies among tasks and combining the critical-path idea, we propose an efficient online offloading algorithm, i.e., the CTF algorithm. This uses a backward criticality notation (BCN) method to mark the criticality of tasks, and it can update the offloading strategy with less time overhead in the dynamic MEC system(iii)
We conduct simulations to assess the effectiveness of the CTF algorithm in different scenarios. Compared with previous studies, the CTF algorithm is effective at reducing the time to complete all tasks and updating the offloading strategy with less time overheadThe rest of this paper is organized as follows. Section2 introduces related work. Section 3 presents the system model and problem formulation. Section 4 introduces the main design of the offloading strategy. Section 5 presents the evaluation results. Section 6 concludes the paper.


## 2. Related Work

As one of the core technologies in MEC, computation offloading has attracted considerable research attention in recent years [13, 14]. According to the optimization goal, computation offloading can be divided into three categories: (i) minimizing the delay [15–17], (ii) reducing the energy consumption [18, 19], or (iii) balancing the delay and energy consumption [20, 21]. Herein, we consider mainly computation offloading to minimize task delays.Previous studies of minimizing task delays can be classified into two broad categories: centralized and distributed. The centralized method [22, 23] sets the MEC controller to collect global information with which it makes an optimal offloading decision for each task. Cooperation among multiple mobile devices is presented in [22], wherein the authors construct a potential game to realize task scheduling aimed at minimizing the overhead of each mobile device. In [23], Chen and Hao propose an efficient task-offloading policy in software-defined ultradense networks; they formulate the task-offloading problem as an NP-hard nonlinear mixed-integer programming problem and transform this optimization problem into a task-placement subproblem and a resource-allocation subproblem. Another direction is distributed resource allocation for multiuser MEC systems [24–26]. In [24], by targeting a multiuser and multiserver scenario involving a small-cell network integrated with MEC, the authors formulate the problem as a distributed overhead-minimization problem to minimize the overhead for users.Dependency-aware computation offloading has also been studied widely. In [27], the authors propose a dependency-aware offloading scheme in MEC with edge–cloud cooperation under task-dependency constraints. In [28], the authors propose a model-free approach based on reinforcement learning, i.e., a Q-learning approach that adaptively learns to optimize the offloading decision and energy consumption jointly by interacting with the network environment. In [29], the authors study the impact of interuser task dependency on task offloading and resource allocation in a two-user MEC network, and they propose an efficient algorithm to optimize such decisions.In [30, 31], the authors use game theory to solve the problem of optimal offloading. In [31], the authors also consider the dependency among subtasks and the contention among multiple users, and they propose the distributed earliest finish-time offloading (DEFO) algorithm based on noncooperative game theory to reduce the overall completion time of IoT applications. Compared with our CTF algorithm, the DEFO algorithm only decides the offloading positions and execution order of tasks without considering the offloading moments, thereby causing serious channel interference. Also, the DEFO algorithm is designed for static MEC systems, but actual MEC systems change dynamically. By contrast, the proposed CTF algorithm can perform temporal and positional computation offloading according to task dependencies and update the offloading strategy with less time overhead in dynamic MEC systems.


## 3. System Model

This section introduces the system model. We begin by describing the network model and then present the communication and computation models in detail. For clarity of presentation, Table2 summarizes the notations used in the following formulation.Table 2
Notations used herein.
NotationDefinitionASet of IoT devicesSSet of edge serversTi,jTaskj of Aimi,jComputation input data size ofTi,jci,jNo. of CPU cycles required forTi,jai,jOffloading position ofTi,jPi,jPredecessor task set ofTi,jSi,jSuccessor task set ofTi,jSTi,jOffloading moment ofTi,jFTi,jFinishing moment ofTi,jri,ktData upload rate fromAi to Sk at time tBkBandwidth of channel connected toSkϖBackground noiseqiTransmission power of IoT deviceAigi,kChannel gainfilComputation capability of IoT deviceAifkeComputation capability of edge serverSkti,jTotal delay ofTi,jΦOffloading strategy for all tasksΨMoment at which all tasks are completed


### 3.1. Network Model

As shown in Figure2, we consider a typical multiuser and multiserver MEC system with n IoT devices, l nearby edge servers, and wireless access points such as macro base stations and small-cell base stations with relatively powerful and heterogeneous computation abilities. The IoT devices can offload tasks to any edge server through the base stations and the core network. The sets of IoT devices and edge servers are denoted as A=A1,A2,⋯,Ai,⋯,An and S=S1,S2,⋯,Sk,⋯,Sl, respectively. We suppose that each IoT device generates a set of computationally intensive tasks to be executed during the work. Let Ti,1,Ti,2,⋯,Ti,j,⋯,Ti,m denote the set of tasks from IoT device Ai, where Ti,j represents task j. For efficient computation offloading, we exploit the potential dependency correlation among the tasks [32]. As in the example in Figure 1(a), executing the data analysis task requires completion of the feature extraction task as a prerequisite. Therefore, we define the feature extraction task as the predecessor task of the data analysis task, and the data analysis task is its successor task.Figure 2
Typical multiuser and multiserver mobile edge computing (MEC) system.TaskTi,j can then be described by the five-tuple mi,j,ci,j,ai,j,Pi,j,Si,j, where the terms are as follows: (i) mi,j is the size of the input data for task execution (e.g., the program codes and input parameters); (ii) ci,j is the total number of CPU cycles required to accomplish task Ti,j; (iii) because each task can be either executed locally or offloaded to a nearby edge server, we use ai,j∈0∪S to denote the offloading position of task Ti,j, where ai,j=0 means that task Ti,j is executed locally on IoT device Ai and ai,j=k means that Ti,j is offloaded to edge server Sk for execution; (iv) Pi,j is the predecessor task set of Ti,j; and (v) Si,j is the successor task set. A task can start only after all its predecessors have been completed. STi,j is the offloading moment of Ti,j, and FTi,j is the finishing moment.


### 3.2. Communication and Computation Models

In this subsection, we introduce how to model the task delay, which can be divided into communication and computation parts. If tasks are executed by the IoT devices themselves, then only a computing delay is incurred; otherwise, the IoT devices select an edge server from the edge server setS for computation offloading, which incurs uploading, waiting, and computing delays. Next, we introduce the communication model followed by the computation model.Communication model: the communication channel quality changes constantly during the process of computation offloading. In [30, 31], the authors give a formula for calculating the task upload rate. Based on this, we introduce how to calculate the aforementioned communication delays in detail according to the time. pi,kt indicates whether device Ai is uploading tasks to edge server Sk at time t. If there is a task Ti,j such that ai,j=k and its uploading interval contains time t, then pi,kt=1, otherwise pi,kt=0. ri,kt denotes the data upload rate from device Ai to edge server Sk at time t and is given as
(1)ri,kt=Bklog21+qigi,kϖ+∑i′∈1,.,n,i′≠iqi′gi′,kpi′,kt,where Bk is the bandwidth of the communication channel connected to edge server Sk, qi is the transmission power of Ai, gi,j is the channel gain for the link between Ai and Sk, ϖ is the background noise, and ∑i′∈1,..,n,i′≠iqi′gi′,kpi′,kt is the wireless interference suffered from other IoT devices when Ai uploads tasks to Sk.Computation model: a computation task can be either handled locally or offloaded to an edge server for computing, which leads to two different delay computing methods.
(1)
Local computing: the task is handled on the IoT device itself, and there is only a computing delay in the process. fil is the computing capability of IoT device Ai, which represents the number of CPU cycles that Ai can calculate per second. Given the number of CPU cycles for task Ti,j, the delay ti,jl of Ti,j with local computing can be represented as(2)ti,jl=ci,jfil(2)
Edge computing: tasks are offloaded to edge servers for computing, and the process involves the following steps: the task is uploaded to the edge server; then, it is queued in the server for execution, and finally, the edge server computes the task to obtain the results. Therefore, these three steps produce a three-part delay (upload delay, queuing delay, and computing delay). The upload delay ti,jk,U of Ti,j from Ai to Sk is determined by the data upload rate ri,kt and the data volume mi,j. Therefore, ti,jk,U is calculated as(3)ti,jk,U=mi,jri,ktAfter arriving at the edge server,Ti,j may need to queue in the server for computing, and ti,jk,Q denotes the queuing delay of Ti,j on Sk. We use Qi,j to denote the task set that is queued in front of Ti,j on Sk. Therefore, ti,jk,Q is calculated as
(4)ti,jk,Q=∑Ti′,j′∈Qi,j:‍ci′,j′fke.fke is the computing capability of edge server Sk, and we calculate the computing delay ti,jk,C as
(5)ti,jk,C=ci,jfke.Inedge computing, the delay ti,jk of Ti,j comprises the uploading, queuing, and computing delays as
(6)ti,jk=ti,jk,U+ti,jk,Q+ti,jk,C.ti,j is the total delay of Ti,j and is denoted as
(7)ti,j=ti,jlifai,j=0,ti,jkifai,j=k.IfTi,j chooses local computing, then ti,j=ti,jl. If Ti,j chooses edge server Sk, then ti,j=ti,jk. Therefore, given STi,j and ai,j of the task, we calculate the finishing moment as
(8)FTi,j=STi,j+ti,j.


### 3.3. Problem Formulation

Herein, given the dependencies among tasks, the dynamics of the MEC system, and the multiuser wireless interference, we jointly optimize the task offloading position and moment.(1)
Optimizing offloading positions: tasks are either executed locally at the IoT devices or offloaded to different edge servers, thereby causing different delays. Optimizing the offloading positions involves finding the optimal offloading position for each task that minimizes the time to complete all tasks(2)
Optimizing offloading moments: offloading tasks at different moments produces channel interference among IoT devices. Optimizing the offloading moments involves determining the optimal offloading moments to avoid channel interference and reduce the time of uploading tasksHerein, our goal is to find both (i) the offloading positionai,j at which task Ti,j is executed and (ii) the offloading moment STi,j at which Ti,j starts to be offloaded. We use Φa1,1,ST1,1,⋯,ai,j,STi,j,⋯,an,m,STn,m to represent the offloading strategy. Our goal is then to find the optimal offloading strategy that minimizes the total time to complete all tasks. Let Ψ denote the moment at which all tasks are completed, which is equivalent to the finishing moment of the final completed task, i.e.,
(9)Ψ=MaxSTi,j+ti,j,i∈1,.,n,j∈1,.,m.Therefore, we formulate the problem of TPD (temporal and positional computation offloading with dynamic and dependent tasks) mathematically as follows:(10)Opt.minΨ(11)s.t.STi,j,FTi,j∩STi′,j′,FTi′,j′=∅,∀ai,j=ai′,j′,i,i′∈1,n,j,j′∈1,m,(12)STi,j≥maxSTi′,j′+ti′,j′,Ti′,j′∈Pi,j.We seek the optimal offloading strategyΦ with the minimized Ψ (Equation (10)). However, there are two restrictions: (i) an edge server can only calculate one task at a time; therefore, the time intervals of two tasks that select the same server cannot overlap (Equation (11)); (ii) the limitation of dependencies means that a successor task can only start after all its predecessor tasks are completed, and its offloading moment must be later than the finishing moments of all its predecessors (Equation (12)).


### 3.4. Complexity Analysis of the Problem

Here, we analyze the complexity of the above optimization problem by comparing it with the flexible job-shop scheduling problem (FJSP), which is the problem of scheduling workpiece processing on machines. In the FJSP, a group of workpieces must be processed on a group of machines. Each workpiece involves multiple dependency-aware jobs, a machine can only process one job at a time, and jobs have different execution times on different machines. As a classic NP-hard problem [33, 34], the goal of the FJSP is to determine the execution machines and order of the jobs to reduce the time to complete all jobs.After abstraction, our optimization problem is similar to the FJSP. The applications running on the IoT devices can be regarded as workpieces, the tasks can be regarded as jobs, and the edge servers can be regarded as machines in the FJSP. Also, the constraints and optimization objectives of the two problems are the same. Therefore, our optimization problem of computation offloading can be regarded as a type of FJSP. However, our optimization problem is more complicated than the classic FJSP because we not only determine the offloading positions and order of the tasks but must also calculate the precise offloading moments, and we consider the communication time and channel interference. Therefore, the optimal offloading problem proposed by us is also an NP-hard problem.


## 3.1. Network Model

As shown in Figure2, we consider a typical multiuser and multiserver MEC system with n IoT devices, l nearby edge servers, and wireless access points such as macro base stations and small-cell base stations with relatively powerful and heterogeneous computation abilities. The IoT devices can offload tasks to any edge server through the base stations and the core network. The sets of IoT devices and edge servers are denoted as A=A1,A2,⋯,Ai,⋯,An and S=S1,S2,⋯,Sk,⋯,Sl, respectively. We suppose that each IoT device generates a set of computationally intensive tasks to be executed during the work. Let Ti,1,Ti,2,⋯,Ti,j,⋯,Ti,m denote the set of tasks from IoT device Ai, where Ti,j represents task j. For efficient computation offloading, we exploit the potential dependency correlation among the tasks [32]. As in the example in Figure 1(a), executing the data analysis task requires completion of the feature extraction task as a prerequisite. Therefore, we define the feature extraction task as the predecessor task of the data analysis task, and the data analysis task is its successor task.Figure 2
Typical multiuser and multiserver mobile edge computing (MEC) system.TaskTi,j can then be described by the five-tuple mi,j,ci,j,ai,j,Pi,j,Si,j, where the terms are as follows: (i) mi,j is the size of the input data for task execution (e.g., the program codes and input parameters); (ii) ci,j is the total number of CPU cycles required to accomplish task Ti,j; (iii) because each task can be either executed locally or offloaded to a nearby edge server, we use ai,j∈0∪S to denote the offloading position of task Ti,j, where ai,j=0 means that task Ti,j is executed locally on IoT device Ai and ai,j=k means that Ti,j is offloaded to edge server Sk for execution; (iv) Pi,j is the predecessor task set of Ti,j; and (v) Si,j is the successor task set. A task can start only after all its predecessors have been completed. STi,j is the offloading moment of Ti,j, and FTi,j is the finishing moment.


## 3.2. Communication and Computation Models

In this subsection, we introduce how to model the task delay, which can be divided into communication and computation parts. If tasks are executed by the IoT devices themselves, then only a computing delay is incurred; otherwise, the IoT devices select an edge server from the edge server setS for computation offloading, which incurs uploading, waiting, and computing delays. Next, we introduce the communication model followed by the computation model.Communication model: the communication channel quality changes constantly during the process of computation offloading. In [30, 31], the authors give a formula for calculating the task upload rate. Based on this, we introduce how to calculate the aforementioned communication delays in detail according to the time. pi,kt indicates whether device Ai is uploading tasks to edge server Sk at time t. If there is a task Ti,j such that ai,j=k and its uploading interval contains time t, then pi,kt=1, otherwise pi,kt=0. ri,kt denotes the data upload rate from device Ai to edge server Sk at time t and is given as
(1)ri,kt=Bklog21+qigi,kϖ+∑i′∈1,.,n,i′≠iqi′gi′,kpi′,kt,where Bk is the bandwidth of the communication channel connected to edge server Sk, qi is the transmission power of Ai, gi,j is the channel gain for the link between Ai and Sk, ϖ is the background noise, and ∑i′∈1,..,n,i′≠iqi′gi′,kpi′,kt is the wireless interference suffered from other IoT devices when Ai uploads tasks to Sk.Computation model: a computation task can be either handled locally or offloaded to an edge server for computing, which leads to two different delay computing methods.
(1)
Local computing: the task is handled on the IoT device itself, and there is only a computing delay in the process. fil is the computing capability of IoT device Ai, which represents the number of CPU cycles that Ai can calculate per second. Given the number of CPU cycles for task Ti,j, the delay ti,jl of Ti,j with local computing can be represented as(2)ti,jl=ci,jfil(2)
Edge computing: tasks are offloaded to edge servers for computing, and the process involves the following steps: the task is uploaded to the edge server; then, it is queued in the server for execution, and finally, the edge server computes the task to obtain the results. Therefore, these three steps produce a three-part delay (upload delay, queuing delay, and computing delay). The upload delay ti,jk,U of Ti,j from Ai to Sk is determined by the data upload rate ri,kt and the data volume mi,j. Therefore, ti,jk,U is calculated as(3)ti,jk,U=mi,jri,ktAfter arriving at the edge server,Ti,j may need to queue in the server for computing, and ti,jk,Q denotes the queuing delay of Ti,j on Sk. We use Qi,j to denote the task set that is queued in front of Ti,j on Sk. Therefore, ti,jk,Q is calculated as
(4)ti,jk,Q=∑Ti′,j′∈Qi,j:‍ci′,j′fke.fke is the computing capability of edge server Sk, and we calculate the computing delay ti,jk,C as
(5)ti,jk,C=ci,jfke.Inedge computing, the delay ti,jk of Ti,j comprises the uploading, queuing, and computing delays as
(6)ti,jk=ti,jk,U+ti,jk,Q+ti,jk,C.ti,j is the total delay of Ti,j and is denoted as
(7)ti,j=ti,jlifai,j=0,ti,jkifai,j=k.IfTi,j chooses local computing, then ti,j=ti,jl. If Ti,j chooses edge server Sk, then ti,j=ti,jk. Therefore, given STi,j and ai,j of the task, we calculate the finishing moment as
(8)FTi,j=STi,j+ti,j.


## 3.3. Problem Formulation

Herein, given the dependencies among tasks, the dynamics of the MEC system, and the multiuser wireless interference, we jointly optimize the task offloading position and moment.(1)
Optimizing offloading positions: tasks are either executed locally at the IoT devices or offloaded to different edge servers, thereby causing different delays. Optimizing the offloading positions involves finding the optimal offloading position for each task that minimizes the time to complete all tasks(2)
Optimizing offloading moments: offloading tasks at different moments produces channel interference among IoT devices. Optimizing the offloading moments involves determining the optimal offloading moments to avoid channel interference and reduce the time of uploading tasksHerein, our goal is to find both (i) the offloading positionai,j at which task Ti,j is executed and (ii) the offloading moment STi,j at which Ti,j starts to be offloaded. We use Φa1,1,ST1,1,⋯,ai,j,STi,j,⋯,an,m,STn,m to represent the offloading strategy. Our goal is then to find the optimal offloading strategy that minimizes the total time to complete all tasks. Let Ψ denote the moment at which all tasks are completed, which is equivalent to the finishing moment of the final completed task, i.e.,
(9)Ψ=MaxSTi,j+ti,j,i∈1,.,n,j∈1,.,m.Therefore, we formulate the problem of TPD (temporal and positional computation offloading with dynamic and dependent tasks) mathematically as follows:(10)Opt.minΨ(11)s.t.STi,j,FTi,j∩STi′,j′,FTi′,j′=∅,∀ai,j=ai′,j′,i,i′∈1,n,j,j′∈1,m,(12)STi,j≥maxSTi′,j′+ti′,j′,Ti′,j′∈Pi,j.We seek the optimal offloading strategyΦ with the minimized Ψ (Equation (10)). However, there are two restrictions: (i) an edge server can only calculate one task at a time; therefore, the time intervals of two tasks that select the same server cannot overlap (Equation (11)); (ii) the limitation of dependencies means that a successor task can only start after all its predecessor tasks are completed, and its offloading moment must be later than the finishing moments of all its predecessors (Equation (12)).


## 3.4. Complexity Analysis of the Problem

Here, we analyze the complexity of the above optimization problem by comparing it with the flexible job-shop scheduling problem (FJSP), which is the problem of scheduling workpiece processing on machines. In the FJSP, a group of workpieces must be processed on a group of machines. Each workpiece involves multiple dependency-aware jobs, a machine can only process one job at a time, and jobs have different execution times on different machines. As a classic NP-hard problem [33, 34], the goal of the FJSP is to determine the execution machines and order of the jobs to reduce the time to complete all jobs.After abstraction, our optimization problem is similar to the FJSP. The applications running on the IoT devices can be regarded as workpieces, the tasks can be regarded as jobs, and the edge servers can be regarded as machines in the FJSP. Also, the constraints and optimization objectives of the two problems are the same. Therefore, our optimization problem of computation offloading can be regarded as a type of FJSP. However, our optimization problem is more complicated than the classic FJSP because we not only determine the offloading positions and order of the tasks but must also calculate the precise offloading moments, and we consider the communication time and channel interference. Therefore, the optimal offloading problem proposed by us is also an NP-hard problem.


## 4. Task Offloading Strategy

In this section, we introduce the detailed task-offloading strategy for our problem. We begin by constructing a directed acyclic graph (DAG) according to the dependency correlation of tasks and proposing a BCN method to mark the criticality of all tasks. We then devise the online CTF offloading algorithm to minimize the time to complete all tasks.


### 4.1. Marking of Task Criticality

The dependency correlation among tasks means that we can first construct a DAG, as the example shown in Figure3, to present their topological structure. The nodes in the DAG represent tasks generated by IoT devices, and the directed edges denote the specific dependency relations between tasks. A node is weighted by the number of CPU cycles required by the corresponding task, and the length of a path in the DAG is the sum of the weights of the nodes on the path. The critical path is the longest path in the DAG, and the completion times of tasks on the critical path have a direct effect on the time Ψ.Figure 3
Example of topological diagram of tasks.Intuitively, we can find the critical path and offload tasks on it to edge servers with sufficient computing capability to reduceΨ. However, searching for the longest path in the DAG using traditional methods such as the Floyd or Dijkstra algorithm would generally incur a large computation time overhead. Also, the critical path will change frequently with the emergence of new tasks. Therefore, we can transform the problem of finding the critical path into marking the criticality of each task. A task with a greater impact on Ψ has higher criticality, and we use γi,j to denote the criticality of task Ti,j. Next, we introduce the method for calculating the criticality of tasks.Tasks without successors are calledexit tasks, such as T3, T4, and T6 in Figure 3, and the path from a task to an exit tasks is called an influence path. As shown in Figure 3, T2 has two influence paths such as (T2⟶T4) and (T2⟶T5⟶T6). The length of an influence path of T2 is the sum of CPU cycles required by tasks on that path and indicates the amount of calculation affected by T2. We reason that a task that affects a greater amount of calculation is more critical, so we define the criticality of a task as the length of its longest influence path.On this basis, we propose a BCN method for calculating the length of a task’s longest influence path and marking the task’s criticality with less time overhead. The criticality of anexit task is the number of CPU cycles that it requires. The criticality of a nonexit task depends on its successor tasks and is calculated as
(13)γi,j=ci,j+maxγi′,j′,Ti′,j′∈Pi,j.In this way, we can mark the criticality of all tasks. When IoT devices generate new tasks (e.g.,T7), thereby changing the task topology, the BCN method can update the criticality of affected tasks with a small overhead. As an example in Figure 4, T7 is generated and added to the task topology, thereby affecting its predecessor tasks. Therefore, the BCN method recalculates the criticality of T4 by means of Equation (13). In this way, the criticality of the other affected tasks (T1,T2), as indicated by the arrows in Figure 4, is updated.Figure 4
A new task is added to the topological diagram of tasks.


### 4.2. CTF Algorithm

Based on the criticality of tasks, we propose the CTF algorithm. In a dynamic MEC system, the CTF algorithm will monitor the tasks’ criticality in real time and find the optimal offloading position and moment for each task to minimizeΨ. The pseudocode of the CTF algorithm is shown in Algorithm 1 and has four stages.
(1)
State divisionAlgorithm 1: Critical task first (CTF) algorithm.
Input:Information about tasks, edge servers, and IoT devicesOutput: Offloading strategy with minimized Ψ1 Put tasks into three types of queues according to task status. Use the BCN method to mark the criticality of tasks. Sort ready tasks from high to low according to criticality. all tasksTi,j in ready queue do2for all Sk in Sdo3   CalculateSTi,jk and FTi,jk on Sk4end5  Choose the edge server with the smallestFTi,jk Calculate STi,jl and FTi,jl on local IoT device FTi,jl < FTi,jkthen6FTi,j=FTi,jl, STi,j=STi,jl, ai,j=07end8else9FTi,j=FTi,jk, STi,j=STi,jk, ai,j=k10end11end12 Go back to step 2 when a new task or new ready task is generated.First, the CTF algorithm collects information about all the tasks and divides them (line 1) according to the following three states.
(1)
Waiting state: a task whose predecessor tasks have not been completed(2)
Ready state: a task whose predecessor tasks have been completed but have not been offloaded(3)
Computing state: a task that has been offloaded and is now computingCorrespondingly, the CTF algorithm generates three types of task queues: the waiting queue, the ready queue, and the computing queue. As shown in Figure5, tasks generated by IoT devices are first put into the waiting queue. After all its predecessors have been completed, a task is moved from the waiting queue to the ready queue. When its offloading moment comes, a ready task is offloaded for computing and then put into the computing queue. Finally, the computation results of tasks are obtained. After the tasks have been divided into the three states, the CTF algorithm uses the BCN method to mark their criticality (line 2).
(2)
Sorting of ready tasksFigure 5
Transformation of the three task states.Because waiting tasks are not yet ready for computing and computing tasks have been offloaded, we only need to determine when and where the tasks in the ready queue should be offloaded. First, the CTF algorithm sorts the tasks according to their criticality (line 3). Based on the principle of critical tasks first, the CTF algorithm decides the offloading positions and moments for critical tasks first and then for other tasks. If two tasks choose the same edge server, the one with the higher criticality is offloaded first, and the other tasks must wait.
(3)
Deciding on task offloadingIn the process of computation offloading, the CTF algorithm calculates the offloading and finishing moments of the task on each edge server or locally and chooses the position with minimized finishing moment as the final result. Next, usingTi,j as an example, we introduce how the CTF algorithm calculates the offloading and finishing moments on edge servers (taking Sk as an example) for ready tasks at time tnow (lines 5–8). The detailed calculation process can be divided into the following three cases.Case 1.
Sk is idle, and no more-critical tasks have chosen it. In this case, task Ti,j can be offloaded directly; the offloading moment on Sk is STi,jk=tnow, and Ti,j is calculated after it arrives on the edge server, as in Figure 6. Therefore, the finishing moment of Ti,j on Sk is FTi,jk=tnow+ti,jk,U+ti,jk,C.Case 2.
A task is being executed onSk but no more-critical tasks have chosen it. As shown in Figure 7, we suppose that Ta,b is the task being executed on Sk. We calculate the offloading moment of Ti,j as STi,jk=FTa,bk−ti,jk,U. Therefore, Ti,j can be calculated as soon as it arrives at Sk, and its finishing time is FTi,jk=FTa,bk+ti,jk,C.Case 3.
A task is being executed onSk but some more-critical tasks have also chosen it. Although task Ta,b is being executed, multiple more-critical tasks have selected Sk, so Ti,j must wait for those tasks to complete before it can be executed on the edge server (Figure 8). We use φi,j to represent this more-critical task set. The finishing moment of task Ti,j is calculated as
(14)FTi,jk=FTa,bk+∑Ti′,j′∈φi,jti′,j′k,C+ti,jk,C,and the offloading moment of Ti,j is STi,jk=FTi,jk−ti,jk,C−ti,jk,U.Figure 6
First case of the calculation.Figure 7
Second case of the calculation.Figure 8
Third case of the calculation.As shown above, the CTF algorithm controls the offloading moments of tasks so that they (i) do not need to wait on a server, thereby avoiding waiting delay and (ii) are uploaded separately, thereby avoiding channel interference from other IoT devices. Therefore, the upload rate of taskTi,j becomes
(15)ri,kt=Bklog21+qigi,kϖ.Finishing moment on local IoT device: On the local IoT device, taskTi,j can be calculated directly (line 9), and the offloading moment is then STi,jl=tnow and FTi,jl=STi,jl+ti,jl.After calculating the finishing moments ofTi,j on all edge servers and locally, the CTF algorithm chooses the offloading position with minimized FTi,j, and the offloading moment is calculated according to the offloading position (lines 10–15). Therefore, we can obtain the offloading strategy for ready tasks at time tnow.
(4)
Updating of offloading strategyIn a dynamic MEC system, the status of tasks changes over time, thereby decreasing the effectiveness of the offloading strategy. In the following two situations, the offloading strategy for ready tasks at timetnow may become suboptimal and require recalculation: (i) IoT devices generate new waiting tasks, thereby changing the task topology and thus the task criticality; (ii) new ready tasks are added to the ready queue but the offloading strategy at time tnow does not account for them.As an online algorithm, the CTF algorithm updates the offloading strategy for ready tasks (line 17) in time to ensure the best effect. After a new waiting task is generated, the CTF algorithm first uses the BCN method to update the criticality of the affected tasks and then recalculates the best offloading position and moment for each ready task. If only new ready tasks are generated, then the CTF algorithm only needs to recalculate the offloading strategy for ready tasks.


### 4.3. Complexity Analysis of the CTF Algorithm

Here, we take calculating the finishing moments of tasks as the basic calculation for analyzing the complexity of the CTF algorithm. Suppose that the MEC system hask edge servers and that the IoT devices generate n tasks in total, with Q denoting the number of ready tasks. When deciding the offloading positions of ready tasks, the CTF algorithm calculates the finishing moment of the ready task on each edge server and locally, so it does k+1 basic calculations. Therefore, finding the offloading strategy for all ready tasks requires Q×k+1 basic calculations.In the worst case, tasks are generated one at a time and no ready tasks are executed. Therefore, every time a new task is generated by an IoT device and put into the ready queue, the CTF algorithm updates the offloading strategy of all ready tasks. The number of tasks in the ready queue increases gradually from 1 ton, thereby requiring 1+2+,⋯,+nk+1=n2+n/2k+1 basic calculations in total.As analyzed above, in a dynamic MEC system containingk edge servers, the CTF algorithm offloads n tasks and requires n2+n/2k+1 basic calculations at most. In actual situations, tasks are rarely generated one at a time, and the number of tasks in the ready queue decreases with offloading. Therefore, the actual number of calculations is much less than n2+n/2k+1. Every time an IoT device generates a new task, the CTF algorithm requires only Q×k+1 basic calculations. However, in some other methods (e.g., noncooperative game methods, genetic algorithms), once a new task is generated, the offloading strategy for all tasks must be recalculated, and the process of iterative convergence is very complicated, thereby generating a large time overhead.


## 4.1. Marking of Task Criticality

The dependency correlation among tasks means that we can first construct a DAG, as the example shown in Figure3, to present their topological structure. The nodes in the DAG represent tasks generated by IoT devices, and the directed edges denote the specific dependency relations between tasks. A node is weighted by the number of CPU cycles required by the corresponding task, and the length of a path in the DAG is the sum of the weights of the nodes on the path. The critical path is the longest path in the DAG, and the completion times of tasks on the critical path have a direct effect on the time Ψ.Figure 3
Example of topological diagram of tasks.Intuitively, we can find the critical path and offload tasks on it to edge servers with sufficient computing capability to reduceΨ. However, searching for the longest path in the DAG using traditional methods such as the Floyd or Dijkstra algorithm would generally incur a large computation time overhead. Also, the critical path will change frequently with the emergence of new tasks. Therefore, we can transform the problem of finding the critical path into marking the criticality of each task. A task with a greater impact on Ψ has higher criticality, and we use γi,j to denote the criticality of task Ti,j. Next, we introduce the method for calculating the criticality of tasks.Tasks without successors are calledexit tasks, such as T3, T4, and T6 in Figure 3, and the path from a task to an exit tasks is called an influence path. As shown in Figure 3, T2 has two influence paths such as (T2⟶T4) and (T2⟶T5⟶T6). The length of an influence path of T2 is the sum of CPU cycles required by tasks on that path and indicates the amount of calculation affected by T2. We reason that a task that affects a greater amount of calculation is more critical, so we define the criticality of a task as the length of its longest influence path.On this basis, we propose a BCN method for calculating the length of a task’s longest influence path and marking the task’s criticality with less time overhead. The criticality of anexit task is the number of CPU cycles that it requires. The criticality of a nonexit task depends on its successor tasks and is calculated as
(13)γi,j=ci,j+maxγi′,j′,Ti′,j′∈Pi,j.In this way, we can mark the criticality of all tasks. When IoT devices generate new tasks (e.g.,T7), thereby changing the task topology, the BCN method can update the criticality of affected tasks with a small overhead. As an example in Figure 4, T7 is generated and added to the task topology, thereby affecting its predecessor tasks. Therefore, the BCN method recalculates the criticality of T4 by means of Equation (13). In this way, the criticality of the other affected tasks (T1,T2), as indicated by the arrows in Figure 4, is updated.Figure 4
A new task is added to the topological diagram of tasks.


## 4.2. CTF Algorithm

Based on the criticality of tasks, we propose the CTF algorithm. In a dynamic MEC system, the CTF algorithm will monitor the tasks’ criticality in real time and find the optimal offloading position and moment for each task to minimizeΨ. The pseudocode of the CTF algorithm is shown in Algorithm 1 and has four stages.
(1)
State divisionAlgorithm 1: Critical task first (CTF) algorithm.
Input:Information about tasks, edge servers, and IoT devicesOutput: Offloading strategy with minimized Ψ1 Put tasks into three types of queues according to task status. Use the BCN method to mark the criticality of tasks. Sort ready tasks from high to low according to criticality. all tasksTi,j in ready queue do2for all Sk in Sdo3   CalculateSTi,jk and FTi,jk on Sk4end5  Choose the edge server with the smallestFTi,jk Calculate STi,jl and FTi,jl on local IoT device FTi,jl < FTi,jkthen6FTi,j=FTi,jl, STi,j=STi,jl, ai,j=07end8else9FTi,j=FTi,jk, STi,j=STi,jk, ai,j=k10end11end12 Go back to step 2 when a new task or new ready task is generated.First, the CTF algorithm collects information about all the tasks and divides them (line 1) according to the following three states.
(1)
Waiting state: a task whose predecessor tasks have not been completed(2)
Ready state: a task whose predecessor tasks have been completed but have not been offloaded(3)
Computing state: a task that has been offloaded and is now computingCorrespondingly, the CTF algorithm generates three types of task queues: the waiting queue, the ready queue, and the computing queue. As shown in Figure5, tasks generated by IoT devices are first put into the waiting queue. After all its predecessors have been completed, a task is moved from the waiting queue to the ready queue. When its offloading moment comes, a ready task is offloaded for computing and then put into the computing queue. Finally, the computation results of tasks are obtained. After the tasks have been divided into the three states, the CTF algorithm uses the BCN method to mark their criticality (line 2).
(2)
Sorting of ready tasksFigure 5
Transformation of the three task states.Because waiting tasks are not yet ready for computing and computing tasks have been offloaded, we only need to determine when and where the tasks in the ready queue should be offloaded. First, the CTF algorithm sorts the tasks according to their criticality (line 3). Based on the principle of critical tasks first, the CTF algorithm decides the offloading positions and moments for critical tasks first and then for other tasks. If two tasks choose the same edge server, the one with the higher criticality is offloaded first, and the other tasks must wait.
(3)
Deciding on task offloadingIn the process of computation offloading, the CTF algorithm calculates the offloading and finishing moments of the task on each edge server or locally and chooses the position with minimized finishing moment as the final result. Next, usingTi,j as an example, we introduce how the CTF algorithm calculates the offloading and finishing moments on edge servers (taking Sk as an example) for ready tasks at time tnow (lines 5–8). The detailed calculation process can be divided into the following three cases.Case 1.
Sk is idle, and no more-critical tasks have chosen it. In this case, task Ti,j can be offloaded directly; the offloading moment on Sk is STi,jk=tnow, and Ti,j is calculated after it arrives on the edge server, as in Figure 6. Therefore, the finishing moment of Ti,j on Sk is FTi,jk=tnow+ti,jk,U+ti,jk,C.Case 2.
A task is being executed onSk but no more-critical tasks have chosen it. As shown in Figure 7, we suppose that Ta,b is the task being executed on Sk. We calculate the offloading moment of Ti,j as STi,jk=FTa,bk−ti,jk,U. Therefore, Ti,j can be calculated as soon as it arrives at Sk, and its finishing time is FTi,jk=FTa,bk+ti,jk,C.Case 3.
A task is being executed onSk but some more-critical tasks have also chosen it. Although task Ta,b is being executed, multiple more-critical tasks have selected Sk, so Ti,j must wait for those tasks to complete before it can be executed on the edge server (Figure 8). We use φi,j to represent this more-critical task set. The finishing moment of task Ti,j is calculated as
(14)FTi,jk=FTa,bk+∑Ti′,j′∈φi,jti′,j′k,C+ti,jk,C,and the offloading moment of Ti,j is STi,jk=FTi,jk−ti,jk,C−ti,jk,U.Figure 6
First case of the calculation.Figure 7
Second case of the calculation.Figure 8
Third case of the calculation.As shown above, the CTF algorithm controls the offloading moments of tasks so that they (i) do not need to wait on a server, thereby avoiding waiting delay and (ii) are uploaded separately, thereby avoiding channel interference from other IoT devices. Therefore, the upload rate of taskTi,j becomes
(15)ri,kt=Bklog21+qigi,kϖ.Finishing moment on local IoT device: On the local IoT device, taskTi,j can be calculated directly (line 9), and the offloading moment is then STi,jl=tnow and FTi,jl=STi,jl+ti,jl.After calculating the finishing moments ofTi,j on all edge servers and locally, the CTF algorithm chooses the offloading position with minimized FTi,j, and the offloading moment is calculated according to the offloading position (lines 10–15). Therefore, we can obtain the offloading strategy for ready tasks at time tnow.
(4)
Updating of offloading strategyIn a dynamic MEC system, the status of tasks changes over time, thereby decreasing the effectiveness of the offloading strategy. In the following two situations, the offloading strategy for ready tasks at timetnow may become suboptimal and require recalculation: (i) IoT devices generate new waiting tasks, thereby changing the task topology and thus the task criticality; (ii) new ready tasks are added to the ready queue but the offloading strategy at time tnow does not account for them.As an online algorithm, the CTF algorithm updates the offloading strategy for ready tasks (line 17) in time to ensure the best effect. After a new waiting task is generated, the CTF algorithm first uses the BCN method to update the criticality of the affected tasks and then recalculates the best offloading position and moment for each ready task. If only new ready tasks are generated, then the CTF algorithm only needs to recalculate the offloading strategy for ready tasks.


## 4.3. Complexity Analysis of the CTF Algorithm

Here, we take calculating the finishing moments of tasks as the basic calculation for analyzing the complexity of the CTF algorithm. Suppose that the MEC system hask edge servers and that the IoT devices generate n tasks in total, with Q denoting the number of ready tasks. When deciding the offloading positions of ready tasks, the CTF algorithm calculates the finishing moment of the ready task on each edge server and locally, so it does k+1 basic calculations. Therefore, finding the offloading strategy for all ready tasks requires Q×k+1 basic calculations.In the worst case, tasks are generated one at a time and no ready tasks are executed. Therefore, every time a new task is generated by an IoT device and put into the ready queue, the CTF algorithm updates the offloading strategy of all ready tasks. The number of tasks in the ready queue increases gradually from 1 ton, thereby requiring 1+2+,⋯,+nk+1=n2+n/2k+1 basic calculations in total.As analyzed above, in a dynamic MEC system containingk edge servers, the CTF algorithm offloads n tasks and requires n2+n/2k+1 basic calculations at most. In actual situations, tasks are rarely generated one at a time, and the number of tasks in the ready queue decreases with offloading. Therefore, the actual number of calculations is much less than n2+n/2k+1. Every time an IoT device generates a new task, the CTF algorithm requires only Q×k+1 basic calculations. However, in some other methods (e.g., noncooperative game methods, genetic algorithms), once a new task is generated, the offloading strategy for all tasks must be recalculated, and the process of iterative convergence is very complicated, thereby generating a large time overhead.


## 5. Experiments and Evaluation

In this section, we report simulation experiments conducted to assess how the CTF algorithm performs with static and dynamic MEC systems. We also compare the CTF algorithm with the DEFO algorithm [31] and two other classic algorithms, i.e., the random algorithm and the first-come first-served (FCFS) algorithm. The random algorithm chooses offloading positions and moments randomly for tasks, whereas in the FCFS algorithm, tasks that are generated first are sent to the nearest edge server and executed first. The design of the simulation experiments and analysis of the results are shown below.


### 5.1. Experimental Settings

The simulation experiments involved a multiuser and multiserver MEC system with the parameter settings given in Table3. The channel bandwidth of each base station was 20MHz±20%, and the computing capability of each edge server was 10GHz±20%. The computing capability of the IoT devices was 1GHz±20%, and the transmission power of each IoT device was 100mW±20%. Considering the mobility of IoT devices, the distance l between an IoT device and an edge servers was 20–50 m and changed continuously. The channel gain gi,k from Ai to Sk is gi,k=lα, where α is the pass loss factor, and we set α=4. For tasks generated by IoT devices, the task data volume was 1000kB±50%, and the number of CPU cycles required by a task was 1000–5000 megacycles. The background noise was −100 dBm, and the dependencies among tasks were generated randomly.Table 3
Experimental parameters.
ParameterValueBase-station bandwidth20MHz±20%Computing capability of edge servers10GHz±20%Computing capability of IoT devices1GHz±20%Transmission power of IoT devices100mW±20%Distance from IoT device to each server20–50 mPass loss factor4Task data volume1000kB±50%No. of CPU cycles required for task1000–5000 megacyclesBackground noise−100 dBm


### 5.2. Effects of Different Algorithms with Static MEC System

Here, we begin by assessing the performances of the four algorithms with a static MEC system without generating new tasks. To explore how different factors (numbers of tasks, IoT devices, and edge servers) influence the algorithms, we conducted simulation experiments in the following three scenarios.(1)
MEC system with different numbers of tasksIn this experiment, we studied how different task numbers affectΨ. To prevent the influence of other factors, we set 15 edge servers and 20 IoT devices. The number of tasks in the MEC system was 30 initially and then was increased gradually to 200. The Ψ of the offloading strategies generated by the four algorithms varied with the task number, and the results are shown in Figures 9(a) and 9(b).Figure 9
Effects of different algorithms with a static MEC system.
(a)
Ψ for different numbers of tasks (4 algorithms)(b)
Ψ for different numbers of tasks (2 algorithms)(c)
Ψ for different numbers of IoT devices (4 algorithms)(d)
Ψ for different numbers of IoT devices (2 algorithms)(e)
Ψ for different numbers of edge servers (4 algorithms)(f)
Ψ for different numbers of edge servers (2 algorithms)Figure9(a) shows that as the number of tasks increases, the computation resources become insufficient, and the Ψ values of the four algorithms increase constantly. In particular, the Ψ growth rates of the FCFS and random algorithms are very high, and their Ψ values are much higher than those of the CTF and DEFO algorithms. For clarity, we plot the results of the CTF and DEFO algorithms separately in Figure 9(b). The CTF algorithm performs better when facing a different number of tasks, and its Ψ values are only approximately half of those for the DEFO algorithm, which shows that the CTF algorithm adapts well to the MEC system with more tasks.
(2)
MEC system with different numbers of IoT devicesIoT devices are the sources of tasks in the MEC system, so it is necessary to study how their number influencesΨ. In this experiment, we set 15 edge servers. Because task number is related to the number of IoT devices, we set the former as six times the latter. Starting with a MEC system with only 15 IoT devices, we gradually increased that number to 30, and the results of the experiment are shown in Figures 9(c) and 9(d).As their number increases, IoT devices compete more fiercely for computing resources, thereby increasing the task execution delay. TheΨ values of the four algorithms continue to increase as the number of IoT devices is increased. However, the experimental results show that the Ψ values for the CTF algorithm are 30% of those for the DEFO algorithm when the number of IoT devices exceeds 18 and remain low for the MEC system with different numbers of IoT devices.
(3)
MEC system with different numbers of edge serversAs an important computing resource in a MEC system, the number of edge servers has a significant effect on the time to complete all tasks. Therefore, we explore how the number of edge servers influencesΨ. In this experiment, there were 30 IoT devices and 200 tasks. The number of edge servers was 5 initially and was increased gradually to 20, and the results of the experiment are shown in Figures 9(e) and 9(f).The results show thatΨ can be reduced significantly by having more edge servers. In particular, the Ψ values for the random, FCFS, and DEFO algorithms decrease significantly. By contrast, the CTF algorithm performs better and is more stable in a MEC system with different numbers of servers.From the three simulation experiments above, we conclude that the CTF algorithm can reduceΨ significantly in different static MEC systems.


### 5.3. Effects of Different Algorithms with Dynamic MEC System

Here, we report simulation experiments conducted to assess the performances of the four algorithms with a dynamic MEC system. To build such a system, we added new tasks continuously to simulate the process of IoT devices generating tasks while the algorithms are running. First, we constructed an initial MEC system with 15 edge servers, 30 IoT devices, and 200 tasks. During the execution of the algorithms, we added 20 new tasks to the MEC system in each round. As the number of rounds increased, the MEC system became more dynamic, and the results of the experiment with different numbers of rounds are shown in Figure10.Figure 10
Effects of different algorithms with a dynamic MEC system.
(a)
Ψ for different numbers of rounds (4 algorithms)(b)
Ψ for different numbers of rounds (2 algorithms)(c)
Average task delay for different numbers of rounds (4 algorithms)The enhanced dynamics of the MEC system decrease the effectiveness of the offloading strategy. Figure10(a) shows that as the number of rounds increases, the Ψ values of each algorithm increase significantly, but those for the CTF algorithm are lower, as is their growth rate. In particular, the Ψ values for the CTF algorithm are only 60% of those for the DEFO algorithm (Figure 10(b)). In addition to Ψ, the average task delay is also affected. Figure 10(c) shows that as the number of rounds increases, so does the average task delay. However, the average task delay with the CTF algorithm is significantly lower than that with the other three algorithms, which means that the CTF algorithm adapts better to the dynamic MEC system.In a dynamic MEC system, the CTF algorithm adjusts the offloading positions and moments of tasks continuously to maintain the most effective offloading strategy. Figure11 shows the numbers of changes in offloading positions and moments of tasks made by the CTF algorithm in different rounds. As the number of rounds increases, the MEC system becomes more dynamic, and the CTF algorithm adjusts the offloading strategy frequently to ensure the best results.Figure 11
Numbers of decision changes in different rounds.An online algorithm incurs a short time overhead to update the offloading strategy in a dynamic MEC system. Here, we study the time overhead of the DEFO and CTF algorithms with the dynamic MEC system. The DEFO and CTF algorithms were both programmed in Python on a Windows 10 platform and tested in an Intel 2.60 GHz, 16 GB memory environment. We measured the time overhead of running the two algorithms in different rounds, as given in Table4. Clearly, the time overhead of the CTF algorithm under different rounds is short and stable. With 10 rounds, the time overhead of the DEFO algorithm is 100 times that of the CTF algorithm. Compared with Ψ, the time overhead incurred by the CTF algorithm is acceptable, whereas that for the DEFO algorithm is too long to deal with the dynamic MEC system. Therefore, the CTF algorithm can update the offloading strategy in the dynamic MEC system with less time overhead and deliver better results.Table 4
Time overhead andΨ of DEFO and CTF algorithms.
Round12345678910Time overhead of CTF (s)0.811.301.161.191.231.301.431.441.271.38Time overhead of DEFO(s)23.1830.8536.4242.0760.2252.9370.68105.41106.22132.66Ψ of CTF (s)6.228.0710.7110.7912.0112.5015.1816.7618.4720.60Ψ of DEFO (s)7.3211.0513.5618.4520.86 s22.0325.4528.2430.9334.91


## 5.1. Experimental Settings

The simulation experiments involved a multiuser and multiserver MEC system with the parameter settings given in Table3. The channel bandwidth of each base station was 20MHz±20%, and the computing capability of each edge server was 10GHz±20%. The computing capability of the IoT devices was 1GHz±20%, and the transmission power of each IoT device was 100mW±20%. Considering the mobility of IoT devices, the distance l between an IoT device and an edge servers was 20–50 m and changed continuously. The channel gain gi,k from Ai to Sk is gi,k=lα, where α is the pass loss factor, and we set α=4. For tasks generated by IoT devices, the task data volume was 1000kB±50%, and the number of CPU cycles required by a task was 1000–5000 megacycles. The background noise was −100 dBm, and the dependencies among tasks were generated randomly.Table 3
Experimental parameters.
ParameterValueBase-station bandwidth20MHz±20%Computing capability of edge servers10GHz±20%Computing capability of IoT devices1GHz±20%Transmission power of IoT devices100mW±20%Distance from IoT device to each server20–50 mPass loss factor4Task data volume1000kB±50%No. of CPU cycles required for task1000–5000 megacyclesBackground noise−100 dBm


## 5.2. Effects of Different Algorithms with Static MEC System

Here, we begin by assessing the performances of the four algorithms with a static MEC system without generating new tasks. To explore how different factors (numbers of tasks, IoT devices, and edge servers) influence the algorithms, we conducted simulation experiments in the following three scenarios.(1)
MEC system with different numbers of tasksIn this experiment, we studied how different task numbers affectΨ. To prevent the influence of other factors, we set 15 edge servers and 20 IoT devices. The number of tasks in the MEC system was 30 initially and then was increased gradually to 200. The Ψ of the offloading strategies generated by the four algorithms varied with the task number, and the results are shown in Figures 9(a) and 9(b).Figure 9
Effects of different algorithms with a static MEC system.
(a)
Ψ for different numbers of tasks (4 algorithms)(b)
Ψ for different numbers of tasks (2 algorithms)(c)
Ψ for different numbers of IoT devices (4 algorithms)(d)
Ψ for different numbers of IoT devices (2 algorithms)(e)
Ψ for different numbers of edge servers (4 algorithms)(f)
Ψ for different numbers of edge servers (2 algorithms)Figure9(a) shows that as the number of tasks increases, the computation resources become insufficient, and the Ψ values of the four algorithms increase constantly. In particular, the Ψ growth rates of the FCFS and random algorithms are very high, and their Ψ values are much higher than those of the CTF and DEFO algorithms. For clarity, we plot the results of the CTF and DEFO algorithms separately in Figure 9(b). The CTF algorithm performs better when facing a different number of tasks, and its Ψ values are only approximately half of those for the DEFO algorithm, which shows that the CTF algorithm adapts well to the MEC system with more tasks.
(2)
MEC system with different numbers of IoT devicesIoT devices are the sources of tasks in the MEC system, so it is necessary to study how their number influencesΨ. In this experiment, we set 15 edge servers. Because task number is related to the number of IoT devices, we set the former as six times the latter. Starting with a MEC system with only 15 IoT devices, we gradually increased that number to 30, and the results of the experiment are shown in Figures 9(c) and 9(d).As their number increases, IoT devices compete more fiercely for computing resources, thereby increasing the task execution delay. TheΨ values of the four algorithms continue to increase as the number of IoT devices is increased. However, the experimental results show that the Ψ values for the CTF algorithm are 30% of those for the DEFO algorithm when the number of IoT devices exceeds 18 and remain low for the MEC system with different numbers of IoT devices.
(3)
MEC system with different numbers of edge serversAs an important computing resource in a MEC system, the number of edge servers has a significant effect on the time to complete all tasks. Therefore, we explore how the number of edge servers influencesΨ. In this experiment, there were 30 IoT devices and 200 tasks. The number of edge servers was 5 initially and was increased gradually to 20, and the results of the experiment are shown in Figures 9(e) and 9(f).The results show thatΨ can be reduced significantly by having more edge servers. In particular, the Ψ values for the random, FCFS, and DEFO algorithms decrease significantly. By contrast, the CTF algorithm performs better and is more stable in a MEC system with different numbers of servers.From the three simulation experiments above, we conclude that the CTF algorithm can reduceΨ significantly in different static MEC systems.


## 5.3. Effects of Different Algorithms with Dynamic MEC System

Here, we report simulation experiments conducted to assess the performances of the four algorithms with a dynamic MEC system. To build such a system, we added new tasks continuously to simulate the process of IoT devices generating tasks while the algorithms are running. First, we constructed an initial MEC system with 15 edge servers, 30 IoT devices, and 200 tasks. During the execution of the algorithms, we added 20 new tasks to the MEC system in each round. As the number of rounds increased, the MEC system became more dynamic, and the results of the experiment with different numbers of rounds are shown in Figure10.Figure 10
Effects of different algorithms with a dynamic MEC system.
(a)
Ψ for different numbers of rounds (4 algorithms)(b)
Ψ for different numbers of rounds (2 algorithms)(c)
Average task delay for different numbers of rounds (4 algorithms)The enhanced dynamics of the MEC system decrease the effectiveness of the offloading strategy. Figure10(a) shows that as the number of rounds increases, the Ψ values of each algorithm increase significantly, but those for the CTF algorithm are lower, as is their growth rate. In particular, the Ψ values for the CTF algorithm are only 60% of those for the DEFO algorithm (Figure 10(b)). In addition to Ψ, the average task delay is also affected. Figure 10(c) shows that as the number of rounds increases, so does the average task delay. However, the average task delay with the CTF algorithm is significantly lower than that with the other three algorithms, which means that the CTF algorithm adapts better to the dynamic MEC system.In a dynamic MEC system, the CTF algorithm adjusts the offloading positions and moments of tasks continuously to maintain the most effective offloading strategy. Figure11 shows the numbers of changes in offloading positions and moments of tasks made by the CTF algorithm in different rounds. As the number of rounds increases, the MEC system becomes more dynamic, and the CTF algorithm adjusts the offloading strategy frequently to ensure the best results.Figure 11
Numbers of decision changes in different rounds.An online algorithm incurs a short time overhead to update the offloading strategy in a dynamic MEC system. Here, we study the time overhead of the DEFO and CTF algorithms with the dynamic MEC system. The DEFO and CTF algorithms were both programmed in Python on a Windows 10 platform and tested in an Intel 2.60 GHz, 16 GB memory environment. We measured the time overhead of running the two algorithms in different rounds, as given in Table4. Clearly, the time overhead of the CTF algorithm under different rounds is short and stable. With 10 rounds, the time overhead of the DEFO algorithm is 100 times that of the CTF algorithm. Compared with Ψ, the time overhead incurred by the CTF algorithm is acceptable, whereas that for the DEFO algorithm is too long to deal with the dynamic MEC system. Therefore, the CTF algorithm can update the offloading strategy in the dynamic MEC system with less time overhead and deliver better results.Table 4
Time overhead andΨ of DEFO and CTF algorithms.
Round12345678910Time overhead of CTF (s)0.811.301.161.191.231.301.431.441.271.38Time overhead of DEFO(s)23.1830.8536.4242.0760.2252.9370.68105.41106.22132.66Ψ of CTF (s)6.228.0710.7110.7912.0112.5015.1816.7618.4720.60Ψ of DEFO (s)7.3211.0513.5618.4520.86 s22.0325.4528.2430.9334.91


## 6. Conclusion

Herein, we studied the problem of temporal and positional computation offloading in a dynamic MEC system with dependent tasks. Unlike previous studies, we also considered the impact of dependencies on the offloading positions of tasks and calculated the offloading moments of tasks accurately to reduce channel interference. To cope with dynamic tasks, we proposed the CTF algorithm, which updates the offloading strategy in real time to ensure the most effective computation offloading. Simulation experiments were conducted, and the results showed that the CTF algorithm reduces significantly the time to complete all tasks and incurs less time overhead.



---

*Source: 3877285-2021-11-10.xml*