0 引言

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

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

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

1 網絡模型及問題描述

1.1 網絡模型及相關定義

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

1.2 問題描述

    通過對考慮負載均衡的具有代表性的LEO衛星網絡路由算法SDRZ-MA進行研究，發現該算法存在以下問題：

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

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

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

2 本文DRLB算法

    由于基于移動Agent的LEO衛星網絡路由算法存在網絡控制開銷偏大、流量調節機制不合理的問題，本文提出了基于負載均衡的動態LEO衛星網絡路由算法DRLB。

2.1 流量調節因子的改進

    在SDRZ-MA算法中，調節因子的函數如下：

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

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

2.2 優化前向Agent目的衛星的選取策略

    在SDRZ-MA算法中，衛星節點會定期向其他衛星發送前向Agent，該前向Agent的目的地址以概率q_d來確定：

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

2.3 壓縮Agent分組長度

2.4 DRLB算法規則及基本操作

2.4.1 算法規則

    (1)規則1

    路由表初始化：

    (2)規則2

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

    ②第二個周期開始，每個衛星節點在生成前向Agent前，首先排除前向Agent產生間隔內該衛星記錄的經過自己的前向Agent的目的衛星地址，然后再按概率q_d選擇Agent的目的地址，前向Agent生成后發送給鄰居衛星。

    (3)規則3

    ①前向Agent到達中間衛星后，根據該衛星節點的路由表來選擇下一跳。若存在鏈路不可用時，則先排除不可用的鏈路，并對該衛星的路由表重新更新，再選擇下一跳。

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

    (4)規則4

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

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

    ②前向Agent根據規則3選擇下一跳時，選擇的下一跳衛星已經被該前向Agent訪問過或沒有可用的路徑。

    (5)規則5

    ①網絡代價模型的更新：

2.4.2 具體步驟

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

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

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

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

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

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

3 仿真和性能分析

3.1 仿真環境設置

    本文借助仿真軟件是OPNET14.5來測試本文路由算法的網路性能^[9-10]。為了模擬實際的衛星網絡的流量分布，仿真中衛星在北緯0°～50°之間衛星節點每發送0.4 s數據包停止0.8 s，其他非極地區域衛星節點每發送0.1 s數據包停止1.1 s，數據包的目的地址隨機。為了體現本文算法的先進性，將當前LEO衛星網路由性能較好的SDRZ-MA算法視為對照組，并取α=3，β=5，η=0.8。星座拓撲仿真參數如表1所示。

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

3.2 實驗數據與分析

    (1)丟包率

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

    (2)平均端到端時延

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

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

    (3)歸一化ISL負載

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

4 結論

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

參考文獻

[1] 韋娟，薄振雨，劉葉.基于分時的LEO衛星網絡非對稱路由算法[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] 任智，王路路，楊勇.機會網絡中基于定向數據傳輸的地理路由算法[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.