矿井无线通信网络中LEACH协议的改进

刘云翔++张伟

摘 要： 针对矿井下无线传感器网络通信的特点，对LEACH协议分簇进行优化，并充分考虑能量和距离的因素，对簇头节点的选取进行优化，提出基于K?means++聚类的路由算法LEACH?KPPE，有效地改善了LEACH算法中簇头节点分布不均、能耗不均以及网络的稳定性等问题。仿真实验结果表明，该算法有效地改善了整个网络的能耗，提高了能量的利用率，有效延长了网络的生命周期。

关键词： 矿井； 无线传感网络； LEACH协议； K?means++算法

中图分类号： TN915.04?34 文献标识码： A 文章编号： 1004?373X（2017）09?0066?04

Abstract： According to the features of the wireless sensor network communication for mine， an LEACH protocol clustering is optimized. The factors of energy and distance are taken into full consideration to optimize the selection of cluster head nodes. The routing algorithm LEACH?KPPE based on K?means++ clustering is proposed to solve the problems of uneven cluster head node distribution， unbalanced energy consumption and network stability existing in the LEACH algorithm. The simulation experiment results show that the LEACH?KPPE algorithm improved the energy consumption of the whole network， enhance the energy utilization， and prolong the network life cycle effectively.

Keywords： mine； wireless sensor network； LEACH protocol； K?means++ algorithm

0 引 言

无线传感器网络（Wireless Sensor Network，WSN）是由大量具有数据采集、数据处理以及通信能力的传感器节点以自组织方式形成的一种拓扑动态变化的网络[1?3]。其具有抗毁性强、自适应性强以及能快速展开等优点，因此被广泛应用于工业控制、环境监测、交通控制、医疗护理、军事等重要领域[4?6]。

开采煤炭作业主要是在井下进行，在无线传感器网络还未普及之前，在矿井下基本使用有线通信装置。有线通信存在一定的弊端，发生安全事故时无法精确定位井下事发地点以及人员位置，煤矿地面人员不能及时准确地获取井下具体信息[7]，因此不利于井下工作以及安全管理。通过利用无线传感器网络实现井下通信，无线安全系统能够完善矿井下移动通信系统，并加强了矿井的安全管理。

根据煤矿井下巷道的特性，其网络拓扑结构是带状的，而且通信环境相对恶劣。与一般的无线通信网络相同，其节点工作在一些无人监控的区域，不易维护，自身能量有限且不能再生，所以高效、稳定、节能的路由协议对整个无线传感器网络来说是相当重要的。

LEACH（Low Energy Adaptive Clustering Hierarchy）协议是目前应用较为广泛的层次路由[8?9]，其能适用于一般的工作环境。但是针对矿井下的特殊环境，LEACH协议已经不能满足其要求，因此本文主要对LEACH协议进行研究并改进，提出一种基于K?means++聚類的路由算法LEACH?KPPE，使其能高效、稳定地在矿井环境下正常工作。

1 LEACH协议

1.1 LEACH协议概述

LEACH协议是无线传感器网络中应用较广泛的一种层次路由协议，其工作流程主要分为两个步骤：生成簇和传输数据信息。整个过程会周期性地重复进行，所以可以称其一个周期内的过程为“轮”[10]。每轮中首先从网络中的节点随机选出若干个较合适的节点作为簇头，在选取簇头前，LEACH算法中给出一个预先设定好的阈值此阈值的计算公式为：

式中：是网络中簇头占所有节点比例的期望值；是当前周期循环选取簇头的轮数；为不是簇头节点的集合。

当簇头确定后，这些簇头节点就会向其余节点发送消息，接收到信息的节点同时根据簇头发出的信号强弱来选择加入哪一个簇群。在完成分簇的工作之后，簇内的非簇头节点开始采集所需要的信息，然后将采集到的数据发送给自己所在簇的簇头节点，接收到数据的簇头节点对数据进行处理和整合，最后再将数据发送给基站。

1.2 LEACH协议应用于煤矿井中的不足

对于不同的应用环境而言，LEACH并不是最优的路由协议，所以在煤矿井下这一特殊的环境中，LEACH也存在一些不足，其簇头节点是随机选择的，这样会导致簇头节点分布不均匀，同时剩余能量较少的节点也有可能被选为簇头节点，就会导致簇头节点过早死亡，除此之外煤矿井下的通道一般都很长，针对这一特性，LEACH中单跳通信方式不再适用于煤矿井下通信。

