基于復(fù)雜網(wǎng)絡(luò)的無線傳感器網(wǎng)絡(luò)能量脆弱性分析*

吳 蔣， 王 冬

(1.中南大學(xué) 軟件學(xué)院,湖南 長沙 410083; 2.瓊州學(xué)院 電子信息工程學(xué)院,海南 三亞 572022)

0 引 言

由于無線傳感器網(wǎng)絡(luò)(WSNs)中的傳感器節(jié)點(diǎn)能量嚴(yán)重受限而且部署后難以回收，因而,針對(duì)無線傳感器網(wǎng)絡(luò)的能量效率的研究一直是該領(lǐng)域的熱點(diǎn)和難點(diǎn)。無線傳感器網(wǎng)絡(luò)鏈路中，諸如：突發(fā)大流量、自然災(zāi)害、人為破壞、節(jié)點(diǎn)能量失效等突發(fā)事件可能會(huì)導(dǎo)致某條鏈路斷開，從而影響網(wǎng)絡(luò)通信的全局效率。不同節(jié)點(diǎn)能量失效引起全局網(wǎng)絡(luò)效率變化的大小稱為節(jié)點(diǎn)的脆弱性。分析無線傳感網(wǎng)的網(wǎng)絡(luò)拓?fù)湫圆⒍坑?jì)算各個(gè)節(jié)點(diǎn)的脆弱性以采取相應(yīng)對(duì)策預(yù)防網(wǎng)絡(luò)癱瘓，對(duì)保障整個(gè)無線傳感器網(wǎng)絡(luò)的通信暢通有重要意義。

國內(nèi)外學(xué)者利用復(fù)雜網(wǎng)絡(luò)理論，已對(duì)無線傳感器網(wǎng)絡(luò)做過大量研究。陳力軍等人[1]借助于復(fù)雜網(wǎng)絡(luò)理論，提出了一種基于隨機(jī)行走的無線傳感器網(wǎng)絡(luò)簇間拓?fù)溲莼Ｐ?。該模型?duì)完善無線傳感器網(wǎng)絡(luò)的容錯(cuò)機(jī)制起到了積極的作用，可防止節(jié)點(diǎn)出現(xiàn)因能量的耗盡而失效或鏈路因網(wǎng)絡(luò)的入侵而失靈的現(xiàn)象。張成才等人[2]對(duì)無線傳感器網(wǎng)絡(luò)的聯(lián)通性展開研究，結(jié)果表明增加通信半徑則可以迅速地使網(wǎng)絡(luò)聯(lián)通。Guidoni D L等人[3]曾用小世界網(wǎng)絡(luò)特性應(yīng)用于無線傳感網(wǎng)絡(luò)的研究。以上學(xué)者側(cè)重于研究無線傳感器網(wǎng)絡(luò)的整體效率變化情況，缺乏對(duì)每個(gè)節(jié)點(diǎn)脆弱性的定量分析。筆者在描述復(fù)雜網(wǎng)絡(luò)理論的基礎(chǔ)上，確定定量化評(píng)價(jià)節(jié)點(diǎn)脆弱性的指標(biāo)，并以文獻(xiàn)[4]網(wǎng)絡(luò)為例，使用Space D法構(gòu)造其拓?fù)渚W(wǎng)絡(luò)，并用Matlab分析節(jié)點(diǎn)度、平均路徑長度、聚類系數(shù)等指標(biāo)和分布規(guī)律，最后定量計(jì)算各個(gè)節(jié)點(diǎn)能量消耗的脆弱性，以確定其中的關(guān)鍵節(jié)點(diǎn)，為維護(hù)和優(yōu)化提供科學(xué)依據(jù)。

1 無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量脆弱性分析

1.1 復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)參數(shù)

