基于遗传算法和模糊C均值聚类的WSN分簇路由算法

董发志 丁洪伟 杨志军 熊成彪 张颖婕

摘 要：针对无线传感器网络（WSN）的节点能量有限、生命周期短、吞吐量低等问题，提出一种基于遗传算法（GA）和模糊C均值（FCM）聚类的WSN分簇路由算法GAFCMCR，采取“集中分簇，分布簇头选举”的方式。网络初始化时基站采用由GA优化的FCM聚类算法形成网络分簇。第一轮簇头由距簇中心最近的节点担任;从第二轮开始，簇头的选举由上一轮的簇头负责，选举过程综合考虑候选节点的剩余能量、与基站的距离、与簇内其他节点的平均距离三个因子，并根据网络状态实时调整三个因子的权重。在数据传输阶段，将轮询机制引入簇内通信。仿真结果表明，相同网络环境下，与LEACH算法和基于K-Means的均匀分簇路由（KUCR）算法相比，GAFCMCR将网络生命周期延长了105%和20%。GAFCMCR成簇效果良好，具有良好的能量均衡性和更高的吞吐量。

关键词：无线传感器网络;模糊C均值聚类;遗传算法;均匀分簇;轮询机制

中图分类号： TP393.04

文献标志码：A

WSN clustering routing algorithm based on genetic algorithm and fuzzy C-means clustering

DONG Fazhi1， DING Hongwei1*， YANG Zhijun1，2， XIONG Chengbiao1， ZHANG Yingjie1

1.School of Information Science and Engineering， Yunnan University， Kunming Yunnan 650500， China ;

2.Yunnan Academy of Educational Sciences， Kunming Yunnan 650223， China

Abstract： Aiming at the problems of limited energy of nodes， short life cycle and low throughput of Wireless Sensor Network （WSN）， a WSN Clustering Routing algorithm based on Genetic Algorithm （GA） and Fuzzy C-Means （FCM） clustering （GAFCMCR） was proposed， which adopted the method of centralized clustering and distributed cluster head election. Network clustering was performed by the base station using a FCM clustering algorithm optimized by GA during network initialization. The cluster head of the first round was the node closest to the center of the cluster. From the second round， the election of the cluster head was carried out by the cluster head of the previous round. The residual energy of candidate node， the distance from the node to the base station， and the mean distance from the node to other nodes in the cluster were considered in the election process， and the weights of these three factors were real-time adjusted according to network status. In the data transfer phase， the polling mechanism was introduced into intra-cluster communication. The simulation results show that， compared with the LEACH （Low Energy Adaptive Clustering Hierarchy） algorithm and the K-means-based Uniform Clustering Routing （KUCR） algorithm， the life cycle of the network in GAFCMCR is prolonged by 105% and 20% respectively. GAFCMCR has good clustering effect， good energy balance and higher throughput.

Key words： Wireless Sensor Network （WSN）; Fuzzy C-Means （FCM） clustering; Genetic Algorithm （GA）; uniform clustering; polling mechanism

0 引言

無线传感器网络（Wireless Sensor Network，WSN）由大量廉价的微传感器节点组成，可以部署在监控区域，并可以通过无线通信方式形成自组织网络。传感器节点可以感知网络，收集和处理数据并将信息传输给监测中心[1]。近年来WSN广泛应用于监测、跟踪、事件检测、监视和灾害管理等各方面[2]。WSN的长期有用性主要依赖于节点的生命周期。节点的寿命完全取决于其电池电量，由于这些电池几乎不可更换，所以通过节约电池能量可以实现无线传感器网络生命周期的延长[3]。针对这个问题，许多层次型路由协议被提出，通过控制成簇、优化网络的拓扑结构达到降低网络能耗、延长网络生命周期的目的[4]。

