# Tradeoff of Computation Bits and Computing Speed in an Edge Computing System for Sensor Networks

Authors: Jiaying Huang; Yawen Shi; Fahui Wu
Journal: Journal of Sensors
 (2021)

---

## Abstract

Unmanned aerial vehicle (UAV) enabled mobile-edge computing (MEC) has been recognized as a promising approach for providing enhanced coverage and computation capability to Internet of Things (IoT), especially in the scenario with limited or without infrastructure. In this paper, we consider the UAV assisted partial computation offloading mode MEC system, where ground sensor users are served by a moving UAV equipped with computing server. Computation bits (CB) and computation efficiency (CE) are two vital metrics describe the computation performance of system. To reveal the CB-CE tradeoff, an optimization problem is formulated to maximize the weighted sum of the above two metrics, by optimizing the UAV trajectory jointly with communication resource, as well as the computation resource. As the formulated problem is non-convex, it is difficult to be optimally solved in general. To tackle this issue, we decouple it into two sub-problems: UAV trajectory optimization and resource allocation optimization. We propose an iterative algorithm to solve the two sub-problems by Dinkelbach’s method, Lagrange duality and successive convex approximation technique. Extensive simulation results demonstrate that our proposed resource allocation optimization scheme can achieve better computational performance than the other schemes. Moreover, the proposed alternative algorithm can converge with a few iterations.


---

## Body

## 1. Introduction

With the increasing popularity of computer terminals and the emergence of new applications (e.g. online games, face recognition, smart home, etc.), mobile data traffic continues to grow at a high speed, and users’ demands for computing power and quality of experience (QoE) are also increasing [1]. However, the limited battery lifetime and low computing capacity make it difficult for mobile terminal to provide good QoE [2].The computing offloading technology under the mobile cloud computing (MCC) architecture was first proposed to solve the above challenge, but the network bandwidth pressure and transmission delay problem make MCC unable to meet the application requirements well [2]. Therefore, mobile edge computing (MEC) has received widely attention as an advanced technology that can overcome these challenges [3]. The MEC serves are at the edge of the wireless sensor network, providing communication, computing, storage and other services to a large number of end users who are tightly deployed [2]. MEC enables rapid data analysis and processing, reduces the possibility of latency, and ensures high security [2]. However, terrestrial MEC systems have limitations in application scenario, such as infrastructures are destroyed due to natural disasters [4–6].Unmanned aerial vehicles (UAV) can tackle this challenge due to the flexibility and controllability, they can be flexibly deployed in most scenarios, especially in the scenario with limited or without infrastructure. Moreover, the UAV-enabled MEC system has more reliable line-of sight (LoS) communication links thus improve the performance of computation tasks offloading and computation results downloading, significantly improved the computation performance eventually [7–9]. Furthermore, the trajectory of the UAV can be optimized to further improve the user computation performance [10–17].For the above reasons, this paper considers an UAV-enabled MEC system. In order to achieve a good tradeoff between computation bits and computation efficiency of all sensor users, a resource allocation scheme with jointly optimized computation performance and UAV’s trajectory is proposed under partial computation offloading mode.


### 1.1. Related Work and Motivation

Resource allocation is one of the gordian technologies in mobile edge computing networks, MEC systems need to continuously optimize resource allocation algorithms to improve the computation performance. At present, there are a lot of researches on resource allocation in the conventional MEC networks [18–23]. Jian et al. [18] proposed a profit maximization problem based on the task-aware cloud radio access network with MEC system, which jointly optimizing offloading tactics, radio and computational resources allocation. In order to minimize the energy computation of the overall user, when multiple mobile users request for computation offloading to a public cloud server, Sardellitti et al. [19] defined the offloading problem specifically as the transmit precoding matrices of the multiple mobile users and the CPU cycles/second assigned by the cloud to each mobile user, thus proposing an optimization scheme for computing and radio resources. In order to provide high quality of experience, the issues about content caching strategies and computation offloading in wireless cellular network with MEC were considered, specifically, Wang et al. [20] designed the resource allocation scheme under the premise of considering the total network revenue, while the goal of Zhang et al. [21] is minimize the total delay computation during the computation process. Consider there is a delay of user’s task completion, in order to avoid serious delay, Ding et al. [22] formulated a power and time allocation joint optimization scheme to decrease the energy consumption when performing computation offloading task in a NOMA-assisted MEC network. Du et al. [23] studied computation, communication and bandwidth allocation problem in a mixed fog/cloud system by considering computation resource allocation or offloading decision making while considering user fairness and tolerable delay.In order to tackle the problem of achieving good communication and computation performance in complex environments, the resource allocation problems in UAV-enabled MEC networks have been studied [10, 11]. The authors of [10] first proposed a UAV-enabled MEC network and demonstrated that UAV can improve system’s computing performance due to the LoS link and trajectory optimization, a testbed was developed for performance validation and results demonstrated that the UAV-enabled MEC reducing the processing time of recognition. In order to improve the computing performance, considering an UAV user is served by cellular ground base stations (GBSs) for computation offloading, Cao et al. [11] formulated an effective scheme that optimizes the computation offloading schedule and adjusts the trajectory to minimize the time for the UAV to complete the mission. Xiong et al. [12] studied a resource allocation scheme to minimize the sum of the maximum delay of multiple ground users in MEC system, a Block coordinate descent (BCD) based optimization algorithm was proposed to alternatively optimize the offloading decisions, bit allocations and the UAV trajectory in each iteration. Hu et al. [13] and Jeong et al. [14] proposed a resource allocation program to minimize the consumed overall energy of the system, the problem of jointly offloading and trajectory design in [13] with energy budget constraints was addressed by leveraging penalty dual decomposition-based algorithm, and the problem of jointly optimizing the bit allocation and path plan under energy consumption constraints was solved by leveraging successive convex approximation (SCA) strategies. Furthermore, Messous et al. [15] considered the tradeoff between execution time and energy consumption, a game theory model was adopted to minimize the cost function combination of energy overhead and delay. Zhou et al. [16] and Zhang et al. [17] designed resource allocation scheme by jointly optimizing the UAV’s trajectory, the CPU frequencies, the offloading times and transmit powers of user to maximize the computation bits and computation efficiency, respectively.Although a lot of literatures has been studied the resource optimization problems in the MEC networks, and UAV-enabled MEC system, none of the above works considered the tradeoff between computation bits and computation efficiency. Computation bits maximization aims to maximize the number of total computation bits by offloading and local computing. It can directly reflect the computation performance of UAV-enabled MEC system. However, the computation bits maximization overemphasizes the importance of computation bits, may lead to excessive energy usage. The computation efficiency maximization overemphasizes the importance of efficiency, the computation bits may too small to meet the computation requirement. In a word, consider only one metric maximization may fall into the trap of local (or partial) performance optimum. Thus, we study a tradeoff problem between computation bits and computation efficiency by jointly optimizing the UAV trajectory, the CPU frequencies, the offloading times and transmit powers of user in the UAV-based MEC system under the partial computation offloading mode. From the above discussion, this is the first study of considering the tradeoff between computation bits and computation efficiency in the UAV-enabled MEC system.


