计算机科学与技术（参考文献）基于分簇的传感器网络数据聚集估算机制

ISSN 1000-9825,CODEN RUXUEW E-mail:jos@iscas.ac.cn Journal of Sofnware,Vol.20,No.4,April 2009,pp.1023-1037 http://www.jos.org.cn doi:10.3724/SP.J.1001.2009.03282 Tel/Fax:+86-10-62562563 by Institute ofSofare,the Chinese Academy of Sciences.All rights reserved. 基于分簇的传感器网络数据聚集估算机制” 谢磊2，陈力军124，陈道蓄2，谢立口 (南京大学计算机软件新技术国家重点实验室，江苏南京210093) 2(南京大学/香港理工大学无线与移动传感器网络联合实验室，江苏南京210093) Clustering-Based Approximate Scheme for Data Aggregation over Sensor Networks XIE Lei2,CHEN Li-Jun +CHEN Dao-Xu'2,XIE Li2 (State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210093,China) (NJU-POLYU Cooperative Laboratory for Wireless Sensor Network,Nanjing University,Nanjing 210093,China) +Corresponding author:E-mail:chelj@nju.edu.cn,http://dislab.nju.edu.cn Xie L,Chen LJ,Chen DX,Xie L.Clustering-Based approximate scheme for data aggregation over sensor networks.Journal of Sofnware,2009,20(4):1023-1037.http://www.jos.org.cn/1000-9825/3282.htm Abstract:In this paper,a hierarchical clustering-based approximate scheme for in-network aggregation over sensor networks called CASA(clustering-based approximate scheme for data aggregation)is proposed,CASA achieves a good performance in terms of lifetime by minimizing overall energy consumption for communications and balancing energy load among all nodes,while maintaining user-specified quality of data requirement.CASA adopts an optimal parameter for the cluster size,which can well handle the hierarchical approximate work for in-network aggregation with the minimized communication cost.Furthermore,an adaptive tolerance-reallocating scheme is leveraged to further reduce the overall communication cost and maintain a load balance according to various data change rates over deployment regions.Experimental results indicate that significant benefits can be achieved through this CASA approximate scheme. Key words:sensor network;data aggregation;approximation;cluster 摘要：提出一种基于簇结构的传感器网络数据聚集估算机制CASA(clustering-based approximate scheme for data aggregation),在保证用户对数据精确度需求的前提下，CASA通过最小化网络通信开销以及协调节，点间的负载 均衡，有效地提高了估算机制的节能性能.CASA采用最优的分簇规模参数，在基于分簇的网内聚集估算架构中能够 最小化网络节点的总体通信开销此外，CASA考虑到部署区域城感知数据变化率的差异性，采用自适应的误差分配方 案来进一步降低网络节点的通信开销，维护节点间的负载均衡.模拟实验结果表明，CASA估算机制能够显著地提升 传感器网络网内数据聚集机制的节能性能同时保证聚集数据的精确程度」 关键词：传感器网络：数据聚集：估算：分簇 中图法分类号：TP393 文献标识码：A Supported by the National Natural Science Foundation of China under Grant Nos.60573I32,60873026,60s73106(国家自然科学 基金，the National High-Tech Research and Development Plan of China under Grant No.2006AA01ZI99(国家高技术研究发展计划 (863)片，the National Basic Research Program of China under Grant No..2006CB303000(国家重点基础研究发展计划(973) Received 2007-09-24:Accepted 2008-02-21 中国科学院软件研究所。hp/,j0s,org.cn

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn Journal of Software, Vol.20, No.4, April 2009, pp.1023−1037 http://www.jos.org.cn doi: 10.3724/SP.J.1001.2009.03282 Tel/Fax: +86-10-62562563 © by Institute of Software, the Chinese Academy of Sciences. All rights reserved. 基于分簇的传感器网络数据聚集估算机制∗ 谢 磊 1,2, 陈力军 1,2+, 陈道蓄 1,2, 谢 立 1,2 1 (南京大学 计算机软件新技术国家重点实验室,江苏 南京 210093) 2 (南京大学/香港理工大学 无线与移动传感器网络联合实验室,江苏 南京 210093) Clustering-Based Approximate Scheme for Data Aggregation over Sensor Networks XIE Lei1,2, CHEN Li-Jun1,2+, CHEN Dao-Xu1,2, XIE Li1,2 1 (State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China) 2 (NJU-POLYU Cooperative Laboratory for Wireless Sensor Network, Nanjing University, Nanjing 210093, China) + Corresponding author: E-mail: chelj@nju.edu.cn, http://dislab.nju.edu.cn Xie L, Chen LJ, Chen DX, Xie L. Clustering-Based approximate scheme for data aggregation over sensor networks. Journal of Software, 2009,20(4):1023−1037. http://www.jos.org.cn/1000-9825/3282.htm Abstract: In this paper, a hierarchical clustering-based approximate scheme for in-network aggregation over sensor networks called CASA (clustering-based approximate scheme for data aggregation) is proposed, CASA achieves a good performance in terms of lifetime by minimizing overall energy consumption for communications and balancing energy load among all nodes, while maintaining user-specified quality of data requirement. CASA adopts an optimal parameter for the cluster size, which can well handle the hierarchical approximate work for in-network aggregation with the minimized communication cost. Furthermore, an adaptive tolerance-reallocating scheme is leveraged to further reduce the overall communication cost and maintain a load balance according to various data change rates over deployment regions. Experimental results indicate that significant benefits can be achieved through this CASA approximate scheme. Key words: sensor network; data aggregation; approximation; cluster 摘 要: 提出一种基于簇结构的传感器网络数据聚集估算机制 CASA(clustering-based approximate scheme for data aggregation).在保证用户对数据精确度需求的前提下,CASA 通过最小化网络通信开销以及协调节点间的负载 均衡,有效地提高了估算机制的节能性能.CASA 采用最优的分簇规模参数,在基于分簇的网内聚集估算架构中能够 最小化网络节点的总体通信开销.此外,CASA 考虑到部署区域感知数据变化率的差异性,采用自适应的误差分配方 案来进一步降低网络节点的通信开销,维护节点间的负载均衡.模拟实验结果表明,CASA 估算机制能够显著地提升 传感器网络网内数据聚集机制的节能性能,同时保证聚集数据的精确程度. 关键词: 传感器网络;数据聚集;估算;分簇 中图法分类号: TP393 文献标识码: A ∗ Supported by the National Natural Science Foundation of China under Grant Nos.60573132, 60873026, 60573106 (国家自然科学 基金); the National High-Tech Research and Development Plan of China under Grant No.2006AA01Z199 (国家高技术研究发展计划 (863)); the National Basic Research Program of China under Grant No.2006CB303000 (国家重点基础研究发展计划(973)) Received 2007-09-24; Accepted 2008-02-21

