基于LEACH的無線傳感器網(wǎng)絡(luò)路由協(xié)議改進(jìn)算法*

翁錦深，秦華標(biāo)，張宗國

（華南理工大學(xué)電子與信息學(xué)院 廣州510640）

1 引言

無線傳感器網(wǎng)絡(luò)由許多具有低功率無線收發(fā)裝置的傳感器節(jié)點(diǎn)組成，能夠有效地在不同環(huán)境中監(jiān)測收集周邊環(huán)境信息，并傳送到遠(yuǎn)處的基站進(jìn)行處理。無線傳感器網(wǎng)絡(luò)可以被廣泛地應(yīng)用于軍事、商業(yè)、醫(yī)療救護(hù)和環(huán)境監(jiān)測等多方面。由于傳感器節(jié)點(diǎn)的電池能量有限，因此節(jié)點(diǎn)的通信應(yīng)該有效地利用能量，以延長網(wǎng)絡(luò)的生命周期[1]。LEACH協(xié)議是一種典型的、可以有效延長網(wǎng)絡(luò)生命周期的節(jié)能路由協(xié)議，然而其存在很多不完善的地方，主要體現(xiàn)在3方面：一是簇頭的產(chǎn)生具有極大的隨機(jī)性，可能會出現(xiàn)部分簇頭相距過近或部分區(qū)域的節(jié)點(diǎn)離簇頭太遠(yuǎn)的情況，大大增加了節(jié)點(diǎn)的傳輸能耗；二是每個簇中節(jié)點(diǎn)數(shù)目分布不均勻，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分布不均勻使節(jié)點(diǎn)能耗不一，大大減少了網(wǎng)絡(luò)生存時間；三是LEACH協(xié)議采用單跳的形式，所有節(jié)點(diǎn)都可以與匯聚節(jié)點(diǎn)直接通信，距離匯聚節(jié)點(diǎn)遠(yuǎn)的簇頭能量消耗巨大，并且也不適合在規(guī)模較大的無線傳感器網(wǎng)絡(luò)中應(yīng)用。針對LEACH協(xié)議的缺點(diǎn)，很多參考文獻(xiàn)提出了相應(yīng)的改進(jìn)算法。參考文獻(xiàn)[2]通過建立多層次的聚類方法減少節(jié)點(diǎn)之間的通信距離，從而降低系統(tǒng)的能耗。參考文獻(xiàn)[3]提出了一種基于分簇的自適應(yīng)混合型路由控制算法，該算法針對大規(guī)模時間驅(qū)動型網(wǎng)絡(luò)場景應(yīng)用，采用網(wǎng)內(nèi)節(jié)點(diǎn)啟發(fā)機(jī)制，解決了LEACH算法面對大規(guī)模網(wǎng)絡(luò)缺乏自適應(yīng)性、通信效率難以得到保障等問題。參考文獻(xiàn)[4]引入簇成員數(shù)門限和合并極小簇的方法，避免極大簇和極小簇同時存在的問題。參考文獻(xiàn)[5]在簇頭數(shù)據(jù)傳輸方面將網(wǎng)絡(luò)中均勻分布的簇頭構(gòu)造成一棵路由樹，通過多跳傳輸?shù)姆绞剑瑴p少直接與基站通信的簇頭節(jié)點(diǎn)數(shù)量。參考文獻(xiàn)[6]主要針對無線傳感器網(wǎng)絡(luò)面臨的眾多安全問題，從組合公鑰和節(jié)點(diǎn)能量入手，對LEACH協(xié)議進(jìn)行了改進(jìn)。

綜上所述，對LEACH協(xié)議的改進(jìn)可以歸結(jié)為對簇頭選擇算法的改進(jìn)、簇形成階段算法的改進(jìn)、多跳路由方法的實(shí)現(xiàn)、數(shù)據(jù)融合算法[7]的改進(jìn)等。而眾多參考文獻(xiàn)也主要針對LEACH協(xié)議缺點(diǎn)的一兩點(diǎn)進(jìn)行相應(yīng)改進(jìn)，本文綜合考慮了LEACH協(xié)議的幾大缺點(diǎn)，從簇頭選舉算法、簇形成階段、多跳路由的實(shí)現(xiàn)等方面入手，提出了改進(jìn)協(xié)議算法LEACH-Ⅱ協(xié)議。

2 LEACH-Ⅱ協(xié)議

2.1 LEACH-Ⅱ協(xié)議的簇頭選舉算法

LEACH簇頭的選舉過程[8]是：節(jié)點(diǎn)從0～1中隨機(jī)選擇一個值，若當(dāng)前輪中這個值小于設(shè)定的閾值Ti（n），則該節(jié)點(diǎn)成為簇頭，閾值Ti（n）按式（1）計算：

