序列式低軌星座全連通網絡拓撲結構設計方法

肖瑤，郭帥，*，楊震，羅亞中

1.國防科技大學 空天科學學院，長沙 410073

2.空天任務智能規劃與仿真湖南省重點實驗室，長沙 410073

低軌（Low Earth Orbit，LEO）衛星星座具有信號傳輸里程短、信號衰減小、傳輸時延短等優點，同時，能夠覆蓋地面基站無法覆蓋的地區，為全球用戶提供全方位多維度的服務［1］。星間鏈路是指衛星之間用于信息傳輸的鏈路，星間鏈路的部署策略，即星座網絡拓撲結構的設計結果決定了通信網絡連通性、衛星通信終端利用率、端到端時延和鏈路穩定性，以及星座的連通性和通信鏈路的抗毀傷性等性能［2］，因此衛星網絡拓撲結構的設計對提升星座性能尤為重要。

根據拓撲結構中包含的星間鏈路是否存在鏈路切換，可以將其分為靜態拓撲結構和動態拓撲結構。針對星座靜態拓撲結構設計問題，Suzuki 和Yasuda［3］提出了“8 字形”的改進曼哈頓網絡。黃錚［4］針對相鄰相連和交叉相連2 種骨干網絡進行分析，發現交叉相連的骨干網絡結構在進行信息傳輸時跳數更少。王占偉［5］基于Walker星座，提出使用扭曲因子表征拓撲結構，并設計了2D-Torus、Hamilton 以及Mobius 拓撲結構，同時，采用0-1 整數規劃方法設計了鏈路總距離最小的Mobius 結構。Chaudhry 和Yanikomeroglu［6-7］對Starlink 的靜態網絡拓撲結構進行了分析，并討論了可建鏈距離對星座中每顆衛星的可建鏈衛星數量的影響。在靜態拓撲結構基礎上，動態星間鏈路的加入能夠有效提高衛星間信息傳輸效率和衛星網絡性能。Zhu 等［8］在Starlink星座靜態拓撲結構基礎上，提出了動態鏈路對于增強衛星網絡的抗毀傷性和降低傳輸時延方面的優越性。郭麗榮［2］在Starlink 衛星星座的基礎上，設計了靜態和動態2 種拓撲結構，進一步說明了動態鏈路在減少路徑跳數等方面的優勢。Liu等［9］針對大規模LEO 星座的動態鏈路設計問題，提出DP-ALNS（Data-driven Parallel Adaptive Large Neighborhood Search）算法。目前，針對星座動態拓撲結構設計的研究主要基于全球導航衛星系統（Global Navigation Satellite System，GNSS）星座展開，此類問題在考慮傳輸時延的基礎上還需要考慮星間測距的要求［10-11］。另外，Yan 等［12］針對ISL 和GSL（Ground-Satellite Link）的交互問題，提出了在考慮GSL 時隙情況下的基于最大權重匹配的啟發式算法，并對GNSS 星座的拓撲結構進行了設計。

上述大部分研究僅針對于單一構型Walker星座展開，然而，單一構型星座往往無法很好地滿足任務需求，故常采用由多個Walker 星座組成的混合星座。目前應用較多的混合星座主要由LEO、MEO（Medium Earth Orbit）、IGSO（Inclined Geosynchronous Satellite Orbit）、GEO（Geosynchr-onous Earth Orbit）中2 類或3 類高度層子星座組成，例如中國的北斗導航衛星星座。同時，由于低軌衛星部署成本低、通信時延短等優勢，以Starlink 為主的低軌巨型混合星座成為了當前的熱點之一，國內已有部分學者開展了巨型低軌混合星座的設計、部署等研究工作［13-15］。

