无线传感器网络路由协议LEACH的研究与改1.doc

1、无线传感器网络路由协议LEACH的研究与改进摘要:无线传感器网络由许多具有低功率无线收发装置的传感器节点成,能够有效地感知、采集和处理网络覆盖区域中的相关信息,并发送给远处的基站进一步处理。由于传感器节点能量有限,路由协议必须尽可能地减少能量消耗,延长网络生命周期。在LEACH算法基础上,提出一种改进的路由算法,改进后的算法采用相对固定的成簇方式,每隔一轮重新构建簇。利用图论中的prim算法,选择每轮中Ped最大的簇头作为根节点,在簇头节点之间构造树形路由,簇头之间以多跳方式将收集到的数据发送到根节点,然后通过根节点将整个网络收集到的数据发送到基站。仿真结果表明,与LEACH算法相比,改进算法

2、降低了能耗,有效延长了网络生存周期。关键词:无线传感器网络; LEACH算法; 分簇;生命周期;能量消耗Abstract: W ireless sensor networks consisting of a large number of small sensorswith low-power transceiver can be an effective tool for apperceiving, collecting and computing data in a variety of environment.The collected data mustbe transmitted t

3、o the base station for further processing. Based on LEACH algorithm, this paper presents a novel clustering algorithm in which cluster are relatively fixed and the nodes re-organize themselves into new clusters every other round. It utilizes the Prim algorithm in the graph theory to form tree routin

4、g among cluster-head nodes, and selects the cluster-head with the largestPedas the root node. The cluster heads send data to the root node in a multi-hop manner and the root node then sends the gathered data by the whole network to the base station. Simulation results show that compared with LEACH,

5、the improved algorithm can reduce the energy consumption and prolong the lifetime of the network.Key Words：wireless sensor network, LEACH algorithm, clustering, lifetime, energy consume1、前言无线传感器网络被认为是在一定空间范围内密集分布的由大量体积小、廉价、电池供电的通信器件构成的自组织系统由于无线传感器网络大都需要在无人看管、不更换电池或者几乎不可能更换电池的条件下长时间的工作，如何提高能量的有效利用率并延

6、长网络寿命便成了一个重要问题网络数据传输离不开路由协议,路由协议对网络的整体性能有重要影响,因此,作为无线传感器网络核心技术之一的路由协议一直是研究的热点。路由算法在路由协议中起着至关重要的作用,无线传感器网络中的路由算法从网络逻辑结构角度可以分为平面路由和层次路由。层次路由算法是无线传感器网络路由算法的研究重点,其中,LEACH算法是比较具有代表性的层次型路由算法。本文在LEACH算法的基础上,介绍一种改进的路由算法,改进算法的成簇方式相对固定,减少了构造簇的能量消耗。簇形成之后,在簇头间构造最小生成树,簇间通过多跳方式通信,降低了簇头节点之间长距离通信的能耗。2、LEACH 算法2.1算法

