基于改進遺傳算法的導航衛星星間鏈路網絡動態拓撲優化技術

韓凱,董日昌,邵豐偉,龔文斌1,,*,常家超

1. 中國科學院大學,北京 100049 2. 中國科學院 微小衛星創新研究院,上海 201210

衛星導航系統作為重要的國家戰略基礎設施,提高其可靠性和系統性能具有重要意義。星間鏈路(Inter-Satellite Links, ISLs)作為全球導航衛星系統(Global Navigation Satellite Systems, GNSS)的重要組成部分,為監控站分布受限情況下的星座定軌提供了一種有效方法。星間鏈路的作用主要包括星間測量和星間通信。

當前,衛星導航系統的星間鏈路主要包括微波鏈路和激光鏈路。相較激光鏈路,微波鏈路的發展與應用更早。美國的GPS率先實現了UHF (Ultra High Frequency)星間鏈路,并逐步向更高頻段的星間鏈路發展。其中,射頻窄波束天線與寬波束天線相比具有指向靈活、抗干擾能力強、測距精度高等優勢。近年來,高速率、高容量、高精度的空間激光通信開始應用于星間鏈路。歐洲航天局(European Space Agency, ESA)主導的Sentinel-1A環境監測衛星與Alphasat通信衛星成功開展了激光星間鏈路實驗。但由于其復雜的設計,激光鏈路在全球導航衛星系統中的應用需要進一步驗證。本文主要針對Ka射頻波段窄波束星間鏈路開展研究。由于衛星平臺和星間鏈路硬件數量的約束,衛星所裝配的星間鏈路天線的數量遠少于該衛星當前的可見衛星數量。當衛星只裝配有一個天線時,衛星網絡的連通性是不連續的,只有 ISL在不同的時隙進行切換才能實現衛星網絡之間的互相連通。因此,導航衛星網絡是典型的延遲/中斷容忍網絡(Delay/Disruption Tolerant Networks, DTN)。DTN的動態變化特性使得導航衛星網絡需要在不同的時間切換星間鏈路,而星間測距作為衛星導航系統的重要功能之一,星間鏈路的數量和分布影響著導航定位的精度。因此,優化星間鏈路的動態拓撲網絡是實現高精度導航定位中至關重要的問題。

針對星間鏈路拓撲優化問題,國內外學者已廣泛開展了相關研究。文獻[7-9]采用“永久鏈路+非永久鏈路”的思想實現衛星導航系統的鏈路分配。其中,文獻[7]提出了一種多層鏈路拓撲及混合路由設計方案,按照持續可見鏈路為主和非持續可見鏈路為輔的原則,采用基于代價函數的非持續鏈路選擇方法實現了星間鏈路拓撲方案的生成。文獻[8]針對非永久鏈路提出了基于幾何精度因子(Geometric Dilution of Precision, GDOP)貢獻值的設計方法,實現了任意MEO (Medium Earth Orbit)定軌精度的平均空間位置精度因子(Position Dilution of Precision, PDOP) 小于2.2的技術指標。文獻[9]以可見衛星距離和俯仰角作為約束原則為非永久鏈路進行分配。

文獻[10-14]以通信性能作為優化目標,對星間鏈路分配做出優化。其中,文獻[10]提出以通信時延作為優化目標、以星間測距最優性能和衛星間關系為約束條件的優化問題,從而對鏈路拓撲結構進行優化。文獻[11]基于最小生成樹理論提出一種混合導航星座的鏈路分配算法,將GEO衛星為核心傳輸節點,首先分配通信成本較低的星間鏈路,然后通過迭代為所有可見衛星至少分配一次。通過仿真分析,降低了全網平均通信時延。文獻[12]將星間測距需求作為一個約束,以星間通信的時延性能為優化目標,利用基于首次改善的本地搜索算法和基于模擬退火的啟發式優化算法對鏈路分配問題進行求解,并提出了一種基于分支交換策略的新鏈路分配生成方法。文獻[13]提出了一種基于目標評價函數進行負載均衡的網絡拓撲優化方法,并以網絡時延和接入能力為指標進行驗證。文獻[14]提出了有限狀態自動機(Finite State Automation, FSA)的思想,以衛星的負載均衡為優化目標,通過兩步啟發式算法解決了不確定多項式(Non-deterministic Polynomial, NP)完全混合整數優化問題,并使用模擬退火算法迭代計算。然而,上述研究在鏈路規劃問題中只考慮了通信指標,并未考慮衛星導航系統的測距定位需求。

