WSN中一種基于EE-CPK-means的簇頭選舉改進(jìn)算法

汪巖 徐利亞 周夢(mèng)玲

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

關(guān)鍵詞：無(wú)線(xiàn)傳感器網(wǎng)絡(luò)；簇頭選舉算法；節(jié)點(diǎn)生命周期

中圖分類(lèi)號(hào)：TN711.1 ?文獻(xiàn)標(biāo)志碼：A

0 引言

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

許多學(xué)者通過(guò)對(duì)路由協(xié)議進(jìn)行研究來(lái)均衡網(wǎng)絡(luò)能耗，從而延長(zhǎng)網(wǎng)絡(luò)生存周期。RAY等［4］提出了EE-CPK-means算法，根據(jù)與基站之間的距離確定簇頭節(jié)點(diǎn)，避免簇頭的分布過(guò)于集中或者分散。劉志龍等［5］提出一種基于遺傳算法的網(wǎng)絡(luò)拓?fù)淇刂品椒ǎ鶕?jù)最優(yōu)解控制實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)淇刂啤armanpreet［6］提出一種可伸縮分簇路由EESCP，通過(guò)蜻蜓粒子群進(jìn)行簇頭選舉優(yōu)化。

傳統(tǒng)的LEACH算法簇頭的過(guò)程中是隨機(jī)選舉的，網(wǎng)絡(luò)負(fù)載比較均衡，并且LEACH選用分簇結(jié)構(gòu)，使網(wǎng)絡(luò)具有良好的擴(kuò)展性。但是簇頭的選擇是隨機(jī)的，無(wú)法控制簇頭節(jié)點(diǎn)的位置分布。可能會(huì)出現(xiàn)因簇頭節(jié)點(diǎn)過(guò)于集中或分散于網(wǎng)絡(luò)邊緣，導(dǎo)致網(wǎng)絡(luò)節(jié)點(diǎn)能耗不均，出現(xiàn)一些節(jié)點(diǎn)過(guò)早死亡的現(xiàn)象。EE-CPK-means 算法，根據(jù)與基站之間的距離確定簇頭，使簇頭的分布更加均勻，但低能量節(jié)點(diǎn)多次充當(dāng)簇頭，影響節(jié)點(diǎn)生命周期的問(wèn)題仍然存在。

1 WSN網(wǎng)絡(luò)模型

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

在M×M的二維平面區(qū)間內(nèi)，將N個(gè)節(jié)點(diǎn)隨機(jī)部署。對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的屬性提出如下假設(shè)：節(jié)點(diǎn)部署完畢后，節(jié)點(diǎn)位置不再發(fā)生改變。傳感器節(jié)點(diǎn)能量有限，死亡后不再參與網(wǎng)絡(luò)。各節(jié)點(diǎn)可以計(jì)算出彼此之間的距離。基站的位置固定，基站與節(jié)點(diǎn)、節(jié)點(diǎn)與節(jié)點(diǎn)之間可以直接進(jìn)行無(wú)線(xiàn)通信。節(jié)點(diǎn)分為簇頭節(jié)點(diǎn)和成員節(jié)點(diǎn)兩種模式。所有成員節(jié)點(diǎn)將信息匯聚成一個(gè)數(shù)據(jù)包由簇頭節(jié)點(diǎn)傳輸?shù)紹S。

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

2 算法描述

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

本算法主要從以下幾個(gè)角度去設(shè)計(jì)：

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

（2）對(duì)于閾值公式進(jìn)行優(yōu)化，防止因閾值未及時(shí)更新而導(dǎo)致篩選功能不夠準(zhǔn)確的問(wèn)題。

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

2.1 閾值公式

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

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

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

2.2 剩余能量因子

隨著網(wǎng)絡(luò)的不斷運(yùn)行，節(jié)點(diǎn)的剩余能量不斷下降。如果剩余能量較低的節(jié)點(diǎn)多次被選舉為簇頭節(jié)點(diǎn)，則其會(huì)因?yàn)槟芰窟^(guò)早耗盡而死亡。所以節(jié)點(diǎn)的剩余能量也是選舉簇頭節(jié)點(diǎn)一個(gè)重要考慮因素。本文引入了剩余能量因子公式如（2）所示［7］。

renf=EicurE0（2）

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

2.3 步驟

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

步驟如下：

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

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

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

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

（5）結(jié)束。

3 算法分析

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

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

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

經(jīng)過(guò)分析將3種算法LEACH 、EE-CPK-means和本文的算法對(duì)比如表1所示。

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

［1］田興臣.大規(guī)模無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)能策略研究［D］.成都：電子科技大學(xué)，2021.

［2］王海明.無(wú)線(xiàn)傳感網(wǎng)中分簇算法研究［D］.呼和浩特：內(nèi)蒙古大學(xué)，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］劉志龍，張淋江，周紅雷．非均勻分簇?zé)o線(xiàn)傳感器網(wǎng)絡(luò)拓?fù)淇刂品抡妫跩］．計(jì)算機(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ìn)算法［J］.通信學(xué)報(bào)，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