一种适用于星地网络的流量负载均衡算法*

郑健阳,李 晖,2,周又玲,王 萍,林志阳

(1.海南大学 信息与通信工程学院，海口 570228；2.南京信息工程大学滨江学院 电子信息工程学院，江苏 无锡 214105)

0 引 言

目前星地网络的研究可以分为两个方向。

一种是对卫星路由进行研究，关注于卫星网络上的路由算法而忽略了地面网络。Guo等人[1]提出了一种基于软件虚拟化网络(Software Defined Networks，SDN)的低轨卫星-地面网络弹性数据流端到端碎片感知路由，他们给星间链路规定了最小支持带宽和弹性带宽，建立了SDN统一管理架构，考虑了星地综合网络中的延迟、波长分段、分配带宽，然而却忽视了地面网络对延迟的要求。王卫东等人[2]根据低轨卫星覆盖范围内业务分布的的时空特性提出了端到端的流量预测方法，根据预测结果提出了动态缓存分配路由，但是其研究的是卫星节点的拥塞情况，动态分配也是依赖对地面业务一天之内的变化情况进行的统计。Wen等人[3]考虑光学低轨道卫星网络，并提出了相应的蚁群算法进行路由和波长分配。Liu等人[4]提出了一种基于卫星网络的物联网全局-局部混合的负载均衡路由方案，使卫星能够通过全局规划和局部实时调整两步来路由物联网流量，但是算法只研究卫星路由的转发。Lagunas等人[5]提出了一种用于具有主动频率复用和卫星与地面网络之间有频谱共享的星地网络的联合功率和流量分配算法，运用凸松弛的方法简化公式，提出了一种可行性方案，但是没有给出地面网络的拓扑结构。Li等人[6]提出了一种星地网络下基于SDN的基础结构并提出了两个面向用户服务质量的算法，然而他们将地面网络简单化的方法还应设置更加合适的场景。

另外一种研究是集中在地面网络中的路由，将卫星网络作为地面网络中的一个简单的中继节点，优化的对象是需要将卫星作为中继的地面网络[7]。Shahid等人[8]提出了一种用于多无线接入技术网络的负载平衡算法，在地面网络中达到多个小区的负载均衡，把过载小区中的用户分配给相邻的小区，使每个小区的无线资源利用率低于作者提出的阈值，但算法没有考虑用户的延迟问题。Abdelsalam等人[9]提出了一种基于SDN的虚拟性能增强代理的设计方案和实施方法，混合卫星地面网络通过虚拟性能增强代理实现，将快速UDP网络连接(Quick UDP Internet Connection，QUIC)协议运用于星地链路中，使网络可以在较低延时的情况下当链路出现拥塞时通过代理服务器将数据通过卫星网络进行传输，但没有考虑卫星网络的负载。Soleymani等人[10]提出了一种在包括无线网络和蜂窝网络的5G异构网络中的概率无线接入选择方法，使用一种多中继站网络来增加中继站的容量和覆盖范围，但没有考虑地面中继站的负载平衡。Lyu等人[11]验证了将双曲几何的相关知识应用于星地一体化网络的路由策略是可行和有效的，在时间复杂度为O(n)的情况下，最优路径选择的路由成功率保持在93%左右，保证了最优路径但没有考虑负载。Hendaoui等人[12]将SDN加入到星地网络的混合架构中，以利用SDN控制器在降低复杂性、增强无线电资源管理过程、保证动态性和扩展整个网络的容量方面的优势。此外，网络切片、分离用户平面和控制平面允许卸载过载并有效地执行频谱共享，但是缺乏对用户延时的计算。

综上可以看出，学者们针对不同的应用场景提出了不同的应用，但是星地网络的研究中缺乏对地面业务实时性的考虑，有些没有考虑卫星网络的负载或者是地面负载，有些研究没有给出地面网络的拓扑结构。为此，本文提出了一个负载平衡算法来平衡地面网络，地面用户基于改进的蚁群算法进行路径搜索，设置一个自适应的卸载阈值，当地面链路出现拥塞的时候将用户的数据流卸载到别的链路或者卫星网络中。为了能够达到负载均衡需要估算链路的负载状态，并选择合适的用户以避免不必要的卸载。

