基于鏈路預測的LEO衛星稀疏自組織網絡異步路由算法

戴永珊 ， 姜興龍 ， 劉會杰

（1.中國科學院 上海微系統與信息技術研究所，上海 200050；2.上海微小衛星工程中心 上海 201210）

衛星星座與衛星編隊飛行技術是現階段兩種主流衛星集群實現方式[1]。衛星星座系統是面向特定需求而設計的通信系統，在最初設計階段限定了網絡的規模和容量，在業務需求超過原有系統的承載能力時，需要進行網絡擴容；而衛星編隊飛行中以美國的F6計劃[2]最為典型，以“快速響應需求、靈活采辦、快速研制、快速部署、分散目標、靈活重構、適于攻防對抗”為設計目標，需要具備自發現、自動配置、故障自愈功能；此外，復雜的空間環境使衛星及星間鏈路存在故障風險。因此，航天任務對空間網絡提出了新的技術要求——具有可快速兼容平穩擴展、自主故障發現并修復的特性，自組織網絡技術正好可以解決這個技術難題。隨著空間技術的發展，未來航天任務的發展正向靈活的分布式動態星座、成型空間移動平臺組成的自組織空間網絡[2]方向靠攏。另一方面，星座系統往往受到成本及風險的制約，在分階段擴展部署過程中，稀疏空間網絡的路由問題將是其面對的首要問題。

在Ad Hoc網絡中，移動節點通過無線多跳實現相互通信，開發一種能有效找到節點間路由的動態路由算法是網絡設計的關鍵。常用的自組織路由算法[4]主要有DSDV、WRP、AODV、DSR等，但應用于空間自組織網的路由算法研究較少。文獻[2]研究了空間自組織網絡的拓撲結構、消息傳遞機制、路由算法，其路由算法通過對空間網絡中每一個節點進行特殊的多層次命名，根據節點名稱的可識別性進行路由路徑選擇。該方法在空間系統龐大情況下，具有較高效率，而在單個衛星系統中效率極低。文獻[5]提出了在LEO/MEO衛星網絡中運用自組網思想，將整個網絡劃分成簇，將一張大網規劃成子網，降低系統信令開銷，該方案適用于網絡節點密集，且星間結構變化不頻繁的情況。

鑒于對稀疏空間網絡路由算法研究的不足，以LEO衛星稀疏自組織網絡為研究對象，針對缺乏持續連接（缺乏穩定的端到端路徑）、高延時、網絡資源有限的特點，提出一種基于鏈路預測的異步路由算法，并從時延最優和跳數最少兩個方面對算法進行了仿真比較。

1 基于鏈路預測的LEO衛星稀疏自組織網絡異步路由

LEO衛星稀疏自組織網絡缺乏穩定連接，傳統的同步路由算法通常無效，但這不表示衛星間不能傳輸數據。隨著衛星的運動，鏈路在網絡中不同的位置不斷連接或斷開。如果將單位時間內的網絡看成一個靜態網絡，用靜態的無向圖描述，將多個這樣的無向圖按時間序列重疊，則必然存在一條或多條“基于時間推移的端到端路徑”[6]。基于這種思想，通過鏈路預測預估衛星間的連接關系，將衛星網絡通過時間-空間圖描述，然后基于最少跳數、最短時延準則，運用三維的Bellman-Ford算法，得到最優路由表。

1.1 研究模型與度量標準

Walker星座具有很好的對稱性，在星座系統中有廣泛的應用，例如Globalstar，GPS，北斗。研究模型選擇Walker傾斜軌道星座[5]，由N顆衛星在P個相同傾斜衛星軌道平面組成、能夠全球覆蓋的衛星星座。Walker星座通常采用符號N/P/F表示，參數描述：

1）S＝N/P表示每個軌道面衛星的個數，F表示 Walker星座的相位因子（F=1，2，…，P-1），F 確定了相鄰軌道平面上衛星之間的偏離角度Δwf=2πF/N；

