LEACH算法在WMSN中的性能与仿真研究

吴琼，范菁，张翠，郝俊峰

(云南民族大学电气信息工程学院，云南昆明650031)

LEACH算法在WMSN中的性能与仿真研究

吴琼，范菁，张翠，郝俊峰

(云南民族大学电气信息工程学院，云南昆明650031)

低功耗自适应分簇(LEACH)算法是最早提出的分簇算法，将LEACH算法应用在无线网状传感器网络(Wireless Mesh Sensor Networks，WMSN)中，令簇首直接和Mesh路由器或基站进行通信.与应用在WSN中相比，可以减少簇首的通信距离，降低能量消耗.实验结果表明，LEACH算法应用在WMSN中能够有效地延长网络的生命周期.

无线网状传感器网络;LEACH算法;能量消耗;生命周期

1 相关工作

无线传感器网络［1－6］(Wireless Sensor Network，WSN)是由大量的微型传感器节点组成，通过无线通信方式形成的一个自组织的网络系统，其目的是协作地感知、采集和处理网络覆盖区域中被感知对象的信息，并发送给观察者.WSN有一些特点例如能量的限制、大规模、自组织、多跳路由、动态性网络、以数据为中心的网络等.

无线网状网［4－5，7－9］(Wireless Mesh Network，WMN)也称为多跳网络，它是一种与传统无线网络完全不同的新型无线网络技术.WMN是由Mesh路由和Mesh客户端组成.WMN有一些特点例如快速部署和易于安装、非视距传输、健壮性、结构灵活、高带宽等.这样它就可以在不便于被打扰的或者是高价的场合得到利用.如同WSN，WMN的部署策略非常严格，WMN的设计包括Mesh路由和网关的部署，有策略的放置和连接网关是非常重要的.

基于WMN原理，结合WSN的分簇拓扑结构特点，对WMN进行重构，构建WSN中传感器节点为网状拓扑结构，将无线传感器节点作为终端节点并通过WMN骨干网络接入Internet，能够形成WSN与WMN网状全互联的无线网状传感器网络［1］(Wireless Mesh Sensor Networks，WMSN)拓扑结构，WMSN网络拓扑结构如图1所示.

改善WMSN的部署能够概括成一个线性整数规划问题，并且在模型中部署Mesh路由和网关是一个NP问题.文献［1］提出了一种基于权重的启发式算法将WSN和WMN相结合得到Mesh混合网络的拓扑，这样在WMSN中就可以合理地部署Mesh路由器，有效地解决了WMSN的改善部署问题.

目前，无线传感器网络典型的分簇算法有LEACH［10］(Low Energy Adaptive Clustering Hierarchy)、PEGASIS［11］(Power Efficient Gathering in Sensor Information systems)、TEEN［12］(Threshold Sensitive Energy efficient Sensor Network)、APTEEN［13］(A-daptive Periodic TEEN)等算法，LEACH算法通过周期性地选择簇首节点来延长节点的工作时间，并实现节点的能耗平衡.PEGASIS算法通过将网络中的所有节点连接成一条链来避免频繁选举簇首的开销.TEEN算法和APTEEN算法都是对LEACH的改进，TEEN针对LEACH算法实时性不强的问题提出的一种解决方案.APTEEN算法综合了LEACH和TEEN的思想，提出了一种既可以周期采集数据，又可以实时采集数据的方法.

本文所描述的是将LEACH算法用在文献［1］提出的WMSN的无线传感器中，令簇首直接和Mesh路由器或基站进行通信.

2 LEACH算法简介

为了节省网络的能量消耗，延长节点的工作时间，均衡节点消耗的能量，Heinzelman等人提出了LEACH算法，其基本思想是每个周期内簇首被随机的选取，非簇首节点就近加入簇首成为簇成员，成员节点将数据发给簇首，由簇首负责将数据进行融合处理后再转发给其它节点做进一步的中继传输或直接传输到接收节点.