針對混合構型星座拓撲結構的研究，大部分面向上述多高度層混合星座展開［5，16-18］，面向LEO 混合星座拓撲結構設計的研究很少。由于LEO 衛星軌道高度較低，受大氣阻力和地球扁率等攝動因素影響較大，衛星間的相對位置無法長期保持與所設計的星座構型一致，衛星相對運動規律更為復雜，增加了衛星星座整體或局部星群的拓撲結構設計難度。所以，面向多高度層混合星座的拓撲結構設計方法不再適用于LEO 低軌混合星座。已有的LEO 混合星座拓撲結構設計方法［15］采用了貪婪式建鏈規則，以人為給定的衛星編號為選定建立星間鏈路的先后順序，按照該建鏈順序逐個選擇與之最大相對距離最小的衛星直接建鏈。然而，該方法限制了衛星的建鏈順序以及每顆衛星建鏈對象的選擇規則，無法保證排序靠后的每顆衛星都有足夠的可建鏈衛星。另外，該方法在拓撲結構設計階段沒有將連通性納入考慮范圍，無法確保星座全連通任務需求。

在此背景下，本文提出序列式拓撲結構設計方法，將拓撲結構設計問題轉換為全連接序列規劃問題，通過將全連通約束化解到設計變量中，壓縮解空間，以快速搜索得到自然滿足連通性需求的較優解。該方法不受衛星星座或局部衛星星群構型的限制，能夠適用于任意構型星座或空間幾何關系的衛星星群。同時，本文提出的序列式拓撲結構設計方法可為低軌巨型星座實時動態鏈路設計提供參考。

1 網絡拓撲結構設計模型

1.1 設計變量

為了描述星座拓撲結構，常使用二分圖等抽象圖方法替代傳統純圖形化方法［19-20］。在此基礎上，基于鄰接矩陣的拓撲結構描述方法已得到廣泛的應用。將衛星和星間鏈路抽象成點集以及點對的連線，可以得到表征星座拓撲結構的圖G［21］。對于任意的圖G，其對應了一個鄰接矩陣A（G）=［aij］，可以得到星座拓撲結構對應的鄰接矩陣為

式中：N為衛星總數量；aij表示第i顆衛星與第j顆衛星間的星間鏈路數量，i，j=1，2，…，N。由于衛星不會與其自身建立星間鏈路，故鄰接矩陣A的對角線元素均為0。同時，同一對衛星之間僅建立一條星間鏈路，故A中的元素均為0 或1，即

因此，星座拓撲結構設計問題的設計變量為鄰接矩陣A中的元素取值，即

1.2 約束條件

1）衛星可視約束

在實際工程中，為了便于對航天器進行預報和控制，常采用偏心率為0 的圓軌進行LEO 衛星的設計。假設衛星SA、SB在圓軌道上運行，兩者星間鏈路如圖1 所示。圖中：RA、RB為衛星的軌道半徑；RE為地球半徑；h為星間鏈路到地面的距離；θ為2 顆衛星所對應的地心角。2 顆衛星之間星間鏈路長度，即衛星間的距離dAB為

圖1 星間鏈路示意圖Fig.1 Schematic diagram of inter-satellite link

為了避免地球大氣中的粒子和氣體對于信號的散射和吸收作用，要求星間鏈路高于地表一定距離，即h＞H。星間鏈路距地表的高度h的計算公式為

由式（4）和式（5）可以得到使用星間距離表示的星間建鏈約束為

表示2 顆星之間滿足建鏈可視條件的最大距離。

2）通信載荷對準約束

當前，激光通信鏈路視軸轉動角度范圍主要由伺服結構決定，現有的激光通信終端伺服結構已經能夠實現較大范圍的立體空間掃描和指向［22］，故本文取方位角、俯仰角大小約束分別為±180°和±90°。但是，為了保持2 顆衛星之間鏈路的連接狀態，要求衛星間的方位角、俯仰角變化率均在給定的衛星天線掃描角速度內；同時考慮星上通信設備的各項性能，要求衛星的相對距離變化率也需要在給定范圍內［23］。故描述考慮通信載荷的掃描對準約束為

3）鄰接矩陣對稱性約束

在工程應用中，星間鏈路均為雙向鏈路，根據鄰接矩陣的定義，則A為對稱矩陣，即

4）鏈路數量約束

