事件驅(qū)動無線傳感器網(wǎng)絡(luò)中有效節(jié)點的選擇方法

朱旻如 郭 劍

(南京郵電大學(xué)計算機學(xué)院 江蘇 南京 210003)

事件驅(qū)動無線傳感器網(wǎng)絡(luò)中有效節(jié)點的選擇方法

朱旻如 郭 劍

(南京郵電大學(xué)計算機學(xué)院 江蘇 南京 210003)

事件驅(qū)動的無線傳感器網(wǎng)絡(luò)需要對事件狀態(tài)做出合理的判斷以進行處理，本文研究如何選取少量節(jié)點參與通信，以較低的能耗代價獲取事件狀態(tài)。文中提出的NSS(Node Supported Selection)算法，首先利用節(jié)點之間的空間相關(guān)性將事件感知空間劃分為若干相關(guān)單元，再依據(jù)節(jié)點支持度選取代表節(jié)點參與數(shù)據(jù)傳輸。仿真結(jié)果表明，該算法只需小比例的節(jié)點數(shù)就能保證感知精度，且具有較好的可擴展性，能滿足多樣的應(yīng)用需求。

事件驅(qū)動無線傳感器網(wǎng)絡(luò)；環(huán)狀空間相關(guān)性；最優(yōu)節(jié)點集選擇；節(jié)點支持度；失真度

1.引言

WSN(Wireless Sensor Networks)因其能滿足戰(zhàn)場監(jiān)控、災(zāi)難管理、環(huán)境監(jiān)測、智能家居、健康管理等特殊環(huán)境而日益受到重視，但是WSN節(jié)點多是微小的，能量、存儲和處理能力有限，該現(xiàn)狀造成對WSN的研究存在很多約束，諸如能耗限制、計算能力和存儲能力限制等，而能耗的控制更是首當其沖的設(shè)計要素[1-2]。WSN依賴網(wǎng)內(nèi)各個節(jié)點的協(xié)作共同完成任務(wù)，各個節(jié)點不僅需要感知周邊信息并及時向sink傳輸，往往還需要作為中繼節(jié)點幫助形成有效的傳輸路徑。節(jié)點之間的協(xié)同合作有利于提高感知精度、增強覆蓋范圍，及對事態(tài)做出正確評估等[3]。

然而，為增強整個網(wǎng)絡(luò)的連通性和魯棒性，節(jié)點通常是密集部署，大量的被感知數(shù)據(jù)在網(wǎng)內(nèi)傳遞也造成能耗的急劇增加，甚至信道的競爭和擁塞，這都不利于網(wǎng)絡(luò)的持續(xù)和穩(wěn)定。近年研究者利用密集分布的節(jié)點之間感知的信息具有空間相關(guān)性特點展開了研究。文獻[4-5]采用數(shù)據(jù)融合技術(shù)，感知的數(shù)據(jù)延路由向sink傳遞經(jīng)過融合節(jié)點時進行融合計算，減少冗余數(shù)據(jù)，從而減輕無線鏈路和基站的通信開銷；文獻[6-9]從密集分布的節(jié)點中選取部分節(jié)點參與數(shù)據(jù)的傳輸，在保證數(shù)據(jù)精度的同時也能大大降低網(wǎng)內(nèi)傳輸?shù)臄?shù)據(jù)總量。文獻[10-11]利用DSC（Distributed Source Coding）消除數(shù)據(jù)之間的冗余。文獻[10]在信道編碼的思想上考慮空間相關(guān)性以分割信源的符號空間，使得通信時只需要傳遞信源所在陪集的索引就可以 完成信息傳遞，大大減低能耗。

