无线传感器网络的LEACH协议的改进与实现

刘得兵，梁刚

（四川大学计算机学院，成都 610065）

无线传感器网络的LEACH协议的改进与实现

刘得兵，梁刚

（四川大学计算机学院，成都 610065）

针对LEACH协议簇头分布不均匀和网络能量不均衡而导致网络生命周期短的问题，提出一种改进方法。该方法在簇头选举阶段，引入能量因子和位置因子来平均网络中节点的剩余能量；在数据传输阶段，引入新的数据融合机制来降低网络中的传输能耗。通过NS2仿真实验证明，与原协议相比，改进后的协议在单位时间内网络的平均能耗低于原来的50%，网络的生命周期延长114%。

无线传感器网络；LEACH协议；簇头选取；能量因子；位置因子

0 引言

随着科学技术的飞速发展，人类正处于信息时代，而作为下一代互联网中至关重要的技术——无线传感器技术，也得到了飞跃式的发展。无线传感器网络（Wireless Sensor Network，WSN[1～4]）是一种全新的信息获取平台，能够实时监测和收集分布在网络区域内的各种检测对象的信息，然后通过无线收发装置将这些信息传输给汇聚节点，以实现对指定范围内目标的检测与跟踪，具有展开迅速，抗毁性强等特点，有着非常广阔的应用前景。

近年来，随着人们对无线传感器网络研究的不断深入，使得无线传感器网络得到了快速发展，也产生了越来越多的实际应用。我们可以大胆地预见，将来无线传感器网络将无处不在，将完全融入我们的生活[4～10]。

无线传感器网络最突出的特点是节点能量有限且不可再生[11]，所以降低网络能耗，延长网络生命周期显得尤为重要。正因为如此，路由协议成为了当前研究无线传感器网络的一大热点[12～13]。与有线网络相比，无线传感器网络没有实际的物理基础设施支持，而且网络的工作都是无人工干预的，其通信拓扑是动态自组织的。因此，传统的路由算法对无线传感器网络并不适用，必须结合无线传感器网络的特性来研究新的路由协议[1，14～16]。

低功耗自适应分层型协议（LEACH）是针对无线传感器网络提出的第一个分层型路由协议。它保证了网络中每个节点都有相等的概率当选为簇头，从而使得网络的能量较为均匀地消耗。但是由于簇头选举具有很大的随机性，不能保证簇头的均匀分布，而且当网络中有节点提前死亡，会造成网络路由空洞，影响通信[12，17～19]。针对LEACH协议的不足，一些以LEACH协议为基础的改进协议相继被提出，如基于能量效率的阈值敏感传感器网络协议（Threshold Sensitive Energy Efficient Sensor Network Protocol，TEEN）[20]，PEGASIS（Power-Efficient Gathering in Sensor Information Systems）[21]，混合节能分布式聚类协议（Hybrid Energy-Efficient Distributed Clustering，HEEN）[22]等，但是这些方法仍然存在因网络能量不均衡，簇头分布不均匀而造成的网络生命周期短的问题[4，17]。

本文提出了一种改进方法。首先，在簇头选举阶段，对LEACH协议的簇头选择算法进行改进，从而保证算法在进行簇头选择时充分考虑备选节点剩余能量和其网络中的位置两大因素，使得剩余能量越高、越靠近最佳簇头位置的节点当选簇头的概率越大。其次，在数据传输阶段，引入新的数据融合机制，减少传输给基站数据中的冗余信息，从而降低网络中的传输能耗。通过以上改进，能平均网络中节点的剩余能量，避免网络中的节点过早死亡；同时也使得被选出的簇头节点能相对均匀地分布在网络中。最终达到降低在单位时间内网络的平均能耗和延长网络生命周期的效果。

1 LEACH协议

