無線傳感器網(wǎng)絡(luò)LEACH算法的改進(jìn)

李 登，徐東明

(西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安 710121)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)由小型傳感器組成[1]。由于傳感器內(nèi)置電池不易更換的缺點，節(jié)點的能效對于WSN尤為重要。分簇算法常被用來優(yōu)化WSN的網(wǎng)絡(luò)能耗，聚類是分簇算法中常見的一種方法[2]，低功耗自適應(yīng)集分簇算法(low energy adaptive clustering hierarchy，LEACH)[3]被認(rèn)為是現(xiàn)有突出的分簇路由算法之一，但它隨機分簇和簇頭能耗不均勻的缺點，會使簇頭節(jié)點能量耗盡的時間縮短而影響WSN的性能。文獻(xiàn)[4]的改進(jìn)算法加入距離因子，剩余能量因子來選擇簇頭節(jié)點；文獻(xiàn)[5]提出基于集中節(jié)能距離(CEED)算法，在頭節(jié)點選取時加入能量的考量，但是該算法降低了節(jié)點成為簇頭的概率。文獻(xiàn)[6]提出基于能量和密度的低功耗自適應(yīng)集簇(LEACH-ED)分層協(xié)議，利用加權(quán)思想使節(jié)點產(chǎn)生了基于能量和密度的權(quán)值，但是該算法未考慮節(jié)點之間的距離及節(jié)點可重復(fù)利用的情況。

本文基于LEACH分簇算法，對文獻(xiàn)[6]算法進(jìn)行了改進(jìn)。改進(jìn)的算法除了考慮每輪運行中網(wǎng)絡(luò)的平均能量，還加入節(jié)點到基站的距離、網(wǎng)絡(luò)運行的有效輪次及每輪運行結(jié)束后節(jié)點的能量剩余等情況。此外每個分組中的節(jié)點數(shù)不能太多更不能太少，所以節(jié)點選擇加入某個分簇時，還需計算頭節(jié)點的半徑范圍。改進(jìn)的方法充分考慮已當(dāng)過簇頭的節(jié)點可以重復(fù)被選為頭節(jié)點的情況，最大化提高網(wǎng)絡(luò)中節(jié)點的利用率。

1 無線傳感器網(wǎng)絡(luò)和能量模型

1.1 無線傳感器網(wǎng)絡(luò)模型

無線傳感器網(wǎng)絡(luò)的組成如圖1所示。數(shù)據(jù)從節(jié)點發(fā)送到基站(base station，BS)可以是單跳或者多跳，節(jié)點多部署在偏遠(yuǎn)地區(qū)。由于傳感器節(jié)點電池不易更換的特點導(dǎo)致它容易出現(xiàn)能量耗盡的問題。因此，如何盡可能使節(jié)點的能耗均勻化作為整個網(wǎng)絡(luò)生存時間的有利條件。

WSN網(wǎng)絡(luò)模型[7]假設(shè)如下：

(1)WSN由n個傳感器節(jié)點和一個基站(BS)組成。節(jié)點均勻分布在區(qū)域A=M×M[m2] 空間上；

(2)每個節(jié)點的有效感知范圍、存儲的容量、通信的范圍相同；

(3)基站位于傳感區(qū)域外，具有無限的資源(即功率和存儲容量)；

(4)每個節(jié)點始終都有要在其各自指定的時間內(nèi)發(fā)送的信息；

(5)傳感器節(jié)點和基站都是靜止的；

(6)傳感器節(jié)點配備GPS設(shè)備，因此可識別位置。

圖1 無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)

1.2 無線傳感器網(wǎng)絡(luò)能量模型

采用文獻(xiàn)[8]中使用的能量模型如圖2所示。

圖2 無線電能量模型

發(fā)送端發(fā)送Lbit數(shù)據(jù)的耗能如式(1)所示

(1)

節(jié)點接收Lbit消息的能耗如式(2)所示

Er=L*Eelec

(2)

分組中頭節(jié)點處理成員節(jié)點數(shù)據(jù)消息的能量消耗如式(3)所示

Ea=L*Eda

(3)

式中：Eda為單位數(shù)據(jù)消息聚合的耗能大小。

2 LEACH算法的改進(jìn)

2.1 LEACH算法