文獻[15-18]在鏈路拓撲優化中除了考慮通信指標的要求之外,同時也將測距性能加入優化模型中。文獻[15]中以PDOP和傳輸時延分別為測距性能和通信度量,使用Blossom算法來獲得每個時隙中的鏈路最大匹配,并使用非支配排序遺傳算法II生成與優化整個時隙的衛星序列。文獻[16]以網絡時延和PDOP作為通信性能和高精度測量的量化指標,提出了一種基于多目標模擬退火算法的改進算法求解,并在某衛星或某條激光鏈路失效時進行動態優化。此外設計了一種避免沖突的鏈路交叉算法,改進了多源最小時延路由算法。文獻[17]采用雙層規劃求解兼顧測量與通信的星間鏈路設計,其中上層采用啟發式星間測量鏈路貪婪搜索分配算法對星間測量進行優化,而下層采用基于全局“鄰域”搜索的星間路由優化算法對星間通信進行優化。文獻[18]提出了基于遺傳算法的雙環星間鏈路分配優化方法,通過設定通信和測量性能的權重,將星間鏈路分配問題描述為單目標優化問題。在上述研究中,鏈路規劃目標函數不僅包括了通信指標,還對測距性能做出了要求,所以星間鏈路拓撲規劃的結果表現為測距性能與通信性能的均衡,以犧牲彼此的部分性能指標作為代價來實現全局優化的均衡。

隨著星間鏈路技術的發展,衛星導航精密定軌的研究逐步成為熱點。目前,武漢大學和中國科學院上海天文臺開展了相關的定軌實驗,并對精度衰減因子(Dilution of Precision, DOP)的結果進行了分析。結果表明,基于星間鏈路測量的定軌結果可以通過改變觀測幾何構型和增加星間測量次數進行改善。當前在星間鏈路拓撲規劃的研究中通常使用PDOP作為評估星間鏈路測距性能的指標。其中,文獻[12,15,16]分別采用本地搜素算法+模擬退火算法、遺傳算法和模擬退火算法進行求解。然而,上述的啟發式算法都包含新鏈路分配的產生環節。當衛星所搭載的星間鏈路天線數量受限時,隨機交叉產生的新鏈路必須滿足天線數量受限的約束條件,因此需要在新鏈路生成后補充沖突檢測算法,文獻[12,16]分別提出了相應的沖突檢測算法。為了減少鏈路分配的計算量,如何設計一種在既滿足鏈路約束,同時避免沖突檢測交叉機制是有必要的。

本文以一顆衛星只能攜帶一個星間鏈路相控陣天線為例,建立了以星間測量PDOP值作為優化目標的星間鏈路規劃模型。通過利用FSA的思想設計了一種星間鏈路拓撲劃分機制,將每個超幀(包含20個子幀)視為種群,建模為以最大PDOP值最小化為目標的優化問題。針對傳統遺傳算法的基因變異機制和染色體交叉機制無法滿足優化模型約束條件的難題,本文提出了單點溯源變異(SPTV)機制和基于“雜交+自交”思想的時隙雜交(TSX)與位置自交(PSX)染色體交叉機制。最后,利用改進后的遺傳算法對星間鏈路拓撲優化進行迭代求解。

1 動態鏈路拓撲規劃問題描述

星間鏈路的建立需要滿足3個基本條件：① 2 顆建鏈衛星之間不被遮擋；② 2顆衛星的天線都在給定的指向角內；③ 二者之間的距離小于最大通信距離。但由于衛星在空間中一直處于運動狀態,因此衛星之間的可視性是動態變化的。在衛星搭載星間鏈路天線受限的情況下,如何在動態變化的可視衛星集合中選擇1顆衛星建立星間鏈路值得深入研究。

1.1 鏈路拓撲處理

