# Joint Scheduling and Power Optimization for Complex Status Updates in Multiantenna UAV-Assisted Multiaccess Edge Computing

Authors: Xianbang Diao; Wendong Yang; Jianchao Zheng; Yueming Cai
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

The status information of complex status update applications (e.g., real-time environmental monitoring in disaster areas) can only be obtained after data processing. Therefore, the impact of data processing on age of information (AoI) cannot be ignored in complex status update applications. In this paper, complex status updates in emergency scenario are investigated, where some multiantenna unmanned aerial vehicles (UAVs) help resource-limited user devices (UDs) complete complex status updates which involve computing processes. To reduce average AoI, UDs’ energy consumptions, and UAVs’ energy consumptions in a balanced manner, the weighted sum of the three metrics is aimed to be minimized. Scheduling strategies (i.e., data transmission and computing start moments, service period, and flight radius) and power (i.e., data and pilot transmit power) allocation strategies are jointly optimized to reduce the weighted sum. The original problem is NP-hard. Thus, it is decoupled into some subproblems. Then, the near-optimal solution or stationary point of each subproblem is obtained by analyzing the characteristics of the subproblems. Finally, an iterative algorithm is proposed to alternately optimize the scheduling and power allocation strategies to obtain the suboptimal solution of the original problem. Simulation results show that the proposed algorithm can effectively reduce the average AoI and the energy consumptions of UDs and UAVs in a balanced way.


---

## Body

## 1. Introduction

The steady development of Internet of Things (IoT) has promoted the demand for real-time status update applications. In these applications, the user device (UD) (e.g., IoT device) sends sensing data to the control terminal for subsequent control processes [1]. The work [2] first proposed the age of information (AoI) to characterize the freshness of information during status updates. Recently, some works studied optimizations for AoI [2–6]. These works pay attention to the impact of simple data transmission on AoI. However, the impact of computing on AoI cannot be ignored in some complex status update applications. For example, in intelligent driving, the environmental information sensed by vehicles needs to be transformed into status information by complex computing. During the complex status update process, the computing delay affects AoI, which is different from the traditional status update process.Resource-limited UDs may not afford the energy consumptions caused by the complex computing. Computing offloading technology allows UDs to offload computing tasks to computing servers, which is an effective solution to the problem above. It is worth noting that compared to tasks in conventional computing offloading, we adopt AoI instead of task delay to evaluate the tasks in complex state updates. Some works studied the AoI in cloud computing or fog computing scenarios [7–11]. More recently, some works analyzed and optimized AoI in multiaccess edge computing (MEC) systems [12–17]. The works above studied the AoI in MEC systems where the computing servers are fixed. However, fixed servers cannot adapt to emergency scenarios such as disaster rescue.Owing to the high mobility, unmanned aerial vehicles (UAVs) [18–20] can be used to assist or serve UDs in some emergency scenarios. Specifically, UAVs can be used as data repeaters to assist UDs during status updates [21–23]. Furthermore, UAVs can be used as temporary servers to provide computing services for UDs [24–27]. Therefore, multiple UAVs can help UDs complete complex status updates in emergency scenarios. Moreover, since multiple antennas [28–30] can effectively reduce the transmission energy consumption without increasing the power and bandwidth, it is a basic physical layer technology in 5G and even in B5G/6G. Therefore, UAVs can be equipped with multiple antennas in the millimeter wave band [31] to provide higher quality services to UDs.In this paper, we focus on the complex status updates in a multiantenna UAV-assisted MEC system. During one service period, each UD offloads its computing task to an UAV. Next, the UAV completes the task and then transmits the status information back to the UD. Since average AoI can reflect the average information freshness of complex status updates, it is an important performance metric. Furthermore, the energy consumptions of energy-limited UDs and UAVs should be considered for extending the UDs’ and UAVs’ endurance. Therefore, we aim to reduce the average AoI and the energy consumptions of UDs and UAVs simultaneously. However, there are complex correlations between the three performance metrics. Thus, independent optimizations for one of the performance metrics cannot achieve the global optimization. To this end, we aim to minimize the weighted sum of the average AoI and the energy consumptions of UDs and UAVs, which aims to optimize the three performance metrics in a balanced way.During the status updates, reaping the minimization of the weighted sum requires taking into account the following key issues. Firstly, the transmission and computing start moments affect average AoI. Furthermore, the transmission start moments can affect the UAVs’ positions of receiving tasks and then further influence the UDs’ energy consumptions. Secondly, pilot and data transmit powers affects UDs’ energy consumptions significantly. Thirdly, service period and flight radius affect the average AoI and the energy consumptions of UDs and UAVs. Therefore, the six types of variables above should be jointly optimized.However, the joint optimization problem has the following challenges. Firstly, compared to the existing works where servers are fixed, the UAVs’ positions of receiving tasks decide UDs’ transmission rates and further affect the average AoI and the energy consumptions of UDs, which increases the difficulty of the optimization. Secondly, transmission start moments of the adjacent status updates are coupled with each other, which greatly increases the complexity of the problem. The discussion above also applies to the computing start moments. Thirdly, since we model the channels between the UAVs and UDs as Rician channels under imperfect channel state information, the transmission rate is a complex and nonconvex function with respect to the pilot and data transmit powers, service period, and flight radius. Although the joint optimization problem has the challenges above, we obtain the suboptimal solution by analyzing the problem and proposing an iterative algorithm. Moreover, a large rotor UAV at a higher altitude, as a central controller [32], collect UDs’ positions and task information and release the optimized scheduling and power allocation strategies to UDs and UAVs. The main contributions of this paper are summarized as follows.
(1)
Complex status updates in an emergency scenario are investigated. In the scenario, multiantenna UAVs, as air computing servers, provide computing services for UDs so that they can update their statuses timely. Moreover, the Rician channel and the nonideal channel state information are both considered, which are realistic(2)
We adopt the zero-wait principle for the computing offloading process, which aims to avoid the increase of average AoI caused by data accumulations. Moreover, the weighted sum of the average AoI and the energy consumptions of UDs and UAVs is reduced by jointly optimizing scheduling and power allocation strategies, which improves the efficiency of status update with low energy consumption(3)
The NP-hard problem is decoupled into five subproblems, and we obtain the near-optimal solutions or stationary points of the subproblems by analyzing their characteristics. Specially, we propose a search algorithm based on greedy rules to obtain the near-optimal solution of the transmission and computing start moment subproblem. Subsequently, we transform the pilot and data transmit power subproblems into convex problems and propose search algorithms based on the successive convex approximation to obtain their stationary pointsThe rest of this paper is organized as follows. In Section II, we introduce the system model and formulate the optimization problem. In Section III, the five subproblems are solved one by one and an iterative algorithm is proposed to solve the optimization problem. Section IV presents the numerical results. Finally, we conclude the paper in Section V.


## 2. System Model and Problem Formulation

