无线传感器网络数据收集技术进展

2010-08-15戴振华王建新

电脑与电信 2010年12期

戴振华王建新

(1.中南大学信息科学与工程学院，湖南长沙410083；2.湖南科技学院，湖南永州425100)

1.前言

无线传感器网络(Wireless Sensor Network，简称WSN)综合了传感器技术、嵌入式计算技术、分布式信息处理技术和通信技术，能够协作地实时监测、感知和采集网络分布区域内的各种环境或监测对象的信息，并对这些信息进行处理，获得详尽准确的信息，传送到需要这些信息的用户。

传感器网络技术将应用于越来越多的领域，例如战场监视、医疗护理、污染监测和目标跟踪等，在这些应用中，基本的操作是数据收集。与传统的有线网络和无线网络相比，传感器网络的数据收集面临更多的技术难题：(1)能效问题，无线传感器网络中节点具有通信和计算能力弱、电源能量有限且无法补充、易被损坏等特点；(2)存在相关数据收集和精确数据收集模式；(3)交互式数据收集，在某一特定时段，观测者可能只对某一区域的某些类型的传感器收集的数据感兴趣，不必激活大量传感器节点的数据收集；(4)自适应性，传感器网络的拓扑可能由于多种原因(节点失效、链路干扰等)而发生变化，这要求数据收集机制能够适应这些变化，具有动态的自适应性。基于传感器数据收集的这些特点，目前学者提出了一些传感器网络数据收集的算法，本文根据数据收集结构、节点数据流量、移动性、功率控制和睡眠调度方面的不同，综述了传感器网络数据收集的相关技术算法。

2.基于结构化的数据收集协议和算法

WSN的网络结构是影响数据收集协议的一个重要因素，如果网络区域很大，平坦型网络消耗更少的能量，如果网络规模小，层次型网络消耗更少的能量。

2.1 平坦型(Flat)网络

在平坦型网络里，包含大量的静态传感器节点和一个sink，所有传感器节点拥有同样的能量，具有相同的角色，都能够与sink通信。报文通过一跳或多跳转发到sink，即所有数据流量都流向sink。因此，靠近sink的节点比处于网络边缘的节点消耗更多的能量，这种网络结构只适合于小规模的网络。通常包括两阶段pull扩散、一阶段pull扩散和push扩散。

2.2 层次型(Hierarchical)网络

层次型结构通过在网络里选举某些节点作为簇头或增加少数高能量的节点，把整个网络自组织成不同的层次，增强了扩展性。

(1)基于簇结构的网络

所谓分簇技术，就是将节点划分成许多组，称为簇(cluster)，每个簇都有一个簇头和许多簇成员节点。分簇将网络划分为两层结构，簇头节点形成高一层，成员节点形成低一层，成员节点将数据发送给各自的簇头节点，簇头节点将数据融合后通过其它簇头节点发送到基站(sink)。分簇技术是一种优化能耗的拓扑控制技术，能减少冗余数据量，延长网络寿命，有效地进行网内数据融合，减少数据报告延迟和增强网络的可扩展性。由于簇头节点经常远距离传输数据，因此它们将消耗更多的能量。因此，网络将定期地重新进行分簇，选择能量充裕的节点担当簇头节点，从而将负载均匀地分布到所有节点上。分簇路由己经成为传感器网络的热门研究领域。近年来提出的较有代表性簇结构的网络协议主要有LEACH、HEED、CLUDDA。

LEACH是一个经典的延长网络寿命的聚类协议，它的基本思想是通过周期性等概率地随机选择簇头，将整个网络的能量负载平均分配到每个传感器节点，在簇头执行数据聚合，从而达到降低网络能耗的目的。尽管LEACH延长了系统生命期和数据的准确性，但要求簇头节点具有较大的通信能力，扩展性差，不适合大规模的网络，簇头节点的能量消耗也很快，频繁地选择簇头大大增加了网络能耗。

HEED的主要目标是通过高效成簇，将能耗均匀分布到整个网络从而最大化网络生命期。HEED的簇头选择主要依据主、次两个参数。HEED的主要改进是：在簇头选择中考虑了节点的剩余能量，并以主从关系引入了多个约束条件作用于簇头的选择过程，HEED在簇头选择标准以及簇头竞争机制上都与LEACH不同。实验结果表明，HEED分簇速度更快，能产生更加分布均匀的簇头、更合理的网络拓扑。

CLUDDA是一种结合了成簇和定向扩散的混合方法。主要分为两个阶段：兴趣传播和数据传播，兴趣消息里包含查询定义，描述需要对数据执行的操作。在兴趣传播阶段，只有簇头和sink执行兴趣分发任务，普通节点保持沉默，直到它能提供查询请求的服务，在簇头缓存查询消息，列出需要聚合的不同数据成分。在数据传播阶段执行分层聚合任务，聚合点是动态的，随源节点位置的变化而变化，尽可能在靠近源节点的地方执行数据聚合任务，任何具有查询定义的簇头或sink节点都可以选为聚合点。

(2)基于链式的网络

