李涵秋，魏 達，朱建啟，肖 慶，馬 艷

(1.吉林大學 計算機科學與技術學院，長春 130012；2.西安衛(wèi)星測控中心，西安 710043)

0 引 言

采用星間鏈路，導航星座能夠在空中組網，可以不依賴地面設備實現所有網絡節(jié)點的連接，將各顆衛(wèi)星有機地聯結為一個整體[1]。路由是星間互聯的核心,路由協議直接決定著星間互聯與數據傳輸性能[2]。衛(wèi)星導航系統所提供的各類服務都依賴于衛(wèi)星播發(fā)的廣播星歷、衛(wèi)星鐘差和衛(wèi)星歷書等導航電文，這是由上行數據注入系統負責保障的。上行數據注入系統是衛(wèi)星導航系統的喉舌，處于極其重要的地位[3]。同時，在導航星座網絡中，存在多種不同類型的數據流量傳輸，星上處理資源以及星間鏈路資源相對有限。如何應對導航星座網絡中的各種問題，充分利用導航星座網絡的獨特特性，實現高效的數據傳輸，選取合適的路由成為關鍵[4]。

針對基于星間鏈路的衛(wèi)星星座系統星間路由問題，國內外眾多學者已進行了大量的研究工作。文獻[4]提出了一種帶有指向性天線分時隙通信的導航星座網絡的算法。文獻[5]提出了一種考慮鏈路異常狀態(tài)的路由改進算法，但該算法需要檢測結束后對整個星座的鏈路狀態(tài)信息進行實時更新，時間和空間上消耗較大。文獻[6]提出了一種多層鏈路拓撲及混合路由設計方案，該方案考慮了鏈路速率及節(jié)點負載，但是沒有考慮發(fā)送數據總量。文獻[7]提出了一種利用星間鏈路將境外星數據快速回傳至境內的路由優(yōu)化方法。大部分工作在考慮“北斗”系統衛(wèi)星上行數據上注時，將每顆衛(wèi)星作為獨立的管理對象進行調度。對于地面站可見的衛(wèi)星直接進行數據上注，對于地面站不可見的衛(wèi)星通過可見衛(wèi)星的星間鏈路進行上注數據轉發(fā)，數據上注包含地面站到可見衛(wèi)星、地面站到可見衛(wèi)星再到不可見衛(wèi)星兩種類型。當可見衛(wèi)星與不可見衛(wèi)星所需上注的數據相同時，由于各個衛(wèi)星上注過程獨立，可見衛(wèi)星向多顆不可見衛(wèi)星進行轉發(fā)就需要地面站重新上注多次，既占用了寶貴的信道資源又延長了星座的數據上注完成時間。

本文針對“北斗”導航系統日常管理維護中數據上注時隙表、路由表等數據更新操作中星座各星更新數據一致的特點，考慮鏈路帶寬、更新時限等因素，提出了一種“北斗”導航系統星座數據上注更新路由算法。仿真結果表明，該方法可以有效縮短“北斗”導航星座全網上行注入數據更新的時間。

1 導航鏈路數據上注

1.1 導航星座建鏈約束

“北斗”導航系統采用混合型導航星座，星座包括24顆中地球軌道衛(wèi)星(Medium Earth Orbit，MEO)、3顆傾斜地球同步軌道衛(wèi)星(Inclined Geo Synchronous Orbit，IGSO)和3顆地球同步軌道衛(wèi)星(Geostationary Earth Orbit，GEO)。地面控制中心可以通過星間鏈路的建立經由境內星與境外星建立通信，實現境外星遙測數據的回傳和遙控指令的上注[8]。

