LEACH協議的改進與仿真分析*

湯 玉，汪學明

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

0 引言

無線傳感器網絡（WSN)由隨機布設在監測區域內大量廉價微型傳感器節點組成，是一個多跳的自組織網絡系統。與移動自組織網絡(AdHoc)相比，WSN具有節點數量大、能量受限、以數據為中心、拓撲結構動態變化等特點，使得一些為傳統固定網絡和AdHoc網絡設計的路由算法不適合無線傳感器網絡的特點和應用要求[1]。由于WSN節點采用微型電池供電，節點能量有限且能量不可補充，設計節能有效的路由機制能延長整個網絡的生存周期，因此合理的路由協議是無線傳感器網絡研究的重點問題[2]。

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

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

1 LEACH協議算法

LEACH協議采用分簇思想將網絡中的節點分成很多簇，每個簇具有一個簇頭，簇內的非簇頭節點采集到數據后直接發送給該簇的簇頭節點，簇頭節點融合簇內成員發送來的數據后，將數據直接發送給基站。簇的形成是周期性的，稱為輪。每輪循環都包括兩個階段，第一個階段完成簇的組成，第二個階段負責穩定的數據通信。一輪完了重復進入下一輪工作。

1.1 簇的組成

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

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

1.2 穩定數據通信

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

2 LEACH協議的改進

由于 LEACH協議的簇頭既要融合簇內節點發送來的數據又要將處理后的數據發送給基站，這兩大任務消耗能量都是最嚴重的部分，所以簇頭比普通節點消耗能量要大很多。針對上述缺點對LEACH進行改進，通過簇內節點成鏈，讓簇內節點由單跳通信轉變為簇內節點多跳的傳輸模式，讓簇內節點融合數據后再由一個簇內節點將數據發送給簇頭，這樣簇頭就減少了處理簇內節點數據的能耗，只負責將收集到的數據發送給基站即可。

2.1 簇的形成

簇頭的產生和簇內節點的確定都采用 LEACH協議的產生方式，這里不在介紹，不過簇頭不用對本簇內各成員分配相應的傳輸時隙。

2.2 簇內節點成鏈

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

圖 1 簇內鏈式結構

2.3 簇內數據傳輸

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

圖2 一個簇的數據傳輸

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

在改進的算法中，之所以通過簇內離簇頭最近的節點與簇頭進行數據通信，是考慮到最短路徑的因素。因為一般簇頭四周都會有簇內節點，如果形成的鏈收集到的數據直接由鏈首傳輸給簇頭的話，路徑可能達不到最優，從而對于整個簇來說消耗的總能量會加大。如圖 3，簇一就是采用由鏈首將信息融合后發送給簇頭。簇二是采用由離簇頭最近的節點融合數據后發送給簇頭。相比之下簇二路徑更短，所以整個簇消耗的能量也最低。

3 仿真分析

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

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

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

圖 3 兩種成鏈結構的比較

圖4 存活節點數目

4 結語

考慮到簇頭即要融合簇內數據又要轉發數據消耗過多能量以及簇內節點單跳發送數據消耗多余能量的缺點，利用簇內節點成鏈，通過簇內節點融合簇內采集到的數據為簇頭節點分擔任務，節約簇頭節點能量消耗，使網絡中的節點能耗均衡，以此達到提高每輪簇穩定數據通信時間，進而提高網絡壽命。使用NS2對改進后的LEACH協議進行仿真，分析結果表明網絡壽命比LEACH協議延長。

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

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

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

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

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

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

[7] 王薇.無線傳感器網絡低功耗分級路由協議研究[D].浙江:浙江大學,2006.

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

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

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