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

馬紅艷，鄒學(xué)玉

(長江大學(xué)電子信息學(xué)院，湖北 荊州 430023)

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

馬紅艷，鄒學(xué)玉

(長江大學(xué)電子信息學(xué)院，湖北 荊州 430023)

無線傳感器網(wǎng)絡(luò)是一種能源受限網(wǎng)絡(luò)，因而降低能耗并提高網(wǎng)絡(luò)生存周期成為重要的研究目標(biāo)。以分層路由協(xié)議LEACH為研究基礎(chǔ)，針對(duì)其不足，在簇首選舉、簇首對(duì)Sink節(jié)點(diǎn)的通信方式2方面進(jìn)行改進(jìn)，并利用 OPNET對(duì)LEACH算法及其改進(jìn)算法進(jìn)行仿真試驗(yàn)。結(jié)果表明，改進(jìn)算法有利于提高網(wǎng)絡(luò)性能，明顯延長網(wǎng)絡(luò)生存時(shí)間。

無線傳感器網(wǎng)絡(luò)；分層路由協(xié)議；LEACH協(xié)議算法；網(wǎng)絡(luò)生存時(shí)間

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSN)是由微電子機(jī)械系統(tǒng)、計(jì)算機(jī)、通信、自動(dòng)控制和人工智能等技術(shù)發(fā)展起來的一種新型測(cè)控網(wǎng)絡(luò)，其具有自組織、自治、自適應(yīng)等智能屬性，在軍事、醫(yī)療監(jiān)測(cè)、空間探索等領(lǐng)域有廣泛用途[1]。無線傳感器網(wǎng)絡(luò)路由協(xié)議主要分為平面路由協(xié)議和分層路由協(xié)議。由于平面路由協(xié)議中網(wǎng)絡(luò)內(nèi)各節(jié)點(diǎn)功能地位相同，沒有引入管理分層機(jī)制，其可擴(kuò)張性小，缺乏對(duì)通信資源的優(yōu)化管理，限制了網(wǎng)絡(luò)規(guī)模，而分層路由協(xié)議在一定程度上可解決上述問題[2]。低功耗自適應(yīng)聚類路由協(xié)議LEACH是比較典型的分層路由算法，但其對(duì)簇首的選擇具有隨機(jī)性，而簇首對(duì)Sink節(jié)點(diǎn)采用單跳傳輸方式不能有效提高網(wǎng)絡(luò)生存時(shí)間[3]。為此，筆者對(duì)(Low Energy Adaptive Clustering Hierarchy，LEACH)算法進(jìn)行改進(jìn)以降低無線傳感器網(wǎng)絡(luò)功耗來延長其生命周期。

1 LEACH算法

1.1LEACH算法原理

圖1 分簇路由協(xié)議的數(shù)據(jù)傳輸流程簡圖

無線傳感器網(wǎng)絡(luò)的路由協(xié)議中，通常有不帶分簇的單跳路由和多跳路由協(xié)議、帶分簇的單跳路由和多跳路由協(xié)議[4-5]。在分簇路由通信協(xié)議中數(shù)據(jù)常按“輪”進(jìn)行，每1輪可分2階段，即成簇階段和數(shù)據(jù)傳輸階段。圖1所示為LEACH分簇路由協(xié)議的簡單數(shù)據(jù)傳輸時(shí)間流程[6]。

在數(shù)據(jù)傳輸階段，簇首在1幀內(nèi)收集簇內(nèi)所有活動(dòng)節(jié)點(diǎn)的監(jiān)測(cè)數(shù)據(jù)，經(jīng)簇內(nèi)處理后轉(zhuǎn)發(fā)至BS節(jié)點(diǎn)，上述過程可重復(fù)多次，但若重復(fù)次數(shù)過多，通信協(xié)議將由動(dòng)態(tài)分簇路由退化為靜態(tài)分簇路由，易于導(dǎo)致簇首節(jié)點(diǎn)能量過度消耗而死亡，因而在每1輪內(nèi)，簇首一般工作1～2個(gè)幀。

