基于LEACH的WSN路由算法研究

馬簫雯，余 翔，許 未

(重慶郵電大學(xué)電信增值業(yè)務(wù)研究所，重慶400065)

0 引言

隨著無線通信技術(shù)以及傳感器技術(shù)的飛速發(fā)展，由具有感知能力、計(jì)算能力和通信能力節(jié)點(diǎn)組成的無線傳感器網(wǎng)絡(luò)［1-2］的研究越來越受到研究人員的重視。組成傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)包括數(shù)據(jù)匯聚節(jié)點(diǎn)(sink)和普通的傳感器節(jié)點(diǎn)。由于傳感器節(jié)點(diǎn)能量有限，在進(jìn)行傳感器網(wǎng)絡(luò)路由研究的時候，降低能耗使得無線傳感器網(wǎng)絡(luò)的整體存活時間延長是需要考慮的［3］。

低功耗自適應(yīng)聚類路由協(xié)議［4］(Low Energy Adaptive Clustering Hierarchy，LEACH)是無線傳感器網(wǎng)絡(luò)中一種經(jīng)典的分層次路由協(xié)議，算法通過循環(huán)隨機(jī)地選取簇首節(jié)點(diǎn)來提高網(wǎng)絡(luò)的能量利用率和延長系統(tǒng)的生命周期。相對于無線傳感器網(wǎng)絡(luò)的傳統(tǒng)平面靜態(tài)路由協(xié)議，LEACH可以將網(wǎng)絡(luò)生存時間延長接近15%［5］。但是，LEACH協(xié)議在簇首選擇采用的是各個節(jié)點(diǎn)等概率隨機(jī)成為簇首的方式，沒有考慮到節(jié)點(diǎn)的能量以及簇首與基站的距離等因素，而這些因素恰恰可能導(dǎo)致所選擇的簇首不是最優(yōu)，從而影響到整個網(wǎng)絡(luò)的性能。針對LEACH協(xié)議存在的一些不足，提出一些改進(jìn)建議，并針對其中的部分建議做了仿真驗(yàn)證，所采取的措施有效地提高了節(jié)點(diǎn)的能量利用率同時也延長了整個網(wǎng)絡(luò)的生命周期。

1 LEACH協(xié)議

LEACH路由協(xié)議是Heinzelman(MIT，電子與計(jì)算系)于2000年為WSN設(shè)計(jì)的基于分層的低功耗自適應(yīng)聚類路由算法。LEACH協(xié)議的工作過程被劃分為周期性的“輪”，每輪包括成簇和數(shù)據(jù)傳輸兩個階段。在成簇階段，節(jié)點(diǎn)之間首先按照一定的策略進(jìn)行簇首選舉，等到簇首節(jié)點(diǎn)確定之后，將向全網(wǎng)廣播自身本輪擔(dān)任簇首的消息，其他節(jié)點(diǎn)根據(jù)接收到的廣播信號的強(qiáng)度來決定本輪所要加入的簇，最后，簇首節(jié)點(diǎn)接收加入請求消息并創(chuàng)建TDMA和CDMA編碼機(jī)制。在數(shù)據(jù)傳輸階段，簇首節(jié)點(diǎn)首先接收簇內(nèi)成員節(jié)點(diǎn)采集的監(jiān)測數(shù)據(jù)，然后對接收到的數(shù)據(jù)和自身的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合，最終將融合后的數(shù)據(jù)發(fā)送給基站［6］。

簇首節(jié)點(diǎn)的選取是LEACH算法的核心組成部分，這部分在整個LEACH協(xié)議中占有很重要的位置，其具體的選擇策略描述如下:在成簇階段，每個傳感器節(jié)點(diǎn)產(chǎn)生一個［0，1］之間的隨機(jī)數(shù)，如若該數(shù)小于某一個閥值Pi(t)，則向全網(wǎng)通告自己本輪擔(dān)任簇首的消息;若該節(jié)點(diǎn)之前已經(jīng)擔(dān)任過簇首，則將閥值Pi(t)設(shè)置為0，表明本輪不再擔(dān)任簇首;反之，如果節(jié)點(diǎn)之前沒有擔(dān)任過簇首，則在本輪中以閥值Pi(t)為概率競選簇首;當(dāng)網(wǎng)絡(luò)中只剩下一個節(jié)點(diǎn)沒有擔(dān)任過簇首時，該節(jié)點(diǎn)將把閥值Pi(t)設(shè)為1，表明自己本輪無條件的成為簇首。其中Pi(t)的計(jì)算公式如下:

