| 摘要: |
| 由于卫星星上处理以及存储能力有限，随着卫星网络的规模越来越庞大，迫切需要一种简单高效的路由算法。为此，提出了一种基于网络拥塞程度感知的路由策略(Network Congestion-Aware Routing Algorithm，NCARA)。NCARA路由策略在网络处于非拥塞状态时采用Dijkstra算法寻路，网络拥塞时换用改进广度优先搜索算法(Enhance Breadth First Search，en-BFS)寻找最短路径。en-BFS算法利用卫星网络拓扑呈二维网格拓扑的特征，将最小跳数作为主要衡量指标，选出最小跳数路径集合；然后将传输时延和传播时延作为衡量标准，以O(V+E)（V为图的节点个数，E为图的边的数目）的时间复杂度在最小跳数集合中选择出最小权值路径。最后通过数学方法证明了算法的正确性以及有效性。仿真结果表明，所提路由算法的平均时延、丢包率等都与传统算法相当，但是算法复杂度却得到极大的降低。 |
| 关键词: LEO卫星网络 网络拥塞程度感知 广度优先搜索 最短路径 路由算法 |
| DOI： |
|
| 基金项目:长江学者和创新团队发展计划(IRT_16R72) |
|
| An efficient routing algorithm for LEO satellite networks |
| LEI Yuanjie,TANG Hong,MA Shuqing,LI Yi |
| (a.School of Communication and Information Engineering;b.Chongqing Key Laboratory of Mobile Communications Technology,Chongqing University of Posts and Communications,Chongqing 400065,China) |
| Abstract: |
| Due to the limited on-satellite processing and storage capacity,there is an urgent need for a simple and efficient routing algorithm as satellite networks become larger and larger.A network congestion-aware routing algorithm(NCARA) is proposed to solve the above problem.The NCARA routing policy adopts Dijkstra algorithm to find the shortest path when the network is uncongested and switches to Enhance Breadth First Search(en-BFS) to find the shortest path when the network is congested.en-BFS algorithm takes advantage of the fact that the satellite network topology is a two-dimensional grid topology.The minimum number of hops is used as the main measure to select the set of minimum-weighted paths.The transmission delay and propagation delay are used as the measures to select the minimum-weighted path from the set of minimum-weighted paths with the time complexity of O(V+E)，where V is the node number of graph and E is the edge number of graph.The correctness and effectiveness of the algorithm are proved by mathematical methods.The simulation results show that the average delay and packet loss rate of the proposed routing algorithm are comparable to those of the traditional algorithm,but the complexity is greatly reduced. |
| Key words: LEO satellite network network uncongested level awareness breadth first search shortest path routing algorithm |
