摘  要： 針對(duì)無(wú)線傳感器網(wǎng)絡(luò)中傳感器有限能量的特點(diǎn)，在分析LEACH算法的基礎(chǔ)上，提出一種休眠簇頭的算法——S_LEACH，以達(dá)到延長(zhǎng)網(wǎng)絡(luò)生存期的目的。新算法一次性選定所需要的工作簇頭和休眠簇頭，并且只分一次簇，節(jié)省了在LEACH中因再次簇頭選舉和分簇消耗的能量。使用Matlab進(jìn)行算法改進(jìn)前后的仿真，結(jié)果表明改進(jìn)后的算法網(wǎng)絡(luò)生存期延長(zhǎng)了大約34%。
關(guān)鍵詞： 無(wú)線傳感器網(wǎng)絡(luò)；休眠簇頭；網(wǎng)絡(luò)生存期；LEACH算法；Matlab仿真

　在無(wú)線傳感器網(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]把四色算法引入到簇頭的選舉過(guò)程中，并且通過(guò)此算法優(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)中提出的算法，都在一定程度上延長(zhǎng)了網(wǎng)絡(luò)生存期，但是都需要通過(guò)輪選舉簇頭、重新分簇過(guò)程，消耗額外能量較多。
　因此，本文在對(duì)分簇算法LEACH[6]的詳細(xì)研究分析的基礎(chǔ)上，針對(duì)LEACH算法中簇頭選擇算法存在的一些不足，提出改進(jìn)后的分簇算法S_LEACH。
1 LEACH算法的介紹與分析
　LEACH算法的基本思想是將網(wǎng)絡(luò)劃分為若干個(gè)簇，再通過(guò)隨機(jī)數(shù)值來(lái)選擇簇頭和輪換簇頭，以達(dá)到能量消耗相對(duì)均衡。LEACH算法簇頭選取公式T（n）定義如下：

　式中：p為簇頭的百分比，r為當(dāng)前輪數(shù)，rmod（1/p）為此輪以前已當(dāng)選過(guò)簇頭的節(jié)點(diǎn)個(gè)數(shù)，G為在此輪以前還未當(dāng)選過(guò)簇頭的節(jié)點(diǎn)集合。該算法分為兩個(gè)階段：簇建立階段和穩(wěn)定工作階段。
　簇建立階段。在選舉產(chǎn)生簇頭后，所有當(dāng)選的簇頭都向網(wǎng)絡(luò)中的所有節(jié)點(diǎn)廣播這一消息，非簇頭節(jié)點(diǎn)通過(guò)接收信號(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í)隙到來(lái)時(shí)向簇頭傳輸數(shù)據(jù)，簇頭融合處理該簇節(jié)點(diǎn)傳來(lái)的數(shù)據(jù)，之后發(fā)送到基站（BS）。網(wǎng)絡(luò)中節(jié)點(diǎn)不斷地進(jìn)行輪循環(huán)工作。
　LEACH算法的一些不足：
　（1）整體網(wǎng)絡(luò)能量利用率低，每輪都要重新選簇頭，重新分簇[7]。這一過(guò)程會(huì)消耗大量的節(jié)點(diǎn)能量，整個(gè)網(wǎng)絡(luò)的生存期也會(huì)隨之縮短。
　（2）能耗不均勻，LEACH算法中假定所有節(jié)點(diǎn)都可以直接與BS通信，造成LEACH算法無(wú)法更好應(yīng)用于較大的WSN區(qū)域，特別對(duì)于簇頭，由于其要處理的數(shù)據(jù)比較多，這會(huì)導(dǎo)致其較早的死亡。
　（3）簇頭選擇不合理，所有節(jié)點(diǎn)當(dāng)選簇頭概率相同，沒(méi)有考慮節(jié)點(diǎn)自身的限制條件如剩余能量[8]。
2 S_LEACH算法
　針對(duì)上述問(wèn)題，本文對(duì)簇頭選擇進(jìn)行了改進(jìn)，以提高網(wǎng)絡(luò)總能量利用率、增強(qiáng)網(wǎng)絡(luò)穩(wěn)定性、延長(zhǎng)網(wǎng)絡(luò)生存期的設(shè)計(jì)目標(biāo)，提出了S_LEACH算法。
2.1 S_LEACH設(shè)計(jì)思想
　無(wú)線傳感器網(wǎng)絡(luò)在工作到一段時(shí)間后，會(huì)出現(xiàn)節(jié)點(diǎn)死亡，這樣整個(gè)網(wǎng)絡(luò)的工作節(jié)點(diǎn)總數(shù)就會(huì)減少，通過(guò)LEACH算法計(jì)算得到的簇頭數(shù)量Popt值會(huì)變成不是最優(yōu)的選擇，導(dǎo)致簇頭的選舉過(guò)程變的不可信，進(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]，此過(guò)程仍采用LEACH算法。在第一次完成分簇與首批簇頭的選定后，就進(jìn)行休眠簇頭的選擇，之后便可以進(jìn)入穩(wěn)定工作階段。在此階段當(dāng)某簇的簇頭能量小于當(dāng)前簇的平均能量時(shí)，可喚醒其中一個(gè)休眠的簇頭接替當(dāng)前簇頭工作，避免了因頻煩的簇頭選舉帶來(lái)的能量損耗。通過(guò)這種方式也可以避免當(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)測(cè)節(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ì)算公式：


