王 進(jìn)， 邵玉斌， 龍 華， 杜慶治

(昆明理工大學(xué) 信息工程與自動化學(xué)院，云南 昆明 650500)

0 引 言

多年來，無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)技術(shù)得到了長足的發(fā)展[1]，利用其自身的優(yōu)勢，廣泛應(yīng)用于環(huán)境檢測、智能家居、公共交通等領(lǐng)域[2,3]。但由于受到其自身軟硬件條件的限制，存儲、運(yùn)算和通信能力較弱[4]，特別是能量有限，不能實(shí)時補(bǔ)給，因此,傳統(tǒng)的路由協(xié)議不適用于無線傳感器網(wǎng)絡(luò)，如何平衡能耗、延長網(wǎng)絡(luò)壽命就成為了設(shè)計無線傳感器網(wǎng)絡(luò)路由協(xié)議的重點(diǎn)和難點(diǎn)。

由于分簇路由協(xié)議相比于平面路由協(xié)議具有更大的優(yōu)勢，近年來已成為研究的熱點(diǎn)。文獻(xiàn)[5]提出以虛擬化的多輸入多輸出(MIMO)為基礎(chǔ)的用戶合作通信方式，在每個簇內(nèi)選取一個簇頭和若干個協(xié)作簇頭；DAIC[6]協(xié)議將整個網(wǎng)絡(luò)分為若干層，各層中運(yùn)用模擬退火算法選取簇頭并形成相應(yīng)的簇；文獻(xiàn)[7]將節(jié)點(diǎn)能量和節(jié)點(diǎn)的鄰近數(shù)目作為簇頭選擇的參考因素；BCDCP[8]協(xié)議均勻分配耗能，傳感器節(jié)點(diǎn)間利用最小生成樹，建立基站到簇頭間的多跳路由。但是,以上協(xié)議存在未對簇頭數(shù)目和簇頭選取后進(jìn)一步優(yōu)化的問題。

本文在LEACH協(xié)議的基礎(chǔ)上，將節(jié)點(diǎn)能量和節(jié)點(diǎn)到基站的距離作為參考因素引入閾值公式，目的是為了降低能量較少或離基站較遠(yuǎn)的節(jié)點(diǎn)被選為簇頭的可能性，避免一些節(jié)點(diǎn)過早死亡；簇頭選擇時，依據(jù)新的閾值公式使每輪選出的簇頭數(shù)達(dá)到預(yù)設(shè)的最優(yōu)值，這樣可以減少因簇結(jié)構(gòu)不合理所產(chǎn)生的額外能量消耗，從而延長網(wǎng)絡(luò)的生命周期；針對分簇結(jié)束后已有的簇頭可能并非該分簇最佳簇頭的問題，提出了簇頭的二次優(yōu)化算法，從而最終確定最佳的簇頭。

1 基于LEACH協(xié)議的改進(jìn)算法

1.1 LEACH協(xié)議的簇頭選擇算法

在LEACH協(xié)議的簇結(jié)構(gòu)建立階段，每個節(jié)點(diǎn)產(chǎn)生一個(0～1)隨機(jī)數(shù)，如果該數(shù)小于閾值T(n)，則該節(jié)點(diǎn)就被選為當(dāng)輪的簇頭節(jié)點(diǎn)。T(n)的表達(dá)式如式(1)所示

(1)

其中,r為當(dāng)前的輪數(shù)；p為網(wǎng)絡(luò)中簇頭數(shù)與節(jié)點(diǎn)總數(shù)的比值；G為最近1/p輪中未當(dāng)選簇頭的節(jié)點(diǎn)集。

LEACH協(xié)議未考慮以下幾個方面：1)簇頭的數(shù)目未優(yōu)化；2)假定簇頭與基站直接通信，距離基站越遠(yuǎn)的簇頭傳輸能耗越大；3)簇頭是隨機(jī)選出的，因而未考慮簇頭的剩余能量，若能量很低的節(jié)點(diǎn)被選為簇頭，會使得該節(jié)點(diǎn)過快死亡，從而影響網(wǎng)絡(luò)生命周期。本文就是在LEACH的基礎(chǔ)上進(jìn)行改進(jìn)，優(yōu)化路由算法。

