MLDR: An O(|V|/4) and Near-Optimal Routing Scheme for LEO Mega-Constellations
- 16 February 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Internet of Things Journal
- Vol. 11 (10) , 18663-18675
Abstract
Low Earth Orbit (LEO) mega-constellations enable the Internet of Things (IoT) industry to realize the vision of integrated space-air-ground-sea communication networks under B5G and 6G. However, due to the high complexity of O(|V|log|V|+|E|) of Dijkstra’s algorithm, existing LEO mega-constellations suffer from excessive routing reconvergence time under frequent topology changes caused by satellite-ground station link handovers and network failures. To this end, we propose MLDR, a Manhattan-like topology-and Low ISL Delay-based Routing scheme with an ultra-low routing complexity of O(|V|4) while maintaining near-optimal routing. Firstly, for any source satellite, MLDR divides the Manhattan-like topology of LEO mega-constellations into four non-interfering Minimum Hop (MH) areas. Secondly, MLDR concurrently and non-repeatedly computes MH paths for all destinations within each MH area and installs routing tables. Thirdly, MLDR incrementally computes and updates the MH paths by more optimal MH detour paths, which select other neighboring satellites as relaying nodes. Finally, by conducting extensive simulations on real-world LEO mega-constellations, our MLDR outperforms all state-of-the-art schemes by remarkably reducing reconvergence time and achieving the highest routing optimality.Keywords
Funding Information
- Key Research and Development Program of Shaanxi (2023-YBGY-270)
- National Key Research and Development Program of China (2022YFB2701800)
- National Natural Science Foundation of China (62125205, 61502375)
This publication has 25 references indexed in Scilit:
- Software Defined Multicast Using Segment Routing in LEO Satellite NetworksIEEE Transactions on Mobile Computing, 2022
- Coverage Enhancement of Underwater Internet of Things Using Multilevel Acoustic Communication NetworksIEEE Internet of Things Journal, 2022
- A Survey on Space-Air-Ground-Sea Integrated Network Security in 6GIEEE Communications Surveys & Tutorials, 2021
- ASER: Scalable Distributed Routing Protocol for LEO Satellite Networks2021
- A Refined Dijkstra's Algorithm with Stable Route Generation for Topology-Varying Satellite Networks2021
- A Joint Optimization Scheme for Hybrid MAC Layer in LEO Satellite Supported IoTIEEE Internet of Things Journal, 2021
- Radar–Communication Integration for 6G Massive IoT ServicesIEEE Internet of Things Journal, 2021
- Towards Energy-Efficient Routing in Satellite NetworksIEEE Journal on Selected Areas in Communications, 2016
- A formal study on topology and floorplan characteristics of mesh and torus-based optical networks-on-chipMicroprocessors and Microsystems, 2013
- Topological dynamics characterization for LEO satellite networksComputer Networks, 2007