1998年，Watts D J等人[5]提出著名的小世界網(wǎng)絡(luò)概念，1999 年，Barabbsi A L等人提出無標(biāo)度網(wǎng)絡(luò)的概念。可以做這樣一個(gè)假設(shè)，就是將系統(tǒng)內(nèi)部的各個(gè)元素的關(guān)系作為連接，把元素視為節(jié)點(diǎn)，那么系統(tǒng)就形成了一個(gè)網(wǎng)絡(luò)，例如：大量隨機(jī)節(jié)點(diǎn)通過簇頭進(jìn)行通信而組成的網(wǎng)絡(luò)稱之為無線傳感器網(wǎng)絡(luò)；神經(jīng)網(wǎng)絡(luò)的形成被看作是大量神經(jīng)細(xì)胞通過神經(jīng)纖維相互連接的結(jié)果；計(jì)算機(jī)網(wǎng)絡(luò)被認(rèn)為是計(jì)算機(jī)通過各種通信介質(zhì)相互連接形成的網(wǎng)絡(luò)，如光纜、雙絞線、同軸電纜等；類似的還有人際關(guān)系網(wǎng)絡(luò)、水利樞紐網(wǎng)絡(luò)、火車軌道網(wǎng)絡(luò)、公路交通網(wǎng)絡(luò)等[6，7]。復(fù)雜網(wǎng)絡(luò)的研究思路主要是強(qiáng)調(diào)系統(tǒng)的結(jié)構(gòu)，值得注意的是從結(jié)構(gòu)角度來分析系統(tǒng)的功能，區(qū)別在于這些抽象的真實(shí)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)性質(zhì)和以往研究的網(wǎng)絡(luò)不同，節(jié)點(diǎn)眾多是其特點(diǎn)。關(guān)于復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)特點(diǎn)所描述的統(tǒng)計(jì)特征有很多,例如：最短路徑、介數(shù)、平均度、聚類系數(shù)、平均距離、相關(guān)系數(shù)、連通片分布等，其中，有3個(gè)統(tǒng)計(jì)特征最尤為重要，即度、聚類系數(shù)和平均路徑長度，下面就對(duì)此做簡要的說明。

1.1.1 節(jié)點(diǎn)度與度分布

圖論中與i節(jié)點(diǎn)連接的其他節(jié)點(diǎn)的數(shù)目ki，也可定義為i節(jié)點(diǎn)的度，從直覺上，一個(gè)節(jié)點(diǎn)的度越大就表示該節(jié)點(diǎn)在某種程度上越重要。正常情況下，大部分的節(jié)點(diǎn)都不具有相同的度，常用分布函數(shù)p(k)來描述度在網(wǎng)絡(luò)中的分布情況，p(k)表示一個(gè)隨機(jī)選定節(jié)點(diǎn)的度剛好是k的概率。節(jié)點(diǎn)度的分布特征往往被視為網(wǎng)絡(luò)的重要幾何性質(zhì)，規(guī)則性網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的度值是一樣的，與Delta分布相吻合，隨機(jī)網(wǎng)絡(luò)的度分布與Poisson分布相類似，絕大部分的現(xiàn)實(shí)網(wǎng)絡(luò)存在冪律形式的度分布，稱之為無標(biāo)度網(wǎng)絡(luò)[8～10]，同時(shí)還有很多網(wǎng)絡(luò)的度分布局限于指數(shù)分布。

1.1.2 聚類系數(shù)

很顯然，假設(shè)網(wǎng)絡(luò)G中一個(gè)節(jié)點(diǎn)i有ei條邊與另外ki個(gè)節(jié)點(diǎn)連接，該ki個(gè)節(jié)點(diǎn)就稱為節(jié)點(diǎn)i的鄰居。顯然，該ki個(gè)節(jié)點(diǎn)間最多可能有ki(ki-1)/2條邊，ki個(gè)節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)Ei與總的可能邊數(shù)的比值定義為節(jié)點(diǎn)i的聚類系數(shù)Ci，網(wǎng)絡(luò)中所有節(jié)點(diǎn)i的聚類系數(shù)的平均值就是網(wǎng)絡(luò)的聚類系數(shù)，用C表示，即

(1)

(2)

1.1.3 平均路徑長度

網(wǎng)絡(luò)G中2個(gè)節(jié)點(diǎn)i和j之間的距離dij定義為連接這2個(gè)節(jié)點(diǎn)的最短路徑的邊數(shù)。對(duì)于一個(gè)無向網(wǎng)絡(luò)，定義平均路徑長度L為網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)之間距離dij的平均值

(3)

