程竟爽 何善寶 林益明 謝軍

（北京空間飛行器總體設(shè)計(jì)部，北京 100094）

1 引言

利用星間鏈路，導(dǎo)航星座可以支持星地聯(lián)合定軌與時(shí)間同步、全球星座實(shí)時(shí)測(cè)控管理，并實(shí)現(xiàn)導(dǎo)航星座自主導(dǎo)航等功能，提高了地面對(duì)系統(tǒng)的管理能力，增強(qiáng)了系統(tǒng)的自主運(yùn)行能力［1］。導(dǎo)航星座在運(yùn)行過程中，衛(wèi)星節(jié)點(diǎn)及星間鏈路設(shè)備會(huì)由于故障或維護(hù)而出現(xiàn)失效情況，導(dǎo)致星座與星間網(wǎng)絡(luò)拓?fù)湓械男阅芟陆?，須?duì)其進(jìn)行重構(gòu)。如何優(yōu)化設(shè)計(jì)重構(gòu)后的星座構(gòu)型與網(wǎng)絡(luò)拓?fù)?，使星座綜合性能得到最優(yōu)恢復(fù)，而重構(gòu)風(fēng)險(xiǎn)則處于可接受的范圍內(nèi)，是一個(gè)需要研究的問題。

目前，針對(duì)星座的重構(gòu)研究多集中在無星間鏈路的星座構(gòu)型設(shè)計(jì)［2-4］上，對(duì)于具有星間鏈路的星座重構(gòu)的研究較少。文獻(xiàn)［5］研究了具有星間鏈路的星座設(shè)計(jì)問題，考慮了星間鏈路的性能因素，但未對(duì)網(wǎng)絡(luò)拓?fù)溥M(jìn)行優(yōu)化設(shè)計(jì)。文獻(xiàn)［6］研究了具有星間鏈路的通信星座重構(gòu)問題，提出了“補(bǔ)網(wǎng)”的基本策略，但僅考慮到網(wǎng)絡(luò)的連通性，與導(dǎo)航星座網(wǎng)絡(luò)的設(shè)計(jì)目標(biāo)有較大差別。

本文提出了一種基于遺傳算法的優(yōu)化設(shè)計(jì)方法。將星座構(gòu)型重構(gòu)設(shè)計(jì)與星間網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)統(tǒng)一考慮，以星座導(dǎo)航服務(wù)性能、網(wǎng)絡(luò)測(cè)距與通信性能，以及星座與網(wǎng)絡(luò)的重構(gòu)風(fēng)險(xiǎn)程度為設(shè)計(jì)指標(biāo)，建立了導(dǎo)航星座的綜合重構(gòu)優(yōu)化設(shè)計(jì)模型，并以遺傳算法為基本手段實(shí)現(xiàn)綜合重構(gòu)優(yōu)化設(shè)計(jì)。仿真分析表明，重構(gòu)后網(wǎng)絡(luò)性能得到一定程度的改善，滿足重構(gòu)策略的期望。

2 具有星間鏈路的導(dǎo)航星座重構(gòu)優(yōu)化設(shè)計(jì)問題

具有星間鏈路的導(dǎo)航星座重構(gòu)優(yōu)化設(shè)計(jì)問題，可以表述為尋找重構(gòu)后的衛(wèi)星軌道參數(shù)和各星之間的網(wǎng)絡(luò)拓?fù)?，使得形成的星座?gòu)型和星間網(wǎng)絡(luò)具有良好的綜合性能。本文只考慮衛(wèi)星在同一軌道面內(nèi)軌道機(jī)動(dòng)實(shí)現(xiàn)星座重構(gòu)，因此只將各衛(wèi)星的相位角集合C作為設(shè)計(jì)變量。星間網(wǎng)絡(luò)可用包含衛(wèi)星節(jié)點(diǎn)集合V和星間鏈路集合E的圖G（V，E）描述，其拓?fù)淇捎脠D的鄰接矩陣U表示［7］，uij為U中的元素，表示節(jié)點(diǎn)i、j間的連接關(guān)系，若i、j建立雙向鏈路，則uij＝uji＝1。

