文档介绍：天津大学硕士学位论文
无线传感器数据库中 KNN 查询算法研究
Research on KNN Query Algorithm in
Wireless Sensor Database System
学科专业：系统工程
研 究 生：黄才炎
指导教师：李敏强 教授
南国芳 副教授
天津大学管理学院
二零零九年五月
独创性声明
本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的
研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表
或撰写过的研究成果，也不包含为获得 天津大学 或其他教育机构的学位或证
书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中
作了明确的说明并表示了谢意。
学位论文作者签名： 签字日期： 年 月 日
学位论文版权使用授权书
本学位论文作者完全了解 天津大学 有关保留、使用学位论文的规定。
特授权 天津大学 可以将学位论文的全部或部分内容编入有关数据库进行检
索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校
向国家有关部门或机构送交论文的复印件和磁盘。
（保密的学位论文在解密后适用本授权说明）
学位论文作者签名： 导师签名：
签字日期： 年 月 日 签字日期： 年 月 日
中文摘要
有效的查询特定节点 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）对所提出的算法进行了大量的仿真。仿真结果显示混合索引结构融合了
两种索引结构的优点，达到了降低能耗和提高查询精度的目的。
关键词： 无线传感器 空间查询 KNN