健壯性通信網(wǎng)絡(luò)的抗毀性

張小萌， 文昌俊

(1 湖北工業(yè)大學(xué)機(jī)械工程學(xué)院， 湖北 武漢 430068； 2 湖北省現(xiàn)代制造質(zhì)量工程重點(diǎn)實(shí)驗(yàn)室， 湖北 武漢 430068)

?

健壯性通信網(wǎng)絡(luò)的抗毀性

張小萌1，2， 文昌俊1，2

(1 湖北工業(yè)大學(xué)機(jī)械工程學(xué)院， 湖北 武漢 430068； 2 湖北省現(xiàn)代制造質(zhì)量工程重點(diǎn)實(shí)驗(yàn)室， 湖北 武漢 430068)

以全連通網(wǎng)絡(luò)為參考標(biāo)準(zhǔn)，以最短路徑數(shù)為評(píng)價(jià)指標(biāo)，建立健壯性通信網(wǎng)絡(luò)的抗毀性模型，利用MATLAB提出一種新的計(jì)算最短路徑數(shù)的方法，通過實(shí)例進(jìn)行計(jì)算，得出網(wǎng)絡(luò)的抗毀性。研究發(fā)現(xiàn)，拓?fù)浣Y(jié)構(gòu)越對(duì)稱，健壯性通信網(wǎng)絡(luò)的抗毀性越好。

抗毀性； 拓?fù)浣Y(jié)構(gòu)； 最短路徑數(shù)； 健壯性通信網(wǎng)絡(luò)； MATLAB

若干個(gè)拓?fù)涔?jié)點(diǎn)構(gòu)成的大型無線通信系統(tǒng)，使網(wǎng)絡(luò)節(jié)點(diǎn)間的信息交換以及傳遞更加快速、準(zhǔn)確和方便。為了保證信息準(zhǔn)確快速傳遞，對(duì)健壯性網(wǎng)絡(luò)可靠性的要求特別嚴(yán)格。但在網(wǎng)絡(luò)使用過程中，由于自然條件或者人為破壞，某些節(jié)點(diǎn)或是某些鏈路斷開可能嚴(yán)重影響到網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的可靠性?？箽宰鳛樵u(píng)價(jià)健壯性通信網(wǎng)絡(luò)可靠性的一個(gè)重要性能指標(biāo)，在設(shè)計(jì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)時(shí)應(yīng)該把網(wǎng)絡(luò)的抗毀性考慮在其中。同時(shí)只有通過網(wǎng)絡(luò)抗毀性的計(jì)算，設(shè)計(jì)者才可知道網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中有哪些節(jié)點(diǎn)和邊是比較重要的，需要進(jìn)一步加固，使其不被外部條件破壞。

網(wǎng)絡(luò)抗毀性[1]一直是一個(gè)熱門問題，很多外國學(xué)者從連通度、粘聚度、中心度等方面著手分析，然而網(wǎng)絡(luò)抗毀性一直都是一個(gè)NP完全問題。Douglas R.White 和 Frank Harary提出了網(wǎng)絡(luò)連通度和凝聚度等問題[2]，另外Douglas R.Shier[3]基于圖理論提供了一種計(jì)算網(wǎng)絡(luò)可靠性的方法，Manchester.J[4]等人提出交通網(wǎng)絡(luò)的抗毀性。國內(nèi)的相關(guān)研究方向分為兩種：一是基于節(jié)點(diǎn)分析，如節(jié)點(diǎn)重要性評(píng)估，有生成樹法、網(wǎng)絡(luò)凝聚度等；二是基于全網(wǎng)的抗毀性分析，如刪除后最短路[5]。陳建[6]用均方差來度量節(jié)點(diǎn)的抗毀性值；郭偉[7]提出跳面節(jié)點(diǎn)法來研究通信網(wǎng)絡(luò)的抗毀性；趙靜嫻[8]提出基于不重疊路徑數(shù)的標(biāo)準(zhǔn)穩(wěn)定熵指標(biāo)來評(píng)價(jià)網(wǎng)絡(luò)抗毀性；魏福林[9]提出利用基于最小割集來衡量網(wǎng)絡(luò)的抗毀性；饒育萍[10]提出利用最短路徑來評(píng)價(jià)網(wǎng)絡(luò)抗毀性。

