多狀態空間信息網絡拓撲生成優化算法

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

1. 大連大學 信息工程學院，大連 116622

2. 大連大學 通信與網絡重點實驗室，大連 116622

3. 南京理工大學 自動化學院，南京 210094

隨著“空天地一體化”進程的推進，空間信息網絡(Space Information Network，SIN)在信息的傳輸、獲取和分發任務中起著極其重要的作用。與地面網絡不同，衛星網絡中通信節點高速運動，通信鏈路頻繁斷開，信息傳輸的時延大、誤碼率高[1]，嚴重影響網絡拓撲的穩定性。而穩定的衛星網絡拓撲不僅是實現網絡信息交換和資源共享的基礎，而且也是實現網絡管理、協議設計優化、安全控制等的前提。因此，設計可靠的衛星網絡拓撲算法至關重要。

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

傳統的衛星網絡拓撲生成算法大多僅考慮衛星網絡的空間特性，即看作分布在近地空間的一般節點，石磊玉等[6]針對如何有效分配有限波束來建立星間鏈路的問題，提出了一種基于貪婪算法的分配策略，在保證衛星觀測數量最大化的前提下，以降低整網通信代價為優化目標，實現鏈路分配，但貪婪算法在該處的收斂性不佳。Chu和Chen[7]提出了一種基于北斗導航系統的時分拓撲生成算法，從拓撲角度實現源節點到端節點數據的快速傳輸。Ma等[8]提出一種新的低軌-中軌(Low Earth Orbit-Medium Earth Orbit,LEO-MEO)雙層衛星網絡拓撲模型，并考慮了極地邊界的影響，但該模型工程上難以實現。Wang等[9]提出了一種綜合權重的策略對衛星網絡建鏈，減少了時延，擁塞率和鏈路切換。董明佶等[10]設計了一種改進的模擬退火算法，以空間位置精度因子(Position Dilution of Precision，PDOP)和網絡時延等為優化目標，生成衛星激光星間鏈路拓撲，但是針對激光鏈路，與微波鏈路不同。

上述算法均未考慮衛星節點的多狀態，僅考慮衛星節點位置等因素，當某節點狀態不佳時，而不改變原有拓撲，將導致網絡時延增大等問題。本文考慮衛星系統的多狀態特點，利用現有的衛星星座，以連接度和可視距離等為約束條件，針對衛星網絡高動態性，以鏈路平均端到端時延和最大端到端時延為優化目標，設計了一種改進的多目標模擬退火(Improved Multi-Objective Simulated Annealing，IMOSA)算法進行拓撲生成，使該算法在考慮衛星多狀態的情況下，對衛星拓撲具有較好的優化效果，得到全局最優拓撲結構的近似解，并證明了生成的衛星網絡拓撲的可靠性和抗毀性。

1 衛星系統的多狀態

隨著衛星的長時間使用，將會有電阻、電容發生老化，磁盤機械磨損，故障率提升等現象，并且當衛星節點數據并發量過大，導致CPU和存儲讀寫繁忙，都會導致處理能力下降，讀取數據速度變慢等問題。本文依據衛星處理能力將其劃分為不同的狀態等級，衛星在每一刻的狀態對應一個確定的狀態等級，狀態等級越低，誤碼率越高，處理能力越差，越容易出現故障，從而導致處理時延和排隊時延增加，再加上由于星間距離產生的大傳播時延，使得整體時延變大。

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

2 衛星網絡模型

2.1 衛星網絡拓撲模型

星間鏈路拓撲實際上是一個各邊權值為星間距離的無向圖[8-10]。描述為G(S,E)，其中；S={s1,s2,…，sn}為n顆衛星的有限節點集，表示網絡中衛星節點；E為有限邊集，表示網絡中衛星間的鏈路。通常用矩陣表示圖，如建立n×n的矩陣A，當衛星si和衛星sj之間連通時，aij=1，否則aij=0，當i=j時aij=0，其中i,j=1,2,…,n。稱A為衛星網絡的鄰接矩陣，其表達式為

(1)

設矩陣V為衛星網絡的可視矩陣，表示衛星由于地球的遮擋，呈現可視或不可視狀態的矩陣。當衛星si和衛星sj之間可視時，vij=1，否則，vij=0。其表達形式與矩陣A類似。由于衛星在軌運行時相互會被地球遮擋，因而2顆衛星之間的鏈路長度存在一個滿足可視條件的最大值。假設Hi、Hj分別表示衛星si、sj的軌道高度；Rd為地球半徑，ξ為2顆衛星與地心形成的夾角。此時dmax為衛星si、sj可視的最大鏈路長度，即

(2)

設dij為2顆衛星之間的實際距離，其計算公式為

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

圖1 衛星可視性判斷示意圖

2.2 拓撲周期模型

