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

传感器网络中基于抽样的带权近似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]利用传感器节点感知数据的时空相关性.