通信網(wǎng)絡(luò)拓?fù)淇箽远攘磕Ｐ团c算法研究

通信網(wǎng)絡(luò)拓?fù)淇箽远攘磕Ｐ团c算法研究

0網(wǎng)絡(luò)拓?fù)淇箽栽u估技術(shù)抗癲癇能力是網(wǎng)絡(luò)抗癲癇能力的一個(gè)重要方面。多年來,網(wǎng)絡(luò)設(shè)計(jì)人員用不同的技術(shù)手段設(shè)計(jì)出諸多網(wǎng)絡(luò)拓?fù)鋱D,這些拓?fù)鋱D有些是針對物理拓?fù)浣Y(jié)構(gòu)的,有些是針對邏輯拓?fù)浣Y(jié)構(gòu)的。他們有一個(gè)共同特性,就是具有一定的抗毀性能。網(wǎng)絡(luò)拓?fù)淇箽詫τ谲娛峦ㄐ啪W(wǎng)絡(luò)具有極其重要的意義,因?yàn)槭紫溶娛峦ㄐ啪W(wǎng)絡(luò)是軍事行動的通信保障,可能受到敵方不同方式的打擊;其次,網(wǎng)絡(luò)拓?fù)淇箽允蔷W(wǎng)絡(luò)業(yè)務(wù)抗毀性的基礎(chǔ)。伴隨著抗毀網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)技術(shù),出現(xiàn)了網(wǎng)絡(luò)拓?fù)淇箽栽u估技術(shù)。研究人員從不同角度,以不同方式提出了一些網(wǎng)絡(luò)拓?fù)淇箽栽u估方法。研究網(wǎng)絡(luò)拓?fù)淇箽栽u估的目的就是判斷所設(shè)計(jì)的網(wǎng)絡(luò)拓?fù)鋱D是否具有所期望的抗毀性能。1評估模型1.1節(jié)點(diǎn)抗毀度的度量值國內(nèi)外關(guān)于網(wǎng)絡(luò)拓?fù)淇箽栽u估技術(shù)方面的研究大致分為以下幾個(gè)方面:1)基于綜合性的單一抗毀性度量的評估技術(shù)文獻(xiàn)中定義了一種綜合性網(wǎng)絡(luò)拓?fù)淇箽远攘?即抗毀連通度G,該連通度表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)團(tuán)之間可能通信路徑的平均值,并以此度量值對網(wǎng)絡(luò)拓?fù)涞目箽赃M(jìn)行了評估?？箽нB通度G是一個(gè)網(wǎng)絡(luò)拓?fù)淇箽跃C合性指標(biāo),該值宏觀上表示了被評估網(wǎng)絡(luò)拓?fù)涞目箽?沒有反映節(jié)點(diǎn)團(tuán)對之間通信路徑數(shù)量的個(gè)體差異。文獻(xiàn)提出了網(wǎng)絡(luò)拓?fù)淇箽Ф萭,該值表示網(wǎng)團(tuán)間可能建立的路徑總數(shù)p與網(wǎng)團(tuán)間要建立的通路s之比。該度量值也是一個(gè)綜合評價(jià)全網(wǎng)拓?fù)淇箽缘闹笜?biāo)。有的文獻(xiàn)定義了網(wǎng)絡(luò)凝聚度,即節(jié)點(diǎn)數(shù)與平均最短路徑乘積的倒數(shù),該值表示網(wǎng)絡(luò)中節(jié)點(diǎn)重要程度,也是一個(gè)綜合性指標(biāo)。文獻(xiàn)中首先定義了節(jié)點(diǎn)抗毀度,然后將各個(gè)節(jié)點(diǎn)抗毀度的平均值作為網(wǎng)絡(luò)抗毀度來評估網(wǎng)絡(luò)抗毀性,沒有表現(xiàn)出節(jié)點(diǎn)抗毀度量值的分散特性。2)基于多抗毀性度量值的評估技術(shù)基于多抗毀性度量值的評估技術(shù)是指在對網(wǎng)絡(luò)拓?fù)淇箽赃M(jìn)行評估時(shí),給出多個(gè)評估指標(biāo),例如,對網(wǎng)絡(luò)中所有(或部分)節(jié)點(diǎn)對之間通信路徑數(shù)量進(jìn)行評估、對網(wǎng)絡(luò)中所有(或部分)節(jié)點(diǎn)抗毀度量值進(jìn)行評估、對網(wǎng)絡(luò)中所有(或部分)鏈路的抗毀性度量值進(jìn)行評估等。這種評估技術(shù)充分體現(xiàn)了抗毀需求的特殊性要求,但是缺乏對這些度量值的分散程度的評估。從以上描述中可以看出,不管是單一度量值的綜合性評估技術(shù),還是多度量值的評估技術(shù),都沒有考慮各種度量值的分散性,而僅僅是對度量值進(jìn)行了均值處理或加權(quán)式均值處理。實(shí)際上,節(jié)點(diǎn)抗毀性度量值的分散特性具有較重要意義,它表示了網(wǎng)絡(luò)拓?fù)渲惺欠翊嬖陉P(guān)鍵節(jié)點(diǎn)或鏈路。對于軍事通信網(wǎng)絡(luò),如果存在關(guān)鍵(或比較關(guān)鍵)節(jié)點(diǎn)或鏈路,從純拓?fù)浣Y(jié)構(gòu)角度考慮,無疑他們將是敵方首選打擊目標(biāo)。因此,在網(wǎng)絡(luò)資源允許情況下,應(yīng)當(dāng)盡量避免出現(xiàn)關(guān)鍵節(jié)點(diǎn)或鏈路,使攻擊任何一個(gè)節(jié)點(diǎn)或鏈路對網(wǎng)絡(luò)拓?fù)湓斐傻膿p壞程度基本相同。1.2節(jié)點(diǎn)抗毀性度值的估計(jì)在網(wǎng)絡(luò)拓?fù)鋱D中,節(jié)點(diǎn)抗毀性度量值的均值體現(xiàn)了度量值取值平均的大小,是度量值的重要數(shù)字特征,但是只是知道平均值是不夠的,還應(yīng)該知道度量值的取值如何在其均值周圍變化,即刻劃度量值的分散程度。對于節(jié)點(diǎn)抗毀性度量值均值相同的兩個(gè)網(wǎng)絡(luò)拓?fù)?其度量值的波動程度可能是不同的。波動較小的網(wǎng)絡(luò)拓?fù)渲泄?jié)點(diǎn)的重要性差別較小,拓?fù)浔容^穩(wěn)定,沒有特別重要的節(jié)點(diǎn)。節(jié)點(diǎn)抗毀性度量值的均方差可以完全表示網(wǎng)絡(luò)拓?fù)渲懈鱾€(gè)度量值的波動特性。定義D(S)為網(wǎng)絡(luò)拓?fù)鋱D抗毀性量度,則:Ci,j,k表示對應(yīng)于節(jié)點(diǎn)i的節(jié)點(diǎn)對(j,k)之間所有穿越節(jié)點(diǎn)i的路徑數(shù)量;n表示網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù);Si表示第i個(gè)節(jié)點(diǎn)的抗毀性度量值;V表示節(jié)點(diǎn)對集合;(j,k)表示節(jié)點(diǎn)編號。2算法和模擬2.1求各個(gè)節(jié)點(diǎn)路徑數(shù)量對于給定的連通網(wǎng)絡(luò)拓?fù)鋱D,節(jié)點(diǎn)抗毀性度量值均方差D(S)的求解過程如下:①對于拓?fù)鋱D中的每個(gè)節(jié)點(diǎn),求所有節(jié)點(diǎn)對(不包括該節(jié)點(diǎn))之間所有穿越該節(jié)點(diǎn)的路徑數(shù)量,得到Ai;②這些路徑數(shù)量的平均值,得到A;③用每個(gè)節(jié)點(diǎn)求出的路徑數(shù)量除以路徑數(shù)量的平均值,得到Si;④求Si的平均值,得到;⑤最后,求解全網(wǎng)拓?fù)鋱D的節(jié)點(diǎn)抗毀性度量均方差D(S)。2.2節(jié)點(diǎn)抗毀性分析圖1(a)、1(b)、1(c)、1(d)、1(e)、1(f)表示了6個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖。這6個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖具有相同的節(jié)點(diǎn)數(shù)量和鏈路數(shù)量(消耗的網(wǎng)絡(luò)資源相同)。根據(jù)計(jì)算機(jī)的仿真計(jì)算,得到這6個(gè)網(wǎng)絡(luò)拓?fù)鋱D的節(jié)點(diǎn)抗毀性度量均方差值分別是:0.0,0.19,0.53,0.90,1.20和2.72?？梢钥闯鏊麄兊木讲顢?shù)值逐漸增大。比較這6個(gè)拓?fù)鋱D,可以得知拓?fù)鋱D1(a)具有最好的抗毀特性,其次,分別是圖1(b)、1(c)、1(d)、1(e)、1(f)。拓?fù)鋱D1(a)的節(jié)點(diǎn)抗毀性度量均方差值等于0,說明拓?fù)鋱D1(a)中的6個(gè)節(jié)點(diǎn)的重要性相同,或者說,該圖中6個(gè)節(jié)點(diǎn)的任何一個(gè)被破壞掉時(shí),對網(wǎng)絡(luò)拓?fù)涞膿p害程度是相同的,這也是光纖網(wǎng)絡(luò)拓?fù)錇楸ＷC一定抗毀性最起碼要構(gòu)成環(huán)形網(wǎng)絡(luò)的原因。拓?fù)鋱D1(f)非常接近星形網(wǎng)絡(luò),均方差值最大,這說明星形網(wǎng)絡(luò)拓?fù)涞目箽宰畈?。因?要使網(wǎng)絡(luò)拓?fù)渚哂休^好的抗毀性,應(yīng)當(dāng)避免采用星形或類似星形結(jié)構(gòu)。由表1可以看出,圖1(a)中各個(gè)節(jié)點(diǎn)抗毀性度量值相同,都等于1。圖1(b)、(c)、(d)、(e)和(f)中的節(jié)點(diǎn)抗毀性度量值不盡相同。例如,圖1(f)中節(jié)點(diǎn)2的度量值最大,其次是節(jié)點(diǎn)3,這說明節(jié)點(diǎn)2是一個(gè)至關(guān)重要的節(jié)點(diǎn),當(dāng)它被攻擊失效時(shí),除了節(jié)點(diǎn)3和7之間還可以通信外,其它節(jié)點(diǎn)都將變成孤立節(jié)點(diǎn)。圖2表示出對應(yīng)圖1的6種網(wǎng)絡(luò)拓?fù)鋱D的節(jié)點(diǎn)抗毀性度量值的分散特性。由圖2可以看出隨著網(wǎng)絡(luò)抗毀性度量值(均方差值)的增加(由0增加到2.72),節(jié)點(diǎn)抗毀性度量值分散性加大(以理想值1為中心),節(jié)點(diǎn)重要性程度差異變大。這說明均方差值準(zhǔn)確度量了網(wǎng)絡(luò)拓?fù)涞目箽?網(wǎng)絡(luò)拓?fù)淇箽栽胶?其方差值越小。顯然,理想方差值是0。3節(jié)點(diǎn)抗毀性度量本文首先回顧了目前普遍采用的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)抗毀性評估技術(shù),然后提出了一種新的網(wǎng)絡(luò)拓?fù)淇箽栽u估算法。該算法可以求出給定的連通網(wǎng)絡(luò)拓?fù)鋱D中各個(gè)節(jié)點(diǎn)的抗毀性度量值,以此為基礎(chǔ)進(jìn)一步得出全網(wǎng)抗毀性度量值(各節(jié)點(diǎn)抗毀性度量值均方差)。計(jì)算機(jī)仿真結(jié)果表明:網(wǎng)絡(luò)拓?fù)鋱D的節(jié)點(diǎn)抗毀性度量均方差值可以準(zhǔn)確表達(dá)出圖中各個(gè)節(jié)點(diǎn)的抗