一种基于优先级的LEACH算法改进及仿真

张岩

（西安文理学院信息工程学院 陕西 西安　710065）

一种基于优先级的LEACH算法改进及仿真

张岩

（西安文理学院信息工程学院 陕西 西安710065）

针对传统协议LEACH在簇头分布、簇头选取及数据传输等方面存在的不足，提出一种基于优先级的算法对LEACH协议簇头选举公式及簇头分布位置加以改进，保证簇头分布均匀并且处于网络节点密集区域，达到均衡能耗的目的；数据传输阶段采用单、多跳结合的方式平衡网络负载。仿真结果表明，与LEACH及LEACH-EI相比，本文算法有效延长了网络生命周期。

无线传感器网络；邻居节点；能量优先；网络生命周期

低功耗自适应分簇算法LEACH［1］是由麻省理工大学Heinzelman W.R等人于1999年提出的，它是无线传感器网络的一种分簇路由协议，更是具代表性的层次管理算法。LEACH算法通过周期性选择簇头使得各节点等概率地担任簇头，从而相对均衡了网络中节点能量消耗。本文详细分析了LEACH算法的工作原理，并针对其在簇头选举及数据传输方面的不足提出改进并进行仿真。

1LEACH协议

LEACH协议下，网络中所有节点以随机的方式轮流成为簇头节点，非簇头节点就近加入相应的簇，网络中各节点将所采集数据传输给簇头，簇头进行数据融合后再将数据包发送给基站。

1.1LEACH协议簇头选举和簇的建立

依据所需簇头比例和节点是否承担过群头来决定。每轮初时，节点产生一个[0，1]之间的随机数，次随机数如果小于阈值T（n），则此节点成为本轮工作的簇头；反之，皆为普通节，当选簇头的公式为：

其中，P是网络中簇头节点所占的比例，r是当前运行轮数，G是本轮未当选簇头的节点集合。簇头节点确立后，即广播此消息，普通节点通过所接收到的信号强弱程度发送加入最近的簇的请求。簇头节点为本簇成员建立时隙表并公布。

1.2数据通信

簇内各节点在各自时隙内将感知数据发送至所属簇头，数据如果在一个时隙未发送完，则下一时隙继续发送。簇头节点将来自本簇的数据进行压缩及融合，进而将处理后的数据传给基站。整个过程为一个稳定的通信阶段[2-3]。

2　LEACH协议不足及改进

2.1LEACH协议不足

LEACH协议簇头选举完全依赖所产生的随机数，对节点的剩余能量、分布位置等属性并未考虑在内，导致某些节点能耗过快；簇头与基站直接通信导致网络中较基站距离远的节点容易出现能量空洞。

2.2LEACH协议改进

根据LEACH算法簇头选取及数据传输方式的缺陷，本文提出一种基于优先级的分簇路由方式 LEACH-bop对LEACH算法加以改进。

2.2.1LEACH-bop算法簇头分布及选取方案

为保证簇头节点的分布比较均匀，规定任意两个簇头之间的距离应大于常数ds。此方案具体实施为：所有节点以ds/2为半径发布一个信息[4]，用以统计出自己的邻居节点数m，则簇头选取公式为：

其中，mn为节点n的邻居节点数，N为网络中节点总数，En（t）为n的当前能量，Eavg（t）为网络中节点平均能量。公式（2）认为m数最大且当前能量较大的节点首先成为本轮工作的一个簇头，进而在距离此簇头ds外按此公式产生其它簇头，既保证节点分布密集区域存在簇头节点并且簇头分布均匀，又考虑到簇头节点当前能量较大。

2.2.2数据传输方案

与LEACH算法相似簇内普通节点在各自时隙内单跳向簇头发送数据，簇头向基站发送数据的方式LEACH-bop算法作以下改进。

网络中的簇头节点与普通节点一样也有传输半径dcrosscover，当传输距离大于此值时，需要重新调整（即增大）发射功率。工作中当簇头选取完毕则有G={V，E}，V={v1，v2，…，vk}，V为簇头集，则距离基站较远的簇头结点直接向基站发送数据能量会损失较快，不利于网络能量均衡，在簇头向基站传输数据时就存在簇间通信路径的选择，假定在一个网络中均为簇头，为vi到基站的距离。则簇间数据传输方案按以下模型:

满足公式（3）的vi节点可作为vj的中转节点，vj向vi发送数据符合自由空间模型，总体能量消耗远小于多路衰减模型，减小了距基站较远的簇头的能耗，更均衡了链路能耗。LEACH-bop算法节点与簇头的通信仍采用单跳的方式，非簇头节点在相应时隙内以单跳方式直接将数据传送给相应的簇头，簇头选择单跳或多跳方式与基站通信[5-6]。

3　算法仿真与性能验证

3.1能耗模型

采用文献[1]中无线电通信模型。即节点发出大小为lbit的信息所消耗的能量为：

Eelec为单位bit数据收发能耗，dcrossove为模型划分阈值，大于 dcrossove选择多路衰减模型， 其功放能耗为 Eamp，小于 dcrossove选择自由空间模型，其功放能耗为Efs，N为节点总数，M网络监测区域边长[7-8]。

3.2仿真环境设定

