基于演化圖的導航星座星間路由算法

王彥 劉波 虞萬榮 趙寶康

（國防科學技術大學計算機學院，長沙410073）

1 引言

近年來，全球衛星導航系統在國民經濟和國防軍事等領域的應用日益廣泛和深入，推動著其技術的不斷進步和功能的持續完善。美國的GPS率先實現了星間鏈路，并且計劃在GPS III中裝配指向性天線，并引入路由轉發機制，以提升星間鏈路數據通信性能［1］?？偨Y國外衛星導航系統的發展經驗，在星座內建立星間鏈路，并利用星間鏈路進行星間測距和數據通信，以實現星座的自主運行是一種發展趨勢［2］。本文針對導航星座星間數據通信的需求，對導航星座星間路由相關問題展開研究。

針對基于星間鏈路的衛星星座系統星間路由問題，國內外眾多學者已進行了大量的研究工作，但大多數工作都是針對用于承載地面用戶數據流量的衛星通信系統的星間路由問題，鮮有學者針對導航星座進行星間路由研究。文獻［3］提出了一種基于地面站集中式的導航星座星間路由算法，其假設條件是：星座系統的星間鏈路資源豐富，一顆衛星可在同一時刻與其他多顆衛星建立星間鏈路，確保星座網絡拓撲在任意時刻處于全連通狀態。但在星間鏈路資源受限的情況下，一顆導航衛星無法同時建立并維持多條星間鏈路，將持續進行星間鏈路切換并導致星座網絡拓撲處于非連通狀態，上述方法將難以有效地解決星間路由問題。

為降低導航星座星間數據通信對地面站的依賴，星上在線計算的路由算法是未來發展的必然趨勢。本文針對裝配指向性天線、具有確定性鏈路調度的衛星導航星座系統，充分分析了由衛星在軌飛行及星間鏈路調度切換所導致的星座動態變化的網絡拓撲結構，引入演化圖模型［4］，對星座動態變化的網絡拓撲結構進行建模，提出一種星間最早到達路徑的路由算法，再給定導航星座構型及星間鏈路調度方案，對算法進行模擬驗證。

2 導航星座動態網絡拓撲結構的演化圖建模

2.1 場景描述

圖1給出了6個連續時間間隔的導航星座網絡拓撲結構快照，每個時間間隔長度固定為Δt。為簡化描述，圖1中只給出了導航星座中的一部分導航衛星及這些導航衛星之間建有的星間鏈路。如圖1所示，將導航衛星分別記為A、B、C、D、E、F和G；以A與C之間的星間鏈路為例，將導航衛星間的星間鏈路記為ISL（A，C）。在每個時間間隔內，導航星座中的每顆衛星或選擇與另一顆特定的衛星建立一條全雙工的星間鏈路，或處于空閑狀態；但不能同時與多顆衛星建立星間鏈路，故在每個時間間隔內導航星座網絡拓撲都處于非連通狀態［5］。由于導航星座具有確定性的星間鏈路調度，星座中的每顆導航星都可獲得當前時間間隔內和后續一定時間間隔內整個導航星座網絡拓撲信息。

觀察圖1，在從0～6Δt的每個時間間隔內，導航星座的網絡拓撲結構都是固定不變的，但都處于非連通狀態；且在任意一個時間間隔內，A與G之間都未建立星間鏈路。由于在同一時刻，每顆衛星至多只能建立一條星間鏈路，故不可能在導航星座網絡拓撲結構不發生變化的一個時間間隔內找到一條從A至G的路徑。然而，可通過導航星座網絡拓撲結構隨著每個時間間隔的變化，在時域空間中找到從A至G的路徑。例如，在0～Δt內，從A出發到達C，在2Δt～3Δt內，再從C出發就可到達G。

圖1 不同時間間隔內導航星座網絡拓撲結構快照Fig.1 Snapshots taken at different time intervals of the network topology of navigation constellation

2.2 導航星座動態網絡拓撲結構的演化圖模型