2）傾斜軌道平面的上升節點沿著赤道等間隔排列；

3）傾斜軌道平面之間具有固定的平面偏移ΔΩ=2π/P；

4）每個傾斜軌道平面內衛星以Δω=2π/S間隔均勻分布。

文中Walker星座模型為應用場景，研究LEO衛星稀疏異步自組織網絡的路由算法，從而實現星上最優路徑路由表生成。

根據稀疏Ad Hoc網絡的結構特點[7]，可歸納主要的性能度量準則如下：

1）跳數：描述了源到目的節點的組成路徑的鏈路數量，跳數少則整體功耗低。

2）端到端時延：端到端時延指的是數據包從目的到源節點所經歷的時間，包括路由等待時間和接口時延等。

3）生存時間：路由生存時間指的是路由建立開始到下一次更新所能夠正常使用的時間。

4）路由容量：路由容量用來描述源到目標節點在生存時間內能夠傳輸的最大數據量。

本算法為異步路由算法，只要前一個節點的數據成功傳輸到下一個節點，以前的鏈路不再影響后續路由，路由生存時間只與數據當前到達時間、時間窗結束時間相關，故算法選擇最少跳數、最短端到端時延為最優路由路徑的衡量準則。

1.2 路由算法描述

Walker星座是一個具有延遲拓撲結構[8]的LEO衛星稀疏自組織網絡，不同節點對應不同衛星，節點間的連接關系代表星間鏈路，如圖1所示（以Walker6/2/1為例）。衛星隨時間不斷運動，網絡拓撲結構也在不斷變化。傳統靜態圖不能表示出這種變化過程，需要一系列的靜態圖來建立隨時間變化的延遲拓撲網絡結構模型。如圖1所示，每一張靜態圖都是網絡中所有節點的快照，記錄當前時刻各節點間的連接關系。在T0時刻，該星座存在三條星間鏈路，整個網絡是不連通的，不能實現從sat11至sat13的數據傳送。本文描述的鏈路預測，是指通過STK軟件實時預報的軌道信息，計算出衛星間的連通關系，得到任意時刻的網絡連接圖。通過約束星間的可見條件，可以模擬衛星網絡的變化。

圖1 衛星網絡的隨時間變化的連接關系Fig.1 A time-evolving topologies of a satellite network

為方便下文算法的描述，進一步分析上述模型，并轉化為圖論問題。將連續的時間分成離散時間序列{1，2，…，T}，該星座有 6 個節點，分別為 sat11、sat12、sat13、sat21、sat22、sat23，以 S={s1，s2，…，s6}表示，而 Gt=（St，Et）表示網絡在時刻 t的網絡快照，其中∈Et表示節點si和節點sj在時刻t存在一條互相連通的信道，因此該網絡可以表示為{Gt|t=1，2，…，T}。圖2描述了在時刻t處的星座網絡對應的快照示意圖，這種表示法包含了空間和時間上的所有信息，與大多數現有的延遲拓撲網絡路由算法適用的如圖3所示的連接模型不同（在時刻t每個節點都連接著多個其余節點，有多條可選擇路徑，整個網絡中任意兩個節點互相可達，但該模型忽略了網絡中的時間、順序信息，沒有反映出同一時刻鏈路的部分有效性），為此，本文條件下，需針對圖2所示模型進行深入分析。

圖2 衛星網絡的網絡快照示意圖Fig.2 A sequence of snapshots of the satellite network at each time slot satellite network

圖3 衛星網絡的網絡連接示意圖Fig.3 The aggregated graph modelofthe