仿真实验在MATLAB环境下进行，以随机方式在监测区域内部署传感器节点，假设节点分布在坐标为到的区域内。实验中仿真参数取值如表1所示。

表1　仿真模型参数取值Tab.1　Paramters’figures of the simulation model

3.3性能测试与分析

LEACH算法与LEACH-bop算法在网络生命周期内每一轮能量消耗如图1所示。

图1　两种算法能耗对比Fig.1　The comparison of two algorithms for energy consumption

仿真结果显示，模拟环境与初始能量相同时LEACH算法[9]运行7轮，第8轮出现节点能量耗尽；而LEACH-bop算法运行12轮左右开始出现能量耗尽的节点。LEACH-bop算法首节点死亡轮数较LEACH算法有明显延长，并且由图可见LEACH原算法在前7轮中网络能耗均小于LEACH-bop算法，从第8轮以后能量衰减明显较快，说明LEACH算法在每一轮的工作中考虑到了总能量最小，而缺乏对各个节点能耗的考虑。而LEACH-bop算法前期每一轮能耗都比原算法高，但是此算法各节点能耗相差较小[10]，由仿真结果可见能耗变化趋势较为平缓，即网络中各节点能耗较为均衡。

3.4对网络密度的适应性分析

将网络节点数扩展为N=200。对LEACH-bop算法、LEACH算法及基于LEACH的改进算法LEACH-EI算法进行对比。

图2显示LEACH-bop算法首节点能量耗尽是第27轮，LEACH的算法是18轮，LEACH-EI算法是23轮。即网络节点数扩展后，LEACH-bop算法与LEACH算法相比首节点死亡时的网络生命周期延长了约49%；与LEACH-EI相比，首节点死亡时的网络生命周期延长了约17%。即LEACH-bop

图2　网络节点数扩展后3种算法能耗对比

4　结束语

文中提出了基优先级的分簇路由算法（LEACH-bop）。此算法采用邻居节点数、节点当前能量等属性确定簇头[11]，给出了分簇方式和基于优先级的簇头选择公式，每轮初始阶段均按照优先级策略生成一个最具优先条件的簇头，随后在规定范围之外以同样的方式再选出其余的簇头[11]，这既保证了簇头节点分布的均衡性又兼顾了当选簇头的节点的能量及位置的优先性，即在簇头分布均匀的基础上使得其邻居节点多且能量优先；路由方式采用单、多跳结合降低网络能耗。仿真实验及对比表明LEACH-bop算法能够有效均衡网络能耗、延长网络生命周期，从整体上提升了网络性能。

[1]Heinzellnan W B，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wirelessmicrosensor networks[J].IEEE Transactions on Wireless Communications，2002，1（4）:660-670.

[2]Thein M C M，Thein T.An energy efficient cluster-head selection for wireless sensor networks[C]//2010 International Conference on Intelligent Systems，Modelling andSimulation. 2010:287-291．

[3]Li Y L，Ding L W，Liu F.The improvement of LEACHprotocolin WSN[C]//2011 International Conference on Computer Science and Network Technology，2011（2）:1345-1348.

[4]马杰良，王垚，顾蕾蕾.基于覆盖率的无线传感器网络LEACH协议研究及改进[J].传感技术学报，2011，24（12）:1777-1781.

[5]白风娥，王莉莉，马艳艳，等.无线传感器网络路由协议LEACH的算法分析[J].太原理工大学学报，2009，40（4），248-252

[6]毕艳忠，孙利民.传感器网络中的数据融合[D].计算机科学，2004，31（7）:101-103

[7]黄廷辉，杨旻，崔更申，等.基于LEACH协议的无线传感器网络密钥管理路由方案[J].传感技术学报，2014，27（8）: 1143-1146.

[8]胡星华，骆坚，谭珊珊，等.固定簇的LEACH半径自适应簇头改进算法[J].传感技术学报，2011，24（1）:79-82.

[9]韩涛，李训铭.基于静态分簇的LEACH算法改进研究[J].电子设计工程，2014（6）:109-112.

[10]李菡薏，陈家琪.云计算环境下任务调度算法的研究[J].电子科技，2015（11）:43-46，60.

[11]张飞鸽.LEACH协议簇头个数优化的研究[J].计算机与现代化，2015（9）:95-99，104.

The improvement and simulation of LEACH algorithm based on the priority

ZHANG Yan
（College of Information Engineering，Xi’an University of Arts and Science，Xi’an 710065，China）

Be aimed at the insufficient in the distribution and selection of the cluster heads，the data transmission of the LEACH protocol，this paper proposes an algorithm that improved the LEACH in the selection and the distribution of Cluster head，which Ensures the distribution of cluster heads are uniform and the cluster heads in the dense regions of nodes in the network；The data transmission adopts the methods of one-hop and Multiple-hop.The simulation results show that compared with LEACH algorithm and LEACH-EI algorithm，the scheme prolongs the life cycle of network effectively.

wireless sensor networks；neighbor node；energy priority；lifecycle of the network

TN915.04

A

1674－6236（2016）01-0077-03

2015-05-08稿件编号：201505071

国家自然科学基金资助项目（41301413）；西安市科技计划项目（CXY1443WL19）

张 岩（1982—），女，陕西蓝田人，硕士研究生，讲师。研究方向：无线传感器网络。