天基信息網(wǎng)絡(luò)低軌非對(duì)稱(chēng)路由協(xié)議研究

李偉明 張素娟 申景詩(shī)

（山東航天電子技術(shù)研究所，山東煙臺(tái) 264670）

天基信息網(wǎng)絡(luò)低軌非對(duì)稱(chēng)路由協(xié)議研究

李偉明 張素娟 申景詩(shī)

（山東航天電子技術(shù)研究所，山東煙臺(tái) 264670）

天基信息網(wǎng)絡(luò)中的低軌道（LEO）衛(wèi)星因拓?fù)渥兓?、軌道周期短，存在較多的信息網(wǎng)絡(luò)相關(guān)節(jié)點(diǎn)間的非對(duì)稱(chēng)鏈路。文章從路由表優(yōu)化和特殊鏈路處理方案等方面進(jìn)行研究，提出了一種基于分時(shí)的低軌衛(wèi)星網(wǎng)絡(luò)路由算法。以星間鏈路傳輸時(shí)延作為計(jì)算代價(jià)度量來(lái)判斷路由選擇的優(yōu)劣，從鏈路檢測(cè)、路由計(jì)算和數(shù)據(jù)轉(zhuǎn)發(fā)等三部分對(duì)路由協(xié)議進(jìn)行描述，并制定了低軌鏈路處理方案，可以有效地發(fā)現(xiàn)網(wǎng)絡(luò)中的非對(duì)稱(chēng)鏈路，及時(shí)進(jìn)行相應(yīng)處理。最后，仿真對(duì)比分析結(jié)果表明，文章所提出的協(xié)議方案在非對(duì)稱(chēng)鏈路存在的情況下性能更為優(yōu)越。

天基信息網(wǎng)絡(luò)；分時(shí)路由；最短路徑；路由協(xié)議

1 引言

隨著載人航天器、人造衛(wèi)星和空間探測(cè)器的快速發(fā)展，如何保證空間信息高效可靠的傳輸，是當(dāng)前天基信息網(wǎng)絡(luò)的重點(diǎn)。天基信息網(wǎng)絡(luò)由多層衛(wèi)星組成，其中，低軌道（LEO）衛(wèi)星拓?fù)渥兓?、軌道周期短，存在較多的層內(nèi)及層間非對(duì)稱(chēng)鏈路，而空間路由協(xié)議則是以上鏈路實(shí)現(xiàn)有效通信的基礎(chǔ)，其優(yōu)劣程度直接影響到路由算法和通信質(zhì)量的性能。現(xiàn)有的衛(wèi)星網(wǎng)絡(luò)路由協(xié)議大都假定所有的星間鏈路為雙向?qū)ΨQ(chēng)鏈路，但隨著衛(wèi)星網(wǎng)應(yīng)用的不斷更新和拓展，這種假設(shè)的合理性和可行性就明顯出現(xiàn)問(wèn)題。因此，研究非對(duì)稱(chēng)鏈路的路由協(xié)議，對(duì)實(shí)現(xiàn)低軌道衛(wèi)星穩(wěn)定通信具有實(shí)際工程意義。