1 系统模型

1.1 网络体系结构

如图1所示，假设卫星网络由低地球轨道卫星星座(如Iridium、Globalstar等)组成，而地面网络由地面站、交换机和服务器组成。假设卫星网络的链路是光星间链路(Inter-Satellite Link,ISL)，而地面网络的链路是采用更高带宽的光纤。尽管卫星网络有一些限制，如仰角，但大多数星座保证一颗以上的卫星可以随时与地面网络连接。与传统的综合网络不同，由于卫星链路具有多个地面站，同时使用不同的波束，因此存在多个可供使用的星地链路(Satellite-to-Terrestrial Link,STL)。因此，从卫星网络传输到地面网络中的服务器或数据中心的数据流可以通过任何STL。考虑到卫星节点的运动性，在进行地面向卫星网络进行流量卸载的时候将卫星节点看成一个虚拟的节点，即看成总有一个卫星能够为地面网络提供服务。网络控制器拥有基于SDN技术控制卫星和地面组成的异构网络的能力，使统一管理路由和流量成为可能，在本文中可以用于平衡地面网络的负载。LEO卫星网络可以用于数据服务访问、服务收集和数据流传输，具有低延时的特点。

图1 网络模型

当地面节点随机分布于一个正方形区域内时，存在一种情况，所有节点准备将自身收集的数据发往顶角的节点，这样就会极易出现与该点相连的对角线以及对角线的两侧链路过载的现象，导致链路拥塞，这样的节点我们称之为汇聚节点。本文要解决的就是出现这种情况导致的链路拥塞问题。为了防止这些链路的负载，需要先对地面网络进行建模。

对地面网络进行建模可以为G=〈V,E〉，其中V是节点集，E(t)代表的是网络中的链路集，e(i,j)是E(t)中的元素，i和j之间的链路如果是连通的则代表1，不连通就代表0。G(t)可以用公式(1)描述：

G(t)=Gt(t)∪Gs(t)∪Est(t)。

(1)

这里的Gs=〈Vs,Es〉和Gt=〈Vt,Et〉 分别代表的是卫星网络和地面网络的网络图，同时Est(t) 表示的是卫星与地面的链路。

1.2 数据流和算法

可以将网络的数据流分为延迟容忍和延迟敏感两种。由3GPP在5G系统中所定义的分组延迟预算(Packet Delay Budget,PDB)对数据流进行分类，把那些PDB大于卫星传播时延的数据流当做延迟容忍流，PDB小于卫星传播延迟的流被认为是延迟敏感流。为了支持不同的数据流，5G中引入了不同的参数集[13]。基于数据流，每个用户可以使用不同的5G参数集,如载波间隔。表1给出了5G空口的多种参数集。一个物理资源块是一个基站分配给用户的最小单位，每个5G地面网络都有一些基于系统带宽和载波间隔的可用物理资源块，可用资源块带宽取决于载波间隔，一个物理资源块占用的带宽等于进入载波间隔的连续子载波数。

表1 5G传输参数集[13]

为使地面的链路情况达到最佳，且考虑到卫星接入后卫星网络的延迟比地面高出几个数量级，所以我们提出一个链路资源利用率β来衡量地面网络的流量，地面链路负载高则链路资源利用率高，可表示为

β=∑τ∈(t-T,t)(λτ+γτ)/T·ωs，

(2)

(3)

在卫星网络中也由链路资源利用率来表示对卫星网络造成的负载情况，用下面的公式进行计算：

βS=∑τ∈(t-T,t)φτ/T·ωsat。

(4)

(5)

这时候再对每条链路的β进行判断：对所有βn>Thrad的链路χ={E1,E2,…,Em}按照{E1,E2,…,Em}的大小进行降序排序得到{βα1,βα2,…,βαm}，从大到小对链路中的数据流进行流量卸载的计算。

