基于啟發(fā)式遺傳算法的時(shí)分星間網(wǎng)絡(luò)拓?fù)鋬?yōu)化設(shè)計(jì)

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

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

0 引言

在全球衛(wèi)星導(dǎo)航系統(tǒng)中，引入星間鏈路可以進(jìn)行星間測(cè)距和星間數(shù)據(jù)傳輸，通過(guò)星間測(cè)距可以提高導(dǎo)航衛(wèi)星的定軌精度，利用星間數(shù)據(jù)傳輸可以提高導(dǎo)航星歷的更新頻度，也可以減少全球布站的數(shù)量，因此，依托星間鏈路技術(shù)在空間建立星間網(wǎng)絡(luò)是衛(wèi)星導(dǎo)航系統(tǒng)必然的發(fā)展趨勢(shì)。目前，國(guó)際上全球?qū)Ш较到y(tǒng)(GNSS) 都已加入或正在進(jìn)行星間鏈路的建設(shè)，GPS 通過(guò)星間鏈路已經(jīng)實(shí)現(xiàn)星座自主導(dǎo)航，并且可以保證系統(tǒng)自主運(yùn)行180天，系統(tǒng)精度不會(huì)降低，極大地提高了系統(tǒng)的抗毀能力，我國(guó)的北斗系統(tǒng)也加入了星間鏈路。

北斗三號(hào)衛(wèi)星工程星間鏈路網(wǎng)絡(luò)是我國(guó)第一個(gè)在建的大型星地一體的空間信息網(wǎng)絡(luò)系統(tǒng)，采用相控陣時(shí)分體制，是天地一體、具有精密測(cè)量和數(shù)傳功能的動(dòng)態(tài)無(wú)線網(wǎng)絡(luò)[1]。

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

本文提出一種將網(wǎng)絡(luò)的鏈路層與網(wǎng)絡(luò)層管理解耦合，提出一種基于啟發(fā)式遺傳算法的網(wǎng)絡(luò)拓?fù)鋬?yōu)化設(shè)計(jì)方法，并采用分時(shí)最短時(shí)延的路由算法。最后，對(duì)星間網(wǎng)絡(luò)測(cè)量指標(biāo)進(jìn)行了統(tǒng)計(jì)分析，以星間數(shù)據(jù)傳輸和星星地?cái)?shù)據(jù)下傳作為星間網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)牡湫凸r，對(duì)星間網(wǎng)絡(luò)拓?fù)渎酚梢?guī)劃的結(jié)果進(jìn)行了邏輯仿真，驗(yàn)證了算法的實(shí)用性和優(yōu)越性。

1 問(wèn)題分析

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

1.1 可見(jiàn)性約束

1.1.1 幾何可見(jiàn)性約束

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

圖1 星間幾何可見(jiàn)

滿足地球無(wú)阻擋條件：

(1)

d≤dmax

(2)

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

滿足衛(wèi)星掃描角約束：

(3)

(4)

θ1≤α1

(5)

θ2≤α2

(6)

其中：θ1,θ2分別為衛(wèi)星2和衛(wèi)星1在對(duì)方本體坐標(biāo)系中的視線錐角，α1，α2分別為衛(wèi)星1和衛(wèi)星2的天線掃描角。

對(duì)于衛(wèi)星與地面站，它們互相可見(jiàn)的條件是衛(wèi)星位于地面站外切水平面之上，并滿足衛(wèi)星波束掃描角度和地面設(shè)備波束截止角度的約束。

圖2 星地幾何可見(jiàn)

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

(7)

ψ≥ψmin

(8)

其中：ψmin為地面設(shè)備的截止角。

1.1.2 鏈路可達(dá)性約束

受星上天線載荷的條件限制，星間幾何可見(jiàn)的衛(wèi)星可能由于天線的發(fā)射功率、天線增益、接收靈敏度、空間損耗等原因，星間信號(hào)可傳輸?shù)臉O限距離小于實(shí)際幾何距離，導(dǎo)致建鏈不成功，因此，在進(jìn)行規(guī)劃時(shí)，必須考慮鏈路可達(dá)性。