2．1 設(shè)計(jì)目標(biāo)

具有星間鏈路的導(dǎo)航星座重構(gòu)優(yōu)化設(shè)計(jì)目標(biāo)，是盡可能地恢復(fù)星座及星間鏈路性能，同時(shí)其重構(gòu)的風(fēng)險(xiǎn)最小，設(shè)計(jì)目標(biāo)包括性能目標(biāo)函數(shù)和重構(gòu)風(fēng)險(xiǎn)函數(shù)。

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

導(dǎo)航星座的地面定位性能常用對(duì)地位置幾何精度因子（Position Dilution of Precision，PDOP）值來描述。記對(duì)地PDOP值為ρ，可采用ρ＜6的區(qū)域百分比（f1）作為定位性能指標(biāo)。即

式中：A為總的服務(wù)區(qū)域面積；Ⅰ為5°仰角條件下滿足ρ＜6約束的區(qū)域個(gè)數(shù)，Ak為上述區(qū)域中第k個(gè)區(qū)域的面積。

與通信星座不同，導(dǎo)航星座的星間網(wǎng)絡(luò)承擔(dān)了測(cè)距和通信的雙重功能［8］，其性能目標(biāo)函數(shù)包括以下幾個(gè)方面：

（1）網(wǎng)絡(luò)測(cè)距性能的指標(biāo)之一是網(wǎng)絡(luò)測(cè)距量數(shù)目（f2），指一個(gè)定軌周期內(nèi)網(wǎng)絡(luò)包含的星間測(cè)距量總數(shù)目。若整個(gè)定軌周期中網(wǎng)絡(luò)拓?fù)錇榉€(wěn)態(tài)拓?fù)洌瑒t測(cè)距量數(shù)目可以由網(wǎng)絡(luò)的鏈路數(shù)目描述。即

式中：n為星座中衛(wèi)星節(jié)點(diǎn)數(shù)目；uij表示節(jié)點(diǎn)i，j之間的連接關(guān)系。

（2）網(wǎng)絡(luò)測(cè)距性能的另一方面是網(wǎng)絡(luò)的測(cè)距構(gòu)型性能，可由星間PDOP值來描述。記節(jié)點(diǎn)的星間PDOP值為σ，可用網(wǎng)絡(luò)各節(jié)點(diǎn)σ＜3的平均時(shí)間百分比（f3）作為網(wǎng)絡(luò)測(cè)距性能指標(biāo)。該指標(biāo)是指一個(gè)定軌周期內(nèi)網(wǎng)絡(luò)各節(jié)點(diǎn)σ＜3的時(shí)間占定軌周期T的時(shí)間百分比的平均值，即

式中：tσi＜3為節(jié)點(diǎn)i在整個(gè)定軌周期T內(nèi)滿足σ＜3的總時(shí)間。

（3）網(wǎng)絡(luò)通信性能可由網(wǎng)絡(luò)平均距離來描述，指一個(gè)周期內(nèi)網(wǎng)絡(luò)各節(jié)點(diǎn)間最小路徑長(zhǎng)度的平均值。本文將其簡(jiǎn)化為各節(jié)點(diǎn)間的平均最小跳數(shù)（f4），即

式中：N為網(wǎng)絡(luò)各節(jié)點(diǎn)間存在的最短路徑總數(shù)；dij為節(jié)點(diǎn)i、j間最小跳數(shù)。

2）重構(gòu)風(fēng)險(xiǎn)函數(shù)

星座及星間網(wǎng)絡(luò)的重構(gòu)風(fēng)險(xiǎn)目標(biāo)函數(shù)，包括參與軌道機(jī)動(dòng)的衛(wèi)星數(shù)目f5和重構(gòu)前后的鏈路變化率f6，反映了星座及星間網(wǎng)絡(luò)的重構(gòu)風(fēng)險(xiǎn)。

