測控通信網(wǎng)絡(luò)可生存性建模與分析

于金濤，葉 偉

(1.哈爾濱商業(yè)大學 計算機信息與工程學院， 哈爾濱 150028，2.哈爾濱醫(yī)科大學 生物信息科學與技術(shù)學院，哈爾濱 150080)

深空測控通信網(wǎng)絡(luò)是一個龐大復(fù)雜的網(wǎng)絡(luò)，它主要負責遙感數(shù)據(jù)和科學信息的傳送，跟蹤并指揮深空探測器執(zhí)行科學任務(wù)[1-2].測控通信網(wǎng)是深空探測器與地面站之間聯(lián)系的紐帶，該網(wǎng)絡(luò)系統(tǒng)在整個深空探測中起著重要作用.整個測控通網(wǎng)絡(luò)中各節(jié)點之間的連通關(guān)系對其可生存性有重要影響.為了避免網(wǎng)絡(luò)通信中斷導(dǎo)致的損失，測控通信網(wǎng)絡(luò)的設(shè)計需要考慮因網(wǎng)絡(luò)中節(jié)點失效或者深空環(huán)境引起故障時測控通信網(wǎng)絡(luò)的可生存性.

可生存性研究最早出現(xiàn)在傳統(tǒng)軍事領(lǐng)域，進入通信時代后網(wǎng)絡(luò)系統(tǒng)的可生存性逐漸引起人們關(guān)注[3].研究的主要方面是以通信設(shè)備的性能為基礎(chǔ)，從通信鏈路的連通性角度來分析其可生存性.對測控通信網(wǎng)絡(luò)可生存性的研究，選取合適的指標參數(shù)是基礎(chǔ).現(xiàn)階段，網(wǎng)絡(luò)連通性主要以圖論中點的連通度和邊的連通度為指標，但是這些參數(shù)僅反映了網(wǎng)絡(luò)出現(xiàn)故障的可能性，并不能反映出網(wǎng)絡(luò)出現(xiàn)故障后繼續(xù)服務(wù)的能力，而系統(tǒng)可生存性就是要研究其在遭受攻擊或意外事故的情況下，仍然能夠及時地完成關(guān)鍵任務(wù).吳俊等人在文獻[4]中研究了復(fù)雜網(wǎng)絡(luò)的抗毀性指標.以網(wǎng)絡(luò)結(jié)構(gòu)的連通度為參考，同時考慮了網(wǎng)絡(luò)的連通路徑.然而這種指標只能在一定程度上反應(yīng)網(wǎng)絡(luò)的抗毀性，并不能描述網(wǎng)絡(luò)受到損毀后的恢復(fù)能力.1955年Cozzens以及其研究小組以圖論相關(guān)領(lǐng)域知識為背景提出網(wǎng)絡(luò)的韌性度指標，它能夠描述網(wǎng)絡(luò)損毀狀況和損毀后網(wǎng)絡(luò)的連通狀態(tài).但是韌性度的相關(guān)計算仍然是一個NP問題(Nondeterministic Polynomial problem)，而限制了其廣泛應(yīng)用[5].在文獻[6]中王玥等人使用遺傳算法在一定程度上降低了韌性度計算的復(fù)雜度，但是由于遺傳算法本身的缺點，實驗數(shù)據(jù)的收斂結(jié)果不理想.

綜上所述，本文借助可生存性特點以及圖論中的韌性度作為指標來研究深空測控通信網(wǎng)絡(luò)，著眼于測控通信網(wǎng)絡(luò)整體而非局部單元，并采用一種基于模擬退火粒子群算法的韌性度計算方法，與傳統(tǒng)遺傳算法相比，該算法收斂速度較快且有較好的全局尋優(yōu)能力，進而實現(xiàn)從拓撲結(jié)構(gòu)上，對測控通信網(wǎng)絡(luò)可生存性進行量化評估.

1 深空測控通信網(wǎng)絡(luò)可生存性分析

測控通信網(wǎng)絡(luò)可以看作是由有限個通信資源組成的網(wǎng)絡(luò)，各個通信資源連接的鏈路看作網(wǎng)絡(luò)連通支路.當測控通信網(wǎng)絡(luò)節(jié)點或支路出現(xiàn)故障時，期望測控通信網(wǎng)絡(luò)不易被破壞，即使在網(wǎng)絡(luò)遭受到一定破壞后仍然能保持其主要節(jié)點的連通能力，并且容易被重構(gòu).根據(jù)可生存性的定義，用一個三組來描述測控通信網(wǎng)絡(luò)的可生存性.三元組形式如下：