1　健壯性通信網(wǎng)絡(luò)的抗毀性評(píng)價(jià)

1.1參考標(biāo)準(zhǔn)

對(duì)于一個(gè)無向連通圖G=(V,E)，用集合V={v1,v2,v3,…,vn}表示無向連通圖的點(diǎn)集合。用集合E={e1,e2,…,e3}表示邊的集合。

定義1全連通圖：無向連通圖中，對(duì)于任意兩點(diǎn)vi和vj之間都有直接連接的圖(圖1)。否則，則稱為非連通圖。

圖 1　全連通圖　　　　圖 2　非全連通圖

由圖1可以看出，依據(jù)抗毀性概念，對(duì)于有N個(gè)節(jié)點(diǎn)的全連通圖而言，任意去掉小于N-1個(gè)節(jié)點(diǎn)或者N-1邊，拓?fù)鋱D都是連通的，因此可以得出在所有網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中抗毀性最強(qiáng)的是全連通網(wǎng)絡(luò)。另外，全連通圖分布均勻，對(duì)稱性強(qiáng)，結(jié)構(gòu)緊湊，任意兩節(jié)點(diǎn)之間都能直接連接。但是在實(shí)際生活中，大多數(shù)通信網(wǎng)絡(luò)都是非全連通的(圖2)，主要是因?yàn)榻⑷B通網(wǎng)絡(luò)所耗費(fèi)用較大。在實(shí)際網(wǎng)絡(luò)中，像通信網(wǎng)絡(luò)、社交網(wǎng)絡(luò)以及交通網(wǎng)絡(luò)等大型網(wǎng)絡(luò)都是在全連通網(wǎng)絡(luò)的基礎(chǔ)上改進(jìn)的。因此，全連通網(wǎng)絡(luò)經(jīng)常被作為評(píng)價(jià)實(shí)際網(wǎng)絡(luò)抗毀性的參考標(biāo)準(zhǔn)。

1.2評(píng)價(jià)方法

跳面節(jié)點(diǎn)法[6]論及評(píng)價(jià)網(wǎng)絡(luò)抗毀性的方法，因?yàn)閭?cè)重點(diǎn)不同，評(píng)價(jià)方法有所差異，不適用于一些特殊的拓?fù)浣Y(jié)構(gòu)。例如在基于最小路徑數(shù)的網(wǎng)絡(luò)抗毀性中，文獻(xiàn)[10]指出了錯(cuò)誤之處。

例如圖3所示的拓?fù)浣Y(jié)構(gòu),當(dāng)結(jié)構(gòu)中存在多個(gè)割點(diǎn)時(shí)，利用生成樹法判斷節(jié)點(diǎn)的重要性就不準(zhǔn)確。拓?fù)浣Y(jié)構(gòu)中3、4節(jié)點(diǎn)都是割點(diǎn)，利用生成樹方法判斷可知，不論是3節(jié)點(diǎn)還是4節(jié)點(diǎn)失效，都將造成拓?fù)浣Y(jié)構(gòu)不連通且生成樹數(shù)目均為0。所以，對(duì)于圖3所示的拓?fù)浣Y(jié)構(gòu)而言，節(jié)點(diǎn)3和4是同等重要。但很明顯，節(jié)點(diǎn)4上所連接的分支比節(jié)點(diǎn)3所連接的分支多，因此，在此拓?fù)浣Y(jié)構(gòu)中利用生成樹評(píng)價(jià)節(jié)點(diǎn)的重要性是不準(zhǔn)確的。

圖 3　多割點(diǎn)圖

總結(jié)以上方法的不足，發(fā)現(xiàn)各個(gè)節(jié)點(diǎn)之間的信息傳遞，跳數(shù)較多的比跳數(shù)少的路徑可靠性差。另外，只有在最短路徑被破壞的情況下，系統(tǒng)才會(huì)選擇走相對(duì)較長的路徑。一個(gè)健壯性通信網(wǎng)絡(luò)中，最短路徑的數(shù)量越多，拓?fù)浣Y(jié)構(gòu)越緊湊，這個(gè)網(wǎng)絡(luò)的抗毀性就會(huì)越高。所以本文把最短路徑作為評(píng)價(jià)抗毀性的一個(gè)重要指標(biāo)。因此，只要找到拓?fù)鋱D最短路徑的數(shù)量，就可以評(píng)價(jià)實(shí)際網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的抗毀性。