式中N為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)。網(wǎng)絡(luò)的平均路徑長度用來衡量網(wǎng)絡(luò)節(jié)點(diǎn)間的離散程度，也被稱為網(wǎng)絡(luò)的特征路徑長度。研究表明，盡管許多實(shí)際網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)巨大，但網(wǎng)絡(luò)的平均路徑長度L相對(duì)于N來說卻很小，這種現(xiàn)象稱之為“小世界效應(yīng)[5]”。

1.2 無線傳感器網(wǎng)絡(luò)構(gòu)建

根據(jù)文獻(xiàn)[1]，假設(shè)所有簇頭的最大通信半徑可控，各個(gè)水源地入口相鄰的簇頭都在最大通信半徑內(nèi)，Space D拓?fù)浣Y(jié)構(gòu)模型即把簇頭視為節(jié)點(diǎn)，若某一線路上的2個(gè)簇頭是相鄰的，它們之間就有通信鏈路，如圖1所示。

圖1 Space D網(wǎng)絡(luò)構(gòu)建方法

在無線傳感器網(wǎng)絡(luò)中，簇頭和通信鏈路是基本的組成元素，鏈路連接著簇頭節(jié)點(diǎn)相互感知和轉(zhuǎn)發(fā)數(shù)據(jù)，因此，無線傳感器網(wǎng)絡(luò)可看成由鏈路和簇頭所構(gòu)成的復(fù)雜網(wǎng)絡(luò)。這里可以定義為:無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)代表通信鏈路中的簇頭，邊代表各簇頭之間的鏈路,這樣，由很多的邊和點(diǎn)組成的網(wǎng)絡(luò)就構(gòu)成了無線傳感器網(wǎng)絡(luò)的基本框架。

1.3 無線傳感器網(wǎng)絡(luò)脆弱性分析

脆弱性可以解釋為：受事件影響而使服務(wù)水平降低的敏感系數(shù)。無線傳感器網(wǎng)絡(luò)的脆弱性則可定義為不同簇頭節(jié)點(diǎn)在能量耗盡而影響無線傳感器網(wǎng)絡(luò)全局效率的大小。節(jié)點(diǎn)能量消耗與通信量大小有關(guān)，而通信量的大小可隨路由選擇的隨機(jī)性有莫大的關(guān)系。因此，對(duì)于無線傳感器網(wǎng)絡(luò)，研究隨機(jī)失效節(jié)點(diǎn)的脆弱性有助于識(shí)別脆弱環(huán)節(jié)并采取相應(yīng)對(duì)策以預(yù)防整個(gè)網(wǎng)絡(luò)癱瘓的發(fā)生。筆者通過計(jì)算文獻(xiàn)[1]網(wǎng)絡(luò)效率，來描述其脆弱性。網(wǎng)絡(luò)效率E是用于度量網(wǎng)絡(luò)中節(jié)點(diǎn)交換信息的效率。定義G的平均網(wǎng)絡(luò)效率之前，需要計(jì)算任意2點(diǎn)間的最短路徑{dij}。設(shè)定頂點(diǎn)i和j之間的效率為最短路徑的倒數(shù)eij=1/dij，當(dāng)i和j之間沒有邊連接時(shí)，dij=+∞，eij=0，這樣，G的平均網(wǎng)絡(luò)效率可以定義為

(4)

當(dāng)E值很大時(shí)，表明網(wǎng)絡(luò)效率很高且連通性很好。當(dāng)節(jié)點(diǎn)i能量耗盡失效后，網(wǎng)絡(luò)遭到破壞，網(wǎng)絡(luò)效率也受到影響，不同節(jié)點(diǎn)失效時(shí)引起網(wǎng)絡(luò)效率的變化大小不同，即脆弱性不同，則第i個(gè)節(jié)點(diǎn)的脆弱性ΔE定義為

(5)

2 文獻(xiàn)[4]網(wǎng)絡(luò)實(shí)證研究

2.1 文獻(xiàn)[4]網(wǎng)絡(luò)結(jié)構(gòu)

本文用Space D方法對(duì)三亞半嶺水庫水質(zhì)監(jiān)控網(wǎng)絡(luò)進(jìn)行拓?fù)浣＃負(fù)浜缶W(wǎng)絡(luò)如圖2所示。

