基于事件触发的无线传感器网络动态分簇＊

裴晓黎 刘志坤 刘 忠

（1.海军装备部驻上海地区军事代表局 上海 200083）（2.海军工程大学电子工程学院 武汉 430033）

1 引言

无线传感器网络已在民用、军事领域得到了广泛的应用，能量问题是制约其正常运行的一个瓶颈：其单个节点能量有限，且难以进行能量补充。分簇协议把网络节点划分为多个簇，每个簇包含一个簇头（cluster head）节点和多个簇成员（cluster member）节点，簇内节点间的通信由簇头控制。合理的分簇协议可以有效地平衡节点的能量消耗，延长网络的生存周期［1］。

簇组织可分为两类：静态簇和动态簇。其中静态簇在完成组建后其结构不再发生改变，具有组建方法简单的优点，但是适应性较差。而动态簇由目标事件激发组建，其位置和规模由事件的具体状态决定，因此具有很好的适应性和生存能力，其组建方法相应的也比较复杂。动态簇的这种特点，使其特别适用于目标定位跟踪等领域［2～3］。目前，相对于在静态分簇协议方面的大量研究成果［4～5］，对于动态分簇的研究显得相对较少。文献［6］给出了一种基于目标预测位置的动态簇组建方法，该方法强烈依赖于预测精度，容易出现目标丢失的情况。文献［7］介绍了一种多层动态簇的组建方法，但是该方法管理代价较大。文献［8］给出了一种基于Voronoi图的动态分簇算法，其计算程度复杂且簇头选择方式不尽合理。文献［9］提出的方法在簇头选择时综合考虑了接收信号强度和节点剩余能量两项因素，但是没有考虑到簇头与汇聚节点的距离，并且对簇的规模没有做约束。

本文在文献［9］的基础上，提出了一种新的动态分簇协议，在簇头选择时增加了簇头与汇聚节点距离这一因素，同时给出了簇规模的限定方法，仿真结果表明，该协议能够有效地节省能量，延长网络寿命。

2 模型及问题描述

2.1 网络模型

本文提出的动态分簇协议针对的网络模型如下：

1）除汇聚节点外，节点属于同构节点，具有相同的初始能量、信息处理能力、探测半径和通信半径，并且通信半径远大于探测半径；

2）发射功率在允许范围内可调；

3）节点的位置固定，其自身的位置信息已知，可以通过GPS设备或者节点自定位算法［10］获得，本文不讨论WSN节点自定位问题；

4）汇聚节点唯一且位置固定，各网络节点到汇聚节点的距离已知，可以通过节点与汇聚节点的信息交换获取。

2.2 能量模型

节点的能量消耗主要用于数据收发和处理。文献［13］指出，对于服从四次方衰减的无线电，在100m距离上传输1kb数据所消耗的能量大致相当于在100MIPS／W处理器上执行300万个指令，即节点的数据处理能耗要远小于数据收发能耗，基于此结论，本文主要考虑数据收发的能耗。

按照时间顺序对簇头和簇成员的能耗进行分析：

簇成员的能量消耗可分为：在构建簇时，接收簇头当选信息；簇构建完成后，向簇头节点发送目标的相关信息；簇寿命结束时，接收簇重组信息。

簇头的能量消耗可分为：在构建簇时，接收前一簇头发出的簇重组信息，向簇成员发送当选信息；簇构建完成后，接收簇成员的目标信息，进行数据处理估计目标状态，将数据处理结果发送给汇聚节点；簇寿命结束时，发送簇重组信息。

本文采用无线通信模型，根据传输距离门限，分别采用自然空间模型和多径衰落模型，传感器节点发送kbit数据传输dm距离消耗的能量Etx为［14］：

传感器节点接收kbit数据所需要的能量ERx为

其中，Eelec是发送电路和接收电路的能量消耗；εfs和εmp分别是自由空间模型和多径衰减模型中功率放大器的能量消耗，d0是传输距离门限，决定了衰减模式。

2.3 信号衰减模型

