（通信与信息系统专业论文）无线传感器网络中数据聚合策略研究.pdf

北京邮电大学硕士研究生学位论文 无线传感器网络中数据聚合策略研究 k - 一 北京邮电大学硕士研究生学位论文 无线传感器网络中数据聚合策略研究 独创性( 或创新性) 声明 川| | | | i | | | l | | | i i i | l | 1 1 | | l i | l l i f l 川 17 5 9 9 9 3 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：j 罐五象蜜一 日期：j 墟尘_ l 习 一 if 。 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位 本人签名： 导师签名： 适用本授权书。 日期：塑：之：丝 日期： 盈2 ：i 羔肇 三! 苎塑皇大学硕士研究生学位论文无线传感器网络中数据聚合策略研究 o _ ，- 北京邮电大学硕士研究生学位论文无线传感器网络中数据聚合策略研究 无线传感器网络中数据聚合策略研究 摘要 无线传感器网络综合了传感器技术、嵌入式计算技术、无线通信 技术、分布式信息处理技术等，是信息感知领域的一场革命。在传感 器网络中，单个节点由于自身因素及环境影响，无法保证数据的精确 性；数目众多、布撒密集的大量节点，由于采样数据之间具有一定程 度的信息冗余，将所有的采样数据全部进行传输势必造成网络资源的 极大浪费。通过数据聚合技术，将处理后的信息而不是原始数据报告 给终端用户，既可以节省节点能量，还可以获得更准确的信息，有利 于提高数据收集效率。论文围绕数据聚合技术展开了深入研究，主要 工作包括： ( 1 ) 针对数据聚合技术进行深入调研，分别从数据聚合点的选 择、数据聚合时机的选择和数据聚合处理算法等方面分析总结了当前 国内外的数据聚合技术。 ( 2 ) 基于分簇网络结构，从无线传感器网络中的数据冗余处理 角度出发，提出一套较为完整的数据聚合策略。该策略以网络中数据 流向为主线，逐步剖析原始数据采集量化形式、特征属性提取形式。 然后根据数据分类结果，对同类型的多数据源提出了基于数据相关度 的聚合判定依据，对不同类型的多数据源提出了基于关联分析的聚合 判定依据，并分别列举了典型的数据聚合方法。 ( 3 ) 为验证聚合策略的可行性和有效性，论文分别针对标量和 j 北京邮电大学硕士研究生学位论文 无线传感器网络中数据聚合策略研究 量 标 术 飞 处 网 数 a 北京邮电大学硕士研究生学位论文 无线传感器网络中数据聚合策略研究 d a t aa g g r e g a n o ns t r a t e g yr e s e a r c h i n 啪l e sss e n s o rn e t w o r k s a bs t r a c t w i r e l e s ss e n s o rn e t w o r k si n t e g r a t e ds e n s o rt e c h n o l o g y , e m b e d d e d c o m p u t i n gt e c h n o l o g y , w i r e l e s s c o m m u n i c a t i o n t e c h n o l o g y a n d d i s t r i b u t e di n f o r m a t i o np r o c e s s i n gt e c h n o l o g yi tw a sar e v o l u t i o ni nt h e f i e l do fi n f o r m a t i o ns e n s i n g as i n g l en o d ec o u l d n tg u a r a n t e et h ed a t a a c c u r a c yb e c a u s eo f i t sf a c t o r sa n de n v i r o n m e n t a li m p a c t f o rn u m e r o u s a n dd e n s en o d e s ，t r a n s m i t t i n ga l lt h es e n s o r yd a t aw o u l dc a u s eag r e a t w a s t eo fn e t w o r kr e s o u r c e sd u et oac e r t a i nd e g r e eo fi n f o r m a t i o n r e d u n d a n c yb e t w e e nt h es a m p l e dd a t a a c c o r d i n gt o d a t aa g g r e g a t i o n t e c h n o l o g y , t r a n s m i t t i n gp r o c e s s e dd a t an o tr a wd a t aw o u l de f f e c t i v e l y s a v ee n e r g ya n dn e t w o r kr e s o u r c e s t h ep a p e rc a r r i e do u ti n d e p t h r e s e a r c ho nd a t aa g g r e g a t i o nt e c h n i q u e s ，t h em a i nc o n t r i b u t i o n si n c l u d e ： f i r s t l y , t h ep a p e rd e s c r i b e dt h er e s e a r c ha th o m ea n da b r o a db a s e d o nd e e p l ys u r v e y , i n c l u d i n gh o wt os e l e c tt h ed a t aa g g r e g a t i o np o s i t i o n ， h o wt os e l e c tt h ed a t aa g g r e g a t i o nt i m ea n dt h et y p i c a la g g r e g a t i o n a l g o r i t h m s e c o n d l y , t h ep a p e rp r o p o s e dak i n do fd a t aa g g r e g a t i o ns t r a t e g y r e s u l ti n d i c a t e dt h a td a t aa g g r e g a t i o nt e c h n o l o g yc o u l ds a v et h en e t w o r k b a n d w i d t hb u ta tt i m e d e l a yc o s t t h i s s c h e m ew a ss u i t a b l ef o r a p p l i c a t i o ni nw h i c h t i m ed e l a yw a sn o ts t r i c t l yr e q u i r e d b a s e do nt h e i m p l e m e n t a t i o n o ft h es p e c i f i cd a t a a g g r e g a t i o n s c h e m e ，t h ep a p e rf u r t h e rm i n e dt h et y p i c a lw i r e l e s ss e n s o rn e t w o r k a p p l i c a t i o n 北京邮电大学硕士研究生学位论文无线传感器网络中数据聚合策略研究 k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k s ，a g g r e g a t i o ns t r a t e g y , t i n y o s ， s y s t e mi n t e g r a t i o n v 北京邮电大学硕士研究生学位论文 无线传感器网络中数据聚合策略研 、 一 ， 北京邮电大学硕士研究生学位论文 无线传感器网络中数据聚合策略研究 目录 第一章绪论l 1 1 无线传感器网络概述1 1 1 1 无线传感器网络简介1 1 1 2 无线传感器节点构成和网络协议栈。1 1 1 3 无线传感器网络特点和关键技术3 1 2 数据聚合技术的研究目的与意义。4 1 2 1 数据聚合技术的引入4 1 2 2 数据聚合和数据融合的区别5 1 2 3 数据聚合技术的研究意义5 1 3 本文的主要工作与章节安排5 第二章数据聚合关键技术7 2 1 典型网络结构与路由协议7 2 1 1 典型网络结构。7 2 1 2 典型分簇路由协议。8 2 2 数据聚合点的选择1 0 2 2 1 路由显式建立数据聚合结构1 0 2 2 2 路由不显式建立数据聚合结构。1 0 2 3 数据聚合时机的确定1 1 2 3 1 周期性数据回传中数据聚合时机的确定1 1 2 3 2 事件触发类数据回传中聚合时机的确定1 2 2 4 数据聚合处理算法1 2 2 4 1 基于数据顺序的聚合方式1 3 2 4 2 基于管道的聚合方式1 4 2 4 3 自适应矢量量化压缩方式1 4 2 4 4 分布式信源编码压缩方式l5 2 5 小结1 6 第三章w s n 中数据聚合策略研究1 7 3 1 数据聚合网络结构。1 7 3 2 数据聚合策略研究1 9 3 2 1 原始数据采集2 0 3 2 2 特征属性提取2 0 3 2 3 基于数据相关度的数据聚合2 1 3 2 4 基于关联规则的数据聚合2 2 3 3 小结2 3 第四章基于t i n y o s 平台的标量数据聚合2 5 4 1 硬件实体描述2 5 4 2t i n y o s 平台简介2 6 4 2 1t i n y o s 组件模型与n e s c 语言2 7 4 2 2 消息通信模型2 7 4 2 3t o s s i m 仿真环境2 8 北京邮电大学硕士研究生学位论文 无线传感器网络中数据聚合策略研究 4 2 4 程序调试方法2 8 4 3 标量数据聚合方案详细设计2 9 4 3 1 网络结构2 9 4 3 2 节点系统组成3 0 4 3 3 节点软件模块3 l 4 3 4 节点工作流程3 2 4 3 5 系统功能测试3 5 4 3 6 网络性能测试。3 9 4 4d 、结4 l 第五章基于l i n u x 平台的图像数据聚合4 3 5 1 系统集成主要技术简介4 3 5 1 1l i n u x 操作系统4 3 5 1 2g s t r e a m e r 多媒体架构4 4 5 1 3 图像拼接技术4 5 5 2 图像数据聚合方案详细设计4 6 5 2 1 网络拓扑结构4 6 5 2 2 节点系统组成4 7 5 2 3 系统流程设计4 8 5 2 4 实例测试。4 8 5 3 小结。4 9 第六章数据聚合应用部署5 1 6 1 数据筛选或简单运算的数据聚合模式5 1 6 2 报头压缩的数据聚合模式5 2 6 3 关联分析的数据聚合模式5 2 6 4 混合聚合模式5 3 6 5 j 、结5 4 第七章总结与展望5 5 参考文献5 7 致谢5 9 攻读硕士学位期间发表的学术论文目录。6 0 、 北京邮电大学硕士研究生学位论文 无线传感器网络中数据聚合策略研究 1 1 无线传感器网络概述 1 1 1 无线传感器网络简介 第一章绪论 近年来，随着微机电系统技术、无线通信技术和电子技术的发展，由低成本、 低功耗、多功能、体积小、可进行短距离通信的传感器构建网络的技术得到越来 越多的关注。这些传感器节点集成了信息感知、数据处理和无线通信等功能，大 量节点利用无线通信功能组成一个自组织网络，通过协同工作，共同完成特定的 应用任务，由此构成的信息采集网络被称为无线传感器网络( w i r e l e s ss e n s o r n e t w o r k s ，简称w s n ) 1 1 。 目前，对无线传感器网络的研究与开发是信息科技领域的一个热点。国际上 许多著名的大学和公司纷纷从不同的层次、角度对传感器网络进行了研究和开 发。美国政府和国外各科研机构都投入巨资，设立启动了多项关于w s n 的计划， 包括p i c or a d i o ，w i n s ， s m a r td u s t ，l x a m p s 等。中国政府对无线传感器网 络技术的研究也十分重视，国内许多大学和科研机构都开展了无线传感器网络的 项目和研究工作并取得了一定的成果。 由于无线传感器网络可以通过随机布撒大量廉价的节点，并在无人监管的环 境中进行有效的数据采集传输，因此在军事、环境、医疗、家庭等领域具有广阔 的应用前景。在军事领域，传感器网络主要应用于战场监测、目标识别与跟踪等 方面；在民用领域，传感器网络可用于交通管理、工业生产自动化、生态环境监 测、住宅安全监测等方面。 1 1 2 无线传感器节点构成和网络协议栈 传感器节点主要由微处理器、无线通信模块、电源和各种传感器组成，图1 1 为一个典型w s n 节点的结构图。各种传感器被放置在传感器板上，负责采集监 测区域内的信息；处理器和无线芯片放在控制板上，处理器控制整个传感器节点， 存储和处理本身采集的数据，有时还要处理其他节点发来的数据；无线通信芯片 北京邮电大学硕士研究生学位论文无线传感器网络中数据聚合策略研究 负责与汇聚节点和普通节点的通信，完成控制信息交换和数据传输；电源为传感 器节点提供运行所需的能量，通常采用小型的电池。 图1 - 1 传感器节点结构图 无线传感器网络节点的协议栈如图1 2 ，包括应用层、传输层、网络层、数 据链路层以及物理层，能量管理平面、移动管理平面以及任务管理平面。 图1 - 2 无线传感器网络协议构成 其中能量管理平面、移动管理平面、任务管理平面贯穿于协议栈的各个层次， 协议栈中各层的功能如下： 物理层：负责数据的调制、发送与接收，该层的设计将直接影响到电路的复 杂度和能耗，研究目标是设计低成本、低功耗、小体积的传感器节点。物理层协 议研究涉及传输采用的传输媒体、频段选择以及调制方式。目前采用的媒体主要 有：无线电、红外线、光波等。其中无线电传输是目前的主流传输方式。 北京邮电大学硕士研究生学位论文无线传感器网络中数据聚合策略研究 数据链路层：负责数据成帧、帧检测、媒体访问和差错控制，主要侧重于研 究媒体访问控制子层( m a c ) 。w s n 的m a c 层主要目标是使节点公平有效地共 享无线信道，最大可能的降低冲突。采用的信道访问方式可以分为三类：固定分 配方式，如t d m a ，f d m a 等；随机竞争方式，如c s m a ；混合方式。 网络层：主要负责路由生成与路由选择，对数据进行路由。 传输层：在应用层需要时负责进行数据流量的控制，当系统需要通过接入 i n t e r n e t 或者其它外部网络时，该层显得非常重要。 应用层：依赖于不同的感测任务，不同类型的应用软件可以在应用层上使用。 1 1 3 无线传感器网络特点和关键技术 与传统的有线网络和a d h o c 网络相比，无线传感器网络具有以下特点： ( 1 ) 无线传感器网络的规模大，通常包含成千上万的节点，同时节点的密 度也很大。节点通常布撒在恶劣环境下，由于节点易失效以及感测不精确，因此 一般都进行密集布置。 ( 2 ) 无线传感器网络节点通常是一次部署，独立工作，可维护性很低。无 线传感器网络的节点一般都通过飞行器撒播、人工埋置和火箭弹射等方式布置在 人类无法接近或者由于某种用途而不能接近的地区，如敌军基地，因此相对于普 通的有线网络和其它形式的无线网络而言，具有部署方便、迅速和成本低的优点。 由于其执行任务的环境往往无法或难于接近，使得对节点进行定期检测、充电等 维护工作无法进行。 ( 3 ) 节点自身携带的能量有限，节点的计算能力、存储能力也有限。传感 器网络的能量有限包含两方面的含义，首先是指节点能量储备低，由于能量一般 由电池供应，携带能量较低，另一层含义是能源一般无法进行补充。 ( 4 ) 无线传感器网络的拓扑结构体现出时变性，但是这种变化不同于a d h o c 网络中由于节点的移动性引起的，而是由于节点能量耗尽引起的节点失效。 ( 5 ) 无线传感器网络功能上实现的是传感器到数据处理中心的数据采集， 不同于传统网络中数据从一个节点到另一个节点的传送，传感器网络一般以某个 参数属性值来传送数据，路由协议需要解决多到一的数据流和- - n 多的控制流。 由于无线传感器网络存在以上的一些特点，因此引起人们对于以下多个关键 技术的研究： ( 1 ) 网络协议 传感器网络协议负责使各个独立的节点形成一个多跳的数据传输网络，目前 研究的重点是网络层协议和数据链路层协议。 ( 2 ) 网络拓扑控制 3 北京邮电大学硕士研究生学位论文 无线传感器网络中数据聚合策略研究 对于无线自组织的传感器网络而言，通过拓扑控制能够自动生成良好的网络 拓扑结构，提高路由协议和m a c 协议的效率，可为数据聚合、时间同步、目标 定位等奠定基础，有利于节省节点的能量来延长网络的生存期。 ( 3 ) 网络安全 无线传感器网络作为任务型的网络，不仅要进行数据的传输，而且要进行数 据采集和聚合，任务间的协同控制等。如何保证任务执行的机密性、数据产生的 可靠性、数据聚合的高效性以及数据传输的安全性，就成为无线传感器网络安全 问题需要全面考虑的内容。 ( 4 ) 数据聚合 无线传感器网络中节点密集部署，导致节点采样数据之间存在很大的相似 性，存在一定程度的数据冗余，因此在从各个传感器节点收集数据的过程中，需 要通过数据聚合技术，减少网络中传输的数据量，提高信息的准确度。 1 2 数据聚合技术的研究目的与意义 1 2 1 数据聚合技术的引入 数量众多的传感器节点在无线传感器网络中产生了大量的传感数据，需要在 网内进行处理以避免原始传感数据的传输，减少数据收集中参与通信的数据量， 从而节省传输耗能与存储开销。一般来说，传感器节点的耗能主要分为四部分【2 】： ( 1 ) 产生传感数据需要的传感耗能； ( 2 ) 数据处理耗能； ( 3 )数据传输耗能； ( 4 ) 空闲时侦听无线信道的耗能。 有研究表吲3 1 ，对一般的无线传感器网络来说，传感器节点的大部分能量消 耗在无线通信模块。传感器节点传送数据远比执行计算耗能，将l b i t 数据传送 1 0 0 米消耗的能量大约相当于执行3 0 0 0 条计算指令需要的能量。因此，若能利 用节点的计算能力进行网内数据处理，减少参与通信的数据量，则数据收集的效 率将随之大大提高。从目前国内外的研究情况来看，无线传感器网络中网内处理 技术主要包含数据聚合技术和数据融合技术。 4 飞 广 北京邮电大学硕士研究生学位论文 无线传感器网络中数据聚合策略研究 1 2 2 数据聚合和数据融合的区别 数据聚合与数据融合技术有所区别。数据融合【4 】是利用计算机技术将来自多 个传感器或多源的观测信息进行分析、综合处理，从而得出决策和估计任务所需 的信息的处理过程。其目标是基于各传感器检测信息，通过对信息的优化组合来 导出更多的有效信息，给决策和评估提供参考依据。 而数据聚合，目前并没有明确的定义，论文中数据聚合技术是指节点对采集 或者接收到的多个数据进行聚集处理，其目的主要是去除数据冗余，有效减少网 络中传输的数据量，提高信息收集效率。 1 2 3 数据聚合技术的研究意义 由于无线传感器网络是面向应用的，以数据为中心的网络，通过数据聚合技 术，实现节点间的协作，将处理后的信息而不是原始的采集数据报告给终端用户， 具有十分重要的研究意义。 首先，数据聚合技术可以节省节点能量。传感器节点的覆盖区域是相互重叠 的，数据聚合可以去掉冗余数据，进而省去传送多余数据的能量。 其次，通过数据聚合可以获得更准确的信息。仅仅收集少数几个分散的传感 器节点的数据较难确保信息的正确性，需要通过对监测同一对象的多个传感器所 采集的数据进行综合，来有效地提高所获得信息的精确度和可信度。 再次，数据聚合技术有利于提高数据收集效率。数据聚合减少了需要传输的 数据量，减少了数据分组的个数，从而减少了传输中的冲突现象，提高了无线信 道利用率。 1 3 本文的主要工作与章节安排 在无线传感器网络中，针对数据聚合技术的研究具有十分重要的意义。论文 从无线传感器网络中的数据冗余处理角度出发，研究网内数据聚合技术，提出了 一种较为完整的数据聚合策略。该策略不仅考虑了节点的本地冗余信息处理，同 时针对网络中不同的感知数据源，考虑数据源之间的相似或关联程度，给出对应 的聚合处理方案，使网络资源得到更合理更有效的利用。 本论文的主要工作有以下几点： ( 1 ) 针对数据聚合技术进行深入调研，分别从数据聚合点的选择、数据聚 合时机的选择和数据聚合处理算法等方面阐述当前国内外的数据聚合技术。 5 北京邮电大学硕士研究生学位论文 无线传感器网络中数据聚合策略研究 ( 2 ) 基于分簇网络结构，从无线传感器网络中的数据冗余处理角度出发， 提出能够缓解网络负担的通用数据聚合策略。该策略以网路中数据流向为主线， 逐步分析原始数据采集量化形式、特征属性提取形式，然后依据数据属性进行分 类。根据分类结果，对于同类数据源提出基于数据相关度的聚合判定依据；对于 不同类型多数据源提出基于关联分析的聚合判定依据。 ( 3 ) 为验证聚合策略的有效性和可行性，论文分别给出基于t i n y o s 系统的 标量数据聚合实现方案和基于l i n u x 系统的图像数据聚合方案。 对于标量数据，借助t i n y o s 平台通过n e s c 语言编写标量数据聚合算法，用 t o s s i m 模拟节点的手段，实现网络中标量数据冗余处理。对于需要进行简单运 算的数据源，实现标量数据的最大值、最小值、均值等聚合处理；对于数据分组 部分重叠的数据源，实现标量数据的数据报文拆分合并聚合处理；对于符合关联 规则的多个数据源，实现标量数据的关联分析聚合。除此之外，论文还通过分析 比较聚合前后网络的整体性能，来验证数据聚合的价值。 对于图像数据，基于l i n u x 平台，通过集成g s t r e a m e r 多媒体架构、图像拼 接处理算法和通信协议栈，将具有一定相关度的两幅图像进行拼接处理。 ( 4 ) 根据文中提到的数据聚合策略，结合特定的应用场景，指出其在数据 处理过程中能够采用的数据聚合方法。 论文章节安排如下： 第一章，介绍了无线传感器网络的基本概念、网络特点、关键技术等，从而 引入针对数据聚合技术的研究，并阐述了数据聚合技术的研究意义； 第二章，主要调研数据聚合关键技术，分别从数据聚合点的选择、数据聚合 时机的选择、数据聚合处理算法等方面展开论述； 第三章，在充分调研的基础上，以分簇网络结构为基础，提出通用数据聚合 策略，给出抽象数据聚合模型； 第四章，参照数据聚合策略，给出标量数据聚合实现方案，并对聚合前后网 络性能进行对比分析； 第五章，参照数据聚合策略，给出图像数据聚合实现方案，并对聚合处理技 术进行分析评价； 第六章，参考聚合策略，挖掘适用于特定数据聚合技术的典型应用。 第七章，对全文进行总结，并对未来的研究工作进行展望。 6 北京邮电大学硕士研究生学位论文无线传感器网络中数据聚合策略研究 第二章数据聚合关键技术 无线传感器网络中的数据聚合，必须以无线传感器网络的特点为背景，需建 立在具体的无线传感器网络结构基础之上，在调研数据聚合关键技术时，需要先 分析总结无线传感器网络的网络结构。 本章先介绍无线传感器网络的典型网络结构和路由协议，再介绍无线传感器 网络中数据聚合关键技术，主要涉及数据聚合点的选择、数据聚合时机的选择、 数据聚合处理等方面的相关技术问题【5 j 。 2 1 典型网络结构与路由协议 2 1 1 典型网络结构 一般来说，无线传感器网络结构可分为：星型、簇型和树型结构 6 1 ，如图2 1 所示。 囊)i 艮) 图2 - 1无线传感器典型网络结构 ( 1 ) 星型 星型网络中传感器节点直接将采集数据送到s i n k 节点，如图2 1 ( a ) 所示。但 因电池容量有限，传感器的通信距离不能太长，因此这种结构不适于大规模的传 感器网络，只能作为小规模传感器网络的一种组网方式，或者是簇内通信的一种 方式。 ( 2 ) 树型 7 北京邮电大学硕士研究生学位论文 无线传感器网络中数据聚合策略研究 如图2 1 ( c ) 所示，树型网络中的节点即作为传感器，感知并上报数据，同时 作为中继器，转发其他节点的信息。在无线传感器网络中，树型结构的多跳传输 方式也有广泛的应用，主要是由于射频传输所需的能量与传输距离的n ( 2 删 次方成正比，短距离多跳传输比长距离直达传输更节省能量。 树型结构虽然灵活并且功耗较低，但同样存在规模问题，只能用于中等规模 的传感器网络中。原因是，网络内所有传感器的感知数据都要通过s i n k 附近的 传感器节点中继，才能将信息转发给s i n k 节点。当网络规模很大、数据很多时， s i n k 节点附近的传感器节点会很快因能量耗尽而无法工作，最终导致网络无法连 通，信息无法到达s i i l k 。 ( 3 ) 簇型 在大规模的传感器网络中，可以通过基于簇的多跳网络结构解决平面a dh o e 网络的规模问题。在这种网络结构中，如图2 1 ( b ) 所示，众多的传感器被分成“簇”， 每个簇可通过协商选出一个簇首，每个传感器只把信息送到其所在簇的簇首，簇 首再把信息送到s i n k 。每个簇内，可以采用直通方式或平面a dh o c 方式建立传 感器与簇首的连接。图2 1 ( b ) 中，只展示了一层的簇结构。实际上，对于更大规 模的网络，可以采用多层分簇策略，低一级的簇首再聚类，并与高一级的簇首通 信。 基于分簇的网络结构中，簇首不仅完成数据中继的任务，还可以完成本地的 数据分类和数据聚合，从而减少传至s i n k 的数据量，降低传输能耗。鉴于分簇 结构的这种特性，论文中将以分簇网络结构为基础，研究大规模网络下的数据聚 合技术。 但分簇结构本身也存在不足之处，其主要不足是簇首成了系统的瓶颈，因此， 如何分簇和轮选簇首是这种组网方式面临的问题，这就涉及到网络层中的路由技 术。下面将介绍无线传感器网络中典型的分簇路由协议。 2 1 2 典型分簇路由协议 典型的基于分簇的路由有l e a c h ，h e e d 协议等，使用分簇的方式使得数 据聚合的地位突显出来。每个簇首在收到本簇内成员的数据后进行聚合处理，并 将结果发送给s i n k 节点。 ( 1 ) l e a c h 协议 l e a c h 协议【7 】是一种基于聚类的网络分层路由协议。协议将所有节点分为 若干簇，每个簇选举一个簇首，簇首还可以组成更高层次的簇。簇首接收本簇中 节点发送的数据，并向s i n k 节点发送数据。由于向s i n k 节点发送数据要消耗很 大的电能，每隔一段时间需要重新选举簇首，以保证功耗在所有节点的平均分配。 8 北京邮电大学硕士研究生学位论文无线传感器网络中数据聚合策略研究 l e a c h 协议分为两个阶段操作，即分簇阶段和数据传输阶段。为了使能耗 最小化，数据传输阶段持续的时间比分簇阶段长。分簇阶段和数据传输阶段所持 续的时间总和称为一轮。 在分簇阶段，l e a c h 协议随机选择一个传感器节点作为簇首节点，随机性 确保簇首与s i n k 之间数据传输的高能耗成本均匀地分摊到所有传感器节点。在 簇首节点选定后，该簇首节点对网络中所有节点进行广播，广播数据包含有该节 点成为簇首节点的信息。一旦传感器节点收到广播数据包，根据接收到的各个簇 首节点广播信号强度，该节点选择信号强度最大的簇首节点加入，向其发送成为 其成员的数据包。 簇形成后，簇首节点采用t d m a 策略分配信道使用权给簇内节点。一旦处 于数据传输阶段，簇首节点开始接收簇内各节点采集的数据，然后将数据传输给 s i n k 节点。在数据传输阶段持续了一段时间后，网络又进入了另一次的分簇阶段。 l e a c h 协议的缺点：由于网内所有节点必须能够与s i n k 直接通信，并且每 个节点都具备支持不同m a c 协议计算能力，因此该协议不适合在大规模的无线 传感器网络中应用。 ( 2 ) h e e d 协议 o s s a m ay o u n i s 等人提出了h e e d ( h y b r i de n e r g ye f f i c i e n td i s t r i b u t e d c l u s t 甜n g ) 协谢8 1 ，是l e a c h 基础上的改进协议。 在h e e d 协议中，簇首的选择主要依据主次两个参数。主参数依赖于剩余能 量，用于随机选取候选簇首集合，而最终该节点是否一定能成为簇首则取决于剩 余能量是否比周围节点多；次参数依赖于簇内通信代价，用于确定落在多个簇范 围内的节点最终属于哪个簇。h e e d 协议的这种簇首选取方法更加合理，使拥有 较多剩余能量的节点成为簇首的概率更大，整个网络的工作寿命也更长，更好的 解决了能耗均匀分担的问题。 为了克服节点通信能力的问题，h e e d 协议能让簇首收集到的数据以相互接 力的方式路由到s i n k 。这样，簇首与s i n k 之间就不必要直接通信，而可以通过多 跳中继的方式传输数据，显著扩大了网络规模，有效解决了网络规模受限的问题， 从而得以应用在大规模网络中。论文后面在对标量数据聚合设计实现方案时，就 采用了h e e d 分簇路由协议。 在确定了网络基本结构和路由协议之后，可以此为基础，进一步调研国内外 数据聚合的关键技术，挖掘可供借鉴和启发的思想和方法，以促进下一步工作。 纵观众多文献，针对数据聚合技术的研究最终可分为三个大类：数据聚合点的选 9 北京邮电大学硕士研究生学位论文无线传感器网络中数据聚合策略研究 择、数据聚合时机的选择、数据聚合处理算法等。下面详细介绍目前的研究成果。 2 2 数据聚合点的选择 聚合点的选择与网络层的路由协议关系密切，需要依靠路由协议建立的路由 回传路径，并且使用路由结构中的某些节点作为数据聚合点。通常情况下，根据 路由生成阶段是否将聚合因素考虑在内，可将路由分为不显式建立数据聚合结构 和显式建立数据聚合结构两种。 2 2 1 路由显式建立数据聚合结构 文献【9 】中提到一种显式建立数据聚合结构的路由算法，其主要思想是：将聚 合代价作为路由选择时的考虑因素，先根据聚合代价判断在中间节点是否进行数 据聚合，然后将整个网络拓扑划分为聚合子图和非聚合子图，聚合子图采用最小 生成树路由方法，非聚合子图采用最短路径树路由方法，最终实现数据收集有效 性，兼顾整个网络生命周期最大化。 对于周期性数据采集等具有固定流量业务模型的应用，一般适合采用显式建 立聚合结构的数据聚合技术。但显式建立聚合结构的路由也会引入一些问题，比 如路由的控制更加复杂，相应的控制开销也增大，实现起来亦比较困难，因而应 用相对较少，只处于理论研究阶段。 2 2 2 路由不显式建立数据聚合结构 论文上一节中提到的l e a c h 和h e e d 协议，都属于路由不显式建立数据聚 合结构，簇首位置即为选取出的数据聚合点。文献【l l j 中也探讨了不显式建立数据 聚合树的高效数据聚合方法，给出了不依赖于数据聚合结构的高效节能的数据聚 合机制，具体体现在对数据在空间上尽可能早的进行数据聚合，以适应动态变化 的事件。 对于事件触发等具有动态特性业务模型的应用，一般适合采用不显式建立聚 合结构的数据聚合技术。因为对于事件触发类及动态性强的网络场景，建立和维 护这些数据聚合结构的能量开销很大【l0 1 。在动态的网络环境下，该能耗开销可 能大于使用数据聚合技术节省的能耗；而且使用数据聚合技术的性能与转发节点 的等待时间也有关系，若转发节点等待时间短，则聚合的概率较低；若转发节点 等待时间长，将增加数据回传的时延，最优等待时间的确定将依赖于转发节点在 l o 北京邮电大学硕士研究生学位论文无线传感器网络中数据聚合策略研究 数据聚合结构中的位置，这在事件触发类等应用中是很难确定的。 路由不显式建立数据聚合结构的特点在于：在路由生成过程中没有考虑聚合 代价因素，实现起来相对简单。 2 3 数据聚合时机的确定 在无线传感器网络中，当确定了数据回传路径中的数据聚合点后，数据聚合 的效果还与这些数据聚合节点进行数据聚合前的等待时间密切相关，需要知道等 待多长时间，合并哪些节点传来的数据，即需要确定数据聚合节点的数据聚合时 机。由于无线传感器网络中节点随机性布设，且节点能量、计算及存储空间等能 力有限，不可能维护动态变化的全局信息，因而解决上述问题是一个难点。数据 聚合节点需要对尽可能多的数据进行聚合，但是等待的时间过短，可能造成没有 进行或仅进行了部分数据的聚合；等待时间过长了，又可能造成数据传送至s i n k 节点的时延过长，因此需要在数据聚合时机和时延之间进行折中。 2 3 1 周期性数据回传中数据聚合时机的确定 文献【1 2 】对周期性监测应用中的三种数据聚合时机模型进行了比较，它们是周 期性简单数据聚合时机模型、周期性逐跳数据聚合时机模型及周期性逐跳调整数 据聚合时机模型等。 ( 1 ) 周期性简单聚合时机模型 每个节点等待固定时间长度，对已经接收到的数据执行数据聚合，然后向下 一跳发送聚合后的数据分组。 ( 2 ) 周期性逐跳数据聚合时机模型 与上一种相似，其不同之处在于：当节点收到自己所有孩子节点的数据后， 立即进行数据聚合并发送聚合后的结果。 论文后续章节里对于标量数据进行聚合处理过程中，聚合时机的确定就采用 了这种方法。 ( 3 ) 周期性逐跳调整数据聚合时机模型 根据节点在数据聚合树中的位置确定数据聚合的时机，距离s i n k 近的节点等 待时间长，距离s i n k 节点远的节点等待时间短。文献【1 3 】中的聚合方法就属于这 种模型。级联超时法也属于这种模型，根据节点在数据聚合树中距离s i n k 节点 的跳数确定数据的聚合时机，离s i n k 节点跳数少的等待时间长，离s i n k 节点跳 数多的等待时间短。所有节点的等待时间形成一种级联效应，在保证数据准确性 北京邮电大学硕士研究生学位论文无线传感器网络中数据聚合策略研究 及时延小的情况下，可以有效的节省能量。 a t c m 1 4 】是一种自适应的无线传感器网络数据聚合时机控制算法，它在级联 超时法的基础上，根据节点在数据聚合树中的位置及子节点个数的差异，自适应 的使用以节点为根的数据聚合子树的最大加权深度值，为节点选择合适的等待时 间，以有效的进行数据聚合处理。 与前两种模型相比，第三种模型在保证数据回传时延的情况下，能够使传感 器节点采集的数据在沿已知数据聚合树回传时最大程度的聚合，能更有效的节省 无线传感器网络的能耗。 2 3 2 事件触发类数据回传中聚合时机的确定 文献【i5 】为事件触发类数据回传提出了一种确定数据聚合时机的协议 m f s ，其网络模型为： ( 1 )节点密集部署，当无线传感器网络中发生某个事件时，事件附近区 域的多个传感器节点将采集到的数据报告给s i n k 节点。 ( 2 ) 每个节点进行数据回传时，知道自己的子节点和父节点。 ( 3 )s i n k 节点根据实际应用对数据时延及准确性等的要求，确定数据回 传的最大时延乙。、相邻层次节点数据聚合时机的时间间隔差。 当某事件发生时，如果是子节点探测到该事件，将立即向父节点回传数据； 如果是中间节点探测到事件或从子节点接收到第一个关于某事件的数据分组时， 将设置数据聚合定时器，其超时间隔为( 已。，一k * a ) ，k 为该节点距离s i n k 的最 小跳数，同时节点向相邻节点广播s t a r t 消息，触发上游节点。 这样，一个非子节点触发设置数据聚合定时器的时刻有三种情况： ( 1 )节点探测到该事件； ( 2 )从其子节点第一次接收到s t a r t 消息； ( 3 )从相邻节点接收到s t a r t 消息。 当节点的数据聚合定时器超时后，将执行数据聚合操作，并将聚合后的结果 传递至父节点。如果子节点的数据在该定时器超时后到达，则被丢弃。 2 4 数据聚合处理算法 数据聚合算法指对多个数据源进行处理，去除冗余，减少数据量，可以认为 是一种压缩算法【1 6 】。当前的流行的数据压缩算法有h u f f m a n 压缩算法、算术编 码、预测编码等。但这些算法并不能应用在无线传感器网络节点上，其原因主要 北京邮电大学硕士研究生学位论文无线传感器网络中数据聚合策略研究 有两点： ( 1 )传感器节点硬件限制，上述压缩算法均需要强大的计算能力，一般 的传感器节点不能满足其硬件要求。 ( 2 )上述算法规模太大，算法写入传感器节点后，自身剩余内存容量不 多，不能完成其在监测过程中对于数据的存储任务。 在无线传感器网络中，对聚合算法本身这一领域的研究与应用密切相关，包 括对温度、湿度的统计聚合以及图像聚合等。例如，在森林防火应用中，可以通 过数据聚合检测最高温度；在目标识别应用中，可以通过对各个节点所拍摄图像 的聚合得到观测目标的全貌。下面介绍几种适用于无线传感器网络中的数据聚合 机制。 2 4 1 基于数据顺序的聚合方式 文献【1 7 】主要介绍了该算法的核心思想。例如在某个感兴趣区域内，四个节点 n 1 、n 2 、n 3 、n 4 以及聚合节点n a 的分布如图2 2 所示，n 1 、n 2 、n 3 、n 4 四 个节点采集的数据在聚合节点n a 上进行聚合处理，然后再由n a 将压缩后的数 据发送给其上层节点。 n 4 n l 图2 - 2 数据顺序聚合算法 在该算法中，若采集数据的发送顺序对于应用不重要时