空間網(wǎng)絡(luò)多路徑路由算法﹡

朱 超， 洪佩琳， 盧漢成， 張林杰， 閻長(zhǎng)江

（①中國(guó)科學(xué)技術(shù)大學(xué) 電子工程與信息科學(xué)系信息網(wǎng)絡(luò)實(shí)驗(yàn)室，安徽 合肥 230027；②軍用通信網(wǎng)信息傳輸與分發(fā)技術(shù)國(guó)防科技重點(diǎn)實(shí)驗(yàn)室，河北 石家莊 050081）

0 引言

空間網(wǎng)絡(luò)通信相關(guān)技術(shù)近年來(lái)得到越來(lái)越多的人關(guān)注[1-2]。不同于地面通信網(wǎng)絡(luò),空間網(wǎng)絡(luò)通信[3]具有距離遠(yuǎn)、延時(shí)大、周期性間歇連接以及誤碼率高等特點(diǎn)。傳統(tǒng)的路由協(xié)議并不能直接適用于空間網(wǎng)絡(luò)。因此提出新的適用于空間網(wǎng)絡(luò)環(huán)境的路由協(xié)議是十分必要的。

目前，針對(duì)空間網(wǎng)絡(luò)的路由算法主要有：ASCOT[4]、S-OSPF[5]、RADSCN[6]、CGR[7]、ECGR[8]、SQRA[9]等路由協(xié)議。其中ASCOT是一種以數(shù)據(jù)為中心基于節(jié)點(diǎn)位置的空間網(wǎng)絡(luò)路由協(xié)議，其中以數(shù)據(jù)為中心實(shí)現(xiàn)了與其它鄰近網(wǎng)絡(luò)的互通，基于節(jié)點(diǎn)位置可以適應(yīng)空間網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化的特點(diǎn)。S-OSPF協(xié)議一種分等級(jí)的路由協(xié)議，將空間網(wǎng)絡(luò)分成三個(gè)區(qū)域，不同的區(qū)域使用不同的路由協(xié)議。RADSCN是一種最大吞吐量算法，基于聯(lián)通時(shí)序圖計(jì)算出一條吞吐量最大的路徑。CGR協(xié)議充分利用了空間網(wǎng)絡(luò)節(jié)點(diǎn)連接可預(yù)測(cè)性這一特點(diǎn)，網(wǎng)絡(luò)中節(jié)點(diǎn)的捆綁層可預(yù)測(cè)其它節(jié)點(diǎn)的當(dāng)前狀態(tài)和節(jié)點(diǎn)間連接時(shí)刻表，從而進(jìn)行有效的路徑選擇。文獻(xiàn)[10]驗(yàn)證了可以將CGR算法應(yīng)用于鄰地空間中。ECGR是對(duì)CGR協(xié)議的改進(jìn)，使用Dijkstra算法代替了CGR中回溯法，大大減少了算法的復(fù)雜度。文獻(xiàn)[11]在CGR基礎(chǔ)上提出了多目標(biāo)路由算法MD-CGR。SQRA提出了一種滿(mǎn)足不同業(yè)務(wù)的空間路由算法。

空間網(wǎng)絡(luò)節(jié)點(diǎn)采集的實(shí)驗(yàn)數(shù)據(jù)非常龐大，但是網(wǎng)絡(luò)的數(shù)據(jù)傳輸能力又十分有限，如果不能有效的傳輸這些數(shù)據(jù)，會(huì)給網(wǎng)絡(luò)造成沉重的負(fù)擔(dān)。目前空間網(wǎng)絡(luò)路由算法主要都是單路徑路由算法，并不能充分利用空間網(wǎng)絡(luò)的寶貴資源。文獻(xiàn)[12]提出了一種空間多路徑路由算法，該算法使用多條吞吐量最大的路徑來(lái)傳輸數(shù)據(jù)，但是算法復(fù)雜度高達(dá)并不適用于節(jié)點(diǎn)計(jì)算能力較弱的空間網(wǎng)絡(luò)，此外，該算法還忽略了空間長(zhǎng)時(shí)延傳輸?shù)奶攸c(diǎn)?？臻g網(wǎng)絡(luò)多路徑最大吞吐量的路由算法（SMMT, Space Multi-path and Max Throughput Routing Algorithm）是對(duì)

最小費(fèi)用最大流算法的改進(jìn)，在保證傳輸時(shí)延性能要求的基礎(chǔ)上，為間歇性網(wǎng)絡(luò)提供多條端到端的連接，充分利用了空間網(wǎng)絡(luò)的寶貴資源。

1 系統(tǒng)模型

在空間網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都在各自的軌道上周期性運(yùn)行，節(jié)點(diǎn)之間間歇性連接，通過(guò)星歷表[4]或者節(jié)點(diǎn)軌道參數(shù)[5]就可以實(shí)時(shí)準(zhǔn)確預(yù)測(cè)出每個(gè)節(jié)點(diǎn)的位置信息和節(jié)點(diǎn)間的連接狀態(tài)。