采用文献［15］的目标信号衰减模型：假定目标的信号强度随距离成指数衰减，节点i在t时刻接收到的信号强度Si（t）为

其中，S表示目标源的信号强度；ri（t）是t时刻目标到节点i的距离；α是信号强度的衰减指数，一般取值为2；ni是测量噪声。

2.4 问题描述

合理的动态分簇协议应该遵循以下原则：

1）节点采集到的信号强度较大。较强的信号说明该节点距离目标较近，获得的信息更可靠，数据处理更准确；

2）节点的剩余能量较多。因为簇头节点要担负更多的管理和通信任务，消耗的能量也相应的更多，如果当选的簇头节点能量不足，会造成簇组织的维持时间缩短，造成任务执行失败。

3）节点与汇聚节点的距离相对较近。簇头节点根据簇成员节点汇报的目标信息进行初步的处理后，要将结果发送给汇聚节点，如果簇头距离汇聚节点过远，信号的发送将消耗大量的能量，会使得簇头很快因能量耗尽而死亡。

4）簇头节点激活的范围要适当。适当就是指簇的规模不能太大，这会造成簇边界成员与簇头的通信距离过远，此外，过多的成员节点与簇头信息交互有可能造成不必要的数据冲突；簇的规模又不能太小，这会造成簇的检测范围减小，簇头频繁交接，造成不必要的能量消耗。因此，需要通过强制手段限定簇范围，达到确保簇具有局部性的目的。

第1）～3）条原则，本文通过对簇头选取计时器的合理设置来满足，第4）条原则，则给出一种基于任务需求的自适应簇范围划分方法。

3 动态分簇协议

本文提出的动态分簇协议，其工作过程如下：

1）当目标事件在监测区域内发生后，检测到该事件的节点开始组簇，组簇过程包括簇头竞选和簇成员加入；2）簇成员将采集到的相关目标信息发送给簇头节点；3）簇头接收各成员发送的事件信息，处理后发送给汇聚节点；

4）簇寿命到期时，簇头发出簇重组信息，组建新簇。

下面着重阐述协议的簇头竞选、簇成员加入以及簇重组等环节。

3.1 簇头竞选

当发现目标事件在监测区域范围内发生时，传感器网络中信号强度超过检测门限s0的节点成为簇头候选节点，并广播自身的位置和测量值。每个簇头候选节点设置一个选取计时器（backoff timer），如果簇头候选节点i的计时器终止时还没有接收到其它节点的簇头当选信息，那么i节点就向其它节点发送当选信息，成为簇头。候选节点最终能否成为簇头由选取计时器决定，设计计时器时权衡节点接收信号强度，节点剩余能量及节点与汇聚节点的距离三个因素。计时器的长度计算公式为

如果节点i的计时器终止前未收到簇头当选消息，那么该节点就向其他节点发布当选消息，成为簇头。当选信息包含簇头节点的ID、位置信息和时间信息等。如果节点i在其计时器终止前接收到簇头当选消息，则该节点停止竞选进程，成为簇成员节点，存储簇头节点的ID等各种信息，并通过调整本地时钟与簇头节点实现时钟同步。

3.2 簇成员加入

对于簇范围的选择，许多文献将其简单的以节点通信范围划分［16～17］，这种划分无法保证簇的局部性，不利于节省能量。而如果具体指定簇范围，由于网络中节点的随机分布和目标出现位置的不确定性，有可能造成簇内的节点满足不了任务要求。因此，本文提出一种自适应的划分方法来确定簇范围。首先对探测到目标的节点数量设置一个阈值区间［NminNmax］，如果簇头初始激活范围内的活跃节点数Na＜Nmin，则扩大激活半径Ra，尺度为可调半径梯度Radjust；如果Na＞Nmax，则缩小Ra。调整过程持续到Na∈［NminNmax］为止，此时对应的Ra即为簇半径。Nmin和Nmax可根据实际应用中的具体需求确定，其基本原则是使簇头能获得足够的目标信息，满足对目标状态信息获取的要求。

