WSN中一种基于多sink的快速数据收集算法

郑凯津

ZHENG Kaijin

天津市信息中心，天津 300201

1 引言

综合了无线通信技术、传感器技术、嵌入式计算技术和分布式信息处理技术的无线传感器网络（Wireless Sensor Network，WSN），是目前国际上前沿热点的研究领域。传感器节点能够协作地实时监测、感知网络区域内各种信息，然后以多跳的方式将这些信息传送给远方的基站（Sink）[1]。无线传感器网络在工作过程中，节点会不断地感知到周边环境的数据。而在无线传感器网络任何一个应用中，用户都需要获取相应的数据进行处理。采集网络中用户需要的数据，就被称为数据收集[2]。数据收集是无线传感器网络中最重要的操作之一，能否有效地采集到合适的数据，直接关系到应用的效果。为了使网络能长时间地工作，在进行数据收集时必须有效地降低节点能耗以保存能量。此外，网络还需要提供延迟保证和容错性等能力以满足用户的需要。但是，受到节点有限的性能以及网络动态性等因素的影响，目前已有的数据收集协议还无法有效应用。因此，对网络中的数据收集协议进行研究，具有重要的理论意义和应用价值。

2 相关工作

数据收集问题一直是WSN中的一大研究热点。相继有众多的学者提出了一系列方法用于无线传感网中数据收集的方法[3-13]，如潘文虎等[3]提出一种改进的MWSF算法。该算法结合A*算法求解出移动Sink在传感器节点之间移动的最短路径，利用MWSF算法找到移动Sink所需访问的下一个传感器节点，并与单跳通信范围内的其他传感器节点进行通信，从而收集数据。仿真结果表明，该算法能降低数据溢出发生率，提高网络的数据传输效率；袁凌云等[4]针对无线传感器网络应用于突发事件监测场景的能量消耗和网络延迟问题，提出了基于移动Agent的无线传感器网络簇式数据收集算法。该算法基于事件严重程度来动态成簇，并由其决定簇的生命周期和覆盖范围。Sink和簇头之间形成以Sink节点为簇头的虚拟簇，提出了基于移动Agent迁移路径规划来完成对所有簇内成员节点信息的收集。仿真结果表明，相对于C/S数据收集模型，该算法具有更好的节能效果，并能一定程度地减少网络延迟，尤其适用于大规模无线传感器网络应用；闫宇博等[5]针对不可靠低轮值无线传感器网络所具有的特性，综合考虑了不可靠链路和低轮值的影响，给出了纠删编码在多条路径上的分配策略，从而在保证能量效率和较高递交率的前提下极大地减少了递交时延。仿真分析表明提出的算法以递交率轻微降低的代价获取了递交时延的显著下降。

另外，陈涛等[6]针对传统的无线传感器网络数据收集协议大多受制于发生在基站周围的热点问题，提出了一种使用移动基站的数据收集方法。将数据收集问题转化为支配集构造和旅行商问题，并提出了一种分布式的支配集构建算法，结合旅行商问题的近似算法生成基站的移动路线。仿真结果表明，所提出的方法减少了通信消耗，且能使负载均衡地分布；为了在无线传感器网络中降低能耗和最大化网络生存期，杨靖等[7]提出一种能量高效的数据收集算法。该算法利用移动代理模型在网络中进行数据收集。首先，根据监测精度的要求控制活动节点的数量；然后，通过求最小支配集得到具体的工作节点；最后，利用蚁群算法规划移动代理迁移的最优路线，移动代理以渐进方式收集活动节点的监测数据。仿真结果表明，与典型算法相比，该算法具有更低的能耗和更长的网络生存期。本文在现有工作的基础上，针对时间响应和数据准确度要求高的应用，提出了一种快速数据收集方法，并通过仿真实验验证了本文方法的有效性。

3 系统模型

本文研究的无线传感器网络数据收集问题限定于以下假设：

