ISSN 1000-9825,CODEN RUXUEW E-mail:jos@iscas.ac.cn Journal of Software http://www.jos.org.cn doi:10.3724/SP.J.1001.2009.03474 Tel/Fax:+86-10-62562563 by Institute of Sofare,the Chinese Academy of Sciences.All rights reserved. 基于环结构的传感器网络多分辨率数据存储机制 谢磊2，陈力军以+，陈道蓄口，谢立口 '(南京大学计算机软件新技术国家重点实验室，江苏南京210093) 南京大学.香港理工大学无线与移动传感器网络联合实验室江苏南京210093) Ring-Based Multi-Resolution Data Storage for Sensor Networks XIE Lei2,CHEN Li-Jun'2+,CHEN Dao-Xu'2,XIE Li' (State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210093,China) (NJU-POLYU Cooperative Laboratory for Wireless Sensor Network,Nanjing University,Nanjing 210093,China) +Corresponding author:E-mail:chenlj@nju.edu.cn.htp://dislab.nju.edu.cn Xie L,Chen LJ,Chen DX,Xie L.Ring-Based multi-resolution data storage for sensor networks.Journal of Software,2009.http://www.jos.org.cn/1000-9825/3474.htm Abstract:In this paper,a ring-based multi-resolution storage scheme for sensor networks is proposed.Combined with the hierarchical scheme for data storage and query,it leverages characters of the ring-based structure to support multi-resolution data storage and query operations,achieving a good performance in terms of energy consumption. It adopts optimal parameters for ring-based storage structures,which can well handle the hierarchical data storage and query scheme with the minimized overall communication cost.Furthermore,the authors do theoretical analysis on the performance of the ring-based multi-resolution storage scheme,including energy efficiency,load balance. The experimental results indicate that significant benefits can be achieved with this ring-based multi-resolution storage scheme. Key words:sensor network;data storage;event;query;ring;multi-resolution 摘要：提出了一套基于环结构的传感器网络多分辨率数据存储机制，结合层次结构的存储查询方案，有效地利 用了环结构的特性高效、节能地支持事件信息的不同分辨率的存储和查询操作，并采用优化的环结构参数，在基于 环的层次结构数据存储架构中能够最小化网络节，点的总体通信能耗同时，对环结构多分辨率数据存储机制的相关 性能从节能性、负载均衡性等多个角度进行了具体理论分析模拟实验结采表明，基于环的层次结构存储机制能够 高效、节能地支持传感器网络事件数据的多分辩率存储和查询操作 关键词：传感器网络：数据存储：事件：查询：环结构：多分辨率 中图法分类号：TP393、文献标识码：A 随着传感器技术、嵌入式计算技术以及低功耗无线通信技术的发展，无线传感器网络己经广泛地出现在环 ·Supported by the National Natural Science Foundation of China under Grant Nos.60s73132,60873026,60573I06(国家自然科学基 金；the National Basic Research Program of China under Grant No..2006CB303000(国家重点基础a研究发展计划(973)；the National High-Tech Research and Development Plan of China under Grant No.2006AA01Z199(国家高技术研究发展计划(863) Received 2007-12-06:Accepted 2008-10-09;Published online 2009-04-07 中国科学院软件研究所。hp/,j0s,org.cn
ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn Journal of Software http://www.jos.org.cn doi: 10.3724/SP.J.1001.2009.03474 Tel/Fax: +86-10-62562563 © by Institute of Software, the Chinese Academy of Sciences. All rights reserved. 基于环结构的传感器网络多分辨率数据存储机制∗ 谢 磊 1,2, 陈力军 1,2+, 陈道蓄 1,2, 谢 立 1,2 1 (南京大学 计算机软件新技术国家重点实验室,江苏 南京 210093) 2 (南京大学-香港理工大学 无线与移动传感器网络联合实验室,江苏 南京 210093) Ring-Based Multi-Resolution Data Storage for Sensor Networks XIE Lei1,2, CHEN Li-Jun1,2+, CHEN Dao-Xu1,2, XIE Li1,2 1 (State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China) 2 (NJU-POLYU Cooperative Laboratory for Wireless Sensor Network, Nanjing University, Nanjing 210093, China) + Corresponding author: E-mail: chenlj@nju.edu.cn, http://dislab.nju.edu.cn Xie L, Chen LJ, Chen DX, Xie L. Ring-Based multi-resolution data storage for sensor networks. Journal of Software, 2009. http://www.jos.org.cn/1000-9825/3474.htm Abstract: In this paper, a ring-based multi-resolution storage scheme for sensor networks is proposed. Combined with the hierarchical scheme for data storage and query, it leverages characters of the ring-based structure to support multi-resolution data storage and query operations, achieving a good performance in terms of energy consumption. It adopts optimal parameters for ring-based storage structures, which can well handle the hierarchical data storage and query scheme with the minimized overall communication cost. Furthermore, the authors do theoretical analysis on the performance of the ring-based multi-resolution storage scheme, including energy efficiency, load balance. The experimental results indicate that significant benefits can be achieved with this ring-based multi-resolution storage scheme. Key words: sensor network; data storage; event; query; ring; multi-resolution 摘 要: 提出了一套基于环结构的传感器网络多分辨率数据存储机制,结合层次结构的存储查询方案,有效地利 用了环结构的特性高效、节能地支持事件信息的不同分辨率的存储和查询操作,并采用优化的环结构参数,在基于 环的层次结构数据存储架构中能够最小化网络节点的总体通信能耗.同时,对环结构多分辨率数据存储机制的相关 性能从节能性、负载均衡性等多个角度进行了具体理论分析.模拟实验结果表明,基于环的层次结构存储机制能够 高效、节能地支持传感器网络事件数据的多分辨率存储和查询操作. 关键词: 传感器网络;数据存储;事件;查询;环结构;多分辨率 中图法分类号: TP393 文献标识码: A 随着传感器技术、嵌入式计算技术以及低功耗无线通信技术的发展,无线传感器网络已经广泛地出现在环 ∗ Supported by the National Natural Science Foundation of China under Grant Nos.60573132, 60873026, 60573106 (国家自然科学基 金); the National Basic Research Program of China under Grant No.2006CB303000 (国家重点基础研究发展计划(973)); the National High-Tech Research and Development Plan of China under Grant No.2006AA01Z199 (国家高技术研究发展计划(863)) Received 2007-12-06; Accepted 2008-10-09; Published online 2009-04-07
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.cn
2 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]提出了一个
谢磊等：基于环结构的传感器网络多分辨率数据存储机制 3 基于环结构的索引机制，在环上提供多个复制的索引节点来有效支持数据的分发与查询 上述这些支持多分辨率查询的层次结构的存储机制都采用基于GHT句的存储方案，具体结构如图1所示 通过将部署区域递归地划分为多个层次(L1,…,L),每个层次内包括一个或多个子区域，第1层只有1个子区域 即传感器网络覆盖的地理区域，第ⅰ层具有4个子区域，第i层每个子区域的大小是第+1层子区域大小的4 倍.在每个层次内采用地理散列函数把事件信息按关键字散列(hash)到某个地理点，并把数据存储到离该点最 近的传感器节点上这种基于GHT的存储方案使用地理散列函数将存储节点均匀地分布在部署区域内，结合使 用结构复制(structured replication)的方法，能够有效地分雄事件存储和查询的负载.但是，这种方案并不能够充 分考虑到存储节点的优化部署问题，对于事件的存储需要更新每一层的相关存储节点，并且对于多分辨率查询 中的全集查询(all-type query)和聚集查询(aggregate query),需要同时访问多个相关的存储节点，而基于GHT的 存储查询方案由于利用地理散列函数过分地分散存储节点，需要在网络中来回往复地访问多个存储节点，其存 储查询的总体能耗开销是相当大的.针对这个问题，基于Double Ruling的存储机制I3-l则使用了一种push-pull 结合的存储查询方式，如图2所示，事件生成节点p与查询节点g分别沿部署区域的水平方向和垂直方向产生 事件发布的push路径和事件查询的pul路径，当两条路径相交时即完成了对事件的查询.两条路径的正交性保 证了对于任意查询必然能够找到对应的事件存储节点获取数据.Double Ruling的存储查询机制通过合理部署 冗余存储节点，保证了在不需要精确定位信息情况下也能够实现事件存储查询任务，同时，通过平衡pus-pul路 径有效地降低了邻近节点间的事件存储查询开销，但由于事件和查询节点的随机分布性导致其存储节点的部 署结构也非充分优化的，同时不能提供合理的多分辨率层次结构的检索机制. 】 O y ●Storage node ○Ordinary node Fig.1 GHT based data storage Fig.2 Double ruling based data storage 图1基于GHT的存储机制 图2基于Double Ruling的存储机制 2问题描述与系统模型 2.1问题描述 基于前面对支持多分辨率查询的层次结构存储机制的分析，为了能够实现高效节能的传感器网络多分辨 率数据存储机制，我们需要考虑如何部署层次结构中的存储节点，充分减少在多个层次结构上的数据存储和查 询的路由开销，从而最小化存储查询的整体能耗.由此，我们需要构建优化的存储查询结构，并定制相应的优化 存储查询策略，从网络整体节能性、数据存储查询的有效便捷性、节点间的负载均衡性这几个方面来指导构建 优化的实现机制.基于这样的思路，我们综合借鉴GHT和Double Ruling的设计思想，提出半结构化的基于环的 层次结构的存储查询机制（如图3所示），采用优化的存储结构参数和存储查询策略来高效、节能地支持不同分 辨率的存储查询操作。 ⊙中国科学院软件研究所hp/W,j0s,org.cn
谢磊 等:基于环结构的传感器网络多分辨率数据存储机制 3 基于环结构的索引机制,在环上提供多个复制的索引节点来有效支持数据的分发与查询. 上述这些支持多分辨率查询的层次结构的存储机制都采用基于 GHT[5]的存储方案,具体结构如图 1 所示. 通过将部署区域递归地划分为多个层次(L1,…,Ld),每个层次内包括一个或多个子区域,第 1 层只有 1 个子区域, 即传感器网络覆盖的地理区域,第 i 层具有 4i−1 个子区域,第 i 层每个子区域的大小是第 i+1 层子区域大小的 4 倍.在每个层次内采用地理散列函数把事件信息按关键字散列(hash)到某个地理点,并把数据存储到离该点最 近的传感器节点上.这种基于 GHT 的存储方案使用地理散列函数将存储节点均匀地分布在部署区域内,结合使 用结构复制(structured replication)[5]的方法,能够有效地分摊事件存储和查询的负载.但是,这种方案并不能够充 分考虑到存储节点的优化部署问题,对于事件的存储需要更新每一层的相关存储节点,并且对于多分辨率查询 中的全集查询(all-type query)和聚集查询(aggregate query),需要同时访问多个相关的存储节点,而基于 GHT 的 存储查询方案由于利用地理散列函数过分地分散存储节点,需要在网络中来回往复地访问多个存储节点,其存 储查询的总体能耗开销是相当大的.针对这个问题,基于 Double Ruling 的存储机制[13−15]则使用了一种 push-pull 结合的存储查询方式,如图 2 所示,事件生成节点 p 与查询节点 q 分别沿部署区域的水平方向和垂直方向产生 事件发布的 push 路径和事件查询的 pull 路径,当两条路径相交时即完成了对事件的查询.两条路径的正交性保 证了对于任意查询必然能够找到对应的事件存储节点获取数据.Double Ruling 的存储查询机制通过合理部署 冗余存储节点,保证了在不需要精确定位信息情况下也能够实现事件存储查询任务,同时,通过平衡 push-pull 路 径有效地降低了邻近节点间的事件存储查询开销,但由于事件和查询节点的随机分布性导致其存储节点的部 署结构也非充分优化的,同时不能提供合理的多分辨率层次结构的检索机制. Fig.1 GHT based data storage Fig.2 Double ruling based data storage 图 1 基于 GHT 的存储机制 图 2 基于 Double Ruling 的存储机制 2 问题描述与系统模型 2.1 问题描述 基于前面对支持多分辨率查询的层次结构存储机制的分析,为了能够实现高效节能的传感器网络多分辨 率数据存储机制,我们需要考虑如何部署层次结构中的存储节点,充分减少在多个层次结构上的数据存储和查 询的路由开销,从而最小化存储查询的整体能耗.由此,我们需要构建优化的存储查询结构,并定制相应的优化 存储查询策略,从网络整体节能性、数据存储查询的有效便捷性、节点间的负载均衡性这几个方面来指导构建 优化的实现机制.基于这样的思路,我们综合借鉴 GHT 和 Double Ruling 的设计思想,提出半结构化的基于环的 层次结构的存储查询机制(如图 3 所示),采用优化的存储结构参数和存储查询策略来高效、节能地支持不同分 辨率的存储查询操作. p q Storage node Ordinary node Li+1 Li Li Li Li Li+1 Li+1 Li+1 Li+1 Li+1 Li+1 Li+1 Li+1 Li+1 Li+1 Li+1 Li+1 Li+1 Li+1 Li+1 Li 1 Li−1
Journal of Software软件学报 0 0 0 ●0入 0 0 000 o Ring 3 0 0 。8 0 00 0 0 oOrdinary sensor node .Index/Storage sensor node Fig.3 Ring based data storage 图3基于环结构的存储机制 2.2系统模型 本文假设N个传感器节点随机均匀地分布在半径为L的圆形部署区域内，节点间的平均距离为r根据多分 辨率存储查询机制的需求，层次结构的维度即环的个数为d,这里设默认值仁3，从内到外各环半径分别为 R1,R2,,Ra.所有层次上复制节点的冗余度为n.存在k个事件类型E1,E2…,E,事件发生频率为2…，其总体 更新频率为，有∫=∑，对应k个事件类型每层的存储节点数日（不考虑复制节点）分别为k,k2…,k4用户对 d种不同分辨率数据的查询频率分别为q1q25,…,9/其中，9(=1,2…，d)为相对查询频率我们假设网络中的节 点密度足够大，从而保证在每个方向都有很好的连通性，这样，通过统计数据在网络中传输路径的长度即可衡量 对应的通信能耗开销对于传感器网络的应用属性，本文假设具有如下性质：(1)传感器网络为静态网络，即节点 部署后不再移动：(2)节点可以获知其位置信息.节点依靠GPS或定位算法等辅助设施或算法获取位置信息： (3)查询用户分散在传感器网络部署区域内，事件信息与查询请求的生成符合随机、均匀分布的性质！ 3基于环结构的多分辨率事件存储和查询方案 对于传感器网络存储节点的优化部署问题，我们需要找出将存储节点放置在何处才能够使得整个传感器 网络事件存储和查询总能量开销最低.对于这个问题的研究，存在定理1， 定理1.若传感器节点均匀地分布在观察区域内，指定距离网络中心最近的节点作为事件存储节点，可使传 输事件所消耗的能量最少 对于定理】的证明，文献[10]有详细的证明过程因此在这里略去具体证明过程.通过定理1我们得知，对于 层次结构的多分辨率存储机制，为保证事件存储和查询的高效节能性，我们需要尽可能地将存储节点放置在网 络中心区域中，同时，考虑到这样可能会造成网络热点(hot spot))问题，需要利用复制存储节点方案(replicated storag©)来分摊存储和查询的传输量，由此，我们需要一个接近网络中心同时结合复制存储节点方案的网内存储 结构来高效、节能地处理多分辨率的事件存储和查询请求基于以上分析，我们提出一个基于环的层次结构的 存储机制，如图3所示，各层的存储节点成环状的形式以网络中心位置0为圆心聚集在其周围，这里，我们假设根 据应用需求设定层次结构维度仁3环1~环3上存储着不同分辨率的数据信息，各环之上包括同一层次的数据 存储节点(storage node)和复制存储节点(replicated storage node),以及普通的转发节点(forwarding node). 3.1基于环的层次式索引结构存储机制 对于层次式的索引结构，与DIMENTION,DIM相同，我们采用索引树的存储机制来构建层次式的存储结构 考虑索引树结构的存储，将整个索引树放到单个节点上的方案是不明智的，这样容易出现单点失效(single point of failur©)的问题，不利于存储节点的负载均衡性和高可用性需求.因此，我们考虑将索引树中的各个节点信息存 放在多个分布式的传感器节点上，如图3所示，以一个3层的索引树为例，我们将每层的索引节点分别存放在不 同的环结构上，按照由高到低的分辨率，环1存放着子区域L1,L2…,Lm上对事件E1,E2,…,E的精确数据，环2存 中国科学院软件研究所。hp/,j0s,org.cn
4 Journal of Software 软件学报 Ring 1 Ring 2 Ring 3 Ordinary sensor node Index/Storage sensor node O Fig.3 Ring based data storage 图 3 基于环结构的存储机制 2.2 系统模型 本文假设 N 个传感器节点随机均匀地分布在半径为 L 的圆形部署区域内,节点间的平均距离为 r.根据多分 辨率存储查询机制的需求,层次结构的维度即环的个数为 d,这里设默认值 d=3,从内到外各环半径分别为 R1,R2,…,Rd.所有层次上复制节点的冗余度为 n.存在 k 个事件类型 E1,E2,…,Ek,事件发生频率为 f1,f2,…,fk,其总体 更新频率为 f,有 1 k i i f f = = ∑ ,对应 k 个事件类型每层的存储节点数目(不考虑复制节点)分别为 k1,k2,…,kd.用户对 d 种不同分辨率数据的查询频率分别为 q1⋅f,q2⋅f,…,qd⋅f,其中,qi(i=1,2,…,d)为相对查询频率.我们假设网络中的节 点密度足够大,从而保证在每个方向都有很好的连通性,这样,通过统计数据在网络中传输路径的长度即可衡量 对应的通信能耗开销.对于传感器网络的应用属性,本文假设具有如下性质:(1) 传感器网络为静态网络,即节点 部署后不再移动;(2) 节点可以获知其位置信息.节点依靠 GPS 或定位算法等辅助设施或算法获取位置信息; (3) 查询用户分散在传感器网络部署区域内,事件信息与查询请求的生成符合随机、均匀分布的性质. 3 基于环结构的多分辨率事件存储和查询方案 对于传感器网络存储节点的优化部署问题,我们需要找出将存储节点放置在何处才能够使得整个传感器 网络事件存储和查询总能量开销最低.对于这个问题的研究,存在定理 1. 定理 1. 若传感器节点均匀地分布在观察区域内,指定距离网络中心最近的节点作为事件存储节点,可使传 输事件所消耗的能量最少. 对于定理 1 的证明,文献[10]有详细的证明过程.因此在这里略去具体证明过程.通过定理 1 我们得知,对于 层次结构的多分辨率存储机制,为保证事件存储和查询的高效节能性,我们需要尽可能地将存储节点放置在网 络中心区域中,同时,考虑到这样可能会造成网络热点(hot spot)问题,需要利用复制存储节点方案(replicated storage)来分摊存储和查询的传输量,由此,我们需要一个接近网络中心同时结合复制存储节点方案的网内存储 结构来高效、节能地处理多分辨率的事件存储和查询请求.基于以上分析,我们提出一个基于环的层次结构的 存储机制,如图 3 所示,各层的存储节点成环状的形式以网络中心位置 O 为圆心聚集在其周围,这里,我们假设根 据应用需求设定层次结构维度 d=3.环 1~环 3 上存储着不同分辨率的数据信息,各环之上包括同一层次的数据 存储节点(storage node)和复制存储节点(replicated storage node),以及普通的转发节点(forwarding node). 3.1 基于环的层次式索引结构存储机制 对于层次式的索引结构,与 DIMENTION,DIM 相同,我们采用索引树的存储机制来构建层次式的存储结构. 考虑索引树结构的存储,将整个索引树放到单个节点上的方案是不明智的,这样容易出现单点失效(single point of failure)的问题,不利于存储节点的负载均衡性和高可用性需求.因此,我们考虑将索引树中的各个节点信息存 放在多个分布式的传感器节点上,如图 3 所示,以一个 3 层的索引树为例,我们将每层的索引节点分别存放在不 同的环结构上,按照由高到低的分辨率,环 1 存放着子区域 L1,L2,…,Lm 上对事件 E1,E2,…,Ek 的精确数据,环 2 存
谢磊等：基于环结构的传感器网络多分辨率数据存储机制 5 放着每个子区域对事件E,E2,E,的概要数据，环3存放着对所有子区域相关事件的综合的概要数据，概要数 据的类型可以包括平均值(average)、最小值(min)、最大值(max)等类型.这些索引节点的存储信息分别适用于 不同的查询类型，包括精确数据查询、不同粒度的聚集查询、交互式的由粗到细的查询.各环的半径大小关系 R1,R2,R3可以根据用户的实际需求决定，也可以根据计算最优环半径参数结果而得，我们将在第34节讨论该问 题.各索引树存储节点之间通过转发节点连接，通过这种方式在传感器网络的分布式结构上构建出一个层次式 的索引树结构.在传感器网络的监测过程中，随着事件的产生将对索引树结构的相应节点进行更新，不同类型的 查询请求也根据其具体需求对相应层次的索引存储节点进行查找.考虑到负载均衡和高可用性的因素，可以在 层次式的环结构上提供索引树结构的冗余复制，复制的存储节点之间通过环结构进行同步和更新操作假设环 结构上提供的信息冗余度为n,即存在个复制索引树结构，我们基于角度来衡量环结构的信息冗余程度，即环 上每隔角度部署一个索引树结构，其中有一2πn. 3.2基于环结构的事件存储和查询路由方案 通过第3.1节介绍了基于环的层次式索引结构的数据存储机制，可以看到，该存储机制是对传统以数据为 中心多维存储机制的扩展对于这样的层次式索引结构，需要考虑如何构建高效节能的路由策略来支持事件的 存储和查询利用环和索引树的结构特性，我们提出基于环结构的事件存储和查询路由方案图4展示了基于环 结构的事件存储和查询路由方案，可以看到，基于环结构的路由路径包括两种：(1)向心路径：指向环的圆心的路 由路径，可以同时沿向心和离心两个方向延伸：(2)绕环 路径：沿环结构作顺时针或逆时针的路由路径对于事件 存储或查询的路由路径，会同时由这两种路径组成.下面， 我们分别介绍事件存储的路由策略与查询的路由策略。 对于事件存储的路由方案，事件节点S。感知到相关 事件E:后，根据S。在多个环结构中的位置，首先会沿向心 路径的单个两个方向路由传输事件信息，路由到相应的 环结构后，沿环绕路径顺时针或逆时针方向传输事件信 息，当到达环上索引结构中对应的存储节点时，存储或更 OEvent sensor node- Track of event 新该节点上的事件信息.若网络中存在复制的索引树结 Query sensor node-Track of query Fig.4 Routing strategy for event storage and query 构则在绕环路由时需要遍历更新所有的复制存储节点」 对于事件查询的路由方案，查询节点S。发出查询Q 图4事件存储和查询的路由策略 后，根据查询Q,的类型，首先会沿向心路径向对应层次的环结构路由传输查询请求，到达对应环结构后，沿绕环 路径顺时针或逆时针方向传输查询信息，寻找对应的事件信息，当到达环上索引结构中对应的存储节点时，获取 相应的查询结果完成查询后，存在两种路由策略：(1)沿原有路径返回；(2)寻找到查询节点S。最近的路由路径 返回 在整个路由过程中，所有节点使用地理路由协议GPSR根据节点的位置信息路由数据包，文献[20]对于在曲 线上的路由方案给出了详细的介绍，本文在设计绕环路由的具体实现时参考了文献[20]的曲线路由方案 3.3基于环的层次索引结构的构建与维护 本节介绍如何在传感器网络分布式的环境中构建和维护层次式的多环索引结构，具体包括环的构建以及 索引树的构建. (1)环的构建 对于环结构的构建，我们以部署区域中心处存在基站和不存在基站两种场景分别考虑：如果在部署区域中 心处存在基站，则在构建环结构之前由基站发送事先计算好的环结构参数(R1,R2…,R)的广播报文，每个节点S 接收到广播报文后，分别统计到基站的跳数h,同时将跳数h,递增(=h+1),向外层节点转发报文.假设节点间平 均距离为r,则跳数为「RrR2r「Rr的节点分别为环1,2，，d上的节点对于部署区域中心处不存在基站 中国科学院软件研究所。hp/,j0s,org.cn
谢磊 等:基于环结构的传感器网络多分辨率数据存储机制 5 放着每个子区域对事件 E1,E2,…,Ek 的概要数据,环 3 存放着对所有子区域相关事件的综合的概要数据,概要数 据的类型可以包括平均值(average)、最小值(min)、最大值(max)等类型.这些索引节点的存储信息分别适用于 不同的查询类型,包括精确数据查询、不同粒度的聚集查询、交互式的由粗到细的查询.各环的半径大小关系 R1,R2,R3 可以根据用户的实际需求决定,也可以根据计算最优环半径参数结果而得,我们将在第 3.4 节讨论该问 题.各索引树存储节点之间通过转发节点连接,通过这种方式在传感器网络的分布式结构上构建出一个层次式 的索引树结构.在传感器网络的监测过程中,随着事件的产生将对索引树结构的相应节点进行更新,不同类型的 查询请求也根据其具体需求对相应层次的索引存储节点进行查找.考虑到负载均衡和高可用性的因素,可以在 层次式的环结构上提供索引树结构的冗余复制,复制的存储节点之间通过环结构进行同步和更新操作.假设环 结构上提供的信息冗余度为 n,即存在 n 个复制索引树结构,我们基于角度来衡量环结构的信息冗余程度,即环 上每隔角度θ部署一个索引树结构,其中有θ=2π/n. 3.2 基于环结构的事件存储和查询路由方案 通过第 3.1 节介绍了基于环的层次式索引结构的数据存储机制,可以看到,该存储机制是对传统以数据为 中心多维存储机制的扩展.对于这样的层次式索引结构,需要考虑如何构建高效节能的路由策略来支持事件的 存储和查询.利用环和索引树的结构特性,我们提出基于环结构的事件存储和查询路由方案.图 4 展示了基于环 结构的事件存储和查询路由方案,可以看到,基于环结构的路由路径包括两种:(1) 向心路径:指向环的圆心的路 由路径,可以同时沿向心和离心两个方向延伸;(2) 绕环 路径:沿环结构作顺时针或逆时针的路由路径.对于事件 存储或查询的路由路径,会同时由这两种路径组成.下面, 我们分别介绍事件存储的路由策略与查询的路由策略. 对于事件存储的路由方案,事件节点 Se 感知到相关 事件 Ei 后,根据 Se 在多个环结构中的位置,首先会沿向心 路径的单个/两个方向路由传输事件信息,路由到相应的 环结构后,沿环绕路径顺时针或逆时针方向传输事件信 息,当到达环上索引结构中对应的存储节点时,存储或更 新该节点上的事件信息.若网络中存在复制的索引树结 构,则在绕环路由时需要遍历更新所有的复制存储节点. 对于事件查询的路由方案,查询节点 Sq 发出查询 Qi 后,根据查询 Qi 的类型,首先会沿向心路径向对应层次的环结构路由传输查询请求,到达对应环结构后,沿绕环 路径顺时针或逆时针方向传输查询信息,寻找对应的事件信息,当到达环上索引结构中对应的存储节点时,获取 相应的查询结果.完成查询后,存在两种路由策略:(1) 沿原有路径返回;(2) 寻找到查询节点 Sq 最近的路由路径 返回. 在整个路由过程中,所有节点使用地理路由协议 GPSR 根据节点的位置信息路由数据包,文献[20]对于在曲 线上的路由方案给出了详细的介绍,本文在设计绕环路由的具体实现时参考了文献[20]的曲线路由方案. 3.3 基于环的层次索引结构的构建与维护 本节介绍如何在传感器网络分布式的环境中构建和维护层次式的多环索引结构,具体包括环的构建以及 索引树的构建. (1) 环的构建 对于环结构的构建,我们以部署区域中心处存在基站和不存在基站两种场景分别考虑:如果在部署区域中 心处存在基站,则在构建环结构之前由基站发送事先计算好的环结构参数(R1,R2,…,Rd)的广播报文,每个节点 S 接收到广播报文后,分别统计到基站的跳数 hi,同时将跳数 hi 递增(hi=hi+1),向外层节点转发报文.假设节点间平 均距离为 r,则跳数为⎡R1/r⎤,⎡R2/r⎤,…,⎡Rd/r⎤的节点分别为环 1,2,…,d 上的节点.对于部署区域中心处不存在基站 Ring 1 Ring 2 Ring 3 Event sensor node O Track of event Query sensor node Track of query Fig.4 Routing strategy for event storage and query 图 4 事件存储和查询的路由策略