基于休眠簇頭的LEACH算法研究

蘭 慎 ，彭 剛 ，李發(fā)飛

（1.桂林電子科技大學(xué) 計(jì)算機(jī)與控制學(xué)院，廣西 桂林 541004；2.桂林空軍學(xué)院 教育技術(shù)中心，廣西 桂林 541003）

在無線傳感器網(wǎng)絡(luò) WSN （Wireless Sensor Networks）[1]中，分簇算法是有效節(jié)約能量的一種手段，是目前研究的關(guān)鍵技術(shù)之一。參考文獻(xiàn)[2]在簇頭選舉上加入了節(jié)點(diǎn)剩余能量指標(biāo)，提出了每簇簇頭獨(dú)立輪換機(jī)制，參考文獻(xiàn)[3]把四色算法引入到簇頭的選舉過程中，并且通過此算法優(yōu)化了網(wǎng)絡(luò)簇結(jié)構(gòu)，參考文獻(xiàn)[4]提出了將整個(gè)網(wǎng)絡(luò)分為兩級(jí)拓?fù)浯貎?nèi)和簇間，利用節(jié)能算法，在優(yōu)化的拓?fù)浣Y(jié)構(gòu)中找到能耗最小路徑轉(zhuǎn)發(fā)數(shù)據(jù)，減少了存儲(chǔ)和控制消息，參考文獻(xiàn)[5]在LEACH算法的基礎(chǔ)上提出了備用節(jié)點(diǎn)和負(fù)載平衡的思想。這些文獻(xiàn)中提出的算法，都在一定程度上延長了網(wǎng)絡(luò)生存期，但是都需要通過輪選舉簇頭、重新分簇過程，消耗額外能量較多。

因此，本文在對(duì)分簇算法LEACH[6]的詳細(xì)研究分析的基礎(chǔ)上，針對(duì)LEACH算法中簇頭選擇算法存在的一些不足，提出改進(jìn)后的分簇算法S_LEACH。

1 LEACH算法的介紹與分析

LEACH算法的基本思想是將網(wǎng)絡(luò)劃分為若干個(gè)簇，再通過隨機(jī)數(shù)值來選擇簇頭和輪換簇頭，以達(dá)到能量消耗相對(duì)均衡。LEACH算法簇頭選取公式 T（n）定義如下：

式中：p為簇頭的百分比，r為當(dāng)前輪數(shù)，rmod（1/p）為此輪以前已當(dāng)選過簇頭的節(jié)點(diǎn)個(gè)數(shù)，G為在此輪以前還未當(dāng)選過簇頭的節(jié)點(diǎn)集合。該算法分為兩個(gè)階段：簇建立階段和穩(wěn)定工作階段。

簇建立階段。在選舉產(chǎn)生簇頭后，所有當(dāng)選的簇頭都向網(wǎng)絡(luò)中的所有節(jié)點(diǎn)廣播這一消息，非簇頭節(jié)點(diǎn)通過接收信號(hào)的強(qiáng)度，選擇信號(hào)最強(qiáng)的簇加入并通知該簇頭，收到通知的簇頭就產(chǎn)生一個(gè)TDMA定時(shí)消息，并且連同將在本簇節(jié)點(diǎn)中通信時(shí)使用的CDMA編碼一起發(fā)送給該簇中所有其他節(jié)點(diǎn)。

在穩(wěn)定階段，節(jié)點(diǎn)持續(xù)采集數(shù)據(jù)并在時(shí)隙到來時(shí)向簇頭傳輸數(shù)據(jù)，簇頭融合處理該簇節(jié)點(diǎn)傳來的數(shù)據(jù)，之后發(fā)送到基站（BS）。網(wǎng)絡(luò)中節(jié)點(diǎn)不斷地進(jìn)行輪循環(huán)工作。

LEACH算法的一些不足：

