扰动粒子群优化的SDWSN路由算法

胡 敏，汪腾飞，黄宏程

重庆邮电大学 通信与信息工程学院，重庆 400065

1 引言

传统的无线传感器网络（Wireless Sensor Networks，WSN）大多面向于特定的应用，在部署后，节点的策略和网络功能难以改变，导致网络的资源利用率低，网络管理变得困难[1-2]。软件定义网络（Software-Defined Network，SDN）将网络设备控制面与数据面分离，带来网络应用可编程、集中式控制、网络设备开销少等好处[3]。SDN的思想应用于WSN中产生了软件定义无线传感器网络（Software-Defined Wireless Sensor Networks，SDWSN），SDWSN由软件定义传感器节点组成，可根据实时感测请求按需加载不同的程序，动态地重新配置其功能和属性。SDWSN利用了SDN的优点，通过将WSN中分布式的节点管理有机整合，形成全网优化的管理控制，提高了WSN的资源利用率。

Luo等人[4]第一次将SDN与WSN结合来解决无线传感器网络中的一些固有问题。Gante等人[5]提出了一种基于基站的集中式控制平面的智能无线传感器网络，可实现简单的重配置，以解决传统传感器网络中传感器节点的移动、定位等问题。Huang等人[6]提出了一种SDWSN原型，以提高环境监控WSN的适应性和能量效率。已有的研究在不同方面证实了SDWSN方案是可行的，但对于WSN中的重要问题如路由算法，如何利用软件定义的优势来进行研究的较少。WSN中，节点的能量由电池供应且难以替换，因而节能路由算法成为研究热点[7-9]。LEACH（Low-Energy Adaptive Clustering Hierarchy）[10]协议依概率随机选取簇头节点，通过轮换簇头的方式来平衡网络能耗。但簇头选择的随机性会使得簇头分布不均匀，且簇头的选择没有考虑能量因素。HEED（Hybrid Energy-Efficient Distributed clustering）[11]考虑节点的剩余能量，先选取一部分候选簇头，然后根据簇内能量消耗代价竞争产生最终簇头，使选出的簇头分布更均匀，能量较高。但单跳通信的方式导致距基站较远的节点能耗大。采用多跳通信方式的网络中，距基站越近的簇头越多地参与数据转发而使其能量快速耗尽。EEUC（Energy-Efficient Uneven Clustering）[12]采用非均匀分簇的方法使得距基站较近的簇拥有较少的成员节点，簇内能耗减少，从而平衡簇内能耗和数据转发能耗。DEBUC（Distributed Energy-Balanced Unequal Clustering）[13]利用节点剩余能量构造的计时广播机制代替EEUC中的竞争机制，节省了簇头竞争过程中的能量消耗。但簇头的选择采用概率和门限值会导致能量较小节点的无效竞争，且能够继续工作的簇头还需重新分簇，造成能量浪费。IPSOCH[14]利用中继节点分担簇头能耗，考虑节点剩余能量和距离信息，利用改进的粒子群优化算法选择簇头和中继节点，有效地提高了能量使用效率。然而，在SDWSN的范例中，路由功能在逻辑上集中在控制器上。现有的WSN路由协议采用分布式算法在节点上运行，分簇和路由选择过程需要进行大量的信息交换，增加了网络负担，消耗大量能量，而基于软件定义的WSN中的路由协议如NWPSO-based[15]、SDUCR[16]，其簇头能量消耗不均衡，导致网络的能量利用率低，生存周期短。

本文在已有的SDWSN架构下，提出了一种基于扰动粒子群优化的能耗均衡路由算法tPSOEB（Extremum Disturbed Particle Swarm Optimization based Energy-Balanced Routing Protocol），通过考虑节点的剩余能量、位置和能量均衡信息选择簇头，并引入扰动改进了PSO的搜索性能，依据节点距基站距离、节点剩余能量和邻居节点个数将整个网络动态划分为大小不等的簇。同时每周期进行一轮全局分簇和k轮局部簇头更新，节省分簇时的能量消耗。在簇间路由建立时，传感器控制服务器采用集中式方式根据链路能耗、节点剩余能量和簇内节点数构建最短路由树。仿真结果表明，tPSOEB能显著提高网络的能量使用率，延长网络寿命。

2 网络模型与能耗模型

2.1 网络模型

网络模型如图1所示，其由在基站处实现的传感器控制服务器CS（Sensor Control Server）和一组随机分布在监测区域的软件定义传感器节点组成，且具有如下性质：（1）考虑一组感测目标如温度、湿度等，随机分布在SDWSN区域内。每个软件定义传感器节点配备具有不同感测能力的多个传感器，可同时执行多个任务。（2）传感器控制服务器可根据执行任务的不同，为传感器节点分配相应的程序来重新编程一些传感器节点。（3）每个传感器节点配有ID，其能量、通信能力相同。（4）传感器节点部署后可感知其位置，不能随意移动，节点的发射功率能够进行自动调整。

