一种改进LEACH的无线传感器路由协议仿真

覃琪 谭松鹤

摘  要：文章在研究LEACH协议的基础上，提出了一种改进的层次型路由协议LEACH-Improved，改进的路由协议主要针对原有LEACH路由协议的不足，主要改进在两个方面：一是在簇头节点的选择上依据节点的剩余能量和节点与区域中心的距离，作为主要考虑因素，减少簇头分布的不合理情况，能有效地平衡节点的能量消耗;二是簇头节点采用多跳路由的方式向基站传输数据，也减少了部分簇头节点与基站的远距离的通信。最后通过OMNeT++仿真工具进行仿真实验，实验结果显示该算法相比原有的LEACH路由协议能有效地延长网络生命周期，降低网络能耗，实现网络负载平衡。

关键词：无线传感器网络;LEACH;层次型路由协议;网络生命周期

中图分类号：TP212.9        文献标志码：A         文章编号：2095-2945（2019）08-0011-04

Abstract： Based on the study of LEACH protocol， an improved hierarchical routing protocol， LEACH-Improved， is proposed in this paper. The improved routing protocol mainly aims at the shortcomings of the original LEACH routing protocol. The main improvement is in two aspects： First， according to the residual energy of the node and the distance between the node and the regional center， as the main consideration factor， the unreasonable distribution of the cluster head can be reduced in the selection of the cluster head node， which can effectively balance the energy consumption of the nodes. Second， the cluster head nodes use multi-hop routing to transmit data to the base station， thereby can reduce the long-distance communication between some cluster head nodes and the base station. Finally， the simulation experiments are carried out by OMNeT++ simulation tool. The experimental results show that the algorithm can effectively prolong the network life cycle， reduce network energy consumption and achieve network load balancing， compared with the original LEACH routing protocol.

Keywords： wireless sensor networks （WSN）; LEACH; hierarchical routing protocol; network life cycle

引言

無线传感器网络作为一种新型网络体系，具有移动性、无线布线、多跳路由等多种特点，在远程监测、信息采集以及交通控制等多个领域都有广泛应用[1-2]。无线传感器网络通过传感器节点采集与处理覆盖域内监测到的信息，在军事、消防以及工业领域均有着广泛的应用[3]。在实际网络应用中，传感器节点分布不均，使得某些簇头与距离较远的基站进行通信时，发射功率较大，增加了网络通信能耗，缩短了网络生命周期[4]。在这种情况下，如何有效地进行降低网络通信能耗，成为了该领域亟待解决的主要问题。而低能耗多跳路由协议中的簇头选取策略，通过综合考虑网络候选传感器节点的剩余能量以及自身位置信息等参数优化簇头选取，避免剩余能量较少和位置不佳的传感器节点被推选成簇首，减少能量消耗，是解决上述弊端的有效手段，引起了该领域相关专家学者的高度关注[5]。

1 LEACH路由协议研究

LEACH协议是为无线传感器网络WSN设计的一种低功耗自适应分簇层次型路由协议。LEACH协议算法以一定概率随机选取某个节点担任簇头并与相邻节点动态形成簇，算法使得网络中的节点轮流担任簇头而平均的分摊通信能量消耗，最终达到实现节点能量的负载均衡、延长网络寿命的目标[7]。LEACH协议工作过程是分成很多“轮”（round）进行的，每一轮包含簇建立（setup_up）阶段和稳定运行（steady-state）阶段。

簇建立（setup_up）阶段，每一轮开始都会为每个节点n随机选取一个在0到1之间的实数，成为标记值或者节点的记号。如果n的这个标记值小于一个门限值T（n）的话，节点n就当选为本轮的簇头节点。门限值T（n）通过公式（1）计算得出。各簇头节点广播建簇信号，其他相邻节点选择信号最强的簇头加入形成簇[7]。

P是网络中每轮期望选出的簇头节点所占总节点数目的百分比（根据不同应用场景选值在4%-5%之间）;r为当前的轮数，G是前l/P轮中没有充当过簇头节点的节点的集合[8]，mod符号是求模运算符。通过这样的计算公式，可以保证每个节点会在1/P轮内都充当一次簇头节点，从而实现节点能量的负载均衡。

目前针对LEACH协议的研究很多，MIT学者Heinzelman等人在LEACH协议的基础上又提出了LEACH-C协议，它解决了LEACH协议中“无法确定每轮簇头的数量和位置”以及“根据随机数决定节点是否当选为簇头”等方面的问题，大大提高了簇的生成质量。此外，该算法直接由基站选择簇头，健壮性较好，但由于所有节点都必须向基站周期性地发送它们的位置和能量等信息，成簇开销较大，并且会增加网络流量、信号干扰以及时间延迟的概率。

另有研究者文献[6]提出一种基于节点区域中心的改进算法LEACH_CS，该算法针对簇头选举算法中簇头节点个数偏离最优值范围，导致全网能耗过快，以及簇头位置分布不均匀，造成的簇头节点负载的不均衡问题，通过考虑簇头节点的最优分布区域，使簇头节点尽可能的均匀分布在网络中，形成簇的规模也近似相等，还设定了簇首节点“弃权”机制，以限制簇首个数超出最优值的范围。

2 基于LEACH路由协议的改进算法

本文提出一种基于LEACH路由协议的改进路由协议LEACH-Improved后面简称LEACH-I。改进算法的主要思想是：首先，根据节点的剩余能量作为主要依据选择簇头，并在簇头和基站之间通信引入改进的多跳路由算法，簇内节点和簇头节点之间还是采用直接通信的方式。LEACH-I协议的运行过程类似于LEACH协议分为多“轮”进行，每一轮分为两个阶段，簇建立阶段和簇稳定运行阶段，如图1所示。

