PaperlayerView exact revision on arXiv

Source-linked AI summary

Wireless Communication using Unmanned Aerial Vehicles (UAVs): Optimal Transport Theory for Hover Time Optimization

Mohammad Mozaffari, Walid Saad, Mehdi Bennis, Merouane Debbah

arXiv:1704.04813v1cs.IT

TL;DR

The paper studies how flight-time-constrained UAV base stations can serve spatially distributed ground users efficiently and fairly. It uses optimal transport-based cell partitioning, together with bandwidth allocation, to maximize fair data service or minimize hover time under user loads. The proposed approach improves fairness over weighted Voronoi partitioning, reduces average hover time by 64% in the second scenario, and exposes a hover-time–bandwidth-efficiency tradeoff.

  • Problem

    The paper addresses UAV wireless service optimization when hover time is constrained and users have arbitrary spatial distributions.

  • Method

    The paper applies optimal transport theory to derive cell partitions and combines them with optimal bandwidth allocation for two hover-time and load-constrained scenarios.

  • Results

    The proposed partitioning provides higher user fairness than classical weighted Voronoi partitioning and reduces average hover time by 64% in the second scenario.

  • Takeaways & Limitations

    The results identify an inherent tradeoff between UAV hover time and bandwidth efficiency while servicing ground users.

Abstract

from arXiv · show

In this paper, the effective use of flight-time constrained unmanned aerial vehicles (UAVs) as flying base stations that can provide wireless service to ground users is investigated. In particular, a novel framework for optimizing the performance of such UAV-based wireless systems in terms of the average number of bits (data service) transmitted to users as well as UAVs' hover duration (i.e. flight time) is proposed. In the considered model, UAVs hover over a given geographical area to serve ground users that are distributed within the area based on an arbitrary spatial distribution function. In this case, two practical scenarios are considered. In the first scenario, based on the maximum possible hover times of UAVs, the average data service delivered to the users under a fair resource allocation scheme is maximized by finding the optimal cell partitions associated to the UAVs. Using the mathematical framework of optimal transport theory, a gradient-based algorithm is proposed for optimally partitioning the geographical area based on the users' distribution, hover times, and locations of the UAVs. In the second scenario, given the load requirements of ground users, the minimum average hover time that the UAVs need for completely servicing their ground users is derived. To this end, first, an optimal bandwidth allocation scheme for serving the users is proposed. Then, given this optimal bandwidth allocation, the optimal cell partitions associated with the UAVs are derived by exploiting the optimal transport theory. Results show that our proposed cell partitioning approach leads to a significantly higher fairness among the users compared to the classical weighted Voronoi diagram. In addition, our results reveal an inherent tradeoff between the hover time of UAVs and bandwidth efficiency while serving the ground users.

I. INTRODUCTION

The paper addresses flight-time-constrained UAV wireless communication by developing a framework for optimizing data service and hover duration. It considers fair data maximization under maximum hover times and minimum hover time for meeting user loads.

  • Motivation: UAVs can provide connectivity in poorly covered areas and support coverage expansion, capacity enhancement, hotspots, emergencies, and public safety.Their mobility, flexibility, adaptive altitude, and potential for line-of-sight links support these applications.
  • Motivation: Flight time is a central design challenge because hover duration affects service and is limited by onboard energy and flight regulations.Higher hover time can support higher loads and larger service areas, but UAVs cannot remain airborne indefinitely.
  • Research gap: Prior UAV studies generally did not consider hover time constraints in their analysis.Related work also includes limitations involving uniform user distributions, fairness, and flight-time-insensitive cell partitioning.
  • Contributions: The paper uses optimal transport theory and a gradient-based algorithm to partition geographical areas according to user distributions, UAV hover times, and locations.It also introduces optimal bandwidth allocation and cell partitions for minimizing average hover time under user load requirements.
  • Results: The proposed partitioning yields significantly higher user fairness than classical weighted Voronoi partitioning, while the second scenario reduces average hover time by 64%.The results also reveal a tradeoff between UAV hover time and bandwidth efficiency.

