基于LEACH協(xié)議的鏈式簇頭節(jié)能路由算法

米守防

(大連民族學(xué)院計算機科學(xué)與工程學(xué)院，遼寧大連116605)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)是由部署在監(jiān)測區(qū)域內(nèi)大量的智能微型傳感器節(jié)點組成，通過無線通信方式形成的一個多跳的、自組織的網(wǎng)絡(luò)系統(tǒng)［1-3］。其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中被感知對象的信息，并發(fā)送給觀察者。作為一種全新的信息獲取和處理技術(shù)，無線傳感器網(wǎng)絡(luò)已在軍事、環(huán)境科學(xué)、醫(yī)療護理、智能家居和其他領(lǐng)域得到廣泛應(yīng)用。

傳感器節(jié)點是微型電子設(shè)備，體積微小，通常攜帶能量十分有限的電池。由于無線傳感器網(wǎng)絡(luò)部署區(qū)域環(huán)境復(fù)雜，有些區(qū)域甚至人員不能到達［3］，而且傳感器節(jié)點個數(shù)多，所以傳感器節(jié)點通過更換電池的方式來補給能量變得非常困難。如何合理利用傳感器節(jié)點有限的能量延長網(wǎng)絡(luò)生命周期是傳感器網(wǎng)絡(luò)協(xié)議設(shè)計所面臨的首要問題［4］。將傳感器節(jié)點組織成簇的形式有效的減少能量消耗，許多能量高效的路由協(xié)議都是在基于分簇(clustering)的路由基礎(chǔ)上進行設(shè)計的［5］。

分簇技術(shù)是一種節(jié)省能耗十分有效的網(wǎng)絡(luò)拓撲控制技術(shù)，所謂“分簇技術(shù)”就是將節(jié)點劃分成許多組，稱為簇，每個簇都有一個簇頭和許多簇成員節(jié)點。網(wǎng)絡(luò)定期的進行分簇，由簇頭節(jié)點管理

整個簇，對簇成員節(jié)點感知的數(shù)據(jù)進行融合后再傳輸給匯聚節(jié)點［6］。分簇算法具有拓撲管理方便、能量利用高效、數(shù)據(jù)融合簡單等優(yōu)點，是當(dāng)前重點研究的路由技術(shù)。其中比較有代表性的分簇路由協(xié)議是Heinzelman等人在2000年聯(lián)合提出低功耗自適應(yīng)分簇層次路由協(xié)議(low energy adaptive clustering hierarchy，LEACH)［7-8］。

1 LEACH協(xié)議分析

1.1 LEACH協(xié)議概述

LEACH協(xié)議是第一個基于多簇結(jié)構(gòu)的路由協(xié)議，其基本思想是將網(wǎng)絡(luò)劃分為不同的簇，通過等概率周期性的選擇簇頭，將整個網(wǎng)絡(luò)的能量負載相對均衡的分配到每個傳感器節(jié)點，從而達到減少網(wǎng)絡(luò)能量消耗、延長網(wǎng)絡(luò)生命周期的目的。其中，簇頭的選擇是依據(jù)網(wǎng)絡(luò)中所需要的簇頭節(jié)點總數(shù)和迄今為止每個階段已成為簇頭的次數(shù)來決定的。LEACH定義了“輪”(Round)的概念，其運行分為兩個階段:簇建立階段和穩(wěn)定數(shù)據(jù)通信階段。

在簇建立階段，LEACH協(xié)議隨機選擇一個傳感器節(jié)點作為簇頭，在每輪簇的組織階段，每個節(jié)點都生成一個介于0和1之間的隨機數(shù)n，如果該隨機數(shù)小于閥值T(n)，則該節(jié)點成為簇頭。閥值T(n)按公式(1)計算。

其中，p是簇頭在所有節(jié)點中所占的百分比，r為選舉輪數(shù)，r mod(1/p)代表這一輪循環(huán)中當(dāng)選過簇頭的節(jié)點個數(shù)，G是這一輪循環(huán)中未當(dāng)選過簇頭的節(jié)點集合。在第0輪中，即r=0時，每一個節(jié)點都有概率為p的可能性成為簇頭。

