# A Three-Stage Alternative Optimization Promoting Multi-UAV-Assisted Mobile Offloading

Authors: Xiao Han; Huiqiang Wang; Guangsheng Feng; Xiaoxiao Zhuang; Chengbo Wang
Journal: Security and Communication Networks
 (2022)

---

## Abstract

A solution using multiple-relay method is presented to provide an efficient solution using UAV-assisted mobile devices to complete computation offloading tasks, which considers the UAVs in the offloading system to help mobile devices to offload tasks in remote areas. Additionally, a mixed integer nonlinear optimization (MINO) problem is constructed to maximize minimum user computational speed, and a three-stage iterative optimization algorithm is proposed to find a solution of the MINO problem. Simulation experiments are setup to verify the effectiveness of the devised methods, which show that our proposed algorithm and solution is superior to the single UAV method.


---

## Body

## 1. Introduction

With the blooming of Internet of things (IoT) and wireless mobile networks, smart mobile terminals are extensively considered in high speed information transmission systems to provide powerful platform for various intelligent applications, such as interactive games, augmented/visual realities (ARs/VRs), and unmanned driving, and so on. However, computation resource and battery budget limitations are main obstacle for achieving higher performance. As we know, mobile edge computing, which is a promising paradigm and a new technique to enhance computation speed and robust information transmissions and sharing, uses cloud servers at network edges. Then, one of the effective methods is to offload the data and computation tasks to servers to improve the system performance. For another case, there is little available infrastructures in use, such as disaster scenarios, military maneuver, and so on. Fortunately, unmanned aerial vehicles (UAVs) has been used and developed for assisting mobile edge computing (MEC) to tackle these challenges with less infrastructures.In UAV-assisted MEC networks, computation and communication resources are optimized for achieving objective system design, including minimization consumption energy [1, 2] and minimization system cost [3]. Then, the energy reduction problem is investigated in UAV-enhanced edge via smart offloading decisions and allocating transmitting bits in both uplink and downlink [1]. The energy optimization problem has been extended into multi-UAV-assisted MEC systems using an iterative algorithm with double-loop structure to find optimal solution. To minimize the system cost of vehicle computing tasks, a software defined network (SDN)-derived UAV-assisted vehicular computation offloading optimization framework has been reported to construct a multiplayers offloading sequential game [3]. However, these works focused on optimizing a single objective [1]. After that, multiobjective optimization problems for UAV-assisted MEC network have been presented [4, 5] to provide a balance between the CPU frequencies, the offloading amount, the transmit power, and the UAV’ s trajectory. Additionally, the mission completion time was minimized though jointly optimizing UAV trajectory and communication resource allocation [6] and air base-stations (BSs) with multiple UAVs are used to provide services for users on the ground using multiple UAVs in a wireless communication [7], where UAV trajectory and power can be controlled by optimizing multiuser communication scheduling and association, resulting in maximization throughput for all terrestrial users in downlink communications and hence achieving fair performance between users. Then, a UAV interference channel (UAV-IC) is considered in which each UAV communicates with the associated ground terminal (GT) on the same spectrum to establish a joint trajectory and power control (TPC) to maximize the total power of UAV-IC over a given flight interval [8]. However, all the ideas consider the densely deployed scenarios, which cannot always hold when the BSs are damaged by natural disasters. In addition, these works considered the single demand of users, while both uploading and downloading requirements of users have not been well studied.In contrast to [1–10], the resource allocation problem for multi-UAV-assisted MEC system is investigated and studied, where we consider different offloading requirements for each user. In the devised system, multi-UAV promoting MEC system can be used for mountain and desert damage senses. In the proposed scheme, the UAVs should fulfill offloading before decision and avoid collisions, in which the offloading decision, resources allocation and UAV’s trajectory planning are jointly considered to find an efficient solution using multi-UAV-assisted mobile devices to complete computation offloading tasks. Also, a mixed integer nonlinear optimization (MINO) problem is solved by maximizing minimum user computational speed. In addition, a three-stage iterative optimization algorithm is proposed to find a solution of the MINO problem that is a NP-hard problem. Simulation experiments are setup to verify the effectiveness of the devised methods, which show that our proposed algorithm and solution is superior to the single UAV method. The main contributions of this paper are summarized as follows.(1)
Considering both user data offloading and computation offloading, the multiple UAVs-assisted mobile offloading (MUMO) problem is formulated by considering maximization minimum user calculation rate.(2)
The MUMO problem is carefully considered and divided into three sub-problems, namely, resource allocation, trajectory optimization and anti-collision and offloading decision. The closed form of optimal solution for resource allocation is obtained and analyzed in detail.(3)
A three-stage iterative optimization (TSIO) algorithm is proposed to solve the three sub-questions given above based on successive convex approximation (SCA) methods.As mentioned above, a solution using multiple-relay method is presented to provide an efficient solution using UAV-assisted mobile devices to complete computation offloading tasks, which considers the UAVs in the offloading system to help mobile devices to offload tasks in remote areas. Additionally, a mixed integer nonlinear optimization (MINO) problem is constructed to maximize minimum user computational speed, and a three-stage iterative optimization algorithm is proposed to find a solution of the MINO problem. Simulation experiments are setup to verify the effectiveness of the devised methods, which show that our proposed algorithm and solution is superior to the single UAV method.In this paper, we proposed TSIO algorithm to address the multi-UAV-assisted mobile computation offloading and the simulation experiments are constructed to verify the performance of the proposed scheme and TSIO algorithm. The rest of this work is organized as follows. Section2 introduces the offloading model and presents the optimization problem. The property of the MUMO problem and the TSIO algorithm are proposed in Section 3. The numerical results and the conclusions are given in Sections 4 and 5, respectively.