7、描述： LEACH协议的操作是按轮进行的,每一轮包含簇建立和稳定运行2个阶段,在簇建立阶段,自适应分簇结构形成,在稳定运行阶段进行数据传输。在簇建立阶段,选取一定数目的节点充当簇头节点。每个节点随机分配一个在0到1之间的数字,成为其标志值。如果节点的标志值小于门限值T(n)的话,该节点就充当本轮的簇头节点。门限T(n)定义如下：T(n)=p/(1-p*(rmod(1/p)nGT(n)=0其他式中p为网络中簇头节点所占总节点数目的百分比; r为当前的轮数;G为一个集合,集合中的节点是前1/p轮中没有充当过簇头节点的节点。使用这个门限,每个节点会在1/p轮操作内充当一次簇头节点。等过了1/p轮以后

8、,所有的节点都充当过簇头节点,从而又可以重新充当簇头节点。节点被选为簇头后,就向外发送广播信息;其他节点就根据收到消息的信号强弱,选取信号最强的发送源节点作为自己的簇头节点,加入那个簇,并向簇头发送加入的请求。簇头收到请求后为成员节点设定一个TDMA时隙表。此后的簇稳定阶段,节点在属于自己的时隙里将采集的数据发送给簇头节点,簇头节点将接收到的成员节点的数据进行融合,然后,直接发送给基站。2.2LEACH算法的不足及其改进算法在LEACH算法中,每一轮循环都要重新构造簇,而构造簇的能量开销比较大。其次,远离汇聚节点的簇头节点可能会由于长距离发送数据而过早耗尽自身能量,造成网络分割。另外,LEAC

9、H算法没有考虑簇头节点当前的能量状况,如果能量很低的节点当选为簇头节点,那么将会加速该节点的死亡,影响整个网络的生命周期。3、改进的算3.1改进算法的基本思想本文的改进算法也按轮的机制运行,但是与LEACH不同的是,改进后的算法不必每一轮都重新构建簇。改进算法运行到第N轮,当N为奇数时,新算法采用与LEACH-EA相同的机制选择簇头,这样产生的簇头在新算法中称为活动簇头,活动簇头选定后,该活动簇头发布自己是簇头的消息,非簇头节点根据接收信号的强弱来选择加入哪个簇,并通知相应的活动簇头,完成簇的建立。簇建立之后,簇内节点通过单跳通信方式直接向其簇头节点传送数据。当N为偶数时,原来的簇固定不变。如

10、果此时活动簇头节点能量低于某一个门限值时,则在原簇内重新选择簇头节点,以簇内剩余能量最多的节点为新的簇头节点,这样产生的簇头在新算法中称为固定簇头。为降低簇头(包括活动簇头和固定簇头)节点的通信代价,在簇头间构造树形路由,簇头间以多跳方式通信。3.2改进算法的描述（1）簇的建立和簇内通信改进算法第N轮的开始,首先判断N是奇数还是偶数。当N是奇数时,就需要重新构建簇,此时,采用与LEACH-EA相同的簇头选择机制。活动簇头选择过程如下:每个节点产生一个01之间的随机数,如果这个数小于阈值T(n),则该节向周围节点广播它是簇头的消息,参照LEACH-EA的阈值计算公式T(n)可表示为:T(n)=（

11、p（1-p*(rmod(1/p)）（En-currentEaver）, nGT(n)=0,其它其中,p是簇头占所有节点的百分比,即节点当选簇头的概率;r代表目前进行的轮数;G表示最近1/p轮中还未当选过簇头的节点集合;En-current表示节点的当前能量;Eaver表示每一轮结束后节点的平均能量。节点当选为活动簇头后,该活动簇头广播自己是簇头的消息,非簇头节点根据接收信号的强弱。选择加入哪个簇,并通知相应的活动簇头,完成簇的建立。活动簇头接收到所有的加入信息后,就产生一个TDMA定时信息表,给簇中每个非簇头成员节点分配传送数据的时间片,成员节点只能在其特定的时间片内与簇头节点进行通信。算法执

12、行首轮时,簇的建立与此种情况相同。当N是偶数时,则原来的簇固定不变。如果活动簇头节点能量低于某一个规定的门限值,则在原簇内重新选择簇头节点,以簇内剩余能量最多的节点为簇头节点,这样产生的簇头称为固定簇头。固定簇头与簇内成员的通信方式和活动簇头一样。当节点持续采集监测数据时,在其相应时间片,使用最小能量传给簇头节点。节点不发送数据时,关闭节点以节约能量。簇头节点必须保持其接收器一直打开,以接收簇内不同节点的数据,然后进行数据融合。3.2.2簇头间树形路由的构建与簇间通信假设要在n个城市之间建立通信联络网,则连通n个城市只需要n-1条线路。如果用连通网的顶点来表示城市,边表示两城市之间的线路,赋予

13、边的权值代表相应的代价,需要考虑如何在最节省经费的前提下建立这个通信网。对于n个顶点的连通网可以建立许多不同的生成树,每一棵生成树都可以是一个通信网,要选择一棵生成树,使总的代价最少,这就是构造连通网的最小代价生成树(Minimum Cost Spanning Tree)问题7(简称为最小生成树问题)。考虑将此问题中的城市与无线传感器网络中的簇头节点相对应,可以在簇头节点之间构造最小生成树,降低簇头节点间的通信代价。prim算法构造最小生成树的过程:假设N=(V,E)为连通网,V表示网中顶点的集合,E表示边的集合,U是V的一非空子集,TE为最小生成树中边的集合。首先,从集合V中取一个顶点V0加

14、入集合U中,这时U=V0,集合TE=,接着重复执行以下操作:从V0出发,在集合V中寻找与U中顶点相邻顶点中权值最小的边的另一顶点V1,然后将V1并入U中,并将该边加入集合TE中,直到U=V为止。这时TE中有n-1条边,T=(U,TE)为N的最小生成树。本文参照文献5,利用prim算法构造最小生成树的原理在簇头间构造树形路由,在文献5的基础上进行了改进,过程如下:1)选出的簇头节点将自己的剩余能量和到基站的距离加入到广播数据包中进行广播,根据其剩余能量和到基站的距离关系参数Ped,选取Ped最大的簇头节点作为树根节点。Ped的定义公式:Ped(i)=Ey2(i)De(i)(3)其中,i是传感器节

15、点编号,Ey(i)是节点i的剩余能量,De(i)是节点i到基站的距离。2)利用prim算法构造最小生成树原理,树根节点选择下一跳中最小有效簇头节点作为其子节点,该子节点以树根节点为父节点,同时向下一跳簇头节点继续搜索。若该子节点搜索成功,则继续执行路由算法,若没有搜索到最小有效簇头节点,则返回该根节点继续搜索。3)重复2),直到所有节点加入到树中,构成树形网络路由。簇头节点通过树网络路由,以多跳方式通信,最后作为树根节点的簇头将数据传给基站。簇头间的树形路由如图1所示。4、算法的仿真分析采用Matlab仿真工具,对LEACH算法、LEACH-EA算法和改进的算法进行仿真比较。仿真场景假设有10

