無線傳感器網(wǎng)絡的關(guān)節(jié)點分析模型

摘 要：對隨機分布的無線傳感器網(wǎng)絡中的節(jié)點流量因子、匯聚因子和橋接因子進行了理論建模，在此基礎上提出了關(guān)鍵節(jié)點的理論判據(jù)和發(fā)現(xiàn)算法.通過實驗模擬，發(fā)現(xiàn)通過該方法識別出來的關(guān)節(jié)點是對網(wǎng)絡生存期影響最大的節(jié)點.通過該方法，可以快速找出傳感網(wǎng)中的熱點區(qū)域和關(guān)節(jié)點，為提高無線傳感網(wǎng)生存期提供了重要的理論依據(jù).

關(guān)鍵詞：無線傳感器網(wǎng)絡；能耗均衡；關(guān)節(jié)點；網(wǎng)絡生存期

中圖分類號：TP393 文獻標識碼：A

Modeling the Articulation Nodes of Wireless Sensor Networks

TAO Yong1，2， GONG Zhenghu1， WANG Yimin2

（1.School of Computer，National Univ of Defense Technology，Changsha， Hunan 410073，China;

2. Software College， Hunan Univ， Changsha， Hunan 410082， China)

Abstract:

This paper presented a WSN node’s theoretical mode， which includes traffic factor， aggregation factor and bridging factor， and then constructed an articulationnode’s determination and discovery algorithm. Experiment results have shown that the invalidation of nodes identified by the model will have a serious impact on the connectivity of the network. By using this method， we can quickly identify the hot spots in WSN.

Key words: wireless sensor networks; energy balance; articulation node; wireless sensor network lifetime

能耗是無線傳感器網(wǎng)絡面對的主要挑戰(zhàn)^［1］.為充分發(fā)揮能量的效率，從單個節(jié)點的能耗出發(fā)，已提出了能量有效路由算法^［2-3］、低能耗數(shù)據(jù)處理、低能耗短距離通信、數(shù)據(jù)融合^［4］、分簇^［5］等節(jié)能措施，然而由于缺乏對全網(wǎng)能耗的整體性認識，特別是能耗不均衡的影響，難以有效識別出傳感節(jié)點間的差異，容易引起網(wǎng)絡分割和內(nèi)環(huán)能量空洞^［6］.

傳感器網(wǎng)絡逐跳傳輸至sink節(jié)點的multihop傳輸模式下，部分節(jié)點成為需要完成傳感、轉(zhuǎn)發(fā)功能的復合節(jié)點，且節(jié)點間的流量負載具有很大的差異性^［7］，這種能量消耗不均衡現(xiàn)象將導致網(wǎng)絡中特定關(guān)鍵節(jié)點的能量損耗率較大，而某些傳感區(qū)域極易由于這些節(jié)點的失效而成為“傳感孤島”^［8］.實驗結(jié)果表明當節(jié)點按照通常情況分布在網(wǎng)絡中，網(wǎng)絡生命結(jié)束時，網(wǎng)絡中的90%能量沒有被利用^［9］.當前研究主要通過網(wǎng)絡部署或引入移動節(jié)點來解決內(nèi)環(huán)能量空洞問題^［10-11］，然而應用于危險場景（如敵情偵察、火山監(jiān)測、災難救援等）的無線傳感器網(wǎng)絡因無法進行統(tǒng)一的規(guī)劃部署，傳感器網(wǎng)絡多采用直升機拋灑的“0配置”方式，大量成本低廉的傳感節(jié)點的分布特性難以預知.文[12]提出了“準瓶頸節(jié)點”概念（當且僅當這個節(jié)點的鄰居集可以劃分成兩個或者多個不相交的非空集合，并且任一集合中的任一節(jié)點不屬于其他集合中的任一節(jié)點的鄰居集時），然而其算法執(zhí)行結(jié)果的識別準確性較低.本文的主要工作是給出關(guān)鍵節(jié)點的特征屬性，同時提出關(guān)節(jié)點的分析模型，實驗結(jié)果表明該模型所標識出的關(guān)節(jié)點的失效將對網(wǎng)絡的連通性造成嚴重影響.