(9)

d≤dmax

(10)

1.2 體制約束

本文所設(shè)計(jì)的星間鏈路系統(tǒng)是基于TDMA體制下的，即在一個(gè)超幀內(nèi)，將時(shí)間劃分成若干個(gè)等同的時(shí)間片，稱為時(shí)隙。在一個(gè)時(shí)隙內(nèi)，衛(wèi)星可以與在其可見(jiàn)范圍內(nèi)的某一顆衛(wèi)星建立鏈路進(jìn)行測(cè)量與數(shù)據(jù)傳輸。在每個(gè)時(shí)隙內(nèi)，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)固定，整個(gè)衛(wèi)星星座擁有許多條星間鏈路，這些鏈路相互獨(dú)立互不干擾，每一條連接著兩顆相互可見(jiàn)的衛(wèi)星，它們可以通過(guò)鏈路進(jìn)行測(cè)量數(shù)據(jù)傳輸，并且每顆衛(wèi)星有且僅有一條鏈路。

以5個(gè)節(jié)點(diǎn)組成的10時(shí)隙時(shí)分網(wǎng)絡(luò)為例，圖3表示了時(shí)分體制的建鏈拓?fù)浔磉_(dá)方式。圖中第一行表示，在1時(shí)隙，節(jié)點(diǎn)1與節(jié)點(diǎn)5建鏈，節(jié)點(diǎn)2與節(jié)點(diǎn)3建鏈，節(jié)點(diǎn)4輪空。

圖3 時(shí)分體制網(wǎng)絡(luò)拓?fù)?/p>

對(duì)于一個(gè)衛(wèi)星來(lái)說(shuō)，在一個(gè)超幀的不同時(shí)隙，可以通過(guò)與不同的衛(wèi)星輪流進(jìn)行建鏈，以滿足測(cè)量的多樣性。但是在星間數(shù)據(jù)傳輸過(guò)程中，若路由所選鏈路的時(shí)隙與數(shù)據(jù)的傳輸時(shí)機(jī)距離較遠(yuǎn)，就可能因時(shí)隙等待造成較大的數(shù)據(jù)傳輸時(shí)延，在網(wǎng)絡(luò)規(guī)劃時(shí)應(yīng)當(dāng)給予充分考慮。

1.3 業(yè)務(wù)要求

導(dǎo)航星座星間鏈路承載著自主導(dǎo)航、精密定軌、時(shí)間統(tǒng)一等導(dǎo)航業(yè)務(wù)，這些業(yè)務(wù)對(duì)網(wǎng)絡(luò)的測(cè)量和數(shù)傳要求均不相同，本文取其在某工作模式下的指標(biāo)要求如表1所示。

表1 導(dǎo)航星座指標(biāo)要求

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

拓?fù)湟?guī)劃是復(fù)雜星間網(wǎng)絡(luò)的鏈路層規(guī)劃，是網(wǎng)絡(luò)層路由規(guī)劃的基礎(chǔ)，本文采取將二者解耦和的方式進(jìn)行規(guī)劃，在進(jìn)行底層的拓?fù)湟?guī)劃時(shí)充分將業(yè)務(wù)數(shù)據(jù)傳輸要求納入考慮范疇，在進(jìn)行網(wǎng)絡(luò)層路由規(guī)劃時(shí)，以已有拓?fù)湟?guī)劃為基礎(chǔ)進(jìn)行路徑選擇，不再根據(jù)路由的結(jié)果返回修改拓?fù)湟?guī)劃。

