面向新疆平原灌区的LEACH路由算法研究

池涛,汪磊

面向新疆平原灌区的LEACH路由算法研究

池涛,汪磊*

上海海洋大学信息学院, 上海 201306

已研究的无线传感器网络系统多使用于温室大棚、中部平原等环境中，并采用LEACH路由算法均衡网络能量，以达到延长网络寿命的目的；这些网络中节点与节点之间的距离较近、面积规模较小、每个节点能量相对充足，因此在使用LEACH路由算法时不容易出现因选取簇头不当、节点能耗过快而产生网络空洞等问题；但在新疆平原灌区中进行无线布网时，因硬件成本有限、地理环境复杂等各种因素的限制，导致部署出来的无线传感器网络是一种典型的Zig Bee广域网，该网络中节点与节点间距离较远，不同节点之间传输信息时能量消耗过大，因此当网络中选举不当节点作为簇头时会因该节点能量消耗过快而产生节点失效的问题，产生网络空洞现象；本文针对这种现象，在面向新疆平原灌区网络这一限制区域中，联合节点距离、密度及剩余能量提出了一种的改进型LEACH算法，该算法针对传统LEACH算法在随机选取簇头过程中的缺点，在簇头选取过程中，首先将网络按照终端节点与基站之间的距离等级划分为多个区域，使得距离基站越近的节点成为簇头的概率越大，然后通过各个区域中节点密度和剩余能量因素将适合的节点选举为簇头，提高网络利用率，解决网络空洞问题，延长网络生命周期。采用Matlab软件对改进算法进行仿真，实验结果表明在节点稀疏的网络中改进后的LEACH算法比传统LEACH算法的网络寿命提升了16%，且可以满足新疆平原灌区中广域网络要求，减少了网络空洞问题的产生。

LEACH路由算法; 簇头; 广域网; 网络空洞

新疆是我国农业种植密集区域，因地理环境复杂，基础网络条件设施不全等因素的限制，直接影响了新疆农业经济的发展。随着近几年无线传感器网络技术的发展，如何在西部农业灌区网络中设计一套合适的低功耗路由算法已经成为当今社会的一大研究热点。

自2000年LEACH算法被设计出来以来[1]，基于均衡无线传感器网络中能量消耗，延长网络寿命的目的，国内外研究人员设计了多套改进型LEACH算法[2-7]。Heinzelman WR等人提出了一种基于簇的LEACH协议，利用簇内随机旋转选取簇头来均衡网络中能量负载，仿真结果表明，LEACH协议与传统路由协议相比降低了能耗，网络生命周期得到了延长[1]。Ahlawat A，Malik V等人在分析LEACH路由协议的基础上提出了一种改进型路由协议V-LEACH，基于最小距离、最小能量和最大剩余能量等因素在每个网络簇中选举一个副簇头，用于当簇头因能量耗尽而死亡后进行取代的作用。仿真结果表明V-LEACH路由协议有效延长了网络寿命[2]。李年琼等人针对LEACH路由算法随机选取簇头节点的弊端，提出了一种基于剩余能量和位置的改进型LEACH算法，该算法将传感器节点的节点剩余能量和几何平均位置作为选簇的重要因素，在此基础上选最佳簇头[3]。顾明霞等人针对节点剩余能量的状态，使能量高的节点尽量成为簇头，在数据传输阶段采用单跳和多跳结合的混合通信方式均衡簇头和基站能量消耗[4]，仿真结果表明改进后的E_LEACH算法相比于LEACH路由算法更能均衡网络能量。叶继华针对在多种类型数据同时采集的异构网络，提出一种改进型可变通周期性策略的能量均衡协议，将数据通信周期和数据采集周期分离，采用可变通周期策略来减少网络中簇头节点的消耗，达到平衡网络能量的功能[5]。蒋建明等人在针对水产养殖无线传感网络中测量节点能耗过快、个别节点过早失效导致网络寿命缩短等问题，联合节点距离基站位置及剩余能量因素选取合适的簇头节点提出了一种改进型的LEACH-C算法，该算法在LEACH算法的基础上将生命周期延长了8%[6]。但是当前改进的LEACH路由算法多是使用于小面积的、网络节点分布密度较大的小型网络中，对于西部这种节点稀疏的大型广域网络并不适用。

文章针对西部农业灌区这一应用场景，在农业灌区中随机网络布点，采用Zig Bee和北斗相结合的方案，设计了一套基于Zig Bee技术和北斗点位技术相结合的无线传感器网络监测系统。针对随机簇头选举过程中导致节点能量消耗过快从而导致节点失效引起的网络空洞等问题，在传统的LEACH算法的基础上，结合网络中节点位置、网络簇中所有节点密度等因数，提出了一种改进型LEACH路由算法，提高了网络能量有效性，延长网络寿命。实验证明该算法适用于大多数节点密度较低、锚节点分布稀疏的新疆农业灌区网络中。

