孔国利　苏玉

摘 要： 无线传感网络中低功耗自适应聚类分簇（LEACH）路由算法等概率选取簇首节点，容易导致整个网络节点能量损耗出现极端化，减少网络生存时间。为此，提出一种针对簇首节点选取和分簇的改进LEACH算法。该算法把整个网络区域分为四个扇形区域，在每个区域内独立进行分簇路由；然后基站根据节点剩余能量和与基站的距离进行簇首节点选择，节点根据簇首节点和基站接收信号强度选择路由方式，以均衡网络能量消耗。仿真结果表明，改进LEACH算法的网络寿命是原有LEACH算法的150%，数据吞吐量提升了3倍。

关键词： 无线传感器网络； 能量均衡； 扇形分簇； 簇首； 路由算法

中图分类号： TN915?34； TP393.2 文献标识码： A 文章编号： 1004?373X（2017）05?0014?05

Abstract： The low energy adaptive clustering hierarchy （LEACH） routing algorithm for wireless sensor network selects the cluster head node by means of equal probability， which is easy to result in the extreme energy loss of the whole network nodes， and reduce the network lifetime. Therefore， an improved LEACH algorithm for the selection and clustering of the cluster head node is proposed. The whole network area is divided into four fan?shaped subareas with the algorithm to perform the clustering routing in each subarea independently. The cluster head node of the base station is selected according to the node residual energy and distance to the base station. The routing mode of the node is selected according to the cluster head node and the received signal strength of the base station to balance the network energy consumption. The simulation results show that the network lifetime of the improved LEACH algorithm is 150% of the original LEACH algorithm， and its data throughout is increased by three times.

Keywords： wireless sensor network； energy balance； fan?shaped clustering； cluster head； routing algorithm

0 引 言

无线传感网络是由分布式部署的微型传感器节点组成的自组织网络，其节点数量巨大，部署区域和环境复杂，被广泛应用于实时车辆监控、智能家居、森林防火防灾等方面。其中，传感器节点体积微小，配置的电池能量、计算能力和存储能力有限，因此，如何均衡网络能耗，提升网络生存时间是合理有效设计无线传感网络的重要课题[1?2]。一般来说，无线传感器网络的路由算法应该具有能量优先，基于局部的拓扑结构，以数据为中心的特点。现在国内外已经提出了很多经典的无线传感器网络路由算法，有以数据中心为主的[3]，有以数据传输质量为主的[4]，有以节点地理位置信息为主的[5]等，其中以网络构成的结构划分的，分为平面路由算法和分层路由算法。分层路由最经典的算法为LEACH（Low Energy Adaptive Clustering Hierarchy）算法。LEACH算法在數据汇聚、拓扑适应和能量效率方面具有明显的优势。

现有大量文献对LEACH算法进行改进，以提升其性能。文献[5]提出并对比了三种通过把节点自身的位置坐标和当前能量状况汇报给基站，基站根据这些因素选取簇首的方法，但对于地理位置的获取会消耗很大能量，同时没有考虑到链首个数占整体节点总数的比例，导致不均衡。文献[6]提出了簇首多跳算法，使得簇首之间形成一个多跳的最优路径，减少簇首的能量消耗，但是延长了路径，从而使数据传输过程加长，时效性变弱。文献[7]提出引入簇成员数门限和合并极小簇的方法，首先估计簇首能量消耗的情况，然后人为的控制节点休眠的状况来配合簇首消息的传送，虽然能量消耗方面得到改善，但是在时效性方面没有充分考虑。文献[8]考虑节点剩余能量和通信半径，选择簇首节点以减少整个传感网络中簇首节点的数目，延长网络整体寿命。

本文考虑到能量消耗均衡性，网络寿命长短因素，提出基于扇形分簇的路由算法，缩小分簇范围进行通信。然后，根据剩余能量、通信距离选取簇首节点，均衡能量消耗，延长网络寿命。

1 系统模型

LEACH示意图如图1所示，假定其覆盖一定区域的无线传感网络，并且有以下假设[9]：

假设1：基站与整个网络的位置保持不变，基站与整个网络中的节点距离较远。

假设2：每个节点有着同样性质、有限的能量、与基站直接通信的特性。

假设3：节点计算能力较强，支持TDMA。

