您的当前位置：首页正文

基于LEACH的无线传感器网络分簇路由算法

来源：爱够旅游网

总第246期

2010年第4期

计算机与数字工程

Computer&DigitalEngineeringVol.38No.4

基于LEACH的无线传感器网络分簇路由算法

白凤娥　牟汇慧　姜晓荣

(太原理工大学计算机与软件学院　太原　030024)

摘　要　路由协议是无线传感器网络的重要组成部分之一,而路由算法在路由协议中起着至关重要的作用。文章在

LEACH算法基础上,提出一种改进的路由算法,改进后的算法采用相对固定的成簇方式,每隔一轮重新构建簇。利用图论

中的prim算法,选择每轮中Ped最大的簇头作为根节点,在簇头节点之间构造树形路由,簇头之间以多跳方式将收集到的数据发送到根节点,然后通过根节点将整个网络收集到的数据发送到基站。仿真结果表明,与LEACH算法相比,改进算法降低了能耗,有效延长了网络生存周期。关键词　无线传感器网络;LEACH算法;分簇;生命周期中图分类号　TP393LEACH2BasedClusteringRoutingAlgorithmforWirelessSensorNetworks

BaiFengπe　MouHuihui　JiangXiaorong

(CollegeofComputerandSoftware,TaiyuanUniversityofTechnology,Taiyuan　030024)

Abstract　Routingprotocolisanimportantpartofwirelesssensornetworkandtheroutingalgorithmplaysacrucial

roleintheroutingprotocol.BasedonLEACHalgorithm,thispaperpresentsanovelclusteringalgorithminwhichclustersarerelativelyfixedandthenodesre2organizethemselvesintonewclusterseveryotherround.ItutilizesthePrimalgorithminthegraphtheorytoformtreeroutingamongcluster2headnodes,andselectsthecluster2headwiththelargestPedastherootnode.Theclusterheadssenddatatotherootnodeinamulti2hopmannerandtherootnodethensendsthegathereddatabythewholenetworktothebasestation.SimulationresultsshowthatcomparedwithLEACH,theimprovedalgorithmcanre2ducetheenergyconsumptionandprolongthelifetimeofthenetwork.

KeyWords　wirelesssensornetwork,LEACHalgorithm,clustering,lifetimeClassNumber　TP393

1　引言

无线传感器网络(WirelessSensorNetwork,简

称WSN)是监视远程环境的有力工具之一,它的基本功能是收集并返回传感器节点所在监测区域的信息。由于工作环境和自身构造的限制,传感器节点一般是电池供电,并且节点的更换和充电也较难实现。因此,降低节点能耗,延长网络生命周期是无线传感器网络传输机制的一个主要研究目标[1]。

网络数据传输离不开路由协议,路由协议对网络的整体性能有重要影响,因此,作为无线传感器

网络核心技术之一的路由协议一直是研究的热点。路由算法在路由协议中起着至关重要的作用,无线传感器网络中的路由算法从网络逻辑结构角度可以分为平面路由和层次路由。层次路由算法是无线传感器网络路由算法的研究重点,其中,LEACH算法[2～3]是比较具有代表性的层次型路由算法。

本文在LEACH算法的基础上,介绍一种改进的路由算法,改进算法的成簇方式相对固定,减少了构造簇的能量消耗。簇形成之后,在簇头间构造最小生成树,簇间通过多跳方式通信,降低了簇头节点之间长距离通信的能耗。

收稿日期:2009年11月2日,修回日期:2009年12月5日

作者简介:白凤娥,女,教授,硕士生导师,研究方向:计算机控制与嵌入式系统,无线传感器网络。牟汇慧,女,硕士研究生,研究方向:嵌入式系统与无线自组网络。姜晓荣,女,硕士研究生,研究方向:嵌入式系统与无线自组网络。© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net

　50白凤娥等:基于LEACH的无线传感器网络分簇路由算法第38卷

2　LEACH算法

2.1　LEACH算法描述

LEACH(Low2EnergyAdaptiveClusteringHierarchy)算法是由MIT的Heinzelman等人提

基于LEACH2C的思想,针对LEACH的不足,提出了可有效解决网络能耗不均衡问题,延长网络生

命周期的LEACH2EA(EnergyAverage)算法。LEACH2EA算法的簇头选择综合考虑了节点的当