目前，可根據(jù)對(duì)拓?fù)渥兓幚聿呗缘牟煌瑢⒖臻g路由協(xié)議歸納為：拓?fù)浣Y(jié)構(gòu)固定化路由協(xié)議［1－3］、基于時(shí)空位置信息的路由協(xié)議［4－5］和基于切換技術(shù)的路由協(xié)議［6－8］。這些協(xié)議在對(duì)拓?fù)涓咚賱?dòng)態(tài)變化問(wèn)題的解決策略、鏈路度量值、路徑計(jì)算以及衛(wèi)星失效處理等方面各有特點(diǎn)，其中，基于時(shí)空位置信息的路由協(xié)議相比于其余兩類(lèi)，可根據(jù)當(dāng)前網(wǎng)絡(luò)中承載業(yè)務(wù)的統(tǒng)計(jì)特性動(dòng)態(tài)調(diào)整路由方案，實(shí)現(xiàn)全網(wǎng)資源的最佳分配，避免出現(xiàn)某些鏈路嚴(yán)重超載。而該類(lèi)中的DTRA（Discrete Time based Routing Algorithm）協(xié)議［7］是可適用于多層IP衛(wèi)星網(wǎng)絡(luò)，在充分利用衛(wèi)星網(wǎng)絡(luò)運(yùn)行的規(guī)律性、周期性和可預(yù)測(cè)性等固有特征的基礎(chǔ)上，采用計(jì)算最短時(shí)延路徑的方式，不僅能夠保證單個(gè)時(shí)間段內(nèi)的星上分組無(wú)環(huán)轉(zhuǎn)發(fā)，而且可做到切實(shí)保證路由表切換時(shí)不產(chǎn)生路由環(huán)路。

為此，針對(duì)天基信息網(wǎng)絡(luò)低軌道衛(wèi)星所存在的非對(duì)稱(chēng)鏈路問(wèn)題，本文提出了一種基于分時(shí)的網(wǎng)絡(luò)非對(duì)稱(chēng)路由算法（A－DTRA），從鏈路檢測(cè)、路由計(jì)算及數(shù)據(jù)轉(zhuǎn)發(fā)等三部分對(duì)路由協(xié)議進(jìn)行描述，并制定了非對(duì)稱(chēng)鏈路處理方案，可以有效地發(fā)現(xiàn)網(wǎng)絡(luò)中的非對(duì)稱(chēng)鏈路，及時(shí)進(jìn)行相應(yīng)處理。最后，仿真對(duì)比分析結(jié)果表明，該協(xié)議方案在非對(duì)稱(chēng)鏈路存在的情況下性能更為優(yōu)越，可為建設(shè)空間信息網(wǎng)絡(luò)提供工程參考。

2 相關(guān)定義

在具體闡述DTRA協(xié)議前，先對(duì)協(xié)議內(nèi)各參數(shù)進(jìn)行如下定義：

使用ISLa→b表示衛(wèi)星節(jié)點(diǎn)a和衛(wèi)星節(jié)點(diǎn)b之間的星間鏈路（ISL），使用D（ISLa→b）來(lái)表示衛(wèi)星節(jié)點(diǎn)a到衛(wèi)星節(jié)點(diǎn)b之間的傳輸時(shí)延。衛(wèi)星節(jié)點(diǎn)a與衛(wèi)星節(jié)點(diǎn)b之間的多跳路徑可表示為

式中：Qi表示數(shù)據(jù)分組在中間衛(wèi)星節(jié)點(diǎn)i上的排隊(duì)時(shí)延；Pi表示數(shù)據(jù)分組在該衛(wèi)星節(jié)點(diǎn)上的處理時(shí)延。由于算法僅以ISL傳輸時(shí)延作為計(jì)算代價(jià)度量，因此可將Qi和Pi取為固定值D0，路徑Ra→b上的總傳輸時(shí)延還可表示為

故在衛(wèi)星節(jié)點(diǎn)a到衛(wèi)星節(jié)點(diǎn)b的路徑集合S（Ra→b）中，最短時(shí)延路徑可定義為