其中，p為期望的簇頭節(jié)點(diǎn)在所有傳感器節(jié)點(diǎn)中的百分比，r是當(dāng)前的輪數(shù)。LEACH簇頭選擇算法雖然實(shí)現(xiàn)了簇頭隨機(jī)產(chǎn)生，各節(jié)點(diǎn)當(dāng)簇頭的機(jī)會相對均等，但是實(shí)際上隨機(jī)產(chǎn)生簇頭很容易導(dǎo)致多輪運(yùn)行后各節(jié)點(diǎn)剩余能量相差較大而使大部分節(jié)點(diǎn)死亡。所以，LEACH-Ⅱ協(xié)議在選擇簇頭時，不僅考慮了各節(jié)點(diǎn)成為簇頭的概率，還綜合考慮了節(jié)點(diǎn)剩余能量、平均能量和最大能量的大小，保證簇頭盡量在能量高的節(jié)點(diǎn)中產(chǎn)生，避免能量低的節(jié)點(diǎn)成為簇頭。

LEACH-Ⅱ協(xié)議的簇頭選舉算法中，閾值Ti(n)的定義為：

其中，Ecurrent為節(jié)點(diǎn)當(dāng)前的能量，Emax為當(dāng)前各節(jié)點(diǎn)中剩余能量的最大值，Eaverage為當(dāng)前各節(jié)點(diǎn)能量的平均值。LEACH-Ⅱ協(xié)議的簇頭選舉策略同LEACH協(xié)議相比，發(fā)生了很大的變化：節(jié)點(diǎn)能否成為簇頭，不僅與隨機(jī)概率有關(guān)，還與節(jié)點(diǎn)本身能量、平均節(jié)點(diǎn)能量有關(guān)。如果一個節(jié)點(diǎn)能量較小，小于各節(jié)點(diǎn)的平均能量，它成為簇頭的幾率就會大大減少；反之，如果一個節(jié)點(diǎn)的能量較大，遠(yuǎn)遠(yuǎn)大于各節(jié)點(diǎn)平均能量，它成為節(jié)點(diǎn)的幾率就比能量低于平均能量的節(jié)點(diǎn)大得多。更重要的是，它也保留了LEACH協(xié)議隨機(jī)產(chǎn)生簇頭的機(jī)制。LEACH-Ⅱ協(xié)議的簇頭選舉策略大大改善了LEACH協(xié)議中因距離不等而導(dǎo)致大批節(jié)點(diǎn)不均勻死亡的問題。其流程如圖1所示。

2.2 LEACH-Ⅱ協(xié)議的簇形成階段算法

某輪簇頭選舉出來后，就到了簇的形成階段，即節(jié)點(diǎn)選擇簇頭并成為該簇的簇成員。在LEACH-Ⅱ協(xié)議的簇形成階段中，簇頭會利用CSMA(carrier sense multiple access，載波偵聽多路訪問)的MAC機(jī)制廣播一個通告消息ADV，并定義一個系統(tǒng)參數(shù)NM，初始化為0。ADV本身是一個很小的消息，僅包含了節(jié)點(diǎn)ID和表明信息類型的頭部。非簇頭節(jié)點(diǎn)接收到通告消息后，首先判斷各簇頭消息信號的強(qiáng)弱，然后選擇發(fā)送通告信號最強(qiáng)的那個簇頭，并加入該簇成為其簇成員。該節(jié)點(diǎn)同時會給簇頭發(fā)送一個請求消息joint-REQ，這個消息和通告消息ADV類似，也僅由節(jié)點(diǎn)ID和簇頭ID構(gòu)成。簇頭每接到一個joint-REQ消息，NM就自動加1。當(dāng)NM增加到為當(dāng)前存活節(jié)點(diǎn)數(shù)，k為簇數(shù)）時，簇頭將禁止別的節(jié)點(diǎn)再加入本簇。如果此時簇頭還有別的節(jié)點(diǎn)發(fā)來的joint-REQ消息，簇頭將給該節(jié)點(diǎn)發(fā)送一個拒絕消息。這個信息類似于ADV消息，所不同的是，原來表示信息類型的部分被填充了表示拒絕的內(nèi)容。收到拒絕消息的節(jié)點(diǎn)將檢查所收到的所有通告消息ADV，根據(jù)信號強(qiáng)弱，挑選發(fā)出第二強(qiáng)信號的簇頭作為自己將要加入的簇，然后再重復(fù)之前的過程，給該簇頭發(fā)送一個請求消息joint-REQ。一個簇建立起來后，簇頭根據(jù)簇內(nèi)節(jié)點(diǎn)情況建立一個TDMA(time division multiple access,時分多址)調(diào)度，并把這個調(diào)度通知給簇內(nèi)各節(jié)點(diǎn)。為了減少能量消耗，簇內(nèi)非簇頭節(jié)點(diǎn)將一直關(guān)閉無線電模塊，直到處于各自的傳輸階段才重新開啟。TDMA調(diào)度保證了各非簇頭節(jié)點(diǎn)傳輸數(shù)據(jù)不會發(fā)生沖突。