选举簇首的详细过程如下所述.每个传感器随机选择0～1之间的一个数，如果该值小于T(n)则成为簇首，T(n)的计算如式(1)所示:

在上式中，N是节点的数目，k是最优簇首数，r已完成的周期数，G是生存期内拥有的周期数.

3 LEACH算法在WMSN中的应用

采用基于以下前提的假设:①所有无线传感器节点都是同构的，具有数据转发、接收和融合能力.②节点布设好以后，整个网络不需要人工维护.③所有无线传感器初始能量相等.④无线传感器单跳到达簇首，簇首单跳可达Mesh路由器.研究中不考虑基站和Mesh路由器的能量消耗.⑤无线传感器、无线Mesh路由器和基站是静止的.⑥无线传感器的发射功率可控.⑦基于权重的启发式算法，已经完成WMSN的部署工作.

3.1 能量消耗模型

根据第1无线电能量模型，发射电路的发射能量:

其中d0是一个阈值，式(2)中，l是数据大小，Eelec为电路发射、接收每比特所需要的发射能量，d是传输距离，ξfs、ξmp为不同传输距离的衰减参数.

3.2 LEACH算法在WMSN中的应用

在WSN中由LEACH算法产生的簇首直接和基站进行通信，基站通常远离监测区域.根据公式(2)，当基站距离簇首超过d0时，传感器发送数据消耗的能量与发送距离的四次方相关.假设在WSN中簇首发送数据到基站消耗的能量为EWSN，则:

在式(3)中，dtoBS－WSN是在WSN中簇首到基站的距离.

在WMSN中由LEACH算法产生的簇首和最近的Mesh路由器或基站进行通信，然后Mesh路由器再将汇聚的数据转发给基站，Mesh路由器和基站均由电源供电，形成的通信树如图2所示.Mesh路由器较均匀地部署在监控区域内，簇首与Mesh路由器的距离小于d0，根据公式(2)，传感器发送数据消耗的能量与发送距离的二次方相关，假设在WMSN中簇首发送数据到Mesh路由器消耗的能量为EWMSN，则:

在式(4)中，dtoMesh－WMSN是在WMSN中簇首到Mesh路由器的距离.

当EWSN＞EWMSN时，LEACH算法应用在WSN中比应用在WMSN中消耗更多的能量，此时

当dtoBS－WSN和dtoMesh－WMSN满足式(6)时，LEACH算法应用在WSN中会消耗更多的能量，否则LEACH算法应用在WMSN中会消耗更多的能量.

4 仿真模型

对LEACH算法应用在WSN和WMSN中分别进行仿真，并对存活节点比例进行对比分析，仿真初始参数如表1所示:

表1 仿真初始参数

图4是LEACH算法应用在WMSN和WSN中存活节点所占比例.当LEACH算法应用在WSN时，第1个节点在404轮时死亡，在1050轮时节点全部死亡.而LEACH算法应用在WMSN中第1个节点在480轮时死亡，在930轮时节点全部死亡.在WSN中，基站远离控制区域，簇首发送数据到基站需要消耗较多的能量.而在WMSN中Mesh路由器和基站产生在控制区域内，簇首距离Mesh路由器或基站较近，直接将数据传送到Mesh路由器或基站消耗较少能量，所以和WSN相比，传感器节点的生命周期会得到延长.

5 结语

本文将LEACH算法应用在WMSN，令LEACH算法产生的簇首直接和Mesh路由器或基站进行通信，与应用在WSN中的LEACH算法相比，能够减少簇首的通信距离，降低能量消耗，通过仿真实验验证，LEACH算法应用在WMSN中能够使网络生命周期延长约20%.

［1］FAN Jing，YIN Shitang，WU Qiong.Study on refined deployment of wireless mesh sensor network［C］//Proceedings of International Conference on Wireless Communications，Networking and Mobile Computing.Piscataway: IEEE Press，2010:1－5.

