一種改進的無線傳感器網絡LEACH協議及仿真

王巧玲　曾春華

摘 要： 針對無線傳感器網絡經典LEACH協議中簇首數目選擇及通信方面的不足，提出一種改進的M-LEACH算法，對如何動態確定最優簇數目進行了研究，分析了影響最優簇數目的因素，推導出了最優簇首比例公式，同時給出了一種能量均衡的無線傳感器網絡分簇路由算法。仿真實驗結果表明，與經典LEACH協議相比，運行M-LEACH協議后能夠減少網絡能耗和均衡網絡能耗，延長網絡的生命周期。

關鍵詞： 無線傳感器網絡；LEACH協議；簇首選取；網絡生命周期

中圖分類號：TP393。01 文獻標識號：A 文章編號：2095-2163（2014）05-

A Modified LEACH Protocol and Simulation for Wireless Sensor Networks

WANG Qiaoling， ZENG Chunhua

（College of Science， Jiangxi Agricultural University， Nanchang 330045， China）

Abstract： Aiming at the efficiency of cluster head election and communications in the classical LEACH protocol for Wireless Sensor Networks （WSN）， an improved M-LEACH algorithm is proposed。 In this algorithm， the factors affecting the optimal number of clusters are analyzed， and also the optimal proportion of cluster head is deduced， further an energy balanced routing algorithm for WSN is proposed。 The simulation result shows that the improved M-LEACH algorithm can reduce and balance the network energy consumption effectively comparing with classical LEACH， therefore can prolong the lifetime of the network。

Keywords： Wireless Sensor Networks； LEACH Protocol； Cluster Head Election； Network Lifetime

0 引 言

無線傳感器網絡（Wireless Sensor Networks， WSN）是由大量具有通信與計算能力的微小傳感器節點以大區域、高密度方式而布設在無人值守的監控區域所構成的能夠根據環境自主完成指定任務的“智能”自治測控網絡系統[1]。而且由于WSN能夠聯合協作地實時監測、感知并采集分布在區域內的監測對象的信息，再傳輸給需要信息的基礎用戶，已經廣泛地應用于各大領域，諸如國防軍事、國家安全、環境監測、醫療監護、空間探索、交通管理、森林火險監測、智能家居等多個方面[2]。但由于傳感器節點在能量、存儲、計算和通信能力上仍較為有限，且WSN還具有節點多、資源受限、多跳路由、動態變化等具體特點，若要實現能量高效的數據傳輸，以及同時提高網絡的健壯性和擴展性，有效的針對方法之一就是將網絡劃分為簇，且通過簇首對數據的融合而減少傳輸的數據量，由此即可降低網絡能量消耗、并節約帶寬等有限資源[3]。接下來的分析還可知道，由于允許鄰居節點在發送給基站前能夠實現數據信息共享，且簇首節點也能夠對簇成員節點的信息進行高效融合，這就使得基于簇的路由算法相對平面路由算法能節約能耗，進而更延長了網絡的生命周期。此外，還因為分簇的拓撲結構可以容忍個別節點的失效，隨之即使得網絡具有了較好的適應性和穩定性，并且路由和控制開銷也會較少，在移動管理和網絡的局部同步的實現上也將相對容易一些。只是目前大多數層次路由算法僅僅根據節點當前的信息（如剩余能量）簡單隨機地選擇簇首，卻忽略了周圍鄰居節點的信息及網絡剩余能量的均衡性，為此而導致某些簇頭節點負載較重、進而成為瓶頸，具體后果即是嚴重降低了網絡的生命周期。因此對WSN進行有效分簇已然成為當前的研究熱點[4]。

綜上所論可知，為了避免部分節點過早死亡而導致整個網絡失效，簇首的負載要盡可能地均衡，同時簇數目的選取及簇首的分布也要合理。因此，研究過程就需要綜合考慮各種因素以最佳確定簇首數目和簇首分布。不言而喻，這是研究開展的核心關鍵所在。

1 相關工作及問題描述

1.1 相關工作

分簇算法是WSN分簇路由協議設計中的關鍵技術，若將其依據不同基準，則有各種分類方式。具體來說，如果按照不同參數選擇簇頭可分為基于節點剩余能量、節點ID、最高連接數、節點位置、節點的權重等；如果另按算法的執行方式可分為集中式（在基站執行）和分布式，而分布式的分簇算法又可分為概率式（如LEACH）[5]和迭代式（如HEED）[6]兩大類。其中，LEACH協議采用周期性隨機選取簇首的機制，簇內成員節點在自己的TDMA時隙可將數據發送給簇首，其余時間則進入休眠狀態，并且簇首對數據融合后將直接發送給基站。與平面路由和靜態路由相比，該算法既節省了能耗，又延長了網絡生存時間，但也存在相應不足[7]，對其分析論述如下：

