无线传感器网络LEACH分簇路由协议研究*

张 珉，王中训，娄 阳，刘宝军

（烟台大学 光电信息科学技术学院，山东 烟台 264005）

无线传感器网络LEACH分簇路由协议研究*

张 珉，王中训，娄 阳，刘宝军

（烟台大学 光电信息科学技术学院，山东 烟台 264005）

无线传感器网络是物联网的重要支撑基础技术之一，在国防民用各个方面有着广泛应用。无线传感器网络由很多具有无线射频功能的传感器节点组成，是一种灵活、自适应性强的网络。研究无线传感器网络中的分簇路由协议，分析LEACH协议的优缺点，指出问题所在，设计和改进的首要目的是延长网络的生命周期，提高能量的利用率。因此，针对原LEACH协议存在的不足，在簇头的选举、特殊节点的处理以及簇间路由传输问题上分别进行改进，并利用MATLAB进行仿真，对比分析其与原协议在存活点个数、耗能、传输数据效率的性能，具有一定的实用价值。

无线传感器网络；分簇；路由协议；仿真

0　引 言

无线传感器网络（Wireless Sensor Networks，WSNs）是近年来炙手可热的研究方向。因为该项技术在恶劣环境、无人值守、资源受限制等的特殊环境中具有十分卓越的表现性能，能够客观及时有效地获得人们想要的物理信息，所以广泛应用于譬如抢险救灾、防空反恐、危险区域远程控制、生物医疗、智能家居、城市管理、工农业控制、军事国防等诸多领域。

无线传感器网络的拓扑结构不是一成不变的，并且网络中每个节点的能量也是受限的且通常非常少，所以在无线传感器网络的诸多研究中，能够连接所有传感器节点且可以降低能耗的路由协议是其最关键的技术之一。结构上，WSN路由协议可分为平面协议和层次性协议。平面协议工作时需要维持较大的路由表，并不适合应用于大规模网络；层次性协议又称分布式协议或分簇性协议，如图1所示，其较为经典的协议即本文将要讨论的低功耗自适应集簇分层型协议[1]（Low Energy Adaptive Clustering Hierarchy，LEACH）。该协议是由MIT的Heinzelman等人与2000年提出的，由节点轮流担任簇头而达到能量尽可能均匀消耗的目的。但是，该协议也存在簇头的分布不合理、能耗不均、单跳选择等缺陷。W-LEACH[2]、T-LEACH、LEACHRA和LEACH-C等改进协议，对原LEACH协议在不同角度进行了不同改进[3]，但大部分算法选簇时仍沿用LEACH的分布式方法。

图1　无线传感器网络分簇

1　LEACH协议分析研究

1.1LEACH协议概述

LEACH协议的核心是确定簇头节点，为此提出“轮”（Round）的概念。每一个Round由簇的建立态和稳定态两个状态组成。每一轮开始都要重新确定簇头的位置，然后簇头广播自己的位置和信息。普通节点接收到离自己最近的簇头节点信息后加入。所有的簇头和普通节点都已经确定时（实际应用时，并不是所有的头都有下属的普通节点，也不是所有的普通节点都能加入某一个簇头），网络开始进入稳定状态，后再进入选举状态，依此周期性进行，直至系统所有能量都耗尽，系统死亡。

确定簇头节点时，每个节点随机生成一个[0,1]之间的数。若小于式（1）中的T(n)，则该节点就被选为簇头节点，其余点则为普通节点。式（1）中，p是该网络中簇头节点与总节点的比例，r是当前选举的轮数，G是在剩余1/p轮中普通节点的集合。

选定簇头节点后，簇头节点广播告知整个网络。网络中的其他普通节点根据信号的强度决定自己从属哪个簇头节点，并告知簇头节点，至此完成簇的建立。然后，簇头用TDMA方式分配给每个下属普通节点传递数据的时间点（发送时隙）。在稳定阶段，簇头对接收到的各个普通节点的数据进行融合，然后转发至基站（Base Station，BS），整个过程如图2所示。