LEACH算法的具體操作過程是以“輪”的方式進(jìn)行，每輪的運行由如下階段組成：網(wǎng)絡(luò)的初始化階段和分簇內(nèi)節(jié)點數(shù)據(jù)的穩(wěn)定傳輸階段。第一階段通過讓各個節(jié)點在 [0 1] 之間選擇隨機數(shù)來判斷該節(jié)點能否成為該輪傳輸?shù)拇仡^節(jié)點，如果該隨機數(shù)與已經(jīng)確定的T(n) 相比較小于該閾值，那么這個節(jié)點就可以被選取成為簇頭節(jié)點，此時新的簇頭節(jié)點就會廣播給其它節(jié)點以告知其成為頭節(jié)點，網(wǎng)絡(luò)中其它節(jié)點會依據(jù)頭節(jié)點傳來的消息情況來決定要加入某個分簇中。一旦分簇完成，系統(tǒng)就會開始節(jié)點數(shù)據(jù)的傳輸階段，在此階段普通節(jié)點使用時分多址(time division multiple access，TDMA)協(xié)議進(jìn)行數(shù)據(jù)的傳輸，簇頭節(jié)點會把來自其它節(jié)點的消息進(jìn)行處理后發(fā)送給BS。每一輪重復(fù)該過程。其中在簇頭形成階段，網(wǎng)絡(luò)的閾值T(n)[9]的表達(dá)式如式(4)所示

(4)

式中：p為網(wǎng)絡(luò)所需CH的比例大小，r為網(wǎng)絡(luò)現(xiàn)階運行的輪次。

2.2 改進(jìn)的LEACH算法

針對LEACH算法、文獻(xiàn)[6]中基于LEACH算法優(yōu)化算法的不足，本文在LEACH算法的基礎(chǔ)上，對文獻(xiàn)[6]的算法進(jìn)行了改進(jìn)，改進(jìn)后的算法同LEACH算法一樣分為兩個階段。改進(jìn)后算法的流程如圖3所示。

圖3 改進(jìn)算法的流程

在簇的形成階段，首先考慮到整個系統(tǒng)中節(jié)點的平均能量，平均能量[10]的計算公式如式(5)所示

(5)

式中：Eto表示的是網(wǎng)絡(luò)總的能量。

在簇頭節(jié)點的選擇上，改進(jìn)算法優(yōu)化了簇頭節(jié)點的選取方法，在簇頭節(jié)點的選取函數(shù)中加入了每輪運行中各個節(jié)點的能量剩余情況，改進(jìn)的公式如式(6)所示

(6)

式中：nalive是網(wǎng)絡(luò)系統(tǒng)運行中節(jié)點的存活數(shù)量，Ere是網(wǎng)絡(luò)運行中各個節(jié)點的能量剩余大小，Ebe是網(wǎng)絡(luò)中各個節(jié)點最初的原始能量。

文獻(xiàn)[6]中算法利用加權(quán)思想，使節(jié)點產(chǎn)生了基于節(jié)點能量和密度的權(quán)值來優(yōu)化簇頭節(jié)點的選取，權(quán)值公式如式(7)所示

(7)

式中：Eres是網(wǎng)絡(luò)中節(jié)點的剩余能量大小，E0是節(jié)點的初始能量，nneb是節(jié)點的鄰居節(jié)點數(shù)，Ncul是該簇頭節(jié)點的簇內(nèi)成員數(shù)量，γ1和γ2是權(quán)值影響因子。

根據(jù)上面的權(quán)值公式得到改進(jìn)之后的閾值公式如式(8)所示

(8)

針對文獻(xiàn)[6]中算法引入的加權(quán)值未考慮節(jié)點距離的情況進(jìn)行優(yōu)化。當(dāng)一個節(jié)點被選取成為簇頭節(jié)點之后，如果此時該簇頭節(jié)點的能量剩余仍大于當(dāng)前網(wǎng)絡(luò)系統(tǒng)中的平均能量剩余值，那么該簇頭節(jié)點可再一次被選擇成為頭節(jié)點。此時需要考慮到節(jié)點每輪運行結(jié)束后的能量剩余情況、網(wǎng)絡(luò)運行輪次以及節(jié)點到基站的距離因素，得到改進(jìn)之后的閾值公式如式(9)所示

(9)

式中：Er-re(i) 是每輪運行結(jié)束后總的剩余能量，rre為網(wǎng)絡(luò)運行中剩余的輪數(shù)，其中rre=r-rnow，rnow是當(dāng)前運行的輪次數(shù)，dmax、dmin、dto-BS分別為各個節(jié)點到匯聚節(jié)點的最大、最小距離值、當(dāng)前輪中節(jié)點到匯聚節(jié)點的大小，可以看出剩余能量越多，到匯聚節(jié)點的距離越近，被選取成為簇頭節(jié)點的可能性就越大。

