Journal of Software软件学报 境监测、目标追踪、突发事件报警等多种相关应用领域中组成无线传感器网络的传感器节点不仅能够接收物 理世界的感知数据，而且还能够有效地存储、计算和转发这些数据，以实现对部署区域感知信息的有效收集.本 文主要关注对传感器网络部署区域内相关事件进行监测的一类应用，在这类应用中，用户所关心的并不是大量 原始的感知数据，而是由这些底层原始数据所综合而成的事件信息.例如，对于火灾这个事件，信息往往包括火 灾发生的地点、时间以及周围的温度、湿度等诸多原始感知数据在这种应用场景下，传感器网络的用户往往 分布在传感器网络的部署区域之中，随时通过传感器网络对当前所感兴趣的事件信息进行查询.对于这种大规 模的事件探测和查询应用，传感器节点可能会在不同的观测区域探测到多种不同种类的事件信息而同时用户 发出的查询往往具有很高的选择性仅仅对其中某些区域某些种类的事件感兴趣，加之事件产生和查询请求是 随机出现的，分布在传感器网络的部署区域内，为了能够有效地处理用户的查询请求，需要充分利用传感器网络 的网内存储特性来支持信息的分发与收集.由于组成传感器网络的传感器节点往往具有苛刻的能耗限制，因此 设计一套高效节能的数据分发与收集机制，对大规模部署的传感器网络应用更为重要叮 针对传感器网络上不同查询用户所关心事件的粒度不同，某些用户只会关心特定地点某些特定事件的精 确信息，而其他一些用户则关心局部区域或整个区域内相关事件信息的概要数据，如平均值、最大值等，本文旨 在利用传感器网络以数据为中心的网内存储机制，提供一套多分辨率的事件存储机制以有效支持精确事件查 询、不同粒度的聚集查询以及由粗到细的混合查询请求，充分满足传感器网络中多种用户不同种类的应用需 求针对当前己有的传感器网络多分辨率存储机制在优化存储部署问题上的不足，本文提出了一套基于环的层 次结构的存储查询机制，采用优化的存储结构参数和存储查询策略来高效、节能地支持不同分辨率的存储查询 操作，实验结果表明，基于环结构的多分辨率存储机制能够有效地降低传感器网络的整体存储查询能耗， 本文第1节介绍以数据为中心的存储查询机制的相关工作第2节对本文研究的问题进行描述与分析，并 给出系统模型描述.第3节具体介绍基于环的层次结构的事件存储和查询机制，对存储查询策略和优化的环结 构参数进行分析第4节对环结构存储查询机制的各项性能进行具体理论分析第5节通过实验对相关性能进 行验证最后总结全文. 1相关工作 传感器网络的数据存储机制主要分为外部存储、本地存储和以数据为中心的存储机制文献[2-4]对这3 种机制的相关性能进行了具体的分析.其中，以数据为中心的存储机制(data centric storage)基于感知数据的属 性来存储和查询数据，通过映射算法将事件信息路由到对应的网内节点存储，同时，查询请求也通过相应的映射 算法路由至存储节点获取数据，这种机制又进一步分为结构化的存储机制和无结构的存储机制。 结构化的存储机制主要依赖于采用固定的映射算法，如地理散列函数将固定类型的事件信息映射到确定 的存储位置，查询节点能够使用与事件产生节点相同的地理散列函数寻找到特定的事件存储节点，并采用地理 路由协议(GPSR)路由到存储节点获取数据这种类型的存储方案主要包括GHT5-一类的方法，文献[10]基于 GHT提出了优化的结构化存储机制，无结构的存储机制主要依赖于采用push-pull技术来实现，1Push是指事 件节点在网络中的某些路径上分发事件信息，pl是指查询节点在网络中的某些路径上扩散查询信息.当查询 路径与事件分发路径相交时，即实现了相关事件信息的收集，因此，当前的无结构存储方案主要在于研究如何在 事件数据的push和pul之间实现更好的平衡，以充分达到高效、节能的效果.这种类型的存储方案主要包括 Double Ruling!3-l1,Rumor Routingl6等.文献[l刀提出了一个GHT与Double Ruling混合的数据分发方案，将整 个部署区域分为多片，在片间实现GHT分发方案，在片内实现Double Ruling的分发方案.文献[18]对这两类结构 化和无结构的数据存储机制进行了基本的扩展性分析 由于传感器网络上不同查询用户所关心事件的粒度不同，因此需要提供多分辨率层次结构的存储查询机 制来有效地支持不同粒度由粗到细的查询请求.文献[6,7刀提出了一个称为维(DIMENTION)的层次体系存储结 构，这种层次结构适合于下钻(drill down)操作，文献[8]给出了一种称为DIFS的分布式索引方法，可以有效地处 理区域查询，文献[9]提出了一个称为DM的能够支持多维属性区域查询的空间索引结构.文献19]提出了一个 中国科学院软件研究所。hp/,j0s,org.cn2 Journal of Software 软件学报 境监测、目标追踪、突发事件报警等多种相关应用领域中.组成无线传感器网络的传感器节点不仅能够接收物 理世界的感知数据,而且还能够有效地存储、计算和转发这些数据,以实现对部署区域感知信息的有效收集.本 文主要关注对传感器网络部署区域内相关事件进行监测的一类应用,在这类应用中,用户所关心的并不是大量 原始的感知数据,而是由这些底层原始数据所综合而成的事件信息.例如,对于火灾这个事件,信息往往包括火 灾发生的地点、时间以及周围的温度、湿度等诸多原始感知数据.在这种应用场景下,传感器网络的用户往往 分布在传感器网络的部署区域之中,随时通过传感器网络对当前所感兴趣的事件信息进行查询.对于这种大规 模的事件探测和查询应用,传感器节点可能会在不同的观测区域探测到多种不同种类的事件信息,而同时用户 发出的查询往往具有很高的选择性,仅仅对其中某些区域某些种类的事件感兴趣,加之事件产生和查询请求是 随机出现的,分布在传感器网络的部署区域内,为了能够有效地处理用户的查询请求,需要充分利用传感器网络 的网内存储特性来支持信息的分发与收集.由于组成传感器网络的传感器节点往往具有苛刻的能耗限制,因此, 设计一套高效节能的数据分发与收集机制,对大规模部署的传感器网络应用更为重要[1]. 针对传感器网络上不同查询用户所关心事件的粒度不同,某些用户只会关心特定地点某些特定事件的精 确信息,而其他一些用户则关心局部区域或整个区域内相关事件信息的概要数据,如平均值、最大值等,本文旨 在利用传感器网络以数据为中心的网内存储机制,提供一套多分辨率的事件存储机制以有效支持精确事件查 询、不同粒度的聚集查询以及由粗到细的混合查询请求,充分满足传感器网络中多种用户不同种类的应用需 求.针对当前已有的传感器网络多分辨率存储机制在优化存储部署问题上的不足,本文提出了一套基于环的层 次结构的存储查询机制,采用优化的存储结构参数和存储查询策略来高效、节能地支持不同分辨率的存储查询 操作.实验结果表明,基于环结构的多分辨率存储机制能够有效地降低传感器网络的整体存储查询能耗. 本文第 1 节介绍以数据为中心的存储查询机制的相关工作.第 2 节对本文研究的问题进行描述与分析,并 给出系统模型描述.第 3 节具体介绍基于环的层次结构的事件存储和查询机制,对存储查询策略和优化的环结 构参数进行分析.第 4 节对环结构存储查询机制的各项性能进行具体理论分析.第 5 节通过实验对相关性能进 行验证.最后总结全文. 1 相关工作 传感器网络的数据存储机制主要分为外部存储、本地存储和以数据为中心的存储机制.文献[2−4]对这 3 种机制的相关性能进行了具体的分析.其中,以数据为中心的存储机制(data centric storage)[2]基于感知数据的属 性来存储和查询数据,通过映射算法将事件信息路由到对应的网内节点存储,同时,查询请求也通过相应的映射 算法路由至存储节点获取数据,这种机制又进一步分为结构化的存储机制和无结构的存储机制. 结构化的存储机制主要依赖于采用固定的映射算法,如地理散列函数将固定类型的事件信息映射到确定 的存储位置,查询节点能够使用与事件产生节点相同的地理散列函数寻找到特定的事件存储节点,并采用地理 路由协议(GPSR)[5]路由到存储节点获取数据.这种类型的存储方案主要包括 GHT[5−9]一类的方法,文献[10]基于 GHT 提出了优化的结构化存储机制.无结构的存储机制主要依赖于采用 push-pull 技术来实现[11,12].Push 是指事 件节点在网络中的某些路径上分发事件信息,pull 是指查询节点在网络中的某些路径上扩散查询信息.当查询 路径与事件分发路径相交时,即实现了相关事件信息的收集.因此,当前的无结构存储方案主要在于研究如何在 事件数据的 push 和 pull 之间实现更好的平衡,以充分达到高效、节能的效果.这种类型的存储方案主要包括 Double Ruling[13−15],Rumor Routing[16]等.文献[17]提出了一个 GHT 与 Double Ruling 混合的数据分发方案,将整 个部署区域分为多片,在片间实现 GHT 分发方案,在片内实现 Double Ruling的分发方案.文献[18]对这两类结构 化和无结构的数据存储机制进行了基本的扩展性分析. 由于传感器网络上不同查询用户所关心事件的粒度不同,因此需要提供多分辨率层次结构的存储查询机 制来有效地支持不同粒度由粗到细的查询请求.文献[6,7]提出了一个称为维(DIMENTION)的层次体系存储结 构,这种层次结构适合于下钻(drill down)操作,文献[8]给出了一种称为 DIFS 的分布式索引方法,可以有效地处 理区域查询,文献[9]提出了一个称为 DIM 的能够支持多维属性区域查询的空间索引结构.文献[19]提出了一个