徐 野，袁邱偉

(沈陽理工大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 110159)

?

具備小世界網(wǎng)絡(luò)拓?fù)涮匦缘臒o線傳感器網(wǎng)絡(luò)魯棒性分析

徐 野，袁邱偉

(沈陽理工大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 110159)

無線傳感器網(wǎng)絡(luò)(WSN)傳感器節(jié)點數(shù)量多且分布廣，將復(fù)雜網(wǎng)絡(luò)理論引入無線傳感器網(wǎng)絡(luò)(WSN),對分析網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、發(fā)現(xiàn)其中隱藏的規(guī)律以及提高網(wǎng)絡(luò)性能具有十分重要的意義。根據(jù)LEACH分簇算法，通過將網(wǎng)絡(luò)中介數(shù)較小的鏈路刪除，構(gòu)建具備小世界網(wǎng)絡(luò)特性的無線傳感器網(wǎng)絡(luò)。提出基于網(wǎng)絡(luò)負(fù)載和冗余的傳感器網(wǎng)絡(luò)連通性的測度，在此基礎(chǔ)上給出無線傳感器網(wǎng)絡(luò)魯棒性分析的方法。針對兩種攻擊方法，隨機(jī)攻擊和蓄意攻擊，對基于小世界網(wǎng)絡(luò)模型的無線傳感器網(wǎng)絡(luò)魯棒性能進(jìn)行分析。仿真結(jié)果表明，減少網(wǎng)絡(luò)負(fù)載增加網(wǎng)絡(luò)冗余利于傳感器網(wǎng)絡(luò)魯棒性的增強(qiáng)。

復(fù)雜網(wǎng)絡(luò)；無線傳感器網(wǎng)絡(luò)；網(wǎng)絡(luò)負(fù)載；網(wǎng)絡(luò)冗余；魯棒分析

無線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)是由部署在監(jiān)測區(qū)域內(nèi)大量的、廉價的、微型的傳感器組成，通過無線通信方式形成的一個多跳的自組織的網(wǎng)絡(luò)系統(tǒng)[1]。通過無線傳感器網(wǎng)絡(luò)，人們可以感知客觀世界，豐富和擴(kuò)展了現(xiàn)有的網(wǎng)絡(luò)功能以及人們認(rèn)識客觀世界的能力。無線傳感器網(wǎng)絡(luò)由傳感器節(jié)點、匯聚節(jié)點和管理節(jié)點組成。在無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點將監(jiān)測收集的數(shù)據(jù)經(jīng)過多條路徑傳遞到匯聚節(jié)點，之后通過互聯(lián)網(wǎng)或衛(wèi)星送達(dá)管理節(jié)點。通常無線傳感器網(wǎng)絡(luò)所處的環(huán)境惡劣且節(jié)點眾多資源受限，傳感器節(jié)點很容易出現(xiàn)故障，導(dǎo)致整個網(wǎng)絡(luò)陷入癱瘓狀態(tài)，因此對無線傳感器網(wǎng)絡(luò)魯棒性的研究對于傳感器網(wǎng)絡(luò)的穩(wěn)定高效運行顯得尤為重要。

復(fù)雜網(wǎng)絡(luò)并非指具體的網(wǎng)絡(luò)，具體的網(wǎng)絡(luò)包括通訊網(wǎng)絡(luò)、Internet、交通網(wǎng)絡(luò)等，復(fù)雜網(wǎng)絡(luò)是對具體網(wǎng)絡(luò)的抽象，研究網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)形成機(jī)制及演化規(guī)律，描述復(fù)雜網(wǎng)絡(luò)內(nèi)部元素之間相互作用和關(guān)系的理論。復(fù)雜網(wǎng)絡(luò)有無標(biāo)度網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)、隨機(jī)圖、規(guī)則網(wǎng)絡(luò)等多種類型，其中最為典型的復(fù)雜網(wǎng)絡(luò)為小世界網(wǎng)絡(luò)[2]。Watts在1998年提出了小世界網(wǎng)絡(luò)模型，具有平均路徑長度小和聚類系數(shù)大的特點[3]，是一種從規(guī)則網(wǎng)絡(luò)向隨機(jī)網(wǎng)絡(luò)的過渡的網(wǎng)絡(luò)。網(wǎng)絡(luò)具有平均路徑長度小的特性，節(jié)點之間的數(shù)據(jù)傳輸通過較少的跳數(shù)就可完成，利于網(wǎng)絡(luò)路由機(jī)制的維護(hù)，同時降低網(wǎng)絡(luò)節(jié)點能量的消耗；網(wǎng)絡(luò)中節(jié)點的連通性可以用聚類系數(shù)來體現(xiàn)，小世界網(wǎng)絡(luò)聚類系數(shù)大的特點反映網(wǎng)絡(luò)內(nèi)部協(xié)作性高，降低網(wǎng)絡(luò)通信開銷，利于網(wǎng)絡(luò)的穩(wěn)定運行。