(1)Rm,k,n=Blog21+pm,ngm,k,nL2Km,k,n2+2LKm,k,n+2L2Km,k,nηm,k,n+L+L2ηm,k,n2pm,nKm,k,n+1∑i=1,i≠kKmgm,i,nΔm,k,i,n+Lpm,ngm,k,nKm,k,n+ηm,k,n/1+gm,k,npm,np+N0BLKm,k,n+1Km,k,n+ηm,k,n,In a system without infrastructures, UDs have perception and communication capabilities. They obtain perceived data by sensing physical processes in the real world. Specially, the perceived data needs to be calculated and transformed into status information for subsequent operations. Since the energy of each UD is limited, multiple UAVs equipped with multiple antennas fly over the target area and provide UDs with computing services.As shown in Figure1, we consider a multiantenna UAV-assisted MEC system, where M fixed-wing UAVs equipped with L antennas provide computing services to K single-antenna UDs. The system adopts the millimeter wave frequency band, which allows the deployment of multiple antennas on UAVs [33, 34]. The UDs are randomly distributed in the circular area with radius rud, and the circular area is uniformly divided into M sector areas. For convenience, we denote the set of sector areas as M=1,⋯,M, and the set of all UDs belonging to the sector area m is Km=1,⋯,Km, where Km is the number of UDs in the sector area m. All UAVs fly with the same altitude H and on the same circular trajectory of radius ruav. Moreover, all UAVs make uniform circular motions and the flight period of each UAV is T. In particular, since UAVs perform services during the flight process, the service period is equivalent to the flight period. At the initial moment of a service period, M UAVs start flying from the angular bisector of M sector areas, respectively. Therefore, in any sector area, there is always one UAV over the area at any moment t within the period T. It is worth noting that since each UAV makes a uniform circular motion and its initial position is known, the position of each UAV at any moment can be obtained by calculations. Moreover, a three dimensional Cartesian coordinate system is adopted, where the coordinate of UD k in the sector area m is um,k=uxm,k,uym,k,0T,∀k∈K. The coordinate of the UAV m at moment t is qm,t=qxm,t,qym,t,HT,∀m∈M, where qxm,t=ruavcos2πt/T+ζm and qym,t=ruavsin2πt/T+ζm, where ζm represents the initial azimuth of UAV m. Each UD needs to complete N status updates during a service period. Define N=1,⋯,N as the set of the number of status updates. During each status update, the perceived data of UD k in the sector area m is the input data of a computation-intensive task Am,kΔ=Dm,k,Cm,k, which adopts the binary offloading model where the task has to be executed as a whole at one equipment. Dm,k represents the amount of computing task for the UD k in the sector area m, and Cm,k is the CPU cycles required to complete Am,k.Figure 1
The multiantenna UAV-assisted multiaccess edge computing system.All UDs in sector aream utilize the same time-frequency resource to offload perceived data to the UAV over the sector area. Due to the strong line-of-sight (LoS) link and some NLoS links, the channels between UAVs and UDs can be modeled as Rician channels [35]. In order to facilitate the decoding of multiuser signals, UAVs need to perform uplink channel estimation based on the UDs’ uplink pilot signals before the data transmission. Specifically, all UDs in sector area m send uplink pilots with symbol sequences of length τ to the UAV over the sector area m, where τ is smaller than the channel coherence interval Tc. Moreover, the pilots of all UDs in a sector area are designed pair-wise orthogonally, i.e., there is no pilot pollution. The UAVs adopt the minimum mean-square-error (MMSE) estimation approach and the maximal ratio combining (MRC) detection method. Based on the work [36], at moment tn, the achievable uplink rate of the UD k in the sector area m is shown in formula (1), where tn is the generation moment and the transmission start moment of the perceived data during the n-th status update, i.e., the perceived data are sent immediately when they are generated. It is worth noting that the transmission start moments of all UDs are the same. In addition, B=W/M represents the bandwidth allocated to each sector area, and W represents the total system bandwidth. Moreover, some parameters in formula (1) are defined as
(2a)gm,k,n=g0uxm,k−qxm,tn2+uym,k−qym,tn2+H2⏟dm,k,n2,(2b)ϕm,k,i,n=sinLπ/2sinθm,k,n−sinθm,i,nsinπ/2sinθm,k,n−sinθm,i,n,(2c)Δm,k,i,n=Km,k,nKm,i,nϕm,k,i,n2+Lηm,k,nKm,i,n+ηm,k,n+Km,k,nKm,i,n+1,wherepm,np and pm,n represent the pilot transmit power and data transmit power of all UDs in sector area m during the n-th status update, respectively. gm,k,n represents the deterministic channel gain between UD k in the sector area m and the UAV over the area m during the n-th status update. Moreover, g0 and dm,k,n represent the channel power gain at the reference distance d0=1 m and the distance between the UD k and the UAV over the sector area m during the n-th status update, respectively. Based on the work [35], the Rician factor can be modeled by the exponential function of the elevation angle θm,k,n=arcsinH/dm,k,n, and its expression is Km,k,n=C1eC2θm,k,n, where C1 and C2 are constant coefficients determined by the specific environment. Moreover, ηm,k,n=pm.npgm,k,n/1+pm.npgm,k,n.During then-th status update, the transmission delay, computing delay, and energy consumption of the UD k in the sector area m can be given as follows:
(3a)Tm,k,n=TcDm,kTc−τRm,k,n,(3b)TCm,k,n=Cm,kfm,k,(3c)Em,k,n=τpm,npDm,k/Tc−τ+pm,nDm,kRm,k,n,wherefm,k is the computing rate assigned to the UD k in the sector area m. We define that the total computing rate of any UAV is F, and each UAV equally distributes its computing rate to all UDs connected to it. In other words, fm,k=F/Km. Moreover, the transmission delay includes the pilot transmission delay and data transmission delay. The data transmission delay has proportional relationships with the transmission delay and pilot transmission delay. Therefore, in formulas (3a) and (3c), the transmission delay and the pilot transmission delay can be obtained by multiplying the data transmission delay with scale factors.We adopt the zero-wait principle for the communication process and the specific principle is given as follows. To avoid the communication queuing, the transmission start moment of then+1-th status update should not be less than the transmission termination moment of the n-th status update, and the constraint is given as follows:
(4a)tn+1≥tn+Tntr,∀n∈N\N,whereTntr represents the maximal transmission delay during the n-th status update, and its expression is Tntr=maxm,kTm,k,n.Moreover, the positions of all UAVs are considered to be stationary during each status update. Therefore, the maximal transmission delay of each status update needs to satisfy the following constraint:(4b)Tntr≤TF,∀n∈N,whereTF represents a time threshold. Specifically, if the maximal transmission delay of the n-th status update is smaller than the threshold, UAVs are approximately regarded as stationary.To keep UDs from spending large idle time on the communication, the transmission start moment of then+1-th status update should not be greater than the termination moment of the n-th status update. The constraint is given as follows:
(4c)tn+1≤tn+Tntr+Tncom,∀n∈N\N,whereTncom represents the maximal computing delay of the n-th status update, and its expression is Tncom=maxm,kTCm,k,n. tn+Tntr+Tncom represents the termination moment of the n-th status update. Since the amount of status information is small, the download time of status information can be ignored.Since the status update is continuous and time-sensitive, the AoI is introduced to characterize the freshness of the status information. The change rules of the AoI are given as follows. During then-th status update, if the computation- intensive task Am,k of UD k in the sector area m does not be completed, the UD k does not receive new status information. Thus, its AoI increases linearly with time t. Otherwise, the AoI of UD k in the sector area m can be given as follows:
(5)Δm,kt=t−tn.Furthermore, the average AoI of UDk in the sector area m can be given as follows:
(6)Δ¯m,k=∫0TΔm,ktdt.In Figure2, a schematic of the AoI of UD k in the sector area m is depicted. The initial AoI of the UD k in the sector area m is Δm,k0. Its average AoI can be calculated by the areas of N isosceles trapezoids P1,⋯,PN and the area of an isosceles triangle AN. The expression can be given as follows:
(7)Δ¯m,k=1T∫0TΔm,ktdt=12Tc1+TCm,k,1+Δm,k02−c1+TCm,k,1−t12+∑n=2Ncn+TCm,k,n−tn−12−cn+TCm,k,n−tn2+T−tN2−Δm,k02,Figure 2
A schematic of AoI of UDk in the sector area m.wherecn is the computing start moment of the n-th status update. Since there are multiple sector areas in the system, all UAVs start to perform computing tasks simultaneously for the facilitate management.Moreover, UAVs have flight energy consumptions and computing energy consumptions during the service period. Since computing energy consumptions are much smaller than flight energy consumptions, we mainly consider flight energy consumptions of UAVs. Similar to work [18], the flight energy consumption of UAV m that flies on a circle is given as follows:
(8)Emfly=c1+c2ruav28π3ruav3T2+c2T22πruav,wherec1 and c2 are parameters related to UAV weight, wing area, air density, and gravitational acceleration, etc.In order to improve the efficiency of status update with low energy consumption, we aim to minimize the weighted sum of the average AoI and the energy consumptions of UDs and UAVs by jointly optimizing the scheduling and power allocation strategies, where the scheduling strategies include the transmission and computing start moments, service period, and flight radius. The power includes the pilot and data transmit power. The optimization problem is given as follows:(9a)OP:minΖωA∑m=1M∑k=1KmΔ¯m,k+ωE∑n=1N∑m=1M∑k=1KmEm,k,n+ωU∑m=1MEmfly,(9b)Tntr≤TF,∀n∈N,(9c)t1≥0,(9d)tn≥tn−1+Tn−1tr,∀n∈N\1,(9e)tn≤tn−1+Tn−1tr+Tn−1com,∀n∈N\1,(9f)cn≥tn+Tntr,∀n∈N,(9g)cn≥cn−1+Tn−1com,∀n∈N\1,(9h)cN+TNcom≤T,(9i)0<pm,n≤Pmax,∀m∈M,n∈N,(9j)0<pm,np≤Pmax,∀m∈M,n∈N,(9k)dmin2sinπ/M≤ruav≤rud,(9l)2πruavVmax≤T≤2πruavVmin,whereZ=tn,cn,pm,np,pm,n,T,ruav. ωA, ωE, and ωU are the weighted factors of average AoI, UDs’ energy consumptions, and UAVs’ energy consumptions, respectively. The main function of weighted factors is to optimize the average AoI and the energy consumptions of UDs and UAVs in a blanced way. The values of the weighted factors can be determined by comparing the average AoI and the energy consumptions of UDs and UAVs under an initial solution.Here, constraint (9b) ensures that all UAVs are consider to be stationary during any status update. Constraint (9c) requires that the transmission start moment of the 1-st status update must be nonnegative. Constraint (9d) ensures the realization of the zero-wait principles in communication process. Constraint (9e) avoids long-term idleness in communications. Constraint (9f) indicates that the computing start moment should not be less than the transmission termination moment during any status update. Constraint (9g) means that the computing start moment of the n-th status update cannot be less than the termination moment of the n−1-th status update. The reason is that the computing tasks of the n-th status update should be started at the same time, and the computing tasks of the n-th status update cannot be executed when the computing tasks of the n−1−th status update are being executed. Constraint (9h) indicates that the termination moment of the N-th status update should not be greater than the service period T. Constraints (9i) and (9j) represent that the pilot and data transmit powers must be in the feasible power ranges. Constraint (9k) indicates that the flight radius of UAVs should ensure the UAV minimum safe distance dmin and do not exceed the radius of the UDs’ area. Constraint (9l) means that the service period of UAVs should satisfy the flight constraints of UAVs, where Vmax and Vmin are the maximal and minimal flight speed of each UAV. Since the objective function and the constraints (9b) and (9d)–(9f) are nonconvex, the problem is a nonconvex optimization problem and cannot be directly solved by the convex optimization techniques.


## 3. Algorithm Design

In this section, we first transform the original problem into multiple subproblems based on the correlations between variables. Specifically, there are constraints between transmission and computing start moments, and they are independent of other variables. Therefore, we formulate a sub-problem related with transmission and computing start moments. Since the other variables are independent of each other, we formulate the corresponding subproblem for each variable. Then, we solve subproblems according to their characteristics. Finally, an iterative algorithm is proposed to obtain the suboptimal solutions of the original problem.


### 3.1. Transmission and Computing Start Moment Optimization

Since the transmission start moment and the computing start moment are tightly coupled, the subproblem SP1 jointly optimizes the two types of variables. With givenpm,np,pm,n,T,ruav, the transmission and computing start moment optimization problem can be formulated as follows:
(10a)SP1:mintn,cnωA∑m=1M∑k=1KmΔ¯m,k+ωE∑n=1N∑m=1M∑k=1KmEm,k,n,(10b)Tntr≤TF,∀n∈N,(10c)t1≥0,(10d)tn≥tn−1+Tn−1tr,∀n∈N\1,(10e)tn≤tn−1+Tn−1tr+Tn−1com,∀n∈N\1,(10f)cn≥tn+Tntr,∀n∈N,(10g)cn≥cn−1+Tn−1com,∀n∈N\1,(10h)cN+TNcom≤T.Although there is a strong coupling relationship betweencn and tn, we can simplify the SP1 by analyzing the objective function. Specifically, we obtain the partial derivative of the objective function with respect to cn as
(11a)ωA∂∑m=1M∑k=1KmΔ¯m,k∂c1=ωAT∑m=1M∑k=1Km∑n=1Nt1+Δm,k0,(11b)ωA∂∑m=1M∑k=1KmΔ¯m,k∂cn=ωAT∑m=1M∑k=1Km∑n=1Ntn−tn−1,∀n∈N\1.It can be seen that the objective function is a linear expression ofcn. Since t1+Δm,k0≥0,∀m∈M,k∈Km and tn−tn−1≥Tn−1tr>0,∀n∈N\1, the objective function is monotonically increasing with respect to cn. Therefore, if cn does not take the minimum value within its feasible region, a smaller cn can always be found to make the objective function smaller. In summary, when the objective function is optimal, the formulascn=tn+Tntr,n=1maxtn+Tntr,cn−1+Tn−1com,1<n≤Nalways hold. Therefore, the transmission and computing start moment optimization problem can be equivalently transformed as follows:(12a)SP1.1:mintnωA∑m=1M∑k=1KmΔ¯m,k+ωE∑n=1N∑m=1M∑k=1KmEm,k,n,(12b)Tntr≤TF,∀n∈N,(12c)t1≥0,(12d)tn≥tn−1+Tn−1tr,∀n∈N\1,(12e)tn≤tn−1+Tn−1tr+Tn−1com,∀n∈N\1,(12f)tN+TNtr+TNcom≤T.Since the objective function of the SP1.1 is still a nonconvex function oftn, it is difficult to solve it by convex optimization techniques. In addition, both Tntr and Em,k,n are complex functions of tn. It is intractable to analyze tn in the objective function of the SP1.1. Therefore, search algorithms are more suitable for solving the SP1.1. However, the number of variables in the SP1.1 is N, and the adjacent variables tn and tn+1 are coupled. If the exhaustive search algorithm is performed for all variables, the computational complexity of the exhaustive search algorithm is highly exponential. Therefore, the exhaustive search algorithm is not suitable for solving the SP1.1.In order to obtain an approximately optimal solution with lower complexity, we further analyze the SP1.1. Whent1 is fixed, there is a optimal set of tn,∀n∈N\1 to minimize the objective function. Moreover, the constraints (12d) and (12e) indicate the Markov properties of the transmission start moments, i.e., tn+1 is only related to tn. In other words, the SP1.1 can be divided into multiple subproblems step by step. For example, when t1 is fixed, the subproblem of t2 can be solved. When t2 is fixed, the subproblem of t3 can be solved and so on. Based on the characteristics above, the greedy rule can be used to solve each sub-problem above. Specifically, when tn is fixed, we only choose tn+1 that minimizes the current weighted sum as the solution of tn+1. The current weighted sum is shown in formulas (13) and (14), where c¯n=maxtn+Tntr,cn−1+Tn−1com. The specific steps of the algorithm are shown in Algorithm 1, where N1 is the number of sampling points of t1, and t1max is the maximum feasible value of t1 and can be obtained by search algorithms. Specially, Tn is a set of tn which are generated from N2 sampling points and satisfies constraints tn≥tn−1+Tn−1tr, tn≤tn−1+Tn−1tr+Tn−1com, and Tntr≤TF within the interval tn−1+Tn−1tr,tn−1+Tn−1tr+Tn−1com. Moreover, TN is a set of tN which are generated from N2 sampling points and satisfies constraints tN≥tN−1+TN−1tr, tN≤tN−1+TN−1tr+TN−1com, tN+TNtr+TNcom≤T, and TNtr≤TF within the interval tN−1+TN−1tr,tN−1+TN−1tr+TN−1com.
(13)cwsn=ωA2T∑m=1M∑k=1Kmtn−tn−12c¯n+TCm,k,n−tn−tn−1+ωE∑m=1M∑k=1KmEm,k,n,∀n∈N\1,N,(14)cwsN=ωA2T∑m=1M∑k=1KmtN−tN−12c¯N+TCm,k,N−tN−tN−1+T−tN2+ωE∑m=1M∑k=1KmEm,k,N.Algorithm 1: Obtaining the near-optimal solutions of SP1.1.
1:ξ=t1max/N1 and o=12:repeat3: Sett1o=o−1ξ and n=1.4: CalculateTntr based on formula (3a).5: ifTntr>TFthen6:o=o+1.7:else8:n=n+1.9:repeat10:if2≤n≤N−1then11:    Find the setTn of tn.12:    ifTn=∅then13:o=o+1.14:break.15:else16:     Choosetn′ in the Tn that minimizes cwsn as tno and set n=n+1.17:end if18:end if19:ifn=Nthen20:    Find the setTN of tN.21:ifTN=∅then22:o=o+1.23:break.24:else25:     ChoosetN′ in the set TN that minimizes cwsN as tNo and set n=n+1.26:end if27:end if32128:untiln=N+129:end if30:untilt1o≥t1max31: Choose the settno with the smallest objective function as tn∗.32:Output: tn∗.


