一种基于LEACH的无线传感器网络路由算法及仿真

苏俭华,刘宇红,徐跃州

(贵州大学电子信息学院,贵州贵阳550025)

一种基于LEACH的无线传感器网络路由算法及仿真

苏俭华,刘宇红,徐跃州

(贵州大学电子信息学院,贵州贵阳550025)

在低功耗自适应分簇(LEACH,Low Energy Adaptive Clustering Hierarch)算法中,由于每一轮循环都要重新构造簇,距离较远的簇头节点可能会因长距离发送数据而过早耗尽自身能量,能量较低的节点当选为簇头节点时将会加速该节点的死亡,影响整个网络的生命周期。针对LEACH算法分簇机制中存在的不足,提出了一种改进的路由算法。仿真结果表明,改进算法通过考虑节点的剩余能量与固定分簇的方法,有效的改善了网络能量均衡,提高了网络生存时间。

无线传感器网络 分簇路由算法 网络生存时间

0 引 言

无线传感器网络[1-3](WSN)是一种低功耗、低成本、低速率的无线通信网络,它由众多传感器节点以自组织方式组成,借助节点内置的传感器测量采集所在周边环境中我们感兴趣的物质现象的信息。并通过数据处理单元对采集信息进行处理,获得详尽准确的信息,最后将这些信息发送到需要它们的处理节点。用户通过终端的管理和分析软件来观测网络的运行状况,并且可以对网络中的各个节点进行管理和监控。

根据无线传感器网络自身的优势和特点,它在恶劣环境、无人区、资源受限等场景中具有得天独厚的应用价值,能够客观有效的获取物理信息,具有十分广阔的应用前景,可应用于军事国防、工农业控制、目标跟踪、智能家居、医疗健康、环境监测、防恐反恐、危险区域远程控制等诸多领域[4]。由于无线传感器网络节点的能力限制,以及节点能量无法补给的特点,因此设计一套有效的路由算法来提高能量效率是十分重要的[5]。

从网络逻辑结构角度可以将无线传感器网络路由算法分为平面路由和分簇路由。鉴于分簇路由算法具有良好的可扩展性,适用于大规模的WSN中,现研究主要重点集中在分簇路由算法上,而低功耗自适应分簇(LEACH)算法是比较成熟且具有代表性的层次路由算法。分簇路由算法中簇头节点的产生方式一直是人们研究的重点和热点,其中典型的有集中控制类算法LEACH-C[6],基本思想是全网节点直接与基站进行信息交互,基站根据得到的各个节点信息,然后结合全局信息来选择最优的簇头节点,但是由于各个节点每次都要与基站进行交互,这样额外增加了不少能量消耗;在文献[7]中李成岳等人提出的LEACH-T算法则是将簇头的产生依靠定时器产生一个随机时间间隔,拥有最短的时间间隔的节点将有更大概率成为簇头节点,该算法还将每轮簇头的个数固定在最优簇头数,有效的均衡了整个网络的能量,但是由于加入一个定时器,每轮簇头竞选时定时器产生的能耗也不容忽视且在硬件上实现增加了工艺的复杂性。

1 LEACH算法概述

LEACH[8](Low Energy Adaptive Clustering Hierarchy)算法是由MIT的Heinzelman等人提出的,它是一种为无线传感器网络设计的低功耗自适应聚类路由协议,是一种典型的层次路由协议。LEACH算法的基本思想是:减少与基站直接通信的节点个数,等概率随机性周期地选取网络的簇头节点,将整个网络的能耗均衡到各个节点上去,以此来降低全网的能耗,达到延长网络生存时间的目的。仿真表明, LEACH算法相较于一般的平面多跳路由协议,将网络生命周期提高了15%。

LEACH算法提出‘轮'的概念来描述簇的建立过程。每轮分为两个阶段:簇的建立和稳定传输阶段,且稳定传输阶段的持续时间要大于簇的建立时间。簇的建立过程可以分为4个阶段:簇头节点的选择、簇头节点的广播、簇头节点的建立和调度机制的生成。

LEACH算法簇头的选举过程是:节点产生一个大于0小于1的随机数,如果这个随机数小于设定的阈值T(n),那么这个节点成为簇头阶段。T(n)的计算公式如下:

其中:P是簇头节点的百分比;r是已经完成的轮数;G是1/P轮中没有成为簇头的节点集合;mod是求模运算。

LEACH算法是让网络中的节点自组织地形成簇,簇头是随机产生的。由于簇头的选择没有考虑剩余能量,若选择剩余能量小的节点做为簇头,则簇头节点会过早的死亡,当簇头节点失效时簇内的节点就停止数据发送,直到下轮簇头的重新选举。簇头节点的过早死亡,降低了网络的生存时间,影响整个网络性能。

