基于LEACH协议的链式簇头节能路由算法

米守防

(大连民族学院计算机科学与工程学院，辽宁大连116605)

无线传感器网络(Wireless Sensor Network，WSN)是由部署在监测区域内大量的智能微型传感器节点组成，通过无线通信方式形成的一个多跳的、自组织的网络系统［1-3］。其目的是协作地感知、采集和处理网络覆盖区域中被感知对象的信息，并发送给观察者。作为一种全新的信息获取和处理技术，无线传感器网络已在军事、环境科学、医疗护理、智能家居和其他领域得到广泛应用。

传感器节点是微型电子设备，体积微小，通常携带能量十分有限的电池。由于无线传感器网络部署区域环境复杂，有些区域甚至人员不能到达［3］，而且传感器节点个数多，所以传感器节点通过更换电池的方式来补给能量变得非常困难。如何合理利用传感器节点有限的能量延长网络生命周期是传感器网络协议设计所面临的首要问题［4］。将传感器节点组织成簇的形式有效的减少能量消耗，许多能量高效的路由协议都是在基于分簇(clustering)的路由基础上进行设计的［5］。

分簇技术是一种节省能耗十分有效的网络拓扑控制技术，所谓“分簇技术”就是将节点划分成许多组，称为簇，每个簇都有一个簇头和许多簇成员节点。网络定期的进行分簇，由簇头节点管理

整个簇，对簇成员节点感知的数据进行融合后再传输给汇聚节点［6］。分簇算法具有拓扑管理方便、能量利用高效、数据融合简单等优点，是当前重点研究的路由技术。其中比较有代表性的分簇路由协议是Heinzelman等人在2000年联合提出低功耗自适应分簇层次路由协议(low energy adaptive clustering hierarchy，LEACH)［7-8］。

1 LEACH协议分析

1.1 LEACH协议概述

LEACH协议是第一个基于多簇结构的路由协议，其基本思想是将网络划分为不同的簇，通过等概率周期性的选择簇头，将整个网络的能量负载相对均衡的分配到每个传感器节点，从而达到减少网络能量消耗、延长网络生命周期的目的。其中，簇头的选择是依据网络中所需要的簇头节点总数和迄今为止每个阶段已成为簇头的次数来决定的。LEACH定义了“轮”(Round)的概念，其运行分为两个阶段:簇建立阶段和稳定数据通信阶段。

在簇建立阶段，LEACH协议随机选择一个传感器节点作为簇头，在每轮簇的组织阶段，每个节点都生成一个介于0和1之间的随机数n，如果该随机数小于阀值T(n)，则该节点成为簇头。阀值T(n)按公式(1)计算。

其中，p是簇头在所有节点中所占的百分比，r为选举轮数，r mod(1/p)代表这一轮循环中当选过簇头的节点个数，G是这一轮循环中未当选过簇头的节点集合。在第0轮中，即r=0时，每一个节点都有概率为p的可能性成为簇头。

在第0轮中成为簇头的节点，在接下来的1/p轮中不会再成为簇头，在经过1/p-1轮后，T值变为1，这时还没有成为簇头的节点就被选择为簇类节点;在经过1/p轮后，所有节点再次开始平等地竞争是否当选簇头［9］。

节点当选簇头后，发布通知消息告知其他节点自己是簇头。非簇头节点根据自己与簇头之间的距离来选择加入哪个簇，并告知该簇头。当簇头接收到所有的加入信息后，就产生一个TDMA定时消息，并且通知该簇内所有节点。为了避免附近簇的信号干扰，簇头可以决定本簇中所有节点的CDMA编码。这个用于当前阶段的CDMA编码连同TDMA定时一起发送。当簇内节点收到这个消息后，他们就会在各自的时间槽内发送数据。经过一段时间的数据传输，簇头节点收齐簇内节点发送的数据后，运行数据融合算法来处理数据，并将结果直接发送给汇聚节点。

1.2 LEACH协议存在的问题

