基于剩余能量和睡眠控制的改進LEACH算法

摘 要：無線傳感器網絡（WSN）路由協議研究的一個重要的目標是如何在有限的能源下降低整個網絡的能耗，提高網絡的生存時間。以分簇路由協議LEACH為研究基礎，提出了一種改進算法。該算法改進了簇首選擇規則，引入協調件協議算法，通過在成簇階段降低剩余能量低的節點被選擇成為簇首的概率，在穩定運行階段使簇首節點盡可能多的保持睡眠狀態，從而降低了網絡能耗。仿真結果表明，與原LEACH算法相比，改進的算法能夠明顯地延長網絡生存時間。

關鍵詞：無線傳感器網絡； 分簇算法； 協調件協議； 生存周期

中圖分類號：TN91134 文獻標識碼：A 文章編號：1004373X（2012）22009704

0 引 言

無線傳感器網絡（WSN）是由具有感知、計算存儲和無線通信能力的微型傳感器組成的網絡，由于其具有自組織、自治、自適應等屬性，已廣泛應用于軍事偵察、醫療監護、環境監測、農業養殖等領域［1］。由于無線傳感器網絡節點體積小，一般都依靠電池供電，但是電池容量有限，而網絡中節點數量巨大，節點的更換和能量補充很難實現，因此，如何最大限度地節省能源的使用以及延長整個網絡的生存時間是無線傳感器網絡研究的關鍵［24］。

針對上述問題，國內外提出了多種路由算法，其中分簇路由算法是比較符合傳感器網絡特性的高效算法。LEACH就是一種經典的分簇路由算法，它的基本思想是以循環方式隨機選取簇首，將網絡的能量負載平均到每一個節點上，從而降低能耗和延長網絡生存時間。但是LEACH算法存在一些不足，主要是由于簇首節點在整個網絡傳輸中擔負著重要角色，一旦簇首節點死亡則整個網絡就會出現數據丟失，產生監控盲點［5］。本文提出了一種能夠有效提高簇首生存時間的算法，其與LEACH算法相比能夠更加有效的提高網絡的生存時間。

1 LEACH協議簡介

LEACH協議［6］是一種按層次分簇的自適應路由算法，它將整個網絡節點分成不同的簇，并以簇首產生概率p在其中選出簇首節點，簇首節點負責收集簇內節點的信息和簇間數據通信。并引入“輪”（round）的概念，通過周期性的簇重構來避免簇首節點能量消耗過快，從而提高了整個網絡的生存時間。每一輪都包括2個階段：簇建立階段和數據傳輸階段。

簇建立階段：每個節點都產生一個0～1之間的隨機數，如果某個節點產生的隨機值小于設定的閾值T（n），則選擇該節點為簇首節點。式（1）是閾值T（n）的定義：T（n）=p1－p·（r mod1p），n∈G

0，其他

（1）式中：p為簇首節點在傳感器網絡節點中所占的百分比；r為當前所進行的輪次；G為上一輪選擇中未被選中為簇首的節點集合。當簇首選擇完成后，簇首節點使用CSMAMAC協議以相同能量對整個網絡進行廣播通知。網絡中的其他節點通過接收到廣播信號的強弱自主選則加入到哪個簇，并通知所屬簇首節點。之后，簇首節點產生一個TDMA進度表并在簇內廣播，簇內節點按照進度表分配的時隙與簇首節點進行通信。

數據傳輸階段：當整個網絡完成簇劃分并確定TDMA進度表后，即進入本輪的數據傳輸階段。簇首節點將接收到的簇內節點采集的數據融合后，發送到基站。經過一定時間的傳輸段后，進行新一輪的簇首選擇過程。

LEACH算法與一般的平面路由算法相比較，具有能量消耗明顯減少，整個網絡負載相對均衡的特點，從而延長了網絡的生存時間，據文獻［7］研究可提高30%左右的網絡生命周期。但LEACH算法的不足之處在于，一方面簇首的選擇沒有考慮到節點的剩余能量，這樣就會出現剩余能量少的節點被選成簇首的情況，從而導致這個簇首節點迅速死亡，造成網絡盲點。另一方面，當簇建立后簇首節點在無數據傳輸時仍然處于活躍狀態，能量白白消耗，降低了網絡的生存時間［8］。

2 改進的LEACH算法

針對LEACH算法的不足，考慮到簇首節點擔負著融合簇內信息，并且發送至BS的任務，簇首節點的壽命在很大程度上影響了整個網絡的生存時間。在這里提出了兩點改進方法：

（1） 在簇首選擇時考慮節點剩余能量，避免能量低的節點被選為簇首節點；

（2） 在簇建立后，簇內通信方式引入MD協議，從而起到減少簇首能量消耗，提高全網生存時間的作用。

2.1 無線傳感網絡模型說明

本文假定N個傳感器節點隨機均勻分布在一個二維平面區域內，且具有如下性質［9］：

（1） 傳感器節點布置后不再移動；