Sur(N)={S,ω(N-S),τ(N-S)}

其中：S，ω(N-S)，τ(N-S)分別表示測控通信網(wǎng)絡(luò)的抵抗能力、可恢復(fù)性、容錯性.S為網(wǎng)絡(luò)拓撲圖的割點集，它描述了不同節(jié)點集合對網(wǎng)絡(luò)的斷裂能力，反映出測控通信網(wǎng)絡(luò)的抵抗能力，即需要毀壞網(wǎng)絡(luò)中節(jié)點的個數(shù).ω(N-S)代表剩余網(wǎng)絡(luò)被重新構(gòu)建的復(fù)雜度，ω(N-S)的大小表示損毀后的網(wǎng)絡(luò)需要被重建的難易程度，τ(N-S)是網(wǎng)絡(luò)的容錯性指標，圖論中其表示被破壞網(wǎng)絡(luò)最大的有效連通分支數(shù)大小.其值越大則損毀后網(wǎng)絡(luò)的重構(gòu)難度越小，因為有效地連通子網(wǎng)數(shù)目最大.

2 深空測控通信網(wǎng)絡(luò)可生存性建模

本文用圖論表示法，將深空測空通信網(wǎng)中各個測控單元看作其拓撲結(jié)構(gòu)圖中的節(jié)點，通信鏈路看作是圖中的邊.選取韌性度作為描述測控通信網(wǎng)絡(luò)可生存性參數(shù)，此參數(shù)表明了網(wǎng)絡(luò)結(jié)構(gòu)連接的合理性，目的是用圖論中相關(guān)知識有效地描述網(wǎng)絡(luò)結(jié)構(gòu)的可生存性[7].網(wǎng)絡(luò)的可生存性定義為：

S?G(N),ω(N-S)>1

(1)

其中：G(N)表示測控通信網(wǎng)絡(luò)，|N|表示網(wǎng)絡(luò)中一共的節(jié)點數(shù)，ω(N-S)表示網(wǎng)絡(luò)的所有連通分支數(shù)，S表示網(wǎng)絡(luò)中所有的割點集，τ(N-S)表示剩余網(wǎng)絡(luò)的最大連通分支的階數(shù).

S，ω(N-S)，τ(N-S)三者在可生存性分析中相互制約.測控通信網(wǎng)絡(luò)中各重要節(jié)點都會有冗余備份，一般只有極少節(jié)點會出現(xiàn)故障，因此我們在本文只討論|S|?|N|時的情況，即割點集中割點數(shù)遠小于網(wǎng)絡(luò)中節(jié)點數(shù).測控通信網(wǎng)絡(luò)中割點集中割點的個數(shù)|S|越大，則網(wǎng)絡(luò)出現(xiàn)故障的可能性越高，并且在剩余網(wǎng)絡(luò)中ω(N-S))越大，τ(N-S)三越小.當網(wǎng)絡(luò)中割點數(shù)相同時，即|S|不變，剩余網(wǎng)絡(luò)連通分支數(shù)ω(N-S)越大，則連通分數(shù)τ(N-S)越小.三者的變化制約關(guān)系如圖1所示.

圖1 |S|，ω(N-S)，τ(N-S)相互制約關(guān)系

3 深空測控通信網(wǎng)絡(luò)可生存性計算

深空測控通信網(wǎng)絡(luò)可生存性評估中采用韌性度做為參數(shù)，現(xiàn)階段關(guān)于點的韌性度計算沒有相應(yīng)的多項式時間算法.通過對網(wǎng)絡(luò)結(jié)構(gòu)中所有割點集合進行全局搜索，然后再計算出剩余網(wǎng)絡(luò)中的最大連通分支數(shù)ω(N-S)和最大連通分支階數(shù)τ(N-S)，將其帶入公式1求得點的韌性度值.在前人工作的基礎(chǔ)上，本文采用基于模擬退火和粒子群優(yōu)化的混合算法來計算網(wǎng)絡(luò)節(jié)點的韌性度值[8].本文所采用的法吸收了融合思想的算法改進策略，同時利用了兩種算法各自優(yōu)點，如快速收斂能力和局部極值搜索能力[9].

3.1 網(wǎng)絡(luò)節(jié)點表示及編碼

