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
1028 Journal of Softw'ae软件学报Vol.20,No.4,April2009 4≤C214,故有B≤C214,所以，1c-(a+B)=a+B+B)-(a+B)≤C214 ▣ 根据定理1，当a+<20%时（通常用户指定的精确度在这个范围之内），总体查询误差1ct将十分接近于a+B, 其实际偏差小于1%，因此，给定用户指定的误差1Ct,可以近似地分解为簇内聚集估算误差a和簇间聚集估算误差 Ct-位.下面，我们将利用该定理的结果计算最优分簇规模， 3.2最优分簇规模的计算 第3.1节已经介绍了具有层次结构的聚集数据估算机制的原理，该估算机制依赖于在传感器网络上构建一 个基于分簇的数据收集结构，考虑这种分簇结构的规模，如何决定簇的大小以充分发挥层次结构估算机制的特 性，使网络节点总体通信能耗接近最低，便成为一个至关重要的问题.因为当分簇规模过大时，成员节点往往需 要通过较远的距离向簇头发送感知数据，消耗了过多的能量：当分簇规模过小时整个网络便退化为接近于传统 的树形路由结构，根据第22节的论述，这种结构不能高效、节能地支持估算机制.下面我们通过定理来证明：根 据基站获取的信息，可以计算出最优分簇规模，从而最小化传感器网络的总体通信能耗 定理2.基于层次结构的聚集数据估算机制，其最优分簇规模k可以通过计算获得，且有 MN EpP(dop) √2元VE.ee[P'(tct-aop)-P(aopr】+Empdons·P'tct-ap) 证明：假设当前网络中存在k个分簇，每个簇的大小基本相同，根据第2.1节给出的能耗模型，在簇内对每一 个成员节点，其能耗为 Eon-C=(IEe+lpdcn)P(a) (10) 其中，docH为成员节点到簇头节点的距离，P(a为当误差为a时成员节点向簇头更新数据的概率.对于每一个簇 头，其能耗为 am=la(g-小ra+lEu义+e+eds)P (11) 其中，ds为簇头到基站的距离，P"()为当误差为时簇头向基站更新部分聚集数据PSR的概率，根据定理1，有 压1ct-a.每个簇的能量消耗为 Enon-CH (12) k 由文献[11]我们知道，有focH的期望值为 EldcH]= 1M2 (13) πk 因此，网络中所有簇的总体能量消耗为 Eota(k,a）=kEchter 1M2 (14) -IE[(2N-k)-P(a)+k-P'(ict-EpN+P(ct-a)N.P(a) 为了获得该优化问题中Eo的最小值，根据对最优点的求解方案，我们对变量k和a求偏导数： E(k.c)=0 (15) a Eoa(k,a）=0 由此通过数值计算求出aop,从而得到最优的分簇规模kp: -M√N 8sP(ap） (16) V2元VEckeel[P'(tct-agr）-P(agpr】+EmpdioRs·P'(tct-ae） 当仅使用簇内聚集层次的估算机制，即a=1Ct,一0时， 中国科学院软件研究所。hp/,j0s,org.cn
1028 Journal of Software 软件学报 Vol.20, No.4, April 2009 2 4 /4 ≤ C ,故有 2 αβ ≤ C / 4 ,所以, 2 tct C − + = ++ − + ≤ ( ) ( ) ( ) /4 α β α β αβ α β . □ 根据定理 1,当α+β<20%时(通常用户指定的精确度在这个范围之内),总体查询误差 tct 将十分接近于α+β, 其实际偏差小于 1%,因此,给定用户指定的误差 tct,可以近似地分解为簇内聚集估算误差α和簇间聚集估算误差 tct−α.下面,我们将利用该定理的结果计算最优分簇规模. 3.2 最优分簇规模的计算 第 3.1 节已经介绍了具有层次结构的聚集数据估算机制的原理,该估算机制依赖于在传感器网络上构建一 个基于分簇的数据收集结构,考虑这种分簇结构的规模,如何决定簇的大小以充分发挥层次结构估算机制的特 性,使网络节点总体通信能耗接近最低,便成为一个至关重要的问题.因为当分簇规模过大时,成员节点往往需 要通过较远的距离向簇头发送感知数据,消耗了过多的能量;当分簇规模过小时,整个网络便退化为接近于传统 的树形路由结构,根据第 2.2 节的论述,这种结构不能高效、节能地支持估算机制.下面我们通过定理来证明:根 据基站获取的信息,可以计算出最优分簇规模,从而最小化传感器网络的总体通信能耗. 定理 2. 基于层次结构的聚集数据估算机制,其最优分簇规模 kopt 可以通过计算获得,且有: 4 ( ) 2 [ ( ) ( )] ( ) fs opt opt elec opt opt mp toBS opt M N P k E P tct P d P tct ε α α αε α = π ′ ′ −− + ⋅ − . 证明:假设当前网络中存在 k 个分簇,每个簇的大小基本相同,根据第 2.1 节给出的能耗模型,在簇内对每一 个成员节点,其能耗为 2 ( )() E lE l d P non CH elec fs toCH − = + ε α (10) 其中,dtoCH 为成员节点到簇头节点的距离,P(α)为当误差为α时成员节点向簇头更新数据的概率.对于每一个簇 头,其能耗为 4 1 () ( ) () CH elec DA elec mp toBS N N E lE P lE lE l d P k k α ε β ⎛ ⎞ = −⋅ + + + ⋅ ′ ⎜ ⎟ ⎝ ⎠ (11) 其中,dtoBS 为簇头到基站的距离,P′(β)为当误差为β时簇头向基站更新部分聚集数据 PSR 的概率,根据定理 1,有 β≈tct−α.每个簇的能量消耗为 1 cluster CH non CH CH non CH N N EE E E E k k − − ⎛ ⎞ = +− ≈ + ⎜ ⎟ ⎝ ⎠ (12) 由文献[11]我们知道,有 d2 toCH 的期望值为 2 2 1 [ ] 2 toCH M E d k = π (13) 因此,网络中所有簇的总体能量消耗为 [ ] 2 4 (, ) 1 (2 ) ( ) ( ) ( ) ( ) 2 total cluster elec DA mp toBS fs E k kE M lE N k P k P tct lE N lk d P tct l N P k α α α ε αε α = = − ⋅ +⋅ − + + − + ⋅ ′ ′ π (14) 为了获得该优化问题中 Etotal 的最小值,根据对最优点的求解方案,我们对变量 k 和α求偏导数: (, ) 0 (, ) 0 total total E k k E k α α α ⎧ ∂ = ⎪⎪∂ ⎨ ∂ ⎪ = ⎪⎩∂ (15) 由此通过数值计算求出αopt,从而得到最优的分簇规模 kopt: 4 ( ) 2 [ ( ) ( )] ( ) fs opt opt elec opt opt mp toBS opt M N P k E P tct P d P tct ε α α αε α = π ′ ′ −− + ⋅ − (16) 当仅使用簇内聚集层次的估算机制,即α=tct,β=0 时
谢磊等：基于分簇的传感器网络数据聚集估算机制 1029 MN P(tcI) (17) V2π VEe(I-P(1c）+Epd6as 证明完毕 口 根据定理2，对于刷新概率函数P(心和P"(),我们根据随机过程的原理假设其符合下面的形式： P(a)=Z·a,P'(B)=Z2·B,其中，Z为常数P,为正数对于原始感知数据估算层次的刷新概率P(a),根据文 献[l4]的论证结果，P(a)符合随机行走模型(random walk model),因而有： 1 Pa) (25 (18) 其中，心为随机行走的步长信息.P'()由于其表示簇间聚集估算的刷新概率，其结果与实际分簇规模k有关，但 可以验证：当分簇大小Nk到达一定数量时，刷新概率随k变化相对稳定，为了简化计算，我们用平均分簇规模k 来估算P'(B)的相关参数.有时，为了使运算结果更加精确，可以采用迭代的方法求取kor即采用krg为k的初 始估算值，通过多次迭代地将修正的k估算值对应的P'()代入式(16)中求得最终充分逼近k的估算值.因此， 根据以上分析，只需在传感器网络构建分簇结构之前，通过一个学习阶段(learning phase)变化相对误差，收集刷 新信息，即可估算出P()和P"()刷新概率函数中的相关参数，以指导基站对最优分簇规模的计算， 3.3分簇结构的生成与维护 分簇结构的生成和维护主要分为3个阶段：学习阶段、构建分簇阶段和维护阶段在学习阶段当所有传感 器节点都被部署在观测区域中时，每个节点周期性地获取感知数据，并向基站发送当前数据V,在基站为每一个 节点根据缓存窗口机制维护一个估算值c,同时维护误差值α，在当前数据V与估算值V℃，之差超过a指定的误 差范围时，基站为每个节点维护的刷新次数U,递增.基站在一定范围内调整α心，从而获取相应的刷新次数U,利用 计算出的平均刷新率估算出P()的参数同理，基站在一定范围内调整簇间聚集误差B,利用节点的位置分布信 息和平均分簇规模kg结合PSR的平均刷新概率估算出P'()的参数结合以上参数基站根据定理2计算出最 优分簇规模kp以及误差参数ap和Bp,发送给每个节点.在构建分簇阶段，每个节点以P=kpN的概率选择自 己成为簇头节点，并向邻居节点广播消息构建分簇，成员节点根据到候选簇头的距离参数加入相应的分簇在维 护阶段，每个节点根据获得的误差参数a和B,实现估算机制，定期地更新数据，并周期性地交替更换簇头以保 证节点的负载均衡学习阶段和构建分簇阶段往往会带来通信能量的额外开销，但可以有效地减少维护阶段的 长时间周期的数据聚集通信能耗其节能效果是显著的.分簇结构的生成算法流程如图6所示， 3.4自适应的误差分配方案 当传感器网络被部署到观测区域中后，由于地区性数据变化率存在差异，会出现某些区域感知数据变化较 快而某些区域变化较慢的现象，根据均一的误差分配机制，每个节点拥有相同的误差，这样会导致感知数据变化 较快区域的节点频繁传输数据从而过早地耗尽能量而变化较慢区域的节点则无法利用富余的能量基于上述 分析，可以考虑通过调整不同区域节点的误差，对于变化较慢区域的节点赋予较少的误差量，把更多的误差量赋 予数据变化较快区域的节点，在分布式环境中根据不同的数据变化率采取自适应的方案来分配误差通过这种 非均一的误差分配机制，可以使网络节点达到负载均衡的效果同时，通过把富余的误差量分配给变化较快区 域的节点，可以实现在不显著增加变化较慢区域节点通信能耗的同时能够有效降低这些节点的通信能耗，从而 降低传感器网络的整体能量消耗，达到高效节能的目的. 这样，结合地区数据变化率差异性，如何在分布式环境中自适应地合理分配误差量，在达到负载均衡目的同 时使网络节点总体能耗接近最低，便成为一个有待解决的问题.本文提出的自适应误差分配方案旨在解决上述 问题，我们在簇内聚集估算层次使用自适应的、非均一的误差分配方案来有效降低网络的整体通信能耗，在簇 间通信层次，由于簇头数量较少，其能耗并非占总体通信能耗的主要部分，同时，由于部分聚集结果变化相对稳 定，所以仍考虑使用均一的误差分配方案」 中国科学院软件研究所。hp/,j0s,org.cn
谢磊 等:基于分簇的传感器网络数据聚集估算机制 1029 4 ( ) 2 (1 ( )) fs opt elec mp toBS M N P tct k E P tct d ε ε = π − + (17) 证明完毕. □ 根据定理 2,对于刷新概率函数 P(α)和 P′(β),我们根据随机过程的原理假设其符合下面的形式: 1 1 ( ) p P Z α α− = ⋅ , 2 2 ( ) p P Z β β− ′ = ⋅ ,其中,Zi 为常数,pi 为正数.对于原始感知数据估算层次的刷新概率 P(α),根据文 献[14]的论证结果,P(α)符合随机行走模型(random walk model),因而有: 2 2 1 ( ) (2 ) P s α α− ≈ ⋅ ⋅ (18) 其中,s 为随机行走的步长信息.P′(β)由于其表示簇间聚集估算的刷新概率,其结果与实际分簇规模 kopt 有关,但 可以验证:当分簇大小 N/k到达一定数量时,刷新概率随 k变化相对稳定,为了简化计算,我们用平均分簇规模 kavg 来估算 P′(β)的相关参数.有时,为了使运算结果更加精确,可以采用迭代的方法求取 kopt.即采用 kavg 为 kopt 的初 始估算值,通过多次迭代地将修正的 kopt 估算值对应的 P′(β)代入式(16)中求得最终充分逼近 kopt 的估算值.因此, 根据以上分析,只需在传感器网络构建分簇结构之前,通过一个学习阶段(learning phase)变化相对误差,收集刷 新信息,即可估算出 P(α)和 P′(β)刷新概率函数中的相关参数,以指导基站对最优分簇规模的计算. 3.3 分簇结构的生成与维护 分簇结构的生成和维护主要分为 3 个阶段:学习阶段、构建分簇阶段和维护阶段.在学习阶段,当所有传感 器节点都被部署在观测区域中时,每个节点周期性地获取感知数据,并向基站发送当前数据 Vi,在基站为每一个 节点根据缓存窗口机制维护一个估算值 Vci,同时维护误差值α,在当前数据 Vi 与估算值 Vci 之差超过α指定的误 差范围时,基站为每个节点维护的刷新次数 Ui 递增.基站在一定范围内调整α,从而获取相应的刷新次数 Ui,利用 计算出的平均刷新率估算出 P(α)的参数.同理,基站在一定范围内调整簇间聚集误差β,利用节点的位置分布信 息和平均分簇规模 kavg,结合 PSR 的平均刷新概率估算出 P′(β)的参数.结合以上参数基站根据定理 2 计算出最 优分簇规模 kopt 以及误差参数αopt 和βopt,发送给每个节点.在构建分簇阶段,每个节点以 P=kopt/N 的概率选择自 己成为簇头节点,并向邻居节点广播消息构建分簇,成员节点根据到候选簇头的距离参数加入相应的分簇.在维 护阶段,每个节点根据获得的误差参数αopt 和βopt 实现估算机制,定期地更新数据,并周期性地交替更换簇头以保 证节点的负载均衡.学习阶段和构建分簇阶段往往会带来通信能量的额外开销,但可以有效地减少维护阶段的 长时间周期的数据聚集通信能耗,其节能效果是显著的.分簇结构的生成算法流程如图 6 所示. 3.4 自适应的误差分配方案 当传感器网络被部署到观测区域中后,由于地区性数据变化率存在差异,会出现某些区域感知数据变化较 快而某些区域变化较慢的现象,根据均一的误差分配机制,每个节点拥有相同的误差,这样会导致感知数据变化 较快区域的节点频繁传输数据从而过早地耗尽能量,而变化较慢区域的节点则无法利用富余的能量.基于上述 分析,可以考虑通过调整不同区域节点的误差,对于变化较慢区域的节点赋予较少的误差量,把更多的误差量赋 予数据变化较快区域的节点,在分布式环境中根据不同的数据变化率采取自适应的方案来分配误差.通过这种 非均一的误差分配机制[14],可以使网络节点达到负载均衡的效果.同时,通过把富余的误差量分配给变化较快区 域的节点,可以实现在不显著增加变化较慢区域节点通信能耗的同时,能够有效降低这些节点的通信能耗,从而 降低传感器网络的整体能量消耗,达到高效节能的目的. 这样,结合地区数据变化率差异性,如何在分布式环境中自适应地合理分配误差量,在达到负载均衡目的同 时使网络节点总体能耗接近最低,便成为一个有待解决的问题.本文提出的自适应误差分配方案旨在解决上述 问题,我们在簇内聚集估算层次使用自适应的、非均一的误差分配方案来有效降低网络的整体通信能耗,在簇 间通信层次,由于簇头数量较少,其能耗并非占总体通信能耗的主要部分,同时,由于部分聚集结果变化相对稳 定,所以仍考虑使用均一的误差分配方案
1030 Journal of Softw'ae软件学报Vol.20,No.4,April2009 Sensor Node Side: Base Station Side: while (the timer(7)for learning phase is not expired) while(the timer(7)for learning phase is not expired) VgetLocalSensorData() receive data V from each sensor node i send /to the base station if(W-Vc>ax Bwp-Bo✉lD endwhile VcF[Vex(m-1)+Villm receive from the base station "=, P=kopr/N U=U+1 generate a random number n,where 0P) Vc=[Vcix(m-1)+Vilm elect itself to be the cluster head,broadcast endif HEAD AD MSG to neighbour nodes endwhile else Calculate parameters for probability function P(a)and wait for HEAD AD MSG and join the first-heard cluster P"( head [Kopr,cop]=calculateOptimalClusterSize(P(a),P(B)) endif Send [kopr oBopl to each sensor node i Fig.6 Pseudo-Code for constructing clusters 图6分簇的构造算法伪码 对于簇内聚集估算层次非均一的误差分配方案，存在以下的误差约束，所有节点的误差均值应等于聚集结 果的误差值： Bp-Biowa= ∑Bp-Ba) (19) N, 式(19)可以进一步简化为 a= (a (20) 我们定义负荷指数来指导自适应误差分配方案的误差分配， 定义l(负荷指数burden factor).负荷指数刻画传感器节点平均每轮通信能量开销，其形式如下： B=CP(a,) (21) 其中，C,表示向族头更新数据包的能量开销，P()表示簇内聚集误差设为a,时的刷新概率，a,为节点的当前设定 误差.下面我们具体描述自适应误差分配方案. 在构建分簇步骤完成之后，每个成员节点首先向簇头发送簇内通信开销C,在簇内聚集层次每一轮，每个 成员节点产生感知数据V,成员节点根据估算机制判断是否有V-Vc(Bom,Bp)×a,如果成立，则向簇头发送数 据'，簇头递增刷新次数U,成员节点和簇头同时更新Vc,维持误差a不变；否则，成员节点无须向簇头发送数据 ',成员节点和簇头同时利用上次估算值更新V℃并缩小误差a,有：a=a×(1-),为设定的缩小比例，0<k1.每 T-1轮，成员节点需向簇头发送剩余能量值E 对于簇头节点，除了在首轮向基站节点发送簇内每轮平均通信开销Ag(C)以及根据估算机制向基站节点 更新部分聚集数据PSR外，在簇头上为每个成员节点ⅰ维护一个负荷指数B,在每T-1轮还需向基站发送簇内 平均剩余能量AgE,)和平均更新概率Ag(P),有： 1 Avg(Er)=- Er (22) ,白 Avg,(P)-N, U (23) 其中，E,和U:分别为T轮内节点i的剩余能量与刷新次数N,为簇的大小同时，簇头统计当前簇内误差之和 SUMa,作为误差调整的下界(lower bound),并发送给基站，有： 中国科学院软件研究所。hp/,j0s,org.cn
1030 Journal of Software 软件学报 Vol.20, No.4, April 2009 Fig.6 Pseudo-Code for constructing clusters 图 6 分簇的构造算法伪码 对于簇内聚集估算层次非均一的误差分配方案,存在以下的误差约束,所有节点的误差均值应等于聚集结 果的误差值: 1 1 ( ) N j up low up low i i j BB BB N α α = − ⋅= ⋅ − ⋅ ∑ (19) 式(19)可以进一步简化为 1 1 ( ) N j i i N j α α = = ⋅∑ (20) 我们定义负荷指数来指导自适应误差分配方案的误差分配. 定义 1(负荷指数 burden factor). 负荷指数刻画传感器节点平均每轮通信能量开销,其形式如下: ( ) i i i i C P B α α ⋅ = (21) 其中,Ci 表示向簇头更新数据包的能量开销,P(αi)表示簇内聚集误差设为αi 时的刷新概率,αi 为节点的当前设定 误差.下面我们具体描述自适应误差分配方案. 在构建分簇步骤完成之后,每个成员节点 i 首先向簇头发送簇内通信开销 Ci,在簇内聚集层次每一轮,每个 成员节点产生感知数据 Vi,成员节点根据估算机制判断是否有|Vi−Vci|>(Blow,Bup)×αi,如果成立,则向簇头发送数 据 Vi,簇头递增刷新次数 Ui,成员节点和簇头同时更新 Vci,维持误差αi 不变;否则,成员节点无须向簇头发送数据 Vi,成员节点和簇头同时利用上次估算值更新 Vci,并缩小误差αi,有:αi=αi×(1−θ),θ为设定的缩小比例,0α×|Bup−Blow|) Vci=[Vci×(m−1)+Vi]/m V′i=Vi Ui=Ui+1 else Vci=[Vci×(m−1)+V′i]/m endif endwhile Calculate parameters for probability function P(α) and P′(β) [kopt,αopt]=calculateOptimalClusterSize(P(α),P′(β)) Send [kopt,αopt,βopt] to each sensor node i Sensor Node Side: while (the timer(T) for learning phase is not expired) ViÅgetLocalSensorData() send Vi to the base station endwhile receive [kopt,αopt,βopt] from the base station P=kopt/N generate a random number n, where 0P) elect itself to be the cluster head, broadcast HEAD_AD_MSG to neighbour nodes else wait for HEAD_AD_MSG and join the first-heard cluster head endif
谢磊等：基于分簇的传感器网络数据聚集估算机制 1031 SUM,(a)=>(a,)=Avg(a)-N, (24) 对于基站节点，基站为每个簇维护一个负荷指数W用来刻画每个簇的总体负荷： W,= Avg(C)Avg(P)·N 25) Avg(a).Avg(E) 基站在每T轮根据W,为各簇重新分配误差区间，首先保证分配各簇的误差下界值SUM以)，对剩下的误差区间 4D根据权重按比例为每个簇j分配4d,即有： 4D=a·N-sUM,a (26) j=1 4d,= aN->SUM(a) (27) j扫 j=1 在完成分配计算后，基站将为各簇分配的误差区间d发送给相应的簇头.在每T轮，簇头根据基站分配出的误差 区间4d,在簇内为每个成员节点分配误差量簇头以每个成员节点的负荷指数B:为权重，为每个节点再次按权 重比例分配富余的误差值4%，对分配到富余误差值的成员节点i更新其误差值心： B△d B·W, Adi=N a·N->SUM,(a) 28) ∑B ∑B·W, j= 通过对每个节点以负荷指数为权重分配富余误差值的策略，使得当前簇内通信能耗较高并且误差分配量相对 较小的那些节点能够获得较大的富余误差量补给，能够有效地均衡各节点的负荷并且降低整体网络通信开销 自适应误差分配的算法流程如图7所示. 3.5自适应误差分配机制分析 第3.4节提出了自适应的误差分配方案，其目的是为了均衡各节点间的通信负载，同时有效降低整体的网 络通信能耗.下面我们来证明在簇内聚集估算层次自适应误差分配方案的节能效果是接近理论最优的 定理3.在簇内聚集估算层次自适应误差分配方案的节能效果收敛于非均一误差分配的理论最优方案。 证明：考虑在簇内聚集估算层次采用非均一的误差分配方案，如何在固定的总体误差范围内合理分配误差 以使簇内聚集层次总体通信能耗最低便成为一个优化问题」 我们使用效用函数(utility function)C(ag)来表示簇内聚集层次总体通信能耗： ca-cPa) (29) C(a)包括N-k个成员节点的通信开销，C,为节点i的通信开销，P(a)为节点i的通信概率，a,为分配给节点i 的误差量，根据式(20)可以推导出对于所有的成员节点误差，其满足约束关系： ∑a=a-N=ud--N (30) 其中，1c1-卿为簇内聚集估算分配的误差量α，在这里为常数.我们的优化问题便为如何在满足约束关系(32)的 前提下调整以最小化总体能量开销C()的数值.针对这样的优化问题，我们可以利用拉格朗日乘子法17 (Lagrange multiplier)计算最优解，存在目标函数a=C(a: fa=岁cPa) (31) 以及约束函数g(a: g(a)=∑a-(tct-)N (32) 中国科学院软件研究所。hp/,j0s,org.cn
谢磊 等:基于分簇的传感器网络数据聚集估算机制 1031 1 () ( ) () N j j i j i SUM Avg N αα α = = ∑ = ⋅ (24) 对于基站节点,基站为每个簇 j 维护一个负荷指数 Wj,用来刻画每个簇的总体负荷: () () () ( ) j j r Avg C Avg P N W Avg Avg E α ⋅ ⋅ = ⋅ (25) 基站在每 T 轮根据 Wj 为各簇重新分配误差区间,首先保证分配各簇的误差下界值 SUMj(α),对剩下的误差区间 ΔD 根据权重按比例为每个簇 j 分配Δdj,即有: 1 ( ) k j j Δα α D N SUM = =⋅−∑ (26) 1 1 1 ( ) k j j j j k k j j j j j W W d D N SUM W W ΔΔ α α = = = ⎡ ⎤ = = ⋅− ⎢ ⎥ ⎣ ⎦ ∑ ∑ ∑ (27) 在完成分配计算后,基站将为各簇分配的误差区间Δdj发送给相应的簇头.在每 T轮,簇头根据基站分配出的误差 区间Δdj,在簇内为每个成员节点分配误差量.簇头以每个成员节点的负荷指数 Bi 为权重,为每个节点再次按权 重比例分配富余的误差值Δαi,对分配到富余误差值的成员节点 i 更新其误差值αi. 1 1 11 ( ) j j k i j i ij j N N k j i ij j jj B B W d N SUM B BW Δα Δ α α = = == ⋅ ⎡ ⎤ = = ⋅− ⎢ ⎥ ⎣ ⎦ ⋅ ∑ ∑ ∑∑ (28) 通过对每个节点以负荷指数为权重分配富余误差值的策略,使得当前簇内通信能耗较高并且误差分配量相对 较小的那些节点能够获得较大的富余误差量补给,能够有效地均衡各节点的负荷并且降低整体网络通信开销. 自适应误差分配的算法流程如图 7 所示. 3.5 自适应误差分配机制分析 第 3.4 节提出了自适应的误差分配方案,其目的是为了均衡各节点间的通信负载,同时有效降低整体的网 络通信能耗.下面我们来证明在簇内聚集估算层次自适应误差分配方案的节能效果是接近理论最优的. 定理 3. 在簇内聚集估算层次自适应误差分配方案的节能效果收敛于非均一误差分配的理论最优方案. 证明:考虑在簇内聚集估算层次采用非均一的误差分配方案,如何在固定的总体误差范围内合理分配误差 以使簇内聚集层次总体通信能耗最低,便成为一个优化问题. 我们使用效用函数(utility function)C(α)来表示簇内聚集层次总体通信能耗: 1 () ( ) N k i i i C CP α α − = = ∑ (29) C(α)包括 N−k 个成员节点的通信开销,Ci 为节点 i 的通信开销,P(αi)为节点 i 的通信概率,αi 为分配给节点 i 的误差量,根据式(20)可以推导出对于所有的成员节点误差,其满足约束关系: 1 ( ) N k i i αα β N tct N − = ∑ = ⋅= − ⋅ (30) 其中,tct−β即为簇内聚集估算分配的误差量α,在这里为常数.我们的优化问题便为如何在满足约束关系(32)的 前提下调整αi 以最小化总体能量开销 C(α)的数值.针对这样的优化问题,我们可以利用拉格朗日乘子法[17] (Lagrange multiplier)计算最优解,存在目标函数 f(α)=C(α): 1 () ( ) N k i i i f CP α α − = = ∑ (31) 以及约束函数 g(α): 1 () ( ) N k i i g αα β tct N − = = ∑ − −⋅ (32)
1032 Journal of Software软件学报Vol.20,No.4,April2009 Algorithm for Cluster Head. Algorithm for Cluster Member. Algorithm for Base Station. round=0 round=0 round=0 if (round ==0) if (round==0) if(round-=O） receive C from each node,calculate send C to its cluster head receive Avg(C)from each cluster Avg(C)and send Avg(C)to base station round=round+1 round=round+1 round=round+1 endif endif endif for each round>0 for each round>0 for each round>0 VgetLocalSensorData() receive PSR from each cluster if(receive V from member node if (WV-Vc(Bio,B)xa) with approximate scheme Ve =[Vcx(m-1)+Vil/m VeF(Vex(m-1)+Vil/m if (round%T==(T-1)) VEV UFU+1 "= receive AvgEr),AvgdP),Avgda) else send Vto its cluster head from each cluster a=a4·(1-0) else endif Vc=[Vcx(m-1)+VV/m a=a(1-00 if (round%T==0) endif VcF(Vcx(m-1)+V'/m calculate W,and new allocated Ad calculate PSR,and send PSR,to the base endif for each cluster station with approximate scheme if(own%T=(T-1)》 send Ad,to each cluster head if(round%T=(T-l)》 send Er,to the cluster head endif calculate Avg(E,),Avg (P)and Avg(a) endif round=round+1 and send to base station if (round%T==0) endfor endif receive new allocated Aa if(round%T=0) a=ar+Aa receive allocated tolerance Ad,from base endif station,calculate B,and new allocated round=round+1 Aa,for each node endfor send Aa;to node i endif round=round+1 endfor Fig.7 Pseudo-Code for adaptive tolerance allocate algorithm 图7自适应误差分配算法伪码 构造辅助函数F(a)=f(a)-1·g(a),为某一常数，则根据拉格朗日乘子法有 -F(α)=0，我们得到： C· a aa P(a)=元(N-k) (33) 根据随机行走的模型，对P(a)有：P(a) 2:可a,根据上式我们得到下面的约束关系 1 CP(a)=D. (34) 其中，D1为常数，D=-12.由负荷指数B,的定义，存在下面的等式关系： B-C:P(@)=D. (35) 上式表明，当所有节点的负荷指数趋向于一个相等的常数时，总体通信能耗最低，而根据我们的自适应误差分配 方案，通过在数据变化快，即P()高的节点上逐步提高误差%的取值，以及在数据变化慢，即P(%)低的节点上逐 步降低误差4取值的方式，最终能够使所有节点的负荷指数B,收敛于一个相等的数值，使得整体能耗最低.口 由定理3我们得知，通过自适应误差分配方案，其节能效果最终可以收敛于非均一误差分配的理论最优方 案其收敛速度受到自适应调整的时间间隔T的影响，考虑到调整的时间间隔T越小，其收敛速度越快，但同时带 中国科学院软件研究所。hp/,j0s,org.cn
1032 Journal of Software 软件学报 Vol.20, No.4, April 2009 Fig.7 Pseudo-Code for adaptive tolerance allocate algorithm 图 7 自适应误差分配算法伪码 构造辅助函数 Ff g () () () α = −⋅ αλ α ,λ为某一常数,则根据拉格朗日乘子法有 F() 0 α α ∂ = ∂ ,我们得到: 1 () ( ) N k i i i i C P Nk α λ α − = ∂ ⋅ =⋅ − ∂ ∑ (33) 根据随机行走的模型,对 P(αi)有: 2 2 1 ( ) (2 ) P i i s α α− ≈ ⋅ ⋅ ,根据上式我们得到下面的约束关系: ( ) i i i C P D α λ α ⋅ = ⋅ (34) 其中, D ⋅λ 为常数,D=−1/2.由负荷指数 Bi 的定义,存在下面的等式关系: ( ) i i i i C P B D α λ α ⋅ = = ⋅ (35) 上式表明,当所有节点的负荷指数趋向于一个相等的常数时,总体通信能耗最低,而根据我们的自适应误差分配 方案,通过在数据变化快,即 P(αi)高的节点上逐步提高误差αi 的取值,以及在数据变化慢,即 P(αi)低的节点上逐 步降低误差αi 取值的方式,最终能够使所有节点的负荷指数 Bi 收敛于一个相等的数值,使得整体能耗最低. □ 由定理 3 我们得知,通过自适应误差分配方案,其节能效果最终可以收敛于非均一误差分配的理论最优方 案.其收敛速度受到自适应调整的时间间隔 T 的影响,考虑到调整的时间间隔 T 越小,其收敛速度越快,但同时带 Algorithm for Base Station. round=0 if (round==0) receive Avg(Ci) from each cluster round=round+1 endif for each round>0 receive PSRj from each cluster j with approximate scheme if (round%T==(T−1)) receive Avgj(Er),Avgj(P),Avgj(α) from each cluster j endif if (round%T==0) calculate Wi and new allocated Δdj for each cluster j send Δdj to each cluster head j endif round=round+1 endfor Algorithm for Cluster Member. round=0 if (round==0) send Ci to its cluster head round=round+1 endif for each round>0 ViÅgetLocalSensorData() if (|Vi−Vci|>(Blow,Bup)×αi) Vci=[Vci×(m−1)+Vi]/m V′i=Vi send Vi to its cluster head else (1 ) αi i = α θ ⋅ − Vci=[Vci×(m−1)+V ′i]/m endif if (round%T==(T−1)) send Eri to the cluster head endif if (round%T==0) receive new allocated Δαi αi=αi+Δαi endif round=round+1 endfor Algorithm for Cluster Head. round=0 if (round ==0) receive Ci from each node, calculate Avg(Ci) and send Avg(Ci) to base station round=round+1 endif for each round>0 if (receive Vi from member node i) Vc =[Vci×(m−1)+Vi]/m V′i=Vi Ui=Ui+1 else (1 ) αi i = ⋅− α θ Vci=[Vci×(m−1)+V′i]/m endif calculate PSRj and send PSRj to the base station with approximate scheme if (round%T==(T−1)) calculate Avgj(Er),Avgj(P) and Avgj(α） and send to base station endif if (round%T==0) receive allocated tolerance Δdj from base station, calculate Bi and new allocated Δαi for each node send Δαi to node i endif round=round+1 endfor