基于局部洪泛优化的低轨星座分布式路由算法

周 宇，尹增山，王 龙

（1.中国科学院微小卫星创新研究院，上海 201304；2.上海科技大学信息科学与技术学院，上海 201210；3.中国科学院大学，北京 100049）

0 引言

卫星网络近年来发展迅速，星座路由算法致力于实现卫星网络数据包的高效转发和拥塞控制，将显著地影响网络性能和效率，许多学者对此做了长期研究。WERNER 等［1］提出的虚拟路径路由算法［1］和GOUNDER 等［2］提出的快照序列算法，首先将卫星的周期运动划分为离散的状态序列以实现静态路由，但难以进行网络拥塞控制。AKYILDIZ等［3］随后提出了多层路由算法，通过协同星座内部高/中/低多层轨道，进行分区分工管理，以实现卫星之间动态路由和网络协调。在此基础上，许多学者针对服务质量（Quality of Service，QoS）路稳定性、拥塞控制等方面进行了研究。

分布式路由算法不依赖地面站，能够在轨自主运行，对网络突发流量和需求波动快速响应，具有重要工程价值。HENDERSON 和EKICI 等［4-7］指出，通信星座网络拓扑结构具有规律性，轻量级算法即可实现近似最优路由性能。TARIK 等［8-11］通过相邻链路的拥塞感知，利用交通灯机制、拓扑关系或替代路径分配，进一步改进了算法。此外，融入了蚁群算法、极限学习机等启发式方法的分布式算法［12-13］相继出现，通过全局传导或洪泛收集沿途链路信息，以进行网络拥塞控制。随后，多层星座的分布式路由算法［14-16］也被提出，用于中/低轨层间的流量均衡或QoS 性能保障。

然而，目前低轨星座呈现规模大、节点数量多、多层分布特征。例如StarLink 星座一期包含数千颗卫星，分5 层，轨道高度在540～570 km 之间［17］。基于全局洪泛的网络路径规划存在较大路由延迟和通信开销；而传统分布式算法［4-6］以单层卫星网络拓扑为主，较难适用于多层低轨卫星网络结构［17-18］。针对以上问题，提出一种基于局部洪泛优化的分布式路由算法，具有如下创新：

1）利用分布式的局部洪泛，以较低的算力开销和延迟，实现了对局部拥塞的路径优化。

2）基于局部链路感知，可适用于单层或多层低轨卫星网络结构，提高了对卫星随机故障的适应性，降低网络丢包率。

1 基于局部洪泛的拥塞感知

1.1 通信需求高度不均的分布特征

相比地面通信网络，低轨星座网络具有规律性移动特征。因此各类星座计划［17-18］，主要采用均匀稳定Walker［19］或极地轨道星座构型。若要对特定区域提供持续卫星信号覆盖，需要均匀地部署大量低轨卫星。然而，陆地仅占地球表面积约30%，并且人口和经济活动进一步集中在少数陆地区域［20］，如图1 所示，图中颜色越深表示人口和经济活动密度越大（耶鲁大学的G-Econ［21］项目）。

图1 人口与通信需求的高度不均匀分布Fig.1 Highly uneven distribution of population and communication demand

卫星星座建设无法像地面网络基站一样依据用户密度按需部署，因此容易出现局部拥塞。传统路由一般采用全局洪泛［22］或启发式方法的全局传导［12］，然而对于大型低轨星座，通信和处理开销很大。因此，提出了基于局部洪泛优化的分布式路由算法，有利于解决图1 中高度不均衡的通信业务需求引起的局部拥塞。

1.2 局部洪泛的过程

为了缓解局部拥塞，算法采取局部洪泛的机制收集周围链路的排队延迟。

1）洪泛数据包格式定义

设单颗卫星共有q条星间链路，则每经过时间周期Tlocal，每颗卫星即向周围发出一个局部洪泛包，数据格式为

式中：IDsate为当前卫星的唯一标号；tpacket为此局部洪泛包的生成时间，s；hlocal为此局部洪泛包的剩余跳数，当跳数被用完，此包失活并被丢弃；tISL-1～tISL-q为当前卫星的q条星间链路的实时排队延迟。IDsate和tpacket用于唯一确定洪泛包，防止重复转发。