## 2. Multi-UAV-Assisting Mobile Offloading Model

Considering a multi-UAV-assisted mobile computing and offloading scenario, each UAV can serve multiple users, while one user can only select one UAV. In this case, users are divided in three types, namely, users with computation offloading demand, users with traffic offloading demand, and users with both offloading demands. LetN=1,2,…,N denote the set of users and K=1,2,…K denote the set of UAVs. The position coordinates of user i can be expressed as Li=xil,yil,0, where xil represents the horizontal coordinate of the user location and yil is their ordinate values. All users are fixed on the ground [11–13], and all UAVs fly in the same plane and have a fixed starting point qst and ending point qend. Moreover, the UAV flies at a fixed altitude, which is the height that guarantees normal flying and does not encounter obstacles, and can guarantee normal communication with all users. The wireless channel mode between UAVs and each user adopts the LOS [14] mode, and the channel loss model is Path loss model. The maximum flight speed of the UAV is vmax [15], while the total time from the start point to end point is T that is divided into M slots. Then, the UAV position at each slot can be expressed as qjt=xjct,yjct,H. Assume that there is no interfere between uplink and downlink and the bandwidth is BHz. In addition, the uplink and downlink adopt time division multiplexing (TDM) technology. The specific scenario is shown in Figure 1. Each UAV has its own trajectory, and each user can only select one UAV for service. Moreover, User 2 and User 4 have both uploading and downloading requirements, while User 1 has only downloading requirements, and User 4 has only uploading requirements. User 1 selects UAV2 for service, which may be due to excessive load on UAV2, also including distance and other factors. Therefore, the matching between user and UAV is mainly determined UAV load and UAV distance, UAV power, and so on. bijt represents whether user i chooses UAV j for service at slot t. Herein, bijt is a binary variable. When bijt equals to 1, it means that user chooses the UAV for serving, and vice versa.Figure 1
Multi-UAV assisting users with mobile offloading.The frequency division duplexing (FDD) mode with equal channel bandwidth is adopted for both uplink and downlink.αiut and αidt represent the proportion of upload and download time allocated to users, respectively. θiu indicates whether user has an upload request, and θid indicates whether user has a download request. According to TDM, the sum of the upload time ratios is constrained by(1)∑i=0Nθiuαiut≤1,while the sum of download time ratios is bounded by(2)∑i=0Nθidαidt≤1,where θiu, θid, αiut, and αidt are notified to UAV in advance. Here, the user is restricted to select only one UAV for service in each time slot, and hence, we have(3)∑j=1Kbijt=1.Then, the distance between UAV and user is written assijt=qjt−Ii2. Here, the used channel loss model is the space loss model, and the signal propagation loss hijt of user i to UAV j in time slot t is(4)hijt=δqjt−Ii,where δ is channel power gain. The upload rate of user i at time slot j is(5)Riut=∑j=1KbijtαiuθiuBlog21+PiuthijtN0,where piut represents user transmitting power, and hijt is the signal propagation loss from user i to the UAV j, and N0 is spatial noise. Similar to the uplink, the download rate Ridt of user i is(6)Ridt=∑j=1KbijtαidθidBlog21+PijdthijtN0,where pijdt represents the transmit power allocated by the UAV j. Therefore, uploading data amount Diut and downloading data amount Didt for user i is written as(7)Diut=TRiutM,Didt=TRidtM,(8)Dimint≤Didt.Then, flight speed for UAVj in time slot t is given by(9)vjt=qjt−qjt−1T/M.Moreover, due to the limitations of volume and power, flight speed of UAV is upper bounded by its maximum flight speedvjmax(10)vjt≤vjmax.Due to user equipment size and security factors, the user transmitting power has a certain upper bound(11)piut≤pimax,which is given by(12)∑i=1Npijdt≤pjmax,for each use. To ensure transmission, both of the user and UAV transmitting powers should be greater than 0. Then, one has(13)0<piu,and(14)0<pijd.Since the UAV computing power is high [16], the calculation time and download time for UAVs are ignored. The energy consumed by UAVs includes flight energy consumption and communication energy consumption. The flight energy consumption Ejflyt of the UAV j is(15)Ejflyt=0.5gTvjt2M,where g represents weight of UAV. At each time slot t, the calculation energy consumption model for UAV is created as(16)Eijct=φDiutγjfijc2∀i∈K,j∈N,where φ denotes energy conversion efficiency of UAV processor. γic represents the number of CPU cycles required for user to calculate each bit of data, and fijc is CPU frequency that the UAV j is assigned to the user i in the time slot t. The calculation energy consumption of all the users for UAV j is(17)Ejct=∑i=1NEijct.In time slott, the download energy consumption generated by UAV j is(18)Eijdt=TθidbijtpijdtαidtM.For UAVj, the communication energy consumption caused by data download is(19)Ejdt=∑i=1NEijdt.Similarly, in time slott, the upload energy consumption generated by UAV j is(20)Ejut=∑i=1NbijTθiupjrαiutM.Due to effects such as UAV batteries and volume limitations, the energy for UAVs is limited, which cannot exceed the maximum residual energyσj in the UAV, and hence, the UAV has following energy constraints(21)∑t=1MEjflyt+Ejdt+Ejut+Ejct≤σj.In addition, since multiple UAVs fly in the same height, collision avoiding is a problem that must be solved.dmin is defined as the safest distance between multiple UAVs. During each time slot, UAV i and UAV j must follow the conditions(22)qit−qjt≥dmin.Considering the fairness of users, the goal is to maximize minimum user computational rate. Letη represent the minimum calculation rate of all users. Then, we have(23)∑t=1MDiut≥η.Since the UAV has a fixed starting pointqjs and an ending point qje, it has constraint(24)qj0=qjs,and(25)qjM=qje.Therefore, the optimization P0 is formulated as(26)P0′maxαiut,αidt,qjt,piut,pijdt,bijtηs.t.bijt∈0,1,and equations (1)–(3), (9), (11)–(15) and (22)–(26)The constraints (1) and (2) represent dynamic bandwidth allocation constraints while the constraint (3) represents the dynamic matching constraint for UAVs and the users. The constraint (8) is the minimum user download rate constraint, and the constraint (10) represents the maximum UAV flight rate constraint. The constraints (11) and (13) represent the upper and lower limits of transmission power of the user, respectively. The constraints (12) and (14) represent the transmission power constraints of the UAVs. (21) indicates the energy constraint of the UAV, while (22) represents multiple UAV anti-collision constraints, and (23) is minimum user upload rate constraint. In addition, the constraints (24) and (25) denotes a fixed starting point and ending point for the UAV. In order to ensure fairness between users, the objective function is taken to maximize minimum user calculation rate.