（1）无线传感器网络具有多个sink节点，节点部署后不再移动，在多sink节点的无线传感器网络中有n个普通节点，有k个基站节点，网络划分为l个子网格。网络中任意两个sink节点之间可以互相直接通信，任意一个节点可以与其邻居节点互相直接通信。每个节点在某一个时刻可以接收或发送数据，并且在同一个时刻只能接收到一个邻居节点的消息，如果同一时刻两个邻居节点同时发送，将容易造成冲突。网络模型如图1所示。

图1 WSN网络结构示意图

（2）无线传感器网络的拓扑结构通过一个有向图G={V，S，E}来表示。其中V代表l个网格组成的集合，S代表k个sink节点的集合，E⊆V×(V+S)代表边的集合，边eij=1表示网格Ci和网格Cj相邻可以直接进行通信，亦表明网格Ci中存在节点是网格Cj中节点的通信邻居，反之eij=0。假设任意两个网格i和 j之间的通信关系具有对称性，即eij=eji。定义A为图G的邻接矩阵。该矩阵表示为下面的形式，该矩阵分为A1和A2两部分，A1代表网格区域之间通信关系，A2代表网格与sink节点的通信关系。每个网格i对应的度D(i)代表该网格的邻居网格数目。N(i)代表该网格内节点数。相邻通信网格之间的通信时间为τ。相邻节点之间通信时间为t。数据收集响应时间为ω。

（3）无线传感器网络中任意节点i的能耗可以表示为：Ei=Ei-MCU+Ei-TCR+Ei-SB。其中Ei-MCU表示节点i上微控制单元的能耗；Ei-SB表示节点i上中央处理器的计算能耗；Ei-TCR则表示节点i收发数据的通信能耗。Ei-TCR可以进一步表示为：Ei-TCR=Ei-TCR-RX+Ei-TCR-TX(di)。其中Ei-TCR-RX表示节点i接收数据的能耗；Ei-TCR-TX(di)表示节点i发送数据的能耗，它是一个关于距离di的函数，节点i发送的数据与接收节点的距离越大，能耗也越大。基于以上分析，对于一个拥有N个节点的传感器网络的总能耗可以表示为：

其中C1为常数，假设网络中节点传输的路径衰减因子为2，则有：

其中Ei-TCR-EC和Ei-TCR-PA分别表示节点i发送数据时的电子电路和功率放大所导致的能量消耗，它们是一个常数。因此，公式（2）可以表示为：

其中，C2和C3为常数。

4 快速数据收集算法

本文提出的快速数据收集算法（QDGA）是一种分层集中式与局部自适应相结合的方法。首先充分利用sink节点的无需考虑能量消耗，并且通信能力和计算能力强的特点，集中式计算出全局最优的粗粒度并行数据收集策略。同时为了使得数据收集的算法不受节点失效、局部通信链路失效的影响，在并行数据收集任务分发和数据收集过程中，有效利用局部信息进行自适应的调整，从而有效避免单个节点失效时数据收集失败。一个数据收集任务进行计算后从全局可以看成是一个基于网格的收集森林{T1，T2，…}，每个序列Ti代表了一条数据收集的分支树，根节点为sink节点。而网格内部数据收集任务由根据网格内部的节点发起网格内进行响应的数据收集。本文中涉及的是所有监测区域的融合数据收集，原始数据收集在以后的工作中进一步研究。

QDGA算法分成两个阶段：

（1）sink节点计算数据收集策略阶段。sink节点接收到一个数据收集命令时，在保证数据收集的准确性和完整性的前提下，尽可能地利用所有sink节点，计算出符合并行收集数据要求的策略，以加快数据收集的效率。在该阶段的数据收集策略基于sink节点对全局网格信息进行最优分配，即该数据收集策略是基于网格粒度的。

（2）任务分发与数据收集阶段。此过程中各个网格接收到相应数据收集子任务，并可根据自身的局部信息进行网格内的数据收集，动态调整数据收集路径。该阶段主要是利用局部信息有效避免节点失效引发的空洞等问题。

4.1 基站集中式计算阶段