圖2 三亞半嶺水庫水質(zhì)監(jiān)控網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

2.2 文獻(xiàn)[4]網(wǎng)絡(luò)的統(tǒng)計(jì)特性與分析

本文對(duì)三亞半嶺水庫的各個(gè)監(jiān)測(cè)點(diǎn)采用的是環(huán)形的節(jié)點(diǎn)布置方式，相鄰節(jié)點(diǎn)的數(shù)據(jù)鏈路唯一，某節(jié)點(diǎn)一旦失效，其數(shù)據(jù)接收為0或該節(jié)點(diǎn)效率逐漸降低趨向于0。對(duì)文獻(xiàn)[4]網(wǎng)絡(luò)分別計(jì)算其網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)、邊數(shù)、平均度、平均路徑長度和聚類系數(shù)，結(jié)果見表1。

表1 特征指標(biāo)值

環(huán)形節(jié)點(diǎn)布置方式方便于計(jì)算，從表1可知，一共布置了36個(gè)監(jiān)測(cè)節(jié)點(diǎn)，36條連接邊，每個(gè)節(jié)點(diǎn)與2個(gè)相鄰節(jié)點(diǎn)直接連接，平均鏈路長度為9.25，并擁有較小的聚類系數(shù)，同時(shí)有較小的鏈路長度。根據(jù)拓?fù)鋱D，計(jì)算得到其平均聚類系數(shù)為0。

2.3 節(jié)點(diǎn)能量耗盡時(shí)網(wǎng)絡(luò)的脆弱性

對(duì)文獻(xiàn)[4]網(wǎng)絡(luò)的36個(gè)節(jié)點(diǎn)進(jìn)行電池更換，該電池能量為即將耗盡的電池，并用式(4)計(jì)算更換電池后的網(wǎng)絡(luò)效率。經(jīng)計(jì)算，網(wǎng)絡(luò)正常情況下的網(wǎng)絡(luò)效率為36.4 %。在一一更換電池后，網(wǎng)絡(luò)效率的變化如圖3所示。

圖3 更換電池后的網(wǎng)絡(luò)效率

由圖3可知，面對(duì)大面積因能量問題導(dǎo)致失效節(jié)點(diǎn)的增多，整個(gè)網(wǎng)絡(luò)效率受到影響較大。當(dāng)節(jié)點(diǎn)數(shù)剩余36 %時(shí)，網(wǎng)絡(luò)效率已接近于0。為避免能量耗盡導(dǎo)致網(wǎng)絡(luò)癱瘓，應(yīng)對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行有意識(shí)的保護(hù)，包括關(guān)鍵節(jié)點(diǎn)的保護(hù)。

表2中列出脆弱性最高的4個(gè)點(diǎn)。數(shù)據(jù)顯示，這4個(gè)點(diǎn)分別位于水流變化比較大的區(qū)域，水質(zhì)一旦發(fā)生變化，采集節(jié)點(diǎn)將持續(xù)工作，對(duì)能量的消耗也就相對(duì)較大。一旦這些節(jié)點(diǎn)失效，整個(gè)網(wǎng)絡(luò)的效率降低超過25 %，表中列出的節(jié)點(diǎn)度都一致，均為2。因此，該網(wǎng)絡(luò)對(duì)節(jié)點(diǎn)度數(shù)的依賴可以忽略不計(jì)，鑒于將來對(duì)無線傳感器網(wǎng)絡(luò)的設(shè)計(jì)在通信鏈路可控的前提下，盡量對(duì)簇頭節(jié)點(diǎn)的度數(shù)保持一致，這樣在對(duì)網(wǎng)絡(luò)維護(hù)時(shí)重點(diǎn)對(duì)脆弱性高的節(jié)點(diǎn)進(jìn)行優(yōu)化保護(hù)而不用對(duì)全局節(jié)點(diǎn)進(jìn)行高強(qiáng)度保護(hù)，可節(jié)約成本。

表2 網(wǎng)絡(luò)節(jié)點(diǎn)失效后指標(biāo)值

3 結(jié) 論