將各目標(biāo)函數(shù)fi表述為歸一化最大值形式f′i，利用相應(yīng)權(quán)重因子Wi加權(quán)為單一目標(biāo)F，即

2．2 數(shù)學(xué)模型

具有星間鏈路的導(dǎo)航星座綜合重構(gòu)優(yōu)化設(shè)計(jì)問題描述如下：

式中：ci，cj分別表示節(jié)點(diǎn)i、j所處軌道面內(nèi)的相位，Pi、Pj為節(jié)點(diǎn)i、j所處軌道面編號(hào)。式（7）為星座構(gòu)型約束，表明星座中各衛(wèi)星之間應(yīng)避免碰撞風(fēng)險(xiǎn)；式（8）為鏈路的可建性約束，表明i、j之間建立鏈路須滿足星間可連性eij；式（9）為網(wǎng)絡(luò)連通性約束，表明各節(jié)點(diǎn)間至少存在一條連通路徑；式（10）為網(wǎng)絡(luò)節(jié)點(diǎn)度約束和網(wǎng)絡(luò)2-連接約束［9］，表明節(jié)點(diǎn)i建立的鏈路數(shù)目不超過天線數(shù)目ki，且任意節(jié)點(diǎn)的鏈路數(shù)目不少于2，以保證網(wǎng)絡(luò)的穩(wěn)健性。

3 星座重構(gòu)優(yōu)化設(shè)計(jì)的遺傳算法實(shí)現(xiàn)

3．1 整體算法

如圖1所示，星間網(wǎng)絡(luò)重構(gòu)優(yōu)化設(shè)計(jì)的整體算法流程如下：①設(shè)定星座的故障模式；②產(chǎn)生一個(gè)初始化的星座構(gòu)型染色體群；③針對(duì)染色體群中每一個(gè)染色體代表的星座構(gòu)型，優(yōu)化設(shè)計(jì)網(wǎng)絡(luò)拓?fù)?；④根?jù)星座的服務(wù)性能與該構(gòu)型下最優(yōu)網(wǎng)絡(luò)的拓?fù)湫阅?，?jì)算綜合適應(yīng)度；⑤執(zhí)行染色體群的選擇、交叉、變異操作。迭代執(zhí)行上述遺傳學(xué)操作，直至迭代次數(shù)達(dá)到一定次數(shù)時(shí)終止，最終得到最佳的子星座構(gòu)型與網(wǎng)絡(luò)拓?fù)洹?/p>

圖1 具有星間鏈路的導(dǎo)航星座重構(gòu)優(yōu)化設(shè)計(jì)流程Fig．1 Flow chart of reconfiguration optimization of navigation constellation with inter-satellite links

3．2 網(wǎng)絡(luò)拓?fù)鋬?yōu)化設(shè)計(jì)

上述算法流程中，涉及到網(wǎng)絡(luò)拓?fù)涞膬?yōu)化設(shè)計(jì)。網(wǎng)絡(luò)拓?fù)鋬?yōu)化的算法流程如下：

（1）根據(jù)星座構(gòu)型，更新星間可見性等網(wǎng)絡(luò)拓?fù)浼s束。

（2）初始化網(wǎng)絡(luò)拓?fù)淙旧w種群。在滿足可連性約束前提下，首先利用最小生成樹算法生成網(wǎng)絡(luò)的最小支撐樹，以確保網(wǎng)絡(luò)的連通性；檢驗(yàn)網(wǎng)絡(luò)是否滿足節(jié)點(diǎn)度約束和2-連接約束，如果不滿足，則利用相應(yīng)的修補(bǔ)算子進(jìn)行修補(bǔ)操作；最后對(duì)網(wǎng)絡(luò)補(bǔ)充新鏈路直至接近飽和狀態(tài)，以保證鏈路數(shù)目的近似最大化。