由于衛星所搭載的通信終端的數量有限，每顆衛星建立的鏈路數量有限。同時，為了能夠獲得更好的連通性及更強的魯棒性，需要盡量多的利用衛星的載荷終端［24］，故本文要求每顆衛星建立的鏈路數量與所搭載的通信載荷終端數量相等，即

式中：li為第i顆衛星建立的鏈路數量；lISL為衛星搭載的通信終端數量，即單星建鏈數量。

1.3 目標函數

將星間建鏈約束融入目標函數中作為鏈路評價指標，能夠有導向地搜索可行解，提升拓撲結構設計效率。首先，根據不同建鏈約束，建立兩類星間鏈路性能評價指標。

1）僅考慮衛星可視條件

在不考慮星間鏈路切換的情況下，衛星間的相對距離越小，衛星間信息傳輸的距離越短，信號衰減越小，信息傳輸時間越少，星間鏈路品質更好［8，15］。本文針對衛星可視約束，以衛星相對距離作為鏈路評價依據，建立標準化評價指標為

式中：dij為第i顆和第j顆衛星的距離，考慮靜態鏈路時，其表示該對衛星在整個生命周期內的最大距離。衛星間距離逐漸增大，評價指標取值及其變化率逐漸減小，即星間最大距離越小，評價指標的敏感度更高，在進行拓撲結構設計時，更有利于選擇距離更加接近的衛星進行建鏈。

2）考慮通信載荷約束

衛星間角度變化率和相對距離變化率越小，衛星間鏈路越穩定，即星間鏈路品質越好。與式（11）類似，建立不同約束對應的標準化評價指標為

式（12）～式（14）分別對應了方位角變化率約束、俯仰角變化率約束以及距離變化率約束對應的評價指標，以此設計考慮衛星通信載荷掃描對準約束的評價指標為

然后，根據式（11）、式（15），建立星座鏈路評價指標矩陣為

將星座鏈路評價指標矩陣V中各元素與鄰接矩陣A各元素分別相乘并求和，得到使用星座拓撲結構設計評價指標描述的目標函數J為

式中：vISL為星座中星間鏈路評價指標的和；nISL為星座星間鏈路的數量。當J的值越大，表示拓撲結構中星間鏈路的平均最大距離越小，星間鏈路更加穩定，更利于信息傳輸。

2 序列式拓撲結構優化設計方法

網絡拓撲結構的優化設計一般基于0-1 整數規劃方法［5］，直接求解拓撲結構對應的鄰接矩陣或每顆衛星的建鏈對象。針對LEO 混合星座的解空間巨大、拓撲結構設計約束復雜，以及巨型星座局部衛星群分布不規則的問題，本文在保證對于不同構型適用性的前提下，針對星座全連通的任務需求，提出序列式拓撲結構優化設計方法。

2.1 序列式拓撲結構設計方法

根據星座全連通的定義，即星座中的任意的2 顆衛星均能夠找到一條路徑來進行信息傳輸，故一個全連通的星座拓撲結構中一定存在一條能夠連接起所有衛星的序列。首先，定義全連接序列為長度等于N+1，除首尾元素外，其他元素均不重復的序列。基于此，本文提出通過設計全連接序列來設計拓撲結構的思路。

假設某衛星星座中包含N顆衛星，且衛星的編號分別為{1，2，…，N}。若存在一條全連接序列，記為

式中：pi為序列中第i顆衛星的編號，i=1，2，…，N，且pN=p0。則可以得到該星座對應的鄰接矩陣A中每個元素取值為

例如，假設存在一個8 節點的網絡，其中一條全連接序列為{5，7，3，6，2，8，1，4，5}，則其對應的鄰接矩陣A為

可以發現，一條全連接序列能夠對每顆衛星建立2 條星間鏈路，故此方法僅針對通信終端數量為2 的倍數的情況。基于上述轉換方法，將星座拓撲結構設計問題轉換為序列規劃問題，通過直接求解所有衛星的全連接序列，獲得星座網絡拓撲結構的設計結果，設計步驟如算法1 所示。