在第0輪中成為簇頭的節(jié)點，在接下來的1/p輪中不會再成為簇頭，在經(jīng)過1/p-1輪后，T值變?yōu)?，這時還沒有成為簇頭的節(jié)點就被選擇為簇類節(jié)點;在經(jīng)過1/p輪后，所有節(jié)點再次開始平等地競爭是否當(dāng)選簇頭［9］。

節(jié)點當(dāng)選簇頭后，發(fā)布通知消息告知其他節(jié)點自己是簇頭。非簇頭節(jié)點根據(jù)自己與簇頭之間的距離來選擇加入哪個簇，并告知該簇頭。當(dāng)簇頭接收到所有的加入信息后，就產(chǎn)生一個TDMA定時消息，并且通知該簇內(nèi)所有節(jié)點。為了避免附近簇的信號干擾，簇頭可以決定本簇中所有節(jié)點的CDMA編碼。這個用于當(dāng)前階段的CDMA編碼連同TDMA定時一起發(fā)送。當(dāng)簇內(nèi)節(jié)點收到這個消息后，他們就會在各自的時間槽內(nèi)發(fā)送數(shù)據(jù)。經(jīng)過一段時間的數(shù)據(jù)傳輸，簇頭節(jié)點收齊簇內(nèi)節(jié)點發(fā)送的數(shù)據(jù)后，運行數(shù)據(jù)融合算法來處理數(shù)據(jù)，并將結(jié)果直接發(fā)送給匯聚節(jié)點。

1.2 LEACH協(xié)議存在的問題

LEACH分簇協(xié)議按照一定概率隨機選擇簇頭，簇頭將簇內(nèi)數(shù)據(jù)在本地數(shù)據(jù)融合后再轉(zhuǎn)發(fā)給匯聚節(jié)點，減少了實際需要傳輸?shù)臄?shù)據(jù)量，降低了大部分節(jié)點的能量消耗;通過簇頭更換機制去均衡負載耗能，從而延長網(wǎng)絡(luò)的生存周期。但該協(xié)議并未從全局的角度考慮節(jié)能，具體有以下幾點。

(1)隨機選舉出來的簇頭概率相同，意味著少能量或者位置偏遠的節(jié)點都有可能成為簇頭。由于簇頭節(jié)點要與匯聚節(jié)點直接通信，簇頭會消耗較多的能量。

(2)隨機選舉的簇頭，簇頭需負擔(dān)的簇內(nèi)節(jié)點數(shù)不同，個別簇內(nèi)節(jié)點相對較多的簇頭負擔(dān)過重，導(dǎo)致這個網(wǎng)絡(luò)的負載不均衡。

(3)在選擇簇頭時，并未考慮簇頭的剩余能量，可能某個節(jié)點成為簇頭后，剩余能量不夠本輪的通信使用，必然會導(dǎo)致該簇頭的能量迅速耗盡而至死亡，整個被監(jiān)測區(qū)域出現(xiàn)盲區(qū)。

簇頭和匯聚節(jié)點通信采用單跳通信，會導(dǎo)致距離匯聚節(jié)點較遠的簇頭較早死亡，引起網(wǎng)絡(luò)拓撲變化影響網(wǎng)絡(luò)壽命。

2 基于LEACH協(xié)議的鏈式簇頭節(jié)能路由算法

2.1 鏈式簇頭節(jié)能路由協(xié)議

針對LEACH協(xié)議的上述缺點，本文在簇頭和匯聚節(jié)點數(shù)據(jù)傳輸階段進行了改進。以平衡總的能量消耗、延長網(wǎng)絡(luò)的存活時間為主要設(shè)計目標，提出了一種改進的LEACH路由協(xié)議。在數(shù)據(jù)傳輸階段，LEACH協(xié)議采用的是單個簇頭直接傳輸給匯聚節(jié)點的方式，這種方式簡單，但是對簇頭來講，能量消耗相對很大，尤其不適用于匯聚節(jié)點相對較遠和大型網(wǎng)絡(luò)的情況。對于簇頭和匯聚節(jié)點數(shù)據(jù)傳輸方式的改進，首先考慮的是實現(xiàn)簇頭之間的多跳數(shù)據(jù)通信，通過選擇其他簇頭中繼，使數(shù)據(jù)傳送的距離最小，以減少遠離匯聚點的簇頭能量消耗，進而延長網(wǎng)絡(luò)的生存時間。因此，改進后的協(xié)議采用了簇頭之間進行多跳傳輸?shù)姆绞剑唧w如下:考慮每輪選舉出的簇頭剩余能量和簇頭與匯聚節(jié)點間距離等因素，將簇頭節(jié)點按照公式(2)所計算出值連接成鏈，在鏈中選取TCH(i)值最小的節(jié)點作為鏈首，值最大作為鏈尾(領(lǐng)導(dǎo)節(jié)點)直接與匯聚節(jié)點通信，通過數(shù)據(jù)融合，既能減少了需要傳輸?shù)臄?shù)據(jù)量，減少能量消耗，又能保證節(jié)點能量不會很快耗盡，而影響數(shù)據(jù)的采集。

