有效降低無線網絡節點能量的LEACH新算法

岑成龍，王 玫

(桂林電子科技大學通信研究所，廣西桂林541004)

無線傳感器網絡(WSN)是由大量具有通信和計算能力的微小傳感器節點，以無線的方式連接構成的自組測控網絡。它綜合了傳感器技術、嵌入式計算技術、分布式信息處理技術等多個學科，是新興的交叉研究領域。由于無線傳感器網絡具有自組性、可靠性、可擴展性和容錯性等特點成為了目前國際科學研究的熱點。傳感器節點的能量非常有限，對于如何提高節點的能量效率是面臨的主要挑戰。

對于如何提高無線網絡的能量效率，國內外的專家已進行了許多研究。文獻［1-2］中介紹了一種自組、自適應按簇分層的LEACH算法，該算法的不足之處是在選舉簇頭時沒有考慮節點的剩余能量。文獻［3］通過最優化鏈路層編碼和物理層調制來折中傳輸能量和電路能量，使網絡的總能量消耗降低。在文獻［4］中研究了單位成本條件下信道傳輸的最大比特數、比特傳輸能耗與傳輸數量及速率的關系。在文獻［5］中，介紹了基于CDMA的無線傳感器網絡最小能量消耗的問題，其能量消耗模型包括傳輸消耗的能量和電路消耗的能量兩方面，文中通過聯合最優化網絡中每個節點的傳輸能量和傳輸時間以使網絡的能量消耗達到最小。文獻［6］中，提出了一種將網絡節點分成多層簇的分簇算法。文獻［7］研究了無線傳感器網絡中進行中短距離信息傳輸時能量消耗對系統性能的影響。以上這些文獻在研究如何使網絡節點能量消耗達到最小時，都沒有考慮到節點收集到的信息冗余量過多的情況，本文在LEACH協議的基礎上，研究當節點收集到的冗余信息過多時，再進一步分簇，目的是將冗余信息剔除掉，從而降低節點的能量消耗。

1 LEACH協議

LEACH［1］(Low-Energy Adaptive Clustering Hierarchy)是MIT的Chandrakasan等人為無線傳感網絡設計的低功耗自適應分層路由算法。在LEACH算法中，將WSN中所有節點分成若干的簇，每個簇中選舉一個節點作為簇頭負責與基站通信。LEACH算法引入了“輪”的機制，每一輪分為簇形成階段和簇穩定階段。在簇形成階段，WSN中以一個給定的概率隨機地選舉節點成為簇頭，被選為簇頭的節點在網絡中就其身份進行廣播，其他非簇頭節點根據“就近原則”加入離它最近的簇中;分簇完成后，簇頭節點為簇中每個節點制定一個時序表，此時簇的形成階段結束。在簇穩定階段，所有的非簇頭節點根據簇頭節點制定的時序表按順序將自己收集到的數據發給所屬簇的簇頭節點，簇頭節點將收集到的所有數據進行融合后，再把數據發送給遠方的基站。由于簇頭節點需要消耗大量的能量，因此，在LEACH算法中，為了避免簇頭能量消耗過快，每個節點須輪流擔任簇頭。

2 新算法的描述

2.1 基于LEACH簇頭選舉閾值的改進

LEACH協議在選擇簇頭的時候沒有考慮節點的剩余能量這一因素，而LEACH在選舉簇頭時都是隨機的，這就有可能導致有的節點在剩余能量過少時被選作簇頭。而由于簇頭需要消耗大量的能量，從而加速了該節點的死亡。針對這一情況，在對LEACH協議在簇頭選舉時進行一些改進。在每一輪簇頭的選舉時，將節點的剩余能量這一因素考慮進來。LEACH算法在選擇簇頭時，每個節點首先隨機分配一個隨機數，只要這個隨機數小于規定的閾值T(n)就成為簇頭。這導致成為簇頭的節點數大大超過最優簇頭數kopt。簇頭節點數太多就會導致在分簇時，網絡節點消耗大量的能量進行分簇。為此，對LEACH算法規定的閾值T(n)做一些改進，使網絡的簇頭數降低從而節省因分簇而大量消耗的能量，并將節點的剩余能量考慮進來。文獻［1］中T(n)定義為