LEACH协议[23]是一种自适应分簇拓扑算法，其核心思想是通过等概率地随机选出簇头节点，然后通过选出的簇头节点来将整个网络组织成簇结构。每个簇只有一个簇头，簇内其他节点称为非簇头节点，非簇头节点只与所在簇的簇头节点通信。簇头节点将簇内所有非簇头节点的监测数据经过数据融合处理后传输给Sink节点（也称作基站）。由于簇头节点除了要建立簇结构，还要收集并处理簇内非簇头节点的监测数据，因此会消耗更多能量。为了避免出现节点因长期担任簇头而过早耗尽自身能量而死亡，LEACH协议采用轮转的方式来选举簇头节点，从而让所有节点都有机会当选簇头，而已担任过簇头的节点只有在所有节点都已担任过簇头后才有机会再次成为簇头，这样保证了网络中节点的能量均匀消耗。

LEACH协议是按轮（rounds）周期性地执行，每轮分为网络的成簇阶段和稳定工作阶段。在成簇阶段，随机选出簇头节点，其他节点选择离它最近的簇加入；在稳定工作阶段，簇头节点收集簇内所有非簇头节点的监测数据，然后对其进行数据融合处理并将结果发送给基站。

（1）网络的成簇阶段

LEACH协议中的所有传感器节点是同构的，因此所有节点的初始能量相同，为了使得网络中节点能量消耗平衡，期望每轮选出Popt·N个簇头节点，其中，N为网络节点总个数，Popt为期望簇头个数在网络节点中所占的比例（通过大量的实验，当Popt=5%时，网络性能最优[24]）。每个节点通过公式（1）计算出其阈值T（si），同时产生一个随机数random（0＜random＜1）。当random＞T（si）时，该节点当选为簇头。

式中，r为当前轮数，G为在最近r×mod（1/Popt）轮中没有当选簇头的节点集合。

当节点当选为簇头节点后，就使用TDMA广播ADV消息（Advertisement Message）通知其他节点自己是簇头节点。每个非簇头节点根据接收到的ADV消息信号的强弱来判断自己与簇头节点之间的距离，然后选择最近的簇加入，并发送消息通知该簇头，簇头节点接收到消息后就将该节点加入自己的簇成员列表。当所有节点都加入了相应的簇，网络的成簇阶段就结束了，将进入网络的稳定工作阶段。

（2）网络的稳定工作阶段

簇头节点建立一个TDMA调度来防止簇内节点在数据传输过程中发生冲突，簇内节点接收到簇头节点发送的TDMA调度方案后就可以进行数据传输了。

TDMA调度使得每个非簇头节点只能在指定的时间间隙内发送数据。非簇头节点在没有数据要传输时，将会进入休眠状态以节省自身能量，而簇头节点一直保持工作状态来接收簇内节点的监测数据。簇头节点一旦接收完所有簇内节点的监测数据，就对所接收到的所有监测数据进行数据融合处理，然后将处理的结果传输给基站。

2 LEACH协议的改进

2.1 簇头选举改进方案

（1）能量因子Erate

LEACH协议在簇头选举保证了每个节点都有机会成为簇头，但是未将节点当前能量考虑进去，很有可能使得能量非常小的节点当选为该轮的簇头。这样就可能出现簇头无法完成对该簇的正常管理，或者无法对接收到的数据进行综合分析处理，从而造成该簇内的通信无法正常进行。针对这一问题，在改进的簇头选举算法中，通过引入能量因子实现将节点的当前能量作为簇头选举的一个因素。

能量因子Erate的计算式如（2）式所示：

式中，E0为节点的初始能量值，Ecur为节点的当前能量值，Eaver为当前网络中节点的平均能量值。

（2）位置因子Drate

LEACH协议在簇头选举过程中也没考虑节点的位置，有可能出现所选出的簇头节点过于集中或者过于分散，从而使得簇内节点与簇头节点之间或者簇头节点与基站节点之间的传输能耗过大，这样就会造成节点能量的极大浪费。针对这种情况，在改进的簇头选举算法中，通过引入位置因子实现将节点的位置作为簇头选举的一个因素。

如图1所示，为了便于说明位置因子的定义，首先将研究的无线传感器网络的拓扑区域虚拟成一个能覆盖所有节点的正方形区域，其边长记作len_topo，A点的坐标为（min_x，min_y），len_topo可由公式（3）求得，其中min_x、max_x表示所有传感器节点（不包括Sink节点）的坐标中最小和最大的横坐标，min_y、max_y表示所有传感器节点（不包括Sink节点）的坐标中最小和最大的纵坐标。