導航星座建鏈受到多種限制因素的制約，可歸納為兩大類。第一類為可見性約束，包括幾何可見約束、天線可視約束和星間距離約束?？梢娦约s束是建立星間鏈路的前提，導航星座構成了一個拓撲結構不斷變化的空間信息網絡，所以傳輸的時效性非常重要，如果兩顆衛(wèi)星在一個可見時段內數據未傳輸完畢，下個可見時段可能是幾十分鐘甚至十幾個小時之后。所以數據上注的耗時并不是線性的，受星間可見約束的影響會有階躍式的延長。第二類為功能性能約束，“北斗”導航星座的星間鏈路需要兼顧星間測量、地面定軌、遙測下傳等要求，即使在兩顆衛(wèi)星完全可見的時段內也無法保持兩顆衛(wèi)星之間的長鏈接，而是為了滿足位置精度(Position Dilution of Precision，PDOP)的要求，在一定時間內要一顆衛(wèi)星保證盡可能多地與其他衛(wèi)星鏈接。這就導致了單位時間內指定衛(wèi)星間的傳輸容量是有限的，當上注數據量較大時短時間無法完成上注，地面站與衛(wèi)星及衛(wèi)星間的可見關系可能發(fā)生變化，需要考慮星間鏈路的拓撲變化情況。

1.2 導航星座數據上注現狀

“北斗”全球衛(wèi)星導航網絡由空間段和地面段組成：空間段包括 MEO、IGSO、GEO 星座，是多層衛(wèi)星網絡；地面段主要用于維護空間段諸衛(wèi)星的正常運轉。上行數據注入系統將地面運行控制系統生成的導航電文及載荷管理指令上注到衛(wèi)星并保持及時更新，是地面運行控制系統有效管理和控制星上業(yè)務載荷的有效途徑，是保障衛(wèi)星導航系統服務的“生命線”，其工作直接影響系統服務的連續(xù)性和穩(wěn)定性[3]。

“北斗”導航系統采用空時分多址(Space Time Division Multiple Access，STDMA)接入模式用于星間鏈路衛(wèi)星組網。在該接入模式下，衛(wèi)星之間按照預先安排的時隙有秩序的建立鏈接。將連續(xù)的衛(wèi)星軌道時間劃分成多個超幀T，每個超幀T內認為星座間的可見關系固定，作為是一個鏈路分配的基本操作單元。同時超幀T由多組相等的時隙組成，每個時隙作為星間鏈路的建立和維護的基本單元，星間鏈路的切換等操作都是在各個時隙之間轉換完成[9]。

“北斗”星間鏈路數據上注一般過程如圖1所示，地面站分別對M11、M21和M31星進行數據上注。當各星上注數據不同時考慮的是三顆星之間的上注操作順序；而當上注數據是全網統一的時隙表等數據時，圖1中作為中轉節(jié)點的M11就會接收到相同的數據MX1Data三次，同時整個天地網絡仍有三次完整的建鏈過程。如果考慮只向M11發(fā)送一遍數據，而后由M11在后續(xù)時隙中向M21和M31發(fā)送數據，將極大地降低數據占用整個信道的帶寬，同時也能顯著縮短整個星座的數據更新時間。此時，需要考慮的問題是向M11星發(fā)送數據的時機以及M11向M21和M31轉發(fā)數據的時機。

圖1 數據上注過程示意圖

2 動態(tài)鏈路樹路由方法

為了解決全網統一更新相同數據時，每顆衛(wèi)星分別建鏈造成的對整個天地網絡的信道冗余占用，本文提出了一種動態(tài)鏈路樹的上行路由改進算法。下面先介紹需要引入的相關概念，然后對算法步驟進行描述。

2.1 動態(tài)鏈路樹概念

“北斗”導航系統的星間鏈路在一個超幀T內可見關系及路由關系固定，一個超幀時段對應一張路由表，下一超幀時段衛(wèi)星可見關系發(fā)生變化，就對應另一張新的路由表。為簡化說明問題，選取某一超幀內包含1個地面節(jié)點和4個衛(wèi)星節(jié)點的前8個時隙構成的路由表，如圖2所示，在第二個時隙地面站與M01星直接鏈接，地面站不直接與M02星、M03星和M04星鏈接，而是通過M01星轉發(fā)進行通信。為了描述改進路由策略，需要將圖2中所示的路由表轉換為一種邊可擴展的動態(tài)樹形式。

圖2 星間鏈路局部路由表

下面對動態(tài)鏈路樹進行定義。

