# UAV-Enabled Data Collection: Multiple Access, Trajectory Optimization, and Energy Trade-Off

Authors: Lin Xiao; Yipeng Liang; Chenfan Weng; Dingcheng Yang; Qingmin Zhao
Journal: Wireless Communications and Mobile Computing
 (2019)

---

## Abstract

In this paper, we consider a ground terminal (GT) to an unmanned aerial vehicle (UAV) wireless communication system where data from GTs are collected by an unmanned aerial vehicle. We propose to use the ground terminal-UAV (G-U) region for the energy consumption model. In particular, to fulfill the data collection task with a minimum energy both of the GTs and UAV, an algorithm that combines optimal trajectory design and resource allocation scheme is proposed which is supposed to solve the optimization problem approximately. We initialize the UAV’s trajectory firstly. Then, the optimal UAV trajectory and GT’s resource allocation are obtained by using the successive convex optimization and Lagrange duality. Moreover, we come up with an efficient algorithm aimed to find an approximate solution by jointly optimizing trajectory and resource allocation. Numerical results show that the proposed solution is efficient. Compared with the benchmark scheme which did not adopt optimizing trajectory, the solution we propose engenders significant performance in energy efficiency.


---

## Body

## 1. Introduction

With series of features such as low cost, long duration, high flexibility, and high adaptability, extensive research endeavour has been rendered to exploring the application of UAV. In [1], the authors made a survey on autonomous cargo pickup with an UAV helicopter by designing systems including self-tracking, payload pickup, and deployment of cargo. In [2], the UAVs are employed to airborne maritime surveillance, which commits to monitoring of the marine environment, safeguarding national security, sovereignty, and as sea rescue. Anwar et al. [3] studied the framework of detecting and classifying sounds of amateur aircraft out in noisy environment by leveraging machine learning to maintain public safety. They also [4] proposed a disaster-resilient architecture including centralized control and edge computing for disaster areas, which can reduce delay effectively. Moreover, UAV networks are developing rapidly embracing the wireless technologies such as IEEE 802.11n, IEEE 802.15.4, and 3G/LTE [5–9]. However, UAVs will also face many challenges in its application. Researchers are also trying to solve these problems. In particular, it can not only be hired for delivery of goods, but also serve as low-altitude aircraft to improve the coverage and rate of wireless networks in different scenarios. First, placement/deployment optimization is a major challenge for quasistatic drones [10–14]. In [10], coverage was optimized by adjusting the height of the platform. In [11], the authors characterize the performance and trade-offs of UAV with underlaid device-to-device communication. Compared with terrestrial base stations, UAV has more advantages as airborne static base stations, for its excellent capability to have line-of-sight communication links (LOSs) to the ground terminal, which will achieve the maximum communication coverage of the ground terminal. Thus, in [12], the authors propose an efficient deployment method based on circle packing theory, using minimum transmit power and maximizing the total coverage area. Bor-Yaliniz et al. [13] emphasized the performances of drone-cell placement problem by designing it as a 3D placement that leads to maximum revenue of the network. Second, UAV’s energy efficiency and resource management are crucial factors in its communication systems. There are many differences between traditional wireless communication system and UAV communication. Energy efficiency maximization of traditional wireless communication systems is to save energy of communication, but in the UAV communication system, the energy for communication is much lower than that of the UAV itself. So, the UAV’s energy consumption is the main factor that needs to be considered toward high efficiency and energy saving [14–16]. Inspired by this, trajectory optimization of energy-efficient UAV communication has been studied, in which sequential convex optimization techniques are applied to deal with the nonconvex trajectory optimization problems [17], despite its research object being single UAV and a ground user, but the frame can extend to a joint trajectory and communication design in multi-UAVs wireless network. Motivated by this, the joint optimization problem of user scheduling, transmit power, and UAV trajectories was studied in the multi-UAV system [18]. In IoT networks, an efficient mobile scheme of uplink data collection was studied [19]. Wu and Zhang [20] consider the user communication delay requirements, maximizing the system total throughput via joint resource allocation and UAV trajectory. Furthermore, energy saving has been recognized as a vital target in designing future wireless communication system [21]. In particular, UAV communication systems are considered. In [22], the author proposed a throughput-delay trade-off in a new cyclical multiple access scheme in UAV communications. In the previous work, we have investigated an energy trade-off between a UAV and single ground user [23], with results being extendable to UAV-enabled multiuser communication networks.As we discussed previously, energy efficiency is a factor that cannot be ignored for UAV due to the limited on-board power. He et al. [24] investigated the throughput by jointly optimizing the UAV’s flying altitude and antenna beamwidth in case of downlink multicasting, downlink broadcasting, and uplink multiple access models without considering energy consumption. Lyu et al. [25] optimize the deployment of the UAV to provide wireless coverage for ground terminal which does not study the issue of energy efficiency. Zeng et al. [26] aim to design trajectories to minimize the mission completion time and also hardly consider energy consumption. Zeng and Zhang [17] study energy efficiency by trajectory optimization, but only a UAV and a user included. For a UAV communication system, besides coverage, UAV’s energy efficiency and resource management is necessary to investigate, especially in multiuser UAV communication.In this paper, a flexible UAV is deployed to collect data from a group of ground terminals at known location in ground terminals to a UAV (G2U) system. Intuitively, the study needs to jointly consider the uplink transmission energy of GTs and the UAV’s propulsion energy consumption. To obtain the most fundamental insights, we focus on a G2U wireless communication system, where a group of ground terminals are collected data by a UAV, as shown in Figure1. Specially, an efficient algorithm that combines optimal trajectory design and resource allocation scheme is proposed to approximately solve the optimization problem. For optimal trajectory design and resource allocation, we gain the optimal GTs transmit power and UAV trajectory, respectively. Numerical results evaluate the trade-off involved in the proposed designs. A special case where a G2U communication scheme considering two ordinary UAV trajectories with circular and straight trajectories has been studied in [23].Figure 1
A UAV-enabled data collection system.The rest of this paper is organized as follows. Section2 introduces the system model, and problem formulation for a high-mobile UAV is deployed regularly to total ground nodes for data collection. In Section 3, we first formulate the optimization problem to describe the Pareto boundary of the energy region. An efficient iterative algorithm is proposed by combining optimal trajectory design and resource allocation scheme; then the numerical results are solved in Section 4. Finally, we conclude the paper in Section 5.


## 2. System Model and Problem Formulation

### 2.1. System Model

