基于能耗均衡的LEACH改進方法

張 帥 楊清海 馮友兵

1(西安電子科技大學通信工程學院綜合業務網理論及關鍵技術國家重點實驗室 陜西 西安 710071)2(江蘇科技大學電子信息學院 江蘇 鎮江 212003)

0 引 言

無線傳感器網絡(WSN)作為一種新興的信息采集技術，具有自組織、部署快捷、高容錯性和強隱蔽性等技術優勢， 目前已廣泛應用于工農業、國家安全、城市監控、空間探索等許多重要的領域[1-4]。而其自組織性使得拓撲控制成為WSN生命期最大化的關鍵技術[5-7]。

LEACH[8]是最早提出的高效能分簇算法，其以簇為單元向基站傳送數據，在執行過程中不斷循環進行簇的重構過程，重構過程可以分兩個階段：簇的建立階段和傳輸數據的穩定階段。為節省算法開銷，穩定傳輸階段的持續時間要大于建立階段的持續時間。簇的建立過程可詳細分成4個階段：簇頭的選擇、簇頭的廣播、簇頭的建立和調度機制的生成；穩定傳輸階段中，普通節點將采集的數據傳送到簇頭，簇頭對簇中所有節點的數據進行信息融合后再傳送給匯聚節點。LEACH很好地解決了傳感器節點能耗過大的問題，有效降低了節點能耗。

但LEACH算法存在以下不足：在選擇簇頭時根據節點隨機產生一個0～1之間的隨機數選取簇頭，而沒有考慮節點當前的剩余能量，有可能將低能量節點誤選為簇頭而加快該節點死亡的速度；同時，簇的數量具有很大的隨機性，而過多的簇也會減少分簇的帶來的能耗有效性。因此，如何改進LEACH算法的簇頭選擇機制、優化簇頭的數目成為延長網絡正常生命周期的關鍵。

1 相關工作

針對傳統LEACH算法在簇頭選擇機制和簇頭數目隨機等方面存在的問題，國內外學者作了很多提高其性能的改進。其中，文獻[9]提出LEACH-C算法，節點在每一輪開始時先把位置和能量等狀態信息發至基站，基站接收到節點狀態信息后，先計算網絡的能量均值，只有剩余能量大于該值的才可參與簇頭的選擇，然后基站利用模擬退火算法[10]進行統一分簇，并選出簇頭，最后基站廣播包含分簇及簇頭的信息給各個節點完成入簇過程。該方法實際上是對LEACH算法中參加簇頭選擇的節點作了一些限制條件，但這種限制極其有限，特別是在節點的平均剩余能量較低時，即使滿足LEACH-C算法的條件，也有較大可能出現簇頭過早死亡的情況。文獻[11]提出一種基于LEACH的簇頭成鏈可靠拓撲控制算法，該算法規定簇頭數目為5個，利用PEGASIS算法使簇頭成鏈,并選擇剩余能量最多的簇頭傳送信息給基站。選擇簇頭時考慮節點的剩余能量，給節點設置一個能量閾值，小于該值則不能當選為簇頭。此方法雖提高了網絡的健壯性，但卻增加了延遲，網絡總能量消耗過快。文獻[12]提出基于節點剩余能量的分時分簇LEACH改進算法，其通過分時分簇方式，有效克服了傳統LEACH算法中簇頭數目不穩定的缺陷，且不會額外增加網絡的能耗，使得簇頭在整個網絡中的分布以及網絡的能量消耗較為均衡。文獻[13]提出基于簇頭間距均勻部署的LEACH改進算法，該算法在簇頭選擇過程中限定簇頭間的最小距離，使得選出的簇規模近似均衡，以降低簇內通信能量消耗，為避免網絡中各個節點的能量失衡，基于節點剩余能量設定新的簇頭選擇閾值改進算法，增加剩余能量高的節點成為簇頭的概率。通過比較分析，本文算法在選取簇頭時考慮節點剩余能量因素，同時采用均衡化的思想，包括與網絡能耗相關的最優簇頭數目和考慮節點剩余能量的簇頭選擇閾值，以降低網絡節點整體能耗、延長網絡生命周期。

