无线传感器网络数据收集研究综述

摘要：数据收集是无线传感器网络的重要技术之一，在对诸多文献进行归纳总结的基础上，介绍了几种无线传感器网络中周期性数据收集的方法。

关键词：无线传感器网络；数据收集；周期性

中图分类号：TP212文献标识码：A 文章编号：1009-3044(2011)30-7370-02

Overview of Data Gathering in Wireless Sensor Networks

HE Hui-lin, XIAO Qiang-hua

(School of Mathematics & Physics, University of South China, Hengyang 421001, China)

Abstract: Data gathering is crucial technology in wireless sensor networks. Based on the summary of some literatures, methods of Data gathering in wireless sensor networks are introduced.

Key words: wireless sensor network; data gathering; periodicity

无线传感器网络(Wireless Sensor Network，简称WSN)是一种由大量微型传感器节点通过无线通信自组织而成的网络系统，用于实时地监测、感知和采集某个区域的信息，对信息进行处理，并发送给观察者。近年来，无线传感器在军事国防、工农业控制、生物医疗、环境监测等诸多领域得到了广泛的应用。

数据收集是无线传感器网络的基本功能之一，指将节点感知到的数据传送到Sink节点，使得用户可以进行分析和处理。数据收集包括数据采集、数据处理和数据传输，其中数据传输会消耗大量的能量。而传感器节点仅通过携带能量有限的电池进行供电，这使得网络中的能量资源有限，因此在无线传感器网络中，尽可能地保存节点能量，及有效地进行数据收集以尽量延长网络工作寿命是研究的热点。目前，已有大量的工作对无线传感器网络中的数据收集进行研究，本文根据Sink节点是否固定来讨论传感器网络周期性数据收集方法，而周期性数据收集是指传感器网络对监测区域进行周期性监测，节点定期生成数据返回给用户。

1 Sink节点固定的数据收集

1.1 基于簇的数据收集

在基于簇的数据收集中，一部分节点将选择性地成为簇首(Cluster head)，负责收集簇内节点传输来的数据，然后直接或多跳地传送给Sink节点；网络中的其他节点则加入离自己最近的簇首，从而形成一种Voronoi结构的网络。

最典型的基于簇的协议是LEACH[1]。在LEACH中，每个节点以一定概率成为簇首，然后网络中的其他节点选择加入离自己最近的簇首以组成簇。所有的簇首和Sink节点会组成一个连通结构。簇首负责收集簇内的数据，然后传送到上一级的簇首或sink节点。显然，簇首的能量耗费要远远大于其他节点。为了均衡节点的能量耗费，每隔一段时间会重新选择担任簇首的节点。

基于簇的协议会遇到如下问题：簇的规模（或最优的簇半径）如何确定、何时更换簇首、簇首的个数为多少、节点的能量如何能消耗均衡从而延长网络生命周期（第一个节点死亡的时间）等。为了能解决如上问题，近年来的工作分别从簇结构的调整、簇首的选择、数据特征的抽取等方面来优化分簇协议。

从簇结构的调整方面来看，传统协议中簇的半径是固定或任意的。文献[2]针对数据收集过程中靠近Sink的那部分节点需要转发大量从远方来的数据从而导致能量消耗过大而过早死亡的问题，提出采用非均匀分簇的方法来均衡不同区域节点的负载。其思想是：靠近Sink节点的位置形成较小的簇，而远离Sink节点的位置形成较大的簇。这样，靠近Sink的那些节点就能节省出能量用于转发远方来数据。

从簇首的选择方面来看，文献[3]为了改变LEACH等传统分簇协议中节点仅根据自身被预设的概率成为簇首从而导致多个临近的节点可能同时成为簇首（造成簇首分布不均）的不足，提出结合节点邻居的状态来决定成为簇首，其中设计了一种新的簇首竞争参数，每个节点vi成为簇首的概率与Ea/Ei成反比，其中Ea是vi邻居的平均剩余能量，Ei是vi的剩余能量。这样能够更好地使能量异构的节点均衡地的消耗能量。

从数据特征的抽取方面来看，文献[4]提出一种利用多项式回归提取数据特征，进而减少数据收集过程中数据传输量的方法。首先，每个节点根据最近几轮中感知到数据的特征，近似出相应的回归函数。然后，传送函数的相关因子和参数到Sink。最后，Sink再通过这些因子和参数还原出原数据。

1.2 基于链的数据收集