針對(duì)衛(wèi)星網(wǎng)絡(luò)具有周期性及可預(yù)測(cè)性的特點(diǎn)，將衛(wèi)星網(wǎng)絡(luò)的運(yùn)轉(zhuǎn)周期預(yù)先分割成為若干等長(zhǎng)的小的時(shí)間片，在每一個(gè)時(shí)間片內(nèi)，分別對(duì)衛(wèi)星網(wǎng)絡(luò)鏈路狀態(tài)進(jìn)行檢測(cè)。經(jīng)過(guò)鏈路檢測(cè)這一步驟后，相當(dāng)于對(duì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行了離散化，拓?fù)浣Y(jié)構(gòu)成為一個(gè)靜態(tài)的加權(quán)有向鏈路圖Gk（權(quán)值設(shè)置為星間鏈路傳輸時(shí)延）。將Gk定義為衛(wèi)星網(wǎng)絡(luò)在時(shí)間片［tk，tk＋1］的有向虛擬拓?fù)鋱D，并用以下的鏈表格式表示：＜a，b，D（ISLa→b），flag＞，其中a和b為直接相鄰衛(wèi)星，flag表示為衛(wèi)星節(jié)點(diǎn)a到衛(wèi)星節(jié)點(diǎn)b的鏈路狀態(tài)標(biāo)志，用以表明在路由通路上是否含有非對(duì)稱(chēng)鏈路。flag的默認(rèn)值是0，表示鏈路是對(duì)稱(chēng)的。

定義起始路由表為等間隔的時(shí)間片內(nèi)對(duì)應(yīng)的有向虛擬拓?fù)鋱D開(kāi)展路由計(jì)算時(shí)產(chǎn)生的路由表［9］。該表是一個(gè)臨時(shí)的數(shù)據(jù)結(jié)構(gòu)，只在離線狀態(tài)下進(jìn)行路由計(jì)算時(shí)使用。衛(wèi)星節(jié)點(diǎn)a的起始路由表由時(shí)間標(biāo)簽和各表項(xiàng)結(jié)構(gòu)組成。時(shí)間標(biāo)簽表示以該時(shí)間點(diǎn)作為起始時(shí)間點(diǎn)的時(shí)間片對(duì)應(yīng)的路由表。起始路由表的表項(xiàng)格式表示為

式中：衛(wèi)星b在此作為目的端節(jié)點(diǎn)，t表示以t為起始時(shí)刻對(duì)應(yīng)的路由表，為衛(wèi)星節(jié)點(diǎn)a到衛(wèi)星節(jié)點(diǎn)b的首選下一跳，D（Ra→b）表示衛(wèi)星節(jié)點(diǎn)a到衛(wèi)星節(jié)點(diǎn)b的最短傳輸時(shí)延，為衛(wèi)星節(jié)點(diǎn)a到衛(wèi)星節(jié)點(diǎn)b的次優(yōu)路徑下一跳。flag1代表首選下一跳的鏈路狀態(tài)標(biāo)志，flag2代表次優(yōu)路徑下一跳的鏈路狀態(tài)標(biāo)志。

簡(jiǎn)化星上路由表定義為衛(wèi)星節(jié)點(diǎn)加載經(jīng)過(guò)時(shí)間片合并處理后的路由表。使用簡(jiǎn)化星上路由表的目的是為了減小星上開(kāi)銷(xiāo)，其表項(xiàng)格式表示為

式中：flagt1，1，flagt1，2為衛(wèi)星節(jié)點(diǎn)a到目的端衛(wèi)星節(jié)點(diǎn)b在t1時(shí)間段的首選下一跳及次優(yōu)路徑下一跳的鏈路狀態(tài)標(biāo)志；flagt2，1，flagt2，2為衛(wèi)星節(jié)點(diǎn)a到目的端衛(wèi)星節(jié)點(diǎn)b在t2時(shí)間段的首選下一跳及次優(yōu)路徑下一跳的鏈路狀態(tài)標(biāo)志。tk表示在一個(gè)系統(tǒng)周期的時(shí)間內(nèi)從tk到tk＋1的時(shí)間段中，當(dāng)前的衛(wèi)星節(jié)點(diǎn)a將首選下一跳Ntk，1a，b及次優(yōu)路徑下一跳Ntk，2a，b當(dāng)作目的端衛(wèi)星節(jié)點(diǎn)b的路由選擇［10－11］。

切換路由表，定義為記錄衛(wèi)星節(jié)點(diǎn)a的起始路由表的切換時(shí)間，該表的表項(xiàng)結(jié)構(gòu)表示為

