一種基于LEACH的能量高效分簇路由協(xié)議

段圓圓，陳桂芬

（長(zhǎng)春理工大學(xué) 電子信息工程學(xué)院，長(zhǎng)春 130022）

隨著微電子技術(shù)，無(wú)線通信與傳感技術(shù)的發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)引起了人們的的廣泛關(guān)注［1］。無(wú)線傳感器網(wǎng)絡(luò)是由大量的微型傳感器節(jié)點(diǎn)組成［2］，然而這些傳感器節(jié)點(diǎn)能量和生存周期均有限，節(jié)點(diǎn)的數(shù)據(jù)處理能力和通信范圍同樣有局限性［3］。無(wú)線傳感器網(wǎng)絡(luò)一般部署于惡劣的環(huán)境之中，節(jié)點(diǎn)一旦失效網(wǎng)絡(luò)的應(yīng)用便受到限制［4］。因此如何減少節(jié)點(diǎn)的能量消耗，延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生存周期，一直是研究的熱點(diǎn)問題［5］。無(wú)線傳感器網(wǎng)絡(luò)的路由協(xié)議作為無(wú)線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一，可以在傳感器節(jié)點(diǎn)和基站之間建立高效的傳輸路徑，提高整個(gè)網(wǎng)絡(luò)的傳輸效率，有效地延長(zhǎng)網(wǎng)絡(luò)的生存周期。

在現(xiàn)有的路由協(xié)議中，LEACH（Low Energy Adaptive Clustering Hierarchy）協(xié)議作為第一個(gè)分層路由協(xié)議［6］，它的應(yīng)用優(yōu)化了平面路由協(xié)議在建立路由時(shí)能量開銷較大的缺點(diǎn)。其在易于管理和良好的擴(kuò)展性以及在平衡能耗方面的優(yōu)勢(shì)，使得分簇路由協(xié)議成為關(guān)注的焦點(diǎn)。PEGASIS由LEACH發(fā)展而來，在平衡節(jié)點(diǎn)能耗方面具有相當(dāng)優(yōu)勢(shì)，所以國(guó)內(nèi)外學(xué)者提出了依據(jù)PEGASIS（Power Efficient Gathering in Sensor Information System）來改進(jìn)LEACH的方法。如文獻(xiàn)［7］借鑒PEGASIS成鏈方法，只將簇首節(jié)點(diǎn)成鏈，雖然減少能耗和時(shí)延，但是簇內(nèi)簇首輪換由基站負(fù)責(zé)，當(dāng)簇首剩余能量不是簇內(nèi)節(jié)點(diǎn)剩余能量的最大值時(shí)進(jìn)行簇首輪換，頻繁的簇首選取會(huì)帶來不必要的能量開銷。文獻(xiàn)［8］中，除簇首節(jié)點(diǎn)成鏈之外，在簇內(nèi)節(jié)點(diǎn)至簇首也采取形成節(jié)點(diǎn)鏈的方式傳輸數(shù)據(jù)。如果在成鏈過程中有節(jié)點(diǎn)失效，那么頻繁地重新成鏈同樣會(huì)帶來巨大能耗。

本文基于LEACH協(xié)議提出了一種改進(jìn)的協(xié)議—EEPBL，將PEGASIS協(xié)議的節(jié)點(diǎn)成鏈思想應(yīng)用于LEACH協(xié)議的分簇結(jié)構(gòu)之中，只將LEACH協(xié)議中的簇頭節(jié)點(diǎn)成鏈。這樣既可以解決PEGASIS時(shí)延問題，同時(shí)也改進(jìn)LEACH的單跳傳輸方式，平衡節(jié)點(diǎn)之間的能耗。同時(shí)利用動(dòng)態(tài)能量閾值來減少簇內(nèi)簇首輪換過程中的能耗。

1 無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議相關(guān)研究

路由協(xié)議對(duì)于提高無(wú)線傳感器網(wǎng)絡(luò)的數(shù)據(jù)傳輸效率以及延長(zhǎng)網(wǎng)絡(luò)生命周期有著至關(guān)重要的作用，目前已是國(guó)內(nèi)外研究的熱點(diǎn)之一。分簇路由協(xié)議作為無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議中的一種，它的應(yīng)用優(yōu)化了平面路由協(xié)議在建立路由時(shí)能量開銷較大的缺點(diǎn)。其在易于管理和良好的擴(kuò)展性以及在平衡能耗方面的優(yōu)勢(shì)，使得分簇路由協(xié)議成為關(guān)注的焦點(diǎn)。

1.1 LEACH協(xié)議

