MLDR: An O(|V|/4) and Near-Optimal Routing Scheme for LEO Mega-Constellations

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.