多狀態(tài)空間信息網(wǎng)絡(luò)拓?fù)渖蓛?yōu)化算法

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

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

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

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

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

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

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

上述算法均未考慮衛(wèi)星節(jié)點的多狀態(tài)，僅考慮衛(wèi)星節(jié)點位置等因素，當(dāng)某節(jié)點狀態(tài)不佳時，而不改變原有拓?fù)洌瑢?dǎo)致網(wǎng)絡(luò)時延增大等問題。本文考慮衛(wèi)星系統(tǒng)的多狀態(tài)特點，利用現(xiàn)有的衛(wèi)星星座，以連接度和可視距離等為約束條件，針對衛(wèi)星網(wǎng)絡(luò)高動態(tài)性，以鏈路平均端到端時延和最大端到端時延為優(yōu)化目標(biāo)，設(shè)計了一種改進(jìn)的多目標(biāo)模擬退火(Improved Multi-Objective Simulated Annealing，IMOSA)算法進(jìn)行拓?fù)渖桑乖撍惴ㄔ诳紤]衛(wèi)星多狀態(tài)的情況下，對衛(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)星的長時間使用，將會有電阻、電容發(fā)生老化，磁盤機(jī)械磨損，故障率提升等現(xiàn)象，并且當(dāng)衛(wèi)星節(jié)點數(shù)據(jù)并發(fā)量過大，導(dǎo)致CPU和存儲讀寫繁忙，都會導(dǎo)致處理能力下降，讀取數(shù)據(jù)速度變慢等問題。本文依據(jù)衛(wèi)星處理能力將其劃分為不同的狀態(tài)等級，衛(wèi)星在每一刻的狀態(tài)對應(yīng)一個確定的狀態(tài)等級，狀態(tài)等級越低，誤碼率越高，處理能力越差，越容易出現(xiàn)故障，從而導(dǎo)致處理時延和排隊時延增加，再加上由于星間距離產(chǎn)生的大傳播時延，使得整體時延變大。

假設(shè)衛(wèi)星狀態(tài)等級集合為g={0,1,…,m}。仿照實際情況，假設(shè)衛(wèi)星性能水平服從一定的概率分布，狀態(tài)最佳的衛(wèi)星數(shù)量最多，一定比例出現(xiàn)狀態(tài)較差的衛(wèi)星。不同狀態(tài)的衛(wèi)星發(fā)送時延、處理時延和排隊時延之和不同，當(dāng)衛(wèi)星處于狀態(tài)R∈ {0,1,…,m}時，其發(fā)送時延、處理時延和排隊時延之和t分別滿足范圍t∈{[ti,ti+1),[ti-1,ti)，…,[ti-m,ti-m+1)}，即存在映射關(guān)系。例如本文取0,1,2這3個狀態(tài)：狀態(tài)2，時延t∈[0,20)最小；狀態(tài)1，時延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ù)鋵嶋H上是一個各邊權(quán)值為星間距離的無向圖[8-10]。描述為G(S,E)，其中；S={s1,s2,…，sn}為n顆衛(wèi)星的有限節(jié)點集，表示網(wǎng)絡(luò)中衛(wèi)星節(jié)點；E為有限邊集，表示網(wǎng)絡(luò)中衛(wèi)星間的鏈路。通常用矩陣表示圖，如建立n×n的矩陣A，當(dāng)衛(wèi)星si和衛(wèi)星sj之間連通時，aij=1，否則aij=0，當(dāng)i=j時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之間可視時，vij=1，否則，vij=0。其表達(dá)形式與矩陣A類似。由于衛(wèi)星在軌運(yùn)行時相互會被地球遮擋，因而2顆衛(wèi)星之間的鏈路長度存在一個滿足可視條件的最大值。假設(shè)Hi、Hj分別表示衛(wèi)星si、sj的軌道高度；Rd為地球半徑，ξ為2顆衛(wèi)星與地心形成的夾角。此時dmax為衛(wèi)星si、sj可視的最大鏈路長度，即

