无线传感器网络数据查询关键技术研究

论文摘要

无线传感器网络（Wireless Sensor Network,WSN）,也称传感器网络（Sensor Network）,在军事、民用、环境监控、城市管理等领域有着非常广泛的应用。早期的无线传感器网络主要指节点一旦部署不再移动的静态无线传感器网络（Static Wireless Sensor Network,SWSN）,随着传感器网络研究的深入与拓展,汇聚节点sink可移动的动态无线传感器网络模型（Dynamic Wireless Sensor Network,DWSN）以及所有节点均可自由移动的机会无线传感器网络模型（Opportunistic Wireless Sensor Network,OWSN）被相继提出,进一步扩大了传感器网络的研究与应用领域。传感器网络下的数据查询是用户主动获取和分析网络感应数据集的重要手段。随着传感器网络研究的深入,数据查询领域出现许多新的课题。一方面,查询需求从简单的聚合查询逐渐向复杂查询拓展,Top-k查询、Skyline查询等查询算子被引入到传感器网络查询处理领域,如何克服通用查询处理算法的不足,结合查询算子特征,建立能量高效的面向具体算子的查询处理算法成为新的课题。此外,由于DWSN和OWSN下节点的移动性,DWSN下如何规划sink移动路径以提高查询处理性能,OWSN下如何建立适应OWSN特征的查询处理策略等都成为新的挑战。本文以传感器网络中的数据查询为研究内容,对不同传感器网络模型数据查询处理中的关键问题展开研究,提出有效的解决策略。本文的研究工作与主要成果包括：（1）针对SWSN下精确快照Top-k查询通用处理算法TAG能耗较高的问题,从结合查询算子特征与网络拓扑优化的角度,提出了SWSN下基于查询-验证机制与生成树优化的精确快照Top-k查询处理算法QVTOP。首先根据Top-k查询算子性质和传感器网络的通信特性,提出基于查询-验证机制的Top-k查询处理算法QVTOP-Base,通过首先查询少量高概率Top-k节点的实时数据并向其它节点分发验证,有效降低了通信能耗。在QVTOP-Base基础上,提出QVTOP-Improve算法,优化生成树结构,进一步降低查询分发与验证阶段的能耗。理论分析和仿真结果表明在感应数据平滑变化的应用中,QVTOP-Base算法和QVTOP-Improve算法有更高的能量有效性。（2）针对SWSN下的位置属性为决策属性之一的Skyline查询应用,提出了SWSN下Skyline查询与KNN控制关系相结合的KNNSkyline查询问题及基于区域划分的精确快照KNNSkyline查询处理算法RingSkyline（RS）。首先提出SWSN下的KNNSkyline查询问题,即寻找距离指定位置最近的k个Skyline值。根据KNNSkyline查询算子性质,提出基于区域划分的查询处理算法RSSerial和RSParallel。基本思想是将查询区域划分为若干以指定查询位置为中心的环形区,各环形区内的节点采用链簇式结构组织,采用分发并汇聚的模式进行查询处理。各环形区内的查询处理过程采用串行或并行的方式进行。理论分析和仿真实验结果表明,相比于集中式和TAG查询处理算法,RSSerial和RSParallel能实现KNNSkyline查询结果的渐进式输出并有效地降低了查询处理延迟与处理能耗。（3）针对DWSN下数据查询需要首先合理规划sink移动路线,但是已有的sink移动路径规划策略主要着重考虑节点的相关参数,并未考虑sink本身移动区域的约束这一问题,提出了sink移动区域受限下的路径规划问题。在假设网络为高密度稠密网络以及采用缓冲区辅助结果收集模式的前提下,分别针对sink可选移动路径全局信息已知和未知的情况,提出利用传输能耗与节点负载的理论计算模型进行Voronoi划分求解的理论建模规划策略和以最接近于将监测区域平分的最长路线为sink近似最优移动路线的启发式的规划策略。仿真实验结果表明了所提策略的可行性和有效性。（4）针对OWSN数据查询中需要高可靠、低延迟、低能耗地进行查询分发,将查询分发问题拓展为数据分发问题,提出了循环移动OWSN下基于节点分发能力细粒度评价的数据分发策略QADD。首先利用时间-概率图和转发状态-空间图对节点的循环移动模型进行描述,并研究了基于该模型对节点分发能力的细粒度计算。在此基础上,分别提出了面向延迟、可靠性和通信能耗优化的数据分发策略QADDd, QADDr和QADDc。主要思想是两节点相遇时,分别根据自身维护的转发状态-空间图评价自身对分发目标节点的分发能力,然后根据评价结果对分发计划进行拆分和交换,使得节点对持有的分发计划具有最大期望分发能力。仿真实验结果表明在循环移动模型机会传感器网络中,相比于多路单播分发策略,QADDd和QADDr策略具有更小的能耗、延迟与更高的可靠性。

