無線傳感器網(wǎng)絡(luò)能耗均衡LEACH路由算法

李建坡 姜 雪 朱緒寧

(東北電力大學(xué)信息工程學(xué)院，吉林 吉林 132012)

0 引言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)最關(guān)心的問題之一是在能量有限的情況下盡可能地延長網(wǎng)絡(luò)生命周期［1］。WSN路由協(xié)議分為平面路由協(xié)議和分簇路由協(xié)議。平面路由協(xié)議算法簡單，易于實(shí)現(xiàn)，但一般需要犧牲存儲空間維持大量的路由表，這增加了通信負(fù)擔(dān)，造成信息冗余及擁塞，使能量損耗增大、延遲加長［2］。分簇路由通過簇頭對簇內(nèi)節(jié)點(diǎn)間的信息融合及轉(zhuǎn)發(fā)機(jī)制來減少數(shù)據(jù)的傳輸量和距離，進(jìn)而降低通信能量，達(dá)到節(jié)能的目的。低能量自適應(yīng)分簇路由協(xié)議(low energy adaptive clustering hierarchy，LEACH)是比較成熟常用的分簇路由算法。該算法簇頭可隨機(jī)選擇并定期更換，這在一定程度上實(shí)現(xiàn)了節(jié)點(diǎn)的負(fù)載平衡，延長了網(wǎng)絡(luò)的生命周期，可以更好地進(jìn)行資源分配，是一種優(yōu)化能量使用效率的算法。

1 LEACH路由算法

LEACH算法是針對無線傳感器網(wǎng)絡(luò)設(shè)計的一種低功耗自適應(yīng)的分簇路由算法，它是第一個在無線傳感器網(wǎng)絡(luò)中提出的層次式路由協(xié)議。由于短距離通信比較節(jié)約能量，因此在LEACH算法中，更多的通信都是局限在簇的內(nèi)部，只有少數(shù)簇頭節(jié)點(diǎn)才和遠(yuǎn)處的基站進(jìn)行遠(yuǎn)距離通信［3］。同時，LEACH算法采用分簇的自適應(yīng)技術(shù)和簇頭節(jié)點(diǎn)的輪換技術(shù)，使得網(wǎng)絡(luò)的載荷分布相對比較均衡，能夠延長網(wǎng)絡(luò)的生命周期。另外，LEACH算法在每個簇內(nèi)部可以進(jìn)行本地計算和處理，去除數(shù)據(jù)中的冗余成分，減輕簇頭節(jié)點(diǎn)的通信負(fù)擔(dān)，所需能耗要遠(yuǎn)遠(yuǎn)小于通信能耗。

當(dāng)研究低功耗的無線通信時，不同的通信特征和假設(shè)模型會很大程度地影響算法性能。在LEACH算法的仿真過程中，使用的硬件能耗模型如圖1所示［4－5］。

圖1 LEACH通信功耗模型Fig.1 Communication energy consumption model of LEACH

收發(fā)電路處理1 bit數(shù)據(jù)所消耗的能量為:

發(fā)射放大電路向單位面積發(fā)送1 bit數(shù)據(jù)所消耗的能量為:

在d距離內(nèi)處理k比特的信號，發(fā)送消耗的總能量為:

接收時消耗的總能量為:

由以上公式可以看出，接收一個分組的能耗與數(shù)據(jù)量及通信距離有很大的關(guān)系。因此，在算法設(shè)計中不僅要盡量減少通信距離，而且要盡量減少所要傳輸?shù)臄?shù)據(jù)量。

2 改進(jìn)的LEACH路由算法

LEACH算法是一個用來優(yōu)化能量使用效率的協(xié)議體系，它具有許多優(yōu)點(diǎn)。但LEACH算法也有它的不足之處，主要體現(xiàn)在以下幾個方面。

①每輪都要先確定簇頭節(jié)點(diǎn)，然后建立簇，期間用于建立簇的通信開銷較大。由于LEACH算法的簇頭選舉機(jī)制沒有考慮到具體地理位置，這使得簇頭節(jié)點(diǎn)不能均勻地分布在整個網(wǎng)絡(luò)中，無法做到最優(yōu)。

