一種LEACH協議的多級分簇改進算法

羅 冰，黃玉清

(西南科技大學信息學院，四川 綿陽 621010)

1 概述

無線傳感器網絡(Wireless Sensor Network,WSN)是集信息采集、信息傳輸、信息處理于一體的智能信息系統，它綜合了傳感器技術、嵌入式技術、現代網絡及無線通信技術、分布式信息處理技術等，可用于環境檢測、醫療護理、軍事等眾多領域。無線傳感器網絡節點具有體積小、能量有限且電池不宜更換等特點。因此，采用高效的功率控制策略，減少不必要的能量消耗，延長網絡生存時間是無線傳感器網絡的一個重要研究課題[1]。

LEACH(Low Energy Adaptive Clustering Hierarchy)[2]協議是第一個提出數據聚合的層次路由協議，采用動態分簇，各個節點以循環的方式隨機擔任簇頭，由簇頭節點負責收集簇內其他節點的數據，進行數據融合，直接發送到sink節點，以此均衡節點的能量消耗。與之前的平面多跳路由協議以及靜態分簇算法相比，LEACH 協議可以將網絡生存壽命延長15%左右[2]。

本文提出一種LEACH 協議的多級分簇改進算法。采用多級聚簇的思想，并結合傳感器網絡的節能策略，對LEACH 協議進行改進。

2 LEACH 協議

LEACH 協議的核心思想是使用分布式算法，傳感器節點通過自主聚簇，并在簇內通過隨機選舉產生簇頭節點。簇頭節點收集簇內其他傳感器節點數據并進行數據融合，最終傳送到sink 節點。

在LEACH 的運行過程中，通過“輪”的概念表示每個簇的循環重構。每輪分為2 個階段：構建階段和穩定階段。(1)在構建階段，隨機選舉簇頭并進行聚簇。(2)在穩定階段，簇內節點向簇頭節點發送數據，簇頭節點進行數據融合并向sink 節點傳輸。

2.1 構建階段

各節點產生一個在[0,1]之間的隨機數，如果該數小于T(n)，則該節點當選為簇頭。T(n)的計算方法如下：

其中，n 為總節點數；p 為網絡中簇頭數與總節點數的百分比；r 為當前的選舉輪數；G 為最近1/p 輪不是簇頭的節點集合。當選為簇頭的節點向網絡廣播消息時，在其他節點接收到廣播消息后，依據廣播消息的信號強度，確定要加入的簇，使用載波監聽機制向各自的簇頭節點發送通知。

2.2 穩定階段

接收到通知消息的簇頭節點，為其簇內的普通節點創建時分多址(Time Division Multiple Access,TDMA)時隙表。普通節點在其各自的時隙內，將采集的數據傳輸到簇頭節點。在所有數據傳輸完畢后，簇頭節點進行數據融合，并將其直接傳輸到sink 節點，結束本輪循環，準備開始下一輪選舉。LEACH 是最簡單的層次路由協議，每輪隨機選取簇頭節點，避免了簇頭因能量消耗過多而死亡，可以有效降低無線傳感器網絡能量消耗，延長網絡生存壽命。但是仍然存在一些缺點：選舉產生的簇頭節點是不均勻分布的，會導致一部分簇頭節點集中分布在某一區域，而其他區域沒有簇頭節點[3]。

LEACH 協議要求任意2 個節點可以直接互相通信，要求節點具有較大功率通信能力、擴展性差，且簇頭節點直接將數據傳輸到sink 節點，因此，不適用于sink 節點距離傳感器區域較遠的大規模網絡。LEACH 協議假設簇頭節點為簇內每個普通節點創建TDMA 時隙表，盡管有些節點可能沒有數據需要傳輸，從而造成不必要的開銷[4-5]。

3 LEACH 協議改進算法

針對LEACH 協議的不足，出現很多對其改進的算法，主要涉及T(n)的計算、簇頭數的優化、簇內節點數的計算等[6-7]。本文在LEACH 協議的基礎上，通過采用多級分簇[8]，減少與sink 節點直接通信的簇頭節點數量，從而降低能量消耗、均衡節點能量、延長網絡生存周期。

