WSN中基于改进粒子群优化算法的分簇路由协议

武小年，张楚芸，张润莲,2，孙亚平

（1.桂林电子科技大学广西密码学与信息安全重点实验室，广西 桂林 541004；2.桂林电子科技大学广西高校云计算与复杂系统重点实验室，广西 桂林 541004）

1 引言

在无线传感器网络（WSN,wireless sensor network）中，传统分簇路由协议通过簇头节点进行数据融合并发给基站，以减少网络通信量，降低网络能耗。但由于簇头节点承担的任务过重，加快了其能量消耗，缩短了网络生存周期。为分担簇头节点的任务并避免簇头节点离基站太远而加剧消耗，现有的分簇路由协议通常会选择离基站尽可能近的转发节点，由簇头节点将融合的数据发给转发节点，再由转发节点将数据发给基站。但若转发节点数量太少，节点的任务将非常繁重；若采用单跳方式向基站发送数据，当节点与基站距离超过阈值时，节点的通信开销将激增。如何在WSN路由协议中合理选举簇头节点与转发节点，并优化转发节点的传输路径、均衡和降低网络通信开销、延长网络生存周期是有待优化的问题。

针对WSN路由协议面临的上述问题，文献[1]采用随机分簇策略和周期性簇头轮换维持节点的能量平衡；文献[2]采用基于跳数和能量的分层自治系统实现合理的路由选择；文献[3]采用中继节点分担簇头的数据传输任务以降低簇头的能耗；文献[4]采用基于虚拟交叉区域的树型路由协议降低数据传输延迟；文献[5]通过等间距环形划分和等夹角扇形划分的非均匀分簇方式保证源节点与基站的通信距离最短；文献[6]采用基于节点接收基站信号强度和剩余能量的簇头选择方法避免频繁更换簇头；文献[7]采用基于压缩感知的聚类路由协议确定簇的通信半径以延长网络寿命。

粒子群优化（PSO,particle swarm optimization）算法是一种基于种群的群智能优化算法，具有实现简单、收敛速度快和搜索精度高等特点，在解决组合优化问题上相比其他算法有很大优势[8]。文献[9]采用动态调节簇内节点数的改进粒子群算法减少簇头节点能耗；文献[10]采用基于粒子位置和速度的重编码方式增加网络覆盖面积；文献[11]通过优化网络覆盖率和链路质量的方式提高网络能量效率，但这3个算法未考虑粒子群算法中相关因素对最优分簇的影响。文献[12]采用基于离散的粒子群算法选择簇头和中继节点构建最优簇结构；文献[13]通过调整惯性权重系数避免算法陷入局部最优；文献[14]采用基于模糊和网络编码的改进型粒子群算法构建节点到基站的最佳传输路径，并未考虑转发节点的通信开销。

综上所述，现有簇头节点选取方法主要根据剩余能量筛选，部分方法考虑了簇头节点与基站的距离，但未考虑簇头节点位置的均衡性，而位置分布均衡的簇头节点，能够有效缩短通信的总距离，降低网络通信开销；其次，现有分簇路由协议大多选取的转发节点太少，加大了转发节点的能耗，而部分增加了转发节点的协议，主要采用随机方式进行选取，其有可能与簇头节点重复，且未考虑被选取节点的剩余能量及位置是否均衡；第三，现有协议中转发节点采用单跳与多跳相结合的方式发送数据，靠近基站的转发节点采取单跳方式，采用多跳方式时主要考虑相邻转发节点的距离，缺乏考虑节点能量及面向基站的方向性，导致能量受限和路径不合理增加开销。基于粒子群算法的协议未能充分利用粒子群算法的优势，并对算法存在的不足进行优化，如粒子初始化的随机性容易导致节点分布不均衡并陷入局部最优；在速度更新计算中，固定的学习因子和惯性权重无法平衡局部搜索和全局搜索的能力，使算法的收敛速度缓慢，较难获得高质量的簇头节点集等。

