论文部分内容阅读
无线传感器网络是由大量布置在监测区域内的传感器以Ad Hoc方式构成的无线通讯网络。其目的是协作地感知、采集和处理网络覆盖区域内被监测对象的信息。由于传感器源源不断的产生各种观测数据,可以将传感器网络视为一种特殊的数据库,用户通过向传感器网络下发查询获取所需信息。无线传感器网络具有节点数量多、通信距离短、各种资源有限等特点。其中最重要的特点是每个节点的能量有限,因此针对传感器网络设计的各种查询处理算法必须尽量减小算法的能量消耗。数据存储是查询处理算法的重要组成部分,对传感器观测数据的合理组织可以有效减小查询处理过程中的能量消耗,延长网络生命周期。本文对传感器网络的数据存储及相关查询处理算法进行深入研究,主要研究成果如下:第一、提出一种基于时间索引的存储方法及相关查询处理算法,解决事件在整个网络分布出现较大偏斜情况下,传统以数据为中心存储方法中源节点对观测事件进行存储时所造成的能量浪费问题。在此情况下更节省能量的存储方法是:源节点将事件保存在本地,并在事件存储节点保存一个源节点观测事件发生的时间段作为索引。此时用户查询需要通过事件存储节点上保存的索引到源节点取得查询结果。本文分析了上述基于时间索引的存储方法较传统以数据为中心存储方法节省能量的条件,并据此提出一种自适应的数据存储选择算法。自适应算法可以根据用户查询与事件产生之间的实际情况,动态调整源节点的事件存储方法,使其始终保持最节省能量的状态。实验表明,自适应数据存储选择算法较传统的以数据为中心的存储方法节省能量。第二、提出一种基于环的数据存储方法及相关查询处理算法,解决事件在整个网络分布均匀情况下,传统以数据为中心存储方法存在的热点问题。基于环的存储方法将传感器网络划分成多个环,通过将各个传感器观测的事件分散存储在某个环形区域内的多个节点并使不同环之间轮换工作等方式,解决事件存储过程中出现的热点问题。同时,基于环存储的查询处理算法使环上的所有节点都参与到用户查询处理过程中,从而解决了查询处理过程中出现的热点问题。基于环的数据存储及查询处理算法通过使传感器网络中的所有节点均匀的消耗能量,达到延长网络寿命的目的。实验表明,基于环的数据存储及查询处理算法可以解决传统以事件为中心存储方法中出现的热点问题,延长网络寿命。第三、提出一种基于Filter存储的查询处理算法,解决传感器网络一种新的连续查询——连续动态范围查询。该查询与一般范围查询的关键区别在于:一般范围查询都是“静态”的,即查询范围由常数构成。本文提出的动态范围查询则是以传感器网络中某个传感器的实时观测值作为比较对象。具体的,连续动态范围查询的含义是:以网络中某个传感器当前周期的观测值作为比较对象,返回连续若干个周期内网络中观测值大于等于目标节点当前周期观测值的节点ID及其观测值。本文提出的基于Filter存储的查询处理算法为每个节点分配一个Filter作为阈值。节点根据当前周期的观测值与Filter值之间的关系决定将该观测值保存在本地或传递给sink。基于Filter存储算法的关键是为传感器网络中的各个节点设定合适的Filter值。本文通过分析基于Filter存储算法的能量消耗,选择使算法能量消耗最小的Filter值作为阈值。基于Filter存储的查询处理算法在减少基于局部存储查询处理算法广播次数的同时,还可以减少基于外部存储算法中不满足查询条件的无关节点向sink传递消息的数量。最后通过实验验证了本文提出的基于Filter存储算法较其他算法的能量节省性。第四、提出一种基于局部存储的能量有效查询处理算法,解决传感器网络一种新的snapshot查询——节点个数约束查询。节点个数约束查询指满足查询的一部分节点向用户返回结果,并使返回结果的节点个数占网络中满足查询节点总数的比例达到用户精度要求。与其他采用局部存储的查询处理算法相比,本算法的核心是利用节点个数约束查询的特点进行相关节点选择,不但减少了将查询在整个网络洪泛产生的能量浪费,还可以节省结果回收的能量消耗。具体的,算法由三部分构成:相关节点选择、能量有效的查询下发和能量有效的结果回收。相关节点选择算法用于从网络中寻找与用户查询相关的一部分节点,同时保证找到的节点满足用户的精度要求。能量有效的查询下发算法采用基于Steiner树的协议将查询下发到各个相关节点。能量有效的结果回收算法采用直接和间接两种方式进行结果回收,并给出两种方式在结果回收中节省能量的条件。实验表明,本文提出的基于局部存储的节点个数约束查询处理算法能够在满足用户精度的同时,使其能量消耗小于其他查询处理算法。