传感器网络中基于抽样的带权近似Top—k查询算法

刘彩苹+蔡玉武+毛建旭+龙亚辉

摘 要：提出一种适用于传感器网络的抽样带权阀值过滤近似Top-k聚集查询算法.该近似算法会将无线传感器网络划成几个两两不相交的簇进行处理，在汇聚节点进行预处理以及在各个簇内进行抽样过滤处理，在抽样过程中给可靠而重要的节点赋上相应更大的权值，同时根据节点采集的信息具有时间相关特性，在簇内进行抽样阀值过滤处理，每个簇头节点都会接收到该簇内的Top-k候选子集，然后将每个簇的子集发送给Sink节点，该Sink节点将接收到能代表整网Top-k样本候选集.仿真实验结果显示该算法只需发送少量的数据，更小的抽样样本，并能满足任意精度要求.

关键词：无线传感器网络；抽样算法；Top-k查询

中图分类号：TP212.9 文献标识码：A

文章编号：1674-2974（2016）10-0134-05

Abstract：An approximate algorithm of Top-k query based on sampling and weight in wireless sensor network was presented. The algorithm divides the network into several disjoint clusters in the sink node and the nodes in cluster to take sampling process. In the process of sampling， greater weight for reliable and important sensor node is given. The sensor node sensing data has a time correlation， and sampling threshold filtering in the cluster. Each cluster head node receives a Top-k candidate subset of the cluster， and then sends the subset to the sink node. Finally， the sink node can receive a Top-k sample candidate that represents the whole network. Simulation experiments show that the algorithm only needs to send small data and smaller samples， and can satisfy arbitrary precision requirements.

Key words：wireless sensor networks； sampling algorithm； Top-k query

近年来，随着信息技术的快速发展，物联网时代已经悄悄向我们走来，无线传感器网络是物联网技术中关键技术之一.该技术广泛使用在现代化信息农业[1]、矿井智能化探测开采[2]和智能家居[3]等方面.传感器网络是由许多廉价的微型节点组织而成，可以在其监测范围内经由路由算法自组织成一个网络.用户在网络中会进行聚集查询处理，而Top-k查询是最常见的操作之一，具有非常大的实际意义，例如：用户在进行空气质量监测时，甲需要了解PM2.5值最大的k个值，乙需要了解空气质量指数最大的k个值，有时甲和乙对查询的精度标准和要求不一样，需要设计出能适应不同用户查询精度的Top-k聚集查询处理算法以便来满足多用户的实际应用需求.

由于传感器网络中的节点通信范围、计算处理、存储容量和能量大小都非常有限，聚集查询算法第一要务就要考虑节能，最大化网络的寿命.节点能量耗尽而失效，网络拓扑结构随时发生变化，而且节点在发送数据丢包和通信连接失败时，就会破坏生成的路由树，在很多情况下，传感器网络无法得到用户精确的查询分析结果.近年来，许多学者提出了许多能在传感器网络中进行近似查询的算法，近似算法能减少节点数据的发送量，节约节点的能量，最大化提高网络的寿命.

文献[4]提出一种垂直数据处理的Top-k算法.算法的主要思想是生成路由树，在路由树中进行Top-k查询，同时采用历史数据进行处理.文献[5]使用位图压缩机制减少节点间数据的发送量.节点能量和存储空间，但是恶意节点利用桶的信息可以估计出查询结果.文献[6]提出了一种近似Top-k聚集查询算法.该算法对传感器节点感知的数据进行抽样，并用线性模型得到满足用户精度要求的近似查询结果.文献[7]利用传感器节点感知数据的时空相关性.该算法采用综合样本抽样和数据压缩技术进行聚集查询.文献[8]提出了连续k近邻查询算法.算法的核心思想是采用环查询和变量维护技术减少节点数据的发送量.

文献[9]使用了一种概要查询处理技术.与其它查询算法不同的是在查询处理过程中只需要传输概要信息，而不需要传感器节点的感知值，这种技术可以减少节点的能量开销.文献[10]利用传感器网络的时间和空间相关性原理进行近似查询处理，减少节点数据的发送，降低能量的消耗.

实际上，节点在放置时往往出现分布不均匀的情况.目前的Top-k聚集查询算法有时并不能反映监测区域真实情况，例如下面情况：在环境污染监测的区域，越靠近人类居住或者水源的区域越重要，可能这些区域的空气质量指数并不是很高，但是它已经对人们的健康产生了影响，需要给用户报警提示.还有传感器网络监测某一小区的噪声大小，查询者需要了解噪声大小会影响居民最高的k个点，在监测范围内，离居民比较近的点噪声分贝值虽然不是最大的，但是它对居民的影响超出了远处分贝值比它高的点.为了满足实际的需要，可以对重要的区域增加权值的参数，扩大它的作用效果，从而更加能够反映传感器网络监测区域的真实情况[11].

传感器网络节点感知的数据具有时间和空间相关性，可以利用网络的历史查询信息估算出一个抽样阀值，在每个簇内进行抽样过滤处理时，只有大于阀值的感知值才会被发送给簇头节点，从而能够减少节点不相关信息的发送，节约能源，提高网络的寿命.

4 实验仿真及结果分析

在伯克利分校研究者研发的TAG[13]平台上进行实验.仿真实验中的感知数据来自于Berkeley Intel实验室传感器网络监测真实环境时得到的温度数据.

选取简单的Top-k抽样近似算法和本文的基于抽样带权阀值过滤近似Top-k聚集查询算法进行对比实验.

