基于双簇头及数据融合的改进LEACH算法的网络拓扑控制研究

宋锦波 徐海芹 宫晓慧 刘洋

摘要：针对LEACH算法固有的能量损耗问题，对其数据融合率以及簇头的选举进行重新规划。在数据融合阶段，采用模糊理论定义各节点的信任度，实现最优形式进行数据融合。利用最优簇头率求解最佳簇头数目，引入主副簇头概念，有效保证了数据安全性，且以特有双簇头轮换模式减少了能量的损耗。研究结果表明，该算法可以有效减少簇头竞选次数，避免不必要能量损耗，延长网络生存周期。

关键词：数据融合率;最优簇头数;双簇头;网络生存周期

中图分类号：TP393

文献标志码：A

文章编号：1006-1037（2021）03-0022-06

随着无线传感器网络的不断发展，应用范围也随之不断地扩大，现已被广泛的应用在数据采集、军事侦察、环境检测等方面，网络内的节点可以感知周围环境[1]，对数据进行接收、处理和转发。在无线传感器网络中，从路由结构要素出发可以分为平面路由协议和分簇路由协议[2-3]。前者设计较为简单，适用于小型网络环境中;后者的健壮性较好，扩展性佳，相对于平面路由协议有着较为明显的优势。LEACH协议作为一种比较经典的分簇路由协议，基于传统分簇协议，将感知到的数据发送到无线传感器网络（Wireless Sensor Network，后简称WSN）选取的簇头（Cluster Header，后简称CH）上，簇头节点将接收到的数据转发送至基站处，数据的接收与转发是一个消耗能量的过程[4]，而数据的接收与转发又分为簇内集群信息的传递以及簇间信息的传递[5]，传输的数据量在能量损耗中占了一定的比重。LEACH不仅在选取簇头时具有很大的随机性，在冗余数据上也没有做过多的处理，但网络的生存周期与分簇的结果和数据量的发送息息相关，为了优化能量消耗并延长网络的周期[6]，现对网络的簇头的选取进行重新规划，首先计算出当前网络环境的最优簇头数目[7-9]并对此进行合理划分区域[10]，同时引入双簇头概念[11]，簇头的选举会考虑通信代价[12]，对于数据传输中的冗余数据计算出最优融合率[13]，以达到有效地延长网络的生命周期[14]。

1 LEACH算法介绍

LEACH（Low Energy Adaptive Clustering Hierarchy）算法是Heinzelman提出的一种低能耗自适应聚簇分层型协议算法，是一种以轮的形式进行迭代的算法，每个轮分为初始化和稳定通信两个阶段。初始化时每一轮会随机选举簇头，给予每个节点一个随机值，并与阈值T（n）进行比较。当小于阈值T（n）时，则当前节点被选举成为簇头节点;稳定通信时，节点向簇头传送数据，簇头接收簇内节点数据并转发到基站。

1.1 LEACH算法的簇头选举阶段和簇的形成

LEACH算法在每一轮都会重新构建簇的集群，首先网络内的各节点会随机生成一个[0，1]之间的数值rand，然后将这个节点的rand值与T（n）比较，当前节点rand值小于当前的阈值時，则该节点被标记成为该轮次的簇头节点，否则该节点为普通节点。T（n）的计算公式

其中，p是簇头在网络中的节点所占的比例，r是当前选举的轮数，n是网络的节点数，S是r轮后还未当选过簇头的节点的集合。

当每一轮选举出簇头后，簇头节点会发布广播信息告知自己可达跳数范围内的节点自己当选簇头的信息，节点会根据各自接收到的节点的信息强度进行判断自己属于哪个簇头节点构建的集群（就近原则），然后簇内节点会发送自己的节点id和位置信息到簇头处，簇头构建簇群内节点信息表进行保存，同时簇头按照时分复用（Time Division Multiple Access，后简称TDMA）为每一个节点划分时隙用以发送数据或停止工作进入睡眠状态，簇内节点会根据TDMA原则采集数据和发送数据到簇头处，同时在自己的休眠时间点不再工作，进入睡眠状态后直到下一次被唤醒。当簇内节点信息发送完毕后，簇头将接受该数据并与其自身的数据进行一定的融合，融合后的数据将被发送至基站处，基站会接收所有簇头节点的信息然后统一将节点信息发送到用户处，如此反复进行，每一轮都需要重新选举簇头节点。

