无线传感器网络中一种基于移动Sink的数据收集算法*

张 蕾，张 堃，宋 军

(北京建筑工程学院计算机教学与网络信息部，北京 100044)

随着物联网技术、嵌入式技术以及低功耗的无线通信技术的发展，生产具备感应、无线通信以及信息处理能力的微型无线传感器已成为可能，这些廉价的、低功耗的传感器节点共同组织成无线传感器网络WSNs(Wireless Sensor Networks)，通过节点间的相互协作，将其监测和感应到的信息(温度、湿度等)传送到基站(Sink)，实现网络数据收集功能。利用WSN进行数据收集可以应用到许多重要领域，如国防军事、环境监测、交通管理、医疗卫生、抗震救灾等［1］。

静态无线传感器网络的研究，前提都是假设节点保持不动。但近年来提出的移动无线传感器网络mWSN(mobile WSN)概念，是针对某些实际应用中无线传感器节点的移动是不可避免的，例如:监测野生动物生活习惯、追踪医院病人心跳情况［2－3］；还有交通指挥中心根据安装在汽车上的传感器节点来获知、分析和处理这一地区的交通流量，进而发布实时有效的交通调度信息等。

数据收集是WSN研究的重点。随着近年mWSN成为学术界的研究热点，原来针对静态无线传感器网络的数据收集协议由于网络中的传感器节点或Sink节点的移动引起的网络拓扑变化、路径失效等问题，已经不能应用到mWSN。因此针对mWSN的数据收集协议的研究在国内外得到了广泛的重视。

本文从mWSN数据收集角度出发，基于分簇技术，利用移动Sink来解决多跳路由通信中的“热区”问题，延长了网络的生存期。

1 mWSN网络体系结构

在进行网络部署时，采取确定性部署与随机部署相结合的特点，网络中的移动传感器节点是随机部署，与此同时根据应用的需要部署一定数目的固定参考节点，这样既能较好地适应网络动态拓扑变化，又能构建较为稳定的网络拓扑，达到节省能耗的目的。mWSN网络层状结构如图1所示。将网络分成固定数量、大小均匀的簇，每一个簇内有一个参考固定节点，一个簇头节点(Cluster)和多个簇内成员节点。底层是簇内节点与Cluster的通信，上层是固定节点之间的通信。

图1 移动无线传感器网络的层状结构图

图2为mWSN网络结构示意图，n个传感器节点部署在一个监测区域，根据应用的需要，除了在正方形网格上部署m个固定节点外，还在监测区域随机均匀部署n－m个移动节点。其中的每一个固定节点坐标位置可知，移动节点的位置不可知，Cluster是通过分簇算法从移动节点中选出的。

图2 mWSN网络结构示意图

WSN中的节点通过分簇算法被划分成不同的簇，每个簇的形成都是由一个固定节点作为参考的，所以每一个簇由某个固定节点、一个Cluster和多个簇内成员节点组成，所有固定节点形成以Sink为根的一颗路由汇集树［4－5］。图3 描述了分簇网络中的数据流［6］。

图3 mWSN簇－树结构示意图

在图3所示的簇－树拓扑结构中，成员节点将数据发送给各自的Cluster，Cluster将数据融合后发送给对应的固定节点，再经由其它的中间固定节点路由发送到Sink。由于节点的移动性和Cluster负责簇内的通信调度，相对簇内成员节点，Cluster将消耗更多的能量。因此，网络将定期地重新进行分簇，选择能量较高的且距离固定节点最近的移动节点担任Cluster，从而将所有负载均匀地分布到所有节点。该簇－树拓扑结构既能实现高效节能，又能降低数据包碰撞的几率，使得整个mWSN有较好的数据吞吐量［7］。

2 基于移动Sink的数据收集协议

本文主要研究在基于分簇技术的mWSN数据收集协议中使用移动Sink解决多跳路由通信中的“热区”问题。

2.1 移动 Sink

mWSN中有节点移动和Sink移动。Sink移动可以延长网络的生命周期，因为在一个部署固定Sink的WSN中，在数据收集过程中，Sink周围的一跳节点会以更快的速度消耗完自己的能量。而在Sink移动的mWSN中，由于Sink的移动，其周围的一跳节点在不断变换，所以在多跳路由通信中，能使网络中所有节点的能量消耗处在一个平均水平，显著延长网络的寿命，避免因多跳路由而出现能量空洞的“热区”。

很多人已经认识到利用移动Sink来延长传感器网络生命周期的潜在好处。由于在不同时刻，多跳路由会随时间、Sink位置而改变，因此，对于Sink移动问题，具有一定的理论难度。Yi等人在文献［8］中，提出了一种移动Sink最佳运动理论。

