LEACH 协议簇头个数优化的研究

张飞鸽

(宝鸡文理学院电子电气工程学院，陕西 宝鸡 721007)

0 引言

无线传感器网络(Wireless Sensor Network，WSN)主要由一组较为齐全的MEMS 设备构成，这些设备体积仅有毫米般大小且能量有限，在整个网络中分布数量较多，覆盖区域面积较大［1］;WSN 与传统传感器相比，WSN 可以分布于偏远区域，并使用某些复杂技术区分周围环境噪声中的对象，还可以将传感器感知到的现象随着时间序列发送给中心节点，中心节点再对此做相应的处理，如数据融合和计算等。WSN 将采集的信息发送到中心节点离不开路由协议，笔者主要根据WSN 中节点能量有限的特点，计算在一定条件下LEACH 协议的最佳簇头个数，确定整个网络的簇头数，减少网络能量消耗，达到延长网络生命周期的目的。

1 LEACH 协议概述

无线微型传感器网络低能量自适应分群分层(Low Energy Adaptive Clustering Hierarchy，LEACH)是一个采用MAC 协议和路由协议进行低能量网络操作的应用型协议体系，其具有自组织网络节点的分布式分群技术，实现节点间能量均衡分布的分群自适应算法和簇头节点的更换循环算法，相对于一般多跳路由算法，如果LEACH 中的簇头节点采用多跳方式将信息转发给中心节点，则可以将系统的寿命提高大于一个数量级［1］。

LEACH 是WSN 最早提出的一种分簇路由协议，它用到了“轮”的概念，即具有周期性的特点。在LEACH 算法中，每轮包括簇的准备建立阶段和稳定状态阶段。在准备阶段主要完成簇的建立，这一阶段消耗的能量相对于稳定阶段完成数据传送消耗能量较少，为了节约网络能耗，稳定阶段所设置的时间远远大于准备阶段［2］。经过一段时间后，如果已经完成了本轮所有工作，那么就可以重新进入到下一轮的启动，直到网络中节点全部死亡［3］。

在LEACH 协议中，节点将采集的信息发送给基站主要依靠簇头。当簇建立阶段完成后进入稳定阶段，非簇头节点将信息发送给簇头，簇头再将信息融合后发送给基站。即簇头在网络中有2 个方面的作用:1)建簇和接收成员节点的数据并进行融合;2)转发数据到基站。如果网络内选取的簇头数过多就会造成数据冗余，浪费节点能量;如果簇头数量过少又会加重簇头负担，导致簇头节点能耗过快而死亡［4］。因此，网络中簇头的作用非常重要，如果确定最佳簇头的个数，那么就可以均衡网络的能量消耗，有效地延长网络的生存周期。

文献［5］中结合节点分布密度和节点剩余能量2个因子重新设置阈值T(n);文献［6］考虑了节点的剩余能量和节点距离基站的能量因子设置新的阈值;文献［7］根据节点剩余能量，动态选择分簇算法;文献［8］考虑了节点剩余能量和位置信息。在簇的建立阶段，这些方法都是将能量因子与阈值T(n)结合，选取剩余能量较多节点当选为簇头，但是其并没有考虑簇头的选取与节点产生的随机数有关，只有让剩余能量大的节点产生的随机数较小，即随机数小于T(n)的概率增大，才能保证能量较小的节点不被选为簇头，从而延长网络生存时间。在稳定阶段，文献［9］采用选择能耗最小的簇头转发信息;文献［10］中簇头采用多跳方式转发信息并推导出单跳与多跳的条件;文献［11］中簇头将融合后的信息发送给基站采用单跳和多跳相结合的方式。这些研究结果表明，在稳定阶段应该采用单跳和多跳相结合的方法转发信息，才能更多地节约网络能耗。