出的一种低功耗自适应分簇算法。其基本思想是以循环的方式随机选择簇头节点,将整个网络的能量负载均匀分配到网络中的每个传感器节点,从而达到降低网络能耗,提高网络生存周期的目的。

LEACH在运行过程中不断地循环执行簇的

前能量和每轮结束后的节点平均能量,比较适用于长时间运行且规模较大的网络。3　改进的算法3.1　改进算法的基本思想重构。算法操作使用了“轮”的概念,每一轮由初始化和稳定的工作两个阶段组成。在初始化阶段,每个节点产生一个0～1之间的随机数,如果某个节点产生的随机数小于所设的阈值T(n),则该节点发布自己是簇头的消息,T(n)的计算公式设为:

3T(n)=1-p(rmod(1/p))

本文的改进算法也按轮的机制运行,但是与LEACH不同的是,改进后的算法不必每一轮都重

新构建簇。

改进算法运行到第N轮,当N为奇数时,新算法采用与LEACH2EA相同的机制选择簇头,这样产生的簇头在新算法中称为活动簇头,活动簇头选定后,该活动簇头发布自己是簇头的消息,非簇头节点根据接收信号的强弱来选择加入哪个簇,并通知相应的活动簇头,完成簇的建立。簇建立之后,簇内节点通过单跳通信方式直接向其簇头节点传送数据。当N为偶数时,原来的簇固定不变。如果此时活动簇头节点能量低于某一个门限值时,则在原簇内重新选择簇头节点,以簇内剩余能量最多的节点为新的簇头节点,这样产生的簇头在新算法中称为固定簇头。为降低簇头(包括活动簇头和固定簇头)节点的通信代价,在簇头间构造树形路由,簇头间以多跳方式通信。3.2　改进算法的描述3.2.1　簇的建立和簇内通信

p,n∈G

(1)

其它

其中,p是簇头占所有节点的百分比,即节点当选簇头的概率;r表示目前进行的轮数;G代表最近1/p轮中还没有当选过簇头的节点集合。

非簇头节点根据接收信号的强弱来选择加入到哪个簇,并通知相应的簇头。在稳定阶段,簇内的节点通过TDMA方式与簇头进行通信,簇头节点接收簇内其它节点发送的数据,并将这些数据进行融合,然后发送给基站。

2.2　LEACH算法的不足及其改进算法

在LEACH算法中,每一轮循环都要重新构造簇,而构造簇的能量开销比较大。其次,远离汇聚节点的簇头节点可能会由于长距离发送数据而过早耗尽自身能量,造成网络分割。另外,LEACH算法没有考虑簇头节点当前的能量状况,如果能量很低的节点当选为簇头节点,那么将会加速该节点的死亡,影响整个网络的生命周期。

以LEACH算法的思想为基础,针对LEACH存在的不足,研究人员提出了很多的改进算法,例

如LEACH2C(LEACH2Centralized)[4],LEACH2EA(EnergyAverage)[5]等算法。LEACH2C算法

改进算法第N轮的开始,首先判断N是奇数还是偶数。当N是奇数时,就需要重新构建簇,此时,采用与LEACH2EA相同的簇头选择机制。活动簇头选择过程如下:每个节点产生一个0～1之间的随机数,如果这个数小于阈值T(n),则该节点向周围节点广播它是簇头的消息,参照LEACH2EA的阈值计算公式[6]T(n)可表示为:

T(n)=1-p(rmod(1/p))

En2current,n∈GEaver(2)

是由基站基于整个网络信息集中挑选簇头,每个节点把自身地理位置和当前能量报告给基站,基站根据所有节点的报告信息计算出平均能量,低于平均能量的节点不能成为候选簇头,基站根据所有成员节点到簇头的距离平方和最小的原则,从剩余候选节点中选出合适数量和最优地理位置的簇头集合,最后由基站将簇头集合以及簇的结构广播出去。

0,其它

其中,p是簇头占所有节点的百分比,即节点当选簇头的概率;r代表目前进行的轮数;G表示最近1/p轮中还未当选过簇头的节点集合;En2current表示节点的当前能量;Eaver表示每一轮结束后节点的平均能量。

