路由算法LEACH的改進研究

應越

（杭州師范大學錢江學院，浙江 杭州 310012）

一.引言

LEACH（Low-Energy Adaptive Clustering Hierarchy）協議是第一個在無線傳感網絡中提出的分簇式路由協議，其后的大部分分簇式路由協議都是在它的基礎上發展而來的。LEACH協議是MIT的Heinzelman等人為無線傳感器網絡設計的低功耗自適應分簇式路由算法。該算法的基本思想是先將傳感節點恰當分簇（Clustering），然后為每個簇（Cluster）選取簇頭，簇內非簇頭節點直接與簇頭通信，而簇頭節點在接收到本簇之內所有節點的數據后進行數據融合，然后發給數據Sink。該算法通過隨機選擇每簇簇頭，平均分擔中繼通信業務來實現負荷的均勻分擔。LEACH協議定義了"輪"(round)的概念，每一輪隨機選擇簇頭，動態分簇，由簇頭承擔中繼通信業務。下一輪工作周期重新選擇簇頭并分簇。采用這種方法可以使因中繼業務繁重而衰竭的節點呈均勻分布狀態，LEACH可以延長網絡的生命周期。但是LEACH假設所有的節點都能直接與每簇簇頭和Sink通信，因每簇的大小受限，而且整個網絡規模的擴張性也并不良好。而且動態分簇引起路由計算的時延和計算處理的能耗。當然，LEACH算法的主要缺陷為：非簇頭節點均需直接和簇頭節點通信，參與大距離通信的節點數目依然很多。

二.LEACH算法概述

1.算法環境

在開發協議的過程中，對傳感器網絡和網絡模式做了如下假設：

假設所有節點都能夠與匯聚點直接通信；節點可以使用電源控制來控制發送能量的不同；每個節點都具備支持不同MAC協議的計算能力；進行信號處理的能量是可以計算的。

無線傳感器節點能量受限，在最初的簇首選擇回合中，所有的節點都攜帶相同的能量，并且每個成為簇首的節點都消耗大致相同的能量。無線電信號傳輸在各個方向上能量消耗相同。節點可感知它的剩余能量，并能相應地改變它的發射功率。

2.算法描述

LEACH(Low-Energy Adaptive Clustering Hierarchy)協議是第一個在無線傳感器網絡中提出的層次式路由協議，其后的大部分層次式路由協議都是在它的基礎上發展而來的。LEACH協議節約能量的主要原因是它運用了數據壓縮技術和分層動態路由技術，通過本地的聯合工作來提高網絡的可擴展性和魯棒性，通過數據融合來減少發送的數據量，通過把節點隨機地設置成群頭節點來達到網絡內部負載均衡的目的，防止群頭節點的過快死亡。LEACH協議分為兩個階段操作，即簇類建立階段（set-upphase）和穩定工作階段（steady-state phase）。簇類建立階段和穩定工作階段持續時間總和為一輪（round）。在簇類建立階段，LEACH協議隨機選擇一個傳感器節點作為簇頭節點，隨機性確保簇頭與Sink之間數據傳輸的高能耗成本均勻的分攤到所有傳感器節點。在簇頭節點選定后，該節點對網絡中所有節點進行廣播，廣播數據包含有該節點成為簇頭節點的信息。一旦傳感器節點收到廣播數據包，根據接收到的各個簇頭節點廣播信號強度，該節點選擇信號強度最大的簇頭，加入該簇，發送成為其成員節點的數據包。分簇形成后，簇頭采用TDMA策略分配信道使用權給成員節點。一旦處于穩定工作階段，簇頭節點開始接收該簇中每個節點采集的數據，然后采用數據融合和數據壓縮等技術進行匯聚，將整合后的數據傳輸給Sink，在穩定階段持續一段時間后，網絡又進入另一次分簇建立階段。

3.存在不足

從上一節的分析，我們知道LEACH協議的精華內容是分布式的成簇技術和自適應的成簇算法以及簇首位置的輪換算法。其中分布式的成簇技術保證了大數口的節點的自組織行為。自適應的成簇算法以及簇首位置的輪換算法保證所有節點公平地承擔能量消耗的負擔，最終可以延長整個系統的生存時間。主要的不足有些下幾方面：

