摘 要：分層路由算法是延長無線傳感器網絡壽命的一個重要方法。然而現有的分簇算法大都存在著負載能量不均衡的問題。本文主要針對經典分簇算*EACH，對其基本思想、分簇機制和簇的通信方式等作了分析，同時對其負載能量不均衡的問題作出改進，并用MATLAB進行仿真分析。仿真后的結果表明，改進后的算法能夠均衡節點的能耗，使分簇更加合理，有效延長了網絡的生命周期。

0 引言

無線傳感器網絡是近年來信息技術領域的一個研究熱點，它融合了傳感器、計算機科學、信號與信息處理、通信等多個領域的技術。作為一個新興的、正在發展的技術領域，業界對其研究正在不斷深入。無線傳感器網絡為人類與客觀物理世界的交互提供了一種新的有效手段，它的諸多特點使其應用范圍涉及軍事應用、工業監視與控制、醫療監護、智能家居、物流管理、消費電子等諸多領域，具有廣闊的市場及產業前景。2003 年8 月，美國《商業周刊》的技術*論將無線傳感網絡定位成21 世紀高技術領域的四大支柱型產業之一。

在無線傳感器網絡中，能量有效性是網絡性能的一個重要指標。它對能源消耗有著很嚴格的限制，應盡可能少地消耗能量以達到延長網絡生命周期的目的。因此，設計一種良好的路由協議，減少不必要的能源消耗是非常必要的。本文主要探討了低能量自適應聚類協議（LEACH），指出了LEACH 協議存在的缺陷，并給出相應的解決方案加以優化。

1 經典LEACH 協議分析

1.1 算法描述

LEAC(Low-Energy Adaptive CluSTering Hierarchy）協議是針對無線傳感網絡設計的一種低功耗自適應分層路由算法，是最早提出的分簇路由協議。它的基本思想是以循環的方式隨機選擇簇頭節點，其他各節點根據接收到的來自簇頭的信號強度進行集群分組，使得整個網絡的能量負載平均分配到每個傳感器節點中，從而降低網絡能源消耗，提高網絡整體生存時間。

LEACH 協議定義了“輪”的概念，每一輪由簇的建立和穩定狀態階段組成。在簇的建立階段，首批簇頭的選取是隨機的。對于一個節點n 而言，為其隨機選取一個在0 到1 之間的隨機數，若這個數字小于一個門限值T(n)，則節點n 就成為本輪的簇頭節點。門限T(n)定義如下：

其中，P 是網絡中簇頭節點占總節點數目的百分比；r 是當前的輪數；G 是在前1/P 輪中沒有擔當過簇頭節點的節點集合；符號mod 是求模運算符號。

簇頭節點選定后，向周圍廣播自己成為簇頭的信息（ADV），非簇頭節點根據接收到的信號強度來決定從屬的簇類。當簇頭收到反饋消息后，便為簇內節點分配時隙（基于TDMA 方式）。在穩定階段，簇內節點在自己時隙到來時刻向簇頭發送檢測數據，簇頭節點則將接收到的數據后進行必要的融合后傳送到基站或匯聚節點。經過一段時間的數據傳送后，網絡重新進行簇的建立階段，進行下一輪的簇重建，如此循環。

1.2 LEACH 算法的局限性

LEACH 算法將負載均勻地分布在整個網絡上，大大節約了通信過程中的能量損耗。簇頭位置的輪換算法把遠距離通信的負載輪流分配給網絡節點，可以延長整個系統的生存時間。另外，簇頭節點在處理數據時用到了數據融合和數據壓縮技術，使得傳輸的數據量大大減小。但LEACH 算法同時也存在著許多不足之處：

(1)簇頭選擇問題 。LEACH 協議的簇頭是隨機產生的，選擇機制中沒有考慮節點的剩余能量和節點已經做過簇頭的次數。一旦所剩能量較少的節點成為簇頭，將會很快耗盡其能量，過早死亡。其簇內成員也將因收不到已死簇頭發出的信息而不斷地發送請求信號，耗費大量的能量而導致加速死亡，降低了整個網絡的生存時間。

(2)簇頭數量問題。在 LEACH 協議隨機選擇簇頭的機制中，并沒有控制簇頭的數量。所以很有可能在某一輪中出現只產生一兩個簇頭，或產生很多簇頭的情況。若簇頭過少，則成員節點要經過很長的路徑與簇頭進行通信，簇頭也將接收大量節點的信息并向基站進行轉發。因此對每一個節點來說都負擔過重；而若產生過多簇頭，則會有過多的節點與基站通信，降低了網絡能量的利用率。

(3)簇頭分布問題。 LEACH 協議中，雖然在統計上簇頭是均勻分布的，但是由于簇頭產生的隨機性，可能會出現部分區域簇頭密度大，部分區域簇頭稀少的現象。

2 LEACH 算法的優化

上述LEACH 算法中的不足，導致了無線傳感器網絡負載能量不均衡。本文主要通過改進簇頭節點選舉算法來對LEACH 協議進行優化。主要目標是避免能量低的節點成為簇頭，控制簇頭數量達到最優，減少簇頭在每輪中分布不均的現象。從而達到降低系統能量消耗，延長網絡生命周期的最終目的。

2.1 簇頭選舉機制的算法改進

對于簇頭選舉的改進協議，在文獻[6]中將其閾值作了改進：

2.2 改進算法的具體實現

算法進行優化后詳細描述如下。

1)在簇的建立階段，簇頭由所有節點自主決定，在每一輪中自行生成k 個簇。k 的值由（4）式決定。