基于lech算法的无线传感器网络分簇路由机制研究

基于lech算法的无线传感器网络分簇路由机制研究

作为一种新的获取和处理形式，无线传感器网络（无线传感器网络，简称wsd）已成为国内外的研究热点。由于工作环境和自身构造所限,WSN网络传感器节点的计算、通信能力及能量都十分有限,对于节点的更换和充电也较难实现。因此,尽量减少节点能耗、延长网络生存时间已成为WSN网络协议及传输机制研究的一个主要目标。网络中的数据传输是靠路由协议来控制管理的,无线传感器网络具有与传统网络不同的特点,且与应用高度相关,传统路由协议不能有效地用于无线传感器网络。WSN路由协议负责在基站节点和其余节点间可靠地传输数据。由于WSN与应用高度相关,单一的路由协议不能满足各种应用需求,因而人们研究了众多的路由协议,其中LEACH(Low-EnergyAdaptiveClusteringHierarchy)协议是由美国麻省理工学院的J.Heinzelman等人提出的一种低功耗自适应分层算法,对该算法的分析研究及其改进有着重要的应用价值。1第一阶段:初始和稳定阶段LEACH算法将WSN中的所有节点分为若干簇,每个簇选举一个首领,简称簇头。算法操作时使用了“轮”的概念,每一轮由初始化和稳定工作两个阶段组成。在初始化阶段,算法随机地选取节点作为簇头,簇头向所有节点广播此消息,其它节点根据接收信号的强弱加入就近的簇,并通知相应的簇头;在稳定阶段,簇头节点接收簇中其它节点发送的数据,并将这些数据进行必要的融合,然后发送给基站节点。在本轮工作结束之后,网络将进入初始化和稳定工作的下一轮新的工作周期。1.1性确保节点成为簇头的概率,算法b初始化工作阶段,对簇头的选择是LEACH协议关键的任务,LEACH采用阈值的方式,即每个节点产生一个0～1之间的随机数,如果这个数小于阈值T(n),则该节点向周围节点广播它是簇头的消息。T(n)的计算公式为:T(n)={p1−p(rmod(1/p))0n∈G‚其他.(1)Τ(n)={p1-p(rmod(1/p))n∈G‚0其他.(1)式中:p是簇头占所有节点的百分比,即节点当选簇头的概率;r是目前进行的轮数;G是最近1/p轮中还未当选过簇头的节点集合。从公式(1)知,当选过簇头的节点在接下来的1/p轮循环中将不能成为簇头;剩余节点当选簇头的阈值T(n)增大,节点产生小于T(n)的随机数的概率随之增大,所以节点当选簇头的概率增大。p值决定了每轮产生的簇头数量,在实际应用中,最佳p值的确定是十分困难的,与网络规模和节点密度等因素有关。另外,T(n)没有考虑能量因素,这种算法必须基于两个前提假设才能达到每个节点平均耗费能量的预期目标:1)每个节点初始能量均等;2)每个节点担任簇头期间耗费的能量均等。然而,由于每个簇的大小以及簇头到基站的距离不一样,前提假设(2)不符合现实情况。1.2基于letch-h的动态分簇算法基于LEACH协议分层的思想,研究人员提出了一些新的改进算法,如LEACH-F(LEACH-Fixed)和LEACH-C(LEACH-Centralized)算法,这两种算法与LEACH算法的不同在于挑选簇头的方式。LEACH算法是由节点根据某个阈值自主决定是否当选簇头,称为分布式簇头选择算法;而LEACH-F和LEACH-C是由基站基于整个网络信息集中挑选簇头,称为集中式簇头选择算法。LEACH-F算法中,在初始阶段根据节点的初始能量,将WSN中的所有节点分为几个固定的簇,基站为每一个簇分配一个簇头列表,每个簇在每一轮结束后,根据簇头列表指示簇内节点轮流充当簇头的顺序。当簇形成以后,整个簇结构就不再发生变化,簇内节点根据簇头列表依次成为簇头。LEACH-F最大的优点就是无需每轮循环都构造簇,减少了构造簇的开销,其缺点是LEACH-F不能动态处理节点的加入、死亡和移动等情况。借助LEACH-F考虑初始因素的思想以及LEACH动态分簇的思想,针对两者的不足,提出了将节点初始能量因素考虑进来的LEACH-EI(EnergyInitializationCluster-HeadSelection)算法,LEACH-EI将节点初始能量因素考虑进来,改进了T(n)的计算公式,其公式为:T(n)={p1−p(rmod(1/p))En−cEn−i0n∈G‚其他.(2)Τ(n)={p1-p(rmod(1/p))En-cEn-in∈G‚0其他.(2)式中:En-c表示节点的当前能量;En-i表示节点的初始能量。改进后的公式(2)使能量消耗比例较低的节点优先当选簇头。然而,公式(2)有一个缺陷,即当网络运行相当长一段时间后,所有节点的当前能量En-c都变得很低,那么阈值T(n)就会变小,所有节点成为簇头的概率都大大降低,每轮当选的簇头数量减少,终将导致网络能量耗费不均衡,网络生命周期缩短的局面。LEACH-C算法根据全局信息挑选簇头,可以有效解决LEACH在每轮挑选簇头时不能确定簇头个数和地理位置的不足。采用LEACH-C算法的WSN中,每个节点把自身地理位置和当前能量报告给基站,基站根据所有节点的报告计算平均能量,当前能量低于平均能量的节点不能成为候选簇头。基于LEACH-C的思想,针对LEACH-EI的不足,提出了可有效解决网络能耗不均衡问题,进而延长网络生命周期的LEACH-EA(EnergyAverage)算法,其阈值计算公式T(n)为:T(n)={p1−p(rmod(1/p))En−cEav0n∈G‚其他.(3)Τ(n)={p1-p(rmod(1/p))En-cEavn∈G‚0其他.(3)式中En-c表示节点的当前能量,Eav表示每一轮结束后的节点平均能量。2协议模拟分析2.1接收方无线装置能耗仿真LEACH协议及其改进算法LEACH-EI,LEACH-EA算法所采用的能量模型均为第一顺序无线电模型,如图1所示。在此模型中,如果接收器、发送器之间的距离d小于某个临界值d0,则使用自由空间模型(FreeSpaceModel,记为fs);如果接收器、发送器之间的距离d大于某个临界值d0,则使用多路衰减模型(MultiPathModel,记为mp)。这个临界值d0定义如下:d0=4πL√hrhtλ.(4)d0=4πLhrhtλ.(4)式中,L表示传输损耗,hr表示接收天线高度,ht表示发送天线高度,λ表示波长。在文献中,公式(4)的参数取值分别为:L=1(表示无传输损耗),hr=ht=1.5m,无线电频率取914MHz,计算d0≈86.2m,本文取无线电频率为2.4GHz,则λ=(3×108)/(2.4×109)m,计算得d0≈125.6m.当发送方传输数据到接收方时,使用公式(5)计算其能耗:ET(k,d)=ET−e(k)+ET−a(k,d)={kEe+kεfsd2kEe+kεmpd4d＜d0；d≥d0.(5)EΤ(k,d)=EΤ-e(k)+EΤ-a(k,d)={kEe+kεfsd2d＜d0；kEe+kεmpd4d≥d0.(5)式中:k表示传输数据比特数,ET(k,d)表示发送方传输k-bit数据所消耗的能量,ET-e(k)表示发送装置消耗能量,ET-a(k,d)表示发送端信号放大器消耗能量,Ee表示电子能耗,εfs表示采用自由空间传播模型(fs)的系数,εmp表示多路衰减模型(mp)的能量系数。相应的,接收方无线装置的能耗为:ER(k)=ER−e(k)=kEe.(6)ER(k)=ER-e(k)=kEe.(6)式中:ER(k)表示接收方接收k-bit数据所消耗的能量,即接收方无线装置的能耗ER-e(k)。本文中协议仿真采用仿真工具Matlab,仿真场景如下:假设有100个传感器节点随机分布在一个介于(x=0,y=0)与(x=100,y=100)的区域内。每个节点都拥有相同的初始能量E0=0.5J,且能量无法补充,基站位置为(50,50),p=0.05(节点成为簇头的概率)。根据能量模型,数据融合消耗的能量记为EDA=5×10-9J,最大循环轮数rmax=5000轮,公式(5),(6)中取ER−e(k)=ET−e(k)=k*Ee=50×10−9J‚εfs=10×10−12J/(bit⋅m2)‚εmp=0.0013×10−12J/(bit⋅m4).ER-e(k)=EΤ-e(k)=k*Ee=50×10-9J‚εfs=10×10-12J/(bit⋅m2)‚εmp=0.0013×10-12J/(bit⋅m4).2.2剩余节点的确定借助Matlab仿真工具,通过编写Matlab程序,实现对LEACH算法,LEACH-EA算法和LEACH-EI算法的仿真比较。仿真过程如下:1)根据仿真环境的设置,每一轮都要对100个节点进行分簇,并选择不同的节点成为簇头,同时为非簇头节点选择自己所属的簇。通过每一轮的筛选簇头过程,可以将能量较高的节点选为簇头,避免由于能量消耗不均匀而影响网络生命周期。2)每一轮运行过程中,都要判断是否有死亡节点,并将每一轮的剩余节点数保存为文件表。由于网络运行过程中并不一定每一轮都会有节点死亡,因此有些轮的剩余节点数是相同的。3)根据剩余节点文件表,选出剩余节点不同的轮。由于三种算法的不同,可以通过该过程,成功记录每一种算法在运行过程中剩余节点不同的轮数。4)比较网络生命周期。在无线传感器网络中,对网络生命周期有不同的计算标准:将第一个节点的死亡时间作为网络生命周期;将50%的节点死亡时间作为网络生命周期;将节点全部死亡的时间作为网络生命周期。根据剩余节点文件表,按照网络周期的不同计算方法,选出节点死亡1%、50%和100%的轮。仿真流程图,如图2所示。2.3网络生命周期参数采用Matlab仿真平台,根据仿真过程中的数据,对仿真结果加以分析。LEACH-EI和LEACH-EA在运行完5000轮后,还有剩余节点,因此选择95%的节点死亡时间作为网络生命周期的参数。表1是在Matlab仿真平台上,采用不同的网络生命周期作为参数,得出的在100m×100m范围的网络中,当节点死亡1%,50%,95%时所经过的轮数。图3是经过一次仿真测试后,LEACH,LEACH-EA,LEACH-EI剩余节点数对比图,每个节点的初始能量为0.5J.剩余节点数表明了随着时间的推移,仍然存活的节点的总数,该参数是体现路由协议是否属于能源有效性协议的一个重要指标。由图3可知,当轮数r≤2500的时候,LEACH-EI仍然存活的节点数大于LEACH和LEACH-EA。当轮数r≤2500≤3500的时候,LEACH-EA和LEACH-EI存活节点数基本相同,r≥3500时LEACH-EI存活节点数比LEACH-EA少。图4是经过仿真测试后,根据仿真过程绘制的三种算法的网络生命周期柱状图。分析图4可知,如果以节点死亡1%和50%的时间作为衡量网络生命周期的参数,LEACH和LEACH-EA网络生命周期大致相同,LEACH-EI稍有提高;如果以节点死亡95%的时间作为网络生命周期的参数,则LEACH-EA和LEACH-EI分别比LEACH提高了大约227%和139%,LEACH-EA比LEACH-EI提高了大约33.2%.3不同网络模型网络的matlab仿真笔者在LEACH协议的基础上,