1 系統(tǒng)建模與問題描述

不失一般性，我們采用單靜止sink節(jié)點的均質(zhì)無線傳感器網(wǎng)絡模型，其工作壽命以網(wǎng)絡覆蓋率的可用性指標來衡量，即網(wǎng)絡開始工作至網(wǎng)絡分割的時間作為網(wǎng)絡的有效工作壽命，而關(guān)節(jié)點則是指由于其失效導致網(wǎng)絡分割的節(jié)點集合.所有節(jié)點的地位在部署之前都是平等的，但一旦被部署完成，各節(jié)點間的平等地位就會被打破，基于節(jié)點對網(wǎng)絡壽命的影響級別，我們需要對節(jié)點和區(qū)域進行動態(tài)分類，確定約束網(wǎng)絡有效工作壽命的因素及其優(yōu)先級，從而可以識別出關(guān)節(jié)點，并對節(jié)點采取不同的能量控制策略.

1.1 流量因子

如圖1所示，節(jié)點u與sink的有效距離為D(u)，為將數(shù)據(jù)發(fā)送至sink節(jié)點S，u發(fā)送數(shù)據(jù)給鄰居P′的有效單跳距離為z，如果每一個節(jié)點都選擇有效單跳距離最大的鄰居節(jié)點作為下一跳，則該路徑稱為最大有效單跳路徑Z（maximum onehop progress），而最大有效單跳路徑可近似為最短路徑.在隨機部署的WSNs中平均最大單跳距離與節(jié)點平均度（鄰居個數(shù)）g，距離D（u）和覆蓋半徑R有關(guān)，可近似表示為≈(1－e－12g－0.07－0.09e(5－g)13)R^［9］.

圖1 無線傳感器網(wǎng)絡數(shù)據(jù)傳輸圖

所有節(jié)點到達sink的平均距離在隨機網(wǎng)絡中等同于傳感區(qū)域所有點到達sink的平均距離，若sink節(jié)點位置坐標為S(W/2，W/2

)，則=W6ln (1+22W)－ln (W2)+2，計算可得平均跳數(shù)h-=.

定義1節(jié)點流量因子

Lu=D(u)，反映節(jié)點u在網(wǎng)絡拓撲中的位置屬性，用于度量節(jié)點u距離sink遠近的不同導致承載數(shù)據(jù)中繼任務的多少.

1.2 節(jié)點匯聚因子

