潘成勝，行貴軒,*，戚耀文，楊力

1. 大連大學(xué) 信息工程學(xué)院，大連 116622

2. 大連大學(xué) 通信與網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室，大連 116622

3. 南京理工大學(xué) 自動(dòng)化學(xué)院，南京 210094

隨著“空天地一體化”進(jìn)程的推進(jìn)，空間信息網(wǎng)絡(luò)(Space Information Network，SIN)在信息的傳輸、獲取和分發(fā)任務(wù)中起著極其重要的作用。與地面網(wǎng)絡(luò)不同，衛(wèi)星網(wǎng)絡(luò)中通信節(jié)點(diǎn)高速運(yùn)動(dòng)，通信鏈路頻繁斷開，信息傳輸?shù)臅r(shí)延大、誤碼率高[1]，嚴(yán)重影響網(wǎng)絡(luò)拓?fù)涞姆€(wěn)定性。而穩(wěn)定的衛(wèi)星網(wǎng)絡(luò)拓?fù)洳粌H是實(shí)現(xiàn)網(wǎng)絡(luò)信息交換和資源共享的基礎(chǔ)，而且也是實(shí)現(xiàn)網(wǎng)絡(luò)管理、協(xié)議設(shè)計(jì)優(yōu)化、安全控制等的前提。因此，設(shè)計(jì)可靠的衛(wèi)星網(wǎng)絡(luò)拓?fù)渌惴ㄖ陵P(guān)重要。

衛(wèi)星節(jié)點(diǎn)本身是一個(gè)多狀態(tài)系統(tǒng)。多狀態(tài)系統(tǒng)的定義及可靠性概念在20世紀(jì)70年代首次被提出[2-5]，實(shí)際上，衛(wèi)星在軌運(yùn)行期間，由于零部件老化，負(fù)載及儲(chǔ)能損耗等，衛(wèi)星系統(tǒng)性能逐漸劣化，系統(tǒng)從正常工作到完全失效需要經(jīng)歷一系列中間過(guò)渡狀態(tài)，這些不同狀態(tài)導(dǎo)致了衛(wèi)星實(shí)際上的工作性能不同，即衛(wèi)星工作中具有多態(tài)性。

傳統(tǒng)的衛(wèi)星網(wǎng)絡(luò)拓?fù)渖伤惴ù蠖鄡H考慮衛(wèi)星網(wǎng)絡(luò)的空間特性，即看作分布在近地空間的一般節(jié)點(diǎn)，石磊玉等[6]針對(duì)如何有效分配有限波束來(lái)建立星間鏈路的問(wèn)題，提出了一種基于貪婪算法的分配策略，在保證衛(wèi)星觀測(cè)數(shù)量最大化的前提下，以降低整網(wǎng)通信代價(jià)為優(yōu)化目標(biāo)，實(shí)現(xiàn)鏈路分配，但貪婪算法在該處的收斂性不佳。Chu和Chen[7]提出了一種基于北斗導(dǎo)航系統(tǒng)的時(shí)分拓?fù)渖伤惴?，從拓?fù)浣嵌葘?shí)現(xiàn)源節(jié)點(diǎn)到端節(jié)點(diǎn)數(shù)據(jù)的快速傳輸。Ma等[8]提出一種新的低軌-中軌(Low Earth Orbit-Medium Earth Orbit,LEO-MEO)雙層衛(wèi)星網(wǎng)絡(luò)拓?fù)淠Ｐ?，并考慮了極地邊界的影響，但該模型工程上難以實(shí)現(xiàn)。Wang等[9]提出了一種綜合權(quán)重的策略對(duì)衛(wèi)星網(wǎng)絡(luò)建鏈，減少了時(shí)延，擁塞率和鏈路切換。董明佶等[10]設(shè)計(jì)了一種改進(jìn)的模擬退火算法，以空間位置精度因子(Position Dilution of Precision，PDOP)和網(wǎng)絡(luò)時(shí)延等為優(yōu)化目標(biāo)，生成衛(wèi)星激光星間鏈路拓?fù)?，但是針?duì)激光鏈路，與微波鏈路不同。