基于链的数据收集是将网络中的节点构成一条或若干条链，并在链上选择一个节点作为头节点与Sink节点进行通信，而链两端的数据均沿链传输到头结点。基于链的数据收集的典型工作，按组成链的方式，可以分为单链式协议和多链式协议。

PEGASIS[5]是最早出现的单链式协议，也是基于链的协议中最典型的工作之一。在PEGASIS中，每个节点根据信号的强度判断各个邻居节点与自己的距离。然后，每个节点选择离自己最近的邻居进行通信以减少能量耗费。链中每个节点将轮流成为头节点向Sink节点发送数据，这样可以均衡节点的能量耗费。

由于单链协议中节点组成的链较长，造成数据延迟较大而且头节点负载过重。文献[6]提出一个基于同心圆环的改进PEGASIS协议，该协议是典型的多链式协议。首先，根据各个节点到Sink节点的距离，划分网络为若干个以Sink节点为中心的同心圆环。然后，每个同心圆环内的节点组成一条链，链上选择一个头节点负责接收其他节点的数据并进行完全汇聚。最后，各个头节点再组成一条以Sink节点为头节点的链以传送数据。由于各个同心圆环中节点数量不一定均衡，从而造成各节点能量消耗也不均衡。

1.3 基于树的数据收集

基于树的数据收集是将网络中的所有节点组成一棵生成树，非叶子节点可以执行数据聚合，沿树枝路径把数据发送到根节点。根据构造树的方式及树的典型工作可分为基于线性规划的协议、基于结构增长的协议和基于性能提高的协议。

1.3.1 基于线性规划的协议

文献[7]提出的MLDR是最早出现的工作之一，是一个集中式的算法。MLDR的目标是使网络生命周期最大化，其中网络生命周期定义为网络中第一个节点死亡的时间。它首先将该问题建模为一个节点带有能量限制的最大流问题。然后，利用整数规划来找出一个树的集合，集合中每棵树将被用来收集一次网络中全部节点的数据。

1.3.2 基于结构增长的协议

文献[8]提出了第一个基于结构增长的构造树的算法PEDAP，这是一个以迭代方式来实现的算法。在一个网络中，PEDAP给每条边分配一个代表其两个端点间通信代价(能量耗费)的权值。初始时，树上只有一个Sink节点。然后，在每轮迭代中，PEDAP选择一条权值最小而且有一个端点在树上而另一个端点不在树上的边加入树中。此时，这条边上原先不在树上的端点也被加入树中。因此树上的节点数量增加了一个，即树结构增长了。如此迭代，直至网络中的所有节点被加入树。该算法中的权值只反映了节点间通信代价，并没有考虑节点自身的能量水平，无法做到能量有效。

1.3.3 基于性能提高的协议

文献[9]针对数据收集过程中数据无法进行汇聚的情形，提出一个新的方法来构造树。首先，构造一棵任意的初始树T0。然后，通过逐个改变每个节点的父亲，找到一棵生命周期比T0大的新树T1。接着，通过同样的方法继续寻找生命周期比T1大的树T2。如此迭代，直至无法找到生命周期更大的树。它可以获得Ω(logn/loglogn)的近似率。

2 Sink节点移动的数据收集

在Sink节点移动的数据收集中，由于Sink节点的位置不断变化，因此很难将所有节点组织成一个固定的拓扑结构来向Sink节点传送数据。在这种情况下，只能由Sink节点移动到节点附近收集他们的数据。根据Sink节点采集的数据是否被进行编码处理可分为非数据编码的移动数据收集和基于数据编码的移动数据收集。

2.1 非数据编码的移动数据收集

非数据编码的移动数据收集指节点感知到数据后，如果移动Sink节点路过其附近区域，则将数据直接传送给移动Sink节点。根据移动Sink节点行走的方式又可以分为路径可变的移动数据收集和路径固定的移动数据收集。

2.1.1 路径可变的移动数据收集

对于路径可变的移动数据收集，移动Sink节点出发后将根据网络的状况不断调整自己的路线，以在保证数据采集率的前提下均衡节点的能量消耗。文献[10]提出，移动Sink周期性地从一个固定点出发，在访问完所有节点并采集他们的数据后返回。基本思想是：首先，将该问题形式化为一个混合整数规划并证明它是NP难的。然后，通过求解这个混合整数规划制定移动Sink的路径。该方法的目标是最小化移动Sink行走的路径长度，但数据收集延迟较高。