图1 位置因子说明图

将该正方形区域分为四个大小相等的小正方形区域，这四个正方形区域的中心点称为最佳簇头位置。若被选簇头的位置是在最佳簇头位置的附近，这样簇头将较为均匀地分布在网络中。也就是被选簇头的节点离其所在区域的中心点距离越小，最终所有的簇头将会较为均匀地分布在网络中。通过公式（4）给出位置因子的定义，其中radius表示小正方形区域的外接圆的半径，mdsi表示节点si到其所在区域中心点的距离，mdaver表示所有节点到其所在区域中心点的平均距离。

表1 关键点坐标值

由此，可以得到节点si的映射距离（即Ostd和si'之间的距离）的计算公式如公式（6）。

（3）改进的簇头选举算法

改进的簇头选举算法并不改变原协议的簇头选举流程，只是在计算节点的阈值时将节点的当前能量和位置通过能量因子和位置因子加入到计算中来，因此对于节点si将采用公式（7）来计算其阈值：

式中，Popt为期望簇头个数在网络节点中所占的比例，r为当前轮数，G为在最近r×mod（1/Popt）轮中没有当选簇头的节点集合，Erate为节点的能量因子，Drate为节点的位置因子。

新的簇头选举算法不仅保证了每个节点都有机会成为簇头，也对参与簇头选举的节点的剩余能量和位置进行了筛选。通过公式（7）可以看出，只有当Erate× Drate＞1时，对该节点当选簇头起促进作用，当Erate×Drate＜1时，对该节点当选簇头起阻碍作用。改进后的协议使得当前能量越大，离最佳簇头位置越近的节点当选簇头的概率越大。从而达到均衡网络节点剩余能量，使得簇头能相对均匀地分布在网络中的目的。

2.2 数据通信改进方案

在簇头选举完毕，簇的建立已经完成的情况下，开始数据通信稳定阶段。此阶段的数据融合在原协议中是由簇头节点担当的，这样簇头不仅要承担簇管理的任务，还要承担该簇中的数据处理工作，这样会使得簇头节点的能量消耗过大。现在通过引入文献[19]中的数据融合方案来对其进行改进，以便分担簇头节点的负担，减少它的能耗，进一步均衡网络节点的剩余能量。

改进方法中，在簇内重新选择一个除簇头节点外能量最大的节点（又称为数据簇头）来担当本簇内的数据融合工作。数据簇头负责接收簇内节点发送过来的监测数据，并去除其中的冗余信息，然后将经过数据融合处理的数据发送给基站。基站会接收数据簇头发送来的监测数据，并且当有新的监测任务时，基站会将其分配给簇头节点，再由簇头节点分配给簇内节点。这样在一个簇内就有两个领导，一个是簇头节点，除了负责簇的构建工作之外，还会将基站分配的监测任务向下传达给簇内节点；另一个是数据簇头节点，负责收集簇内节点的监测数据，并对其进行数据融合处理，然后向上发送给基站。这样能均衡簇头节点的能量消耗，从而达到平衡网络中节点的剩余能量的目的。

2.3 改进后协议的流程图

采用改进后的簇头选举算法和数据融合机制的协议的流程图如图2所示。

在簇建立阶段，根据改进的簇头选举算法选出网络中的簇头节点，节点当选簇头后就会向全网发布其当选簇头的消息，非簇头节点会根据接收到的消息信号的强弱来选择离它最近的簇加入。当所有节点都加入了相应的簇，就结束成簇阶段，网络将进入稳定工作阶段。

在稳定工作阶段，当有新的监测任务时，簇头节点会唤醒处于休眠状态的簇内节点，并向其分配监测任务。簇内节点会根据监测任务收集数据，然后将数据发送给簇内的数据簇头节点，完成了监测任务的簇内节点会进入休眠状态。数据簇头会将接收到的所有数据进行数据融合，然后发送给基站。