在事件驅(qū)動的無線傳感器網(wǎng)絡(luò)如森林火災(zāi)檢測、目標跟蹤等應(yīng)用中，研究者更關(guān)注的在一定誤差容忍范圍內(nèi)對事件做出及時有效的處理而不是數(shù)據(jù)的無損傳遞[12][13]，因此，當有突發(fā)事件產(chǎn)生時，從感知到事件的節(jié)點中選取部分具有代表性節(jié)點參與數(shù)據(jù)傳輸，盡量以較低的能耗代價使得sink節(jié)點在接收到數(shù)據(jù)后能對事件做出有效正確的評估，該問題是值得研究的。文獻[8]中M.C.Vuran等在時間和空間相關(guān)性的模型基礎(chǔ)上，依據(jù)節(jié)點分布的統(tǒng)計屬性給出部分節(jié)點參與感知來保證事件感知的精度，所采用的隨機節(jié)點選取方法經(jīng)過驗證顯示盡管隨著節(jié)點的加入失真度逐步降低，但隨機選擇的節(jié)點不一定具有很好的代表性[8]。隨后又進一步提出INS(Interative Node selection)算法選擇節(jié)點集，用矢量量化算法將節(jié)點投影到Voronoi空間，再根據(jù)感知半徑選取一定的代表節(jié)點以保證失真度要求，但是過程中沒有考慮事件源的位置對代表節(jié)點選擇的影響[14]。文獻[15]改進了失真度判斷方法，用AOST(Adaptive Add One Sensor node at a Time)算法逐個選取節(jié)點加入傳輸節(jié)點集，算法簡單且性能上有較大提高，但是每一輪選取節(jié)點時都需要對感知范圍內(nèi)的所有節(jié)點進行遍歷，大大增加了運算工作量和計算時間。和本文相似的研究如蘇威等也提出了環(huán)狀相關(guān)性模型并驗證其可行性，但是并沒有就此給出代表節(jié)點選擇的方法[16]。

本文將在文獻[8]基礎(chǔ)上考慮到節(jié)點之間的相關(guān)性不僅和節(jié)點之間的距離有關(guān)，還和節(jié)點到事件源的距離有關(guān)，得到環(huán)狀相關(guān)性模型，在此基礎(chǔ)上提出NSS（Node Supported Selection）算法，將事件感知空間劃分為若干相關(guān)單元，從每個相關(guān)單元選取一個代表節(jié)點，這些代表節(jié)點協(xié)作參與數(shù)據(jù)傳輸，通過調(diào)整相關(guān)單元的大小選取不同的代表節(jié)點集以滿足不同失真度要求。

2.空間相關(guān)性模型

2.1 系統(tǒng)模型

本文采用M. C. Vuran等提出事件感知系統(tǒng)模型[8]。描述如下：

(2) N個傳感器節(jié)點隨機均勻地分布在半徑為的圓形事件域內(nèi)，節(jié)點靜止且位置已知。傳感器節(jié)點傳輸半徑為Rc，且Rc＜Re，使得事件域內(nèi)的多個節(jié)點要協(xié)作完成對事件的感知；

(3) 傳感器節(jié)點i的坐標為(xi,yi)，其對事件S感知到信息Si的測量值為Xi，Xi是有噪聲的，即：Xi=Si+Ni，噪聲Ni也是期望為0，均方差為的高斯隨機序列，且各個節(jié)點的噪聲相互獨立；

(4) 節(jié)點觀測到的信息Xi編碼為Yi傳輸給sink節(jié)點，sink節(jié)點對接收到的M個編碼信息 Yi解碼后得到Zi，由此獲得事件S的估計值這樣就可以用失真度衡量估算值的準確性。

由于節(jié)點之間相關(guān)性的存在，通過M個對事件源進行估算，基于MMSE(Minimum Mean Square Error)原則其失真度可由式(1)計算得到：

其中：

式(2)和(3)分別表示傳感器節(jié)點之間以及傳感器節(jié)點和事件源的相關(guān)系數(shù)。

2.2 環(huán)狀相關(guān)性模型

相關(guān)系數(shù)的計算主要有四種形式，根據(jù)監(jiān)測事件的物理屬性可以選取相關(guān)的模型。本文采用能量指數(shù)模型，如公式(4)所示，其中

其中相關(guān)系數(shù) 是和節(jié)點之間距離 、節(jié)點和事件源距離 相關(guān)的，介于[0，1]之間的單調(diào)遞減非負函數(shù)。

