李偉明 張素娟 申景詩

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

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

李偉明 張素娟 申景詩

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

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

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

1 引言

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

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

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

2 相關(guān)定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

（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］周云暉，孫富春，張鈸.一種基于時隙劃分的三層衛(wèi)星網(wǎng)絡(luò)QoS路由協(xié)議［J］.計算機學(xué)報，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

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

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