图1 多任务软件定义无线传感器网络

2.2 能耗模型

能耗模型同文献[7]，节点向相距为d的目标节点发送k bit数据的能量消耗为：

节点接收k bit数据的能量消耗为：

数据聚合也会消耗一定的能量，聚合1 bit数据消耗的能量用EDA表示。

3 tPSOEB路由算法

tPSOEB算法包括簇的形成、簇间多跳路由建立和数据传输阶段，这三个阶段周期性地执行。簇建立阶段，传感器控制服务器综合网络信息和业务需求选出簇头，划分大小不同的簇，然后根据分簇结果建立簇间最佳路由，将选出的簇头信息以及路由信息发送给相应簇头，簇头接收控制服务器的指令，指示所在簇区域内的节点完成相应的任务。数据传输阶段，簇头收集簇内节点的数据，将数据聚合后依照传感器控制服务器所做的路由决策进行数据传输。

3.1 基于扰动粒子群优化的簇头选择算法

簇头的选择对路由算法的性能影响重大，为了节省传感器节点的能量，簇头的选择由传感器控制服务器完成。设在全网范围内随机部署了N个软件定义传感器节点，根据应用的需要被分为了n个簇，设簇头节点集合为CN（Cluster Head Node）={CN1,CN2,…,CNj,…,CNn},普通传感器节点集合为ON（Ordinary Node）={ON1,ON2,…,ONi,…,ONN-n}，节点Ni的邻居节点集合为NNi（Neighbor Node）={Nj|Nj是 Ni的邻居节点，d(Ni,Nj)＜R}，R为节点的通信半径，d(Ni,Nj)表示Ni与Nj的欧式距离。

为了选出最佳的簇头，定义适应度函数：

适应度函数的定义基于以下几个因素考虑：f1为剩余能量比例因子；f2为距离因子，含义为选出的一组簇头距传感器控制服务器的平均距离与网中普通节点距传感器控制服务器的平均距离的比值，其值越小，代表选出的全网簇头距离传感器控制服务器的平均距离越小；f3为簇内紧凑性因子，其值越小，代表选出的全网簇头距它们的邻居节点越近；f4为能量均衡因子。适应度函数越小，表明选出的簇头剩余能量越高，距传感器控制服务器及邻居节点越近，剩余的能量越均衡。参数 α1、α2、α3、α4决定了各因子对适应度函数贡献的比值且α1+α2+α3+α4=1。粒子群优化算法（Particle Swarm Optimization，PSO）是一种群体化算法，通过适应度对粒子进行评价，经过不断迭代来找到优化问题的解。因其简单高效，收敛速度快，可用来进行簇头的选择。但标准粒子群优化算法在求解多峰值问题时易陷入局部最优，导致选出来的簇头并非全网最优。因此，本文改进PSO算法，提出一种基于扰动粒子群优化的簇头选择算法。

（1）对优化问题和算法参数初始化。创建一定数量的粒子，每个粒子代表问题的初始解，即选出的一组簇头。设粒子数量为m，种群X={x1,x2,…,xm}，第i个粒子的速度矢量为vi={vi1,vi2,…,vin},位置矢量为xi={xi1,xi2,…,xin},n代表问题的维数即簇头个数。由式（3）评价每个粒子，得到粒子对应的个体最优解为 pi={pi1,pi2,…,pin},所有粒子找到的全局最优解为 pg={pg1,pg2,…,pgn}。

（2）更新粒子的速度和位置矢量。标准PSO算法的速度和位置更新公式分别为：

式中，vij是第i个粒子速度矢量的第 j维值；t为迭代次数；c1、c2为加速因子；r1、r2是服从U(0,1)均匀分布的随机数；ω为惯性权值。

标准的粒子群算法由于群体中所有粒子都向同一个全局最优粒子学习，很容易因学习强度过大，群体丧失多样性而陷入局部极值。本文对其进行改进，首先引入扰动更新全局最优粒子gbest，待更新的粒子向扰动后的全局最优粒子gbest'学习。然后对个体最优值的进化停滞次数t0进行判断，高于阈值时进行随机扰动，进一步增加迭代后期群体的多样性，更利于找到全局最优解。极值扰动算子与改进的速度更新公式为：

（3）根据式（3）评价每个粒子，更新粒子的极值。返回到步骤（2）进行循环，用式（11）和式（9）对粒子的速度和位置进行更新，直到达到最大迭代次数，当前最优解即选为簇头。

3.2 簇头竞争半径的计算

