1、無線傳感器網絡路由協議leach的研究與改進摘要:無線傳感器網絡由許多具有低功率無線收發裝置的傳感器節點成, 能夠冇效地感知、采集和處理網絡覆蓋區域中的相關信息,并發送給遠處的基站 進一步處理。由于傳感器節點能量有限，路由協議必須盡可能地減少能量消耗, 延長網絡生命周期。在leach算法基礎上，提出一種改進的路由算法，改進后的 算法采用相對同定的成簇方式，每隔一輪重新構建簇。利用圖論屮的prim算法, 選擇每輪中ped最大的簇頭作為根節點，在簇頭節點z間構造樹形路由,簇頭z 間以多跳方式將收集到的數據發送到根節點，然后通過根節點將整個網絡收集 到的數據發送到基站。仿真結果表明，與leach算法

2、相比，改進算法降低了能耗, 有效延t了網絡生存周期。關鍵詞:無線傳感器網絡;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 transmi

3、tted 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

4、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 le

5、ach, the improved algorithm can reduce the energy consumption and prolong the lifetime of the networkkey words： wireless sensor network, leach algorithm, clustering, lifetime, energy consume1、前言無線傳感器網絡被認為是在一定空間范圍內密集分布的由大量體積小、廉 價、電池供電的通信器件構成的口組織系統.由于無線傳感器網絡大都需耍在 無人看管、不更換電池或者幾乎不可能更換屯池的條件下長時間的工作，如何 提高能

6、量的有效利用率并延長網絡壽命便成了一個重要問題.網絡數據傳輸離 不開路由協議，路由協議對網絡的整體性能有重要影響，因此，作為無線傳感器網 絡核心技術z的路由協議一直是研究的熱點。路由算法在路由協議屮起著至 關重要的作用，無線傳感器網絡中的路由算法從網絡邏輯結構角度可以分為平 面路由和層次路由。層次路由算法是無線傳感器網絡路出算法的研究重點，其 p,leach算法是比較具有代表性的層次型路由算法。木文在leach算法的 基礎上，介紹一種改進的路由算法，改進算法的成簇方式相對固定,減少了構造簇 的能量消耗。簇形成z后，在簇頭間構造最小生成樹，簇間通過多跳方式通信，降 低了簇頭節點z間長距離通信的能