### 3.2. Pilot Transmit Power Optimization

With giventn,cn,pm,n,T,ruav, the pilot transmit power optimization problem can be formulated as follows:
(15a)SP2:minpm,npωE∑n=1N∑m=1M∑k=1Kmτpm,npDm,k/Tc−τ+pm,nDm,kRm,k,n,(15b)Tntr≤TF,∀n∈N,(15c)Tntr≤tn+1−tn,∀n∈N\N,(15d)Tntr≥tn+1−tn−Tncom,∀n∈N\N,(15e)Tntr≤cn−tn,∀n∈N,(15f)0<pm,np≤Pmax,∀m∈M,n∈N.It can be seen that the objective function of the SP2 only includes UDs’ energy consumptions. Moreover,pm,np does not affect the energy consumptions of UDs in different status updates and in different sector areas. Therefore, the SP2 can be equivalently transformed into a problem of minimizing energy consumptions of UDs in sector area m and during status update n. Specifically, the equivalent problem SP2.1 can be given as follows:
(16a)SP2.1:minpm,npωE∑k=1Kmτpm,npDm,k/Tc−τ+pm,nDm,kRm,k,n,(16b)s.t.Tntr≤Tnmax,(16c)Tntr≥Tnmin,(16d)0<pm,np≤Pmax,where(16e)Tnmax=minTF,tn+1−tn,cn−tn,1≤n≤N−1,minTF,cn−tn,n=N.(16f)Tnmin=tn+1−tn−Tncom,∀n∈N\N.It can be seen that the objective function of the SP2.1 is nonconvex, and constraints (16b)-(16c) need to be further processed. Thus, we convert the SP2.1 into an approximate convex problem and utilize successive convex approximation (SCA) to obtain the stationary point of the SP2.1. First, we deal with the objective function of the SP2.1. The auxiliary variables φm,k,n are introduced, which satisfy constraints Rm,k,n≥e−φm,k,n,∀k∈Km. Then, we further deal with the constraints above.Firstly, the transmission rate can be equivalently written as(17)Rm,k,n=Blog21+zm,k,n+ym,k,npm,np+xm,k,npm,np2z~m,k,n+y~m,k,npm,np+x~m,k,npm,np2,where the expressions ofzm,k,n, z~m,k,n, ym,k,n, y~m,k,n, xm,k,n, and x~m,k,n are shown in formulas (18–23). Therefore, the constraints Rm,k,n≥e−φm,k,n,∀k∈Km can be equivalently expressed as formula (24):
(18)zm,k,n=L2Km,k,n2pm,ngm,k,n,(19)z~m,k,n=pm,nKm,k,n+1∑i=1,i≠kKmgm,i,nKm,k,nKm,i,nϕm,k,i,n2+LKm,k,nKm,i,n+1+Lpm,ngm,k,nKm,k,n+N0BLKm,k,n+1Km,k,n,(20)ym,k,n=2pm,ngm,k,n2L2Km,k,n2+pm,n2LKm,k,n+2L2Km,k,ngm,k,n2,(21)y~m,k,n=2pm,nKm,k,n+1∑i=1,i≠kKmgm,k,ngm,i,nKm,k,nKm,i,nϕm,k,i,n2+LKm,k,nKm,i,n+1+pm,nKm,k,n+1∑i=1,i≠kKmLgm,i,ngm,k,n+Lpm,ngm,k,nKm,k,ngm,k,n+gm,k,n+N0BLKm,k,n+12Km,k,ngm,k,n+gm,k,n,(22)xm,k,n=pm,ngm,k,n3L2Km,k,n2+pm,ngm,k,n32LKm,k,n+2L2Km,k,n+pm,nL+L2gm,k,n3,(23)x~m,k,n=pm,nKm,k,n+1∑i=1,i≠kKmgm,i,ngm,k,n2Km,k,nKm,i,nϕm,k,i,n2+LKm,k,nKm,i,n+1+pm,nKm,k,n+1∑i=1,i≠kKmLgm,i,ngm,k,n2+N0BLgm,k,n2Km,k,n+12,(24)lnz¯m,k,n+y¯m,k,npm,np+x¯m,k,npm,np2z~m,k,n+y~m,k,npm,np+x~m,k,npm,np2≥e−φm,k,nln2B,∀k∈Km,where z¯m,k,n=zm,k,n+z~m,k,n, y¯m,k,n=ym,k,n+y~m,k,n, x¯m,k,n=xm,k,n+x~m,k,n.We setXm,k,n=z¯m,k,n+y¯m,k,npm,np+x¯m,k,npm,np2/z~m,k,n+y~m,k,npm,np+x~m,k,npm,np2>0. Since lnXm,k,n is a concave function with respect to Xm,k,n, we obtain the first-order Taylor expansion of lnXm,k,n at the feasible point Xm,k,nlocal=z¯m,k,n+y¯m,k,npm,np,local+x¯m,k,npm,np,local2/z~m,k,n+y~m,k,npm,np,local+x~m,k,npm,np,local2. Then, the constraint (24) can be written approximately as follows:
(25)lnXm,k,nlocal+z¯m,k,n+y¯m,k,npm,np+x¯m,k,npm,np2Xm,k,nlocalz~m,k,n+y~m,k,npm,np+x~m,k,npm,np2−1≥e−φm,k,nln2B,∀k∈1,⋯,Km.It is worth noting that constraint (25) does not guarantee the validity of constraint (24), namely, it cannot ensure that we can obtain the upper bound of the objective function of SP2.1 for minimization. However, the effectiveness of constraint (25) can be seen from the simulation section. Therefore, constraint (25) is acceptable. Next, we introduce variables ψm,n and set eψm,n=pm,np. Then, constraint (25) can be equivalently written as follows:
(26)z⌢m,k,n+y⌢m,k,neψm,n+x⌢m,k,ne2ψm,n+e−φm,k,nln2Bz⌢m,k,n+y⌢m,k,neψm,n+x⌢m,k,ne2ψm,n≤0,∀k∈Km,where x⌢m,k,n=x~m,k,n−x~m,k,nlnXm,k,nlocal−x¯m,k,n/Xm,k,nlocal, y⌢m,k,n=y~m,k,n−y~m,k,nlnXm,k,nlocal−ym,k,n/Xm,k,nlocal, and z⌢m,k,n=z~m,k,n−z~m,k,nlnXm,k,nlocal−z¯m,k,n/Xm,k,nlocal. Moreover, we define a function fψm,n=y⌢m,k,neψm,n+x⌢m,k,ne2ψm,n.Lemma 1.
fψm,n is a concave function with respect to ψm,n.Proof.
The functionfψm,n can be written equivalently as
(27)fψm,n=y~m,k,n−y~m,k,nlnXm,k,nlocal−y¯m,k,nXm,k,nlocaleψm,n+x~m,k,n−x~m,k,nlnXm,k,nlocal−x¯m,k,nXm,k,nlocale2ψm,n.
Further, formula (27) can be written as
(28)f1ψm,n=y~m,k,nf2Xm,k,nlocal−ym,k,nXm,k,nlocaleψm,n+x~m,k,nf2Xm,k,nlocal−xm,k,nXm,k,nlocale2ψm,n,
wheref2Xm,k,nlocal=1−lnXm,k,nlocal−1/Xm,k,nlocal.
Sincelnx+1/x takes the minimal value of 1 when x=1 and Xm,k,nlocal≠1, then the inequality 1−lnXm,k,nlocal−1/Xm,k,nlocal<0 holds. Moreover, because xm,k,n, x~m,k,n, ym,k,n, y~m,k,n, and Xm,k,nlocal are all positive, both x~m,k,nf2Xm,k,nlocal−xm,k,n/Xm,k,nlocal and y~m,k,nf2Xm,k,nlocal−ym,k,n/Xm,k,nlocal are less than 0. In summary, since eψm,n and e2ψm,n are convex function with respect to ψm,n, fψm,n is a concave function with respect to ψm,n.
It can be seen that constraint (26) is nonconvex. Thus, we perform first-order Taylor expansions of eψm,n and e2ψm,n at the feasible point ψm,nlocal=lnpm,np,local. Next, constraint (26) can be approximately written as
(29)z⌢m,k,n+y⌢m,k,nTL1m,n+x⌢m,k,nTL2m,n+e−φm,k,nln2Bz~m,k,n+y~m,k,neψm,n+x~m,k,ne2ψm,n≤0,∀k∈Km,
where the first-order Taylor expansions ofeψm,n and e2ψm,n are TL1m,n=eψm,nlocal+eψm,nlocalψm,n−ψm,nlocal and TL2m,n=e2ψm,nlocal+2e2ψm,nlocalψm,n−ψm,nlocal, respectively. Moreover, TL1m,n and TL2m,n need to be greater than zero to approximate eψm,n and e2ψm,n, respectively. Obviously, constraint (29) is convex. Moreover, the objective function of SP2.1 can be transformed into ωE∑k=1KmτDm,k/Tc−τeψm,n+pm,nDm,keϕm,k,n based on the φm,k,n and ψm,n.
Next, we process constraints (16b) and (16c). Firstly, constraint (16b) can equivalently be written as
(30a)z^m,k,n+y^m,k,neψm,n+x^m,k,ne2ψm,n≤0,∀k∈Km,where
(30b)x^m,k,n=υm,k,nx~m,k,n−xm,k,n,(30c)y^m,k,n=υm,k,ny~m,k,n−ym,k,n,(30d)z^m,k,n=υm,k,nz~m,k,n−zm,k,n,(30e)υm,k,n=eTcDm,kln2/BTc−τTnmax−1.
Based on analyses of different situations ofx^m,k,n, we rewrite the constraint (30a) as follows:
(31)ψm,n⩽ln−z^m,k,n/y^m,k,n,x^m,k,n=0,y^m,k,n>0,ψm,n⩾ln−z^m,k,n/y^m,k,n,x^m,k,n=0,y^m,k,n<0,ψm,n∈ℝ,x^m,k,n=0,y^m,k,n=0,lnslm,k,n⩽ψm,n⩽lnshm,k,n,x^m,k,n>0,ψm,n⩽lnslm,k,n,ψm,n⩾lnshm,k,n,x^m,k,n<0,,∀k∈Km,
whereslm,k,n=−y^m,k,n−y^m,k,n2−4x^m,k,nz^m,k,n/2x^m,k,n, shm,k,n=−y^m,k,n+y^m,k,n2−4x^m,k,nz^m,k,n/2x^m,k,n. Moreover, ℝ represents the set of real numbers.
For the constraint (16c), we choose sector area m for analyses. If UD k in the sector area m satisfies constraint Tm,k,n≥Tnmin, the constraint can be equivalently written as follows:
(32a)żm,k,n+ẏm,k,neψm,n+ẋm,k,ne2ψm,n≤0,where
(32b)ẋm,k,n=xm,k,n−νm,k,nx~m,k,n,(32c)ẏm,k,n=ym,k,n−νm,k,ny~m,k,n,(32d)żm,k,n=zm,k,n−νm,k,nz~m,k,n,(32e)νm,k,n=eTcDm,kln2/BTc−τTnmin−1.Define that the UDk^ in the sector area m^ during the n-th status update satisfies constraint (32a). Since the constraint (32a) is similar to the constraint (30a), the constraints after processing are shown as follows.
(33)ψm^,n≤ln−żm^,k^,nẏm^,k^,n,ẋm^,k^,n=0,ẏm^,k^,n>0,ψm^,n≥ln−żm^,k^,nẏm^,k^,n,ẋm^,k^,n=0,ẏm^,k^,n<0,lnslm^,k^,n≤ψm^,n≤lnshm^,k^,n,ẋm^,k^,n>0,ψm^,n≤lnslm^,k^,n,ẋm^,k^,n<0,ψm^,n≥lnshm^,k^,n,ẋm^,k^,n<0.Algorithm 2: Obtaining the optimal solutions of SP2.1.1.
1: ObtainM1=∅ and M2=∅ based on analyses for all sector areas.2: For all sector areas inM1, search pm,np∗ based on constraints (31) and (34c)-(34d).3: Seto=1.4:repeat5: Obtainpm,np∗o,∀m∈M2\mM2o by the one-dimensional search method based on constraints (31), (34c), and (34d).6: For all UDs belonging to the setKF, search pmM2o,np,k∗ based on constraints (31), (33), (34c), and (34d)) and further obtain pmM2o,np∗.7: CalculateEmM2o=ωE∑m∈M2∑k=1KmEm,k,n based on the power setpm,np∗o,pmM2o,np∗.8:o=o+1.9: untilo>M210: Choose the setpm,np∗o,pmM2o,np∗ with the minimal EmM2o as the optimal pilot transmit powers of all sector areas inM2.11:Output: pm,np∗.In summary, the SP2.1 can be written approximately as follows:(34a)SP2.1.1:minψm,n,φm,k,nωE∑k=1KmτDm,kTc−τeψm,n+pm,nDm,keφm,k,n,(34b)s.t.Constraints24,26,28,(34c)TL1m,k,n>0,TL2m,k,n>0,∀k∈Km,(34d)lnPmin<ψm,n≤lnPmax,wherePmin=10−8, and it is to obtain a certain lower bound of ψm,n for subsequent processing.Obviously, the SP2.1.1 is convex. However, due to a large number of variables and the high complexity of SP2.1.1, it is difficult to utilize the CVX toolkit for solving the problem. Therefore, we further analyze the problem and propose a search algorithm. Firstly, based on the Lemma1, x⌢m,k,n, y⌢m,k,n, and z⌢m,k,n are negative. In addition, TL1m,n and TL2m,n are positive. Thus, z⌢m,k,n+y⌢m,k,nTL1m,n+x⌢m,k,nTL2m,n<0. Moreover, since x~m,k,n, y~m,k,n, and z~m,k,n are positive, z~m,k,n+y~m,k,neψm,n+x~m,k,ne2ψm,n>0. In summary, constraint (29) can be equivalently expressed as
(35)eφm,k,n≥−z~m,k,n+y~m,k,neψm,n+x~m,k,ne2ψm,nln2Bz⌢m,k,n+y⌢m,k,nTL1m,n+x⌢m,k,nTL2m,n,∀k∈Km.When the objective function of SP2.1.1 is optimal, the equality in the constraint (35) always holds. Thus, the objective function of SP2.1.1 is a function with respect to ψm,n. In other words, a one-dimensional search algorithm is proposed for obtaining the optimal solutions of SP2.1.1. In particular, since the proposed search algorithm is based on the analysis of SP2.1.1, its computational complexity is lower than that of general search algorithms. Finally, we can obtain the stationary point of SP2.1 by iteratively optimizing SP2.1.1. The detailed solution process of obtaining the optimal solution of SP2.1.1 is shown in Algorithm 2. In the algorithm, if there is no UD that satisfy constraint (33) in sector area m, then m∈M1. Otherwise, m∈M2. Moreover, mM2o represents the area number of the o-th element in the set M2, and M2 represents the number of all elements in the set M2. Moreover, the feasible region of ψm,n of each UD k in the sector area mM2o can be obtained based on constraints (31), (33), (34c), and (34d). If the feasible region is not empty, k∈KF. In addition, pmM2o,np∗ is the pmM2o,np,k∗ that minimizes ∑k∈mM2oEmM2o,k,n.


