基于LEACH的低能耗改进算法研究

曹喜珠，丁绪星，冯友宏，凌 敏，王再见

(安徽师范大学 物理与电子信息学院，安徽 芜湖 241000)



基于LEACH的低能耗改进算法研究

曹喜珠，丁绪星，冯友宏，凌 敏，王再见

(安徽师范大学 物理与电子信息学院，安徽 芜湖 241000)

为了解决LEACH协议在簇头分布不均和能量消耗集中等方面的缺陷，提出一种基于LEACH协议的距离调控改进路由算法LEACH-D。在簇头选取阶段，充分考虑簇头选择的个数和相对分布位置；在簇形成阶段，采用节点维护的路由属性表和分布的密集程度及相对距离确定入簇方式。仿真结果表明，相较于LEACH算法，改进后的算法有效均衡了网络能耗，延长了网络生存周期。

LEACH协议；路由属性表；无线传感网络；均衡能耗

0 引言

无线传感器网络(Wireless Sensor Networks,WSNs)是由大量的静止或移动的传感器以自组织和多跳的方式构成的无线网络[1]。与传统无线通信网络不同，WSN中节点带宽、内存资源更为匮乏，在一些特殊场合其电池不能更换和有效补充，进而直接影响感知网络的生存周期和传输的信息质量，基于此，感知网络中节点通信协议应该能有效地利用节点有限的能量，尽可能地延长网络的生存周期。其中经典的LEACH(Low Energy Adaptive Clustering Hierarchy)协议是应用于无线传感网络中的一种典型的层次型路由算法，与一般的平面多跳路由协议和静态分层算法相比，该算法可以将网络生命周期延长15% 以上[2-3]。

1 LEACH算法

LEACH算法是层次型路由算法的基础，提出将网络分成若干个簇，每个簇选取簇头节点汇聚簇成员信息，融合后发送至网络的BS(Base Station)节点[4]。该算法仍存在一些不足之处，如：LEACH路由算法中簇头的产生方法在数量上常常呈现不稳定状态；LEACH路由算法中簇头的分布往往不均匀,失去了分层的意义[4];LEACH路由算法簇头的选择没有考虑节点自身的剩余能量[5-6]；LEACH路由算法采用简单的分层方式，这样限制了网络的规模扩展[7]。LEACH路由算法中的成簇阶段没有考虑节点传送信息的相关性和冗余性[8-9]。

文献[10]中提出将蚁群算法应用到LEACH协议中，通过动态改变成簇半径，以及簇头间通信采用蚁群算法；文献[11] 提出将网络根据节点与sink节点的距离分为两层；文献[3]提出基于基站距离与基站方向的成簇路由算法。以上算法不同程度上降低了网络能耗，但是在整体网络的簇头分布随机性很大，同时存在簇头节点负荷比较大的问题没有有效解决，且在成员节点入簇阶段没有考虑成簇的成员节点之间的相对距离。

基于此本文算法具有如下的特点：① 在簇头产生阶段为每个传感节点分配选择簇头的参考半径；② 同时节点维护自身的路由属性表，候选簇头节点根据属性表判断是否可竞选簇头角色；③ 在节点入簇阶段，通过查询自身属性表选择不同的入簇方式；④ 充分考虑了普通节点信息的冗余性和相关性，为此采用休眠机制来降低信息的相关性；⑤ 簇头融合簇成员信息与基站通信，根据与基站之间的距离选择单跳或者多跳路由方式。

2 改进的算法

2.1 算法详述

LEACH算法在簇头产生阶段存在簇头分布集中，造成网络局部负载大等问题，本文算法的主要思想是选择位置分布相对均匀的簇头节点，同时优化分簇结构，从而平衡网络能量消耗，延长无线传感网络的寿命。该算法过程如下：

① 设置5%的网络节点数目作为阈值门限；

② 非簇头节点根据本文提出的属性表选择不同的入簇方式；

③ 处理本文定义的游离节点的入簇方式；

④ 为了降低信息采集的冗余性，根据周围是否有活跃节点来决定休眠还是激活采集并传输信息；

⑤ 对于远离基站节点的簇头采用多跳路由方式进行通信。

下面对于本算法中的关键部分进行说明：对于采用分簇路由方式的无线传感网络，簇头节点在网络通信中占据着非常重要的角色，因此簇头节点的选取和产生方式至关重要。如表1所示，本文算法中，网路各节点维护自身路由属性表。其中，字段ID表示该节点的唯一编号，在网络初始化时随机分配；字段Alive表示该节点是否为存活节点，取值为0(死亡)或者1(存活)；字段Sleep表示该节点是否为休眠节点，取值为0(休眠)或者1(活跃)；字段Head表示该节点是否为簇头节点，取值为0(否)或者1(是)，在网络初始化阶段，该属性统一设置为0；字段Active表示该节点在簇头选取阶段是否参与，取值为0表示该节点在本轮选取簇头阶段没有当选簇头或者没有收到簇头广播的消息，或者收到至少两个簇头节点广播的消息，为游离节点，取值为1表示该节点当选为簇头或者在参考范围内只接收到一个簇头广播的消息，该属性初始值为0；字段Cluster表示节点是否入簇属性，取值为0(未入簇)或者1(已入簇)，初始值为0。该路由属性表在网络初始化时候被写入初始值，在分簇建立阶段和稳定阶段被改写和读取。