（3）選擇、交叉和變異操作。其中變異通過“分支-交叉”操作實(shí)現(xiàn)，以減少非可行解的產(chǎn)生。交叉變異操作需要經(jīng)過鏈路可連性約束的判斷，若不滿足約束，則需要重新執(zhí)行操作。

（4）對(duì)染色體個(gè)體進(jìn)行約束條件的判斷。若違反約束條件，還需要進(jìn)行相應(yīng)的修補(bǔ)操作。

（5）采取精英保留策略，使最優(yōu)個(gè)體保留至下一代群體中。反復(fù)執(zhí)行上述操作直至迭代達(dá)到一定次數(shù)。

其中，步驟（2）與步驟（4）涉及到網(wǎng)絡(luò)拓?fù)涞男扪a(bǔ)操作，如圖2所示。

圖2 網(wǎng)絡(luò)拓?fù)湫扪a(bǔ)操作示意圖Fig．2 Illustration of network topology repair operation

針對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)度約束的修補(bǔ)操作步驟包括：找出所有違反約束的節(jié)點(diǎn)集合；隨機(jī)選擇該集合中的任一節(jié)點(diǎn)，刪除與之關(guān)聯(lián)的一條邊；判斷是否違反連通性約束，若違反約束，則根據(jù)各節(jié)點(diǎn)度與鏈路可建性約束隨機(jī)添加一條新邊，使網(wǎng)絡(luò)連通；更新節(jié)點(diǎn)度后，對(duì)其他節(jié)點(diǎn)重復(fù)上述操作直至該集合為空集。

針對(duì)網(wǎng)絡(luò)2-連接性約束的修補(bǔ)操作步驟包括：找出所有違反約束的節(jié)點(diǎn)集合；選擇該集合中的任一節(jié)點(diǎn)，尋找可與之建立鏈路且節(jié)點(diǎn)度不小于2的節(jié)點(diǎn)集合，隨機(jī)選擇其中一點(diǎn)并刪除與之關(guān)聯(lián)的一條邊，該邊刪除的前提是對(duì)應(yīng)端點(diǎn)的節(jié)點(diǎn)度大于2；建立新的鏈路；更新節(jié)點(diǎn)度后，對(duì)其他節(jié)點(diǎn)重復(fù)上述操作直至該集合為空集。

4 星座重構(gòu)設(shè)計(jì)算例

4．1 仿真環(huán)境

本文假設(shè)全球?qū)Ш叫亲捎肳alker 24／3／2構(gòu)型的星座，軌道高度20 200km，偏心率為0，軌道傾角55°，各軌道面升交點(diǎn)赤經(jīng)相隔120°。全配置星座的星間網(wǎng)絡(luò)采用類似網(wǎng)狀的星間鏈路［10］，每顆衛(wèi)星最多可建立3條鏈路，分別與同軌相鄰兩顆衛(wèi)星建立同軌鏈路，與異軌道面一顆相鄰衛(wèi)星建立異軌鏈路。整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)如圖3所示。

圖3 網(wǎng)狀星間網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)Fig．3 Topology of mesh-shaped satellite network

根據(jù)對(duì)導(dǎo)航星座及網(wǎng)絡(luò)可靠性的初步分析，出現(xiàn)3顆以下衛(wèi)星故障、3條以下鏈路故障的概率較大。設(shè)定故障模式為3 顆衛(wèi)星故障和3 副天線故障，根據(jù)失效性能分析，當(dāng)編號(hào)為11、25、32衛(wèi)星故障時(shí)導(dǎo)航服務(wù)性能最為惡劣，故選取上述3顆衛(wèi)星為故障衛(wèi)星。故障天線編號(hào)為18、28、35衛(wèi)星的天線，故障鏈路編號(hào)為（17，18），（27，28），（26，35）。此時(shí)，編號(hào)為18、26和27的三顆衛(wèi)星與主衛(wèi)星網(wǎng)絡(luò)的鏈路均中斷，3顆衛(wèi)星脫離網(wǎng)絡(luò)形成一個(gè)孤島，是一種較為惡劣的故障工況。

