基于LEACH協(xié)議的鏈?zhǔn)酱仡^節(jié)能路由算法

米守防

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

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

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

分簇技術(shù)是一種節(jié)省能耗十分有效的網(wǎng)絡(luò)拓?fù)淇刂萍夹g(shù)，所謂“分簇技術(shù)”就是將節(jié)點(diǎn)劃分成許多組，稱為簇，每個(gè)簇都有一個(gè)簇頭和許多簇成員節(jié)點(diǎn)。網(wǎng)絡(luò)定期的進(jìn)行分簇，由簇頭節(jié)點(diǎn)管理

整個(gè)簇，對(duì)簇成員節(jié)點(diǎn)感知的數(shù)據(jù)進(jìn)行融合后再傳輸給匯聚節(jié)點(diǎn)［6］。分簇算法具有拓?fù)涔芾矸奖?、能量利用高效、?shù)據(jù)融合簡(jiǎn)單等優(yōu)點(diǎn)，是當(dāng)前重點(diǎn)研究的路由技術(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é)議是第一個(gè)基于多簇結(jié)構(gòu)的路由協(xié)議，其基本思想是將網(wǎng)絡(luò)劃分為不同的簇，通過等概率周期性的選擇簇頭，將整個(gè)網(wǎng)絡(luò)的能量負(fù)載相對(duì)均衡的分配到每個(gè)傳感器節(jié)點(diǎn)，從而達(dá)到減少網(wǎng)絡(luò)能量消耗、延長(zhǎng)網(wǎng)絡(luò)生命周期的目的。其中，簇頭的選擇是依據(jù)網(wǎng)絡(luò)中所需要的簇頭節(jié)點(diǎn)總數(shù)和迄今為止每個(gè)階段已成為簇頭的次數(shù)來決定的。LEACH定義了“輪”(Round)的概念，其運(yùn)行分為兩個(gè)階段:簇建立階段和穩(wěn)定數(shù)據(jù)通信階段。

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

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

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

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

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

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

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

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

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

簇頭和匯聚節(jié)點(diǎn)通信采用單跳通信，會(huì)導(dǎo)致距離匯聚節(jié)點(diǎn)較遠(yuǎn)的簇頭較早死亡，引起網(wǎng)絡(luò)拓?fù)渥兓绊懢W(wǎng)絡(luò)壽命。

2 基于LEACH協(xié)議的鏈?zhǔn)酱仡^節(jié)能路由算法

2.1 鏈?zhǔn)酱仡^節(jié)能路由協(xié)議

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

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

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

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

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

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

2.2 算法描述

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

圖1 改進(jìn)后算法流程圖

3 仿真實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

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

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

4 結(jié)語

本文提出了一種基于LEACH協(xié)議的鏈?zhǔn)酱仡^節(jié)能路由算法，核心思想就是在簇頭和匯聚節(jié)點(diǎn)數(shù)據(jù)傳輸階段進(jìn)行了改進(jìn)。根據(jù)簇頭的剩余能量和簇頭與匯聚節(jié)點(diǎn)間距離等因素，將簇頭節(jié)點(diǎn)連接成鏈，根據(jù)規(guī)則計(jì)算出的值最小的節(jié)點(diǎn)作為鏈?zhǔn)?，值最大作為鏈?領(lǐng)導(dǎo)節(jié)點(diǎn))直接與匯聚節(jié)點(diǎn)通信，通過數(shù)據(jù)融合，既能減少了需要傳輸?shù)臄?shù)據(jù)量，減少能量消耗，又能保證節(jié)點(diǎn)能量不會(huì)很快耗盡，而影響數(shù)據(jù)的采集。實(shí)驗(yàn)證明新算法節(jié)約了網(wǎng)絡(luò)的能量消耗，提高了數(shù)據(jù)傳輸?shù)目煽啃?，延長(zhǎng)了整個(gè)網(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é)報(bào):自然科學(xué)版，2010，33(9):1416-1419.

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

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

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

［6］周新蓮.基于分簇技術(shù)的移動(dòng)無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集協(xié)議研究［D］.長(zhǎng)沙:中南大學(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é)報(bào)，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.