LEACH协议的簇头多跳LEACHM改进算法

LEACH协议的簇头多跳（LEACH-M）改进算法摘要：节能高效的实现路由转发是路由设计的一个关键点。总结了目前已有的无线传感器网络的传输路由模式，发现早先提出的LEACH协议虽是无线传感网中的低功耗自适应分层路由算法，但会造成簇头节点负载过重。成簇算法是传感器网络中减少能量消耗的一种关键技术。提出的是基于LEACH算法的多跳路由改进算法，并在考虑簇头最优个数的选择下，通过采用簇头之间的多跳算法达到减少能量消耗、延长传感网的寿命的目的。实验表明此方法有效。关键词：低功耗自适应分簇聚类路由（LEACH）协议；簇头；轮；LEACH协议的簇头多跳算法DOI：10.3778/j.issn.1002-8331.2009.34.033文章编号：10028331（2009）34-0107-03文献标识码：A中图分类号：TP3931引言无线传感器网络（WirelessSensorNetworks，WSN）综合了传感器技术、嵌入式计算技术、分布式信息处理技术和无线通信技术，能够协作地实时监测、感知和采集网络分布区域内的各种环境或监测对象的信息，并对这些数据进行处理，获得详尽而准确的信息，传送到需要这些信息的用户。传感器网络在环境与军事监控、地震与气候预测、地下、深水以及外层空间探索、生物医疗健康、空间探索等许多方面都有广泛的应用前景，是目前国际科学研究的热点。传感器网络相对于传统网络具有以下特性：（1）节点分布极其稠密且数目很大，每个节点均维护全局信息是不可能的；（2）节点的能量、存储空间及计算能力等资源非常有限，而且各种资源无法补充；（3）网络内节点大部分是静止的，而且恶劣的工作环境使得节点失效的概率很高。因此，传统上有线网络中基于链路状态或距离向量的路由算法以及AdHoc网络中的常用的DSDV，AODV等路由算法由于几乎没有考虑节点失效的问题因而并不适合于传感器网络，必须针对其特性研究新的路由算法，由于传感器节点通常由电池供电，高效使用有限的电池资源，尽量延长节点的生命周期是任何路由协议的首要考虑因素，尤其是对节省节点能源损耗的路由算法研究就显得更为重要。2无线传感器网络的路由2.1路由算法的进展针对WSN的特点与通信需求，网络层需要解决通过局部信息来决策并优化全局行为（路由生成与路由选择）的问题。为此，国内外科研人员设计了多种路由协议。目前已有的路由种类很多，有基于能量的路由、基于协商的路由、进行分层和查询的路由等等。从网络拓扑结构的角度可分为两类：平面路由协议和分层路由协议，如图11所示。平面路由协议中，节点间地位平等，通过局部操作和反馈信息来生成路由。平面路由的优点是简单、易扩展，但平面路由协议需要维持路由表，在大规模网络中，这样的路由表维持需要消耗大量的存储空间，同时发送信息中所包含的路由信息也会引起通信负担的加重，缺乏对通信资源的优化管理，对网络动态变化的反应速度较慢。典型的平面路由算法有：SPIN（SensorProtocolforInformationviaNegotiation）、DD（DirectedDiffusion）、HREEMR、SAR（SequentialAssignmentRouting）、SMENCE等。其中，SPIN2和DD3是以数据为中心路由协议的典型代表。与平面结构对应的是层次结构。典型分层网络一般以簇的形式存在，LEACH（LowEnergyAdaptiveClusteringHierarchy）4是第一个基于多簇结构的集群路由协议，它的成簇方法贯穿于其后提出的很多层次路由协议中，如TEEN（ThresholdsensitiveEnergyEfficientsensorNetworkproto-col）、PEGASIS（Power-EfficientGatheringinSensorInfor-mationSystem）等。但是，分层网络中的群头节点（以分簇网络中的簇头为典型）是瓶颈，如果群内节点数量众多，簇头能量又是有限的，那么很容易很快耗光群头节点的能量。2.2LEACH协议LEACH算法建立在所有节点都是平等且无线电信号在各个方向上能耗相同的假设上。在LEACH算法中，节点自组织成不同的簇，每个簇只有一个簇头。所有非簇头节点将自己的数据发给所属簇的簇头节点，为减少冗余数据的传输，簇头节点在数据融合后将数据发送给远方的接收器。这样，每个非簇头节点都只需要知道自己所属簇的簇头信息即可；簇头也只需要维持很小的路由表。在实际使用中，还可以根据需要建立更多层次。在LEACH算法中，为了避免簇头能量消耗过快，每个节点须轮流担任簇头。因此LEACH算法的实现分成一个个回合，每个回合又可分成簇形成阶段和簇稳定阶段。为了减少分簇带来的额外能耗，簇稳定阶段远远长于簇形成阶段。在簇形成阶段，每个传感器节点先生成01之间的随机数，如果生成的随机数小于阀值，那么这个节点就被选为簇头。阀值的大小由式（1）确定：I=p1-p*（rmod（1p）cG0其他（1）其中：p是网络中簇头所占比例，r是目前进行的回合次，G是在最后1/p轮中没有成为簇头的节点集合。节点被选为簇头后，就向外发送广播信息；其他节点根据收到的广播信息的信号大小决定要加入的簇，并向簇头发送加入簇的请求。簇头收到请求后将节点加入自己的路由表并为每个节点设定一个TDMA时间表，再将该表发送给所有簇内节点。此后的簇稳定阶段，节点按照该表进行数据传输。每隔一定时间整个网络重新进入簇形成阶段开始新一轮的簇头选举过程5-6。和平面路由算法相比，LEACH算法可以延长将近15%的网络生存时间。但是，由于LEACH算法中簇头的产生具有极大的随机性，可能会出现部分簇头相距基站远近不一，或者节点相距簇头远近不一，以及每个簇中节点数目分布不均匀，网络拓扑结构分布不均匀使得节点消耗能耗不一，大大减少了网络生存时间。另外在节点被选为簇头后，以另外的簇头为中转站向基站发送数据的时候，由于中转站节点有可能正在接收其他节点给它发送数据，容易导致冲突，影响网络作用。提出的是基于LEACH算法的多跳路由改进算法，并在考虑簇头最优个数的选择下，通过采用簇头之间的多跳算法达到减少能量消耗的目的。3基于LEACH协议的簇头多跳改进算法3.1算法的提出无线通信中，能量消耗E与通信距离d存在关系：E=kdn，其中k为常量，2n4。由于传感器网络中节点通常贴近地面，应用环境中可能有较多障碍物，接收天线的能力也有限，因此n接近于4。所以，在传感器网络中要减少单跳通信距离，使用多跳短距离无线通信方式。由于LEACH是一种低功耗自适应分簇和单跳路径选择模式协议，根据以下两点进行改进：（1）针对低功耗改进，其主要思想在于根据监测区域面积、节点数目及基站位置来确定最优簇个数而不是低功耗自适应算法中的固定值。（2）对于单跳路径选择模式，簇头节点离基站很远就会使簇头消耗很大的能量，导致簇头节点过早的死亡。为了减少簇头节点的负载，提出了基于LEACH协议的簇头多跳算法。综合以上两种情况，提出了LEACH算法的多跳路由改进算法。3.2算法的描述3.2.1确定最优簇头个数N在LEACH算法中，每轮循环的簇建立阶段要保证每轮形成N个簇，而这个N为系统参数，然而实际情况是N的值如果过小，网络中每个簇头的负担将加重，使某些簇头会过早地耗尽能量而死亡；如果N的值过大，因为每个簇头要向所有的节点发送广播信息，这样也会造成一些不必要的开销。因此，N的值应根据被测区域的面积及传感器节点的数目来确定，得出N的最优值，尽可能地延长整个网络的生命周期。设R为一个边长为2a的正方形被测区域，X（R）=T是在区域R中规则分布的传感器节点数目。文献7中指出基站与传感器节点的距离期望为：（2）其中这个距离期望主要取决于基站的位置坐标（x*，y*）。文献8对公式（2）进一步推导出当N为下面值时，网络消耗的总能量为最小值。3）其中Eelec是发射电路和接收电路所消耗的能量，它取决于电路的数字编码、调制和滤波等因素，在该文中发射与接收电路两者相同。3.2.2算法详细描述在N最优簇数目确定前提下，接下来提出多跳算法同样在运行过程中不断地循环执行簇的重构过程。每个轮也分成两个阶段：簇的建立阶段和传输数据的稳定阶段。簇的建立过程又可以分成4个阶段：簇首节点的选择、簇首节点的广播、簇的建立和调度机制的生成。（1）簇首节点选举办法和LEACH是相同的（N已经确定），这里就不详细叙述了；（2）簇首节点的广播、簇的建立和调度机制的伪代码：初始化时每个簇头包含以下信息：簇头编号i；簇头的位置Di（Xi，Yi）；其他簇头信息的集合Headi，初始值Headi=；该簇头与其他簇头之间距离的集合HeadDiN，初始值HeadDi=；该簇头与基站之间距离的集HeadBi，初始值HeadBi=0；并且已知基站的位置为BS（X，Y）。If（选定簇头节点i）/向网络中所有节点广播Headi=1，2，i-1，i+1，N；/簇头节点i收到其他簇头节点的广播信息后将其编号加入簇头集合HeadDiN=HeadDi1，HeadDi2，HeadDii-1，HeadDii+1，HeadDiN；/簇头i计算出和其他簇头之间的距离HeadBi=bsi/簇头i计算出和基站之间的距离其他节点根据信号强度选择从属的簇头，并发条信息通知簇首节点；/完成簇的建立簇首节点采用TDMA方法为簇中每个节点分配向其传送数据的时间片。/调度机制的生成（3）数据传输阶段对这一阶段算法思想采用逐步搜索的过程，首先找出基站到所有簇头的最短距离的簇头编号，然后以这个簇头编号查找到其他簇头之间的最短距离，由此类推，就寻找出到基站的最短距离。部分代码：lenmin=HeadB1；k=1；/lenmin初始值设为簇头编号1到基站的距离最短，并且用k记录编号，初始为1。for（i=2；iN；i+）/找簇头到基站的最短距离和该簇头的编号If（lenminHeadBi）Lenmin=HeadBi；k=i；SL=lenmin；lenmin1=HeadDk1；k1=1；f=1；/f控制循环的次数While（fHeadDkj）lenmin1=HeadBi；k1=j；SL=SL+Lenmin1；f+；lenmin1=HeadDk11；k1=1；SL就是反向建立起一条通向基站的最短的路径。然后从找到的最后那个簇头节点出发，传输并聚合数据，经过多跳，最终到达基站。然而这是个理想的寻径过程，在从中选取最小值的时候，HeadBi和HeadDiN时会出现两个或两个以上相等的最小值的情况。解决办法就是把SL设置为数组，把K和K1也置为数组，然后取SL的最小值，就确定了一条通向基站最短的路径，最后沿着这条路径融合传输数据。该程序在已经在C+环境下通过，限于篇幅不再介绍。4仿真结果与分析通过仿真实验比较改进算法（NEW）和LEACH，以及LEACH-M9算法。在图2是基站位置为（50，255），监测区域A大小为100m100m，节点数量为100时节点死亡数量与网络工作时间（轮数）之间的关系图，其中当T=100时，根据公式（2）和（3），得到簇的数目最优值Nopt=6。可以看到，NEW算法和LEACH-M的曲线几乎是一条平行于X轴的直线。由于这两个算法使得网络能耗被均匀地分担到每个节点上，因此第一个节点和最后一个节点的死亡时间非常接近，LEACH-M与LEACH相比使得网络寿命分别提高了46%（第一节点死亡），NEW与LEACH-M相比使得网络寿命分别提高了16%左右。NEW和LEACH-M的簇头之间采用多跳方式传输数据到达基站，所以基站与检测区域A之间的距离的增加对网络寿命的影响不大，而在LEACH协议中，基站与检测距离过大，就会导致一些簇头节点能量过快的损耗，从而影响了网络的寿命。图3描述网络寿命与基站位置之间的关系。从图3可以看出，随着基站距离的增大网络寿命衰减的速度变慢。实验表明，当基站位置从（65，215）到（65，390）时，网络寿命从420轮减少到250轮，减少幅度40.5%，优于LEACH-M和LEACH算法。5结论在考虑簇头最优个数的选择下，提出基于LEACH的簇头多跳改进算法，通过仿真实验，证明了得到最优簇数目的改进多跳算法比LEACH算法在能量开销和网络生命周期方面性能要好很多。由于改进的算法首先根据区域面积、节点数目及基站位置来确定最优簇数目而不是低功耗自适应算法中的固定值，并且还继承了LEACH按轮选举簇头的特点，使得能量消耗均衡的分布在各节点上，又对簇头节点采用了多跳算法，而且保证了数据尽快地传输到基站，弥补了LEACH算法单跳的不足，从而使网络寿命得到了相应的延长。参考文献：1YuHai-bin，ZengPeng，WangZhong-feng，etal.StudyofcommunicationprotocolofdistributedsensornetworkJ.JournalofChinaInstituteofCommnunications，2004（10）：102-110.2HeinzelmanKulkJ，BalakRishnanH.AdaptiveprotocolsforinformationdisseminationforwirelesssensornetworksC/ProcofACMConferenceonMobileComputingandNetworking，Washington，USA，1999：174-185.3IntanagonWiwatC，GovindanR，EstrinD.Directeddiffusion：AscalableandrobustcommunicationparadigmforsensornetworksC/ProcofACMConferenceonMobileComputingandNetworking，Boston，MA，2000.4HeinzelmanW，ChandrakasanA，BalakrishnanH.Energy-efficientcommunicationprotocolforwirelessmicrosensornetworksC/TheHawaiiIntlConfSystemSciences.Hawaii：IEEEComputerSociety，2000.5杨冕，秦前清.基于无线传感器网络的路由协议J.计算机工程与应用，2004，40（32）：130-131.6黄少昱，曹阳，王悦伟.无线传感器网络中的路由技术J.计算机工程与应用，2004，40（19）：123-126.7EdwardJ.AnenergyefficienthierarchicalclusteringalgorithmforwirelesssensornetworksC/ProceedingsoftheIEEEWirelessCommunicationsandNetworkingConference，2003.8张世庆，孙超，张西良，等.无线传感器网络高能效分簇路由算法J.传感器与仪器仪表，2006，22（11）：202-204.9李岩，张曦煌，李彦中.基于LEACH协议的簇头多跳（LEACH-M）算法J.计算机工程与设计，2007，28（17）：4158-4159.5 / 5