无线传感器网络中能量有效分簇路由算法＊

周则顺 李腊元 许 毅 高 玉

（武汉理工大学计算机学院 武汉 430063）

无线传感器网络（wireless sensor networks）是信息感知和采集技术最重要的技术之一，它部署灵活、维护简单，广泛应用于军事侦察、环境监测、医疗监护、农业养殖和其他商业领域，以及空间探索和抗灾抢险等特殊领域.由于传感器节点一般由电池供电，能量有限且不可补充，因此，在影响无线传感器网络生命周期的众多因素中，节点的能量最为重要.同时，分簇算法与平面路由算法相比具有更好的能量有效性及可扩展性［1］.文献［2］中HEED选举簇头时考虑了剩余能量，但以主从关系引入了多个约束条件作用于簇头的选举过程，提高了协议的复杂度.本文提出了一种基于能量有效的分簇的路由算法（EECRA），该算法有效地平衡各节点的能量消耗，最大化整个网络的生命周期.

1 EECRA的网络描述

无线传感网络由N个随机部署的节点组成，因此可有如下描述定义.

定义1设图G＝（V，E）为简单连通无向图，当且仅当图G为无自圈的、连通的无向图；且G中任意2个节点之间最多有一条边，其中V为所有节点构成的顶点集合，E为所有链路构成的边集合.

定义2假定传感器网络G中各节点均具有相同的初始能量E0，对G中的任意节点v，可用E（v）表示节点v的当前剩余能量；同时，节点具备数据融合功能，每个节点都有一个惟一的标识（ID）.

定义3网络中节点通信采用Heinzelman等人在文献［2－3］中提出的无线通信模型.当发送节点与接节点的距离小于阈值d0时，采用自由空间模型，即发送方发数据的能耗与距离的平方成正比，否则采用多路衰减模型，发送方发送数据的能耗与距离的四次方成正比.发送方发送kbit的数据到距离为d的接收方所消耗的能量为

式中：Eelec为发射电路的能耗；εfs，εmp分别为这2种模型中功率放大所需的能量.

2 EECRA的实现

EECRA算法是按轮运行，每轮分为成簇阶段和数据传输阶段.在成簇阶段首先将所有节点组织成簇，然后构造路由树，在数据传输阶段把网络采集的数据融合后传递到基站.为了减小簇头节点的能量开销，簇头之间采用了多跳中继的方式将采集的数据发送到基站.

2.1 簇及簇头的选择算法

EECRA为分布式竞争算法，簇首的选择以节点与基站的距离及其邻居节点的剩余能量中的最小为主要依据.算法开始时，基站先以给定的功率向全网发送广播信号BS＿message，节点根据接收到的信号强度计算出它到基站的距离di－BS，由该距离值得到自己的竞争半径Ri，计算如下.

式中：c为控制取值范围的参数，依网络规模在［0，1］内取值，其值确定后固定不变；dmax和dmin为节点到基站的距离的最大值和最小值；Rc为节点的最大竞争半径.

每个节点将竞争半径内的区域作为自己的竞争区域，将竞争区域内的所以其他节点看做是自己的邻居.节点以半径Rc广播消息E＿message（ID，Eresidual）并根据邻居节点发送的 E＿message消息更新邻居表，得到其开始簇首竞争的时刻tc.

式中：μ为分布在［0.9，1］的随机实数；T为事先规定的簇首竞争持续时间；¯E为邻居节点的平均剩余能量；Eresidual为节点的剩余能量.

若节点在竞争时刻到来之前已经收到邻居节点的簇首申明消息 HEAD－message（ID），则退出竞争并加入以邻居节点为簇首的簇.否则，节点统计邻居节点中已加入簇的节点数并与阈值k（t）进行比较.当节点数小于阈值k（t）时，节点广播簇首申明消息宣布竞争成功.

阈值k（t）的计算公式如下

式中：t为当前时间；m为全部邻居节点数.

2.2 簇成员加入簇算法

网络的簇头确定后，普通节点选择合适的簇加入.普通节点选择转发功耗最小的簇头作为自己的簇头.首先所有的簇头广播自己的节点号和接收到Sink的信号强度，在簇头通信半径内，普通节点接收并将簇头信息存储到自己的簇头集合中，并依据信号强度计算自己经过簇头转发到Sink的能量消耗（计算按照式（1））；选取转发能量消耗最小的簇头加入［4］.

簇首竞争结束后，邻居节点中有多个簇首的节点加入距自己最近的簇以减少通信干扰，未加入簇的节点发送消息J＿JOIN＿message（ID，JumpID）至剩余能量最小的邻居节点，通过该邻居节点成为其他簇的多跳成员.

2.3 候选节点的处理

由无线通信模型可知，节点的传输能耗随传输距离的增加显著增大.为降低传输能耗，EECRA不仅采用基于树结构的多跳路由方式，而且在选择路由候选节点时选择距离自己较近的节.因此，在簇生成后，每个簇首向全网广播消息RELAY＿message（ID，Eresidual，di－BS），根据其他簇首发送的消息强度计算得到距其他簇首的距离，依据距离值选择路由候选节点.这里引入一个阈值DBS，若簇首节点si到基站的距离大于DBS，则路由候选节点集合为SCH（i）＝ ｛sj｜dj－BS≤di－BS且di－j≤kRi｝，其中k是使得sj存在的最小整数；否则路由候选节点集合为SCH（i）＝ ｛sj｜dj－BS≤di－BS且di－j≤Ri｝，当且仅当集合为空集（即没有可用于数据中继的路由候选节点）时，si将数据直接传送至基站［5］.