最经典的分簇路由协议是由Heinzelman等[5]提出的LEACH（Low Energy Adaptive Clustering Hierarchy）算法，它将无线传感器网络划分为若干簇，每个簇中随机选取至少一个簇头，簇内节点将自己收集的数据发送给簇头，簇头进行数据融合之后通过单跳或者多跳将数据发送给基站。采用“轮”的方式将能量损耗均匀分布到各个节点，从而延长了生命周期;但是簇头的选取没有考虑节点的剩余能量，若能量低的节点被选为簇头，则会加快节点的死亡。Heinzelman等[6]在LEACH的基础上又提出了LEACH-C（LEACH-centralized）算法，由基站集中计算分簇，减少了簇头的计算能耗，但是没有考虑簇头节点的位置。Kumar等[7]提出了U-LEACH（Universal-Low Energy Adaptive Cluster Hierarchy）算法，利用不均匀成簇解决了LEACH协议中的热点区域问题。Bakaraniya等[8]提出了基于K-means分簇的K-LEACH（Kmedoids-LEACH protocol）算法，初始阶段利用K-means进行分簇，提升了网络性能，但簇头的选举未考虑节点能量。张雅琼[9]提出的基于K-Means 的均匀分簇路由（Uniform Clustering Routing based on K-Means，KUCR）算法利用K-Means进行分簇，采取一次成簇、多次簇头更新的机制，提升了性能，但簇头选举时并未考虑节点与其他节点的距离关系。严静静等[10]利用粗糙C-均值聚类改进了LEACH算法，利用粗糙C-均值聚类进行分簇，保证了簇头节点分布均匀，延长了生命周期，但在簇头选举时未考虑节点与基站的距离。

本文在研究LEACH、KUCR算法的基础上，提出了一种基于遗传算法（Genetic Algorithm，GA）和模糊C均值（Fuzzy C-Means，FCM）的WSN分簇算法（Clustering Routing algorithm based on Genetic Algorithm and fuzzy C-means clustering， GAFCMCR）。该算法的主要特点是：在网络初始化阶段，由基站采用GA改进的FCM算法进行集中式分簇;然后，每个簇内节点根据自身的剩余能量、到基站的距离以及与簇内其他节点的距离三个因子进行簇头的竞选;最后，在数据的传输阶段，簇内通信引入轮询控制，簇间采用载波侦听多路访问（Carrier Sense Multiple Access，CSMA）机制。仿真结果表明，相比LEACH和KUCR，GAFCMCR能够有效延长网络生命周期，降低能耗，提高网络的吞吐量。

1 系统模型

1.1 网络模型

本文对无线传感器网络作出如下假设：网络中有N个节点随机分布在面积为M×M的监测区域中，节点部署之后不随时间移动;节点的初始能量相同，可以获取自身的位置和剩余能量，且都可以担任簇头，能够进行计算处理和数据融合，具有唯一地址;基站位于监测区域中心，能量和计算能力无限;所有节点都可以和基站直接通信。

1.2 能耗模型

本文采用与文献[11]相同的一阶无线电能耗模型，节点发送lbit的数据消耗的能量包括发射损耗和功率放大损耗两部分，一个节点经过距离d发送lbit数据的能耗如下：

ETX（l，d）=

lEelec+lεfsd2，   d

lEelec+lεmpd4， d≥d0

（1）

接收消耗的能量和距离无关，接收lbit数据消耗的能量如下：

ERX=lEelec

（2）

式中：Eelec为节点每发送或接收1bit数据消耗的能量;d0为节点之间传输数据的模型选择的一个阈值，取值为d0= εfs/εmp 。当传输距离小于d0时，采用自由空间信道模型;當传输距离大于d0时，采用多路径衰减模型[12-14]。其中相应的参数εfs和εmp表示的是上述两种情况下单位功率放大时需要的能量。

2 GAFCMCR

GAFCMCR采用与LEACH相同的按“轮”运行方式，如图1所示，分为簇的形成、簇头选举和稳定传输三个过程。在初始化阶段各节点将位置信息发送给基站，由基站采用优化的FCM算法进行迭代计算，形成C个簇。不同于LEACH算法每轮都需要重新分簇，GAFCMCR的第一轮分簇完成后，以后的轮次只在簇内进行簇头的更新，只在最优簇数发生改变时才重新分簇。这样有的轮次簇结构和簇头都是不变的，减少了频繁分簇和簇头选举带来的能量损耗，能延长生命周期。

