基于多尺寸网格的LEACH协议改进

刘国繁,丁 燕

(1.湖南工程学院电气信息学院,湖南湘潭411104; 2.湘潭大学信息工程学院,湖南湘潭411105)

基于多尺寸网格的LEACH协议改进

刘国繁1,丁 燕2

(1.湖南工程学院电气信息学院,湖南湘潭411104; 2.湘潭大学信息工程学院,湖南湘潭411105)

针对低功耗自适应集簇分层型(LEACH)协议中节点采集的数据存在大量冗余和能量消耗不均衡问题,提出一种能量高效路由协议MDG-LEACH。该协议基于虚拟网格和多尺寸网格选取活跃节点,采用综合考虑节点剩余能量和空间分布情况的簇头选择机制,簇头与基站之间根据动态规划方法建立最短传输路由树进行数据传输。仿真结果表明,与LEACH协议以及单剑锋的LEACH改进协议(计算机技术与发展,2013年第2期)相比,MDGLEACH协议在均衡节点能量消耗和延长无线传感器网络寿命方面有了较大提高。

低功耗自适应集簇分层型协议;多尺寸网格;活跃节点;分簇;多跳;Matlab仿真

1 概述

无线传感器网络由大量能量有限的节点组成［1-2］,这些节点由感应模块、处理模块、存储模块、传输模块以及电源模块组成。它们一般部署在人们无法靠近的恶劣环境,一旦电源耗完,节点也就失效了,因此,如何降低无线传感器网络的能量消耗、延长网络寿命成为研究的热点［3-4］。

低功耗自适应集簇分层型(Low Energy Adaptive Clustering Hierarchy,LEACH)路由协议［5］是一种经典的分层路由协议,该协议的主要思想是通过轮询随机选择簇头节点,将整个网络的能量负载平均分配到每个传感器节点中,目的是为了均衡整个系统的能量消耗,进而延长网络的生命周期。在LEACH协议的基础上,许多学者提出了大量的改进路由协议。文献［6］提出一种节点分组机制,在簇内,基于组间检测的数据存在冗余这一思想,让簇内各组之间交替工作,大大减少了系统的能量消耗,延长了网络寿命。文献［7］提出了一个改进LEACH协议ESSCSTA,该协议基于节点监测数据的相似度成簇,让离簇头近的50%的节点和簇内其他节点轮询处于休眠状态,簇间采用最小生成树的方法将采集的数据发送至基站。文献［8］提出一种基于各节点的属性不同,给予各节点不同簇首概率的算法,并在数据传输过程中,采用了多种传输选择机制,均衡了能量消耗,从而延长了无线传感器网络的寿命。文献［9］则从簇头选择、簇的形成以及数据传输等方面考虑,提出了一种改进的LEACH协议,延长了网络的生存时间。

针对LEACH协议中节点采集的数据存在大量冗余和节点能量消耗不均衡问题,基于虚拟网格思想,本文提出一种基于多尺寸网格的LEACH改进协议,以减少活跃节点的数量,均衡各节点的能量消耗,从而延长无线传感器网络的生命周期。

2 LEACH协议

LEACH［5］协议是一种基于聚类的路由协议,它最大限度地减少了系统能量的使用,在不同的时间,基站分发负载到不同的节点。LEACH是一个完全分布式的,不需要基站控制信息的以轮为周期的循环过程,在每轮中,LEACH分为2个阶段:簇的建立阶段和数据通信阶段。

2.1 簇的建立阶段

这个阶段包括簇头的选取和簇的形成。在LEACH协议中,所有节点都可以直接和基站通信。在每一轮中,每个节点都试图成为簇头,节点随机产生一个0-1的随机数,如果该随机数小于阈值T(n),则节点便可成为簇头。T(n)的计算公式如下:

一个节点一旦成为簇头,就发送一个成为簇头的消息,其他节点根据接收到信号强度的强弱,加入最近的簇头。

2.2 数据通信阶段

当簇建立完成后,簇头按照时分多址(TDMA)技术,为簇内普通节点分配时隙,簇内节点则在自己的时隙内,把采集到的数据发送到簇头节点,簇头节点把接收的数据进行融合、汇聚,然后直接发送至基站。

LEACH协议存在以下不足:

(1)簇头在选举过程中采用随机轮询的办法,没有考虑节点的剩余能量,由于簇头节点耗能要比普通节点大,因此如果能量小的节点担任簇头节点,则可能导致此节点快速死亡［10］。

