LEACH

LEACH協定，全稱是“低功耗自適應集簇分層型協定” (Low Energy Adaptive Clustering Hierarchy)，是一種無線感測器網路路由協定。基於LEACH協定的算法，稱為LEACH算法。

基本介紹

• 中文名：低功耗自適應集簇分層型協定
• 外文名：LEACH
• 屬性：無線感測器網路路由協定
• 算法基本思想：以循環方式隨機選擇簇頭節點

算法簡介

LEACH算法是一種無線感測器網路路由協定，來源於Wendi Rabiner Heinzelman, Anantha Chandrakasan, 和Hari Balakrishnan三人在2000年Proceedings of the 33rd Hawaii International Conference on System Sciences上的一篇文章Energy-Efficient Communication Protocol for Wireless Microsensor Networks。

該算法基本思想是：以循環的方式隨機選擇簇頭節點，將整個網路的能量負載平均分配到每個感測器節點中，從而達到降低網路能源消耗、提高網路整體生存時間的目的。仿真表明，與一般的平面多跳路由協定和靜態分層算法相比，LEACH分簇協定可以將網路生命周期延長15%。

運行過程

LEACH在運行過程中不斷的循環執行簇的重構過程，每個簇重構過程可以用回合的概念來描述。每個回合可以分成兩個階段：簇的建立階段和傳輸數據的穩定階段。為了節省資源開銷，穩定階段的持續時間要大於建立階段的持續時間。簇的建立過程可分成4個階段：簇頭節點的選擇、簇頭節點的廣播、簇頭節點的建立和調度機制的生成。

簇頭節點的選擇依據網路中所需要的簇頭節點總數和迄今為止每個節點已成為簇頭節點的次數來決定。具體的選擇辦法是：每個感測器節點隨機選擇0-1之間的一個值。如果選定的值小於某一個閾值，那么這個節點成為簇頭節點。

選定簇頭節點後，通過廣播告知整個網路。網路中的其他節點根據接收信息的信號強度決定從屬的簇，並通知相應的簇頭節點，完成簇的建立。最後，簇頭節點採用TDMA方式為簇中每個節點分配向其傳遞數據的時間點。

穩定階段中，感測器節點將採集的數據傳送到簇頭節點。簇頭節點對簇中所有節點所採集的數據進行信息融合後再傳送給匯聚節點，這是一種較少通信業務量的合理工作模型。穩定階段持續一段時間後，網路重新進入簇的建立階段，進行下一回合的簇重構，不斷循環，每個簇採用不同的CDMA代碼進行通信來減少其他簇內節點的干擾。

LEACH路由協定主要分為兩個階段：即簇建立階段(setup phase)和穩定運行階段(ready phase)。簇建立階段和穩定運行階段所持續的時間總和為一輪(round)。為減少協定開銷，穩定運行階段的持續時間要長於簇建立階段。

在簇建立階段，感測器節點隨機生成一個0，1之間的隨機數，並且與閾值T(n)做比較，如果小於該閾值，則該節點就會當選為簇頭。T(n)按照下列公式計算：式中：P為節點成為簇頭節點的百分數，r為當前輪數，G為在最近的1/p輪中未當選簇頭的節點集合。簇頭節點選定後，廣播自己成為簇頭的訊息，節點根據接收到的訊息的強度決定加入哪個簇，並告知相應的簇頭，完成簇的建立過程。然後，簇頭節點採用TDMA的方式，為簇內成員分配傳送數據的時隙。

在穩定階段，感測器節點將採集的數據傳送到簇頭節點。簇頭節點對採集的數據進行數據融合後再將信息傳送給匯聚節點，匯聚節點將數據傳送給監控中心來進行數據的處理。穩定階段持續一段時間後，網路重新進入簇的建立階段，進行下一輪的簇重建，不斷循環。

協定特點

1 為了減少傳送到匯聚節點的信息數量，簇首節點負責融合來自簇內不同源節點所產生的數據，並將融合後的數據傳送到匯聚點。

2 LEACH採用基於TDMA/CDMA的MAC層機制來減少簇內和簇間的衝突。

3 由於數據採集是集中的和周期性的，因此該協定非常適合於要求連續監控的套用系統。

4 對於終端使用者來說，由於它並不需要立即得到所有的數據，因此協定不需要周期性的傳輸數據，這樣可以達到限制感測器節點能量消耗的目的。

5 在給定的時間間隔後，協定重新選舉簇首節點，以保證無線感測器網路獲取統一的能量分布。

儘管LEACH能夠提高網路的生存時間，但是 協定所使用的假設條件仍存在著一些值得討論的問題。

局限性

1 由於LEACH假定所有節點能夠與匯聚節點直接通信，並且每個節點都具備支持不同MAC協定的計算能力，因此該協定不適合在大規模的無線感測器網路中套用。

2 協定沒有說明簇頭節點的數目怎么分布才能及於整個網路。因此，很可能出現被選的簇頭節點集中在網路某一區域的現象，這樣就會使得一些節點的周圍沒有任何簇頭節點。

3 由於LEACH假定在最初的簇頭選擇回合中，所有的節點都攜帶相同的能量，並且每個成為簇頭的節點都消耗大致相同的能量。因此，協定不適合節點能量不均衡的網路。