式中，Ci(t)表示節(jié)點(diǎn)i在最近rmod(N/k)輪是否擔(dān)當(dāng)過簇首節(jié)點(diǎn)，若擔(dān)當(dāng)過簇首，則Ci(t)=0，否則Ci(t)=1;k表示網(wǎng)絡(luò)中簇首節(jié)點(diǎn)的個數(shù)，在一個已知的目標(biāo)區(qū)域內(nèi)，面積為M×M，傳感器節(jié)點(diǎn)總數(shù)為N，節(jié)點(diǎn)均勻分布在檢測區(qū)域中，即 ρ=(1/(M2/k))?？梢酝ㄟ^下面公式推導(dǎo)出網(wǎng)絡(luò)中最優(yōu)的分簇個數(shù):

式(2)、式(3)、式(4)中:εfs和 εmp表示無線能量模型中的參數(shù);dtoCH是簇內(nèi)成員節(jié)點(diǎn)到簇首節(jié)點(diǎn)的距離;Etotal表示總共消耗的能量;dtoBS表示簇首節(jié)點(diǎn)到基站之間的距離;Eelec表示發(fā)射電路和接收電路所消耗的能量;EDA表示節(jié)點(diǎn)進(jìn)行數(shù)據(jù)融合所消耗的能量。

在每輪的穩(wěn)定階段，傳感器節(jié)點(diǎn)將采集的數(shù)據(jù)傳送到簇首節(jié)點(diǎn)。簇首節(jié)點(diǎn)對采集的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合后再將信息傳送給匯聚中心，匯聚中心將數(shù)據(jù)傳送給監(jiān)控中心來進(jìn)行數(shù)據(jù)的處理。穩(wěn)定階段持續(xù)一段時間之后，網(wǎng)絡(luò)重新進(jìn)行簇的建立階段，也就是進(jìn)行下一輪的簇重建，這樣不斷地循環(huán)。

2 LEACH協(xié)議的不足及改進(jìn)方案

2.1 LEACH協(xié)議的不足

LEACH的不足在于，每輪進(jìn)行都要選擇簇頭并劃分簇，并且簇頭需要一直處于醒著的狀態(tài)以接收數(shù)據(jù)，這樣系統(tǒng)開銷較大，離散式區(qū)域算法對節(jié)點(diǎn)位置等要求不高，雖然能夠通過公式推導(dǎo)出可能的分簇?cái)?shù)目，但無法確定最優(yōu)的簇?cái)?shù)目。LEACH采用TDMA的MAC層機(jī)制，而事實(shí)上，在分配給節(jié)點(diǎn)的每個時隙，節(jié)點(diǎn)并不是都有數(shù)據(jù)要發(fā)送給簇頭，這樣的通信機(jī)制不能有效利用帶寬，浪費(fèi)了能量。LEACH還要求節(jié)點(diǎn)之間以及節(jié)點(diǎn)與sink之間都可以直接通信，因此局限了網(wǎng)絡(luò)的可擴(kuò)展性［7，8］。

LEACH以循環(huán)的方式隨機(jī)選取簇首，將整個網(wǎng)絡(luò)的能量負(fù)載平均分配到每個傳感器節(jié)點(diǎn)中，從而降低能源消耗，提高網(wǎng)絡(luò)整體生存時間。由于冗余數(shù)據(jù)被大量消除，因而在能耗方面有較好的性能。但LEACH仍存在如下不足之處。首先，LEACH算法是由網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)自組織的形成簇，簇首的選擇具有極大的隨機(jī)性。在該算法中進(jìn)行簇首選擇時沒有考慮節(jié)點(diǎn)的剩余能量、周圍鄰節(jié)點(diǎn)的數(shù)目以及已經(jīng)擔(dān)任過簇首的次數(shù)等因素，這樣會加重簇首的負(fù)擔(dān)，使能耗不均［9］。當(dāng)一個節(jié)點(diǎn)做簇首的次數(shù)過多時，不但自身的能量消耗加大，而且會使得距離自身較遠(yuǎn)的節(jié)點(diǎn)消耗較多的能量，不利于整個網(wǎng)絡(luò)中節(jié)點(diǎn)能量的均衡和網(wǎng)絡(luò)壽命的延長;其次，不同的簇首數(shù)目也會影響到整個網(wǎng)絡(luò)的生存時間，LEACH算法簇首選擇的隨機(jī)性導(dǎo)致簇首數(shù)目的不確定。

基于以上LEACH算法在簇首選擇過程中的不足，對算法進(jìn)行改進(jìn)，改進(jìn)后的算法跟LEACH算法采用相同的網(wǎng)絡(luò)要求。

2.2 改進(jìn)算法LEACH_NEW描述

2.2.1 LEACH_NEW設(shè)計(jì)思路

根據(jù)上文中所指出的LEACH算法在簇首選擇方面存在的問題，對LEACH算法做如下改進(jìn):