## 3. Three-Stage Iterative Optimization Algorithm

Sincebijt is a binary variable, pijdt and αidt are continuous variables. Additionally, there is a nonlinear coupling between the variables in constraint (24). Thus, the problem P0′ can be considered as a mixed integer nonlinear programming problem. At the same time, as the constraints (9) and (24) are non-convex, the problem P0′ changes to be a non-convex optimization problem. For non-convex mixed integer nonlinear programming problems (MINLP), currently, there is no effective solution. Thus, it is difficult to solve this problem since multiple variables are coupled together. Herein, we propose a TSIO to solve problem P0′. The first stage fixes qjt and bijt. Then, this problem is transformed into a resource allocation optimization problem. The second stage takes the value of the resource allocation-related variable into P0′. At the same time, bijt are always fixed, and an optimization problem of UAV path planning and collision avoidance with only the variable qjt can be obtained. The third stage brings qjt and the resource allocation-related variables into P0′. Then, the optimization problem has only integer variables.


### 3.1. Stage 1: Resource Optimization

The first step of the TSIO method is to fix the variablesqjt,bijt, and the following optimization problem P1′ is obtained for UAV and user matching(27)P1′:maxαiut,αidt,piut,pijdtη,s.t. (1), (2), (9), (12)–(15) and (12)–(26).The nonlinear coupling of variables exists in the constraints in (8) and (21) so that the problem P0 is a non-convex nonlinear programming problem. First, let ϕiut=αiutpiut , ϕijdt=αidupijd,ϕijru=αiuupjr. The problem P1′ can be changed to the following optimization problem P2′ given in (28),(28)P2′:maxαiut,αidt,piut,pijdt,ϕijdt,ϕiut,ϕijrtηs.t.1,2,12−15TM∑j=1KbijtαidtθidBlog21+ϕijdthijtαidtN0≥DimintTM∑j=1KbijtαiutθiuBlog21+ϕiuthijtαidtN0≥η∑t=1M0.5TMvj2t+∑i=1NTMθidbijtϕijdt+∑i=1NTMθiubijtϕijrt+∑i=1NTφγjfijc2M∑j=1KbijtαiutθiuBlog21+ϕiuthijtN0αiut≤σj,(29)L=η+∑t=1M∑i=1Nβiut∑i=1Nαiutθiu−1+∑t=1M∑i=1Nβidt∑i=1Nαidtθid−1+∑i=1N∑t=1MπidtDimint−∑j=1Kξijd+∑t=1M∑i=1Nμiumtpiut−pimax+∑t=1M∑j=1Kμjdmt∑i=1Npijdt−pjmax−∑t=1M∑i=1Nμidtpidt−∑t=1M∑i=1N∑j=1Kμijdtpijdt+∑i=1Nπiuη−∑t=1MDiut+∑j=1Kλj∑t=1MEjflyt+∑i=1NTMθidbijtϕijdt+∑i=1NTMθiubijtϕijrt+∑i=1Nφγjfijc2TM∑m=1Kbimtξiut,where these constraints have nonlinear coupling variables, resulting in the problem being a non-convex nonlinear programming problem. Let φiut=αiutpiut, φijdt=αidtpijdt, φijrt=αiutpjr. Then problem P1 can be transformed into the optimization problem P2. Since the constraints (1), (2), (12)–(15) and (31) and the objective function in the problem P2′ are both linear functions, and the constraints (28) and (29) are both nonlinear convex, the problem P2′ is considered as a convex optimization problem. It can be derived using convex optimization tools. Then, we get the following Theorem 1.(30)κβiut,βidt,πidt,μiumt,μjdmt,μidt,μijdt,πiu,λj=maxL,(31)minκβiut,βidt,πidt,μiumt,μjdmt,μidt,μijdt,πiu,λj.Theorem 1.
In questionP2′, the expression of the optimal solution αi,optut,αi,optdt,pi,optut,pij,optdt of the variable αiut,αidt,piut,pijdt can be obtained by solving the Lagrangian multipliers corresponding to (1), (2), (12)–(15) and (29)–(31).Proof.
To simplify the expression, letξijdt=T/MαidtθidBlog21+ϕijdthijt/αidtN0, ξiut=T/MαiutθiuBlog21+ϕiuthit/αiutN0. Then, the Lagrangian function of the problem P2′ can be constructed and given by equation (30), where βiut,βidt,πidt,μiumt,μjdmt,μidt,μijdt, πiu,λj are the corresponding Lagrangian multipliers for constraints (1), (2), (12)–(15) and (29)–(31), respectively. Next, Lagrangian dual function for P2′ is presented as equation (31).
By solving its dual problem, the optimal solution of P2 can be obtained. The dual problem is given in (31) since P2′ is a convex optimization problem. Then, the optimal solution can be obtained.


