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

柳 平,陳 歡,石中華,呂金風(fēng)

(汕頭大學(xué)電子工程系,廣東汕頭 515063)

隨著傳感技術(shù)、嵌入式技術(shù)以及低功耗無線通信技術(shù)的發(fā)展,生產(chǎn)具備感應(yīng)、無線通信以及信息處理能力的微型無線傳感器已成為可能.這些傳感器節(jié)點(diǎn)之間通過相互協(xié)作,將其監(jiān)測和感應(yīng)的多種環(huán)境信息(如溫度和濕度等)傳送到基站進(jìn)行處理,無線傳感器網(wǎng)絡(luò)廣泛應(yīng)用在國防軍事、救急和環(huán)境監(jiān)測等領(lǐng)域[1-2].與無線移動(dòng)自組網(wǎng)不同,無線傳感器網(wǎng)絡(luò)一般具有較大的節(jié)點(diǎn)密度且沒有IP地址,同時(shí)由于受到成本和體積等原因限制,無線傳感器節(jié)點(diǎn)的處理能力低并且無線帶寬以及電池容量等資源匱乏.在大多數(shù)應(yīng)用中,傳感器節(jié)點(diǎn)被部署后就無法對(duì)其充電,這使得如何提高網(wǎng)絡(luò)生存時(shí)間成為無線傳感器網(wǎng)絡(luò)研究主要方向之一.

1 LEACH協(xié)議

LEACH[3](Low Energy Adaptive Clustering Hierarchy)是一種分層路由協(xié)議,它的基本思想是網(wǎng)絡(luò)周期地選擇簇頭節(jié)點(diǎn),將整個(gè)網(wǎng)絡(luò)的負(fù)載平均分配到每個(gè)節(jié)點(diǎn),普通節(jié)點(diǎn)按照就近原則加入到相應(yīng)的簇頭.簇內(nèi)節(jié)點(diǎn)將感知數(shù)據(jù)發(fā)送到簇頭,簇頭節(jié)點(diǎn)收集所有簇內(nèi)節(jié)點(diǎn)發(fā)送來的數(shù)據(jù)并進(jìn)行處理,最后簇頭將處理后數(shù)據(jù)直接傳送到基站.

LEACH協(xié)議每個(gè)周期(輪)由初始化和穩(wěn)定工作兩個(gè)階段組成.在初始化階段時(shí),網(wǎng)絡(luò)隨機(jī)選擇節(jié)點(diǎn)作為簇頭,成為簇頭的節(jié)點(diǎn)向網(wǎng)絡(luò)廣播其成為簇頭消息,普通節(jié)點(diǎn)接收到該消息后,根據(jù)就近原則判斷應(yīng)該選擇哪個(gè)簇頭,然后向該簇頭發(fā)送加入消息.在穩(wěn)定工作階段,簇內(nèi)節(jié)點(diǎn)把監(jiān)測到數(shù)據(jù)發(fā)送到簇頭,簇頭對(duì)數(shù)據(jù)進(jìn)行處理后直接發(fā)送到基站.本周期內(nèi)任務(wù)完成后,馬上進(jìn)入下一個(gè)周期.

簇頭選擇是 LEACH協(xié)議關(guān)鍵,具體方法如下:每個(gè)傳感器節(jié)點(diǎn)選擇[0,1]之間的一個(gè)隨機(jī)數(shù),如果產(chǎn)生隨機(jī)數(shù)值小于閾值T(n)[3],那么這個(gè)傳感器節(jié)點(diǎn)就成為簇頭.整個(gè)網(wǎng)絡(luò)選出的期望簇頭個(gè)數(shù)為

2 ECHT協(xié)議

圖1 每輪時(shí)隙圖Fig.1 Time slot at each round

LEACH協(xié)議及改進(jìn)協(xié)議[4-5]采用周期地隨機(jī)選擇簇頭,避免了簇頭過度消耗能量,同時(shí)簇頭利用數(shù)據(jù)融合技術(shù)減少了網(wǎng)絡(luò)數(shù)據(jù)通信量.但由于簇頭直接與基站通信,對(duì)于比較大的網(wǎng)絡(luò),將消耗較多能量,而且動(dòng)態(tài)分簇有帶來額外開銷.針對(duì)以上問題,本文提出了一種基于時(shí)間均勻分簇混合路由協(xié)議(ECHT).

