岑成龍，王 玫

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

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

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

1 LEACH協(xié)議

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

2 新算法的描述

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

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

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

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

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

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

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

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

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

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

3 仿真實驗

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

圖1 LEACH與改進閾值后的LEACH存活節(jié)點數(shù)與時間關系的比較圖

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

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

4 結論

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

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