为了延长网络的生存时间，笔者主要从2 个方面对LEACH 算法改进。首先根据节点在本轮中消耗的总能量确定最佳簇头个数范围，簇头将消息发送到基站可以采用单跳与多跳结合的方式。其次根据节点剩余能量对节点本身产生的随机数进行优化，并结合节点与簇头距离，使选取的簇头更加合理。仿真实验可知，改进后的算法不但可以延长网络生存时间，而且使选取的簇头分布较为合理。

2 确定最佳簇头数

2.1 节点能耗模型

文献［1］利用了一个简单电台模型，此模型包括2 个信道模型，分别为自由空间(d2)信道模型和多径衰落(d4)信道模型，为了确保每轮的分簇期望个数k，通过计算通信能量模型，从而得到k 的最佳值为:

其中，d 为发射机与接收机之间的距离，假设有N 个节点均匀分布于M×M 的区域中，簇头到基站之间的距离设为dtoBS，efs和emp分别为信号放大器的放大倍数。由于计算簇头数kopt时，LEACH 协议设节点具有完全累积数据的能力，并且每个节点直接将消息发送给簇头或基站，即簇头采用一跳方式将消息发送给基站［12］。同时，计算一帧网络总能耗时，仅考虑节点在稳定阶段的能量消耗，并没有考虑建立簇时所消耗的能量。本文继续沿用该简单电台硬件模型，考虑到节点数据融合能力，簇头采用多跳的方式将消息发送给基站(目的是节约网络能耗)，从而计算出分簇的最佳个数。

网络在一轮中所消耗的能量包括建立阶段能耗及稳定阶段能耗。建立阶段能耗包括簇头建立簇所用的能量，稳定阶段能耗不仅用于数据传送还用于数据融合［13］。由于簇头的个数直接影响网络能耗，簇头数过多不但降低节点冗余率而且增加簇头节点的能耗，簇头数过少增加成员节点能耗，因此需要根据网络在一轮中总能耗得到分簇的最佳数。

2.2 簇的建立能耗

在LEACH 中，采用分簇算法是为了保证每轮的分簇期望个数K［14］。一旦节点选定为簇头后，簇头会立即向全网节点广播自己为簇头的消息，假设广播的距离为d，为了保证簇头广播的消息能够覆盖范围较广，因此可以采用多径衰落模型，那么，簇头广播一条长度l 比特消息的耗能为:lEelec+lempd4，其中，Eelec表示电台电子元器件耗能;未被选为簇头的节点(成员节点)根据收到广播消息的信号强度选择通信能量最低的簇头作为自己本轮的簇头［15］。簇头将会收到成员节点的加入请求消息，则簇头接收加人消息所消耗的平均能量为:lEelec(N/K-1)，成员节点数为N/K-1 个。

在LEACH 协议中，簇头是本地的控制中心，协调簇内的数据传输，簇头节点创建簇内的TDMA 时隙表并发送给簇成员，簇头到非簇头的距离用dtoch表示，则此时簇头消耗的能量为:lEelec+。所以，簇建立阶段每个簇头节点消耗的能量为:

在簇的建立阶段，成员节点主要任务接收簇头广播自己为当前簇头的消息，并接收簇头发送的TDMA时隙和发送该加入簇的请求消息。因此，簇建立阶段每个成员节点消耗的能量为:

根据上述分析，簇建立阶段的总能耗为:

2.3 稳定阶段的能耗

稳定阶段主要是进行数据的传输［16］，簇内成员节点和簇头的距离较近，簇头和基站的距离相对较远，所以采用簇内单跳和簇间多跳(利用中继节点)的数据传输策略，其中簇头节点的耗能主要由3 部分构成，分别为簇头融合数据能耗、簇头接收成员节点发送的消息能耗和融合后的消息发送给中继节点的能耗［17］。

假设簇头和基站之间距离较远，簇头节点采用多跳方式将消息转发到基站［18］。簇头首先将消息转发给中继节点，再通过中继节点将消息转发给基站，设中继节点数为n，那么簇头需要经过n +1 跳才能将消息传递基站。如果每个分群有ω 个节点，每个节点数据融合率为m，且节点融合一个比特数所消耗的能量为EDA，那么簇头最多融合ω 个长度为l 比特消息所消耗的能量为:

在稳定阶段，单个簇头接收成员节点的耗能为:

当簇头采用多跳传输方式向基站发送消息时，假设簇头到中继节点的距离为dhop，而中继节点相对簇头到基站的距离较短时，采用自由空间模型发送消息［19］。簇头将数据融合后发送给第一个中继节点的耗能为:

根据以上分析，在数据传输阶段某个簇头节点的3 部分能量消耗为:

由于中继节点数为n，那么簇头需要n +1 跳才能将消息传送给基站，且要求每个中继节点能够将数据完全融合。假设每跳距离相等都为dhop=γ，那么n个中继节点给基站发送消息的能耗为:

在本阶段成员节点将收集的消息按照TDMA 时隙发送给自己的簇头［20］。成员节点与簇头之间的距离较短，采用自由空间模型，则成员节点耗能为:

通过式(8)～式(10)的分析与推导，可知稳定阶段的总耗能表示为:

根据文献［1］中求解非簇首节点距离其簇头的平方距离的期望值的方法，有:

其中，为了便于推导，N 个节点均匀分布在M ×M 的正方形区域内，ω 取值为N/K，得到最差情况下稳定阶段的总能耗为:

2.4 最佳簇头数的优化

在一轮运行过程中，网络中所有节点消耗的总能量为建立阶段能耗E1与稳定阶段本帧的耗能E2之和，即:

根据式(14)可知，Enet是关于K 的函数，那么可以按照导数的性质得到网络中分群个数的最佳期望值为:

其中，efs，Eelec，EDA，emp均是固定的参数值，所以最佳簇头个数k 由网络区域M、网络中分布的传感器节点总数N、簇头节点建簇时发布广播消息的距离d 以及采用多跳传输的平均单跳距离γ 和中继节点数n 共同决定。由于n≥1，且当nγ2/2≥Eelec/efs时，簇头节点采用多跳方式，否则采用单跳方式，直接将消息发送到基站，这样可以节约簇头节点的能量消耗［14］。

3 优化簇头的选取

3.1 LEACH 簇头的选取

在LEACH 算法的建立阶段，簇头的选取主要根据节点产生的随机数(在0 -1 之间)是否满足阈值T(n)，如果节点随机数小于T(n)，那么该节点成为本轮的簇头，否则作为成员节点。阈值T(n)根据式(16)得:

其中，p 为簇头节点与非簇头节点的个数比;r 表示轮数;G 是在附近1/p 轮中从未当选为簇头的节点集合。由于最佳簇头范围可以根据之前的推导确定，那么p 值就能够根据所得到的k 值得到。从式(16)可知，阈值T(n)是关于轮数r 的函数，且在一定区域内，T(n)具有单调递增的特性，从而很难保证选取剩余能量较大的节点当选为簇头，当剩余能量较少的节点被选为簇头时，该节点有可能过早死亡，影响网络的生命周期。另外，LEACH 算法并没有考虑选取簇头分布是否均匀，如果簇头分布过于集中将会更多地浪费网络资源。

3.2 改进簇头选取

针对以上问题，根据相关文献的研究及分析，本文结合节点剩余能量，重新设置随机数α，使得:

其中，β 为节点产生的随机数，当节点能量各不相等时，能量较多节点应该比能量较少节点成为簇头的概率大，可以确保大部分节点能够在相同时间耗尽能量停止工作。为了达到该目的，设簇头的概率ρ 为关于节点剩余能量等级的函数，即ρ=，Ecurrent为节点剩余能量，E0为节点初始能量。λ 为调制因子，保证0 ＜α ＜1。