图2　LEACH运行过程

1.2LEACH协议的主要问题

LEACH协议提出时，相对整个物联网和无线传感器网络的发展进度，非常具有前瞻性和创新性。LEACH协议相对其他平面节点，可以减少15%以上的能耗[1]。其后人们开始研究对LEACH协议的改进，提出了很多实用的改进方向。本文主要针对LEACH的以下问题进行研究和改进。

第一，实际应用中簇的划分及其不平衡，有的簇过于庞大，有的反而只有一个节点，造成节点能量大量的浪费。文献[4]指出，极小簇节点能耗相比极大簇节点高出20%左右，同时原协议对加入簇失败的节点处置不够合理。

第二，簇节点与基站通信是单路径点对点传输，此时若簇头与基站距离太远，则需很大的发送功率[5]。同时，稳定阶段若某簇头因意外情况猝死，原LEACH协议是没有备用簇头节点的，则该簇内的普通节点仍会按照原先分配的时间进行通信，直至本轮结束，从而造成大量能量浪费。

第三，文献[6]指出，簇头节点与普通节点比例以1/19为佳，即5%比重时，系统效率最高。事实上，该比例是基于初始节点数目确定簇头节点数目的，实际运行中经常有新节点加入或者已有节点死亡而引起的拓扑结构的变化。

2　对LEACH协议的综合改进

2.1基本思想

基于原协议存在的问题，本文主要在以下方面进行改进：要对各个簇划分规模，控制簇成员，控制最小簇或者等待时间超过限制直接与基站通信；首轮过后，要由基站节点选出下一轮簇头，依据剩余能量、与基站位置距离、已当选次数和邻居节点数目等，综合选举下一轮簇头节点；特殊节点的处理更加科学；意外情况发生时，本文程序会自动启用备用簇头节点；最后，设置更科学合理的多跳簇间路由[7]等。

2.2一阶无线电模型

图3为一阶无线电模型。本文工作中，假设一个简单的模型的发送和接收信号，分别耗能Eelec=50 nJ/bit，发送放大器放大倍数为εamp=100 pJ/bit/m2，以得到可以接受的值。同时，假设在信道传输中有r2的能量损耗。因此，无线电模型在距离d发送k bit信息时，无线电扩展为：

同样条件下，接收信息无线电扩展为：

图3　一阶无线电模型

由以上可知，接收信息功耗是不低的。因此，本文的路由协议应该不仅降低发送功率，还要去降低接收功率[1]。

2.3簇头的选择

首轮选举，主要采用原协议的方法，并且引入ts等待时间、Tr每轮持续时间。当特殊节点等待时间ts＞Tr/2时，此节点直接与BS通信，以减少不必要的能量浪费[8]。通过首轮选举，BS已经收集掌握了各个节点的当前信息，从第二轮开始，簇头节点由BS分配，具体流程如图4所示。

记Ecurrent(ni)为节点ni目前的剩余能量，dtoBS(ni)表示节点ni到基站的距离，N(ni)表示此节点上一轮同簇节点总数。同时，记节点ni在属于簇ci时，被选为下轮簇头的评估函数f(ni,ci)，则：

式中，fe、fd和fc分别用来考查剩余节点能量情况、与BS的远近程度以及相邻节点数。在提出的协议中，用上轮同簇节点数目来近似邻居节点数。we、wd和wc是所考察指标的权重指数，具体取值可以根据网络规模和应用情况来调整[9]。

同时，所提协议规定，簇头选举程序会选出一个备用簇头节点。这样当簇头节点猝死时，备用簇头节点还可以继续代替它进行工作，不会让簇内成员能量无谓损耗。

图4　簇头选择流程

2.4簇间多跳通信

