Computation Offloading and Trajectory Control for UAV-Assisted Edge Computing Using Deep Reinforcement Learning

Abstract

Task offloading has attracted widespread attention in accelerating applications and reducing energy consumption. However, in areas with surging traffic (nucleic acid testing, concerts, etc.), the limited resources of fixed-base stations cannot meet user requirements. Unmanned aerial vehicles (UAVs) can effectively serve as temporary-base stations or aerial access points for mobile devices (MDs). In the UAV-assisted MEC system, we intend to jointly optimize the trajectory and user association to maximize computational efficiency. This problem is a non-convex fractional problem; therefore, it is not feasible to use only a traditional method, such as Dinkelbach’s method, for solving a fractional problem. Therefore, to facilitate online decision making for this joint optimization problem, we introduce deep reinforcement learning (DRL) and propose a double-layer cycle algorithm for maximizing computation efficiency (DCMCE). Specifically, in the outer loop, we model the trajectory planning problem as a Markov decision process, and use deep reinforcement learning to output the best trajectory. In the inner loop, we use Dinkelbach’s method to simplify the fraction problem, and propose a priority function to optimize user association to maximize computational efficiency. Simulation results show that DCMCE achieves higher computational efficiency than the baseline scheme.

1. Introduction

Mobile edge computing (MEC) provides storage and computing resources at the network edge to speed up application execution and reduce the energy consumption of IoT devices [1]. However, traditional fixed-position edge computing nodes have been unable to meet the needs of the future more complex dynamic environment.

For example, when large-scale gathering activities (e.g., temporary nucleic acid tests, football matches, etc.) occur, people from different communities gather in a specific area within a period and the temporary increase in mobile devices far outstrips the capacity of web services [2], resulting in high data transmission delay and network congestion.

The high mobility and flexibility of UAVs have attracted wide attention. If the UAV is equipped with advanced transceivers and computing resources, it can be used as a mobile base station and mobile relay to solve the challenges faced by MEC networks with fixed edge computing nodes, such as complex computing tasks, limited communication resources and network congestion. Gupta et al. studied and proposed an iterative greedy algorithm to maximize throughput by optimizing the flight time and flight trajectory of UAVs [3]. Wu et al. investigated the problem of maximizing the minimum average throughput of all users in UAV-driven orthogonal frequency division multiple access (OFDMA) networks, using successive convex optimization and Lagrange duality to alternately optimize UAVs’ trajectory and OFDMA resource allocation [4].

However, UAVs are also limited by the size of the aircraft and the size of the onboard batteries. Therefore, it is necessary to identify an efficient mechanism to utilize this limited energy to improve UAVs’ communication performance and extend their endurance. Zeng et al. introduced research on the wireless communication of the wireless system of a rotary UAV, which utilized the successive convex approximation technique to jointly optimize the UAV’s trajectory and communication time to minimize the total energy consumption of the system [5]. Lyu et al. maximized the computational bits of the system by optimizing bandwidth, time allocation and UAV trajectory. To simplify the problem, the target problem is transformed into three sub-optimization problems, and the optimal solution is obtained by using the convex optimization technique and block coordinate descent algorithm successively [6]. The above methods work well in static scenarios, where tasks are determined and users do not move. However, in dynamic scenarios, these methods are calculated multiple times with changes, which leads to a complicated calculation and fails to achieve the expected results.

Deep reinforcement learning (DRL) allows the agent to understand and store knowledge about the UAV-MEC network environment which can obtain optimal policies and solve complex non-convex optimization problems without an accurate environment. In a dynamic network environment, DRL has been used to solve decision and control problems [7,8]. Under the constraint of energy consumption, the author proposed a DRL-based trajectory control algorithm to minimize the energy consumption of all MDs by optimizing user association, resource allocation and UAV trajectories [7]. Wang et al. proposed a DRL-based algorithm that minimizes local and offload processing delays by jointly optimizing the user selection, task offload rate and location of UAVs [8]. Zeng et al. investigated the problem of a UAV providing wireless services, and proposed a TRPO-based approach to maximize the energy efficiency of the UAV by optimizing the control of the UAV, considering the dynamic environment caused by the movement of the UAV and the user [9]. These works perform well when only dealing with continuous variables; however, when the solution contains both integer and continuous variables (such as user association decisions), the continuous values of neural network output need to be mapped to integers, which will lead to certain loss of accuracy and even fall into local optimal solutions.

To solve the above challenges, this paper proposes a double-layer cycle algorithm for maximizing computational efficiency (DCMCE) based on proximal policy optimization (PPO). First, the outer layer uses a DRL algorithm to determine the UAV’s movements, and then the inner layer uses the association algorithm to calculate the total user computing efficiency, taking the maximum computing efficiency as the reward of the outer loop. Through iteration, the optimal computational efficiency of the whole cycle is obtained.

The rest of the paper is organized as follows. Section 2 presents the related work of the paper and Section 3 presents the system model and asks the questions. In Section 4, we introduce our proposed method. Section 5 discusses the simulation results. Finally, the paper is concluded in Section 6.

2. Related Work

2.1. Offloading Scheme for UAV-Assisted Edge Computing

Part of the current literature use heuristic algorithms to solve optimization problems in UAVs. Zhang et al. constructed a computational efficiency maximization problem for a UAV-assisted MEC system and proposed a two-layer cyclic algorithm to optimize computational offloading mode, user scheduling, CPU frequency, power allocation and UAV trajectory planning [10]. Hu et al. proposed an alternate optimization algorithm under the constraints of task completion time, bandwidth allocation and UAV trajectory with an iterative approach to minimize the weighting and energy consumption of the UAV and the users [11].

2.2. Offloading Scheme Based on Deep Reinforcement Learning

