# Energy-Efficient Task Migration and Path Planning in UAV-Enabled Mobile Edge Computing System

Authors: Can Gong; Li Wei; Deliang Gong; Tiantian Li; Fang Feng
Journal: Complexity
 (2022)

---

## Abstract

With the rapid development of unmanned aerial vehicles (UAVs) technology and the advent of the 5G era, the role of UAV-enabled mobile edge computing (MEC) system has attracted much attention, especially in the event of some emergencies. However, considering the limited battery life and computing capabilities of UAVs, it is challenging to provide energy-efficient services for mobile devices. To solve this challenge, we propose an energy-efficient dynamic task migration algorithm (EDTM) that minimizes the total energy consumption of the system while ensuring UAVs system load balance. Based on the improved ant colony algorithm and path elimination strategy, the proposed algorithm comprehensively considers task migration distance between UAVs, the load situation of UAVs, and environmental factors (e.g., wind speed and air density) and finally plans a reasonable task migration path. The simulation results show that the performance of the proposed EDTM is superior to the benchmark schemes.


---

## Body

## 1. Introduction

In recent years, 5G communication technology and the Internet of Things (IoTs) have developed rapidly. Mobile edge computing (MEC) attracts much attention, which can leverage the proximate computing resources to provide latency-critical and computation-intensive tasks for mobile users [1, 2]. The computation tasks generated by mobile devices (MDs) can be offloaded to the nearby edge server, such as base stations. However, these edge servers are static. It is difficult to provide powerful and stable computing services for MDs when encountering emergency calls, disaster response, and rural environments. In these cases, UAVs can act as mobile edge servers to provide more flexible and dynamic services [3]. Compared with cellular-based MEC, UAVs have the advantages of fast, high mobility, and controllable mobile management [4].Despite the advantages of UAV-enabled MEC, there are several challenges. First, the energy capacity of UAVs is constrained. To guarantee the quality of service (QoS) of MDs, it is crucial to consider the energy consumption of task migration. Second, the computation capabilities of UAVs is limited, a single UAV cannot support high computation loads, it is necessary to perform task migration with other UAVs, while ensure load balance among UAVs system. Third, an energy-efficient path planning strategy is also a challenge in UAV-enabled MEC. With an optimal task migration path, UAVs can pay less migration energy cost under load balancing. In the literature, there have been some studies focused on task migration [5–9] in MEC and optimization UAV-assisted network [10–14]. However, on the one hand, these research works mainly focus on energy consumption optimization, while neglecting considering load balance in MEC system. Therefore, the works related to dynamic task migration in MEC system cannot be efficiently applied in the UAV-enabled MEC systems. On the other hand, the existing works targeted on UAV-assisted network did not comprehensively considers task migration distance between UAVs, the load situation of UAVs, and environmental factors for the path planning of task migration with load balance within the UAVs systems, which is significant for task migration in UAV-assisted network.In this paper, we consider a joint optimization problem that simultaneously considers the above challenges have not been sufficiently investigated and considering actual environmental factors, such as wind speed and air density. To address these challenges, we propose an energy-efficient dynamic task migration algorithm (EDTM) in a UAV-enabled MEC system, which minimizes the total energy consumption of the system under load balance. The main contributions of the paper are summarized as follows:(i)
We formulate a system model in the UAV-enabled MEC system, which consists of communication model, task computation model, and energy consumption model. We fully consider the energy costs of the MDs and UAVs, including local computation energy consumption on MDs, edge computing energy consumption on UAVs, task migration energy consumption.(ii)
We improve the ant colony algorithm and propose an EDTM algorithm to migrate computation tasks. Considering the load balance of UAVs, we design a path planning elimination strategy, which comprehensively considers task migration distance between UAVs, the load situation of UAVs, and environmental factors.(iii)
We conduct extensive experiments and the simulation results demonstrate that the proposed EDTM algorithm can achieve superior performance than the benchmark schemes, which can effectively reduce the total energy consumption of the system while ensuring the load balance of the UAVs system.The remainder of the paper is organized as follows. Section2 introduces related works. In Section 3, the system model and problem are described. Section 4 presents the EDTM algorithm to solve the joint optimization problem. In Section 5, we evaluate the performance of the proposed EDTM with extensive simulation results. Finally, we conclude the paper in Section 6.


## 2. Related Works

We review the related works by two categories, i.e., dynamic task migration and UAV-assisted networks in MEC.


### 2.1. Dynamic Task Migration

There are some research efforts on dynamic task migration [5–9]. Wang et al. [5] described the task migration problem as a Markov decision process and designed an optimal service migration strategy in MEC. Kuang et al. [6] studied the partial offloading scheduling and power distribution problem for single-user MEC system. They proposed an iterative algorithm to reduce energy consumption and achieve optimal delay performance. Moreover, the authors of [7] proposed a task migration energy optimization strategy by considering resource caching. Meanwhile, Anajemba et al. [8] studied cooperative offloading scheme in energy-efficient multi-access edge computing and proposed a Lagrangian suboptimal convergent computation offloading algorithm. Zhou et al. [9] studied dynamic task offloading in MIMO MEC system with energy harvesting. The authors proposed an algorithm to minimize the time average of a weighted sum of energy consumption and execution delay, meanwhile stabilizing the battery energy queue. However, the above research works focus on energy consumption optimization, while neglecting considering load balance in the MEC system. Therefore, they cannot be efficiently applied in the UAV-enabled MEC systems.


### 2.2. UAV-Assisted Networks

UAVs have been deployed to enhance the network capacity and provide services to mobile users with or without infrastructure coverage which attracts much attention in the literature [10–14]. Particularly, the paper [10] studied energy-efficient resource management in UAV-assisted MEC. The goal is to jointly minimize the energy consumption at the IoT devices and the UAVs during task execution. Liu et al. [11] proposed a machine learning framework for trajectory design and power control for multi-UAV assisted networks. In addition, Li et al. [12] studied UAV-assisted MEC with the objective to optimize computation offloading with minimum UAV energy consumption. They adopted the Dinkelbach algorithm and the successive convex approximation technique to solve it. Wu et al. [13] considered a multi-UAV enabled wireless communication system, where multiple UAV-mounted aerial base stations are employed to serve a group of users on the ground. Existing UAV communication and trajectory schemes are inefficient as they assume limited drone mobility and static transmission power. Garg [14] considered a multi-UAV system where UAV-mounted mobile base stations serve users on the ground and proposed an iterative approach using block gradient descent. To summarize, although some research problems related to UAV-assisted networks have been investigated. However, they did not comprehensively consider task migration distance between UAVs, the load situation of UAVs, and environmental factors for the path planning of task migration with load balance within the UAVs systems, which is significant for task migration in UAV-assisted network and motivates our research in this paper.


## 2.1. Dynamic Task Migration

There are some research efforts on dynamic task migration [5–9]. Wang et al. [5] described the task migration problem as a Markov decision process and designed an optimal service migration strategy in MEC. Kuang et al. [6] studied the partial offloading scheduling and power distribution problem for single-user MEC system. They proposed an iterative algorithm to reduce energy consumption and achieve optimal delay performance. Moreover, the authors of [7] proposed a task migration energy optimization strategy by considering resource caching. Meanwhile, Anajemba et al. [8] studied cooperative offloading scheme in energy-efficient multi-access edge computing and proposed a Lagrangian suboptimal convergent computation offloading algorithm. Zhou et al. [9] studied dynamic task offloading in MIMO MEC system with energy harvesting. The authors proposed an algorithm to minimize the time average of a weighted sum of energy consumption and execution delay, meanwhile stabilizing the battery energy queue. However, the above research works focus on energy consumption optimization, while neglecting considering load balance in the MEC system. Therefore, they cannot be efficiently applied in the UAV-enabled MEC systems.


## 2.2. UAV-Assisted Networks

UAVs have been deployed to enhance the network capacity and provide services to mobile users with or without infrastructure coverage which attracts much attention in the literature [10–14]. Particularly, the paper [10] studied energy-efficient resource management in UAV-assisted MEC. The goal is to jointly minimize the energy consumption at the IoT devices and the UAVs during task execution. Liu et al. [11] proposed a machine learning framework for trajectory design and power control for multi-UAV assisted networks. In addition, Li et al. [12] studied UAV-assisted MEC with the objective to optimize computation offloading with minimum UAV energy consumption. They adopted the Dinkelbach algorithm and the successive convex approximation technique to solve it. Wu et al. [13] considered a multi-UAV enabled wireless communication system, where multiple UAV-mounted aerial base stations are employed to serve a group of users on the ground. Existing UAV communication and trajectory schemes are inefficient as they assume limited drone mobility and static transmission power. Garg [14] considered a multi-UAV system where UAV-mounted mobile base stations serve users on the ground and proposed an iterative approach using block gradient descent. To summarize, although some research problems related to UAV-assisted networks have been investigated. However, they did not comprehensively consider task migration distance between UAVs, the load situation of UAVs, and environmental factors for the path planning of task migration with load balance within the UAVs systems, which is significant for task migration in UAV-assisted network and motivates our research in this paper.


## 3. System Model

### 3.1. System Architecture

