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

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

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

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

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

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

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

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

1 相關工作

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

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

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

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

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

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

2 LEACH算法簡介

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

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

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

3 LEACH算法在WMSN中的應用

采用基于以下前提的假設:①所有無線傳感器節(jié)點都是同構的，具有數(shù)據(jù)轉發(fā)、接收和融合能力.②節(jié)點布設好以后，整個網(wǎng)絡不需要人工維護.③所有無線傳感器初始能量相等.④無線傳感器單跳到達簇首，簇首單跳可達Mesh路由器.研究中不考慮基站和Mesh路由器的能量消耗.⑤無線傳感器、無線Mesh路由器和基站是靜止的.⑥無線傳感器的發(fā)射功率可控.⑦基于權重的啟發(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中的應用

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

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

在WMSN中由LEACH算法產(chǎn)生的簇首和最近的Mesh路由器或基站進行通信，然后Mesh路由器再將匯聚的數(shù)據(jù)轉發(fā)給基站，Mesh路由器和基站均由電源供電，形成的通信樹如圖2所示.Mesh路由器較均勻地部署在監(jiān)控區(qū)域內，簇首與Mesh路由器的距離小于d0，根據(jù)公式(2)，傳感器發(fā)送數(shù)據(jù)消耗的能量與發(fā)送距離的二次方相關，假設在WMSN中簇首發(fā)送數(shù)據(jù)到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中分別進行仿真，并對存活節(jié)點比例進行對比分析，仿真初始參數(shù)如表1所示:

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

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

5 結語

本文將LEACH算法應用在WMSN，令LEACH算法產(chǎn)生的簇首直接和Mesh路由器或基站進行通信，與應用在WSN中的LEACH算法相比，能夠減少簇首的通信距離，降低能量消耗，通過仿真實驗驗證，LEACH算法應用在WMSN中能夠使網(wǎ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ǎng)絡平臺3種拓撲結構的TinyOS實現(xiàn)［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－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.

(責任編輯梁志茂)

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.

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

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

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