基于啟發式遺傳算法的時分星間網絡拓撲優化設計

田 露，向才炳，孫劍偉，李駿平

(1.中國電子科技集團公司 第十五研究所，北京 100083; 2.中國人民解放軍32021部隊，北京 100094)

0 引言

在全球衛星導航系統中，引入星間鏈路可以進行星間測距和星間數據傳輸，通過星間測距可以提高導航衛星的定軌精度，利用星間數據傳輸可以提高導航星歷的更新頻度，也可以減少全球布站的數量，因此，依托星間鏈路技術在空間建立星間網絡是衛星導航系統必然的發展趨勢。目前，國際上全球導航系統(GNSS) 都已加入或正在進行星間鏈路的建設，GPS 通過星間鏈路已經實現星座自主導航，并且可以保證系統自主運行180天，系統精度不會降低，極大地提高了系統的抗毀能力，我國的北斗系統也加入了星間鏈路。

北斗三號衛星工程星間鏈路網絡是我國第一個在建的大型星地一體的空間信息網絡系統，采用相控陣時分體制，是天地一體、具有精密測量和數傳功能的動態無線網絡[1]。

區別于傳統的地面網絡，衛星與衛星之間、衛星與地面站之間的相對運動導致星間鏈路拓撲持續快速地變化，這對網絡的管理和使用提出了更高的要求。文獻[2]通過對具有異軌星間鏈路的星間的能見分析，探索了建立異軌道星間鏈路的可行性，偏向于軌道理論研究，沒有與工程實際相結合。文獻[3]在進行星間可見理論分析的基礎上，分別針對點波束和寬波束星間鏈路條件進行了鏈路分配研究，提出寬波束條件更適用于導航系統的星間建鏈。文獻[4]就一種基于TDMA的雙層混合型星座提出了一種時隙分配方案。文獻[5]將星間測距需求作為一個約束，以星間通信的延時性能為優化目標，提出一種基于首次改善(FI)的本地搜索算法和基于模擬退火(SA)的啟發式優化算法以對鏈路分配問題進行求解。文獻[6]利用演化圖對動態變化的星間網絡拓撲結構進行建模，從而解決星座網絡拓撲非連通狀態條件下星座中任意兩顆衛星間的最早到達路由問題。文獻[7]基于演化圖理論分別從最短路徑、最先路徑、最快路徑三種不同的路徑衡量指標進行了星間路由算法的研究。文獻[8]針對基于時分捷變建鏈全球衛星導航網絡特點及其數據傳輸要求，圍繞其數據業務過程中的路由問題開展了研究。但是這些研究都沒有兼顧導航系統測量和通信需求，對此，文獻[9]考慮測量與通信之間的依賴關系，構建雙層規劃模型分別設計上層啟發式星間測量鏈路貪婪搜索分配算法(RL-HGSA) 和下層基于全局“鄰域”搜索的星間路由優化算法(ROA-SGN)，但是其計算路由的等待時延時并沒有考慮發送時刻的不確定性。

本文提出一種將網絡的鏈路層與網絡層管理解耦合，提出一種基于啟發式遺傳算法的網絡拓撲優化設計方法，并采用分時最短時延的路由算法。最后，對星間網絡測量指標進行了統計分析，以星間數據傳輸和星星地數據下傳作為星間網絡數據傳輸的典型工況，對星間網絡拓撲路由規劃的結果進行了邏輯仿真，驗證了算法的實用性和優越性。

1 問題分析

本問題針對的是GEO/IGSO/MEO多層混合星座場景，共30顆衛星。其中MEO軌道高度為21 000 km，軌道傾角為55°，構型為24/3/1的Walker星座，即衛星總數為24、軌道面數為3，相鄰軌道面鄰近衛星之間的相位因子為1。GEO的緯度選取分別為E80°，E110°和E140°的3顆衛星，而IGSO則選擇傾角55°，緯度E116°，相位間隔120°的3顆衛星，并設置了2個時分體制地面站。

1.1 可見性約束

1.1.1 幾何可見性約束

