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

　在無線傳感器網絡WSN（Wireless Sensor Networks）[1]中，分簇算法是有效節(jié)約能量的一種手段，是目前研究的關鍵技術之一。參考文獻[2]在簇頭選舉上加入了節(jié)點剩余能量指標，提出了每簇簇頭獨立輪換機制，參考文獻[3]把四色算法引入到簇頭的選舉過程中，并且通過此算法優(yōu)化了網絡簇結構，參考文獻[4]提出了將整個網絡分為兩級拓撲簇內和簇間，利用節(jié)能算法，在優(yōu)化的拓撲結構中找到能耗最小路徑轉發(fā)數據，減少了存儲和控制消息，參考文獻[5]在LEACH算法的基礎上提出了備用節(jié)點和負載平衡的思想。這些文獻中提出的算法，都在一定程度上延長了網絡生存期，但是都需要通過輪選舉簇頭、重新分簇過程，消耗額外能量較多。
　因此，本文在對分簇算法LEACH[6]的詳細研究分析的基礎上，針對LEACH算法中簇頭選擇算法存在的一些不足，提出改進后的分簇算法S_LEACH。
1 LEACH算法的介紹與分析
　LEACH算法的基本思想是將網絡劃分為若干個簇，再通過隨機數值來選擇簇頭和輪換簇頭，以達到能量消耗相對均衡。LEACH算法簇頭選取公式T（n）定義如下：

　式中：p為簇頭的百分比，r為當前輪數，rmod（1/p）為此輪以前已當選過簇頭的節(jié)點個數，G為在此輪以前還未當選過簇頭的節(jié)點集合。該算法分為兩個階段：簇建立階段和穩(wěn)定工作階段。
　簇建立階段。在選舉產生簇頭后，所有當選的簇頭都向網絡中的所有節(jié)點廣播這一消息，非簇頭節(jié)點通過接收信號的強度，選擇信號最強的簇加入并通知該簇頭，收到通知的簇頭就產生一個TDMA定時消息，并且連同將在本簇節(jié)點中通信時使用的CDMA編碼一起發(fā)送給該簇中所有其他節(jié)點。
　在穩(wěn)定階段，節(jié)點持續(xù)采集數據并在時隙到來時向簇頭傳輸數據，簇頭融合處理該簇節(jié)點傳來的數據，之后發(fā)送到基站（BS）。網絡中節(jié)點不斷地進行輪循環(huán)工作。
　LEACH算法的一些不足：
　（1）整體網絡能量利用率低，每輪都要重新選簇頭，重新分簇[7]。這一過程會消耗大量的節(jié)點能量，整個網絡的生存期也會隨之縮短。
　（2）能耗不均勻，LEACH算法中假定所有節(jié)點都可以直接與BS通信，造成LEACH算法無法更好應用于較大的WSN區(qū)域，特別對于簇頭，由于其要處理的數據比較多，這會導致其較早的死亡。
　（3）簇頭選擇不合理，所有節(jié)點當選簇頭概率相同，沒有考慮節(jié)點自身的限制條件如剩余能量[8]。
2 S_LEACH算法
　針對上述問題，本文對簇頭選擇進行了改進，以提高網絡總能量利用率、增強網絡穩(wěn)定性、延長網絡生存期的設計目標，提出了S_LEACH算法。
2.1 S_LEACH設計思想
　無線傳感器網絡在工作到一段時間后，會出現節(jié)點死亡，這樣整個網絡的工作節(jié)點總數就會減少，通過LEACH算法計算得到的簇頭數量Popt值會變成不是最優(yōu)的選擇，導致簇頭的選舉過程變的不可信，進而造成整個網絡的穩(wěn)定性下降。
　因此本文對LEACH算法做如下改進：
　（1）用休眠簇頭節(jié)點代替原算法中用輪換方法選擇的簇頭節(jié)點，避免了整體網絡的能量利用率低的情況。改進后算法只需要一次并且是第一次分簇[9]，此過程仍采用LEACH算法。在第一次完成分簇與首批簇頭的選定后，就進行休眠簇頭的選擇，之后便可以進入穩(wěn)定工作階段。在此階段當某簇的簇頭能量小于當前簇的平均能量時，可喚醒其中一個休眠的簇頭接替當前簇頭工作，避免了因頻煩的簇頭選舉帶來的能量損耗。通過這種方式也可以避免當網絡中節(jié)點不斷死亡時，使得計算所得的popt不可信，進而導致的網絡不穩(wěn)定。
　（2）在實際情況下，由于LEACH算法分簇不均衡，而且簇頭節(jié)點到BS距離不等的因素，要計算得到優(yōu)化的簇頭數量。首先按照參考文獻[6]中的假設計算特殊的情況，假設有N個節(jié)點均勻分布在一個A=M×M區(qū)域，且基站離監(jiān)測節(jié)點都相對較遠。在這種情況下存在兩種能量衰退模型，一種是多路徑衰退模型其衰退系數為εmp，另一種是自由空間衰退模型其衰退系數為εfs。如果網絡中存在k個簇，則每個簇平均有N/k個節(jié)點，由參考文獻[6]中可得最優(yōu)簇kopt值的計算公式：


