基于PSO 优化模糊C 均值的WSN 分簇路由算法

孙爱晶，李世昌，张艺才

（1.西安邮电大学通信与信息工程学院，陕西 西安 710121；2.西安邮电大学电子工程学院，陕西 西安 710121）

1 引言

无线传感器网络（WSN,wireless sensor network）位于物联网的感知层，是由众多的传感器节点构成的一种自组织网络，目前，已被广泛地应用于环境检测等领域[1]。传感器节点具有体积小、性能稳定和功耗低等特点。然而，由于节点自身能量有限，网络的生命周期主要由节点的能量决定，因此如何平衡节点的负载始终是众多学者研究的热点问题。目前，研究者已经提出多种优化算法来解决这一问题，主要通过优化网络的拓扑结构、提高网络的通信效率来延长网络的生命周期。

针对节点的能耗问题，文献[2]提出了经典的LEACH（low energy adaptive clustering hierarchy）算法，将每一轮分为2 个阶段：成簇阶段和数据传输阶段。成簇阶段，LEACH 算法通过循环的方式在网络中随机挑选簇首，以实现网络整体能耗的均衡。数据传输阶段，簇首直接与基站通信，但由于簇首分布不均，且容易形成极大簇和极小簇，导致一些节点过载，使网络的生命周期变短。

针对LEACH 算法存在的问题，学者提出多种改进方法。文献[3]在LEACH 算法的基础上提出LEACH-C 算法，成簇阶段不再采用随机挑选簇首的方式，而是由基站根据节点的剩余能量来选择簇首，但簇首选取仅考虑了节点的剩余能量。文献[4]针对LEACH 算法提出了改进的EE-LEACH，成簇阶段选取剩余能量较高的节点作为簇首，同时数据传输阶段选择剩余能量较高的节点作为中继节点，平衡网络中的能耗，但数据传输阶段可能会形成路由环路和数据分组向后转发。文献[5]提出了LEACH-improved 算法，通过在成簇阶段加入间距因子、剩余能量因子和节点密度因子来改进LEACH 阈值计算式，同时综合考虑节点剩余能量和地理位置选择簇首，减缓了节点死亡，但容易形成极大簇和极小簇。

针对分簇路由方法，学者进行了多种改进。文献[6]提出了EEUC（energy-efficient uneven clustering）算法，成簇阶段利用非均匀成簇的方法，数据传输阶段的簇首以多跳的方式将数据传到基站，有效地平衡了簇首的负载，但网络规模越大，距离基站远的簇就越大，不利于大规模部署。文献[7]提出了FUCHAR（fuzzy based unequal clustering and ACO based routing）算法，成簇阶段使用模糊逻辑算法选取簇首，并将网络划分为不等簇，然后根据阈值动态更新簇首，数据传输阶段使用蚁群算法规划路由，实现了网络负载均衡。文献[8]提出了FBECS（fuzzy based enhanced cluster head selection）算法，成簇阶段使用模糊逻辑算法，根据节点剩余能量、节点密度与基站的距离计算每个节点的资格指数，节点通过随机生成的随机数与资格指数比较以产生簇首，有效地平衡了负载，但数据传输阶段仅考虑了单跳传输，不利于大规模部署。文献[9]提出PECE（predictive energy consumption efficiency）算法，成簇阶段通过节点度、节点间的相对距离和节点剩余能量选择簇首，数据传输阶段在考虑路径能量消耗和传播时延的基础上，使用蜂群优化算法选择最优路径，提高整体的网络性能，平衡整个网络的负载，延长网络的生命周期。文献[10]提出了BeeSwarm 算法，该算法在成簇阶段首先使用人工蜂群算法基于能量和距离因子寻找最优簇首并成簇，数据传输阶段使用人工蜂群算法为簇内节点规划到簇首的路由路径，簇首直接与基站通信。但BeeSwarm 算法在规划路径的过程中并没有考虑中继节点的能量，这会导致节点早衰。

为了解决上述问题，本文在已有研究的基础上提出了一种基于粒子群优化（PSO,particle swarm optimization）算法优化模糊C 均值（FCM,fuzzy C-means）的分簇路由算法POFCA。在成簇阶段，使用PSO 算法优化FCM 算法的初始聚类中心，避免FCM 算法在聚类过程中陷入局部最优。同时考虑到节点的随机部署会使一些节点距基站较近，因此在总簇数的基础上加入了基站簇，簇内节点直接与基站通信。为了防止簇首过载，簇首通过簇内节点的剩余能量、相对距离计算出每个节点的适应度函数值，动态地更新簇首。在数据传输阶段，簇内节点直接将数据包发送给簇首，簇首将收集的数据融合之后，通过最佳能距比，判断簇首是否需要多跳传输将数据转发到基站，并基于距离因子、能量因子和节点负载，使用猫群优化算法为簇首规划最优前向路由路径，降低簇首负载。