當突發(fā)事件產(chǎn)生時，一方面，事件域內(nèi)感知到事件的節(jié)點的觀測值和事件源的相關(guān)度將隨著與事件源的距離增加而降低；另一方面，和事件源距離相同的那些節(jié)點的觀測值，之間相關(guān)度較高。因此給出如圖1所示的環(huán)狀相關(guān)性模型。圖中，事件源位于(0,0)，事件域為半徑是500的圓形區(qū)域。將節(jié)點劃分到以事件源為圓心的各個同心圓環(huán)中，同一層圓環(huán)中節(jié)點感知的數(shù)據(jù)相關(guān)性較高?；诖?，本文提出NSS算法選取部分代表節(jié)點參與數(shù)據(jù)傳輸，而普通節(jié)點則不傳輸數(shù)據(jù)，以此降低能耗。

圖1 環(huán)狀相關(guān)性模型示意圖

3.NSS算法

為解決事件驅(qū)動的傳感器網(wǎng)絡(luò)中選取有效的代表節(jié)點集傳遞感知數(shù)據(jù)的問題，根據(jù)上述環(huán)狀相關(guān)性模型，可以將公式(4)代入式(1)整理后得到：

由式(5)可知，失真度大小與選取的節(jié)點個數(shù)及其位置相關(guān)。為降低失真度，代表節(jié)點集 中各節(jié)點應(yīng)滿足以下條件：

即在滿足最大失真度的要求下選取和事件高度相關(guān)，而彼此之間相關(guān)性盡可能低的節(jié)點集作為代表節(jié)點參與信息的傳輸，事件域中其他節(jié)點不參與信息傳遞，以降低能耗。

因此，本文提出NSS算法：首先將事件域根據(jù)環(huán)狀相關(guān)性分層，而后劃分相關(guān)單元，使得相關(guān)單元內(nèi)的節(jié)點相關(guān)度較高，最后根據(jù)節(jié)點支持度得到相關(guān)單元的代表節(jié)點。NSS算法得到的相關(guān)單元為如圖1所示的區(qū)域。

3.1 事件域分層

根據(jù)環(huán)狀相關(guān)性模型，首先應(yīng)對事件域進行分層，將事件域劃分為 個同心圓環(huán)，根據(jù)和事件源的距離由近及遠劃分成半徑序列為{R1,R2,…,Rk,…,RL}的同心圓環(huán)，各層次半徑之間的關(guān)系如式(8)所示：

其中，k=1,2…,L 表示將事件域劃分為L層。R0=0為事件源所在位置；wk為圓環(huán)的寬度，最內(nèi)層的w1可以取值為節(jié)點傳輸半徑，因為距離事件一跳范圍內(nèi)的節(jié)點相關(guān)性較高。wk滿足其中圓環(huán)相關(guān)半徑系數(shù)1α＜=，表示從事件源由內(nèi)而外圓環(huán)寬度逐步減少或者相等，這是因為根據(jù)能量衰減模型，隨著距離的增加信號強度下降越快，即隨著節(jié)點和事件距離的增加，節(jié)點之間相關(guān)性會逐步減少。

3.2 劃分相關(guān)單元

根據(jù)和事件源的距離確定節(jié)點所在層次后，本文將各個圓環(huán)區(qū)域進一步劃分成一個個面積相同的相關(guān)單元，相關(guān)單元內(nèi)的節(jié)點對事件源的感知信息相似。其如圖2中陰影顯示的是半徑分別為1kR-，的相鄰兩層同心圓環(huán)中的兩個相關(guān)單元。

若和事件源S最近的第一層初始圓心角為β1，以事件源S為圓心，各層中相關(guān)單元的圓心角βk（k=1,2,…,L ）可以用式(9)依次求得：

考慮到空間相關(guān)和節(jié)點間距離關(guān)系密切，可以認為相關(guān)單元內(nèi)的節(jié)點之間具有最大的相關(guān)度，只要選擇其中一個作為代表節(jié)點即可。顯然，1β越大，相關(guān)單元的面積越大。

圖2 相關(guān)單元示意圖

3.3 確定代表節(jié)點

考慮公式(6)和(7)的約束，選擇距離事件源較近而彼此之間較遠的節(jié)點能有效地降低失真度。為評價節(jié)點和本層其他節(jié)點的接近程度，本文引入節(jié)點支持度（Node Supported），定義如下：