针对上述问题，本文提出一种基于改进粒子群算法的分簇路由协议（CRIPSO,clustering routing protocol based on improved PSO algorithm in WSN），基于节点的能量和位置评估来筛选候选簇头节点；通过优化粒子群算法的惯性系数和学习因子，平衡算法的全局搜索与局部探索能力，选举出能量和位置合理的簇头节点，构建最优分簇；建立基于最小生成树的转发节点多跳数据传输路径，缩短通信距离。

2 系统模型

2.1 网络模型

首先对网络模型做如下约定。

1)WSN的实验区域形状为平面规则图形，传感器节点在监测区域中随机不均匀分布且固定不动，每个节点由一个全局唯一的ID标识。

2)基站的能量不受限，其他所有传感器节点能量有限，但各节点的初始能量相同，处理能力和通信能力相等。

3)节点无线发射功率可以自我调控，可自主选择发射功率。

2.2 能耗模型

WSN中，传感器节点的能耗主要包括通信能耗（如数据发送能耗与数据接收能耗）和数据处理能耗（如数据融合能耗），通信能耗与通信环境、传输距离、数据分组的大小有关。本文采用低功耗自适应分簇分层（LEACH,low energy adaptive clustering hierarchy）[1]的能耗模型，根据距离的不同分别采用自由空间模型或多路衰减模型。以d表示发射节点和接收节点之间的距离，d0表示门限距离；以Efs和Emp分别表示自由空间模型和多路衰减模型的功放因子参数；m表示一个数据分组的比特数，Eelec表示每传输1 bit数据的能耗，EDA表示每融合1 bit数据的能耗，则距离为d的2个节点传输mbit数据的发送能耗ETX(m,d)和接收能耗ERX(m,d)，以及融合mbit数据的融合能耗EDA(m,d)计算方法分别为

3 基于改进粒子群算法的分簇路由算法

合理的分簇划分及转发节点选取，将有利于缩短通信距离，降低并均衡节点通信开销，延长网络生存周期。本文改进粒子群算法选举能量与位置最优的簇头节点和转发节点，以降低和均衡网络通信开销。

3.1 簇头选举

3.1.1 簇头初始化

由于粒子群算法计算相对复杂，为避免选举计算增加节点的能耗，基于粒子群算法的分簇及路由选择计算都将由能量不受限的基站完成。在初始化过程中，所有节点将自身剩余能量、位置和编号信息发送给基站，基站接收并保存各节点的信息。在基站完成基于粒子群算法的分簇计算后，将计算结果进行广播，每一个存活节点根据接收的广播信息获得被选举节点及路由选择节点的具体位置信息。由基站完成粒子群算法的计算工作，实现选举和分簇的优化；各节点则不用进行复杂的计算，以有效节省节点的能耗。

粒子群算法采用随机方式选取粒子，传统的分簇路由协议也大多采用随机方式选取簇头，这容易陷入局部最优，导致簇内节点分布不均衡；且若被选取的节点能量过低，其难以承担簇头节点的繁重任务。针对该问题，对参与簇头节点选举的节点能量进行限制。

假设WSN中有N个存活节点，节点i的能量为E(i)，基站计算WSN中所有节点的平均剩余能量为

为保证选出的簇头节点有充足的能量进行簇内数据的处理，基站将所有能量大于或等于Eavg的节点构成一个集合EA，再采用随机方式，从EA中选择K个节点，存入候选簇头节点集，构成一个粒子。在初始确定了一组候选簇头节点后，其他的非簇头节点分别加入与其距离最近的簇头节点，完成初始分簇的建立。

采用随机方式在EA中继续选择K个节点，一共进行M次筛选，最终生成M组初始簇头节点集，即M个粒子，并形成M组的分簇。

3.1.2 适应度函数

因簇头节点能耗大，以节点剩余能量作为一个评价指标有利于选出更高能量的簇头节点；簇头所在位置在网络中分布越均衡，簇头与非簇头节点、基站的距离越小，通信开销将越小。为从M组初始簇头节点集中选举出最优的候选簇头节点集作为簇头节点集，以节点的剩余能量和位置作为评价指标，构建适应度函数对各个候选簇头节点集进行评估。

适应度函数要对初始簇头节点集中的所有候选簇头节点进行综合评估，这需要考虑所有候选簇头节点的平均能量与均衡位置。适应度函数值越大，表明选出的簇头节点集越优。