上述算法均未考慮衛(wèi)星節(jié)點(diǎn)的多狀態(tài)，僅考慮衛(wèi)星節(jié)點(diǎn)位置等因素，當(dāng)某節(jié)點(diǎn)狀態(tài)不佳時(shí)，而不改變?cè)型負(fù)洌瑢?dǎo)致網(wǎng)絡(luò)時(shí)延增大等問(wèn)題。本文考慮衛(wèi)星系統(tǒng)的多狀態(tài)特點(diǎn)，利用現(xiàn)有的衛(wèi)星星座，以連接度和可視距離等為約束條件，針對(duì)衛(wèi)星網(wǎng)絡(luò)高動(dòng)態(tài)性，以鏈路平均端到端時(shí)延和最大端到端時(shí)延為優(yōu)化目標(biāo)，設(shè)計(jì)了一種改進(jìn)的多目標(biāo)模擬退火(Improved Multi-Objective Simulated Annealing，IMOSA)算法進(jìn)行拓?fù)渖?，使該算法在考慮衛(wèi)星多狀態(tài)的情況下，對(duì)衛(wèi)星拓?fù)渚哂休^好的優(yōu)化效果，得到全局最優(yōu)拓?fù)浣Y(jié)構(gòu)的近似解，并證明了生成的衛(wèi)星網(wǎng)絡(luò)拓?fù)涞目煽啃院涂箽浴?/p>

1 衛(wèi)星系統(tǒng)的多狀態(tài)

隨著衛(wèi)星的長(zhǎng)時(shí)間使用，將會(huì)有電阻、電容發(fā)生老化，磁盤機(jī)械磨損，故障率提升等現(xiàn)象，并且當(dāng)衛(wèi)星節(jié)點(diǎn)數(shù)據(jù)并發(fā)量過(guò)大，導(dǎo)致CPU和存儲(chǔ)讀寫繁忙，都會(huì)導(dǎo)致處理能力下降，讀取數(shù)據(jù)速度變慢等問(wèn)題。本文依據(jù)衛(wèi)星處理能力將其劃分為不同的狀態(tài)等級(jí)，衛(wèi)星在每一刻的狀態(tài)對(duì)應(yīng)一個(gè)確定的狀態(tài)等級(jí)，狀態(tài)等級(jí)越低，誤碼率越高，處理能力越差，越容易出現(xiàn)故障，從而導(dǎo)致處理時(shí)延和排隊(duì)時(shí)延增加，再加上由于星間距離產(chǎn)生的大傳播時(shí)延，使得整體時(shí)延變大。

假設(shè)衛(wèi)星狀態(tài)等級(jí)集合為g={0,1,…,m}。仿照實(shí)際情況，假設(shè)衛(wèi)星性能水平服從一定的概率分布，狀態(tài)最佳的衛(wèi)星數(shù)量最多，一定比例出現(xiàn)狀態(tài)較差的衛(wèi)星。不同狀態(tài)的衛(wèi)星發(fā)送時(shí)延、處理時(shí)延和排隊(duì)時(shí)延之和不同，當(dāng)衛(wèi)星處于狀態(tài)R∈ {0,1,…,m}時(shí)，其發(fā)送時(shí)延、處理時(shí)延和排隊(duì)時(shí)延之和t分別滿足范圍t∈{[ti,ti+1),[ti-1,ti)，…,[ti-m,ti-m+1)}，即存在映射關(guān)系。例如本文取0,1,2這3個(gè)狀態(tài)：狀態(tài)2，時(shí)延t∈[0,20)最小；狀態(tài)1，時(shí)延t∈[20,100)；狀態(tài)0，t∈[100,∞)最大，衛(wèi)星狀態(tài)最差。

2 衛(wèi)星網(wǎng)絡(luò)模型

2.1 衛(wèi)星網(wǎng)絡(luò)拓?fù)淠Ｐ?/h3>