由于衛星的動態可視性,導航衛星網絡的拓撲結構也是一直動態變化的。當單顆衛星僅能建立一個星間鏈路的時候,導航衛星網絡就構成了一個典型的DTN網絡。圖1為不同時隙下導航衛星網絡拓撲示意圖。在不同的時隙下,除自身以外,衛星1～衛星4分別與不同的衛星建鏈。每一時隙下每顆衛星僅能與1顆衛星建立雙向鏈路,因此衛星只有建鏈和空閑2種狀態。如圖1中,在時隙4時刻,衛星1和衛星4均處于空閑狀態,衛星2和衛星3處于建鏈狀態。

圖1 不同時隙下導航衛星網絡拓撲示意圖Fig.1 Topology for navigation satellite network in different time slots

導航衛星網絡以時分復用傳輸模式(Time-Division Multi-plexing Access, TDMA)運行,且軌道運動的周期具有周期性,因此本文借鑒FSA的思想進行建模。FSA的思想是將時間范圍劃分成對應于不同狀態的幾個等長時間間隔,并將其定義為超幀。每個超幀由幾個等長的子幀組成,每個子幀包含若干個時隙。每個超幀都是一個星間鏈路觀測周期,也是鏈路分配的基本時間單位。

圖2為星間鏈路網絡拓撲處理方案,將導航衛星網絡系統的周期劃分為個等長的時間間隔,每個時間間隔對應一個FSA狀態。當2顆衛星在整個FSA狀態下彼此可見時,才被定義為可見,否則定義為不可見。因此在上述方案下,每個FSA狀態下衛星之間的能見度是固定的,因此可以在不同的FSA狀態中以固定的可見性進行鏈路分配。通過FSA狀態的設置可以節省計算和存儲資源,并提高鏈路計劃管理的簡單性?？紤]到不同大小的將會影響一個FSA狀態內的可見衛星數量,因此本文在第3節性能分析部分對不同對衛星可見數量和鏈路影響進行了評估。

圖2 星間鏈路網絡拓撲處理方案Fig.2 Scheme for handling ISL network topology

1.2 性能指標PDOP

導航衛星網絡的軌道定位精度取決于測距衛星的數量、幾何分布和測距精度。當可見衛星數量和鏈路測距精度固定時,衛星網絡的軌道定位精度由測距鏈路的幾何形狀決定。由于PDOP既能反映星間觀測的數量,又能反映星間觀測的幾何分布,因此本文采用PDOP作為測距性能的度量,其計算方式為

(1)

式中：表示當衛星與顆衛星相連接時,得到具有個觀測值的觀測矩陣,維度為×3,即

(2)

文獻[22]推導出PDOP+1始終小于PDOP,這就表明觀測數量的增多會導致更小的PDOP。由于衛星間能見度和Ka波段天線數量的限制,PDOP受到一個定軌周期內時隙分配的影響。因此,應該為每個時隙分配更多不同的測距鏈路。

1.3 鏈路拓撲優化模型

導航衛星網絡鏈路分配的目的是實現星間測距最優化,本文將星間測距的PDOP作為優化目標,將鏈路分配問題建模為在滿足星間鏈路建鏈約束下,以最大PDOP值最小化為目標的優化問題?；谝陨系膯栴}描述,對模型符號進行了相關定義與說明,如表1所示。

表1 模型參數說明Table 1 Model parameter description

假設在第個時隙存在第顆衛星和第顆衛星,此時二者的可見關系可以表述為,,。當,,=1時,表示衛星與衛星可視。若選擇衛星與衛星在第個時隙建鏈,則,,=1,否則,,=0。因為FSA的思想是在時間間隔內2顆衛星持續可見才定義為可見,故衛星網絡的可視矩陣集合為=[,,…,,…,]。其中,為第個超幀的可見關系矩陣。

由以上符號定義可知,鏈路拓撲優化問題模型可以描述為

1) 目標函數

(3)

2) 約束條件

,,=,,, ?,,

(4)

(5)

(6)

,,=,,, ?,,

(7)

,,∈[0,1], ?,,

(8)

,,∈[0,1], ?,,

(9)

,,=0,=, ?

(10)

,,=0,=, ?

(11)