給定圖G＝（V，E），及圖G的有序靜態子圖SG＝G1，G2，…，GL使得可定義EG＝ （G，SG）為演化圖［6］。令EEG＝∪Ei，定義M為演化圖EG中邊的數目，M＝｜EEG｜，令VEG＝∪Vi，定義N為演化圖EG中節點的數目，N＝｜VEG｜。對應至導航星座，Gi是對導航星座處在第i個時間間隔時的網絡拓撲結構的描述，M為星座在一段時間內所建立的星間鏈路的條數，N為星座在一段時間內處于運行狀態的導航衛星的顆數。圖2給出了圖1所對應的從0～6Δt，共6個時間間隔內的導航星座的動態網絡拓撲的演化圖模型。圖2中星間鏈路上標記的數字表示衛星間建立該星間鏈路時所處的時間間隔。

給定演化圖EG中的節點v∈VEG及邊e∈VEG。定義節點v的動態度為在演化圖EG其他節點中與節點v間存在邊調度的節點的個數，記為δv；定義邊e的動態度為演化圖EG對該邊的調度次數，記為δe；定義演化圖EG的最大節點動態度δV＝max｛δv，v∈VEG｝，最大邊動態度δE＝max｛δe，e∈EEG｝。如圖2有，δA＝4，表示A在0～6Δt內分別與其他4顆導航衛星建立了星間鏈路；δISL（B，F）＝2， 表示B與F之間在0～6Δt內建立了兩次星間鏈路；δV＝6，即表示在0～6Δt內，E分別與其他6顆導航衛星建立了星間鏈路；δE＝δISL（B，F）＝δISL（F，G）＝2，即表示在0～6Δt內，B與F之間及F與G之間分別建立了兩次星間鏈路。

給定演化圖EG，可定義如下函數：

1）函數ζ（e，r）→tld，有e∈EEG，r∈N＋及tld∈T，給出在演化圖EG中第r次調度e時所處時間間隔內，e的傳播時延tld。如圖2，在第2個時間間隔，B與F間第1次建立星間鏈路，假定此時B與F之間的星間距離為27 900km，則B與F間的星間鏈路時延為93ms，故有ζ［ISL（B，F），1］＝93ms；在第6個時間間隔，B與F間第2次建立星間鏈路，假定此時B與F之間的星間距離為28 500km，則B與F間的星間鏈路時延為95ms，故有ζ［ISL（B，F），2］＝95ms。在本文討論中，假設在同一個時間間隔內，星間鏈路時延保持不變。

2）函數S（e，r）→ ［tsi，tei］，有e∈EEG，r∈N＋及tsi，tei∈T，且tsi＜tei， 給出在演化圖EG中第r次調度e的時間間隔［tsi，tei］，其中tsi是時間間隔的起始時刻，而tei是時間間隔的終止時刻。如圖2，在第3個時間間隔，A與B間第1次建立星間鏈路，故有S［ISL（A，B），1］＝［2Δt，3Δt］。

3）函數f（e，t）→［tet，tld］，有e∈EEG及t，tet，tld∈T， 給出在演化圖EG中t時刻后e可進行傳輸的最早時刻tet，及此時e的傳播時延tld。若在t時刻后，演化圖EG中不存在對e的調度，則有tet＝tld＝∞。如圖2，在時刻2.5Δt后，C與G在第3個時間間隔［2Δt，3Δt］內建立了星間鏈路，則在時刻2.5Δt，C可向G進行數據傳輸，假定此時C與G間的星間距離為27 000km，則C與G間的星間鏈路時延為90ms，故有f［ISL（C，G），2.5Δt］＝（2.5Δt，90ms）； 而在時刻3Δt后，C與G之間沒有星間鏈路的建立，故有f［ISL（C，G），3Δt］＝（∞，∞）。

給定圖G中的路徑R＝e1，e2，…，ek，有e∈EEG，及Rσ＝σ1，σ2，…，σk，有σi∈T，σi表示ei的起始傳輸時刻。定義J＝（R，Rσ）為演化圖EG中的一條路徑 （當且僅當Rσ與R、ζ、S保持一致）。Rσ與R、ζ、S保持一致是指，對于任意的ei、σi，存在ri∈N＋，且1≤ri≤δE（ei），使得σi∈S（ei，ri）并且σi＋ζ（ei，ri）∈S（ei，ri）。 給定演化圖EG中的任意兩個節點u和v，時刻t，起始時刻為t的從u到v的路徑可表示為J（u→v，t）。

給定演化圖EG中的路徑J＝ （R，Rσ），R＝e1，e2，…，ek，Rσ＝σ1，σ2，…，σk，有如下定義：

