基于LEACH协议的分簇算法设计.docx

基于LEACH协议的分簇算法设计.docx

《基于LEACH协议的分簇算法设计.docx》由会员分享，可在线阅读，更多相关《基于LEACH协议的分簇算法设计.docx（8页珍藏版）》请在冰点文库上搜索。

基于LEACH协议的分簇算法设计

基于LEACH协议的分簇算法设计

摘要：

基于对LEACH算法的研究，提出助理簇头ASCH算法。

该算法能够在无线传感器网络中，根据簇头节点所处的地理位置、剩余能量及簇内成员节点数目，动态决定是否需要在簇内产生助理簇头，并在需要产生助理簇头的簇内选择合适的节点来减少簇头通信能耗，同时解决某些簇头与基站通信可能存在困难的问题，从仿真结果可见此算法能有效均衡及降低网络能耗，达到延长网络的生存时间的目的。

　　关键词：

无线传感器网络；LEACH算法；分簇算法；助理簇头；通信能耗

　　0引言

　　在层次路由协议中，无线传感器网络被划分成多个簇，每个簇由一个簇头节点（ClusterHead）及多个簇内成员节点（ClusterMember）构成，多个簇头形成高一级网络。

在高一级网络中，又可以再分簇，再次形成更高一级网络，一直到最高级的汇聚节点为止。

　　层次结构中，每个簇的形成常常是基于节点能量及与簇头的接近程度。

簇头不仅要负责簇内信息的采集及融合处理，还要负责簇间的数据转发，它的可靠性和稳定性对于整个网络性能影响较大，信息的收集和处理也将消耗簇头的大部分能量。

　　1LEACH协议

　　LEACH（LowEnergyAdaptiveClusteringHierarchy）是为无线传感器网络设计的一种低功耗自适应的层次路由协议。

它的基本思想是以循环方式随机选取簇头，将网络的能量负载平均的分配到每一个节点之上，从而降低能耗和延长网络生命周期。

主要是通过随机选择簇头节点，平均的分担转发通信任务来实现。

　　LEACH算法中通过引入“轮（Round）”的概念，每轮由构建阶段（Set-up）以及稳态阶段（Stead-state）构成。

构建阶段中节点被分成若干簇，且产生相应簇头；稳态阶段中数据从非簇头节点被发给簇头节点，在簇头节点上处理后发给汇聚节点。

在簇的构建阶段，簇头节点的选择根据所需的簇头总数以及迄今为止每一个节点已成为簇头的次数来决定。

具体选择办法是每一个节点选择0~1之间的一个随机数，如选的a小于某阈值T（n），那这个节点就成为簇头节点。

T（n）的计算公式为：

　　T（n）=p[]1-rmod1[]p,n∈G0,其它情况[JY]

（1）

　　公式1的p是簇头数与总节点数的百分比；r是当前轮数；G是前r轮中未充当过簇头的节点集合。

节点确定自己成为簇头节点之后，广播自己成为簇头节点的消息，非簇头节点根据接收信号强度来确定要加入到哪个簇中，并且通知该簇头节点将成为它的一个成员节点。

簇头回复一个TDMA消息给簇内的成员节点。

稳态阶段，各节点在其时隙内把所监测到的数据发给簇头，簇头节点将接收到的数据融合，最后把结果发给汇聚节点。

　　LEACH使用随机选簇头节点方式，避免了簇头节点消耗过多能量，采用数据融合方法来有效减少通信量，因此和一般的多跳路由协议和静态聚类算法相比，可将网络生命周期延长15%。

但LEACH协议是假设所有节点都可以直接与簇头、汇聚节点通信，采用连续数据发送的模式及单跳路径选择的模式，所以在大范围监测应用中是不适合的，即使是在小规模网络中，距离汇聚节点远的节点由于大功率通信，也会导致生存时间比较短；并且动态地分簇也带来了拓扑变化和大量广播这样额外的开销，会耗费过多能量。

　　此外，LEACH假设簇内成员节点在属于它们的时隙内都有数据发给簇头，但实际情况有可能是节点只在监测到事件后才会发送。

而且，LEACH中簇头节点都是随机的产生的，并不考虑节点剩余能量，有可能导致剩余能量少的簇头节点的能量尽早耗尽。

　　2问题描述

　　LEACH是在无线传感器网络中最早提出的路由协议，并且是比较常用的分簇路由协议，LEACH协议可以使得所有节点在一个周期内都担任一次簇头，均衡的分担能耗，但簇头节点都是随机产生的，并不考虑节点地理位置，无法保证簇头节点均匀分布，有可能产生的大部分簇头节点集中在某一区域，或所产生的簇头节点分布在离基站较远的区域的情况，而与基站距离较远时进行通信，将消耗过多能量，簇头可能会快速死亡，影响传感器网络的生命周期；另外，协议中簇头的选择没有考虑节点的剩余能量，有可能导致某些剩余能量小的节点能量提早的耗尽；并且，由于随机的选举簇头则簇头需负担的簇内节点数不同，个别簇内节点相对较多的簇头负担会过重，网络的负载平衡度随之下降。

