LEACH算法的改進分簇模型在無線傳感器網絡中的研究

牛瀟，王忠慶

（中北大學，山西省 太原 030051）

0 引言

傳感器網絡具有異于MANET的獨特性質，而傳統MANET協議不適用于傳感器網絡，需要為傳感器網絡研究新的有效的路由算法。目前，在傳感器網絡的路由算法研究中，鑒于傳感器網絡中節點稠密分布、節點的能量、存儲及數據處理能力十分有限的特性，一般采用基于分簇的方法來進行路由算法設計，以提高路由算法的性能。分簇算法作為路由協議的研究基礎，對路由算法性能的優劣具有重要的影響。

1 LEACH算法及分析

LEACH算法是一種典型的層次路由算法。LEACH算法分別做了如下假設，主要設基站(BS)遠離傳感器網絡節點并且是穩定的；傳感器網絡中的所有節點是同構的并且能量都受到限制；所有節點可以直接與基站通訊；節點都沒有位置信息；簇頭節點負責數據壓縮匯聚以及與基站進行通訊；該算法主要通過隨機選擇簇首領，平均分擔中繼通信業務來實現節能。同時LEACH定義了“輪”(Round)的概念，針對每個節點n設定了一個閾值T(n)：

式(1)中p表示簇頭節點占網絡節點總數的百分比；r表示重新挑選簇頭節點的輪數；G表示網絡中最近1/p輪未當選簇頭的節點的集合。并根據該閾值從侯選節點中挑選簇頭，具體的步驟：

（1） 若傳感器節點Ni∈G，則對于每個Ni獨立運算(2.1)式，獲得閾值T(n)。

（2） 若Ni不屬于G，則根據(1)式，T(n)為零。

（3） Ni產生一個0~1之間的隨機數RadomNum。

（4） 若T(n)＞RadomNum，則該節點當選為簇頭，并廣播當選消息。

（5） 其余節點選擇加入某簇頭所在的簇，形成穩定的拓撲結構。

（6） 穩定工作階段。

（7） 每隔時間t，進行下一輪簇頭選取，轉Step1，重新選擇簇頭并成簇。

由以上步驟可知LEACH算法中的輪是指兩次簇頭選取之間的時間段，每一輪由初始化和穩定工作兩個階段組成。在初始化階段，隨機選擇節點為簇首領，成為簇首領的節點向周圍廣播信息，其它節點根據接收到廣播信息的強度來選擇它所要加入的簇，并告知相應的簇首領，由于信息的強度和節點之間的距離是成正比的，因此，實際上各非簇頭節點是選擇距離自己地理距離最短的簇頭所在的簇加入，并形成簇拓撲結構，如圖1所示。

圖1 成簇階段圖

無線傳感器網絡首先產生中心節點，其余節點加入距離自己最近的中心節點所在的簇，然后由中心節點直接和Sink節點進行通訊。在穩定工作階段，節點持續采集監測數據，傳送到簇頭，由簇頭對數據進行必要的融合處理之后，發送到終端節點。每輪工作周期結束后，重新選擇簇頭并重復前面的工作。

2 能量有效的分布式簇頭選取算法

目前提出的很多路由算法都沒有考慮傳感器節點的實際分布情況。在上述的LEACH算法描述中，LEACH存在著以下的諸多問題。

(1)由于位于簇邊緣位置的簇頭通訊能耗遠大于位于簇中心位置的簇頭，因此將導致各簇頭能耗不均衡，使某些簇頭節點能量提前耗盡。

(2) LEACH沒有考慮到傳感器網絡在進行部署的時候，節點分布密度對簇頭能耗的影響。由此導致在傳感器節點密集分布區域的簇頭能耗巨大，而在傳感器節點稀疏分布區域的簇頭能耗較小，網絡中各簇頭的能耗極不均衡。

(3) 動態分簇引起網絡拓撲結構頻繁變換和大量廣播通信，從而帶來了額外的能量開銷。

因此上述節點可能在某個局部分布非常的密集，而在其他的一些地方分布又非常稀疏。因此在這種情況下，簡單的采用LEACH算法中的簇頭選取機制，從而導致傳感器網絡生命周期的提前結束。首先提出了密度調節參數數學模型，然后將其與上一章提出的平均能耗調節參數結合起來，進而提出了能量有效的分布式簇頭選取算法。

為了解決上面的問題，首先必須量化傳感器網絡的節點分布密度，為方便描述，做如下的假設：

