基于能耗均衡的LEACH改進(jìn)方法

張 帥 楊清海 馮友兵

1(西安電子科技大學(xué)通信工程學(xué)院綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 陜西 西安 710071)2(江蘇科技大學(xué)電子信息學(xué)院 江蘇 鎮(zhèn)江 212003)

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)(WSN)作為一種新興的信息采集技術(shù)，具有自組織、部署快捷、高容錯(cuò)性和強(qiáng)隱蔽性等技術(shù)優(yōu)勢(shì)， 目前已廣泛應(yīng)用于工農(nóng)業(yè)、國(guó)家安全、城市監(jiān)控、空間探索等許多重要的領(lǐng)域[1-4]。而其自組織性使得拓?fù)淇刂瞥蔀閃SN生命期最大化的關(guān)鍵技術(shù)[5-7]。

LEACH[8]是最早提出的高效能分簇算法，其以簇為單元向基站傳送數(shù)據(jù)，在執(zhí)行過(guò)程中不斷循環(huán)進(jìn)行簇的重構(gòu)過(guò)程，重構(gòu)過(guò)程可以分兩個(gè)階段：簇的建立階段和傳輸數(shù)據(jù)的穩(wěn)定階段。為節(jié)省算法開銷，穩(wěn)定傳輸階段的持續(xù)時(shí)間要大于建立階段的持續(xù)時(shí)間。簇的建立過(guò)程可詳細(xì)分成4個(gè)階段：簇頭的選擇、簇頭的廣播、簇頭的建立和調(diào)度機(jī)制的生成；穩(wěn)定傳輸階段中，普通節(jié)點(diǎn)將采集的數(shù)據(jù)傳送到簇頭，簇頭對(duì)簇中所有節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行信息融合后再傳送給匯聚節(jié)點(diǎn)。LEACH很好地解決了傳感器節(jié)點(diǎn)能耗過(guò)大的問(wèn)題，有效降低了節(jié)點(diǎn)能耗。

但LEACH算法存在以下不足：在選擇簇頭時(shí)根據(jù)節(jié)點(diǎn)隨機(jī)產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù)選取簇頭，而沒有考慮節(jié)點(diǎn)當(dāng)前的剩余能量，有可能將低能量節(jié)點(diǎn)誤選為簇頭而加快該節(jié)點(diǎn)死亡的速度；同時(shí)，簇的數(shù)量具有很大的隨機(jī)性，而過(guò)多的簇也會(huì)減少分簇的帶來(lái)的能耗有效性。因此，如何改進(jìn)LEACH算法的簇頭選擇機(jī)制、優(yōu)化簇頭的數(shù)目成為延長(zhǎng)網(wǎng)絡(luò)正常生命周期的關(guān)鍵。

1 相關(guān)工作

針對(duì)傳統(tǒng)LEACH算法在簇頭選擇機(jī)制和簇頭數(shù)目隨機(jī)等方面存在的問(wèn)題，國(guó)內(nèi)外學(xué)者作了很多提高其性能的改進(jìn)。其中，文獻(xiàn)[9]提出LEACH-C算法，節(jié)點(diǎn)在每一輪開始時(shí)先把位置和能量等狀態(tài)信息發(fā)至基站，基站接收到節(jié)點(diǎn)狀態(tài)信息后，先計(jì)算網(wǎng)絡(luò)的能量均值，只有剩余能量大于該值的才可參與簇頭的選擇，然后基站利用模擬退火算法[10]進(jìn)行統(tǒng)一分簇，并選出簇頭，最后基站廣播包含分簇及簇頭的信息給各個(gè)節(jié)點(diǎn)完成入簇過(guò)程。該方法實(shí)際上是對(duì)LEACH算法中參加簇頭選擇的節(jié)點(diǎn)作了一些限制條件，但這種限制極其有限，特別是在節(jié)點(diǎn)的平均剩余能量較低時(shí)，即使?jié)M足LEACH-C算法的條件，也有較大可能出現(xiàn)簇頭過(guò)早死亡的情況。文獻(xiàn)[11]提出一種基于LEACH的簇頭成鏈可靠拓?fù)淇刂扑惴?，該算法?guī)定簇頭數(shù)目為5個(gè)，利用PEGASIS算法使簇頭成鏈,并選擇剩余能量最多的簇頭傳送信息給基站。選擇簇頭時(shí)考慮節(jié)點(diǎn)的剩余能量，給節(jié)點(diǎn)設(shè)置一個(gè)能量閾值，小于該值則不能當(dāng)選為簇頭。此方法雖提高了網(wǎng)絡(luò)的健壯性，但卻增加了延遲，網(wǎng)絡(luò)總能量消耗過(guò)快。文獻(xiàn)[12]提出基于節(jié)點(diǎn)剩余能量的分時(shí)分簇LEACH改進(jìn)算法，其通過(guò)分時(shí)分簇方式，有效克服了傳統(tǒng)LEACH算法中簇頭數(shù)目不穩(wěn)定的缺陷，且不會(huì)額外增加網(wǎng)絡(luò)的能耗，使得簇頭在整個(gè)網(wǎng)絡(luò)中的分布以及網(wǎng)絡(luò)的能量消耗較為均衡。文獻(xiàn)[13]提出基于簇頭間距均勻部署的LEACH改進(jìn)算法，該算法在簇頭選擇過(guò)程中限定簇頭間的最小距離，使得選出的簇規(guī)模近似均衡，以降低簇內(nèi)通信能量消耗，為避免網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的能量失衡，基于節(jié)點(diǎn)剩余能量設(shè)定新的簇頭選擇閾值改進(jìn)算法，增加剩余能量高的節(jié)點(diǎn)成為簇頭的概率。通過(guò)比較分析，本文算法在選取簇頭時(shí)考慮節(jié)點(diǎn)剩余能量因素，同時(shí)采用均衡化的思想，包括與網(wǎng)絡(luò)能耗相關(guān)的最優(yōu)簇頭數(shù)目和考慮節(jié)點(diǎn)剩余能量的簇頭選擇閾值，以降低網(wǎng)絡(luò)節(jié)點(diǎn)整體能耗、延長(zhǎng)網(wǎng)絡(luò)生命周期。

