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

湯 玉，汪學(xué)明

（貴州大學(xué) 計算機科學(xué)與信息學(xué)院，貴州 貴陽 550025）

0 引言

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

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

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

1 LEACH協(xié)議算法

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

1.1 簇的組成

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

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

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

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

2 LEACH協(xié)議的改進

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

2.1 簇的形成

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

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

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

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

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

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

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

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

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

3 仿真分析

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

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

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

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

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

4 結(jié)語

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

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

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

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

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

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

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

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

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

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

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