用于大规模无线传感器网络突发事件监测的路由策略

吴玉成，付红玉

（重庆大学 通信工程学院，重庆 400044）

0 引 言

事件监测是无线传感器网络（Wireless sensor networks，WSN）主要应用之一［1］，具有监测范围广、监测对象随机性大、对数据传输实时性和可靠性要求高等特点。而传感器节点能量和功能的有限性制约了该应用的有效开展，设计能量高效的路由策略以延长无线传感器网络生命周期十分必要。

分层式路由协议能够有效地降低和均衡网络能耗，特别适用于大规模 WSN 应用场景［2］。LEACH （Low－energy adaptive clustering hierarchy）［3］是最早提出的分层式路由协议，但存在簇头选择未考虑节点剩余能量、簇的数量和大小分布过于随机、单跳通信使节点能量消耗过快等不足。诸如CM－EDR（Continuous monitoring based on an event－driven reporting）［4］、AEEC（Adaptive and energy efficient clustering algorithm）［5］、SAHRC （Self－adaptive hybrid routing control）［6］、SCTC（Static chain－cluster routing protocol）［7］等改进算法在一定程度上克服了LEACH算法的不足，但应用于突发事件监测场景仍然存在缺陷，如:不相关节点参与成簇产生不必要的能量消耗；成簇区域和事件区域不吻合降低了数据融合的有效性等。文献［8］提出的事 件 驱 动 成 簇 EDC（Event－driven clustering routing algorithm）算法，保证成簇区域与事件区域的一致吻合性，克服了上述缺陷。但该算法需要借助基站和网关节点的作用，增加了网络节点的复杂度。ARPEES（Adaptive routing protocol with energy efficiency and event clustering for wireless sensor networks）算法［9］通过事件驱动成簇和多跳中继机制来提高网络能量效率，但中继路由采用实时选择方式，增大了传输时延；且仅将节点剩余能量和数据采集信息量作为簇头选举条件，并未考虑距离Sink节点远近等因素。

针对现有路由协议应用于大规模WSN突发事件监测场景的不足，本文提出了一种基于事件驱动成簇机制的路由策略。该策略在簇头选举时综合考虑了节点剩余能量、距离Sink节点的跳数、与邻居节点的连通性以及父节点数目等因素以节省和均衡网络能耗。在数据传输阶段，簇头和Sink节点间通过时延梯度路径树进行多路径选择和多跳中继通信，进一步均衡网络能耗，并为数据的及时和可靠传输提供了保障。

1 网络模型和能量消耗模型

鉴于大规模WSN突发事件监测场景，本文对网络模型做如下假设:

（1）N个传感器节点随机分布于M ×M 的正方形区域内，各节点在网络中的地位平等，具有唯一ID，网络部署后节点位置不再变化。

（2）各节点具有相同的初始能量以及数据处理和通信能力，包括存储转发、数据融合、自适应功率控制等。

（3）Sink节点唯一，静置于监测区域中心且不受能量和功能的限制。

基于文献［3］给出的WSN能量消耗模型，节点发射k bit数据到距离d处所消耗的能量为

式中:ETX－elec为发射数据时电路消耗的能量；ETX－amp为将需发射的数据放大到一定的信噪比所消耗的能量；Eelec为电路运算和处理每比特数据的能耗；εfs为自由空间模型参数；εmp为多径衰落模型参数；d0为传输模型选择门限:

节点接收k bit数据消耗的能量为

将N个长度为k bit的数据包进行数据融合处理所消耗的能量为

式中:Edata为融合处理1bit数据消耗的能量。

2 路由策略描述

本文策略由时延梯度路径树的建立、簇头选举及成簇、路由选择和路由维护4个部分组成。在网络布置初期，通过时延梯度路径树的建立使监测区域内所有节点以树的形式构成一个监测网络，同时各节点完善自身路由表信息，为簇头选举和成簇以及路由选择和维护提供必要的参考信息。节点监测到突发事件时，根据自身剩余能量、距离Sink节点的跳数、与邻居节点的连通度以及回传路径选择度等信息参与簇头竞选；所有相关节点以选举出的簇头为首构成事件簇。簇头负责收集簇内相关节点的监测数据并进行融合处理，然后根据路由信息表中信息选择合理的路由将处理后的有效数据传送回Sink节点。

2.1 时延梯度路径树的建立

鉴于突发事件监测应用对数据传输的实时性和可靠性要求，本策略做了两点设计:首先，建立以Sink节点为首的时延梯度路径树并以此完善节点路由信息表；其次，路由信息表中记录了多条备用路径选择以保证数据传输的可靠性。时延梯度路径树建立步骤如下。

（1）节点初始化:Sink节点跳数为0，剩余能量和有效父节点数均为∞；普通节点跳数为∞，剩余能量为E0，有效父节点数为0。所有节点初始化功率半径均为R0。

（2）Sink节点以初始化功率半径广播生成树消息，该消息包含节点的ID、距离Sink节点的跳数以及剩余能量等信息。

