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

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

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

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

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

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

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

1 相關(guān)工作

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

無(wú)線網(wǎng)狀網(wǎng)［4－5，7－9］(Wireless Mesh Network，WMN)也稱為多跳網(wǎng)絡(luò)，它是一種與傳統(tǒng)無(wú)線網(wǎng)絡(luò)完全不同的新型無(wú)線網(wǎng)絡(luò)技術(shù).WMN是由Mesh路由和Mesh客戶端組成.WMN有一些特點(diǎn)例如快速部署和易于安裝、非視距傳輸、健壯性、結(jié)構(gòu)靈活、高帶寬等.這樣它就可以在不便于被打擾的或者是高價(jià)的場(chǎng)合得到利用.如同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)，對(duì)WMN進(jìn)行重構(gòu)，構(gòu)建WSN中傳感器節(jié)點(diǎn)為網(wǎng)狀拓?fù)浣Y(jié)構(gòu)，將無(wú)線傳感器節(jié)點(diǎn)作為終端節(jié)點(diǎn)并通過(guò)WMN骨干網(wǎng)絡(luò)接入Internet，能夠形成WSN與WMN網(wǎng)狀全互聯(lián)的無(wú)線網(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的部署能夠概括成一個(gè)線性整數(shù)規(guī)劃問(wèn)題，并且在模型中部署Mesh路由和網(wǎng)關(guān)是一個(gè)NP問(wèn)題.文獻(xiàn)［1］提出了一種基于權(quán)重的啟發(fā)式算法將WSN和WMN相結(jié)合得到Mesh混合網(wǎng)絡(luò)的拓?fù)?，這樣在WMSN中就可以合理地部署Mesh路由器，有效地解決了WMSN的改善部署問(wèn)題.

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

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

2 LEACH算法簡(jiǎn)介

為了節(jié)省網(wǎng)絡(luò)的能量消耗，延長(zhǎng)節(jié)點(diǎn)的工作時(shí)間，均衡節(jié)點(diǎn)消耗的能量，Heinzelman等人提出了LEACH算法，其基本思想是每個(gè)周期內(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ì)過(guò)程如下所述.每個(gè)傳感器隨機(jī)選擇0～1之間的一個(gè)數(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è):①所有無(wú)線傳感器節(jié)點(diǎn)都是同構(gòu)的，具有數(shù)據(jù)轉(zhuǎn)發(fā)、接收和融合能力.②節(jié)點(diǎn)布設(shè)好以后，整個(gè)網(wǎng)絡(luò)不需要人工維護(hù).③所有無(wú)線傳感器初始能量相等.④無(wú)線傳感器單跳到達(dá)簇首，簇首單跳可達(dá)Mesh路由器.研究中不考慮基站和Mesh路由器的能量消耗.⑤無(wú)線傳感器、無(wú)線Mesh路由器和基站是靜止的.⑥無(wú)線傳感器的發(fā)射功率可控.⑦基于權(quán)重的啟發(fā)式算法，已經(jīng)完成WMSN的部署工作.

3.1 能量消耗模型

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

其中d0是一個(gè)閾值，式(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)測(cè)區(qū)域.根據(jù)公式(2)，當(dāng)基站距離簇首超過(guò)d0時(shí)，傳感器發(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路由器和基站均由電源供電，形成的通信樹(shù)如圖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時(shí)，LEACH算法應(yīng)用在WSN中比應(yīng)用在WMSN中消耗更多的能量，此時(shí)

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

4 仿真模型

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

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

圖4是LEACH算法應(yīng)用在WMSN和WSN中存活節(jié)點(diǎn)所占比例.當(dāng)LEACH算法應(yīng)用在WSN時(shí)，第1個(gè)節(jié)點(diǎn)在404輪時(shí)死亡，在1050輪時(shí)節(jié)點(diǎn)全部死亡.而LEACH算法應(yīng)用在WMSN中第1個(gè)節(jié)點(diǎn)在480輪時(shí)死亡，在930輪時(shí)節(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)的生命周期會(huì)得到延長(zhǎng).

5 結(jié)語(yǔ)

本文將LEACH算法應(yīng)用在WMSN，令LEACH算法產(chǎn)生的簇首直接和Mesh路由器或基站進(jìn)行通信，與應(yīng)用在WSN中的LEACH算法相比，能夠減少簇首的通信距離，降低能量消耗，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證，LEACH算法應(yīng)用在WMSN中能夠使網(wǎng)絡(luò)生命周期延長(zhǎng)約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ú)線傳感器網(wǎng)絡(luò)平臺(tái)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.

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

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

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