Optimal Placement of UAVs for Minimum Outage Probability

Maryam Shabanighazikelayeh, Erdem KoyuncuIEEE Trans. Vehicular Technology 2022 · OpenReview

TL;DR

This paper tackles the problem of optimally positioning multiple drones (UAVs) to serve ground users (GTs) with the goal of minimizing communication outages. It reveals a counter-intuitive finding: for high altitudes, all drones should cluster together, suggesting a single multi-antenna drone could suffice. The authors also develop practical algorithms for finding these optimal placements.

What Problem Does This Paper Address?

In modern wireless networks, Unmanned Aerial Vehicles (UAVs) are increasingly being explored as flying base stations to enhance coverage and connectivity. A critical challenge in deploying these UAVs is determining their optimal locations to ensure reliable communication. Specifically, this paper focuses on minimizing the "outage probability," which is the likelihood that a ground user cannot establish a connection with any UAV due to signal degradation. Existing research often focuses on maximizing coverage or efficiency, but this work specifically targets outage probability, which is crucial for applications like data collection from low-power devices. The problem is complex because the optimal placement depends on the distribution of ground users, the number of UAVs, and their altitude, making it a challenging optimization problem.

Methods

The authors employ a multi-pronged approach:

  • Analytical Framework: They first derive general upper and lower bounds on the optimal outage probability. This involves using random deployment arguments and analyzing the behavior of the outage probability as the number of UAVs increases.
  • Structural Analysis: A key contribution is the analysis of the structure of optimal deployments. They investigate how the optimal locations change with UAV altitude and user density.
  • Optimization Algorithms: To find practical solutions, they develop two algorithms:
  • Centralized Particle Swarm Optimization (PSO): This algorithm assumes a central controller with complete knowledge of user density to find globally optimal UAV placements.
  • Distributed Gradient Descent: This approach is more practical, allowing each UAV to communicate with its neighbors to iteratively adjust its position, requiring only local information about user density and neighboring UAVs.
  • Fading Models: The analysis is conducted for both Rayleigh fading (representing a highly scattered environment) and a modified Rician fading model specifically designed for UAV communications, incorporating factors like elevation angle and line-of-sight probability.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulation-based evaluation using synthetic user density functions (e.g., uniform, Gaussian).

Key Insights and Ideas

  • The "Collapse" Phenomenon: Perhaps the most striking finding is that for high UAV altitudes, the optimal placement for all UAVs is to converge to a single location. This is counter-intuitive to traditional base station deployment strategies that aim for uniform coverage.
  • Single Multi-Antenna UAV vs. Multiple Single-Antenna UAVs: The "collapse" phenomenon implies that a single UAV equipped with multiple antennas could achieve the same minimum outage probability as multiple single-antenna UAVs clustered together, simplifying deployment and potentially reducing costs.
  • Exponential Decay of Outage Probability: The paper proves that the optimal outage probability decreases exponentially with the number of UAVs, a significant finding for understanding scalability.
  • Distributed Algorithm Performance: The developed distributed gradient descent algorithm performs remarkably well, achieving near-optimal results even with limited communication and sensing ranges between UAVs. This highlights its practical applicability for real-time deployment.

Key Results

  • Analytical Bounds: General upper and lower bounds on the optimal outage probability are derived, showing exponential decay with the number of UAVs.
  • Optimal Deployment Structure: For large altitudes, all UAVs converge to a single optimal location. For a single UAV, the optimal location is at the center of the user density if it's unimodal.
  • Algorithm Performance:
    • The PSO algorithm provides globally optimal or near-optimal solutions.
  • The distributed gradient descent algorithm achieves performance very close to PSO, even with reduced communication and sensing ranges. For example, in Fig. 5, the performance with reduced ranges (Ds=10m, Dc=10m) is comparable to PSO.
  • The analytical formulas for outage probability provide good approximations to simulation results, especially at higher altitudes.

Limitations and Future Work

  • General GT Densities and UAV Altitudes: The authors aim to provide better bounds for more general user densities and UAV altitudes in future work.
  • Time-Varying GT Density: The current model assumes a static user density. Future work will study the movement of UAVs according to a time-varying GT density.
  • Selection Diversity vs. Maximum Ratio Combining: The current model uses selection diversity for reception. Applying maximum ratio combining for better performance is suggested as future work.
  • Practical Deployment of Distributed Algorithms: While the distributed algorithm shows promise, further investigation into adapting communication and sensing ranges (Ds, Dc) based on UAV altitude constraints to conserve power is suggested.
  • Real-world Deployment Challenges: The paper's focus is on theoretical optimization and simulation. Real-world deployment would involve additional complexities like dynamic environments, battery life, and air traffic control.

Summary updated

Abstract

We consider multiple unmanned aerial vehicles (UAVs) serving a density of ground terminals (GTs) as base stations. The objective is to minimize the outage probability of GT-to-UAV transmissions. Optimal placement of UAVs under different UAV altitude constraints and GT densities is studied. A practical variant of the Rician fading model, which has been developed by Azari et al. (2018) specifically for UAV systems, is used to model the communication channels. First, the structure of optimal deployments is determined when the common altitude constraint is large. For a wide class of GT densities, it is shown that all UAVs should be placed to the same location in an optimal deployment. A design implication is that one can use a single multi-antenna UAV as opposed to multiple single-antenna UAVs without loss of optimality. Next, using a random deployment argument, a general upper bound on the optimal outage probability is found for any density of GTs and any number of UAVs. Further, for any arbitrary user density, centralized and distributed numerical algorithms are designed using particle swarm optimization and modified gradient descent algorithms, respectively. Simulations show that our distributed algorithm provides almost optimal results even with considerably reduced communication and sensing ranges at the UAVs.
BibTeX
@article{shabanighazikelayeh2022optimal,
  author = {Maryam Shabanighazikelayeh and Erdem Koyuncu},
  title = {{Optimal Placement of UAVs for Minimum Outage Probability}},
  journal = {IEEE Trans. Vehicular Technology},
  year = {2022},
  url = {https://openreview.net/forum?id=oXZoKhnNpn},
}
Figure