一种基于LEACH的异构WSN能量均衡成簇协议*

叶继华，王 文，江爱文

（江西师范大学计算机信息工程学院，南昌330022）

无线传感网络WSN（Wireless Sensor Network）是一种自组织、多跳路由、动态、以数据为中心的大规模网络［1］。无线传感器网络路由技术是当今国内外研究的重点和热点，其设计的首要目标是提高能量有效性，延长网络生命周期［2］。WSN低功耗路由协议负责在Sink点和其余节点间可靠地传输数据［3］。LEACH［4］协议是层次型无线低功耗路由协议的典型代表。现今的很多经典都是受LEACH协议的成簇思想启发而来，比较有代表性的主要有HEED［5］、EECS［6］、PEGASIS［7］、EEUC［8］、TEEN［9］等。HEED是一种在LEACH协议基础上的改进协议，利用迭代的方式改进了簇头选举方法。但是，HEED算法在簇头选举阶段采取迭代的方式，增加了能量消耗，在采用单跳数据传输的假设下，其性能尚不如LEACH。EECS协议具有控制消息开销小，聚类在空间上分布近似均匀，网络能量有效利用率高等特点。但是，EECS也存在容易造成簇头分布漏洞、节点加入簇首未考虑节点剩余能量等问题。PEGA⁃SIS算法继承了LEACH的动态选举方法并加以改进，减少了因经常选举簇头而产生的能量浪费，并采用链式路由。TEEN协议采用与LEACH协议相同的分簇算法，但是在数据传输阶段使用不同的策略，通过设置软、硬两个阈值来减少数据的发送次数。EEUC是一种非均匀分簇的路由协议，考虑到靠近基站的簇头需要转发其他簇头的信息从而造成更多的能量消耗，通过竞争半径的计算，使得距离基站远的簇头具有更大的竞争半径形成更大的簇，但是EEUC对于节点与基站之间的距离等全局信息有很高的要求，这限制了其应用尤其是大规模应用的意义。Kodali R K等人针对LEACH协议不适合大规模网络问题，提出了多层次机构的LEACH协议，一定程度上解决了LEACH协议在超大范围网络 的 应 用［10］。Sapna Gambhir等 人 提 出 了 Op-LEACH［11］协议，这是一种针对稳定期的改进，让高信息量的节点占用其他不传输数据的节点的时间槽进行额外通信，可以有效降低数据传输延迟，提高数据传输效率。马建乐等人提出了基于位置与剩余能量的LEACH-LC［12］算法，与LEACH-C算法类似并在向BS提交的信息中增加剩余能量及与BS的距离等信。针对无线传感器网络中网络能量损耗不均的问题，陈晓娟等人提出了一种基于LEACH的改进节能路由协议 LEACH-PSOC［13］。

本文针对感知异构的传感器网络，以LEACH协议为基础，提出了基于簇内可变通信周期的能量均衡改进协议—ACPSEB-LEACH协议，在收集实际数据的基础上进行的仿真结果表明，改进后的协议在延长网络生存周期、平衡全局能量上有更好的效果。

1 改进的协议ACPSEB-LEACH

1.1 LEACH协议分析

LEACH协议的全称为低功耗自适应集簇分层型协议，为层次路由协议的典型代表。该算法基本思想是：以循环的方式随机选择簇头节点，将整个网络的能量负载平均分配到每个传感器节点中，从而达到降低网络能源消耗、提高网络整体生存时间的目的。

LEACH算法分为三个部分：①簇头选举；②簇成员加入成簇；③簇的路由。选举时，每个节点产生一个介于0和1之间的随机数，如果这个数小于阈值T（n），该节点成为簇头。

式中为T（n）的计算方法，其中p表示网络中的簇头比例，r表示轮数，集合G表示前1/p轮没有当选簇头的节点集合。但LEACH算法存在如下不足：①LEACH算法的随机簇头选举会造成簇分布不合理，全局能耗不均，特别是离基站远的节点更容易过早死亡。②扩展性差。由于簇头与基站采取的是单跳的通信方式，使其不适合大规模网络的应用。③适应性差。无线传感器网络的应用场合多样，每种应用的要求可能完全不同。全网几乎统一的采样、传输周期使其不能适应现场应用的复杂环境，降低了算法的实际应用意义。

1.2 ACPSEB-LEACH协议

ACPSEB-LEACH协议节能思想是：依据实际感知信息特点，抑制节点数据发送量，从而造成各类节点之间以及较远地区的同种节点之间的能耗差异，以此差异来进行簇头、成簇优化。实现网络能量均衡，延长网络生存时间。