拓?fù)湟?guī)劃的對(duì)象包括30個(gè)節(jié)點(diǎn)，且每分鐘20個(gè)時(shí)隙，拓?fù)湟?guī)劃的鏈路≤600，并且存在很多約束條件，是一個(gè)多維多約束多解問(wèn)題，無(wú)論是通過(guò)經(jīng)驗(yàn)設(shè)定規(guī)則進(jìn)行規(guī)劃還是單純依靠的通用智能算法進(jìn)行搜索，都很難求得其確定的最優(yōu)解，因此本方案采用啟發(fā)式遺傳算法將二者相結(jié)合，先通過(guò)理論分析制定拓?fù)湟?guī)劃的基本原則，給出一個(gè)能滿足大部分需求的拓?fù)淇蚣?，以此作為初值，利用遺傳算法對(duì)拓?fù)溥M(jìn)行優(yōu)化，來(lái)尋求其有限時(shí)間內(nèi)能取得的局部最優(yōu)解。

2.1 初步規(guī)劃

通過(guò)對(duì)星座的仿真分析，有如下結(jié)論：

1) 全星座下，每一個(gè)MEO衛(wèi)星都有8個(gè)MEO衛(wèi)星與之永久可見(jiàn)。

2) 每小時(shí)內(nèi)MEO都有大于等于12 個(gè)非永久可見(jiàn)衛(wèi)星(包括GEO、IGSO和MEO)在本小時(shí)內(nèi)與之持續(xù)可見(jiàn)。

通過(guò)對(duì)星座數(shù)據(jù)傳輸任務(wù)過(guò)程和拓?fù)湟?guī)劃過(guò)程的分析，有如下結(jié)論：

1) 境外-境內(nèi)星間鏈路在星星地?cái)?shù)據(jù)傳輸中起重要作用；

2) 境外-境內(nèi)星間鏈路的時(shí)序排列與星星地?cái)?shù)據(jù)傳輸時(shí)延息息相關(guān)；

3) 在進(jìn)行拓?fù)浔淼囊?guī)劃時(shí)，存在先后制約關(guān)系，在排入可見(jiàn)的衛(wèi)星對(duì)時(shí)，必須先檢查拓?fù)浔碇性摃r(shí)隙下預(yù)排入的兩個(gè)衛(wèi)星是否空閑，如果任何一方已經(jīng)建鏈，則本次排列不成功。故先排入的衛(wèi)星配對(duì)排列成功的概率要比后排入的衛(wèi)星配對(duì)排列成功的概率要高。

充分利用以上先驗(yàn)知識(shí)，本方案在進(jìn)行初步規(guī)劃時(shí)，制定了如下原則：

1) 排入的衛(wèi)星配對(duì)必須在本周期內(nèi)持續(xù)可見(jiàn)；

2) 優(yōu)先排列境內(nèi)-境外星間鏈路；

3) 優(yōu)先為可見(jiàn)境內(nèi)星較少的境外衛(wèi)星安排境內(nèi)-境外星間鏈路；

4) 優(yōu)先排列永久可見(jiàn)鏈路；

5) 境內(nèi)-境外星間鏈路盡量等間隔均勻排入，避免出現(xiàn)局部長(zhǎng)時(shí)間無(wú)境內(nèi)-境外鏈路的情況；

6) 對(duì)各衛(wèi)星盡量安排與不同衛(wèi)星建立星間鏈路。

規(guī)劃步驟如下：

步驟1：進(jìn)行可見(jiàn)性統(tǒng)計(jì)，本周期內(nèi)持續(xù)可見(jiàn)方認(rèn)為可見(jiàn)，并生成星間可見(jiàn)矩陣K；

(11)

K為0,1對(duì)稱矩陣，N為節(jié)點(diǎn)個(gè)數(shù)，為衛(wèi)星節(jié)點(diǎn)和時(shí)分體制地面站節(jié)點(diǎn)之和，ki,j為0表示節(jié)點(diǎn)i與節(jié)點(diǎn)j不可見(jiàn)，ki,j為1表示節(jié)點(diǎn)i與節(jié)點(diǎn)j可見(jiàn)。

步驟2：統(tǒng)計(jì)境內(nèi)星集合，境外星集合，境外星的可見(jiàn)境內(nèi)星集合；

步驟3：生成境外衛(wèi)星按照可見(jiàn)境內(nèi)星個(gè)數(shù)從少到多排序序列；