II. SYSTEM MODEL

The system models multiple UAVs as aerial base stations serving users distributed over a geographical area. It defines cell assignments, hover and transmission times, bandwidth resources, and two optimization scenarios.

  • Wireless assumptions: The model assumes downlink FDMA, with each UAV characterized by a three-dimensional location, maximum transmit power, and total available bandwidth.The UAV coordinates include horizontal position and altitude.
  • System setup: Users are distributed over a geographical area according to an arbitrary spatial distribution, and each disjoint cell partition is assigned to one UAV.Users in partition Ai connect to UAV i.
  • Time model: Each UAV’s hover time includes effective data transmission and control time for connections, computations, and signaling.Control time depends on the number of users in the associated partition and increases as that number grows.
  • Service model: Data service is the number of bits transmitted to a user and depends on effective transmission time, bandwidth, user location, and serving UAV.Effective transmission time and bandwidth are treated as service resources.
  • Optimization scenarios: Scenario 1 maximizes fair average data service under maximum hover times, whereas Scenario 2 minimizes average hover time while completely meeting user load requirements.The second scenario is motivated by resource-limited and emergency-service settings.

A. Air-to-ground path loss model

The air-to-ground model represents propagation through probabilistic line-of-sight and non-line-of-sight links. It uses path loss, received power, interference, SINR, bandwidth, and effective transmission time to characterize user service.

  • Propagation model: The model accounts for uncertainty in LoS and NLoS links when exact obstacle information is unavailable.LoS probability depends on obstacle characteristics and the elevation angle between each UAV and served user.
  • Path loss: Average path loss combines LoS and NLoS attenuation factors under the ITU-R probabilistic path loss model.The model uses carrier frequency, speed of light, reference distance, and UAV-user distance in its propagation formulation.
  • Interference: The received SINR includes interference from all other UAVs, scaled by an interference weight β between 0 and 1.β = 1 represents full interference and β = 0 represents an interference-free case.
  • Service calculation: User throughput is determined from allocated bandwidth and received SINR, while total data service additionally depends on the UAV’s effective transmission time.The resulting service depends on the user location, serving UAV, bandwidth allocation, and transmission duration.

III. SCENARIO 1: OPTIMAL CELL PARTITIONING FOR DATA SERVICE MAXIMIZATION WITH FAIR RESOURCE ALLOCATION

Scenario 1 optimizes UAV cell partitions to maximize average data service under fair resource allocation and fixed hover times. The formulation accounts for user density, UAV resources, connectivity, and geometric partition constraints.

  • Objective: The objective is to maximize average data service while ensuring resources are equally shared among users.This avoids unbalanced partitions and is intended to improve fairness over classical Voronoi partitioning.
  • Fairness rationale: Classical partitioning can create congested cells because it does not account for user spatial distribution, producing unfair data service.The proposed approach incorporates user distribution while maximizing total data service.
  • Fair allocation: Fair partition loads depend on UAV resources, so UAVs with more bandwidth and hover time serve more users.When UAVs have identical resources, the generated partitions have equal user loads.
  • Constraints: The optimization assigns each location to a feasible UAV while requiring disjoint cells whose union covers the target area.Connectivity and cell-load constraints are included in the formulation.
  • Solution approach: The continuous, mutually dependent partition variables and generic user-density integrations make the optimization challenging.The paper addresses this difficulty by modeling the problem with optimal transport theory.

A. Optimal Transport Theory: Preliminaries

Optimal transport formulates the matching of user and UAV distributions as a minimum-cost transport problem. The Monge–Kantorovich relaxation and its dual provide a tractable framework for deriving optimal mappings and cell partitions.

  • Optimal transport formulation: Optimal transport finds a minimum-cost map matching two probability distributions over source and destination spaces.The transport cost c(x,T(x)) measures moving unit mass from x to T(x).
  • Monge–Kantorovich relaxation: Monge’s formulation is difficult because of its nonlinear structure and possible nonexistence of a map satisfying the one-destination constraint.Each source point must map to only one destination location.
  • Monge–Kantorovich relaxation: The Monge–Kantorovich relaxation replaces transport maps with plans, allowing one source point to serve multiple destination points.The transport plan π is a probability distribution on X × Y with marginals f1 and f2.
  • Kantorovich duality: The relaxed problem admits solutions for semi-continuous costs and has a dual formulation that can yield tractable solutions.The paper uses Kantorovich duality to address its optimization problem.
  • Application to UAV cells: The UAV partitioning problem is modeled as semi-discrete transport, with a continuous user measure and discrete UAV locations.The resulting transport map assigns users to UAV-associated cells.