网络中存在多个sink节点，数据收集任务可以划分成若干个子任务，然后分发给各个sink节点进行并行处理。首先是接收到收集任务的sink节点利用全局的信息构建基于网格粒度的收集森林，森林的构建遵循最小度的BFS算法。整个森林构建过程时间复杂度为O(m)。

算法1网格粒度数据收集森林构造算法

输入 数据收集任务Q和网络的连接矩阵A。

输出 收集森林 F={T1，T2，…}，每个Ti代表一棵以sink节点为根节点的网格粒度收集树

（1）根据查询条件构造出包含数据收集区域的网格集合SetI，收集范围为整个网络SetI=V

（2）构造数据收集森林

（3）全局分析

4.2 任务分发和数据收集阶段

各个sink节点接收到以自己为根节点数据收集树后进行收集任务的分发。该树既可以作为数据收集任务下发的基础也可以作为数据收集返回的基础。

各个网格收到了相应的分发任务就会根据消息进行收集任务的分发，分发完成之后再进行自己网格内的数据收集。在整个数据收集任务下发过程中要经过LEVEL层，LEVEL不会超过ln(m)，而每个网格的子网格的度不超过max(d(i))，因此下发的时间复杂度是O(ln(m)×max(d(i)))。数据收集任务分发伪代码描述见算法2。

算法2收集任务分发算法

当数据收集结果返回时，各个网格会收到孩子网格的融合数据结果，并进一步进行合并返回给父亲网格，最终返回给sink节点。这个过程中的时间消耗与任务分发的时间消耗也是O(ln(m)×max(d(i)))。

算法3网格间数据收集算法

当收集任务分发下去之后，将进行自己网格内部的数据收集。进行网格内数据收集时，每个网格中的节点数目相对较少，网格内的节点可以相对实时地保存网格内的节点信息和相应的邻居信息，并可以根据局部的网络结构优化选择相应的时隙分配。发起网格内数据收集的节点，可以在以自己为根节点的BFS树的基础上，通过多信道时隙分配来进行网格内数据收集。网格内的节点数据收集时隙分配伪代码描述见算法4。

算法4网格内数据收集算法

算法结束后，标记的最大值则为网格内数据收集最多时隙。各个节点按照时隙分配进行数据发送。网格内的数据收集时隙数目不会超过网格内的节点数目。时间消耗最多为O(N(i))。

在数据收集任务下发和数据收集的过程中，每个网格内的所有节点均能收到下行网格和上行网格的代表节点发送过来的任务消息和数据消息。只要网格内还存在未失效的节点，则不会影响该网格的数据收集的分发和收集执行。可以看出利用节点的冗余保证了数据收集处理不易受节点失效的影响。同时在这个过程中，如果按照原有方式出现了突发的空洞或者链路失效的问题，任务下发和数据返回可以自适应调整发送路径。数据收集的路径可以在收集过程中自适应生成，能有效地消除通信链路失效和节点移动的影响。并且在数据回收过程中保存了数据回收路径，当最终返回到sink节点时这些信息可以为sink节点对基于网格的全局网络结构维护提供依据，限于篇幅，该部分的内容在本文中不再阐述。

5 仿真实验与分析

5.1 实验设计

实验场景如下：N个传感器节点被随机分布M大小的监测区域内，N的个数在50到350之间取值；M的大小为（125 m，125 m）～（300 m，300 m）。节点间的同步通过物理层和数据链路层来实现。实验参数设置为：每个节点的初始能量为50 J；节点接收和发送单位数据的能耗都为50×10-6J/bit；节点上收发电路的能耗为50×10-6J/bit；节点成功发送一位数据通过1 m距离的能耗为100×10-9J/bit/m2；节点上计算能耗为 5×10-6J/bit；每个数据包的长度为1 024 bit；每个控制包的长度为64 bit，如表1所示。网络的生命周期被定义为一个节点在耗光自身的能量前，已经进行的数据收集轮数。

表1 实验参数

另外，本文使用数据收集延迟来评价数据收集的效率。定义网络的通信距离为：