### 3.3. Data Transmit Power Optimization

The data transmit power optimization problem can be formulated with giventn,cn,pm,np,T,ruav, since pm,n has no effect on the energy consumptions of UDs in the sector area m~∈M\m during any status update and has no effect on the energy consumptions of UDs in the sector area m during other status updates. Therefore, the data transmit power optimization problem can be investigated with given status update n and sector area m. Specifically, the simplified optimization problem can be given as follows:
(36a)SP3:minpm,nωE∑m=1M∑k=1Kmτpm,npDm,k/Tc−τ+pm,nDm,kRm,k,n,(36b)s.t.Tntr≤Tnmax,(36c)Tntr≥Tnmin,(36d)0<pm,n≤Pmax, where
(36e)Tnmax=minTF,tn+1−tn,cn−tn,1≤n≤N−1,minTF,cn−tn,n=N,(36f)Tnmin=tn+1−tn−Tncom,∀n∈N\N.Since the objective function of SP3 is nonconvex, we introduce the auxiliary variablesϖm,k,n which satisfy constraints Rm,k,n≥e−ϖm,k,n,∀k∈Km. In addition, we define that eμm,n=pm,n, and the constraints above can be rewritten as follows:
(37a)lneμm,nam,k,n+bm,k,n+cm,k,n≥e−ϖm,k,n1n2B+lneμm,nbm,k,n+cm,k,n,∀k∈Km,where
(37b)am,k,n=2LKm,k,n+2L2Km,k,ngm,k,nηm,k,n+gm,k,nL2Km,k,n2+L+L2gm,k,nηm,k,n2,(37c)bm,k,n=Km,k,n+1∑i=1,i≠kKmgm,i,nΔm,k,i,n+Lgm,k,nKm,k,n+ηm,k,n1+gm,k,npm,np,(37d)cm,k,n=N0BLKm,k,n+1Km,k,n+ηm,k,n.The functionlneμm,nam,k,n+bm,k,n+cm,k,n in constraint (37a) is a convex function with respect to μm,n. Moreover, e−ϖm,k,n1n2/B and lneμm,nbm,k,n+cm,k,n in constraint (37a) are convex functions with respect to ϖm,k,n and μm,n, respectively. In order to transform the nonconvex constraint (37a) into a convex constraint, we obtain the first-order Taylor expansion of the function lneμm,nam,k,n+bm,k,n+cm,k,n at the feasible point μm,nlocal=lnpm,nlocal. Then, constraint (37a) can be written approximately as
(38)lneμm,nlocalam,k,n+bm,k,n+cm,k,n+eμm,nlocalam,k,n+bm,k,nμm,n−μm,nlocalam,k,n+bm,k,neμm,nlocal+cm,k,n≥e−ϖm,k,n1n2B+lneμm,nbm,k,n+cm,k,n,∀k∈Km.Sincelneμm,nbm,k,n+cm,k,n and e−ϖm,k,n are convex functions of μm,n and ϖm,k,n, constraint (38) is convex. It is worth noting that the first-order Taylor expansion in constraint (38) has to be greater than zero. Moreover, constraint (37b) can be rewritten as follows:
(39)pm,n≥maxkcm,k,neTcDm,kln2/BTc−τTnmax−1am,k,n−bm,k,neTcDm,kln2/BTc−τTnmax−1,∀k∈Km.In constraint (36c), if UD k in the sector area m satisfies constraint (36c), the UD k’s data transmit power satisfies the following constraint.
(40)pm,nk≤cm,k,neTcDm,kln2/BTc−τTnmin−1am,k,n−bm,k,neTcDm,kln2/BTc−τTnmin−1.We setpm,n≤maxkcm,k,neTcDm,kln2/BTc−τTnmin−1/am,k,n−bm,k,neTcDm,kln2/BTc−τTnmin−1 based on constraint (35). In summary, we denote that
(41a)pm,nmin=maxmaxkcm,k,neTcDm,kln2/BTc−τTnmax−1am,k,n−bm,k,neTcDm,kln2/BTc−τTnmax−1,Pmin,(41b)pm,nmax=minmaxkcm,k,neTcDm,kln2/BTc−τTnmin−1am,k,n−bm,k,neTcDm,kln2/BTc−τTnmin−1,Pmax,where thePmin is the same as the Pmin in the constraint (34d).If there is no UD that satisfies constraint (36c) in the sector area m, then m∈M3. Otherwise, m∈M4. Then, the following constraints hold based on the eμm,n=pm,n.
(42)lnpm,nmin≤μm,n≤lnPmax,∀m∈M3,lnpm,nmin≤μm,n≤lnpm,nmax,∀m∈M4.In summary, the problem SP3 can be approximately expressed as follows:(43a)SP3.1:minμm,n,ϖm,k,nωE∑k=1KmτDm,k/Tc−τ+eμm,nDm,keϖm,k,n,(43b)s.t.Constraints33,37.Sinceeϖm,k,n and eμm,n+ϖm,k,n are convex functions, the objective function is convex. Therefore, SP3.1 is a convex problem. However, the CVX toolkit is difficult to solve SP3.1 because of the high complexity of the problem. Next, we further analyze the problem and propose a search algorithm to solve it. Firstly, constraint (38) can be rewritten as follows:
(44a)eϖm,k,n≥1n2BYm,k,n+Wm,k,nμm,n−μm,nlocal−lneμm,nbm,k,n+cm,k,n,(44b)Ym,k,n+Wm,k,nμm,n−μm,nlocal−lneμm,nbm,k,n+cm,k,n>0,whereWm,k,n=am,k,n+bm,k,neμm,nlocal/am,k,n+bm,k,neμm,nlocal+cm,k,n and Ym,k,n=lneμm,nlocalam,k,n+bm,k,n+cm,k,n.It can be seen that when the minimal objective function of SP3.1 is obtained, the equation in constraint (44a) holds. Therefore, we only need to perform one-dimensional search within the feasible interval of μm,n to obtain the optimal solution of SP3.1. Specially, we further analyze the problem to reduce the number of searches. Finally, we can adopt SCA to iteratively optimize SP3.1 for obtaining the stationary point of SP3. The detailed process of obtaining the optimal solution of the SP3.1 is shown in Algorithm 3, where mM4o represents the area number of the o-th element in the set M4, and M4 represents the number of all elements in the set M4.Algorithm 3: Obtaining the optimal solutions of SP3.1.
1: ObtainM3 and M4.2: For all sector areas inM3, search μm,n∗ and further obtain pm,n∗.3: Seto=1.4:repeat5: For all areasm∈M4\mM4o, search μm,n∗ within the interval lnpm,nmin,lnPmax and further obtain pm,n∗o.6: SearchμmM4o,n∗ within the interval lnpm,nmin,lnpm,nmax and further obtain pmM4o,n∗.7: CalculateEmM4o=ωE∑m∈M4∑k=1KmEm,k,n based on the power set pm,n∗o,pmM4o,n∗.8:o=o+1.9:untilo>M410: Choose the setpm,n∗o,pmM4o,n∗ with the minimal EmM2o as the optimal data transmit powers of all sector areas in M4.11:Output: pm,n∗.


### 3.4. Service Period Optimization

The service period optimization problem can be formulated as follows:(45a)SP4:minTωA∑m=1M∑k=1KmΔ¯m,k+ωE∑n=1N∑m=1M∑k=1KmEm,k,n+ωU∑m=1MEmfly,(45b)s.t.Constraints9b,9d−9f,9l.Algorithm 4: Joint Scheduling and Power Optimization.
1: InitializeZ0=tn,cn,pm,np,pm,n,T,ruav0, and calculate the weighted sum OBJ0 based on Z0.2: Set the iteration numberl=0, and the tolerance error ε=10−5.3:repeat4:l=l+1.5: Obtaintnl and cnl with given pm,nppm,n,T,ruavl−1 by the Algorithm 1 and SCA.6: Seto=0, pm,np,local=pm,npl−1 and pm,np,∗0=pm,npl−1.7:repeat8:  Seto=o+1.9:  Obtain the stationary points of pilot transmit powerspm,np,∗o based on the Algorithm 2 and feasible point pm,np,local and withgiventnl,cnl,pm,nl−1,Tl−1,ruavl−1.10:  Setpm,np,local=pm,np,∗o.11:until∑n=1N∑m=1Mpm,np,∗o−pm,np,∗o−1≤ε12: Setpm,npl=pm,np,∗o.13: Seto=0, pm,nlocal=pm,nl−1 and pm,n∗0=pm,nl−1.14:repeat15:  Seto=o+1.16:  Obtain the stationary points of data transmit powerspm,n∗o based on Algorithm 3 and feasible point pm,nlocal and with giventnl,cnl,pm,npl,Tl−1,ruavl−1.17:  Setpm,nlocal=pm,n∗o.18:until∑n=1N‍∑m=1M‍pm,n∗o−pm,n∗o−1≤ε19: Setpm,nl=pm,n∗o.20: Utilize one-dimensional search algorithm to obtainTl with given tnl,cnl,pm,npl,pm,nl,ruavl−1.21: Utilize one-dimensional search algorithm to obtainRl with given tnl,cnl,pm,npl,pm,nl,Tl.22: Obtain the weighted sumOBJl based on Zl.23:untilOBJl−1−OBJl≤ε24:Output:Zl.The coordinate of the UAVm at moment t is qm,t=qxm,t,qym,t,HT,∀m∈, where qxm,t=ruavcos2πt/T+ζm and qym,t=ruavsin2πt/T+ζm. Obviously, the UAV’s location is a complex function with respect to the service period. Therefore, the UD’s transmission energy consumption Em,k,n and the maximal transmission delay of the n-th status update Tntr are complex functions with respect to the service period. Function analysis method and SCA method are difficult to be used for the objective function and constraints of SP4. Therefore, we adopt a one-dimensional search algorithm to obtain the near-optimal solution of SP4.