对于一个过载的Ex，我们对经过这条链路的数据流按照数据流的大小进行排序得到Ex={e1,e2,…,ea}，先从最大的开始计算卸载路线，得到的卸载后的路线需要满足以下条件才能认为可以进行卸载：

(6)

(7)

∃β>Thrad，

(8)

βS

(9)

满足以上条件则可以对地面的延迟容忍流量进行卸载。首先要生成一组ε={e1,e2,…,ex}表示过载的链路，将链路中的设备按照升序排序，将数据流逐个卸载到卫星链路，然后根据用户设备所需的速率使用香农公式计算出

(10)

(11)

1.3 基于SDN的管理架构

由于SDN实现了对网络的统一控制，基于SDN的路由机制的服务质量属性和传输路径也得到统一管理，使得异构网络端到端路由成为可能[1，14]。本节描述了一个典型的控制结构和关键的功能模块，如图2所示。

图2 基于SDN的星地网络管理和控制架构

基础设施层包含地面网络和卫星网络，运行在控制层的SDN控制器通过南向接口对两个异构网络进行控制，控制层包含算法、拓扑结构和服务分析；北向接口将应用层中应用的指令传至控制层，控制层将指令在传至基础设施层，并将相关信息提供至应用层中。

1.4 蚁群算法

本文用基于蚁群算法改进后的ARA算法[15]作为计算网络最短路径的算法。ARA算法是一个基于蚁群算法的移动自组织网路由协议，通过使用前向蚂蚁和后向蚂蚁两种不同的蚂蚁分组来建立路由，前向蚂蚁负责探测路径、采集信息，后向蚂蚁对信息素浓度进行更新，通过这种方式实现信息素浓度随着不同路径的特征不均衡分布，以便使蚂蚁分组能够根据这些找到路径。由于蚁群算法容易出现局部最优的情况，采用轮盘赌法选择下一个点，并且设置了最大信息素可以在局部信息素更新之后进行判断，目的是防止过早收敛。ARA算法也进行了改进，在链路中加入路径评价，把节点的能量消耗加入蚁群算法[16]。蚂蚁在路径搜索过程中释放的信息素大小公式如下：

(12)

式中：EAver(m) 表示路径中各个节点剩余的平均能量，Emin(m) 表示路径中各个节点剩余的最小能量，Ec(m) 表示消耗的能量。

2 本文所提算法

本文所提算法运用ARA算法计算路径，基于每个节点数据流占用链路的带宽计算出链路资源利用率，找到需要进行负载均衡的节点，通过对这些节点中的数据流改变路径来达到链路的均衡。该算法大致可以分为两个步骤：第一步就是地面节点之间的流量转移；第二步是对地面链路中延迟容忍类流量往卫星网络的卸载过程。为了更好地介绍，我们将其分为地面网络的缷载(算法1)和卫星网络间的卸载(算法2)。

算法1是对地面流量的计算。在发现地面链路出现超过阈值的情况时运行算法1可以使数据流改变路径以减少经过过载路径的数据流。该算法收集过载链路中的负载信息，在卸载流量前，需要确定各个链路的负载情况判断合适的阈值，这样可以避免卸载过多或者产生不必要的卸载，先对过载的链路进行排序，然后对通过这些链路的数据流按照它们占用链路的大小进行排序，按照从小到大的顺序一个接一个地将它们合理地在链路中进行分配，并且还要防止卸载之后的链路超过阈值。

算法1伪代码如下：

输入：网络的拓扑结构G，数据流e，初始阈值Thr0

1 求每个节点到目的节点的路径PATH

2 将每个节点产生的数据流带宽代入路径得到每条链路的β

4 对这些β进行降序排序得到{βα1,βα2,…,βαx}

5 fori=1:x

6 对链路中的数据流按照带宽大小降序排序

7 forj=1:数据流的数量

9 if 满足式(6)和式(7)

10 更新路径PATH、βαi和βei

11 ifβαi

12 break

13 end if

14 end if

15 end for

16 end for

输出：所有节点到目的节点的路径PATH，自适应阈值Thrad