1024 Journal of Software软件学报Vol.20,No.4,April2009 随着传感器技术、嵌入式计算技术以及低功耗无线通信技术的发展，大量具备感知、计算和通信能力的传 感器节点共同组织成大规模的无线传感器网络，已经广泛出现在多种相关的应用领域中这些传感器节点口能 够收集不同的感知数据，例如光照和温度同时能够对这些数据进行一些更为复杂的操作，如缓存、聚集和过滤 等这种由大量传感器节点组成的网络往往在通信能力、计算能力尤其是能量消耗上存在严重的资源限制，因 此，设计一种高效、节能的数据收集策略对大规模部署的传感器网络便至为重要考虑到在传感器网络中节点 的通信能量开销远大于节点计算能量开销，因此，通过合理利用节点的本地计算能力去降低网络的通信开销能 够有效地节省大量能量开销.近年来，基于数据库的处理方案2，被引入到传感器网络的研究与实现中，以有效 地利用网内处理(in network processing)的特性来降低传感器网络的能量消耗.在对传感器网络的数据进行收集 和处理时，将整个传感器网络看成一个大型的分布式数据库，采用类似于SQL(structured query language)的说明 性查询语言对传感器网络进行查询的方式来获取感知信息通过这种方式，传感器网络中每个节点可以根据用 户需求，有效地对相关数据在网内进行过滤、聚集、缓存等操作，最后传至基站终端用户 网内聚集机制(in-network aggregation)4,作为一种高效、节能的数据聚集方式，能够充分利用传感器节点 的本地处理能力，在将原始数据发送到基站之前，在中间节点就进行数据的聚集合并.目前对于传感器网络数据 收集估算机制的研究6-已经得到越来越广泛的关注，通过合理权衡获取数据的精确度和能量消耗，在保证获 取的数据在指定的精确度范围内这一前提下，能够有效地降低网络的能量开销.在本文中，我们针对网内聚集机 制提出了一种基于分簇的估算机制CASA(clustering-based approximate scheme for data aggregation),不同于以 前的研究工作，我们提出了一种基于层次结构的估算机制，能够根据部署的环境信息计算获取最优的分簇规模 参数，以最小化网络节点的总体通信开销.此外，针对部署区域感知数据变化率的差异性，CASA采用自适应的误 差分配方案进一步降低网络节点的通信开销，维护节点间的负载均衡，并通过理论证明和模拟实验证实，自适应 的误差分配结果收敛于理论最优方案. 本文第1节介绍相关工作第2节对本文的动因以及采用的系统模型进行描述第3节给出CASA的详细 设计第4节进行模拟实验，对CASA性能进行分析最后总结全文 1相关工作 对于网内聚集工作的研究，Krishnamacharil等人对传感器网络中数据聚集机制的节能效果做出了全面分 析.Madden等人提出了TAG(tiny aggregation)l,一种基于管道(pipeline)的网内数据聚集方案，文中对不同的聚 集函数的属性进行了详细的分类，并利用管道技术对网内数据聚集执行有效的调度，以保证子节点能够在指定 时间段内将数据聚集并传输给父节点.Demers等人提出了一种基于推拉(push and pull)技术的聚集节点选择方 案和聚集路由树的构建机制对于网内聚集机制的路由构建，相比于传统树形结构的路由机制，分簇路由具有 拓扑管理方便、能量利用高效、数据融合简单等优点，成为当前重点研究的路由技术.Heinzelman等人提出一 种基于簇的数据收集协议LEACH(low energy adaptive clustering hierarchy),其基本思想是构建一个两跳的分 簇路由结构，每个簇内成员节点向簇头发送感知数据，由簇头将处理后的数据直接发送给基站.Lu等人提出了 一种分布式的传感器网络数据收集和聚合协议DEEG(distributed energy-efficient data gathering)),与LEACH 有所不同，簇头之间以多跳方式将收集到的数据发送到指定簇头节点，然后通过该节点将整个网络收集的数据 发送到基站.在文献[13]中，沈波等人对目前无线传感器网络簇算法进行了详细的分析和比较 对于数据收集估算机制的研究.当前的研究工作主要集中于权衡数据精确度和能量消耗的关系，在满足用 户对数据精确度需求的前提下，采用估算机制允许适量误差以有效降低网络的整体能量开销.Sharaf等人提出 了一套基于树形路由结构的网内聚集估算机制TiNA向，利用误差率TCT(temporal coherency tolerence)对聚集 数据的精确度进行控制.Deshpande等人提出了一种基于统计模型的传感器网络估算机制例]，在基站通过机器学 习的方法维护一个数据模型，用户通过查询的方式与该模型交互获取估算结果，该模型按照特定需求定期更新 通过这种方式显著减少了网络传输量，从而达到节能的效果.Tulone等人继而提出了PAQ(probabilistic adaptable query system)估算机制9，通过在节点本地维护一个轻量级的自回归模型(autoregressive model)来达到基于时间 中国科学院软件研究所。hp/,j0s,org.cn

