基于区域划分的星间流量均衡路由算法

朱 博，双 炜， 闫海平，喻竹希，李 波

(中国航天三江集团 航天行云科技有限公司，武汉 430048)

0 引言

低轨卫星(low-earth orbit,LEO)通信技术是下一代移动通信技术的主要发展方向之一，IMT2030推进组指出，低轨卫星网络是6G时代的关键基础设施，以为全球用户提供无缝覆盖的空天地一体化网络为建设目标[1]。我国由于受地缘政治等因素的影响，用于接收卫星下传数据的信关站在建设和运营等方面受到诸多限制，难以在全球范围内广泛部署。比如服务于我国卫星网络的信关站通常集中部署在某一片区域(国境内以及一些友好国家)，导致在单位时间内大量的回传数据只能路由到少数几个目的节点，从而在流量较大时容易导致局部链路的过载，甚至引发网络拥塞[2-3]。因此，需要借鉴流量工程的思路，充分利用卫星网络中的冗余路径，在路由计算时兼顾回传流量的均衡问题。

低轨卫星网络与地面互联网在拓扑结构、应用场景和用户需求方面存在很大差异，因此，很难在卫星网络中直接使用成熟的地面网络技术。比如提出了路由干扰概念的最小干扰路由算法[4]、将分布式路由模型用于低轨卫星网络的离散时间流量拓扑自适应路由算法[5]以及分布式流量均衡路由算法[6]等，这些算法对于星间流量工程具有很强的启发意义，但一些限制因素使其更适用于地面网络场景，并且在当前的研究中，对于地面信关站部署受限的问题并未得到足够的关注。针对该问题，本文提出了一种基于区域划分的星间流量均衡路由算法。该算法在考虑信关站位置集中的情况下，首先根据卫星星座的“反向缝”与信关站的相对位置关系将回传流量密集的区域划分为轻负荷区和重负荷区，然后针对不同的负荷区域，分别采用不同的路由策略，对于轻负荷区采用预加权最短路径算法，在最小生成树算法的基础上增加新的预设置项，以路径加权和最小为目标计算最优路径。对于重负荷区域，采用基于拥塞系数的最低权重路由算法，该算法利用拥塞系数来对链路权重进行分配，以此来减少拥塞发生的概率，从而最大化网络吞吐量。在系统运行时，不同区域分别执行两种不同的算法，并使用分段路由(segment routing,SR)技术[7]来统一实施，最终达到流量均衡的目的。

1 系统建模

本文的主要研究对象是具备星间链路的地轨卫星网络，其中每颗卫星可分别与同轨道面和相邻轨道面上的四颗卫星建立通信连接，同时还可通过星地间的馈电链路与地面信关站建立连接。对系统建模时需定义一些约束条件并对问题进行适当的简化。首先，假定地面信关站仅部署在有限的区域内，并且每个信关站在单位时间内只能与一颗卫星建立通信链路，因此卫星节点与星下小区具有一一对应关系。此外，由于星座构型的原因，第一个轨道面与最后一个轨道面之间存在“反向缝”，即这两个轨道面上的卫星彼此运行方向相反，相对移动速度很快，导致难以建立稳定的通信连接，所以处于“反向缝”上的两个轨道面之间通常没有星间链路。最后，模型中所涉及的通信信道均被认为是理想信道，不考虑衰落，多径等影响，并且将用户与卫星间的切换过程理想化，不考虑异常情况的发生。

网络中所有卫星均被看作理想的对等节点，令整个星座中卫星节点总数为N×M，其中N表示轨道数，M表示每条轨道上的卫星节点数。卫星节点在轨道上呈均匀分布,除“反向缝”上的节点之外，所有节点都能包含两条同轨链路和两条异轨链路。因此，整个卫星网络拓扑可建模为一张由节点和边组成的图G(V,E)，令包含N个卫星节点的集合为VS，网关节点集合为VGW，其中包含X个信关站节点，以及中心站节点VC(中心站可达任意信关站节点，且卫星下行链路仅与中心站相连)。链路集合E中包含的星间链路条数为EISL，馈电链路集合为EF，信关站间的地面链路集合为EG。各信关站节点均可直接访问中心站节点，EISL的带宽为BISL，EF的带宽为BF，EG可认为带宽无穷大。

