基于灰色关联度的Leach算法的改进

宋倩倩，王宏刚，卢光跃

(西安邮电大学 通信与信息工程学院，陕西 西安 710121)

基于灰色关联度的Leach算法的改进

宋倩倩，王宏刚，卢光跃

(西安邮电大学 通信与信息工程学院，陕西 西安 710121)

Leach算法是无线传感器网络中应用最为广泛的分簇路由协议之一，但是该算法的簇头是随机产生的，有可能导致节点过早死亡，从而使整个网络崩溃。针对这一问题，提出一种基于优选簇头的改进Leach算法——gcLeach算法。改进算法引入灰色关联度思想对簇头进行分区选举，兼顾考虑了簇头的剩余能量以及位置分布，有效地避免了簇头分布不合理，以及簇头剩余能量过低导致的节点过早死亡的情况。仿真结果表明，改进后的gcLeach算法能够有效地降低网络能耗，延长网络生命周期。

无线传感器网络；Leach算法；灰色关联度；簇头

无线传感器网络(Wireless Sensor Network,WSN)是由部署在监测区域内大量的廉价微型传感器节点组成，并通过无线通信方式形成的一个多跳的自组织网络系统，其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发送给用户[1]。它在军事、医疗、家庭智能和其他社会生活及生产活动领域有着广泛的应用前景。然而无线传感器网络也受到一些限制，其中能量限制是最主要的限制[2]。因为网络大多部署在人迹罕至或者环境恶劣的地方，更换单个节点的电池是不可取的，也是不现实的，所以如何使网络的生命周期最大化是要解决的问题[3]。针对这个问题，目前已有一些研究。文献[4]提出一个新算法LEACH-NEW，它考虑节点的能量和位置来获取能量和定位功能。文献[5]是在Leach路由算法基于能耗和应用规模的不足之处，引入“层”的概念，并建立新的簇头选择机制来改进原来的Leach。文献[6]是根据接收和发送作者参考的一种机制，动态地开启或关闭不同的组件，调整传送传感器节点的功率和调制电平，同时保持所需的性能，通过引入动态电源管理(DPM)技术，修改和为一个平均获取马尔可夫决策过程(AR-MDP)建模，最后结合模拟退火算法(SA)、Q学习算法来解决与平均绩效标准的节能优化问题。文献[7]是基于传感器通道节点因素的地理位置，剩余能量和邻居的数目提出一个簇路由算法，并通过管理传感器节点和簇来降低无线传感器网络中的能量消耗，增加无线传感器网络的寿命。文献[8]提出了一种改进的Leach协议(Leach-C)算法，称为基于分区的Leach(pLeach)，首先使用集中式计算将网络划分为最佳数量的扇区，然后选择具有最高能量的节点为每个扇区的头。文献[9]基于能量的限制，设计了一个双簇头的非均匀分簇路由协议来降低能源消耗。文献[10]根据簇头预期的频率评估的理念，提出了改进的LEACH-HEFA(LEACH主管预期频率评估)算法，可以平衡无线传感器网络节点的能量消耗，理顺聚类过程，有效地延长网络的寿命，该算法适用于水情监测系统。文献[11]使用OPNET构造仿真模型和性能进行对比研究，改进后的路由算法I-Leach(改进-Leach)比原来的Leach算法扩展了网络的生命周期，从而降低了整个系统的能耗，提高了网络的可扩展性。

1 Leach算法

Leach算法是由Wendi Rabiner等人提出的以“轮”来实现的低功耗自适应集簇分层型协议。该算法的基本思想是：以循环的方式随机选择簇头节点，从而达到能量均衡以降低网络能源消耗、提高生命周期的目的。在Leach每一轮被分为簇的建立阶段和稳定数据传输阶段，为了节省能源，稳定阶段的持续时间要长于建立阶段。

Leach算法的工作流程如图1所示。

图1 Leach算法工作流程图

在簇建立阶段，传感器节点从0到1随机选择一个数值，并与设定的阈值T(n)相比较，若当前轮中该值小于T(n)，则该节点成为簇头，反之则为非簇头节点。每一轮循环中，若节点已被选为簇头，则T(n)设置为零，来避免此节点再次当选为簇头，阈值T(n)定义为

(1)

在数据稳定传输阶段，节点将采集到的数据发送到簇头，簇头对数据进行融合后再将信息发送到汇聚节点，汇聚节点将数据发送给监控中心来进行数据处理。数据稳定传输阶段持续一定的时间之后，网络将重新进入簇的建立阶段，开始下一轮的簇重建，不断地周期循环。

2 改进的Leach算法gcLeach

与静态分层算法和平面多跳路由协议相比，Leach算法可以将网络的生命周期延长15%，但是簇头选举的过程中Leach算法仍然存在着不足。本文着重在簇头选举上进行改进。

