面向双层卫星网络的多业务负载均衡算法

王　娟, 郭俞江, 孙力娟, 周　剑, 韩　崇

(1. 南京邮电大学计算机学院, 江苏 南京 210003;2. 江苏省无线传感网高技术研究重点实验室, 江苏 南京 210003)



面向双层卫星网络的多业务负载均衡算法

王娟1,2, 郭俞江1,2, 孙力娟1,2, 周剑1,2, 韩崇1,2

(1. 南京邮电大学计算机学院, 江苏 南京 210003;2. 江苏省无线传感网高技术研究重点实验室, 江苏 南京 210003)

卫星网络中由于卫星高动态拓扑和地面用户分布不均,导致卫星网络易出现区域负载失衡。设计高效的动态路由算法是当前卫星网络的研究热点,为此,提出了一种面向双层卫星网络的多业务负载均衡算法。该算法根据卫星链路上的数据传输量进行拥塞判断,根据链路时延因素和链路负载因素进行负载代价计算,不同服务质量(qualityofservice,QoS)需求的业务进行不同路径选择,通过分流均衡网络流量。仿真结果表明,该算法能够减少数据包的排队时延和丢包率,提高整网吞吐量。

负载均衡; 双层卫星网络; 拥塞判断; 负载代价; 多业务分流

0　引　言

地面终端日益小型化和卫星星上处理技术的快速发展[1],使得卫星在军事、商业等领域备受关注。由非静止轨道(non-geostationaryearthorbitsatellite,Non-GEO)卫星组成的网络,在往返时延和地面终端功率方面具有较大优势,并且能够提供广泛地理区域的覆盖和远程地面网络的互联,是现代卫星通信研究的重点[2]。但是,卫星信息资源有限、卫星链路连接不稳定使得卫星在支持高服务质量(qualityofservice,QoS)需求的业务中表现不足[3]。

另外,卫星网络具有高动态拓扑、地面用户分布不均等特点,网络负载容易失衡[4-5],出现部分卫星拥塞而周围卫星未被充分利用的情况,增加了数据包的排队时延和丢包率。因此,有必要对卫星网络的流量进行负载均衡,选择合理的路径进行传输,减小数据包的传播时延和阻塞率。

传统卫星网络路由算法有多层卫星网络路由(multilayersatelliterouting,MLSR)[6]和卫星组管理路由协议(satellitegroupingandroutingprotocol,SGRP)[7]等,主要关注卫星网络的拓扑分片、链路切换、运行开销的优化,却没有考虑网络拥塞时如何进行负载均衡的问题。

考虑卫星网络负载均衡的有紧凑式多路径路由(compactexplicitmulti-pathrouting,CMER)算法[8]和显式负载均衡(explicitloadbalancing,ELB)策略[9]等。CMER同时考虑了传播和队列时延作为链路代价,提高了链路利用率,确保整个卫星系统更好的负载均衡。该算法在单颗卫星链路负载时对链路上传输数据流量的调整明显,但没有考虑到邻接卫星的负载情况。在ELB中,卫星会把自己的拥塞状态通报给自己的邻居卫星,邻居卫星收到信息后更新路由表,搜索其他后备路径,并降低至忙碌或拥塞卫星的数据发送率。文献[10]提出了网络拥塞的预测机制,在人口多、经济发达的地区意味着网络负载业务就比较多,相反地,人口稀少、经济落后地区意味着网络业务负载量就比较少,基于此,达到对网络中业务进行负载均衡传输的目的。上述算法在处理单层卫星网络拥塞时有一定的优势,但是却不适用于多层卫星网络。

多层卫星网络是双层或多层轨道平面同时布星,主要由低轨道(lowearthorbit,LEO)或中轨道(mediumearthorbit,MEO)和同步地球轨道(geostationaryearthorbit,GEO)星座构成的系统,现有的负载均衡路由算法研究中,Hiroki等在2011年提出了一种基于拥塞预估的LEO/GEO双层卫星负载均衡算法[4],在该算法中将地面区域分为正常区域和负载区域;当卫星进入负载区域时,将经过该卫星的数据进行分流。但是,由于卫星在分流时对所有数据包都要通过监测链路队列来决定如何分流,对卫星网络的负担较大。在2012年,Hiroki等又提出了一种针对LEO/MEO双层卫星的负载均衡算法[5],该算法区分地面数据包和卫星数据包,然后根据这些数据包的跳数来采用不同的分流措施。这两种算法没有考虑多业务的QoS需求。文献[11]提出了一种负载均衡的动态路由算法,区分簇内路由、簇间路由和层间路由,通过层内和层间设定不同的拥塞门限值进行路由的触发更新,提高了双层卫星网络可靠性。文献[12]提出了一种基于链路权重自适应调整的流量工程路由算法,网络吞吐量、平均跳数、平均传输时延等性能在GEO/LEO网络中得到优化。文献[13]改进了路由计算使用的经典最短路径优先算法的性能,提出了一种适合网络拓扑动态变化的路由算法,减少了卫星网络路由计算量和路由切换概率。

