WSN中一種基于EE-CPK-means的簇頭選舉改進算法

汪巖 徐利亞 周夢玲

摘要：無線傳感器網絡被廣泛應用于各個領域，如環境監控、自然災害預警、公共衛生等。網絡中的節點由電池提供能源，節點能量有限。無線傳感器網絡中簇頭的傳統選擇是隨機的，無法控制簇頭節點的位置分布，導致節點能量消耗不均，出現節點過早死亡的問題。EE-CPK-means算法通過各節點與基站之間的距離來決定簇頭節點，能夠使簇頭節點避免出現過于集中或分散的問題，但是低能量節點多次充當簇頭從而過早死亡的問題仍然存在。文章提出了一種基于EE-CPK-means算法的簇頭選舉改進算法。當簇頭進行選舉時，檢測出所有節點剩余能量，根據能量設定閾值，篩選出低于閾值的節點，避免其過早成為簇頭節點，從而延長節點生命周期。

關鍵詞：無線傳感器網絡；簇頭選舉算法；節點生命周期

中圖分類號：TN711.1 ?文獻標志碼：A

0 引言

無線傳感器網絡是一種自組織網絡，它的核心原理是通過無線通信技術將數目不同的傳感器節點以自組織的方式組合在一起，體系結構如圖1所示。傳感器節點被部署在無線傳感器網絡中指定區域，各節點負責對所覆蓋的特定對象進行監測和數據采集，然后在自身進行處理后，通過路由傳輸至匯聚節點，最終把數據信息傳遞給網絡擁有者［1］。在無線傳感器網絡的使用中，傳感器節點可能被部署在惡劣的環境中，因此在節點自身儲存能量耗盡后無法及時更換電源，從而導致網絡的功能受到影響。為了提高網絡能效，許多科研人員提出了簇頭選舉的方案，以實現節點能量的優化管理，延長網絡的生命周期［2-3］。

許多學者通過對路由協議進行研究來均衡網絡能耗，從而延長網絡生存周期。RAY等［4］提出了EE-CPK-means算法，根據與基站之間的距離確定簇頭節點，避免簇頭的分布過于集中或者分散。劉志龍等［5］提出一種基于遺傳算法的網絡拓撲控制方法，根據最優解控制實現網絡拓撲控制。Harmanpreet［6］提出一種可伸縮分簇路由EESCP，通過蜻蜓粒子群進行簇頭選舉優化。

傳統的LEACH算法簇頭的過程中是隨機選舉的，網絡負載比較均衡，并且LEACH選用分簇結構，使網絡具有良好的擴展性。但是簇頭的選擇是隨機的，無法控制簇頭節點的位置分布。可能會出現因簇頭節點過于集中或分散于網絡邊緣，導致網絡節點能耗不均，出現一些節點過早死亡的現象。EE-CPK-means 算法，根據與基站之間的距離確定簇頭，使簇頭的分布更加均勻，但低能量節點多次充當簇頭，影響節點生命周期的問題仍然存在。

1 WSN網絡模型

在無線傳感器網絡中，節點傳輸方式是全向傳輸，傳輸過程如圖2所示。傳感器節點隨機分布在需要監測的區域，將此區域劃分為若干個小區域，每個小區域都作為一個目標，某些區域甚至能被一個或少數節點完全覆蓋，這種區域被稱作目標區域。但某些小區域仍然需要多個節點才能夠完全覆蓋，這種區域被稱作關鍵目標區域。定義目標區域集合為T={t1，t2...tn}，傳感器節點集合為C={c1，c2...cm}。每個傳感器節點的ci的能量為ei，傳感器感知范圍為Ri.。

在M×M的二維平面區間內，將N個節點隨機部署。對無線傳感器網絡的屬性提出如下假設：節點部署完畢后，節點位置不再發生改變。傳感器節點能量有限，死亡后不再參與網絡。各節點可以計算出彼此之間的距離。基站的位置固定，基站與節點、節點與節點之間可以直接進行無線通信。節點分為簇頭節點和成員節點兩種模式。所有成員節點將信息匯聚成一個數據包由簇頭節點傳輸到BS。

針對上述WSN模型分析得知，為了解決低能量節點多次充當簇頭過早死亡問題，須在生成簇頭節點時動態考慮節點的剩余能量，排除將能量較低的節點生成簇頭，而導致簇頭節點過早死亡。

2 算法描述

在EE-CPK-means算法的基礎上，本文提出一種在簇頭選舉時，自動根據節點剩余能量實時生成閾值的改進算法。引入閾值公式，剩余能量因子，降低低能量節點擔任簇頭而過早死亡的概率。

本算法主要從以下幾個角度去設計：

（1）EE-CPK-means算法簇頭節點選舉時能很好地考慮到了成員節點與基站之間的距離來進行選舉，但并未考慮節點的剩余能量不同對選舉的影響。本算法對這一點進行改進，避免剩余能量低的節點成為簇頭節點。

（2）對于閾值公式進行優化，防止因閾值未及時更新而導致篩選功能不夠準確的問題。

（3）在選舉過程中加入了兩種函數，完成對數據收集和簇頭的選舉。GatherData（）函數用于數據收集。成員節點通過設定好的函數進行數據收集。BuildCluster（）函數用于網絡建簇。尋找最近的簇頭節點并建立通信關系。首先，將所有節點與基站之間的距離和剩余能量掃描記錄，然后根據閾值公式實時生成閾值公式。其次，選擇條件最優的節點成為簇頭節點。最后，成員節點與簇頭建立通信關系。

