無線傳感器網(wǎng)絡(luò)中的LEACH算法分析與設(shè)計

摘要：在分析了經(jīng)典的LEACH分簇路由算法，以及基于LEACH算法基礎(chǔ)上的幾種經(jīng)典的改進(jìn)算法后，針對小規(guī)模無線測距網(wǎng)絡(luò)的特點，在傳輸數(shù)據(jù)量較少、簇首節(jié)點無需進(jìn)行大量數(shù)據(jù)融合的情況下，對LEACH算法進(jìn)行改進(jìn)，增加了節(jié)點與基站直接通信的個數(shù)，減少了多跳累加誤差對測距的影響。使用MATLAB軟件進(jìn)行仿真，理論與實驗仿真表明，本文提出的改進(jìn)算法能夠延長整個網(wǎng)絡(luò)的生存時間，減少了一些不必要的能量浪費。
關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；分簇路由算法；LEACH；性能分析

引言
    無線傳感器網(wǎng)絡(luò)是當(dāng)前網(wǎng)絡(luò)技術(shù)界備受關(guān)注的前沿?zé)狳c研究領(lǐng)域，涉及多學(xué)科，高度交叉，知識高度集成。無線傳感器網(wǎng)絡(luò)集成了傳感器技術(shù)、計算機技術(shù)和通信技術(shù)，在軍事、環(huán)境、健康、家庭、商業(yè)等許多方面有著巨大的潛在應(yīng)用前景。無線傳感器網(wǎng)絡(luò)由大量密集分布的傳感器節(jié)點通過自組織的方式形成網(wǎng)絡(luò)，節(jié)點通過網(wǎng)絡(luò)協(xié)議快速形成自主構(gòu)建、自主組織和自主管理的通信網(wǎng)絡(luò)。這種通過數(shù)千個微小的節(jié)點之間互相通信，通過接力的方法實現(xiàn)大范圍監(jiān)控的模式極大地提高了工作效率。然而節(jié)點大都需要在無人看管、不更換電池或者不可能更換電池的條件下長時間地工作，因此高效、低功耗路由算法在無線傳感器網(wǎng)絡(luò)中就顯得非常重要。

1 基于LEACH的經(jīng)典分簇算法分析
1．1 LEACH路由算法分析
    為了提高整個網(wǎng)絡(luò)的的生存時間，將功耗均衡的分配到網(wǎng)絡(luò)中的每個節(jié)點，麻省理工學(xué)院的Wendi Rabiner Heinzelman等人提出了一種低功耗的自適應(yīng)路由協(xié)議——LEACH協(xié)議(Low-Energy Adaptive ClusteriingHierarchy)。在LEACH協(xié)議中，每個傳感節(jié)點都有機會充當(dāng)簇頭節(jié)點，簇頭節(jié)點的選擇主要依據(jù)網(wǎng)絡(luò)中所需要的簇頭節(jié)點個數(shù)與到目前為止每個節(jié)點已經(jīng)充當(dāng)簇頭節(jié)點的次數(shù)來判定的。網(wǎng)絡(luò)中每個節(jié)點在0～1之間隨機選擇一個數(shù)，如果選擇的數(shù)小于規(guī)定閥值T(n)，則該節(jié)點就充當(dāng)簇首節(jié)點。T(n)的計算如下：
   
    式(1)中，p表示在無線網(wǎng)絡(luò)中簇頭節(jié)點所占的百分比，r為當(dāng)前循環(huán)次數(shù)，G是在前1／p輪中未充當(dāng)過簇頭節(jié)點的集合。LEACH算法通過設(shè)置T(n)值，以保證每個節(jié)點在1／p輪內(nèi)都有機會充當(dāng)一次簇頭節(jié)點，從而平衡了節(jié)點的能量消耗。簇頭節(jié)點確定之后，簇頭節(jié)點通過廣播告知整個網(wǎng)絡(luò)自己已經(jīng)成為簇頭節(jié)點，簇頭節(jié)點在廣播過程中采用CSMA MAC協(xié)議來避免沖突。這時，網(wǎng)絡(luò)中的非簇頭節(jié)點可以根據(jù)接收到的信號強度來決定自己要從屬于哪個簇，選擇信號強度最強的源節(jié)點作為自己的簇頭節(jié)點，并告知相關(guān)的簇頭節(jié)點，自己則成為簇內(nèi)組員。
    LEACH分簇算法缺點：
    ①剛開始假設(shè)每個節(jié)點能量相同，在現(xiàn)實環(huán)境中很難做到。
    ②每個節(jié)點成為簇首節(jié)點的概率相同，這樣可能導(dǎo)致一些高能量節(jié)點沒機會成為簇首節(jié)點，而一些低能量節(jié)點成為簇首節(jié)點。一旦這些低能量節(jié)點成為簇首節(jié)點，將會很快耗盡其能量。
    ③LEACH協(xié)議不能保證簇頭在每個區(qū)域都分布均勻，雖然統(tǒng)計上面是均勻的，但是由于簇頭產(chǎn)生帶有極大的隨機性，有些區(qū)域可能簇頭數(shù)會較多。
    ④簇首節(jié)點在通信過程中采用單跳與基站通信，這樣就會導(dǎo)致較遠(yuǎn)的簇首節(jié)點能量消耗過大，而過早死亡，影響整個網(wǎng)絡(luò)的性能。
    ⑤整個網(wǎng)絡(luò)節(jié)點在兩跳范圍內(nèi)，這樣不符合大規(guī)模網(wǎng)絡(luò)需求。