式中：ttime代表路由表的切換時(shí)刻，表示衛(wèi)星節(jié)點(diǎn)將當(dāng)前路由表切換為以時(shí)間ttime為起始時(shí)間的時(shí)間片對(duì)應(yīng)的路由表；nnumber代表切換后時(shí)間片的原始路由表編號(hào)，與時(shí)間片序號(hào)相對(duì)應(yīng)。切換路由表是臨時(shí)的數(shù)據(jù)結(jié)構(gòu)，在計(jì)算星上路由表時(shí)使用［12］。

3 基于非對(duì)稱(chēng)鏈路的優(yōu)化路由協(xié)議設(shè)計(jì)

路由計(jì)算分為起始路由表計(jì)算及星上路由表計(jì)算兩部分。在執(zhí)行起始路由表計(jì)算之前，可依據(jù)對(duì)ISL動(dòng)態(tài)特性的分析，將星座周期提前劃分，計(jì)算出每段時(shí)間片所對(duì)應(yīng)的有向虛擬拓?fù)鋱D，路由算法的計(jì)算代價(jià)以ISL傳輸時(shí)延作為度量標(biāo)準(zhǔn)。按照衛(wèi)星網(wǎng)絡(luò)的運(yùn)行參數(shù)以及最終鏈路狀態(tài)的檢測(cè)結(jié)果，起始路由表算法可在每個(gè)有向虛擬拓?fù)鋱D上，為所有衛(wèi)星節(jié)點(diǎn)計(jì)算出該時(shí)間片內(nèi)的起始路由表。之后由星上路由表算法遵循避免策略對(duì)起始路由表進(jìn)行合并，生成簡(jiǎn)化的星上路由表［13－14］。其路由表計(jì)算步驟如下：

（1）采用Dijkstra算法計(jì)算路由路徑的首選下一跳，之后計(jì)算出符合無(wú)環(huán)多路徑約束條件下的下一跳集合，并且從集合中選擇路徑時(shí)延最短的衛(wèi)星節(jié)點(diǎn)作為次優(yōu)路徑下一跳。若同時(shí)存在多個(gè)路徑時(shí)延最短者，則優(yōu)先選擇邏輯編號(hào)較小的衛(wèi)星節(jié)點(diǎn)。若次優(yōu)路徑下一跳的集合為空，則將次優(yōu)路徑下一跳設(shè)置為空。

（2）根據(jù)鏈路狀態(tài)檢測(cè)結(jié)果，若首選下一跳衛(wèi)星節(jié)點(diǎn)為失效衛(wèi)星，或是其鏈路狀態(tài)標(biāo)志flag1的值為－1，則將次優(yōu)路徑下一跳作為首選下一跳，并從次優(yōu)路徑下一跳的集合中重新選擇次優(yōu)路徑下一跳，直至滿足首選及次優(yōu)路徑下一跳的鏈路狀態(tài)標(biāo)志flag為0或1為止。

（3）完成起始路由表計(jì)算后，比較相鄰時(shí)間片內(nèi)路由表的內(nèi)容以生成切換路由表。

（4）按照衛(wèi)星網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化的規(guī)律性，若在若干相鄰時(shí)間片內(nèi)衛(wèi)星節(jié)點(diǎn)間的連接關(guān)系不變，而僅是星間鏈路的長(zhǎng)度改變，則起始路由表的內(nèi)容可能完全相同。故為降低星上存儲(chǔ)開(kāi)銷(xiāo)，星上路由表計(jì)算算法首先對(duì)相鄰衛(wèi)星節(jié)點(diǎn)切換前后的起始路由表的內(nèi)容進(jìn)行比較，如連續(xù)若干時(shí)間片的起始路由表內(nèi)容都相同，則將其合并成為同一時(shí)間段的簡(jiǎn)化星上路由表，而時(shí)間段的長(zhǎng)度就等于這些相鄰時(shí)間片長(zhǎng)度之和。