節(jié)點u的鄰居N(u)={v|(u，v)∈A}{v|D(u，v)

N0={S}，

Ni=v|D(u，v)≤Z，v∈V/∪i－1j=0Nj，u∈Ni－1.

定義2一跳虛節(jié)點

1）N0=N0； 2）Ni=∪ij=0Nj.

于是傳感網(wǎng)絡流量可抽象表示為虛源Ni+1到虛匯節(jié)點Ni的數(shù)據(jù)流：Ni+1匯聚Ni.

定義3關(guān)鍵路徑

v∈Ni，l(v)=(v，u)|u∈N(v)，u∈Ni－1.

我們以Cvu表示節(jié)點v在鏈路（v，u）上的流量， Cmax(v，u）表示鏈路集合l(v)中最大流量，其中記u=lmin (v)，則Li=(v，lmin (v))|v∈Ni為Ni→Ni－1的最短路徑集.

定義4 節(jié)點匯聚因子

Bu=∑l∈LiδulLi，其中δul={1v是l的點

0否則，表示節(jié)點u的匯聚程度，用于度量節(jié)點u在環(huán)域間數(shù)據(jù)中繼的重要性.

1.3 橋接因子

由于網(wǎng)絡部署的隨機性，那些連接不同緊密區(qū)域的松散節(jié)點，它的能量消耗速率會很高，同時由于它們的失效，整個網(wǎng)絡可能被割裂成兩個或多個不相連的區(qū)域.根據(jù)文獻[12]準瓶頸節(jié)點的定義，相互支援的節(jié)點都被判定為準瓶頸節(jié)點，該類節(jié)點具有如下特征：

1）成對出現(xiàn)，且互為鄰居；

2）出現(xiàn)在一個邊長為4的圈上.

我們將上述這類節(jié)點稱為“偽瓶頸節(jié)點”，表現(xiàn)為如圖2所示的3種情況.此外，該定義還將處于網(wǎng)絡邊緣的葉子節(jié)點等非關(guān)鍵節(jié)點判斷為準瓶頸節(jié)點，因而算法執(zhí)行結(jié)果的識別準確性較低.

圖2 偽瓶頸節(jié)點圖示

Fig. 2 Pseudobottlenecknode

1.3.1二跳瓶頸節(jié)點發(fā)現(xiàn)算法

一個節(jié)點為二跳準瓶頸節(jié)點，當且僅當其鄰居被分割成不交的節(jié)點集，且這些不相交的節(jié)點集的鄰居集合也不相交.現(xiàn)證明二跳準瓶頸節(jié)點的定義可以滿足準瓶頸節(jié)點的定義并且不包含偽瓶頸節(jié)點.要證明這個結(jié)論，只需證明二跳準瓶頸節(jié)點不具備偽瓶頸節(jié)點的第二特征，即只要證明在邊長為4的圈上，任何節(jié)點都不可能成為二跳準瓶頸節(jié)點.

證明 所有邊長為4的圈的情況如圖2所示，被圈節(jié)點是被誤判的節(jié)點，可以容易地看出后兩種情況甚至不是準瓶頸節(jié)點，于是只要判斷第一種情況.由于被圈節(jié)點的兩個鄰居不直接相連，即處于不同的節(jié)點集，設這兩個不相交的節(jié)點集分別為S1，S2，于是被圈節(jié)點符合準瓶頸節(jié)點的定義，可以被準瓶頸節(jié)點算法發(fā)現(xiàn).再繼續(xù)考察，可以很容易地得到N(S1)∩N(S2)≠Φ (N (S)表示節(jié)點集合S的鄰居集合)，也就是被圈節(jié)點不符合二跳準瓶頸節(jié)點的定義，所以得出結(jié)論：在邊長為4的圈上，任何的節(jié)點都不可能成為二跳準瓶頸節(jié)點，也就是說，偽瓶頸節(jié)點不滿足二跳準節(jié)點的定義，由此命題得證.根據(jù)二跳準瓶頸節(jié)點的定義我們可以提出二跳準瓶頸節(jié)點的算法，算法的過程如下.

1) 鄰居發(fā)現(xiàn)階段：當網(wǎng)絡部署完畢后，每個節(jié)點通過發(fā)送“HELLO”探測包來通知獲得鄰居信息.

2) 連接信息交換階段：當節(jié)點獲得鄰居信息后，它和自己的每個鄰居交換連接信息.

3) 鄰居交換鄰居表階段：每個節(jié)點把自己的鄰居列表發(fā)給所有的鄰居，同時也收到來自其他鄰居的鄰居表.

4) 自判斷階段：獲得鄰居節(jié)點的鄰居表后，每個節(jié)點現(xiàn)在知道自己二跳距離內(nèi)的拓撲情況，于是執(zhí)行下面的算法以判斷自己是否為“二跳準瓶頸節(jié)點”：

Step1 將該節(jié)點的每個鄰居放到單獨塊中記為partition(i)，簡記為 Pi；

Step2對任意兩個塊Pi和Pj，若node1∈Pi，node2∈Pj，且node1和node2是鄰居， 記為node1＆node2 ， 則合并Pi和Pj，將合并操作記為Pi=Union（Pi，Pj）， Pi為新的分塊，重復本步驟，直到所有的分塊都不能再合并為止；