（1）整體網(wǎng)絡(luò)能量利用率低，每輪都要重新選簇頭，重新分簇[7]。這一過程會(huì)消耗大量的節(jié)點(diǎn)能量，整個(gè)網(wǎng)絡(luò)的生存期也會(huì)隨之縮短。

（2）能耗不均勻，LEACH算法中假定所有節(jié)點(diǎn)都可以直接與BS通信，造成LEACH算法無法更好應(yīng)用于較大的WSN區(qū)域，特別對(duì)于簇頭，由于其要處理的數(shù)據(jù)比較多，這會(huì)導(dǎo)致其較早的死亡。

（3）簇頭選擇不合理，所有節(jié)點(diǎn)當(dāng)選簇頭概率相同，沒有考慮節(jié)點(diǎn)自身的限制條件如剩余能量[8]。

2 S_LEACH算法

針對(duì)上述問題，本文對(duì)簇頭選擇進(jìn)行了改進(jìn)，以提高網(wǎng)絡(luò)總能量利用率、增強(qiáng)網(wǎng)絡(luò)穩(wěn)定性、延長網(wǎng)絡(luò)生存期的設(shè)計(jì)目標(biāo)，提出了S_LEACH算法。

2.1 S_LEACH設(shè)計(jì)思想

無線傳感器網(wǎng)絡(luò)在工作到一段時(shí)間后，會(huì)出現(xiàn)節(jié)點(diǎn)死亡，這樣整個(gè)網(wǎng)絡(luò)的工作節(jié)點(diǎn)總數(shù)就會(huì)減少，通過LEACH算法計(jì)算得到的簇頭數(shù)量Popt值會(huì)變成不是最優(yōu)的選擇，導(dǎo)致簇頭的選舉過程變的不可信，進(jìn)而造成整個(gè)網(wǎng)絡(luò)的穩(wěn)定性下降。

因此本文對(duì)LEACH算法做如下改進(jìn)：

（1）用休眠簇頭節(jié)點(diǎn)代替原算法中用輪換方法選擇的簇頭節(jié)點(diǎn)，避免了整體網(wǎng)絡(luò)的能量利用率低的情況。改進(jìn)后算法只需要一次并且是第一次分簇[9]，此過程仍采用LEACH算法。在第一次完成分簇與首批簇頭的選定后，就進(jìn)行休眠簇頭的選擇，之后便可以進(jìn)入穩(wěn)定工作階段。在此階段當(dāng)某簇的簇頭能量小于當(dāng)前簇的平均能量時(shí)，可喚醒其中一個(gè)休眠的簇頭接替當(dāng)前簇頭工作，避免了因頻煩的簇頭選舉帶來的能量損耗。通過這種方式也可以避免當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)不斷死亡時(shí)，使得計(jì)算所得的popt不可信，進(jìn)而導(dǎo)致的網(wǎng)絡(luò)不穩(wěn)定。

（2）在實(shí)際情況下，由于LEACH算法分簇不均衡，而且簇頭節(jié)點(diǎn)到BS距離不等的因素，要計(jì)算得到優(yōu)化的簇頭數(shù)量。首先按照參考文獻(xiàn)[6]中的假設(shè)計(jì)算特殊的情況，假設(shè)有N個(gè)節(jié)點(diǎn)均勻分布在一個(gè)A=M×M區(qū)域，且基站離監(jiān)測節(jié)點(diǎn)都相對(duì)較遠(yuǎn)。在這種情況下存在兩種能量衰退模型，一種是多路徑衰退模型其衰退系數(shù)為 εmp，另一種是自由空間衰退模型其衰退系數(shù)為εfs。如果網(wǎng)絡(luò)中存在k個(gè)簇，則每個(gè)簇平均有N/k個(gè)節(jié)點(diǎn)，由參考文獻(xiàn)[6]中可得最優(yōu)簇kopt值的計(jì)算公式：

通過實(shí)驗(yàn)得出，當(dāng) N=100，M=100 m，75 m