將圖2的靜態圖轉化為圖4的時間-空間關系圖G=（υ，ε）。由圖知，該時間-空間關系圖G中有T+1組節點，每組含6 個節點，其中 υ={|j=1，…，6 and t=0，…，T}，是所有節點的集合，因此網絡總共含6（T+1）個節點。圖中所示有兩種類型的鏈路，分別為時間鏈路和空間鏈路，組與組之間的空白部分代表的是時間的流逝，在一塊空白中數據保存在本節點則向右平傳，否則在該時間段內傳送到下一個時間節點。因此，表示在第（t-1）秒至第t秒間，數據保存在j節點，相當于時間鏈路；表示在第（t-1）秒至第t秒間，數據從節點i傳送到j節點，相當于空間鏈路。通過上述定義，時間-空間關系圖中的任意一條鏈路都能用數學模型抽象表示，如圖4所示，路徑sat110sat133表示一條路由路徑從節點sat11出發，在節點sat11處存儲了1個單位時間間隔，在第二個單位時間間隔傳送至節點sat22，在第3個單位時間間隔傳送至節點sat13。

圖4 衛星網絡的時間-空間連接關系表Fig.4 The time-space graph of the satellite network

至此，問題轉化為通過圖4表示的連接關系，選擇一條最優路徑，由起始點至終點。即：假定鏈路都是可靠的，基于最少跳數、最短端到端時延原則，利用三維的Bellman-Ford算法求取最優路徑。

Bellman-Ford算法基本思想是通過迭代確定最優路徑。假定我們尋找一條從源節點s1到目的節點s3的最短端到端時延路徑，以迭代方程表示如下：

其中，dij由每一時刻的鄰接矩陣給出，若衛星i和衛星j之間存在星間鏈路，則設定其鏈路重量dij為1，否則為無窮大（Inf）。

在s1→s3最短端到端時延路徑求解中，目的節點為s3，距離符號Di表示在一定限制條件下，從i節點到目的節點s3的最優路徑的代價（其中i為任意中間節點），每次迭代過程中，所有節點的距離標號都是臨時標號，當迭代終止時，限制條件被完全消除，因此所有節點的臨時標號同時被轉為永久標號，j是最優路徑的中間節點。即D是第h次迭代得到的節點i的臨時標號，表示經h步可到達的路徑中最短徑的長度。最后得到的Di=D是最終的最短路徑的時延。

2 算法仿真

為了對算法的性能進行仿真驗證，搭建基于STK和OPNET的仿真平臺，選取典型的仿真場景進行系統建模和仿真。

2.1 仿真場景設置

仿真目的主要包括：1）驗證基于鏈路預測的低軌衛星自組織網絡異步路由算法，因此僅包含衛星交換網絡，不包括地面站、終端等設備；2）分析其擴展性，比較該算法在不同規模網絡結構中的整體網絡性能；3）比較以不同性能度量為設計目標的系統性能，性能度量選取典型的平均時延和平均跳數。

網絡規模分別選取常見的6/2/1Walker星座、12/3/1Walker星座、24/4/1Walker星座、48/8/1 Walker星座。衛星軌道選擇軌道高度為1 400 km，軌道傾角為52°的圓軌道（參照Globalstar）。仿真中假設衛星天線為全向天線，限定最遠通信距離為該軌道高度視距可見最大距離8 800 km，仿真周期設為2個軌道周期（軌道周期為6 600 s）。在時延統計上，假設星間鏈路帶寬足夠大，不存在擁塞，時延主要來自等待時延和傳播時延。

2.2 仿真結果

根據上述設置，分別以最少跳數和最短時延為設計準則，仿真分析基于鏈路預測的LEO衛星稀疏自組織網絡異步路由算法的可行性，得到了以平均時延、平均跳數為衡量準則的網絡性能隨星座規模的變化規律。