在ACPSEB-LEACH协议中：在每一个簇头选举开始阶段，所有节点都是普通节点。这里，对于所有节点引入节点活跃度L（i）表示节点i的前一段时间的总体活跃程度、引入AL（i，r）∈（0，1］表示节点第r轮当轮的活跃度。当AL（i，r）为1时表示节点处于最活跃阶段，每一次属于自己的时隙该节点都上交数据包；该值越小表示节点越不活跃，有部分属于自己的时隙该节点并未选择与簇头进行通信，从而节约了能耗；0表示节点完全不活动，即代表节点已经死亡。

ACPSEB-LEACH协议同样分三个部分：①簇头选举；②簇的形成；③数据传输。

1.2.1 簇头选举

ACPSEB-LEACH的簇头选举分为两阶段：第一阶段是临时簇头选举；第二阶段是最终簇头选出。

阶段一：临时簇头选举。

选举时，每个存活节点产生一个介于0和1之间的随机数，如果这个数小于阈值T（n），该节点成为簇头。这里，我们使用上文中提到的节点活跃度L（i）作为参数，构建一个修正函数G（n，r）对T（n）进行修正，如式（2）所示。

其中G(n,r)计算方法如式（3）所示。

其中Lavg表示全局节点平均活跃度，a、b均为可调整变量。引入G（n，r）的目的是使得高活跃度节点当选簇头大大降低，低活跃度度阶段当选簇头节点概率大大增加，从而平均能量消耗，延长网络存活时间，使得第一个死亡节点的时间得到延后。对于节点活跃度有两种设定方法：①在网络的初始部署阶段，依据各种节点采集数据的现实需求与相关设计规范，可以对各类节点的采样、发送周期进行区分设计，依据设定好的发送周期计算出固定的节点活跃度。②无法明确各类采集数据的具体要求时，也可以全网采用统一的最小采样、通信周期，即全部节点初始活跃度为1，依据本文中的算法进行自我调整。

阶段二：最终簇头选出

由于引入了修正函数，可能会出现簇头过密集的现象，前期低活跃度节可能会集体当选簇头、后期前几轮未当选的高活跃度节点也会出现同时当选的情况，因此在临时簇头选举之后引进竞争半径Rc（i）来进行簇头调整，以确定最终簇头，只有在竞争半径Rc（i）以内的节点才能接收到该临时簇头的当选信息。Rc（i）的计算［4］如式（4）所示：

其中，S为该区域的面积，kopt为最佳簇头数目，Lavg表示全局节点平均活跃度。

节点i当选为临时簇头后，按如下步骤进行调整：①依据公式（4）计算自身竞争半径Rc（i）。②若临时簇头i收到临时簇头j的当选消息，判断两者之间的距离d（i，j）与自身竞争半径Rc（i）之间的关系。若Rc（i）＜d（i，j）临时簇头i将退出竞选，发送退出竞选消息。③调整之后，未退出的临时簇头当选为正式簇头，向以自己为圆心，竞争半径为Rc（i）的圆形区域广播当选消息，接收其他节点的加入请求。

通过以上方法，在出现簇头竞争区域相冲突时可以保证高活跃度临时节点总是收到低活跃度节点的当选消息，那么高活跃度节点将向外发送退出竞选消息，自动成为普通节点，就大大降低了高活跃度节点的能量消耗。

1.2.2 簇形成阶段

高活跃度节点当选簇头后，其能量消耗非常快，为了平衡全局能耗，延长网络存活时间，要尽量延长高活跃度节点的存活时间，因此普通节点接收到正式簇头后，综合考虑距离、活跃度、剩余能量等因素选择最佳的簇头加入。对于节点i，接到正式簇头j的当选通知后，计算自己加入该簇的成本C（i，j），选择成本最小的簇头加入。C（i，j）计算方法如式（5）所示：

其中w为可调节权重值，d（i，j）表示节点i到节点j之间的距离，d（j，Base）表示节点j到基站的距离。由公式可以看到，这样的选择方法可以降低远离基站且高活跃度节点的簇成员数进而降低其能耗延长其存活时间；同时又考虑到节点i与簇头j之间的距离，使得簇成员得到合理的分配。

所有簇成员加入后，簇头为所有簇成员分配TDMA时隙并以广播的方式通知各成员。

1.2.3 稳定阶段