2 網絡部署

將N個WSN節點隨機分布在M×M的監測區域內，構成WSN，其結構如圖1所示。為便于分析，全文作如下假設：

(1) 假設監測區域無障礙物；

(2) 基站的能量充足，且固定位于區域中心位置；

(3) 節點保持靜止且為同構節點且自身能量已知；

(4) 節點間采用單跳通信。

圖1 無線傳感器網絡部署示意圖

3 能耗均衡拓撲控制算法

3.1 通信能耗模型

本文算法無論是匯聚節點(基站)收集網絡節點的剩余能量，還是匯聚節點與簇頭節點、簇頭節點與簇內成員節點之間的通信能耗均采用一階無線電能耗模型。WSN中匯聚中心(基站)和簇頭根據不同的情況使用多徑衰減模型和自由空間模型計算發送端和接收端之間在交換信息時的能量消耗[14]。設發送和接收1比特數據的能耗為Eelec，d為發送節點和接收節點之間的距離，則發送l比特的數據包的能耗為:

ETx(l,d)=lEelec+lεfsd2d

(1)

ETx(l,d)=lEelec+lεampd4d≥d0

(2)

接收l比特的數據包的能耗為：

ERx(l)=lEelec

(3)

式中：l為傳送數據的長度；d為發送節點和接收節點之間的距離；d0為自由空間模型和多徑衰減模型轉折的閾值，一般在80米左右;εfs為自由空間模型參數;εamp為多徑衰落空間模型參數;Eelec為發送和接收單位比特數據的能耗。

3.2 最優簇頭數目

令簇頭的數量為k，利用能量消耗模型可以推出最優簇頭數目Kopt。

(4)

式中：l為傳送數據的長度，單位為bit;dtoBS為簇頭和基站的距離，如圖1所示。

簇內成員節點的主要任務是將采集感知的信息傳送到對應的簇頭，本文設置成員節點距離簇頭比較近即簇內傳輸距離較小，故在簇內采用自由空間能耗模型。因此，成員節點的能量消耗為：

(5)

式中：dtoCH為普通節點與簇頭之間的距離，如圖1所示。

?r2ρ(r,θ)drdθ

(6)

(7)

(8)

每個簇的能量消耗為:

(9)

故能量總消耗為:

Etotal=kEcluster=

(10)

最后，對Etotal求導k，從而計算出WSN最優簇頭數目為：

(11)

式中：N為總節點數；εamp為多徑衰落模型系數;εfs為自由空間模型系數;M為布置區域邊長;dtoBS是簇頭與基站之間的距離。

3.3 基于能量的簇頭選擇閾值

由于簇的規模和簇頭選擇對WSN總能耗影響較大：一方面，當簇的規模較小時，易導致WSN能量消耗不合理；另一方面，當簇的規模較大時，簇頭轉發數據量太大、負擔較重，易造成能耗增大，使普通成員節點在單位之間可發送的數據量急速降低。故本文提出的簇頭選擇機制的改進方法為：

(12)

3.4 算法描述

基于能耗均衡的LEACH改進算法在執行時循環進行簇的重構，仍然和傳統LEACH一樣按輪(round)進行，每輪依然分成簇的建立階段和傳輸數據的穩定階段。該算法的目標是在每一輪中產生可以實現整個WSN更低能耗的最優數目的簇頭，同時，在簇頭的選舉時充分考慮節點的剩余能量引入簇頭選擇新閾值，從而使能量消耗更加均衡。

