PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Deployment of UAV Networks for Optimal Wireless Coverage

Xiao Zhang, Lingjie Duan

arXiv:1710.05616v2cs.NI

TL;DR

The paper addresses fast wireless-coverage deployment of heterogeneous UAVs, which prior UAV work overlooks and sensor-network methods cannot directly handle. It studies min-max and min-sum deployment delay under different dispatch settings, proving general NP-completeness and providing exact, approximate, and dynamic-programming algorithms.

  • Problem

    Prior UAV-network work overlooks fast wireless-coverage deployment, while sensor-network deployment results do not directly apply to heterogeneous UAVs deployed in the air.

  • Method

    The paper models heterogeneous UAV deployment through min-max and min-sum delay objectives and designs algorithms for same-location and different-location dispatch.

  • Results

    Both problems are NP-complete in general; the paper provides an optimal O(n^2) same-location min-max algorithm, an FPTAS for different locations, and algorithms for min-sum deployment.

  • Takeaways & Limitations

    Fast deployment of heterogeneous UAVs requires distinct fairness- and efficiency-oriented algorithms tailored to dispatch location settings.

  • Takeaways & Limitations

    Sensor-network deployment algorithms cannot apply directly because UAVs must be deployed to the air and have heterogeneous speeds, altitudes, and coverage radii.

Abstract

from arXiv · show

Unmanned Aerial Vehicle (UAV) networks have emerged as a promising technique to rapidly provide wireless coverage to a geographical area, where a flying UAV can be fast deployed to serve as cell site. Existing work on UAV-enabled wireless networks overlook the fast UAV deployment for wireless coverage, and such deployment problems have only been studied recently in sensor networks. Unlike sensors, UAVs should be deployed to the air and they are generally different in flying speed, operating altitude and wireless coverage radius. By considering such UAV heterogeneity to cover the whole target area, this paper studies two fast UAV deployment problems: one is to minimize the maximum deployment delay among all UAVs (min-max) for fairness consideration, and the other is to minimize the total deployment delay (min-sum) for efficiency consideration. We prove both min-max and min-sum problems are NP-complete in general. When dispatching UAVs from the same location, we present an optimal algorithm of low computational complexity $O(n^2)$ for the min-max problem. When UAVs are dispatched from different locations, we propose to preserve their location order during deployment and successfully design a fully polynomial time approximation scheme (FPTAS) of computation complexity $O(n^2 \log \frac{1}ε)$ to arbitrarily approach the global optimum with relative error $ε$. The min-sum problem is more challenging. When UAVs are dispatched from the same initial location, we present an approximation algorithm of linear time. As for the general case, we further reformulate it as a dynamic program and propose a pseudo polynomial-time algorithm to solve it optimally.

2 I. INTRODUCTION

This paper studies rapid deployment of heterogeneous UAVs to provide wireless coverage, addressing a gap in prior UAV and sensor-network deployment research. It formulates fairness- and efficiency-oriented delay objectives and develops exact, approximate, and pseudo-polynomial algorithms for different dispatch settings.

  • Research gap: Existing UAV-network research overlooks fast deployment for wireless coverage, while sensor-network results do not directly apply to UAVs.UAV deployment differs because vehicles must operate in the air and vary in flying speed, altitude, and coverage radius.
  • Problem formulation: The paper minimizes either the maximum deployment delay for fairness or the total deployment delay for efficiency.The min-max objective addresses worst-case service delay, whereas min-sum targets average travel time for full coverage.
  • Problem formulation: The min-max and min-sum deployment problems are both NP-complete in general.The two objectives can conflict: reducing maximum delay may increase total delay, and vice versa.
  • Min-max deployment: For same-location dispatch, the paper gives an optimal min-max algorithm with complexity O(n^2).The algorithm balances UAVs’ diverse flying speeds.
  • Min-max deployment: For different-location dispatch, preserving UAV location order enables an FPTAS with complexity O(n^2 log 1/ε) and relative error ε.The scheme approaches the global optimum while retaining the location-order constraint.
  • Min-sum deployment: For min-sum deployment, the paper presents a linear-time approximation for same-location dispatch and a pseudo-polynomial dynamic-programming algorithm for different locations.The general-case method reformulates the min-sum problem as a dynamic program and solves it optimally.

II. RELATED WORK