简单Top-k抽样近似查询算法由Sink节点随机独立地产生样本大小为S的样本，Sink节点将样本S广播到网络中进行抽样，如果节点编号在抽样样本中，就将该节点的信息发送给汇聚节点，汇聚节点收到数据后输出前k个最大值作为Top-k查询的近似结果.而带权近似Top-k查询抽样算法只需抽样本簇中少量数据发送给簇头节点，大大减少了数据的发送量，节省了网络中节点的能量.图1可以说明这种变化趋势.

选取简单Top-k簇内抽样近似查询算法和本文带权过滤簇内抽样算法在不同的网络规模下应当选取样本容量的大小关系如图2所示.

在（ε，δ）和k一定的条件下，简单Top-k抽样近似查询算法进行查询时随机独立地产生样本大小为S的样本.而抽样带权近似过滤Top-k查询处理算法通过给定的（ε，δ）和历史信息估计确定样本的容量S，在查询过程中根据权值确定查询概率计算每个簇内的抽样样本以及依据历史信息过滤抽样的样本值，得到能符合（ε，δ）精度的近似Top-k查询数据.从图2可以看出，在（ε，δ）和k确定的条件下，带权近似Top-k查询抽样算法在同样网络规模大小下样本容量比简单Top-k抽样近似查询算法都要小.

给定k值进行带权近似Top-k查询抽样算法时，抽样的样本容量与用户查询的精度大小和网络规模有着密切的关系，网络中节点的数量越多，查询精度要求越低，抽样的样本大小就越大，从图3的实验结果可以知道这种变化趋势.

5 结 语

本文提出一种适用于传感器网络的抽样带权阀值过滤近似Top-k聚集查询算法.与其它Top-k查询处理算法不同，本算法进行分簇抽样处理，并根据实际情况给节点加入了权值参数，同时在每个簇内进行抽样，根据历史信息过滤掉不必要的数据，每个簇头节点会将抽样子集传送给汇聚节点，最终汇聚节点收集到全网的满足用户查询精度的Top-k集合.带权近似Top-k查询抽样算法可以有效地减少节点不相关信息的发送，节约能量，提高网络的生命周期.与普通抽样算法相比，只需要更少的样本容量即可，同时可以满足不同用户对查询精度不同的请求.所以，带权近似Top-k查询抽样算法适用于注重节约节点能量的无线传感器网络，同时能满足多用户的精度要求，以及Top-k查询的近似结果可以反应传感器网络监测区域的真实情况.

参考文献

[1] BARBAGLI B， BENCINI L，MAGRINI I， et al. A real-time traffic monitoring based on wireless sensor network technologies[C]//Proceedings of the 7th International Wireless Communications and Mobile Computing Conference. Istanbul，Turkey： IEEE Computer Society， 2011：820-825.

[2] ZHANG F， DISANTO W， REN J， et al. A novel cps system for evaluating a neuralmachine interface for artificial legs[C]//Proceedings of IEEE/ACM International Conference on Cyber-Physical Systems. Chicago， USA： IEEE Computer Society， 2011：67-76.

[3] BOCCA M，TOIVOLA J，ERIKSSON M， et al. Structural health monitoring in wireless sensor networks by the embedded goertzel algorithm[C]//Proceedings of IEEE/ACM International Conference on Cyber-Physical Systems.Chicago：IEEE Computer So.Ciety， 2011：206-214.

[4] CHU D， DESHPANDE A， M.HELLERSTEIN J M，et al.data collection in sensor networks using probabilistic models[C]//In Proceedings of the 22th International Conference on Data Eingineering. Georgia， USA：April 3-7，2006： 234-251.

[5] CAO Q， ABDELZAHER T， HE T， et al.Towards optimal sleep scheduling in sensor networks for rare event detection[C]//Proceedings of IPSN.CA，USA：IPSN， 2005： 20-27.

[6] KOUSHANFAR F， TAFT N， POTKONJAK M.Sleeping coordination for comprehensive sensing using isotonic regression and domatic partitions[C]//Proceedings of IEEE Infocom.Barcelona， Spain： 2006：45-58.

[7] LI J，LI Z.Data sampling control，compression and query in sensor[J] . International Journal of Sensor Networks，2014，2（1/2）：53-61.

[8] YAO Yu-xia ， TANG Xue-yan， LIM Ee-peng .Localized monitoring of knn queries in wireless sensor networks[J]. The VLDB Journal， 2014，18（1）：99-117.

[9] NASRIDINOV A，PARKY H.Optimal aggregator node selection in wireless sensor networks[C]//Proceedings of ICCA.Seoal， Korea：ICCA，2013， ASTL， 2013： 37-39.

[10]DELIGIANNAKIS A，PROCESSING Y K. Approximate aggregation queries in wireless senor networks[J]. Information Systems， 2013， 31（8）：770-792.

[11]BI Ran，LI Jian-zhong，CHENG Si-yao.Approximate Top-k query processing algorithm in wireless sensor networks[J].Journal on Communications，2011，32（8）：45-54.

[12]BEMSEIN S， BERNSTEIN R. Elements of statistics II： descriptive statistics[M].Newyork：USA McGraw-Hill， 2004.

[13]MADDEN S， FRANKLIN M J， HELLERSTEIN J M.TAG： a tiny aggregation service for Ad-Hoc sensor networks[C]//Symposium on Operating Systems Design and Implementation.Boston：MA，2002：131-146.