無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的研究報(bào)告及改

.z無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的研究與改良摘要:無線傳感器網(wǎng)絡(luò)由許多具有低功率無線收發(fā)裝置的傳感器節(jié)點(diǎn)成,能夠有效地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中的相關(guān)信息,并發(fā)送給遠(yuǎn)處的基站進(jìn)一步處理。由于傳感器節(jié)點(diǎn)能量有限,路由協(xié)議必須盡可能地減少能量消耗,延長(zhǎng)網(wǎng)絡(luò)生命周期。在LEACH算法根底上,提出一種改良的路由算法,改良后的算法采用相對(duì)固定的成簇方式,每隔一輪重新構(gòu)建簇。利用圖論中的prim算法,選擇每輪中Ped最大的簇頭作為根節(jié)點(diǎn),在簇頭節(jié)點(diǎn)之間構(gòu)造樹形路由,簇頭之間以多跳方式將收集到的數(shù)據(jù)發(fā)送到根節(jié)點(diǎn),然后通過根節(jié)點(diǎn)將整個(gè)網(wǎng)絡(luò)收集到的數(shù)據(jù)發(fā)送到基站。仿真結(jié)果說明,與LEACH算法相比,改良算法降低了能耗,有效延長(zhǎng)了網(wǎng)絡(luò)生存周期。關(guān)鍵詞:無線傳感器網(wǎng)絡(luò);LEACH算法;分簇;生命周期;能量消耗Abstract:Wirelesssensornetworksconsistingofalargenumberofsmallsensorswithlow-powertransceivercanbeaneffectivetoolforapperceiving,collectingandputingdatainavarietyofenvironment.Thecollecteddatamustbetransmittedtothebasestationforfurtherprocessing.BasedonLEACHalgorithm,thispaperpresentsanovelclusteringalgorithminwhichclusterarerelativelyfi*edandthenodesre-organizethemselvesintonewclusterseveryotherround.ItutilizesthePrimalgorithminthegraphtheorytoformtreeroutingamongcluster-headnodes,andselectsthecluster-headwiththelargestPedastherootnode.Theclusterheadssenddatatotherootnodeinamulti-hopmannerandtherootnodethensendsthegathereddatabythewholenetworktothebasestation.SimulationresultsshowthatparedwithLEACH,theimprovedalgorithmcanreducetheenergyconsumptionandprolongthelifetimeofthenetwork.KeyWords：wirelesssensornetwork,LEACHalgorithm,clustering,lifetime,energyconsume1、前言無線傳感器網(wǎng)絡(luò)被認(rèn)為是在一定空間*圍內(nèi)密集分布的由大量體積小、廉價(jià)、電池供電的通信器件構(gòu)成的自組織系統(tǒng)．由于無線傳感器網(wǎng)絡(luò)大都需要在無人看管、不更換電池或者幾乎不可能更換電池的條件下長(zhǎng)時(shí)間的工作，如何提高能量的有效利用率并延長(zhǎng)網(wǎng)絡(luò)壽命便成了一個(gè)重要問題．網(wǎng)絡(luò)數(shù)據(jù)傳輸離不開路由協(xié)議,路由協(xié)議對(duì)網(wǎng)絡(luò)的整體性能有重要影響,因此,作為無線傳感器網(wǎng)絡(luò)核心技術(shù)之一的路由協(xié)議一直是研究的熱點(diǎn)。路由算法在路由協(xié)議中起著至關(guān)重要的作用,無線傳感器網(wǎng)絡(luò)中的路由算法從網(wǎng)絡(luò)邏輯構(gòu)造角度可以分為平面路由和層次路由。層次路由算法是無線傳感器網(wǎng)絡(luò)路由算法的研究重點(diǎn),其中,LEACH算法是比擬具有代表性的層次型路由算法。本文在LEACH算法的根底上,介紹一種改良的路由算法,改良算法的成簇方式相對(duì)固定,減少了構(gòu)造簇的能量消耗。簇形成之后,在簇頭間構(gòu)造最小生成樹,簇間通過多跳方式通信,降低了簇頭節(jié)點(diǎn)之間長(zhǎng)距離通信的能耗。2、LEACH算法2.1算法描述：LEACH協(xié)議的操作是按輪進(jìn)展的,每一輪包含簇建立和穩(wěn)定運(yùn)行2個(gè)階段,在簇建立階段,自適應(yīng)分簇構(gòu)造形成,在穩(wěn)定運(yùn)行階段進(jìn)展數(shù)據(jù)傳輸。在簇建立階段,選取一定數(shù)目的節(jié)點(diǎn)充當(dāng)簇頭節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)隨機(jī)分配一個(gè)在0到1之間的數(shù)字,成為其標(biāo)志值。如果節(jié)點(diǎn)的標(biāo)志值小于門限值T(n)的話,該節(jié)點(diǎn)就充當(dāng)本輪的簇頭節(jié)點(diǎn)。門限T(n)定義如下：T(n)=p/(1-p*(rmod(1/p)))n∈GT(n)=0其他式中p為網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)所占總節(jié)點(diǎn)數(shù)目的百分比;r為當(dāng)前的輪數(shù);G為一個(gè)集合,集合中的節(jié)點(diǎn)是前1/p輪中沒有充當(dāng)過簇頭節(jié)點(diǎn)的節(jié)點(diǎn)。使用這個(gè)門限,每個(gè)節(jié)點(diǎn)會(huì)在1/p輪操作內(nèi)充當(dāng)一次簇頭節(jié)點(diǎn)。等過了1/p輪以后,所有的節(jié)點(diǎn)都充當(dāng)過簇頭節(jié)點(diǎn),從而又可以重新充當(dāng)簇頭節(jié)點(diǎn)。節(jié)點(diǎn)被選為簇頭后,就向外發(fā)送播送信息;其他節(jié)點(diǎn)就根據(jù)收到消息的信號(hào)強(qiáng)弱,選取信號(hào)最強(qiáng)的發(fā)送源節(jié)點(diǎn)作為自己的簇頭節(jié)點(diǎn),參加那個(gè)簇,并向簇頭發(fā)送參加的請(qǐng)求。簇頭收到請(qǐng)求后為成員節(jié)點(diǎn)設(shè)定一個(gè)TDMA時(shí)隙表。此后的簇穩(wěn)定階段,節(jié)點(diǎn)在屬于自己的時(shí)隙里將采集的數(shù)據(jù)發(fā)送給簇頭節(jié)點(diǎn),簇頭節(jié)點(diǎn)將接收到的成員節(jié)點(diǎn)的數(shù)據(jù)進(jìn)展融合,然后,直接發(fā)送給基站。2.2LEACH算法的缺乏及其改良算法在LEACH算法中,每一輪循環(huán)都要重新構(gòu)造簇,而構(gòu)造簇的能量開銷比擬大。其次,遠(yuǎn)離會(huì)聚節(jié)點(diǎn)的簇頭節(jié)點(diǎn)可能會(huì)由于長(zhǎng)距離發(fā)送數(shù)據(jù)而過早耗盡自身能量,造成網(wǎng)絡(luò)分割。另外,LEACH算法沒有考慮簇頭節(jié)點(diǎn)當(dāng)前的能量狀況,如果能量很低的節(jié)點(diǎn)中選為簇頭節(jié)點(diǎn),則將會(huì)加速該節(jié)點(diǎn)的死亡,影響整個(gè)網(wǎng)絡(luò)的生命周期。3、改良的算3.1改良算法的根本思想本文的改良算法也按輪的機(jī)制運(yùn)行,但是與LEACH不同的是,改良后的算法不必每一輪都重新構(gòu)建簇。改良算法運(yùn)行到第N輪,當(dāng)N為奇數(shù)時(shí),新算法采用與LEACH-EA一樣的機(jī)制選擇簇頭,這樣產(chǎn)生的簇頭在新算法中稱為活動(dòng)簇頭,活動(dòng)簇頭選定后,該活動(dòng)簇頭發(fā)布自己是簇頭的消息,非簇頭節(jié)點(diǎn)根據(jù)接收信號(hào)的強(qiáng)弱來選擇參加哪個(gè)簇,并通知相應(yīng)的活動(dòng)簇頭,完成簇的建立。簇建立之后,簇內(nèi)節(jié)點(diǎn)通過單跳通信方式直接向其簇頭節(jié)點(diǎn)傳送數(shù)據(jù)。當(dāng)N為偶數(shù)時(shí),原來的簇固定不變。如果此時(shí)活動(dòng)簇頭節(jié)點(diǎn)能量低于*一個(gè)門限值時(shí),則在原簇內(nèi)重新選擇簇頭節(jié)點(diǎn),以簇內(nèi)剩余能量最多的節(jié)點(diǎn)為新的簇頭節(jié)點(diǎn),這樣產(chǎn)生的簇頭在新算法中稱為固定簇頭。為降低簇頭(包括活動(dòng)簇頭和固定簇頭)節(jié)點(diǎn)的通信代價(jià),在簇頭間構(gòu)造樹形路由,簇頭間以多跳方式通信。3.2改良算法的描述〔1〕簇的建立和簇內(nèi)通信改良算法第N輪的開場(chǎng),首先判斷N是奇數(shù)還是偶數(shù)。當(dāng)N是奇數(shù)時(shí),就需要重新構(gòu)建簇,此時(shí),采用與LEACH-EA一樣的簇頭選擇機(jī)制?；顒?dòng)簇頭選擇過程如下:每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)0~1之間的隨機(jī)數(shù),如果這個(gè)數(shù)小于閾值T(n),則該節(jié)向周圍節(jié)點(diǎn)播送它是簇頭的消息,參照LEACH-EA的閾值計(jì)算公式T(n)可表示為:T(n)=〔p÷〔1-p*(rmod(1/p))〕〕×〔En-current÷Eaver〕,n∈GT(n)=0,其它其中,p是簇頭占所有節(jié)點(diǎn)的百分比,即節(jié)點(diǎn)中選簇頭的概率;r代表目前進(jìn)展的輪數(shù);G表示最近1/p輪中還未中選過簇頭的節(jié)點(diǎn)集合;En-current表示節(jié)點(diǎn)的當(dāng)前能量;Eaver表示每一輪完畢后節(jié)點(diǎn)的平均能量。節(jié)點(diǎn)中選為活動(dòng)簇頭后,該活動(dòng)簇頭播送自己是簇頭的消息,非簇頭節(jié)點(diǎn)根據(jù)接收信號(hào)的強(qiáng)弱。選擇參加哪個(gè)簇,并通知相應(yīng)的活動(dòng)簇頭,完成簇的建立?；顒?dòng)簇頭接收到所有的參加信息后,就產(chǎn)生一個(gè)TDMA定時(shí)信息表,給簇中每個(gè)非簇頭成員節(jié)點(diǎn)分配傳送數(shù)據(jù)的時(shí)間片,成員節(jié)點(diǎn)只能在其特定的時(shí)間片內(nèi)與簇頭節(jié)點(diǎn)進(jìn)展通信。算法執(zhí)行首輪時(shí),簇的建立與此種情況一樣。當(dāng)N是偶數(shù)時(shí),則原來的簇固定不變。如果活動(dòng)簇頭節(jié)點(diǎn)能量低于*一個(gè)規(guī)定的門限值,則在原簇內(nèi)重新選擇簇頭節(jié)點(diǎn),以簇內(nèi)剩余能量最多的節(jié)點(diǎn)為簇頭節(jié)點(diǎn),這樣產(chǎn)生的簇頭稱為固定簇頭。固定簇頭與簇內(nèi)成員的通信方式和活動(dòng)簇頭一樣。當(dāng)節(jié)點(diǎn)持續(xù)采集監(jiān)測(cè)數(shù)據(jù)時(shí),在其相應(yīng)時(shí)間片,使用最小能量傳給簇頭節(jié)點(diǎn)。節(jié)點(diǎn)不發(fā)送數(shù)據(jù)時(shí),關(guān)閉節(jié)點(diǎn)以節(jié)約能量。簇頭節(jié)點(diǎn)必須保持其接收器一直翻開,以接收簇內(nèi)不同節(jié)點(diǎn)的數(shù)據(jù),然后進(jìn)展數(shù)據(jù)融合。3.2.2簇頭間樹形路由的構(gòu)建與簇間通信假設(shè)要在n個(gè)城市之間建立通信聯(lián)絡(luò)網(wǎng),則連通n個(gè)城市只需要n-1條線路。如果用連通網(wǎng)的頂點(diǎn)來表示城市,邊表示兩城市之間的線路,賦予邊的權(quán)值代表相應(yīng)的代價(jià),需要考慮如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通信網(wǎng)。對(duì)于n個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹,每一棵生成樹都可以是一個(gè)通信網(wǎng),要選擇一棵生成樹,使總的代價(jià)最少,這就是構(gòu)造連通網(wǎng)的最小代價(jià)生成樹(MinimumCostSpanningTree)問題[7](簡(jiǎn)稱為最小生成樹問題)?？紤]將此問題中的城市與無線傳感器網(wǎng)絡(luò)中的簇頭節(jié)點(diǎn)相對(duì)應(yīng),可以在簇頭節(jié)點(diǎn)之間構(gòu)造最小生成樹,降低簇頭節(jié)點(diǎn)間的通信代價(jià)。prim算法構(gòu)造最小生成樹的過程:假設(shè)N=(V,{E})為連通網(wǎng),V表示網(wǎng)中頂點(diǎn)的集合,E表示邊的集合,U是V的一非空子集,TE為最小生成樹中邊的集合。首先,從集合V中取一個(gè)頂點(diǎn)V0參加集合U中,這時(shí)U={V0},集合TE={},接著重復(fù)執(zhí)行以下操作:從V0出發(fā),在集合V中尋找與U中頂點(diǎn)相鄰頂點(diǎn)中權(quán)值最小的邊的另一頂點(diǎn)V1,然后將V1并入U(xiǎn)中,并將該邊參加集合TE中,直到U=V為止。這時(shí)TE中有n-1條邊,T=(U,TE)為N的最小生成樹。本文參照文獻(xiàn)[5],利用prim算法構(gòu)造最小生成樹的原理在簇頭間構(gòu)造樹形路由,在文獻(xiàn)[5]的根底上進(jìn)展了改良,過程如下:1)選出的簇頭節(jié)點(diǎn)將自己的剩余能量和到基站的距離參加到播送數(shù)據(jù)包中進(jìn)展播送,根據(jù)其剩余能量和到基站的距離關(guān)系參數(shù)Ped,選取Ped最大的簇頭節(jié)點(diǎn)作為樹根節(jié)點(diǎn)。Ped的定義公式:Ped(i)=Ey2(i)De(i)(3)其中,i是傳感器節(jié)點(diǎn)編號(hào),Ey(i)是節(jié)點(diǎn)i的剩余能量,De(i)是節(jié)點(diǎn)i到基站的距離。2)利用prim算法構(gòu)造最小生成樹原理,樹根節(jié)點(diǎn)選擇下一跳中最小有效簇頭節(jié)點(diǎn)作為其子節(jié)點(diǎn),該子節(jié)點(diǎn)以樹根節(jié)點(diǎn)為父節(jié)點(diǎn),同時(shí)向下一跳簇頭節(jié)點(diǎn)繼續(xù)搜索。假設(shè)該子節(jié)點(diǎn)搜索成功,則繼續(xù)執(zhí)行路由算法,假設(shè)沒有搜索到最小有效簇頭節(jié)點(diǎn),則返回該根節(jié)點(diǎn)繼續(xù)搜索。3)重復(fù)2),直到所有節(jié)點(diǎn)參加到樹中,構(gòu)成樹形網(wǎng)絡(luò)路由。簇頭節(jié)點(diǎn)通過樹網(wǎng)絡(luò)路由,以多跳方式通信,最后作為樹根節(jié)點(diǎn)的簇頭將數(shù)據(jù)傳給基站。簇頭間的樹形路由如圖1所示。4、算法的仿真分析采用Matlab仿真工具,對(duì)LEACH算法、LEACH-EA算法和改良的算法進(jìn)展仿真比擬。仿真場(chǎng)景假設(shè)有100個(gè)傳感器節(jié)點(diǎn)組成,節(jié)點(diǎn)隨機(jī)分布在一個(gè)介于(*=0,y=0)與(*=100,y=100)的區(qū)域內(nèi),每個(gè)節(jié)點(diǎn)都擁有一樣的初始能量E0=0.5J,仿真模型參照文獻(xiàn)[6]。如圖2所示,前1000輪中,LEACH和LEACH-EA算法的節(jié)點(diǎn)存活數(shù)比擬接近,改良算法相對(duì)來說比前兩種算法更優(yōu)越。網(wǎng)絡(luò)生命周期是衡量網(wǎng)絡(luò)質(zhì)量的一個(gè)重要標(biāo)志,圖3顯示了當(dāng)節(jié)點(diǎn)死亡率為1%,50%,100%時(shí)所經(jīng)過的輪數(shù)。從圖中可以看出新算法的通信輪數(shù)高于LEACH和LEACH-EA算法,說明改良之后得到的新算法降低了能耗,延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間。5、參考文獻(xiàn)[1]TaoYang,ZhengYaling.Thebinationoftheoptimalnumberofcluster-headsandenergyadaptivecluster-headselectionAlgorithminwirelesssensornetworks[C].Wi2006InternationalConference.Wuhan,China,2006:1-4.[2]HouGuofeng,TangKW.EvaluationofLEACHprotocolsubjecttodifferenttrafficmodels[C]//COIN-NGNCON2006.HyattRegencyJeju,[3]Heinzelman,W.R.,A.Chandrakasan,andH.Balakrishnan.Energy-Ef-ficientmunicationProtocolforWirelessMicrosensorNetworks,Proc.ofthe33rdAnnuaHawaiiInternationalConferenceonSystemSciences,January4~7,2000.Maui,Hawaii.p.3005~3014[4]HandyMJ,HaaseM,TimmermannD.Lowenergya-daptiveclusteringhierarchywithdeterministicclus-ter-headselection[A].Procofthe4thIEEEConfonMobileandWirelessmunicationsNetworks[C].Stockholm:IEEEmunicationsSociety,2002.368-372[5]王振興,熊偉麗,*保國(guó).基于LEACH的簇樹網(wǎng)絡(luò)路由算法研究[J].計(jì)算機(jī)測(cè)量與