SAHRC: 一种基于分簇的无线传感器网络路由控制算法

张小波 程良伦 Zhu Quan-min

①(广东工业大学自动化学院 广州 510006)

②(英国西英格兰大学计算机工程与数学学院 布里斯托尔 BS161QY)

1 引言

无线传感器网络建设最主要考虑的问题之一就是降低全网能耗。路由控制算法是达到这一目标的重要手段之一。路由控制算法从研究方向进行分类可以分为：节点功率控制算法、层次型控制算法、网内节点协同启发机制[1]。节点功率控制机制调节网络中每个节点的发射功率，目的是在保证全网连通性的情况下，均衡节点一跳距离的邻居数量。经典算法有：LMA[2]、DRNG[3]等；层次型控制算法是选择网络中的一些节点做为骨干节点，构架起包转发的骨干网络，其他非骨干网节点接受骨干节点管辖；网内节点协同启发机制是节点按照周边通信环境的变化，进行自主控制以及和邻居节点进行交互的机制，经典算法有：STEM算法[4,5]，ASCENT算法[6,7]等。无线传感器网络实际中面对的是随机部署的大规模密集型网络，经典的路由控制机制无法适应无线传感器网络应用场合的特殊要求，特别是针对大规模事件驱动型网络的应用场合。功率控制由于缺乏休眠机制而无法适应大规模密集型网络。层次型控制可以近似地用于大规模网络但是缺乏本地功率优化和自适应性。而协同启发机制的缺点在于局部的自适应性不能很好地扩展到大规模网络。除此之外，大多数算法都没有考虑节点剩余能量和负载均衡问题。

针对这一问题，通过结合各种路由控制机制的优势来构建一种适应于大规模事件驱动型网络场景的无线传感器网络路由控制算法。在这种场合下，兴趣事件的低概率发生使得网络中传递的数据量较小，因此大部分能耗会流失在节点侦听环节，所以降低网络的侦听能耗成为延长无线传感器网络生命期的特性因素和主要手段，同时该场景下路由控制算法的设计还必须符合传统算法设计的共性原则[8]。回顾以往面向事件驱动型网络经典算法有GAF[9],LEACH[10]等；本文在研究LEACH算法分簇机制思想[11]的基础上结合网内节点启发机制改善设计一种自适应的混合型路由控制(Self-Adaptive Hybrid Routing Control, SAHRC)算法。仿真结果表明，改进后的算法较原有算法有更好的稳定性和可靠性。

2 LEACH算法的局限及SAHRC算法的提出

LEACH算法具有以下不足：

(1)由于LEACH 算法中簇头产生的随机性，会导致部分簇头相距过近或簇头处于网络边缘，簇内成员离簇头太远的情况，从而大大增加了节点的传输能耗。

(2)由于LEACH 簇头选择的随机性，使得网络中簇头节点所负担的簇内成员数不同(即每个簇头节点的节点度不同)，加重了个别簇头节点的负担，使得网络的负载平衡度下降。

(3)LEACH算法在簇头选举过程中，没有考虑节点的剩余能量状态，会出现某一节点的剩余能量很小，但仍被当选为簇头的情况。

(4)LEACH算法并没有考虑到网络热区问题。网络热区问题指的是网络中距离汇聚节点越近的节点传输信息的频率就会越大，而越是离汇聚节点远的簇头节点负责转发信息的负担就会越小。

本文针对以上不足提出一种自适应混合型路由控制算法——SAHRC算法，该算法是在LEACH分簇思想的基础上，结合了网内节点启发机制，使原有算法更适应于大规模事件驱动型网络。

3 SAHRC算法设计

3.1 SAHRC算法描述

SAHRC算法在沿用LEACH算法的原有分簇机制的基础上引入网内节点启发机制思想，使得算法更适应于大规模网络。在分簇之后的网内通信和簇间通信都利用了启发机制的思想。

(1)相关定义

CM(Cluster Member)：簇内节点，非簇头节点。

CH(Cluster Head)：簇头节点。

Ei：节点i当前剩余能量。

TEST消息：TEST消息发送成功则节点发送包含自身ID号的HELLO消息，表示自身成为簇头。节点若已经是簇头，或者已经属于某一个簇，则不发送TEST消息。

节点信息：一个节点的节点信息包括自身ID及剩余能量值Ei。

CLUSTER消息：由簇头节点发送，告知簇内节点簇头节点的ID与En，及该簇内部所有节点之间的邻居节点关系和Ei。收到该消息的簇内节点记录自身处于哪一个簇，并确定邻居节点，调整发送功率。

HELP消息：用来把节点由侦听状态转入测试状态或由测试状态转入活动状态的直接依据。

时间域值Ta：在时间Ta内如果没有消息转发，则认为该节点可以由活动状态转入休眠状态。

