面向雙層衛星網絡的多業務負載均衡算法

王　娟, 郭俞江, 孫力娟, 周　劍, 韓　崇

(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