幾何可見是最基本的建鏈前提條件，星間可見的影響因素包括衛星位置和天線掃描角。具體的判斷條件如圖1所示。

圖1 星間幾何可見

滿足地球無阻擋條件：

(1)

d≤dmax

(2)

其中：dmax為兩星之間的最大可視距離，Re為地球平均半徑，h為大氣層厚度。

滿足衛星掃描角約束：

(3)

(4)

θ1≤α1

(5)

θ2≤α2

(6)

其中：θ1,θ2分別為衛星2和衛星1在對方本體坐標系中的視線錐角，α1，α2分別為衛星1和衛星2的天線掃描角。

對于衛星與地面站，它們互相可見的條件是衛星位于地面站外切水平面之上，并滿足衛星波束掃描角度和地面設備波束截止角度的約束。

圖2 星地幾何可見

根據設置的軌道高度，地球整體都在衛星波束掃描角范圍之內，所以只需計算地面設備波束的截止角度約束，計算方式如下：

(7)

ψ≥ψmin

(8)

其中：ψmin為地面設備的截止角。

1.1.2 鏈路可達性約束

受星上天線載荷的條件限制，星間幾何可見的衛星可能由于天線的發射功率、天線增益、接收靈敏度、空間損耗等原因，星間信號可傳輸的極限距離小于實際幾何距離，導致建鏈不成功，因此，在進行規劃時，必須考慮鏈路可達性。

(9)

d≤dmax

(10)

1.2 體制約束

本文所設計的星間鏈路系統是基于TDMA體制下的，即在一個超幀內，將時間劃分成若干個等同的時間片，稱為時隙。在一個時隙內，衛星可以與在其可見范圍內的某一顆衛星建立鏈路進行測量與數據傳輸。在每個時隙內，網絡拓撲結構固定，整個衛星星座擁有許多條星間鏈路，這些鏈路相互獨立互不干擾，每一條連接著兩顆相互可見的衛星，它們可以通過鏈路進行測量數據傳輸，并且每顆衛星有且僅有一條鏈路。

以5個節點組成的10時隙時分網絡為例，圖3表示了時分體制的建鏈拓撲表達方式。圖中第一行表示，在1時隙，節點1與節點5建鏈，節點2與節點3建鏈，節點4輪空。

圖3 時分體制網絡拓撲

對于一個衛星來說，在一個超幀的不同時隙，可以通過與不同的衛星輪流進行建鏈，以滿足測量的多樣性。但是在星間數據傳輸過程中，若路由所選鏈路的時隙與數據的傳輸時機距離較遠，就可能因時隙等待造成較大的數據傳輸時延，在網絡規劃時應當給予充分考慮。

1.3 業務要求

導航星座星間鏈路承載著自主導航、精密定軌、時間統一等導航業務，這些業務對網絡的測量和數傳要求均不相同，本文取其在某工作模式下的指標要求如表1所示。

表1 導航星座指標要求

2 拓撲規劃

拓撲規劃是復雜星間網絡的鏈路層規劃，是網絡層路由規劃的基礎，本文采取將二者解耦和的方式進行規劃，在進行底層的拓撲規劃時充分將業務數據傳輸要求納入考慮范疇，在進行網絡層路由規劃時，以已有拓撲規劃為基礎進行路徑選擇，不再根據路由的結果返回修改拓撲規劃。

拓撲規劃的對象包括30個節點，且每分鐘20個時隙，拓撲規劃的鏈路≤600，并且存在很多約束條件，是一個多維多約束多解問題，無論是通過經驗設定規則進行規劃還是單純依靠的通用智能算法進行搜索，都很難求得其確定的最優解，因此本方案采用啟發式遺傳算法將二者相結合，先通過理論分析制定拓撲規劃的基本原則，給出一個能滿足大部分需求的拓撲框架，以此作為初值，利用遺傳算法對拓撲進行優化，來尋求其有限時間內能取得的局部最優解。

2.1 初步規劃

通過對星座的仿真分析，有如下結論：

1) 全星座下，每一個MEO衛星都有8個MEO衛星與之永久可見。

