一種能量均衡的WSN分簇算法

王亭 王瑩瑩 陳曉磊

【摘要】 針對WSN能耗進行研究，在簇頭選擇過程中利用節點的能量、鄰節點數以及簇頭數等參數設置節點當選簇頭的優先度；在簇的組建過程中利用能量參數設置簇的重建條件，達到減小簇的重建頻率的目的，有效地防止網絡中熱點問題的出現。

【關鍵字】 WSN LEACH 分簇機制

一、引言

在WSN的研究中，良好的分簇機制能有效實現路徑的選擇及資源管理，減少節點維護拓撲和廣播數據的能耗 [1]。目前針對LEACH的研究正在深入。

Kim等人提出使用代理簇頭，當數據傳輸的能耗大于閾值時，則采用代理簇頭進行數據傳輸，保證數據傳輸過程的準確性，其中，代理簇頭為距離簇頭最近的且能量最高的節點[2]。

Ma Chaw Mon Thein等人提出利用節點的當前能量與初始能量以及簇頭的個數影響閾值，保證簇頭有足夠的能量完成網絡的運行（簡稱為“Kopt算法”）[3]。目前關于LEACH算法的改進已經取得顯著的成就，但在網絡能量的均衡分布以及能量利用率方面有待提高。

二、算法的改進

針對目前分簇算法存在的問題，改進算法利用節點的能量、鄰節點數、網絡中簇頭的個數以及節點間的距離等，針對簇頭的選擇提出改進方案，達到延長網絡壽命的目的。

2.1 簇頭選擇

利用節點的當前能量、初始能量以及每一輪簇頭個數影響，選出候選簇頭，然后計算每個節點的鄰節點數，及節點的鄰節點數的平均值，在時，將此節點選為簇頭。其中閾值計算方法如下所示：

2.2 簇的重建

網絡以輪的方式運行，每輪開始前，對當前簇內的能量以及簇頭能量進行比較，當簇內節點總能量滿足所需值，且SCH.E≥Eth則說明簇內的節點能夠保證下一輪的網絡運行，則網絡直接進入網絡的數據傳輸階段。反之則進入簇頭的重新選擇以及簇的重建階段。其中，第r輪節點的能量閾值Eth的計算公式如下：

2.3 算法分析

在LEACH算法的基礎上，采用新型的簇頭選擇機制保證節點能量負載的均衡化，同時通過對簇的重建條件的設置降低了網絡的拓撲的變化頻率，使網絡能量得到有效利用。該算法的優點主要有：

（1）降低簇的重建次數；通過對網絡能量閾值的設置，在簇節點以及簇頭的能量不能保證網絡下一輪運行時重新構造簇，降低網絡的重建頻率，減少構造簇消耗的能量，有效的延長網絡的壽命。

（2）簇頭的選擇不完全是隨機的；在保證節點有相同的機會當選簇頭的前提下，根據每輪節點的剩余能量、鄰節點數等參數設置其當選簇頭的優先度；以使簇頭均勻的分布在網絡中，避免剩余能量低的節點作為簇頭，有效的防止網絡空洞的出現。

三、仿真實驗

本文對改進算法和LEACH、Kopt算法進行了仿真和性能比較。實驗顯示，LEACH、Kopt算法、改進算法的第一個節點死亡（FND）分別為133、205、194，一半節點死亡（HND）為402、511、1077、全部死亡（LND）為1087、1294、大于1500。由此可見，三種算法FND時間差不多，改進算法可以顯著地延長網絡HND、LND的死亡時間，即隨著網絡運行時間的增加，使用改進算法的網絡與使用LEACH、Kopt算法的網絡相比，不僅可以使簇頭均勻的分布在網絡中，使能量消耗均勻的分布在各節點上，達到平衡網絡負載的目的，使網絡的能量得到均衡的利用，而且有效地提高能量利用率，顯著的延長網絡壽命。

四、結束語

本文針對LEACH算法進行改進，針對簇頭選擇提出改進方案，使網絡中簇頭的分布更加均勻，有效地降低了網絡拓撲的重建頻率，網絡的能量利用率更加高效。

參 考 文 獻

[1] Kumarawadu P et al. Algorithms for Node Clustering in Wireless Sensor Networks： A Survey [C].Information and Automation for Sustainability， 2008： 295 – 300.

[2] K.T. Kim， et al. An Energy Efficient Routing Protocol in Wireless Sensor Networks”. International Conference on Computational Science and Engineering， pp.132-139， 2009.

[3]Ma Chaw Mon Thein.et al An Energy Efficient Cluster-Head Selection for Wireless Sensor Networks [C].Intelligent Systems， Modelling and Simulation， 2010： 287 - 291.