2 系统模型

2.1 网络模型

对本文算法与对比算法所使用的网络模型，做出如下几点假设。

1) 节点被随机部署在目标区域内，部署后节点不再移动，每个节点都有唯一的ID。

2) 所有的节点具有相同的初始能量、计算能力与通信能力，可自动调节发送功率。

3) 每个节点都可独立地与基站通信，基站的位置已知。

4) 节点可以根据信号的到达角与信号强度计算自身的相对位置[11]。

2.2 能量模型

无线传感器网络节点的能耗主要产生于数据分组的收发，本文采用与LEACH[2]相同的能量模型进行节点之间的通信。根据节点i与节点j之间的距离，选择信道模型。节点发送kbit 数据到距离为d的节点所需消耗的能量为

节点接收和融合kbit 数据消耗的能量为

其中，Eelec为接收或发送1 bit 数据所需消耗的能量，Eda为节点融合1 bit 数据所消耗的能量。节点选用何种发射模型进行通信由决定，fsε和εmp为自由空间信道模型和多径衰落模型功率放大所需的能量，当节点间的距离d＜d0时，选择自由空间信道模型，否则选择多径衰落模型。

3 FCM 算法的优化

3.1 FCM 算法

FCM 算法[12]是一种软聚类算法，被广泛地应用于机器学习之中，在无线传感器网络中可以表现为节点对某一聚类中心的隶属度是模糊的，可以表示为

其中，uij表示节点i对聚类中心j的隶属度，c表示聚类中心数，节点i对所有聚类中心的隶属度总和为1。

假设有N个节点被随机抛洒在目标区域内，网络的聚类中心数为c，FCM 算法可以通过最小化目标函数，将整个网络按地理相似度进行划分。FCM算法的目标函数可以表示为

其中，m为模糊因子，dij为第i个节点与第j个聚类中心的欧氏距离，uij为节点i对聚类中心j的隶属度，可以表示为

聚类中心数可以表示为

当迭代停止时，输出最优聚类中心。

3.2 PSO 算法优化FCM 算法

FCM 算法简单，收敛快，但对初始聚类中心较敏感，容易陷入局部最优，这在一定程度上限制了FCM 算法的应用。

PSO 算法[13]是模拟鸟群觅食行为的一种群体优化算法。PSO 算法中，每个粒子都可以看作一个可行解，根据适应度函数可以计算出每个粒子的适应度值，从而得到全局最优解gBest 和局部最优解pBest。每个粒子根据全局最优解和局部最优解更新自身的速度和位置，可以表示为

其中，c1、c2为学习因子，通常取2；v∈[vmin,vmax]；rand ∈(0,1)；w为惯性权重，w越大，全局寻优能力越强；w越小，局部寻优能力越强，w一般随着迭代次数增加而线性下降，可以表示为

其中，w∈[wmin,wmax]，iter 为当前迭代次数，itermax为最大迭代次数。

PSO 算法优化FCM 算法的步骤如下[14-15]。

步骤1PSO 算法种群初始化，参数初始化

步骤2根据式(4)，计算全局最优解gBest 和局部最优解pBest

步骤3根据全局最优解gBest 和局部最优解pBest 更新每个粒子的速度和位置

步骤4重复步骤2 和步骤3，直至达到最大迭代次数

步骤5将PSO 算法迭代的最优解作为FCM算法的初始聚类中心

步骤6执行FCM 算法

步骤7输出最优聚类中心

PSO 算法优化FCM 算法流程如图1 所示。

4 POFCA

POFCA 以轮为基本单位，每轮由成簇阶段和数据传输阶段组成。成簇阶段，基于最优簇首数，使用PSO 算法优化FCM 算法对网络进行分簇，并基于剩余能量和相对距离动态地更新簇首。数据传输阶段，通过最优能距比判断簇首是否需要多跳，并基于距离因子、能量因子和节点负载，使用猫群算法为簇首规划最优前向路由路径。

图1 PSO 算法优化FCM 算法流程

4.1 成簇阶段