所有傳感器節點隨機分布在指定區域并作如下假設：所有節點擁有相同的初始能量；任意2 個節點可以直接相互通信[9]；在節點部署之后，不會隨時間移動，一直保持靜止；sink 節點位于離傳感器節點區域較遠的位置。

3.1 多級分簇結構

依據簇頭數與總節點數的百分比p，確定將網絡劃分為小單元的個數。在指定的場景中，按照所確定的單元個數，將網絡進行均勻劃分從而確定不同單元的范圍，各個節點通過判斷其坐標確定其所屬單元。

在每個劃分好的小單元中，分布若干傳感器節點，每個單元通過選舉產生一個二級簇頭節點，單元內其他節點將數據傳輸到二級簇頭節點進行數據融合。通過二次選舉，在二級簇頭中產生若干一級簇頭節點，二級簇頭節點將數據傳輸到最近的一級簇頭節點進行數據融合，最終由一級簇頭節點將數據直接傳輸到sink 節點。網絡聚簇情況示意圖如圖1 所示。

圖1 網絡聚簇情況示意圖

通過劃分網絡單元，保證簇頭節點的均勻分布；通過采用多級分簇[10-11]，減少與sink 節點直接通信的節點數量，從而均衡網絡能量消耗，延長網絡生存周期。

3.2 簇頭選舉機制

在網絡建立后，進行簇頭選取。在第一輪的選舉中，采用與LEACH 協議相同的方法，在劃分的每個單元中，每個節點隨機產生一個[0,1]之間的隨機數，并按式(1)計算T(n)[12]。若該隨機數小于T(n)，則該節點當選為二級簇頭。同理，在二級簇頭節點中隨機產生[0,1]之間的隨機數并與T(n)比較，若小于T(n)，則當選為一級簇頭。

在之后的選舉中，以節點剩余能量為標準；在每個單元中，各個節點將其剩余能量情況發送到二級簇頭，由二級簇頭動態選擇具有最多剩余能量的節點為新的二級簇頭。同理，二級簇頭將其剩余能量情況發送到一級簇頭并由一級簇頭選取剩余能量最多的節點為新的簇頭。在數據傳輸階段，各級簇頭節點采用與LEACH 協議同樣的方法為其簇內各個節點創建TDMA 時隙表，各個節點在指定的時隙內，進行數據傳輸。簇頭節點收到數據后進行數據融合，并向上一級節點傳輸，最終由一級簇頭傳輸到sink 節點。

簇頭選舉算法如下：

定義 Ui表示普通節點；CH(Ui)表示二級簇頭節點；MCH(Ui)表示一級簇頭節點；A(Ui)表示普通節點產生的隨機數；A(CHi)表示二級簇頭節點產生的隨機數；E(Ui)表示節點剩余能量。

算法描述如下：

通過上述方法，對LEACH 協議進行改進，采用多級分簇減少與sink 直接通信的節點數目，通過引入剩余能量進行簇頭節點選取，均衡節點能量消耗。

4 仿真分析

4.1 仿真場景與參數

在100 m×100 m 區域內，隨機分布100 個傳感器節點，所有節點同構，擁有同樣的初始能量且節點靜止不動，sink節點固定在(40,200)。取p 為0.15，即將網絡劃分為15 個小單元，并通過計算坐標，確定不同單元的范圍。各個節點通過其坐標確定其所屬單元。節點初始能量為0.5 J，傳輸能耗和接收能耗為50 nJ/bit，數據融合能耗為5 nJ/bit，數據包大小為4000 bit。仿真采用Matlab R2007a 進行，將改進后的協議與LEACH 協議進行對比，驗證其性能。

LEACH 協議聚簇分布如圖2 所示。

圖2 LEACH 協議聚簇分布

利用本文算法改進LEACH 協議，得到的聚簇分布如圖3 所示。LEACH 協議由簇頭節點直接將數據傳輸到sink節點，改進后的協議經過2 次選舉，減少了與sink 節點直接通信的節點數目。

圖3 改進協議的聚簇分布

4.2 節點存活數比較

