事件驅動無線傳感器網絡中有效節點的選擇方法

朱旻如 郭 劍

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

事件驅動無線傳感器網絡中有效節點的選擇方法

朱旻如 郭 劍

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

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

事件驅動無線傳感器網絡；環狀空間相關性；最優節點集選擇；節點支持度；失真度

1.引言

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

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

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

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

2.空間相關性模型

2.1 系統模型

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

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

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

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

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

其中：

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

2.2 環狀相關性模型

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

其中相關系數 是和節點之間距離 、節點和事件源距離 相關的，介于[0，1]之間的單調遞減非負函數。

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

圖1 環狀相關性模型示意圖

3.NSS算法

為解決事件驅動的傳感器網絡中選取有效的代表節點集傳遞感知數據的問題，根據上述環狀相關性模型，可以將公式(4)代入式(1)整理后得到：

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

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

因此，本文提出NSS算法：首先將事件域根據環狀相關性分層，而后劃分相關單元，使得相關單元內的節點相關度較高，最后根據節點支持度得到相關單元的代表節點。NSS算法得到的相關單元為如圖1所示的區域。

3.1 事件域分層

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

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

3.2 劃分相關單元

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

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

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

圖2 相關單元示意圖

3.3 確定代表節點

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

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

綜上，NSS算法流程如下：

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

α，β1，Rc//圓環相關半徑系數、相關域初始角度和節點感知半徑

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

Dmax//最大失真度

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

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

4β1=π,根據計算各層圓心角度數

5 for each ∈()NΦ

計算,sid //計算節點和事件發生位置的距離

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

得到節點i所屬層次編號為1kL+

end

根據所屬層次的1kβ+，得到節點i所屬的相關單元

end

61l=，()DM=0

7forl層的各個相關單元

end

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

9 ifD(M)＞Dmax且l≤L

l=l+1

轉7，繼續選擇代表節點

end

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

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

4.性能分析及仿真

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

4.1 NSS算法性能分析

NSS算法中代表節點個數和相關單元的個數息息相關，而這又依賴于網絡中的參數。

表1 仿真參數

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

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

圖4 初始角對算法的影響

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

圖5 節點個數對算法的影響

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

圖6 算法性能比較

4.2 相關算法比較

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

5.結論

針對事件驅動傳感器網絡中如何選取代表節點集傳遞感知數據來以獲取滿足一定精度要求的事件信息的問題，本文利用節點之間的空間相關性，在環狀相關性模型基礎上提出NSS算法，將事件域劃分為若干相關單元，并選取合適的節點作為代表節點協作參與數據傳輸。仿真表明算法性能穩定，且能通過相關參數的調整滿足不同精度或應用要求，算法能適應不同規模的無線傳感器網絡。

6.致謝

本文章服務于國家自然科學基金資助項目（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] 蘇威,林亞平,尤志強,胡玉鵬,周四望. 無線傳感器網絡中一種環狀空間相關性模型. 計算機應用研究,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