We consider a MEC system with multiuser and multiedge servers with dynamic task migration. The system consists ofM MDs and N UAVs that integrate MEC servers and communication circuits. We define M=1,2,…,M,m∈M, and U=1,2,…,t,…,U,∀u∈U to represent the set of MDs and UAVs, respectively. As for the total time T for task migration completion in the system, it is divided into F time slots on average. We use T·=0,1,…,F,t∈T to represent the set of time slots, where the length of all time slots t is τ. Moreover, the length of the time slot is small enough to ensure that the position of the UAVs during each time slot is approximately unchanged. The definitions of the main symbols involved in this paper are shown in Table 1.Table 1
Definition of main symbols.
SymbolsDefinitionMThe set of MDsUThe set of UAVsT·The set of time slotslutThe position of UAVu in time slot tl˜mtThe position of MDm in time slot tNutThe set of MDs in UAVu service range at time slot tVutThe set of MDs in UAVu communication range at time slot tdutThe set of distances between UAVu and MDs contained in set in time slot td˜utThe set of distances between UAVu and UAVs contained in set in time slot tHmThe channel gain between MDm and UAVspm,utThe uplink transmission power of MDm to offload tasks to UAV u in time slot tfmtThe CPU cycle frequency of MDm in time slot tfu,mtThe computing resources of UAVu allocate to MD m in time slot tγmtThe total number of tasks processed by MDm in time slot trmtThe total number of tasks that MDm offloaded to UAVs in time slot tQmMDtThe dynamic task backlog queue of UAVu in time slot tEcom,mtThe task processing energy consumption of MDm in time slot tEcom,utThe energy consumption for processing offloaded tasks of UAVu in time slot tEtra,mtThe transmission energy consumption of MDm offloads tasks to UAV u in time slot tEtra,utThe task migration energy of UAVu migrates tasks to UAV 1 in time slot tEfly,utThe flight energy consumption of UAVu in time slot tEUAVtThe total energy consumption of all UAVs in time slottEtotaltThe total energy consumption of the entire system in time slottIn this paper, due to the strong mobility of MDs, UAVs will have dynamic task migration in the process of providing services (task processing) to MDs. In order to facilitate the understanding of dynamic task migration, we describe task migration in the UAV-enabled MEC system architecture with multi-user and multiedge server, as shown in Figure1. Among them, UAVs are distributed around MDs to provide computing services for MDs. We select MD m for the paper detailed description. Initially, MD m was within the service coverage of UAV u. When MD m moved from the initial position 1 to position 2, MD m had already left the service range of UAV u. During the mobile process of MD m, its service quality will be seriously affected and even service termination will occur. In order to ensure the quality of the service, we need to migrate the tasks that were initially processed on UAV u. In addition, task migration also needs to consider whether location 2 is the endpoint of the MD m move. If position 2 is the endpoint of MD m during the movement, MD m will stop moving after reaching position 2; otherwise, MD m will continue to move after reaching position 2. This greatly increases the difficulty of dynamic task migration. The above constitutes the most basic dynamic task migration process of a mobile device. In Figure 1, du,mt, d4,mt, and dU,mt represent the distance between UAV u, UAV 4, UAV U and MD m in time slot t, respectively. While d˜u,1t, d˜u,4t, and d˜u,Ut represent the distance between UAV u and UAV 1, UAV 4, and UAV U in time slot t, respectively.Figure 1
The UAV-enabled MEC system architecture.To facilitate the description of the dynamic task migration path, we also define the positions of UAVs and MDs in all time slots. We define the initial position of MDs at the origin (0,0,0) of the spatial rectangular coordinate system, and the direction in which the MDs are connected from position 1 to position 2 is thex-axis of the spatial rectangular coordinate system. Therefore, a line perpendicular to the x-axis on the horizontal plane is the y-axis. The vertical plane can get the z-axis perpendicular to the x-axis and y-axis. Specifically for a certain UAV, we use xut and yut to represent the coordinates of the UAV u on the horizontal x-axis and y-axis in time slot t, that is, the horizontal position of the UAV u in time slot t. Based on the particularity of UAVs, we add a height variable zut to represent the position of UAV u in the vertical direction in time slot t. Therefore, the position of UAV u in time slot t is finally defined as the triple lut=xut,yut,zut. Similarly, the position of a particular MD, such as the position of MD m in time slot t is defined as a binary groups l˜mt=x˜mt,y˜mt, where x˜mt and y˜mt represent the coordinate positions of MD m in time slot t on the horizontal x-axis and y-axis, respectively.Because UAVs are widely distributed around MDs, and each MD can access a groups of UAVs within the broadcast range, MDs can offload computing tasks to UAVs within the accessible range [15]. We use Nut∈M to represent the set of MDs in the service range of UAV u in time slot t, and the UAVs set in its communication range are defined as Vut∈U. And because only the digital description of the distance between UAVs and MDs and UAVs can guide the task migration process. Next, we define the distance set dut between UAV u and the MDs included in the set Nut in time slot t and the distance set d˜ut between UAV u and the UAVs included in the set Vut. Among them, du,mt=xut−x˜mt2+yut−y˜mt2+zut2 and d˜u,1t=xut−x1t2+yut−y1t2+zut−z1t2 represent the distances between UAV u and MD m and UAV u and UAV 1 in time slot t, respectively. And and satisfy and respectively. Furthermore, we can get the relative position of UAV u in time slot t, that is, Lut=dut,d˜ut.


### 3.2. Communication Model

In this section, we introduce the communication model and give the uplink transmission rate when MDs offload computation tasks to UAVs. We defineHm as the channel gain between MD m and UAVs. At the same time, because the research focus of this paper is to offload the computing tasks that have been offloaded by MDs from the original UAVs to UAVs with relatively low load and close to MDs, then we assume Hm less variable. Therefore, we add a constant error value ς for Hm, and satisfying the following equation:(1)Hm=H0+ς,where H0 indicates the channel gain in the initial state.In [16], the uplink transmission power of MDs is mainly determined by the channel gain and channel bandwidth. As UAVs are used in this paper to provide edge service functions, the uplink transmission power of MDs is also greatly affected by the dynamic change of the distance between MDs and UAVs. When the distance between MDs and UAVs increases, in order to ensure that the task offload is not affected, the uplink transmission power of MDs will increase accordingly. Otherwise, the uplink transmission power of MDs will decrease accordingly. Specifically, the uplink transmission power of MD m to offload tasks to UAV u in time slot t is defined as(2)pm,ut=21/Bactually⋅τ−1σ2⋅du,mtHm=21/Bactually⋅τ−1σ2⋅du,mtH0+ς,where σ2 and Bactually represent the noise power and the actual network bandwidth in the uplink transmission process, respectively. And pm,ut satisfies the following equality, i.e.,(3)0≤pm,ut≤pUAVmax,m∈M,u∈U,t∈T,where pMDmax is the maximum transmission power of MDs.At the same time, because this paper uses UAVs to perform edge computing functions, the information transmission between UAVs and MDs and between UAVs is wireless communication [17]. In the process of wireless communication, the theoretical bandwidth and actual bandwidth will be different, because network loss and line attenuation will occur in real scenarios. Table 2 is a set of actual measured data, which shows the relationship between the channel bandwidth and the theoretical download speed as well as the actual download speed.Table 2
Relationship between network bandwidth, theoretical download speed, and actual download speed.
Network bandwidth (M)Theoretical download speedActual download speed2256 kB/s225 kB/s4512 kB/s450 kB/s6768 kB/s675 kB/s81.024 MB/s901 kB/s101.28 kB/s1.126 kB/sAccording to the data in Table2, we can get the relationship between the actual bandwidth and the theoretical bandwidth of the network, that is,(4)Bactually=88%⋅Btheory.In this paper, we do not consider downlink transmission delay and packager loss, because the data size of the result after the task is processed is usually smaller than the data size before the task processed [18], and the downlink transmission rate from UAVs to MDs will be higher than the uplink transmission rate from MDs to UAVs.


### 3.3. Task Computation Model

In this section, we introduce the computational model of the system. The main research direction of this paper is the task migration strategy in mobile edge computing systems.In this paper, we definefmt as the CPU cycle frequency of MD m in time slot t, and fu,mt is defined as the computing resource that UAV u allocates to MD m in time slot t for processing the computing tasks offloaded by MD m. And fmt and fu,mt satisfy the following equality, respectively, that is,(5)0<fmt≤fMDmax,m∈M,t∈T,0<∑m∈Mfu,mt≤fUAVmax,u∈U,t∈T,where fMDmax and fUAVmax represent the maximum cycle frequencies of MDs and UAVs, respectively.Whether it is an UAV or a MD, the tasks in the task queue are processed according to the “first come, first served” rule. In particular, the unit of the task amount is unified as bits, and the CPU cycle required to process one bit of any type of computing task isc. We assume that task arrival MDs are a random model and that task arrival is independent. The total number of tasks processed by MD m in time slot t is γmt, that is,(6)γmt=fmt⋅τc.While the total number of tasks that MDm offloads to UAVs is rmt.When MDs offload some tasks to UAVs, UAVs will process these tasks. Although the computing power of UAVs is much stronger than that of MDs, the computing power of UAVs is extremely limited compared to cloud servers. UAVu handles the number of tasks from MD m offload at time slot t is bu,mt. Therefore, we can get the dynamic task backlog queue of UAV u, i.e.,(7)QuUAVt+1=QuUAVt−∑m∈Mbu,mt++∑m∈Mrmt,where bu,mt=fu,mt⋅τ/c. And QuUAVt satisfies equality (8).(8)∑m∈Mbu,mt≤QuUAVt,u∈U,t∈T,In a real application scenario, some MDs will offload tasks to UAVs, while some MDs may not [19]. So, ∑m∈Mrmt≥0. In addition, because our optimization goal is to ensure that each UAV achieves load balancing in each time slot as much as possible, that is, the number of tasks that each UAV needs to process in each time slot is approximately equal. Therefore, we define the limiting conditions as shown in equality (9), so that the number of tasks of each UAV in each time slot cannot exceed 10\% of the average number of tasks in the queue of all UAVs. Furthermore, MDs can make full use of the computing resources of UAVs without causing a waste of resources.(9)QuUAVt≤1U∑u=1UQuUAVt⋅1+10%,u∈U,t∈T.Next, we introduce the system energy consumption model in detail.


## 3.1. System Architecture

