基于復雜網絡的無線傳感器網絡能量脆弱性分析*

吳 蔣， 王 冬

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

0 引 言

由于無線傳感器網絡(WSNs)中的傳感器節點能量嚴重受限而且部署后難以回收，因而,針對無線傳感器網絡的能量效率的研究一直是該領域的熱點和難點。無線傳感器網絡鏈路中，諸如：突發大流量、自然災害、人為破壞、節點能量失效等突發事件可能會導致某條鏈路斷開，從而影響網絡通信的全局效率。不同節點能量失效引起全局網絡效率變化的大小稱為節點的脆弱性。分析無線傳感網的網絡拓撲性并定量計算各個節點的脆弱性以采取相應對策預防網絡癱瘓，對保障整個無線傳感器網絡的通信暢通有重要意義。

國內外學者利用復雜網絡理論，已對無線傳感器網絡做過大量研究。陳力軍等人[1]借助于復雜網絡理論，提出了一種基于隨機行走的無線傳感器網絡簇間拓撲演化模型。該模型對完善無線傳感器網絡的容錯機制起到了積極的作用，可防止節點出現因能量的耗盡而失效或鏈路因網絡的入侵而失靈的現象。張成才等人[2]對無線傳感器網絡的聯通性展開研究，結果表明增加通信半徑則可以迅速地使網絡聯通。Guidoni D L等人[3]曾用小世界網絡特性應用于無線傳感網絡的研究。以上學者側重于研究無線傳感器網絡的整體效率變化情況，缺乏對每個節點脆弱性的定量分析。筆者在描述復雜網絡理論的基礎上，確定定量化評價節點脆弱性的指標，并以文獻[4]網絡為例，使用Space D法構造其拓撲網絡，并用Matlab分析節點度、平均路徑長度、聚類系數等指標和分布規律，最后定量計算各個節點能量消耗的脆弱性，以確定其中的關鍵節點，為維護和優化提供科學依據。

1 無線傳感器網絡節點能量脆弱性分析

1.1 復雜網絡的統計參數

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

1.1.1 節點度與度分布

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

1.1.2 聚類系數

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

(1)

(2)

1.1.3 平均路徑長度

網絡G中2個節點i和j之間的距離dij定義為連接這2個節點的最短路徑的邊數。對于一個無向網絡，定義平均路徑長度L為網絡中節點對之間距離dij的平均值

(3)

式中N為網絡節點數。網絡的平均路徑長度用來衡量網絡節點間的離散程度，也被稱為網絡的特征路徑長度。研究表明，盡管許多實際網絡的節點數巨大，但網絡的平均路徑長度L相對于N來說卻很小，這種現象稱之為“小世界效應[5]”。

1.2 無線傳感器網絡構建

根據文獻[1]，假設所有簇頭的最大通信半徑可控，各個水源地入口相鄰的簇頭都在最大通信半徑內，Space D拓撲結構模型即把簇頭視為節點，若某一線路上的2個簇頭是相鄰的，它們之間就有通信鏈路，如圖1所示。

圖1 Space D網絡構建方法

在無線傳感器網絡中，簇頭和通信鏈路是基本的組成元素，鏈路連接著簇頭節點相互感知和轉發數據，因此，無線傳感器網絡可看成由鏈路和簇頭所構成的復雜網絡。這里可以定義為:無線傳感器網絡中的節點代表通信鏈路中的簇頭，邊代表各簇頭之間的鏈路,這樣，由很多的邊和點組成的網絡就構成了無線傳感器網絡的基本框架。

1.3 無線傳感器網絡脆弱性分析

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

(4)

當E值很大時，表明網絡效率很高且連通性很好。當節點i能量耗盡失效后，網絡遭到破壞，網絡效率也受到影響，不同節點失效時引起網絡效率的變化大小不同，即脆弱性不同，則第i個節點的脆弱性ΔE定義為

(5)