1.2 簇頭選擇的改進(jìn)算法

1.2.1 閾值公式的改進(jìn)

將當(dāng)前節(jié)點(diǎn)能量和網(wǎng)絡(luò)中節(jié)點(diǎn)平均能量作為參考因素，同時將節(jié)點(diǎn)到基站的距離作為因子引入閾值公式，從而提高剩余能量較高或離基站較近的節(jié)點(diǎn)被選為簇頭的可能性，將網(wǎng)絡(luò)能量消耗均衡到每個節(jié)點(diǎn)上，得到改進(jìn)后的閾值公式

T(n)=

(2)

式中Ecurr為節(jié)點(diǎn)的剩余能量，Eaver為每一輪結(jié)束后節(jié)點(diǎn)的平均能量，dtoBS為簇頭到基站的距離，dmax為所有節(jié)點(diǎn)中到基站的最大距離。

1.2.2 簇頭的選擇

簇頭選擇前，先計算出該輪的最優(yōu)簇頭數(shù)，這是因?yàn)長EACH中簇頭是隨機(jī)產(chǎn)生的，每輪的簇頭數(shù)波動較大，如果事先將每輪的簇頭數(shù)設(shè)為最優(yōu)值，可以達(dá)到合理優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的目的，進(jìn)而減少因結(jié)構(gòu)不合理所產(chǎn)生的能量消耗。最優(yōu)簇頭數(shù)公式如下[9]

(3)

式中kopt為最優(yōu)簇頭數(shù)；εfs為在自由空間模型下信號的放大倍數(shù)；εmp為在多徑衰減信道模型下信號的放大倍數(shù)；N為整個網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量；M為網(wǎng)絡(luò)中節(jié)點(diǎn)所在區(qū)域的邊長。

使用改進(jìn)后的閾值公式選取簇頭，并將選出的簇頭加入到初始簇頭集中，如果初始簇頭集中的簇頭數(shù)少于最優(yōu)簇頭數(shù)kopt，繼續(xù)使用改進(jìn)后的閾值公式選取簇頭并加入到初始簇頭集中，直到選出的簇頭數(shù)達(dá)到最優(yōu)值；如果初始簇頭集中的簇頭數(shù)多于最優(yōu)簇頭數(shù)kopt，先將初始簇頭集中簇頭按剩余能量從高往低排序，從初始簇頭集中選擇前kopt個簇頭加入到新的初始簇頭集中，選取剩余能量較大的節(jié)點(diǎn)當(dāng)選簇頭，這樣可以將網(wǎng)絡(luò)中消耗的能量盡可能的平均分配到每個節(jié)點(diǎn)上，從而延長整個網(wǎng)絡(luò)的生命周期。

1.2.3 簇頭的二次優(yōu)化

當(dāng)簇頭位于簇的幾何中心點(diǎn)時，簇內(nèi)成員節(jié)點(diǎn)到簇頭的距離平方和最小，又由于節(jié)點(diǎn)間的通信能耗主要與節(jié)點(diǎn)間的距離有關(guān)，因此，當(dāng)簇頭位置越靠近簇的幾何中心時，簇內(nèi)節(jié)點(diǎn)間通信時的總能耗也應(yīng)該越小。分簇結(jié)束后，為了進(jìn)一步減少簇內(nèi)通信時的總能耗，需要對簇頭進(jìn)行二次優(yōu)化選擇。先將每個簇中剩余能量大于平均能量的節(jié)點(diǎn)加入到該簇的候選簇頭集中，這樣是為了均衡每個節(jié)點(diǎn)上的能量消耗，然后基站根據(jù)簇中節(jié)點(diǎn)的位置信息，計算每個分簇的幾何中心位置，最后從候選簇頭集中選擇距離幾何中心位置最近的節(jié)點(diǎn)作為該簇新的簇頭。

2 仿真與性能分析

