基于LEACH的WSN路由算法研究

馬簫雯，余 翔，許 未

(重慶郵電大學電信增值業務研究所，重慶400065)

0 引言

隨著無線通信技術以及傳感器技術的飛速發展，由具有感知能力、計算能力和通信能力節點組成的無線傳感器網絡［1-2］的研究越來越受到研究人員的重視。組成傳感器網絡的節點包括數據匯聚節點(sink)和普通的傳感器節點。由于傳感器節點能量有限，在進行傳感器網絡路由研究的時候，降低能耗使得無線傳感器網絡的整體存活時間延長是需要考慮的［3］。

低功耗自適應聚類路由協議［4］(Low Energy Adaptive Clustering Hierarchy，LEACH)是無線傳感器網絡中一種經典的分層次路由協議，算法通過循環隨機地選取簇首節點來提高網絡的能量利用率和延長系統的生命周期。相對于無線傳感器網絡的傳統平面靜態路由協議，LEACH可以將網絡生存時間延長接近15%［5］。但是，LEACH協議在簇首選擇采用的是各個節點等概率隨機成為簇首的方式，沒有考慮到節點的能量以及簇首與基站的距離等因素，而這些因素恰恰可能導致所選擇的簇首不是最優，從而影響到整個網絡的性能。針對LEACH協議存在的一些不足，提出一些改進建議，并針對其中的部分建議做了仿真驗證，所采取的措施有效地提高了節點的能量利用率同時也延長了整個網絡的生命周期。

1 LEACH協議

LEACH路由協議是Heinzelman(MIT，電子與計算系)于2000年為WSN設計的基于分層的低功耗自適應聚類路由算法。LEACH協議的工作過程被劃分為周期性的“輪”，每輪包括成簇和數據傳輸兩個階段。在成簇階段，節點之間首先按照一定的策略進行簇首選舉，等到簇首節點確定之后，將向全網廣播自身本輪擔任簇首的消息，其他節點根據接收到的廣播信號的強度來決定本輪所要加入的簇，最后，簇首節點接收加入請求消息并創建TDMA和CDMA編碼機制。在數據傳輸階段，簇首節點首先接收簇內成員節點采集的監測數據，然后對接收到的數據和自身的數據進行數據融合，最終將融合后的數據發送給基站［6］。

簇首節點的選取是LEACH算法的核心組成部分，這部分在整個LEACH協議中占有很重要的位置，其具體的選擇策略描述如下:在成簇階段，每個傳感器節點產生一個［0，1］之間的隨機數，如若該數小于某一個閥值Pi(t)，則向全網通告自己本輪擔任簇首的消息;若該節點之前已經擔任過簇首，則將閥值Pi(t)設置為0，表明本輪不再擔任簇首;反之，如果節點之前沒有擔任過簇首，則在本輪中以閥值Pi(t)為概率競選簇首;當網絡中只剩下一個節點沒有擔任過簇首時，該節點將把閥值Pi(t)設為1，表明自己本輪無條件的成為簇首。其中Pi(t)的計算公式如下:

式中，Ci(t)表示節點i在最近rmod(N/k)輪是否擔當過簇首節點，若擔當過簇首，則Ci(t)=0，否則Ci(t)=1;k表示網絡中簇首節點的個數，在一個已知的目標區域內，面積為M×M，傳感器節點總數為N，節點均勻分布在檢測區域中，即 ρ=(1/(M2/k))。可以通過下面公式推導出網絡中最優的分簇個數:

式(2)、式(3)、式(4)中:εfs和 εmp表示無線能量模型中的參數;dtoCH是簇內成員節點到簇首節點的距離;Etotal表示總共消耗的能量;dtoBS表示簇首節點到基站之間的距離;Eelec表示發射電路和接收電路所消耗的能量;EDA表示節點進行數據融合所消耗的能量。

在每輪的穩定階段，傳感器節點將采集的數據傳送到簇首節點。簇首節點對采集的數據進行數據融合后再將信息傳送給匯聚中心，匯聚中心將數據傳送給監控中心來進行數據的處理。穩定階段持續一段時間之后，網絡重新進行簇的建立階段，也就是進行下一輪的簇重建，這樣不斷地循環。

2 LEACH協議的不足及改進方案

2.1 LEACH協議的不足

