基于簇頭閾值優(yōu)化的LEACH的分簇路由

劉 衛(wèi)，李躍飛, 謝英輝

(1. 長沙民政職業(yè)技術(shù)學(xué)院，湖南 長沙 410004;2. 湖南信息學(xué)院，湖南 長沙 410104)

0 引 言

隨著現(xiàn)代電子技術(shù)的發(fā)展，無線傳感網(wǎng)絡(luò)廣泛應(yīng)用于各類應(yīng)用，如康復(fù)醫(yī)療、戰(zhàn)場、野外環(huán)境監(jiān)測等[1-3]。這些傳感節(jié)點先感測環(huán)境數(shù)據(jù)，然后經(jīng)處理后，再傳輸至基站。由于無線傳感網(wǎng)絡(luò)常部署于野外惡劣環(huán)境，更換節(jié)點電池是不現(xiàn)實的。因此，能量消耗成為無線傳感網(wǎng)絡(luò)的研究熱點[4]。

為了節(jié)省傳感節(jié)點能量，一般不允許傳感節(jié)點與基站直接通信。因此，為了存儲節(jié)點能量，將鄰近節(jié)點或具有相同特性的節(jié)點匯聚成一個簇[5-6]。每個簇內(nèi)選擇一個節(jié)點作為簇頭，并由簇頭收集簇內(nèi)節(jié)點的感測數(shù)據(jù)，經(jīng)融合后，再傳輸至基站。通過簇結(jié)構(gòu)，有利于降低能量消耗。

目前，研究人員提出不同的簇算法，如基于層次、基于區(qū)域以及基于節(jié)點度分簇算法，其中基于節(jié)點度分簇算法得到廣泛關(guān)注，也是本文關(guān)注的焦點?；诠?jié)點度的分簇算法是利用節(jié)點度決策簇頭。所謂節(jié)點度就是指節(jié)點的一跳鄰居節(jié)點數(shù)。盡管節(jié)點度反映了節(jié)點密度信息，但是未能全面地反映鄰居節(jié)點的分布情況。

為此，以低功耗自適應(yīng)簇分層 (Low Energy Adaptive Clustering Hierarchy，LEACH)[7]協(xié)議為基礎(chǔ)，提出基于節(jié)點分布密度的LEACH的修正協(xié)議，記為LEACH-C。LEACH-C協(xié)議充分考慮了節(jié)點分布密度。其原因在于：分布密度越高，意味著在一小面積區(qū)域內(nèi)節(jié)點數(shù)越多，即鄰居節(jié)點間相距更近。那么位于密集區(qū)域中心的節(jié)點就只需消耗較少的能量就連接到其他節(jié)點。因此，分布密度高的節(jié)點優(yōu)先成為簇頭。反之，分布密度越低，意味著在區(qū)域內(nèi)其鄰居節(jié)點數(shù)少，且分布廣。這類節(jié)點需要消耗更的能量才能與鄰居節(jié)點通信。

為了更好地描述節(jié)點分布密度，LEACH-C協(xié)議首先定義內(nèi)部節(jié)點和邊界節(jié)點，并通過內(nèi)部節(jié)點數(shù)計算節(jié)點分布密度。然后，依據(jù)節(jié)點分布密度因子和剩余能量因子對LEACH協(xié)議中的閾值進行修正。同時，依據(jù)節(jié)點分布密度調(diào)整節(jié)點傳輸距離，進而降低節(jié)點能量消耗。最后，仿真實驗數(shù)據(jù)表明，修正后的LEACH-C協(xié)議能夠有效地保存能量，提高網(wǎng)絡(luò)壽命。

1 LEACH概述及約束條件

1.1 LEACH協(xié)議及其不足

作為經(jīng)典分簇算法，低功耗自適應(yīng)分層LEACH協(xié)議受到廣泛的關(guān)注。LEACH協(xié)議由初始階段和穩(wěn)定傳輸兩個階段組成。同時，LEACH協(xié)議將時間劃分不同的輪。每一輪執(zhí)行一次簇頭選擇算法。在每輪內(nèi)，每個傳感節(jié)點競爭成為簇頭或加入鄰近的簇。

