《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計應(yīng)用 > 一種高效動態(tài)LEO衛(wèi)星網(wǎng)絡(luò)流量調(diào)節(jié)路由算法
一種高效動態(tài)LEO衛(wèi)星網(wǎng)絡(luò)流量調(diào)節(jié)路由算法
2016年電子技術(shù)應(yīng)用第5期
羅擁華,,鄔家煒
華南師范大學(xué) 計算機(jī)學(xué)院,,廣東 廣州510631
摘要: 針對考慮負(fù)載均衡的LEO衛(wèi)星網(wǎng)絡(luò)路由算法存在控制網(wǎng)絡(luò)開銷偏大,、路由更新不及時以及流量調(diào)節(jié)機(jī)制分配不均等問題,,提出了一種基于負(fù)載均衡的動態(tài)LEO衛(wèi)星網(wǎng)絡(luò)路由算法DRLB,。根據(jù)衛(wèi)星節(jié)點路徑記錄信息以及后向Agent讀取策略設(shè)計新的路由機(jī)制,,獲得動態(tài)衛(wèi)星拓?fù)浣Y(jié)構(gòu),;分析前向Agent的分組格式并刪除冗余字段,,達(dá)到減小網(wǎng)絡(luò)開銷目的,;根據(jù)數(shù)據(jù)發(fā)送時間間隔構(gòu)造前向Agent選址策略,提高路由更新效率,,通過考慮衛(wèi)星所處緯度流量分配不均問題,,改進(jìn)流量調(diào)節(jié)因子,獲得更好的負(fù)載均衡效果,。仿真結(jié)果表明,,與SDRZ-MA算法相比,DRLB算法在減緩星地之間的控制開銷,、平均端到端時延等方面具有較好的優(yōu)勢,。
中圖分類號: TP393
文獻(xiàn)標(biāo)識碼: A
DOI:10.16157/j.issn.0258-7998.2016.05.029
中文引用格式: 羅擁華,鄔家煒. 一種高效動態(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.
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
Abstract: 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.
Key words : load balancing,;satellite network routing;traffic regulation,;update route,;adjustment factor

0 引言

    LEO衛(wèi)星網(wǎng)絡(luò)具有動態(tài)變化的拓?fù)浣Y(jié)構(gòu),拓?fù)湟恢倍荚诳焖僮兓?,這是LEO衛(wèi)星網(wǎng)絡(luò)區(qū)別于地面自組織網(wǎng)絡(luò)的主要特點,,而且衛(wèi)星的存儲能力和處理能力有限[1-2]。同時,,衛(wèi)星間的距離很遠(yuǎn),,容易導(dǎo)致較大的端到端傳輸時延[3]

    對此,,研究人員提出了一些基于負(fù)載均衡的路由機(jī)制,,如ELB算法[4]是由TALEB T提出的,該算法主要是將衛(wèi)星節(jié)點在發(fā)送或轉(zhuǎn)發(fā)數(shù)據(jù)分組前已經(jīng)獲取到了下一跳節(jié)點的鏈路負(fù)載狀況,,依次作為依據(jù),,為數(shù)據(jù)分組選擇合適的轉(zhuǎn)發(fā)路徑。但如果網(wǎng)絡(luò)中出現(xiàn)的擁塞節(jié)點過多時,,該算法性能會降低甚至失效,。KUCUKATES R等人[5]提出了PAR算法,該算法是在網(wǎng)絡(luò)擁塞發(fā)生前及時采取措施進(jìn)行避免,,從而實現(xiàn)網(wǎng)絡(luò)負(fù)載均衡的效果,。但是該算法網(wǎng)絡(luò)吞吐量不高,同時分組端到端時延也比較大,。SDRZ-MA算法[6]將Agent引入到LEO衛(wèi)星網(wǎng)路由中,,其衛(wèi)星節(jié)點定時產(chǎn)生前向Agent在衛(wèi)星節(jié)點間來回轉(zhuǎn)發(fā),遷移過程中收集衛(wèi)星緯度,、鏈路代價等路由更新所需信息,。但SDRZ-MA算法存在部分衛(wèi)星負(fù)載過重,、其他衛(wèi)星資源開發(fā)不足的問題。

    對此,,本文基于SDRZ-MA算法思想,,提出了基于負(fù)載均衡的動態(tài)LEO衛(wèi)星網(wǎng)絡(luò)路由算法DRLB(Dynamic Routing Algorithm based on Load Balance)。分析前向,、后向Agent如何讀取路由機(jī)制,,并設(shè)計新的路由策略以及優(yōu)化前向Agent的分組長度,改進(jìn)流量調(diào)節(jié)因子函數(shù),,使網(wǎng)絡(luò)流量更適應(yīng)具體維度位置,。最后,測試了本文路由算法在控制開銷,、流量調(diào)節(jié)以及平均端到端時延等方面的性能,。