1024 Journal of Software 软件学报 Vol.20, No.4, April 2009 随着传感器技术、嵌入式计算技术以及低功耗无线通信技术的发展,大量具备感知、计算和通信能力的传 感器节点共同组织成大规模的无线传感器网络,已经广泛出现在多种相关的应用领域中.这些传感器节点[1]能 够收集不同的感知数据,例如光照和温度,同时能够对这些数据进行一些更为复杂的操作,如缓存、聚集和过滤 等.这种由大量传感器节点组成的网络往往在通信能力、计算能力尤其是能量消耗上存在严重的资源限制,因 此,设计一种高效、节能的数据收集策略对大规模部署的传感器网络便至为重要.考虑到在传感器网络中节点 的通信能量开销远大于节点计算能量开销,因此,通过合理利用节点的本地计算能力去降低网络的通信开销能 够有效地节省大量能量开销.近年来,基于数据库的处理方案[2,3]被引入到传感器网络的研究与实现中,以有效 地利用网内处理(in network processing)的特性来降低传感器网络的能量消耗.在对传感器网络的数据进行收集 和处理时,将整个传感器网络看成一个大型的分布式数据库,采用类似于 SQL(structured query language)的说明 性查询语言对传感器网络进行查询的方式来获取感知信息.通过这种方式,传感器网络中每个节点可以根据用 户需求,有效地对相关数据在网内进行过滤、聚集、缓存等操作,最后传至基站终端用户. 网内聚集机制(in-network aggregation)[4,5]作为一种高效、节能的数据聚集方式,能够充分利用传感器节点 的本地处理能力,在将原始数据发送到基站之前,在中间节点就进行数据的聚集合并.目前对于传感器网络数据 收集估算机制的研究[6−9]已经得到越来越广泛的关注,通过合理权衡获取数据的精确度和能量消耗,在保证获 取的数据在指定的精确度范围内这一前提下,能够有效地降低网络的能量开销.在本文中,我们针对网内聚集机 制提出了一种基于分簇的估算机制 CASA(clustering-based approximate scheme for data aggregation),不同于以 前的研究工作,我们提出了一种基于层次结构的估算机制,能够根据部署的环境信息计算获取最优的分簇规模 参数,以最小化网络节点的总体通信开销.此外,针对部署区域感知数据变化率的差异性,CASA 采用自适应的误 差分配方案进一步降低网络节点的通信开销,维护节点间的负载均衡,并通过理论证明和模拟实验证实,自适应 的误差分配结果收敛于理论最优方案. 本文第 1 节介绍相关工作.第 2 节对本文的动因以及采用的系统模型进行描述.第 3 节给出 CASA 的详细 设计.第 4 节进行模拟实验,对 CASA 性能进行分析.最后总结全文. 1 相关工作 对于网内聚集工作的研究,Krishnamachari[4]等人对传感器网络中数据聚集机制的节能效果做出了全面分 析.Madden 等人提出了 TAG(tiny aggregation)[5],一种基于管道(pipeline)的网内数据聚集方案,文中对不同的聚 集函数的属性进行了详细的分类,并利用管道技术对网内数据聚集执行有效的调度,以保证子节点能够在指定 时间段内将数据聚集并传输给父节点.Demers 等人提出了一种基于推拉(push and pull)技术的聚集节点选择方 案和聚集路由树的构建机制[10].对于网内聚集机制的路由构建,相比于传统树形结构的路由机制,分簇路由具有 拓扑管理方便、能量利用高效、数据融合简单等优点,成为当前重点研究的路由技术.Heinzelman 等人提出一 种基于簇的数据收集协议 LEACH(low energy adaptive clustering hierarchy)[11],其基本思想是构建一个两跳的分 簇路由结构,每个簇内成员节点向簇头发送感知数据,由簇头将处理后的数据直接发送给基站.Liu 等人提出了 一种分布式的传感器网络数据收集和聚合协议 DEEG(distributed energy-efficient data gathering)[12],与 LEACH 有所不同,簇头之间以多跳方式将收集到的数据发送到指定簇头节点,然后通过该节点将整个网络收集的数据 发送到基站.在文献[13]中,沈波等人对目前无线传感器网络簇算法进行了详细的分析和比较. 对于数据收集估算机制的研究,当前的研究工作主要集中于权衡数据精确度和能量消耗的关系,在满足用 户对数据精确度需求的前提下,采用估算机制允许适量误差以有效降低网络的整体能量开销.Sharaf 等人提出 了一套基于树形路由结构的网内聚集估算机制 TiNA[6],利用误差率 TCT(temporal coherency tolerence)对聚集 数据的精确度进行控制.Deshpande 等人提出了一种基于统计模型的传感器网络估算机制[8],在基站通过机器学 习的方法维护一个数据模型,用户通过查询的方式与该模型交互获取估算结果,该模型按照特定需求定期更新, 通过这种方式显著减少了网络传输量,从而达到节能的效果.Tulone 等人继而提出了 PAQ(probabilistic adaptable query system)估算机制[9],通过在节点本地维护一个轻量级的自回归模型(autoregressive model)来达到基于时间