2 改进算法

2.1 传送节点的选择

改进算法首先将目标区域以sink节点为圆心划分为K个半径为等差的子区域,然后将离sink节点最近的子区域标记为传送区域,在该区域将选取一个节点作为传送节点,在融合了各簇头节点的数据后转发给sink节点。传送节点选择条件为:Ds＜Do+,ΔS为等差半径。

当传送节点能量低于某一阈值时,重新选择一个能量较高的节点作为传送节点。一旦当选为传送节点,该节点将不再参与竞选簇头节点以及不再申请加入到其他簇内,可避免数据重复传送融合产生的能量开销。

当簇头节点离基站较远时,要以较大的功率发送数据,将导致簇头节点能量快速消耗,不利于网络能量的均衡。传送节点的出现避免了簇头节点直接与sink节点联系,降低了簇头节点过早死亡的概率,均衡了全网能量分布。

2.2 簇头选举

在选择簇头时,将节点的剩余能量和节点充当簇头节点的次数综合考虑进去。簇头节点的选择先从目标区域开始,随着时间的推移簇头选举范围以r为长度逐步往两侧扩展。x为目标ΔS区域的边界长,n为等差半径的子区域数。调整后簇头阈值计算方法:

其中,P是节点成为簇头节点的百分比;r是当前轮数;G是节点落在区域内过去1/P轮中没有当选为簇头节点的集合;Ec为当前节点剩余能量;E0为节点的初始能量,CH_Times为节点在以前回合中充当簇头的次数。

2.3 簇的形成

当簇头选定之后,簇头采用非持续CSMA(Carrier-sense Multiple Access)MAC协议向全网广播自己成为簇头的消息。其他普通节点在接收到各簇头的广播消息后,根据接收到的消息强度来决定加入某个簇头。并给簇头发送一个请求加入消息,消息中包含节点自身ID和剩余能量以及簇头ID号。簇头根据接收到的请求加入消息确定簇成员数,以此来为每个簇成员分配一个时隙,各成员节点只在相应的时隙内进行数据传输,在其他时间内进入休眠状态,减少能量开销。

2.4 数据传输

当簇形成后,节点将采集到的数据发送给簇头,簇头进行数据融合后再与传送节点通信,而不是直接与sink节点进行通信。原因是在单跳的通信方式中,若簇头距离sink节点过远,则将损耗较大功率发送数据不利于簇头的能量均衡。选择距离较近的传送节点转发保存了簇头的能量。

3 仿真结果分析

文中采用MATLAB软件对LEACH算法及改进后的算法(LEACH-S)进行仿真、分析和比较。由于实际应用环境中节点很难绝对平均分布,在此将选择100个节点随机分布于检测区域中,节点分布图如图1所示,仿真环境参数设置如表1所示。

图1 节点分布Fig.1 Node distribution

表1 仿真环境参数设置Table 1 Parameter settings of simulation environment

文中采用网络存活节点数和剩余节点总能量两个方面对比LEACH和新算法。为避免偶然性,对网络仿真数据采用多次求平均的方法来绘制效果图。网络总能耗随时间变化图,如图2所示。可以看出新算法的总能耗低于LEACH算法,这是由于优化了簇头的位置,采用了传送节点来与基站发送数据的方式,有效的节省了簇头的能量,均衡了全网的总能耗。

图2 网络节点剩余总能量随工作轮数变化Fig.2 Total remaining energy of network nodes changing as the working rounds

如图3所示,为网络存活节点数随时间变化图。在仿真实验中,若节点的剩余能量小于0则认为该节点死亡。据仿真结果,LEACH算法在612轮时第一个节点死亡,改进后的算法则是在940轮时出现节点死亡;比LEACH提高了53.6%。

图3 节点存活个数随工作轮数变化Fig.3 Number of survival nodes changing as the working rounds

表2给出了2种算法就网络中第一个节点死亡时间FND、50%节点死亡时间HND和70%节点死亡时间MND的对比。可以看出LEACH-S算法第一个节点死亡时间远晚于LEACH算法半数节点死亡时间,当网络中大部分节点死亡时,网络监测就失去了意义,网络生命周期实质上相当于结束。

表2 节点死亡时间比较Table 2 Dead time of nodes

4 结 语

文中对传统LEACH路由算法进行了分析,提出了簇头选择问题、能耗不均问题。针对LEACH算法的不足之处做了改进,并对新算法进行了仿真分析,