重新定義T(n)，其公式為

式中:p是網絡中簇頭所占的比例，p=0.05;r為當前的輪數，G是在最后1/p輪中沒有成為簇頭的節點集合;Eave表示每一輪所有非死亡節點剩余能量的平均值。改進后的式(1)可以降低節點成為簇頭的概率，從而節省分簇所要消耗的能量，達到延長網絡生命周期的目的。

2.2 基于剩余能量的LEACH二層簇頭的描述

為了使LEACH適合更大范圍的傳感器網絡，在LEACH第一層簇頭的基礎之上再次對網絡進行分簇。也就是在LEACH選出簇頭時，把LEACH的第一層簇頭再看作普通的節點，然后再對這些節點分簇并選出第二層的簇頭。這樣做的優點是:在大規模的網絡中，由于節點分布的密度較高，許多節點收集到的信息可能是重疊的，這很容易導致信息冗余。而在第一層簇頭的基礎之上再進行分簇就可以進一步將信息進行壓縮，這樣可以減少傳到基站的數據量，從而達到降低節點能量消耗的目的。

LEACH二層簇頭算法的思路是:在網絡節點中首先選舉第一層簇頭，這里選舉的第一層簇頭和LEACH算法選舉簇頭的思路一樣;所不同的是，被選舉為簇頭的節點在進行廣播時，將自己剩余能量的信息E(i)和坐標位置(xi，yi)一起進行廣播。然后所有的簇頭節點將自己的剩余能量E(i)和根據所收到信息中其他簇頭節點的剩余能量E(i)進行比較，將剩余能量最大的節點作為第二層的簇頭。

需要注意的是:因為第一層簇頭節點通過剩余能量E(i)的比較就可以知道第二層簇頭的身份和位置。因此，在選擇第二層簇頭時就不需要像第一層簇頭那樣進行身份廣播了。第一層簇頭根據E(i)的標記按順序將信息傳給第二層簇頭，而不是基站。

進行二層簇頭的改進是基于節點收集到的信息有較多重疊，也就是信息冗余。假設第一層簇頭收到的信息冗余量為x，當第一層簇頭將自己的全部信息傳給第二層簇頭時，第二層簇頭就會將這些冗余信息剔除掉，而將剩下的信息傳給基站。那么，LEACH二層簇頭算法每輪所消耗的能量為

式中:ECH1表示第一層簇頭的能量;ECH2表示第二層簇頭的能量;Enon-CH表示非簇頭節點的能量;k1表示第一層簇頭數;k2表示第二層簇頭數;Etot表示每輪節點消耗的總能量;M為區域邊長;N為節點數。

3 仿真實驗

實驗參數為:區域邊長M=100 m的正方形中，節點數n=200，基站的位置為(50，350)，數據長度l=4 000，控制包長度為100，發射電路和接收電路能量參數為ETx=ERx=Eele=50 nJ/bit，初始能量Eo=0.5 J，發射機放大器的參數為efs=10 pJ和emp=0.001 3 pJ，壓縮數據消耗的能量為EDA=5 nJ·bit-1·signal-1。圖1所示為LEACH與改進閾值后的LEACH存活節點數與時間關系的比較圖。在圖1中，改進后的LEACH算法出現第一個節點死亡是在r=108輪，最后一個節點死亡是在r=1 989輪;而LEACH算法出現第一個節點死亡是在r=101輪，最后一個節點死亡是在r=360輪。經過多次實驗發現:改進后的LEACH算法簇頭數目大約降低了40%，改進后的LEACH算法出現第一個節點死亡與原LEACH算法差不多，而改進后LEACH算法的生命周期比原LEACH算法生命周期提高了5倍。