Some of the literature tries to solve the computation offloading problem with deep reinforcement learning. Users can benefit from offloading tasks to the MEC server. Ke et al. considered the MEC server to perform random computing tasks and involve a time-varying wireless channel model, proposed the weighted total cost function of transmission delay, energy consumption and bandwidth allocation by using computational offloading, and proposed an actor–critic based asynchronous method to minimize the total system cost [12]. Guan et al. aimed to minimize the long-term average transmission power consumed by users by dynamically optimizing user association and power allocation in each slot [13]. Chen et al. proposed a new method based on a deep Q-network (DQN) to obtain a near-optimal computation offloading strategy for MEC networks [14]. The authors proposed a method which adopts deep deterministic policy gradient to make optimization decisions for computation offloading according to the real-time state of the network and the properties of the task. Considering multitasking, heterogeneity of edge subnets and mobility of edge devices, the algorithm can learn the network environment and generate computation offloading decisions to minimize task latency [15].

2.3. Offloading Scheme of UAV-Assisted Edge Computing Based on Deep Reinforcement Learning

Some of the literature tries to apply DRL in a UAV-assisted MEC system. Zhang et al. proposed a new DRL approach to optimize UAV trajectory control and user offload task ratio to minimize the energy consumption and latency of UAV-assisted MEC systems [11]. The authors studied the schedulability problem of large-scale UAV-assisted MECs, decomposed the scheduling problem into two levels of sub-problems and proposed a scalable scheduling algorithm based on hierarchical reinforcement learning alternating optimization [16]. Ding et al. proposed a two-stage algorithm based on DRL to solve the trajectory design of UAVs to minimize their energy consumption and to solve the problem of band allocation under fairness among ground users [17]. Cai et al. propose a new collaborative data sensing and computational offloading scheme for a UAV-assisted MCS system to maximize the overall utility of the system in remote areas [18]. Piao et al. explicitly consider navigating multiple unmanned vehicles to perform sensing tasks in the presence of multiple charging stations. To meet the challenges of maximizing the ratio of data acquisition to fairness and minimizing energy consumption for all vehicles, a new sequential DRL model is proposed [19].

Good results have been achieved, but there are still some problems:

• These methods perform well in static environments. However, due to the complexity of the environment, such information is often unavailable, so the offloading effect is not as good as expected.

• These deep reinforcement learning algorithms are not effective when dealing with both discrete and continuous variables.

Therefore, although DRL has achieved excellent results in many fields, such as games, it is still a direction worth exploring in the UAV-MEC field.

3. System Model

As shown in Figure 1, we consider a UAV-assisted MEC system consisting of $M$ users and a UAV. Each user has an MD, and the set of MDs is described by $ℳ\triangleq \left\{1,2,\dots ,M\right\}$. The UAV is configured with an edge server with powerful computing power and flies to an area of size $L\times W$, providing services for the MDs. Tasks that need to be offloaded from the MDs can be unloaded to the UAV over the wireless link. The system runs during the specified task period, the slot length of each task period is $\tau$, indexed by $n\in \mathcal{T}\triangleq \left\{1,2,\dots ,N\right\}$. During each slot, the UAV is assumed to serve its associated MDs. Each user $i\in ℳ$ is scattered randomly in a dense area, and its horizontal coordinate is given by $u_i\left(n\right)=\left(x_i\left(n\right),y_i\left(n\right)\right)$. Suppose the UAV is flying at a constant altitude $H$ above the ground, the horizontal coordinate of the UAV can be expressed as $q\left(n\right)=\left(x\left(n\right),y\left(n\right)\right)$. The UAV flies for $t_{fly}$ seconds in each slot and hovers the rest of the time. the distance between the user $i$ and the UAV in the time slot $n$ can be expressed as the Formula (1).

(1)$d_i\left(n\right)=\sqrt{H^2+{\parallel q\left(n\right)-u_i\left(n\right)\parallel }^2}$

For UAV-MD wireless communications, line-of-sight (LoS) channels typically have advantages over other channels. A wireless channel-free space path loss model for UAVs is similar to [20], and can be expressed as Formula (2).

(2)$h_i\left(n\right)={\beta }_0{\left(d_i\left(n\right)\right)}^{-2}$

where $d_i$ is the distance between the i-th MD and the UAV, and ${\beta }_0$ is the channel power gain at the reference distance $d_0=1 m$. Furthermore, we consider that the maximum horizontal coverage of the UAV is $R^{max}$. This UAV’s energy usage can be described using a Formula (3).

(3)$E_{fly}\left(n\right)=\varphi \parallel v\left(n\right){\parallel }^2$

where $\varphi =0.5M_{\mathrm{UAV}}{t}_{fly}$ [8], $M_{\mathit{UAV}}$ is related to the payload of the UAV and $v\left(n\right)$ indicates velocity at time slot $n$.

Each MD can assign missions to a UAV or conduct them locally. To distinguish between various states, a binary variable $s_i\left(n\right)\in \left\{0, 1\right\}$ is introduced. If $s_i\left(n\right)=1$, then user $i$ is connected to and being serviced by UAV at slot n; if not, $s_i\left(n\right)=0$.

3.1. Local Computing

Each MD has limited computing power, denoted as $f_i\left(n\right)$. The quantity of CPU cycles needed to complete one computation task in one bit is $\rho$. Therefore, the computation bits performed at user $i$ at time slot n can be obtained, as shown in the Formula (4).

(4)$R_i^l\left(n\right)=\frac{f_i\left(n\right)\tau }{\rho }$

According to [21], $p_i^l\left(n\right)=\kappa f_i^3\left(n\right)$ is a model for how much power user $i$ uses for local computation. The value of $\kappa$, the CPU’s effective switched capacitance, depends on the design of the chip. Therefore, the energy consumption of user $i$ in the period $\tau$ can be expressed as Formula (5).

(5)$E_i^l\left(n\right)=\kappa f_i^3\left(n\right)\tau$

3.2. UAV-Assisted Edge Computing

The data from the task can be transmitted via a wireless uplink when the task is carried out by a UAV. The spectral bandwidth of each user is $B_0$. The computation bits offloaded from the user are expressed as Formula (6).