其中j=1,2…,n為節(jié)點i所在層的其他節(jié)點個數(shù)。Ci越小，說明節(jié)點 和其他節(jié)點感知的數(shù)據(jù)越接近，其他節(jié)點和節(jié)點i的相關(guān)性越高，節(jié)點i具有代表性。

綜上，NSS算法流程如下：

1 輸入:S //事件源發(fā)生位置(xe,ye)，事件半徑 Re

α，β1，Rc//圓環(huán)相關(guān)半徑系數(shù)、相關(guān)域初始角度和節(jié)點感知半徑

Φ(N) //感知到事件的N個節(jié)點集，節(jié)點i的位置(xi,yi)

Dmax//最大失真度

2輸出:Φ(M) //代表節(jié)點集

3R0=0，計算Rk=Rk-1+wk，其中k=1,2…,L

4β1=π,根據(jù)計算各層圓心角度數(shù)

5 for each ∈()NΦ

計算,sid //計算節(jié)點和事件發(fā)生位置的距離

if,sid＞=kR and,sid＜1kR+

得到節(jié)點i所屬層次編號為1kL+

end

根據(jù)所屬層次的1kβ+，得到節(jié)點i所屬的相關(guān)單元

end

61l=，()DM=0

7forl層的各個相關(guān)單元

end

8 根據(jù)式(5)計算失真度()DM

9 ifD(M)＞Dmax且l≤L

l=l+1

轉(zhuǎn)7，繼續(xù)選擇代表節(jié)點

end

10 輸出代表節(jié)點集()MΦ及()DM

NSS算法基于相關(guān)性將事件域劃分為若干相關(guān)單元，各個相關(guān)單元依據(jù)節(jié)點之間的支持度選取具有代表性的部分節(jié)點參與數(shù)據(jù)的傳輸，能有效降低無線傳感器網(wǎng)絡(luò)總的數(shù)據(jù)傳輸量，從而有效降低能耗。公式(5)顯示失真度的大小和參與運算的節(jié)點個數(shù)M、節(jié)點和事件源的距離及節(jié)點之間的距離相關(guān)，而NSS算法中可以通過調(diào)整圓環(huán)相關(guān)參數(shù)以得到不同的代表節(jié)點個數(shù)滿足實際應(yīng)用的需求。

4.性能分析及仿真

下面就本文提出的NSS算法用Matlab進行仿真，仿真參數(shù)見表1所示。4.1分析算法中各個參數(shù)對算法性能的影響，結(jié)果表明通過調(diào)整相應(yīng)參數(shù)可以得到不同的代表節(jié)點集以滿足不同的應(yīng)用場景；4.2在同等條件下比較相關(guān)算法對事件估計的失真度以及選取的代表節(jié)點個數(shù)占總節(jié)點數(shù)比例，仿真顯示NSS只需要選取較少的代表節(jié)點就能得到對事件源較為理想的估算精度。文中所有數(shù)據(jù)都是1000次試驗的平均值。

4.1 NSS算法性能分析

NSS算法中代表節(jié)點個數(shù)和相關(guān)單元的個數(shù)息息相關(guān)，而這又依賴于網(wǎng)絡(luò)中的參數(shù)。

表1 仿真參數(shù)

節(jié)點感知半徑Rc的影響：圖3顯示β1=π，Rc分別為{50，100，150，200}時，代表節(jié)點的個數(shù)以及失真度變化曲線。圖中顯示：隨著感知半徑cR的增大，代表節(jié)點個數(shù)減少，失真度也有所增加。這是因為當cR變大即節(jié)點感知的范圍增大，使得相鄰節(jié)點覆蓋重疊范圍也增加，感知信息大量冗余，這時只需要較少的代表節(jié)點。仿真也顯示，雖然cR取值不同，但是當代表節(jié)點數(shù)接近10左右時失真度最小，此后增加代表節(jié)點個數(shù)，失真度不但沒有降低反而有所增加，分析后知道，隨著遠離事件源的節(jié)點的加入，外界的干擾逐步增大，失真度會略微增加，這也是算法中考慮到感知節(jié)點和事件源位置的結(jié)果。

圖3 感知半徑對算法的影響

圖4 初始角對算法的影響