2) 每小時內MEO都有大于等于12 個非永久可見衛星(包括GEO、IGSO和MEO)在本小時內與之持續可見。

通過對星座數據傳輸任務過程和拓撲規劃過程的分析，有如下結論：

1) 境外-境內星間鏈路在星星地數據傳輸中起重要作用；

2) 境外-境內星間鏈路的時序排列與星星地數據傳輸時延息息相關；

3) 在進行拓撲表的規劃時，存在先后制約關系，在排入可見的衛星對時，必須先檢查拓撲表中該時隙下預排入的兩個衛星是否空閑，如果任何一方已經建鏈，則本次排列不成功。故先排入的衛星配對排列成功的概率要比后排入的衛星配對排列成功的概率要高。

充分利用以上先驗知識，本方案在進行初步規劃時，制定了如下原則：

1) 排入的衛星配對必須在本周期內持續可見；

2) 優先排列境內-境外星間鏈路；

3) 優先為可見境內星較少的境外衛星安排境內-境外星間鏈路；

4) 優先排列永久可見鏈路；

5) 境內-境外星間鏈路盡量等間隔均勻排入，避免出現局部長時間無境內-境外鏈路的情況；

6) 對各衛星盡量安排與不同衛星建立星間鏈路。

規劃步驟如下：

步驟1：進行可見性統計，本周期內持續可見方認為可見，并生成星間可見矩陣K；

(11)

K為0,1對稱矩陣，N為節點個數，為衛星節點和時分體制地面站節點之和，ki,j為0表示節點i與節點j不可見，ki,j為1表示節點i與節點j可見。

步驟2：統計境內星集合，境外星集合，境外星的可見境內星集合；

步驟3：生成境外衛星按照可見境內星個數從少到多排序序列；

步驟4：統計生成永久可見的衛星配對；

步驟5：優先排列可見境內星較少的MEO境外星，將MEO境外衛星中境外-境內的可見配對，以間隔2個時隙的規律排入時隙表，在此步驟中，優先排固定可見的衛星配對，其次排僅本周期內可見的衛星配對。為避免重復建鏈，如果排列成功，則在可見矩陣中將該配對置0；如果該境外星的可見境內星不足，則選取已經排過的境外-境內鏈路重復建鏈。

步驟6：加入高低鏈路，將高低鏈路中境內-境外的可見配對間隔2個時隙排入時隙表，優先原則同上，如果排列成功，則在可見矩陣中將該配對置0。

步驟7：進行檢查，如果境外-境內鏈路還有剩余沒有排入的，較境外-境外鏈路優先排入，如果排列成功，則在可見矩陣中將該配對置0。

步驟8：排入星地鏈路，優先選取持續2小時可見且有空閑時隙的境內衛星與地面站配對進行建鏈。再次選取本周期內可見且有空閑時隙的境內衛星與地面站配對進行建鏈。如果排列成功，則在可見矩陣中將該配對進行置0。

步驟9：排入境外-境外鏈路，優先排入固定可見的衛星配對，其次排僅本周期內可見的衛星配對。如果排列成功，則在可見矩陣中將該配對進行置0。

至此，初步規劃完成，基本構成間隔2個時隙有境內-境外鏈路的拓撲框架，同時還補充了境外-境外鏈路和星地鏈路。但是該拓撲框架中存在一些空閑時隙，并不能滿足各項指標要求。

2.2 遺傳算法優化

本方案采用經典遺傳算法對拓撲框架進行優化，遺傳算法是一種模擬生物進化規律適者生存優勝劣汰的遺傳機制來實現的一種通用的隨機搜索方法，過程介紹如下：

1)種群初始化：

本方案隨機生成50個個體P，構成初始群體，每一個個體是一個N×3的矩陣:

(12)

其中:TN×1為時隙，SN×1為衛星1，DN×1為衛星2。個體P的含義為在原有拓撲框架的基礎上，進行N次編輯修改，每次修改的含義為另ti時隙衛星si與衛星di進行建鏈；若si在ti時隙有建鏈對象，則進行拆鏈處理，同時將該時隙下si原建鏈對象的拓撲置為0；對衛星di的處理與之相同。