假设4：WSN节点发送信息的功率可以变化、调整。

节点间的数据通信采用一阶无线电模型（First Order Radio Model），通信模型如图2所示。

这种通信模式有比较成熟的能量消耗计算体系。该模型假设WSN节点有着相同的计算能力，有限的能量；电信号在不同方向上的路径损耗一样。当传输长为m bit的信息经过距离[d]的过程中，节点的能量消耗如下：

数据发送：

[ETx（m，d）=Eelec?m+εfs?m?d2， d

数据接收：

[ERx=Eelec] （2）

数据融合：

[EGx=Eg?m] （3）

式中：[εfs]是信号放大器的放大倍数；[Eelec]是发送和接收信息时对应的数据处理模块消耗的能量。由于传感器节点间距离不同，传播环境迥异，因此，传播相同数据量的能量消耗不同。式（1）中不同的能量消耗表征不同传播距离和传播环境对能量消耗的影响。其中，[d]是数据通信的距离；[d0]是节点的通信半径；[εmp]是信道传输能量衰减系数，通信传输距离越短，能量消耗越少。

2 LEACH算法流程

LEACH算法将传感器节点分为若干个簇，每个簇内节点的信息汇聚至簇首节点后，由簇首节点转发至基站。汇聚转发的工作方式能够提升LEACH算法的能量效率。此外，由于簇首节点的能量消耗较大，各个节点根据剩余能量状况轮流担任簇首节点，提升网络整体寿命[10]。

LEACH算法以循环也就是“轮（round）”的方式执行簇的构造过程。每轮都由两阶段组成：初始化簇的建立阶段和数据传输阶段，具体时序示意图如图3所示。

2.1 初始化簇阶段

初始化簇阶段分为簇首选取和成簇过程两个步骤。

Step1：簇首选取。网络中所有的节点会随机产生一个在0～1之间的数，网络会设定一个门限值[T（n）]如式（4）所示，基站会把节点产生的随机数与设定的门限[T（n）]进行比较，会选择小于[T（n）]的节点作为簇首。

[T（n）=Q1-Q?（lmod1Q） ， n∈G0， otherwise] （4）

式中：[Q]为每轮簇首节点与[n]个节点的比率；[l]为第[l]轮；[G]为在之前的几轮中没有被选为簇首节点的总和。

Step2：成簇过程。节点被选为簇首后会向其他所有节点广播自己被选为簇首的消息。其他节点在接收到消息之后，根据最小能量的原则通过比较，判断发送这些消息的节点的功率大小来选择加入到相应的簇。一般节点会选择接收到的功率越大的簇首节点形成的簇；然后发送自己要加入相应簇的消息给相应的簇首节点。簇首节点收到消息后会给节点一个回应，并将该节点加入自己的路由表中。

2.2 数据发送和接收

当所有传感器节点都形成簇之后，节点间采用TDMA方式发送数据。各个节点的数据在簇头节点处融合，然后由簇头节点转发给基站。一个簇分配方案维持数据通信一段时间后，重新进行下一轮的簇分配，以避免对簇首节点的能量过度消耗，提升网络整体寿命。

3 改进LEACH算法原理

从LEACH算法中可知，以轮的方式等概率的选取簇首，并没有考虑剩余能量的因素。对于剩余能量不同的节点当选簇首的几率是一样的。如果剩余能量偏低的节点被选为簇首，很容易耗尽能量，降低整个网络的寿命。此外，在LEACH算法中，节点根据接收信号的强度来选择簇首。若该节点距离簇首节点较远，路径损耗较高[11]，因此，节点能量会过早消耗而死亡，导致网络的通信出现黑洞。

针对这些缺点，综合考虑节点的能量和整个网络信息传输的及时性，本文在基于LEACH算法的基础上提出了改进LEACH算法。该算法把整个网络划分为四个扇形分区；基站在每个扇形分区中通过比较每个节点产生的随机数和节点的剩余能量选择簇首，接着基站公布簇首的消息，节点根据接收到的该区域的消息强度、与簇首和基站的距离比较选择加入簇还是选择直接与基站进行通信。

3.1 扇形结构模型

由于覆盖区域为圆形时，传感器节点间的最大距离比覆盖區域为其他形状时要小，本文假定圆形覆盖区域，基站位于圆形覆盖区域中心。同时，为了进一步缩小节点间的最大距离，同时减少由于网络中节点死亡而重新分簇带来的通信开销，改进LEACH算法将圆形覆盖区域分为4个扇区，如图4所示。在每个扇区内，分别进行LEACH算法路由。选定某个参考点后，4个扇区分别记为扇区编号num={1，2，3，4}，圆心角[θ=π2。]

3.2 扇区编号确定

划分好区域后，所有传感器节点进行分簇时需要确定每个节点所在的扇区编号及在扇区的具体位置，方法如下：

（1） 计算节点的极坐标角度。所有的节点需要将自己的位置信息与ID信息发送给基站，基站根据正切函数特征进行计算。把圆放到直角坐标系中，圆心[O]的坐标为（0，0），设任意一个点[i]的坐标为[（x（i），y（i）），]如图5所示。

（2） 确定节点所在区域。将节点[i]对应的角度[α]与圆心角[θ]相除，得到整数[k（i），]比较[k（i）]与已经划分好区域的编号[num（n），]获得节点[i]所在的区域编号[k（i），]即：

所有节点的极坐标角度和扇区编号构成一个矩阵，记为Loc，其中，[Loc=（i）={a（i），k（i）}。]

3.3 簇首选取

改进LEACH算法同时考虑通信距离和节点剩余能量来选择簇首节点，并且在每一轮都会进行选取，流程图如图6所示。

簇首节点选择过程分为两步：

Step1：先按照LEACH算法机制，比较每个节点产生的随机数与网络给定的阈值[T（n），]在低于阈值的节点中选择簇首节点。

Step2：在第一步选择的节点中，综合考虑节点的能量和与基站的距离，进行簇首节点选择。具体选择的准则为：

[Q=Edis] （9）

式中：[E]为节点的剩余能量；dis为节点与基站之间的距离。由式（1）可以看出，距离dis也与[Q]成反比，距离基站越远的节点消耗的能量更大，因此该点被选为簇头的几率也比较小。

综上所述，剩余能量越多，离基站距离越近的节点成为最终簇首节点的概率越大。

3.4 分簇通信过程

当簇首节点选定以后，基站会向各个扇区广播相应区域簇首节点的消息。各个扇区内对应的节点知道自己为簇首后，就会在自己的覆盖区域内发布自己是簇首的消息。各个扇区的普通节点会根据自己接收到的来自簇首的信息和接收到来自基站的信息强度和相应的距离判断是选择加入簇还是直接与基站进行通信。当选择加入簇后，会给相应的簇首发送消息，同时簇首也会相应的给回应。对于不加入簇中的节点，就只会把测量的消息直接发送给基站，流程图如图7所示。

在每轮传输数据时，各个区域簇内的节点会把测量到的信息数据发送到相应的簇首，簇首节点传送到基站，而簇外的节点会把消息直接传输给基站。当节点为普通节点或者是簇外节点时，能量消耗只包括节点将数据发送的能量；当节点为簇首节点时，能量消耗为节点接收、融合以及发送数据的能量总和。

4 仿真结果分析

为了评估改进LEACH算法的性能，使用Matlab进行仿真，重点分析经过一定轮数网络节点的死亡个数和网络传输数据的情况[12]。假定基站固定且位于监测区域的最中心，远离传感器节点；所有的节点计算能力和能量容量一样；节点具有与其他节点和基站进行通信的能力；节点的位置固定不动。同时对比了原有的两种改进算法LEACH1，LEACH2。其中，LEACH1是由文献[13]提出的只针对簇首选取改进的算法，采用粒子群算法进行分区，分别在各个区域通过节点剩余能量选取簇首的方法。LEACH2是文献[14]提出的结合LEACH与PEGASIS的改进算法，通过对节点分区分簇，把不同簇的簇首连成链进行通信的方法。

仿真中假定基站坐标为（0，0），数据包的长度为3 000 b，控制包的长度较小，可以忽略不计，其他的实验参数设置如表1所示。

首先对两种原有算法和LEACH算法在不同轮数死亡节点总数的统计进行比较，具体显示结果如图8所示。

从图8可以看出，当运行到500轮左右时，四种算法都出现了节点开始死亡的现象。LEACH和LEACH2算法的节点死亡速度比较快。经过1 500轮左右，使用这两种算法的无线传感网络节点死亡率达到最大限度。到将近2 000轮左右时，两种算法的节点死亡速度接近平缓，并将近全部死亡。这是由于这两种算法没有考虑节点剩余能量的影响，导致部分节点过早死亡。而改进LEACH算法和LEACH1算法的节点死亡状况在一开始比较平缓，到1 300轮左右时速度变快，但都没有LEACH快，并且在LEACH接近死亡时，改进算法中还存活将近20个节点。可以看出，改进算法比原有算法更好地延长了网络寿命，并且比LEACH算法在节点存活概率方面提升了20%，节约了能量的消耗，延长了网络的生命周期。

几种算法数据传输性能的比较如图9所示。

由图9可知，随着轮数的增大，四种算法数据传输的量都在增加，并且改进LEACH算法与原有算法的数据传输差距也随之增大，当到1 000轮左右时，改进算法的数据传输量是LEACH算法的3倍。LEACH算法和改进算法LEACH2在1 500轮左右时，数据传输量的增加趋于稳定，而改进算法和另外一种算法LEACH1的数据传输量一直在快速增加，当到2 000轮左右时，LEACH和LEACH2算法已经达到了最大数据传输量，而改进算法的数据传输量还在增加，并且将要达到LEACH算法的4倍，明显提高了数据传输效率。因此，本文提出的改进算法通过合理使用节点能量，能够提高网络有效数据的传输量。

5 结 语

本文综合考虑了扇形分区和节点剩余能量，对LEACH算法进行改进。仿真结果表明，改进LEACH算法能够提升约150%的网络寿命，同时能够传输4倍于对比算法的数据量；该算法在均衡了能量消耗的同时还增强了网络接收数据信息的及时性，提高了网络的利用率，增加了网络生存时间。

参考文献

[1] 苏俭华，刘宇红，徐跃州.一种基于LEACH的无线传感器网络路由算法及仿真[J].通信技術，2014，47（1）：60?63.

[2] MAMUN Q. A qualitative comparison of different logical topologies for wireless sensor networks [J]. Sensors， 2012， 12（11）： 14887?14913.

[3] 任克强，余建华，谢斌.基于改进LEACH的多簇头分簇路由算法[J].电视技术，2015，39（13）：69?71.

[4] MCBRIDE D， CROFT T N， CROSS M， et al. Optimization of a CFD： heap leach model and sensitivity analysis of process operation [J]. Minerals engineering， 2014， 63（8）： 57?64.

[5] 周萌，陈跃东，陈孟元.能耗最优的LEACH协议改进[J].计算机工程与应用，2014，50（23）：82?86.

[6] GOETZ E R， RIEFLER R G. Performance of steel slag leach beds in acid mine drainage treatment [J]. Chemical engineering journal， 2014， 240（6）： 579?588.

[7] 陈晓娟，王卓，吴洁.一种基于LEACH的改进WSN路由算法[J].传感技术学报，2013，26（1）：116?121.

[8] HU Songhua， HAN Jianghong， WEI Xing， et al. A multi?hop heterogeneous cluster?based optimization algorithm for wireless sensor networks [J]. Wireless networks， 2015， 21（1）： 57?65.

[9] 王梦莹，王鑫，蒋华.基于簇首成链的低能耗层次路由协议[J].计算机科学，2015，42（11）：144?148.

[10] 蒋畅江，石为人，唐贤伦，等.能量均衡的无线传感器网络非均匀分簇路由协议[J].软件学报，2012，23（5）：1222?1232.

[11] 吉正洵，江冰，李丽芳，等.采用改进算法对无线网络节能优化仿真研究[J].计算机仿真，2015，32（6）：266?270.

[12] 张岩.非变换簇的WSN分簇路由算法[J].现代电子技术，2015，38（18）：26?29.

[13] YANG Y， WANG X， WANG M， et al. Recovery of iron from red mud by selective leach with oxalic acid [J]. Hydrometallurgy， 2015， 157： 239?245.

[14] 王鑫，王梦莹，蒋华.一种基于簇首成链的分层分簇路由协议[J].微电子学与计算机，2014（10）：9?12.