2.2 S_LEACH工作過程
　S_LEACH算法工作也可以分為兩個過程：準備階段和工作階段。準備階段包括簇頭的選擇、分簇和休眠簇頭的確定。休眠簇頭的確定環(huán)節(jié)是確保新算法可以正確工作的重要環(huán)節(jié)，也是算法的改進點。
為了方便說明，用Ai0表示第i簇的簇頭；用Aij表示第i簇的標號為j的節(jié)點，其中0<j<Ni，Ni為第i簇的節(jié)點數量；Ais表示休眠的節(jié)點，且是Aij的真子集。
　（1）準備階段
　簇的建立過程中主要是選第一批簇頭和分簇，因為改進的算法S_LEACH是一次性確定所有簇頭，并且只需要一次分簇，所以在簇的初始階段仍采用LEACH算法進行確定第一批簇頭和首次分簇。
　基于LEACH算法，在分簇的過程中，簇頭Ai0（i=0，1，2，3，4）會在全網范圍內廣播ADV消息，非簇頭節(jié)點根據收到的ADV能量大小，回復JoinREQ消息（含節(jié)點自身ID和簇頭ID）選擇加入哪個簇。簇頭Ai0統計加入的節(jié)點數量，并由式（2）計算出本簇中休眠簇頭的數量n=kopt。再在為簇內成員節(jié)點分配TDMA時隙表和CDMA編碼時，把前n個回復確認的節(jié)點確定為休眠簇頭節(jié)點，并作好標記存儲在Ai0緩存中。完成后，Ai0再給標記的n個節(jié)點發(fā)送含有將來用于喚醒休眠簇頭節(jié)點的特定的發(fā)射功率Wi的消息，這n個節(jié)點收到后記錄Wi，之后馬上進入休眠狀態(tài)并設定定時器，定時蘇醒后，等待一定時間再查看是否有喚醒消息，無則進入睡眠狀態(tài)。
　（2）工作階段
　在準備階段的工作完成之后，WSN就進入工作階段，在此階段每個簇的Ai0每隔一定時間先查看自己的緩存中是否還有有標記了的Ais，有則計算當前簇的所有節(jié)點的平均剩余能量（Ei_ave）的大小并且和自己的剩余能量（Ei_res）比較。
　如果Ei_res>Ei_ave，則Ai0繼續(xù)當選為簇頭，如果Ei_res<Ei_ave，則Ai0從自己的記錄中隨機取一個標記節(jié)點的ID，用剛剛和休眠簇頭協商的Wi發(fā)射功率廣播一個含有此ID的喚醒消息Mwakeup，只有Ais能收到此消息。
　當Ais收到后對比自已ID和Mwakeup中的ID，如果相同則結束睡眠進入工作狀態(tài)，如果不同則繼續(xù)睡眠。對比結果相同的節(jié)點A′is回復消息Mback給Ai0，說明自己已經做好準備當簇頭了。
　Ai0收到Mback后，再發(fā)送包含正處于休眠狀態(tài)的簇頭信息的消息給A′is，A′is收到后記錄并且回復確認。之后Ai0再發(fā)送消息（含有A′is的ID）給基站說明本簇的簇頭現在更改為A′is，基站在收到消息后回復同意消息給Ai0，并把自己記錄的該簇的簇頭信息更新為A′is。Ai0同時在簇內廣播簇頭更改消息，簇內所有普通節(jié)點都更新自己的簇頭信息。在廣播消息發(fā)送完成并且Ai0收到BS回復的同意消息之后就降級為普通節(jié)點，并保存新簇頭Ais的信息，之后進入穩(wěn)定工作階段。
　隔一定時間再次計算當前簇的所有節(jié)點的平均剩余能量（Ei_ave）的大小并且和當前簇頭的剩余能量（Ei_res）比較大小，然后再按上述過程喚醒休眠簇頭。
3 仿真及其結果分析
　本文以Matlab作為實驗仿真平臺，在區(qū)域為100 m×100 m的范圍內隨機部署100個節(jié)點，基站位置為（50，175），節(jié)點初始能量為0.5 J，
　εmp=0.001 3 pJ/bit/m4，εfs=10 pJ/bit/m2。
　圖1比較了兩種算法下在不同時段網絡剩余總能量的值，可以看出LEACH算法在250 s時能量剩余總量為0 J；而S_LEACH算法在336 s時能量剩余總量才為0 J，新算法延長了大約34%的網絡生命周期。這是因為原算法需要頻繁地進行簇頭選舉和重分簇區(qū)，而且這些過程都需要和基站進行直接通信，能量消耗大。新算法只需要在本簇內喚醒休眠簇頭節(jié)點即可保證網絡繼續(xù)工作，新算法除了在數據融合之后需要向基站發(fā)送信息外，只有在更換簇頭時，通信一次即可，節(jié)約了大量的能量。

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

