摘 要:在分析LEACH協(xié)議的基礎(chǔ)上提出一種基于能量和距離的多跳路由算法(CAED)。由基站依據(jù)節(jié)點(diǎn)剩余能量和簇頭與基站的距離分別選出二層簇頭，簇內(nèi)節(jié)點(diǎn)利用單跳和多跳模式與簇頭進(jìn)行通信。仿真實(shí)驗(yàn)表明，新算法有效地平衡了節(jié)點(diǎn)的能量消耗，并顯著地延長了網(wǎng)絡(luò)的生命周期。

關(guān)鍵詞: 無線傳感器網(wǎng)絡(luò); 路由算法; 剩余能量; 生命周期

中圖分類號(hào):TP393 文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1004-373X(2010)10-0162-03

Cluster Routing Algorithm for Wireless Sensor Network

LIU Qiong， CHENG Yun

(Hunan Institute of Humanities，Science and Technology， Loudi 417000， China)

Abstract: A new clustering algorithm based on energy and distance(CAED) is proposed based on analysing LEACH protocal. The two layer cluster heads were selected by base station in terms of residual energy of node and distance between cluster heads and base station. Sensor nodes communication was performed by cluster heads with single hop mode and multi-hop mode. Simulation results show that the noval algorithm can balance energy consumption of node， and can obviously improve the lifetime of the wireless sensor network.

Key words: wireless sensor network; routing protocol; residual energy; lifetime

0 引 言

隨著微電子工藝和無線通信技術(shù)的飛速發(fā)展，無線傳感器網(wǎng)絡(luò)(WSN)的研究越來越受到人們的重視。 傳感器網(wǎng)絡(luò)(sensor network)是由部署在觀測環(huán)境附近的大量微型廉價(jià)低功耗傳感器節(jié)點(diǎn)組成，通過無線通信方式組成一個(gè)多跳的無線網(wǎng)絡(luò)系統(tǒng)[1]。由于無線傳感器網(wǎng)絡(luò)通常部署在人無法接近或者高危險(xiǎn)區(qū)域，且數(shù)量眾多，這使得隨時(shí)更換節(jié)點(diǎn)能量變得非常困難。在監(jiān)測區(qū)域內(nèi)傳感器節(jié)點(diǎn)采集的相關(guān)信息，通常攜帶一次性電池且能量有限，在經(jīng)過一段時(shí)間的數(shù)據(jù)采集后，無線傳感器網(wǎng)絡(luò)存在嚴(yán)重的能量約束問題。所以，傳感器網(wǎng)絡(luò)協(xié)議的首要設(shè)計(jì)目標(biāo)就是要高效地使用傳感器節(jié)點(diǎn)的能量，延長網(wǎng)絡(luò)的存活時(shí)間。將傳感器節(jié)點(diǎn)組織成簇的形式，以有效地減少能量消耗，許多能量高效的路由協(xié)議都是在簇結(jié)構(gòu)的基礎(chǔ)上進(jìn)行設(shè)計(jì)的[2-8]。

LEACH[2]是一個(gè)典型的自適分簇協(xié)議，網(wǎng)絡(luò)中節(jié)點(diǎn)通過隨機(jī)方式自組織形成簇，在分配給的時(shí)隙

向簇首發(fā)送數(shù)據(jù)，簇首對收到的數(shù)據(jù)融合后在每幀結(jié)束后直接與基站通信。節(jié)點(diǎn)輪流擔(dān)任簇首，均衡了網(wǎng)絡(luò)的能耗，但簇首在當(dāng)選時(shí)，沒有考慮節(jié)點(diǎn)的能量高低，若節(jié)點(diǎn)能量很低，仍要擔(dān)當(dāng)簇首時(shí)，會(huì)加速它死亡。另外，數(shù)據(jù)直接發(fā)送到基站，會(huì)使距基站較遠(yuǎn)的節(jié)點(diǎn)能耗很大，導(dǎo)致局部節(jié)點(diǎn)提前死亡，產(chǎn)生監(jiān)控盲點(diǎn)。