(6)$R_i^c\left(n\right)=B_0\tau {\log }_2\left(1+\frac{p_i\left(n\right)h_i\left(n\right)}{N_0+w_i\left(n\right)P_{NLOS}}\right)$

Among them, $N_0$ represents the noise power spectral density, $p_i\left(n\right)$ represents the transmit power of user $i$ in time slot $n$, and $w_i\left(n\right)$ represents whether there is an obstacle between the UAV and user $i$ at time slot $n$. $P_{NLOS}$ represents transmission loss. Formula (7) is used to express the corresponding amount of energy used to transmit computation bits.

(7)$E_i^c\left(n\right)=p_i\left(n\right)\tau$

Local computation bits and offloading bits, which are determined using Formula (8), make up the total computation bits.

(8)$R\left(\mathrm{s}\left(n\right),\mathrm{q}\left(n\right)\right)={\displaystyle {\displaystyle \sum }_{n=1}^N}{\displaystyle {\displaystyle \sum }_{i=1}^M}\left\{\left(1-s_i\left(n\right)\right)R_i^l\left(n\right)+s_i\left(n\right)R_i^c\left(n\right)\right\}$

In addition to the energy consumption of transmission and calculation and flight of the UAV, the actual system also involves baseband processing of other static energy consumption. The static power $P_c$ is assumed to be constant, irrespective of other energy consumption [10]. Then, the total energy consumption can be expressed as Formula (9).

(9)$E\left(\mathrm{s}\left(n\right),\mathrm{q}\left(n\right)\right)={\displaystyle {\displaystyle \sum }_{n=1}^N}{\displaystyle {\displaystyle \sum }_{i=1}^M}\left\{\kappa f_i^3\left(n\right)+s_i\left(n\right)p_i\left(n\right)+P_c\right\}\tau$

According to [10], the computational efficiency is defined as the ratio of the total computation bits to the total energy consumption.

(10)$\eta =\frac{R\left(\mathrm{s}\left(n\right),\mathrm{q}\left(n\right)\right)}{E\left(\mathrm{s}\left(n\right),\mathrm{q}\left(n\right)\right)}$

3.3. Problem Establishment

The flying trajectory of the UAV and the transmission power of the MD are collaboratively optimized to maximize the user’s calculation efficiency, in order to make the best use of the available computing resources. As a result, the UAV-assisted MEC system’s computing efficiency maximization problem can be stated as:

(11)$\begin{array}{c}P:\underset{\mathrm{s}\left(n\right),\mathrm{p}\left(n\right)}{max} \eta \\ C1:0⩽p_i\left(n\right)⩽p_{i,max},\forall i,n,\\ C2:s_i\left(n\right)⩽1,\forall i,n,\\ C3:\parallel \mathrm{q}\left(n+1\right)-\mathrm{q}\left(n\right)\parallel ⩽V_{max}\tau ,\forall n,\\ C4:\mathrm{q}\left(1\right)={\mathrm{q}}_I,\\ C5:0<x_i\left(\mathrm{n}\right)<L,0<y_i\left(\mathrm{n}\right)<W, \forall i,\\ C6:0<x\left(\mathrm{n}\right)<L,0<y\left(\mathrm{n}\right)<W.\end{array}$

In the optimization problem $P$, $\eta$ is the total computational efficiency of the MDs. $C1$ denotes the transmission power restriction, and all MDs’ transmission powers are constrained to not go over the maximum transmission power. $C2$ represents the user association constraint, indicating that the task is performed on the UAV. $C3$ denotes that the UAV’s maximum flying speed cannot be exceeded. In $C4$, The UAV starts from the same place as in ${\mathrm{q}}_I$, which is its initial position. $C5$ and $C6$ represent the user, and the UAV will not leave the area, respectively.

4. Methodology

4.1. Simplification

The solution to a fractional programming problem is challenging. We first utilize the Dinkelbach approach to transform the original problem into an integral programming problem to solve the fractional programming problem. Assuming that ${\eta }^{*}$ is the best possible computational efficiency, the following conditions are both sufficient and necessary for the best possible outcome:

(12)$max\left\{R\left(\mathrm{s}\left(n\right),\mathrm{q}\left(n\right)\right)-{\eta }^{*}E\left(\mathrm{s}\left(n\right),\mathrm{q}\left(n\right)\right)\right\}=0$

Therefore, problem $P$ can be converted into integral problem $P1$ as follows:

(13)$\begin{array}{c}P1:\underset{n,X\left(n\right)}{max}R\left(\mathrm{s}\left(n\right),\mathrm{q}\left(n\right)\right)-\eta E\left(\mathrm{s}\left(n\right),\mathrm{q}\left(n\right)\right)\\ s.t.C1-C6.\end{array}$

where $\eta$ is a non-negative parameter. We define $F\left(\eta \right)=R\left(\mathrm{s}\left(n\right),\mathrm{q}\left(n\right)\right)-\eta E\left(\mathrm{s}\left(n\right),\mathrm{q}\left(n\right)\right)$, which is a strictly monotonic decreasing function of $\eta$. If the optimal computational efficiency ${\eta }^{*}$ is given in advance, there is $F\left(\eta \right)\ge 0$ when $\eta \le {\eta }^{*}$, when $\eta \le {\eta }^{*}$, $F\left(\eta \right)<0$.

To obtain the best computational efficiency, the method first initializes $\eta$ to a small constant, creates a set of gradually increasing $\eta$ values according to the feasible solutions $\mathrm{s}\left(n\right),\mathrm{q}\left(n\right)$ in several iterations, and then updates the $\eta$ values. So, $F\left(\eta \right)$ is approximately 0. The best ${\mathrm{s}}^{*}\left(n\right),{\mathrm{q}}^{*}\left(n\right)$ and ${\eta }^{*}$ can be identified after a predetermined number of iterations.

Although the $P1$ problem is relatively easy to deal with, due to the interaction between the UAV trajectory and other optimization variables, $P1$ is still not convex. This problem still cannot be solved directly. Problem $P1$ is divided into two sub-problems $SP1$ and $SP2$ based on the types of coupling variables to further simplify the non-convex problem. The trajectory scheduling of UAVs can be optimized given user associations, and the problem can be expressed as $SP1$:

(14)$\begin{array}{c}SP1:\underset{q\left(n\right)}{max}{\displaystyle {\displaystyle \sum }_{n=1}^N}{\displaystyle {\displaystyle \sum }_{i=1}^M}{s}_i\left(n\right)W\tau \cdot {\log }_2\left(1+\frac{p_i\left(n\right){\beta }_0}{\left(N_0+w_i\left(n\right)P_{NLOS}\right)\left(h^2+\parallel q\left(n\right)-u_i\parallel {}^2\right)}\right)\\ \mathrm{s}. \mathrm{t}. C1,C3,C4,C6.\end{array}$

In relation to the UAV flight path $q\left(n\right)$, the objective function is non-convex, and the $SP1$ problem is still non-convex. To maximize energy efficiency in the long run and to compensate for Dinkelbach’s shortcomings, we used deep reinforcement learning to solve this subproblem.

The user association in problem $P1$ is an integer planning process for a given UAV’s trajectory.

(15)$\begin{array}{c}SP2:\underset{\mathrm{s}\left(n\right)}{max}{\displaystyle {\displaystyle \sum }_{n=1}^N}{\displaystyle {\displaystyle \sum }_{i=1}^M}{s}_i\left(n\right)W\tau {\log }_2\left(1+\frac{p_i\left(n\right)h_i\left(n\right)}{N_0+w_i\left(n\right)P_{NLOS}}\right)-\eta {\displaystyle {\displaystyle \sum }_{n=1}^N}{\displaystyle {\displaystyle \sum }_{i=1}^M}{s}_i\left(n\right)p_i\left(n\right)\tau \\ \mathrm{s}. \mathrm{t}. C2,C5.\end{array}$

Since continuous variables are completely separated, the $SP2$ problem is a standard integer linear programming problem. To make a quick decision to solve the user association problem, we introduce priority function ${\psi }_i\left(n\right)$ and balance factor $\mathsf{\Theta }=\frac{\alpha }{M+{\varsigma }_i\left(n\right)}$ to achieve offloading fairness.

(16)${\psi }_i\left(n\right)=\frac{\{\left(1-s_i\left(n\right)\right)R_i^l\left(n\right)+s_i\left(n\right)R_i^c)\}}{\left\{\kappa f_i^3\left(n\right)+s_i\left(n\right)p_i\left(n\right)+P_c\right\}\tau } \mathsf{\Theta }$

${\varsigma }_i\left(n\right)$ represents the total number of times that have been offloaded before time $n$. The larger the ${\varsigma }_i\left(n\right)$, the smaller the $\mathsf{\Theta }$, the smaller the priority of the user. $\alpha$ is a coefficient.

4.2. Preliminaries

In reinforcement learning (RL), the agent continuously engages with its surroundings. The agent observes the environmental state $s_n$ in the state space $\mathcal{S}$ for each time slot n and then follows the policy $\pi \left(a_n\mid s_n\right)$ by selecting actions $a_n$ from the action space A, and the environment then changes to the following state $s_{n+1}\in \mathcal{S}$. According to the environment $P\left(s_{n+1}\mid s_n,a_n\right)$, reward function $R\left(s_n,a_n,s_{n+1}\right)$ sends a reward signal $r_n$ to the agent. Until the maximum number of iterations is reached or the agent notices a terminal state, this process keeps going indefinitely. This kind of process is usually expressed as MDP, which defines a quintuple $ℳ=\left(\mathcal{S},\mathcal{A},P,R,\gamma \right)$. The cumulative reward from state $s_n$ to the future is defined as:

(17)$R_n={\displaystyle {\displaystyle \sum }_{\ell =0}^{\infty }}{\gamma }^l{r}_{n+\ell }$

where $\gamma \in \left(0,1\right)$ is called the discount factor. $r$ is the instantaneous reward.

The value function $v_{\pi }\left(s\right)={\mathbb{E}}_{\pi }\left[R_{\mathrm{n}}\mid s_n=s\right]$ is the expectation of the cumulative reward obtained by following the policy $\pi$ in state $s$. To choose the action in accordance with the policy in the state s and obtain the cumulative reward expectations, use the action value function $q_{\pi }\left(s,a\right)={\mathbb{E}}_{\pi }\left[R_{\mathrm{n}}\mid s_n=s,a_{\mathrm{n}}=a\right]$. They represent a good state and a good state–action pair, respectively, and are defined by $v_{\pi }\left(s\right)={\displaystyle \sum }_{a\in A}\pi \left(a\mid s\right)q_{\pi }\left(s,a\right)$ to convert each other. Finding the best policy ${\pi }^{*}$ that maximizes predicted cumulative reward for any state in the state space is the aim of RL, as shown in Formula (18).

(18)$v_{{\pi }^{*}}\left(s\right)=\underset{\pi }{max}{v}_{\pi }\left(s\right)=\underset{a}{max}{q}_{{\pi }^{*}}\left(s,a\right),s\in \mathcal{S}$

To approximate a policy or value function, DRL employs DNN. DNNs are used in value-based DRL techniques to simulate value functions. All strategies can be evaluated, allowing the best strategy to be chosen, if strategy is finite, meaning there are a finite number of states and actions. A value-based DRL method’s main goal is to reduce the discrepancy between the value network and the real value function. In writing, the objective function is:

(19)$L^V\left(\theta \right)={\mathbb{E}}_n{\left[v_{{\pi }^{*}}\left(s_n\right)-v\left(s_n;\theta \right)\right]}^2$

where $v\left(· ;\theta \right)$ is the value network and $\theta$ is its parameter set. $v_{{\pi }^{*}}$ represents the true value. ${\mathbb{E}}_n[ ]$ represents the empirical mean of a finite batch of samples in the optimal way of sampling.

