羅 冰，黃玉清

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

1 概述

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

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

本文提出一種LEACH 協(xié)議的多級分簇改進算法。采用多級聚簇的思想，并結(jié)合傳感器網(wǎng)絡(luò)的節(jié)能策略，對LEACH 協(xié)議進行改進。

2 LEACH 協(xié)議

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

在LEACH 的運行過程中，通過“輪”的概念表示每個簇的循環(huán)重構(gòu)。每輪分為2 個階段：構(gòu)建階段和穩(wěn)定階段。(1)在構(gòu)建階段，隨機選舉簇頭并進行聚簇。(2)在穩(wěn)定階段，簇內(nèi)節(jié)點向簇頭節(jié)點發(fā)送數(shù)據(jù)，簇頭節(jié)點進行數(shù)據(jù)融合并向sink 節(jié)點傳輸。

2.1 構(gòu)建階段

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

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

2.2 穩(wěn)定階段

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

LEACH 協(xié)議要求任意2 個節(jié)點可以直接互相通信，要求節(jié)點具有較大功率通信能力、擴展性差，且簇頭節(jié)點直接將數(shù)據(jù)傳輸?shù)絪ink 節(jié)點，因此，不適用于sink 節(jié)點距離傳感器區(qū)域較遠的大規(guī)模網(wǎng)絡(luò)。LEACH 協(xié)議假設(shè)簇頭節(jié)點為簇內(nèi)每個普通節(jié)點創(chuàng)建TDMA 時隙表，盡管有些節(jié)點可能沒有數(shù)據(jù)需要傳輸，從而造成不必要的開銷[4-5]。

3 LEACH 協(xié)議改進算法

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

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

3.1 多級分簇結(jié)構(gòu)

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

在每個劃分好的小單元中，分布若干傳感器節(jié)點，每個單元通過選舉產(chǎn)生一個二級簇頭節(jié)點，單元內(nèi)其他節(jié)點將數(shù)據(jù)傳輸?shù)蕉壌仡^節(jié)點進行數(shù)據(jù)融合。通過二次選舉，在二級簇頭中產(chǎn)生若干一級簇頭節(jié)點，二級簇頭節(jié)點將數(shù)據(jù)傳輸?shù)阶罱囊患壌仡^節(jié)點進行數(shù)據(jù)融合，最終由一級簇頭節(jié)點將數(shù)據(jù)直接傳輸?shù)絪ink 節(jié)點。網(wǎng)絡(luò)聚簇情況示意圖如圖1 所示。

圖1 網(wǎng)絡(luò)聚簇情況示意圖

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

3.2 簇頭選舉機制

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

在之后的選舉中，以節(jié)點剩余能量為標準；在每個單元中，各個節(jié)點將其剩余能量情況發(fā)送到二級簇頭，由二級簇頭動態(tài)選擇具有最多剩余能量的節(jié)點為新的二級簇頭。同理，二級簇頭將其剩余能量情況發(fā)送到一級簇頭并由一級簇頭選取剩余能量最多的節(jié)點為新的簇頭。在數(shù)據(jù)傳輸階段，各級簇頭節(jié)點采用與LEACH 協(xié)議同樣的方法為其簇內(nèi)各個節(jié)點創(chuàng)建TDMA 時隙表，各個節(jié)點在指定的時隙內(nèi)，進行數(shù)據(jù)傳輸。簇頭節(jié)點收到數(shù)據(jù)后進行數(shù)據(jù)融合，并向上一級節(jié)點傳輸，最終由一級簇頭傳輸?shù)絪ink 節(jié)點。

簇頭選舉算法如下：

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

算法描述如下：

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

4 仿真分析

4.1 仿真場景與參數(shù)

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

LEACH 協(xié)議聚簇分布如圖2 所示。

圖2 LEACH 協(xié)議聚簇分布

利用本文算法改進LEACH 協(xié)議，得到的聚簇分布如圖3 所示。LEACH 協(xié)議由簇頭節(jié)點直接將數(shù)據(jù)傳輸?shù)絪ink節(jié)點，改進后的協(xié)議經(jīng)過2 次選舉，減少了與sink 節(jié)點直接通信的節(jié)點數(shù)目。

圖3 改進協(xié)議的聚簇分布

4.2 節(jié)點存活數(shù)比較

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

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

4.3 能量消耗情況比較

網(wǎng)絡(luò)剩余能量比較如圖5 所示。

圖5 網(wǎng)絡(luò)剩余能量比較

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

4.4 網(wǎng)絡(luò)規(guī)模情況比較

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

圖6 存活節(jié)點數(shù)比較(200 節(jié)點)

5 結(jié)束語

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

[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]張 昱. 無線傳感器網(wǎng)絡(luò)的簇頭間距自適應(yīng)HAD-LEACH算法[J]. 計算機工程與應(yīng)用,2007,43(30): 124-127.

[7]王 法. 無線傳感器網(wǎng)絡(luò)分簇協(xié)議LEACH 協(xié)議中的簇頭選擇的改進研究[D]. 成都: 電子科技大學(xué),2008.

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

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

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

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

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