基于LEACH协议簇头定位算法研究

丁俊美 ，范生海

(1.合肥财经职业学院 人工智能学院， 安徽 合肥 230601；2.盐城工学院 材料科学与工程学院， 江苏 盐城 224051)

无线传感器网络WSN是一种可以对被感知对象的信息进行发送、采集、处理、融合等系列操作的自组织无线网络［1］。网络中大量传感器节点通常布设在较为恶劣的环境中，许多学者一直在寻求一种既能均衡能耗、又能延长网络寿命的路由算法，其中最早、最为经典的是由Heinzelman等［2］于2000年提出的分簇路由协议LEACH，该协议将网络划分成多个簇，大大降低了网络能耗。2002年，Heinzelman等［3］对此协议进行了改进，提出了LEACH-C协议，其节点可以将自身的坐标信息和剩余能量信息传输给基站，优化了簇头选择，很好地节省了普通节点的能耗；2017年，黄利晓等［4］提出了LEACH-improved节能算法，通过加入间距因子、剩余能量因子和节点密度因子来改进阈值计算公式，再综合考虑节点剩余能量和地理位置选择簇首；2019年，常铁原等［5］提出了OLEACH算法，在成簇过程中加入簇头节点的能量和节点距各簇头的距离等参考量对成簇过程进行优化；2021年，Maheshwari等［6］提出使用蝴蝶优化算法选取最佳簇首，有效地延长了网络的寿命；同年，马泽等［7］提出LEACH-HD算法，通过推导一阶无线能量模型，得到最佳簇首数目，再通过加入节点的剩余能量因子和节点与主机节点的平均距离因子，改进了簇首节点的选择方式。

本文在深入分析LEACH算法及其改进算法的基础上，综合考虑网络簇头边缘化、分布不均的情况，提出一种簇头定位控制的路由算法。

1 LEACH协议剖析

LEACH算法是一个比较经典的单跳分簇协议［8］，该算法使每轮成簇过程中各个传感器节点成为簇头的机会相等，并循环下去。每轮成簇都可分为两个阶段，分别是簇的建立和稳定阶段。

在簇的建立过程中，簇头的选取最为关键。节点成为簇头的条件是第n个传感器节点的随机数T(n)大于该传感器节点自动生成的随机数，此随机数为0～1。当某个节点成为簇头后，需要广播自己成为簇头节点的消息［9］。

T(n)的计算公式如式（1）所示。

式中：T(n)表示第n个传感器节点的随机数；P表示簇头节点占总节点数的百分比；r为当前循环轮数，轮；n表示第n个传感器节点；G表示过去1/P轮中仍未当选簇头的节点集合。

显然，如果簇头数固定，随着r的减小、T(n)的增大，所有节点最后都有机会成为簇头［10］。

LEACH协议仅仅在概率的角度上体现节点成为簇头的公平性，而没有把节点的能耗、边缘化以及簇头密度等作为簇形成的重要影响因素［11］。LEACH协议的不足之处如下：

（1）未将节点剩余能量考虑进LEACH算法。因为节点的类型和距离不同，其能耗也不相同。

（2）LEACH协议簇头选取具有随机性。如果簇头选在网络的边缘，簇头的覆盖面积会变小，传输数据的能耗就会过大［12］。

（3）LEACH协议没有对簇头选取区域进行限制，造成簇头密度不均，大部分簇头与基站间距较远，能量消耗过大。

2 LEACH协议能量模型

LEACH协议采用一阶无线通信模式［13］，如图1所示。该模式中，能量的消耗主要发生在数据接收和发送过程中。

图1 无线通信模型Fig.1 Wireless communication model

当两节点的距离为dm，发送数据总量为lbit时，发送过程与接收过程的能量消耗ETX(l，d)、ERX(l)计算公式分别如式（2）、式（3）所示［14］。

