Source-linked AI summary
Placement Optimization of UAV-Mounted Mobile Base Stations
Jiangbin Lyu, Yong Zeng, Rui Zhang, Teng Joon Lim
TL;DR
The paper addresses how to cover distributed GTs without fixed infrastructure using as few UAV-mounted MBSs as possible. It proposes a polynomial-time spiral placement algorithm that sequentially prioritizes boundary GTs while moving inward. The algorithm matches the minimum of 11 MBSs in an 80-GT example and performs favorably against benchmark schemes in broader experiments.
Problem
The problem is to cover all distributed GTs with the minimum number of MBSs, despite the general NP-hardness of geometric disk covering and limitations of strip-based partitioning.
Method
The spiral algorithm sequentially places MBSs along the perimeter of uncovered GTs, moves each placement inward, and prioritizes boundary GTs while using localized coverage optimization.
Results
11 MBSs cover the 80-GT topology at radius 0.5 km, matching the core-sets minimum and outperforming the strip-based algorithm’s 13 MBSs.
Takeaways & Limitations
The proposed polynomial-time algorithm provides near-optimal coverage for small networks and favorable MBS-count and time-complexity performance across networks of different sizes.
Abstract
from arXiv · showhide
In terrestrial communication networks without fixed infrastructure, unmanned aerial vehicle (UAV)-mounted mobile base stations (MBSs) provide an efficient solution to achieve wireless connectivity. This letter aims to minimize the number of MBSs needed to provide wireless coverage for a group of distributed ground terminals (GTs), ensuring that each GT is within the communication range of at least one MBS. We propose a polynomial-time algorithm with successive MBS placement, where the MBSs are placed sequentially starting on the area perimeter of the uncovered GTs along a spiral path towards the center, until all GTs are covered. Each MBS is placed to cover as many uncovered GTs as possible, with higher priority given to the GTs on the boundary to reduce the occurrence of outlier GTs that each may require one dedicated MBS for its coverage. Numerical results show that the proposed algorithm performs favorably compared to other schemes in terms of the total number of required MBSs and/or time complexity.
I. INTRODUCTION
The paper frames UAV-mounted MBSs as a way to provide connectivity without fixed infrastructure and proposes a spiral placement algorithm to cover distributed GTs efficiently.
- UAV-mounted MBSs can provide wireless connectivity in infrastructure-free areas such as battlefields or disaster scenes.Their mobility allows deployment at locations and along trajectories unavailable to terrestrial base stations.
- The placement problem seeks to cover all GTs while reducing the number of required MBSs.The paper formulates this setting as a geometric disk cover problem.
- The proposed algorithm places MBSs sequentially from the uncovered GTs’ perimeter inward along a spiral path.Each placement covers uncovered GTs, prioritizing boundary GTs to reduce isolated outliers.
- The algorithm has worst-case complexity O(K^3), comparable to the strip-based method and lower than the core-sets method.For small networks, it achieves near-optimal MBS counts, while averaging favorable MBS-count and time-complexity results across different network sizes.
II. SYSTEM MODEL AND PROBLEM FORMULATION
The system model assumes known GT locations, fixed-altitude UAVs, LOS-dominated channels, and a fixed ground-projected coverage radius; the objective is minimum-MBS coverage of every GT.
- The model considers K known GT locations on a two-dimensional ground plane and UAV-GT channels dominated by line-of-sight propagation.The LOS assumption makes channel quality primarily dependent on UAV-GT distance.
- The optimization deploys the minimum number of MBSs so every GT lies within communication radius r of at least one MBS.Some GTs may be covered by multiple MBSs, while subsequent interference management is outside the paper’s scope.
- The MBS placement formulation is the geometric disk cover problem, which is NP-hard in general.Each MBS corresponds to a disk of radius r covering GTs within that distance.
- The related p-center formulation searches for the smallest disk radius covering all K GTs with p centers.Increasing p until the radius is at most r yields the smallest feasible MBS count.
- The p-center problem is non-convex and NP-hard, with brute-force complexity O(p^K), making exact optimization infeasible for moderate p and K.Core-sets methods can find optimal solutions for small p, but retain exponential worst-case complexity.
III. SPIRAL MBS PLACEMENT ALGORITHM
The spiral MBS placement algorithm sequentially covers uncovered GTs from the perimeter inward, prioritizing boundary GTs while locally refining each MBS location to cover additional terminals. Its local search avoids exhaustive subset enumeration, and numerical evaluation matches the core-sets optimum while using fewer MBSs than the strip-based method.
- Spiral placement: The algorithm places MBSs sequentially along the perimeter of uncovered GTs, moving inward until all GTs are covered.The perimeter is defined by boundary GTs of the uncovered set, listed counterclockwise.
- Spiral placement: Each MBS guarantees coverage of a boundary GT and gives higher priority to boundary GTs to reduce isolated outlier terminals.After placement, the remaining perimeter shrinks locally, and the next MBS is selected counterclockwise from the next uncovered boundary GT.
- Local refinement: LocalCover first enforces coverage of prioritized GTs, then adds as many secondary GTs as possible by refining the MBS location.The exact optimization may require exhaustive search over 2^|Psec| subsets, so the proposed procedure uses possibly sub-optimal solutions for low complexity.
- Local refinement: The procedure excludes GTs more than 2r from prioritized GTs and uses a 1-center check to test whether nearby points can share one MBS.This confines the search to a local region and avoids considering GT subsets that cannot be jointly covered.
- Complexity: O(K[K log K + K · C(K)]) is the spiral algorithm’s upper-bounded computational complexity, where C(K) is the 1-center subroutine runtime.Actual runtime can be lower because far-away GTs are excluded and nearby GTs are included during local refinement.
- Numerical evaluation: 11 MBSs cover 80 GTs at r = 0.5 km, matching the core-sets minimum and improving on the strip-based method’s 13 MBSs.For the same topology, the core-sets method gives minimum coverage radii of 0.5231 km for 10 centers and 0.4829 km for 11 centers.
IV. NUMERICAL RESULTS
The numerical evaluation averages MBS counts and running times over five random topologies for networks with 80 and 400 GTs. The spiral algorithm outperforms the strip-based and two other heuristic schemes on average in both metrics.
- Evaluation setup: The evaluation uses five random topologies for each of two network sizes, K = 80 and K = 400, across different coverage radii.For each D/r ratio, required MBSs M and running time t are averaged over the five topologies.
- Comparison: The spiral algorithm outperforms the strip-based algorithm because MBSs can flexibly cover GTs across fixed-strip boundaries, reducing outliers and required MBSs.The strip-based method independently considers GTs in different strips, which can cause performance loss.
- Comparison: The spiral algorithm outperforms two other heuristic schemes on average in both required MBSs M and running time t across network sizes.The comparison covers networks of different sizes.
V. CONCLUSIONS
The letter proposes a polynomial-time spiral algorithm for successive MBS placement and reports favorable comparisons with benchmark schemes. It targets coverage of all GTs while reducing the required MBS count without the exponential complexity of the core-sets method.
- Contribution: The spiral algorithm places MBSs successively and is proposed as a polynomial-time solution for UAV-GT communications.The algorithm is termed the spiral algorithm.
- Conclusion: The method compares favorably with core-sets, strip-based, and two heuristic schemes in the minimum number of MBSs required to cover all GTs.The core-sets benchmark has exponential complexity, while the strip-based scheme has low complexity.
- Future work: Future work includes additional backhaul connectivity constraints between MBSs and adaptive placement for moving GTs.These extensions are outside the presented setting.