步驟4：統(tǒng)計(jì)生成永久可見(jiàn)的衛(wèi)星配對(duì)；

步驟5：優(yōu)先排列可見(jiàn)境內(nèi)星較少的MEO境外星，將MEO境外衛(wèi)星中境外-境內(nèi)的可見(jiàn)配對(duì)，以間隔2個(gè)時(shí)隙的規(guī)律排入時(shí)隙表，在此步驟中，優(yōu)先排固定可見(jiàn)的衛(wèi)星配對(duì)，其次排僅本周期內(nèi)可見(jiàn)的衛(wèi)星配對(duì)。為避免重復(fù)建鏈，如果排列成功，則在可見(jiàn)矩陣中將該配對(duì)置0；如果該境外星的可見(jiàn)境內(nèi)星不足，則選取已經(jīng)排過(guò)的境外-境內(nèi)鏈路重復(fù)建鏈。

步驟6：加入高低鏈路，將高低鏈路中境內(nèi)-境外的可見(jiàn)配對(duì)間隔2個(gè)時(shí)隙排入時(shí)隙表，優(yōu)先原則同上，如果排列成功，則在可見(jiàn)矩陣中將該配對(duì)置0。

步驟7：進(jìn)行檢查，如果境外-境內(nèi)鏈路還有剩余沒(méi)有排入的，較境外-境外鏈路優(yōu)先排入，如果排列成功，則在可見(jiàn)矩陣中將該配對(duì)置0。

步驟8：排入星地鏈路，優(yōu)先選取持續(xù)2小時(shí)可見(jiàn)且有空閑時(shí)隙的境內(nèi)衛(wèi)星與地面站配對(duì)進(jìn)行建鏈。再次選取本周期內(nèi)可見(jiàn)且有空閑時(shí)隙的境內(nèi)衛(wèi)星與地面站配對(duì)進(jìn)行建鏈。如果排列成功，則在可見(jiàn)矩陣中將該配對(duì)進(jìn)行置0。

步驟9：排入境外-境外鏈路，優(yōu)先排入固定可見(jiàn)的衛(wèi)星配對(duì)，其次排僅本周期內(nèi)可見(jiàn)的衛(wèi)星配對(duì)。如果排列成功，則在可見(jiàn)矩陣中將該配對(duì)進(jìn)行置0。

至此，初步規(guī)劃完成，基本構(gòu)成間隔2個(gè)時(shí)隙有境內(nèi)-境外鏈路的拓?fù)淇蚣?，同時(shí)還補(bǔ)充了境外-境外鏈路和星地鏈路。但是該拓?fù)淇蚣苤写嬖谝恍┛臻e時(shí)隙，并不能滿足各項(xiàng)指標(biāo)要求。

2.2 遺傳算法優(yōu)化

本方案采用經(jīng)典遺傳算法對(duì)拓?fù)淇蚣苓M(jìn)行優(yōu)化，遺傳算法是一種模擬生物進(jìn)化規(guī)律適者生存優(yōu)勝劣汰的遺傳機(jī)制來(lái)實(shí)現(xiàn)的一種通用的隨機(jī)搜索方法，過(guò)程介紹如下：

1)種群初始化：

本方案隨機(jī)生成50個(gè)個(gè)體P，構(gòu)成初始群體，每一個(gè)個(gè)體是一個(gè)N×3的矩陣:

(12)

其中:TN×1為時(shí)隙，SN×1為衛(wèi)星1，DN×1為衛(wèi)星2。個(gè)體P的含義為在原有拓?fù)淇蚣艿幕A(chǔ)上，進(jìn)行N次編輯修改，每次修改的含義為另ti時(shí)隙衛(wèi)星si與衛(wèi)星di進(jìn)行建鏈；若si在ti時(shí)隙有建鏈對(duì)象，則進(jìn)行拆鏈處理，同時(shí)將該時(shí)隙下si原建鏈對(duì)象的拓?fù)渲脼?；對(duì)衛(wèi)星di的處理與之相同。

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

2)適應(yīng)度評(píng)估：