基于链的数据收集协议将网络中所有的节点构成一条链，并在链上选择一个节点作为头节点与sink节点直接通信，链两端数据沿链传输到头结点。基于链的数据收集协议减小了分簇算法在簇重构过程中所产生的开销，节点采用小功率与最近邻居节点通信，从而降低了能量的消耗。比较典型的基于链的数据收集协议有：PEGASIS。

PEGASIS是在LEACH基础上建立的一种链式的数据收集协议。该协议假设所有节点都静止，通过利用贪心算法，能够以一种中心化的方式形成一条相邻节点之间距离最短的链。

(3)基于树结构的网络

基于树的数据收集协议将在基于树结构的网络里，传感器节点被组织成一棵树的结构，非叶子节点可以执行数据聚合，沿树枝路径把数据发送到根节点。由于树结构是支持网络连通性的最小图结构，因此基于树的数据收集协议能有效保证网络的连通性和可靠性，具有保证QoS、容易实现高效的能量管理等优点，是目前研究的热点。比较典型的基于树结构的数据收集协议有：MAXLAT、PEDAP等。

MAXLAT算法以一棵拥有最多子树的生成树为基础，不断转移“瓶颈节点”的子树到“非瓶颈节点”的子树上去，以此减轻“瓶颈节点”的负载，使树的生命周期最大化。节点负载均衡，生命周期最大化。网络使用这种生成树进行数据收集，不用频繁地更换树结构，节省相应的通信和计算费用。仿真试验表明，算法能有效延长网络生命周期。

PEDAP以两个节点间通信代价作为权值构造生成树，能均衡网络中总的能量耗费，延长网络中最后一个死亡节点的生命周期。但是没有考虑节点剩余能量，容易使具有小能量的节点死亡。

(4)基于网格的网络

在基于网格的聚合机制里，传感器网络的监测环境被分割为一些网格或区域。在每一个网格或区域里选择一个传感器，赋予数据聚合者的角色，负责聚合网格里所有传感器的数据并向sink通报关键信息。网格内的传感器之间不相互通信，直接向本网格的聚合者发送数据。类似于基于簇的数据聚合，但网格里的聚合者是固定的，基于网格的数据聚合适合于网络拓扑动态变化或事件移动的环境。

3.基于流量优化的数据收集协议和算法

目前很多研究者把传感器网络建模为一个有向图，利用图论和最优化的相关知识研究传感器网络数据收集问题。假设传感器网络部署在某一区域，传感器的位置已知，而且是固定的。一般用有向图G=(V，E)建模，其中V是节点集，E是边(无线链路)的集合。近年来提出的基于流量优化的网络协议主要有MLDA。

MLDA是一种用于解决传感器网络最大生命期数据收集问题的多项式时间次优算法，其目标是获得一个最大生命期的数据收集调度。MLDA根据一阶射频模型建立了传感器的能量模型，并假设系统完全连接，每一轮执行一次数据收集，且每一个传感器只产生一个数据报文，中间节点能够把来自多个源的输入报文聚合成一个简单的输出报文。MLDA里提出了一种构造聚合树的启发式方法，在每一个数据收集轮次，根据容许流量生成一棵表示数据收集调度的有向树，数据聚合发生在生成聚合树之后。但是，在最坏情况下MLDA算法可扩展性较差，不适应大规模网络的要求。

4.基于移动性的数据收集协议和算法

4.1 存在移动观测者的数据收集算法

这一类网络中引入一个或多个移动数据观测者动态收集数据。移动数据观测者可能是一个具有高功率收发器的移动机器人或车辆，可视为移动的sink。移动数据观测者从基站开始巡游，穿越网络，从附近节点收集感知数据，最后返回远程数据处理中心更新数据。通过利用移动性增强传感器网络的数据传输性能，大大减少节点的能耗。

4.2 基于移动Agent的数据收集算法

移动Agent的作用非常类似于移动观测者，只不过移动的是Agent程序而不是节点。移动Agent具有传输数据少、能耗低、可伸缩性好、可靠性高等优点，适合于传感器网络数据收集应用。

5.基于功率控制的数据收集协议和算法

所谓功率控制，就是为传感器节点选择合适的发射功率。希腊佩特雷大学(University of Patras)的Kirousis等人将其简化为发射范围分配问题，详细讨论了该问题的计算复杂性，证明了功率控制在二维和三维情况下是NP难的。比较典型的功率控制协议有：TCMNC、TOED、BDL等。功率控制能通过有效降低节点的发射功率来延长网络的生命周期和调节传输延迟，但却没有很好地考虑空闲侦听时的能量消耗和覆盖冗余，在节点密集网络效果不佳。

6.基于睡眠调度的数据收集协议和算法

所谓睡眠调度，就是控制传感器节点在工作状态和睡眠状态之间的转换，从而延长网络的生命期。根据网络中节点间的协作关系，比较典型的睡眠调度协议有：MLDS、MEC、AELT等。睡眠调度能使冗余节点进入睡眠状态，大幅度地降低网络的能量消耗和竞争信道冲突，这对于节点密集型和事件驱动型的网络十分有效。但它需要在保证网络覆盖的情况下构造最优的连通支配集，这也一个NP完全的问题。而且，由于节点存储能力有限，当数据采样率高于节点唤醒率时，缓冲区溢出会导致数据丢失并重传，数据传输延迟很难保证。