簇形成之后，协议运行进入稳定阶段。在该阶段，普通节点按一定的周期采集信息发送给簇头节点，簇头节点将数据压缩、融合后传送给基站。采集、传输这两步骤都是以周期为间隔的，即信息采集周期Ts以及信息发送周期Tc。为了保证数据的实时性，采集到的数据应该保证能在下一个时隙发送出去，在LEACH协议中，Ts与Tc是相等的。

在本文所提出的ACPSEB-LEACH协议中，提出了簇内可变通信周期策略即Ts与Tc不一定相等。节点并不是每个时隙都与簇头进行通信，以减少数据的发送量。对于簇成员节点i，Ts（i）与Tc（i）的确定方式如下：

令Tc(i)=k×Ts(i),k=1,2,3…kmax

①节点每发送一次数据，k自动增加1，若节点两次采集的数据不相同，k复位为1。

②节点发送数据的条件：节点两次采集的数据不相同或者Tc（i）超时。

③每次变更通信周期Tc，簇成员都应该在新的通信周期生效前及时通知簇头节点。簇头节点在接到其成员节点i的数据后将其保存。在Tc的持续时间内，如果节点i不发送新的数据，簇头默认使用节点i上次传递过来的数据；如果节点i发来新的数据，则更新数据及对应的簇内通信周期。依据这样的策略，可以依据情况决定是否发送数据、多长时间发送一次，节约了节点能量。由于每个节点都知道自己在当轮的各个簇内通信周期及持续时间，那么在每次发送数据包大小都相同的情况下，很容易得到当轮的数据发送总量。最活跃的节点每次数据采集后都执行数据发送，假设它的数据发送量为D，对于其他次活跃节点来说，在每一轮结束阶段，自己的数据发送量D（i，r-1）与D之间存在以下关系：

AL（i，r-1）表示节点i在第r-1轮的活跃度。因为节点的能量消耗是和相对长时间的节点活跃度相关的，所以对AL（i，r-1）进行算术平均，得到反映前一段时间的节点活跃度L（i），计算公式如下：

依据得到的L（i）即可在下一轮开始时，将其带入式（3）中，以达到优化簇头选举，平衡能量消耗的目的。

2 实验测试与分析

2.1 应用场景假设

由于传感器网络具有很强的应用相关性，不同应用中的路由协议可能差别很大，没有一个通用的路由协议［14］。研究无线传感器网络路由协议不可忽略其应用场景。无线传感器网络的应用场合多样，每种应用的要求不尽相同。在多种传感器同时采集的情况下，除了要解决网络能耗等传统问题还要要面对更为复杂的情况：①为了延长网络生存时间，尽可能地保证采样精度的情况下应尽量延长采样周期［15］，每一种数据的要求可能不同，LEACH等协议难以满足这种多样需求。②传感器采集的同一种信息数据在一段时间内可能是完全相同的，重复的传输浪费系统资源。③对于一个多类型信息采集系统，任何一种信息的缺失都会给用户带来巨大的麻烦。

本实验参照实际采集数据的结果，在此基础上进行模拟。依据实验室现有物联网设备，完成了实际数据的采集。使用了实验室中的三种传感器，采集了光照、温度及湿度三种信息。本次采集所使用的无线传感器节点是CC2530节点，在TinyOS系统环境下，实现数据采集功能及数据转发功能。光照、温度及湿度数据的采集如图1、图2所示。

可以看到，实际采集到的数据都有浮动期和稳定期。在实际采集时发现，在一段时间内，采集到大量的相同数据。所以，依据数据采集的经验，对于本文实验，假设监测区域内需要采集的物理量在每一轮内随采集次数count变化示意图如图3所示。模拟数据1、3代表部分变化部分恒定的物理量，数据2代表一直变化的物理量，数据4代表绝大部分时间恒定数值偶尔波动的物理量。由于节点活跃度L（i）衡量标准是数据的变化，所以以上四种情况基本可以涵盖大部分情况。

图1 光照数据采集

图2 温度及湿度数据采集

图3 信号模拟示意图

仿真实验设定对一个边长为200 m的正方形区域内的4种物理信号进行周期性同时采集。设采集周期为t，每一轮的采集次数为count，则每一轮的总时长为Tr=t*count。基站位于区域中心位置，如图4所示。

图4 应用场景示意图

因此，我们布置4种传感器节点分别采集以上四种模拟信息。假设每种节点的覆盖度相同，每一种传感器个数为200，网络总的传感器节点个数N=800。所有节点初始活跃度都设为1。

2.2 网络通信模型