1.2 LEACH算法的能量消耗

LEACH的能量损耗主要在于节点发送数据和接收数据两方面，其中普通节点发送数据和接收数据的能量损耗为

其中，Eelec为无线电接收和发送单位比特数据的能耗系数，参数εfs和εmp代表的是自由空间模型的能耗系数和多径衰落能耗中的系数，d0= εfs/εmp，d0决定了LEACH使用什么样的模型，d是目标节点到源节点的距离，当节点距离小于等于d0时，传输模型采用自由空间模型，反之则使用多径衰落模型。

节点接收L位数据的能量损耗为

2 TLE-LEACH算法

针对传统LEACH算法的不足，本文提出基于融合率和计算簇头节点最低能耗的改进TLE-LEACH（The Least Energy- Low Energy Adaptive Clustering Hierarchy）算法。引入数据融合率，首先利用信任度函数计算综合信任度，搭建信任矩阵，在簇头处对传感器节点所测得数据进行一定的融合，发送给基站;再根据能量损耗最低的原则进行簇头选取，分别计算簇内各节点和簇头节点所需的能量损耗，考虑节点的信任度，计算求得最佳簇头C1和C2，C2作为备选簇头，当C1的能量低于簇内节点的平均能量时，备选簇头C2则代替C1进行数据传输，二者不断轮换当选簇头，直到C1、C2能量均低于簇内平均能量时，簇内开始重新选举簇头。当网络内70%节点死亡后，节点采用单步传输数据到基站，直到90%节点死亡，网络瘫痪。

2.1 簇的形成阶段

在节点比较密集的地方，不可避免地会出现节点收集到的信息是重复的，传输这些数据对于簇头的能量损耗是比较大的，所以需要在簇头节点处对冗余数据进行一定的融合，引入数据融合率的概念，以减少数据的冗余。

由文献[15]可知，数据融合率算方法如下：初始化网络迭代的轮数，节点需要计算集群内各节点对于自己的信任度并采用模糊理论对数据之间的接近程度进行处理，利用其构建信任矩阵w，计算数据融合率并利用矩阵存储相应的信息。

信任度函数构建如下：N个传感器节点对于同一数据进行监测，Xi和Xj为第i个节点和第j个节点测得的数据，且都服从高斯分布，pi（x） 和pj（x）是传感器的特性函数，Xi和Xj的一次观测值用xi，xj表示，二者之间的偏差用置信距离测度反映。

2.2 最优簇头数的计算

在一个网络中，节点当选簇头后需要承担发送数据到基站并接收节点信息的任务，同时告知节点自己成为簇头信息等。但这些过程都需要消耗能量，簇头数目过多时，簇头节点与基站直接进行信息传输，会增加网络节点的能耗，簇头数目较少时，会加大簇头的能量损耗，加重簇头负担，以至于簇头过快死亡影响整个网络的运行[8]。当选举出来的簇头节点的位置距离基站较远时，簇头到基站的数据传输压力就会加大，严重影响了簇头的存活性，因而簇头数目的多少和分布关乎到整个网络的生存周期。

由此可见网络的区域划分即簇头的数目对于网络整体生存周期的延长十分重要，而原有的LEACH算法生成的簇头数具有随机性，对于传感器节点赋予的随机数的大小依赖十分巨大，在LEACH初步分区的基础上根据当前能量的损耗计算出当前网络中的最佳簇头数k并根据簇头的数目进行区域的划分。

假设此时网络中的节点数为N，簇头节点的能量损耗主要在于接收节点的数据所造成的能量损耗ERN，转发数据到基站所造成的能量损耗EHB以及对节点传送过来的数据进行融合所造成的能量损耗EDA。簇头节点接收集群内节点的数据造成的能量损耗为[19]