1）路徑J的跳數為h（J），則有h（J）＝｜R｜＝k，即構成路徑的邊的數目。

2）路徑J的起始時刻為s（J），即路徑源節點發起路徑請求的時刻。

3）路徑J的到達時刻為a（J），則有a（J）＝σk＋tld［f（ek，σk）］，即路徑所調度的最后一條邊ek的起始傳輸時刻與此時邊ek的傳播時延之和。

4）路徑J的時間開銷為c（J），則有c（J）＝a（J）-s（J），即路徑到達時刻與路徑起始時刻之差。

給定演化圖EG中的任意兩個節點s和v，時刻t。起始時刻為t的從s到v的最早到達路徑定義為JE（s→v，t）∈ ｛J（s→v，t）｜min［c（J）］｝； 記JE（s→v，t）的到達節點v的時刻為a［（s，v），t］，則有a［（s，v），t］＝c［JE（s→v，t）］＋t。若在路徑JE（s→v，t）上，節點u是節點v的直接前驅節點， 則有a［（s，v），t］＝tet｛f［（u，v），a［（s，u），t］］｝＋tld｛f［（u，v），a［（s，u），t］］｝。

圖2 動態網絡拓撲的演化圖模型Fig.2 Evolving graph model ofdynamic network topology

2.3 數據結構表示

描述導航星座動態網絡拓撲結構的演化圖模型的數據結構如圖3所示。由于本文考慮的導航星座內建立的星間鏈路較少，因此采用鄰接鏈表表示導航星座動態網絡拓撲結構的演化圖模型可以取得較優的存儲開銷，該鄰接鏈表的存儲開銷為O（MδE＋NδV）［4］。

演化圖的鄰接鏈表表示法就是對演化圖中的每個節點，用一個單向鏈表列出從該節點發出的所有邊，鏈表中每個單元對應于一條邊，為記錄每條邊的相關信息，鏈表中的每個單元除列下一條邊的另一個端點外，還需包含相應的數據域以儲存這條邊的相關信息。例如，圖3中衛星節點u在一段時間內與δu顆衛星節點建立了星間鏈路，衛星節點u所對應的鄰接鏈表的長度即為δu；衛星節點u與相鄰衛星節點v1建立了δISL（u，v1）次星間鏈路，S［ISL（u，v1），1］和ζ［ISL（u，v1），1］記錄了衛星節點u與相鄰衛星節點v1第一次建立的星間鏈路的相關信息，其中S［ISL（u，v1），1］為星間鏈路的調度時間間隔，ζ［ISL（u，v1），1］為星間鏈路的鏈路時延。注意，圖3中相鄰衛星節點的概念是指兩顆衛星之間有建立星間鏈路，而不是指一顆衛星與另一顆衛星在軌道物理位置上的相鄰。

圖3 演化圖模型的數據結構Fig.3 Data structure for evolving graph

3 基于演化圖模型的星間路徑計算

由于導航星座在軌運動具有周期性和可預測性，再結合星間鏈路調度的確定性，星座中的每顆導航星都可獲得足夠導航星座網絡拓撲信息以在星上獨立地進行在線路由計算。算法的基本思想在于：適應導航星座網絡拓撲的急劇變化，并正確給出任意起始時刻的任意兩顆衛星之間的最早到達路徑。

3.1 最早到達路徑算法

Dijkstra最短路徑算法［6］中的最短路徑能保持所謂的前向路徑屬性，即最短路徑的任意前向路徑都是最短路徑。文獻［7］證明了在演化圖模型中有且僅有一條最早到達路徑能保持前向路徑屬性。在演化圖模型中計算路徑起始時刻為t的單源節點s到所有節點最早到達路徑算法的輸入、輸出及步驟具體如下：

變量：演化圖EG，節點s∈VEG，時刻t∈T。

輸出：數組tEAD［v］∈T，給出在時刻t后從節點s至每個節點v∈VEG的最早到達路徑的到達時刻；數組father［v］∈VEG，給出每個節點v≠s∈VEG在最早到達路徑上的直接前驅節點。

變量：最小優先隊列Q，按鍵值tEAD排序；集合C，記錄已完成最早達到路徑計算的節點。

