無線傳感器網絡LEACH算法淺析

黃 靜

（泉州經貿職業技術學院慈山分院，福建 泉州 360003）

無線傳感器網絡LEACH算法淺析

黃 靜

（泉州經貿職業技術學院慈山分院，福建 泉州 360003）

LEACH算法就是針對于無線傳感器網絡而提出的一種經典的層次型拓撲組織算法。對LEACH算法進行詳細的描述，闡述了該算法的不足，然后重點就現有的LEACH改進算法進行分析和比較，總結各自的優缺點，最后給出該算法研究發展方向。

無線傳感器網絡；LEACH；LEACH-C；HEED；PEGASIS

引言

無線傳感器網絡是一種全新的信息獲取技術，是新興的下一代無線網絡，具有廣泛的應用前景。傳感器節點主要由電池供電，且大都分布在無人看管、幾乎不可能更換電池的環境中，如何能提高能量的有效利用率并延長網路壽命是一個重要的問題。對網絡通信及拓撲控制方面的研究現在正成為無線傳感器網絡研究中的熱點。LEACH（低功耗自適應分簇）算法就是針對無線傳感器網絡而提出的一種層次型拓撲組織算法。本文首先對經典的LEACH算法進行深入研究，并結合前人工作已提出的一些較為重要的改進算法進行對比和剖析。最后探討了今后研究的方向，指出了下一步研究中的重點。

1 .LEACH算法

LEACH（Low-Energy Adaptive Clustering Hierarchy）是一種自適應分簇拓撲算法，它的執行過程是周期性的，每輪循環分為簇的建立階段和穩定的數據通信階段。在簇的建立階段，相鄰節點隨機產生簇頭，動態地形成簇；在數據通信階段，簇內節點把數據發送給簇頭，簇頭進行數據融合并把結果發送給匯聚節點。LEACH算法中簇頭的選擇是依據網絡中所需要的簇頭節點總數和迄今為止每個節點已成為簇頭的次數來決定的。具體的選擇辦法是：每個傳感器節點選擇0-1之間的一個值，如果選定的值小于某個閾值，那么這個節點成為簇頭節點。節點當選簇頭以后，廣播告知其他節點自己是新簇頭。非簇頭節點根據自己與簇頭之間的距離來選擇加入哪個簇，并告知該簇頭。當簇頭接收到所有的加入信息后，就產生一個TDMA定時消息，并且通知該簇中所有節點。為了避免附近簇的信號干擾，簇頭可以決定本簇中所有節點所用的CDMA編碼。這個用于當前階段的CDMA編碼連同TDMA定時一起發送。當簇內節點收到這個消息后，它們就會在各自的時間槽內發送數據。經過一段時間的數據傳輸，簇頭節點將運行數據融合算法來處理收到的數據，并將結果直接發送給匯聚節點。

2 .存在不足

LEACH算法還沒有考慮節點的能量狀態，如果某一節點的剩余能量很小，仍有同樣幾率被當選為簇頭；在LEACH算法中，簇頭的產生具有隨機性，簇頭分布不均勻，有可能會出現部分地區簇頭密度大，部分地區簇頭稀少的現象；LEACH 算法選舉簇頭的機制也具有隨機性，沒有控制每輪簇頭的數量；LEACH算法還是經典的一跳算法，即簇內成員向簇頭發送信息是一跳將數據發送給簇頭。它要求節點具備較大的通信能力，以滿足節點間能進行直接通信。這也使得部分網絡節點的能量消耗過快，不利于網絡能量的充分利用。

3 .現有改進

HEED算法主要是針對LEACH算法生成簇的簇首分布不均勻這個問題進行了改進。該算法構建了一種節能、分布式的成簇策略，但在選擇簇頭時需要在一定的迭代次數內與周圍鄰居節點不斷地緊系信息交互，因此該算法的實現也需要額外的通信代價。同時，針對節點一跳發送數據造成的能量過快消耗問題，在LEACH算法的基礎上，Lindsey等人提出了PEGASIS算法，其思想是進一步減少直接與基站通信的節點。PEGASIS將網絡中的所有節點連成一條鏈，數據在鏈上進行融合處理，最后傳輸至基站。但是，該算法需要知道每個節點的位置信息，開銷非常大。文提出通過構造生成樹，使得簇內生成樹中的節點基本都是選擇距離自身最近的簇成員節點為自己的父節點，簇首生成樹中的簇首節點基本都是選擇距離自身最近的簇首為父節點。所以，在數據收集中，各個節點都基本上與距離自身最近的節點通信，而且沒有增加LEACH的時延（不像PEGASIS）。但是它也有其局限性。由于傳感器節點的處理能力有限，對于需要大量原始數據上傳、聚合過程復雜或聚合后數據尺寸急劇膨脹的應用場景，文中算法就不太適用。因此，該算法只適用于中小型無線傳感器網絡。

4 .小結

目前，對于LEACH算法的改進大都只是從個別的幾個因素來考慮，很少關注全局的網絡特征。還不存在一個能適用于所有網絡場景的十全十美的算法，每種算法都存在某些方面的劣勢。而且改進的策略有相當部分在仿真實驗中可以取得較好的效果，在實際網絡中往往會有些偏差，還是有待進一步的驗證。

[1] 熊昊翔，李峰，李平. 基于節能的無線傳感器網絡 LEACH協議改進[J]. 計算機技術與發展，2007，（11）.

[2] 陳建明，王青海，路建軍. 自適應分簇拓撲算法EC-LEACH的研究[J]. 測試技術學報，2008，（6）.

TP212

A

1008-7427（2010）01-0160-01

2009-11-18