谢磊等：基于分簇的传感器网络数据聚集估算机制 1025 序列进行数据估算的目的.Hellerstein等人提出了一套基于小波压缩技术的聚集数据估算机制.Olston等人针 对分布式数据源的聚集查询提出了基于缓存的估算机制)，能够动态地自适应调整各数据源的精度需求以最 小化数据更新的开销.Goel等人提出了PREMON(prediction-based monitoring)I,利用感知数据的时空相关性 来对移动目标的属性进行估算.上述研究工作大都从设计性能高效的估算模型入手来解决传感器网络的节能 问题，不同于以前的研究工作，本文主要结合传感器网络多跳路由结构特性，从设计良好的支持估算机制的网络 架构入手，有效地解决传感器网络的节能问题，本文是我们在前期研究工作的基础上进一步深入和扩展的研 究成果」 2系统模型与问题描述 2.1系统模型 本文假设N个传感器节点随机、均匀分布在一个M×M的二维正方形区域A内，并假设该传感器网络具 有如下性质： ·传感器网络为静态网络，即节点部署后不再移动 ·基站部署在区域A以外的一个固定位置，且基站是唯一的 ·节点可以获知其位置信息节点依靠GS、有向天线或定位算法等辅助设施或算法获取位置信息 ·节点的无线发射功率可控即节点可以根据接收者的距离来调整其发射功率 对于节点通信能量消耗的计算，我们使用文献[I1门中LEACH提出的能耗模型，该能耗模型给出一个阙值 derossover,当发送节点与接收节点的距离小于derossorer时，发送方发送数据的能量损耗与距离的平方成正比，否则 与距离的4次方成正比.上述的两种能量衰减模型分别称为自由空间(free space))模型和多路衰减(multipath fading)模型.因此，每发送I比特的数据到d距离处的节点，本地节点需要能耗： En(l,d)=Er-cke()+Eamp(,d)= IEkedd (1) IEcke+lepd',d≥d 每接收I比特的数据，本地节点需要能耗： Ek(1)=ERs-clec(1)=lEdee (2) 在上面的公式中，E。c表示无线收发电路所消耗的能量.s和p分别表示自由空间模型和多路衰减模型中 放大器消耗的能量，其大小取决于发送节点与接收节点间的距离以及可接受的位错误率」 对于网内聚集模型，结合估算机制，我们采用了文献6中TNA提出的指定精确度的聚集查询方式，如图1 所示，查询语句的前3项SELECT..FROM..WHERE与通常的SQL语句相同，指定参与聚集查询的节点范围 EPOCH DURATION i用来指定连续查询中聚集结果收集的时间间隔VALUES WITHIN1c1用来指定聚集查询 的误差范围.对于误差1c的定义，我们使用图2来说明通常聚集查询对应的感知属性，如平均温度AVG(temp), 往往在一个固定的范围之内(Bo,Bp)变化，ZeroBound则表示该属性的一个理论最低值，基站和每个传感器节点 会存储每个感知属性的常规变化范围.我们使用1来表示对于这个变化范围的相对误差，则整个聚集结果的绝 对误差Tol即为Tol=(Bo,Bp)×1ct.例如：对于某地平均温度AVG(temp),其常规变化范围为(-I0C,40C),其理论 最低值为-273℃.若设定1C=10%,则绝对误差T6=[40C-(-10C)】×10%=5C.对于其他聚集函数，如 SUM(attribute),由于可以获知参与聚集计算的节点数count,,SUMattribute)=AVG(attribute)×count,.其估算处理方 案可以按照AWVG(attribute)进行处理，此时，整个聚集结果的绝对误差Tol=(Bomw-B)x1 ctxcount. 中国科学院软件研究所。hp/,j0s,org.cn