LEACH協(xié)議由麻省理工學(xué)院Wendi Rabiner Heinzelman等三人提出［9］。主要運(yùn)作過程是將網(wǎng)絡(luò)中的節(jié)點(diǎn)分成多個(gè)簇，通過節(jié)點(diǎn)產(chǎn)生的隨機(jī)數(shù)與某個(gè)閾值進(jìn)行比較，隨機(jī)數(shù)小于閾值的節(jié)點(diǎn)擔(dān)任簇首節(jié)點(diǎn)。簇內(nèi)成員節(jié)點(diǎn)依次把數(shù)據(jù)發(fā)送給簇首，簇首將接收到的數(shù)據(jù)和自身感知的數(shù)據(jù)融合后，發(fā)送給匯聚節(jié)點(diǎn)，由于簇首承擔(dān)任務(wù)較重，能量消耗較大，為了平衡節(jié)點(diǎn)間的能量消耗，簇內(nèi)節(jié)點(diǎn)會(huì)輪換著成為簇首。LEACH協(xié)議是周期性的路由協(xié)議，在實(shí)際運(yùn)行過程按照一定周期性，每一個(gè)周期稱為一輪，每一輪又由簇首形成階段和穩(wěn)定傳輸階段組成。LEACH協(xié)議的拓?fù)浣Y(jié)構(gòu)如圖1所示：

圖1 LEACH協(xié)議的拓?fù)浣Y(jié)構(gòu)

在簇首形成階段，節(jié)點(diǎn)是否能成為簇首的條件主要取決于簇首數(shù)占整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的百分比p和上次成為簇首的輪數(shù)。這時(shí)節(jié)點(diǎn)n將產(chǎn)生一個(gè)隨機(jī)數(shù)，位于0-1之間。如果這個(gè)隨機(jī)數(shù)小于閾值，則該節(jié)點(diǎn)在這輪成為簇首，閾值公式如下：

其中，p=k/n；n表示傳感器網(wǎng)絡(luò)中任一節(jié)點(diǎn)，k表示傳感器網(wǎng)絡(luò)中的簇首數(shù)量，p簇頭占總結(jié)點(diǎn)的百分比，r表示為當(dāng)前輪數(shù)，G表示在最近1p輪中還沒有當(dāng)選簇首的集合。

LEACH協(xié)議雖然較一般平面路由協(xié)議在一定程度上延長(zhǎng)了網(wǎng)絡(luò)壽命，但是協(xié)議中沒有考慮到節(jié)點(diǎn)的剩余能量因素，無(wú)論節(jié)點(diǎn)的剩余能量多少，被選為簇首節(jié)點(diǎn)的概率相同。每一輪結(jié)束之后，就會(huì)重新選擇簇首節(jié)點(diǎn)，頻繁選取簇首會(huì)帶來額外的能耗。而且LEACH協(xié)議在進(jìn)行數(shù)據(jù)傳輸時(shí)，沒有考慮到節(jié)點(diǎn)與簇首節(jié)點(diǎn)和簇首與基站之間的距離因素。無(wú)論是簇內(nèi)成員節(jié)點(diǎn)傳送數(shù)據(jù)到簇首還是簇首節(jié)點(diǎn)傳送數(shù)據(jù)到基站均是采用單跳的通信方式，這會(huì)加速進(jìn)行長(zhǎng)距離數(shù)據(jù)傳輸?shù)墓?jié)點(diǎn)死亡，縮短網(wǎng)絡(luò)壽命。

1.2 PEGASIS協(xié)議

PEGASIS協(xié)議是基于LEACH協(xié)議的改進(jìn)版本。該協(xié)議的核心思想是利用貪婪算法從基站最遠(yuǎn)端形成一條由所有節(jié)點(diǎn)組成的單鏈。然后通過隨機(jī)方式選取一個(gè)節(jié)點(diǎn)成為鏈?zhǔn)坠?jié)點(diǎn)負(fù)責(zé)與基站通信。除端節(jié)點(diǎn)之外，每個(gè)節(jié)點(diǎn)將接收到的數(shù)據(jù)與自身的采集的數(shù)據(jù)進(jìn)行融合，從兩端沿著鏈傳送給鏈?zhǔn)坠?jié)點(diǎn)，最后由鏈?zhǔn)坠?jié)點(diǎn)將接收到的數(shù)據(jù)融合后傳送至基站。在協(xié)議運(yùn)行過程中，每當(dāng)有節(jié)點(diǎn)失效，剩余節(jié)點(diǎn)就會(huì)重新形成一條鏈，直至所有節(jié)點(diǎn)失效，通信結(jié)束［10］。

