一種基于LEACH 協(xié)議改進(jìn)的簇間多跳路由協(xié)議

趙　靜，呂紅芳，渠帥軍

(上海電機學(xué)院 電氣學(xué)院， 上海 201306)

?

一種基于LEACH 協(xié)議改進(jìn)的簇間多跳路由協(xié)議

趙靜，呂紅芳，渠帥軍

(上海電機學(xué)院 電氣學(xué)院， 上海 201306)

針對無線傳感器網(wǎng)絡(luò)(WSN)路由協(xié)議中能量消耗不均衡問題，研究了一種基于LEACH協(xié)議改進(jìn)的簇間多跳路由協(xié)議LEACH-D算法。在分簇過程中，簇頭選擇增加了節(jié)點剩余能量和節(jié)點的“度”的因素；在簇間通信階段，簇頭節(jié)點按照Dijkstra算法形成的簇頭間的最優(yōu)路徑以多跳的方式將信息傳遞給sink節(jié)點，其中權(quán)值綜合考慮了下一跳簇頭的能量和距離因素。通過對LEACH-D、LEACH-C和LEACH算法的網(wǎng)絡(luò)剩余能量和網(wǎng)絡(luò)生存時間進(jìn)行仿真比較，結(jié)果表明LEACH-D算法可有效均衡網(wǎng)絡(luò)的能量消耗，延長WSN的生命周期。

無線傳感器網(wǎng)絡(luò)； LEACH； 度； Dijkstra算法

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network， WSN)是集信息采集、信息傳輸、信息處理于一體的綜合智能信息處理系統(tǒng)，被廣泛用于農(nóng)業(yè)、軍事、醫(yī)療、環(huán)境監(jiān)測等領(lǐng)域[1]。WSN中，節(jié)點一般采用電池供電，由于其一般都在人員很難接近的場所，能源不能及時供給；另外，目前可再生能源技術(shù)的應(yīng)用還不夠成熟[2]，故節(jié)能一直是WSN研究的重點之一。對于WSN中路由協(xié)議設(shè)計而言，一直都以均衡網(wǎng)絡(luò)能量損耗、延長網(wǎng)絡(luò)生存時間作為WSN路由協(xié)議設(shè)計的重要性能指標(biāo)。目前，WSN路由協(xié)議分為平面路由和分簇路由兩種[1]。平面路由不適合大規(guī)模網(wǎng)路應(yīng)用，為了能在運行中維持較大的路由表，對分簇路由做了一定改進(jìn)。LEACH路由協(xié)議是第一個提出分簇路由的協(xié)議，此后又做了許多改進(jìn)。文獻(xiàn)[3]中提出了一種基于LEACH的改進(jìn)節(jié)能路由協(xié)議LEACH-PSOC，通過對簇頭選擇算法的改進(jìn)，利用粒子群算法良好的收斂性和全局優(yōu)化能力，將整個網(wǎng)絡(luò)區(qū)域合理地分割成多個子區(qū)域，使網(wǎng)絡(luò)能量均衡消耗，也減少了能量損耗，延長了網(wǎng)絡(luò)的生存時間。文獻(xiàn)[4]中提出一種改進(jìn)的Q-LEACH路由協(xié)議，通過非均勻分簇以及自適應(yīng)競爭半徑的應(yīng)用，有效地減少了能量消耗，通過Q-LEACH路由協(xié)議的子區(qū)間劃分機制，改善了簇首間的多跳通信，更加減少了能量消耗，生命周期得到延長。文獻(xiàn)[5]中針對LEACH協(xié)議中簇頭選擇不合理、多個簇頭與基站遠(yuǎn)距離通信能量消耗過多的問題，運用PEGASIS協(xié)議中節(jié)點成鏈思想構(gòu)造了簇頭間的多跳路由，最后由鏈上擔(dān)任Leader的節(jié)點完成了與基站的數(shù)據(jù)通信，均衡了能量消耗，延長了網(wǎng)絡(luò)生存時間。文獻(xiàn)[6]中提出一種基于穩(wěn)定性的S-HEED分簇算法，以穩(wěn)定性作為參數(shù)來決定節(jié)點的所屬簇，針對節(jié)點移動性帶來的簇內(nèi)節(jié)點和簇頭能量消耗過高問題，減少了簇頭的消耗，延長了網(wǎng)絡(luò)壽命。文獻(xiàn)[7]中提出了一種基于能量均衡的分簇多跳路由協(xié)議EB-LEACH，通過增設(shè)中繼節(jié)點協(xié)助數(shù)據(jù)轉(zhuǎn)發(fā)、分擔(dān)簇首節(jié)點工作的方式來節(jié)省節(jié)點能量，延長了整個網(wǎng)絡(luò)的生命周期。文獻(xiàn)[8]中提出了一種基于LEACH協(xié)議改進(jìn)的簇間多跳路由協(xié)議，通過引入能量因子和距離因子修正了LEACH協(xié)議的閾值函數(shù)；在簇間通信過程中，簇頭節(jié)點與sink節(jié)點之間采用多跳通信方式，簇頭與簇頭之間形成一條通向sink節(jié)點的優(yōu)化路徑，延長了網(wǎng)絡(luò)的生存時間。

