# Deep Reinforcement Learning-Based Dynamic Offloading Management in UAV-Assisted MEC System

Authors: Kang Tian; Yameng Liu; Haojun Chai; Boyang Liu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Unmanned aerial vehicles (UAVs) have been envisioned as a promising technique to provide relaying and mobile edge computing (MEC) services for ground user equipment (UE). In this paper, we propose a UAV-assisted MEC architecture in dynamic environment, where a UAV flies with a fixed trajectory and may act as a MEC server to process the tasks offloaded from the UE or act as a relay to help the UE to offload their tasks to the ground base station (BS). The objective of this work is to maximize the long-term number of completed tasks of the UE. An optimization problem is formulated to optimize the task offloading decisions of the UE. Considering the random demands of the UE, a deep reinforcement learning- (DRL-) based algorithm is proposed to solve the formulated nonconvex optimization problem. Simulation results verify the effectiveness and correctness of the proposed algorithm.


---

## Body

## 1. Introduction

The smart city paradigm brings massive computation-intensive and latency-sensitive applications, such as augmented reality (AR), virtual reality (VR), and video compression [1–3]. Due to the limited computing capability, it is hard for the user equipment (UE) to complete above applications in time without extra computing service. Although the mobile cloud computing can provide powerful computing service, the computation tasks needed to be transmitted to the remote cloud server, which may cause severe transmission delay and it is difficult for it to meet the delay demands of the applications. To address this issue, mobile edge computing (MEC) technique emerges.In MEC systems, MEC servers are deployed at the edge of the network to establish direct connection between the UE and the servers to provide real-time computing service for the UE [4]. The UE offloads computation tasks to the MEC servers through wireless channels. In traditional MEC architectures, MEC servers are typically deployed in fixed locations, such as being equipped at base stations (BS) or at the access points (AP). The quality of the communication links between the UE and MEC servers is easily influenced by dense buildings, which may lead to weak transmission signals or even interruption. This circumstance is especially serious in 5G scenarios due to the transmission characteristics of millimeter waves.Equipping the MEC server at unmanned aerial vehicle (UAV) can alleviate the problem stated above with its advantages of easy deployment, high flexibility, and maneuverability. The UAVs fly with predetermined trajectories in the air and have higher probability to establish line-of-sight (LoS) communication links with the ground UE. Hence, it is a great attempt to incorporate the UAVs in MEC systems to enlarge the MEC service coverage range and enhance the service capacity at the same time.To prolong the endurance of the UAV, the authors in [5] studied an energy consumption minimization problem; the scheduling, resource allocation, and the hovering time of the UAV were jointly designed. The authors in [6] jointly optimized the bit allocation and communications for uplink and downlink and the trajectory of the UAV to minimize the total mobile energy consumption. In [7], a UAV enabled MEC network was considered; the UAV position, time slot allocation, and computation task partition were jointly optimized to minimize the sum of energy consumption of ground users. In [8], the computing scheduling, 3D trajectory of the UAV, bandwidth, and transmission power allocation were jointly optimized to maximize the computation efficiency. In [9], the sum of the maximum delay among all the users was minimized by jointly optimizing the trajectory of the UAV, offloading task partition, and computing scheduling of the users.In [10], the computation rate was maximized by jointly optimizing the CPU frequencies, the length of the offloading times, the transmit power, and the trajectory of the UAV under both partial and binary computation offloading modes. A computation efficiency maximization problem was formulated in [11], and the user association, CPU frequency, spectrum resources, and the UAV trajectory were jointly optimized.Efforts in [5–11] focused on how to adopt the UAVs to provide computation services to the ground UE. In [12,13], the UAV was utilized not only as a MEC server but also as a relay to establish high-quality LoS wireless links between the UE and the remote ground high-performance MEC servers. The authors in [12] designed the trajectory of the UAV and the transmit power of the UE and the UAV to minimize the outage probability of the considered UAV-assisted MEC network. In [13], the computation resource scheduling parameters and the trajectory of the UAV were jointly optimized to minimize the weighted sum energy consumption subject to the task and the information causality, the bandwidth allocation, and the UAV’s trajectory constraints. In [14], the bits allocation, time slot scheduling, power allocation, and the trajectory of the UAV were jointly optimized to minimize the total energy consumption of the MEC network.The works mentioned above mainly concerned the resource allocation and trajectory design problems in static environment. However, the task arrivals or the locations of the ground UE may be randomly changed in practical scenarios [15–19]. Therefore, the dynamic environment should be taken into account during the design process of the UAV-assisted MEC system.In [15], the motion of the UE was considered, and a double Q-network based deep reinforcement learning (DRL) algorithm was proposed to maximize the system reward and meet the QoS constraint by optimizing the trajectory of the UAV and the association of the UE. In [16], a multi-UAV-assisted MEC system was studied, where multiple UAVs helped the BS for computing the tasks offloaded from the UE. An average mission response time minimization problem was formulated and solved by a conceived multiagent reinforcement learning algorithm. In [17], the task scheduling was optimized by a DRL-based method to balance the workload among multiple UAVs while guaranteeing the coverage constraint and the quality of service (QoS) demands of the UE. In [18], a three-layer online data processing network was proposed; the bottom layer was composed of sensors to generate raw data. The middle layer included multiple UAVs to collect and preprocess the data. The top layer was responsible for relieving the processed results and conducted further evaluation. Lyapunov optimization and DRL-based algorithms were proposed to schedule edge processing and plan the path online. In [19], the multiagent deep deterministic policy gradient method was adopted to design the trajectory of UAVs to jointly optimize the fairness among all the UE, the UAV’s UE-load, and the total energy consumption of the UE.It is worth noting that, due to the short battery life and the limited physical size, the UAVs cannot equip too powerful MEC servers. Hence, it is not practical to just rely on the UAVs to process all the tasks of the UE. The role of the UAVs in MEC systems should be a helper of the UE. The UAVs and the ground MEC servers (BS or AP) with strong computing power should coexist in UAV-assisted MEC systems. The main function of the UAVs should be establishing a communication link between the UE and the ground MEC servers. The secondary function of the UAVs is to provide limited computing service for the UE. Motivated by all facts analysed above, we investigate the task allocation problem in UAV-assisted MEC system in dynamic environment. The main contributions are summarized as follows:(1)
We propose a UAV-assisted MEC system in dynamic environment, where a UAV is deployed to provide relaying and edge computing service to the ground UE with randomly computation task arrivals at the beginning of each time slot.(2)
We formulate a long-term number of completed tasks maximization problem for the proposed UAV-assisted MEC system, which is nonconvex and difficult to solve. A DRL-based algorithm is proposed to solve the formulated problem.(3)
Simulation results are presented to evaluate the performance of the proposed algorithm. The convergence and effectiveness of the proposed algorithm are demonstrated by the simulation results.The remainder of this paper is organized as follows. Section2 presents the system model and formulates the optimization problem. The DRL-based optimization algorithm is described in Section 3. Simulation results are presented and discussed in Section 4. Finally, we conclude this study in Section 5.


