無線傳感器網絡LEACH路由協議的改進

摘要:針對LEACH協議的不足，提出了一種基于k均值聚類的多跳分簇路由算法LEACH-KMCM。經過MATLAB仿真平臺的測試，與LEACH協議相比，LEACH-KMCM使得整個網絡的生命周期延長，具有較好的能量優化特性。

關鍵詞:WSN;路由協議;簇頭;LEACH

中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2009)14-3668-03

Wireless Sensor Network Routing Protocol LEACH Improvement

MA Ge

(School of Information Engineering，Zhengzhou University，Zhengzhou 450044，China)

Abstract: LEACH routing protocol for the lack of a k-means clustering based on the multi-hop routing algorithm clustering LEACH-KMCM.MATLAB simulation platform， after the test， compared with the LEACH routing protocol， LEACH-KMCM the entire network to extend the life cycle， has good properties of energy optimization.

Key words: wireless sensor network; routing protocol; cluster head; LEACH

1 研究背景

無線傳感器網絡(wireless sensor Network，WSN)是由部署在檢測區域內大量廉價的微型傳感器節點通過無線通信的方式形成的一個多跳的自組織的網絡系統。[1]近年來，隨著傳感器技術、微電子技術的進步，WSN得到了快速發展.它已經成為計算機科學技術的一個新的研究領域，主要應用在國防軍事、救災、環境監測等領域，被認為是21世紀最重要的技術之一。

目前，路由協議的研究已成為WSN研究的熱點之一。與傳統網絡不同，WSN的路由協議有其自身的特點和設計要求。因此，傳統的路由協議并不適用于WSN，必須研究新的能夠有效節省和平衡節點能量消耗、延長網絡生命周期的路由協議。LEACH協議是針對WSN提出的第一個分層路由協議，其后的分層路由協議大多是在它的基礎上發展而來的，但是LEACH協議也存在著不足，具有可行的改進。因此，該文選擇LEACH協議作為研究的對象具有良好的典型性。

2 LEACH路由協議的分析

LEACH(Low-Energy Adaptive Clustering Hierarchy)是由MIT的Heinzelman等人為WSN設計的低功耗自適應分層路由算法。[2]LEACH協議中定義了“輪”(round)的概念，每一輪分為簇的建立階段和穩定階段。

2.1 簇的建立階段

在簇的建立階段，相鄰節點動態地形成簇，隨機產生簇頭節點，可分成以下四個階段:

1) 簇頭節點的選舉

節點產生一個0～1之間的隨機數，如果產生的隨機數小于閥值T(n)，則該節點就擔任本輪周期的簇頭。閥值T(n)可以表示為:

(1)

其中，P是簇頭在所有節點中所占的百分比，γ是選舉輪數，γ mod(1/P)代表這一輪循環中當選過簇頭的節點個數，G是這一輪循環中未當選過簇頭的節點集合。

2) 簇頭節點的廣播

節點當選簇頭節點以后，通過廣播向網絡中其他節點發布信息告知自己是本輪的新簇頭。在整個廣播的過程中，簇頭節點使用CSMA MAC層協議，運用相同的發射功率發布信息，非簇頭節點的接收器始終處于工作狀態，用于接收來自簇頭節點的廣播消息。

3) 簇的建立

每個非簇頭節點根據接收到的簇頭節點信息的信號強度選擇加入哪個簇，并告知該相應的簇頭節點，完成簇的建立。

4) 時隙表的創建

當簇頭節點根據簇內節點的數量，將創建一個TDMA時隙表并通知每個非簇頭節點何時開始傳輸數據。

2.2 穩定階段

在初始狀態下，簇頭節點一直保持監聽狀態，簇內節點處于休眠狀態。當分配的時隙來到時，簇內節點會自動喚醒并把數據發送給自己的簇頭節點。在其它時隙，簇內節點將處于休眠狀態.經過一段時間的數據傳輸，簇頭節點收集簇內所有節點發送的數據后，運行數據融合算法將結果直接發送給匯聚節點。

穩定階段持續一段時間后，網絡重新進入簇的建立階段，進行下一回合的簇的重構，不斷循環。

3 LEACH路由協議的改進

針對LEACH協議的以下不足之處，本文提出了一種LEACH的改進算法——基于k均值聚類的多跳分簇路由算法，簡稱為LEACH-KMCM。

3.1 問題的提出

1) 最優簇頭個數的選取

LEACH協議的簇頭節點的產生是完全隨機的，不能保證每一輪都能得到固定個數的最優的簇，影響了LEACH協議的性能。

2) 簇頭節點分布

簇頭選舉沒有考慮節點的具體地理位置，產生的簇頭節點可能比較集中或者分布在網絡的邊緣.簇頭節點分布不均勻，簇內通信能耗不平衡，不利于全網負載的均衡，從而嚴重影響網絡的生存周期。

3) 簇頭節點的選擇依據

簇頭節點比非簇頭節點所消耗的能量多。如果簇頭節點是固定不變的，那么能量較低的節點一旦選作簇頭節點，在傳輸過程中很容易耗盡能量而失效。簇頭節點一旦失效，整個簇將無法通信，所有屬于這個簇的非簇頭節點也將失去和匯聚節點通信的能力。

4) 簇頭節點的廣播

簇頭節點選定后，成為簇頭的節點將在整個網絡范圍內向所有節點廣播消息。在網絡覆蓋區域很大的情況下，簇頭節點需要將廣播消息發送到相當遠的區域，這個過程將消耗簇頭節點相當多的能量。另外，網絡中的所有非簇頭節點都要參與簇的建立，增加了成簇的復雜性。