(2)簇头在选举时,没有考虑节点的空间分布位置,假如簇头节点位于簇的边界处,则簇内节点在发送数据到簇头时消耗的能量不同,会造成簇内节点的能耗分布不均。

(3)在LEACH协议中,由于簇内某些节点之间的距离很小,它们监测的数据存在很高的冗余度,而簇内的所有节点都要始终保持活跃状态,将检测的数据发送至相应的簇头,导致部分簇内节点不必要的数据传输和簇头节点不必要的数据聚合。

(4)簇头节点采用单跳的方式和基站通信,在大规模的无线传感器网络中,远离基站的簇头节点直接将数据发送至基站,不但消耗大量的能量,而且会造成簇头节点的能量消耗不均［11］。

3 MDG-LEACH协议

MDG-LEACH协议以LEACH协议为基础,同样采用以轮为周期的循环过程,在每一轮中,基于虚拟网格和多尺寸网格选取活跃节点,活跃节点采用分簇的方式将检测的数据发送至基站。

假设网络模型如下:

(1)所有预先部署在特定区域内的无线传感器网络节点具有有限的能量。

(2)基站没有能量限制。

(3)所有无线传感器网络的节点可以通过GPS或者其他定位算法获取自己所在的位置。

(4)一旦布置完成,所有的无线传感器网络节点以及基站不再移动。

(5)L×L区域内的所有节点可以直接与基站通信,并且能够根据需要调节发射功率的大小。

3.1 簇的建立和活跃节点的选取

图1 虚拟网格的划分

在每个虚拟网格内选取一个剩余能量最多的节点作为活跃节点的候选节点,以平衡整个网络的能量消耗,防止能量小的节点很快耗完自身能量。

每个候选节点随机产生一个0～1的随机数,如果该随机数小于阈值T1(n),则该候选节点便可成为候选簇头节点。候选簇头节点的选取考虑节点的剩余能量和节点所在网格内非死亡节点的个数,候选节点的剩余能量越多,候选节点所在网格内非死亡节点的个数越多,则候选节点成为候选簇头节点的可能性越大。T1(n)的计算公式如下:

其中,p代表候选节点成为候选簇头节点的概率;r代表当前运行的轮数;Eres代表候选节点的剩余能量;Eo代表候选节点的初始能量;G代表在前1/p轮中还未成为簇头节点的候选节点的集合;num代表候选节点所在网格内非死亡节点的个数。

为了防止簇头节点的空间分布过于集中,设置一个簇头节点之间的最小距离dmin,只有候选簇头节点与其他簇头节点的距离不小于dmin才能成为簇头节点,没有成为簇头节点的候选簇头节点重新标记为候选节点。成为簇头的节点发送一个成为簇头的消息给所有的候选节点,候选节点收到来自簇头的消息,根据接收信号的强弱加入收到信号最强的簇头。

由于簇头节点可能分布在监测区域的任何一个位置,监测区域将被分成多种尺寸的大网格,如图2所示。

图2 簇头节点随机分布时的网格和活跃节点分布情况

候选节点根据节点关联算法决定是否保持活跃状态,成为活跃节点。假设任意簇头节点为A(x1,y1),任意候选节点为B(x,y),其中,x1,y1,x,y分别为节点A,B的横纵坐标。节点关联算法如下:

3.2 数据通信阶段

簇内数据的传输采用类似于LEACH的数据传输方式,簇头节点给簇内的活跃节点分配TDMA时隙,并通知簇内所有的活跃节点,这样,簇内活跃节点在属于自己的时隙内将检测到的数据直接发送至相应簇头。

簇头节点之间数据的传输采用动态规划的方法从根节点逐渐向叶子节点建立最短传输路由树。假设簇头节点的个数为n,每个簇头节点将检测的数据传输至其下一跳节点,即其父节点,直到传输至根簇头节点,建立一条最短传输路径。簇头节点之间数据的传输采用自由空间模型,即簇头节点到根簇头节点的最短传输距离表示簇头节点到根簇头节点的多跳距离的平方和最小。具体实现方案如下:

(1)根簇头节点的选取考虑簇头节点的剩余能量和到基站的距离,在满足能量大于簇头节点平均能量的簇头节点内选取到基站距离最近的簇头节点为根簇头节点,令其为s0,令其最短传输距离为0,即f(s0)=0。

(2)依此选取离根簇头节点s0距离最近的簇头节点sk,k=1,2,…,n-1,根据式(3)求出其到根簇头节点s0的最短传输距离f(sk),并保存其下一跳节点,即簇头节点sk的父节点,建立最短传输路由树。