(2)SAHRC算法步骤

步骤1 分簇

(a)簇首选择机制 LEACH算法中，随机簇首选择机制保证了网络的自组织特性，但并没有将剩余能量作为簇首选择的条件，本文在簇首选择中加入了剩余能量和平均能量的考虑，从而优化了LEACH的簇首选择机制。在每一轮的簇重构之前，节点都查看其当前剩余能量Erest和上一轮末节点所属簇的平均剩余能量Eaverage。当Erest≥Eaverage时，此节点产生随机数，参与候选簇首竞争；反之，当Erest＜Eaverage时，节点能量有限，则节点就处于休眠状态，不参与候选簇首竞争，直至候选簇首竞争结束。在LEACH中，采用随机数小于阈值的方式选为簇首，簇首的产生具有极大的随机性，容易出现部分簇首剩余能量相对较小但仍被选为簇首的情况，此时节点的能量就会很快耗尽，不利于延长整个网络的使用寿命。基于以上考虑，各节点采取随机数生成策略：若节点参与候选簇首竞争，则随机地产生一个初始随机数，将节点剩余能量与初始能量的比值的负指数函数作为临时随机数的大小调节因子来产生最终随机数，利用单调递减的负指数函数对产生的随机数作进一步的调整。剩余能量越大的节点产生的最终随机数越小，越容易小于当前阈值，也就越容易成为本轮的候选簇首；而剩余能量越小的节点调节因子越大，产生的最终随机数也越大，越不容易成为本轮候选簇首。这样使得能量大节点尽可能容易地成为候选簇首，平衡了网络能量负载，可以延长网络寿命。

式中rand(i)是节点i与阈值比较的最终随机数，temp(i)是节点i生成的0～1间的初始随机数，E(i)是节点i此时的剩余能量，E0是节点i的初始能量。若rand(i)小于阈值T(n)，这个节点i就成为候选簇首。T(n)的计算公式与LEACH算法中类似。

(b)簇的生成算法 通过簇首选择机制产生了一定比例的候选簇首，这些候选簇首通过竞争产生本轮正式簇首，而其他节点处于休眠状态直至簇首竞争结束。

在竞争初始阶段，基站在整个区域内以一定的发射功率广播TEST消息，每个候选簇首根据收到的消息的强弱程度计算自身到基站的距离。考虑到非均匀分簇能够很好地解决多跳路由的传感器网络中常见的热区问题，这里提出的计算竞争半径的公式如下：

其中R是簇首si的竞争半径，c是用来控制取值范围的参数，在0～1之间取随机值。当c值取0时，算法分成大小均匀的簇；当c大于0.5后，网络的存活时间逐渐下降，这是由于算法产生的簇首的数量逐渐增加，增大了网络的能量消耗。Dmax和Dmin分别表示网络中节点到基站BS的距离的最大值和最小值，D(si,BS)表示簇首si到基站的距离，Rmax是预先定义好的最大的竞争半径。每个候选簇首得到自身的竞争半径后，在自己的竞争区域内广播竞争簇首的消息。若在它的竞争区域内没有其他候选节点，则此候选簇首竞争成功，并在整个网络中广播竞争成功的消息；若在自己的竞争区域内存在其他候选簇首，则比较各个候选簇首的剩余节点能量，剩余节点能量较大的竞争成功，并广播此消息，其他候选簇首退出竞争；网络中的其他节点根据接收到的信息的强度加入各个簇中，若有节点未收到任何一个簇首发来的消息，则此节点成为候选簇首参与竞争。最后，网络中的所有节点都成为簇首或簇内成员。由此保证了监测区域中所有节点形成的监测范围可以满足应用需求，任何一个节点都能将感知到的数据发送到簇首，再由簇首转发给基站，而不会产生网络分隔，从而可以保证簇节点的连通与覆盖。簇内成员向簇首发送加入消息并将自身的剩余能量告诉簇首，簇首就知道了簇内成员的总数并在得到各个节点的能量信息后计算簇内平均能量并将此消息在簇内广播，此时整个网络的簇结构基本确定。

规则1 在网络成簇过程中如果预备簇首发现自己的簇内还有另外一个或一个以上的预备簇首，则通过距离汇聚节点的远近将优先选择离汇聚节点较近的节点作为这个簇的簇头。

规则2 在网络成簇过程中，如果簇首发现自己的节点度已经超过了6或者以上时则自动分为两个簇，并选择簇内成员节点密集处优先成簇。如果簇首发现自己的节点度小于4或者更少时，则主动与邻居簇结合成一个簇。

规则3 如果在全网簇首选择过程中发现某些靠近汇聚节点的节点或热区节点能量消耗过多时要优先考虑离汇聚节点较远的节点作为候选簇首。

步骤2 簇内通信

