论文部分内容阅读
第3卷第4期2013年8月智 能 计 算 机 与 应 用INTELLIGENT COMPUTER AND APPLICATIONSVol.3 No.4Aug.2013
收稿日期：2013-04-24
基金项目：国家自然科学基金重点项目（61033015）。
作者简介：于博（1985-），男，黑龙江黑河人，博士研究生，主要研究方向：无线传感器网络、算法设计；
李建中（1950-），男，黑龙江哈尔滨人，教授、博士生导师，主要研究方向：数据库、无线传感器网络、海量数据计算等。
无线传感器网络上数据聚集及调度研究综述
于博， 李建中（哈尔滨工业大学 计算机科学与技术学院， 哈尔滨 150001）摘要：无线传感器网络是近年来倍受关注的热点研究领域，综合了无线通信技术、微电子技术、嵌入式技术、传感器技术等，具有广阔的应用前景。数据聚集是无线传感器网络上一项基础而重要的操作，被研究者们所广泛关注，也涌现出了很多研究工作。总结了近年来无线传感器网络上的数据聚集以及数据聚集调度方向的研究工作，讨论了现有工作的内容和需要进一步研究的方向，并提供了广泛的参考文献。
关键词：无线传感器网络； 数据聚集； 调度
中图分类号：TP393 文献标识码：A文章编号：2095-2163（2013）04-0005-05
Survey on Data Aggregation and Scheduling in Wireless Sensor Networks
YU Bo， LI Jianzhong
（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001，China）
Abstract：Wireless sensor network is a research area with many hot research topics， which is widely concerned in recent years. Wireless sensor network integrates the technology of wireless communication， microelectronics， embedded system， sensing etc.， and provides significant application perspective. Data aggregation is an essential and important operation in wireless sensor networks， which is widely concerned by researchers， and there are also large amounts of research work on data aggregation. This paper introduces and summarizes the research work on data aggregation and aggregation scheduling in wireless sensor networks. This paper also discusses the existing solutions and the possible future work， and provides with plenty of references.
Key words：Wireless Sensor Networks； Data Aggregation； Scheduling
1无线传感器网络的背景和意义
无线传感器网络是近年来引起国内外广泛关注的新兴前沿热点研究领域，综合了无线通信技术、微电子技术、嵌入式计算技术、传感器技术等。无线传感器网络通过各种低成本、低功耗、多功能的微型传感器协调工作、有效感知并收集监测环境或监测对象的信息，再通过无线自组织通信网络以多跳传输方式将信息传送到基站或终端用户，从而形成了一种新的信息获取及处理模式。这是信息感知和采集的一场革命，是继互联网后将会对二十一世纪人类生活方式产生重大影响的热点技术。互联网构成了逻辑上的信息世界，改变了人类的沟通和交流的方式，而无线传感器网络则是将逻辑上的信息世界与客观上的物理世界融合在一起，彻底改变了人类与自然界的交互方式。
无线传感器网络具有十分光明的前景，因为其应用背景是极为广阔的。在环境监测领域，无线传感器网络可以用于收集环境信息方面的参数，比如温度、湿度、光强、二氧化碳浓度等。在军事领域，无线传感器网络可以应用于战地监测，用以对敌方军事目标的跟踪和定位、侦查敌方地形和布防等。在医疗卫生领域，无线传感器网络可以安装在病人身上，用于监测病人的健康指标，比如心率和血压等，以随时了解被监护病人的病情。无线传感器网络还可以应用在工农业生产、建筑物健康监测、交通管理等众多领域。如上所述，由于无线传感器网络的巨大应用价值，许多国家的军事部门、工业界以及学术界都对无线传感器网络给予了高度关注，使其成为当前计算机网络领域的一个重要的研究热点。
在无线传感器网络的许多应用中，网络中的传感器节点获取的感知数据需要进行收集并加以分析。然而，大量的感知数据全部都传输到无线传感器网络的基站则会消耗巨大的能量，在实际应用中是无法做到的。因此，研究者们提出了数据聚集的策略，旨在削减网络中通过无线传输的数据量，同时获得无线传感器网络覆盖区域的某些物理属性的聚集值，这是对物理世界的一个粗粒度的简约描述。数据聚集是无线传感器网络上的一项重要操作，近年来也受到了研究者们广泛的关注[1]。无线传感器网络上的数据聚集不同于传统的有线和无线网络上的数据聚集，原因在于无线传感器节点的能量、带宽、计算及存储能力都非常有限，所以基于其上的数据聚集更注重考虑能量的节省和通信的开销，这些都为无线传感器网络上的聚集研究带来了新的挑战。因此，无线传感器网络上数据聚集策略的研究是一个带有挑战性的前沿研究领域，具有重要的理论和实际意义。 1.1无线传感器网络概述
无线传感器网络是由一组低成本、低功耗的无线传感器节点通过自组织的方式形成的无线网络，其目的是协同感知、采集和处理无线传感器网络覆盖区域范围内感知对象的信息，并发布给观察者[2-4]。通常每个传感器节点是由电源、感知部件、嵌入式处理器、存储器、通信部件和软件等几个部分组成。其中，电源可为传感器节点提供正常工作所必需的能源。感知部件用于感知和获取物理世界的属性信息，并将其转化为数字信号。嵌入式处理器部件负责协调传感器节点各部分的有序工作，比如对感知部件获取的信息进行处理、控制感知部件以及电源的工作模式等。存储器负责存放传感器节点需要用到的程序和数据。通信部件负责与其他传感器节点或用户进行通信。软件则是为传感器节点提供软件支持，包括嵌入式操作系统、嵌入式数据管理系统等。
无线传感器节点、感知对象和观察者是无线传感器网络的三个基本要素[5]。传感器网络是传感器节点之间、传感器节点与观察者之间的通信方式，用于在传感器节点与观察者之间建立通信路径。协同感知、采集、处理及发布感知信息是无线传感器网络的基本功能。观察者是无线传感器网络的用户，是感知信息的接受者和应用者。观察者可以是人、计算机或其他设备，观察者可以主动地收集、查询传感器网络获取的感知信息，也可以被动地接收传感器网络发布的感知信息。
具体地讲，一个典型的无线传感器网络是由多个无线传感器节点、一个或多个基站、互联网或通信卫星、任务管理节点等部分有机组成。无线传感器节点依靠无线方式与其他节点进行通信，节点可以通过多次无线传输 （又称多跳传输） 将感知数据送达目标节点。无线传感器节点以此方式形成了一个自组织的无线网络，同时网络中的基站也可以通过多跳传输的方式将数据和控制信息传送到各个传感器节点上，而基站又可以通过互联网或外部网络将感知数据传输至任务管理节点 （即观察者）。在数据聚集中，无线传感器网络中的所有或者部分传感器节点将感知数据首先在网内进行聚集，然后再以多跳传输的方式将聚集结果传送到基站。第4期于博，等：无线传感器网络上数据聚集及调度研究综述智能计算机与应用第3卷
1.2无线传感器网络的特点与挑战
与传统的网络不同，无线传感器网络具有很多鲜明的特点，而这些特点也相应地带来了一系列的挑战性问题，在此可简要总结为以下几个方面。
（1）节点能量有限。目前现有的大多数无线传感器节点通过电池供电，而有限的电源能量则限制了节点的生命周期，网络中的传感器由于电源能量的原因经常失效或废弃，这已经成为阻碍无线传感器网络实际应用的一个重大问题[2]。无线传感器节点传输信息比执行计算操作更消耗电能，据研究，无线传感器传输1位信息所需的电能足以执行3 000条计算指令[5]。因此，可以认为传感器节点的主要能耗在于无线通信，而执行计算的能耗则可以忽略不计。
（2）节点的计算和存储能力有限。无线传感器网络中的节点都具有嵌入式处理器和存储器。这些传感器节点都具有计算能力，可以完成一些信息处理工作。然而，由于嵌入式处理器和存储器的能力和容量都十分有限，传感器的计算能力也很有限。因此，如何利用大量的能力有限的无线传感器节点进行协同分布式信息处理，也成为一个重要挑战。
（3）节点的通信能力有限。由于无线传感器节点之间以无线方式通信，无线传感器网络覆盖区域内的自然环境将严重影响节点间的通信质量。无线传感器节点之间的常用通信频段高、带宽窄，致使通信半径一般只有几十米，且数据传输速率比其他高速无线网络更低。同时，由于传感器节点采用无线通信技术，常常会出现信号碰撞的情况，这也会消耗网络的能量。因此，无线通信的干扰对感知数据计算的影响也是研究中需要考虑的。在考虑无线干扰的情况下，设计分布式感知数据的无冲突计算策略又是一个挑战。
（4）网络规模巨大。传感器网络中传感器节点密集，数量巨大，可能达到几百、几千甚至更多。此外，传感器网络可以分布在广袤的地理区域。传感器数量大、分布广的特点使得网络的维护将十分困难，那么如何在大规模传感器网络背景下完成分布式感知数据的计算值得加大力度认真研究。
（5）网络动态性强。在某些应用背景下，传感器网络会具有很强的动态性。无线传感器网络中的传感器、感知对象和观察者这三要素都可能具有移动性，并且经常有新节点加入或已有节点失效，也或者是链路失效。针对这种网络动态性，传感器网络上的感知数据计算机制必须具有自调整和自恢复性，比如失效节点和新加入节点的处理，移动节点参与计算机制等问题。
（6）以数据为中心，感知数据流巨大。在无线传感器网络的现实应用中，每个传感器节点需要对感知对象进行实时监测并产生感知数据。随着时间的累积，大规模的传感器网络中常常会产生巨大的数据流汇聚到基站。因此，不同于传统网络“以传输数据为目的”的特点，无线传感器网络的特点是以数据为中心[4]。基于此，高效的分布式流数据处理、查询和分析方法已然成为研究者们面临的一大重要挑战。
2无线传感器网络上数据聚集的研究工作
数据聚集是无线传感器网络上的一个重要的基本操作，包括简单的聚集操作如 MAX （最大值）、MIN （最小值）、SUM （求和）、COUNT （计数）、LOGIC AND （逻辑与）、LOGIC OR （逻辑或） 等，也包括复杂的聚集操作如AVERAGE （平均值）、MEDIAN （中位数）等。由于无线传感器网络的能源有限，网内聚集[6]技术得到了研究者们的高度重视和普遍研究。网内聚集指的是在网络内部传输数据的过程中同时进行聚集操作，并不断地传输中间聚集结果，再将最终的聚集结果传输到基站。由此可以极大地减少网络中传输的数据量，节省了能量，同时减轻了网络的数据传输负担，降低了数据的传输延迟。下面，介绍无线传感器网络上有关数据聚集的代表性研究工作。
文献[7]最早提出了无线传感器网络上的数据聚集操作，允许用户向网络提出简单的、陈述性的查询，并在网内高效执行。文献[8]提出了一种数据聚集新机制，不仅支持简单聚集查询，而且支持复杂聚集查询，如中位数等。 在无线传感器网络上数据聚集的研究工作绝大部分都可分为基于树结构和基于聚簇两种聚集模式。文献[6-10]等皆是基于树结构进行数据聚集，也是最常见的方式。文献[11]研究了传感器网络上基于树结构的聚集中如何提高数据采集率的问题。文献[12]考察了传感器网络上最小化能量的聚集树构造问题的复杂性并提出了相应的算法。基于聚簇的聚集模式则有以下重点成果。LEACH协议[13]基于聚簇实现网内的数据收集，每个簇头负责收集本簇中所有节点的数据并将数据聚集后传送到基站。文献[14]针对LEACH协议的缺点，提出了PEGASIS协议。在该协议中，所有传感器节点作为一个簇，全部节点的数据被传送到簇头，簇头执行聚集操作并把结果传输到基站。为了保证负载平衡，PEGASIS协议轮转地选择簇头。文献[15]在聚簇模式的传感器网络上研究了自适应的数据聚集机制。文献[16]为传感器网络上的数据聚集与收集提出了一种分级的聚簇协议DEEG，通过优化能量消耗和平衡网内节点间的能量负载延长网络生命周期。文献[17]考虑了聚簇模式传感器网络上数据收集过程中簇间的负载平衡，以避免通信热点的形成。
除了树结构和聚簇两种模式以外的数据聚集则有如下的瞩目性工作成果。文献[18]为无线传感器网络提出了新的网内聚集的策略Tributary-Delta，同时结合了树结构和多路径结构的优点。文献[19]提出了无线传感器网络上的无结构数据聚集方法。
研究者们在传感器网络的数据聚集方面也开展了一些理论性研究工作。文献[20]研究了无线传感器网络的密度对数据聚集的影响。文献[21]研究了以数据为中心的路由对数据聚集的影响，并且从理论上给出了最优数据聚集问题的复杂性。文献[22]给出了无线传感器网络上数据聚集、收集、选择操作的复杂性分析。文献[23]研究了无线传感器网络中有延迟约束的数据聚集，通过调度数据包传输来最小化数据聚集树中节点的能量消耗，并考察了能量消耗与延迟之间的折中问题。
在无线传感器网络上数据聚集的算法技术研究方面，有如下坐标式的工作成果。文献[24]为传感器网络上的数据聚集提出了一种启发式算法，旨在降低时间延迟和能量消耗。文献[25]为传感器网络上的数据聚集提出了一种基于位置信息的路由策略。文献[26]研究了在大规模无线传感器网络中节点稀疏的情况下如何处理数据聚集问题，提出了传感器节点自发建立优化传输路径的方法，而且节省了聚集过程所用的能量。文献[10]提出了模型驱动的数据获取技术，并研究了如何平衡数据置信度与网络中数据获取开销的方法。文献[27]为避免重复计数，利用 synopsis 技术实现了传感器网络上的数据聚集。
无线传感器网络中数据聚集的评价性能指标一般包括能量开销、网络生命周期、聚集时间延迟、数据质量等，有很多研究工作考虑对上述的某项或某些项性能指标进行优化或平衡。文献[28]从理论上给出了无线传感器网络上数据聚集时网络的最大生命周期。文献[29]将数据聚集和路由结合在一起提出了一种聚集机制，目标是最大化传感器网络生命周期。文献 [30]研究了传感器网络上连续数据聚集时如何延长网络生命周期的问题，考察了数据质量和能量开销的基本平衡。文献[31]为传感器网络上的分布式聚集操作提出了一种随机策略，并考虑了能量开销和聚集时间延迟的平衡。文献[32]为节省传感器网络的能量，并针对低数据速率的传感器网络上的数据收集与聚集而设计了能量有效的协议。
无线传感器网络上数据聚集还有一些研究工作考虑了不同的应用需求和技术策略。例如，文献[33]考虑了无线传感器网络中移动用户收集数据的需求，通过动态更新数据收集树结构给出了一种数据收集方法。文献[34]考察了无线传感器网络上数据聚集的安全问题。文献[35]研究了大规模无线传感器网络上的压缩数据聚集问题，由此降低了网络整体的通信开销。
3无线传感器网络上数据聚集调度的研究工作
本节详细介绍无线传感器网络上数据聚集调度方面的研究工作如下。
文献[9]提出了一种同时支持传感器网络上广播和聚集的启发式算法。文献[36]为由n个节点组成的传感器网络提出了一种分布式的随机算法，其期望的延迟是O（logn）。该模型中有两个假设，第一个是假设每个传感器节点在发送数据后能够检测到是否发生冲突，第二个是假设传感器节点可以无限制地调整其传输半径。这两个假设对硬件设计增加了很大的难度，而且第二个假设在大网络规模下并不成立。文献[37]为数据收集提出了一个无冲突的调度方法，目标是优化能量开销和可靠性。
无线传感器网络上的数据聚集调度问题是指给定一个无线传感器网络的拓扑结构图，为网络中的所有节点产生相关的调度，每个节点的调度指定了该节点在哪个时间片将其数据传输给哪个节点，并且保证在数据聚集时所有节点均按照此调度进行数据传输，而不会发生冲突，同时最小化聚集时间。文献[38]证明最小化聚集时间的数据聚集调度问题是NP-难的，并且提出了一个近似算法，基本思想是采用最短的路径进行数据聚集。该算法的近似比为 （Δ-1），其中，Δ是网络拓扑图的最大顶点度。文献[39]为解决最小化时间数据聚集调度问题给出了一个调度算法，聚集时间延迟的上界为23R Δ-18，其中，R是网络拓扑图的半径，Δ仍然是网络拓扑图的最大顶点度。然而，该算法不能保证返回的结果是网络的一个无冲突的调度。文献[40]给出了解决无线传感器网络上最小化时间的数据聚集调度问题的第一个分布式算法，之前的算法均是集中式的，而且在网络拓扑变化的网络中具有一定的局限性，同时也给出了聚集时间的理论上界。
文献[41]为了进一步降低数据聚集调度问题的聚集时间延迟，给出了几个集中式算法。这几个算法的聚集时间上界分别为 15R Δ-4，2R O（logR） Δ 和 （1 O（logR/3√R））R，其中， R是关于基站的网络半径。文献[42]提出了一种新的分布式数据聚集调度算法，改进了之前的工作，其聚集时间为16R Δ-14。文献[43]为最小化时间的数据聚集调度问题提出了一个分布式算法，进一步改进了之前工作的聚集时间，该算法的聚集时间不超过4R Δ-2。文献[44-46]研究了在物理干扰模型 （Physical Interference Model） 下无线传感器网络上最小化时间延迟的数据聚集调度问题，并给出了相应的算法。文献[47]提出了最小化时间的分布式的数据收集调度算法，而数据收集要求传感器网络内的所有节点将数据传输到基站，并且数据包不能在网络内部完成合并，因此在N个节点构成的传感器网络中数据收集的时间延迟下界是N 个时间片 （因为基站需要至少 N 个时间片来接收网络中的 N个数据包）。文献[47]提出的算法的时间延迟上界为max{3nk-1， N}，其中，nk是最大一跳子树中的节点个数。注意，该算法是数据收集的调度算法，而非数据聚集的调度。 在无线传感器网络上的聚集调度问题还可以考虑一些特殊类型的无线传感器网络环境，比如周期轮转模式的无线传感器网络、异构的混合无线传感器网络等，也可以将聚集调度工作延展到普通的无线网络上，这些都是未来可以考虑的研究方向。
4结束语
目前，无线传感器网络已引起了研究者们前所未有的广泛关注与重视，而数据聚集作为无线传感器网络中最基本、且最重要的操作则得到了深入的研究，得到了为数众多的研究成果。在本文中，归纳并总结了数据聚集方向以及数据聚集调度方向已有的研究，并对可能的研究方向进行了简要分析和阐述，希望能够借此推动国内对数据聚集问题更大范围和规模的研究。
参考文献：
[1]RAJAGOPALAN R， VARSHNEY P K. Data-aggregation techniques in sensor networks： a survey[J]. Communications Surveys
收稿日期：2013-04-24
基金项目：国家自然科学基金重点项目（61033015）。
作者简介：于博（1985-），男，黑龙江黑河人，博士研究生，主要研究方向：无线传感器网络、算法设计；
李建中（1950-），男，黑龙江哈尔滨人，教授、博士生导师，主要研究方向：数据库、无线传感器网络、海量数据计算等。
无线传感器网络上数据聚集及调度研究综述
于博， 李建中（哈尔滨工业大学 计算机科学与技术学院， 哈尔滨 150001）摘要：无线传感器网络是近年来倍受关注的热点研究领域，综合了无线通信技术、微电子技术、嵌入式技术、传感器技术等，具有广阔的应用前景。数据聚集是无线传感器网络上一项基础而重要的操作，被研究者们所广泛关注，也涌现出了很多研究工作。总结了近年来无线传感器网络上的数据聚集以及数据聚集调度方向的研究工作，讨论了现有工作的内容和需要进一步研究的方向，并提供了广泛的参考文献。
关键词：无线传感器网络； 数据聚集； 调度
中图分类号：TP393 文献标识码：A文章编号：2095-2163（2013）04-0005-05
Survey on Data Aggregation and Scheduling in Wireless Sensor Networks
YU Bo， LI Jianzhong
（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001，China）
Abstract：Wireless sensor network is a research area with many hot research topics， which is widely concerned in recent years. Wireless sensor network integrates the technology of wireless communication， microelectronics， embedded system， sensing etc.， and provides significant application perspective. Data aggregation is an essential and important operation in wireless sensor networks， which is widely concerned by researchers， and there are also large amounts of research work on data aggregation. This paper introduces and summarizes the research work on data aggregation and aggregation scheduling in wireless sensor networks. This paper also discusses the existing solutions and the possible future work， and provides with plenty of references.
Key words：Wireless Sensor Networks； Data Aggregation； Scheduling
1无线传感器网络的背景和意义
无线传感器网络是近年来引起国内外广泛关注的新兴前沿热点研究领域，综合了无线通信技术、微电子技术、嵌入式计算技术、传感器技术等。无线传感器网络通过各种低成本、低功耗、多功能的微型传感器协调工作、有效感知并收集监测环境或监测对象的信息，再通过无线自组织通信网络以多跳传输方式将信息传送到基站或终端用户，从而形成了一种新的信息获取及处理模式。这是信息感知和采集的一场革命，是继互联网后将会对二十一世纪人类生活方式产生重大影响的热点技术。互联网构成了逻辑上的信息世界，改变了人类的沟通和交流的方式，而无线传感器网络则是将逻辑上的信息世界与客观上的物理世界融合在一起，彻底改变了人类与自然界的交互方式。
无线传感器网络具有十分光明的前景，因为其应用背景是极为广阔的。在环境监测领域，无线传感器网络可以用于收集环境信息方面的参数，比如温度、湿度、光强、二氧化碳浓度等。在军事领域，无线传感器网络可以应用于战地监测，用以对敌方军事目标的跟踪和定位、侦查敌方地形和布防等。在医疗卫生领域，无线传感器网络可以安装在病人身上，用于监测病人的健康指标，比如心率和血压等，以随时了解被监护病人的病情。无线传感器网络还可以应用在工农业生产、建筑物健康监测、交通管理等众多领域。如上所述，由于无线传感器网络的巨大应用价值，许多国家的军事部门、工业界以及学术界都对无线传感器网络给予了高度关注，使其成为当前计算机网络领域的一个重要的研究热点。
在无线传感器网络的许多应用中，网络中的传感器节点获取的感知数据需要进行收集并加以分析。然而，大量的感知数据全部都传输到无线传感器网络的基站则会消耗巨大的能量，在实际应用中是无法做到的。因此，研究者们提出了数据聚集的策略，旨在削减网络中通过无线传输的数据量，同时获得无线传感器网络覆盖区域的某些物理属性的聚集值，这是对物理世界的一个粗粒度的简约描述。数据聚集是无线传感器网络上的一项重要操作，近年来也受到了研究者们广泛的关注[1]。无线传感器网络上的数据聚集不同于传统的有线和无线网络上的数据聚集，原因在于无线传感器节点的能量、带宽、计算及存储能力都非常有限，所以基于其上的数据聚集更注重考虑能量的节省和通信的开销，这些都为无线传感器网络上的聚集研究带来了新的挑战。因此，无线传感器网络上数据聚集策略的研究是一个带有挑战性的前沿研究领域，具有重要的理论和实际意义。 1.1无线传感器网络概述
无线传感器网络是由一组低成本、低功耗的无线传感器节点通过自组织的方式形成的无线网络，其目的是协同感知、采集和处理无线传感器网络覆盖区域范围内感知对象的信息，并发布给观察者[2-4]。通常每个传感器节点是由电源、感知部件、嵌入式处理器、存储器、通信部件和软件等几个部分组成。其中，电源可为传感器节点提供正常工作所必需的能源。感知部件用于感知和获取物理世界的属性信息，并将其转化为数字信号。嵌入式处理器部件负责协调传感器节点各部分的有序工作，比如对感知部件获取的信息进行处理、控制感知部件以及电源的工作模式等。存储器负责存放传感器节点需要用到的程序和数据。通信部件负责与其他传感器节点或用户进行通信。软件则是为传感器节点提供软件支持，包括嵌入式操作系统、嵌入式数据管理系统等。
无线传感器节点、感知对象和观察者是无线传感器网络的三个基本要素[5]。传感器网络是传感器节点之间、传感器节点与观察者之间的通信方式，用于在传感器节点与观察者之间建立通信路径。协同感知、采集、处理及发布感知信息是无线传感器网络的基本功能。观察者是无线传感器网络的用户，是感知信息的接受者和应用者。观察者可以是人、计算机或其他设备，观察者可以主动地收集、查询传感器网络获取的感知信息，也可以被动地接收传感器网络发布的感知信息。
具体地讲，一个典型的无线传感器网络是由多个无线传感器节点、一个或多个基站、互联网或通信卫星、任务管理节点等部分有机组成。无线传感器节点依靠无线方式与其他节点进行通信，节点可以通过多次无线传输 （又称多跳传输） 将感知数据送达目标节点。无线传感器节点以此方式形成了一个自组织的无线网络，同时网络中的基站也可以通过多跳传输的方式将数据和控制信息传送到各个传感器节点上，而基站又可以通过互联网或外部网络将感知数据传输至任务管理节点 （即观察者）。在数据聚集中，无线传感器网络中的所有或者部分传感器节点将感知数据首先在网内进行聚集，然后再以多跳传输的方式将聚集结果传送到基站。第4期于博，等：无线传感器网络上数据聚集及调度研究综述智能计算机与应用第3卷
1.2无线传感器网络的特点与挑战
与传统的网络不同，无线传感器网络具有很多鲜明的特点，而这些特点也相应地带来了一系列的挑战性问题，在此可简要总结为以下几个方面。
（1）节点能量有限。目前现有的大多数无线传感器节点通过电池供电，而有限的电源能量则限制了节点的生命周期，网络中的传感器由于电源能量的原因经常失效或废弃，这已经成为阻碍无线传感器网络实际应用的一个重大问题[2]。无线传感器节点传输信息比执行计算操作更消耗电能，据研究，无线传感器传输1位信息所需的电能足以执行3 000条计算指令[5]。因此，可以认为传感器节点的主要能耗在于无线通信，而执行计算的能耗则可以忽略不计。
（2）节点的计算和存储能力有限。无线传感器网络中的节点都具有嵌入式处理器和存储器。这些传感器节点都具有计算能力，可以完成一些信息处理工作。然而，由于嵌入式处理器和存储器的能力和容量都十分有限，传感器的计算能力也很有限。因此，如何利用大量的能力有限的无线传感器节点进行协同分布式信息处理，也成为一个重要挑战。
（3）节点的通信能力有限。由于无线传感器节点之间以无线方式通信，无线传感器网络覆盖区域内的自然环境将严重影响节点间的通信质量。无线传感器节点之间的常用通信频段高、带宽窄，致使通信半径一般只有几十米，且数据传输速率比其他高速无线网络更低。同时，由于传感器节点采用无线通信技术，常常会出现信号碰撞的情况，这也会消耗网络的能量。因此，无线通信的干扰对感知数据计算的影响也是研究中需要考虑的。在考虑无线干扰的情况下，设计分布式感知数据的无冲突计算策略又是一个挑战。
（4）网络规模巨大。传感器网络中传感器节点密集，数量巨大，可能达到几百、几千甚至更多。此外，传感器网络可以分布在广袤的地理区域。传感器数量大、分布广的特点使得网络的维护将十分困难，那么如何在大规模传感器网络背景下完成分布式感知数据的计算值得加大力度认真研究。
（5）网络动态性强。在某些应用背景下，传感器网络会具有很强的动态性。无线传感器网络中的传感器、感知对象和观察者这三要素都可能具有移动性，并且经常有新节点加入或已有节点失效，也或者是链路失效。针对这种网络动态性，传感器网络上的感知数据计算机制必须具有自调整和自恢复性，比如失效节点和新加入节点的处理，移动节点参与计算机制等问题。
（6）以数据为中心，感知数据流巨大。在无线传感器网络的现实应用中，每个传感器节点需要对感知对象进行实时监测并产生感知数据。随着时间的累积，大规模的传感器网络中常常会产生巨大的数据流汇聚到基站。因此，不同于传统网络“以传输数据为目的”的特点，无线传感器网络的特点是以数据为中心[4]。基于此，高效的分布式流数据处理、查询和分析方法已然成为研究者们面临的一大重要挑战。
2无线传感器网络上数据聚集的研究工作
数据聚集是无线传感器网络上的一个重要的基本操作，包括简单的聚集操作如 MAX （最大值）、MIN （最小值）、SUM （求和）、COUNT （计数）、LOGIC AND （逻辑与）、LOGIC OR （逻辑或） 等，也包括复杂的聚集操作如AVERAGE （平均值）、MEDIAN （中位数）等。由于无线传感器网络的能源有限，网内聚集[6]技术得到了研究者们的高度重视和普遍研究。网内聚集指的是在网络内部传输数据的过程中同时进行聚集操作，并不断地传输中间聚集结果，再将最终的聚集结果传输到基站。由此可以极大地减少网络中传输的数据量，节省了能量，同时减轻了网络的数据传输负担，降低了数据的传输延迟。下面，介绍无线传感器网络上有关数据聚集的代表性研究工作。
文献[7]最早提出了无线传感器网络上的数据聚集操作，允许用户向网络提出简单的、陈述性的查询，并在网内高效执行。文献[8]提出了一种数据聚集新机制，不仅支持简单聚集查询，而且支持复杂聚集查询，如中位数等。 在无线传感器网络上数据聚集的研究工作绝大部分都可分为基于树结构和基于聚簇两种聚集模式。文献[6-10]等皆是基于树结构进行数据聚集，也是最常见的方式。文献[11]研究了传感器网络上基于树结构的聚集中如何提高数据采集率的问题。文献[12]考察了传感器网络上最小化能量的聚集树构造问题的复杂性并提出了相应的算法。基于聚簇的聚集模式则有以下重点成果。LEACH协议[13]基于聚簇实现网内的数据收集，每个簇头负责收集本簇中所有节点的数据并将数据聚集后传送到基站。文献[14]针对LEACH协议的缺点，提出了PEGASIS协议。在该协议中，所有传感器节点作为一个簇，全部节点的数据被传送到簇头，簇头执行聚集操作并把结果传输到基站。为了保证负载平衡，PEGASIS协议轮转地选择簇头。文献[15]在聚簇模式的传感器网络上研究了自适应的数据聚集机制。文献[16]为传感器网络上的数据聚集与收集提出了一种分级的聚簇协议DEEG，通过优化能量消耗和平衡网内节点间的能量负载延长网络生命周期。文献[17]考虑了聚簇模式传感器网络上数据收集过程中簇间的负载平衡，以避免通信热点的形成。
除了树结构和聚簇两种模式以外的数据聚集则有如下的瞩目性工作成果。文献[18]为无线传感器网络提出了新的网内聚集的策略Tributary-Delta，同时结合了树结构和多路径结构的优点。文献[19]提出了无线传感器网络上的无结构数据聚集方法。
研究者们在传感器网络的数据聚集方面也开展了一些理论性研究工作。文献[20]研究了无线传感器网络的密度对数据聚集的影响。文献[21]研究了以数据为中心的路由对数据聚集的影响，并且从理论上给出了最优数据聚集问题的复杂性。文献[22]给出了无线传感器网络上数据聚集、收集、选择操作的复杂性分析。文献[23]研究了无线传感器网络中有延迟约束的数据聚集，通过调度数据包传输来最小化数据聚集树中节点的能量消耗，并考察了能量消耗与延迟之间的折中问题。
在无线传感器网络上数据聚集的算法技术研究方面，有如下坐标式的工作成果。文献[24]为传感器网络上的数据聚集提出了一种启发式算法，旨在降低时间延迟和能量消耗。文献[25]为传感器网络上的数据聚集提出了一种基于位置信息的路由策略。文献[26]研究了在大规模无线传感器网络中节点稀疏的情况下如何处理数据聚集问题，提出了传感器节点自发建立优化传输路径的方法，而且节省了聚集过程所用的能量。文献[10]提出了模型驱动的数据获取技术，并研究了如何平衡数据置信度与网络中数据获取开销的方法。文献[27]为避免重复计数，利用 synopsis 技术实现了传感器网络上的数据聚集。
无线传感器网络中数据聚集的评价性能指标一般包括能量开销、网络生命周期、聚集时间延迟、数据质量等，有很多研究工作考虑对上述的某项或某些项性能指标进行优化或平衡。文献[28]从理论上给出了无线传感器网络上数据聚集时网络的最大生命周期。文献[29]将数据聚集和路由结合在一起提出了一种聚集机制，目标是最大化传感器网络生命周期。文献 [30]研究了传感器网络上连续数据聚集时如何延长网络生命周期的问题，考察了数据质量和能量开销的基本平衡。文献[31]为传感器网络上的分布式聚集操作提出了一种随机策略，并考虑了能量开销和聚集时间延迟的平衡。文献[32]为节省传感器网络的能量，并针对低数据速率的传感器网络上的数据收集与聚集而设计了能量有效的协议。
无线传感器网络上数据聚集还有一些研究工作考虑了不同的应用需求和技术策略。例如，文献[33]考虑了无线传感器网络中移动用户收集数据的需求，通过动态更新数据收集树结构给出了一种数据收集方法。文献[34]考察了无线传感器网络上数据聚集的安全问题。文献[35]研究了大规模无线传感器网络上的压缩数据聚集问题，由此降低了网络整体的通信开销。
3无线传感器网络上数据聚集调度的研究工作
本节详细介绍无线传感器网络上数据聚集调度方面的研究工作如下。
文献[9]提出了一种同时支持传感器网络上广播和聚集的启发式算法。文献[36]为由n个节点组成的传感器网络提出了一种分布式的随机算法，其期望的延迟是O（logn）。该模型中有两个假设，第一个是假设每个传感器节点在发送数据后能够检测到是否发生冲突，第二个是假设传感器节点可以无限制地调整其传输半径。这两个假设对硬件设计增加了很大的难度，而且第二个假设在大网络规模下并不成立。文献[37]为数据收集提出了一个无冲突的调度方法，目标是优化能量开销和可靠性。
无线传感器网络上的数据聚集调度问题是指给定一个无线传感器网络的拓扑结构图，为网络中的所有节点产生相关的调度，每个节点的调度指定了该节点在哪个时间片将其数据传输给哪个节点，并且保证在数据聚集时所有节点均按照此调度进行数据传输，而不会发生冲突，同时最小化聚集时间。文献[38]证明最小化聚集时间的数据聚集调度问题是NP-难的，并且提出了一个近似算法，基本思想是采用最短的路径进行数据聚集。该算法的近似比为 （Δ-1），其中，Δ是网络拓扑图的最大顶点度。文献[39]为解决最小化时间数据聚集调度问题给出了一个调度算法，聚集时间延迟的上界为23R Δ-18，其中，R是网络拓扑图的半径，Δ仍然是网络拓扑图的最大顶点度。然而，该算法不能保证返回的结果是网络的一个无冲突的调度。文献[40]给出了解决无线传感器网络上最小化时间的数据聚集调度问题的第一个分布式算法，之前的算法均是集中式的，而且在网络拓扑变化的网络中具有一定的局限性，同时也给出了聚集时间的理论上界。
文献[41]为了进一步降低数据聚集调度问题的聚集时间延迟，给出了几个集中式算法。这几个算法的聚集时间上界分别为 15R Δ-4，2R O（logR） Δ 和 （1 O（logR/3√R））R，其中， R是关于基站的网络半径。文献[42]提出了一种新的分布式数据聚集调度算法，改进了之前的工作，其聚集时间为16R Δ-14。文献[43]为最小化时间的数据聚集调度问题提出了一个分布式算法，进一步改进了之前工作的聚集时间，该算法的聚集时间不超过4R Δ-2。文献[44-46]研究了在物理干扰模型 （Physical Interference Model） 下无线传感器网络上最小化时间延迟的数据聚集调度问题，并给出了相应的算法。文献[47]提出了最小化时间的分布式的数据收集调度算法，而数据收集要求传感器网络内的所有节点将数据传输到基站，并且数据包不能在网络内部完成合并，因此在N个节点构成的传感器网络中数据收集的时间延迟下界是N 个时间片 （因为基站需要至少 N 个时间片来接收网络中的 N个数据包）。文献[47]提出的算法的时间延迟上界为max{3nk-1， N}，其中，nk是最大一跳子树中的节点个数。注意，该算法是数据收集的调度算法，而非数据聚集的调度。 在无线传感器网络上的聚集调度问题还可以考虑一些特殊类型的无线传感器网络环境，比如周期轮转模式的无线传感器网络、异构的混合无线传感器网络等，也可以将聚集调度工作延展到普通的无线网络上，这些都是未来可以考虑的研究方向。
4结束语
目前，无线传感器网络已引起了研究者们前所未有的广泛关注与重视，而数据聚集作为无线传感器网络中最基本、且最重要的操作则得到了深入的研究，得到了为数众多的研究成果。在本文中，归纳并总结了数据聚集方向以及数据聚集调度方向已有的研究，并对可能的研究方向进行了简要分析和阐述，希望能够借此推动国内对数据聚集问题更大范围和规模的研究。
参考文献：
[1]RAJAGOPALAN R， VARSHNEY P K. Data-aggregation techniques in sensor networks： a survey[J]. Communications Surveys