為了確保建鏈有效性，且不損失建鏈率，在隨機生成個體時，必須滿足2個條件，首先衛星si與衛星di在本周起內必須為可見配對，其次ti時隙衛星si與衛星di至少有一個為空閑狀態，同時滿足以上2個條件方為也可用個體基因，否則將重新隨機生成。

2)適應度評估：

本方案采用綜合指標評估準則，將鏈路空置率、星間不重復建鏈數均值，星間幾何精度因子均值，星星地數據傳輸時延納入綜合指標，對指標值進行了歸一化處理，在此，適應度值越小表示越優；

(13)

其中：第一項為全局鏈路空置率，E為全局鏈路空置率，意為空閑時隙占總拓撲表的百分比，ωe為鏈路空置率權值系數；

第二項為星間不重復建鏈數均值，Li為衛星i的星間不重復建鏈數，ωl為星間不重復建鏈數均值項的權值系數；

第三項為星間幾何精度因子均值項，Pdopi,j為衛星i在j時刻的星間幾何精度因子值，ωp為星間幾何精度因子均值項的權值系數；

第四項為星間幾何精度因子最大均值項，ωpmax為星間幾何精度因子最大均值項的權值系數；

第五項為星星地數據傳輸時延項，Di.k為衛星i在k時隙要將數據傳至地面站或者境內衛星的傳輸時延(本文僅統計時隙等待時延)，ωd為星星地數據傳輸時延項的權值系數。

以星星地數據下傳為例進行星星地數據傳輸時延統計，涉及一層下傳的路徑選擇規劃，本文在此采用簡化路由的方案進行選擇，直接建鏈的衛星配對之間必然存在路由，境外星從任意一個時隙出發，要將數據傳輸至地面，有3種方式：

(1)傳輸至境內星，由境內衛星通過星地連續體制鏈路傳至地面站；

(2)傳輸至境內星，由境內衛星通過星地時分體制鏈路傳至地面站；

(3)傳輸至境外星，由其他境外星將數據轉發至境內星，再傳輸至地面站；

由于本方案已經預設了間隔2個時隙的境內-境外鏈路，對于境外星來說，找尋當前時隙之后最近的境內星節點進行下傳即可，本文在此基礎上進行了增補設計，如果連續3個時隙以上沒有找到下傳時機，查找與之建鏈的境外星在該時隙之后的下一個時隙是否是下傳時機，如果是，則可以通過該境外-境外-境內鏈路進行下傳。

3)選擇操作:通過個體適應度值從當前種群中選擇一部分個體進行接下來的交叉，突變操作，本文采用錦標賽選擇法。每次從50個個體中隨機選取25個個體，從25個個體中選擇適應度函數值最小的個體，進入下一代，重復50次，選出50個個體作為下一代的父本。

4)交叉操作:從50個父本中隨機選擇2個父本P1和P2，以一定的交叉概率，進行交叉操作，在進行基因交叉時，從1～N中隨機選擇3個交叉點c1，c2，c3，將3個交叉點對應的3個編輯項進行交換，將此交叉操作重復50次，得到50個子代個體。

圖4 遺傳算法交叉操作示意

5)變異操作：以較低的變異概率，對50個子代個體進行隨機選擇，并隨機選擇變異點，按照初代個體的生成原則重新生成對所選中個體變異點處的3個編輯要素(時隙，衛星1，衛星2)，生成新的子代個體。

6) 計算每個子代個體的適應度評估值，并記錄群體極值、全局極值與對應個體。

7) 重復3)～6)步，直到完成所有迭代次數。

8) 將全局極值對應的個體作為編輯要素，對拓撲框架進行編輯修改，得到最終優化后的拓撲規劃結果。

3 路由規劃

