空間網絡多路徑路由算法﹡

朱 超， 洪佩琳， 盧漢成， 張林杰， 閻長江

（①中國科學技術大學 電子工程與信息科學系信息網絡實驗室，安徽 合肥 230027；②軍用通信網信息傳輸與分發技術國防科技重點實驗室，河北 石家莊 050081）

0 引言

空間網絡通信相關技術近年來得到越來越多的人關注[1-2]。不同于地面通信網絡,空間網絡通信[3]具有距離遠、延時大、周期性間歇連接以及誤碼率高等特點。傳統的路由協議并不能直接適用于空間網絡。因此提出新的適用于空間網絡環境的路由協議是十分必要的。

目前，針對空間網絡的路由算法主要有：ASCOT[4]、S-OSPF[5]、RADSCN[6]、CGR[7]、ECGR[8]、SQRA[9]等路由協議。其中ASCOT是一種以數據為中心基于節點位置的空間網絡路由協議，其中以數據為中心實現了與其它鄰近網絡的互通，基于節點位置可以適應空間網絡拓撲結構動態變化的特點。S-OSPF協議一種分等級的路由協議，將空間網絡分成三個區域，不同的區域使用不同的路由協議。RADSCN是一種最大吞吐量算法，基于聯通時序圖計算出一條吞吐量最大的路徑。CGR協議充分利用了空間網絡節點連接可預測性這一特點，網絡中節點的捆綁層可預測其它節點的當前狀態和節點間連接時刻表，從而進行有效的路徑選擇。文獻[10]驗證了可以將CGR算法應用于鄰地空間中。ECGR是對CGR協議的改進，使用Dijkstra算法代替了CGR中回溯法，大大減少了算法的復雜度。文獻[11]在CGR基礎上提出了多目標路由算法MD-CGR。SQRA提出了一種滿足不同業務的空間路由算法。

空間網絡節點采集的實驗數據非常龐大，但是網絡的數據傳輸能力又十分有限，如果不能有效的傳輸這些數據，會給網絡造成沉重的負擔。目前空間網絡路由算法主要都是單路徑路由算法，并不能充分利用空間網絡的寶貴資源。文獻[12]提出了一種空間多路徑路由算法，該算法使用多條吞吐量最大的路徑來傳輸數據，但是算法復雜度高達并不適用于節點計算能力較弱的空間網絡，此外，該算法還忽略了空間長時延傳輸的特點。空間網絡多路徑最大吞吐量的路由算法（SMMT, Space Multi-path and Max Throughput Routing Algorithm）是對

最小費用最大流算法的改進，在保證傳輸時延性能要求的基礎上，為間歇性網絡提供多條端到端的連接，充分利用了空間網絡的寶貴資源。

1 系統模型

在空間網絡中，每個節點都在各自的軌道上周期性運行，節點之間間歇性連接，通過星歷表[4]或者節點軌道參數[5]就可以實時準確預測出每個節點的位置信息和節點間的連接狀態。

如圖1所示，空間網絡拓撲圖G由4個矩陣表示，分別為：連接開始矩陣連接結束矩陣傳輸時延矩陣和傳輸帶寬矩陣

圖1 空間網絡拓撲

2 SMMT路由算法

SMMT路由算法使用存儲轉發機制，構造多條非實時的端到端的連接。算法主要包含兩個步驟：①使用改進的Dijkstra算法[5]尋找最小費用路徑；②使用改進的最大流算法查找最大吞吐量路徑。首先使用改進的 Dijkstra算法主要用于尋找單條最短時延路徑，在時延約束得到保證的前提下，使用改進最大流算法查找多條符合條件的路徑。改進的最大流算法又主要分為瓶頸參數計算和殘留網絡構造兩個部分。

2.1 SMMT路由選擇算法

算法1:SMMT路由選擇算法；

輸入：一段時間 T內的網絡拓撲圖（如圖 1所示）；

輸出：點到點的多路徑路由表；

①while（ture）do begin

a)使用改進的 Dijkstra算法查找一條源節點到目的節點的最短時延路徑；

b)如果不存在，則跳出循環，尋路結束；

c)如果數據到達目的節點的時間已經大于數據包的生存時間，則跳出循環，尋路結束；

d)計算已找出路徑的瓶頸參數；

e)按照2.3節構造間歇性殘留網絡；

end

②整合各條已找出的單條路徑，構造多路徑路由表。