2.1.2 路径固定的移动数据收集

对于路径固定的移动数据收集，移动Sink的路线是事先确定的，所有节点设法将自己的数据传输到路线附近的节点上以使移动Sink进行接收。文献[11]提出将移动Sink形象化为一个数据骡子(Data mule)，当数据骡子经过某个区域时，区域内的节点可以将数据传送给它。每个节点vi传送数据时必须满足一定的时间约束，即：需要至少ti的时间才能使Sink完全接收到节点的数据。其研究目标是最小化数据收集延迟。首先，将这个问题形式化为一个带位置和时间约束的调度问题(Scheduling problem)。然后，通过求解问题的线性规划方程来调节数据骡子的速度。

2.2 基于数据编码的移动数据收集

基于数据编码的移动数据收集一般是针对无法固定部署Sink节点的网络。为了防止自己死亡后数据的丢失，每个节点将自己的数据发送到网络中一部分节点上进行冗余存储。由于节点的存储容量有限，节点存储数据时必须采取编码的方式，而由于节点的计算能力有限，选择的数据编码方式应具有较低的计算复杂度。当所有节点完成数据分发和存储后，移动Sink节点在任意时刻从任意地点进入网络，只需要访问少量仍然存活的节点就能恢复出全部的数据。

文献[12]是基于LT码的方案，无须地理信息的支持，具有较高的解码性能。基本思想是：当节点产生数据后，将多个数据副本分发到网络中。所有节点在转发数据包时，将根据马尔科夫链理论中的稳态分布(Steady-state distribution)以概率选择下一跳。当一个数据包被转发的次数达到一定程度（由LT码的参数决定）后，将被当前接收到它的节点存储并停止转发。

3 结束语

WSN能量资源有限但应用领域广泛，尽管目前国内外已提出了许多出色的研究方法，但该领域仍然存在许多问题，尤其是在数据收集方面，需要提出更为安全更为高效的数据收集方法。

参考文献：

[1] Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[J].in Proc.of the 33rd Annual Hawaii International Conference on System Sciences,IEEE Computer Society,2000:3005-3014.

[2] 李成法,陈贵海,叶懋,吴杰.一种基于非均匀分簇的无线传感器网络路由协议[J].计算机学报,2007,30(1):27-36.

[3] 刘明,曹建农,陈贵海,等.EADEEG：能量感知的无线传感器网络数据收集协议[J].软件学报,2007,18(5):1092-1109.

[4] Guojun Wang,Jiannong Cao,Huan Wang,Minyi Guo.Polynomial Regression for Data Gathering in Environmental Monitoring Applications[J].in Proc.of IEEE Global Telecommunications Conference(GLOBECOM 2007),2007:1307-1311.

[5] Lindsey S,Raghavendra CS.PEGASIS: Power efficient gathering in sensor information systems[J].in Proc.of the IEEE Aerospace Conference.San Francisco: IEEE Computer Society,2002:1-6.

[6] Sung-Min Jung,Young-Ju Han,Tai-Myoung Chung.The concentric clustering scheme for efficient energy consumption in the PEGASIS[J].in ICACT,2007:260-265.

[7] Konstantinos Kalpakis,Koustuv Dasgupta,Parag Namjoshi.Maximum lifetime data gathering and aggregation in wireless sensor networks[J].in Proc. of IEEE International Conference on Networking, ICC,2002:75-81.

[8] Tan HO,Korpeoglu I.Power efficient data gathering and aggregation in wireless sensor networks[J].SIGMOD Record,2003,32(3):66-71.

[9] Chiranjeeb Buragohain,Divyakant Agrawal,Subhash Suri.Power Aware Routing for Sensor Databases[J].in Proc. of the IEEE 24th Conference on Computer Communications (INFOCOM 2005),2005:1747-1757.

[10] Ming Ma,Yuanyuan Yang.SenCar: An energy-efficient data gathering mechanism for large-scale multihop sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2007,18(10):1476-1488.

[11] Sugihara R,Gupta R K.Optimal speed control of mobile node for data collection in sensor networks[J].IEEE Transactions on Mobile Computing,2010,9(1):127-139.

[12] Yunfeng Lin,Ben Liang,Baochun Li.Data persistence in large-scale sensor networks with decentralized fountain codes[J].in Proc.of the IEEE 26th Conference on Computer Communications (INFOCOM 2007),2007:1658-1666.