We consider a MEC system with multiuser and multiedge servers with dynamic task migration. The system consists ofM MDs and N UAVs that integrate MEC servers and communication circuits. We define M=1,2,…,M,m∈M, and U=1,2,…,t,…,U,∀u∈U to represent the set of MDs and UAVs, respectively. As for the total time T for task migration completion in the system, it is divided into F time slots on average. We use T·=0,1,…,F,t∈T to represent the set of time slots, where the length of all time slots t is τ. Moreover, the length of the time slot is small enough to ensure that the position of the UAVs during each time slot is approximately unchanged. The definitions of the main symbols involved in this paper are shown in Table 1.Table 1
Definition of main symbols.
SymbolsDefinitionMThe set of MDsUThe set of UAVsT·The set of time slotslutThe position of UAVu in time slot tl˜mtThe position of MDm in time slot tNutThe set of MDs in UAVu service range at time slot tVutThe set of MDs in UAVu communication range at time slot tdutThe set of distances between UAVu and MDs contained in set in time slot td˜utThe set of distances between UAVu and UAVs contained in set in time slot tHmThe channel gain between MDm and UAVspm,utThe uplink transmission power of MDm to offload tasks to UAV u in time slot tfmtThe CPU cycle frequency of MDm in time slot tfu,mtThe computing resources of UAVu allocate to MD m in time slot tγmtThe total number of tasks processed by MDm in time slot trmtThe total number of tasks that MDm offloaded to UAVs in time slot tQmMDtThe dynamic task backlog queue of UAVu in time slot tEcom,mtThe task processing energy consumption of MDm in time slot tEcom,utThe energy consumption for processing offloaded tasks of UAVu in time slot tEtra,mtThe transmission energy consumption of MDm offloads tasks to UAV u in time slot tEtra,utThe task migration energy of UAVu migrates tasks to UAV 1 in time slot tEfly,utThe flight energy consumption of UAVu in time slot tEUAVtThe total energy consumption of all UAVs in time slottEtotaltThe total energy consumption of the entire system in time slottIn this paper, due to the strong mobility of MDs, UAVs will have dynamic task migration in the process of providing services (task processing) to MDs. In order to facilitate the understanding of dynamic task migration, we describe task migration in the UAV-enabled MEC system architecture with multi-user and multiedge server, as shown in Figure1. Among them, UAVs are distributed around MDs to provide computing services for MDs. We select MD m for the paper detailed description. Initially, MD m was within the service coverage of UAV u. When MD m moved from the initial position 1 to position 2, MD m had already left the service range of UAV u. During the mobile process of MD m, its service quality will be seriously affected and even service termination will occur. In order to ensure the quality of the service, we need to migrate the tasks that were initially processed on UAV u. In addition, task migration also needs to consider whether location 2 is the endpoint of the MD m move. If position 2 is the endpoint of MD m during the movement, MD m will stop moving after reaching position 2; otherwise, MD m will continue to move after reaching position 2. This greatly increases the difficulty of dynamic task migration. The above constitutes the most basic dynamic task migration process of a mobile device. In Figure 1, du,mt, d4,mt, and dU,mt represent the distance between UAV u, UAV 4, UAV U and MD m in time slot t, respectively. While d˜u,1t, d˜u,4t, and d˜u,Ut represent the distance between UAV u and UAV 1, UAV 4, and UAV U in time slot t, respectively.Figure 1
The UAV-enabled MEC system architecture.To facilitate the description of the dynamic task migration path, we also define the positions of UAVs and MDs in all time slots. We define the initial position of MDs at the origin (0,0,0) of the spatial rectangular coordinate system, and the direction in which the MDs are connected from position 1 to position 2 is thex-axis of the spatial rectangular coordinate system. Therefore, a line perpendicular to the x-axis on the horizontal plane is the y-axis. The vertical plane can get the z-axis perpendicular to the x-axis and y-axis. Specifically for a certain UAV, we use xut and yut to represent the coordinates of the UAV u on the horizontal x-axis and y-axis in time slot t, that is, the horizontal position of the UAV u in time slot t. Based on the particularity of UAVs, we add a height variable zut to represent the position of UAV u in the vertical direction in time slot t. Therefore, the position of UAV u in time slot t is finally defined as the triple lut=xut,yut,zut. Similarly, the position of a particular MD, such as the position of MD m in time slot t is defined as a binary groups l˜mt=x˜mt,y˜mt, where x˜mt and y˜mt represent the coordinate positions of MD m in time slot t on the horizontal x-axis and y-axis, respectively.Because UAVs are widely distributed around MDs, and each MD can access a groups of UAVs within the broadcast range, MDs can offload computing tasks to UAVs within the accessible range [15]. We use Nut∈M to represent the set of MDs in the service range of UAV u in time slot t, and the UAVs set in its communication range are defined as Vut∈U. And because only the digital description of the distance between UAVs and MDs and UAVs can guide the task migration process. Next, we define the distance set dut between UAV u and the MDs included in the set Nut in time slot t and the distance set d˜ut between UAV u and the UAVs included in the set Vut. Among them, du,mt=xut−x˜mt2+yut−y˜mt2+zut2 and d˜u,1t=xut−x1t2+yut−y1t2+zut−z1t2 represent the distances between UAV u and MD m and UAV u and UAV 1 in time slot t, respectively. And and satisfy and respectively. Furthermore, we can get the relative position of UAV u in time slot t, that is, Lut=dut,d˜ut.


## 3.2. Communication Model

In this section, we introduce the communication model and give the uplink transmission rate when MDs offload computation tasks to UAVs. We defineHm as the channel gain between MD m and UAVs. At the same time, because the research focus of this paper is to offload the computing tasks that have been offloaded by MDs from the original UAVs to UAVs with relatively low load and close to MDs, then we assume Hm less variable. Therefore, we add a constant error value ς for Hm, and satisfying the following equation:(1)Hm=H0+ς,where H0 indicates the channel gain in the initial state.In [16], the uplink transmission power of MDs is mainly determined by the channel gain and channel bandwidth. As UAVs are used in this paper to provide edge service functions, the uplink transmission power of MDs is also greatly affected by the dynamic change of the distance between MDs and UAVs. When the distance between MDs and UAVs increases, in order to ensure that the task offload is not affected, the uplink transmission power of MDs will increase accordingly. Otherwise, the uplink transmission power of MDs will decrease accordingly. Specifically, the uplink transmission power of MD m to offload tasks to UAV u in time slot t is defined as(2)pm,ut=21/Bactually⋅τ−1σ2⋅du,mtHm=21/Bactually⋅τ−1σ2⋅du,mtH0+ς,where σ2 and Bactually represent the noise power and the actual network bandwidth in the uplink transmission process, respectively. And pm,ut satisfies the following equality, i.e.,(3)0≤pm,ut≤pUAVmax,m∈M,u∈U,t∈T,where pMDmax is the maximum transmission power of MDs.At the same time, because this paper uses UAVs to perform edge computing functions, the information transmission between UAVs and MDs and between UAVs is wireless communication [17]. In the process of wireless communication, the theoretical bandwidth and actual bandwidth will be different, because network loss and line attenuation will occur in real scenarios. Table 2 is a set of actual measured data, which shows the relationship between the channel bandwidth and the theoretical download speed as well as the actual download speed.Table 2
Relationship between network bandwidth, theoretical download speed, and actual download speed.
Network bandwidth (M)Theoretical download speedActual download speed2256 kB/s225 kB/s4512 kB/s450 kB/s6768 kB/s675 kB/s81.024 MB/s901 kB/s101.28 kB/s1.126 kB/sAccording to the data in Table2, we can get the relationship between the actual bandwidth and the theoretical bandwidth of the network, that is,(4)Bactually=88%⋅Btheory.In this paper, we do not consider downlink transmission delay and packager loss, because the data size of the result after the task is processed is usually smaller than the data size before the task processed [18], and the downlink transmission rate from UAVs to MDs will be higher than the uplink transmission rate from MDs to UAVs.


## 3.3. Task Computation Model

In this section, we introduce the computational model of the system. The main research direction of this paper is the task migration strategy in mobile edge computing systems.In this paper, we definefmt as the CPU cycle frequency of MD m in time slot t, and fu,mt is defined as the computing resource that UAV u allocates to MD m in time slot t for processing the computing tasks offloaded by MD m. And fmt and fu,mt satisfy the following equality, respectively, that is,(5)0<fmt≤fMDmax,m∈M,t∈T,0<∑m∈Mfu,mt≤fUAVmax,u∈U,t∈T,where fMDmax and fUAVmax represent the maximum cycle frequencies of MDs and UAVs, respectively.Whether it is an UAV or a MD, the tasks in the task queue are processed according to the “first come, first served” rule. In particular, the unit of the task amount is unified as bits, and the CPU cycle required to process one bit of any type of computing task isc. We assume that task arrival MDs are a random model and that task arrival is independent. The total number of tasks processed by MD m in time slot t is γmt, that is,(6)γmt=fmt⋅τc.While the total number of tasks that MDm offloads to UAVs is rmt.When MDs offload some tasks to UAVs, UAVs will process these tasks. Although the computing power of UAVs is much stronger than that of MDs, the computing power of UAVs is extremely limited compared to cloud servers. UAVu handles the number of tasks from MD m offload at time slot t is bu,mt. Therefore, we can get the dynamic task backlog queue of UAV u, i.e.,(7)QuUAVt+1=QuUAVt−∑m∈Mbu,mt++∑m∈Mrmt,where bu,mt=fu,mt⋅τ/c. And QuUAVt satisfies equality (8).(8)∑m∈Mbu,mt≤QuUAVt,u∈U,t∈T,In a real application scenario, some MDs will offload tasks to UAVs, while some MDs may not [19]. So, ∑m∈Mrmt≥0. In addition, because our optimization goal is to ensure that each UAV achieves load balancing in each time slot as much as possible, that is, the number of tasks that each UAV needs to process in each time slot is approximately equal. Therefore, we define the limiting conditions as shown in equality (9), so that the number of tasks of each UAV in each time slot cannot exceed 10\% of the average number of tasks in the queue of all UAVs. Furthermore, MDs can make full use of the computing resources of UAVs without causing a waste of resources.(9)QuUAVt≤1U∑u=1UQuUAVt⋅1+10%,u∈U,t∈T.Next, we introduce the system energy consumption model in detail.


## 4. Energy Consumption Model

First, the task processing energy consumption includes the energy consumption of MDs and UAVs when processing tasks. According to the capacitance theory, whether it is a MD or an UAV, the processing energy consumption is mainly determined by the CPU performance of the electronic device, that is, chip architecture [20]. In the paper [21], we can know that the CPU cycle frequency varies with the CPU voltage and is linearly related. Therefore, the task processing energy consumption of MD m and the energy consumption of UAV u processing offloaded tasks are respectively expressed as (9) and (10), that is,(10)Ecom,mt=κ⋅fmt3⋅τ,(11)Ecom,ut=∑m∈Mκ⋅fu,mt3⋅τ.Among them,κ represents the effective capacitance switch of the CPU, and the value of κ is determined by the performance of the CPU.Secondly, the communication energy consumption consists of the energy consumption of the MDs offload task and the energy consumption of task migration between UAVs. As mentioned earlier, if MDm chooses to offload computing tasks to UAV u through the uplink, then the transmission energy consumption of MD m offloads tasks to UAV u in time slot t can finally get and show as follows:(12)Etra,mt=pm,ut⋅τ.In addition, the dynamic task migration from UAVu to UAV 1 is shown in Figure 2. In Figure 2, MD 3 is initially in the service range of UAV u, so MD 3 offloads tasks to UAV u. However, with the movement of MD 3, MD 3 eventually moves away from the service range of UAV u. In order to ensure the normal service of MD 3, UAV u needs to reselect a new UAV and migrate the tasks to the new UAV according to the load of each UAV and the distance from each UAV within its communication range Vut. As shown in Figure 2, the new UAV is UAV 1. At this time, we can get the task migration energy consumption of UAV u migrates the tasks to UAV 1, that is,(13)Etra,ut=pu,1t⋅τ,where pu,1t is the transmission power between UAV 1 and UAV u, and its specific computation method is similar to (2) in Section 3.2. And pu,1t cannot exceed the maximum transmission power of UAV, that is,(14)0≤pu,1t≤pUAVmax,u∈U,t∈T.Figure 2
The dynamic process of task migration from UAVu to UAV 1.Finally, in addition to the energy consumption of task computation and task migration for UAVs, the energy consumed by UAVs for a flight cannot be ignored. Most of the papers only consider the flying speed of UAVs as the independent variable when studying the flight energy consumption of UAVs. However, it shows that the flight energy consumption of UAVs depends not only on the speed of UAVs but also on the acceleration of UAVs [21–23]. Next, we define the velocity and acceleration of UAV u in time slot t, which are expressed as follows:(15)vut=lut+1−lutτ,aut=vut−vut−1τ.Therefore, we can get the flight energy consumption of UAVu in time slot t, that is,(16)Efly,ut=ku,1vut3+ku,2vut1+aut2g2.Among them,ku,1=0.5⋅ρ⋅Gu⋅τ, ku,2=2⋅Gu2⋅τ/πρARSr. Gu represents the weight of UAV u, and g represents the acceleration of gravity. ρ stands for air density (kg/m3). Aut and Sut represent the number of revolutions per second of the propeller of UAV u and the speed of the wind around the UAV u (m/s) in time slot t, respectively.Regarding the flight of UAVs, there are three special restrictions that need to be specified. First, the flying speed of every UAV at each moment should be less than the maximum flying speedvmax, that is,(17)vut≤vmax,u∈U,t∈T.Equality (18) restrict the position of UAVs. The meaning of equality (18) means that each UAV’s own trajectory history cannot be changed. The meaning of equality (18) means that during the total time T, each UAV has an initial position and a final position. The specific restrictions are as follows:(18)∑t=0T−1lut+1−lut≤η,u∈U,t∈T,lu0=lu,start,luF−1=lu,end,u∈U,where η is a small nonnegative value. lu,start and lu,end represent the initial and final positions of UAV u, respectively.In summary, the total energy consumption of all UAVs in the system in time slott is defined as follows:(19)EUAVt=∑u∈UEcom,ut+Etra,ut+ε⋅Efly,ut,where ε is a nonnegative penalty coefficient, which represents the ratio of the flying energy consumption Efly,ut to the total energy consumption EUAVt of UAVs. The larger the value of ε, the greater the proportion of Efly,ut in EUAVt. Otherwise, the smaller the proportion of Efly,ut in EUAVt. In the MEC system, we adjust the ε value to achieve a balance between UAVs flight energy consumption and UAVs computation migration energy consumption. Similarly, we can get the total energy consumption of the entire system in time slot t, that is,(20)Etotalt=ϖ1⋅∑m∈MEcom,mt+Etra,mt+ϖ2⋅EUAVt,where ϖ1 and ϖ2 represent energy consumption weighting factors of MDs and UAVs, respectively, and satisfy 0≤ϖ1≤1, 0≤ϖ2≤1, and ϖ1+ϖ2=1. When ϖ1 increases, ϖ2 will decrease accordingly. At this time, the energy consumption ratio of MDs becomes larger and the energy consumption ratio of UAVs becomes smaller. Conversely, the energy consumption ratio of MDs becomes smaller, and the energy consumption ratio of UAVs becomes larger. In this model, we can dynamically adjust ϖ1 and ϖ2 according to the actual situation to meet the priority energy demand, and finally, achieve the energy balance between MDs and UAVs.