众所周知，簇头负责与BS之间的通信。然而，当簇头离BS距离较远时，簇头会消耗很大的发送功率，从而造成簇头节点能量过快消耗光。于是，提出解决方法：当簇头离BS较远时，采用多跳的路由，选择最小的路径，把数据传输给BS；而当距离很近时，簇头直接与BS通信。目前，有很多最小能量路由协议，基本上在选择路由的时候只考虑发送功耗，而忽略接收功耗。这里进行综合考量，中间路由转发节点必须使总能量消耗尽可能小，所以不仅要减少转发距离，还要降低转发次数[5]。

3　改进协议的MATLAB仿真

MATLAB是美国MathWorks公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，在工程领域应用非常广泛。本文将使用MATLAB 7.1仿真工具，对提出的改进协议进行仿真。设置仿真参数如表1所示[10]。

设置网络运行3 000轮，100个节点具有相同的初始能量，分别对两种协议进行仿真，死亡节点随时间变化对比图如图5所示。

表1　仿真参数

图5　LEACH和LEACH-Improvement的死亡节点随时间变化对比

分析数据发现，原协议在第1～731轮都没有出现死亡节点，所有的节点都是存活的，直至第732轮，出现了第一个死亡节点，其后死亡节点急剧增加，至第1 220轮所有节点都死亡，整个网络死亡；而LEACH-Improvement在第1～783轮都没有死亡节点，所有的节点都是存活的，直至第784轮出现了第一个死亡节点，其后死亡节点同样急剧增加，但存活节点数始终大于原协议，死亡节点数一直少于原协议，至第1 560轮所有节点死亡，整个网络死亡。通过曲线对比可以很直观地发现，LEACH-Improvement在存活上的表现比原协议好。

如图6所示，在网络吞吐量上，原协议BS首轮接收6单位数据，此后随着轮数的增加，接收数据缓慢增加，直至所有节点死亡，BS接收到9 925单位数据；而LEACH-Improvement的BS首轮接收18单位数据，其后快速增长，直至节点全部死亡共接收到25 454单位数据，整个生命周期始终保持比原协议高的数据量。可见，改进后的协议在时间上的效率相对原协议高。

在网络消耗上，如图7所示。在前500轮，两个协议的消耗大体无异。500轮之后，原协议的网络消耗急剧增加，至所有节点死亡，共消耗50.14 J能量；而LEACH-Improvement协议在500轮之后耗能增加，至所有节点死亡，共耗能50.07 J。在能耗方面，原协议比改进协议耗能更快，改进协议比原协议更加节能，能量消耗速度更缓慢。

图6　LEACH和LEACH-Improvement的数据传输对比

图7　LEACH和LEACH-Improvement的网络消耗对比

4　结 语

无线传感器网络分簇算法采用轮换的节点作为簇头方式来平衡整个传感器网络的负载和能量，但随机选择簇头的方式和单跳的簇间路由有时会造成能源的大量浪费。针对这些问题，本文逐一进行逐改进。在簇头选择上，参考更多的节点客观参数。仿真发现，在100个节点上，改进算法在生存期、能耗、效率上，均有一定的提高。但同时发现，本改进算法在更大规模网络上（如300枚节点）的应用效果并不理想，因为对网络进行的一些细节改进使得自适应性被削弱；BS在确定簇头时会产生更多簇间路由。鉴于此，下一步在解决以上问题的同时，会在选举函数参数上做更多的研究。

[1] 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:Piscataway,2000:175-187．

[2] Sharma I,Singh R,Khurana M.Comparative Study of LEACH,LEACH-C and PEGASIS Routing Protocols for Wireless Sensor Network[C].IEEE Computer Engineering and Applications,2015:1-15.

[3] Sony C T,Sangeetha C P,Suriyakala C D.Multi-hop LEACH Protocol with Modified Cluster Head Selection and TDMA Schedule for Wireless Sensor Networks[C].IEEE Communication Technologies(GCCT),2015:539-543.