在網(wǎng)絡(luò)建立階段,基站需要用足夠大的發(fā)送功率向全網(wǎng)絡(luò)廣播信息.網(wǎng)絡(luò)中節(jié)點(diǎn)根據(jù)基站的發(fā)送功率計(jì)算出到基站的近似距離,利用此距離可以調(diào)節(jié)向基站發(fā)送數(shù)據(jù)所需的發(fā)送功率.ECHT協(xié)議包括分簇和數(shù)據(jù)傳輸兩個(gè)階段,分簇階段又可以分為簇頭選擇和簇的形成兩部分,數(shù)據(jù)傳輸階段也分為簇內(nèi)數(shù)據(jù)傳輸和簇頭間數(shù)據(jù)傳輸.為了使簇內(nèi)信息進(jìn)行交流,該協(xié)議引入了簇內(nèi)信息交流階段.它們在每一輪中有對(duì)應(yīng)時(shí)隙,如圖1所示.

2.1 簇頭選擇

在無線傳感器網(wǎng)絡(luò)中,當(dāng)每輪進(jìn)行簇頭選擇時(shí),首先傳感器節(jié)點(diǎn)根據(jù)剩余能量計(jì)算出其廣播成為簇頭的CLUSTER-HEAD-MSG消息的時(shí)間,其表達(dá)式為

式中:T1為在每輪中簇頭選擇時(shí)間;Ei表示節(jié)點(diǎn)i剩余能量;Ea,Emin和Emax分別表示上一輪節(jié)點(diǎn)i所在簇內(nèi)的平均剩余能量、最小剩余能量和最大剩余能量.ni∈(0,1)隨機(jī)數(shù),用于避讓相同剩余能量節(jié)點(diǎn)廣播消息引起的沖突.

在每輪簇頭選擇時(shí),所有節(jié)點(diǎn)按照自身競選時(shí)間來廣播CLUSTER-HEAD-MSG消息.因此,剩余能量高的節(jié)點(diǎn),先廣播該消息,它的廣播半徑是為競爭半徑,如式(3)所示.

其中A為監(jiān)測區(qū)域的面積,k為期望簇頭的個(gè)數(shù).

當(dāng)普通節(jié)點(diǎn)接收到CLUSTER-HEAD-MSG消息后,將不廣播其消息并記錄發(fā)送節(jié)點(diǎn)的信息.當(dāng)簇頭接收到CLUSTER-HEAD-MSG消息后,不做任何處理.經(jīng)過時(shí)間T1后,網(wǎng)絡(luò)中簇頭全部選出.

2.2 簇的形成

簇頭選擇完成后,如果普通節(jié)點(diǎn)只接收到一個(gè)簇頭發(fā)送來的CLUSTER-HEAD MSG 消息,就選擇該簇頭.如果接收到多個(gè)簇頭發(fā)送來的CLUSTER-HEAD MSG 消息,就選擇簇內(nèi)通信代價(jià)最小亦即接收信號(hào)強(qiáng)度最大的簇頭.當(dāng)普通節(jié)點(diǎn)選擇其簇頭后,就發(fā)送加入JOIN-CLUSTER-MAG消息通知該簇頭.簇頭接收到該消息后,進(jìn)行構(gòu)建TDMA調(diào)度表并將它發(fā)送給簇內(nèi)所有節(jié)點(diǎn),確保簇內(nèi)所有節(jié)點(diǎn)發(fā)送數(shù)據(jù)沒有碰撞,同時(shí)可以讓節(jié)點(diǎn)除了自身工作時(shí)間外進(jìn)入休眠,節(jié)省節(jié)點(diǎn)能量.

2.3 數(shù)據(jù)傳輸

在簇頭間傳輸數(shù)據(jù)之前,基站構(gòu)建 TDMA調(diào)度表并發(fā)送給網(wǎng)絡(luò)中每一個(gè)簇頭,TDMA調(diào)度表規(guī)定遠(yuǎn)離基站的簇頭先發(fā)送數(shù)據(jù),靠近基站簇頭后發(fā)送并轉(zhuǎn)發(fā)數(shù)據(jù),因此,這可以避免簇頭多次轉(zhuǎn)發(fā)其它簇頭發(fā)來的數(shù)據(jù).

