沈海燕，廖惜春，劉玉錕

?

基于梯度與數(shù)據(jù)流機制的WSN分簇路由協(xié)議

沈海燕，廖惜春，劉玉錕

（五邑大學(xué) 信息工程學(xué)院，廣東 江門 529020）

針對無線傳感器網(wǎng)絡(luò)的能量受限和網(wǎng)絡(luò)壽命有限的問題，結(jié)合梯度和數(shù)據(jù)流機制，對經(jīng)典的LEACH分簇路由協(xié)議中簇頭的選舉及簇內(nèi)通信方式進行了改進. Matlab的仿真結(jié)果表明，改進后的基于梯度與數(shù)據(jù)流機制的分簇路由協(xié)議與LEACH協(xié)議相比，能更為有效地節(jié)約節(jié)點能量，使網(wǎng)絡(luò)壽命延長約50%～65%.

無線傳感器網(wǎng)絡(luò)；分簇路由；LEACH協(xié)議；梯度；數(shù)據(jù)流機制

無線傳感器網(wǎng)絡(luò)（wireless sensor network，WSN）是由大量部署在監(jiān)測區(qū)域內(nèi)的傳感器節(jié)點組成的，部署的節(jié)點通過采集網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)對象的信息，采用多跳的無線通信方式，將節(jié)點收集、處理后的信息提供給目標用戶. 路由協(xié)議是在路由指導(dǎo)IP數(shù)據(jù)包發(fā)送過程中事先約定好的規(guī)定和標準，WSN的路由協(xié)議在網(wǎng)絡(luò)數(shù)據(jù)的傳輸過程中起著舉足輕重的作用. 由于WSN中的能耗問題影響到整個網(wǎng)絡(luò)的壽命，因此，低功耗高性能的路由協(xié)議一直是研究的熱點[1-4]. 目前，針對WSN中的路由機制，國內(nèi)外的學(xué)者己經(jīng)作了大量的分析和研究，對節(jié)點分簇是無線傳感器網(wǎng)絡(luò)中節(jié)約能源的一種有效方案，其中LEACH（low-energy adaptive clustering hierarchy）[5]3006是最早的WSN分簇路由協(xié)議. 本文研究并改進LEACH協(xié)議，針對傳感器網(wǎng)絡(luò)節(jié)點能量異構(gòu)的情況設(shè)計更適合于傳感器網(wǎng)絡(luò)特點的分簇路由協(xié)議——基于梯度與數(shù)據(jù)流機制的分簇路由協(xié)議.

1 LEACH算法

1.1 LEACH算法的描述

LEACH的基本思想是通過等概率的隨機循環(huán)選擇簇頭，使得整個網(wǎng)絡(luò)的能耗盡可能地平均分配到每個傳感器節(jié)點，從而達到降低網(wǎng)絡(luò)能量耗費、延長網(wǎng)絡(luò)生命周期的目的[5]3005.

LEACH在運行過程中不斷地周期性循環(huán)執(zhí)行簇的重構(gòu). 算法操作使用“輪”的概念. 每一輪由初始化和穩(wěn)定的工作兩個階段組成. 初始化階段，每個節(jié)點產(chǎn)生介于0與1之間的一個隨機數(shù)，若節(jié)點產(chǎn)生的這個隨機數(shù)小于閾值()，則該節(jié)點向周圍節(jié)點廣播它成為簇頭節(jié)點的消息.()的計算公式為：

其中，是簇頭占所有節(jié)點的百分比，即節(jié)點當選簇頭的概率；是目前循環(huán)已進行的輪數(shù)；是最近1/輪中還未當選過簇頭的剩余節(jié)點的集合. 從式（1）可以看出，當選過簇頭的節(jié)點在接下來的1/輪循環(huán)中將不能成為簇頭，剩余節(jié)點當選簇頭的閾值()增大，節(jié)點產(chǎn)生小于()的隨機數(shù)的概率隨之增大，所以節(jié)點當選簇頭的概率增大[5]3012,[6].

非簇頭節(jié)點根據(jù)接收到各個簇頭節(jié)點的信號強弱來選擇加入到哪個簇，并發(fā)出信息通知相應(yīng)的簇頭節(jié)點. 當網(wǎng)絡(luò)進入穩(wěn)定階段后，簇內(nèi)的節(jié)點通過TDMA方式與簇頭節(jié)點進行通信[7]，簇頭接收簇內(nèi)其他節(jié)點發(fā)送的數(shù)據(jù)，將這些數(shù)據(jù)進行融合后發(fā)送給匯聚節(jié)點，在匯聚節(jié)點再次進行數(shù)據(jù)融合后發(fā)送給基站. 其中，數(shù)據(jù)融合技術(shù)是指對有用信息的采集、傳輸及在一定準則下加以自動分析、綜合，以輔助人們進行態(tài)勢和環(huán)境判定、分析的一種信息處理方法. 信息源經(jīng)由路由協(xié)議傳輸?shù)酱仡^節(jié)點和匯聚節(jié)點，在簇頭節(jié)點及匯聚節(jié)點再進行數(shù)據(jù)融合，這樣既定義了信息的傳輸標準，又簡化了需要傳輸?shù)臄?shù)據(jù)量.