在LEACH的成簇階段，簇首的選舉方法是每個(gè)傳感器節(jié)點(diǎn)隨機(jī)選擇0～1之間的一個(gè)值，如果選擇的值小于某個(gè)閾值T(n),那么該節(jié)點(diǎn)就成為簇首節(jié)點(diǎn)。T(n)的計(jì)算公式如下：

(1)

式中，p為網(wǎng)絡(luò)中簇首數(shù)量與節(jié)點(diǎn)總數(shù)的百分比；r為當(dāng)前選舉的輪數(shù)；G為最近1/p輪不是簇首的節(jié)點(diǎn)集。

選定簇首節(jié)點(diǎn)后，通過廣播告知整個(gè)網(wǎng)絡(luò)。網(wǎng)絡(luò)中的其他節(jié)點(diǎn)根據(jù)接收信號(hào)的強(qiáng)弱決定從屬哪個(gè)簇，并通知相應(yīng)的簇首節(jié)點(diǎn)，完成簇的建立。最后，簇首節(jié)點(diǎn)采用TDMA方法為簇中每個(gè)節(jié)點(diǎn)分配向其傳送數(shù)據(jù)的時(shí)間片。

在 LEACH的傳輸階段，傳感器節(jié)點(diǎn)將采集到的數(shù)據(jù)傳送到簇首節(jié)點(diǎn)。簇首節(jié)點(diǎn)對(duì)簇中所有節(jié)點(diǎn)采集的數(shù)據(jù)進(jìn)行信息融合后再傳送給匯聚點(diǎn)，這是一種減小通信業(yè)務(wù)的合理模式。穩(wěn)定階段持續(xù)一段時(shí)間后，網(wǎng)絡(luò)重新進(jìn)入簇的建立階段，進(jìn)行下一回合的簇重構(gòu)，如此不斷循環(huán)。每個(gè)簇采用不同的CDMA代碼進(jìn)行通信來減少其他簇內(nèi)節(jié)點(diǎn)的干擾。

1.2LEACH協(xié)議的網(wǎng)絡(luò)模型及數(shù)據(jù)傳輸

圖2 LEACH協(xié)議及改進(jìn)后的數(shù)據(jù)傳輸圖

LEACH協(xié)議的網(wǎng)絡(luò)模型存在如下特點(diǎn)：①網(wǎng)絡(luò)中有固定基站(sink節(jié)點(diǎn)),其具有充足的能源，故研究中不考慮其能耗，且具傳感器節(jié)點(diǎn)均較遠(yuǎn)。②網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)同構(gòu)并具有相等的有限起始能量。③節(jié)點(diǎn)處于靜止?fàn)顟B(tài)且總有數(shù)據(jù)需要傳輸。④節(jié)點(diǎn)能改變發(fā)射功率并感知其剩余節(jié)點(diǎn)能量。

LEACH協(xié)議數(shù)據(jù)傳輸如圖2(a)所示。由圖2(a)可知，從圖簇內(nèi)節(jié)點(diǎn)通過一跳通信將數(shù)據(jù)傳送給簇首，簇首也通過一跳通信將聚合后的數(shù)據(jù)傳送給sink節(jié)點(diǎn)。

1.3LEACH算法的不足