簇頭節(jié)點為集群中各個普通節(jié)點分配信息傳輸?shù)?TDMA 時隙，這樣就能確保各節(jié)點在進(jìn)行數(shù)據(jù)傳輸時不會發(fā)生沖突，此外還允許每個非簇頭節(jié)點在其TDMA時隙未到達(dá)期間保持休眠狀態(tài)，不發(fā)送任何數(shù)據(jù)直至其TDMA時隙的到來，從而減少各個節(jié)點能量的消耗。此刻網(wǎng)絡(luò)的分簇階段完成并且開始進(jìn)行數(shù)據(jù)傳輸階段。

在傳輸數(shù)據(jù)階段，簇頭節(jié)點的能量損失主要有：接收其分組中各個成員節(jié)點數(shù)據(jù)消息的能耗、對各成員節(jié)點的數(shù)據(jù)消息及自身數(shù)據(jù)進(jìn)行融合處理的能耗,以及向匯聚節(jié)點發(fā)送消息的能耗，具體如式(10)所示

(10)

各個簇中普通節(jié)點的能量損失如式(11)所示

(11)

則網(wǎng)絡(luò)的總能耗情況如式(12)所示

(12)

(13)

當(dāng)簇頭節(jié)點選取完成后，其它成員節(jié)點與簇頭節(jié)點進(jìn)行數(shù)據(jù)傳輸需要在簇頭節(jié)點的有效范圍內(nèi)，每個分簇所占面積如式(14)所示

(14)

普通節(jié)點在該區(qū)域內(nèi)傳輸數(shù)據(jù)給簇頭節(jié)點，不會產(chǎn)生簇中節(jié)點分布極度不均勻的情況，普通節(jié)點入簇的有效半徑如式(15)所示

(15)

3 仿真結(jié)果分析

3.1 參數(shù)設(shè)置

為了評估優(yōu)化后算法的優(yōu)勢，利用MATLAB平臺檢驗其有效性。在實驗環(huán)境中我們將100個節(jié)點隨機分布在范圍為(0，0)和(100,100)內(nèi)，一個匯聚節(jié)點的分布位置為(xm,ym)=(50,50)。 我們將最佳簇頭百分比定義為0.05 (p=0.05)， 具體的通信能量參數(shù)配置見表1。

表1 仿真參數(shù)設(shè)置

3.2 結(jié)果分析

本文主要考慮了各個分簇算法的網(wǎng)絡(luò)生命持續(xù)時間、節(jié)點的數(shù)據(jù)傳輸情況、網(wǎng)絡(luò)中節(jié)點的能量剩余情況幾個方面，將改進(jìn)的算法與LEACH算法、文獻(xiàn)[6]的算法進(jìn)行對比。3種算法節(jié)點死亡數(shù)量隨輪次增加的變化情況見表2，算法的生命持續(xù)時間對比如圖4所示。

表2 死亡節(jié)點個數(shù)及對應(yīng)的輪次

圖4 3種算法的生命周期情況

圖4顯示了節(jié)點剩余數(shù)量隨時間增大的變化狀態(tài)。結(jié)合表2可以看出，改進(jìn)后的算法的生命周期較LEACH算法提高了36.4%，較文獻(xiàn)[6]的算法提高了15.8%。LEACH算法的網(wǎng)絡(luò)生存時間較短是因為簇頭隨機選擇的原因，LEACH算法判定節(jié)點在下一輪中是否能選取成為簇頭節(jié)點僅僅依據(jù)該節(jié)點在前面輪次中是否已經(jīng)當(dāng)選過簇頭節(jié)點，若當(dāng)選過，則下一輪中不會再成為簇頭節(jié)點。文獻(xiàn)[6]算法雖然引入了能量密度加權(quán)因子，但是沒有考慮到節(jié)點距離基站的遠(yuǎn)近、網(wǎng)絡(luò)運行的輪次及節(jié)點可重復(fù)當(dāng)選為簇頭節(jié)點的情況。而改進(jìn)后的算法不僅考慮到節(jié)點的剩余能量，還加入節(jié)點到基站距離的考量，以及節(jié)點傳輸數(shù)據(jù)的有效范圍等因素，有效改善了節(jié)點分布不合理的問題。經(jīng)過對比，改進(jìn)后的算法優(yōu)化了簇頭節(jié)點的選取，增加了網(wǎng)絡(luò)生存時間長度。

3種算法節(jié)點數(shù)據(jù)消息發(fā)送到匯聚節(jié)點的情況如圖5所示。

圖5 3種算法的傳輸數(shù)據(jù)情況