在競爭簇頭時，每個傳感節(jié)點先產(chǎn)生一個隨機數(shù)Nr，再與閾值Th進行比較。若小于閾值，就成為簇頭。節(jié)點si的閾值定義如式(1)所示。

(1)

其中p表示網(wǎng)內(nèi)簇頭數(shù)的比例，即簇頭數(shù)占總的節(jié)點數(shù)的百分比。而r表示當(dāng)前輪數(shù)。G為節(jié)點集，由在r-1輪內(nèi)未成為簇頭的節(jié)點組成。

依式(1)可知，閾值隨輪數(shù)r的增加而上升。換而言之，后期節(jié)點比前期節(jié)點成為簇頭的概率要大。一旦成為簇頭，節(jié)點就向鄰居節(jié)點廣播消息包，該消息包有兩個目的：一是告知鄰近節(jié)點，該節(jié)點已成為簇頭；二是讓非簇頭節(jié)點接收該消息包，使得這些接收節(jié)點能夠估算與該簇頭的距離，進而決策是否加入該簇。

一旦形成簇后，簇頭給簇成員節(jié)點分配時隙。簇成員節(jié)點在各自時隙內(nèi)傳輸數(shù)據(jù)，而其他時隙保持睡眠狀態(tài)，進而減少能量消耗。

盡管LEACH協(xié)議相比其他算法存在一定的優(yōu)勢，但是它仍存在一些不足。首先，LEACH協(xié)議在選擇簇頭是以單個節(jié)點的特性為依據(jù)，而并沒有考慮到周圍環(huán)境特性，如節(jié)點密度。其次，在選擇簇頭時，沒有考慮到距離信息。離簇頭或基站近的節(jié)點的能量消耗速度更快。因此，若不考慮到距離信息，容易導(dǎo)致覆蓋空洞。

為此，本文以LEACH協(xié)議為基礎(chǔ)，對其簇頭選擇策略進行改進，即對閾值進行修改，同時采用自適應(yīng)調(diào)整傳輸距離策略。

1.2 約束條件

提出的LEACH-C協(xié)議基于以下約束條件:

(1)節(jié)點隨機分布于網(wǎng)絡(luò)；

(2)所有節(jié)點的初始能量相同，并且有限；

(3)網(wǎng)絡(luò)屬靜態(tài)的。即節(jié)點一旦部署后，就不再移動；

(4)節(jié)點能夠依據(jù)接收信號強度，估算自己的位置；

(5)節(jié)點能夠估算自己的剩余能量。

1.3 能量模型

無線電能量消耗主要有兩部分組成：運行電子元器件、功率放大器所消耗的能量和接收器所消耗的能量[8]。如圖1所示，在相距為d的兩節(jié)點間傳輸q比特的數(shù)據(jù)信息，消耗的能量：

(2)

其中，Eelec運行發(fā)射器或接收器固定的能量消耗，Efrris、Etworay分別表示發(fā)射器在自空間、雙徑傳播模型(two ray ground model)的單位功率放大器的能量消耗[9]。而dco的定義如式(3)所示：

(3)

其中，λ為波長、l為系統(tǒng)損耗。ht、hr分別表示發(fā)射天線和接收天線的增益系數(shù)。相應(yīng)地，對于接收q比特的數(shù)據(jù)包所消耗的能量：

ERX(q)=q*Eelec

(4)

圖1 無線電能量消耗模型

2 LEACH-C協(xié)議

與LEACH協(xié)議不同，LEACH-C協(xié)議在選擇簇頭充分考慮了能量、距離以及節(jié)點分布密度。同時，依據(jù)節(jié)點分布密度自適應(yīng)調(diào)整傳輸距離。

