LEO衛星網絡中基于分布式路由算法的流量均衡策略

段思睿，劉元安，胡鶴飛，李 虎

(1. 北京郵電大學電子工程學院 北京 海淀區 100876; 2. 北京郵電大學安全生產智能監控北京市重點實驗室 北京 海淀區 100876)

LEO衛星網絡具有全球覆蓋特性，其各網絡節點具有在軌信息處理、轉發的能力。伴隨著高帶寬的星間鏈路ISL (inter satellite link)應用，衛星網絡能夠滿足各種數據業務的需求，必將在下一代互聯網(next generation Internet, NGI)的發展中占有重要地位[1-2]。

LEO衛星網絡的流量分布具有不均勻特性，大量流量負載會集中在高緯度區域[2-5]。產生這種現象的主要原因是，地球表面的弧度使高緯度區域相鄰衛星間的距離近，在低緯度區域的距離遠。而以最短路徑為優化目標的衛星網絡路由算法，會側重于選擇高緯度的星間鏈路，從而導致大量的數據流量會集中在高緯度區域。因此，應用于LEO衛星網絡中的路由算法，除了尋找最短路徑外，還必須考慮網絡流量的均衡問題。

應用于衛星網絡的路由算法主要采用集中式路由和分布式路由兩種思想[6-14]。分布式路由算法是在掌握網絡結構及周期性變化特性的基礎上，對單節點設計的路由策略。各個網絡節點僅需要了解本節點或者鄰節點的網絡信息，路由信息交互較少。網絡節點利用地址信息對轉發的每一個包單獨計算其下一跳節點，避免了大量的存儲開銷。文獻[4]根據分布式思想，提出了一種應用于節點的精確負載均衡(explicit load balancing, ELB)策略。當節點出現鏈路數據擁塞時，對相鄰節點發出通知，鄰節點選擇次優路徑避免數據發送到擁塞鏈路。但該策略僅能解決局部區域的流量阻塞問題，不能對全局網絡的流量分布進行優化和控制。文獻[10-12]基于分布式思想提出了一種邏輯地址的概念，各在軌衛星根據自身位置選擇獨立的路由策略即可。

為了更加合理靈活地解決LEO衛星網絡的流量均衡問題，本文提出了兩種基于分布式路由算法的流量均衡策略。首先對LEO衛星網絡結構進行了分析，根據網絡結構的特點，提出基于橫向轉發優先級的分布式路由算法，再以此路由算法為基礎，提出了兩種均衡流量分布的優化策略。通過系統仿真，驗證了兩種流量均衡策略對網絡流量分布產生的不同影響效果。

1 分布式路由算法

本文提出的基于橫向轉發優先級(horizontal transmitting priority，HTP)的分布式路由算法充分考慮了星座結構的特點，相較于其他分布式路由算法，具有更低的計算復雜度。文獻[12]對該路由算法做出了前期的理論探索。下面對算法的實現方式進行介紹。

1.1 極軌道星座模型

極軌道星座模型廣泛應用于各種LEO衛星系統[11-12]，它由N個軌道面組成，每個軌道中均勻分布了M顆衛星，所有的軌道平面相對于地球的赤道面的傾角是相同的，并且N個軌道平面與赤道平面的交點是均勻分布在赤道平面的，其角距為360°/2N。

在相關研究中，將極軌道星座的網絡結構等效為一種類似于曼哈頓街區的網狀網絡結構[10-12]，如圖1所示，節點勻速由上至下運動，代表衛星從北向南，再從南向北(下半部分)的運動。在頂端和中部，代表極地區域，軌道間鏈路不能建立。

為了體現軌道間鏈路的不等長特性，定義橫向轉發優先級參數。HTP表示相對區域內橫向鏈路(軌道間鏈路)長度與全網內橫向鏈路長度的比較關系。橫向鏈路長度越短，其HTP值越高。考慮到衛星在圓形軌道下的對稱排列，其中，0表示該區域不存在橫向鏈路。鏈路的長短直接影響衛星網路中數據傳輸的延遲。HTP值是網絡節點決定下一跳路徑的決定因素，因為在需要橫向傳輸數據的情況下，選擇HTP值越高(鏈路長度越短)的橫向鏈路，其傳輸的延遲越小。

