卫星时变拓扑网络最短路径算法研究

A Shortest Path Algorithm for Satellite Time-Varying Topological Network

在提出卫星时变拓扑网络模型的基础上,首先证明了传统网络中的最短路径算法(如Dijkstra算法)在卫星时变拓扑网络中使用存在局限性,给出了一种可适用于卫星时变拓扑网络的最短路径算法并利用卫星节点间邻居关系的相对规律性,对算法进行了优化.相关仿真表明该算法比目前常用的卫星网络路由算法(如DVTR)更适合于切换频繁的卫星网络.

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 ete has been achieved by using this novel algorithm.