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