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.cn4 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 存