對(duì)于N節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)，將節(jié)點(diǎn)vi到vj之間跳數(shù)最少的路徑稱為最短路徑[9]。

圖 4　簡(jiǎn)單拓?fù)浣Y(jié)構(gòu)圖

對(duì)于圖4而言，任意兩點(diǎn)之間條數(shù)為1的最短路徑數(shù)量為7，分別為：v1→v2，v1→v3，v1→v4，v1→v5，v2→v3，v3→v4，v4→v5；任意兩點(diǎn)跳數(shù)為2的最短路徑數(shù)為3，分別為：v2→v4，v2→v5，v3→v5。

2　網(wǎng)絡(luò)的抗毀度函數(shù)

2.1健壯性網(wǎng)絡(luò)的抗毀性理論模型

本文以最短路徑作為評(píng)價(jià)指標(biāo)，全連通網(wǎng)絡(luò)作為評(píng)價(jià)標(biāo)準(zhǔn)，基于上述分析推出網(wǎng)絡(luò)抗毀性函數(shù)

(1)

式中：I為網(wǎng)絡(luò)的抗毀性；在節(jié)點(diǎn)總數(shù)為N的條件下，X為實(shí)際健壯性通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中任意vi和vj兩點(diǎn)的之間的最短路徑總數(shù)，且

(2)

Y為全連通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中任意vi和vj兩點(diǎn)的之間的最短路徑總數(shù)。

根據(jù)經(jīng)驗(yàn)公式可知，節(jié)點(diǎn)數(shù)為N的全連通網(wǎng)絡(luò)最短路徑數(shù)

(3)

式中：k表示跳數(shù)；Y(k)表示節(jié)點(diǎn)vi到vj之間跳數(shù)不大于k的所有路徑數(shù)。

全連通網(wǎng)絡(luò)任意兩點(diǎn)之間的路徑總數(shù)

(4)

式中：抗毀性I以百分比表示，其越趨近于0，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)抗毀性就越低；I越趨近于1，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)抗毀性就越高。

2.2健壯性網(wǎng)絡(luò)的抗毀性求解

為了求取網(wǎng)絡(luò)的抗毀性，必須先求出X,Y,和Q,由于已知實(shí)際健壯性網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中節(jié)點(diǎn)數(shù)N，由式(3)、(4)可分別求出Y和Q。因此，現(xiàn)在要解決的是要求出實(shí)際健壯性網(wǎng)絡(luò)最短路徑數(shù)X。由于實(shí)際健壯性通信網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)都比較復(fù)雜，節(jié)點(diǎn)多，利用饒育萍提出的鄰接陣的k次冪的方法求最短路徑比較耗時(shí)。另外，求最短路長的方法還有現(xiàn)在使用比較普遍的D算法和F算法[11]，但這兩種算法只能求最小路徑的長度，不能求最短路徑數(shù)的數(shù)量。因此，本文在D算法和F算法的基礎(chǔ)上，改進(jìn)了D算法和F算法，利用MATLAB軟件編程，在MATLAB的輸入端口，輸入實(shí)際健壯性通信網(wǎng)絡(luò)的鄰接陣，可以求出任意兩點(diǎn)之間的最短路徑數(shù)量。此方法不論網(wǎng)絡(luò)拓?fù)涫嵌嗝磸?fù)雜，都可以快速利用計(jì)算機(jī)得到抗毀性的數(shù)值。

3　實(shí)例分析

分析圖5、圖6的網(wǎng)絡(luò)抗毀性。

圖 5　連通圖G1　　　　　圖 6　連通圖G2

G1(10,15)的鄰接陣

G2(10,15)的鄰接陣

利用MATLAB軟件計(jì)算得：I1=0.4142，I2=0.3999。通過對(duì)以上兩個(gè)連通圖的網(wǎng)絡(luò)抗毀性計(jì)算可以看出，對(duì)于相同節(jié)點(diǎn)、相同邊數(shù)，拓?fù)浣Y(jié)構(gòu)越對(duì)稱，節(jié)點(diǎn)分布越均勻，拓?fù)浣Y(jié)構(gòu)的抗毀性越強(qiáng)。