基于以上网络模型，根据星座覆盖情况将整个地球划分为多个等面积的小区[8]，卫星与小区在某一时刻具有唯一映射关系，即每个小区内的用户在任意时刻都仅能与一颗卫星建立连接。用户当前接入的卫星如果移动到相邻小区，则将触发用户与接入卫星之间的服务切换[9]。与此同时，每个小区产生的上行流量可根据地理位置、经济程度以及人口数量境因素来进行初步的估计[10]。

(1)

(2)

(3)

综上所述，本系统的求解目标可定义为在满足以下两个约束条件的情况下，设计路由算法来求解路径P，使得吞吐量最大化。

(1)约束条件1：G=(V,E)

f(k),k∈[0,N-1]

(2)约束条件2：

2 星间流量均衡路由算法

2.1 算法描述

地面小区发起的上行流量会通过星间链路逐跳转发到信关站上方的卫星节点，由于信关站的位置分布不均匀，待下传的流量最终会汇集到有限的几颗卫星上，使得靠近信关站区域的链路负荷过重。将这部分区域定义为重负荷区，除此之外的所有区域均定义为轻负荷区。重负荷区域的面积由覆盖该区域的卫星总数An×m来定量表示，其中n表示轨道数，m表示每条轨道上的卫星数。因此轻负荷区域的面积为A(N-n×m)。由于“反向缝”的存在，根据星座“反向缝”与信关站集中区域的相对位置，将星下小区按照流量负荷的轻重进行划分。反向缝与信关站的距离越远，重负荷区面积越大，当反向缝处于信关站正上方时，重负荷区面积达到最小。

针对轻负荷区的路由策略将分为两段来执行。首先，流量从轻负荷区路由到重负荷区边缘节点，然后与重负荷区产生的流量一同执行后续的路由策略，直至目的信关站。因为轻负荷区的流量较少，在到达重负荷区边缘节点前的路由可直接采用最短路径算法生成最小生成树(MST)，但是为了避免过多的流量同时选择了相同的边缘目的节点，采用预加权的方法来减少这类情况的发生。首先每个边缘节点被路由算法选中的次数可以根据初始MST的原始路径进行计算。对于使用频次较高的边缘节点，增加对应的链路权重，以降低被算法选中的频率。假设i所占据的边缘节点数为xi，则链路权重函数可设置为(0.5+0.1xi)，其中0.5表示网络中的初始链路权重，0.1作为阻尼因子来降低xi的调整幅度，从而避免权重值的过度震荡。按照本路由策略，每条从轻负荷区域卫星节点发起的流量会在重负荷区的某个边缘节点处结束，然后与重负荷区域的流量合并开始执行下一阶段的路由。

重负荷区的路由策略与轻负荷区有很大区别。显然，处于重负荷区的卫星节点产生的流量仅会在区域内路由直到目的信关站，而不会进入轻负荷区。重负荷区域的边缘节点所承载的流量主要由两部分组成，一部分直接来自地面小区的上行流量，另一部分则是来自轻负荷区。使用拥塞指数c(e)来描述链路的拥塞程度，如式(4)所示，其中b(e)表示链路e的带宽，F(e)表示当前链路e上承载的总流量，r(e)表示链路e中的剩余带宽。c(e)越大表明链路拥塞越严重，当r(e)=0且b(e)=F(e)时,c(e)=∞，此时说明链路e已经没有可用带宽。相反，当c(e)=0且r(e)=b(e)时，F(e)=0，此时链路e的全部带宽均可使用。可见，拥塞指数c(e)对于F(e)具有更加单调的递增趋势，对于链路负荷的变化更加敏感，因此可用c(e)的变化来评价算法对于链路拥塞状态的控制能力。

c(e)=F(e)/r(e),r(e)=b(e)-F(e)

(4)

链路的权重系数用于描述其承载的流量负荷，链路e在重负荷区的权重系数w(e)定义如式(5)所示，链路承载的流量越少，权重值w(e)就越小。当链路处于空载时，权重值达到最小值0.01。相反，链路承载的流量越多时，权重值w(e)就越大，当链路带宽被耗尽时w(e)=∞。所以，路径P的权重如式(6)所示，路径P的剩余带宽如式(7)所示。需要注意的是，当在重负荷区路由时，如果链路的剩余带宽小于所需带宽，则该链路将被删除。

w(e)=0.01+c(e)=0.01+F(e)+r(e)

(5)

(6)

r(P)=mine∈Pr(e)

(7)

