應(yīng)越

（杭州師范大學(xué)錢江學(xué)院，浙江 杭州 310012）

一.引言

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

二.LEACH算法概述

1.算法環(huán)境

在開發(fā)協(xié)議的過程中，對傳感器網(wǎng)絡(luò)和網(wǎng)絡(luò)模式做了如下假設(shè)：

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

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

2.算法描述

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

3.存在不足

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

①簇首的產(chǎn)生具有極大的隨機性，可能會出現(xiàn)部分簇首相距sink節(jié)點太遠或部分簇內(nèi)成員離簇首太遠的情況，大大增加了節(jié)點的傳輸能耗，故不能有效地延長網(wǎng)絡(luò)生存時間。

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

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

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

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

三.LEACH算法改進

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

該算法在LEACH的基礎(chǔ)上，利用加權(quán)思想使節(jié)點產(chǎn)生一個改進的權(quán)值概率，通過與隨機產(chǎn)生的概率閾值相比來選擇簇首，進而生成整個簇，改進的權(quán)值概率要綜合考慮節(jié)點所處的網(wǎng)絡(luò)環(huán)境和本身狀態(tài)。基于網(wǎng)絡(luò)能耗最小的考慮，通過數(shù)學(xué)推導(dǎo)和仿真實驗，一般選取簇首比例為5%，為了使得權(quán)值概率能維持5%的平均值，權(quán)值因子可以起到調(diào)節(jié)作用，以確保最優(yōu)簇首個數(shù)的選取。

權(quán)值因子在成簇概率中調(diào)節(jié)著距離因素和剩余能量因素之間的權(quán)衡關(guān)系，權(quán)值因子值的確定自接影響著成簇概率的大小，決定了協(xié)議優(yōu)化的效果?？闯?，隨著權(quán)值因子的增大，第一個節(jié)點死亡的時間也隨之減小，這是因為隨著權(quán)值因子的增大，距離函數(shù)開始占據(jù)主要作用，導(dǎo)致網(wǎng)絡(luò)中處于理想位置的節(jié)點更容易成為簇首，增加了這部分節(jié)點的能量消耗，從而使得這些節(jié)點過早的死亡。反之，權(quán)值因子減小的時候，簇首主要是根據(jù)網(wǎng)絡(luò)中的節(jié)點的剩余能量來選擇，所以更進一步的考慮了網(wǎng)絡(luò)的能量消耗平衡，使得網(wǎng)絡(luò)中第一個節(jié)點死亡的時間往后推遲。隨著權(quán)值因子增大時，處于理想位置的節(jié)點總是優(yōu)先被選為簇首，所以減小了網(wǎng)絡(luò)的總能量消耗，進而使得網(wǎng)絡(luò)中最后一個節(jié)點死亡的時間得到延遲。

結(jié)束語

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

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

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

[3]宋文，王兵，周應(yīng)賓等著.無線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用[M].北京：電子工業(yè)出版社，2007.