其中，TCH(i)為簇頭i權(quán)值，Er(i)為簇頭i的剩余能量，Sd(i)為簇頭i與匯聚節(jié)點之間的距離，為常量。

本文采用文獻［10］中簡單的能量消耗模型，在傳輸k比特信息經(jīng)過距離d的過程中，發(fā)送端能量消耗為

其中，Eelec表示發(fā)射電路能量消耗;εfs和 εmp為功率放大器所消耗的能量。節(jié)點接收k比特的數(shù)據(jù)所消耗的能量為

將l個長度為k比特的數(shù)據(jù)包融合所消耗的能量為

其中，EDA為處理1比特數(shù)據(jù)需要的能量損耗。

2.2 算法描述

算法也是按輪進行運作，每輪由簇的建立和穩(wěn)定數(shù)據(jù)傳輸兩個階段組成。簇建立階段采用LEACH構(gòu)建階段的簇頭選擇和成簇方式選擇簇頭并成簇，簇頭選舉出來以后，向全網(wǎng)發(fā)送廣播消息，節(jié)點比較收到廣播的強度選擇要加入的簇，并告知簇頭。簇頭為簇內(nèi)節(jié)點創(chuàng)建TDMA時隙表，簇內(nèi)節(jié)點按照時隙表向簇頭發(fā)送數(shù)據(jù)。簇頭接收數(shù)據(jù)并融合成一個數(shù)據(jù)包，同時受令牌(Token)控制，然后根據(jù)各簇頭的自身情況確定Sd、d0和Er的值，依據(jù)公式(2)計算出TCH，并按照TCH的大小進行成鏈。使數(shù)據(jù)包順著這個鏈向領(lǐng)導(dǎo)節(jié)點傳送，領(lǐng)導(dǎo)節(jié)點將接收的數(shù)據(jù)融合成一個數(shù)據(jù)包發(fā)送給匯聚節(jié)點。改進后的算法流程如圖1。

圖1 改進后算法流程圖

3 仿真實驗與分析

本文采用的網(wǎng)絡(luò)模型如下:傳感器節(jié)點隨機分布在一個正方形區(qū)域內(nèi);傳感器節(jié)點同構(gòu)，具有全網(wǎng)唯一的id號，能量受限，節(jié)點靜止;匯聚節(jié)點固定;無線發(fā)射功率可調(diào)。使用Matlab7對LEACH協(xié)議和本文算法進行仿真，模擬參數(shù)見表1。

表1 模擬參數(shù)列表

為了更好的對比改進后協(xié)議的性能，在實驗中分別的LEACH協(xié)議和改進后的協(xié)議進行了仿真。如圖2給出了兩種算法死亡節(jié)點數(shù)隨時間變化對比，從圖中可以看出本文算法相比原來的LEACH算法，在首個節(jié)點到最后一個節(jié)點死亡的時間方面要延遲很多，整個網(wǎng)絡(luò)的生存周期也延長了很多，本算法更有效使用能量，提高了網(wǎng)絡(luò)壽命。

圖2 2種協(xié)議死亡節(jié)點個數(shù)隨時間變化比較

圖3給出了兩種算法數(shù)據(jù)傳輸隨時間變化對比，從圖中可以本算法隨著數(shù)據(jù)頻率的降低，傳輸數(shù)據(jù)量(可靠性)整體上有所提升。從實驗過程分析可看，本算法保障了簇頭之間的連通性，這是提高傳輸可靠性的最重要因素。