其中，Nalive指的是当前网络中的节点存活数量，根据kopt对网络内的节点进行区域的划分，令kopt=k，分区完成后会根据每一轮的节点存活数目重新计算出最优的簇头数并以此重新进行区域划分，传统的区域划分是k个区域内定义k个簇头，簇头承担起簇内集群内节点的数据转发和融合，但由于考虑传感器节点传输数据安全性以及在竞选簇头阶段减少能量损耗的需要，现提出主副簇头的概念，在k个区域内现引入副簇头，区域内簇头节点依据每个簇头节点能量损耗最少的原则进行竞聘，网络能耗最少的当选主簇头C1（Cluster1），能量消耗其次的，并引入主簇头和基站的距离因子考虑C2（Cluster2）副簇头。副簇头用于接收主簇头传递过来的数据，保证了数据的安全性，防止主簇头突然死亡引起的数据丢失;另一方面，当主簇头的能量低于簇内节点平均能量时，会比较副簇头与簇内平均能量的大小，若高于簇内平均能量，则副簇头当选为主簇头，主簇头为副簇头，直到主副簇头的能量均低于簇内能量或副簇头能量低于总能量的10%时，进行下一轮簇头选举，极大的减少了由簇头的选举而带来的能量损耗。

3 实验结果分析

在300×300的区间内随机分布了200个传感器节点，各节点通信能力相同，初始能量均相同，基站位于中心位置。仿真环境是Matlab2017b，电脑为联想拯救y7000，处理器为Intel（R） Core（TM） i7-9750H。

3.1 死亡节点数

整个传感器网络的性能好坏与传感器网络的生存时间息息相关，现通过各时间的节点死亡数目来进行衡量。图1是协议改进前后死亡节点数随时间变化的曲线，可以看出LEACH算法在2 000轮左右时，90%节点已经全部死亡，网络自此进入瘫痪不再感知和传送数据。TLE-LEACH算法在前期节点死亡较多是因为前期簇头C1和C2承担的簇内节点数据的接收，距离较远的容易较先死亡，在网络的500轮后，TLE-LEACH算法节点死亡速率较为平缓，网络生命周期持续到了15 000轮左右，相对于LEACH的2 000轮，网络的生命周期有了较好的改善。

3.2 网络能耗图

网络的总能量消耗可以衡量一个系统性能上的好坏，节点的能量损耗在传感器网络中占據了较为重要的部分，图2是协议改进前后网络能量随着时间变化的曲线，如图所示LEACH在2 000轮左右能量消耗殆尽，而TLE-LEACH在后续的竞选中簇头C1、C2竞选次数越来越少，使得能量的损耗大为减少，直到15 000轮左右时能量几乎耗尽，有效的延长了网络生存周期。

3.3 基站接收数据

图3是协议改进前后基站数据的接收量随着时间的变化的曲线图，可以看出TLE-LEACH算法在数据的转发量上有了较大的改进，原有的LEACH算法由于每轮选举簇头导致能量消耗较快，生命周期较短，发送数据量少，Sink节点接收的数据量就少，而TLE-LEACH算法的数据融合、最优簇头和双簇头机制有效的加长了网络的生存周期，增加了数据的发送量和基站接收的数据量，相对于LEACH算法，数据量的接收提升较大。

4 结论

无线传感器网络内的节点自身能量受限，且在一些恶劣的环境中，节点不易被替换，故需要尽量减少网络能耗，尽可能的延长网络生命周期。本文首先分析了LEACH协议，针对传统的LEACH算法，TLE-LEACH算法首先在簇头节点的选择上考虑了对冗余数据的融合以及最优簇头率，其次在LEACH的基础上引入了双簇头的概念，一方面加强了数据传输的安全性，另一方面由于减少了簇头的轮换进而减少了能量损耗以达到延长网络生存时间，传输更多数据的目的。仿真实验结果表明，本文提出的TLE-LEACH算法可以有效地延长网络生存时间，降低能耗，提升基站接收到的数据量，进而提升了网络整体的性能。本文依旧存在不足，在副簇头的选取时由于LEACH算法的随机性过大，网络节点内分区的数目会随之改变，主副簇头的选取也会随之改变，能量损耗与主副簇头的选取个数以及位置有关。簇内节点到簇头的数据传输以及簇头到基站的数据也是单跳形式进行传输，造成的能量损耗较大。在后续的工作中，可以考虑对LEACH算法的簇头选取进行一定的约束，同时在簇内和簇间数据传输时引入不同的路径规划算法，减少传感器网络的能量损耗来更好的延长网络生命周期。