成簇阶段使用PSO 算法优化FCM 算法，根据最优簇首数加上额外的基站簇，将整个网络划分为均匀的簇，降低簇内节点的通信成本。同时动态的簇首更新机制可以避免簇首过载，使簇内的负载更加均衡。

4.1.1 簇的形成

合理的簇首数有利于形成更加均匀的簇，同时降低网络的整体能量消耗成本。本文采用与文献[16]相同的最优簇首数，可以表示为

基于网络最优簇首数对粒子进行编码，编码格式为{x1y1x2y2…xc yc}，其中，xi和yi代表聚类中心在目标区域中的位置，可以表示为

其中，xmin、ymin、xmax、ymax分别代表目标区域的边界。

首先使用PSO 算法对聚类中心的位置进行优化，迭代结束后将最优粒子作为FCM 算法的初始聚类中心，FCM 算法继续进行优化，直至迭代停止，输出最优聚类中心，选择距离聚类中心最近的节点作为簇首。然后簇首为簇内成员分配TDMA 时隙，簇内节点仅在分配给自己的时隙到来时发送数据，其他时候都保持休眠。

考虑到节点的随机部署会存在一些节点距基站较近的情况，因此本文在最优簇首数的基础上额外增添了一个基站簇，使部分节点可以直接与基站进行通信，减少了节点回传所造成的额外能量消耗。新的粒子编码格式为{x1y1x2y2…xc y cxBSyBS}，其中，xBS和yBS为基站坐标，执行PSO 算法优化FCM算法时只需优化前2c个位，最后两位保持不变。

随着网络的运行，存活节点的数目也会逐渐减少，因此分簇是一个动态的过程，当最优的簇首数发生变化时，就需要重新成簇。

4.1.2 动态簇首的选举

簇首收集簇内节点数据会给簇首带来较大的负载，而簇内节点的负载则相对较小，为了平衡簇内节点的负载，考虑簇内节点的剩余能量与相对距离这2 个因素动态更新簇首。每次分簇完成后的首轮都以距聚类中心最近的节点担任簇首，其他轮则综合考虑剩余能量与节点之间的相对距离计算每个节点的适应度函数的值，评价是否担任簇首。

能量是节点面临的最重要的挑战，选择能量高的节点担任簇首有助于簇内负载更均衡。因此，考虑节点i的剩余能量与簇内所有存活节点的平均剩余能量的比值作为参考，可以表示为

其中，n为节点i所在簇内存活节点的数目，Eres(i)为节点i的剩余能量。节点i剩余能量越大，f1(i) 就越大，当选簇首的概率就越高。

节点的相对距离可以表示为

其中，dij表示为节点i与簇内其他节点j之间的距离。由式(13)可知，f2(i) 越大，节点之间的相对距离越小，节点之间的通信代价就越小。

每轮数据传输阶段，节点都会将自身剩余能量和位置包含在数据分组中，簇首根据约定好的通信协议读取该数据，然后通过式(14)计算每个节点的适应度值。节点的剩余能量越高，相对距离越大，节点在下一轮当选簇首的概率就会越大。

其中，α、β为权重因子，用于动态调整参数的权重，初始阶段。随着网络的运行，节点的剩余能量将会成为直接影响网络生命周期的重要因素，因此α、β需要在网络运行阶段动态更新，可表示为

其中，Eloss为簇内所有节点所消耗的能量，Etotal为簇内初始的总能量。能量消耗越多，α就会越大，节点的剩余能量也就越重要，整个簇内负载就会更加均衡。

为了避免频繁更换簇首造成不必要的通信损耗，当前的簇首节点会将自身的适应度函数值与簇内最大的适应度函数值的节点做比较[16]。

其中，λ为网络系数，决定簇首的更新速度。若式(16)满足，则簇首通知适应度函数值最大的节点作为下一轮的簇首，并交换簇内成员信息。新簇首为簇内成员分配新的TDMA 时隙，节点仅在时隙到来时发送数据分组，其他时间则休眠，降低节点能量损耗。若式(16)不满足，则保持当前簇首，下一轮簇内其他节点还是默认将数据发送到当前簇首。

4.2 数据传输阶段

簇内节点根据TDMA 时隙将数据分组发送给簇首后，簇首对收集到的数据进行融合，并基于簇首到基站的距离选择合适的中继节点将数据转发到基站，减轻长距离传输给簇首带来的负载，实现簇首负载平衡。

针对数据传输阶段簇首负载平衡，已有的算法[17-18]都是采用簇首到簇首的转发来平衡簇首负载。尽管能够在一定程度上减轻一些距基站较远簇首的负载，但簇首与簇首转发会给相距较近的基站的簇首带来额外负载。