SMMT算法是一個循環迭代的過程，不斷的通過改進的 Dijkstra算法和最大流算法查找出網絡中多個最短時延路徑，直到網絡中不存在可行的單條路徑為止。SMMT算法最終可為用戶計算出多條滿足Qos需求的傳輸路徑。

2.2 改進的Dijkstra算法

ASCOT協議采用改進的適用空間網絡的Dijkstra算法[4]查找最短時延路徑。改進的 Dijkstra算法需要更新數據到達每個節點的時間，這里使用矩陣 []nA 表示。

在空間網絡中，節點之間成間歇性連接，如圖 2所示，鏈路,ikl 的連接開始時間為,ikb ，連接結束時間為,ike ，數據在兩節點之間的傳輸時延為,ikd 。假設數據在ia時刻到達節點i，那么數據從節點i通過節點k到達節點j的情況可分為圖2中三種情況：數據到達時鏈路處于聯通狀態、數據到達時鏈路處于等待聯通狀態和數據到達時鏈路聯通時間不足以傳輸數據。根據式(1)可以得出數據到達每個節點的時間，然后使用 Dijkstra算法求出端到端的最短時延路徑[4]。

圖2 間歇性連接到達時間

2.3 改進的最大流算法

多路徑最大吞吐量算法是對最小費用最大流算法[13]的改進，其中最小費用算法參考 2.2節。不同于最大流算法，SMMT算法提出了新的路徑瓶頸參數計算方式和空間間歇性殘留網絡概念。

2.3.1 瓶頸參數的計算

節點i和節點k在時間 T內的鏈路連接的開始時間為,ikb ，結束時間為,ike ，傳輸時延為,ikd 和鏈路帶寬為,ikw ，則鏈路可用的有效傳輸時間,ikt 為：

假設使用改進的 Dijkstra算法求出的可行的最短時延路徑,SDP 為定義路徑的瓶頸參數分別為瓶頸傳輸時間mint 、瓶頸帶寬和瓶頸吞吐量minTh 。首先，可以根據每條鏈路的帶寬計算出整條路徑,SDP 的瓶頸帶寬：

然后根據數據達到節點ik的時間ika，計算出每條鏈路的有效傳輸時間，這時分為兩種可能：

同理可以計算出路徑,SDP 上所有鏈路的有效傳輸時間。那么，路徑,SDP 的瓶頸傳輸時間為：

2.3.2 間歇性殘留網絡構造

從2.3.1節可以得出路徑,SDP 的瓶頸傳輸時間、瓶頸帶寬和瓶頸吞吐量，SMMT算法是一個循環迭代的過程，那么每一次間歇性殘留網絡的構造是由原始網絡去除上一次計算出的單路徑已經占用的時間和帶寬而得到的。更新后的殘留網絡的相關參數為：

更新間歇性殘留網絡之后繼續按照改進的Dijkstra算法查找下一條可行路徑，直到殘留網絡中不存在可行的單條路徑。

對于給定的網絡，假設在時間T內一共執行了M次最小費用路由算法，每次獲得的瓶頸吞吐量為mTh，那么SMMT算法在時間T內的網絡平均吞吐量為：

圖3 殘留鏈路

2.4 SMMT算法正確性分析

2.5 SMMT算法復雜度分析

如果給定的網絡中有V個節點，E條邊，在時間T內的最大吞吐量為maxTh ，由2.4節可知，SMMT算法最多執行maxTh 次最小費用路由算法，使用改進的 Dijkstra算法查找最小費用路徑的時間復雜度為處理間歇性殘留網絡時間復雜度為 ()O E，那么整個 SMMT算法時間復雜度為

3 仿真實驗

空間網絡通信可分為鄰地空間通信和深空網絡通信,分別使用 Opnet仿真軟件構造了這兩種場景,并對SMMT算法和ASCOT、S-OSPF協議進行了仿真分析。

圖4為使用Opnet構造的鄰地空間通信仿真場景，該場景由7個衛星節點和一個地面固定節點組成，7個衛星節點的高度分別為10 000 km（Sa10，Sa11，Sa12）、20 000 km（Sa20，Sa21，Sa22）和36 000 km（Geo_beijing）。地面節點部署在北京地區，每個節點的通信范圍為50 000 km。圖5為使用Opnet構造的深空通信仿真場景，該場景由8個節點構成，分別為火星節點、地球節點、地球 L4、L5節點、金星L4、L5節點和水星L4、L5節點。每個節點的通信范圍為1.5AU。

圖4 鄰地空間仿真場景