尽管上述文献已经对卫星网络中的路由控制以及负载均衡机制有所研究,但目前没有文献对卫星网络业务分布的不均匀性、LEO/MEO卫星网络的结构特征以及实现多种业务的QoS特性综合考虑。本文提出了面向双层卫星网络的多业务负载均衡算法,通过拥塞判断和负载代价计算来得到不同的传输路径,然后根据不同业务对QoS的需求进行路径选择。该算法可以有效均衡卫星网络的流量,满足不同数据业务的QoS需求。

1　面向双层卫星网络的多业务负载均衡算法概述

本文针对LEO/MEO双层卫星网络,在该网络中划分4种链路[14]:轨道内星际链路(intra-satellitelink,ISL)、轨道间星际链路(inter-orbitallink,IOL)、层间星际链路(inter-layerinter-satellitelink,ILISL)和用户数据链路(userdatalink,UDL),如图1所示。通过这些链路把双层卫星整合成一个网络,有效地克服了LEO卫星星上处理能力有限、覆盖范围较小和MEO卫星传播时延较大的缺点,利用LEO和MEO各自的优势,对不同业务的传输提供支持。

本文在每个拓扑时间段内(tp)进行链路流量统计[15-16]。首先对链路进行拥塞判断;然后对于负载链路进行负载代价计算;最后根据最短路径算法的思想,分别通过时延代价和负载代价计算得到时延最短路径集(shortestpath,SP)和负载最短路径集(loadshortestpath,LSP),以进行多业务分流。

本文将业务对QoS的需求进行划分,归为话音业务、流媒体业务、数据业务3类业务[17]。话音业务优先级最高,对时延和丢包率较为敏感;流媒体业务较话音业务对时延和丢包率的要求低;数据业务优先级最低,对时延和丢包率的要求不高。

下面分别从拥塞判断、负载代价计算和多业务分流方面来介绍本文算法。

2　拥塞判断

卫星网络中单颗卫星维持着多条链路,这些链路与不同的邻居卫星相连,拥塞情况各不相同。式(1)是链路负载的计算公式[18],用来判断链路的拥塞情况:

(1)

式中,每个tp时间段对链路进行负载计算;λl是该时间段内需要从该链路传输的数据量;ql是该链路在该时间段内的平均队列长度,平均队列长度是在tp时间段内,对tp进行更小的时间段划分,取n个时间段的瞬时队列长的平均值;kq是该队列的缩减率;γl是该链路的目标利用率;Cl是链路的数据发送能力。

对每条链路设定一个拥塞阀值α和 β(α<β)。当α<ρl<β时,标记该条链路的状态为低负载;当ρl>β时,标记该条链路的状态为高负载;当ρl<α时,标记该条链路的状态为正常。

3　负载代价计算

为了使整个网络能够更好地适应流量的变化,对整个网络进行流量分布估算。参照文献[19]按地域人口分布对区域进行的流量预估,结合卫星分布规律,对全球进行了12×6的区域划分,每个小区占30°经度和30°纬度。这样划分可以让卫星系统均匀地分布在这几个小区上。每个小区设定一个流量预估值wi(i为区域编号),当各个卫星进入不同的小区时,卫星获取该小区的流量预估值。每个小区的流量预估值按照用户分布的基本规律,被划分为0～8的预估等级,具体区域的流量预估值设置如图2所示。流量预估值预示着一个区域总体的流量趋势,它反映了停留在该区域的卫星当前链路大致的流量情况。卫星链路的负载,在系统运行的不同时间段会不断变化[10]。流量预估值的作用是提前对链路负载状况进行估算,以便在下一拓扑时间更有效地分流。

图2　区域流量分布图Fig.2　Area flow distribution diagram

Dijkstra最短路径(Dijkstrashortestpath,DSP)路由算法是以链路的传输时延作为链路代价的。因此,DSP算法在路径选择时,仅仅选择时延代价最短的路径,不会考虑链路拥塞情况,导致数据包在某些区域内滞留和丢失。本文通过负载代价变换公式将链路时延因素和链路负载因素进行综合后得到负载代价,在以负载代价选择路径时,可以避开拥塞区域,达到平衡整个网络流量的目的。