初始角度1β的影響：圖4顯示cR=100，1β分別為0.5π，π，1.5π，2π時代表節(jié)點的個數(shù)以及失真度曲線。圖中顯示，隨著1β的增加，代表節(jié)點個數(shù)減少，失真度卻增大了。這是因為初始角度增加，相關(guān)單元的面積增大，劃分的相關(guān)域個數(shù)減少，代表節(jié)點相應(yīng)減少。但是相關(guān)單元面積增大后，節(jié)點之間感知數(shù)據(jù)的相關(guān)度減少，因此失真度變大。但是，不管選取怎樣的1β，失真度變化的趨勢是一致的。

圖5 節(jié)點個數(shù)對算法的影響

節(jié)點數(shù)N的影響：圖5顯示cR=100，1β=π，事件域內(nèi)N的個數(shù)分別為50、100、300、1000的情況，結(jié)果顯示：隨著事件域內(nèi)感知的節(jié)點數(shù)量增加，失真度會變小，這是因為同樣的事件域內(nèi)感知到的節(jié)點個數(shù)越多，節(jié)點之間的相關(guān)度越高，感知的信息也越準確。值得注意的是，本文提出的NSS算法不僅能迅速找到具有代表性的節(jié)點，使得失真度快速下降，而且代表節(jié)點集的個數(shù)并沒有隨著節(jié)點個數(shù)的增加而迅速增加。這說明節(jié)點規(guī)模增加對算法影響不大。

圖6 算法性能比較

4.2 相關(guān)算法比較

為了評估算法的效果，在半徑為500的事件域中部署的節(jié)點數(shù)N分別為{50，80，100，150，200，250，300，350，400，450，500，600，700，800，900，1000}，計算最小失真度和選擇的代表節(jié)點數(shù)M占總節(jié)點數(shù)N的百分比，以此比較本文提出的NSS算法以及文獻[8]中提出的隨機節(jié)點選取和其后的INS算法的性能。仿真結(jié)果如圖6所示，圖中顯示，在同樣的環(huán)境下，隨機選取節(jié)點的算法波動性比較大，這是因為選擇的節(jié)點的位置是隨機的，造成對事件的感知精度也不確定。INS算法中代表節(jié)點選取節(jié)點總數(shù)的20％～40％能得到較小的失真度。而NSS算法能得到更為理想的失真度，代表節(jié)點數(shù)占總節(jié)點數(shù)的比例在N較小時較高，但是隨著N的增加迅速下降，逐漸趨于穩(wěn)定。分析后知道，算法中優(yōu)先考慮距離事件源較近的節(jié)點，能較好地反映事件真實信息，有利于降低失真度。但是當事件域內(nèi)節(jié)點數(shù)目較少時，節(jié)點之間的相關(guān)度不高，相對需要較多的代表節(jié)點參與信息的感知，之后隨著節(jié)點的逐步增加，節(jié)點感知信息之間的冗余增加，所選的代表節(jié)點個數(shù)占總節(jié)點數(shù)的比例逐步下降。

5.結(jié)論

針對事件驅(qū)動傳感器網(wǎng)絡(luò)中如何選取代表節(jié)點集傳遞感知數(shù)據(jù)來以獲取滿足一定精度要求的事件信息的問題，本文利用節(jié)點之間的空間相關(guān)性，在環(huán)狀相關(guān)性模型基礎(chǔ)上提出NSS算法，將事件域劃分為若干相關(guān)單元，并選取合適的節(jié)點作為代表節(jié)點協(xié)作參與數(shù)據(jù)傳輸。仿真表明算法性能穩(wěn)定，且能通過相關(guān)參數(shù)的調(diào)整滿足不同精度或應(yīng)用要求，算法能適應(yīng)不同規(guī)模的無線傳感器網(wǎng)絡(luò)。

6.致謝

本文章服務(wù)于國家自然科學(xué)基金資助項目（61300239）。

[1] G. Anastasi, M. Conti, M. Francesco. Energy Conservation in Wireless Sensor Networks: A survey. Adhoc Networks, 7:537-568, 2009.

[2] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. Wireless Sensor Networks: A Survey. Computer Networks, 38:393 422, 2002.