### 3.2. Stage 2: Decision Optimization

When the solution of Stage 1 is completed, the optimal solution ofαi,optut,αi,optdt,pi,optut,pij,optdt is assigned to the variables αiut,αidt,piut,pijdt and brought into the original question P1′. Then, by fixing the variable bijt, we get the following multi-UAV path planning problem P3(32)P3:maxqjtη,s.t (9), (11) and (24)–(26)(33)TM∑j=1KbijtαidtθidBlog21+pijdtδN0H2+qjt−lit2≥Dimint,(34)TM∑j=1KbijtαidtθidBlog21+pijdtδN0H2+qjt−lit2≥η,(35)∑t=1M0.5gqjt−qjt−1+Ejdt+Ejut+∑i=1NTφγjfijc2M∑j=1KbijtαiutθiuB×log21+piutδN0H2+qjt−lit2≤σj,where the constraints (9), (22), and (24) are listed in equations (34), (35), and (36). By finding the Hessian matrix of the function, the constraints (27)–(29) can be found to be convex. Therefore, the following Theorem 2 can be obtainedTheorem 2.
For any given feasible UAV trajectoryqj0t, the following inequality holds(36)log21+δpiutN0H2+qjt−lit2≥ψijut=log21+δpiutN0H2+qj0t−lit2−δlog2epiutqjt−lit2N0H2+δpijdt+N0qj0t2H2+qj0t2,log21+δpijdtN0H2+qjt−lit2≥ψijdt=log21+δpijdtN0H2+qj0t−lit2−δlog2epijdtqjt−lit2N0H2+δpijdt+N0qj0t2H2+qj0t2.
Whenqjt=qj0t, the equal sign of inequality (30) and (31) holds. Obviously, the proof can be gotten using Taylor formula, which is to say that after the non-convex term is relaxed, it becomes a convex function P3′. If it is brought into a problem, the convex optimization problem P4′ can be obtained as follows(37)P4′:maxqjtηs.t.11TM∑j=1KbijtαidtθidBψijdt≥DimintTM∑j=1KbijtαiutθiuBψijut≥η∑t=1M0.5gqjt−qjt−1+Ejdt+Ejut+∑i=1NTφγjfijc2M∑j=1KbijtαiutθiuBψijut≤σj.
Since all constraints and objective functions inP4′ are convex, P4′ is a convex optimization problem. For this problem, we can solve it using convex optimization tool.


### 3.3. Stage 3: Trajectory Optimization

