基于改進(jìn)遺傳算法的導(dǎo)航衛(wèi)星星間鏈路網(wǎng)絡(luò)動(dòng)態(tài)拓?fù)鋬?yōu)化技術(shù)

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

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

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

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

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

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

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

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

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

1 動(dòng)態(tài)鏈路拓?fù)湟?guī)劃問(wèn)題描述

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

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

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

圖1 不同時(shí)隙下導(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ò)以時(shí)分復(fù)用傳輸模式(Time-Division Multi-plexing Access, TDMA)運(yùn)行,且軌道運(yùn)動(dòng)的周期具有周期性,因此本文借鑒FSA的思想進(jìn)行建模。FSA的思想是將時(shí)間范圍劃分成對(duì)應(yīng)于不同狀態(tài)的幾個(gè)等長(zhǎng)時(shí)間間隔,并將其定義為超幀。每個(gè)超幀由幾個(gè)等長(zhǎng)的子幀組成,每個(gè)子幀包含若干個(gè)時(shí)隙。每個(gè)超幀都是一個(gè)星間鏈路觀測(cè)周期,也是鏈路分配的基本時(shí)間單位。

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

圖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ò)的軌道定位精度取決于測(cè)距衛(wèi)星的數(shù)量、幾何分布和測(cè)距精度。當(dāng)可見(jiàn)衛(wèi)星數(shù)量和鏈路測(cè)距精度固定時(shí),衛(wèi)星網(wǎng)絡(luò)的軌道定位精度由測(cè)距鏈路的幾何形狀決定。由于PDOP既能反映星間觀測(cè)的數(shù)量,又能反映星間觀測(cè)的幾何分布,因此本文采用PDOP作為測(cè)距性能的度量,其計(jì)算方式為

(1)

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

(2)

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

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

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

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

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

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

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

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

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

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

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

(12)

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

2.1 遺傳算法

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

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

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

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

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

2.2 改進(jìn)遺傳算法

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

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

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

2.2.1 種群初始化

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

,=?,,

(13)

,=?,,

(14)

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

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

由1.3節(jié)中式(3)可知,鏈路拓?fù)鋬?yōu)化模型以最大PDOP值的最小化為優(yōu)化目標(biāo)。根據(jù)式(1)和式(2)可以計(jì)算得出一個(gè)超幀內(nèi)某個(gè)子幀的鏈路分配矩陣中所有衛(wèi)星的PDOP,然后取一個(gè)子幀內(nèi)中最大的PDOP值作為適應(yīng)度值進(jìn)行父代種群的選擇。父代種群的選擇使用輪盤(pán)賭選擇算法進(jìn)行,若最大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中隨機(jī)選擇染色體的片段作為交叉對(duì)象遺傳給子代,將父代2中除去被選中的交叉對(duì)象段后按順序依次遺傳給子代。PBX方法將父代2中除去被選中位置的交叉?zhèn)€體后,按照先后順序依次遺傳給子代。相比于OX和PBX,CX的思想較為復(fù)雜。CX隨機(jī)選擇一個(gè)位置作為起始點(diǎn),按照從父代1到父代2交替的原則尋找一個(gè)閉合循環(huán)圈。以圖7(c)為例,父代1中以“1”作為起點(diǎn),依次尋找得到的循環(huán)：1→5→3→1,將父代1中的對(duì)應(yīng)位置遺傳給子代,從父代2中剔除已經(jīng)被選中的對(duì)象后,將剩余對(duì)象遺傳給子代。

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

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

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

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

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

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

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

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

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

2.2.4 基因突變

基因突變是種群基因改變的方式之一,不同于染色體交叉操作,基因突變是染色體上某些點(diǎn)位的改變。但因?yàn)殒溌贩峙渚仃囆枰獫M足模型約束,因此當(dāng)某一個(gè)衛(wèi)星鏈路發(fā)生改變時(shí),勢(shì)必會(huì)引起其他衛(wèi)星鏈路的改變,為了解決以上沖突問(wèn)題,本文提出了單點(diǎn)溯源突變機(jī)制(Single Point and Traceable Variation, SPTV)。

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

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

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

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

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

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

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

圖10為基因突變操作同樣屬于一種隨機(jī)過(guò)程,其組成部分與染色體交叉過(guò)程一致。假設(shè)染色體的交叉率為,則內(nèi)層變異的復(fù)雜度為(1)。而外層循環(huán)的次數(shù)與種群數(shù)量(子幀數(shù)量)相關(guān),復(fù)雜度為()。因此,染色體交叉過(guò)程的復(fù)雜度為()。綜上,本文改進(jìn)遺傳算法的復(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°,交叉點(diǎn)經(jīng)度為東經(jīng)118°,3顆衛(wèi)星以升交點(diǎn)赤經(jīng)相差120°均勻分布在3個(gè)軌道面內(nèi)。衛(wèi)星星載天線采用簡(jiǎn)單圓錐型,圓錐半角為60°,方位角范圍為-180°～180°。仿真時(shí)間從UTC 2021/05/30 00∶00∶00—2021/05/31 00∶00∶00,共計(jì)86 400 s。為了便于計(jì)算將星座數(shù)據(jù)的采樣周期設(shè)置為1 min。

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

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

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

3.2 仿真結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

致 謝

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