Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Multi-Drone 3D Trajectory Planning and Scheduling in Drone Assisted Radio Access Networks

Multi-Drone 3D Trajectory Planning and Scheduling in Drone Assisted Radio Access Networks Multi-Drone 3D Trajectory Planning and Scheduling in Drone Assisted Radio Access Networks Weisen Shi, Junling Li, Nan Cheng, Feng Lyu, Shan Zhang, Haibo Zhou, and Xuemin (Sherman) Shen, Fellow, IEEE Abstract—Drone base station (DBS) is a promising technique is to deploy massive small cells, which, however, is inefficient to extend wireless connections for uncovered users of terrestrial and costly for RAN operators [4]. To overcome the coverage radio access networks (RAN). To improve user fairness and and flexibility challenges faced by current RAN, the emerging network performance, in this paper, we design 3D trajectories of drone, a.k.a. unmanned aerial vehicle (UAV), communication multiple DBSs in the drone assisted radio access networks (DA- technology is proposed as a promising solution. RAN) where DBSs fly over associated areas of interests (AoIs) and relay communications between the base station (BS) and users Equipped with specific wireless transceivers, drones can in AoIs. We formulate the multi-DBS 3D trajectory planning communicate with both terrestrial users and cellular base and scheduling as a mixed integer non-linear programming stations (BSs) using WiFi [5] or LTE [6] technologies. By (MINLP) problem with the objective of minimizing the average integrating drone communication with terrestrial RAN, the DBS-to-user (D2U) pathloss. The 3D trajectory variations in drone assisted radio access networks (DA-RAN), in which both horizontal and vertical directions, as well as the state- of-the-art DBS-related channel models are considered in the drones perform as drone base stations (DBSs) to relay data formulation. To address the non-convexity and NP-hardness of between users in areas of interests (AoIs) and the associated the MINLP problem, we first decouple it into multiple integer terrestrial BS , has been proposed and verified by field exper- linear programming (ILP) and quasi-convex sub-problems in iments [7]. In DA-RAN, AoI includes both the CHs and the which AoI association, D2U communication scheduling, hori- traffic dense spots (TDBs) where the allocated RAN spectrum zontal trajectories and flying heights of DBSs are respectively optimized. Then, we design a multi-DBS 3D trajectory planning resources are temporarily inadequate, e.g. congested road, and scheduling algorithm to solve the sub-problems iteratively concerts and sports events, etc. Compared with the terrestrial based on the block coordinate descent (BCD) method. A k-means- RAN, DA-RAN advances in following four aspects: 1) The based initial trajectory generation and a search-based start slot line-of-sight (LoS) probability for the DBS-to-ground (D2G) scheduling are considered in the proposed algorithm to improve wireless link is higher than the terrestrial BS-to-user wireless trajectory design performance and ensure inter-DBS distance constraint, respectively. Extensive simulations are conducted to link [4]. Experiments indicate that LoS links probability is investigate the impacts of DBS quantity, horizontal speed and the dominating factor to increase network performance [8]; 2) initial trajectory on the trajectory planning results. Compared DBSs can be dynamically deployed and dispatched to different with the static DBS deployment, the proposed trajectory planning controllers/users with respect to the spatial and temporal traffic can achieve 10-15 dB reduction on average D2U pathloss, and variations [9]; 3) unlike connected vehicles whose mobility is reduce the D2U pathloss standard deviation by 68%, which indicate the improvements of network performance and user controlled by drivers or autonomous driving controller, the tra- fairness. jectories of DBSs can be fully controlled by system providers, which empowers DBSs with the dynamic deployment feature Index Terms—Drone Communication, Drone Base Station, Trajectory Planning, DA-RAN, Space-Air-Ground Integration. [10] [11]; 4) DBS are capable of executing computing tasks by equipping with CPU or caching modules [12] [13]. However, it is challenging to fully utilize the potential of DBSs due to I. I NTRODUCTION the following two reasons. First, the 3D mobility of DBS poses The future radio access networks (RAN) is expected to great complexity on the DBS spatial placement, especially in provide ubiquitous connectivity for any users or devices at multi-DBS scenarios [14]. Second, specific channel models any time with diversified service requirements [1]. However, are required to highlight the unique features of DBS-to-user coverage holes (CH) of terrestrial RAN prevail in both urban (D2U) and DBS-to-BS (D2B) channels[15]. and rural scenarios due to the lack of infrastructures or deeply Several studies optimizing the multi-DBS spatial placements blocking by obstacles [2]. Specifically, as the terrestrial RAN to support terrestrial users emerges in recent year, which can are statically fixed in certain geographical locations, it is be divided into two categories, i.e., static DBS deployment normally hard to ensure the quality of service (QoS) of users and DBS trajectory planning. The static DBS deployment that are uneven and dynamically distributed in both spatial research focus on optimizing the hovering positions of DBSs and temporal domain [3]. One solution to address those CHs to maximize terrestrial users QoS. However, the static de- ployment fails to guarantee the fairness for users, in which W. Shi, J. Li, N. Cheng (corresponding author), F. Lyu, and X. Shen are the users located at the edge of the DBS’s radio coverage with the Department of Electrical and Computer Engineering, University of suffer relatively higher pathloss compared with the users Waterloo, 200 University Avenue West, Waterloo, Ontario, Canada, N2L 3G1, (email: fw46shi, j742li, n5cheng, f2lyu, ssheng@uwaterloo.ca). located at the center of the DBS’s coverage. In addition, most S. Zhang is with the School of Computer Science and Engineering, Beihang University, Beijing, China, 100191, (email: zhangshan2007@gmail.com). H. Zhou is with the School of Electronic Science and Engineering, Nanjing In this paper, the abbreviation BS means the terrestrial base station and University, Nanjing, China, 210023, (email: haibozhou@nju.edu.cn). DBS is referred to as drone base station. arXiv:1906.00777v2 [cs.NI] 22 Oct 2019 2 existing DBS deployment works focus on optimizing the D2U mize AoI association, D2U communication scheduling, communication, while ignore or idealize the D2B link quality horizontal trajectories and flying heights of DBSs in constraints. different sub-problems, respectively. Besides, a k-means- To promote the fairness for all users and maintain low based scheme is devised to generate the DBS initial deployment cost, some researchers further propose the DBS trajectories for further improvements on performance. trajectory planning approach that allows DBSs fly over and We conduct extensive simulations and results demonstrate serve AoIs periodically according to designed trajectories. that the proposed 3D trajectory planning and scheduling The purpose of DBS trajectory planning is optimizing AoIs algorithm can reduce the average D2U pathloss by 15 association and trajectory for each DBS to maximize user 20 dB, and lower the D2U pathloss standard deviation QoS [16] [17]. However, three issues remain unsolved in by 68%, in comparison with the static DBS deployment current works. First, to reduce the complexity of optimization algorithm based on particle swarm optimization (PSO). problems, most existing works assume that all DBSs fly at a The remainder of this paper is organized as follows. The pre-defined constant height, which shrinks the 3D trajectory literature review is conducted in Section II. In Section III the planning into a 2D horizontal trajectory planning, and fails system model for DBS trajectory planning and scheduling in to realize the performance improvements by adjusting DBS DA-RAN is introduced. Then the multi-DBS 3D trajectory flying heights. Second, the commonly used assumption of Friis planning and scheduling problem is formulated in Section IV. free space propagation model cannot reflect the unique D2G In Section V the MINLP problem in Section IV is decoupled channel features. Third, the D2B link quality constraint is also into sub-problems and the BCD based algorithm is proposed omitted by most DBS trajectory planning works. to solve it. Simulation and numerical results are carried out in To address those issues, in this paper, we investigate the 3D Section VI, and the conclusion is given in Section VII. trajectory planning and scheduling for multiple DBSs in the II. RELATED WORKS DA-RAN. Considering the state-of-the-art D2U [18] and D2B [6] channel models, and constraints of D2B link qualities, the Promoted by the advancements in the flying control and multi-DBS 3D trajectory planning problem is formulated as communication technologies, both industry and academia are a mixed integer non-linear programming (MINLP) problem devoting many efforts to exploit the full potential of DA- which aims at minimizing the average D2U pathloss for RAN [4]. As the foundation for drone communication and all users within one trajectory period. By decoupling the DA-RAN research, Al-Hourani et al. built the D2U pathloss MINLP problem into multiple quasi-convex or integer linear model for DBS according to abundant field test data in various programming (ILP) sub-problems, we can separately optimize scenarios [18]. A close-form expression of D2U pathloss the AoI association, D2U communication scheduling, DBS model suiting different scenarios is proposed in which the horizontal trajectories and flying heights in each sub-problem, probabilities of both LoS and NLoS D2U links are considered. respectively. In essence, we adopt the block coordinate descent As the extension work, they further formulated the pathloss (BCD) mechanism to devise a multi-DBS 3D trajectory plan- model for D2B communication in suburban scenario [6] where ning and scheduling algorithm, in which the sub-problems are the D2B links are dominated by LoS links. Leveraging the iteratively optimized and converge to the optima. The main pathloss model in [18] and [6], various studies have emerged contributions of this work are listed as follows: in both static DBS deployment and DBS trajectory planning. We investigate the 3D trajectory planning of multiple A. Static DBS Deployment DBSs in which both the flying heights and horizontal trajectories of DBS are optimized together instead of In most static DBS deployment works, the terrestrial user optimizing horizontal trajectories on a 2D plane. As far QoS or network performance is improved through optimizing as we know, this is the first work considering the real 3D the hovering position of single or multiple DBSs. For instance, trajectory in which the flying height of any DBS can be through a clustering based approach, Mozaffari et al. designed adjusted at different slots on its trajectory. the optimal locations of DBSs that maximize the information To make the system model more practical, we employ the collection gain from terrestrial IoT devices [19]. In [20], Zhang state-of-the-art D2U and D2B pathloss models rather than et al. optimized the DBS density in DBS network to maximize the traditional pathloss models (e.g., Friis equation) in the the network throughput while satisfying the efficiency require- system model. We formulate the multi-DBS trajectory ments of the cellular network. Zhou et al. studied the downlink planning problem, which turn to be an MINLP, and coverage features of DBS using Nakagami-m fading models, decouple it into multiple sub-problems to resolve the and calculated the optimal height and density of multiple non-convexity. A protect distance constraint between any DBSs to achieve maximal coverage probability [21]. Although two DBSs at every time slots is considered in the prob- various works have investigated the static DBS deployments lem formulation to suppress the physical collision and in different scenarios with different methods, the D2B link mutual interference of DBSs. Instead of modifying the quality constraint is simplified or ignored by most works. 3D trajectories, we ensure the protect distance constraint In the works considering the D2B links, the D2B channel by scheduling the start slot of each trajectory to avoid models are either as same as the D2U pathloss model [22] introducing non-convex constraints in trajectory-related or traditional terrestrial channel models [23]. In this paper, we sub-problems. further implement the specific D2B channel model derived in A BCD based algorithm is proposed to separately opti- [6] to highlight the D2B channel features. v v v DBS D2B Link D2U Link Base Station Users Trajectory DBS D2B Link D2U Link Horizontal Distance Base Station Users Communication Resource 50% 20% 25% Computation Resource 30% 80% D2B Link 30% 20% D2U Link Base Station Users Drone-cell B. DBS Trajectory Planning D2B Link In [24], Li et al. proposed an cooperative relaying scheme Horizontal in which multiple DBSs relay data from terrestrial sensors Trajectory Distance U2D Link to the BS using time division multiple access (TDMA). As User a pioneer work, the trajectories of all DBSs are assumed (IoT device) Base Station to be pre-optimized for simplicity. Mozaffari et al studied (a) DBS photograph [29] both the static and mobile DBS-enabled wireless networks Base Station D2B Link underlaid with a device-to-device communication network DBS DBS θ [25]. Though the trajectory optimization is considered in this D2B Link work, the D2U communications are only permitted at pre- D2U Link defined stop points, which fails to exploit the impact of DBS mobility feature on the network performance. Motivated by Base Station [25], Zeng et al. proposed a general framework for joint AoI Trajectory trajectory and communication optimization in D2U point-to- point communication scenario [26]. For DBS-enabled multi- AoI Horizontal Distance user networks, Lyu et al. proposed a cyclical multiple access (b) System model scheme in [27], where the DBS forms a cyclical trajectory and periodically serves each terrestrial users using TDMA. Fig. 1: Multi-DBS 3D trajectory planning and scheduling. Wu et al. formulated the DBS trajectory planning as a mixed integer non-convex optimization problem in which the user jSj is a circle with radius r , and is divided into a mesh BS bs association, DBSs trajectories planning and DBS transmitting consisting of multiple grids on X-Y plane. The side-length power control schemes are jointly optimized [16]. Considering of each grid is denoted as L . Without loss of generality, aoi the delay constraints, Wu et al. further studied a DBS-enabled the average D2U pathloss for any users in one grid can be OFDMA network where a single DBS is dispatched to serve treated as equal since L is far smaller than r . Assuming aoi BS a group of delay-sensitive users on the ground [17]. The that users are uniformly distributed over jSj , and each grid bs DBS trajectory planning and OFDMA resource allocation are can be chosen as AoI with same probability. Therefore, the jointly optimized through an iterative parameter-assisted BCD user association is equal to AoI association in this work. Both method. As the pioneer works of trajectory planning, [16] users in AoIs and DBSs are considered as identical devices [17] set the foundation models for DBS trajectory planning. with identical transmit power and uplink/downlink bandwidth. To dynamically deploy multiple DBSs while maintaining the Considering the fact that AoIs change their distribution in connectivity among them, Zhao et al. proposed both the a relatively low frequency, the dynamic distribution of AoIs centralized and distributed DBS motion control algorithms for can be treated as a quasi-static scenario between successive scenarios with or without global information of users [28]. trajectory planning. Based on the current snapshot of AoIs However, in those works the flying height of all DBS are distribution, the BS running trajectory planning and scheduling treated as a pre-defined constant, and most of them idealize the algorithm to calculate optimal trajectories for all DBSs, and D2B link quality constraints. In this paper, not only the D2B update them to the DBSs via D2B links. When the BS senses link quality constraint is introduced in problem formulation significant changes of AoIs distribution, re-planning process and optimization, but also the flying heights of each DBS at is triggered to design new trajectories for DBSs, otherwise, every slots are jointly optimized with the horizontal trajectory. the trajectory planning result keeps constant. The set of AoIs to be served and the set of DBSs to be deployed are denoted as U and D, respectively. Their cardinalities, jUj and jDj, III. SYSTEM MODEL represent the number of AoIs and DBSs, respectively. In this section, we introduce the DA-RAN scenario, D2U and D2B channel models, as well as the DBS trajectory model used for further analyses and problem formulation. B. D2U and D2B Channel Models A. Drone Assisted Radio Access Networks Based on the state-of-the-art Drone-to-Ground (D2G) chan- nel research [18] [6], both the D2U and D2B links are modeled Fig. 1 shows the system model and the DBS photograph for in our work, respectively. For D2U links, the LoS probability the multi-DBS 3D trajectory planning and scheduling. The is calculated as [18] DBS is supported by the quad-copter or multi-rotor drones, which is regarded as low altitude platform (LAP) with the low flying height (below 300m) [14], limited communication P ¹r ; hº = (1) LoS DU 1 + a exp¹b¹arctan¹ º aºº coverage (less than 3km) [14] and static hovering capability. DU Based on the DA-RAN architecture, we investigate the sce- nario in which multiple DBSs are controlled by a single BS where r is the horizontal distance between DBS and the DU to support users in AoI through the state-of-the-art wireless AoI, h represents the flying heights of the DBS. a and b are relay techniques [30] [31]. The radio coverage area of the BS environment-based constant values. The average D2U pathloss 4 can be derived based on (1) [18]: simultaneously, they share the same trajectory period length T to simplify the trajectory planning and scheduling. 4 f h + r Several trajectory constraints are considered in our work: DU PL¹r ; hº = 20 log¹ º DU (2) 1) Each DBS needs to return to its initial location by the end of each period T , which implies that the trajectory of each + P ¹r ; hº +¹1 P ¹r ; hºº LoS DU LoS LoS DU NLoS DBS is a closed curve in 3D space. 2) Within any slot n, the where f (Hz) and c (m/s) are carrier frequency and speed of horizontal and vertical shifts of any DBS cannot exceed the light, respectively.  and  are additional losses for LoS N LoS maximal horizontal distance V  , and the maximal height max t LoS and NLoS links obtained through field test data, which difference H  , respectively. V and H are maximum max t max max involves the impacts of shadowing components. a, b,  and LoS allowed horizontal and vertical speeds. 3) For any slot n, the are all environment-based parameters. N LoS 3D distance between any two DBSs cannot be smaller than a D2B links are designed to provide high-reliability data pre-defined protect distance Z , which prevents the physical min transmission between DBSs and their corresponding BS. The collision, disturbance and mutual interference among DBSs. average D2B pathloss is calculated as follow by implementing Since calculating interference from non-associated DBSs to the D2B channel model in [6]: any AoI based on D2U pathloss model is highly complex 0 and makes the trajectory planning problem unsolvable, in this ¹ º B (3) PL¹r ; º = 10 log¹r º + A¹  ºe + DB DB 0 0 work, we assume that the mutual interference (to AoIs) among where r and  denote the horizontal distance and the vertical DBSs can be effectively avoided by ensuring the protect DB angle between the DBS and the BS antenna, respectively. , distance constraint. A,  , B, and  are the terrestrial pathloss exponent, excess 0 0 pathloss scalar, angle offset, angle scalar, and excess pathloss D. AoI Association and D2U Communication Scheduling offset, respectively. All of them are environment-based param- In this work, the DBS-AoI association is denoted by the eters and involving impacts of shadowing components. Except binary variable a . a = 1 when AoI u 2 U is associated to d;u d;u r and , all other parameters in (3) are environment-based DB DBS d 2 D, and otherwise a = 0. The U2D communication d;u constants. Since the D2B channel model in [6] use 850 MHz scheduling is denoted by the binary variable k »n¼ for d;u LTE bands, (3) contains no parameter representing carrier 8d 2 D; u 2 U; n 2 N . If AoI u is severed by DBS d in frequency. slot n, k »n¼ is set as 1; otherwise, k »n¼ = 0. For each d;u d;u Both the D2U [18] and D2B [6] pathloss models are large- DBS with pre-defined trajectory planning and AoI association scale pathloss models. For the small scale fading and multipath results, a D2U communication scheduling scheme is designed effects, currently there is no specific model for the drone-to- to allocate each slot to the corresponding AoI, and guarantee ground communication links. Moreover, since the objective of the fairness among all associated AoIs. Several constraints are our multi-DBS trajectory planning is to minimize the mean considered in the AoI association and scheduling model: 1) D2U pathloss of the system, the small-scale pathloss can be One DBS can serve maximal jA j number of AoIs. 2) In max average out at zero or a constant offset during the analysis. any slot n, one DBS d can serve at most one AoI u 2 A ; in all Therefore, based on the assumptions in D2U and D2B channel slots, one AoI u can only be associated to one DBS. 3) For any models, in this work we do not focus on the small scale fading given T and A , the total N slots are uniformly scheduled to and multipath effects in D2U and D2B links. each u 2 A to ensure fairness. 4) The slot amount scheduled to every AoIs cannot be smaller than a pre-defined threshold C. DBS Trajectory Model S , which indicates the minimal user service time constraint. min 5) To prevent the overloads and delay caused by frequent For an arbitrary DBS d 2 D, we design its trajectory switching between associated AoIs, all slots scheduled to one such that the DBS serves the associated AoI set A  U u within T have to be consecutive. periodically. Within one period T , d flies over all its associated AoI and serves them sequentially according to the scheduling IV. PROBLEM FORMULATION result. Since the continuous time can introduce infinite number of position variables to describe the DBS trajectory, we In this section we formulate the multi-DBS 3D trajectory discrete the period T into N equal-time slots to simplify the planning problem based on the aforementioned system model. formulation. The length of each slot  = can be set as small According to (4), the the 3D distance from the DBS d to as possible to approximate the continuous optimal trajectory. AoI u in time slot n can be expressed as Based on this model, the trajectory of DBS d within each T m »n¼ = h »n¼ + kl »n¼ l k can be modeled as a N -length sequence composed by three- d;u d d u q (5) dimensional vectors: 2 2 = h »n¼ + r »n¼ d d;u W »n¼ = »x »n¼; y »n¼; h »n¼¼; n = 1; :::; N (4) d d d d where l = »x ; y ¼ is the 3D coordinate of AoI u. l »n¼ is u u u d where x »n¼, y »n¼ and h »n¼ denote the 3D coordinates d’s 2D projection on X-Y plane l »n¼ = »x »n¼; y »n¼¼. r »n¼ d d d d d d d;u of DBS d at slot n. DBS d is considered to follow the denotes the horizontal distance between DBS d and AoI u. same trajectory W »n¼ over consecutive periods until the re- Without loss of generality, we set the BS at the original point planning process is triggered. For multiple DBSs working of coordinate system. By substituting m »n¼ for the D2U d;u 5 and D2B distances in (2) and (3), we can calculate the D2U Due to the quadratic and exponential terms in (8) and con- pathloss between DBS d and AoI u in slot n straints, as well as the binary variable a , k »n¼, problem d;u d;u (8) is a MINLP problem [32]. Besides, the optimization ob- 4 f m »n¼ c d;u P »n¼ = 20 log¹ º jective (8) and constraints are non-convex for DBS trajectory d;u W, which is difficult to solve directly. (6) + P ¹r »n¼; h »n¼º LoS d;u d LoS +¹1 P ¹r »n¼; h »n¼ºº LoS d;u d NLoS V. M ULTI-DBS 3D TRAJECTORY PLANNING AND as well as the D2B pathloss between the BS and DBS d in SCHEDULING ALGORITHM slot n Although the objective and constraints in problem (8) are P »n¼ = 10 log¹kl »n¼kº d;B d (7) non-convex or non-linear for the decision variables, the prob- »n¼ 0 d;B ¹ º + A¹ »n¼  ºe + d;B 0 0 lem can still be transformed into solvable forms (e.g. quasi- convex or ILP) by setting parts of the decision variables as where  »n¼ = arctan¹h »n¼kl »n¼kº in degree. d;B d d constants. Then, the MINLP problem can be decoupled into Since all users and DBSs are identical devices with fixed multiple sub-problems which are solvable for parts of the transmission power and transmission bandwidth in each pe- decision variables. Specifically, for the multi-DBS 3D trajec- riod, the achievable D2U data rate between DBS d and AoI tory planning and scheduling problem, we divide the decision u is negative correlated with the D2U pathloss. Therefore, the variable set into four blocks (i.e. A, K, L = fl »n¼; 8d; ng aim of the multi-DBS 3D trajectory planning and scheduling and H = fh »n¼; 8d; ng), and propose multiple sub-problems problem is minimizing the average D2U pathloss of the in which all blocks or their sub-blocks are optimized, respec- network over one period T . tively. However, the problem (8) remains non-convex to DBS Define A = fa ; 8d; ug, K = fk »n¼; 8d; u; ng and d;u d;u trajectory variable W even with given A and K. Therefore, W = fW »n¼; 8d; ng, the trajectory planning and scheduling we further divide W into two independent blocks, i.e. the problem can be formulated as horizontal DBS trajectory L and the DBS flying height H. jUj jDj N ÕÕ Õ min a ¹ k »n¼P »n¼º (8) d;u d;u d;u A;K;W NjUj u=1 d=1 n=1 A. AoI Association Optimization jUj s:t: a  jA j ; 8d; (8a) d;u d max Given the constant K, L and H, which indicate the pre- u=1 jDj defined trajectories of multiple DBSs, the AoI association sub- a = 1; 8u; (8b) d;u d=1 problem can be written as an ILP problem: jUj k »n¼ = 1; 8d; n; (8c) d;u jUj jDj u=1 N ÕÕ Õ jDj min a ¹ k »n¼P »n¼º d;u d;u d;u k »n¼ = 1; 8u; n; (8d) d;u A NjUj (9) d=1 u=1 d=1 n=1 N N s:t: ¹8aº;¹8bº; a 2 f0; 1g 8d; u: k »n¼ = ; 8d; u; (8e) d;u d;u n=1 jA j Since exact K can only be determined with given A , an k »n¼  S ; 8d; u; (8f) d;u min n=1 initial D2U communication scheduling K , in which k »n¼ = 0 d;u Õ N jA j d 1; 8d; u; n, is defined for the first AoI association optimization. k »¹n + oº mod N¼  ; 8d; u; n; (8g) d;u jA j d The branch and bound method supported by various solvers a ; k »n¼ 2 f0; 1g; 8d; u; n; (8h) (e.g. Gurobi [33]) can be used to solve problem (9) efficiently. d;u d;u W »1¼ = W »N + 1¼; 8d; (8i) d d kl »n + 1¼ l »n¼k  V  ; 8d; n; (8j) d d max t B. D2U Communication Scheduling Optimization jh »n + 1¼ h »n¼j  H  ; 8d; n; (8k) d d max t Based on the optimized A, as well as the constant L and kW »n¼ W »n¼k  Z ; 8n; i; j , i; (8l) i j min H, the D2U communication scheduling sub-problem is an ILP P »n¼  P ; 8d; u; n: (8m) d;B DB problem too: jUj jUj jDj In (8), jA j = N a is the number of AoIs associated N d d;u ÕÕ Õ u=1 to DBS d. kW »n¼ W »n¼k represents the 3D distance min a ¹ k »n¼P »n¼º i j d;u d;u d;u NjUj u=1 n=1 between DBS i and j at slot n. a mod b is the modulo d=1 (10) operation between a and b. P is the pathloss threshold s:t: ¹8aº;¹8bº;¹8cº;¹8dº;¹8eº;¹8 fº;¹8gº; DB for D2B communication. (8a)-(8h) are AoI association and k »n¼ 2 f0; 1g 8d; u; n: d;u D2U communication scheduling constraints, in which (8a) is constraint 1); (8b)-(8d) represent the constraint 2); (8e) and It is worth noting that constraint (8e) and (8g) turn to be (8f) corresponds to constraint 3) and 4), respectively; (8g) linear constraint to K given constant A. Same as problem (9), indicates constraint 5). (8i)-(8l) correspond to DBS trajectory problem (10) can be efficiently solved by the branch and bound constraints 1), 2) and 3). (8m) is the D2B pathloss constraint. method. 6 C. DBS Horizontal Trajectory Optimization substituting r »n¼ tan¹ »n¼º for corresponding h »n¼. Fig. d;u d;u d 2 shows the curves of P »n¼ versus  »n¼ under different d;u d;u The sub-problem to optimize L with constant A, K and H r »n¼. We can prove that the (15) is quasi-convex to  »n¼ d;u d;u can be expressed as and has only one global minimum. The detail proof can be jUj jDj N ÕÕ Õ found in Appendix A. To obtain the optimal  »n¼ at which 1 d;u opt min a ¹ k »n¼P »n¼º d;u d;u d;u L NjUj (11) u=1 d=1 n=1 r [n]=50m d,u s:t: ¹8jº;¹8mº; l »1¼ = l »N + 1¼ 8d: d d r [n]=150m d,u r [n]=250m d,u According to (6), (11) is non-convex for L. Instead of jointly r [n]=350m d,u optimizing L, we further divide the block into its element r [n]=450m d,u variable l »n¼ and revise (11) as d r [n]=550m d,u min a »n¼k »n¼P »n¼+ d;u d;u d;u NjUj l »n¼ jUj jDj ÕÕ Õ (12) a ¹ k »n ¯¼P »n ¯¼º 80 d;u d;u d;u NjUj u=1 d=1 n ¯=1;n ¯,n 0 20 40 60 80 s:t: ¹8jº;¹8mº; l »1¼ = l »N + 1¼ 8d: d d θ [n] (degree) d,u Keeping other l »n ¯¼; 8d; u; n ¯ , n fixed, the second part of Fig. 2: P »n¼ versus  »n¼. d;u d;u (12) turns to be constant. With the given H, we can prove P »n¼ reaches the global minimum, we let the first-order d;u that P »n¼ is a quasi-convex and non-decreasing function derivation of P »n¼ to  »n¼ equals zero: d;u d;u d;u to D2U horizontal distance r »n¼; 8d; u; n. Therefore, min- d;u @P »n¼ d;u = tan¹ »n¼º imizing the objective function in (12) equals minimizing d;u @ »n¼ ln¹10º 2 d;u r »n¼ = kl »n¼ l k , which is a quadratic convex opti- u;d d u ab¹  º exp¹b¹ »n¼ aºº LoS NLoS d;u mization problem for l »n¼: d + = 0: ¹1 + a exp¹b¹ »n¼ aººº d;u min kl »n¼ l k (17) d u l »n¼ (13) (17) is a transcendental equation without closed-form solution. s:t: ¹8jº;¹8mº; l »1¼ = l »N + 1¼; 8d: d d However, considering the fact that (15) has only one global minimum which is the single solution for (17), we can further It is worth noting that the feasible region of l »n¼ constrained calculate the second-order derivation of P »n¼ to  »n¼: d;u d;u by (8m) can form a convex set in any X-Y plane by ignoring the working-zone burst close to the BS antenna [34]. @ P »n¼ 20 d;u = sec ¹ »n¼º d;u ln¹10º @ »n¼ d;u 2 2 D. DBS Flying Height Optimization 2a b ¹  º exp¹2b¹ »n¼ aºº LoS NLoS d;u Similar to problem (11), the sub-problem optimizing H is ¹1 + a exp¹b¹ »n¼ aººº d;u also non-convex with given A, K and L. Further decoupling 2 ab ¹  º exp¹b¹ »n¼ aºº LoS NLoS d;u H into h »n¼ 8d; n, the sub-problem to optimize each h »n¼ d u;d ¹1 + a exp¹b¹ »n¼ aººº d;u is (18) Then, the  »n¼ can be calculated through the Newton- d;u opt min a »n¼k »n¼P »n¼+ d;u d;u d;u h »n¼ NjUj Raphson method: jUj jDj ÕÕ Õ P »n¼ ¹ »n¼ º d;u d;u i (14) »n¼ =  »n¼ (19) d;u i+1 d;u i a ¹ k »n ¯¼P »n ¯¼º d;u d;u d;u 00 P »n¼ ¹ »n¼ º d;u d;u i NjUj u=1 d=1 n ¯=1;n ¯,n where the iteration stops when  »n¼  »n¼ d;u i+1 d;u i s:t: ¹8kº;¹8mº; h »1¼ = h »N + 1¼ 8d: d d and  »n¼ =  »n¼ . The calculation of  »n¼ is d;u opt d;u i+1 d;u opt To solve (14), we first transform (6) as the summation constrained by h »n¼  r »n¼ tan¹ »n¼º  h »n¼ where d d d;u d;u d u of one function of r »n¼ and one function of  »n¼ = d;u d;u h »n¼ and h »n¼ are upper and lower bounds of h »n¼ due d d d u d arctan¹h »n¼r »n¼º: d d;u to D2B link quality constraint. After obtaining  »n¼ for d;u opt each  »n¼, the optimal h »n¼ can be calculated as d;u d opt 4 f (15) P »n¼ = 20 log¹ r »n¼º +  + F¹ »n¼º d;u d;u NLoS d;u h »n¼ d up c 8 >h »n¼ ;  »n¼  arctan¹ º d u d;u opt r »n¼ d;u >< where h »n¼ d down h »n¼ = (20) h »n¼ ;  »n¼  arctan¹ º d opt d d d;u opt r »n¼ > d;u F¹ »n¼º = 20 log¹sec¹ »n¼º > d;u d;u r »n¼ tan¹ »n¼ º; otherwise. d;u d;u opt (16) LoS NLoS + : 1 + a exp¹b¹ »n¼ aºº d;u E. Protect Distance Constraint Since r »n¼ is pre-defined with given L, (15) is constant Given the assumption that all trajectories are closed curves d;u and optimizing h »n¼ equals optimizing  »n¼ in (14) by in 3D space, the start slot of each trajectory can be any slots d d;u Pathloss (dB) 7 on the trajectory. Because all trajectories are assumed to have D2U communication scheduling and DBS trajectories after same length of period N , for any trajectory, different start each iteration t, respectively. W is composed by L and H . t t t slots can lead to different inter-DBS distances at all following According to the BCD method, the proposed algorithm ensures slots. Since that, it is efficient to schedule the start slot of convergence since the global optimal results of all sub-problem each DBS to prevent violating protect distance constraint (8l) are accurately achieved [16] [35]. in following slots. We address protect distance constraint in Initial trajectories are required for the first iteration of AoI the start slot scheduling process due to two reasons: First, association. Without loss of generality, we set the same initial the feasible set of constraint (8l) is non-convex for trajectory height h 2 »h »n¼ ; h »n¼ ¼ for all DBS. For each DBS, 0 d d d u related variables, i.e., L and H, optimizing them in horizontal we apply a circle initial trajectory with radius r = 1 m. trajectory or height optimization problems can significantly Given the assumption in subsection A that the initial D2U increase the problem complexity. Besides, by ensuring the communication scheduling k »n¼ equals one for 8d; u; n, it d;u protect distance constraint through start slot scheduling, the is better to deploy the center of each circle trajectory to DBS trajectory planning result can be maintained, which the position where the summation of D2U pathloss between achieves better average D2U pathloss than modifying those its adjacent AoIs (will be associated to the DBS with high optimized trajectories. Since the start slot scheduling is not probability) is minimized. Therefore, the classic k-means an optimization problem, we can accept any start slots set algorithm can be effectively applied to determine the initial as long as it ensures constraint (8l). In this work, we apply trajectory center of each DBS by substituting D2U pathloss a greedy-based searching algorithm, as shown in Algorithm for the geometric distance in original algorithm. To reduce 1, to iteratively schedule the start slots of all DBSs d 8i = the convergence time and improve the result quality, we apply 1; 2; : : :;jDj. In each iteration, d sequentially sets its start the k-means ++ algorithm which prefers centroid seeds with slot as n 8j = 1; 2; : : :; N and calculate the 3D distances large mutual distances [36]. between d and previous scheduled d 8k  i at every slots. i k Algorithm 2 Multi-DBS 3D trajectory planning and schedul- If any start slot n ensures protect distance constraint at every ing algorithm Algorithm 1 Start slots scheduling algorithm 1: Initiate initial U2D communication scheduling K , initial height h . 1: Generate start slots set S = fn = 1; n = 1; : : :; n = 1g 0 1 2 jDj 2: Calculate initial horizontal trajectory L through k-means for DBS d ; d ; : : :; d . 0 1 2 jDj ++ algorithm. 2: for i = 1; 2; : : :;jDj do 3: Set t = 1, W = 1. 3: for j = 1; 2; : : :; N do 4: while W   do 4: Set d ’s start slot as n . i j 5: Solve problem (9) to obtain A by treating K , L 5: Calculate distance between d and d 8k  i at all t t1 t1 i k and H as constants. slots with d starts at n . t1 i j 6: Solve problem (10) to obtain K by treating A , L 6: Break if all distances are larger than Z t t t1 min and H as constants. 7: end for t1 7: for d 2 D; n = 1; 2; : : :; N do 8: if Z is violated for all n 2 N then min j 8: Solve problem (12) to obtain L »n¼ by treating 9: Set i = 1; n = n + 1. d opt 1 1 A , K , H and L »n ¯¼ 8d; n ¯ , n as constants. 10: end if t t t1 d 9: Update L with l »n¼ . 11: end for t d opt 10: end for 11: for d 2 D; n = 1; 2; : : :; N do slots, the start slot of d is temporally scheduled to n and i j 12: Solve problem (14) to obtain h »n¼ by treating break to the d iteration. If all n 8j = 1; 2; : : :; N on d opt i+1 j A , K , L and h »n ¯¼ 8d; n ¯ , n as constants. d ’s trajectory cannot ensure protect distance constraint, the t t t d 13: Update H with h »n¼ . algorithm abandons the current and all previous scheduled t d opt 14: end for DBSs and re-run the first iteration of d with updated start 15: Update W with L and H . slot n = n + 1. Algorithm 1 stops until all d are scheduled t t t 1 1 i 16: t = t + 1. with feasible start slots. 17: W = W W . t t1 18: end while F. Proposed Algorithm 19: Run Algorithm 1 to ensure protect distance constraint. By decoupling the decision variable set into multiple blocks, i.e., A , K , l »n¼ 8d; n, h »n¼ 8d; n, each block’s sub-problem t t d d can be optimized respectively with other blocks keeping VI. NUMERICAL RESULTS constant. Therefore, the problem (8) can be solved through iteratively optimizing those sub-problems until the results We conduct extensive simulations to verify the perfor- converge, which yields to the classic BCD method. Based on mance of our proposed algorithm in minimizing average the BCD method, we propose the algorithm to solve the multi- D2U pathloss of the network. The simulations are link level DBS 3D trajectory planning and scheduling problem, which without simulating specific MAC or upper layers protocols. shows in Algorithm 2. A , K , W denote the AoI association, The BS is located at the origin point (coordinate ¹0; 0; 0º) t t t 8 and the side-length of grid is set to 20 m. Both U2D and D2B pathloss models are configured in suburban scenario. DBS−1 DBS−2 To provide additional spectrum resources for DA-RAN and DBS−3 reduce the interference to terrestrial RAN users, the frequency DBS−4 DBS−5 band of D2U communication f is expected to be different Start point AoI from the licensed cellular band. Like most commercial drone BS products [37] [38] and DBS related works [39] [7] [19] [28], we use the 2:4 GHz unlicensed band as the carrier for D2U 50 communications. D2B communications use the 850 MHz LTE band according to the D2B pathloss model [6]. By allocating different carrier frequencies, the interference between D2U 500 and D2B communication can be prevented. Initial height h is 0 0 −500 −500 set to 80 m within the working-zone of DBS over the whole BS Y−axis (m) X−axis (m) radio coverage area [34]. We treat  as the minimal time unit (a) 3D view to calculate related variables including V , H , etc. There max max is no need to assign specific value for  in the simulation, DBS−1 DBS−2 however, according to the general specifications of commercial DBS−3 drones (50 70 kmh for horizontal speed, 3 5 ms for DBS−4 DBS−5 ascent/descent speed) [40], the approximate value of  is Start point AoI around 10 s. Table. I shows detail simulation parameters. BS TABLE I: Simulation Parameters −200 −400 Parameters Numerical Values −600 BS radio coverage radius r 900 m BS AoI number jUj 20 −800 D2U parameters ¹ ;  ; a; bº (0.1,21,4.88,0.43) LoS NLoS −800 −400 0 400 800 D2B parameters ¹ ; A;  ; B;  º (3.04,-23.29,-3.61,4.14,20.7) 0 0 X−axis (m) Carrier frequencies (D2U, D2B) ¹2:4 GHz; 850 MHzº (b) 2D projection on X-Y plane Slots amount in one period N 60 slot D2B pathloss constraint P 80 dB DB Minimal per-AoI slot number S 10 slot min DBS−1 Maximal per-DBS AoI number jA j 6 DBS−2 max DBS−3 Maximal horizontal speed V 30; 50; 70; 90; 110 mslot max DBS−4 Maximal vertical speed H 10 mslot max DBS−5 Protect Distance Z 200 m min 100 Trajectory difference  0:1 m for each slot A. 3D Trajectory Planning for Multiple DBSs Fig. 3 shows the scenario where the trajectories of five DBSs are optimized to serve twenty AoIs with V = 90 mslot. The max closed curves dotted by different markers in Fig. 3(a) and Fig. 0 10 20 30 40 50 60 3(b) denote different DBS trajectories; the squares on the X- Time Step (slot) Y plane represent AoIs. AoIs are associated to corresponding (c) Heights DBSs with same colors. Fig. 3(c) illustrates the changes of flying height within one period. As shown in Fig. 3(a) and 3(b), for each DBS, the optimized trajectory can fly over all 0.8 its associated AoIs and form a closed curve in 3D space. In Inter−DBS distance Fig. 3(c), all DBS flying height curves are lower bounded constraint 0.6 around 78 m, which is the lower bound of h »n¼ due to the d d D2B pathloss constraint. Note that for each trajectory in Fig. 3(b), the summation of 0.4 dots on the section between two AoIs is less than 50% of the total slots number N . Besides, the height curves in Fig. 3(c) 0.2 show the trend to maintain fixed values for consecutive slots. Combining Figs. 3(b) and 3(c), we can justify that the remain- 0 200 400 600 800 1000 1200 1400 ing dots in Fig. 3(b) are overlapped above the associated AoIs, Inter−DBS Distance (m) and those overlapped dots corresponds to the consecutive slots (d) Protect distance guarantee have fixed heights in Fig. 3(c). In other word, the proposed Fig. 3: Trajectory planning results of 5 DBSs serving 20 AoIs. algorithm prefers hovering DBSs above the associated AoIs, Y−axis (m) CDF DBS Height (m) Height (m) 9 DBS−1 DBS−1 DBS−1 DBS−1 800 110 800 110 DBS−2 DBS−2 DBS−2 DBS−2 DBS−3 DBS−3 DBS−3 DBS−3 600 600 105 105 DBS−4 DBS−4 DBS−4 DBS−4 Start point Start point 400 400 AoI AoI 100 100 BS BS 200 200 95 95 0 0 90 90 −200 −200 −400 −400 85 85 −600 −600 80 80 −800 −800 75 75 −500 0 500 0 10 20 30 40 50 60 −500 0 500 0 10 20 30 40 50 60 X−axis (m) Time Step (slot) X−axis (m) Time Step (slot) (a) V = 30 mslot (b) Heights of V = 30 mslot (c) V = 110 mslot (d) Heights of V = 110 mslot max max max max Fig. 4: Trajectory planning results impacted by horizontal speeds. 800 DBS−1 110 DBS−1 DBS−1 110 DBS−1 DBS−2 DBS−2 DBS−2 DBS−2 DBS−3 DBS−3 DBS−3 DBS−3 105 105 DBS−4 DBS−4 600 DBS−4 DBS−4 Start point DBS−5 DBS−5 AoI DBS−6 DBS−6 100 100 BS DBS−7 DBS−7 Start point 95 AoI 95 BS 90 90 −200 −200 −400 85 85 −400 −600 80 80 −600 −800 75 −800 75 −500 0 500 0 10 20 30 40 50 60 −500 0 500 0 10 20 30 40 50 60 X−axis (m) Time Step (slot) X−axis (m) Time Step (slot) (a) jDj = 4 (b) Heights of jDj = 4 (c) jDj = 7 (d) Heights of jDj = 7 Fig. 5: Trajectory planning results impacted by DBS number. while leave minimal slots for the travelling process between within one period. In Fig. 4(c) where V is high enough, max adjacent hovering positions. Such a “hovering effect” can be the DBSs can even hovering on each associated AoI for few explained as follows. For any slot n, the proposed algorithm slots since the flying interval between two hovering positions is prone to small r »n¼ which minimizes the D2U pathloss requires less slots. Comparing Fig. 4(b) and 4(d), we can see d;u with given h »n¼. On the contrary, the smaller the r »n¼ is, the that the variation of flying height with V = 30 mslot d d;u max higher the probability that r »n¼ »n¼  h »n¼ . Based on is larger than the height variation with V = 110 mslot. d;u d;u opt d d max (20), if r »n¼ »n¼  h »n¼ , the optimal height equals Because in low V scenario, the travelling process between d;u d;u opt d d max the lower bound of flying height h »n¼ at current position. two AoIs requires more slots than that in the high V d d max Since the minimal r »n¼ equals zero, the minimal average scenario, the optimal height r »n¼ tan¹ »n¼ º in small d;u d;u d;u opt D2U pathloss can be achieved by the trajectory with most V has higher probability to fall into the feasible flying max slots hovering above the AoIs. From Fig. 3(c), we can see height range. Considering the four DBSs trajectory planning that several height bursts occur when each DBS is flying scenario, the CDF of D2U pathloss under different V are max between two AoI with a long inter-AoI distance. At those compared in Fig. 6. Given any pathloss threshold, We can see slots, the DBS is relatively far from the scheduled AoI and that the probability of D2U pathloss less than the threshold r »n¼ tan¹ »n¼ º can fall in the feasible height range raises as the V increases. d;u d;u opt max between h »n¼ and h »n¼ constrained by D2B pathloss d d d u Fig. 5 compares the trajectory planning results when jDj = threshold. Therefore, the optimal heights prefer to approach 4 and jDj = 7. The horizontal speed is set as V = 70 mslot max the value of r »n¼ tan¹ »n¼ º in those slots, which leads d;u d;u opt for both scenarios. As the number of available DBS increases, to the height bursts. Fig. 3(d) shows the cumulative distribution the average number of AoI associated to one DBS is reduced, function (CDF) of inter-DBS distance within one period T . The some trajectories can even degenerate to one static deployment red dotted line is the protect distance constraint. It can be seen position when the corresponding DBS is associated with only that all inter-DBS distances of the final trajectory planning one AoI. On the other hand, since the average r »n¼ length d;u result are larger than the protect distance threshold Z , min is also reduced with the decreasing of associated AoI number which indicates the effectiveness of the start slots scheduling for each DBS, the variation of flying height can be reduced algorithm to ensure protect distance constraint. with the increasing of jDj. Fig. 7 shows the CDF of D2U pathloss under different jDj. Similar to Fig. 6, the probability Fig. 4 presents two groups of trajectory planning results of D2U pathloss less than any given threshold increases as with V = 30 mslot and V = 110 mslot, respectively. max max more numbers of DBS are provided. The available DBS number jDj equals four for both groups. As shown in Fig. 4, the AoI associations are same under Fig. 6 and Fig. 7 indicate that the D2U pathloss performance different V . The trajectories in Fig. 4(a) cannot fly over can be influenced by both V and jDj. In Fig. 8, we further max max every associated AoI since the maximal horizontal speed is too investigate the average pathloss performance with different small to ensure the DBSs to approach every associated AoIs V and jDj. From preceding analyses, we know that both the max Y−axis (m) Y−axis (m) DBS Height (m) DBS Height (m) Y−axis (m) Y−axis (m) DBS Height (m) DBS Height (m) 10 Comparing the performance gaps between ITs, we note that 0.9 applying k-means ++ algorithm has more significant impact 0.8 to both average D2U pathloss and pathloss standard deviation 0.7 than using circle-shaped IT. 0.6 0.5 83 4 DBSs 5 DBSs 0.4 6 DBSs 7 DBSs 0.3 110m/slot 90m/slot 0.2 70m/slot 80 50m/slot 0.1 30m/slot 78 79 80 81 82 83 84 85 86 87 78 Pathloss (dB) Fig. 6: CDF of D2U pathloss under different V . max 0.9 30 50 70 90 110 0.8 Maximal Horizontal Speed (m/slot) 0.7 Fig. 8: Average D2U pathloss with different horizontal speeds 0.6 and DBS numbers. 0.5 0.4 non−k−means, point IT 0.3 non−k−means, circle IT 7 DBSs k−means, point IT 0.2 k−means, circle IT 6 DBSs 5 DBSs 0.1 4 DBSs 78 79 80 81 82 83 84 85 Pathloss (dB) Fig. 7: CDF of D2U pathloss under different jUj. higher V and larger jDj can lead to smaller average r , max d;u 76 which eventually reduces the average pathloss level. According to Fig. 8, given the same number of DBS, the average 4 5 6 7 pathloss level decreases slightly as the V increases; while max DBS Number significant average pathloss level reduction occurs as the jDj Fig. 9: Initial trajectory comparison. increases under fixed maximal horizontal speed. Therefore, we can conclude that both raising the horizontal speed and B. Performance Comparison increasing the number of available DBS can promote the av- erage D2U pathloss performance of DBS trajectory planning, To highlights the efficiency of the proposed multi-DBS while increasing the number of available DBSs is proved to 3D trajectory planning and scheduling, we compare the av- be more efficient than raising horizontal flying speed. Note erage D2U pathloss performance achieved by our proposed that this conclusion is valid for the average D2U pathloss trajectory planning algorithm, as well as the static DBS performance of the whole network only. Since the standard deployment scheme in Fig. 10 and Table II. For static DBS deviations of pathloss (error-bars) plotted in Fig. 8 are highly deployment algorithm, we use the per-drone iterated particle overlapped with each other, the D2U pathloss performance swarm optimization (DI-PSO) algorithm proposed in [34]. of specific DBS-to-AoI pair can vary a lot. Nevertheless, as Without loss of generality, we use all data achieved by the horizontal speed and available DBS number increase, the V = 30; 50; 70; 90; 110 mslot to calculate the average D2U max standard deviation is reduced, which indicates that the user pathloss of the proposed trajectory planning algorithm. From fairness can also be promoted by raising V and jDj. Fig. 10, we can see that the average D2U pathloss of both max We further analyze the impacts of different initial trajecto- algorithms are reduced as the available DC number increases. ries (ITs) to the achieved average D2U pathloss performance. However, the D2U pathloss performance achieved by our We compare four types of ITs, i.e., 1) circle IT with the trajectory planning algorithm maintains 10 15 dB smaller center location determined by k-means ++; 2) point IT (where than that achieved by the DI-PSO algorithm. the trajectory shrinks to one hovering point) with the point The user fairness promotion provided by the proposed location determined by k-means ++; 3) circle IT with the trajectory planning algorithm is indicated by the error-bars in center location uniformly distributed over jSj ; 4) point IT Fig. 10 and the D2U pathloss standard deviation comparison bs with the point location uniformly distributed over jSj . Fig. in Table II.  and  are D2U pathloss standard deviations t s bs 9 shows the comparison result. We can see that the k-means- for DBS trajectory planning and static DBS deployment, based circle IT used in the proposed algorithm achieves min- respectively. In Fig. 10, we can see that the standard deviation imal average D2U pathloss and pathloss standard deviation. of D2U pathloss achieved by both algorithms are reduced as Probability Probability Average D2U Pathloss (dB) Average D2U Pathloss (dB) 11 the MINLP problem into multiple solvable sub-problems, DBS Trajectory Planning DBS Static Deployment and devised a BCD-based multi-DBS 3D trajectory planning and scheduling algorithm in which the AoI association, U2D communication scheduling, horizontal trajectories, and fly- 85 ing altitudes of DBSs are iteratively optimized. A start slot scheduling algorithm and a k-means-based circle IT have been proposed to ensure the protect distance constraint and generate initial DBS trajectories. We have investigated the impacts of available DBS number, horizontal speed and different IT on the achieved average D2U pathloss. Simulation results have shown that the proposed algorithm can achieve 10 15 dB 4 5 6 7 average D2U pathloss reduction, and promote pathloss stan- DBS number dard deviation by 68% when compared with the static DBS Fig. 10: Average D2U pathloss comparison between trajectory deployment algorithm. In future works, we will investigate planning and static deployment of multiple DBSs. the communication and resource allocation of multiple DBS in DA-RAN based on the optimized trajectories. the available DBS number increases. While the  maintains less than half of the  , there is no overlap between the APPENDIX A error-bars achieved by two algorithms. From Table II, we can calculate that the DBS trajectory planning can lower the D2U Since the first two parts of (15) are constant or the function pathloss standard deviation by 68:34% on average compared of r »n¼, analyzing the convexity of (15) is equal to analyzing d;u with the static DBS deployment. the convexity of (16). (16) can be regarded as the summation To highlight the cost-efficiency of the trajectory planning of two functions: algorithm, and provide a guideline to determine the number of F¹ »n¼º = F ¹ »n¼º + F ¹ »n¼º d;u 1 d;u 2 d;u required DBS, we compare the minimal required DBS number = 20 log¹sec¹ »n¼º + F ¹ »n¼º d;u 2 d;u (21) under different D2U pathloss thresholds in Table III. The D2U LoS NLoS pathloss threshold is a strict constraint, which means that for = 20 log¹sec¹ »n¼º + : d;u 1 + a exp¹b¹ »n¼ aºº d;u any DBS at any slot, the D2U pathloss to any AoI cannot The first-order derivations of F ¹ »n¼º and F ¹ »n¼º are exceed it. As shown in Table III, under the same D2U pathloss 1 d;u 2 d;u threshold, the minimal required DBS amount is decreased F ¹ »n¼º = tan¹ »n¼º; (22a) d;u d;u as the maximal horizontal speed of DBS increases. Besides, 1 ln¹10º given any threshold levels, the static DBS deployment always ab¹  º exp¹b¹ »n¼ aºº LoS NLoS d;u F ¹ »n¼º = : (22b) requires two to four more DBSs than the DBS trajectory d;u ¹1 + a exp¹b¹ »n¼ aººº d;u planning algorithm, which implies that the DBS trajectory We further calculate the second-order derivations of planning algorithm is more economical than the static DBS F ¹ »n¼º and F ¹ »n¼º as deployment. 1 d;u 2 d;u 00 2 TABLE II: D2U pathloss standard deviation comparison F ¹ »n¼º = sec ¹ »n¼º; (23a) d;u d;u ln¹10º DBS number 4 5 6 7 ab ¹  º exp¹b¹ »n¼ aºº NLoS LoS d;u 2:1203 2:0476 1:3923 0:9887 F ¹ »n¼º = t d;u ¹1 + a exp¹b¹ »n¼ aººº d;u 6:8313 6:7562 4:2329 3:0530 2 2 ¹  º 68:96% 69:69% 67:11% 67:61% s t s 2a b ¹  º exp¹2b¹ »n¼ aºº NLoS LoS d;u : (23b) ¹1 + a exp¹b¹ »n¼ aººº d;u TABLE III: Minimal DBS amounts comparison Note that (23a) is always larger than zero for all  »n¼ 2 d;u D2U pathloss threshold (dB) 98 95 92 89 86 »0 ; 90 ¼, so (22a) is proved to be non-decreasing function. 30mslot 3 4 5 6 8 Let (23b) equals zero, we can calculate the only root of (23b) 30mslot 3 4 5 6 8 »n¼ = a + ln¹aºb at which (22b) achieves its global d;u root 70mslot 3 4 4 6 7 90mslot 3 4 4 5 7 minimum. 110mslot 3 3 4 4 6 Given the suburban scenario parameters ¹ ;  ; a; bº = LoS NLoS Static deployment 6 7 8 10 10 ¹0:1; 21; 4:88; 0:43º, we can calculate that: 0  0 F ¹90 º + F ¹90 º  0; (24a) 1 2 VII. C ONCLUSION 0 0 F ¹ »n¼ º + F ¹ »n¼ º  0; (24b) d;u root d;u root 1 2 In this paper, we have studied the 3D trajectory planning 0  0 F ¹0 º + F ¹0 º  0: (24c) 1 2 and scheduling for multiple DBSs in DA-RAN with the state- 0 0 of-the-art D2U and D2B pathloss models considered. We which indicates F ¹ »n¼º + F ¹ »n¼º, i.e., (17), has only d;u d;u 1 2 have formulated the MINLP problem to minimize the average one root between  »n¼ and 90 . Therefore, we can d;u root D2U pathloss achieved by multi-DBS trajectory planning and conclude that (16) is a uni-modal function with only one global scheduling. To solve the MINLP problem, we have decoupled minimum for all  »n¼ 2 »0 ; 90 ¼. d;u Average D2U Pathloss (dB) 12 Define the  »n¼ achieves the global minimum of (16) as [17] Q. Wu and R. Zhang, “Common throughput maximization in UAV- d;u enabled OFDMA systems with delay consideration,” IEEE Trans. Com- »n¼ , a 2 »0 ; 90 ¼, b 2 »0 ; 90 ¼ and t = a+¹1ºb 8 2 d;u opt mun., vol. 66, no. 12, pp. 6614–6627, 2018. »0; 1¼. If a  b   »n¼ , (16) is non-increasing function d;u opt [18] A. Al-Hourani, S. Kandeepan, and S. Lardner, “Optimal lap altitude for to t and F¹bº  F¹tº  F¹aº. If  »n¼  a  b, (16) maximum coverage,” IEEE Wireless Commun. Lett., vol. 3, no. 6, pp. d;u opt 569–572, 2014. is non-decreasing function to t and F¹aº  F¹tº  F¹bº. If [19] M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Mobile unmanned a   »n¼  b, (16) ensures that F¹tº  maxfF¹aº; F¹bºg. d;u opt aerial vehicles (UAVs) for energy-efficient internet of things communica- Since that, we can argue that for any a 2 »0 ; 90 ¼ and b 2 tions,” IEEE Trans. Wireless Commun., vol. 16, no. 11, pp. 7574–7589, »0 ; 90 ¼: [20] C. Zhang and W. Zhang, “Spectrum sharing for drone networks,” IEEE J. Sel. Areas Commun., vol. 35, no. 1, pp. 136–144, 2017. F¹a +¹1 ºbº  maxfF¹aº; F¹bºg 8 2 »0; 1¼ (25) [21] L. Zhou, Z. Yang, S. Zhou, and W. Zhang, “Coverage probability analysis of UAV cellular networks in urban environments,” in Proc. which corresponds to the definition of quasi-convex function. IEEE ICC Workshops, Kansas City, MO, May. 2018, pp. 1–6. [22] S. A. W. Shah, T. Khattab, M. Z. Shakir, and M. O. Hasna, “A distributed Therefore, (15) is a quasi-convex function with only one global approach for networked flying platform association with small cells in minimum. 5g+ networks,” in Proc. IEEE GLOBECOM, Singapore, Singapore, Dec. 2017, pp. 1–7. [23] A. Fouda, A. S. Ibrahim, I. Guvenc, and M. Ghosh, “UAV-based REFERENCES in-band integrated access and backhaul for 5G communications,” 2018. [Online]. Available: https://arxiv.org/abs/1807.07230. [1] I. Bor-Yaliniz and H. Yanikomeroglu, “The new frontier in RAN [24] K. Li, W. Ni, X. Wang, R. P. Liu, S. S. Kanhere, and S. Jha, “Energy- heterogeneity: Multi-tier drone-cells,” IEEE Commun. Mag., vol. 54, efficient cooperative relaying for unmanned aerial vehicles,” IEEE Trans. no. 11, pp. 48–55, 2016. Mobile Comput., vol. 15, no. 6, pp. 1377–1386, 2016. [2] S. Zhang, W. Quan, J. Li, W. Shi, P. Yang, and X. Shen, “Air-ground [25] M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Unmanned aerial integrated vehicular network slicing with content pushing and caching,” vehicle with underlaid device-to-device communications: Performance IEEE J. Sel. Areas Commun., vol. 36, no. 9, pp. 2114–2127, 2018. and tradeoffs,” IEEE Trans. Wireless Commun., vol. 15, no. 6, pp. 3949– [3] Q. Ye, J. Li, K. Qu, W. Zhuang, X. Shen, and X. Li, “End-to-end quality 3963, 2016. of service in 5g networks: Examining the effectiveness of a network [26] Y. Zeng and R. Zhang, “Energy-efficient UAV communication with slicing framework,” IEEE Veh. Technol. Mag., vol. 13, no. 2, pp. 65–74, trajectory optimization,” IEEE Trans. Wireless Commun., vol. 16, no. 6, pp. 3747–3760, 2017. [4] M. Mozaffari, W. Saad, M. Bennis, Y. Nam, and M. Debbah, “A tutorial [27] J. Lyu, Y. Zeng, and R. Zhang, “Cyclical multiple access in UAV-aided on UAVs for wireless networks: Applications, challenges, and open communications: A throughput-delay tradeoff,” IEEE Wireless Commun. problems,” IEEE Commun. Surveys Tuts., early access, 2019. Lett., vol. 5, no. 6, pp. 600–603, 2016. [5] Z. M. Fadlullah, D. Takaishi, H. Nishiyama, N. Kato, and R. Miura, “A [28] H. Zhao, H. Wang, W. Wu, and J. Wei, “Deployment algorithms for dynamic trajectory control algorithm for improving the communication uav airborne networks toward on-demand coverage,” IEEE J. Sel. Areas throughput and delay in UAV-aided networks,” IEEE Netw., vol. 30, Commun., vol. 36, no. 9, pp. 2015–2031, 2018. no. 1, pp. 100–105, 2016. [29] N. Summers, “EE looks to drones and big balloons to tackle 4G [6] A. Al-Hourani and K. Gomez, “Modeling cellular-to-UAV path-loss for ’notspots’,” 2017. [Online]. Available: https://www.engadget.com/2017/ suburban environments,” IEEE Wireless Commun. Lett., vol. 7, no. 1, 02/21/ee-drone- balloon-truck- 4g-coverage. pp. 82–85, 2018. [30] Q. Li, S. Feng, X. Ge, G. Mao, and L. Hanzo, “On the performance [7] A. Dhekne, M. Gowda, and R. R. Choudhury, “Cell tower extension of full-duplex multi-relay channels with df relays,” IEEE Trans. Veh. through drones: Poster,” in Proc. ACM MobiCom, New York, NY, Oct. Technol., vol. 66, no. 10, pp. 9550–9554, 2017. 2016, pp. 456–457. [31] Q. Li, M. Yu, A. Pandharipande, X. Ge, J. Zhang, and J. Zhang, [8] F. Lyu, H. Zhu, H. Zhou, L. Qian, W. Xu, M. Li, and X. Shen, “Momac: “Performance of virtual full-duplex relaying on cooperative multi-path Mobility-aware and collision-avoidance mac for safety applications in relay channels,” IEEE Trans. Wireless Commun., vol. 15, no. 5, pp. vanets,” IEEE Trans. Veh. Technol., vol. 67, no. 11, pp. 10 590–10 602, 3628–3642, 2016. [32] R. I. Bor-Yaliniz, A. El-Keyi, and H. Yanikomeroglu, “Efficient 3D [9] Z. Xue, J. Wang, G. Ding, Q. Wu, Y. Lin, and T. A. Tsiftsis, “Device-to- placement of an aerial base station in next generation cellular networks,” device communications underlying UAV-supported social networking,” in Proc. IEEE ICC, Kuala Lumpur, Malaysia, May. 2016, pp. 1–5. IEEE Access, vol. 6, pp. 34 488–34 502, 2018. [33] “Gurobi optimizer 8.1.” [Online]. Available: http://www.gurobi.com. [10] N. Cheng, F. Lyu, W. Quan, C. Zhou, H. He, W. Shi, and X. Shen, [34] W. Shi, J. Li, W. Xu, H. Zhou, N. Zhang, S. Zhang, and X. Shen, “Space/aerial-assisted computing offloading for IoT applications: A “Multiple drone-cell deployment analyses and optimization in drone learning-based approach,” IEEE J. Sel. Areas Commun., vol. 37, no. 5, assisted radio access networks,” IEEE Access, vol. 6, pp. 12 518–12 529, pp. 1117–1129, 2019. [11] D. Takaishi, Y. Kawamoto, H. Nishiyama, N. Kato, F. Ono, and [35] D. P. Bertsekas, Nonlinear programming. Belmont, MA, USA: Athena R. Miura, “Virtual cell based resource allocation for efficient frequency scientific, 1999. utilization in unmanned aircraft systems,” IEEE Trans. Veh. Technol., [36] D. Arthur and S. Vassilvitskii, “k-means++: The advantages of careful vol. 67, no. 4, pp. 3495–3504, 2018. seeding,” in Proc. ACM-SIAM, Philadelphia, PA, Jan. 2007, pp. 1027– [12] S. Jeong, O. Simeone, and J. Kang, “Mobile edge computing via a uav- mounted cloudlet: Optimization of bit allocation and path planning,” [37] DJI, “Mavic pro platinumspecs,” 2018. [Online]. Available: https: IEEE Trans. Veh. Technol., vol. 67, no. 3, pp. 2049–2063, 2018. //www.dji.com/mavic-pro- platinum/info#specs. [13] M. Chen, M. Mozaffari, W. Saad, C. Yin, M. Debbah, and C. S. Hong, [38] N. Cheng, W. Xu, W. Shi, Y. Zhou, N. Lu, H. Zhou, and X. Shen, “Air- “Caching in the sky: Proactive deployment of cache-enabled unmanned ground integrated mobile edge networks: Architecture, challenges, and aerial vehicles for optimized quality-of-experience,” IEEE J. Sel. Areas opportunities,” IEEE Commun. Mag., vol. 56, no. 8, pp. 26–32, 2018. Commun., vol. 35, no. 5, pp. 1046–1061, 2017. [39] I. Bor-Yaliniz, A. El-Keyi, and H. Yanikomeroglu, “Spatial configuration [14] N. H. Motlagh, T. Taleb, and O. Arouk, “Low-altitude unmanned aerial of agile wireless networks with drone-bss and user-in-the-loop,” IEEE vehicles-based internet of things services: Comprehensive survey and Trans. Wireless Commun., vol. 18, no. 2, pp. 753–768, 2019. future perspectives,” IEEE Internet Things J., vol. 3, no. 6, pp. 899– [40] C. Tseng, C. Chau, K. M. Elbassioni, and M. Khonji, “Autonomous 922, 2016. recharging and flight mission planning for battery operated autonomous [15] J. Liu, Y. Shi, Z. M. Fadlullah, and N. Kato, “Space-air-ground integrated drones,” 2017. [Online]. Available: http://arxiv.org/abs/1703.10049. network: A survey,” IEEE Commun. Surveys Tuts., vol. 20, no. 4, pp. 2714–2741, 2018. [16] Q. Wu, Y. Zeng, and R. Zhang, “Joint trajectory and communication design for multi-UAV enabled wireless networks,” IEEE Trans. Wireless Commun., vol. 17, no. 3, pp. 2109–2121, 2018. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Electrical Engineering and Systems Science arXiv (Cornell University)

