傳感器網(wǎng)絡中節(jié)點能量有效均衡的Top-k查詢技術

宋保利 鄭吉平*② 王海翔

?

傳感器網(wǎng)絡中節(jié)點能量有效均衡的Top-查詢技術

宋保利①鄭吉平*①②王海翔①

①(南京航空航天大學計算機科學與技術學院 南京 210016)②(南京大學計算機軟件新技術國家重點實驗室 南京 210093)

無線傳感器網(wǎng)絡；能量均衡；近似top-查詢；反復隨機采樣

1 引言

Top-查詢[1,2]作為不確定數(shù)據(jù)和關系數(shù)據(jù)庫中廣泛使用的一種聚集查詢技術，在無線傳感器網(wǎng)絡中有著廣泛應用。傳感器節(jié)點由電池供電，能量有限。因此，節(jié)點能量高效以及能量均衡在無線傳感器網(wǎng)絡top-查詢中具有重要的現(xiàn)實價值和研究意義。

對于集中式環(huán)境中的top-查詢，已經(jīng)提出許多基于排序和修剪技術的方法減小計算復雜度以提高效率。然而，這些方法并不適應于分布式環(huán)境[3]。對于傳感器網(wǎng)絡環(huán)境下的top-查詢，人們已進行了一些研究工作。Madden等人[4]提出聚集技術TAG(Tiny AGregation)，但該方法存在大量冗余數(shù)據(jù)的傳輸。Wu等人[5]提出基于滑動窗口的top-查詢算法FILA(FILter-based monitoring Approach)，該算法基于過濾思想，為每一個節(jié)點設置一個過濾窗口，減少了冗余數(shù)據(jù)的傳輸，但會產(chǎn)生很大的窗口更新代價。Mai等人[6]提出通過預測方法減小窗口更新代價的DAFM(Distributed Adaptive Filter based Monitoring)算法，但節(jié)點讀數(shù)在時間上的線性自回歸預測法具有局限性。Chen等人[7]提出分位數(shù)過濾算法QF(Quantile Filter)，該算法可以避免大量冗余數(shù)據(jù)的上傳，但每個節(jié)點與父節(jié)點都要進行通信，傳感器網(wǎng)絡的無線通信次數(shù)仍然很大。在一些實際應用中，近似的top-查詢結(jié)果往往可以滿足用戶的需求。對于近似top-查詢處理的研究，Ye等人[8]提出傳感器網(wǎng)絡環(huán)境下的概率top-查詢，很大程度上減少了數(shù)據(jù)的傳輸，節(jié)省了能量，但傳感器網(wǎng)絡中數(shù)據(jù)是分布式存儲，計算代價較高，且中間節(jié)點能量消耗過快，不能實現(xiàn)傳感器網(wǎng)絡能量的均衡使用。Silberstein等人[9]提出基于采樣的top-查詢優(yōu)化算法PROSPECTORLP+LF(用LP+LF表示)，該算法可以有效地減少網(wǎng)絡中的全局能量消耗，但會導致頻繁落在top-結(jié)果集中的節(jié)點能量消耗過快而失效，不能實現(xiàn)節(jié)點能量的均衡使用。此外，上述兩種近似top-查詢處理算法不能滿足用戶的精度要求。

本文提出一種基于采樣技術和節(jié)點間空間相關性，實現(xiàn)節(jié)點能量高效且均衡的top-查詢處理技術。首先對傳感器網(wǎng)絡進行區(qū)域劃分，利用區(qū)域內(nèi)兩兩節(jié)點間的空間相關性對其建立預測模型。然后根據(jù)相對誤差界和置信水平，制定節(jié)點高相關性預測準則。最后，根據(jù)上述預測準則提出基于反復隨機采樣的算法EBSTopk(Energy Balance SamplingTopk)。在EBSTopk算法中每次只采樣區(qū)域中的一個節(jié)點，然后利用節(jié)點高相關性預測準則，根據(jù)該節(jié)點感知的數(shù)據(jù)對其它節(jié)點的值進行估計，依此進行，直至整個區(qū)域內(nèi)所有節(jié)點的值被直接采集或間接估計。EBSTopk算法很大程度上減少了傳感器網(wǎng)絡中節(jié)點的數(shù)據(jù)采集和無線通信。實驗表明，在滿足用戶查詢精度要求的前提下，本文提出的EBSTopk算法不僅可以降低網(wǎng)絡中的全局能量消耗，而且在多次近似top-查詢后各節(jié)點能量消耗相對均衡。

2 傳感器網(wǎng)絡中近似查詢Topk

2.1 問題定義

2.2 查詢精度分析

為分析查詢精度，引入定理1和定理2。

證畢

進一步得