1)能量因子

能量因子是候选簇头节点集中所有候选簇头节点的平均剩余能量与所有非簇头节点的平均剩余能量的比值。候选簇头节点集的平均剩余能量越大，能量因子的值越大。以N表示WSN中的存活节点数量，一个候选簇头节点集中有K个候选簇头节点，则非簇头节点为N-K个；以表示第r轮中候选簇头节点CHi的剩余能量，表示第r轮中非簇头节点NCHj的剩余能量，则能量因子f1的计算式为

2)位置均衡因子

位置均衡因子通过通信距离来描述候选簇头节点在WSN中的分布状态，是候选簇头节点集中所有候选簇头节点与基站的距离与每个候选簇头节点与该分簇内非簇头节点的距离之和，与所有非簇头节点与基站距离的反比。对于具有N个存活节点的WSN，有K个候选的簇头节点，N–K个非簇头节点；以d(NCHi,BS)表示非簇头节点NCHi与基站BS之间的距离，d(CHj,BS)表示簇头节点CHj与基站BS之间的距离，d(NCHi,CHj)表示非簇头节点NCHi到其对应的候选簇头节点CHj的距离，则候选簇头节点集位置均衡因子f2的计算式为

其中，非簇头节点NCHi位于簇头节点CHj所在的分簇内。候选簇头节点集距离基站越近，各分簇内非簇头节点到簇头节点的距离越小，则网络通信距离越短，候选簇头节点集的位置在WSN中分布越均衡，f2的值越大。

基于能量因子和位置均衡因子，对候选簇头节点集采用加权方式计算适应度，适应度值函数F1计算方法为

其中，a∈(0,1]是权重系数，根据WSN对剩余能量和位置均衡的需求不同，可以调整权值。在适应度函数中，候选簇头节点集的剩余能量越大，位置分布越均衡，则适应度值越大，选出的候选簇头节点集越优。

针对M组初始簇头节点集，完成对其中各组候选簇头节点集的适应度函数计算后，记录每个候选簇头节点集本身适应度最大的位置作为每一组候选簇头节点集的局部最优位置（初始时为每个候选簇头节点集自身的位置），初始M组簇头节点集中最大适应度函数值的候选簇头节点集所在的位置为全局最优位置。

3.1.3 速度与位置的更新方法

根据初始适应度计算及初始产生的局部最优位置和全局最优位置，开始进行一轮迭代计算，首先对候选簇头节点集的位置更新，再计算位置更新后候选簇头节点的适应度。为完成对候选簇头节点集的位置更新并获得优化结果，设置一个速度来控制其变化过程。速度是矢量，设候选簇头节点在x和y方向上的速度分量分别为vxid和vyid，位置分量分别为xxid和xyid。2个速度分量的计算，初始时通过随机生成，但在后续的每一轮迭代中根据候选簇头节点集前一轮的速度分量与局部最优位置(pxid,pyid)和全局最优位置(pxgd,pygd)的变化关系确定，具体计算方法[15]为

其中，w是惯性权值，表示候选簇头节点集前一轮t–1迭代的速度对本轮t迭代的候选簇头节点集的速度的影响程度；c1是认知学习因子，c2是社会学习因子，分别表示候选簇头节点集靠近局部最优位置和全局最优位置的加速权值；r1,r2∈(0,1)为随机数，借鉴仿生学中的变异性，使簇头节点集具有变异特性。

基于2个速度分量，候选簇头节点在x和y方向上的位置分量xxid和xyid的计算方法为

3.1.4 具有自适应的学习因子和惯性权重

在上述速度更新计算中，传统基于粒子群算法的路由协议中的学习因子和惯性权重通常设置为固定值，无法平衡局部搜索能力和全局搜索能力，算法的收敛速度比较缓慢，较难获得高质量的簇头节点集。