LEACH-Ⅱ協(xié)議的簇形成階段還對形成的時間做了規(guī)定，具體操作時在簇頭函數(shù)里添加了一個時間定時器。一旦超過了這個時間，簇頭將不再接受節(jié)點(diǎn)入簇的申請。簇形成階段中簇頭和非簇頭對應(yīng)的工作流程分別如圖2和圖3所示。

2.3 LEACH-Ⅱ協(xié)議的多跳路由實(shí)現(xiàn)

LEACH-Ⅱ協(xié)議的多跳路由具體實(shí)現(xiàn)為：節(jié)點(diǎn)成為簇頭后，會向周圍節(jié)點(diǎn)廣播通告消息，當(dāng)匯聚節(jié)點(diǎn)獲取到各個簇頭的廣播消息后，便根據(jù)這些簇頭通告消息的強(qiáng)弱，把信號最強(qiáng)的那個簇頭定義為第一簇頭(the first cluster)。其他簇頭將不再向匯聚節(jié)點(diǎn)傳遞數(shù)據(jù)，而是先把數(shù)據(jù)傳遞給第一簇頭，由第一簇頭對其他簇頭傳遞過來的數(shù)據(jù)做進(jìn)一步的融合處理之后，再傳遞給匯聚節(jié)點(diǎn)，從而實(shí)現(xiàn)簇頭與匯聚節(jié)點(diǎn)之間的多跳路由，LEACH-Ⅱ協(xié)議的多跳路由示意如圖4所示。

LEACH-Ⅱ協(xié)議多跳路由第一簇頭選舉流程如圖5所示，定義第一簇頭的多跳路由的優(yōu)點(diǎn)是距離匯聚節(jié)點(diǎn)較遠(yuǎn)的簇頭先把數(shù)據(jù)傳遞給第一簇頭，大大減少了能量的消耗。雖然這會大大增加第一簇頭的負(fù)擔(dān)，但從總體上看，它依舊有利于節(jié)省網(wǎng)絡(luò)的總能量。

當(dāng)網(wǎng)絡(luò)處于多跳路由的工作方式時，一般簇頭不直接向匯聚節(jié)點(diǎn)發(fā)送數(shù)據(jù)，而是先發(fā)向第一簇頭，這里會出現(xiàn)一個問題：在某一輪中，某個普通簇頭與第一簇頭之間的距離要大于該普通簇頭與匯聚節(jié)點(diǎn)的距離，也就是說，會出現(xiàn)個別普通簇頭因?yàn)槎嗵酚?，能耗不但沒有減小反而增大的現(xiàn)象。這個現(xiàn)象在某一輪的執(zhí)行過程中可能出現(xiàn)，但這是小概率的事件。而在實(shí)際情況中，多跳路由考慮的是網(wǎng)絡(luò)的總體消耗能量的減小和均衡，從整個網(wǎng)絡(luò)長遠(yuǎn)的運(yùn)作上看，大多數(shù)普通簇頭節(jié)省的能量要大于個別簇頭多消耗的能量。

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

為了檢驗(yàn)LEACH-Ⅱ協(xié)議的性能，首先在NS2平臺上對LEACH和LEACH-Ⅱ協(xié)議進(jìn)行仿真。仿真分為兩部分：一是基于不同初始能量0.5 J、1 J的仿真；二是基于不同匯聚節(jié)點(diǎn)位置((50,-50)、(50,-100)、(50,-150))的仿真。接著針對本文改進(jìn)協(xié)議LEACH-Ⅱ和已有的LEACH改進(jìn)協(xié)議LEACH-C進(jìn)行對比仿真。

3.1 基于不同初始能量的仿真

在初始能量分別為0.5 J和1 J的情況下，兩種協(xié)議的網(wǎng)絡(luò)生存周期如圖6和圖7所示。

