無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的研究與改1.doc

河南師范大學(xué)本科畢業(yè)論文（設(shè)計）無線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的研究與改進(jìn)摘要:無線傳感器網(wǎng)絡(luò)由許多具有低功率無線收發(fā)裝置的傳感器節(jié)點(diǎn)成,能夠有效地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中的相關(guān)信息,并發(fā)送給遠(yuǎn)處的基站進(jìn)一步處理。由于傳感器節(jié)點(diǎn)能量有限,路由協(xié)議必須盡可能地減少能量消耗,延長網(wǎng)絡(luò)生命周期。在LEACH算法基礎(chǔ)上,提出一種改進(jìn)的路由算法,改進(jìn)后的算法采用相對固定的成簇方式,每隔一輪重新構(gòu)建簇。利用圖論中的prim算法,選擇每輪中Ped最大的簇頭作為根節(jié)點(diǎn),在簇頭節(jié)點(diǎn)之間構(gòu)造樹形路由,簇頭之間以多跳方式將收集到的數(shù)據(jù)發(fā)送到根節(jié)點(diǎn),然后通過根節(jié)點(diǎn)將整個網(wǎng)絡(luò)收集到的數(shù)據(jù)發(fā)送到基站。仿真結(jié)果表明,與LEACH算法相比,改進(jìn)算法降低了能耗,有效延長了網(wǎng)絡(luò)生存周期。關(guān)鍵詞:無線傳感器網(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ǎng)絡(luò)被認(rèn)為是在一定空間范圍內(nèi)密集分布的由大量體積小、廉價、電池供電的通信器件構(gòu)成的自組織系統(tǒng)由于無線傳感器網(wǎng)絡(luò)大都需要在無人看管、不更換電池或者幾乎不可能更換電池的條件下長時間的工作，如何提高能量的有效利用率并延長網(wǎng)絡(luò)壽命便成了一個重要問題網(wǎng)絡(luò)數(shù)據(jù)傳輸離不開路由協(xié)議,路由協(xié)議對網(wǎng)絡(luò)的整體性能有重要影響,因此,作為無線傳感器網(wǎng)絡(luò)核心技術(shù)之一的路由協(xié)議一直是研究的熱點(diǎn)。路由算法在路由協(xié)議中起著至關(guān)重要的作用,無線傳感器網(wǎng)絡(luò)中的路由算法從網(wǎng)絡(luò)邏輯結(jié)構(gòu)角度可以分為平面路由和層次路由。層次路由算法是無線傳感器網(wǎng)絡(luò)路由算法的研究重點(diǎn),其中,LEACH算法是比較具有代表性的層次型路由算法。本文在LEACH算法的基礎(chǔ)上,介紹一種改進(jìn)的路由算法,改進(jìn)算法的成簇方式相對固定,減少了構(gòu)造簇的能量消耗。簇形成之后,在簇頭間構(gòu)造最小生成樹,簇間通過多跳方式通信,降低了簇頭節(jié)點(diǎn)之間長距離通信的能耗。2、LEACH 算法2.1算法描述： LEACH協(xié)議的操作是按輪進(jìn)行的,每一輪包含簇建立和穩(wěn)定運(yùn)行2個階段,在簇建立階段,自適應(yīng)分簇結(jié)構(gòu)形成,在穩(wěn)定運(yùn)行階段進(jìn)行數(shù)據(jù)傳輸。在簇建立階段,選取一定數(shù)目的節(jié)點(diǎn)充當(dāng)簇頭節(jié)點(diǎn)。每個節(jié)點(diǎn)隨機(jī)分配一個在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)nGT(n)=0其他式中p為網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)所占總節(jié)點(diǎn)數(shù)目的百分比; r為當(dāng)前的輪數(shù);G為一個集合,集合中的節(jié)點(diǎn)是前1/p輪中沒有充當(dāng)過簇頭節(jié)點(diǎn)的節(jié)點(diǎn)。使用這個門限,每個節(jié)點(diǎn)會在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ù)收到消息的信號強(qiáng)弱,選取信號最強(qiáng)的發(fā)送源節(jié)點(diǎn)作為自己的簇頭節(jié)點(diǎn),加入那個簇,并向簇頭發(fā)送加入的請求。簇頭收到請求后為成員節(jié)點(diǎn)設(shè)定一個TDMA時隙表。此后的簇穩(wěn)定階段,節(jié)點(diǎn)在屬于自己的時隙里將采集的數(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)造簇的能量開銷比較大。其次,遠(yuǎn)離匯聚節(jié)點(diǎn)的簇頭節(jié)點(diǎn)可能會由于長距離發(fā)送數(shù)據(jù)而過早耗盡自身能量,造成網(wǎng)絡(luò)分割。另外,LEACH算法沒有考慮簇頭節(jié)點(diǎn)當(dāng)前的能量狀況,如果能量很低的節(jié)點(diǎn)當(dāng)選為簇頭節(jié)點(diǎn),那么將會加速該節(jié)點(diǎn)的死亡,影響整個網(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ù)時,新算法采用與LEACH-EA相同的機(jī)制選擇簇頭,這樣產(chǎn)生的簇頭在新算法中稱為活動簇頭,活動簇頭選定后,該活動簇頭發(fā)布自己是簇頭的消息,非簇頭節(jié)點(diǎn)根據(jù)接收信號的強(qiáng)弱來選擇加入哪個簇,并通知相應(yīng)的活動簇頭,完成簇的建立。簇建立之后,簇內(nèi)節(jié)點(diǎn)通過單跳通信方式直接向其簇頭節(jié)點(diǎn)傳送數(shù)據(jù)。當(dāng)N為偶數(shù)時,原來的簇固定不變。如果此時活動簇頭節(jié)點(diǎn)能量低于某一個門限值時,則在原簇內(nèi)重新選擇簇頭節(jié)點(diǎn),以簇內(nèi)剩余能量最多的節(jié)點(diǎn)為新的簇頭節(jié)點(diǎn),這樣產(chǎn)生的簇頭在新算法中稱為固定簇頭。為降低簇頭(包括活動簇頭和固定簇頭)節(jié)點(diǎn)的通信代價,在簇頭間構(gòu)造樹形路由,簇頭間以多跳方式通信。3.2改進(jìn)算法的描述（1）簇的建立和簇內(nèi)通信改進(jìn)算法第N輪的開始,首先判斷N是奇數(shù)還是偶數(shù)。當(dāng)N是奇數(shù)時,就需要重新構(gòu)建簇,此時,采用與LEACH-EA相同的簇頭選擇機(jī)制?；顒哟仡^選擇過程如下:每個節(jié)點(diǎn)產(chǎn)生一個01之間的隨機(jī)數(shù),如果這個數(shù)小于閾值T(n),則該節(jié)向周圍節(jié)點(diǎn)廣播它是簇頭的消息,參照LEACH-EA的閾值計算公式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)選過簇頭的節(jié)點(diǎn)集合;En-current表示節(jié)點(diǎn)的當(dāng)前能量;Eaver表示每一輪結(jié)束后節(jié)點(diǎn)的平均能量。節(jié)點(diǎn)當(dāng)選為活動簇頭后,該活動簇頭廣播自己是簇頭的消息,非簇頭節(jié)點(diǎn)根據(jù)接收信號的強(qiáng)弱。選擇加入哪個簇,并通知相應(yīng)的活動簇頭,完成簇的建立?；顒哟仡^接收到所有的加入信息后,就產(chǎn)生一個TDMA定時信息表,給簇中每個非簇頭成員節(jié)點(diǎn)分配傳送數(shù)據(jù)的時間片,成員節(jié)點(diǎn)只能在其特定的時間片內(nèi)與簇頭節(jié)點(diǎn)進(jìn)行通信。算法執(zhí)行首輪時,簇的建立與此種情況相同。當(dāng)N是偶數(shù)時,則原來的簇固定不變。如果活動簇頭節(jié)點(diǎn)能量低于某一個規(guī)定的門限值,則在原簇內(nèi)重新選擇簇頭節(jié)點(diǎn),以簇內(nèi)剩余能量最多的節(jié)點(diǎn)為簇頭節(jié)點(diǎn),這樣產(chǎn)生的簇頭稱為固定簇頭。固定簇頭與簇內(nèi)成員的通信方式和活動簇頭一樣。當(dāng)節(jié)點(diǎn)持續(xù)采集監(jiān)測數(shù)據(jù)時,在其相應(yīng)時間片,使用最小能量傳給簇頭節(jié)點(diǎn)。節(jié)點(diǎn)不發(fā)送數(shù)據(jù)時,關(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個城市之間建立通信聯(lián)絡(luò)網(wǎng),則連通n個城市只需要n-1條線路。如果用連通網(wǎng)的頂點(diǎn)來表示城市,邊表示兩城市之間的線路,賦予邊的權(quán)值代表相應(yīng)的代價,需要考慮如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個通信網(wǎng)。對于n個頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹,每一棵生成樹都可以是一個通信網(wǎng),要選擇一棵生成樹,使總的代價最少,這就是構(gòu)造連通網(wǎng)的最小代價生成樹(Minimum Cost Spanning Tree)問題7(簡稱為最小生成樹問題)?？紤]將此問題中的城市與無線傳感器網(wǎng)絡(luò)中的簇頭節(jié)點(diǎn)相對應(yīng),可以在簇頭節(jié)點(diǎn)之間構(gòu)造最小生成樹,降低簇頭節(jié)點(diǎn)間的通信代價。prim算法構(gòu)造最小生成樹的過程:假設(shè)N=(V,E)為連通網(wǎng),V表示網(wǎng)中頂點(diǎn)的集合,E表示邊的集合,U是V的一非空子集,TE為最小生成樹中邊的集合。首先,從集合V中取一個頂點(diǎn)V0加入集合U中,這時U=V0,集合TE=,接著重復(fù)執(zhí)行以下操作:從V0出發(fā),在集合V中尋找與U中頂點(diǎn)相鄰頂點(diǎn)中權(quán)值最小的邊的另一頂點(diǎn)V1,然后將V1并入U中,并將該邊加入集合TE中,直到U=V為止。這時TE中有n-1條邊,T=(U,TE)為N的最小生成樹。本文參照文獻(xiàn)5,利用prim算法構(gòu)造最小生成樹的原理在簇頭間構(gòu)造樹形路由,在文獻(xiàn)5的基礎(chǔ)上進(jìn)行了改進(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)編號,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),同時向下一跳簇頭節(jié)點(diǎn)繼續(xù)搜索。若該子節(jié)點(diǎn)搜索成功,則繼續(xù)執(zhí)行路由算法,若沒有搜索到最小有效簇頭節(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仿真工具,對LEACH算法、LEACH-EA算法和改進(jìn)的算法進(jìn)行仿真比較。仿真場景假設(shè)有100個傳感器節(jié)點(diǎn)組成,節(jié)點(diǎn)隨機(jī)分布在一個介于(x=0,y=0)與(x=100,y=100)的區(qū)域內(nèi),每個節(jié)點(diǎn)都擁有相同的初始能量E0=0.5J,仿真模型參照文獻(xiàn)6。如圖2所示,前1000輪中, LEACH和LEACH-EA算法的節(jié)點(diǎn)存活數(shù)比較接近,改進(jìn)算法相對來說比前兩種算法更優(yōu)越。網(wǎng)絡(luò)生命周期是衡量網(wǎng)絡(luò)質(zhì)量的一個重要標(biāo)志,圖3顯示了當(dāng)節(jié)點(diǎn)死亡率為1%,50%,100%時所經(jīng)過的輪數(shù)。從圖中可以看出新算法的通信輪數(shù)高于LEACH和LEACH-EA算法,表明改進(jìn)之后得到的新算法降低了能耗,延長了網(wǎng)絡(luò)的生存時間。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王振興,熊偉麗,徐保國.基于LEACH的簇樹網(wǎng)絡(luò)路由算法