　　3助理簇头ASCH算法

　　许多分簇算法在节能方面都相当有成效，但是往往存在着簇头节点负担相对过重的问题，本文是从减轻簇头负担，以降低能耗这方面考虑，提出了助理簇头算法ASCH（AssistantClusterHead），此算法以LEACH为基础，在其基础上进行改进，算法根据簇头节点的剩余能量，簇头距离基站的远近以及簇内成员节点数目等因素产生阈值公式，来确定是否需要在簇内产生助理簇头ASCH，所选择的助理簇头负责转发本簇簇头的数据给基站，起到一个转发数据之功能，以此来分担簇头节点的负担，均衡能耗；然后，在需要产生助理簇头的簇内的非簇头节点中选择ASCH的时候，根据各成员节点发送数据的能耗以及它们自身的剩余能量情况，选择出合适的节点成为本簇的助理簇头ASCH。

　　3.1网络类型说明

　　传感器节点随机的分布于一个正方形区域内，对该传感器网络假设如下：

①每一个节点都有唯一ID，且节点初始能量相等；②传感器节点部署后，不会随时间推移而移动；③基站位于离传感器区域较远的地方；④每一个节点都能与网络中其他任一个节点通信，也能与基站直接通信；⑤节点可根据接收信号强度计算它到发射点的近似距离。

　　3.2ASCH的产生阈值

　　在网络的部署阶段，基站需向网内广播信号，每一个节点在接收到此信号之后，由接收信号强度来计算它与基站的近似距离。

算法仍采用LEACH算法构建阶段的簇头节点选择及成簇的方式，先是产生出簇头节点并形成簇，然后再产生助理簇头。

而关键首先考虑的问题是要在哪些簇内产生助理簇头，那么助理簇头ASCH的产生从3个方面来考虑，即簇头节点的剩余能量、簇头与基站的距离，及其簇内成员节点的数目。

一般情况下，在簇头剩余能量较少，离基站较远，以及簇内成员节点较多的簇内需产生助理簇头ASCH。

由此，可定义产生助理簇头ASCH的阈值T-{AS}的公式，其式如下：

　　T-{AS}=c•E-{re}[]E-{max}•d-{max}-d-{（c,b）}[]d-{max}•N-{total}-N-i[]N-{total}[JY]

（2）

　　其中，0

在簇的构建阶段，选择簇头节点时生成的随机数a如大于阈值T-{AS}，则此簇内需产生助理簇头ASCH，那么就从本簇的非簇头节点中选择助理簇头ASCH；相反的，则本簇就不产生助理簇头ASCH。

3.3簇内产生ASCH

　　在需要产生助理簇头的簇内的非簇头节点中选择出一个助理簇头，要考虑的是其接收和发送数据能耗E-{Tx}、E-{Rx}较少，而其节点剩余能量E-{re}较多。

　　在LEACH路由算法中使用的能量消耗的公式是一阶无线模型。

根据这种模式，将l位数据发送距离d的发送耗能和接收耗能，由下面方程表示：

　　发送能耗：

　　E-{Tx}（l,d）=E-{Tx-elec}（l）+E-{Tx-amp}（l,d）=lE-{elec}+lε-{fs}d+2,d＜d-0lE-{elec}+lε-{mp}d+4,d≥d-0[JY]（3）

　　接收能耗：

　　E-{Rx}（l）=E-{Rx-elec}（l）=lE-{elec}[JY]（4）

　　由公式（3）可知发送相同比特的数据时，距离越远所耗的能量越多，在我们选择ASCH时要求它的剩余能量多，且接收簇头数据的能耗和发送数据到基站的能耗要少，而由接收能耗公式（4）可知节点接收相同比特数据的能耗是相同的，所以接收能耗我们就不予考虑了，这里只考虑节点剩余能量E-{re}和发送能耗E-{Tx}，由此可以产生如下的公式：

　　T-i=E-{re}（i）[]E-{Tx（i,b）}[JY]（5）

　　其中：

E-{re}（i）为节点i的剩余能量；E-{Tx（i,b）}为节点i发送单位比特数据给基站的能耗，当节点i与基站的距离d

lE-{elec}+lε-{fs}d+2，若节点i与基站的距离d≥d-0时，使用：

lE-{elec}+lε-{mp}d+4。

当某一非簇头节点i的T-i值最大时，那么它就被选择成为助理簇头ASCH。

由此公式可以看出所选择的助理簇头的剩余能量较大，且发送相同比特数据到基站的能耗较少。

　　3.4算法描述