1.2 LEACH算法的不足

LEACH算法是基于這樣的假設(shè)的：所有傳感器節(jié)點都可以直接和匯聚節(jié)點通信. 但是在實際的應(yīng)用中，當網(wǎng)絡(luò)的規(guī)模較大時，每個傳感器節(jié)點都可以直接與匯聚節(jié)點通信的概率很小. 由于LEACH算法采用產(chǎn)生隨機數(shù)與()比較來產(chǎn)生簇頭，這樣有可能出現(xiàn)簇頭非均勻分布[7-8]，如圖1所示. 其中，“☆”代表普通節(jié)點，“○”代表簇頭節(jié)點. 可見，LEACH算法不能保證簇頭在網(wǎng)絡(luò)中的均勻性分布. 當簇頭節(jié)點分布不夠均勻時，簇內(nèi)通信就不能滿足自由空間(free space)模型，這將導(dǎo)致較大的能耗.

圖1 LEACH簇頭分布示意圖

2 基于梯度與數(shù)據(jù)流機制的分簇路由協(xié)議

針對LEACH協(xié)議存在的問題，本課題研究的目的是讓簇頭節(jié)點盡可能均勻分布，并使每個簇的大小相近，使簇頭與匯聚節(jié)點的通信距離趨于平衡，進而減少通信開銷. 梯度路由與數(shù)據(jù)流機制結(jié)合的分簇路由算法將能有效地解決此問題. 該算法的主要思路是：在簇頭的產(chǎn)生和簇內(nèi)數(shù)據(jù)傳輸方面分別運用梯度路由機制和數(shù)據(jù)流機制作了改進，其余部分與LEACH協(xié)議基本一致. 基于梯度的路由機制[9]的原理是在能量模型基礎(chǔ)上建立路由梯度，沿梯度變化最快的方向傳輸數(shù)據(jù)，減小通信開銷. 數(shù)據(jù)流機制的基本思路是當某節(jié)點有數(shù)據(jù)流通過時，新的數(shù)據(jù)不再通過該節(jié)點，以減少網(wǎng)絡(luò)延遲和節(jié)點能量消耗的不平衡，延長網(wǎng)絡(luò)壽命[10-13].

本文對LEACH的改進和設(shè)計的步驟如下：

Step1：建立梯度和鄰居表（梯度機制）

2）當節(jié)點收到節(jié)點廣播梯度的消息時，則節(jié)點檢查自身的鄰居表中是否已經(jīng)有了節(jié)點的信息，若沒有，則將節(jié)點加入到節(jié)點的鄰居表，鄰居表也同時保存鄰居節(jié)點的梯度信息. 若已經(jīng)有了節(jié)點的信息，則更新節(jié)點的梯度.

4）當節(jié)點自身梯度發(fā)生改變后，向鄰居節(jié)點廣播自身梯度.

Step2：簇頭選舉

Step3：簇的形成

Step4：簇內(nèi)通信（數(shù)據(jù)流機制）

每個簇頭節(jié)點產(chǎn)生一個TDMA時隙表，簇成員只在自己的時隙內(nèi)發(fā)送數(shù)據(jù)，其余時間進入休眠狀態(tài)以節(jié)約能源. 簇頭節(jié)點整合簇內(nèi)數(shù)據(jù)后，從它的鄰居表中選擇梯度值小于簇頭節(jié)點的梯度，并從當前處于空閑狀態(tài)（數(shù)據(jù)流機制）的節(jié)點中選擇剩余能量最大的節(jié)點作為轉(zhuǎn)發(fā)節(jié)點. 可見，節(jié)點梯度越大，數(shù)據(jù)經(jīng)過它傳送的幾率就越小. 當中間節(jié)點的梯度為1時，則直接傳遞給匯聚節(jié)點，完成數(shù)據(jù)的傳輸.

3 仿真試驗與結(jié)果分析

圖2 仿真區(qū)域節(jié)點分布（其中，上邊緣的*節(jié)點為sink節(jié)點，其余節(jié)點為普通節(jié)點）

圖3 LEACH與本文改進算法的存活節(jié)點數(shù)與簇頭數(shù)目的對比圖