16、0个传感器节点组成,节点随机分布在一个介于(x=0,y=0)与(x=100,y=100)的区域内,每个节点都拥有相同的初始能量E0=0.5J,仿真模型参照文献6。如图2所示,前1000轮中, LEACH和LEACH-EA算法的节点存活数比较接近,改进算法相对来说比前两种算法更优越。网络生命周期是衡量网络质量的一个重要标志,图3显示了当节点死亡率为1%,50%,100%时所经过的轮数。从图中可以看出新算法的通信轮数高于LEACH和LEACH-EA算法,表明改进之后得到的新算法降低了能耗,延长了网络的生存时间。5、参考文献1Tao Yang,Zheng Yaling.The combination

17、 of the optimal number of cluster-heads and energy adaptive cluster-head selectionAlgorithm in wireless sensor networksC.WiCOM 2006 International Conference.Wuhan,China,2006:1-4.2Hou Guofeng,Tang K W.Evaluation of LEACH protocol subject to different traffic modelsC/COIN-NGNCON 2006.Hyatt Regency Jej

18、u,Korea,2006:281-283.3Heinzelman,W.R.,A.Chandrakasan,andH.Balakrishnan.Energy-Ef-ficient Communication Protocol for Wireless Microsensor Networks,Proc.of the 33rd AnnuaHawaiiInternationalConferenceonSystemSciences,January47,2000.Maui,Hawaii.p.3 0053 0144Handy MJ,Haase M,Timmermann D.Low energy a-dap

19、tive clustering hierarchy with deterministic clus-ter-head selectionA.Proc of the 4th IEEE Conf onMobile and Wireless Communications NetworksC.Stockholm: IEEE Communications Society, 2002.368-3725王振兴,熊伟丽,徐保国.基于LEACH的簇树网络路由算法研究J.计算机测量与控制,2008,16(11):173517376 Wendi B. Heinzelman, Anantha Chandrakasan

20、, HariBalakrishnan. An application-specific protocol architec-ture for wireless microsensor networks J. IEEETransactions On wireless Communications,2002,1(4):6606707李保强，面向无线传感器网络的低能耗关键技术研究【学位论文，西北工业大学，2005. 3.8孙利民李建中陈渝等编无线传感器网络清华大学出版社2005.59吴臻,金心宇.无线传感器网络的LEACH算法的改进J.传感技术学报,2006 343610于海斌,曾鹏.智能无线传感器网络系统M.(第一版)科学出版社,2006,119139 致谢本论文是在我的导师王亚丽老师细心指导和严格要求下完成的，在此向王老师致以最崇高的敬意与最诚挚的感谢。从07年入学以来，一直深受李老师的感染，王老师严谨的治学态度、渊博的学识、为人师表的高尚品格和勇于创新的科学精神令学生终生难忘，对我在做人、工作、生活诸多方面产生了积极的影响，我深信这将使我终生受益。感谢课题组的各位同学，在与大家学习交流的过程中，我受益匪浅。感谢我的亲人和朋友对我无私的关怀和帮助。真诚感谢所有关心和帮助过我的人们! word文档 可自由复制编辑