一种无线传感器网络路由协议LEACH的改进算法
2015-07-22李兰英刘昌东
李兰英++刘昌东
摘 要：针对低功耗自适应集簇分层型协议LEACH（low energy adaptive clustering hierarchy）的节点生命周期短和能量消耗不平衡的问题，提出了一种LFACH协议的改进算法.算法的主要思想是考虑了节点的当前位置以及当前能量，从而可以使簇头的分布更加均匀，延长节点的生命周期，对改进后的LEACH协议和原LEACH协议进行仿真，结果表明改进后的协议在生存时间上提高了40.7%，并增加了数据的发送量，减少了节点的能量消耗.
关键词：无线传感器网络；LEACH协议；网络生存时间：NS-2仿真；能量均衡
DOI： 10.15938/j.jhust.2015.02.014
中图分类号：TP391.1
文献标志码：A
文章编号：1007-2683（2015）02-0075-05
0 引 言
无线传感器网络WSN（ wireless serisor net-works）被认为是21世纪最重要的技术之一，是一种南大量无线传感器节点组成的白组织多跳网络，其日的是协作地感知、采集和处理网络覆盖区域感知对象的信息，并发送给观察者，传感嚣、感知对象和观察者构成了传感器网络的3个要素.传感器节点由汇聚节点SN（sink node）和普通传感器节点组成.无线传感器网络节点一般以电池供电，但针对应用业务的不同需求，有时需要太阳能、震动能、风能、热能等额外能量提取技术.WSN的能耗主要分为通信能耗、感知能耗和计算能耗，其中通信能耗所占比重最大，所以均衡通信能耗能有效的延长整个网络的生存时间，在无线传感器网络中，网络的拓扑控制与优化重要性表现在：影响整个网络的生存时问；减小节点间通信干扰，提高网络通信效率和为路由协议提供基础，
在无线传感器网络体系结构中，网络层的路由技术对无线传感器网络的性能好坏有着重要影响.随着国内外无线传感器网络的研究发展，许多路由协议被提了出来，从网络拓扑结构的角度可以大体把它们分为两类：平面路由结构和层次路由结构，层次路由算法是现有无线传感器网络路由算法的研究重点，下面将概述一下LEACH路由协议研究：LEACH是无线传感器网络中提出的第一个层次型路由协议，运用了数据压缩技术和分层动态技术，通过随机选取某些节点为簇头来均衡网络内部负载；文描述了一种基于LFACH的改进型非均匀分簇协议UCS（unequal clustering size），协议的中心思想是：考虑候选簇头节点到基站的远近，构造出大小非均匀的簇，从而实现了网络中节点能耗的均衡；文中的LEACH-C是LEACH协议自身的提出者后来在LFACH协议上所做的改进算法；文提出的TEEN（threshold sensitive energy efficient sen-sor network protocol）是阈值敏感能量高效传感器网络协议，它采用与LEACH类似的簇结构和运行方式，定义了软、硬两个阈值来确实是否发送数据；文提出的混合有效能量分布式分簇HEED（hybirdenergy-efficient distributed clustering）算法是在LEACH算法簇头分布不均匀这一问题基础之上做出的对LEACH协议的改进；在文中，高能效传感器采集信息协议PFGASIS（power-efficientgathering in sensor information system）是使用贪婪算法GA（greeciy algorithm）形成链式的簇结构；文中，LEACH-M协议中引入了遗传模拟退火算法.
LEACH算法与一般平面多跳路南算法相比，可以将网络生命周期延长15%，但却存在簇受开销大、重复形成簇和簇规模分布不合理等不足，为此本文提出一种改进算法.
1 LEACH协议简介
L l 算法概述
LEACH协议是由MIT的Hei nzelman等提出的，该算法是为无线传感器网络设计的一种低功耗自适应的分层路由协议，假定了一个均匀的、节点能量有限的密集传感器网络，各节点向接收点报告其数据.LEACH协议将基于TDMA的MAC协议与聚类协}义和一个简单的“路由”协议集成在一起，其基本思想是：通过循环的方式随机选择簇头节点，对簇头节点进行轮换，把整个网络的能量负载平均分配到各个节点上，从而平衡和降低能耗、延长网络的生存周期.
LEACH协议提出“轮”的概念，算法的执行过程是周期性的，每轮循环分为簇的建立阶段和稳定的数据通信阶段，在簇的建立阶段，随机选择节点作为簇头节点，簇头节点确定后即向周围广播信息，其他节点根据接收到的广播信息信号的强弱来选择要加入的簇，并告知相应的簇头节点，从而网络被划分为若干个簇.在数据通信阶段，网络完成簇结构构建，普通节点将采集数据发送给簇头节点，由簇头节点对数据进行处理（如数据融合）操作，再转发给汇聚节点，为了避免额外的处理开销，数据通信阶段一般持续较长的时间.每一轮结束后，网络将重新进入下一轮，继续执行这两个阶段的过程.
LEACH算法选举簇头的过程如下：节点产生一个0-1之间的随机数，如果这个数小于阈值T（n），则发布自己是簇头的公告消息.在每轮循环中，如果节点已经当选过簇头，则把T（n）设置为0，这样该节点就不再会再次当选为簇头，对于未当选过簇头的节点，则将以T（n）的概率当选；随着当选过簇头的节点数目增加，剩余节点当选簇头的阈值T（n）随之增大，节点产生小于T（n）的随机数的概率随之增大，所以节点当选簇头的概率增大，当只剩一个节点未当选时，T（n）=1，表示这个节点一定当选.T（n）如式（1）所示：其中：P簇头在所有节点中所占的百分比；r是选举轮数；rmod（l/P）代表这一轮循环中当选簇头的节点个数；G这一轮循环中未当选过簇头的节点集合.
采用这种随机选举簇头的方法，需要得到节点总数与簇头数的最优比；因为基站是在远离仿真区域的位置，与距离较远的节点通信时，需要设置一些簇头节点提升通信的效率，但是也不能过多（在极端情况下，每一个节点都是簇头，和没有分簇是一样的，没有多跳和数据融合优势），在相对低的比值处有一个最优的数值；在一种典型的情况下，Heinzelman等认为最优值是5%，但是这要依赖于特定的设置并且要求预先确定.
LEACH协议采用了随机选举簇头的方式来轮换簇头，避免了簇头过分消耗能量，采用数据融合则有效地减少了通信量，与一般的多跳路由协议和静态聚类算法相比，能够将网络生命延长15%.
1.2 算法不足
1）由于LEACH协议是假定所有节点都能直接和基站进行通信，而且每个节点都具备支持不同MAC的能力，因此该协议不大适合在大规模部署的应用场景.2）LEACH协议没有说明簇头节点要怎么分布才更加均匀，有可能在实际应用中出现一个区域有很多的簇头节点，而有的很大的区域没有任何的簇头节点，这样会出现网络能耗不均衡.3） LFACH协议假定每个节点的能耗都差不多，这使得该协议不适用于节点能量不均衡负载的网络部署中.4）LEACH协议的簇头选举算法没有考虑剩余能量低的节点当选为簇头节点的情况，该节点很快会耗尽能量提早失效.不利于延长网络的生存时间，网络的鲁棒性也不好.5）簇头节点将采集到的数据通过数据融合后直接发送到基站，若传感器节点分布在很广的范围内，经过很多轮后，距离基站近的簇头节点与距离基站远的节点剩余能量相差很大；如果传感器节点的初始能量值一致，距离汇聚节点远的节点能量最先消耗完，从而导致整体网络生存时间缩短；假设簇头节点和汇聚节点之间只采用多跳路由方式转发数据，那么在网络节点部署区.域广、节点数日众多的情形下，距离基站近的区域的节点因为频繁参与数据的转发，能量消耗极快，该区域的节点反而很容易死掉，进而影响整个网络的生命周期.针对LEACH路由协议的不足，本文提出一种改进的算法，我们且称为NEWLEACH.
2 LEACH协议的改进算法
2.1NEWLEACH算法的基本思想
因为涉及到距离，先简单介绍下LEACH的物理模型：LEACH算法采用第一顺序无线电能量模型FORM（first order radio model），该模型由发送电路、放大电路和接收电路组成.假定信道是双向对称的，即节点A传送数据到节点B的能量消耗与B传送到A是相同的.在传输距离为d时，传感器节点发送和接收kbits消息所消耗的能量见式（2）和式（3）.其中：E是发送电路和接收电路无线电通信消耗的功率值，信号传输距离为d.信号在无线信道传输中的能量消耗与距离dr成正比，在短距离无线传输，即d
本文的算法基本思想是：从上面的能量消耗模型可以看出，能量消耗其实也和距离有关，在设计优化的簇头选举方法时，应该根据距离来选择不同的能量衰减模型；簇头的最优选择应该是，在当前轮数剩余能量较高的，又或者是距离基站更近的节点，在数据的通信阶段，应该选择当前轮剩余节点剩余能量最高的节点进行数据融合，如果该节点恰好是簇头节点，在完成数据融合后，将数据发送给基站；如果是普通节点，在完成了数据融合后，将数据转发给簇头节点，簇头节点再发送给基站.
2.2 NEWLEACH算法
2.2.1簇头选举
假设仿真区域是在100m×100m的区域内进行的，基站的坐标是在（50，175），我们称为bs，存仿真区域内有一个中心点，我们称为center，任一节点到bs的距离为（d1，到centei‘的距离为d2，如图l所示.从图中我们可以看出d1》d2，因此在设计距离因子时，把节点到基站的距离看成多路信道衰减模型，把节点到中心点的距离看成自由空间衰减模型根.据不同的情况选用不同的模型，使得距离基站近的有更大几率当选为簇头.
传统的LFACH协议不涉及节点的剩余能量问题，改进的NEWLEACH算法用节点的当前剩余能量和初始能量相比，这样做可以使剩余能量更多的节点有更大几率称为簇头，
改进后的簇头选举如式（4）所示.式（4）是在式（1）的基础上做的一个改进：在最坏的情况下（‰…。《E..州且d。《d，），式（4）和式（1）是等价的，在其他的情形下，式（4）能够在一定的程度卜优化簇头的选举情况. -P[rmod（l/P）…案+卢羔]胙r（n）：I -P[rmod（l/P）
C，（4）
0，其他.其中：k为最佳簇头数；理为能量因子；E。。。。.为当前节点的剩余能量值；E训为当前轮所有节点的剩余能量总值；β为距离因子；定义β=1-a，d2为节点到中心点的距离；d1为节点到基站的距离.
2.2.2数据通信
每一轮都有一个数据通信阶段，因为要进行数据融合，这将消耗非常多的能量，而簇头也在簇的建立阶段消耗很大一部分能量，有可能不再是簇内能量最高的节点了，因此，本文采用的方法是：簇建完后，在本簇内寻找一个剩余能量最高的节点，不一定非是簇头节点，进行数据融合后，再发送给基站，这将会减少簇内簇头节点的耗能，对平衡整个簇内的能量起到至关重要的作用.
3 仿真结果及分析
假设在100m×100m的范围内随机播散100个节点，基站坐标为（50，175），节点的初始能量为2J，最佳簇头数为5个.在LinuX平台下，利用NS-2软件对LFACH算法和改进后的算法NE—WLEACH进行仿真实现.
3.1 确定α，β的取值
NEWLFACH改进协议的目的是为了使网络整体寿命延长，因此我们用节点的生存时间为指标做了仿真，如图2所示.在图中用NEWLEACHX中的最后一个数字代表了lOa，例如NEWLFACHI代表了a=0.1，α从0.1到1每隔0.1取值一次，共9组数据.从图中可以看出NEWLFACH4表现最好，因为第一个节点死亡较晚，而且整个网络的生存时间也较长，其他的取值要么死亡节点出现过早，要么整体寿命太短，所以取值α=0.4，p=0.6.
3.2 网络生存时间对比
网络生存周期对比如图3所示，较长的是NE-WLEACH，较短的是LEACH.从图中可以看出，NE-WLEACH整体寿命延长了，首次出现死亡节点是在380s，而LEACH首次出现死亡节点是在270s.LEACH在490s的时候只有6个存活节点，而NE—WLEACH在81Os时还有8个节点存活，节点寿命延长了40.7%.
3.3基站接收数据对比
基站的接收数据对比图如图4所示，在前490s，NEWLEACH和LEACH的发送数据量相差不大，所以曲线基本重合了.LEACH在490s时向基站发送了l116429bit数据，NEWLEACHA-810s时向基站发送了2338967bit个数据，说明改进后的协议数据通信能力也得到了提高，但是存在一样的时间里面，基站接收的数据差异并不那么明显.
3.4能量消耗对比
节点的能量消耗对比如图5所示，在上面的是LFACH，下面的是NWELEACH.在初始能量一致的情况下，在前120s内，改进后的协议消耗较快，有可能足计算各个节点的位置所消耗了一部分能量，但是在很大一部分时间内，LEACH要比NE-WLEACH能量消耗快得多，也说明了改进后的协议在能耗上也有了改善.
4 结 语
本文分析了LEACH协议的簇头选举过程，针对其存在的缺陷，提出了一种基于位置和剩余能量的新的簇头选举方法，通过仿真对比发现：新的算法延长了网络节点生存时间，增加了节点与基站的通信量，也减少网络节点能量的消耗；但是在通信阶段，在相同的时问里，基站接收到的数据相差并不大，说明了新协议在数据的融合方面并没有得到显著的改善.另外，在仿真的初期，整体的能量消耗要比LEACH高一些，这是今后需要改进的地方，希望本文的研究思路及结果对研发适用性广、性能稳定高效的新型无线传感协议有所帮助.