②簇頭的選舉是等概率產(chǎn)生的，沒有考慮到不同節(jié)點(diǎn)之間能量的差異。如果能量低的節(jié)點(diǎn)被選作簇頭，很容易導(dǎo)致能量耗盡而死亡，那么在這一輪中，整個簇?zé)o法通信，既不利于整個網(wǎng)絡(luò)的健壯性，也不利于網(wǎng)絡(luò)整體生命的延長。

③LEACH的傳輸距離較遠(yuǎn)，并且數(shù)據(jù)融合相對較少，這就要求傳輸更多的數(shù)據(jù)到更遠(yuǎn)的距離，從而加大了能量消耗。某些離基站很遠(yuǎn)的簇頭節(jié)點(diǎn)能量消耗更快，這將影響網(wǎng)絡(luò)的覆蓋范圍和生存時間［6－8］。

針對LEACH算法的不足，本文主要從以下兩個方面對LEACH算法進(jìn)行改進(jìn)。

①選擇設(shè)置網(wǎng)絡(luò)內(nèi)的最優(yōu)簇頭個數(shù)。在LEACH算法中，簇頭節(jié)點(diǎn)擔(dān)當(dāng)著至關(guān)重要的角色，簇頭節(jié)點(diǎn)個數(shù)的選擇直接影響LEACH算法性能的優(yōu)劣。若簇頭數(shù)目過少，那么節(jié)點(diǎn)到簇頭節(jié)點(diǎn)的距離就會較遠(yuǎn)，傳輸數(shù)據(jù)的能量損耗會增加;若簇頭數(shù)目過多，會使得數(shù)據(jù)融合的效率較低，且簇頭節(jié)點(diǎn)消耗能量較多，從而使得整個網(wǎng)絡(luò)在每輪中的總耗能增大。

②簇頭節(jié)點(diǎn)選舉算法。LEACH算法的簇頭輪換時隨機(jī)產(chǎn)生一個數(shù)，由于簇頭是隨機(jī)產(chǎn)生的，所以可能存在某些節(jié)點(diǎn)的剩余能量不多但仍被選為簇頭節(jié)點(diǎn)的情況，這樣這個節(jié)點(diǎn)可能因?yàn)槟芰坎蛔愣鵁o法完成簇頭節(jié)點(diǎn)的功能或因能量迅速耗盡而死去。所以，簇頭的選取依據(jù)必須要考慮到這方面的因素。

2.1 簇頭節(jié)點(diǎn)數(shù)目的選取

由于εamp＜＜Eelec，比較式(3)和式(4)可以得出，能量主要消耗在遠(yuǎn)距離的傳輸中。在選取最優(yōu)簇頭數(shù)目時，我們希望達(dá)到兩方面的效果:一是每輪數(shù)據(jù)通信所耗費(fèi)的總能量最小;二是所耗費(fèi)的能量能夠比較均勻地分布在整個網(wǎng)絡(luò)上。為此，我們假設(shè)在一個不太大的M×M區(qū)域內(nèi)較均勻地分布有N個節(jié)點(diǎn)，并且這N個節(jié)點(diǎn)將被分為n個簇，那么每個簇都將有一個簇頭節(jié)點(diǎn)和N/n－1個成員節(jié)點(diǎn)［7］。一個簇頭節(jié)點(diǎn)在每幀消耗的能量為:

式中:k為每次數(shù)據(jù)傳輸包含的比特數(shù);EDA為進(jìn)行數(shù)據(jù)融合及數(shù)據(jù)壓縮所需要的能量;dtosink為簇頭節(jié)點(diǎn)到基站的距離。

每個成員節(jié)點(diǎn)只需要在各自的時隙內(nèi)傳送數(shù)據(jù)到相應(yīng)的簇頭節(jié)點(diǎn)，一個成員節(jié)點(diǎn)在每幀內(nèi)消耗的能量為:

式中:dtoCH為從成員節(jié)點(diǎn)到簇頭節(jié)點(diǎn)的距離。