定義1 動態(tài)鏈路樹是由星間鏈路路由表生成的樹，其中樹的根節(jié)點為星間鏈路中的地面節(jié)點或控制中心；樹的節(jié)點是星間鏈路中建立鏈接的各個節(jié)點，同時按照從根節(jié)點幾跳可達作為樹的層數，對其余節(jié)點進行排列；樹中的邊表示兩個節(jié)點可以建立直接鏈接，邊的值為兩個節(jié)點之間建鏈時隙的列表。

選取一個超幀T內的路由表，由圖2所示的星間鏈路路由表生成的動態(tài)鏈路樹如圖3所示，樹中總共包含5個節(jié)點，地面站為根節(jié)點，一跳可與地面站建立鏈接的M01星為第一層，兩跳可與地面站建立鏈接的M02、M03、M04星為第二層，同時M01與地面站之間邊的值為一個動態(tài)擴展的序列。在第一組時隙中M01星與地面站在第二個時隙建鏈，設一組時隙包含的時隙總數為n，則在第二組時隙中M01星與地面站是在2+n的相對時隙建立鏈接，同理在一個超幀T內M01星與地面站按照分組時隙周期性的建鏈，建鏈的相對時隙組成擴展的邊序列[2,2+1n,2+2n,2+3n,…]，直到該超幀時間結束。其他邊同理為星間鏈路兩節(jié)點間建立鏈接的動態(tài)擴展時隙序列。

圖3 星間鏈路局部動態(tài)鏈路樹

建立了動態(tài)鏈路樹后，需要對全網上行注入的效果進行評價，引入兩個評價指標,即鏈路占用總時隙數量和鏈路最后更新時隙。下面結合動態(tài)鏈路樹進行定義。

定義2 鏈路占用總時隙數量是數據上注完成整個鏈路所有節(jié)點數據更新所占用的時隙數量的總和，為動態(tài)鏈路樹中所有葉節(jié)點中每個葉節(jié)點實際用于傳輸的最大時隙的總和。

圖3中地面站在第二個時隙與M01星鏈接，然后M01星在第七個時隙與M02星鏈接，看似這個鏈接過程只有第二時隙和第七時隙兩個時隙，然后實際上數據轉發(fā)到M01星時，M01星無法立即與M02星建立鏈接，而是需要在星上暫存數據到第七個時隙然后再向M02星轉發(fā)。由于星上存儲等資源的限制，該次上注到M02星的過程實際消耗為7個時隙。因此，圖3中的鏈路占用總時隙數量為M02星、M03星和M04星從地面站到各節(jié)點實際用于傳輸的最大時隙的總和。

定義3 鏈路最后更新時隙為星間鏈路所有完成數據上注更新的最后相對時隙數，為鏈路中各節(jié)點實際用于數據上注時隙中的最大值。

圖3中，假設M01星在第二個時隙完成數據更新，M02星在第七個時隙完成數據更新，M03星在第四個時隙完成數據更新，M04星在第六個時隙完成數據更新，則四個節(jié)點中的最大時隙數為7，整個鏈路的最后更新時隙就是7，這代表了從數據上注開始，經歷7個時隙該網絡中的所有節(jié)點都能夠完成數據更新。

2.2 動態(tài)鏈路樹路由方法

通過將星間鏈路路由表轉換成動態(tài)鏈路樹，將“北斗”系統星間鏈路的全網數據更新問題轉化為樹的遍歷問題。與一般遍歷樹算法不同之處在于，節(jié)點之間的連接受到建鏈時隙的邊權值約束。具體體現在當前節(jié)點與下一級節(jié)點的建鏈時隙一定要大于當前節(jié)點與父節(jié)點的建鏈時隙；當前節(jié)點有多個子節(jié)點時，各子節(jié)點之間的遍歷順序為各節(jié)點最近與當前節(jié)點的可建鏈時刻進行排列。下面給出動態(tài)鏈路樹路由算法的偽代碼:

算法名稱：updateBDLinks #上行路由改進算法

算法輸入：nodeTree #動態(tài)樹

rootStr #根節(jié)點名稱

rootValue #根節(jié)點權值

算法輸出：edgeListDic #動態(tài)邊序列

subNodes=list(nodeTree.Subs) #獲得所有子節(jié)點

For item in subNodes:

IfrootStr!=‘Root’: #如果不是根節(jié)點