谢磊 等:基于分簇的传感器网络数据聚集估算机制 1025 序列进行数据估算的目的.Hellerstein 等人提出了一套基于小波压缩技术的聚集数据估算机制[7].Olston 等人针 对分布式数据源的聚集查询提出了基于缓存的估算机制[14],能够动态地自适应调整各数据源的精度需求以最 小化数据更新的开销.Goel 等人提出了 PREMON(prediction-based monitoring)[15],利用感知数据的时空相关性 来对移动目标的属性进行估算.上述研究工作大都从设计性能高效的估算模型入手来解决传感器网络的节能 问题,不同于以前的研究工作,本文主要结合传感器网络多跳路由结构特性,从设计良好的支持估算机制的网络 架构入手,有效地解决传感器网络的节能问题,本文是我们在前期研究工作[16]的基础上进一步深入和扩展的研 究成果. 2 系统模型与问题描述 2.1 系统模型 本文假设 N 个传感器节点随机、均匀分布在一个 M × M 的二维正方形区域 A 内,并假设该传感器网络具 有如下性质: • 传感器网络为静态网络,即节点部署后不再移动. • 基站部署在区域 A 以外的一个固定位置,且基站是唯一的. • 节点可以获知其位置信息.节点依靠 GPS、有向天线或定位算法等辅助设施或算法获取位置信息. • 节点的无线发射功率可控,即节点可以根据接收者的距离来调整其发射功率. 对于节点通信能量消耗的计算,我们使用文献[11]中 LEACH 提出的能耗模型,该能耗模型给出一个阈值 dcrossover,当发送节点与接收节点的距离小于 dcrossover 时,发送方发送数据的能量损耗与距离的平方成正比,否则 与距离的 4 次方成正比.上述的两种能量衰减模型分别称为自由空间(free space)模型和多路衰减(multipath fading)模型.因此,每发送 l 比特的数据到 d 距离处的节点,本地节点需要能耗: 2 4 , (, ) () (, ) , elec f s crossover Tx Tx elec Tx amp elec mp crossover lE l d d d E ld E l E ld lE l d d d ε ε − − ⎧ + < ⎪ =+ = ⎨ ⎪ + ≥ ⎩ (1) 每接收 l 比特的数据,本地节点需要能耗: () () E l E l lE Rx Rx elec elec = − = (2) 在上面的公式中,Eelec 表示无线收发电路所消耗的能量.εfs 和εmp 分别表示自由空间模型和多路衰减模型中 放大器消耗的能量,其大小取决于发送节点与接收节点间的距离以及可接受的位错误率. 对于网内聚集模型,结合估算机制,我们采用了文献[6]中 TiNA 提出的指定精确度的聚集查询方式,如图 1 所示,查询语句的前 3 项 SELECT…FROM…WHERE 与通常的 SQL 语句相同,指定参与聚集查询的节点范围. EPOCH DURATION i 用来指定连续查询中聚集结果收集的时间间隔.VALUES WITHIN tct 用来指定聚集查询 的误差范围.对于误差 tct 的定义,我们使用图 2 来说明.通常聚集查询对应的感知属性,如平均温度 AVG(temp), 往往在一个固定的范围之内(Blow,Bup)变化,ZeroBound则表示该属性的一个理论最低值,基站和每个传感器节点 会存储每个感知属性的常规变化范围.我们使用 tct 来表示对于这个变化范围的相对误差,则整个聚集结果的绝 对误差 Tol 即为 Tol=(Blow,Bup)×tct.例如:对于某地平均温度 AVG(temp),其常规变化范围为(−10°C, 40°C),其理论 最低值为 −273°C. 若设定 tct=10%, 则绝对误差 Tol=[40°C−(−10°C)]×10%=5°C. 对于其他聚集函数 , 如 SUM(attribute),由于可以获知参与聚集计算的节点数 count,SUM(attribute)=AVG(attribute)×count,其估算处理方 案可以按照 AVG(attribute)进行处理,此时,整个聚集结果的绝对误差 Tol=(Blow−Bup)×tct×count