图2 改进后协议的流程图

3 仿真实验结果

100个传感器节点随机分布在100m×100m的范围内，基站坐标取（50，175），节点的初始能量相同，且为2J。同时取min_x=min_y=0，len_topo=100。采用NS2网络仿真工具[25]对LEACH协议和改进后的协议进行了仿真实现，仿真结果如下（文中的仿真结果是100次随机实验结果的平均值）。

3.1 网络生存周期对比

网络生存周期对比图如图3所示，该图中细的曲线代表的是LEACH协议的节点生存周期，粗的曲线代表的是改进后的协议的节点生存周期。从图中可以看出，改进后的协议网络的生命周期延长了，原有协议大约在480s的时候，网络节点整体死亡；而改进后的协议大约在1030s的时候，网络节点才整体死亡，网络的生命周期延长了1倍。

在静态的网络中，当失效的节点数量超过30%时，网络的性能就会变得非常差[26]，因此我们把网络从开始到失效节点数量不超过30%的这段时间称为网络的最佳生命周期。从图3中，可以看出，网络的最佳生命周期从改进前的390s延长到了改进后的880s，提高了接近1.25倍。

图3 网络生存时间对比图

3.2 网络能耗对比

网络能量消耗如图4所示，图中上面细的曲线代表原有的LEACH协议，下面的粗的曲线代表改进后的协议。从图中可以看出，改进后的协议在网络能耗方面明显优于原有的协议，这表明对LEACH协议的改进达到了均衡网络能量，降低单个节点在单位时间内的能耗的目的。

但是改进后的协议在560s～600s这段时间，能量消耗过大，造成这种情况的原因可能有以下两方面：①节点的动态分簇，形成的簇头节点过多，在数据通信过程中发生碰撞，造成能量消耗过大。②该时间段没有节点当选为簇头，这样网络中的所有节点就不得不将其收集到的数据直接传输给基站，从而造成了网络传输能耗过大。

图4 网络能耗对比图

4 结语

本文在分析LEACH协议算法缺点的基础上，对原有的算法进行了改进。在簇头选举阶段，结合节点的当前能量和位置进行簇头选举。在数据传输阶段，将原本由簇头节点承担的数据融合工作转交给簇内除簇头之外的最大能量的节点。通过以上两方面的改进，新协议不仅降低了网络能耗，还平衡了网络中节点的剩余能量，从而延长了网络的生命周期。但是原协议中就存在的某些时间段簇头数量过多或者没有节点当选簇头的问题仍然没有解决，如何解决该问题将是进一步研究的重点。

[1] Akyildiz IF，Wei LS，Sankarasubramaniam Y，Cayirci E.A Survey on Sensor Networks[J].Communications Magazine，IEEE，Volume: 40，Issue:8，2002，8:102～114

[2] AkyildizW.S，Y..Sanakarasubramaniam Y，et al.Wireless Sensor Networks:A Survey[J].Computer Networks，2002，38（4）:393～422

[3] David E C，Wei H.Wireless Sensor Networks[J].Communications of ACM，2004，47（6）:30～33

[4] 黄海平，沙超，蒋凌云等.无线传感器网络技术及其应用[M].北京：人民邮电出版社，2012

[5] 任丰原，黄海宁，林闯.无线传感器网络[J].软件学报.2003，14（7）:1282～1291

[6]于海斌，曾鹏.智能无线传感器网络系统[M].北京：科学出版社，2006

[7] 刘君华.智能传感器系统[M].第二版.西安：西安电子科技大学出版社，2010

[8] Atzori L，Lera A，Morabito G.The Internet of Things:A Survey[J].Computer Networks，2010，31（5）:1～19

[9] Welbourne E，Battle L，Cole G，et al.Building the Internet of Things Using RFID:the RFID Ecosystem Experience[J].IEEE Internet Computering，2009，13（3）：48～55

[10] Broll G，Rukzio E，Paolucci M，et al.PERCI:Pervasive Service Interaction with the Internet of Things[J].IEEE Internet Computing，2009，13（6）:74～81