We consider a wireless system consisting ofK ground nodes, denoted as U1,…,Uk, where the coordinate of Uk is denoted as qk=xk,ykT. We assume that each of the ground node Uk periodically generates data of size R^k for each period of duration Ts, which need to be regularly uploaded to the fusion center for data processing. This could correspond to the practical periodic sensing applications. We assume that there is no established communication link between the ground nodes and fusion center due to their long separation distance as well as the high cost in deploying fixed communication infrastructure such as relays. Instead, we assume that a high-mobile UAV is despatched regularly to fly over the ground nodes for data collection and then brings it back to the fusion center for off-line processing.We assume that the UAV flying at a fixed altitudeH around the ground terminals for data collection for a finite time horizon T. Note that T is the time required for the UAV to complete the data collection task R^k for each period Ts. In practice, we usually have T≪Ts (e.g., dozens of minutes versus several days) since the data are only generated intermittently. We denote the time-varying coordinate of the UAV’s horizontal location as wt=xt,ytT, 0≤t≤T. Thus, wt represents the UAV trajectory, which is to be optimized. We assume that the initial and final locations of the UAV are predetermined, which are denoted as w0 and wF∈ℝ2×1, respectively. Furthermore, we assume that the maximum UAV speed and acceleration is Vmax and amax, respectively. Thus, the UAV trajectory must satisfy vt≤Vmax and at≤amax, where vt=w˙t and at=w¨t denotes the instantaneous velocity and acceleration, respectively.We assume that the channels between the UAV and the ground nodes are dominated by LoS links. Furthermore, we assume that the Doppler effect due to the UAV mobility can be perfectly compensated. Thus, the channel coefficient from the ground terminalUk to the UAV at time t can then be expressed as(1)hkt=β0dk−2t=β0H2+qk−wt2,k=1,…,K,where β0 denotes the channel gain at the reference distance d0=1 meter, and dkt=H2+qk−wt2 represents the distance between ground node Uk and the UAV. Denote by B the total bandwidth assigned for the uplink data collection system, which is assumed to be dynamically allocated to the K ground terminals for orthogonal multiple access. Specifically, denote by 0≤αkt≤1 the fractional of the spectrum bandwidth that is assigned to Uk at time t. Note that, in practical implementation, αkt is determined by the number of subbands allocated for Uk normalized by the total number of frequency subbands, which has discrete values in general. However, we assume that the number of subbands is sufficiently large so that αkt can be approximated to have continuous values between 0 and 1 for simplicity. Denote by Pkt the transmit power of Uk at time t. Then, the maximum transmission rate for the uplink from Uk to the UAV can be expressed as(2)Rkt=αktBlog21+PkthktαktBN0=αktBlog21+Pktγ0αktH2+qk−wt2,where N0 is the noise power spectrum density in Watts/Hz, and γ0≜β0/BN0 represents the reference SNR. It is observed from (2) that the data collection rate for Uk is a function of αkt,Pkt, as well as the UAV trajectory wt. The aggregated transmission throughput over the time horizon T for Uk can be presented as(3)QkT,αkt,Pkt,wt=∫0TRktdt=∫0TαktBlog21+Pktγ0αktH2+qk−wt2dt,where the total rate Qk of each ground terminal Uk should be larger than the data collection task Q^k: Qk≥Q^k.There are two parts of energy consumption in the UAV-enabled data collection system:(1)
Ground Terminal Energy Consumption. The total energy consumption EGT for ground terminals can be written as(4)EGTT,Pkt=∑k=1K∫0TPktdt.(2)
UAV Energy Consumption. The UAV energy consumption of the considered data collection system consists of two main components. The first one is the energy consumption related to the communication functions, such as circuitry and signal processing. The other component is the propulsion energy consumption, which is required for the UAV to remain aloft as well as for supporting its mobility. In practice, the communication-related energy is much smaller than the propulsion energy and hence is neglected in this paper.For fixed-wing UAVs, the total propulsion energyE¯wt as a function of the trajectory wt can be modelled as [21](5)E¯T,wt=∫0Tc1vt3+c2vt1+at2−aTtvt2/vt2g2dt+12mvT2−v02,where c1 and c2 are the parameters depending on the aircraft’s weight, wing area, air density, etc, m is the mass of the aircraft including all it payload, and g denotes the gravitational acceleration with nominal value 9.8m/s2, and vt and at are the instantaneous UAV velocity and acceleration vectors, respectively, which are related to its trajectory wt as(6)vt≜w˙t,at≜v˙t.The energy consumptionEUAV for UAV can be expressed as(7)EUAV=E¯T,wt.Note that the achievable data rate for each ground terminal is a function of total operating timeT, spectrum, and power allocation αt,Pkt, as well as UAV trajectory wt. Denote by S the set of strategies in terms of the resource allocations and UAV trajectories such that the data collection requirement R^k can be fulfilled. The set can be expressed as(8)S≜T,Pkt,αkt,wt∣QkT,Pkt,αkt,wt≥Q^k,k=1,…,K.Consider the data collection system which both ground terminals and UAV would consume energy to support the data transmission and UAV flying. There are two parts of energy consumption: (1) ground terminal energyEGT and (2) UAV energy EUAV. It is seen that the optimal strategies for minimizing the transmitting power of ground terminals and UAV energy consumption for flying are in general different. For data transmission, UAV would be slowly flying when it is near to the ground terminals. On the other hand, for UAV’ flying, the steady level flight would be a better choice for energy decreasing. It thus motivates our investigation of the following question: what are the optimal UAV flying trajectory strategies for data transmission and UAV flight energy consumption? To answer this question, we propose to use ground terminal-UAV (G-U) region for the energy consumption model to characterize all the ground terminal transmit power and UAV energy consumption pairs under a given data collection rate constraint. We define the feasible energy region to be the set of all energy pairs of ground terminal and UAV that can be achieved using the wireless resource and trajectory vector s∈S that satisfy the rate constraint. It can be presented as(9)ε≜∪s∈SEGTs,EUAVs.The outer boundary of this region is called thePareto boundary, because it consists of operating points EGT,EUAV for which it is impossible to decrease one of the energies, without simultaneously increasing one of the other energies. More precisely, we define the Pareto optimality of an operating point as follows:Definition 1.
An energy pairEGT,EUAV is Pareto optimal if there is no other energy pair UGT,UUAV with QGT,QUAV≤EGT,EUAV and UGT,UUAV≠EGT,EUAV (the inequality is component-wise) can meet the rate constraints for the data collection system.The Pareto boundary of the energy region characterizes that the minimum energy consumption for UAV and ground terminal for data collection task. It can be adopted to evaluate the trade-off of the energy consumption in the data collection system. It is an interesting topic to investigate the UAV trajectory strategy and resource allocation scheme for UAV and ground terminals to finish the data collection task cooperatively.


## 2.1. System Model

We consider a wireless system consisting ofK ground nodes, denoted as U1,…,Uk, where the coordinate of Uk is denoted as qk=xk,ykT. We assume that each of the ground node Uk periodically generates data of size R^k for each period of duration Ts, which need to be regularly uploaded to the fusion center for data processing. This could correspond to the practical periodic sensing applications. We assume that there is no established communication link between the ground nodes and fusion center due to their long separation distance as well as the high cost in deploying fixed communication infrastructure such as relays. Instead, we assume that a high-mobile UAV is despatched regularly to fly over the ground nodes for data collection and then brings it back to the fusion center for off-line processing.We assume that the UAV flying at a fixed altitudeH around the ground terminals for data collection for a finite time horizon T. Note that T is the time required for the UAV to complete the data collection task R^k for each period Ts. In practice, we usually have T≪Ts (e.g., dozens of minutes versus several days) since the data are only generated intermittently. We denote the time-varying coordinate of the UAV’s horizontal location as wt=xt,ytT, 0≤t≤T. Thus, wt represents the UAV trajectory, which is to be optimized. We assume that the initial and final locations of the UAV are predetermined, which are denoted as w0 and wF∈ℝ2×1, respectively. Furthermore, we assume that the maximum UAV speed and acceleration is Vmax and amax, respectively. Thus, the UAV trajectory must satisfy vt≤Vmax and at≤amax, where vt=w˙t and at=w¨t denotes the instantaneous velocity and acceleration, respectively.We assume that the channels between the UAV and the ground nodes are dominated by LoS links. Furthermore, we assume that the Doppler effect due to the UAV mobility can be perfectly compensated. Thus, the channel coefficient from the ground terminalUk to the UAV at time t can then be expressed as(1)hkt=β0dk−2t=β0H2+qk−wt2,k=1,…,K,where β0 denotes the channel gain at the reference distance d0=1 meter, and dkt=H2+qk−wt2 represents the distance between ground node Uk and the UAV. Denote by B the total bandwidth assigned for the uplink data collection system, which is assumed to be dynamically allocated to the K ground terminals for orthogonal multiple access. Specifically, denote by 0≤αkt≤1 the fractional of the spectrum bandwidth that is assigned to Uk at time t. Note that, in practical implementation, αkt is determined by the number of subbands allocated for Uk normalized by the total number of frequency subbands, which has discrete values in general. However, we assume that the number of subbands is sufficiently large so that αkt can be approximated to have continuous values between 0 and 1 for simplicity. Denote by Pkt the transmit power of Uk at time t. Then, the maximum transmission rate for the uplink from Uk to the UAV can be expressed as(2)Rkt=αktBlog21+PkthktαktBN0=αktBlog21+Pktγ0αktH2+qk−wt2,where N0 is the noise power spectrum density in Watts/Hz, and γ0≜β0/BN0 represents the reference SNR. It is observed from (2) that the data collection rate for Uk is a function of αkt,Pkt, as well as the UAV trajectory wt. The aggregated transmission throughput over the time horizon T for Uk can be presented as(3)QkT,αkt,Pkt,wt=∫0TRktdt=∫0TαktBlog21+Pktγ0αktH2+qk−wt2dt,where the total rate Qk of each ground terminal Uk should be larger than the data collection task Q^k: Qk≥Q^k.There are two parts of energy consumption in the UAV-enabled data collection system:(1)
Ground Terminal Energy Consumption. The total energy consumption EGT for ground terminals can be written as(4)EGTT,Pkt=∑k=1K∫0TPktdt.(2)
UAV Energy Consumption. The UAV energy consumption of the considered data collection system consists of two main components. The first one is the energy consumption related to the communication functions, such as circuitry and signal processing. The other component is the propulsion energy consumption, which is required for the UAV to remain aloft as well as for supporting its mobility. In practice, the communication-related energy is much smaller than the propulsion energy and hence is neglected in this paper.For fixed-wing UAVs, the total propulsion energyE¯wt as a function of the trajectory wt can be modelled as [21](5)E¯T,wt=∫0Tc1vt3+c2vt1+at2−aTtvt2/vt2g2dt+12mvT2−v02,where c1 and c2 are the parameters depending on the aircraft’s weight, wing area, air density, etc, m is the mass of the aircraft including all it payload, and g denotes the gravitational acceleration with nominal value 9.8m/s2, and vt and at are the instantaneous UAV velocity and acceleration vectors, respectively, which are related to its trajectory wt as(6)vt≜w˙t,at≜v˙t.The energy consumptionEUAV for UAV can be expressed as(7)EUAV=E¯T,wt.Note that the achievable data rate for each ground terminal is a function of total operating timeT, spectrum, and power allocation αt,Pkt, as well as UAV trajectory wt. Denote by S the set of strategies in terms of the resource allocations and UAV trajectories such that the data collection requirement R^k can be fulfilled. The set can be expressed as(8)S≜T,Pkt,αkt,wt∣QkT,Pkt,αkt,wt≥Q^k,k=1,…,K.Consider the data collection system which both ground terminals and UAV would consume energy to support the data transmission and UAV flying. There are two parts of energy consumption: (1) ground terminal energyEGT and (2) UAV energy EUAV. It is seen that the optimal strategies for minimizing the transmitting power of ground terminals and UAV energy consumption for flying are in general different. For data transmission, UAV would be slowly flying when it is near to the ground terminals. On the other hand, for UAV’ flying, the steady level flight would be a better choice for energy decreasing. It thus motivates our investigation of the following question: what are the optimal UAV flying trajectory strategies for data transmission and UAV flight energy consumption? To answer this question, we propose to use ground terminal-UAV (G-U) region for the energy consumption model to characterize all the ground terminal transmit power and UAV energy consumption pairs under a given data collection rate constraint. We define the feasible energy region to be the set of all energy pairs of ground terminal and UAV that can be achieved using the wireless resource and trajectory vector s∈S that satisfy the rate constraint. It can be presented as(9)ε≜∪s∈SEGTs,EUAVs.The outer boundary of this region is called thePareto boundary, because it consists of operating points EGT,EUAV for which it is impossible to decrease one of the energies, without simultaneously increasing one of the other energies. More precisely, we define the Pareto optimality of an operating point as follows:Definition 1.
An energy pairEGT,EUAV is Pareto optimal if there is no other energy pair UGT,UUAV with QGT,QUAV≤EGT,EUAV and UGT,UUAV≠EGT,EUAV (the inequality is component-wise) can meet the rate constraints for the data collection system.The Pareto boundary of the energy region characterizes that the minimum energy consumption for UAV and ground terminal for data collection task. It can be adopted to evaluate the trade-off of the energy consumption in the data collection system. It is an interesting topic to investigate the UAV trajectory strategy and resource allocation scheme for UAV and ground terminals to finish the data collection task cooperatively.