Prior UAV-network research primarily addresses communication, coverage, energy, or movement objectives, while fast deployment for full-area wireless coverage remains insufficiently studied. Sensor-network deployment methods do not directly apply because UAV deployment must account for aerial operation and heterogeneous flight and coverage parameters.

  • Existing UAV-network studies focus mainly on communication performance, coverage, transmit power, or propulsion energy rather than fast deployment for wireless coverage.
  • Recent sensor-network studies consider maximum or total deployment movement, but their methods cannot apply directly to fast UAV deployment.
  • UAV deployment differs from sensor deployment because UAVs must operate in the air with heterogeneous altitudes, flying speeds, and coverage radii.
  • The paper formulates full wireless coverage of a target area using diverse UAVs that travel to final positions and hover at operating altitudes.
  • The target area is reduced to a line interval for theoretical analysis, and both deployment problems are shown to be NP-complete.

IV. OPTIMIZATION OF MIN-MAX DEPLOYMENT PROBLEM

The min-max objective seeks fair deployment by minimizing the largest UAV travel time. For UAVs dispatched from one location, a greedy furthest-point assignment yields an optimal O(n^2) algorithm.

  • The min-max objective minimizes the maximum deployment delay among UAVs so users across the target region are treated fairly.
  • When UAVs start from the same location, the algorithm repeatedly assigns the unassigned UAV with minimum travel time to cover the furthest uncovered point.
  • The procedure records each selected UAV’s travel time and continues until the target interval is fully covered.
  • For fixed altitudes, UAVs with larger flying speeds and coverage radii are preferred for positions farther away in the target area.
  • Algorithm 1 optimally solves the same-location min-max problem in O(n^2) time.

B. Problem reformulation under order preserving of UAVs’ locations

The general min-max problem is difficult, so the paper preserves UAV location order and tests deployment feasibility under a common deadline. An ordered feasibility algorithm constructs a full coverage when possible.

  • The general min-max deployment problem is NP-complete, and selecting an optimal UAV combination can be exponential in the number of UAVs.
  • Preserving initial location order requires final positions to maintain the same order, simplifying coordination and avoiding UAV crossings.
  • 1) Feasibility checking problem: For a deadline T, each UAV is characterized by leftmost and rightmost points it can cover within that deadline.
  • 1) Feasibility checking problem: The feasibility algorithm processes UAVs in location order, skips those unable to reach altitude, and dispatches eligible UAVs that can extend the covered interval.
  • 1) Feasibility checking problem: The feasibility problem is solved optimally in O(n^2) time, returning UAV assignments and final locations whenever full coverage is achievable within T.

2) Binary search over feasible deadlines:

The approximation scheme searches between lower and upper deployment-delay bounds, using feasibility checks to locate the smallest feasible deadline. Its returned delay is within a factor 1 + ϵ of optimum.

  • Binary search evaluates candidate deadlines by combining the feasibility checker with a bounded search interval.
  • The search uses lower and upper bounds Tl and Tu, with accuracy set to ϵ · Tl.
  • The search stops at the transition from an infeasible deadline to a feasible deadline, selecting the latter as the approximation.
  • The FPTAS runs in O(n^2 log(1/ϵ)) time, with relative error determined by the binary-search constant ϵ.
  • The resulting deployment delay satisfies T* < T ≤ (1 + ϵ)T* and therefore has approximation ratio 1 + ϵ over the global optimum.

V. TOTAL UAV DEPLOYMENT DELAY OPTIMIZATION

The min-sum deployment problem minimizes the total delay of selected UAVs covering the target interval and is NP-complete when UAVs start from different locations. For a common starting location, a greedy algorithm is optimal under homogeneous speed and altitude, while heterogeneity yields a linear-time approximation with a bounded factor.

  • General problem: The total deployment delay minimization problem is NP-complete when UAVs are dispatched from different locations.The hardness result is established by reduction from 3-partition.
  • Same-location deployment: For a common initial location, Algorithm 4 sequentially deploys the available UAV with the longest coverage radius to the furthest point of the remaining uncovered interval.The algorithm updates the covered interval, accumulates each selected UAV’s travel time, and may use only a subset of UAVs.
  • Same-location deployment: Algorithm 4 optimally solves min-sum deployment when all UAVs share the same flying speed and operating altitude.Its linear-time implementation follows from at most n iterations of the main loop.
  • Approximation guarantee: O(n) Algorithm 4 achieves total delay Γ ≤ κτΓ∗, where κ = hmax/hmin and τ = vmax/vmin, for heterogeneous UAVs from one location.The bound compares the algorithm with the optimal heterogeneous total delay.
  • Limitation: The approximation gap can become large when operating altitudes or flying speeds have high variance, despite the algorithm’s low computational time.The paper recommends a pseudo-polynomial method for better performance in the more general setting.

