无线传感器网络LEACH 协议的研究与改进

游晓黔，李明隆，杨 佳

（重庆邮电大学计算机科学与技术学院，重庆 400065）

0 引言

无线传感器网络（wireless sensor network，WSN）已被广泛地应用在民用和军事领域。它是由大量低成本的体积小的传感器节点组成，通过无线通信方式形成的一个多跳自组织网络。不需要固定的基础网络设施，具有快速展开，抗毁性强等优势以及自组织，动态拓扑和能量受限等特点。由于它具有良好的应用前景，目前已经成为无线信息技术领域的研究热点［1］。

路由技术是WSN关键技术之一。由于传感器节点计算能力不强，存储空间有限，能量储备和通信能力较低等限制条件，能量的约束性问题成为了WSN中必须考虑的核心问题［2］。根据WSN的拓扑结构，路由协议可以分为平面路由协议和分簇路由协议。常见的平面路由协议有Flooding，Gossiping，MTE，SPIN等。由于平面路由协议需要维持较大的路由表，占据存储空间较多，因此不适合在大规模的网络中采用。在分簇路由协议中，簇首节点协调簇内成员节点之间的工作，可以在一定程度上克服平面路由协议的缺点，从而有效地减少能量消耗，延长网络的生命周期。目前，层次化路由成为WSN中主导的路由协议。以低功耗自适应分簇协议（low energy adaptive clustering hierarchy，LEACH）协议为代表的分簇路由协议能够有效地延长网络的生命周期［3］。本文首先分析LEACH以及LEACH相关改进协议的特点和不足，然后提出一种改进的基于LEACH的能量高效分簇路由算法（the energy-efficient clustering routing algorithm based on LEACH，LEACH-EE）算法，主要目标是降低网络系统能量消耗，延长网络的生命周期，并对该方案进行理论分析和实验仿真，仿真结果验证了该方案的有效性。

1 LEACH协议机制分析

LEACH［4］是MIT学者Heinzelman等为WSN设计的低功耗自适应聚类路由算法，是最早提出的分簇路由算法，仿真表明，与一般的平面多跳路由协议和静态分簇路由协议相比，LEACH可以将网络生命周期延长15%。LEACH分为2个阶段，即簇的建立阶段（set up phase）和数据传输阶段（ready phase）。簇的建立阶段和数据传输阶段所持续的时间总和称为一轮（round）。为了节省资源开销，数据传输阶段的持续时间要大于建立阶段的持续时间。它的基本思想是系统运行后依据网络中所需的簇首节点数和迄今为止每个节点已成为簇首节点的次数来决定簇首节点的选择。具体选择办法是:每个传感器节点在第r轮时（假设当前时间为t）从（0，1）之间选择一个随机数，如果选定的值小于某个阈值Pi（t），那么这个节点成为簇首节点，Pi（t）可由（1）式计算得到。

（1）式中:Ci（t）表示节点i在最近r mod（N/k）轮是否担当过簇首节点，如果担当过，则Ci（t）=0，否者Ci（t）=1;k表示网络中簇首节点的个数，在一个已知的目标区域内，面积为M×M，传感器节点总数为n，节点均匀分布在监测区域中，即ρ=（1/（M2/k））。可以通过以下计算推导出网络中最优的分簇个数

（2）—（4）式中:εfs和εmp表示无线能量模型中的参数;dtoCH是簇内成员节点到簇首节点的距离;Etotal为总共消耗的能量;dtoBS为簇首节点到基站之间的距离;Eelec为发射电路和接收电路所消耗的能量;EDA为进行数据融合所消耗的能量。

选定簇首节点后，簇首节点通过广播告知整个网络自己成为簇首节点的消息，网络中的非簇首节点根据接收信号的强度决定加入相应的簇首形成簇，并通知相关的簇首节点。最后簇首节点采用TDMA方式为簇中每个节点分配传输数据的时隙。在数据传输阶段簇内成员节点将监测到的数据直接发送给簇首节点，簇首节点在对监测到的数据进行数据融合后再转发给基站。经过一段时间后进入下一轮。LEACH网络结构如图1所示。

图1 LEACH网络结构Fig.1 LEACH network structure

LEACH假设网络中使用相同的能量受限的传感器节点且每个节点均可以与基站直接通信。在网络部署后，传感器节点随机均匀部署在监测区域，所有节点持续监测周围的物理现象，然后以恒定的速率发送监测的数据。