如圖1所示，空間網(wǎng)絡(luò)拓?fù)鋱DG由4個(gè)矩陣表示，分別為：連接開(kāi)始矩陣連接結(jié)束矩陣傳輸時(shí)延矩陣和傳輸帶寬矩陣

圖1 空間網(wǎng)絡(luò)拓?fù)?/p>

2 SMMT路由算法

SMMT路由算法使用存儲(chǔ)轉(zhuǎn)發(fā)機(jī)制，構(gòu)造多條非實(shí)時(shí)的端到端的連接。算法主要包含兩個(gè)步驟：①使用改進(jìn)的Dijkstra算法[5]尋找最小費(fèi)用路徑；②使用改進(jìn)的最大流算法查找最大吞吐量路徑。首先使用改進(jìn)的 Dijkstra算法主要用于尋找單條最短時(shí)延路徑，在時(shí)延約束得到保證的前提下，使用改進(jìn)最大流算法查找多條符合條件的路徑。改進(jìn)的最大流算法又主要分為瓶頸參數(shù)計(jì)算和殘留網(wǎng)絡(luò)構(gòu)造兩個(gè)部分。

2.1 SMMT路由選擇算法

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

輸入：一段時(shí)間 T內(nèi)的網(wǎng)絡(luò)拓?fù)鋱D（如圖 1所示）；

輸出：點(diǎn)到點(diǎn)的多路徑路由表；

①while（ture）do begin

a)使用改進(jìn)的 Dijkstra算法查找一條源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最短時(shí)延路徑；

b)如果不存在，則跳出循環(huán)，尋路結(jié)束；

c)如果數(shù)據(jù)到達(dá)目的節(jié)點(diǎn)的時(shí)間已經(jīng)大于數(shù)據(jù)包的生存時(shí)間，則跳出循環(huán)，尋路結(jié)束；

d)計(jì)算已找出路徑的瓶頸參數(shù)；

e)按照2.3節(jié)構(gòu)造間歇性殘留網(wǎng)絡(luò)；

end

②整合各條已找出的單條路徑，構(gòu)造多路徑路由表。

SMMT算法是一個(gè)循環(huán)迭代的過(guò)程，不斷的通過(guò)改進(jìn)的 Dijkstra算法和最大流算法查找出網(wǎng)絡(luò)中多個(gè)最短時(shí)延路徑，直到網(wǎng)絡(luò)中不存在可行的單條路徑為止。SMMT算法最終可為用戶(hù)計(jì)算出多條滿(mǎn)足Qos需求的傳輸路徑。

2.2 改進(jìn)的Dijkstra算法

ASCOT協(xié)議采用改進(jìn)的適用空間網(wǎng)絡(luò)的Dijkstra算法[4]查找最短時(shí)延路徑。改進(jìn)的 Dijkstra算法需要更新數(shù)據(jù)到達(dá)每個(gè)節(jié)點(diǎn)的時(shí)間，這里使用矩陣 []nA 表示。

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

圖2 間歇性連接到達(dá)時(shí)間

2.3 改進(jìn)的最大流算法

多路徑最大吞吐量算法是對(duì)最小費(fèi)用最大流算法[13]的改進(jìn)，其中最小費(fèi)用算法參考 2.2節(jié)。不同于最大流算法，SMMT算法提出了新的路徑瓶頸參數(shù)計(jì)算方式和空間間歇性殘留網(wǎng)絡(luò)概念。

2.3.1 瓶頸參數(shù)的計(jì)算

節(jié)點(diǎn)i和節(jié)點(diǎn)k在時(shí)間 T內(nèi)的鏈路連接的開(kāi)始時(shí)間為,ikb ，結(jié)束時(shí)間為,ike ，傳輸時(shí)延為,ikd 和鏈路帶寬為,ikw ，則鏈路可用的有效傳輸時(shí)間,ikt 為：

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

然后根據(jù)數(shù)據(jù)達(dá)到節(jié)點(diǎn)ik的時(shí)間ika，計(jì)算出每條鏈路的有效傳輸時(shí)間，這時(shí)分為兩種可能：

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

2.3.2 間歇性殘留網(wǎng)絡(luò)構(gòu)造

從2.3.1節(jié)可以得出路徑,SDP 的瓶頸傳輸時(shí)間、瓶頸帶寬和瓶頸吞吐量，SMMT算法是一個(gè)循環(huán)迭代的過(guò)程，那么每一次間歇性殘留網(wǎng)絡(luò)的構(gòu)造是由原始網(wǎng)絡(luò)去除上一次計(jì)算出的單路徑已經(jīng)占用的時(shí)間和帶寬而得到的。更新后的殘留網(wǎng)絡(luò)的相關(guān)參數(shù)為：

