基于廣度優(yōu)先搜索算法的復(fù)雜網(wǎng)絡(luò)可靠性分析

荊平 李永明 韋利春 高紅慧

摘要：要加強(qiáng)網(wǎng)絡(luò)的可靠性，需要對(duì)非葉子節(jié)點(diǎn)關(guān)聯(lián)的割邊進(jìn)行多重連接，本文給出了利用廣度優(yōu)先搜索算法尋找非葉子節(jié)點(diǎn)關(guān)聯(lián)的割邊算法，對(duì)網(wǎng)絡(luò)的割邊進(jìn)行加固。對(duì)加固后的網(wǎng)絡(luò)進(jìn)行了隨機(jī)故障和故意攻擊的測(cè)試，并給出了一些仿真結(jié)果。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；Prim算法；割邊；廣度優(yōu)先搜索算法；可靠性

1 引言

由于數(shù)據(jù)網(wǎng)絡(luò)日趨復(fù)雜、網(wǎng)絡(luò)規(guī)模日趨龐大,客觀、可靠地對(duì)網(wǎng)絡(luò)進(jìn)行規(guī)劃設(shè)計(jì)顯得愈發(fā)重要。因此,在沒(méi)有實(shí)際的路由實(shí)驗(yàn)環(huán)境下,一種有效的手段就是利用網(wǎng)絡(luò)仿真技術(shù)建立仿真平臺(tái)進(jìn)行仿真實(shí)驗(yàn)。網(wǎng)絡(luò)仿真中最重要的前提步驟就是構(gòu)造復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。實(shí)際中,在某一種特定網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上表現(xiàn)良好的路由協(xié)議或算法,在網(wǎng)絡(luò)拓?fù)浒l(fā)生重大變化或移植到另一個(gè)不同的網(wǎng)絡(luò)時(shí),往往不能表現(xiàn)同樣良好的性能并且不同的拓?fù)錁?gòu)造方法所生成的拓?fù)鋱D不同,因此對(duì)網(wǎng)絡(luò)的性能造成很大的影響,因此,為了仿真在真實(shí)網(wǎng)絡(luò)環(huán)境下的拓?fù)浣Y(jié)構(gòu)特性,需要構(gòu)造與真實(shí)網(wǎng)絡(luò)相同的拓?fù)浣Y(jié)構(gòu)，并對(duì)網(wǎng)絡(luò)進(jìn)行一些可靠分析，進(jìn)行隨機(jī)故障和故意攻擊的測(cè)試。

目前常用的網(wǎng)絡(luò)拓?fù)淠Ｐ桶ㄒ韵聨追N：（1）簡(jiǎn)單規(guī)則的拓?fù)浣Y(jié)構(gòu),如星型連接、環(huán)型連接、樹(shù)型連接、網(wǎng)格結(jié)構(gòu)等；（2）眾所周知的拓?fù)浣Y(jié)構(gòu), 如ARPANET,NFSNET,MCI主干域等；（3）隨機(jī)生成的拓?fù)浣Y(jié)構(gòu),如完全隨機(jī)網(wǎng)絡(luò)模型[1]，動(dòng)態(tài)隨機(jī)拓?fù)淠Ｐ蚚2,3],Waxman模型[4,5]等。本文利用度優(yōu)先準(zhǔn)則和距離優(yōu)先準(zhǔn)則構(gòu)造一類局域網(wǎng)作為測(cè)試局域網(wǎng)，求出網(wǎng)絡(luò)的割邊并進(jìn)行加固，最后對(duì)網(wǎng)絡(luò)進(jìn)行了測(cè)試。

2 測(cè)試局域網(wǎng)的構(gòu)造

測(cè)試局域網(wǎng)的構(gòu)造步驟如下，水平方設(shè)置m個(gè)點(diǎn)，垂直方向設(shè)置n個(gè)點(diǎn)，在平面上設(shè)置mn個(gè)網(wǎng)格節(jié)點(diǎn)。隨機(jī)地取N1個(gè)網(wǎng)格節(jié)點(diǎn)作為網(wǎng)絡(luò)的初始節(jié)點(diǎn)，節(jié)點(diǎn)（xi,yi）和節(jié)點(diǎn)（xj,yj）的距離為 接著利用Prim算法構(gòu)造這N1個(gè)節(jié)點(diǎn)的最小生成樹(shù)。然后執(zhí)行下面兩個(gè)步驟中的一個(gè)。