In order to find the best policy, policy-based DRL methods conduct a direct search in the policy space. Comparatively speaking to a method based on a value function, the policy search can directly optimize the strategy without a value function, and the parameterized strategy can handle continuous state and action. It operates by calculating a gradient estimator for policies. The most used gradient estimator is written as Formula (20).

(20)$\nabla L^{PG}\left(\theta \right)={\mathbb{E}}_n\left[{\nabla }_{\theta }\log \pi \left(a_n\mid s_n;\theta \right){\widehat{A}}_n\right]$

where $\pi$ is a random strategy and ${\widehat{A}}_n$ is the estimation function.

Generalized advantage estimation (GAE), which creates an elasticity between variation and bias, is suggested as a solution to the issue of high variance. GAE estimations are calculable using a Formula (21).

(21)${\widehat{A}}_n^{GAE\left(\gamma ,\varphi \right)}={\displaystyle {\displaystyle \sum }_{l=0}^{\infty }}{(\gamma \varphi )}^l{\eta }_{n+l}^v$

where $\varphi$ is a hyperparameter that is used to compromise between variance and bias. ${\eta }_n^v$ is TD error and defined as Formula (22).

(22)${\eta }_n^v=r_n+\gamma v\left(s_{n+1};\omega \right)-v\left(s_n;\omega \right)$

To alleviate the problem of local optimization, it is necessary to introduce off-policy, that is, using different strategies for training and sampling and training methods to improve the exploration ability of policy-based methods in the training process. However, sampling and training under different strategies will lead to unstable training and difficult convergence. Recently, OpenAI proposed the PPO algorithm [22]. Its objective function is as Formula (23).

(23)$L^C\left(\theta \right)={\mathbb{E}}_n\left[\min \left(p_n\left(\theta \right){\widehat{A}}_n,clip\left(p_n\left(\theta \right),1-ϵ,1+ϵ\right){\widehat{A}}_n\right)\right]$

Among them, $p_n\left(\theta \right)$ is the ratio of the probability of the training strategy to the sampling strategy. The clipping function, defined as $clip\left(p_n\left(\theta \right),1-ϵ,1+ϵ\right),$ is used to constrain the value of $p_n\left(\theta \right)$ to prevent the difference between the old and new strategies out of the interval $[1-ϵ,1+ϵ]$. $ϵ$ is a hyperparameter that controls the size of this clipping interval.

4.3. Solution

The framework of DCMCE is shown in Figure 2, including actor network, critic network, environment and replay buffer. The network structure adopts DNN architecture with shared parameters, and the overall objective is to merge the critic network and actor network’s error terms. The overall maximization objective function can be written as Formula (24).

(24)$L^{PPO}\left(\theta \right)={\mathbb{E}}_n\left[L_n^C\left(\theta \right)-c{L}_n^V\left(\theta \right)\right]$

First, we utilize DCMCE to calculate the UAV’s trajectory for time slot t. Since DCMCE is dependent on DRL, let us first describe the three components of DRL: status, action, and reward.

• State;

(25) $s\left(t\right)=\left(E_{\mathrm{b} }\left(t\right),q\left(t\right),u_1\left(t\right)\dots u_M\left(t\right),w_1\left(t\right)\dots w_M\left(t\right)\right)$

$E_{\mathrm{b} }\left(t\right)$ reflects the battery’s remaining power in the time slot $t$, $q\left(t\right)$ represents the UAV’s location information, $u_k\left(t\right)$ represents the position of the k-th user and $w_k\left(t\right)$ shows whether the k-th user’s signal is being obstructed by objects.

• 2.. Action;

(26) $a\left(t\right)=\left(\sigma \left(t\right),v\left(t\right)\right)$

The UAV’s flight angle and flight speed can be precisely optimized in the continuous action space. $\sigma \left(t\right)$ represents the UAV’s flight angle and $v\left(t\right)$ represents the UAV’s flight speed, where $\sigma \left(t\right)\in \left[0, 2\pi \right],v\left(t\right)\in \left[0, v_{max}\right]$.

• 3.. Reward;

(27)$r\left(t\right)=\eta \left(t\right)-\zeta$

where $\eta \left(t\right)$ is the computational efficiency at time $t$. It is obtained through the Formula (10), where $\zeta$ is the penalty obtained by flying out of the active area.

The details of the PPO-based DCMCE algorithm proposed in this paper are given in Algorithm 1. We initialize two DNNs with the same parameters (${\theta }_{\mathrm{old} }\leftarrow \theta$) and ${\pi }_{{\theta }_{\mathrm{old} }}$ for sampling, and ${\pi }_{\theta }$ for optimization. The algorithm alternates between sampling (lines 6 to 10) and optimization (lines 12 to 14). In the sampling phase, the UAV performs action $a_t$ to move to a certain position, and then performs Algorithm 2 to calculate the priority function to obtain the best user association and reach the next state $s_{t+1}$ and calculate the current reward. After repeating the process for $D$ times, trajectories $\left(s_0,a_0,r_0,s_1,\dots ,s_{\mathrm{D}}\right)$ follow the old strategy ${\pi }_{{\theta }_{\mathrm{old} }}$ for sampling. At this stage, GAEs are computed in advance to increase training efficiency. Data from samples are cached for efficiency. The policy’s parameters are changed in $D$ epochs during the optimization phase. The approach uses a stochastic gradient ascent on the cached sampled data, based on the objective function to enhance the strategy once every $D$ time slots. The sample strategy ${\pi }_{{\theta }_{\mathrm{old} }}$ is updated with the current ${\pi }_{\theta }$ and the cached data are removed at the conclusion of the optimization phase. Then, the next iteration begins.

