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

来源：电讯技术杂志2021年第6期北京时间：

作者：雷援杰,唐宏,马枢清,李艺

单位：(重庆邮电大学 a.通信与信息工程学院;b.移动通信技术重庆市重点实验室，重庆 400065)

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

关键词：LEO卫星网络；网络拥塞程度感知；广度优先搜索；最短路径；路由算法；

基金资助：长江学者和创新团队发展计划(IRT_16R72)