本方案采用綜合指標(biāo)評(píng)估準(zhǔn)則，將鏈路空置率、星間不重復(fù)建鏈數(shù)均值，星間幾何精度因子均值，星星地?cái)?shù)據(jù)傳輸時(shí)延納入綜合指標(biāo)，對(duì)指標(biāo)值進(jìn)行了歸一化處理，在此，適應(yīng)度值越小表示越優(yōu)；

(13)

其中：第一項(xiàng)為全局鏈路空置率，E為全局鏈路空置率，意為空閑時(shí)隙占總拓?fù)浔淼陌俜直?，ωe為鏈路空置率權(quán)值系數(shù)；

第二項(xiàng)為星間不重復(fù)建鏈數(shù)均值，Li為衛(wèi)星i的星間不重復(fù)建鏈數(shù)，ωl為星間不重復(fù)建鏈數(shù)均值項(xiàng)的權(quán)值系數(shù)；

第三項(xiàng)為星間幾何精度因子均值項(xiàng)，Pdopi,j為衛(wèi)星i在j時(shí)刻的星間幾何精度因子值，ωp為星間幾何精度因子均值項(xiàng)的權(quán)值系數(shù)；

第四項(xiàng)為星間幾何精度因子最大均值項(xiàng)，ωpmax為星間幾何精度因子最大均值項(xiàng)的權(quán)值系數(shù)；

第五項(xiàng)為星星地?cái)?shù)據(jù)傳輸時(shí)延項(xiàng)，Di.k為衛(wèi)星i在k時(shí)隙要將數(shù)據(jù)傳至地面站或者境內(nèi)衛(wèi)星的傳輸時(shí)延(本文僅統(tǒng)計(jì)時(shí)隙等待時(shí)延)，ωd為星星地?cái)?shù)據(jù)傳輸時(shí)延項(xiàng)的權(quán)值系數(shù)。

以星星地?cái)?shù)據(jù)下傳為例進(jìn)行星星地?cái)?shù)據(jù)傳輸時(shí)延統(tǒng)計(jì)，涉及一層下傳的路徑選擇規(guī)劃，本文在此采用簡(jiǎn)化路由的方案進(jìn)行選擇，直接建鏈的衛(wèi)星配對(duì)之間必然存在路由，境外星從任意一個(gè)時(shí)隙出發(fā)，要將數(shù)據(jù)傳輸至地面，有3種方式：

(1)傳輸至境內(nèi)星，由境內(nèi)衛(wèi)星通過(guò)星地連續(xù)體制鏈路傳至地面站；

(2)傳輸至境內(nèi)星，由境內(nèi)衛(wèi)星通過(guò)星地時(shí)分體制鏈路傳至地面站；

(3)傳輸至境外星，由其他境外星將數(shù)據(jù)轉(zhuǎn)發(fā)至境內(nèi)星，再傳輸至地面站；

由于本方案已經(jīng)預(yù)設(shè)了間隔2個(gè)時(shí)隙的境內(nèi)-境外鏈路，對(duì)于境外星來(lái)說(shuō)，找尋當(dāng)前時(shí)隙之后最近的境內(nèi)星節(jié)點(diǎn)進(jìn)行下傳即可，本文在此基礎(chǔ)上進(jìn)行了增補(bǔ)設(shè)計(jì)，如果連續(xù)3個(gè)時(shí)隙以上沒(méi)有找到下傳時(shí)機(jī)，查找與之建鏈的境外星在該時(shí)隙之后的下一個(gè)時(shí)隙是否是下傳時(shí)機(jī)，如果是，則可以通過(guò)該境外-境外-境內(nèi)鏈路進(jìn)行下傳。

3)選擇操作:通過(guò)個(gè)體適應(yīng)度值從當(dāng)前種群中選擇一部分個(gè)體進(jìn)行接下來(lái)的交叉，突變操作，本文采用錦標(biāo)賽選擇法。每次從50個(gè)個(gè)體中隨機(jī)選取25個(gè)個(gè)體，從25個(gè)個(gè)體中選擇適應(yīng)度函數(shù)值最小的個(gè)體，進(jìn)入下一代，重復(fù)50次，選出50個(gè)個(gè)體作為下一代的父本。