(1) 傳感器的通信半徑R可以根據需求而改變，R0是基本通信半徑，R≥ R0；

(2) Ni表示傳感器網絡中的第i個節點；

(3) 任意節點Ni坐標為（xNi, yNi）；

根據上面的假設，可知Dist(Ni，Nj)表示傳感器網絡中任意兩點之間的直線距離，但是由于在分布式路由算法中節點的位置信息都無法獲取，因此給出函數f(SignalIntension)，其中SignalIntension表示Ni節點接收到的，由Nj節點發出的信號的強度，這個值可以通過Ni節點的通訊模塊獲得，而f(SignalIntension)則表示接收信號的強度與收發信號的兩節點之間距離的映射關系。對于任意節點Ni，若Dist(Ni，Nj)

根據以上分析提出一種能量有效的分布式簇頭 選 取 算 法(EECHS，Energy Efficient Cluster Heads Selection)，該算法同時引入能量調節參數和密度調節參數，通過能量調節參數可以使得剩余能量越大且每輪平均工作能耗越小的節點有更多機會成為簇頭。通過密度調節參數可以使得分布密度越大區域的節點有更多機會成為簇頭。密度調節參數如下：

N(j)∈NeighborSet(i)。NeighborSet(i)是節點Ni的鄰居節點集合。即Nodedensity(i)的值表示節點Ni的鄰居節點的總數，也就是以N(i)為圓心，R0為半徑的圓形區域的節點的個數。當Nodedensity(i)的值比較大時，意味著該節點所在區域節點分布的密度比較大。故，式(1)可修訂為式(2)：

在式(3)中，Ecur表示節點當前的剩余能量，Eavg表示節點每輪的平均能耗。故，式(1)可修訂為：

其中，rs為節點連續未當選為簇頭的輪數，一旦節點當選簇頭，則rs重置為0。

得出能量調節參數如式(6)：

故LEACH算法的式(5)可以改進為如式(7)所示：

顯然，a=0，b=1時，式(7)將簡化為式(9)：

即只在LEACH算法中進一步考慮剩余能量與工作能耗對網絡生命周期的影響。

而當a=1，b=0時，式(9)將簡化為式(10)：

即只在LEACH算法中進一步考慮節點分布密度對網絡生命周期的影響。在穩定工作階段，節點周期性的采集監測數據，并傳送給簇首，進行必要的數據聚集和融合之后，將處理后的數據發送到Sink節點，這是一種減小通信數據流的有效工作模式。持續一段時間以后，整個網絡進入下一輪工作周期，重新選擇簇首。

LEACH可以在一定的程度上節省能量，與一般的協議相比，簇首的能量消耗非常高，各節點需要等概率地擔任簇首才能使網絡中所有節點比較均衡地消耗能量，有利于延長整個網絡的生命周期，至少延長15%；其特點是分層和數據融合，分層有利于網絡的擴展，數據融合能夠減少通信量。但是它必須在每個簇首都可以和節點直接通信的基礎上進行，因而有一定的局限性。

3 算法仿真實驗

在輸入要進行部署的傳感器節點個數，區域大小，初始能量和調節參數等相關數據后，可以根據這些數據產生指定個數的節點，并且為每個節點隨機分配一個坐標。通過仿真實驗平臺將生成節點分布的模擬圖。因此采用EECHS算法在剛才模擬部署的傳感器節點中選擇簇頭并成簇，實驗平臺將以直觀的方式顯示簇頭選取的結果。最后實驗平臺還將記錄每輪分簇過程中產生的簇頭的坐標，并以列表的方式顯示出來。具體的操作界面如圖2所示。

圖2 獲取初始參數界面圖

圖2為仿真系統中獲取部署節點參數數據的截圖，取得相應的數據后即可對節點進行部署，其中能量調節參數和密度調節參數的取值范圍為0~1之間。

圖3為模擬100個節點部署的截圖，其中每個小圈代表一個傳感器節點。

圖4為節點數為200個時，最后一輪分簇時選取的簇頭截圖，其中比較粗的小圈表示當選為簇頭的節點，較細的圈表示普通節點。可通過選擇左側窗格中的分簇輪數來查看該輪產生的簇頭節點的個數及各簇頭的坐標，同時還可以查看總的分簇輪數，從而與采用LEACH算法時傳感器網絡的生命周期進行比較。

圖3 節點部署模擬圖

圖4 簇頭選取模擬圖

4 實驗結果