（1）節點以相同的概率選擇充當簇首，因此剩余能量小的節點負載過重，可能過早死亡，如此將影響網絡的壽命和健壯性；

（2）所有節點采取單跳方式發送數據，使得某些距基站較遠的節點能量開銷較大，即將導致網絡能量分布不均衡。

而HEED成簇路由通過采用混合簇頭選舉機制，同時考慮了節點的剩余能量和鄰節點的度，尤其做到了平衡能量消耗和簇首節點的均勻分布而延長了網絡的壽命，但卻未曾考慮到最優簇數目的問題。

分簇算法中最優簇數目的確定將直接影響著網絡的壽命，然而現有的大多數成簇算法對于最優簇數目沒有施與充分的考慮。研究表明[8]，簇數目的最優值kopt是存在的。一方面，若分成簇的數目小于kopt，則簇內成員節點將會由于距簇頭太遠而在數據傳輸過程中使能量耗盡，或在還未接受到足夠數量的節點反饋信息時簇首就開始為其他節點分配TDMA時隙，而將形成冗余通信而造成能量的浪費；另一方面，若簇數目大于kopt，則將無法達到WSN分層結構減少數據傳輸量的設計效果[9]。實際上，在經典LEACH協議中，簇數目只是固定的比例，而沒有考慮節點剩余能量及鄰居節點的狀態。但已有文獻[10]從平衡網絡負載均衡程度對的角度來優化簇數目，也就是通過設置定時器將節點的剩余能量和簇頭比例聯系起來，使剩余能量大的節點成為簇頭的概率也相應增大，且仿真實驗表明隨著簇頭比例的增大，負載均衡程度也已出現大幅增加。另有文獻[11]利用概率知識推導了最優簇數目，并指出若未按最優方式分簇，即會導致網絡消耗的能量呈指數增長。雖然如此，但上述算法卻都依然我能獲得網絡能耗良好均衡的實現。有鑒于此，本文將重點給出有針對性的完整研究稱，而且經過仿真測試，得到了理想的實驗結果，

1.2 問題描述

（1） 系統模型

為了簡化問題模型，本文對要研究的無線傳感器網絡作以下假設：

①所有節點隨機部署在監測區域，部署后節點和基站是靜止的；

②除Sink節點外，每個節點的能量有限、初始能量相同、地位平等；

③每個節點均有唯一的標識ID，且剩余能量和位置可以感知；

④除基站外所有節點的有效通信范圍相同，節點間的通信鏈路是雙向的。

將無線傳感器網絡抽象為一個無向加權圖G=（V，E），其中V為傳感器節點的集合，V={vi|i=1，2…N}，且N為傳感器節點的個數；E則是邊的集合，E={（vi，vj）|（vi，vj）VV，ij}。

（2） 能量模型

本文采用文獻[11]中的節點工作能耗模型來計算網絡的能量消耗。每發送l bit的信息到距離為d的節點所消耗的能量為：

ET（l， d）=ET-elec（l）+ET-amp（l， d）= （1）

在式（1）中，Eelec表示發射裝置和接收電路每發送或接收單位bit的能量消耗；fs和mp表示發射放大器將每bit數據傳送單位平方米所耗的能量；d0是傳輸距離的門限值，并且 。若傳輸距離小于閾值d0時，功率放大損耗采用自由空間模型；而當傳輸距離大于等于閾值d0時，即采用多路徑衰減模型。

傳感器節點每接收l bit信息所消耗的能量可計算為：

ER（l）=ER-elec（l）=Eelecl （2）

因此，將l bit的數據從節點ni傳輸到nj消耗的能量可表示為：

Ei， j（l）=ER（l）+ET（l， d） （3）

（3） 問題描述

定義1 節點vi與vj之間的距離dij可用公式（4）進行計算，其中（xi， yi）和（xj， yj）分別表示節點vi、vj的坐標。

（4）

定義2 設傳感器節點的通信半徑為R，節點i、j間的距離為d（j， i），若d（j， i）R則稱節點i、j互為鄰居節點，記節點i的鄰居節點集合為N（i），即N（i）={jd（j， i）R}。

