无线传感器网络中基于负载均衡的分布式定向分簇算法

无线传感器网络中基于负载均衡的分布式定向分簇算法

簇是无线传感器网络（无线传感器网络）算法研究的主要方向之一。与平面路由算法相比，分簇算法具有更好的扩展性和适应性，适合于无线传感器网络的应用特点。基于簇中节点的基本思想，将网络划分为几个逻辑区域，这些区域称为“簇”。每个簇通常由一个簇头节点（clert）和几个集群中的成员节点（clert）组成。集群中所有成员节点仅与簇中节点沟通。集群节点负责收集来自簇中节点的数据，并通过数据整合和数据压缩来传输数据。本文提出一种基于负载均衡的分布式定向分簇算法(distributedanddirectedclusteringalgorithm,DDC).该算法有效解决了在分簇条件下网络中节点负载不均衡的问题,并最大程度地延长了网络的生命周期.DDC算法的核心思想是利用文献的分簇思想,基于节点的当前能量水平对网络进行分割,以获得适当的网络节点分区,并在分区中基于节点负载能力选取簇头,从而达到网络中各节点能量均衡消耗的目的.为此,DDC算法引入了两个重要参量:节点能量预评估因子和节点负载能力预评估因子.这两个参量用来衡量节点的当前能量水平及节点在某一轮中的负载能力水平,并基于分区的信息预估计实现,这保证了DDC算法的分布式特性.由于在确定节点负载能力时考虑了其发送数据包到Sink节点的能量消耗,这使得分区所选取的簇头呈现向Sink节点靠拢的特征,特别是在网络中节点能量一致的情况更加明显.因此,我们称DDC算法是一种向Sink节点靠拢的定向分簇算法.1基于heed的分布式能量成簇算法在无线传感器网络中,LEACH是最早提出的分簇路由协议之一.它的基本思想是通过等概率的随机循环选择簇头,将整个网络负载平均分配到每个传感器节点中,从而达到降低网络能量消耗、延长网络生命周期的目的.它的成簇思想对后来发展出的很多分簇路由协议影响深远.文献提出的TEEN采用与LEACH类似的成簇算法,只是在数据传输阶段使用不同的策略,即将数据传输分为主动型和响应型两类,并通过在协议中设置硬、软两个阈值,以减少发送数据的次数,从而延长网络生命.文献提出的HEED是一种完全分布式成簇算法,它通过节点间交互动态产生簇头,并在簇头选取过程中考虑了节点的剩余能量,但算法的控制开销比较大.文献提出的DCHS在成簇过程中也考虑了能量因素,利用节点的当前能量和节点的初始能量的比例来影响阈值,从而使能量比例消耗低的节点优先当选簇头,但是,仍然没有解决网络负载的均衡性.文献借鉴了LEACH的分簇思想,提出了PEGASIS算法,从严格意义上来讲,它并不是真正的分簇算法,它的簇就是一条基于地理位置的链.文献是一种较典型的集中式分簇算法,它利用CBR(case-basedreasoning)技术在基站完成分簇,产生适当的簇数,并在每轮结束时根据簇的相似度来决定是否需要重组,从而节省每轮重新成簇的开销.以上算法虽然都能较好地符合无线传感器网络路由协议的设计要求和特点,但这些算法对网络初始能量的异构性和节点负载的均衡性考虑不够,在实际应用中存在一定的局限性.文献提出的SEP协议虽然考虑了网络节点初始能量可能不一致问题,但该算法仅考虑网络中存在两种初始能量的问题,因而仍然无法解决实际网络中节点初始能量分布的随机性.文献基于SEP协议的设计思想针对一般性的多级异构网络提出了一种分布式能量有效成簇算法,但算法对网络节点的平均能量的估计比较粗糙,而且处理多级异构的算法相对复杂.2基于负载平衡的分布式向量分布模式算法2.1节点能耗模型假定在M×M的区域随机分布了N个传感器节点,如图1所示.并给出如下假设条件:1)网络中节点一旦部署,节点的地理位置便可确定(可通过节点定位技术或GPS实现);2)网络中各节点的发送功率级别可调;3)网络中各节点的初始能量相同或不同,节点可获取自身的当前能量.论文采用文献的能量模型,节点能耗包括3部分:发送数据能耗ETx、接收数据能耗ERx、数据融合能耗EDA.其能量计算公式如式(1)所示.{EΤx(l,d)={lEelec+lξfsd2,d<dthresh,lEelec+lξmpd4,d>dthresh,ERx(l,d)=lEelec‚EDA(l)=lEDA‚(1)其中,l是节点发送或接收数据的比特数;Eelec是发送电路和接收电路消耗的能量,在这个模型里面两者相等;EDA是簇头进行数据融合时消耗的能量;ξmp和ξfs是信号放大器的放大倍数;dthresh为距离阈值.2.2第r轮负载能力评估在分簇算法中,网络中各节点的负载能力,是有效控制网络负载均衡的重要依据.在DDC算法中,为了有效评价节点在每一轮中的负载能力,我们提出了节点的负载能力预评估因子的概念.定义1.节点负载能力预评估因子:设在第r轮,具有N个节点的无线传感器网络被分割成k个区域,对任意分区t(1≤t≤k)的集合T(t,r)中有C(t,r)个节点.则对网络中任意节点i(i∈T(t,r))在第r轮的负载评估因子为lbf(i,r)=(1-Epc(i,r)E(i,r)),(2)其中Epc(i,r)是假设节点i在第r轮的分区t中担任簇首时预估能耗.其能耗主要包括接收分区中各成员节点数据所消耗的能量、根据相关性进行数据融合所消耗的能量以及将数据传送到Sink节点所消耗的能量.这个预估能耗可根据式(1)计算可得.式(2)表明,节点的当前能量越大,拟担任簇首的预估能耗越少,则其负载能力预评估因子值就越大,相应的该节点负载能力就越强.2.3节点初始量水平在DDC算法中,为了实现对网络中各节点能量水平的评价,我们提出了一种局部的基于分区的节点能量预评估因子来衡量网络中各节点的能量水平.下面给出其定义:定义2.节点能量预评估因子.设在第r-1轮,任意节点i的初始能量为E0(i,r-1),具有N个节点的无线传感器网络被分割成k个区域,对任意分区t(1≤t≤k)的集合T(t,r-1)中有C(t,r-1)个节点.则对网络中任意节点i(i∈T(t,r-1))在第r轮的能量预评估因子为:ef(i,r)={E0(i,r)1ΝΝ∑i=1E0(i,r),r=1；E0(i,r-1)-Ep(i,r-1)1C(t,r-1)∑j∈Τ(t,r-1)(E0(i,r-1)-Ep(i,r-1)),r>1；(3)其中,Ep(i,r-1)为节点i在第r轮所消耗的预估能量,根据式(1)可得.式(3)表明,当r=1时(首轮),节点i的初始能量因子ef(i,r)是节点i的初始能量与网络平均能量1ΝΝ∑i=1E0(i,r)的比值,在网络初始能量不同的情况下,ef(i,r)的值越大,则表示节点的初始量水平越高;而当网络初始能量相同时,ef(i,r)的值为1,表明网络中各节点的能量水平相同.当r>1时,节点i的能量预评估因子ef(i,r)的计算不再依赖于网络平均能量,而是通过对节点i在前一轮(即第r-1轮)所属分区的平均能量1C(t,r-1)∑j∈Τ(t,r-1)(E0(i,r-1)-Ep(i,r-1))来计算.显然,ef(i,r)值越大,表明节点在本分区的能量水平越高.这种仅仅利用前一轮的分区信息来获取下一轮节点的能量预评估因子,可以有效保证DDC算法的分布式特性.2.4分散算法2.4.1ddosc算法中的最优簇头理论在DDC算法中,我们利用文献的分簇思想对网络中的节点进行分割,即根据式(4)给定的阈值进行网络分割.Τ(n)={Ρ1-Ρ[rmod(1/Ρ)],n∈G,0,其他,(4)其中P是所有节点中簇头所占的百分比(即节点当选簇头的概率),r是当前的轮数,G是最近1/P轮中还未当选过簇头的节点的集合.未成为簇头的节点根据接收到广播信号的强弱来决定加入哪个簇头节点,实现对网络的预分簇,从而达到对网络节点进行区域分割的目的.但在分割的基础上应充分考虑网络的能量均衡性,即在分割的各区域内尽可能包含高能量节点,从而使得各区域的能量消耗均衡.根据文献中最优簇头数理论,我们设在M×M的平面内均匀分布N个传感器节点,则网络的最优簇头数为kopt=√Ν√2π√ξfsξmpΜd2toBS.(5)因此,在等概率的情况下,网络中各节点成为簇头的最优概率为:Ρopt=koptΝ.(6)考虑到网络能量消耗的均衡性,应尽可能增加当前能量水平高的节点出任簇头的概率.我们将能量水平评估因子引入网络的簇头轮转过程,以调节节点的轮转周期,让当前能量高的节点获得更多机会出任簇头:Ρ(i,r)=Ρoptef(i,r);(7)Τr(i)=1Ρoptef(i,r).(8)式(7)和式(8)分别是节点i在第r轮出任簇首的概率及其轮转周期.显然,对节点i而言,能量越高,其出任簇头的概率越大,簇头轮转周期越短.同时,我们分析P(i,r)的数学期望值并由式(8)和式(3)可得:E(#CΗ)=Ν∑i=1Ρ(i,r)=Ν∑i=1Ρoptef(i,r)=ΡoptΝ∑i=1ef(i,r)=ΡoptΝ=kopt.(9)式(9)表明在引入能量评估因子ef(i,r)后,网络优化簇头数kopt仍然可以得到保证.因此,DDC算法在每一轮中基于式(4)对网络进行分割时,根据节点能量预评估因子对节点担任簇头的轮转周期进行调整.设在第r轮中节点i的能量预评估因子为ef(i,r),则节点i提前或滞后进入集合G的轮数为rounds(i,r)=1p-1ef(i,r)p=(1-1ef(i,r))1p.(10)式(10)表明,当节点i的能量预评估因子值大于1时,rounds(i,r)的值大于0,即该节点可以提前rounds(i,r)进入集合G;当节点i的能量预评估因子值等于1时,节点i的当前轮转状态不变;当节点i的能量预评估因子值小于1时,rounds(i,r)的值小于0,即该节点滞后|rounds(i,r)|进入集合G.因此,该调整方法可以有效保证每轮分割过程中各分区能量的均衡性.2.4.2分区设置时节点能量均衡通过预分簇对网络节点进行区域分割后,在各分区中选举合适的簇头节点是有效实现网络负载均衡的重要手段.在分簇算法中,簇头承担接收分区内各成员节点发送的数据包,并根据相关性进行数据融合处理,然后再发送到Sink节点.相对于成员节点,簇头节点每轮消耗的能量要大得多.因此,在分区中选择一个具有良好负载能力的节点担任簇头,有利于网络负载的均衡.设在第r轮中,任意分区t(1≤t≤k)的节点集合T(t,r)中有C(t,r)个节点.则分区中出任簇头的节点j必须满足以下条件:j∈G且lbf(j,r)=maxi∈Τ(t,r)(lbf(i,r)).(11)式(11)条件实际上是保证在分区中拥有最大负载能力的节点来出任簇头,从而使分区中节点能量能均衡消耗.2.4.3打造控制消息DDC算法是一种基于负载均衡的分布式成簇算法,它通过利用节点的能量评估因子和节点的负载能力预评估因子来实现网络中各节点的能量均衡消耗,进一步维持网络的稳定性.在DDC算法中我们定义了节点的4种状态:1)未定义状态(undefined,UN).节点每一轮开始时的初始状态;2)区头节点(areahead,AH).网络分割时各分区产生的预定义簇头节点;3)簇头节点(clusterhead,CH).4)从节点(slavenode,SN).隶属于各簇头的节点.同时,还定义了3种控制消息:1)区头声明消息(AH_MSG)2)从节点加入消息(ADD_MSG)3)从簇头选定消息(CH_MSG)DDC算法的每一轮包括3个阶段:1)节点分割阶段.在每一轮开始时,每个节点选取一个介于0和1之间的随机数,并根据式(4)给定的阈值,决定自己是否成为区头(AH),若是,则向所有节点广播声明区头消息(AH_MSG);否则,从已收到的各区头声明消息中选取距自己最近的区头,并向其发送加入消息(ADD_MSG).经过一段时间后,每个区头都拥有一定数量的成员节点(SN).在这个阶段,利用区头实现了对网络节点的分割.2)节点成簇阶段.在网络节点分割完毕后,每个区头节点从收到的ADD_MSG消息中提取各从节点的当前能量和坐标,根据式(2)计算各从节点的负载能力评估因子,并根据式(11)选取本分区的簇头节点(CH).然后根据式(3)重新计算分区中各节点的能量预评估因子,并将其包含在CH_MSG消息中发送给各从节点.若选取的簇头节点就是区头节点,则区头将自己状态设为簇头节点(CH);否则,将自己的状态设置为从节点,并将所依附的簇头节点设为已选取的簇头节点.各从节点收到来自本分区的CH_MSG消息后,若CH_MSG消息中指定的簇头ID与自己相符,则从节点将自己状态更新为簇头节点(CH);否则,将自己所依附的簇头节点设为CH_MSG消息中指定的簇头节点.3)数据传输阶段.节点成簇阶段完成后,各从节点开始向本节点所依附的簇头节点发送数据包.节点在本轮数据传输完成后,根据式(10)对自身的轮转状态进行调整.下面我们给出DDC算法中任意节点i在第r轮的一般成簇算法.算法1.节点i在第r轮成簇算法.3基于算法的仿真实验在本节,主要利用仿真实验对算法的性能进行分析和评价.仿真实验采用文献所使用的通信能量模型,并设定主要参数如表1所示:场景A.节点的初始能量相同,即设定每个节点的初始能量为2J,网络初始总能量为200J.场景B.节点的初始能量在[1J,3J]区域内随机分布,但网络的初始总能量为200J.基于算法比较的公平性,分别在这两种仿真场景下对LEACH算法、LEACH-LBF算法、DCHS算法、DCHS-LBF算法及DDC算法进行了仿真.其中,LEACH-LBF算法和DCHS-LBF算法是基于lbf因子对LEACH和DCHS的改进算法.3.1算法性能对比网络生命周期是衡量算法能量有效性的重要依据.在分簇算法中,网络生命周期主要体现在成簇稳定期(即从网络开始运行到第1个节点死亡时持续的轮数),成簇稳定期越长,则网络能量有效性越好.根据仿真场景A和B(Sink节点位于(50m,250m))得到算法的网络生命周期图(如图2～4所示):由图2～4可知,在场景A和B下,LEACH-LBF性能较原算法均没有明显改善,但DCHS-LBF算法较原算法改善明显,这是由于DCHS算法考虑了节点剩余能量的结果.由于场景B并不符合LEACH的理想条件(节点初始能量相同),因此,在场景B下,LEACH的第1节点死亡时持续的轮数比在场景A下降低了30%;同样,DCHS算法也存在类似情况.相对LEACH算法和DCHS算法,DDC算法的生命周期得到了显著提高,而且在场景B下表现更为明显.为了更好对算法性能进行比较,我们通过改变Sink节点的位置(X=50m,Y=150～550m)来分析算法的生命周期的变化情况(如图5～7所示).从图5～7可知,在场景A和B下,LEACH-LBF和DCHS-LBF算法在不同位置中的生命周期均优于原算法;LEACH和DCHS在不同位置下的生命周期场景A中要明显优于场景B,这表明这两个算法不适用于初始能量不同的场合;而DDC算法在两种场景中优势明显.3.2能量消耗对比显然,网络负载越均衡,节点在每轮中消耗的能量就越均匀,其生命周期就越长.根据场景A和B(Sink节点位于(50m,250m)