1 新疆广域网络分析

图 1 新疆广域网络

如图1所示，新疆农业灌区网络通过Zig Bee自组织网络将监测区域分为若干簇，网络中节点主要分为普通节点、簇头节点和基站；普通传感器节点用于收集周围参数信息，簇头节点用于接受传自普通节点中的信息，将簇头节点的信息传递给基站，最后基站将所有的信息汇总传递给所需的终端;本网络模型中，网络节点满足以下条件[8-10]：

1）网络中所有节点的构造和初始能量相同，节点能量在网络工作的过程中是不能补充的；

2）网络中所有节点的通信半径R是一致且已知的，且发射功率可控；

3）网络中所有节点有唯一标识；

4）网络中节点的位置已经通过少量的带有北斗模块的节点监测出来；

5）网络中的基站能量不需要我们考虑。

与常见无线传感器网络的不同在于新疆农业灌区网路面积更大，且网络中节点数目更少，导致网络节点密度远远低于常规网络，一些常规的路由算法（例如LEACH路由算法）在这种广域网中并不能适用[11-13]。

1.1 LEACH协议分析

LEACH协议是一种基于分簇的低功耗自适应路由协议，是层次型路由协议的典型代表。该算法的核心思想：将整个网络分为多个簇，并引入”轮”的概念，每轮可以分为粗的建立和稳定的数据传输阶段，每次循环以随机的方式选取簇头节点，簇中其余节点收集附近的信息，并将信息汇集到簇头，由簇头将簇中所有信息进行融合传递给基站。簇头融合传递本簇中所有信息，因此能量消耗消耗比其余节点快，该协议在每轮中将不同的节点轮转为簇头，这种轮转将网络中能量消耗均衡到每个节点，达到降低网络能量消耗，延长网络寿命的目的。让网络中节点完成轮转，实现每个节点成为簇头完成信息融合传递是该协议的重要核心所在。

图2显示了LEACH算法的运作过程。

图 2 LEACH算法运行过程

在建立阶段采用随机自治的方式选取簇头，簇头的选取是独立的、自治的，每个节点都有相同的概率成为簇头。在选取过程中，每个节点产生0~1之间的随机数，如果这个随机数大于阈值()，则此节点为普通节点，反之，则设置为簇头节点，簇头节点产生后向网络中其余节点进行广播，普通节点接受到簇头信息后，加入距离较近的簇头组成的簇中；在每轮中，只要该节点担任过簇头，则把()设置成0，在以后的轮中不再担任簇头。()的公式如（1）所下：

矿体主要分布于花岗闪长斑岩侵入体与香夼组灰岩接触带上，共探明64个矿体，矿体呈脉状、透镜状、似层状、囊状，主矿体向下700m仍为封闭[12]。矿化具有明显的分带现象，垂向上由浅部向深部，平面上由外部向内部，依次为矽卡岩铅锌矿带、矽卡岩-斑岩铜硫矿带、斑岩铜钼矿带。矿石主要包括矽卡岩型和绢英岩化斑岩型两类，矿石主要呈浸染状、细脉浸染状、块状及条带状构造。围岩蚀变自岩体内部向外围蚀变类型依次为：硅化、绢云母化、钾化→矽卡岩化→绿泥石化、绿帘石化、绢云母化、碳酸盐化等。

：簇头在所有节点中的比例；：选取的轮数；rmod(1/)：表示这一轮中当选为簇头的节点的个数；：这一轮中未当选为簇头节点的集合。

在稳定的数据通信阶段，簇内其余节点将采集到的数据发送给簇头，簇头把其余非簇头节点的信息融合后发送给基站，在这一过程中簇头需要消耗大量的能量，经过一段的数据传送后，节点进行下一轮的工作。

通过周期性随机选取簇头和网络重组将网络中消耗的能量均衡到每一个节点中达到延长网络寿命的目的，提高网络生存的总体时间，避免簇头节点因消耗过快而产生网络寿命提前结束的问题。但是LEACH算法仍然存在不足：①LEACH算法中随机选取簇头节点的方式会造成簇分布不合理现象，增加了某些簇头节点的负担，导致某些离基站较远的簇过早因能量消耗过快导致网络空洞等问题；②LEACH算法中每个簇内节点分布不均，增加了某些簇头节点的能量消耗，降低网络负载平衡。