2.1 簇建立阶段

Step1每一轮开始时，每个节点先根据自己的剩余能量生成一个定时时间，剩余能量越大的节点生成的定时时间越短。

Step2 定时时间到的节点生成一个随机数Rnd，计算过程见公式（2），即剩余能量越大的节点越容易产生较小的数值，也就越容易当选簇头节点。

其中      为该节点的剩余能量，    为节点的初始能量。

Step3 节点生成的随机数Rnd如果小于文献[6]给出的门限值Tnew（n）则被选为簇头，并向网络中发送广播建簇信息。随机数不小于阀值Tnew（n）的节点返回Step2生成新的随机数，再确定能否当选为簇头节点。

其中，P是一个0-1间的实数，表示网络中每轮成为簇头的节点占所有节点的比例;r表示当前轮数;G表示在前的r-1轮内未充当簇头的节点集合，mod符号表示求模运算符，di表示节点i到分布区域中心的距离，dj表示本轮中参与选举的节点到分布区域中心的距离，n代表参加选举的节点个数，R代表中心圆周的半径。

由公式（2）和（3）可知，优化后簇头节点的选择除了要考虑未选举成功过的节点数目和网络所需要的簇头节点的比例，还要考虑节点到中心圆周的距离和所有未当选簇头的节点到中心圆周的平均距离，以及节点的剩余能量。优化选举产生的簇头节点将大致以中心圆周为基准进行分布，确保了簇头节点之间的通信间距比较短，同时能有效减少簇头节点集中在某一局部区域的最差情况发生。

2.2 簇稳定运行阶段

在簇稳定运行阶段，簇内节点根据簇头分配的TDMA时隙号通过单跳方式向簇头传输数据，簇头节点将收到的数据进行数据融合后采用多跳路由的方式发送给区域外的基站。网络稳定运行一段时间后，在下一个时间周期开始新一轮的簇头选举过程。簇头到基站之間通信的多跳路由算法描述如下：

分簇完成后，簇头节点在区域内广播其自身权重（WEIGHT）消息，该消息包含权值W（由公式（4）计算得出）和节点自己的ID。各簇头节点收到WEIGHT消息后，将自身的权值和消息中包含的权值和进行比较，选择权值较大的节点作为自己的父节点，并发出加入队列的消息，另外在所有簇头节点中选出权值最大的节点作为多跳树的根节点，从而形成了簇头节点间多跳通信的路径。簇头节点沿着多跳树路径将融合计算后的数据传送给父节点，再一级一级传递到根节点，最后由根节点直接和基站通信传递数据。当出现簇类的分布较为稀疏或节点已绝大部分死亡时的情况时，簇头节点不会收到任何WEIGHT消息，则簇头直接与基站通信传递数据。

其中，E为节点剩余能量、Emax为节点初始最大能量、D为节点到基站的距离，Dmax为传感器节点范围内离基站最远的距离。

算法能够确保那些距离基站较近并且剩余能量较多的簇头节点能优先成为多条树的根节点。当出现权值相等的情形时，则根据节点的ID大小来选择父节点，ID大的节点当选为父节点。该算法通过选择最小的MTE路由来减少距离基站较远的节点的能量消耗;同时又能防止距离基站较近的簇头节点因为频繁转发其他簇头节点的数据而导致死亡的情况发生，保证了该算法的能量低耗性，可以有效的延长整个网络的生存周期。

3 实验结果与分析

通过仿真实验验证改进算法的有效性，实验采用OMNet++仿真平台，实验仿真环境是在100m×100m范围内随机布置100个无线传感器节点。鉴于目前针对网络节点寿命的定义尚未形成统一的标准，为了满足不同应用场合的需要，本文将节点寿命评价指标定义为三种形式：第一个节点死亡（FisrtNodeDied）、一半节点死亡（HalfNodeDied）和全部节点死亡（LastNodeDied）。下面从两个方面分别与LEACH协议和LEACH_CS协议进行仿真实验对比。

4 结论

本文在研究LEACH协议的基础上，提出了一种改进的层次型路由协议LEACH-Improved，改进的路由协议主要针对原有LEACH路由协议的不足，最后通过OMNeT++仿真工具进行仿真实验，仿真结果表明，LEACH-I协议在网络生存周期、减少能量消耗两个方面相对于LEACH协议都有明显的提高。

参考文献：

[1]焦克莹，郭强.面向异构WSNs的基于能量感知的簇路由算法[J].传感技术学报，2017，30（9）：1427-1432.

[2]陈志刚，沈小建，刘立.无线mesh网中最小编码代价低时延多播路由[J].通信学报，2016，37（1）：10-16.

[3]肖军弼，刘战军.AntNet算法在AdHoc网络QoS组播路由中的研究[J].计算机系统应用，2014，23（11）：127-131.

[4]周欣欣，余镇危.基于情景感知的移动AdHoc网络自适应路由协议[J].计算机工程与设计，2014，35（11）：3799-3903.

[5]刘迪，等.基于NDN的多层卫星网络分布式动态路由方法[J].电子学报，2017，45（11）：2769-2778.

[6]腾英政.基于LEACH的无线传感网络路由协议研究[D].大连理工大学，2008.

[7]陈晨，杨红丽.无线传感器网络LEACH协议能耗改进[J].计算机系统应用，2017，26（11）：205-212.