基于廣度優先搜索算法的復雜網絡可靠性分析

荊平 李永明 韋利春 高紅慧

摘要：要加強網絡的可靠性，需要對非葉子節點關聯的割邊進行多重連接，本文給出了利用廣度優先搜索算法尋找非葉子節點關聯的割邊算法，對網絡的割邊進行加固。對加固后的網絡進行了隨機故障和故意攻擊的測試，并給出了一些仿真結果。

關鍵詞：復雜網絡；Prim算法；割邊；廣度優先搜索算法；可靠性

1 引言

由于數據網絡日趨復雜、網絡規模日趨龐大,客觀、可靠地對網絡進行規劃設計顯得愈發重要。因此,在沒有實際的路由實驗環境下,一種有效的手段就是利用網絡仿真技術建立仿真平臺進行仿真實驗。網絡仿真中最重要的前提步驟就是構造復雜網絡的拓撲結構。實際中,在某一種特定網絡拓撲結構上表現良好的路由協議或算法,在網絡拓撲發生重大變化或移植到另一個不同的網絡時,往往不能表現同樣良好的性能并且不同的拓撲構造方法所生成的拓撲圖不同,因此對網絡的性能造成很大的影響,因此,為了仿真在真實網絡環境下的拓撲結構特性,需要構造與真實網絡相同的拓撲結構，并對網絡進行一些可靠分析，進行隨機故障和故意攻擊的測試。

目前常用的網絡拓撲模型包括以下幾種：（1）簡單規則的拓撲結構,如星型連接、環型連接、樹型連接、網格結構等；（2）眾所周知的拓撲結構, 如ARPANET,NFSNET,MCI主干域等；（3）隨機生成的拓撲結構,如完全隨機網絡模型[1]，動態隨機拓撲模型[2,3],Waxman模型[4,5]等。本文利用度優先準則和距離優先準則構造一類局域網作為測試局域網，求出網絡的割邊并進行加固，最后對網絡進行了測試。

2 測試局域網的構造

測試局域網的構造步驟如下，水平方設置m個點，垂直方向設置n個點，在平面上設置mn個網格節點。隨機地取N1個網格節點作為網絡的初始節點，節點（xi,yi）和節點（xj,yj）的距離為 接著利用Prim算法構造這N1個節點的最小生成樹。然后執行下面兩個步驟中的一個。

（1）以概率p（0≤p≤1）增加一個新節點。新節點與網絡中離它最近的m1（m≤m0）個節點相連接。

（2）以概率1-p增加一個新節點。新節點根據優先連接概率

重復上面的（1），（2）操作，直到網絡中的節點總數達到N2時，算法終止。

仿真時參數的取值如下，m=n=100，N1=20，p=0.3，m1=3，m2=2，N2=100。仿真圖見圖1。Matlab軟件所畫的網絡圖，不便于觀察節點之間的關系，用Pajek軟件對圖1的網絡進行可視化的效果見圖2。

3 隨機故障和故意攻擊的測試

為了測試我們構造網絡的可靠性，隨機地刪除10%節點后，網絡仍然是連通的，效果圖見圖3。刪除度最高的10%節點后，網絡就不連通了，有多個分支，其效果圖見圖4，說明網絡面臨故意攻擊，其樞紐很容易被破壞，從而造成網絡的崩潰。

4 結論

本文構造了一種局域網，并用Matlab軟件進行了仿真，為了加強網絡的可靠性，我們對網絡中的割邊進行了加固，測試了所構造的網絡對于隨機故障和故意攻擊的魯棒性。

用Matlab實現復雜網絡的仿真并不困難。與其它語言相比，Matlab語言有豐富的工具箱函數，能夠寫出簡約的代碼。對于非計算機專業的大學生、研究生和科研人員，能夠快速進入復雜網絡前沿研究課題，對其科研能力的培養極為有益。

參考文獻

[1] Bollobás B. Random Graphs, New York: Academic Press, 2nd ed., 2001.

[2] 汪小帆，李祥，陳關榮，復雜網絡理論及應用，北京：清華大學出版社[M]，2006: 27-29.

[3] 呂國英主編，任瑞征，錢宇華參編，算法設計與分析（第2版），清華大學出版社[M]，2009: 199.

作者簡介：

荊平（1966-），山東煙臺人，煙臺南山學院電氣信息實驗中心工程師，研究方向：自動化。

李永明（1987-），山東菏澤人，煙臺南山學院助理實驗師，技師，研究方向：機電一體化。

韋利春（1985－），男，漢族，山東德州人，本科，煙臺南山學院高級技師，研究方向為實訓教學。

高紅慧（1985－），女，漢族，吉林白城人，本科，煙臺南山學院助教/技師，研究方向為自動化控制。