（5）源端衛(wèi)星節(jié)點(diǎn)僅須要按照當(dāng)前的運(yùn)行時(shí)間進(jìn)行查找相應(yīng)時(shí)間段對(duì)應(yīng)的路由表，然后采用簡(jiǎn)化的星上路由表信息進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)即可。

4 協(xié)議性能仿真分析

采用具有12顆衛(wèi)星節(jié)點(diǎn)的網(wǎng)絡(luò)作為低軌衛(wèi)星網(wǎng)絡(luò)仿真模型，分別分布在3個(gè)軌道平面上。衛(wèi)星軌道高度設(shè)為780km，軌道面傾角為86.4°，網(wǎng)絡(luò)運(yùn)行周期為101min，偏心率為0。衛(wèi)星網(wǎng)絡(luò)域模型的鏈路連接關(guān)系如圖1所示。

圖1 衛(wèi)星網(wǎng)絡(luò)域模型的鏈路連接關(guān)系與路由開(kāi)銷(xiāo)（單位s）Fig.1 Link and routing overhead of satellite network zone model

將衛(wèi)星網(wǎng)絡(luò)的運(yùn)行時(shí)間設(shè)置為7200s。衛(wèi)星節(jié)點(diǎn)（0，1）與衛(wèi)星節(jié)點(diǎn)（3，2）之間的平均路由跳數(shù)的仿真結(jié)果如圖2所示，平均端到端時(shí)延仿真結(jié)果如圖3所示。由圖2可知，路由算法A－DTRA所建立的路由，其路由跳數(shù)的平均值為4跳。圖3中的平均端到端時(shí)延穩(wěn)定維持在100ms左右，與理論分析相同。

不同于現(xiàn)有的基于虛擬拓?fù)?、覆蓋區(qū)域劃分或虛擬節(jié)點(diǎn)的路由算法，該算法利用最小路徑計(jì)算原理，把動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)劃分成按時(shí)間段分割的一系列連續(xù)的靜態(tài)拓?fù)浣Y(jié)構(gòu)，可利用局部狀態(tài)信息，僅須要在時(shí)間的分割點(diǎn)更新路由表即可，在星上可進(jìn)行實(shí)時(shí)計(jì)算，可較好地解決擁塞問(wèn)題。

圖2 平均路由跳數(shù)曲線Fig.2 Average number of hops curve

圖3 平均端到端時(shí)延曲線Fig.3 Average end－to－end delay curve

5 結(jié)束語(yǔ)

本文以天基信息網(wǎng)絡(luò)低軌道衛(wèi)星內(nèi)存在的非對(duì)稱(chēng)鏈路問(wèn)題為背景，研究了一種基于分時(shí)的低軌衛(wèi)星網(wǎng)絡(luò)非對(duì)稱(chēng)路由算法。從鏈路檢測(cè)、路由計(jì)算及數(shù)據(jù)轉(zhuǎn)發(fā)等三部分對(duì)路由協(xié)議進(jìn)行描述并制定了非對(duì)稱(chēng)鏈路情況處理方案，可有效地發(fā)現(xiàn)網(wǎng)絡(luò)中的非對(duì)稱(chēng)鏈路并及時(shí)進(jìn)行相應(yīng)處理。仿真算例表明：在非對(duì)稱(chēng)鏈路情況下，本協(xié)議方案性能更為優(yōu)越，可較好地避免擁塞問(wèn)題。這種設(shè)計(jì)思想可以做進(jìn)一步改進(jìn)后推廣到低中高跨層網(wǎng)絡(luò)的非對(duì)稱(chēng)鏈路路由中。

（References）

［1］Chang H S，Kim B W，Lee C G，et al.FSA－based link assignment and routing in low－earth orbit satellite networks［J］.IEEE Transactions on Vehicular Technology，1998，47（3）：1037－1048

［2］Gounder V V，Prakash R，Abu Amara H.Routing in LEO－based Satellite Networks［C］／／IEEE Emerging Technologies Symposium on Wireless Communications and Systems.New York：IEEE，2000：221－226