分析该算法可以发现：当簇头周围活跃节点数量多时，就可以选择较小的激活半径，以减少通信造成的能量消耗；当活跃节点数量少时，簇头就选择较大的激活半径以保证跟踪质量。从而自适应地选择簇范围。

3.3 簇重组

当簇寿命结束时，簇头发出重组信息，重组信息里包含了当前对目标事件的监测信息，比如目标位置，速度和方向等，便于下一个簇的任务完成，以保证连续性。簇寿命结束的标志是当前簇无法满足监测任务要求。比如在二维平面内，至少需要三个不在同一直线上的传感器才能完成对目标的定位，在三维空间内，完成定位至少需要四个不在同一平面内的传感器，因此，为了保证簇头能获得足够的冗余信息，将簇生命结束的标志定为：簇内接收到目标信号的成员节点数Na≤Nmin的时刻。为了避免由于目标机动造成簇头误以为寿命结束，发出不恰当的重组信息，在此设置一个簇寿命结束检测计时器τdet，其长度等于系统允许的分簇时延上限τmax。当簇头发现能够检测到目标的成员个数不超过Nmin时，启动检测计时器，如在计时器τdet结束时，能够探测到目标的簇成员节点数仍不超过Nmin，簇头就发出重组信息；如果在计时器τdet结束前Na的个数超过Nmin，则取消τdet，继续进行目标定位跟踪。簇成员节点在收到重组信息之后，清除存储的当前簇头信息，退出簇，而后判断自身能否检测到目标信号，如果能，则根据簇头竞争计时器的长短，参与新簇头的选举；如果没有检测到目标信号，则转入休眠状态。

为了避免簇重组中断，造成目标丢失，有必要加入目标丢失检测机制和目标恢复机制［9］。

目标丢失检测机制：簇头发出簇重组信息后，设置一个目标丢失检测计时器，其长度等于允许的分簇时延上限τmax。如果在此计时器终止前收到下一簇头的当选信息，则取消此计时器，存储下一个簇头信息，作为簇成员加入。如果在此计时器到期时仍未收到下一个簇头当选信息，则启动目标恢复机制。

目标恢复机制：簇头提高发射功率，激活更大范围内的节点，被激活的节点感应目标，竞选簇头，重新组簇。如果仍然没有新簇头产生，则认为目标已不在网络监测区域内。

4 仿真及性能评估

为了对本文提出的分簇协议性能进行评估，在相同条件下对本文协议和文献［9］提出的协议进行仿真比较。实验中取200m＊200m的区域，区域顶点的坐标分别为（0，0）、（200，0）、（200，200），（0，200）。随机部署的节点的数为200个，q0取2J，Eelec取50nJ／bit，εfs取10pJ／bit／m2，εmp取0.0013pJ／bit／m4，d0取75m，数据包取4000bit，Nmin取10，Nmax取15。α1、α2、α3分别取0.3、0.5、0.2。目标信号源强度取100，检测门限s0取0.5。

在簇头竞选时，本文提出的协议考虑到了与汇聚节点距离这一因素，其目的是降低簇头向汇聚节点发送数据时的能量消耗。实验中汇聚节点的横坐标取100m不变，纵坐标依次从300m延伸到900m，即汇聚节点到网络区域的距离不断增加，节点的剩余能量服从［0，2］均匀分布，对两种协议选出的簇头与汇聚节点通信产生的能耗进行比较。

从图中可以看出，随着汇聚节点距离网络越来越远，两种协议选出的簇头与汇聚节点通信所产生的能耗都增加，本文提出的簇头竞选方案（协议2）在各个汇聚节点的位置消耗的能量都低于文献［9］的簇头竞选方案（协议1），并且随着汇聚节点距离的增大，能量节省的效果越明显。说明在簇头选举时加入与汇聚节点距离这一因素对降低能耗起到了积极的效果。

两种协议下节点死亡速度与网络生存时间的对比仿真如图2所示。仿真中汇聚节点的位置取（100，350）不变。