表1 节点路由属性表

2.2 选取簇头阶段

为了避免簇头节点分布集中的情况，该阶段综合考虑簇头剩余能量以及簇头之间相对位置因素，采取局部集中原则选取簇头节点。对于节点数为N的无线传感网络，预设簇头节点的百分比为P，网络进行初始化后，BS根据式(1)通过广播的方式为每个节点分配分簇参考距离Rre，Active属性值为0的节点产生0～1之间的随机数，当该随机数小于式(1)设定的阈值，则当选为候选簇头节点；第一个当选为候选簇头的节点则为第一个簇头节点，该节点向周围广播消息并且将自身Head属性置为1，BS记录下簇头节点个数，同时在Rre半径内的节点接收到消息后将自身属性表的Active属性置为1，该节点在本阶段不参与簇头竞选。遵循该过程依次产生其他簇头节点，由BS控制本阶段产生簇头节点的个数。当簇头节点数达到N*P后，本轮簇头选取结束。式(1)中，S为无线传感网络的面积大小，N为网络中节点个数，P为节点成为簇头节点的百分比：

(1)

2.3 节点入簇阶段

由于在簇头产生阶段遵循每个簇头节点的参考半径范围内不产生其他簇头节点，则存在部分非簇头节点的参考半径内没有簇头节点，或者在参考距离内有多个簇头节点，称为活跃节点，如图1所示。对于路由属性表的Active属性为1的非簇头节点，选择参考距离内最近距离的簇头节点单播消息入簇，如式(2)，计算d最小的情况；对于Active属性为0的非簇头节点，在该阶段计算各自的入簇阈值Tclu，如式(2)，选择阈值Tclu最大的簇头节点入簇，即选择距离较近且剩余能量较高的簇头节点入簇。

(2)

式中，d为当前节点到簇头节点的距离，dmax为网络中任意节点间的最大距离值，Einit为节点的初始能量值，Ecur为节点的当前剩余能量值。

图1 节点入簇图

节点之间的通信 ：LEACH-D算法在簇内采取近距离内能量较低的节点轮流进入休眠状态，从而降低节点信息的冗余。簇头负责与基站的通信，当簇头离基站较远时，要以较大的功率发送数据，这会造成簇头节点能量的过快消耗。LEACH-D处理方法是，当簇头节点距离基站较近时，簇头节点直接与基站通信，当簇头节点距离基站较远时，簇头节点把融合后的数据发送到适宜的临近簇头节点，临近簇头节点再把数据转发给下一个适宜转发的簇头节点，以此类推，直到把数据交付给基站。

3 仿真分析

选择针对无线传感网络仿真的平台Atos-SensorSim，对本文算法和LEACH进行了对比仿真。在300m*100m环境中随机分布200个节点。仿真网络环境选择基站位于(150,50)和(300,100)两个位置的无线传感网络，参数设置如表2所示。

表2 仿真参数

3.1 基站位置位于(150,50)

3.1.1 网络生命周期

对该环境下，通过网络节点的存活数和分簇的轮数的关系，对LEACH算法和本文算法进行对比仿真，如图2所示。

图2 节点存活数-轮数

由图2可以看出，本文改进的LEACH分簇路由算法提高了节点的存活率，LEACH算法在20轮之前便出现节点死亡，改进算法在75轮以后出现；在轮数300之前，LEACH算法的节点存活率高于45%，本文改进的算法节点存活率高于60%，提高了15%。所以，在基站距离较近的随机分布无线传感网络环境中，改进算法提高了节点存活率，延长网络寿命。

3.1.2 网络能耗

同样对该环境下，通过网络总能耗和分簇的轮数的关系，对LEACH算法和本文算法进行对比仿真，如图3所示。

图3 网络总能耗-轮数

从图3 可以看出，本文算法在网络能耗的统计上低于LEACH算法，在轮数为30时，网络能耗节约2 000 J左右；在轮数150以后，相较于LEACH算法，本文算法平均降低网络能耗750 J左右。所以，在随机分布的无线传感网络中，本文算法通过平衡网络簇头节点的负载分配，能有效降低网络能耗。

3.2 基站位置位于(300,100)

3.2.1 网络生命周期

通过网络节点的存活数和分簇的轮数的关系，对LEACH算法和本文算法进行对比仿真，如图4所示。

图4 节点存活数-轮数

从图4可以看出， 相较于基站位于中心位置的环境，该环境下节点存活率降低，这也证明了LEACH协议在簇头节点与基站通信耗能多的不足。本文改进的分簇路由算法针对簇头与基站之间的通信处理方法提高了节点的存活率，LEACH算法在25轮以前出现节点的死亡，改进算法在75轮以后出现；在轮数为350之前，LEACH算法的节点存活率高于42%，本文改进的算法存活率高于60%，提高了18%。所以，在基站距离较远的随机分布无线传感网络环境中，改进算法能有效提高节点存活率，延长网络寿命。