其中橫坐標(biāo)代表輪數(shù)，縱坐標(biāo)代表存活節(jié)點(diǎn)的數(shù)目。如圖6所示，不管節(jié)點(diǎn)初始能量為多大，LEACH-Ⅱ協(xié)議運(yùn)行的輪數(shù)均要大于LEACH協(xié)議。也就是說，LEACH-Ⅱ協(xié)議延長了網(wǎng)絡(luò)的生命周期。初始能量為0.5 J時，LEACH-Ⅱ協(xié)議的網(wǎng)絡(luò)周期由LEAC協(xié)議H的不足800輪延長到了近900輪，網(wǎng)絡(luò)壽命延長了12.5%。從圖7可以看出，初始能量為1 J時，LEACH協(xié)議運(yùn)行了1 378輪，而LEACH-Ⅱ協(xié)議整整多出了200輪，網(wǎng)絡(luò)壽命延長了14.5%。事實(shí)上，初始能量越高，LEACH-Ⅱ協(xié)議網(wǎng)絡(luò)壽命延長的效果就越明顯。這說明，LEACH-Ⅱ協(xié)議的各簇內(nèi)成員經(jīng)過數(shù)量均衡和簇頭選舉優(yōu)化后，節(jié)點(diǎn)在傳輸數(shù)據(jù)時消耗的能量變得均衡了，網(wǎng)絡(luò)壽命得到延長。

在初始能量分別為0.5 J和1 J的情況下，兩種協(xié)議的網(wǎng)絡(luò)總能量消耗如圖8和圖9所示。

初始能量為0.5 J時，LEACH-Ⅱ協(xié)議中節(jié)點(diǎn)總能量消耗的速度明顯比LEACH協(xié)議慢。在前500輪中，由于節(jié)點(diǎn)數(shù)量多，傳輸數(shù)據(jù)任務(wù)重，總能量急劇減小，但是LEACH-Ⅱ協(xié)議減小的速度始終比LEACH協(xié)議慢。初始能量為1 J時和0.5 J時的趨勢一致，即LEACH-Ⅱ協(xié)議的能量消耗速度要小于LEACH協(xié)議。LEACH-Ⅱ協(xié)議能量消耗得慢，從而延長了網(wǎng)絡(luò)的生存周期，可見總能量消耗圖同節(jié)點(diǎn)生成圖互相對應(yīng)。

初始能量不同時，通過對LEACH-Ⅱ協(xié)議和LEACH協(xié)議的仿真結(jié)果分析比較可知，LEACH-Ⅱ協(xié)議無論是在網(wǎng)絡(luò)生存周期還是在能量消耗方面都有了較大的改善。

3.2 基于不同匯聚節(jié)點(diǎn)位置的仿真

上面通過不同初始能量的仿真得出了LEACH-Ⅱ協(xié)議優(yōu)于LEACH協(xié)議的結(jié)論。接下來是對匯聚節(jié)點(diǎn)分別位于(50,-50)、(50,-100)和(50,-150)這3種情況下的網(wǎng)絡(luò)生存周期進(jìn)行仿真。為了方便分析，本次仿真只關(guān)注節(jié)點(diǎn)死亡10%、25%、50%、75%和100%這5個點(diǎn)。3種情況下的節(jié)點(diǎn)存活仿真結(jié)果分別如圖10～圖12所示。

其中，橫坐標(biāo)代表能量耗盡的節(jié)點(diǎn)數(shù)量，縱坐標(biāo)代表輪數(shù)。如圖10、圖11和圖12所示，即使匯聚節(jié)點(diǎn)在不同位置，LEACH-Ⅱ協(xié)議的生命周期也均大于LEACH協(xié)議的生命周期。匯聚節(jié)點(diǎn)在(50,-50)時，LEACH-Ⅱ協(xié)議中10%、25%、50%、75%和100%死亡節(jié)點(diǎn)的運(yùn)行輪數(shù)均大于LEACH協(xié)議。匯聚節(jié)點(diǎn)在(50,-100)和(50,-150)時，死亡相同節(jié)點(diǎn)LEACH-Ⅱ協(xié)議運(yùn)行的輪數(shù)均比LEACH協(xié)議多；且可以看出匯聚節(jié)點(diǎn)離普通節(jié)點(diǎn)越遠(yuǎn)，LEACH-Ⅱ協(xié)議的優(yōu)越性越明顯。

3.3 LEACH-Ⅱ協(xié)議與其他改進(jìn)算法的比較

在LEACH協(xié)議的各種改進(jìn)算法協(xié)議中，LEACH-C協(xié)議[9]是目前為數(shù)不多的公開源代碼的LEACH改進(jìn)協(xié)議。LEACH-C協(xié)議以循環(huán)的方式選擇簇頭，將整個網(wǎng)絡(luò)的能量負(fù)載和通信業(yè)務(wù)平均分配到每個節(jié)點(diǎn)，改善了LEACH隨機(jī)選擇簇頭導(dǎo)致的簇頭分布不均和沒有考慮節(jié)點(diǎn)能量的缺點(diǎn)，從而可以更好地降低傳感器的能量消耗。