［3］Werner M.A dynamic routing concept for ATM－based satellite personal communication networks［J］.IEEE Journal on Selected Areas in Communications，1997，15（8）：1636－1648

［4］Hashimoto Y，Sarikaya B.Design of IP－based routing in a LEO satellite network［C］／／Proceedings of Third International Workshop on Satellite－Based Information Services.California：WOSBIS，1998

［5］周云暉，孫富春，張鈸.一種基于時(shí)隙劃分的三層衛(wèi)星網(wǎng)絡(luò)QoS路由協(xié)議［J］.計(jì)算機(jī)學(xué)報(bào)，2006，29（10）：1813－1822.Zhou Yunhui，Sun Fuchun，Zhang Bo.A time－division QoS routing protocol for three－layered satellite networks［J］.Chinese Journal of Computers，2006，29（10）：1813－1822（in Chinese）

［6］Akyildiz I F，Ekici E，Bender M D.MLSR：a novel routing algorithm for multilayered satellite IP networks［J］.Networking，IEEE／ACM Transactions on，2002，10（3）：411－424

［7］Mao T Y.A multicast routing algorithm for LEO satellite networks［C］／／2009ETP International Conference on Future Computer and Communication.Wuhan：ETP，2009：94－96

［8］S Scott K，Burleigh S.Bundle protocol specification，IETF RFC5050［S］.Pasadena：NASA Jet Propulsion Laboratory，2007

［9］Lee J，Kang S.Satellite over Satellite（SOS）network：a novel architecture for satellite network［C］／／Proceedings of Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies.New York：IEEE，2000：315－321

［10］Liu C，Wu J.Destination－region－based local minimum aware geometric routing［C］／／IEEE Internatonal Conference on Digital Object Identifier.New York：IEEE，2007：127－131

［11］Henderson T R.Networking over next－generation satellite systems［D］.Berkeley：University of California，1999

［12］Vutukury S，Garcia J J.A simple approximation to minimum delay routing［J］.ACM SIFCOMM Computer Communication Review，1999，29（4）：227－238

［13］Sam J.Semantically routing queries in peer－to－peer networks［C］／／Proceedings of the International Workshop on Peer－to－Peer Computing.Berkeley：IPTPS，2002：152－160

［14］Bai J J，Lu X C，Lu Z X.Compact explicit multi－path routing for LEO satellite networks［C］／／Porceedings of IEEE Workshop on High Performance Switching and Routing.New York：IEEE，2005：296－301

（編輯：張小琳）

Research on Asymmetric Routing Protocol for LEO Satellite of Space－based Information Network

LI Weiming ZHANG Sujuan SHEN Jingshi
（Shandong Aerospace Electr－technology Institute，Yantai，Shandong 264670，China）

LEO satellites of space－based information network have the characteristics of rapid topology transforming，short orbital period，and more asymmetric links inside layers.This paper studies routing table optimization，special link solutions etc，and proposes a LEO satellite network routing algorithm based on time division.It determines the routing selection result according to inter－satellite link transmission delay，describes routing protocol in three aspects of link detection，routing calculation and data relay，and formulates the dealing scheme for LEO link，which can find out and deal with the asymmetry of the network effectively.Finally，the simulation result shows that the protocol scheme proposed by this paper is more effective in the condition of asymmetric link.

spatial information network；discrete time routing；shortest path；routing protocol

TN915

：ADOI：10.3969／j.issn.1673－8748.2016.01.011

2015－11－17；

：2016－01－11

國(guó)家高新技術(shù)研究發(fā)展計(jì)劃（863計(jì)劃）（2015AA7015087）

李偉明，男，博士，工程師，從事衛(wèi)星編隊(duì)控制及組網(wǎng)協(xié)議、通信與導(dǎo)航技術(shù)研究工作。Email：liweiming513＠163.com。