Energy-saving deployment algorithms of UAV swarm for sustainable wireless coverage
Xiao Zhang Lingjie Duan






 
 


































Energy-saving deployment algorithms of UAV swarm for sustainable wireless coverage
     Xiao Zhang, Member, IEEE, and
         Lingjie Duan, Senior Member, IEEE
         




X. Zhang is with College of Computer Science, South-Central University for Nationalities. L. Duan are with Engineering Systems and Design Pillar, Singapore University of Technology and Design, Singapore. E-mail: xiao.zhang@my.cityu.edu.hk, lingjie_duan@sutd.edu.sg. Part of the work by X. Zhang was done when he was a postdoc research fellow at Singapore University of Technology and Design.

 
    December 30, 2023
======================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================









Recent years have witnessed increasingly more uses of Unmanned Aerial Vehicle (UAV) swarms for rapidly providing wireless coverage to ground users. Each UAV is constrained in its energy storage and wireless coverage, and it consumes most energy when flying to the top of the target area, leaving limited leftover energy for hovering at its deployed position and keeping wireless coverage. The literature largely overlooks this sustainability issue of deploying UAV swarm deployment, and we aim to maximize the minimum leftover energy storage among all the UAVs after their deployment. Our new energy-saving deployment problem captures that each UAV's wireless coverage is adjustable by its service altitude, and also takes the no-fly-zone (NFZ) constraint into account. Despite of this, we propose an optimal energy-saving deployment algorithm by jointly balancing heterogeneous UAVs' flying distances on the ground and final service altitudes in the sky. We show that a UAV with larger initial energy storage in the UAV swarm should be deployed further away from the UAV station. Moreover, when n homogeneous UAVs are dispatched from different initial locations, we first prove that any two UAVs of the same initial energy storage will not fly across each other, and then design an approximation algorithm of complexity n log1/ϵ to arbitrarily approach the optimum with error ϵ. Finally, we consider that UAVs may have different initial energy storages, and we prove this problem is NP-hard. Despite of this, we successfully propose a heuristic algorithm to solve it by balancing the efficiency and computation complexity well.




UAV Smarm, Energy-efficient Deployment, Sustainable Wireless Coverage, No-Fly-Zone, Approximation Algorithm.




















§ INTRODUCTION


Recently, there are increasingly more exercises and commercial uses of Unmanned Aerial Vehicle (UAV) swarms for rapidly providing wireless coverage to ground users (e.g., <cit.> <cit.> <cit.> <cit.>). In these applications, UAVs serve as flying base stations to serve a geographical area (e.g., cell edge or disaster zone) out of the capacity or reach of territorial base stations. The continuing development of UAV applications for keeping wireless coverage faces two key challenges. First, since each UAV's wireless coverage radius (though adjustable by its deployed altitude) is small, it consumes most energy when flying over a long distance to reach the target area to serve ground users closely. This leaves limited leftover energy for the UAV network's lifetime of keeping wireless coverage afterwards, results in a severe sustainability issue. The endurance of each UAV's on-board energy storage is fundamentally limited by its weight and aircraft size. Multiple UAVs in the swarm need to cooperate to balance their energy consumption during deployment to fully cover users in the distant target area.

Second, many countries have set up sizable No-Fly-Zones (NFZs) which prohibit any deployment of UAVs inside <cit.>. Usually, NFZs include restricted areas, prohibited areas, and military bases. Take Singapore as a typical urban city example, Figure <ref> shows that NFZs in orange widely cover airports, air bases and military context [https://garuda.io/what-you-must-know-about-drone-no-fly-zones-nfz/]. UAVs can only fly at very low altitude to cross these NFZs before reaching their final deployment positions outside NFZs. The optimal UAV swarm deployment should consider these NFZ constraints. To the best of our knowledge, none of the existing work study the energy-saving UAV swarm deployment algorithms by considering the UAV-to-UAV cooperation and NFZ constraint. Further, since each UAV's wireless coverage is adjustable by its hovering altitude, we should jointly optimize its flying distance on the ground and final service altitude in the sky, which was also overlooked in the literature.










The literature of UAV-enabled wireless communications assumes UAVs are already in or around the target area to serve ground users, and overlooks the energy-saving issue during the deployment phase of UAVs to reach the target (e.g., <cit.>). Recent work on UAV-enabled communications have studied multiple issues such as air-to-ground transmission modeling <cit.> <cit.>, interference management <cit.> <cit.>, and UAV trajectory planning <cit.>. For example, <cit.> and <cit.> investigate the optimal service altitude for a single UAV, where a higher service altitude of the UAV increases the line-of-sight opportunity for air-to-ground transmission but incurs a larger path loss. <cit.> studies the mutual interference of a UAV downlink links and analyzes the link coverage probability between the UAV and ground users. <cit.> uses a UAV-enabled base station to serve multiple users on the ground and jointly optimize the transmit power and the UAV trajectory to maximize the average throughput per ground user. <cit.> and <cit.> study the energy-efficient UAV movement and UAV-user link scheduling when serving users, and  <cit.> studies how a UAV should dynamically adapt its location to user movements. Due to a UAV's small wireless service coverage, it consumes most energy when flying over a long distance to the top of the target area, leaving limited leftover energy for the UAV network's hovering and wireless coverage in service phase. It is important to optimize the UAV network deployment before the actual service phase, yet this sustainable deployment issue is largely overlooked in the literature. There are very few works studying the network deployment phase (<cit.> <cit.>). Further, <cit.> studies the UAV-user interaction for learning users' truthful locations from strategic users before UAV deployment. <cit.> studies the economics issues (e.g., pricing and energy allocation) for deploying UAV-provided services.



In this paper, we study energy-saving deployment of a UAV swarm to prolong the UAV swarm's residual lifetime for keeping wireless coverage after deployment. We present Table <ref> to summarize our proposed algorithms for various deployment scenarios happening in practice. Our key novelty and main contributions are summarized as follows.


  * Energy-saving deployment of UAV swarm under UAVs' cooperation and NFZ constraint (Section <ref>): To our best knowledge, this is the first paper to study the energy-saving issue for deploying a UAV swarm to fully cover a target area, and we aim to provide long enough UAV-provided wireless coverage by seeking UAVs' mutual cooperation. We jointly optimize multi-UAVs' flying distances on the ground and service altitudes in the sky for energy saving purpose, by practically considering the correlation between each UAV's service altitude and its coverage radius as well as the NFZ distribution Our objective is to maximize the UAV swarm's lifetime which is defined as the minimum leftover energy storage among all the UAVs after their deployment.


  * Optimal deployment by balancing multi-UAVs' energy consumptions in their flights (Section <ref>): When UAVs are initially located in the same location (e.g., the closest UAV station), we first propose an optimal deployment algorithm of constant complexity O(1) without considering NFZ, and show that a UAV with larger initial energy storage should be deployed further away on the ground for balancing multi-UAVs' energy consumptions in the flights. Further, we show the NFZ constraint will make our problem complex and we manage to present an optimal algorithm of complexity O(n log n). We show some UAVs will be moved out of the NFZ to the edges, reducing the lifetime of the UAV swarm.


  * Near-optimal UAV deployment from different initial locations: In Section <ref>, when dispatching UAVs from different initial locations, we first prove that any two UAVs of the same energy storage should not fly across each other during the deployment. This greatly helps us simplify the UAV swarm deployment problem by keeping the UAVs' final position order along the ground. Then we successfully design an (1-ϵ)-approximation algorithm of time complexity O(n log1/ϵ). Further, when UAVs are of different initial locations, we prove the problem is NP-hard and propose a heuristic algorithm to balance the performance efficiency and computational complexity well. Finally, in Section V, we extend the swarm deployment to a 3D space where the target area to cover is no longer in 1D ground line but in the 2D ground plane.







§ SYSTEM MODEL AND PROBLEM FORMULATION


This section introduces our system model and problem formulation for deploying multi-UAVs to provide full wireless coverage to a target service area on the ground. The target area includes potential users in an activity to be served (e.g., crowd celebrating new year in the fifth avenue in Manhattan) and we first model the target area as a line interval L = [0, L] in 1D, as shown in Figure <ref>. Here, a number n of UAVs in a set U = {μ_1, ⋯, μ_n} are initially rested in 1D ground locations {x_1, ⋯, x_n} with initial energy storages {B_1, ⋯, B_n} before their deployment. Later in Section <ref>, we will extend to model the target area in 2D (see Figure <ref>) and generalize our design of UAV deployment algorithms to a 3D space by considering altitude. Here, denote any UAV μ_i's final position after deployment as (x_i^', h_i) at ground distance x_i^' and hovering altitude h_i. After deployment, UAV μ_i at position (x_i^', h_i) covers [x_i^'-r(h_i), x_i^'+r(h_i)] in [0, L]. We require a full coverage over the target interval [0, L] by deploying n cooperative UAVs, i.e., [0, L] ⊆⋃_i=1^n [x_i^' - r(h_i), x_i^' + r(h_i)]. According to the air-to-ground transmission model in <cit.> and <cit.>, the wireless coverage radius of UAV r(h_i) on the ground concavely increases with the service altitude h_i due to LoS benefit and then decreases due to path loss from the turning point h^*. For energy saving, a UAV's flying to an altitude higher than h^* is not necessary for deployment since it will not enlarge the coverage range but consume more energy for flying longer. Therefore, at the optimum the altitude h_i of each UAV μ_i after deployment to be not higher than h^*.













