雷援杰 ，唐 宏，马枢清，李 艺

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

0 引 言

随着通信技术的发展，天地一体化网络已成为下一代通信的发展趋势。作为天基骨干网络的低轨(Low Earth Orbit，LEO)卫星网络因为具有全球覆盖、可以忽略地形限制进行点对点通信等优点而成为研究的热点[1]。

LEO卫星网络具有时变的动态拓扑特征，这是不能直接将地面网络路由算法直接迁移到卫星网络上的主要原因[2]。随着SpaceX的starlink计划的推进[3]，卫星组网规模变得更加庞大，成为未来卫星网络发展的一种趋势，但是卫星星上存储以及计算能力有限[4]，所以高效简洁的路由算法成为卫星网络的一个研究重点。

卫星路由是卫星通信中的核心。针对该问题，DT-DVTR(Discrete Time Dynamic Virtual Topology Routing)算法[5]利用快照的思想，将卫星随时间连续变化的动态网络拓扑结构离散化，并且在每个快照内近似认为网络拓扑结构是静止不变的，然后将在线下利用Dijkstra算法寻找出的最短路径存储在卫星上，当有数据转发需求时，查询路由表完成数据转发。但是该算法并没有应对突发流量的能力。文献[6-7]通过对服务质量(Quality of Service,QoS)指标进行最优化建模，通过蚁群算法计算出满足多种QoS约束的最优路径。尽管蚁群算法能够求解出一条或者多条满足QoS指标的路径，但是相对于传统算法，计算复杂度相对较高。

最短路径算法是表驱动路由中的重要组成部分。广度优先搜索(Breadth First Search,BFS)算法可以解决无权图的最短路径问题。Dijkstra算法拥有较低的复杂度，但是不能处理负权边问题。……