为均衡簇头能耗，采用非均匀分簇的结构，DEBUC等协议在计算簇半径时只考虑节点到基站的距离而忽略了节点能量、节点个数等因素的影响，导致集群的划分不够合理。本文综合考虑簇头到传感器控制服务器的距离、簇头的剩余能量及其邻居节点的个数来计算簇竞争半径，计算公式如下：

式中，β1、β2、β3是参数控制因子且 β1+β2+β3=1；dmax、dmin分别为簇头CNj到传感器控制服务器CS的最大、最小距离；Emax为所有簇头剩余能量的最大值；|NNj|为簇头CNj邻居节点的个数；|NN|min为全部簇头邻居节点个数的最小值；Rmax为预先定义的最大竞争半径。

传感器控制服务器根据扰动粒子群算法选出簇头后，由式（12）得到每个簇头的竞争半径划分簇区域。定义簇头CNj的成员节点集为MNj={Ni|Ni是CNj的成员节点，d(Ni,CNj)＜Rc}。传感器控制服务器选出簇头得到簇成员集合后生成簇头通知包，发送到对应的簇头，簇头收到通知包后生成与之对应的流表项，并产生簇成员通知包，发送到相对应的簇成员节点。

为了避免频繁分簇，tPSOEB算法每周期进行一轮全局分簇和动态的k轮局部簇头更新。在以上分簇阶段完成后，传感器控制服务器依据当前分簇情况，在每个簇内选出能够作为代理簇头的节点，代理簇头的选择依据簇内节点的适应度来决定。适应度的计算公式为：

如果簇内节点ONi的适应度小于λ倍当前簇头节点的适应度，则该成员节点可作为代理簇头。一个簇内代理簇头的个数即为该簇局部簇头更新的次数。设簇Cj中代理簇头的个数为kCj，则全网的局部簇头更新次数为：

3.3 簇间多跳路由的建立

传感器控制服务器选出全网的簇头后，通过Dijkstra算法利用收集到的簇头的能量信息、位置信息、分簇后簇内普通节点数、任务的Qos需求等信息，以自己为根节点构建最短路由树，路由的建立采用集中式算法在传感器控制服务器处运行。

传感器控制服务器通过最小跳路由发现得到网络中全部可用链路集合。其步骤为，引入一个距离阈值TDmax，若簇头与传感器控制服务器的距离小于阈值则一跳传输数据，找到所有可一跳与传感器控制服务器通信的簇头集合CN1hop，将这些单跳链路加入总可用链路，重复这一过程，找到所有可一跳与CN1hop通信的簇头集合，将所得单跳链路加入总可用链路，直至网络中所有簇头都能通过一跳或多跳将数据发送给传感器控制服务器。

为了找出最佳路由路径，定义链路权值为：

式中，ωij为链路(CNi,CNj)的权值；Ec(CNi,CNj)为链路(CNi,CNj)的能量消耗；E(CNj)为簇头CNj的剩余能量为簇头CNj的成员节点数；为可一跳与CNi通信的簇头其成员节点数均值。链路的能耗越小，簇头剩余能量越高，簇内节点数越少，则该簇头越适合选作下一跳节点，从而节省数据传输的能耗，达到整个网络的能耗平衡。传感器控制服务器由式（15）得到每条链路的权值后，用Dijkstra算法计算出每个簇头的最优数据传输路径，生成对应簇头的流表项并发送给相对应的簇头，多跳路由建立。tPSOEB算法的工作流程如图2所示。

4 算法分析及仿真

4.1 消息复杂度分析

假设网络中有N个节点，根据应用需要选出n个簇头，每周期开始时，传感器控制服务器收集网中全部节点的剩余能量、距离等信息，消息开销为N，选出簇头后需下发n个簇头通知包，每个簇头广播一条簇成员通知包，消息开销为n，最后N-n个簇成员节点广播N-n条入簇消息包，因此在首轮簇建立阶段网络总消息开销为：

图2 tPSOEB算法工作流程图

本文算法采用后续k轮进行局部簇头更新，在首轮簇建立阶段完成后，传感器控制服务器由式（13）在每个簇内计算簇内节点的适应度并进行排序即可得到每个簇在下一轮进行更换的簇头，此时传感器控制服务器只需生成n个局部簇头更新包发送到对应的节点即可完成局部簇头更新，簇头更新后需广播簇成员通知包，消息开销为n，然后簇成员节点广播入簇消息，消息开销为N-n，因此后续k轮簇的建立阶段网络总消息开销为：