基于我們的假設(shè)前提，每個簇的面積為M2/n，假定節(jié)點(diǎn)在這個區(qū)域的分布密度為ρ=n/M2，那么dtoCH的數(shù)學(xué)期望為:

如果假定每個簇所覆蓋的區(qū)域是一個圓形區(qū)域，那么，這個圓的半徑為，則式(7)可變?yōu)?

將式(9)代入式(6)可知，每個成員節(jié)點(diǎn)每幀的能量消耗為:

那么，所有節(jié)點(diǎn)的能量消耗為:

對Etotal求關(guān)于n的導(dǎo)數(shù)，解得:

求得的最優(yōu)簇頭數(shù)目考慮到了更全面的能量消耗因素，因而與原有的最優(yōu)簇頭數(shù)目相比，其更能夠降低整體網(wǎng)絡(luò)的能耗。

2.2 簇頭節(jié)點(diǎn)的選取

在LEACH的簇頭選取算法中，節(jié)點(diǎn)能否當(dāng)選為簇頭節(jié)點(diǎn)主要取決于節(jié)點(diǎn)在過去的r輪中是否擔(dān)當(dāng)過簇頭節(jié)點(diǎn)，以及產(chǎn)生的(0，1)之間的隨機(jī)數(shù)是否小于閾值T(i)。假設(shè)節(jié)點(diǎn)i(從時刻t開始)在第(R+1)輪開始被選定為簇頭節(jié)點(diǎn)的概率為Pi(t)，通過Pi(t)的設(shè)定來保證本輪產(chǎn)生的簇頭節(jié)點(diǎn)數(shù)為k，如果網(wǎng)絡(luò)中有N個節(jié)點(diǎn)，那么產(chǎn)生簇頭節(jié)點(diǎn)數(shù)的期望值為:

式中:G為在過去Rmod(N/k)輪中沒有擔(dān)任過簇頭節(jié)點(diǎn)的節(jié)點(diǎn)集合。

由LEACH算法可知，只有在過去R輪中沒有擔(dān)任過簇頭節(jié)點(diǎn)的節(jié)點(diǎn)，才有可能在第(R+1)輪中當(dāng)選為簇頭節(jié)點(diǎn)，且當(dāng)選的概率為:

前R輪中，沒有成為簇頭節(jié)點(diǎn)的個數(shù)應(yīng)該為N(1－kr/N)，如果經(jīng)過N/k輪之后，所有的節(jié)點(diǎn)都擔(dān)任過一次簇頭節(jié)點(diǎn)，那么在以后的輪中，它們又可以重新?lián)未仡^節(jié)點(diǎn)。因此，在第(R+1)輪中，有資格擔(dān)任簇頭節(jié)點(diǎn)的節(jié)點(diǎn)集合G的期望值為:

這種機(jī)制保證了每輪產(chǎn)生的簇頭節(jié)點(diǎn)數(shù)為k，且在N/k輪之內(nèi)，每個節(jié)點(diǎn)都有且僅有一次擔(dān)任簇頭節(jié)點(diǎn)。在一定程度上，我們認(rèn)為這種機(jī)制能夠保證網(wǎng)絡(luò)能量消耗的均衡分布。

考慮到LEACH算法的簇頭選擇方法并不能夠使得能量消耗均勻地分布在整個網(wǎng)絡(luò)中，所以，我們有必要對LEACH的簇頭選擇方式進(jìn)行相應(yīng)的修改。具體修改方案為:第一，將節(jié)點(diǎn)的剩余能量因素加入到簇頭選取的標(biāo)準(zhǔn)中，目的就是為了避免選擇那些剩余能量較低的節(jié)點(diǎn)成為簇頭，本算法采用的是節(jié)點(diǎn)剩余能量與整個網(wǎng)絡(luò)平均剩余能量的比值;第二，將節(jié)點(diǎn)的能量消耗速度加入到簇頭選取的標(biāo)準(zhǔn)中，簇頭節(jié)點(diǎn)本身要消耗遠(yuǎn)高于成員節(jié)點(diǎn)的能量，如果一個能量消耗速度快的節(jié)點(diǎn)被選為簇頭節(jié)點(diǎn)，那么也會加速它的死亡。最終方案可表示為:

式中:Eremain為節(jié)點(diǎn)第(R+1)輪選擇開始前剩余的能量;Eave為在第(R+1)輪選舉開始前整個網(wǎng)絡(luò)的平均剩余能量;Ecorsume為在第 R輪中節(jié)點(diǎn)能量的消耗;Eave_cors為網(wǎng)絡(luò)在第R輪中平均消耗的能量。

從改進(jìn)后的最終方案來看，引入了節(jié)點(diǎn)剩余能量、網(wǎng)絡(luò)平均剩余能量、上一輪能量消耗和上一輪網(wǎng)絡(luò)平均能量消耗四個因素。

在這個方案中，節(jié)點(diǎn)能否成為簇頭與其當(dāng)前剩余能量成正比，與其上一輪中消耗能量數(shù)成反比。那么，如果一個節(jié)點(diǎn)的剩余能量比網(wǎng)絡(luò)的平均能量級別要低，它當(dāng)選為簇頭的概率也將大大降低。同時，如果一個節(jié)點(diǎn)在一輪消耗的能量比網(wǎng)絡(luò)平均消耗的能量要多，那么也會相應(yīng)地降低它被選為簇頭的概率。

3 LEACH算法的仿真與分析

為了驗(yàn)證改進(jìn)算法的可行性，本文用Matlab仿真平臺，將改進(jìn)的LEACH算法和LEACH算法做比較。

在仿真環(huán)境中，無線傳感器網(wǎng)絡(luò)［9－13］包括1個基站和100個節(jié)點(diǎn)，節(jié)點(diǎn)隨機(jī)分布在(100×100)m2的范圍內(nèi)，基站坐標(biāo)(50，50)。具有5個簇頭節(jié)點(diǎn)的網(wǎng)絡(luò)分布情況如圖2所示。圖2中，“°”表示普通節(jié)點(diǎn)，“+”表示簇頭節(jié)點(diǎn)，“×”表示基站。

圖2 網(wǎng)絡(luò)分布情況示意圖Fig.2 Network distribution

3.1 試驗(yàn)參數(shù)設(shè)定

仿真網(wǎng)絡(luò)中的主要參數(shù)值如表1所示。

表1 網(wǎng)絡(luò)主要參數(shù)Tab.1 Major network parameters

3.2 仿真結(jié)果分析

圖3 P取不同值時網(wǎng)絡(luò)生命周期示意圖Fig.3 The network life cycle under different P

當(dāng)P=0.05和P=0.2時，網(wǎng)絡(luò)生命周期示意圖如圖3所示。從圖3可以看出，當(dāng)P=0.05時，網(wǎng)絡(luò)大概在工作600輪時開始出現(xiàn)死亡節(jié)點(diǎn);當(dāng)工作1200輪時，所有節(jié)點(diǎn)死亡，網(wǎng)絡(luò)癱瘓。當(dāng) P=0.2時，網(wǎng)絡(luò)在工作100輪時開始出現(xiàn)死亡節(jié)點(diǎn);當(dāng)工作800輪時，網(wǎng)絡(luò)癱瘓。所以，P取不同的值時，網(wǎng)絡(luò)在統(tǒng)一模型下的性能并不相同，簇頭節(jié)點(diǎn)數(shù)目占網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目的百分比對網(wǎng)絡(luò)的影響很大，本仿真模型中P取0.05。

兩種算法網(wǎng)絡(luò)生命周期的仿真結(jié)果如圖4所示。

圖4 網(wǎng)絡(luò)生命周期比較曲線Fig.4 Comparison of the network lifecycle

相關(guān)仿真表明，采用LEACH算法時，在第520輪開始出現(xiàn)節(jié)點(diǎn)死亡，在1204輪節(jié)點(diǎn)全部死亡;采用改進(jìn)后的LEACH算法時，在610輪出現(xiàn)節(jié)點(diǎn)死亡，在1400輪節(jié)點(diǎn)全部死亡。改進(jìn)后的LEACH算法由于考慮了分群數(shù)量均衡和簇頭節(jié)點(diǎn)位置信息，從而使整個網(wǎng)絡(luò)分簇更加合理，節(jié)省了能量，有效地延長了整個網(wǎng)絡(luò)的生命周期。