### 1.2. Contributions and Organization

An UAV-assisted MEC network is considered in the paper, where multiple ground sensor users receive energy and computation services from the UAV. In the system, each sensor user has an on-chip computing microprocessor that can perform simple computation tasks, and the UAV is equipped with a power computing processor that can execute computationally heavy tasks [11–15]. Even if the flight time is affected by battery capacity, which limits computing performance, it is promising due of the LoS links of UAV-to-ground communication channel [7]. The objective of this paper is to reveal and achieve a good tradeoff between the total computation bits and the computation efficiency of all users under partial computation offloading mode. Hence, our main contributions are summarized as follows:
(i)
The resource optimization scheme is formulated in an UAV-enabled MEC system under partial computation offloading mode. The tradeoff problem between computation bits and computation efficiency of users is formulated by jointly the CPU frequency, the offloading times, the transmit powers of users and the trajectory of UAV, subject to the time constraint, the maximum consumed energy constraint, the initial and final horizontal location constraints, and the speed constraint of the UAV.(ii)
We transform the challenging primal non-convex problem into a form that is easier to solve by decomposing it into two subproblems. Thus, a two-stage alternative optimization method is proposed to address the formulated original problem. With the UAV’s trajectory fixed, the closed-form expressions for the optimal CPU frequencies, the offloading times and the transmit powers of users can be derived by the Lagrangian dual method. And the SCA method is used to optimize the trajectory of the UAV.(iii)
The simulation results demonstrate that the proposed resource allocation optimization scheme has better computational performance than the disjoint scheme. Moreover, it is seen that the convergence speed of the alternative algorithm is good, and it can converge after a few iterations.The structure of the paper is as follows. The system model is introduced in Section2. Section 3 formulates the resource allocation optimization problem under partial computation offloading and decomposed into two subproblems that are easy to solve. Section 4 presents the simulation results. Finally, Section 5 concludes this paper.


## 1.1. Related Work and Motivation

Resource allocation is one of the gordian technologies in mobile edge computing networks, MEC systems need to continuously optimize resource allocation algorithms to improve the computation performance. At present, there are a lot of researches on resource allocation in the conventional MEC networks [18–23]. Jian et al. [18] proposed a profit maximization problem based on the task-aware cloud radio access network with MEC system, which jointly optimizing offloading tactics, radio and computational resources allocation. In order to minimize the energy computation of the overall user, when multiple mobile users request for computation offloading to a public cloud server, Sardellitti et al. [19] defined the offloading problem specifically as the transmit precoding matrices of the multiple mobile users and the CPU cycles/second assigned by the cloud to each mobile user, thus proposing an optimization scheme for computing and radio resources. In order to provide high quality of experience, the issues about content caching strategies and computation offloading in wireless cellular network with MEC were considered, specifically, Wang et al. [20] designed the resource allocation scheme under the premise of considering the total network revenue, while the goal of Zhang et al. [21] is minimize the total delay computation during the computation process. Consider there is a delay of user’s task completion, in order to avoid serious delay, Ding et al. [22] formulated a power and time allocation joint optimization scheme to decrease the energy consumption when performing computation offloading task in a NOMA-assisted MEC network. Du et al. [23] studied computation, communication and bandwidth allocation problem in a mixed fog/cloud system by considering computation resource allocation or offloading decision making while considering user fairness and tolerable delay.In order to tackle the problem of achieving good communication and computation performance in complex environments, the resource allocation problems in UAV-enabled MEC networks have been studied [10, 11]. The authors of [10] first proposed a UAV-enabled MEC network and demonstrated that UAV can improve system’s computing performance due to the LoS link and trajectory optimization, a testbed was developed for performance validation and results demonstrated that the UAV-enabled MEC reducing the processing time of recognition. In order to improve the computing performance, considering an UAV user is served by cellular ground base stations (GBSs) for computation offloading, Cao et al. [11] formulated an effective scheme that optimizes the computation offloading schedule and adjusts the trajectory to minimize the time for the UAV to complete the mission. Xiong et al. [12] studied a resource allocation scheme to minimize the sum of the maximum delay of multiple ground users in MEC system, a Block coordinate descent (BCD) based optimization algorithm was proposed to alternatively optimize the offloading decisions, bit allocations and the UAV trajectory in each iteration. Hu et al. [13] and Jeong et al. [14] proposed a resource allocation program to minimize the consumed overall energy of the system, the problem of jointly offloading and trajectory design in [13] with energy budget constraints was addressed by leveraging penalty dual decomposition-based algorithm, and the problem of jointly optimizing the bit allocation and path plan under energy consumption constraints was solved by leveraging successive convex approximation (SCA) strategies. Furthermore, Messous et al. [15] considered the tradeoff between execution time and energy consumption, a game theory model was adopted to minimize the cost function combination of energy overhead and delay. Zhou et al. [16] and Zhang et al. [17] designed resource allocation scheme by jointly optimizing the UAV’s trajectory, the CPU frequencies, the offloading times and transmit powers of user to maximize the computation bits and computation efficiency, respectively.Although a lot of literatures has been studied the resource optimization problems in the MEC networks, and UAV-enabled MEC system, none of the above works considered the tradeoff between computation bits and computation efficiency. Computation bits maximization aims to maximize the number of total computation bits by offloading and local computing. It can directly reflect the computation performance of UAV-enabled MEC system. However, the computation bits maximization overemphasizes the importance of computation bits, may lead to excessive energy usage. The computation efficiency maximization overemphasizes the importance of efficiency, the computation bits may too small to meet the computation requirement. In a word, consider only one metric maximization may fall into the trap of local (or partial) performance optimum. Thus, we study a tradeoff problem between computation bits and computation efficiency by jointly optimizing the UAV trajectory, the CPU frequencies, the offloading times and transmit powers of user in the UAV-based MEC system under the partial computation offloading mode. From the above discussion, this is the first study of considering the tradeoff between computation bits and computation efficiency in the UAV-enabled MEC system.