B. Optimal Cell Partitioning

The paper converts optimal UAV cell partitioning into a finite-dimensional concave optimization over Kantorovich potentials. A gradient-based method then obtains the potentials and corresponding partitions from user distributions, UAV locations, hover times, and bandwidth-related costs.

  • Problem formulation: The continuous user-to-UAV partitioning problem is represented as semi-discrete optimal transport with a continuous source and discrete UAV destinations.The transport cost combines control time qi(x,y) and rate-dependent service cost −λlog2(1 + γi(x,y)).
  • Dual optimization: Theorem 1 transforms the complex partitioning problem into a tractable optimization problem with M variables.The optimal values of ψi determine the associated cell partitions.
  • Dual optimization: Theorem 2 establishes that the dual objective F is concave in the vector of potential variables ψT.The optimal potentials can therefore be obtained by maximizing F.
  • Algorithm: A gradient-based algorithm finds the optimal potential vector without computing the Hessian matrix.The approach is adopted because the second derivative of F is challenging to obtain.
  • Objective: The resulting framework maximizes average data service while incorporating fairness through optimal UAV-associated cell partitions.The partitions are determined using the optimal-transport formulation and the user distribution.

IV. SCENARIO 2: MINIMUM HOVER TIME FOR MEETING LOAD REQUIREMENTS

Scenario 2 minimizes UAV hover time while meeting users’ load requirements. Optimal bandwidth allocation yields the hover-time expression, and optimal transport then determines partitions and an iterative solution for the coupled problem.

  • Objective: The scenario seeks to meet ground-user load requirements while minimizing the average hover time of the UAVs.The method first derives minimum hover time under optimal bandwidth allocation.
  • Bandwidth allocation: Under a fixed cell partition, optimal bandwidth allocation minimizes the maximum user service time plus the partition’s control time.The hover time accounts for sequential service and additional control time.
  • Hover-time behavior: Hover time increases with user count, user load, and density, while increasing transmission rate can reduce it.For equal user loads, the increase with load is sublinear because control time does not depend on load.
  • Optimal transport reformulation: The partition optimization is difficult because the cell sets are mutually dependent and control time is a generic function of each partition.The paper notes that the problem is intractable in its direct form.
  • Optimal solution: Theorem 3 characterizes the optimal hover times and partitions, minimizing the average hover time required to serve the target area.The theorem supports finding both optimal cell partitions and minimum hover time.
  • Iterative solution: An iterative algorithm solves the coupled partition and hover-time problem, with convergence to the optimal solution and linear complexity in the area size.The algorithm updates partitions and hover times over iterations.

V. SIMULATION RESULTS AND ANALYSIS

The simulations model users in a 1000 m × 1000 m area using a truncated Gaussian hotspot distribution and grid-deployed UAVs. Results are averaged over many independent runs and compared with the classical weighted Voronoi baseline.

  • Simulation setup: Simulations use a rectangular area of size 1000 m × 1000 m with ground users distributed according to a two-dimensional truncated Gaussian.The distribution models a hotspot area and is parameterized by coordinate means and standard deviations.
  • User distribution: The Gaussian hotspot uses equal coordinate standard deviations, σx = σy = σo, while the analysis can accommodate arbitrary user distributions.The hotspot center is represented by (µx, µy).
  • Deployment and interference: UAVs are deployed on a grid at an altitude of 200 m, with full interference modeled using β = 1 unless otherwise stated.The control-time function is gi(Nai) = α(Nai)2.
  • Control time: The control-time function is superlinear in the number of users and can be scaled by α, while arbitrary continuous control-time functions are also allowed.The simulations use gi(Nai) = α(Nai)2 as a reasonable model choice.
  • Evaluation: The proposed optimal cell partitioning approach is compared with the classical weighted Voronoi diagram using averages over many independent runs.Results are presented separately for Scenario 1 and Scenario 2.

