健壯性通信網絡的抗毀性

張小萌， 文昌俊

(1 湖北工業大學機械工程學院， 湖北 武漢 430068； 2 湖北省現代制造質量工程重點實驗室， 湖北 武漢 430068)

?

健壯性通信網絡的抗毀性

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

(1 湖北工業大學機械工程學院， 湖北 武漢 430068； 2 湖北省現代制造質量工程重點實驗室， 湖北 武漢 430068)

以全連通網絡為參考標準，以最短路徑數為評價指標，建立健壯性通信網絡的抗毀性模型，利用MATLAB提出一種新的計算最短路徑數的方法，通過實例進行計算，得出網絡的抗毀性。研究發現，拓撲結構越對稱，健壯性通信網絡的抗毀性越好。

抗毀性； 拓撲結構； 最短路徑數； 健壯性通信網絡； MATLAB

若干個拓撲節點構成的大型無線通信系統，使網絡節點間的信息交換以及傳遞更加快速、準確和方便。為了保證信息準確快速傳遞，對健壯性網絡可靠性的要求特別嚴格。但在網絡使用過程中，由于自然條件或者人為破壞，某些節點或是某些鏈路斷開可能嚴重影響到網絡拓撲結構的可靠性。抗毀性作為評價健壯性通信網絡可靠性的一個重要性能指標，在設計網絡的拓撲結構時應該把網絡的抗毀性考慮在其中。同時只有通過網絡抗毀性的計算，設計者才可知道網絡拓撲結構中有哪些節點和邊是比較重要的，需要進一步加固，使其不被外部條件破壞。

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

1　健壯性通信網絡的抗毀性評價

1.1參考標準

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

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

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

由圖1可以看出，依據抗毀性概念，對于有N個節點的全連通圖而言，任意去掉小于N-1個節點或者N-1邊，拓撲圖都是連通的，因此可以得出在所有網絡拓撲結構中抗毀性最強的是全連通網絡。另外，全連通圖分布均勻，對稱性強，結構緊湊，任意兩節點之間都能直接連接。但是在實際生活中，大多數通信網絡都是非全連通的(圖2)，主要是因為建立全連通網絡所耗費用較大。在實際網絡中，像通信網絡、社交網絡以及交通網絡等大型網絡都是在全連通網絡的基礎上改進的。因此，全連通網絡經常被作為評價實際網絡抗毀性的參考標準。

1.2評價方法

跳面節點法[6]論及評價網絡抗毀性的方法，因為側重點不同，評價方法有所差異，不適用于一些特殊的拓撲結構。例如在基于最小路徑數的網絡抗毀性中，文獻[10]指出了錯誤之處。

例如圖3所示的拓撲結構,當結構中存在多個割點時，利用生成樹法判斷節點的重要性就不準確。拓撲結構中3、4節點都是割點，利用生成樹方法判斷可知，不論是3節點還是4節點失效，都將造成拓撲結構不連通且生成樹數目均為0。所以，對于圖3所示的拓撲結構而言，節點3和4是同等重要。但很明顯，節點4上所連接的分支比節點3所連接的分支多，因此，在此拓撲結構中利用生成樹評價節點的重要性是不準確的。

圖 3　多割點圖

總結以上方法的不足，發現各個節點之間的信息傳遞，跳數較多的比跳數少的路徑可靠性差。另外，只有在最短路徑被破壞的情況下，系統才會選擇走相對較長的路徑。一個健壯性通信網絡中，最短路徑的數量越多，拓撲結構越緊湊，這個網絡的抗毀性就會越高。所以本文把最短路徑作為評價抗毀性的一個重要指標。因此，只要找到拓撲圖最短路徑的數量，就可以評價實際網絡拓撲結構的抗毀性。

對于N節點的拓撲結構的網絡，將節點vi到vj之間跳數最少的路徑稱為最短路徑[9]。

圖 4　簡單拓撲結構圖

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

2　網絡的抗毀度函數

2.1健壯性網絡的抗毀性理論模型

本文以最短路徑作為評價指標，全連通網絡作為評價標準，基于上述分析推出網絡抗毀性函數

(1)

式中：I為網絡的抗毀性；在節點總數為N的條件下，X為實際健壯性通信網絡拓撲結構中任意vi和vj兩點的之間的最短路徑總數，且

(2)

Y為全連通網絡拓撲結構中任意vi和vj兩點的之間的最短路徑總數。

根據經驗公式可知，節點數為N的全連通網絡最短路徑數

(3)

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

全連通網絡任意兩點之間的路徑總數

(4)

式中：抗毀性I以百分比表示，其越趨近于0，網絡拓撲結構抗毀性就越低；I越趨近于1，網絡拓撲結構抗毀性就越高。

2.2健壯性網絡的抗毀性求解

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

3　實例分析

分析圖5、圖6的網絡抗毀性。

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

G1(10,15)的鄰接陣

G2(10,15)的鄰接陣

利用MATLAB軟件計算得：I1=0.4142，I2=0.3999。通過對以上兩個連通圖的網絡抗毀性計算可以看出，對于相同節點、相同邊數，拓撲結構越對稱，節點分布越均勻，拓撲結構的抗毀性越強。

4　結束語

健壯性通信網絡拓撲結構比較復雜、節點多，全連通圖的拓撲結構分布均勻、對稱性強，抗毀性在常見網絡中最強。本文利用MATLAB軟件簡化了最短路徑的求法，直接輸入實際健壯性網絡的鄰接陣，可以從MATLAB軟件中得到結果，從而簡化求解抗毀性的步驟。此方法對于復雜網絡抗毀性計算簡單用時短。非賦權的有向網絡和無向網絡，都不能利用本文提出的方法求出抗毀性，因此，下一步研究將從網絡各節點的賦權和有向性等方面作更深入地考量。

[1]熊小萍.電力系統廣域通信網絡可靠性分析及優化設計[D].南寧：廣西大學,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]羅金龍.城市軌道交通網絡復雜性及演化分析[D].北京：北京交通大學,2013.

[6]陳建國.通信網絡拓撲結抗毀性評估法研究[J].通信系統與網絡技術，2006,32(1):6-8.

[7]郭偉.野戰地域通信網可靠性的評價方法[J].電子學報，2000,28(1):3-6.

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

[9]魏福林.野戰地域通信拓撲層抗毀性研究[D].鄭州：中國人民解放軍信息工程大學，2006.

[10] 饒育萍.基于最短路徑數的網絡抗毀性評價方法[J].通信學報，2009,30(4):113-116.[11] 周炯磐.通信網理論基礎[M].北京：人民郵電出版社，1991：94-96.

[責任編校： 張眾]

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-)，女，湖北武漢人，湖北工業大學碩士研究生，研究方向為可靠性工程

文昌俊(1970-)，男，湖北仙桃人，湖北工業大學教授，研究方向為質量與可靠性

1003-4684(2016)04-0038-03

TN915.02

A