无线传感网络LEACH协议的优化研究

舒冰，苏震

(中国传媒大学 信息工程学院，北京 100024)



无线传感网络LEACH协议的优化研究

舒冰，苏震

(中国传媒大学 信息工程学院，北京 100024)

摘要：LEACH(Low-Energy Adaptive Clustering Hierarchy低功耗自适应分簇)算法可以有效地解决传感器节点能量限制的问题，显著地延长整个网络的生命周期。但在分簇簇头的选择过程中仅考虑此节点是否在之前的轮中担任过簇头节点，并未考虑节点剩余的能量与其所处的位置，使得簇头的选择并非最优。针对这种情况，本文在原有LEACH路由算法的基础上从节点剩余能量与节点分布位置两方面对其进行优化，提出了一种新的路由优化算法为I-LEACH。仿真结果显示I-LEACH较LEACH协议延长了网络生存周期，降低了网络总体能耗，使无线传感网的整体性能得到一定提升。

关键词：LEACH；无线传感网络；分簇；簇头选择；能耗；生存周期

1引言

无线传感器网络(wireless sensor network，WSN)由许多具有低功率无线收发装置的传感器节点组成，能够采集周围环境信息并传送到远处的基站进行处理。由于传感器节点的电池能量有限，因此节点的通信应该有效地利用能量，以延长网络的生命周期。

无线传感器网络节点要进行数据通信就要有相应的无线网络协议(包括MAC层、路由、网络层、应用层等)，传统的无线协议很难适应WSN的低花费、低能量、高容错性等的要求。在这种情况下，ZigBee协议应运而生，Zigbee的基础是IEEE 802.15.4。但IEEE仅处理低级MAC层和物理层协议，而Zigbee联盟扩展了IEEE，对其网络层协议进行了标准化。但值得注意的是，在已经发布的ZigbeeV1.0中并没有规定具体的路由协议。

网络数据传输离不开路由协议，路由协议是其组网的基础，路由技术是WSN通信层的核心技术。路由选择问题是WSN网络构建时所要着重考虑的一个问题，从路由的角度来看，WSN有其自身的特点，使它既不同于传统固定网络，又不同于无线自组网AdHoc网络。在其研究初期，人们认为成熟的Internet技术加上AdHoc路由机制对WSN的设计是足够充分的，但是深入地研究表明，WSN有不同于传统无线网络和AdHoc网络的特点，前者以数据为中心，而后两者以传输数据为目的。由于WSN与传统网络对数据的侧重点不同，使得传统的无线AdHoc网络路由协议并不适合用于WSN，所以我们必须设计全新的、适合于WSN特点的路由协议。虽然已经提出了很多的路由协议，但是到底哪一种是最合适的还没有一个定论，因此WSN路由协议的研究与设计是近年来国内外研究的热点课题。

LEACH协议是为WSN专门设计的低功耗自适应分簇路由协议，是一种基于分簇结构和完全分布式的层次路由协议，其后的大部分层次式路由协议都是在此基础上发展而来。它将传感器网络节点以一定限制条件划分成簇，在工作过程中各节点独立地按照概率随机决定自己是否做簇头，通过周期性的簇头选举和网络重组过程，形成了轮转的工作方式。这样可有效平衡网络负载，大大节约了通信过程中的能量消耗。另外，簇头节点在处理数据的时候用到了数据融合技术和数据压缩技术，使得传输的数据量大大减小。因此如何优化簇头的选择是算法设计中所必须考虑的重要问题之一。然而由于LEACH协议的簇头选择仅以此节点是否在过去几轮担任过簇头这一标准，在实际应用中，会使拥有较低剩余能量的节点同较高剩余能量的节点具有相同的概率成为簇头节点，并未能达到簇头选择的最优化。

本文针对LEACH簇头选择算法的不足之处，在LEACH簇头选择算法的基础上，提出将节点剩余能量与节点到基站的距离作为簇头选择的考虑因素，根据节点所在区域的不同将上述的两个参数进行加权处理，最后根据加权簇头选择阈值选出更加合理的簇头，进而合理分配网络节点能耗，提高网络的生命周期。

2LEACH协议

LEACH协议的主要目的是均衡网络能耗以增加网络生命周期。为达到此目的LEACH路由算法使用分层方式将网络分为一系列的簇，每个簇由一个簇头控制。簇头按照TDMA(Time Division Multiple Access，时分多址机制)分配时隙给每个簇成员节点，使其可在分配的时隙内向簇头发送数据以及对接收的数据进行聚合处理以去除多余的相关数据进而减少发送能耗，最后簇头将处理后的数据直接发送至基站，LEACH协议网络拓扑如图1所示。LEACH协议的流程以轮作为基本单元，每轮又由两个阶段组成，分别是簇形成阶段与稳定传输阶段。

图1　LEACH协议网络拓扑图

2.1　簇形成阶段

2.1.1　簇头选择轮转算法