## 3. Multiple Ground Terminals with UAV Arbitrary Flight

In this section, we address the data collection system in a general scenario where there are multiple ground terminals which is served by a flexible flying UAV. We first formulate the optimization problem to describe the Pareto boundary of the energy region. Then, we investigate the optimal solution of the optimization problem for this scenario, from which we obtain an upper bound for the achievable energy consumption pairs in the G-U region. Then, we propose an alternating iterative method to derive the optimal resource allocation scheme and optimal trajectory design strategy.


### 3.1. Problem Formulation for Optimal Resource Allocation and Trajectory Design

In order to characterize the trade-off of the energy region effectively, we adopt the strategy to minimize the ground terminal energy consumption with fixed UAV energy consumption. By traversingEUAV, the Pareto boundary of G-U region can be obtained. In this case, the design objective for data collection system is to minimize the energy consumption for ground terminals with the fixed UAV energy consumption. The optimization problem can be formulated as(10)P2MinimizeT,wt,Pkt,αktEGT=∑k=1K∫0TPktdt,subject toCa1:R¯kαkt,Pkt,wt≥R^k,∀k,Ca2:E¯wt≤EUAV,Ca3:w0=w0,wT=wF,Ca4:v0=v0,vT=vF,Ca5:vt≤Vmax,∀t,Ca6:at≤amax,∀t,Ca7:∫0Tαktdt=1,0≤αkt≤1,∀k,t.The constraintCa1 is the data collection requirement for each ground node, which R^k denotes the total amount of data to be collected for Uk. Ca2 is the energy consumption constraint for UAV, with EUAV denoting the total available energy consumption for UAV. Ca3−Ca6 represent the UAV’s initial/final location and velocity constraints, respectively. It is noted that the amount of available energy for UAV is larger than the minimum energy consumption for UAV flying from the initial location to final location. Without considering the UAV’s energy consumption, the minimum transmit power for ground terminal is the situation that the UAV would be sequentially located above each ground terminal during the data collection time T. However, the optimal solution to the above problem is difficult to be directly solved.


### 3.2. Linear Discrete State-Space Approximation

Note that the problem (P2) is difficult to be directly solved since the trajectory wn is a continuous variable respect to the optimization problem and its first- and second-order derivatives. To tackle the problem more tractable, we utilize the linear discrete state-space approximation to reformulate the optimization problem (P2).For ease of exposition, the time horizonT is discreteized into N+2 equally spaced time slots with step δt, where δt is chosen to be sufficiently small so that the UAV location can be assumed to be approximately constant. Therefore, the UAV trajectory can be represented by the sequence wn. Moreover, vn and an are the instantaneous UAV velocity and acceleration vectors, respectively. Considering the relationship between wn and vn, wn and an are first- and second-order derivatives, respectively. Then, applying Taylor approximation, the velocity vn and acceleration vn are related to its trajectory wn as(11)vn+1=vn+anδt,wn+1=wn+vnδt+12anδt2.Correspondingly, the spectrum and power allocationαkt,pkt can be expressed as αkn,pkn for the discretization.For the problem (P2), the objective is to minimize the total ground node transmit power while satisfying the data collection requirements of all the ground terminals, subject to a fixed UAV energy consumption. It should jointly optimize the operation period N with fixed step size δt, the UAV trajectory wn, and spectrum and power allocation αkn,pkn. The problem (P2) can be reformulated as(12)P3MinimizeN,wn,Pkn,αknEGT=∑k=1K∑n=1NPkn,subject toCb1:R¯kαkn,Pkn,wn≥R^k,∀k,Cb2:E¯wn≤PUAV,Cb3:w0=w0,wN+1=wF,Cb4:wn+1=wn+vnδt+12anδt2,n=0,…,N,Cb5:v0=v0,vN+1=vF,Cb6:vn+1=vn+anδt,n=0,…,N,Cb7:vn≤Vmax,n=1,…,N,Cb8:an≤amax,n=0,…,N,Cb9:∑k=1Kαkn=1,0≤αkn≤1,∀k,n.The constraintCb1, Cb2, Cb9 are the discrete mode for the data collection requirement for each ground node, energy consumption constraint for UAV, and spectrum allocation constraint for ground terminals, respectively. Cb3 to Cb8 represent the UAV’s initial/final location and velocity constraints, respectively. It is noted that the amount of available energy for UAV is larger than the minimum energy consumption for UAV flying from the initial location to final location.Problem (13) is nonconvex; hence, it cannot be directly solved by standard convex optimization techniques. In the following sections, we propose an efficient algorithm to find an approximate solution to (13) via iteratively optimizing trajectory and resource optimizations.


### 3.3. Combining Optimal Trajectory Design and Resource Allocation Scheme for Multiuser UAV Network

In this section, an efficient algorithm that combines optimal trajectory design and resource allocation scheme is proposed to approximately solve the original optimization problem. The sequential convex optimization method is applied to meet the optimized goal by iteratively obtaining the optimal trajectory and allocating the wireless resource to the ground terminals.The original optimization problem can be classified into two subproblems: (1) wireless resource allocation issue for the multiple ground nodes and (2) the UAV trajectory optimization problem. To make the optimization problem more trackable, we propose to adopt the iteratively optimization method which assumes that one issue is determined when the other issue is considered to be optimized, and vice versa.


#### 3.3.1. Minimizing Energy Consumption for Constrained UAV Flight

Firstly, we should find a feasible solution for the UAV flight trajectory from the initial point to the final location by the predefined available energyPUAV. In other words, we should examine whether the UAV can finish the flight under the initial/finial location, velocity constraints within the N+2 operation time slots without considering any rate constraints of ground terminals. The optimization problem can be formulated as(13)P3.1MinimizewnEUAV=E¯wn,subject toCc1:w0=w0,wN+1=wF,Cc2:wn+1=wn+vnδt+12anδt2,n=0,…,N,Cc3:v0=v0,vN+1=vF,Cc4:vn+1=vn+anδt,n=0,…,N,Cc5:vn≤Vmax,n=1,…,N,Cc6:an≤amax,n=0,…,N.It is noted that the constraintsCc1−Cc6 are convex sets. However, the objective function is nonconvex. The problem cannot be directly solved with the standard convex optimization techniques. We should adopt some relaxation method to construct the standard convex form and solve the problem (P3.1) efficiently.The UAV energy consumption of the objective function can be upper-bounded by the following equation:(14)E¯wn≤∑n=1Nc1vn3+c2vn1+a2g2δt+ΔK≜E¯ubwn,where ΔK≜1/2mvN+12−v02 denotes the amount of the UAV’s kinetic energy variation, which would be determined as a constant value by the initial and final velocity constraints Cc3. It is noted that the energy consumption upper bound is tight for the circular flight mode, in which case anvn=0. Therefore, the objective function can be approximately formulated as(15)P3.1.1MinimizeE¯ubwn.Considering the function is still a nonconvex set for the variablevn, we propose to introduce a slack variable ξn to reformulate the objective function as(16)P3.1.2MinimizeE¯ubvn,ξn=∑n=1Nc1vn3+c2ξn1+a2g2δt+ΔK,subject toCc1−Cc6,Cc7:vn2≥ξn2.It can be shown that we must haveξn=vn,∀n, for all n $ at the optimal solution for (P3.1.2), since otherwise one can always increase ξn and decrease vn when the UAV near the ground terminal to decrease the objective function value and obtain a strictly lower energy consumption. Until now, the objective is a convex with respect to vn,anξn, but with a new nonconvex constraint Cc7. Similarly, to tackle the nonconvexity of the constraint, a local convex approximation is adopted to tackle this issue. For any given local point vjn, we have the following expression by applying the first-order Taylor expansion:(17)vn≥vjn+2vjTnvn−vjn≜φlbvn,where the equality holds at the point vn=vjn. The function φlbvn is a linear function. Then, the new constraint is a convex set, which can be expressed as(18)Cc7lb:φlbvn≥ξn2,∀n.Then, the inequality in first-order Taylor expansion shows that the new constructed convex constraintCc7lb always implies the nonconvex constraint Cc7, but the reverse is not true in general.Then, the optimization problem (P3.1) can be reformulated as(19)P3.1.3MinimizeE¯ubvn,ξn=∑n=1Nc1vn3+c2ξn1+a2g2δt+ΔKsubject toCc1−Cc6,Cc7lb:φlbvn≥ξn2,∀n.Based on the previous discussions, the optimal solution of (P3.1.3) is the upper bound to that of problem (P3.1). Fortunately, the optimization problem (P3.1.3) is a standard convex optimization problem with the convex objective function with all convex constraints. It can be solved efficiently via the bisection method or the standard Dinkelbach’s algorithm.