[3] M. Mitici, J. Goseling. Decentralized vs. Centralized Scheduling in Wireless Sensor Networks for Data Fusion. Acoustics, Speech and Signal Processing (ICASSP), 2014.

[4] Eskandari Z. , Yaghmaee M.H. , Mohajerzadeh A.-M. Automata Based Energy Efficient Spanning Tree for Data Aggregation in Wireless Sensor Networks. Communication Systems , ICCS 2008. 943-947,2008.

[5] Kulkarni, R.V. , Venayagamoorthy, G.K. Particle Swarm Optimization in Wireless Sensor Networks: A Brief Survey. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on Volume 41, Issue 2: 262- 267, 2011.

[6] Leandro A. Villas, Azzedine Boukerche. An Energy-Aware Spatial Correlation Mechanism to Perform Efficient Data Collection in WSNs. 11th IEEE International Workshop on Wireless Local Networks:882-889,2011.

[7] L. Doherty, K.Pister. Scattered Data Selection for Dense Sensor Networks. In Proceedings of IPSN’04, 2004.

[8] M. C. Vuran and B. Akan, I. F. Akyildiz. Spatiotemporal correlation: theory and applications for wireless sensor networks. Computer Network, vol. 45, no. 3,pp. 245 259, Jun. 2004.

[9] Gedik.B., Ling Liu and P.S. YU. ASAP: An Adaptive Sampling Approach to Data Collection in Sensor Networks. IEEE Transactions on Parallel and Distributed Systems, 18: 1766 1783, 2007.

[10] S.S. Pradhan and K. Ramchandran, Distributed Source Coding Using Syndromes (DISCUS): Design and Construction. Information Theory, IEEE Transactions 49: 626-643, 2003.

[11] Karjee, J. , Jamadagni, H.S. Data Accuracy Estimation for Cluster with Spatially Correlated Data in Wireless Sensor Networks. Communication Systems and Network Technologies (CSNT):427- 434,2012.

[12] Arnoldo Díaz-Ramíreza, Luis A. Tafoyaa, Jorge A. Atempaa, and Pedro Mejía-Alvarezb. Wireless Sensor Networks and Fusion Information Methods for Forest Fire Detection. Procedia echnology 3:69 79, 2012.

[13] Singh P. , Kumar R. , Kumar V.. An Energy Efficient Grid based Data Dissemination Routing Mechanism to mobile sinks in Wireless Sensor Network. Issues and Challenges in Intelligent Computing Techniques (ICICT): 401-409, 2014.

[14] Mehmet C. Vuran, and Ian F. Akyildiz. Spatial Correlation-based Collaborative Medium Access Control in Wireless Sensor Networks. IEEE/ACM Transactions on Networking. 14: 316 -329, 2006.

[15] Zoghi, M.R. ; Kahaei, M.H. Efficient sensor selection based on spatial correlation in wireless sensor networks. Computer Conference: 627- 632,2009.

[16] 蘇威,林亞平,尤志強,胡玉鵬,周四望. 無線傳感器網(wǎng)絡(luò)中一種環(huán)狀空間相關(guān)性模型. 計算機應(yīng)用研究,2008(25):1860～1863

[17] Ren Guocan, Ding Guowei. An Improved Isoline based Data Aggregation Scheme in Wireless Sensor Networks . Procedia Engineering,23: 326 332,2011.

An Efficient Node Selection Method in Event-Driven Wireless Sensor Networks

Zhu Min-ru, Guo Jian
(College of Computer, Nanjing University of Posts and Telecommunications, Jiang su Province, Nanjing 210003, China)

Event-driven wireless sensor networks need to make reasonable judgments for event states. In this paper, we study how to select a small number of active nodes so as to reduce energy consumption and acquire event states with minor cost. The proposed NSS (Node Supported Selection) algorithm exploits the spatial correlation in nodes and makes use of node supported degree to select representative nodes involved in data transmissions. Simulation results show that this algorithm can keep data accuracy with a small ratio of nodes. Besides, the performance of NSS is better than other algorithms, especially, it has good scalability.

Wireless Sensor Networks; Circular Spatial Correlation Model; Efficient Node Selection; Distortion

TP212

A

1009-5624-（2016）02-0051-06