無(wú)線傳感器網(wǎng)絡(luò)LEACH路由協(xié)議的改進(jìn)算法

周志強(qiáng) 劉森 王允臣

摘 要:針對(duì)無(wú)線傳感器網(wǎng)絡(luò)簇頭節(jié)點(diǎn)選取難、網(wǎng)絡(luò)生存周期短、能量消耗大等問(wèn)題,本文在傳統(tǒng)的LEACH算法基礎(chǔ)上,設(shè)計(jì)了E-LEACH算法,E-LEACH算法引入了能量閾值的概念。能量閾值是判斷該節(jié)點(diǎn)是否可以作為簇頭節(jié)點(diǎn)的先決條件,同時(shí)引入距離因子的概念,在每輪選取簇頭時(shí),都會(huì)考慮到和基站的距離。仿真實(shí)驗(yàn)表明,該算法有效的降低了網(wǎng)絡(luò)能耗,延長(zhǎng)了節(jié)點(diǎn)的生命時(shí)間。

關(guān)鍵詞:無(wú)線傳感器網(wǎng)絡(luò)LEACH節(jié)點(diǎn)生存周期能量

中圖分類號(hào):TP3 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1672-3791(2012)06(b)-0015-02

近年來(lái),由于無(wú)線技術(shù)、計(jì)算機(jī)技術(shù)與傳感器技術(shù)的迅猛發(fā)展和快速融合,無(wú)線傳感器網(wǎng)絡(luò)應(yīng)運(yùn)而生。無(wú)線傳感器網(wǎng)絡(luò)技術(shù)作為一種新型網(wǎng)絡(luò)技術(shù)受到研究者的普遍重視和廣泛研究[1]。

但傳感器網(wǎng)絡(luò)也有一些固有的缺點(diǎn)如:能量利用率低、生存周期短、抗干擾能力差。而通過(guò)良好的分簇算法不僅可以減少傳感器節(jié)點(diǎn)的能耗,還可以降低通訊干擾、提高M(jìn)AC協(xié)議和路由協(xié)議的效率。因此,提出一個(gè)高效穩(wěn)定合理的算法便成為迫切需要解決的問(wèn)題[2]。本文在LEACH算法的基礎(chǔ)上,綜合考慮了各個(gè)節(jié)點(diǎn)的剩余能量,提出了一種更為高效、更為合理的低開(kāi)銷(xiāo)自適應(yīng)分層的E-LEACH算法。

1LEACH算法分析

LEACH協(xié)議是由Wendi等人提出的,其基本思想是:提出了“輪(round)”的概念,通過(guò)每一輪的循環(huán)隨機(jī)選擇簇頭節(jié)點(diǎn),然后再對(duì)簇頭節(jié)點(diǎn)進(jìn)行輪換,從而達(dá)到平衡和降低能耗、延長(zhǎng)網(wǎng)絡(luò)的生存周期的目的。在LEACH協(xié)議中,每一輪由兩部分構(gòu)成。第一部分是構(gòu)建簇階段,第二部分為穩(wěn)定工作階段。

在實(shí)際的無(wú)線傳感器網(wǎng)絡(luò)中,經(jīng)過(guò)多輪選舉后,各個(gè)節(jié)點(diǎn)的剩余能量將會(huì)有很大的不同,靠近簇頭的節(jié)點(diǎn)剩余的能量多,而遠(yuǎn)離簇頭的節(jié)點(diǎn)剩余的能量少。但是在傳統(tǒng)的LEACH算法中,所有的節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的概率是相同的。因此,若在以后的多輪數(shù)據(jù)傳播中都選取遠(yuǎn)離基站的節(jié)點(diǎn)做簇頭,則該節(jié)點(diǎn)的能量將很快被耗盡,最終成為失效節(jié)點(diǎn)。過(guò)多的失效節(jié)點(diǎn)將導(dǎo)致整個(gè)網(wǎng)絡(luò)的癱瘓。

另外,在傳統(tǒng)的LEACH算法中,每一輪的初始化階段,節(jié)點(diǎn)根據(jù)接收到簇頭節(jié)的廣播信號(hào)的強(qiáng)弱,選擇要加入的簇。但是,這種方案不一定是最優(yōu)的方案。A、B、C為選擇出來(lái)的簇首節(jié)點(diǎn),D為基站,E為非簇首節(jié)點(diǎn)。顯然節(jié)點(diǎn)E距離A、C的距離均比距離B的距離近,但若E要將數(shù)據(jù)傳到基站D,最優(yōu)的簇頭卻應(yīng)選B。因?yàn)椴徽撌沁xC還是選A,整個(gè)網(wǎng)絡(luò)消耗的能量都大于B路徑。

2LEACH改進(jìn)算法