节点当选为活动簇头后,该活动簇头广播自己是簇头的消息,非簇头节点根据接收信号的强弱来

2010年第4期计算机与数字工程　51

选择加入哪个簇,并通知相应的活动簇头,完成簇的建立。活动簇头接收到所有的加入信息后,就产生一个TDMA定时信息表,给簇中每个非簇头成员节点分配传送数据的时间片,成员节点只能在其特定的时间片内与簇头节点进行通信。算法执行首轮时,簇的建立与此种情况相同。

当N是偶数时,则原来的簇固定不变。如果活动簇头节点能量低于某一个规定的门限值,则在原簇内重新选择簇头节点,以簇内剩余能量最多的节点为簇头节点,这样产生的簇头称为固定簇头。固定簇头与簇内成员的通信方式和活动簇头一样。当节点持续采集监测数据时,在其相应时间片,使用最小能量传给簇头节点。节点不发送数据时,关闭节点以节约能量。簇头节点必须保持其接收器一直打开,以接收簇内不同节点的数据,然后进行数据融合。

3.2.2　簇头间树形路由的构建与簇间通信

余能量和到基站的距离关系参数Ped,选取Ped最大的簇头节点作为树根节点。Ped的定义公式:

Ped(i)=

Ey(i)De(i)

(3)

其中,i是传感器节点编号,Ey(i)是节点i的剩余能量,De(i)是节点i到基站的距离。

2)利用prim算法构造最小生成树原理,树根节点选择下一跳中最小有效簇头节点作为其子节点,该子节点以树根节点为父节点,同时向下一跳簇头节点继续搜索。若该子节点搜索成功,则继续执行路由算法,若没有搜索到最小有效簇头节点,则返回该根节点继续搜索。

3)重复2),直到所有节点加入到树中,构成树形网络路由。

簇头节点通过树网络路由,以多跳方式通信,最后作为树根节点的簇头将数据传给基站。簇头间的树形路由如图1所示。

假设要在n个城市之间建立通信联络网,则连通n个城市只需要n-1条线路。如果用连通网的顶点来表示城市,边表示两城市之间的线路,赋予边的权值代表相应的代价,需要考虑如何在最节省经费的前提下建立这个通信网。对于n个顶点的连通网可以建立许多不同的生成树,每一棵生成树都可以是一个通信网,要选择一棵生成树,使总的代价最少,这就是构造连通网的最小代价生成树(MinimumCostSpanningTree)问题[7](简称为最小生成树问题)。考虑将此问题中的城市与无线传感器网络中的簇头节点相对应,可以在簇头节点之间构造最小生成树,降低簇头节点间的通信代价。

prim算法构造最小生成树的过程:假设N=

(V,{E})为连通网,V表示网中顶点的集合,E表

4　算法的仿真分析

采用Matlab仿真工具,对LEACH算法、LEACH2EA算法和改进的算法进行仿真比较。仿

真场景假设有100个传感器节点组成,节点随机分布在一个介于(x=0,y=0)与(x=100,y=100)的区域内,每个节点都拥有相同的初始能量E0=0.5J,仿真模型参照文献[9]。

示边的集合,U是V的一非空子集,TE为最小生成树中边的集合。首先,从集合V中取一个顶点

V0加入集合U中,这时U={V0},集合TE={},

如图2所示,前1000轮中,LEACH

接着重复执行以下操作:从V0出发,在集合V中寻找与U中顶点相邻顶点中权值最小的边的另一顶点V1,然后将V1并入U中,并将该边加入集合

TE中,直到U=V为止。这时TE中有n-1条

和LEACH2EA算法的节点存活数比较接近,改进算法相对来说比前两种算法

图3　三种算法的网络生命周期图

边,T=(U,TE)为N的最小生成树。

本文参照文献[8],利用prim算法构造最小生成树的原理在簇头间构造树形路由,在文献[8]的基础上进行了改进,过程如下:

1)选出的簇头节点将自己的剩余能量和到基

更优越。

网络生命周期

是衡量网络质量的

一个重要标志,图3显示了当节点死亡率为1%,50%,100%时所经过的轮数。从图中可以看出新

站的距离加入到广播数据包中进行广播,根据其剩　　(下转第186页)

　186王鲁宁:固体钽电容的可靠性筛选研究第38卷