由于不是任意2 顆衛星之間都能夠建立星間通信鏈路，很難找到一條滿足建鏈約束的全連接序列。本文利用智能優化算法，在上述序列式拓撲結構設計思路的基礎上，生成全連接序列，完成拓撲結構的優化設計。

2.2 全連接序列優化生成方法

根據2.1 節的設計思路，可以將拓撲結構設計問題轉換為路徑受限的TSP（Traveling Salesman Problem）問題。與傳統TSP 問題不同，不是任意2 顆衛星之間都能夠建立星間鏈路，導致每顆衛星選擇下一序列節點時受到限制，故引入罰函數，對無法建鏈的衛星間設置懲罰值。得到基于星座鏈路評價指標矩陣定義衛星間等效路徑長度為

式中：ηij表示衛星i與衛星j之間鏈路評價指標，定義為

如式（20）所示，當鏈路評價指標為0 時，令其對應的節點之間的啟發函數為一極小值，同時，對應的節點間等效路徑長度也極大，從而使得此序列被選擇的概率極小。

傳統的搜索算法需要對所有可能的序列進行遍歷，無法快速得到可行解，本文采用蟻群算法［25］求解對上述全連接序列。為了能夠在兼顧全局最優的基礎上獲得更好的收斂速度，在經典蟻群算法（Ant Colony Optimization，ACO）的輪盤賭選擇策略基礎上，加入貪婪式衛星選擇策略。選擇與衛星i相連接的下一顆衛星時，得到衛星j與其建立星間鏈路的概率為

式中：τij表示衛星i與衛星j之間的信息素濃度；α和β分別表示信息素濃度和啟發函數在選擇概率中的貢獻度。貪婪式衛星選擇策略指選擇目前概率最大的衛星作為序列的下一節點，即

式中：li為序列中第i顆衛星的下一個衛星編號。在每次選擇建鏈衛星時，算法采用該策略的概率為q0。

同時，在全局信息素更新策略基礎上加入局部信息素更新策略。每完成一個衛星序列節點選擇后，算法就立即依據式（23）更新一次信息素。

綜上，可以得到拓撲結構優化設計流程如圖2所示，主要流程如下：

圖2 序列式拓撲結構優化設計流程Fig.2 Process of sequence-based topology design and optimization

步驟1根據星座各衛星軌道信息，計算各衛星之間可建鏈評價指標，得到可建鏈評價指標矩陣，初始化已生成的全連接序列數量p。

步驟2使用混合選擇策略和信息素更新策略的蟻群算法求解最優全連接序列，更新已生成全連接序列數量p=p+1。

步驟3根據2.1 節方法，將全連接序列轉換為對應的鄰接矩陣，將已建鏈衛星間的評價指標賦值為0，更新鏈路評價指標矩陣。

步驟4判斷已生成全連接序列數量是否＜lISL2，若是，則返回步驟2，反之，則進入步驟5。

步驟5輸出鄰接矩陣，完成星座拓撲結構設計。

3 拓撲結構性能評價方法

為了實現LEO 星座的快速信息傳輸以及滿足鏈路的冗余性要求，在鏈路評價指標的基礎上，本文進一步對星座拓撲結構的連通性和抗毀傷性進行評估。本節給出星座拓撲結構連通性和抗毀傷性的評價模型，用于對所設計的拓撲結構進行性能分析。

3.1 連通性

對于導航增強、對地觀測等任務的較大規模LEO 星座而言，衛星間進行信息傳輸的快慢是其能否高效完成任務的關鍵之一。對于LEO 衛星間的通信鏈路，每顆衛星與其所有可建鏈衛星之間的距離相差不大。采用激光通信終端作為衛星通信有效載荷時，由于每2 顆衛星間距離不同導致的通信時延的差異較小，故低軌衛星信息傳輸時延主要受路徑跳數的影響［26］，即信息傳輸時所需要經過的衛星數量。同時，星間信息的傳輸跳數在一定程度上也會影響信息傳輸的正確率，故本文以星座中任意2 顆星進行通信的最大跳數，即任意2 顆星進行信息傳輸的過程中，經過的星間鏈路的數量作為衡量星座拓撲結構的連通性的標準。根據鄰接矩陣的性質［16］，衛星網絡中長度不超過k途徑的數量的矩陣為