在最优簇头节点集的选取过程中，前期的迭代侧重局部最优搜索，后期的迭代侧重全局最优搜索。局部最优搜索若搜索范围小，算法将容易陷入局部最优解，因此需要尽可能地扩大寻找最优候选簇头节点集的局部搜索范围，以增强群体的多样性；全局搜索则需要加快算法收敛，保持收敛速度和搜索效果的均衡。为达到该目标，设置认知学习因子c1和社会学习因子c2动态变化，在逐步迭代过程中，使c1从大到小变化，c2从小到大变化。

为满足2个学习因子的上述变化规律，结合传统学习因子的固定值设置情况，构造动态变化的学习因子，计算方法为其中，t为本轮迭代次数，tmax为最大迭代次数。随着迭代次数的变化，c1和c2动态变化，满足其变化规律，使算法能够自适应地在迭代前期扩大局部搜索范围，在迭代后期加快全局收敛速度。

在迭代过程中，惯性权值可以根据上一轮的速度影响本轮的搜索范围。在每一轮迭代结束都要对选取的候选簇头节点集进行适应度函数计算，以适应度值的结果动态调整惯性权值，使本轮迭代中选取的簇头节点集具有更均衡的位置。在此，采用非线性自适应惯性权重策略[16]计算惯性权值，方法为

其中，wmax和wmin分别为设置的最大和最小惯性权重，fi为候选簇头节点CHi的适应度值，fmin、fmax和favg分别表示本轮候选簇头节点集的最小、最大和平均适应度值。当fi＞favg时，本次候选簇头节点的速度主要参考上一轮的速度，增加候选簇头节点集的活跃度；反之，本次候选簇头节点的速度主要参考局部最优位置和全局最优位置，加速候选簇头节点集向优势空间靠近。

3.1.5 位置映射策略

在每一轮迭代后，候选簇头节点集的位置都将被更新，可能会出现更新后的节点位置在WSN中找不到匹配的存活节点。此时，需要进行位置映射处理[11]，基本思路是采取就近原则，将更新后的位置映射到距离该位置最近的存活节点所在的位置。以Xxid、Xyid为更新后的节点坐标，CMnx、CMny为网络中存活节点CMn的坐标，位置映射处理过程为

位置映射策略解决了网络节点分布离散所带来的更新后的位置与实际存活节点位置不匹配的情况。当出现多个节点更新后的位置坐标一样时，需要在更新节点的同时设置一个标志位，其他节点更新并进行位置映射时先检查标志位是否已经被标识为簇头节点，若是则依次选择距离次近的节点位置进行映射。

完成位置映射后，将位置更新后的各候选簇头节点集作为优化结果，计算各候选簇头节点集的适应度值。根据计算结果，更新每一组候选簇头节点集的局部最优位置以及本轮M组簇头节点集的全局最优位置。若迭代未结束，则继续进行候选簇头节点的位置更新与映射；否则，最后计算出的全局最优位置的候选簇头节点集作为最优簇头节点集，簇头选举完成。

基站在完成簇头选举后，进一步计算非簇头节点到各个簇头节点的距离，将非簇头节点加入距离最近的簇头节点，完成分簇。此时，传感器节点分为簇头节点和普通节点。普通节点仅进行数据发送，将自身监测的数据融合后单跳发送给簇头节点；簇头节点接收来自普通节点的数据后进行数据融合，再发送给相应的转发节点。转发节点需要进一步从普通节点中选取，其接收来自簇头的数据，并选择到基站的最优路径，将数据发送给基站。

在上述基于粒子群算法的分簇计算中，每一次分簇都需要重新获取各节点的剩余能量。针对下一次分簇的开启和期间各节点的通信交互，在此采用捎带技术以减少通信开销，即各节点完成数据采集和处理后，将自身剩余能量添加在数据后面一起发送给簇头节点；簇头节点进行数据融合，也将自身剩余能量与融合数据通过转发节点发送到基站；同样，转发节点将自身剩余能量捎带一起发送；基站在收到数据后，记录收到的各节点的剩余能量信息和数据，根据收到的节点剩余能量信息进行新一轮的分簇选举。各节点捎带的剩余能量信息为当前节点能量减去本次数据发送需要消耗的能量。

3.2 转发节点的选举与多跳传输

3.2.1 选举转发节点