edgeKey=rootStr+item #形成兩節(jié)點的鍵值

linkList=edgeListDic[edgeKey]

#獲得兩節(jié)點間時隙序列

searchValue=next(x for x in linkList if x>rootValue)

#找到比根節(jié)點權值大的第一個時隙

rootValue=searchValue #更新根節(jié)點權值

linkList[edgeKey][searchValueIndex]=0

#標記使用時隙

subtree=nodeTree[item] #當前節(jié)點子節(jié)點

updateBDLinks(subtree,item,rootValue)

#遞歸調用

算法描述中，動態(tài)邊序列集合edgeListDic為字典結構，Key為建鏈兩個節(jié)點衛(wèi)星的名稱組合，Value為這兩個衛(wèi)星的建鏈時隙列表。最后遍歷實際使用的時隙序號也在edgeListDic中的各時隙列表中進行了標記。

3 仿真驗證

3.1 仿真場景設置

將“北斗”三代導航星座中的24顆MEO衛(wèi)星標記為M01～M24，3顆GEO衛(wèi)星標記為G01～G03，3顆IGSO衛(wèi)星標記為I01～I03。根據“北斗”導航系統星座公開的TLE軌道數據，選取地面站坐標為北京站，計算2020年11月1日一天24 h的可見性及路由表，共形成24個超幀T1～T24，每個超幀時長為1 h，一個超幀內衛(wèi)星間可見性及路由表不變。

由“北斗”三代導航星座超幀T1時段內的路由表生成的動態(tài)鏈路樹如圖4所示。從圖4中可知，由地面站作為根節(jié)點，樹的層數就是根節(jié)點到該層各節(jié)點的跳數。在該超幀內最多跳數為3跳，1跳可達第一層的M04、I03等衛(wèi)星，2跳可達第二層的M06、M02等衛(wèi)星，最大跳轉3次就能到達該星座的所有衛(wèi)星。以圖4中I03節(jié)點構成的子樹為例，如果地面站對該子樹的所有節(jié)點依次進行數據上注更新，需要進行地面站-I03、地面站-I03-M05、地面站-I03-M15、地面站-I03-M18共4次上注，由于地面站與I03在一組時隙中只有第二個時隙相鏈接，則在更新M05星、M15星和M18星需要分別在三組時隙中進行，導致更新時間過長。

圖4 生成的動態(tài)鏈路樹圖

3.2 仿真結果比對分析

由于每個超幀內星間可見性及路由表都會發(fā)生變化，分別按照逐星更新的上行數據注入方法和動態(tài)鏈路樹路由方法，對“北斗”星座星間鏈路全天24 h的24個超幀進行結果比對。

比較鏈路占用總時隙數量如圖5所示，逐星更新路由方法平均上注占用時隙數量為312個時隙，動態(tài)鏈路樹路由方法平均上注占用時隙數量為215個時隙，占用整個星座的時隙數量降低了31%。鏈路占用總時隙數表征占用整個星間鏈路容量資源的大小，動態(tài)鏈路樹路由算法能顯著降低整個星座數據上注更新過程的資源占用。

圖5 鏈路占用總時隙數量比對

在數據上注過程中更為重要的是上注總時長，圖6對兩種方法的鏈路最后更新時隙進行了對比。逐星更新路由方法平均鏈路最后更新時隙為105，動態(tài)鏈路樹路由方法平均鏈路最后更新時隙為27，僅為逐星更新路由方法的25.7%，也就是相同的數據上注更新過程，動態(tài)鏈路樹路由方法完成的時間為逐星更新路由方法的1/4，較大幅度地提高了完成數據上注任務速度，縮短了數據上注時間。

圖6 鏈路最后更新時隙比對

4 結束語

本文針對目前“北斗”導航系統星間鏈路星座維護中頻繁進行的更新時隙表、路由表等數據上注操作，提出了一種動態(tài)鏈路樹路由算法，在星座各星上注數據一致的情況下顯著降低了整個星座數據上注更新過程的資源占用，并較大幅度地提高了完成數據上注任務速度，縮短了數據上注時間。但算法未考慮設備狀態(tài)切換時間因素的影響，將該因素納入算法模型是下一步改進和完善的重點。