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