3 EBSTopk算法

3.1 節(jié)點讀數(shù)相關性建模

通常由于傳感器網(wǎng)絡的應用環(huán)境不同，傳感器節(jié)點所感知的數(shù)據(jù)分布也會不同?？梢愿鶕?jù)不同的數(shù)據(jù)分布特點，發(fā)現(xiàn)其空間相關性，建立不同的預測模型。本文以線性回歸預測模型和多元高斯預測模型為例。

3.1.1線性回歸預測模型 假設傳感器節(jié)點感知的數(shù)據(jù)存在著很強的線性關系，可以對其建立線性回歸預測模型。

在實際傳感器網(wǎng)絡環(huán)境中，節(jié)點讀數(shù)在不同時刻不會只服從單一高斯分布。以一天的溫度值為例：早晨溫度通常逐漸升高，而到了晚上溫度逐漸下降。因此，可以將一天分成多個時間段分別建立高斯模型。

3.2 節(jié)點高相關性預測準則

當置信度足夠大時，可以認為節(jié)點的真實值x()就落在這個置信區(qū)間里，即

進一步求得

由式(11)和式(16)可得

3.3 能量均衡的采樣算法EBSTopk

將傳感器網(wǎng)絡劃分成多個區(qū)域，位置較近的節(jié)點劃分到同一區(qū)域。本文對如何更合理地進行區(qū)域劃分不做深入研究，僅根據(jù)節(jié)點位置信息以均值算法對傳感器網(wǎng)絡進行區(qū)域劃分。以伯克利大學英特爾實驗室無線傳感器網(wǎng)絡[14]為例，利用均值算法把其劃分成10個區(qū)域。表1所示為區(qū)域劃分結(jié)果，其中用方框框起來的節(jié)點表示在對傳感器網(wǎng)絡進行均值劃分時各區(qū)域的初始質(zhì)心節(jié)點。

表1伯克利大學英特爾實驗室無線傳感器網(wǎng)絡區(qū)域劃分結(jié)果

區(qū)域節(jié)點編號 R148, 49, 50, , 52 R27,, 9, 10, 11, 53, 54 R312, 13, , 15, 16 R417, 18, , 20, 21 R52, 3,, 5, 6 R644, , 46, 47 R738, 39, , 41, 42, 43 R81, 33, 34, , 36, 37 R928, 29,, 31, 32 R1022, 23, 24,, 26

基站通過歷史數(shù)據(jù)對區(qū)域內(nèi)兩兩節(jié)點間的空間相關性進行建模，求得模型參數(shù)，以及誤差標準差?；鞠蛎恳粋€節(jié)點發(fā)送此節(jié)點與其所在區(qū)域內(nèi)其它節(jié)點之間的模型參數(shù)以及誤差標準差。區(qū)域內(nèi)每一節(jié)點輪流擔任區(qū)域頭節(jié)點。首先，隨機選取一個節(jié)點作為區(qū)域頭節(jié)點，然后根據(jù)節(jié)點高相關性預測準則，選出與區(qū)域頭節(jié)點滿足高相關性預測準則的節(jié)點，這些節(jié)點的值可以通過區(qū)域頭節(jié)點的值估計得到。進而，在區(qū)域內(nèi)剩余節(jié)點再隨機采樣一個節(jié)點，估計與此節(jié)點滿足高相關性預測準則的節(jié)點的值。以此類推，直至獲得區(qū)域內(nèi)所有傳感器節(jié)點的值，其中包括直接采集值和間接估計值。區(qū)域頭節(jié)點選擇個值上傳給基站，不足個值，所有值一起上傳。最后基站把接收來的所有值進行排序，選擇前個值作為top-結(jié)果集?；谏鲜鏊枷?，本文提出能量均衡的采樣算法EBSTopk，具體算法如表2所示。

基站隨機選擇區(qū)域Ri的頭節(jié)點； 基站發(fā)送參數(shù), , k至區(qū)域Ri的頭節(jié)點； 令count(i)←1; 令access(RegionHead(i))←1; /*標識已獲得區(qū)域Ri的頭節(jié)點的讀數(shù)*/讀數(shù)*/ 令CurSNode←RegionHead(i); /*表示當前采樣節(jié)點*/ while count(i)

3.4 EBSTopk算法能耗分析

表3符號典型取值

符號取值 0.645 mJ 0.0144 mJ/Byte 0.258 mJ 0.00576 mJ/Byte

每個區(qū)域的能量消耗分為兩部分：采樣節(jié)點(不包含區(qū)域頭節(jié)點)以及區(qū)域頭節(jié)點的能量消耗。區(qū)域的總能量消耗記為E()，采樣節(jié)點的能量消耗記為E()，區(qū)域頭節(jié)點的能量消耗記為E()，則