确定当前节点i是否成为簇头节点，i节点在0到1之间选择一个随机数V，随后将此V值与簇头选择阈值T(n)进行比较，若V

(1)

式中，P是簇头的节点占节点总数的百分比，r为当前循环轮数，G为在过去轮中没有当选成簇头的节点集合，符号mod是求模运算符，使用这个阈值，每个节点会在轮操作内担当一次簇头节点。

在每轮循环中，如果节点己经当选过簇头，则把T(n)设置为0，这样该节点不会再次当选为簇头。对于未当选过簇头的节点，则将以T(n)的概率当选；随着当选过簇头的节点数目增加，剩余节点当选的阈值T(n)随之增大，节点产生小于T(n)的随机数的概率随之增大，所以节点当选簇头的概率增大，这样才能保证每一轮中簇头的个数保持均衡。当只剩下一个节点未当选簇头时，设其T(n)=1，表示还没有做过簇头的节点，即这个节点一定当选为簇头节点，因为所有的节点的标志值都是在0-1之间的，等过了1/P轮以后，所有的节点就又可以重新充当簇头节点了。

2.1.2　簇形成算法

一旦某些节点被选定为簇头，这些簇头必须让网络中其它节点知道在当前轮中他们成为簇头的消息。这要求每个簇头使用CSMA(Carrier Sense Multiple Access，载波侦听多路访问)MAC协议向剩余节点们广播自己成为簇头的宣告消息。剩余节点在簇头广播阶段必须将接收器持续打开以接听簇头们的宣告消息，在一定时间间隔接收到多个宣告消息之后，根据接收到宣告消息的强度来决定加入哪个簇。这是由于宣告消息的强度越大说明这个节点和发出此消息的簇头的距离越近，从而加入此簇头所在的簇相对可以节省能量。

在每个节点确定加入哪个簇之后，它必须告诉簇头它成为这个簇的成员。每个节点同样使用CSMA MAC协议发送加入此簇申请消息到相应的簇头。簇头接收所有的申请消息后根据簇成员节点的数目，以TDMA方式为每个簇成员节点分配时隙并用广播的形式发送到本簇内所有的簇成员节点，每个簇成员节点便可以在自己分配到的时隙中进入了稳定传输阶段。

2.2　稳定传输阶段

在此阶段，簇成员节点周期地采集传感数据并在分配到的时隙中向簇头发送采集到的数据。整个传输阶段以帧为单位分为等时间间隔的时隙，在发送完数据后，簇成员节点进入休眠状态以减少能耗。建立数据发送时序表是为了避免同时向簇头发送数据时所产生的碰撞，并且增加每一个非簇头节点的休眠时间以减少能耗。LEACH协议时序流程如图2所示。

图2　LEACH协议时序流程图

3I-LEACH优化协议

由于LEACH路由算法中簇头选择方式单一，仅考虑其在之前的轮中是否已被选为簇头节点这一条限制条件。而在实际情况中，仅此一条限制条件无法达到簇头的最优选择。针对LEACH路由算法的这种缺点，本文在LEACH协议簇头选择算法的基础上从能量与距离两个方面对算法提出优化。

本文使用的传感网络仿真区域分为3个部分。根据节点当前能量与初始能量的比值与簇头到基站的距离作为簇头选择的两个主要参数，在不同的子区域内能量与距离的加权处理方式不同。式(2)为I-LEACG协议T(n)的表达式：

(2)

式中，α为能量和距离的加权因子为一常数值0.75，dtoBS是传感节点到基站的距离，Ecurrent是本轮当前节点能量值，Einit是传感节点初始能量值：

同LEACH算法一样，每个传感节点选择一个随机数，但在本文提出的优化路由算法中此随机数的取值范围有所不同，即在0至narea_i之间随机选择一个数值为V，同时在不同的节点分布区域内narea_i的取值范围不同，具体取值方法如下：

接着将此随机数V与优化的簇头选择阈值进行比较。假如，v

图3　I-LEACH协议簇头选择算法流程图

4仿真结果与分析

本文使用Matlab软件仿真路由算法优化的结果。WSN区域是一个200m×200m的正方形区域，基站位于原点处，分别以两个半径不同的同心圆弧(半径分别为100m和200m)将整个网络区域分为三个子区域，网络节点区域分布仿真如图4所示以及仿真参数的具体设定如表1所示。

表1　仿真参数的设定

图4　网络节点区域分布仿真图

4.1　网络生存周期

如图5所示的是网络存活节点总数随轮数的变化曲线，此曲线即是整个网络的生存周期图。从图中可以明显看出I-LEACH协议的仿真曲线比LEACH协议下降的更慢，这说明I-LEACH协议在接下来的周期里存活节点数比LEACH协议更多。在此两种路由协议管理下的网络失效周期即无存活节点周期分别为LEACH(460轮左右)而I-LEACH(850轮左右)，I-LEACH协议网络的生存周期相较LEACH协议几乎增大了一倍。这是因为I-LEACH路由算法在进行簇头选择时考虑到了更多实际因素，使得网络整体能耗更加趋于合理，从而增加了网络的生存周期。