在完成簇头节点选举后，将为簇头节点选择对应的转发节点。若网络中的转发节点过少，多个簇头节点通过少量转发节点向基站发送数据，将加大转发节点的能耗。针对该问题，现有的WSN路由协议采取一个簇头节点对应一个转发节点的方式[11]，增加转发节点的数量，但其采用随机方式在所有节点中选取，未考虑被选取节点的剩余能量及位置是否均衡。

本文在转发节点选举时，采用上述簇头节点选举的改进粒子群算法，为每个簇头节点在其分簇内的普通节点中选举一个转发节点，使被选举出的转发节点具有最优的能量和位置关系，并避免WSN中转发节点过少而加快其能量消耗。

在对转发节点计算和评估中，由于转发节点只能在一个分簇内选举，能量因子和位置均衡因子的计算方法与簇头节点选举的计算方法有所区别。

同样以N表示WSN中的存活节点数量，在选举出K个簇头节点后，WSN被分为K个分簇，初始化时根据簇头节点筛选的方法，在各个分簇内筛选出较高剩余能量的候选转发节点，组成候选转发节点集，每个候选集中包含K个节点。

在初始化后，普通节点数量为N–2K，以表示第r轮中候选转发节点RNi的剩余能量，表示第r轮中普通节点CNj的剩余能量，能量因子fit1的计算式为

以d(CNk,CHj)表示普通节点CNk到对应的簇头节点CHj之间距离，d(RNi,BS)表示转发节点RNi到基站BS的距离，d(RNi,CHj)表示转发节点RNi到对应的簇头节点CHj的距离，d(RNi,RNm)表示转发节点RNi和RNm之间的距离，转发节点位置均衡因子fit2计算方法为

其中，普通节点CNk位于簇头节点CHj所在的分簇内；候选转发节点RNi对应于簇头节点CHj。候选转发节点集距离基站越近，各分簇内簇头节点与转发节点的距离越小，候选转发节点集中各转发节点之间的距离越小，候选转发节点集的位置分布越均衡，fit2值越大。

基于候选转发节点选举的能力因子和位置均衡因子，采用加权方法构建的对候选转发节点集评价的适应度函数F2为

其中，b∈(0,1]为权值。候选转发节点集剩余能量越高，位置越均衡，则候选转发节点集的适应度值将越大，表明候选转发节点集越优。

在候选转发节点集的多次迭代选举过程中，采用与簇头节点选举类似的速度更新及位置映射方法，选出最优的转发节点集。

3.2.2 转发节点的多跳传输

基于LEACH能耗模型[1]，若基站远离WSN，转发节点与基站的距离d大于门限距离d0，发送能耗量级为d4；但若d≤d0，则节点间数据传输能耗大大降低，其能耗级数为d2。在实际应用中，基站通常远离WSN。现有WSN路由算法中转发节点常采用单跳的方式向基站转发数据[13]，能耗过大；而采用多跳方式的算法主要根据转发节点间的最短距离选择多跳[17]，没有考虑转发节点的剩余能量；且未考虑基站方向，多跳路径可能并非最短距离。

本文在选举出最优的转发节点集后，将根据转发节点与基站的距离d确定转发节点采用单跳还是多跳方式向基站传输数据，若d＞d0，则该转发节点采用多跳方式传输；否则该转发节点采用单跳方式传输。

在转发节点多跳路径选择中，本文利用构造最小生成树的方法搜索转发节点多跳传输的最短路径，同时兼顾节点剩余能量，以在降低网络能耗时，维持转发节点消耗的均衡性。

转发节点之间的路由以基站为树根，开始时将每个转发节点抽象为点，把转发节点用边连接起来，构造为一个带权的连通图G=(V,E)，其中，V包括所有转发节点，E包括V中任意2个节点间的边的集合。为搜索某个转发节点到基站的最优路径，需要综合考虑在每一跳中相邻2个转发节点间的距离与剩余能量。