LEACH-C［5］是一种基于LEACH的改进协议。它根据全局信息挑选簇首，每个节点把自身地理位置和当前能量报告给基站。基站根据所有节点的报告计算平均能量，当前能量低于平均能量的节点不能成为候选簇首节点。从剩余候选节点中选出合适数量和最优地理位置的簇首集合是一个NP问题。基站根据所有簇内成员节点到簇首节点的距离平方和最小的原则，采用模拟退火算法解决该问题，最后基站把最优分簇信息广播出去。因为每个区域的节点数大致相同，从而实现了负载均衡，其性能要优于LEACH协议。

LEACH-F［6］也是基于 LEACH的一个改进协议。其中，网络中第一轮簇的形成与LEACH-C协议相同，同样是通过基站采用模拟退火算法生成均匀的分簇。不同的是，基站为每一个簇生成一个簇首节点的列表，按照列表的顺序依次选择下一个节点担当簇首。网络中的分簇一旦形成，簇结构不再改变。此协议的优点是在一定程度上减少了成簇开销，但是可能选择剩余能量小的节点担任簇首节点。

上述几种协议在一定程度上均衡了各个节点的能量消耗，但是这些协议仍有以下几点不足。

1）成员节点在每轮分配的时隙中都必须向簇首节点发送数据，节点能量利用率不高。

2）簇首节点与基站采用直接通信的方式，这造成远离基站的簇首节点能量消耗较高。

3）在LEACH协议中，簇的形成完全是随机的，因此，很可能出现被选的簇头节点集中在网络某一区域的现象，这样就会使得一些节点的周围没有任何簇头节点，无法保证得到最优的分簇方案。

4）在LEACH-C协议中，在每轮成簇阶段，所有节点都必须将自己的位置和能量信息发送给基站，增加了节点之间的通信量，成簇开销较大。

5）在LEACH-F协议中，虽然减少了成簇的开销，但是网络中不能动态地处理节点的加入和删除，并且增加了簇间信号的干扰。

以LEACH为代表的路由协议提供了一种很好的负载均衡机制，最大限度地延长了网络的生命周期，但是，此类协议中依然存在一定的问题。文献［7］在基于固定分簇算法的基础上，为了减少通信量，通过由基站设定的阈值比例x，实现簇首节点的轮换，从而节省节点的能量。文献［8］提出了一种流量自适应分簇算法，通过在发送数据中捎带节点的状态信息state，从而对节点的发送时隙进行调整，实现减少节点能量消耗的目的。文献［9］针对网络覆盖范围变大时LEACH协议存在的问题，提出一种综合考虑节点位置、节点能量状况的多跳改进算法。

2 本文的改进方案

2.1 相关问题分析

在LEACH协议中，簇首节点作为一个簇的控制中心，簇内成员节点根据所分配的TDMA时刻表，在不同的传输时隙向簇首节点发送数据。这样做的目的是允许节点在不属于自己的时隙期间可以进入休眠状态，节省节点能量。但是节点在属于自己的时隙内必须向簇首发送数据，然而，在现实的大多数环境中节点不需要一直发送数据，通常是在监测到有异常数据时才发送自己的数据［10］。本文认为，在簇的建立阶段完成以后，簇内节点可以根据事先设定的阈值来向簇首节点发送数据，而不再是在规定的时隙里一直发送数据。这样可以达到限制传感器节点能量消耗的目的，延长了节点的寿命，从而也延长了网络的生命周期。

其次，LEACH-C协议解决了LEACH协议中簇首节点分布不均匀以及簇首节点根据随机数决定等方面的问题，提高了簇的生成质量。但是，在每轮的簇首选择阶段，网络中的所有节点都必须向基站报告它们的位置和能量信息，导致网络时延和成簇开销都比较大。而本文认为，应该减少节点的通信量，尽量避免不必要的通信。

最后，在LEACH协议中，簇首节点与基站都是单跳的通信，这样不可避免地造成偏离基站比较远的簇首节点与基站直接通信能量消耗增大。因此，应该在簇首节点之间建立路由树，在数据传输阶段采用单跳和多跳混合通信方式均衡簇头与基站能量消耗。由文献［11］可知，采用簇首节点间多跳的方式，可以保证数据尽快地传递到基站，并且可以降低网络整体的能耗。