## 1.2. Contributions and Organization

An UAV-assisted MEC network is considered in the paper, where multiple ground sensor users receive energy and computation services from the UAV. In the system, each sensor user has an on-chip computing microprocessor that can perform simple computation tasks, and the UAV is equipped with a power computing processor that can execute computationally heavy tasks [11–15]. Even if the flight time is affected by battery capacity, which limits computing performance, it is promising due of the LoS links of UAV-to-ground communication channel [7]. The objective of this paper is to reveal and achieve a good tradeoff between the total computation bits and the computation efficiency of all users under partial computation offloading mode. Hence, our main contributions are summarized as follows:
(i)
The resource optimization scheme is formulated in an UAV-enabled MEC system under partial computation offloading mode. The tradeoff problem between computation bits and computation efficiency of users is formulated by jointly the CPU frequency, the offloading times, the transmit powers of users and the trajectory of UAV, subject to the time constraint, the maximum consumed energy constraint, the initial and final horizontal location constraints, and the speed constraint of the UAV.(ii)
We transform the challenging primal non-convex problem into a form that is easier to solve by decomposing it into two subproblems. Thus, a two-stage alternative optimization method is proposed to address the formulated original problem. With the UAV’s trajectory fixed, the closed-form expressions for the optimal CPU frequencies, the offloading times and the transmit powers of users can be derived by the Lagrangian dual method. And the SCA method is used to optimize the trajectory of the UAV.(iii)
The simulation results demonstrate that the proposed resource allocation optimization scheme has better computational performance than the disjoint scheme. Moreover, it is seen that the convergence speed of the alternative algorithm is good, and it can converge after a few iterations.The structure of the paper is as follows. The system model is introduced in Section2. Section 3 formulates the resource allocation optimization problem under partial computation offloading and decomposed into two subproblems that are easy to solve. Section 4 presents the simulation results. Finally, Section 5 concludes this paper.


## 2. System Model

Consider a UAV-assisted MEC system as shown in Figure1, where a UAV equipped with an MEC server to provide the computation capability for the ground sensors. The UAV is dispatched to fly from an appointed initial location to a final location. There are M sensor users fixed on the ground, denoted by M≜1,2,⋯,M. Each user offloads a portion of its computing tasks to the UAV and carries out the rest locally. Without loss of generality, a three-dimensional (3D) Euclidean coordinate is adopted, where the horizon coordinate of ground user m is denoted by qm=xm,ym,m∈M. It is assumed that the ground users’ locations can be detected by the UAV to facilitate the trajectory design [7–9]. Suppose that the UAV flies at altitude HH>0 from the ground remains unchanged during a given flight period, H is the minimum height that can avoid obstacles on the ground and ensure normal communication.Figure 1
The system model.


### 2.1. System Model

The period time for the UAV flight is expressed byT. For convenience, the time duration T is divided into N time slots with equal length, which are expressed by a set N≜1,2,⋯,NN. And then, the horizontal plane coordinate of UAV over time slot n can be characterized by the discrete time locations qun=xun,yun,0≤n≤N. Hence, the distance between the ground user m∈M and UAV in each time slot n∈N can be denoted by dmn=H2+qun−qm2, where ⋅denotes the Euclidean norm. The number of N should be large enough to ensure that the position of the UAV in each time slot (or the distance between the UAV and ground users) can be regarded as constant. Particularly, the UAV’s initial and final horizontal positions are assumed to be determined before flight, which denoted as q0 and qF, respectively. Thus, we have the UAV’s location and speed constraints:
(1a)qu1=q0(1b)quN+1=qF(1c)qun+1−qUn≤1NVmax,n∈Nwhere Vmax is the maximum flying speed of the UAV. We consider block fading channel in this paper i.e., during each T, the channel remains static. Similar to [24–26], it is assumed that the wireless channel between the UAV and ground users is dominated by line of sight (LoS) link, hence the channels between the UAV and ground users are modelled by the free space path loss model. Thus, the channel power gain between the UAV and the mth user is denoted by hmn, given as:
(2)hmn=β0dm−2n=β0H2+qun−qm2,m∈M,n∈Nwhere β0 is the channel power gain at a reference distance d0=1m.