Step3 若所有的塊都被合并成一塊，則目標節(jié)點不是準節(jié)點，算法結(jié)束，否則目標節(jié)點是一跳準節(jié)點，繼續(xù)執(zhí)行Step4，判斷是否為二跳準節(jié)點；

Step4 經(jīng)Step2 后所得的分塊記為Pi，N（Pi）為Pi塊中所有節(jié)點的鄰居節(jié)點（除目標節(jié)點node 以外），進行操作Pi=N（Pi）；

Step5 對任意兩個塊Pi和Pj ，若node.(node.∈Pi.∧node.∈Pj.)，則執(zhí)行Pi=Union（Pi，Pj），重復該步驟，直到不能再合并為止.若所有的塊都被合并為一塊，則目標節(jié)點不是二跳準節(jié)點，否則是二跳準節(jié)點，算法結(jié)束.

1.3.2 算法分析

由于二跳準節(jié)點是在一跳準節(jié)點的基礎上進行判斷，因此該算法時間復雜度為：

T2(n)=T1(n)+O(f2(n)).

式中:T1(n)=O(n3) 為一跳準瓶頸節(jié)點的時間復雜度; f2(n)為二跳準瓶頸節(jié)點算法的運算次數(shù).

定理1 經(jīng)過一跳算法處理后，至多會產(chǎn)生3個分塊.

證明 如圖3所示，圓心為目標節(jié)點，則傳感區(qū)域可以分為6個等份，并用數(shù)字標記.

圖3 區(qū)域分割圖示

Fig. 3 Regional block diagram

目標節(jié)點的鄰居節(jié)點全部散布在這6個區(qū)域，可以很容易地看出，在相鄰的兩個區(qū)域的節(jié)點互為鄰居，也就是經(jīng)一跳算法處理后必是處在同一分塊的節(jié)點，如處在區(qū)域1，2 的節(jié)點必處于同一分塊，如果區(qū)域1，3 內(nèi)有節(jié)點，而其他區(qū)域內(nèi)都無節(jié)點，經(jīng)算法處理后則至多產(chǎn)生兩個分塊.這樣，我們可以得出結(jié)論，只要當1，3，5（2，4，6 同理）內(nèi)有節(jié)點，而其他區(qū)域內(nèi)無節(jié)點時，經(jīng)一跳算法處理后可以產(chǎn)生最多的3個分塊，而其他的任何方案都不可能產(chǎn)生更多的分塊.N 個鄰居節(jié)點散布于6個區(qū)域被分成兩塊的概率為q=(13)n.N 個鄰居節(jié)點散布于6個區(qū)域被分成3塊的概率為p=(12)n， 則f2(n)=n2+qn42+pn69，于是T2(N)=O(n3)+O(n2+qn42+pn69)=O(n3).

可以看出，由于隨著鄰居節(jié)點數(shù)n 的增長，被分成3塊和2塊的概率p 和q 的概率呈指數(shù)級地下降，于是二跳準節(jié)點算法的時間復雜度并未比文[12]提高.

由此我們得到如下瓶頸節(jié)點.

定義5瓶頸節(jié)點

一個節(jié)點是瓶頸節(jié)點，當且僅當其鄰居可以被分割成不相交的兩個或多個節(jié)點集，且這些不相交的節(jié)點集的鄰居集合也不相交.易知，該定義消除了偽瓶頸節(jié)點.

定義6環(huán)域內(nèi)橋接因子