星間鏈路拓?fù)鋵?shí)際上是一個(gè)各邊權(quán)值為星間距離的無(wú)向圖[8-10]。描述為G(S,E)，其中；S={s1,s2,…，sn}為n顆衛(wèi)星的有限節(jié)點(diǎn)集，表示網(wǎng)絡(luò)中衛(wèi)星節(jié)點(diǎn)；E為有限邊集，表示網(wǎng)絡(luò)中衛(wèi)星間的鏈路。通常用矩陣表示圖，如建立n×n的矩陣A，當(dāng)衛(wèi)星si和衛(wèi)星sj之間連通時(shí)，aij=1，否則aij=0，當(dāng)i=j時(shí)aij=0，其中i,j=1,2,…,n。稱A為衛(wèi)星網(wǎng)絡(luò)的鄰接矩陣，其表達(dá)式為

(1)

設(shè)矩陣V為衛(wèi)星網(wǎng)絡(luò)的可視矩陣，表示衛(wèi)星由于地球的遮擋，呈現(xiàn)可視或不可視狀態(tài)的矩陣。當(dāng)衛(wèi)星si和衛(wèi)星sj之間可視時(shí)，vij=1，否則，vij=0。其表達(dá)形式與矩陣A類似。由于衛(wèi)星在軌運(yùn)行時(shí)相互會(huì)被地球遮擋，因而2顆衛(wèi)星之間的鏈路長(zhǎng)度存在一個(gè)滿足可視條件的最大值。假設(shè)Hi、Hj分別表示衛(wèi)星si、sj的軌道高度；Rd為地球半徑，ξ為2顆衛(wèi)星與地心形成的夾角。此時(shí)dmax為衛(wèi)星si、sj可視的最大鏈路長(zhǎng)度，即

(2)

設(shè)dij為2顆衛(wèi)星之間的實(shí)際距離，其計(jì)算公式為

(3)

式中：

X*=H[cosmcos(Ω-ΩG)-

sinmsin(Ω-ΩG)cosα]

(4)

Y*=H[cosmsin(Ω-ΩG)-

sinmcos(Ω-ΩG)cosα]

(5)

Z*=H(sinmsinα)

(6)

m=ma+n0(t-t0)

(7)

ΩG=ωe(t-t0)

(8)

式中：*=i,j；ma為衛(wèi)星真近地點(diǎn)角；n0為線速度；ωe為地球自轉(zhuǎn)角速度；Ω為衛(wèi)星升交點(diǎn)赤經(jīng)，α為衛(wèi)星軌道傾角，X、Y、Z分別為單顆衛(wèi)星的地固坐標(biāo)系。該坐標(biāo)系的原點(diǎn)為地心，XOY平面和地球赤道平面重合，OX軸與格林威治子午線方向一致，OZ軸與地球的極軸重合。若不考慮其他天體和人造衛(wèi)星對(duì)衛(wèi)星的影響，由式(3)～式(7) 得到星間距離dij。當(dāng)dij≤dmax時(shí)，衛(wèi)星可視，vij=1，否則為不可視，vij=0?？梢曅耘袛嗍疽鈭D如圖1所示。

圖1 衛(wèi)星可視性判斷示意圖

2.2 拓?fù)渲芷谀Ｐ?/h3>

衛(wèi)星在軌道上的相對(duì)運(yùn)動(dòng)使得互相之間的可視性隨時(shí)間變化，為了減少這種由拓?fù)鋭?dòng)態(tài)性引起的拓?fù)渥兓膹?fù)雜程度，本文將衛(wèi)星星座周期長(zhǎng)度T分成N個(gè)時(shí)間片[11-12]。這樣時(shí)變的可視性衛(wèi)星周期就轉(zhuǎn)化為一系列拓?fù)涔潭ǖ臅r(shí)間片，而在此基礎(chǔ)上設(shè)計(jì)算法就能以每個(gè)時(shí)間片作為計(jì)算對(duì)象。