令局部洪泛跳数hlocal的初始值为一个预设值Hlocal，则单个洪范包所能传输的最远跳数是Hlocal。由此，星座中每颗卫星能够搜集到相隔Hlocal跳之内各颗邻近卫星的链路排队延迟信息。

2）局部洪泛范围的确定

局部洪泛跳数Hlocal的取值应当对于不同的星座参数进行调整，以保证覆盖可能产生局部拥塞的人口密集区域。但如果Hlocal的取值过大，则容易加重卫星算力负担。使用如下步骤确定Hlocal的取值。

步骤1计算出邻近某个特定城市的卫星集合Z。

式中：Si为卫星；Ssite_city为城市坐标；Llocal为城市区域的半径，m。

把以Ssite_city为中心Llocal为半径的地面范围，视为可能会产生局部网络拥塞的城市区域。而函数N(Si，Ssite_city)用于计算卫星Si所覆盖的地面区域，到城市坐标Ssite_city的距离。此函数与轨道高度、星地通信最小仰角有关，可根据几何关系求解。

步骤2计算出距离最接近某个特定城市的卫星Scity，如下式所示。其中，函数D(·)用于计算两者距离，易知Scity∈Z。

步骤3依据集合Z和卫星Scity，计算出最远跳数Hlocal的取值，如下式所示：

式中：函数Hop(Si，Scity)用于计算从卫星Si到Scity最少需要经过几条星间链路，可通过Ekici 等［4］的卫星标号方法算得。

基于此流程算得的Hlocal，保证了卫星的局部洪泛范围能够完整地覆盖容易产生网络局部拥塞的城市区域（以Llocal为预设半径），因为其包含了所有可能对城市区域进行波束覆盖并建立星地链路的卫星。一般选取从低纬度的新加坡，到高纬度的伦敦等主要城市的坐标带入参数Ssite_city，并按照现在的城区范围，令Llocal为100 km 等数值，即可算得局部洪泛最远跳数Hlocal。

2 局部感知优化的算法设计

2.1 路径优化

在局部洪泛的基础上，设存在卫星A正在路由转发数据包P，并且数据包P的接收地为点O，则局部洪泛优化如图2 所示。图中绿色背景的卫星处于洪泛边缘。

图2 局部洪泛感知和确定转发路径Fig.2 Diagram for local flooding awareness and selecting forwarding paths

设局部洪泛共涵盖N颗卫星，共有M颗卫星位于洪泛边缘，洪泛边缘的卫星可表示为Ei(1 ≤i≤M)。首先，根据式（1）进行局部洪泛获取的链路信息，用Dijkstra 算法得出局部最优路径序列：

式中：tpath为生成此序列的时间，s；IDi为图2 中的第i颗卫星的唯一标号；Qi为卫星A到第i颗卫星的最短路径权重，是路径上每条星间链路的排队延迟和传输延迟之和，s；Pi为最短路径中途经卫星的标号序列。

因为通常单颗卫星有4 条星间链路数（2 条同轨，2 条异轨），远小于卫星数量N，可利用堆结构将Dijkstra 算法的时间复杂度降为O(NlogN)［23］。

在高度拥塞的局部网络中，最优路径会变得迂回曲折。因此，定义了指标“距离成本系数”，用于衡量数据包P如果传输至洪泛边缘卫星Ei，是否能用更短的时间更快地接近目的地。以图2 为例，处于洪泛边缘的卫星Ei相对于数据包P及其接收地O的距离成本系数为

式中：函数D(·)用于计算两者间的直线距离；ε用于防止除零；QEi式（5）中的最短路径权重。

路由时，当前卫星会为每个数据包选出“距离成本系数”最大的转发路径，如式（7）所示。其中函数p(·)可依据式（5）将参数卫星映射为对应的局部最优路径（以途径卫星的标号序列表示），RP为路由算法数据包P选出的转发路径。