为了均衡网络能耗，避免节点由于能量消耗过多导致提前死亡，簇首节点应当在路由候选节点中选择剩余能量较多的节点作为其中继节点.然而网络能耗还与中继节点的位置有关，仅考虑剩余能量选择中继节点往往会造成网络能耗增大，因此选择中继节点时还需考虑节点位置.

假设通信采用式（1）中的自由空间模型，中继节点sj直接与基站通信，则si通过sj传输l比特数据至基站时，节点si和sj的总能耗为

可以看出，d2i－j＋d2j－BS越小则传输总能耗越小.因此为减小网络能耗，EHUC协议的路由树构造策略为：节点有多个路由候选节点时，从剩余能量最大的两个节点中选择d2i－j＋d2j－BS最小的节点作为中继节点.

3 算法的正确性和复杂度分析

性质1整个网络的控制消息复杂度为O（N）.

证明协议开始时，每个节点广播一条E＿message消息.簇生成过程中，每个簇首广播一条HEAD＿message消息，每个单跳簇成员最多广播两条JOIN＿message消息，每个多跳簇成员广播一条J＿JOIN＿message消息.假设网络节点数为N，生成簇首数为X，单跳簇成员数为Y，则多跳簇成员数为N－X－Y.在路由树构造过程中，每个簇首广播一条RELAY＿MSG消息［6］.因此网络中总的控制消息开销为

所以整个网络的控制消息复杂度为O（N）.证毕

性质2整个网络中，节点的存储开销为O（N）.

证明协议中节点存储开销在于每个节点保存所有邻居节点的信息以及簇首节点保存路由路径里中继簇首节点的信息.网络模型为高密度静态网络，节点随机分布在整个监测区域A内，由此可知节点si的邻居数量期望为.其中：为网络监测区域的面积.同样设协议生成X个簇，则每个簇首的邻簇首数量期望最大为网络中任一节点的存储复杂度最大为

所以节点的存储开销为O（N）.证毕.

4 仿真实验结果分析

通过对LEACH和EECRA算法的仿真比较来评估算法的平均性能，在仿真实验中由改进的NS2软件包生成，无线通信模块的参数与文献［3］相同.节点数为300，主要比较了2种算法在不同网络负载情况下的存活节点数量，平均能量消耗和网络负载平衡值等方面对它们进行性能对比.曲线上每点是40次仿真结果的平均值，每次仿真产生50次连接请求，请求产生服从呼叫的源节点和目的节点对以均匀的概率随机地从节点中选取.

图1为平均能量耗费与网络规模大小的关系，显示了2种协议的网络平均能量消耗情况，当网络通信负载较大时，所有协议的能耗都在增加，但是EECRA协议的能量消耗比LEACH少，这是由于负载较高时，所有协议的簇头节点工作的时间都很长，而LEACH还存在调度开销比EECRA要大.由图还可以看出，EECRA的网络能耗都低于LEACH，这是因为LEACH采用单跳通信方式，使得簇首与基站之间的远距离无线通信消耗了大量能量.EECRA都采用多跳通信来克服LEACH的不足，降低了网络能耗，从而延长网络的寿命.

图2表示存活节点数量与时间关系，说明了EECRA协议在存活节点数量方面比LEACH要强，这是因为EECRA算法能够根据簇成员数目和它们的负载动态地调整帧的长度，提高了信道的利用率，使节点的传输能量力增强，因而数据包的时间延迟较小，数据包接收率增大.

图3表示网络负载平衡值与网络规模大小的关系，图中结果可以看出，EECRA算法随着网络节点增加而负载平衡值基本不变，而LEACH算法的值波动相对较大，说明EECRA算法更加稳定.

图1 平均能量耗费与网络规模

图2 存活节点数量与时间关系

图3 网络负载与网络规模大小

5 结束语

文章分析了无线传感器网络路由协议的发展现状，讨论了各类路由协议的优缺点.从延长网络生存时间的角度出发，提出一种能量有效分簇路由算法，为了缩短节点间的平均通信距离，在LEACH算法的基础上提出了一种基于能量最小的分簇路由算法，此算法充分利用了分簇状路由算法的优点，通过高能量的基站完成诸多的高能耗任务，比如簇的建立、簇头节点的选举、路由机制的选择等，因此算法取得了较好的节能效果，通过NS2进行了仿真验证，EECRA算法相比LEACH算法和在能量有效性和能耗均衡方面具有更优越的性能，更适合应用于大规模的传感器网络，也更适合于未来无线传感网面向实际应用要求的通用结构配置方案.

［1］李腊元，李春林.动态QoS多播路由协议［J］.电子学报.2003，9（9）：1 345－1 453.

［2］Soro S，Heinzelman W B.Prolonging the lifetime of wireless sensor networks via unequal clustering［J］.In：Proc.of the 19th IEEE Int＇l on Parallel and Distributed Processing Symposium.San Francisco：IEEE Computer Society Press，2005：236－240.

［3］Heinzelman W R，Chandrakasan A，Balakrishman H.An application－specific protocol architecture for wireless microsensor networks［J］.IEEE Trans.On Wireless Communications，2002，1（4）：660－670.

［4］李成法，陈贵海，叶 懋，等.一种基于非均匀分簇的无线传感器网络路由协议［J］.计算机学报，2007，30（1）：27－36.

［5］Chan H，Perrig A.ACE：An emergent algorithm for highly uniform cluster formation［C］／／Proc.of the 1st European Workshop on Sensor Networks（EWSN）.LNCS 2920，Berlin：Springer－Verlag，2004：154－171.

［6］刘 明，曹建农，陈贵海，等.EADEEG：能量感知的无线传感器网络数据收集协议［J］.软件学报，2007，18（5）：1 092－1 109.