本文所用的仿真參數(shù)如下：網(wǎng)絡(luò)監(jiān)測區(qū)域?yàn)?00 m×100 m，監(jiān)測區(qū)域內(nèi)隨機(jī)分布了100個傳感器節(jié)點(diǎn)，假定基站的位置為(50,175)m，每個節(jié)點(diǎn)初始能量相同，均為0.5 J，數(shù)據(jù)包長度為4 000 bit，距離閾值為87.705 8 m，發(fā)送/接收電路能量Eelec為50 nJ/bit，數(shù)據(jù)融合消耗能量EDA為5 nJ/bit/signal，自由空間放大倍數(shù)εfs為10 pJ/bit/m2，多徑衰減信號放大倍數(shù)εmp為0.001 3 pJ/bit/m2，仿真時忽略無線碰撞和信道干擾的影響。

如圖1所示，改進(jìn)后的LEACH延長了網(wǎng)絡(luò)生命周期，相比于未改進(jìn)的LEACH協(xié)議，網(wǎng)絡(luò)的整體生存時間延長了9.4%，同時LEACH協(xié)議在第731輪出現(xiàn)第一個死亡節(jié)點(diǎn)，改進(jìn)后的LEACH協(xié)議的第一個死亡節(jié)點(diǎn)出現(xiàn)在第858輪，說明改進(jìn)后的LEACH算法穩(wěn)定性更好。從圖2可以看出:改進(jìn)后的LEACH算法使得網(wǎng)絡(luò)中的能耗更為均衡。由于將節(jié)點(diǎn)能量和節(jié)點(diǎn)到基站的距離作為選取簇頭的參考因素，這樣就避免了能量較低和離基站較遠(yuǎn)的節(jié)點(diǎn)過多的能量消耗，但是，改進(jìn)后的算法需要考慮節(jié)點(diǎn)的能量和位置信息，也會消耗少量的能量。

圖1 LEACH和改進(jìn)后的LEACH存活節(jié)點(diǎn)數(shù)的對比

圖2 LEACH和改進(jìn)后的LEACH網(wǎng)絡(luò)總能耗的對比

3 結(jié)束語

本文針對LEACH協(xié)議存在的問題加以改進(jìn)，將當(dāng)前節(jié)點(diǎn)能量和網(wǎng)絡(luò)中節(jié)點(diǎn)平均能量作為參考因素，并將節(jié)點(diǎn)到基站的距離作為因子引入閾值公式，在選取簇頭時，依據(jù)改進(jìn)后的閾值公式使所選取的簇頭數(shù)達(dá)到最優(yōu)值，減少不必要的簇頭能耗，并通過簇頭的二次選擇，最終確定最佳的簇頭。仿真結(jié)果表明：改進(jìn)后的LEACH算法延長了整個網(wǎng)絡(luò)的生命周期，同時也使網(wǎng)絡(luò)負(fù)載更為均衡。

參考文獻(xiàn):

[1] AKyildiz I F,Su W,Cayirci E.A survey on sensor network[J].IEEE Communication Magazine,2009,40(8):102-114.

[2] Alwan H,Aqarwal A.A survey on fault tolerant routing techniques in wireless sensor networks[C]∥2009 3rd International Conference on Sensor Technologies and Applications,Athens,Greece,2009:366-371.

[3] Jiang C,Yuan D,Zhao Y.Towards clustering algorithms in wireless sensor networks—A survey[C]∥2009 IEEE Wireless Communication and Networking Conference,Budapest,Hungary,2009:1-6.

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

[5] Asaduzzaman,Kong Hyung Yun.Energy efficient cooperative LEACH protocol for wireless sensor networks[J].Journal of Communication and Networks,2010,12(4):358-365.

[6] Gautam Navin,Pyun JaeYoung.Distance aware intelligent clustering protocol for wireless sensor networks[J].Journal of Communication and Networks,2010,12(2):122-129.

[7] 胡 剛,謝東梅,吳元忠.無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的研究與改進(jìn)[J].傳感技術(shù)學(xué)報,2007,20(6):1391-1396.

[8] Muruganathan S D,Ma D C F,Bhasin P I.A centralized energy-efficient routing protocol for wireless sensor networks[J].IEEE Communications Magazine,2005,43(3):8-13.

[9] Heinzelman W R,Chandrakasan A,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.