#### 3.3.2. Optimal Resource Allocation with Fixed Trajectory

For the wireless resource allocation issue, it is proposed to minimize the ground nodes transmit power under the fixed UAV trajectoryw∗n assumption. Then, the optimization problem for wireless resource allocation can be formulated as(20)P3.2MinimizePkn,αkn∑k=1K∑n=1NPkn,subject toCd1:R¯kαkn,Pkn,w∗n≥R^k,∀k,Cd2:∑k=1Kαkn≤1,0≤αkn≤1,∀k,n.This subproblem may correspond to the practical scenario when the UAV’s trajectory is predetermined due to other tasks (e.g., surveillance) rather than data collection. In this case, the optimal solution of the subproblem (P3.2) can minimize the transmit power of the ground nodes and extend the life time of the node.Since the trajectoryw∗n is fixed, the constraint Cd1 is a convex set combined with respect to Pkn,αkn. It can be verified that the subproblem (P3.2) satisfied the Slater’s condition. Using the dual Lagrangian method, the optimal power allocation Pk∗n can be expressed as(21)Pk∗n=λkBδtln2−1γk∗n+αk∗n,where γk∗n=γ0/H2+qk−w∗n2, λk is the Lagrange multiplier (or dual variable) associated with the constraint.∑
n
=
1
N
R
k
P
k
n
,
α
k
n
,
w
∗
n
≥
R
^
k; αk∗n is the optimal frequency band allocation factor. This is one instance of the water-filling solution to the optimal power allocation.Substitute the optimalPk∗n in the equation, the optimal frequency band allocation factor αk∗n can be obtained as equation (22):(22)αk∗n=1,ifλkBδtln2−1γk∗n+−Bδtλklog21+λkBδtγk∗nln2−1++μn<0,ak∗,ifλkBδtln2−1γk∗n+−Bδtλklog21+λkBδtγk∗nln2−1++μn=0,0,otherwise,where μn is the Lagrange multiplier (or dual variable) associated with the constraint ∑k=1Kαkn≤1; ak∗ can be any real number between 0 and 1, which can be calculated by satisfying the constraints Ca1 and Ca2. Generally, the optimal solution for αkn is binary solution if the amount of time slot n is large enough. Otherwise, ak∗ is adopted to fine-tune the resource allocation solution to meet the constraint.It is proposed to adopt an iterative subgradient method (Algorithm1) to optimize the dual variable λk,μn: the subgradient for λk of ground node k is given by gk=R^k−∑n=1NRk∗n and for μn of each time slot is given by tn=∑k=1Kαkn−1. The update procedure of Lagrangian dual variables are performed as(23)λkl=maxλkl−1+βlgk,0,μnl=maxμnl−1+θltn,0,where βl,θl are the step size for the iterative search process. Several step size rules have been proven to guarantee convergence under some general conditions.Algorithm 1:Iterative subgradient method for (P3.2).
(1)
Initializeλkl,μnl. Let l=0
(2)
repeat
(3)
Obtain the optimal powerPk∗n and αk∗n from the equations (21) and (22).
(4)
Get the subgradientgk and tn for all n
(5)
Update the dual variable according the equation (23) for all n.
(6)
Updatel=l+1.
(7)
Until Converges to a prescribed accuracy.The optimal solution includes two steps: (1) each of subproblem in slotn can be solved with fixed Lagrangian multipliers using the combinatorial method, (2) the convergency updates of Lagrangian multipliers are performed to meet the constraints. For the optimal dual variables optimization, it can also adopt the ellipsoid method to find the optimal solution. Our proposed procedure above is convenient for the transceiver processing for both UAV and ground nodes.


#### 3.3.3. UAV Trajectory Optimization with Fixed Resource Allocation

Since the ground node has been allocated with fixed frequency band and power resource, we should adopt a dual problem to achieve the optimization goal by optimizing the UAV trajectory. In this section, we consider the issue to maximize the total rate of ground nodes by optimizing the UAV’s trajectory with fixed frequency band and power allocation. It is noted that maximizing the total rate of ground nodes can minimize the total energy consumption of ground nodes with the rate constraints. They are dual problems with each other. The optimization subproblem (P3.3) can be formulated as(24)P3.3Maximizewn∑k=1KR¯kαk∗n,Pk∗n,wn,subject toCe1:R¯kαk∗n,Pk∗n,wn≥R^k,∀k,Ce2:w0=w0,wN+1=wF,Ce3:wn+1=wn+vnδt+12anδt2,n=0,…,N,Ce4:v0=v0,vN+1=vF,Ce5:vn+1=vn+anδt,n=0,…,N,Ce6:vn≤Vmax,n=1,…,N,Ce7:an≤amax,n=0,…,N,Ce8:E¯wn≤PUAV.It is noted that the constraintsCe2−Ce7 are convex sets. However, the constraint Ce1 and Ce8 are nonconvex, and the objective function is nonconvex neither. The problem cannot be directly solved with the standard convex optimization techniques. We should adopt some relaxation method to construct the standard convex form and solve the problem (P3.3) efficiently.Firstly, to tackle the nonconvexity of the objective function, for any local pointwjn, define function R¯k,lbwn for each ground node as(25)R¯k,lbwn=Bδt∑n=1N−1ηj,kn−ψj,knqk−wn2−qk−wjn2,where(26)ηj,kn=αk∗nlog21+Pk∗nγ0αk∗nH2+qk−wn2,ψj,kn=log2ePk∗nγ0αk∗nH2+qk−wjn2+Pk∗nγ0H2+qk−wjn2.Note thatR¯k,lbwn is a concave function with respect to wn. Then the upper contour set R¯k,lbwn≥R^k is convex set. Moreover, as mentioned in [21], R¯kwn≥R¯k,lbwn holds true for any given wjn. The lower bound equation is the first order Taylor expansion of a convex differential function which is its global underestimator. Both R¯kwn and R¯k,lbwn have an identical gradient.Therefore, the optimization problem (P3.3) can be approximately solved by maximizing the lower bound as(27)P3.3.1Maximizewn∑k=1KR¯k,lbαk∗n,Pk∗n,wn,subject toCe1lb:R¯k,lbαk∗n,Pk∗n,wn≥R^k,∀k,Ce2−Ce7:Ce8:E¯wn≤PUAV,where the constraint of Ce1 is reformulated as a convex set Ce1lb.Secondly, considering the constraint set is still a nonconvex set for the variablevn. Just like the approximation method as in minimizing energy consumption for constrained UAV flight, we propose to introduce a slack variable ξn to reformulate the constraint Ce8 as(28)Ce8≜Cf8ub:E¯ubvn,ξn=∑n=1Nc1vn3+c2ξn1+a2g2δt+ΔK,Ce9:φlbvn≥ξn2,∀n.Then, all the constraints are convex set. Until now, we reformulate the optimization problem for any given local pointwjn,vjn, and it can be written as:(29)P3.3.2Maximizewn∑k=1KR¯k,lbαk∗n,Pk∗n,wn,subject toCe1lb:R¯k,lbαk∗n,Pk∗n,wn≥R^k,∀k,Ce2−Ce7:Ce8ub:E¯ubwn≤PUAV,Ce8ub:E¯ubwn≤PUAV,Ce9lb:φlbvn≥ξn2,∀n,Ce10:ξn≥0,∀n.Based on the previous discussions, the optimal solution of (P3.3.2) is the lower bound to that of problem (P3.3). Fortunately, the optimization problem (P3.3.2) is a standard convex optimization problem with the convex objective function with all convex constraints. It can be solved efficiently via the bisection method or the standard Dinkelbach’s algorithm. Then, the nonconvex problem (P3.3) can be solved by iteratively optimization (P3.3.2) with local point updated in each iteration. It can be summarized as the following table (Algorithm 2).Algorithm 2:Sequential convex optimization for (P3.3).
(1)
Initializew0n,v0n. Let j=0
(2)
repeat
(3)
Solve problem (P3.3.2) under the given local point wjn,vjn, and obtain the optimal solution as wj∗n,vj∗n.
(4)
Update the local pointwj+1n=wj∗n,vj+1n=vj∗n,∀n.
(5)
Updatej=j+1.
(6)
Until Converges to a prescribed accuracyIn summary, through adopting the relaxation method and sequential convex optimization technique, an efficient solution is proposed to solve the UAV trajectory optimization problem which is guaranteed that the optimal point is fulfill the Karush–Kuhn–Tucker conditions of the original nonconvex problem (P3.3).


#### 3.3.4. Iterative Method for Optimal Resource Allocation and UAV Trajectory Design