根據(jù)粒子群優(yōu)化算法粒子群選取特點，用二進制變量表示網(wǎng)絡(luò)中已獲得種群粒子狀態(tài).假設(shè)網(wǎng)絡(luò)N1中有8個節(jié)點即G(N1)={V1,V2,……V8}.用二進制1和0分別表示節(jié)點狀態(tài)：正常和故障.如網(wǎng)絡(luò)中節(jié)點{V1,V3,V5}為故障狀態(tài)，則可用二進制編碼表示種群粒子M={1010111}.網(wǎng)絡(luò)G(N1)用鄰接矩陣A表示，若節(jié)點V1,V3,V5故障，則將矩陣A中第1行、第1列，第3行、第3列，第5行、第5列中所有元素置0.此時可得剩余網(wǎng)絡(luò)的鄰接矩陣A′.

3.2 粒子群算法參數(shù)設(shè)置

(2)

xid(t+1)=xid+vid(t+1)

(3)

其中：c1和c2是算法的兩個學習因子，通過調(diào)節(jié)c1可控制算法在全局尋優(yōu)方面的能力.c2可影響粒子向最優(yōu)結(jié)果運動的步長.算法在實際運用時一般令c1=c2=2.式(2)中r1、r2是區(qū)間(0,1)中的隨機自然數(shù).通過調(diào)節(jié)式中慣性因子w可以在保證全局尋優(yōu)結(jié)果的情況下平衡算法的局部尋優(yōu)收斂效果.并且選取合適的w值可以降低計算時間.根據(jù)算法所在的搜索時期，靈活的調(diào)節(jié)w值，當選取較大的w值可以提高算法的全局搜索能力；相反的，選取較小的w值可以提高算法搜索的分辨率，提高精度.每個粒子的慣性權(quán)重設(shè)置公式如下：

(4)

其中：wmax為慣性因子的最大值，wmin為慣性因子最小值，t為當前迭代次數(shù)，tmax為最大迭代次數(shù).

3.3 模擬退火算法參數(shù)設(shè)置

1)模擬退火算法中的初始溫度值是影響其全局搜索能力的重要因素[10].實際操作后發(fā)現(xiàn)二者之間呈正比，并且當計算時搜索結(jié)果越準確，計算時間也就越長，反之亦然.為了保證結(jié)果準確的前提下縮短計算時間，本文優(yōu)化了初始溫度的設(shè)置方法.算法中初始溫度由計算公式如下：

(5)

其中：fmax、fmix和Δf分別表示最大、最小目標函數(shù)適應(yīng)值及二者之間的差值；Pr值限定在區(qū)間[0.7，0.9]中，表示模擬退火算法的初始概率值.

2)算法中退火速度直接關(guān)系到在計算中算法全局搜索能力.計算時選取合適的T0，然后通過式(6)實現(xiàn)算法的退火過程.為了提高算法自身的動態(tài)調(diào)整機制，在衰變函數(shù)中加入調(diào)整系數(shù)，使衰變函數(shù)可以根據(jù)計算的收斂情況自適應(yīng)的調(diào)整衰變函數(shù).計算溫度衰變系數(shù)的公式如下：

(6)

其中：fpi為當前微粒的適應(yīng)度；favg為種群的平均適應(yīng)度值；μ為初始溫度的衰減系數(shù)；Tk為前一次迭代中微粒的溫度；N(0,1)高斯分布的隨機數(shù).

3.4 模擬退火粒子群優(yōu)化算法描述

模擬退火粒子群優(yōu)化算法的執(zhí)行過程由以下3部分組成.1粒子群算法參數(shù)設(shè)置；2在進化中采用式(2)、(3)使粒子在搜索過程中不斷靠近最優(yōu)解；3利用模擬退火算法搜索粒子群優(yōu)化算法的隨機生成的m個粒子的位置最優(yōu)值，通過不斷地反復(fù)迭代，得到算法最優(yōu)解.

1)隨機生成m個粒子作為初始種群，并且將每個粒子的位置初始化；設(shè)置每個粒子的慣性權(quán)重w、學習因子c1和c2，初始接受概率Pr，粒子速度Vmax.

2)通過下面公式計算每個粒子的初始化退火溫度和適應(yīng)度值：

3)根據(jù)步驟1)隨機生成的m粒子，用pbest表示這m個粒子的適應(yīng)度值.同時在這些最優(yōu)極值中選取粒子群的最優(yōu)值gbest.

4)檢驗算法計算結(jié)果是否滿足其結(jié)束條件.若達到要求則輸出計算后的結(jié)果；否則執(zhí)行循環(huán)部分，其中k是從1～M的循環(huán)次數(shù).

5)計算每個隨機生成的m個粒子的適應(yīng)度fpi(k)和相應(yīng)的平均適應(yīng)度函數(shù)favg(k).