2 網(wǎng)絡(luò)部署

將N個(gè)WSN節(jié)點(diǎn)隨機(jī)分布在M×M的監(jiān)測(cè)區(qū)域內(nèi)，構(gòu)成WSN，其結(jié)構(gòu)如圖1所示。為便于分析，全文作如下假設(shè)：

(1) 假設(shè)監(jiān)測(cè)區(qū)域無(wú)障礙物；

(2) 基站的能量充足，且固定位于區(qū)域中心位置；

(3) 節(jié)點(diǎn)保持靜止且為同構(gòu)節(jié)點(diǎn)且自身能量已知；

(4) 節(jié)點(diǎn)間采用單跳通信。

圖1 無(wú)線傳感器網(wǎng)絡(luò)部署示意圖

3 能耗均衡拓?fù)淇刂扑惴?/h2>

3.1 通信能耗模型

本文算法無(wú)論是匯聚節(jié)點(diǎn)(基站)收集網(wǎng)絡(luò)節(jié)點(diǎn)的剩余能量，還是匯聚節(jié)點(diǎn)與簇頭節(jié)點(diǎn)、簇頭節(jié)點(diǎn)與簇內(nèi)成員節(jié)點(diǎn)之間的通信能耗均采用一階無(wú)線電能耗模型。WSN中匯聚中心(基站)和簇頭根據(jù)不同的情況使用多徑衰減模型和自由空間模型計(jì)算發(fā)送端和接收端之間在交換信息時(shí)的能量消耗[14]。設(shè)發(fā)送和接收1比特?cái)?shù)據(jù)的能耗為Eelec，d為發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的距離，則發(fā)送l比特的數(shù)據(jù)包的能耗為:

ETx(l,d)=lEelec+lεfsd2d

(1)

ETx(l,d)=lEelec+lεampd4d≥d0

(2)

接收l(shuí)比特的數(shù)據(jù)包的能耗為：

ERx(l)=lEelec

(3)

式中：l為傳送數(shù)據(jù)的長(zhǎng)度；d為發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的距離；d0為自由空間模型和多徑衰減模型轉(zhuǎn)折的閾值，一般在80米左右;εfs為自由空間模型參數(shù);εamp為多徑衰落空間模型參數(shù);Eelec為發(fā)送和接收單位比特?cái)?shù)據(jù)的能耗。

3.2 最優(yōu)簇頭數(shù)目

令簇頭的數(shù)量為k，利用能量消耗模型可以推出最優(yōu)簇頭數(shù)目Kopt。

(4)

式中：l為傳送數(shù)據(jù)的長(zhǎng)度，單位為bit;dtoBS為簇頭和基站的距離，如圖1所示。

簇內(nèi)成員節(jié)點(diǎn)的主要任務(wù)是將采集感知的信息傳送到對(duì)應(yīng)的簇頭，本文設(shè)置成員節(jié)點(diǎn)距離簇頭比較近即簇內(nèi)傳輸距離較小，故在簇內(nèi)采用自由空間能耗模型。因此，成員節(jié)點(diǎn)的能量消耗為：

(5)

式中：dtoCH為普通節(jié)點(diǎn)與簇頭之間的距離，如圖1所示。

?r2ρ(r,θ)drdθ