### 4.1. Problem Formulation

Next, we mainly optimize from two aspects of energy consumption, UAVs load balancing (that is, to ensure that the task queue of UAVs in each time slot in the system has a minimum backlog), and comprehensively consider performance indicators such as task offloading, CPU cycle frequency allocated by UAVs to MDs offloaded tasks and flight energy consumption of UAVs. Finally, we worked out the problem of minimizing the energy consumption of the system under the premise of UAVs load balancing, that is,(21)P:minX1T∑t=0T−1Etotalt,s.t.3,5,8,10,11,15,18,19,20,where X represents a migration decision, which is a set of nodes on a migration path. For example, X=1,3,4 means that tasks are migrated from UAV 1 to UAV 3 first, and then they are migrated from UAV 3 to UAV 4. The research focus of this paper is to find the optimal edge servers (i.e., UAVs) migration path that is most suitable for tasks to complete the migration while ensuring that each edge server is load balanced, so that edge servers are not overloaded. Especially, the optimal migration path with the lowest energy consumption.


## 4.1. Problem Formulation

Next, we mainly optimize from two aspects of energy consumption, UAVs load balancing (that is, to ensure that the task queue of UAVs in each time slot in the system has a minimum backlog), and comprehensively consider performance indicators such as task offloading, CPU cycle frequency allocated by UAVs to MDs offloaded tasks and flight energy consumption of UAVs. Finally, we worked out the problem of minimizing the energy consumption of the system under the premise of UAVs load balancing, that is,(21)P:minX1T∑t=0T−1Etotalt,s.t.3,5,8,10,11,15,18,19,20,where X represents a migration decision, which is a set of nodes on a migration path. For example, X=1,3,4 means that tasks are migrated from UAV 1 to UAV 3 first, and then they are migrated from UAV 3 to UAV 4. The research focus of this paper is to find the optimal edge servers (i.e., UAVs) migration path that is most suitable for tasks to complete the migration while ensuring that each edge server is load balanced, so that edge servers are not overloaded. Especially, the optimal migration path with the lowest energy consumption.


## 5. Joint Optimization Strategy of Task Migration and Load Balancing

### 5.1. Description of the Dynamic Migration Algorithm

In this section, we propose a new and improved iterative algorithm, called Energy-efficient Dynamic Task Migration (EDTM). The proposed EDTM algorithm is modified on the basis of the ant colony algorithm. The traditional ant colony algorithm is a heuristic optimization algorithm. Although the initial optimization results of the problem can be obtained by the traditional ant colony algorithm, it has the disadvantages of being easily trapped into a local optimum and slower convergence speed [24]. In this paper, we combine the specific research content of this paper to improve the traditional ant colony algorithm. According to the inspiration of [25], the proposed EDTM algorithm has adaptive consistency and is more suitable for MEC. The main improvements are as below.First, we modified the pheromone update strategy in the ant colony algorithm. The idea of the ant colony algorithm originally originated from the process of ants finding the best path. An ant leaves an odor when walking through a certain path. This odor is called a pheromone. The ants behind it would be based on the pheromone concentration to choose a path, the greater the pheromone concentration, the higher the probability that an ant will choose this path, and vice versa. In this model, the proposed EDTM algorithm will also select the next UAV node according to the number of different UAV nodes and the location of each UAV node in each time slot. It can prevent the proposed EDTM algorithm from falling into a local optimum too quickly, and at the same time increase the global search capability of the algorithm.Secondly, based on the goal of this paper is to jointly optimize UAV load balancing and reduce the total energy consumption of the system, so we add the task queue of UAVs as a variable to the formula transition probability. The meaning of transition probability is the probability that the ant chooses the next UAV node. This helps us find a reasonable migration path.Thirdly, in the initial iterative process of the ant colony algorithm, the ant has to try all possible paths in order to find the optimal path, which will cause the algorithm to be redundant and increase the complexity. In the proposed EDTM algorithm, we propose a method of path elimination. By setting the “number of pathfinding nodes” to control the number of iterations of the algorithm. On the basis of ensuring the accuracy of the algorithm results, the complexity of the algorithm is further reduced, and the algorithm execution efficiency is improved.The proposed EDTM algorithm comprehensively considers the migration distance, the UAVs load situation, and the migration cost to finally plan a reasonable task migration path. The algorithm has a very strong ability to find solutions to combined optimization problems. In addition, it has the advantages of distributed computing and the advantages of easy integration with other algorithms. In particular, it can show a high degree of flexibility and robustness in dynamic environments [26, 27]. Because the scenario in this paper uses UAVs as edge servers to provide services to users, we attach great importance to the advantages of mutual cooperation between UAVs.Finally, these UAVs process the sub-tasks and return corresponding results to MDs.


### 5.2. Solution to ProblemP

In this section, we specifically explain how the proposed EDTM algorithm solves problemP. In the previous model, we have defined the UAVs set U=1,2,…,t,…,U,∀u∈U, and d˜ut represents the distance between UAVs nodes in time slot t. Specifically, our description of the proposed EDTM algorithm is divided into the following seven steps.Step 1.
Initialize. In this paper, UAVs nodes can communicate with each other, so we initialize the pheromone on each edge to a small constant value, and then randomly assignA ants to U UAVs nodes. At the same time, we set the starting UAV node to the tabu list. One thing that needs to be explained here is that the reason why we did not initialize the pheromone directly to zero is that the ants choose the next hop UAV node will receive the influence of the pheromone concentration.Step 2.
Each ant will select the next UAV node according to formulas (22) and (23), and update the tabu list.(22)j=argj∉Yamaxϕijt⋅φijtβ⋅χijtλ,ifq≤q0,pija,otherwise,where i∈U,j∈U, and Ya is a set, that is, tabu table. Ya is used to record the UAV nodes passed by ant a. The tabu table Ya will be updated as the algorithm iterates. ϕijt indicates the value of the pheromone transferred from UAV node i to UAV node j in time slot t. The greater the value of the pheromone, the greater the probability that the ant chooses the UAV node as the migration node, and the two show a proportional relationship. ϕijt is the heuristic information of the ant transferred from UAV node i to UAV node j in time slot t, and the heuristic information will affect the probability that the ant chooses the next node. In this paper, we take the distance between UAV node i and UAV node j as the independent variable of the heuristic information, so we define ϕijt=1/d˜i,jt. The longer the distance between UAV node i and UAV node j, the smaller the value of heuristic information; otherwise, the larger the value of heuristic information. Next, we named the χijt in formula (22) as a statin, which represents the value of the statin of the ants from UAV node i to UAV node j in time slot t. The effect of statin is opposite to that of pheromone. The greater the value of statin, the lower the probability that the ant will choose the UAV node as the migration node, and the two show an inverse relationship. The optimization goals of this paper are two aspects, namely, to ensure the load balance of UAV groups and reduce the total energy consumption of the system. Therefore, we specifically represent the statin χijt in formula (22) as χijt=k3⋅QjUAVt. It can be seen that the larger the load of the UAV node (that is, the longer the task backlog queue length of the UAV node in time slot t), the larger the statin of this path. Similarly, the smaller the load of the UAV nodes in this path is, the smaller the statin of this path is. Therefore, χijt and QjUAVt have a function proportional relationship, where k3 is used as the coefficient of the function expression. It should be noted that q0∈0,1 is a parameter initially set by the system, and q is a random number and satisfies q∈0,1; finally, pija represents the probability that the ant a moves from UAV node i to UAV node j. The specific expression is as follows,(23)pija=ϕijtα⋅φijtβ⋅χijtλ∑a∉Yaϕiatα⋅φiatβ⋅χiatλ,j∉Ya,0,j∈Ya.
In particular, formula (22) and formula (23) contain the weighting factors of pheromone, heuristic information, and statin, which represent the importance of pheromone on paths i and j, represent the importance of heuristic information and represent the importance of statin on paths i and j.Step 3.
Local update of pheromone. According to the idea of bionics in biology, if an ant passes a certain path, then the pheromone concentration on this path will increase again. The specific formula for the pheromone update is as follows,(24)ϕijt+1=1−μtϕijt+μt⋅Δϕija,i∈U,j∈U,where μt is called the pheromone volatility factor, which indicates the volatility coefficient of the pheromone in time slot t. The setting of μt in the proposed EDTM algorithm is very important, it directly affects the execution efficiency of the algorithm. μmin is the minimum value of the pheromone volatilization rate set by the system in advance, and its role is to prevent the convergence speed of the proposed EDTM algorithm from being too low due to μt too small. At the beginning of the algorithm, μt should take a larger value. The advantage of this is that it can speed up the convergence speed of the algorithm. With the increase of the number of iterations, in order to prevent the convergence from falling too quickly into a local optimum, the value of μt should be gradually reduced to improve the global search capability of the proposed EDTM algorithm. Therefore, this model uses the method shown in (25) to adaptively adjust μt.(25)μt=0.95μt−1,0.95μt−1>μmin,μmin,0.95μt−1≤μmin.
In addition,Δϕija in (24) represents the amount of pheromone left on the path when ant a passes through UAV node i and UAV node j. The specific expression of Δϕija is shown:(26)Δϕija=QDij,when ant a walks across the path of UAV nodeiandj,0,otherwise,where Q represents the total amount of information released by ant a for one week, and it is a constant; Dij is the length of the path that ant a has traveled from the starting UAV node to the current UAV node.Step 4.
Compute the best path. AfterA ants have walked through all UAV nodes, we need to choose a path suitable for migration among these paths. In the task migration, in addition to the load of the nodes, we also need to consider the energy consumption caused by the migration [28, 29]. In the model part of the paper, equation (13) defines the migration cost, so we use migration cost as a measure of optimal path quality. The specific formula is as follows:(27)Eminmig=minEa,where Ea is the migration cost caused by the path taken by ant a.Step 5.
Path elimination rules. In this paper, we set the “number of pathfinding nodes” B to control the number of iterations of the algorithm, and we defineB=⌈20%⋅U⌉. It can be seen that the number of pathfinding nodes is related to the total number of nodes in the entire system. When the proposed EDTM algorithm starts to run, A ants do not have to iterate over all UAV nodes, but only needs to filter out the B nodes closest to the initial UAV node in the system for access. After each iteration is completed, the algorithm automatically executes Step 4 to find the optimal migration path from path set, and the remaining paths no longer participate in the operation of subsequent algorithms.Step 6.
Global update of pheromone. After the ants have walked through all UAV nodes, we need to distinguish the best path from the normal path. Therefore, we process the pheromone on the best path according to formula (28) to convert the old pheromone ϕijoldt into the new pheromone ϕijnewt.(28)ϕijnewt=1−σϕijoldt+σ⋅Δϕij,where σ is the global pheromone volatility coefficient, Δϕij represents the sum of the pheromone amount of all ants passing through the path between i and j, and Δϕij is defined as follows:(29)Δϕij=1Dgood,if the global optimal solution across the path of UAV nodeiandj,0,otherwise,where Dgood represents the length of the optimal path.Step 7.
In this paper, as the number of iterations increases, the change of the migration node-setX will stabilize. Therefore, we set a search number in the proposed EDTM algorithm. If the specified search number is not reached, the tabu list is cleared and the above process is repeated.