首先簇頭收集從簇內(nèi)成員節(jié)點(diǎn)發(fā)送來數(shù)據(jù),并進(jìn)行數(shù)據(jù)融合,然后把數(shù)據(jù)發(fā)送給中繼簇頭或基站.中繼簇頭只是簡單轉(zhuǎn)發(fā)來自其它簇頭的數(shù)據(jù),而不能進(jìn)行數(shù)據(jù)融合.

在簇頭間傳輸數(shù)據(jù)開始時(shí),每個(gè)簇頭以相同的功率向全網(wǎng)絡(luò)廣播NODE-STATE MSG 消息,它包含簇頭的ID、當(dāng)前剩余能量和到基站的距離.如果簇頭i收到由簇頭j廣播一條消息NODE-STATEMSG,計(jì)算出兩者距離.ECHT協(xié)議定義簇頭的中繼簇頭集合

采用無線通信能量消耗模型[3],發(fā)送數(shù)據(jù)能量消耗與距離的平方或4次方成比.簇頭i從中繼簇頭集合選擇簇頭作為下一跳,如果選擇離自己近的簇頭作為下一跳,可以減少簇頭i的能量消耗,但會(huì)使得靠近基站的簇頭轉(zhuǎn)發(fā)更多其它簇頭發(fā)送來的數(shù)據(jù),消耗更多能量.如果選擇離自己較遠(yuǎn)簇頭作為下一跳,可以減少靠近基站的簇頭轉(zhuǎn)發(fā)其它簇頭發(fā)送來的數(shù)據(jù)量,但是會(huì)增加簇頭i能量消耗.綜上所述,本文定義了一個(gè)轉(zhuǎn)發(fā)代價(jià)函數(shù)f(i,j),如式(5),表示簇頭i把中繼簇頭集合的簇頭j作為下一跳代價(jià).

式中:Ei是簇頭i的剩余能量;Ej是簇頭j的剩余能量;w∈[0,1]是代價(jià)函數(shù)權(quán)值;Eij是簇頭i發(fā)送L比特?cái)?shù)據(jù)(它包括簇頭i產(chǎn)生數(shù)據(jù)和轉(zhuǎn)發(fā)其它簇頭數(shù)據(jù))到簇頭j能量消耗;dij是簇頭i與簇頭j之間距離;EjBS是簇頭j發(fā)送L+k比特?cái)?shù)據(jù)(包括接收簇頭i發(fā)送L比特?cái)?shù)據(jù)和簇頭j本身產(chǎn)生數(shù)據(jù))到簇頭基站(基站)能量消耗;是基站與簇頭j之間距離;ER是簇頭j接收簇頭i發(fā)送L比特?cái)?shù)據(jù)消耗能量.

當(dāng)簇頭j屬于簇頭i中繼簇頭集合,代價(jià)函數(shù)第一部分表示采取多跳通信代價(jià),選擇與自己距離最短的簇頭作為下一跳,第二部分表示單跳通信代價(jià),選擇離基站最近簇頭作為下一跳,通過調(diào)節(jié)w來權(quán)衡多跳和單跳通信,當(dāng)w=1時(shí),簇頭i選擇最近簇頭作為下一跳.當(dāng)w=0時(shí),簇頭i選擇基站作為下一跳.總之,簇頭i從中繼簇頭集合和基站中選擇其轉(zhuǎn)發(fā)代價(jià)函數(shù)最小的簇頭作為下一跳.

在簇頭間傳輸數(shù)據(jù)結(jié)束后,該協(xié)議進(jìn)入簇內(nèi)信息交流階段,各簇內(nèi)成員節(jié)點(diǎn)把自身剩余能量信息發(fā)送到簇頭,簇頭接收該信息并計(jì)算出簇內(nèi)平均剩余能量Ea、最小剩余能量Emin和最大剩余能量Emax,然后向簇內(nèi)廣播一條CLUSTER ENERGY-MSG消息,它包含

3 仿真及結(jié)果分析

3.1 仿真模型和參數(shù)

在仿真環(huán)境中,400個(gè)無線傳感器節(jié)點(diǎn)隨機(jī)分布在200m×200m二維平面區(qū)域內(nèi),基站(基站)位于(100,250)的位置,圖2所示為無線傳感器節(jié)點(diǎn)在監(jiān)測區(qū)域中的分布圖.仿真時(shí)所使用參數(shù)設(shè)置見表1.