When the optimal solution of Stage 1 and Stage 2 are solved, the following optimization problemP5 of UAV for user matching can be obtained(38)log21+δpijdtN0H2+qjt−lit2≥ψijdt=log21+δpijdtN0H2+qj0t−lit2−δlog2epijdtqjt−lit2N0H2+δpijdt+N0qj0t2H2+qj0t2.Whenqjt=qj0t, sign of equality in (29) and (30) holds. Obviously, the proof can be obtained using Taylor formula, which is to say that it becomes a convex function P3′ after non-convex term relaxation. Then, the convex optimization problem P5 can be obtained(39)P5:maxbijtη,s.t (1), (2), (9), (22) and (24).Wherebijt is a binary variable, and both constraint and objective function are linear so that the problem P5 is an integer linear programming problem (ILP) which can be solved using the classical branch and bound (BB) algorithm [17]. The main idea of the BB algorithm is to continuously traverse the solution space of P5 until optimal solution is found. The integer variable is relaxed to get a continuous variable to create a new sub-problem with a branch operation. Meanwhile, the optimal solution based on the sub-problem continuously obtains upper and lower bounds. When the upper and lower bounds are equal, the optimal solution is gotten. When the optimal solution bij,optt of the TSIO and ηopt of the objective function are obtained. They will be brought into the first stage to promote to update the phases until the difference between optimal values is less than a threshold to stop the iteration. In a word, the solution is converged and an approximate optimal solution is found. The devised TSIO algorithm is summarized as Algorithm 1.Algorithm 1: The TSIO algorithm.
(1)
Initializeqjst, qjet, k  = 1, threshold ρ1, ρ2, ρ3, η0=∞(2)
whileηk−ηk−1>ρ1 do(3)
Givenqj,opt and variable bij,opt, use convex optimization tool to solve P2, and obtain αi,optut,αi,optdt,pi,optut,pij,optdt;(4)
Substitute the optimal solution of P2 into P4, and letm=1;(5)
while∃j∈1,2,…,K,∑t=1Mqj,mt−qj,m−1t>ρ2 do(6)
SolveP4 using convex optimization tool to obtain qj,opt; m=m+1; qj,m=qj,opt(7)
end while(8)
Substituteqj,opt of P4 into P5; relax bij of P5 to grt a continuous variable. Then, obtain its relaxation sub-problem SPk and place them in the solution queue a; Set upper bound of(9)
while list is not empty do(10)
Take a sub-problem from the solution queueSPk, solve it, and get its optimal solution bij,opt and ηopt;(11)
ifbijm are integers then(12)
ifηopt>LB then(13)
SetLB=ηopt, remove the sub-problems if UB<LB(14)
end if(15)
else(16)
Relaxbij,opt, then, get a new sub-problem SPk+1, SPk+2 and put it into the solution queue; Set m=m+1,UBm=ηopt(17)
end if(18)
end while(19)
k=k+1,ηk=ηopt(20)
end while


## 3.1. Stage 1: Resource Optimization

The first step of the TSIO method is to fix the variablesqjt,bijt, and the following optimization problem P1′ is obtained for UAV and user matching(27)P1′:maxαiut,αidt,piut,pijdtη,s.t. (1), (2), (9), (12)–(15) and (12)–(26).The nonlinear coupling of variables exists in the constraints in (8) and (21) so that the problem P0 is a non-convex nonlinear programming problem. First, let ϕiut=αiutpiut , ϕijdt=αidupijd,ϕijru=αiuupjr. The problem P1′ can be changed to the following optimization problem P2′ given in (28),(28)P2′:maxαiut,αidt,piut,pijdt,ϕijdt,ϕiut,ϕijrtηs.t.1,2,12−15TM∑j=1KbijtαidtθidBlog21+ϕijdthijtαidtN0≥DimintTM∑j=1KbijtαiutθiuBlog21+ϕiuthijtαidtN0≥η∑t=1M0.5TMvj2t+∑i=1NTMθidbijtϕijdt+∑i=1NTMθiubijtϕijrt+∑i=1NTφγjfijc2M∑j=1KbijtαiutθiuBlog21+ϕiuthijtN0αiut≤σj,(29)L=η+∑t=1M∑i=1Nβiut∑i=1Nαiutθiu−1+∑t=1M∑i=1Nβidt∑i=1Nαidtθid−1+∑i=1N∑t=1MπidtDimint−∑j=1Kξijd+∑t=1M∑i=1Nμiumtpiut−pimax+∑t=1M∑j=1Kμjdmt∑i=1Npijdt−pjmax−∑t=1M∑i=1Nμidtpidt−∑t=1M∑i=1N∑j=1Kμijdtpijdt+∑i=1Nπiuη−∑t=1MDiut+∑j=1Kλj∑t=1MEjflyt+∑i=1NTMθidbijtϕijdt+∑i=1NTMθiubijtϕijrt+∑i=1Nφγjfijc2TM∑m=1Kbimtξiut,where these constraints have nonlinear coupling variables, resulting in the problem being a non-convex nonlinear programming problem. Let φiut=αiutpiut, φijdt=αidtpijdt, φijrt=αiutpjr. Then problem P1 can be transformed into the optimization problem P2. Since the constraints (1), (2), (12)–(15) and (31) and the objective function in the problem P2′ are both linear functions, and the constraints (28) and (29) are both nonlinear convex, the problem P2′ is considered as a convex optimization problem. It can be derived using convex optimization tools. Then, we get the following Theorem 1.(30)κβiut,βidt,πidt,μiumt,μjdmt,μidt,μijdt,πiu,λj=maxL,(31)minκβiut,βidt,πidt,μiumt,μjdmt,μidt,μijdt,πiu,λj.Theorem 1.
In questionP2′, the expression of the optimal solution αi,optut,αi,optdt,pi,optut,pij,optdt of the variable αiut,αidt,piut,pijdt can be obtained by solving the Lagrangian multipliers corresponding to (1), (2), (12)–(15) and (29)–(31).Proof.
To simplify the expression, letξijdt=T/MαidtθidBlog21+ϕijdthijt/αidtN0, ξiut=T/MαiutθiuBlog21+ϕiuthit/αiutN0. Then, the Lagrangian function of the problem P2′ can be constructed and given by equation (30), where βiut,βidt,πidt,μiumt,μjdmt,μidt,μijdt, πiu,λj are the corresponding Lagrangian multipliers for constraints (1), (2), (12)–(15) and (29)–(31), respectively. Next, Lagrangian dual function for P2′ is presented as equation (31).
By solving its dual problem, the optimal solution of P2 can be obtained. The dual problem is given in (31) since P2′ is a convex optimization problem. Then, the optimal solution can be obtained.


