基于LEACH的无线传感器网络混合优化协议算法

摘要：在无线传感器网络（WSN）协议研究中，降低节点的能量损耗、延长节点的使用寿命是研究的关键问题。针对无线传感器网络中传统LEACH协议在分簇机制及数据通信方面的不足，提出了一种混合优化的改进协议——HOBDELEACH。新的协议采用先分簇再选举簇头的策略，提出覆盖半径种子扫描成簇算法（CRSSCA）进行快速分簇，保证对区域的全覆盖；网络运行期间结合能量和距离考虑负载均衡，分阶段采用不同的簇头选举和通信机制。仿真实验结果表明，与LEACH协议相比，HOBDELEACH的第一个节点死亡的轮循次数延长了66%，50%节点死亡时的网络轮循次数延长了20%；与LEACHEI协议相比，所提协议的第一节点死亡的轮循次数延长了50%，50%节点死亡的网络轮循次数延长了19%。改进后的协议能有效地均衡网络负载和簇头节点能量消耗，更合理地分布簇头节点，延长网络生命周期。

关键词：无线传感器网络；路由协议；覆盖半径种子扫描成簇算法；混合优化

中图分类号： TP391； TN915.04

文献标志码：A

Abstract： In the research of Wireless Sensor Network （WSN） protocol， the central topics are reducing the energy consumption of sensor nodes and prolonging the life of the network. Because of the weakness of LowEnergy Adaptive Clustering Hierarchy （LEACH） in clustering mechanism and data communications for WSN， a hybrid optimization protocol， called HOBDELEACH （Hybrid Optimization LEACH Protocol Based on Distance and Energy）， was proposed. In the new protocol， the strategy of dividing all nodes into clusters and then selecting head node in each cluster was adopted. The clustering algorithm of coverage radius and seedscan （CRSSCA） was introduced to fast clustering and guaranteed that the whole area would be covered. During the running of network， considering the load balance together with energy and distance， the different cluster head selections and communication mechanisms were adopted in different stages. The simulation results show that， compared with the LEACH protocol， the round robin of first node death is extended by 66% and the round robin of 50% nodes death is extended by 20% in HOBDELEACH protocol； Compared with the LEACHEI protocol， the round robin of first node death is extended by 50%， the round robin of 50% node death is extended by 19%. The HOBDELEACH protocol can balance the network load and energy consumption of cluster heads effectively， distribute cluster nodes reasonably and prolong the lifetime of networks obviously.

Key words： Wireless Sensor Network （WSN）； routing protocol； clustering algorithm of coverage radius and seedscan； hybrid optimization

0引言

无线传感器网络（Wireless Sensor Network， WSN）中，由于传感器节点可以持续采集监测环境中的数据，数据往往是近似的且数据分布的统计特征是未知的，同时传感器节点体积小、功耗低，数据传输的准确性受带宽、传输延时、能量等因素影响，因此在进行无线传感器网络路由设计过程中，关键技术主要考虑降低节点的能量损耗，延长节点的使用寿命[1]。

随着无线传感器自组网络规模的扩大，分簇路由方案成为WSN路由设计中的主要解决办法之一[2]。在成簇算法中，网络由多个簇组成，每个簇包括簇首和成员两种类型的节点，处于同一簇内的簇首和成员节点共同维护所在簇内的路由信息。簇首节点负责所管辖簇内拓扑信息的压缩和融合处理，并与其他簇首节点交换处理后的拓扑信息，直到传感数据传送至基站。由于分簇路由协议有较大的优势，国内外不少学者对此做了很多研究[3-5]，其中LEACH（LowEnergy Adaptive Clustering Hierarchy）协议具有分层结构，动态选择簇头等优点[6]，在环境监测中应用较为广泛。然而LEACH协议存在一些不足，主要表现在两点：1）无线传感器节点数巨大，采用随机部署方式，造成本簇内节点分布不均而导致簇首节点负载不均衡；2）簇首节点距离基站较远，在与基站进行通信时损耗能量大，从而形成盲节点，会使网络生存时间缩短[7]。针对LEACH协议存在的问题，学者们以减少能量消耗和延长网络生命周期为目标，从考虑覆盖的区域、成簇、能量和距离等方面提出一些改进的LEACH协议[7-14]。比如其中LEACHEI（Energy Initialization Clusterhead Selection）LEACH-EI的英文全称中，缺少LEACH的全称，请问这个LEACHEI的全称是否书写得正确？请作相应调整。协议[10]考虑节点初始能量和节点当前能量，采用动态分簇的思想，重新计算能量阈值，根据能量阈值使得能量较高的节点当选簇头的几率增大，从而有效延长网络生命周期。然而LEACHEI协议当网络运行一段时间后，所有节点的当前能量都变得很低，那么阈值T（n）就会变小，从而降低节点成为簇头的概率，致使每轮当选簇头的数量减少，最终导致网络能量耗费不均衡，网络生命周期缩短。因此，本文从提高节点成为簇头的概率，均衡网络能量耗量的角度延长网络生命周期。