在實驗過程中隨機生成若干個點，代表隨機分布的傳感器，假定p=0.1，節點初始能量均為2000。當傳感器節點個數固定為200，而部署區域大小分別取800×800，900×900，1000×1000，1100×1100，1200×1200時，得到的仿真實驗結果如圖5所示。

圖5 部署區域大小變化時EECHS與LEACH算法實驗對比圖

在圖5中，橫坐標為正方形部署區域的邊長，縱坐標為采用LEACH算法或EECHS算法時成簇的輪數(即網絡的生命周期)。由圖5可知，當節點數量不變，隨部署區域面積的擴大，僅考慮節點的分布密度(a=0，b=1)、或僅考慮節點的剩余能量及其工作能耗(a=1，b=0)、或綜合考慮節點的分布密度以及節點的剩余能量及其工作能耗(a=0.5，b=0.5)時，采用EECHS算法，傳感器網絡的生命周期均比采用LEACH算法時更長。特別的，當綜合考慮節點的分布密度、節點的剩余能量及其工作能耗(a=0.5，b=0.5)時，傳感器網絡的生命周期延長了近150%。

若隨機生成100，150，200……個點，而部署區域大小固定為1000×1000時，p=0.1，則仿真實驗結果如圖6所示。

圖6 節點個數變化時EECHS與LEACH算法實驗對比圖

在圖6中，橫坐標為部署的節點個數，縱坐標為采用LEACH算法或EECHS算法時成簇的輪數(即網絡的生命周期)。由圖6知，當部署區域面積一定，隨部署的節點數增加，僅考慮節點的分布密度(a=0，b=1)、或僅考慮節點的剩余能量及其工作能耗(a=1，b=0)、或綜合考慮節點的分布密度以及節點的剩余能量及其工作能耗(a=0.5，b=0.5)時，采用EECHS算法，傳感器網絡的生命周期均比采用LEACH算法時更長。特別地，當綜合考慮節點的分布密度、節點的剩余能量及其工作能耗(a=0.5，b=0.5)時，傳感器網絡的生命周期延長了近100%。

若隨機生成100個點，而部署區域大小固定為1000 1000，p=0.1時，節點的初始能量分別取1000，1500，2000，2500，3000則仿真實驗結果如圖7所示。

在圖7中，橫坐標為節點的初始能量，縱坐標為采用LEACH算法或EECHS算法時成簇的輪數(即網絡的生命周期)。由圖7知，當部署區域面積及節點個數一定，隨節點初始能量的增加，當僅考慮節點的分布密度(a=0，b=1)、或僅考慮節點的剩余能量及其工作能耗(a=1，b=0)、或綜合考慮節點的分布密度以及節點的剩余能量及其工作能耗(a=0.5，b=0.5)時，采用EECHS算法，傳感器網絡的生命周期均比采用LEACH算法時更長。特別地，當綜合考慮節點的分布密度、節點的剩余能量及其工作能耗(a=0.5，b=0.5)時，傳感器網絡的生命周期比采用LEACH算法時延長了近90%。

圖7 初始能量變化時EECHS與LEACH算法實驗對比圖

[1] 史龍,王福豹,段渭軍，等.無線傳感器網絡Range-Free 自身定位機制與算法[J].計算機工程與應用,2004,40（23）：127-130.

[2] B. Krishnamachari, D. Estrin, and S. Wicker. Modelling Data-Centric Routing in Wireless Sensor Networks[J]. In Proceedings of IEEE Infocom, 2002,102-111.

[3] 盧春枝.LU Chunzhi 無線傳感器網絡分簇路由協議分析[J].武漢理工大學學報:信息與管理工程版, 2008,30(1).

[4] 朱彬.廖俊國.羅芽松.使用部署知識的異構傳感器網絡有效成簇算法[J].計算機工程與應用,2009,45(13).

[5] 張新秀.張淼.張振川.無線傳感器網絡分簇路由改進算法及其性能[J].中國科技論文在線,2010,5(2).

[6] M. Chu, H. Haussecker,F. Zhao.Scalable informationdriven sensor querying and routing for ad hoc heterogeneous sensor networks[J].International Journal of High-Performance Computing Applications, 2002,16(3):348-356.

[7] 田艷霞,辛兵,吳克軍.無線傳感器網絡的節能研究[J].兵工自動化，2006,25(3).

[8] 沈 波,張世永,鐘亦平. 無線傳感器網絡分簇路由協議[J]. 軟件學報, 2006,17(7): 1672-1681.