### 2.2. Local Computation and Computation Offloading

In this paper, the partial computation offloading mode is adopted, the computing task of each user consists of local computing and computation offloading to the UAV. Each user can simultaneously perform the two tasks. Similar to the works in [27–29], let C denote the number of CPU cycles required to process one bit of date at each user and fmn denote the CPU frequencies of the mth user at the nth slot. Thus, the total computation bits and the total consumed energy of the mth user when performing the local computing task during n slots are, respectively, denoted as:
(3)Rlocal=∑k=1nTfmkNC,m∈M,n∈N(4)Elocal=TN∑k=1nγcfm3k,m∈M,n∈Nwhere γc denote the effective capacitance coefficient of the processor’s chip at the mth user. Furthermore, each user’s chip architecture determines γc. In the computation offloading part, as shown in Figure 2, a time-division multiple access (TDMA) protocol is applied. The computation process of mth user in each time slot can be divided into three stages: offloading, computation and downloading phase. In the offloading phase, M users execute their computation offloading task one after another during each slot. The UAV performs computing tasks and sends results to the user after all users have completed their computation offloading tasks at the nth slot. Similar to [16, 17], compare with the ground user, the UAV has a strong computation capability, thus, the computation time is much less than that of ground users. Moreover, the number of the bits related to the computation result is very small. Thus computation time and the downloading time of the UAV are neglected.Figure 2
Computation offloading from user to the UAV.According to the works in [28], the total number of bits that the 𝑚th user offloads to the UAV at the nth slot is given by:
(5)BTtmnvmNlog21+hmnPmnσ02,m∈M,n∈Nwhere B represents communication bandwidth; Pmn denotes the transmit power of the mth user at the nth slot; σ02 is noise power of the mth user; Ttmn/N,0≤tmn≤1 denotes the lasting time for the mth user offloads the computation tasks to the UAV at the nth time slot and vm denotes the redundant data in communication.Moreover, the sum of the total offloading time of all users should not be greater than the duration of one time slot, thus:(6)∑m=1Mtmn≤1,m∈M,n∈NWe apply the energy available constraint to each ground userm so that the energy consumed for local computing and task offloading cannot exceed a threshold, denoted by Γm,m∈M. Thus, we have:
(7)TN∑k=1nγcfm3k+tmkPmk≤Γm,m∈M,n∈NUnder the partial computation offloading mode, the total computation bitsCBm of the mth user is expressed as:
(8)CBm=∑n=1NTfmnNC+BTtmnvmNlog21+hmnPmnσ02,m∈M.The total energy consumption of themth user is given as:
(9)Em=TN∑n=1Nγcfm3n+tmkpmn,m∈MTherefore, the computation efficiency of themth user can be expressed as:
(10)CEm=CBmEm=∑n=1NTfmn/NC+BTtmn/νmNlog21+hmnPmn/σ02T/N∑n=1Nγcfm3n+tmnpmn,m∈M


## 2.1. System Model

The period time for the UAV flight is expressed byT. For convenience, the time duration T is divided into N time slots with equal length, which are expressed by a set N≜1,2,⋯,NN. And then, the horizontal plane coordinate of UAV over time slot n can be characterized by the discrete time locations qun=xun,yun,0≤n≤N. Hence, the distance between the ground user m∈M and UAV in each time slot n∈N can be denoted by dmn=H2+qun−qm2, where ⋅denotes the Euclidean norm. The number of N should be large enough to ensure that the position of the UAV in each time slot (or the distance between the UAV and ground users) can be regarded as constant. Particularly, the UAV’s initial and final horizontal positions are assumed to be determined before flight, which denoted as q0 and qF, respectively. Thus, we have the UAV’s location and speed constraints:
(1a)qu1=q0(1b)quN+1=qF(1c)qun+1−qUn≤1NVmax,n∈Nwhere Vmax is the maximum flying speed of the UAV. We consider block fading channel in this paper i.e., during each T, the channel remains static. Similar to [24–26], it is assumed that the wireless channel between the UAV and ground users is dominated by line of sight (LoS) link, hence the channels between the UAV and ground users are modelled by the free space path loss model. Thus, the channel power gain between the UAV and the mth user is denoted by hmn, given as:
(2)hmn=β0dm−2n=β0H2+qun−qm2,m∈M,n∈Nwhere β0 is the channel power gain at a reference distance d0=1m.


## 2.2. Local Computation and Computation Offloading