①靜態(tài)分簇，在第一輪簇首選擇之前根據(jù)節(jié)點(diǎn)位置情況進(jìn)行靜態(tài)分簇，并且之后不再重新分簇，只在該簇內(nèi)選擇最佳節(jié)點(diǎn)成為本簇的簇首節(jié)點(diǎn)，簇首節(jié)點(diǎn)在廣播自己成為簇首的信息時也只是向本簇內(nèi)的成員節(jié)點(diǎn)廣播，不需要全網(wǎng)廣播，大大減小了節(jié)點(diǎn)的能量消耗;

②在簇首選擇過程中，將節(jié)點(diǎn)的剩余能量和網(wǎng)絡(luò)的平均能量作為參數(shù)考慮，對閥值的計(jì)算公式進(jìn)行改進(jìn)，使得選出的簇首節(jié)點(diǎn)更加有利于網(wǎng)絡(luò)能耗的均衡以及整個網(wǎng)絡(luò)的生存;

③在數(shù)據(jù)傳輸階段，利用參數(shù)記錄簇頭節(jié)點(diǎn)的鄰簇頭節(jié)點(diǎn)的數(shù)目、簇頭到基站的最佳跳數(shù)和剩余能量，以便在多跳傳輸時簇頭節(jié)點(diǎn)能夠選擇更合適的下一跳節(jié)點(diǎn)并且減小節(jié)點(diǎn)的能耗。

2.2.2 LEACH_NEW的工作過程

LEACH_NEW的工作過程與LEACH一樣，也分為3個階段。即簇首的選擇階段、簇形成階段和數(shù)據(jù)傳輸階段。

首先由于考慮到每一輪重新建立簇過程中所有節(jié)點(diǎn)消耗的能量，本文算法在算法執(zhí)行開始時先采用靜態(tài)分簇方式，在初始過程中節(jié)點(diǎn)就將簇分好，并進(jìn)行相應(yīng)的優(yōu)化。之后簇內(nèi)的節(jié)點(diǎn)不再發(fā)生變化，每一輪簇首的選擇更新都在原簇內(nèi)進(jìn)行，這樣減少了每一輪之前分簇時節(jié)點(diǎn)所消耗的不必要的能量。

①在第一輪簇首選擇階段，若按照式(1)得到的閥值選擇簇首，就會出現(xiàn)簇首選擇不當(dāng)?shù)膯栴}。所以改進(jìn)算法利用新的閥值計(jì)算公式如下:

式中，Ecurrent表示節(jié)點(diǎn)的當(dāng)前能量，Einitial為節(jié)點(diǎn)的初始能量，Nneighbour表示節(jié)點(diǎn)的鄰節(jié)點(diǎn)數(shù)目，CHtime表示節(jié)點(diǎn)在之前的輪中被選為簇首的次數(shù)。

②簇形成階段，經(jīng)過簇首選擇階段已經(jīng)選出了網(wǎng)絡(luò)中擔(dān)任簇首的節(jié)點(diǎn)，隨后每個簇首節(jié)點(diǎn)利用CSMA協(xié)議向自己管轄范圍內(nèi)的所有剩余節(jié)點(diǎn)以相同的傳輸能量發(fā)送自己是簇首的消息，通過該消息廣播告知本簇內(nèi)的成員節(jié)點(diǎn)自己成為簇首;接著簇內(nèi)的剩余節(jié)點(diǎn)將會接受到來自簇首的消息，不過簇內(nèi)節(jié)點(diǎn)可能會在一定間隔內(nèi)收到多個這種消息，應(yīng)為鄰簇間存在干擾，在這種情況下節(jié)點(diǎn)根據(jù)接收消息的強(qiáng)度來選擇簇首，然后再決定加入哪個簇。

每個節(jié)點(diǎn)加入相應(yīng)的簇的同時，同樣采用非持續(xù)CSMA協(xié)議向相應(yīng)的簇首發(fā)送入簇消息，包括自身的ID號。當(dāng)簇首接收所有簇內(nèi)節(jié)點(diǎn)發(fā)來的該消息時，根據(jù)成員節(jié)點(diǎn)的數(shù)目，采用TDMA方式為每個簇成員分配發(fā)送數(shù)據(jù)的時隙。每個節(jié)點(diǎn)只在屬于自己的時間內(nèi)發(fā)送數(shù)據(jù)，在其他時間處于休眠狀態(tài)，這樣做也是為了減少節(jié)點(diǎn)的總能耗。

③數(shù)據(jù)傳輸階段，采用多跳和單跳相結(jié)合的方式。在簇內(nèi)采用單跳方式傳輸，在簇首與基站之間則分情況決定采用哪種傳輸方式。利用參數(shù)記錄簇頭節(jié)點(diǎn)的鄰簇頭節(jié)點(diǎn)的數(shù)目和剩余能量，若距離基站較近時就要避免多跳的路由機(jī)制，以減少路由的開銷。當(dāng)傳輸距離較大時，通過記錄的鄰簇頭數(shù)目、跳數(shù)以及鄰簇首的剩余能量選擇最佳的一個下一跳節(jié)點(diǎn)，采用多跳傳輸機(jī)制，減少網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)能耗，同時由于考慮了跳數(shù)因素，盡量減少簇首到基站的跳數(shù)，以節(jié)約中間節(jié)點(diǎn)的能耗。