LEACH以循環(huán)的方式隨機(jī)選取簇首，將整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)傳感器節(jié)點(diǎn)中，從而降低能源消耗，提高網(wǎng)絡(luò)整體生存時(shí)間。由于冗余數(shù)據(jù)被大量消除，因而在能耗方面有較好的性能。但LEACH仍有如下不足之處：①LEACH算法是由網(wǎng)絡(luò)中的節(jié)點(diǎn)自組織地形成簇，簇首是隨機(jī)產(chǎn)生的。由于簇首的選擇未考慮節(jié)點(diǎn)的剩余能量，周圍鄰節(jié)點(diǎn)數(shù)及已經(jīng)擔(dān)任過簇首的次數(shù)會(huì)加重簇首負(fù)擔(dān)，使能耗不均。節(jié)點(diǎn)做簇首次數(shù)過多時(shí)，不但自身能耗大，而且會(huì)使離自身較遠(yuǎn)的節(jié)點(diǎn)消耗較多能量，不利于節(jié)點(diǎn)能量的均衡和網(wǎng)絡(luò)壽命的延長。②簇首在傳輸數(shù)據(jù)時(shí)采用單跳傳輸方式，直接將數(shù)據(jù)包傳送給sink節(jié)點(diǎn)，距離sink較遠(yuǎn)的簇首因此會(huì)消耗較大能量，部分簇首會(huì)過早死亡。

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

針對(duì)LEACH算法的不足，可以在簇首選擇及簇間數(shù)據(jù)傳輸2方面進(jìn)行改進(jìn)(見圖2(b))，以平衡總的能量消耗來延長網(wǎng)絡(luò)生存壽命。

2.1簇首的選擇

由于LEACH的簇首競(jìng)爭(zhēng)門限引起了區(qū)域性能量消耗不均衡等問題，因而可以充分考慮節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)臨近數(shù)目(通信半徑內(nèi)節(jié)點(diǎn))及節(jié)點(diǎn)有未充當(dāng)簇首的次數(shù)，根據(jù)文獻(xiàn)[7]，將式(1)改進(jìn)如下：

(2)

式中，Ecurrent表示節(jié)點(diǎn)的當(dāng)前能量；Emax表示節(jié)點(diǎn)的初始能量；Nx表示節(jié)點(diǎn)在最近連續(xù)幾輪中未充當(dāng)簇首節(jié)點(diǎn)的次數(shù)；Nneighbor表示節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的數(shù)目。

改進(jìn)算法中除閾值算法不同外，簇首選擇的其他過程與LEACH算法相同。

2.2簇間數(shù)據(jù)傳輸

在進(jìn)行簇間數(shù)據(jù)傳輸時(shí)，簇首收到所屬成員的傳感數(shù)據(jù)后先做初步的數(shù)據(jù)融合，然后將新的融合數(shù)據(jù)通過多跳算法發(fā)往基站。

傳感器節(jié)點(diǎn)總能量消耗E與距離d的關(guān)系為[8]：

E(d)=kdα+γ

(3)

式中，k=wΔt,w為系數(shù)常量，Δt為數(shù)據(jù)包發(fā)送的時(shí)間；γ為額外功率消耗，是不隨距離d變化的常數(shù)，在不依賴于距離變化的任何功率消耗都可以加到γ上去。

圖3 簇首中繼節(jié)點(diǎn)選擇圖

由于傳感節(jié)點(diǎn)的能量消耗與通信距離成指數(shù)關(guān)系，當(dāng)中繼節(jié)點(diǎn)i(0

假設(shè)簇首與基站的傳輸距離小于自由空間傳播與多徑傳播的臨界距離，由式(3)可得簇首與基站直接通信的能耗：

(4)

式中，d0為簇首0到基站的距離。

假設(shè)傳感器節(jié)點(diǎn)額外功率消耗γ相同，當(dāng)通過簇首i中繼通信后，簇首0的通信能耗為：

(5)

式中，ci為簇首節(jié)點(diǎn)0到簇首節(jié)點(diǎn)i的距離；di為簇首節(jié)點(diǎn)i到基站的距離。

由于能量消耗主要涉及無線通信鏈路，而γ在整個(gè)節(jié)點(diǎn)能耗中所占的比例很小，若忽略γ，則：

(6)

在圖3中，當(dāng)中繼節(jié)點(diǎn)處于以基站和簇首節(jié)點(diǎn)0的連線為直徑的圓O上時(shí)，通過中繼節(jié)點(diǎn)消耗的能量等同于簇首節(jié)點(diǎn)直接傳輸?shù)哪芰肯摹Ｓ善矫鎺缀沃R(shí)證明如下不等式成立，即：