2 LEACH路由算法的改进

在新疆平原灌区网络中因节点随机分布，导致传统LEACH算法选举出来的簇头节点并不能最好地发挥整个网络的功能，当某些偏远节点当选为簇头时容易使网络产生网络空洞[14,15]。改进后的LEACH路由算法节能核心思想是：对网络中节点距离基站的位置进行划分，增加距离基站较近位置的节点成为簇头的概率，然后通过网络簇中节点密度及剩余能量因子选取合适簇头节点，则簇头将普通节点传递额信息进行融合后传递给基站时消耗能量比远距离簇头传递信息所消耗的能量要少，使选举出的簇头节点能延长网络寿命，更适用与新疆平原灌区中。改进型LEACH路由算法的簇头选取阶段优化主要分为两步：①通过网络节点区域划分；②区域节点密度、能量划分。

2.1 簇头节点优化选举

2.1.1 网络节点区域划分由于LEACH算法中对簇头的选取是随机的，导致簇头集中分布不合理。本算法通过节点距离基站位置将整个网络划分为8个区域，如图3所示。

图 3 网络区域划分

在每个区域中固定簇头的比例，其中区域1中代表基站，不需要设置簇头，其余区域中簇头按以下步骤：

1）区域理想簇头比例：

2）每个区域中节点的数目：Q

3）区域中簇头节点的比例：

*=C/Q(3)

采用区域节点分区的方法对节点成为簇头的概率进行了初步划分，对每个区域的簇头比例进行了严格控制，防止了簇头分布严重不均匀的问题，这样避免了不合理簇头的产生。

2.1.2 区域节点密度、能量划分通过网络节点分区的方法划分了不同区域内簇头节点的比例，解决了簇头分布不合理的问题，再结合每个区域中节点能量及密度值，解决簇内节点分布不均匀、剩余能量较少的问题。

1)设置剩余能量限制条件

每个区域中节点参与簇头的选举时剩余能量e需要满足以下条件：

avr：整块网络区域中存活节点的平均能量；：每块区域中存活节点的数目。

表示区域中每个存活的节点只有在剩余能量大于avr的时候才能有条件当选为该簇的簇头节点。避免了在传统LEACH算法中能量过少的节点成为簇头，加快节点死亡的突出问题。

2)设置节点密度限制条件

注：*为（3）中*;

算法工作流程如图4所示。

图4 改进算法流程图

通过*()可知，普通节点对最近簇头和基站位置进行比较，判断将信息直接传递给基站还是簇头；当离基站距离越近的区域内簇头节点的比例越高，节点的周围节点数目越多时，节点成为簇头的概率得到提升，反之则成为簇头节点的概率越低。该改进后的LEACH算法有效解决了西部平原灌区网络中簇内节点分布不均匀、簇头节点分布不均和网络空洞的问题，能有效使用于西部农业中。

3 仿真及结果分析

为了评价改进后LEACH算法的性能，利用MATLAB工具对本文的改进型LEACH算法和传统LEACH算法进行比较。选取面积为400 m*400 m大小区域，在该区域内随机布置N个节点，基站坐标为（0 m,0 m），簇头的比例占整个网络节点的10%，每个节点的传感半径为40 m，节点初始能量为0=0.5 J，自由空间信道模型的能耗参数ɛ=10 PJ/bit/m2,多路信道衰减信道模型参数ɛ=0.0013 PJ（bit*m4，最大循环次数rmax=500。

仿真实验中以不同节点密度下LEACH算法和改进后LEACH算法中节点存活时间为指标评判算法对整体网络性能的影响。

图 5 节点存活率比较图（50个节点）

图 6 节点存活率比较图(100个节点)

图 7 节点存活率比较图（150个节点）

如图5、6、7所示，分别为50个节点、100个节点、150个节点在400 m*400 m的区域中节点死亡率，每图左边为LEACH算法，右图为改进后的LEACH算法，一般情况下，整体网络中80%节点死亡后，说明该网络已经死亡；实验结果证明，在节点密度为0.0003个/m2的网络中改进后LEACH算法比传统LEACH算法存活率提高了16%；在节点密度为0.0006个/m2的网络中改进后LEACH算法比传统LEACH算法存活率提高了19%；在节点密度为0.0003个/m2的网络中改进后LEACH算法比传统LEACH算法存活率提高了24%；因此在节点稀疏的新疆平原区域可以使用改进后的LEACH算法，以达到延长网络寿命，减少网络空洞的作用。

4 结语