在深入研究无线传感器网络LEACH协议的基础上，本文对LEACH协议的分簇机制及数据通信方面进行了优化，提出一种基于LEACH的混合优化的改进路由协议——HOBDELEACH（Hybrid Optimization LEACH Protocol Based on Distance and Energy）。该协议提出一种先分簇再选举簇头的策略，在网络管理方面采用集中式与分布式相结合的方法，提出覆盖半径种子扫描成簇算法（clustering algorithm of coverage radius and seedscan， CRSSCA）进行快速分簇保证对区域的全覆盖。在局部集中式的簇内结合能量和距离考虑负载均衡改进网络运行机制，分阶段采用不同的簇头选举和通信机制，实现降低节点的能量损耗，延长网络的使用寿命；并通过仿真实验，对算法进行了验证分析。

1传统的LEACH协议

LEACH在协议运行过程中不断地循环执行簇的重构过程。每轮簇的形成先选定簇头节点，通过广播告知整个网络。网络中的其他节点根据接收信息的信号强度决定从属的簇，并通知相应的簇头节点，完成簇的建立。然后簇头节点采用TDMA（Time Division Multiple Address）方式为簇中每个节点分配向其传递数据的时间点，簇内簇成员节点直接与簇头节点通信。簇头节点的选择依据网络中所需要的簇头节点总数和迄今为止每个节点已成为簇头节点的次数来决定，未被当选为簇头节的节点，则将以T（n）的概率当选。

LEACH协议中，簇头的选举机制中通过1/p次循环轮换了所有的节点，在一定程度上均衡了各个节点的能耗。但由于LEACH算法采用随机的方式产生簇头，簇头的选择并没有考虑到在网络中均衡分布，可能导致某些区域簇头节点分布比较密集，而某些区域会相对比较稀疏。而且T（n）的计算公式并没有考虑节点能量因素的不足，会产生当前剩余能量较小的节点承担簇头的工作，这样的簇头节点生存周期短而成为盲节点。同时为减少传送到基站的信息数量，簇头节点负责融合来自簇内不同源节点所产生的数据，并将融合后的数据发送到基站。在选择簇头过程中忽略了节点位置信息，在每一轮选择簇头节点时就不能保证选出的簇头都是最合适的，如果簇头位置处于边缘位置时，与基站节点距离增加，会增大能量的耗损，寿命也很短。盲节点出现的频率大，就会降低网络平均寿命，导致算法效率低下。

2HOBDELEACH网络协议模型

在以往的分簇协议中，重新选举簇头节点是在整个网络内的全局性的动作，即所有节点通过分簇算法来选举出新的簇头节点。这种全局性簇头节点选举方式会带来大量的通信和计算负载，消耗大量的节点能量；在成簇阶段先选择簇头，非簇头节点再按最近原则加入离自己最近的簇头形成簇，选取节点没有考虑对区域的覆盖情况。本文提出一种混合优化的能量有效的快速分簇协议——HOBDELEACH，采用先分簇再选举簇头的策略，分簇时考虑对区域保证全覆盖，成簇后结合能量和距离考虑负载均衡改进网络运行机制。

HOBDELEACH网络运行框架如图1所示。HOBDELEACH在网络管理方面采用了基于集中式与分布式相结合的有效方法。在系统初始化时采用集中式的成簇管理方式快速把网络划分成多个簇，网络中的簇一旦划分形成将不会再改变，变化的只是由簇内哪个成员担当簇头节点，即网络内每个簇节点都是静态的，不再发生变化。在网络分簇管理方面，采用了基于局部集中式的簇头管理策略，重新选举簇头节点变成在簇内的局部性的动作，从而使得网络的整体管理分布到各个簇内的局部管理在簇头与基站进行通信时，采用基于分布式的传输管理策略，考虑到距离的影响，有效地降低簇头节点的能量损耗，从而也增强系统的鲁棒性，提高网络的平均寿命，使得网络的运行不会因为个别节点遭到破坏而整体崩溃。

HOBDELEACH在网络运行阶段，把网络的运行分为稳定和轮循两个阶段。在稳定阶段，系统初始化时把部署区域节点快速分成多个簇，采用基于局部的簇头选择方法，在各个簇内根据节点间发送简短报文，确定在簇内与其他节点通信消耗能量最少的节点充当簇头节点，以保证在簇内通信时，簇头节点消耗相对较少的能量，即簇头节点的选举保证是局部最优的。当网络传输的次数大于一个给定的阈值α时，网络运行进入轮循阶段，为了均衡簇内各个节点的能量，采用簇头选举和网络传输轮循更换的方式运行。在簇头与基站进行通信时，考虑到簇头节点与基站的距离，从而决定是应用单跳传送策略，还是应用簇头间多跳传送策略，有效地降低因远距离传输使簇头节点的能量损耗大的问题。HOBDELEACH网络运行的状态机模型如图2所示。模型中n代表网络运行的轮循次数；InitialNum代表网络中初始节点的数目；num（i）代表第i轮时，网络中存活节点的数目，当网络中存活节点的数目小于初始节点数的30%时，则认为网络失效；α代表网络运行阶段划分的一个固定阈值。

5结语