（2） 傳感器節點同構，能量相同，且每一節點有惟一的標志ID，區域內有惟一的基站（Base Station，BS）；

（3） 所有節點具有相似的處理能力（處理/通信），并且地位平等；

（4） 每一個節點都能與網絡中其他任何節點通信，也能與基站直接通信。

2.2 協調件協議

在MD協議（Mediation Device Protocol） 中［10］，使用MD節點接收網絡內所有通信請求，其作用是預先使網絡內節點進入睡眠狀態，當收到通信請求時喚醒網絡內相應節點進行數據傳輸，通過這種方法節約整個系統的能量消耗。MD協議不需要額外添加新的硬件，對節點電池壽命的影響也很小。

網絡中節點平均耗能表示為：E=μEa+（1-μ） *Es

（2）式中：E表示平均功耗，μ為節點工作占空比［11］（一個完整的喚醒周期包括休眠時段和監聽時段，監聽時段與喚醒時段的時間長度之比就是占空比。） Ea為活動狀態下的功耗， Es為待機狀態下的功耗。在實際應用中，大多數時候Ea> >Es，所以可以通過降低占空比來延長網絡壽命，引入協調件協議就是在保持功耗最小化的同時實現穩定的時間同步。

如果節點A需要傳輸數據到節點B，則A發送RTS（Request To Send）信標到MD節點，信標中包含目的節點B的地址和數據傳輸請求。MD節點向目的節點B發送喚醒信號。B節點收到喚醒信號后醒來并根據查詢信標等待一點時間接收數據，如果期間無數據傳輸則返回睡眠狀態，如果節點得到數據被收到的確認后，A和B均返回睡眠。使用MD節點使網絡中的節點只在有數據傳輸時網絡節點才會被喚醒，從而減少了節點能耗，延長了網絡的生存時間。

MD協議具有以下優點：

（1） 進行數據傳輸的節點之間無需同步時間；

（2） MD協議是能量的消耗集中在MD節點上，其他節點大部分時間都處于睡眠狀態，而睡眠狀態期間主要的能量消耗只產生在收發周期性信標時。

2.3 簇首選擇階段

在網絡的初始階段，所有節點的能量都是相同的，但經過幾個輪次后，節點的剩余能量會存在很大的不同，為避免能量低的節點被選擇成為簇首，導致整個網絡穩定性下降，我們將節點剩余能量作為簇首選擇時的一個參數，來保證剩余能量多的節點被選擇成為簇首的概率加大。

Ecurrent表示當前節點剩余能量，Eoriginal表示節點的初始能量，r表示已經過的輪次，v表示節點被選擇成為簇首的次數，令：λ=（r－v）EcurrentrEoriginal

（3）將式（3）引入LEACH算法簇首的閾值計算中，則改進的閾值計算公式變為：T（n）=p1－p（rmod1p）λ，n∈G

0，其他

（4） 通過加入節點的當前的剩余能量作為簇首的選擇條件，算法能夠有效地降低剩余能量較小的節點被選為簇首節點的幾率，避免了出現簇首節點迅速死亡造成網絡盲點的現象。

2.4 穩定運行階段

在簇內通信階段，簇首節點周期性地進入睡眠狀態，只有當接收到MD節點發來的喚醒信號才進入活躍狀態。此時簇首節點準備接收數據，簇內節點在基于TDMA分配的時隙中與簇首節點進行數據傳輸。一旦簇首節點完成了數據收集，則將其融合后傳給BS。

當簇內節點采集到數據后，該節點保存數據直至他所分配到的時隙來臨。此時其按照如下步驟進行數據傳輸：簇內節點連續發送RTS（請求和發送）信標到MD節點，并等待RTS應答；MD節點發送一個喚醒消息給簇首節點，消息中包含請求通信節點的地址；簇首節點收到MD節點的喚醒消息后，根據消息中的地址發送CTS（清除和發送）信標，傳輸開始；當得到消息被收到的確認后，簇首節點返回睡眠狀態。在這里假定節點所分配的時隙足夠完成數據傳輸。通過這種方法盡可能多地使簇首節點保持睡眠狀態，從而減少了能量消耗。當簇首節點能量低于一定水平時，進行新一輪的簇首選舉過程。

如圖1所示，具體算法描述如下：

（1） 簇內節點

當節點采集到數據并且當前是它所在的時隙時：

① 向MD節點發送RTS請求；

② 等待簇首節點發回的CTS；

③ 向簇首節點傳送數據；

④ 收到確認（ACK）信號。

（2） MD節點

當收到簇內節點發來的RTS請求時，向簇首節點發送喚醒信標。

（3） 簇首節點

當收到喚醒信標：

① 向請求通信的節點發送CTS信號；

② 接收數據；

③ 傳輸完成后發回確認（ACK）信號；

④ 無通信請求返回睡眠狀態。

圖1 簇首節點在MD節點協調下的數據傳輸過程3 仿真與結果分析