7、耗。2、leach 算法2.1算法描述：leach協議的操作是按輪進行的，每一輪包含簇建立和穩定運行2個階段, 在簇建立階段，自適應分簇結構形成，在穩定運行階段進行數據傳輸。在簇建立階 段,選取-定數口的節點充當簇頭節點。每個節點隨機分配一個在0到1之間的 數字,成為其標志值。如果節點的標志值小于門限值t(n)的話，該節點就充當本輪 的簇頭節點。門限t(n)定義如下：t(n)=p/(1 -p*(rmod(l/p) n 丘 gt(n)= 0其他式屮p為網絡中簇頭節點所占總節點數目的百分比;r為當前的輪數;g為一個 集合，集合中的節點是m 1/p輪中沒有充當過簇頭節點的節點。使用這個門限, 每個節

8、點會在1/p輪操作內充當一次簇頭節點。等過了 1/p輪以后，所有的節點 都充當過簇頭節點，從而又可以重新充當簇頭節點。節點被選為簇頭后，就向外發 送廣播信息;其他節點就根據收到消息的信號強弱,選取信號最強的發送源節點 作為自己的簇頭節點，加入那個簇，并向簇頭發送加入的請求o簇頭收到請求后為 成員節點設定一個tdma時隙表。此后的簇穩定階段，節點在屈丁自己的時隙 里將采集的數據發送給簇頭節點，簇頭節點將接收到的成員節點的數據進行融 合，然后，直接發送給基站。2.2 leach算法的不足及其改進算法在leach算法中，每一輪循環都要重新構造簇，而構造簇的能量開銷比較 大。其次,遠離匯聚節點的簇頭節

9、點可能會由于長距離發送數據而過早耗盡自身 能量，造成網絡分割。另外,leach算法沒有考慮簇頭節點當前的能量狀況，如果 能量很低的節點當選為簇頭節點,那么將會加速該節點的死廣，影響整個網絡的 生命周期。3、改進的算3.1改進算法的基木思想木文的改進算法也按輪的機制運行，但是與leach不同的是,改進后的算 法不必每一輪都重新構建簇。改進算法運行到第n輪，當n為奇數時，新算法采 用與leach-ea相同的機制選擇簇頭，這樣產生的簇頭在新算法屮稱為活動簇 頭，活動簇頭選定后，該活動簇頭發布口己是簇頭的消息，非簇頭節點根據接收信 號的強弱來選擇加入哪個簇，并通知相應的活動簇頭，完成簇的建立。簇建立之

10、后, 簇內節點通過單跳通信方式直接向其簇頭節點傳送數據。當n為偶數時,原來的 簇固定不變。如果此時活動簇頭節點能量低于某一個門限值時，則在原簇內重新 選擇簇頭節點，以簇內剩余能量最多的節點為新的簇頭節點，這樣產生的簇頭在 新算法中稱為固定簇頭。為降低簇頭(包括活動簇頭和固定簇頭)節點的通信代 價，在簇頭間構造樹形路由，簇頭間以多跳方式通信。3.2改進算法的描述(1) 簇的建立和簇內通信改進算法第n輪的開始，首先判斷n是奇數還是偶數。當n是奇數時，就需 要重新構建簇，此時，采用與leach-ea相同的簇頭選擇機制。活動簇頭選擇過 程如下:每個節點產生一個01 z間的隨機數,如果這個數小于閾值t(

11、n),則該節 向周圍節點廣播它是簇頭的消息，參照leach-ea的閾值計算公式t(n)可表示 為：t(n)= (p4- (l-p*(rmod(l/p) x (en-current4-eaver) , ngt(n)=o,其它其中,p是簇頭占所冇節點的百分比，即節點當選簇頭的概率;i代表目前進行的輪 數;g表示最近1/p輪屮還未當選過簇頭的節點集合;en-current表示節點的當前 能量;eaver表示每一輪結束后節點的平均能量。節點當選為活動簇頭后,該活動 簇頭廣播自己是簇頭的消息，非簇頭節點根據接收信號的強弱。選擇加入哪個簇, 并通知相應的活動簇頭，完成簇的建立。活動簇頭接收到所有的加入信息

12、后，就產 生一個tdma定時信息表，給簇中每個非簇頭成員節點分配傳送數據的時間片, 成員節點只能在其特定的吋間片內與簇頭節點進行通信。算法執行首輪時，簇的 建立與此種情況相同。當n是偶數時，則原來的簇固定不變。如果活動簇頭節點 能量低于某一個規定的門限值，則在原簇內重新選擇簇頭節點，以簇內剩余能量 最多的節點為簇頭節點，這樣產生的簇頭稱為固定簇頭。固定簇頭與簇內成員的 通信方式和活動簇頭一樣。當節點持續采集監測數據時，在其相應時間片,使用最 小能量傳給簇頭節點。節點不發送數據吋，關閉節點以節約能量。簇頭節點必須 保持其接收器一直打開，以接收簇內不同節點的數據,然后進行數據融合。3.2.2簇頭間

13、樹形路由的構建與簇間通信假設要在n個城市之間建立通信聯絡網，則連通n個城市只需要nl條線路。 如果用連通網的頂點來表示城市，邊表示兩城市之間的線路，賦予邊的權值代表 相應的代價,需要考慮如何在最節省經費的前提下建立這個通信網。對于n個頂 點的連通網可以建立許多不同的生成樹，每一 棵生成樹都可以是一個通信網，要 選擇一棵生成樹，使總的代價最少，這就是構造連通網的最小代價生成樹 (minimum cost spanning tree)問題7(簡稱為最小牛成樹問題)。考慮將此問題 屮的城市與無線傳感器網絡屮的簇頭節點相對應，可以在簇頭節點z間構造最 小生成樹，降低簇頭節點間的通信代價。prim算法構

14、造最小生成樹的過程:假設 n=(v,e)為連通網,v表示網中頂點的集合,e表示邊的集合,u是v的一非空子 集,te為最小生成樹中邊的集合。首先,從集合v中取一個頂點v0加入集合u 中，這時u=vo傑合te=，接著重復執行以下操作:從v0出發,在集合v中尋 找與u中頂點相鄰頂點中權值最小的邊的另一頂點vi撚后將vi并入u中，并 將該邊加入集合te中，直到u二v為止。這時te中有n-1條邊,t=(u,te)為n的 最小生成樹。本文參照文獻5,利用prim算法構造最小生成樹的原理在簇頭間 構造樹形路由，在文獻5的基礎上進行了改進，過程如下:1)選出的簇頭節點將口 己的剩余能量和到基站的距離加入到廣播

15、數據包中進行廣播，根據其剩余能量 和到基站的距離關系參數ped,選取ped最大的簇頭節點作為樹根節點。ped的 定義公式:ped(i)二ey2(i)de(i)(3)其中,i是傳感器節點編號,ey(i)是節點i的剩余能 量,de(i)是節點i到基站的距離。2)利用prim算法構造最小生成樹原理,樹根節 點選擇卜一跳中最小有效簇頭節點作為其了節點，該了節點以樹根節點為父節 點，同時向下-跳簇頭節點繼續搜索。若該子節點搜索成功，則繼續執行路曲算法, 若沒有搜索到最小有效簇頭節點,則返冋該根節點繼續搜索。3)重復2),直到所有 節點加入到樹中，構成樹形網絡路由。簇頭節點通過樹網絡路由，以多跳方式通信,

16、 最后作為樹根節點的簇頭將數據傳給基站。簇頭間的樹形路由如圖1所示。4、算法的仿真分析采用matlab仿真工具，對leach算法、leach-ea算法和改進的算法進 行仿真比較。仿真場景假設有100個傳感器節點組成，節點隨機分布在一個介于 (x=0,y=0)tj(x=100,y=100)的區域內，每個節點都擁冇相同的初始能量e0=0.5j,仿 真模型參照文獻。如圖2所示，前1000輪'i1, leach和leach-ea算法的節 點存活數比較接近,改進算法相對來說比前兩種算法更優越。網絡生命周期是衡 量網絡質量的一個重耍標志，圖3顯示了當節點死廣率為1%,50%,100%時所經 過的輪

17、數。從圖中可以看出新算法的通信輪數高丁 leach和leach-ea算法, 表明改進z后得到的新算法降低了能耗，延長了網 絡的生存時間。mws2 mm險leach 辺 leachea aw5、參考文獻1 tao 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.wuha

18、n,china,2006:1 -4.2 hou guofeng,tang k w.evaluation of leach protocol subject to different trafficmodelscl/coin-ngncon2oo6.hyattregencyjeju,korea,2006:281 -283.3 heinzelman,w.r.,a.chandrakasan,andh.balakrishnan.energy-ef-ficient communication protocol for wireless microsensor networks,proc.of the 33

19、rd annuahawaiilnternationalconferenceonsystemsciences.january 4 7,2000.maui,h awaii.p.3 0053 0144 handy 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-372王振興,熊偉麗，徐保國.st leach的簇樹網絡