在每個(gè)時(shí)間片內(nèi)，衛(wèi)星拓?fù)洳蛔?，因此也稱為拓?fù)淇煺铡＿@種方法將周期T分成如下N個(gè)時(shí)間片：[t0=0,t1],[t1,t2],[t2,t3],…,[tN-1,tN=T]，在新時(shí)間片開始處，存在鏈路交換時(shí)間texch，用來(lái)完成從上一個(gè)拓?fù)淇煺战粨Q鏈路后生成下一個(gè)拓?fù)淇煺?，時(shí)間片分割示意如圖2所示，其中Pi(i=1,2,…,N)為周期。

以上星座時(shí)間片的切換，由地面站配合完成。地面站分為主控站、監(jiān)測(cè)站和注入站，主控站同時(shí)也是監(jiān)測(cè)站[13]。監(jiān)測(cè)站跟蹤監(jiān)控衛(wèi)星狀態(tài)，主控站依據(jù)已知星歷和監(jiān)測(cè)站反饋的信息運(yùn)算各個(gè)時(shí)間片的拓?fù)浜托拚齾?shù)，轉(zhuǎn)換為每顆衛(wèi)星的建鏈信息發(fā)給注入站，注入站可見衛(wèi)星由注入站直接上注，否則通過(guò)星間鏈路轉(zhuǎn)發(fā)上注，進(jìn)而完成時(shí)間片之間的鏈路交換。

3 衛(wèi)星網(wǎng)絡(luò)拓?fù)渖伤惴?/h2>

3.1 算法建模

衛(wèi)星網(wǎng)絡(luò)的拓?fù)渖伤惴▽?shí)際上是尋找在滿足衛(wèi)星約束條件的前提下，生成的網(wǎng)絡(luò)拓?fù)渚仃嘇的全局最優(yōu)解。其中，衛(wèi)星拓?fù)湓诿總€(gè)時(shí)間片之間動(dòng)態(tài)變化，算法需要在多條件約束下求出每個(gè)時(shí)間片的矩陣A的全部集合。僅對(duì)于有66顆衛(wèi)星的銥星星座來(lái)說(shuō)，矩陣A的取值空間就有265×32=22 080，若采取給優(yōu)化目標(biāo)賦予權(quán)值并遍歷取值空間的做法，將是難以完成的任務(wù)。因此需要一種尋找矩陣A最優(yōu)解的策略，使得算法能在有效時(shí)間內(nèi)逼近全局最優(yōu)解，故提出一種IMOSA算法以解決上述問(wèn)題。

衛(wèi)星拓?fù)渖煽梢赞D(zhuǎn)化為一個(gè)多目標(biāo)優(yōu)化的問(wèn)題，本文依據(jù)衛(wèi)星通信的實(shí)際情況，綜合考慮衛(wèi)星間鏈路約束條件，以網(wǎng)絡(luò)平均時(shí)延、最大時(shí)延為優(yōu)化目標(biāo)，建立多目標(biāo)優(yōu)化的數(shù)學(xué)模型，對(duì)生成星間鏈路拓?fù)浣Y(jié)構(gòu)問(wèn)題進(jìn)行求解，多目標(biāo)優(yōu)化問(wèn)題的數(shù)學(xué)模型可以表示為

圖2 時(shí)間片分割示意圖

minf(A)=[fτa(A),fτm(A)]T

(9)

式中：f為最優(yōu)化的目標(biāo)函數(shù)，試求解A=[aij](i,j=1,2,…,n)，A為鏈路拓?fù)渚仃嚨臒o(wú)向圖模型，aij∈{0,1}表示一個(gè)時(shí)間片中衛(wèi)星si與衛(wèi)星sj是否建立星間鏈路；τa、τm分別為星間鏈路的端到端時(shí)延的平均值和最大值，fτa(A)、fτm(A)是其二者關(guān)于A的優(yōu)化函數(shù)。其計(jì)算公式為

(10)

τm=maxcij

(11)

式中：cij(i,j=1,2,…,n)表示在一個(gè)時(shí)間片內(nèi)衛(wèi)星si與sj之間鏈路的平均最小端到端時(shí)延。

建鏈約束條件為

s.t.vij∈{0,1}

(12)

vij=vji?i,j

(13)

vij-aij≥0 ?i,j

(14)

(15)

cij<∞ ?i,j

