一种高效动态LEO卫星网络流量调节路由算法

罗拥华，邬家炜

(华南师范大学 计算机学院，广东 广州 510631)

一种高效动态LEO卫星网络流量调节路由算法

罗拥华，邬家炜

(华南师范大学 计算机学院，广东 广州 510631)

针对考虑负载均衡的LEO卫星网络路由算法存在控制网络开销偏大、路由更新不及时以及流量调节机制分配不均等问题，提出了一种基于负载均衡的动态LEO卫星网络路由算法DRLB。根据卫星节点路径记录信息以及后向Agent读取策略设计新的路由机制，获得动态卫星拓扑结构；分析前向Agent的分组格式并删除冗余字段，达到减小网络开销目的；根据数据发送时间间隔构造前向Agent选址策略，提高路由更新效率，通过考虑卫星所处纬度流量分配不均问题，改进流量调节因子，获得更好的负载均衡效果。仿真结果表明，与SDRZ-MA算法相比，DRLB算法在减缓星地之间的控制开销、平均端到端时延等方面具有较好的优势。

负载均衡；卫星网络路由；流量调节；更新路由；调节因子

0　引言

LEO卫星网络具有动态变化的拓扑结构，拓扑一直都在快速变化，这是LEO卫星网络区别于地面自组织网络的主要特点，而且卫星的存储能力和处理能力有限[1-2]。同时，卫星间的距离很远，容易导致较大的端到端传输时延[3]。

对此，研究人员提出了一些基于负载均衡的路由机制，如ELB算法[4]是由TALEB T提出的，该算法主要是将卫星节点在发送或转发数据分组前已经获取到了下一跳节点的链路负载状况，依次作为依据，为数据分组选择合适的转发路径。但如果网络中出现的拥塞节点过多时，该算法性能会降低甚至失效。KUCUKATES R等人[5]提出了PAR算法，该算法是在网络拥塞发生前及时采取措施进行避免，从而实现网络负载均衡的效果。但是该算法网络吞吐量不高，同时分组端到端时延也比较大。SDRZ-MA算法[6]将 Agent引入到LEO卫星网路由中，其卫星节点定时产生前向Agent在卫星节点间来回转发，迁移过程中收集卫星纬度、链路代价等路由更新所需信息。但SDRZ-MA算法存在部分卫星负载过重、其他卫星资源开发不足的问题。

对此，本文基于SDRZ-MA算法思想，提出了基于负载均衡的动态 LEO卫星网络路由算法DRLB（Dynamic Routing Algorithm based on Load Balance)。分析前向、后向Agent如何读取路由机制，并设计新的路由策略以及优化前向 Agent的分组长度，改进流量调节因子函数，使网络流量更适应具体维度位置。最后，测试了本文路由算法在控制开销、流量调节以及平均端到端时延等方面的性能。

1　网络模型及问题描述

1.1网络模型及相关定义

在本文 DRLB算法中，用 Walker星座[7-8]进行组网，该算法是将卫星网络抽象看作一个由一组节点V和一组边E组成的无向连通图G=(V，E)。其中，|V|为网络中所有卫星节点的个数，|E|是网络中所有星际链路的个数。算法相关定义为：

(1)如果卫星节点s与卫星节点v之间存在星际链路，则用links↔v表示；

(2)卫星节点s的所有邻居卫星的个数用Ns表示；

(3)costs，v(t)表示在 t时刻，卫星节点 s与邻居卫星 v之间星际链路的代价值；

(4)假设源卫星 s与目的卫星 d之间的最短路径为：

1.2问题描述

通过对考虑负载均衡的具有代表性的LEO卫星网络路由算法SDRZ-MA进行研究，发现该算法存在以下问题：

(1)因地面业务热点集中在北半球，尤其是北纬 50°以内，原始SDRZ-MA算法设计了λvi代价调节因子，以促使流量由北半球向南半球分配，但代价调节因子λvi的设计存在缺陷；

(2)在SDRZ-MA算法中，卫星星座运行一个周期后，每个卫星节点仅以概率 qd的值来确定前向 Agent的目的卫星地址，这不够全面，会导致卫星节点对于全网的拓扑信息获取得不够及时准确；

(3)前向Agent分组存在冗余字段。

2　本文DRLB算法