導航衛星網絡的鏈路拓撲優化問題模型將PDOP值最小化作為優化目標,為了更準確地表征測距性能這一指標,本文采用所有衛星中的最大PDOP值作為考量標準。如式(3)所示,通過計算某一子幀中各衛星的PDOP,將其中的最大值作為需要優化的目標,在滿足約束條件的情況下,實現鏈路拓撲的最大PDOP的最小化。將最大PDOP最小化作為優化目標的原因是平均PDOP只能代表整網的位置精度因子,并不能保證每顆衛星的PDOP都較小。若當前子幀以犧牲某一顆衛星的PDOP作為代價實現整網的平均PDOP最小,這樣的鏈路分配同樣是不可取的。而最大PDOP的最小化能夠保證每顆衛星的PDOP均為最優解,保證每顆衛星的星間測量PDOP平均值都比較小,不以犧牲某一衛星的PDOP值來提高其他衛星的PDOP值。同時,最大PDOP的最小化也會有助于整網平均PDOP的優化。因此,選擇最大PDOP的最小化作為優化目標是合理的。

約束條件中,約束式(4)為可見性矩陣對稱性約束,表示衛星與衛星在時隙時的可視性是對稱的。約束式(5)和式(6)為鏈路數量約束,由于星間鏈路數量受限,對于任意的衛星和衛星,在時隙時所能鏈接的最大鏈路數為1。約束式(7)為鏈路分配矩陣對稱性約束,當衛星與衛星在時隙時互相建鏈,那么二者的取值是相等的。約束式(8)和式(9)分別為衛星與衛星在時隙時的可見關系和建鏈關系取值約束。約束式(10)和式(11)表示衛星與衛星在時隙時,衛星自身是無法可見和建鏈的,因此可視關系矩陣和鏈路分配矩陣的對角線元素均為0。圖3為不同時隙下鏈路分配矩陣示意圖。在鏈路分配問題中,衛星與衛星能否建鏈不僅受衛星之間可視性約束、鏈路數量約束,同時也受時間維度的約束。在不同的時隙下,衛星之間的建鏈情況是不同的。因此,鏈路分配問題需要結合DTN的屬性來完成以測距性能為優化目標的導航衛星網絡拓撲優化。

圖3 不同時隙下鏈路分配矩陣示意圖Fig.3 Schematic of link allocation matrix for different time slots

2 拓撲規劃算法

從第1節中所建立的鏈路拓撲優化模型可以看出,在實現最大PDOP值的最小化目標的過程中,首先需要從在滿足給定約束條件下生成鏈路分配集合,將其定義為集合,再以最大PDOP值最小化為目標,從生成的鏈路分配集合中為每個時隙尋找最優的分配方案。假設星座中有顆衛星,在不考慮鏈路約束的條件下,某一時隙下星座的鏈路分配集合為

(12)

當=27時,鏈路分配集合的可能取值約為5×10。若對所有時隙的集合采用遍歷的方法進行全局搜索,在不考慮鏈路約束條件下的計算量已經十分巨大,因此全局搜索求解最優鏈路分配十分困難。因此,本文采用遺傳算法(Genetic Algorithm, GA)的思想,針對拓撲矩陣機制下的導航衛星鏈路分配問題進行求解。

2.1 遺傳算法

遺傳算法最早是由美國的Holland提出的,該算法通過模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程實現最優解的解算。

傳統的遺傳算法的流程如圖4所示。種群預先初始化后,對染色體進行編碼,然后根據評估函數計算當前種群的適應度,以此來評估當前種群的優劣性。通過種群的適應度,選擇出優質的種群作為父代,并經過染色體交叉生成子代種群。

圖4 傳統遺傳算法流程圖Fig.4 Flow chart of traditional genetic algorithm

考慮到自然界中基因變異的存在,根據子代種群生成變異子代種群,通過與父代種群集合形成新一代種群后,再次進行種群的適應度計算。如此循環,直至迭代結束,最終解碼染色體得到最優解。

遺傳算法的優點在于不需要全網遍歷檢索求解目標函數,而是將初始化種群按照優勝劣汰的準則,為種群選擇優質的基因,從而實現最優解的求解。相比于遍歷搜索,遺傳算法具有計算量小的優勢。

2.2 改進遺傳算法