(16)

式中：vij為星間鏈路可視矩陣，其值與衛(wèi)星相對(duì)距離等有關(guān)；k為連接度。式(12)表示可視矩陣元素取值只能為1或0，即建鏈或斷開；式(13)為矩陣的對(duì)稱性約束；式(14)表示衛(wèi)星拓?fù)渲辽贊M足可視性條件；式(15)表示衛(wèi)星節(jié)點(diǎn)存在最大連接度k；式(16) 表示任意2顆衛(wèi)星之間通信時(shí)延不能是無(wú)限大，即衛(wèi)星網(wǎng)絡(luò)拓?fù)涫冀K為連通圖。

3.2 IMOSA算法

多目標(biāo)模擬退火(MOSA)算法是一種啟發(fā)式算法，Kirkpatrick等將退火思想引入組合優(yōu)化領(lǐng)域，提出了模擬退火算法[14]。該算法采用Metropolis接受準(zhǔn)則，并用一組稱為冷卻進(jìn)度表的參數(shù)控制算法進(jìn)程，使算法求出問(wèn)題的近似最優(yōu)解。在每次迭代中接受較優(yōu)解，并以一定的概率接受未優(yōu)化解，從而獲得跳出局部最優(yōu)解的能力。

本文以前述多目標(biāo)優(yōu)化模型為MOSA算法模型，選取平均端到端時(shí)延、最大端到端時(shí)延作為優(yōu)化目標(biāo)，對(duì)傳統(tǒng)MOSA算法進(jìn)行改進(jìn)，結(jié)合多狀態(tài)特點(diǎn)，設(shè)計(jì)了符合衛(wèi)星網(wǎng)絡(luò)拓?fù)涞泥徲蚪馍蒊MOSA算法。IMOSA算法采用修改的Metropolis準(zhǔn)則，相較于標(biāo)準(zhǔn)Metropolis準(zhǔn)則更好地處理多目標(biāo)的情況，并通過(guò)加入Pareto解集、和每隔一定迭代次數(shù)從Pareto解集中進(jìn)行優(yōu)選的策略，來(lái)保存歷史最優(yōu)值，以確保最終結(jié)果是最優(yōu)解，相比一般MOSA算法，優(yōu)化了迭代尋找最優(yōu)解的方向，使之能更好地找到最優(yōu)解，從而改善了收斂效果，提高了收斂速度。

IMOSA算法流程如圖3所示。初始拓?fù)渚仃嘇0為待優(yōu)化的靜態(tài)拓?fù)渚仃?，將其加入到Pareto解集中。每次迭代生成鄰域解An，若新矩陣An的τa和τm均優(yōu)于前一次，則令其為新的當(dāng)前矩陣An，每隔一定迭代次數(shù)從Pareto解集中隨機(jī)選擇一個(gè)矩陣作為初始矩陣，重新搜索；如果新矩陣未被接受，則保留當(dāng)前矩陣進(jìn)行下一次迭代。接受概率為

(17)

圖3 IMOSA算法流程

式中：Δτa=τan-τa，Δτm=τmn-τm，表示新矩陣和原矩陣平均端到端時(shí)延和最大端到端時(shí)延的差值；Tem1、Tem2為IMOSA算法冷卻進(jìn)度表中的溫度參數(shù)。冷卻進(jìn)度表是IMOSA算法效果的重要影響因素，其取值將影響最終優(yōu)化結(jié)果。冷卻進(jìn)度表參數(shù)主要有：初始溫度參數(shù)、溫度更新參數(shù)、迭代終止條件。初始溫度影響算法的優(yōu)化效率，取值越大獲得最優(yōu)解概率越大，但迭代次數(shù)會(huì)增加，因此需折中取值。本文取平均端到端時(shí)延和最大端到端時(shí)延的方差分別為Tem1、Tem2的值。通過(guò)2個(gè)優(yōu)化目標(biāo)的乘積形式，使二者同時(shí)影響接受概率，協(xié)同優(yōu)化。溫度更新函數(shù)Temk+1=λBTemk，λB為Boltzmann常數(shù)，一般地0<λB<1，每隔一定代數(shù)降一次溫。迭代終止條件為設(shè)定外循環(huán)次數(shù)來(lái)控制，歷經(jīng)多次迭代后逼近拓?fù)涞娜肿顑?yōu)解。IMOSA算法是通過(guò)搜索矩陣An的鄰域解來(lái)找到最優(yōu)解的，若直接隨機(jī)交換，將會(huì)導(dǎo)致新的鏈路不滿足可視條件或連接度條件，從而無(wú)法正確交換鏈路。