通過計算，即使衛星在同一區域內的上半部分和下半部分，HTP值也不相同(由于軌道內衛星數和區域數相等，根據對稱性，同軌道上的衛星會同時處于其對應區域的上半或下半區域中)。將各區域內等分為兩個子區域(在本文中，每個子區域縱向寬度為15°)，則全網內的HTP值如表1所示。

圖1 LEO衛星網絡結構圖

表1 HTP分布值

1.2 分布式路由算法

分布式路由算法的主要特點是網絡節點不會收集全網絡的狀態信息，僅僅根據自身節點對網絡結構的判斷，決定數據包的下一跳節點。

為實現分布式路由算法，首先需要將全網節點賦予一個唯一的地址，如圖2所示。

設網絡中存在一個初始狀態，用表示某節點的地址，其中，n為軌道面序號，m為同軌道面內節點的序號。節點地址在網絡中固定，不會因為衛星的運動而改變。目的節點所在的區域為：

式中，pD表示目的節點區域；pC表示當前節點所在區域。

圖2 節點地址分配

在上述地址分配方式的基礎上，分布式路由算法由確立方向和查詢HTP值兩個步驟組成。

1) 確立方向。當前節點收到發往目的節點的數據包時，首先計算目的節點所在的方向，以保證數據包能以最短條數到達目的節點。設dn和dm分別表示當前節點與目的節點在水平方向和垂直方向上的距離，則：

按照圖3所示的方向確立關系圖，當前節點可以得到通往目的節點的一條或者兩條(橫縱向各一條)備選方向。

圖3 方向確立關系圖

2) 查詢HTP。若通過確立方向，得到橫向及縱向兩條備選方向，則以當前節點為起點，按縱向方向，查詢當前節點與目的節點之間所有區域的HTP值。如果當前節點已處于最高HTP值區域，則將數據包發往橫向鄰節點，反之發往縱向的鄰節點。

如果只存在一條備選方向，則將數據直接發往該方向的鄰節點。特殊的，若源節點與目的節點同處于HTP=0的區域，需要在縱向兩個鄰節點內，選擇HTP值較高的作為下一跳節點。

2 流量均衡策略

LEO衛星網絡由于其網絡結構的特殊性，流量分布是不均勻的[2-5]。根據文獻[3]的仿真分析，如全網絡中的每一個網絡節點都對其他節點發送等量數據，網絡內在橫向上的流量會大量集中于高緯度區域。

本節在前文介紹的分布式路由算法的基礎上，提出了兩種流量均衡策略，對LEO衛星網絡中的流量分配不均勻情況進行優化。

2.1 鏈路流量

為分析整個網絡鏈路流量特性，首先需要對鏈路流量計算方式進行定義：

2.2 基于HTP的流量均衡策略

在分布式路由算法中，HTP值的高低決定了數據流量的走向。因此合理修改HTP值，能調整網絡橫向流量的分布情況。針對圖4中的場景，有3個源節點a1、a2、a3位于HTP=1的區域，它們共同的目的節點c4位于HTP=3區域。每個源節點同時對目的節點發送數據量B，根據式(4)，則C(c1c2)=B、C(c2c3)=2B、C(c3c4)=3B。

所有的橫向流量都集中于HTP=3的區域內，而在其他區域沒有橫向流量分布。在OD對數量增加時，大量流量會集中在高HTP區域，而低HTP區域只有少量流量分布。這是導致LEO衛星網絡橫向流量分布不均勻的原因。

圖4 傳輸場景一

考慮到HTP值對于網絡流量的影響，當高HTP區域的流量達到一定程度時，對網絡的HTP值進行適當修改，可以分散高HTP區域的流量。如將圖4所示場景改為圖5的場景。

圖5 傳輸場景二

將HTP=3區域改為HTP=2后，OD路徑中會出現2個最高HTP=2的區域，此時在路由策略第二步中，加入如下規則：

若當前節點與目的節點間存在n個HTP最高值時，節點有1/n的概率將數據包橫向轉發。

按照改變的HTP場景和路由策略，重新計算各鏈路的流量分布：C(c1c2)= C(b1b2)=B/2，C(c2c3)=C(b2b3)=B，C(c3c4)= C(b3b4)=3/2B。