### 3.5. Flight Radius Optimization

The flight radius optimization problem can be formulated as follows:(46a)SP5:minruavωE∑n=1N∑m=1M∑k=1KmEm,k,n+ωU∑m=1MEmfly,(46b)s.t.Constraints9b,9d−9f,9k.Similarly, the UAV’s location is a complex function with respect to the flight radius. Therefore, the UD’s transmission energy consumptionEm,k,n and the maximal transmission delay of the n-th status update Tntr are complex functions with respect to the flight radius. Function analysis method and SCA method are difficult to be used for the objective function and constraints of SP5. Therefore, we adopt a one-dimensional search algorithm to obtain the near-optimal solution of SP5.


### 3.6. The Iterative Algorithm and Analysis

Finally, we propose an iterative algorithm for joint scheduling and power optimization (JSPO). The JSPO is shown in Algorithm4. Next, we analyze the convergence of the JSPO. Although the loop in the JSPO is comprised of five nonconvex subproblems, we utilize greedy, SCA, and one-dimensional search methods to obtain their near-optimal solutions or stationary points, respectively. Define OBJ=ωA∑m=1M∑k=1KmΔ¯m,k+ωE∑n=1N∑m=1M∑k=1KmEm,k,n+ωU∑m=1MEmfly. In each iteration, since the near-optimal solution or stationary point of each subproblem can be obtained with given other variables, the weighted sum OBJ is monotonically nonincreasing. Moreover, the optimal solution of the OP is a lower bound of the solution obtained by the JSPO. In summary, the JSPO can converge.Moreover, the computational complexity of the JSPO depends mainly on the five decomposed subproblems in the loop. First, the computational complexity of solving SP1.1 mainly comes from Algorithm1. In Algorithm 1, we first select N1 sampling points for t1. Then, for each t1, we use the greedy method to select each subsequent transmission start moment under the N2 sampling points. Therefore, the computational complexity of Algorithm 1 is ON1N2N−1. Second, the computational complexity of solving SP2.1.1 mainly comes from the loop in Algorithm 2. In the worst case, Algorithm 2 requires M iterations. In each iteration, a one-dimensional search with N3 sample points is conducted for M−1 sector areas, and kmean one-dimensional searches with N3 sample points are conducted for a sector area, where kmean represents the average number of UDs in a sector area. Therefore, the computational complexity of Algorithm 2 is OMM−1N3+kmeanN3. Third, the computational complexity of solving SP3.1 mainly comes from the loop in Algorithm 3. In the worst case, Algorithm 3 requires M iterations. In each iteration, a one-dimensional search with N4 sample points is conducted for M sector areas. Therefore, the computational complexity of Algorithm 3 is OM2N4. SP4 and SP5 are both solved by the one-dimensional search algorithm, and the number of samples is N5 and N6, respectively. In summary, the computational complexity of the JSPO is OI1N1N2N−1+I2MM−1N3+kmeanN3+I3M2N4+N5+N6, where I1, I2, and I3 are the number of iterations of the JSPO, Algorithm 2, and Algorithm 3, respectively.


## 3.1. Transmission and Computing Start Moment Optimization

Since the transmission start moment and the computing start moment are tightly coupled, the subproblem SP1 jointly optimizes the two types of variables. With givenpm,np,pm,n,T,ruav, the transmission and computing start moment optimization problem can be formulated as follows:
(10a)SP1:mintn,cnωA∑m=1M∑k=1KmΔ¯m,k+ωE∑n=1N∑m=1M∑k=1KmEm,k,n,(10b)Tntr≤TF,∀n∈N,(10c)t1≥0,(10d)tn≥tn−1+Tn−1tr,∀n∈N\1,(10e)tn≤tn−1+Tn−1tr+Tn−1com,∀n∈N\1,(10f)cn≥tn+Tntr,∀n∈N,(10g)cn≥cn−1+Tn−1com,∀n∈N\1,(10h)cN+TNcom≤T.Although there is a strong coupling relationship betweencn and tn, we can simplify the SP1 by analyzing the objective function. Specifically, we obtain the partial derivative of the objective function with respect to cn as
(11a)ωA∂∑m=1M∑k=1KmΔ¯m,k∂c1=ωAT∑m=1M∑k=1Km∑n=1Nt1+Δm,k0,(11b)ωA∂∑m=1M∑k=1KmΔ¯m,k∂cn=ωAT∑m=1M∑k=1Km∑n=1Ntn−tn−1,∀n∈N\1.It can be seen that the objective function is a linear expression ofcn. Since t1+Δm,k0≥0,∀m∈M,k∈Km and tn−tn−1≥Tn−1tr>0,∀n∈N\1, the objective function is monotonically increasing with respect to cn. Therefore, if cn does not take the minimum value within its feasible region, a smaller cn can always be found to make the objective function smaller. In summary, when the objective function is optimal, the formulascn=tn+Tntr,n=1maxtn+Tntr,cn−1+Tn−1com,1<n≤Nalways hold. Therefore, the transmission and computing start moment optimization problem can be equivalently transformed as follows:(12a)SP1.1:mintnωA∑m=1M∑k=1KmΔ¯m,k+ωE∑n=1N∑m=1M∑k=1KmEm,k,n,(12b)Tntr≤TF,∀n∈N,(12c)t1≥0,(12d)tn≥tn−1+Tn−1tr,∀n∈N\1,(12e)tn≤tn−1+Tn−1tr+Tn−1com,∀n∈N\1,(12f)tN+TNtr+TNcom≤T.Since the objective function of the SP1.1 is still a nonconvex function oftn, it is difficult to solve it by convex optimization techniques. In addition, both Tntr and Em,k,n are complex functions of tn. It is intractable to analyze tn in the objective function of the SP1.1. Therefore, search algorithms are more suitable for solving the SP1.1. However, the number of variables in the SP1.1 is N, and the adjacent variables tn and tn+1 are coupled. If the exhaustive search algorithm is performed for all variables, the computational complexity of the exhaustive search algorithm is highly exponential. Therefore, the exhaustive search algorithm is not suitable for solving the SP1.1.In order to obtain an approximately optimal solution with lower complexity, we further analyze the SP1.1. Whent1 is fixed, there is a optimal set of tn,∀n∈N\1 to minimize the objective function. Moreover, the constraints (12d) and (12e) indicate the Markov properties of the transmission start moments, i.e., tn+1 is only related to tn. In other words, the SP1.1 can be divided into multiple subproblems step by step. For example, when t1 is fixed, the subproblem of t2 can be solved. When t2 is fixed, the subproblem of t3 can be solved and so on. Based on the characteristics above, the greedy rule can be used to solve each sub-problem above. Specifically, when tn is fixed, we only choose tn+1 that minimizes the current weighted sum as the solution of tn+1. The current weighted sum is shown in formulas (13) and (14), where c¯n=maxtn+Tntr,cn−1+Tn−1com. The specific steps of the algorithm are shown in Algorithm 1, where N1 is the number of sampling points of t1, and t1max is the maximum feasible value of t1 and can be obtained by search algorithms. Specially, Tn is a set of tn which are generated from N2 sampling points and satisfies constraints tn≥tn−1+Tn−1tr, tn≤tn−1+Tn−1tr+Tn−1com, and Tntr≤TF within the interval tn−1+Tn−1tr,tn−1+Tn−1tr+Tn−1com. Moreover, TN is a set of tN which are generated from N2 sampling points and satisfies constraints tN≥tN−1+TN−1tr, tN≤tN−1+TN−1tr+TN−1com, tN+TNtr+TNcom≤T, and TNtr≤TF within the interval tN−1+TN−1tr,tN−1+TN−1tr+TN−1com.
(13)cwsn=ωA2T∑m=1M∑k=1Kmtn−tn−12c¯n+TCm,k,n−tn−tn−1+ωE∑m=1M∑k=1KmEm,k,n,∀n∈N\1,N,(14)cwsN=ωA2T∑m=1M∑k=1KmtN−tN−12c¯N+TCm,k,N−tN−tN−1+T−tN2+ωE∑m=1M∑k=1KmEm,k,N.Algorithm 1: Obtaining the near-optimal solutions of SP1.1.
1:ξ=t1max/N1 and o=12:repeat3: Sett1o=o−1ξ and n=1.4: CalculateTntr based on formula (3a).5: ifTntr>TFthen6:o=o+1.7:else8:n=n+1.9:repeat10:if2≤n≤N−1then11:    Find the setTn of tn.12:    ifTn=∅then13:o=o+1.14:break.15:else16:     Choosetn′ in the Tn that minimizes cwsn as tno and set n=n+1.17:end if18:end if19:ifn=Nthen20:    Find the setTN of tN.21:ifTN=∅then22:o=o+1.23:break.24:else25:     ChoosetN′ in the set TN that minimizes cwsN as tNo and set n=n+1.26:end if27:end if32128:untiln=N+129:end if30:untilt1o≥t1max31: Choose the settno with the smallest objective function as tn∗.32:Output: tn∗.


## 3.2. Pilot Transmit Power Optimization