3 仿真與分析

3.1 仿真環(huán)境

本文仿真工具采用網(wǎng)絡(luò)仿真工具 NS2［10，11］進(jìn)行仿真。NS2是一種可擴(kuò)展的、容易配置的和可編程的時間驅(qū)動網(wǎng)絡(luò)仿真工具，是由美國加州的LNBL網(wǎng)絡(luò)研究組于1989年開始研究開發(fā)的軟件。NS2源代碼全部公開，提供開放的網(wǎng)絡(luò)接口。本文的仿真環(huán)境:節(jié)點(diǎn)為100個并且隨機(jī)分布在100 m×100 m的監(jiān)測區(qū)域內(nèi)，Sink節(jié)點(diǎn)的位置(50，100)，消息長度為500 byte，信息包的長度為25 byte，每一輪的時間為20 s，即節(jié)點(diǎn)每隔20 s的時間更換一次簇首，時間片的大小為0.023 s，每個節(jié)點(diǎn)的初始能量相同并且為2 J，網(wǎng)絡(luò)帶寬為2 M/s。

3.2 性能分析

通過對整個網(wǎng)絡(luò)總的能耗以及網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)目在LEACH和LEACH-NEW不同算法之下兩個指標(biāo)的對比，由圖1可以看出在相同時間內(nèi)，LEACH-NEW算法的能量消耗少，提高了網(wǎng)絡(luò)的能量利用率，有效地延長了網(wǎng)絡(luò)的生命周期。

圖1 網(wǎng)絡(luò)中的總的耗能情況比較

由圖2可以明顯地看出改進(jìn)算法有效地延長了網(wǎng)絡(luò)的生命周期，LEACH算法在150 s已經(jīng)開始出現(xiàn)節(jié)點(diǎn)死亡，而LEACH-NEW算法在350 s才開始出現(xiàn)第一個節(jié)點(diǎn)的死亡，本文算法減少了簇頭節(jié)點(diǎn)在建立簇時能量的消耗，同時數(shù)據(jù)傳輸階段的單跳和多跳相結(jié)合也是減少了網(wǎng)絡(luò)中節(jié)點(diǎn)的總的能耗。

圖2 網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)目

4 結(jié)束語

無線傳感器網(wǎng)絡(luò)的路由算法一直都是研究的熱點(diǎn)，在對傳統(tǒng)的LEACH算法深入研究的基礎(chǔ)上，指出存在的不足，提出改進(jìn)的算法，并利用NS2仿真工具進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明改進(jìn)算法減少了網(wǎng)絡(luò)的總能耗，有效地延長了整個網(wǎng)絡(luò)的生存時間。

［1］ AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，etal.Wireless Sensor Networks:A Survey［J］.Computer Networks，2002，38(4):393-422.

［2］ 孫建民.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2006.

［3］ KHAMFOROOSH K，KHAMFOROUSH H.A New Rounting Algorithm for Energy Reduction in Wireless Sensor Networks［J］.IEEE，2009:505-509.

［4］ 馬祖長，孫怡寧，梅濤.無線傳感器網(wǎng)絡(luò)綜述［J］.通信學(xué)報(bào)，2004，25(4):114-124.

［5］ 陳志奎，倪晶晶，姜國海，等.WSN中一種基于剩余能量級別的負(fù)載均衡路由協(xié)議［J］.微電子學(xué)與計(jì)算機(jī)，2010，27(12):82-86.

［6］ ZHANG Z，ZHANG X.Research of Improved Clustering Routing Algorithm Based on Load Balance in Wireless Sensor Networks［C］∥IET International Communication Conference on Wireless Mobile and Computing，2009:661-664.

［7］ HEINZELMANW R，CHANDRAKASANA，BALAKRISHNAN H.Energy Efficient Communication Protocol for Wireless Microsensor Networks ［C］∥ Proc.of HICSS＇00.Los Alamitos，CA，USA:IEEE Press，2000:3005-3014.

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

［9］ 王磊，施榮華.無線傳感器網(wǎng)絡(luò)路由算法的仿真研究［J］.計(jì)算機(jī)仿真，2010，28(3):170-174.

［10］ UCB/LBNL/VINT Network Simulator-ns(Version 2)，http://www.isi.edu/nsnam/ns/，2011.

［11］徐雷鳴，龐博，趙耀.NS與網(wǎng)絡(luò)模擬［M］.北京:人民郵電出版社，2008.