6)若計算得出粒子的適應(yīng)度優(yōu)于原有個體極值pbest，則當前適應(yīng)度設(shè)置為pbest，選擇最優(yōu)個體極值作為群體極值gbest.

7)結(jié)合公式(2),(3)不斷計算更新各粒子的速度Vmax和飛行位置.

8)重新計算每個新粒子更新過速度和位置后的適應(yīng)度fpi(k+1)和平均適應(yīng)度favg(k+1).

9)計算粒子更新位置之后兩個位置所導(dǎo)致的適應(yīng)度值的變化Δf=fpi(k+1)-fpi(k+1)．若Δf<0則使用更新后的位置；否則仍然采用舊位置.

10)依據(jù)公式(6)代入個體適應(yīng)度和平均適應(yīng)度，從而得到溫度自動衰減系數(shù)ξ.

11)Tk+1=ξTk，k=k+1，ξ∈(0,1)，繼續(xù)執(zhí)行第4)步.

4 仿真分析

4.1 算法性能分析

為驗證算法有效性以及性能，本文采用文獻[7]中的兩種基本網(wǎng)絡(luò)結(jié)構(gòu).圖2(A)中的網(wǎng)絡(luò)有11個連接節(jié)點、15條連通邊，圖2(B)中的網(wǎng)絡(luò)有11個連接節(jié)點、11條連通邊.

圖2 兩種簡單網(wǎng)絡(luò)連接關(guān)系圖

在本文仿真分析中采用模擬退火粒子群優(yōu)化算法，其相關(guān)參數(shù)設(shè)置如下：其中起始種群數(shù)為50，算法迭代次數(shù)設(shè)為80，80次迭代后算法截止，慣性權(quán)重值w=0.4，學習因子c1=c2=1.5且Vmax=8.仿真結(jié)果如圖3、4所示.

圖3 基本網(wǎng)絡(luò)1仿真

圖4 基本網(wǎng)絡(luò)2仿真

經(jīng)計算網(wǎng)絡(luò)1對應(yīng)的割點集為{V1,V4,V5,V8,V9,V10}，{V1,V4,V5,V8,V10,V11}.則其對應(yīng)割點數(shù)為6，最大連通分支數(shù)為5，最大連通分支階數(shù)為1，則網(wǎng)絡(luò)1的生存性值為1.4.網(wǎng)絡(luò)2對應(yīng)的割點集為{V2,V5,V6,}，則其對應(yīng)割點數(shù)為3，最大連通分支數(shù)為3，最大連通分支階數(shù)為1，其生存性值為0.5.由韌性度的定義和計算結(jié)果可知，網(wǎng)絡(luò)1的生存性值大于網(wǎng)絡(luò)2，因此網(wǎng)絡(luò)1具有更好的可生存性.網(wǎng)絡(luò)1喪失通信能力需要6個節(jié)點同時出現(xiàn)故障，假設(shè)每個節(jié)點出現(xiàn)故障的概率相同，則網(wǎng)絡(luò)1失去通信能力的概率小于網(wǎng)絡(luò)2.在網(wǎng)絡(luò)設(shè)計時網(wǎng)絡(luò)1中{V1,V4,V5,V8,V9,V10,V11}7個節(jié)點，網(wǎng)絡(luò)2中{V2,V5,V6}3個節(jié)點應(yīng)增加冗余備份以提升網(wǎng)絡(luò)可生存性.網(wǎng)絡(luò)1在節(jié)點時效后剩余網(wǎng)絡(luò)的連通分支數(shù)大于網(wǎng)絡(luò)2，表明網(wǎng)絡(luò)1剩余部分的可恢復(fù)性強于網(wǎng)絡(luò)2.

4.2 仿真實例分析

本文以文獻[11]給出的深空探測信息網(wǎng)為例進行可生存性評估，此網(wǎng)絡(luò)目的是實現(xiàn)達到數(shù)據(jù)中繼，信息共享，相互協(xié)助共同完成深空探測.網(wǎng)絡(luò)之間的信息就是靠節(jié)點之間的無線連接來傳遞，因此網(wǎng)絡(luò)中節(jié)點的連接關(guān)系對網(wǎng)絡(luò)至關(guān)重要.其連接關(guān)系如圖5所示.

圖5 深空測控信息網(wǎng)絡(luò)連接關(guān)系圖