B. Reformulation of Problem (5) and bound analysis

The general min-sum problem is reformulated under an order-preserving deployment constraint. A min-max FPTAS provides an n(1 + ε)-approximation for min-sum, while the resulting dynamic-programming formulation supports a complementary n-approximation for min-max.

  • Order-preserving reformulation: The reformulation preserves the initial UAV location order, x1 ≤ ··· ≤ xn, to make the general min-sum analysis tractable.Even with order preservation, factorially many solution combinations remain possible.
  • Objective: The min-sum objective coordinates the sum of deployment delays of selected UAVs, unlike min-max optimization, which focuses on the largest delay.Identical deadlines for all UAVs do not provide a satisfactory solution for min-sum.
  • Approximation transfer: Algorithm 3, originally targeting min-max, produces a value Γ′ that approximately minimizes the total delay in the reformulated min-sum problem.Γ′ is the sum of the UAV delays returned by Algorithm 3.
  • Approximation bounds: The min-max solution obtained by Algorithm 3 achieves an n(1 + ε)-approximation for min-sum, while the optimal min-sum solution gives an n-approximation for min-max.These bounds relate the two optimization objectives under the order-preserving constraint.

C. Dynamic programming for solving problem (11)

The paper solves the order-preserving min-sum problem with dynamic programming over UAV prefixes and total delay budgets. Each state records the longest left-aligned interval covered, and Algorithm 5 returns an optimum in pseudo-polynomial time.

  • State definition: The dynamic program defines R(i, j) as the longest left-aligned interval covered by the leftmost i UAVs within total delay j.The recurrence considers whether UAV µi is unused or assigned a feasible time budget t.
  • State transition: For each UAV and time budget, the recurrence evaluates whether deployment extends coverage through the UAV’s movement and wireless radius.Three placement cases determine whether the interval is unchanged, seamlessly extended from the current boundary, or extended to a rightmost feasible position.
  • Case 2: Case 2 extends coverage seamlessly from R(i −1, j −t) to R′ = R(i −1, j −t) + 2ri when the UAV can bridge the existing boundary.The new UAV position is set to (R(i −1, j −t) + ri, hi).
  • Case 3: Case 3 extends coverage to R′ = min{xi + ri + p∆(i,t), R(i −1, j −t) + 2ri} and places the UAV at (R′ −ri, hi).The update is retained only if it improves the interval already covered by the first i−1 UAVs.
  • Guarantee and complexity: Algorithm 5 returns the optimum of problem (11) in pseudo-polynomial time.The table entries are computed in constant time, but the delay bound Γu need not be polynomial in n.
  • Cross-objective result: Algorithm 5 also achieves an n-approximation for the min-max problem.This follows from the relationship between the two optimization formulations.

VI. PERFORMANCE EVALUATION

Simulations evaluate deployment algorithms for minimizing maximum and total deployment delay under heterogeneous UAV settings. Results show benefits from greater UAV speed, coverage radius, and fleet size, while min-max and min-sum objectives involve a deployment-delay trade-off.

  • 1000 runs per algorithm provide the reported simulation averages under randomly generated UAV parameters and default target settings.
  • Min-max deployment delay: Increasing flying speed or coverage radius decreases deployment delay by reducing the distance or time needed to cover the target interval.
  • Min-max deployment delay: Increasing the number of UAVs decreases deployment delay through greater UAV diversity, with the improvement eventually converging.
  • Min-max deployment delay: Smaller relative error ε requires greater running time, while observed growth with UAV count is smaller than the theoretical O(n^2) bound.
  • Min-max deployment delay: The FPTAS obtains a close deployment delay to the optimal Brute-Force result, and its gap does not necessarily increase with the number of UAVs.
  • Min-sum deployment delay: For min-sum deployment, increasing speed or altitude variance increases delay, while increasing UAV count decreases it through greater diversity.
  • Min-sum deployment delay: Algorithm 5 achieves lower total deployment delays than Algorithm 3 but requires more computational time because it uses a pseudo-polynomial algorithm.
  • Objective trade-offs: Min-max optimization can significantly increase total deployment delay, while min-sum optimization can significantly increase maximum deployment delay.