LEACH的不足在于，每輪進行都要選擇簇頭并劃分簇，并且簇頭需要一直處于醒著的狀態以接收數據，這樣系統開銷較大，離散式區域算法對節點位置等要求不高，雖然能夠通過公式推導出可能的分簇數目，但無法確定最優的簇數目。LEACH采用TDMA的MAC層機制，而事實上，在分配給節點的每個時隙，節點并不是都有數據要發送給簇頭，這樣的通信機制不能有效利用帶寬，浪費了能量。LEACH還要求節點之間以及節點與sink之間都可以直接通信，因此局限了網絡的可擴展性［7，8］。

LEACH以循環的方式隨機選取簇首，將整個網絡的能量負載平均分配到每個傳感器節點中，從而降低能源消耗，提高網絡整體生存時間。由于冗余數據被大量消除，因而在能耗方面有較好的性能。但LEACH仍存在如下不足之處。首先，LEACH算法是由網絡中的傳感器節點自組織的形成簇，簇首的選擇具有極大的隨機性。在該算法中進行簇首選擇時沒有考慮節點的剩余能量、周圍鄰節點的數目以及已經擔任過簇首的次數等因素，這樣會加重簇首的負擔，使能耗不均［9］。當一個節點做簇首的次數過多時，不但自身的能量消耗加大，而且會使得距離自身較遠的節點消耗較多的能量，不利于整個網絡中節點能量的均衡和網絡壽命的延長;其次，不同的簇首數目也會影響到整個網絡的生存時間，LEACH算法簇首選擇的隨機性導致簇首數目的不確定。

基于以上LEACH算法在簇首選擇過程中的不足，對算法進行改進，改進后的算法跟LEACH算法采用相同的網絡要求。

2.2 改進算法LEACH_NEW描述

2.2.1 LEACH_NEW設計思路

根據上文中所指出的LEACH算法在簇首選擇方面存在的問題，對LEACH算法做如下改進:

①靜態分簇，在第一輪簇首選擇之前根據節點位置情況進行靜態分簇，并且之后不再重新分簇，只在該簇內選擇最佳節點成為本簇的簇首節點，簇首節點在廣播自己成為簇首的信息時也只是向本簇內的成員節點廣播，不需要全網廣播，大大減小了節點的能量消耗;

②在簇首選擇過程中，將節點的剩余能量和網絡的平均能量作為參數考慮，對閥值的計算公式進行改進，使得選出的簇首節點更加有利于網絡能耗的均衡以及整個網絡的生存;

③在數據傳輸階段，利用參數記錄簇頭節點的鄰簇頭節點的數目、簇頭到基站的最佳跳數和剩余能量，以便在多跳傳輸時簇頭節點能夠選擇更合適的下一跳節點并且減小節點的能耗。

2.2.2 LEACH_NEW的工作過程

LEACH_NEW的工作過程與LEACH一樣，也分為3個階段。即簇首的選擇階段、簇形成階段和數據傳輸階段。

首先由于考慮到每一輪重新建立簇過程中所有節點消耗的能量，本文算法在算法執行開始時先采用靜態分簇方式，在初始過程中節點就將簇分好，并進行相應的優化。之后簇內的節點不再發生變化，每一輪簇首的選擇更新都在原簇內進行，這樣減少了每一輪之前分簇時節點所消耗的不必要的能量。

①在第一輪簇首選擇階段，若按照式(1)得到的閥值選擇簇首，就會出現簇首選擇不當的問題。所以改進算法利用新的閥值計算公式如下:

式中，Ecurrent表示節點的當前能量，Einitial為節點的初始能量，Nneighbour表示節點的鄰節點數目，CHtime表示節點在之前的輪中被選為簇首的次數。

②簇形成階段，經過簇首選擇階段已經選出了網絡中擔任簇首的節點，隨后每個簇首節點利用CSMA協議向自己管轄范圍內的所有剩余節點以相同的傳輸能量發送自己是簇首的消息，通過該消息廣播告知本簇內的成員節點自己成為簇首;接著簇內的剩余節點將會接受到來自簇首的消息，不過簇內節點可能會在一定間隔內收到多個這種消息，應為鄰簇間存在干擾，在這種情況下節點根據接收消息的強度來選擇簇首，然后再決定加入哪個簇。

每個節點加入相應的簇的同時，同樣采用非持續CSMA協議向相應的簇首發送入簇消息，包括自身的ID號。當簇首接收所有簇內節點發來的該消息時，根據成員節點的數目，采用TDMA方式為每個簇成員分配發送數據的時隙。每個節點只在屬于自己的時間內發送數據，在其他時間處于休眠狀態，這樣做也是為了減少節點的總能耗。