簇内通信采用局部的ASCENT算法，不同的是从数据源发起求助信息，并考虑节点剩余能量问题。

(a)在初始化阶段，所有节点进入测试阶段。开始由任一数据源发起HELP消息，发给节点剩余能量较为高的邻居节点。

(b)邻居节点加入活动节点一起转发数据，如此反复直到本簇的簇头节点加入活动节点。

规则4 如果节点发现自己的邻居中有簇头节点，则直接选择该节点充当活动节点并转到步骤3的(a)步，如果节点发现自己的邻居中没有簇头节点，但是有关联节点，则选择关联节点充当活动节点并转到步骤3的(b)步。

规则5 在规则4的基础上， 如果节点发出HELP消息之后，发现丢包率仍然高于丢包临界(DL)，则选择剩余能量次高的邻居，要求其加入活动节点。依此类推，直到发现邻居数量高于邻居临界(NL)为止。

步骤3 簇间通信

在簇间仍然使用ASCENT规则来完成数据的转发。

(a)当某一簇头节点CH加入活动节点之后，向汇聚节点方向的关联节点发布HELP消息。选择剩余能量大的关联节点加入到网络中。

(b)该关联节点再向汇聚节点方向的簇头发送HELP消息。如此反复直到把消息传送给汇聚节点。

规则6 对于孤立簇，如果簇头没有收到簇内节点的CONECTNODE消息时，则要求所有的簇内节点探测自身的邻居节点，加入关联节点。

步骤4 网络维护

当簇内节点失效数量达到一定的阈值或者网络中有簇头节点失效则重新进入簇头选择和全网待定状态，也即等待网络中随机事件的发生。

经过SAHRC算法之后，理论上得到如图1所示的SAHRC算法网络拓扑结构分析图。

3.2 SAHRC算法的状态转换机制

在SAHRC算法中，每一节点始终处于4种状态中的任意一种：休眠(SLEEP)、侦听(PASSIVE)、测试(TEST)、活动(ACTIVE)。

图1 SAHRC算法网络拓扑结构分析图

初始状态时一个随机的定时器打开，任意节点在测试阶段初始化。当一个节点进入测试阶段时候，它就设定一个时间器Tt，当Tt期满的时候，发送“邻居声明”消息，节点进入活动状态。如果在Tt到来之前活动节点的数量超过了邻居上限(NT)或者如果平均数据丢失率(DL)高于在自己处于测试阶段时的平均数据丢失率时节点转入侦听状态。如果多个节点同时转入了测试状态，就选择在“邻居声明”消息里节点ID高的节点成为活动节点。活动节点的数量不能超过NT值。当一个节点进入侦听态的时候，它设置了一个定时器Tp。当Tp时间到的时候，节点进入休眠状态。如果在Tp到来之前邻居数量低于NT，或者DL高于丢包临界值(LT)，或者DL低于丢包临界值但是节点收到了一个来自于活动邻居的求助消息，节点就转入到测试状态。当在侦听状态时节点打开它们的射频模块，能够监听到所有的活动邻居传送的包，但不传送任何数据包。处于侦听和测试状态的节点，持续刷新活动邻居的数量和数据丢失率的值。一个进入休眠态的节点关闭射频模块，设置一个时间Ts用来度量休眠长度，当Ts到了的时候，节点转入侦听模式。一个节点一旦进入活动状态，就在活动状态继续传递数据和路由包直到它消耗完能量为止。如果数据丢失率高于LT时，活动的节点又开始发送求助消息。

所有网络节点都按照4种状态不停循环，并加入一个时间域Ta值，即如果在这个时间内活动节点不再转发数据则主动转入休眠状态。这样就大大节省了网络资源的消耗，使得算法更加适用于事件驱动型网络。这里Ta的值要通过实际事件发生概率的大小等因素而定。

4 模拟实验与结果分析

这里通过OMNET++仿真工具进行模拟并分析SAHRC算法的性能。利用NED和INI配置文件描述下面实验环境：N个节点随机部署在100 m×100 m的正方形事件区域内。随机选择1个节点作为汇聚节点，p个节点作为源节点，源节点以速率v=5 kbps匀速获知数据并发往汇聚节点。每个节点通信半径50 m，节点初始能量10 J，节点侦听能耗0.1 J。实验中不考虑节点移动性和报文传输延时，并且忽略节点接收报文及处理器的能耗。模拟实验的基本参数设定如表1所示。

表1 模拟实验主要参数

为了尽量忽略由于Ta值导致的网络性能不同，设Ta=20Tp。节点信号强度之比用距离平方的反比来表示。

4.1 网络节能性实验分析