由于基于移动Agent的LEO卫星网络路由算法存在网络控制开销偏大、流量调节机制不合理的问题，本文提出了基于负载均衡的动态LEO卫星网络路由算法DRLB。

2.1流量调节因子的改进

在SDRZ-MA算法中，调节因子λvi的函数如下：

其函数见图1(a)。依图可知，当纬度大于北纬 50°后，调节因子的曲线走势仍继续向上，这显然不符合实际情况。对此，本文考虑卫星纬度具体地理位置，对模型（3）进行修正，形成新的流量调节因子模型：

新的调节因子的函数见图1（b）。依图可知，改进后的调节因子可以保证北半球的权值始终大于南半球，其中0°～50°的权值最大，这更符合实际的业务分布状况。

图1　流量因子改进前后的函数分布

2.2优化前向Agent目的卫星的选取策略

在SDRZ-MA算法中，卫星节点会定期向其他卫星发送前向Agent，该前向Agent的目的地址以概率qd来确定：

其中，fsd表示从源卫星s向目的卫星d发送的数据总量。在SDRZ-MA算法中，会出现短时间内重复产生同一目的地址的前向 Agent的情况。为此，本文通过（前向Agent发送时间间隔来避免重复发送的问题。在本文DRLB算法中，卫星节点在发送前向 Agent的时间间隔内，记录本时间段内经过自己的其他卫星节点产生的前向Agent的目的地址。当某一卫星节点需要发送自己的前向 Agent时，首先排除自己记录的前向 Agent的目的地址，然后再按概率 qd选择前向 Agent的目的地址，这样卫星节点能够获取更准确的网络负载状况，寻找最优路径。

2.3压缩Agent分组长度

在SDRZ-MA算法中，前向Agent记录的路由信息为：

显然，DRLB算法的前向Agent长度明显小于SDRZMA算法。在DRLB算法中，每颗卫星都有一个纬度表和邻居卫星到自己的代价表，当前向Agent到达某一卫星节点后，该卫星节点会更新自己的纬度和该前向Agent上一跳节点到本节点的链路代价，同时在前向Agent分组中加入该卫星的信息，然后继续迁移。当前向Agent满足规则4中的任意一个条件后生成后向Agent，后向Agent沿前向Agent原路返回，依次从所经过的卫星节点上读取该卫星记录的纬度和对应链路的代价信息，压入自己的内存中，同时更新经过卫星节点的路由表。后前Agent到达源节点后，其堆栈信息为：，这与 SDRZ-MA算法的后向Agent携带信息一样。

2.4DRLB算法规则及基本操作

2.4.1算法规则

(1)规则1

路由表初始化：

(2)规则2

①在网络运行的第一个周期内，所有卫星节点会定时生成前向Agent，前向Agent的目的地址从本卫星外的其他卫星节点中随机选取。

②第二个周期开始，每个卫星节点在生成前向Agent前，首先排除前向Agent产生间隔内该卫星记录的经过自己的前向Agent的目的卫星地址，然后再按概率qd选择Agent的目的地址，前向Agent生成后发送给邻居卫星。

(3)规则3

①前向 Agent到达中间卫星后，根据该卫星节点的路由表来选择下一跳。若存在链路不可用时，则先排除不可用的链路，并对该卫星的路由表重新更新，再选择下一跳。

②前向Agent生成后向Agent，生成的后向Agent沿该前向反方向移动。

(4)规则4

当下面的任意一个条件成立时，前向Agent生成后向Agent，前向Agent消失：

①前向移动Agent达到其寿命期。

②前向Agent根据规则3选择下一跳时，选择的下一跳卫星已经被该前向 Agent访问过或没有可用的路径。

(5)规则5

①网络代价模型的更新：

其中：η为学习率，是一个大于0小于1之间的数。

②路由表的更新：

如果前向Agent从源卫星节点s到达目的卫星节点d的路径为 s→v→…→d，那么Ts路由表根据下式来进行更新：

2.4.2具体步骤

(1)所有节点按规则1完成路由表的初始化工作。