表1 仿真參數(shù)Tab.1 Simulation param eters

圖2 無線傳感器節(jié)點(diǎn)隨機(jī)分布圖Fig.2 Wirelesssensor node random distribu tion

圖3 仿真流程圖Fig.3 Simulation flow figure

3.2 實(shí)驗(yàn)仿真步驟

在實(shí)驗(yàn)過程中,通過上述的無線傳感網(wǎng)絡(luò)模型分別使用LEACH協(xié)議與ECHT協(xié)議進(jìn)行仿真,大致的仿真流程如圖3所示.

如圖3所示,實(shí)驗(yàn)包含了主循環(huán),該循環(huán)進(jìn)行了包括了2.3數(shù)據(jù)傳輸中提到的簇集內(nèi)數(shù)據(jù)傳輸開銷、簇頭間數(shù)據(jù)傳輸開銷等的計(jì)算,計(jì)算開銷的依據(jù)是傳輸不同數(shù)據(jù)包、不同傳送距離是能量的消耗.一個(gè)節(jié)點(diǎn)由于產(chǎn)生能量消耗,當(dāng)能量耗完時(shí)死亡,整個(gè)主循環(huán)通過判斷是否全部節(jié)點(diǎn)死亡來確定繼續(xù)與否.在循環(huán)中記錄的信息包括第一個(gè)死亡的節(jié)點(diǎn),最后一個(gè)死亡的節(jié)點(diǎn),以及簇頭的情況.依據(jù)上述的仿真流程,分別對(duì)兩種協(xié)議 LEACH、ECHT進(jìn)行仿真,記錄結(jié)果并進(jìn)行比對(duì),從而獲得協(xié)議算法的優(yōu)劣.

3.3 實(shí)驗(yàn)結(jié)果分析

圖4 各種協(xié)議生成簇頭分布F ig.4 C luster head distribu tion for various protocol

簇頭在網(wǎng)絡(luò)中的分布將會(huì)很大程度影響網(wǎng)絡(luò)性能,如果簇頭在網(wǎng)絡(luò)中分布均勻,網(wǎng)絡(luò)覆蓋率將提高,同時(shí)減少網(wǎng)絡(luò)能量消耗.否則,網(wǎng)絡(luò)覆蓋率降低,網(wǎng)絡(luò)能量消耗增加.從每種分簇協(xié)議的模擬過程中隨機(jī)選取一輪,觀察每種分簇協(xié)議產(chǎn)生簇頭在網(wǎng)絡(luò)中分布情況,如圖4所示. LEACH協(xié)議生成簇頭分布不均勻,而ECHT協(xié)議產(chǎn)生的簇頭在網(wǎng)絡(luò)中分布均勻,原因是LEACH協(xié)議采用隨機(jī)數(shù)與閾值的機(jī)制產(chǎn)生簇頭,沒有考慮簇頭之間的距離.ECHT協(xié)議通過網(wǎng)絡(luò)節(jié)點(diǎn)競爭半徑進(jìn)行局部競爭,使得簇頭分布均勻.

在網(wǎng)絡(luò)拓?fù)涔潭ㄇ闆r下,一個(gè)穩(wěn)定的分簇協(xié)議應(yīng)該產(chǎn)生比較一致的簇頭,優(yōu)化網(wǎng)絡(luò)的能量消耗.圖5是每種分簇協(xié)議在整個(gè)網(wǎng)絡(luò)周期中生成相同簇頭數(shù)目的輪數(shù)對(duì)比,從圖中可以看出,每種協(xié)議生成的簇頭數(shù)目都有一個(gè)期望值,也是協(xié)議在此仿真環(huán)境下最優(yōu)的簇頭數(shù)目.ECHT協(xié)議產(chǎn)生的簇頭數(shù)量穩(wěn)定,LEACH產(chǎn)生簇頭數(shù)量的波動(dòng)范圍最大,這是因?yàn)長EACH協(xié)議單純采用隨機(jī)概率與閾值的機(jī)制產(chǎn)生簇頭,因此簇頭數(shù)量變化比較明顯.ECHT協(xié)議簇頭數(shù)量變化比較集中,該協(xié)議采用了局部區(qū)域競爭的方法,有效地控制了協(xié)議所生成的簇頭數(shù)量.總的來說,ECHT協(xié)議產(chǎn)生的簇頭數(shù)量比較穩(wěn)定,可靠性較好.