本文主要從生存周期和總能量消耗兩方面對LEACH-Ⅱ協(xié)議和LEACH-C協(xié)議進(jìn)行仿真對比。其中初始能量設(shè)為1 J，匯聚節(jié)點(diǎn)坐標(biāo)(50,-150)，仿真結(jié)果如圖13和圖14所示。

如圖13所示，50%節(jié)點(diǎn)死亡，LEACH-Ⅱ協(xié)議在第1 163輪出現(xiàn)該情況，LEACH-C協(xié)議在第1 098輪出現(xiàn)，LEACH-Ⅱ協(xié)議比LEACH-C協(xié)議提高5.91%。LEACH-Ⅱ協(xié)議在經(jīng)過1 534輪后節(jié)點(diǎn)全部死亡，LEACH-C協(xié)議最后節(jié)點(diǎn)死亡則出現(xiàn)在第1 501輪，LEACH-Ⅱ協(xié)議比LEACH-C協(xié)議提高2.19%。從圖14也可以看出，在能量消耗方面，LEACH-Ⅱ協(xié)議比LEACH-C協(xié)議略占優(yōu)勢。

因此，無論在網(wǎng)絡(luò)存活周期方面還是網(wǎng)絡(luò)耗能方面，LEACH-Ⅱ協(xié)議都要優(yōu)于LEACH-C協(xié)議，雖然優(yōu)勢并不是十分明顯。但從理論上講，LEACH-C協(xié)議采用退火算法使簇頭總能從能量大的節(jié)點(diǎn)中產(chǎn)生，雖然消除了簇頭選舉的隨機(jī)性并考慮了節(jié)點(diǎn)的能量，但在簇形成過程中極大極小簇問題以及單跳方式使得距離匯聚節(jié)點(diǎn)遠(yuǎn)的簇頭能量消耗巨大的現(xiàn)象依舊存在，而LEACH-Ⅱ協(xié)議綜合考慮了這些問題，它的優(yōu)勢在于簇頭選舉階段不受匯聚節(jié)點(diǎn)的控制，簇內(nèi)節(jié)點(diǎn)數(shù)量均衡和簡單多跳，因此在總能量消耗和生存周期方面都比LEACH-C協(xié)議都有所改善。

4 結(jié)束語

本文主要針對LEACH的不足，提出了一種高效聚類路由算法，該算法從簇頭選舉策略、簇形成階段和多跳路由的實(shí)現(xiàn)3個方面對LEACH協(xié)議進(jìn)行了改進(jìn)，仿真結(jié)果表明該算法降低了總能量消耗，延長了網(wǎng)絡(luò)的生存周期，同時算法簡單、實(shí)現(xiàn)容易。

1 Nikolidakis S,Vergados D.Energy-efficient routing protocols in wireless sensor networks:a survey.IEEE Communications Survey& Tutorials,2012(3)

2 Meenakshi S,Kalpana S.An energy efficient extended LEACH.International Conference on Communication Systems and Network Technologies,Rajkot,India,2012

3 張小波,程良倫.SAHRC:一種基于分簇的無線傳感器網(wǎng)絡(luò)路由控制算法.電子與信息學(xué)報,2011,33(8)

4 呂濤,朱清新,張路橋.一種基于LEACH協(xié)議的改進(jìn)算法.電子學(xué)報,2011,39(6)

5 尚鳳軍,任東海.無線傳感器網(wǎng)絡(luò)中分布式多跳路由協(xié)議算法研究.傳感器技術(shù)學(xué)報,2012,25(4)

6 蔡志偉,江汀,李銀勇等.基于CPK和能量的安全路由算法.電信科學(xué),2011(10)

7 Wang J,Yu H,Shang Z.Research on reliable link layer communication in wireless sensor networks.Proceedings of the International Conference on Communication,Circuits and Systems,HongKong,2005

8 Yektaparast A,Nabavi F H,Sarmast A.An improvement on LEACH protocol(Cell-LEACH).International Conference on 14th Advance Communication Technology,PyeongChang,Korea,2012

9 HeinzelmanW,ChandrakasanA,BalakrishnanH.Anapplication-specific protocol architecture for wireless microsensor networks.IEEE Transactions on Wireless Communication,2002,1(4):60～70

10 孫利民,李建中,陳渝等.無線傳感器網(wǎng)絡(luò).北京:清華大學(xué)出版社,2005