本文在已有文獻(xiàn)研究的基礎(chǔ)上，研究了一種基于LEACH協(xié)議改進(jìn)的簇間多跳路由協(xié)議LEACH-D算法。該算法修正了簇頭選擇的閾值函數(shù)，增加了節(jié)點剩余能量、節(jié)點“度”的考慮；簇間通信采取多跳形式，簇頭按照Dijkstra算法形成的最優(yōu)路徑來選擇傳輸路徑，權(quán)值考慮了下一跳簇頭的距離和能量因素。通過仿真比較，表明該算法能均衡網(wǎng)絡(luò)的能量消耗，延長網(wǎng)絡(luò)的生存時間。

1　LEACH協(xié)議分析

LEACH協(xié)議運行流程以輪為周期[9-10]，分為簇結(jié)構(gòu)形成和穩(wěn)定工作兩個階段。簇結(jié)構(gòu)形成階段，全部節(jié)點按簇劃分，節(jié)點當(dāng)選簇頭是隨機的。簇頭選舉過程如下：每個節(jié)點隨機生成1個在[0，1]間的數(shù)，若該節(jié)點n生成的隨機值小于閾值T(n)，該節(jié)點為簇頭節(jié)點；否則，為非簇頭節(jié)點，

(1)

式中，p為當(dāng)選簇頭的節(jié)點數(shù)和所有節(jié)點數(shù)的比值；G為在剩余1/p輪中沒有當(dāng)選為簇頭節(jié)點的節(jié)點集；r為協(xié)議的輪數(shù)。

節(jié)點當(dāng)選為簇頭節(jié)點后，在簇內(nèi)廣播信息(信息包括簇頭信息和簇首ID等)，宣布自己當(dāng)選為簇首。非簇首節(jié)點根據(jù)收到信號的強弱，加入信號強的簇中。簇頭節(jié)點根據(jù)收到的加入簇請求的節(jié)點數(shù)生成相應(yīng)的時分多址(Time Division Multiple Access， TDMA)時隙表，簇內(nèi)的信息就按此TDMA時隙表傳遞，以避免信息堵塞。簇頭節(jié)點收到簇內(nèi)的數(shù)據(jù)，融合后直接發(fā)送到sink節(jié)點，每輪回一次，整個網(wǎng)絡(luò)就重新分簇。

LEACH-D算法和LEACH算法的數(shù)據(jù)傳遞都采用一階無線電模型[11]，如圖1所示。圖中，Etx和Erx分別為發(fā)射機和接受機處理數(shù)據(jù)所損耗的能量；Eelec為電路處理單位比特信號所損耗的能量，J/bit；εamp為放大器的放大系數(shù)。

圖1　無線電模型Fig.1　Radio model diagram

當(dāng)兩個簇頭的間距為d時，發(fā)射端發(fā)送k bit信息所損耗的能量為

(2)

接受端的能量損耗為

Erx=Etx(k)=k Eelec

(3)

此外，簇頭節(jié)點對信號進(jìn)行融合也要消耗一定的的能量EDA[12]。

2　改進(jìn)的分簇算法LEACH-D

2.1成簇過程