为了减轻簇首的负载，基于簇首节点i与基站的距离di_BS，决定簇首应该经过几次中继然后将数据转发到基站，round()表示四舍五入。根据最优传输距离[19]dbest计算跳数，可以表示为

4.2.1 猫群算法

对于组合优化问题的求解，仿生算法往往可以带来好的结果。猫群优化（CSO,cat swarm optimization）算法[20]通过观测猫的习性而提出，同时基于猫的习性，将猫群分为搜索猫和跟踪猫，使其具有更好的全局寻优且不易陷入局部最优的特性，相较于遗传算法与PSO 算法，其实现起来也更加容易，收敛速度也更快。因此选择CSO 算法求解最优路径。

CSO 算法中每只猫都代表一个可行解。每只猫由猫的位置、猫的速度、适应度和标志值4 个属性组成，标志值用于区分猫处于搜寻模式还是跟踪模式，CSO 算法根据猫所处的模式进行不同的操作。

1) 搜寻模式

搜寻模式是一种全局寻优模式，通过模拟猫寻找下一个较优位置，这一状态定义了4 个变量。

SMP（记忆池），定义了每只猫的记忆大小，在搜寻模式下，将自身的位置复制M份。

SRD（变化域），定义了域的变化范围，一般取0.2。

CDC（变化数），定义了变异的维度大小。

SPC（自身位置判断），计算变异池中每只猫的适应度，选择适应度最高的替代当前猫。

处于搜寻模式的猫首先会将自身的位置复制M份，对于记忆池中的副本，根据CDC 的大小，随机地对当前值加上或者减去自身的SRD%，然后计算记忆池中所有副本的适应度函数，选取适应度最大的副本替代当前猫。

2) 跟踪模式

跟踪模式是一种局部寻优的模式，处于当前模式的猫根据当前全局最优解更新自身的速度和位置。

其中，为全局最优猫在第d维的位置，rand ∈(0,1)；c3是一个常量，一般取0.5；(t)为t时刻第k只猫在第d维的速度，(t+1)为更新后的速度。

CSO 算法可以分为以下5 个步骤。

步骤1初始化每只猫的位置和速度

步骤2根据分组率MR 将猫群随机划分为搜寻模式和跟踪模式

步骤3根据猫所处模式分别进行搜索算子和跟踪算子

步骤4计算每只猫的适应度，找到全局最优解

步骤5判断是否满足停止条件，否则执行步骤2～步骤4

猫群算法的工作流程如图2 所示。

图2 猫群算法的工作流程

CSO 算法寻找最优路径的过程需要评价路径的好坏，才能进一步寻找最优路径，因此需要为CSO 算法设计一个路径选择的适应度函数。

4.2.2 路径选择适应度函数设计

WSN 前向路由主要是为距基站较远的簇首选择中继节点，通过转发来自簇首的数据分组，降低簇首的负载。假设数据分组需要经过n跳发送到基站，也就是途经n-1 个中继节点，则最优的中继节点应具备以下几个特征。

1) 中继节点与中继节点之间的距离应该尽量均衡。

2) 中继节点应该具备较高的能量，以满足数据的传输需求。

3) 总距离应该尽可能地接近簇首与基站直接通信的距离。

4) 中继节点的选择应该避免选到其他簇首。

5) 中继节点的负载应该尽可能小，避免过度开发。

根据上述几点要求，设计了相应的适应度函数，可以表示为

其中，Emin是中继节点中能量最小的节点；节点的负载由节点接收数据分组的数量决定，loadmax是中继节点中具有最大负载的节点；dmin和dmax分别是前向路由路径中相邻节点距离的最小值和最大值；dinit和dtotal分别是簇首与基站的距离和整条前向路由路径的距离之和；α与β按照式(15)更新，将簇内节点的总能量消耗换为需要规划路由的簇首消耗的能量，簇内总能量换为簇首的初始能量，随着网络的运行，动态地调整参数权重比。

4.3 算法复杂度分析

初始化阶段网络中共有N个节点，最优簇首数为c，算法复杂度从成簇阶段和数据传输阶段2 个阶段进行分析。

成簇阶段，PSO 迭代次为M，种群大小为K，维度为2c，因此PSO 算法的复杂度为O(MKc)。FCM 算法的迭代次数为M，聚类中心维度为2c，因此FCM 算法的复杂度为O(Mc)。当簇首动态更新时，遍历的节点数为N，复杂度为O(N)。因此，成簇阶段的复杂度为O(MKc)。