假设以转发节点RNi为起点，要搜索到基站所途经的下一跳节点；若转发节点RNj为RNi的邻居转发节点，则需要评估节点RNj能否作为下一跳节点，在此，以这2个节点的边的权值来衡量，权值由2个节点的距离与剩余能量确定，并以wi,j表示。若节点RNj到基站的距离大于或等于节点RNi到基站的距离，则节点RNj不能作为下一跳节点，设置wi,j为∞；否则以2个节点的距离与剩余能量计算wi,j，计算方法为

其中，di,j表示转发节点RNi与RNj之间的距离，di,BS表示转发节点RNi与基站之间的距离，和分别表示第r轮转发节点RNi、RNj的剩余能量。若2个转发节点的距离越大，剩余能量越小，则2个节点的权值越大，该邻居转发节点被选为下一跳的概率越小。若转发节点RNi有多个相邻的转发节点，则分别计算转发节点RNi与其他相邻节点的权值，并选取权值最小的转发节点作为其下一跳节点。

在每轮转发节点选举结束后，将采用上述最小生成树方式建立转发节点到基站的多跳路径。基于最小生成树的多跳路径建立方法具体过程如下所示。在上述构造的带权连通图G=(V,E)中，将基站v0作为树的根节点加入V中，以U记录最小生成树的节点集合，W记录待选择的转发节点与其邻居节点所构成边的权值集合，T记录最小生成树中边的权值集合。

步骤1初始将根节点v0加入集合U中，T和W为空。

步骤2根据设置的门限距离d0，依次计算V中除v0外的某节点vi到v0的距离di,0，若di,0≤d0，则vi将采用单跳方式向基站传输数据，将vi加入U中，设置vi与v0的边的权值wi,0=0，并将wi,0加入T，转至步骤5；否则，转至步骤3，计算建立vi到v0的多跳路径。

步骤3根据式(13)计算vi到其他所有转发节点的边的权值，并将其加入W中。

步骤4在W中选出最小的权值wi,k，此时，vi到v0的距离为di,0，vk到v0的距离为dk,0，计算vi到vk的距离di,k。若di,0≤di,k，或者ETX(m,di,BS)＜(ETX(m,di,j)+ETX(m,di,BS))，则由vi经vk发送数据到v0的开销更大，此时，vi将直接发送数据到v0，将节点vi加入U中，设置vi与v0的边的权值wi,0=0，并将wi,0加入T，并置W为空；否则，将节点vi加入U中，并将wi,k加入T中，并置W为空。

步骤5若U=V，结束搜索，转至步骤6；否则，转至步骤2。

步骤6对于T中权值为0且后一个节点为v0的权值，将该权值对应边的前一个节点作为单跳节点输出；否则，将权值对应边的前一个节点作为起点，后一个节点作为下一跳节点，继续查找下一跳节点，直到下一跳节点为v0，形成多跳路径输出。

4 仿真实验及结果分析

在Matlab中模拟生成WSN，基站位于网络之外。在此环境下实现基于改进粒子群算法的路由协议并进行测试。测试计算机配置为2.3 GHz Intel Core i5，8 GB内存，64位Windows10。WSN初始化、簇头节点与转发节点选举、数据处理的相关实验环境及参数设置如表1所示。

表1 实验参数设置

考虑到WSN一般相对稳定，数据采集与数据处理的频率不高，在此主要根据WSN的数据处理频率来开启新一轮的分簇选举，即当簇头节点完成对簇内节点数据的融合并发送给基站，基站收到数据后，将开始新一轮的分簇选举。对于数据处理频率较快的WSN情况，本文暂未考虑，但可以采用事件触发发送，通过判断簇头节点的剩余能量来确定是否开启新一轮的分簇选举。

基于上述实验环境，测试适应度函数不同权值对网络的影响及本文协议CRIPSO下的节点能耗及网络生存周期变化情况，并与LEACH[1]、IPSOCH[12]和NAPSO[13]进行对比测试。

4.1 适应度函数权值的选取实验

在式(4)和式(12)中，权值a与b体现能量因子与位置均衡因子对适应度的影响程度。为设置合理的权值，根据节点剩余能量均方差评判协议采用不同权值进行迭代计算和网络运行中节点能耗的均衡程度。均方差越小，不同节点的剩余能量差别较小，均衡性较好。基于上述仿真环境，测试了本文协议在不同权值下运行的节点剩余能量均方差，结果如图1所示。