Until now, we have solved the issues of UAV trajectory optimal design and resource allocation for ground terminals when one of them is fixed. In order to obtain the optimal solution for the original optimization problem (P3), we propose an alternate iterative solution to optimize the UAV trajectory and resource allocation, based on the methods mentioned in Sections 3.3.1.–3.3.3.The proposed optimal solution can be summarized as follows (Algorithm3).Algorithm 3:Alternate iterative solution for original optimization problem (P3).
(1)
Feasible solution check: Solve the problem (P3.1) to calculate the minimum energy consumption PUAVmin for UAV flight from initial point to final location.
If PUAVmin≤PUAV;
Set: The initial UAV trajectory with minimum energy consumption as w0Fixn,v0Fixn.
Letl=0;
Go toStep 2;
Otherwise, There is no feasible solution, End
(2)
repeat
(3)
Solve problem (P3.2) under the fixed trajectory wlFixn,vlFixn by Algorithm 1, and obtain the optimal resource allocation solution as αk,l∗n,Pk,l∗n,∀n .
(4)
Update the fixed resource allocation solutionαk,lFixn=αk,l∗n,Pk,lFixn=Pk,l∗n;
(5)
Solve problem (P3.3) under the fixed resource allocation αk,lFixn,Pk,lFixn by Algorithm 2, and obtain the optimal UAV trajectory as wg,l∗n,vg,l∗n,∀n
(6)
Update the fixed UAV trajectorywl+1Fixn=wg,l∗n,vl+1Fixn=vg,l∗n,∀n
(7)
Update l=l+1.
(8)
Until Converges to a prescribed accuracyNote that the solution for problem (P3.2) adopts an iterative subgradient method in Algorithm 1 whose complexity is OlN where l is the iteration time. As Algorithm 2 requires to solve convex optimization problems, it has a polynomial complexity in the worst case each iteration [27]. Thus, the complexity of Algorithm 3 combining Algorithms 1 and 2 is the polynomial complexity because polynomial complexity multiplied by iterations is still polynomial complexity which is affordable.


## 3.1. Problem Formulation for Optimal Resource Allocation and Trajectory Design

In order to characterize the trade-off of the energy region effectively, we adopt the strategy to minimize the ground terminal energy consumption with fixed UAV energy consumption. By traversingEUAV, the Pareto boundary of G-U region can be obtained. In this case, the design objective for data collection system is to minimize the energy consumption for ground terminals with the fixed UAV energy consumption. The optimization problem can be formulated as(10)P2MinimizeT,wt,Pkt,αktEGT=∑k=1K∫0TPktdt,subject toCa1:R¯kαkt,Pkt,wt≥R^k,∀k,Ca2:E¯wt≤EUAV,Ca3:w0=w0,wT=wF,Ca4:v0=v0,vT=vF,Ca5:vt≤Vmax,∀t,Ca6:at≤amax,∀t,Ca7:∫0Tαktdt=1,0≤αkt≤1,∀k,t.The constraintCa1 is the data collection requirement for each ground node, which R^k denotes the total amount of data to be collected for Uk. Ca2 is the energy consumption constraint for UAV, with EUAV denoting the total available energy consumption for UAV. Ca3−Ca6 represent the UAV’s initial/final location and velocity constraints, respectively. It is noted that the amount of available energy for UAV is larger than the minimum energy consumption for UAV flying from the initial location to final location. Without considering the UAV’s energy consumption, the minimum transmit power for ground terminal is the situation that the UAV would be sequentially located above each ground terminal during the data collection time T. However, the optimal solution to the above problem is difficult to be directly solved.


## 3.2. Linear Discrete State-Space Approximation

Note that the problem (P2) is difficult to be directly solved since the trajectory wn is a continuous variable respect to the optimization problem and its first- and second-order derivatives. To tackle the problem more tractable, we utilize the linear discrete state-space approximation to reformulate the optimization problem (P2).For ease of exposition, the time horizonT is discreteized into N+2 equally spaced time slots with step δt, where δt is chosen to be sufficiently small so that the UAV location can be assumed to be approximately constant. Therefore, the UAV trajectory can be represented by the sequence wn. Moreover, vn and an are the instantaneous UAV velocity and acceleration vectors, respectively. Considering the relationship between wn and vn, wn and an are first- and second-order derivatives, respectively. Then, applying Taylor approximation, the velocity vn and acceleration vn are related to its trajectory wn as(11)vn+1=vn+anδt,wn+1=wn+vnδt+12anδt2.Correspondingly, the spectrum and power allocationαkt,pkt can be expressed as αkn,pkn for the discretization.For the problem (P2), the objective is to minimize the total ground node transmit power while satisfying the data collection requirements of all the ground terminals, subject to a fixed UAV energy consumption. It should jointly optimize the operation period N with fixed step size δt, the UAV trajectory wn, and spectrum and power allocation αkn,pkn. The problem (P2) can be reformulated as(12)P3MinimizeN,wn,Pkn,αknEGT=∑k=1K∑n=1NPkn,subject toCb1:R¯kαkn,Pkn,wn≥R^k,∀k,Cb2:E¯wn≤PUAV,Cb3:w0=w0,wN+1=wF,Cb4:wn+1=wn+vnδt+12anδt2,n=0,…,N,Cb5:v0=v0,vN+1=vF,Cb6:vn+1=vn+anδt,n=0,…,N,Cb7:vn≤Vmax,n=1,…,N,Cb8:an≤amax,n=0,…,N,Cb9:∑k=1Kαkn=1,0≤αkn≤1,∀k,n.The constraintCb1, Cb2, Cb9 are the discrete mode for the data collection requirement for each ground node, energy consumption constraint for UAV, and spectrum allocation constraint for ground terminals, respectively. Cb3 to Cb8 represent the UAV’s initial/final location and velocity constraints, respectively. It is noted that the amount of available energy for UAV is larger than the minimum energy consumption for UAV flying from the initial location to final location.Problem (13) is nonconvex; hence, it cannot be directly solved by standard convex optimization techniques. In the following sections, we propose an efficient algorithm to find an approximate solution to (13) via iteratively optimizing trajectory and resource optimizations.


## 3.3. Combining Optimal Trajectory Design and Resource Allocation Scheme for Multiuser UAV Network

In this section, an efficient algorithm that combines optimal trajectory design and resource allocation scheme is proposed to approximately solve the original optimization problem. The sequential convex optimization method is applied to meet the optimized goal by iteratively obtaining the optimal trajectory and allocating the wireless resource to the ground terminals.The original optimization problem can be classified into two subproblems: (1) wireless resource allocation issue for the multiple ground nodes and (2) the UAV trajectory optimization problem. To make the optimization problem more trackable, we propose to adopt the iteratively optimization method which assumes that one issue is determined when the other issue is considered to be optimized, and vice versa.


### 3.3.1. Minimizing Energy Consumption for Constrained UAV Flight

Firstly, we should find a feasible solution for the UAV flight trajectory from the initial point to the final location by the predefined available energyPUAV. In other words, we should examine whether the UAV can finish the flight under the initial/finial location, velocity constraints within the N+2 operation time slots without considering any rate constraints of ground terminals. The optimization problem can be formulated as(13)P3.1MinimizewnEUAV=E¯wn,subject toCc1:w0=w0,wN+1=wF,Cc2:wn+1=wn+vnδt+12anδt2,n=0,…,N,Cc3:v0=v0,vN+1=vF,Cc4:vn+1=vn+anδt,n=0,…,N,Cc5:vn≤Vmax,n=1,…,N,Cc6:an≤amax,n=0,…,N.It is noted that the constraintsCc1−Cc6 are convex sets. However, the objective function is nonconvex. The problem cannot be directly solved with the standard convex optimization techniques. We should adopt some relaxation method to construct the standard convex form and solve the problem (P3.1) efficiently.The UAV energy consumption of the objective function can be upper-bounded by the following equation:(14)E¯wn≤∑n=1Nc1vn3+c2vn1+a2g2δt+ΔK≜E¯ubwn,where ΔK≜1/2mvN+12−v02 denotes the amount of the UAV’s kinetic energy variation, which would be determined as a constant value by the initial and final velocity constraints Cc3. It is noted that the energy consumption upper bound is tight for the circular flight mode, in which case anvn=0. Therefore, the objective function can be approximately formulated as(15)P3.1.1MinimizeE¯ubwn.Considering the function is still a nonconvex set for the variablevn, we propose to introduce a slack variable ξn to reformulate the objective function as(16)P3.1.2MinimizeE¯ubvn,ξn=∑n=1Nc1vn3+c2ξn1+a2g2δt+ΔK,subject toCc1−Cc6,Cc7:vn2≥ξn2.It can be shown that we must haveξn=vn,∀n, for all n $ at the optimal solution for (P3.1.2), since otherwise one can always increase ξn and decrease vn when the UAV near the ground terminal to decrease the objective function value and obtain a strictly lower energy consumption. Until now, the objective is a convex with respect to vn,anξn, but with a new nonconvex constraint Cc7. Similarly, to tackle the nonconvexity of the constraint, a local convex approximation is adopted to tackle this issue. For any given local point vjn, we have the following expression by applying the first-order Taylor expansion:(17)vn≥vjn+2vjTnvn−vjn≜φlbvn,where the equality holds at the point vn=vjn. The function φlbvn is a linear function. Then, the new constraint is a convex set, which can be expressed as(18)Cc7lb:φlbvn≥ξn2,∀n.Then, the inequality in first-order Taylor expansion shows that the new constructed convex constraintCc7lb always implies the nonconvex constraint Cc7, but the reverse is not true in general.Then, the optimization problem (P3.1) can be reformulated as(19)P3.1.3MinimizeE¯ubvn,ξn=∑n=1Nc1vn3+c2ξn1+a2g2δt+ΔKsubject toCc1−Cc6,Cc7lb:φlbvn≥ξn2,∀n.Based on the previous discussions, the optimal solution of (P3.1.3) is the upper bound to that of problem (P3.1). Fortunately, the optimization problem (P3.1.3) is a standard convex optimization problem with the convex objective function with all convex constraints. It can be solved efficiently via the bisection method or the standard Dinkelbach’s algorithm.


### 3.3.2. Optimal Resource Allocation with Fixed Trajectory