傳統的遺傳算法對于極值求解、旅行商模型求解等問題具有較好的通用性,但對于導航衛星網絡的鏈路分配問題,需要設計新的種群機制、交叉機制和變異機制。由第1節可知,由于DTN的特有屬性使得鏈路分配問題既包括空間的約束,也受到時間的約束,因此這是一個由衛星、超幀和時隙組成的三維體系。若直接使用傳統的遺傳算法進行目標優化,種群的初始化和種群的交叉和基因的變異是較難完成的。因此,本文采用一種緊湊型的鏈路分配矩陣,將原有三維體系降為二維系統,如此將衛星和時隙結合,更加有利于導航衛星網絡的鏈路拓撲優化問題。圖5為緊湊型鏈路分配矩陣示意圖。當鏈路分配矩陣由圖3緊湊至圖5時,可以通過構建多個不同的矩陣實現種群的初始化。

圖5 緊湊型鏈路分配矩陣Fig.5 Compact link allocation matrix

此外,由于鏈路分配矩陣和可視關系矩陣的取值均為0或1,所以對于導航衛星網絡鏈路拓撲優化問題不需要進行編碼和解碼。同時,依照傳統遺傳算法的思想,可以通過染色體交叉和基因變異完成最優解的求解。但由第1節中的模型約束可知,星間鏈路受限情況下,衛星僅能有一條鏈路。若對鏈路分配矩陣進行交叉操作和變異操作,極易產生大量的沖突,導致新生成的種群不滿足模型約束。針對上述問題,本文提出了更加適合于鏈路分配矩陣的新型交叉機制和變異機制,有效地避免了沖突問題的產生。

2.2.1 種群初始化

基于圖5的緊湊型鏈路分配矩陣設計,可以將每一張鏈路分配矩陣看做每個子幀的鏈路分配結果,當一個超幀中存在個子幀時,可以將鏈路分配矩陣擴充為張,如此就形成了第個超幀的初始種群。鏈路分配矩陣需要滿足第1節中的模型約束,由于緊湊型鏈路分配矩陣包含了時隙信息,約束式(7)需要更改為

,=?,,

(13)

,=?,,

(14)

式中：,和,為鏈路分配矩陣的元素,維度大小為×。張鏈路分配矩陣可以構成第個超幀的鏈路分配集合,所以鏈路分配矩陣集合為={,,…,,…,}。圖6為鏈路分配矩陣種群初始化流程圖,若超幀發生變化時,可以通過輸入不同超幀對應的可視關系矩陣,實現新的種群初始化。

2.2.2 適應度計算與父代選擇

由1.3節中式(3)可知,鏈路拓撲優化模型以最大PDOP值的最小化為優化目標。根據式(1)和式(2)可以計算得出一個超幀內某個子幀的鏈路分配矩陣中所有衛星的PDOP,然后取一個子幀內中最大的PDOP值作為適應度值進行父代種群的選擇。父代種群的選擇使用輪盤賭選擇算法進行,若最大PDOP的值越大,反而該鏈路分配矩陣被選中的概率越小,從而選擇將最大PDOP中較小的鏈路分配矩陣作為父代。

圖6 鏈路分配矩陣Am的種群初始化流程圖Fig.6 Flow chart of population initialization of link allocation matrix Am

2.2.3 染色體交叉

目前,常用的染色體交叉算法包括：順序交叉(Order Crossover, OX)、基于位置的交叉(Position Based Crossover, PBX)和循環交叉(Cyclic Crossover, CX)。圖7為遺傳算法的3種交叉方法示意圖。

OX的思想是在父代1中隨機選擇染色體的片段作為交叉對象遺傳給子代,將父代2中除去被選中的交叉對象段后按順序依次遺傳給子代。PBX方法將父代2中除去被選中位置的交叉個體后,按照先后順序依次遺傳給子代。相比于OX和PBX,CX的思想較為復雜。CX隨機選擇一個位置作為起始點,按照從父代1到父代2交替的原則尋找一個閉合循環圈。以圖7(c)為例,父代1中以“1”作為起點,依次尋找得到的循環：1→5→3→1,將父代1中的對應位置遺傳給子代,從父代2中剔除已經被選中的對象后,將剩余對象遺傳給子代。

圖7 遺傳算法的3種交叉方法Fig.7 Three crossover methods of genetic algorithm