（1）以概率p（0≤p≤1）增加一個(gè)新節(jié)點(diǎn)。新節(jié)點(diǎn)與網(wǎng)絡(luò)中離它最近的m1（m≤m0）個(gè)節(jié)點(diǎn)相連接。

（2）以概率1-p增加一個(gè)新節(jié)點(diǎn)。新節(jié)點(diǎn)根據(jù)優(yōu)先連接概率

重復(fù)上面的（1），（2）操作，直到網(wǎng)絡(luò)中的節(jié)點(diǎn)總數(shù)達(dá)到N2時(shí)，算法終止。

仿真時(shí)參數(shù)的取值如下，m=n=100，N1=20，p=0.3，m1=3，m2=2，N2=100。仿真圖見(jiàn)圖1。Matlab軟件所畫(huà)的網(wǎng)絡(luò)圖，不便于觀察節(jié)點(diǎn)之間的關(guān)系，用Pajek軟件對(duì)圖1的網(wǎng)絡(luò)進(jìn)行可視化的效果見(jiàn)圖2。

3 隨機(jī)故障和故意攻擊的測(cè)試

為了測(cè)試我們構(gòu)造網(wǎng)絡(luò)的可靠性，隨機(jī)地刪除10%節(jié)點(diǎn)后，網(wǎng)絡(luò)仍然是連通的，效果圖見(jiàn)圖3。刪除度最高的10%節(jié)點(diǎn)后，網(wǎng)絡(luò)就不連通了，有多個(gè)分支，其效果圖見(jiàn)圖4，說(shuō)明網(wǎng)絡(luò)面臨故意攻擊，其樞紐很容易被破壞，從而造成網(wǎng)絡(luò)的崩潰。

4 結(jié)論

本文構(gòu)造了一種局域網(wǎng)，并用Matlab軟件進(jìn)行了仿真，為了加強(qiáng)網(wǎng)絡(luò)的可靠性，我們對(duì)網(wǎng)絡(luò)中的割邊進(jìn)行了加固，測(cè)試了所構(gòu)造的網(wǎng)絡(luò)對(duì)于隨機(jī)故障和故意攻擊的魯棒性。

用Matlab實(shí)現(xiàn)復(fù)雜網(wǎng)絡(luò)的仿真并不困難。與其它語(yǔ)言相比，Matlab語(yǔ)言有豐富的工具箱函數(shù)，能夠?qū)懗龊?jiǎn)約的代碼。對(duì)于非計(jì)算機(jī)專業(yè)的大學(xué)生、研究生和科研人員，能夠快速進(jìn)入復(fù)雜網(wǎng)絡(luò)前沿研究課題，對(duì)其科研能力的培養(yǎng)極為有益。

參考文獻(xiàn)

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

[2] 汪小帆，李祥，陳關(guān)榮，復(fù)雜網(wǎng)絡(luò)理論及應(yīng)用，北京：清華大學(xué)出版社[M]，2006: 27-29.

[3] 呂國(guó)英主編，任瑞征，錢(qián)宇華參編，算法設(shè)計(jì)與分析（第2版），清華大學(xué)出版社[M]，2009: 199.

作者簡(jiǎn)介：

荊平（1966-），山東煙臺(tái)人，煙臺(tái)南山學(xué)院電氣信息實(shí)驗(yàn)中心工程師，研究方向：自動(dòng)化。

李永明（1987-），山東菏澤人，煙臺(tái)南山學(xué)院助理實(shí)驗(yàn)師，技師，研究方向：機(jī)電一體化。

韋利春（1985－），男，漢族，山東德州人，本科，煙臺(tái)南山學(xué)院高級(jí)技師，研究方向?yàn)閷?shí)訓(xùn)教學(xué)。

高紅慧（1985－），女，漢族，吉林白城人，本科，煙臺(tái)南山學(xué)院助教/技師，研究方向?yàn)樽詣?dòng)化控制。