本文提出一种基于LEACH的混合优化的改进路由协议——HOBDELEACH，从分簇机制及数据通信两方面对LEACH协议进行了优化。协议在网络管理方面采用集中式与分布式相结合的方法，给出覆盖半径种子扫描成簇算法进行快速分簇，保证对区域的全覆盖。网络运行机制结合能量和距离考虑负载均衡，合理地将整个网络的运行分为稳定和轮循两个阶段，对这两个阶段的簇头选举和通信机制采用不同的运行策略。在簇头与基站进行通信时，采用了基于分布式的传输管理策略，同时考虑了距离的影响。通过与相关算法的比较分析实验表明，HOBDELEACH减少了网络总能耗，增强了网络的鲁棒性，延长了网络生命期。当节点的初始能量比较大的时候，网络的效率将会有更加显著的提高。在此基础上，今后将通过实践进一步研究无线传感网络的广泛应用。

参考文献：

[1]YU H， ZENG P， LIANG W. Intelligent wireless sensor networks [M]. Beijing： Science Press， 2006.（于海斌，曾鹏，梁.智能无线传感器网络系统[M].北京：科学出版社，2006.）

[2]YU H， ZENG P， WANG Z， et al. Study of communication protocol of distributed sensor network [J]. Journal on Communications， 2004， 25（10）： 102-110.（于海斌，曾鹏，王忠锋，等.分布式无线传感器网络通信协议研究[J].通信学报，2004，25（10）：102-110.）

[3]HEINZELMAN W. Applicationspecific protocol architectures for wireless networks [D]. Boston： Massachusetts Institute of Technology， 2000.

[4]WU C， XU B， YE Y. Routing method research based on energy intensity and clustering [J]. Control Engineering of China， 2012， 19（4）： 566-570.（邬春学，许博威，叶胤鹏.基于能量强度的簇区分路由方法研究[J].控制工程，2012，19（4）：566-570.）

[5]CHEN Z， LUO P， YUE W， et al. An energyaware topology control algorithm for wireless sensor networks [J]. Chinese Journal of Sensors and Actuators， 2013， 26（3）： 382-387.（陈志，骆平，岳文静.一种能量感知的无线传感网拓扑控制算法[J].传感技术学报，2013，26（3）：382-387.）

[6]HEINZELMAN W， CHANDRAKASAN A， BALAKRISHNAN H. Energyefficient communication protocol for wireless microsensor networks [C]// Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Washington， DC： IEEE Computer Society， 2000： 3005-3014.

[7]LU Y， CHEN Y， CHEN M. The improvement and simulation research of wireless sensor network LEACH protocol [J]. Journal of Anhui University of Engineering， 2012， 27（4）： 42-45.（鲁玉定，陈跃东，陈孟元.无线传感器网络LEACH协议改进与仿真研究[J].安徽工程大学学报，2012，27（4）：42-44.）

[8]GARGARI E A， HASHEMZADEH F， RAJABIOUN R. Colonial competitive algorithm a novel approach for PID controller design in MIMO distillation column process [J]. International Journal of Intelligent Computing and Cybernetics， 2008， 1（3）： 337-355.

[9]HUANG H， YAO D， SHEN J， et al. A multiweight based clustering algorithm for wireless sensor networks [J]. Journal of Electronics and Information Technology， 2008， 30（6）： 1489-1492.（黄河清，姚道远，沈杰，等.一种基于多权值优化的无线传感网分簇算法的研究[J].电子与信息学报，2008，30（6）：1489-1492.）

[10]BAI F， WANG L， MA Y， et al. Algorithm analysis of routing protocolsLEACH for wireless sensor networks [J]. Journal of Taiyuan University of Technology， 2009， 40（4）： 248-252.（白凤娥，王莉莉，马艳艳，等.无线传感器网络路由协议LEACH的算法分析[J].太原理工大学学报，2009，40（4），248-252.）

[11]WU H. An improved energy and distance LEACH clustering algorithm in wireless sensor network [J]. Chinese Test， 2012， 38（5）： 62-66.（邬厚民.无线传感网络中能量和距离改良的LEACH分簇算法[J].中国测试，2012，38（5）：62-66.）

[12]FAN Z， JIN Z， XIE D. Energyefficient clustering algorithm for wireless sensor networks [J]. Journal of Chinese Computer Systems， 2013， 34（3）： 535-539.（樊志平，金政哲，谢冬青.基于能量效率的无线传感网络分簇算法[J].小型微型计算机系统，2013，34（3）：535-539.）

[13]LI J， CAO B， WANG L， et al. An improved cluster routing algorithm for wireless sensor network [J]. Journal of Hunan University of Arts and Science： Natural Science， 2012， 24（2）： 51-55.（李建奇，曹斌芳，王立，等.一种基于LEACH的无线传感器网络改进路由算法[J].湖南文理学院学报：自然科学版，2012，24（2）：51-55.）

[14]IQBAL A， AKBAR M. Advanced LEACH： a static clustering based heteroneous routing protocol for WSNs [J]. Journal of Basic and Applied Scientific Research， 2013， 3（5）： 864-872.