3.1 仿真環境

為了驗證和評價改進后的算法性能，在這里使用Matlab軟件進行仿真。采用文獻［6］的無線通信系統模型，當發送方傳輸k比特的數據與距離為d的節點通信時，發送和接收方所消耗的能量分別為：

發送信息時的能耗：

ETx（k，d）=ETx-elec（k）+ETx-amp（k）

=Eelec×k+εfs×k×d2， d≤d0

Eelec×k+εmp×k×d4， d≥d0

（5）

接收時的能耗：ERx（k）=ERx－elec（k）

ERx（k）=Eeleck

（6）式中：Eelec表示發送和接收電路功耗；εfs表示當接收雙方的距離d小于閾值d0時的放大電路功耗；εmp表示當接收雙方的距離d大于或等于閾值d0時的放大電路功耗。整個網絡是在100 m×100 m的正方形監測區域中隨機分布著100個無線傳感器節點，如圖2所示。具體仿真的試驗參數如表1所示。

3.2 實驗結果分析

延長網絡壽命的一個重要因素是如何能夠更有效地使用網絡中節點的能量。圖3分別對改進算法和LEACH的能耗情況進行了仿真對比。由圖3可以看出，改進的算法的能耗與LEACH算法的相比明顯降低，這是因為該進算法在成簇階段考慮到節點的剩余能量，避免了剩余能量較低的節點被選為簇首節點，在穩定運行階段改進的算法簇首節點盡可能多的保持睡眠狀態從而降低了能量消耗。

網絡生命周期比較如圖4所示。在圖4中，將改進算法和LEACH的生命周期進行了對比。在相同的參數設置條件下，分別對2種算法對每輪過后網絡中存活節點數目進行統計，取200次仿真實驗中每輪存活節點數目的平均值?？梢钥闯?，改進的算法比LEACH算法的網絡生命周期延長了約14%，有效的提高了網絡的工作效率。

本文針對無線傳感器網絡中傳感器節點能量有限、能耗不均衡的問題，通過改進簇首選擇規則，引入協調件協議的有關算法，提出了一種在成簇階段有效降低剩余能量低的節點被選擇成為簇首，穩定運行階段使簇首節點盡可能多的保持睡眠狀態，從而達到節約能量和提高整個網絡生存周期的改進算法。實驗結果表明，該算法相對于LEACH協議改進的算法在延長網絡生存時間方面取得了良好的效果。

參 考 文 獻

［1］ 孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京：清華大學出版社，2005.

［2］ FAN Xiangning， SONG Yulin. Improvement on LEACH protocol of wireless sensor network ＼[C＼]// Proceedings of the International Conference on Sensor Technologies and Applications. Valencia： ICSTA， 2007： 260264.

［3］ BUTT I， KHAN S. Analyzing enhancing energy efficient communication protocol for wireless microsensor networks ＼[C＼]// Proceedings of the International Conference. ＼[S.l.＼]： ICICT， 2005： 123129.

［4］ ABUHELALEH M， MISMAR T， ABUZNEID A. ArmorLEACHenergy efficient， secure wireless networks communication ＼[C＼]// Proc. of the ICCCN. ＼[S.l.＼]： ICCCN， 2008： 222227.

［5］ POTTIE G J， KAISER W J. Wireless intergated network sensors ＼[J＼].Communication. 2000， 43（5）： 5158.

［6］ HEINZELMAN W， CHANDRAKASAN A， BALAKRISHNAN H. Energyefficient communication protocol for wireless microsensor networks ＼[C＼]// Proc.of the 33rd Annual Hawaii International Conf. on System Science. Maui， USA： IEEE Computer Society， 2000： 30053014.

［7］ IBBINI E. An efficient mechanism for saving energy of LEACH protocol in WSN ＼[D＼]. Jordan： Computer Science， Jordan University of Science Technology， 2010.

［8］ XUNBO L， NA L， LIANG C S， et al. An improved LEACH for clustering protocols in wireless sensor networks ＼[C＼]// Proceedings of the IEEE International Conference on Measuring Technology and Mechatronics Automation. ＼[S.l.＼]： IEEE， 2010： 111117.

［9］ 彭鐸，張秋余，賈科軍.能量高效的無線傳感器網絡分簇路由協議［J］.計算機工程，2009，35（17）：123126.

［10］ KARL H， WILLING A. Protocols and architecture for wireless sensor network ＼[M＼]. ＼[S.l.＼]： John Wiley and Sons， 2005.

［11］ AKYILDIZ I， SU W， SANKARASUBRAMANIAM Y， et al. A survey on sensor networks ＼[J＼]. IEEE Communications Magazine， 2002 （9）： 1118.

［12］ ELHOIYDI A. On the lifetime of wireless sensor networks ＼[J＼]. ACM Transactions on Sensor Networks， 2009， 5（1）： 3539.

作者簡介： 韓媛萍 女，1981年出生，貴州人，工程師，碩士。研究方向為無線通信技術。