在多狀態(tài)條件下，衛(wèi)星的狀態(tài)值將影響衛(wèi)星鏈路發(fā)送時(shí)延、處理時(shí)延和排隊(duì)時(shí)延，加上星間動(dòng)態(tài)的傳播時(shí)延，即為端到端時(shí)延。運(yùn)用Dijkstra算法進(jìn)行求解衛(wèi)星端到端時(shí)延，并依據(jù)衛(wèi)星不同狀態(tài)賦予鏈路權(quán)值，進(jìn)而實(shí)現(xiàn)時(shí)延增大的效果。同時(shí)，若生成的圖為不連通圖，則必然至少出現(xiàn)某一端到端時(shí)延為無(wú)限大，那么算法將返回上一步驟重新交換鏈路，從而保證拓?fù)涫冀K為連通圖。因?yàn)橥負(fù)渚仃嚲哂袑?duì)稱性，只用計(jì)算上三角的時(shí)延即可，以減少Dijkstra算法的運(yùn)算量。

3.3 算法復(fù)雜度

在整個(gè)算法程序中，除了計(jì)算網(wǎng)絡(luò)時(shí)延的最短路徑算法Dijkstra算法外，其他模塊均為O(N)或O(1)復(fù)雜度。在計(jì)算網(wǎng)絡(luò)時(shí)延過(guò)程中，需要對(duì)每顆衛(wèi)星求解一次最短路徑，即執(zhí)行N次Dijkstra算法。而算法中每一步找到最小值需要花費(fèi)O(N)時(shí)間，從而整個(gè)算法過(guò)程花費(fèi)O(N2)時(shí)間查找最小值；每次更新最短路徑的時(shí)間為常數(shù)，而每條邊最多更新一次，若有E條邊則花費(fèi)O(E)。因此總的復(fù)雜度為

N[O(N2)+O(E)]=O(N3)

(18)

綜上，IMOSA算法的復(fù)雜度為O(N3)。

4 仿真分析

4.1 仿真環(huán)境

本文利用MATLAB和STK軟件進(jìn)行聯(lián)合仿真，仿真采用具有66顆LEO的銥星星座(Iridium Constellation)作為星座構(gòu)型。其具體參數(shù)如表1所示。

仿真中設(shè)衛(wèi)星狀態(tài)等級(jí)m=2，即有0，1，2這3個(gè)狀態(tài)，因?yàn)閷?shí)際衛(wèi)星在軌運(yùn)動(dòng)期間，狀態(tài)滿足正態(tài)分布，大多數(shù)衛(wèi)星狀態(tài)都在2和1之間，狀態(tài)為0的占少數(shù)，研究過(guò)程中發(fā)現(xiàn)，隨著狀態(tài)0和狀態(tài)1的比例變大，算法優(yōu)化效果變明顯，但比例過(guò)大算法將失去優(yōu)化空間。由于上述比例不符合正態(tài)分布的實(shí)際情況，因此本文不多加敘述。故假設(shè)狀態(tài)分布概率參數(shù)如表2所示，狀態(tài)2和狀態(tài)1分別涵蓋了大約60%，35%的衛(wèi)星，狀態(tài)0的衛(wèi)星僅占5%，符合實(shí)際情況。之后在衛(wèi)星所屬狀態(tài)映射的區(qū)間內(nèi)，隨機(jī)產(chǎn)生衛(wèi)星鏈路發(fā)送時(shí)延、處理時(shí)延和排隊(duì)時(shí)延。星間傳播時(shí)延由實(shí)時(shí)更新的星間距離與無(wú)線電在真空傳播速度之比得到。