［2］MOHAMED Y，AKKAYA K.Strategies and techniques for node placement in wireless Sensor networks:A survey［J］.Ad Hoc Networks，2008，6:621－655.

［3］BEJERANO Y.Efficient integration of multi－hop wireless and wired networks with QoS constraints［C］//The Annual International Conference on Mobile Computing and Networ-king(MobiCom).New York:ACM，2002:215－226.

［4］CHANDRA R，QIU L，JAIN K.Optimizing the placement of integration points in multi－hop wireless networks［C］// Proceedings of IEEE ICNP.Piscataway:IEEE Press，2004:271－282.

［5］李慧，高飞，王兵.HBE－ZigbeX无线传感器网络平台3种拓扑结构的TinyOS实现［J］.云南民族大学学报:自然科学版，2011，20(1):46－49.

［6］AKKAYA K，SENEL F，McLAUGHLAN B.Clustering of wireless Sensor and actor networks based on Sensor distribution and connectivity［J］.J Parallel Distrib Comput，2009，69:573－587.

［7］AKYILDIZ I F，WANG Xudong，WANG Weilin.Wireless mesh networks:a survey［J］.Computer Networks，2005，47:445－487.

［8］AOUN B，BOUTABA R，IRAQI Y.Gateway placement optimization in WMN with QoS constraints［J］.Journal on Selected Areas in Communications(JSAC):Special Issue on Multi－hop Wireless Mesh Networks，2006，11:2 127－2 136.

［9］HE Bing，XIE Bin，AGRAWAL D P.Optimizing deployment of Internet Gateway in Wireless Mesh Networks［J］.Computer Communications，2008，31:1 259－1 275.

［10］HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.Energy－efficient communication protocol for wireless microsensor networks［C］//the 33rd Hawaii International Conference on System Science.Piscataway:IEEE Press，2000:1－10.

［11］LINDSEY S，RAGHANENDRA C S.PeGASIS:Powerefficient gathering in sensor information system［C］//the IEEE Aerospace Conference，Aerospace and Electronic Systems Society.Piscataway:IEEE Press，2002，3: 1 125－1 130.

［12］MANJESHWAR A，AGARWAL D P.TEEN:a routing protocol for enhanced efficiency in wireless sensor networks［J］.1st Int’l.Wksp.On Parallel and Distrib.Comp.Issues in Wireless Networks and Mobile Comp.2001:2 009－2 015.

［13］MANJESHWAR A，AGARWAL D P.APTEEN:A hybird protocol for efficient routing and comprehensive information retrieval in wireless sensor network［C］//Proc Int’l Parallel and Distrib Proc Symp.Piscataway，IEEE Press，2002，2:195－202.

(责任编辑梁志茂)

Study on the Performance and Simulation of LEACH Algorithm in WMSN

WU Qiong，FAN Jing，ZHANG Cui，HAO Jun-feng
(School of Electrical and Information Technology，Yunnan University of Nationalities，Kunming 650031，China)

LEACH algorithm of low energy adaptive clustering hierarchy is the earliest algorithm of clustering，which this paper applies to the wireless mesh sensor networks(WMSN)，making the cluster head communicate with the mesh router or the base station directly.Compared with the application in WSN，the communication distance of the cluster head becomes shorter and the energy consumption becomes lower.Experiment results show that this algorithm can extend effectively the life cycle of the network when it is applied in WMSN.

WMSN;LEACH algorithm;energy consumption;life cycle

TP393.03

A

1672－8513(2011)04－0245－04

10.3969/j.issn.1672－8513.2011.04.002

2011－03－08.

国家自然科学基金(NSFC60963026);国家民委科研基金(09YN05);云南省教育厅科研基金重点项目(09Z0053，08Z0051).

吴琼(1986－)，男，硕士研究生.主要研究方向:无线传感器网络.

范菁(1976－)，女，博士研究生，副教授.主要研究方向:无线传感器网络.