一種無線傳感器網(wǎng)絡分簇路由算法研究

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

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

中圖分類號:TP393 文獻標識碼:A

文章編號: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 引 言

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

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

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

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

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

1 系統(tǒng)模型

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

(1) 所有傳感器節(jié)點部署后不再移動，且都有1個惟一的標識ID;

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

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

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

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

這里采用與文獻[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基礎上，提出一個基于能量和距離的分簇算法(clustering algorithm based on energy and distance)。該算法按輪運行，每輪分為二層簇頭的建立，簇內節(jié)點數(shù)據(jù)轉發(fā)和穩(wěn)定數(shù)據(jù)的傳輸。

2.1 二層簇頭的建立

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

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

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

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

2.2 簇內節(jié)點數(shù)據(jù)轉發(fā)

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

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

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

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

圖1 簇內節(jié)點數(shù)據(jù)轉發(fā)方式圖

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

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

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

3 算法分析和仿真結果

利用Matlab工具對LEACH，EBAC和CAED算法進行仿真比較，各項參數(shù)設置如下:假設無線傳感器網(wǎng)絡由300個相同的節(jié)點組成，隨機拋撒在200 m×200 m的區(qū)域內，遠程基站的坐標是(x=100 m，y=350 m)。每個節(jié)點的初始能量為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)時dd0。其中，d0為常數(shù)[1]，數(shù)據(jù)包長度為4 200 b，廣播包長度為60 b，簇頭個數(shù)kopt=5。節(jié)點能量低于Eth=0.000 1 J時，認為其死亡，假設數(shù)據(jù)融合率為100%，且在轉發(fā)過程中無數(shù)據(jù)包丟失，沒有誤碼率。

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

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

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

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

首節(jié)點失效輪數(shù)30%節(jié)點失效輪數(shù)800輪時節(jié)點的失效個數(shù)

LEACH108235245

EBAC4341 09435

CAED7231 31211

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

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

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

4 結 語

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

參考文獻

[1]孫利民，葉馳，廖勇，等.傳感器網(wǎng)絡的路由機制[J].計算機科學，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)絡能量均衡自適應分簇算法[J].傳感技術學報，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)絡分簇方法[J].計算機應用研究，2008，3(25):878-880.

[7]尚鳳軍，雷陽.無線傳感器網(wǎng)絡能量有效成簇算法研究[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.