2.1 內(nèi)部節(jié)點和邊界節(jié)點

首先定義兩類節(jié)點：內(nèi)部節(jié)點和邊界節(jié)點。假定網(wǎng)絡(luò)節(jié)點集為S,其內(nèi)有N個傳感節(jié)點，即si∈S,且i=1,2,…,N。節(jié)點si的一跳鄰居節(jié)點集表示為Nei。

內(nèi)部節(jié)點：如果節(jié)點sk∈S被鄰居節(jié)點包圍，則節(jié)點sk稱為內(nèi)部節(jié)點。具體而言，如果在節(jié)點sk一跳鄰居集Nek內(nèi)有三個節(jié)點，并且這三個節(jié)點分別與節(jié)點sk所形成的三個夾角之和等于360°，則該節(jié)點稱為內(nèi)部節(jié)點。

圖2 內(nèi)部節(jié)點和邊界節(jié)點的定義示意圖

如圖2(a)所示，節(jié)點sk的一跳鄰居集內(nèi)有三個節(jié)點sa、sb和sc。它們分別與sk連線所形成的三個角度之和等于360°，如式(5)所示，則節(jié)點sk稱為內(nèi)部節(jié)點。

∠α+∠β+∠λ=360°

(5)

利用三角函數(shù)知識，并結(jié)合各連線的長度，可計算式(5)：

(6)

其中x、y、z、a、b和c分別表示各連線的長度。

邊界節(jié)點：如果節(jié)點sj∈S不是內(nèi)部節(jié)點，則該節(jié)點就稱為邊界節(jié)點。

如圖2(b)所示，節(jié)點sj不滿足內(nèi)部節(jié)點的定義。在其一跳鄰居節(jié)點內(nèi)，不存在三個節(jié)點與它形成的三個夾角之和等于360°。

2.2 節(jié)點分布密度

每個節(jié)點判斷自己是否為內(nèi)部節(jié)點或邊界節(jié)點。引入變量flag，若是內(nèi)部節(jié)點，則flag=1，否則為0。然后節(jié)點將自己的flag值將載入HELLO消息包，并向鄰居節(jié)點傳輸。

鄰居節(jié)點通過交互HELLO消息包，便可估算一跳鄰居節(jié)點中有多少節(jié)點是內(nèi)部節(jié)點。節(jié)點si的一跳鄰居節(jié)點集為Nei，集內(nèi)節(jié)點數(shù)為|Nei|。若Nei內(nèi)有Mi個內(nèi)部節(jié)點，則節(jié)點si的分布密度ρi：

(7)

從式(7)可知，ρi值越大，表明節(jié)點分布越密集，反之，節(jié)點分布越稀疏。

2.3 自適應(yīng)傳輸距離策略

傳統(tǒng)的LEACH協(xié)議采用固定傳輸距離，不論節(jié)點周期環(huán)境是密集或稀疏[10]，這不但浪費了節(jié)點能量，也可能形成了不必要的干擾。為此，LEACH-C協(xié)議自適應(yīng)調(diào)整傳輸距離。依據(jù)節(jié)點分布密度情況，提升或縮短傳輸距離。

從式(7)可知，節(jié)點的分布密度反映了鄰居節(jié)點類型，即是內(nèi)部節(jié)點多還是邊界節(jié)點多。這也體現(xiàn)了鄰居節(jié)點的分布情況，是分布緊密還是松散的。節(jié)點的分布密度越高，意味著節(jié)點所處的區(qū)域越密集。反之，節(jié)點所處的區(qū)域越稀疏。

如圖3所示，三角形狀的點表示邊界節(jié)點，而圓節(jié)點表示內(nèi)部節(jié)點。區(qū)域1的邊界節(jié)點形成了一個覆蓋空洞，而區(qū)域2的內(nèi)部節(jié)點表征了一個密集區(qū) 域。而區(qū)域3表征了一個低密度區(qū)域，其周圍有多個邊界節(jié)點。