2.1 簇的形成

网络初始化时，基站首先为每个节点分配唯一的通信ID，各节点将自身的位置坐标发送给基站，基站经过计算，将分簇信息广播给节点。广播信息包括簇ID、节点与基站的距离。

2.1.1 最优簇头数

FCM算法需指定聚类数目，在无线传感器网络中，为了得到合理的分簇，根据网络特征确定最优簇头数。对于本文的网络模型和能耗模型，基站位于监测区域中心，所以每个节点到基站的距离都小于等于d0，故簇头和簇内节点运行一轮消耗的能量[15]为：

ECH=l Eelec  N c -1 +Eda  N c +Eelec+εfsd2toBS

（3）

EnoCH=l（Eelec+εfsd2toCH）

（4）

式中：c为簇头数，Eda为融合1bit数据消耗的能量。则网络的总能耗为：

Etotal=l[2NEelec+NEda+cεfsd4toBS+Nεfsd2toCH]

（5）

要使得总能耗最小，则

Etotal c =0

（6）

dtoBS为节点到基站的距离，计算如下：

E[dtoBS]=∫A x2+y2  1 A dA=0.765 m 2

（7）

dtoCH为节点到簇头的距离，计算如下：

E[d2toCH]=

（x2+y2）ρ（x，y）dxdy=ρ∫2π0∫ m  πc  0 r3drdθ= m2 2πc

（8）

综上可得最优簇头数：

c=  N 2π   m dtoBS =  N 2π    2 0.765

（9）

2.1.2 模糊C均值聚类

FCM算法首先是由Ruspini[16]提出来的，目前在机器学习中应用广泛，将FCM应用到无线器网络的分簇中，能够将网络中的节点按照紧密程度分为固定的几个簇，有效减少了由于簇结构不均匀带来的能量损耗。FCM算法的目标函数为：

