文獻(xiàn)標(biāo)識(shí)碼: A
DOI:10.16157/j.issn.0258-7998.2016.05.029
中文引用格式: 羅擁華,,鄔家煒. 一種高效動(dòng)態(tài)LEO衛(wèi)星網(wǎng)絡(luò)流量調(diào)節(jié)路由算法[J].電子技術(shù)應(yīng)用,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.
0 引言
LEO衛(wèi)星網(wǎng)絡(luò)具有動(dòng)態(tài)變化的拓?fù)浣Y(jié)構(gòu),,拓?fù)湟恢倍荚诳焖僮兓?,這是LEO衛(wèi)星網(wǎng)絡(luò)區(qū)別于地面自組織網(wǎng)絡(luò)的主要特點(diǎn),而且衛(wèi)星的存儲(chǔ)能力和處理能力有限[1-2],。同時(shí),,衛(wèi)星間的距離很遠(yuǎn),容易導(dǎo)致較大的端到端傳輸時(shí)延[3],。
對(duì)此,,研究人員提出了一些基于負(fù)載均衡的路由機(jī)制,如ELB算法[4]是由TALEB T提出的,,該算法主要是將衛(wèi)星節(jié)點(diǎn)在發(fā)送或轉(zhuǎn)發(fā)數(shù)據(jù)分組前已經(jīng)獲取到了下一跳節(jié)點(diǎn)的鏈路負(fù)載狀況,,依次作為依據(jù),為數(shù)據(jù)分組選擇合適的轉(zhuǎn)發(fā)路徑,。但如果網(wǎng)絡(luò)中出現(xiàn)的擁塞節(jié)點(diǎn)過多時(shí),,該算法性能會(huì)降低甚至失效。KUCUKATES R等人[5]提出了PAR算法,,該算法是在網(wǎng)絡(luò)擁塞發(fā)生前及時(shí)采取措施進(jìn)行避免,,從而實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載均衡的效果。但是該算法網(wǎng)絡(luò)吞吐量不高,,同時(shí)分組端到端時(shí)延也比較大,。SDRZ-MA算法[6]將Agent引入到LEO衛(wèi)星網(wǎng)路由中,其衛(wèi)星節(jié)點(diǎn)定時(shí)產(chǎn)生前向Agent在衛(wèi)星節(jié)點(diǎn)間來回轉(zhuǎn)發(fā),遷移過程中收集衛(wèi)星緯度,、鏈路代價(jià)等路由更新所需信息,。但SDRZ-MA算法存在部分衛(wèi)星負(fù)載過重、其他衛(wèi)星資源開發(fā)不足的問題,。
對(duì)此,,本文基于SDRZ-MA算法思想,提出了基于負(fù)載均衡的動(dòng)態(tài)LEO衛(wèi)星網(wǎng)絡(luò)路由算法DRLB(Dynamic Routing Algorithm based on Load Balance),。分析前向,、后向Agent如何讀取路由機(jī)制,并設(shè)計(jì)新的路由策略以及優(yōu)化前向Agent的分組長(zhǎng)度,,改進(jìn)流量調(diào)節(jié)因子函數(shù),,使網(wǎng)絡(luò)流量更適應(yīng)具體維度位置。最后,,測(cè)試了本文路由算法在控制開銷,、流量調(diào)節(jié)以及平均端到端時(shí)延等方面的性能。
1 網(wǎng)絡(luò)模型及問題描述
1.1 網(wǎng)絡(luò)模型及相關(guān)定義
在本文DRLB算法中,,用Walker星座[7-8]進(jìn)行組網(wǎng),,該算法是將衛(wèi)星網(wǎng)絡(luò)抽象看作一個(gè)由一組節(jié)點(diǎn)V和一組邊E組成的無向連通圖G=(V,E),。其中,,|V|為網(wǎng)絡(luò)中所有衛(wèi)星節(jié)點(diǎn)的個(gè)數(shù),|E|是網(wǎng)絡(luò)中所有星際鏈路的個(gè)數(shù),。算法相關(guān)定義為:
1.2 問題描述
通過對(duì)考慮負(fù)載均衡的具有代表性的LEO衛(wèi)星網(wǎng)絡(luò)路由算法SDRZ-MA進(jìn)行研究,,發(fā)現(xiàn)該算法存在以下問題:
(1)因地面業(yè)務(wù)熱點(diǎn)集中在北半球,尤其是北緯50°以內(nèi),,原始SDRZ-MA算法設(shè)計(jì)了代價(jià)調(diào)節(jié)因子,,以促使流量由北半球向南半球分配,但代價(jià)調(diào)節(jié)因子
的設(shè)計(jì)存在缺陷,;
(2)在SDRZ-MA算法中,,衛(wèi)星星座運(yùn)行一個(gè)周期后,每個(gè)衛(wèi)星節(jié)點(diǎn)僅以概率qd的值來確定前向Agent的目的衛(wèi)星地址,,這不夠全面,,會(huì)導(dǎo)致衛(wèi)星節(jié)點(diǎn)對(duì)于全網(wǎng)的拓?fù)湫畔@取得不夠及時(shí)準(zhǔn)確;
(3)前向Agent分組存在冗余字段,。
2 本文DRLB算法
由于基于移動(dòng)Agent的LEO衛(wèi)星網(wǎng)絡(luò)路由算法存在網(wǎng)絡(luò)控制開銷偏大,、流量調(diào)節(jié)機(jī)制不合理的問題,本文提出了基于負(fù)載均衡的動(dòng)態(tài)LEO衛(wèi)星網(wǎng)絡(luò)路由算法DRLB,。
2.1 流量調(diào)節(jié)因子的改進(jìn)
在SDRZ-MA算法中,,調(diào)節(jié)因子的函數(shù)如下:
其函數(shù)見圖1(a),。依圖可知,當(dāng)緯度大于北緯50°后,,調(diào)節(jié)因子的曲線走勢(shì)仍繼續(xù)向上,,這顯然不符合實(shí)際情況。對(duì)此,,本文考慮衛(wèi)星緯度具體地理位置,,對(duì)模型(3)進(jìn)行修正,形成新的流量調(diào)節(jié)因子模型:
新的調(diào)節(jié)因子的函數(shù)見圖1(b),。依圖可知,,改進(jìn)后的調(diào)節(jié)因子可以保證北半球的權(quán)值始終大于南半球,其中0°~50°的權(quán)值最大,,這更符合實(shí)際的業(yè)務(wù)分布狀況,。
2.2 優(yōu)化前向Agent目的衛(wèi)星的選取策略
在SDRZ-MA算法中,衛(wèi)星節(jié)點(diǎn)會(huì)定期向其他衛(wèi)星發(fā)送前向Agent,,該前向Agent的目的地址以概率qd來確定:
其中,fsd表示從源衛(wèi)星s向目的衛(wèi)星d發(fā)送的數(shù)據(jù)總量,。在SDRZ-MA算法中,,會(huì)出現(xiàn)短時(shí)間內(nèi)重復(fù)產(chǎn)生同一目的地址的前向Agent的情況。為此,,本文通過(前向Agent發(fā)送時(shí)間間隔來避免重復(fù)發(fā)送的問題,。在本文DRLB算法中,衛(wèi)星節(jié)點(diǎn)在發(fā)送前向Agent的時(shí)間間隔內(nèi),,記錄本時(shí)間段內(nèi)經(jīng)過自己的其他衛(wèi)星節(jié)點(diǎn)產(chǎn)生的前向Agent的目的地址,。當(dāng)某一衛(wèi)星節(jié)點(diǎn)需要發(fā)送自己的前向Agent時(shí),首先排除自己記錄的前向Agent的目的地址,,然后再按概率qd選擇前向Agent的目的地址,,這樣衛(wèi)星節(jié)點(diǎn)能夠獲取更準(zhǔn)確的網(wǎng)絡(luò)負(fù)載狀況,尋找最優(yōu)路徑,。
2.3 壓縮Agent分組長(zhǎng)度
2.4 DRLB算法規(guī)則及基本操作
2.4.1 算法規(guī)則
(1)規(guī)則1
路由表初始化:
(2)規(guī)則2
①在網(wǎng)絡(luò)運(yùn)行的第一個(gè)周期內(nèi),,所有衛(wèi)星節(jié)點(diǎn)會(huì)定時(shí)生成前向Agent,前向Agent的目的地址從本衛(wèi)星外的其他衛(wèi)星節(jié)點(diǎn)中隨機(jī)選取,。
②第二個(gè)周期開始,,每個(gè)衛(wèi)星節(jié)點(diǎn)在生成前向Agent前,首先排除前向Agent產(chǎn)生間隔內(nèi)該衛(wèi)星記錄的經(jīng)過自己的前向Agent的目的衛(wèi)星地址,,然后再按概率qd選擇Agent的目的地址,,前向Agent生成后發(fā)送給鄰居衛(wèi)星。
(3)規(guī)則3
①前向Agent到達(dá)中間衛(wèi)星后,,根據(jù)該衛(wèi)星節(jié)點(diǎn)的路由表來選擇下一跳,。若存在鏈路不可用時(shí),,則先排除不可用的鏈路,并對(duì)該衛(wèi)星的路由表重新更新,,再選擇下一跳,。
②前向Agent生成后向Agent,生成的后向Agent沿該前向反方向移動(dòng),。
(4)規(guī)則4
當(dāng)下面的任意一個(gè)條件成立時(shí),,前向Agent生成后向Agent,前向Agent消失:
①前向移動(dòng)Agent達(dá)到其壽命期,。
②前向Agent根據(jù)規(guī)則3選擇下一跳時(shí),,選擇的下一跳衛(wèi)星已經(jīng)被該前向Agent訪問過或沒有可用的路徑。
(5)規(guī)則5
①網(wǎng)絡(luò)代價(jià)模型的更新:
2.4.2 具體步驟
(1)所有節(jié)點(diǎn)按規(guī)則1完成路由表的初始化工作,。
(2)衛(wèi)星節(jié)點(diǎn)s根據(jù)規(guī)則2產(chǎn)生一個(gè)具有一定壽命的前向Agent Fs,,在遷移期間,Agent Fs記錄每個(gè)被訪問節(jié)點(diǎn)Vi的地址,,最后一個(gè)被訪問節(jié)點(diǎn)的緯度和該節(jié)點(diǎn)的上一個(gè)跳節(jié)點(diǎn)到本節(jié)點(diǎn)的代價(jià),。當(dāng)Agent Fs到達(dá)中間衛(wèi)星節(jié)點(diǎn)后,中間衛(wèi)星節(jié)點(diǎn)根據(jù)Agent Fs攜帶的信息更新自己所處的緯度位置以及上一節(jié)點(diǎn)到本衛(wèi)星節(jié)點(diǎn)的代價(jià),。當(dāng)Agent Fs到達(dá)目的衛(wèi)星節(jié)點(diǎn)時(shí),,所攜帶的信息格式為:
(3)前向Agent在遷移過程中根據(jù)規(guī)則3來進(jìn)行路由選擇,當(dāng)規(guī)則4要求的任意一個(gè)條件滿足時(shí),,前向Agent生成后向Agent Bd,。
(4)前向移動(dòng)Agent Fs將自己攜帶的路由更新所需信息壓入到后向Agent Bd的內(nèi)存中,同時(shí)自身壽命結(jié)束,。
(5)后向Agent Bd沿前向反方向遷移,。當(dāng)遷移到路由中間節(jié)點(diǎn)Vi時(shí),讀取中間節(jié)點(diǎn)記錄的自己的緯度和在該緯度位置時(shí)上一節(jié)點(diǎn)到本節(jié)點(diǎn)的代價(jià),,存入堆棧,,同時(shí)獲取下一跳節(jié)點(diǎn)信息繼續(xù)遷移,直至遷移到源節(jié)點(diǎn),,每經(jīng)過一個(gè)中間節(jié)點(diǎn),,按照規(guī)則5更新節(jié)點(diǎn)的路由表和網(wǎng)絡(luò)代價(jià)統(tǒng)計(jì)模型
如果通往下一跳節(jié)點(diǎn)的鏈路不可用,則后向Agent Bd自動(dòng)銷毀,。后前Agent到達(dá)源節(jié)點(diǎn)后,,其內(nèi)存信息為:
本文DRLB算法Agent工作流程如圖2所示。
3 仿真和性能分析
3.1 仿真環(huán)境設(shè)置
本文借助仿真軟件是OPNET14.5來測(cè)試本文路由算法的網(wǎng)路性能[9-10],。為了模擬實(shí)際的衛(wèi)星網(wǎng)絡(luò)的流量分布,,仿真中衛(wèi)星在北緯0°~50°之間衛(wèi)星節(jié)點(diǎn)每發(fā)送0.4 s數(shù)據(jù)包停止0.8 s,其他非極地區(qū)域衛(wèi)星節(jié)點(diǎn)每發(fā)送0.1 s數(shù)據(jù)包停止1.1 s,,數(shù)據(jù)包的目的地址隨機(jī),。為了體現(xiàn)本文算法的先進(jìn)性,,將當(dāng)前LEO衛(wèi)星網(wǎng)路由性能較好的SDRZ-MA算法視為對(duì)照組,并取α=3,,β=5,,η=0.8。星座拓?fù)浞抡鎱?shù)如表1所示,。
為了量化本文算法與對(duì)照組算法的網(wǎng)絡(luò)性能,,本文用丟包率、平均端到端時(shí)延與歸一化ISL負(fù)載等指標(biāo)[11]來評(píng)估,。
3.2 實(shí)驗(yàn)數(shù)據(jù)與分析
(1)丟包率
如圖3所示,,SDRZ-MA算法和DRLB算法在終端比特率小于400 kb/s時(shí),丟包率都接近0,,這是由于這時(shí)網(wǎng)絡(luò)比較空閑,,數(shù)據(jù)包能夠及時(shí)準(zhǔn)確地送達(dá)目的節(jié)點(diǎn)。當(dāng)終端數(shù)據(jù)量增大時(shí),,DRLB算法的丟包要小于SDRZ-MA算法,,這是由于調(diào)節(jié)因子的改進(jìn)使得全網(wǎng)流量得到了合理分配,同時(shí)根據(jù)節(jié)點(diǎn)的流量排序選取前向Agent目的節(jié)點(diǎn),,避免了重復(fù)向同一節(jié)點(diǎn)連續(xù)發(fā)送前向Agent的情況,,節(jié)點(diǎn)對(duì)全網(wǎng)的負(fù)載信息獲得更加準(zhǔn)確;而SDRZ-MA算法沒有考慮到衛(wèi)星通信中節(jié)點(diǎn)移動(dòng)速率巨大導(dǎo)致的流量分配難題,,使其丟包率較高。
(2)平均端到端時(shí)延
平均端到端時(shí)延隨終端變化率見圖4,、圖5,。圖4中數(shù)據(jù)源衛(wèi)星和目的衛(wèi)星都在北半球,此時(shí)DRLB算法的性能明顯優(yōu)于SDRZ-MA算法,,這是由于DRLB算法針對(duì)地面人口和大陸板塊的分布現(xiàn)實(shí)狀況,,設(shè)計(jì)新的流量調(diào)節(jié)因子,更好地將網(wǎng)絡(luò)流量分配到南半球,,最大程度上避免了由于鏈路擁塞而造成數(shù)據(jù)分組在衛(wèi)星節(jié)點(diǎn)長(zhǎng)時(shí)間緩存得不到轉(zhuǎn)發(fā)的情況,。
圖5中數(shù)據(jù)源衛(wèi)星和目的衛(wèi)星都在南半球中,兩種算法的端到端時(shí)延差不多,,但在新算法中前向Agent的目的地址的選取策略得到優(yōu)化,,降低了重復(fù)獲取某若干條鏈路負(fù)載信息的概率,使節(jié)點(diǎn)獲得準(zhǔn)確的全網(wǎng)負(fù)載信息來更新路由表,,因此DRLB算法的平均端到端時(shí)延稍微好一點(diǎn),。
(3)歸一化ISL負(fù)載
歸一化ISL負(fù)載隨衛(wèi)星緯度的變化如圖6所示,在南半球DRLB算法的鏈路負(fù)載要大于SDRZ-MA算法,,北緯大約0°~50°之間,,DRLB算法中鏈路負(fù)載要小于原SDRZ-MA算法,。這是由于本文算法對(duì)流量調(diào)節(jié)因子進(jìn)行了改進(jìn),增加了0°到北緯50°間的鏈路代價(jià)權(quán)值,,使得業(yè)務(wù)流量更多的被分配到了南半球,。同時(shí),該算法對(duì)前向Agent的目的地址的選取進(jìn)行了改進(jìn),,提高了路徑更新的效率,,衛(wèi)星節(jié)點(diǎn)更好地獲得網(wǎng)絡(luò)的負(fù)載狀況,進(jìn)一步實(shí)現(xiàn)了流量的再分配,。而SDRZ-MA算法在衛(wèi)星節(jié)點(diǎn)移動(dòng)速率巨大時(shí)不能動(dòng)態(tài)對(duì)鏈路業(yè)務(wù)流量進(jìn)行分配,,導(dǎo)致網(wǎng)絡(luò)出現(xiàn)較大的擁塞。
4 結(jié)論
針對(duì)考慮負(fù)載均衡的LEO衛(wèi)星網(wǎng)絡(luò)路由算法網(wǎng)絡(luò)控制開銷偏大以及流量調(diào)節(jié)機(jī)制存在缺陷等問題,,提出了基于負(fù)載均衡的動(dòng)態(tài)LEO衛(wèi)星網(wǎng)絡(luò)路由算法DRLB,。在DRLB算法中,路由更新所需信息采用由衛(wèi)星節(jié)點(diǎn)記錄,、后向Agent讀取策略,,減小前向Agent的分組長(zhǎng)度,降低網(wǎng)絡(luò)控制開銷,;對(duì)前向Agent目的地址的選取策略進(jìn)行改進(jìn),,提高路由更新的效率;優(yōu)化流量調(diào)節(jié)機(jī)制,,更好地實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載均衡,。理論分析和仿真結(jié)果表明,與SDRZ-MA算法相比,,DRLB算法在丟包率,、平均端到端時(shí)延等方面的性能均有所提高。
參考文獻(xiàn)
[1] 韋娟,,薄振雨,,劉葉.基于分時(shí)的LEO衛(wèi)星網(wǎng)絡(luò)非對(duì)稱路由算法[J].計(jì)算機(jī)科學(xué)與探索,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ī)會(huì)網(wǎng)絡(luò)中基于定向數(shù)據(jù)傳輸?shù)牡乩砺酚伤惴╗J].計(jì)算機(jī)應(yīng)用,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.