## 2. System Model

In this section, we describe the system model and formulate a long-term number of completed tasks’ maximization problem. The key notations used in this paper are summarized in Table1.Table 1
Key notations used in this paper.
NotionDescriptionθnUEtComputation task arrived at the UEn at time slot t,t∈TLxInput data size of computation taskxτxMaximal tolerable latency of computation taskxCxThe number of CPU cycles required for computing 1 bit of the taskxθnUEtn,bCompThe first task processed at the UEnθnUEtn,bTrThe first task to be offloaded by the UEnθnUEtUAV,n,bCompThe first task of the UEn processed by the UAVθnUEtUAV,bTrThe first task of the UEn offloaded by the UAVμn,TrUExThe index of time slot that the taskx begins to be offloaded to the UAV by the UE nμTrUAVxThe index of time slot that the taskx of the UE n begins to be offloaded to the BS by the UAVTn,lCompxThe number of time slots required for computing the taskx of the UE n at localTUAV,nCompxThe number of time slots required for computing the taskx of the UE n by the UAVTnTrxThe number of time slots required for offloading the taskx to the UAV by the UE nTUAV,nTrxThe number of time slots required for offloading the taskx of the UE n from the UAV to the BSTn,CompWaitxThe number of time slots the taskx of the UE n will wait for local processingTn,TrWaitxThe number of time slots the taskx will wait for offloading at the UE nTUAV,n,CompWaitxThe number of time slots that the taskx of the UE n will wait for processing at the UAVTUAV,n,TrWaitxThe number of time slots the taskx of the UE n will wait for offloading at the UAVTn,endCompxThe index of time slot that the computation of the taskx of the UE n is completed by local computingTUAV,n,endCompxThe index of time slot that the computation of the taskx of the UE n is completed at the UAVTn,endTrxThe index of time slot that the offloading of the taskx is completed at the UE nTUAV,n,endTrxThe index of time slot that the offloading of the taskx of the UE n is completed by the UAVTn,l,totalCompxThe number of total time slots required for completing the taskx’s computation by the UE nTUE,n,totalTrxThe number of total time slots required for completing the offloading of the taskx by the UE nTUAV,totalCompxThe number of total time slots required for completing the computation of taskx of the UE n by the UAVTBS,totalCompxThe number of total time slots required for completing the computation of taskx of the UE n by the BSTn,l,total,trueCompxThe number of total time slots consumed for completing taskx by the UE nTUAV,total,trueCompxThe number of total time slots consumed for completing the computation of the taskx of the UE n by the UAVTBS,total,trueCompxThe number of total time slots consumed for completing the computation of the taskx of the UE n by the BS


### 2.1. Network Model

As shown in Figure1, we consider a UAV-assisted MEC system with one ground BS, one UAV, and N ground UE. A MEC server with strong computing power is equipped at the BS. Let N=1,2,…,N denote the set of UE. The system is assumed to be operated in a time-slotted manner with time slot length Δ. We are concerned about the long-term utility during T consecutive time slots. The set of time slots is denoted as T=1,2,…,T.Figure 1
The illustration of the UAV-assisted MEC system.In this paper, the three-dimensional Cartesian coordinate system is adopted. The BS and UE are fixed on the ground with zero altitude. The horizontal locations of the BS and the UEn,n∈N are denoted as lBS=xb,yb and lnUE=xn,yn, respectively. The altitude of the UAV is set to H, which is appropriate to avoid buildings in the work terrain. The UAV flies with a predetermined trajectory. The horizontal location of the UAV in time slot t,t∈T is denoted as lUAVt=xUt,yUt. As the length of each time slot is relatively short, the location of the UAV can be considered unchanged during each time slot, which is similar to [13].


### 2.2. Channel Model

In this paper, we consider the case that there are no direct links between the UE and the BS owing to the long distances and blockages between them. Similar to [9, 13, 14, 20, 21], we assume the air-ground wireless channels are dominated by LoS links. The channel power gains from the UAV to the ground BS and from the UAV to the UE n,n∈N at time slot t,t∈T are, respectively, given as(1a)gBSt=ρ0lUAVt−lBS2+H2,n∈N,t∈T,(1b)hnt=ρnlUAVt−lnUE2+H2,n∈N,t∈T,where ρn,n=0,1,…,N denote the channel power gain with reference distance 1 m.


### 2.3. Computation Model

At the beginning of each time slott,t∈T, each user n,n∈N has a new task arrival θnUEt, which can be represented by a 3-tuple LθnUEt,CθnUEt,τθnUEt, where LθnUEt denotes the size (in bits) of task θnUEt, CθnUEt denotes the computation complexity (i.e., the number of required CPU cycles for computing 1 bit of task θnUEt) of the task θnUEt, and τθnUEt is the maximal tolerable latency of the task θnUEt. We consider a random task arrival scenario: LθnUEt is randomly generated from a discrete set with Mn elements ΘLn=Ln,1,Ln,2,…,Ln,Mn. The corresponding task complexity set and maximal tolerable latency set of the task θnUEt are denoted as ΘCn=Cn,1,Cn,2,…,Cn,Mn and Θτn=τn,1,τn,2,…,τn,Mn, respectively.At the beginning of each time slot, the UE decides to execute the taskθnUEt either at local, offloading to the UAV, or relaying to the BS for processing. Let αn,t∈0,−1,1,n∈N,t∈T denote the task allocation variable. If αn,t=0, the task θnUEt is processed locally by the UE n,n∈N; if αn,t=−1, the task θnUEt is offloaded to the UAV for processing; otherwise, if αn,t=1, the task θnUEt is relayed by the UAV to the BS for processing. Similar to [22], we assume that if the task processing period exceeds its maximal tolerable latency, the task must be dropped immediately.All the UE and the UAV keep two queues for each UE: computation queue and transmission queue, which are operated with a first-in-first-out (FIFO) manner. Ifαn,t=0, the task θnUEt will be stored into the computation queue at the UE n,n∈N and wait for processing. If αn,t=±1, the task θnUEt will be stored into the transmission queue at the UE n,n∈N and wait for offloading to the UAV. If αn,t=−1, after receiving task θnUEt, the UAV will store θnUEt into the UE n’s computation queue at the UAV and wait for processing. If αn,t=1, after receiving task θnUEt, the UAV stores θnUEt into the UE n,n∈N’s transmission queue at the UAV and wait for relaying to the BS.