(7)

由此可得：

(8)

即：

E1(d1,c1)

(9)

圖4 中繼節(jié)點(diǎn)選擇流程圖

3 仿真試驗(yàn)

為了評(píng)價(jià)改進(jìn)算法的性能，利用網(wǎng)絡(luò)仿真工具OPNET對(duì)相同狀態(tài)下的LEACH算法和改進(jìn)算法在網(wǎng)絡(luò)生存時(shí)間方面進(jìn)行仿真比較，使用的網(wǎng)絡(luò)模型配置如下，在200m×200m的平面區(qū)域使用500個(gè)無線傳感器節(jié)點(diǎn)和1個(gè)固定位置的sink節(jié)點(diǎn)，且sink節(jié)點(diǎn)遠(yuǎn)離該感知區(qū)域。每個(gè)無線傳感器節(jié)點(diǎn)的初始能源為2J，數(shù)據(jù)包大小為500byte,元數(shù)據(jù)大小為25byte。簇首節(jié)點(diǎn)剩余能量比較圖如圖5所示。由圖5可知，在相同時(shí)間內(nèi)使用改進(jìn)算法的簇首能耗比使用LEACH算法的簇首能耗要低。網(wǎng)絡(luò)生存時(shí)間比較圖如圖6所示。由圖6可知，在簇首數(shù)相同時(shí)，使用改進(jìn)算法的網(wǎng)絡(luò)生存時(shí)間比使用LEACH算法的網(wǎng)絡(luò)生存時(shí)間更長。

圖5 簇首節(jié)點(diǎn)剩余能量比較圖 圖6 網(wǎng)絡(luò)生存時(shí)間比較圖

4 結(jié) 語

闡述了LEACH算法的基本原理，針對(duì)該算法的不足，在簇首選擇及簇間數(shù)據(jù)傳輸2方面進(jìn)行改進(jìn)。改進(jìn)簇首選擇機(jī)制可平衡節(jié)點(diǎn)的剩余能量，采用單跳與多跳相結(jié)合的簇間數(shù)據(jù)傳輸方式可平衡每個(gè)簇間的能量消耗。因此，對(duì)LEACH算法的改進(jìn)有利于提高網(wǎng)絡(luò)性能，明顯延長網(wǎng)絡(luò)生存時(shí)間。

[1]于海斌，曾鵬.智能無線傳感器網(wǎng)絡(luò)系統(tǒng)[M].北京：科技出版社，2006.

[2] 李善倉，張克旺.無線傳感器網(wǎng)絡(luò)原理與應(yīng)用[M].北京：機(jī)械工業(yè)出版社，2008.

[3] Heinzelman W,Chandrakasan A, Balakrishman H. An application-specific protocol architecture for wireless micro-sensor networks [J]. Wireless Communications,2002,1:660-670 .

[4] Kalaki J N,Kamal A E. Routing techniques in wireless sensor networks: A Survey [J]. Wireless communications 2004，11:6-28.

[5] Younis O, Fahmy S. HEED: A Hybrid, energy-efficient, distributed clustering approach for Ad Hoc sensor networks [J]. Transactions on mobile computing，2004，3:366-379.

[6] 顧明霞.無線傳感器網(wǎng)絡(luò)的LEACH算法改進(jìn)與仿真研究[J].計(jì)算機(jī)仿真，2010,27(9)：139-185.

[7] Handy M J, Haase M D.Timmermann low energy adaptive clustering hierarchy with deterministic cluster-head selection[J]. Mobile and wireless communications networks,2002,9:368-372.

[8] 姜華，王沛.無線傳感網(wǎng)絡(luò)中的OPNET仿真模型的研究[J].計(jì)算機(jī)工程，2007，33(4)：73-78.

[編輯] 李啟棟

10.3969/j.issn.1673-1409.2011.08.030

TP751

A

1673-1409(2011)08-0094-04