图1 适应度函数不同权值下的节点剩余能量均方差

图1表明，能量因子和位置均衡因子在不同权值下，对网络中节点的剩余能量与网络生存周期的影响不同。当能量因子与位置均衡因子对适应度函数的影响不平衡时，即能量因子影响较大位置均衡因子影响较小，或者反过来，所测得的均方差都较大，表明网络中节点的剩余能量差异较大，节点死亡较快，最终导致网络生存周期下降。当能量因子与位置权衡因子对适应度函数的影响均衡，特别是当a=b=0.5时，所测得的均方差最小，网络迭代执行的过程最长，网络生存周期最长。在后续的实验中，令a=b=0.5。

4.2 协议性能对比实验与结果分析

实验1协议运行能耗与生存周期

本文协议通过改进粒子群算法及设计的转发节点多跳传输路径选择方法，力图构建最优分簇和最短多跳传输路径。在上述实验环境下，对比测试了本文协议CRIPSO与LEACH、IPSOCH和NAPSO在2 500轮迭代中的节点存活数量及网络生存周期的变化情况，实验结果如图2所示。

图2 不同算法的网络生存周期对比测试结果

图2表明，随着迭代次数的增加，4种协议的节点能耗增加，WSN中存活的节点数量逐渐减少，直至最终节点全部死亡。

LEACH协议中簇头选举采用基于阈值的方法且簇头节点采用单跳传输，节点的能耗较大，在较短的时间内，死亡的节点较多，WSN生存周期最短。IPSOCH协议利用改进粒子群算法，通过节点的剩余能量信息和位置信息选择簇头和转发节点，优化了分簇，降低了节点能耗，相对LEACH协议节点死亡减缓，WSN生存周期延长。但IPSOCH协议在计算位置时仅考虑节点与基站的距离，其选举出来的簇头节点集难以达到全局最优。NAPSO协议增加了对惯性权重的改进，相比于IPSOCH协议进一步优化了分簇，降低了节点能耗，其WSN生存周期较IPSOCH协议有所延长。

本文协议CRIPSO基于能量因子与位置均衡因子评估候选簇头节点集，并通过自适应学习因子与惯性权重，选举出最优簇头节点集和转发节点集，并通过设计的最小生成树多跳传输路径选择方法建立路由，并采用捎带技术减少信息交互的开销，相对于对比协议，降低了转发节点的通信距离，降低并均衡了节点能耗，大大延长了WSN生存周期。

实验2簇头节点的位置均衡测试

位置均衡因子体现了簇头节点集与转发节点集在WSN中的分布均衡情况，节点分布的越均衡，则WSN通信中总的通信距离越小，节点能耗越低。基于上述实验环境，分别测试了本文协议CRIPSO与LEACH、IPSOCH和NAPSO协议在多次迭代中所有普通节点到簇头距离的总和、所有簇头节点到基站距离的总和，实验结果分别如图3和图4所示。

图3 不同协议中普通节点到簇头距离的总和

图4 不同协议中簇头到基站距离的总和

由图3与图4可知，随着迭代次数的增加，4种协议中所有普通节点到簇头的总距离、所有簇头到基站的总距离都越来越小。

LEACH协议在簇头选举中未考虑节点的能量和位置，初始时图3和图4的2个距离都最大，但在987轮后2个距离迅速下降，这是因为其通信距离大，能耗大且不均衡，节点死亡较快，随着存活节点大量减少，其通信距离减小，WSN生存周期大大缩短。IPSOCH协议考虑了位置信息，初始时其2个距离相对缩小，能耗有所降低，WSN生存周期延长。NAPSO协议在惯性权重中的优化，使选举的簇头节点向全局最优靠拢，初始时测得的2个距离低于IPSOCH协议，节点能耗降低，WSN生存周期较IPSOCH有所延长。IPSOCH和NAPSO协议同样在迭代后期因死亡节点激增，存活节点较少，测得的2个距离都小于本文协议，但生存周期都更小。