更新間歇性殘留網(wǎng)絡(luò)之后繼續(xù)按照改進(jìn)的Dijkstra算法查找下一條可行路徑，直到殘留網(wǎng)絡(luò)中不存在可行的單條路徑。

對(duì)于給定的網(wǎng)絡(luò)，假設(shè)在時(shí)間T內(nèi)一共執(zhí)行了M次最小費(fèi)用路由算法，每次獲得的瓶頸吞吐量為mTh，那么SMMT算法在時(shí)間T內(nèi)的網(wǎng)絡(luò)平均吞吐量為：

圖3 殘留鏈路

2.4 SMMT算法正確性分析

2.5 SMMT算法復(fù)雜度分析

如果給定的網(wǎng)絡(luò)中有V個(gè)節(jié)點(diǎn)，E條邊，在時(shí)間T內(nèi)的最大吞吐量為maxTh ，由2.4節(jié)可知，SMMT算法最多執(zhí)行maxTh 次最小費(fèi)用路由算法，使用改進(jìn)的 Dijkstra算法查找最小費(fèi)用路徑的時(shí)間復(fù)雜度為處理間歇性殘留網(wǎng)絡(luò)時(shí)間復(fù)雜度為 ()O E，那么整個(gè) SMMT算法時(shí)間復(fù)雜度為

3 仿真實(shí)驗(yàn)

空間網(wǎng)絡(luò)通信可分為鄰地空間通信和深空網(wǎng)絡(luò)通信,分別使用 Opnet仿真軟件構(gòu)造了這兩種場(chǎng)景,并對(duì)SMMT算法和ASCOT、S-OSPF協(xié)議進(jìn)行了仿真分析。

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

圖4 鄰地空間仿真場(chǎng)景

圖5 深空通信仿真場(chǎng)景

吞吐量：在鄰地空間通信場(chǎng)景中，同步衛(wèi)星為源節(jié)點(diǎn)，地面節(jié)點(diǎn)為目的節(jié)點(diǎn)，仿真持續(xù)時(shí)間為180個(gè)小時(shí)，在深空通信網(wǎng)絡(luò)場(chǎng)景中，火星為源節(jié)點(diǎn)，地球?yàn)槟康墓?jié)點(diǎn)，仿真持續(xù)時(shí)間為3 500個(gè)小時(shí)。從圖6和圖7中可以看出，由于SMMT算法使用多條路經(jīng)傳輸數(shù)據(jù)包，SMMT算法的吞吐量比ASCOT和 S-OSPF算法都有了明顯的提升，其中鄰地空間環(huán)境提升了約212%，深空通信環(huán)境提升約90%。

圖6 鄰地空間網(wǎng)絡(luò)吞吐量

圖7 深空通信網(wǎng)絡(luò)吞吐量

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

仿真耗時(shí)：圖9為在兩種仿真環(huán)境下分別使用SMMT、ASCOT和S-OSPF三種算法仿真相同的周期（鄰地空間為1周，深空通信為20周）所消耗的仿真時(shí)延，由于SMMT算法在提高吞吐量的同時(shí)也增加了算法的復(fù)雜度，因此該算法的開(kāi)銷(xiāo)最大，耗時(shí)也最多。S-OSPF算法因?yàn)橐?jīng)常發(fā)送數(shù)據(jù)包來(lái)廣播節(jié)點(diǎn)的軌道信息，開(kāi)銷(xiāo)就比較大，耗時(shí)次之。從時(shí)間上來(lái)看，ASCOT每次根據(jù)預(yù)測(cè)只需要計(jì)算一條最短路徑，算法耗時(shí)最少。

圖8 傳輸時(shí)延

圖9 仿真耗時(shí)

4 結(jié)語(yǔ)

基于空間環(huán)境的多路徑路由算法—SMMT是對(duì)最小費(fèi)用最大流算法的改進(jìn)，適用于空間間歇性連接網(wǎng)絡(luò)。仿真可以表明，SMMT算法使用多條路徑傳輸數(shù)據(jù)，有效的保證了數(shù)據(jù)包的傳輸時(shí)延并且明顯的提高了網(wǎng)絡(luò)的吞吐量，使得空間網(wǎng)絡(luò)的寶貴資源得到了充分的利用。

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

[2] 吳曉光,雷菁,黃英.CCSDS分包遙控協(xié)議分析[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] 李紅艷,楊光祥,王文龍.一種最大吞吐量的深空通信網(wǎng)絡(luò)路由算法[J].西安電子科技大學(xué)學(xué)報(bào),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] 韋娟,王丹丹.空間因特網(wǎng)的路由技術(shù)研究[J].通信技術(shù),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] 李紅艷,胡云,李建東,等.基于連通時(shí)序的多路徑路由選擇方法：中國(guó),CN102316546A[P]. 2012-01-11.

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