美国Berkeley大学 S.R.Madden等在文献［9］中将WSN分为事件驱动和连续监测两种类型。在事件驱动类型的WSN应用中，如果网络中的Sink是可移动的，那么Sink向事件感知区域移动就能减少中转节点的数量，从而降低能量开销。

EARM［10］假设节点的发射功率可以调整，如果Sink距离路径最后一跳节点的距离越来越远，那么该节点不断增大自己的发射功率来保持和Sink的连接，当距离远到即使节点以最大发射功率也不能满足维持连接的时候，移动Sink寻找一个新的邻居节点，这个过程不断持续下去。

分布式动态共享树协议DST(Distributed Dynamic Shared Tree)［11］是一个在Sink高速移动的环境下，高效率、低时延的数据融合协议。DST采用基于Sink的生成树方法，根据Sink的移动轨迹，很好地保持与Sink的通信，解决了过度的能量消耗和Sink位置更新消息的协议中增加的碰撞等问题。

2.2 MSDG算法的基本思想

本文提出一种基于移动Sink的数据收集协议MSDG(Mobile Sink-based Data Gathering)。当 Sink收集数据时，直接向自己的邻居固定节点发起数据查询请求报文；经分簇后，Sink根据移动轨迹沿途以最近的固定节点作为根节点动态构建由固定节点组成的路由树；各个移动节点感知的数据经Cluster进行数据融合计算，然后将融合后的数据沿路由树反向逐跳转发给Sink节点。

2.3 MSDG算法实现的主要步骤

MSDG算法的主要实现步骤归纳如下:

(1)分布式分簇算法开始，每个固定节点发送Fixednode_Msg报文，移动节点接受Fixednode_Msg报文并计算与周围固定节点的距离，选择距离最近的作为参考固定节点；持续时间为Tc。

(2)形成簇，选择Cluster，进行簇内k个节点优化调度；持续时间为TH。

(3)Sink给距离最近的固定节点发送Sink_Msg报文广播，相邻的固定节点收到广播后，若是第一次收到，则将发送者作为父节点，对固定节点进行时隙划分。然后继续向邻居固定节点转发Sink_Msg报文直到源数据结束到构造树的叶子节点。持续时间为Tt。

(4)簇内通信。簇内工作节点根据TDMA时隙划分策略顺序将感知数据Data_Msg传输给Cluster。Cluster将其存储在缓冲区内进行数据融合处理后，更新Data_Msg的data内容，将ID统一换成Cluster的ID，再把融合后的Data_Msg转发给相应的参考固定节点。持续时间为Tdl。

(5)簇间通信。固定节点将数据沿路由树反向多跳路由到Sink节点。持续时间为Td2。

与文献［12］中的数据收集协议一样，本文提出的MSDG算法由Sink启动，Sink采用泛洪广播Init_Msg消息，内容包括 Tc，TH，Tt和 Td以及时间同步指令，进而触发网络的分簇进程。

3 仿真与结果

本节对 MSDG 与 LEACH［13－14］、ACE-L［15］进行仿真比较。

LEACH(Low Energy Adaptive Clustering Hierarchy)是典型的簇型数据收集协议，它将整个WSN划分为多个逻辑上的簇，通过随机的方式选举Cluster，Cluster负责调度簇内所有节点的数据传输，并将簇内节点监测到的数据进行数据融合后，再传送给Sink。LEACH的基本思想是通过随机循环地选择Cluster，从而将整个网络的能量负载平均分配到每个传感器节点中，达到降低网络能源消耗、提高网络整体生存时间的目的。但Cluster分布不均匀，Cluster和Sink单跳通信，对Cluster通信能力能耗要求比较高，分簇协议的性能依赖网络结构、系统模型和应用场景。

ACE-L(Location-Based Algorithm for Cluster Establishment)是一种具有良好反馈机制的自适应分布式成簇算法。簇的形成包括簇的产生和簇的迁移两个逻辑部分。基于相邻节点之间的信息反馈，每个节点独立运行ACE-L，最终由两个逻辑部分交叉迭代形成簇。ACE-L具有良好的健壮性，对节点失效和报文丢失反应迅速，生成的簇能有效减少相互之间的重叠，降低簇间通信干扰的概率，并且成簇收敛速度与网络规模无关，簇的分布均匀，性能优于LEACH，但是没有考虑节点移动快慢等因素，节点的通信半径限制了该算法只能适用于小范围数据收集的WSN。

WSN中衡量数据收集协议性能的一个主要指标是网络的生命周期，网络的生命周期用网络生存节点数与网络运行轮数的关系表述。本文采用与文献［12］相同的无线传感器网络能量耗费模型。

式(1)为发射k比特数据耗损的能量ETx的计算公式，由发射电路耗损和功率放大耗损两部分构成。功率放大耗损则根据发送者和接收者之间的距离分别采用自由空间模型和多路径衰减模型，Eelec为发射电路的耗损能量，εfs为自由空间信道模型下功率放大所需能量、εmp为多路径衰减信道模型下功率放大所需能量。