2 LEACH?KPPE协议

针对LEACH应用于煤矿井中的一些缺陷，本文在LEACH的基础上提出一种改进后的LEACH?KPPE协议。LEACH?KPPE与原有的LEACH协议在主要工作流程上是一致的，都是周期性进行轮的重构，每个轮也都包括建立簇和稳定数据传输两个阶段。

2.1 建立簇阶段

在建立簇时，将区域内所有节点的位置以及剩余能量信息先发送给基站，再利用K?means++算法对网络内的节点进行聚类处理。K?means++是在K?means算法基础上提出的一种算法，K?means首先从区域内节点中随机选择个节点作为初始的聚类中心，但不同的聚类中心会出现完全不同的聚类结果，所以分簇结果可能不是最优的。为解决这一问题，本文采用K?means++算法，其主要的工作过程如下：

（1） 先从区域内节点中随机选择一个节点作为第一个聚类中心；

（2） 对于区域内的每一个节点计算其与最近聚类中心（指已经存在的聚类中心）的距离

（3） 选择一个新的节点作为新的聚类中心，其中较大的节点被选为新的聚类中心的几率较大；

（4） 重复执行步骤（2）和步骤（3）直到选出个聚类中心；

（5） 分别计算剩下的节点到个聚类中心的相异度，将这些节点分别划分到与其相异度最低的簇；

（6） 根据聚类结果，通过计算每个簇中所有节点维度的均值来重新更新这个聚类中心；

（7） 重复步骤（5）和步骤（6），直到准则函数开始收敛为止，最后每一个聚类就是一个簇。

其中选取新的聚类中心关键在于第（3）步，为了将与被选为下一个聚类中心的概率相关联，先计算每个节点与其最近的聚类中心的距离并将这些保存到数组中，对这些距离全部求和得到再取一个随机值Random并使这个随机值能落在中，当满足时，此时的节点就是新的聚类中心。建立簇的流程图如图1所示。

完成分簇后还需对簇头节点优化，因为通过K?means++算法得出的簇头节点在位置分布上已经达到全局最优，但此时选出的簇头节点有可能剩余能量较低，这样就会导致此节点过早死亡。由簇内所有节点剩余能量的均值得出一个阈值，如果通过K?means++得出的簇头节点的剩余能量高于此阈值，則此节点作为簇头节点不更换，否则重新选取剩余能量高于所求阈值且离当前簇头节点最近的节点作为新的簇头节点。这样所选出的簇头节点在位置分布以及剩余能量上都达到全局最优，提升了整个网络的能量均衡，延长了整个系统的生命周期。

2.2 数据稳定传输阶段

完成分簇工作后，开始进行数据传输。煤矿井下的通道一般都很长，这样节点就会按着通道路线进行分布，从而生成的簇也会按着通道走向呈纵向排列，导致有些簇头节点离基站很远。如果采用LEACH中单跳方式进行通信，离基站很远的簇头节点向基站传输数据时就会因为消耗大量的能量而过早死亡。因此单一的单跳通信方式不适用于煤矿井下通信，本文在单跳通信的基础上结合多跳方式进行数据传输。在簇内其成员节点与簇头节点之间的距离较近，直接使用单跳方式，当簇头节点离基站较近时也采用单跳方式，如果簇头节点离基站较远，则采用多跳路由传递信息。在采用多跳方式时，从簇头节点中选出离基站最近的节点作为目标节点，离基站较远的节点作为源节点，将其与目标节点之间的簇头节点作为路由中继，将数据发送给目标节点，最后由目标节点将数据直接传给基站。

在源节点与目标节点之间进行多跳通信前，利用Floyd算法找出源节点与目标节点之间的最短路由。通过Floyd算法求最短路由时，需要对其初始化稍作修改，由于源节点与目标节点之间不直接通信，所以一开始将源节点与目标节点的距离初始化为无穷大，这样最终可以由Floyd算法得出从源节点经过若干中间簇头节点之后到达目标节点的最短路由。

3 仿真结果及分析

本文在Matlab平台对LEACH以及LEACH?KPPE协议进行仿真分析，主要通过整个网络分簇结果、能耗以及节点的存活率这三个方面对比LEACH和LEACH?KPPE算法的性能。本文模拟将100个传感器节点分布于100 m×100 m的网络区域中，模拟仿真中参数设置如表1所示。