研究目的旨在建立一個能量均衡的WSN簇拓撲結構，從而實現整個網絡中節點剩余能量的均衡，并延長網絡的生命周期，因此在分簇過程中應加入對最優簇數目的考慮。問題就是如何在能量約束的前提下確定最優簇數目及通過優化得到最優簇首，而且在均衡整個網絡能量的同時使得網絡消耗的能量最小。本文主要討論均勻分布下最優簇數目的確定及影響最優簇數目的主要因素，同時還通過仿真實驗對改進最優簇數目后的算法與經典LEACH相比而對網絡性能的影響展開分析，并給出結論。

2 改進簇首選擇后的分簇算法

2.1 最優簇數目的確定

設有n個節點均勻分布在面積為A=2a2a的正方形監測區域中，并假定：

（1）數據包長度相同，且不考慮重發和碰撞所消耗的能量；

（2）基站處于區域的中心，并且成員節點到CH的距離和CH到Sink節點的距離d都滿足dd0。

各輪循環傳輸l bit數據時，每個簇頭節點消耗的能量ECH主要包括：接收簇內節點信息所消耗的能量、進行數據融合所消耗的能量和將融合后的數據發送到基站消耗的能量。在此，設簇的數目為k，則平均每個簇中的成員節點為N1=n/k1，每輪中每個CH節點消耗的能量將為ECH=（nk1） Eelecl+nkEDAl+Eelecl +lfsdBS2，而單輪中每個非簇首節點消耗的能量即為Enon-CH=lEelec+lfsdCH2。其中，dBS是簇首節點到基站的平均距離，dCH則是成員節點到CH節點的平均距離。現對 dBS和dCH的運算過程可做如下呈現：

dBS= = =0。765a

dCH2= （5）

其中，（x，y）是節點的分布密度函數，每輪循環節點傳輸l bit數據時每個簇消耗的能量ECluster= ，因此網絡消耗的總能量為：

Etotal=kECluster= （6）

求Etotal對k的一階導數，并令其等于零，得

=0

由其可得到最優簇數目，具體公式為：

（7）

進一步地，最優簇的比例則表示為：

（8）

2.2 M-LEACH路由算法

分簇路由包括簇的生成（Cluster formation）和數據傳輸（Data transmission）兩個過程。其中，簇的生成又可分為初始化簇首、初始簇首收集簇成員信息、最優簇形成、及穩定運行等四個技術階段；而數據傳輸則可分為簇內傳輸和簇間路由兩個階段。

（1） 初始化簇首階段

首先選擇候選簇首節點構成初始簇首集合，只有候選簇首才有可能成為本輪的簇首。設Scandidate表示候選簇首的集合，定義：

Scandidate={ni|Ei>E} （9）

其中：

E= （10）

式中，N為網絡中節點的數目；Ei表示節點i的當前剩余能量，也就是只有大于當前平均剩余能量的節點才有機會成為候選簇首。

（2） 收集簇成員信息階段

成員節點將自身的剩余能量、位置及ID號等信息通過候選簇首發送至基站，于是每個候選簇首節點即已獲得鄰居節點的ID、位置和剩余能量等必要信息。

（3）簇的形成階段

采用2.1中優化后的簇首數目選擇簇首，基站會將最優簇首集合和簇的結構廣播出去，每個非簇首節點則根據收到信號的強弱選擇加入哪個簇，同時再將自己的位置和剩余能量等信息發送給簇首節點，即會等待CH節點分配TDMA時隙，以避免數據信息的沖突。簇成員節點在相應的時隙內就會將數據包發送給CH節點，而在發送時間外則將關閉收發設備，進入休眠狀態，以減少消量消耗。

（4） 穩定運行階段

當最優簇首集形成后，就進入穩定運行階段。而在CH節點接收到了所有成員節點的數據后，即將數據融合后再通過簇間傳輸發送至基站。形成的簇經過一段時間運行后則很難保證所有簇成員節點能量消耗的平衡，此時若出現簇首節點的當前剩余能量低于門限值時，將重新選舉簇首。

由于M-LEACH算法在優化簇首選擇階段充分考慮了節點本身及鄰居節點的位置和剩余能量等信息，因此就能夠平衡簇成員節點間的能量消耗，進而有效避免盲節點的產生，并在一定程度上可防范網絡空洞的出現。

3 M-LEACH算法的仿真分析

通常，分簇算法的性能評估主要參照如下指標：網絡的生存周期、每輪存活的節點數目、吞吐量、可靠性，等。基于此，本文即在探討與分析參數對最優簇數目的影響及改進最優簇數目后的路由協議對網絡能耗和生命周期影響的基礎上，又對仿真結果進行了比較和分析。