钽电容在使用中就一定会失效。假设在电容的阳极区域有一个电解质较薄的位置,电容的大部分电流(充电电流、漏电流)将流过这个位置,这个位置将被加热,如果温度上升到400～500℃之间,将会发生如下化学变化。:

4MnO2=2Mn2O3+O2

陷和失效的电容被甄别剔除,还可以使合格的电容器结构和性能更加稳定,通过失效分析,对更合理的使用电容器和提高产品质量都是有益的。

参考文献

[1]唐万军,张世莉,张建宏.固体钽电容的使用可靠性[J].微电子学,2008[2]张声飞.钽电解电容使用中的注意事项[J].电子元件

导电性能良好的MnO2化学反应后转化为导电性能差的Mn2O3缺陷位置的MnO2转化为不导电物料Mn2O3后,流过这个位置的电流将大大的减小,这个缺陷点将被有效地“弥补”,钽电容又可以正常地工作了。而因其承受功率的能力相对较低,当受到浪涌电流或高温工作时,失效的可能性会增大。和材料,1995[3]周胜海,涂有超.电解电容使用可靠性[J].大学物理实

验室,2001

[4]石伦.小型电解电容器失效模式探讨[J].电子元件和

5　结语

通过对电容器的可靠性筛选,不仅可以使有缺

材料,1996,2

[5]廉军.片式钽电容的结构及制造工艺[J].电子工业专

用设备,2009(9)

(上接第51页)

算法的通信轮数高于LEACH和LEACH2EA算法,表明改进之后得到的新算法降低了能耗,延长了网络的生存时间。

protocolforwirelessmicrosensornetwork[C]//IEEEProceedingsoftheHawaiiInternationalConferenceonSystemScience.Washington:IEEEComputerSociety,2000:3005～3014

[3]J.N.AlKarak,A.E.Kamal.Routingtechniquesin

wirelesssensornetwork:asurvey[J].IEEEWirelessCommunications,2004(11):6～28

[4]HandyMJ,HaaseM,TimmermannD.Lowenergya2

daptiveclusteringhierarchywithdeterministiccluster2headselection[C]//Proc.ofthe4thIEEEConf.onMobileandWirelessCommunicationsNetworks.Stock2holm:

IEEECommunicationsSociety,http://citeseer.

ist.psu.edu/handy02low.html,2002:368～372[5]HeinzelmanW.R.Application2specificprotocolarchi2

tectureforwirelessnetworks[Ph.D.Thesis].Boston:MassachusettsInstituteofTechnology,2000

[6]沈波,张世永,钟亦平.无线传感器网络分簇路由协议

[J].软件学报,2006,17(7):1588～1600

[7]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华

5　结语

LEACH算法是一种经典的层次型路由算法,

它利用簇头轮换机制将能量消耗较均匀地分摊到了整个网络。在LEACH的基础上提出了一种改进的路由算法,改进算法的簇相对固定,在一定程度上避免了频繁分簇造成的能量浪费,降低了整个网络的能耗。簇头节点接收簇中其它节点发送的数据,并将这些数据进行融合,通过树形路由,以多跳方式进行通信,降低了簇头节点的通信代价。仿真结果表明,该算法进一步降低了网络中的能量消耗,有效延长了网络生命周期。

本文在基于网络数据传输可以进行数据融合的前提下,对LEACH算法进行了改进,但改进算法没有考虑具体的数据融合方法。下一步的工作,将在本文算法的基础上研究如何提高数据融合与传输的效率和可靠性。

参考文献

[1]I.F.Akyildiz,W.Su,Y.Sankarasubramaniam,etal.

WirelessSensorNetworks:ASurvey[J].ComputerNetworks,2002:393～442

[2]WendiRabinerHeinzelman,AnanthaChandrakasan,

HariBalakrishnan.

Energy2efficient

communication

大学出版社,2005

[8]王振兴,熊伟丽,徐保国.基于LEACH的簇树网络路

由算法研究[J].计算机测量与控制,2008,16(11):1735～1737

[9]WendiB.Heinzelman,AnanthaChandrakasan,Hari

Balakrishnan.Anapplication2specificprotocolarchitec2tureforwirelessmicrosensornetworks[J].660～670

IEEE

TransactionsOnwirelessCommunications,2002,1(4):

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文