LEACH協(xié)議的改進(jìn)與仿真分析*

湯 玉，汪學(xué)明

（貴州大學(xué) 計(jì)算機(jī)科學(xué)與信息學(xué)院，貴州 貴陽(yáng) 550025）

0 引言

無(wú)線傳感器網(wǎng)絡(luò)（WSN)由隨機(jī)布設(shè)在監(jiān)測(cè)區(qū)域內(nèi)大量廉價(jià)微型傳感器節(jié)點(diǎn)組成，是一個(gè)多跳的自組織網(wǎng)絡(luò)系統(tǒng)。與移動(dòng)自組織網(wǎng)絡(luò)(AdHoc)相比，WSN具有節(jié)點(diǎn)數(shù)量大、能量受限、以數(shù)據(jù)為中心、拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化等特點(diǎn)，使得一些為傳統(tǒng)固定網(wǎng)絡(luò)和AdHoc網(wǎng)絡(luò)設(shè)計(jì)的路由算法不適合無(wú)線傳感器網(wǎng)絡(luò)的特點(diǎn)和應(yīng)用要求[1]。由于WSN節(jié)點(diǎn)采用微型電池供電，節(jié)點(diǎn)能量有限且能量不可補(bǔ)充，設(shè)計(jì)節(jié)能有效的路由機(jī)制能延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生存周期，因此合理的路由協(xié)議是無(wú)線傳感器網(wǎng)絡(luò)研究的重點(diǎn)問(wèn)題[2]。

當(dāng)今的路由結(jié)構(gòu)主要有平面式和分層式。分層路由在節(jié)點(diǎn)的組織管理和網(wǎng)絡(luò)擴(kuò)展性方面都比平面路由要好。層次路由協(xié)議中，無(wú)線傳感器網(wǎng)絡(luò)被劃分成多個(gè)簇，每個(gè)簇由一個(gè)簇頭節(jié)點(diǎn)及多個(gè)簇內(nèi)成員節(jié)點(diǎn)構(gòu)成，多個(gè)簇頭形成高一級(jí)網(wǎng)絡(luò)。在高一級(jí)網(wǎng)絡(luò)中，又可以再分簇，再次形成更高一級(jí)網(wǎng)絡(luò)，一直到最高級(jí)的匯聚節(jié)點(diǎn)為止[3]。簇的形成解決了平面路由的路由開(kāi)銷(xiāo)大、維護(hù)較大的路由表、占用較多的存儲(chǔ)空間的缺點(diǎn)。LEACH協(xié)議是分層協(xié)議中最早提出也是最具有代表性的協(xié)議，采用自適應(yīng)、隨機(jī)分布、自組織的成簇方式，數(shù)據(jù)通信采用局部控制方法，采用低能耗MAC協(xié)議和信息壓縮法、除冗余信息的處理技術(shù)實(shí)現(xiàn)節(jié)能的目的。

廖明華等提出一種改進(jìn)的簇頭選舉算法LEACH-ECHC，當(dāng)所有簇頭的剩余能量最小值小于某個(gè)閾值時(shí)，進(jìn)行全網(wǎng)選舉，當(dāng)簇頭能量小于該簇剩余能量的平均值時(shí)，進(jìn)行簇內(nèi)選舉，并對(duì)簇頭產(chǎn)生的閾值進(jìn)行優(yōu)化[4]。張震等提出利用PEGASIS算法使簇頭成鏈，并選擇剩余能量最多的簇頭傳送信息給基站。在選擇簇頭時(shí)，考慮節(jié)點(diǎn)的剩余能量，給節(jié)點(diǎn)設(shè)置一個(gè)能量閾值，小于該值則不能當(dāng)選為簇頭，因此提高了網(wǎng)絡(luò)的健壯性[5]。還有很多有關(guān)基于 LEACH協(xié)議的改進(jìn)算法，很好地提高了網(wǎng)絡(luò)某些方面的性能。

1 LEACH協(xié)議算法