表1 星座仿真參數(shù)

表2 衛(wèi)星狀態(tài)概率分布

4.2 仿真結(jié)果

衛(wèi)星坐標(biāo)每1 s更新一次，可視矩陣改變即進(jìn)入下一時(shí)間片，開始執(zhí)行算法。IMOSA算法的冷卻進(jìn)度表中的初始溫度參數(shù)T1、T2分別取均勻抽樣的一組網(wǎng)絡(luò)拓?fù)錉顟B(tài)中的各自目標(biāo)函數(shù)值的方差。其取值在不同時(shí)間片和星座中不同。另外溫度更新函數(shù)設(shè)為λB=0.95較為合理[15-16]，外循環(huán)迭代次數(shù)為2 000次。

圖4為單個(gè)時(shí)間片內(nèi)，IMOSA算法在銥星星座中，以平均時(shí)延和最大時(shí)延為目標(biāo)，生成拓?fù)溥^(guò)程的收斂性能。由圖4可知，在迭代次數(shù)達(dá)到1 500次之前目標(biāo)函數(shù)值已經(jīng)收斂。相較于初始拓?fù)?，兩目?biāo)函數(shù)分別優(yōu)化了11%和15%。另外從圖中可以看出，隨著迭代次數(shù)增加，目標(biāo)函數(shù)值并非單調(diào)遞減，而是會(huì)出現(xiàn)先增后再減小到更小值的情況，印證了IMOSA算法具有跳出局部最優(yōu)解的性能。

較新提出的啟發(fā)式算法有蜂群(Artificial Bee Colony，ABC)算法[17-18]等，圖5為本文提出的IMOSA算法，與文獻(xiàn)[10]中一般的MOSA算法、文獻(xiàn)[17]中蜂群算法的收斂性進(jìn)行對(duì)比。在保持其他條件一致的情況下，均對(duì)銥星星座進(jìn)行拓?fù)渖煞抡鎸?shí)驗(yàn)，統(tǒng)計(jì)在本文算法達(dá)到2 000次迭代的時(shí)間內(nèi)各算法的收斂情況。如圖5所示，本文算法完成2 000次迭代的時(shí)間為12.03 s，在相同時(shí)間內(nèi)，文獻(xiàn)[10]的一般MOSA算法和文獻(xiàn)[17]中的ABC算法收斂度均低于本文算法。實(shí)驗(yàn)表明，一般MOSA算法難以收斂到最優(yōu)解，ABC算法雖然最終收斂效果好，但算法復(fù)雜度高，運(yùn)行時(shí)間長(zhǎng)。本文改進(jìn)的MOSA算法兼顧收斂效果和運(yùn)行時(shí)間，具有一定優(yōu)越性。

圖4 單個(gè)時(shí)間片IMOSA算法收斂特性

圖5 IMOSA、MOSA和ABC算法收斂情況比較

圖6為是否考慮多狀態(tài)情況時(shí)，衛(wèi)星網(wǎng)絡(luò)時(shí)延的對(duì)比。由圖可知在多狀態(tài)情況下，端到端平均時(shí)延和最大時(shí)延均明顯增大，且時(shí)延抖動(dòng)也變大。因?yàn)槭聦?shí)上不考慮多狀態(tài)的情況相當(dāng)于假設(shè)所有衛(wèi)星均處于最佳狀態(tài)，當(dāng)考慮多狀態(tài)時(shí)，狀態(tài)差的衛(wèi)星影響了網(wǎng)絡(luò)性能，而且在切換至下一個(gè)時(shí)間片時(shí)，狀態(tài)差的衛(wèi)星位置和與其他衛(wèi)星鏈接狀態(tài)發(fā)生改變，導(dǎo)致最大時(shí)延激增或銳減，同時(shí)平均時(shí)延也受到影響。

圖6 銥星星座中考慮多狀態(tài)因素時(shí)的網(wǎng)絡(luò)時(shí)延改變

