传感网中Top-k查询处理优化算法研究

摘要

无线传感网是一种以数据为中心的网络，具有自组织、大规模、拓扑动态、应用相关等特点，主要有信息采集、处理和查询等功能，其中信息查询是无线传感器网络研究的重点。根据无线传感器网络的以上特点和功能，诸多学者都提出了相关的算法以及解决方案，其中Top-k查询算法占据着重要的地位。而Top-k查询的有效实现也对信息检索有着至关重要的作用，但是传统网络或数据库Top-k查询并不适用于传感网，必须针对无线传感器网络的特点进行相应的修改或者调整。特别是随着前沿技术的发展（如物联网），大量的用户直接到物理世界搜索信息，因此Top-k查询处理本身也面临着许多新的挑战。从用户的角度来看，用户可以通过设置不同的优先级来请求相应的信息集。因此，Top-k不但要能够查询多维空间类型的数据，而且也要能够查询符合用户指定条件（偏好函数）的数据。从系统的角度来看，传感器网络通常由微小传感设备收集数据，这些设备通常有严格的能量限制，所以系统效率也是至关重要的。
　　本文提出了一个采用基于层排序的框架来满足以上两方面的需求。框架中我们首先采用擂台算法对节点采集的数据构造非支配集，再通过构建非支配集中数据间的父子关系形成DG图(Dominan tGraph)。在读入数据时框架会保持一个高效的DG图结构，包括DG图的构建和更新，以确保从DG图中获取的数据是正确的。本文通过实验对比发现，擂台算法相较于快速排序算法和改进的快速排序算法，在构造非支配集时所需要的运行时间优于后面两者，从而有效的减少了对能量的消耗，降低了构造过程时间的消耗，提高了查询处理的效率。最后本文提出了一个简单的Top-k查询算法，实验结果表明在k值较小的情况下，即使数据量增加，该查询算法仍能获得较好的查询效率，降低数据查询过程中能量的消耗。

目录

摘要

1 绪论

1．1 研究背景

1．2 传感器网络节点和体系结构

1．3 树结构的查询处理技术

1．4 数据融合处理技术

1．5 本文主要工作

1．6 本文组织结构

2 相关工作

2．1 传感网中Top-k查询处理技术

2．2 Skyline查询处理问题和Top-k查询

3 基于层排序的Top-k算法

3．1 Top-k查询定义

3．2 单个节点数据的查询

3．3 网内多节点的Top-k融合

3．4 Top-k算法具体步骤

4 实验与分析

4．1 测试平台与实验数据集

4．2 实验结果与分析

5 结论

5．1 研究工作总结

5．2 研究工作展望

参考文献

致谢

声明