分布式能量有效成簇路由算法研究

分布式能量有效成簇路由算法研究

1设置了设置一个专门的wsn分簇作为一种新的获取和处理形式，无线传感器网络（无线传感器网络，无线传感器网络）已成为国内外的研究热点。WSN通过大量部署在监测区域内的传感器节点,采集网络覆盖区域内感知对象的信息,通过多跳的无线通信方式,将收集、处理后的信息提供给终端用户。WSN不需要固定的网络支持,具有快速展开、抗毁性强等特点,可广泛应用于军事侦察、环境监测、医疗监护、农业养殖和其他商业领域,以及空间探索和灾难抢险等特殊领域。在WSN体系结构中,网络层的路由技术对WSN的性能好坏有着重要影响。随着国内外WSN的研究发展,许多路由协议被提了出来。由于传感器节点本身资源的限制,针对adhoc网络的分簇算法不能被直接利用,特别是WSN节点能量更为有限,因此必须研究新的分簇算法。LEACH(low-energyadaptiveclusteringhierarchy)是WSN中最早提出的分簇路由协议。它的成簇思想贯穿于其后发展出的很多分簇路由协议中,如TEEN(thresholdsensitiveenergyefficientsensornetworkprotocol)、HEED(hybridenergy-efficientdistributedclustering)等。另外,还有一些独立开发的分簇路由协议,如ACE(algorithmforclusterestablishment)、LSCP(lightweightsensingandcommunicationprotocols)等。2相关研究传感器网络成簇算法发展迅速,按照成员节点到基站的跳数,簇的结构一般分为单跳和多跳网络。2.1基于剩余能量的分布式联合打造LEACH是最早提出的单跳分簇算法,其基本思想是:通过等概率地随机循环选择簇头,将整个网络的能量负载平均分配到每个传感器节点,从而达到降低网络能量耗费、延长网络生命周期的目的。近几年,提出了许多LEACH的改进算法,其中包括EECS、LEACH-B等,在不同方面改进了LEACH算法的性能。在EECS中,节点在选择簇头时不是简单地选择距离自身最近的簇头,而是考虑了候选簇头到基站距离的远近,构造出相应的簇,均衡簇头的负载。但该协议只能平衡簇头地区的能量分布,缺乏对全网消耗能量的平衡。文献提出一种根据节点剩余能量选举簇头的算法,缺点在于每个节点需要知道当前网络的总能量,而难以分布式实现。SEP则是针对二级异构网络设计的,即网络中只有2种不同初始能量的节点。DEEC算法针对一般性的多级异构网络设计,不适用于同构传感器网络。DCHS引入了能量阈值,延长了网络的生存周期,但该算法未考虑平衡全网能量。HEED也是一种完全分布式的成簇算法,它随机选择簇头节点,选举概率与该节点的剩余能量直接相关。HEED算法首先根据节点的剩余能量来概率性地选取一些候选簇头,然后以簇内部通信代价的高低来竞争产生最终簇头。簇生成算法需要在簇半径内进行多次消息迭代,由此带来的通信开销比较显著。上述的这些协议均通过周期性地重新分簇,让节点轮流担任簇头,达到节点均衡地消耗能量的目的。2.2apteen协议多跳网络的简介PEGASIS则将节点组织成链的形式,链的形成由每一个节点或者基站计算得到,因此需要知道网络拓扑的全局知识。文献研究了多跳簇结构网络,并使用一种随机成簇方案来组织传感器节点。TEEN协议适用于实时性要求较高的应用场合,用户可以及时获取感兴趣的信息,它设置了硬、软2个阈值,以减少发送数据的次数。通过调节2个阈值的大小,可以在精度要求和系统能耗之间取得合理的平衡。但TEEN存在3个缺陷:一是如果阈值不能达到,节点不会传送任何数据;二是数据一旦符合阈值要求,节点立即传送,容易造成信号干扰,如果采用TDMA,则会造成数据延迟;三是该协议的阈值选择是非常困难的。APTEEN协议的功耗相对降低,增加了网络的生命周期。对于实时性要求不高的查询,时延可以大一些,这可以使生命周期增加近一倍,但APTEEN协议的实现难度比较大,给实际应用带来了困难。ECMR(energy-consciousmessagerouting)是多跳的路由传输协议。ECMR假设簇头预先部署,能量不受限,能与成员节点直接通信,而成员节点需多跳路由才能到簇头。ECMR由簇头采用Dijkstra算法求解。其中,节点i和j之间链路的权值定义不仅计算了它们之间的通信耗费,也考虑了节点能量、数据延迟和链路负载等因素。ECMR在运行过程中具有良好的节能性能、较高的吞吐量和较低的通信延迟。但是,该协议扩展性较差,需要部署新的簇头来扩展网络,而且对簇头依赖性大,不支持节点移动。在文献中,李成法等人提出了基于竞争的多跳非均匀分簇算法,仿真结果显示了较好的效果,但该算法中的参数选取主要凭经验给出,理论分析不够,需要进行深入研究。另外,基于竞争产生簇头仍然存在能量浪费问题,因为候选簇头数量较多,需要竞争的次数较多,因此需要继续深入研究。M-LEACH针对多跳网络,算法比较复杂。文献引入了能量和距离阈值以均衡全网能量消耗,但算法未考虑全网的能量分布情况。对于单跳成簇算法,操作简单,时延小,适合于实时性较强的网络,缺点是向基站传输数据时需要消耗更多的能量。多跳成簇算法一般较复杂,实现难度较大,时延较大。本文主要研究单跳成簇算法,试图寻找一种较为合理的思路延长网络的生命周期。然而,从均衡节点的能量消耗以延长网络的存活时间这个目标看,先前的研究主要集中于均衡簇成员节点之间的能量消耗,没有考虑到簇头间的能量消耗均衡问题。本文提出的DEEUC算法是为同构单跳网络而设计的。它借鉴了LEACH的簇头轮转思想,同时让簇头节点的选举与节点剩余能量直接相关,避免了同构成簇算法所遇到的问题。DEEUC还保留了分布式算法的优点,不需要中心机构在网络操作过程中提供全局信息。3基于平均能量的引领性选举算法本文引入平均能量阈值的核心思想是根据节点的剩余能量来合理选择簇头,剩余能量高的优先选择为簇头,最终能有效地平衡全网能量,基于此,提出了基于全网平均能量的簇头选举算法,类似于LEACH-C,但克服了必须向基站传送剩余能量的问题,引入估计方法,避免了LEACH-C的能量消耗问题。簇头选好后,对于加入簇的节点来说,加入那个簇是平衡全网能量的关键因素,本文提出了基于距离和能量因子的能量消耗率函数,有效地延长了网络的生命周期。3.1有节点的数据融合模型研究的网络分布在一正方形区域内,由N个随机分布的传感器节点组成,其应用场景为周期性的数据收集。用in表示第i个节点,相应的节点集合为Node={n1,n2,…,nN},|Node|=N。假设如下。1)基站位于一个方形观测区域的外侧,传感器节点和基站BS在部署后均不再发生位置移动。2)所有节点都是同构的且能量有限,具备数据融合的功能。每个节点都有唯一的标识(ID)。3)所有节点都能够一跳到达基站(BS)。4)每个节点没有位置信息。5)根据接收者的距离远近,节点可以自由调整其发射功率以节约能量消耗。6)链路是对称的,若已知对方发射功率,节点根据接收信号强度RSSI计算出发送者到自己的距离。采用与文献相同的无线通信能量消耗模型,如图1所示。节点发射Lbit的数据到距离为d的位置,消耗的能量由发射电路损耗和功率放大损耗2部分组成,即其中,Eelec表示发射电路损耗的能量。若传输距离小于阈值do,功率放大损耗采用自由空间模型;当传输距离大于等于阈值do时,采用多路径衰减模型。εfs、εmp分别为2种模型中功率放大所需的能量。节点接收Lbit的数据消耗的能量为数据融合也消耗一定的能量,用EDF表示融合单位比特数据消耗的能量。假设邻近节点采集的数据具有较高的冗余度,簇头可以将其成员的数据融合成一个长度固定的数据包,然后发送给基站(BS)。3.2成簇算法deeuc在网络建立阶段,基站(BS)需要用一个给定的发送功率向网络内广播一个信号。每个传感器节点在接收到此信号后,根据接收信号的强度计算它到基站的近似距离。获得这个距离不仅有助于传感器节点向基站传输数据时选择合适的发送功率以节约能量消耗,而且它还是算法构造簇的必要信息之一。图2给出本文提出的基于平均能量的成簇路由算法的示意图,其中不规则的多边形围成的小图形表示簇头节点的覆盖范围,带箭头的直线表示簇头向基站单跳数据传输。从图2可以看出,成簇算法是使远离基站的节点尽量少成为簇头以减少能量消耗,在每一个簇头覆盖范围内尽量选取能量高的作为簇头。DEEUC每轮循环的基本过程是:在簇建立阶段,基站(BS)每个节点选取一个介于0和1之间的随机数,如果这个数小于某个阈值,该节点成为候选簇头。然后,通过竞争算法确定最终的簇头,簇头向周围节点广播自己成为簇头的消息。每个节点根据提出的能量消耗率函数来确定加入哪个簇,并回复该簇簇头。在数据传输阶段,簇内的所有节点按照TDMA(时分复用)时隙向簇头发送数据。簇头将数据融合之后把结果发给基站。在持续工作一段时间之后,网络重新进入启动阶段,进行下一轮的簇头选取并重新建立簇。3.3节点选取引领性算法候选簇头的产生是簇形成的基础,产生候选簇头时,每个节点产生一个0~1之间的随机数,如果节点n产生的随机数小于阈值T(n),则该节点向周围节点广播它是候选簇头的消息。由于LEACH算法没有考虑剩余能量和距离因素,因此改进了LEACH的T(n)计算公式,将平均能量因素考虑进来,使能量消耗比例较低的节点优先当选为候选簇头。在候选簇头选举算法中引入的关键参数如下:其中,E(i)residual表示第i个节点的剩余能量,E(r)表示第r轮网络平均剩余能量。Energy因子主要用来平衡全网剩余能量。定义从第一轮选择簇头开始到第一个节点死亡(能量消耗尽)的轮数,称为网络生命周期。通过以上分析发现,引入Energy阈值因子后,能够有效地降低全网的能量消耗,延长网络的生命周期。式(4)给出了新构造的阈值计算公式T(n)new。其中,p是簇头占所有节点的百分比,即节点当选簇头的概率;r是目前循环进行的轮数;G是最近1/p轮中还未当选过簇头的节点集合。从T(n)new可以看出,当选过候选簇头的节点在接下来的1/p轮循环中将不能成为簇头,剩余节点当选簇头的阈值T(n)new增大,节点产生小于T(n)new的随机数的概率随之增大,所以节点当选候选簇头的概率增大。p值决定了每轮产生的候选簇头数量,在应用中,最佳p值的确定十分困难,这与网络规模和节点密度有关。3.4传感器网络平均能量平均能量的计算需要全网节点的剩余能量信息,这是非常困难的,特别是对于节点密集型传感器网络。一方面要有相应的通信协议支持该数据的传送,另一方面即使有如此协议进行通信,对于基站(BS)来说,收集如此密集数据的开销也是十分惊人的,因此必须考虑其他途径获得平均能量信息。引入估计方法,对平均能量进行相应估计。假设每轮传感器网络消耗相同的能量,这种假设是合理的,因为每轮的簇头数量相近,通信开销相近。假设传感器节点均匀分布在M×M的正方形中,节点数设为N个,初始能量相同。每轮中消耗的能量包括2部分:簇头消耗的能量ECH和非簇头消耗的能量Enon-CH,设传感器网络每轮消耗的能量为Eround,则有对于传感器簇头而言,在一轮中消耗的能量ECH为对于传感器非簇头节点而言,在一轮中消耗的能量Enon-CH为其中,k为簇头的数量,dtoCH为节点到簇头的平均距离,dtoCH为簇头到基站的平均距离,如果这3个参数可以估计,那么每轮的能量Eround就可以估计。在文献中,作者已经估计了dtoCH和参数k分别为在文献中,作者估计了参数dtoCH为把式(6)、式(7)、式(8)、式(9)、式(10)代入式(5),从而可以粗略估计出全网一轮消耗的能量,进而估计出全网剩余的平均能量为其中,Etotal为全网初始能量,r为轮数。3.5簇头选择过程候选簇头产生后,引入竞争算法获得最终的簇头。首先使每个候选簇头以R(R为竞争半径)为半径广播竞争消息,如果si、sj为候选簇头,设以sj为核心,R为半径的特定面积内的候选簇头组成集合sj.ACH,在该面积内选择剩余能量最多的候选簇头作为最终簇头(如果最大能量有多个相同,选择第一个候选簇头作为最终簇头),然后将此面积内的其他候选簇头删除(即设置成簇成员节点),最后最终簇头以dn_CH(簇成员节点到达特定簇头的最大距离)为半径广播竞选成功消息,完成簇头选择过程。在竞争过程中,竞争半径的选取是非常重要的,下面作简单说明。引入非均匀簇机制,目标是让靠近基站(BS)的簇的成员较少,使其簇头能够预留部分能量供簇头与基站间通信使用。远离基站的簇头的成员较多,这样可以减少簇头与基站之间的通信次数,降低能量消耗,因为远距离通信消耗更多的能量。因此,靠近基站(BS)簇头的竞争半径应该较小。亦即,随着候选簇头到基站(BS)距离的减小,其竞争半径应该随之减小。记候选簇头竞争半径的最大取值为Rmax,最小取值为cR。算法需要控制竞争半径的取值范围,使得距离基站最远节点的竞争半径为(1+c)cR,其中c是用于控制取值范围的参数,取值范围为,c越大竞争半径越大,簇头消耗能量越大,根据选取的场景,c取值为1。候选簇头si确定其竞争半径si.R的计算公式如式(12)所示。其中,dmax和dmin分别代表网络中的节点到基站(BS)距离的最大值和最小值,d(si,BS)代表节点si到基站(BS)的距离。竞争半径与节点到基站的距离呈线性递增关系。3.6获得能量的需求簇头选好后,节点如何加入簇头是非常关键的,这直接关系到平衡当前簇头地区的能量消耗。例如在图2中节点i是加入簇头5还是6,必须由能量消耗率函数决定。直观上该节点加入簇头5,因为距离簇头5最近,但这不利于平衡全网能量消费。定义的能量消耗率函数f(i,j)为其中,1≤i≤CM,CM为加入第j个簇头的簇成员数量,1≤j≤CH,CH为簇头数量。节点i加入簇头CHj的条件就是使能量消耗率函数f(i,j)最小。其中iE表示节点i的当前能量,ECHj表示簇头j的当前能量。其中其中,d(CHj,BS)表示第j个簇头到基站(BS)的距离,。d(ni,CHj)为节点i到簇头j的距离,。提出的能量消耗率函数f既引入了距离因素,又引入了能量因素,直观上更能有效平衡当前簇头区的能量消耗。简单说明如下。选择簇成员的标准是使能量消耗率函数f(i,j)最小,则有为分析方便将常数合并,则有由于每轮中簇成员节点都要与簇头通信,簇头都要与基站(BS)通信,因此有等价变换为下式:上式中εfsd2(ni,CHj)是簇成员消耗能量的关键部分,εmpd4(CHj,BS)是簇头消耗能量的关键部分。直观上,只要能量消耗率函数最小,簇成员和簇头消耗能量均最低,继而全网消耗能量最低,因此能有效延长网络的生命周期。反之,如果簇成员和簇头消耗能量均最低,那么能量消耗率函数f(i,j)必定最小。3.7deeuc算法DEEUC是一个分布式动态算法,以节点的剩余能量和节点到簇头的距离为主要参数来选取簇头。在成簇算法中,簇头是非常重要的,因为簇头在每轮中完成最多的任务,消耗最多的能量。簇头选举算法包括2个阶段:候选簇头产生和最终簇头产生阶段。在选择候选簇头时,基站(BS)向每一个节点广播平均能量消息,在选择候选簇头过程中用平均能量参数来约束候选簇头的选择,大于平均能量的节点优先选择为候选簇头,由于平均能量是全网的信息,因此可以有效地描述全网的能量状态。当候选簇头选好后,算法便进入最终簇头产生阶段。引入基于竞争机制的簇头选举算法来获得最终的簇头,选好的簇头向它周围的节点广播加入消息,周围节点可以根据所提出的能量消耗率函数选择加入的簇头,随后节点向选择的簇头发送应答消息,确认自己加入该簇,完成簇的建立,最后将完全融合后的数据直接发送给基站,完成一轮的数据传送工作,等待进入下一轮。但是对于簇成员的能量消耗也是不能忽略的,因为簇成员也有可能成为簇头。在EECS算法中,选择簇头时,主要在候选簇头里选择真正的簇头,但是对于候选簇头而言并不一定是所有节点中剩余能量较高的,对于此算法而言由于引入了平均能量阈值,使得选取的候选簇头是剩余能量最高的,保证了候选簇头的高能量特性,因此算法具有很好的结果。算法1给出了整个算法的伪码,sj.ACH表示以候选簇头sj为中心,以sj.R为半径的所有候选簇头集合。算法1DEEUC算法伪码在此算法中,每个节点均以同样的功率发送广播消息,为了节约能量,这个广播半径为Rmax(Rmax为最大簇头半径)即可。算法首先根据阈值大小和节点的剩余能量状态,产生候选簇头;然后通过竞争算法获得最终簇头;最后每个簇头广播HEAD_MSG消息,消息的内容为节点的ID、节点到达簇头的最大距离dn_CH(为节约能量使dn_CH=Rmax即可)。节点根据收到的广播消息计算能量消耗率函数f(i,j),选择f(i,j)最小的簇头加入,最后发送加入消息JOIN_ClusterHead_MSG,通知该簇头。簇头选择完成后,节点根据能量消耗率函数选择加入的簇头,进入簇内数据传输阶段,簇头构建TDMA调度,然后簇成员向簇头传输数据。性质在所选网络中,DEEUC算法的消息复杂度为O(N)。证明首先,基站(BS)广播一条平均能量AE_MSG消息给每个节点。其次,有N×Threshold个节点成为候选簇头,共广播N×Threshold条COMPETE_HEAD_MSG消息,然后每个候选簇头广播一条FINAL_HEAD_MSG消息宣布其竞选成功,或者广播一条QUIT_MSG消息宣布其退出竞选。假设共选出k个簇头,每个簇头广播一条HEAD_MSG消息,而N-k个非簇头节点广播一条JOIN_ClusterHead_MSG消息。因此消息开销为所以消息复杂度为O(N)。性质说明DEEUC算法的消息开销比较小,进而算法具有较好的能量效率。HEED的簇生成算法需要在簇半径内进行多次消息迭代,由此带来的通信开销比较显著,一般其消息交换次数的上界为Niter×N,Niter是消息迭代的次数。因为DEEUC算法避免了消息迭代,因此消息开销低于HEED。对于EECS算法来说,消息复杂度也为O(N),与此算法相同,但由于EECS算法在选择簇头时未考虑簇头到基站(BS)的距离,因此未能有效地平衡簇头能量的消耗。4deeuc算法的性能比较为了说明算法效果,使用MATLAB对算法进行了仿真测试,选择的仿真场景参数如表1所示。算法中能量消耗率函数参数w的选择是十分重要的,因为w是平衡簇头和簇成员之间的权值,从0.1到1范围内进行实验,结果如图3所示,可以看出,w=0.5或w=0.6效果最好,在文中选择w=0.6。比较LEACH-C、EECS和DEEUC3种算法。图4是3种算法生命周期的比较,从图中可以看出,DEEUC生命周期最长,EECS次之,LEACH-C最差,其中DEEUC比LEACH-C的生命周期至少长45%以上,比EECS的生命周期延长达到约30%。从死亡节点的数量来看,DEEUC在1200轮时死亡节点数量不到20个节点,约占总节点数的2%,EECS死亡约170个节点,占总节点数的17%,LEACH-C最多死亡约390个节点,至少占39%,死亡节点数可以反映出网络中节点的能量均衡情况,死亡越少说明网络的能量使用效率越高。DEEUC不仅显著地延长了网络的生命周期,而且死亡节点数也远小于其他算法,这说明DEEUC很好地均衡了网络中所有节点的能量消耗。EECS已经引入了花费函数,但其性能略差于DEEUC,原因可能主要有3点:一是候选簇头的选取未充分考虑全网的能量利用情况;二是花费函数中仅注意到了距离因素,未考虑节点和簇头的剩余能量因素;三是簇头选举时未考虑候选簇头到基站(BS)的距离因素。LEACH-C在选取簇头时虽然考虑了节点的剩余能量,但由于其簇头数量波动较大,因此传播消息带来的能量开销最大,导致其性能最差。图5是簇头数量的比较,从图中可以看出,DEEUC和EECS算法产生的簇头数量稳定,LEACH-C簇头数量的波动范围最大,这是因为LEACH-C单纯性地采用随机数与阈值的机制产生簇头,因此簇头的数量变化比较明显。DEEUC和EECS的簇头数量比较集中,这是因为2种算法均采用了候选簇头在局部区域进行竞争的方法,有效地控制了算法所生成的簇头的数量。但是,DEEUC算法产生的簇头数量更集中于簇头数量的期望值,主要原因是提出的能量消耗率函数能更有效地刻划网络性能,使簇头分布和数量较为准确地描述了网络特性,因此簇头分布和数量能稳定更长的时间。图6是节点到簇头的信息量比较,从图中可以看出,DEEUC和EECS在第一个节点死亡之前的信息量是非常接近的,但是由于EECS生命周期小于DEEUC,当存在死亡节点时,DEEUC的信息量略大于EECS,在约850轮以后,信息量明显大于EECS,原因是EECS死亡的节点数增加很快,导致节点到簇头的信息量