Jm=∑ N i=1 ∑ C j=1 （μij）m（dij）2; m∈[1，∞）

（10）

式中：dij=‖xi-cj‖，xi为第i个样本，cj为第j个聚类中心;μij是样本xi对第j个聚类中心的隶属度;m是模糊因子。

μij的更新公式为：

μij= 1 ∑ C k=1   dij dik   2 m-1

（11）

聚类中心更新的公式为：

Cj= ∑ N i=1 （μij）mxi ∑ N i=1 （μij）m

（12）

算法终止条件为：‖ U （k+1）- U （k）‖≤ε。

FCM算法流程如图2所示。

2.1.3 遗传算法优化初始聚类中心

FCM算法对初始聚类中心敏感，容易收敛于局部最优解，为了克服该缺点，将GA应用于FCM算法的优化计算中，由GA得到初始聚类中心，再使用标准的FCM算法得到最终的分类结果。

遗传算法源于生物进化论和遗传学，是一种模仿自然界适者生存机制的自适应搜索算法[17-18]。GA优化FCM算法的步骤[19-20]为：

步骤1  参数初始化， 设置种群规模N，交叉概率pc，变异概率pm，终止进化的迭代次数T以及初始聚类数目c。采用二进制编码，根据聚类中心坐标（xi，yi），将其编码为基因串α={α1α2…αi…αq}，其中，q=c×2，在α中每两个值代表一个聚类中心的坐标。

步骤2  设置迭代次数t=0，并随机选取初始种群。

步骤3  计算个体适应值，其适应函数f=1/Jm。

步骤4  进行选择、交叉、变异，获得新一代的种群，判断新种群是否满足停止迭代准则，t=t+1。

步骤5  如果t大于最大迭代次数，则停止迭代，输出聚类个数和聚类中心，否则返回步骤2继续迭代。

GA优化FCM算法的流程如图3所示。

GA优化的FCM算法的伪代码如下：

输入   X ={x1，x2，…，xN}T（样本集合），c（聚类数目），m（模糊因子），N（种群规模）， pc（交叉概率），变异概率pm（交叉概率）， T（迭代次数）;

输出  聚类结果，聚类中心。

程序前

be gin

t←0;

Initialize Pop（t）;

//初始化种群

计算初始化种群个體适应值f=1/Jm;

wh ile t

GA-Operation Pop （t）;

//遗传算法运算

计算个体适应值f=1/Jm;

t+ +;

end while

bestcenter;

//最优初始聚类中心

repeat

fo r i=1 to n do

fo r j=1 to c do

根据式（11）计算价值函数

根据式（12）计算隶属度矩阵 U

根据式（13）更新聚类中心

end for

end for

until

‖ U （k+1）- U （k）‖≤ε

return 聚类结果和聚类中心

end

程序后

2.1.4 动态分簇

随着网络的运行，存活节点数不断减少，网络特征发生了变化，初始化阶段确定的最优簇数不再适合当前网络状态。所以GAFCMCR在每一轮运行结束时，基站会根据式（9）计算最优簇数，当最优簇数改变时，就重新分簇，直到簇数为1。动态的分簇过程优化了性能，延长了网络的生命周期。

2.2 簇头的选举

为了减少簇头的能耗，避免节点过早死亡从而导致网络失效，本文算法的簇头选举综合考虑节点的剩余能量、到基站的距离以及与簇内其他节点的距离关系等三个因素。第一轮分簇完成后，基站广播分簇结果时将每一簇离簇中心最近的节点指定为簇头。

第二轮开始，簇头的选举综合考虑剩余能量、与基站的距离及它与簇内其他节点的距离等三个因素。

剩余能量是簇头选举的重要参考，GAFCMCR采用节点的剩余能量与所属簇内所有节点平均剩余能量的比值作为参考标准，如式（13）：

f1（i）= Eres（i）  1 n ∑ n j=1 Eres（i）

（13）

式中：n为节点i所属簇的节点总数。f1越大说明节点i的剩余能量越高。

式（14）表示候选节点到基站的距离因素：

f2（i）=  1 n ∑ n j=1 dtoBS（i） dtoBS（i）

（14）

式中，dtoBS（i）为节点i到基站的距离。f2越大，说明节点距离基站越近，簇头到基站传输数据的距离越短，能耗越低。

式（15）表示候选节点与簇内其他节点的距离关系：

f3（i）= n ∑ n j=1 d（i， j）

（15）

式中，d（i， j）为节点i到节点j的距离。 f3越大，说明相对于其他节点，候选节点能够使簇内通信的距离更小。

每一轮的最后一帧，节点将自身位置和剩余能量发送给簇头，簇头根据式（16）重新计算每个节点的参量p。节点剩余能量多、距离基站近且与其他节点紧密程度较好的节点能够成为候选簇头。

p（i）=αf1（i）+βf2（i）+γf3（i）

（16）

其中， α、β、γ为权重参数，用来调整三个因子的重要程度。初始化阶段， α=β=γ=1/3;随着网络的运行，节点能量不断下降，成为影响网络生命周期的重要因子，所以权重应该随着网络的运行而变化。将α、β、γ按照下式进行更新：

α=Einit/Eres（i）

（17）

β=γ=（1-α）/2

（18）

运行过程中，α动态增大，剩余能量大的节点当选簇头的概率更高，使得能量更加均衡。

簇头节点选取参量最大的节点i与自身参量进行比较：

pCH≤λpmax（i），λ∈（0，1）

（19）

如果式（19）成立，则簇头通知节点i当选为新簇头，并交换成员信息，节点i广播成为簇头信息;若不成立，则本轮次不进行簇头的更新。由于不是每轮都需要更新簇头，从而节省了能耗，降低了时延。式（19）中，λ为网络系数，影响网络的更新速度：取值太小，则个别节点会长时间担任簇头而导致能量消耗大，缩短了节点生命周期;取值太大，则需要频繁更新簇头，也导致能耗增加。

2.3 数据传输

LEACH及其大多数改进算法的簇内通信机制均采用时分多址（Time Division Multiple Access，TDMA）机制[21-22]，簇头为每个成员节点划分一个时隙，节点在固定的时隙内传输数据。但在无线传感器网络中，并不是所有节点都一直处于活跃状态，有些节点在一定时期处于休眠状态，当需要采集数据时再唤醒。这就会出现空闲的时隙，增加了能量的浪费。因此根据文献[23]，将轮询控制引入无线传感器网络，作为GAFCMCR的簇内通信介质访问控制（Medium Access Control， MAC）機制，采用由簇头节点依次轮询成员节点的方式来传输信息，簇头节点建立轮询表来记录所需要轮询的节点。轮询表记录的是轮询顺序和节点ID的对应关系，而且轮询表并不是一一对应，一个节点ID可以对应多个序号，反映了该节点具有较高优先级，在一个轮询周期内被多次访问。当节点能量耗尽或者处于休眠状态时，将此节点从轮询列表中移除，充分利用了时隙，又可以有效避免常见协议因碰撞带来的能量损耗。

簇头节点完成一个轮询周期后进行数据的融合，采用CSMA机制单跳将数据发送至基站。

GAFCMCR的伪代码如下：

程序前

初始化网络，设定相关参数;

fo r round=1 to maxround do

if  round= =0 then

执行GA优化的FCM算法，得到结果和聚类中心;

CH←离聚类中心最近的节点

el se

fo r i=1 to n do

根据式（17）计算每个节点的参量p（i）

end for

if  pCH≤λpmax（i） then

CH←pmax（i）对应节点

end if

if  最优簇数发生改变&&最优簇数大于1 then

执行GA优化的FCM算法，更新各参数

end if

end if

end for

程序后

2.4 算法复杂度分析

假设网络中有N个节点，每轮选取K个簇头，下面对算法的复杂度进行分析：

不同于其他轮，第一轮的簇头选举直接由基站指定，当分簇完成后，基站广播N条消息，消息中包含了哪些节点是簇头和各节点所属簇，各节点不用发送请求直接入簇。所以算法第一轮的复杂度为：O（N）。

从第二轮开始，每轮选举K个簇头，当前簇头发送一条消息与新簇头进行成员信息的交换，共发送K条消息;新的簇头向成员发送消息，告知其他节点自己成为簇头，此过程共产生N-K条消息。因此每轮的总消息数为：K+N-K=N。所以算法每轮的复杂度为：O（N）。

3 仿真与分析

3.1 仿真环境

本文使用Matlab 2014Rb软件进行无线传感器网络的仿真。 在理想的信道条件下，忽略随机因素的干扰和信号冲突等影响，监测在100m×100m传感器网络区域内随机分布的100个节点。节点的能量损耗主要考虑数据包和控制包的发送和接收能量损失，以及数据融合能量。仿真所用到的具体参数见表1。遗传算法的参数设置为：种群规模N=N×10×2，交叉概率pc=0.7，变异概率pm=0.01，终止进化的迭代次数T=100;FCM算法终止条件阈值ε=10-6。

3.2 GA改进FCM的必要性分析

FCM算法和GA改进的FCM算法应用于无线传感器网络同一环境的成簇结果如图4所示。从图中能够直观地看出，GA改进后的FCM算法成簇结果更加均匀。FCM算法成簇后有几个簇的成员到簇头的距离过远，这势必会增加簇内通信的能耗，而改进的FCM则使得簇间的通信距离比较均匀，能够减少能耗。说明用GA改进FCM算法形成网络分簇能够改善成簇效果。

3.3 成簇结果

GAFCMCR与KUCR、LEACH算法的成簇对比如图5所示，可以看出，LEACH算法由于簇头选举的随机性，成簇不理想，簇头分布不合理，簇的数量和大小不均匀，导致了能耗的增加;KUCR算法采用K-means聚类算法，根据节点位置和节点ID计算形成分簇结果，分簇比较均匀，但是由于K-means算法对于初始聚类中心敏感，容易陷入局部最优，成簇存在“极大簇”“极小簇”，造成了能耗失衡。GAFCMCR使用GA优化的FCM聚类算法进行分簇，使得成簇相比其他两种算法更加均匀，簇头分布位置更加合理。

3.4  网络生命周期

将网络生命周期定义为网络开始运行到出现第一个死亡节点期间的运行轮数，此定义下GAFCMCR算法的生命周期为2238轮，比LEACH和KUCR分别延长了105%和20%。也有研究将生命周期定义为网络运行开始到网络中全部节点都死亡所运行的轮数或者网络运行截止到一半节点死亡的运行轮数。表2统计了不同比例节点死亡运行到的轮数，从表中可以看出，网络运行的整个阶段GAFCMCR算法的生命周期都有优势。

图6是各算法生命周期对比，从图中可以看出，相比LEACH和KUCR，GAFCMCR有效提升了生命周期，而且GAFCMCR的曲线的斜率较大，说明能量均衡性好。GAFCMCR具有优势的原因是改进了聚类算法、成簇方式以及簇头的选举方式。

3.5 网络能耗

三种算法的网络剩余能量对比如图7所示，在相同初始能量下，GAFCMCR的网络剩余能量始终高于另外两种算法。这表明GAFCMCR能够有效降低能耗，主要原因是：GAFCMCR使用GA改进的FCM算法进行分簇，不存在极大、极小簇，簇头的选举过程综合考虑了剩余能量、节点与基站的距离以及与其他节点的紧密程度，距离基站近、与簇内其他节点近的节点大概率当选簇头，降低了簇头传输数据和簇间通信的能耗。

3.6 网络吞吐量

传感网络节点部署的主要目的就是收集监测区域的各种数据，因此网络的吞吐量是一个重要的性能指标。本文用基站接收到总的数据量来衡量网络的吞吐量。GAFCMCR和其他两种算法的吞吐量对比如图8所示，从图中可以看出：相比LEACH和KUCR，由于GAFCMCR的生命周期较长，所以基站接收了更多的数据;而且GAFCMCR的吞吐量从网络运行开始就高于其他算法，这得益于数据传输阶段引入了轮询机制，充分了利用了时隙。

4 结语

为了延长无线传感器网络的生命周期、降低能耗和提高吞吐量，本文提出了基于GA和FCM的WSN分簇算法GAFCMCR。在成簇階段，利用FCM算法实现分簇，并针对FCM算法对初始值敏感的问题，使用GA优化初始聚类中心后再进行聚类;在簇头选举阶段，综合考虑节点的状态，使得选出的簇头更合理;在数据传输阶段，将轮询引入簇内通信，提高了网络的吞吐量。实验结果表明，GAFCMCR能够有效降低能耗，提高能量的均衡性，明显延长网络生命期。

参考文献

[1] 徐晶晶，张欣慧，许必宵，等.无线传感器网络分簇算法综述[J].计算机科学，2017，44（2）：31-37. （XU J J， ZHANG X H， XU B X， et al. Overview of clustering algorithms for wireless sensor networks [J]. Computer Science， 2017， 44 （2）： 31-37.）

[2] SINGH S P， SHARMA S C. Cluster based routing algorithms for wireless sensor networks [J]. IJETI International Journal of Engineering & Technology Innovations， 2014， 1（4）： 1-8.

https：//pdfs.semanticscholar.org/32cf/4e781fa41fd314f567960cf1cb666fee9715.pdf

https：//zz.glgoo.top/scholar？hl=zh-CN&as_sdt=0%2C5&q=Cluster+based+routing+algorithms+for+wireless+sensor+networks&btnG=

[3] LIU F， WANG Y， LIN M， et al. A distributed routing algorithm for data collection in low-duty-cycle wireless sensor networks [J]. IEEE Internet of Things Journal， 2017， 4（5）： 1420-1433.

[4] GULERIA K， VERMA A K. Comprehensive review for energy efficient hierarchical routing protocols on wireless sensor networks [J]. Wireless Networks， 2019， 25（3）： 1159-1183.