1．2 根據(jù)節(jié)點初始能量不同改進(jìn)
    根據(jù)整個網(wǎng)絡(luò)中節(jié)點能量的初始不同，Georgios Smaragdakis等人提出了一種改進(jìn)行分簇算法——SEP算法(a Stable Election Proto-col for clustered heterogeneous)，先把整個網(wǎng)絡(luò)分成兩類節(jié)點，能量較高的節(jié)點稱為高能量節(jié)點，能量低的稱為正常節(jié)點。高能量節(jié)點則根據(jù)式(2)進(jìn)行選擇成為簇首節(jié)點的概率，而正常節(jié)點則根據(jù)式(3)選擇成為簇首節(jié)點的概率?？梢钥闯?，高能量節(jié)點成為簇首節(jié)點的機會大于低能量節(jié)點。相較于LEACH算法，充分利用了整個網(wǎng)絡(luò)的功耗。
   
    為整個網(wǎng)絡(luò)簇首節(jié)點的概率，Pnrm為正常節(jié)點成為簇首節(jié)點的概率，Padv為高能量節(jié)點成為簇首節(jié)點的概率。r為當(dāng)前循環(huán)次數(shù)，G1是在前1／p輪中正常節(jié)點未充當(dāng)過簇頭節(jié)點的集合。G2是在前1／p輪中高能量節(jié)點未充當(dāng)過簇頭節(jié)點的集合。m為網(wǎng)絡(luò)中高能量節(jié)點的比例。a為高能量節(jié)點高于正常節(jié)點能量部分。
    在參考文獻(xiàn)中，作者對SEp算法進(jìn)行再次改進(jìn)，利用整個網(wǎng)絡(luò)節(jié)點的平均能量與節(jié)點當(dāng)前能量的比值來限制節(jié)點成為簇首節(jié)點的概率，兩類節(jié)點成為簇首節(jié)點概率如式(4)所示。
   
    根據(jù)式(4)，可以看出進(jìn)一步限制的低能量節(jié)點成為簇首節(jié)點的概率。
1．3 根據(jù)節(jié)點剩余能量的不同而改進(jìn)
    M．J．Handy等人提出了DCHS(Deterministic Clus-ter-Head Selection)算法，根據(jù)LEACH算法中的T(n)計算不足之處，對其進(jìn)行改進(jìn)，如式(5)所示。式(5)中En_current表示節(jié)點當(dāng)前的能量，En_max表示節(jié)點初始的能量。
    由改進(jìn)后的算法可以看出，當(dāng)前節(jié)點能量比較高的節(jié)點成為簇首節(jié)點的概率變大，從而降低了低能量節(jié)點成為簇首節(jié)點的概率，提高了整個網(wǎng)絡(luò)的性能。然而根據(jù)式(5)可以看出，當(dāng)整個網(wǎng)絡(luò)運行到一定的時間后，大部分節(jié)點的能量都將剩余不多，相應(yīng)的T(n)就會變小，那么整個網(wǎng)絡(luò)中節(jié)點成為簇首的概率變小，從而影響到整個網(wǎng)絡(luò)的性能。M．J．Handy等人對式(5)進(jìn)一步改進(jìn)，得到式(6)，從而有效解決了式(5)的不足之處。在式(6)中rs表示節(jié)點連續(xù)未當(dāng)選過簇頭的輪次。一旦節(jié)點當(dāng)選為簇首節(jié)點，則rs置零。
   