根據式（24），定義kmin為使Rk中的任意元素不為0 的k的最小值。故kmin為使得星座網絡全連通的最小途徑長度，即星座中信息傳輸所經過的最大跳數。kmin的值越小，星座拓撲結構連通性更好。

在實際應用過程中，為了保證任意位置的衛星或用戶能夠將信息傳遞給全球或星座內任意目標，要求星座中任意2 顆衛星均能通過星間鏈路進行信息傳輸，即滿足全連通的性能要求。若當k=N-1 時，式（24）中仍存在為0 的元素，則該拓撲結構無法全連通。

3.2 抗毀傷性

抗毀傷性用于評估在個別衛星節點或星間鏈路損壞后，星座網絡結構維持其功能的能力。針對衛星網絡而言，基于自然連通度的抗毀傷性評價方法在準確度、精度以及計算復雜度上都具有較好的效果［27-28］。建立基于自然連通度的網絡抗毀傷性評價指標Qinv為

式中：N表示網絡中節點的個數；λi為鄰接矩陣A的特征值，其反映了網絡中長度不超過N的閉途徑的數量。

4 仿真分析

4.1 混合星座拓撲結構設計

1）參數設置

為了驗證本文所提出的方法在衛星靜態鏈路數量有限情況下的適用性，取單星建鏈數量lISL取2，該數量為理論上滿足全連通的最小建鏈數量。取15 個Walker 星座組成混合星座，各子星座均設置為軌道高度7 125 km、軌道傾角55°的均勻星座，且星座參數取值為15/15/1（三元參數N/P/F分別描述Walker 星座衛星總數、軌道面數量以及相位因子）；每個子星座種子衛星升交點赤經以24°為間隔，在0°～360°范圍內均勻分布。用于全連接序列生成的蟻群算法參數取值如表1。

表1 面向混合構型星座的蟻群算法仿真參數Table 1 Simulation parameters of ACO for hybrid constellation

2）求解結果與分析

由于所給混合星座分布較分散，不同子星座間衛星運行規律較復雜，極易無法找到滿足建鏈條件的全連接序列。圖3 給出了全連接序列等效鏈路距離隨算法迭代次數的變化，當等效距離達到1010時，表示該序列中存在建鏈衛星間不滿足建鏈約束情況，與式（20）對應，在不影響算法正常運行的情況下，顯式表達了約束不滿足的情況，從而能夠快速判斷求解序列對建鏈約束的滿足情況。算法運行到1 006 代時，找到可行全連接序列的解，并在此后迭代中優化序列中星間鏈路品質。另外，在后續的搜索中，每代最優解受當前最優解的影響很小，搜索解空間不受當前最優個體的影響，仍具有一定的全局搜索能力。

圖3 序列等效距離迭代示意圖Fig.3 Equivalent distance of each sequence in each iteration

圖4 和圖5 分別展示了星座拓撲結構的設計結果和星間鏈路評價指標的取值分布。為了達到全連通的任務需求，序列式設計方法得到的拓撲結構中建立了更多的跨軌的星間鏈路，導致鏈路評價指標值在更小的取值上分布更多。

圖4 混合星座拓撲結構Fig.4 Topology construction of hybrid constellation

圖5 混合星座拓撲結構評價指標分布Fig.5 Evaluation distribution of topology construction for hybrid constellation

分析拓撲結構的性能，得到表2 結果。雖然，使用貪婪式建鏈策略所得到的星座拓撲結構更為規則，且評價指標相較于序列式設計方法更高，但其在單星僅建立2 條靜態星間鏈路的極端情況下，無法達到星座全連通的任務要求，其抗毀傷性指標值也相對更小；序列式設計方法雖然拓撲結構更為復雜，但即使在單星建鏈數量僅為2 的情況下，也能夠達到全連通要求。

表2 混合星座拓撲結構性能Table 2 Topology performance of hybrid constellation