Multi-Drone 3D Trajectory Planning and Scheduling in Drone Assisted Radio Access Networks

Loading next page...
 
/lp/arxiv-cornell-university/multi-drone-3d-trajectory-planning-and-scheduling-in-drone-assisted-hIMr9w4hMu

References (40)

ISSN
0018-9545
eISSN
ARCH-3348
DOI
10.1109/TVT.2019.2925629
Publisher site
See Article on Publisher Site

Abstract

Multi-Drone 3D Trajectory Planning and Scheduling in Drone Assisted Radio Access Networks Weisen Shi, Junling Li, Nan Cheng, Feng Lyu, Shan Zhang, Haibo Zhou, and Xuemin (Sherman) Shen, Fellow, IEEE Abstract—Drone base station (DBS) is a promising technique is to deploy massive small cells, which, however, is inefficient to extend wireless connections for uncovered users of terrestrial and costly for RAN operators [4]. To overcome the coverage radio access networks (RAN). To improve user fairness and and flexibility challenges faced by current RAN, the emerging network performance, in this paper, we design 3D trajectories of drone, a.k.a. unmanned aerial vehicle (UAV), communication multiple DBSs in the drone assisted radio access networks (DA- technology is proposed as a promising solution. RAN) where DBSs fly over associated areas of interests (AoIs) and relay communications between the base station (BS) and users Equipped with specific wireless transceivers, drones can in AoIs. We formulate the multi-DBS 3D trajectory planning communicate with both terrestrial users and cellular base and scheduling as a mixed integer non-linear programming stations (BSs) using WiFi [5] or LTE [6] technologies. By (MINLP) problem with the objective of minimizing the average integrating drone communication with terrestrial RAN, the DBS-to-user (D2U) pathloss. The 3D trajectory variations in drone assisted radio access networks (DA-RAN), in which both horizontal and vertical directions, as well as the state- of-the-art DBS-related channel models are considered in the drones perform as drone base stations (DBSs) to relay data formulation. To address the non-convexity and NP-hardness of between users in areas of interests (AoIs) and the associated the MINLP problem, we first decouple it into multiple integer terrestrial BS , has been proposed and verified by field exper- linear programming (ILP) and quasi-convex sub-problems in iments [7]. In DA-RAN, AoI includes both the CHs and the which AoI association, D2U communication scheduling, hori- traffic dense spots (TDBs) where the allocated RAN spectrum zontal trajectories and flying heights of DBSs are respectively optimized. Then, we design a multi-DBS 3D trajectory planning resources are temporarily inadequate, e.g. congested road, and scheduling algorithm to solve the sub-problems iteratively concerts and sports events, etc. Compared with the terrestrial based on the block coordinate descent (BCD) method. A k-means- RAN, DA-RAN advances in following four aspects: 1) The based initial trajectory generation and a search-based start slot line-of-sight (LoS) probability for the DBS-to-ground (D2G) scheduling are considered in the proposed algorithm to improve wireless link is higher than the terrestrial BS-to-user wireless trajectory design performance and ensure inter-DBS distance constraint, respectively. Extensive simulations are conducted to link [4]. Experiments indicate that LoS links probability is investigate the impacts of DBS quantity, horizontal speed and the dominating factor to increase network performance [8]; 2) initial trajectory on the trajectory planning results. Compared DBSs can be dynamically deployed and dispatched to different with the static DBS deployment, the proposed trajectory planning controllers/users with respect to the spatial and temporal traffic can achieve 10-15 dB reduction on average D2U pathloss, and variations [9]; 3) unlike connected vehicles whose mobility is reduce the D2U pathloss standard deviation by 68%, which indicate the improvements of network performance and user controlled by drivers or autonomous driving controller, the tra- fairness. jectories of DBSs can be fully controlled by system providers, which empowers DBSs with the dynamic deployment feature Index Terms—Drone Communication, Drone Base Station, Trajectory Planning, DA-RAN, Space-Air-Ground Integration. [10] [11]; 4) DBS are capable of executing computing tasks by equipping with CPU or caching modules [12] [13]. However, it is challenging to fully utilize the potential of DBSs due to I. I NTRODUCTION the following two reasons. First, the 3D mobility of DBS poses The future radio access networks (RAN) is expected to great complexity on the DBS spatial placement, especially in provide ubiquitous connectivity for any users or devices at multi-DBS scenarios [14]. Second, specific channel models any time with diversified service requirements [1]. However, are required to highlight the unique features of DBS-to-user coverage holes (CH) of terrestrial RAN prevail in both urban (D2U) and DBS-to-BS (D2B) channels[15]. and rural scenarios due to the lack of infrastructures or deeply Several studies optimizing the multi-DBS spatial placements blocking by obstacles [2]. Specifically, as the terrestrial RAN to support terrestrial users emerges in recent year, which can are statically fixed in certain geographical locations, it is be divided into two categories, i.e., static DBS deployment normally hard to ensure the quality of service (QoS) of users and DBS trajectory planning. The static DBS deployment that are uneven and dynamically distributed in both spatial research focus on optimizing the hovering positions of DBSs and temporal domain [3]. One solution to address those CHs to maximize terrestrial users QoS. However, the static de- ployment fails to guarantee the fairness for users, in which W. Shi, J. Li, N. Cheng (corresponding author), F. Lyu, and X. Shen are the users located at the edge of the DBS’s radio coverage with the Department of Electrical and Computer Engineering, University of suffer relatively higher pathloss compared with the users Waterloo, 200 University Avenue West, Waterloo, Ontario, Canada, N2L 3G1, (email: fw46shi, j742li, n5cheng, f2lyu, ssheng@uwaterloo.ca). located at the center of the DBS’s coverage. In addition, most S. Zhang is with the School of Computer Science and Engineering, Beihang University, Beijing, China, 100191, (email: zhangshan2007@gmail.com). H. Zhou is with the School of Electronic Science and Engineering, Nanjing In this paper, the abbreviation BS means the terrestrial base station and University, Nanjing, China, 210023, (email: haibozhou@nju.edu.cn). DBS is referred to as drone base station. arXiv:1906.00777v2 [cs.NI] 22 Oct 2019 2 existing DBS deployment works focus on optimizing the D2U mize AoI association, D2U communication scheduling, communication, while ignore or idealize the D2B link quality horizontal trajectories and flying heights of DBSs in constraints. different sub-problems, respectively. Besides, a k-means- To promote the fairness for all users and maintain low based scheme is devised to generate the DBS initial deployment cost, some researchers further propose the DBS trajectories for further improvements on performance. trajectory planning approach that allows DBSs fly over and We conduct extensive simulations and results demonstrate serve AoIs periodically according to designed trajectories. that the proposed 3D trajectory planning and scheduling The purpose of DBS trajectory planning is optimizing AoIs algorithm can reduce the average D2U pathloss by 15 association and trajectory for each DBS to maximize user 20 dB, and lower the D2U pathloss standard deviation QoS [16] [17]. However, three issues remain unsolved in by 68%, in comparison with the static DBS deployment current works. First, to reduce the complexity of optimization algorithm based on particle swarm optimization (PSO). problems, most existing works assume that all DBSs fly at a The remainder of this paper is organized as follows. The pre-defined constant height, which shrinks the 3D trajectory literature review is conducted in Section II. In Section III the planning into a 2D horizontal trajectory planning, and fails system model for DBS trajectory planning and scheduling in to realize the performance improvements by adjusting DBS DA-RAN is introduced. Then the multi-DBS 3D trajectory flying heights. Second, the commonly used assumption of Friis planning and scheduling problem is formulated in Section IV. free space propagation model cannot reflect the unique D2G In Section V the MINLP problem in Section IV is decoupled channel features. Third, the D2B link quality constraint is also into sub-problems and the BCD based algorithm is proposed omitted by most DBS trajectory planning works. to solve it. Simulation and numerical results are carried out in To address those issues, in this paper, we investigate the 3D Section VI, and the conclusion is given in Section VII. trajectory planning and scheduling for multiple DBSs in the II. RELATED WORKS DA-RAN. Considering the state-of-the-art D2U [18] and D2B [6] channel models, and constraints of D2B link qualities, the Promoted by the advancements in the flying control and multi-DBS 3D trajectory planning problem is formulated as communication technologies, both industry and academia are a mixed integer non-linear programming (MINLP) problem devoting many efforts to exploit the full potential of DA- which aims at minimizing the average D2U pathloss for RAN [4]. As the foundation for drone communication and all users within one trajectory period. By decoupling the DA-RAN research, Al-Hourani et al. built the D2U pathloss MINLP problem into multiple quasi-convex or integer linear model for DBS according to abundant field test data in various programming (ILP) sub-problems, we can separately optimize scenarios [18]. A close-form expression of D2U pathloss the AoI association, D2U communication scheduling, DBS model suiting different scenarios is proposed in which the horizontal trajectories and flying heights in each sub-problem, probabilities of both LoS and NLoS D2U links are considered. respectively. In essence, we adopt the block coordinate descent As the extension work, they further formulated the pathloss (BCD) mechanism to devise a multi-DBS 3D trajectory plan- model for D2B communication in suburban scenario [6] where ning and scheduling algorithm, in which the sub-problems are the D2B links are dominated by LoS links. Leveraging the iteratively optimized and converge to the optima. The main pathloss model in [18] and [6], various studies have emerged contributions of this work are listed as follows: in both static DBS deployment and DBS trajectory planning. We investigate the 3D trajectory planning of multiple A. Static DBS Deployment DBSs in which both the flying heights and horizontal trajectories of DBS are optimized together instead of In most static DBS deployment works, the terrestrial user optimizing horizontal trajectories on a 2D plane. As far QoS or network performance is improved through optimizing as we know, this is the first work considering the real 3D the hovering position of single or multiple DBSs. For instance, trajectory in which the flying height of any DBS can be through a clustering based approach, Mozaffari et al. designed adjusted at different slots on its trajectory. the optimal locations of DBSs that maximize the information To make the system model more practical, we employ the collection gain from terrestrial IoT devices [19]. In [20], Zhang state-of-the-art D2U and D2B pathloss models rather than et al. optimized the DBS density in DBS network to maximize the traditional pathloss models (e.g., Friis equation) in the the network throughput while satisfying the efficiency require- system model. We formulate the multi-DBS trajectory ments of the cellular network. Zhou et al. studied the downlink planning problem, which turn to be an MINLP, and coverage features of DBS using Nakagami-m fading models, decouple it into multiple sub-problems to resolve the and calculated the optimal height and density of multiple non-convexity. A protect distance constraint between any DBSs to achieve maximal coverage probability [21]. Although two DBSs at every time slots is considered in the prob- various works have investigated the static DBS deployments lem formulation to suppress the physical collision and in different scenarios with different methods, the D2B link mutual interference of DBSs. Instead of modifying the quality constraint is simplified or ignored by most works. 3D trajectories, we ensure the protect distance constraint In the works considering the D2B links, the D2B channel by scheduling the start slot of each trajectory to avoid models are either as same as the D2U pathloss model [22] introducing non-convex constraints in trajectory-related or traditional terrestrial channel models [23]. In this paper, we sub-problems. further implement the specific D2B channel model derived in A BCD based algorithm is proposed to separately opti- [6] to highlight the D2B channel features. v v v DBS D2B Link D2U Link Base Station Users Trajectory DBS D2B Link D2U Link Horizontal Distance Base Station Users Communication Resource 50% 20% 25% Computation Resource 30% 80% D2B Link 30% 20% D2U Link Base Station Users Drone-cell B. DBS Trajectory Planning D2B Link In [24], Li et al. proposed an cooperative relaying scheme Horizontal in which multiple DBSs relay data from terrestrial sensors Trajectory Distance U2D Link to the BS using time division multiple access (TDMA). As User a pioneer work, the trajectories of all DBSs are assumed (IoT device) Base Station to be pre-optimized for simplicity. Mozaffari et al studied (a) DBS photograph [29] both the static and mobile DBS-enabled wireless networks Base Station D2B Link underlaid with a device-to-device communication network DBS DBS θ [25]. Though the trajectory optimization is considered in this D2B Link work, the D2U communications are only permitted at pre- D2U Link defined stop points, which fails to exploit the impact of DBS mobility feature on the network performance. Motivated by Base Station [25], Zeng et al. proposed a general framework for joint AoI Trajectory trajectory and communication optimization in D2U point-to- point communication scenario [26]. For DBS-enabled multi- AoI Horizontal Distance user networks, Lyu et al. proposed a cyclical multiple access (b) System model scheme in [27], where the DBS forms a cyclical trajectory and periodically serves each terrestrial users using TDMA. Fig. 1: Multi-DBS 3D trajectory planning and scheduling. Wu et al. formulated the DBS trajectory planning as a mixed integer non-convex optimization problem in which the user jSj is a circle with radius r , and is divided into a mesh BS bs association, DBSs trajectories planning and DBS transmitting consisting of multiple grids on X-Y plane. The side-length power control schemes are jointly optimized [16]. Considering of each grid is denoted as L . Without loss of generality, aoi the delay constraints, Wu et al. further studied a DBS-enabled the average D2U pathloss for any users in one grid can be OFDMA network where a single DBS is dispatched to serve treated as equal since L is far smaller than r . Assuming aoi BS a group of delay-sensitive users on the ground [17]. The that users are uniformly distributed over jSj , and each grid bs DBS trajectory planning and OFDMA resource allocation are can be chosen as AoI with same probability. Therefore, the jointly optimized through an iterative parameter-assisted BCD user association is equal to AoI association in this work. Both method. As the pioneer works of trajectory planning, [16] users in AoIs and DBSs are considered as identical devices [17] set the foundation models for DBS trajectory planning. with identical transmit power and uplink/downlink bandwidth. To dynamically deploy multiple DBSs while maintaining the Considering the fact that AoIs change their distribution in connectivity among them, Zhao et al. proposed both the a relatively low frequency, the dynamic distribution of AoIs centralized and distributed DBS motion control algorithms for can be treated as a quasi-static scenario between successive scenarios with or without global information of users [28]. trajectory planning. Based on the current snapshot of AoIs However, in those works the flying height of all DBS are distribution, the BS running trajectory planning and scheduling treated as a pre-defined constant, and most of them idealize the algorithm to calculate optimal trajectories for all DBSs, and D2B link quality constraints. In this paper, not only the D2B update them to the DBSs via D2B links. When the BS senses link quality constraint is introduced in problem formulation significant changes of AoIs distribution, re-planning process and optimization, but also the flying heights of each DBS at is triggered to design new trajectories for DBSs, otherwise, every slots are jointly optimized with the horizontal trajectory. the trajectory planning result keeps constant. The set of AoIs to be served and the set of DBSs to be deployed are denoted as U and D, respectively. Their cardinalities, jUj and jDj, III. SYSTEM MODEL represent the number of AoIs and DBSs, respectively. In this section, we introduce the DA-RAN scenario, D2U and D2B channel models, as well as the DBS trajectory model used for further analyses and problem formulation. B. D2U and D2B Channel Models A. Drone Assisted Radio Access Networks Based on the state-of-the-art Drone-to-Ground (D2G) chan- nel research [18] [6], both the D2U and D2B links are modeled Fig. 1 shows the system model and the DBS photograph for in our work, respectively. For D2U links, the LoS probability the multi-DBS 3D trajectory planning and scheduling. The is calculated as [18] DBS is supported by the quad-copter or multi-rotor drones, which is regarded as low altitude platform (LAP) with the low flying height (below 300m) [14], limited communication P ¹r ; hº = (1) LoS DU 1 + a exp¹b¹arctan¹ º aºº coverage (less than 3km) [14] and static hovering capability. DU Based on the DA-RAN architecture, we investigate the sce- nario in which multiple DBSs are controlled by a single BS where r is the horizontal distance between DBS and the DU to support users in AoI through the state-of-the-art wireless AoI, h represents the flying heights of the DBS. a and b are relay techniques [30] [31]. The radio coverage area of the BS environment-based constant values. The average D2U pathloss 4 can be derived based on (1) [18]: simultaneously, they share the same trajectory period length T to simplify the trajectory planning and scheduling. 4 f h + r Several trajectory constraints are considered in our work: DU PL¹r ; hº = 20 log¹ º DU (2) 1) Each DBS needs to return to its initial location by the end of each period T , which implies that the trajectory of each + P ¹r ; hº +¹1 P ¹r ; hºº LoS DU LoS LoS DU NLoS DBS is a closed curve in 3D space. 2) Within any slot n, the where f (Hz) and c (m/s) are carrier frequency and speed of horizontal and vertical shifts of any DBS cannot exceed the light, respectively.  and  are additional losses for LoS N LoS maximal horizontal distance V  , and the maximal height max t LoS and NLoS links obtained through field test data, which difference H  , respectively. V and H are maximum max t max max involves the impacts of shadowing components. a, b,  and LoS allowed horizontal and vertical speeds. 3) For any slot n, the are all environment-based parameters. N LoS 3D distance between any two DBSs cannot be smaller than a D2B links are designed to provide high-reliability data pre-defined protect distance Z , which prevents the physical min transmission between DBSs and their corresponding BS. The collision, disturbance and mutual interference among DBSs. average D2B pathloss is calculated as follow by implementing Since calculating interference from non-associated DBSs to the D2B channel model in [6]: any AoI based on D2U pathloss model is highly complex 0 and makes the trajectory planning problem unsolvable, in this ¹ º B (3) PL¹r ; º = 10 log¹r º + A¹  ºe + DB DB 0 0 work, we assume that the mutual interference (to AoIs) among where r and  denote the horizontal distance and the vertical DBSs can be effectively avoided by ensuring the protect DB angle between the DBS and the BS antenna, respectively. , distance constraint. A,  , B, and  are the terrestrial pathloss exponent, excess 0 0 pathloss scalar, angle offset, angle scalar, and excess pathloss D. AoI Association and D2U Communication Scheduling offset, respectively. All of them are environment-based param- In this work, the DBS-AoI association is denoted by the eters and involving impacts of shadowing components. Except binary variable a . a = 1 when AoI u 2 U is associated to d;u d;u r and , all other parameters in (3) are environment-based DB DBS d 2 D, and otherwise a = 0. The U2D communication d;u constants. Since the D2B channel model in [6] use 850 MHz scheduling is denoted by the binary variable k »n¼ for d;u LTE bands, (3) contains no parameter representing carrier 8d 2 D; u 2 U; n 2 N . If AoI u is severed by DBS d in frequency. slot n, k »n¼ is set as 1; otherwise, k »n¼ = 0. For each d;u d;u Both the D2U [18] and D2B [6] pathloss models are large- DBS with pre-defined trajectory planning and AoI association scale pathloss models. For the small scale fading and multipath results, a D2U communication scheduling scheme is designed effects, currently there is no specific model for the drone-to- to allocate each slot to the corresponding AoI, and guarantee ground communication links. Moreover, since the objective of the fairness among all associated AoIs. Several constraints are our multi-DBS trajectory planning is to minimize the mean considered in the AoI association and scheduling model: 1) D2U pathloss of the system, the small-scale pathloss can be One DBS can serve maximal jA j number of AoIs. 2) In max average out at zero or a constant offset during the analysis. any slot n, one DBS d can serve at most one AoI u 2 A ; in all Therefore, based on the assumptions in D2U and D2B channel slots, one AoI u can only be associated to one DBS. 3) For any models, in this work we do not focus on the small scale fading given T and A , the total N slots are uniformly scheduled to and multipath effects in D2U and D2B links. each u 2 A to ensure fairness. 4) The slot amount scheduled to every AoIs cannot be smaller than a pre-defined threshold C. DBS Trajectory Model S , which indicates the minimal user service time constraint. min 5) To prevent the overloads and delay caused by frequent For an arbitrary DBS d 2 D, we design its trajectory switching between associated AoIs, all slots scheduled to one such that the DBS serves the associated AoI set A  U u within T have to be consecutive. periodically. Within one period T , d flies over all its associated AoI and serves them sequentially according to the scheduling IV. PROBLEM FORMULATION result. Since the continuous time can introduce infinite number of position variables to describe the DBS trajectory, we In this section we formulate the multi-DBS 3D trajectory discrete the period T into N equal-time slots to simplify the planning problem based on the aforementioned system model. formulation. The length of each slot  = can be set as small According to (4), the the 3D distance from the DBS d to as possible to approximate the continuous optimal trajectory. AoI u in time slot n can be expressed as Based on this model, the trajectory of DBS d within each T m »n¼ = h »n¼ + kl »n¼ l k can be modeled as a N -length sequence composed by three- d;u d d u q (5) dimensional vectors: 2 2 = h »n¼ + r »n¼ d d;u W »n¼ = »x »n¼; y »n¼; h »n¼¼; n = 1; :::; N (4) d d d d where l = »x ; y ¼ is the 3D coordinate of AoI u. l »n¼ is u u u d where x »n¼, y »n¼ and h »n¼ denote the 3D coordinates d’s 2D projection on X-Y plane l »n¼ = »x »n¼; y »n¼¼. r »n¼ d d d d d d d;u of DBS d at slot n. DBS d is considered to follow the denotes the horizontal distance between DBS d and AoI u. same trajectory W »n¼ over consecutive periods until the re- Without loss of generality, we set the BS at the original point planning process is triggered. For multiple DBSs working of coordinate system. By substituting m »n¼ for the D2U d;u 5 and D2B distances in (2) and (3), we can calculate the D2U Due to the quadratic and exponential terms in (8) and con- pathloss between DBS d and AoI u in slot n straints, as well as the binary variable a , k »n¼, problem d;u d;u (8) is a MINLP problem [32]. Besides, the optimization ob- 4 f m »n¼ c d;u P »n¼ = 20 log¹ º jective (8) and constraints are non-convex for DBS trajectory d;u W, which is difficult to solve directly. (6) + P ¹r »n¼; h »n¼º LoS d;u d LoS +¹1 P ¹r »n¼; h »n¼ºº LoS d;u d NLoS V. M ULTI-DBS 3D TRAJECTORY PLANNING AND as well as the D2B pathloss between the BS and DBS d in SCHEDULING ALGORITHM slot n Although the objective and constraints in problem (8) are P »n¼ = 10 log¹kl »n¼kº d;B d (7) non-convex or non-linear for the decision variables, the prob- »n¼ 0 d;B ¹ º + A¹ »n¼  ºe + d;B 0 0 lem can still be transformed into solvable forms (e.g. quasi- convex or ILP) by setting parts of the decision variables as where  »n¼ = arctan¹h »n¼kl »n¼kº in degree. d;B d d constants. Then, the MINLP problem can be decoupled into Since all users and DBSs are identical devices with fixed multiple sub-problems which are solvable for parts of the transmission power and transmission bandwidth in each pe- decision variables. Specifically, for the multi-DBS 3D trajec- riod, the achievable D2U data rate between DBS d and AoI tory planning and scheduling problem, we divide the decision u is negative correlated with the D2U pathloss. Therefore, the variable set into four blocks (i.e. A, K, L = fl »n¼; 8d; ng aim of the multi-DBS 3D trajectory planning and scheduling and H = fh »n¼; 8d; ng), and propose multiple sub-problems problem is minimizing the average D2U pathloss of the in which all blocks or their sub-blocks are optimized, respec- network over one period T . tively. However, the problem (8) remains non-convex to DBS Define A = fa ; 8d; ug, K = fk »n¼; 8d; u; ng and d;u d;u trajectory variable W even with given A and K. Therefore, W = fW »n¼; 8d; ng, the trajectory planning and scheduling we further divide W into two independent blocks, i.e. the problem can be formulated as horizontal DBS trajectory L and the DBS flying height H. jUj jDj N ÕÕ Õ min a ¹ k »n¼P »n¼º (8) d;u d;u d;u A;K;W NjUj u=1 d=1 n=1 A. AoI Association Optimization jUj s:t: a  jA j ; 8d; (8a) d;u d max Given the constant K, L and H, which indicate the pre- u=1 jDj defined trajectories of multiple DBSs, the AoI association sub- a = 1; 8u; (8b) d;u d=1 problem can be written as an ILP problem: jUj k »n¼ = 1; 8d; n; (8c) d;u jUj jDj u=1 N ÕÕ Õ jDj min a ¹ k »n¼P »n¼º d;u d;u d;u k »n¼ = 1; 8u; n; (8d) d;u A NjUj (9) d=1 u=1 d=1 n=1 N N s:t: ¹8aº;¹8bº; a 2 f0; 1g 8d; u: k »n¼ = ; 8d; u; (8e) d;u d;u n=1 jA j Since exact K can only be determined with given A , an k »n¼  S ; 8d; u; (8f) d;u min n=1 initial D2U communication scheduling K , in which k »n¼ = 0 d;u Õ N jA j d 1; 8d; u; n, is defined for the first AoI association optimization. k »¹n + oº mod N¼  ; 8d; u; n; (8g) d;u jA j d The branch and bound method supported by various solvers a ; k »n¼ 2 f0; 1g; 8d; u; n; (8h) (e.g. Gurobi [33]) can be used to solve problem (9) efficiently. d;u d;u W »1¼ = W »N + 1¼; 8d; (8i) d d kl »n + 1¼ l »n¼k  V  ; 8d; n; (8j) d d max t B. D2U Communication Scheduling Optimization jh »n + 1¼ h »n¼j  H  ; 8d; n; (8k) d d max t Based on the optimized A, as well as the constant L and kW »n¼ W »n¼k  Z ; 8n; i; j , i; (8l) i j min H, the D2U communication scheduling sub-problem is an ILP P »n¼  P ; 8d; u; n: (8m) d;B DB problem too: jUj jUj jDj In (8), jA j = N a is the number of AoIs associated N d d;u ÕÕ Õ u=1 to DBS d. kW »n¼ W »n¼k represents the 3D distance min a ¹ k »n¼P »n¼º i j d;u d;u d;u NjUj u=1 n=1 between DBS i and j at slot n. a mod b is the modulo d=1 (10) operation between a and b. P is the pathloss threshold s:t: ¹8aº;¹8bº;¹8cº;¹8dº;¹8eº;¹8 fº;¹8gº; DB for D2B communication. (8a)-(8h) are AoI association and k »n¼ 2 f0; 1g 8d; u; n: d;u D2U communication scheduling constraints, in which (8a) is constraint 1); (8b)-(8d) represent the constraint 2); (8e) and It is worth noting that constraint (8e) and (8g) turn to be (8f) corresponds to constraint 3) and 4), respectively; (8g) linear constraint to K given constant A. Same as problem (9), indicates constraint 5). (8i)-(8l) correspond to DBS trajectory problem (10) can be efficiently solved by the branch and bound constraints 1), 2) and 3). (8m) is the D2B pathloss constraint. method. 6 C. DBS Horizontal Trajectory Optimization substituting r »n¼ tan¹ »n¼º for corresponding h »n¼. Fig. d;u d;u d 2 shows the curves of P »n¼ versus  »n¼ under different d;u d;u The sub-problem to optimize L with constant A, K and H r »n¼. We can prove that the (15) is quasi-convex to  »n¼ d;u d;u can be expressed as and has only one global minimum. The detail proof can be jUj jDj N ÕÕ Õ found in Appendix A. To obtain the optimal  »n¼ at which 1 d;u opt min a ¹ k »n¼P »n¼º d;u d;u d;u L NjUj (11) u=1 d=1 n=1 r [n]=50m d,u s:t: ¹8jº;¹8mº; l »1¼ = l »N + 1¼ 8d: d d r [n]=150m d,u r [n]=250m d,u According to (6), (11) is non-convex for L. Instead of jointly r [n]=350m d,u optimizing L, we further divide the block into its element r [n]=450m d,u variable l »n¼ and revise (11) as d r [n]=550m d,u min a »n¼k »n¼P »n¼+ d;u d;u d;u NjUj l »n¼ jUj jDj ÕÕ Õ (12) a ¹ k »n ¯¼P »n ¯¼º 80 d;u d;u d;u NjUj u=1 d=1 n ¯=1;n ¯,n 0 20 40 60 80 s:t: ¹8jº;¹8mº; l »1¼ = l »N + 1¼ 8d: d d θ [n] (degree) d,u Keeping other l »n ¯¼; 8d; u; n ¯ , n fixed, the second part of Fig. 2: P »n¼ versus  »n¼. d;u d;u (12) turns to be constant. With the given H, we can prove P »n¼ reaches the global minimum, we let the first-order d;u that P »n¼ is a quasi-convex and non-decreasing function derivation of P »n¼ to  »n¼ equals zero: d;u d;u d;u to D2U horizontal distance r »n¼; 8d; u; n. Therefore, min- d;u @P »n¼ d;u = tan¹ »n¼º imizing the objective function in (12) equals minimizing d;u @ »n¼ ln¹10º 2 d;u r »n¼ = kl »n¼ l k , which is a quadratic convex opti- u;d d u ab¹  º exp¹b¹ »n¼ aºº LoS NLoS d;u mization problem for l »n¼: d + = 0: ¹1 + a exp¹b¹ »n¼ aººº d;u min kl »n¼ l k (17) d u l »n¼ (13) (17) is a transcendental equation without closed-form solution. s:t: ¹8jº;¹8mº; l »1¼ = l »N + 1¼; 8d: d d However, considering the fact that (15) has only one global minimum which is the single solution for (17), we can further It is worth noting that the feasible region of l »n¼ constrained calculate the second-order derivation of P »n¼ to  »n¼: d;u d;u by (8m) can form a convex set in any X-Y plane by ignoring the working-zone burst close to the BS antenna [34]. @ P »n¼ 20 d;u = sec ¹ »n¼º d;u ln¹10º @ »n¼ d;u 2 2 D. DBS Flying Height Optimization 2a b ¹  º exp¹2b¹ »n¼ aºº LoS NLoS d;u Similar to problem (11), the sub-problem optimizing H is ¹1 + a exp¹b¹ »n¼ aººº d;u also non-convex with given A, K and L. Further decoupling 2 ab ¹  º exp¹b¹ »n¼ aºº LoS NLoS d;u H into h »n¼ 8d; n, the sub-problem to optimize each h »n¼ d u;d ¹1 + a exp¹b¹ »n¼ aººº d;u is (18) Then, the  »n¼ can be calculated through the Newton- d;u opt min a »n¼k »n¼P »n¼+ d;u d;u d;u h »n¼ NjUj Raphson method: jUj jDj ÕÕ Õ P »n¼ ¹ »n¼ º d;u d;u i (14) »n¼ =  »n¼ (19) d;u i+1 d;u i a ¹ k »n ¯¼P »n ¯¼º d;u d;u d;u 00 P »n¼ ¹ »n¼ º d;u d;u i NjUj u=1 d=1 n ¯=1;n ¯,n where the iteration stops when  »n¼  »n¼ d;u i+1 d;u i s:t: ¹8kº;¹8mº; h »1¼ = h »N + 1¼ 8d: d d and  »n¼ =  »n¼ . The calculation of  »n¼ is d;u opt d;u i+1 d;u opt To solve (14), we first transform (6) as the summation constrained by h »n¼  r »n¼ tan¹ »n¼º  h »n¼ where d d d;u d;u d u of one function of r »n¼ and one function of  »n¼ = d;u d;u h »n¼ and h »n¼ are upper and lower bounds of h »n¼ due d d d u d arctan¹h »n¼r »n¼º: d d;u to D2B link quality constraint. After obtaining  »n¼ for d;u opt each  »n¼, the optimal h »n¼ can be calculated as d;u d opt 4 f (15) P »n¼ = 20 log¹ r »n¼º +  + F¹ »n¼º d;u d;u NLoS d;u h »n¼ d up c 8 >h »n¼ ;  »n¼  arctan¹ º d u d;u opt r »n¼ d;u >< where h »n¼ d down h »n¼ = (20) h »n¼ ;  »n¼  arctan¹ º d opt d d d;u opt r »n¼ > d;u F¹ »n¼º = 20 log¹sec¹ »n¼º > d;u d;u r »n¼ tan¹ »n¼ º; otherwise. d;u d;u opt (16) LoS NLoS + : 1 + a exp¹b¹ »n¼ aºº d;u E. Protect Distance Constraint Since r »n¼ is pre-defined with given L, (15) is constant Given the assumption that all trajectories are closed curves d;u and optimizing h »n¼ equals optimizing  »n¼ in (14) by in 3D space, the start slot of each trajectory can be any slots d d;u Pathloss (dB) 7 on the trajectory. Because all trajectories are assumed to have D2U communication scheduling and DBS trajectories after same length of period N , for any trajectory, different start each iteration t, respectively. W is composed by L and H . t t t slots can lead to different inter-DBS distances at all following According to the BCD method, the proposed algorithm ensures slots. Since that, it is efficient to schedule the start slot of convergence since the global optimal results of all sub-problem each DBS to prevent violating protect distance constraint (8l) are accurately achieved [16] [35]. in following slots. We address protect distance constraint in Initial trajectories are required for the first iteration of AoI the start slot scheduling process due to two reasons: First, association. Without loss of generality, we set the same initial the feasible set of constraint (8l) is non-convex for trajectory height h 2 »h »n¼ ; h »n¼ ¼ for all DBS. For each DBS, 0 d d d u related variables, i.e., L and H, optimizing them in horizontal we apply a circle initial trajectory with radius r = 1 m. trajectory or height optimization problems can significantly Given the assumption in subsection A that the initial D2U increase the problem complexity. Besides, by ensuring the communication scheduling k »n¼ equals one for 8d; u; n, it d;u protect distance constraint through start slot scheduling, the is better to deploy the center of each circle trajectory to DBS trajectory planning result can be maintained, which the position where the summation of D2U pathloss between achieves better average D2U pathloss than modifying those its adjacent AoIs (will be associated to the DBS with high optimized trajectories. Since the start slot scheduling is not probability) is minimized. Therefore, the classic k-means an optimization problem, we can accept any start slots set algorithm can be effectively applied to determine the initial as long as it ensures constraint (8l). In this work, we apply trajectory center of each DBS by substituting D2U pathloss a greedy-based searching algorithm, as shown in Algorithm for the geometric distance in original algorithm. To reduce 1, to iteratively schedule the start slots of all DBSs d 8i = the convergence time and improve the result quality, we apply 1; 2; : : :;jDj. In each iteration, d sequentially sets its start the k-means ++ algorithm which prefers centroid seeds with slot as n 8j = 1; 2; : : :; N and calculate the 3D distances large mutual distances [36]. between d and previous scheduled d 8k  i at every slots. i k Algorithm 2 Multi-DBS 3D trajectory planning and schedul- If any start slot n ensures protect distance constraint at every ing algorithm Algorithm 1 Start slots scheduling algorithm 1: Initiate initial U2D communication scheduling K , initial height h . 1: Generate start slots set S = fn = 1; n = 1; : : :; n = 1g 0 1 2 jDj 2: Calculate initial horizontal trajectory L through k-means for DBS d ; d ; : : :; d . 0 1 2 jDj ++ algorithm. 2: for i = 1; 2; : : :;jDj do 3: Set t = 1, W = 1. 3: for j = 1; 2; : : :; N do 4: while W   do 4: Set d ’s start slot as n . i j 5: Solve problem (9) to obtain A by treating K , L 5: Calculate distance between d and d 8k  i at all t t1 t1 i k and H as constants. slots with d starts at n . t1 i j 6: Solve problem (10) to obtain K by treating A , L 6: Break if all distances are larger than Z t t t1 min and H as constants. 7: end for t1 7: for d 2 D; n = 1; 2; : : :; N do 8: if Z is violated for all n 2 N then min j 8: Solve problem (12) to obtain L »n¼ by treating 9: Set i = 1; n = n + 1. d opt 1 1 A , K , H and L »n ¯¼ 8d; n ¯ , n as constants. 10: end if t t t1 d 9: Update L with l »n¼ . 11: end for t d opt 10: end for 11: for d 2 D; n = 1; 2; : : :; N do slots, the start slot of d is temporally scheduled to n and i j 12: Solve problem (14) to obtain h »n¼ by treating break to the d iteration. If all n 8j = 1; 2; : : :; N on d opt i+1 j A , K , L and h »n ¯¼ 8d; n ¯ , n as constants. d ’s trajectory cannot ensure protect distance constraint, the t t t d 13: Update H with h »n¼ . algorithm abandons the current and all previous scheduled t d opt 14: end for DBSs and re-run the first iteration of d with updated start 15: Update W with L and H . slot n = n + 1. Algorithm 1 stops until all d are scheduled t t t 1 1 i 16: t = t + 1. with feasible start slots. 17: W = W W . t t1 18: end while F. Proposed Algorithm 19: Run Algorithm 1 to ensure protect distance constraint. By decoupling the decision variable set into multiple blocks, i.e., A , K , l »n¼ 8d; n, h »n¼ 8d; n, each block’s sub-problem t t d d can be optimized respectively with other blocks keeping VI. NUMERICAL RESULTS constant. Therefore, the problem (8) can be solved through iteratively optimizing those sub-problems until the results We conduct extensive simulations to verify the perfor- converge, which yields to the classic BCD method. Based on mance of our proposed algorithm in minimizing average the BCD method, we propose the algorithm to solve the multi- D2U pathloss of the network. The simulations are link level DBS 3D trajectory planning and scheduling problem, which without simulating specific MAC or upper layers protocols. shows in Algorithm 2. A , K , W denote the AoI association, The BS is located at the origin point (coordinate ¹0; 0; 0º) t t t 8 and the side-length of grid is set to 20 m. Both U2D and D2B pathloss models are configured in suburban scenario. DBS−1 DBS−2 To provide additional spectrum resources for DA-RAN and DBS−3 reduce the interference to terrestrial RAN users, the frequency DBS−4 DBS−5 band of D2U communication f is expected to be different Start point AoI from the licensed cellular band. Like most commercial drone BS products [37] [38] and DBS related works [39] [7] [19] [28], we use the 2:4 GHz unlicensed band as the carrier for D2U 50 communications. D2B communications use the 850 MHz LTE band according to the D2B pathloss model [6]. By allocating different carrier frequencies, the interference between D2U 500 and D2B communication can be prevented. Initial height h is 0 0 −500 −500 set to 80 m within the working-zone of DBS over the whole BS Y−axis (m) X−axis (m) radio coverage area [34]. We treat  as the minimal time unit (a) 3D view to calculate related variables including V , H , etc. There max max is no need to assign specific value for  in the simulation, DBS−1 DBS−2 however, according to the general specifications of commercial DBS−3 drones (50 70 kmh for horizontal speed, 3 5 ms for DBS−4 DBS−5 ascent/descent speed) [40], the approximate value of  is Start point AoI around 10 s. Table. I shows detail simulation parameters. BS TABLE I: Simulation Parameters −200 −400 Parameters Numerical Values −600 BS radio coverage radius r 900 m BS AoI number jUj 20 −800 D2U parameters ¹ ;  ; a; bº (0.1,21,4.88,0.43) LoS NLoS −800 −400 0 400 800 D2B parameters ¹ ; A;  ; B;  º (3.04,-23.29,-3.61,4.14,20.7) 0 0 X−axis (m) Carrier frequencies (D2U, D2B) ¹2:4 GHz; 850 MHzº (b) 2D projection on X-Y plane Slots amount in one period N 60 slot D2B pathloss constraint P 80 dB DB Minimal per-AoI slot number S 10 slot min DBS−1 Maximal per-DBS AoI number jA j 6 DBS−2 max DBS−3 Maximal horizontal speed V 30; 50; 70; 90; 110 mslot max DBS−4 Maximal vertical speed H 10 mslot max DBS−5 Protect Distance Z 200 m min 100 Trajectory difference  0:1 m for each slot A. 3D Trajectory Planning for Multiple DBSs Fig. 3 shows the scenario where the trajectories of five DBSs are optimized to serve twenty AoIs with V = 90 mslot. The max closed curves dotted by different markers in Fig. 3(a) and Fig. 0 10 20 30 40 50 60 3(b) denote different DBS trajectories; the squares on the X- Time Step (slot) Y plane represent AoIs. AoIs are associated to corresponding (c) Heights DBSs with same colors. Fig. 3(c) illustrates the changes of flying height within one period. As shown in Fig. 3(a) and 3(b), for each DBS, the optimized trajectory can fly over all 0.8 its associated AoIs and form a closed curve in 3D space. In Inter−DBS distance Fig. 3(c), all DBS flying height curves are lower bounded constraint 0.6 around 78 m, which is the lower bound of h »n¼ due to the d d D2B pathloss constraint. Note that for each trajectory in Fig. 3(b), the summation of 0.4 dots on the section between two AoIs is less than 50% of the total slots number N . Besides, the height curves in Fig. 3(c) 0.2 show the trend to maintain fixed values for consecutive slots. Combining Figs. 3(b) and 3(c), we can justify that the remain- 0 200 400 600 800 1000 1200 1400 ing dots in Fig. 3(b) are overlapped above the associated AoIs, Inter−DBS Distance (m) and those overlapped dots corresponds to the consecutive slots (d) Protect distance guarantee have fixed heights in Fig. 3(c). In other word, the proposed Fig. 3: Trajectory planning results of 5 DBSs serving 20 AoIs. algorithm prefers hovering DBSs above the associated AoIs, Y−axis (m) CDF DBS Height (m) Height (m) 9 DBS−1 DBS−1 DBS−1 DBS−1 800 110 800 110 DBS−2 DBS−2 DBS−2 DBS−2 DBS−3 DBS−3 DBS−3 DBS−3 600 600 105 105 DBS−4 DBS−4 DBS−4 DBS−4 Start point Start point 400 400 AoI AoI 100 100 BS BS 200 200 95 95 0 0 90 90 −200 −200 −400 −400 85 85 −600 −600 80 80 −800 −800 75 75 −500 0 500 0 10 20 30 40 50 60 −500 0 500 0 10 20 30 40 50 60 X−axis (m) Time Step (slot) X−axis (m) Time Step (slot) (a) V = 30 mslot (b) Heights of V = 30 mslot (c) V = 110 mslot (d) Heights of V = 110 mslot max max max max Fig. 4: Trajectory planning results impacted by horizontal speeds. 800 DBS−1 110 DBS−1 DBS−1 110 DBS−1 DBS−2 DBS−2 DBS−2 DBS−2 DBS−3 DBS−3 DBS−3 DBS−3 105 105 DBS−4 DBS−4 600 DBS−4 DBS−4 Start point DBS−5 DBS−5 AoI DBS−6 DBS−6 100 100 BS DBS−7 DBS−7 Start point 95 AoI 95 BS 90 90 −200 −200 −400 85 85 −400 −600 80 80 −600 −800 75 −800 75 −500 0 500 0 10 20 30 40 50 60 −500 0 500 0 10 20 30 40 50 60 X−axis (m) Time Step (slot) X−axis (m) Time Step (slot) (a) jDj = 4 (b) Heights of jDj = 4 (c) jDj = 7 (d) Heights of jDj = 7 Fig. 5: Trajectory planning results impacted by DBS number. while leave minimal slots for the travelling process between within one period. In Fig. 4(c) where V is high enough, max adjacent hovering positions. Such a “hovering effect” can be the DBSs can even hovering on each associated AoI for few explained as follows. For any slot n, the proposed algorithm slots since the flying interval between two hovering positions is prone to small r »n¼ which minimizes the D2U pathloss requires less slots. Comparing Fig. 4(b) and 4(d), we can see d;u with given h »n¼. On the contrary, the smaller the r »n¼ is, the that the variation of flying height with V = 30 mslot d d;u max higher the probability that r »n¼ »n¼  h »n¼ . Based on is larger than the height variation with V = 110 mslot. d;u d;u opt d d max (20), if r »n¼ »n¼  h »n¼ , the optimal height equals Because in low V scenario, the travelling process between d;u d;u opt d d max the lower bound of flying height h »n¼ at current position. two AoIs requires more slots than that in the high V d d max Since the minimal r »n¼ equals zero, the minimal average scenario, the optimal height r »n¼ tan¹ »n¼ º in small d;u d;u d;u opt D2U pathloss can be achieved by the trajectory with most V has higher probability to fall into the feasible flying max slots hovering above the AoIs. From Fig. 3(c), we can see height range. Considering the four DBSs trajectory planning that several height bursts occur when each DBS is flying scenario, the CDF of D2U pathloss under different V are max between two AoI with a long inter-AoI distance. At those compared in Fig. 6. Given any pathloss threshold, We can see slots, the DBS is relatively far from the scheduled AoI and that the probability of D2U pathloss less than the threshold r »n¼ tan¹ »n¼ º can fall in the feasible height range raises as the V increases. d;u d;u opt max between h »n¼ and h »n¼ constrained by D2B pathloss d d d u Fig. 5 compares the trajectory planning results when jDj = threshold. Therefore, the optimal heights prefer to approach 4 and jDj = 7. The horizontal speed is set as V = 70 mslot max the value of r »n¼ tan¹ »n¼ º in those slots, which leads d;u d;u opt for both scenarios. As the number of available DBS increases, to the height bursts. Fig. 3(d) shows the cumulative distribution the average number of AoI associated to one DBS is reduced, function (CDF) of inter-DBS distance within one period T . The some trajectories can even degenerate to one static deployment red dotted line is the protect distance constraint. It can be seen position when the corresponding DBS is associated with only that all inter-DBS distances of the final trajectory planning one AoI. On the other hand, since the average r »n¼ length d;u result are larger than the protect distance threshold Z , min is also reduced with the decreasing of associated AoI number which indicates the effectiveness of the start slots scheduling for each DBS, the variation of flying height can be reduced algorithm to ensure protect distance constraint. with the increasing of jDj. Fig. 7 shows the CDF of D2U pathloss under different jDj. Similar to Fig. 6, the probability Fig. 4 presents two groups of trajectory planning results of D2U pathloss less than any given threshold increases as with V = 30 mslot and V = 110 mslot, respectively. max max more numbers of DBS are provided. The available DBS number jDj equals four for both groups. As shown in Fig. 4, the AoI associations are same under Fig. 6 and Fig. 7 indicate that the D2U pathloss performance different V . The trajectories in Fig. 4(a) cannot fly over can be influenced by both V and jDj. In Fig. 8, we further max max every associated AoI since the maximal horizontal speed is too investigate the average pathloss performance with different small to ensure the DBSs to approach every associated AoIs V and jDj. From preceding analyses, we know that both the max Y−axis (m) Y−axis (m) DBS Height (m) DBS Height (m) Y−axis (m) Y−axis (m) DBS Height (m) DBS Height (m) 10 Comparing the performance gaps between ITs, we note that 0.9 applying k-means ++ algorithm has more significant impact 0.8 to both average D2U pathloss and pathloss standard deviation 0.7 than using circle-shaped IT. 0.6 0.5 83 4 DBSs 5 DBSs 0.4 6 DBSs 7 DBSs 0.3 110m/slot 90m/slot 0.2 70m/slot 80 50m/slot 0.1 30m/slot 78 79 80 81 82 83 84 85 86 87 78 Pathloss (dB) Fig. 6: CDF of D2U pathloss under different V . max 0.9 30 50 70 90 110 0.8 Maximal Horizontal Speed (m/slot) 0.7 Fig. 8: Average D2U pathloss with different horizontal speeds 0.6 and DBS numbers. 0.5 0.4 non−k−means, point IT 0.3 non−k−means, circle IT 7 DBSs k−means, point IT 0.2 k−means, circle IT 6 DBSs 5 DBSs 0.1 4 DBSs 78 79 80 81 82 83 84 85 Pathloss (dB) Fig. 7: CDF of D2U pathloss under different jUj. higher V and larger jDj can lead to smaller average r , max d;u 76 which eventually reduces the average pathloss level. According to Fig. 8, given the same number of DBS, the average 4 5 6 7 pathloss level decreases slightly as the V increases; while max DBS Number significant average pathloss level reduction occurs as the jDj Fig. 9: Initial trajectory comparison. increases under fixed maximal horizontal speed. Therefore, we can conclude that both raising the horizontal speed and B. Performance Comparison increasing the number of available DBS can promote the av- erage D2U pathloss performance of DBS trajectory planning, To highlights the efficiency of the proposed multi-DBS while increasing the number of available DBSs is proved to 3D trajectory planning and scheduling, we compare the av- be more efficient than raising horizontal flying speed. Note erage D2U pathloss performance achieved by our proposed that this conclusion is valid for the average D2U pathloss trajectory planning algorithm, as well as the static DBS performance of the whole network only. Since the standard deployment scheme in Fig. 10 and Table II. For static DBS deviations of pathloss (error-bars) plotted in Fig. 8 are highly deployment algorithm, we use the per-drone iterated particle overlapped with each other, the D2U pathloss performance swarm optimization (DI-PSO) algorithm proposed in [34]. of specific DBS-to-AoI pair can vary a lot. Nevertheless, as Without loss of generality, we use all data achieved by the horizontal speed and available DBS number increase, the V = 30; 50; 70; 90; 110 mslot to calculate the average D2U max standard deviation is reduced, which indicates that the user pathloss of the proposed trajectory planning algorithm. From fairness can also be promoted by raising V and jDj. Fig. 10, we can see that the average D2U pathloss of both max We further analyze the impacts of different initial trajecto- algorithms are reduced as the available DC number increases. ries (ITs) to the achieved average D2U pathloss performance. However, the D2U pathloss performance achieved by our We compare four types of ITs, i.e., 1) circle IT with the trajectory planning algorithm maintains 10 15 dB smaller center location determined by k-means ++; 2) point IT (where than that achieved by the DI-PSO algorithm. the trajectory shrinks to one hovering point) with the point The user fairness promotion provided by the proposed location determined by k-means ++; 3) circle IT with the trajectory planning algorithm is indicated by the error-bars in center location uniformly distributed over jSj ; 4) point IT Fig. 10 and the D2U pathloss standard deviation comparison bs with the point location uniformly distributed over jSj . Fig. in Table II.  and  are D2U pathloss standard deviations t s bs 9 shows the comparison result. We can see that the k-means- for DBS trajectory planning and static DBS deployment, based circle IT used in the proposed algorithm achieves min- respectively. In Fig. 10, we can see that the standard deviation imal average D2U pathloss and pathloss standard deviation. of D2U pathloss achieved by both algorithms are reduced as Probability Probability Average D2U Pathloss (dB) Average D2U Pathloss (dB) 11 the MINLP problem into multiple solvable sub-problems, DBS Trajectory Planning DBS Static Deployment and devised a BCD-based multi-DBS 3D trajectory planning and scheduling algorithm in which the AoI association, U2D communication scheduling, horizontal trajectories, and fly- 85 ing altitudes of DBSs are iteratively optimized. A start slot scheduling algorithm and a k-means-based circle IT have been proposed to ensure the protect distance constraint and generate initial DBS trajectories. We have investigated the impacts of available DBS number, horizontal speed and different IT on the achieved average D2U pathloss. Simulation results have shown that the proposed algorithm can achieve 10 15 dB 4 5 6 7 average D2U pathloss reduction, and promote pathloss stan- DBS number dard deviation by 68% when compared with the static DBS Fig. 10: Average D2U pathloss comparison between trajectory deployment algorithm. In future works, we will investigate planning and static deployment of multiple DBSs. the communication and resource allocation of multiple DBS in DA-RAN based on the optimized trajectories. the available DBS number increases. While the  maintains less than half of the  , there is no overlap between the APPENDIX A error-bars achieved by two algorithms. From Table II, we can calculate that the DBS trajectory planning can lower the D2U Since the first two parts of (15) are constant or the function pathloss standard deviation by 68:34% on average compared of r »n¼, analyzing the convexity of (15) is equal to analyzing d;u with the static DBS deployment. the convexity of (16). (16) can be regarded as the summation To highlight the cost-efficiency of the trajectory planning of two functions: algorithm, and provide a guideline to determine the number of F¹ »n¼º = F ¹ »n¼º + F ¹ »n¼º d;u 1 d;u 2 d;u required DBS, we compare the minimal required DBS number = 20 log¹sec¹ »n¼º + F ¹ »n¼º d;u 2 d;u (21) under different D2U pathloss thresholds in Table III. The D2U LoS NLoS pathloss threshold is a strict constraint, which means that for = 20 log¹sec¹ »n¼º + : d;u 1 + a exp¹b¹ »n¼ aºº d;u any DBS at any slot, the D2U pathloss to any AoI cannot The first-order derivations of F ¹ »n¼º and F ¹ »n¼º are exceed it. As shown in Table III, under the same D2U pathloss 1 d;u 2 d;u threshold, the minimal required DBS amount is decreased F ¹ »n¼º = tan¹ »n¼º; (22a) d;u d;u as the maximal horizontal speed of DBS increases. Besides, 1 ln¹10º given any threshold levels, the static DBS deployment always ab¹  º exp¹b¹ »n¼ aºº LoS NLoS d;u F ¹ »n¼º = : (22b) requires two to four more DBSs than the DBS trajectory d;u ¹1 + a exp¹b¹ »n¼ aººº d;u planning algorithm, which implies that the DBS trajectory We further calculate the second-order derivations of planning algorithm is more economical than the static DBS F ¹ »n¼º and F ¹ »n¼º as deployment. 1 d;u 2 d;u 00 2 TABLE II: D2U pathloss standard deviation comparison F ¹ »n¼º = sec ¹ »n¼º; (23a) d;u d;u ln¹10º DBS number 4 5 6 7 ab ¹  º exp¹b¹ »n¼ aºº NLoS LoS d;u 2:1203 2:0476 1:3923 0:9887 F ¹ »n¼º = t d;u ¹1 + a exp¹b¹ »n¼ aººº d;u 6:8313 6:7562 4:2329 3:0530 2 2 ¹  º 68:96% 69:69% 67:11% 67:61% s t s 2a b ¹  º exp¹2b¹ »n¼ aºº NLoS LoS d;u : (23b) ¹1 + a exp¹b¹ »n¼ aººº d;u TABLE III: Minimal DBS amounts comparison Note that (23a) is always larger than zero for all  »n¼ 2 d;u D2U pathloss threshold (dB) 98 95 92 89 86 »0 ; 90 ¼, so (22a) is proved to be non-decreasing function. 30mslot 3 4 5 6 8 Let (23b) equals zero, we can calculate the only root of (23b) 30mslot 3 4 5 6 8 »n¼ = a + ln¹aºb at which (22b) achieves its global d;u root 70mslot 3 4 4 6 7 90mslot 3 4 4 5 7 minimum. 110mslot 3 3 4 4 6 Given the suburban scenario parameters ¹ ;  ; a; bº = LoS NLoS Static deployment 6 7 8 10 10 ¹0:1; 21; 4:88; 0:43º, we can calculate that: 0  0 F ¹90 º + F ¹90 º  0; (24a) 1 2 VII. C ONCLUSION 0 0 F ¹ »n¼ º + F ¹ »n¼ º  0; (24b) d;u root d;u root 1 2 In this paper, we have studied the 3D trajectory planning 0  0 F ¹0 º + F ¹0 º  0: (24c) 1 2 and scheduling for multiple DBSs in DA-RAN with the state- 0 0 of-the-art D2U and D2B pathloss models considered. We which indicates F ¹ »n¼º + F ¹ »n¼º, i.e., (17), has only d;u d;u 1 2 have formulated the MINLP problem to minimize the average one root between  »n¼ and 90 . Therefore, we can d;u root D2U pathloss achieved by multi-DBS trajectory planning and conclude that (16) is a uni-modal function with only one global scheduling. To solve the MINLP problem, we have decoupled minimum for all  »n¼ 2 »0 ; 90 ¼. d;u Average D2U Pathloss (dB) 12 Define the  »n¼ achieves the global minimum of (16) as [17] Q. Wu and R. Zhang, “Common throughput maximization in UAV- d;u enabled OFDMA systems with delay consideration,” IEEE Trans. Com- »n¼ , a 2 »0 ; 90 ¼, b 2 »0 ; 90 ¼ and t = a+¹1ºb 8 2 d;u opt mun., vol. 66, no. 12, pp. 6614–6627, 2018. »0; 1¼. If a  b   »n¼ , (16) is non-increasing function d;u opt [18] A. Al-Hourani, S. Kandeepan, and S. Lardner, “Optimal lap altitude for to t and F¹bº  F¹tº  F¹aº. If  »n¼  a  b, (16) maximum coverage,” IEEE Wireless Commun. Lett., vol. 3, no. 6, pp. d;u opt 569–572, 2014. is non-decreasing function to t and F¹aº  F¹tº  F¹bº. If [19] M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Mobile unmanned a   »n¼  b, (16) ensures that F¹tº  maxfF¹aº; F¹bºg. d;u opt aerial vehicles (UAVs) for energy-efficient internet of things communica- Since that, we can argue that for any a 2 »0 ; 90 ¼ and b 2 tions,” IEEE Trans. Wireless Commun., vol. 16, no. 11, pp. 7574–7589, »0 ; 90 ¼: [20] C. Zhang and W. Zhang, “Spectrum sharing for drone networks,” IEEE J. Sel. Areas Commun., vol. 35, no. 1, pp. 136–144, 2017. F¹a +¹1 ºbº  maxfF¹aº; F¹bºg 8 2 »0; 1¼ (25) [21] L. Zhou, Z. Yang, S. Zhou, and W. Zhang, “Coverage probability analysis of UAV cellular networks in urban environments,” in Proc. which corresponds to the definition of quasi-convex function. IEEE ICC Workshops, Kansas City, MO, May. 2018, pp. 1–6. [22] S. A. W. Shah, T. Khattab, M. Z. Shakir, and M. O. Hasna, “A distributed Therefore, (15) is a quasi-convex function with only one global approach for networked flying platform association with small cells in minimum. 5g+ networks,” in Proc. IEEE GLOBECOM, Singapore, Singapore, Dec. 2017, pp. 1–7. [23] A. Fouda, A. S. Ibrahim, I. Guvenc, and M. Ghosh, “UAV-based REFERENCES in-band integrated access and backhaul for 5G communications,” 2018. [Online]. Available: https://arxiv.org/abs/1807.07230. [1] I. Bor-Yaliniz and H. Yanikomeroglu, “The new frontier in RAN [24] K. Li, W. Ni, X. Wang, R. P. Liu, S. S. Kanhere, and S. Jha, “Energy- heterogeneity: Multi-tier drone-cells,” IEEE Commun. Mag., vol. 54, efficient cooperative relaying for unmanned aerial vehicles,” IEEE Trans. no. 11, pp. 48–55, 2016. Mobile Comput., vol. 15, no. 6, pp. 1377–1386, 2016. [2] S. Zhang, W. Quan, J. Li, W. Shi, P. Yang, and X. Shen, “Air-ground [25] M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Unmanned aerial integrated vehicular network slicing with content pushing and caching,” vehicle with underlaid device-to-device communications: Performance IEEE J. Sel. Areas Commun., vol. 36, no. 9, pp. 2114–2127, 2018. and tradeoffs,” IEEE Trans. Wireless Commun., vol. 15, no. 6, pp. 3949– [3] Q. Ye, J. Li, K. Qu, W. Zhuang, X. Shen, and X. Li, “End-to-end quality 3963, 2016. of service in 5g networks: Examining the effectiveness of a network [26] Y. Zeng and R. Zhang, “Energy-efficient UAV communication with slicing framework,” IEEE Veh. Technol. Mag., vol. 13, no. 2, pp. 65–74, trajectory optimization,” IEEE Trans. Wireless Commun., vol. 16, no. 6, pp. 3747–3760, 2017. [4] M. Mozaffari, W. Saad, M. Bennis, Y. Nam, and M. Debbah, “A tutorial [27] J. Lyu, Y. Zeng, and R. Zhang, “Cyclical multiple access in UAV-aided on UAVs for wireless networks: Applications, challenges, and open communications: A throughput-delay tradeoff,” IEEE Wireless Commun. problems,” IEEE Commun. Surveys Tuts., early access, 2019. Lett., vol. 5, no. 6, pp. 600–603, 2016. [5] Z. M. Fadlullah, D. Takaishi, H. Nishiyama, N. Kato, and R. Miura, “A [28] H. Zhao, H. Wang, W. Wu, and J. Wei, “Deployment algorithms for dynamic trajectory control algorithm for improving the communication uav airborne networks toward on-demand coverage,” IEEE J. Sel. Areas throughput and delay in UAV-aided networks,” IEEE Netw., vol. 30, Commun., vol. 36, no. 9, pp. 2015–2031, 2018. no. 1, pp. 100–105, 2016. [29] N. Summers, “EE looks to drones and big balloons to tackle 4G [6] A. Al-Hourani and K. Gomez, “Modeling cellular-to-UAV path-loss for ’notspots’,” 2017. [Online]. Available: https://www.engadget.com/2017/ suburban environments,” IEEE Wireless Commun. Lett., vol. 7, no. 1, 02/21/ee-drone- balloon-truck- 4g-coverage. pp. 82–85, 2018. [30] Q. Li, S. Feng, X. Ge, G. Mao, and L. Hanzo, “On the performance [7] A. Dhekne, M. Gowda, and R. R. Choudhury, “Cell tower extension of full-duplex multi-relay channels with df relays,” IEEE Trans. Veh. through drones: Poster,” in Proc. ACM MobiCom, New York, NY, Oct. Technol., vol. 66, no. 10, pp. 9550–9554, 2017. 2016, pp. 456–457. [31] Q. Li, M. Yu, A. Pandharipande, X. Ge, J. Zhang, and J. Zhang, [8] F. Lyu, H. Zhu, H. Zhou, L. Qian, W. Xu, M. Li, and X. Shen, “Momac: “Performance of virtual full-duplex relaying on cooperative multi-path Mobility-aware and collision-avoidance mac for safety applications in relay channels,” IEEE Trans. Wireless Commun., vol. 15, no. 5, pp. vanets,” IEEE Trans. Veh. Technol., vol. 67, no. 11, pp. 10 590–10 602, 3628–3642, 2016. [32] R. I. Bor-Yaliniz, A. El-Keyi, and H. Yanikomeroglu, “Efficient 3D [9] Z. Xue, J. Wang, G. Ding, Q. Wu, Y. Lin, and T. A. Tsiftsis, “Device-to- placement of an aerial base station in next generation cellular networks,” device communications underlying UAV-supported social networking,” in Proc. IEEE ICC, Kuala Lumpur, Malaysia, May. 2016, pp. 1–5. IEEE Access, vol. 6, pp. 34 488–34 502, 2018. [33] “Gurobi optimizer 8.1.” [Online]. Available: http://www.gurobi.com. [10] N. Cheng, F. Lyu, W. Quan, C. Zhou, H. He, W. Shi, and X. Shen, [34] W. Shi, J. Li, W. Xu, H. Zhou, N. Zhang, S. Zhang, and X. Shen, “Space/aerial-assisted computing offloading for IoT applications: A “Multiple drone-cell deployment analyses and optimization in drone learning-based approach,” IEEE J. Sel. Areas Commun., vol. 37, no. 5, assisted radio access networks,” IEEE Access, vol. 6, pp. 12 518–12 529, pp. 1117–1129, 2019. [11] D. Takaishi, Y. Kawamoto, H. Nishiyama, N. Kato, F. Ono, and [35] D. P. Bertsekas, Nonlinear programming. Belmont, MA, USA: Athena R. Miura, “Virtual cell based resource allocation for efficient frequency scientific, 1999. utilization in unmanned aircraft systems,” IEEE Trans. Veh. Technol., [36] D. Arthur and S. Vassilvitskii, “k-means++: The advantages of careful vol. 67, no. 4, pp. 3495–3504, 2018. seeding,” in Proc. ACM-SIAM, Philadelphia, PA, Jan. 2007, pp. 1027– [12] S. Jeong, O. Simeone, and J. Kang, “Mobile edge computing via a uav- mounted cloudlet: Optimization of bit allocation and path planning,” [37] DJI, “Mavic pro platinumspecs,” 2018. [Online]. Available: https: IEEE Trans. Veh. Technol., vol. 67, no. 3, pp. 2049–2063, 2018. //www.dji.com/mavic-pro- platinum/info#specs. [13] M. Chen, M. Mozaffari, W. Saad, C. Yin, M. Debbah, and C. S. Hong, [38] N. Cheng, W. Xu, W. Shi, Y. Zhou, N. Lu, H. Zhou, and X. Shen, “Air- “Caching in the sky: Proactive deployment of cache-enabled unmanned ground integrated mobile edge networks: Architecture, challenges, and aerial vehicles for optimized quality-of-experience,” IEEE J. Sel. Areas opportunities,” IEEE Commun. Mag., vol. 56, no. 8, pp. 26–32, 2018. Commun., vol. 35, no. 5, pp. 1046–1061, 2017. [39] I. Bor-Yaliniz, A. El-Keyi, and H. Yanikomeroglu, “Spatial configuration [14] N. H. Motlagh, T. Taleb, and O. Arouk, “Low-altitude unmanned aerial of agile wireless networks with drone-bss and user-in-the-loop,” IEEE vehicles-based internet of things services: Comprehensive survey and Trans. Wireless Commun., vol. 18, no. 2, pp. 753–768, 2019. future perspectives,” IEEE Internet Things J., vol. 3, no. 6, pp. 899– [40] C. Tseng, C. Chau, K. M. Elbassioni, and M. Khonji, “Autonomous 922, 2016. recharging and flight mission planning for battery operated autonomous [15] J. Liu, Y. Shi, Z. M. Fadlullah, and N. Kato, “Space-air-ground integrated drones,” 2017. [Online]. Available: http://arxiv.org/abs/1703.10049. network: A survey,” IEEE Commun. Surveys Tuts., vol. 20, no. 4, pp. 2714–2741, 2018. [16] Q. Wu, Y. Zeng, and R. Zhang, “Joint trajectory and communication design for multi-UAV enabled wireless networks,” IEEE Trans. Wireless Commun., vol. 17, no. 3, pp. 2109–2121, 2018.

Journal

Electrical Engineering and Systems SciencearXiv (Cornell University)

Published: May 30, 2019

There are no references for this article.