根据WSN研究中的常见假设，本文中的网络模型作如下假设［16-17］：①每个节点都具有相同的计算能力、通信能力，均具备数据聚合的能力。②若已知发送方的发射功率，接收方可以根据信号的强度计算二者间距离的近似值。③节点的最大发射功率是有限的，节点可以自由调节发射功率。④节点间的链路是对称的，他们以相同的传输功率进行通信。⑤传感网络各节点的时间是同步的，有可靠的时间同步机制。⑥基站可以能够和所有节点进行通信。簇头与基站之间进行单跳或多跳方式进行通信。本文统一采用单跳形式。

2.3 能耗模型及参数选择

无线传感网络中，节点的能耗大部分来自于数据的发送接收，少部分来自于发射电路损耗和功放损耗。本文采用与文献［16］相同的的无线通信能耗模型：

式（8）表示节点发送l比特数据到距离d的接收者的能量消耗，式（9）表示接收l比特数据的能量消耗。Eelec表示发射电路的能量损耗，当传输距离d小于阈值d0时，采用自由空间模型，εfs表示功放所需的能量。当传输距离d大于等于阈值d0时，采用多路径衰减模型，εmp表示在该模型下功率放大所需能量。

本次实验中采用的各参数值如下［4］：所有节点统一初始能量，节点初始能量E0=0，Eelec=50 nJ/bit，εfs=10 pJ/（bit/m2），d0=87.7，εmp=0.001 3 Pj/（bit/m4），p=0.05。

数据融合的能耗为：

对于本文中的场景，M=200。文中提到的w，a，b依据经验值设定：w=0.8，a=2.8，b=5。

2.4 性能分析与比较比较

本文采用Matlab仿真软件对LEACH，EECS，ACPSEB-LEACH在上述的环境下进行仿真比较。由于采用簇内通信周期可变策略，使得实际发送数据的减少，从而节省能量，所以对所有协议都采取这样的发送策略进行比较。

实验比较主要依据以下几点性能：①网络生存周期；②节点平均剩余能量，该参数表征全局能量利用效率；③簇头数据发送量，簇头发给基站的数据越多，监测到的信息越全面；④死亡节点构成，参与传感的不同类型网络是否基本同时开始死亡。

2.4.1 网络生存周期及死亡节点实验

网络的生存周期是本最重要的一个指标，三种算法的实验结果如图5所示。

从图5可见，ACPSEB-LEACH协议的网络生存周期最长，EECS其次，LEACH最差。

图5 网络生存周期示意图

LEACH协议由于没有依据节点活跃度来采取相应的节能措施，同时随机选取簇头的方式使得簇头分布不合理不可控，使得高活跃节点过早死亡，曲线横向跨度非常大，实际上是不同活跃度的依次死亡造成的，网络拓扑在高活跃度节点死亡后已经不完整，后期采集上的数据意义已经不大。LEACH协议的节点死亡细节如图6所示。

图6 LEACH中各组节点死亡示意图

EECS比LEACH略有提高，虽然采取了一些能量平衡的措施，但是在本文的实验环境中并没有太好的效果，也存在与LEACH类似的问题。

对于ACPSEB-LEACH协议，从图5可见，首个死亡节点大幅度延后，1600轮以后节点死亡曲线上升很快，表明网络中的节点在快速死亡，整个网络的能耗非常平均，ACPSEB-LEACH中各组节点死亡示意图如图7所示。

图7 ACPSEB-LEACH各组节点死亡示意图

实验结果说明，ACPSEB-LEACH协议的网络生存时长效果最好，各组节点死亡时间基本一致，各类型节点之间能量消耗比较均衡。

2.4.2 节点平均剩余能量实验

节点平均剩余能量是衡量网络中节点能量利用效率的一个标准，剩余能量越多，说明每一轮节点的消耗越少，这样也就能够更好的延长传感网络的生命周期。图8表示的是三种算法的节点平均剩余能量。

从图8中可以看出。EECS与本文提出的ACPSEB-LEACH算法有一个交叉点。本文提出的ACPSEB-LEACH协议的平均剩余能量在交叉点以前都要好于LEACH及EECS的效果，在交叉点以后低于EECS。出现这种情况是因为在交叉点附近，EECS与LEACH协议中的高活跃节点基本已全部死亡，留下的低活跃节点能量消耗非常少。这说明ACPSEB-LEACH协议的能量均衡，利用率高，算法收敛性快的特点。

图8 节点平均剩余能量

可见，在有效的网络生存周期内，本文提出的ACPSEB-LEACH协议的平均剩余能量要高于其他两种。

