基于能量和距離加權(quán)的WSNs簇頭選擇算法*

王 進， 邵玉斌， 龍 華， 杜慶治

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

0 引 言

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

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

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

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

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

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

(1)

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

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

1.2 簇頭選擇的改進算法

1.2.1 閾值公式的改進

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

T(n)=

(2)

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

1.2.2 簇頭的選擇

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

(3)

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

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

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

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

2 仿真與性能分析

本文所用的仿真參數(shù)如下：網(wǎng)絡監(jiān)測區(qū)域為100 m×100 m，監(jiān)測區(qū)域內(nèi)隨機分布了100個傳感器節(jié)點，假定基站的位置為(50,175)m，每個節(jié)點初始能量相同，均為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所示，改進后的LEACH延長了網(wǎng)絡生命周期，相比于未改進的LEACH協(xié)議，網(wǎng)絡的整體生存時間延長了9.4%，同時LEACH協(xié)議在第731輪出現(xiàn)第一個死亡節(jié)點，改進后的LEACH協(xié)議的第一個死亡節(jié)點出現(xiàn)在第858輪，說明改進后的LEACH算法穩(wěn)定性更好。從圖2可以看出:改進后的LEACH算法使得網(wǎng)絡中的能耗更為均衡。由于將節(jié)點能量和節(jié)點到基站的距離作為選取簇頭的參考因素，這樣就避免了能量較低和離基站較遠的節(jié)點過多的能量消耗，但是，改進后的算法需要考慮節(jié)點的能量和位置信息，也會消耗少量的能量。

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

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

3 結(jié)束語

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

參考文獻:

[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)絡[M].北京:清華大學出版社,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)絡路由協(xié)議LEACH的研究與改進[J].傳感技術(shù)學報,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.