参考文献

[1]YANG L， LU Y， LIU S， et al. A Dynamic behavior monitoring game based trust evaluation scheme for clustering in wireless sensor networks[J]. IEEE Access， 2018， （99）： 71404-71412.

[2]李兰凤，马佳荣.无线传感器网络路由协议分析[J].网络安全技术与应用，2019（5）：64-66.

[3]刘伟，杜佳鸿，贾素玲，等.能量有效的无线传感器网络分簇路由协议[J].北京航空航天大学学报，2019，45（1）：50-56.

[4]徐晶晶，张欣慧，许必宵，等.无线传感器网络分簇算法综述[J].计算机科学，2017，44（2）：31-37.

[5]CHEN D R， CHEN L C， CHEN M Y， et al. A coverage-aware and energy-efficient protocol for the distributed wireless sensor networks. 2019， 137：15-31.

[6]KHALIL E A， ATTEA B A， et al. Energy-aware evolutionary routing protocol for dynamic clustering of wireless sensor networks [J]. Swarm and Evolutionary Computation， 2011， 1（4）：195-203.

[7]李雪，南建國.基于IK-means聚类的分簇路由算法[J/OL].计算机应用研究：1-7[2021-01-29].https：//doi.org/10.19734/j.issn.1001-3695.2020.04.0104.

[8]章春华，陈宏伟.LEACH协议簇头选择算法的改进与研究[J].湖北工业大学学报，2012，27（2）：19-22.

[9]郭前岗，周德祥，周西峰.LEACH路由协议最优簇头数计算方法[J].微型机与应用，2013，32（3）：61-63+66.

[10] 蒋勇，赵作鹏.低能耗的无线传感网络分层聚类与节点管理机制[J].计算机工程与设计，2019，40（3）：638-643.

[11] 张顶，张琳.基于K-Means的WSN动态信任度双簇头选取算法[J].南京邮电大学学报（自然科学版），2020，40（2）：108-114.

[12] 李蕾，方明科.基于证据理论加权融合的无线传感器网络路由算法[J].吉林大学学报（理学版），2020，58（5）：1223-1228.

[13] 孔玉静，侯鑫，华尔天，等.基于BP神经网络的无线传感器网络路由协议的研究[J].传感技术学报，2013，26（2）：246-251.

[14] 石蔚，贾小珠. 一种Ad Hoc网络混合式分簇路由算法[J].青岛大学学报（自然科学版），2009，22（4）：62-66.

[15] 张秋，梁小凡，孙顺远，等.基于数据融合率的WSN节能策略[J].计算机测量与控制，2013，21（2）：454-457.

[16] DANIEL C. On the solution of linear differential equations with singular coefficients[J]. Journal of Differential Equations， 1982， 46（2）： 310-323.

[17] MADAN R， LALL S. Distributed algorithms for maximum lifetime routing in wireless sensor networks[J]. IEEE Trans on Wireless Communications， 2006， 5（8）： 2185-2193.

[18] 王勇，杨杰.基于无线传感网络定位的网关功能模块的实现[J]. 青岛大学学报（自然科学版），2016，29（1）：80-84.

[19] 章春华，陈宏伟.LEACH协议簇头选择算法的改进与研究[J].湖北工业大学学报，2012，27（2）：19-22.

[20] SOURABH P， AVINASH K. An application and architecture of low energy adaptive clustering hierarchy protocol in wireless microsensor network[J].Intematioual Journal of Engineering，Science and Mathematic， 2018， 7（3）：314-326.