采用局部簇头更新方式使后续k轮簇建立过程消息包的数量减少了N。综上，tPSOEB算法在分簇阶段消息的复杂度为O(N)。EEUC、DEBUC等算法在簇建立阶段，候选簇头竞争最终簇头时需要广播和接收大量消息，总的消息开销分别为(2T+1)N、(T+1)N+n，T为候选簇头节点的比例。此外在网络初始化阶段，基站需广播消息并获取网络中节点距基站的最近和最远距离以用于竞争半径的计算，消息开销为N。IPSOCH算法消息开销为(2N+n)。本文算法簇的建立工作由传感器控制服务器来做，避免了节点间大量的信息交换，因此消息开销较小。

4.2 仿真环境和参数分析

为了验证tPSOEB算法的性能，在MATLAB中进行仿真实验，并与LEACH、EEUC、DEBUC以及IPSOCH算法进行对比，通过网络的生命周期和总能耗的变化来衡量算法的性能。tPSOEB算法中的参数 α1、α2、α3、α4决定了适应度函数的4个因子所占的比重。α1越大，表明选出的节点剩余能量越高，由于节点担任簇头要消耗大量的能量，剩余能量越高的节点越适合担任簇头，因此要使α1取较大值。α2、α3分别表示节点距传感器控制服务器的平均距离与节点距邻居节点集的平均距离对适应度的贡献比例，它们的取值越大，表明选出的簇头距传感器控制服务器越近，簇内能耗越小，使得网络的能量消耗减少。α4取值越大，表明选出的簇头节点剩余的能量越均衡，簇头节点剩余能量均衡程度越高，越容易避免出现网络空洞。通过调节这4个参数的大小可以使算法的性能有所偏重。本文致力于设计非均匀分簇算法来延长网络寿命，通过选取多组取值不同的α1、α2、α3、α4来仿真对比其对网络生命周期的影响，从而确定最优的参数取值。图3显示了 α1、α2、α3、α4分别取不同值时tPSOEB算法网络寿命的变化曲线，其余仿真参数如表1所示。可以看出在此场景下 α1、α2、α3、α4取值为0.4、0.2、0.2、0.2时，网络的生命周期最优。用理论化的方法选择最优的参数正在进一步的研究中。

图3 权重系数取不同值时存活节点数的变化

表1 仿真实验的参数设置

4.3 实验结果及分析

首先，分析网络生命周期随簇头个数的变化，如图4所示，增加簇头的数量可以使得划分的集群更小，簇内成员节点数减少，从而节省簇内能耗。但如果一味地增加簇头个数，簇间的能量消耗将会显著升高。另外，簇头的任务之一是融合所管辖区域内成员节点的感测数据，消除错误数据，减少冗余信息，如果选择过多的簇头，那么相似的感测数据可能会传输给不同的簇头，导致部分冗余的信息发送给传感器控制服务器造成能量浪费。因此，对于给定网络存在一个最优簇头数使得能量效率最高，本场景中最优簇头数为18。

图4 网络生命周期随簇头个数的变化

图5 为各算法存活节点数随仿真时间的变化曲线。可以看出同LEACH协议相比，EEUC、DEBUC、IPSOCH以及本文所提算法都显著提高了网络的生命周期，这是因为它们通过多跳路由，节省了簇头的能量消耗。同时，本文算法第一个节点死亡时间相比LEACH、EEUC、DEBUC以及IPSOCH分别延长227.0%、49.5%、24.8%和16.6%，网络生存时间分别延长了110.3%、58.6%、36.6%和12.7%。这是因为本文引入了软件定义的架构，采用集中式的算法，将网络拓扑的划分和路由决策都交由传感器控制服务器来进行，网络中的簇头无需进行路由计算，大大减少了簇头的能量消耗。此外，传感器控制服务器在选择簇头时，使用tPSO来改进对PSO的搜索，很好地考虑了节点的剩余能量和位置信息，产生了更好的网络聚类结构，因此节点消耗的能量更少。

图5 各种路由算法存活节点数对比

图6 为5种算法网络剩余总能量随仿真时间的变化，曲线的斜率代表能量消耗的速率。可以看出本文算法相对于LEECH、EEUC、DEBUC和IPSOCH算法能量消耗速度慢且波动较小，说明本文算法更好地均衡了网络中所有节点的能量消耗，从而延长了网络寿命。

图6 网络能耗对比

5 结束语

本文针对软件定义的无线传感器网络提出了一种能耗均衡的路由算法。传感器控制服务器采用集中式的算法调取网络中节点信息用于集群划分和路由计算。根据网络中节点的剩余能量、位置和能量均衡信息，采用扰动粒子群算法优化簇头的选择，同时依据节点距基站距离、节点剩余能量和邻居节点个数将网络动态划分为大小不同的簇以均衡簇头的能耗，使数据传输距离短且整个网络能耗小。路由计算综合考虑链路能耗、节点剩余能量和成员节点数构建最短路径树。仿真结果表明，tPSOEB能显著提高网络的能量使用率，延长网络寿命。