#### 2.3.1. Local Computing at the UEn,n∈N

The number of time slots required for computing the taskθnUEt at local is expressed as(2)Tn,lCompθnUEt=LθnUEtCθnUEtfnlΔ,n∈N,t∈T,where ⋅ is the ceiling function, and fnl is the CPU frequency of the UE n,n∈N. In practice, the task θnUEt may not be completed within one time slot. The subsequent tasks of the UE n,n∈N may wait for processing. Let Tn,CompWaitθnUEt denote the number of time slots the task θnUEt will wait for local processing, which is given as(3)Tn,CompWaitθnUEt=maxt′∈0,1,…,t−1Tn,endCompθnUEt′−t+1+,n∈N,t∈T,where x+=max0,x; Tn,endCompθnUEt′ is the index of time slot that the computation of the task θnUEt′ is completed, which is given as(4)Tn,endCompθnUEt′=Tn,CompWaitθnUEt′+Tn,lCompθnUEt′+t′−1,n∈N,t′∈T.Recursive method can be used to obtain the value ofTn,endCompθnUEt′ with Tn,CompWaitθnUEtn,bComp=0, where θnUEtn,bComp is the first task processed at the UE n,n∈N. Then, the number of total time slots required for completing the task θnUEt by the UE n,n∈N is given as(5)Tn,l,totalCompθnUEt=Tn,CompWaitθnUEt+Tn,lCompθnUEt,n∈N,t∈T.However, as mentioned above, if the task processing period ofθnUEt exceeds the maximal tolerable latency, θnUEt must be dropped immediately. Hence, the number of total time slots consumed for completing task θnUEtn,n∈N (including the time for waiting and processing) is given as(6)Tn,l,total,trueCompθnUEt=minTn,l,totalCompθnUEt,τθnUEt,n∈N,t∈T.


#### 2.3.2. Task Offloaded to the UAV for Computing

We adopt frequency-division multiple access (FDMA) for the UE’s task offloading. The total bandwidth of the channel between the UE and the UAV is equally allocated to each UE. Then, the offloading rate of the UEn,n∈N at time slot t,t∈T is given as(7)rnt=WUNlog21+PnUEhntσ2,n∈N,t∈T,where WU denotes the total available bandwidth between UE and the UAV, σ2 denotes the noise power at the UAV, and PnUE is the transmit power of the UE n,n∈N. Thus, the number of time slots required for offloading the task θnUEt to the UAV by the UE n,n∈N can be expressed as(8)TnTrθnUEt=argminm∑t′=μn,TrUEθnUEtμn,TrUEθnUEt+m−1rnt′Δ≥LθnUEt,m∈Z++,n∈N,t∈T,where Z++ denotes the set of positive integers; μn,TrUEθnUEt is the index of the time slot that the task θnUEt begins to be offloaded to the UAV by the UE n,n∈N.The taskθnUEt may not be able to be offloaded to the UAV within one time slot. The subsequent tasks of the UE n,n∈N may wait for offloading. The number of time slots the task θnUEt will wait for offloading at the UE n,n∈N is given as(9)Tn,TrWaitθnUEt=maxt′∈0,1,…,t−1Tn,endTrθnUEt′−t+1+,n∈N,t∈T.Tn,endTrθnUEt′ denotes the index of time slot that the offloading of the task θnUEt′ is completed at the UE n,n∈N, which is given as(10)Tn,endTrθnUEt′=Tn,TrWaitθnUEt′+TnTrθnUEt′+t′−1,n∈N,t′∈T.Similar to (4), recursive method can be used to obtain the value of Tn,endTrθnUEt′ with Tn,TrWaitθnUEtn,bTr=0, where θnUEtn,bTr is the first task to be offloaded by the UE n,n∈N. The number of total time slots required for completing the task θnUEt’s offloading by the UE n,n∈N is given as(11)TUE,n,totalTrθnUEt=Tn,TrWaitθnUEt+TnTrθnUEt,n∈N,t∈T.After the taskθnUEt’s offloading is finished, it will be stored in UE n’s computation queue at the UAV. We adopt a simple resource allocation scheme: the UAV equally allocates its computing resource to each UE. Then, the number of time slots required for computing the task θnUEt by the UAV is given as(12)TUAV,nCompθnUEt=LθnUEtCθnUEtfmax/N,n∈N,t∈T,where fmax is maximal CPU frequency of the UAV. The number of time slots that the task θnUEt will wait for processing at the UAV is given as(13)TUAV,n,CompWaitθnUEt=maxt′∈0,1,…,t−1TUAV,n,endCompθnUEt′−t+1+,n∈N,t∈T,where TUAV,n,endCompθnUEt′ is the index of time slot that the computation of the task θnUEt′ is completed at the UAV, which is given as(14)TUAV,n,endCompθnUEt′=TUAV,n,CompWaitθnUEt′+TUAV,nCompθnUEt′+t′−1,n∈N,t′∈T.We haveTUAV,n,CompWaitθnUEtUAV,n,bComp=0, where θnUEtUAV,n,bComp is the first task of the UE n,n∈N processed by the UAV. The number of total time slots required for completing the computation of the task θnUEt by the UAV (including the time for task offloading from the UE n,n∈N to the UAV and the waiting and processing time at the UAV) is given as(15)TUAV,totalCompθnUEt=TUE,n,totalTrθnUEt+TUAV,n,CompWaitθnUEt+TUAV,nCompθnUEt,n∈N,t∈T.The number of total time slots consumed for completing the computation of the taskθnUEt by the UAV is given as(16)TUAV,total,trueCompθnUEt=minTUAV,totalCompθnUEt,τθnUEt,n∈N,t∈T.