LEACH和ILEACH的網(wǎng)絡(luò)能耗的仿真比較結(jié)果如圖5所示。

圖5 網(wǎng)絡(luò)能耗比較曲線Fig.5 Comparison of the network energy consumption

從圖5可以看出，ILEACH比LEACH能量消耗小，因此網(wǎng)絡(luò)壽命會更長。具體來說，對于100個節(jié)點(diǎn)隨機(jī)分布的場景，節(jié)點(diǎn)的總能量為25 J，采用LEACH算法在第610輪開始出現(xiàn)節(jié)點(diǎn)死亡，消耗的能量為19.7 J;而對應(yīng)的ILEACH算法，此時的能耗只有16.8 J，在這一階段能耗降低了14.7%。可見，ILEACH算法在能量節(jié)省方面顯示出極大的優(yōu)越性。

4 結(jié)束語

針對LEACH算法存在的不足，分析了簇頭個數(shù)對系統(tǒng)性能的影響，并提出了改進(jìn)的簇頭選取算法。該算法全面考慮了簇內(nèi)節(jié)點(diǎn)的各主要能量消耗，引入了節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)消耗能量速度、網(wǎng)絡(luò)平均剩余能量和網(wǎng)絡(luò)平均消耗能量速度四個參數(shù)，能夠更真實(shí)地反映網(wǎng)絡(luò)最優(yōu)簇頭節(jié)點(diǎn)數(shù)目的選取。該算法繼承了LEACH算法隨機(jī)選取簇頭節(jié)點(diǎn)的優(yōu)點(diǎn)，防止有限輪次內(nèi)同一節(jié)點(diǎn)被多次選為簇頭節(jié)點(diǎn)，使簇頭節(jié)點(diǎn)的選取更合理，能在一定程度上減少網(wǎng)絡(luò)能量損耗，延長網(wǎng)絡(luò)生存時間。

［1］孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005.

［2］Akyildizetal I.Wireless sensor networks:a survey［J］.Computer Networks，2002，38(3):392 －422.

［3］胡剛，謝冬梅，吳元忠.無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的研究與改進(jìn)［J］.傳感技術(shù)學(xué)報，2007，20(6):1391 －1396.

［4］Li J P，Zhu X N，Tang N，et al.Study on ZigBee network architecture and routing algorithm［C］∥2010 the 2nd International Conference on Signal Processing Systems，2010:389 －393.

［5］武春濤，胡艷軍.無線傳感器網(wǎng)絡(luò)LEACH算法的改進(jìn)［J］.計算機(jī)技術(shù)與發(fā)展，2009，19(3):80 －83.

［6］陳林星.無線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用［M］.北京:電子工業(yè)出版社，2009.

［7］李善倉，張克旺.無線傳感器網(wǎng)絡(luò)原理與應(yīng)用［M］.北京:機(jī)械工業(yè)出版社，2008.

［8］李建坡，朱緒寧，唐寧.基于DSP的無線指紋考勤系統(tǒng)［J］.自動化儀表，2012，33(9):28 －31.

［9］張學(xué).無線傳感器網(wǎng)絡(luò)的拓?fù)淇刂疲跩］.軟件學(xué)報，2007，18(4):945.

［10］李建中，高宏.無線傳感器網(wǎng)絡(luò)的研究進(jìn)展［J］.計算機(jī)研究與發(fā)展，2008，45(1):5.

［11］任豐原，黃海寧，林闖.無線傳感器網(wǎng)絡(luò)［J］.軟件學(xué)報，2004，14(7):1283.

［12］孫利民.無線傳感器網(wǎng)絡(luò)［M］，北京:清華大學(xué)出版社，2005:156.

［13］繆強(qiáng)，鄭扣根.無線傳感器網(wǎng)絡(luò)的路由協(xié)議設(shè)計研究［J］.計算機(jī)應(yīng)用研究，2004(3):35.