其中，ui的取值为0或1，ui=1表示节点i是簇头，ui=0表示节点i是簇成员；di_B表示簇头与基站之间的距离；cij的取值为0或1，cij=1表示节点i和节点 j之间存在数据链路，反之则不存在；dij表示节点i和节点 j之间的地理距离，h表示路径衰减因子，在模拟中取值h=2。网络中所有节点通信距离越短，则数据收集延迟越低。

5.2 实验结果

为了测试本文提出方案的性能，以Matlab2009为工具进行了仿真实验，将本文提出的快速数据收集算法QDGA与目前较为典型的MLD[7]方案和EEDGA[14]方案进行了对比。分别做了两组实验，实验结果取50次模拟的平均值。

第一组实验：在传感器节点个数固定为100个，监测区域大小M可变情况下的数据收集延迟和网络生命周期比较。

图2给出了不同M值下的数据收集的延迟比较结果。从中可以看到，随着网络监测区域的增加，不同方案的数据收集延迟都呈现增加的趋势，从（125 m，125 m）到（300 m，300 m），EEDGA、MLD和QDGA的延迟分别增加了22.1 s，17.6 s，10.8 s。其中QDGA的延迟最低，相比于EEDGA和MLD，QDGA的总延迟分别降低了24.8%和15.5%。这主要是因为，在EEDGA中节点的数据包是逐跳传输的，随着M的增大，当传输链路中的某一跳出现丢包现象或节点意外死亡时，在保证数据收集质量的前提下，会对整个网络的传输延迟产生极大影响；而MLD通过建立最小生成树的方式来为节点的数据包找到合适的传输路径，在一定程度上降低了延迟，取得了比EEDGA更好的性能。而QDGA则将数据收集任务划分成若干个并行任务，通过利用多个sink节点来构造具有最小度的网格粒度数据收集森林，从而加速了数据收集过程。

图2 不同M下的数据收集延迟比较

图3给出了不同M值下的数据收集的网络生命周期比较结果。从中可以看到，随着网络监测区域的增加，不同方案的网络生命周期都呈现下降的趋势，从（125 m，125 m）到（300 m，300 m），EEDGA、MLD 和QDGA的生命周期分别下降了133轮、120轮和98轮。其中QDGA的表现要优于EEDGA和MLD。这主要是因为，EEDGA方案没有考虑到监测区域大小变化对于节点间数据通信质量的影响，随着M的增加，EEDGA需要额外消耗极大的能量来保证数据收集的可靠性，从而影响了网络的寿命；而MLD方案在网络规模不断增大的情况下，如果传感器节点的分布不统一或者不均匀，则构建最大生命周期树的难度会呈指数级增加，从而极大消耗了节点的能量。

图3 不同M下的数据收集网络生命周期比较

第二组实验：在监测区域大小M固定为（150 m，150 m），传感器节点个数从50个增加到350个的数据收集延迟和网络生命周期比较。

图4给出了不同节点个数下的数据收集的延迟比较结果。从中可以看到，随着传感器节点个数的增加，不同方案的数据收集延迟都呈现增加的趋势，从（125 m，125 m）到（300 m，300 m），QDGA的数据收集延迟始终要低于EEDGA和MLD。仔细分析其原因可知，这主要是因为，EEDGA中的节点通过仅仅和距离它最近的邻居建立连接来降低总的通信距离，这种策略仅当网络中节点个数较少时是有效的；MLD则在建模时考虑了节点个数可变情况下的收集延迟，通过可靠路径选择来规避节点个数增加所导致的收集延迟增大问题；而QDGA基于多sink节点对监测区域进行网格粒度的划分，避免了数据收集过程随着传感器节点个数增加而导致的多跳传输。另外，QDGA可以相对实时地保存网格内的节点信息和相应地邻居信息，并通过多信道时隙的最优分配来进行网格内数据收集，因此数据收集延迟相对较低，取得了比其他两种方法更好的性能。

图4 不同节点个数下的数据收集延迟比较