其中,f(sk)代表簇头节点sk到根簇头节点s0的最短传输距离;d2(sk,uk(sk))代表簇头节点sk与属于集合uk(sk)中簇头节点的距离的平方;uk(sk)代表到根簇头节点s0的距离小于簇头节点sk到根簇头节点s0的距离的簇头节点集合;集合uk(sk)中满足使f(sk)最小的簇头节点为sk的下一跳节点,即簇头节点sk的父节点。

(3)当簇头节点有数据要传输时,根据簇间建立的最短传输路由树采用多跳的方式将检测的数据传输至根簇头节点s0,根簇头节点s0将接收的数据进行融合、汇聚,然后直接发送至基站。

4 仿真与分析

4.1 能耗模型

能量消耗模型使用一阶无线通信模式,如图3所示［12］。

图3 无线传感器网络能耗模型

在该模型下,每个节点发送l位数据消耗的能量为:

每个节点接收l位数据消耗的能量为:

其中,Eelec为发送(或接收)数据的单位能耗;εfs为自由空间模型的功率放大系数;εmp为多路衰减模型的功率放大系数。

4.2 实验参数

在无线传感器条件下采用 LEACH协议、文献［8］LEACH改进协议以及本文协议进行大量的仿真实验,实验在PC机上Matlab7.1中完成。具体仿真参数如下:

100个节点随机分布在100×100的矩形区域内,基站位于(50,50),节点的初始能量Eo=0.5 J,节点成为簇头的概率P=0.05,数据包的长度为4 000 bit,Eelec=50 nJ/bit,εfs=10 pJ/bit/m2,εmp=0.001 3 pJ/ bit/m4,节点处理数据的耗能EDA=5 nJ/bit/signal,簇头之间的最小距离dmin=30,虚拟网格的边长R=10。

4.3 性能分析

在相同实验环境下,对LEACH协议、文献［8］的LEACH改进协议以及MDG-LEACH协议进行仿真。

3种协议的节点存活数量与轮数的关系如图4所示。表1显示了3种协议分别在第一个节点死亡(First Node Dead,FND)、半数节点死亡(Half Node Dead,HND)、最后一个节点死亡(First Node Dead, LND)时所对应的轮数。由表1可知,MDG-LEACH协议第一个节点的死亡时间比LEACH协议和文献［8］LEACH改进协议提高了600%和450%;半数节点的死亡时间比LEACH协议和文献［8］LEACH改进协议分别提高了760%和580%;最后一个节点的死亡时间比LEACH协议和文献［8］LEACH改进协议提高了650%和510%。MDG-LEACH协议使能量较大的节点处于活跃状态,从而避免了能量较低的节点由于能量损耗过大而提前死亡,有效地延长了第一个节点的死亡时间,均衡了各节点的能量消耗。一般网络的生命周期可以定义为第一个节点、半数节点以及最后一个节点死亡时所对应的时间,不管定义多少个节点死亡时间为网络的生命周期,MDG-LEACH在延长网络寿命方面都明显优于LEACH协议和文献［8］的LEACH改进协议。

图4 存活节点个数与轮数的关系

表1 3种协议死亡节点与轮数的关系

3种协议的网络剩余总能量与轮数的关系如图5所示。由图5可知,每轮中MDG-LEACH协议网络剩余总能量大于LEACH协议和文献［8］LEACH改进协议。在1 500轮左右时,LEACH协议和文献［8］LEACH改进协议的网络总能量基本耗完,而MDGLEACH协议的网络剩余总能量约为40 J,总体能量消耗较LEACH协议以及文献［8］LEACH改进协议减少了80%。这是由于MDG-LEACH协议中每一轮活跃节点个数减少了,大大降低了每一轮消耗的总能量;簇头的选取考虑节点的能量和位置因素,使得簇头节点的分布更合理,网络能耗更均衡;簇头到基站的数据传输采用动态规划的方法建立最短传输路由树,大大减少了簇头在数据传输时的能量消耗。

图5 网络剩余总能量与轮数的关系

5 结束语

