吳瓊，范菁，張翠，郝俊峰

(云南民族大學(xué)電氣信息工程學(xué)院，云南昆明650031)

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

吳瓊，范菁，張翠，郝俊峰

(云南民族大學(xué)電氣信息工程學(xué)院，云南昆明650031)

低功耗自適應(yīng)分簇(LEACH)算法是最早提出的分簇算法，將LEACH算法應(yīng)用在無線網(wǎng)狀傳感器網(wǎng)絡(luò)(Wireless Mesh Sensor Networks，WMSN)中，令簇首直接和Mesh路由器或基站進(jìn)行通信.與應(yīng)用在WSN中相比，可以減少簇首的通信距離，降低能量消耗.實(shí)驗(yàn)結(jié)果表明，LEACH算法應(yīng)用在WMSN中能夠有效地延長網(wǎng)絡(luò)的生命周期.

無線網(wǎng)狀傳感器網(wǎng)絡(luò);LEACH算法;能量消耗;生命周期

1 相關(guān)工作

無線傳感器網(wǎng)絡(luò)［1－6］(Wireless Sensor Network，WSN)是由大量的微型傳感器節(jié)點(diǎn)組成，通過無線通信方式形成的一個自組織的網(wǎng)絡(luò)系統(tǒng)，其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中被感知對象的信息，并發(fā)送給觀察者.WSN有一些特點(diǎn)例如能量的限制、大規(guī)模、自組織、多跳路由、動態(tài)性網(wǎng)絡(luò)、以數(shù)據(jù)為中心的網(wǎng)絡(luò)等.

無線網(wǎng)狀網(wǎng)［4－5，7－9］(Wireless Mesh Network，WMN)也稱為多跳網(wǎng)絡(luò)，它是一種與傳統(tǒng)無線網(wǎng)絡(luò)完全不同的新型無線網(wǎng)絡(luò)技術(shù).WMN是由Mesh路由和Mesh客戶端組成.WMN有一些特點(diǎn)例如快速部署和易于安裝、非視距傳輸、健壯性、結(jié)構(gòu)靈活、高帶寬等.這樣它就可以在不便于被打擾的或者是高價的場合得到利用.如同WSN，WMN的部署策略非常嚴(yán)格，WMN的設(shè)計(jì)包括Mesh路由和網(wǎng)關(guān)的部署，有策略的放置和連接網(wǎng)關(guān)是非常重要的.

基于WMN原理，結(jié)合WSN的分簇拓?fù)浣Y(jié)構(gòu)特點(diǎn)，對WMN進(jìn)行重構(gòu)，構(gòu)建WSN中傳感器節(jié)點(diǎn)為網(wǎng)狀拓?fù)浣Y(jié)構(gòu)，將無線傳感器節(jié)點(diǎn)作為終端節(jié)點(diǎn)并通過WMN骨干網(wǎng)絡(luò)接入Internet，能夠形成WSN與WMN網(wǎng)狀全互聯(lián)的無線網(wǎng)狀傳感器網(wǎng)絡(luò)［1］(Wireless Mesh Sensor Networks，WMSN)拓?fù)浣Y(jié)構(gòu)，WMSN網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示.

改善WMSN的部署能夠概括成一個線性整數(shù)規(guī)劃問題，并且在模型中部署Mesh路由和網(wǎng)關(guān)是一個NP問題.文獻(xiàn)［1］提出了一種基于權(quán)重的啟發(fā)式算法將WSN和WMN相結(jié)合得到Mesh混合網(wǎng)絡(luò)的拓?fù)洌@樣在WMSN中就可以合理地部署Mesh路由器，有效地解決了WMSN的改善部署問題.

目前，無線傳感器網(wǎng)絡(luò)典型的分簇算法有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算法通過周期性地選擇簇首節(jié)點(diǎn)來延長節(jié)點(diǎn)的工作時間，并實(shí)現(xiàn)節(jié)點(diǎn)的能耗平衡.PEGASIS算法通過將網(wǎng)絡(luò)中的所有節(jié)點(diǎn)連接成一條鏈來避免頻繁選舉簇首的開銷.TEEN算法和APTEEN算法都是對LEACH的改進(jìn)，TEEN針對LEACH算法實(shí)時性不強(qiáng)的問題提出的一種解決方案.APTEEN算法綜合了LEACH和TEEN的思想，提出了一種既可以周期采集數(shù)據(jù)，又可以實(shí)時采集數(shù)據(jù)的方法.

本文所描述的是將LEACH算法用在文獻(xiàn)［1］提出的WMSN的無線傳感器中，令簇首直接和Mesh路由器或基站進(jìn)行通信.

2 LEACH算法簡介

為了節(jié)省網(wǎng)絡(luò)的能量消耗，延長節(jié)點(diǎn)的工作時間，均衡節(jié)點(diǎn)消耗的能量，Heinzelman等人提出了LEACH算法，其基本思想是每個周期內(nèi)簇首被隨機(jī)的選取，非簇首節(jié)點(diǎn)就近加入簇首成為簇成員，成員節(jié)點(diǎn)將數(shù)據(jù)發(fā)給簇首，由簇首負(fù)責(zé)將數(shù)據(jù)進(jìn)行融合處理后再轉(zhuǎn)發(fā)給其它節(jié)點(diǎn)做進(jìn)一步的中繼傳輸或直接傳輸?shù)浇邮展?jié)點(diǎn).

選舉簇首的詳細(xì)過程如下所述.每個傳感器隨機(jī)選擇0～1之間的一個數(shù)，如果該值小于T(n)則成為簇首，T(n)的計(jì)算如式(1)所示:

在上式中，N是節(jié)點(diǎn)的數(shù)目，k是最優(yōu)簇首數(shù)，r已完成的周期數(shù)，G是生存期內(nèi)擁有的周期數(shù).