式(2)为接收k比特数据的能量耗损ERx的计算公式，仅由电路耗损引起。

实验中，监视区域要求100%被覆盖(即簇内所有节点都为活动节点)。实验中未考虑紧急数据的处理。实验结果均为100次独立实验结果的均值，每次独立实验都采用不同的随机拓扑。取上式中参数为:Eelec=50 nJ/bit，εmp=0.0013 pJ/(bit·m4)，εfs=13 pJ/(bit·m2)，d=85 m。此外，对数据信号进行融合等处理时也将耗损能量，由Efusion表示融合单个数据信号所耗损的能量。对于任一Cluster，假设其簇内成员节点数为q，则将q个成员节点的数据信号和自身的数据信号融合为一个有效信号耗费的能量为Ecomp=(q+1)·Efusion·k。仿真实验参数见表1。

表1 实验参数

(1)移动Sink与静止Sink的对比分析

将MSDG与LEACH进行比较，LEACH中Sink静止不动，而MSDG中的Sink是可移动的。

图4表明，MSDG中节点的能耗大约只有保持静止情况下的一半，延长了网络生命周期。

图4 节点能耗比较

(2)节点死亡数量与时间的关系

图5是LEACH、ACE-L和MSDG 3种数据收集算法的网络生存期比较图。可以看出，MSDG的节点生存时间相对LEACH、ACE-L都有显著提高，网络生存期得以延长。

图5 3种算法网络生命周期比较

4 总结

本文提出了基于移动Sink的数据收集协议MSDG，Sink沿途以最近的固定节点作为根节点动态构建由固定节点组成的路由树，Cluster收集簇内所有普通节点的数据后做数据融合计算，将融合后的数据沿路由树反向传给Sink。仿真显示MSDG在节点的平均能耗和网络生存时间等方面的性能远超过LEACH、ACE-L等算法。

［1］李虹.无线传感器网络中节能相关若干关键问题研究［D］.中国科学技术大学，2007:7－8.

［2］赵泽，崔莉.一种基于无线传感器网络的远程医疗监护系统［J］.信息与控制，2006，35(2):265－269.

［3］杨靖，洪露，李泽滔，等.无线传感器网络中一种高能效数据收集协议［J］.传感技术学报，2011，24(5):742－746.

［4］李晓维，徐勇军，任丰原.无线传感器网络技术［M］.北京理工大学出版社，2007:8.

［5］李善仓，张克旺.无线传感器网络原理与应用［M］.北京:机械工业出版社，2008:3.

［6］Ossama Younis，Marwan Krunz，Srinivasan Ramasubramanian，et al.Node Clustering in Wireless Sensor Networks:Recent Developments and Deployment Challenges［J］.IEEE Network，June，2006.

［7］Tri Pham，Eun Jik Kim，Melody Moh.On Data Aggregation Quality and Energy Efficiency of Wireless Sensor Network Protocols-Extended Summary［C］//First International Conference on Broadband Networks.2004.730－732.

［8］Yi Shi Y.Thomas Hou.Theoretical Results on Base Station Movement Problem for Sensor Network［C］//The IEEE INFOCOM 2008 Proceedings.

［9］Luo J，Panchard J，Piorkowski M，et al.Mobi-Route:Routing towards a Mobile Sink for Improving Lifetime in Sensor Networks［C］//Proc.of the Int’l Conf on Distributed Computing in Sensor Systems，2006.

［10］Ye F，Zhong G，Lu S，et al.GRAdient Broadcast:A Robust Data Delivery Protocol for Large Scale Sensor Networks［J］.ACM Wireless Networks(WINET)，2005，11(2): － .

［11］KWang-il Hwang，Jeong Sik In，Doo-seop Eom.Distributed Dynamic Shared Tree for Minimum Energy Data Aggregation of Multiple Mobile Sinks in Wireless Sensor Networks［C］//EWSN O6，LNCS 3868，2006:132－147.

［12］徐建波.无线传感器网络分布式分簇和节能的数据收集协议研究［D］.长沙:湖南大学，2008.

［13］Wendi Rabiner Heinzelman，Anantha Chandrakasan，Hari Balakrishnan.Energy-Efficient Communication Protocol for Wireless Micro-Sensor Networks［C］//Proceedings of the 33rd Hawaii International Conference on System Sciences，2000.3005－3014.

［14］李成岳，申铉京，陈海鹏，等.无线传感器网络中LEACH路由算法的研究与改进［J］.传感技术学报，2010，23(8):1163－1167.

［15］Chuan-Ming Liu，Chuan-Hsiu Lee，Li-Chun Wang.Distributed Clustering Algorithms for Data-Gathering in Wireless Mobile Sensor Networks［J］.Journal of Parallel and Distributed Computing，2007，67(11):1187－1200.