2.1 传感器节点分区算法研究

由于Leach算法是随机的选举簇头，可能使簇头集中分布不合理，从而使能量分布不均衡。本文首先按照网络的大小、节点的传输范围和节点的分布密度把网络分为6个区域，在分区的基础上固定每个区域内的簇头比例，其中区域1由于包括基站位置，设定不需要簇头，区域2固定一个簇头，其他区域的簇头比例按照以下步骤：

2)统计出该区域中的节点数目Qnum。

根据以上步骤计算得到的每个区域的簇首比例为：区域1为0；区域2为0(固定1个簇头)；区域3为0.065574；区域4为0.069 307；区域5为0.081 818；区域6为0.066667，如图2所示。

图2 网络区域划分和簇头比例图

由于采用区域进行处理，最近的两个区域由于离基站较近，因此簇头数目得到严格控制，避免了不合理的簇头分布。

2.2 基于灰色关联度思想的簇头选举算法研究

对网络规划分区后，使网络中的簇头能够分布均匀合理，但是没有考虑到节点与基站的距离以及自身的剩余能量，这样就有可能使剩余能量少或者距离基站距离较远的节点当选为簇头,从而造成网络生命周期减少或者能耗较大。因此，本文又在分区的基础上引入灰色关联度的思想，根据节点剩余能量、通信距离等因素采用灰色关联度分析法推选簇头序列，形成无线网络的层次结构。选举簇头节点时考虑节点剩余能力、通信距离等因素，克服Leach协议中簇头选举的随机性、节点能耗分布不平均等缺点，同时减少网络在不断选举簇头时的能量消耗，延长无线传感器网络的生命周期。

灰色系统理论是由邓聚龙首创的一种系统科学理论，其中的灰色关联度分析[12]是根据各个因素之间发展趋势的相似或相异程度来作为衡量因素之间的关联程度的方法。

1)确定最优指标集F

(2)

式中：jk为第k个指标的最优值。此最优值是在方案中最优的值(若某一指标取大值为好,则取该指标在各个方案中的最大值;若取小值为好, 则取各个方案中的最小值),也可以是评估者普遍认为的最优值。不过在定最优值时,不仅要考虑到先进性,还要考虑到可行性。若最优值标志得过高,则不现实,不能实现,评价的结果也就不可能准确。

选定最优指标集后,构造矩阵

(3)

式中：dn和En分别表示节点到基站的距离和剩余能量的原始数值。

2)指标值的规范化处理

由于指标间通常是有不同的量纲和数量级,所以不能直接进行比较,为了保证结果的可靠性,因此要对原始的数值进行规范化处理。本文采用式(4)将式(3)中的原始数值变换成无量纲的值，Ci是转化后的无量纲值

(4)

这样D→C矩阵为

(5)

3)计算综合评判结果

(6)

(7)

(8)

式中：R为M个被评价对象的综合评价结果向量；W为N个评价指标的权重向量；E为各指标的评价矩阵。

(9)

3 算法仿真与分析

3.1 仿真场景

本文是在MATLAB环境下进行的仿真，仿真实现了Leach算法和改进的gcLeach算法，并对两种算法的性能指标进行了比较。仿真场景的参数设置如表1所示。

表1 场景参数

3.2 仿真结果分析

仿真主要是从网络生存周期和节点的剩余能量两个性能指标进行比较。

图3是Leach算法和改进后的gcLeach算法的生存周期的比较，从图中可以看出，gcLeach算法的性能明显要优于Leach算法，生命周期要比Leach算法延长2.8倍左右。形成这个结果的原因有：

1)划分区域使节点分布均匀，在每一轮中使gcLeach算法选择最佳比例的节点作为簇头。在选举过程中保证了簇头的最佳数目。

2)固定簇头比例后，在簇头选举中，gcLeach算法又选择较高的剩余能量和距离基站较近的节点作为簇头。这保证了簇头节点的能量和传输距离。

图3 网络生存周期比较图

图4 节点剩余总能量比较图

图4所示为Leach算法和gcLeach算法的能量消耗比较图。通过上述的优选簇头选举的机制，同时使网络的能量分布和负载均衡，达到总能量消耗最优化管理。从图中可以看出，gcLeach算法的能量消耗要低于Leach算法。

4 结论

Leach算法是在WSN中应用比较广泛的一种分簇路由算法，本文在Leach算法的基础上，从簇头选举的方法上做了改进，提出了一种改进的gcLeach算法。从仿真结果可以看出，改进后的算法可以显著提高网络的能源利用率，延长网络的生命周期。

[1]HEINZELMANWR，CHANDRAKASANA，BALAKRISHNANH.Energy-efficientcommunicationprotocolforwirelessmicrosensornetworks[C]∥Proc.33rdHawaiiInternationalConferenceonSystemSciences.LosAlamitos：IEEEPress，2000：3005-3014.