3 LEACH算法在WMSN中的應(yīng)用

采用基于以下前提的假設(shè):①所有無線傳感器節(jié)點(diǎn)都是同構(gòu)的，具有數(shù)據(jù)轉(zhuǎn)發(fā)、接收和融合能力.②節(jié)點(diǎn)布設(shè)好以后，整個網(wǎng)絡(luò)不需要人工維護(hù).③所有無線傳感器初始能量相等.④無線傳感器單跳到達(dá)簇首，簇首單跳可達(dá)Mesh路由器.研究中不考慮基站和Mesh路由器的能量消耗.⑤無線傳感器、無線Mesh路由器和基站是靜止的.⑥無線傳感器的發(fā)射功率可控.⑦基于權(quán)重的啟發(fā)式算法，已經(jīng)完成WMSN的部署工作.

3.1 能量消耗模型

根據(jù)第1無線電能量模型，發(fā)射電路的發(fā)射能量:

其中d0是一個閾值，式(2)中，l是數(shù)據(jù)大小，Eelec為電路發(fā)射、接收每比特所需要的發(fā)射能量，d是傳輸距離，ξfs、ξmp為不同傳輸距離的衰減參數(shù).

3.2 LEACH算法在WMSN中的應(yīng)用

在WSN中由LEACH算法產(chǎn)生的簇首直接和基站進(jìn)行通信，基站通常遠(yuǎn)離監(jiān)測區(qū)域.根據(jù)公式(2)，當(dāng)基站距離簇首超過d0時，傳感器發(fā)送數(shù)據(jù)消耗的能量與發(fā)送距離的四次方相關(guān).假設(shè)在WSN中簇首發(fā)送數(shù)據(jù)到基站消耗的能量為EWSN，則:

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

在WMSN中由LEACH算法產(chǎn)生的簇首和最近的Mesh路由器或基站進(jìn)行通信，然后Mesh路由器再將匯聚的數(shù)據(jù)轉(zhuǎn)發(fā)給基站，Mesh路由器和基站均由電源供電，形成的通信樹如圖2所示.Mesh路由器較均勻地部署在監(jiān)控區(qū)域內(nèi)，簇首與Mesh路由器的距離小于d0，根據(jù)公式(2)，傳感器發(fā)送數(shù)據(jù)消耗的能量與發(fā)送距離的二次方相關(guān)，假設(shè)在WMSN中簇首發(fā)送數(shù)據(jù)到Mesh路由器消耗的能量為EWMSN，則:

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

當(dāng)EWSN＞EWMSN時，LEACH算法應(yīng)用在WSN中比應(yīng)用在WMSN中消耗更多的能量，此時

當(dāng)dtoBS－WSN和dtoMesh－WMSN滿足式(6)時，LEACH算法應(yīng)用在WSN中會消耗更多的能量，否則LEACH算法應(yīng)用在WMSN中會消耗更多的能量.

4 仿真模型

對LEACH算法應(yīng)用在WSN和WMSN中分別進(jìn)行仿真，并對存活節(jié)點(diǎn)比例進(jìn)行對比分析，仿真初始參數(shù)如表1所示:

表1 仿真初始參數(shù)

圖4是LEACH算法應(yīng)用在WMSN和WSN中存活節(jié)點(diǎn)所占比例.當(dāng)LEACH算法應(yīng)用在WSN時，第1個節(jié)點(diǎn)在404輪時死亡，在1050輪時節(jié)點(diǎn)全部死亡.而LEACH算法應(yīng)用在WMSN中第1個節(jié)點(diǎn)在480輪時死亡，在930輪時節(jié)點(diǎn)全部死亡.在WSN中，基站遠(yuǎn)離控制區(qū)域，簇首發(fā)送數(shù)據(jù)到基站需要消耗較多的能量.而在WMSN中Mesh路由器和基站產(chǎn)生在控制區(qū)域內(nèi)，簇首距離Mesh路由器或基站較近，直接將數(shù)據(jù)傳送到Mesh路由器或基站消耗較少能量，所以和WSN相比，傳感器節(jié)點(diǎn)的生命周期會得到延長.

5 結(jié)語

本文將LEACH算法應(yīng)用在WMSN，令LEACH算法產(chǎn)生的簇首直接和Mesh路由器或基站進(jìn)行通信，與應(yīng)用在WSN中的LEACH算法相比，能夠減少簇首的通信距離，降低能量消耗，通過仿真實(shí)驗(yàn)驗(yàn)證，LEACH算法應(yīng)用在WMSN中能夠使網(wǎng)絡(luò)生命周期延長約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－h(huán)op 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－h(huán)op wireless networks［C］// Proceedings of IEEE ICNP.Piscataway:IEEE Press，2004:271－282.

［5］李慧，高飛，王兵.HBE－ZigbeX無線傳感器網(wǎng)絡(luò)平臺3種拓?fù)浣Y(jié)構(gòu)的TinyOS實(shí)現(xiàn)［J］.云南民族大學(xué)學(xué)報(bào):自然科學(xué)版，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－h(huán)op 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.

(責(zé)任編輯梁志茂)

Study on the Performance and Simulation of LEACH Algorithm in WMSN

WU Qiong，F(xiàn)AN 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.

國家自然科學(xué)基金(NSFC60963026);國家民委科研基金(09YN05);云南省教育廳科研基金重點(diǎn)項(xiàng)目(09Z0053，08Z0051).

吳瓊(1986－)，男，碩士研究生.主要研究方向:無線傳感器網(wǎng)絡(luò).

范菁(1976－)，女，博士研究生，副教授.主要研究方向:無線傳感器網(wǎng)絡(luò).