1 WSN魯棒性分析

小世界現(xiàn)象作為復(fù)雜網(wǎng)絡(luò)的一個重要特征，存在于網(wǎng)絡(luò)結(jié)構(gòu)中，相關(guān)研究人員對無線傳感器網(wǎng)絡(luò)是否存在小世界現(xiàn)象進(jìn)行了大量的研究，發(fā)現(xiàn)無線傳感器網(wǎng)絡(luò)也存在小世界現(xiàn)象[4]。在現(xiàn)實應(yīng)用中，根據(jù)小世界復(fù)雜網(wǎng)絡(luò)理論構(gòu)建無線傳感器網(wǎng)絡(luò)，將會提高無線傳感器網(wǎng)絡(luò)的魯棒性，改善網(wǎng)絡(luò)的整體性能。

1.1 WSN魯棒性

魯棒性[5](robustness)是指網(wǎng)絡(luò)節(jié)點移走后，網(wǎng)絡(luò)中的絕大部分節(jié)點仍然保持連通，網(wǎng)絡(luò)的結(jié)構(gòu)和性能能夠維持基本穩(wěn)定的能力。在大規(guī)模無線傳感器網(wǎng)絡(luò)中，單個節(jié)點的失效是不可避免的，即使尋找到了網(wǎng)絡(luò)中的失效節(jié)點也無能為力，這就需要構(gòu)建魯棒性強(qiáng)的無線傳感器網(wǎng)絡(luò)。無線傳感器網(wǎng)絡(luò)只有保證采集數(shù)據(jù)的覆蓋，才能確保數(shù)據(jù)結(jié)果的真實可靠，提高網(wǎng)絡(luò)的整體效率。為了更準(zhǔn)確、客觀地分析傳感器網(wǎng)絡(luò)的魯棒性，提出傳感器網(wǎng)絡(luò)魯棒性分析的新方法，充分考慮傳感器節(jié)點的度量特征、網(wǎng)絡(luò)的連通性、攻擊方式等相關(guān)因素對傳感器網(wǎng)絡(luò)魯棒性的影響。

1.2 節(jié)點的度和度分布

無線傳感器網(wǎng)絡(luò)節(jié)點的度為該節(jié)點與其他節(jié)點連接的數(shù)目，在傳感器網(wǎng)絡(luò)中，大部分節(jié)點地位性能相同，節(jié)點的度趨于一致。同時存在少數(shù)節(jié)點如簇頭節(jié)點、匯聚節(jié)點，在節(jié)點能量、通信能力、網(wǎng)絡(luò)優(yōu)先級等方面具有一定的優(yōu)勢，因此這些高性能的節(jié)點具有較大的節(jié)點度數(shù)。正常情況下，傳感器網(wǎng)絡(luò)中的節(jié)點不具有相同的度，常用度分布函數(shù)P(k)來描述度在網(wǎng)絡(luò)中的分布情況。計算公式為

(1)

式中，Ni(k)為度為k的節(jié)點數(shù)，N為節(jié)點總數(shù)。傳感器網(wǎng)絡(luò)中，每個節(jié)點的度數(shù)最小為0，最大為N-1 ，節(jié)點的度分布相加為1，即

(2)

在無線傳感器網(wǎng)絡(luò)中各節(jié)點的不平等性決定網(wǎng)絡(luò)中存在小世界現(xiàn)象，網(wǎng)絡(luò)中節(jié)點度數(shù)較大的節(jié)點擁有較強(qiáng)網(wǎng)絡(luò)性能，當(dāng)這些節(jié)點遭受到攻擊或干擾時，網(wǎng)絡(luò)會出現(xiàn)較大的異常，網(wǎng)絡(luò)的整體性能下降。

1.3 節(jié)點的介數(shù)與網(wǎng)絡(luò)負(fù)載

介數(shù)作為網(wǎng)絡(luò)的全局統(tǒng)計量，在無線傳感器網(wǎng)絡(luò)中反映節(jié)點或邊的重要性。如果傳感器節(jié)點之間有B條不同的最短路徑，其中有b條路徑經(jīng)過節(jié)點i在節(jié)點對的介數(shù)為b/B，節(jié)點i對所有節(jié)點對的介數(shù)之和稱為節(jié)點i的介數(shù)[6]。節(jié)點i的介數(shù)Bi的計算公式如下：