Algorithm 1. DCMCE algorithm
1.	Randomly initialize the parameters $\theta$ and ${\theta }_{old}$
2.	Initialize the collection $ℛ$, sample size $\mathcal{D}$
3.	for$\mathrm{e} =1,2,\dots , {\rm Z}$
4.	Initialize ${\mathrm{S}}_t$
5.	for $t=1,2,3,\dots ,N$
6.	Use $s_t$ as the input of DNN to obtain the $a_t$
7.	Execute action $a_t$, obtain state $s_{t+1}$
8.	Obtain user association through Algorithm 2
9.	Calculate reward $r_t$ through the Formula (27)
10.	Store the transition $\left(s_t,a_t,r_t\right)$ in $ℛ$
11.	if t%$\mathcal{D}$==0 or t ==T
12.	Compute advantage function estimates ${\widehat{A}}_n^{GAE\left(\gamma ,\varphi \right)}$
13.	Update the policy according to the objective function $\theta \leftarrow \arg \underset{\theta }{max}{L}^{PPO}\left(\theta \right)$
14.	Synchronous sampling strategy
15.	end
16.	end
end

After the trajectory of the UAV is determined, we need to obtain the optimal user association to maximize energy efficiency. Algorithm 2 summarizes the details of the association algorithm based on Dinkelbach. First, initialize the computational efficiency ${\eta }^k$ and the number of associated users $Y$ in coverage $R^{max}$, and obtain the current position of the UAV $q\left(n\right)$ from DCMCE. Then, enter the loop, allow the number of user associations $O$ to be the minimum value of the maximum number of associated users $Y$ and the current user request number $I$. The user’s priority is calculated by Equation (16), and the first $O$ users are selected to associate with the UAV to obtain $\mathrm{s}\left(n\right)$. Then, calculate the current computational efficiency ${\eta }^{\prime }$ and use ${\eta }^{\prime }$ to approximate the optimal computational efficiency ${\eta }^{*}$. When $\left|{\eta }^{\prime }-{\eta }^k\right|$ is less than a small enough number $\xi$, the best computational efficiency ${\eta }^{*}$ may be achieved; otherwise, update ${\eta }^k$ until the maximum number of iterations is exceeded.

To analyze complexity, after adequate training, the DCMCE model can be saved in preparation for the test phase. In each time slot, the action of UAV is generated together by actor network. In our paper, as the fully connected hidden layers are applied, and the computational complexity for generating action of UAV is $O({{\displaystyle \sum }}_{l=1}^L{n}_l\cdot n_{l-1})$, where $L$ is the number of network layers and $n_l$ is the number of neurons in the l-th layer. Then, the worst computational complexity of association algorithm is $O\left(KM\right)$. The overall complexity of DCMCE algorithm in the testing process is $O(({{\displaystyle \sum }}_{l=1}^L{n}_l\cdot n_{l-1}+KM)N)$.

Algorithm 2. Association algorithm
1.	Initialize computational efficiency ${\eta }^k$, iteration number $\varkappa =1$, maximum number of iterations $K$
2.	Obtain $q\left(n\right)$ from Algorithm 1
3.	Calculate maximum number of associated users $Y$
4.	repeat
5.	for $i=1,2,3,\dots , Y$
6.	Select the user who has the request to join the set $S$ to obtain the set Length $I$, let $O=\min \left(Y,I\right)$
7.	Calculate the priority of each user by Equation (16) in the set $S$
8.	end
9.	Select the top $O$ users with the highest priority in the set $S$ to obtain $s^k\left(n\right)$ and calculate the current computational efficiency ${\eta }^{\prime }$
10.	if $\left|{\eta }^{\prime }-{\eta }^k\right|⩽\xi$ then
11.	${\eta }^{*}={\eta }^{\prime }$
12.	$s^{*}\left(n\right)=s^k\left(n\right)$
13.	$q^{*}\left(n\right)=q^k\left(n\right)$
14.	break
15.	else
16.	${\eta }^{k+1}=\frac{1}{2}\left({\eta }^{\prime }+{\eta }^k\right)$
17.	end
18.	$\varkappa =\varkappa +1$
until$\varkappa \le K$

5. Performance Evaluation

5.1. Experimental Setup

In the UAV-assisted MEC scenario, algorithms can be deployed to UAV via lightweight neural networks when the infrastructure is overloaded. This reduces the energy consumption of communication within the infrastructure. A total of 20 users are randomly distributed in a two-dimensional region of 100 m × 100 m [18]. In the experimental scenario, the user’s task arrives randomly. The UAV is to fly from the initial position to the user area to provide services for the user, and the user’s computing tasks can be performed from the drone or locally. Assumedly, the UAV is flying at a constant height of 100 m. Table 1 provides a summary of the remaining flying, computation and communication parameters.

We first conducted a series of experiments to determine the optimal values for important hyper-parameters used in algorithm comparisons. Since the algorithm did not change much with $\mathcal{D}$, we set $\mathcal{D}$ to 32. Other parameters were set as follows.

From Figure 3, we can see that when the learning rate of actor network ${\alpha }_a$ is 0.0005 and that of critic network ${\alpha }_c$ is 0.001, the convergence curve fluctuates obviously and converges to a suboptimal value. The reason for this is that a larger learning rate will make both film critic network and actor network have a larger updating pace. When the learning rate of actor network ${\alpha }_a$ is 0.00001 and the learning rate of critic network ${\alpha }_c$ is 0.00002, the lower learning rate will lead to a slower neural network update rate, resulting in slower convergence. Therefore, when the learning rate of actor network ${\alpha }_a$ and the learning rate of critic ${\alpha }_c$ are 0.0001 and 0.0002, respectively, the performance is optimal.

In Figure 4, we compare the effects of different discount factors 𝛾 on the convergence performance of the proposed algorithm. The results show that when the discount factor is 0.9, the performance of the trained algorithm is optimal. Because circumstances vary widely from time to time, data over the entire period are not fully representative of long-term behavior. A larger 𝛾 means that the neural network regards the data collected in the whole period as long-term data, resulting in poor generalization ability in different time periods. Therefore, an appropriate value of 𝛾 will improve the final performance of our trained strategy, and we set the discount factor 𝛾 to 0.9 in the following experiment.

The larger the clipping function factor 𝜖 is, the greater the difference between the two output strategies. As shown in Figure 5, when the clipping function factor 𝜖 is 0.2, both excellent exploration ability and stability are considered.