Due to the NFZ policy, a UAV cannot be finally deployed within NFZ. Suppose there are in total K NFZs in this area, and we model NFZ k as a sub-interval δ_k = [δ_k^l,  δ_k^r] in [0, L]. For UAV μ_i, x_i^'∉∪_k=1^K δ_k. Despite of this, it is still allowed for UAVs to just bypass NFZs on the way at low altitude according to <cit.>. To bypass NFZs, Figure <ref> shows that UAV μ_i first flies horizontally from x_i to x_i^', then flies vertically up to h_i[This is equivalent to the deployment case that UAVs fly vertically first to the desired altitudes and then horizontally to the destination.]. It travels a normalized distance d_i(x_i^', h_i) = w · |x_i-x_i^'|+h_i, where w < 1 tells the different energy consumptions per unit horizontally and vertically flying distances. In practice, it is more energy consuming to fly vertically to the sky than horizontally along the ground. One may wonder the relationship between the normalized flying distance d_i and the energy consumption for a UAV. According to <cit.>, the energy consumption of UAV μ_i is a linear term c ḋ_i. The value of energy consumption c per unit distance depends on UAV prototype, and is estimated as 21.6 Watt hour per km (Wh/km) for UAV prototype MD4-3000 and 10.8 Wh/km for prototype DJI S1000, respectively.

After deployment, UAV μ_i only has leftover energy B_i - c · d_i to hover and providing wireless coverage. To prolong the whole UAV swarm's lifetime, we aim to maximize the minimum leftover energy among all the UAVs. Once one UAV uses up its energy, we can no longer guarantee full wireless coverage over [0,L] and the UAV swarm's service lifetime is ended up. Our energy-saving deployment problem of the UAV swarm is




    max_{(x_1^',h_1), ⋯, (x_n^',h_n)}1 ≤ i ≤ nmin  B_i - c ·d_i(x_i^', h_i)   , 
         s.t.,  [0, L] ⊆⋃_i=1^n [x_i^' - r(h_i), x_i^' + r(h_i)],
                 x_i^'∉∪_k=1^K δ_k.

To solve this max-min problem requires n UAVs to cooperate with each other in deployment distance and altitude to evenly use up their energy finally. The problem (<ref>) belongs to the domain of combinatorial optimization and the deployment solution is a specific combination of ordered UAVs above the ground in 2D, which is generally exponential in the number of UAVs and difficult to solve.




§ UAV SWARM DEPLOYMENT FROM A CO-LOCATED UAV STATION
 

In this section, we study problem (<ref>) when dispatching all the n UAVs from the nearest UAV ground station  (i.e., x_i = x_j for 1 ≤ i, j ≤ n). This is the case for covering a not huge service area L, and we do not need more UAVs from some other distant UAV stations. Without loss of generality, we assume that x_i = 0, ∀ 1 ≤ i ≤ n, which is symmetric to the case of x_i = L. Then the total travel distance of UAV μ_i is d_i=w x_i^'+h_i.  Note that for the case of 0 < x_i < L, we can divide the line interval into two subintervals (i.e., [0, x_i] and [x_i, L]), and apply our deployment algorithm (as presented later) similarly over both subintervals. We first skip the NFZ constraint in the first subsection as a benchmark and will add it back later to tell its effect.



 §.§ Deployment of UAVs without NFZ constraint
 

During the deployment, UAVs should cooperate to cover the whole target area and balance their energy consumptions. We have the following result for multi-UAV cooperation.



At an optimal solution to problem (<ref>), all the UAVs have the same amount of leftover energy storage after deployment, i.e., B_i-c d_i=B_j-c d_j, for 1≤ i, j≤ n. Their coverage radii do not overlap with each other and seamlessly cover the target interval. That is, [0, L] =  ⋃_i=1^n [x_i^' - r(h_i), x_i^' + r(h_i)], as illustrated in Figure <ref>.


See Appendix <ref>.


As the objective of problem (<ref>) is to maximize the minimum leftover energy bottleneck among the UAVs, we do not expect any two UAVs ending with different levels of leftover energy storage after deployment. Otherwise, we can improve the performance by lowering the UAV with less leftover energy and increasing the other UAV's altitude to make up the coverage gap. Then we have the following corollary. When the initial energy storage is identical, we expect the same flying distance to keep the same leftover energy among UAVs. The more energy is consumed in flying horizontal distance, less energy is left for flying vertically up to service altitude. Therefore, a UAV deployed further away on the ground should be placed to a lower altitude, while a closer UAV should be placed to a higher altitude for balancing multi-UAV energy consumption during deployment. It should be noted that if UAVs have different initial storages, the result below may not hold.


In the special case that UAVs have the same initial energy storages (i.e., B_i=B_j for 1 ≤ i,j ≤ n), in the optimal deployment solution, UAV μ_i deployed further away (i.e., with large x_i^' on the ground) should be placed to a lower altitude h_i for keeping the same energy consumptions among the UAVs during the deployment.





If UAVs are heterogeneous to have different initial energy storages upon deployment, we have following proposition to show that the UAV with larger energy storage should be dispatched further away along the ground in the optimal solution.


Without the loss of generality, suppose the initial energy storages of the n UAVs satisfy B_1 ≤ B_2 ≤⋯≤ B_n. Then the ground destinations of UAVs satisfy x_1^'≤ x_2^'≤⋯≤ x_n^' in the optimal solution to problem (<ref>).


First of all, for energy saving, a UAV's flying to an altitude higher than h^* is not necessary for deployment since it will not enlarge the coverage range but consume more energy for flying longer. Therefore, at the optimum the altitude h_i of each UAV μ_i after deployment to be not higher than h^*. Thus, in our algorithm design, we only need to consider the concavely increasing part of the function r(h_i).

At the optimum, we denote each UAV's leftover energy storage after deployment as B̂. Consider two neighboring UAVs μ_i and μ_j with initial energy storages B_i and B_j satisfying B_i < B_j. They seamlessly cover a continuous interval [x_j^' - r(h_j), x_i^' + r(h_i)] with touching point x_j^' + r(h_j) = x_i^' - r(h_i), as shown in the upper subfigure of Figure <ref>. We have B̂_i = B_i - c · (w · x_i^' + h_i) = B̂, and  B̂_j = B_j - c · (w · x_j^' + h_j) = B̂ for leaving the same residual energy after deploying the two UAVs. We prove by contradiction by supposing x_i^' > x_j^' at optimality given B_i < B_j, then we have h_i < h_j. As illustrated in the lower subfigure of Figure <ref>, we then swap μ_i and μ_j to show a better solution is actually achieved. Specifically, we move μ_i to x_i^'' at altitude h_i^' such that x_i^'' + r(h_i^') = x_j^' - r(h_j) to cover the same starting point in the target area. We can see that μ_i covers [x_i^'' - r(h_i^'), x_i^'' + r(h_i^')]. Then we divide our discussion, depending on the relationship between x_i^'' and x_j^'.

If x_i^''≥ x_j^', then h_i^'≥ h_j due to larger coverage and x_i^'' + r(h_i^') ≥ x_j^' + r(h_j). In this case, we can simply move μ_j to x_j^'' = x_i^' and h_j^' = h_i to cover prior [x_j^' + r(h_j), x_i^' + r(h_i)], as UAV μ_j has larger energy storage at x_i^' than UAV μ_i does at x_i^'. Since x_i^'' + r(h_i^') ≥ x_j^' + r(h_j) now, these two UAVs unnecessarily overlap in their coverage and we can further improve this solution beyond the optimal solution (before UAVs' swapping). This completes our proof by contradiction for this case.

Next, we consider x_i^'' < x_j^', then h_i^' < h_j and we move UAV μ_j rightwards to x_j^'' such that x_j^'' - r(h_j^') = x_i^'' + r(h_i^') for seamless coverage from UAV μ_i. As shown in Figure <ref>, x_i^' - 2r(h_j) = r(h_i), x_j^'' - 2r(h_i^') = r(h_j^'). If x_j^''≥ x_i^' given h_i^' < h_j, we have x_j^'' - 2r(h_i^') = r(h_j^') ≥ x_i^' - 2r(h_i^') ≥ x_i^' - 2r(h_j) = r(h_i), implying r(h_j^')≥ r(h_i). Therefore, we have x_j^'' + r(h_j^') ≥ x_i^' + r(h_j^') ≥ x_i^' + r(h_i). By using up the same amount of energy for both UAVs, we cover a larger total coverage than the optimal solution, telling that UAV swapping provides a better solution than the assumed optimal solution. This completes our proof by contradiction for this subcase.

Now, we only need to consider the other subcase of x_j^'' < x_i^'. As h_i^' = B_i - B̂/c - w · x_i^'' and h_j^' = B_j - B̂/c - w · x_j^'', then we have h_i^' + h_j^' = B_i - B̂/c - w · x_i^'' + B_j - B̂/c - w · x_j^''. Since x_i^'' < x_j^' and x_j^'' < x_i^', we have h_i^' + h_j^'≥B_i - B̂/c - w · x_i^' + B_j - B̂/c - w · x_j^' = h_i + h_j. Due to x_i^'' < x_j^' and x_j^' < x_i^', and h_i < h_i^' for leaving the same residual energy B̂. Moreover, h_i + h_j ≤ h_i^' + h_j^' < h_j + h_j^' due to h_i^'< h_j, we have h_i < h_j^'.

After swapping the two UAVs, we have x_j^'' = x_j^' - r(h_j) + 2 r(h_i^') + r(h_j^'). Note that h_i^'+h_j^'≥ h_i+h_j implies h_i^' + h_j^' > h_j. Since r(h) is an increasing function in our interested scope, we have r(h_i^') + r(h_j^')- r(h_j) > 0 and further 2r(h_i^')-r(h_j)+r(h_j^')>0. By combining this with the first equation in this paragraph, we have x_j^'' >  x_j^' and h_j^' < h_j for leaving the same residual energy B̂. Overall, we have h_i < h_i^' < h_j, h_i < h_j^' < h_j and h_i + h_j < h_i^' + h_j^'. To show the contradiction, we just need to prove x_j^' - r(h_j) + 2 (r(h_i^') + r(h_j^')) > x_j^' - r(h_j) + 2(r(h_i) + r(h_j)) for enlarging the total coverage with the same B̂. Simply, we only need to prove r(h_i^') + r(h_j^') > r(h_i) + r(h_j).

We let p = h_i^' + h_j^', then p - h_i > h_j. We define function f(λ) = r(λ) + r(p - λ) and the derivative is f^'(λ) = r^'(λ) - r^'(p - λ). f^'(λ) = 0 implies λ = p/2. As r(h) is an increasing concave function, r^'(h) > 0 and function r^'(h) is decreasing. Thus, f^'(λ) > 0 for 0 ≤λ < p/2. It follows that f(λ) is an increasing function for 0 ≤λ < p/2. Since p = h_i^' + h_j^', either h_i^' or h_j^' is less than p/2. Specifically, if h_j^'≤p/2, then we have f(h_j^') = r(h_i^') + r(h_j^') > f(h_i)=r(h_i)+r(p-h_i) due to h_i<h_j^'; if h_i^'≤p/2, then we have f(h_i^') = r(h_i^') + r(h_j^') >  f(h_i) =r(h_i)+r(p-h_i) due to h_i < h_i^'. In both cases, we thus have r(h_i^')+r(h_j^')>r(h_i)+r(h_j) due to p-h_i>h_j. This completes our proof by contradiction for this final subcase.





By Proposition <ref>, we can determine the ground destination order of the UAVs according to the order of B_1 ≤ B_2 ≤⋯≤ B_n. Based on Propositions <ref> and <ref>, we are ready to determine the optimal destination of each UAV in 2D for keeping their leftover energy storages identical. Specifically, due to non-overlapping full coverage of area [0, L], we first have



    2 ∑_1 ≤ i ≤ n r(h_i) = L.


Recall that, the leftover energy storage of UAV μ_i is B_i - c · (w · |x_i^'| + h_i), which should be the same as any other UAV's leftover energy storage, i.e.,


    B_i - c · (w · (2 (r(h_1) + r(h_2) + … + r(h_i)) -r(h_i)) + h_i) = 
         B_j - c · (w · (2 (r(h_1) + r(h_2) + … + r(h_j)) -r(h_j)) + h_j),  for 1 ≤ i ≠ j ≤ n,

where any UAV μ_i's final ground destination is x_i^' = 2 (r(h_1) + r(h_2) + … + r(h_i)) - r(h_i).  As we now rewrite x_i^' as functions of h_i's, we only have n unknowns of h_i's in the n equations in (<ref>) and (<ref>). By solving these equations jointly in a constant time O(1), we obtain the optimal deployment position (x_i^', h_i) for each UAV μ_i.






 §.§ Incorporation of NFZs for multi-UAV deployment
 


As presented in Section <ref>, we can compute the maximum minimum leftover energy storage objective B̂^* by solving (<ref>) and (<ref>) without considering NFZs. However, if the destinations of some UAVs fall into NFZ, the solution is not feasible. Without much loss of generality, we assume there is one NFZ, i.e., (δ^l, δ^r).[If there is more than one NFZ, we can similarly discuss each UAV's possibility to fly into any NFZ and there are just more combinations of Cases 1-3 across NFZs as in this subsection.] In this case, we consider all three possible cases for refining the deployment solution, and we have at most two UAVs relocated to the left- and right-hand-side edges of the NFZ at the optimum.

Case 1: UAV μ_i is chosen among all to relocate to the left-edge of NFZ (i.e.,x_i^' = δ^l), as shown in Figure <ref>. This UAV is not necessarily the one inside NFZ at the solution to (<ref>)-(<ref>). Similar to Proposition <ref>, given B_1 ≤⋯≤ B_n, we can show that at the performance bottleneck UAVs μ_i, μ_i+1, ⋯, μ_n have the same leftover energy storage as B̂^* and they seamlessly cover [δ^l -r(h_i), L] including NFZ without any overlap in their own coverages. That is,
        
        
    2 ∑_i ≤ j ≤ n r(h_j) = L - δ^l + r(h_i), 
        B_j - c · ( w · ( δ^l + r(h_i) + 2( r(h_i+1)+ r(h_i+2) + 
        ⋯ + r(h_j-1) + r(h_j)))) + h_j) = 
        B_i - c · (w ·δ^l + h_i) = B̂^*,   ∀ j,  i ≤ j ≤ n,

        where UAV μ_i is newly located to (x_i^'=δ^l, h_i) and UAV μ_j to (x_j^'=δ^l+r(h_i) + 2(r(h_i+1)+ r(h_i+2) + ⋯ + r(h_j-1) + r(h_j), h_j). By solving (<ref>)-(<ref>), we can determine the deployment positions of UAVs μ_i, μ_i+1, ⋯, μ_n as well as the objective B̂^*. Still we need to check and make sure that the other UAVs μ_1, μ_2, …, μ_i-1 are able to cover [0, δ^l - r(h_i)] by keeping at least energy B̂^* after deployment. Note that they may overlap with UAV μ_i's wireless coverage without reaching the bottleneck.

Case 2: UAV μ_i is chosen among all to dispatch to the right-edge of NFZ (x_i^' = δ^r), as shown in Figure <ref>. Similar to Proposition <ref>, we can show that at the performance bottleneck, UAVs μ_1, μ_2, …, μ_i should have the same leftover energy storage as B̂^* and they seamlessly cover [0, δ^r] without any coverage overlap. That is,
      
    2 ∑_1 ≤ j ≤ i r(h_j) = δ^r + r(h_i), 
        B_j - c · ( w · (2(r(h_1) + r(h_2) + ⋯ + r(h_j-1))+r(h_j)) 
        + h_j ) = B_i - c · (w ·δ^l + h_i) = B̂^*  ∀ j, 1 ≤ j ≤ i,

      where UAV μ_i is located to (x_i^'=δ^r, h_i) in 2D and UAV μ_j is located to (x_j^'= 2(r(h_1) + r(h_2) + ⋯ + r(h_j-1))+r(h_j), h_j). Still we need to check and make sure that the other UAVs μ_i, μ_i+1, …, μ_n are able to cover the rest target area [δ^r + r(h_i), L] by keeping at least energy B̂^* after deployment. Note that they may overlap with UAV μ_i's wireless coverage without reaching the bottleneck.

Case 3: Two neighboring UAVs μ_i-1 and μ_i are chosen to dispatch to the both edges of NFZ (i.e., x_i-1^' = δ^l, x_i^' = δ^r), as shown in Figure <ref>. The NFZ is covered by μ_i-1 and μ_i seamlessly and these two UAVs' coverages do not overlap. That is,
      
        
    r(h_i-1) + r(h_i) =  δ^r - δ^l, 
        B_i-1 - c · (w ·δ^l + h_i-1) = B_i - c · (w ·δ^r + h_i) = B̂^*

      
Moreover, we need to check if UAVs μ_1, μ_2, …, μ_i-2 are able to cover [0, δ^l - r(h_i-1)] and if UAVs μ_i+1, …, μ_n are able to cover [δ^r + r(h_i), L], by keeping at least energy B̂^* after deployment.

In these three cases, we can see that the critical UAV index i ∈{1, ⋯, n} is still undetermined. We propose to run binary search on UAV set {μ_1, ⋯, μ_n} to find the optimal i, providing the maximum leftover energy storage for the whole UAV network. Note that the binary search has complexity O(log n) for each UAV in each case. For example, in Case 1, after solving (<ref>)-(<ref>) for each UAV μ_i, we still need to check the feasibility of the other UAVs μ_1, ⋯, μ_i-1 on the left-hand side to fully cover [0, δ^l-r(h_i)] in linear running time, resulting in running time O(n log n) for scanning through all the UAVs. We summarize all the above in Algorithm <ref> and have the following result.






When dispatching UAVs from the same UAV station under the NFZ constraint, Algorithm <ref> optimally finds the maximum minimum leftover energy storage in O(n log n) running time.





§ DEPLOYING UAVS FROM DIFFERENT INITIAL LOCATIONS
 

In this section, we study the problem when UAVs may be initially located at different locations (e.g., different UAV ground stations or the places that UAVs rest after last task). This is especially the case under emergency when we need a lot more UAVs than those just from the nearest UAV station. Due to the UAV diversity in both initial energy storage and initial location, this problem becomes very difficult. It belongs to the domain of combinatorial optimization and the complexity is generally exponential in the number of UAVs. We aim to design approximation algorithms to maximize the minimum leftover energy storage.



 §.§ When UAVs have identical initial energy storage
 

In this subsection, we first study the special case when all UAVs have identical initial energy storage B. Without loss of generality, we assume the UAVs are sorted according to the increasing order of their initial ground locations, i.e., x_1 ≤ x_2 ⋯≤ x_n. We first prove that all UAVs' destinations after deployment should follow the same order as the initial locations.


Given that the initial locations of the n UAVs follow the order x_1 ≤ x_2 ≤⋯≤ x_n, the final ground destinations of them preserve the same order x_1^'≤ x_2^'≤⋯≤ x_n^' in the optimal solution of deployment.


Consider any two neighboring UAVs μ_i, μ_j with initial locations x_i ≤ x_j on the ground. We prove by contradiction here. After deployment, UAVs μ_i and μ_j cover a continuous portion of the line interval l, and suppose x_i^' > x_j^' in an optimal solution, as illustrated on the left-hand side of Figure <ref>. We obtain their travel distances d_i = w · |x_i-x_i^'| + h_i and d_j = w · |x_j- x_j^'| + h_j. If we swap the locations of μ_i and μ_j without changing their altitudes as illustrated on the right hand side of Figure <ref>, the new travel distances d_i and d_j are smaller than before and they save more energy by keeping the same total coverage l. Then the UAV network's leftover energy increases and the previous allocation of x_i^'≥ x_j^' is actually not optimal. This is the contradiction and we require x_i^'≤ x_j^' given x_i ≤ x_j.





Proposition <ref> greatly simplifies the algorithm design of deploying UAVs by fixing their location order after deployment, and we do not need to consider many combinations of UAVs' possible location orders in the combinatorial optimization. It also holds after incorporating NFZs and we next design the algorithm in two stages. First, we introduce the feasibility checking problem and design Algorithm <ref> to determine whether we can find a deployment scheme for any given leftover energy storage B̂. Then, we run binary search over all these feasible energy storages to find the optimum in Algorithm <ref>.



  §.§.§ Feasibility checking problem





Given any amount of leftover energy storage B̂∈ (0, B), we want to determine whether the energy budget B - B̂ is feasible to support all the UAVs to reach a full coverage of [0, L] and avoid sitting into NFZs. Let B̂^* denotes the maximum minimum leftover storage, we next design the feasibility checking algorithm to determine whether B̂ > B̂^* (infeasible for the UAVs to cover the whole target area) or B̂≤B̂^* (feasible). Note that B̂ is unknown yet and will be determined in next subsection. Our feasibility checking algorithm also works for the case with NFZs and its complexity order does not increase in the number of NFZs.

For UAV μ_i, we respectively denote a_i as the leftmost ground point and b_i as the rightmost point on L that can be covered by this UAV with B̂ leftover storage and altitude h_i. Note that a_i<x_i<b_i. To cover a_i, UAV μ_i travels horizontally x_i-a_i-r(h_i) distance, and it travels horizontally b_i-r(h_i)-x_i distance to cover b_i. Then we have




    a_i(h_i)= (B̂ - B/c · w) + x_i + h_i/w- r(h_i),






    b_i(h_i)= (B - B̂/c · w) + x_i - h_i/w + r(h_i),



both of which are functions of altitude h_i. Without loss of generality, we sequentially deploy UAVs to cover the target area from the left to right hand side, and we denote the currently covered interval as [0, L̅]. 

In Algorithm <ref>, we first respectively compute a_i and b_i in equations (<ref>) and (<ref>) in line 3, and then deploy the UAVs one by one (in line 5) according to their initial locations' order to cover from the left endpoint of target interval [0, L] as in Proposition <ref>. As x_1 ≤ x_2 ≤⋯≤ x_n, we start with UAV μ_1 and end up with UAV μ_n. Specifically, given our currently covered interval [0, L], we check whether UAV μ_i can extend L̅ within its energy budget B-B̂ (i.e., L∈ [a_i, b_i] in line 6). If so, we will deploy UAV μ_i's ground destination to x_i^' = min(L+r_i(h_i), b_i(h_i)- r_i(h_i)) in line 7 and cover from point L̅. Note that we do not use a UAV if L̅ is not within [a_i, b_i]. If the computed x_i^' falls into some NFZ (δ^l, δ^r), we should deploy UAV μ_i to δ^l on the ground and the corresponding service altitude is B-B̂/c - w · |x_i - δ^l| in the sky, as shown in lines 6-13. If the outcome of the algorithm shows B̂ is feasible i.e., (B̂≤B̂^*) in line 18, our algorithm will further return the UAVs' final locations (x_i^', h_i)'s in 2D. Otherwise, it returns that B̂ is infeasible in line 16. Overall, Algorithm <ref> solves the feasibility checking problem given a particular leftover energy storage B̂ in linear running time.








  §.§.§ Binary search over all feasible energy storages


With the help of Algorithm <ref>, we can verify whether a given leftover energy storage B̂ is feasible or not. The maximum leftover storage among all the feasible ones is actually the optimum. Here, we apply binary search to find the maximum leftover storage upon determining the search scope of B̂ and step size.

We first determine the search scope by computing its upper and lower bounds. By using the n UAVs to cover the line interval of length L, we must have at least one UAV with coverage radius r ≥L/2n. For each UAV μ_i, the minimum moving distance is its service altitude h_i without any ground movement. Suppose UAV μ_i is the one with coverage radius r(h_i) ≥L/2n or equivalently altitude h_i ≥ r^-1(L/2n), the upper bound of minimum leftover energy storage among all the UAVs is B̂_u = B - c · r^-1(L/2n).

We next determine the lower bound. We know that the longest horizontal travel distance of UAV μ_i is max{|L - x_i|, |x_i|}. Without flying any distance horizontally but vertically to the sky, the maximum service altitude is r^-1(max{|x_i|, |L-x_i|}) to cover [0, L]. Then we have the lower bound B̂_̂l̂=B- c(w max{|x_i|, |L-x_i|} + r^-1(max{|x_i|, |L-x_i|})).[In case that this formula returns a negative lower bound, we can replace it by the smallest possible positive energy storage.]

Now we are ready to present the approximation algorithm in Algorithm <ref> by combining both binary search and feasibility checking in Algorithm <ref>. We denote the relative error as ϵ, and accordingly set the search accuracy as ϵB̂_l in line 1 of Algorithm <ref>. Algorithm <ref> starts with ϵB̂_l in line 3 and stops once turning from feasible leftover energy storage B̂^' to infeasible B̂^'' in lines 12-15 as illustrated in illustrated in Figure <ref>. Then, the final B̂^' in line 17 is our searched optimum and is denoted as B̂^*.





Let B̂^* be the optimal leftover energy storage in problem (<ref>). Algorithm <ref> presents an (1 - ϵ)-approximation algorithm of computational complexity O(n log1/ϵ).


The leftover energy storage of a given instance has an upper bounded of B̂_u and a lower bound of B̂_l. Obviously, B̂_l ≤B̂^* ≤B̂_u. Choosing a small constant ϵ > 0, we divide each B̂_l into 1/ϵ sub-intervals. Each interval has length ϵ·B̂_l, where ϵ·B̂_l ≤ϵ·B̂^*. We divide B̂_u by ϵ·B̂_l into ⌈B̂_u/ϵ·B̂_l⌉ sub-intervals as set Λ as in line 1 of Algorithm <ref>.

Then, each operation in line 6 of binary search will reduce set Λ by applying Algorithm <ref> on a given B̂. It finally terminates with leftover energy storages B̂^' and B̂^'', as illustrated in Figure <ref>, where B̂^' < B̂^* and B̂^'' = B̂^' + ϵ·B̂_l > B̂^*. The outcome B̂^' is our searched optimum. We can obtain that B̂^' = B̂^'' - ϵ·B̂_l ≥B̂^* - ϵ·B̂_l ≥ (1 - ϵ) B̂^*. That is, we have (1 - ϵ) B̂^* ≤B̂  < B̂^*. Therefore, we obtain the minimum leftover storage with approximation ratio 1-ϵ as compared to the global optimum. Regarding the computational complexity, note that our feasibility checking algorithm runs in O(n) time. Moreover, we have O(⌈B̂_u/ϵ·B̂_l⌉) candidates of leftover energy storage for binary search with logarithmic running time, in which B̂_u/B̂_l is constant and independent of n. Overall, this algorithm runs in O(n log1/ϵ) time.




 §.§ Deploying UAVs with different initial energy storages


When UAVs are required to undertake emergency tasks, some of them may not be fully charged yet and they have different initial energy storages in general. To be specific, each UAV μ_i has an initial storage B_i upon deployment. In this subsection, we further consider that UAVs may have different initial energy storages under the constraint of NFZs. The UAVs' two-dimensions of heterogeneity (in both initial locations and initial energy storages), joint ground-sky movements and NFZ consideration results in high complexity for UAVs' energy-saving deployment algorithm design. In the following, we show such a general UAV deployment problem is NP-hard, and propose a heuristic algorithm accordingly.



Given any value of B̂ as the minimum leftover energy storage among the UAVs after deployment, we want to determine whether UAVs can be moved to reach a full coverage of [0, L] under the NFZs constraint. We call it feasibility problem as in previous Section <ref>, which is now proved to be NP-complete by reducing from the well-known Partition problem <cit.>. In this reduction, the basic idea is to consider two NFZs around the middle point of the target line interval, and partition the UAVs with different coverage energy storages into two subsets, each of which seamlessly covers a half of the line interval without any overlaps.


When UAVs have different initial energy storages and are deployed from different initial locations under the NFZ consideration, our energy-saving UAV swarm deployment problem in (<ref>) is NP-hard.


See Appendix <ref>.







The problem (<ref>) is difficult to solve due to the UAVs' distinct initial locations and initial energy storages, which result in exponential number of sequences of UAVs for searching. Yet if the location order after deployment is determined (e.g., with initial location order preserving as in Algorithm <ref> under the same initial energy storage), we can compute the maximum leftover energy storage fast under the given location order. Further, if we enumerate the location order among UAVs as many as possible, then we can reach the optimality without any efficiency loss. To balance complexity and efficiency, we accordingly propose Algorithm <ref> with κ as the order changing degree after deployment. Specifically, we select κ UAVs and enumerate all possible permutations for their final ground locations' ordering. This produces N = C_n^κ·κ ! sequences of UAVs'ordering, each of which runs Algorithm <ref> separately. If we care more about the efficiency rather than the complexity, we can choose a larger κ and when κ = n, Algorithm <ref>'s performance is arbitrarily approach the global optimum as in Theorem <ref>.







§ EXTENSION TO UAVS'ENERGY-SAVING DEPLOYMENT IN A 3D SPACE
 

Recall in all the previous sections, we model the target service area as a line interval [0, L] and assume all the UAVs are initially located in the same 1D linear domain. Then we deploy each UAV in 2D by considering the 1D ground and 1D sky movements. In this section, we consider that UAVs' initial locations may not be along the target interval and need to determine UAVs' ground movements in 2D as well as 1D movement to the Sky. Without much loss of generality, we consider two UAV stations on the left and right corners of the ground plane with locations (x_l, y_l, 0) and (x_r, y_r, 0) satisfying x_l<x_r, and also place target interval [0, L] in the x-axis in the 2D ground plane, as illustrated in Figure <ref>. That is, target interval ranges from point (0, 0 ,0) to (L, 0, 0) in the 3D space. Then each UAV μ_i is now placed finally to point (x_i^', y_i^', h_i) in 3D space. We want to extend the previously proposed UAV swarm deployment algorithms with theoretical guarantee to 3D. There are n UAVs in total with |U_l+U_r| = n including UAVs μ_1 - μ_|U_l| initially located in the left UAV station (belonging to set  U_l) and UAVs μ_|U_l|+1 - μ_n initially located in the right UAV station (belonging to set U_r). We reorder the UAVs from U_l such that B_1 ≤⋯≤ B_|U_l| in increasing energy storage order, while reorder the UAVs from U_r such that B_|U_l|+1≥⋯≥ B_n in decreasing order.



At the optimum, the UAVs from the left- and right-hand side UAV stations will not cross each other. That is, x_1^'≤⋯≤ x_n^' in the x-domain in the 3D space. And finally the UAVs will keep the same leftover energy after the deployment.


First of all, for UAV subset U_l or U_r in the left or right-hand side UAV station, we can prove Proposition <ref> still holds here. That is, we should deploy all the UAVs in U_l from left to right hand side of the target interval according to increasing order of their initial energy storages. Similarly, we deploy the UAVs in U_r from right to left hand side of the target interval according to increasing order of by their initial energy storages. At the optimum, all the UAVs' leftover energy is the same to maximize the minimum leftover energy storage.

Now, we are ready to prove that any two UAVs will not fly to cross each other by contradiction. Note that the UAVs from the same UAV station will not fly across each other, and we will only look at the UAVs' possible crossing from different stations. Suppose that there are two UAVs μ_i and μ_j originally in U_l and U_r (i.e., x_i=x_l and x_j=x_r), respectively, and they will cross each other with x_i^'≥ x_j^' and become neighbors after deployment. They cover a continuous line interval [x_j^'-√(r(h_j)^2- y_j^'^2), x_i^'+√(r(h_i)^2-y_i^'^2)] as part of the target interval [0, L], and they have the same leftover energy (B_i - d_i = B_j - d_j = B̂^*) in the optimal solution. Next we swap UAVs μ_i and μ_j to show a better solution is actually achieved. If we swap the x-domain ground location order of μ_i and μ_j without changing any UAV's coverage radius or altitude, we can see that d_i^' = w ·√((x_l-x_i^')^2 + (y_l-y_i^')^2)+h_i and d_j^' =  w ·√((x_r-x_j^')^2+ (y_r-y_j^')^2)+h_j will decrease, i.e., d_i^' < d_i and d_j^'< d_j. Specifically, we move μ_i to cover from x_j^' - √(r(h_j)^2-y_j^'^2) and move μ_j to cover until x_i^' + √(r(h_i)^2-y_i^'^2). We can see that the original covered range [x_i^' - √(r(h_i)^2- y_i^'^2), x_j^' -√(r(h_j)^2+ y_j^'^2)] is still covered by UAVs μ_i and μ_j, and d_i^' < d_i and d_j^'< d_j. Given B_i - c d_i^'  > B̂^* and B_j - c d_j^' > B̂^*, a better solution is achieved to prolong the UAV network lifetime.



We decide the cooperation among UAVs by separating the UAVs into two subsets U_l and U_r, which cover left and right hand parts of [0, L], respectively. Lemma <ref> helps fix the final location order in x-domain of all UAVs and based on the given ordering sequence, we next introduce the feasibility checking problem and binary search similar to Section <ref>.


Before extending Algorithm <ref> to our new deployment problem in 3D  given any leftover energy storage B̂ and altitude h_i for UAV μ_i, we first determine the leftmost point a_i and the rightmost point b_i on L that can be covered by UAV μ_i as follows:




    a_i(h_i)= x_l - √((B_i - B̂/c · w - h_i/w)^2 - (y_i^' - y_l)^2) - r(h_i),






    b_i(h_i)= x_r + √((B_i - B̂/c · w - h_i/w)^2 - (y_i^' - y_r)^2) + r(h_i).



Here we deploy the UAVs in U_l to cover the target area from left to right hand side, and we denote the currently covered interval as [0, L_l], while we deploy the UAVs in U_r to cover the target area from right to left hand side, and the currently covered interval is [L_r, L].





Next, we determine the scope of binary search. The leftover energy B̂ among all the UAVs is upper bounded by B̂_u = maxB_i. We choose a smallest possible energy storage B̂_l as the lower bound of B̂. Obviously, B̂_l ≤B̂^* ≤B̂_u. Similar to Algorithm <ref>, we choose a small positive constant ϵ > 0 and divide each B̂_l into 1/ϵ sub-intervals. Each interval has length ϵ·B̂_l, where ϵ·B̂_l ≤ϵ·B̂^*. We divide B̂_u by ϵ·B̂_l to partition into ⌈B̂_u/ϵ·B̂_l⌉ sub-intervals in set Λ as the input of Algorithm <ref>.

In Algorithm <ref>, we first compute a_i and b_i in line 7 according to equations (<ref>) and (<ref>), then deploy the UAVs one by one (line 9 for the UAVs in U_l and line 15 for those in U_r) according to their initial energy storages' order to cover the target interval [0, L]. Specifically, considering the UAVs in U_l, given our currently covered interval [0, L_l], iteration i starts with checking whether UAV μ_i inside can extend the current covered area. That is, we need to check if μ_i can seamlessly cover from the point L_l (i.e., b_i(h_i) - r(h_i) ≤L_l ≤ b_i(h_i) in line 10). If so, we will deploy UAV μ_i to x_i^' = L_l + r(h_i) and update L_l  in lines 11-12. Similar procedure with reverse direction in lines 15-20 follows for those UAVs in set U_r.

If L_l ≥L_r to fully cover the target interval [0,L], the feasibility checking returns that the given B̂ is feasible (i.e., B̂≤B̂^*) in line 22, our algorithm will skip this choice B̂ and keep running binary search for larger leftover energy solution (if feasible). Otherwise, it returns that B̂ is infeasible in line 24 and our algorithm will search for smaller feasible candidates. Finally, our algorithm will return the optimal B̂^* in the search scope. Similar to Theorem <ref>, we have the following corollary.

 
Let B̂^* be the optimal leftover energy storage of our energy-saving UAV deployment problem by dispatching the UAVs swarm from two UAV stations, given any allowable error ϵ >0, Algorithm <ref> achieves approximation ratio (1 - ϵ) and runs in O(n log1/ϵ) time.







§ SIMULATIONS
 
In this section, we present extensive simulations to evaluate the proposed algorithms in different scenarios. Regarding the setting of UAVs' technical specifications, we approximate the wireless coverage radius of UAV μ_i hovering at altitude h_i as a concavely increasing function r(h_i) = α h_i^β with α =1, β = 0.5 till the turning point h^*= 2km according to the measurement experiment done in <cit.>. We set w = 0.2, the initial energy storage B = 0.78 kWh, and the energy consumption per flying distance c = 21.6 Wh/km, as recommended by <cit.>. Moreover, we set the length of target interval as L = 20 km, and the length of the NFZ as 3 km inside.










 §.§ Deploying UAVs from the same station


We first present the simulation results when dispatching the UAVs from the same location, as studied in Section <ref>. Figure <ref> shows 5 UAVs' final service altitudes and ground destinations by solving (<ref>) and (<ref>). Figure <ref> shows the optimal solution without NFZ consideration, and it tells us that a UAV deployed further away to the right-hand-side of the ground should be placed to a lower altitude for keeping multi-UAVs' energy consumptions or travel distances the same. Figure <ref> shows the case when we add an NFZ [δ^l, δ^r] with edges δ^l=10 km, δ^r=13 km. We can see that UAV μ_3 has to re-locate to the right NFZ edge δ^r. This pushes UAVs μ_4 and μ_5 further away to the right corner of [0, L]. Further, after increasing UAV μ_3's initial energy storage from 0.78 to 0.9 kWh in Figure <ref>, UAV μ_3 with the largest energy storage flies to the right-most ground location and UAV μ_4 re-locates to δ^l finally. This is consistent with Proposition <ref>.

Next, we show the minimum leftover energy storage or UAV the swarm's residual lifetime (i.e., objective of problem (<ref>)) as a function of the number of UAVs. Figure <ref> shows the minimum leftover energy storage increases as more UAVs are given, as each UAV only needs to cover a smaller range and this improves the bottleneck UAV performance. It also shows more energy will be consumed when we take into account the NFZ constraints.






 §.§ Deploying UAVs from different initial locations


In Figure <ref>, we show the running time or computational complexity of our Algorithm <ref> in Section <ref> under different values of relative error ϵ = 0.1, 0.01 and 0.001, respectively. All the UAVs have the same initial energy storage here. It can be observed that the smaller value of ϵ is, the longer running time is required. In addition, as the number of the UAVs increases, the running time increases yet is actually less than the theoretical bound O(n log1/ϵ) proved in Theorem <ref>, since the theoretical analysis there is based on the worst case analysis and here is based on average or empirical analysis.





Now we are ready to evaluate Algorithm <ref> in Section <ref> for deploying the UAVs with different initial locations as well as different energy storages. Recall that the initial order preserving property no longer holds, and we need to update the order changing degree κ to balance the efficiency and complexity. In Figure <ref>, problem (<ref>) is solved by Algorithm <ref> with κ = 0 (preserving all the UAVs' initial location order as in Algorithm <ref>), and with κ = 1, 2, 3, 4 (with increasingly more freedom to rotate any two neighboring UAVs's final ground destinations), respectively. The computational complexity is positively related to κ. As κ increases, we gradually relax the location order preserving constraint, and Figure <ref> shows the minimum leftover storages obtained by Algorithm <ref> increases.




 §.§ Deploying UAVs in the 3D space


In Figure <ref>, the sustainable UAV deployment problem in 3D is solved by Algorithm <ref>, assuming all UAVs are dispatching from the two UAV stations on the left and right-hand corners of the target interval. As the UAV set is U = U_l ∪ U_r = {μ_1, μ_2, …, μ_n}, we set n = 10 and discuss the effect of the difference between |U_l| and |U_r| on the UAV swarm's lifetime performance. By setting a larger value of |U_l|, we have more UAVs in the left station rather than the right station. We can see from Figure <ref>, when the division of UAVs is symmetric between the two UAV stations, our algorithm can achieve the longest UAV swarm lifetime, since the UAVs on the left-hand-side (or right-hand-side) station do not need to fly further to cover the right (left) part of the target interval [0, L].






§ CONCLUSION
 

The energy-saving UAV deployment problem for keeping wireless coverage is of great practical importance. We study the energy-saving UAV deployment problem to prolong the UAV swarm's residual lifetime. When all UAVs are deployed from a common UAV station, we propose an optimal deployment algorithm, by jointly optimizing UAVs' flying distances on the ground and final service altitudes in the sky. We show that a UAV with larger initial energy storage should be deployed further away from the UAV station for balancing multi-UAVs' energy consumption in the flight. Due to NFZs consideration, the problem becomes more difficult and the whole UAV swarm consumes more energy. We solve it optimally in O(n log n) time. Moreover, when n UAVs are dispatched from different initial locations, we first prove that any two UAVs will not fly across each other in the flight as long as they have the same initial energy storage, and then design an approximation algorithm to arbitrarily approach the optimum. Further, we consider that UAVs may have different initial energy storages under the constraint of NFZs, and we prove this problem is NP-hard. Despite of this, we successfully propose a heuristic algorithm to solve it by balancing the efficiency and computation complexity well. Finally, we extend the FPTAS to a 3D scenario and validate theoretical results by extensive simulations. Still, there are some open issues in future work, i.e., the interference among UAVs' wireless services and/or the algorithms' extensions to cover higher dimensional target, e.g 2D area or 3D object.





§ PROOF OF PROPOSITION <REF>
 




As shown in Section <ref>, for energy saving, at the optimum the altitude h_i of each UAV μ_i after deployment to be not higher than h^*. Thus, we only consider the concavely increasing part of the function r(h_i) here. First, we show that any two neighboring UAVs will not overlap in the optimal solution by contradiction. Suppose in the optimal solution, the coverages of two UAVs μ_i and μ_j overlap as shown in Figure <ref>. In this case, we can simply lower the service altitude of μ_i and move left relatively to remove the overlap, while decrease its energy consumption for moving. We can see that we can obtain better solution and the leftover energy storages of both UAVs do not increase by removing the overlap. This is a contradiction. Next, suppose two UAVs μ_i and μ_j seamlessly cover a subinterval of L in the optimal solution, but they have different leftover energy (i.e., B̂_i = B_i-c · d_i, B̂_j = B_j - c · d_j). If B̂_i < B̂_j and B̂_i is the bottleneck, we can lower the service altitude of μ_i and move left relatively to decrease its energy consumption while increase the service altitude of μ_j for keeping exactly the same total coverage. In this way, the bottleneck μ_i has more leftover energy and the objective of problem (<ref>) is further improved. Otherwise, B̂_i > B̂_j and B̂_j is the bottleneck, we can lower the service altitude of μ_j and move right relatively to decrease its energy consumption. In the meantime, we increase the service altitude of μ_i and move right to cover more for keeping exactly the same total coverage. In the end, the bottleneck B̂_j is increased and our proof is completed.




§ PROOF OF THEOREM <REF>
 


Given an instance of the sustainable UAV deployment problem and B̂, we show that it is NP-hard to determine whether the UAVs' leftover energy storage is at least B̂ after deployment. Here, we choose concave function r(h_i) = α h_i^β till turning point h^* and set α = 0.5 and β = 1, and the problem is NP-hard as long as we show this special problem is NP-hard.

We reduce the Partition problem, which is a well-known NP-hard problem <cit.>, to our sustainable UAV deployment problem. The Partition problem is defined as follows: Given a sequence of positive integers 1 ≤ a_1≤ a_2≤, …, ≤ a_m, we want to determine whether there exists a set of indices Γ⊆{1, 2, …, m} such that ∑_i ∈Γa_i = 1/2∑_i=1^ma_i.

Given a Partition instance, we construct the following sustainable UAV deployment problem. There is a UAV for each input number: x_i = L/2, and B_1 = ρ + 3r(h_1) + B̂, B_n = L/2 + r(h_n) + B̂, and B_1≤ B_2≤, …, ≤ B_n. We add one UAV μ_m+1 with B_m+1 = 2ρ + B̂. r(h_1) > ρ.

We show that if a_1, …, a_m∈ Partition, then there exists a solution with B̂. ∑_i ∈Γa_i = 1/2∑_i=1^ma_i = L/2 - ρ. We set r_i = 1/2 a_i. We deploy the UAVs with initial energy storage B_i for i ∈Γ to cover [0, L/2 - ρ].

For UAV μ_i (i ∈Γ), assume |Γ| = T, we make the initial energy storage B_i satisfy the following requirements:


    L/2 + r(h_1) = B_1 - B̂
       …
       L/2 - 2(r(h_1) + … + r(h_T-1) + r(h_T) = B_T - B̂
       r(h_1) + … + r(h_T-1) + r(h_T) = L/2 - ρ

Similar process can be conducted on UAVs μ_i (i ∉Γ) to cover [ρ, L/2]. We can compute ∑ B_i = 1/2∑_i=1^ma_i to just fully cover [0, L/2 - ρ] or [L/2 + ρ, L/2].



In our sustainable UAV deployment problem, we have n=m+1 UAVs which are initially located at the position L/2. Moreover, μ_i is associated with initial energy storage B_i = a_i for 1 ≤ i ≤ m and μ_m+1 is associated with 2 ρ + B̂. There are two NFZs with length 2 ρ located at both sides of point L/2. This transformation can clearly be performed in polynomial time. See Figure <ref> for an example.



We now prove that there exists a solution to the instance P of the Partition problem if and only if the constructed instance C of the sustainable UAV deployment problem has a solution of at least B̂.


(⟹) Given a solution Γ to the instance P of the Partition problem, we can move UAVs μ_i for i ∈Γ to the left such that every point of the interval [0,L/2 - ρ] is covered and move μ_j for j ∉Γ to the right such that every point of the interval [L/2 + ρ, L/2] is covered. Moreover, we move μ_m+1's vertically to ρ such that every point of the interval [L/2 - ρ, L/2 + ρ] is covered. Since we have ∑_i ∈Γ2 · r(h_i) =∑_j ∈{1, 2, …, m}∖Γ2 · r(h_j) = 1/2∑_i=1^ma_i = L/2 - ρ, it is obvious to see that this is a feasible solution and the detailed movements can be implemented in the straightforward way. Therefore, we have a solution of at least B̂ to the instance C of the sustainable UAV deployment problem.


(⟸) Now we have a feasible solution of at least B̂ to the instance C of the sustainable UAV deployment problem. We first observe that the UAV μ_m+1 has to fly vertically to 2ρ. Since every point of the interval [0, L] is required to be covered, there does not exist an “overlapped interval” between any two UAVs' ranges in a feasible solution. For the UAVs μ_1, …, μ_n, we need to find a subset of UAVs with the summation of battery to fully cover [0,L/2 - ρ] or [L/2 + ρ, L/2], which is 1/2∑_i=1^ma_i. The above analysis shows that ∑_i ∈Γ r(h_i)= ∑_i ∈Γa_i=1/2∑_i=1^ma_i, which implies that we have a solution to the instance P of the Partition problem. The proof is thus complete.





§ PROOF OF LEMMA <REF>
 

First of all, for UAV subset U_l or U_r in each of the left and right-hand side UAV stations, Proposition <ref> still holds. That is, we should deploy all the UAVs in U_l from left to right hand side of the target interval according to increasing order of by their initial energy storages. Similarly, we deploy the UAVs in U_r from right to left hand side of the target interval according to increasing order of by their initial energy storages. At the optimum, all the UAVs' leftover energy is the same.

Now, we are ready to prove this lemma by contradiction. Consider that there are two UAVs μ_i and μ_j that will cross each other with x_i^'≥ x_j^' and become neighbors after deployment. Here, μ_i is originally located in U_l and μ_j in U_r (i.e., x_i = x_l, x_j = x_r). They cover a continuous line interval [x_j^'-√(r(h_j)^2- y_j^'^2), x_i^'+√(r(h_i)^2-y_i^'^2)] along target interval [0, L], and they have the same leftover energy (B_i - d_i = B_j - d_j = B̂^*) in the optimal solution. Next we swap μ_i and μ_j to show a better solution is actually achieved. If we swap the ground location order of μ_i and μ_j without changing any UAV's coverage radius or altitude, we can see that d_i^' = w ·√((x_l-x_i^')^2 + (y_l-y_i^')^2)+h_i and d_j^' =  w ·√((x_r-x_j^')^2+ (y_r-y_j^')^2)+h_i will decrease, i.e., d_i^' < d_i and d_j^'< d_j. Specifically, we move μ_i to cover from x_j^' - √(r(h_j)^2-y_j^'^2) and move μ_j to cover until x_i^' + √(r(h_i)^2-y_i^'^2). We can see that the original covered range [x_j^' -√(r(h_j)^2- y_j^'^2), x_i^' + √(r(h_i)^2- y_i^'^2)] is still covered by μ_i and μ_j, and d_i^' < d_i and d_j^'< d_j. Given B_i - c d_i^'  > B̂^* and B_j - c d_j^' > B̂^*, a better solution is achieved to prolong the UAV network lifetime. The proof is completed.





plainnat
19

zeng2016wireless
Y. Zeng, R. Zhang, and T. J. Lim, “Wireless communications with unmanned
  aerial vehicles: opportunities and challenges,” IEEE Communications
  Magazine, vol. 54, no. 5, pp. 36–42, 2016.
  
zhang2017optimization
X. Zhang and L. Duan, “Optimization of emergency UAV deployment for
  providing wireless coverage,” in IEEE Global Communications Conference
  (GLOBECOM), 2017.
  
chenjimingUAV
L. Wang, H. Yang, J. Long, K. Wu, J. Chen, “Enabling Ultra-Dense UAV-Aided Network with Overlapped Spectrum Sharing: Potential and Approaches,” IEEE Network, vol. 32, no. 5, 85–91, 2018.
  
xu2018uav
X. Xu, L. Duan, and M. Li, “UAV placement games for optimal wireless service
  provision,” in 16th International Symposium on Modeling and
  Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), 2018.

NFZ
Civil Aviation Authority of Singapore (CAAS), “Unmanned aircraft systems,”
  <https://www.caas.gov.sg/public-passengers/unmanned-aircraft-systems>,
  accessed October 29, 2018.

pan2012cooperative
M. Pan, P. Li, and Y. Fang, “Cooperative communication aware link scheduling
  for cognitive vehicular networks,” IEEE Journal on Selected Areas in
  Communications, vol. 30, no. 4, pp. 760–768, 2012.

al2014optimal
A. Al-Hourani, S. Kandeepan, and S. Lardner, “Optimal lap altitude for maximum
  coverage,” IEEE Wireless Communications Letters, vol. 3, no. 6, pp.
  569–572, 2014.

mozaffari2015drone
M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Drone small cells in the
  clouds: Design, deployment and performance analysis,” in IEEE Global
  Communications Conference (GLOBECOM), 2015.
  
liwangTVT
L. Wang, H. Tang, H. Wu, and G. Stber, “Resource Allocation for D2D Communications Underlay in Rayleigh Fading Channels,” IEEE Transactions on Vehicular Technology, vol. 66, no. 2, pp. 1159–1170, 2017.

zeng2017energy
Y. Zeng and R. Zhang, “Energy-efficient UAV communication with trajectory
  optimization,” IEEE Transactions on Wireless Communications, vol. 16,
  no. 6, pp. 3747–3760, 2017.
  


zhang2018fast
X. Zhang and L. Duan, “Fast deployment of UAV networks for optimal wireless
  coverage,” IEEE Transactions on Mobile Computing, vol. 18, no. 3, pp.
  588–601, 2019.

azari2017coverage
M. M. Azari, Y. Murillo, O. Amin, F. Rosas, M.-S. Alouini, and S. Pollin,
  “Coverage maximization for a poisson field of drone cells,” in 28th
  Annual International Symposium on Personal, Indoor, and Mobile Radio
  Communications (PIMRC), 2017, pp. 1–6.

wang2018unmanned
H. Wang, G. Ren, J. Chen, G. Ding, and Y. Yang, “Unmanned aerial vehicle-aided
  communications: Joint transmit power and trajectory optimization,”
  IEEE Wireless Communications Letters, 2018.

wu2017joint
Q. Wu, Y. Zeng, and R. Zhang, “Joint trajectory and communication design for
  multi-uav enabled wireless networks,” arXiv preprint
  arXiv:1705.02723, 2017.

wang2018traffic
Z. Wang, L. Duan, and R. Zhang, “Traffic-aware adaptive deployment for
  uav-aided communication networks,” IEEE Transactions on Wireless Communications, forthcoming. [Online]. Available: https://arxiv.org/pdf/1812.03267.pdf.

wang2018dynamic
X. Wang and L. Duan, “Dynamic pricing and capacity allocation of
  UAV-provided mobile services,” in IEEE Conference on Computer
  Communications (INFOCOM), 2019.

gao2018approximation
X. Gao, J. Fan, F. Wu, and G. Chen, “Approximation algorithms for sweep
  coverage problem with multiple mobile sensors,” IEEE/ACM Transactions
  on Networking (TON), vol. 26, no. 2, pp. 990–1003, 2018.

lu2015maximum
Z. Lu, W. W. Li, and M. Pan, “Maximum lifetime scheduling for target coverage
  and data collection in wireless sensor networks,” IEEE Transactions on
  vehicular technology, vol. 64, no. 2, pp. 714–727, 2015.

figliozzi2017drones
M. Figliozzi, “Drones for commercial last-mile deliveries: A discussion of
  logistical, environmental, and economic trade-offs,” Civil and
  Environmental Engineering Faculty Publications and Presentations. 416.,
  2017.

garey2002computers
M. Garey and D. Johnson, Computers and intractability.1em plus
  0.5em minus 0.4emW. H. Freeman New York, 2002, vol. 29.

caillouet2018optimization
C. Caillouet, F. Giroire, and T. Razafindralambo, “Optimization of mobile
  sensor coverage with UAVs,” in IEEE Conference on Computer
  Communications (Workshops) (INFOCOM), 2018, pp. 622–627.