在上述拓撲規劃的前提下進行網絡路由計算，與傳統網絡路由不同，時分體制下的路徑規劃與節點的傳輸起始時刻有關，以最短時延原則為例，從源節點A到目的節點B從不同的時隙出發有不同的最短時延路徑。此外，在進行路徑規劃時，還必須考慮星上的跳數限制。

本方案采用遍歷樹的方法，步驟如下：

1) 根據拓撲表生成以衛星i為根節點的3級節點樹結構；

2) 對節點樹進行遍歷，尋找衛星i到衛星j之間的所有可達路徑；

3) 計算不同出發時隙下，所有可達路徑的傳輸時延；

4) 選擇最短時延對應的路徑，時延相同的情況下，選擇跳數較小的路徑；

5) 將所有路徑中的第一跳路徑記錄在路由表中；

6) 重復1)～5)步，計算全網任意2個節點之間的端到端路由。

4 仿真驗證

為驗證算法的可用性，在VS2016工程中進行了編碼仿真，規劃時間為2020-03-15 00∶00∶00～2020-03-15 06∶00∶00，星座構成為3GEO+3IGSO+24MEO，Ka地面站2個，S地面站3個，拓撲表周期3 600 s。

4.1 測量性能驗證

遺傳算法種群大小50，編輯點規模100，迭代次數100。

種群迭代過程中群體適應度極值和適應度均值變化如圖5所示。

圖5 群體適應度極值/均值變化圖

可以看出，在種群迭代過程中群體的適應度極值在不斷下降，均值下降7%，極值下降4%，有明顯的優化效果。

最終的拓撲規劃的適應度評估結果如表2～4所示。

表2 鏈路空置率

表3 星間不重復建鏈數均值

表4 星間幾何精度因子均值

可以看出，該優化算法對拓撲表鏈路空置率、星間幾何精度因子均有一定的優化效果，空置率提升約3.9%，星間幾何精度因子提升約30%，星星地數據下傳最大時延保持不變，星間不重復建鏈數指標略有下降，優化后拓撲表的星間不重復建鏈數，星間幾何精度因子均滿足測量各項指標要求。

4.2 數傳性能驗證

軟件對路由規劃結果進行了邏輯仿真驗證，按照路由表進行數據傳輸，驗證任意兩個節點之間不同的出發時隙下，數據傳輸是否可達，數據傳輸的跳數和數據傳輸的時延。統計結果如下：

1) 任意兩個節點之間數據均可達；

2) 端到端跳數在5跳以內，且各跳數比例如表5所示。

表5 端到端跳數比例

圖6 端到端跳數分布

端到端跳數在4跳以內的占比達到98.02%。

3)端到端時延在60 s內，且比例如表6所示。

端到端數據傳輸時延在30s之內的占比達到97.72%。

4)星星地數據下傳時延

按照本文2.2節中描述的星星地數據下傳時機選取方案，對拓撲表進行了邏輯傳輸仿真，統計結果如表7所示。

表6 端到端時延比例

圖7 端到端時延分布

表7 星星地數據下傳傳輸時延 時隙

從表中可以看出：星星地數據下傳傳輸最大時延保持3個時隙不變，平均時延有所減少，有一定的優化效果。

仿真結果表明，采用本文提出的啟發式遺傳算法對拓撲規劃進行優化，并且采用最短時延原則的路由計算方法，其星間數據傳輸、星星地數據下傳過程均滿足業務數據的傳輸跳數與傳輸時延要求。

5 結束語

本文針對時分體制導航衛星星座的測量與數據傳輸要求，分析了網絡規劃的約束條件和業務要求，提出一種基于啟發式遺傳算法的網絡拓撲優化設計方法，首先通過仿真分析制定了規劃的基本原則，給出一個能滿足大部分需求的拓撲框架，再以此作為初值，利用遺傳算法對拓撲進行了優化，在此基礎上采用了分時最短時延的路由算法，并進行了仿真驗證，結果表明，拓撲路由規劃結果能滿足導航星座的常規業務。本文能為解決導航星座星間網絡的復雜運行管理提供一種解決問題的思路，仿真驗證過程未能將星上真實的處理過程納入考慮，與實際工程尚有一定的偏差。