(2)卫星节点s根据规则 2产生一个具有一定寿命的前向 AgentFs，在迁移期间，AgentFs记录每个被访问节点Vi的地址，最后一个被访问节点的纬度和该节点的上一个跳节点到本节点的代价。当AgentFs到达中间卫星节点后，中间卫星节点根据AgentFs携带的信息更新自己所处的纬度位置以及上一节点到本卫星节点的代价。当 AgentFs到达目的卫星节点时，所携带的信息格式为：。

(3)前向Agent在迁移过程中根据规则3来进行路由选择，当规则4要求的任意一个条件满足时，前向Agent生成后向AgentBd。

(4)前向移动 AgentFs将自己携带的路由更新所需信息压入到后向AgentBd的内存中，同时自身寿命结束。

(5)后向 AgentBd沿前向反方向迁移。当迁移到路由中间节点Vi时，读取中间节点记录的自己的纬度和在该纬度位置时上一节点到本节点的代价，存入堆栈，同时获取下一跳节点信息继续迁移，直至迁移到源节点，每经过一个中间节点，按照规则5更新节点的路由表Tvi和网络代价统计模型Cvi。如果通往下一跳节点的链路不可用，则后向AgentBd自动销毁。后前Agent到达源节点后，其内存信息为：。

本文DRLB算法Agent工作流程如图2所示。

图2　移动Agent工作流程

3　仿真和性能分析

3.1仿真环境设置

本文借助仿真软件是OPNET14.5来测试本文路由算法的网路性能[9-10]。为了模拟实际的卫星网络的流量分布，仿真中卫星在北纬0°～50°之间卫星节点每发送0.4 s数据包停止0.8 s，其他非极地区域卫星节点每发送0.1 s数据包停止 1.1 s，数据包的目的地址随机。为了体现本文算法的先进性，将当前LEO卫星网路由性能较好的 SDRZ-MA算法视为对照组，并取 α=3，β=5，η=0.8。星座拓扑仿真参数如表1所示。

表1　本文DRLB算法的仿真参数设置

为了量化本文算法与对照组算法的网络性能，本文用丢包率、平均端到端时延与归一化ISL负载等指标[11]来评估。

3.2实验数据与分析

(1)丢包率

如图3所示，SDRZ-MA算法和DRLB算法在终端比特率小于400 kb/s时，丢包率都接近0，这是由于这时网络比较空闲，数据包能够及时准确地送达目的节点。当终端数据量增大时，DRLB算法的丢包要小于SDRZ-MA算法，这是由于调节因子的改进使得全网流量得到了合理分配，同时根据节点的流量排序选取前向Agent目的节点，避免了重复向同一节点连续发送前向Agent的情况，节点对全网的负载信息获得更加准确；而SDRZ-MA算法没有考虑到卫星通信中节点移动速率巨大导致的流量分配难题，使其丢包率较高。

图3　两种算法的丢包率测试结果

(2)平均端到端时延

平均端到端时延随终端变化率见图4、图5。图4中数据源卫星和目的卫星都在北半球，此时DRLB算法的性能明显优于SDRZ-MA算法，这是由于DRLB算法针对地面人口和大陆板块的分布现实状况，设计新的流量调节因子，更好地将网络流量分配到南半球，最大程度上避免了由于链路拥塞而造成数据分组在卫星节点长时间缓存得不到转发的情况。

图4　南半球位置下的平均端到端时延

图5　北半球位置下的平均端到端时延

图5中数据源卫星和目的卫星都在南半球中，两种算法的端到端时延差不多，但在新算法中前向Agent的目的地址的选取策略得到优化，降低了重复获取某若干条链路负载信息的概率，使节点获得准确的全网负载信息来更新路由表，因此DRLB算法的平均端到端时延稍微好一点。

(3)归一化ISL负载

归一化ISL负载随卫星纬度的变化如图6所示，在南半球DRLB算法的链路负载要大于SDRZ-MA算法，北纬大约0°～50°之间，DRLB算法中链路负载要小于原SDRZ-MA算法。这是由于本文算法对流量调节因子进行了改进，增加了0°到北纬 50°间的链路代价权值，使得业务流量更多的被分配到了南半球。同时，该算法对前向Agent的目的地址的选取进行了改进，提高了路径更新的效率，卫星节点更好地获得网络的负载状况，进一步实现了流量的再分配。而SDRZ-MA算法在卫星节点移动速率巨大时不能动态对链路业务流量进行分配，导致网络出现较大的拥塞。

