传感器网络中能量有效的Top-k查询处理研究.pdf

摘 要 无线传感器网络是当前信息领域兴起的多学科交叉的重大前沿热点，广泛 用于军事侦查，情报获取，环境监测，交通管理，灾难预防，基础设施的安全 性监测等等。Top-k 查询是数据库和信息检索系统中一个长期研究的问题，其目 标是快速返回用户最希望得到的 k 个结果。 在传感器网络中 Top-k 查询有广泛的应用，与现有基于其他数据集的 Top-k 查询不同，传感器网络中的 Top-k 查询既有基于垂直数据分片的也有基于水平 数据分片的，既有快照查询也有连续查询。同时，由于传感器网络规模大，能 量少的特点，设计查询算法时关注的是如何减少能量消耗，侧重于利用网内处 理技术来减少数据传输。本文在前人的工作基础上，对传感器网络中基于水平 数据分片和垂直数据分片的 Top-k 查询分别进行了研究。 在传感器网络中基于水平数据分片的 Top-k 研究中，传统的查询需求大多 是在网络中找到监测值最大的 k 个节点。然而在实际应用中，人们关注的往往 不是某个节点的细节数据，而是网络中区域的整体状况，例如农场主需要找到 整个农场中最干旱的 k 块区域进行灌溉，传统的 Top-k 查询无法给出合理的答 案。针对这种特殊的需求，本文首次提出 Top-k Range 的概念，并利用TAG 树 结构提出解决 Top-k Range 问题的基本算法，由于此算法通信代价过高，又提出 解决 Top-k Range 问题的近似查询算法。利用传感器网络的空间相关性，构建基 于值的分簇模型（Value based D-hop Cluster ），将网络中地理位置靠近、监测值 相似的节点分到一个簇中，由簇头聚集簇内数据，以簇作为回答查询的单位。 理论分析和仿真都证明 Top-k Range 近似查询不仅能够满足用户的需求，并且大 大降低了传输代价。 在基于垂直数据分片的 Top-k 查询中，现有的 TJA 算法在对象位置特殊时 会产生较大的过滤集，从而导致网络中传输的数据激增。本文针对这一缺陷， 首先提出基于值的 Top-k join 算法（VTJA ），用阈值来过滤数据。又利用VDC 模型改进 VTJA 算法，根据各簇的值的范围，为其设置不同的阈值，各簇内节 点使用相同的阈值，从而避免出现各簇传输的对象数量不平衡的问题。还针对 对象缺失值的问题进行了研究，利用 Blomm Filter 原理在簇头和基站构建两级 1 索引来记录没有发送这个对象的节点，补全缺失值的时候，只要求这些节点报 告对象得分即可。从而减少查询处理过程中数据包传递的数量。 关键字：传感器网络 Top-k 查询 能量有效 2 Abstract In the recent years, wireless sensor networks (WSN), a kind of networks composed of several base stations and a large number of wireless sensors, have been widely used in many fields, such as military reconnaissance, intelligence acquisition environmental monitoring, traffic management, disaster prevention, security monitoring, etc. Top-k query has been studied for a long-term in database and information retrieval system, the goal