橫向鏈路流量均勻地分配到兩條最高HTP的區域內。這種均衡策略能夠迅速緩解高HTP區域流量集中的問題。

2.3 基于橫向轉發率的流量均衡策略

針對如圖6所示的傳輸場景，a1節點為源節點，cN節點為目的節點，發送數據量為B。

圖6 傳輸場景三

若按照前文介紹的分布式路由策略，所有橫向流量都會集中在HTP=3區域，而其他區域無橫向流量。

取N=6(其他N值方法類似)，利用Matlab，計算得到k的變化與各HTP區域橫向流量歸一化占用率的關系如圖7所示。

圖7 各HTP區域橫向流量歸一化占用率

其中歸一化占用率計算方式是：

3 仿真及結果分析

本節將對路由算法和兩種流量均衡策略的有效性進行仿真驗證。仿真中LEO衛星星座采用72/6/0:1375km:90°的星座參數，極地區域設定為緯度高于75°地區。

3.1 基于HTP的流量均衡策略

為了在流量均衡的仿真中引入對比，首先計算在正常情況下網絡流量的分布情況。

在仿真中，截取衛星在區域內上下半區域的兩個靜態網絡場景，網絡中的每一個節點都對其他節點發送10 kb的數據，利用式(6)的計算方式，得到每條鏈路上的數據流量；然后累計每個區域中的橫向鏈路的流量，得到圖8的結果。圖中上下半區域劃分的HTP值如表1所示。根據圖中上下半區域流量分配的兩條曲線可以看到，由于最短路徑的變化導致HTP值的微小變化，反應在全局網絡中，產生了高緯度區域的橫向數據量波動情況：在第2和第8區域，當衛星處于上半區域時，橫向網絡流量很低，但當衛星到達下半區域時，網絡流量突然增大；而在第6和第12區域的情況則剛好相反。這種波動變換隨著衛星的移動是持續存在的，且數據總量變化劇烈，對網絡的穩定度而言會產生巨大影響。為了消除這種波動現象，可采用表2中均衡化的HTP分布值，其流量分布如圖8中的均衡分布曲線。均衡化的HTP值忽視了上下半區域的概念，因此高緯度區域的總流量不會因節點處于上下半區域而劇烈地波動。這種方式雖然會讓部分OD對沒有采用最短路徑，犧牲了個別路徑的延遲，但保證了網絡環境中流量分布的持續穩定。

圖8 正常情況下網絡流量分布圖

表2 均衡化HTP分布值

為驗證修改HTP值對緩解高緯度區域的大流量現象的影響，建立3組HTP分布值，如表3所示。其中第一組采用均衡化的HTP值作為流量參照；第二組降低了某一個高緯度區域(區域2)的HTP值；第三組將全網內的高緯度HTP值降低。

3組環境中各區域橫向網絡流量分布對比如圖9所示。根據第一組與第二組數據對比，可以看到降低HTP值可以明顯消減橫向網絡流量，區域2中第二組流量相較于第一組顯著降低，但是會增加其他最高HTP區域的最大流量(如區域6,12的第二組流量大于第一組流量)；從第三組曲線可以發現，在全局網絡中降低最高HTP值，可以均衡地將網絡流量分布在等HTP值的多個區域內部。這個仿真結果與2.2節的分析結果是吻合的。

表3 3組HTP值對比

圖9 不同HTP下網絡流量分布對比

利用HTP值對網絡流量的分布調整的結果是明顯而迅速的，但這種調整只能將最大流量均勻分散到等高的HTP區域，而高緯度區域橫向鏈路延遲短的優勢就無法體現。

3.2 基于轉發率的流量均衡策略

仿真環境與上一組實驗的參數相同，以表2的均衡化HTP分布值為基礎，網絡中的每一個節點對其他節點發送10 kb的數據，驗證多組轉發概率k值對流量分布的影響。

基于轉發概率的流量分布圖如圖10所示，從數據結果可以看到，轉發概率k的改變對各HTP區域的分布存在影響。當k=0時，等同于無均衡的情況，作為均衡策略的對比參照；隨著k值的增大，即k=0.15和k=0.35時，高HTP區域的流量聚集的趨勢逐漸降低，仍然維持了最大的比例，而低HTP區域值的流量漸增；當k=0.55時，各區域分布的流量接近相等。仿真結果與2.3節中對流量分布的分析結果吻合。