圖5是3種算法隨著時間的增長，網(wǎng)絡(luò)中匯聚節(jié)點接收數(shù)據(jù)消息的情況。可以看出，改進(jìn)后的算法節(jié)點向匯聚節(jié)點傳輸?shù)臄?shù)據(jù)包大小約為66 559數(shù)據(jù)包，文獻(xiàn)[6]算法節(jié)點向匯聚節(jié)點傳輸?shù)臄?shù)據(jù)包大小約為35 893，LEACH算法節(jié)點向匯聚節(jié)點傳輸?shù)臄?shù)據(jù)包大小約為7560。文獻(xiàn)[6]算法匯聚節(jié)點接收數(shù)據(jù)包大小是LEACH算法的4.7倍，改進(jìn)后算法匯聚節(jié)點接收數(shù)據(jù)包大小是文獻(xiàn)[6]算法的1.8倍。LEACH算法、文獻(xiàn)[6]算法向匯聚節(jié)點傳輸?shù)臄?shù)據(jù)包數(shù)量較少，是因為未考慮網(wǎng)絡(luò)中節(jié)點距離匯聚節(jié)點的遠(yuǎn)近，導(dǎo)致分簇中節(jié)點入簇可能不在有效范圍內(nèi)的情況，從而影響了匯聚節(jié)點接收數(shù)據(jù)消息的大小。改進(jìn)的算法優(yōu)化了簇頭節(jié)點的選取，不僅加入了各個節(jié)點到匯聚節(jié)點的距離大小考量，還考慮到節(jié)點當(dāng)選過簇頭節(jié)點后，可再一次被選為簇頭的情況，繼而最大化的提高節(jié)點的利用率，提高了匯聚節(jié)點接收數(shù)據(jù)包的大小。

3種算法節(jié)點剩余能量情況如圖6所示。

圖6 3種算法節(jié)點剩余能量情況

圖6是網(wǎng)絡(luò)中節(jié)點的剩余能量隨著時間增長的對比情況，與圖4中存活節(jié)點數(shù)量直接相關(guān)。改進(jìn)后算法節(jié)點能量在第1570輪耗盡，文獻(xiàn)[6]算法在1355輪耗盡，LEACH算法在1151輪耗盡。LEACH算法耗能大是因為簇頭節(jié)點選取隨機、節(jié)點分布不合理、沒有考慮節(jié)點到匯聚節(jié)點距離，節(jié)點剩余能量的原因等。節(jié)點的不合理分布容易造成網(wǎng)絡(luò)中出現(xiàn)極大簇、極小簇的情況，從而導(dǎo)致網(wǎng)絡(luò)中節(jié)點能耗不均勻的問題。文獻(xiàn)[6]算法沒有考慮各個節(jié)點到匯聚節(jié)點的距離大小，如果選取的簇頭節(jié)點距離匯聚節(jié)點較遠(yuǎn)，會加劇網(wǎng)絡(luò)中總能耗的增加。改進(jìn)的算法增加了節(jié)點的剩余能量，節(jié)點距離匯聚節(jié)點遠(yuǎn)近的考量來優(yōu)化簇頭節(jié)點的選取，不會產(chǎn)生能量剩余少的節(jié)點被選為簇頭節(jié)點的情況，此外還考慮到簇頭節(jié)點接收普通節(jié)點數(shù)據(jù)消息的有效范圍，避免距離簇頭節(jié)點遠(yuǎn)的節(jié)點向該簇頭節(jié)點傳輸數(shù)據(jù)時能耗快速耗盡的問題。可以看出進(jìn)行改進(jìn)后算法節(jié)點總的能量剩余趨勢優(yōu)于文獻(xiàn)[6]，體現(xiàn)出改進(jìn)算法有效均衡了網(wǎng)絡(luò)能耗。

4 結(jié)束語

針對文獻(xiàn)[6]中LEACH優(yōu)化算法的不足，本文在LEACH分簇算法初始化階段，簇頭節(jié)點選擇隨機、成員節(jié)點入簇不合理的基礎(chǔ)上，提出了一種改進(jìn)的LEACH算法。改進(jìn)算法先優(yōu)化了簇頭節(jié)點的選擇概率，加入了節(jié)點在每輪運行結(jié)束后網(wǎng)絡(luò)的平均剩余能量、簇頭節(jié)點接收普通節(jié)點消息的有效范圍、網(wǎng)絡(luò)運行的輪次以及節(jié)點到匯聚節(jié)點的距離因素；此外還考慮到簇頭節(jié)點是否可以重復(fù)當(dāng)選為頭節(jié)點的情況來提高網(wǎng)絡(luò)中節(jié)點的利用率。實驗結(jié)果表明，改進(jìn)后的算法有明顯的性能優(yōu)勢。