实验中采用一半节点死亡的时间作为网络生存时间的评价标准。因为若网络中一半节点死亡，剩余节点的能量已经很低，网络的连通度也无法有效保证。网络生存时间的对比如图2所示，SAHRC的网络生存期明显高于LEACH，特别是随着节点数量的增多，LEACH算法下网络生存期增幅越来越小。这是因为一方面随着网络节点数量的增多，处于侦听与活动状态节点过多，造成了网络不必要的消耗；另一方面由于活动节点无法进入休眠状态而导致大部分节点过早死亡，出现网络割裂现象。SAHRC算法在考虑剩余能量的基础上加入网内节点启发机制使得节点有效选择链路而避免了过多节点加入到信息转发中来，同时也达到了负载均衡的目的。而Ta和Tj参数的加入，很好地避免了节点早死现象。实验表明SAHRC算法更适应于大规模事件驱动型网络。

图2 SAHRC与LEACH网络生命期对比

4.2 网络稳定性实验分析

实验不断增加模型节点数量参数，在与其相应的网络生命期内统计两种算法导致的汇聚节点收到数据包数量总和。由图3可见，随着节点的增加，SAHRC算法汇聚节点收到的数据包数在相应地增多，而且增幅较高。而LEACH算法汇聚节点收到的数据包数量在节点数少于200的时候还有一些增幅，但是当节点数接近200时汇聚节点收到的数据包数已经基本上不变，即增幅趋向于零。

图3 SAHRC与LEACH数据包数量对比

仿真实验表明，SAHRC算法延长了网络生命周期，提高了网络通信效率。改进了LEACH算法的节能性和稳定性。

5 结束语

本文在LEACH算法的基础上，设计了一种适用于大规模事件驱动型网络的自适应混合型路由控制算法。该算法结合层次型路由算法的分簇思想以及节点网内启发机制，扩大了原算法的应用场合，使网络中剩余能量高的节点充当活动节点，延长了网络生命周期，提高了网络的通信效率。同时设定了活动节点状态转换域值，进一步降低了全网能耗。

[1] 杨贺, 张树东, 孙利民. 无线传感器网络的拓扑控制机制[J].计算机科学, 2007, 34(1): 36-38.Yang He, Zhang Shu-dong, and Sun Li-min. Topology control mechanism in wireless sensor networks[J].Computer Science,2007, 34(1): 36-38.

[2] 邓克波, 刘中. 基于感知距离调节的无线传感器网络节能区域覆盖[J]. 电子与信息学报, 2009, 31(10): 2305-2309.Deng Ke-bo and Liu Zhong. Energy-efficient area coverage in wireless sensor networks with adjustable sensing ranges[J].Journal of Electronics&Information Technology, 2009,31(10): 2305-2309.

[3] Park Kyung-joon, Kim Laeyoung, and Hou J C. Adaptive physical carrier sense in topology-controlled wireless networks[J].IEEE Transactions on Mobile Computing,2010, 9(1): 87-97.

[4] Liu Yun-huai, Zhang Qian, and Ni L M. Opportunity-based topology control in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems, 2010,21(3): 405-416.

[5] Huang C M, Ku H H, and Kung H Y. Efficient powerconsumption-based load-sharing topology control protocol for harsh environments in wireless sensor networks[J].Communications,IET, 2009, 3(5): 859-870.

[6] Cerpa A and Estrin D. ASCENT: adaptive self-configuring sensor networks topologies[J].IEEE Transactions on Mobile Computing, 2004, 3(3): 272-285.

[7] White J, Doughtery B, and Schmidt D. ASCENT: an algorithmic technique for designing hardware and software in tandem[J].IEEE Transactions on Software Engineering,2010, 36(6): 838-851.

[8] 刘林峰, 金杉. 面向低概率事件场景的传感器网络分簇控制算法[J]. 计算机研究与发展, 2008, 45(10): 1662-1668.Liu Lin-feng and Jin Shan. A clustering control algorithm of wireless sensor networks in low probability event scenario[J].Journal of Computer Research and Development, 2008,45(10): 1662-1668.

[9] 沙超, 王汝传, 黄海平, 等. 基于生命期划分的无线传感器网络节能策略[J]. 通信学报, 2010, 31(4): 1-7.Sha Chao, Wang Ru-chuan, Huang Hai-ping,et al.. Energy saving scheme based on life period division for wireless sensor networks[J].Journal on Communications, 2010, 31(4): 1-7.

[10] Heinzelman W R, Chandrakasan A, and Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.

[11] 徐劲松, 杨庚, 陈生寿, 等. 基于全局信息的 LEACH 协议改进算法[J]. 南京邮电大学学报(自然科学版), 2009, 29(4):55-63.Xu Jing-song, Yang Geng, Chen Sheng-shou,et al.. A global information based protocol for LEACH improvement[J].Journal of Nanjing University of Posts and Telecommunications(Natural Science), 2009, 29(4): 55-63.