For the wireless resource allocation issue, it is proposed to minimize the ground nodes transmit power under the fixed UAV trajectoryw∗n assumption. Then, the optimization problem for wireless resource allocation can be formulated as(20)P3.2MinimizePkn,αkn∑k=1K∑n=1NPkn,subject toCd1:R¯kαkn,Pkn,w∗n≥R^k,∀k,Cd2:∑k=1Kαkn≤1,0≤αkn≤1,∀k,n.This subproblem may correspond to the practical scenario when the UAV’s trajectory is predetermined due to other tasks (e.g., surveillance) rather than data collection. In this case, the optimal solution of the subproblem (P3.2) can minimize the transmit power of the ground nodes and extend the life time of the node.Since the trajectoryw∗n is fixed, the constraint Cd1 is a convex set combined with respect to Pkn,αkn. It can be verified that the subproblem (P3.2) satisfied the Slater’s condition. Using the dual Lagrangian method, the optimal power allocation Pk∗n can be expressed as(21)Pk∗n=λkBδtln2−1γk∗n+αk∗n,where γk∗n=γ0/H2+qk−w∗n2, λk is the Lagrange multiplier (or dual variable) associated with the constraint.∑
n
=
1
N
R
k
P
k
n
,
α
k
n
,
w
∗
n
≥
R
^
k; αk∗n is the optimal frequency band allocation factor. This is one instance of the water-filling solution to the optimal power allocation.Substitute the optimalPk∗n in the equation, the optimal frequency band allocation factor αk∗n can be obtained as equation (22):(22)αk∗n=1,ifλkBδtln2−1γk∗n+−Bδtλklog21+λkBδtγk∗nln2−1++μn<0,ak∗,ifλkBδtln2−1γk∗n+−Bδtλklog21+λkBδtγk∗nln2−1++μn=0,0,otherwise,where μn is the Lagrange multiplier (or dual variable) associated with the constraint ∑k=1Kαkn≤1; ak∗ can be any real number between 0 and 1, which can be calculated by satisfying the constraints Ca1 and Ca2. Generally, the optimal solution for αkn is binary solution if the amount of time slot n is large enough. Otherwise, ak∗ is adopted to fine-tune the resource allocation solution to meet the constraint.It is proposed to adopt an iterative subgradient method (Algorithm1) to optimize the dual variable λk,μn: the subgradient for λk of ground node k is given by gk=R^k−∑n=1NRk∗n and for μn of each time slot is given by tn=∑k=1Kαkn−1. The update procedure of Lagrangian dual variables are performed as(23)λkl=maxλkl−1+βlgk,0,μnl=maxμnl−1+θltn,0,where βl,θl are the step size for the iterative search process. Several step size rules have been proven to guarantee convergence under some general conditions.Algorithm 1:Iterative subgradient method for (P3.2).
(1)
Initializeλkl,μnl. Let l=0
(2)
repeat
(3)
Obtain the optimal powerPk∗n and αk∗n from the equations (21) and (22).
(4)
Get the subgradientgk and tn for all n
(5)
Update the dual variable according the equation (23) for all n.
(6)
Updatel=l+1.
(7)
Until Converges to a prescribed accuracy.The optimal solution includes two steps: (1) each of subproblem in slotn can be solved with fixed Lagrangian multipliers using the combinatorial method, (2) the convergency updates of Lagrangian multipliers are performed to meet the constraints. For the optimal dual variables optimization, it can also adopt the ellipsoid method to find the optimal solution. Our proposed procedure above is convenient for the transceiver processing for both UAV and ground nodes.


### 3.3.3. UAV Trajectory Optimization with Fixed Resource Allocation

Since the ground node has been allocated with fixed frequency band and power resource, we should adopt a dual problem to achieve the optimization goal by optimizing the UAV trajectory. In this section, we consider the issue to maximize the total rate of ground nodes by optimizing the UAV’s trajectory with fixed frequency band and power allocation. It is noted that maximizing the total rate of ground nodes can minimize the total energy consumption of ground nodes with the rate constraints. They are dual problems with each other. The optimization subproblem (P3.3) can be formulated as(24)P3.3Maximizewn∑k=1KR¯kαk∗n,Pk∗n,wn,subject toCe1:R¯kαk∗n,Pk∗n,wn≥R^k,∀k,Ce2:w0=w0,wN+1=wF,Ce3:wn+1=wn+vnδt+12anδt2,n=0,…,N,Ce4:v0=v0,vN+1=vF,Ce5:vn+1=vn+anδt,n=0,…,N,Ce6:vn≤Vmax,n=1,…,N,Ce7:an≤amax,n=0,…,N,Ce8:E¯wn≤PUAV.It is noted that the constraintsCe2−Ce7 are convex sets. However, the constraint Ce1 and Ce8 are nonconvex, and the objective function is nonconvex neither. The problem cannot be directly solved with the standard convex optimization techniques. We should adopt some relaxation method to construct the standard convex form and solve the problem (P3.3) efficiently.Firstly, to tackle the nonconvexity of the objective function, for any local pointwjn, define function R¯k,lbwn for each ground node as(25)R¯k,lbwn=Bδt∑n=1N−1ηj,kn−ψj,knqk−wn2−qk−wjn2,where(26)ηj,kn=αk∗nlog21+Pk∗nγ0αk∗nH2+qk−wn2,ψj,kn=log2ePk∗nγ0αk∗nH2+qk−wjn2+Pk∗nγ0H2+qk−wjn2.Note thatR¯k,lbwn is a concave function with respect to wn. Then the upper contour set R¯k,lbwn≥R^k is convex set. Moreover, as mentioned in [21], R¯kwn≥R¯k,lbwn holds true for any given wjn. The lower bound equation is the first order Taylor expansion of a convex differential function which is its global underestimator. Both R¯kwn and R¯k,lbwn have an identical gradient.Therefore, the optimization problem (P3.3) can be approximately solved by maximizing the lower bound as(27)P3.3.1Maximizewn∑k=1KR¯k,lbαk∗n,Pk∗n,wn,subject toCe1lb:R¯k,lbαk∗n,Pk∗n,wn≥R^k,∀k,Ce2−Ce7:Ce8:E¯wn≤PUAV,where the constraint of Ce1 is reformulated as a convex set Ce1lb.Secondly, considering the constraint set is still a nonconvex set for the variablevn. Just like the approximation method as in minimizing energy consumption for constrained UAV flight, we propose to introduce a slack variable ξn to reformulate the constraint Ce8 as(28)Ce8≜Cf8ub:E¯ubvn,ξn=∑n=1Nc1vn3+c2ξn1+a2g2δt+ΔK,Ce9:φlbvn≥ξn2,∀n.Then, all the constraints are convex set. Until now, we reformulate the optimization problem for any given local pointwjn,vjn, and it can be written as:(29)P3.3.2Maximizewn∑k=1KR¯k,lbαk∗n,Pk∗n,wn,subject toCe1lb:R¯k,lbαk∗n,Pk∗n,wn≥R^k,∀k,Ce2−Ce7:Ce8ub:E¯ubwn≤PUAV,Ce8ub:E¯ubwn≤PUAV,Ce9lb:φlbvn≥ξn2,∀n,Ce10:ξn≥0,∀n.Based on the previous discussions, the optimal solution of (P3.3.2) is the lower bound to that of problem (P3.3). Fortunately, the optimization problem (P3.3.2) is a standard convex optimization problem with the convex objective function with all convex constraints. It can be solved efficiently via the bisection method or the standard Dinkelbach’s algorithm. Then, the nonconvex problem (P3.3) can be solved by iteratively optimization (P3.3.2) with local point updated in each iteration. It can be summarized as the following table (Algorithm 2).Algorithm 2:Sequential convex optimization for (P3.3).
(1)
Initializew0n,v0n. Let j=0
(2)
repeat
(3)
Solve problem (P3.3.2) under the given local point wjn,vjn, and obtain the optimal solution as wj∗n,vj∗n.
(4)
Update the local pointwj+1n=wj∗n,vj+1n=vj∗n,∀n.
(5)
Updatej=j+1.
(6)
Until Converges to a prescribed accuracyIn summary, through adopting the relaxation method and sequential convex optimization technique, an efficient solution is proposed to solve the UAV trajectory optimization problem which is guaranteed that the optimal point is fulfill the Karush–Kuhn–Tucker conditions of the original nonconvex problem (P3.3).


### 3.3.4. Iterative Method for Optimal Resource Allocation and UAV Trajectory Design

Until now, we have solved the issues of UAV trajectory optimal design and resource allocation for ground terminals when one of them is fixed. In order to obtain the optimal solution for the original optimization problem (P3), we propose an alternate iterative solution to optimize the UAV trajectory and resource allocation, based on the methods mentioned in Sections 3.3.1.–3.3.3.The proposed optimal solution can be summarized as follows (Algorithm3).Algorithm 3:Alternate iterative solution for original optimization problem (P3).
(1)
Feasible solution check: Solve the problem (P3.1) to calculate the minimum energy consumption PUAVmin for UAV flight from initial point to final location.
If PUAVmin≤PUAV;
Set: The initial UAV trajectory with minimum energy consumption as w0Fixn,v0Fixn.
Letl=0;
Go toStep 2;
Otherwise, There is no feasible solution, End
(2)
repeat
(3)
Solve problem (P3.2) under the fixed trajectory wlFixn,vlFixn by Algorithm 1, and obtain the optimal resource allocation solution as αk,l∗n,Pk,l∗n,∀n .
(4)
Update the fixed resource allocation solutionαk,lFixn=αk,l∗n,Pk,lFixn=Pk,l∗n;
(5)
Solve problem (P3.3) under the fixed resource allocation αk,lFixn,Pk,lFixn by Algorithm 2, and obtain the optimal UAV trajectory as wg,l∗n,vg,l∗n,∀n
(6)
Update the fixed UAV trajectorywl+1Fixn=wg,l∗n,vl+1Fixn=vg,l∗n,∀n
(7)
Update l=l+1.
(8)
Until Converges to a prescribed accuracyNote that the solution for problem (P3.2) adopts an iterative subgradient method in Algorithm 1 whose complexity is OlN where l is the iteration time. As Algorithm 2 requires to solve convex optimization problems, it has a polynomial complexity in the worst case each iteration [27]. Thus, the complexity of Algorithm 3 combining Algorithms 1 and 2 is the polynomial complexity because polynomial complexity multiplied by iterations is still polynomial complexity which is affordable.


