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.cn10 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