式中：ETX(l，d)表示发送数据lbit到距离为dm的另一个节点需要耗费的总能量，J；Eelec为发送和接收单位数据的能量消耗，为50 nJ/bit，包括电磁数据编码、发送、接收和调制解调等消耗的能量；ETX-mp(l，d)为发送数据信号放大电路的能量消耗，J；εmp、εfs为放大器的增益，均为常数，在一阶无线通信模式中，当d≥d0(d0=时，εmp为多路衰减信道模型下的功率放大系数，为0.0013 pJ/(bit·m4)，当d＜d0时，εfs为自由空间信道模型下的功率放大系数，为10 pJ/(bit·m2)；ERX(l)为接受lbit的数据需要消耗的能量，J。

3 LEACH协议改进

在网络建设的初始阶段，各节点能量相同，随着时间的推移，因传感器类型、节点与簇头距离的不同，导致各节点剩余能量发生较大变化。为尽量不将能量较低的节点选为簇头，导致网络过早死亡。在簇头选取时，要加入能量比例，优先选择剩余能量多的节点成为簇头［15］。改进后的T(n)计算公式如式（4）所示。

式中：Er、Ei分别为节点的当前能量和初始能量，J。

为避免将网络边缘区域节点选为簇头，可以在式（4）中加入节点距离中心基站的面积比例，在满足所有节点覆盖情况下，缩短节点至簇头、簇头至基站的传输距离［16］，使所选的簇头尽量靠近中心基站，簇头节点的覆盖面积尽量最大。

改进后的T(n)计算公式如式（5）所示。

式中：μ为常量，表示节点的能耗比例和面积比例在T(n)中所占的比重；S为节点到中心基站的距离R形成的圆形区域面积，即S=πR2；Smax为最远节点至中心基站的距离Rmax形成的网络面积，Smax=。

除了考虑簇头剩余能量和边缘化之外，簇头的密度对网络影响也比较大。在LEACH协议中，为了防止簇头位置在某区域过于密集，在选取簇头时，可对簇头之间的距离进行限制［17］，使得簇头分布较为均匀。

簇头之间最小距离公式如式（6）所示。

式中：L为簇头间距的最小门限值，m；N为传感器节点总数［18］。

4 模拟仿真及结果分析

4.1 仿真准备

在模拟仿真实验中，将改进后综合考虑了簇头剩余能量、簇头边缘化、簇头密度算法的LEACH协议命名为LEACH-NEW协议，将仅考虑簇头剩余能量、减小簇头边缘化、簇头密度均匀化算法的LEACH协议分别命名为LEACH-EN协议、LEACH-MA协议、LEACH-DE协议。仿真实验前需要确定最优簇头个数K和μ值。对于一定区域内的传感器网络，最优簇头个数K由传感器节点的总个数N和簇头到基站距离共同决定［19］。

优化后的最优簇头数计算公式如下：

式中：K为最优簇头个数；M为监测区域边长，m；dtoBS为簇头到基站的距离，m。

仿真前，确定网络节点布设图如图2所示，仿真参数如表1所示。图2中，黑色正三角形为基站（Sink节点），位于中心点，坐标为（50，50）m；实心正圆为新一轮簇形成后的簇头；空心正圆为普通节点。当簇头位于图2监测区域的中心点时，簇头到基站距离dtoBS最短，为0；当簇头在4个角时，距离dtoBS最大，为71 m，因此，本仿真实验中dtoBS取值为0～71 m。

表1 实验仿真参数Table 1 Experimental simulation parameters

图2 网络节点布设图Fig.2 Layout diagram of network nodes

将dtoBS值及表1中参数代入公式（7），得到最优簇头数K为4～5个，由P=K/N得出簇头节点与总节点数百分比P的最优值为4%～5%。本实验簇头数K选择5个，P取5%。

仿真时需要对各种算法进行性能比较，而μ值对新算法LEACH-NEW的影响较大，因此仿真前必须确定μ值。为此，需要在LEACH-NEW算法下，对网络死亡时间及发送数据量进行综合比较，从而固定μ值。

设网络第一个节点死亡时间为T1，所有节点死亡的时间为Ts，网络存活期内节点给基站发送的总数据量为D，根据表1的仿真参数，经过多轮仿真，得到结果如表2所示。

表2 不同μ值性能参数对比Table 2 Comparison of performance parameters of different μ values

由表2可知，当μ=0.6时，网络第一个节点死亡时间T1约为470 s，网络整体死亡时间Ts约为790 s，数据接收总量为2141 603 B，均优于其它μ值时的网络性能。因此，取μ=0.6，此时T1、Ts、数据传输总量均最大，网络整体性能最佳。

4.2 模拟仿真

根据上面确定的最优簇头数K=5、P=5%、μ=0.6，以及表1的仿真参数，采用MATLAB对以上含LEACH算法的5种算法下Sink节点数据接收量、节点存活时间、能量消耗3个方面进行仿真［20］，结果如图3～图5及表3所示。

表3 网络性能对比表Table 3 Comparison table of network performance

图3 接收数据量仿真结果曲线图Fig.3 Simulation result curve of received data volume

由图3、图4及表3可知，在运行前期，5种协议的数据量基本相同，但LEACH协议的数据接收量约在410 s出现拐点，并首先出现节点死亡，约在690 s节点全部死亡，接收的数据总量为1543 675 B；基于簇头密度均匀化的LEACH-DE协议约在420 s出现节点死亡，约在720 s节点全部死亡，接收的数据总量为1702 541 B；基于减小簇头边缘化的LEACH-MA协议约在440 s出现节点死亡，约在740 s节点全部死亡，接收的数据总量为1877 492 B；基于剩余能量的LEACH-EN协议约在450 s出现节点死亡，约在760 s节点全部死亡，接收的数据总量为1982 474 B；LEACHNEW协议约在470 s出现节点死亡，约在790 s节点全部死亡，接收的数据总量为2141 603 B。因此改进后的LEACH-NEW协议不仅在数据接收总量方面均优于其他4种协议，也有效地延长了网络的整体寿命。

图4 存活节点仿真结果曲线图Fig.4 Simulation result curve of living node

由图5的整个网络能耗与网络存活周期之间关系曲线可以看出，所有协议在前期阶段能量消耗较快，在后期阶段逐渐放缓，主要因为节点死亡速度逐渐加快。LEACH协议网络总能量在690 s左右消耗完毕；LEACH-DE协议在720 s左右总能量消耗结束；LEACH-MA协议在740 s左右总能量消耗结束；LEACH-EN协议在760 s左右总能量消耗结束；LEACH-NEW协议在790 s左右总能量消耗结束，且能耗曲线相对其他协议更加平缓，即LEACH-NEW协议能耗均衡性更好，原因在于LEACH-NEW协议的簇头选取算法比其他协议的有效性更好，在每一轮簇头选取过程都节省了节点的能量，从而降低了网络的总体能耗。

图5 能量消耗仿真结果曲线图Fig.5 Simulation result curve of energy consumption

5 总结

本文在传统LEACH算法基础上进行了改进，综合考虑了无线传感器网络节点的剩余能量、节点到基站中心区域的面积约束条件、簇头节点密度的优化，保证了网络簇头节点覆盖面积最大化和密度均匀化。通过对改进前后的算法进行大量的仿真试验及结果分析，可以看出改进后的LEACH-NEW算法在网络节点存活时间、能量消耗及发送数据总量的优越性，表明该算法是一种有效的分簇算法。