5.2. Baseline

The simulation results are provided below, and the proposed algorithm is contrasted with three baselines to assess the performance and efficiency of the algorithm.

• Random-offload (RO); some tasks are randomly selected within the UAV communication range to offload.

• Local-offload (LO); all computing tasks are computed locally.

Trust region policy optimization (TRPO): The output of TRPO is continuous action. Here, we output a continuous value for each user according to the method [9]. Like DCMCE, we select the top O users to associate with the UAV.

Table 1

Experimental parameters.

Parameter	Value
$K$	50
L, H, W	100 m
$P_c$	0.1 W
$N$	80
$t_{fly}$	1 s
$B_0$	100 MHz
$P_{NLOS}$	20 dB
$E_b$	500 kJ
$f_i\left(n\right)$	0.1–0.2 GHz
${\theta }^{max}$	$\pi /4$
$M_{\mathrm{UAV}}$	9.65 kg
${\rm Z}$	2500
$v_{\max }$	30 m/s
${\alpha }_0$	−50 dBm
$P_{up,max}$	0.2 W
$\rho$	1000 cycle/bit
$T$	320 s

5.3. Experimental Results

In Figure 6, the optimal UAV trajectory for a cycle is shown, with $M=20$ MDs randomly distributed throughout the target area. Each time slot includes a sample of a UAV’s flight path. We choose some of the key points to stay represented as red stars for a better display of flight conditions. The larger the red star, the longer the UAV stays. The location of the UAV will be suitable for real-time requests. The UAV always flies directly to requests, making the system computationally efficient and spending more time in areas with high user density.

Figure 7 depicts the speed distribution of the UAV in a cycle. The UAV flies faster at the beginning. It may be that the UAV quickly approaches the requested area and spends most of the time providing services for the request area to save energy. When there is no request in the current area, the UAV quickly flies to other request areas to provide services.

As shown in Figure 8, the convergence performance of all algorithms is verified. It can be seen from Figure 8 that the DCMCE in this paper tends to be stable after the first 200 iterations and can achieve relatively good computational efficiency. The convergence rate of TRPO is lower than that of DCMCE, and the convergence results fluctuate greatly. This is because the offloading decision is a discrete action, but TRPO does not handle discrete actions well. Our algorithm processes the two actions separately to achieve better results.

As shown in Figure 9, the average computational efficiency of the LO scheme will fluctuate as the number of users increases, because the average computational efficiency of the LO scheme will change with the computing power of different users. The computational efficiency of the RO scheme is increasing. When the number of users increases, the distribution of users is dense. Although the association of users is blind, the computational efficiency increases. The TRPO algorithm first rises and then falls with the increase of users. The TRPO algorithm performs well when the action–space dimension is low. However, the action–space dimension increases due to the increase in users, and the continuous actions output by the algorithm cannot properly evaluate the user association decision. As an excellent reinforcement learning algorithm, DCMCE has better performance than other algorithms. This is because our scheme can find the optimal user association strategy, and combines the exploration mechanism of reinforcement learning, thereby obtaining the optimal control strategy. With an increase in devices, DCMCE will not show obvious performance degradation.

6. Conclusions

To solve the problem of heavy load on a fixed-base station, we studied a computation offloading problem in a UAV-assisted MEC system in which a flying UAV provides services to MDs. We tended to optimize user associations and the UAV trajectory to maximize the computing efficiency of all MDs. To tackle the computation offloading problem, we propose a DCMCE algorithm based on DRL. Simulation results show that the proposed DCMCE algorithm performs better than the baseline algorithm. We will consider expanding the DCMCE algorithm to multi-UAV scenarios in subsequent work.

Author Contributions

Conceptualization, H.Q. and Z.Z.; methodology, H.Q. and Z.Z.; validation, H.Q. and Z.Z.; formal analysis, H.Q. and Z.Z.; writing—original draft, Z.Z.; writing—review and editing, H.Q. and Z.Z.; visualization, Z.Z. All authors have read and agreed to the published version of the manuscript.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Conflicts of Interest

The authors declare no conflict of interest.

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Figures and Table

Figure 1. The overview of system model.

Figure 2. The structure of DCMCE algorithm.

Figure 3. Convergence performance of the DCMCE algorithm under different learning rates.

Figure 4. Convergence performance with different discount factors.

Figure 5. Convergence performance with different clipping function factors.

Figure 6. The trajectories of the UAV.

Figure 7. The speed of the UAV.

Figure 8. The convergence performance of algorithms.

Figure 9. Computational efficiency of schemes versus MDs.

References

1. Sabella, D.; Sukhomlinov, V.; Trang, L.; Kekki, S.; Acs, B.P. Developing Software for Multi-Access Edge Computing; ETSI: Sophia Antipolis, France, 2019.

