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 事件存储和查询的路由策略
6 Journal of Software软件学报 的情况，可以事先利用部署区域的地理位置信息计算出中心位置坐标(X,Yo),在构建环结构之前，每个节点根据 其位置(X计算到中心位置(Xo,Yo)的距离这里，我们定义距离函数D(X),Xo,Yo) D(X,Y),(X,o)》=VX-X)2+(Y-)2 (1) 若对于节点S有D(X,),(Xo,Y)-R≤Ra%(其中，a%为预设的误差参数，默认值a%=5%),则当前节点设为 环ⅰ上的存储节点对于上述两种场景，该阶段完成之后，环上每个节点向一跳内的周围邻居节点发送广播寻找 同一环上的邻居节点收到该广播的环上节点进行反馈构建环上邻居关系，由此，同一环上所有节点可以采用基 于GPSR的曲线路由机制2o围绕环结构顺时针或逆时针方向建立路由联系. (2)索引树的构建 完成环结构的构建之后，需要考虑如何在环结构上部署索引树结构来有效地支持多分辨率的事件存储和 查询任务.我们根据用户对d个不同层次存储结构的相对查询频率q1,q2,,q来将不同层次的索引存储节点部 署到不同半径的环结构上，根据查询频率递增地排序，我们依次将 对应层次存储结构部署在由内至外半径依次递增的环结构上.为 了便于后文分析，这里假设存在q1<q2<..<q,从而有对应的 R1<R2<.<R4通过后面第3.4节的论述可以验证这种部署策略能 够有助于使用优化的部署参数，是高效节能的考虑到负载均衡和 高可用性的需求，假设存在个复制索引树结构，则需要在环上每 隔角度部署一个索引树结构，其中有任2πn.如图5所示，传感器网 络在每个以角度扇形的区域内分别部署索引树结构，在每个扇形 ●Storage node o Forwarding node 区域的多个环结构上，传感器网络随机均匀地选择节点成为该区 Fig.5 Construct index tree over the rings 域的索引存储节点.对于该部署机制的分布式实现，在最内环上每 图5在环结构上构建索引树 个节点S产生一个随机数N,通过绕环路径路由传播并比较出数 值最大的随机数Nma,此时将产生Nmx的节点S设为地标 ((landmark)节点S4,S,以向心路径逆方向路由接触到多个外环对应的地标节点，分别将其设为S,S,,S2, 每个环上的地标节点沿绕环路径路由角度，均匀地选择环上节点成为索引树的存储节点，每隔角度完成对一 个索引树结构的部署如图5所示，环结构上部署完成的存储节点间由中转节点衔接保持互联关系 3.4选择优化的环结构参数 衡量传感器网络以数据为中心的存储查询方案的一个重要性能指标便是其节能特性，对于基于环结构的 多分辨率数据存储机制，为达到最小化的节能效果，我们需要对环结构的相关参数的优化问题进行研究、 为了计算环结构的优化参数，我们首先需要考察事件存储和查询对每个环结构的访问频率考虑层次结构 每个环上事件存储的访问频率，由于每个事件需要更新索引结构上每层相关节点，其对每个环的访问频率都是 固定的，因此将每个环的总体访问频率设为，根据第22节系统模 型的描述，有∫=∑，，即为每种事件发生频率之和对于事件查 询的访问频率，针对查询类型的不同，对每个环的访问频率也不同」 通常情况下，不同类型的查询只对相应层次的环结构进行访问由 此，我们根据第2.2节的系统模型定义对d种不同层次环结构的查 询访问频率分别为q,q2寸…，9f其中，9：为相对查询频率根据第 22节系统模型的描述，我们用事件存储查询路由路径的长度来表 示其能量开销，下面我们从最小化传感器网络总体能耗的角度来 对环的最优参数进行分析 我们来计算部署区域内部节点到环结构的平均距离D,如图6 Fig.6 Model of the ring-based structure 所示 图6环结构的模型 中国科学院软件研究所。hp/,j0s,org.cn
6 Journal of Software 软件学报 的情况,可以事先利用部署区域的地理位置信息计算出中心位置坐标(X0,Y0),在构建环结构之前,每个节点根据 其位置(X,Y)计算到中心位置(X0,Y0)的距离.这里,我们定义距离函数 D((X,Y),(X0,Y0)): 2 2 00 0 0 D XY X Y X X Y Y (( , ),( , )) ( ) ( ) = − +− (1) 若对于节点 S 有|D((X,Y),(X0,Y0))−Ri|≤Ri⋅α%(其中,α%为预设的误差参数,默认值α%=5%),则当前节点设为 环 i 上的存储节点.对于上述两种场景,该阶段完成之后,环上每个节点向一跳内的周围邻居节点发送广播寻找 同一环上的邻居节点,收到该广播的环上节点进行反馈构建环上邻居关系,由此,同一环上所有节点可以采用基 于 GPSR 的曲线路由机制[20]围绕环结构顺时针或逆时针方向建立路由联系. (2) 索引树的构建 完成环结构的构建之后,需要考虑如何在环结构上部署索引树结构来有效地支持多分辨率的事件存储和 查询任务.我们根据用户对 d 个不同层次存储结构的相对查询频率 q1,q2,…,qd 来将不同层次的索引存储节点部 署到不同半径的环结构上,根据查询频率递增地排序,我们依次将 对应层次存储结构部署在由内至外半径依次递增的环结构上.为 了便于后文分析,这里假设存在 q1<q2<…<qd ,从而有对应的 R1<R2<…<Rd.通过后面第 3.4 节的论述可以验证这种部署策略能 够有助于使用优化的部署参数,是高效节能的.考虑到负载均衡和 高可用性的需求,假设存在 n 个复制索引树结构,则需要在环上每 隔θ角度部署一个索引树结构,其中有θ=2π/n.如图 5 所示,传感器网 络在每个以θ角度扇形的区域内分别部署索引树结构,在每个扇形 区域的多个环结构上,传感器网络随机均匀地选择节点成为该区 域的索引存储节点.对于该部署机制的分布式实现,在最内环上每 个节点 Si 产生一个随机数 Ni,通过绕环路径路由传播并比较出数 值最大的随机数 Nmax ,此时将产生 Nmax 的节点 Sk 设为地标 (landmark)节点 L1 S . L1 S 以向心路径逆方向路由接触到多个外环对应的地标节点,分别将其设为 2 3 , ,..., L L Ld SS S , 每个环上的地标节点沿绕环路径路由θ角度,均匀地选择环上节点成为索引树的存储节点,每隔θ角度完成对一 个索引树结构的部署.如图 5 所示,环结构上部署完成的存储节点间由中转节点衔接保持互联关系. 3.4 选择优化的环结构参数 衡量传感器网络以数据为中心的存储查询方案的一个重要性能指标便是其节能特性,对于基于环结构的 多分辨率数据存储机制,为达到最小化的节能效果,我们需要对环结构的相关参数的优化问题进行研究. 为了计算环结构的优化参数,我们首先需要考察事件存储和查询对每个环结构的访问频率.考虑层次结构 每个环上事件存储的访问频率.由于每个事件需要更新索引结构上每层相关节点,其对每个环的访问频率都是 固定的,因此将每个环的总体访问频率设为 f,根据第 2.2 节系统模 型的描述,有 1 k i i f f = = ∑ ,即为每种事件发生频率之和.对于事件查 询的访问频率,针对查询类型的不同,对每个环的访问频率也不同. 通常情况下,不同类型的查询只对相应层次的环结构进行访问.由 此,我们根据第 2.2 节的系统模型定义对 d 种不同层次环结构的查 询访问频率分别为 q1⋅f,q2⋅f,…,qd⋅f,其中,qi 为相对查询频率.根据第 2.2 节系统模型的描述,我们用事件存储查询路由路径的长度来表 示其能量开销,下面我们从最小化传感器网络总体能耗的角度来 对环的最优参数进行分析. 我们来计算部署区域内部节点到环结构的平均距离 D,如图 6 所示. Fig.5 Construct index tree over the rings 图 5 在环结构上构建索引树 O Ri Ring i+1 Storage node Forwarding node Ring i+2 Ri+1 Ring i Ri+2 θ Fig.6 Model of the ring-based structure 图 6 环结构的模型 O Ri L Dout Din
谢磊等：基于环结构的传感器网络多分辨率数据存储机制 (1)环内节点到环i的平均距离Dn D(R)= g-ae- (2) 2x1 (2)环外节点到环i的平均距离D ∫r-R后rd0d Dove(R,)= 2(E+R+LR-R (3) a0-号0 3 L+R, 因此，环内、环外所有部署节点到环i的平均距离D为 21 D(R)= a0-a0 (4) do ·D(R)+ Eao 0风-号器-R 考虑基于环结构的多分辨率存储查询模型整体能量消耗Eo,由于在各环上存储事件信息时共享向心路 由的路径，在这里我们单独将共享的向心路由能耗Em抽取出来计算，对于各环上的路由能耗E(R)只包括事 件存储的绕环路由能耗Eproduceo(R,)和事件查询能耗E comsumer(R Eean=Emm+∑E(R)=Ewn+∑(E at-(R)+E.(R》 (5) 下面，我们分析环的半径R,以及冗余复制数n这两个环结构参数对总体性能的影响。 事件存储绕环路由平均每次能量开销为2πRP(n),其中P()为绕环路由的比例参数，这是由于复制存储机 制的存在，对应事件信息需要更新到所有的复制存储节点，结合个复制节点的均匀分布性，可以验证，在平均情 况下： Pm)=1-1=2n-1 (6) 2n2n 根据第2.2节系统模型的描述，假设事件存储的对环i的访问频率为∫，因此有 8风=2R29分/ (7) 对于事件查询在环结构上的平均能量开销，主要包括向心路由的能耗开销D(R)和绕环路由的能耗开销 2πRP'(),P'()为绕环路由的比例参数，由于复制存储机制的存在，查询只需要访问到任意一个复制存储节点即 可，可以验证，在平均情况下： P(n)=2n (8) 这里我们假设查询完成后采用沿原路返回的路由策略，结合事件查询对环1的相对访问频率q,因此有 5R1=24[04器} (9) 根据上述分析结果，环上事件存储与查询的整体平均能耗开销（除去事件存储共享向心路由的能耗） E(R)E()+E(R)=2+2D(R)+ (10) 2n 2n 带入公式(4)中DR)的结果，我们有， 风)-号/R+[420-*2-24/R+4y (11) n 3 对于事件存储共享向心路由的能耗Em,考虑到事件节点相对多环结构的位置可能存在3种情况：多环之 内、多环之间以及多环之外，由此综合考虑向心路由能耗的期望值有 ⊙中国科学院软件研究所。hp/W.j0s,0rg.cn
谢磊 等:基于环结构的传感器网络多分辨率数据存储机制 7 (1) 环内节点到环 i 的平均距离 Din: ( ) 2 0 0 2 2 0 ( ) dd 1 ( ) 1 3 d 2 Ri i in i i Rr r r DR R R θ θ π π − = = ∫ ∫ ∫ (2) (2) 环外节点到环 i 的平均距离 Dout: ( ) 2 2 2 0 2 2 2 2 0 0 ( ) dd 2 ( ) 1 1 3 d d 2 2 i L i R i i out i i i rR r r L R LR DR R L R L R θ θ θ π π π − ⎛ ⎞ + + = =− ⎜ ⎟ ⎝ ⎠ + − ∫ ∫ ∫ ∫ (3) 因此,环内、环外所有部署节点到环 i 的平均距离 D 为 2 22 2 22 3 0 0 0 2 2 2 2 2 0 0 1 11 d dd 2 2 2 22 () () () 1 1 3 3 d d 2 2 i i i i in i out i i R LR R DR D R D R L R L L L θ θθ θ θ π ππ π π − = ⋅ + ⋅ =⋅ + − ∫ ∫∫ ∫ ∫ (4) 考虑基于环结构的多分辨率存储查询模型整体能量消耗 Eoverall,由于在各环上存储事件信息时共享向心路 由的路径,在这里我们单独将共享的向心路由能耗 Ecentri 抽取出来计算,对于各环上的路由能耗 E(Ri)只包括事 件存储的绕环路由能耗 Eproducer-round(Ri)和事件查询能耗 Econsumer(Ri): 1 1 ( ) ( _ ( ) ( )) d d overall centri i centri producer round i consumer i i i E E ER E E R E R = = =+ =+ + ∑ ∑ (5) 下面,我们分析环的半径 Ri 以及冗余复制数 n 这两个环结构参数对总体性能的影响. 事件存储绕环路由平均每次能量开销为 2πRi⋅P(n),其中 P(n)为绕环路由的比例参数,这是由于复制存储机 制的存在,对应事件信息需要更新到所有的复制存储节点,结合 n 个复制节点的均匀分布性,可以验证,在平均情 况下: 121 () 1 2 2 n P n n n − =− = (6) 根据第 2.2 节系统模型的描述,假设事件存储的对环 i 的访问频率为 f,因此有 _ 2 1 ()2 2 producer round i i n E RR f n − = π⋅ ⋅ (7) 对于事件查询在环结构上的平均能量开销,主要包括向心路由的能耗开销 D(Ri)和绕环路由的能耗开销 2πRi⋅P′(n),P′(n)为绕环路由的比例参数,由于复制存储机制的存在,查询只需要访问到任意一个复制存储节点即 可,可以验证,在平均情况下: 1 ( ) 2 P n n ′ = (8) 这里我们假设查询完成后采用沿原路返回的路由策略,结合事件查询对环 i 的相对访问频率 qi,因此有 2 () 2 () 2 i consumer i i i R E R q DR f n ⎡ π ⎤ = + ⋅ ⎢ ⎥ ⎣ ⎦ (9) 根据上述分析结果,环 i 上事件存储与查询的整体平均能耗开销(除去事件存储共享向心路由的能耗): _ 21 2 () () ()2 2 () 2 2 i i producer round i consumer i i i i n R ER E R E R R f q DR f n n − π ⎡ ⎤ = + =π ⋅ ⋅ + + ⋅ ⎢ ⎥ ⎣ ⎦ (10) 带入公式(4)中 D(Ri)的结果,我们有, 3 2 4 (2 1 2 ) 4 () 2 3 3 i ii i i ii q n q Lq ER f R q f R f L n ⎡ ⎤ π −+ = ⋅⋅ + − ⋅⋅ + ⋅ ⎢ ⎥ ⎣ ⎦ (11) 对于事件存储共享向心路由的能耗 Ecentri,考虑到事件节点相对多环结构的位置可能存在 3 种情况:多环之 内、多环之间以及多环之外,由此综合考虑向心路由能耗的期望值有
Journal of Software软件学报 E=D,R)+(R-R答/+R-Rx2星/+DR)+R-RIx2我/ 2 (12) =证1代+购+1-了R 由公式(12)可以看到，Ecmm仅与最内环半径R1和最外环半径R。相关，因此，我们将整体的优化问题拆分为 R,R:和R(=2,…,d-1)(R10,即当q1/2,则E随n的增大而减小，此时，当→o时节能效果最优，但考虑到传感器节点的存储能力是有限的，因此 →0是不可行的，我们只有在满足节点存储能力的前提下尽可能地提高n.下面，我们将分别考虑最优半径参数 的取值 对于R,(=2,…,d-1)参数(R10)分别加以讨论： ()当n满足1s元时，存在2n-)2n-D恒成立，公式1)中R,项的参数为非负数，ER 2(n-π) 2(n-π) 与R呈单调递增关系，为保证总体能耗最低，此时，R=0时使E(R)取得最小值，因此，在这种条件下R应越小越好 (2②)当n满足>元时，存在2m-)>0,此时有 2(n-π) a 当02-时，公式中见项的参数为负数R)随见递减后又递增因此，我们需要道过求取极值的 2(n-元) 方式来求取最优解R,我们将E(R)对R求偏导数得 E(R)_443R2+ x2n-1+2g2-2,=0 (16) 通过公式(1)求得最优解R: 1 R 2n-1+24.π.L (17) 2n 2g: 中国科学院软件研究所。hp/,j0s,org.cn
8 Journal of Software 软件学报 2 22 22 1 1 11 1 1 22 2 3 3 2 1 1 [ ( ) ( )] ( ) [ ( ) ( )] 1 2 ( ) 3 3 d d centri in d d out d d d R R R LR E DR R R f R R f D R R R f LL L f R R Lf fR L − − = + − × ⋅+ − × ⋅+ + − × ⋅ = ⋅⋅ + + ⋅−⋅ (12) 由公式(12)可以看到,Ecentri 仅与最内环半径 R1 和最外环半径 Rd 相关,因此,我们将整体的优化问题拆分为 R1,Rd 和 Ri(i=2,…,d−1)(R10,即当 q1/2,则 E 随 n 的增大而减小,此时,当 n→∞时节能效果最优,但考虑到传感器节点的存储能力是有限的,因此 n→∞是不可行的,我们只有在满足节点存储能力的前提下尽可能地提高 n.下面,我们将分别考虑最优半径参数 的取值. 对于 Ri(i=2,…,d−1)参数(R10)分别加以讨论: (1) 当 n 满足 1≤n − π 恒成立,公式(11)中 Ri 项的参数为非负数,E(Ri) 与 Ri呈单调递增关系,为保证总体能耗最低,此时,Ri=0 时使 E(Ri)取得最小值,因此,在这种条件下 Ri应越小越好. (2) 当 n 满足 n>π时,存在 (2 1) 0 2( ) n n π − > − π ,此时有: 当 (2 1) 0 2( ) i n q n π − − π 时,公式(11)中 Ri 项的参数为负数,E(Ri)随 Ri 递减后又递增.因此,我们需要通过求取极值的 方式来求取最优解 * Ri ,我们将 E(Ri)对 Ri 求偏导数得: 2 2 ( ) 4 (2 1 2 ) 3 20 3 ii i i i i ER q n q R q RL n ∂ π −+ ⎡ ⎤ =⋅+ − = ⎢ ⎥ ∂ ⎣ ⎦ (16) 通过公式(17)求得最优解 * Ri : * 1 2 12 22 2 i i i n q R L n q −+ π = − ⋅⋅ (17)
谢磊等：基于环结构的传感器网络多分辨率数据存储机制 9 从公式(17)可以看出，此时最优解R的取值与9，呈单调递增关系，由于我们在部署层次索引结构时实施了 按照访问频率q,递增关系由内至外部署环结构的策略，即存在q2≤q≤.…≤qu1,因此，我们可以确保R≤R≤…≤ R的结果 对于环结构的半径R1,Ra的优化问题，我们根据冗余复制数目n2l,n为整数)结合q:的不同取值情况(q>O) 分别加以讨论： (①当n满足1s2m-)-”恒成立：对于R存在2n-》-恒成立这样，公式4中R项(=1，④的参数为非负数，此时，(R)与R呈单调递增关系，为保证总体 能耗最低，当R=0时，使E(R,)取得最小值. (2)当n满足>元时，对于R,存在2n--”>0,对于R存在2m->0,此时有 2(n-π) 2(n-元) 当0<4，≤2n-”或0<4≤2n-D时，公式14)中R项=l,d的参数为非负数，ER)与R星单调递 2(n-π) 2(n-π) 增关系，为保证总体能耗最低，当R=0时，使E(R)取得最小值 -核公纯帅州参狼随港装咸型 2(n-元) 我们将E对R求偏导数来求取极值R,得到 OE' =0 R= 2n-元)4，+n-2wm+元.L 41q1+n (18) ae' =0 2(n-元)9a-2n+T.L aR R= 4nga +n 为了确保R1≤R2,R≥R4-1的约束关系，对于R1,R的最优值R,R的取值有， R'=min(R,R2),Ri=max(RR). 通过上述的环结构半径最优值求解，我们最终可以确保R≤R≤≤R的结果.当存在一个或多个 R→0(=1,2，…，k,1≤k≤小的情况时，此时考虑到有效分摊各区域节点负载的需求，我们定义一个最小环间隔的 参数4d,存在当k<d时有0<4KRk,当=d时有0<4kL/d.此时可以设定R=Ad,R+=R+△d(=1,2,,k,1≤k≤d. 可以验证该机制对多个9，相等或逼近相等导致R充分接近的情形同样适用d的设定可以根据具体应用的节 能需求来设定，通常4d越小，其节能效果越逼近最优值，但其负载均衡性能越差；反之，4d越大，其负载均衡性能 越优，但同时节能效果越偏离最优值 4性能分析 本节我们对基于环结构的传感器网络多分辨率存储查询机制的相关性能进行理论分析，分析过程中，我们 从下列几个方面进行性能评价：()事件存储和事件查询的能耗开销以及网络总体能耗开销：(2)聚集查询的性 能，(3)网络能耗负载均衡性能.。 4.1环结构存储查询机制的性能 根据第3.4节的分析，在选择优化的环结构参数后，我们最终得到的整体网络的能耗为Eal,有 5m=5n（g.心+是g)=E民购+2+6-K》 d-1 (19) 对于同样的参数，如果使用基于GHT结构化的层次结构存储机制，其整体网络的能耗Eoe!包括事件存储 开销和查询开销，在最坏情况下，所有的存储和查询开销都为整个部署区域的直径长度，因此，其能耗为 中国科学院软件研究所。hp/,j0s,org.cn
谢磊 等:基于环结构的传感器网络多分辨率数据存储机制 9 从公式(17)可以看出,此时最优解 * Ri 的取值与 qi 呈单调递增关系,由于我们在部署层次索引结构时实施了 按照访问频率 qi 递增关系由内至外部署环结构的策略,即存在 q2≤q3≤…≤qd−1,因此,我们可以确保 * * 2 3 R R ≤ ≤≤ ... * Rd −1 的结果. 对于环结构的半径 R1,Rd的优化问题,我们根据冗余复制数目 n(n≥1,n 为整数)结合 qi的不同取值情况(qi>0) 分别加以讨论: (1) 当 n 满足 1≤n − π 恒成立;对于 Rd 存在 (2 1) 0 2( ) n n π − − π 恒成立.这样,公式(14)中 Ri 项(i=1,d)的参数为非负数,此时,E(Ri)与 Ri 呈单调递增关系,为保证总体 能耗最低,当 Ri=0 时,使 E(Ri)取得最小值. (2) 当 n 满足 n>π时,对于 R1 存在 (2 1) 0 2( ) n n n π −− > − π ,对于 Rd 存在 (2 1) 0 2( ) n n π − > − π ,此时有: 当 1 (2 1) 0 2( ) n n q n π −− − π 或 (2 1) 2( ) d n q n π − > − π 时,公式(14)中 Ri 项(i=1,d)的参数为负数,E(Ri)随 Ri 递减后又递增.因此, 我们将 E′对 Ri 求偏导数来求取极值 Ri ′ ,得到 1 1 1 1 2( ) 2 0 4 2( ) 2 0 4 d d d d E n qn n R L R nq n E nq n R L R nq n ⎧∂ ′ ⎧ −π + − π +π = ⎪ ′ = ⋅ ⎪ ⎪ ⎪ ∂ + ⎨ ⎨ ⇒ ∂ ′ ⎪ ⎪ −π − π +π = ′ = ⋅ ⎪ ⎪ ⎩∂ + ⎩ (18) 为了确保 R1≤R2,Rd≥Rd−1 的约束关系,对于 R1,Rd 的最优值 * R1 , * Rd 的取值有, * * R1 12 = min( , ) R R′ , * * R RR d dd max( , ) −1 = ′ . 通过上述的环结构半径最优值求解,我们最终可以确保 ** * 1 2 ... R ≤ R R ≤ ≤ d 的结果.当存在一个或多个 * 0 Ri → (i=1,2,…,k,1≤k≤d)的情况时,此时考虑到有效分摊各区域节点负载的需求,我们定义一个最小环间隔的 参数∆d,存在当 k<d 时有 0<∆d< * Rk +1 /k,当 k=d 时有 0<∆d<L/d.此时可以设定 R1=∆d,Ri+1=Ri+∆d(i=1,2,…,k,1≤k≤d). 可以验证该机制对多个 qi 相等或逼近相等导致 * Ri 充分接近的情形同样适用.∆d 的设定可以根据具体应用的节 能需求来设定,通常∆d 越小,其节能效果越逼近最优值,但其负载均衡性能越差;反之,∆d 越大,其负载均衡性能 越优,但同时节能效果越偏离最优值. 4 性能分析 本节我们对基于环结构的传感器网络多分辨率存储查询机制的相关性能进行理论分析,分析过程中,我们 从下列几个方面进行性能评价:(1) 事件存储和事件查询的能耗开销以及网络总体能耗开销;(2) 聚集查询的性 能;(3) 网络能耗负载均衡性能. 4.1 环结构存储查询机制的性能 根据第 3.4 节的分析,在选择优化的环结构参数后,我们最终得到的整体网络的能耗为 Eoverall,有 1 1 ** * ** * * 1 1 2 2 ( , ) ( ) ( , ) ( _ ( ) ( )) d d overall centri d i centri d producer round i consumer i i i E E R R ER E R R E R E R − − = = = += + + ∑ ∑ (19) 对于同样的参数,如果使用基于 GHT 结构化的层次结构存储机制,其整体网络的能耗 Eoverall 包括事件存储 开销和查询开销,在最坏情况下,所有的存储和查询开销都为整个部署区域的直径长度,因此,其能耗为
0 Journal of Software软件学报 Enm=f-22L+4l-g） (20) i=l 考虑结构化层次结构的存储机制在平均情况下的能耗开销图7展示了层次结构存储机制中某一层的存 储节点部署结构.可以看到，在结构化的存储机制中，其存储节点是均匀分散在部署区域中的因此，对不同方位 存储节点的平均存储查询路由开销是不同的我们可以根据其距离中心位置的不同划分为多个近似的环结构 利用公式(4)的运算结果来近似计算其存储和查询开销.假设1-d层的层次结构中，第ⅰ层存在k种类型的存储 节点，每种类型存储节点存在n个复制节点，则存储节点间距离D,=2L√·k),存在的环结构数目为 n,1og2(nk/2)1,每个环的半径近似等于0.5D,1.5D…,(n,-0.5)D,则根据式(4)的运算结果，i层的能耗开销E,可 以表示为 E,=f1+2q) &[2U-0.5D+2L-U-0.5)D) 3 (21) 因此平均情况下结构化层次结构的存储机制总体能耗为 Enm-25=f+24.-0DL+2L-U-0.5-D 22) 3 3 通过分析比较上述环结构存储查询方案和基于GHT的结构化存储查询方案我们可以看到，环结构存储查 2L 询方案的特点决定了其性能上的优点：()环结构事件 存储时向心路由的路径可以充分共享，这使得事件存 储路由时仅通过一条向心路径(dmax(R,一R1,R-R1, R,一R),R为事件节点所在半径)就可以经过多个层次环 结构更新数据，有效地降低了整体的路由能耗，而结构 化存储查询机制层次结构存储节点之间的路由不存在 共享路径，往往需要来回反复经过多个层次结构进行 更新，其节能效果是不理想的：(2)环结构使用优化的 部署参数确定存储节点的部署位置，从理论上证明能 够充分降低存储和查询的整体路由开销，而对于结构 Fig.7 GHT based deployment of the ith level storage 化的层次结构存储查询机制并未充分考虑到其优化部 图7基于GHT的第i层存储节点部署 署问题如图7所示，对于每一层存储节点并未将所有 存储节点放置到节能效果最优化的位置上：(3)环结构存储查询方案在最坏情况下的事件存储路径长度、事件 查询路径长度分别为D,和D,有 D.=ma(R.L-R)+(2R) (23) D=mNR,-R4日2aR (24) 而对于结构化的存储查询方案，在最坏情况下，事件存储路径长度和事件查询路径长度分别为D,和D,我 们有D:=2Ldn以及D,=2L.通常情况下，当复制节点冗余度n足够大时存在D<D,D,<D,可以看到，环结构 的存储查询方案相比结构化的存储查询方案能够有效地确保低延迟性和低能耗性 4.2聚集查询的性能 传感器网络上的聚集查询需要获取区域内部所有事件信息的聚集值，由于环结构提供了多个层次的索引 机制，因此存在多种可行的查询方案如图8所示，对于某一区域的聚集查询，存在两条路由路径：路径1为直接查 询所有相关的原始事件存储节点进行聚集，路径2为查询相关的部分聚集结果存储节点进行聚集我们分析比 较了两条路径方案的性能，设查询节点的位置半径为R,到R环的向心路由距离为Dg=R1-,到R2环的向心路 中国科学院软件研究所。hp/,j0s,org.cn
10 Journal of Software 软件学报 1 (2 4 ) d overall i i E f L Lq = = ⋅ +⋅ ∑ (20) 考虑结构化层次结构的存储机制在平均情况下的能耗开销,图 7 展示了层次结构存储机制中某一层的存 储节点部署结构.可以看到,在结构化的存储机制中,其存储节点是均匀分散在部署区域中的,因此,对不同方位 存储节点的平均存储查询路由开销是不同的.我们可以根据其距离中心位置的不同划分为多个近似的环结构, 利用公式(4)的运算结果来近似计算其存储和查询开销.假设 1−d 层的层次结构中,第 i 层存在 ki 种类型的存储 节点,每种类型存储节点存在 n 个复制节点,则存储节点间距离 2 1/( ) D L nk i i = ⋅ ,存在的环结构数目为 nr=⎡log2(n⋅ki/2)⎤,每个环的半径近似等于 0.5Di,1.5Di,…,(nr−0.5)Di,则根据式(4)的运算结果,i 层的能耗开销 Ei 可 以表示为 3 2 1 2 (( 0.5) ) 2 (1 2 ) (( 0.5) ) 3 3 r n i ii i j j D Ef q L j D = L ⎡ − ⋅ ⎤ =⋅+ ⋅ + − − ⋅ ⎢ ⎥ ⎣ ⎦ ∑ (21) 因此,平均情况下结构化层次结构的存储机制总体能耗为 3 2 11 1 2 (( 0.5) ) 2 (1 2 ) (( 0.5) ) 3 3 r d d n i overall i i i ii j j D E Ef q L j D == = L ⎡ ⎤ ⎡ − ⋅ ⎤ = =⋅ + ⋅ + − − ⋅ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎣ ⎦ ∑∑ ∑ (22) 通过分析比较上述环结构存储查询方案和基于 GHT 的结构化存储查询方案我们可以看到,环结构存储查 询方案的特点决定了其性能上的优点:(1) 环结构事件 存储时向心路由的路径可以充分共享,这使得事件存 储路由时仅通过一条向心路径(d=max(Rd−R1,R−R1, Rd−R),R 为事件节点所在半径)就可以经过多个层次环 结构更新数据,有效地降低了整体的路由能耗,而结构 化存储查询机制层次结构存储节点之间的路由不存在 共享路径,往往需要来回反复经过多个层次结构进行 更新,其节能效果是不理想的;(2) 环结构使用优化的 部署参数确定存储节点的部署位置,从理论上证明能 够充分降低存储和查询的整体路由开销,而对于结构 化的层次结构存储查询机制并未充分考虑到其优化部 署问题.如图 7 所示,对于每一层存储节点并未将所有 存储节点放置到节能效果最优化的位置上;(3) 环结构存储查询方案在最坏情况下的事件存储路径长度、事件 查询路径长度分别为 Ds 和 Dq,有 1 1 max( , ) (2 ) d s d i i D RL R R = = −+ π ∑ (23) 1 1 max( , ) 2 D RL R R qd i n ⎛ ⎞ = − + ⋅π ⎜ ⎟ ⎝ ⎠ (24) 而对于结构化的存储查询方案,在最坏情况下,事件存储路径长度和事件查询路径长度分别为 Ds ′ 和 Dq ′ ,我 们有 Ds ′ =2Ldn 以及 Dq ′ =2L.通常情况下,当复制节点冗余度 n 足够大时存在 Ds<< Ds ′ ,Dq<< Dq ′ ,可以看到,环结构 的存储查询方案相比结构化的存储查询方案能够有效地确保低延迟性和低能耗性. 4.2 聚集查询的性能 传感器网络上的聚集查询需要获取区域内部所有事件信息的聚集值,由于环结构提供了多个层次的索引 机制,因此存在多种可行的查询方案.如图 8 所示,对于某一区域的聚集查询,存在两条路由路径:路径 1 为直接查 询所有相关的原始事件存储节点进行聚集,路径 2 为查询相关的部分聚集结果存储节点进行聚集.我们分析比 较了两条路径方案的性能,设查询节点的位置半径为 R,到 R1 环的向心路由距离为 R1 D =|R1−R|,到 R2 环的向心路 Fig.7 GHT based deployment of the ith level storage 图 7 基于 GHT 的第 i 层存储节点部署 O 2L 2L