所以，当卫星在重负荷区进行路由时，将依据权重配置生成一个带权值的网络，可使用Dijkstra算法求解出权重值累计最小的路径，以此来建立对应的路由表项。注意，如果卫星节点无法找到到达信关站的路径，则节点承载的流量将会被路由算法拒绝。

综上所述，基于区域划分的流量均衡路由算法的主要执行步骤如下：

1.根据“反向缝”与信关站的位置关系进行区域划分;2.将重、轻负荷区域的节点集合分别记为(yn×ym)、(N-yn×ym);3.轻负荷区进行初始MST路由计算;4.记录原始路径集并生成预加权网络;5.根据预加权网络来更新MST;6.记录轻负荷区域的路径集,并标记重负荷区边缘节点;7.更新重负荷区边缘节点承载的流量值;8.分配和存储每个卫星节点在重负荷区的优先级,然后对重负荷区流量进行路由;for(i=0;i

2.2 复杂度分析

在包含v个网络节点的拓扑中使用Dijkstra算法的时间复杂度是Q(v2)[11]。低轨卫星网络中如果存在N个卫星节点，X个信关站以及一个中心站节点，重负荷区拥有yn×ym个节点，且N≥yn×ym。轻负荷区使用Dijkstra算法时的复杂度为O(N+X+12)=O(N2)，重负荷区的复杂度则为：O((yn×ym)×(yn×ym+X+1)2)=O(yn×ym)3，所以本算法的时间复杂度为O(N2+(yn×ym)3)。随着重负荷区域面积An×m的扩大，算法的复杂度也会提高，反之则会降低。当轻负荷区域有N颗卫星节点时，重负荷区域面积为0，此时复杂度降低到O(N2)。

3 算法验证与性能评估

3.1 实验设置

本实验场景包含72个卫星节点，均匀分布在6个轨道面上，小区的划分如图1所示。

图1 流量小区划分Fig.1 Traffic cells division

每个小区中的数值为参考流量密度[12]。实验中设置了两种流量密度的分布方式用于对比，流量密度均为1的均匀分布和依据图1中预测得到的分布(预配置分布)。在均匀分布时，设置单位服务面积分别为U=1、2和3。在预配置分布时，考虑到很多人口稀疏的地区上行流量会很有限，网络有足够容量来满足传输需求，因此设置为U=4和U=5。

流量负荷区域的划分是该算法的关键步骤，为了分析重负荷区域面积的大小对该算法性能的影响，将重负荷区的面积进行适当的缩放，考虑轨道面从3～6和每轨卫星数2～6之间的所有可能区域(最大6×6)，并将全球面积(6×12)设置为对照组。考察本算法在流量密度为均匀分布和预配置分布两种情况下的性能。实验使用的SR技术是一种基于源路由的转发技术，它在计算路由时将流量路径按照节点和链路的组合进行分段，并为每个段和转发节点分配专属的段标签(SID)，将所有段和节点按顺序排列成段列表，以形成完整的转发路径[13]。SR的特点是配置灵活且易于实现，适用于本算法的验证。

3.2 实验结果分析

为了客观有效地评估本算法的性能，将使用以下4个指标来对实验结果进行评估：

1)平均拒绝率

如果流量无法找到可达目的地址的转发路径，则本次传输请求将会被系统拒绝，平均拒绝率指的是被拒绝的总流量与系统总流量的比值，定义如式(8)，式(8)中R表示平均拒绝率，RS表示被拒绝的流量小区的集合。平均拒绝率越低表明算法的均衡能力越强。

(8)

在流量均匀分布情况下平均拒绝率的仿真结果如图2(a)所示。小区面积在A6×12时，相比其他情况下的平均拒绝率达到最优(接近于0%)。当U随着相同面积的重负荷区增加时平均拒绝率也随之增加。当重负荷区的轨道数相同时，平均拒绝率随着每轨卫星数量的增加而逐渐降低。当每轨卫星数量相同时，拒绝率也会随着轨道数的增加而降低。在预配置分布的情况下(如图2(b)所示)，小区面积为A6×12时的拒绝率为0%，且随着重负荷区面积的增大呈现出减少的趋势，负载均衡的性能表现更好。

图2 平均拒绝率Fig. 2 Average rejection ratio

2)平均相对吞吐量

平均相对吞吐量是成功传输流量的总和，定义如式(9)所示，T表示平均相对吞吐量，Ss是流量传输成功的小区的集合，相对吞吐量和拒绝率是一对互补的概念。相对吞吐量定量地反应了成功传输的流量，与拒绝率成反比关系，平均相对吞吐量越大，算法的均衡能力就越强。