（3）收到生成树消息的节点标记为树成员，若自身跳数L0小于消息中跳数Lm值加1，则丢弃该消息；否则，在路由信息表中记录该消息。同时更新自身跳数为Lm＋1，生成包含自身信息的生成树消息，并广播。

（4）在初始化功率半径情况下的孤立节点可通过适当增大发生功率，选择距离自己最近，且比自身距离Sink节点近的有效节点作为自己的父节点，相应地更新自身跳数和路由表信息。

通过时延梯度路径树的建立，网络中所有节点都加入到该树型网络中，且各节点的路由信息表中根据到达Sink节点的时延按照从小到大的顺序依次记录了若干父节点的相关信息，为数据回传提供了最短时延路径和若干备用路径选择，为数据回传的及时性和可靠性提供了保障。

2.2 簇头选举及成簇

为了节省和均衡网络能量消耗，避免单个节点因能量耗尽过早死亡而降低网络的连通性，本文在选择簇头时不仅考虑了节点的剩余能量信息，同时考虑了节点跳数、与邻居节点的连通度以及父节点数目等因素。

节点监测到异常事件发生，立即根据式（5）计算自身竞选簇头节点的机率PCH0。机率最大的节点成为簇头节点。若Sink节点在事件区域内，则直接由Sink节点担任簇头节点。

式中:Eres、E0分别为节点剩余能量和初始化能量；L0为节点距离Sink节点的跳数；Nnbs、Npar分别为该节点的邻居节点数目和有效父节点数目；N 为总节点数目；αi（i＝1，2，3，4）为各影响因素的比重系数，αi＞0且∑αi＝1。

簇头选举流程如图1所示。

图1 簇头选举流程图Fig.1 Flow chart of cluster head selecting

簇头选举算法步骤描述如下:

（1）各相关节点生成包含ID和PCH0信息的簇头选举消息MCH0，并根据PCH0大小等待一个时间段Ti，其中Ti＝ （1－PCHi）×T0，i为节点ID，T0为一个常数。可见，机率越小的节点等待的时间越长。

（2）在等待时段内，若收到来自其他节点的簇头选举消息（MCHm），则将其保存为MCH0并广播；否则，在Ti结束时广播自身簇头选举消息MCH0。簇头选举消息包含了生成该消息的节点的ID和竞选簇头的机率。可见，机率最大的节点最先广播自身簇头选举消息，机率小的节点可避免不必要的广播自身簇头选举消息，从而减少了能量消耗和碰撞机率。

（3）在TN（TN＞T0）时间段内，节点若收到其他簇头选举消息MCHm，将当前MCH0中的PCH0与MCHm中的PCHm进行比较，若PCH0＞PCHm，则丢弃该MCHm，否则，将MCHm保存为MCH0并广播。

（4）TN时段结束后，节点保存的MCH0即为当前事件的簇头节点信息。

经过上述流程，当前事件所有相关节点都记录了簇头节点的ID，各节点采用CSMA协议将自身监测数据直接或通过其他相关节点中继传送给簇头节点。簇头节点进行数据融合处理得到有效监测数据。为了尽可能地减少节点能量消耗，各簇内节点监测数据在逐跳返回簇头节点的过程中，也可以进行必要的融合处理。

2.3 路由选择

节点根据路由信息表提供的父节点信息来选择数据回传路由，路由信息表中的多路径选择为数据的可靠性传输提供了必要的保障。数据回传路由选择按照以下原则进行:

（1）若Sink节点在当前节点路由信息表中，直接选择Sink节点作为下一跳路由节点。

（2）否则，当前节点应综合考虑有效父节点的剩余能量、中继跳数和传输时延等因素，尽可能选择剩余能量高、中继跳数少的节点作为下一跳路由以均衡和节省网络能量消耗。

（3）对时延要求高的数据信息，选择路由信息表中靠前的节点作为下一跳路由，以保证实时性。

2.4 路由维护

时延梯度路径树建立于网络部署初期，随着时间推移，节点可能因为意外情况或能耗过度而失效，导致数据无法及时可靠地传回Sink节点。因此，需要对路由信息表采取必要的维护措施:

（1）节点应及时广播自身剩余能量更新消息，其子节点根据消息更新路由信息表。

（2）当某节点剩余能量低于一定阈值时，广播失效预警消息，避免成为中继节点。

（3）节点路由信息表中父节点全部失效时，应适当增大发射功率，寻找新的有效父节点信息。

（4）新节点加入时只需广播包含自身ID的加入请求消息。接收到该消息的邻居节点发送生成树消息作为应答。新节点按照生成树的建立方法相应地更新自身跳数和路由表信息，并广播包含自身信息的生成树消息。邻居节点根据此消息相应地调整路由表信息。

3 仿真及性能分析

为了评价本文算法的性能，在 Matlab环境下，对大规模WSN突发事件监测场景进行了模拟实现，将本文算法（仿真图中简写为ET）与LEACH［3］、AEEC［5］、ARPEES［9］算法进行对比验证。仿真参数设置如表1所示。