從上述的交叉操作中不難發現,不論是OX、PBX還是CX,都不適用于鏈路分配矩陣的情況。如果采用上述的交叉操作后,將會因沖突問題而增加沖突檢測算法來滿足鏈路拓撲優化模型的約束條件,這將導致計算量的額外增加?？紤]到上述交叉操作的缺陷,本文基于“雜交與自交”的思想提出了一種適用于導航衛星網絡拓撲矩陣的時隙雜交操作(Time Slots Crossover, TSX)和位置自交操作(Position Self-Crossover, PSX)。圖8為TSX方法示意圖,由隨機函數rand產生時隙編號,并隨機選取群體中的鏈路分配矩陣和作為父系和母系,將時隙的所有鏈路分配結果交叉至父系。雖然TSX的方法操作簡單,但TSX的最大優點在于避免了交叉所產生的沖突,保證新雜交產生的子代滿足鏈路分配模型的約束條件。

圖8 TSX方法示意圖Fig.8 Diagram of TSX method

考慮到TSX進行交叉無法保證種群的多樣性,本文提出了PSX操作方法。圖9為PSX方法示意圖,沿用TSX方法中隨機產生的時隙編號,分別讀取當前時隙的簡單型鏈路分配矩陣。然后隨機選擇衛星和衛星作為交叉對象,將中衛星和衛星所在的行與列交叉互換,同時將衛星和衛星的原建鏈衛星和衛星所在的行與列交叉互換。自交完成后的鏈路既滿足約束條件,也出現了新的鏈路。為了更清楚地闡述PSX方法的操作流程,以算例1為例進行說明。

假設Sat 1～Sat 5表示5顆衛星,Slot 1～Slot 5表示5個時隙,A～J表示在Slot 3時隙5顆衛星的匹配衛星編號,若圖9(a)中隨機選擇Sat 1和Sat 5作為交叉對象,將隨機時隙的簡單型鏈路分配矩陣父代中Sat 2所在的行和列與Sat 5所在的行和列自我交叉互換,同時將父代中Sat 1所連接的Sat 4和Sat 5所連接的Sat 3所在的行和列自我交叉互換。經過PSX操作后,種群的鏈路分配結果由父代的“1→4”與“3→5”改變為子代的“1→3”與“4→5”,所產生的新一代子代不僅鏈路分配發生了改變,同時還滿足了模型約束條件。

圖9 PSX方法示意圖Fig.9 Diagram of PSX

但是,并非所有的自交操作都如圖9所示的完美無暇,而是存在特殊情況使得交叉后的子代不滿足鏈路優化模型約束條件。為了避免沖突,在隨機選擇衛星和衛星時,要避免選擇已建鏈衛星對作為自交對象,即衛星和衛星已互相建鏈。若衛星和衛星為衛星對,自交后矩陣對角元素將不滿足約束。同時還要考慮衛星和衛星中不存在空閑衛星,即原建鏈衛星和衛星不能為0,這樣就不會違背式(10)和式(11) 的約束。

在染色體交叉操作中,本文采用“先雜交后自交”的原則進行。考慮到自交會增加衛星空閑個數,因此在在交叉結束后通過搜索所有不可見衛星的排列組合結果,在滿足可視的條件下為空閑衛星重新建鏈。染色體雜交的實現見偽代碼1,其中new_link函數主要為空閑衛星重新建鏈,Compact函數負責將簡單型鏈路分配矩陣轉化為緊湊型。

偽代碼1 染色體交叉操作的偽代碼

2.2.4 基因突變

基因突變是種群基因改變的方式之一,不同于染色體交叉操作,基因突變是染色體上某些點位的改變。但因為鏈路分配矩陣需要滿足模型約束,因此當某一個衛星鏈路發生改變時,勢必會引起其他衛星鏈路的改變,為了解決以上沖突問題,本文提出了單點溯源突變機制(Single Point and Traceable Variation, SPTV)。

如圖10所示,隨機選擇時隙編號上的衛星,從衛星的可視集合中隨機選擇1顆衛星作為突變衛星進行建鏈。由于衛星有可能本身已經建鏈,因此新建鏈路“→”將會影響其他原有鏈路衛星的建鏈情況,因此需要溯源尋找到受影響的衛星,并按照模型約束重新建鏈。為了直觀地理解單點溯源法,本文以算例2進行闡述,基因變異SPTV操作見偽代碼2。