1 網(wǎng)絡(luò)模型及問題描述

1.1 網(wǎng)絡(luò)模型及相關(guān)定義

    在本文DRLB算法中,用Walker星座[7-8]進(jìn)行組網(wǎng),,該算法是將衛(wèi)星網(wǎng)絡(luò)抽象看作一個由一組節(jié)點V和一組邊E組成的無向連通圖G=(V,E),。其中,,|V|為網(wǎng)絡(luò)中所有衛(wèi)星節(jié)點的個數(shù),|E|是網(wǎng)絡(luò)中所有星際鏈路的個數(shù),。算法相關(guān)定義為:

tx7-gs1-2.gif

1.2 問題描述

    通過對考慮負(fù)載均衡的具有代表性的LEO衛(wèi)星網(wǎng)絡(luò)路由算法SDRZ-MA進(jìn)行研究,,發(fā)現(xiàn)該算法存在以下問題:

    (1)因地面業(yè)務(wù)熱點集中在北半球,尤其是北緯50°以內(nèi),,原始SDRZ-MA算法設(shè)計了tx7-1.2-x1.giftx7-1.2-x1.gif代價調(diào)節(jié)因子,,以促使流量由北半球向南半球分配,但代價調(diào)節(jié)因子tx7-1.2-x1.gif的設(shè)計存在缺陷,;

    (2)在SDRZ-MA算法中,,衛(wèi)星星座運行一個周期后,每個衛(wèi)星節(jié)點僅以概率qd的值來確定前向Agent的目的衛(wèi)星地址,,這不夠全面,,會導(dǎo)致衛(wèi)星節(jié)點對于全網(wǎng)的拓?fù)湫畔@取得不夠及時準(zhǔn)確;

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

2 本文DRLB算法

    由于基于移動Agent的LEO衛(wèi)星網(wǎng)絡(luò)路由算法存在網(wǎng)絡(luò)控制開銷偏大,、流量調(diào)節(jié)機(jī)制不合理的問題,本文提出了基于負(fù)載均衡的動態(tài)LEO衛(wèi)星網(wǎng)絡(luò)路由算法DRLB,。

2.1 流量調(diào)節(jié)因子的改進(jìn)

    在SDRZ-MA算法中,,調(diào)節(jié)因子tx7-1.2-x1.gif的函數(shù)如下:

    tx7-gs3.gif

    其函數(shù)見圖1(a)。依圖可知,,當(dāng)緯度大于北緯50°后,,調(diào)節(jié)因子的曲線走勢仍繼續(xù)向上,,這顯然不符合實際情況。對此,,本文考慮衛(wèi)星緯度具體地理位置,,對模型(3)進(jìn)行修正,形成新的流量調(diào)節(jié)因子模型:

    tx7-gs4.gif

    新的調(diào)節(jié)因子的函數(shù)見圖1(b),。依圖可知,,改進(jìn)后的調(diào)節(jié)因子可以保證北半球的權(quán)值始終大于南半球,其中0°~50°的權(quán)值最大,,這更符合實際的業(yè)務(wù)分布狀況,。

tx7-t1.gif

2.2 優(yōu)化前向Agent目的衛(wèi)星的選取策略

    在SDRZ-MA算法中,衛(wèi)星節(jié)點會定期向其他衛(wèi)星發(fā)送前向Agent,,該前向Agent的目的地址以概率qd來確定:

    tx7-gs5.gif