2.2 S_LEACH工作過(guò)程
　S_LEACH算法工作也可以分為兩個(gè)過(guò)程：準(zhǔn)備階段和工作階段。準(zhǔn)備階段包括簇頭的選擇、分簇和休眠簇頭的確定。休眠簇頭的確定環(huán)節(jié)是確保新算法可以正確工作的重要環(huán)節(jié)，也是算法的改進(jìn)點(diǎn)。
為了方便說(shuō)明，用Ai0表示第i簇的簇頭；用Aij表示第i簇的標(biāo)號(hào)為j的節(jié)點(diǎn)，其中0<j<Ni，Ni為第i簇的節(jié)點(diǎn)數(shù)量；Ais表示休眠的節(jié)點(diǎn)，且是Aij的真子集。
　（1）準(zhǔn)備階段
　簇的建立過(guò)程中主要是選第一批簇頭和分簇，因?yàn)楦倪M(jìn)的算法S_LEACH是一次性確定所有簇頭，并且只需要一次分簇，所以在簇的初始階段仍采用LEACH算法進(jìn)行確定第一批簇頭和首次分簇。
　基于LEACH算法，在分簇的過(guò)程中，簇頭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ā)送含有將來(lái)用于喚醒休眠簇頭節(jié)點(diǎn)的特定的發(fā)射功率Wi的消息，這n個(gè)節(jié)點(diǎn)收到后記錄Wi，之后馬上進(jìn)入休眠狀態(tài)并設(shè)定定時(shí)器，定時(shí)蘇醒后，等待一定時(shí)間再查看是否有喚醒消息，無(wú)則進(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<Ei_ave，則Ai0從自己的記錄中隨機(jī)取一個(gè)標(biāo)記節(jié)點(diǎn)的ID，用剛剛和休眠簇頭協(xié)商的Wi發(fā)射功率廣播一個(gè)含有此ID的喚醒消息Mwakeup，只有Ais能收到此消息。
　當(dāng)Ais收到后對(duì)比自已ID和Mwakeup中的ID，如果相同則結(jié)束睡眠進(jìn)入工作狀態(tài)，如果不同則繼續(xù)睡眠。對(duì)比結(jié)果相同的節(jié)點(diǎn)A′is回復(fù)消息Mback給Ai0，說(shuō)明自己已經(jīng)做好準(zhǔn)備當(dāng)簇頭了。
　Ai0收到Mback后，再發(fā)送包含正處于休眠狀態(tài)的簇頭信息的消息給A′is，A′is收到后記錄并且回復(fù)確認(rèn)。之后Ai0再發(fā)送消息（含有A′is的ID）給基站說(shuō)明本簇的簇頭現(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）比較大小，然后再按上述過(guò)程喚醒休眠簇頭。
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，新算法延長(zhǎng)了大約34%的網(wǎng)絡(luò)生命周期。這是因?yàn)樵惴ㄐ枰l繁地進(jìn)行簇頭選舉和重分簇區(qū)，而且這些過(guò)程都需要和基站進(jìn)行直接通信，能量消耗大。新算法只需要在本簇內(nèi)喚醒休眠簇頭節(jié)點(diǎn)即可保證網(wǎng)絡(luò)繼續(xù)工作，新算法除了在數(shù)據(jù)融合之后需要向基站發(fā)送信息外，只有在更換簇頭時(shí)，通信一次即可，節(jié)約了大量的能量。

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

　本文詳述了LEACH算法的基本原理，針對(duì)該算法的不足，提出了一種休眠簇頭的算法。與LEACH算法相比，改進(jìn)后的算法減少了簇頭選舉的能耗并且避免了重新分簇帶來(lái)的能量損耗，可使網(wǎng)絡(luò)中的能量利用最大化。仿真實(shí)驗(yàn)表明，新算法的穩(wěn)定性較好，并且能夠有效地利用網(wǎng)絡(luò)中有限能量，實(shí)現(xiàn)了延長(zhǎng)網(wǎng)絡(luò)生存周期的目標(biāo)。
參考文獻(xiàn)
[1] 孫利民，李建中，陳渝，等.無(wú)線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2006.
[2] 張強(qiáng)，盧瀟，崔曉臣.基于能量高效的無(wú)線傳感器網(wǎng)絡(luò)LEACH算法改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010，32（2）：427-433.
[3] 劉波，柴喬林，劉玲.基于分簇的無(wú)線傳感器網(wǎng)絡(luò)節(jié)能算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（4）：846-848.
[4] 王春雷，柴喬林，王華，等.基于分簇的無(wú)線傳感器網(wǎng)絡(luò)節(jié)能算法[J].計(jì)算機(jī)應(yīng)用，2007，27（2）：342-345.
[5] 邢云冰，史浩山，趙洪鋼.基于備用節(jié)點(diǎn)的無(wú)線傳感器網(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ú)線傳感器網(wǎng)絡(luò)LEACH算法分析[J].網(wǎng)絡(luò)技術(shù)，2010（4）：56-59.
[8] 楊偉偉.基于LEACH的WSN分簇算法研究[D].鄭州：鄭州大學(xué)信息工程學(xué)院，2010.
[9] 陳楠.無(wú)線傳感器網(wǎng)絡(luò)LEACH算法的研究與改進(jìn)[D].北京：北京郵電大學(xué)，2008.
[10] BANDYOPADHYAY S， COYLE E J. Minimizing communication costs in hierarchically-clustered net-works of wireless 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 sensor networks[C]. Proc. of the Int′l Workshop on SANPA， 2004， 251-261.