Qu＝{1，如果u∈K0，如果uK，它表示一個環(huán)域內(nèi)與u節(jié)點相連的鄰居節(jié)點之間互相連接的程度，也即反映了該節(jié)點的鄰居節(jié)點間的抱團特性.

2 關(guān)鍵節(jié)點

2.1 關(guān)鍵節(jié)點屬性

我們可根據(jù)上節(jié)所定義影響網(wǎng)絡生存期的流量因子、匯聚因子和橋接因子，得到節(jié)點的關(guān)節(jié)點屬性：Ku=α#8226;Qu+β#8226;Lu+γ#8226;Bu ，其中α，β，γ分別是橋接因子、流量因子和匯聚因子對于關(guān)節(jié)點判斷時的權(quán)重，表示各因子的重要程度，其取值決定于網(wǎng)絡的具體應用場景.例如在位置可知型網(wǎng)絡中流量因子的精確性較高，相應地其權(quán)重也取較大值；而在稀疏網(wǎng)路中橋接因子的權(quán)重卻比較大，α，β，γ的值在滿足α+β+γ=1條件下，可由協(xié)議開發(fā)者自主確定.

由此，我們可以得到關(guān)節(jié)點集K={u|u∈N，Ku>δ#8226;(max i∈VBi)}，其中常量δ是一個安全邊際，同WSN分布情況相關(guān).

2.2 模擬結(jié)論

本節(jié)通過仿真實驗驗證關(guān)節(jié)點屬性的正確性和關(guān)鍵節(jié)點對網(wǎng)絡的顯著影響，我們首先將看到關(guān)鍵節(jié)點具有較高水平的能量消耗速度和較低的能量剩余，另外我們還發(fā)現(xiàn)網(wǎng)絡分割后，失效節(jié)點中關(guān)鍵節(jié)點所占比率平均超過95.7％.

實驗所用的仿真工具是ns2，實驗所使用的傳感器網(wǎng)絡包含500個節(jié)點，隨機拋灑在面積為700 m×700 m的正方形區(qū)域內(nèi)，sink節(jié)點位于區(qū)域中心.基于Crossbow系列傳感節(jié)點相關(guān)參數(shù)，我們假定所有傳感節(jié)點的通信半徑均為70 m，節(jié)點的初始能量為5×105 J，節(jié)點用于感知、收集與傳送單位數(shù)據(jù)的能耗分別為2 J，2 J和10 J.關(guān)節(jié)點判斷算法中的α，β，γ分別取值0.2，0.5，0.3.

實驗比較了4種類型節(jié)點：一般節(jié)點(ONs: Ordinary Nodes)、準瓶頸節(jié)點（QBNs: QuasiBottleneck Nodes）、內(nèi)環(huán)節(jié)點（OHNs: OneHop Nodes）和關(guān)節(jié)點（KNs: Key Nodes）.

圖4給出了4類節(jié)點的平均能耗速度的對比，從圖中我們可以看出關(guān)節(jié)點由于在網(wǎng)絡中的特殊性需要中繼大量的數(shù)據(jù)，能量的消耗速度很快，是一般節(jié)點平均能耗的3倍左右.圖5給出了在不同的節(jié)點密度下，引起網(wǎng)絡分割的失效節(jié)點中關(guān)節(jié)點所占的比率，從中我們發(fā)現(xiàn)關(guān)節(jié)點是對網(wǎng)絡生存期影響最大的節(jié)點.

采樣時間/s

圖4 節(jié)點剩余能量比較

Fig.4 Comparison of residual energy

圖5 網(wǎng)絡分割時刻失效節(jié)點比率比較

Fig. 5 Radio of failed nodes

綜上可知，模擬結(jié)果表明該模型識別出的關(guān)鍵節(jié)點的能耗速度是一般節(jié)點的3倍以上，網(wǎng)絡的連通性受嚴重影響時關(guān)鍵節(jié)點失效比率超過一般節(jié)點失效比率近一倍.通過該方法，可以快速找出傳感網(wǎng)中的熱點區(qū)域和節(jié)點，為提高無線傳感網(wǎng)生存期提供了重要的理論依據(jù).

3 結(jié) 論

在現(xiàn)有的節(jié)能措施和路由算法中，大部分的策略是選擇代價最小路徑，但這類方案會導致網(wǎng)絡中出現(xiàn)一些熱點節(jié)點或區(qū)域，這些傳感節(jié)點很快消耗完其有限的能量，因此消除能耗不均衡現(xiàn)象，實現(xiàn)負載均衡、實施擁塞控制、開發(fā)能耗感知路由等，首先都需要識別出這類節(jié)點，該類節(jié)點的建模是WSN一個重要的基礎問題.因此本文針對應用于危險環(huán)境的無線傳感器網(wǎng)絡，根據(jù)節(jié)點在網(wǎng)絡中與sink節(jié)點的關(guān)系、節(jié)點鄰居節(jié)點的分布特性以及節(jié)點本身的位置等因素，分別形式化定義了節(jié)點成為關(guān)節(jié)點的流量因子、匯聚因子和橋接因子，給出了關(guān)鍵節(jié)點的數(shù)學模型.實驗表明該模型具有較好的準確性.下一步的主要工作是設計基于關(guān)節(jié)點的能耗均衡路由選擇算法，從全局優(yōu)化的角度出發(fā)，通過關(guān)節(jié)點數(shù)據(jù)流量的轉(zhuǎn)移實現(xiàn)均衡網(wǎng)絡中不同區(qū)域能量消耗速度的目標.

參考文獻

［1］ AKYILDIZ F， SU W， SANKARASUBRAMANIAN Y.Wireless sensor networks: a survey[J]. Computer Networks， 2002， 38(4): 393-422.

［2］ SHAH R， RABAEY J. Energy aware routing for low energy ad hoc sensor networks[C]//Proceedings of Wireless Communications and Networking Conference，Orlando，USA. New York: IEEE Communications Society， 2002:350-355.

［3］ 唐勇，周明天，張欣.無線傳感器網(wǎng)絡路由協(xié)議研究進展[J].軟件學報， 2006，17(3):410-421.

TANG Yong，ZHOU Mingtian，ZHANG Xin. Overview of routing protocols in wireless sensor networks [J].Journal of Software， 2006，17(3):410-421. (In Chinese)

［4］ BANDYOPADHYAY S， COYLE E J. An energyefficient hierarchical clustering algorithm for wireless sensor networks[C]// MITCHELL K， ed. Proceedings ofthe INFOCOM 2003. New York: IEEE Press， 2003:1713-1723.

［5］ MHATRE V， ROSENBERG C. Design guidelines for wireless sensor networks: communication， clustering and aggregation[J]. Ad Hoc Networks， 2004， 2: 45-63.

［6］ LI J， MOHAPATRA P. An analytical model for the energy hole problem in manytoone sensor networks[C]//Proceedings of IEEE Vehicular Technology Conference， Dallas， TX， 2005. New York: IEEE Communications Society，2005:2721-2725.

［7］ DUARTEMELO E J， LIU M Y. Analysis of energy consumption and lifetime of heterogeneous wireless sensor networks[C]//Proceedings of Global Telecommunications Conference， 2002. New York: IEEE Communications Society， 2002:21-25.

［８］ PERILLO M， CHENG Z， HEINZELMAN W. On the problem of unbalanced load distribution in wireless sensor networks[C]// Proceedings of Global Telecommunications Conference Workshops， 2004. New York: IEEE Communications Society， 2004:74-79.

［９］ LIAN J， NAIK K， AGNEW G B. Data capacity improvement of wireless sensor networks using nonuniform sensor distribution[J]. International Journal of Distributed Sensor Networks， 2006，2(2):121-145.

［１０］WU X B， CHEN G H， DAS S K. On the energy hole problem of nonuniform node distribution in wireless sensor networks[C]//2006 IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS2006)， Vancouver， Canada， October 9-12， 2006. New York: IEEE Communications Society， 2006:180-187.

［11］OLARIU S， STOJMENOVIC I. Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting[C]// Proceedings of 25th IEEE International Conference on Computer Communications， Barcelona， Spain， April 2006. New York: IEEE Communications Society， 2006:1-12.

［12］田樂，謝東亮，韓冰. 無線傳感器網(wǎng)絡中瓶頸節(jié)點的研究[J]. 軟件學報，2006， 17(4):830-837.

TIAN Le， XIE Dongliang， HAN Bing. Study on bottleneck nodes in wireless sensor networks[J].Journal of Software， 2006， 17(4):830-837.(In Chinese)