衛星在軌道上的相對運動使得互相之間的可視性隨時間變化，為了減少這種由拓撲動態性引起的拓撲變化的復雜程度，本文將衛星星座周期長度T分成N個時間片[11-12]。這樣時變的可視性衛星周期就轉化為一系列拓撲固定的時間片，而在此基礎上設計算法就能以每個時間片作為計算對象。

在每個時間片內，衛星拓撲不變，因此也稱為拓撲快照。這種方法將周期T分成如下N個時間片：[t0=0,t1],[t1,t2],[t2,t3],…,[tN-1,tN=T]，在新時間片開始處，存在鏈路交換時間texch，用來完成從上一個拓撲快照交換鏈路后生成下一個拓撲快照，時間片分割示意如圖2所示，其中Pi(i=1,2,…,N)為周期。

以上星座時間片的切換，由地面站配合完成。地面站分為主控站、監測站和注入站，主控站同時也是監測站[13]。監測站跟蹤監控衛星狀態，主控站依據已知星歷和監測站反饋的信息運算各個時間片的拓撲和修正參數，轉換為每顆衛星的建鏈信息發給注入站，注入站可見衛星由注入站直接上注，否則通過星間鏈路轉發上注，進而完成時間片之間的鏈路交換。

3 衛星網絡拓撲生成算法

3.1 算法建模

衛星網絡的拓撲生成算法實際上是尋找在滿足衛星約束條件的前提下，生成的網絡拓撲矩陣A的全局最優解。其中，衛星拓撲在每個時間片之間動態變化，算法需要在多條件約束下求出每個時間片的矩陣A的全部集合。僅對于有66顆衛星的銥星星座來說，矩陣A的取值空間就有265×32=22 080，若采取給優化目標賦予權值并遍歷取值空間的做法，將是難以完成的任務。因此需要一種尋找矩陣A最優解的策略，使得算法能在有效時間內逼近全局最優解，故提出一種IMOSA算法以解決上述問題。

衛星拓撲生成可以轉化為一個多目標優化的問題，本文依據衛星通信的實際情況，綜合考慮衛星間鏈路約束條件，以網絡平均時延、最大時延為優化目標，建立多目標優化的數學模型，對生成星間鏈路拓撲結構問題進行求解，多目標優化問題的數學模型可以表示為

圖2 時間片分割示意圖

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

(9)

式中：f為最優化的目標函數，試求解A=[aij](i,j=1,2,…,n)，A為鏈路拓撲矩陣的無向圖模型，aij∈{0,1}表示一個時間片中衛星si與衛星sj是否建立星間鏈路；τa、τm分別為星間鏈路的端到端時延的平均值和最大值，fτa(A)、fτm(A)是其二者關于A的優化函數。其計算公式為

(10)

τm=maxcij

(11)

式中：cij(i,j=1,2,…,n)表示在一個時間片內衛星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為星間鏈路可視矩陣，其值與衛星相對距離等有關；k為連接度。式(12)表示可視矩陣元素取值只能為1或0，即建鏈或斷開；式(13)為矩陣的對稱性約束；式(14)表示衛星拓撲至少滿足可視性條件；式(15)表示衛星節點存在最大連接度k；式(16) 表示任意2顆衛星之間通信時延不能是無限大，即衛星網絡拓撲始終為連通圖。

3.2 IMOSA算法

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

本文以前述多目標優化模型為MOSA算法模型，選取平均端到端時延、最大端到端時延作為優化目標，對傳統MOSA算法進行改進，結合多狀態特點，設計了符合衛星網絡拓撲的鄰域解生成IMOSA算法。IMOSA算法采用修改的Metropolis準則，相較于標準Metropolis準則更好地處理多目標的情況，并通過加入Pareto解集、和每隔一定迭代次數從Pareto解集中進行優選的策略，來保存歷史最優值，以確保最終結果是最優解，相比一般MOSA算法，優化了迭代尋找最優解的方向，使之能更好地找到最優解，從而改善了收斂效果，提高了收斂速度。

IMOSA算法流程如圖3所示。初始拓撲矩陣A0為待優化的靜態拓撲矩陣，將其加入到Pareto解集中。每次迭代生成鄰域解An，若新矩陣An的τa和τm均優于前一次，則令其為新的當前矩陣An，每隔一定迭代次數從Pareto解集中隨機選擇一個矩陣作為初始矩陣，重新搜索；如果新矩陣未被接受，則保留當前矩陣進行下一次迭代。接受概率為

(17)

圖3 IMOSA算法流程

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

