羅擁華，鄔家煒

(華南師范大學 計算機學院，廣東 廣州 510631)

一種高效動態(tài)LEO衛(wèi)星網(wǎng)絡流量調(diào)節(jié)路由算法

羅擁華，鄔家煒

(華南師范大學 計算機學院，廣東 廣州 510631)

針對考慮負載均衡的LEO衛(wèi)星網(wǎng)絡路由算法存在控制網(wǎng)絡開銷偏大、路由更新不及時以及流量調(diào)節(jié)機制分配不均等問題，提出了一種基于負載均衡的動態(tài)LEO衛(wèi)星網(wǎng)絡路由算法DRLB。根據(jù)衛(wèi)星節(jié)點路徑記錄信息以及后向Agent讀取策略設計新的路由機制，獲得動態(tài)衛(wèi)星拓撲結構；分析前向Agent的分組格式并刪除冗余字段，達到減小網(wǎng)絡開銷目的；根據(jù)數(shù)據(jù)發(fā)送時間間隔構造前向Agent選址策略，提高路由更新效率，通過考慮衛(wèi)星所處緯度流量分配不均問題，改進流量調(diào)節(jié)因子，獲得更好的負載均衡效果。仿真結果表明，與SDRZ-MA算法相比，DRLB算法在減緩星地之間的控制開銷、平均端到端時延等方面具有較好的優(yōu)勢。

負載均衡；衛(wèi)星網(wǎng)絡路由；流量調(diào)節(jié)；更新路由；調(diào)節(jié)因子

0　引言

LEO衛(wèi)星網(wǎng)絡具有動態(tài)變化的拓撲結構，拓撲一直都在快速變化，這是LEO衛(wèi)星網(wǎng)絡區(qū)別于地面自組織網(wǎng)絡的主要特點，而且衛(wèi)星的存儲能力和處理能力有限[1-2]。同時，衛(wèi)星間的距離很遠，容易導致較大的端到端傳輸時延[3]。

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

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

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

1.1網(wǎng)絡模型及相關定義

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

(1)如果衛(wèi)星節(jié)點s與衛(wèi)星節(jié)點v之間存在星際鏈路，則用links?v表示；

(2)衛(wèi)星節(jié)點s的所有鄰居衛(wèi)星的個數(shù)用Ns表示；

(3)costs，v(t)表示在 t時刻，衛(wèi)星節(jié)點 s與鄰居衛(wèi)星 v之間星際鏈路的代價值；

(4)假設源衛(wèi)星 s與目的衛(wèi)星 d之間的最短路徑為：

1.2問題描述

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

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

(2)在SDRZ-MA算法中，衛(wèi)星星座運行一個周期后，每個衛(wèi)星節(jié)點僅以概率 qd的值來確定前向 Agent的目的衛(wèi)星地址，這不夠全面，會導致衛(wèi)星節(jié)點對于全網(wǎng)的拓撲信息獲取得不夠及時準確；

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

2　本文DRLB算法

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

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

在SDRZ-MA算法中，調(diào)節(jié)因子λvi的函數(shù)如下：

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

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

圖1　流量因子改進前后的函數(shù)分布

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

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

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

2.3壓縮Agent分組長度

在SDRZ-MA算法中，前向Agent記錄的路由信息為：

顯然，DRLB算法的前向Agent長度明顯小于SDRZMA算法。在DRLB算法中，每顆衛(wèi)星都有一個緯度表和鄰居衛(wèi)星到自己的代價表，當前向Agent到達某一衛(wèi)星節(jié)點后，該衛(wèi)星節(jié)點會更新自己的緯度和該前向Agent上一跳節(jié)點到本節(jié)點的鏈路代價，同時在前向Agent分組中加入該衛(wèi)星的信息，然后繼續(xù)遷移。當前向Agent滿足規(guī)則4中的任意一個條件后生成后向Agent，后向Agent沿前向Agent原路返回，依次從所經(jīng)過的衛(wèi)星節(jié)點上讀取該衛(wèi)星記錄的緯度和對應鏈路的代價信息，壓入自己的內(nèi)存中，同時更新經(jīng)過衛(wèi)星節(jié)點的路由表。后前Agent到達源節(jié)點后，其堆棧信息為：，這與 SDRZ-MA算法的后向Agent攜帶信息一樣。

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

2.4.1算法規(guī)則

(1)規(guī)則1

路由表初始化：

(2)規(guī)則2

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

②第二個周期開始，每個衛(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到達中間衛(wèi)星后，根據(jù)該衛(wèi)星節(jié)點的路由表來選擇下一跳。若存在鏈路不可用時，則先排除不可用的鏈路，并對該衛(wèi)星的路由表重新更新，再選擇下一跳。

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

(4)規(guī)則4

當下面的任意一個條件成立時，前向Agent生成后向Agent，前向Agent消失：

①前向移動Agent達到其壽命期。

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

(5)規(guī)則5

①網(wǎng)絡代價模型的更新：

其中：η為學習率，是一個大于0小于1之間的數(shù)。

②路由表的更新：

如果前向Agent從源衛(wèi)星節(jié)點s到達目的衛(wèi)星節(jié)點d的路徑為 s→v→…→d，那么Ts路由表根據(jù)下式來進行更新：

2.4.2具體步驟

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

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

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

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

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

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

圖2　移動Agent工作流程

3　仿真和性能分析

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

本文借助仿真軟件是OPNET14.5來測試本文路由算法的網(wǎng)路性能[9-10]。為了模擬實際的衛(wèi)星網(wǎng)絡的流量分布，仿真中衛(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ù)包的目的地址隨機。為了體現(xiàn)本文算法的先進性，將當前LEO衛(wèi)星網(wǎng)路由性能較好的 SDRZ-MA算法視為對照組，并取 α=3，β=5，η=0.8。星座拓撲仿真參數(shù)如表1所示。

表1　本文DRLB算法的仿真參數(shù)設置

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

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

(1)丟包率

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

圖3　兩種算法的丟包率測試結果

(2)平均端到端時延

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

圖4　南半球位置下的平均端到端時延

圖5　北半球位置下的平均端到端時延

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

(3)歸一化ISL負載

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

圖6　各算法的歸一化ISL負載測試

4　結論

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

[1]韋娟，薄振雨，劉葉.基于分時的 LEO衛(wèi)星網(wǎng)絡非對稱路由算法[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]任智，王路路，楊勇.機會網(wǎng)絡中基于定向數(shù)據(jù)傳輸?shù)牡乩砺酚伤惴╗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-），男，碩士，講師，主要研究方向：網(wǎng)絡路由設計。

鄔家煒（1950-)，男，碩士，教授，主要研究方向：計算機網(wǎng)絡。

中文引用格式：羅擁華，鄔家煒.一種高效動態(tài)LEO衛(wèi)星網(wǎng)絡流量調(diào)節(jié)路由算法[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.