3.2.2 网络能耗

通过网络总能耗和分簇的轮数的关系，对LEACH算法和本文算法进行对比仿真，如图5所示。

图5 网络总能耗-轮数

由图5可以看出，本文算法同样在网络能耗的统计上低于LEACH算法，在轮数为25时，网络能耗节约2 500 J左右；在轮数50以前，相较于LEACH算法，本文算法平均降低网络能耗2 250 J左右；在轮数100以后，平均节约网络能耗1 500 J左右。所以，在基站分布较远的随机分布无线传感网络中，本文算法通过簇头节点间多跳配合的方式完成与基站的通信，能有效降低网络能耗。

4 结束语

分层协议LEACH相较于平面多跳路由等协议能有效地提高网络寿命，但存在能量消耗不均匀、局部负载大等局限性。本文提出一种基于LEACH的改进分层路由算法，每个节点维护自身路由属性表，节点根据距离和能量两个因素选择入簇，同时根据距离调整了簇成员以及簇与簇之间的通信方式。仿真结果表明，改进的分层路由算法能有效降低网络能耗，延长网络寿命。该算法思路适应于传感器节点随机分布的大中型传感采集场景，如图书管理、仓储管理管理等。

[1] 任丰原,黄海宁,林 闯.无线传感器网络[J].软件学报,2003,14(7):1282-1291.

[2] Jisoo S,Chang J S.CREEC:Chain Routing with Even Energy Consumption[J].Communications and Networks,2011,13(1):17-25.

[3] 冯友宏，关 可.基于OMNET的无线传感器网络算法的改进[J].传感技术学报，2010,23(6):859-862.

[4] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]∥Proceedings of the 33rd Annual Hawaii International Conference on System Sciences,Jan.2000,2:10-15.

[5] Himanshu B P,Devesh C J.E-LEACH:Improving the LEACH Protocol for Privacy Preservation in Secure Data Aggregation in Wireless Sensor Networks[C]∥IEEE International Conference on Industrial and Information Systems (ICIIS),Gwalior:IEEE Press,2014:1-5.

[6] 胡 钢，谢冬梅，吴元忠.无线传感器网络路由协议LEACH 的研究与改进[J].传感技术学报，2007，20(6):1391-1396.

[7] XIE Wei-xian,ZHANG Qi-ye,SUN Ze-ming,et al.A Clustering Routing Protocol for WSN Based on Type-2 Fuzzy Logic and Ant Colony Optimization [J].Wireless Personal Communications,2015,84(2):1165-1196.

[8] Masaeli N,Javadi H H S,NOORI E.Optimistic Selection of Cluster Heads Based on Facility Location Problem in Cluster-Based Routing Protocols[J].Wireless Personal Communications,2013,72(4):2721-2740.

[9] 李灯熬，郝海龙，郭锦龙，等.一种能量有效的无线传感器网络分簇及簇间路由算法[J].自动化仪表,2015,36(12):4-7.

[10]段 军.蚁群算法在LEACH 路由协议中的应[J].计算机技术与发展,2014,24(1):65-68.

[11]Navin G,Pyun J Y.Distance Aware Intelligent Clustering Protocol for Wireless Sensor Networks[J].Communications and Networks,2010,12(2):122-129.

Research of Low-energy Consumption Routing Algorithm Based on LEACH

CAO Xi-zhu,DING Xu-xing,FENG You-hong,LING Min,WANG Zai-jian

(College of Physics and Electronic Information,Anhui Normal University,Wuhu Anhui 241000,China)

Low-Energy Adaptive Clustering Hierarchy (LEACH) is a kind of hierarchical routing protocol,but some drawbacks exist,such as uneven distribution of Cluster Heads (CHs),centralized energy consumption and so on.In this paper,an improved algorithm in distance control based on LEACH is proposed to solve the problems above,which is called LEACH-D (LEACH-Distance).In the step of selecting CHs,the number of CHs and the relative distribution position of them are considered.In the step of clusters formation,the way that the nodes join the cluster is decided by the routing attribute tables and the density.Simulation results show that the improved algorithm balances the network energy consumption effectively,and prolongs the lifetime of networks compared with LEACH.

LEACH;routing attribute tables;wireless sensor networks;balancing the energy consumption

10.3969/j.issn.1003-3114.2016.06.12

曹喜珠,丁绪星,冯友宏,等.基于LEACH的低能耗改进算法研究[J].无线电通信技术,2016,42(6):48-51.

2016-07-14

国家自然科学基金项目(61401004)；江苏省2015年高校研究生科研创新计划项目(KYLX15_0833)

曹喜珠(1980—) ，女，硕士研究生，主要研究方向：无线传感网、物理层安全。丁绪星( 1970—) ，男，教授，主要研究方向：智能仪器、无线传感器网络。冯友宏( 1979—) ，男，副教授，主要研究方向：无线通信、物理层安全。

TP212

A

1003-3114(2016)06-48-4