圖1 LEACH與改進閾值后的LEACH存活節點數與時間關系的比較圖

如圖2所示為二層簇頭的LEACH、LEACH算法的生命周期與冗余度x的關系圖。從圖中可以看出當x≈0.8時，二層簇頭的LEACH與LEACH算法的生命周期相等。當x＜0.8時，LEACH算法的生命周期比二層簇頭的LEACH算法的生命周期長;當x＞0.8后，二層簇頭的LEACH算法的生命周期比LEACH算法的生命周期長，而且隨著x的增大，它們的生命周期差值越來越大。

圖2 LEACH、二層簇頭的LEACH生命周期與冗余度x的關系圖

如圖3、圖4所示為二層簇頭的LEACH與LEACH的對比圖。在圖3中，x=0.8，二層簇頭的LEACH出現第一個節點死亡的時間是在r=139輪，最后一個節點死亡的時間是在r=377輪，而LEACH出現第一個節點死亡時間是在r=101輪，最后一個節點死亡的時間是在r=360輪;當第一層簇頭節點數據冗余量為80%時，通過對比首輪節點的死亡輪數，可知采取二層簇頭的LEACH算法首輪節點死亡延遲了約38%。而且從圖中的曲線可以看出二層簇頭的LEACH算法使節點消耗的能量更加均衡。

在圖4中，假設x=1情況，也就是其他節點傳給第二層簇頭的信息都是冗余的情況。二層簇頭的LEACH出現第一個節點死亡的時間是在r=151輪，LEACH出現第一個節點死亡時間是在r=106輪，二層簇頭的LEACH出現首個節點死亡的時間比LEACH算法推遲了近50%;二層簇頭的LEACH最后一個節點死亡是在r=419輪，而LEACH最后一個節點死亡是在r=377輪，二層簇頭的LEACH的生命周期比LEACH算法的生命周期延長了11%。不僅如此，從圖4中可以看出:二層簇頭的LEACH算法的節點消耗的能量比LEACH算法節點消耗的能量更加均衡，這樣可以避免有的區域節點過早地死亡，而導致信息收集盲點區域。

4 結論

本文提出了基于LEACH的二層簇頭算法，繼承了LEACH按輪選舉簇頭的特點，在第一層簇頭的基礎之上再次分層選舉簇頭，使得網絡節點的能量消耗更加地均衡，彌補了LEACH算法個別節點消耗能量過快的不足，并且二層簇頭LEACH算法能進一步地剔除節點中的冗余信息，使需要傳輸到基站的數據量減少，從而節省了節點的能量，延長網絡生命周期。

［1］HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.Energyefficient communication protocol for wireless microsensor networks［C］//Proc.33rd HICSS.Hawaii:IEEE Computer Society，2000:3005-3014.

［2］HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Trans.Wireless Communications，2002，1(4):660-670.

［3］CUI S，GOLDSMITH A J，BAHAI A.Energy-constrained modulation optimization［J］.IEEE Trans.Wireless Commun，2005，4(5):2349-2360.

［4］VERDU S.On channel capacity per unit cost［J］.IEEE Trans.Inf.Theory，1990，36(5):1019-1030.

［5］SHU T，KRUNZ M，VRUDHULA S.Joint optimization of transmit power-time and bit energy efficiency in CDMA wireless sensor networks［J］.IEEE Trans.Wireless Communications，2006，5(11):3109-3118.

［6］BANDYOPADHYAY S，COYLE E J.An energy efficient hierarchical clustering algorithm for wireless sensor networks［C］//Proc.IEEE INFOCOM.San Francisco:IEEE Press，2003:1713-1723.

［7］CUI S，MADAN R，GOLDSMITH A J，et al.Cross-layer energy and delay optimization in small-scale sensor networks［J］.IEEE Trans.Wireless Commun，2007，6(10):3688-3699.