4．2 結(jié)果分析與討論

優(yōu)化算法的參數(shù)設(shè)置為：種群規(guī)模Np＝100，最大迭代次數(shù)M＝100，交叉率pc＝0．6，變異率pm＝0．1。各優(yōu)化目標(biāo)的權(quán)重因子w＝［1／6，1／6，1／6，1／6，1／6，1／6］，反映了對(duì)星座與星間網(wǎng)絡(luò)性能的綜合優(yōu)化設(shè)計(jì)。經(jīng)過優(yōu)化后得到的最佳星座重構(gòu)方案為：編號(hào)為23的衛(wèi)星由120°機(jī)動(dòng)至216°，編號(hào)為35的衛(wèi)星由240°機(jī)動(dòng)至114°，此時(shí)ρ＜6的區(qū)域百分比提高到100%，重構(gòu)后的對(duì)地PDOP峰值分布如圖4所示。

圖4 重構(gòu)后星座對(duì)地PDOP峰值分布Fig．4 Distribution of maximum PDOP after reconfiguration

利用本文方法得到最優(yōu)重構(gòu)拓?fù)?，重?gòu)前后的網(wǎng)絡(luò)拓?fù)淙鐖D5所示。

圖5 重構(gòu)前后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)比較Fig．5 Comparison of network topology before and after reconfiguration

網(wǎng)絡(luò)拓?fù)渲貥?gòu)前后的性能如表1所示。

表1 混合故障下的星座與網(wǎng)絡(luò)拓?fù)渲貥?gòu)前后性能比較Table 1 Results of constellation reconfiguration in case of mixed failure

由表2可以看出，經(jīng)綜合優(yōu)化重構(gòu)設(shè)計(jì)后，星座的ρ＜6區(qū)域百分比由48．18%提高到100%。重構(gòu)后的網(wǎng)絡(luò)拓?fù)涫乖缺桓綦x的衛(wèi)星重新接入網(wǎng)絡(luò)，恢復(fù)了網(wǎng)絡(luò)的連通性，網(wǎng)絡(luò)鏈路數(shù)從27條增加到31條，提高了σ＜3時(shí)間百分比，縮短了通信時(shí)延，從而改善了網(wǎng)絡(luò)的測(cè)距與通信性能。同時(shí)，只進(jìn)行了5條鏈路的切換，降低了鏈路切換的風(fēng)險(xiǎn)。星座和網(wǎng)絡(luò)拓?fù)湫阅芡瑫r(shí)得到優(yōu)化，說明了此方法的有效性。

與無星間鏈路的星座重構(gòu)設(shè)計(jì)結(jié)果［2］相比，本方法得到的子星座構(gòu)型的ρ＜6區(qū)域百分比性能，同樣達(dá)到了100%，這說明此重構(gòu)方案收斂到眾多無星間鏈路的星座重構(gòu)方案其中之一。造成這種現(xiàn)象的原因是無星間鏈路的星座重構(gòu)設(shè)計(jì)僅考慮星座性能的優(yōu)化，可選方案較多；而有星間鏈路的設(shè)計(jì)則需要綜合考慮星座與星間網(wǎng)絡(luò)的性能，其星座的優(yōu)化空間受到一定的限制，因而導(dǎo)致可選方案收斂。

5 結(jié)束語