[4] 吕涛,朱清新,张路桥.一种基于LEACH协议的改进算法[J].电子学报,2011,39(06):1405-1409. LV Tao,ZHU Qing-xin,ZHANG Lu-qiao.An Improved Algorithm based on LEACH Protocol[J].Journal of Electr onics,2011,39(06):1405-1409.

[5] Omari M,Fateh W H.Enhancing Multihop Routing Protocols in Wireless Sensor Networks Using LEACH-1R[C].Web Applications and Networking(WSWAN),2015 2nd World Symposium on IEEE,2015:1-6.

[6] Heinzelman W B,Chandrakasan A P,Balakrishnan H.An Application-specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Transactions on Wireless Communications,2002,1(04):660-670.

[7] 陈炳才,么华卓,杨明川等.一种基于LEACH协议改进的簇间多跳路由协议[J].传感技术学报,2014(03):373-377. CHEN Bing-cai,YAO Hua-zhuo,YANG Ming-chuan,et al.An Improved Inter Cluster Multi Hop Routing Protocol based on LEACH Protocol[J].Journal of Sensing Technology,2014(03):373-377.

[8] 陈慧杰,韩江洪,刘磊.无线传感器网络中自然能收集分簇路由算法研究[J].计算机工程,2016,42(03):143-147. CHEN Hui-jie,HAN Jiang-hong,LIU Lei.Research on Clustering Routing Algorithm in Wireless Sensor Networks[J].Computer Engineering,2016,42(03):143-147.

[9] 马建乐,杨军.基于位置和剩余能量的局部集中式LEACH算法研究[J].传感技术学报,2013(08):1147-1151. MA Jian-le,YANG Jun.Local Centralized LEACH Algorithm based on Position and Residual Energy[J].Journal of Sensing Technology,2013(08):1147-1151.

[10] 陈晓娟,王卓,吴洁.一种基于LEACH的改进WSN路由算法[J].传感技术学报,2013,26(01):116-121. CHEN Xiao-juan,WANG Zhuo,WU Jie.An Improved WSN Routing Algorithm based on LEACH[J].Journal of Sensing Technology,2013,26(01):116-121.

张 珉（1991—），男，硕士研究生，主要研究方向为物联网通信、无线传感器网络仿真等；

王中训（1965—），男，博士，教授，硕士研究生导师，主要研究方向为LDPC编码以及水下通信；

娄 阳（1990—），男，硕士研究生，主要研究方向为LDPC码混沌加密技术；

刘宝军（1991—），男，硕士研究生，主要研究方向为LDPC码和FPGA仿真技术。

LEACH Clustering Routing Protocol for Wireless Sensor Networks

ZHANG Min, WANG Zhong-xun, LOU Yang, LIU Bao-jun
(Institute of Science and Technology for Opto-Electronics Information, Yantai University, Yantai Shandong 264005, China)

Wireless sensor network ,as one of the important supporting technologies for IOT (Internet of things), is now widely used in the defense and civilian fields. Wireless sensor network,composed of many sensor nodes with wireless radio frequency function, is also a very flexible and adaptive network, and its routing protocol is extremely important. The cluster routing protocol in wireless sensor network is discussed, the advantage and disadvantage of LEACH protocol analyzed, and the problem pointed out. The primary purpose of design and modification lies in extending life cycle of the network, improving the utilization rate of energy. Aiming at the problems existing in the original LEACH protocol, the selection of cluster head, the processing of special node and the routing of between the clusters are improved.Simulation with MATLAB and comparison with the original LEACH in the number of survival points, the energy consumption and the efficiency of data transmission indicate that this modification is feasible and of certain practical value.

wireless sensor network; clustering; LEACH; simulation

Science and Technology Development Project of Shandong Province（No.2012J0030009）

TN212

A

1002-0802(2016)-08-01023-06

10.3969/j.issn.1002-0802.2016.08.013

2016-04-21;

2016-07-21

date:2016-04-21;Revised date:2016-07-21

山东省科技发展计划项目（No.2012J0030009）