天基信息網絡低軌非對稱路由協議研究

李偉明 張素娟 申景詩

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

天基信息網絡低軌非對稱路由協議研究

李偉明 張素娟 申景詩

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

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

天基信息網絡；分時路由；最短路徑；路由協議

1 引言

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

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

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

2 相關定義

在具體闡述DTRA協議前，先對協議內各參數進行如下定義：

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

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

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

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

定義起始路由表為等間隔的時間片內對應的有向虛擬拓撲圖開展路由計算時產生的路由表［9］。該表是一個臨時的數據結構，只在離線狀態下進行路由計算時使用。衛星節點a的起始路由表由時間標簽和各表項結構組成。時間標簽表示以該時間點作為起始時間點的時間片對應的路由表。起始路由表的表項格式表示為

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

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

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

切換路由表，定義為記錄衛星節點a的起始路由表的切換時間，該表的表項結構表示為

式中：ttime代表路由表的切換時刻，表示衛星節點將當前路由表切換為以時間ttime為起始時間的時間片對應的路由表；nnumber代表切換后時間片的原始路由表編號，與時間片序號相對應。切換路由表是臨時的數據結構，在計算星上路由表時使用［12］。

3 基于非對稱鏈路的優化路由協議設計

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

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

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

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

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

（5）源端衛星節點僅須要按照當前的運行時間進行查找相應時間段對應的路由表，然后采用簡化的星上路由表信息進行數據轉發即可。

4 協議性能仿真分析

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

圖1 衛星網絡域模型的鏈路連接關系與路由開銷（單位s）Fig.1 Link and routing overhead of satellite network zone model

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

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

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

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

5 結束語

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

（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］周云暉，孫富春，張鈸.一種基于時隙劃分的三層衛星網絡QoS路由協議［J］.計算機學報，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

國家高新技術研究發展計劃（863計劃）（2015AA7015087）

李偉明，男，博士，工程師，從事衛星編隊控制及組網協議、通信與導航技術研究工作。Email：liweiming513＠163.com。