2 文獻[4]網絡實證研究

2.1 文獻[4]網絡結構

本文用Space D方法對三亞半嶺水庫水質監控網絡進行拓撲建模，拓撲后網絡如圖2所示。

圖2 三亞半嶺水庫水質監控網絡拓撲結構圖

2.2 文獻[4]網絡的統計特性與分析

本文對三亞半嶺水庫的各個監測點采用的是環形的節點布置方式，相鄰節點的數據鏈路唯一，某節點一旦失效，其數據接收為0或該節點效率逐漸降低趨向于0。對文獻[4]網絡分別計算其網絡節點數、邊數、平均度、平均路徑長度和聚類系數，結果見表1。

表1 特征指標值

環形節點布置方式方便于計算，從表1可知，一共布置了36個監測節點，36條連接邊，每個節點與2個相鄰節點直接連接，平均鏈路長度為9.25，并擁有較小的聚類系數，同時有較小的鏈路長度。根據拓撲圖，計算得到其平均聚類系數為0。

2.3 節點能量耗盡時網絡的脆弱性

對文獻[4]網絡的36個節點進行電池更換，該電池能量為即將耗盡的電池，并用式(4)計算更換電池后的網絡效率。經計算，網絡正常情況下的網絡效率為36.4 %。在一一更換電池后，網絡效率的變化如圖3所示。

圖3 更換電池后的網絡效率

由圖3可知，面對大面積因能量問題導致失效節點的增多，整個網絡效率受到影響較大。當節點數剩余36 %時，網絡效率已接近于0。為避免能量耗盡導致網絡癱瘓，應對網絡中的節點進行有意識的保護，包括關鍵節點的保護。

表2中列出脆弱性最高的4個點。數據顯示，這4個點分別位于水流變化比較大的區域，水質一旦發生變化，采集節點將持續工作，對能量的消耗也就相對較大。一旦這些節點失效，整個網絡的效率降低超過25 %，表中列出的節點度都一致，均為2。因此，該網絡對節點度數的依賴可以忽略不計，鑒于將來對無線傳感器網絡的設計在通信鏈路可控的前提下，盡量對簇頭節點的度數保持一致，這樣在對網絡維護時重點對脆弱性高的節點進行優化保護而不用對全局節點進行高強度保護，可節約成本。

表2 網絡節點失效后指標值

3 結 論

1)本文針對文獻[4]網絡脆弱性的定量分析方法，基于復雜網絡理論，從節點度、平均路徑長度等方面對該網絡的拓撲特性進行分析，提出基于網絡效率的節點脆弱性計算方法。案例研究結果表明：水流變化比較大的區域，水質一旦發生變化，采集節點將持續工作，對能量的消耗也就

相對較大，表2中所列的節點為該網絡脆弱性最高的節點。

2)無線傳感器網絡脆弱性分析能夠解決無線傳感器網絡中普遍存在負載不均衡和能量優化等問題提供理論依據[12]。在隨機播撒節點組成的自組織網絡中，尤其注重網絡脆弱性分析，找到那些負載不均衡的節點，優化脆弱性高的節點，從而實現整個網絡的拓撲優化。

3) 運用復雜網絡理論對無線傳感器網絡的脆弱性進行分析，當網絡正常運行時，其網絡效率是最高的。面對突然失效節點時，不同節點失效的概率不同。如何快速的找到這些失效節點，進行網絡重新優化，是保證網絡通暢的前提。

參考文獻:

[1] 陳力軍,劉 明,陳道蓄,等.基于隨機行走的無線傳感器網絡簇間拓撲演化[J].計算機學報，2009，32(1):71-75.

[2] 張成才,齊小剛.基于復雜網絡理論的無線傳感器網絡特征度量分析[J].計算機科學,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技術的飲用水水源地水質遠程監控系統[J].東北農業大學學報,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].應用科學學報,2010,28(6):552-554.