該網(wǎng)絡(luò)包含18個網(wǎng)絡(luò)節(jié)點31條邊.采用本文給出的算法經(jīng)過50次仿真取平均值，最后求得網(wǎng)絡(luò)3的生存性值為1.57，對應(yīng)的割點集為V1,V3,V4,V5,V8,V13,V14,V15,V17.最大連通分支數(shù)ω(N-S)為7，最大連通分支階數(shù)τ(N-S)為2.仿真結(jié)果如圖6所示.

圖6 深空測控信息網(wǎng)絡(luò)仿真

從可生存性角度對網(wǎng)絡(luò)3分析：最大連通分支階數(shù)較少，因此網(wǎng)絡(luò)中節(jié)點出現(xiàn)故障后相應(yīng)剩余網(wǎng)絡(luò)繼續(xù)通信的能力較低.最大連通分支數(shù)較多，應(yīng)當增加關(guān)鍵節(jié)點的通信鏈路以提高網(wǎng)絡(luò)的可恢復(fù)性.節(jié)點V1,V3,V4,V5,V8,V13,V14,V15,V17對于整個網(wǎng)絡(luò)的持續(xù)通信能力至關(guān)重要，針對這些節(jié)點設(shè)計應(yīng)急響應(yīng)方案具有最高的性價比，網(wǎng)絡(luò)設(shè)計組建階段應(yīng)當重點考慮.

5 結(jié) 語

本文研究了測控通信網(wǎng)絡(luò)的可生存性，并采用圖論理論中韌性度的概念結(jié)合可生存性抵抗能力、可恢復(fù)性、容錯性三方面性質(zhì)對深空測控通信網(wǎng)絡(luò)的可生存性進行了量化分析.在計算過程中對模擬退火粒子群算法進行了優(yōu)化，降低了韌性度計算的時間，與現(xiàn)有的遺傳算法相比本文所用算法計算更高效，并通過對控制參數(shù)的優(yōu)化，提高了算法全局尋優(yōu)的能力克服了傳統(tǒng)遺傳算法容易陷入局部最優(yōu)解的缺陷.最后本文通過對可生存性建模，并利用模退火粒子群優(yōu)化算法對模型進行求解，得出文獻[11]所提出的深空探測信息網(wǎng)絡(luò)的可生存性值，并對仿真結(jié)果進行分析給出了合理的設(shè)計、優(yōu)化建議.本文對深空探測測控通信網(wǎng)絡(luò)的設(shè)計提供了重要的理論依據(jù).

[1] 茍 亮，張更新，孫 偉，等.深空通信網(wǎng)發(fā)展與展望[J].數(shù)字通信世界，2012(1):54-59.

[2] 陳志國，張 強.國際空間站信息系統(tǒng)架構(gòu)綜述[J].載人航天，2011，17(1):5-9.

[3] 林雪綱, 許榕生, 熊 華,等. 一種信息系統(tǒng)生存性的量化分析框架[J]. 電子與信息學報, 2006, 28(9):1721-1726.

[4] 吳 俊,譚索怡,譚躍進,等.基于自然連通度的復(fù)雜網(wǎng)絡(luò)抗毀性分析[J].復(fù)雜系統(tǒng)與復(fù)雜性科學,2014,11(1):77-86.

[5] COZZENS M, MOAZZAMI D, STUECKLE S. The tenacity of a graph[C]//Proc of the 7th International Conference on the Theory and Applications of Graphs.NewYork: Wiley, 1995: 1111-1122.

[6] 王 玥,蔡皖東,段 琪.基于遺傳算法的網(wǎng)絡(luò)脆弱性計算方法[J].系統(tǒng)仿真學報,2009, 21(6):1628-1632.

[7] CHOUDUM SA,PRIYA N.Tenacity of complete graph prod-ucts and grids[J].Networks,1999,34(3):192-196.

[8] JIA S W,GAOY L.Hybridpartical swarm optimization algorithm merging simulated annealing and chaos[J].Computer Engineering and Applications,2009,45(7);52-55.

[9] PAN Quan-ke,WANG Wen-hong,ZHU Jian-ying.Effective hybrid heuristics based on partical swarm optimization and simulated annealing algorithm for job shop scheduling [J].China Mechanical Engineering ,2006,17(10):1004-1008.

[10] MOUSSI R, EUCHI J, YASSINE A,etal. A hybrid ant colony and simulated annealing algorithm to solve the container stacking problem at seaport terminal[J]. International Journal of Operational Research, 2015.

[11] 徐 瑞, 崔平遠, 張振江. 深空信息網(wǎng)分層骨干網(wǎng)布局方案[C]// 中國空間科學學會空間探測專業(yè)委員會第十九次學術(shù)會議論文集(上冊). 2006：218-227.