一种基于能量均衡的WSN分簇路由算法

王飞飞，孙志远

(平顶山学院，河南平顶山467000)

无线传感器网络(Wireless Sensor Network，WSN)[1]与传统网络不同，是集数据采集、数据处理、数据传输于一体的复杂系统，它改变了与人自然的交互方式[2]。在WSN中，数据收集是网络应用的基本功能，传感器节点(sensor node)之间相互协作，将其监测到的多种环境信息传送到基站，由于节点一般部署在恶劣或危险的环境中且节点采用能量有限的电池供电，能量难以二次补充，为了延长网络生存时间，在算法设计时研究者应以合理有效利用有限能量为首要目标，因此基于分簇的思想被应用在路由协议中，簇结构的使用可以有效地增加网络的可扩展性，与平面算法相比，可以使网络变得比较灵活，降低承担路由的节点数目，减少能耗。目前已经有许多学者对其进行了深入的研究，目前经典的分簇算法包括LEACH[3]、PEGASIS[4]、HEED[5]、CODA[6]等，与平面路由相比，可以减少节点能耗、延长网络寿命，但同时也各自存在缺陷：LEACH随机选择簇首，没有考虑到节点剩余能量，簇首与基站直接通信;PEGASIS协议中各节点通过贪婪算法成链，簇首为链上的节点之一，一旦簇首死亡则数据无法正常传输;HEED协议在成簇阶段需广播多条信息，增大了能量消耗;CODA需要知道所有节点的位置，扩展性不好。本文在对现有协议研究的基础上提出了一种基于能量均衡的WSN分簇路由算法CRAE(Cluster Routing Algorithm Based Energy Balance)，在该算法中，采用新的簇首竞争机制，簇形成后，簇间采用基于链路质量的多跳路由。仿真结果表明该算法可以延缓节点死亡，有效利用能量。

1 系统模型

1.1 网络模型

1)传感器网络为静态网络，节点部署后不再移动且可扩充新节点，节点具有唯一ID;

2)节点具有相似能量E，地位平等，节点类型同构但能量不能二次补充;

3)每轮中节点能耗不同;

4)各节点通信半径为R，无线发射功率可调，例如Berkeley Motes节点，它经由ioctl系统调用设置发射功率;

5)网络中节点时间同步，具有数据融合能力，周期性进行数据传输;

6)该网络以考虑节点能量与均衡网络能耗为首要目标，不考虑数据传输失败、节点通信安全等问题。

1.2 能量传输模型

该算法与LEACH协议所用通信模型相同，发送k bit数据与接收k bit的数据消耗能量公式如下：

在无线传感器网络中，节点能耗主要有接收能耗、发送能耗、数据融合能耗以及计算存储能耗等，其中以发送能耗与接收能耗为主，同时由式(1)可知，节点发送能耗远大于接收能耗，因此，在进行路由算法研究时要构建合适的路由以有效合理地利用节点能量。

2 算法描述

在分簇网络中，簇首需要管理簇内成员、协调数据传输、进行数据融合，还需要承担数据转发的任务，因此与普通节点相比，簇首能耗较大。在该算法中，以节点的剩余能量为主要依据选择簇首、成簇以及构建数据传输时的簇间路由。具体算法描述如下。

2.1 簇首选择

LEACH协议以随机产生阈值的方式选择簇首，但是该种算法适用的能量同构网络在实际应用中并不存在，因此有的分簇算法[5-7]在节点阈值产生时引入节点的剩余能量，但是仅以剩余能量为依据选择簇首不能保证在所有情况下都能有效延长网络寿命。基于此，本文算法以节点剩余能量与其邻节点平均能量为竞争参数。

根据文献[8]可知，无线传感器网络监测区域中理想的簇首个数为

簇的理想半径为

每轮开始工作时，节点Si以半径为r广播消息Msg，Msg中包括节点ID与节点剩余能量Eresidual，r范围内的所有节点被看做Si的邻节点，每个节点根据接收到的信息更新邻节点表Ti后，计算得出其邻节点的平均能量Si×Eave。在本文算法中，簇首竞争公式为(参数设置同文献[7])

在簇首选择阶段，节点Si产生一个位于0～1之间的随机数n：

当n＜T(s)时，Si被选为簇首并广播信息，信息中包含节点ID，簇首标识CH;

当n＞=T(s)时，Si根据收到的广播信息判断自己理想半径范围内是否存在簇首，如果存在，该节点为普通节点，否则，Si成为簇首，并广播信息。

2.2 成簇策略

在成簇阶段，簇首节点以半径r广播成簇信息，由于WSN的特性，网络节点密度较大，可能存在某些节点同时接收到来自多个簇首的信息，在现有的成簇算法中，有以簇首剩余能量为依据的，有以到簇首距离为依据的，也有将二者综合进行比较的。在本文算法中，簇首选择已将能量因素考虑在内，因此普通节点选择距离较近的簇首作为其簇首节点。