卫星链路的负载代价(Cp)变换公式为

(2)

式中,m为双层卫星网络中统一的链路编号; D(ISLi)为链路时延因素;F(ISLi)为链路负载因素，负载因素通过卫星的流量预估值,结合上一时间段链路的拥塞情况得到：

(3)

式中,q是该链路的队列大小; ql是上一时间段tp的队列平均值;wi和wj是该链路两端卫星的流量预估值;u是该函数的缩减系数。为了使得调整的代价在合理的范围内,u在本文中取统一的值。通过增加负载路径的链路代价,在路由计算时,可以使得负载较重链路上的数据包分散到其他负载较轻的链路上。

4　多业务分流

在双层卫星网络中,同时维护着以时延代价计算得到的SP和以负载代价计算得到的LSP,以对不同QoS需求的业务进行分流。其中,负载最短路径计算时把LEO层和MEO层作一个网络,整个网络维护统一的LSP。此外,LEO层和MEO层都独自保存了自己的SP,如图3所示。

图3　数据分流示意图Fig.3　Data distribution diagram

本文多业务分流中,按照优先级从高到低将业务分为话音业务、流媒体业务、数据业务3类,为了保证高优先级业务的QoS,这里引入了优先级队列(priority-queue,PQ)。PQ使用3个子队列,优先级分别是high,medium,low,相应保存话音、流媒体、数据3类业务。PQ会先服务高优先级的子队列,若高优先级子队列里没有数据后,再服务中等优先级子队列,依此类推。每一个子队列都有一个最大队列深度,如果达到了最大队列深度,则进行队尾丢弃。

话音业务具有最高优先级,对QoS要求较高,在传输过程中不对其进行分流,从以时延代价计算得到的LEO最短路径集来进行传输。

流媒体业务和数据业务对QoS要求相对较低,在传输过程中从负载代价计算得到的负载最短路径集上进行传输。

数据业务队列优先级最低,当区域发生拥塞时会首先丢弃数据业务的数据包,导致数据业务的丢包率较大。因此,当数据业务通过LSP高负载区域(ρl>β)时,对其进行MEO分流,直接转移到MEO层的SP路径集中去。其分流的百分比按式(4)计算得到:

(4)

式中,CISL是链路的发送能力;Ic是该条链路业务C的数据发送量。

5　仿真分析

5.1仿真环境

为了验证算法的有效性,采用网络仿真(networksimulator,NS)软件[20]进行仿真与性能分析。仿真采用表1所示的星座参数[21]。MEO层由2个中圆轨道(intermediatecircleorbit,ICO)组成,轨道间由IOL连接;LEO层采用极地轨道Iridium星座。

表1　LEO/MEO双层卫星星座参数

卫星的星间链路带宽设置:下行链路与星间链路的发送速率设为10Mbps;LEO层星间链路的发送速率设为2.5Mbps;MEO层星间链路的发送速率设为25Mbps;LEO和MEO间的链路带宽为25Mbps。数据包大小设为1kB;采用优先级队列,队列大小设为20kB。

算法中的其他参数参照文献[19]设置,如表2所示。

表2　相关参数设置表

地面节点根据文中图2所示的流量分布图设置[22],全球设立100个地面终端,每个地面终端产生2个数据流,总共200个数据流,数据流的走向按照表3所示。每2秒进行链路负载和卫星状态的更新,每10秒进行路由的更新。

表3　数据流图

5.2仿真结果

采用DSP算法作为本文算法的比较对象。在不同数据发送速率下,测试话音业务(A)、流媒体业务(B)、数据业务(C)3类业务的丢包率、吞吐量和时延。

5.2.1数据丢包率

图4是各类业务在不同发送速率下丢包率的比较。从图4可以看出,A类业务具有最高的服务等级,采用最短路径算法在LEO层进行传输,具有低时延和低丢包率,在数据发送率为500kbps时丢包率控制在6%;C类业务优先级最低,链路发生拥塞首先被丢弃,丢包率最高;B类业务和C类业务丢包率曲线陡峭,随着数据发送率的增高而骤然增大,但采用本文算法较DSP算法各业务在数据丢包率方面仍有明显改善。图5是本文算法和DSP算法在不同发送速率下的总丢包率比较。在不同的数据发送速率下,本文算法的丢包率低于DSP算法。

图4　各类业务数据丢包率Fig.4　Data packet dropout of multi-traffic

图5　数据总丢包率Fig.5　Total data packet dropout

5.2.2业务时延