数据传输阶段，簇首数为c，迭代次数为M，种群大小为K，因此，CSO 算法的复杂度为O(MKc)。

因此，POFCA 每轮的复杂度为O(MKc)，复杂度等同于算法执行所需要的基本运算次数。POFCA的每轮由成簇阶段和数据传输阶段组成，每阶段执行所需要的基本运算次数为MKc，即POFCA 每轮可以在2MKc次的运算次数中得到结果，算法可行。

5 仿真分析

采用 MATLAB 对本文算法和 LEACH[2]、LEACH-improved[7]等对比算法进行仿真，并在相同的仿真环境中对算法进行对比分析，仿真参数如表1所示。

5.1 成簇结果对比

图3 为LEACH 成簇结果。LEACH 的簇首是随机生成的，从图3 可以得出，2 号簇、3 号簇、5 号簇和8 号簇分别有15、21、15、15 个节点，而1 号簇只有4 个节点。4 个较大的簇吸引了65%的节点，而最小的簇仅吸引了4%的节点，同时簇首在簇中的位置不够合理，会增加额外的通信开销。

表1 仿真参数

图3 LEACH 成簇结果

图4 为FCM 算法成簇结果。FCM 算法需要指定聚类的数目，将聚类数目设为10，并对初始聚类中心进行初始化。从图4 中可以看出，1～3 号簇是完全重合的，这是由于FCM 算法对初始聚类中心敏感，若初始聚类中心相隔较近，则会重合，因此对FCM 算法进行优化是有必要的。

图5 为POFCA 成簇结果。POFCA 的聚类数由最优簇首数+1（基站簇）决定。从图5 中可以看出，POFCA 的每个簇都比较均匀，簇内节点的数目较稳定，同时簇首在簇中的位置也比较居中，基站簇（11 号簇）使距基站更近的节点直接加入基站进行直接通信，更合理。

图4 FCM 算法成簇结果

图5 POFCA 成簇结果

由图3～图5 可以看出，与LEACH 相比，POFCA的成簇结果更均匀，并克服了极大簇和极小簇的缺点。同时，使用PSO 算法优化FCM 算法克服了FCM算法对聚类中心敏感的问题，验证了POFCA 成簇的可行性和优越性。

5.2 网络生命周期

网络节点一经部署便无法移动或补充能量。随着工作轮数的增加，一些节点由于能量耗尽而死亡，产生新的覆盖空洞，影响整个网络的性能，因此网络生命周期是评价无线传感器网络性能的重要指标。

图6 是POFCA 和LEACH 算法、LEACHimproved 算法节点存活数的对比。从图6 中可以看出，POFCA、LEACH 算法和LEACH-improved 算法首个节点的死亡时间分别为1 173 轮、877 轮和816 轮，POFCA 比LEACH 算法、LEACH-improved算法分别提升了34%和44%。同时，POFCA 存活节点数目在整体上均高于2 种对比算法。因此，本文算法能有效地提高WSN 的网络生命周期。

图6 POFCA 和LEACH 算法、LEACH-improved 算法节点存活数的对比

5.3 网络剩余能量

图7 为3 种算法剩余能量的对比。从图7 中可以看出，LEACH 算法和LEACH-improved 算法的能量消耗差距不大，因为它们在聚类的过程中形成极大簇和极小簇的概率非常大，所以能量消耗不均衡。POFCA 是一种依靠地理位置的均匀分簇算法，簇首的选择和簇的构建都考虑了整体的负载均衡，因此所需消耗的能量较少。

图7 3 种算法剩余能量的对比

6 结束语

为了平衡WSN 负载，本文提出了一种新的分簇路由算法POFCA，该算法分别在成簇阶段和数据传输阶段进行了优化。在成簇阶段，使用PSO 算法优化FCM 算法，克服了FCM 算法容易陷入局部最优的缺点，使每个簇都更加紧凑，动态的簇首更新机制也使每个簇内的负载更均衡，同时基站簇的加入减少了节点的回传。在数据传输阶段，根据最佳能距比判断簇首是否需要多跳，基于距离因子、能量因子和节点负载使用CSO 算法为簇首规划前向路由路径。仿真分析结果表明，相较于已有算法，POFCA 的分簇结果更加均匀，可以有效地延长网络生命周期，降低节点的能量损耗。

本文算法主要针对二维网络，后续的工作可结合实际场景进一步研究三维WSN、无基站场景下WSN 的路由优化问题。