路由算法的研究对无线传感器网络在新疆平原区域中的应用有着重要的意义，它的性能直接影响着在实际应用中的实用性。本文在常规的LEACH路由算法的基础上，采用新型的簇头选举策略来保证整体网络中节点能量均衡，进一步延长了网络寿命。实验表明，改进型的LEACH路由算法在实际中延长了网络整体寿命，在一定程度上避免了网络空洞的产生。

[1] Heinzelman WR, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless sensor networks[C]// Hawaii International Conference on System Sciences, IEEE Computer Society, 2000:8020

[2] Ahlawat A, Malik V. An Extended Vice-Cluster Selection Approach to Improve V Leach Protocol in WSN[C]// Third International Conference on Advanced Computing & Communication Technologies, IEEE Computer Society, 2013:236-240

[3] 李年琼,黄宏光,李鹏.基于剩余能量和位置的LEACH改进算法[J].计算机工程,2012,38(24):70-73,77

[4] 顾明霞.一种新的基于LEACH的WSN路由算法[J].计算机仿真,2011,28(8):129-133

[5] 叶继华,王文,江爱文.一种基于LEACH的异构WSN能量均衡成簇协议[J].传感技术学报,2015,28(12):1853-1860

[6] 蒋建明,史国栋,李正明,等.基于无线传感器网络的节能型水产养殖自动监控系统[J].农业工程学报,2013,29(13):166-174

[7] 叶继华,王文,江爱文.一种基于LEACH的异构WSN能量均衡成簇协议[J].传感技术学报,2015(12):1853-1860

[8] 周洁,石志东,张震,等.WSN中一种基于LEACH协议的改进算法[J].上海大学学报:自然科学版,2013,19(2):116-119

[9] 马建乐,杨军.基于位置和剩余能量的局部集中式LEACH算法研究[J].传感技术学报,2013(8):1147-1151

[10] 廖明华,张华,王东.基于LEACH协议的簇头选举改进算法[J].计算机工程,2011,37(7):112-114

[11] 严斌亨,陈任秋,刘军.能量优化的无线传感器网络LEACH算法[J].传感器与微系统,2016,35(7):120-122

[12] 谭军.簇首选择改进的LEACH无线传感器路由协议[J].计算机应用与软件,2015(6):171-173

[13] Ran G, Zhang HZ, Gong SL. Improving on LEACH Protocol of Wireless Sensor Networks Using Fuzzy Logic[J]. Journal of Information & Computational Science, 2010,7(3):767-775

[14] Godbole V. FCA-An Approach On LEACH Protocol Of Wireless Sensor Networks Using Fuzzy Logic[J]. International Journal of Computer Communications and Networks(IJCCN), 2013,2(3):1-13

[15] Banimelhem O, Taqieddin E, Awad F,. Fuzzy Logic-Based Cluster Heads Percentage Calculation for Improving the Performance of the LEACH Protocol[J]. International Journal of Fuzzy System Applications, 2015,4(4):100-118

Study on LEACH Routing Algorithm for Xinjiang Plain Irrigation Area

CHI Tao, WANG Lei*

201306,

With the wide use of wireless sensor networks in agricultural areas, the LEACH routing algorithm is often used to balance the energy of the network in the agricultural region,to achieve the purpose of prolonging network life;In these networks, the distance between the node and the node is very close, the network area is very small and the energy of each node is relatively sufficient, therefore, it is not easy to generate the network hole problem caused by the irrational network holes caused by randomly selected cluster heads when using the LEACH routing algorithm; but the wireless distribution network in Xinjiang plain irrigation area, various factors such as hardware cost and special geographic environment are considered. So that the deployed wireless sensor network is a typical ZigBee wide area network. In this network, the distance between nodes is far from the nodes, therefore, cluster heads can't be randomly selected in the network. If the improper nodes are selected as cluster heads, the energy consumption of nodes will be too fast, resulting in node failure and network cavitation. In view of this phenomenon, this paper proposes an improved LEACH algorithm based on node distance and node density, the algorithm for the traditional LEACH algorithm in randomly selected cluster head in the process of the shortcomings in the cluster head selection process, considering the residual energy of node and the network node location and node density, as far as possible to select higher residual energy in a network node density is high in the area from the base station node distance as the cluster head to Improve network utilization, solve the problem of network hole and prolong the life cycle of network.

LEACH routing algorithm; cluster head;wide area network; network cavity

TP302.1

A

1000-2324(2019)04-0675-06

2018-05-07

2018-08-12

国家自然科学基金(61561027);上海市自然科学基金(16ZR1415100)

池涛(1976-),博士/博士后,副教授,研究方向为嵌入式系统及农业物联网. E-mail:tchi@shou.edu.cn

Author for correspondence. E-mail:907861285@qq.com