#### 2.3.3. Task Offloaded to the BS for Computing

We adopt time division multiple access (TDMA) scheme for the UAV to offload UE’s tasks to the BS. Each time slot is further divided intoN equal durations with length δ=Δ/N. The transmission rate from the UAV to the BS at time slot t,t∈T is given as(17)rBSt=WUlog21+PUAVgBStσb2,n∈N,t∈T,where σb2 is the power of noise at the BS; PUAV is the transmit power of the UAV. The number of time slots required for offloading the task θnUEt from the UAV to the BS is given as(18)TUAV,nTrθnUEt=argminm∑t′=μTrUAVθnUEtμTrUAVθnUEt+m−1rBSt′δ≥LθnUEt,m∈Z++,n∈N,t∈T,where μTrUAVθnUEt is the index of time slot that the task θnUEt begins to be offloaded to the BS by the UAV. The number of time slots the task θnUEt will wait for offloading at the UAV is given as(19)TUAV,n,TrWaitθnUEt=maxt′∈0,1,…,t−1TUAV,n,endTrθnUEt′−t+1+,n∈N,t∈T,where TUAV,n,endTrθnUEt′ is the index of time slot when the offloading of the task θnUEt′ is completed by the UAV, which is given as(20)TUAV,endTrθnUEt′=TUAV,TrWaitθnUEt′+TUAVTrθnUEt′+t′−1,n∈N,t′∈T.We haveTUAV,TrWaitθnUEtUAV,bTr=0 where θnUEtUAV,bTr is the first task of the UE n,n∈N offloaded by the UAV.Similar to [23–25], we assume that the computing power of the BS is strong enough and the computing time of UE’s tasks can be neglected. Then, the number of total time slots required for completing the computation of the task θnUEt by the BS (including the time required for task offloading from the UE θnUEt to the UAV, the waiting time, and the offloading time from the UAV to the BS) is given as(21)TBS,totalCompθnUEt=TUE,n,totalTrθnUEt+TUAV,TrWaitθnUEt+TUAVTrθnUEt,n∈N,t∈T.Similar to (6), the number of total time slots consumed for completing the computation of the task θnUEt by the BS is given as(22)TBS,total,trueCompθnUEt=minTBS,totalCompθnUEt,τθnUEt,n∈N,t∈T.


### 2.4. Problem Formulation

Our objective is to maximize the long-term number of completed tasks of the UE; i.e., maximize the number of the completed tasks of the UE duringT consecutive time slots. Towards this end, we formulate the optimization problem as(23)P1:maxαn,t,n∈N,t∈T∑t=1T∑n=1Nγt−1In,tθnUEts.t.αn,t∈−1,0,1,n∈N,t∈T,where γ∈0,1 is the discount factor, which denotes the difference on importance between future rewards and present reward [26]. In,tθnUEt is the indicator function that In,tθnUEt=0 if the task θnUEt is completed within its maximal tolerable latency, and In,tθnUEt=−1 if the task θnUEt is failed. Obviously, the problem P1 is nonconvex and difficult to solve by traditional optimization methods. In order to solve this problem, we propose a DRL-based algorithm.


## 2.1. Network Model

As shown in Figure1, we consider a UAV-assisted MEC system with one ground BS, one UAV, and N ground UE. A MEC server with strong computing power is equipped at the BS. Let N=1,2,…,N denote the set of UE. The system is assumed to be operated in a time-slotted manner with time slot length Δ. We are concerned about the long-term utility during T consecutive time slots. The set of time slots is denoted as T=1,2,…,T.Figure 1
The illustration of the UAV-assisted MEC system.In this paper, the three-dimensional Cartesian coordinate system is adopted. The BS and UE are fixed on the ground with zero altitude. The horizontal locations of the BS and the UEn,n∈N are denoted as lBS=xb,yb and lnUE=xn,yn, respectively. The altitude of the UAV is set to H, which is appropriate to avoid buildings in the work terrain. The UAV flies with a predetermined trajectory. The horizontal location of the UAV in time slot t,t∈T is denoted as lUAVt=xUt,yUt. As the length of each time slot is relatively short, the location of the UAV can be considered unchanged during each time slot, which is similar to [13].


## 2.2. Channel Model

In this paper, we consider the case that there are no direct links between the UE and the BS owing to the long distances and blockages between them. Similar to [9, 13, 14, 20, 21], we assume the air-ground wireless channels are dominated by LoS links. The channel power gains from the UAV to the ground BS and from the UAV to the UE n,n∈N at time slot t,t∈T are, respectively, given as(1a)gBSt=ρ0lUAVt−lBS2+H2,n∈N,t∈T,(1b)hnt=ρnlUAVt−lnUE2+H2,n∈N,t∈T,where ρn,n=0,1,…,N denote the channel power gain with reference distance 1 m.


## 2.3. Computation Model

At the beginning of each time slott,t∈T, each user n,n∈N has a new task arrival θnUEt, which can be represented by a 3-tuple LθnUEt,CθnUEt,τθnUEt, where LθnUEt denotes the size (in bits) of task θnUEt, CθnUEt denotes the computation complexity (i.e., the number of required CPU cycles for computing 1 bit of task θnUEt) of the task θnUEt, and τθnUEt is the maximal tolerable latency of the task θnUEt. We consider a random task arrival scenario: LθnUEt is randomly generated from a discrete set with Mn elements ΘLn=Ln,1,Ln,2,…,Ln,Mn. The corresponding task complexity set and maximal tolerable latency set of the task θnUEt are denoted as ΘCn=Cn,1,Cn,2,…,Cn,Mn and Θτn=τn,1,τn,2,…,τn,Mn, respectively.At the beginning of each time slot, the UE decides to execute the taskθnUEt either at local, offloading to the UAV, or relaying to the BS for processing. Let αn,t∈0,−1,1,n∈N,t∈T denote the task allocation variable. If αn,t=0, the task θnUEt is processed locally by the UE n,n∈N; if αn,t=−1, the task θnUEt is offloaded to the UAV for processing; otherwise, if αn,t=1, the task θnUEt is relayed by the UAV to the BS for processing. Similar to [22], we assume that if the task processing period exceeds its maximal tolerable latency, the task must be dropped immediately.All the UE and the UAV keep two queues for each UE: computation queue and transmission queue, which are operated with a first-in-first-out (FIFO) manner. Ifαn,t=0, the task θnUEt will be stored into the computation queue at the UE n,n∈N and wait for processing. If αn,t=±1, the task θnUEt will be stored into the transmission queue at the UE n,n∈N and wait for offloading to the UAV. If αn,t=−1, after receiving task θnUEt, the UAV will store θnUEt into the UE n’s computation queue at the UAV and wait for processing. If αn,t=1, after receiving task θnUEt, the UAV stores θnUEt into the UE n,n∈N’s transmission queue at the UAV and wait for relaying to the BS.