4　結(jié)束語

健壯性通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)比較復(fù)雜、節(jié)點(diǎn)多，全連通圖的拓?fù)浣Y(jié)構(gòu)分布均勻、對(duì)稱性強(qiáng)，抗毀性在常見網(wǎng)絡(luò)中最強(qiáng)。本文利用MATLAB軟件簡(jiǎn)化了最短路徑的求法，直接輸入實(shí)際健壯性網(wǎng)絡(luò)的鄰接陣，可以從MATLAB軟件中得到結(jié)果，從而簡(jiǎn)化求解抗毀性的步驟。此方法對(duì)于復(fù)雜網(wǎng)絡(luò)抗毀性計(jì)算簡(jiǎn)單用時(shí)短。非賦權(quán)的有向網(wǎng)絡(luò)和無向網(wǎng)絡(luò)，都不能利用本文提出的方法求出抗毀性，因此，下一步研究將從網(wǎng)絡(luò)各節(jié)點(diǎn)的賦權(quán)和有向性等方面作更深入地考量。

[1]熊小萍.電力系統(tǒng)廣域通信網(wǎng)絡(luò)可靠性分析及優(yōu)化設(shè)計(jì)[D].南寧：廣西大學(xué),2013.

[2]Douglas R. White and Frank Harary. The cohesiveness of blocks in social networks: node connectivity and conditional density [J].Sociological Methodology,2011,31 (1):305-359.

[3]Douglas R.Shie.Network reliability and algebraic structures[M].New York ：Clarendon Press，1991.

[4]Manchester J. The evolution of transport network survivability [J]. Communications Magazine, IEEE,1990,37 (8):44-5.

[5]羅金龍.城市軌道交通網(wǎng)絡(luò)復(fù)雜性及演化分析[D].北京：北京交通大學(xué),2013.

[6]陳建國.通信網(wǎng)絡(luò)拓?fù)浣Y(jié)抗毀性評(píng)估法研究[J].通信系統(tǒng)與網(wǎng)絡(luò)技術(shù)，2006,32(1):6-8.

[7]郭偉.野戰(zhàn)地域通信網(wǎng)可靠性的評(píng)價(jià)方法[J].電子學(xué)報(bào)，2000,28(1):3-6.

[8]趙靜嫻.基于不重疊路徑熵的網(wǎng)絡(luò)抗毀性評(píng)估方法[J].計(jì)算機(jī)應(yīng)用研究，2015,32(3):825-827.

[9]魏福林.野戰(zhàn)地域通信拓?fù)鋵涌箽匝芯縖D].鄭州：中國人民解放軍信息工程大學(xué)，2006.

[10] 饒育萍.基于最短路徑數(shù)的網(wǎng)絡(luò)抗毀性評(píng)價(jià)方法[J].通信學(xué)報(bào)，2009,30(4):113-116.[11] 周炯磐.通信網(wǎng)理論基礎(chǔ)[M].北京：人民郵電出版社，1991：94-96.

[責(zé)任編校： 張眾]

The Invulnerability of Robust Communication Network

ZHANG Xiaomeng1，2，WEN Changjun1，2

(1SchoolofMechanicalEngin.,HubeiUniv.ofTech.,Wuhan430068,China；2HubeiProvincialKeyLaboratoryofModernManufacturingQualityEngin.,Wuhan430068,China)

Based on the fully connected network and the shortest path for evaluation index, the model of the robust communication network invulnerability is established. A new method of calculation of the shortest path is put forward by using MATLAB in this paper. By means of calculating the examples, the network of the invulnerability can be concluded. At the same time, the more symmetrical the robust communication network topology is, the better the invulnerability is.

invulnerability; topology; the shortest path; robust communication network; MATLAB

2016-03-15

張小萌(1990-)，女，湖北武漢人，湖北工業(yè)大學(xué)碩士研究生，研究方向?yàn)榭煽啃怨こ?/p>

文昌俊(1970-)，男，湖北仙桃人，湖北工業(yè)大學(xué)教授，研究方向?yàn)橘|(zhì)量與可靠性

1003-4684(2016)04-0038-03

TN915.02

A