## 3.3.1. Minimizing Energy Consumption for Constrained UAV Flight

Firstly, we should find a feasible solution for the UAV flight trajectory from the initial point to the final location by the predefined available energyPUAV. In other words, we should examine whether the UAV can finish the flight under the initial/finial location, velocity constraints within the N+2 operation time slots without considering any rate constraints of ground terminals. The optimization problem can be formulated as(13)P3.1MinimizewnEUAV=E¯wn,subject toCc1:w0=w0,wN+1=wF,Cc2:wn+1=wn+vnδt+12anδt2,n=0,…,N,Cc3:v0=v0,vN+1=vF,Cc4:vn+1=vn+anδt,n=0,…,N,Cc5:vn≤Vmax,n=1,…,N,Cc6:an≤amax,n=0,…,N.It is noted that the constraintsCc1−Cc6 are convex sets. However, the objective function is nonconvex. The problem cannot be directly solved with the standard convex optimization techniques. We should adopt some relaxation method to construct the standard convex form and solve the problem (P3.1) efficiently.The UAV energy consumption of the objective function can be upper-bounded by the following equation:(14)E¯wn≤∑n=1Nc1vn3+c2vn1+a2g2δt+ΔK≜E¯ubwn,where ΔK≜1/2mvN+12−v02 denotes the amount of the UAV’s kinetic energy variation, which would be determined as a constant value by the initial and final velocity constraints Cc3. It is noted that the energy consumption upper bound is tight for the circular flight mode, in which case anvn=0. Therefore, the objective function can be approximately formulated as(15)P3.1.1MinimizeE¯ubwn.Considering the function is still a nonconvex set for the variablevn, we propose to introduce a slack variable ξn to reformulate the objective function as(16)P3.1.2MinimizeE¯ubvn,ξn=∑n=1Nc1vn3+c2ξn1+a2g2δt+ΔK,subject toCc1−Cc6,Cc7:vn2≥ξn2.It can be shown that we must haveξn=vn,∀n, for all n $ at the optimal solution for (P3.1.2), since otherwise one can always increase ξn and decrease vn when the UAV near the ground terminal to decrease the objective function value and obtain a strictly lower energy consumption. Until now, the objective is a convex with respect to vn,anξn, but with a new nonconvex constraint Cc7. Similarly, to tackle the nonconvexity of the constraint, a local convex approximation is adopted to tackle this issue. For any given local point vjn, we have the following expression by applying the first-order Taylor expansion:(17)vn≥vjn+2vjTnvn−vjn≜φlbvn,where the equality holds at the point vn=vjn. The function φlbvn is a linear function. Then, the new constraint is a convex set, which can be expressed as(18)Cc7lb:φlbvn≥ξn2,∀n.Then, the inequality in first-order Taylor expansion shows that the new constructed convex constraintCc7lb always implies the nonconvex constraint Cc7, but the reverse is not true in general.Then, the optimization problem (P3.1) can be reformulated as(19)P3.1.3MinimizeE¯ubvn,ξn=∑n=1Nc1vn3+c2ξn1+a2g2δt+ΔKsubject toCc1−Cc6,Cc7lb:φlbvn≥ξn2,∀n.Based on the previous discussions, the optimal solution of (P3.1.3) is the upper bound to that of problem (P3.1). Fortunately, the optimization problem (P3.1.3) is a standard convex optimization problem with the convex objective function with all convex constraints. It can be solved efficiently via the bisection method or the standard Dinkelbach’s algorithm.


## 3.3.2. Optimal Resource Allocation with Fixed Trajectory

For the wireless resource allocation issue, it is proposed to minimize the ground nodes transmit power under the fixed UAV trajectoryw∗n assumption. Then, the optimization problem for wireless resource allocation can be formulated as(20)P3.2MinimizePkn,αkn∑k=1K∑n=1NPkn,subject toCd1:R¯kαkn,Pkn,w∗n≥R^k,∀k,Cd2:∑k=1Kαkn≤1,0≤αkn≤1,∀k,n.This subproblem may correspond to the practical scenario when the UAV’s trajectory is predetermined due to other tasks (e.g., surveillance) rather than data collection. In this case, the optimal solution of the subproblem (P3.2) can minimize the transmit power of the ground nodes and extend the life time of the node.Since the trajectoryw∗n is fixed, the constraint Cd1 is a convex set combined with respect to Pkn,αkn. It can be verified that the subproblem (P3.2) satisfied the Slater’s condition. Using the dual Lagrangian method, the optimal power allocation Pk∗n can be expressed as(21)Pk∗n=λkBδtln2−1γk∗n+αk∗n,where γk∗n=γ0/H2+qk−w∗n2, λk is the Lagrange multiplier (or dual variable) associated with the constraint.∑
n
=
1
N
R
k
P
k
n
,
α
k
n
,
w
∗
n
≥
R
^
k; αk∗n is the optimal frequency band allocation factor. This is one instance of the water-filling solution to the optimal power allocation.Substitute the optimalPk∗n in the equation, the optimal frequency band allocation factor αk∗n can be obtained as equation (22):(22)αk∗n=1,ifλkBδtln2−1γk∗n+−Bδtλklog21+λkBδtγk∗nln2−1++μn<0,ak∗,ifλkBδtln2−1γk∗n+−Bδtλklog21+λkBδtγk∗nln2−1++μn=0,0,otherwise,where μn is the Lagrange multiplier (or dual variable) associated with the constraint ∑k=1Kαkn≤1; ak∗ can be any real number between 0 and 1, which can be calculated by satisfying the constraints Ca1 and Ca2. Generally, the optimal solution for αkn is binary solution if the amount of time slot n is large enough. Otherwise, ak∗ is adopted to fine-tune the resource allocation solution to meet the constraint.It is proposed to adopt an iterative subgradient method (Algorithm1) to optimize the dual variable λk,μn: the subgradient for λk of ground node k is given by gk=R^k−∑n=1NRk∗n and for μn of each time slot is given by tn=∑k=1Kαkn−1. The update procedure of Lagrangian dual variables are performed as(23)λkl=maxλkl−1+βlgk,0,μnl=maxμnl−1+θltn,0,where βl,θl are the step size for the iterative search process. Several step size rules have been proven to guarantee convergence under some general conditions.Algorithm 1:Iterative subgradient method for (P3.2).
(1)
Initializeλkl,μnl. Let l=0
(2)
repeat
(3)
Obtain the optimal powerPk∗n and αk∗n from the equations (21) and (22).
(4)
Get the subgradientgk and tn for all n
(5)
Update the dual variable according the equation (23) for all n.
(6)
Updatel=l+1.
(7)
Until Converges to a prescribed accuracy.The optimal solution includes two steps: (1) each of subproblem in slotn can be solved with fixed Lagrangian multipliers using the combinatorial method, (2) the convergency updates of Lagrangian multipliers are performed to meet the constraints. For the optimal dual variables optimization, it can also adopt the ellipsoid method to find the optimal solution. Our proposed procedure above is convenient for the transceiver processing for both UAV and ground nodes.


## 3.3.3. UAV Trajectory Optimization with Fixed Resource Allocation