算法2在算法1之后运行，若发现过载情况则需要计算星地链路的负载情况，判断是否能够将地面网络卸载到卫星网络中，当满足条件后对地面的延迟容忍流进行卸载。

算法2的伪代码如下：

输入：卫星的链路资源利用率βS，所有节点到目的节点的路径PATH，自适应阈值Thrador 初始阈值Thr0，网络的拓扑结构G，数据流e

1 计算地面网络的链路情况，得到所有链路的β

2 判断式(8)得到过载链路{e1,e2,…,em}共计m个，对应的βη={βη1,βη2,…,βηm}

3 fori=1:m

4 if 满足式(9)

6 fory=1:x

8 if 满足式(11)

11 if ∀βη

12 break

13 end if

14 else

15 break

16 end if

17 end for

18 end if

19 end for

输出：地面链路资源利用率β

3 仿真与分析

我们考虑一座城市的大小，将仿真场景设定在一个50 km×50 km的区域里。假设在这个场景中有100个节点，先生成100个节点在区域中的坐标，再为节点使用k类均值算法来限制它们的分布，这可以使节点的分布在兼顾随机性的同时更加均匀，其中每个节点的通信距离为10 km，得到地面网络的拓扑结构，为网络指定一个节点为汇聚节点，其负责与核心网络连接。在网络中，70%的用户数据为延迟敏感流量，而其余的流量为延迟敏感流量。具有延迟容忍流的载波间隔是15 kHz，具有延迟敏感流的载波间隔为15 kHz或30 kHz，链路的带宽为300 Mb/s。由于地面网络范围较小，一颗低轨卫星也足以覆盖，仿真中用到铱星卫星，卫星使用C频段进行通信，频率在3.7～4.2 GHz的频段用于下行链路。卫星的信道带宽为500 MHz，有12个转发器，每个转发器的带宽为36 MHz，保护频带为4 MHz[8]。表2给出了实验参数。

表2 实验参数

选用Matlab对算法进行仿真，选择了一个不进行卸载和一个只在地面网络中具有自适应预知的卸载算法作为对比，分别将它们称为没有使用负载均衡算法和普通负载均衡算法。

模拟一个链路负载的初始场景，为每个节点生成五次数据流，代表这一时刻节点向汇聚节点发送的速率，速率大小在5～15 Mb/s中随机产生，并验证平均值为10±1 Mb/s。仿真时将网络中最右上角的点作为汇聚节点，其他节点通过链路将数据流流向该节点，仿真后地面网络的链路资源利用率如图3所示。

图3 目的节点处链路资源利用率的表现

T=0代表的是链路的初始状态。三种算法的初始情况相同且有链路存在过载的情况，初始状态中有链路原有的数据流和新产生的数据流。在T=0～1的这个时间间隔内，对网络中新产生的数据流进行算法的运算，在T=1时完成对新数据流的路径计算。在T=1～2的时间间隔内，链路完成了之前数据流的传输，减少了链路的负载，期间每个节点继续生成数据流并用算法计算，在T=2时显示出计算后的负载情况。以此类推，继续得到之后几次的链路情况。

图3(a)表示在链路资源利用率较高的情况下如果不及时改变路径进行负载均衡就会导致负载链路资源利用率越来越高；图3(b)表示运用具有自适应阈值的地面负载均衡算法，将负载从过载的小区转移到未充分利用的链路上，例如在T=1时自适应阈值为0.73，虽然地面负载均衡算法减少了过载链路的数量使链路资源利用率低于自适应阈值，但是仍会出现有个别链路依然过载的情况。在T=1时对比图3(b)和图3(c)可以看出，图3(c)中的链路状况更好且经过算法2的运算之后自适应阈值下降至0.7，比图3(b)下降了0.03，且各个链路的资源利用率都低于了阈值。观察图3(c)，在时间T=2～5中每条链路都能够将链路的负载降低至阈值以下，说明利用本文提出的算法能将地面的延迟容忍数据流有选择地卸载到低轨卫星上。