相比于LEACH中無(wú)論節(jié)點(diǎn)間距離遠(yuǎn)近，簇成員節(jié)點(diǎn)與簇首節(jié)點(diǎn)均采用單跳方式傳輸數(shù)據(jù)。在PEGASIS中節(jié)點(diǎn)只需與距自己最近的節(jié)點(diǎn)通信，平衡了節(jié)點(diǎn)之間的能耗。但是數(shù)據(jù)從鏈路的遠(yuǎn)端傳輸?shù)芥準(zhǔn)讜?huì)引起過多的延遲，并且每次鏈路中單個(gè)節(jié)點(diǎn)的死亡都要重新成鏈，如此拓?fù)浣Y(jié)構(gòu)的調(diào)整會(huì)帶來巨大的能量開銷，特別是對(duì)于高度利用的網(wǎng)絡(luò)，這種協(xié)議會(huì)加速網(wǎng)絡(luò)的死亡。

2 改進(jìn)的EEPBL協(xié)議

綜合LEACH和PEGASIS的優(yōu)缺點(diǎn)，從簇首選擇、簇間路由和簇內(nèi)簇首輪換三個(gè)方面改進(jìn)LEACH協(xié)議。提出了一個(gè)基于LEACH的能量高效路由協(xié)議EEPBL。EEPBL協(xié)議基本思想：首先將網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行分簇，然后采用集中控制的方式由基站選取簇首節(jié)點(diǎn)，借鑒PEGASIS的鏈?zhǔn)浇Y(jié)構(gòu)，依據(jù)貪婪算法將選取的簇首節(jié)點(diǎn)在距基站的最遠(yuǎn)端形成一條節(jié)點(diǎn)鏈，并且在所有簇首節(jié)點(diǎn)之中選擇一個(gè)剩余能量最多且離基站最近的簇首節(jié)點(diǎn)擔(dān)任鏈?zhǔn)坠?jié)點(diǎn)，鏈?zhǔn)坠?jié)點(diǎn)負(fù)責(zé)與基站通信。

2.1 EEPBL算法描述

2.1.1 簇首選擇

采用集中控制的方式通過基站選取簇首，由于基站具有能量充足計(jì)算能力強(qiáng)等優(yōu)點(diǎn)，將簇首的選擇工作通過基站來完成，可以達(dá)到節(jié)約能耗的目的。首先網(wǎng)絡(luò)中的所有傳感器節(jié)點(diǎn)將自己的能量和位置信息發(fā)送給基站。在初始階段網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的能量相同，所以基站隨機(jī)選取簇首節(jié)點(diǎn)即可。隨著網(wǎng)絡(luò)的不斷運(yùn)行，各節(jié)點(diǎn)的剩余能量會(huì)有差異，所以基站根據(jù)收到的信息，選擇剩余能量最多的節(jié)點(diǎn)作為簇首節(jié)點(diǎn)，當(dāng)簇首節(jié)點(diǎn)選定之后，向周圍鄰居節(jié)點(diǎn)廣播自己成為簇首的消息，等待鄰居節(jié)點(diǎn)加入簇。

2.1.2 能量模型

本文采用一階無(wú)線電模型的能量模型，無(wú)線信號(hào)強(qiáng)度所產(chǎn)生的能量損耗與傳輸?shù)木嚯x有關(guān)。該能量模型中規(guī)定了兩種信道模型—自由空間模型和多徑衰落模型。當(dāng)傳輸距離超過閾值d0時(shí)采用多徑衰落模型，否則采用自由空間模型。在此模型中節(jié)點(diǎn)經(jīng)過長(zhǎng)度為d的路徑，發(fā)送Lbit的數(shù)據(jù)所消耗的能量可由下式計(jì)算：

其中，Eelec表示發(fā)送單位比特?cái)?shù)據(jù)電路所需消耗的能量，εfs，εmp為功率放大器在不同信道模型的參數(shù)，其中；在此能量模型中，將Lbit的數(shù)據(jù)在長(zhǎng)度為d的路徑上傳輸，所消耗的能量為：

式中，ET(l,d)為發(fā)送時(shí)所消耗的能量，有兩部分組成，其一是發(fā)送電路消耗的能量ET-elec(l,d)，其二是發(fā)送放大器所消耗的能量ET-amp(l,d)。

將發(fā)送電路和發(fā)送放大器這兩部分能耗代入（3）中可得出

ER(l)是接受電路所消耗的能量，主要由接收電路產(chǎn)生