### 2.3.1. Local Computing at the UEn,n∈N

The number of time slots required for computing the taskθnUEt at local is expressed as(2)Tn,lCompθnUEt=LθnUEtCθnUEtfnlΔ,n∈N,t∈T,where ⋅ is the ceiling function, and fnl is the CPU frequency of the UE n,n∈N. In practice, the task θnUEt may not be completed within one time slot. The subsequent tasks of the UE n,n∈N may wait for processing. Let Tn,CompWaitθnUEt denote the number of time slots the task θnUEt will wait for local processing, which is given as(3)Tn,CompWaitθnUEt=maxt′∈0,1,…,t−1Tn,endCompθnUEt′−t+1+,n∈N,t∈T,where x+=max0,x; Tn,endCompθnUEt′ is the index of time slot that the computation of the task θnUEt′ is completed, which is given as(4)Tn,endCompθnUEt′=Tn,CompWaitθnUEt′+Tn,lCompθnUEt′+t′−1,n∈N,t′∈T.Recursive method can be used to obtain the value ofTn,endCompθnUEt′ with Tn,CompWaitθnUEtn,bComp=0, where θnUEtn,bComp is the first task processed at the UE n,n∈N. Then, the number of total time slots required for completing the task θnUEt by the UE n,n∈N is given as(5)Tn,l,totalCompθnUEt=Tn,CompWaitθnUEt+Tn,lCompθnUEt,n∈N,t∈T.However, as mentioned above, if the task processing period ofθnUEt exceeds the maximal tolerable latency, θnUEt must be dropped immediately. Hence, the number of total time slots consumed for completing task θnUEtn,n∈N (including the time for waiting and processing) is given as(6)Tn,l,total,trueCompθnUEt=minTn,l,totalCompθnUEt,τθnUEt,n∈N,t∈T.


### 2.3.2. Task Offloaded to the UAV for Computing

We adopt frequency-division multiple access (FDMA) for the UE’s task offloading. The total bandwidth of the channel between the UE and the UAV is equally allocated to each UE. Then, the offloading rate of the UEn,n∈N at time slot t,t∈T is given as(7)rnt=WUNlog21+PnUEhntσ2,n∈N,t∈T,where WU denotes the total available bandwidth between UE and the UAV, σ2 denotes the noise power at the UAV, and PnUE is the transmit power of the UE n,n∈N. Thus, the number of time slots required for offloading the task θnUEt to the UAV by the UE n,n∈N can be expressed as(8)TnTrθnUEt=argminm∑t′=μn,TrUEθnUEtμn,TrUEθnUEt+m−1rnt′Δ≥LθnUEt,m∈Z++,n∈N,t∈T,where Z++ denotes the set of positive integers; μn,TrUEθnUEt is the index of the time slot that the task θnUEt begins to be offloaded to the UAV by the UE n,n∈N.The taskθnUEt may not be able to be offloaded to the UAV within one time slot. The subsequent tasks of the UE n,n∈N may wait for offloading. The number of time slots the task θnUEt will wait for offloading at the UE n,n∈N is given as(9)Tn,TrWaitθnUEt=maxt′∈0,1,…,t−1Tn,endTrθnUEt′−t+1+,n∈N,t∈T.Tn,endTrθnUEt′ denotes the index of time slot that the offloading of the task θnUEt′ is completed at the UE n,n∈N, which is given as(10)Tn,endTrθnUEt′=Tn,TrWaitθnUEt′+TnTrθnUEt′+t′−1,n∈N,t′∈T.Similar to (4), recursive method can be used to obtain the value of Tn,endTrθnUEt′ with Tn,TrWaitθnUEtn,bTr=0, where θnUEtn,bTr is the first task to be offloaded by the UE n,n∈N. The number of total time slots required for completing the task θnUEt’s offloading by the UE n,n∈N is given as(11)TUE,n,totalTrθnUEt=Tn,TrWaitθnUEt+TnTrθnUEt,n∈N,t∈T.After the taskθnUEt’s offloading is finished, it will be stored in UE n’s computation queue at the UAV. We adopt a simple resource allocation scheme: the UAV equally allocates its computing resource to each UE. Then, the number of time slots required for computing the task θnUEt by the UAV is given as(12)TUAV,nCompθnUEt=LθnUEtCθnUEtfmax/N,n∈N,t∈T,where fmax is maximal CPU frequency of the UAV. The number of time slots that the task θnUEt will wait for processing at the UAV is given as(13)TUAV,n,CompWaitθnUEt=maxt′∈0,1,…,t−1TUAV,n,endCompθnUEt′−t+1+,n∈N,t∈T,where TUAV,n,endCompθnUEt′ is the index of time slot that the computation of the task θnUEt′ is completed at the UAV, which is given as(14)TUAV,n,endCompθnUEt′=TUAV,n,CompWaitθnUEt′+TUAV,nCompθnUEt′+t′−1,n∈N,t′∈T.We haveTUAV,n,CompWaitθnUEtUAV,n,bComp=0, where θnUEtUAV,n,bComp is the first task of the UE n,n∈N processed by the UAV. The number of total time slots required for completing the computation of the task θnUEt by the UAV (including the time for task offloading from the UE n,n∈N to the UAV and the waiting and processing time at the UAV) is given as(15)TUAV,totalCompθnUEt=TUE,n,totalTrθnUEt+TUAV,n,CompWaitθnUEt+TUAV,nCompθnUEt,n∈N,t∈T.The number of total time slots consumed for completing the computation of the taskθnUEt by the UAV is given as(16)TUAV,total,trueCompθnUEt=minTUAV,totalCompθnUEt,τθnUEt,n∈N,t∈T.


### 2.3.3. Task Offloaded to the BS for Computing