存活節點數比較如圖4 所示，LEACH 協議在第170 輪附近的時候，出現第一個死亡節點，本文算法第一個死亡節點出現在第330 輪附近。LEACH 協議在第950 輪左右，節點全部死亡，而更改后的協議，在第1000 輪運行完畢之后，還有若干個存活節點。由此說明，本文算法可以有效避免節點過早死亡，達到延長網絡生存周期的目的。

圖4 存活節點數比較

4.3 能量消耗情況比較

網絡剩余能量比較如圖5 所示。

圖5 網絡剩余能量比較

從圖5 可以看出，本文算法可以降低網絡能量消耗，延長網絡生存周期，這是因為采用多級聚簇，減少了與sink節點直接通信的節點數目，同時，在選舉簇頭節點時，考慮了節點剩余能量，選取具有最多剩余能量的節點為簇頭，所以相較于LEACH 協議，更有利于網絡能量均衡。

4.4 網絡規模情況比較

當傳感器節點數目增加到200 個時，圖6 為存活節點數比較。從圖6 可以看出，當網絡規模增加到200 節點時，LEACH 協議在第230 輪左右，出現第一個死亡節點，而本文算法在第420 輪左右才出現第一個死亡節點。由此說明，當網絡規模增大時，本文算法仍然可以有效地減少能量消耗，延長網絡生存周期。

圖6 存活節點數比較(200 節點)

5 結束語

本文提出一種LEACH 協議的多級分簇改進算法。采用劃分網絡的方法，保證簇頭在整個網絡內均勻分布，通過二次聚簇，減少與sink 節點直接通信的簇頭節點數，并在簇頭選舉過程中引入節點剩余能量，從而更有效地保證了網絡的能耗均衡。仿真結果表明，該算法均衡了節點能耗，避免了節點過早死亡，有效改善了網絡性能。但目前研究都是基于理想環境，下一步將考慮環境干擾因素進行深入研究。

[1]Akyildiz I F,Sankarasubramaniam Y,Su W,et al. Wireless Sensor Networks: A Survey[J]. Computer Networks,2002,38(4): 393-422.

[2]Heinzelman W R,Chandrakasan A,Balakrishnan H. Energy Efficient Communication Protocol for Wireless Microsensor Networks[C]//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. [S. l.]: IEEE Computer Society,2000.

[3]Kumar N,Kaur J. Improved LEACH Protocol for Wireless Sensor Networks[C]//Proceedings of the 33rd Hawaii International Conference on System. Washington D. C.,USA:IEEE Computer Society,2000.

[4]Yektaparast A,Nabavi F H,Sarmast A. An Improvement on LEACH Protocol[C]//Proceedings of International Conference on Advanced Communication Technology. Gujarat,India:[s. n.],2012.

[5]Sharma M,Sharma K. An Energy Efficient Extended LEACH[C]//Proceedings of International Conference on Communication Systems and Network Technologies. Jammu,India:[s. n.],2012.

[6]張 昱. 無線傳感器網絡的簇頭間距自適應HAD-LEACH算法[J]. 計算機工程與應用,2007,43(30): 124-127.

[7]王 法. 無線傳感器網絡分簇協議LEACH 協議中的簇頭選擇的改進研究[D]. 成都: 電子科技大學,2008.

[8]Wairagn G R. Extending LEACH Routing Algorithm for Wireless Sensor Network[D]. Kampala,Uganda: Makerere University,2009.

[9]黃加異,程良偉. 一種聚類區域自適應調整的WSN 能耗均衡分簇算法[J]. 計算機應用研究,2012,42(11): 76-79.

[10] 李成岳,申鉉京. 無線傳感器網絡中LEACH 路由算法的研究與改進[J]. 傳感技術學報,2010,23(8): 63-67.

[11] 胡星華,駱 堅. 固定簇的LEACH 半徑自適應簇頭改進算法[J]. 傳感技術學報,2011,24(1): 79-82.

[12] 呂 濤,朱清新,張路橋. 一種基于LEACH 協議的改進算法[J]. 電子學報,2011,39(6): 5-9.