论文目录

• 摘要
• ABSTRACT
• 目录
• 插图索引
• 术语中英对照表
• 第一章 绪论
• 1.1 研究背景和意义
• 1.2 相关研究现状及分析
• 1.2.1 无线传感器网络模型
• 1.2.2 SWSN数据查询研究现状及分析
• 1.2.3 DWSN通信模式与sink路径规划研究现状及分析
• 1.2.4 OWSN信息分发研究现状及分析
• 1.3 本文的主要研究内容
• 1.4 论文组织结构
• 第二章 SWSN基于查询-验证机制与生成树优化的Top-k查询
• 2.1 引言
• 2.2 相关工作
• 2.3 SWSN下的Top-k查询问题
• 2.3.1 相关定义
• 2.3.2 问题描述
• 2.4 问题分析
• 2.5 基于查询-验证机制与生成树优化的QVTOP算法
• 2.5.1 QVTOP-Base算法
• 2.5.2 QVTOP-Improve算法
• 2.6 QVTOP算法性能分析
• 2.6.1 正确性证明
• 2.6.2 传输开销与延迟分析
• 2.7 仿真实验与分析
• 2.7.1 仿真参数
• 2.7.2 仿真结果
• 2.8 本章小结
• 第三章 SWSN基于区域划分的k最近邻Skyline查询
• 3.1 引言
• 3.2 相关工作
• 3.3 SWSN下的k最近邻Skyline查询问题
• 3.3.1 相关定义
• 3.3.2 问题描述
• 3.4 问题分析
• Skyline（RS）算法'>3.5 基于区域划分的Ring_Skyline（RS）算法
• 3.5.1 RS基本思想
• 3.5.2 环形区的划分
• 3.5.3 链簇式结构的建立
• 3.5.4 两种模式下的RS算法
• 3.6 RS算法性能分析
• 3.6.1 正确性证明
• 3.6.2 传输开销与延迟分析
• 3.7 仿真实验与分析
• 3.7.1 仿真参数
• 3.7.2 仿真结果
• 3.8 本章小结
• 第四章 DWSN数据查询Sink移动区域受限下的路径规划
• 4.1 引言
• 4.2 相关工作
• 4.3 Sink移动区域受限下的路径规划问题
• 4.3.1 相关定义
• 4.3.2 问题描述
• 4.4 问题分析
• 4.5 Sink移动区域受限下的路径规划策略
• 4.5.1 Sink移动路网全局信息已知
• 4.5.2 Sink移动路网局部信息已知
• 4.6 仿真实验与分析
• 4.6.1 仿真参数
• 4.6.2 仿真结果
• 4.7 本章小结
• 第五章 循环移动OWSN下的查询分发
• 5.1 引言
• 5.2 相关工作
• 5.3 OWSN具有循环移动特征下的数据分发问题
• 5.3.1 相关定义
• 5.3.2 问题描述
• 5.4 问题分析
• 5.5 基于节点分发能力细粒度计算的QADD分发策略
• 5.5.1 节点循环移动的图模型
• 5.5.2 节点分发能力计算
• 5.5.3 QADD分发策略
• 5.6 QADD策略性能分析
• 5.7 仿真实验
• 5.7.1 仿真参数
• 5.7.2 仿真结果
• 5.8 本章小结
• 第六章 总结与展望
• 6.1 工作总结
• 6.2 下一步的工作展望
• 参考文献
• 致谢
• 攻读博士学位期间主要研究成果