基于LEACH的無線傳感器網絡路由協議改進算法*

翁錦深，秦華標，張宗國

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

1 引言

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

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

2 LEACH-Ⅱ協議

2.1 LEACH-Ⅱ協議的簇頭選舉算法

LEACH簇頭的選舉過程[8]是：節點從0～1中隨機選擇一個值，若當前輪中這個值小于設定的閾值Ti（n），則該節點成為簇頭，閾值Ti（n）按式（1）計算：

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

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

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

2.2 LEACH-Ⅱ協議的簇形成階段算法

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

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

2.3 LEACH-Ⅱ協議的多跳路由實現

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

LEACH-Ⅱ協議多跳路由第一簇頭選舉流程如圖5所示，定義第一簇頭的多跳路由的優點是距離匯聚節點較遠的簇頭先把數據傳遞給第一簇頭，大大減少了能量的消耗。雖然這會大大增加第一簇頭的負擔，但從總體上看，它依舊有利于節省網絡的總能量。

當網絡處于多跳路由的工作方式時，一般簇頭不直接向匯聚節點發送數據，而是先發向第一簇頭，這里會出現一個問題：在某一輪中，某個普通簇頭與第一簇頭之間的距離要大于該普通簇頭與匯聚節點的距離，也就是說，會出現個別普通簇頭因為多跳路由，能耗不但沒有減小反而增大的現象。這個現象在某一輪的執行過程中可能出現，但這是小概率的事件。而在實際情況中，多跳路由考慮的是網絡的總體消耗能量的減小和均衡，從整個網絡長遠的運作上看，大多數普通簇頭節省的能量要大于個別簇頭多消耗的能量。

3 仿真結果和分析

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

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

在初始能量分別為0.5 J和1 J的情況下，兩種協議的網絡生存周期如圖6和圖7所示。

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

在初始能量分別為0.5 J和1 J的情況下，兩種協議的網絡總能量消耗如圖8和圖9所示。

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

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

3.2 基于不同匯聚節點位置的仿真

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

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

3.3 LEACH-Ⅱ協議與其他改進算法的比較

在LEACH協議的各種改進算法協議中，LEACH-C協議[9]是目前為數不多的公開源代碼的LEACH改進協議。LEACH-C協議以循環的方式選擇簇頭，將整個網絡的能量負載和通信業務平均分配到每個節點，改善了LEACH隨機選擇簇頭導致的簇頭分布不均和沒有考慮節點能量的缺點，從而可以更好地降低傳感器的能量消耗。

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

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

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

4 結束語

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

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:一種基于分簇的無線傳感器網絡路由控制算法.電子與信息學報,2011,33(8)

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

5 尚鳳軍,任東海.無線傳感器網絡中分布式多跳路由協議算法研究.傳感器技術學報,2012,25(4)

6 蔡志偉,江汀,李銀勇等.基于CPK和能量的安全路由算法.電信科學,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 孫利民,李建中,陳渝等.無線傳感器網絡.北京:清華大學出版社,2005