　　采用LEACH算法构建阶段的簇头选择及成簇方式选择出簇头并成簇，然后根据各簇头的自身情况确定是否需要在簇内产生助理簇头ASCH，之后在这些需要产生助理簇头的簇内选择出一个合适的节点成为ASCH。

在稳态阶段，簇内节点在各自的时隙内向簇头节点发送数据，该助理簇头ASCH不参与簇内数据采集等活动，只负责监听簇头节点的活动，簇头节点在收到数据后进行数据融合处理，去除冗余数据信息，提取关键的信息，然后将数据转发给此助理簇头ASCH，由此ASCH再传输给基站。

　　算法描述如下：

　　while（True）

　　{floata,T（n）,T-{AS},T-i;

　　基站向网络内广播一个信号，节点在接收到此信号后，由接收信号的强度计算它到基站的近似距离；

　　计算阈值T（n）;

　　if（a

　　节点当选为簇头并广播当选消息，等待非簇头节点的加入；

　　各簇头节点计算阈值T-{AS};

　　if（a>T-{AS}）then

　　{

　　此簇内需要产生助理簇头ASCH，簇头节点等待簇内节点的T-i值信息；

　　然后把T-i值最大的节点的ID号发送给簇内节点，告知成员节点谁被选为助理簇头ASCH；

　　}

　　else发送TDMA时隙给簇内成员节点;

　　else

　　非簇头节点接收簇头广播消息，依信号强弱加入簇；

　　if（非簇头节点位于需要产生ASCH的簇内）then

　　各非簇头节点计算T-i值，发送Ti值信息给簇头；

　　然后接收来自簇头的T-i值最大的节点ID信息，知道自己是否被选为助理簇头ASCH；

　　if（被选为ASCH）履行助理簇头的义务；

　　else接收簇头发送的TDMA时隙消息

　　进入稳态传输阶段；

　　}

　　4仿真试验

　　下面使用MATLAB2009对LEACH和ASCH进行仿真，对两者做了比较。

假定网络由200个传感器节点组成，随机的分布在200m×200m的范围内，所有节点都不移动，E-{elec}=50nJ/bit，ε-{fs}=10pJ/bit/m+2。

　　图1是基站位于（100，300）点时，节点存活个数和网络工作时间（轮数）间的关系图，由图可看出ASCH的节点运行时间要长于LEACH，且第1个节点和最后一个节点的死亡时间较接近，第一个节点的死亡时间延长了63%，提高了网络寿命。

　　从图2中可看出，在相同时间内ASCH的能耗要小于LEACH，这是由于ASCH算法更好的使得每一个节点相对均匀的分担能耗，更有利于能量的均衡，节省了整个网络的能量。

　　图3是基站所处位置不同的时候与网络生存时间间的关系，从图中可看出，随着基站距离的增大，ASCH的网络寿命减少地相对较慢，当基站位置从（100，250）到（100，450）时，ASCH网络寿命从713轮减少到436轮，减少约39%，其性能远优于LEACH。

　　5结束语

　　助理簇头ASCH算法可动态决定是否需要在簇内产生助理簇头ASCH，并在需要产生ASCH的簇内选择合适的节点成为ASCH，以此来减少簇头通信的能耗，同时也解决了某些簇头与基站通信存在困难的问题。

　　参考文献：

　　[1]YOUNISO,FAHMYS.Heed:

Ahybrid,energy-efficient,distributedclusteringapproachforAd-Hocsensornetworks[J].IEEETransonMobileComputing,2004（4）.

　　[2]HEINZELMANW,CHANDRAKASANA,BALAKRISHNANH.Anapplication-specifiedprotocolarchitectureforwirelessMicrosensorNetworks[J].In:

IEEETransactiononWirelessCommunications,2002（10）.

　　[3]HEINZELMANW,CHANDRAKASANA,BALAKRISHNANH.Energy-EfficientCommunicationProtocolforWirelessMicrosensorNetworks[A].IEEEProceedingsoftheHawaiiInternationalConferenceSystemSciences’00[C].2000.

　　[4]SLINDSEY,CSRAGHAVENDRA.PEGASIS:

powerefficientgatheringinsensorinformationsystems[C].In:

ProceedingsofIEEEAerospaceConference,2002.

　　[5]韩冬雪,张瑞华,刘丹华.基于PSO的无线传感器网络双簇头分簇算法[J].计算机工程,2010（10）.

　　[6]袁辉勇,李小龙,戴经国,等.一种不均衡的无线传感器网络分簇算法[J].计算机工程,2009（12）.

　　[7]任丰原,黄海宁,林闯.无线传感器网络[J].软件学报,2003（8）.

　　[8]赵泽,崔莉.一种基于无线传感器网络的远程医疗监护系统[J].信息与控制,2006

（2）.

　　[9]于海滨.智能无线传感器网络[M].北京:

科学出版社,2006.