無線傳感器網絡能量均衡分簇路由協議

衛 琪

（中北大學 電子與計算機科學技術學院，山西 太原 030051）

0 引言

無線通信技術和電子技術的發展使得無線傳感器網絡(Wireless Sensor Networks, WSN)方面的研究受到越來越多的重視。WSN可實現數據的采集量化、處理融合和傳輸應用，它是信息技術中的一個新的領域，在人們生產、生活的各個領域都有廣闊的應用前景[1-3]。

WSN的一個基本功能就是將監測區域內發生的事件或感知到的數據傳送到基站供進一步分析使用，WSN路由協議對這項功能的實現起著至關重要的作用[4]。通常情況下，傳感器節點能量有限且無法補充，因此降低能量損耗、延長網絡的生命周期是WSN中設計有效路由算法的核心目標。WSN的路由協議作為一項關鍵技術已成為目前研究熱點。

本文在對LEACH協議研究的基礎上，結合其優點、針對其不足，提出一種基于剩余能量且負載均衡的無線傳感器網絡能量有效分簇路由協議(LEACH-improved)，可以更好地均衡網絡負載，延長網絡生存時間。

1 相關工作

LEACH ( Low-Energy Adaptive Clustering Hierachy)[5]低功耗自適應分簇路由協議，是最早提出的分簇路由算法。它的核心思想是通過周期性的隨機選舉產生簇頭，使網絡能耗平均分配到每個傳感器節點上，進而延長網絡的生存時間。 LEACH協議有許多優點，通過動態分簇，使所有節點平均分擔中繼通信業務[6]；在簇內進行的本地融合技術減少了發往sink的數據量，特別是處理具有高度相關性的數據時，冗余數據被大量消除[7]；作為一種分布式的分簇路由協議，節點既不需要全局的網絡信息[8]，也不需要來自基站的任何控制信息。但是，LEACH在簇頭選擇時僅依靠節點產生隨機數，而未考慮參選節點的能量水平；頻繁的簇重構，且每次網絡的拓撲結構都會較大改變；要求所有簇頭與sink一跳通信，為遠離sink的簇頭帶來很大數據傳輸能耗，同時造成簇頭間能量消耗不均衡。

2 系統模型

2.1 網絡模型

LEACH-improved協議采用如下網絡模型：考慮一個具有N的傳感器節點的傳感器網絡，節點周期性的收集數據，相應的節點集合可表示為S= {s1，s2， …，sn} 。假設網絡和傳感器節點具有以下性質：

（1）N個傳感器節點隨機、均勻地分布在M×M的正方形區域中，節點足夠密集，保證一個節點的有效發射半徑內存在其他節點。節點部署之后不再發生位置變化。

（2）sink節點位于觀測區域外的某一固定位置，且沒有能量和發射功率的限制。

（3）傳感器網絡為同構網絡，即所有傳感器節點初始能量相等，都有計算能力、信號處理能力和數據融合功能，且在網絡中地位平等。每個節點都有唯一的標識（ID）。

（4）節點不知道自身的位置信息。

（5）節點可以感知當前自身的能量。

（6）節點的無線發射功率可控，即節點可以根據接收者的距離遠近來調整其發射功率以節約能量。

（7）各節點間的鏈路對稱。若已知對方發射功率，節點可以根據接收信號的強度RSSI計算發送者到自己的近似距離。

2.2 能量模型

LEACH-improved協議采用LEACH協議使用的無線通信模型。節點發射k bit的數據到距離為d的接收方，消耗的能量由發射電路損耗和功率放大損耗兩部分組成，如公式（1）所示。

其中,Eelec表示發射電路損耗的能量，與編碼、調制、濾波等相關；它與mp分別表示自由空間和多徑衰落信道模型下功率放大器的能量消耗常數。節點在傳輸數據時具體采用哪種信道是由發送節點和接收節點之間的距離d決定的。如果兩者之間的距離小于距離閾值d0，則采用自由空間信道模型；若距離大于d0，則采用多徑衰落信道模型。很明顯，后者消耗的能量比前者大得多。

節點接收k bit數據消耗的能量為：

此外，數據融合也會消耗一定能量，用EDA表示融合單位比特數據所消耗的能量。

3 LEACH-improved協議