2.2 方案基本思想

根据LEACH相关协议中存在的问题，主要从成簇的方法，簇首节点的选择以及成簇后的通信方式3个方面对上述方案进行改进。改进后的方案也分为簇的建立阶段和数据传输阶段，其基本思想如下。

1）网络部署后，在第一轮的簇首选择阶段，基站采用GSAA遗传模拟退火算法［12］来提高簇的生成质量。每个节点把自身的位置信息和当前的剩余能量报告给基站，然后基站根据所有节点报告的信息计算所有节点的平均能量。如果节点的当前能量低于平均能量，则不能成为候选簇首节点。然后基站在候选节点中通过遗传模拟退火算法得出一个最优分簇，并把分簇信息记录到一个cluster_info的链表中。最后把分簇信息广播出去，第一轮簇的建立阶段结束。

2）从第二轮开始，在簇的建立阶段，为了减少节点的通信量，网络中所有的节点只向基站发送自己当前的能量信息，不再发送位置信息。基站在接收到所有节点发送的能量信息后，根据第一轮的分簇信息，分别计算每一个分簇的平均能量。然后基站根据cluster_info链表中的分簇信息，依次选取簇内不同的节点担任候选簇首节点。当且仅当此候选簇首节点的剩余能量大于其所在簇的平均能量时，才选取它为下一轮的簇首节点，否者根据cluster_info链表中的分簇信息判断下一个簇内的成员节点。

3）在数据传输阶段，在簇内，簇内成员节点与簇首节点可以直接进行通信。假设网络中节点总数为n，成簇个数为m，使用CHj，（1≤j≤m）表示簇首节点，而{Si}，（0≤i≤n）表示簇内所有成员节点。首先对流量发送概率定义为:在数据传输阶段，节点集{Si}在所分配的TDMA时刻表规定的时隙向所在簇的CHj节点发送监测数据的概率为

P（Si）={x|0 ＜ x≤ 1，i∈［1，n］} （5）

为了符合实际的应用场景，对监测区域使用不同的流量发送概率，可以通过设定不同的P（Si）阈值实现。并可以通过统计基站收到的实际数据量，来对不同的流量发送概率进行评估。

4）在数据传输阶段，簇首与基站进行通信时，可以根据簇首节点与基站的距离采用多跳与单跳相结合的方式进行通信。即每个簇首节点选择在基站方向离自己最近的簇首节点作为下一跳邻居节点，向基站转发自己的数据。如果簇首节点没有找到下一跳邻居节点，则直接与基站进行通信。如图2所示，簇首节点CHa通过将数据转发给它的下一跳邻居节点CHb，从而最后将数据发送给基站。

图2 簇间信息转发过程Fig.2 Progress of inter cluster data forwarding

3 协议仿真和性能分析

3.1 节点流量发送概率仿真分析

NS2是目前WSN的主要仿真工具之一［13］，已广泛被科研院所和各大高校用于进行网络分析、研究和教学。本文仿真是在Windows下用软件Cygwin模拟UNIX系统环境，在此基础上安装NS2对LEACH协议中不同的网络流量模型进行仿真，实验结果取多次仿真的平均值。考虑WSN中有n=101，包括100个无线传感器节点和1个固定位置的BS节点。网络中最优簇个数k=5，节点每隔20 s的时间更换一轮簇首，所有节点的初始能量为2 J，所有节点随机均匀散布在监测区域，仿真中使用的网络配置参数如表1所示。

表1 网络配置参数Tab.1 Network parameters in experiment

在簇首节点CHj对节点集{Si}分配相应的时隙中，分别选取 P（Si） 为 1，0.9，0.8，0.7，0.6，0.5和一个在［0.5，0.9］区间的均匀随机值RND。针对不同的流量发送概率，对LEACH协议进行仿真。

图3 基站接收数据总量与时间关系Fig.3 Total receiving data of base station over time

