无线传感器数据库中KNN查询算法研究

论文摘要

有效的查询特定节点q的k个最近邻居节点（即KNN查询）是当前无线传感器数据库空间查询算法的热点之一.目前具有代表性的KNN查询算法主要有GRT（Geo-routing tree）和IWQE（Itinerary-based Window Query Execution）查询算法,前者是基于索引结构的查询算法,后者是非基于索引结构的查询算法.本文即是在这些思想的引导下展开的,主要研究内容如下:1)系统阐述了无线传感器技术的发展及KNN查询算法的主要内容,对基于索引结构的GRT和非基于索引结构的IWQE算法进行详细的介绍.2)基于索引结构和非基于索引结构的查询算法,提出了混合索引结构的KNN查询算法?混合索引结构查询算法的核心思想是利用GPSR等非索引结构的位置路由算法转发查询请求至查询点q,q收到查询请求后根据k估计出所需要查询的半径大小,最后利用基于R-Tree结构的索引查询算法收集查询半径内的兴趣节点信息.并在此基础上,对查询半径的估计算法做出了改进,进而提出一种适用于动态拓扑网络结构的KNN启发式查询算法.3)对所提出的算法进行了大量的仿真?仿真结果显示混合索引结构融合了两种索引结构的优点,达到了降低能耗和提高查询精度的目的.

论文目录

• 中文摘要
• ABSTRACT
• 第一章 引言
• 1.1 课题背景
• 1.1.1 无线传感器数据库技术研究现状
• 1.1.2 KNN 查询算法研究现状
• 1.2 研究工作介绍
• 1.3 论文结构组织
• 第二章 无线传感器数据库及空间查询算法的介绍
• 2.1 无线传感器概念
• 2.2 无线传感器网络特点
• 2.3 无线传感器网络关键技术
• 2.4 空间查询算法
• 2.4.1 无线传感器数据库
• 2.4.2 空间查询算法
• 2.5 本章小结
• 第三章 混合索引结构的KNN 查询
• 3.1 基本概念
• 3.2 基于索引结构的KNN 查询算法
• 3.3 非基于索引结构的KNN 查询算法
• 3.3.1 路由阶段
• 3.3.2 KNN 查询半径估计阶段
• 3.3.3 查询半径内的查询与收集阶段
• 3.4 基于网络密度混合索引结构的KNN 查询算法
• 3.4.1 基于网络密度非索引的路由阶段
• 3.4.2 基于网络密度KNN 半径估计阶段
• 3.4.3 基于R-Tree 结构的查询与收集阶段
• 3.5 基于动态拓扑网络的 KNN 查询算法
• 3.6 本章小结
• 第四章 性能评价
• 4.1 仿真环境介绍
• 4.2 算法性能比较
• 4.2.1 算法性能指标说明
• 4.2.2 查询半径估计算法的比较
• 4.2.3 网络规模对KNN 查询算法的影响
• 4.2.4 k 对KNN 查询算法的影响
• 4.3 本章小结
• 第五章 总结与展望
• 参考文献
• 发表论文和科研情况说明
• 致谢