由于LEACH算法沒有考慮節(jié)點(diǎn)的剩余能量及與基站的距離等因素，很多文獻(xiàn)提出了相應(yīng)的改進(jìn)算法，如EBAC[4]是在LEACH協(xié)議的基礎(chǔ)上，周期性地選用當(dāng)前輪剩余能量最大的節(jié)點(diǎn)擔(dān)任下一輪簇頭。LEACH-D[5]是基于LEACH的多跳路由算法。文獻(xiàn)[6]提出了構(gòu)建能量均衡簇群的方法，LEACH-L[7]綜合考慮了節(jié)點(diǎn)的位置和能量的多跳路由算法。

本文在LEACH協(xié)議的基礎(chǔ)上，以降低簇頭直接和基站遠(yuǎn)距離通信的能量損耗為首要目標(biāo)，同時(shí)在二層簇頭選擇時(shí)綜合考慮了節(jié)點(diǎn)的剩余能量和基站的距離，并且改進(jìn)了簇頭間的多跳路徑，避免使用低能量的節(jié)點(diǎn)。通過Matlab仿真表明，該算法能進(jìn)一步均衡簇頭節(jié)點(diǎn)的能量消耗，延長網(wǎng)絡(luò)的生命周期。

1 系統(tǒng)模型

N個(gè)傳感器節(jié)點(diǎn)隨機(jī)均勻分布在一個(gè)正方形區(qū)域內(nèi)，周期性地收集周圍環(huán)境信息，并且具有如下性質(zhì):

(1) 所有傳感器節(jié)點(diǎn)部署后不再移動(dòng)，且都有1個(gè)惟一的標(biāo)識(shí)ID;

(2) 基站惟一，且位于離采集區(qū)域較遠(yuǎn)的一個(gè)固定位置;

(3) 所有節(jié)點(diǎn)具有相似的能力(處理/通信)，都具備數(shù)據(jù)融合功能;

(4) 若已知對方的發(fā)射功率，節(jié)點(diǎn)可以根據(jù)接收信號(hào)的強(qiáng)度計(jì)算出發(fā)送方離它的近似距離;

(5) 節(jié)點(diǎn)的能量不能補(bǔ)充，節(jié)點(diǎn)的發(fā)射功率可控。

這里采用與文獻(xiàn)[2]相同的無線通信模型:根據(jù)距離閾值d0，分別采用自由空間模型和多路衰減模型。發(fā)送方發(fā)送k比特的數(shù)據(jù)到距離為d的接收方所消耗的能量為:

ETx(k，d)=kEelec+kεfsd2， d

kEelec+kεmpd4，d≥d0 (2)

接收能耗為:

ERx(k，d)= kEelec

2 CAED算法描述

在LEACH基礎(chǔ)上，提出一個(gè)基于能量和距離的分簇算法(clustering algorithm based on energy and distance)。該算法按輪運(yùn)行，每輪分為二層簇頭的建立，簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)和穩(wěn)定數(shù)據(jù)的傳輸。

2.1 二層簇頭的建立

在簇建立階段，首輪擔(dān)任簇頭的節(jié)點(diǎn)由基站隨機(jī)確定。簇頭的個(gè)數(shù)根據(jù)監(jiān)測區(qū)域的位置、大小及網(wǎng)絡(luò)規(guī)模[3]來確定。被選中擔(dān)任簇頭的ID由基站依次在網(wǎng)絡(luò)中進(jìn)行廣播，網(wǎng)內(nèi)節(jié)點(diǎn)對逐次收到的ID與自己的進(jìn)行對比，相同的即為本輪的簇頭。簇頭全部選出以后，再向全網(wǎng)廣播簇頭ID。簇內(nèi)節(jié)點(diǎn)在每輪數(shù)據(jù)傳輸?shù)淖詈笠粠?，把剩余能量等信息一起發(fā)送至各自簇頭。簇頭對各簇內(nèi)節(jié)點(diǎn)的剩余能量進(jìn)行比較，選舉剩余能量最大的節(jié)點(diǎn)作為下一輪簇頭，這樣建立了第一層簇頭。