圖10 SPTV方法示意圖Fig.10 Diagram of SPTV

假設從圖10(a)中隨機選擇Slot 5中的Sat 4作為突變對象,隨機從Sat 4的可視集合中選取Sat 1作為建鏈衛星。由于Sat 4和Sat 1本身已存在鏈路分配結果。當新鏈路“1→4”建立后,原有鏈路“1→2”和“4→5”需要拆解。若拆解后的Sat 5和Sat 2不重新分配鏈路,那么將會使當前時隙下新增2顆空閑衛星,這對于最大PDOP最小化的目標是不利的。因此,SPTV將詢問空閑的Sat 5和Sat 2是否可視,若可視則建立鏈路,否則將二者置于空閑狀態。從圖10(b)中可以看出,SPTV會影響4顆衛星的建鏈情況,這不僅避免了大規模的沖突,同時為尋找最佳鏈路分配提供了新的可能。

偽代碼2 基因變異SPTV操作的偽代碼

本文在2.2.3節中提出了以“雜交+自交”為思想的TSX-PSX染色體交叉機制,在2.2.4節中提出了SPTV基因突變機制。上述2種機制都很好地避免了因鏈路拆建而導致的沖突問題,是適用于鏈路分配矩陣的較好機制?；趫D4所示的遺傳算法流程圖,結合TSX-PSX染色體交叉和SPTV基因突變機制,可以實現對優化模型的求解。

2.3 算法復雜度分析

遺傳算法屬于迭代算法,復雜度分析僅需分析其單次迭代過程即可。對于改進遺傳算法的單次迭代過程,僅有染色體交叉過程和基因變異過程復雜度較高,其他過程的運行時間為常數。圖9所示的染色體交叉操作屬于一種隨機過程,它包括內層交叉和外層循環2部分。染色體交叉過程可以看作一系列伯努利試驗,假設染色體的交叉率為,則實驗成功的概率=。定義隨機變量為取得一次成功所要進行的實驗次數,則應滿足幾何分布,其期望為()=1,即內層交叉的平均運行次數為1,故內層交叉的復雜度為(1)。外層循環的次數與種群數量(子幀數量)相關,復雜度為(log)。因此,染色體交叉過程的復雜度為((log))。

圖10為基因突變操作同樣屬于一種隨機過程,其組成部分與染色體交叉過程一致。假設染色體的交叉率為,則內層變異的復雜度為(1)。而外層循環的次數與種群數量(子幀數量)相關,復雜度為()。因此,染色體交叉過程的復雜度為()。綜上,本文改進遺傳算法的復雜度為(max((log),))。

3 性能分析

3.1 仿真環境

本文基于STK軟件參考BDS衛星星座搭建了仿真模型,其中MEO層采用Walker-σ 24/3/1構型,軌道高度為21 528 km,軌道傾角為55°。IGSO層軌道高度為35 786 km,軌道傾角為55°,交叉點經度為東經118°,3顆衛星以升交點赤經相差120°均勻分布在3個軌道面內。衛星星載天線采用簡單圓錐型,圓錐半角為60°,方位角范圍為-180°～180°。仿真時間從UTC 2021/05/30 00∶00∶00—2021/05/31 00∶00∶00,共計86 400 s。為了便于計算將星座數據的采樣周期設置為1 min。

拓撲處理參數如表2所示,其中超幀的持續時間分別設置為600 s和900 s。在不同超幀持續時間下,不同超幀的各衛星的可見個數不同,如圖11所示。以IGSO1、MEO11和MEO21和MEO31這4顆為例,當超幀時間分別為600 s和900 s時,各衛星的可視衛星數量整體在11～20之間。但對于不同超幀下,2種超幀時間的可視衛星數量是有變化的,那么鏈路分配結果將會不同。因此,超幀的持續時間對優化目標存在一定的影響。

表2 拓撲處理參數Table 2 Parameters of topology processing

圖11 不同超幀時間的衛星可視數量Fig.11 Number of satellites visible in different superframe durations

3.2 仿真結果

3.2.1 遺傳算法參數對優化目標的影響