根据以上实验的方法产生1 000次数据流并进行仿真，在得到路径的负载情况之后可以计算数据流到达目的节点的延时，数据流通过不超过初始阈值的链路的正常时延等于节点之间的距离除以2/3倍的光速，当链路中出现βi>Thr0时，则会导致3βi的正常延时时间。用每个节点延迟敏感数据流到达目的节点的时延之和除以节点数来表示平均时延大小，结果如图4所示。

图4 三种算法的时延比较

从图4中可以看出，本文提出的算法通过降低链路链路资源利用率的方式来降低链路拥塞的产生，以减少数据流到达汇聚节点的时延。在没有负载均衡算法的情况下由于链路拥塞导致数据流到达汇聚节点的延迟有所增加，使用普通地面负载均衡算法也能够达到较好的降低延迟的效果，而本文提出的算法将延迟容忍数据流卸载到卫星链路能够为地面网络进一步降低平均时延，图中没有使用负载均衡算法的地面网络在1 000次的数据流计算中平均时延为0.003 9 s，使用了普通的负载均衡算法的地面网络平均时延是0.003 0 s，使用星地负载均衡算法的地面网络在不考虑延迟容流的负载时平均时延为0.002 8 s。由于数据流的随机性和路径选择的不一样，导致同一种算法有上下的波动性，但是都在一定范围以内上下浮动，地面负载均衡算法出现与星地负载均衡算法最大的差值为T=847时，普通负载均衡算法的时延是0.003 42 s，星地负载均衡算法为0.002 89 s，提升了18.3%。

图5显示了算法2在这1 000次数据流产生时将数据流中的延迟容忍流卸载到低轨卫星网络的情况，由图可以看出卫星能将链路资源利用率保持在低于阈值的水平，为地面节点提供延迟容忍流的传输服务。考虑到卫星的负载状态，新数据流可以容易地被容纳在网络中，并且卫星可以分配更多的资源来满足用户的服务质量。本次仿真中卫星链路资源利用率的最大值为0.22，说明这一颗卫星最多可以为三个这样的地面网络提供服务，且不超过阈值。

图5 卫星的链路资源利用率

不改变节点的拓扑结构以及节点的初始负载，仿真网络在一个时间间隔内每个节点只产生一个含有延迟容忍和延迟敏感的数据流，且每个节点产生的数据流大小相同速率为5～15 Mb/s中的整数，对这样的地面网络进行负载均衡计算，之后计算各个节点产生的数据流到达汇聚节点的平均时延，结果如图6所示。可以看出，随着数据流速率的增大，刚开始5～9 Mb/s时三种算法的平均时延相对较低，但是由于存在链路超过初始阈值的情况没有使用负载均衡算法的网络时延高于其他两种，而其他两种时延相同。这表明它们即使没有运行算法2，而随着数据流增加，只有星地负载均衡算法还在较低的位置。在各节点速率为13 Mb/s时由于普通负载均衡算法会导致路径变长，自适应阈值上升等原因导致之后的延迟越来越高，使普通负载均衡算法的延迟超过了没有使用负载均衡算法的延迟，所以原有的均衡算法也不再具备优势，只有本文提出的算法降低了网络的时延，在各节点速率为15 Mb/s时，相比普通负载均衡算法降低了0.000 3 s。

图6 不同节点速率对时延的影响

3 结束语

本文提出了一种负载均衡算法用于星地一体化网络，考虑先在地面网络的链路之间进行卸载，当地面链路负载情况不佳时再采用卫星网络间的卸载算法，使地面网络更加均衡。仿真结果表明，把数据流卸载到卫星上可以有效降低地面网络的时延，为用户提供足够的带宽。该算法通过使用链路资源利用率来计算网络的自适应阈值以获得更好的性能表现。

本文仅仿真了算法在星地网络中的可用性，依靠卸载链路中的延迟容忍流达到降低延迟的效果，对于卫星网络只考虑了一颗卫星。下一步将充分利用卫星网络的优势进行星地网络的研究，并希望能借助SDN实现该算法。