### 5.3. Path Elimination Rules

The path elimination rule is a process of determining the number of valid UAV nodes. If the subset of UAV nodes that can be the most likely to become valid nodes can be filtered first, this will greatly reduce the running time and complexity of the proposed EDTM algorithm. Before the proposed EDTM algorithm starts to execute, we can determine the valid nodes from the source nodes. This is a pre-processing process.In Step5 of Section 5.2 of this paper, we mentioned “Number of Pathfinding Nodes” B. These UAV nodes are the possible UAV nodes closest to the initial UAV node. At the same time, these UAV nodes are also the most likely to become valid UAV nodes. Therefore, we have reason to believe that the probability that the optimal path passes through these nodes will be relatively large. In addition, B meets B≤U−1, and U is the total number of UAV nodes in the system. The value of B can only be a constant between 1 and U-1. The value of B will directly affect the convergence speed and accuracy of the proposed EDTM algorithm.To facilitate understanding, we use Figures3–5 to illustrate the process of obtaining the optimal migration path after MD m offloads tasks to UAV 1. In detail, Figure 3 shows that it is currently in the initial state and no task migration has occurred. There are 6 UAV nodes distributed from UAV node 1 to UAV node 6, respectively. Furthermore, node 1 is the initial node and node 6 is the destination node. All we need to do is plan an optimal path from node 1 to node 6. Before we start using the path elimination method, we first introduce the situation of the traditional ant colony algorithm in the early iteration, as shown in Figure 4. When the algorithm started running, UAV node 1 had to calculate the transition probability with the remaining 5 UAV nodes and then make a judgment, which means that the time complexity of the first iteration is On. As the number of iterations increases, the running time of the algorithm will increase at an exponential rate, that is, Onn2−2n+1.Figure 3
Initial state.Figure 4
The situation of the traditional ant colony algorithm in the early iteration.Figure 5
The situation of the traditional ant colony algorithm in the early iteration.
(a)(b)(c)(d)(e)To sum up, the traditional ant colony algorithm does have certain defects in the initial iteration. We start with the path elimination method, and the (a-e) graph contained in Figure5 corresponds to the five processes of optimal path acquisition.There are 6 nodes in Figure5(a), so it can be computed by the formula B=⌈20%⋅6⌉=⌈1.2⌉=2. As shown in Figure 5(a), the two nodes closest to node 1 are node 2 and node 3. The next-hop UAV node can be obtained by computing the transition probability. We assume that the computation result is node 3. Figure 5(b) shows two computation possibilities for the next node. For node 3, we only need to compare its transition probability with node 4 and node 6. We assume that the computation result is that node 4 as the next hop UAV node. Since the ant has searched for the destination node in the process of finding a valid node, we first update the migration node-set to Xut=1,3,6. Next, it is node 4 to start searching for new valid nodes. At this time, the two nodes closest to node 4 are node 1 and node 2. But since node 1 is the initial node, node 1 is excluded from the valid nodes. At this time, we need to compute the transition probability of node 2 and 5. We assume that the computation result is that node 2 as the next-hop node, as shown in Figure 5(c). As shown in Figure 5(d), the two nodes closest to node 2 and not yet visited are node 5 and node 6. Then we need to continuously compare the total migration cost with the migration cost of the previous migrated nodes set Xut=1,3,6 and select the optimal migration path. Finally, the migration node-set Xt is updated. Now, only the last UAV node is left, it is shown in Figure 5(e).


### 5.4. The Proposed EDTM Algorithm

In this section, we mainly introduce the specific process of the proposed EDTM algorithm to solve the joint optimization problem of load balancing and total energy consumption in the system. The number of target UAV nodes that we screen isr=⌈15%⋅U⌉. We select r UAV nodes with the shortest task backlog queue length (that is, the lowest load) as the target UAV nodes. After clarifying the target UAV node, we begin to use the proposed EDTM algorithm to compute the optimal migration path. Because the target UAV node is not unique, the final migration path must also be unique. We can divide the task and then migrate to these UAV nodes. These UAV nodes will perform the distributed processing on the task, and finally, return the results to MDs. The detailed process of the proposed EDTM algorithm is shown in Algorithm 1. In Algorithm 1, e represents the number of iterations, QUAVt represents the task backlog queue set of all UAVs nodes in the system at time slot t.Algorithm 1: The proposed EDTM algorithm.
Input:QUAVt,q0,α,β,λ,Q,num,A,rOutput:QUAVt+1,Xt(1)
Initialize the target UAV node Set and initial UAV nodes(2)
fore = 1: num do(3)
the ant looks for the next hop UAV node according to formula (23)(4)
getϕij,Δϕ,μ according to formula (24)–(26)(5)
Update the tabu table(6)
Update local pheromoneϕij(7)
Update global pheromoneϕijnew by formula (29)(8)
foru∈U(9)
B=⌈20%⋅U⌉(10)
Update migration node setX(11)
U=U−B(12)
Compute total migration costEtotalt(13)
Remove invalid UAV nodes and eliminate nonoptimal paths(14)
end for(15)
end forBesides, the special nature of the proposed EDTM algorithm, the task migration efficiency of multiple users will be higher. Because the ants look for UAV nodes and paths are based on the pheromone left by the previous ants, when there are multiple MDs that need task migration, it is no longer necessary to run the proposed EDTM algorithm to replan the migration path.


### 5.5. Experimental Results

In this experiment, we simulated a 600m × 600 m rectangular area in which a UAV group flies and provides services to MDs. The horizontal movement range of each UAV is 240 square meters. There is no limit to the flight trajectory of each UAV, but one thing we need to emphasize is that the initial position and end position of each UAV is always the same. We assume that the number of UAVs and MDs is 15 and 100, respectively. Besides, the service radius of each UAV is 150 m. The main parameters are defined in Table 3.Table 3
The definition of the main experimental parameters.
ParametersValueThe theoretical communication bandwidth10 MThe channel gainH0=170,ς=15.5The noise power2×10−9WThe maximum transmission power of the MDs1.7 WThe maximum transmitting power of the UAVs100 WThe maximum CPU cycle frequency of the MDs1.8 GHzThe maximum CPU cycle frequency of the UAVs20 GHzThe maximum memory of the UAVs1 TThe CPU effective capacitance switch of the MDs1.2×10−17The CPU effective capacitor switch of the UAVs3×10−16The density of processing tasks103 cycles/bitThe mass of each UAV19.7 kgThe maximum speed of the UAVs13 m/sThe initial height of the UAVs50 mThe gravitational acceleration9.8m/s2The air density1.293kg/m3The range of the UAV propeller rotations per second50,160The wind speed range3.5m/s,10m/s


### 5.6. Setting of Experimental Parameters

In this experiment, we simulated a 600 m × 600 m rectangular area in which a UAV group flies and provides services to MDs. The horizontal movement range of each UAV is 240 square meters. The flight trajectory of each UAV can be the same or different, but one thing we need to emphasize is that the initial position and end position of each UAV is always the same. We assume that the number of UAVs and MDs is 15 and 100, respectively. Besides, the service radius of each UAV is 150 m. In summary, each UAV is flying within a fixed range as an edge server and each MD offloads tasks that it cannot process or has a large amount of computation to the UAVs. The main parameters are defined in Table3.For some parameters in the proposed EDTM algorithm, we defineα=3, β=2, λ=1.5, A = 100, μ0=0.5, μmin=0.1, Q=20000, q0=0.7, σ=0.3. And we set the number of iterations of the entire algorithm during the run to 4500. Besides, we need to explain that if the values of α/β and α/λ are too large, the ant has a strong dependence on the pheromone when choosing the path, which will easily fall into a local optimum; otherwise, the ant will not rely on the pheromone left by other ants to make judgments.


### 5.7. The Effect ofB and r on the Proposed EDTM Algorithm