VII. 2D EXTENSION FOR DEPLOYMENT ALGORITHMS

The paper extends its deployment model from a line to two-dimensional ground areas by incorporating UAV initial positions and coverage over rectangular regions. The extension uses approximations and yields an FPTAS for the generalized min-max problem, with polynomial runtime under identical coverage radii.

  • Model extension: The 2D extension adds a z-axis to UAV initial positions and deploys each UAV from (x_i, z_i, 0) to (y_i, 0, h_i).
  • Model extension: Each UAV’s travel time is based on its Euclidean travel distance and flying speed, while its final coverage region must collectively cover the target area.
  • Complexity: The generalized 2D coverage problem is NP-complete because the corresponding line-interval min-max and min-sum problems are NP-complete.
  • Model extension: Full coverage in a 2D area is generally difficult because UAV coverage regions are non-uniform disks, and static circle packing does not minimize deployment travel time.
  • Min-max deployment: For identical coverage radii, the 2D min-max algorithm grids the rectangular area and sequentially assigns UAVs to cover remaining squares.
  • Min-max deployment: Preserving initial location order enables decomposition into subproblems and supports a 2D deployment FPTAS obtained by combining Algorithm 6 with binary search.
  • Min-max deployment: The 2D deployment algorithm has O(n^3) runtime, yielding an FPTAS with complexity O(n^3 log 1/ε).

2) Different coverage radius:

The paper addresses heterogeneous UAV coverage when UAVs have different parameters, evaluates a 2D deployment algorithm against brute force, and develops approximation and dynamic-programming approaches for deployment-delay objectives.

  • Heterogeneous UAVs differ in flying speed, operating altitude, and wireless coverage radius, complicating full-area deployment.
  • The performance gap between the 2D deployment algorithm and brute force is small when coverage-radius variance is small.
  • The gap enlarges as coverage-radius variance increases because the 2D algorithm treats all UAVs identically.
  • The maximum delay decreases as the number of UAVs or the target-area parameter N increases.

APPENDIX A

The appendix proves NP-completeness of the min-max deployment problem by reducing 3-partition to deployment feasibility, then proves an O(n^2) algorithm optimal for UAVs dispatched from one location.

  • NP-completeness proof: The reduction transforms an arbitrary 3-partition instance into a deployment-feasibility instance with a deadline K.The constructed instance uses UAV groups whose coverage must fill the target interval without overlap.
  • NP-completeness proof: Conversely, any feasible deployment within deadline K induces a corresponding 3-partition, establishing NP-completeness.Feasibility can be verified in polynomial time.
  • NP-completeness proof: A 3-partition into m triples summing to B yields a deployment covering the target interval with maximum delay K.
  • Optimal algorithm: Algorithm 1 repeatedly selects the available UAV with minimum travel time for covering the furthest remaining target point.The proof uses exchange arguments to show that rearranging an optimal sequence to follow these choices does not increase maximum delay.
  • Optimal algorithm: Algorithm 1 is optimal and runs in O(n^2) time when UAVs are dispatched from the same location.

APPENDIX C

The appendix establishes an O(n^2) feasibility procedure for the min-max setting, proves min-sum deployment feasibility NP-complete, and uses exchange reasoning to order same-location UAVs by coverage radius.

  • Min-max feasibility: The min-max feasibility algorithm maintains the longest continuously covered interval and updates it across UAVs in O(n^2) time.The proof shows both that feasible outputs cover the interval and that infeasible outputs cannot be extended further.
  • Min-sum NP-completeness: For min-sum feasibility, the reduction from 3-partition constructs two UAV groups whose total deployment delay is bounded by K.The second group remains stationary because moving any such UAV by distance 1 incurs delay K + 1.
  • Min-sum NP-completeness: The total-delay feasibility problem is NP-complete by the reduction from 3-partition.
  • Min-sum NP-completeness: A valid 3-partition produces a full-coverage deployment whose total delay is at most K, while the converse recovers a 3-partition.
  • Same-location ordering: When UAVs start from one location with identical speeds and altitudes, swapping a larger-radius UAV farther right reduces travel distance and total delay.
Loading 1710.05616v2…