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

1. 中國科學(xué)院大學(xué),北京 100049 2. 中國科學(xué)院 微小衛(wèi)星創(chuàng)新研究院,上海 201210

衛(wèi)星導(dǎo)航系統(tǒng)作為重要的國家戰(zhàn)略基礎(chǔ)設(shè)施,提高其可靠性和系統(tǒng)性能具有重要意義。星間鏈路(Inter-Satellite Links, ISLs)作為全球?qū)Ш叫l(wèi)星系統(tǒng)(Global Navigation Satellite Systems, GNSS)的重要組成部分,為監(jiān)控站分布受限情況下的星座定軌提供了一種有效方法。星間鏈路的作用主要包括星間測量和星間通信。

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

針對星間鏈路拓?fù)鋬?yōu)化問題,國內(nèi)外學(xué)者已廣泛開展了相關(guān)研究。文獻[7-9]采用“永久鏈路+非永久鏈路”的思想實現(xiàn)衛(wèi)星導(dǎo)航系統(tǒng)的鏈路分配。其中,文獻[7]提出了一種多層鏈路拓?fù)浼盎旌下酚稍O(shè)計方案,按照持續(xù)可見鏈路為主和非持續(xù)可見鏈路為輔的原則,采用基于代價函數(shù)的非持續(xù)鏈路選擇方法實現(xiàn)了星間鏈路拓?fù)浞桨傅纳?。文獻[8]針對非永久鏈路提出了基于幾何精度因子(Geometric Dilution of Precision, GDOP)貢獻值的設(shè)計方法,實現(xiàn)了任意MEO (Medium Earth Orbit)定軌精度的平均空間位置精度因子(Position Dilution of Precision, PDOP) 小于2.2的技術(shù)指標(biāo)。文獻[9]以可見衛(wèi)星距離和俯仰角作為約束原則為非永久鏈路進行分配。

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

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

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

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

1 動態(tài)鏈路拓?fù)湟?guī)劃問題描述

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

1.1 鏈路拓?fù)涮幚?/h3>

由于衛(wèi)星的動態(tài)可視性,導(dǎo)航衛(wèi)星網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)也是一直動態(tài)變化的。當(dāng)單顆衛(wèi)星僅能建立一個星間鏈路的時候,導(dǎo)航衛(wèi)星網(wǎng)絡(luò)就構(gòu)成了一個典型的DTN網(wǎng)絡(luò)。圖1為不同時隙下導(dǎo)航衛(wèi)星網(wǎng)絡(luò)拓?fù)涫疽鈭D。在不同的時隙下,除自身以外,衛(wèi)星1～衛(wèi)星4分別與不同的衛(wèi)星建鏈。每一時隙下每顆衛(wèi)星僅能與1顆衛(wèi)星建立雙向鏈路,因此衛(wèi)星只有建鏈和空閑2種狀態(tài)。如圖1中,在時隙4時刻,衛(wèi)星1和衛(wèi)星4均處于空閑狀態(tài),衛(wèi)星2和衛(wèi)星3處于建鏈狀態(tài)。

圖1 不同時隙下導(dǎo)航衛(wèi)星網(wǎng)絡(luò)拓?fù)涫疽鈭DFig.1 Topology for navigation satellite network in different time slots

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

圖2為星間鏈路網(wǎng)絡(luò)拓?fù)涮幚矸桨?將導(dǎo)航衛(wèi)星網(wǎng)絡(luò)系統(tǒng)的周期劃分為個等長的時間間隔,每個時間間隔對應(yīng)一個FSA狀態(tài)。當(dāng)2顆衛(wèi)星在整個FSA狀態(tài)下彼此可見時,才被定義為可見,否則定義為不可見。因此在上述方案下,每個FSA狀態(tài)下衛(wèi)星之間的能見度是固定的,因此可以在不同的FSA狀態(tài)中以固定的可見性進行鏈路分配。通過FSA狀態(tài)的設(shè)置可以節(jié)省計算和存儲資源,并提高鏈路計劃管理的簡單性。考慮到不同大小的將會影響一個FSA狀態(tài)內(nèi)的可見衛(wèi)星數(shù)量,因此本文在第3節(jié)性能分析部分對不同對衛(wèi)星可見數(shù)量和鏈路影響進行了評估。

圖2 星間鏈路網(wǎng)絡(luò)拓?fù)涮幚矸桨窮ig.2 Scheme for handling ISL network topology

1.2 性能指標(biāo)PDOP

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

(1)

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

(2)

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

1.3 鏈路拓?fù)鋬?yōu)化模型

導(dǎo)航衛(wèi)星網(wǎng)絡(luò)鏈路分配的目的是實現(xiàn)星間測距最優(yōu)化,本文將星間測距的PDOP作為優(yōu)化目標(biāo),將鏈路分配問題建模為在滿足星間鏈路建鏈約束下,以最大PDOP值最小化為目標(biāo)的優(yōu)化問題?；谝陨系膯栴}描述,對模型符號進行了相關(guān)定義與說明,如表1所示。

表1 模型參數(shù)說明Table 1 Model parameter description

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

由以上符號定義可知,鏈路拓?fù)鋬?yōu)化問題模型可以描述為

1) 目標(biāo)函數(shù)

(3)

2) 約束條件