分析结果表明改进后的LEACH-S在延长网络节点的生存周期、均衡网络节点的能量消耗方面有明显改善,有效的延长了网络的生存时间,保证了有更多的节点同时监测、采集数据,提高了网络性能。

[1]李晓维,徐勇军,任丰原.无线传感器网络技术[M].北京:北京理工大学出版社,2007:24-25. LI Xiao-wei,XU Yong-jun,REN Feng-yuan.Wireless Sensor Network Technology[M].Beijing:Beijing Institute of Technology Press,2007:24-25.

[2]胡钢,朱佳奇,陈世志.无线传感器网络簇间节能路由算法[J].通信技术,2009,42(11):134-137. HU Gang,ZHU Qi-jia,CHEN Shi-zhi.Study on Power-Scant Cluster-Level Routing Algorithm of WSNBased on Clustered Network[J].Communications Technology, 2009,11(42):134-137.

[3]高伟,胡艳军.WSN中一种基于LEACH的协同通信算法的研究[J].通信技术,2010,43(10):81-83. GAO Wei,HU Yan-jun.A Cooperative Communication Algorithm Bsaed on LEACH in WSN[J].Communications Technology,2010,43(10):81-83.

[4]AKYILDIZ F,SU W,SANKARASUBRAMANIAM Y. Wireless Sensor Networks:A survey[J].Computer Networks,2002,38(04):393-422.

[5]张伟华,李腊元,张刘敏,等.无线传感器网络LEACH协议能耗均衡改进[J].传感技术学报,2008,11(21): 1918-1922. ZHANG Wei-hua,LI La-yuan,ZHANG Liu-min,etc. TheImprovement of LEACH Protocal Energy Balance in Wireless Sensor Networks[J].ChineseJournalofSensorsandActuators,2008,11(21):1918-1922.

[6]HEINZELMAN R W,CHANDRAKASAN A,BALKRISHNAN H.An Application-Specific Protocol Architectures for Wireless Microsensor Networks[D].IEEE Transaction on Wireless Communication,2002,1(4):660-670.

[7]李成岳,申铉京,陈海鹏,等.无线传感器网络中LEACH路由算法的研究与改进[J].传感技术学报, 2010,8(23):1163-1167. LI Cheng-yue,SHEN Xuan-jing,CHEN Hai-peng,ect. Research and Improvement of LEACH Routing Algorithm in Wireless Sensor Networks[J].ChineseJournalofSensorsandActuators,2010,8(23):1163-1167.

[8]WendiRabinerHeinzelman,AnanthaChandrakasan, HariBalakrishnan.Energy Efficient Communication Protocol for Wireless MicrosensorNetworks[C]//Proceedings of the 33rd Hawaii International Conference on System Sciences.Washington D C:IEEE Computer Society Press,2000:3005-3014.

苏俭华(1989—),女,硕士研究生,主要研究方向为无线传感器网络、嵌入式通信系统;

SU Jian Hua(1989-),female,graduate student,majoring in wireless sensor networks, embedded communications systems.

刘宇红(1963—),男,教授,硕士生导师,主要研究方向为信号与信息处理、宽带无线通信、语音与图像处理、DSP与嵌入式微处理器的应用研究、人工神经网络与模糊逻辑及智能化仪器和仪表的研究与开发;

LIU Yu-hong(1963-),male,professor,master tutor,majoring signal and information processing,broadband wireless communications,voice and image processing,application of DSP and embedded microprocessors,artificial neural networks and fuzzy logic and intelligent instruments.

徐跃州(1990—),男,硕士研究生,主要研究方向为无线传感器网络、无线通信技术。

XU Yue-zhou(1990-),male,graduate student,majoring in wireless sensor networks and wireless communication technology.

A Routing Algorithm and Simulation of WSN based on LEACH

SU Jian-hua,LIU Yu-hong,XU Yue-zhou
(College of Electronics and Information,Guizhou University,Guiyang Guizhou 550025,China)

LEACH algorithm is the typical layered routing protocol of WSN,as it reconstructed clusters each loop,the distant cluster head nodes could be out of work easily owing to long-distance-sending data.When the distant node is selected to the cluster head one,it could accelerate the death of the nodes,disrupting the network life cycle.Aiming at the defect of the LEACH algorithm clustering mechanism,a kind of improved routing algorithm is proposed.Experimental result indicates that with the residual energy of node and fixed clustering,the equipoise of network energy could be improved,and the network lifetime increased.

wireless sensor networks;cluster-based routing algorithm;network lifetime

TP393

A

1002-0802(2014)01-0060-04

10.3969/j.issn.1002-0802.2014.01.012