(3)

式中,njk代表節(jié)點j與節(jié)點k之間的最短路徑的數(shù)量；njk(i)代表在節(jié)點j與k之間的最短路徑經(jīng)過節(jié)點i的數(shù)量。研究結(jié)果表明，介數(shù)可以較好地反映節(jié)點在網(wǎng)絡(luò)中的重要性，可以此來研究無線傳感器網(wǎng)絡(luò)的魯棒性。

傳感器網(wǎng)絡(luò)中節(jié)點是沿著最短路徑進(jìn)行信息交換傳遞，可將節(jié)點的負(fù)載定義為該節(jié)點的介數(shù)，它反映了網(wǎng)絡(luò)中通過節(jié)點的最短路徑的數(shù)目。定義節(jié)點i的容量(可承載的最大負(fù)荷)正比于其初始負(fù)載L[7]，公式如下：

C=(1+θ)L

(4)

式中θ為網(wǎng)絡(luò)冗余，其取值范圍為[0，1]。在無線傳感器網(wǎng)絡(luò)的應(yīng)用中，通常都具有大量節(jié)點，而由于制造成本等問題,很難保證在使用過程中每一個節(jié)點的可靠性。如果網(wǎng)絡(luò)中的某一個節(jié)點遭遇故障，使得最短的路徑分布產(chǎn)生影響，進(jìn)而導(dǎo)致使得網(wǎng)絡(luò)上的每個節(jié)點上的負(fù)荷也產(chǎn)生影響。如果節(jié)點中的負(fù)荷無法承受自己最大的容量時，網(wǎng)絡(luò)就發(fā)生了故障，并引起所有的節(jié)點重新分配網(wǎng)絡(luò)中的負(fù)荷。

1.4 網(wǎng)絡(luò)的連通性

連通子圖看成是一個個小的集團(tuán)組合而成，小集團(tuán)定義為從一條隨機(jī)邊的一端出發(fā)搜索，通過這個端點能直接到達(dá)的所有節(jié)點的集合即為一個集團(tuán)。節(jié)點收到數(shù)會向周圍通信節(jié)點發(fā)出訪問信息，鄰居節(jié)點收到信息后根據(jù)一定算法決定自己是否變?yōu)榛顒庸?jié)點，同時向其他節(jié)點發(fā)出信息告知自身為活動節(jié)點，通過循環(huán)的節(jié)點信息發(fā)送確認(rèn)，建立起通信集團(tuán)。圖1為傳感器網(wǎng)絡(luò)連通子圖形成示意圖。

圖1 傳感器網(wǎng)絡(luò)連通子圖形成示意圖

令H1(x)為這些集團(tuán)分布的生成函數(shù)，通過一條邊去訪問某個節(jié)點時，定義與這個節(jié)點相連的其他邊的數(shù)目的分布生成函數(shù)為

(5)

式中qk表示與訪問節(jié)點相連的其他邊數(shù)目的歸一化的概率分布。

(6)

式中：[H1(x)]k表示由qk所確定的k條邊相連的k個集團(tuán)的大小之和的分布函數(shù)；x表示與隨機(jī)選擇的邊相連的一個節(jié)點；pk定義為與節(jié)點直接相連的邊的分布。每條邊的另一端連著其他的集團(tuán)，這些集團(tuán)的大小由函數(shù)H1(x)生成，任意取一個節(jié)點所在集團(tuán)的大小的生成函數(shù)為

(7)

(8)

(9)

式中：r對應(yīng)于網(wǎng)絡(luò)的一個分布指數(shù)，取值范圍為2

1.5 攻擊方式

在傳感器網(wǎng)絡(luò)中，魯棒性是衡量當(dāng)網(wǎng)絡(luò)中部分節(jié)點失效后的網(wǎng)絡(luò)連通狀況的性能指標(biāo)。一般針對傳感器網(wǎng)絡(luò)進(jìn)行的節(jié)點攻擊方式主要有以下兩種：隨機(jī)攻擊方式和蓄意攻擊方式。隨機(jī)攻擊方式，即完全隨機(jī)地去除網(wǎng)絡(luò)中的一部分節(jié)點后，網(wǎng)絡(luò)連通度的變化；蓄意攻擊方式，一般是有目標(biāo)地去除一些網(wǎng)絡(luò)中的關(guān)鍵節(jié)點,如度大的節(jié)點，通信流量較大的節(jié)點等。

2 小世界特性無線傳感器網(wǎng)絡(luò)的構(gòu)建

3 仿真與性能分析

圖2 具備小世界網(wǎng)絡(luò)特性的無線傳感器網(wǎng)絡(luò)的部分拓?fù)淠Ｐ?/p>