又根據(jù)參考文獻(xiàn)[10]，在參考文獻(xiàn)[6]相同的假設(shè)情況下，當(dāng)基站位于監(jiān)測節(jié)點(diǎn)網(wǎng)絡(luò)的中心位置時(shí)，其給出了最優(yōu)簇kopt的值計(jì)算公式：

因?yàn)樵趨⒖嘉墨I(xiàn)[10]同樣環(huán)境下，參考文獻(xiàn)[11]給出了簇頭到基站的平均距離計(jì)算方法：

其中，x，y為節(jié)點(diǎn)的坐標(biāo)，參考文獻(xiàn)[10]中通過式（3）得到式（2），從式（2）可以看出，在參考文獻(xiàn)[10-11]的假設(shè)情況下，網(wǎng)絡(luò)簇?cái)?shù)量或是簇頭數(shù)量與節(jié)點(diǎn)到基站的距離無關(guān)，簇的數(shù)量只與網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量N有關(guān)。

本文在仿真過程中，取 N=100，kopt=5（即實(shí)驗(yàn)中 p=5%）。在第一次分完簇后，可以把每個(gè)簇看成原來WSN網(wǎng)絡(luò)的子網(wǎng)絡(luò)，并且假設(shè)它們是獨(dú)立、均勻分布。此時(shí)簇頭就相當(dāng)于是基站，滿足參考文獻(xiàn)[10]中的假設(shè)，由式（2）可以計(jì)算出該簇（子網(wǎng)絡(luò)）中所需要簇頭的數(shù)量，這個(gè)數(shù)量即為休眠簇頭的數(shù)量。因?yàn)檫@是在子網(wǎng)絡(luò)中計(jì)算的簇頭數(shù)量，而子網(wǎng)絡(luò)本身就是一個(gè)簇，所以根據(jù)式（2）計(jì)算出的簇頭數(shù)量即可為休眠簇頭數(shù)量。

2.2 S_LEACH工作過程

S_LEACH算法工作也可以分為兩個(gè)過程：準(zhǔn)備階段和工作階段。準(zhǔn)備階段包括簇頭的選擇、分簇和休眠簇頭的確定。休眠簇頭的確定環(huán)節(jié)是確保新算法可以正確工作的重要環(huán)節(jié)，也是算法的改進(jìn)點(diǎn)。

為了方便說明，用Ai0表示第 i簇的簇頭；用Aij表示第i簇的標(biāo)號(hào)為j的節(jié)點(diǎn)，其中 0

（1）準(zhǔn)備階段

簇的建立過程中主要是選第一批簇頭和分簇，因?yàn)楦倪M(jìn)的算法S_LEACH是一次性確定所有簇頭，并且只需要一次分簇，所以在簇的初始階段仍采用LEACH算法進(jìn)行確定第一批簇頭和首次分簇。

基于 LEACH算法，在分簇的過程中，簇頭 Ai0（i=0，1，2，3，4）會(huì)在全網(wǎng)范圍內(nèi)廣播 ADV消息，非簇頭節(jié)點(diǎn)根據(jù)收到的ADV能量大小，回復(fù)JoinREQ消息（含節(jié)點(diǎn)自身ID和簇頭ID）選擇加入哪個(gè)簇。簇頭Ai0統(tǒng)計(jì)加入的節(jié)點(diǎn)數(shù)量，并由式（2）計(jì)算出本簇中休眠簇頭的數(shù)量n=kopt。再在為簇內(nèi)成員節(jié)點(diǎn)分配TDMA時(shí)隙表和CDMA編碼時(shí)，把前n個(gè)回復(fù)確認(rèn)的節(jié)點(diǎn)確定為休眠簇頭節(jié)點(diǎn)，并作好標(biāo)記存儲(chǔ)在Ai0緩存中。完成后，Ai0再給標(biāo)記的n個(gè)節(jié)點(diǎn)發(fā)送含有將來用于喚醒休眠簇頭節(jié)點(diǎn)的特定的發(fā)射功率Wi的消息，這n個(gè)節(jié)點(diǎn)收到后記錄Wi，之后馬上進(jìn)入休眠狀態(tài)并設(shè)定定時(shí)器，定時(shí)蘇醒后，等待一定時(shí)間再查看是否有喚醒消息，無則進(jìn)入睡眠狀態(tài)。