In this paper, to accelerate the early convergence speed of the proposed EDTM algorithm, we introduce the variableB. The value of B will directly affect the convergence speed and the accuracy of the results. The B value selected in Figure 6 and Figure 7 are 10%⋅u, 15%⋅u, 20%⋅u, 25%⋅u. Since we have a small number of UAVs, our percentage difference during the experiment is 5%. In Figure 6, the time points at which 25%⋅u, 20%⋅u, 15%⋅u, and 10%⋅u converge are 3560 ns, 4516 ns, 5231 ns, and 6010 ns, respectively. Especially, 25%⋅u has the fastest convergence speed and requires the fewest actual iterations. 10%⋅u has the slowest convergence speed, and it has the most iterations. In Figure 7, the ordinate represents the length of the optimal path. Also, we can know that 10%⋅u has the slowest convergence speed but it has the shortest optimal path length. And 25%⋅u has the fastest convergence speed, but its optimal distance is proportional to the other three best paths. In this paper, we need to consider both the convergence speed of the proposed EDTM algorithm and the accuracy of the results, so we choose B=⌈20%⋅U⌉. Next, we continue to analyze the effect of r value on the proposed EDTM algorithm. To guarantee the users Qos, we split the tasks and then migrate them to multiple UAVs. These UAVs jointly perform the task and then return the final computation result to the MDs. One of our research priorities is how many UAVs we migrate to during this process. As shown in Figures 8 and 9, we consider the impact of r value on the proposed EDTM algorithm from two aspects: migration cost and load balancing. In Figure 8, the migration costs corresponding to 5%⋅u, 10%⋅u, 15%⋅u and 21%⋅u increase with time. Among them, the migration cost of 5%⋅u is the lowest, and the migration cost of 21%⋅u is the highest. This is because the larger the number of target UAVs, the higher the final migration cost. Also, we can find from Figure 8, the migration cost of the system rises rapidly between 2263 ns and 3700 ns, which is because the requirements of the migration task conform to Poisson distribution.Figure 6
The number of iterations versus time andB.Figure 7
The optimum distance length versus time andB.Figure 8
The total migration cost versus time andr.Figure 9
The load status versus time andr.In Figure9, the ordinate indicates the extreme difference of the UAV task queue length as a percentage of its maximum task queue length at the current moment. We use the computation method of extreme difference to judge the load balancing of UAVs in the MEC system. As shown in Figure 9, 0.9 represents 90%, 0.8 represents 80%, and the following values are deduced by analogy. In the previous paper, we explained that our optimization goal is to ensure that the task queue length of each UAV does not exceed 10% of the average number of tasks in the queues, so we set a baseline in the experiment. Also, we can learn that 5%⋅u, 10%⋅u, 15%⋅u, 21%⋅u will all converge to 10%, which proves that the proposed EDTM algorithm can make the load of the UAV group reach equilibrium, but their convergence speed will be different. Among them, 21%⋅u has the fastest convergence speed, and 5%⋅u has the slowest convergence speed.In summary, we chooser=⌈15%⋅U⌉, which ensures the convergence speed of the proposed EDTM algorithm, and the system migration cost is low.


### 5.8. The Analysis of Weight Factor

In formula (20), we use two weighting factors, i.e., ϖ1 and ϖ2. Due to 0≤ϖ1≤1, 0≤ϖ2≤1 and ϖ1+ϖ2=1, we just need to choose the value of ϖ2. As shown in Figure 10, we selected ϖ2=0, ϖ2=0.1, ϖ2=0.2 and ϖ2=0.5. As ϖ2 decreases, ϖ1 will increase accordingly. At this time, the MEC system will tend to minimize the energy consumption of MDs. And the average energy consumption (AEC) of the UAVs will also increase with the acceleration. When the acceleration changes from 40 m/s2 to 47 m/s2, the AEC of the UAVSs has a growth jump, which mainly comes from two aspects. One is because we set the wind speed in the entire area as a random number in 3.5m/s,10m/s, a sudden increase in wind speed will increase the flight energy consumption of the UAVs, which in turn will increase the AEC of the UAVs.Figure 10
The AEC of UAVs versus acceleration and v2.In summary, we can find that the smaller theϖ2, the larger the AEC of the UAVs. When ϖ2=0, the AEC of the UAVs is the largest because the system goal is only to focus on minimizing the energy consumption of MDs.


### 5.9. The Analysis of the Proposed EDTM Algorithm Performance

In this section, we analyze the performance of the proposed EDTM algorithm. As shown in Figure11, the proposed E DTM algorithm converges after approximately 2650 iterations, while the ACO algorithm enters a convergence state after approximately 3460 iterations. Obviously, under the same conditions, the proposed EDTM algorithm converges faster than the ACO algorithm.Figure 11
The convergence comparison between the proposed EDTM algorithm and the ACO algorithm.As shown in Figure12, the abscissa represents time, and the ordinate represents the extreme difference of the UAV task queue length as a percentage of its maximum task queue length at the current moment in the UAV group. In this experiment, we assume that the process of task arrival conforms to the Poisson distribution, so we can know from Figure 12 that the task queue extreme value of the UAV group between 1500 ns and 2700 ns becomes large and rises very quickly. Between 2700 ns and 5000 ns, the proposed EDTM algorithm makes the extreme difference smaller and stays around 0.1 in the end.Figure 12
The comparison in optimizing UAVs load between the proposed EDTM algorithm and the algorithm ACO.According to the above experiment, the proposed EDTM algorithm is superior to the ACO algorithm in terms of convergence speed and optimization of load balancing efficiency of the UAV group. At the same time, we have also proven that the proposed EDTM algorithm can help the UAV group achieve load balancing.Besides, part of the current research work solves the task migration problem in MEC by setting up Markov Decision Process (MDP). For example, researchers proposed an MDP algorithm based on static distance (MDP-SD). Next, we compare the performance of the proposed EDTM algorithm and the MDP-SD algorithm in terms of migration cost and average load percentage of the UAV groups. As shown in Figure13, the reason why the curve changes as shown is because we assume that the computation task request conforms to the Poisson distribution. When t = 0, there is no computation task in the system, so the migration cost of UAVs is 0. When 0<t<1650 ns, the computation task request amount over time slowly rising, and the migration cost of the MDP-SD algorithm is slightly higher than that of the proposed EDTM algorithm. This is because the MDP-SD algorithm consumes more computing resources than the proposed EDTM algorithm when it uses the value iterative method to solve the migration strategy in the early stage. When 1650<t<3800 ns, the amount of computation task requests rises rapidly, and the migration cost of the two algorithms also increases rapidly. When t>3800 ns, the amount of computation task request decrease and the rate of increase in migration costs begin to decrease.Figure 13
The comparison of total migration cost between the proposed EDTM algorithm and the algorithm MDP-SD algorithm.After comparing the migration costs of the proposed EDTM algorithm and the MDP-SD algorithm, next, we compare the performance of the two algorithms from the average load percentage of the UAV groups. As shown in Figure14, 0.9 means that the task queue of the UAV groups at this time accounts for 90% of the total length of the task queue. Besides, the percentage of the task queue length under the MDP-SD algorithm is higher than the proposed EDTM algorithm. This is because we considered the small storage space and computing power of the UAVs when designing the proposed EDTM algorithm. So that the proposed EDTM algorithm does not occupy too much UAV resources. Also, because the amount of computation task request conforms to the Poisson distribution, when 0<t<2800 ns, the average task queue percentage of the UAV groups will increase. And when t=2800 ns, whether it is the proposed EDTM algorithm or the MDP-SD algorithm, the average task queue percentage of the UAV groups will reach the highest point. Until t>2800 ns, the average task queue percentage of the UAV groups slowly decrease. Obviously, from the perspective of the entire process, the average task queue percentage of the UAV groups under the proposed EDTM algorithm is always lower than the MDP-SD algorithm. Therefore, the proposed EDTM algorithm is more suitable for UAV-enabled MEC systems.Figure 14
The comparison of average task queue percentage of the UAV groups between the proposed EDTM algorithm and the MDP-SD algorithm.To sum up, we compare the performance of the algorithm from the following three aspects, including convergence time, energy consumption and maximum system load status. The experimental results are shown in Table4.Table 4
The performance comparison.
Convergence time (ns)Total energy consumption (J)Maximum system load status (%)ACO355010112089MDP36119131281EDTM20008999135


## 5.1. Description of the Dynamic Migration Algorithm

In this section, we propose a new and improved iterative algorithm, called Energy-efficient Dynamic Task Migration (EDTM). The proposed EDTM algorithm is modified on the basis of the ant colony algorithm. The traditional ant colony algorithm is a heuristic optimization algorithm. Although the initial optimization results of the problem can be obtained by the traditional ant colony algorithm, it has the disadvantages of being easily trapped into a local optimum and slower convergence speed [24]. In this paper, we combine the specific research content of this paper to improve the traditional ant colony algorithm. According to the inspiration of [25], the proposed EDTM algorithm has adaptive consistency and is more suitable for MEC. The main improvements are as below.First, we modified the pheromone update strategy in the ant colony algorithm. The idea of the ant colony algorithm originally originated from the process of ants finding the best path. An ant leaves an odor when walking through a certain path. This odor is called a pheromone. The ants behind it would be based on the pheromone concentration to choose a path, the greater the pheromone concentration, the higher the probability that an ant will choose this path, and vice versa. In this model, the proposed EDTM algorithm will also select the next UAV node according to the number of different UAV nodes and the location of each UAV node in each time slot. It can prevent the proposed EDTM algorithm from falling into a local optimum too quickly, and at the same time increase the global search capability of the algorithm.Secondly, based on the goal of this paper is to jointly optimize UAV load balancing and reduce the total energy consumption of the system, so we add the task queue of UAVs as a variable to the formula transition probability. The meaning of transition probability is the probability that the ant chooses the next UAV node. This helps us find a reasonable migration path.Thirdly, in the initial iterative process of the ant colony algorithm, the ant has to try all possible paths in order to find the optimal path, which will cause the algorithm to be redundant and increase the complexity. In the proposed EDTM algorithm, we propose a method of path elimination. By setting the “number of pathfinding nodes” to control the number of iterations of the algorithm. On the basis of ensuring the accuracy of the algorithm results, the complexity of the algorithm is further reduced, and the algorithm execution efficiency is improved.The proposed EDTM algorithm comprehensively considers the migration distance, the UAVs load situation, and the migration cost to finally plan a reasonable task migration path. The algorithm has a very strong ability to find solutions to combined optimization problems. In addition, it has the advantages of distributed computing and the advantages of easy integration with other algorithms. In particular, it can show a high degree of flexibility and robustness in dynamic environments [26, 27]. Because the scenario in this paper uses UAVs as edge servers to provide services to users, we attach great importance to the advantages of mutual cooperation between UAVs.Finally, these UAVs process the sub-tasks and return corresponding results to MDs.


## 5.2. Solution to ProblemP