如圖5所示，網絡傳輸平均時延與Walker星座規模的變化關系，由結果分析可知：衛星的平均傳輸時延隨著衛星規模的增加而減小。1）在網絡規模較小，即LEO衛星分布很稀疏的情況下（15顆星以下），星座網絡是非連通的，時延以等待時延為主（等待時延遠大于傳播時延），兩種準則得到的平均時延普遍偏高；2）隨著網絡規模逐漸擴大，即LEO衛星分布相對密集情況下，以最短時延實現路由路徑尋找效果更好。在衛星規模大于24顆時，星座網絡是全連通的，平均時延以傳播時延為主，由于系統仿真的時延統計設置最小分辨率為分鐘，故該值恒為1。

圖5 以最少跳數和最短時延為設計準則的平均時延Fig.5 The average cost time of the network based on minimumhops and minimum delay

圖6 以最少跳數和最短時延為設計準則的平均跳數Fig.6 The average hops of the network based on minimumhops and minimum delay

如圖6所示，網絡傳輸平均跳數與Walker星座規模的變化關系，由結論分析可知：以最少時延實現最優路由路徑尋找，所耗費的網絡平均跳數大于以最少跳數準則，且隨著網絡規模的擴大，差距越明顯；為實現最少跳數，網絡平均最小跳數長期保持接近于1（卻總是保持大于1，有一些節點不能通過一跳傳輸直接到達目的節點）。

綜上所述，平均時延最小準則可以得到時延性能突出的路由表，但隨著網絡規模的擴大將帶來平均路由跳數的增加，也將大大提高星間鏈路的傳輸負荷，這對稀缺的星間鏈路傳輸帶寬資源提出了挑戰；而平均跳數最小準則隨著衛星規模的擴大，平均跳數變化相對平穩，對星間鏈路傳輸帶寬要求較低，但時延性能相比平均時延最小準則大幅增加。

3 結束語

基于現有衛星集群方式，分析其組網的技術特點，考慮移動自組織網絡技術，提出一種基于鏈路預測的稀疏LEO自組織網絡異步路由算法，并通過仿真驗證了算法的可行性。該算法具有擴展性、抗毀性，適用范圍廣的優點。

但該算法也有不足之處，算法描述模型中一個單位時間只允許一跳傳輸，若需要在一個單位時間間隔內進行多跳，則需要在算法中添加虛擬的路徑，將多跳起始點與終點相連接，這可作為稀疏自組織網絡的下一步研究問題。同時，可進一步研究考慮星間鏈路帶寬較小并存在擁塞的情況下算法采用自適應的機制去調整路由優化的準則。

[1]董云峰，王興龍.衛星集群概念研究[J].航天器工程，2012（4）:83-88.DONG Yun-feng，WANG Xing-long.Research on conception of satellite cluster[J].Spacecraft Engineering，2012（4）:83-88.

[2]吳勤.美國F6計劃概況[J].國際太空，2008（5）:1-5.WU Qing.The general situation of the F6 plan[J].Space International，2008（5）:1-5.

[3]Chien-Chung Shen， SundaramRajagopalan， GirishBorkar.A exible routing architecture for ad hoc space networks[J].Computer Networks，2004(46):389-410.

[4]曹英烈.移動ad hoc網絡路由算法研究[D].廣州：華南理工大學，2006.

[5]李喆，李冬妮，王光興.LEO/MEO衛星網絡中運用自組網思想的動態路由算法[J].通信學報，2005，26（5）:50-56.LI Zhe，LI Dong-ni，WANG Guang-xing.New dynamic routing algorithm based on MANET technologyin the LEO/MEO satellite network[J].Journal on Communications，2005，26（5）:50-56.

[6]王欣.容遲/容斷移動自組織網絡路由技術研究[D].天津：天津大學，2010.

[7]Cruz-Sa'nchez H，Franck L，Beylot A L.Routing metrics for store and forward[J].The Institution of Engineering and Technology，2010，4（13）:1563-1572.

[8]Huang M，Chen S，Li F，et al.Topology design in time-evolving delay-tolerant networks with unreliable links[C]//Global Communications Conference（GLOBECOM），2012IEEE.IEEE，2012:5296-5301.