LEACH算法運行中，簇頭節(jié)點負(fù)責(zé)融合簇內(nèi)節(jié)點的信息;融合后還需要傳遞給sink節(jié)點，故選擇合適的簇頭節(jié)點對減少網(wǎng)絡(luò)損耗、提高傳遞信息的效率、延長網(wǎng)絡(luò)生命周期非常必要。但LEACH算法采用隨機選取簇頭節(jié)點的方式，導(dǎo)致簇頭分布不均勻和某些節(jié)點過早死亡，縮短了網(wǎng)絡(luò)生命周期。為此，本文研究的LEACH-D算法在簇頭選擇時考慮了節(jié)點的剩余能量和節(jié)點的“度”(以節(jié)點為圓心、Tr為半徑范圍內(nèi)所包含的節(jié)點數(shù))，使選出的節(jié)點不僅有較高的剩余能量，且節(jié)點更趨于簇中心。修正后，

(4)

式中，T′(n)的調(diào)節(jié)函數(shù)為

(5)

式中，α和β為調(diào)節(jié)因子；Emax(r)為第r輪節(jié)點剩余能量的最大值；Ei(r)為第r輪節(jié)點i的剩余能量值;N(i)為節(jié)點i在半徑Tr范圍的節(jié)點數(shù);Nmax(i)為節(jié)點的“度”的最大值。從式(5)可見，當(dāng)剩余能量越大，節(jié)點的“度”越大，閾值T′(n)也相應(yīng)變大，節(jié)點當(dāng)選為簇頭的概率也會增加；反之，T′(n)減小，節(jié)點當(dāng)選簇頭的概率也會減小。

2.2簇間通信

簇頭融合簇內(nèi)信息后，采取直接傳輸方式傳遞給sink節(jié)點。這樣的傳遞方式使距離sink節(jié)點遠(yuǎn)的簇頭節(jié)點的能量損耗加大，過大的傳輸損耗將導(dǎo)致節(jié)點過早死亡，縮短網(wǎng)絡(luò)生存周期。LEACH-D算法采取多跳的方式傳遞數(shù)據(jù)。協(xié)作簇頭的選取，即路徑選擇，按照Dijkstra算法形成最優(yōu)路徑。Dijkstra算法是典型最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑，其特點是以起始點為中心向外逐層擴展，直到擴展到終點為止[12-13]。

設(shè)Q=(V，E)是一個帶權(quán)有向圖，假設(shè)簇頭節(jié)點和sink節(jié)點含有n個節(jié)點，用V={v0，v1，v2，…，vn}(j=0，1，2，…，n)表示。將集合V分成兩組：第1組為已求出最優(yōu)路徑的頂點集合，用S表示。初始時，S中只有一個源點，即sink節(jié)點，以后每求得一條最優(yōu)路徑，就將其加入到集合S中，直到全部簇頭節(jié)點都加入到S中，算法即結(jié)束。第2組為其余未確定最短路徑的簇頭集合，用U表示，按最小路徑權(quán)值的遞增次序依次將第2組的簇頭節(jié)點添加到S中，期間，總保持v0到S中其他節(jié)點的權(quán)值都不大于從v0到U中任何簇頭的最短權(quán)值。LEACH-D算法就是由sink節(jié)點出發(fā)尋找到各簇頭節(jié)點的最小權(quán)值和的方法。

設(shè)每輪簇頭數(shù)與sink節(jié)點數(shù)之和為NCH，建立簇頭間的路徑權(quán)矩陣

(6)

式中，a(i，j)為簇頭節(jié)點i到簇頭節(jié)點j的權(quán)，Dijkstra 算法中表示點與點之間的距離。

很顯然，簇頭在選擇下一跳簇頭時，不僅要考慮距離，還要兼顧到兩方面：① 下一跳簇頭的能量；② 與下一跳簇頭間的距離，即

(7)

式中，

a(i，j)=Md(i，j)+N/E(j)

(8)

式中，M、N為權(quán)值函數(shù)的調(diào)節(jié)因子，且M+N=1；d(i，j)為簇頭節(jié)點i到簇頭節(jié)點j的距離；E(j)為簇頭節(jié)點j的剩余能量值。由此可見，當(dāng)i≠j或j≠i時，A(i，j)和d(i，j)成正比，與E(j)成反比。因此，M、N的取值影響了權(quán)值函數(shù)的大小，導(dǎo)致最佳路徑的選取有所不同。