图6是在不同发送速率下,各类业务的时延比较。A类业务和B类业务在本文算法下都保持在低时延的范围内。尤其是A类业务,其对时延的要求较高,一直在0.065s以内;而B类业务的时延也改善明显。C类业务为时延不敏感型业务,本文算法牺牲了C类业务的时延来保证A类业务和B类业务的时延。但在总时延上,如图7所示,本文算法优于DSP算法。

图6　各类业务的端到端平均时延Fig.6　End-to-end average delay of multi-traffic

图7　业务总时延Fig.7　Total traffic delay

5.2.3业务吞吐量

图8是地面终端在不同发送速率下的平均吞吐量,即单位时间内地面终端发送数据量的平均值。随着业务发送速率的增大,本文算法的平均吞吐量较DSP算法改善越来越明显,尤其是在高发送速率下,整网的吞吐量有显著提高。

图8　业务吞吐量Fig.8　Traffic throughput

综上所述,本文算法能够有效均衡网络负载,减少因拥塞所导致的数据丢失与排队时延,提高整个网络的吞吐量。

6　结束语

本文提出了面向双层卫星网络的多业务负载均衡算法。首先,对链路进行拥塞判断;然后,综合时延因素与负载因素对负载链路进行负载代价计算,得到不同的传输路径;最后,对不同QoS需求的业务进行合理的路径选择来进行分流。仿真结果表明,本文算法在网络过载时,能够通过链路代价变换,有效地提高整网的流量均衡性,减少数据的滞留和丢失。

[1]ChoiKS,JoJH,YouMH,etal.UtilizationplansforKabandsatellitecommunicationssystemusingCOMS[C]∥Proc.of the 12th International Conference on Advanced Communication Technology,2010: 561-564.

[2]WangZY,LiDZ,GuoQ,etal.Hierarchicalsatellitenetworkdesignbasedonpermanentinter-satellite-links[C]∥Proc.of the 4th International Conference on Wireless Communications, Networking and Mobile Computing, 2008: 1-4.

[3]JukanA,NguyenHN,VanA,etal.AnapproachtoQoS-basedroutingforLEOsatellitenetworks[C]∥Proc.of the International Conference on Communication Technology Proceedings,2000: 922-929.

[4]NishiyamaH,KudohD,KatoN,etal.LoadbalancingandQoSprovisioningbasedoncongestionpredictionforGEO/LEOhybridsatellitenetworks[J].Proceedings of the IEEE, 2011, 99(11): 1998-2007.

[5]NishiyamaH,TadaY,KatoN,etal.Towardoptimizedtrafficdistributionforefficientnetworkcapacityutilizationintwo-layeredsatellitenetworks[J].IEEE Trans.on Vehicular Technology, 2012, 62(3): 1303-1313.

[6]AkyildizIF,EkiciE,BenderMD.MLSR:anovelroutingalgorithmformultilayeredsatelliteIPnetworks[J].IEEE/ACM Trans.on Networking, 2002, 10(3): 411-424.

[7]ChenC,EkiciE.AroutingprotocolforhierarchicalLEO/MEOsatelliteIPnetworks[J].Wireless Networks, 2005, 11(4): 507-521.

[8]BaiJJ,LuXC,LuZX,etal.Compactexplicitmulti-pathroutingforLEOsatellitenetworks[C]∥Proc.of the Workshop on High Performance Switching and Routing, 2005: 386-390.

[9]TalebT,MashimoD,JamalipourA,etal.ExplicitloadbalancingtechniqueforNGEOsatelliteIPnetworkswithon-boardprocessingcapabilities[J].IEEE/ACM Trans.on Networking, 2009, 17(1): 281-293.

[10]KudohD,KashibuchiK,NishiyamaH,etal.DynamicloadbalancingmethodbasedoncongestionpredictionforIP/LEOsatellitenetworks[J].Institute of Electronics, Information and Communication Engineers Trans.on Communication,2009,29(11):3326-3334.

[11]YaoY,LiangXW.DynamicroutingtechniquebasedonLEO&GEOdouble-layeredsatellitenetwork[J].Systems Engineering and Electronics, 2013, 35(9): 1968-1973. (姚晔,梁旭文.LEO&GEO双层卫星网络的动态路由技术[J].系统工程与电子技术,2013, 35(9): 1968-1973.)

[12]XiaoF,SunLJ,YeXG,etal.RoutingalgorithmforMPLStrafficengineeringinsatellitenetwork[J].Journal on Communications, 2011, 32(5): 104-111. (肖甫,孙力娟,叶晓国,等,面向卫星网络的流量工程路由算法[J].通信学报,2011, 32(5): 104-111.)