We adopt time division multiple access (TDMA) scheme for the UAV to offload UE’s tasks to the BS. Each time slot is further divided intoN equal durations with length δ=Δ/N. The transmission rate from the UAV to the BS at time slot t,t∈T is given as(17)rBSt=WUlog21+PUAVgBStσb2,n∈N,t∈T,where σb2 is the power of noise at the BS; PUAV is the transmit power of the UAV. The number of time slots required for offloading the task θnUEt from the UAV to the BS is given as(18)TUAV,nTrθnUEt=argminm∑t′=μTrUAVθnUEtμTrUAVθnUEt+m−1rBSt′δ≥LθnUEt,m∈Z++,n∈N,t∈T,where μTrUAVθnUEt is the index of time slot that the task θnUEt begins to be offloaded to the BS by the UAV. The number of time slots the task θnUEt will wait for offloading at the UAV is given as(19)TUAV,n,TrWaitθnUEt=maxt′∈0,1,…,t−1TUAV,n,endTrθnUEt′−t+1+,n∈N,t∈T,where TUAV,n,endTrθnUEt′ is the index of time slot when the offloading of the task θnUEt′ is completed by the UAV, which is given as(20)TUAV,endTrθnUEt′=TUAV,TrWaitθnUEt′+TUAVTrθnUEt′+t′−1,n∈N,t′∈T.We haveTUAV,TrWaitθnUEtUAV,bTr=0 where θnUEtUAV,bTr is the first task of the UE n,n∈N offloaded by the UAV.Similar to [23–25], we assume that the computing power of the BS is strong enough and the computing time of UE’s tasks can be neglected. Then, the number of total time slots required for completing the computation of the task θnUEt by the BS (including the time required for task offloading from the UE θnUEt to the UAV, the waiting time, and the offloading time from the UAV to the BS) is given as(21)TBS,totalCompθnUEt=TUE,n,totalTrθnUEt+TUAV,TrWaitθnUEt+TUAVTrθnUEt,n∈N,t∈T.Similar to (6), the number of total time slots consumed for completing the computation of the task θnUEt by the BS is given as(22)TBS,total,trueCompθnUEt=minTBS,totalCompθnUEt,τθnUEt,n∈N,t∈T.


## 2.3.1. Local Computing at the UEn,n∈N

The number of time slots required for computing the taskθnUEt at local is expressed as(2)Tn,lCompθnUEt=LθnUEtCθnUEtfnlΔ,n∈N,t∈T,where ⋅ is the ceiling function, and fnl is the CPU frequency of the UE n,n∈N. In practice, the task θnUEt may not be completed within one time slot. The subsequent tasks of the UE n,n∈N may wait for processing. Let Tn,CompWaitθnUEt denote the number of time slots the task θnUEt will wait for local processing, which is given as(3)Tn,CompWaitθnUEt=maxt′∈0,1,…,t−1Tn,endCompθnUEt′−t+1+,n∈N,t∈T,where x+=max0,x; Tn,endCompθnUEt′ is the index of time slot that the computation of the task θnUEt′ is completed, which is given as(4)Tn,endCompθnUEt′=Tn,CompWaitθnUEt′+Tn,lCompθnUEt′+t′−1,n∈N,t′∈T.Recursive method can be used to obtain the value ofTn,endCompθnUEt′ with Tn,CompWaitθnUEtn,bComp=0, where θnUEtn,bComp is the first task processed at the UE n,n∈N. Then, the number of total time slots required for completing the task θnUEt by the UE n,n∈N is given as(5)Tn,l,totalCompθnUEt=Tn,CompWaitθnUEt+Tn,lCompθnUEt,n∈N,t∈T.However, as mentioned above, if the task processing period ofθnUEt exceeds the maximal tolerable latency, θnUEt must be dropped immediately. Hence, the number of total time slots consumed for completing task θnUEtn,n∈N (including the time for waiting and processing) is given as(6)Tn,l,total,trueCompθnUEt=minTn,l,totalCompθnUEt,τθnUEt,n∈N,t∈T.


## 2.3.2. Task Offloaded to the UAV for Computing

We adopt frequency-division multiple access (FDMA) for the UE’s task offloading. The total bandwidth of the channel between the UE and the UAV is equally allocated to each UE. Then, the offloading rate of the UEn,n∈N at time slot t,t∈T is given as(7)rnt=WUNlog21+PnUEhntσ2,n∈N,t∈T,where WU denotes the total available bandwidth between UE and the UAV, σ2 denotes the noise power at the UAV, and PnUE is the transmit power of the UE n,n∈N. Thus, the number of time slots required for offloading the task θnUEt to the UAV by the UE n,n∈N can be expressed as(8)TnTrθnUEt=argminm∑t′=μn,TrUEθnUEtμn,TrUEθnUEt+m−1rnt′Δ≥LθnUEt,m∈Z++,n∈N,t∈T,where Z++ denotes the set of positive integers; μn,TrUEθnUEt is the index of the time slot that the task θnUEt begins to be offloaded to the UAV by the UE n,n∈N.The taskθnUEt may not be able to be offloaded to the UAV within one time slot. The subsequent tasks of the UE n,n∈N may wait for offloading. The number of time slots the task θnUEt will wait for offloading at the UE n,n∈N is given as(9)Tn,TrWaitθnUEt=maxt′∈0,1,…,t−1Tn,endTrθnUEt′−t+1+,n∈N,t∈T.Tn,endTrθnUEt′ denotes the index of time slot that the offloading of the task θnUEt′ is completed at the UE n,n∈N, which is given as(10)Tn,endTrθnUEt′=Tn,TrWaitθnUEt′+TnTrθnUEt′+t′−1,n∈N,t′∈T.Similar to (4), recursive method can be used to obtain the value of Tn,endTrθnUEt′ with Tn,TrWaitθnUEtn,bTr=0, where θnUEtn,bTr is the first task to be offloaded by the UE n,n∈N. The number of total time slots required for completing the task θnUEt’s offloading by the UE n,n∈N is given as(11)TUE,n,totalTrθnUEt=Tn,TrWaitθnUEt+TnTrθnUEt,n∈N,t∈T.After the taskθnUEt’s offloading is finished, it will be stored in UE n’s computation queue at the UAV. We adopt a simple resource allocation scheme: the UAV equally allocates its computing resource to each UE. Then, the number of time slots required for computing the task θnUEt by the UAV is given as(12)TUAV,nCompθnUEt=LθnUEtCθnUEtfmax/N,n∈N,t∈T,where fmax is maximal CPU frequency of the UAV. The number of time slots that the task θnUEt will wait for processing at the UAV is given as(13)TUAV,n,CompWaitθnUEt=maxt′∈0,1,…,t−1TUAV,n,endCompθnUEt′−t+1+,n∈N,t∈T,where TUAV,n,endCompθnUEt′ is the index of time slot that the computation of the task θnUEt′ is completed at the UAV, which is given as(14)TUAV,n,endCompθnUEt′=TUAV,n,CompWaitθnUEt′+TUAV,nCompθnUEt′+t′−1,n∈N,t′∈T.We haveTUAV,n,CompWaitθnUEtUAV,n,bComp=0, where θnUEtUAV,n,bComp is the first task of the UE n,n∈N processed by the UAV. The number of total time slots required for completing the computation of the task θnUEt by the UAV (including the time for task offloading from the UE n,n∈N to the UAV and the waiting and processing time at the UAV) is given as(15)TUAV,totalCompθnUEt=TUE,n,totalTrθnUEt+TUAV,n,CompWaitθnUEt+TUAV,nCompθnUEt,n∈N,t∈T.The number of total time slots consumed for completing the computation of the taskθnUEt by the UAV is given as(16)TUAV,total,trueCompθnUEt=minTUAV,totalCompθnUEt,τθnUEt,n∈N,t∈T.