In this section, we specifically explain how the proposed EDTM algorithm solves problemP. In the previous model, we have defined the UAVs set U=1,2,…,t,…,U,∀u∈U, and d˜ut represents the distance between UAVs nodes in time slot t. Specifically, our description of the proposed EDTM algorithm is divided into the following seven steps.Step 1.
Initialize. In this paper, UAVs nodes can communicate with each other, so we initialize the pheromone on each edge to a small constant value, and then randomly assignA ants to U UAVs nodes. At the same time, we set the starting UAV node to the tabu list. One thing that needs to be explained here is that the reason why we did not initialize the pheromone directly to zero is that the ants choose the next hop UAV node will receive the influence of the pheromone concentration.Step 2.
Each ant will select the next UAV node according to formulas (22) and (23), and update the tabu list.(22)j=argj∉Yamaxϕijt⋅φijtβ⋅χijtλ,ifq≤q0,pija,otherwise,where i∈U,j∈U, and Ya is a set, that is, tabu table. Ya is used to record the UAV nodes passed by ant a. The tabu table Ya will be updated as the algorithm iterates. ϕijt indicates the value of the pheromone transferred from UAV node i to UAV node j in time slot t. The greater the value of the pheromone, the greater the probability that the ant chooses the UAV node as the migration node, and the two show a proportional relationship. ϕijt is the heuristic information of the ant transferred from UAV node i to UAV node j in time slot t, and the heuristic information will affect the probability that the ant chooses the next node. In this paper, we take the distance between UAV node i and UAV node j as the independent variable of the heuristic information, so we define ϕijt=1/d˜i,jt. The longer the distance between UAV node i and UAV node j, the smaller the value of heuristic information; otherwise, the larger the value of heuristic information. Next, we named the χijt in formula (22) as a statin, which represents the value of the statin of the ants from UAV node i to UAV node j in time slot t. The effect of statin is opposite to that of pheromone. The greater the value of statin, the lower the probability that the ant will choose the UAV node as the migration node, and the two show an inverse relationship. The optimization goals of this paper are two aspects, namely, to ensure the load balance of UAV groups and reduce the total energy consumption of the system. Therefore, we specifically represent the statin χijt in formula (22) as χijt=k3⋅QjUAVt. It can be seen that the larger the load of the UAV node (that is, the longer the task backlog queue length of the UAV node in time slot t), the larger the statin of this path. Similarly, the smaller the load of the UAV nodes in this path is, the smaller the statin of this path is. Therefore, χijt and QjUAVt have a function proportional relationship, where k3 is used as the coefficient of the function expression. It should be noted that q0∈0,1 is a parameter initially set by the system, and q is a random number and satisfies q∈0,1; finally, pija represents the probability that the ant a moves from UAV node i to UAV node j. The specific expression is as follows,(23)pija=ϕijtα⋅φijtβ⋅χijtλ∑a∉Yaϕiatα⋅φiatβ⋅χiatλ,j∉Ya,0,j∈Ya.
In particular, formula (22) and formula (23) contain the weighting factors of pheromone, heuristic information, and statin, which represent the importance of pheromone on paths i and j, represent the importance of heuristic information and represent the importance of statin on paths i and j.Step 3.
Local update of pheromone. According to the idea of bionics in biology, if an ant passes a certain path, then the pheromone concentration on this path will increase again. The specific formula for the pheromone update is as follows,(24)ϕijt+1=1−μtϕijt+μt⋅Δϕija,i∈U,j∈U,where μt is called the pheromone volatility factor, which indicates the volatility coefficient of the pheromone in time slot t. The setting of μt in the proposed EDTM algorithm is very important, it directly affects the execution efficiency of the algorithm. μmin is the minimum value of the pheromone volatilization rate set by the system in advance, and its role is to prevent the convergence speed of the proposed EDTM algorithm from being too low due to μt too small. At the beginning of the algorithm, μt should take a larger value. The advantage of this is that it can speed up the convergence speed of the algorithm. With the increase of the number of iterations, in order to prevent the convergence from falling too quickly into a local optimum, the value of μt should be gradually reduced to improve the global search capability of the proposed EDTM algorithm. Therefore, this model uses the method shown in (25) to adaptively adjust μt.(25)μt=0.95μt−1,0.95μt−1>μmin,μmin,0.95μt−1≤μmin.
In addition,Δϕija in (24) represents the amount of pheromone left on the path when ant a passes through UAV node i and UAV node j. The specific expression of Δϕija is shown:(26)Δϕija=QDij,when ant a walks across the path of UAV nodeiandj,0,otherwise,where Q represents the total amount of information released by ant a for one week, and it is a constant; Dij is the length of the path that ant a has traveled from the starting UAV node to the current UAV node.Step 4.
Compute the best path. AfterA ants have walked through all UAV nodes, we need to choose a path suitable for migration among these paths. In the task migration, in addition to the load of the nodes, we also need to consider the energy consumption caused by the migration [28, 29]. In the model part of the paper, equation (13) defines the migration cost, so we use migration cost as a measure of optimal path quality. The specific formula is as follows:(27)Eminmig=minEa,where Ea is the migration cost caused by the path taken by ant a.Step 5.
Path elimination rules. In this paper, we set the “number of pathfinding nodes” B to control the number of iterations of the algorithm, and we defineB=⌈20%⋅U⌉. It can be seen that the number of pathfinding nodes is related to the total number of nodes in the entire system. When the proposed EDTM algorithm starts to run, A ants do not have to iterate over all UAV nodes, but only needs to filter out the B nodes closest to the initial UAV node in the system for access. After each iteration is completed, the algorithm automatically executes Step 4 to find the optimal migration path from path set, and the remaining paths no longer participate in the operation of subsequent algorithms.Step 6.
Global update of pheromone. After the ants have walked through all UAV nodes, we need to distinguish the best path from the normal path. Therefore, we process the pheromone on the best path according to formula (28) to convert the old pheromone ϕijoldt into the new pheromone ϕijnewt.(28)ϕijnewt=1−σϕijoldt+σ⋅Δϕij,where σ is the global pheromone volatility coefficient, Δϕij represents the sum of the pheromone amount of all ants passing through the path between i and j, and Δϕij is defined as follows:(29)Δϕij=1Dgood,if the global optimal solution across the path of UAV nodeiandj,0,otherwise,where Dgood represents the length of the optimal path.Step 7.
In this paper, as the number of iterations increases, the change of the migration node-setX will stabilize. Therefore, we set a search number in the proposed EDTM algorithm. If the specified search number is not reached, the tabu list is cleared and the above process is repeated.


## 5.3. Path Elimination Rules

The path elimination rule is a process of determining the number of valid UAV nodes. If the subset of UAV nodes that can be the most likely to become valid nodes can be filtered first, this will greatly reduce the running time and complexity of the proposed EDTM algorithm. Before the proposed EDTM algorithm starts to execute, we can determine the valid nodes from the source nodes. This is a pre-processing process.In Step5 of Section 5.2 of this paper, we mentioned “Number of Pathfinding Nodes” B. These UAV nodes are the possible UAV nodes closest to the initial UAV node. At the same time, these UAV nodes are also the most likely to become valid UAV nodes. Therefore, we have reason to believe that the probability that the optimal path passes through these nodes will be relatively large. In addition, B meets B≤U−1, and U is the total number of UAV nodes in the system. The value of B can only be a constant between 1 and U-1. The value of B will directly affect the convergence speed and accuracy of the proposed EDTM algorithm.To facilitate understanding, we use Figures3–5 to illustrate the process of obtaining the optimal migration path after MD m offloads tasks to UAV 1. In detail, Figure 3 shows that it is currently in the initial state and no task migration has occurred. There are 6 UAV nodes distributed from UAV node 1 to UAV node 6, respectively. Furthermore, node 1 is the initial node and node 6 is the destination node. All we need to do is plan an optimal path from node 1 to node 6. Before we start using the path elimination method, we first introduce the situation of the traditional ant colony algorithm in the early iteration, as shown in Figure 4. When the algorithm started running, UAV node 1 had to calculate the transition probability with the remaining 5 UAV nodes and then make a judgment, which means that the time complexity of the first iteration is On. As the number of iterations increases, the running time of the algorithm will increase at an exponential rate, that is, Onn2−2n+1.Figure 3
Initial state.Figure 4
The situation of the traditional ant colony algorithm in the early iteration.Figure 5
The situation of the traditional ant colony algorithm in the early iteration.
(a)(b)(c)(d)(e)To sum up, the traditional ant colony algorithm does have certain defects in the initial iteration. We start with the path elimination method, and the (a-e) graph contained in Figure5 corresponds to the five processes of optimal path acquisition.There are 6 nodes in Figure5(a), so it can be computed by the formula B=⌈20%⋅6⌉=⌈1.2⌉=2. As shown in Figure 5(a), the two nodes closest to node 1 are node 2 and node 3. The next-hop UAV node can be obtained by computing the transition probability. We assume that the computation result is node 3. Figure 5(b) shows two computation possibilities for the next node. For node 3, we only need to compare its transition probability with node 4 and node 6. We assume that the computation result is that node 4 as the next hop UAV node. Since the ant has searched for the destination node in the process of finding a valid node, we first update the migration node-set to Xut=1,3,6. Next, it is node 4 to start searching for new valid nodes. At this time, the two nodes closest to node 4 are node 1 and node 2. But since node 1 is the initial node, node 1 is excluded from the valid nodes. At this time, we need to compute the transition probability of node 2 and 5. We assume that the computation result is that node 2 as the next-hop node, as shown in Figure 5(c). As shown in Figure 5(d), the two nodes closest to node 2 and not yet visited are node 5 and node 6. Then we need to continuously compare the total migration cost with the migration cost of the previous migrated nodes set Xut=1,3,6 and select the optimal migration path. Finally, the migration node-set Xt is updated. Now, only the last UAV node is left, it is shown in Figure 5(e).


## 5.4. The Proposed EDTM Algorithm

In this section, we mainly introduce the specific process of the proposed EDTM algorithm to solve the joint optimization problem of load balancing and total energy consumption in the system. The number of target UAV nodes that we screen isr=⌈15%⋅U⌉. We select r UAV nodes with the shortest task backlog queue length (that is, the lowest load) as the target UAV nodes. After clarifying the target UAV node, we begin to use the proposed EDTM algorithm to compute the optimal migration path. Because the target UAV node is not unique, the final migration path must also be unique. We can divide the task and then migrate to these UAV nodes. These UAV nodes will perform the distributed processing on the task, and finally, return the results to MDs. The detailed process of the proposed EDTM algorithm is shown in Algorithm 1. In Algorithm 1, e represents the number of iterations, QUAVt represents the task backlog queue set of all UAVs nodes in the system at time slot t.Algorithm 1: The proposed EDTM algorithm.
Input:QUAVt,q0,α,β,λ,Q,num,A,rOutput:QUAVt+1,Xt(1)
Initialize the target UAV node Set and initial UAV nodes(2)
fore = 1: num do(3)
the ant looks for the next hop UAV node according to formula (23)(4)
getϕij,Δϕ,μ according to formula (24)–(26)(5)
Update the tabu table(6)
Update local pheromoneϕij(7)
Update global pheromoneϕijnew by formula (29)(8)
foru∈U(9)
B=⌈20%⋅U⌉(10)
Update migration node setX(11)
U=U−B(12)
Compute total migration costEtotalt(13)
Remove invalid UAV nodes and eliminate nonoptimal paths(14)
end for(15)
end forBesides, the special nature of the proposed EDTM algorithm, the task migration efficiency of multiple users will be higher. Because the ants look for UAV nodes and paths are based on the pheromone left by the previous ants, when there are multiple MDs that need task migration, it is no longer necessary to run the proposed EDTM algorithm to replan the migration path.


## 5.5. Experimental Results