设定时，LEACH以及LEACH?KPPE算法分簇仿真结果如图2所示，其中节点是随机分布的，不同的标志符号表示不同的簇。图2中的表示每个簇的簇头节点。为了更有可比性，在LEACH仿真中特意将其初始化簇头节点与LEACH?KPPE仿真得出的簇头节点设为一致。对比图2（a）和图2（b）可以看出，由LEACH仿真得出的分簇结果是不均匀的，有的簇中节点分布过密，除此之外还出现了簇头节点分布在簇边缘的问题。相比而言，由LEACH?KPPE仿真得出的分簇结果更加均匀，而且簇头节点大致分布在每个簇的中心区域。

图3为网络总能耗与其工作时间之间的关系变化，工作时间由具体轮数表示。从图3中可以看出，相比LEACH算法，改进后的LEACH?KPPE算法在能耗上有明显的改善。

LEACH算法在600轮左右网络能量已经耗尽，而LEACH?KPPE算法直至1 200轮后才耗尽，整个网络的工作时间相比LEACH延长了一倍多。将网络从开始运行到整个网络能量耗尽定义为网络的生命周期，改进后的LEACH?KPPE算法有效地延长了整个网络的生命周期，所以在能耗性能上LEACH?KPPE算法比LEACH算法表现更好。

图4是网络剩余节点数与其工作时间的关系图，在LEACH仿真中，网络工作100轮后节点开始出现死亡，在600轮之后节点全部死亡；而LEACH?KPPE中第一个死亡节点在520轮之后，并且直到1 250轮之后才没有剩余节点，这表明LEACH?KPPE算法更有效地使网络中的能量均匀分布，从而有效降低了节点因能耗过大而过早死亡的概率。

4 结 论

将无线传感器网络应用于工作环境恶劣的煤矿井下，能够有效提高对煤矿井下工况以及设备信息的监测效率，对加强煤矿井下的安全管理有着重大意义。路由协议对无线传感器网络而言是其关键核心所在，所以本文通过K?means++聚类算法对LEACH协议的分簇方式加以改进，并结合节点能量对簇头选取进行优化，并在一些簇头节点与基站之间采用多跳方式进行通信，提出一种LEACH?KPPE路由协议，使其更适用于煤矿井下的无线通信。仿真结果表明，改进后的协议在分簇结果、能耗以及节点存活率这三个方面相对于LEACH协议都有着显著的提高，从而有效地提高了网络的生命周期和稳定性。

参考文献

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

[2] 王殊，阎毓杰，胡富平，等.无线传感器网络的理论及应用[M].北京：北京航空航天大学出版社，2007.

[3] 张海燕，刘虹.基于K?means聚类的WSN能耗均衡路由算法[J].传感技术学报，2011，24（11）：1639?1643.

[4] 林楠，史苇杭.无线传感器LEACH算法的优化及仿真[J].计算机仿真，2011，28（1）：178?182.

[5] 赵秀兰，许秀兰，李克清.基于LEACH协议的差异化分簇路由算法[J].计算机应用研究，2013，30（3）：866?868.

[6] 单剑锋，庄琴清，陈明.基于簇首概率优化的LEACH协议改进[J].计算机技术与发展，2013，16（2）：104?108.

[7] 王联春.基于GPS技术的井下人员定位系统应用研究[J].煤炭技术，2012，31（10）：203?204.

[8] HEINZELMAN W R， CHANDRAKASAN A， BALAKBISHNAN H. Energy efficient communication protocol for wireless micro?sensor network [C]// Proceedings of the 33rd Hawaii International Conference on System Sciences. Washington， DC.： IEEE， 2000： 3005?3014.

[9] 刘智珺，李腊元，杨少华.基于能耗均衡的LEACH?DC协议的设计[J].计算机工程与设计，2012，33（4）：1337?1341.

[10] HANDY M J， HAASE M， TIMMERMANN D. Low energy adaptive clustering hierarchy with deterministic cluster?head selection [C]// Proceedings of the 4th IEEE Conference on Mobile and Wireless Communications Networks. Stockholm， Sweden： IEEE， 2002： 368?372.

[11] 林海峰，高德民，蒋安娜.基于流量控制的无线传感器网络生命期算法[J].计算机仿真，2016，33（2）：340?344.

[12] 李军.无線传感网络自私节点检测的软件设计与仿真[J].计算机仿真，2016，33（6）：246?249.