针对LEACH协议中活跃节点存在很高冗余度和能量消耗不均衡的问题,基于网格和分层思想,提出了一种基于多尺寸网格的分簇路由协议MDGLEACH。该协议根据节点检测半径、结合节点位置以及能量信息,将监测区域划分为多尺寸网格,在保证网络完全覆盖的情况下,减少了活跃节点的个数,降低了节点采集数据的冗余度;综合考虑节点剩余能量和空间分布情况选取簇头,均衡了各节点的能量消耗;簇头与基站之间采用动态规划的方法建立最短传输路由树进行数据的传输,减少了簇头节点的通信能量消耗。实验结果表明,MDG-LEACH有效地均衡了节点能量消耗、延长了无线传感器网络的生命周期。

［1］ 沈 波,张世永,钟亦平.无线传感器网络分簇路由协议［J］.软件学报,2006,17(7):1588-1600.

［2］ 贺智勇,龙陈锋,尹 乾.传感器网络中基于节点密度的分布式成簇算法［J］.计算机应用与软件,2008, 25(12):19-20,82.

［3］ 唐甲东,蔡 明.基于LEACH协议的能耗均衡路由算法［J］.计算机工程,2013,39(7):133-136,141.

［4］ 李芳芳,王 靖.一种基于LEACH协议的无线传感器网络路由算法［J］.传感技术学报,2012,25(10): 1445-1451.

［5］ Heinzelman W R,Chandrakasan A,Bala K H.Energy Efficient Communication Protocol for Wireless Microsensor Networks［C］//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences.Hawaii,USA:IEEE Press,2000.

［6］ Haneef M,Zhou Wenxun,Deng Zhongliang.MGLEACH:MultiGroupBasedLEACH anEnergy Efficient Routing Algorthm for Wireless Sensor Network［C］//Proceedings of the 14th International Conference on Advanced Communication Technology.Pyeongchang,Korea:［s.n.］,2012:179-183.

［7］ Chauhan R,Gupta V.Energy Efficient Sleep Scheduled Clustering&Spanning Tree Based Data Aggregation in Wireless Sensor Network［C］//Proceedings of the 1st InternationalConference on Recent Advances in Information Technology.Dhanbad,India:［s.n.］,2012: 536-541.

［8］ 单剑锋,庄琴清,陈 明.基于簇首概率优化的LEACH协议改进［J］.计算机技术与发展,2013, 23(2):138-140,144.

［9］ 李婵婵.无线传感器网络分簇路由协议研究［D］.南京:南京邮电大学,2013.

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

［11］ 何延杰,李腊元,邢明彦.WSN中一种能量均衡的分簇路由协议的设计［J］.传感技术学报,2009,22(10): 1510-1514.

［12］ 郭前岗,周得祥,周西峰.LEACH路由协议最优簇头数计算方法［J］.微型机与应用,2013,32(3):61-63,66.

编辑 任吉慧

Improvement of LEACH Protocol Based on Grids with Multiple Dimensions

LIU Guofan1,DING Yan2
(1.School of Electrical Information,Hunan Institute of Engineering,Xiangtan 411104,China;
2.College of Information Engineering,Xiangtan University,Xiangtan 411105,China)

A new energy efficient routing protocol of MDG-LEACH is proposed in the paper,which is based on the question of numerous redundancies with data collecting in nodes and imbalance of energy consumption in Low Energy Adaptive Clustering Hierarchy(LEACH) protocol.It selects active nodes based on virtual grids and multiple dimensions grids.Further,it adopts cluster head choice mechanism in overall consideration of residual energy and spatial distribution of nodes and establishes the shortest transmission route tree between cluster heads and base station by the dynamic programming method for date transmission.Simulation results show that MDG-LEACH protocol improves LEACH protocol and the improved LEACH protocol(Computer Technology and Development,2013,No.2)in balancing energy consumption of nodes and prolonging the life time of wireless sensor network effectively.

Low Energy Adaptive Clustering Hierarchy(LEACH)protocol;grids with multiple dimensions;active node;clustering;multihop;Matlab simulation

1000-3428(2014)11-0087-05

A

TP393.03

10.3969/j.issn.1000-3428.2014.11.017

湖南省科技计划基金资助项目(2012SK3173)。

刘国繁(1959-),男,教授,主研方向:传感器网络,嵌入式系统应用;丁 燕,硕士研究生。

2013-10-12

2014-01-06E-mail:liugf59@163.com

中文引用格式:刘国繁,丁 燕.基于多尺寸网格的LEACH协议改进［J］.计算机工程,2014,40(11):87-91.

英文引用格式:Liu Guofan,Ding Yan.Improvement of LEACH Protocol Based on Grids with Multiple Dimensions［J］.Computer Engineering,2014,40(11):87-91.