一种一种LEACH协议的改进算法协议的改进算法LEACH_EH
当前,无线传感器由于技术的发展得到更加广泛的应用,针对无线传感器网络(WSN)[1]的研究也越来越多,
无线传感器网络路由协议[2]成为了一个重点研究对象。按照时间先出现了Flooding算法、SPIN算法、SAR算法
和定向扩散(Directed Diffusion)等平面路由算法,其后又研究出了LEACH算法、TEEN算法、HEED算法[3]及
PEGASIS算法等层次路由算法。LEACH算法由于其不同于以往路由算法的指导思想成为以后层次路由算法设计
时的参考标准,针对LEACH算法的自身局限性进行改进也成为了一个研究热点。参考文献[4]提出了一种休眠簇
头的算法,它一次性选出所需要的工作簇头和休眠簇头,并且只分一次簇,减少了LEACH协议中多次选举簇头
和分簇带来的能量耗损。
摘摘 要要: 根据
关键词 关键词:
当前,无线传感器由于技术的发展得到更加广泛的应用,针对无线传感器网络(WSN)[1]的研究也越来越多,无线传感
器网络路由协议[2]成为了一个重点研究对象。按照时间先出现了Flooding算法、SPIN算法、SAR算法和定向扩散(Directed
Diffusion)等平面路由算法,其后又研究出了LEACH算法、TEEN算法、HEED算法[3]及PEGASIS算法等层次路由算法。
LEACH算法由于其不同于以往路由算法的指导思想成为以后层次路由算法设计时的参考标准,针对LEACH算法的自身局限性
进行改进也成为了一个研究热点。参考文献[4]提出了一种休眠簇头的算法,它一次性选出所需要的工作簇头和休眠簇头,并
且只分一次簇,减少了LEACH协议中多次选举簇头和分簇带来的能量耗损。参考文献[5]提出了LEACH-C算法,它提出各个节
点把自身的剩余能量和位置信息发送给Sink节点,由Sink节点进行分簇。参考文献[6]在簇头选取中加入剩余能量,并且结合平
面拓扑、层次拓扑和基于位置拓扑的优点形成混合型拓扑类型,修改LEACH协议中单轮成簇为双轮成簇。参考文献[7]提出了
一种名为LEACH_SD(LELACH_Sensoring Denomina-tion)的协议,它提出了基于网络覆盖的路由生成思想。参考文献[8]
基于节点的剩余能量和位置对LEACH协议进行了改进,将选簇过程分为临时簇头选择和正式簇头,把传感器节点的节点剩余
能量值和几何平均位置作为选簇的重要因素,在此基础上选出区域内最佳簇头。参考文献[9]提出根据节点剩余能量进行筛
选,剩余节点能量较低的暂时不进行采样,以此减少参加采样节点数量,其次对簇形成阶段不正常的节点进行放弃处理。以上
改进方法在特定情况下都能够延长网络的生命周期。
本文结合LEACH协议的特点,提出改变原来LEACH协议先选择簇头后进行分簇的顺序,而是先进行均匀分簇,而后进行
簇头选举的过程。
1 LEACH协议协议
1.1 算法介绍
LEACH算法是由MIT的Chandrakasan等人为无线传感器网络专门设计的低功耗自适应聚类路由算法(Low Energy
Adaptive Clustering Hierachy)。它的基本思想是:将协议的运行过程分成一个个轮(round),每一轮由簇形成阶段和簇的
稳定工作阶段组成[8]。在簇的形成阶段,每一个节点都会生成一个随机数,然后与一阈值T(n)进行比较,阈值T(n)计算
式为:
T(n)=,n∈G0 ,n?埸G(1)
其中,P为期望的簇头节点的百分比,即每个节点成为簇头节点的概率;r为当前轮数;G是最近1/P轮为当选簇头的节点
集合。
如果该节点的随机数小于阈值T(n),则该节点就当选为簇头节点,同时广播自己成为节点的控制帧,所有当选簇头的
节点广播完控制帧后,未当选的普通节点根据收到的控制帧信号强度选择加入到相应的簇头,发送给该簇头加入控制帧。该过
程结束后,簇头节点整理自己接收到的加入控制帧,采用TDMA的方式为相应的簇内节点分配发送时隙,簇就形成了。
在簇稳定工作阶段,簇内节点将收集到的数据在自己的时隙内发送给簇头节点,簇头节点将收集到簇内节点的数据进行处
理、融合,然后将融合后的数据发送给Sink节点,由Sink节点再发送给远程数据处理中心进行处理。这个过程重复进行数次,
之后,再进行簇的形成,以此往复,不断循环。
LEACH协议在簇形成阶段,每个节点都会轮流地成为簇头节点,前面几轮已经当选为簇头的节点,在后面的若干轮都无
法再担任簇头,这就使得所有节点都能够作为簇头来分担作为簇头时能量消耗较大的问题。使得能量消耗能够均衡地分摊到各
个节点,各个节点的能量消耗就能够更加一致,有效延长了网络的生存周期。
1.2 LEACH算法的不足
由于在簇头节点形成过程中,节点当选为簇头的概率是一样的。这样,可能会出现节点剩余能量较多的节点每次都在比较
靠后的轮次当选簇头节点,而节点剩余能量较少的节点在比较靠前的轮次当选簇头,一些节点的能量消耗就会过大。同时,如
果一轮中选举出的簇头节点距离不合适,势必会造成簇头节点内的簇内节点数目不均衡;或者是簇内节点到簇头节点的距离过
大,或者是簇头节点过多或者过少。
上述几种情况都会加重个别簇头节点的负担,不利于均衡节点能耗。本文提出了一种基于K_MEANS算法的先分簇,再选
举簇头的改进算法。该算法首先随机选取几个簇头,然后使用K_MEANS算法进行迭代,找出最优或者部分最优的分簇形式,
接着根据节点剩余能量和距离该簇质心的距离选举出簇头,之后进入簇的稳定工作阶段。
LEACH算法是先选举簇头再形成簇,这种成簇过程带有很大的随机性,直接导致簇头距离不合适,各个簇内节点数目不
评论0