In this paper, the partial computation offloading mode is adopted, the computing task of each user consists of local computing and computation offloading to the UAV. Each user can simultaneously perform the two tasks. Similar to the works in [27–29], let C denote the number of CPU cycles required to process one bit of date at each user and fmn denote the CPU frequencies of the mth user at the nth slot. Thus, the total computation bits and the total consumed energy of the mth user when performing the local computing task during n slots are, respectively, denoted as:
(3)Rlocal=∑k=1nTfmkNC,m∈M,n∈N(4)Elocal=TN∑k=1nγcfm3k,m∈M,n∈Nwhere γc denote the effective capacitance coefficient of the processor’s chip at the mth user. Furthermore, each user’s chip architecture determines γc. In the computation offloading part, as shown in Figure 2, a time-division multiple access (TDMA) protocol is applied. The computation process of mth user in each time slot can be divided into three stages: offloading, computation and downloading phase. In the offloading phase, M users execute their computation offloading task one after another during each slot. The UAV performs computing tasks and sends results to the user after all users have completed their computation offloading tasks at the nth slot. Similar to [16, 17], compare with the ground user, the UAV has a strong computation capability, thus, the computation time is much less than that of ground users. Moreover, the number of the bits related to the computation result is very small. Thus computation time and the downloading time of the UAV are neglected.Figure 2
Computation offloading from user to the UAV.According to the works in [28], the total number of bits that the 𝑚th user offloads to the UAV at the nth slot is given by:
(5)BTtmnvmNlog21+hmnPmnσ02,m∈M,n∈Nwhere B represents communication bandwidth; Pmn denotes the transmit power of the mth user at the nth slot; σ02 is noise power of the mth user; Ttmn/N,0≤tmn≤1 denotes the lasting time for the mth user offloads the computation tasks to the UAV at the nth time slot and vm denotes the redundant data in communication.Moreover, the sum of the total offloading time of all users should not be greater than the duration of one time slot, thus:(6)∑m=1Mtmn≤1,m∈M,n∈NWe apply the energy available constraint to each ground userm so that the energy consumed for local computing and task offloading cannot exceed a threshold, denoted by Γm,m∈M. Thus, we have:
(7)TN∑k=1nγcfm3k+tmkPmk≤Γm,m∈M,n∈NUnder the partial computation offloading mode, the total computation bitsCBm of the mth user is expressed as:
(8)CBm=∑n=1NTfmnNC+BTtmnvmNlog21+hmnPmnσ02,m∈M.The total energy consumption of themth user is given as:
(9)Em=TN∑n=1Nγcfm3n+tmkpmn,m∈MTherefore, the computation efficiency of themth user can be expressed as:
(10)CEm=CBmEm=∑n=1NTfmn/NC+BTtmn/νmNlog21+hmnPmn/σ02T/N∑n=1Nγcfm3n+tmnpmn,m∈M


## 3. Resource Optimization in UAV-Enabled MEC System

Our objective is to characterize the total computation bits CB and the computation efficiency CE tradeoff in the UAV-enabled MEC system under the partial computation offloading mode, by jointly optimizing CPU frequenciesfmn, offloading times tmn, the UAV trajectory qun and the transmit power allocation pmn, subject to the initial and final horizontal location constraints and the speed constraint of the UAV in (1), the time constraint in (6), and the maximum consumed energy constraint in (7). Consequently, the resource and trajectory jointly optimization problem is formulated as:
(11)P1:maxfmn,pmn,qun,tmnρ∑m=1MCBm+1−ρ∑m=1MCEms.t.C1:fmn≥0,pmn≥0,m∈M,n∈N1,6,and7where the constant ρ is a weight coefficient, and its value range is 0,1. In the special case, when ρ=1, the above general problem becomes computation bits maximization problem, when ρ=0, P1 is equivalent to the computation efficiency maximization problem.It is easy to observe that P1 is non-convex problem since the presence of the non-linear couplings among the optimization variables, and the objective function is non-concave with respect to the trajectory of the UAV. An alternative two-stage algorithm is designed to address P1, the details are as follows.


### 3.1. Optimizing Transmit Power, Offloading Times and CPU Frequencies

For a given trajectory, P1 can be re-expressed as:(12)P2:maxfmn,Pmn,tmnρ∑m=1MCBm+1−ρ∑m=1MCEms.t.C1,6,and7.Since the objective function is a fractional form, P2 is still nonconvex. To obtain a tractable solution, a parameter problem based on the Dinkelbach’s method is exploited to tackle the objective function [30]. Thus, P2 can be solved by iteratively solving P3, given by:
(13)P3:maxfmn,Pmn,tmnρ∑m=1MCBm−1−ρηTNγcfm3n+Zm+1−ρ∑m=1MTfmnNC+BTtmvmNlog21+hmnZmtmσ02s.t.C1,and6.where Zmn=Pmntmn, and η is a non-negative parameter. It is seen that P3 is a convex problem and can be solved by using Lagrange duality method [31]. The Lagrangian of P3 can be given by:
(14)LΞ=∑m=1M∑n=1NTfmnNC+BTtmnνmNlog21+hmnZmntmnσ02−1−ρηTNγcfm3n+Zmn−∑m=1M∑n=1Nλm,nTNγcfm3n+Zmn−Γ+∑n=1Nμn1−∑m=1MtmnIn equation (14), λm,n,m∈M,n∈N and μn>0,n∈N are the dual variables associated with the constraint in C1 and (6), respectively, and Ξ represents a collection of all optimization and dual variables. Let θm,n=∑k=nNλm,k and gmk=γcfm3k+Zmk−Γm, then, the Lagrangian function can be rewritten as:
(15)LΞ=∑m−1M∑n=1NTfmnNC+BTtmnνmNlog21+hmnZmntmnσ01/n−1−ρηNTγcfm3n+Zmn−∑m=1M∑n=1NTNθm,ngmk+∑n=1Nμn1−∑m=1MtmnThus, the Lagrangian dual function expression of P3 is written as:
(16)φλm,n,μn=max0≤fmnLΞAccording to equation (16), the optimal solutions of P3 can be obtained by solving its dual problem, given as:
(17)minλ,n,μnφλm,n,μnGiven dual variables, (17) can be decomposed into 𝑀 parallel sub-problems, given as:
(18)Lmλm,n,μn,tmn,Zmn,fmn=∑n=1NTfmnNC+BTtmnvmNlog21+hmnZmntmnσ02−∑n=1N1−ρηTNγcfm3n+Zmn−∑n=1NTNθm,ngmn+∑n=1NμnM−μntmnTherefore, let us take the derivative of (18) with respect to fmn and Zmn, respectively, the optimal CPU frequency fmoptn and transmit power of users pmoptn can be obtained, and their expressions are:
(19)fmoptn=13Cγc1−ρη+∑k=nNλm,kpmoptn=0,tmn=0,Bvmln21−ρη+∑k=nNλm,k−σ02hmn+,tmn>0,where x+=maxx,0 and maxx,0 denotes the bigger value of x and 0.And similar to the above, the optimal offloading time can also be obtained by deriving the following formula for a given trajectoryqun:
(20)log21+hmnZmntmnσ02−hmnZmnln2tmnσ02+hmnZmn−μnNvnBT=0We can handle the (20) by applying the bisection method. Finally, the dual variables can be obtained by using subgradient method [30]. According to [30], the subgradient ensures convergence to the optimal values within a small margin of error.