圖3 內(nèi)部節(jié)點或邊界節(jié)點對區(qū)域覆蓋的影響

由圖3可知，分布密度越大，節(jié)點聚集越多，可縮短傳輸距離，反之，可提升傳輸距離。因此，將節(jié)點分布密度ρi分為三類。假定R是節(jié)點最大的傳輸距離。如果ρi∈(0.85,1]，節(jié)點的傳輸距離為R/4；若ρi∈(0.5,0.85]，節(jié)點的傳輸距離為R/2；若ρi∈(0,0.5]，節(jié)點的傳輸距離為R。傳輸距離調(diào)整策略的偽代碼如圖4所示。

圖4 傳輸距離調(diào)整過程偽代碼

2.4 閾值修改

LEACH協(xié)議的閾值設(shè)置并沒有顧及到節(jié)點密度以及節(jié)點能量信息。為此，LEACH-C協(xié)議對此閾值修改。將節(jié)點的分布密度和剩余能量信息融入閾值，其中節(jié)點si的剩余能量百分比Ei:

(8)

其中Eint、Ecur分別表示節(jié)點si的初始能量、當(dāng)前剩余能量。

考慮到節(jié)點分布密度和剩余能量百分比對閾值影響的不同，給這兩個因子設(shè)置不同的比重。將這兩因子融合成一個變量ψi：

(9)

最后，對LEACH協(xié)議的閾值(式(1))進行修改，如式(10)所示：

(10)

3 性能仿真

3.1 仿真參數(shù)及性能指標(biāo)

本節(jié)評估LEACH-C協(xié)議的性能，利用MATLAB建立仿真平臺，并與LEACH、DT-LEACH[11]和DEGRA[12]進行比較。選擇這三個協(xié)議作為參考原因在于：LEACH是經(jīng)典的簇協(xié)議，并且本文所提出的協(xié)議是基于LEACH的改進協(xié)議。

而DT-LEACH和DEGRA協(xié)議均是基于節(jié)點密度集協(xié)議，與LEACH-C協(xié)議具有可比性。DT-LEACH協(xié)議與LEACH協(xié)議簇頭選擇策略相同，不同之處在于：DT-LEACH協(xié)議依據(jù)節(jié)點密度決策節(jié)點是否有資格加入簇。若節(jié)點密度小于預(yù)定的節(jié)點密度值D，就可以入該簇，否則不能加入。而DEGRA協(xié)議引用了博弈理論，利用博弈理論解決簇頭選擇問題。

100個節(jié)點隨機分布于200 m×200 m監(jiān)測區(qū)域內(nèi)?；疚挥诒O(jiān)測區(qū)域中心。節(jié)點的初始能量為1 J，節(jié)點傳輸距離最R=40 m，其他仿真參數(shù)如表1所示(注：“*”表示相乘)。

表1 仿真參數(shù)

3.2 數(shù)值分析

從每輪的能量消耗、傳輸?shù)南?shù)和網(wǎng)絡(luò)壽命三方面分析LEACH-C協(xié)議，其中，傳輸?shù)南?shù)表示在網(wǎng)絡(luò)內(nèi)有一半節(jié)點失效 (Half Node Die, HND)時，基站所接收到消息數(shù)。而網(wǎng)絡(luò)壽命表示從兩個方面進行分析：在第一個節(jié)點失效 (First Node Die, FND)前，所執(zhí)行的輪數(shù)，以及一半節(jié)點失效HND前，所執(zhí)行的輪數(shù)。每次實驗獨立重要10次，并記錄10次的實驗數(shù)據(jù)。

(1)每輪的能量消耗

平均每輪所消耗的能量數(shù)據(jù)如表2所示。從表2可知，LEACH協(xié)議所消耗的能量最多，而LEACH-C協(xié)議所消耗的能量最少。LEACH-C協(xié)議比LEACH的能量消耗降低50.7%。這主要因為：LEACH協(xié)議僅采用簡單的閾值決策簇頭，具有隨機性，沒有考慮到簇頭節(jié)點本身的特性，如剩余能量，這使得簇頭容易因能量耗盡而失效。一旦簇頭失效，會導(dǎo)致數(shù)據(jù)傳輸中斷，加大了能量消耗。