LEACH協(xié)議采用分簇思想將網(wǎng)絡(luò)中的節(jié)點(diǎn)分成很多簇，每個(gè)簇具有一個(gè)簇頭，簇內(nèi)的非簇頭節(jié)點(diǎn)采集到數(shù)據(jù)后直接發(fā)送給該簇的簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)融合簇內(nèi)成員發(fā)送來(lái)的數(shù)據(jù)后，將數(shù)據(jù)直接發(fā)送給基站。簇的形成是周期性的，稱(chēng)為輪。每輪循環(huán)都包括兩個(gè)階段，第一個(gè)階段完成簇的組成，第二個(gè)階段負(fù)責(zé)穩(wěn)定的數(shù)據(jù)通信。一輪完了重復(fù)進(jìn)入下一輪工作。

1.1 簇的組成

LEACH算法每輪開(kāi)始時(shí)都要先確定簇頭。給每個(gè)節(jié)點(diǎn)設(shè)定閩值T(n)，同時(shí)節(jié)點(diǎn)產(chǎn)生介于0，1之間的隨機(jī)數(shù)，若產(chǎn)生的這個(gè)隨機(jī)數(shù)小于閩值T(n)，則該節(jié)點(diǎn)當(dāng)選為簇首[6]。閾值T(n)由式（1）給出。其中，P是簇頭在所有節(jié)點(diǎn)中所占的百分比，r是選舉輪數(shù)，r m od（1/ p ）代表這一輪循環(huán)中已經(jīng)當(dāng)過(guò)簇頭的節(jié)點(diǎn)個(gè)數(shù)，G是這一輪選舉中未當(dāng)選簇頭的節(jié)點(diǎn)集合。

簇頭選舉好，普通節(jié)點(diǎn)就開(kāi)始選擇加入哪個(gè)簇。簇頭向其他節(jié)點(diǎn)發(fā)送廣播消息，其他節(jié)點(diǎn)根據(jù)收到的消息信號(hào)強(qiáng)弱來(lái)決定加入哪個(gè)簇頭，并向該簇頭發(fā)送請(qǐng)求加入信息，正式成為其簇內(nèi)成員。簇頭對(duì)本簇內(nèi)各成員分配相應(yīng)的傳輸時(shí)隙形成傳輸列表（TDMA），然后將該 TDMA列表發(fā)給簇內(nèi)成員。這樣簇的建立就完成了。

1.2 穩(wěn)定數(shù)據(jù)通信

簇建立好后，就可以進(jìn)行數(shù)據(jù)通信了。簇內(nèi)成員的發(fā)射器在自己的TDMA時(shí)間槽會(huì)自動(dòng)打開(kāi)并將采集到的數(shù)據(jù)發(fā)送給簇頭節(jié)點(diǎn)，其他時(shí)隙處于睡眠狀態(tài)。簇頭節(jié)點(diǎn)一直處于活躍狀態(tài)以接收簇內(nèi)所有節(jié)點(diǎn)發(fā)送來(lái)的數(shù)據(jù)，簇頭接收完數(shù)據(jù)后將收到的數(shù)據(jù)進(jìn)行融合處理，去掉冗余信息后直接發(fā)送給 sink匯聚節(jié)點(diǎn)。這樣通過(guò)簇頭進(jìn)行數(shù)據(jù)處理之后再發(fā)送給匯聚節(jié)點(diǎn)的通信方式有效地減少了發(fā)送能量的消耗。匯聚節(jié)點(diǎn)能量可以補(bǔ)充，對(duì)整個(gè)網(wǎng)絡(luò)的壽命沒(méi)有一點(diǎn)影響。當(dāng)穩(wěn)定數(shù)據(jù)通信持續(xù)一段時(shí)間后，網(wǎng)絡(luò)重新開(kāi)始組簇，進(jìn)入新的一輪工作，如此循環(huán)進(jìn)行，直到網(wǎng)絡(luò)中的節(jié)點(diǎn)能量消耗到網(wǎng)絡(luò)無(wú)法再進(jìn)行為止。

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

由于 LEACH協(xié)議的簇頭既要融合簇內(nèi)節(jié)點(diǎn)發(fā)送來(lái)的數(shù)據(jù)又要將處理后的數(shù)據(jù)發(fā)送給基站，這兩大任務(wù)消耗能量都是最嚴(yán)重的部分，所以簇頭比普通節(jié)點(diǎn)消耗能量要大很多。針對(duì)上述缺點(diǎn)對(duì)LEACH進(jìn)行改進(jìn)，通過(guò)簇內(nèi)節(jié)點(diǎn)成鏈，讓簇內(nèi)節(jié)點(diǎn)由單跳通信轉(zhuǎn)變?yōu)榇貎?nèi)節(jié)點(diǎn)多跳的傳輸模式，讓簇內(nèi)節(jié)點(diǎn)融合數(shù)據(jù)后再由一個(gè)簇內(nèi)節(jié)點(diǎn)將數(shù)據(jù)發(fā)送給簇頭，這樣簇頭就減少了處理簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)的能耗，只負(fù)責(zé)將收集到的數(shù)據(jù)發(fā)送給基站即可。