5) 簇間通信

在LEACH協議中，由于匯聚節點與傳感區域相距較遠，節點與匯聚節點的通信將是高能耗的。由于LEACH采用單跳通信的方式，簇頭節點直接與匯聚節點通信，與匯聚節點通信的節點數目仍然較多，從而加大了能量消耗。

3.2 能量模型

把N個傳感器節點隨機均勻地部署在一個M×M矩形傳感區域內，采用與LEACH協議相同的第一順序無線電模型，如圖2所示。假設WSN具有如下性質:

1) 匯聚節點是唯一的。

2) 傳感器網絡中所有節點都是同構的，并且節點能量有限，具有相同的初始能量。

3) 傳感器節點部署后不再移動。

4) 各個傳感器節點具備GPS功能。

5) 無線發射功率可控。

6) 每輪中節點的能量消耗不統一。

3.3 算法描述

LEACH-KMCM算法也按輪(round)進行，每輪分為兩個階段:簇的建立階段和穩定階段。同樣，為了減少簇的建立階段帶來的額外能耗，穩定階段的時間遠遠長于建立階段的時間。

3.3.1 簇的建立階段

首輪，LEACH-KMCM算法采用k均值聚類算法，根據指定的最優簇頭個數k，將整個網絡劃分成k個簇，每個節點屬于其中一個簇。在每個簇中，簇頭節點僅接收本簇內的節點發來的數據，不接收其他簇的節點數據。在整個網絡生存周期內，各個節點的NODEID，節點所在的簇CHID一旦確定，將不再改變，直至節點失效。

LEACH-KMCM算法的最優簇頭數為:

(2)

其中，N是網絡中節點個數，dtoBS是簇頭到匯聚節點的距離，εmp為多徑衰減信道模型放大指數，εfs是自由空間信道模型放大指數。

如果節點到基站的距離75m≤dtoBS≤185m，代入式(2)，則最優簇頭個數1

k均值聚類算法以 為參數，把N個對象分為k個簇，以歐式距離作為相似性測度，求對應某一初始簇中心向量最優分類，使簇內具有較高的相似度，而簇間的相似度較低。[4]

從第二輪開始，在各個簇，要盡可能選擇離匯聚節點較近、剩余能量值Ecur大的節點擔任簇頭。普通節點向前一輪的簇頭節點報告自身的能量值Ecur。前一輪的簇頭節點依據接收到的各節點的Ecur值來決定新一輪的簇頭節點。

3.3.2 傳輸階段

①簇內數據傳輸

和LEACH協議一樣，在每個簇中非簇頭節點和簇頭節點采用單跳方式直接通信。

②簇間數據傳輸

簇形成后，簇頭節點將向相鄰簇的簇頭節點廣播自己的狀態信息，信息包括節點的NODEID，節點所在的簇CHID及其權值。簇頭節點與匯聚節點之間采用基于權值的路由樹算法實現多跳通信。在整個網絡中距離匯聚節點較近且能量足夠的簇頭節點將優先成為路由樹的根節點。簇頭節點沿著路徑將收集到的數據進行融合并傳送給父節點，逐級傳送到根節點，直至到達匯聚節點。

4 仿真實驗

4.1 仿真模型和參數設置

仿真實驗平臺采用MATLAB，假設模擬場景為100個傳感器節點隨機分布在100×100的正方形區域，匯聚節點位于(50，175)處.仿真模型的參數與Heinzelman分析LEACH協議設置的參數一樣。

圖3 LEACH協議圖4 LEACH-KMCM算法

圖3和圖4的實驗結果顯示:隨機產生100個節點，LEACH-KMCM算法比LEACH協議簇的分布更均勻，簇頭節點在簇內產生，均衡了網絡負載.

4.2 仿真結果性能比較

1) 網絡生命周期(如圖5)

2) 網絡能量消耗(如圖6)

圖5 網絡剩余節點數與輪數變化關系圖6 網絡能量消耗與輪數變化關系

圖5和圖6的實驗結果顯示:LEACH-KMCM算法有效平衡了簇頭的能量消耗，整個網絡的能耗減少，將能量的損耗均勻分布到了所有節點中，避免了單個節點過早死亡，提高了網絡的生命周期。

5結束語

LEACH-KMCM算法，兼顧簇頭節點的合理分布以及數量優化，首輪采用k均值聚類算法將網絡劃分為固定的k個簇，從第二輪開始，以節點剩余能量的多少為主要依據來選取簇頭，在傳輸階段，簇內采用單跳方式直接通信，簇間建立路由樹以多跳方式通信。仿真結果顯示與LEACH協議相比，LEACH-KMCM使得整個網絡的生命周期延長，具有較好的能量優化特性。

參考文獻:

[1] 孫利民，李建中，陳渝，朱紅松.無線傳感器網絡[M].北京:清華大學出版社，2005.

[2] 于海斌，曾鵬，梁韡.智能無線傳感器網絡系統[M].北京:科學出版社，2006.

[3] Heinzelman W R， Chandrakasan A， Balakrishnan H. An application-specific Protocol architecture for wireless microsensor networks. IEEE Transactions on WirelessConununieations.2002，l(4):60-670.

[4] 安淑芝.數據倉庫與數據挖掘[M].北京:清華大學出版社，2005.