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

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