2.1 簇的形成

簇頭的產(chǎn)生和簇內(nèi)節(jié)點(diǎn)的確定都采用 LEACH協(xié)議的產(chǎn)生方式，這里不在介紹，不過(guò)簇頭不用對(duì)本簇內(nèi)各成員分配相應(yīng)的傳輸時(shí)隙。

2.2 簇內(nèi)節(jié)點(diǎn)成鏈

簇形成后，簇內(nèi)的成員節(jié)點(diǎn)按照貪婪算法形成一個(gè)小型的節(jié)點(diǎn)鏈。為了保證簇內(nèi)每個(gè)節(jié)點(diǎn)都有自己的相鄰節(jié)點(diǎn)，節(jié)點(diǎn)發(fā)送能量遞減的測(cè)試信號(hào)，通過(guò)監(jiān)測(cè)應(yīng)答來(lái)確定離自己最近的鄰居節(jié)點(diǎn)[7]。鏈的形成從簇內(nèi)離簇頭最遠(yuǎn)的節(jié)點(diǎn)開(kāi)始構(gòu)建，每個(gè)簇內(nèi)節(jié)點(diǎn)都找到自己的相鄰節(jié)點(diǎn)，通信中只有一個(gè)節(jié)點(diǎn)當(dāng)選為領(lǐng)導(dǎo)節(jié)點(diǎn)與簇頭通信[8]。已經(jīng)成鏈的節(jié)點(diǎn)不能被再次訪問(wèn)，依此下去，簇內(nèi)所有節(jié)點(diǎn)將形成一條鏈。如圖1，每個(gè)節(jié)點(diǎn)只與它最近的鄰居節(jié)點(diǎn)通信。

圖 1 簇內(nèi)鏈?zhǔn)浇Y(jié)構(gòu)

2.3 簇內(nèi)數(shù)據(jù)傳輸

數(shù)據(jù)的傳輸是由簇內(nèi)離簇頭最近的那個(gè)節(jié)點(diǎn)將數(shù)據(jù)傳輸給簇頭的。首先由簇頭在本簇內(nèi)決定離自己最近的那個(gè)節(jié)點(diǎn)作為鏈的領(lǐng)導(dǎo)節(jié)點(diǎn)，然后領(lǐng)導(dǎo)節(jié)點(diǎn)通過(guò)Token控制數(shù)據(jù)從兩個(gè)鏈尾開(kāi)始傳輸，分別經(jīng)過(guò)各自的鄰居節(jié)點(diǎn)將數(shù)據(jù)融合處理和數(shù)據(jù)轉(zhuǎn)發(fā)，一步一步傳到離簇頭最近的那個(gè)節(jié)點(diǎn)，由該節(jié)點(diǎn)融合它兩邊鄰居節(jié)點(diǎn)發(fā)送來(lái)的數(shù)據(jù)和自身采集到的數(shù)據(jù)后發(fā)送給簇頭，簇頭再將接收到的數(shù)據(jù)和自身采集到的數(shù)據(jù)融合后發(fā)送給基站。這樣一次簇內(nèi)數(shù)據(jù)的采集和發(fā)送就完成了。如圖 2，選擇距離簇頭最近節(jié)點(diǎn)B為領(lǐng)導(dǎo)節(jié)點(diǎn)，傳輸數(shù)據(jù)時(shí)節(jié)點(diǎn)B產(chǎn)生Token控制信號(hào)，將Token沿著鏈傳給節(jié)點(diǎn)D，節(jié)點(diǎn)D將自己采集到的數(shù)據(jù)傳給節(jié)點(diǎn)C，節(jié)點(diǎn)C將D的數(shù)據(jù)和自己采集到的數(shù)據(jù)進(jìn)行融合后發(fā)送給節(jié)點(diǎn) B，然后B將Token傳給節(jié)點(diǎn)F，F(xiàn)和E的數(shù)據(jù)傳輸與C和D的數(shù)據(jù)傳輸方式一樣，最后B將C和E還有自己采集的數(shù)據(jù)進(jìn)行融合后發(fā)送給簇頭，簇頭將收到的數(shù)據(jù)和自己采集的數(shù)據(jù)處理后發(fā)送給基站。這樣一輪數(shù)據(jù)的傳輸就完成了。當(dāng)簇頭節(jié)點(diǎn)能量耗盡時(shí)，系統(tǒng)重新啟動(dòng)，進(jìn)入下一輪簇的選舉。