③數據傳輸階段，采用多跳和單跳相結合的方式。在簇內采用單跳方式傳輸，在簇首與基站之間則分情況決定采用哪種傳輸方式。利用參數記錄簇頭節點的鄰簇頭節點的數目和剩余能量，若距離基站較近時就要避免多跳的路由機制，以減少路由的開銷。當傳輸距離較大時，通過記錄的鄰簇頭數目、跳數以及鄰簇首的剩余能量選擇最佳的一個下一跳節點，采用多跳傳輸機制，減少網絡中簇頭節點能耗，同時由于考慮了跳數因素，盡量減少簇首到基站的跳數，以節約中間節點的能耗。

3 仿真與分析

3.1 仿真環境

本文仿真工具采用網絡仿真工具 NS2［10，11］進行仿真。NS2是一種可擴展的、容易配置的和可編程的時間驅動網絡仿真工具，是由美國加州的LNBL網絡研究組于1989年開始研究開發的軟件。NS2源代碼全部公開，提供開放的網絡接口。本文的仿真環境:節點為100個并且隨機分布在100 m×100 m的監測區域內，Sink節點的位置(50，100)，消息長度為500 byte，信息包的長度為25 byte，每一輪的時間為20 s，即節點每隔20 s的時間更換一次簇首，時間片的大小為0.023 s，每個節點的初始能量相同并且為2 J，網絡帶寬為2 M/s。

3.2 性能分析

通過對整個網絡總的能耗以及網絡中存活節點數目在LEACH和LEACH-NEW不同算法之下兩個指標的對比，由圖1可以看出在相同時間內，LEACH-NEW算法的能量消耗少，提高了網絡的能量利用率，有效地延長了網絡的生命周期。

圖1 網絡中的總的耗能情況比較

由圖2可以明顯地看出改進算法有效地延長了網絡的生命周期，LEACH算法在150 s已經開始出現節點死亡，而LEACH-NEW算法在350 s才開始出現第一個節點的死亡，本文算法減少了簇頭節點在建立簇時能量的消耗，同時數據傳輸階段的單跳和多跳相結合也是減少了網絡中節點的總的能耗。

圖2 網絡中存活節點數目

4 結束語

無線傳感器網絡的路由算法一直都是研究的熱點，在對傳統的LEACH算法深入研究的基礎上，指出存在的不足，提出改進的算法，并利用NS2仿真工具進行了仿真實驗。實驗結果表明改進算法減少了網絡的總能耗，有效地延長了整個網絡的生存時間。

［1］ AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，etal.Wireless Sensor Networks:A Survey［J］.Computer Networks，2002，38(4):393-422.

［2］ 孫建民.無線傳感器網絡［M］.北京:清華大學出版社，2006.

［3］ KHAMFOROOSH K，KHAMFOROUSH H.A New Rounting Algorithm for Energy Reduction in Wireless Sensor Networks［J］.IEEE，2009:505-509.

［4］ 馬祖長，孫怡寧，梅濤.無線傳感器網絡綜述［J］.通信學報，2004，25(4):114-124.

［5］ 陳志奎，倪晶晶，姜國海，等.WSN中一種基于剩余能量級別的負載均衡路由協議［J］.微電子學與計算機，2010，27(12):82-86.

［6］ ZHANG Z，ZHANG X.Research of Improved Clustering Routing Algorithm Based on Load Balance in Wireless Sensor Networks［C］∥IET International Communication Conference on Wireless Mobile and Computing，2009:661-664.

［7］ HEINZELMANW R，CHANDRAKASANA，BALAKRISHNAN H.Energy Efficient Communication Protocol for Wireless Microsensor Networks ［C］∥ Proc.of HICSS＇00.Los Alamitos，CA，USA:IEEE Press，2000:3005-3014.

［8］ 沈波，張世永，鐘亦平.無線傳感網絡分簇路由協議［J］.軟件學報，2006，17(7):1588-1600.

［9］ 王磊，施榮華.無線傳感器網絡路由算法的仿真研究［J］.計算機仿真，2010，28(3):170-174.

［10］ UCB/LBNL/VINT Network Simulator-ns(Version 2)，http://www.isi.edu/nsnam/ns/，2011.

［11］徐雷鳴，龐博，趙耀.NS與網絡模擬［M］.北京:人民郵電出版社，2008.