有效降低無線網(wǎng)絡(luò)節(jié)點(diǎn)能量的LEACH新算法

岑成龍，王 玫

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

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

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

1 LEACH協(xié)議

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

2 新算法的描述

2.1 基于LEACH簇頭選舉閾值的改進(jìn)

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

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

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

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

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

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

需要注意的是:因為第一層簇頭節(jié)點(diǎn)通過剩余能量E(i)的比較就可以知道第二層簇頭的身份和位置。因此，在選擇第二層簇頭時就不需要像第一層簇頭那樣進(jìn)行身份廣播了。第一層簇頭根據(jù)E(i)的標(biāo)記按順序?qū)⑿畔鹘o第二層簇頭，而不是基站。

進(jìn)行二層簇頭的改進(jìn)是基于節(jié)點(diǎn)收集到的信息有較多重疊，也就是信息冗余。假設(shè)第一層簇頭收到的信息冗余量為x，當(dāng)?shù)谝粚哟仡^將自己的全部信息傳給第二層簇頭時，第二層簇頭就會將這些冗余信息剔除掉，而將剩下的信息傳給基站。那么，LEACH二層簇頭算法每輪所消耗的能量為

式中:ECH1表示第一層簇頭的能量;ECH2表示第二層簇頭的能量;Enon-CH表示非簇頭節(jié)點(diǎn)的能量;k1表示第一層簇頭數(shù);k2表示第二層簇頭數(shù);Etot表示每輪節(jié)點(diǎn)消耗的總能量;M為區(qū)域邊長;N為節(jié)點(diǎn)數(shù)。

3 仿真實驗

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

圖1 LEACH與改進(jìn)閾值后的LEACH存活節(jié)點(diǎn)數(shù)與時間關(guān)系的比較圖

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

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

如圖3、圖4所示為二層簇頭的LEACH與LEACH的對比圖。在圖3中，x=0.8，二層簇頭的LEACH出現(xiàn)第一個節(jié)點(diǎn)死亡的時間是在r=139輪，最后一個節(jié)點(diǎn)死亡的時間是在r=377輪，而LEACH出現(xiàn)第一個節(jié)點(diǎn)死亡時間是在r=101輪，最后一個節(jié)點(diǎn)死亡的時間是在r=360輪;當(dāng)?shù)谝粚哟仡^節(jié)點(diǎn)數(shù)據(jù)冗余量為80%時，通過對比首輪節(jié)點(diǎn)的死亡輪數(shù)，可知采取二層簇頭的LEACH算法首輪節(jié)點(diǎn)死亡延遲了約38%。而且從圖中的曲線可以看出二層簇頭的LEACH算法使節(jié)點(diǎn)消耗的能量更加均衡。

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

4 結(jié)論

本文提出了基于LEACH的二層簇頭算法，繼承了LEACH按輪選舉簇頭的特點(diǎn)，在第一層簇頭的基礎(chǔ)之上再次分層選舉簇頭，使得網(wǎng)絡(luò)節(jié)點(diǎn)的能量消耗更加地均衡，彌補(bǔ)了LEACH算法個別節(jié)點(diǎn)消耗能量過快的不足，并且二層簇頭LEACH算法能進(jìn)一步地剔除節(jié)點(diǎn)中的冗余信息，使需要傳輸?shù)交镜臄?shù)據(jù)量減少，從而節(jié)省了節(jié)點(diǎn)的能量，延長網(wǎng)絡(luò)生命周期。

［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.