表1 仿真参数Table 1 Simulation parameters

图2为每轮事件结束后网络剩余能量比较。采用LEACH算法时网络能量消耗速率最快，AEEC算法次之，ARPEES算法能量消耗较缓，本文算法最优，说明在节省和均衡能量消耗方面本文算法优于其他几种算法。

图2 网络剩余能量比较Fig.2 Contrast of residual energy of network

图3为每轮事件结束后存活节点的数目比较。从图中可以看出:网络有效工作期内的任何时刻采用本文算法的存活节点数都多于其他几种算法。

由图2和图3可以得出:在网络生命周期方面，本文算法比LEACH、AEEC算法分别提高2倍和1.4倍，较ARPEES算法提高了15%。相对于传统的预成簇算法（如LEACH算法和AEEC算法），事件驱动成簇算法（如ARPEES和本文算法）在节省网络能量方面具有明显优势。原因主要在于事件驱动成簇算法中与事件不相关的节点不参与簇头竞选和成簇，避免了不必要的能量消耗。同时，本文算法采用的簇头选举算法、自适应功率调整、控制消息延迟转发等机制进一步节省和均衡了网络能量消耗，使得本文算法优于ARPEES算法。

图3 网络存活节点数比较Fig.3 Contrast of number of node alive in the network

本文进行了100次重复试验以克服仿真随机性影响，得到网络中发生首个节点死亡和死亡节点数目达到一半的时间，如图4和图5所示。由图可见:LEACH算法通常在第1000轮事件左右出现首个死亡节点，约3500轮事件后死亡节点数达到一半。AEEC、ARPEES以及本文算法的首个节点死亡通常发生在第6000轮事件左右。AEEC和ARPEES算法半数节点死亡分别发生在6500和10500轮事件左右，而本文算法在13000轮事件左右死亡节点数目才达一半。表明本文算法能够更好地保证网络的有效工作期。

图4 首个节点死亡时间比较Fig.4 Contrast of time of first node dead

图5 半数节点死亡时间比较Fig.5 Contrast of time of half node dead

4 结束语

针对大规模WSN突发事件监测应用场景，提出了一种基于事件驱动成簇机制的路由策略。该策略在进行簇头选举时，不仅考虑了节点剩余能量信息，还考虑其距离Sink节点的跳数、与邻居节点的连通性以及父节点数目等因素，从而达到节省和均衡网络能量消耗的目的。同时，利用时延梯度路径树的建立为数据回传提供最短时延路径和多条备用路径选择，保障了数据传输的实时性和可靠性。仿真结果表明:本文策略在节省和均衡网络能量方面优于LEACH、AEEC以及ARPEES算法，使网络生命周期比LEACH算法、AEEC算法分别提高2倍和1.4倍，较ARPEES算法延长了15%。

［1］Prabhu S R B，Sophia S.A survey of adaptive distributed clustering algorithms for wireless sensor networks［J］.International Journal of Computer Science and Engineering，2011，2（4）:165－176.

［2］Li Chang－le，Zhang Han－xiao，Hao Bin－bin，et al.A survey on routing protocols for large－scale wireless sensor networks［J］.Sensors，2011，11（4）:3498－3526.

［3］Heinzelman W R，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.

［4］Bouabdallah N，Rivero－Angeles M E，Sericola B.Continuous monitoring using event－driven reporting for cluster－based wireless sensor networks［J］.IEEE Transactions on Vehicular Technology，2009，58（7）:3460－3479.

［5］Buyanjargal O，Kwon Y.Adaptive and energy efficient clustering algorithm for event－driven application in wireless sensor networks（AEEC）［J］.Networks，2010，5（8）:904－911.

［6］张小波，程良伦，Zhu Quan－min.SAHRC:一种基于分簇的无线传感器网络路由控制算法［J］.电子与信息学报，2011，33（8）:2013－2017.Zhang Xiao－bo，Cheng Liang－lun，Zhu Quan－min.SAHRC:a cluster－based routing control protocol for wireless sensor network［J］.Journal of Electronics＆Information Technology，2011，33（8）:2013－2017.

［7］官健，孙大洋，王爱民，等.无线传感器网络中基于广播坐标的静态链簇路由算法［J］.吉林大学学报:工学版，2012，42（2）:412－417.Guan Jian，Sun Da－yang，Wang Ai－min，et al.Static chain－cluster routing algorithm based on transmitting coordinate for wireless sensor network［J］.Journal of Jilin University（Engineering and Technology Edition），2012，42（2）:412－417.

［8］Zheng Zeng－wei，Wu Zhao－hui，Lin Huai－zhong.An event－driven clustering routing algorithm for wireless sensor networks［C］∥Proceeding of IEEE／RSJ International Conference on Intelligent Robots and Systems，Sendai，2004:1802－1806.

［9］Quang V T，Miyoshi T.Adaptive routing protocol with energy efficiency and event clustering for wireless sensor networks［J］.IEICE Transactions on Communications，2008，91（9）:2795－2805.