本文用少量的簇頭節(jié)點來說明算法具體步驟，網(wǎng)絡(luò)節(jié)點權(quán)向圖如圖2所示。

圖2　網(wǎng)絡(luò)結(jié)構(gòu)權(quán)向圖Fig.2　Right diagram of network structure

(1)初始時，S只包含源點sink節(jié)點，即S={v0}，v0的權(quán)值為0。U包含除v0外的其他簇頭節(jié)點，U={v1，v2，v3}，U中簇頭節(jié)點與v0的距離為兩點之間的權(quán)值(若v0與U中簇頭節(jié)點能連通)。由簇頭間權(quán)的定義可知，由于2個簇頭方向不同，權(quán)也不同，故增加了算法的復(fù)雜度。

(2)從U中選取一個距離v0最小的簇頭節(jié)點v1，將v1加入到S中，路徑權(quán)為3，故v1的權(quán)值為3。

(3)將v1作為中間點，修改U中各簇頭節(jié)點的距離，即v1到v2、v3的權(quán)，則有U={1，5}；若從源點v0到頂點v3的距離(經(jīng)過簇頭v1)比原權(quán)值(v0到v3)短，則修改簇頭節(jié)點v3的權(quán)值，修改后的權(quán)值是頂點v1的權(quán)值加上v1到v3邊的權(quán)，把節(jié)點v3放入集合S中。

(4)重復(fù)步驟(2)、(3)直到所有頂點都包含在S中。按照算法運行得到的最優(yōu)路徑網(wǎng)絡(luò)權(quán)向圖如圖3所示。

圖3　最優(yōu)路徑網(wǎng)絡(luò)權(quán)向圖Fig.3　Right diagram of optimal path of the network

當(dāng)sink點與各簇頭間的最優(yōu)路徑確定后，按照路徑(v0，v1，v3)以反向、多跳的形式傳輸信息至sink節(jié)點，此時發(fā)送節(jié)點為v3。對v3而言，在簇頭節(jié)點間的信息傳遞階段，其能量損耗包括信息的發(fā)送損耗和傳遞損耗，而中間的簇頭節(jié)點能量損耗為接受和發(fā)送信息的能量損耗與傳輸信息的能量損耗之和。

3　仿真實驗及性能分析

本文利用MATLAB軟件，先通過仿真實驗選取最佳的α、β和M、N取值，以分析LEACH-D分簇算法的性能。仿真環(huán)境設(shè)置如下[14-15]：100個點隨機部署在200m×200m的區(qū)域內(nèi)，sink節(jié)點坐標(biāo)安置于中心位置(100，100)。仿真參數(shù)如表1所示。

表1　仿真參數(shù)

(1)調(diào)節(jié)因子(α，β)取值。實驗通過設(shè)置不同的(α，β)來比較LEACH-D算法的不同生命周期曲線，得出最佳的(α，β)取值。

本文對(α，β)的取值采取經(jīng)驗取值法，即針對α>β、α<β和α=β這3種情況進(jìn)行了大量的實驗比較，最后得到當(dāng)(α，β)為(0.9，0.1)、(0.5，0.5)、(0.3，0.7)時，分別在它們所在的取值范圍內(nèi)最優(yōu)。圖4給出了(α，β)為(0.9，0.1)、(0.5，0.5)、(0.3，0.7)時，LEACH-D分簇算法的生命周期曲線比較。

圖4　不同(α，β)取值下，LEACH-D分簇算法的生命周期曲線比較Fig.4　Comparison of life-cycle curves of LEACH-D clusteringalgorithm with different values of α and β

由圖4可見，當(dāng)(α，β)=(0.9，0.1)時，LEACH-D分簇算法的生命周期最大，其次是(α，β)=(0.5，0.5)，當(dāng)(α，β)=(0.3，0.7)時，生命周期最小。這說明當(dāng)α>β時，LEACH-D分簇算法的生命周期曲線較α<β、α=β時都要理想。同時，也最終確定(α，β)的最佳取值為(0.9，0.1)。