2.1 閾值公式

為了減少能量的消耗，本文將成員節點與最近簇頭相隔的距離按式（1）生成閾值，篩選掉與最近簇頭的距離小于或等于閾值的成員節點，拒絕其加入任何簇。閾值T（n）計算公式如下。

T（n）=p1-p×［rbmod（1/p）］（nG）（1）

其中，p為群首節點與非群首節點的個數比；r代表輪數減1；G是當前輪中未當選成員節點集合；1/p輪為一次循環。

2.2 剩余能量因子

隨著網絡的不斷運行，節點的剩余能量不斷下降。如果剩余能量較低的節點多次被選舉為簇頭節點，則其會因為能量過早耗盡而死亡。所以節點的剩余能量也是選舉簇頭節點一個重要考慮因素。本文引入了剩余能量因子公式如（2）所示［7］。

renf=EicurE0（2）

其中，E0為節點初始能量， Eicur為節點剩余能量。

2.3 步驟

本算法在簇頭選舉時通過加入函數，并考慮成員節點與基站之間的距離和剩余能量，避免了簇頭過早死亡或分布不均，從而延長了網絡生命周期。

步驟如下：

（1）根據EE-CPK-means算法選舉簇頭。

（2）檢測所有簇頭節點的剩余能量。

（3）當簇頭節點剩余能量小于給定的閾值，根據EE-CPK-means算法選擇新的簇頭節點替換，原節點不再是簇頭節點，而是作為普通節點。

（4）調到第（2）步，直至找不到節點替換剩余能量小于給定閾值的簇頭，網絡生命周期停止。

（5）結束。

3 算法分析

本算法基于EE-CPK-means算法，在簇頭選舉策略中低能量節點多次擔任簇頭的問題上取得改進。本算法經過實時根據節點剩余能量生成閾值的方法，以下方面相比原協議有所提高：

（1）引入剩余能量因子，對剩余能量的界定更加精確。

（2）對閾值公式進行優化，加入剩余能量因子，在簇頭選舉過程中保留原算法的根據距離選舉和添加剩余能量因素。

經過分析將3種算法LEACH 、EE-CPK-means和本文的算法對比如表1所示。

4 結語

在無線傳感器網絡中，節點生命周期是影響網絡生命周期的根本因素。如何延長節點生命周期是目前網絡研究的重要熱點。本文對LEACH和EE-CPK-means兩個算法進行分析，總結其優缺點。針對EE-CPK-means算法在選舉簇頭時出現低能量節點多次充當簇頭而過早死亡的問題，本文提出一種優化的簇頭選舉改進算法。算法的改進由兩部分組成：（1）引入剩余能量因子，優化閾值公式。（2）通過實時更新閾值，優化篩選準確度。通過理論分析得出本文提出的改進算法，相比傳統的LEACH協議和EE-CPK-means算法，能夠有效均衡節點能耗，延長網絡生命周期。

參考文獻

［1］田興臣.大規模無線傳感器網絡節能策略研究［D］.成都：電子科技大學，2021.

［2］王海明.無線傳感網中分簇算法研究［D］.呼和浩特：內蒙古大學，2021.

［3］SHAH M.A review on wireless sensor networks（WSN）［J］.Journal of Network Communications and Emerging Technologies（JNCET），2015（2）：10-12.

［4］RAY A，DE D.Energy efficient clustering protocol based on K-means EE-CPK-means-midpoint algorithm for enhanced network lifetime in wireless sensor network［J］.IET Wireless Sensor Systems，2016（6）：181-191.

［5］劉志龍，張淋江，周紅雷．非均勻分簇無線傳感器網絡拓撲控制仿真［J］．計算機仿真，2019（4）：260-264.

［6］SINGH H，SINGH D.An energy efficient scalable clustering protocol for dynamic wireless sensor networks［J］.Wireless Personal Communications，2019（4）：2637-2662.

［7］黃利曉，王暉，袁利永.基于能量均衡高效WSN的LEACH協議改進算法［J］.通信學報，2017（S2）：164-169.

（編輯 王雪芬）

An improved cluster head election algorithm based on EE-CPK-means in WSN

Wang? Yan， Xu? Liya*， Zhou? Mengling

（School of Computer and Big Data Science， Jiujiang University， Jiujiang 332005， China）

Abstract： Wireless sensor networks are widely used in various fields， such as environmental monitoring， natural disaster early warning， public health， etc. The nodes in the network are powered by batteries， and the node energy is limited. The traditional selection of cluster heads in wireless sensor networks is random， and the location distribution of cluster head nodes cannot be controlled， resulting in uneven energy consumption of nodes and premature death of nodes.The EE-CPK-means algorithm determines the cluster head node by the distance between each node and the base station. It can prevent cluster head nodes from being too centralized or decentralized. However， the problem that low energy nodes act as cluster heads for many times and thus die prematurely still exists.This paper proposes an improved cluster head election algorithm based on EE-CPK-means algorithm.When selecting the cluster head， the residual energy of all nodes is detected， and the threshold value is set according to the energy to screen the nodes below the threshold value， so as to avoid them becoming cluster head nodes prematurely， thus prolonging the node life cycle.

Key words： WSN; cluster head election algorithm; node life cycle