基于分层的多跳分簇路由算法

基于分层的多跳分簇路由算法

无线传感器网络（wsd）通常由各种随机分布的传感器节点组成，以承担电池电源的任务。在无人监控下。因为节点一般不太可能更换电池,所以能量受限是传感器网络最显著的特点之一,因此设计高效的路由算法是WSN设计的一个重点。随着研究的深入,各种路由算法如LEACH、SEP、HEED等被提出来用以有效利用节点能量。LEACH是最早提出的一种基于簇结构的层次型WSN路由算法。该算法的基本思想是通过随机循环地选择簇首,将整个网络的能量负载平均分配到每个传感器节点中,从而达到降低网络能源消耗、提高网络整体生存时间的目的。SEP是对LEACH的改进,对不同剩余能量的节点采用不同的选举概率。HEED采用能量和通信代价(AMRP)主次两个参数分布式选择簇首,从而使簇首的分布更加均匀,进一步减少能耗。但这些算法都要求传感器节点与Sink节点可以直接通信,因此网络的扩展性不强,不适用于大型网络。为了弥补单跳通信的缺陷,发展出了多跳路由算法如PEGASIS、UCS、EEUC等。PEGASIS算法中距离簇首越近的节点能耗越大,会使整个网络的能耗不均衡。UCS算法将节点按距离Sink的远近分成大小不同的簇,较好地克服了“热点”问题,但该算法假定里层的簇首在圆形区域中的分布是事先设计好的,这个假设不适合于随机部署的WSN网络。EEUC算法是和UCS类似的异构网络算法,该算法的基本思想是使每个节点先根据一个预先确定的门限,随机确定自己是否成为伪簇首,成为伪簇首的节点根据接收到的Sink信号能量,计算自己与Sink的距离,形成不同半径的竞争区域,竞争区域内的伪簇首通过竞争,能量最大的成为簇首;簇首再根据周围簇首的剩余能量与转发代价,从转发代价最小的2个簇首中选择剩余能量最大的簇首作为自己的下一跳节点。同样,该算法中需要得出节点的位置信息,这是一个难点,而且若有节点接收不到Sink节点的信号,则该节点将无法加入网络,这使整个网络的连通性存在一定的问题。针对LEACH等路由算法扩展性不强,而UCS等路由算法应对网络随机性不足等缺点,本文融合了传感网络的分簇思想和链式多跳机制,根据通信代价对网络进行分层,提出了分层多跳分簇路由算法LBMC(LayerBasedMultihopClusteringroutingalgorithm,LBMC)。与SEP、LEACH等算法相比,获得了更好的能量效率和更高的网络生存时间。1区域多排设器假设有N个节点随机分布于一片区域,节点能量异构,但分布基本均匀,节点位置未知,Sink节点位于区域边缘或者区域中间。首先将监控区域根据通信代价分成多个层,层的宽度可以通过参数控制;然后采用类似于LEACH的簇首选举算法,根据事先计算出的最优阈值选举簇首,每一层的最优阈值可以不同,此后根据剩余能量最大原则指定下一轮簇首;簇首间形成簇首链进行通信;簇内节点与簇首间一般通过单跳通信,但对于一些边缘节点可以通过虚拟簇首进行多跳通信;最后形成一个能耗均匀、簇大小异构的多跳无线传感器网络,克服网络中的“热点”问题。1.1最大的所在层参数分层网络模型如图1所示,Sink节点位于监控区域边缘,网络中节点分为多个层,最靠近Sink节点为第1层,向外分别为第2、3…层,各层中节点数量在分层之前并不知道。网络建立路由的第一步便是执行分层算法。分层算法的实质是根据通信代价的高低对区域中的传感器进行分类,到Sink节点的通信代价相同或相近的节点归为一类。分层算法成功结束时,会使每个节点得到唯一的所在层参数,这个参数会逐层递增,表示了通信代价的逐层递增,这个特性在数据路由时提供了一个强有力的路由方向选择依据。层参数越小,通信代价越小,越靠近Sink节点。数据在路由时,便可以据此选出能量代价最小的路由路径。Sink节点向网络发送一个分层指令,并包含一个层宽调节参数Rp、发射功率PT和当前所在层L。其中Rp是功率比阈值,节点用Rp与进行比较来确定自己所处的层,其中PR是接收功率(即RS-SI,ReceivedSignalStrengthIndication)。对于Sink节点来说,L=0。在网络分层之前,每一个节点都将自己所在层标识为L=0。分层指令以类似泛洪传播的方式在网络传播。假设节点i已经确定了自己所在的层(如Sink节点),节点j接收到了来自节点i的分层指令(Rp,PTi,Li),则进行判断,若则忽略这个消息,若则进行如下操作:如果Lj=0或者Lj>Li+1,则设置Lj=Li+1,记录Rp,修正分层指令中的参数,即用PTj和Lj替换PTi和Li,而后转发分层指令。这样处理可以减少不必要的指令转发,有效防止泛洪风暴带来的能量损耗。经过一段时间以后,网络中所有的节点都能确定自己所在的层。分层算法到此结束。1.2无线传感器网络的融合每一层的簇首节点个数及其分布将显著地影响网络的能耗、健壮性、连通性等性能指标,因此我们需要计算出每一层的最优簇首个数。我们将以能耗为考虑重点,推导出每一层最优簇首个数的计算公式。根据文献的无线信道能量消耗自由空间模型,发送一个l比特的数据包到距离发送端为d的节点需要消耗的能量为:而接收这个数据包需要消耗的能量为:根据文献中实验所测数据,通常情况下,发射能量Eelec=50nJ/bit,自由空间传播系数εfs=10pJ/bit/m2,εmp=0.0013pJ/bit/m2,数据融合能量消耗系数EDA=5nJ/bit/signa,在本文的网络模型中,无线传感器网络共分为s层,各层的宽度为δ,每层节点数为Nk,k=1,2…s,每层簇首节点数为mk,k=1,2…s,每个数据包长度为l比特。我们假设簇内节点的数据可以百分百的融合,而簇间的数据则不作融合处理。首先来考虑仅有一层的情况,且假设所有节点距离Sink节点的距离都不超过d0。根据文献、文献和文献的推导,我们可以得到此时的最优簇首节点数为:由式(3)可见,对于仅有一层的情况,最优簇首节点数只跟这一层的节点总数相关。根据我们的假设,我们的网络是分层的,通过对层宽的调节,可以保证,相邻两层的距离小于d0,外层的簇首节点可以选择相邻内层的簇首节点作为下一跳。如果把内层簇首节点看作是Sink节点,则最外层的最优簇首节点数可以按照式(3)来进行计算。内层簇首除了要负担本层簇内节点的数据通信外,还要担任外层簇首的中继节点,这时外层簇首节点可以看成是内层簇首节点的普通节点,但是在簇间数据不作融合处理的情况下,外层簇首节点应该相当于两个普通节点。因为在d不是很大的情况下:设最外层最优簇首节点个数占总本层节点总数的比例为kopt,如果网络的最大层宽为s,那么对于第s-1层来说,其最优簇首节点数满足下式要求:如果我们忽略掉kopt的三次及以上的项,则可以推导出第i层的近似最优簇首节点数:式中这个结论非常符合我们的直觉,因为多跳通信意味着越靠近Sink节点的簇首负担越重,因而需要更多的簇首节点。一旦知道了每一层的最优簇首节点所占的比例,就可以以此作为选举门限,分布式的选举簇首。1.3节点间节点连接的特点LBMC的成簇算法包括簇首选举、簇内节点连接、簇首链的形成、簇首轮换等几个步骤。具体规则如下:(1)簇首选举我们采用类似LEACH算法的方式进行,但又有些不同。各层中节点以各自的随机概率单独进行簇首选举,选举的门限值为根据上一节的分析,每层的最优簇首节点所占的比例为因此我们选择选举门限:这里要求知道网络的最大层数s,这个参数,可以根据事先的信息估算出来,在分层指令中发布到网络中。每一层节点分别计算自己所在层的选举门限,并随机选举。节点成为簇首之后,就以固定的功率广播自己,等待簇内节点的加入。(2)簇内节点根据通信能耗最小原则选择对应的簇首簇内节点根据接收的簇首节点的信号强弱来选择信号最强的一个,因为簇首是以固定的功率广播,通常情况下,接收信号越强,距离就越短,通信能耗就越低。在这里,我们并没有要求某一层的节点只能连接到本层簇首。如图2所示,节点n距离簇首chA更近,则选择加入chA,而不是距离更远的chB,尽管chA不在同一层,而chB则位于同一层。这样可以最大限度的节约节点通信能耗。(3)簇首链的形成同样的,外层簇首根据能耗最优原则选择下一跳。簇首选择或者轮换完成后,就会从最内层,即接近Sink节点的簇首开始计算自己到Sink的距离。当然,这个根据接收信号强度计算出来的距离只是大致距离,但是用来选择下一跳已经足够了。根据文献的无线信道能量衰减模型结合文献的实际测量结果,在假设信号传播距离1m后能量与初始能量相同并忽略其他一些因素后,接收功率PR、发射功率pT和节点间距离d的关系可用下式近似:式中η为路径衰减系数,取值在2~5之间。由式(9)可得:要使所有的簇首都能选择最合理的一个路径,距离估算需要从最内层开始,最内层簇首节点到Sink的距离可以根据式(10)直接计算出来。从第二层开始,如果不是直接与Sink节点通信,则距离可以如下计算:式中di,j为节点i到节点j之间的距离,可以根据式(10)计算出来,dj表示节点j到Sink节点的距离,表示转发代价。节点i比较所有的内层节点包括Sink的通信距离(这个距离即代表了通信能耗代价),选择最小的节点,作为它的下一跳。这样由内而外,由近及远,很快就能建立起最优的簇首链。之后就可以进行数据传输。(4)簇首的轮换规则LEACH、SEP等协议,需要每一轮都重新选举簇首,会消耗比较多的能量。针对这一点,LBMC算法并不是每一轮都重新选举簇首,而是在一定的轮数之内,由本轮簇首来指定下一轮的簇首。本轮簇首根据剩余能量最大原则来选择下一轮簇首。这样剩余能量大的节点可以更多的担任簇首节点,从而从整体上平衡能量消耗。但有时会发生剩余能量多的节点集中到某一块区域的情况,这样就会造成簇首分布不均匀的问题,因此每隔一定的轮数,需要重新进行簇首选举。(5)边缘节点的连接对于某些边缘节点,所有簇首节点都不在它的通信范围之内,如果不采取措施,必然会使网络的连通性降低。这里引入虚拟簇首节点的概念,虚拟簇首节点并不是真正的簇首节点,它只作为某些边缘节点与簇首节点之间通信的中间节点。节点在找不到簇首节点的情况下,会试着寻找已存在的虚拟簇首节点,如果都找不到,则选择某一通信范围内的簇内节点相连,该簇内节点同时成为虚拟簇首。边缘节点选择某簇内节点与其相连的概率为即选择通信能耗最低的节点为虚拟簇首。1.4网络分层控制LBMC算法的执行步骤如下:(1)节点初始化,Sink节点向网络发送网络配置参数:层宽调节参数Rp、最外层簇首选举门限Ts、最大层数s、循环轮数C,并发起网络分层指令。(2)节点分层。(3)各层根据本层的簇首选举门限,随机选举簇首。(4)网络中非簇首节点选择相应的簇首节点并与其连接,当有边缘节点存在时,需选择虚拟簇首节点。簇首节点形成簇首链。(5)当一个簇的生命周期完成时,且小于预设的循环轮数C,则由簇首选择某个簇内节点成为簇首,同时解散原簇并重新成簇。(6)当到达循环轮数C时,重复进行步骤(3)到(6)的过程。2仿真结果与分析仿真实验对LEACH、SEP、HEED和本文提出的LBMC算法进行了分析和比较。仿真环境为Matlab,仿真重点为不同算法的网络存活时间和节点的能耗。前三种算法专注于簇首节点的选举问题,因此不适用于大范围的网络,为此,我们将LBMC的分层算法和簇间路由算法分别加入进去,使之都成为多跳路由算法,扩展其网络范围。其中LEACH、SEP采用文献中使用的参数,HEED采用文献中使用的参数。本文对总节点数为100,事件区域范围为100m×100m到400m×400m的场景进行了仿真。节点参数如下表1所示。图3是100m×100m时,每一轮簇首节点的平均剩余能量,从中可以看出,LBMC的簇首具有更高的剩余能量,且越大后边差距越大,说明LBMC具有比其他三个协议更好的能量效率。图4和图5是100m×100m和400m×400m时,网络生存时间的比较,横轴的代表网络生存时间的周期数,纵轴则是存活的节点数。从中可以看出,SEP相比LEACH的提高很少,HEED则有很大的提高,而LBMC则提高更多。因为LBMC和HEED使网络的能耗更加均匀,网络的中节点的死亡相当集中,从第一个节点死亡到最后一个节点死亡的时间非常接近。图4和图5是LBMC、SEP、LEACH、HEED4个协议的稳定生存周期(即第一个节点死亡之前的运行周期)的比较。从图中可以看出,当场地大小从100m×100m到400m×400m变化时,所有的协议的稳定周期都下降了,但是LBMC的稳定周期明显比其他三个协议要长,且场地越大差距越大,同样说明了LBMC有着更好的能量效率。图6是随着场地范围的扩大,4种协议的网络稳定生存周期的变化,从图中可以看出,LBMC比其他三种协议有更长的稳定生存周期,即网络完整工作的时间比其他三种协议要长。图7是基站接收到的的数据包的总量,结合图4和图5可以看出,虽然SEP和LEACH的最后的生存周期比HEED和LB-MC的要长,但其传输的总的数据包量并没有比HEED和LBMC的多,这是因为由于SEP和LEACH本身协议存在一些缺陷,即当节点数很少时,会出现没有簇首的情况,这时候数