无线传感器网络的leach算法及其改进

1无线传感器网络LEACH算法的研究与改进杨林(华南理工大学自动化科学与工程学院,广东广州510640)摘要：本文重点研究基于无线传感器网络的LEACH和SEP式路由协议，无线传感器网络节点数量庞大、单个节点资源有限，其路由协议设计的首要目标是提高能量有效性，延长网络寿命。本文选择了LEACH路由协议为研究重点，分析了该路由算法的具体实现，针对传感器节点能量及网络生存周期等特点，介绍了其改进型SEP路由算法。并采用MATLAB网络仿真工具对该路由协议进行了整体仿真，并对其数据进行了分析。关键词：无线传感器网络；LEACH路由协议；SEP路由协议；MATLAB仿真ImprovementofleachalgorithmforwirelesssensornetworksYangLin(CollegeofAutomationScienceandTechnology,SouthChinaUniversityofTechnology,GuangzhouGuangdong510640,China)Abstract:ThispaperfocusesonLEACHandSEProutingprotocolbasedonwirelesssensornetworks,wirelesssensornetworknodeahugenumber,thelimitedresourcesofasinglenode,theroutingprotocoldesigngoalistoimproveenergyefficiency,andprolongthenetworklifetime.ThispaperstudiestheLEACHroutingprotocolanalysiswithafocusontheconcreterealizationoftheroutingalgorithmforsensornodeenergyandnetworklifecyclecharacteristics,itsimprovedSEProutingalgorithm.Keywords:WSN;LEACHroutingprotocols;SEProutingprotocols;MATLABSimulation1引言无线传感器网络(WirelessSensorNetwork,WSN)是目前国际上研究的热点，它融合了计算、通信和传感器这3项技术的交叉应用，具有十分广阔的应用前景。在网络中，数据的传输是靠路由协议控制管理的。因此，要设计一个优良的网络系统离不开路由协议的研究。无线传感器网络的特点有：(1)节点没有全球唯一的标识符，传统的互联网路由协议无法应用在传感器网络中。(2)传感器网络中的所有节点都是源节点，向唯一的目的节点Sink发送数据。(3)由于在被测对象内部或附近部署了大量的节点，它们采集到的数据是相同或相近的。这就需要路由协议具有数据融合能力。(4)节点具备的处理能力、电能和存储能力很有限。开发针对WSN的路由协议成为目前无线传感器网2络研究的热点和难点。2WSN简介2.1WSN概念无线传感器网络（wirelesssensornetwork）简称WSN，是一种由大量小型传感器所组成的网络。这些小型传感器一般称作sensornode（传感器节点）或者mote（灰尘）。此种网络中一般也有一个或几个基站(称作sink)用来集中从小型传感器收集的数据。2.2WSN的结构2.2.1节点结构在不同应用中，传感器节点的结构不尽相同，但一般都由传感器模块、处理器模块、无线通信模块和能量供应模块四部分组成，如图2.1所示。图2.1传感器网络节点结构Figure2.1Nodestructureofsensornetwork传感器模块负责监测区域内信息的采集和数据转换，传感器的类型是由被监测物理信号的形式决定的，如用于温度监测的铂电阻传感器，用于压力传感的电容式传感器等;处理器模块负责控制整个传感器节点的操作，存储和处理本身采集的数据以及其他节点发送来的数据;无线通信模块负责与其他传感器节点进行无线通信，交换控制信息和收发采集数据;能量供应模块为传感器节点提供运行所需的能量。2.2.2网络体系结构无线传感器网络典型的体系结构如图2-2所示，包括大量随机分布的传感器节点(sensornode)、汇聚节点(sinknode)、互联网(internet)、用户终端(user)等。散布在监测环境中的传感器节点通过网络自组织多跳方式，将数据向汇聚节点发送，汇聚节点可以使用多种方式与外部网络通信，如Internet卫星或移动通信网络等等，将整个区域内的数据传送到用户终端，用户通过管理节点对无线传感器网络进行配置管理。ABCSinkUserSensorNodeSensorFieldInternet图2.2无线传感器网络体系结构Figure2.2Structureofwirelesssensornetwork23LEACH路由协议的分析与研究LEACH是第一个在无线传感器网络中提出的层次式路由协议。其后的很多层次式路由协议都是在它基础上提出来的。因此这里我们着重介绍LEACH协议。3.1LEACH协议模型LEACH是MIT的Chandrakasan等人为无线传感器网络设计的低功耗自适应聚类路由算法。与一般的平面多跳路由协议和静态聚类算法相比,LEACH可以将网络生命周期延长15%,主要通过随机选择聚类首领,平均分担中继通信业务来实现。LEACH定义了“轮”(round)的概念,一轮由初始化和稳定工作两个阶段组成。为了避免额外的处理开销,稳定态一般持续相对较长的时间。如图3.1所示图3.1LEACH协议的时序图Figure3.1ThesequencediagramofLEACHprotocol在初始化阶段,聚类首领是通过下面的机制产生的。传感器节点生成0,1之间的随机数,如果大于阈值T,则选该节点为聚类首领T的计算方法如下：prPPT1mod1（1）其中p为节点中成为聚类首领的百分数,r是当前的轮数。当簇头选定之后，簇头节点主动向网络中节点广播自己成为簇头的消息(ADV_CH)。接收到此消息的节点，依据接收信号的强度，选择它所要加入的簇，并发消息通知相应的簇头(JOIN_REQ)。基于时分多址(TimeDivisionMultipleAddress，简称TDMA)的方式，簇头节点为其中的每个成员分配通信时隙，并以广播的形式通知所有的簇内节点(ADVSCH)。这样保证了簇内每个节点在指定的传输时隙进行数据传输，而在其他时间进入休眠状态，减少了能量消耗。在稳定工作阶段，节点持续采集监测数据，在自身传输时隙到来时把监测数据传给簇头节点(DATA)，如图4.2所示。簇头节点对接收到数据进行融合处理之后，发送到Sink节点，这是一种减小通信业务量的合理工作模式。持续一段时间以后，整个网络进入下一轮工作周期，重新选择簇头节点。图3.2LEACH协议过程Figure3.2ProgressoftheLEACHprotocalsLEACH协议采用动态转换簇头的方法来平均网络节点的能量消耗，使因能量耗尽而失效的节点呈随机分布状态，因而与一般的多跳路由协议和3静态簇算法相比，LEACH可以将网络生命周期延长15%。但是LEACH协议在每轮固定簇头节点后在划分簇的过程中，簇头节点开销较大。并且簇头节点的选择无法达到最优，有可能簇头节点位于网络的边缘或者几个簇头节点相邻，某些节点不得不传输较远的距离来与簇头通信，这就导致了大量能量消耗。而且LEACH协议所有簇头节点直接与Sink节点通信，采用连续数据发送模式和单跳路径选择模式，使得每轮中簇头节点能耗巨大，因此不适合在大规模的传感器网络中应用。3.2LEACH协议的优缺点LEACH算法是第一个针对无线传感器网络提出的层次型网络拓扑组织算法，与节点直接向BS发送数据的方式相比，在性能上有很大提升，但是该算法在某些方面还是存在一定局限性的。(1)优点LEACH协议是一种层次结构的路由协议，簇首形成高一层的网络，这样簇内成员的功能就变得相对简单，并且不需要维护复杂的路由信息，大大减少路由控制信息的数量。另外，LEACH算法随机选取节点作为簇首，并且簇首是轮换选举的，这样能量的高消耗就平均分配到网络的所有节点上，以此来延长网络生命周期。最后，LEACH协议中簇的组织形式使网络具有很好的扩展性。(2)缺陷LEACH协议中簇首不仅要接收簇内成员节点采集的数据并对其进行融合，而且还要将数据发送给BS，因此消耗的能量比普通的成员节点多，很容易失效，从而导致频繁分簇，分簇过程中所消耗的能量对于整个网络中的能耗是一种额外的头开销，如果频繁分簇的话，所产生的头开销就会增加，所以网络节点能量的利用率就会相应降低。另外，LEACH协议只适用于小规模的无线传感器网络。由于簇内成员将原始数据经过单跳直接发送给簇首，簇首将融合后的数据经过单跳再发送给BS，所以簇内成员与簇首、簇首与BS之间必须布置在通信可达的范围内。3.3LEACH的改进型SEP协议经典的聚类协议假定所有的节点都配备了相同数量的能量，因此，他们不能充分利用节点异质性的存在。本文推荐一种能够异构感知的SEP协议，该协议可以延长第一个节点的死亡时间（也就是稳定期）。稳定期的延长对于许多应用程序是至关重要的，因为它们从传感器网络的反馈要求必须是可靠的。为了延长稳定期，SEP协议试图维持均衡的能源消耗。直观上，SEP协议高级节点（初始能量高的节点）成为簇头的概率大于普通的节点（初始能量低的节点），这就相当于对于能源消耗的约束。SEP协议假定每个节点知道网络的总能量，然后根据节点的剩余能量计算出成为簇头的最佳概率。开始时先给每个节点分配一个权重对应于最优概率optP，权重必须等于每个节4点的初始能量除以普通节点的初始能量。并且还定义nrmP为普通节点加权选举的概率，advP为高级节点加权选举的概率。amPPoptnrm1（2））1（1aamPPoptadv（3）其中a为高级节点的初始能量是普通节点初始能量的倍数，m为高级节点在总节点数中所占比例。普通节点与高级节点成为簇头的阀值分别为)(nrmsT和)(advsT，计算公式如下：pnrmnrmnrmnrmrPPsT1mod1)(（4）padvadvadvadvrPPsT1mod1)(（5）其中r是当前轮数。从而可以保证剩余能量高的节点成为簇头的概率大于剩余能量低的节点。与传统的LEACH相比有如下优势：（1）不同节点的初始能量的不同，SEP协议选择能量大的为簇头从而延长了第一节点的死亡时间，也就是延长了稳定期。（2）由于稳定期的延长，SEP协议的吞吐量也高于其他聚类协议。（3）在一个理想的阶段SEP协议的能量均匀的分布在传感器网络中的所有节点上。4LEACH与SEP协议MATLAB仿真比较4.1LEACH与SEP仿真结果我们在MATLAB编程环境中首先产生一个100×100的区域，并在其内部随机生成一个含有100个节点（坐标不同）的连通图。假设每个节点在网络形成前已知需要传感的数据类型，且能检测到出现在其检测范围内的事件。Sink在网络区域内，不考虑Sink的能耗。普通节点初始初始能量为40mJ。MATLAB中的实验结果图如图4.1a~4.1d所示。图4.1a节点分布图Figure4.1aDistributionofnodes图4.1b存活节点数量图Figure4.1bTheamountofalivenodes5图4.1c剩余能量图Figure4.1cRemainingenergy图4.1d最终节点分布图Figure4.1dFinaldistributionofnodes为具体比较LEACH与SEP协议性能，我们在MATLAB编程环境中首先产生一个100×100的区域，并在其内部随机生成一个含有100个节点（坐标不同）的连通图，而且随机选择100*m个节点作为高级节点。假设每个节点在网络形成前已知需要传感的数据类型，且能检测到出现在其检测范围内的事件