### 3.2. Optimizing UAV Trajectory

For any given CPU frequencies, transmit power, offloading times of users, we can express the sub-problem about trajectory optimization as:(21)P4:maxqunρ∑m=1M∑n=1NBTtmnvmNlog21+Pmnβ0σ02H2+qun−qm2+1−ρ∑m=1M∑n=1NBtmnlog21+Pmnβ0/σ02H2+qun−qm2vmγcfm3n+tmnpmns.t.1a,1b,and1c.Due to the objective function is non-concave with respect toqun, and we can use SCA technology to handle the non-convex problem of P4. The obtained solution can be guaranteed to satisfy the Karush-Kuhn-Tucker (KKT) conditions of P4 [32]. Thus, the global underestimation can be obtained by using the first-order Taylor expansion method.For any local trajectoryqujn,n∈N at the jth iteration, we have:
(22)log21+β0Pmnσ02H2+qun−qm2≥ymjqunwhere:
(23)ymjqun=log21+Pmnβ0σ02H2+qujn−qm2−Pmnβ0log2equn2−qujn2σ02H2+Pmnβ0+σ02qujn2qujn2+H2where the equality holds when qun=qujn.By replacing the objective function of P4 with (22), the problem (21) is approximately transformed to:
(24)P5:maxqunρ∑m=1M∑n=1NBTtmnvmNymjqun+1−ρ∑m=1M∑n=1NBtmnymjqunvmγcfm3n+tmnPmn,s.t.1a,1b,and1c.It is seen that P5 is convex and can be easily solved by using convex optimization tools such as CVX [32]. By solving P3 and P5, the two sub-problems alternate in an iterative manner. The specific process of the proposed algorithm is summarized in Table 1.Table 1
Two-stage alternative optimization algorithm.
Algorithm 1. The alternative optimization algorithm for P1.1:SettingΓ, T, N, Vmax, q0,qF, and the tolerance errors ξ, ξ1, inputting ρ;2:Initialization:The iterative indexi=1, λm,ni, μni andquin;3:Repeat 1Calculatefopt,in and popt,in by solving problem P3 for given quin;Obtaintopt,i using the bisection method to solve (20);Update λm,ni and μni using the sub gradient algorithm;Initialize the iterative numberj=1;Repeat 2  Solve P5 by using CVX for the given fopt,in, popt,in and topt,i;Updatej=j+1, and quin;If∑n=1Nqujn−quj−1n≤ξquin=qujn;Break;EndEnd repeat 2Update the iterative indexi=i+1;Ifmaxn∈N∑i−∑i−1≤ξ1 where ∑i=ρCBm+1−ρCEmBreak;EndEnd repeat 14: Obtain solutionsHere, we give the complexity analysis for the proposed Algorithm 1. It consists of solving resource allocation and optimizing UAV trajectory with CVX. LetL1 and L2 denote the number of iterations required for the Repeat 1 and Repeat 2 of Algorithm 1, respectively. The computation complexity of Repeat 2 isOL2N3. For Repeat 1, the first aspect is calculate fopt,in and popt,in, the computation complexity is OL12MN; the computation complexity of bisection method for obtaining the tOpt,i is OL1Mlog2l1/T,where l1 denotes the tolerance error for bisection method. The computation complexity of computing the dual variables is OL1/l22, where l2 denotes the tolerance error for the subgradient method. Thus, the total complexity of Algorithm 1 is OL12MN+Mlog2l1/T+1/l22+L2N3.


## 3.1. Optimizing Transmit Power, Offloading Times and CPU Frequencies

For a given trajectory, P1 can be re-expressed as:(12)P2:maxfmn,Pmn,tmnρ∑m=1MCBm+1−ρ∑m=1MCEms.t.C1,6,and7.Since the objective function is a fractional form, P2 is still nonconvex. To obtain a tractable solution, a parameter problem based on the Dinkelbach’s method is exploited to tackle the objective function [30]. Thus, P2 can be solved by iteratively solving P3, given by:
(13)P3:maxfmn,Pmn,tmnρ∑m=1MCBm−1−ρηTNγcfm3n+Zm+1−ρ∑m=1MTfmnNC+BTtmvmNlog21+hmnZmtmσ02s.t.C1,and6.where Zmn=Pmntmn, and η is a non-negative parameter. It is seen that P3 is a convex problem and can be solved by using Lagrange duality method [31]. The Lagrangian of P3 can be given by:
(14)LΞ=∑m=1M∑n=1NTfmnNC+BTtmnνmNlog21+hmnZmntmnσ02−1−ρηTNγcfm3n+Zmn−∑m=1M∑n=1Nλm,nTNγcfm3n+Zmn−Γ+∑n=1Nμn1−∑m=1MtmnIn equation (14), λm,n,m∈M,n∈N and μn>0,n∈N are the dual variables associated with the constraint in C1 and (6), respectively, and Ξ represents a collection of all optimization and dual variables. Let θm,n=∑k=nNλm,k and gmk=γcfm3k+Zmk−Γm, then, the Lagrangian function can be rewritten as:
(15)LΞ=∑m−1M∑n=1NTfmnNC+BTtmnνmNlog21+hmnZmntmnσ01/n−1−ρηNTγcfm3n+Zmn−∑m=1M∑n=1NTNθm,ngmk+∑n=1Nμn1−∑m=1MtmnThus, the Lagrangian dual function expression of P3 is written as:
(16)φλm,n,μn=max0≤fmnLΞAccording to equation (16), the optimal solutions of P3 can be obtained by solving its dual problem, given as:
(17)minλ,n,μnφλm,n,μnGiven dual variables, (17) can be decomposed into 𝑀 parallel sub-problems, given as:
(18)Lmλm,n,μn,tmn,Zmn,fmn=∑n=1NTfmnNC+BTtmnvmNlog21+hmnZmntmnσ02−∑n=1N1−ρηTNγcfm3n+Zmn−∑n=1NTNθm,ngmn+∑n=1NμnM−μntmnTherefore, let us take the derivative of (18) with respect to fmn and Zmn, respectively, the optimal CPU frequency fmoptn and transmit power of users pmoptn can be obtained, and their expressions are:
(19)fmoptn=13Cγc1−ρη+∑k=nNλm,kpmoptn=0,tmn=0,Bvmln21−ρη+∑k=nNλm,k−σ02hmn+,tmn>0,where x+=maxx,0 and maxx,0 denotes the bigger value of x and 0.And similar to the above, the optimal offloading time can also be obtained by deriving the following formula for a given trajectoryqun:
(20)log21+hmnZmntmnσ02−hmnZmnln2tmnσ02+hmnZmn−μnNvnBT=0We can handle the (20) by applying the bisection method. Finally, the dual variables can be obtained by using subgradient method [30]. According to [30], the subgradient ensures convergence to the optimal values within a small margin of error.