3.1 無線傳感器網(wǎng)絡(luò)在不同攻擊方式下魯棒性分析

在θ=0、ω=0(網(wǎng)絡(luò)空負(fù)載)情況下，取τ=0、τ=1觀察具有小世界網(wǎng)絡(luò)特性的無線傳感器網(wǎng)絡(luò)在確定攻擊和隨機(jī)攻擊下所表現(xiàn)的魯棒性，如圖3所示。

圖3 不同攻擊方式下傳感器網(wǎng)絡(luò)魯棒性能對比

由圖3可知，具有小世界網(wǎng)絡(luò)特性的無線傳感器網(wǎng)絡(luò)面對隨機(jī)性網(wǎng)絡(luò)攻擊表現(xiàn)出很強(qiáng)的魯棒性即使攻擊點數(shù)達(dá)到500點時，G仍在0.3以上，從而保證無線傳感器網(wǎng)絡(luò)的覆蓋率。在面對蓄意攻擊方式時，傳感器網(wǎng)絡(luò)模型也表現(xiàn)出高的魯棒性，在攻擊節(jié)點接近總點數(shù)的一半時，G保持在0.3，表明即使有目的攻擊傳感器網(wǎng)絡(luò)中比較重要的點時，具有小世界網(wǎng)絡(luò)特性的無線傳感器網(wǎng)絡(luò)仍能保證覆蓋率在0.3以上，確保網(wǎng)絡(luò)穩(wěn)定高效的運行。

3.2 傳感器網(wǎng)絡(luò)冗余對網(wǎng)絡(luò)魯棒性的分析

在上面分析的基礎(chǔ)上，通過改變網(wǎng)絡(luò)冗余，觀察網(wǎng)絡(luò)魯棒性的變化，上面的情形是在θ=0、ω=0(網(wǎng)絡(luò)空負(fù)載)情況下，當(dāng)ω=0不變，網(wǎng)絡(luò)冗余θ變?yōu)?時，研究傳感器網(wǎng)絡(luò)在不同攻擊方式下所表現(xiàn)出的魯棒性，如圖4所示。

圖4 增加網(wǎng)絡(luò)冗余傳感器網(wǎng)絡(luò)魯棒性能對比

由圖4可知，無論是隨機(jī)攻擊方式還是蓄意攻擊方式，網(wǎng)絡(luò)冗余θ為1時，傳感器網(wǎng)絡(luò)的魯棒性相比于原來網(wǎng)絡(luò)冗余θ為0時魯棒性能有所提高，表現(xiàn)為線段2、4相較于線段1、3普遍右移。同樣的攻擊方式，網(wǎng)絡(luò)冗余的增加，處理數(shù)據(jù)的能力增強(qiáng)，傳感器網(wǎng)絡(luò)的魯棒性能有所提高，網(wǎng)絡(luò)整體呈現(xiàn)較強(qiáng)的魯棒性。

3.3 節(jié)點負(fù)載對網(wǎng)絡(luò)魯棒性的分析

現(xiàn)實中，無線傳感器網(wǎng)絡(luò)在工作中，需要對接受的數(shù)據(jù)進(jìn)行分析處理，同時將處理后的數(shù)據(jù)發(fā)送到下一節(jié)點，在此過程中網(wǎng)絡(luò)是有負(fù)載的。為進(jìn)一步真實反映具有小世界特性的無線傳感器網(wǎng)絡(luò)的魯棒性能，網(wǎng)絡(luò)冗余θ為1不變、ω=1(網(wǎng)絡(luò)滿載)情況下，真實的傳感器網(wǎng)絡(luò)在不同攻擊方式下表現(xiàn)出的魯棒性，如圖5所示。

圖5 增加節(jié)點負(fù)載傳感器網(wǎng)絡(luò)魯棒性能對比

由圖5可知，當(dāng)傳感器網(wǎng)絡(luò)工作時，對傳感器網(wǎng)絡(luò)進(jìn)行隨機(jī)攻擊和蓄意攻擊，網(wǎng)絡(luò)所表現(xiàn)出的魯棒性比網(wǎng)絡(luò)空載時魯棒性低，在這種情況下無論采取何種方式的攻擊線段3、4相較于線段1、2普遍左移，意味著在攻擊節(jié)點數(shù)比原來大大減少的情況下，傳感器網(wǎng)絡(luò)面臨崩潰，網(wǎng)絡(luò)所表現(xiàn)出的魯棒性大大降低。由以上仿真結(jié)果可知，傳感器網(wǎng)絡(luò)在攻擊模式確定的情況下，提高網(wǎng)絡(luò)冗余、降低網(wǎng)絡(luò)負(fù)載可以增強(qiáng)傳感器網(wǎng)絡(luò)魯棒特性，延長網(wǎng)絡(luò)生存周期。表1為網(wǎng)絡(luò)負(fù)載、網(wǎng)絡(luò)冗余對傳感器網(wǎng)絡(luò)魯棒性能的影響。