1)本文針對(duì)文獻(xiàn)[4]網(wǎng)絡(luò)脆弱性的定量分析方法，基于復(fù)雜網(wǎng)絡(luò)理論，從節(jié)點(diǎn)度、平均路徑長度等方面對(duì)該網(wǎng)絡(luò)的拓?fù)涮匦赃M(jìn)行分析，提出基于網(wǎng)絡(luò)效率的節(jié)點(diǎn)脆弱性計(jì)算方法。案例研究結(jié)果表明：水流變化比較大的區(qū)域，水質(zhì)一旦發(fā)生變化，采集節(jié)點(diǎn)將持續(xù)工作，對(duì)能量的消耗也就

相對(duì)較大，表2中所列的節(jié)點(diǎn)為該網(wǎng)絡(luò)脆弱性最高的節(jié)點(diǎn)。

2)無線傳感器網(wǎng)絡(luò)脆弱性分析能夠解決無線傳感器網(wǎng)絡(luò)中普遍存在負(fù)載不均衡和能量優(yōu)化等問題提供理論依據(jù)[12]。在隨機(jī)播撒節(jié)點(diǎn)組成的自組織網(wǎng)絡(luò)中，尤其注重網(wǎng)絡(luò)脆弱性分析，找到那些負(fù)載不均衡的節(jié)點(diǎn)，優(yōu)化脆弱性高的節(jié)點(diǎn)，從而實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的拓?fù)鋬?yōu)化。

3) 運(yùn)用復(fù)雜網(wǎng)絡(luò)理論對(duì)無線傳感器網(wǎng)絡(luò)的脆弱性進(jìn)行分析，當(dāng)網(wǎng)絡(luò)正常運(yùn)行時(shí)，其網(wǎng)絡(luò)效率是最高的。面對(duì)突然失效節(jié)點(diǎn)時(shí)，不同節(jié)點(diǎn)失效的概率不同。如何快速的找到這些失效節(jié)點(diǎn)，進(jìn)行網(wǎng)絡(luò)重新優(yōu)化，是保證網(wǎng)絡(luò)通暢的前提。

參考文獻(xiàn):

[1] 陳力軍,劉 明,陳道蓄,等.基于隨機(jī)行走的無線傳感器網(wǎng)絡(luò)簇間拓?fù)溲莼痆J].計(jì)算機(jī)學(xué)報(bào)，2009，32(1):71-75.

[2] 張成才,齊小剛.基于復(fù)雜網(wǎng)絡(luò)理論的無線傳感器網(wǎng)絡(luò)特征度量分析[J].計(jì)算機(jī)科學(xué),2010，37(11):44-46.

[3] Guidoni D L,Mini R A F,Loureiro A A F.Creating small-world models in wireless sensor networks[C]∥IEEE 19th International Symposium on Personal,Indoor and Mobile Radio Communications,2008:1-6.

[4] 吳 蔣,任崇勛.基于Zig Bee技術(shù)的飲用水水源地水質(zhì)遠(yuǎn)程監(jiān)控系統(tǒng)[J].東北農(nóng)業(yè)大學(xué)學(xué)報(bào),2010,41(10):120-123.

[5] Watts D J,Strogatz S H.Collective dynamic of“small-world”networks[J].Nature,1998,393(6684):440-442.

[6] Albert R,Barabsi A L.Statistical mechanics of complex network[J].Review of Modern Physics,2002,74:47-97.

[7] Newman M E J.The structure and function of complex network-s[J].SIAM Review,2003,45:167-256.

[8] Ablert R,Barabasi A L.Statistical mechanics of complex network-s[J].Reviews of Modern Physics,2002,74(1):47-97.

[9] Dorogovtsev S N,Mendes J F F.Evolution of networks [EB/OL].[2007—10—27]. http://arxiv.org/abs/cond-mat/0106144v2.

[10] Strogatz S H. Exploring complex network [J].Nature,2001,410(3):268-276.

[11] Latora Vito,Marchiori Massimo.How the science of complex networks can help developing strategies against terrorism[J].Chaos Soltons and Fractals,2004,20(1):69-75.

[12] 雷 磊,薛小龍,周進(jìn)華,等.實(shí)現(xiàn)節(jié)點(diǎn)負(fù)載均衡的無線傳感網(wǎng)能量高效分簇方法[J].應(yīng)用科學(xué)學(xué)報(bào),2010,28(6):552-554.