[2]WANGH，AGOULMINEN，MAM，etal.Networklifetimeoptimizationinwirelesssensornetworks[J].IEEEJournalonSelectedAreasinCommunication，2010，9(28)：1127-1137.

[3]孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学出版社，2005.

[4]SHUJIANGLD，LIXINKK.Improvementandsimulationofclusteringroutingalgorithminwirelesssensornetwork[C]//Proc.2011 6thIEEEConferenceonIndustrialElectronicsandApplications(ICIEA).Beijing：IEEEPress，2011：1068-1073.

[5]JINKY，ZHANGY，TIANDR.BasedontheimprovementofLEACHprotocolforwirelesssensornetworkroutingalgorithm[C]//Proc.2012SecondInternationalConferenceonIntelligentSystemDesignandEngineeringApplication(ISDEA).Sanya：IEEEPress，2012：1525-1528.

[6]MAOS，TANGH，ZHOUL，etal.AnenergyconservationoptimizationstrategyforwirelesssensornetworknodebasedonQ-learning[C]//Proc.2011 8thAsianControlConference(ASCC).Kaohsiung：IEEEPress，2011：938-943.

[7]BEIRANVANDZ，PATOOGHYA，FAZELIM.I-LEACH:anefficientroutingalgorithmtoimproveperformance&toreduceenergyconsumptioninwirelesssensornetworks[C]//Proc.20135thConferenceonInformationandKnowledgeTechnology(IKT).Shiraz：IEEEPress，2013：13-18.

[8]HAOSONGG，YOUNGHWANY.AnenergybalancingLEACHalgorithmforwirelesssensornetworks[C]//Proc.2010SeventhInternationalConferenceonInformationTechnology:NewGenerations(ITNG).LasVegas：IEEEPress，2010：822-827.

[9]LIUZJ，LILY.BasedonenergybalanceLEACH-DCprotocoldesign[C]//Proc.2011 6thIEEEJointInternationalInformationTechnologyandArtificialIntelligenceConference(ITAIC).Chongqing：IEEEPress，2011:291-294.

[10]LICM，TANGP，WUJY，etal.Analyzingcluster-headselectionmechanismsandimprovingtheLEACH[C]//Proc.2011InternationalConferenceonElectronics，CommunicationsandControl(ICECC).Zhejiang：IEEEPress，2011：747-750.[11]SONGXY.ModelingandsimulationofWSNroutingprotocols[C]//Proc.2011IEEE3rdInternationalConferenceonCommunicationSoftwareandNetworks(ICCSN).Xi'an：IEEEPress，2011：586-590.

[12]ZHAOGS，WANGHQ，WANGJ.Anovelquantitativeanalysismethodfornetworksurvivability[C]//Proc.FirstInternationalMulti-SymposiumsonComputerandComputationalSciences.Hangzhou：IEEEPress，2006：30-33.

[13]ZHANGWY，LIANGZZ，HOUZG，etal.Apowerefficientroutingprotocolforwirelesssensornetwork[C]//Proc.Networking,SensingandControl,IEEEInternationalConference.London：IEEEPress，2007：20-25.

宋倩倩(1987— )，硕士生，主研宽带无线通信技术。

王宏刚(1977— )，讲师，主要研究方向为无线通信、射频识别、无线传感器网络等。

卢光跃(1971— )，硕士生导师，主要研究方向为通信信号处理等。

责任编辑：许 盈

Improved Leach Algorithms Based on Gray Correlation Degree

SONG Qianqian,WANG Honggang,LU Guangyue

(SchoolofCommunicationandInformationEngineering,Xi’anUniversityofPostsandTelecommunication,Xi’an710121,China)

Leach algorithms is one of the most used widely clustering routing protocol in wireless sensor networks, but the cluster head of Leach algorithm is randomly generated, it may lead nodes to premature deaths and then collapse of the entire network.To solve this problem, an improved algorithm is proposed based on Leach--gcLeach algorithm based on optimal cluster head.Improved algorithm for the introduction of gray correlation degree to partition the cluster head election, both considering the remaining energy of the cluster heads and the location of the distribution, effectively, avoid the situation of the irrational distribution of cluster head,as well as the low remaining energy of cluster head leads nodes to premature death.Simulation results show that, improved gcLeach algorithm can effectively reduce energy consumption, and prolong the network lifetime.

wireless sensor networks; Leach algorithm; gray correlation degree; cluster head

【本文献信息】宋倩倩，王宏刚，卢光跃.基于灰色关联度的Leach算法的改进[J].电视技术,2015，39(3).

陕西省科学技术研究发展计划项目(2013KW01-03)

TN929

A

10.16280/j.videoe.2015.03.036

2014-06-10