表1 網(wǎng)絡(luò)負(fù)載、網(wǎng)絡(luò)冗余對傳感器網(wǎng)絡(luò)魯棒性能的影響

由表1可知，相同的攻擊方式以及網(wǎng)絡(luò)負(fù)載(τ=0、w=0),網(wǎng)絡(luò)冗余增加可以增強(qiáng)傳感器網(wǎng)絡(luò)的魯棒特性；相同的攻擊方以及網(wǎng)絡(luò)冗余(τ=0、θ=1)，降低網(wǎng)絡(luò)負(fù)載同樣可以提高傳感器網(wǎng)絡(luò)的魯棒特性。

4 結(jié)論

將復(fù)雜網(wǎng)絡(luò)理論引入無線傳感器網(wǎng)絡(luò)，研究具有小世界特性的無線傳感器網(wǎng)絡(luò)魯棒特性，給出無線傳感器網(wǎng)絡(luò)連通性的新測度和無線傳感器網(wǎng)絡(luò)魯棒性分析的新方法。仿真結(jié)果表明：具有小世界特性的無線傳感器網(wǎng)絡(luò)面對隨機(jī)攻擊和蓄意攻擊兩種網(wǎng)絡(luò)攻擊方式表現(xiàn)出較強(qiáng)魯棒性，能夠很好保障傳感器網(wǎng)絡(luò)穩(wěn)定高效地運行。對網(wǎng)絡(luò)冗余和負(fù)載對傳感器網(wǎng)絡(luò)魯棒性影響的研究中發(fā)現(xiàn)，提高網(wǎng)絡(luò)冗余、降低網(wǎng)絡(luò)負(fù)載可以提高傳感器網(wǎng)絡(luò)的魯棒特性，為現(xiàn)實中傳感器網(wǎng)絡(luò)的合理構(gòu)建提供了新的思路。

[1]孫利民,李建中,陳渝.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005:3-4.

[2]方錦清,汪小帆,鄭志剛.一門嶄新的交叉科學(xué):網(wǎng)絡(luò)科學(xué)[J].物理學(xué)進(jìn)展,2007,27 (3):229-343.

[3]Watts D J.Collective dynamics of “small-world” networks[J].Nature,1998,393 (6684):440-442.

[4]HELMY A.Small worlds in wireless networks[J].IEEE Communication Letters,2003,7 (10):490-492.

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

[6]Rahul C Shah,Jan M Rabaey.Energy Aware Routing for Low Energy AdHoc Sensor Networks[J].Proe IEEE Wireless Communications and Networking Conference(WCNC),March,2002,l (3):17-21.

[7]Motter A E,Nishikawa T,Lai Y C.Cascade-based attacks on complex networks[J].Physical Review E,2002,66 (2):1-4.

[8]Heinzelman W R,Chandrakasan A,Blakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rd Annual Hawaiv International Conference on System Sciences.IEEE Computer Society,San Francisco,2000:3005-2014.

(責(zé)任編輯：馬金發(fā))

Research of Wireless Sensor Network Fault Detection

XU Ye,YUAN Qiuwei

(Shenyang Ligong University,Shenyang 110159,China)

Wireless sensor network is characterized by numerous nodes and wide distribution.The application of complex network theory to WSN is very significant to analyze network topology,find hidden rule and improve network performance of WSN.According to LEACH clustering algorithm,a wireless sensor network is built，which has a small-world network characteristics,and the network construction may remove smaller betweenness links.A new measure of wireless sensor network robustness is proposed.The new method to analyze the robustness of wireless sensor network on the basis of the above.For two different damages,random attacks and deliberate attacks,the robustness of wireless sensor networks is studied by the small-world model.Simulation results indicate that network load reducing increases the robustness of wireless sensor networks in favor of enhanced redundancy.

complex network;wireless sensor network;robustness analysis;network redundant;robustness analysis

2015-06-29

國家自然科學(xué)基金資助項目(61373159)；沈陽市科技應(yīng)用基礎(chǔ)研究計劃資助項目(F13-316-1-22)

徐野(1976—)，男，教授，博士，研究方向：復(fù)雜互聯(lián)系統(tǒng)與大規(guī)模網(wǎng)絡(luò)。

1003-1251(2016)04-0007-05

TP393

A