1．4 根據(jù)簇首節(jié)點隨機分布不均而改進(jìn)
    LEACH-C算法是LEACH算法的集中式控制版本，采用模擬退火算法獲得更優(yōu)的簇頭選舉策略，克服了LEACH算法中每輪產(chǎn)生的簇頭數(shù)與位置的隨機性。
    LEACH-C算法可以把每個節(jié)點的地理位置以及節(jié)點當(dāng)前的能量報告給基站?；景阉泄?jié)點的能量取平均，當(dāng)網(wǎng)絡(luò)中某些節(jié)點的能量低于平均值時，將不能成為候選簇頭節(jié)點，從而更加有效地解決了低能量節(jié)點成為簇頭節(jié)點的概率。
1．5 根據(jù)LEACH實時性不強而改進(jìn)
    根據(jù)LEACH算法實時性不強的問題，Manjeshwar A等人提出了TEEN算法，TEEN算法與LEACH算法較大的不同點是，在簇首節(jié)點的選舉過程中，協(xié)議設(shè)置了兩個閾值，分別為硬閾值、軟閾值兩個參數(shù)。硬閾值是被檢測數(shù)據(jù)不能超過的數(shù)值，而且軟閾值決定了被測數(shù)據(jù)的波動范圍。只有當(dāng)被監(jiān)測數(shù)據(jù)超過硬閾值且被監(jiān)測數(shù)據(jù)的變化幅度大于軟閾值時，節(jié)點才會傳送最新的監(jiān)測數(shù)據(jù)，并設(shè)置為新的硬閾值。相對于LEACH算法，TEEN算法能夠較大地減少節(jié)點之間數(shù)據(jù)傳送的次數(shù)，從而有效減少了整個網(wǎng)絡(luò)的功耗，延長了整個網(wǎng)絡(luò)的壽命。APTEEN算法則結(jié)合了LEACH與TEEN兩種算法，是一種主動型與響應(yīng)型混合的數(shù)據(jù)傳輸模式。但網(wǎng)絡(luò)中有突發(fā)事件時，數(shù)據(jù)傳輸模式將會采用與TEEN相同的模式(響應(yīng)型模式)，只不過AFTEEN算法多了一個計數(shù)器，節(jié)點每傳送一次數(shù)據(jù)，對應(yīng)的計數(shù)器將清零。當(dāng)計數(shù)器的時間到達(dá)的時候，將采取主動發(fā)送這個數(shù)據(jù)，不再判斷軟、硬門限值。
1．6 根據(jù)網(wǎng)絡(luò)節(jié)點分布密度不均而改進(jìn)
    在LEACH算法中并未考慮節(jié)點分布密度對網(wǎng)絡(luò)的影響，在分布密度大的區(qū)域，相對簇首節(jié)點的負(fù)擔(dān)也較重，能量也容易耗盡，因此應(yīng)該增加該區(qū)域簇首節(jié)點的個數(shù)。參考文獻(xiàn)中根據(jù)無線網(wǎng)絡(luò)中周圍節(jié)點存活個數(shù)不同，來改變該區(qū)域內(nèi)節(jié)點成為簇首節(jié)點的概率。為了在節(jié)點密集區(qū)域增加簇頭的個數(shù)，只需要增大對應(yīng)節(jié)點成為簇頭的概率，對于節(jié)點稀疏區(qū)域則降低其中節(jié)點成為簇頭的概率即可。因此將簇頭選舉的閾值修改為：
   
    式(7)中Neighbor(n)_alive與Network_alive分別表示表示節(jié)點n鄰居集中以及整個網(wǎng)絡(luò)中存活節(jié)點的數(shù)目，1／p表示平均每簇中節(jié)點的個數(shù)，從式(7)可以看出當(dāng)節(jié)點周圍存活個數(shù)大于平均值時，該區(qū)域節(jié)點成為簇首節(jié)點的概率將增大，反之則降低。
1．7 根據(jù)大規(guī)模多跳網(wǎng)絡(luò)而改進(jìn)
    根據(jù)LEACH算法跳距的局限性，在LEACH算法中，整個網(wǎng)絡(luò)最大跳距為兩跳，這樣就會導(dǎo)致遠(yuǎn)離基站的簇首節(jié)點，能量消耗太大而過早死亡，影響到整個網(wǎng)絡(luò)的性能，Siva D．Muruganathan等人提出了BCDCP多跳分簇算法，簇首節(jié)點的選擇由基站來控制，基站首先將每個節(jié)點的當(dāng)前能量取平均，只有大于平均值的節(jié)點才有機會成為簇首節(jié)點，這樣就避開了低能量節(jié)點成為簇首節(jié)點的可能。當(dāng)簇首節(jié)點與基站的距離超過一定時，不直接與基站通信，而是借助其他簇首節(jié)點轉(zhuǎn)發(fā)到基站，選擇其他簇首節(jié)點是采用的是最小生成樹算法，這樣就減輕了遠(yuǎn)離基站簇首節(jié)點的負(fù)擔(dān)，也擴展了整個網(wǎng)絡(luò)的規(guī)模。
