TL;DR
This paper applies the classic Gale-Shapley "stable marriage" algorithm to optimize connections between High Altitude Platforms (HAPs) and Unmanned Aerial Vehicles (UAVs) in next-generation integrated networks. By factoring in both signal path loss and ground-user density, the proposed approach ensures stable, efficient relay communication that significantly outperforms random assignment.
What Problem Does This Paper Address?
Next-generation communication frameworks are moving beyond purely terrestrial infrastructure to embrace Space-Air-Ground Integrated Networks (SAGIN). This architecture layers Low Earth Orbit (LEO) satellites, High Altitude Platforms (HAPs), and Unmanned Aerial Vehicles (UAVs) to provide high-speed, widespread coverage via millimeter-wave (mmWave) communications.
However, managing the links between these moving aerial layers is highly challenging. UAVs move rapidly, and the long distances between UAVs and HAPs lead to severe path loss. Furthermore, HAPs must intelligently decide which UAVs to connect with to maximize service to ground users while minimizing power consumption. This paper addresses the core optimization problem: how do we dynamically and stably pair HAPs and UAVs in a complex, multi-layered network?
Methods
The authors frame the HAP-UAV pairing problem as a two-sided matching market and solve it using the Nobel Prize-winning Gale-Shapley algorithm.
- Preference Lists: Both sides of the network establish preferences based on specific criteria. HAPs prefer UAVs that exhibit lower path loss (closer distance) and serve a higher number of ground users. Conversely, UAVs prioritize HAPs that offer the lowest path loss.
- The Matching Process: Unmatched HAP antennas propose to their most-preferred UAVs. If a UAV is free, it accepts. If it is already paired, it compares the new proposal to its current partner. If the new HAP offers a better link, the UAV switches, breaking the old tie. This iterative process continues until a "stable matching" is reached—meaning no HAP and UAV would mutually prefer to break their current assignments to pair with each other.
- Communication Modeling: The matching incorporates a realistic urban communication model accounting for Free Space Path Loss (FSPL), atmospheric gas attenuation, shadow fading, and clutter loss based on 3GPP standards.
Datasets
No real-world datasets were used in this study. The evaluation relies entirely on simulated environments generated using standard parameters for Non-Terrestrial Networks (NTN).
Key Insights and Ideas
- Dual-Criteria Optimization: Rather than just looking at geometric distance, the algorithm balances physical channel quality with network utility (the number of ground users served). This prevents high-capacity UAV nodes from being ignored due to minor distance disadvantages.
- Guaranteed Stability for Dynamic Networks: Applying Gale-Shapley to SAGIN provides a mathematical guarantee of stability. In highly dynamic aerial networks, preventing constant connection "churning" (unstable re-linking) is crucial for maintaining continuous backhaul communication.
Key Results
The authors simulated a network of 100 to 500 HAPs (operating at an altitude of 18–22 km) and 500 to 2500 UAVs (operating at 50–350 m). Each HAP was equipped with five antennas, allowing for a maximum of 2500 possible matches.
- Evaluation Score: The authors devised a custom score indicator where a lower score represents a superior match (low path loss + high user coverage).
- Performance Superiority: The Gale-Shapley algorithm consistently achieved lower (better) average evaluation scores (~40–42) compared to random matching (~44–48) across all test cases.
- Scalability: As the number of UAVs scaled up to 2500, the performance gap between the proposed algorithm and random matching remained stable and significant, demonstrating that the algorithm holds up well under dense network conditions.
Limitations and Future Work
- Simplified Interference: The current model does not fully account for co-channel interference between multiple antennas mounted on the same HAP.
- Static Snapshots: The simulation evaluates a static snapshot of the network; it does not explicitly track real-time continuous mobility and handovers over an extended duration.
- Future Directions: The authors explicitly state plans to incorporate antenna interference constraints and dynamic bandwidth allocation between ground users and UAVs in future work.
Summary updated