在多狀態條件下，衛星的狀態值將影響衛星鏈路發送時延、處理時延和排隊時延，加上星間動態的傳播時延，即為端到端時延。運用Dijkstra算法進行求解衛星端到端時延，并依據衛星不同狀態賦予鏈路權值，進而實現時延增大的效果。同時，若生成的圖為不連通圖，則必然至少出現某一端到端時延為無限大，那么算法將返回上一步驟重新交換鏈路，從而保證拓撲始終為連通圖。因為拓撲矩陣具有對稱性，只用計算上三角的時延即可，以減少Dijkstra算法的運算量。

3.3 算法復雜度

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

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

(18)

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

4 仿真分析

4.1 仿真環境

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

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

表1 星座仿真參數

表2 衛星狀態概率分布

4.2 仿真結果

衛星坐標每1 s更新一次，可視矩陣改變即進入下一時間片，開始執行算法。IMOSA算法的冷卻進度表中的初始溫度參數T1、T2分別取均勻抽樣的一組網絡拓撲狀態中的各自目標函數值的方差。其取值在不同時間片和星座中不同。另外溫度更新函數設為λB=0.95較為合理[15-16]，外循環迭代次數為2 000次。

圖4為單個時間片內，IMOSA算法在銥星星座中，以平均時延和最大時延為目標，生成拓撲過程的收斂性能。由圖4可知，在迭代次數達到1 500次之前目標函數值已經收斂。相較于初始拓撲，兩目標函數分別優化了11%和15%。另外從圖中可以看出，隨著迭代次數增加，目標函數值并非單調遞減，而是會出現先增后再減小到更小值的情況，印證了IMOSA算法具有跳出局部最優解的性能。

較新提出的啟發式算法有蜂群(Artificial Bee Colony，ABC)算法[17-18]等，圖5為本文提出的IMOSA算法，與文獻[10]中一般的MOSA算法、文獻[17]中蜂群算法的收斂性進行對比。在保持其他條件一致的情況下，均對銥星星座進行拓撲生成仿真實驗，統計在本文算法達到2 000次迭代的時間內各算法的收斂情況。如圖5所示，本文算法完成2 000次迭代的時間為12.03 s，在相同時間內，文獻[10]的一般MOSA算法和文獻[17]中的ABC算法收斂度均低于本文算法。實驗表明，一般MOSA算法難以收斂到最優解，ABC算法雖然最終收斂效果好，但算法復雜度高，運行時間長。本文改進的MOSA算法兼顧收斂效果和運行時間，具有一定優越性。

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

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

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

圖6 銥星星座中考慮多狀態因素時的網絡時延改變

在均考慮衛星多狀態的情況下，通過本文IMOSA算法生成的動態拓撲，其平均時延和最大時延相較于未優化的初始靜態拓撲均有降低，原因是算法執行過程中，盡量避免了與狀態差的衛星節點建鏈。如圖7(a)和圖7(b)所示，2個目標函數分別降低16%和34%，驗證了算法的有效性。

圖7 銥星星座多狀態下的IMOSA算法優化效果

本文對生成拓撲的抗毀性進行了分析。抗毀性刻畫了網絡被破壞的難易程度，由于節點間連接的抗毀性取決于節點之間替代途徑的冗余性，那么網絡的抗毀性就可以說取決于網絡中替代途徑的冗余性[19-20]。本文以自然連通度[21-22]作為網絡拓撲的抗毀性指標，自然連通度刻畫了網絡中替代途徑的冗余性。其計算公式為

(19)

式中：λi為拓撲鄰接矩陣的特征根；n為拓撲節點個數。自然連通度關于拓撲抗毀性是嚴格單調的，拓撲結構抗毀性越強，自然連通度值越大。

圖8為用IMOSA算法優化后的拓撲結構與原始拓撲結構自然連通度對比。如圖所示，IMOSA算法優化后，在銥星星座中自然連通度λ的值都有所增大，由于衛星節點較少且連接度小，其增大并不明顯(6%左右)，但由于其嚴格的單調性已經表明拓撲結構的抗毀性提高。另外，圖9選擇其中一個時間片，采用隨機摧毀衛星節點的方式，顯示了經優化后的拓撲在節點損毀時，自然連通度下降稍慢，即抗毀性更好。故證明了本文算法在一定程度上也保證了拓撲的抗毀性。

圖8 IMOSA算法優化前后自然聯通度對比

圖9 單個時間片隨機刪除節點后自然聯通度對比

5 結 論

本文針對空間信息網絡多狀態的情況，分析了多狀態下衛星網絡時延增大的問題，提出了一種以衛星網絡平均時延和最大時延為目標函數的IMOSA算法，用以生成優化衛星星座拓撲，減小多狀態下的網絡時延。通過仿真驗證：

1) 該算法在銥星星座中收斂性較MOSA算法和ABC算法更好，與靜態拓撲相比，網絡端到端平均時延和最大時延分別最大降低16%和34%，實現了網絡拓撲的優化。

2) 同時自然連通度的值提高了6%，即該算法生成的網絡拓撲具有更好的抗毀性。