Shortest path algorithm for satellite time-varying topological network

Satellite time-varying topological network is a special time-varying network. It is different from classical fixed topological networks and also different from time-dependent networks which have been studied. Based on proposing the model of satellite time-varying topological networks, this paper proves that the shortest path algorithm of classical fixed topological networks, such as the Dijkstra algorithm, is restrictive in satellite networks. Here, a novel shortest path algorithm for satellite time-varying topological networks is given. Further more, by analysis of the correlation between two satellite nodes, this algorithm is optimized and an improvement in complexity of algorithms is achieved. In this algorithm, by restricting the selection rule of a discrete time series, an appropriate discrete model of satellite time-varying topological networks can be obtained. By this discrete model, the communication problem of satellite networks can be successfully solved and the Dijkstra algorithm can also be applied availably in satellite communication networks. Correlative simulation indicates that this shortest path algorithm can be effectively applied to satellite communication networks. When the handover of satellite networks becomes frequently, this algorithm is superior to the dynamic virtual topology routing (DVTR) algorithm which has been widely used to compute the routing of satellite networks. Besides, an obvious improvement in the performance of packet dropped and TCP delay etc has been achieved by using this novel algorithm.