針對(duì)LEACH算法的不足之處,本文設(shè)計(jì)了E-LEACH算法,在很大程度上解決了上述問(wèn)題。E-LEACH算法構(gòu)建簇時(shí)經(jīng)過(guò)了兩次選擇。第一次選擇選出符合能量條件和距離極小條件的節(jié)點(diǎn)集合,第二次選擇才是真正的簇頭選擇階段,在該集合中隨機(jī)選出符合要求的簇頭節(jié)點(diǎn)。

首先,E-LEACH算法引入了能量閾值的概念。能量閾值是判斷該節(jié)點(diǎn)是否可以作為簇頭節(jié)點(diǎn)的先決條件。能量閾值的計(jì)算公式:

(1)

式中E(r)為第r輪的能量閾值,K為能量閾值因子,p為期望的簇頭節(jié)點(diǎn)占所有有效節(jié)點(diǎn)的百分比,Er為第r輪循環(huán)網(wǎng)絡(luò)中隨機(jī)選取的有效節(jié)點(diǎn)的能量總和,m為第r輪中簇頭節(jié)點(diǎn)總數(shù)。在每一輪簇頭選擇前,將每個(gè)符合簇頭條件的節(jié)點(diǎn)能量與能量閾值相比,若節(jié)點(diǎn)能量小于能量閾值則將該節(jié)點(diǎn)從簇頭候選節(jié)點(diǎn)中剔除[3～5]。

其次,E-LEACH算法引入了距離因子:

(2)

其中d m為監(jiān)測(cè)區(qū)內(nèi)節(jié)點(diǎn)到基站的最大距離,d(i)為節(jié)點(diǎn)i到基站的距離。有了距離因子,在每輪選取簇頭節(jié)點(diǎn)將數(shù)據(jù)向基站傳送時(shí),都會(huì)考慮距離代價(jià)。從而選擇出數(shù)據(jù)傳輸距離最小的路徑。

經(jīng)過(guò)第一次的選擇,我們可以得到一個(gè)簇頭候選集合Q。

(3)

Q是在1/p輪中未成為簇頭并且能量大于能量閾值的節(jié)點(diǎn)集合。非簇頭節(jié)點(diǎn)選擇加入簇時(shí),也會(huì)參照能量閾值及距離因子,選出能量損耗最小的傳輸路徑[6]。

4仿真與實(shí)驗(yàn)分析

本方案使用MATLAB仿真。在仿真時(shí)K取0.75,傳感器節(jié)點(diǎn)隨機(jī)的分布在1000×1000的平面區(qū)域內(nèi)。傳感器節(jié)點(diǎn)數(shù)為1000個(gè),各個(gè)節(jié)點(diǎn)初始能量為3J,基站坐標(biāo)為(50,750),數(shù)據(jù)包大小為20bytes。LEACH算法與E-LEACH算法存活節(jié)點(diǎn)的數(shù)量隨時(shí)間的變化情況。LEACH算法與E-LEACH算法傳輸數(shù)據(jù)量與能耗的關(guān)系。

由此次實(shí)驗(yàn)的仿真可以看出在初始節(jié)點(diǎn)數(shù)相同條件下,隨時(shí)間的推移,采用LEACH算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)存活數(shù)明顯低于采用E-LEACH算法的無(wú)線傳感器網(wǎng)絡(luò)。而且在傳送相同數(shù)據(jù)量的條件下,E-LEACH算法消耗的能量要更少。

5結(jié)語(yǔ)

本文以傳統(tǒng)的LEACH算法為基礎(chǔ),考慮了每一輪中各個(gè)節(jié)點(diǎn)剩余能量不一致問(wèn)題,以及所選路徑并非最節(jié)能路徑的問(wèn)題。提出了能量閾值及距離因子的概念,通過(guò)能量閾值及距離因子確定優(yōu)選簇頭集合,再在此基礎(chǔ)上選擇出簇頭節(jié)點(diǎn)。通過(guò)這種簇頭選擇優(yōu)化算法,實(shí)現(xiàn)了延長(zhǎng)網(wǎng)絡(luò)生存周期,提高節(jié)點(diǎn)能量利用率的目的。

參考文獻(xiàn)

[1] AKYILDIZ I F,WEILIANS, SANKARASUBRAMANIAMY.A survey on sensor networks [J]. IEEE Communications Magazine,2002.

[2] Akkaya K,Younis M.Asurvey on routing protocols for wirelesssensor networks[J].AdHocNetworks,2005.

[3] 孫利民,李建中,陳渝,等.無(wú)線傳感器網(wǎng)絡(luò)[M].清華大學(xué)出版社,2005.

[4] 江冰,吳元忠,謝冬梅.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自定位算法的研究[J].傳感技術(shù)學(xué)報(bào),2007.

[5] SICHITIU M L.Cross-layer scheduling for power efficiency in wire-less sensor networks[A].Proceedings of IEEE INFOCOM 2004[C].Hong Kong, China,2004.

[6] 葉馳,孫利民,廖勇.傳感器網(wǎng)絡(luò)的能量管理[J].計(jì)算機(jī)工程與應(yīng)用,2004.