于是綜合（3）（4）（5）（6）可以得出

2.1.3 簇間路由

在LEACH協(xié)議中，無(wú)論是簇首節(jié)點(diǎn)傳輸數(shù)據(jù)到基站，還是簇內(nèi)成員節(jié)點(diǎn)傳輸數(shù)據(jù)至簇首，均采用單跳方式傳輸，當(dāng)簇首節(jié)點(diǎn)距離基站距離較遠(yuǎn)時(shí)或成員節(jié)點(diǎn)距離簇首較遠(yuǎn)時(shí)都會(huì)造成不必要的能量消耗。PEGASIS協(xié)議通過將網(wǎng)絡(luò)中的節(jié)點(diǎn)形成節(jié)點(diǎn)鏈［4］，以多跳方式將采集的數(shù)據(jù)傳送至基站［11］，但當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)，會(huì)導(dǎo)致較大時(shí)延。所以本文綜合兩者優(yōu)點(diǎn)，提出一種改進(jìn)的簇間路由算法，僅將簇首節(jié)點(diǎn)依據(jù)貪婪算法從基站的最遠(yuǎn)端成鏈，成鏈之后由基站選擇具有最多的剩余能量且距離基站最近的簇首節(jié)點(diǎn)作為整條鏈的鏈?zhǔn)坠?jié)點(diǎn)。簇內(nèi)成員節(jié)點(diǎn)將采集的數(shù)據(jù)傳送到簇首節(jié)點(diǎn)后，簇首節(jié)點(diǎn)將接收到的數(shù)據(jù)信息沿著這條鏈路傳輸至基站。EEPBL的簇間路由如圖2所示。

圖2 EEPBL的簇間路由

2.1.4 簇內(nèi)簇首輪換

由于LEACH協(xié)議每經(jīng)過一輪就要進(jìn)行全網(wǎng)的簇首選舉，然后當(dāng)選的簇首節(jié)點(diǎn)廣播當(dāng)選信息重新成簇，這樣對(duì)簇首節(jié)點(diǎn)的剩余能量并沒有準(zhǔn)確的估計(jì)。若剩余的能量還可以繼續(xù)支撐數(shù)據(jù)傳輸，簇首節(jié)點(diǎn)就沒有必要進(jìn)行更換。因此EEPBL中設(shè)置動(dòng)態(tài)能量閾值Eeff來避免頻繁地更換簇首造成的能量消耗。

動(dòng)態(tài)閾值Eeff的值會(huì)隨著簇內(nèi)節(jié)點(diǎn)剩余能量的變化而變化，簇首節(jié)點(diǎn)根據(jù)簇成員節(jié)點(diǎn)發(fā)送過來的能量信息計(jì)算簇內(nèi)剩余節(jié)點(diǎn)的平均值Eaverage：

其中，符號(hào)Ei為節(jié)點(diǎn)i的剩余能量，N為簇內(nèi)存活節(jié)點(diǎn)的總數(shù)，本文將能量閾值設(shè)置為簇內(nèi)節(jié)點(diǎn)剩余能量平均值的一半：

當(dāng)簇首能量小于此閾值時(shí)進(jìn)行簇內(nèi)的簇首輪換，選擇簇內(nèi)能量第二多的節(jié)點(diǎn)成為簇首，如此循環(huán)往復(fù)，直至簇內(nèi)節(jié)點(diǎn)剩余能量均小于閾值。

2.2 改進(jìn)算法流程圖

圖3 EEPBL協(xié)議流程圖

3 仿真結(jié)果及分析

3.1 參數(shù)設(shè)置

使用MATLAB仿真平臺(tái)對(duì)改進(jìn)的能量高效路由協(xié)議EEPBL和LEACH協(xié)議在性能方面進(jìn)行對(duì)比分析。仿真參數(shù)如表1所示：

表1 仿真參數(shù)

3.2 結(jié)果分析

如圖4所示，反映了死亡的節(jié)點(diǎn)總數(shù)和存活節(jié)點(diǎn)隨著時(shí)間的變化關(guān)系。仿真結(jié)果表明，LEACH協(xié)議約在1100輪的時(shí)候開始出現(xiàn)死亡節(jié)點(diǎn)，在1500輪的時(shí)候，LEACH協(xié)議約有一半節(jié)傳感器節(jié)點(diǎn)失效，在2250輪的時(shí)候全網(wǎng)所有的節(jié)點(diǎn)失效。