表2 平均每輪所消耗的能量

而LEACH-C協(xié)議在選擇簇頭，充分考慮了節(jié)點能量信息，以及節(jié)點分布密度，并自適應(yīng)調(diào)整傳輸距離，這些策略均有利于存儲節(jié)點能量。此外，DT-LEACH協(xié)議和DEGRA協(xié)議的能量消耗低于LEACH協(xié)議。原因在于：DT-LEACH和DEGRA協(xié)議與LEACH協(xié)議相比，它們在選擇簇頭時融合了更多節(jié)點信息，使得簇結(jié)構(gòu)更為穩(wěn)定。因此，DT-LEACH和DEGRA協(xié)議的能耗低于LEACH協(xié)議。

(2)傳輸?shù)南?shù)

本次實驗分析LEACH-C協(xié)議的在HND前，基站所接收的消息數(shù)，這個指標(biāo)反映了協(xié)議的數(shù)據(jù)傳輸性能。數(shù)據(jù)如表3所示。

表3 基站在HND前所接收的消息數(shù)

從表3可知，提出的LEACH-C協(xié)議所接收的消息數(shù)最多，比傳統(tǒng)的LEACH協(xié)議提高了約42.4%。而DT-LEACH和DEGRA協(xié)議中基站所接收的消息數(shù)也優(yōu)于LEACH協(xié)議。傳統(tǒng)的LEACH協(xié)議并沒有優(yōu)化簇頭選擇過程，只是簡單地利用預(yù)設(shè)的閾值定義節(jié)點成為簇頭的概率，沒有考慮到節(jié)點的個體特性。而盡管DT-LEACH協(xié)議的簇頭選擇策略與LEACH協(xié)議相同，但是它優(yōu)化簇形成過程，非簇頭節(jié)點加入簇，并不是像LEACH協(xié)議那樣采取簡單的就近原則，而是依據(jù)節(jié)點密度進行決策。所以，其性能優(yōu)于LEACH協(xié)議。

(3) 網(wǎng)絡(luò)壽命

最后，分析了各協(xié)議的網(wǎng)絡(luò)壽命，并分別利用在FND和HND時所執(zhí)行的輪數(shù)表征，數(shù)據(jù)結(jié)果如表4所示。

從表4可知，在提出的LEACH-C協(xié)議能夠有效地提高網(wǎng)絡(luò)壽命。在FND時，LEACH-C協(xié)議比LEACH、DT-LEACH和DEGRA協(xié)議的網(wǎng)絡(luò)壽命分別提高了71.87%、31.91%、16.07%。類似在，在HND時，LEACH-C協(xié)議比LEACH、DT-LEACH和DEGRA協(xié)議分別提高了14.30%、31.78%、16.74%。這些數(shù)據(jù)表明改進后LEACH-C協(xié)議能夠保存節(jié)點能量，進而擴延網(wǎng)絡(luò)壽命。

表4 網(wǎng)絡(luò)壽命

4 總 結(jié)

針對無線傳感網(wǎng)絡(luò)的簇算法，首先分析了經(jīng)典的LEACH協(xié)議的不足，然后提出LEACH的修正協(xié)議。依據(jù)節(jié)點分布密度和剩余能量對閾值進行修正，提高了簇頭性能，緩解了簇頭能耗速度。同時，對節(jié)點的傳輸距離進行自適應(yīng)地調(diào)整。在稀疏區(qū)域，提高傳輸距離，而在密集區(qū)域，降低傳輸距離。仿真結(jié)果表明，修正后的LEACH-C協(xié)議有效地保存了節(jié)點能量，提升了網(wǎng)絡(luò)壽命。