1．8 節(jié)點能量傳輸模型與最優(yōu)簇首節(jié)點概率
    大部分作者都把節(jié)點傳輸模型采用公式(8)與(9)，式中k為傳輸信息的比特數(shù)，d為節(jié)點之間距離。εfs為自由空間傳送方式下的功率放大參數(shù)。式(8)為節(jié)點接收數(shù)據(jù)所消耗的能量，式(9)是發(fā)送數(shù)據(jù)所消耗的能量，因本文針對的是小規(guī)模無線傳感器網(wǎng)絡(luò)，所以采用的是自由空間模型。
   
    因為不同規(guī)模的網(wǎng)絡(luò)，節(jié)點密度的不同，最優(yōu)簇首個數(shù)也不相同，采用參考文獻(xiàn)提出的最優(yōu)簇首個數(shù)公式(10)，采用的是自由空間模型。
   

2 分簇路由算法設(shè)計
2．1 算法設(shè)計
    本文主要針對一些特定的環(huán)境下，對經(jīng)典的LEACH算法進(jìn)行改進(jìn)。目前關(guān)于無線傳感器網(wǎng)絡(luò)測距技術(shù)，普遍采用信號強度與信號差往返時間來測距兩種方法。前者在理論上較難實現(xiàn)，一般很難在現(xiàn)實中使用。而后者理論簡單，但由于硬件成本的限制，只能采用一般的時鐘晶振，這時就對節(jié)點之間的時間同步提出了較高的要求。而目前傳統(tǒng)的時間同步算法都會隨著跳數(shù)的增加，誤差越變越大，而在小規(guī)模測距定位系統(tǒng)中，節(jié)點之間無需傳輸大量的數(shù)據(jù)，因此簇首節(jié)點無需進(jìn)行大量的數(shù)據(jù)融合，因此本文設(shè)計的初衷是減少傳輸跳數(shù)、延長整個網(wǎng)絡(luò)生存時間。因此對傳統(tǒng)的LEACH算法作以下改進(jìn)。能量傳輸模型采用式(8)與式(9)，網(wǎng)絡(luò)中最優(yōu)簇首個數(shù)比例采用式(10)，規(guī)定閾值T(n)采用式(6)。
    條件1：如圖1所示，當(dāng)dBD>dAD或dAB>dAD，直接讓簇內(nèi)節(jié)點D把數(shù)據(jù)傳輸給基站，與簇內(nèi)節(jié)點D先把數(shù)據(jù)傳給簇首B，在轉(zhuǎn)發(fā)給基站A的能量要少。

  
    顯然可以看出當(dāng)dBD>dAD時，ETxDB>ETxDA，接收能量是相同的。這樣就很容易得到當(dāng)dBD>dAD時，直接讓簇內(nèi)節(jié)點把數(shù)據(jù)傳輸給基站，與簇內(nèi)節(jié)點先把數(shù)據(jù)傳給簇首，在轉(zhuǎn)發(fā)給基站的能量要少是成立的。同理當(dāng)dAB>dAD時也是成立的。
    條件2：如圖1所示，當(dāng)時，則直接讓簇內(nèi)節(jié)點D把數(shù)據(jù)傳輸給基站，與簇內(nèi)節(jié)點D先把數(shù)據(jù)傳給簇首B，在轉(zhuǎn)發(fā)給基站A的能量要少。

2．2 算法性能分析
    根據(jù)2．1小節(jié)所討論的條件下對LEACH算法進(jìn)行改進(jìn)，在其他參數(shù)都相同的條件下，改進(jìn)前與改進(jìn)后死亡節(jié)點個數(shù)隨選舉輪數(shù)增加而變化情況如圖2所示。從圖2中可以看出，改進(jìn)后的算法節(jié)點生存時間優(yōu)于改進(jìn)前的算法，尤其隨著選舉輪數(shù)增加，優(yōu)勢越來越明顯。改進(jìn)前第一個節(jié)點的死亡時間為1051輪，改進(jìn)后第一個節(jié)點死亡時間為1062輪，改進(jìn)前一半節(jié)點死亡時間為1273輪，改進(jìn)后為1301輪。從2．1小節(jié)也可以知道，部分簇內(nèi)節(jié)點可以直接與基站通信，從而減少了部分節(jié)點的傳輸跳數(shù)。