A. Results for Scenario 1

Scenario 1 optimizes cell partitions to maximize fair average data service under UAV hover-time limits. Compared with weighted Voronoi partitions, the proposed approach produces more balanced service and benefits more from reduced interference and longer hover times.

  • The proposed optimal cell partitions maximize average data service under a fair resource allocation constraint.
  • With five UAVs and non-uniform users, the proposed partitions keep Jain’s fairness index above 0.5, whereas weighted Voronoi fairness can fall to 0.18 at σo = 200 m.
  • Equal UAV bandwidth and hover times produce equal user counts per proposed cell, avoiding the unbalanced partitions of the classical Voronoi approach.
  • Reducing the interference factor β from 1 to 0.1 increases total data service threefold with five UAVs.
  • Increasing UAVs from 5 to 10 yields a 56% data-service gain at β = 0.1 but only 5% under full interference.
  • Five UAVs with 40-minute hover times outperform ten UAVs with 30-minute hover times, making longer-flight UAVs preferable in this case.

B. Results for Scenario 2

Scenario 2 minimizes the hover time required to fully serve users through optimal bandwidth allocation and cell partitioning. The results show reductions in hover time, but also a tradeoff between hover time, bandwidth usage, control time, and interference.

  • Optimal bandwidth allocation reduces hover time by providing higher transmission rates than equal bandwidth allocation.
  • The optimal bandwidth allocation scheme yields a 51% hover-time reduction compared with equal bandwidth allocation.
  • Increasing the number of UAVs from 2 to 6 decreases total hover time by 53% in the interference-free scenario, while total bandwidth usage increases linearly.
  • The results reveal a tradeoff between hover time and bandwidth efficiency, while interference increases hover time by lowering transmission rates.
  • The proposed cell partitioning reduces average total hover time by around 20% versus weighted Voronoi, reaching around 32% reduction when α = 0.5.

VI. CONCLUSIONS

The paper develops an optimal-transport framework for two UAV service scenarios: maximizing fair data service under hover-time limits and minimizing hover time under user-load requirements.

  • Framework: The framework accounts for UAV flight-time constraints while optimizing wireless service and hover duration.It targets UAV-enabled wireless networks serving users distributed over a geographical area.
  • Scenario 1: Given maximum UAV hover times, the method maximizes average data service under fair resource allocation by optimizing UAV cell partitions.Optimal transport theory is used to determine the partitions associated with the UAVs.
  • Scenario 2: Given user load requirements, the method minimizes the average hover time required to completely serve users.This scenario jointly derives optimal cell partitions and bandwidth allocation.
  • Results: The proposed partitioning provides higher fair data service to users than the classical Voronoi case.The comparison concerns fairness in the delivered data service.
  • Results: The second scenario shows that UAV average hover time can be significantly reduced using the proposed approach.The cited conclusion reports a reduction but does not specify its magnitude here.

APPENDIX

The appendix characterizes optimal cell partitions through local variation arguments, assignment conditions, and the resulting hover-time expression.

  • Optimal partitions: Proposition 2 states that optimal cell partitions exist as solutions to the optimization problem.The appendix then analyzes variations of optimal partitions to establish their characterization.
  • Optimality argument: The proof constructs perturbed partitions by moving a small neighborhood between two cells and uses optimality to constrain the variation.The perturbation is defined around a point in one partition using a disk of radius ε.
  • Assignment condition: The derived condition determines when a point is assigned to partition m and compares assignments between candidate cells.This condition is used to characterize the optimal cell boundaries.
  • Hover time: Using the established partition characterization, the appendix derives the optimal average hover time of each UAV and concludes the proof.The final expression follows from an earlier relation in the paper.
Loading 1704.04813v1…