LEACH-improved協議的思想是利用分簇和建立簇間多跳路徑，來達到均衡網絡負載、延長網絡壽命的目的。在首輪成簇時，協議借鑒了LEACH的隨機簇頭選舉機制，簡單、快速地將網絡分簇并選出首輪簇頭節點。隨著網絡的運行，進入非首輪成簇階段，協議考慮了每個簇內參選節點的剩余能量，選擇剩余能量較多的節點擔當下一任簇頭，從而避免了能量已經不足的節點擔當簇頭。

簇形成之后，LEACH-improved協議借鑒了泛洪算法的思想，各簇頭通過轉發來自sink的包含跳數信息的廣播包，在簇頭節點間建立和選擇多跳傳輸路徑，使得遠離sink的簇頭不再使用長距離單跳通信方式傳輸數據到sink。

LEACH-improved協議中，簇頭節點承擔著數據采集、數據融合以及數據轉發3項任務，能量消耗比普通節點大。為了平衡節點能量損耗，延長網絡壽命，本協議也以“輪”為單位周期性執行，每輪循環分為簇形成階段、簇間多跳路徑建立和選擇階段以及數據傳輸階段。其中，簇形成階段根據實際情況又可分為首輪簇形成階段和非首輪簇形成階段。

3.1 簇形成階段

3.1.1 首輪簇形成階段

本階段協議借鑒LEACH的簇頭選舉及成簇機制。因為初始狀態下所有節點的能量相同，所以首輪成簇時不需要考慮節點的能量狀況。每個節點產生一個0～1之間的隨機數，與相應的閾值T(n)作比較，若產生的隨機數小于T(n)則此節點當選為首輪簇頭節點(FCH)，未當選的節點處于空閑狀態。T(n)的計算方法如公式（1）所示。

其中，p為期望的簇頭節點在所有傳感器節點中的百分比，r表示當前輪數，n代表某個節點，G為第r輪之前尚未成為簇頭的節點集合。

節點一旦成為首輪簇頭節點，則向全網用CSMA(Carrier-Sense Multiple Access)的MAC協議廣播其當選消息，該廣播消息中包含了自己的ID。非簇頭節點根據收到消息的信號強弱，選擇信號最強的消息發送源節點作為自己的簇頭，并向該簇頭節點發送消息，請求成為該簇成員，消息中包含了自身ID和首輪簇頭ID。首輪簇頭節點收到成員節點的加入請求后，將各成員節點的信息保存在自己的路由表中。當簇頭收到所有加入請求消息后，向各成員節點發送確認加入消息，消息中包含了本簇使用的CDMA編碼、TDMA時隙表以及要求進入休眠狀態的消息。不同的簇內部通信采用不同的CDMA編碼，避免了相互之間的通信干擾。TDMA時隙表告知了成員節點何時可以傳送數據到簇頭。收到休眠狀態消息后，成員節點即由工作狀態轉換到休眠狀態，節省了能量，也利于簇間多跳路徑的建立。

至此，首輪成簇階段結束，網絡運行進入下一階段。

3.1.2 非首輪簇形成階段

如果網絡不是首輪成簇，那么本輪的簇頭節點由上一輪的簇頭指定。以第二輪簇形成過程為例來說明。

在首輪數據傳輸的最后一幀，各簇的成員節點會將自身剩余能量（Eresidual）信息連同采集到的數據一起發送給相應簇頭，由簇頭計算出本簇當前平均剩余能量(Eave)。簇頭將計算結果發送給簇內各成員節點，各節點比較簇內平均剩余能量和自身當前能量的大小，滿足Eresidual >Eave的成員節點均可參與競爭第二輪本簇的簇頭節點，并向當前簇頭發送競選消息。若競選節點不唯一，那么簇頭節點指定距離自己最近的競選節點成為第二輪的簇頭（NCH），這里的距離可以根據收到競選消息的信號強弱來判斷。

第二輪簇頭選定之后，當前簇頭將成員節點包括自身的信息轉交給第二輪簇頭，并向本簇成員廣播簇頭轉變的消息，隨后，當前簇頭狀態轉換為簇成員節點，第二輪簇頭的狀態轉為簇頭節點。新當選的簇頭將選定的CDMA碼、TDMA時隙表和進入休眠要求，以消息的形式廣播給本簇成員。依此類推，以后各輪的簇形成過程均與第二輪相同。

3.2 簇間多跳路徑建立和選擇階段