4)交叉操作:從50個(gè)父本中隨機(jī)選擇2個(gè)父本P1和P2，以一定的交叉概率，進(jìn)行交叉操作，在進(jìn)行基因交叉時(shí)，從1～N中隨機(jī)選擇3個(gè)交叉點(diǎn)c1，c2，c3，將3個(gè)交叉點(diǎn)對(duì)應(yīng)的3個(gè)編輯項(xiàng)進(jìn)行交換，將此交叉操作重復(fù)50次，得到50個(gè)子代個(gè)體。

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

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

6) 計(jì)算每個(gè)子代個(gè)體的適應(yīng)度評(píng)估值，并記錄群體極值、全局極值與對(duì)應(yīng)個(gè)體。

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

8) 將全局極值對(duì)應(yīng)的個(gè)體作為編輯要素，對(duì)拓?fù)淇蚣苓M(jìn)行編輯修改，得到最終優(yōu)化后的拓?fù)湟?guī)劃結(jié)果。

3 路由規(guī)劃

在上述拓?fù)湟?guī)劃的前提下進(jìn)行網(wǎng)絡(luò)路由計(jì)算，與傳統(tǒng)網(wǎng)絡(luò)路由不同，時(shí)分體制下的路徑規(guī)劃與節(jié)點(diǎn)的傳輸起始時(shí)刻有關(guān)，以最短時(shí)延原則為例，從源節(jié)點(diǎn)A到目的節(jié)點(diǎn)B從不同的時(shí)隙出發(fā)有不同的最短時(shí)延路徑。此外，在進(jìn)行路徑規(guī)劃時(shí)，還必須考慮星上的跳數(shù)限制。

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

1) 根據(jù)拓?fù)浔砩梢孕l(wèi)星i為根節(jié)點(diǎn)的3級(jí)節(jié)點(diǎn)樹(shù)結(jié)構(gòu)；

2) 對(duì)節(jié)點(diǎn)樹(shù)進(jìn)行遍歷，尋找衛(wèi)星i到衛(wèi)星j之間的所有可達(dá)路徑；

3) 計(jì)算不同出發(fā)時(shí)隙下，所有可達(dá)路徑的傳輸時(shí)延；

4) 選擇最短時(shí)延對(duì)應(yīng)的路徑，時(shí)延相同的情況下，選擇跳數(shù)較小的路徑；

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

6) 重復(fù)1)～5)步，計(jì)算全網(wǎng)任意2個(gè)節(jié)點(diǎn)之間的端到端路由。

4 仿真驗(yàn)證

為驗(yàn)證算法的可用性，在VS2016工程中進(jìn)行了編碼仿真，規(guī)劃時(shí)間為2020-03-15 00∶00∶00～2020-03-15 06∶00∶00，星座構(gòu)成為3GEO+3IGSO+24MEO，Ka地面站2個(gè)，S地面站3個(gè)，拓?fù)浔碇芷? 600 s。

4.1 測(cè)量性能驗(yàn)證

遺傳算法種群大小50，編輯點(diǎn)規(guī)模100，迭代次數(shù)100。

種群迭代過(guò)程中群體適應(yīng)度極值和適應(yīng)度均值變化如圖5所示。

圖5 群體適應(yīng)度極值/均值變化圖

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

最終的拓?fù)湟?guī)劃的適應(yīng)度評(píng)估結(jié)果如表2～4所示。

表2 鏈路空置率

表3 星間不重復(fù)建鏈數(shù)均值

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

可以看出，該優(yōu)化算法對(duì)拓?fù)浔礞溌房罩寐?、星間幾何精度因子均有一定的優(yōu)化效果，空置率提升約3.9%，星間幾何精度因子提升約30%，星星地?cái)?shù)據(jù)下傳最大時(shí)延保持不變，星間不重復(fù)建鏈數(shù)指標(biāo)略有下降，優(yōu)化后拓?fù)浔淼男情g不重復(fù)建鏈數(shù)，星間幾何精度因子均滿足測(cè)量各項(xiàng)指標(biāo)要求。