2.3 数据传输

该算法在数据传输时，在LEPS[10]算法的基础上进行动态路由构建。LEPS以最小跳数为标准建立簇首节点到基站的最短路径，选择父节点时以链路质量为依据，在减少时延的同时保证了数据的可靠传输，但是没有考虑到节点的可利用能量与路由的动态性。

该算法在路由构建时首先确定每个簇首到基站的最小跳数，然后确定每个簇首通往基站的父节点集合，以节点Si为例，其父节点选取公式

式中：Ei为Si的剩余能量;Ki为向P发送数据包数;d为Si到父节点P的距离。距离越小，传输信号质量越好，距离越大，传输信号质量越差，应尽量将d控制在d0内[9]，否则不仅信号质量差，而且大大增加簇首发送数据的能耗。一次选择完毕，在余下的节点中进行再次选择，即为每个节点选择两个可供数据传输的父节点。

在本文算法中，采用两轮数据传输后再重新成簇的方法。在首轮进行数据传输时，簇首在父节点集合中随机选择其中一个作为中转节点，并为其加状态标记;在第二次进行数据传输时则选择另外一个节点，这样可以减少簇首选择及节点计算能耗。

3 实验结果及分析

3.1 仿真环境

为了评估该算法的性能，通过OMNET++仿真平台下的模拟实验将其与现有的LEACH、HEED算法进行比较分析。假定400个传感器节点均匀散布在200×200区域中，基站位置为(50，250)，节点均为静止。通信常量设置为Eelec=50 nJ/bit，节点的初始能量为0.5 J，数据包大小为4 000 bit，数据融合能耗为5 nJ/bit/signal，传输放大器的能耗为10 pJ/bit/m2。

3.2 仿真结果分析

图1显示了在随机抽取的10轮中，每轮全网节点最大能量值与最小能量值的方差计算公式为

在式(2)中，emax、emin分别是全网节点的最大剩余能量与最小剩余能量。方差值小则说明网络均衡度较好。由图1可知，LEACH的方差值最高，而且差距明显较大，这是因为LEACH随机选择簇首，不能很好的控制能量均衡消耗。CRAE的方差最低是因为该协议在选择簇首时考虑到节点的剩余能量与邻节点的平均能量，并且在数据传输时考虑到中转节点的能量问题，因此更好的均衡了网络能耗。

图2给出了三种算法的全网存活节点个数随时间的变化趋势。在传感器网络中，设计算法以延长节点及全网的生存时间为主要目标，由于CRAE采用新的簇首竞争策略与多跳路由，使得各节点能量消耗较为均衡，所以在多轮工作后，存活节点个数仍较多，与另外两种算法相比，推迟了第一个节点的死亡，同时缩短了第一个节点与最后一个节点死亡的时间间距。

4 结束语

本文在对现有无线传感器网络分簇路由协议研究基础上，提出了一种新的基于能量均衡的WSN分簇路由算法，该算法依据节点的剩余能量与邻节点平均能量选择簇首，并且在传输过程中综合考虑了簇首与基站的最小跳数以及中转节点的能量问题。实验表明，该算法与LEACH、HEED协议相比，优化了网络能耗，延长了网络生存时间。

[1] 孙建民.无线传感器网络[M].北京：清华大学出版社，2006.

[2] Akyildiz I F，Su W，Sankarasubramaniam Y，Cayirci E.Wireless sensor networks：A survey[J].Computer Networks，2002，38(4)：393-422.

[3] Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-efficient communication protocol for wireless sensor networks[C]//IEEE Proceedings of the Hawaii International Conference System Sciences.Hawaii，2000：3005-3014.

[4] Lindsey S，Raghavendra C.PEGASIS：power efficient gathering in sensor information systems[C]//Proceedings of the IEEE Aerospace Conference’02.Montana，2002：1125-1130.

[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] Ngo H Q，Lee Y K，Lee S Y.MEPA：A new protocol for energy-efficient，distributed clustering in wireless sensor networks[C]//Proc of the IEEE Int’l Symp.on Wireless Communication Systems.Norway：Wireless Communication Systems，2007.40-44.

[7] Handy M J，Haase M，Timmermann D.Low energy adaptive clustering hierarchy with deterministic cluster-head selection[C]//Proc of the 4th IEEE Conf.on Mobile and Wireless Communications Networks.Stockholm：IEEE Communications Society，2002：368-372.

[8] Heinzelman W R，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Trans on Wireless Communications，2002，1(4)：660-670.

[9] 颜庭莘，孙利民.TinyOS路由协议原理及性能评估[J].计算机工程，2007，33(1)：112-114.