An online greedy algorithm for path stretch of LEO satellite networks

In this paper, aiming at the NP-hard property of routing problems in LEO satellite networks, which include the Minimum Path Stretch Schedule (MIN-PSS), Maximum Path Contraction Schedule (MAX-PCS) and Maximum Constant Path Schedule (MAX-CPS) problems, we put forward an online greedy algorithm with the time complexity O(nlogn) to cope with the core MIN-PSS problem. The MAX-PCS and MAX-CPS problems can be solved by the similar method. The simulation results show that the proposed algorithm can effectively reduce the rate of path stretch with low computational complexity.