## 3.2. Optimizing UAV Trajectory

For any given CPU frequencies, transmit power, offloading times of users, we can express the sub-problem about trajectory optimization as:(21)P4:maxqunρ∑m=1M∑n=1NBTtmnvmNlog21+Pmnβ0σ02H2+qun−qm2+1−ρ∑m=1M∑n=1NBtmnlog21+Pmnβ0/σ02H2+qun−qm2vmγcfm3n+tmnpmns.t.1a,1b,and1c.Due to the objective function is non-concave with respect toqun, and we can use SCA technology to handle the non-convex problem of P4. The obtained solution can be guaranteed to satisfy the Karush-Kuhn-Tucker (KKT) conditions of P4 [32]. Thus, the global underestimation can be obtained by using the first-order Taylor expansion method.For any local trajectoryqujn,n∈N at the jth iteration, we have:
(22)log21+β0Pmnσ02H2+qun−qm2≥ymjqunwhere:
(23)ymjqun=log21+Pmnβ0σ02H2+qujn−qm2−Pmnβ0log2equn2−qujn2σ02H2+Pmnβ0+σ02qujn2qujn2+H2where the equality holds when qun=qujn.By replacing the objective function of P4 with (22), the problem (21) is approximately transformed to:
(24)P5:maxqunρ∑m=1M∑n=1NBTtmnvmNymjqun+1−ρ∑m=1M∑n=1NBtmnymjqunvmγcfm3n+tmnPmn,s.t.1a,1b,and1c.It is seen that P5 is convex and can be easily solved by using convex optimization tools such as CVX [32]. By solving P3 and P5, the two sub-problems alternate in an iterative manner. The specific process of the proposed algorithm is summarized in Table 1.Table 1
Two-stage alternative optimization algorithm.
Algorithm 1. The alternative optimization algorithm for P1.1:SettingΓ, T, N, Vmax, q0,qF, and the tolerance errors ξ, ξ1, inputting ρ;2:Initialization:The iterative indexi=1, λm,ni, μni andquin;3:Repeat 1Calculatefopt,in and popt,in by solving problem P3 for given quin;Obtaintopt,i using the bisection method to solve (20);Update λm,ni and μni using the sub gradient algorithm;Initialize the iterative numberj=1;Repeat 2  Solve P5 by using CVX for the given fopt,in, popt,in and topt,i;Updatej=j+1, and quin;If∑n=1Nqujn−quj−1n≤ξquin=qujn;Break;EndEnd repeat 2Update the iterative indexi=i+1;Ifmaxn∈N∑i−∑i−1≤ξ1 where ∑i=ρCBm+1−ρCEmBreak;EndEnd repeat 14: Obtain solutionsHere, we give the complexity analysis for the proposed Algorithm 1. It consists of solving resource allocation and optimizing UAV trajectory with CVX. LetL1 and L2 denote the number of iterations required for the Repeat 1 and Repeat 2 of Algorithm 1, respectively. The computation complexity of Repeat 2 isOL2N3. For Repeat 1, the first aspect is calculate fopt,in and popt,in, the computation complexity is OL12MN; the computation complexity of bisection method for obtaining the tOpt,i is OL1Mlog2l1/T,where l1 denotes the tolerance error for bisection method. The computation complexity of computing the dual variables is OL1/l22, where l2 denotes the tolerance error for the subgradient method. Thus, the total complexity of Algorithm 1 is OL12MN+Mlog2l1/T+1/l22+L2N3.


## 4. Simulation Results

