无线传感器网络能量均衡分簇路由算法的改进

韩红芳 孙守昌 邹凌

(常州大学信息科学与工程学院，江苏 常州 213016)

0 引言

无线传感器网络通常由大量随机分布的、用电池供电的传感器节点组成。这些节点在无人监管的模式下工作。由于节点在布洒之后不方便进行电池更换，因此，网络的工作能力受到电池电量的严重限制。如何节省能量并延长网络生命周期是设计更优算法的目标和准则［1］。

低能量自适应分簇路由协议(low energy adaptive clustering hierarchy，LEACH)［2］是较早提出的、较成熟且常用的一种基于簇结构的层次型的传感器网络路由协议。LEACH算法簇首位置的轮换算法将远距离通信的负载轮流分配给网络节点，以延长整个系统的生存时间。节点轮流担任簇首，均衡了网络的能耗。由于簇首在当选时没有考虑节点的能量高低，若节点在能量很低的情况下仍要担当簇首，就会加速其死亡。本文通过对LEACH协议的研究，采用修改门限值和优化簇首个数的方法，对其负载能量不均衡的问题作出改进。

1 经典LEACH协议分析

1.1 算法描述

LEACH协议定义了“轮”的概念，每一轮由簇的建立和稳定状态阶段组成。在簇建立的阶段，首批簇的选取是随机的。对于一个节点，其在0～1之间选取一个随机数，若该数字小于一个门限值T(n)，则节点n就成为本轮的簇首节点。门限T(n)定义如下:

式中:P为网络中簇首节点占总节点数目的百分比;r为当前的轮数;G为在前1/P轮中没有担当过簇首节点的节点集合;mod为求模运算符号。

在选定簇首节点后，向周围广播自己成为簇首的信息(advertisement，ADV)，非簇首节点根据接收到的信号强度来决定从属的簇类。当簇首收到反馈消息后，就基于TDMA方式为簇内节点分配时隙。在稳定阶段，簇内节点在自己时隙到来时刻向簇首发送采集数据;簇首节点则将接收到的数据进行必要的融合后传送到基站或汇聚节点。经过一段时间的数据传送后，网络将重新进入簇的建立阶段，进行下一轮的簇重建循环［3－5］。

1.2 LEACH算法的局限性

在LEACH算法中，簇首选择机制中没有考虑节点的剩余能量和节点已经做过簇首的次数。一旦所剩能量较少的节点成为簇首，其能量将会很快耗尽从而过早死亡，其簇内成员也将因收不到簇首的信息而不断地发送请求信号，耗费大量的能量而导致加速死亡，最终缩短了整个网络的生存时间［6］。

簇首的数量对整个网络的寿命也有影响。若簇首过少，则成员节点要经过很长的路径与簇首进行通信，簇首也将接收大量节点的信息并向基站进行转发，这对每一个节点来说负担都过重;若产生过多簇首，则会有过多的节点与基站进行通信，降低了网络能量的利用率。LEACH协议簇首选择机制没有控制簇首的数量。

2 LEACH算法的优化

上述LEACH算法存在的不足导致了无线传感器网络负载能量的不均衡。本文主要通过改进簇首节点选举算法对LEACH协议进行优化。其主要目标是避免能量低的节点成为簇首，同时控制簇首数量达到最优，从而达到降低系统能量消耗、最终实现延长网络生命周期的目的。

2.1 簇首选举机制的算法改进

对于簇首选举的改进，文献［6］对其阈值作了以下改进:

式中:En_current为节点n当前的剩余能量;En_max为节点n的初始能量。

从式(2)可以看出，由于节点的剩余能量总是小于其初始能量，所以改进后的T(n)值一定比原值要小。本算法虽然降低了剩余能量少的节点成为簇首节点的可能性，但同时也减少了其在整个网络中能够担当簇首节点的机会。

针对这一现象，本文综合考虑了节点当前剩余能量En_current和当前网络平均能量Eaverage这两个参数，改进后的阈值为:

式中:Eaverage为当前网络平均能量;En_current为节点当前的剩余能量。这样既保证了节点被选为簇首节点的可能性与其剩余能量相关，又保证了新一轮中选举出来的簇首节点数与期望数相同。

网络中簇首的个数也是影响网络寿命的重要因素，因此，本文将簇首个数的优化方案融入了改进的协议。簇首最优个数确定公式如下所示:

式中:M2为无线传感器网络覆盖区域面积;N为区域内节点数量;εamp为信号放大器的放大倍数;Eatart为每发送或接收1 B数据电路自身消耗的能量;dadv为簇首节点的最大覆盖距离。

2.2 改进算法的具体实现

改进算法的具体实现步骤详细描述如下。

①根据式(4)计算出最佳簇首个数。

②根据节点的剩余能量是否大于网络的当前平均能量，判断其是否成为候选簇首。

③候选簇首将自己产生的随机数与T(n)值比较，若随机数小于T(n)，则成为簇首节点;反之，则为成员节点，等待簇首发送告知信息。至此，簇首的选举完成。

④簇首节点以一定的功率发送簇首告知信息ADV后等待簇成员的加入。该消息只包括簇首节点的ID和消息标志符。

⑤非簇首节点根据接收到的ADV信号强度来决定从属的簇类。当簇首收到反馈消息后，便为簇内节点分配时隙(基于TDMA方式)，以确保成员节点与簇首节点通信时不会产生冲突。簇首将TDMA时隙以最小功率发送给簇内成员，这样，网络中某一轮的簇就已建立。

改进后的簇建立阶段算法流程如图1所示。

图1 簇建立阶段算法流程图Fig.1 Flowchart of cluster building phase

⑥在稳定阶段，簇内节点在自己时隙到来的时刻向簇首发送采集数据，簇首节点则将接收到的数据进行必要的融合后传送到基站或汇聚节点。同时根据信息中包含的簇首和节点的ID及其发送信息时的功率强度，估计下一轮发送消息时网络中节点的平均能量，并将此信息广播到网络，为下一轮循环做准备。至此，本轮结束。

3 算法仿真与性能分析

3.1 NS2 仿真过程

网络模拟器第2版(network simulator，version 2，NS2)可构建并仿真分析整个协议栈的运行情况，进行有线或无线网络上多种协议的模拟［7－8］。

仿真平台采用WinXP+Cygwin+NS2，仿真环境及模型如下。模拟开始时，将100个节点随机分布在100 m×100 m的空间内，基站设在X=150 m，Y=150 m的位置，站内所有节点都是静止的。无线信道带宽设置为1×106bit/s，消息长度设置为500 B，发送与接收的时延均为25 μs，每个节点的初始能量均为2 J。一轮的持续时间为10s、簇头数期望值k=5。发射机与接收机处理数据的能耗为5×10－8J/bit。自由空间模型传输放大因子为1×10－11J/(bit·m2)。多路衰减模型传输放大因子为1.3×10－15J/(bit·m4)。数据融合能耗为5×10－9J/(bit·signal)、无线信道带宽为1×106bit/s。

参数设置完成后，执行以下步骤进行协议分析。

① $ns genscen，生成一个100nodes.txt文件，这个txt文件就是随机生成的100个节点的位置信息。

② $./leach_test，进行协议模拟，生成 leach.out、leach.data、leach.alive、leach.energy 等文件。其中leach.out文件记录了节点能量等信息。

③ $awk-f leach.awk leach.alive ＞ live.txt，用 awk处理trace数据。采用awk编写脚本，提取自己需要的信息，awk脚本文件为leach.awk，将需要的信息放到live.txt文件中。

④ $startxwin.bat，进入绘图模式。

⑤ $gnuplot，采用gnuplot画图。

⑥ gnuplot＞ plot'live.txt'with linespoints。在gnuplot下画图的命令是 plot，要画的文件是 live.txt，指定绘图的样式为采用线性插值法连接各点。

3.2 仿真结果与性能分析

LEACH协议改进前后簇首节点个数情况的对比如图2所示。改进前，协议每轮产生的簇首数很不均衡;与之相比，改进后协议每轮产生的簇首数浮动较小且都在最佳值(仿真中为5个)左右。