(6)

(7)

(8)

每個(gè)簇的能量消耗為:

(9)

故能量總消耗為:

Etotal=kEcluster=

(10)

最后，對(duì)Etotal求導(dǎo)k，從而計(jì)算出WSN最優(yōu)簇頭數(shù)目為：

(11)

式中：N為總節(jié)點(diǎn)數(shù)；εamp為多徑衰落模型系數(shù);εfs為自由空間模型系數(shù);M為布置區(qū)域邊長(zhǎng);dtoBS是簇頭與基站之間的距離。

3.3 基于能量的簇頭選擇閾值

由于簇的規(guī)模和簇頭選擇對(duì)WSN總能耗影響較大：一方面，當(dāng)簇的規(guī)模較小時(shí)，易導(dǎo)致WSN能量消耗不合理；另一方面，當(dāng)簇的規(guī)模較大時(shí)，簇頭轉(zhuǎn)發(fā)數(shù)據(jù)量太大、負(fù)擔(dān)較重，易造成能耗增大，使普通成員節(jié)點(diǎn)在單位之間可發(fā)送的數(shù)據(jù)量急速降低。故本文提出的簇頭選擇機(jī)制的改進(jìn)方法為：

(12)

3.4 算法描述

基于能耗均衡的LEACH改進(jìn)算法在執(zhí)行時(shí)循環(huán)進(jìn)行簇的重構(gòu)，仍然和傳統(tǒng)LEACH一樣按輪(round)進(jìn)行，每輪依然分成簇的建立階段和傳輸數(shù)據(jù)的穩(wěn)定階段。該算法的目標(biāo)是在每一輪中產(chǎn)生可以實(shí)現(xiàn)整個(gè)WSN更低能耗的最優(yōu)數(shù)目的簇頭，同時(shí)，在簇頭的選舉時(shí)充分考慮節(jié)點(diǎn)的剩余能量引入簇頭選擇新閾值，從而使能量消耗更加均衡。

簇的建立可詳細(xì)分成4個(gè)階段：選擇簇頭、簇頭廣播信息、普通節(jié)點(diǎn)入簇和生成調(diào)度機(jī)制。首先，為了使得WSN能耗更加均衡，本文改進(jìn)算法中由匯聚中心或者基站集中調(diào)度產(chǎn)生最優(yōu)簇頭數(shù)目Kopt。然后在已經(jīng)確定最優(yōu)數(shù)目簇頭的基礎(chǔ)上，通過(guò)一種分布式的方法來(lái)形成簇，其間節(jié)點(diǎn)不受任何中心節(jié)點(diǎn)調(diào)控而自主決定是否成為簇頭。進(jìn)行選舉簇頭的過(guò)程中，每個(gè)節(jié)點(diǎn)都要產(chǎn)生一個(gè)基于自身剩余能量的簇頭選擇新閾值T′(n)以及一個(gè)0～1之間的隨機(jī)數(shù)，當(dāng)隨機(jī)數(shù)小于T′(n)，并且考慮該節(jié)點(diǎn)在最近的1/P輪中未當(dāng)選為簇頭，則當(dāng)選為簇頭，并發(fā)布自己是簇頭的公告消息，這樣做的目的是具有多能量的節(jié)點(diǎn)比能量少的節(jié)點(diǎn)更加容易被選舉為簇頭。簇頭被選舉之后利用非持續(xù)性CSMA MAC協(xié)議廣播簇頭消息(ADV)，其余節(jié)點(diǎn)根據(jù)自己所收到的廣播信號(hào)的強(qiáng)弱來(lái)判斷其歸屬于哪個(gè)簇，然后簇頭建立一個(gè)TDMA調(diào)度為成員節(jié)點(diǎn)分配交換的時(shí)隙，從而保證數(shù)據(jù)消息之間沒有沖突，并且使非簇頭節(jié)點(diǎn)的無(wú)線電模塊在非傳輸時(shí)間內(nèi)關(guān)閉，節(jié)省了能量。在穩(wěn)定傳輸數(shù)據(jù)的階段，WSN普通節(jié)點(diǎn)將采集的數(shù)據(jù)信息發(fā)給簇頭，簇頭進(jìn)行數(shù)據(jù)信息融合后發(fā)給匯聚節(jié)點(diǎn)。具體步驟：

(1) 在M×M監(jiān)測(cè)區(qū)域中隨機(jī)部署N個(gè)傳感器節(jié)點(diǎn)，并在監(jiān)測(cè)區(qū)域中心部署匯聚節(jié)點(diǎn)或者基站，其結(jié)構(gòu)示意圖如圖1所示。

(2) 無(wú)線傳感器節(jié)點(diǎn)向整個(gè)網(wǎng)絡(luò)廣播自身信息。