4.2 局部衛星群拓撲結構設計

1）參數設置

目前，在設計動態拓撲結構時，大都基于有限狀態自動機（Finite State Automaton，FSA）的思想，將連續時間劃分為多個時隙，每個時隙內單獨進行設計［29］。為了說明所提出方法未來在LEO 混合星座動態鏈路建鏈中的應用潛力，本文以Starlink 星座［30］中的局部衛星星群為對象，基于不同時刻下星座局部星群空間分布，模擬大規模星群執行局部區域任務時不同時隙的衛星構型，并對其展開拓撲結構設計。

設定目標衛星星群為星下點處于表3 所給經緯度范圍內的所有衛星，衛星通信載荷天線掃描能力取值如表4所示，鏈路評價指標根據式（15）計算。設定衛星搭載的通信終端數量為4，取蟻群算法參數如表5 所示。

表3 衛星群星下點所處區域范圍Table 3 Longitude and latitude range of target region

表4 方位、俯仰以及距離變化率約束Table 4 Rate constraints of azimuth，elevation and range

表5 局部衛星群ACO 算法仿真參數Table 5 Simulation parameters of ACO for local satellite collection

2）求解結果與分析

圖6 分別對應了6 個位于表3 區域范圍的不同分布下衛星星群的拓撲結構設計結果，圖中，圓點表示衛星所處的位置，顏色深淺表示衛星所處地心距R，顏色越深，所處高度越低；橘紅色連線表示存在的星間鏈路。各拓撲結構性能分析結果如表6 所示。

表6 不同時刻下衛星星群拓撲結構評價指標Table 6 Topology performance of satellite collection at different time points

圖6 Starlink 局部衛星星群拓撲結構設計結果Fig.6 Topology solutions of Starlink local satellite collection

以圖6（a）為例，首先，由圖6（a）可以得到，衛星群經緯度分布不規則，無法定義常規的“前、后、左、右”建鏈對象；其次，分析衛星地心距分布，得到圖7 結果，可以發現，該時刻的目標衛星群所處軌道高度分布在6 700～7 000 km 的范圍內，衛星群空間高度分布不規則。在此情況下，該衛星群拓撲結構的連通性指標為5，遠小于衛星群內包含的衛星數量，表現出較強的連通性。圖6（b）～（f）同理。

圖7 衛星群在空間分布1 時的地心距Fig.7 Radius distribution of satellite collection at the first time point

可以發現，不同時刻下針對不同的衛星星群分布，本文方法都能夠充分利用衛星通信載荷，設計得到滿足鏈路約束的拓撲結構，不會由于衛星軌道高度、星群空間分布構型的特殊性而無法求解，進一步驗證了本文所提出的序列式拓撲結構設計方法針對各種復雜衛星分布的適應性。另外，根據表6 分析結果，在第6 個時刻時，處于區域范圍內的衛星數量為70 顆，遠大于其他時刻的衛星數量，但在該情況下的連通性指標，即最大信息傳輸跳數僅增加了1～3 跳。進一步說明通過本方法設計的拓撲結構在面向巨型星座局部衛星星群協同任務時，具有信息快速傳輸的優勢。

5 結論

1）本文所提出的序列式拓撲結構設計方法在鏈路數量受限情況下，能夠利用全連接序列特性，設計得到滿足全連通任務需求的拓撲結構，解決了現有設計方法無法確保設計結果滿足該需求的問題。同時，采用該方法設計的衛星拓撲結構在星座信息傳輸的最大跳數上展現了較強的優勢，可服務于星座或局部星群星間快速信息傳輸任務需求。

2）本文提出的序列式拓撲結構設計方法能夠適用于任意空間分布的衛星星座整體或局部星群，解決了現有大部分拓撲結構設計適用星座構型受限問題。

3）根據本文提出的序列式拓撲結構設計方法所建立的框架，在本文基礎上，進一步考慮不同時隙間的鏈路切換，可應用于大規模不規則低軌星座內局部衛星星群的實時動態通信鏈路設計。