图1 簇头与汇聚节点的通信能耗

图2 节点存活个数与网络生存时间

仿真结果表明，协议1第一个节点死亡的时间出现在第75轮，协议2第一个节点死亡的时间出现在第102轮，新协议延长了36%。网络的运行轮数从452轮延长到了688轮，延长了52.2%。说明本文提出的协议明显延长了网络寿命。分析其原因：一方面是由于本文的协议考虑到了簇头与汇聚节点的距离因素，节省了簇头向汇聚节点传送数据的能量；另一方面是因为对簇的范围进行了限制，节省了簇成员与簇头节点之间数据发送的能量。

5 结语

本文提出了一种针对无线传感器网络的动态分簇协议，该协议在簇头竞选时综合考虑了接收信号强度、剩余能量、与汇聚节点距离三个因素，在簇成员加入时，根据具体任务要求对簇规模进行了适当的限制，能够自适应的调节动态簇范围。仿真实验表明，该协议能有效地节省节点能量，延长网络寿命。下一步的工作应研究如何合理的对影响簇头选举的三个因素设置权重。

［1］沈波，张世永，钟亦平.无线传感器网络分簇路由协议［J］.软件学报，2006，17（7）：1588－1600.

［2］申兴发，李鸿斌，赵军，等.面向目标跟踪的传感器网络分布式组管理机制［J］.仪器仪表学报，2007，28（6）：966－972.

［3］林金朝，李国君，周晓娜，等.基于动态能量管理的无线传感器网络动目标定位跟踪方法［J］.通信学报，2010，31（12）：90－96.

［4］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy－efficient communication protocol for wireless microsensor networks［C］／／Proc.of the 33rd Annual Hawaii Int'Conf.on System Sciences.Maui：IEEE Computer Society，2000：3005－3014.

［5］Younis O，Fahmy S.Heed：A hybrid，energy－efficient，distributed clustering approach for ad－hoc sensor networks［J］.IEEE Trans.on Mobile Computing，2004，3（4）：660－669.

［6］Yang H，Sikdar B.A protocol for tracking mobile targets using sensor networks［C］／／Proc IEEE Workshop Sensor Network Protocols and Applications，Piscataway，USA，2003：71－81.

［7］Zhang W，Cao G.DCTC：dynamic convoy tree－based collaboration for target tracking in sensor networks［J］.IEEE Transactions on Wireless Communications，2004，3（5）：1689－1701.

［8］Chen W，Hou J C，Sha L Dynamic clustering for acoustic target tracking in wireless networks［J］.IEEE Transactions on Mobile Computing，2004，3（3）：258－271.

［9］邓克波，刘中.基于无线传感器网络动态簇的目标跟踪［J］.兵工学报，2008，29（10）：1197－1202.

［10］Wang S S，Shih K P，Chang C Y.Distributed direction－based localization in wireless sensor networks［J］.Computer Communications，Elsevier，2007，31（10）：1424－1439.

［11］马保国，乔玲玲，贾寅波.无线传感器网络研究综述［J］.计算机与数字工程，2008，36（9）.

［12］康玮杰，钱慧，余轮.多频段无线传感器网络研究综述［J］.计算机与数字工程，2010，38（5）.

［13］陈磊，赵宝华.低能耗自适应分簇的面向数据融合的路由协议［J］.北京邮电大学学报，2009，32（5）：71－74.

［14］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application－specific protocol architecture for wireless microsensor networks ［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660－670.

［15］Li D，Hu Y H.Energy based on collaborative source localization using acoustic micro－sensor array［J］.Journal EUROSIP Applied Signal Processing，2003，4：321－337.

［16］Selvakennedy S，Sinnappan S，Yi S.A biologically－inspired clustering protocol for wireless sensor networks［J］.Elsevier Computer Communications （S0140－3664），2007，30（10）：2786－2801.

［17］Fan X N，Song Y L.Improvement on LEACH protocol of wireless senor network［J］.International Conference on Sensor Technologies and Application，2007，5（30）：260－264.