第二層簇頭的建立和通信模式與LEACH有較大的區(qū)別。每輪選出的第一層簇頭成為第二層簇頭的普通節(jié)點(diǎn)，在LEACH中這些節(jié)點(diǎn)直接與基站通信。由式(1)可以看出，放大器能耗遠(yuǎn)大于電路能耗，且放大器能耗中與通信距離d有直接關(guān)系，因此在產(chǎn)生第二層簇頭時(shí)，充分考慮了節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)與基站間距離等因素。產(chǎn)生第二層簇頭的閾值按如下公式計(jì)算:

Tch=Eresidual(i)/BSdistance(i)(3)

式中:Eresidual(i)標(biāo)識(shí)為i的簇頭的剩余能量;BSdistance(i)標(biāo)識(shí)為i的簇頭與基站之間的距離。每輪在產(chǎn)生完第一層簇頭且簇頭能量高于某一個(gè)值Eth(若節(jié)點(diǎn)低于Eth就認(rèn)為節(jié)點(diǎn)失效)時(shí)，各簇頭比較Tch值，找出其中Tch最大值為第二層簇頭。因此，第二層簇頭既有較高的能量，又距基站較近，這樣既能減少轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)所消耗的能量，又能保證節(jié)點(diǎn)能量不會(huì)很快耗盡，而影響數(shù)據(jù)的采集。

2.2 簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)

每輪第一層簇頭選出來后，節(jié)點(diǎn)依據(jù)收到廣播信號(hào)的強(qiáng)度選擇要加入的簇，此時(shí)簇內(nèi)通信采用自由空間模型。與第一層簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)通信不同，由于第二層簇內(nèi)節(jié)點(diǎn)距離簇頭較遠(yuǎn)，有些可能遠(yuǎn)遠(yuǎn)超過了d0值，而數(shù)據(jù)通信采用的自由空間模型不一定正確，另外，直接與簇頭通信的能量消耗較大。因此，假設(shè)遠(yuǎn)離簇頭的節(jié)點(diǎn)可與臨近的、能量高于自己的節(jié)點(diǎn)通信，且數(shù)據(jù)經(jīng)過多路轉(zhuǎn)發(fā)直至簇頭，滿足上述假設(shè)條件如式(4)所示:

L2i-h+ L2h-chEi-residual(4)

式中:L2i-h為節(jié)點(diǎn)i到節(jié)點(diǎn)h的距離平方;L2h-ch為節(jié)點(diǎn)h到簇頭ch的距離平方;L2i-ch為節(jié)點(diǎn)i到簇頭ch的距離平方;Eh-residual為節(jié)點(diǎn)h的剩余能量;Ei-residual為節(jié)點(diǎn)i的剩余能量。

由于每一輪每個(gè)簇頭在簇中的位置以及簇內(nèi)節(jié)點(diǎn)的個(gè)數(shù)會(huì)發(fā)生動(dòng)態(tài)變化，為便于分析式(4)的最佳臨近節(jié)點(diǎn)，在圖1中列出了某種狀態(tài)下4種典型的數(shù)據(jù)轉(zhuǎn)發(fā)方式。

圖1 簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)方式圖

圖1(a)出現(xiàn)在數(shù)據(jù)收集的前期階段，由于節(jié)點(diǎn)能量充足，靠近基站的節(jié)點(diǎn)采用直接傳輸方式，而遠(yuǎn)離基站的節(jié)點(diǎn)通過式(4)選擇下一跳節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā);經(jīng)過多輪數(shù)據(jù)采集之后，靠近基站的節(jié)點(diǎn)因過多參與數(shù)據(jù)的轉(zhuǎn)發(fā)能量迅速降低，依據(jù)式(4)出現(xiàn)了圖1(b)或圖1(c);在數(shù)據(jù)收集的后續(xù)階段，由于靠近基站的節(jié)點(diǎn)整體能量下降，它們分別采用單跳的方式直接與基站通信，同時(shí)依據(jù)式(4)出現(xiàn)了圖1(d)。整個(gè)數(shù)據(jù)采集階段遠(yuǎn)離基站的節(jié)點(diǎn)都是通過多跳的方式與臨近節(jié)點(diǎn)通信，說明通過多跳的數(shù)據(jù)轉(zhuǎn)發(fā)能耗要小于直接發(fā)送到簇首[8]，同時(shí)轉(zhuǎn)發(fā)數(shù)據(jù)的節(jié)點(diǎn)能量較高，保證了轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)有足夠的能量，均衡了網(wǎng)絡(luò)的能量。