图5给出了不同节点个数下的数据收集的网络生命周期比较结果。可以看到，QDGA的生命周期要长于EEDGA和MLD。仔细分析其原因可知，这是由于EEDGA首先通过求最小支配集来确定工作节点的个数，这是一个k覆盖问题，在大规模传感器网络中的求解复杂度高，另外采用蚁群算法来规划数据收集的路线，算法的迭代次数过多，以上的操作都给节点造成了较大的能量开销；而MLD通过迭代地降低瓶颈节点的负载来延长网络生命周期，该问题是NP难问题，另外该算法的性能受到网络初始拓扑的影响也较大。总的来说，相比于EEDGA和MLD而言，QDGA在数据收集应用中更为有效。另外随着节点数目的增加，QDGA的表现更为稳定，不会出现生命周期大幅降低的情况。

图5 不同节点个数下的数据收集网络生命周期比较

6 结论和未来工作

本文针对时间响应和数据准确度要求高的应用，提出了一种快速数据收集算法。该算法中基站节点利用自己已知的全局信息和计算能力计算出数据收集网格粒度最优的数据收集策略。网格内的普通节点可以根据自己的邻居信息进行网格内的数据收集和计算，通过实验表明该方法相对非并行处理的数据收集策略在保证网络生命周期的前提下，能够减少时间延迟以及提高数据收集的准确率。实验结果验证了本文算法的有效性。下一步研究工作的重点在于：（1）基于压缩感知理论，研究无线传感网中的数据收集可靠性问题；（2）基于压缩感知理论，研究无线传感网中的数据融合时间选择问题。

[1]梁俊斌.无线传感网中低能耗数据收集协议研究[D].长沙：中南大学，2010.

[2]朱永利，于永华，李丽芬.数据收集传感器网络的多模层次网络构建[J].计算机工程，2011，37（2）：111-113.

[3]潘文虎，张瑞华.WSN中基于移动sink的高效数据收集算法[J].计算机工程，2011，37（18）：94-96.

[4]袁凌云，王兴超，徐天伟.基于移动Agent和WSN的突发事件场景数据收集算法研究[J].电子与信息学报，2010，32（8）：1974-1979.

[5]闫宇博，杨盘隆，张磊.基于低轮值不可靠无线传感器网络的数据收集加速机制研究[J].计算机研究与发展，2010，47（z2）：121-127.

[6]陈涛，郭得科，罗雪山，等.一种基于移动基站的无线传感器网络数据收集方法[J].国防科技大学学报，2011，33（2）：49-53.

[7]杨靖，徐迈，赵伟，等.传感器网络中一种能量高效的数据收集算法[J].系统工程与电子技术，2011，33（3）：650-653.

[8]Kuhn H W.The Hungarian method for the assignment problem[J].Naval Res Logistics，2005，52（1）：7-21.

[9]李燕君，叶敬川，朱艺华.能量感知的传感器网络分布式时空相关数据收集方案[J].北京邮电大学学报，2011，34（53）：110-114.

[10]张龙妹，史浩山，杨俊刚，等.一种适用于WMSNs的多信道快速数据收集算法[J].西北工业大学学报，2011，29（3）：380-383.

[11]奎晓燕，张士庚，王建新.DSCAU：非均衡负载无线传感器网络的基于支配集的分簇数据收集算法[J].高技术通讯，2012，22（9）：918-924.

[12]Cheng Jie，Jiang Hongbo，Ma Xiaoqiang，et al.Efficient data collection with sampling in WSNs：making use of matrix completion techniques[C]//Global Telecommunications Conference（GLOBECOM 2010），2010：1-5.

[13]Chou Chun Tung，Rana R，Hu Wen.Energy efficient information collection in wireless sensor networks using adaptive compressive sensing[C]//2009 IEEE 34th Conference on Local Computer Networks（LCN2009），2009：443-450.

[14]Wu Yan，Fahmy S.On the construction of a maximumlifetime data gathering tree in sensor networks：NP-completeness and approximation algorithm[C]//Proc of The IEEE 27th Conference on Computer Communications（INFOCOM2008），2008：356-360.