## 3.2. Stage 2: Decision Optimization

When the solution of Stage 1 is completed, the optimal solution ofαi,optut,αi,optdt,pi,optut,pij,optdt is assigned to the variables αiut,αidt,piut,pijdt and brought into the original question P1′. Then, by fixing the variable bijt, we get the following multi-UAV path planning problem P3(32)P3:maxqjtη,s.t (9), (11) and (24)–(26)(33)TM∑j=1KbijtαidtθidBlog21+pijdtδN0H2+qjt−lit2≥Dimint,(34)TM∑j=1KbijtαidtθidBlog21+pijdtδN0H2+qjt−lit2≥η,(35)∑t=1M0.5gqjt−qjt−1+Ejdt+Ejut+∑i=1NTφγjfijc2M∑j=1KbijtαiutθiuB×log21+piutδN0H2+qjt−lit2≤σj,where the constraints (9), (22), and (24) are listed in equations (34), (35), and (36). By finding the Hessian matrix of the function, the constraints (27)–(29) can be found to be convex. Therefore, the following Theorem 2 can be obtainedTheorem 2.
For any given feasible UAV trajectoryqj0t, the following inequality holds(36)log21+δpiutN0H2+qjt−lit2≥ψijut=log21+δpiutN0H2+qj0t−lit2−δlog2epiutqjt−lit2N0H2+δpijdt+N0qj0t2H2+qj0t2,log21+δpijdtN0H2+qjt−lit2≥ψijdt=log21+δpijdtN0H2+qj0t−lit2−δlog2epijdtqjt−lit2N0H2+δpijdt+N0qj0t2H2+qj0t2.
Whenqjt=qj0t, the equal sign of inequality (30) and (31) holds. Obviously, the proof can be gotten using Taylor formula, which is to say that after the non-convex term is relaxed, it becomes a convex function P3′. If it is brought into a problem, the convex optimization problem P4′ can be obtained as follows(37)P4′:maxqjtηs.t.11TM∑j=1KbijtαidtθidBψijdt≥DimintTM∑j=1KbijtαiutθiuBψijut≥η∑t=1M0.5gqjt−qjt−1+Ejdt+Ejut+∑i=1NTφγjfijc2M∑j=1KbijtαiutθiuBψijut≤σj.
Since all constraints and objective functions inP4′ are convex, P4′ is a convex optimization problem. For this problem, we can solve it using convex optimization tool.


## 3.3. Stage 3: Trajectory Optimization

When the optimal solution of Stage 1 and Stage 2 are solved, the following optimization problemP5 of UAV for user matching can be obtained(38)log21+δpijdtN0H2+qjt−lit2≥ψijdt=log21+δpijdtN0H2+qj0t−lit2−δlog2epijdtqjt−lit2N0H2+δpijdt+N0qj0t2H2+qj0t2.Whenqjt=qj0t, sign of equality in (29) and (30) holds. Obviously, the proof can be obtained using Taylor formula, which is to say that it becomes a convex function P3′ after non-convex term relaxation. Then, the convex optimization problem P5 can be obtained(39)P5:maxbijtη,s.t (1), (2), (9), (22) and (24).Wherebijt is a binary variable, and both constraint and objective function are linear so that the problem P5 is an integer linear programming problem (ILP) which can be solved using the classical branch and bound (BB) algorithm [17]. The main idea of the BB algorithm is to continuously traverse the solution space of P5 until optimal solution is found. The integer variable is relaxed to get a continuous variable to create a new sub-problem with a branch operation. Meanwhile, the optimal solution based on the sub-problem continuously obtains upper and lower bounds. When the upper and lower bounds are equal, the optimal solution is gotten. When the optimal solution bij,optt of the TSIO and ηopt of the objective function are obtained. They will be brought into the first stage to promote to update the phases until the difference between optimal values is less than a threshold to stop the iteration. In a word, the solution is converged and an approximate optimal solution is found. The devised TSIO algorithm is summarized as Algorithm 1.Algorithm 1: The TSIO algorithm.
(1)
Initializeqjst, qjet, k  = 1, threshold ρ1, ρ2, ρ3, η0=∞(2)
whileηk−ηk−1>ρ1 do(3)
Givenqj,opt and variable bij,opt, use convex optimization tool to solve P2, and obtain αi,optut,αi,optdt,pi,optut,pij,optdt;(4)
Substitute the optimal solution of P2 into P4, and letm=1;(5)
while∃j∈1,2,…,K,∑t=1Mqj,mt−qj,m−1t>ρ2 do(6)
SolveP4 using convex optimization tool to obtain qj,opt; m=m+1; qj,m=qj,opt(7)
end while(8)
Substituteqj,opt of P4 into P5; relax bij of P5 to grt a continuous variable. Then, obtain its relaxation sub-problem SPk and place them in the solution queue a; Set upper bound of(9)
while list is not empty do(10)
Take a sub-problem from the solution queueSPk, solve it, and get its optimal solution bij,opt and ηopt;(11)
ifbijm are integers then(12)
ifηopt>LB then(13)
SetLB=ηopt, remove the sub-problems if UB<LB(14)
end if(15)
else(16)
Relaxbij,opt, then, get a new sub-problem SPk+1, SPk+2 and put it into the solution queue; Set m=m+1,UBm=ηopt(17)
end if(18)
end while(19)
k=k+1,ηk=ηopt(20)
end while