(2)

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

(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)星真近地點角；n0為線速度；ωe為地球自轉(zhuǎn)角速度；Ω為衛(wèi)星升交點赤經(jīng)，α為衛(wèi)星軌道傾角，X、Y、Z分別為單顆衛(wèi)星的地固坐標(biāo)系。該坐標(biāo)系的原點為地心，XOY平面和地球赤道平面重合，OX軸與格林威治子午線方向一致，OZ軸與地球的極軸重合。若不考慮其他天體和人造衛(wèi)星對衛(wèi)星的影響，由式(3)～式(7) 得到星間距離dij。當(dāng)dij≤dmax時，衛(wèi)星可視，vij=1，否則為不可視，vij=0。可視性判斷示意圖如圖1所示。

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

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

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

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

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

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

3.1 算法建模

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

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

圖2 時間片分割示意圖

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向圖模型，aij∈{0,1}表示一個時間片中衛(wèi)星si與衛(wèi)星sj是否建立星間鏈路；τa、τm分別為星間鏈路的端到端時延的平均值和最大值，fτa(A)、fτm(A)是其二者關(guān)于A的優(yōu)化函數(shù)。其計算公式為

(10)

τm=maxcij

(11)

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

建鏈約束條件為

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)星相對距離等有關(guān)；k為連接度。式(12)表示可視矩陣元素取值只能為1或0，即建鏈或斷開；式(13)為矩陣的對稱性約束；式(14)表示衛(wèi)星拓?fù)渲辽贊M足可視性條件；式(15)表示衛(wèi)星節(jié)點存在最大連接度k；式(16) 表示任意2顆衛(wèi)星之間通信時延不能是無限大，即衛(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)程，使算法求出問題的近似最優(yōu)解。在每次迭代中接受較優(yōu)解，并以一定的概率接受未優(yōu)化解，從而獲得跳出局部最優(yōu)解的能力。

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

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

(17)

圖3 IMOSA算法流程

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

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

3.3 算法復(fù)雜度

在整個算法程序中，除了計算網(wǎng)絡(luò)時延的最短路徑算法Dijkstra算法外，其他模塊均為O(N)或O(1)復(fù)雜度。在計算網(wǎng)絡(luò)時延過程中，需要對每顆衛(wèi)星求解一次最短路徑，即執(zhí)行N次Dijkstra算法。而算法中每一步找到最小值需要花費(fèi)O(N)時間，從而整個算法過程花費(fèi)O(N2)時間查找最小值；每次更新最短路徑的時間為常數(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)等級m=2，即有0，1，2這3個狀態(tài)，因為實際衛(wèi)星在軌運(yùn)動期間，狀態(tài)滿足正態(tài)分布，大多數(shù)衛(wèi)星狀態(tài)都在2和1之間，狀態(tài)為0的占少數(shù)，研究過程中發(fā)現(xiàn)，隨著狀態(tài)0和狀態(tài)1的比例變大，算法優(yōu)化效果變明顯，但比例過大算法將失去優(yōu)化空間。由于上述比例不符合正態(tài)分布的實際情況，因此本文不多加敘述。故假設(shè)狀態(tài)分布概率參數(shù)如表2所示，狀態(tài)2和狀態(tài)1分別涵蓋了大約60%，35%的衛(wèi)星，狀態(tài)0的衛(wèi)星僅占5%，符合實際情況。之后在衛(wèi)星所屬狀態(tài)映射的區(qū)間內(nèi)，隨機(jī)產(chǎn)生衛(wèi)星鏈路發(fā)送時延、處理時延和排隊時延。星間傳播時延由實時更新的星間距離與無線電在真空傳播速度之比得到。

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

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

4.2 仿真結(jié)果

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

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

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

圖4 單個時間片IMOSA算法收斂特性

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

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

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

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

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

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

(19)

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

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

圖9 單個時間片隨機(jī)刪除節(jié)點后自然聯(lián)通度對比

5 結(jié) 論

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

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

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