基站收到的数据量和时间的关系如图3所示。从图3中可以看出，使用不同的流量发送概率，网络的生命周期和基站接收到的数据量是不一样的。当P（Si）∈［0.7，0.9］时，基站收到的数据量要比原有的LEACH协议高，说明减少了节点的能量消耗，节点节省下来的能量，传送了更多的有效数据，更加合理有效地利用了节点的能量。原因是在此时的流量模型下，簇内的一些节点在规定的时隙并没有向簇首节点发送数据，从而一些节点可以在数据传输阶段节省一部分能量。因此，基站收到的数据量相对较高。但是当P（Si）＜0.7时，基站收到的数据量要比原有的LEACH协议低，这是因为在此时的流量模型下，首先在延长的网络生命周期内，节点将更多的能量用在了簇首选择阶段。其次，在数据传输阶段，虽然一些簇内成员节点没有在规定的时隙内向簇首节点发送数据，但是此时簇首节点依然需要处于“唤醒”状态，等待接收簇内成员节点的数据，因此消耗了一些不必要的能量。

在实际的应用中，首先必须保证在对监测数据的完整性不会造成影响的前提下设置一个合理的流量发送概率，从而节省网络系统的能量消耗。从图4中可以看出，当选择 P（Si）∈［0.7，0.95］时，网络系统可以获得更好的性能，从而延长网络的生命周期。使用流量发送概率的通信方式，主要目的是通过阈值方式尽量减少节点的通信开销。在实际的应用中，可以通过节点定位技术估算网络中节点的密度，从而为不同的节点设置不同的流量发送概率。例如，在节点密度比较小的监测区域，尽量保证节点的发送概率较大，这样可以尽量保证数据的完整性;而在节点密度比较大的监测区域，由于节点采集的数据冗余度较大，因此可以将此区域中节点的流量发送概率设置偏少。在下一步的研究中，还应该进一步考虑针对每个节点如何选择对应的阈值，并且同时需要考虑动态阈值计算的时间以及能量开销等因素。

图4 基站接收数据总量与P（Si）关系Fig.4 Total receiving data of base station over P（Si）

3.2 网络低能耗验证分析

网络中存活节点数目和整个网络的生命周期随时间变化如图5所示。

图5 节点存活数目与时间关系Fig.5 Number of nodes alive over time

从图5中可以看出，LEACH-EE方案中第1个节点死亡的时刻为430 s，LEACH-C方案为380 s，比LEACH-C延后了13.2%，LEACH方案为360 s，比LEACH延后了19.4%;LEACH-EE方案中第10个节点的死亡时刻为510 s，LEACH-C方案为410 s，比LEACH-C延后了24.4%，LEACH方案为360 s，比LEACH延后了41.7%。而LEACH-EE方案比LEACH-F方案总体性能好的原因在于，在LEACHEE方案中，当且仅当候选簇首节点的剩余能量大于其所在簇的平均能量时，才选取它为下一轮的簇首节点，保证了选取最优的节点担当簇首节点。在相同的时间内采用新的方案可以有效地延长节点的寿命，从而延长整个网络的生命周期。这是因为新的方案在数据传输阶段，簇内节点通过选择比较合理的P（Si）流量发送概率阈值节省了能耗。而且从第二轮开始，在簇的建立阶段网络中所有节点只向基站发送自己的能量信息，减少了节点的通信能耗。最后在数据传输阶段，偏离基站较远的簇首节点通过采用簇首节点间多跳的传输方式将数据传递给基站，解决了簇首节点通信负载过重的问题。因此新的方案有效地延长整个网络的生命周期。

基站收到的数据量和时间的关系如图6所示。从图6中可以看出，改进后方案中基站收到的数据量相对较高，是因为在改进方案中节点通过多种方式节省了自身的能量，传送了更多的有效数据，从而更加合理地利用了有限的能量。其中，在改进的方案中通过设置合理的发送阈值的方式可以尽量减少节点的通信开销以延长了节点的寿命，从而基站可以接收到更多的数据保证了网络中数据监测的完整性。在实际的应用中，可以通过节点定位技术估算网络中节点的密度，从而为不同的节点设置不同的流量发送概率。比如，在节点密度比较小的监测区域，应保证节点的发送概率较大;而在节点密度比较大的监测区域，由于节点采集的数据冗余度较大，因此可以将此区域中节点的流量发送概率设置偏小。

图6 基站接收数据总量与时间关系Fig.6 Total receiving data of base station over time

网络中网络系统总能量消耗随时间的变化如图7所示。网络中每个节点的初始能量均为2 J，系统的总能量为200 J。从图7中可以看出，在改进的方案中，网络中的总能量消耗速度要慢于其他的协议，并且所有节点消耗的能量更加均匀，从而实现了网络系统负载更加均衡。

