湖南大学无线传感器网络论文3Leach算法简述

LEACH算法的简述计科一班刘家宇20110801126摘要：无线传感器网络是众多的传感器通过无线通信的方式，相互联系，处理、传递信息的网络，在军事、工业、交通、安全、医疗、探测以及家庭和办公环境等很多方面都有着广泛的用途，其研究、开发和应用，关系到国家安全、经济发展的各个方面，近年来在国际上引起了广泛的重视和投入。由于外界环境的不确定性，经常导致需要部署成百上千的传感器协同工作，故对由大量传感器构成的大规模传感器网络的研究正逐渐引起关注，并被认为是本世纪的一项具有挑战性的研究课题。目前，学术界的研究热点主要集中在传感器网络分簇算法、通信路由协议、网络覆盖等领域。LEACH算法是一种典型的层次路由算法，该算法提出了低功耗持续运行的模型。但LEACH算法也存在没有考虑能量的消耗和传感器拓扑结构的问题。关键词：传感器网络；LEACH算法；分簇算法；Abstract：Wirelesssensornetworksareakindofnetworkwhichalotofsensorsinterrelate,processandtransmitinformationwitheachotherthroughwirelesscommunications.Thenetworkintegratessensortechnology,embeddedcomputingtechnology,distributedinformationprocessingandcommunicationtechnologywhichcanbereal-timemonitoring,sensingandacquisitiontheinformationofvariousenvironmentalmonitoringortargetingobjectwithinregionalofdistributionnetworks.Suchinformationwillbeprocessedandtransmittedtotheuser.Wirelesssensornetworksarewidelyusedinmilitary,industrial,transportation,security,medical,detection,familyandofficeenvironment.Theresearch,developmentandapplicationofitrelatestonationalsecurity,economicdevelopmentandotherimportantfields.Inrecentyearsthewirelesssensornetworkshavebeencausedmuchattentionandinvestment.Externaluncertaintyenvironmentoftenleadstohundredsofsensorsshallbedeployedtoworktogether,sothelarge-scalesensornetworksresearchisgraduallyarousedwidespreadinterestandconsideredachallengingresearchtopicofthiscentury.Againsttheaboveproblems,theacademicresearchmainlyconcentratedinthesensorclusteringalgorithm,communicationsroutingprotocols,networkcoverageandsensordatafusiontechnology.LEACHalgorithmisatypicallevelroutingalgorithm.Thisalgorithmputforwardacontinuedoperationoflow-powermodel.ButLEACHalgorithmdidnotconsidertheproblemofenergyconsumptionandtopologyofthesensor.Keyword：Sensornetworks;LEACHAlgorithms;ClusteringAlgorithms;一、引言无线传感器网络是一种全新的信息获取技术，是新兴的下一代无线网络，具有广泛的应用前景。传感器节点主要由电池供电，且大都分布在无人看管、几乎不可能更换电池的环境中，如何能提高能量的有效利用率并延长网路寿命是一个重要的问题。对网络通信及拓扑控制方面的研究现在正成为无线传感器网络研究中的热点。在上述背景下，各种有关传感器网络的路由算法和通信协议纷纷被提出，其中，Heinzelman等人提出的LEACH算法是最具代表性和里程碑意义的。[1]LEACH（低功耗自适应分簇）算法就是针对无线传感器网络而提出的一种层次型拓扑组织算法。本文首先对经典的LEACH算法进行简要分析，并结合前人工作已提出的一些较为重要的改进算法进行对比和剖析。二、LEACH算法LEACH（Low-EnergyAdaptiveClusteringHierarchy）是一种自适应分簇拓扑算法，它的执行过程是周期性的，每轮循环分为簇的建立阶段和稳定的数据通信阶段。在簇的建立阶段，相邻节点随机产生簇头，动态地形成簇；在数据通信阶段，簇内节点把数据发送给簇头，簇头进行数据融合并把结果发送给汇聚节点。LEACH算法中簇头的选择是依据网络中所需要的簇头节点总数和迄今为止每个节点已成为簇头的次数来决定的。具体的选择办法是：每个传感器节点选择0-1之间的一个值，如果选定的值小于某个阈值，那么这个节点成为簇头节点。节点当选簇头以后，广播告知其他节点自己是新簇头。非簇头节点根据自己与簇头之间的距离来选择加入哪个簇，并告知该簇头。当簇头接收到所有的加入信息后，就产生一个TDMA定时消息，并且通知该簇中所有节点。为了避免附近簇的信号干扰，簇头可以决定本簇中所有节点所用的CDMA编码。这个用于当前阶段的CDMA编码连同TDMA定时一起发送。当簇内节点收到这个消息后，它们就会在各自的时间槽内发送数据。经过一段时间的数据传输，簇头节点将运行数据融合算法来处理收到的数据，并将结果直接发送给汇聚节点.相比较平面路由算法而言，LEACH算法具有以下的优点：①成员节点大部分时间可以关闭通信模块，由簇头构成一个更上一层的连通网络来负责数据的长距离路由转发。这样既保证了原有覆盖范围内的数据通信，也在很大程度上节省了网络能量。②簇头融合了成员节点的数据之后再进行转发，减少了数据通信量，降低了数据冗余，在节省了通讯能量的同时也降低了传感器网络在数据计算方面的能量开销。③成员节点的功能比较简单，无须维护复杂的路由信息。这大大减少了网络中路由控制信息的数量，减少了通信量。④分簇拓扑结构便于管理，有利于分布式算法的应用，可以对系统变化作出快速反应，具有较好的可扩展性，适合大规模网络。LEACH算法首先作了如下的假设：a.基站(BS)远离传感器网络节点并且是稳定的。b.传感器网络中的所有节点是同构的，并且能量都受到限制。c.所有节点可以直接和基站通讯。d.节点都没有位置信息。e.簇头节点负责数据压缩汇聚以及与基站进行通讯。该算法主要通过随机选择簇首领，平均分担中继通信业务来实现节能。同时LEACH定义了“轮”(Round)的概念，针对每个节点n设定了一个阀值T(n)：：否则：若0)1mod(1)(GnprppnT(1.1)式(1.1)中p表示簇头节点占网络节点总数的百分比，r表示重新挑选簇头节点的轮数，G表示网络中最近1/p轮未当选簇头的节点的集合。并根据该阀值从候选节点中挑选簇头，具体的步骤：Step1：若传感器节点Ni∈G，则对于每个Ni独立运算(2.1)式，获得阀值T(n)。Step2：若Ni不属于G，则根据(2.1)式，T(n)为零。Step3：Ni产生一个0~1之间的随机数RadomNum。Step4：若T(n)＞RadomNum，则该节点当选为簇头，并广播当选消息。Step5：其余节点选择加入某簇头所在的簇，形成稳定的拓扑结构。Step6：稳定工作阶段。Step7：每隔时间t，进行下一轮簇头选取，转Step1，重新选择簇头并成簇。由以上步骤可知LEACH算法中的轮是指两次簇头选取之间的时间段，每一轮由初始化和稳定工作两个阶段组成。在初始化阶段，随机选择节点为簇首领，成为簇首领的节点向周围广播信息，其它节点根据接受到广播信息的强度来选择它所要加入的簇，并告知相应的簇首领，由于信息的强度和节点之间的距离是成正比的，因此，实际上各非簇头节点是选择距离自己地理距离最短的簇头所在的簇加入，并形成簇拓扑结构，如图1.2所示：图1.2成簇阶段图传感器网络首先产生中心节点，其余节点加入距离自己最近的中心节点所在的簇，然后由中心节点直接和SINK节点进行通讯。在稳定工作阶段，节点持续采集监测数据，传送到簇头，由簇头对数据进行必要的融合处理之后，发送到终端节点。每轮工作周期结束后，重新选择簇头并重复前面的工作。三、LEACH算法存在的问题与改进对上述的LEACH算法分析，我们不难发现其中存在着以下的诸多问题：1.算法没有考虑簇头节点在簇结构中的位置对簇头能耗的影响。在簇头选取的过程中，位于簇中心位置的节点和位于簇边缘位置的节点成为簇头的机率是一样的。由于位于簇边缘位置的簇头其通讯能耗远大于位于簇中心位置的簇头，因此将导致各簇头能耗不均衡，使某些簇头节点能量提前耗尽。2.LEACH没有考虑到传感器网络在进行部署的时候，节点分布密度对簇头能耗的影响。由此导致在传感器节点密集分布区域的簇头能耗巨大，而在传感器节点稀疏分布区域的簇头能耗较小，网络中各簇头的能耗极不均衡。3.动态分簇引起网络拓扑结构频繁变换和大量广播通信，从而带来了额外的能量开销。1．未考虑簇头在簇结构中位置时存在的问题为指出未考虑簇头在簇结构中位置时LEACH算法中存在的问题，首先假定通过飞机播撒等方式部署的传感器网络中已经形成了若干个簇。其中有某个簇由5个传感器节点构成，且簇中各节点A，B，C，D，E的初始能量均为40，该簇的5个传感器节点的具体分布情况如图1.3所示。图1.3具有5个节点的传感器网络为计算方便，且假定簇中各节点A，B，C，D，E两两之间的距离如表1.1所示：表1.1图1.3中节点A,B,C,D,E两两间的距离距离ABCDEA01243B10364C23032D46303E34230假定在每轮通信中，各簇成员分别发送一次数据给簇头，则每轮通信中各节点的工作能耗如表1.2所示：表1.2A,B,C,D,E分别为簇头时各节点的工作能耗簇头/能耗ABCDEA102486B2146128C461064D8126166E684612基于式(1.1)可知：采用LEACH算法时整个网络的生命周期可能如表2.3所示：表1.3采用LEACH算法时整个网络的生命周期簇头/剩余能量ABCDE第1轮：A为簇头3038363234第2轮：B为簇头2824302026第3轮：C为簇头2418201422第4轮：D为簇头16614-216显然，采用LEACH算法时，整个网络的生命周期将小于4轮。从上面的分析不难看出，LEACH算法进行第四轮簇头选取时，没有考虑到节点的剩余能量及其工作能耗，导致剩余能量小于工作能耗的节点D当选为簇头，使节点D的能量过早衰竭，网络的生命周期也随之结束。若结合考虑节点的位置信息，使靠近簇结构中心位置且剩余能量较多的节点有更多机会成为簇头，无疑将有效延长网络的生命周期。2．未考虑节点分布密度时存在的问题为考虑节点分布密度对网络生命周期的影响，给出一个具有8个节点的传感器络，如图1.4所示。图1.4具有8个节点的传感器网络假定各节点的初始能量均为20，各节点簇内通讯半径为10。其中D，F，H三个节点为最近1/p轮未当选簇头的节点。网络中各节点A，B，C，D，E，F，G，H两两之间的距离