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 种情况:多环之 内、多环之间以及多环之外,由此综合考虑向心路由能耗的期望值有