[11] CHENG Chitsun，CHI K T，FRANCISC M L.A Delay-Aware Data Collection Network Structure for Wireless Sensor Networks[J]. IEEE Journal，2011，11（3）:699～710

[12] 李辉，彭珍瑞，董海棠.一种LEACH协议的改进方法[J].电子科技，2014，27（5）:172～178

[13] 俞黎阳.无线传感器网络网格状分簇路由协议和数据融合算法的研究[D].上海：华东师范大学博士学位论文，2008

[14] Estrin D，Govindan R，Heidemann J，et al.Next Century Challenges:Scalable Coordination in Sensor Network.In:Proceedings of the 5th ACM/IEEE International Conference on Mobile Computing and Networking.Seattle:IEEE Computer Society，1999（6）:263～270

[15] 马祖长，孙怡宁，梅涛.无线传感器网络综述[J].通信学报，2004，25（4）:114～124

[16] 史美林，英春.自组网路由协议综述[J].通信学报，2001，22（11）：93～103

[17] 王振飞，纪越峰.基于能量均衡策略的无线传感器网络LEACH协议改进[J].东南大学学报（自然科学版），2008，38 Sup（I）:262～270

[18] 王伟超，代增全，徐启建.LEACH协议簇头选择算法的改进[J].无线电工程，2010，40（3）:1～3

[19] 韦宏利，方玉杰.LEACH协议算法改进及仿真[J].西安工业大学学报，2010，30（6）:570～573

[20] Manjeshwar，A，Agrawal D P.TEEN:A Protocol for Enhanced Efficient in Wireless Sensor Networks[C].In:Int'l Proc.of the 15th Parallel and Distributed Processing Symp.San Francisco:IEEE Computer Society，2001:2009～2015

[21] Liu T，Li.FPower-Efficient Clustering Routing Protocol Based on Applications inWireless Sensor Network[C].Proceedings 5th International Conference onWireless Communications.Networking and Mobile Computering，WiCOM 2009，2009

[22] Younis O，Fahmy S.HEED:A Hybrid Energy-Efficient Distributed Clustering Approach for Ad Hoc Sensor Neteorks[J].IEEE Trans. On Mobile Computing，2004，3（4）:660

[23] Heinzelman W，Chandrakasan A，Balakrishnan H.Energy Efficient Communication Protocol for Wireless Microsensor Networks.In: Proceedings of the 33rd Hawaii International Conference on System Sciences.Maui:IEEEComputer Society，2000.3005-3014

[24] Ahlswede R，CaiN，Li SY R，etal.Network Information Flow[J].IEEE Trans.On Inf.Theory，2000，46（4）:1204～1216

[25] 徐雷鸣，庞博，赵耀编著.NS与网络模拟[M].北京：人民邮电出版社，2003，11

[26] 陈良银，王金磊，张靖宇，王强，刘燕，殷锋，罗谦.低占空比WSN中一种节点休眠调度算法.软件学报，2014，，25（3）:631～641

Improvement and Implementation of LEACH Protocol for Wireless Sensor Networks

LIU De-bing，LIANG Gang
（College of Computer Science，Sichuan University，Chengdu 610065）

Aims at the problem of LEACH protocol which exists the uneven distribution of clusterheads and imbalance in energy leading to the short network lifetime.Puts forward an improved method,introduces the energy factor and location factor to average the residual energy of each node during the selection of clusterheads.And introduces a new data fusion mechanism to reduce the energy consumption for transmission during the data transmission.Comparing with the original LEACH by NS2 simulation,it shows that the average energy consumption in unit time of the improved one is lower than 50%,the lifetime is extended 114%.

Wireless Sensor Networks;LEACH Protocol;Select Cluster-Heads;Energy Factor;Location Factor

1007-1423（2015）06-0003-07

10.3969/j.issn.1007-1423.2015.06.001

刘得兵（1989-），男，安徽安庆人，硕士研究生，研究方向为网络信息安全

梁刚，男，硕士生导师，研究方向为网络安全与智能计算

2015-01-22

2015-02-10