图5　网络存活节点数对比图

图6　网络能耗对比图

4.2　网络能量消耗

网络能耗的主要来源为簇头接收和融合数据能耗、簇头发送数据到基站能耗、簇成员节点发送数据到簇头能耗。这里假设簇内数据的接收与发送距离较短，可以使用自由空间模型建模。而簇头与基站的距离较远，采用多径衰落模型建模，两种模型的区分标准如下所示：

设一个区分两种空间模型的距离临界值d0，如果收发距离大于d0，则收发能耗按照多径衰落模型计算，反之，按照自由空间模型计算。式(3)为d0的计算公式：

(3)

发送或接收l bit的数据在距离为d的条件下发送能耗ETX公式与接收数据能耗ERX分别如式(4)-(6)所示：

如果d

ETX(l，d)=Eelec·l+Efs·l·d2

(4)

如果d>d0，符合多径衰落信道模型，

ETX(l，d)=Eelec·l+Efs·l·d4

(5)

ERX=Eelec+EDA·l

(6)

式中，Eelec是收发电路发送或接收每比特数据的能耗值；Emp是在多径衰落信道中的信号放大能耗；Efs是在自由空间信道中的信号放大能耗；EDA是数据聚合能耗值。

网络总体能耗计算模型如式(7)-(10)所示：

簇头能耗：

ECH=ERX+ETX(l，d)

=(Eelec+EDA)·l+Eelec·l+Emp·l+d4

(7)

簇成员能耗：

ECM=ETX(l，d)=Eelec·l+Efs·l·d2

(8)

单个簇群能耗：

(9)

网络总能耗：

(10)

其中，k是本簇内共有的簇成员数，countCHs是每轮网络选出的簇头总数。

如图6所示的是两种路由协议下的网络总体能耗图，从零轮起I-LEACH路由算法能量消耗增长的速率明显低于LEACH协议，其中LEACH路由协议在300轮左右就达到了网络能耗的最大值，而I-LEACH网络能耗达到最大值(与LEACH的相同)则是在750轮左右。此图说明I-LEACH协议下网络的整体能耗在0至750轮之间比LEACH协议要小，进而使网络的生存周期有所延长。

5结论

本文针对LEACH路由协议簇头选择参考因素单一的缺点，从节点本轮能量与初始能量比值和节点与基站之间的距离二者加权的簇头选择阈值对LEACH路由协议进行优化，进而提出了I-LEACH路由协议算法。通过仿真结果可知，此优化协议较LEACH延长了网络生存周期，降低了网络总体能耗，使无线传感网络的整体性能得到进一步提升，对WSN路由协议设计与研究提供了一些参考。

参考文献

[1]Gajjar S H，Dasgupta K S，Pradhan S N，Vala K M.Lifetime Improvement of LEACH Protocol for Wireless Sensor Network[C].NIRMA University International Conference on Engineering，2012.

[2]Handy M，Haase M，Timmermann D.Low energy adaptive clustering hierarchy with deterministic cluster-head selection[C].IEEE International Conference on Mobile Wireless Communications Networks，September 2002：368-372.

[3]孙利民，李建中，陈渝.无线传感器网络[M].北京：清华大学出版社，2005.

[4]张浩，李腊元.基于LEACH 协议的能耗均衡路由算法[J].计算机工程，2011，7(7)：91-93.

[5]谢冬梅.无线传感器网络LEACH路由协议的研究[D].南京：河海大学计算机及信息工程学院，2007.

(责任编辑：王谦)

The Optimization Research of LEACH Protocol In Wireless Sensor Network

SHU Bing，SU Zhen

(College of Information and Engineering，Communication University of China，Beijing 100024，China)

Abstract：LEACH (Low-Energy Adaptive Clustering Hierarchy)can effectively solve the problem which is the energy of sensor node is limited，and significantly extend the lifetime of the whole network.But in the process of the election of cluster head (CH) only consider whether this node in the previous round was served as CH nodes，don’t consider the node residual energy and location，making CH selection is not optimal.In view of this kind of situation，this paper have improved LEACH routing algorithm from the aspects of node location and residual energy of nodes，therefore an optimized algorithm is proposed and called I-LEACH.The simulation results show that I-LEACH extend the network lifetime much longer than LEACH and reduce the network total energy consumption，so making the performance of WSN have been promoted.

Keywords：LEACH；WSN；clustering；selection of CH；energy consumption；lifetime of WSN

作者简介：舒冰(1986-)，男(汉族)，山西太原人，中国传媒大学硕士研究生.E-mail：shubing062022104@163.com

收稿日期：2015-04-12

中图分类号：TN915.02

文献标识码：A

文章编号：1673-4793(2015)05-0054-06