谢磊等：基于环结构的传感器网络多分辨率数据存储机制 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