## 2.3.3. Task Offloaded to the BS for Computing

We adopt time division multiple access (TDMA) scheme for the UAV to offload UE’s tasks to the BS. Each time slot is further divided intoN equal durations with length δ=Δ/N. The transmission rate from the UAV to the BS at time slot t,t∈T is given as(17)rBSt=WUlog21+PUAVgBStσb2,n∈N,t∈T,where σb2 is the power of noise at the BS; PUAV is the transmit power of the UAV. The number of time slots required for offloading the task θnUEt from the UAV to the BS is given as(18)TUAV,nTrθnUEt=argminm∑t′=μTrUAVθnUEtμTrUAVθnUEt+m−1rBSt′δ≥LθnUEt,m∈Z++,n∈N,t∈T,where μTrUAVθnUEt is the index of time slot that the task θnUEt begins to be offloaded to the BS by the UAV. The number of time slots the task θnUEt will wait for offloading at the UAV is given as(19)TUAV,n,TrWaitθnUEt=maxt′∈0,1,…,t−1TUAV,n,endTrθnUEt′−t+1+,n∈N,t∈T,where TUAV,n,endTrθnUEt′ is the index of time slot when the offloading of the task θnUEt′ is completed by the UAV, which is given as(20)TUAV,endTrθnUEt′=TUAV,TrWaitθnUEt′+TUAVTrθnUEt′+t′−1,n∈N,t′∈T.We haveTUAV,TrWaitθnUEtUAV,bTr=0 where θnUEtUAV,bTr is the first task of the UE n,n∈N offloaded by the UAV.Similar to [23–25], we assume that the computing power of the BS is strong enough and the computing time of UE’s tasks can be neglected. Then, the number of total time slots required for completing the computation of the task θnUEt by the BS (including the time required for task offloading from the UE θnUEt to the UAV, the waiting time, and the offloading time from the UAV to the BS) is given as(21)TBS,totalCompθnUEt=TUE,n,totalTrθnUEt+TUAV,TrWaitθnUEt+TUAVTrθnUEt,n∈N,t∈T.Similar to (6), the number of total time slots consumed for completing the computation of the task θnUEt by the BS is given as(22)TBS,total,trueCompθnUEt=minTBS,totalCompθnUEt,τθnUEt,n∈N,t∈T.


## 2.4. Problem Formulation

Our objective is to maximize the long-term number of completed tasks of the UE; i.e., maximize the number of the completed tasks of the UE duringT consecutive time slots. Towards this end, we formulate the optimization problem as(23)P1:maxαn,t,n∈N,t∈T∑t=1T∑n=1Nγt−1In,tθnUEts.t.αn,t∈−1,0,1,n∈N,t∈T,where γ∈0,1 is the discount factor, which denotes the difference on importance between future rewards and present reward [26]. In,tθnUEt is the indicator function that In,tθnUEt=0 if the task θnUEt is completed within its maximal tolerable latency, and In,tθnUEt=−1 if the task θnUEt is failed. Obviously, the problem P1 is nonconvex and difficult to solve by traditional optimization methods. In order to solve this problem, we propose a DRL-based algorithm.


## 3. A Reinforce with Baseline Optimization Framework