根据式(17)可知，当节点剩余能量Ecurrent较大，节点当选簇头概率ρ 就较大，随机数α 就较小，越容易满足阈值T(n);相反，Ecurrent越小，当选为簇头的概率较小。随机数的修改并没有改变原有随机数的均匀性和独立性，同时提高了剩余能量较多节点当选为簇头的概率。与文献［11］相比，式(17)产生的随机数既考虑了簇首的最佳个数还考虑了节点的剩余能量，如果簇首的个数k 在最佳范围内，那么可以更好地提高网络性能和延长网络生存时间。

通过以上分析，可以保证选取的簇头为剩余能量较多的节点，而且簇头数在最佳范围内，但是并没有考虑簇头节点在网络中均匀分布的问题。如果簇头分布集中或者分布边缘化，将会增加节点开销，缩短网络生存时间。因此，在选取簇头时，采用以下方法使得簇头分布较为均匀。

在选取第一轮簇头时，基站根据节点分布密度情况设置簇头分布位置和数量，从而保证初始簇头节点在整个网络中分布较为均匀，随后的簇头需要将上轮节点作为中心，以Rd为半径的圆内选取，Rd为:

其中，di为本簇内第i 个节点到簇头间的距离，μ 为簇内节点数。当满足式(17)且di＜Rd时，该节点才能成为本轮簇头，其他节点作为成员节点根据接收簇头信号强度加入不同的簇。从而可知，选取的簇头节点不但剩余能量较多，而且簇头分布不会过于集中以及边缘化。根据簇头最佳范围的推导，可以保证每轮选取的簇头数不会过多或过少，使得网络性能提高。

3.3 改进算法的实现

网络模型假设基站远离传感器场，且其能量充足，并不需要考虑能量消耗问题。网络初始化阶段，基站将网络的整体信息(包括第一轮簇头的选取)和位置采用泛洪方式广播;当节点收到自己为簇头的消息后，立即广播消息让其它节点知道自己为本轮的簇头，并等待成员节点的加入;成员节点向簇头发送一条Joint-REQ 请求消息，包括簇头和该节点的ID，从而获得Rd，簇头将建立的TDMA 时隙表和Rd发送给簇内节点，完成第一轮簇的建立。当第一轮完成数据的传输后，则进入下一轮簇头的选取，采用如下步骤实现:

由于在选取簇头时，式(16)和式(17)中已经考虑最佳簇头个数，所以在此并未考虑有多个节点同时当选为簇头的可能。

4 仿真与分析

本文使用MATLAB 软件进行仿真，设网络中含有100 个节点，随机分布在100 ×100 的区域内，基站位于(50，175)，仿真参数为:E0=0.5 J，Eelec=50 nJ/bit，EDA=5 nJ/bit，efs=10 pJ/bit/m2，emp=0.0013 pJ/bit/m2，数据包的大小为500 bit;结合式(15)，如果簇头节点到基站的距离为75 ≤dtoBS≤185 范围，可得估算每轮簇头最佳个数范围为3 ≤k ≤6。从图1 知，当簇头数目k 值取4 和5 时，网络消耗的能量明显较小，即当选取的簇头数在最佳簇头个数范围内时，可以相对减少网络能耗，延长网络生命周期。在第一轮中确定网络簇头的初始位置如图2 所示，图中选取了4 个簇头节点，簇头数满足最佳群首个数，而且其位置分布较为均匀，随后根据轮数r 的变化以及节点按照自身产生的随机数α 是否满足阈值T(n)和该节点与上轮簇头间的距离是否小于Rd，判断该节点是否当选为簇头。

图1 不同簇头数目下的网络能耗

图2 起始簇头节点的分布

图3 主要是对LEACH、LEACH-I 和LEACH-II 进行比较与分析，其中，LEACH-I 代表仅采用式(17)来修改节点随机数选取剩余能量更多的节点作为簇头，稳定阶段与LEACH 算法相同;LEACH-II 代表在LEACH-I 的基础上采用式(17)修改节点随机数，同时选取的簇头还要满足di＜Rd，且选取的簇头节点数保证在最佳范围内，以及数据传送阶段节点采用单跳与多跳相结合的方式发送数据给基站。从图中可以看出，LEACH 的第一个死亡节点出现在723 轮，而LEACH-I 和LEACH-II 的第一个死亡节点分别出现在第851 轮和第1169 轮，从而可知，当簇头数选取在最佳范围内，改进后的LEACH-II 提高了网络的寿命，延长网络生命周期。