2.3 穩(wěn)定數(shù)據(jù)傳輸

在穩(wěn)定數(shù)據(jù)傳輸階段，普通節(jié)點(diǎn)與第一層簇頭通信方式和LEACH相同，但是數(shù)據(jù)的采集、融合工作完成之后不是將數(shù)據(jù)包直接發(fā)送到基站，而是在給定的時(shí)隙內(nèi)發(fā)送給第一層各自的簇頭。第二層的節(jié)點(diǎn)依據(jù)能量和距離選出下一跳節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，直至第二層的簇頭或直接與基站通信，第二層簇頭節(jié)點(diǎn)經(jīng)過二次數(shù)據(jù)融合后，發(fā)送數(shù)據(jù)至基站。

3 算法分析和仿真結(jié)果

利用Matlab工具對LEACH，EBAC和CAED算法進(jìn)行仿真比較，各項(xiàng)參數(shù)設(shè)置如下:假設(shè)無線傳感器網(wǎng)絡(luò)由300個(gè)相同的節(jié)點(diǎn)組成，隨機(jī)拋撒在200 m×200 m的區(qū)域內(nèi)，遠(yuǎn)程基站的坐標(biāo)是(x=100 m，y=350 m)。每個(gè)節(jié)點(diǎn)的初始能量為E0=1 J，發(fā)送和接收電路的損耗為ETX=ERX=50 nJ/b，數(shù)據(jù)融合消耗為EDA=5 nJ/b，εfs=10 pJ/(b#8226;m-2)時(shí)dd0。其中，d0為常數(shù)[1]，數(shù)據(jù)包長度為4 200 b，廣播包長度為60 b，簇頭個(gè)數(shù)kopt=5。節(jié)點(diǎn)能量低于Eth=0.000 1 J時(shí)，認(rèn)為其死亡，假設(shè)數(shù)據(jù)融合率為100%，且在轉(zhuǎn)發(fā)過程中無數(shù)據(jù)包丟失，沒有誤碼率。

圖2是存活的節(jié)點(diǎn)數(shù)與輪數(shù)關(guān)系圖?？梢钥闯?，LEACH在整個(gè)生命周期曲線比較陡峭，網(wǎng)絡(luò)中節(jié)點(diǎn)的存活數(shù)量隨時(shí)間的推移變化急劇，網(wǎng)絡(luò)中節(jié)點(diǎn)的能量不均衡。EBAC曲線在1 000輪前比LEACH平滑，由于在選舉簇頭節(jié)點(diǎn)時(shí)考慮了剩余能量，故性能明顯優(yōu)于LEACH，但是EBAC中簇頭直接與基站通信，增加了簇頭節(jié)點(diǎn)遠(yuǎn)程通信能量損耗，當(dāng)運(yùn)行到某一時(shí)刻(大約在1 094輪后)，大量節(jié)點(diǎn)在輪數(shù)相差不多的情況下失效。CAED綜合考慮了剩余能量和距離，并且在第二層簇中使用多跳方式轉(zhuǎn)發(fā)數(shù)據(jù)，CAED的曲線比EBAC平滑，進(jìn)一步延長了網(wǎng)絡(luò)的生命周期。

圖2 每輪存活節(jié)點(diǎn)的數(shù)量

表1統(tǒng)計(jì)出網(wǎng)絡(luò)運(yùn)行這3個(gè)算法時(shí)，發(fā)生首個(gè)節(jié)點(diǎn)失效時(shí)的輪數(shù)，網(wǎng)絡(luò)有30%的節(jié)點(diǎn)失效時(shí)的輪數(shù)和網(wǎng)絡(luò)運(yùn)行800輪時(shí)節(jié)點(diǎn)的失效個(gè)數(shù)。表中數(shù)值都是經(jīng)過多次運(yùn)行相應(yīng)算法得出的平均值，這里用首節(jié)點(diǎn)死亡輪數(shù)來衡量網(wǎng)絡(luò)穩(wěn)定周期，用30%節(jié)點(diǎn)失效來衡量網(wǎng)絡(luò)生命周期。

表1 網(wǎng)絡(luò)穩(wěn)定周期和生命周期對比表

首節(jié)點(diǎn)失效輪數(shù)30%節(jié)點(diǎn)失效輪數(shù)800輪時(shí)節(jié)點(diǎn)的失效個(gè)數(shù)

LEACH108235245

EBAC4341 09435

CAED7231 31211

由表1可見，相對于LEACH來說，CAED網(wǎng)絡(luò)的穩(wěn)定周期延長了570%以上，同時(shí)將網(wǎng)絡(luò)生命周期延長了458%以上。相對于EBAC來說，CAED網(wǎng)絡(luò)的穩(wěn)定周期延長了67%以上，網(wǎng)絡(luò)生命周期延長了20%以上。3種算法在800輪時(shí)，節(jié)點(diǎn)的失效個(gè)數(shù)分別占節(jié)點(diǎn)總數(shù)的81.7%，11.7%和3.7%，網(wǎng)絡(luò)的節(jié)點(diǎn)能耗進(jìn)一步均衡，避免了“盲節(jié)點(diǎn)”過早的發(fā)生。

圖3顯示了網(wǎng)絡(luò)在運(yùn)行3種算法時(shí)，網(wǎng)絡(luò)總的剩余能量情況，仿真實(shí)驗(yàn)中每隔50輪做1次采樣記錄。從圖3可以看出，對網(wǎng)絡(luò)總的剩余能量而言，CAED明顯高于LEACH和EBAC，說明CAED能很好地節(jié)省網(wǎng)絡(luò)能量，延長網(wǎng)絡(luò)的生命周期。

圖3 網(wǎng)絡(luò)中節(jié)點(diǎn)的剩余能量

4 結(jié) 語

提出一種基于能量和距離的分簇多跳算法。第一層簇頭選擇時(shí)考慮了節(jié)點(diǎn)的剩余能量，第二層簇頭充分考慮了節(jié)點(diǎn)能量和到基站的距離，并且改進(jìn)了簇內(nèi)節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)方式。仿真結(jié)果表明，與LEACH算法相比，該算法均衡了網(wǎng)絡(luò)的能量消耗，明顯延長了網(wǎng)絡(luò)的生命周期。