(3) 根據(jù)式(11)確定最優(yōu)簇頭數(shù)目。

(4) 根據(jù)最優(yōu)簇頭數(shù)目Kopt和WSN中已經(jīng)成為簇頭的次數(shù)來(lái)確定簇頭。具體的選擇方法是：每個(gè)WSN節(jié)點(diǎn)產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù)，與將隨機(jī)數(shù)與式(12)所示的閾值進(jìn)行比較，若小于閾值，則當(dāng)選為簇頭。

(5) 簇頭確定之后向全網(wǎng)廣播簇頭消息，其余節(jié)點(diǎn)接收消息，并向距離最近的簇頭發(fā)送加入消息，完成簇的建立。

(6) 簇頭采用TDMA為成員分配交換數(shù)據(jù)的時(shí)隙。

(7) 數(shù)據(jù)穩(wěn)定傳輸階段，成員節(jié)點(diǎn)將采集信息發(fā)給簇頭，簇頭將信息融合后再發(fā)給基站。

(8) 進(jìn)入下一輪，重復(fù)步驟(3)-步聚(7)。

4 仿真與結(jié)果分析

4.1 仿真參數(shù)

設(shè)在100 m×100 m的區(qū)域中隨機(jī)部署N個(gè)傳感器節(jié)點(diǎn)，其中匯聚節(jié)點(diǎn)/基站位于區(qū)域中心(50，50)。其他仿真參數(shù)的設(shè)置參考文獻(xiàn)[14]。

表1 仿真參數(shù)

4.2 仿真結(jié)果分析

為分析節(jié)點(diǎn)消耗的能量是否均衡，對(duì)網(wǎng)絡(luò)已出現(xiàn)節(jié)點(diǎn)死亡后的各輪次死亡節(jié)點(diǎn)數(shù)量進(jìn)行對(duì)比分析。仿真發(fā)現(xiàn)兩種算法在100輪時(shí)均已經(jīng)出現(xiàn)了死亡節(jié)點(diǎn)，圖2給出了本文改進(jìn)算法和傳統(tǒng)LEACH算法在第100輪時(shí)，死亡節(jié)點(diǎn)和工作節(jié)點(diǎn)的分布情況，很顯然本文改進(jìn)算法死亡節(jié)點(diǎn)數(shù)量遠(yuǎn)遠(yuǎn)少于傳統(tǒng)LEACH算法。

(a) 傳統(tǒng)LEACH算法

(b) 本文算法圖2 第100輪時(shí)死亡節(jié)點(diǎn)分布情況

圖3為100個(gè)節(jié)點(diǎn)在同一隨機(jī)分布下，使用本文算法和傳統(tǒng)算法的死亡節(jié)點(diǎn)數(shù)量的變化趨勢(shì)，可以看出，傳統(tǒng)LEACH算法大概在65輪左右出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)，隨后死亡節(jié)點(diǎn)的數(shù)量急劇上升，且節(jié)點(diǎn)大面積死亡。而本文改進(jìn)算法第一個(gè)死亡節(jié)點(diǎn)出現(xiàn)在約70輪，且隨著工作輪數(shù)的增加，死亡節(jié)點(diǎn)的數(shù)量呈平緩上升趨勢(shì)，說(shuō)明使用本文改進(jìn)算法延遲了第一個(gè)節(jié)點(diǎn)時(shí)間，且節(jié)點(diǎn)能耗更加均衡。

圖3 死亡節(jié)點(diǎn)數(shù)量變化趨勢(shì)

為了避免單次仿真的偶然性，圖4給出兩種算法在多次仿真以及同一隨機(jī)分布情況下第一個(gè)節(jié)點(diǎn)死亡的輪數(shù)，可以看出，本文改進(jìn)算法第一個(gè)節(jié)點(diǎn)死亡時(shí)間始終晚于傳統(tǒng)算法，說(shuō)明整個(gè)網(wǎng)絡(luò)的能耗更加均衡，有效延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

圖4 N=100，第一個(gè)節(jié)點(diǎn)死亡的輪數(shù)(first_dead)

5 結(jié) 語(yǔ)

本文在選取簇頭時(shí)考慮節(jié)點(diǎn)剩余能量因素，同時(shí)采用均衡化的思想來(lái)選取簇頭，即從最優(yōu)簇頭數(shù)目和基于能量的簇頭選擇閾值兩個(gè)方面入手，對(duì)LEACH算法進(jìn)行了改進(jìn)。仿真實(shí)驗(yàn)結(jié)果表明，本文算法與傳統(tǒng)LEACH算法相比，降低了WSN節(jié)點(diǎn)的整體能耗，延長(zhǎng)了網(wǎng)絡(luò)使用壽命。