（2）工作階段

在準(zhǔn)備階段的工作完成之后，WSN就進(jìn)入工作階段，在此階段每個(gè)簇的Ai0每隔一定時(shí)間先查看自己的緩存中是否還有有標(biāo)記了的Ais，有則計(jì)算當(dāng)前簇的所有節(jié)點(diǎn)的平均剩余能量（Ei_ave）的大小并且和自己的剩余能量（Ei_res）比較。

如果Ei_res>Ei_ave，則 Ai0繼續(xù)當(dāng)選為簇頭，如果 Ei_res

當(dāng)Ais收到后對(duì)比自已 ID和Mwakeup中的 ID，如果相同則結(jié)束睡眠進(jìn)入工作狀態(tài)，如果不同則繼續(xù)睡眠。對(duì)比結(jié)果相同的節(jié)點(diǎn) A′is回復(fù)消息 Mback給 Ai0，說明自己已經(jīng)做好準(zhǔn)備當(dāng)簇頭了。

Ai0收到Mback后，再發(fā)送包含正處于休眠狀態(tài)的簇頭信息的消息給 A′is，A′is收到后記錄并且回復(fù)確認(rèn)。之后Ai0再發(fā)送消息（含有 A′is的ID）給基站說明本簇的簇頭現(xiàn)在更改為A′is，基站在收到消息后回復(fù)同意消息給Ai0，并把自己記錄的該簇的簇頭信息更新為 A′is。Ai0同時(shí)在簇內(nèi)廣播簇頭更改消息，簇內(nèi)所有普通節(jié)點(diǎn)都更新自己的簇頭信息。在廣播消息發(fā)送完成并且Ai0收到BS回復(fù)的同意消息之后就降級(jí)為普通節(jié)點(diǎn)，并保存新簇頭Ais的信息，之后進(jìn)入穩(wěn)定工作階段。

隔一定時(shí)間再次計(jì)算當(dāng)前簇的所有節(jié)點(diǎn)的平均剩余能量（Ei_ave）的大小并且和當(dāng)前簇頭的剩余能量（Ei_res）比較大小，然后再按上述過程喚醒休眠簇頭。

3 仿真及其結(jié)果分析

本文以Matlab作為實(shí)驗(yàn)仿真平臺(tái)，在區(qū)域?yàn)?00 m×100 m的范圍內(nèi)隨機(jī)部署100個(gè)節(jié)點(diǎn)，基站位置為（50，175），節(jié)點(diǎn)初始能量為 0.5 J，

εmp=0.001 3 pJ/bit/m4，εfs=10 pJ/bit/m2。

圖1比較了兩種算法下在不同時(shí)段網(wǎng)絡(luò)剩余總能量的值，可以看出LEACH算法在250 s時(shí)能量剩余總量為0 J；而S_LEACH算法在336 s時(shí)能量剩余總量才為0 J，新算法延長了大約34%的網(wǎng)絡(luò)生命周期。這是因?yàn)樵惴ㄐ枰l繁地進(jìn)行簇頭選舉和重分簇區(qū)，而且這些過程都需要和基站進(jìn)行直接通信，能量消耗大。新算法只需要在本簇內(nèi)喚醒休眠簇頭節(jié)點(diǎn)即可保證網(wǎng)絡(luò)繼續(xù)工作，新算法除了在數(shù)據(jù)融合之后需要向基站發(fā)送信息外，只有在更換簇頭時(shí)，通信一次即可，節(jié)約了大量的能量。

圖1 兩種算法的生存期