①簇首的產生具有極大的隨機性，可能會出現部分簇首相距sink節點太遠或部分簇內成員離簇首太遠的情況，大大增加了節點的傳輸能耗，故不能有效地延長網絡生存時間。

②LEACH算法隨機選擇簇首并沒有考慮到節點的能量狀態，不能有效提高網絡的生存時間。能量消耗均衡機制要求所有節點的初始能量相同，但這在實際的應用中保證此初始條件比較困難。

③由于每輪固定簇頭之后再建立簇類，所以簇頭開銷較大，并且離散式區域算法雖然對于節點位置等要求不高，但無法做到最優。

④由于LEACH要求節點之間以及節點與基站之間均可以自接通信，所以網絡的擴展性不強，并且不適用于大型網絡。

⑤LEACH的傳輸距離較遠，并且數據融合相對較少，這就要求傳輸更多的數據到更遠的距離，從而加大了能量消耗。

三.LEACH算法改進

為了避免低能量級與位置不佳的節點被選為簇首，進一步均衡整個網絡的能量負載分布，提出一種新型的簇首選擇機制。LEACH提出簇頭位置隨機輪換算法來避免太快地消耗完某個充當簇頭節點的能量，就是讓簇類中的每個節點輪流成為簇頭，這樣就能避免由于一個節點的失效而引起的網絡癱瘓，起到延長整個網絡生命周期的作用。但是LEACH協議的簇頭位置輪換算法是山每個簇頭產生一個隨機數并與系統給定的門限值比較，即簇頭是每輪隨機產生的，故有可能存在某一節點的剩余能量己經很小但仍被選為簇頭節點的情況。這樣這個節點的能量就可能很快耗盡。

該算法在LEACH的基礎上，利用加權思想使節點產生一個改進的權值概率，通過與隨機產生的概率閾值相比來選擇簇首，進而生成整個簇，改進的權值概率要綜合考慮節點所處的網絡環境和本身狀態。基于網絡能耗最小的考慮，通過數學推導和仿真實驗，一般選取簇首比例為5%，為了使得權值概率能維持5%的平均值，權值因子可以起到調節作用，以確保最優簇首個數的選取。

權值因子在成簇概率中調節著距離因素和剩余能量因素之間的權衡關系，權值因子值的確定自接影響著成簇概率的大小，決定了協議優化的效果。看出，隨著權值因子的增大，第一個節點死亡的時間也隨之減小，這是因為隨著權值因子的增大，距離函數開始占據主要作用，導致網絡中處于理想位置的節點更容易成為簇首，增加了這部分節點的能量消耗，從而使得這些節點過早的死亡。反之，權值因子減小的時候，簇首主要是根據網絡中的節點的剩余能量來選擇，所以更進一步的考慮了網絡的能量消耗平衡，使得網絡中第一個節點死亡的時間往后推遲。隨著權值因子增大時，處于理想位置的節點總是優先被選為簇首，所以減小了網絡的總能量消耗，進而使得網絡中最后一個節點死亡的時間得到延遲。

結束語

本文在LEACH協議的基礎上使用新型的簇首選擇機制來擴大了LEACH協議的應用范圍，算法利用加權思想綜合考慮節點的剩余能量、地理位置等參數來優化簇首的選擇，從而有效地避免了低能量與位置不佳的節點被選為簇首的可能性，進一步保證網絡內節點能量負載的均衡性。結果表明，與LEACH協議相比，新型的簇首選擇機制算法明顯延長了網絡的生存壽命。

[1]孫利民，李建中，陳渝，朱紅松著.無線傳感器網絡[M].北京：清華大學出版社，2006.

[2]周東清，葛午未，朱娜.基于QoS的無線傳感器網絡路由 [J].計算機工程與應用.2007，43（23）：157-160.

[3]宋文，王兵，周應賓等著.無線傳感器網絡技術與應用[M].北京：電子工業出版社，2007.