With giventn,cn,pm,n,T,ruav, the pilot transmit power optimization problem can be formulated as follows:
(15a)SP2:minpm,npωE∑n=1N∑m=1M∑k=1Kmτpm,npDm,k/Tc−τ+pm,nDm,kRm,k,n,(15b)Tntr≤TF,∀n∈N,(15c)Tntr≤tn+1−tn,∀n∈N\N,(15d)Tntr≥tn+1−tn−Tncom,∀n∈N\N,(15e)Tntr≤cn−tn,∀n∈N,(15f)0<pm,np≤Pmax,∀m∈M,n∈N.It can be seen that the objective function of the SP2 only includes UDs’ energy consumptions. Moreover,pm,np does not affect the energy consumptions of UDs in different status updates and in different sector areas. Therefore, the SP2 can be equivalently transformed into a problem of minimizing energy consumptions of UDs in sector area m and during status update n. Specifically, the equivalent problem SP2.1 can be given as follows:
(16a)SP2.1:minpm,npωE∑k=1Kmτpm,npDm,k/Tc−τ+pm,nDm,kRm,k,n,(16b)s.t.Tntr≤Tnmax,(16c)Tntr≥Tnmin,(16d)0<pm,np≤Pmax,where(16e)Tnmax=minTF,tn+1−tn,cn−tn,1≤n≤N−1,minTF,cn−tn,n=N.(16f)Tnmin=tn+1−tn−Tncom,∀n∈N\N.It can be seen that the objective function of the SP2.1 is nonconvex, and constraints (16b)-(16c) need to be further processed. Thus, we convert the SP2.1 into an approximate convex problem and utilize successive convex approximation (SCA) to obtain the stationary point of the SP2.1. First, we deal with the objective function of the SP2.1. The auxiliary variables φm,k,n are introduced, which satisfy constraints Rm,k,n≥e−φm,k,n,∀k∈Km. Then, we further deal with the constraints above.Firstly, the transmission rate can be equivalently written as(17)Rm,k,n=Blog21+zm,k,n+ym,k,npm,np+xm,k,npm,np2z~m,k,n+y~m,k,npm,np+x~m,k,npm,np2,where the expressions ofzm,k,n, z~m,k,n, ym,k,n, y~m,k,n, xm,k,n, and x~m,k,n are shown in formulas (18–23). Therefore, the constraints Rm,k,n≥e−φm,k,n,∀k∈Km can be equivalently expressed as formula (24):
(18)zm,k,n=L2Km,k,n2pm,ngm,k,n,(19)z~m,k,n=pm,nKm,k,n+1∑i=1,i≠kKmgm,i,nKm,k,nKm,i,nϕm,k,i,n2+LKm,k,nKm,i,n+1+Lpm,ngm,k,nKm,k,n+N0BLKm,k,n+1Km,k,n,(20)ym,k,n=2pm,ngm,k,n2L2Km,k,n2+pm,n2LKm,k,n+2L2Km,k,ngm,k,n2,(21)y~m,k,n=2pm,nKm,k,n+1∑i=1,i≠kKmgm,k,ngm,i,nKm,k,nKm,i,nϕm,k,i,n2+LKm,k,nKm,i,n+1+pm,nKm,k,n+1∑i=1,i≠kKmLgm,i,ngm,k,n+Lpm,ngm,k,nKm,k,ngm,k,n+gm,k,n+N0BLKm,k,n+12Km,k,ngm,k,n+gm,k,n,(22)xm,k,n=pm,ngm,k,n3L2Km,k,n2+pm,ngm,k,n32LKm,k,n+2L2Km,k,n+pm,nL+L2gm,k,n3,(23)x~m,k,n=pm,nKm,k,n+1∑i=1,i≠kKmgm,i,ngm,k,n2Km,k,nKm,i,nϕm,k,i,n2+LKm,k,nKm,i,n+1+pm,nKm,k,n+1∑i=1,i≠kKmLgm,i,ngm,k,n2+N0BLgm,k,n2Km,k,n+12,(24)lnz¯m,k,n+y¯m,k,npm,np+x¯m,k,npm,np2z~m,k,n+y~m,k,npm,np+x~m,k,npm,np2≥e−φm,k,nln2B,∀k∈Km,where z¯m,k,n=zm,k,n+z~m,k,n, y¯m,k,n=ym,k,n+y~m,k,n, x¯m,k,n=xm,k,n+x~m,k,n.We setXm,k,n=z¯m,k,n+y¯m,k,npm,np+x¯m,k,npm,np2/z~m,k,n+y~m,k,npm,np+x~m,k,npm,np2>0. Since lnXm,k,n is a concave function with respect to Xm,k,n, we obtain the first-order Taylor expansion of lnXm,k,n at the feasible point Xm,k,nlocal=z¯m,k,n+y¯m,k,npm,np,local+x¯m,k,npm,np,local2/z~m,k,n+y~m,k,npm,np,local+x~m,k,npm,np,local2. Then, the constraint (24) can be written approximately as follows:
(25)lnXm,k,nlocal+z¯m,k,n+y¯m,k,npm,np+x¯m,k,npm,np2Xm,k,nlocalz~m,k,n+y~m,k,npm,np+x~m,k,npm,np2−1≥e−φm,k,nln2B,∀k∈1,⋯,Km.It is worth noting that constraint (25) does not guarantee the validity of constraint (24), namely, it cannot ensure that we can obtain the upper bound of the objective function of SP2.1 for minimization. However, the effectiveness of constraint (25) can be seen from the simulation section. Therefore, constraint (25) is acceptable. Next, we introduce variables ψm,n and set eψm,n=pm,np. Then, constraint (25) can be equivalently written as follows:
(26)z⌢m,k,n+y⌢m,k,neψm,n+x⌢m,k,ne2ψm,n+e−φm,k,nln2Bz⌢m,k,n+y⌢m,k,neψm,n+x⌢m,k,ne2ψm,n≤0,∀k∈Km,where x⌢m,k,n=x~m,k,n−x~m,k,nlnXm,k,nlocal−x¯m,k,n/Xm,k,nlocal, y⌢m,k,n=y~m,k,n−y~m,k,nlnXm,k,nlocal−ym,k,n/Xm,k,nlocal, and z⌢m,k,n=z~m,k,n−z~m,k,nlnXm,k,nlocal−z¯m,k,n/Xm,k,nlocal. Moreover, we define a function fψm,n=y⌢m,k,neψm,n+x⌢m,k,ne2ψm,n.Lemma 1.
fψm,n is a concave function with respect to ψm,n.Proof.
The functionfψm,n can be written equivalently as
(27)fψm,n=y~m,k,n−y~m,k,nlnXm,k,nlocal−y¯m,k,nXm,k,nlocaleψm,n+x~m,k,n−x~m,k,nlnXm,k,nlocal−x¯m,k,nXm,k,nlocale2ψm,n.
Further, formula (27) can be written as
(28)f1ψm,n=y~m,k,nf2Xm,k,nlocal−ym,k,nXm,k,nlocaleψm,n+x~m,k,nf2Xm,k,nlocal−xm,k,nXm,k,nlocale2ψm,n,
wheref2Xm,k,nlocal=1−lnXm,k,nlocal−1/Xm,k,nlocal.
Sincelnx+1/x takes the minimal value of 1 when x=1 and Xm,k,nlocal≠1, then the inequality 1−lnXm,k,nlocal−1/Xm,k,nlocal<0 holds. Moreover, because xm,k,n, x~m,k,n, ym,k,n, y~m,k,n, and Xm,k,nlocal are all positive, both x~m,k,nf2Xm,k,nlocal−xm,k,n/Xm,k,nlocal and y~m,k,nf2Xm,k,nlocal−ym,k,n/Xm,k,nlocal are less than 0. In summary, since eψm,n and e2ψm,n are convex function with respect to ψm,n, fψm,n is a concave function with respect to ψm,n.
It can be seen that constraint (26) is nonconvex. Thus, we perform first-order Taylor expansions of eψm,n and e2ψm,n at the feasible point ψm,nlocal=lnpm,np,local. Next, constraint (26) can be approximately written as
(29)z⌢m,k,n+y⌢m,k,nTL1m,n+x⌢m,k,nTL2m,n+e−φm,k,nln2Bz~m,k,n+y~m,k,neψm,n+x~m,k,ne2ψm,n≤0,∀k∈Km,
where the first-order Taylor expansions ofeψm,n and e2ψm,n are TL1m,n=eψm,nlocal+eψm,nlocalψm,n−ψm,nlocal and TL2m,n=e2ψm,nlocal+2e2ψm,nlocalψm,n−ψm,nlocal, respectively. Moreover, TL1m,n and TL2m,n need to be greater than zero to approximate eψm,n and e2ψm,n, respectively. Obviously, constraint (29) is convex. Moreover, the objective function of SP2.1 can be transformed into ωE∑k=1KmτDm,k/Tc−τeψm,n+pm,nDm,keϕm,k,n based on the φm,k,n and ψm,n.
Next, we process constraints (16b) and (16c). Firstly, constraint (16b) can equivalently be written as
(30a)z^m,k,n+y^m,k,neψm,n+x^m,k,ne2ψm,n≤0,∀k∈Km,where
(30b)x^m,k,n=υm,k,nx~m,k,n−xm,k,n,(30c)y^m,k,n=υm,k,ny~m,k,n−ym,k,n,(30d)z^m,k,n=υm,k,nz~m,k,n−zm,k,n,(30e)υm,k,n=eTcDm,kln2/BTc−τTnmax−1.
Based on analyses of different situations ofx^m,k,n, we rewrite the constraint (30a) as follows:
(31)ψm,n⩽ln−z^m,k,n/y^m,k,n,x^m,k,n=0,y^m,k,n>0,ψm,n⩾ln−z^m,k,n/y^m,k,n,x^m,k,n=0,y^m,k,n<0,ψm,n∈ℝ,x^m,k,n=0,y^m,k,n=0,lnslm,k,n⩽ψm,n⩽lnshm,k,n,x^m,k,n>0,ψm,n⩽lnslm,k,n,ψm,n⩾lnshm,k,n,x^m,k,n<0,,∀k∈Km,
whereslm,k,n=−y^m,k,n−y^m,k,n2−4x^m,k,nz^m,k,n/2x^m,k,n, shm,k,n=−y^m,k,n+y^m,k,n2−4x^m,k,nz^m,k,n/2x^m,k,n. Moreover, ℝ represents the set of real numbers.
For the constraint (16c), we choose sector area m for analyses. If UD k in the sector area m satisfies constraint Tm,k,n≥Tnmin, the constraint can be equivalently written as follows:
(32a)żm,k,n+ẏm,k,neψm,n+ẋm,k,ne2ψm,n≤0,where
(32b)ẋm,k,n=xm,k,n−νm,k,nx~m,k,n,(32c)ẏm,k,n=ym,k,n−νm,k,ny~m,k,n,(32d)żm,k,n=zm,k,n−νm,k,nz~m,k,n,(32e)νm,k,n=eTcDm,kln2/BTc−τTnmin−1.Define that the UDk^ in the sector area m^ during the n-th status update satisfies constraint (32a). Since the constraint (32a) is similar to the constraint (30a), the constraints after processing are shown as follows.
(33)ψm^,n≤ln−żm^,k^,nẏm^,k^,n,ẋm^,k^,n=0,ẏm^,k^,n>0,ψm^,n≥ln−żm^,k^,nẏm^,k^,n,ẋm^,k^,n=0,ẏm^,k^,n<0,lnslm^,k^,n≤ψm^,n≤lnshm^,k^,n,ẋm^,k^,n>0,ψm^,n≤lnslm^,k^,n,ẋm^,k^,n<0,ψm^,n≥lnshm^,k^,n,ẋm^,k^,n<0.Algorithm 2: Obtaining the optimal solutions of SP2.1.1.
1: ObtainM1=∅ and M2=∅ based on analyses for all sector areas.2: For all sector areas inM1, search pm,np∗ based on constraints (31) and (34c)-(34d).3: Seto=1.4:repeat5: Obtainpm,np∗o,∀m∈M2\mM2o by the one-dimensional search method based on constraints (31), (34c), and (34d).6: For all UDs belonging to the setKF, search pmM2o,np,k∗ based on constraints (31), (33), (34c), and (34d)) and further obtain pmM2o,np∗.7: CalculateEmM2o=ωE∑m∈M2∑k=1KmEm,k,n based on the power setpm,np∗o,pmM2o,np∗.8:o=o+1.9: untilo>M210: Choose the setpm,np∗o,pmM2o,np∗ with the minimal EmM2o as the optimal pilot transmit powers of all sector areas inM2.11:Output: pm,np∗.In summary, the SP2.1 can be written approximately as follows:(34a)SP2.1.1:minψm,n,φm,k,nωE∑k=1KmτDm,kTc−τeψm,n+pm,nDm,keφm,k,n,(34b)s.t.Constraints24,26,28,(34c)TL1m,k,n>0,TL2m,k,n>0,∀k∈Km,(34d)lnPmin<ψm,n≤lnPmax,wherePmin=10−8, and it is to obtain a certain lower bound of ψm,n for subsequent processing.Obviously, the SP2.1.1 is convex. However, due to a large number of variables and the high complexity of SP2.1.1, it is difficult to utilize the CVX toolkit for solving the problem. Therefore, we further analyze the problem and propose a search algorithm. Firstly, based on the Lemma1, x⌢m,k,n, y⌢m,k,n, and z⌢m,k,n are negative. In addition, TL1m,n and TL2m,n are positive. Thus, z⌢m,k,n+y⌢m,k,nTL1m,n+x⌢m,k,nTL2m,n<0. Moreover, since x~m,k,n, y~m,k,n, and z~m,k,n are positive, z~m,k,n+y~m,k,neψm,n+x~m,k,ne2ψm,n>0. In summary, constraint (29) can be equivalently expressed as
(35)eφm,k,n≥−z~m,k,n+y~m,k,neψm,n+x~m,k,ne2ψm,nln2Bz⌢m,k,n+y⌢m,k,nTL1m,n+x⌢m,k,nTL2m,n,∀k∈Km.When the objective function of SP2.1.1 is optimal, the equality in the constraint (35) always holds. Thus, the objective function of SP2.1.1 is a function with respect to ψm,n. In other words, a one-dimensional search algorithm is proposed for obtaining the optimal solutions of SP2.1.1. In particular, since the proposed search algorithm is based on the analysis of SP2.1.1, its computational complexity is lower than that of general search algorithms. Finally, we can obtain the stationary point of SP2.1 by iteratively optimizing SP2.1.1. The detailed solution process of obtaining the optimal solution of SP2.1.1 is shown in Algorithm 2. In the algorithm, if there is no UD that satisfy constraint (33) in sector area m, then m∈M1. Otherwise, m∈M2. Moreover, mM2o represents the area number of the o-th element in the set M2, and M2 represents the number of all elements in the set M2. Moreover, the feasible region of ψm,n of each UD k in the sector area mM2o can be obtained based on constraints (31), (33), (34c), and (34d). If the feasible region is not empty, k∈KF. In addition, pmM2o,np∗ is the pmM2o,np,k∗ that minimizes ∑k∈mM2oEmM2o,k,n.


## 3.3. Data Transmit Power Optimization