4 结束语

本文在分析LEACH以及LEACH相关路由协议算法缺点的基础上，对原有的算法进行了改进。所有节点形成位置和簇的个数固定的分簇，簇内成员节点根据能量轮换担任簇首节点，均衡了网络负载。在数据传输阶段，簇内成员节点根据实际的监测情况，通过设置合理的流量发送概率阈值向簇首节点发送数据，通过减少节点与基站的通信量，从而节省节点的能量，并且可以延长节点的寿命;同时在簇首节点之间使用多跳的传输方式，弥补了LEACH中单跳的不足。仿真结果表明新的方案可以提高整个网络的生命周期。

［1］AKYILDIZ I F，WEILIAN Su，SANKARASUBRAMANIAM Y，et al.A survey on sensor networks［J］.IEEE Communications Magazine，2002，40（8）:102-114.

［2］张怡，李云，刘占军，等.无线传感器网络中基于能量的簇首选择改进算法［J］.重庆邮电大学学报:自然科学版，2007，19（5）:613-616.

ZHANG Yi，LIYun，LIU Zhan-jun，et al.Cluster-head selection enhancing algorithm based on energy for wireless sensor networks［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2007，19（5）:613-616.

［3］路纲，周明天，佘堃，等.无线传感器网络路由协议寿命分析［J］.软件学报，2009，20（2）:375-393.

LU Gang，ZHOU Ming-tian，SHE Kun，et al.Lifetime Analysis on Routing Protocols of Wireless Sensor Networks［J］.Journal of Software，2009，20（2）:375-393.

［4］ HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H.An Application-Specific Protocol Architecture forWireless Microsensor Networks［C］//IEEE.In IEEE Trans on Wireless Communications.New York:IEEE Press，2002，1（4）:660-670.

［5］ MURUGANATHAN SD，MA Dcf，BHASIN Pi，etal，A centralized energy-efficient routing protocol for wireless sensor networks［J］.IEEE Communications Magazine，2005，43（3）:8-13.

［6］HEINZELAM W.Application-Specific protocol architectures for wireless networks［D］.Boston:Massachusetts Institute of Technology，2000.

［7］ 马玉刚，周群彪.基于LEACH的无线传感器网络节能算法［J］.计算机应用，2009，29（6）:1514-1516.

MA Yu-gang，ZHOU Qun-biao.Energy saving algorithm on wireless sensor network based on LEACH［J］.Journal of Computer Applications，2009，29（6）:1514-1516.

［8］蔡烽，蒋铃鸽，何晨.无线传感器网络的流量自适应分簇算法协议［J］.高技术通讯，2008，18（3）:226-230.

CAIFeng，JIANG Ling-ge，HE Chen.A traffic-adaptive clustering protocol for wireless sensor networks［J］.High Technology Letters，2008，18（3）:226-230.

［9］尚凤军，雷阳.无线传感器网络能量有效成簇算法研究［J］.小型微型计算机系统，2009，30（5）:839-842.

SHANG Feng-jun，LEIYang.Energy EfficientClustering Algorithm for Wireless Sensor Networks［J］.Mini-micro Systems，2009，30（5）:839-842.

［10］ TEAW E，HOU G，GOUZMAN M，et al.A Wireless Health Monitoring System［C］//IEEE.In IEEE International Conference on Information Acquisition.New York:IEEE Press，2005:247-252.

［11］ GUO Shu-jie，ZHENG Jie，QU Yu-gui，et al.Clustering and multi-hop routing with power control in wireless sensor networks［J］.The Journal of Beijing University of Posts and Telecommunications，2007，14（1）:49-57.

［12］刘阳，童小念.基于遗传模拟退火算法的网络负载均衡研究［J］.计算机与数字工程，2008，36（9）:16-18.

LIU Yang，TONG Xiao-nian.Research on Network Loading Balance Based on Genetic Simulated Annealing Algorithm［J］.Computer ＆ Digital Engineering，2008，36（9）:16-18.

［13］ ZHANG Jun-guo，LIWen-bin，CUIDong-xu，et al.The NS2-based Simulation and Research on Wireless Sensor Network Route Protocol［C］//IEEE.In Wireless Communications，Networking and Mobile Computing.Beijing:IEEE Press，2009:24-26.