(9)

流量均匀分布时的平均相对吞吐量如图3(a)所示，在全面积时取得最大值。当重负荷区中的轨道数相同时，平均相对吞吐量随着每轨卫星数量的增加而增加，当每轨卫星数相同时，吞吐量也会随着轨道数的增加而增加。在相同的U时，平均吞吐量随着拒绝率的降低而增加。此外，当重负荷区面积相同时，U增加时吞吐量增加，同时拒绝率也随之增加，但是与最优吞吐量阈值的差异增加了，图3(b)是流量预测分布时的仿真结果，变化趋势与图3(a)类似。

图3 平均相对吞吐量Fig.3 Average relative throughput

3)最大链路利用率

最大链路利用率的定义如式(10)所示，F(e)是当前链路e上承载的流量，b(e)是链路e的带宽，当拒绝率很低的时候，最大链路利用率会很重要。最大链路利用率低，负载均衡能力就越好。

(10)

图4(a)表示流量均匀分布时，最大链路利用率的变化，区域面积A6×12时的最大链路利用率最低，并且提供了更低的阈值，当轨道数相同时，最大链路利用率会随着每轨卫星数量的增加而降低。当每轨卫星数相同时，最大链路利用率随着轨道数的增加而减少。最大链路利用率会随着u的增加而增加。这个结果会更关注拒绝率低的小区面积，因为链路利用率超过100%将会导致传输被拒绝。图4(b)显示了在流量预测分布时的结果，重负荷区面积扩大时最大链路利用率会降低，然而，由于预测分布的极度不平衡，结果与较低阈值有差距。

图4 最大链路利用率Fig.4 Maximum link utilization

4)平均延时

平均延时是所有传输成功的流量所产生延时的平均值，其反映了该算法的代价，定义如式(11)所示，|Ss|表示Ss中小区的具体个数，d(b)是流量f(b)所产生的延时，包括路由过程的处理延时和路径传播延时。平均延时越小，用户的体验也就越好。

(11)

在流量均匀分布的情况下，平均延时的仿真结果如图5(a)所示，小区面积在A6×12时的结果作为参考阈值，当吞吐量增加时，延时和代价都会随之增加，然而，在一些面积区域U值增加时，平均延时会减少。这种现象是因为拒绝率升高导致的，仅有小部分流量可以占用链路资源。当拒绝率很低时，随着小区面积的扩大，平均延时也会增加。在预配置流量分布的情况下，仿真结果如图5(b)所示，可以再次印证前面的观点。

图5 平均延时Fig.5 Average delay

实验结果表明，随着重负荷区面积的扩大，平均拒绝率随之降低，平均相对吞吐量随之提高，最大链路利用率也随着减少，这些指标能够直观地体现本算法的性能。需要注意的是，小区面积的扩大指的是轨道数和每轨上的卫星个数的同时增加，实验表明仅在一个维度上增加，负载均衡的收益会很小。此外，平均延时也会随着小区面积的扩展而增加，这将使代价和资源占用也随之增加。本算法的时间复杂度为O(N2+(yn×ym)3)，显然其随着小区面积的扩大而显著增加，因此，如果小区规模太大，相应的延时和资源消耗也会很大，如果小区面积太小则很难避免网络拥塞，所以重负荷区的面积是需要考虑的关键因素。

4 结语

本文针对低轨卫星网络中，由于信关站部署过于集中而导致下行链路拥塞的问题，提出了一种基于区域划分的负载均衡路由算法，并使用SR技术进行了仿真验证。本算法首先根据星座“反向缝”与信关站区域的位置关系对小区流量负荷的轻重进行划分，使用预加权最小生成树算法来计算轻负荷区域的路由，而重负荷区则采用基于拥塞系数的最小权重路由算法。重负荷区的总面积对算法性能的影响较大，仿真结果表明，随着小区面积的增大，在延时增加不大的情况下，平均拒绝率，平均相对吞吐量，最大链路利用率等指标都有了显著提高，表现出了良好的负载均衡能力，证明本算法能够成为解决低轨卫星网络下行拥塞问题的有效方案。

致 谢

本研究工作受到湖北省军民融合类重点研发计划项目(项目号：2020BIB005)天基物联网关键技术研究课题的资助。