The data transmit power optimization problem can be formulated with giventn,cn,pm,np,T,ruav, since pm,n has no effect on the energy consumptions of UDs in the sector area m~∈M\m during any status update and has no effect on the energy consumptions of UDs in the sector area m during other status updates. Therefore, the data transmit power optimization problem can be investigated with given status update n and sector area m. Specifically, the simplified optimization problem can be given as follows:
(36a)SP3:minpm,nωE∑m=1M∑k=1Kmτpm,npDm,k/Tc−τ+pm,nDm,kRm,k,n,(36b)s.t.Tntr≤Tnmax,(36c)Tntr≥Tnmin,(36d)0<pm,n≤Pmax, where
(36e)Tnmax=minTF,tn+1−tn,cn−tn,1≤n≤N−1,minTF,cn−tn,n=N,(36f)Tnmin=tn+1−tn−Tncom,∀n∈N\N.Since the objective function of SP3 is nonconvex, we introduce the auxiliary variablesϖm,k,n which satisfy constraints Rm,k,n≥e−ϖm,k,n,∀k∈Km. In addition, we define that eμm,n=pm,n, and the constraints above can be rewritten as follows:
(37a)lneμm,nam,k,n+bm,k,n+cm,k,n≥e−ϖm,k,n1n2B+lneμm,nbm,k,n+cm,k,n,∀k∈Km,where
(37b)am,k,n=2LKm,k,n+2L2Km,k,ngm,k,nηm,k,n+gm,k,nL2Km,k,n2+L+L2gm,k,nηm,k,n2,(37c)bm,k,n=Km,k,n+1∑i=1,i≠kKmgm,i,nΔm,k,i,n+Lgm,k,nKm,k,n+ηm,k,n1+gm,k,npm,np,(37d)cm,k,n=N0BLKm,k,n+1Km,k,n+ηm,k,n.The functionlneμm,nam,k,n+bm,k,n+cm,k,n in constraint (37a) is a convex function with respect to μm,n. Moreover, e−ϖm,k,n1n2/B and lneμm,nbm,k,n+cm,k,n in constraint (37a) are convex functions with respect to ϖm,k,n and μm,n, respectively. In order to transform the nonconvex constraint (37a) into a convex constraint, we obtain the first-order Taylor expansion of the function lneμm,nam,k,n+bm,k,n+cm,k,n at the feasible point μm,nlocal=lnpm,nlocal. Then, constraint (37a) can be written approximately as
(38)lneμm,nlocalam,k,n+bm,k,n+cm,k,n+eμm,nlocalam,k,n+bm,k,nμm,n−μm,nlocalam,k,n+bm,k,neμm,nlocal+cm,k,n≥e−ϖm,k,n1n2B+lneμm,nbm,k,n+cm,k,n,∀k∈Km.Sincelneμm,nbm,k,n+cm,k,n and e−ϖm,k,n are convex functions of μm,n and ϖm,k,n, constraint (38) is convex. It is worth noting that the first-order Taylor expansion in constraint (38) has to be greater than zero. Moreover, constraint (37b) can be rewritten as follows:
(39)pm,n≥maxkcm,k,neTcDm,kln2/BTc−τTnmax−1am,k,n−bm,k,neTcDm,kln2/BTc−τTnmax−1,∀k∈Km.In constraint (36c), if UD k in the sector area m satisfies constraint (36c), the UD k’s data transmit power satisfies the following constraint.
(40)pm,nk≤cm,k,neTcDm,kln2/BTc−τTnmin−1am,k,n−bm,k,neTcDm,kln2/BTc−τTnmin−1.We setpm,n≤maxkcm,k,neTcDm,kln2/BTc−τTnmin−1/am,k,n−bm,k,neTcDm,kln2/BTc−τTnmin−1 based on constraint (35). In summary, we denote that
(41a)pm,nmin=maxmaxkcm,k,neTcDm,kln2/BTc−τTnmax−1am,k,n−bm,k,neTcDm,kln2/BTc−τTnmax−1,Pmin,(41b)pm,nmax=minmaxkcm,k,neTcDm,kln2/BTc−τTnmin−1am,k,n−bm,k,neTcDm,kln2/BTc−τTnmin−1,Pmax,where thePmin is the same as the Pmin in the constraint (34d).If there is no UD that satisfies constraint (36c) in the sector area m, then m∈M3. Otherwise, m∈M4. Then, the following constraints hold based on the eμm,n=pm,n.
(42)lnpm,nmin≤μm,n≤lnPmax,∀m∈M3,lnpm,nmin≤μm,n≤lnpm,nmax,∀m∈M4.In summary, the problem SP3 can be approximately expressed as follows:(43a)SP3.1:minμm,n,ϖm,k,nωE∑k=1KmτDm,k/Tc−τ+eμm,nDm,keϖm,k,n,(43b)s.t.Constraints33,37.Sinceeϖm,k,n and eμm,n+ϖm,k,n are convex functions, the objective function is convex. Therefore, SP3.1 is a convex problem. However, the CVX toolkit is difficult to solve SP3.1 because of the high complexity of the problem. Next, we further analyze the problem and propose a search algorithm to solve it. Firstly, constraint (38) can be rewritten as follows:
(44a)eϖm,k,n≥1n2BYm,k,n+Wm,k,nμm,n−μm,nlocal−lneμm,nbm,k,n+cm,k,n,(44b)Ym,k,n+Wm,k,nμm,n−μm,nlocal−lneμm,nbm,k,n+cm,k,n>0,whereWm,k,n=am,k,n+bm,k,neμm,nlocal/am,k,n+bm,k,neμm,nlocal+cm,k,n and Ym,k,n=lneμm,nlocalam,k,n+bm,k,n+cm,k,n.It can be seen that when the minimal objective function of SP3.1 is obtained, the equation in constraint (44a) holds. Therefore, we only need to perform one-dimensional search within the feasible interval of μm,n to obtain the optimal solution of SP3.1. Specially, we further analyze the problem to reduce the number of searches. Finally, we can adopt SCA to iteratively optimize SP3.1 for obtaining the stationary point of SP3. The detailed process of obtaining the optimal solution of the SP3.1 is shown in Algorithm 3, where mM4o represents the area number of the o-th element in the set M4, and M4 represents the number of all elements in the set M4.Algorithm 3: Obtaining the optimal solutions of SP3.1.
1: ObtainM3 and M4.2: For all sector areas inM3, search μm,n∗ and further obtain pm,n∗.3: Seto=1.4:repeat5: For all areasm∈M4\mM4o, search μm,n∗ within the interval lnpm,nmin,lnPmax and further obtain pm,n∗o.6: SearchμmM4o,n∗ within the interval lnpm,nmin,lnpm,nmax and further obtain pmM4o,n∗.7: CalculateEmM4o=ωE∑m∈M4∑k=1KmEm,k,n based on the power set pm,n∗o,pmM4o,n∗.8:o=o+1.9:untilo>M410: Choose the setpm,n∗o,pmM4o,n∗ with the minimal EmM2o as the optimal data transmit powers of all sector areas in M4.11:Output: pm,n∗.


## 3.4. Service Period Optimization

The service period optimization problem can be formulated as follows:(45a)SP4:minTωA∑m=1M∑k=1KmΔ¯m,k+ωE∑n=1N∑m=1M∑k=1KmEm,k,n+ωU∑m=1MEmfly,(45b)s.t.Constraints9b,9d−9f,9l.Algorithm 4: Joint Scheduling and Power Optimization.
1: InitializeZ0=tn,cn,pm,np,pm,n,T,ruav0, and calculate the weighted sum OBJ0 based on Z0.2: Set the iteration numberl=0, and the tolerance error ε=10−5.3:repeat4:l=l+1.5: Obtaintnl and cnl with given pm,nppm,n,T,ruavl−1 by the Algorithm 1 and SCA.6: Seto=0, pm,np,local=pm,npl−1 and pm,np,∗0=pm,npl−1.7:repeat8:  Seto=o+1.9:  Obtain the stationary points of pilot transmit powerspm,np,∗o based on the Algorithm 2 and feasible point pm,np,local and withgiventnl,cnl,pm,nl−1,Tl−1,ruavl−1.10:  Setpm,np,local=pm,np,∗o.11:until∑n=1N∑m=1Mpm,np,∗o−pm,np,∗o−1≤ε12: Setpm,npl=pm,np,∗o.13: Seto=0, pm,nlocal=pm,nl−1 and pm,n∗0=pm,nl−1.14:repeat15:  Seto=o+1.16:  Obtain the stationary points of data transmit powerspm,n∗o based on Algorithm 3 and feasible point pm,nlocal and with giventnl,cnl,pm,npl,Tl−1,ruavl−1.17:  Setpm,nlocal=pm,n∗o.18:until∑n=1N‍∑m=1M‍pm,n∗o−pm,n∗o−1≤ε19: Setpm,nl=pm,n∗o.20: Utilize one-dimensional search algorithm to obtainTl with given tnl,cnl,pm,npl,pm,nl,ruavl−1.21: Utilize one-dimensional search algorithm to obtainRl with given tnl,cnl,pm,npl,pm,nl,Tl.22: Obtain the weighted sumOBJl based on Zl.23:untilOBJl−1−OBJl≤ε24:Output:Zl.The coordinate of the UAVm at moment t is qm,t=qxm,t,qym,t,HT,∀m∈, where qxm,t=ruavcos2πt/T+ζm and qym,t=ruavsin2πt/T+ζm. Obviously, the UAV’s location is a complex function with respect to the service period. Therefore, the UD’s transmission energy consumption Em,k,n and the maximal transmission delay of the n-th status update Tntr are complex functions with respect to the service period. Function analysis method and SCA method are difficult to be used for the objective function and constraints of SP4. Therefore, we adopt a one-dimensional search algorithm to obtain the near-optimal solution of SP4.


## 3.5. Flight Radius Optimization

The flight radius optimization problem can be formulated as follows:(46a)SP5:minruavωE∑n=1N∑m=1M∑k=1KmEm,k,n+ωU∑m=1MEmfly,(46b)s.t.Constraints9b,9d−9f,9k.Similarly, the UAV’s location is a complex function with respect to the flight radius. Therefore, the UD’s transmission energy consumptionEm,k,n and the maximal transmission delay of the n-th status update Tntr are complex functions with respect to the flight radius. Function analysis method and SCA method are difficult to be used for the objective function and constraints of SP5. Therefore, we adopt a one-dimensional search algorithm to obtain the near-optimal solution of SP5.


## 3.6. The Iterative Algorithm and Analysis

Finally, we propose an iterative algorithm for joint scheduling and power optimization (JSPO). The JSPO is shown in Algorithm4. Next, we analyze the convergence of the JSPO. Although the loop in the JSPO is comprised of five nonconvex subproblems, we utilize greedy, SCA, and one-dimensional search methods to obtain their near-optimal solutions or stationary points, respectively. Define OBJ=ωA∑m=1M∑k=1KmΔ¯m,k+ωE∑n=1N∑m=1M∑k=1KmEm,k,n+ωU∑m=1MEmfly. In each iteration, since the near-optimal solution or stationary point of each subproblem can be obtained with given other variables, the weighted sum OBJ is monotonically nonincreasing. Moreover, the optimal solution of the OP is a lower bound of the solution obtained by the JSPO. In summary, the JSPO can converge.Moreover, the computational complexity of the JSPO depends mainly on the five decomposed subproblems in the loop. First, the computational complexity of solving SP1.1 mainly comes from Algorithm1. In Algorithm 1, we first select N1 sampling points for t1. Then, for each t1, we use the greedy method to select each subsequent transmission start moment under the N2 sampling points. Therefore, the computational complexity of Algorithm 1 is ON1N2N−1. Second, the computational complexity of solving SP2.1.1 mainly comes from the loop in Algorithm 2. In the worst case, Algorithm 2 requires M iterations. In each iteration, a one-dimensional search with N3 sample points is conducted for M−1 sector areas, and kmean one-dimensional searches with N3 sample points are conducted for a sector area, where kmean represents the average number of UDs in a sector area. Therefore, the computational complexity of Algorithm 2 is OMM−1N3+kmeanN3. Third, the computational complexity of solving SP3.1 mainly comes from the loop in Algorithm 3. In the worst case, Algorithm 3 requires M iterations. In each iteration, a one-dimensional search with N4 sample points is conducted for M sector areas. Therefore, the computational complexity of Algorithm 3 is OM2N4. SP4 and SP5 are both solved by the one-dimensional search algorithm, and the number of samples is N5 and N6, respectively. In summary, the computational complexity of the JSPO is OI1N1N2N−1+I2MM−1N3+kmeanN3+I3M2N4+N5+N6, where I1, I2, and I3 are the number of iterations of the JSPO, Algorithm 2, and Algorithm 3, respectively.


## 4. Simulation Results