As we adopt FDMA and TDMA and the computing resource of the UAV is equally allocated to all UE, problemP1 can be decomposed into N subproblems. The subproblem of the UE n,n∈N is given as(24)Pn:maxαn,t,t∈T∑t=1Tγt−1In,tθnUEts.t.αn,t∈−1,0,1,t∈T.We adopt the parameterized policy gradient approach with baseline method to obtain the optimal task allocation of the UEn,n∈N. In order to apply the DRL algorithm, we first give the state, action, reward function, and the policy of the UE n,n∈N as follows:(1)
System stateSnt: the state of the UEn,n∈N in time slot t,t∈T is given as(25)Snt=s1t,s2t,s3t,s4t,s5t,s6t,s7t,s8t,s9t,wheres1t=maxt′∈0,1,…,t−1Tn,endCompθnUEt′, s2t=maxt′∈0,1,…,t−1TUAV,n,endCompθnUEt′, s3t=maxt′∈0,1,…,t−1TUAV,n,endTrθnUEt′, s4t=LθnUEt, s5t=CθnUEt, s6t=τθnUEt, s7t=Tn,l,total,trueCompθnUEt, s8t=TUAV,total,trueCompθnUEt, s9t=TBS,total,trueCompθnUEt.(2)
ActionAnt: Ant is the task allocation variable of the UE n,n∈N, namely,(26)Ant=αn,t,n∈N,t∈T.(3)
Reward functionRnt: reward function Rnt,n∈N,t∈T is the immediate reward when selecting action Ant in state Snt, which is directly related with the objective of the optimization problem Pn. Hence, the reward function is defined as(27)Rnt=0,Ti,totalCompθnUEt≤τθnUEt,i=n,UAV,BS,−1,Ti,totalCompθnUEt>τθnUEt,i=n,UAV,BS.(4)
Policyπn,θn: the policy πn,θn denotes the mapping from the state Snt to the action Ant of the UE n,n∈N, i.e., πn,θn:Snt⟶Ant. θn is the parameter of the policy.Our goal is to find an optimal policy for the UEn,n∈N; the problem Pn can be transformed into(28)Pn,DRL:maxπn,θn∑t=1Tγt−1In,tθnUEts.t.23a.The parameterized policy gradient approach adopts a parameterized policy and optimizes the parameters through gradient iteration algorithm [26]. A typical scalar performance measure Uθn is given as vπn,θnSn0, which is the value function for policy πn,θn starting from initial state Sn0. In the episodic case, an analytic expression for the gradient of Uθn is provided by policy gradient theorem [26], which is given as(29)∇Uθn∝∑SntμSnt×∑Antqπn,θnSnt,Ant∇πn,θnAnt|Snt,where μSnt is the on-policy distribution over states; qπn,θnSnt,Ant is the value of taking action Ant in state Snt under policy πn,θn.In order to reduce the variance during the learning process, an action-independent baselinebSnt can be introduced, and the policy gradient with baseline is denoted as [26](30)∇Uθn∝∑SntμSnt×∑Antqπn,θnSnt,Ant−bSnt∇πn,θnAnt|Snt.The estimate of the state valuevSnt;w is often selected as the baseline, where w is the weight vector of the state value function. Considering the baseline, θn is updated as [26](31)θn,t+1=θn,t+αγtG−vSnt;w∇lnπn,θn,tAnt|Snt,where α is the learning rate, G is the return following time slot t,t∈T, and θn,t is the estimate of θn at time slot t,t∈T. The details of the DRL-based algorithm are given in Algorithm 1.Algorithm 1: The DRL-based algorithm.
(1)
Initialization:(2)
θ, w, a differentiable policy πn,θn, maximal number of iterations Kmax, discount factor γ, the learning rate of policy αp>0, the learning rate of the baseline αb>0;(3)
fork=1:Kmax:(4)
According to the policyπn,θn, (24)–(26) to generate trajectory: Sn0,An0,Rn1,Sn1…SnT−1,AnT−1, RnT;(5)
G⟵0;(6)
fort=T−1,T−2,…,0:(7)
Update return:G⟵γG+Rnt;(8)
Updatew: w⟵w+αbG−vSnt;w∇vSnt;w;(9)
Updateθn: update θn by (30) with α=αp;(10)
end for(11)
end for


## 4. Simulation Results

In this section, the performances of the proposed algorithm under different parameters are provided. According to the analysis above, solving problemP1 is equivalent to solving each subproblem Pn. Therefore, we focus on the analysis of the performance for the UE n,n∈N instead of for all the UE. The default simulation parameters are set as follows, if not specified. The computation data size (in bits) of the task θnUEt is randomly selected from set ΘLn=1.5e4bits,3e4bits,4.5e4bits,6e4bits. The corresponding maximal tolerable latency set of the task θnUEt is set as Θτn=3Δ,5Δ,7Δ,9Δ. Without loss of generality, we set CθnUE=β,β=1000, which can be ignored in the system state. The UAV flies around in circles with center coordinates 0,0 and radius 20 m. The UE is uniformly distributed in a 100 m × 100 m square area with center coordinate (0, 0) m, which is the coordinate of the BS. The maximal CPU frequency of the UAV and the UE n,n∈N are set as 200 MHz and 10 MHz, respectively. The bandwidth of the channel between the UE n,n∈N and the UAV and between the UAV and the BS is set as 40 kHz and 200 kHz, respectively. T is set as 100. The length of the time slot Δ and sub-time slot δ is set as 100 ms and 20 ms, respectively. We conduct the simulations through Python 3.8 and Tensorflow 2.5.0. Fully connected hidden layer with 17 and 16 neurons in the policy and the baseline networks are employed. The learning rates of policy and baseline networks change in different figures to guarantee the convergence of the proposed algorithm.Figures2 and 3 show the convergence performance of proposed algorithm versus different learning rate αp. The learning rate is important in iterative algorithms. As shown in Figure 2, the larger the learning rate is, the faster the convergence speed of the algorithm is. However, if the learning rate αp is too large, the variance of the learning curve may become high, which can be observed in Figure 3.Figure 2
The impact of learning rateαp on the accumulated reward, where αp=1e−4,1e−5,2e−5,3e−5, and αb=5e−5.Figure 3
The impact of learning rateαp on the accumulated reward, where αp=1e−3 and αb=5e−5.Figure4 shows the convergence performance of proposed algorithm versus different learning rate αb. As can be observed in Figure 4 the convergence speed of the algorithm is not monotonically increasing in the learning rate αb. The learning rate αb=5e−5 has faster convergence speed than the cases αb=5e−2 and αb=5e−4. αb=5e−2 has faster convergence speed than the case αb=5e−4. Although the convergence speed of the different learning rate αb cases is different, they will converge to the same order of accumulated reward.Figure 4
The impact of learning rateαb on the accumulated reward, where αb=5e−2,5e−4,5e−5, and αp=3e−5.Figure5 shows the performance of the proposed algorithm versus the complexity of the tasks of the UE n,n∈N. As can be seen from Figure 5 the complexity of the task directly affects the performance of the proposed algorithm. The higher the complexity is, the lower the accumulated reward is, which agrees with intuitions.Figure 5
The impact of complexity on the accumulated reward.Figure6 shows the performance of the proposed algorithm versus the computing power of the UE n,n∈N. As shown in Figure 6 the accumulated reward increases with the computing power of the UE n,n∈N. The stronger the computing power of the UE n,n∈N is, the higher the accumulated reward of the UE n,n∈N is.Figure 6
The impact of computing power of the UEn,n∈N on the accumulated reward.Figure7 shows the effects of the length of time slot Δ. It can be observed that the accumulated reward increases with the length of time slot Δ. When Δ is too short, most of the tasks of the UE n,n∈N may fail.Figure 7
The impact of the length of time slotΔ on the accumulated reward.


## 5. Conclusion

We studied the problem of maximizing the long-term number of completed tasks of the UE in a proposed UAV-assisted MEC system. The formulated nonconvex problem was decomposed and solved by our proposed DRL-based algorithm. The validity and the convergence of the proposed algorithm were demonstrated through simulation results.



---

*Source: 2491389-2022-02-16.xml*