河南師范大學(xué)本科畢業(yè)論文（設(shè)計(jì)）無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的研究與改進(jìn)摘要:無(wú)線傳感器網(wǎng)絡(luò)由許多具有低功率無(wú)線收發(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算法基礎(chǔ)上,提出一種改進(jìn)的路由算法,改進(jìn)后的算法采用相對(duì)固定的成簇方式,每隔一輪重新構(gòu)建簇。利用圖論中的prim算法,選擇每輪中Ped最大的簇頭作為根節(jié)點(diǎn),在簇頭節(jié)點(diǎn)之間構(gòu)造樹(shù)形路由,簇頭之間以多跳方式將收集到的數(shù)據(jù)發(fā)送到根節(jié)點(diǎn),然后通過(guò)根節(jié)點(diǎn)將整個(gè)網(wǎng)絡(luò)收集到的數(shù)據(jù)發(fā)送到基站。仿真結(jié)果表明,與LEACH算法相比,改進(jìn)算法降低了能耗,有效延長(zhǎng)了網(wǎng)絡(luò)生存周期。關(guān)鍵詞:無(wú)線傳感器網(wǎng)絡(luò); LEACH算法; 分簇;生命周期;能量消耗Abstract: W ireless sensor networks consisting of a large number of small sensorswith low-power transceiver can be an effective tool for apperceiving, collecting and computing data in a variety of environment.The collected data mustbe transmitted to the base station for further processing. Based on LEACH algorithm, this paper presents a novel clustering algorithm in which cluster are relatively fixed and the nodes re-organize themselves into new clusters every other round. It utilizes the Prim algorithm in the graph theory to form tree routing among cluster-head nodes, and selects the cluster-head with the largestPedas the root node. The cluster heads send data to the root node in a multi-hop manner and the root node then sends the gathered data by the whole network to the base station. Simulation results show that compared with LEACH, the improved algorithm can reduce the energy consumption and prolong the lifetime of the network.Key Words：wireless sensor network, LEACH algorithm, clustering, lifetime, energy consume1、前言無(wú)線傳感器網(wǎng)絡(luò)被認(rèn)為是在一定空間范圍內(nèi)密集分布的由大量體積小、廉價(jià)、電池供電的通信器件構(gòu)成的自組織系統(tǒng)由于無(wú)線傳感器網(wǎng)絡(luò)大都需要在無(wú)人看管、不更換電池或者幾乎不可能更換電池的條件下長(zhǎng)時(shí)間的工作，如何提高能量的有效利用率并延長(zhǎng)網(wǎng)絡(luò)壽命便成了一個(gè)重要問(wèn)題網(wǎng)絡(luò)數(shù)據(jù)傳輸離不開(kāi)路由協(xié)議,路由協(xié)議對(duì)網(wǎng)絡(luò)的整體性能有重要影響,因此,作為無(wú)線傳感器網(wǎng)絡(luò)核心技術(shù)之一的路由協(xié)議一直是研究的熱點(diǎn)。路由算法在路由協(xié)議中起著至關(guān)重要的作用,無(wú)線傳感器網(wǎng)絡(luò)中的路由算法從網(wǎng)絡(luò)邏輯結(jié)構(gòu)角度可以分為平面路由和層次路由。層次路由算法是無(wú)線傳感器網(wǎng)絡(luò)路由算法的研究重點(diǎn),其中,LEACH算法是比較具有代表性的層次型路由算法。本文在LEACH算法的基礎(chǔ)上,介紹一種改進(jìn)的路由算法,改進(jìn)算法的成簇方式相對(duì)固定,減少了構(gòu)造簇的能量消耗。簇形成之后,在簇頭間構(gòu)造最小生成樹(shù),簇間通過(guò)多跳方式通信,降低了簇頭節(jié)點(diǎn)之間長(zhǎng)距離通信的能耗。2、LEACH 算法2.1算法描述： LEACH協(xié)議的操作是按輪進(jìn)行的,每一輪包含簇建立和穩(wěn)定運(yùn)行2個(gè)階段,在簇建立階段,自適應(yīng)分簇結(jié)構(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)志值小于門(mén)限值T(n)的話,該節(jié)點(diǎn)就充當(dāng)本輪的簇頭節(jié)點(diǎn)。門(mén)限T(n)定義如下：T(n)=p/(1-p*(rmod(1/p)nGT(n)=0其他式中p為網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)所占總節(jié)點(diǎn)數(shù)目的百分比; r為當(dāng)前的輪數(shù);G為一個(gè)集合,集合中的節(jié)點(diǎn)是前1/p輪中沒(méi)有充當(dāng)過(guò)簇頭節(jié)點(diǎn)的節(jié)點(diǎn)。使用這個(gè)門(mén)限,每個(gè)節(jié)點(diǎn)會(huì)在1/p輪操作內(nèi)充當(dāng)一次簇頭節(jié)點(diǎn)。等過(guò)了1/p輪以后,所有的節(jié)點(diǎn)都充當(dāng)過(guò)簇頭節(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算法的不足及其改進(jìn)算法在LEACH算法中,每一輪循環(huán)都要重新構(gòu)造簇,而構(gòu)造簇的能量開(kāi)銷(xiāo)比較大。其次,遠(yuǎn)離匯聚節(jié)點(diǎn)的簇頭節(jié)點(diǎn)可能會(huì)由于長(zhǎng)距離發(fā)送數(shù)據(jù)而過(guò)早耗盡自身能量,造成網(wǎng)絡(luò)分割。另外,LEACH算法沒(méi)有考慮簇頭節(jié)點(diǎn)當(dāng)前的能量狀況,如果能量很低的節(jié)點(diǎn)當(dāng)選為簇頭節(jié)點(diǎn),那么將會(huì)加速該節(jié)點(diǎn)的死亡,影響整個(gè)網(wǎng)絡(luò)的生命周期。3、改進(jìn)的算3.1改進(jìn)算法的基本思想本文的改進(jìn)算法也按輪的機(jī)制運(yùn)行,但是與LEACH不同的是,改進(jìn)后的算法不必每一輪都重新構(gòu)建簇。改進(jìn)算法運(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)弱來(lái)選擇加入哪個(gè)簇,并通知相應(yīng)的活動(dòng)簇頭,完成簇的建立。簇建立之后,簇內(nèi)節(jié)點(diǎn)通過(guò)單跳通信方式直接向其簇頭節(jié)點(diǎn)傳送數(shù)據(jù)。當(dāng)N為偶數(shù)時(shí),原來(lái)的簇固定不變。如果此時(shí)活動(dòng)簇頭節(jié)點(diǎn)能量低于某一個(gè)門(mén)限值時(shí),則在原簇內(nèi)重新選擇簇頭節(jié)點(diǎn),以簇內(nèi)剩余能量最多的節(jié)點(diǎn)為新的簇頭節(jié)點(diǎn),這樣產(chǎn)生的簇頭在新算法中稱為固定簇頭。為降低簇頭(包括活動(dòng)簇頭和固定簇頭)節(jié)點(diǎn)的通信代價(jià),在簇頭間構(gòu)造樹(shù)形路由,簇頭間以多跳方式通信。3.2改進(jìn)算法的描述（1）簇的建立和簇內(nèi)通信改進(jìn)算法第N輪的開(kāi)始,首先判斷N是奇數(shù)還是偶數(shù)。當(dāng)N是奇數(shù)時(shí),就需要重新構(gòu)建簇,此時(shí),采用與LEACH-EA相同的簇頭選擇機(jī)制。活動(dòng)簇頭選擇過(guò)程如下:每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)01之間的隨機(jī)數(shù),如果這個(gè)數(shù)小于閾值T(n),則該節(jié)向周?chē)?jié)點(diǎn)廣播它是簇頭的消息,參照LEACH-EA的閾值計(jì)算公式T(n)可表示為:T(n)=（p（1-p*(rmod(1/p)）（En-currentEaver）, nGT(n)=0,其它其中,p是簇頭占所有節(jié)點(diǎn)的百分比,即節(jié)點(diǎn)當(dāng)選簇頭的概率;r代表目前進(jìn)行的輪數(shù);G表示最近1/p輪中還未當(dāng)選過(guò)簇頭的節(jié)點(diǎn)集合;En-current表示節(jié)點(diǎn)的當(dāng)前能量;Eaver表示每一輪結(jié)束后節(jié)點(diǎn)的平均能量。節(jié)點(diǎn)當(dāng)選為活動(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í),則原來(lái)的簇固定不變。如果活動(dòng)簇頭節(jié)點(diǎn)能量低于某一個(gè)規(guī)定的門(mén)限值,則在原簇內(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)必須保持其接收器一直打開(kāi),以接收簇內(nèi)不同節(jié)點(diǎn)的數(shù)據(jù),然后進(jìn)行數(shù)據(jù)融合。3.2.2簇頭間樹(shù)形路由的構(gòu)建與簇間通信假設(shè)要在n個(gè)城市之間建立通信聯(lián)絡(luò)網(wǎng),則連通n個(gè)城市只需要n-1條線路。如果用連通網(wǎng)的頂點(diǎn)來(lái)表示城市,邊表示兩城市之間的線路,賦予邊的權(quán)值代表相應(yīng)的代價(jià),需要考慮如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通信網(wǎng)。對(duì)于n個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹(shù),每一棵生成樹(shù)都可以是一個(gè)通信網(wǎng),要選擇一棵生成樹(shù),使總的代價(jià)最少,這就是構(gòu)造連通網(wǎng)的最小代價(jià)生成樹(shù)(Minimum Cost Spanning Tree)問(wèn)題7(簡(jiǎn)稱為最小生成樹(shù)問(wèn)題)。考慮將此問(wèn)題中的城市與無(wú)線傳感器網(wǎng)絡(luò)中的簇頭節(jié)點(diǎn)相對(duì)應(yīng),可以在簇頭節(jié)點(diǎn)之間構(gòu)造最小生成樹(shù),降低簇頭節(jié)點(diǎn)間的通信代價(jià)。prim算法構(gòu)造最小生成樹(shù)的過(guò)程:假設(shè)N=(V,E)為連通網(wǎng),V表示網(wǎng)中頂點(diǎn)的集合,E表示邊的集合,U是V的一非空子集,TE為最小生成樹(shù)中邊的集合。首先,從集合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的最小生成樹(shù)。本文參照文獻(xiàn)5,利用prim算法構(gòu)造最小生成樹(shù)的原理在簇頭間構(gòu)造樹(shù)形路由,在文獻(xiàn)5的基礎(chǔ)上進(jìn)行了改進(jìn),過(guò)程如下:1)選出的簇頭節(jié)點(diǎn)將自己的剩余能量和到基站的距離加入到廣播數(shù)據(jù)包中進(jìn)行廣播,根據(jù)其剩余能量和到基站的距離關(guān)系參數(shù)Ped,選取Ped最大的簇頭節(jié)點(diǎn)作為樹(shù)根節(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)造最小生成樹(shù)原理,樹(shù)根節(jié)點(diǎn)選擇下一跳中最小有效簇頭節(jié)點(diǎn)作為其子節(jié)點(diǎn),該子節(jié)點(diǎn)以樹(shù)根節(jié)點(diǎn)為父節(jié)點(diǎn),同時(shí)向下一跳簇頭節(jié)點(diǎn)繼續(xù)搜索。若該子節(jié)點(diǎn)搜索成功,則繼續(xù)執(zhí)行路由算法,若沒(méi)有搜索到最小有效簇頭節(jié)點(diǎn),則返回該根節(jié)點(diǎn)繼續(xù)搜索。3)重復(fù)2),直到所有節(jié)點(diǎn)加入到樹(shù)中,構(gòu)成樹(shù)形網(wǎng)絡(luò)路由。簇頭節(jié)點(diǎn)通過(guò)樹(shù)網(wǎng)絡(luò)路由,以多跳方式通信,最后作為樹(shù)根節(jié)點(diǎn)的簇頭將數(shù)據(jù)傳給基站。簇頭間的樹(shù)形路由如圖1所示。4、算法的仿真分析采用Matlab仿真工具,對(duì)LEACH算法、LEACH-EA算法和改進(jìn)的算法進(jìn)行仿真比較。仿真場(chǎng)景假設(shè)有100個(gè)傳感器節(jié)點(diǎn)組成,節(jié)點(diǎn)隨機(jī)分布在一個(gè)介于(x=0,y=0)與(x=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ù)比較接近,改進(jìn)算法相對(duì)來(lái)說(shuō)比前兩種算法更優(yōu)越。網(wǎng)絡(luò)生命周期是衡量網(wǎng)絡(luò)質(zhì)量的一個(gè)重要標(biāo)志,圖3顯示了當(dāng)節(jié)點(diǎn)死亡率為1%,50%,100%時(shí)所經(jīng)過(guò)的輪數(shù)。從圖中可以看出新算法的通信輪數(shù)高于LEACH和LEACH-EA算法,表明改進(jìn)之后得到的新算法降低了能耗,延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間。5、參考文獻(xiàn)1Tao Yang,Zheng Yaling.The combination of the optimal number of cluster-heads and energy adaptive cluster-head selectionAlgorithm in wireless sensor networksC.WiCOM 2006 International Conference.Wuhan,China,2006:1-4.2Hou Guofeng,Tang K W.Evaluation of LEACH protocol subject to different traffic modelsC/COIN-NGNCON 2006.Hyatt Regency Jeju,Korea,2006:281-283.3Heinzelman,W.R.,A.Chandrakasan,andH.Balakrishnan.Energy-Ef-ficient Communication Protocol for Wireless Microsensor Networks,Proc.of the 33rd AnnuaHawaiiInternationalConferenceonSystemSciences,January47,2000.Maui,Hawaii.p.3 0053 0144Handy MJ,Haase M,Timmermann D.Low energy a-daptive clustering hierarchy with deterministic clus-ter-head selectionA.Proc of the 4th IEEE Conf onMobile and Wireless Communications NetworksC.Stockholm: IEEE Communications Society, 2002.368-3725王振興,熊偉麗,徐保國(guó).基于LEACH的簇樹(shù)網(wǎng)絡(luò)路由算法