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.
inter-satellite Dijkstra shortest path Fabonacci
Yanyun Liu Wenquan Feng Hua Sun Jia Yin Zhiyuan Zheng
School of Electronic and Information Engineering BEIHANG University Beijing, China
国际会议
杭州
英文
431-434
2011-10-28（万方平台首次上网日期，不代表论文的发表时间）