步驟1 初始化tEAD［s］＝t，對所有v?VEG，令tEAD［s］＝∞；以s為首節點創建最小優先隊列Q；初始化集合C為空。

步驟2 若Q為空，轉至步驟5；否則，提取Q的首節點u出列。

步驟3 遍歷節點u的鄰接表，對每個不在C中的鄰居節點v，令 （tet，tld）＝f［（u，v），tEAD［u］］。 若tet＋tld≥tEAD［v］， 繼續步驟3；否則，令tEAD［v］＝tet＋tld，father［v］＝u， 查找節點v是否已插入至Q中。若在Q中，則節點v的鍵值已被更改，更新Q；否則，將節點v插入Q。繼續步驟3。

步驟4 將節點u插入C，轉至步驟2。

步驟5 算法結束，輸出結果。

3.2 算法證明與復雜度分析

要證明對演化圖EG運行最早到達路徑算法可給出t時刻后從節點s到所有節點u∈VEG的最早到達路徑，只需證明在算法終止時，對所有節點u∈VEG，有tEAD［u］＝a（（s，u），t）即可。由于算法運行過程中，演化圖EG中的任意節點u只被插入C一次。上述證明可轉化為，將節點u插入C后有tEAD［u］＝a（（s，u），t）。 算法初始時，有C＝｛s｝，及tEAD［s］＝t＝a（（s，s），t）。當算法運行至將某一節點v插入C的前一時刻，這時節點v被插入Q后已經從Q中出列，顯然此時已有路徑將節點s與節點v連接；假設路徑J是當前從節點s到節點v的最早到達路徑，則路徑J可將C中的節點s連接至C外的節點v；若此時節點w是路徑J上第一個不在C內的節點，并且在路徑J上節點u是節點w的直接前驅，則節點u已經被插入至C中，執行步驟3后應有tEAD［u］＝a（（s，u），t）；當節點u被插入C時，節點w已經被插入至Q中，并且節點w不可能是路徑J上節點v的后繼節點，此時算法已運行至將節點v插入C的前一時刻，故有v＝w；根據最早到達路徑 的 屬 性， 有a［（s，v），t］＝tet｛f［（u，v），a［（s，u），t］］｝＋tld｛f［（u，v），a［（s，u），t］］｝；算法下一步執行將節點v插入C的操作，執行后有tEAD［v］＝a［（s，v），t］。 算法終止時，顯然有C＝VEG。

最早到達路徑算法的運行時間主要取決于函數f（·）及最小優先隊列Q的具體實現。根據圖3給出的數據結構，采用二分搜索，可在O（lnδE）的時間內完成函數f（·）的計算。若采用二叉最小堆來實現最小優先隊列，則Q的插入、查找、提取和更新操作都需要O（lnN）的時間［6］。在算法運行過程中，對每個插入C中的節點u，步驟3對節點u的不在C中每個鄰居節點執行函數f（·）的計算及隊列Q的相關操作，耗時為O（lnδE＋lnN）。函數f（·）的計算及隊列Q的相關操作最多執行M次，故算法總計運行時間為O［M（lnδE＋lnN）］。

4 算法模擬與結果分析

4.1 相關模擬參數設置

導航星座選擇Walker-δ24／3／2星座構型，軌道高度為21 000km，軌道傾角為55°，星座回歸周期大約為15h，星座中所建立的星間鏈路的指向方位角限定在［-60°，60°］。

可將星座中的3個軌道面命名為軌道面1、2、3，用1L、2M、3N表示軌道面1、2、3中的第L、M、N顆衛星。星座中的每顆衛星可見的衛星有22顆，每個軌道面內相位差為180°的兩顆衛星由于地球的阻擋而相互不可見。例如，衛星11和衛星15，由于在同一軌道面內，并且相位角相差180°，為兩顆相互不可見的衛星。

由于受到星間鏈路指向方位角的限制，并不是所有可見衛星之間都可建立星間鏈路。在星間鏈路指向方位角限定在 ［-60°，60°］內的條件下，星座中的每顆衛星可與14～16顆衛星建立星間鏈路。導航星座內建立星間鏈路采用矩陣變換規劃方法［8］，并選定時間間隔為3s。

4.2 路徑的時間開銷與跳數

