An Algorithm Design of Inter-satellite Routing Based on Fibonacci Heap

摘要

As the satellites are limited by the deficient hardware resources and the difficulty of upgrading, the application of inter-satellite dynamic routing has been restricted. Meanwhile, the rapid changes of the satellites dynamic network topology caused by satellites' high-speed movement require a highly efficient static routing algorithm. By fully considering the characteristics of sparse edges of the satellite network, an inter-satellite routing algorithm obtaining a good time boundary is analyzed and proposed in this paper based on Fibonacci heap. Firstly, this paper introduces an inter-satellite network topology by using walk constellation and describes the network with the nod-arc-directed line mode. Further, to improve the Dijkstra algorithm, a method implementing the priority queue whose node value can be decreased is proposed. By analyzing the complexity of the algorithm and comparing different simulation results, this paper proves that the remarkable improvement in the conveniences and efficiency for the inter-satellite routing can be achieved through Dijkstra algorithm by using Fibonacci heap structure.