In this section, simulation results are presented to evaluate the performance of the JSPO. Multiple UDs randomly deploys in a cell with a radius ofrud=50 m. The Rician channel model is considered in the system. Moreover, based on the typical settings in [18, 37], we set other related system parameters as K=30, M=4, L=64, B=20 MHz, H=50 m, C1=0 dB, C2=30 dB, Tc=200, TF=0.2 s, F=3.1 GHz, Pmax=10 dBm, Dm,k=0.1 Mbits, ∀m∈M,k∈K, N1=N2=N3=N4=103, N5=N6=105, and N0=−174 dBm/Hz. In order to narrow the numerical gap between the average AoI and the energy consumptions of UDs and UAVs, we design weighted factors ωA, ωE, and ωU based on the initial values of the average AoI and the energy consumptions of UDs and UAVs. Specifically, ωA=0.1, ωE=103, and ωU=10−6.To evaluate the performance of the JSPO, we compare it with other algorithms. Specifically, the comparison algorithms are shown as follows.(i)
“OnlyT”. In this algorithm, only the transmission and computing start moments are optimized(ii)
“OnlyPP”. In this algorithm, only the pilot transmit power is optimized(iii)
“OnlyDP”. In this algorithm, only the data transmit power is optimized(iv)
“OnlySP”. In this algorithm, only the service period is optimized(v)
“OnlyR”. In this algorithm, only the flight radius is optimized(vi)
“RLB”. In this algorithm, we modify the objective function of the original problem, thus transforming it into a relaxed lower bound (RLB) problem, and then obtain the optimal solution of the RLB problem. Specifically, we first set each variable in formula (3c) to its maximal or minimal value to obtain the lower bound of UDs’ energy consumptions. Subsequently, we obtain the minimal average AoI of each UD based on the method of work [38] without considering constraints. Moreover, we utilize the function analysis method to obtain the minimal energy consumptions of UAVs without considering constraints. Finally, the RLB of the original problem is obtained by adding the minimal average AoIs and minimal energy consumptions of the UDs and UAVs. It is worth noting that the solution of the RLB is the relaxed lower bound of the optimal solution of the original problem, and it can be compared with the solution of the proposed algorithmIn Figure3, we plot the convergence performance of the JSPO under different initial service periods and flight radiuses. The JSPO can converge within a finite number of iterations, thus showing convergence performances. Moreover, the convergence value of the weighted sum shows an obvious change with the change of the initial service period and flight radius. This shows that the convergence value of the weighted sum is related to the initial service period and flight radius. In addition, the weighted sum first decreases and then increases with the increase of the initial service period. This is because average AoI is a monotonically increasing function with respect to the service period, and the energy consumptions of UAVs are a convex function with respect to the service period.Figure 3
Convergence performance of the JSPO under different initial service periods and flight radiuses.The weighted sum versus the number of antennas under different algorithms is presented in Figure4. It can be seen from Figure 4(a) that the weighted sum obtained by the JSPO is significantly lower than that obtained by the OnlyPP, OnlySP, and OnlyR, thus indicating the superiority of the JSPO. Moreover, the gap between the weighted sum obtained by the JSPO and that obtained by the RLB is not large, which further proves the superiority of the JSPO. In Figure 4(a), the curve of the weighted sum obtained by the JSPO has two inflection points, which shows that the number of antennas should be appropriate. In order to analyze this phenomenon, we observe the relationship between average AoI/UDs’ energy consumptions/UAVs’ energy consumptions and the number of antennas by adjusting the weighted factors.Figure 4
(a) The weighted sum versus the number of antennas under different algorithms, withωA=0.1, ωE=103, and ωU=10−6. (b) The weighted sum versus the number of antennas under different algorithms, with ωA=0.1, ωE=1, and ωU=10−9. (c) The weighted sum versus the number of antennas under different algorithms, with ωA=10−7, ωE=103, and ωU=10−9. (d) The weighted sum versus the number of antennas under different algorithms, with ωA=10−4, ωE=1, and ωU=10−6.
(a)(b)(c)(d)It can be seen from Figure4(b) that when average AoI has a larger weight than the energy consumptions of UDs and UAVs, the weighted sum obtained by the JSPO first decreases and then increases as the number of antennas increases, which shows that the increase of the number of antennas has both advantages and disadvantages for average AoI. This is because the number of antennas has a complex impact on the maximal transmission delay, and average AoI is a complex function with respect to the maximal transmission delay. Moreover, the optimization effect of the OnlyT is better than that of the JSPO. This is because the OnlyT only optimizes the variables that affect average AoI, while the JSPO takes into account the variables that affect the entire objective function. Therefore, when focusing on optimizing average AoI, the OnlyT can be adopted. However, the performance of the OnlyT is quite different from that of the RLB. There are two main reasons. First, since the solution obtained by the RLB is the relaxed lower bound of the original problem, its performance is better than the optimal solution of the original problem. Second, average AoI is also related to the service period; however, the OnlyT does not optimize the service period.It can be seen from Figure4(c) that when the energy consumptions of UDs have a larger weight, the weighted sum obtained by the JSPO decreases as the number of antennas increases. This is because that the increase of the number of antennas can reduce the transmission delay of most UDs, thereby reducing the sum of UDs’ energy consumptions. In addition, the performance of the JSPO is not much different from that of the RLB, thereby indicating that the JSPO can obtain near-optimal performance when focusing on optimizing the energy consumptions of UDs. It can be seen from Figure 4(d) that when the energy consumptions of UAVs have a larger weight, the weighted sum obtained by the JSPO hardly changes with the increase of the number of antennas. The reason is that the number of antennas does not change the service period and flight radius, thereby having little impact on the energy consumptions of UAVs.Figure5 shows that the weighted sum versus the number of UAVs under different algorithms. It can be seen from Figure 5(a) that the weighted sum obtained by the JSPO is significantly lower than that obtained by the OnlyPP, OnlySP, and OnlyR, thereby indicating the superiority of the JSPO. Moreover, the gap between the weighted sum obtained by the JSPO and that obtained by the RLB is not large, which further proves the superiority of the JSPO. Moreover, when the communication bandwidth of the system is determined, the increase of the number of UAVs mainly brings the following three effects. The first is that the amount of bandwidth divided into each sector area is reduced, thereby increasing the transmission delay and energy consumptions of UDs. The second is that the average number of UDs in each sector area is reduced, which reduces the interference among UDs in same sector area, thereby reducing the transmission delay and energy consumptions of UDs. Thus, the increase of the number of UAVs brings both benefits and disadvantages for the transmission delay and energy consumptions of UDs. Moreover, the transmission delays of UDs are related to the maximal transmission delay Tntr, thereby affects average AoI. Therefore, when we focus on optimizing average AoI or energy consumptions of UDs, there may be some inflection points. The third is that the increase of the number of UAVs increases the total energy consumptions of UAVs.Figure 5
(a) The weighted sum versus the number of UAVs under different algorithms, withωA=0.1, ωE=103, and ωU=10−6. (b) The weighted sum versus the number of UAVs under different algorithms, with ωA=0.1, ωE=1, and ωU=10−9. (c) The weighted sum versus the number of UAVs under different algorithms, with ωA=10−7, ωE=103, and ωU=10−9. (d) The weighted sum versus the number of UAVs under different algorithms, with ωA=10−4, ωE=1, and ωU=10−6.
(a)(b)(c)(d)It can be seen from Figures5(b) and 5(c) that when focusing on optimizing the average AoI and the energy consumptions of UDs, the performance curve of the JSPO shows one or more performance inflection points as the number of UAVs increases, thus verifying the correctness of the conclusion above. In Figure 5(b), since the performance of the OnlyT outperforms that of the JSPO, the OnlyT can be adopted when focusing on optimizing average AoI. In Figure 5(d), the weighted sum obtained by the JSPO increases with the increase of the number of UAVs, which verifies the conclusion mentioned above. Moreover, combined with all subfigures of Figure 5, since the system can obtain favorable performance with a low economic cost, a small number of UAVs is more worthy of being selected. However, due to the delay limitation in constraint (9b), the number of UAVs cannot be reduced indefinitely. Therefore, we should choose the minimal number of UAVs that meets constraint (9b).Figure6 shows that the weighted sum versus the number of status updates under different algorithms. It can be seen from Figure 6(a) that the weighted sum obtained by the JSPO is significantly lower than that obtained by the OnlyPP, OnlySP, and OnlyR under different numbers of status updates, indicating the superiority of the JSPO. It can be seen from Figure 6(b) that when average AoI is mainly optimized, the weighted sum decreases as the number of status updates increases. This shows that increasing the number of status updates can effectively reduce average AoI. This is because under the condition of a fixed service period, increasing the number of status updates can effectively reduce the area enclosed by the curve of the AoI and the time axis, thereby reducing average AoI. In Figure 6(c), the weighted sum increases as the number of status updates increases when the energy consumptions of UDs are mainly optimized. The reason is that increasing the number of status updates increases the number of transmissions, thereby increasing the energy consumptions of UDs. In Figure 6(d), the energy consumptions of UAVs do not change with the number of status updates, which reflects that the number of status updates have no affect on the energy consumptions of UAVs. Moreover, we can observe that the weighted sum obtained by the JSPO gradually decreases as the number of state updates increases in Figure 6(a). However, this does not mean that more status updates can be better. When the number of status updates is large, the total delay may exceed the service period and the energy consumptions of UDs increase.Figure 6
(a) The weighted sum versus the number of status updates under different algorithms, withωA=0.1, ωE=103, and ωU=10−6. (b) The weighted sum versus the number of status updates under different algorithms, with ωA=0.1, ωE=1, and ωU=10−9. (c) The weighted sum versus the number of status updates under different algorithms, with ωA=10−7, ωE=103, and ωU=10−9. (d) The weighted sum versus the number of status updates under different algorithms, with ωA=10−4, ωE=1, and ωU=10−6.
(a)(b)(c)(d)It can be seen from Figure4–6 that the optimization effect of the service period and flight radius related to the energy consumptions of UAVs is not obvious. The reason for this result is given as follows. By analyzing the constraints in the original optimization problem, since the service period and flight radius are strongly constrained and their feasible regions are small, it is difficult to find the service period and flight radius that have better performance and satisfy the constraints. However, Figure 3 shows that the weighted sum is related to the initial service period and flight radius. Moreover, when the average AoI and the energy consumptions of UDs and UAVs are both optimized, the performance of the OnlyDP is close to that of the JSPO. Therefore, we propose the JSPO-R to improve the performance of the JSPO. The flow of the JSPO-R is given as follows. The OnlyDP is performed under different initial service periods and flight radiuses, which aims to obtain the service period and flight radius with better performance. Then, the service period and flight radius obtained by the operation above are regarded as the initial solution of the JSPO. It can be seen from Figure 7 that the performance of the JSPO-R is better than that of the JSPO under different number of the antennas, UAVs, and status updates. Moreover, compared to the JSPO, the gap between the JSPO-R and the RLB is further narrowed. In summary, when the system has high requirements for the performance, the JSPO-R, which is more complex but has better performance, can be adopted.Figure 7
(a) The weighted sum versus the number of antennas under different algorithms, withωA=0.1, ωE=103, and ωU=10−6. (b) The weighted sum versus the number of UAVs under different algorithms, with ωA=0.1, ωE=103, and ωU=10−6. (c) The weighted sum versus the number of status updates under different algorithms, with ωA=0.1, ωE=103, and ωU=10−6.
(a)(b)(c)


## 5. Conclusions

In the multiantenna UAV-assisted MEC system, we have aimed to reduce the average AoI and the energy consumptions of UDs and UAVs in a balanced manner. Therefore, the weighted sum of the three performance metrics was aimed to be minimized by the joint optimization of the scheduling and power allocation strategies. The original NP-hard problem was divided into five sub-problems which were solved one by one. First, a low-complexity search algorithm has been proposed to obtain the near-optimal solution of the transmission and computing start moments. Then, we have obtained stationary points of the pilot and data transmit powers by the SCA. Next, we have adopted a one-dimensional search method to solve the service period and flight radius subproblems. Finally, an iterative algorithm has been proposed to obtain the suboptimal solution of the original problem. Simulation results show that the proposed algorithm can effectively reduce the weighted sum of the average AoI and the energy consumptions of UDs and UAVs. Moreover, the simulation results also demonstrate that we should adjust the number of antennas, the number of UAVs, and the number of status updates according to actual needs and conditions to obtain better performance.



---

*Source: 8117391-2022-02-02.xml*