4 實驗測評

實驗采用的數(shù)據(jù)集是Intel Lab Data[14]，該數(shù)據(jù)集是由部署在伯克利大學英特爾實驗室的54個傳感器節(jié)點感知現(xiàn)實環(huán)境中的多個屬性值得到。本文選擇2004年3月1日的溫度值作為實驗數(shù)據(jù)，利用Matlab仿真實驗來驗證本文所提出算法的有效性。

圖3 不同精度要求下的采樣次數(shù)

圖4 總能量消耗對比

圖5 各節(jié)點能量消耗對比

5 結(jié)束語

圖6 能量均衡水平對比

圖7 平均相對誤差

[1] 李文鳳, 彭智勇, 李德毅. 不確定性top-查詢[J]. 軟件學報, 2012, 23(6): 1542-1560.

Li Wen-feng, Peng Zhi-yong, and Li De-yi. Top-query processing techniques on uncertain data[J]., 2012, 23(6): 1542-1560.

[2] Dylla M, Miliaraki I, and Theobald M. Top-query processing in probabilistic databases with non-materialized views[C]. Proceedings of the 29th International Conference on Data Engineering, Brisbane, 2013: 122-133.

[3] Sun Yong-jiao, Yuan Ye, and Wang Guo-ren. Top-query processing over uncertain data in distributed environments [J]., 2012, 15(4): 429-446.

[4] Madden S, Franklin M, Hellerstein J,.. TAG: a Tiny AGgregation service for Ad-hoc sensor networks[J]., 2002, 35(SI): 131-146.

[5] Wu Min-ji, Xu Jian-liang, Tang Xue-yan,.. Top-monitoring in wireless sensor networks[J]., 2007, 19(7): 962-976.

[6] Mai H, Lee Y, Lee K,.. Distributed adaptive top-monitoring in wireless sensor networks[J]., 2011, 84(2): 314-327.

[7] Chen B, Liang W, Zhou R,Energy-efficient top-query processing in wireless sensor networks[C]. Proceedings of the 19th ACM International Conference on Information and Knowledge Management, Toronto, 2010: 329-338.

[8] Ye M, Lee W, Lee D,.. Distributed processing of probabilistic top-queries in wireless sensor networks[J]., 2013, 25(1): 76-91.

[9] Silberstein A, Braynard R, Ellis C,.. A sampling-based approach to optimizing top-queries in sensor networks[C]. Proceedings of the 22nd International Conference on Data Engineering, Atlanta, 2006: 68-78.

[10] Jindal A and Psounis K. Modeling spatially correlated data in sensor networks[J]., 2006, 2(4): 466-499.

[11] Wang C, Ma H, He Y,.. Adaptive approximate data collection for wireless sensor networks[J]., 2012, 23(6): 1004-1016.

[12] Fateh B and Govindarasu M. Energy minimization by exploiting data redundancy in real-time wireless sensor networks[J]., 2013, 11(6): 1715-1731.

[13] Deshpande A, Guestin C, and Madden S. Model-driven data acquisition in sensor networks[C]. Proceedings of the Thirtieth International Conference on Very Large Data Bases, Toronto, 2004: 588-599.

[14] Intel Berkeley Research. Laboratory. http://db. lcs.mit.edu /labdata/labdata.html. 2013. 2.

[15] Silberstein A, Braynard R, and Yang J. Constraint chaining: on energy-efficient continuous monitoring in sensor networks [C]. Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, Chicago, 2006: 157-168.

宋保利： 男，1987年生，碩士生，研究方向為傳感器數(shù)據(jù)管理.

鄭吉平： 男，1979年生，副教授，CCF高級會員，研究方向為感知數(shù)據(jù)管理、粒子濾波、蒙特卡羅方法等.

王海翔： 女，1989年生，碩士生，研究方向為信息物理融合、Skyline計算.

Energy-efficient and Balanced Top-Query Techniques in Sensor Networks

Song Bao-li①Zheng Ji-ping①②Wang Hai-xiang①

①(,,210016,)②(,,210093,)

Wireless sensor networks;Energy balance; Approximate top-query; Iterative random sampling

TP393

A

1009-5896(2014)06-1478-07

10.3724/SP.J.1146.2013.01163

鄭吉平 zhjcs@nuaa.edu.cn

2013-07-31收到，2013-10-16改回

國家973計劃項目(2014CB744900)，教育部博士點基金(20103218110017)，航空科學基金(20115552030)，江蘇高校優(yōu)勢學科建設工程，南京航空航天大學青年科技創(chuàng)新基金(NN2012102, NS2013089)和南京航空航天大學研究生開放基金(KFJJ120222)資助課題