圖3 2種協(xié)議數(shù)據(jù)傳輸隨時間變化比較

圖4給出了兩種算法隨時間變化網(wǎng)絡(luò)能量消耗比較，由圖中可以看出本算法的能耗明顯低于LEACH算法，這是因為在LEACH算法中所有簇頭都向匯聚節(jié)點發(fā)送消息，這將消耗大量的能量，而本文算法將簇頭連接成鏈，然后簇頭采用令牌傳輸機制將數(shù)據(jù)傳輸給領(lǐng)導(dǎo)節(jié)點，領(lǐng)導(dǎo)節(jié)點融合數(shù)據(jù)并發(fā)送給匯聚節(jié)點。這樣減少了各個簇頭同時向匯聚節(jié)點發(fā)送數(shù)據(jù)而產(chǎn)生的能量，有效的延長了網(wǎng)絡(luò)的生命周期。

圖4 2種協(xié)議網(wǎng)絡(luò)能量消耗隨時間變化比較

從圖3和圖4可以觀察到，兩種算法在數(shù)據(jù)傳輸輪次相同既有效數(shù)據(jù)傳輸量相同的情況下，網(wǎng)絡(luò)的能耗越少意味著算法更節(jié)約能量，網(wǎng)絡(luò)的生存時間越長。而隨著輪次的增加，網(wǎng)絡(luò)消耗相同的情況，網(wǎng)絡(luò)有效數(shù)據(jù)傳輸量越多意味著網(wǎng)絡(luò)的負載能力強，生命周期也長。采用本算法比LEACH算法更加節(jié)約能量。

4 結(jié)語

本文提出了一種基于LEACH協(xié)議的鏈式簇頭節(jié)能路由算法，核心思想就是在簇頭和匯聚節(jié)點數(shù)據(jù)傳輸階段進行了改進。根據(jù)簇頭的剩余能量和簇頭與匯聚節(jié)點間距離等因素，將簇頭節(jié)點連接成鏈，根據(jù)規(guī)則計算出的值最小的節(jié)點作為鏈首，值最大作為鏈尾(領(lǐng)導(dǎo)節(jié)點)直接與匯聚節(jié)點通信，通過數(shù)據(jù)融合，既能減少了需要傳輸?shù)臄?shù)據(jù)量，減少能量消耗，又能保證節(jié)點能量不會很快耗盡，而影響數(shù)據(jù)的采集。實驗證明新算法節(jié)約了網(wǎng)絡(luò)的能量消耗，提高了數(shù)據(jù)傳輸?shù)目煽啃裕娱L了整個網(wǎng)絡(luò)生命周期。

［1］AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，et al.Wireless sensor networks:a survey［J］.Computer Networks，2002，38(4):393-422.

［2］王文光，劉士興，謝武軍.無線傳感器網(wǎng)絡(luò)概述［J］.合肥工業(yè)大學(xué)學(xué)報:自然科學(xué)版，2010，33(9):1416-1419.

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

［4］齊迎迎，禹繼國，王楠楠.無線傳感器網(wǎng)絡(luò)的節(jié)能分布式分簇算法［J］.計算機工程，2011，37(3):83-86.

［5］劉瓊，成運.一種無線傳感器網(wǎng)絡(luò)分簇路由算法研究［J］.現(xiàn)代電子技術(shù)，2010，33(10):162-164.

［6］周新蓮.基于分簇技術(shù)的移動無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議研究［D］.長沙:中南大學(xué)，2010.

［7］HEINZELMAN W E.Energy-efficient communication protocol for wireless microsensor networks［C］//Proceedings of the 33rd Annual Hawaii International Conference on，2000:3005-3014.

［8］HEINZELMAN W R，CHANDRAKASAN A.And Hari balakrishnan Energy-Efficient communication protocol for wireless microsensor networks［C］//Proceedings of the 33rd Annual Hawaii International Conference on Jan 4-7 2000，2000:10.

［9］張品，徐智福，孫巖.一種新的基于簇頭優(yōu)化的WSN路由協(xié)議［J］.傳感技術(shù)學(xué)報，2009，22(7):1013-1017.

［10］HEINZELMAN W E.An application-specific protocol architecture for wireless microsensor networks［J］.Ieee Transactions on Wireless Communications，2002，1(4):660-670.