　本文詳述了LEACH算法的基本原理，針對該算法的不足，提出了一種休眠簇頭的算法。與LEACH算法相比，改進后的算法減少了簇頭選舉的能耗并且避免了重新分簇帶來的能量損耗，可使網絡中的能量利用最大化。仿真實驗表明，新算法的穩(wěn)定性較好，并且能夠有效地利用網絡中有限能量，實現了延長網絡生存周期的目標。
參考文獻
[1] 孫利民，李建中，陳渝，等.無線傳感器網絡[M].北京：清華大學出版社，2006.
[2] 張強，盧瀟，崔曉臣.基于能量高效的無線傳感器網絡LEACH算法改進[J].計算機工程與設計，2010，32（2）：427-433.
[3] 劉波，柴喬林，劉玲.基于分簇的無線傳感器網絡節(jié)能算法[J].計算機工程與設計，2008，29（4）：846-848.
[4] 王春雷，柴喬林，王華，等.基于分簇的無線傳感器網絡節(jié)能算法[J].計算機應用，2007，27（2）：342-345.
[5] 邢云冰，史浩山，趙洪鋼.基于備用節(jié)點的無線傳感器網絡LEACH算法的改進[J].傳感技術學報，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] 張瑞華，高蕊.無線傳感器網絡LEACH算法分析[J].網絡技術，2010（4）：56-59.
[8] 楊偉偉.基于LEACH的WSN分簇算法研究[D].鄭州：鄭州大學信息工程學院，2010.
[9] 陳楠.無線傳感器網絡LEACH算法的研究與改進[D].北京：北京郵電大學，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.