圖2比較了兩種算法在不同時(shí)段網(wǎng)絡(luò)中節(jié)點(diǎn)死亡的數(shù)量，從圖中可以看出，LEACH算法和S_LEACH算法第一次出現(xiàn)死亡節(jié)點(diǎn)的時(shí)間分別為149 s和251 s，這表明新算法很大程度上延長了網(wǎng)絡(luò)的穩(wěn)定性，因?yàn)樵跊]有出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)之前網(wǎng)絡(luò)的整體拓?fù)浣Y(jié)構(gòu)是沒有變化的，算法通過計(jì)算節(jié)點(diǎn)數(shù)計(jì)算的最優(yōu)簇?cái)?shù)量（kopt）也不會(huì)受影響，當(dāng)有死亡節(jié)點(diǎn)出現(xiàn)的時(shí)候，其就會(huì)計(jì)算不準(zhǔn)確，從而影響簇的形成與工作過程。而且S_LEACH的曲線圖很接近直線，說明新算法中的死亡節(jié)點(diǎn)是穩(wěn)定增加的，網(wǎng)絡(luò)不會(huì)因?yàn)樗劳龉?jié)點(diǎn)的突然增加，而使得其他節(jié)點(diǎn)工作受重大影響，避免了監(jiān)測數(shù)據(jù)不準(zhǔn)確或是丟失嚴(yán)重。這些都可以說明新算法能量利用比較均勻并且其穩(wěn)定性較好。

圖2 兩種算法死亡節(jié)點(diǎn)的比較

本文詳述了LEACH算法的基本原理，針對(duì)該算法的不足，提出了一種休眠簇頭的算法。與LEACH算法相比，改進(jìn)后的算法減少了簇頭選舉的能耗并且避免了重新分簇帶來的能量損耗，可使網(wǎng)絡(luò)中的能量利用最大化。仿真實(shí)驗(yàn)表明，新算法的穩(wěn)定性較好，并且能夠有效地利用網(wǎng)絡(luò)中有限能量，實(shí)現(xiàn)了延長網(wǎng)絡(luò)生存周期的目標(biāo)。

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

[2]張強(qiáng)，盧瀟，崔曉臣.基于能量高效的無線傳感器網(wǎng)絡(luò)LEACH 算法改進(jìn)[J].計(jì)算機(jī)工 程與設(shè)計(jì)，2010，32（2）：427-433.

[3]劉波，柴喬林，劉玲.基于分簇的無線傳感器網(wǎng)絡(luò)節(jié)能算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（4）：846-848.

[4]王春雷，柴喬林，王華，等.基于分簇的無線傳感器網(wǎng)絡(luò)節(jié)能算法[J].計(jì)算機(jī)應(yīng)用，2007，27（2）：342-345.

[5]邢云冰，史浩山，趙洪鋼.基于備用節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò) LEACH算法的改進(jìn) [J].傳感技術(shù)學(xué)報(bào)，2007，20（7）：1592-1596.

[6]HEINZELMAN W，CHANDRAKASAN A，BALAKRISHMAN H.An application-specific protocol architecture for wireless micro-sensor networks [J].Wireless Communications，2002（1）： 660-670.

[7]張瑞華，高蕊.無線傳感器網(wǎng)絡(luò) LEACH算法分析[J].網(wǎng)絡(luò)技術(shù)，2010（4）：56-59.

[8]楊偉偉.基于 LEACH的WSN分簇算法研究[D].鄭州：鄭州大學(xué)信息工程學(xué)院，2010.

[9]陳楠.無線傳感器網(wǎng)絡(luò)LEACH算法的研究與改進(jìn)[D].北京：北京郵電大學(xué)，2008.

[10]BANDYOPADHYAYS，COYLEEJ.Minimizingcommunication costsin hierarchically-clustered net-worksofwireless sensors[J].Computer Networks， 2004， 1（44）： 1-16.

[11]SMARAGDAKIS G， MATTA I， BESTAVROS A.SEP：A Stable election protocol for clustered heterogeneous wireless sensornetworks[C].Proc.ofthe Int′lWorkshop on SANPA， 2004， 251-261.