(2)調(diào)節(jié)因子(M，N)取值。由于不同的(M，N)取值影響了最優(yōu)路徑的選取，進(jìn)而對網(wǎng)絡(luò)的能量損耗產(chǎn)生影響，使LEACH-D分簇算法的生命周期也發(fā)生改變。本文同樣對(M，N)的取值采取經(jīng)驗取值法，即針對M>N、M

圖5　不同(M，N)取值下，LEACH-D分簇算法的生命周期曲線比較Fig.5　Comparison of life-cycle curves of LEACH-D clusteringalgorithm with different values of M and N

由圖5可見，當(dāng)(M，N)=(0.8，0.2)時，LEACH-D分簇算法的生命周期最大，其次是(M，N)=(0.5，0.5)，當(dāng)(M，N)=(0.3，0.7)時，生命周期最小。這說明當(dāng)M>N時，LEACH-D分簇算法的生命周期曲線較M

(3)LEACH-D、LEACH-C和LEACH算法性能對比。利用表1的數(shù)據(jù)分別對LEACH-D算法、LEACH算法以及LEACH-C算法[12]進(jìn)行性能比較，其中，LEACH-D算法選取最佳調(diào)節(jié)因子(M，N)=(0.8，0.2)、(α，β)=(0.9，0.1)。圖6給出了LEACH-D、LEACH-C和LEACH 3種算法的生命周期曲線比較。由圖可見，當(dāng)算法運行至20輪左右，3種算法的存活節(jié)點數(shù)開始逐漸減少，其中，LEACH算法存活的節(jié)點數(shù)最少，LEACH-C算法次之，LEACH-D算法存活的節(jié)點數(shù)最多；且由圖可見，LEACH-D算法的生命周期為36，LEACH算法的生命周期為18，LEACH-D算法的生命周期相比于LEACH算法提高了1倍，較LEACH-C算法提高了33.3%。

圖6　3種算法的生命周期曲線比較Fig.6　Comparison of life cycles of three kind of algorithms

圖7給出了3種算法每輪節(jié)點的剩余能量比較。由圖可見，LEACH-D算法的剩余能量最大，其次是LEACH-C算法，LEACH算法的剩余能量最小。這是由于LEACH-D算法在選擇簇頭時，選擇了靠近簇中心位置的簇頭，使剩余能量更大的節(jié)點當(dāng)選為簇頭，減少了簇內(nèi)的通信消耗，也均衡了能量損耗；同時，在簇間通信過程中，按照Dijkstra算法形成的最優(yōu)多跳路徑，不僅考慮到了距離因素，而且兼顧到了下一跳的簇頭能量，從而減少了總能量損耗，也均衡了各簇頭的能量損耗，延長了網(wǎng)絡(luò)的生命周期。

圖7　每輪節(jié)點剩余能量總和比較Fig.7　Total remaining energy consumption of all nodes in each round

3　結(jié)　語

本文在研究LEACH協(xié)議的基礎(chǔ)上，對算法進(jìn)行了改進(jìn)，形成LEACH-D分簇算法。該算法對簇頭的選擇閾值函數(shù)進(jìn)行了修正，增加了剩余能量和節(jié)點“度”的因素，使得剩余能量大、周圍節(jié)點數(shù)多的節(jié)點更加容易當(dāng)選為簇頭節(jié)點，均衡了網(wǎng)絡(luò)能量消耗，減少了簇內(nèi)通信開銷；并且，在簇間通信過程中，簇頭節(jié)點采取簇間多跳的方式傳遞數(shù)據(jù)，按照Dijkstra算法形成的最優(yōu)多跳路徑，考慮了下一跳簇頭節(jié)點的距離以及剩余能量。仿真結(jié)果表明，LEACH-D算法可大幅度減少單跳能耗，均衡了能量損耗，延長了網(wǎng)絡(luò)生存周期。

[1]葉繼華，王文，江愛文.一種基于LEACH的異構(gòu)WSN能量均衡成簇協(xié)議[J].傳感技術(shù)學(xué)報，2015，28(12)：1853-1860.