1026 Journal of Software软件学报Vol.20,No.4,April2009 pper boud B】 SELECT AggregateFunction (attribules) FROM sensors s T=(B。-Bd WHERE s.loc in Range R EPOCH DURATION/ VALUES WITHIN Ic e und Fig.1 Aggregate query with precision specification Fig.2 Definition of tolerance tct 图1指定精确度的聚集查询 图2误差tct定义 2.2问题描述与分析 在传感器网络上实现数据收集的估算机制的主要策略是：在路由结构中的父子节点上都维护一个估算值 Vpp,当子节点产生新的感知数据V时，便计算是否有V-Vp(Bow,Bp)x1c,如果成立，则发送消息更新数据V, 否则，父节点利用本地的估算值'，来估算'，通过这种方式可以有效地避免过多的通信开销，从而达到节能的 目的为了在传感器网络多跳路由结构上实现上述网内聚集的估算机制，需要考虑合理的路由结构来支持聚集 估算机制的实现如图3所示，传统的树形路由方案对于数据聚集的估算存在这样的问题：由于估算机制只是针 对于原始感知数据进行估算操作，对于传统的树形路由结构，仅有少部分分布在边界的叶节点能够产生原始感 知数据，而大部分中间节点通过聚集产生部分聚集数据PSR(partial state record,不能使用估算机制来减少网络 传输量.因此传统的树形路由方案并不能充分利用网内聚集的估算机制来达到高效节能的目的.如图4所示，基 于分簇的路由结构由于感知数据仅在少数簇头节点进行聚集，对于簇内大部分的节点都产生原始的感知数据， 因此能够有效支持和实现估算机制的节能效果 Fig.3 Tree-Based architecture Fig.4 Cluster-Based architecture 图3树形路由方案 图4分簇路由方案 根据以上分析，在基于分簇的路由结构下如何有效地建立层次结构的估算机制，如何决定分簇的大小以使 网络节点总体通信能耗接近最低，以及考虑到地区数据变化率的差异，如何在分布式环境中自适应地合理分配 误差区间，在达到负载均衡目的的同时使网络节点总体能耗接近最低，便成为迫切需要解决的一些问题，本文提 出的CASA估算机制旨在解决上述问题，在下一节中我们对CASA数据聚集估算机制进行具体的描述. 3CASA数据聚集估算机制 3.1估算机制的架构 对于节点间估算值的计算，文献[6-9]提出了多种构建估算模型的方案，本文中我们考虑采用基于缓存窗口 的估算模型：在路由结构中的父子节点之间，双方节点都维护一个缓存窗口(window),窗口大小设为m,用来缓存 最近m轮之内的数据，则估算值V℃取值最近m轮数据的平均数，计算如下： e=2 (3) 中国科学院软件研究所。hp/,j0s,org.cn

1026 Journal of Software 软件学报 Vol.20, No.4, April 2009 Fig.1 Aggregate query with precision specification Fig.2 Definition of tolerance tct 图 1 指定精确度的聚集查询 图 2 误差 tct 定义 2.2 问题描述与分析 在传感器网络上实现数据收集的估算机制的主要策略是:在路由结构中的父子节点上都维护一个估算值 Vappr,当子节点产生新的感知数据 V 时,便计算是否有|V−Vappr|>(Blow,Bup)×tct,如果成立,则发送消息更新数据 V, 否则,父节点利用本地的估算值 Vappr 来估算 V,通过这种方式可以有效地避免过多的通信开销,从而达到节能的 目的.为了在传感器网络多跳路由结构上实现上述网内聚集的估算机制,需要考虑合理的路由结构来支持聚集 估算机制的实现.如图 3 所示,传统的树形路由方案对于数据聚集的估算存在这样的问题:由于估算机制只是针 对于原始感知数据进行估算操作,对于传统的树形路由结构,仅有少部分分布在边界的叶节点能够产生原始感 知数据,而大部分中间节点通过聚集产生部分聚集数据 PSR(partial state record),不能使用估算机制来减少网络 传输量.因此传统的树形路由方案并不能充分利用网内聚集的估算机制来达到高效节能的目的.如图 4 所示,基 于分簇的路由结构由于感知数据仅在少数簇头节点进行聚集,对于簇内大部分的节点都产生原始的感知数据, 因此能够有效支持和实现估算机制的节能效果. Fig.3 Tree-Based architecture Fig.4 Cluster-Based architecture 图 3 树形路由方案 图 4 分簇路由方案 根据以上分析,在基于分簇的路由结构下如何有效地建立层次结构的估算机制,如何决定分簇的大小以使 网络节点总体通信能耗接近最低,以及考虑到地区数据变化率的差异,如何在分布式环境中自适应地合理分配 误差区间,在达到负载均衡目的的同时使网络节点总体能耗接近最低,便成为迫切需要解决的一些问题,本文提 出的 CASA 估算机制旨在解决上述问题,在下一节中我们对 CASA 数据聚集估算机制进行具体的描述. 3 CASA 数据聚集估算机制 3.1 估算机制的架构 对于节点间估算值的计算,文献[6−9]提出了多种构建估算模型的方案,本文中我们考虑采用基于缓存窗口 的估算模型:在路由结构中的父子节点之间,双方节点都维护一个缓存窗口(window),窗口大小设为 m,用来缓存 最近 m 轮之内的数据,则估算值 Vc 取值最近 m 轮数据的平均数,计算如下: 1 1 m i i Vc V m = = ∑ (3) Lower bound Upper bound Zero bound T B B tct up low = ( − )⋅ Bup Blow SELECT AggregateFunction (attributes) FROM sensors s WHERE s.loc in Range R EPOCH DURATION i VALUES WITHIN tct BaseStation BaseStation

谢磊等：基于分簇的传感器网络数据聚集估算机制 1027 当初始时窗口中缓存数据少于m个缓存数据时，估算值'℃则取窗口中所有数据的平均值.这种基于缓存窗 口的估算模型相比于文献[6-9]中提出的估算模型更为简单，有效降低了节点的计算复杂度.同时通过窗口机制 维护估算数据的稳定，减少了感知数据剧烈动荡或接收到错误数据(outlier data)对估算数据产生的影响.基于缓 存窗口估算模型，我们结合分簇的路由结构建立一套具有层次结构的估算机制，如图5所示. Base PSR level CHI CH2 CHA Tolerance=- Raw senso data level Tolerance=a Fig.5 Cluster-Based hierarchical approximate architecture 图5基于分簇的层次估算架构 图5所示的基于分簇的层次估算架构针对网内聚集的实现，分为两个处理层次：第1个层次在每个簇内部 实现，簇头C西对簇内N个成员中每个节点产生的感知数据'，进行聚集，获得部分聚集数据PSR,第2个层次 在所有k个簇头和基站之间实现，在基站对每个簇头产生的PSR进行聚集： (4) 1=1 AggValue=∑PSR (5) j=l 因此，CASA估算机制针对这两个聚集层次，分别提出了两个层次上的估算方案：在簇内聚集层次，对簇内原 始感知数据进行估算，维护估算误差工，在簇间聚集层次，对部分聚集数据PSR进行估算，维护估算误差B.在每个 层次内均一的误差分配机制下，存在下面的误差分配关系： ,-a小a l8,-8a=1立 (6) a-a=安A,BD (7 这种具有层次结构的聚集数据估算机制，分别在原始感知数据和部分聚集数据层次进行估算操作：在原始 感知数据层次进行估算操作，有效地降低了大量簇内成员节点向簇头节点传输数据的能量开销：在部分聚集数 据层次进行估算操作，由于簇头节点相对基站的距离往往远大于簇内通信的距离，其通信开销相对簇内传输要 高很多，通过估算机制降低了簇头与基站通信的概率，从而达到高效节能的目的.CASA估算机制不仅适用于类 似于LEACH的两跳分簇路由结构，也适用于类似于DEEG的簇头之间以多跳方式传输数据的分簇路由结 构，其差别仅在于对前者簇间聚集层次估算适用于所有簇头节点，对后者簇间聚集层次估算适用于簇头节点组 成多跳路由的所有叶节点，因此，对于不同分簇路由结构具有良好的可扩展性.下文中为了便于讨论CASA估算 机制的性质，以LEACH分簇路由结构为模型进行分析，但其相关性质同样适用于其他分簇路由结构. 下面我们通过定理证明，这种层次结构的聚集数据估算机制的总体误差1t接近于两层误差之和a+B. 定理1，当a+B≤C(C为常数)时，有总体误差1c1≈(a+B),且有tc1-(a+B)≤C14. 证明：根据相对误差a,的定义，有0<<1,0<k1,原始感知数据估算层次的误差范围是(1-a,1+,部分聚集 数据估算层次的误差范围是(1-B1+),因此，最终聚集结果误差范围是(1-a1-,(1+)(1+),因而有： (1+a)1+B)=1+(a+B)+ap (8) (1-a1-B)=1-(a+B)+ap (9) 最终聚集结果的误差1c1=max(a+B-aB,a+B+aB)=a+B+aB,当a+B≤C时，存在aB≤(a+B)/ 中国科学院软件研究所。hp/,j0s,org.cn

谢磊 等:基于分簇的传感器网络数据聚集估算机制 1027 当初始时窗口中缓存数据少于m个缓存数据时,估算值Vc则取窗口中所有数据的平均值.这种基于缓存窗 口的估算模型相比于文献[6−9]中提出的估算模型更为简单,有效降低了节点的计算复杂度.同时,通过窗口机制 维护估算数据的稳定,减少了感知数据剧烈动荡或接收到错误数据(outlier data)对估算数据产生的影响.基于缓 存窗口估算模型,我们结合分簇的路由结构建立一套具有层次结构的估算机制,如图 5 所示. Fig.5 Cluster-Based hierarchical approximate architecture 图 5 基于分簇的层次估算架构 图 5 所示的基于分簇的层次估算架构针对网内聚集的实现,分为两个处理层次:第 1 个层次在每个簇内部 实现,簇头 CHj 对簇内 Nj 个成员中每个节点产生的感知数据 Vi 进行聚集,获得部分聚集数据 PSRj,第 2 个层次 在所有 k 个簇头和基站之间实现,在基站对每个簇头产生的 PSR 进行聚集: 1 N j j i i PSR V= = ∑ (4) 1 k j j AggValue PSR = = ∑ (5) 因此,CASA 估算机制针对这两个聚集层次,分别提出了两个层次上的估算方案:在簇内聚集层次,对簇内原 始感知数据进行估算,维护估算误差α;在簇间聚集层次,对部分聚集数据 PSR 进行估算,维护估算误差β.在每个 层次内均一的误差分配机制下,存在下面的误差分配关系: 1 1 ( ) N j up low up low i j BB BB N α α = − ⋅= ⋅ − ⋅ ∑ (6) 1 1 ( ) k up low up low j BB BB k β β = − ⋅=⋅ − ⋅ ∑ (7) 这种具有层次结构的聚集数据估算机制,分别在原始感知数据和部分聚集数据层次进行估算操作:在原始 感知数据层次进行估算操作,有效地降低了大量簇内成员节点向簇头节点传输数据的能量开销;在部分聚集数 据层次进行估算操作,由于簇头节点相对基站的距离往往远大于簇内通信的距离,其通信开销相对簇内传输要 高很多,通过估算机制降低了簇头与基站通信的概率,从而达到高效节能的目的.CASA 估算机制不仅适用于类 似于 LEACH[11]的两跳分簇路由结构,也适用于类似于 DEEG[12]的簇头之间以多跳方式传输数据的分簇路由结 构,其差别仅在于对前者簇间聚集层次估算适用于所有簇头节点,对后者簇间聚集层次估算适用于簇头节点组 成多跳路由的所有叶节点,因此,对于不同分簇路由结构具有良好的可扩展性.下文中为了便于讨论 CASA 估算 机制的性质,以 LEACH 分簇路由结构为模型进行分析,但其相关性质同样适用于其他分簇路由结构. 下面我们通过定理证明,这种层次结构的聚集数据估算机制的总体误差 tct 接近于两层误差之和α+β. 定理 1. 当α + ≤ β C (C 为常数)时,有总体误差 tct ≈ ( ), α + β 且有 2 tct C −+ ≤ ( ) /4 α β . 证明:根据相对误差α,β的定义,有 0<α<1,0<β<1,原始感知数据估算层次的误差范围是(1−α,1+α),部分聚集 数据估算层次的误差范围是(1−β,1+β),因此,最终聚集结果误差范围是((1−α)(1−β),(1+α)(1+β)),因而有: (1 )(1 ) 1 ( ) + + =+ + + α β α β αβ (8) (1 )(1 ) 1 ( ) − − =− + + α β α β αβ (9) 最终聚集结果的误差 tct = +− ++ =++ max( , ) α β αβ α β αβ α β αβ ,当 α + β ≤ C 时,存在 2 αβ α β ≤ + ( )/ Base station ... Raw sensor data level PSR level ... ... Tolerance= Tolerance= α β CH1 CH2 CHk