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.

    Source: §I · p. 2

  • 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.

    Source: §I · pp. 3–4

  • 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.

    Source: §I · pp. 3–4

  • Takeaways & Limitations

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

    Source: §I · pp. 3–4

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

    Source: §I · p. 2, §II · p. 5

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.Source: §I · p. 2

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.Source: §I · p. 3
  • 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.Source: §I · p. 3

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.Source: §I · pp. 3–4
  • 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.Source: §I · p. 4

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.Source: §I · p. 4

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.Source: §II · pp. 4–5
  • Recent sensor-network studies consider maximum or total deployment movement, but their methods cannot apply directly to fast UAV deployment.Source: §II · p. 5
  • UAV deployment differs from sensor deployment because UAVs must operate in the air with heterogeneous altitudes, flying speeds, and coverage radii.Source: §II · p. 5, §III · p. 9
  • The paper formulates full wireless coverage of a target area using diverse UAVs that travel to final positions and hover at operating altitudes.Source: §III · pp. 5–7
  • The target area is reduced to a line interval for theoretical analysis, and both deployment problems are shown to be NP-complete.Source: §III · pp. 8–9

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.

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.

1) Feasibility checking problem

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.

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.Source: §V · p. 15

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.Source: A. Fast algorithm for UAVs deployment… · pp. 16–17
  • 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.Source: A. Fast algorithm for UAVs deployment… · pp. 17–18

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.Source: A. Fast algorithm for UAVs deployment… · p. 17

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.Source: A. Fast algorithm for UAVs deployment… · p. 18

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.Source: B. Reformulation of Problem (5) and… · pp. 18–19

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.Source: B. Reformulation of Problem (5) and… · p. 19

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.Source: B. Reformulation of Problem (5) and… · p. 19

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.Source: B. Reformulation of Problem (5) and… · pp. 19–20

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.Source: C. Dynamic programming for solving… · p. 20

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.Source: C. Dynamic programming for solving… · p. 20

Case 2

Case 3

Guarantee and complexity

Cross-objective result

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.Source: §VI · p. 23

Min-max deployment delay

Min-sum deployment delay

Objective trade-offs

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

Complexity

Model extension

Min-max deployment

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.

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.Source: Appendix A · pp. 39–40
  • Conversely, any feasible deployment within deadline K induces a corresponding 3-partition, establishing NP-completeness.Feasibility can be verified in polynomial time.Source: Appendix A · pp. 40–41
  • A 3-partition into m triples summing to B yields a deployment covering the target interval with maximum delay K.Source: Appendix A · p. 40

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.Source: Appendix B · p. 42
  • Algorithm 1 is optimal and runs in O(n^2) time when UAVs are dispatched from the same location.Source: Appendix B · p. 42

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.Source: Appendix C · p. 43

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.Source: Appendix D · pp. 43–44
  • The total-delay feasibility problem is NP-complete by the reduction from 3-partition.Source: Appendix D · pp. 43–44
  • A valid 3-partition produces a full-coverage deployment whose total delay is at most K, while the converse recovers a 3-partition.Source: Appendix D · p. 44

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.Source: Appendix E · p. 45

Related papers

Loading 1710.05616v2…