在星座回歸周期大約為15h的條件下，算法模擬從0h開始并每隔0.5h選擇一個路徑起始時刻，共選擇30個路徑起始時刻點，計算了星座內所有衛星間、同軌衛星間及異軌衛星間的最早到達路徑。圖4和圖5分別給出了最早到達路徑的時間開銷與轉發跳數的平均值。同軌衛星間最早到達路徑的時間開銷要小于異軌衛星間的；同時，同軌衛星間最早到達路徑的轉發跳數也要小于異軌衛星間的。所有衛星間最早到達路徑的平均時間開銷約為14s，平均轉發跳數約為2.5。

圖4 最早到達路徑的時間開銷Fig.4 Time cost of earliest journey

圖5 最早到達路徑的跳數Fig.5 Hops of earliest journey

4.3 路徑隨起始時刻的變化

為反應星間路徑隨路徑起始時刻的變化情況，算法模擬給出了在不同路徑起始時刻衛星11與衛星15之間的最早到達路徑。分析表1可知，在0.0～21.0s間的8個不同路徑起始時刻下，衛星11與衛星15之間的最早到達路徑在第6.0s、9.0s、12.0s和18.0s發生了切換。

表1 最早到達時刻路徑隨起始時刻的變化Tab.1 Changing of the earliest journey along with the starting time

5 結束語

本文主要研究了導航星座星間路由的相關問題。在導航星座星間鏈路資源受限，不能確保星座網絡拓撲處于全連通狀態的條件下，傳統的方法無法解決星座中任意兩顆衛星間的路由問題。導航星座星間鏈路調度的確定性使得導航衛星可準確地預測后續一段時間內星座網絡拓撲的動態變化情況；利用演化圖對導航星座網絡拓撲結構進行建模，基于演化圖的路由算法有效地解決了星座網絡拓撲非連通狀態條件下星座中任意兩顆衛星間的最早到達路由問題。

進一步工作可考慮結合導航衛星數據傳輸的流量模型，對星間鏈路建立方案和星間路由策略進行聯合優化，以提高星間鏈路資源的利用率，滿足導航衛星間各類型數據傳輸的需求。

［1］MAINE K P，ANDERSON P，BAYUK F.Communication architecture for GPS III［C］.IEEE Aerospace Conference，Big Sky，MT，March 6-13，2004.

［2］陳貴忠，帥平，曲廣吉.現代衛星導航系統技術特點與發展趨勢分析 ［J］.中國科學·技術科學，2009，39（4）：686-695.CHEN GUIZHONG，SHUAI PING，QU GUANGJI.Technical characteristics and development trend analysis of modern navigation satellite systems［J］.Scientia Sinica，Technologica，2009，39（4）：686-695.

［3］李振東，何善寶，劉崇華.一種適用于導航衛星星間鏈路的動態路由算法 ［C］.第2屆中國衛星導航學術年會，上海，2011.LI ZHENDONG，HE SHANBAO，LIU CHONGHUA.An active routing algorithm for navigation satellite constellation inter-satellite links［C］.The 2ndChina Satellite Navigation Conference，Shanghai，2011.

［4］FERREIRA A.Building a reference combinatorial model for MANETs ［J］.IEEE Network，2004，18（5）：24-29.

［5］范麗，張育林.Walker星座星間鏈路構建準則及優化設計研究 ［J］.飛行力學，2007，25（2）：93-96.FAN LI，ZHANG YULIN.Construction rules and design optimization of ISLs in Walker constellation［J］.Flight Dynamics，2007，25（2）：93-96.

［6］CORMEN T H，LEISERSON C E，RIVEST R L.Introduction to algorithms［M］.2nd ed.Cambridge：The MIT Press，2004.

［7］BUIXUAN B，FERREIRA A，JARRY A.Evolving graph and least cost journeys in dynamic networks［C］.Modeling and Optimization in Mobile，Ad Hoc and Wireless Networks，WiOpt′03，Sophia-Atipolis，2003.

［8］林金茂，楊俊，王躍科.基于矩陣變換的GNSS星間鏈路最優規劃算法 ［C］.第2屆中國衛星導航學術年會，上海，2011.LIN JINMAO，YANG JUN，WANG YUEKE.Optimizing algorithm for the scheduling of GNSS crosslink：a matrix transform approach ［C］.The 2ndChina Satellite Navigation Conference，Shanghai，2011.