Time-Varying Graph and Binary Tree Search Based Routing Algorithm for LEO Satellite Networks

Though low earth orbit (LEO) satellite networks have superiorities in short delay, wide coverage and flexible networking, the end-to-end (E2E) transmission has been confronted with severe challenges due to frequent changes of network topology. In this article, a time-varying graph and binary tree search based routing algorithm for LEO satellite networks is proposed to reduce the E2E transmission delay and improve the network quality of service. Firstly, a coordinate graph (CG) model is adopted to characterize the topology structure and resource distribution of LEO satellite networks. Then, an E2E minimum-hop area is determined based on CG model, so that a minimum-hop binary tree (MHBT) is constructed. Finally, the pruning traversal of MHBT is performed to obtain all minimum-hop paths, based on which the E2E path with the shortest delay is determined. Simulation results show that the proposed routing algorithm not only reduces the path delay, but also improves the file delivery ratio.