LEACH分簇协议按照一定概率随机选择簇头，簇头将簇内数据在本地数据融合后再转发给汇聚节点，减少了实际需要传输的数据量，降低了大部分节点的能量消耗;通过簇头更换机制去均衡负载耗能，从而延长网络的生存周期。但该协议并未从全局的角度考虑节能，具体有以下几点。

(1)随机选举出来的簇头概率相同，意味着少能量或者位置偏远的节点都有可能成为簇头。由于簇头节点要与汇聚节点直接通信，簇头会消耗较多的能量。

(2)随机选举的簇头，簇头需负担的簇内节点数不同，个别簇内节点相对较多的簇头负担过重，导致这个网络的负载不均衡。

(3)在选择簇头时，并未考虑簇头的剩余能量，可能某个节点成为簇头后，剩余能量不够本轮的通信使用，必然会导致该簇头的能量迅速耗尽而至死亡，整个被监测区域出现盲区。

簇头和汇聚节点通信采用单跳通信，会导致距离汇聚节点较远的簇头较早死亡，引起网络拓扑变化影响网络寿命。

2 基于LEACH协议的链式簇头节能路由算法

2.1 链式簇头节能路由协议

针对LEACH协议的上述缺点，本文在簇头和汇聚节点数据传输阶段进行了改进。以平衡总的能量消耗、延长网络的存活时间为主要设计目标，提出了一种改进的LEACH路由协议。在数据传输阶段，LEACH协议采用的是单个簇头直接传输给汇聚节点的方式，这种方式简单，但是对簇头来讲，能量消耗相对很大，尤其不适用于汇聚节点相对较远和大型网络的情况。对于簇头和汇聚节点数据传输方式的改进，首先考虑的是实现簇头之间的多跳数据通信，通过选择其他簇头中继，使数据传送的距离最小，以减少远离汇聚点的簇头能量消耗，进而延长网络的生存时间。因此，改进后的协议采用了簇头之间进行多跳传输的方式，具体如下:考虑每轮选举出的簇头剩余能量和簇头与汇聚节点间距离等因素，将簇头节点按照公式(2)所计算出值连接成链，在链中选取TCH(i)值最小的节点作为链首，值最大作为链尾(领导节点)直接与汇聚节点通信，通过数据融合，既能减少了需要传输的数据量，减少能量消耗，又能保证节点能量不会很快耗尽，而影响数据的采集。

其中，TCH(i)为簇头i权值，Er(i)为簇头i的剩余能量，Sd(i)为簇头i与汇聚节点之间的距离，为常量。

本文采用文献［10］中简单的能量消耗模型，在传输k比特信息经过距离d的过程中，发送端能量消耗为

其中，Eelec表示发射电路能量消耗;εfs和 εmp为功率放大器所消耗的能量。节点接收k比特的数据所消耗的能量为

将l个长度为k比特的数据包融合所消耗的能量为

其中，EDA为处理1比特数据需要的能量损耗。

2.2 算法描述

算法也是按轮进行运作，每轮由簇的建立和稳定数据传输两个阶段组成。簇建立阶段采用LEACH构建阶段的簇头选择和成簇方式选择簇头并成簇，簇头选举出来以后，向全网发送广播消息，节点比较收到广播的强度选择要加入的簇，并告知簇头。簇头为簇内节点创建TDMA时隙表，簇内节点按照时隙表向簇头发送数据。簇头接收数据并融合成一个数据包，同时受令牌(Token)控制，然后根据各簇头的自身情况确定Sd、d0和Er的值，依据公式(2)计算出TCH，并按照TCH的大小进行成链。使数据包顺着这个链向领导节点传送，领导节点将接收的数据融合成一个数据包发送给汇聚节点。改进后的算法流程如图1。

图1 改进后算法流程图

3 仿真实验与分析

本文采用的网络模型如下:传感器节点随机分布在一个正方形区域内;传感器节点同构，具有全网唯一的id号，能量受限，节点静止;汇聚节点固定;无线发射功率可调。使用Matlab7对LEACH协议和本文算法进行仿真，模拟参数见表1。