图6　各算法的归一化ISL负载测试

4　结论

针对考虑负载均衡的LEO卫星网络路由算法网络控制开销偏大以及流量调节机制存在缺陷等问题，提出了基于负载均衡的动态LEO卫星网络路由算法DRLB。在DRLB算法中，路由更新所需信息采用由卫星节点记录、后向 Agent读取策略，减小前向 Agent的分组长度，降低网络控制开销；对前向Agent目的地址的选取策略进行改进，提高路由更新的效率；优化流量调节机制，更好地实现网络负载均衡。理论分析和仿真结果表明，与SDRZ-MA算法相比，DRLB算法在丢包率、平均端到端时延等方面的性能均有所提高。

[1]韦娟，薄振雨，刘叶.基于分时的 LEO卫星网络非对称路由算法[J].计算机科学与探索，2014，9(7)：832-838.

[2]WERNER M，JAHN A，LUTZ E.Analysis of system parameters for LEO/ICO-satellite communication networks[J]. Journal on Selected Areas in Communications，2014，13(2)；371-381.

[3]CHANG H S，KMI B W，LEE C G.FSA-based link assignment and routing in low-earth orbit satellite networks[J]. Transactions on Vehicular Technology，2013，47(3)：1037-1048.

[4]TALEB T，MASHIMO D，JAMALIPOUR A.SAT04-3：ELB：an explicit load balancing routing protocol for multi-hop NGEO satellite constellations[C].Global Telecommunications Conference，IEEE Press，2012：1-5.

[5]KUCUKATES R，ERSOY C.Minimum flow maximum residual routing in LEO satellite networks using routing set[J].Wireless Networks，2013，14(4)：501-517.

[6]RAO Y，WANG R C，ZHENG Y.Satellite network dynamic routing algorithm based on mobile agent[J].Journal of PLA University of Science and Technology，2014，11(3)：255-260.

[7]CHAN T H，YEO B S，TURNER L.A localized routing scheme for LEO satellite networks[C].ICSSC，2012：2357-2364.

[8]WERNER M.A dynamic routing concept for ATM-based satellite personal communication networks[J].IEEE Journal on Selected Areas in Communications，2013，15(8)：1636-1648.

[9]CAZABET R，AMBLARD F.Detection of overlapping communities in dynamical social networks[C].Proceedings of Conference on Social Computing，2013：309-315.

[10]任智，王路路，杨勇.机会网络中基于定向数据传输的地理路由算法[J].计算机应用，2014，34(1)：4-7.

[11]Liu Feng，Zhang Yu.Simple change adaptive routing algorithm for satellite IP networks[J].Journal of Software，2013，8(8)：1991-1999.

An efficient routing algorithm based on load balancing for dynamic LEO satellite networks

Luo Yonghua，Wu Jiawei
(College of Computer，South China Normal University，Guangzhou 510631，China)

In order to solve the problems that dynamic routing algorithms based on load balance have the redundancy control packet field,routing is not updated timely and the flow regulating mechanism exists defect,a Dynamic Routing Algorithm based on Load Balance(DRLB)is proposed in this thesis.The required information for updating routing is recorded by the satellite nodes, and then the backward agent reads the required information from the satellite nodes.Moreover,DRLB reduces the length of forward agent to reduce the control overhead of network and it also optimizes the selection of the destination node of forward agent to improve the efficiency of routing updates.Finally,DRLB optimizes the flow control mechanism to achieve better load balancing.Simulation results show that DRLB improves control overhead,the average end to end delay and so on.

load balancing；satellite network routing；traffic regulation；update route；adjustment factor

TP393

A

10.16157/j.issn.0258-7998.2016.05.029

2015-11-18)

罗拥华（1978-），男，硕士，讲师，主要研究方向：网络路由设计。

邬家炜（1950-)，男，硕士，教授，主要研究方向：计算机网络。

中文引用格式：罗拥华，邬家炜.一种高效动态LEO卫星网络流量调节路由算法[J].电子技术应用，2016，42(5)：104-108，112.

英文引用格式：Luo Yonghua，Wu Jiawei.An efficient routing algorithm based on load balancing for dynamic LEO satellite networks[J].Application of Electronic Technique，2016，42(5)：104-108，112.