## 4. Results and Discussion

In this section, the performance of the proposed multi-UAV-assisted mobile offloading using devised TSIO algorithm is presented, analyzed and discussed in detail. Herein, assuming that the number of users isN=5 and the coordinates for all users are L1=0,0, L2=10,0, L3=0,10, L4=10,10, and L5=5,5, respectively. Also, all users have the computation requirement au=1,1,1,1,1 and download requirements ad=1,1,1,1,1, where the value equals to 1, meaning that the user has the requirement. Two UAVs are used, namely, UAV1 and UAV2, respectively. The start point of UAV1 is the same as L1, and the target point (destination) is the same as L2, while the start point of UAV2 is the same as L4, and the target point (destination) is the same as L3. UAV’s maximum flight speed is 20m/s. The continuous flight time T=2s, which is divided into 50 time slots. The vertical height of the UAVs is H=15m. The power of UAV1 is 500kJ2 and the power of UAV2 is 400kJ2, where the power of UAV1 is greater than that of UAV2. Experimental UAV flight trajectory and user matching are given using computer simulations, and the effects of different optimization schemes on the minimum computing rate are studied and discussed, which verifies the superior performance of the proposed scheme and TSIO algorithm.Figure2 shows the flight trajectory for UAV1 and UAV2, while Table 1 presents the UAV used by users. From Table 1, we can see that UAV1 provides service for L1, L2, and L5, while UAV2 provides service for L3 and L4. The trajectory of UAV1 is approximately elliptical, but UAV2 flies along a straight line. The main reason for different trajectories is that UAV1 serves to three users to ensure that all three users could get a reasonable transmission rate. In order to ensure the computation and download rate at L5, UAV1 needs to approach to L5 initially to reduce transmission distance and increase transmission rate. The larger vertical height between UAV1 and L5 is, the larger distances between UAV1, L1, and L2 are. Therefore, when the vertical distance of UAV1 rises to a certain height, it will not change so that it can guarantee the transmission rate for L1 and L2. Thus, the flight trajectory of UAV1 is affected by three users, namely, L1, L2, and L5. On the contrary, UAV 2 is moved horizontally between L3, L4 to get the shortest distance from L3 and L4 since UAV2 provides services for L3 and L4 to increase transmission rate and save transmission power. L1 and L2 choose UAV1 for service because they are close to each other. Similar to the L3 and L4, L5 chooses UAV1 for service as the power of UAV1 is larger than that of UAV2. Hence, the trajectory of UAV and the choice of users are related to not only the distance but also the UAV power.Figure 2
UAV1 and UAV2 flight trajectory.Table 1
User matches with drone.
user1user2user3user4user5UAV num11221Figure3 reveals the dynamic change of the user’s minimum computing rate in the process of solving the TSIO algorithm. It is found that the initial minimum computing rate of users is relatively high, and then it decreases until convergence. Herein, the TSIO algorithm is divided into three stages to solve three problems, which cannot satisfy all constraints at the initial state. With the algorithm going, all the constraints are gradually satisfied. When all constraints are satisfied simultaneously, the results do not change. It is observed that the convergence speed for the TSIO algorithm is faster, which converges at about 13 times. Also, the greater maximum user transmission power is, the greater minimum user calculation rate is and the higher signal-to-noise ratio (SNR) of the transmission is, which further increases the upload rate. Meanwhile, all the users can get high minimum calculation rate to ensure the fairness between users.Figure 3
Dynamic change of minimum user calculation rate.Figure4 demonstrates the change of the minimum user calculation rate with maximum user transmit power in different UAV paths. It can be seen that the larger the maximum user transmit power is, the larger the minimum calculation rate is, which is same as the conclusion in Figure 3. Additionally, compared with the semi-circular path with fixed UAVs, the optimal path obtained by the proposed scheme can achieve a higher minimum calculation rate.Figure 4
Relation between minimum user computing rate and maximum user transmitting Power.Figure5 illustrates the variation of minimum user computation rate with maximum transmit power for UAV1 and UAV2 under different paths, where we assume that the maximum transmit powers for UAV1 and UAV2 are same. We found that the larger the maximum UAV transmitting power is, the larger the minimum user computing rate is. With the increasing of the maximum UAV transmit power, the transmission power allocating to each user also increases, which further increases SNR. Therefore, UAV can satisfy minimum download rate constraining of users in a longer distance. Because UAV path is less affected by user’s minimum download rate constraint, UAV path can be further optimized to make user upload rate higher. Hence, the higher the maximum UAV transmit power is, the higher the minimum user download rate is. Moreover, we can see that the optimal path proposed in this paper can achieve better results than that of the semi-circular path.Figure 5
Relation between minimum UAV computing rate and maximum UAV transmitting Power.Figure6 shows the user transmit power dynamically changes at different times. It is found that the transmitting power of L1 increases with the increment of time slot since L1 chooses UAV1 for service and the distance between L1 and UAV1 is smaller at beginning. In this case, users can achieve higher upload rate with low transmission power. As the UAV1 moves to L2, the distance between them increases. To maintain a higher upload rate, transmit power for L1 should be increased. At the same time, it is observed that L2 has a higher transmission power at its initial. Similar to user 1, it requires a larger transmit power to maintain a higher upload rate since L2 is far away from UAV1. As UAV1 moves, the distance between them becomes smaller and smaller, and it can reach same upload rate with a smaller transmission power. L3 and L4 select UAV2 for service, and the trend is similar to L1 and L2. However, the transmission power of L3 and L4 is smaller than L1 and L2 because UAV1 needs to serve L5 via changing its flight trajectory so that the distance between UAV1 and L1 and L2 becomes farther during the flight. UAV2 only serves L3 and L4, and their distance is relatively closer. Therefore, it only needs to use smaller transmit power to achieve the same upload rate like L1 and L2. Finally, it can be seen that the transmission power of L5 decreases firstly and then increases, which is related to the distance between users and UAV. From the UAV trajectory diagram, we can see that the distance between L5 and UAV1 is first decreased and then increased.Figure 6
Dynamic changes of user transmit power in different time slots.Figure7 shows the dynamic variation of user transmission time ratio over different time slots. It can be seen that the proportion of transmission time for user 1 is continuously decreasing, which is similar to that of Figure 6. Since the distance between UAV1 and user decreases as the time slot increases, the user transmit power also increases. When the user transmit power is small, it indicates that the user is closer to UAV. In order to ensure the fairness between users, the UAV allocates less transmission time for more recent users and allocates more transmission time for farther users to ensure that all users can achieve minimum upload rate. Comparing Figure 6 with 7, it can be concluded that the farther the UAV is from the user, the greater the user transmit power and proportion of transmission time allocated by the user are. The reason for the change trend of the remaining users is similar to that of User 1, which is not described here.Figure 7
Dynamic change of user transmission time ratio in different slots.Figure8 presents the variation of the minimum user computational rate with maximum user transmit power for different UAV numbers. Firstly, similar to Figure 3, the greater the user transmit power is, the greater the user minimum computation rate is. Secondly, it can be seen that the more UAVs are, the greater the minimum user calculation rate is. As the number of UAVs increases, the competition between users becomes smaller, and the number of users of a single UAV service becomes smaller. Thus, the movement trajectory can be further optimized, and if the user is closer to UAV during the movement, the user can obtain a larger calculation rate with the same transmission power. Therefore, the greater the number of UAVs is, the greater the minimum user computational rate is, which also indicates the effectiveness of the proposed scheme.Figure 8
Dynamic changes of minimum computing rate with maximum transmit power for different UAVs.


## 5. Conclusion

A multi-UAV-assisting data unloading and computational uploading scheme for multi-user has been proposed, analyzed, and discussed, which is modeled as mixed-integer nonlinear optimization (MINO) problem. Also, a three-stage iterative optimization (TSIO) algorithm is presented, investigated and discussed to find a solution for the MINO problem. The path conflict avoidance between multiple UAVs, the matching between multiple UAV and users, and the effects, such as UAV energy, user uplink and downlink transmission bandwidth allocation have been investigated using simulation experiments. Additionally, the TSIO is also used for achieving maximization the minimum user calculation rate. Experimental results further verified the effectiveness of the proposed multi-UAV scheme to assist users for mobile offloading, which also show that our proposed algorithm and solution is superior to the single UAV method.We believe that with the proposed method, we solved the computing offloading and data offloading of fixed users by using UAV. However, in certain specific scenarios, the user is mobile (for example, search and rescue in disaster events). For this reason, we will solve the UAV cooperative communication and calculation under the condition of user movement in the follow-up work.



---

*Source: 5682891-2022-08-23.xml*