谢磊等：基于环结构的传感器网络多分辨率数据存储机制 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 事件存储和查询的路由策略