无线传感器网络时空查询处理技术研究

摘要

无线传感器网络能够实时地感知、收集、处理部署区域内监控对象的各种信息，利用无线通信将其返回至基站供用户查询和分析。它具有覆盖区域广、监测精度高等优点，在战场监测、医疗卫生、交通控制等领域有着广泛的应用前景，近年来成为研究热点。不同于传统的网络，无线传感器网络在计算、存储、能量、通信带宽等方面有诸多限制。传感器网络部署后，环境噪声、通信干扰、硬件故障均不可控。这些因素导致传感器网络应用开发十分复杂和困难。如何屏蔽传感器网络的复杂性，降低传感器网络应用开发的难度，是目前亟待解决的问题。
　　考虑到无线传感器网络是以数据为中心的网络，用户使用它的主要目的是查询其感知到的具有时间和空间属性的数据。本文将无线传感器网络整体看成一个分布式的时空数据库，研究无线传感器网络环境下的时空数据查询处理技术，设计并实现无线传感器网络时空数据查询系统，以有效地管理和查询其感知到的时空数据，从而简化无线传感器网络应用的开发。本文的研究成果包含以下几个方面:
　　(1)对于静态无线传感器网络，现有时空范围查询处理算法将全网络或查询区域中的节点组织成一棵路由树，查询区域内的节点通过该路由树将其查询结果返回给用户。采用单棵路由树会使得查询结果返回Sink节点的路径过长，导致能耗较大。证明了在绝大多数情况下，多路由树在能耗方面优于单路由树。设计了一种在查询区域内构造多棵路由树的协议，并基于该协议提出了一种低能耗的无线传感器网络时空范围查询处理算法E2STA(Energy-EfficientSpatio-Temporal Window Query Processing Algorithm for Wireless Sensor Networks)。实验结果表明，E2STA在能量消耗方面优于现有的算法。
　　(2)提出了一个高效的动态无线传感器网络时空范围查询处理框架EST(EfficientSpatio-Temporal Query Processing Framework for Wireless Sensor Networks)。它包含三个阶段:查询区域划分、查询消息分发、感知数据收集。通过查询区域划分，查询区域内节点的感知数据通过不同的转发路径返回，减少了网络中的“热点”;提出了一种基于位置路由的查询消息组播协议，并给出了一种基于路线的查询分发和感知数据收集协议，通过调度查询区域内的部分节点广播查询消息，减少了分发查询消息的能耗;感知数据利用位置路由协议直接返回至基站，减少了收集查询结果的能耗。实验结果表明，EST在能量消耗、网络生命周期方面均优于现有的算法。
　　(3)现有无线传感器网络环境下的空间范围聚集查询和K近邻查询处理算法能耗大，且当节点失效时查询处理过程易被中断，无法返回查询结果。给出了一种基于查询区域划分的容忍节点失效和能耗优化方案。查询区域被划分为若干个查询子区域。当节点失效时，失效节点所在查询子区域中的未失效节点恢复查询处理过程，减少了算法因节点失效而中断的概率。通过推导空间范围聚集查询和K近邻查询的能耗公式得到:在满足无线通信约束条件的前提下，查询子区域面积越大则总能耗越少。基于该结论，提出了最大化查询子区域面积的查子区域划分算法，降低了算法的总能量。
　　(4)设计并实现了一个具有动态可扩充能力的无线传感器网络时空查询处理系统SensorMapReduce。它由基站端的查询编译器和节点端的虚拟机两部分组成。提出了一个时空查询统一处理框架，将各种不同的时空查询抽象为四个基本操作:Map、Reduce、GetNextClusterNode、GetNextClusterShape。查询编译器将用户提交的各种时空查询编译成相应的Map、Reduce等代码，发送至节点虚拟机上解释执行。SensorMapReduce提供了声明性的时空查询语言，以屏蔽底层分布式查询处理的复杂性。通过扩充查询编译器，节点端程序无需改变，SensorMapReduce即可支持其他种类的查询，降低了节点重编程的代价。

目录

摘要

第1章 绪论

1．1 研究背景与意义

1．2 无线传感器网络查询处理相关技术研究现状

1．2．1 无线传感器网络数据管理

1．2．2 无线传感器网络查询处理技术

1．2．3 现有研究存在的问题

1．3 本文主要研究工作

1．3．1 本文主要的研究内容

1．3．2 本文的主要研究成果

1．4 本文的组织结构

第2章 静态无线传感器网络时空范围查询处理

2．1 引言

2．2 预备知识

2．2．1 基本时空范围查询处理算法FullFlood

2．2．2 基于R树的算法

2．2．3 STWinFlood算法

2．2．4 EcstaFlood算法

2．3 低能耗的传感器网络时空范围查询算法E2STA

2．3．1 E2STA算法

2．3．2 理论分析

2．3．3 实验分析

2．4 本章小结

第3章 动态无线传感器网络时空范围查询处理

3．1 引言

3．2 现有算法存在的问题

3．3 能量高效的动态传感器网络时空范围查询处理框架EST

3．3．1 查询区域划分阶段

3．3．2 查询消息发送阶段

3．3．3 分发查询和收集感知数据阶段

3．4 实验分析

3．4．1 比较查询消息发送协议

3．4．2 比较查询区域划分方法

3．4．3 比较能量消耗

3．4．4 比较网络生命周期

3．5 本章小结

第4章 无线传感器网络空间范围聚集查询处理

4．1 引言

4．2 相关工作

4．3 能量高效的传感器网络空间范围聚集查询处理算法

4．3．1 假设与符号定义

4．3．2 算法思想

4．3．3 算法设计

4．3．4 理论分析

4．4 实验分析

4．4．1 比较网格划分方法

4．4．2 比较簇头节点数目

4．4．3 比较能量消耗

4．4．4 比较查询成功率和查询结果质量

4．5 本章小结

第5章 无线传感器网络K近邻查询处理

5．1 引言

5．2 相关工作

5．3 鲁棒的传感器网络K近邻查询处理算法ROC-KNN

5．3．1 假设

5．3．2 算法基本思想

5．3．3 算法能耗分析及优化

5．3．4 算法设计

5．3．5 ROC协议流程

5．3．6 ROC-KNN算法流程

5．3．7 实验分析

5．4 本章小结

第6章 可扩充的无线传感器网络时空查询处理系统设计与实现

6．1 引言

6．2 无线传感器网络应用开发支撑平台研究现状

6．3 SensorMapReduce设计与实现

6．3．1 传感器网络模型

6．3．2 设计目标

6．3．3 硬件平台

6．3．4 SemorMapReduce体系结构

6．3．5 SensorMapReduce虚拟机

6．3．6 SensorMapReduce查询语言

6．3．7 SensorMapReduce时空查询处理机制

6．4 本章小结

第7章 总结与展望

7．1 总结

7．2 展望

参考文献

致谢

在学期间的研究成果及发表的学术论文