參考文獻(xiàn)

[1]孫利民，葉馳，廖勇，等.傳感器網(wǎng)絡(luò)的路由機(jī)制[J].計(jì)算機(jī)科學(xué)，2004，31(3):54-57.

[2]HEINZELMAN Wendi B， CHANDRAKASAN A P， BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Maui: IEEE Computer Society， 2000: 3005-3014.

[3]HEINZELMAN W B， CHANDRAKASAN A P， BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Trans. on Wireless Communication， 2002(1): 660-670.

[4]杜玉紅，張曉敏，蔡成聞，等.無線傳感器網(wǎng)絡(luò)能量均衡自適應(yīng)分簇算法[J].傳感技術(shù)學(xué)報(bào)，2007(7):1616-1619.

[5]FAN Xiang-ning， SONG Yu-lin. Improvemente on LEACH proto-col of wireless sensor network[J]. International Conference on Sensor Technologies and Application， 2007: 260-264.

[6]湯波，羅昌俊，周明天.能量均衡的無線傳感器網(wǎng)絡(luò)分簇方法[J].計(jì)算機(jī)應(yīng)用研究，2008，3(25):878-880.

[7]尚鳳軍，雷陽.無線傳感器網(wǎng)絡(luò)能量有效成簇算法研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2009，5(30):839-842.

[8]ZHANG Wen-ya， LIANG Zi-ze.A power efficient routing protocol forwireless sensor network[C]//Proceedings of the 2007 IEEE International Conference on Networking，Sensing and Control. Washington DC: IEEE Computer Society， 2007: 20-25.