3.1 仿真環境及參數設置

采用的仿真工具是Matlab 7。0，仿真環境為：n個傳感器節點隨機均勻分布在二維平面2a2a（單位：m2）的正方形監測區域中，假定基站的能量足夠大，通信半徑可以覆蓋整個網絡，普通傳感器節點的能耗模型則采用1.2中的能量模型，并按公式（1）計算能耗，模型中各個參數的取值即如表1所示。

表1 能量模型參數設置表

Tab.1 Value of parameters in energy model

參數 Eelec EDA fs mp E0

取值 50nJ/bit 5nJ/bit 100pJ/bit/m2 0。0013pJ/bit/m4 0。5J

3.2 最優簇數目對網絡生命周期的影響

設100個節點隨機分布在100m100m的監測區域中，基站位于區域的中心（50，50）處。每輪發送數據包的長度l=1 000bit，仿真經過一定輪數后計算網絡中存活節點的個數。此時再改變網絡運行的最大輪數，每個實驗重復10次，取平均存活的節點個數，由此而得到了采用改進最優簇數目后的LEACH與經典LEACH協議網絡生命周期的對比曲線則如圖1所示。

圖1 M-LEACH算法與LEACH協議網絡的生命周期對比

Fig. 1 Network lifetime comparison of M-LEACH and LEACH

圖1表明，從網絡開始運行即知，M-LEACH與經典LEACH相比，網絡中第一個節點死亡經過的輪數出現了增加，因此網絡的生命周期就得到了延長。另外，運行經過相同的輪數時，網絡中存活的節點數將比LEACH增長大約20%，這是由于在優化簇數目時已經初步考慮了網絡總的能量消耗。

4結束語

本文主要討論了影響最優簇數目的因素以及均勻分布下最優簇數目的確定，在動態優化簇首選擇的過程中，不僅考慮了候選節點的剩余能量，而且將其余節點到候選簇首的距離及其余節點剩余等因素考慮在內，更好地保證網絡負載均衡，因而在一定程度上避免網絡空洞的出現。仿真結果表明，最優簇數目與監測區域的面積、網絡中的節點數等因素直接有關；而且通過與經典LEACH協議仿真對比可知，經過相同輪數后，改進最優簇數目的LEACH后網絡運行的生命周期得到延長。但由于頻繁構造簇又形成了一定的能量消耗，未來研究時則需提升對該問題的關注和研究力度。

參考文獻

[1] 于海斌，曾鵬，等.智能無線傳感器網絡系統[M].北京：科學出版社，2006：5-6.

[2] JENNIFER Y， BISWANATH M， DIPAK G. Wireless sensor network survey [J]. Computer Networks， 2008（52）： 2292–2330.

[3] MATROUK K， LANDFELDT B. RETT-gen： a globally efficient routing protocol for Wireless Sensor Networks by equalising sensor energy and avoiding energy holes [J]. Ad Hoc Networks，2009， 7： 514-536.

[4] AKKAYA K， YOUNIS M. A survey of routing protocols in Wireless Sensor Networks [J]. Ad Hoc Networks， 2005， 3（3）：325-349.

[5] HEINZELMAN W R， CHANDRAKASAN A， BALAKRISHNAN H. Energy efficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rd Annual International Conference on System Sciences， 2000（2）： 1-10.

[6] YOUNIS O， FAHMY S. HEED： a hybrid energy-efficient， distributed clustering approach for ad hoc sensor networks [J]. IEEE Transactions on Mobile Computing， 2004，3（4）： 366—379.

[7] LINDSEY S， RAGHAVENDRA C， SIVALINGAM K M0 Data gathering algorithms in sensor networks using energy metrics [J].IEEE Transactions on Parallel and Distributed Systems，2002， 13 （9）： 924- 935.

[8] 郝曉辰，房 艷，劉浩然，等.一種無線傳感器網絡的簇數目優化方法[J].傳感技術學報，2008，21（8）：1432-1436.

[9] 吳臻， 金心宇.無線傳感器網絡LEACH算法的改進[J].傳感技術學報，2006， 19（1）： 34-36.

[10] KUMAR D， ASERI T C， PATEL R B. EEHC： Energy efficient heterogeneous clustered scheme for wireless sensor networks [J]. Computer Comunications， 2009，32（4）：662-667.

[11] HEINZELMAN W B， CHANDRAKASAN A P， BALAKRISHNAN H. An application specific protocol architecture for wireless microsensor networks [J].IEEE Transactions on Wireless Communications， 2002， 1（4）：660-670.