图3 网络轮数与剩余节点数的关系

5 结束语

本文首先分析了LEACH 协议的基本工作原理和性能，由于网络能量的消耗受簇头节点数目的影响，通过对建立阶段和稳定阶段各节点的能耗进行分析，并结合簇头采用多跳方式将消息转发给基站节约能耗的方法，推导出最佳簇头个数的范围。其次，在簇建立阶段，不但考虑了节点的剩余能量，而且考虑了成员节点与簇头节点的距离，使选取的簇头避免边缘化分布和能量较少。通过仿真可知，当网络中簇头节点数分布在最佳范围内，改进的LEACH-II 算法的网络总能量消耗相对较少，延长了网络生存时间。

［1］陈林星.无线传感器网络技术与应用［M］.北京:电子工业出版社，2009.

［2］蒋阳，孙柳林，敖文钧，等.WSN 中LEACH 路由协议簇头数优化研究［J］.计算机应用研究，2010，27(11):4251-4253.

［3］Weber S，Andrews J，Jindal N.An overview of the transmission capacity of wireless networks［J］.IEEE Transactions on Communications，2010，58(12):3593-3604.

［4］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 Network.2002:368-372.

［5］单晓娜.无线传感器网络LEACH 算法的研究与改进［D］.南昌:南昌大学，2009.

［6］王郭燕.基于分簇的无线传感器网络路由协议研究与改进［D］.成都:电子科技大学，2012.

［7］单晓娜，李力.LEACH 路由协议技术的分析及改进［J］.计算机与现代化，2009(9):81-83.

［8］李玲，王林，张飞鸽，等.无线传感器网络低功耗自适应分簇协议［J］.计算机应用，2012，32(10):2700-2703.

［9］万青苗，张浩平，王强，等.无线传感器网络LEACH 协议的改进研究［J］.电脑知识与技术，2012，32(8):7679-7701.

［10］唐翠微.能量均衡的无线传感器网络节点路由算法［J］.计算机与现代化，2015(1):102-121.

［11］李建坡，姜雪，朱绪宁.无线传感器网络能耗均衡LEACH 路由算法［J］.自动化仪表，2014，35(1):51-54.

［12］张飞鸽.无线传感器网络路由协议的研究［D］.西安:西安理工大学，2012.

［13］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京:清华大学出版社，2005.

［14］刘玉华，赵永峰，徐凯华，等.无线传感器网络LEACH协议的改进［J］.计算机工程与应用，2010，46(17):117-120.

［15］Yu Jiguo，Liu Wenjun，Song Jingjing，et al.An energy-efficient multi-hop routing protocol for wireless sensor networks［C］// AICCSA 2008.IEEE/ACS International Conference on Computer System and Applications.2008:291-298.

［16］庄琴清.无线传感器网络分层路由协议研究［D］.南京:南京邮电大学，2013.

［17］陈树，徐圆.基于分簇和覆盖优化的改进LEACH 协议［J］.计算机工程，2014，40(11):97-101.

［18］Xu Jia，Jin Ning，Lou Xizhong，et al.Improvement of LEACH protocol for WSN［C］// Proceedings of 2012 International Conference on Fuzzy Systems and Knowledge Discovery.2012:2174-2177.

［19］Zhao Fuzhe，Xu You，Li Ru，et al.Improved LEACH communication protocol for WSN［C］// Proceedings of 2012 International Conference on Control Engineering and Communication Technology.2012:700-702.

［20］王返.基于LEACH 的无线传感器网络路由协议改进研究［D］.广州:华南理工大学，2014.