在遺傳算法中,影響到迭代結果的因素分別為：迭代次數、染色體交叉率和基因變異率。為了探究以上3個因素對優化目標的影響,本文采用控制變量法的方式,分別對3種因素進行了仿真探究。以第1個超幀為例,圖12為3種因素在不同參數下對優化目標最大PDOP的影響結果。從圖12中可以看出,當迭代次數為10 000次時優化后的結果最優,最大PDOP為2.574；當染色體交叉率為0.9時,第1個超幀中最大PDOP為2.473,明顯優于其他參數的優化結果；當基因突變率為0.1時,第1個超幀中最大PDOP為2.538,相比于其他參數較好。

3.2.2 不同超幀的優化目標仿真結果

基于3.2.1節的參數探究,針對不同超幀的優化目標仿真,遺傳算法參數分別設置為：迭代次數10 000、染色體交叉率0.9和基因突變率0.1。由3.1節分析可知,不同超幀持續時間會影響衛星的可視數量,對優化目標存在一定的影響。因此,本文針對兩種超幀時間進行模型優化,仿真結果如圖13所示。

圖13 不同超幀持續時間對最大PDOP的影響Fig.13 Influence of different superframe durations on maximum PDOP

從橫向對比,不論超幀的持續時間取值為多少,迭代優化后的最大PDOP整體趨勢是保持一致的。因為超幀時間分別為600 s和900 s時,影響到衛星可視性的數量是少數的。同時,從圖13中可以看出,所有衛星的整體可視數量區間在超幀改變前后是保持一致的。因此,可視衛星數量的少許變化對于最大PDOP的影響并不明顯。但從縱向對比,由于超幀持續時間的改變會導致仿真周期最大PDOP平均值的改變。如表3所示,超幀持續時間為900 s時,最大PDOP的最小值和均值都比超幀持續時間為600 s時大,PDOP值提高了3.82%。由此可見,超幀持續時間較長時會導致PDOP增大。

表3 不同超幀持續時間的最大PDOP值的結果

3.2.3 改進遺傳算法的優化目標仿真結果

為驗證基于“雜交+自交”思想的TSX-PSX染色體交叉機制的有效性,本文將TSX-PSX作為實驗組,以TSX作為對照組,將超幀持續時間設置為600 s進行仿真,實驗結果如圖14所示。相比于僅使用TSX進行染色體交叉,TSX-PSX交叉后的最大PDOP值更小。TSX-PSX在遺傳母系的鏈路分配結果之后,會對該時隙的鏈路進行內部交叉。正是這種內部交叉不僅保持了母系的大部分鏈路分配結果,而且建立了新的鏈路,增加了種群的多樣性。因此,在采用TSX-PSX之后,最大PDOP整體減小,優化后的鏈路拓撲結構PDOP值更小。

圖14 不同染色體交叉機制下的仿真結果Fig.14 Simulation results of different chromosome crossover mechanisms

如表4所示,相比于TSX染色體交叉機制,TSX-PSX對最大PDOP的優化有顯著的效果,PDOP值減小了27.28%。此外,相比于文獻[22]中的最大PDOP≤2.8,TSX-PSX的結果與之保持一致。因此,改進后遺傳算法的TSX-PSX染色體交叉機制的有效性得到驗證。

表4 不同染色體交叉機制最大PDOP值的結果

4 結 論

本文針對導航衛星星間鏈路數量受限情況下的鏈路拓撲規劃問題,以星間測量最大PDOP值最小化作為優化目標建立了鏈路拓撲優化模型。根據優化目標和約束條件,采用遺傳算法對優化模型進行求解。本文提出了基于“雜交+自交”思想的TSX-PSX染色體交叉機制和SPTV基因突變機制,有效解決了傳統遺傳算法中染色體交叉機制和基因變異機制不滿足鏈路拓撲模型約束而導致大規模沖突問題。仿真結果證明,TSX-PSX染色體機制相比于單一的TSX染色體交叉機制,將最大PDOP值改善了27.28%,驗證了改進遺傳算法的TSX-PSX染色體機制的有效性。

致 謝

感謝中國科學技術大學尹東副教授和盛捷老師的指點,感謝馬慧晨和柯新建對論文研究的幫助和支持。