在均考慮衛(wèi)星多狀態(tài)的情況下，通過(guò)本文IMOSA算法生成的動(dòng)態(tài)拓?fù)?，其平均時(shí)延和最大時(shí)延相較于未優(yōu)化的初始靜態(tài)拓?fù)渚薪档停蚴撬惴▓?zhí)行過(guò)程中，盡量避免了與狀態(tài)差的衛(wèi)星節(jié)點(diǎn)建鏈。如圖7(a)和圖7(b)所示，2個(gè)目標(biāo)函數(shù)分別降低16%和34%，驗(yàn)證了算法的有效性。

圖7 銥星星座多狀態(tài)下的IMOSA算法優(yōu)化效果

本文對(duì)生成拓?fù)涞目箽赃M(jìn)行了分析?？箽钥坍嬃司W(wǎng)絡(luò)被破壞的難易程度，由于節(jié)點(diǎn)間連接的抗毀性取決于節(jié)點(diǎn)之間替代途徑的冗余性，那么網(wǎng)絡(luò)的抗毀性就可以說(shuō)取決于網(wǎng)絡(luò)中替代途徑的冗余性[19-20]。本文以自然連通度[21-22]作為網(wǎng)絡(luò)拓?fù)涞目箽灾笜?biāo)，自然連通度刻畫了網(wǎng)絡(luò)中替代途徑的冗余性。其計(jì)算公式為

(19)

式中：λi為拓?fù)溧徑泳仃嚨奶卣鞲?；n為拓?fù)涔?jié)點(diǎn)個(gè)數(shù)。自然連通度關(guān)于拓?fù)淇箽允菄?yán)格單調(diào)的，拓?fù)浣Y(jié)構(gòu)抗毀性越強(qiáng)，自然連通度值越大。

圖8為用IMOSA算法優(yōu)化后的拓?fù)浣Y(jié)構(gòu)與原始拓?fù)浣Y(jié)構(gòu)自然連通度對(duì)比。如圖所示，IMOSA算法優(yōu)化后，在銥星星座中自然連通度λ的值都有所增大，由于衛(wèi)星節(jié)點(diǎn)較少且連接度小，其增大并不明顯(6%左右)，但由于其嚴(yán)格的單調(diào)性已經(jīng)表明拓?fù)浣Y(jié)構(gòu)的抗毀性提高。另外，圖9選擇其中一個(gè)時(shí)間片，采用隨機(jī)摧毀衛(wèi)星節(jié)點(diǎn)的方式，顯示了經(jīng)優(yōu)化后的拓?fù)湓诠?jié)點(diǎn)損毀時(shí)，自然連通度下降稍慢，即抗毀性更好。故證明了本文算法在一定程度上也保證了拓?fù)涞目箽浴?/p>

圖8 IMOSA算法優(yōu)化前后自然聯(lián)通度對(duì)比

圖9 單個(gè)時(shí)間片隨機(jī)刪除節(jié)點(diǎn)后自然聯(lián)通度對(duì)比

5 結(jié) 論

本文針對(duì)空間信息網(wǎng)絡(luò)多狀態(tài)的情況，分析了多狀態(tài)下衛(wèi)星網(wǎng)絡(luò)時(shí)延增大的問(wèn)題，提出了一種以衛(wèi)星網(wǎng)絡(luò)平均時(shí)延和最大時(shí)延為目標(biāo)函數(shù)的IMOSA算法，用以生成優(yōu)化衛(wèi)星星座拓?fù)洌瑴p小多狀態(tài)下的網(wǎng)絡(luò)時(shí)延。通過(guò)仿真驗(yàn)證：

1) 該算法在銥星星座中收斂性較MOSA算法和ABC算法更好，與靜態(tài)拓?fù)湎啾?，網(wǎng)絡(luò)端到端平均時(shí)延和最大時(shí)延分別最大降低16%和34%，實(shí)現(xiàn)了網(wǎng)絡(luò)拓?fù)涞膬?yōu)化。

2) 同時(shí)自然連通度的值提高了6%，即該算法生成的網(wǎng)絡(luò)拓?fù)渚哂懈玫目箽浴?/p>