由此，算法可在局部洪泛范围内，选出让每个数据包最快接近目的地的局部最优路径，从而实现对局部网络拥塞的路径优化。

2.2 多路径间负载平衡

上述过程分布式地运行在每颗卫星上，存在两个问题：首先，卫星在轨资源受限，局部洪泛和路径优化的频率不能过高；其次，路由算法需要及时响应网络突发流量和通信需求波动。

例如，任意两地之间如果出现大量的瞬时卫星通信需求，式（7）会将全部数据包转发到某一条局部最优路径上，随即加重了此路径的拥塞程度和传输延迟。如果将突发流量分摊到多条相似的路径上，可降低端到端延迟，提高整体的网络效率。

为此，引入指标“路径附加延迟”REi作为式（6）分母的补充，则式（7）更新成下式：

当图2 的卫星A完成路径更新后，REi的初始值为0。当卫星A根据式（8）选择出的局部最短路径，以洪泛边缘卫星Ei为终点时，令数据包长度为LP，星间链路传输速率为SISL，则REi按下式更新：

在式（8）中，REi与路径延迟QEi之和，可用于实时估算各条路径所花费的时间成本，把流量负载动态平衡地分配到多条相似路径上，以提高网络的传输效率。不过，附加延迟REi的数值准确度较低，因为多条路径之间可能包含相同的星间链路，其他相邻卫星也在并行地进行着相同的路由转发过程。其主要作用是实现局部的网路负载均衡。

综上，算法流程图如图3 所示。

图3 局部感知优化的分布式路由算法流程Fig.3 Flow chart of the distributed routing algorithm based on local flooding optimization

如图3 所示，若数据包的接收地靠近当前卫星，则在局部洪泛范围内即可找到下传卫星和下传路径。这种情况依然要用到式（9）的“路径附加延迟”，以助于在多个下传卫星中平衡分配流量。

算法基于“距离成本系数”选择局部转发路径。在图2 中，由于卫星连续均匀部署，总会存在更靠近O点的洪泛边缘卫星，让式（8）的分式D(O，A)-D(O，Ei)大于零，使得数据包会不断接近O点。此过程不可逆，因此算法可以避免出现环路。

同时，利用局部洪泛收集链路信息，该算法可建立到达洪泛边缘卫星的路径映射关系，无论部署在单层或多层低轨卫星网络中，或面对随机的卫星故障，均可屏蔽局部网络的结构差异，正常运行。

2.3 时间和空间复杂度

每颗卫星存在4条星间链路，以Hlocal=4 为例，局部洪泛收集链路信息所涉及的局部网络如图4 所示。根据图4 类推，局部网络的卫星数目为N=1+2Hlocal(Hlocal+1)，洪泛边缘的卫星数M=4Hlocal。为了防止洪泛包的重复转发，需保存O(N)的数据。而式（5）的路径信息，需保存O(N2)的数据。则空间复杂度为

图4 洪泛感知的局部网络（以Hlocal=4 为例）Fig.4 Diagram of flooding aware local network（taking Hlocal=4 as an example）

设局部洪泛和Dijkstra 算法的运行周期为Tlocal，已知Dijkstra 算法的时间复杂度为O(NlogN)，则每秒的计算复杂度为1/TlocalO(NlogN)。设每颗卫星每秒需要传输平均k个数据包。根据式（8），单个数据包选择局部路径的复杂度为O(M)。由图4 类推，从卫星A到洪泛边缘，路径最短为Hlocal。数据包每完成一条路径仅路由一次，则单颗卫星需要处理最多k/Hlocal个数据包。因此，每颗卫星每秒运行的时间复杂度为

近年发表的GomHop 算法［24］和低开销分配方案协 议（Low-overhead Distribution Scheme Protocol，LSP）算法［10］时间复杂均为O(k)。算法增加的部分来自局部路径优化。因为Hlocal取值范围通常在3 至10 之间，若洪泛周期Tlocal取值合理，算法的时间复杂度依然较小。同理根据式（10），算法的空间复杂度也较小。

3 仿真分析

