基于LEACH協議的改進路由算法*

柳 平,陳 歡,石中華,呂金風

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

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

1 LEACH協議

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

LEACH協議每個周期(輪)由初始化和穩定工作兩個階段組成.在初始化階段時,網絡隨機選擇節點作為簇頭,成為簇頭的節點向網絡廣播其成為簇頭消息,普通節點接收到該消息后,根據就近原則判斷應該選擇哪個簇頭,然后向該簇頭發送加入消息.在穩定工作階段,簇內節點把監測到數據發送到簇頭,簇頭對數據進行處理后直接發送到基站.本周期內任務完成后,馬上進入下一個周期.

簇頭選擇是 LEACH協議關鍵,具體方法如下:每個傳感器節點選擇[0,1]之間的一個隨機數,如果產生隨機數值小于閾值T(n)[3],那么這個傳感器節點就成為簇頭.整個網絡選出的期望簇頭個數為

2 ECHT協議

圖1 每輪時隙圖Fig.1 Time slot at each round

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

在網絡建立階段,基站需要用足夠大的發送功率向全網絡廣播信息.網絡中節點根據基站的發送功率計算出到基站的近似距離,利用此距離可以調節向基站發送數據所需的發送功率.ECHT協議包括分簇和數據傳輸兩個階段,分簇階段又可以分為簇頭選擇和簇的形成兩部分,數據傳輸階段也分為簇內數據傳輸和簇頭間數據傳輸.為了使簇內信息進行交流,該協議引入了簇內信息交流階段.它們在每一輪中有對應時隙,如圖1所示.

2.1 簇頭選擇

在無線傳感器網絡中,當每輪進行簇頭選擇時,首先傳感器節點根據剩余能量計算出其廣播成為簇頭的CLUSTER-HEAD-MSG消息的時間,其表達式為

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

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

其中A為監測區域的面積,k為期望簇頭的個數.

當普通節點接收到CLUSTER-HEAD-MSG消息后,將不廣播其消息并記錄發送節點的信息.當簇頭接收到CLUSTER-HEAD-MSG消息后,不做任何處理.經過時間T1后,網絡中簇頭全部選出.

2.2 簇的形成

簇頭選擇完成后,如果普通節點只接收到一個簇頭發送來的CLUSTER-HEAD MSG 消息,就選擇該簇頭.如果接收到多個簇頭發送來的CLUSTER-HEAD MSG 消息,就選擇簇內通信代價最小亦即接收信號強度最大的簇頭.當普通節點選擇其簇頭后,就發送加入JOIN-CLUSTER-MAG消息通知該簇頭.簇頭接收到該消息后,進行構建TDMA調度表并將它發送給簇內所有節點,確保簇內所有節點發送數據沒有碰撞,同時可以讓節點除了自身工作時間外進入休眠,節省節點能量.

2.3 數據傳輸

在簇頭間傳輸數據之前,基站構建 TDMA調度表并發送給網絡中每一個簇頭,TDMA調度表規定遠離基站的簇頭先發送數據,靠近基站簇頭后發送并轉發數據,因此,這可以避免簇頭多次轉發其它簇頭發來的數據.

首先簇頭收集從簇內成員節點發送來數據,并進行數據融合,然后把數據發送給中繼簇頭或基站.中繼簇頭只是簡單轉發來自其它簇頭的數據,而不能進行數據融合.

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

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

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

當簇頭j屬于簇頭i中繼簇頭集合,代價函數第一部分表示采取多跳通信代價,選擇與自己距離最短的簇頭作為下一跳,第二部分表示單跳通信代價,選擇離基站最近簇頭作為下一跳,通過調節w來權衡多跳和單跳通信,當w=1時,簇頭i選擇最近簇頭作為下一跳.當w=0時,簇頭i選擇基站作為下一跳.總之,簇頭i從中繼簇頭集合和基站中選擇其轉發代價函數最小的簇頭作為下一跳.

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

3 仿真及結果分析

3.1 仿真模型和參數

在仿真環境中,400個無線傳感器節點隨機分布在200m×200m二維平面區域內,基站(基站)位于(100,250)的位置,圖2所示為無線傳感器節點在監測區域中的分布圖.仿真時所使用參數設置見表1.

表1 仿真參數Tab.1 Simulation param eters

圖2 無線傳感器節點隨機分布圖Fig.2 Wirelesssensor node random distribu tion

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

3.2 實驗仿真步驟

在實驗過程中,通過上述的無線傳感網絡模型分別使用LEACH協議與ECHT協議進行仿真,大致的仿真流程如圖3所示.

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

3.3 實驗結果分析

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

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

在網絡拓撲固定情況下,一個穩定的分簇協議應該產生比較一致的簇頭,優化網絡的能量消耗.圖5是每種分簇協議在整個網絡周期中生成相同簇頭數目的輪數對比,從圖中可以看出,每種協議生成的簇頭數目都有一個期望值,也是協議在此仿真環境下最優的簇頭數目.ECHT協議產生的簇頭數量穩定,LEACH產生簇頭數量的波動范圍最大,這是因為LEACH協議單純采用隨機概率與閾值的機制產生簇頭,因此簇頭數量變化比較明顯.ECHT協議簇頭數量變化比較集中,該協議采用了局部區域競爭的方法,有效地控制了協議所生成的簇頭數量.總的來說,ECHT協議產生的簇頭數量比較穩定,可靠性較好.

網絡生命周期定義為網絡中出現第一個節點死亡的時間[6],還可以定義為網絡中大部分節點死亡的時間.網絡節點死亡可能導致基站對于監測區域判斷準確性下降,因此,本文把網絡生命周期定義為網絡中第一個節點死亡的時間,它是評價網絡性能的重要指標之一.

圖6是LEACH和ECHT協議網絡生命周期比較,從圖中可以看出,ECHT協議的網絡生命周期長,LEACH協議短.原因是ECHT協議采用時間驅動簇頭選擇,可以降低消息復雜度和節省節點能量.從第一個節點死亡到最后死亡節點的時間跨度可以反映網絡中節點能量均衡情況,跨度越短說明網絡能量利用率越高效,ECHT協議跨度短,LEACH跨度大.原因是ECHT協議選出剩余能量較高的節點作為簇頭,而LEACH協議隨機產生簇頭,沒有考慮節點剩余能量,可能選出的簇頭能量低,這樣會加速節點死亡.

圖5 各種協議簇頭數量對比Fig.5 The number of cluster head com parison for various protocol

圖6 網絡生命周期Fig.6 Netw ork lifetime

4 結 論

針對LEACH協議的不足,提出了一種基于時間均勻分簇混合路由協議,該協議采用了時間驅動簇頭選擇方法和混合通信機制,降低了算法消息復雜度,它具有以下特點:①該分簇路由協議算法穩定,所生成簇的數目波動小;②能有效均衡網絡中節點的能量消耗,延長網絡生命周期.

[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協議的簇頭選舉改進算法[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.