In this experiment, we simulated a 600m × 600 m rectangular area in which a UAV group flies and provides services to MDs. The horizontal movement range of each UAV is 240 square meters. There is no limit to the flight trajectory of each UAV, but one thing we need to emphasize is that the initial position and end position of each UAV is always the same. We assume that the number of UAVs and MDs is 15 and 100, respectively. Besides, the service radius of each UAV is 150 m. The main parameters are defined in Table 3.Table 3
The definition of the main experimental parameters.
ParametersValueThe theoretical communication bandwidth10 MThe channel gainH0=170,ς=15.5The noise power2×10−9WThe maximum transmission power of the MDs1.7 WThe maximum transmitting power of the UAVs100 WThe maximum CPU cycle frequency of the MDs1.8 GHzThe maximum CPU cycle frequency of the UAVs20 GHzThe maximum memory of the UAVs1 TThe CPU effective capacitance switch of the MDs1.2×10−17The CPU effective capacitor switch of the UAVs3×10−16The density of processing tasks103 cycles/bitThe mass of each UAV19.7 kgThe maximum speed of the UAVs13 m/sThe initial height of the UAVs50 mThe gravitational acceleration9.8m/s2The air density1.293kg/m3The range of the UAV propeller rotations per second50,160The wind speed range3.5m/s,10m/s


## 5.6. Setting of Experimental Parameters

In this experiment, we simulated a 600 m × 600 m rectangular area in which a UAV group flies and provides services to MDs. The horizontal movement range of each UAV is 240 square meters. The flight trajectory of each UAV can be the same or different, but one thing we need to emphasize is that the initial position and end position of each UAV is always the same. We assume that the number of UAVs and MDs is 15 and 100, respectively. Besides, the service radius of each UAV is 150 m. In summary, each UAV is flying within a fixed range as an edge server and each MD offloads tasks that it cannot process or has a large amount of computation to the UAVs. The main parameters are defined in Table3.For some parameters in the proposed EDTM algorithm, we defineα=3, β=2, λ=1.5, A = 100, μ0=0.5, μmin=0.1, Q=20000, q0=0.7, σ=0.3. And we set the number of iterations of the entire algorithm during the run to 4500. Besides, we need to explain that if the values of α/β and α/λ are too large, the ant has a strong dependence on the pheromone when choosing the path, which will easily fall into a local optimum; otherwise, the ant will not rely on the pheromone left by other ants to make judgments.


## 5.7. The Effect ofB and r on the Proposed EDTM Algorithm

In this paper, to accelerate the early convergence speed of the proposed EDTM algorithm, we introduce the variableB. The value of B will directly affect the convergence speed and the accuracy of the results. The B value selected in Figure 6 and Figure 7 are 10%⋅u, 15%⋅u, 20%⋅u, 25%⋅u. Since we have a small number of UAVs, our percentage difference during the experiment is 5%. In Figure 6, the time points at which 25%⋅u, 20%⋅u, 15%⋅u, and 10%⋅u converge are 3560 ns, 4516 ns, 5231 ns, and 6010 ns, respectively. Especially, 25%⋅u has the fastest convergence speed and requires the fewest actual iterations. 10%⋅u has the slowest convergence speed, and it has the most iterations. In Figure 7, the ordinate represents the length of the optimal path. Also, we can know that 10%⋅u has the slowest convergence speed but it has the shortest optimal path length. And 25%⋅u has the fastest convergence speed, but its optimal distance is proportional to the other three best paths. In this paper, we need to consider both the convergence speed of the proposed EDTM algorithm and the accuracy of the results, so we choose B=⌈20%⋅U⌉. Next, we continue to analyze the effect of r value on the proposed EDTM algorithm. To guarantee the users Qos, we split the tasks and then migrate them to multiple UAVs. These UAVs jointly perform the task and then return the final computation result to the MDs. One of our research priorities is how many UAVs we migrate to during this process. As shown in Figures 8 and 9, we consider the impact of r value on the proposed EDTM algorithm from two aspects: migration cost and load balancing. In Figure 8, the migration costs corresponding to 5%⋅u, 10%⋅u, 15%⋅u and 21%⋅u increase with time. Among them, the migration cost of 5%⋅u is the lowest, and the migration cost of 21%⋅u is the highest. This is because the larger the number of target UAVs, the higher the final migration cost. Also, we can find from Figure 8, the migration cost of the system rises rapidly between 2263 ns and 3700 ns, which is because the requirements of the migration task conform to Poisson distribution.Figure 6
The number of iterations versus time andB.Figure 7
The optimum distance length versus time andB.Figure 8
The total migration cost versus time andr.Figure 9
The load status versus time andr.In Figure9, the ordinate indicates the extreme difference of the UAV task queue length as a percentage of its maximum task queue length at the current moment. We use the computation method of extreme difference to judge the load balancing of UAVs in the MEC system. As shown in Figure 9, 0.9 represents 90%, 0.8 represents 80%, and the following values are deduced by analogy. In the previous paper, we explained that our optimization goal is to ensure that the task queue length of each UAV does not exceed 10% of the average number of tasks in the queues, so we set a baseline in the experiment. Also, we can learn that 5%⋅u, 10%⋅u, 15%⋅u, 21%⋅u will all converge to 10%, which proves that the proposed EDTM algorithm can make the load of the UAV group reach equilibrium, but their convergence speed will be different. Among them, 21%⋅u has the fastest convergence speed, and 5%⋅u has the slowest convergence speed.In summary, we chooser=⌈15%⋅U⌉, which ensures the convergence speed of the proposed EDTM algorithm, and the system migration cost is low.


## 5.8. The Analysis of Weight Factor

In formula (20), we use two weighting factors, i.e., ϖ1 and ϖ2. Due to 0≤ϖ1≤1, 0≤ϖ2≤1 and ϖ1+ϖ2=1, we just need to choose the value of ϖ2. As shown in Figure 10, we selected ϖ2=0, ϖ2=0.1, ϖ2=0.2 and ϖ2=0.5. As ϖ2 decreases, ϖ1 will increase accordingly. At this time, the MEC system will tend to minimize the energy consumption of MDs. And the average energy consumption (AEC) of the UAVs will also increase with the acceleration. When the acceleration changes from 40 m/s2 to 47 m/s2, the AEC of the UAVSs has a growth jump, which mainly comes from two aspects. One is because we set the wind speed in the entire area as a random number in 3.5m/s,10m/s, a sudden increase in wind speed will increase the flight energy consumption of the UAVs, which in turn will increase the AEC of the UAVs.Figure 10
The AEC of UAVs versus acceleration and v2.In summary, we can find that the smaller theϖ2, the larger the AEC of the UAVs. When ϖ2=0, the AEC of the UAVs is the largest because the system goal is only to focus on minimizing the energy consumption of MDs.


## 5.9. The Analysis of the Proposed EDTM Algorithm Performance

In this section, we analyze the performance of the proposed EDTM algorithm. As shown in Figure11, the proposed E DTM algorithm converges after approximately 2650 iterations, while the ACO algorithm enters a convergence state after approximately 3460 iterations. Obviously, under the same conditions, the proposed EDTM algorithm converges faster than the ACO algorithm.Figure 11
The convergence comparison between the proposed EDTM algorithm and the ACO algorithm.As shown in Figure12, the abscissa represents time, and the ordinate represents the extreme difference of the UAV task queue length as a percentage of its maximum task queue length at the current moment in the UAV group. In this experiment, we assume that the process of task arrival conforms to the Poisson distribution, so we can know from Figure 12 that the task queue extreme value of the UAV group between 1500 ns and 2700 ns becomes large and rises very quickly. Between 2700 ns and 5000 ns, the proposed EDTM algorithm makes the extreme difference smaller and stays around 0.1 in the end.Figure 12
The comparison in optimizing UAVs load between the proposed EDTM algorithm and the algorithm ACO.According to the above experiment, the proposed EDTM algorithm is superior to the ACO algorithm in terms of convergence speed and optimization of load balancing efficiency of the UAV group. At the same time, we have also proven that the proposed EDTM algorithm can help the UAV group achieve load balancing.Besides, part of the current research work solves the task migration problem in MEC by setting up Markov Decision Process (MDP). For example, researchers proposed an MDP algorithm based on static distance (MDP-SD). Next, we compare the performance of the proposed EDTM algorithm and the MDP-SD algorithm in terms of migration cost and average load percentage of the UAV groups. As shown in Figure13, the reason why the curve changes as shown is because we assume that the computation task request conforms to the Poisson distribution. When t = 0, there is no computation task in the system, so the migration cost of UAVs is 0. When 0<t<1650 ns, the computation task request amount over time slowly rising, and the migration cost of the MDP-SD algorithm is slightly higher than that of the proposed EDTM algorithm. This is because the MDP-SD algorithm consumes more computing resources than the proposed EDTM algorithm when it uses the value iterative method to solve the migration strategy in the early stage. When 1650<t<3800 ns, the amount of computation task requests rises rapidly, and the migration cost of the two algorithms also increases rapidly. When t>3800 ns, the amount of computation task request decrease and the rate of increase in migration costs begin to decrease.Figure 13
The comparison of total migration cost between the proposed EDTM algorithm and the algorithm MDP-SD algorithm.After comparing the migration costs of the proposed EDTM algorithm and the MDP-SD algorithm, next, we compare the performance of the two algorithms from the average load percentage of the UAV groups. As shown in Figure14, 0.9 means that the task queue of the UAV groups at this time accounts for 90% of the total length of the task queue. Besides, the percentage of the task queue length under the MDP-SD algorithm is higher than the proposed EDTM algorithm. This is because we considered the small storage space and computing power of the UAVs when designing the proposed EDTM algorithm. So that the proposed EDTM algorithm does not occupy too much UAV resources. Also, because the amount of computation task request conforms to the Poisson distribution, when 0<t<2800 ns, the average task queue percentage of the UAV groups will increase. And when t=2800 ns, whether it is the proposed EDTM algorithm or the MDP-SD algorithm, the average task queue percentage of the UAV groups will reach the highest point. Until t>2800 ns, the average task queue percentage of the UAV groups slowly decrease. Obviously, from the perspective of the entire process, the average task queue percentage of the UAV groups under the proposed EDTM algorithm is always lower than the MDP-SD algorithm. Therefore, the proposed EDTM algorithm is more suitable for UAV-enabled MEC systems.Figure 14
The comparison of average task queue percentage of the UAV groups between the proposed EDTM algorithm and the MDP-SD algorithm.To sum up, we compare the performance of the algorithm from the following three aspects, including convergence time, energy consumption and maximum system load status. The experimental results are shown in Table4.Table 4
The performance comparison.
Convergence time (ns)Total energy consumption (J)Maximum system load status (%)ACO355010112089MDP36119131281EDTM20008999135


## 6. Conclusion

In this paper, we formulated the joint optimization problem in UAV-enabled MEC system, which considers migration costs, total system energy consumption, and load balance. To address this problem, we then propose the EDTM algorithm and path elimination rules, the weight factors and the pheromone update strategy in the algorithm show the stability and robustness of the system. Finally, simulation experiments demonstrate the efficacy of the proposed EDTM algorithm. For future works, we plan to apply the algorithm in a real environment and test its performance.



---

*Source: 4269102-2022-04-11.xml*