传感器网络中节点能量有效均衡的Top-k查询技术

宋保利 郑吉平*② 王海翔



传感器网络中节点能量有效均衡的Top-查询技术

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

①(南京航空航天大学计算机科学与技术学院 南京 210016)②(南京大学计算机软件新技术国家重点实验室 南京 210093)

无线传感器网络；能量均衡；近似top-查询；反复随机采样

1 引言

Top-查询[1,2]作为不确定数据和关系数据库中广泛使用的一种聚集查询技术，在无线传感器网络中有着广泛应用。传感器节点由电池供电，能量有限。因此，节点能量高效以及能量均衡在无线传感器网络top-查询中具有重要的现实价值和研究意义。

对于集中式环境中的top-查询，已经提出许多基于排序和修剪技术的方法减小计算复杂度以提高效率。然而，这些方法并不适应于分布式环境[3]。对于传感器网络环境下的top-查询，人们已进行了一些研究工作。Madden等人[4]提出聚集技术TAG(Tiny AGregation)，但该方法存在大量冗余数据的传输。Wu等人[5]提出基于滑动窗口的top-查询算法FILA(FILter-based monitoring Approach)，该算法基于过滤思想，为每一个节点设置一个过滤窗口，减少了冗余数据的传输，但会产生很大的窗口更新代价。Mai等人[6]提出通过预测方法减小窗口更新代价的DAFM(Distributed Adaptive Filter based Monitoring)算法，但节点读数在时间上的线性自回归预测法具有局限性。Chen等人[7]提出分位数过滤算法QF(Quantile Filter)，该算法可以避免大量冗余数据的上传，但每个节点与父节点都要进行通信，传感器网络的无线通信次数仍然很大。在一些实际应用中，近似的top-查询结果往往可以满足用户的需求。对于近似top-查询处理的研究，Ye等人[8]提出传感器网络环境下的概率top-查询，很大程度上减少了数据的传输，节省了能量，但传感器网络中数据是分布式存储，计算代价较高，且中间节点能量消耗过快，不能实现传感器网络能量的均衡使用。Silberstein等人[9]提出基于采样的top-查询优化算法PROSPECTORLP+LF(用LP+LF表示)，该算法可以有效地减少网络中的全局能量消耗，但会导致频繁落在top-结果集中的节点能量消耗过快而失效，不能实现节点能量的均衡使用。此外，上述两种近似top-查询处理算法不能满足用户的精度要求。

本文提出一种基于采样技术和节点间空间相关性，实现节点能量高效且均衡的top-查询处理技术。首先对传感器网络进行区域划分，利用区域内两两节点间的空间相关性对其建立预测模型。然后根据相对误差界和置信水平，制定节点高相关性预测准则。最后，根据上述预测准则提出基于反复随机采样的算法EBSTopk(Energy Balance SamplingTopk)。在EBSTopk算法中每次只采样区域中的一个节点，然后利用节点高相关性预测准则，根据该节点感知的数据对其它节点的值进行估计，依此进行，直至整个区域内所有节点的值被直接采集或间接估计。EBSTopk算法很大程度上减少了传感器网络中节点的数据采集和无线通信。实验表明，在满足用户查询精度要求的前提下，本文提出的EBSTopk算法不仅可以降低网络中的全局能量消耗，而且在多次近似top-查询后各节点能量消耗相对均衡。

2 传感器网络中近似查询Topk

2.1 问题定义

2.2 查询精度分析

为分析查询精度，引入定理1和定理2。

证毕

进一步得

3 EBSTopk算法

3.1 节点读数相关性建模

通常由于传感器网络的应用环境不同，传感器节点所感知的数据分布也会不同。可以根据不同的数据分布特点，发现其空间相关性，建立不同的预测模型。本文以线性回归预测模型和多元高斯预测模型为例。

3.1.1线性回归预测模型 假设传感器节点感知的数据存在着很强的线性关系，可以对其建立线性回归预测模型。

在实际传感器网络环境中，节点读数在不同时刻不会只服从单一高斯分布。以一天的温度值为例：早晨温度通常逐渐升高，而到了晚上温度逐渐下降。因此，可以将一天分成多个时间段分别建立高斯模型。

3.2 节点高相关性预测准则

当置信度足够大时，可以认为节点的真实值x()就落在这个置信区间里，即

进一步求得

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

3.3 能量均衡的采样算法EBSTopk

将传感器网络划分成多个区域，位置较近的节点划分到同一区域。本文对如何更合理地进行区域划分不做深入研究，仅根据节点位置信息以均值算法对传感器网络进行区域划分。以伯克利大学英特尔实验室无线传感器网络[14]为例，利用均值算法把其划分成10个区域。表1所示为区域划分结果，其中用方框框起来的节点表示在对传感器网络进行均值划分时各区域的初始质心节点。

表1伯克利大学英特尔实验室无线传感器网络区域划分结果

区域节点编号 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

基站通过历史数据对区域内两两节点间的空间相关性进行建模，求得模型参数，以及误差标准差。基站向每一个节点发送此节点与其所在区域内其它节点之间的模型参数以及误差标准差。区域内每一节点轮流担任区域头节点。首先，随机选取一个节点作为区域头节点，然后根据节点高相关性预测准则，选出与区域头节点满足高相关性预测准则的节点，这些节点的值可以通过区域头节点的值估计得到。进而，在区域内剩余节点再随机采样一个节点，估计与此节点满足高相关性预测准则的节点的值。以此类推，直至获得区域内所有传感器节点的值，其中包括直接采集值和间接估计值。区域头节点选择个值上传给基站，不足个值，所有值一起上传。最后基站把接收来的所有值进行排序，选择前个值作为top-结果集。基于上述思想，本文提出能量均衡的采样算法EBSTopk，具体算法如表2所示。

基站随机选择区域Ri的头节点； 基站发送参数, , k至区域Ri的头节点； 令count(i)←1; 令access(RegionHead(i))←1; /*标识已获得区域Ri的头节点的读数*/读数*/ 令CurSNode←RegionHead(i); /*表示当前采样节点*/ while count(i)

3.4 EBSTopk算法能耗分析

表3符号典型取值

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

每个区域的能量消耗分为两部分：采样节点(不包含区域头节点)以及区域头节点的能量消耗。区域的总能量消耗记为E()，采样节点的能量消耗记为E()，区域头节点的能量消耗记为E()，则

4 实验测评

实验采用的数据集是Intel Lab Data[14]，该数据集是由部署在伯克利大学英特尔实验室的54个传感器节点感知现实环境中的多个属性值得到。本文选择2004年3月1日的温度值作为实验数据，利用Matlab仿真实验来验证本文所提出算法的有效性。

图3 不同精度要求下的采样次数

图4 总能量消耗对比

图5 各节点能量消耗对比

5 结束语

图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年生，硕士生，研究方向为传感器数据管理.

郑吉平： 男，1979年生，副教授，CCF高级会员，研究方向为感知数据管理、粒子滤波、蒙特卡罗方法等.

王海翔： 女，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)，江苏高校优势学科建设工程，南京航空航天大学青年科技创新基金(NN2012102, NS2013089)和南京航空航天大学研究生开放基金(KFJJ120222)资助课题