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。 ^[1] 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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