4.2 數(shù)傳性能驗(yàn)證

軟件對(duì)路由規(guī)劃結(jié)果進(jìn)行了邏輯仿真驗(yàn)證，按照路由表進(jìn)行數(shù)據(jù)傳輸，驗(yàn)證任意兩個(gè)節(jié)點(diǎn)之間不同的出發(fā)時(shí)隙下，數(shù)據(jù)傳輸是否可達(dá)，數(shù)據(jù)傳輸?shù)奶鴶?shù)和數(shù)據(jù)傳輸?shù)臅r(shí)延。統(tǒng)計(jì)結(jié)果如下：

1) 任意兩個(gè)節(jié)點(diǎn)之間數(shù)據(jù)均可達(dá)；

2) 端到端跳數(shù)在5跳以內(nèi)，且各跳數(shù)比例如表5所示。

表5 端到端跳數(shù)比例

圖6 端到端跳數(shù)分布

端到端跳數(shù)在4跳以內(nèi)的占比達(dá)到98.02%。

3)端到端時(shí)延在60 s內(nèi)，且比例如表6所示。

端到端數(shù)據(jù)傳輸時(shí)延在30s之內(nèi)的占比達(dá)到97.72%。

4)星星地?cái)?shù)據(jù)下傳時(shí)延

按照本文2.2節(jié)中描述的星星地?cái)?shù)據(jù)下傳時(shí)機(jī)選取方案，對(duì)拓?fù)浔磉M(jìn)行了邏輯傳輸仿真，統(tǒng)計(jì)結(jié)果如表7所示。

表6 端到端時(shí)延比例

圖7 端到端時(shí)延分布

表7 星星地?cái)?shù)據(jù)下傳傳輸時(shí)延 時(shí)隙

從表中可以看出：星星地?cái)?shù)據(jù)下傳傳輸最大時(shí)延保持3個(gè)時(shí)隙不變，平均時(shí)延有所減少，有一定的優(yōu)化效果。

仿真結(jié)果表明，采用本文提出的啟發(fā)式遺傳算法對(duì)拓?fù)湟?guī)劃進(jìn)行優(yōu)化，并且采用最短時(shí)延原則的路由計(jì)算方法，其星間數(shù)據(jù)傳輸、星星地?cái)?shù)據(jù)下傳過(guò)程均滿足業(yè)務(wù)數(shù)據(jù)的傳輸跳數(shù)與傳輸時(shí)延要求。

5 結(jié)束語(yǔ)

本文針對(duì)時(shí)分體制導(dǎo)航衛(wèi)星星座的測(cè)量與數(shù)據(jù)傳輸要求，分析了網(wǎng)絡(luò)規(guī)劃的約束條件和業(yè)務(wù)要求，提出一種基于啟發(fā)式遺傳算法的網(wǎng)絡(luò)拓?fù)鋬?yōu)化設(shè)計(jì)方法，首先通過(guò)仿真分析制定了規(guī)劃的基本原則，給出一個(gè)能滿足大部分需求的拓?fù)淇蚣?，再以此作為初值，利用遺傳算法對(duì)拓?fù)溥M(jìn)行了優(yōu)化，在此基礎(chǔ)上采用了分時(shí)最短時(shí)延的路由算法，并進(jìn)行了仿真驗(yàn)證，結(jié)果表明，拓?fù)渎酚梢?guī)劃結(jié)果能滿足導(dǎo)航星座的常規(guī)業(yè)務(wù)。本文能為解決導(dǎo)航星座星間網(wǎng)絡(luò)的復(fù)雜運(yùn)行管理提供一種解決問(wèn)題的思路，仿真驗(yàn)證過(guò)程未能將星上真實(shí)的處理過(guò)程納入考慮，與實(shí)際工程尚有一定的偏差。