图2 簇首节点个数比较图Fig.2 The comparison of the number of the head clustering nodes

在不考虑处理器、传感器耗能的情况下，网络的能量消耗与数据通信密切相关。LEACH协议在改进前后网络生命期的能量消耗情况如图3所示。

图3 节点平均消耗能量比较图Fig.3 The comparison of the node average energy consumption

从图3可以看出，改进后能量消耗是增加的，即说明改进前大量节点的过早死亡，导致整个网络的瘫痪，剩余能量没有被利用;协议改进后，网络消耗比改进前以略多的能量维持更长的生存期并采集更多的数据，能量被充分利用。

网络节点寿命比较如图4所示。

图4 网络节点寿命比较图Fig.4 The comparison of network node lifecycle

从图4可以看出，改进后算法的第一个节点的死亡时间比改进前算法第一个节点死亡时间延迟了25%左右，全部节点的死亡时间比改进前延迟了大约20%，即改进后的算法网络生存时间比改进前算法网络生存时间延长了20%。试验表明，改进后的算法可以降低传感器节点的通信能耗，从而有效地延长网络的生存时间［9－14］。

4 结束语

针对LEACH协议存在的问题，提出了新的优化方案。新算法将当前剩余能量和当前网络平均能量作为参数引入到簇首选举机制中，并融入簇首最优个数解决方案。利用NS2对改进前后的算法进行了仿真。给出了改进前后的网络生存时间、簇首个数和能量消耗仿真结果。仿真结果证明，本优化方案能使节点分布更加合理，能较好地均衡网络中的能量消耗，这在一定程度上延长了整个网络的生命周期。

［1］Pottie G J，Kaiser W J.Wireless integrated network sensors［J］.Communications of the ACM，1999，43(5):279 －286.

［2］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):660 －670.

［3］Liang Ying，Yu Haibin.Energy adaptive ouster-head selection for wireless sensor networks［C］//Proceedings of the Sixth International Conference on Parallel and Distributed Computing，Applications and Technology，2005:634 －638.

［4］Zhang Jiali，Huang Benxiong，Lai Tu，et al.A cluster-based energyefficient scheme for sensor networks［C］//Proceedings of the Sixth International Conference on Parallel and Distributed Computing，Applications and Technologies，2005:191 －195.

［5］Bianchi G.Performance analysis of the IEEE 802.11 distributed>coordination function［J］.IEEE Journal on Selected Areas in Communications，2000，18(3):535 －547.

［6］Mhatre V，Rosenberg C.Homogeneous vs.heterogeneous clustered sensor networks:a comparative study［C］//Proceedings of 2004 IEEE International Conference on Communications，2004:3646 －3651.

［7］Mhatre V，Rosenberg C.Design guidelines for wireless sensor networks:communication，clustering and aggregation［J］.Adhoc Networks Journal，Elsevier Science，2004，2(1):45 －63.

［8］Akkaya K，Younis M.A survey of routing protocols for wireless sensor networks［J］.Elsevier，Ad Hoc Networks，2005(3):325 －349.

［9］Jiang Q F，Manivannan D.Routing protocols for sensor networks［C］//Consumer Communications and Networking Conference，2004:93 －98.

［10］Dai S，Jing S，Li L.Research and analysis on routing protocols for wirelesssensornet works［C］//Communications Circuits and Systems，2005 International Conference，2005:407 －411.

［11］靳伟，廖延彪，张志鹏.导波光学传感器原理与技术［M］.北京:科学出版社，1998:254－255.

［12］王艳菊，王玉田，刘静.CH检测系统微弱信号处理电路研究［J］.仪表技术与传感器，2006(8):41－43.

［13］李政颖.煤矿瓦斯多通道光纤传感检测仪的研究与开发［D］.武汉:武汉理工大学，2007.

［14］林凌，洪权，李刚，等.模拟乘法器MLT04在高精度微弱光信号锁相检测电路中的应用［J］.光电子技术，2005，25(4):263－266.