为了验证算法的拥塞控制性能，以及对网络随机故障、多层低轨卫星网络结构的宽适应性，独立搭建了仿真环境。

选择StarLink 星座其中3 层作为仿真对象，相关轨道参数见表1［17］。其相位因子、链路设置等细节，参考了Handley 等［25］的处理方法。星间链路传输速率设为10 Gbps，设置所有数据包的收发地相隔大于1 000 km，以排除无需通过星间路由转发情况。通信业务分布假定与人口数量以及人类发展指数（Human Development Index，HDI）正相关，人口数据与HDI 数据参照美国航空航天局官网，经纬度1°方格为网格单元。实验中选择洪泛范围Hlocal和洪泛周期Tlocal分别取(4，0.3 s)、(6，0.3 s)、(6，0.1 s)3 种情况。选择GomHop 算法［24］（2019）和LSP 算法［10］（2019）作为比较对象。

表1 仿真实验的星座轨道参数Tab.1 Constellation orbit parameters of the simulation tests

3.1 拥塞控制和故障包容仿真实验

取表1 中轨道高度550 km 单层卫星网络，针对不同网络负载和卫星故障率5%的情况进行仿真结果如图5 所示。

图5 拥塞控制和故障包容的仿真结果Fig.5 Simulation results for congestion control and fault containment

如图5 所示，图中LAD 为局部感知分布式算法（Locally Aware Distributed Algorithm）。算法能够明显降低网络丢包率，并且局部洪泛跳数越大、洪泛周期越短，丢包率越低，性能越好。在卫星故障率为5%时，依然能将低流量负载的丢包率降至接近0%，对故障的包容性更大。

同时仿真表明，针对通信业务需求均匀分布情况，几种算法的丢包率都会降低到0%。针对高度不均衡通信业务需求分布情况，算法具有拥塞控制能力，能够疏导局部拥塞。

3.2 多层网络结构适应性仿真实验

多层低轨卫星网络存在跨层星间链路。在仿真中设定2 层中满足距离近、移动方向相同，并且位置关系满足一定持续稳定建链时间需求的2 颗卫星间建立一条跨层链路。选取表1 中所有层次作为仿真对象，结果如图6 所示。

图6 多层低轨卫星网络中的丢包率Fig.6 Packet loss rates in multi-layer LEO satellite networks

当卫星出现故障时，本文算法相比GomHop 在丢包率上有更好的表现。当参数选取Hlocal=6，Tlocal=0.1 s 时，本文算法能够将网络负载小于1 000 Gbps 时的丢包率降为接近0%，将网络负载小于1 500 Gbps 的丢包率降至5%以下。

4 结束语

本文针对传统分布式星座路由算法拥塞控制能力有限，全局路径优化开销过大的问题，提出了一种局部洪泛优化的分布式路由算法。通过定义“距离成本系数”为每个数据包确定转发路径，估算各条路径延迟增量，将瞬时流量平衡分配。该算法空间/时间复杂度较低，能够满足小卫星在轨部署的需求，且不会出现路由环路，能够自动适应链路故障和多样化网络结构。仿真表明，针对高度不均通信需求分布，该算法可降低2%～10%的丢包率，并能更好适应多层低轨卫星网络架构。本质上，该算法融合了高计算开销的全局寻径，低拥塞控制能力的静态路由这两者的部分机制，尝试在降低路由开销和减少网络拥塞之间取得平衡，以更好应对地域人口高度集中和需求分布不均的普遍现象，节省在轨路由算力，优化天基网络的通信效率。

未来研究中，面对流量地理分布不均，将计划开展统计学建模分析，构设流量统计和波动预测模型。同时，将跟进修改本文算法，以实现针对拥塞程度和范围的自适应统计感知。并且基于即时拥塞感知，将路由算力按需定向投入，在进一步降低端到端丢包率和通信延迟的同时，尝试保持全局较低的平均路由开销，以优化全网通信效率，让未来的算法更好弥合“地面基站密度可按需按域增减”和“通信星座的卫星密度全球大致均匀”这一硬件机制差异，提升天基网络应对瞬时高强度流量冲击的自适应能力。