圖10 基于轉發概率的流量分布圖

4 結 論

本文提出兩種應用于LEO衛星網絡的分布式路由算法的全網流量均衡策略。通過系統仿真，驗證了基于HTP的流量均衡策略對LEO衛星網絡中高緯度區域的大流量現象有明顯的消減特性，但只能將流量平均分配到相等的HTP值區域；而基于橫向轉發概率的流量均衡策略對網絡流量分布可以全局性的調整，即減少了最高HTP值區域的總流量，又保證了該區域盡可能地占有大比例的流量，使路由算法盡量保持最短路徑。前者適合實時地對單一區域的流量調制，應對局部的流量阻塞問題；而后者能適用于全網絡范圍內的整體優化。

[1] DEL RE E, PIERUCCI L. Next-generation mobile satellite networks[J]. IEEE Communications Magazine, 2002, 40(9):150-159.

[2] FRANCK L, MARL G. Static and adaptive routing in ISL networks from a constellation perspective[J]. Int J Satell Commun, 2002(20): 455-475.

[3] WERNER M, FRINGS J, WAUQUIEZ F, et al. Topological design, routing and capacity dimensioning for ISL networks in broadband LEO satellite systems[J]. Int J Satell Commun,2002, 20(6): 455-475.

[4] PAN Yan-hui, WANG Tao, LI Hua. Research on load balancing method of LEO satellite network routing[J].Computer Engineering, 2011, 37(8): 4-6.

[5] TARIK T, DAISUKE M, ABBAS J, et al. Explicit load balancing technique for NGEO satellite IP networks w ith on-board processing capability[J]. IEEE/ACM Trans on Networking, 2009, 17(1): 281-293.

[6] TONG Rui-xia, ZHU Xiong-feng, A load balancing strategy based on the combination static and dynamic[C]//2010 2nd International Workshop on Database Technology and Applications (DBTA). [S.l.]: IEEE, 2010.

[7] NISHIYAMA H, KUDOH D, KATO N, et al, Load balancing and QoS provisioning based on congestion prediction for GEO/LEO hybrid satellite networks[J].Proceedings of the IEEE. 2011, 99(11): 1998-2007.

[8] GAO Zi-he, GUO Qing, NA Zhen-yu. Novel optimized routing algorithm for LEO satellite IP networks[J]. Journal of Systems Engineering and Electronics, 2011, 22(6):917-925.

[9] HONG S C, BYOUNG W K, CHANG G L, et al.FSA-based link assignment and routing in low-earth orbit satellite networks[J]. IEEE Trans on Vehicular Technology,1998, 47(30): 1037-1048.

[10] KICI E, AKYIIDIZ I F, BENDER M D. A multicast routing algorithm for datagram traffic in LEO satellite networks[J]. IEEE/ACM Trans Networking, 2002, 10(2):183-192.

[11] YANG De-nian, LIAO Wan-jiun. On multicast routing using rectilinear steiner trees for LEO satellite networks[J].IEEE Trans on Vehicular Technology, 2008, 57(4):2560-2659.

[12] DUAN Si-rui, LIU Yua-nan, HU He-fei, et al. An orbital plane based distributed routing algorithm for LEO satellite networks[J]. Journal of Computational Information Systems, 2013, 9(4): 1279-1287.

[13] TUO Yan-jun, LIU Yun, LI Yan. Design and analyses of LEO/MEO constellation networking[J]. Journal of University of Electronic Science and Technology of China,2010, 39(1): 50-54.

[14] JIANG Wen-juan, ZONG Peng. QoS routing algorithm based on traffic classification in LEO satellite networks[C]//2011 Eighth International Conference on Wireless and Optical Communications Networks (WOCN). [S.l.]: IEEE,2011.

[15] PRATT S R, RAINS R A, FOSSA C E, et al. An operational and performance overview of the iridium low earth orbit satellite system[J]. IEEE Communications Surveys, 1999(2): 2-10.

[16] AKYILDIZ I F, EKICI E, BENDER M D. MLSR: a novel routing algorithm for multilayered satellite IP networks[J].IEEE/ACM Trans on Networking, 2002, 10(3): 411-423.

編 輯 張 俊