Since the ground node has been allocated with fixed frequency band and power resource, we should adopt a dual problem to achieve the optimization goal by optimizing the UAV trajectory. In this section, we consider the issue to maximize the total rate of ground nodes by optimizing the UAV’s trajectory with fixed frequency band and power allocation. It is noted that maximizing the total rate of ground nodes can minimize the total energy consumption of ground nodes with the rate constraints. They are dual problems with each other. The optimization subproblem (P3.3) can be formulated as(24)P3.3Maximizewn∑k=1KR¯kαk∗n,Pk∗n,wn,subject toCe1:R¯kαk∗n,Pk∗n,wn≥R^k,∀k,Ce2:w0=w0,wN+1=wF,Ce3:wn+1=wn+vnδt+12anδt2,n=0,…,N,Ce4:v0=v0,vN+1=vF,Ce5:vn+1=vn+anδt,n=0,…,N,Ce6:vn≤Vmax,n=1,…,N,Ce7:an≤amax,n=0,…,N,Ce8:E¯wn≤PUAV.It is noted that the constraintsCe2−Ce7 are convex sets. However, the constraint Ce1 and Ce8 are nonconvex, and the objective function is nonconvex neither. The problem cannot be directly solved with the standard convex optimization techniques. We should adopt some relaxation method to construct the standard convex form and solve the problem (P3.3) efficiently.Firstly, to tackle the nonconvexity of the objective function, for any local pointwjn, define function R¯k,lbwn for each ground node as(25)R¯k,lbwn=Bδt∑n=1N−1ηj,kn−ψj,knqk−wn2−qk−wjn2,where(26)ηj,kn=αk∗nlog21+Pk∗nγ0αk∗nH2+qk−wn2,ψj,kn=log2ePk∗nγ0αk∗nH2+qk−wjn2+Pk∗nγ0H2+qk−wjn2.Note thatR¯k,lbwn is a concave function with respect to wn. Then the upper contour set R¯k,lbwn≥R^k is convex set. Moreover, as mentioned in [21], R¯kwn≥R¯k,lbwn holds true for any given wjn. The lower bound equation is the first order Taylor expansion of a convex differential function which is its global underestimator. Both R¯kwn and R¯k,lbwn have an identical gradient.Therefore, the optimization problem (P3.3) can be approximately solved by maximizing the lower bound as(27)P3.3.1Maximizewn∑k=1KR¯k,lbαk∗n,Pk∗n,wn,subject toCe1lb:R¯k,lbαk∗n,Pk∗n,wn≥R^k,∀k,Ce2−Ce7:Ce8:E¯wn≤PUAV,where the constraint of Ce1 is reformulated as a convex set Ce1lb.Secondly, considering the constraint set is still a nonconvex set for the variablevn. Just like the approximation method as in minimizing energy consumption for constrained UAV flight, we propose to introduce a slack variable ξn to reformulate the constraint Ce8 as(28)Ce8≜Cf8ub:E¯ubvn,ξn=∑n=1Nc1vn3+c2ξn1+a2g2δt+ΔK,Ce9:φlbvn≥ξn2,∀n.Then, all the constraints are convex set. Until now, we reformulate the optimization problem for any given local pointwjn,vjn, and it can be written as:(29)P3.3.2Maximizewn∑k=1KR¯k,lbαk∗n,Pk∗n,wn,subject toCe1lb:R¯k,lbαk∗n,Pk∗n,wn≥R^k,∀k,Ce2−Ce7:Ce8ub:E¯ubwn≤PUAV,Ce8ub:E¯ubwn≤PUAV,Ce9lb:φlbvn≥ξn2,∀n,Ce10:ξn≥0,∀n.Based on the previous discussions, the optimal solution of (P3.3.2) is the lower bound to that of problem (P3.3). Fortunately, the optimization problem (P3.3.2) is a standard convex optimization problem with the convex objective function with all convex constraints. It can be solved efficiently via the bisection method or the standard Dinkelbach’s algorithm. Then, the nonconvex problem (P3.3) can be solved by iteratively optimization (P3.3.2) with local point updated in each iteration. It can be summarized as the following table (Algorithm 2).Algorithm 2:Sequential convex optimization for (P3.3).
(1)
Initializew0n,v0n. Let j=0
(2)
repeat
(3)
Solve problem (P3.3.2) under the given local point wjn,vjn, and obtain the optimal solution as wj∗n,vj∗n.
(4)
Update the local pointwj+1n=wj∗n,vj+1n=vj∗n,∀n.
(5)
Updatej=j+1.
(6)
Until Converges to a prescribed accuracyIn summary, through adopting the relaxation method and sequential convex optimization technique, an efficient solution is proposed to solve the UAV trajectory optimization problem which is guaranteed that the optimal point is fulfill the Karush–Kuhn–Tucker conditions of the original nonconvex problem (P3.3).


## 3.3.4. Iterative Method for Optimal Resource Allocation and UAV Trajectory Design

Until now, we have solved the issues of UAV trajectory optimal design and resource allocation for ground terminals when one of them is fixed. In order to obtain the optimal solution for the original optimization problem (P3), we propose an alternate iterative solution to optimize the UAV trajectory and resource allocation, based on the methods mentioned in Sections 3.3.1.–3.3.3.The proposed optimal solution can be summarized as follows (Algorithm3).Algorithm 3:Alternate iterative solution for original optimization problem (P3).
(1)
Feasible solution check: Solve the problem (P3.1) to calculate the minimum energy consumption PUAVmin for UAV flight from initial point to final location.
If PUAVmin≤PUAV;
Set: The initial UAV trajectory with minimum energy consumption as w0Fixn,v0Fixn.
Letl=0;
Go toStep 2;
Otherwise, There is no feasible solution, End
(2)
repeat
(3)
Solve problem (P3.2) under the fixed trajectory wlFixn,vlFixn by Algorithm 1, and obtain the optimal resource allocation solution as αk,l∗n,Pk,l∗n,∀n .
(4)
Update the fixed resource allocation solutionαk,lFixn=αk,l∗n,Pk,lFixn=Pk,l∗n;
(5)
Solve problem (P3.3) under the fixed resource allocation αk,lFixn,Pk,lFixn by Algorithm 2, and obtain the optimal UAV trajectory as wg,l∗n,vg,l∗n,∀n
(6)
Update the fixed UAV trajectorywl+1Fixn=wg,l∗n,vl+1Fixn=vg,l∗n,∀n
(7)
Update l=l+1.
(8)
Until Converges to a prescribed accuracyNote that the solution for problem (P3.2) adopts an iterative subgradient method in Algorithm 1 whose complexity is OlN where l is the iteration time. As Algorithm 2 requires to solve convex optimization problems, it has a polynomial complexity in the worst case each iteration [27]. Thus, the complexity of Algorithm 3 combining Algorithms 1 and 2 is the polynomial complexity because polynomial complexity multiplied by iterations is still polynomial complexity which is affordable.


## 4. Simulation Results and Analysis

In this part, we provide numerical results to prove the reliability of the proposed algorithm. We assume thatK=10 ground users are randomly distributed in this system with an area of 1×1km2. Other reference values are as follows: UAV’s altitude is H=100m. The communication bandwidth is B=1MHz and noise power is assumed to be σ2=−150dBm. Besides, we set that c1=9.264×10−4 and c2=2250, the maximum speed of UAVs are assumed as Vmax=100m/s, and the maximum acceleration of UAVs are assumed as amax=30m/s2 and Q^k = 100 Mbits (Mb).Firstly, we evaluate the energy trade-off between the consumption of ground terminals and UAV.We consider a certain trajectory. Multiple ground terminal and UAV energy region are shown in Figure2. We can see clearly from the figure that the energy consumption of the ground user decreases as the drone energy consumption increases with different data collect requirement of Q^k. More concretely, when increasing the UAV’s energy from 22 kJoule to 31 kJoule under the requirement of Q^k = 80 Mbits (Mb), the GTs energy consumption would be significantly reduced from 32 Joule to 27 Joule.Figure 2
Multiple GTs and UAV energy region. (a)Q^k = 80 Mbits (Mb). (b) Q^k = 100 Mbits (Mb).
(a)
(b)By comparing with the resource allocation optimization shown in Figure3, the solution we propose that optimizes the resource allocation and trajectory jointly delivers significant performance in energy efficiency. Specifically, the GTs’ energy consumption of combined resource allocation optimization is 27 Joule when the UAV’s energy consumption is 35 kJoule, while that of resource allocation optimization only is 86 Joule. It can be observed that the total energy consumption for ground terminals achieved by the proposed algorithm dramatically decreases with the number of iterations and the algorithm converges in about 4–6 iterations from Figure 4. Thus, the solution we propose is able to converge fast and the computational complexity is suitable for practical implementation.Figure 3
Energy consumption for GTs of differentQ^k.Figure 4
Total energy consumption for ground terminals withQ^k = 100 Mbits (Mb).Next, we study the UAV trajectory optimization.As shown in Figure5, the UAV flies to the top of each GT eventually to fulfill the communication task. It is observed that the obtained trajectories tend to be converged for comparing the trajectory of fifth iteration and that of seventh iteration proposed by the algorithm. We also show the scheduling of every GT in Figure 6 where the UAV maintains communicating with GT all the time in order to save the energy.Figure 5
Trajectories in different iterations. (a) Five iterations. (b) Seven iterations.
(a)
(b)Figure 6
Schedule for each GT.We also collect the UAV trajectory optimization results. In multiuser scenario, we obtained the UAV trajectory under the constraints of limited flight energy and data collection rate, minimizing the energy consumption problem of user communication. The UAV trajectories under different UAV energy consumption are shown in Figure7. With the increase of ΔK, the UAV hovers around more on the top of GTs so as to save that of the GTs but consume energy of the UAV. It is beneficial for energy-limited GTs.Figure 7
Trajectories under different UAV energy consumption. (a) Δk = 0 J. (b) Δk = 3300 J. (c) Δk = 6600 J. (d) Δk = 10000 J.
(a)
(b)
(c)
(d)


## 5. Conclusions

In this paper, we have studied the optimal resource allocation scheme and optimal trajectory design strategy for multiple ground terminals with UAV arbitrary flight. First, UAV’s energy consumption and GT’s energy consumption are derived, and we describe their Pareto optimal trade-offs and adopt the strategy to minimize the ground terminal energy consumption with fixed UAV energy consumption and consider rate constraints of ground terminals. Second, through calculating minimum energy consumption for constrained UAV flight, we gain the initial UAV flight in the G-U system. Next, we propose to get the optimal resource allocation under the fixed flight. Then, through maximizing the total rate of ground nodes by optimizing the UAVs trajectory with fixed frequency band and power allocation. Finally, we use an alternate iterative solution to optimize the UAV trajectory and resource allocation. Simulation results show the alternate solution we proposed can significantly improve the performance in energy efficiency compared with the scheme without optimizing trajectory. Through this paper, we consider a point-to-point G2U communication scheme formerly [23], extending to a UAV to multiusers on designing energy-saving UAV communication. We hope that there will be more development in the future wireless communication.



---

*Source: 9647539-2019-08-25.xml*