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

汪巖 徐利亞 周夢玲

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

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

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

0 引言

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

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

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

1 WSN網絡模型

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

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

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

2 算法描述

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

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

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

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

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

2.1 閾值公式

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

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

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

2.2 剩余能量因子

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

renf=EicurE0（2）

其中，E0為節(jié)點初始能量， Eicur為節(jié)點剩余能量。

2.3 步驟

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

步驟如下：

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

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

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

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

（5）結束。

3 算法分析

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

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

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

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

4 結語

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

參考文獻

［1］田興臣.大規(guī)模無線傳感器網絡節(jié)能策略研究［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協(xié)議改進算法［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