簇的建立可詳細分成4個階段：選擇簇頭、簇頭廣播信息、普通節點入簇和生成調度機制。首先，為了使得WSN能耗更加均衡，本文改進算法中由匯聚中心或者基站集中調度產生最優簇頭數目Kopt。然后在已經確定最優數目簇頭的基礎上，通過一種分布式的方法來形成簇，其間節點不受任何中心節點調控而自主決定是否成為簇頭。進行選舉簇頭的過程中，每個節點都要產生一個基于自身剩余能量的簇頭選擇新閾值T′(n)以及一個0～1之間的隨機數，當隨機數小于T′(n)，并且考慮該節點在最近的1/P輪中未當選為簇頭，則當選為簇頭，并發布自己是簇頭的公告消息，這樣做的目的是具有多能量的節點比能量少的節點更加容易被選舉為簇頭。簇頭被選舉之后利用非持續性CSMA MAC協議廣播簇頭消息(ADV)，其余節點根據自己所收到的廣播信號的強弱來判斷其歸屬于哪個簇，然后簇頭建立一個TDMA調度為成員節點分配交換的時隙，從而保證數據消息之間沒有沖突，并且使非簇頭節點的無線電模塊在非傳輸時間內關閉，節省了能量。在穩定傳輸數據的階段，WSN普通節點將采集的數據信息發給簇頭，簇頭進行數據信息融合后發給匯聚節點。具體步驟：

(1) 在M×M監測區域中隨機部署N個傳感器節點，并在監測區域中心部署匯聚節點或者基站，其結構示意圖如圖1所示。

(2) 無線傳感器節點向整個網絡廣播自身信息。

(3) 根據式(11)確定最優簇頭數目。

(4) 根據最優簇頭數目Kopt和WSN中已經成為簇頭的次數來確定簇頭。具體的選擇方法是：每個WSN節點產生一個0～1之間的隨機數，與將隨機數與式(12)所示的閾值進行比較，若小于閾值，則當選為簇頭。

(5) 簇頭確定之后向全網廣播簇頭消息，其余節點接收消息，并向距離最近的簇頭發送加入消息，完成簇的建立。

(6) 簇頭采用TDMA為成員分配交換數據的時隙。

(7) 數據穩定傳輸階段，成員節點將采集信息發給簇頭，簇頭將信息融合后再發給基站。

(8) 進入下一輪，重復步驟(3)-步聚(7)。

4 仿真與結果分析

4.1 仿真參數

設在100 m×100 m的區域中隨機部署N個傳感器節點，其中匯聚節點/基站位于區域中心(50，50)。其他仿真參數的設置參考文獻[14]。

表1 仿真參數

4.2 仿真結果分析

為分析節點消耗的能量是否均衡，對網絡已出現節點死亡后的各輪次死亡節點數量進行對比分析。仿真發現兩種算法在100輪時均已經出現了死亡節點，圖2給出了本文改進算法和傳統LEACH算法在第100輪時，死亡節點和工作節點的分布情況，很顯然本文改進算法死亡節點數量遠遠少于傳統LEACH算法。

(a) 傳統LEACH算法

(b) 本文算法圖2 第100輪時死亡節點分布情況

圖3為100個節點在同一隨機分布下，使用本文算法和傳統算法的死亡節點數量的變化趨勢，可以看出，傳統LEACH算法大概在65輪左右出現第一個死亡節點，隨后死亡節點的數量急劇上升，且節點大面積死亡。而本文改進算法第一個死亡節點出現在約70輪，且隨著工作輪數的增加，死亡節點的數量呈平緩上升趨勢，說明使用本文改進算法延遲了第一個節點時間，且節點能耗更加均衡。

圖3 死亡節點數量變化趨勢

為了避免單次仿真的偶然性，圖4給出兩種算法在多次仿真以及同一隨機分布情況下第一個節點死亡的輪數，可以看出，本文改進算法第一個節點死亡時間始終晚于傳統算法，說明整個網絡的能耗更加均衡，有效延長了網絡的生命周期。

圖4 N=100，第一個節點死亡的輪數(first_dead)

5 結 語

本文在選取簇頭時考慮節點剩余能量因素，同時采用均衡化的思想來選取簇頭，即從最優簇頭數目和基于能量的簇頭選擇閾值兩個方面入手，對LEACH算法進行了改進。仿真實驗結果表明，本文算法與傳統LEACH算法相比，降低了WSN節點的整體能耗，延長了網絡使用壽命。