簇形成之后，sink將自己的跳數置為0，其余簇頭節點將自身跳數置為最大值。然后，sink以發射半徑d0向全網廣播多跳路徑建立消息，消息中包含了sink的跳數信息。收到消息的簇頭節點，將sink節點加入自己的中繼節點集中，同時將自身的跳數置為1，并向外轉發來自sink的廣播消息。利用傳感器節點可以調節自身無線發射功率的特點，調整簇頭的發射能量，使簇頭節點之間的通信距離大于簇內通信的范圍[9]。其他未收到過來自sink的廣播消息的簇頭，在收到相鄰簇頭轉發來的消息后，將發送該消息的簇頭加入到自己的中繼節點集中，同時將收到的跳數值加1，更新為自身跳數信息，然后再進一步轉發sink的廣播消息。若某個簇頭收到多個具有相同跳數值的簇頭轉發來的消息，則將它們都加入到中繼節點集中。若簇頭收到跳數值大于自身跳數值的消息，則丟棄該消息。依此類推，廣播結束后，每個簇頭節點都保存了通往sink的中繼節點集，簇間多跳路徑建立完畢。

簇頭到sink的數據傳輸已經建立了多條通信路徑，接下來在此基礎上為每個簇頭選擇一條通往sink的最優路徑。各簇頭節點在其中繼節點集中，選擇距離自己最近的簇頭作為其下一跳轉發節點。這里的距離可以根據收到廣播消息的信號強度來衡量。若最優轉發節點失效，則可選擇中繼節點集中的其他簇頭節點。

3.3 數據傳輸階段

簇頭為簇內成員節點分配好TDMA時隙，簇間多跳路徑建立并選擇好之后，各簇頭向成員節點發送喚醒消息，使它們轉換到工作狀態，開始采集監測區域的數據，并在TDMA時隙表為其分配的時間槽內直接向簇頭發送數據。簇頭節點收集到所有成員發來的數據后，與自身采集的數據進行融合處理，再沿著已建立好的多跳路徑傳送給sink。

各成員節點在向簇頭發送采集數據時，將自身的剩余能量“捎帶”發送給簇頭，以便簇頭節點計算出下一輪簇頭選舉所需的本簇平均剩余能量。

為了節省資源開銷，數據傳輸階段的持續時間要比前兩個階段長得多。

4 性能分析

(1)LEACH協議單純地依靠隨機方式產生簇頭，缺乏對簇頭節點能量水平的考慮。雖然一個節點在1/p輪內僅有一次當選簇頭的機會，但如果某些剩余能量已經很少的節點被選為簇頭，它們必然會因大量消耗能量而過早失效，那么其所屬簇內節點采集的數據就不能進一步傳送到sink節點，此時網絡的生存周期結束，網絡中遺留大量未被充分利用的能量資源。這種部分節點因為過早耗盡自身能量導致網絡原有覆蓋區域缺失或者數據無法送達sink節點的現象叫作“能量空洞”[10]現象。

由于初始狀態下網絡中所有節點的能量均充足且相等，LEACH-improved協議在首輪采用了LEACH的隨機簇頭選舉方式，簡捷、快速的將網絡分簇。之后每輪的簇頭節點都由本簇內剩余能量大于簇內平均剩余能量的節點競爭產生，有效避免了能量較低的節點當選簇頭，使網絡負載更加均衡，防止了“能量空洞”現象的發生，繼而延長了網絡壽命。

（2）LEACH協議每輪都要重新建簇，且每輪簇重構時，網絡的拓撲結構都會發生較大變化，同時全網所有節點都要參與此過程，由此帶來的控制和通信開銷是很可觀的。

LEACH-improved協議每輪在不改變簇結構的基礎上，重新選擇簇頭節點和成簇。各簇的成員只需參加本簇的簇頭選舉和成簇，不參與網絡中其他簇的重建過程。因此避免了頻繁簇重構帶來的能量開銷。

（3）LEACH協議要求所有簇頭節點均與sink直接通信，sink附近的簇頭向sink傳送數據基本可以采用自由空間信道模型，距離sink較遠的簇頭很可能因采用多徑衰落信道模型傳輸數據消耗大量能量，造成簇頭節點間能耗的不均衡。

LEACH-improved協議通過在簇頭間建立多跳傳輸路徑，使得所有簇頭之間的數據傳輸都可采用自由空間信道模型，從而大大節省了距sink較遠的簇頭節點的通信能耗，同時簇間負載也得到了均衡。