本文針對(duì)具有星間鏈路的導(dǎo)航星座重構(gòu)優(yōu)化設(shè)計(jì)問題，建立了相應(yīng)的數(shù)學(xué)模型，并提出基于修改的遺傳算法處理該聯(lián)合設(shè)計(jì)問題，以得到重構(gòu)后的最佳星座構(gòu)型與星間網(wǎng)絡(luò)拓?fù)?。利用該方法，針?duì)Walker 24／3／2構(gòu)型星座在3星故障與3條鏈路故障的混合故障下進(jìn)行了優(yōu)化設(shè)計(jì)。對(duì)重構(gòu)前后的星座與網(wǎng)絡(luò)拓?fù)湫阅鼙容^可以看出，該方法能夠有效恢復(fù)星座與星間網(wǎng)絡(luò)的性能，恢復(fù)星座的服務(wù)性能與網(wǎng)絡(luò)的連通性，改善網(wǎng)絡(luò)的測(cè)距與通信性能，而且實(shí)現(xiàn)重構(gòu)的衛(wèi)星數(shù)目和鏈路切換數(shù)目較低，因此，這是一種有效可行的設(shè)計(jì)方法。

（References）

［1］林益明，何善寶，鄭晉軍，等．全球?qū)Ш叫亲情g鏈路技術(shù)發(fā)展建議［J］．航天器工程，2010，19（6）：1-7

Lin Yiming，He Shanbao，Zheng Jinjun，et al．Development recommendation of inter-satellite links in GNSS［J］．Spacecraft Engineering，2010，19（6）：1-7（in Chinese）

［2］胡偉，王劼．基于遺傳算法的全球?qū)Ш叫亲貥?gòu)研究［J］．宇航學(xué)報(bào)，29（6），2008：1819-1823

Hu Wei，Wang Jie．The research on global navigation constellation reconfiguration based on genetic algorithm［J］．Journal of Astronautics，2008，29（6）：1819-1823（in Chinese）

［3］Weck O de，Neufville R de，Chaize M．Staged deployment of communications satellite constellations in low Earth orbit［J］．Journal of Aerospace Computing，Information and Communication，2004，1（3）：119-136

［4］Ferringer M P，Spencer D B，Reed P．Many-objective reconfiguration of operational satellite constellations with the large-cluster epsilon non-dominated sorting genetic algorithm-II［C］／／Proceedings of IEEE Congress on Evolutionary Computation．Throndheim，Norway：IEEE，2009：340-349

［5］張艷，張育林．具有星間鏈路的星座相位設(shè)計(jì)［J］．宇航學(xué)報(bào)，2004，25（6）：669-689

Zhang Yan，Zhang Yulin．Phase design of constellation with inter-satellite links［J］．Journal of Astronautics，25（6），2004：669-689（in Chinese）

［6］Chen Xiaoyan，Han Chao．Reconfiguration ofcommunications constellation with ISLs：Fix the net［C］／／Proceedings of the International Conference on Consumer Electronics，Communications and Networks．Xianning，China：IEEE，2011：1540-1543

［7］徐俊明．圖論及其應(yīng)用［M］．合肥：中國科學(xué)技術(shù)大學(xué)出版社，2010

Xu Junming．Graph theory with applications［M］．Hefei：Press of University of Science and Technology of China，2010（in Chinese）

［8］石磊玉，向?yàn)?，唐小妹．一種兼顧衛(wèi)星導(dǎo)航系統(tǒng)星間觀測(cè)及通信的鏈路分配算法［J］．宇航學(xué)報(bào)，32（9），2011：1971-1977

Shi Leiyu，Xiang Wei，Tang Xiaomei．A link assignment algorithm applicable to crosslink ranging and data exchange for satellite navigation system［J］．Journal of Astronautics，32（9），2011：1971-1977（in Chinese）

［9］玄光男，程潤偉．遺傳算法與工程優(yōu)化［M］．于歆杰，周根貴，譯．北京：清華大學(xué)出版社，2004：148-160

Gen Mitsuo，Chen Runwei．Genetic algorithms and engineering optimization［M］．Yu Xinjie，Zhou Gengui，translated．Beijing：Tsinghua University Press，2004：148-160（in Chinese）

［10］Barnhart C M，Ziemer R E．Topological analysis of satellite-based distributed sensor networks［J］．IEEE Transactions on Systems， Man，and Cybernetics，1991，21（5）：1060-1070