其中,,fsd表示從源衛(wèi)星s向目的衛(wèi)星d發(fā)送的數(shù)據(jù)總量。在SDRZ-MA算法中,,會出現(xiàn)短時間內(nèi)重復(fù)產(chǎn)生同一目的地址的前向Agent的情況,。為此,本文通過(前向Agent發(fā)送時間間隔來避免重復(fù)發(fā)送的問題,。在本文DRLB算法中,,衛(wèi)星節(jié)點在發(fā)送前向Agent的時間間隔內(nèi),記錄本時間段內(nèi)經(jīng)過自己的其他衛(wèi)星節(jié)點產(chǎn)生的前向Agent的目的地址,。當(dāng)某一衛(wèi)星節(jié)點需要發(fā)送自己的前向Agent時,,首先排除自己記錄的前向Agent的目的地址,然后再按概率qd選擇前向Agent的目的地址,,這樣衛(wèi)星節(jié)點能夠獲取更準(zhǔn)確的網(wǎng)絡(luò)負(fù)載狀況,,尋找最優(yōu)路徑。

2.3 壓縮Agent分組長度

tx7-2.3-x1.gif

tx7-2.3-x2.gif

2.4 DRLB算法規(guī)則及基本操作

2.4.1 算法規(guī)則

    (1)規(guī)則1

    路由表初始化:

    tx7-gs6.gif

    (2)規(guī)則2

    ①在網(wǎng)絡(luò)運行的第一個周期內(nèi),,所有衛(wèi)星節(jié)點會定時生成前向Agent,,前向Agent的目的地址從本衛(wèi)星外的其他衛(wèi)星節(jié)點中隨機(jī)選取。

    ②第二個周期開始,,每個衛(wèi)星節(jié)點在生成前向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é)點的路由表來選擇下一跳,。若存在鏈路不可用時,,則先排除不可用的鏈路,并對該衛(wèi)星的路由表重新更新,,再選擇下一跳,。

    ②前向Agent生成后向Agent,,生成的后向Agent沿該前向反方向移動。

    (4)規(guī)則4

    當(dāng)下面的任意一個條件成立時,,前向Agent生成后向Agent,,前向Agent消失:

    ①前向移動Agent達(dá)到其壽命期。

    ②前向Agent根據(jù)規(guī)則3選擇下一跳時,,選擇的下一跳衛(wèi)星已經(jīng)被該前向Agent訪問過或沒有可用的路徑,。

    (5)規(guī)則5

    ①網(wǎng)絡(luò)代價模型的更新:

tx7-gs7-8.gif

2.4.2 具體步驟

    (1)所有節(jié)點按規(guī)則1完成路由表的初始化工作。

    (2)衛(wèi)星節(jié)點s根據(jù)規(guī)則2產(chǎn)生一個具有一定壽命的前向Agent Fs,,在遷移期間,,Agent Fs記錄每個被訪問節(jié)點Vi的地址,最后一個被訪問節(jié)點的緯度和該節(jié)點的上一個跳節(jié)點到本節(jié)點的代價,。當(dāng)Agent Fs到達(dá)中間衛(wèi)星節(jié)點后,,中間衛(wèi)星節(jié)點根據(jù)Agent Fs攜帶的信息更新自己所處的緯度位置以及上一節(jié)點到本衛(wèi)星節(jié)點的代價。當(dāng)Agent Fs到達(dá)目的衛(wèi)星節(jié)點時,,所攜帶的信息格式為:tx7-2.4.2-x1.gif

    (3)前向Agent在遷移過程中根據(jù)規(guī)則3來進(jìn)行路由選擇,,當(dāng)規(guī)則4要求的任意一個條件滿足時,前向Agent生成后向Agent Bd,。

    (4)前向移動Agent Fs將自己攜帶的路由更新所需信息壓入到后向Agent Bd的內(nèi)存中,,同時自身壽命結(jié)束。

    (5)后向Agent Bd沿前向反方向遷移,。當(dāng)遷移到路由中間節(jié)點Vi時,讀取中間節(jié)點記錄的自己的緯度和在該緯度位置時上一節(jié)點到本節(jié)點的代價,,存入堆棧,,同時獲取下一跳節(jié)點信息繼續(xù)遷移,直至遷移到源節(jié)點,,每經(jīng)過一個中間節(jié)點,,按照規(guī)則5更新節(jié)點的路由表tx7-2.4.2-x5.gif和網(wǎng)絡(luò)代價統(tǒng)計模型tx7-2.4.2-x2.gif如果通往下一跳節(jié)點的鏈路不可用,則后向Agent Bd自動銷毀,。后前Agent到達(dá)源節(jié)點后,,其內(nèi)存信息為:tx7-2.4.2-x3.giftx7-2.4.2-x4.gif

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

tx7-t2.gif

3 仿真和性能分析

3.1 仿真環(huán)境設(shè)置

    本文借助仿真軟件是OPNET14.5來測試本文路由算法的網(wǎng)路性能[9-10],。為了模擬實際的衛(wèi)星網(wǎng)絡(luò)的流量分布,,仿真中衛(wèi)星在北緯0°~50°之間衛(wèi)星節(jié)點每發(fā)送0.4 s數(shù)據(jù)包停止0.8 s,其他非極地區(qū)域衛(wèi)星節(jié)點每發(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算法視為對照組,,并取α=3,,β=5,,η=0.8。星座拓?fù)浞抡鎱?shù)如表1所示,。

tx7-b1.gif

    為了量化本文算法與對照組算法的網(wǎng)絡(luò)性能,,本文用丟包率、平均端到端時延與歸一化ISL負(fù)載等指標(biāo)[11]來評估,。