圖3結(jié)果表明：在第176輪的時候，LEACH協(xié)議中出現(xiàn)第一個死亡節(jié)點，在1 378輪的時候，LEACH協(xié)議中所有節(jié)點死亡；而改進后的協(xié)議中，出現(xiàn)第一個節(jié)點死亡是在211輪，直到2 286輪節(jié)點才全部死亡. 由于每次實驗節(jié)點散布的隨機性，經(jīng)過多次仿真結(jié)果表明，LEACH算法基本都是在160輪左右出現(xiàn)第一個節(jié)點死亡，在第1 300輪左右現(xiàn)有節(jié)點全部死亡；采用本文改進的協(xié)議時，第一個節(jié)點死亡出現(xiàn)的時間是在220輪左右，全部節(jié)點死亡的時間大約出現(xiàn)在第2300輪. 因此，對于正方形檢測區(qū)域，本文基于梯度與數(shù)據(jù)流機制的分簇路由協(xié)議，與原LEACH協(xié)議比較，網(wǎng)絡(luò)壽命延長了約66%. 當匯聚節(jié)點位于檢測區(qū)域內(nèi)的其他位置時，仿真實驗也表明本協(xié)議與原LEACH協(xié)議相比網(wǎng)絡(luò)壽命能延長壽命60%以上. 另外對不同形狀偵測區(qū)域的仿真結(jié)果表明，WSN的拓撲結(jié)構(gòu)變化對本協(xié)議的有效性影響很小，并且網(wǎng)絡(luò)壽命延長均可達到50 %以上. 可見，改進后的協(xié)議明顯節(jié)約能耗，這對于能量有限的WSN來說，是十分重要的.

4 結(jié)束語

[1]AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. A survey on sensor networks [J]. IEEE Communications Magazine, 2002, 40(8): 102-114.

[2] 孫利民，李建中，陳渝. 無線傳感器網(wǎng)絡(luò)[M]. 北京：清華大學(xué)出版社，2005.

[3] 任豐原，黃海寧，林闖. 無線傳感器網(wǎng)絡(luò)[J]. 軟件學(xué)報，2003, 14(7): 1282?1291.

[4] 付華，趙剛. 無線傳感器網(wǎng)絡(luò)中一種能量均衡的分簇策略[J]. 計算機應(yīng)用研究，2009, 26(4): 1494-1496.

[5] HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks [C]// Proc of the 33rd Annual Hawaii International Conf on SystemYounis Sciences. Maui: IEEE Computer Society, 2000: 3005-3014.

[6] 王素娟. 無線傳感器網(wǎng)絡(luò)分簇算法的研究[D]. 太原：太原理工大學(xué)，2008.

[7] 龔海剛，劉明，余昌遠，等. 無線傳感器網(wǎng)絡(luò)環(huán)境下基于事件驅(qū)動應(yīng)用的節(jié)能TDMA協(xié)議[J]. 電子學(xué)報，2007(10): 1843-1848.

[8] 張偉華，李臘元. 無線傳感器網(wǎng)絡(luò)LEACH 協(xié)議能耗均衡改進[J]. 傳感技術(shù)學(xué)報，2008, 21(11). 1918-1922.

[9] 張文祥，馬銀花. 基于梯度和剩余能量的WSN路由算法研究[J]. 傳感技術(shù)學(xué)報，2009, 22(8): 1182-1185.

[10] 徐建波，李仁發(fā). 無線傳感器網(wǎng)絡(luò)中一種新型的混合型數(shù)據(jù)收集協(xié)議[J]. 計算機研究與發(fā)展，2008, 45(2): 254-260.

[11] 王聲榮. 無線傳感器網(wǎng)絡(luò)LEACH協(xié)議的研究與改進[D]. 濟南：山東大學(xué)信息科學(xué)與工程學(xué)院，2008.

[12] 顧相平，孫彥景，錢建生. 一種改進的無線傳感器網(wǎng)絡(luò)LEACH-ED算法[J]. 傳感技術(shù)學(xué)報，2008, 21(10): 1770-1774.

[13] 沈波，張世永，鐘亦平. 無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J]. 軟件學(xué)報，2006, 17(7): 1588-1600.

[14]HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. An Application Specific Protocol Architecture for Wireless Microsensor Networks [J]. IEEE Trans on Wireless Communications, 2002, 1(4): 660-670.

[15] 劉明，龔海剛，毛鶯池，等. 高效節(jié)能的傳感器網(wǎng)絡(luò)數(shù)據(jù)收集和聚合協(xié)議[J]. 軟件學(xué)報，2005, 16(12): 2106-2116.

[責(zé)任編輯：韋 韜]

WSN Cluster Routing Protocol Based on Grads and Data Flow Mechanism

SHENHai-yan, LIAOXi-chun, LIUYu-kun

(School of Information Engineering, Wuyi University, Jiangmen 529020, China)

In consideration of the limited energy and limited life in wireless sensor network, the election of cluster heads and the communication way within the cluster in the classic LEACH routing protocol are improved based on the grads and data flow mechanism. The Matlab simulation results show that，compared with LEACH，the improved protocol—Cluster Routing Protocol based on grads and data flow mechanism can be more effectively in saving the energy of the nodes，the network life could be prolonged about 50%～65%.

WSN; cluster-based routing; LEACH protocol; grades; data flow mechanism

1006-7302（2013）01-0064-05

TP393

A

2012-11-02

廣東省科技計劃資助項目（2009B010800012）

沈海燕（1987—），女，河南鄭州人，在讀碩士生，研究方向為無線傳感器網(wǎng)絡(luò)路由及定位算法；廖惜春，教授，碩士生導(dǎo)師，研究方向為無線傳感器網(wǎng)絡(luò)及應(yīng)用、物聯(lián)網(wǎng)技術(shù)及應(yīng)用.