[13]GaoLJ,JiangTJ.Analysisondegreeofsatellitenetworkconnectionandanimprovedefficientroutingalgorithm[J].Systems Engineering and Electronics, 2014,36(10):2071-2075.(高丽娟,蒋太杰. 卫星网络连接度与高效路由算法分析与改进[J].系统工程与电子技术,2014,36(10): 2071-2075.)

[14]KadowakiN,SuzukiR.Overviewofthewidebandinternetworkingengineeringtestanddemonstrationsatelliteproject[J].Journal of the National Institute of Information and Communications Technology, 2007, 54(4): 3-10.

[15]EkiciE,AkyildizIF,BenderMD.DatagramroutingalgorithmforLEOsatellitenetworks[C]∥Proc.of the 9th IEEE Annual Joint Conference on Computer and Communications Societies, 2000: 500-508.

[16]WernerM.AdynamicroutingconceptforATM-basedsatellitepersonalcommunicationnetworks[J].IEEE Journal on Selected Areas in Communications, 1997, 15(8): 1636-1648.

[17]JinS,YueW.Performanceevaluationofmulti-trafficonwirelesssensornetworksusinganovelDiffservmechanism[C]∥Proc.of the International Symposium on Wireless Communication Systems, 2011: 377-381.

[18]XiaY,SubramanianL,StoicaI,etal.Onemorebitisenough[J].IEEE/ACM Trans.on Networking,2008,16(6):1281-1294.

[19]ChangHS,KimBW,LeeCG,etal.FSA-basedlinkassignmentandroutinginlow-earthorbitsatellitenetworks[J].IEEE Trans.on Vehicular Technology, 1998, 47(3): 1037-1048.

[20]Thenetworksimulator-ns-2.[EB/OL].[2015-11-20].http:∥www.isi.edu/nsnam/ns/.

[21]PeterT,PeterB.AnalysisandcomparisonofLEOandMEOsatellitenetworks[C]∥Proc.of the Electronics in Marine International Symposium, 2007: 239-242.

[22]MohorcicM,WernerM,SvigeljA,etal.Adaptiveroutingforpacket-orientedintersatellitelinknetworks:performanceinvarioustrafficscenarios[J].IEEE Trans.on Wireless Communications, 2002,1(4): 808-818.

Loadbalancingalgorithmformulti-trafficindoublelayeredsatellitenetwork

WANGJuan1,2,GUOYu-jiang1,2,SUNLi-juan1,2,ZHOUJian1,2,HANChong1,2

(1.School of Computer, Nanjing University of Posts and Telecommunications, Nanjing 210003, China;2. Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks, Nanjing 210003, China)

Duetothehighdynamictopologyofsatellitenetworksandunevendistributionofusers,thesatellitenetworkwillbeoutofbalanceinregionalareas.Designingefficientdynamicroutingalgorithmsbecomesahottopicintheresearchofwirelesssatellitenetwork.Therefore,aloadbalancingalgorithmformulti-trafficindoublelayeredsatellitenetworkisproposed.Thealgorithm,withcongestiondetectionbasedonlinktransmission,andloadcostcalculationaccordingtotimedelayfactorsaswellasloadfactorsanddatadistribution,makesdifferenttransmissionpathstomeetthequalityofservice(QoS)demandsofdifferentbusinessesinordertobalancenetworktraffics.Andthesimulationresultsindicatethatthisalgorithmcouldreducethepacketqueuingdelayandpacketlossrate,andimprovethethroughputofthewholenetwork.

loadbalancing;doublelayeredsatellitenetworks;congestiondetection;loadcost;multi-trafficdiversion

2015-11-27；

2016-05-25；网络优先出版日期：2016-07-07。

国家自然科学基金 (61572261, 71301081);江苏省自然科学基金(BK20130877,BK20150868)资助课题

TP393

ADOI:10.3969/j.issn.1001-506X.2016.09.27

王娟(1982-),女,讲师,博士研究生,主要研究方向为卫星网络、无线传感器网络。

E-mail:juanw@njupt.edu.cn

郭俞江(1989-),男,硕士研究生,主要研究方向为卫星网络。

E-mail:guoyj@yahoo.com

孙力娟(1963-),女,教授,博士,主要研究方向为计算机网络、无线传感器网络。

E-mail:sunlj@njupt.edu.cn

周剑(1984-),男,副教授,博士,主要研究方向为卫星网络、无线传感器网络。

E-mail:zhoujian@njupt.edu.cn

韩崇(1985-),男,讲师,博士,主要研究方向为无线多媒体传感网、数据处理。

E-mail:hc@njupt.edu.cn

网络优先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160707.1739.002.html