而本文提出的EEPBL算法大約在1400輪的時(shí)候開始出現(xiàn)死亡節(jié)點(diǎn)，在2100輪的時(shí)候約有一半的節(jié)點(diǎn)失效，到2750輪的時(shí)候全網(wǎng)的節(jié)點(diǎn)失效。EEPBL半數(shù)節(jié)點(diǎn)的失效時(shí)間是LEACH的1.4倍；EEPBL全部節(jié)點(diǎn)的失效時(shí)間是LEACH的1.31倍。這是由于EEPBL協(xié)議在簇間路由的選擇方面借鑒PEGASIS的鏈?zhǔn)浇Y(jié)構(gòu)，將簇首節(jié)點(diǎn)組成一條鏈，減少了LEACH協(xié)議中以單跳方式傳輸數(shù)據(jù)至基站的能耗。

圖4 死亡節(jié)點(diǎn)隨時(shí)間的變化

圖5對(duì)數(shù)據(jù)的傳輸量將LEACH和EEPBL進(jìn)行仿真對(duì)比，從仿真結(jié)果可以看出，EEPBL的數(shù)據(jù)傳輸總量大大超過LEACH的數(shù)據(jù)傳輸總量，當(dāng)全網(wǎng)的節(jié)點(diǎn)失效之時(shí)，LEACH協(xié)議的數(shù)據(jù)傳輸總量約為1.8×104bit；而EEPBL協(xié)議在全網(wǎng)失效之時(shí)數(shù)據(jù)傳輸總量約為7×104bit。改進(jìn)后的EEPBL協(xié)議，數(shù)據(jù)傳輸總量約為L(zhǎng)EACH的3.9倍。因此從總體來看EEPBL協(xié)議的性能優(yōu)于LEACH協(xié)議。

圖5 LEACH和EEPBL的數(shù)據(jù)傳輸對(duì)比

4 結(jié)論

EEPBL協(xié)議綜合了LEACH和PEGASIS協(xié)議的優(yōu)點(diǎn)，通過將簇首節(jié)點(diǎn)成鏈的方式，傳遞全網(wǎng)數(shù)據(jù)信息，既改善了PEGASIS中因成鏈過長(zhǎng)而降低數(shù)據(jù)傳輸速率，同時(shí)又解決了LEACH協(xié)議中節(jié)點(diǎn)能耗不均的問題。由仿真結(jié)果可知，EEPBL協(xié)議能夠有效減少節(jié)點(diǎn)能耗，延長(zhǎng)網(wǎng)絡(luò)壽命，提高數(shù)據(jù)傳輸效率。

［1］楊陽(yáng)，劉智，項(xiàng)力領(lǐng)，等.柵格型無(wú)線傳感器網(wǎng)絡(luò)的狀態(tài)空間建模［J］.長(zhǎng)春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，36（06）：129-132.

［2］邊晶，杜威.基于ZigBee的智能公交系統(tǒng)無(wú)線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)探究［J］.長(zhǎng)春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2016，39（04）：135-137.

［3］余恒，王剛亮.無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議研究進(jìn)展［J］.科技傳播，2011，15（02）：173-175.

［4］姚向華.無(wú)線傳感器網(wǎng)絡(luò)原理與應(yīng)用［M］.北京：高等教育出版社，2012：36-52.

［5］劉文進(jìn)，周天明，李新春.一種能量均衡的WSN多級(jí)分簇路由算法［J］.計(jì)算機(jī)工程與應(yīng)用，2016，52（16）：126-131.

［6］莊琴清.無(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議研究［D］.南京：南京郵電大學(xué)，2013.

［7］Abdul Razaque，Musbah Abdulgader，Chaitrali Joshi.P-LEACH：Energy efficientrouting protocolfor wirelesssensornetworks［C］.Systems，Applications and Technology Conference，2016，4（3）：77-81.

［8］趙凌，李盛.基于無(wú)線傳感器網(wǎng)絡(luò)PEGASIS算法的一種改進(jìn)方案［J］.四川兵工報(bào)，2013，34（04）：107-110.

［9］Wassim.Jerb，iAbderrahmen Guermazi，Hafedh Trabelsi.O-LEACH ofrouting protocolforwireless sensor networks［C］.Intelligent Systems and Control（ISCO），2016.，38（4）：393-396.

［10］劉興文.基于無(wú)線傳感器網(wǎng)絡(luò)的節(jié)能路由算法研究［D］.北京：北京交通大學(xué)，2015.

［11］Abdul.Razaque，Satwic，Mudigulam，KiranGavini.H-LEACH：Hybrid-low energy adaptive clustering hierarchy for wireless sensor networks［C］.Systems，ApplicationsandTechnologyConference，2016，4（3）：20-24.