2.4.3 簇头数据发送量实验

考虑到传感网络的应用环境，簇头向基站发送的数据量也是一个重要的指标，对比三种协议的基站数据接收量，如图9所示。

图9 簇头发送数据量

由图9可以看到，在采用簇内可变周期数据发送策略的情况下，ACPSEB-LEACH协议依然可以传送大量数据包到达基站，同时保证了采集的数据量和能量的节约。

综上所述，ACPSEB-LEACH协议在网络生存周期，节点平均剩余能量，发送数据量上都有一个很好的效果，对比LEACH及EECS有很大的提高。

3 总结

本文考虑了一种接近真实的多种数据同时采集的网络环境，提出一种适用于周期性、长期性信号采集应用的低功耗路由协议ACPSEB-LEACH。该协议从LEACH协议的稳定阶段及成簇阶段对LEACH协议进行改进，运行过程中能够自我调整节点数据发送周期，从而满足低功耗与信息感知的双方面要求。仿真表明，改进后的协议在延长网络生存周期、平衡全局能量上有很好的效果。更为重要的是，本文思路为以后进一步对无线传感网络低功耗路进行研究提供了一个科学地、可供参考的方法，此策略在多跳传输及大规模网络扩展方面依然有极大的改进空间。

［1］李建中，高宏.无线传感器网络的研究进展［M］.计算机研究与发展，2008，45（1）：1-15.

［2］李芳芳，王靖.一种基于LEACH协议的无线传感器网络路由算法［J］.传感技术学报，2012，25（10）：1445-1452.

［3］唐勇，周明天，张欣.无线传感器网络路由协议研究进展［J］.软件学报，2006.3：410-412.

［4］Heinzelman W B，Anantha P Chandrakasan，Hari Balakrishnan.An Application-Specific Protocol Architecture for Wireless Micro⁃sensor Networks［C］//Proc of the 33rd Hawaii International Con⁃ference on System Sciences，2000：3005-1130.

［5］Younis O，Fahmy S.HeeD：A Hybrid，Energy-Efficient Distribut⁃ed Clustering Approach for Ad-Hoc Sensor Networks［J］.IEEE Trans on Mobile Computing，2004，3（4）：660-669.

［6］陈贵海，李成法，叶懋，等.EECS：一种无线传感器网络中节能的聚类方案［J］.Journal of Frontiers of Computer Science and Technology，2007，1（2）：1673-9418.

［7］Lindsey S，Raghavendra C.PEGASIS：Power-Efficient Gathering⁃in Sensor Information Systems.IEEE Aerospace ConferencePro⁃ceedings，2002.

［8］李成法，陈贵海，叶懋，等.一种基于非均匀分簇的无线传感器网络路由协议［J］.计算机学报，2007（1）：28-36.

［9］Manjeshwar A，Agrawal D P.TEEN：A Routing Protocol for En⁃hanced Efficiency in Wireless Sensor Networks.Proceedings of the 15th Parallel and Distributed Processing Symposium，2001.

［10］Ravi Kishore Kodali，Naveen Kumar Aravapalli.Multi-Level LEACH Protocol Model Using NS-3［A］.2014 IEEE International Advance Computing Conference（IACC），2014：375-380.

［11］Sapna Gambhir，Nida Fatima.Op-LEACH：An Optimized LEACH Method for Busty Traffic in WSNs［A］.2014 Fourth International Conference on Advanced Computing&Communication Technolo⁃gies，2014：222-2229.

［12］马建乐，杨军.基于位置和剩余能量的局部集中式LEACH算法研究［J］.传感技术学报，2013，26（8）：1147-1151.

［13］陈晓娟，王摇卓，吴摇洁.一种基于LEACH的改进WSN路由算法［J］.传感技术学报，2013，26（1）：116-121.

［14］余成波，李洪兵，陶红艳.无线传感网络实用教程［M］.北京：清华大学出版社，2012.4.

［15］洪锋，褚红伟，金宗科，等.无线传感器网络应用系统最新进展综述［J］.计算机研究与发展，2010，47（Suppl）：81-87.

［16］Intanagonwiwat C，Govindan R，Estrin D.Directed Diffusion：A Scalable and Robust Communication Paradigm for Sensor Net⁃works.In Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking（MOBICOM），August，2000：56-67.

［17］苏金树，郭文忠，余朝龙，等.负载均衡感知的无线传感网络容错分簇算法［J］.计算机学报，2014，37（2）：445-456.