圖2 一個(gè)簇的數(shù)據(jù)傳輸

改進(jìn)后的算法簇內(nèi)節(jié)點(diǎn)之間采用最近距離的多跳方式發(fā)送數(shù)據(jù)，大大節(jié)約了簇內(nèi)節(jié)點(diǎn)單跳發(fā)送數(shù)據(jù)給簇頭消耗的能量。其次一個(gè)簇內(nèi)的節(jié)點(diǎn)不會(huì)過(guò)多，這樣形成短鏈，對(duì)數(shù)據(jù)的傳輸時(shí)延不會(huì)產(chǎn)生太大的影響，對(duì)于無(wú)線傳感器網(wǎng)絡(luò)來(lái)說(shuō)是可以的。再次簇內(nèi)節(jié)點(diǎn)將采集的數(shù)據(jù)進(jìn)行融合處理才發(fā)給簇頭，很大程度上節(jié)約了簇頭融合數(shù)據(jù)消耗的能量，增加了穩(wěn)定數(shù)據(jù)通信階段的時(shí)間，大大地延長(zhǎng)了網(wǎng)絡(luò)壽命。該算法與LEACH協(xié)議相比節(jié)能效果較好。

在改進(jìn)的算法中，之所以通過(guò)簇內(nèi)離簇頭最近的節(jié)點(diǎn)與簇頭進(jìn)行數(shù)據(jù)通信，是考慮到最短路徑的因素。因?yàn)橐话愦仡^四周都會(huì)有簇內(nèi)節(jié)點(diǎn)，如果形成的鏈?zhǔn)占降臄?shù)據(jù)直接由鏈?zhǔn)讉鬏斀o簇頭的話，路徑可能達(dá)不到最優(yōu)，從而對(duì)于整個(gè)簇來(lái)說(shuō)消耗的總能量會(huì)加大。如圖 3，簇一就是采用由鏈?zhǔn)讓⑿畔⑷诤虾蟀l(fā)送給簇頭。簇二是采用由離簇頭最近的節(jié)點(diǎn)融合數(shù)據(jù)后發(fā)送給簇頭。相比之下簇二路徑更短，所以整個(gè)簇消耗的能量也最低。

3 仿真分析

協(xié)議的改進(jìn)主要是為均衡網(wǎng)絡(luò)節(jié)點(diǎn)能耗和提高網(wǎng)絡(luò)壽命為目的。通過(guò)NS2工具對(duì)LEACH協(xié)議和改進(jìn)后的協(xié)議進(jìn)行仿真，分析比較協(xié)議的網(wǎng)絡(luò)壽命和存活節(jié)點(diǎn)的數(shù)目。網(wǎng)絡(luò)壽命規(guī)定為網(wǎng)絡(luò)中節(jié)點(diǎn)開(kāi)始部署到網(wǎng)絡(luò)中 80%節(jié)點(diǎn)死亡的時(shí)間，存活節(jié)點(diǎn)的數(shù)目規(guī)定為不同時(shí)刻存活節(jié)點(diǎn)的個(gè)數(shù)。通過(guò)這兩個(gè)性能指標(biāo)可以反映出網(wǎng)絡(luò)整體能量的消耗水平。

仿真模型采用100個(gè)節(jié)點(diǎn)隨機(jī)分布在50m×50m范圍內(nèi)，基站位置為（25 m，25 m），簇頭節(jié)點(diǎn)概率為0.05，每個(gè)節(jié)點(diǎn)的初始能量為2J，且不能移動(dòng)，信息長(zhǎng)度為500 Byte。