圖5 深空通信仿真場景

吞吐量：在鄰地空間通信場景中，同步衛星為源節點，地面節點為目的節點，仿真持續時間為180個小時，在深空通信網絡場景中，火星為源節點，地球為目的節點，仿真持續時間為3 500個小時。從圖6和圖7中可以看出，由于SMMT算法使用多條路經傳輸數據包，SMMT算法的吞吐量比ASCOT和 S-OSPF算法都有了明顯的提升，其中鄰地空間環境提升了約212%，深空通信環境提升約90%。

圖6 鄰地空間網絡吞吐量

圖7 深空通信網絡吞吐量

傳輸時延：圖 8為在兩種仿真環境下分別使用SMMT、ASCOT和S-OSPF三種算法傳輸相同大小數據包（鄰地空間為50 Mb，深空通信為500 Mb）所消耗的傳輸時延對比圖。從圖中可以看出，由于SMMT算法具有較大的網絡平均吞吐量，因此傳輸相同大小數據包消耗的時延明顯小于另外兩種算法。

仿真耗時：圖9為在兩種仿真環境下分別使用SMMT、ASCOT和S-OSPF三種算法仿真相同的周期（鄰地空間為1周，深空通信為20周）所消耗的仿真時延，由于SMMT算法在提高吞吐量的同時也增加了算法的復雜度，因此該算法的開銷最大，耗時也最多。S-OSPF算法因為要經常發送數據包來廣播節點的軌道信息，開銷就比較大，耗時次之。從時間上來看，ASCOT每次根據預測只需要計算一條最短路徑，算法耗時最少。

圖8 傳輸時延

圖9 仿真耗時

4 結語

基于空間環境的多路徑路由算法—SMMT是對最小費用最大流算法的改進，適用于空間間歇性連接網絡。仿真可以表明，SMMT算法使用多條路徑傳輸數據，有效的保證了數據包的傳輸時延并且明顯的提高了網絡的吞吐量，使得空間網絡的寶貴資源得到了充分的利用。

[1] 尹志忠,陳靜毅,周賢偉.美軍衛星通信系統的發展及其技術研究[J].通信技術,2009,42(11)：55-58.

[2] 吳曉光,雷菁,黃英.CCSDS分包遙控協議分析[J].信息安全與通信保密,2010(11)：28-30.

[3] MARCHESE M. Interplanetary and Pervasive Communications[J]. Aerospace and Electronic Systems Magazine,IEEE,2011,26(02)：12-18.

[4] GNAWALI O, POLYAKOVT M, BOSE P, et al. Data Centric,Position-based Routing in Space Networks[C]//Aerospace Conference, 2005 IEEE.[s.l.]： IEEE, 2005：1322-1334.

[5] BANTAN N,KKAN J. Space OSPF： an Area Hierarchic Routing Protocol for Routers in Motion[C]//25th AIAA International Communications Satellite Systems Conference.Seoul, South Korea, 2007： 10-13.

[6] 李紅艷,楊光祥,王文龍.一種最大吞吐量的深空通信網絡路由算法[J].西安電子科技大學學報,2012,39(01)：92-97.

[7] BURLEIGH C S. Contact Graph Routing[S]. IRTF,Internet-Draft draft-burleigh-dtnrg-cgr-00,Dec 2009.

[8] SEGUí J, JENNINGS E, BURLEIGH S. Enhancing Contact Graph Routing for Delay Tolerant Space Networking[C]// Global Telecommunications Conference (GLOBECOM 2011), 2011 IEEE.[s.l.]： IEEE,2011：1-6.

[9] 韋娟,王丹丹.空間因特網的路由技術研究[J].通信技術,2010,43(12)：29.

[10] CAINI C, FIRRINCIELI R. Application of Contact Graph Routing to LEO satellite DTN Communications[C]//Communications (ICC), 2012 IEEE International Conference.[s.l.]： IEEE, 2012：3301-3305.

[11] BIRRANE E, BURLEIGH S, KASCH N. Analysis of the Contact Graph Routing Algorithm： Bounding Interplanetary Paths[J]. Acta Astronautica,2012(75)：108-119.

[12] 李紅艷,胡云,李建東,等.基于連通時序的多路徑路由選擇方法：中國,CN102316546A[P]. 2012-01-11.

[13] CORMEN H T,LEISERSON E C,RIVEST L R,et al.算法導論[M].潘金貴,顧鐵成,李成法,等譯.北京：機械工業出版社,2006：396-425.