荊平 李永明 韋利春 高紅慧

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

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

1 引言

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

目前常用的網(wǎng)絡(luò)拓?fù)淠Ｐ桶ㄒ韵聨追N：（1）簡單規(guī)則的拓?fù)浣Y(jié)構(gòu),如星型連接、環(huán)型連接、樹型連接、網(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]，動態(tài)隨機(jī)拓?fù)淠Ｐ蚚2,3],Waxman模型[4,5]等。本文利用度優(yōu)先準(zhǔn)則和距離優(yōu)先準(zhǔn)則構(gòu)造一類局域網(wǎng)作為測試局域網(wǎng)，求出網(wǎng)絡(luò)的割邊并進(jìn)行加固，最后對網(wǎng)絡(luò)進(jìn)行了測試。

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

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

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

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

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

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

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

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

4 結(jié)論

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

用Matlab實現(xiàn)復(fù)雜網(wǎng)絡(luò)的仿真并不困難。與其它語言相比，Matlab語言有豐富的工具箱函數(shù)，能夠?qū)懗龊喖s的代碼。對于非計算機(jī)專業(yè)的大學(xué)生、研究生和科研人員，能夠快速進(jìn)入復(fù)雜網(wǎng)絡(luò)前沿研究課題，對其科研能力的培養(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] 呂國英主編，任瑞征，錢宇華參編，算法設(shè)計與分析（第2版），清華大學(xué)出版社[M]，2009: 199.

作者簡介：

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

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

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

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