網(wǎng)絡(luò)生命周期定義為網(wǎng)絡(luò)中出現(xiàn)第一個(gè)節(jié)點(diǎn)死亡的時(shí)間[6],還可以定義為網(wǎng)絡(luò)中大部分節(jié)點(diǎn)死亡的時(shí)間.網(wǎng)絡(luò)節(jié)點(diǎn)死亡可能導(dǎo)致基站對(duì)于監(jiān)測區(qū)域判斷準(zhǔn)確性下降,因此,本文把網(wǎng)絡(luò)生命周期定義為網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)死亡的時(shí)間,它是評(píng)價(jià)網(wǎng)絡(luò)性能的重要指標(biāo)之一.

圖6是LEACH和ECHT協(xié)議網(wǎng)絡(luò)生命周期比較,從圖中可以看出,ECHT協(xié)議的網(wǎng)絡(luò)生命周期長,LEACH協(xié)議短.原因是ECHT協(xié)議采用時(shí)間驅(qū)動(dòng)簇頭選擇,可以降低消息復(fù)雜度和節(jié)省節(jié)點(diǎn)能量.從第一個(gè)節(jié)點(diǎn)死亡到最后死亡節(jié)點(diǎn)的時(shí)間跨度可以反映網(wǎng)絡(luò)中節(jié)點(diǎn)能量均衡情況,跨度越短說明網(wǎng)絡(luò)能量利用率越高效,ECHT協(xié)議跨度短,LEACH跨度大.原因是ECHT協(xié)議選出剩余能量較高的節(jié)點(diǎn)作為簇頭,而LEACH協(xié)議隨機(jī)產(chǎn)生簇頭,沒有考慮節(jié)點(diǎn)剩余能量,可能選出的簇頭能量低,這樣會(huì)加速節(jié)點(diǎn)死亡.

圖5 各種協(xié)議簇頭數(shù)量對(duì)比Fig.5 The number of cluster head com parison for various protocol

圖6 網(wǎng)絡(luò)生命周期Fig.6 Netw ork lifetime

4 結(jié) 論

針對(duì)LEACH協(xié)議的不足,提出了一種基于時(shí)間均勻分簇混合路由協(xié)議,該協(xié)議采用了時(shí)間驅(qū)動(dòng)簇頭選擇方法和混合通信機(jī)制,降低了算法消息復(fù)雜度,它具有以下特點(diǎn):①該分簇路由協(xié)議算法穩(wěn)定,所生成簇的數(shù)目波動(dòng)小;②能有效均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗,延長網(wǎng)絡(luò)生命周期.

[1] Estrin D,Girod L,PottieG,et al.Instrumenting the World with Wireless Sensor Networks[C].In:Proc.of the Int'l Con f.on Acoustics,Speech,and Signal Processing(ICASSP 2001),2001.

[2] Pottie G J,KaiserWJ.Wireless integrated network sensors[J].Communications of the ACM,2000,43(5):51-58.

[3] Heinzelman WR,Chand rakasanA P,Balak rishnan H.An application specific protocol architecture for wirelessm icrosensor networks[J].IEEE Trans on Wireless Communic-ations,2002,1(4):660-670.

[4] Lu Tao,Zhu Qingxin,Zhang Luqiao.An Improvement for LEACH Algorithm in Wireless Sensor Network[C].Industrial Electronics and Applications(ICIEA),2010 the 5th IEEE Conference on.,2010:1811-1814.

[5] 廖明華,張華,王東.基于LEACH協(xié)議的簇頭選舉改進(jìn)算法[J].計(jì)算機(jī)工程,2011,37(7):112-114.

Liao Minghua,Zhang Hua,Wang Dong.Improved cluster-head election algorithm based on LEACH p rotocol[J].Computer Engineering,2011,37(7):112-114.(in Chinese)

[6] Chang JH,Tassiulas L.Maximum lifetime routing in wireles sensor netw orks[J].IEEE/ACMTrans.on Netw orking, 2004,12(4):609-619.