,,=,,, ?,,

(4)

(5)

(6)

,,=,,, ?,,

(7)

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

(8)

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

(9)

,,=0,=, ?

(10)

,,=0,=, ?

(11)

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

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

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

2 拓?fù)湟?guī)劃算法

從第1節(jié)中所建立的鏈路拓?fù)鋬?yōu)化模型可以看出,在實現(xiàn)最大PDOP值的最小化目標(biāo)的過程中,首先需要從在滿足給定約束條件下生成鏈路分配集合,將其定義為集合,再以最大PDOP值最小化為目標(biāo),從生成的鏈路分配集合中為每個時隙尋找最優(yōu)的分配方案。假設(shè)星座中有顆衛(wèi)星,在不考慮鏈路約束的條件下,某一時隙下星座的鏈路分配集合為

(12)

當(dāng)=27時,鏈路分配集合的可能取值約為5×10。若對所有時隙的集合采用遍歷的方法進行全局搜索,在不考慮鏈路約束條件下的計算量已經(jīng)十分巨大,因此全局搜索求解最優(yōu)鏈路分配十分困難。因此,本文采用遺傳算法(Genetic Algorithm, GA)的思想,針對拓?fù)渚仃嚈C制下的導(dǎo)航衛(wèi)星鏈路分配問題進行求解。

2.1 遺傳算法

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

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

圖4 傳統(tǒng)遺傳算法流程圖Fig.4 Flow chart of traditional genetic algorithm

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

遺傳算法的優(yōu)點在于不需要全網(wǎng)遍歷檢索求解目標(biāo)函數(shù),而是將初始化種群按照優(yōu)勝劣汰的準(zhǔn)則,為種群選擇優(yōu)質(zhì)的基因,從而實現(xiàn)最優(yōu)解的求解。相比于遍歷搜索,遺傳算法具有計算量小的優(yōu)勢。

2.2 改進遺傳算法

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

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

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

2.2.1 種群初始化

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

,=?,,

(13)

,=?,,

(14)

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

2.2.2 適應(yīng)度計算與父代選擇

由1.3節(jié)中式(3)可知,鏈路拓?fù)鋬?yōu)化模型以最大PDOP值的最小化為優(yōu)化目標(biāo)。根據(jù)式(1)和式(2)可以計算得出一個超幀內(nèi)某個子幀的鏈路分配矩陣中所有衛(wèi)星的PDOP,然后取一個子幀內(nèi)中最大的PDOP值作為適應(yīng)度值進行父代種群的選擇。父代種群的選擇使用輪盤賭選擇算法進行,若最大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)和循環(huán)交叉(Cyclic Crossover, CX)。圖7為遺傳算法的3種交叉方法示意圖。

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

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

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

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

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

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

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

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

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

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

2.2.4 基因突變

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

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

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

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

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

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

2.3 算法復(fù)雜度分析

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

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

3 性能分析

3.1 仿真環(huán)境

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

拓?fù)涮幚韰?shù)如表2所示,其中超幀的持續(xù)時間分別設(shè)置為600 s和900 s。在不同超幀持續(xù)時間下,不同超幀的各衛(wèi)星的可見個數(shù)不同,如圖11所示。以IGSO1、MEO11和MEO21和MEO31這4顆為例,當(dāng)超幀時間分別為600 s和900 s時,各衛(wèi)星的可視衛(wèi)星數(shù)量整體在11～20之間。但對于不同超幀下,2種超幀時間的可視衛(wèi)星數(shù)量是有變化的,那么鏈路分配結(jié)果將會不同。因此,超幀的持續(xù)時間對優(yōu)化目標(biāo)存在一定的影響。

表2 拓?fù)涮幚韰?shù)Table 2 Parameters of topology processing

圖11 不同超幀時間的衛(wèi)星可視數(shù)量Fig.11 Number of satellites visible in different superframe durations

3.2 仿真結(jié)果

3.2.1 遺傳算法參數(shù)對優(yōu)化目標(biāo)的影響

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

3.2.2 不同超幀的優(yōu)化目標(biāo)仿真結(jié)果

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

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

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

表3 不同超幀持續(xù)時間的最大PDOP值的結(jié)果

3.2.3 改進遺傳算法的優(yōu)化目標(biāo)仿真結(jié)果

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

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

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

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

4 結(jié) 論

本文針對導(dǎo)航衛(wèi)星星間鏈路數(shù)量受限情況下的鏈路拓?fù)湟?guī)劃問題,以星間測量最大PDOP值最小化作為優(yōu)化目標(biāo)建立了鏈路拓?fù)鋬?yōu)化模型。根據(jù)優(yōu)化目標(biāo)和約束條件,采用遺傳算法對優(yōu)化模型進行求解。本文提出了基于“雜交+自交”思想的TSX-PSX染色體交叉機制和SPTV基因突變機制,有效解決了傳統(tǒng)遺傳算法中染色體交叉機制和基因變異機制不滿足鏈路拓?fù)淠Ｐ图s束而導(dǎo)致大規(guī)模沖突問題。仿真結(jié)果證明,TSX-PSX染色體機制相比于單一的TSX染色體交叉機制,將最大PDOP值改善了27.28%,驗證了改進遺傳算法的TSX-PSX染色體機制的有效性。

致 謝

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