同時，LEACH-improved協議僅通過發送查詢廣播數據包進行尋路過程，并不進行采集數據的傳輸，并且通過調節簇頭發射功率限制了消息的轉發半徑，因而也不存在泛洪算法固有的“內爆”和“重疊”問題。

（4）LEACH-improved的多跳傳輸路徑使得簇頭在向sink轉發數據時，每一跳都可以充分地進行數據融合，從而減少了網絡中的數據傳輸量，降低了節點的通信能耗。

5 仿真實驗和分析

本文在TinyOS操作系統的TOSSIM仿真平臺下對LEACH-improved協議進行仿真實驗，演示新協議的工作過程。通過對比LEACH協議來驗證它的有效性。

在100m×100m的正方形區域內隨機部署100個節點，每個節點的初始能量為2J，其余參數設置為：Eelec=50nJ/b，EDA=5 nJ/b，d0=87，fs=10pj/bit/m2，mp=0.0013pJ/bit/m，數據包的大小是2000b，報頭和廣播包的大小是20b。

本文通過第一個節點的死亡時間（FND）和最后一個節點的死亡時間（LND），來衡量兩種協議下網絡的生命周期。仿真實驗分別采用LEACH協議和LEACH-improved協議進行傳感器網絡的運行，得到了兩種協議下網絡運行輪數隨死亡節點個數的變化關系，如圖1所示。

由圖1可見，LEACH-improved協議下FND比LEACH協議的延遲了近32% ，LND比LEACH協議的延遲了近24%。這是因為LEACH-improved協議在簇頭選擇時考慮了節點的能量狀況，在簇頭節點間通過構造中繼節點集并選擇最佳路徑進行數據發送，使網絡中節點能量能耗更加均衡，網絡壽命得到了延長。

圖1 LEACH-improved與LEACH的網絡生命周期比較圖

5 結論

本文通過對LEACH協議的分析，針對其在簇頭選擇、成簇及數據傳輸方面存在的不足，提出了一種基于能量且負載均衡的路由協議LEACH-improved，用節點剩余能量來約束簇頭的選舉，在簇頭和sink間建立并選擇多跳傳輸路徑，保證距離較遠的簇頭采用多跳方式發送數據到sink。仿真結果表明，與LEACH協議相比，LEACH-improved協議平衡了簇間負載，節約了網絡能量，網絡壽命得到了延長。但LEACH-improved協議仍存在不足之處，比如，沒有考慮到簇頭在網絡中是否均勻分布，各簇的大小是否合理等。這兩點對于網絡生命周期的延長都有很大影響，今后還需做進一步的研究和完善。

[1]楊文國，郭田德，趙彤.基于動態規劃的無線傳感器網絡的路由算法[J].計算機研究與發展，2007,44(5):890-897.

[2]李建中，高宏.無線傳感器網絡的研究進展[J].計算機研究與發展，2008,45(1):1-15.

[3]陳力軍，毛鶯池，陳道蓄，等.平均度約束的無線傳感器網絡拓撲控制[J].計算機學報，2007,30(9):1544-1549.

[4]OK CS, LEE S, MITRA P, et al.Distributed energy balanced routing for wireless sensor networks[J].Computers & Industrial Engineering, 2009, 57(1):125-135.

[5]HEINJZELMAN W，CHANDRAKSAN A，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transcations on Wireless Communications, 2002,1(4):660-670.

[6]劉昕，王全玉，金旭亮.基于能量感知的數據匯聚和路由協議[J].計算機研究與發展，2008，45(1):83-89.

[7]GAUTAM N, LEE WI, PYUN JY.Dynamic clustring and distance aware routing protocol for wireless sensor networks[C]//Proceedings of the 6th ACM symposium on Performance evaluation of wireless ad hoc, sensor,and ubiquitous networks.Tenerife,Canary Islands,Spain:ACM Press, 2009:9-14.

[8]徐建波，李仁發.無線傳感器網絡中一種新型的混合型數據收集協議[J].計算機研究與發展，2008，45(2):254-260.

[9]樂世成，王培康.無線傳感器網絡中的節能路由算法[J].計算機工程，2008，34(7)：113-117.

[10]吳小兵，陳貴海.無線傳感器網絡中節點非均勻分布的能量空洞問題[J].計算機學報，2008,31(2):253-261.