3.2 實驗數(shù)據(jù)與分析

    (1)丟包率

    如圖3所示,,SDRZ-MA算法和DRLB算法在終端比特率小于400 kb/s時,丟包率都接近0,,這是由于這時網(wǎng)絡(luò)比較空閑,,數(shù)據(jù)包能夠及時準(zhǔn)確地送達(dá)目的節(jié)點。當(dāng)終端數(shù)據(jù)量增大時,,DRLB算法的丟包要小于SDRZ-MA算法,,這是由于調(diào)節(jié)因子的改進(jìn)使得全網(wǎng)流量得到了合理分配,同時根據(jù)節(jié)點的流量排序選取前向Agent目的節(jié)點,,避免了重復(fù)向同一節(jié)點連續(xù)發(fā)送前向Agent的情況,,節(jié)點對全網(wǎng)的負(fù)載信息獲得更加準(zhǔn)確;而SDRZ-MA算法沒有考慮到衛(wèi)星通信中節(jié)點移動速率巨大導(dǎo)致的流量分配難題,,使其丟包率較高,。

tx7-t3.gif

    (2)平均端到端時延

    平均端到端時延隨終端變化率見圖4、圖5,。圖4中數(shù)據(jù)源衛(wèi)星和目的衛(wèi)星都在北半球,,此時DRLB算法的性能明顯優(yōu)于SDRZ-MA算法,這是由于DRLB算法針對地面人口和大陸板塊的分布現(xiàn)實狀況,,設(shè)計新的流量調(diào)節(jié)因子,,更好地將網(wǎng)絡(luò)流量分配到南半球,最大程度上避免了由于鏈路擁塞而造成數(shù)據(jù)分組在衛(wèi)星節(jié)點長時間緩存得不到轉(zhuǎn)發(fā)的情況,。

tx7-t4.gif

tx7-t5.gif

    圖5中數(shù)據(jù)源衛(wèi)星和目的衛(wèi)星都在南半球中,,兩種算法的端到端時延差不多,但在新算法中前向Agent的目的地址的選取策略得到優(yōu)化,,降低了重復(fù)獲取某若干條鏈路負(fù)載信息的概率,,使節(jié)點獲得準(zhǔn)確的全網(wǎng)負(fù)載信息來更新路由表,因此DRLB算法的平均端到端時延稍微好一點,。

    (3)歸一化ISL負(fù)載

    歸一化ISL負(fù)載隨衛(wèi)星緯度的變化如圖6所示,,在南半球DRLB算法的鏈路負(fù)載要大于SDRZ-MA算法,北緯大約0°~50°之間,,DRLB算法中鏈路負(fù)載要小于原SDRZ-MA算法,。這是由于本文算法對流量調(diào)節(jié)因子進(jìn)行了改進(jìn),增加了0°到北緯50°間的鏈路代價權(quán)值,,使得業(yè)務(wù)流量更多的被分配到了南半球,。同時,,該算法對前向Agent的目的地址的選取進(jìn)行了改進(jìn),提高了路徑更新的效率,,衛(wèi)星節(jié)點更好地獲得網(wǎng)絡(luò)的負(fù)載狀況,,進(jìn)一步實現(xiàn)了流量的再分配。而SDRZ-MA算法在衛(wèi)星節(jié)點移動速率巨大時不能動態(tài)對鏈路業(yè)務(wù)流量進(jìn)行分配,,導(dǎo)致網(wǎng)絡(luò)出現(xiàn)較大的擁塞,。

tx7-t6.gif

4 結(jié)論

    針對考慮負(fù)載均衡的LEO衛(wèi)星網(wǎng)絡(luò)路由算法網(wǎng)絡(luò)控制開銷偏大以及流量調(diào)節(jié)機(jī)制存在缺陷等問題,提出了基于負(fù)載均衡的動態(tài)LEO衛(wèi)星網(wǎng)絡(luò)路由算法DRLB,。在DRLB算法中,,路由更新所需信息采用由衛(wèi)星節(jié)點記錄、后向Agent讀取策略,,減小前向Agent的分組長度,,降低網(wǎng)絡(luò)控制開銷;對前向Agent目的地址的選取策略進(jìn)行改進(jìn),,提高路由更新的效率,;優(yōu)化流量調(diào)節(jié)機(jī)制,更好地實現(xiàn)網(wǎng)絡(luò)負(fù)載均衡,。理論分析和仿真結(jié)果表明,,與SDRZ-MA算法相比,DRLB算法在丟包率,、平均端到端時延等方面的性能均有所提高,。

參考文獻(xiàn)

[1] 韋娟,薄振雨,,劉葉.基于分時的LEO衛(wèi)星網(wǎng)絡(luò)非對稱路由算法[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ī)會網(wǎng)絡(luò)中基于定向數(shù)據(jù)傳輸?shù)牡乩砺酚伤惴╗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.

此內(nèi)容為AET網(wǎng)站原創(chuàng),,未經(jīng)授權(quán)禁止轉(zhuǎn)載。