面向LEO卫星网络的高效路由算法

由于卫星星上处理以及存储能力有限,随着卫星网络的规模越来越庞大,迫切需要一种简单高效的路由算法。为此,提出了一种基于网络拥塞程度感知的路由策略(Network Congestion-Aware Routing Algorithm,NCARA)。NCARA路由策略在网络处于非拥塞状态时采用Dijkstra算法寻路,网络拥塞时换用改进广度优先搜索算法(Enhance Breadth First Search,en-BFS)寻找最短路径。en-BFS算法利用卫星网络拓扑呈二维网格拓扑的特征,将最小跳数作为主要衡量指标,选出最小跳数路径集合;然后将传输时延和传播时延作为衡量标准,以O(V+E)(V为图的节点个数,E为图的边的数目)的时间复杂度在最小跳数集合中选择出最小权值路径。最后通过数学方法证明了算法的正确性以及有效性。仿真结果表明,所提路由算法的平均时延、丢包率等都与传统算法相当,但是算法复杂度却得到极大的降低。