2. Ren, T.; Niu, J.; Dai, B.; Liu, X.; Hu, Z.; Xu, M.; Guizani, M. Enabling Efficient Scheduling in Large-Scale UAV-Assisted Mobile-Edge Computing via Hierarchical Reinforcement Learning. IEEE Internet Things; 2021; 9, pp. 7095-7109. [DOI: https://dx.doi.org/10.1109/JIOT.2021.3071531]

3. Gupta, N.; Agarwal, S.; Mishra, D. Trajectory design for throughput maximization in UAV-assisted communication system. IEEE Trans. Green Commun. Netw.; 2021; 5, pp. 1319-1332. [DOI: https://dx.doi.org/10.1109/TGCN.2021.3085867]

4. Wu, Q.; Zhang, R. Common throughput maximization in UAV-enabled OFDMA systems with delay consideration. IEEE Trans. Commun.; 2018; 66, pp. 6614-6627. [DOI: https://dx.doi.org/10.1109/TCOMM.2018.2865922]

5. Zeng, Y.; Xu, J.; Zhang, R. Energy minimization for wireless communication with rotary-wing UAV. IEEE Trans. Wirel. Commun.; 2019; 18, pp. 2329-2345. [DOI: https://dx.doi.org/10.1109/TWC.2019.2902559]

6. Lyu, L.; Zeng, F.Z.; Xiao, Z.; Zhang, C.Y.; Jiang, H.B.; Havyarimana, V. Computation Bits Maximization in UAV-Enabled Mobile-Edge Computing System. IEEE Internet Things; 2022; 9, pp. 10640-10651. [DOI: https://dx.doi.org/10.1109/JIOT.2021.3123429]

7. Wang, L.; Wang, K.; Pan, C.; Xu, W.; Aslam, N.; Nallanathan, A. Deep Reinforcement Learning Based Dynamic Trajectory Control for UAV-assisted Mobile Edge Computing. arXiv; 2019; arXiv: 1911.03887[DOI: https://dx.doi.org/10.1109/TMC.2021.3059691]

8. Wang, Y.P.; Fang, W.W.; Ding, Y.; Xiong, N.X. Computation offloading optimization for UAV-assisted mobile edge computing: A deep deterministic policy gradient approach. Wirel. Netw.; 2021; 27, pp. 2991-3006. [DOI: https://dx.doi.org/10.1007/s11276-021-02632-z]

9. Ho, T.M.; Nguyen, K.-K.; Cheriet, M. UAV control for wireless service provisioning in critical demand areas: A deep reinforcement learning approach. IEEE T Veh. Technol.; 2021; 70, pp. 7138-7152. [DOI: https://dx.doi.org/10.1109/TVT.2021.3088129]

10. Zhang, J.; Zhou, L.; Zhou, F.H.; Seet, B.C.; Zhang, H.J.; Cai, Z.P.; Wei, J.B. Computation-Efficient Offloading and Trajectory Scheduling for Multi-UAV Assisted Mobile Edge Computing. IEEE T Veh. Technol.; 2020; 69, pp. 2114-2125. [DOI: https://dx.doi.org/10.1109/TVT.2019.2960103]

11. Hu, X.; Wong, K.-K.; Yang, K.; Zheng, Z. UAV-assisted relaying and edge computing: Scheduling and trajectory optimization. IEEE Trans. Wirel. Commun.; 2019; 18, pp. 4738-4752. [DOI: https://dx.doi.org/10.1109/TWC.2019.2928539]

12. Ke, H.; Wang, J.; Wang, H.; Ge, Y. Joint optimization of data offloading and resource allocation with renewable energy aware for IoT devices: A deep reinforcement learning approach. IEEE Access; 2019; 7, pp. 179349-179363. [DOI: https://dx.doi.org/10.1109/ACCESS.2019.2959348]

13. Guan, X.; Huang, Y.; Dong, C.; Wu, Q. User association and power allocation for uav-assisted networks: A distributed reinforcement learning approach. China Commun.; 2020; 17, pp. 110-122. [DOI: https://dx.doi.org/10.23919/JCC.2020.12.008]

14. Chen, X.; Zhang, H.; Wu, C.; Mao, S.; Ji, Y.; Bennis, M. Performance optimization in mobile-edge computing via deep reinforcement learning. Proceedings of the 2018 IEEE 88th Vehicular Technology Conference (VTC-Fall); Chicago, IL, USA, 27–30 August 2018; IEEE: Piscataway, NJ, USA, 2018; pp. 1-6.

15. Li, Y.; Qi, F.; Wang, Z.; Yu, X.; Shao, S. Distributed edge computing offloading algorithm based on deep reinforcement learning. IEEE Access; 2020; 8, pp. 85204-85215. [DOI: https://dx.doi.org/10.1109/ACCESS.2020.2991773]

16. Zhang, L.; Zhang, Z.Y.; Min, L.; Tang, C.; Zhang, H.Y.; Wang, Y.H.; Cai, P. Task Offloading and Trajectory Control for UAV-Assisted Mobile Edge Computing Using Deep Reinforcement Learning. IEEE Access; 2021; 9, pp. 53708-53719. [DOI: https://dx.doi.org/10.1109/ACCESS.2021.3070908]

17. Ding, R.J.; Gao, F.F.; Shen, X.M. 3D UAV Trajectory Design and Frequency Band Allocation for Energy-Efficient and Fair Communication: A Deep Reinforcement Learning Approach. IEEE Trans. Wirel. Commun.; 2020; 19, pp. 7796-7809. [DOI: https://dx.doi.org/10.1109/TWC.2020.3016024]

18. Cai, T.; Yang, Z.; Chen, Y.; Chen, W.; Zheng, Z.; Yu, Y.; Dai, H.-N. Cooperative Data Sensing and Computation Offloading in UAV-assisted Crowdsensing with Multi-agent Deep Reinforcement Learning. IEEE Trans. Netw. Sci. Eng.; 2021; 9, pp. 3197-3211. [DOI: https://dx.doi.org/10.1109/TNSE.2021.3121690]

19. Piao, C.; Liu, C.H. Energy-efficient mobile crowdsensing by unmanned vehicles: A sequential deep reinforcement learning approach. IEEE Internet Things; 2019; 7, pp. 6312-6324. [DOI: https://dx.doi.org/10.1109/JIOT.2019.2962545]

20. Jeong, S.; Simeone, O.; Kang, J. Mobile cloud computing with a UAV-mounted cloudlet: Optimal bit allocation for communication and computation. IET Commun.; 2017; 11, pp. 969-974. [DOI: https://dx.doi.org/10.1049/iet-com.2016.1114]

21. Zhou, F.; Wu, Y.; Hu, R.Q.; Qian, Y. Computation Rate Maximization in UAV-Enabled Wireless-Powered Mobile-Edge Computing Systems. IEEE J. Sel. Areas Commun.; 2018; 36, pp. 1927-1941. [DOI: https://dx.doi.org/10.1109/JSAC.2018.2864426]

22. Schulman, J.; Wolski, F.; Dhariwal, P.; Radford, A.; Klimov, O. Proximal Policy Optimization Algorithms. arXiv; 2017; arXiv: 1707.06347