圖4為L(zhǎng)EACH協(xié)議和改進(jìn)后的協(xié)議在整個(gè)網(wǎng)絡(luò)各時(shí)刻中節(jié)點(diǎn)存活數(shù)量變化圖。由圖4可知，改進(jìn)后的協(xié)議壽命比 LEACH協(xié)議長(zhǎng)，且曲線的坡度明顯沒(méi)有 LEACH那么陡，這是因?yàn)榇貎?nèi)節(jié)點(diǎn)鏈?zhǔn)竭B接后，無(wú)論是簇頭還是簇內(nèi)節(jié)點(diǎn)的能量消耗都有所減少，所以每輪的數(shù)據(jù)穩(wěn)定通信時(shí)間也就相對(duì)變長(zhǎng)了，進(jìn)而提高了路由協(xié)議的使用時(shí)間。改進(jìn)后的協(xié)議雖然在性能方面比改進(jìn)前有明顯的提高，但由于該算法比較復(fù)雜，不太適合大規(guī)模的WSN網(wǎng)絡(luò)。

圖 3 兩種成鏈結(jié)構(gòu)的比較

圖4 存活節(jié)點(diǎn)數(shù)目

4 結(jié)語(yǔ)

考慮到簇頭即要融合簇內(nèi)數(shù)據(jù)又要轉(zhuǎn)發(fā)數(shù)據(jù)消耗過(guò)多能量以及簇內(nèi)節(jié)點(diǎn)單跳發(fā)送數(shù)據(jù)消耗多余能量的缺點(diǎn)，利用簇內(nèi)節(jié)點(diǎn)成鏈，通過(guò)簇內(nèi)節(jié)點(diǎn)融合簇內(nèi)采集到的數(shù)據(jù)為簇頭節(jié)點(diǎn)分擔(dān)任務(wù)，節(jié)約簇頭節(jié)點(diǎn)能量消耗，使網(wǎng)絡(luò)中的節(jié)點(diǎn)能耗均衡，以此達(dá)到提高每輪簇穩(wěn)定數(shù)據(jù)通信時(shí)間，進(jìn)而提高網(wǎng)絡(luò)壽命。使用NS2對(duì)改進(jìn)后的LEACH協(xié)議進(jìn)行仿真，分析結(jié)果表明網(wǎng)絡(luò)壽命比LEACH協(xié)議延長(zhǎng)。

[1] 馬祖長(zhǎng),孫怡寧,梅濤.無(wú)線傳感器網(wǎng)絡(luò)綜述[J].通信學(xué)報(bào),2004,25(04):114-127.

[2] 胡鋼,朱佳奇,陳世志.無(wú)線傳感器網(wǎng)絡(luò)簇間節(jié)能路由算法[J].通信技術(shù),2009,42(11):135-137.

[3] 王殊，閻毓杰，胡富平,等.無(wú)線傳感器網(wǎng)絡(luò)的理論及應(yīng)用[M].北京:北京航空航天大學(xué)出版社,2007:1-78.

[4] 廖明華,張華,王東.基于 LEACH協(xié)議的簇頭選舉改進(jìn)算法[J].計(jì)算機(jī)工程,2011,37(07):112-114.

[5] 張震,閆連山,潘煒,等.基于LEACH和PEGASIS的簇頭成鏈可靠路由協(xié)議研究[J].傳感技術(shù)學(xué)報(bào),2010, 23(08):1173-1178.

[6] 張瑞華,張紅.無(wú)線傳感器網(wǎng)絡(luò)分簇算法分析與性能比較[J].通信技術(shù),2010,43(01):156-161.

[7] 王薇.無(wú)線傳感器網(wǎng)絡(luò)低功耗分級(jí)路由協(xié)議研究[D].浙江:浙江大學(xué),2006.

[8] 孫獻(xiàn)璞,張艷玲,張建東.無(wú)線動(dòng)態(tài)令牌協(xié)議及性能分析[J].電子學(xué)報(bào)，2009,36(10):2039-2043.

[9] 李林,穆靈. 基于組合公鑰的 WSN認(rèn)證協(xié)議的設(shè)計(jì)及分析[J].信息安全與通信保密,2009(07):93-95.

[10] 林先超,楊壽保,單來(lái)祥,等.一種傳感器網(wǎng)絡(luò)分布式認(rèn)證方案[J].信息安全與通信保密,2006(07):114-116.