In this section, the numerical results are presented to validate our proposed design. The parameter settings in the simulation process refers to the works in [16, 17]. In this paper, assuming that there are four ground users whose locations are set to q1=3,3, q2=3,8, q3=8,8, and q4=8,3, and the maximum consumed energy constraints are identical for multiple ground users, i.e., Γm=Γ,m∈M, the details of others parameters setting are shown in Table 2.Table 2
Simulation parameters.
ParametersNotationTypical valuesThe height of the UAVH10 mThe time length of the UAV flyingT2 secCommunication bandwidthB40 MHzThe receiver noise powerδ210-9 wThe number of time slotsN50The effective switched capacitanceN10-28The channel power gainβ-50 dBThe tolerance errorξ,ξ110-4The initial location of the UAVq0[0,0]The final location of the UAVqF[10,0]The maximum speed of the UAVVmax10 m/sTo illustrate the effectiveness of our proposed design, two benchmark schemes are considered. 1) The UAV flies from the initial position to final position follow a straight trajectory. 2) The UAV flies from the initial position to final position follow a semi-circle trajectory.Figure3 shows the available CB-CE region of the tradeoff for different schemes, in which the energy consumed threshold Γ=1. This figure shows that available CB-CE region of proposed scheme is bigger than that of benchmark’s, which indicate that through proper design the resource allocation and trajectory, the proposed UAV-MEC system design can achieve better computation performance and reduce the operation cost.Figure 3
The available CB-CE region for different schemes whenΓ=1.We observe the values of the objective function about the tradeoff between computation efficient CE and computation bits CB for different weight parameterρ and maximum consumed energy in Figure 4. For the proposed scheme, as ρ increases, the weight coefficient of the computation bits becomes larger, and the utility function gradually approaches the CB maximization problem. As ρ changes, we can obtain different tradeoff results between CB and CE. Besides, as shown in Figure 4, for a fixed weight parameter ρ, the objective function values increase with consumed energy Γ, and the rate of increase gradually slows down. When ρ=0, since the value of the objective function is very small, the figure shows a straight line close to x axis. On the other hand, compared with CE, CB is more affected by the variation of tradeoff factor ρ and its range of change is larger, which indicates that on the premise of ensuring a large CB value, a relatively large CE value can be taken to optimize the resource allocation of the system. When ρ∈0.4,0.8, both CB and CE values are relatively large, and the designed scheme achieves a good tradeoff effect.Figure 4
The relationship among the objective function values, the weight coefficientρ, and the maximum consumed energy Γ.Figure5 depicts the UAV’s flight trajectory in three different scenarios when T = 2 seconds. In the first scheme, the UAV flies in a straight line from the initial position to the end position and the flight speed remains unchanged; the second scheme, the trajectory of the UAV is a semi-circle with its diameter being qF−q0; the last one is the optimization scheme introduced in previous sections, where the weight parameter is set as ρ=0.5and the maximum consumed energy of user is set as Γ=1.3 joule. By comparing the three trajectories, it can be seen that when the weight of each user is not considered, the trajectory of the proposed scheme is more evenly approaching the location of four users and providing computation service to them. This means that when the UAV is closer to the users, the transmission distance is smaller and the channel power gain is larger, the ground user may tend to offloading more bits to the UAV, and UAV can provide more comupution services for the users.Figure 5
The trajectories of UAV under different schemes.Figure6 shows the relationship between the values of objective function and the maximum consumed energy under three different trajectories when ρ=0.5. It can be clearly seen that the value of the objective function increases with the maximum energy consumption under different schemes, and the objective function value of the designed optimization proposal is significantly higher than that of the UAV flying at a constant speed and flying in a semi-circular trajectory. This means that the designed resource allocation optimization algorithm by jointly optimizing the UAV trajectory is more effective to maximize the tradeoff between computation bits and computation efficiency.Figure 6
Values of the objective function versus the under three different trajectories when 𝜌=0.5.Figure7 shows the objective function values in three modes of local computation, global offloading, and partial computation offloading mode. The first mode is that the users only perform task of local computing, and the second mode is that the users only execute the process of offloading to the UAV. The two benchmark modes are jointly optimized in the trajectory of UAV and Algorithm 1 is used to obtain the curve of partial offloading mode presented in Figure 7. It is obvious that the value of the objective function of offloading mode (include global and partial) is directly proportional to the maximum energy consumed since energy can support users to perform computing tasks and offloading. Moreover, it can be seen that the performance obtained by partial offloading mode is better than that of global offloading modes. The reason is that although the UAV’s computation ability is much stronger than ground users, the ground’s energy and offloading time are both limited, thus the offloading bits are also limited, let the ground user’s computation capability lain idle not a resource-efficiency way. Moreover, users can obtain higher quality channel state information (CSI) when performing tasks under partial offloading mode, so they can allocate resources dynamically and effectively. Furthermore, the performance of local computing mode is inferior to global offloading mode and not changes as the energy increases, this because the ground users’ computation ability is weak in general, within given time duration T=2sec, users energy consumption cannot exceed Γ=1 due to limited computation ability.Figure 7
Values of the objective function versus the maximum consumed energy under three different schemes.Figure8 is given to prove the proposed scheme can guarantee convergence. The figure shows the convergence performance when the maximum consumed energy of users is set as Γ=1.3 joule and the weight coefficients take different values (ρ=0.2; ρ=0.4; ρ=0.6). It is seen that the algorithm can converge after a few iterations. Therefore, it can be concluded that the optimization algorithm adopted in this paper has fast convergence speed and low computational complexity.Figure 8
Values of the objective function versus the number of iterations with different values of 𝜌 andΓ.


## 5. Conclusion

In this paper, we studied the CB-CE tradeoff for the UAV enabled MEC system. The tradeoff optimization problem was formulated to maximize weighted sum of the CB and CE of all users. To tackle the nonconvex problem of jointly optimizing the computation performance and UAV’s trajectory, a two-stage alternative optimization method was exploited to address the primal non-convex problem by formulating it into two subproblems. A combination of the Lagrange duality, SCA method and CVX solver is employed to iteratively solve the subproblems. Simulation results demonstrated that the proposed resource allocation optimization scheme is superior to other benchmark schemes in terms of the computational performance. Moreover, the proposed alternative algorithm has a faster convergence speed, which converged within fewer iterations.



---

*Source: 5775953-2021-09-15.xml*