[2]NAYL A A，ALY H F.Solvent extraction of V(Ⅴ)and Cr(Ⅲ)from acidic leach liquors of ilmenite using aliquat 336 [J].Transactions of Nonferrous Metals Society of China，2015，25(12)：4183-4191.

[3]陳曉娟,王卓,吳潔.一種基于LEACH的改進(jìn) WSN 路由算法[J].傳感技術(shù)學(xué)報，2013，26(1)：116-121.

[4]王東東，崔寶同.基于非均勻分簇多跳通信的改進(jìn)Q-Leach研究[J].計算機技術(shù)與發(fā)展，2015，25(2)：212-215，220.

[5]胡峰松，肖球.一種基于 LEACH的能耗均衡多跳路由算法[J].小型微型計算機系統(tǒng)，2014，35(1)：70-73.

[6]楊夢寧，楊丹，黃超.無線傳感器網(wǎng)絡(luò)中改進(jìn)的HEED分簇算法[J].重慶大學(xué)學(xué)報，2012，35(8)：101-106.

[7]周方，李臘元，戴佳佳，等.一種基于能量均衡的分簇多跳路由協(xié)議EB-LEACH[J].中北大學(xué)學(xué)報(自然科學(xué)版)，2013，34(4)：413-418.

[8]陳炳才，么華卓，楊明川，等.一種基于LEACH協(xié)議改進(jìn)的簇間多跳路由協(xié)議[J].傳感器技術(shù)學(xué)報，2014，27(3)：373-377.

[9]胡艷華，張建軍.LEACH 協(xié)議的簇頭多跳(LEACH-M)改進(jìn)算法[J].計算機工程與應(yīng)用，2009，45(34)：107-109.

[10]蔣華，劉偉強，王鑫.無線傳感器網(wǎng)絡(luò)中Leach-C路由協(xié)議的研究與改進(jìn)[J].微電子學(xué)與計算機，2014，31(12)：43-47.

[11]楊永健，賈冰，王杰.無線傳感器網(wǎng)絡(luò)中LEACH協(xié)議的改進(jìn)[J].北京郵電大學(xué)學(xué)報，2013，36(1)：105-109.

[12]王樹西，李安渝.Dijkstra算法中的多鄰接點與多條最短路徑問題[J].計算機科學(xué)，2014，41(6)：217-224.

[13]劉春年，鄧青菁.應(yīng)急決策信息系統(tǒng)最優(yōu)路徑研究：基于路阻函數(shù)理論及Dijkstra算法[J].災(zāi)害學(xué)，2014，29(3)：18-23.

[14]馬建樂，楊軍.基于位置和剩余能量的局部集中式LEACH算法研究[J].傳感技術(shù)學(xué)報，2013，26(3)：1147-1151.

[15]呂濤，朱清新，張路橋.一種基于LEACH協(xié)議的改進(jìn)算法[J].電子學(xué)報，2011，39(6)：1405-1409.

Improved Inter-Cluster Multi-Hop Routing Protocol Based on LEACH Protocol

ZHAO Jing，Lü Hongfang，QU Shuaijun

(School of Electrical Engineering， Shanghai Dianji University， Shanghai 201306， China)

To solve the problem of imbalance in energy consumption of routing protocols for wireless sensor networks(WSN)， an improved multi-hop routing protocol LEACH-D algorithm is proposed based on the LEACH algorithm.In clustering， the algorithm takes into account a factor of “degree” and the residual energy of nodes.In inter-cluster communications， cluster head nodes pass information to the sink through an optimal path according to the Dijkstra algorithm.By simulation， LEACH-D， LEACH-C and LEACH algorithms are compared in terms of network lifetime and residual energy of all nodes.The results show that the LEACH-D protocol can effectively keep balance in network energy consumption， and prolong life span of WSN.The weight function of the algorithm between cluster head nodes is modified by considering energy and the distance.

wireless sensor network(WSN); LEACH protocol; degree; Dijkstra algorithm

2016-06-25

趙靜(1990-)，女，碩士生，主要研究方向為無線傳感器網(wǎng)絡(luò)通信協(xié)作，E-mail：2643894096@qq.com

2095-0020(2016)04-0221-06

TP 212.9

A