A Novel Routing Algorithm for LEO Mega-Constellations

With the rapid development of space information networks and global commercial spaceflight, the deployment of low Earth orbit (LEO) mega-constellation systems using a large number of low-cost satellites to provide internet and various other services to the ground has become a significant direction for future space and communication sectors. Among these, routing technology is a crucial element to ensure the interconnection between nodes within the satellite network. However, as constellations become larger and their orbital altitudes decrease, LEO mega-constellation networks encounter issues such as complex and highly dynamic topologies, frequent transitions between satellite and ground, and node failures. Existing LEO mega-constellation routing algorithms perform poorly under conditions of Inter-SatelliteLink (ISL) failures and node failures.

A Manhattan-like topology and low intersatellite link delay-based routing scheme is a near-optimal routing scheme, but it does not consider the increased delay caused by sudden node or ISL failures during transmission. To address this challenge, an improved mega-constellation routing algorithm is proposed that maintains near-optimal routing while considering node and ISL failures during transmission, with a lower routing complexity of O(V/4), where V is the number of satellite nodes in the constellation.

Firstly, based on the source satellite, the topology of the LEO mega-constellation is divided into four interference-free areas. Secondly, the algorithm is applied to obtain near-minimum delay paths for all targets within each area under the minimum hop (MH) path. Finally, through simulation comparisons on the LEO mega-constellation, it is verified that the proposed algorithm has near-optimal routing and achieves lower complexity. Current research and this study both explore constellation routing transmission strategies at the same orbital altitude, and future research is expected to explore new routing algorithms for heterogeneous orbital mega-constellation networks.