本文协议CRIPSO在位置均衡因子中考虑了簇头节点与基站的距离、每个簇头节点与该分簇内非簇头节点的距离，以及所有非簇头节点与基站的距离，且设计了优化转发节点通信路径的多跳传输路径选择方法，使筛选的簇头节点和转发节点在WSN中位置均衡，初始时2个距离都最小，有效降低并均衡了节点能耗，死亡的节点数量呈线性缓慢下降，变化较为稳定，延长了WSN生存周期。

实验3自适应学习因子的影响

在最优簇头节点集的选取过程中，前期的迭代侧重局部最优搜索，后期的迭代侧重全局最优搜索。在速度更新中，2个学习因子分别控制候选簇头节点集靠近局部最优位置和全局最优位置的加速度。固定学习因子无法满足迭代过程中的局部和全局最优搜索变化需求，自适应学习因子则给出了有效的解决方法。基于上述实验环境，分别对比测试了本文协议在固定学习因子和自适应学习因子下的网络生存周期变化情况。其中，固定学习因子时2个学习因子都设置为当前常用的固定值，令c1=2，c2=2。实验结果如图5所示。

图5表明，随着迭代次数增加，2种协议下的网络节点能耗增加，存活节点逐步减少。采用固定学习因子的协议在2 004轮节点全部死亡，采用自适应学习因子的协议的网络生存周期延长了100多轮。其原因在于自适应学习因子在迭代前期加速候选簇头节点集向局部最优位置靠拢，扩大了局部搜索能力，使选取的候选簇头节点集能够根据节点的剩余能量与位置均衡性进行有效调整，并倾向于局部最优；在迭代后期则逐步加速候选簇头节点集向全局最优位置靠拢，即加速算法进行全局收敛，获得节点剩余能量与位置均衡性全局最优的簇头节点，降低通信距离，降低并均衡网络能耗，延长了WSN生存周期。

图5 不同的学习因子值对网络的影响

实验4转发节点传输路径对比

转发节点承担了将WSN中的数据传输到基站的任务，数据量大且通信距离较长。根据LEACH能耗模型，若转发节点与基站的距离d大于门限距离d0，则发送能耗激增。缩短转发节点集与基站的通信距离，将可以大大降低网络能耗，延长WSN生存周期。基于上述同样的实验环境，对比测试了本文协议CRIPSO与IPSOCH、NAPSO的转发节点通信距离与网络生存周期情况，实验结果如图6所示。

图6 不同协议下的转发节点到基站的总距离

图6表明，随着迭代次数的增加，3种协议中转发节点到基站的总距离减少。IPSOCH协议和NAPSO协议在1 113轮后转发节点到基站的总距离快速下降，低于本文协议CRIPSO，这是因为2种协议中转发节点与基站均采用单跳方式进行数据传输，远离基站的转发节点在数据传输过程中采用多路衰减模型，节点能量衰减较快，转发节点死亡较快，网络中存活节点数量下降迅速，因此在开始时2种协议的总距离大于本文协议，在后期低于本文协议。

本文协议CRIPSO通过转发节点的优化选举，及基于最小生成树构建转发节点多跳传输路径，大大缩短了转发节点的通信距离，降低了网络能耗，节点死亡速度较慢，故在0～1 002轮期间本文协议的总距离最小；后期因存活节点远多于2个对比协议，其通信距离高于2个对比协议，WSN生存周期更长。

5 结束语

针对WSN分簇路由协议的分簇优化与转发节点的通信传输方法问题，提出一种基于改进粒子群算法的WSN分簇路由协议。该协议基于节点剩余能量和节点位置关系，优化粒子群算法中的初始化筛选、适应度函数及学习因子，实现簇头节点的优化选举和分簇，保证簇头节点的高能量，缩短网络通信距离，均衡和降低通信开销；并针对选举的转发节点，设计一种基于最小生成树的多跳路径选择方法优化通信路径，降低节点通信能耗，以延长网络生存周期。实验测试结果表明，本文提出的协议前期的局部搜索明显扩大，后期迭代的收敛速度加快，选举的簇头节点能量高、位置分布较为均衡，转发节点的传输路径较短，网络的能耗降低并比较均衡，延长了网络生存周期。