表1 模拟参数列表

为了更好的对比改进后协议的性能，在实验中分别的LEACH协议和改进后的协议进行了仿真。如图2给出了两种算法死亡节点数随时间变化对比，从图中可以看出本文算法相比原来的LEACH算法，在首个节点到最后一个节点死亡的时间方面要延迟很多，整个网络的生存周期也延长了很多，本算法更有效使用能量，提高了网络寿命。

图2 2种协议死亡节点个数随时间变化比较

图3给出了两种算法数据传输随时间变化对比，从图中可以本算法随着数据频率的降低，传输数据量(可靠性)整体上有所提升。从实验过程分析可看，本算法保障了簇头之间的连通性，这是提高传输可靠性的最重要因素。

图3 2种协议数据传输随时间变化比较

图4给出了两种算法随时间变化网络能量消耗比较，由图中可以看出本算法的能耗明显低于LEACH算法，这是因为在LEACH算法中所有簇头都向汇聚节点发送消息，这将消耗大量的能量，而本文算法将簇头连接成链，然后簇头采用令牌传输机制将数据传输给领导节点，领导节点融合数据并发送给汇聚节点。这样减少了各个簇头同时向汇聚节点发送数据而产生的能量，有效的延长了网络的生命周期。

图4 2种协议网络能量消耗随时间变化比较

从图3和图4可以观察到，两种算法在数据传输轮次相同既有效数据传输量相同的情况下，网络的能耗越少意味着算法更节约能量，网络的生存时间越长。而随着轮次的增加，网络消耗相同的情况，网络有效数据传输量越多意味着网络的负载能力强，生命周期也长。采用本算法比LEACH算法更加节约能量。

4 结语

本文提出了一种基于LEACH协议的链式簇头节能路由算法，核心思想就是在簇头和汇聚节点数据传输阶段进行了改进。根据簇头的剩余能量和簇头与汇聚节点间距离等因素，将簇头节点连接成链，根据规则计算出的值最小的节点作为链首，值最大作为链尾(领导节点)直接与汇聚节点通信，通过数据融合，既能减少了需要传输的数据量，减少能量消耗，又能保证节点能量不会很快耗尽，而影响数据的采集。实验证明新算法节约了网络的能量消耗，提高了数据传输的可靠性，延长了整个网络生命周期。

［1］AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，et al.Wireless sensor networks:a survey［J］.Computer Networks，2002，38(4):393-422.

［2］王文光，刘士兴，谢武军.无线传感器网络概述［J］.合肥工业大学学报:自然科学版，2010，33(9):1416-1419.

［3］孙利民，李建中，陈渝.无线传感器网络［M］.北京:清华大学出版社，2005.

［4］齐迎迎，禹继国，王楠楠.无线传感器网络的节能分布式分簇算法［J］.计算机工程，2011，37(3):83-86.

［5］刘琼，成运.一种无线传感器网络分簇路由算法研究［J］.现代电子技术，2010，33(10):162-164.

［6］周新莲.基于分簇技术的移动无线传感器网络数据收集协议研究［D］.长沙:中南大学，2010.

［7］HEINZELMAN W E.Energy-efficient communication protocol for wireless microsensor networks［C］//Proceedings of the 33rd Annual Hawaii International Conference on，2000:3005-3014.

［8］HEINZELMAN W R，CHANDRAKASAN A.And Hari balakrishnan Energy-Efficient communication protocol for wireless microsensor networks［C］//Proceedings of the 33rd Annual Hawaii International Conference on Jan 4-7 2000，2000:10.

［9］张品，徐智福，孙岩.一种新的基于簇头优化的WSN路由协议［J］.传感技术学报，2009，22(7):1013-1017.

［10］HEINZELMAN W E.An application-specific protocol architecture for wireless microsensor networks［J］.Ieee Transactions on Wireless Communications，2002，1(4):660-670.