無線傳感器網(wǎng)絡LEACH路由協(xié)議的改進

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

關鍵詞:WSN;路由協(xié)議;簇頭;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 研究背景

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

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

2 LEACH路由協(xié)議的分析

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

2.1 簇的建立階段

在簇的建立階段，相鄰節(jié)點動態(tài)地形成簇，隨機產(chǎn)生簇頭節(jié)點，可分成以下四個階段:

1) 簇頭節(jié)點的選舉

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

(1)

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

2) 簇頭節(jié)點的廣播

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

3) 簇的建立

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

4) 時隙表的創(chuàng)建

當簇頭節(jié)點根據(jù)簇內節(jié)點的數(shù)量，將創(chuàng)建一個TDMA時隙表并通知每個非簇頭節(jié)點何時開始傳輸數(shù)據(jù)。

2.2 穩(wěn)定階段

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

穩(wěn)定階段持續(xù)一段時間后，網(wǎng)絡重新進入簇的建立階段，進行下一回合的簇的重構，不斷循環(huán)。

3 LEACH路由協(xié)議的改進

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

3.1 問題的提出

1) 最優(yōu)簇頭個數(shù)的選取

LEACH協(xié)議的簇頭節(jié)點的產(chǎn)生是完全隨機的，不能保證每一輪都能得到固定個數(shù)的最優(yōu)的簇，影響了LEACH協(xié)議的性能。

2) 簇頭節(jié)點分布

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

3) 簇頭節(jié)點的選擇依據(jù)

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

4) 簇頭節(jié)點的廣播

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

5) 簇間通信

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

3.2 能量模型

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

1) 匯聚節(jié)點是唯一的。

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

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

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

5) 無線發(fā)射功率可控。

6) 每輪中節(jié)點的能量消耗不統(tǒng)一。

3.3 算法描述

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

3.3.1 簇的建立階段

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

LEACH-KMCM算法的最優(yōu)簇頭數(shù)為:

(2)

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

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

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

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

3.3.2 傳輸階段

①簇內數(shù)據(jù)傳輸

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

②簇間數(shù)據(jù)傳輸

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

4 仿真實驗

4.1 仿真模型和參數(shù)設置

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

圖3 LEACH協(xié)議圖4 LEACH-KMCM算法

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

4.2 仿真結果性能比較

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

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

圖5 網(wǎng)絡剩余節(jié)點數(shù)與輪數(shù)變化關系圖6 網(wǎng)絡能量消耗與輪數(shù)變化關系

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

5結束語

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

參考文獻:

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

[2] 于海斌，曾鵬，梁韡.智能無線傳感器網(wǎng)絡系統(tǒng)[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] 安淑芝.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘[M].北京:清華大學出版社，2005.