基于自适应粒子群优化的WSNs非均匀分簇路由算法*

杭 超, 李 刚,2,3, 包 涵, 李雯珺, 李德仓

(1.兰州交通大学 机电技术研究所,甘肃 兰州 730070； 2.甘肃省物流及运输装备信息化工程技术研究中心,甘肃 兰州 730070； 3.甘肃省物流与运输装备行业技术中心,甘肃 兰州 730070)

0 引 言

无线传感器网络(wireless sensor networks,WSNs)是由大量具有感知、无线通信和计算能力的低成本微型传感器节点组成[1～3]。网络一般由能量有限的电池进行供电,为了最大程度利用能量,设计一种高效的路由协议至关重要,尤其在大规模WSNs中,高效的路由协议能提高网络的工作效率,均衡网络能量。

相比平面路由协议,基于分簇的层次路由方法能有效提升网络的可扩展性[4],减少数据转发次数,降低网络能耗,提高数据采集效率和精度。LEACH[5]作为一种最为经典的均匀分簇路由算法,在一定程度上能缓解网络能耗问题,但该算法在簇头选举和簇间传输上存在缺陷,不利于网络中能量均衡。HEED[6]改进了LEACH上述缺陷，在簇首竞选时充分考虑到节点的剩余能量、节点相邻度和节点密度等因素,簇间路由以多跳的形式传输数据。李成法等人[7]提出了EEUC算法,运用竞争半径思想合理划分网络来均衡能耗,簇首到汇聚节点以多跳的通信方式。粒子群优化(particle swarm optimization,PSO)算法作为种群智能优化算法,相比其他算法在解决组合优化问题上具有很大优势[8]。文献[9]提出了一种基于PSO的非均匀双簇头分簇算法,簇首节点通过PSO算法优化确定,然后在规模较大的簇中构造一个副簇头以减轻主簇头的能耗,但选举副簇首会消耗大量能量,不利于网络能量平衡。文献[10]提出一种基于非线性自适应PSO(adaptive PSO,APSO)的WSNs分簇策略,通过调整传统PSO算法的惯性权重避免过早陷入局部最优。

为了使网络能耗更加均衡,本文提出一种基于APSO的WSNs非均匀分簇路由(APSO-based non-uniform clustering routing,APSO-NUCR)算法。仿真结果表明,该算法能有效均衡网络能耗,延长网络生存周期。

1 系统网络模型

将N个传感器节点随机布置在一个规则平面内,并具有以下性质：1)所有传感器节点同构且位置固定,并具有唯一编号；2)基站的能量和计算能力不被限制；3)根据需要可自主调节无线发射功率。WSNs的数据通信能耗模型计算公式如下

(1)

ERX(k,d)=kEelec

(2)

2 基于改进PSO的NUCR算法

2.1 非均匀分簇建立

1)候选簇首节点

引入能量阈值对网络中的节点进行筛选,考虑到网络能量热区问题,筛选公式引入距离因子如下

(3)

式中E(i)为节点i的当前能量,Eave为网络中节点的平均能量,w为调节系数,di为节点i到汇聚节点之间的距离。初始化时,每一个节点产生在[0,1]区间的随机数μ,只有当T(i)>μ时,节点才有机会当选为候选簇首。

2)竞争半径

通过上式筛选出的候选簇首节点的能量充足且靠近汇聚节点附近区域的簇首数量较多。为了有效均衡网络能耗,需要对网络进行合理的划分,竞争半径计算公式如下

(4)

2.2 基于改进PSO的簇首优化

将非均匀分簇阶段筛选出的候选簇首节点形成一个候选簇首集合,从中进行M次选取,每次选取K个候选簇首,最终形成M组包含K个元素的初始簇头集合,即形成含有K个元素的M个粒子。本文将从簇首能量、簇首位置2个方面建立适应度函数从而来综合评价,如式(5)所示

F=af1+(1-a)f2

(5)

式中a为权值系数,用来调整能量与位置之间的比重,a∈(0,1]。

1)簇首能量因子

簇首能量因子定义为簇首的能量平均值与全网络中簇成员节点的能量均值之比

(6)

2)簇首位置因子

由能耗模型可知,通信距离与能耗成正比。考虑到位置因素对候选簇首的影响,从以下两个方面分析：一是候选簇首在WSNs中的位置,二是候选簇首在簇内的位置。通过网络中非簇首节点到汇聚节点的距离与候选簇首分别到汇聚节点距离、簇内成员节点距离之和比

(7)

式中d(NCHi,Sink)为簇内成员节点i和汇聚节点之间的距离,d(CHj,Sink)为簇首j到汇聚节点的距离,d(NCHi,CHj)为在簇首j竞争半径范围内,簇内成员节点i到簇首节点j的距离。

算法初始时,对每一组候选簇首节点集合进行适应度计算,即计算每个粒子的适应度值。此时,适应度值最大粒子的位置作为全局最优位置,其他粒子的为局部最优位置。

2.3 速度与位置的更新

算法完成初始化参数后,开始进行迭代,更新粒子的速度和位置,再计算更新后粒子的适应度值。由于速度是矢量,WSNs布置的区域又是一个规则的平面,所以建立一个二维平面坐标系,能很好地将网络中节点的位置xid和速度vid用在x,y坐标方向上的分量表示,计算公式如下

(8)

式中w为惯性权重,起调整粒子搜索速度的作用；c1,c2分别为个体部分和群体部分的认知因子,通常取2；r1和r2为分布在区间[0,1]内的随机数,用来增加搜索的随机性。

粒子在x,y轴上的位置分量更新公式为

(9)

由于WSNs中节点是离散式分布的,在每一轮迭代结束后,候选簇首的位置被更新,但在网络中不一定能找到对应位置存在的节点,这时按照距离最近原则确定实际节点所在位置,计算公式如式(10)所示

dCMn=

(10)

式中 (CMnx,CMny)为节点CMn的坐标。

PSO簇首流程如图1所示。

图1 PSO簇首流程

2.4 改进惯性权重系数

传统PSO算法将惯性权重系数设置为固定值,无法随着算法具体运行状态的改变而变化。当粒子适应度值小时,增大粒子的搜索速度,注重寻找全局最优位置；相反,当粒子适应度较大时,降低粒子的搜索速度,重点关注局部最优位置,提高收敛精度。根据不同粒子的不同适应度值,提出了自适应的惯性权重分配策略。在每一次迭代中,计算每一个粒子的适应度值,根据粒子的当前适应度值为每个粒子分配一个惯性权重,计算公式如式(11)

(11)

2.5 自适应的学习因子

学习因子c1为粒子靠近个体最优位置的能力强弱。当c1值越大,粒子靠近个体最优的能力越强,即粒子加强对自身的思考,行为越发独立,导致粒子在搜索空间内越分散。学习因子c2为粒子靠近种群最优位置的能力。当c2值越大时,粒子靠近种群最优位置的能力越强,即加强了粒子群体意识,粒子在搜索空间上体现出更加聚集,算法收敛速度大大增强,但收敛精度下降,容易越过全局最优位置[11]。

传统PSO算法将学习因子统一设定为固定值,这不利于算法的收敛速度和精度。当粒子的适应度值越大时,表明此时粒子处于较优的位置,应加强对粒子本身的思考,反之当粒子适应度值较小时,应加强种群间的社会认知能力,具体计算公式如下

(12)

式中c1max,c2max为影响个体、种群部分的最大学习因子,在本文中均取2.5,c1min,c2min为影响个体、种群部分的最小学习因子,在本文中都均取0.5。

3 数据传输阶段

簇内成员节点直接与簇首进行通信,簇间通信则采用基于最小生成树建立的最优路径进行数据传输。采用Prim算法以汇聚节点为作为根节点,建立基于最小生成树的最优数据传输路径,由于在本文中WSNs中通信链路是对称的,建立了从汇聚节点到各个簇首的最优路径等同于各个簇首到汇聚节点的最优路径。以簇首和汇聚节点的位置构造一个带有权值的有向连通图G=(V,E),V为包含有簇首节点和汇聚节点的集合,E代表V集合中节点连线的权值。用U集合来保存最小生成树的节点,W记录待转发节点和其邻居节点连线的权值,T用来记录最小生成树的边的权值,权值计算公式如下

(13)

式中a,b,c分别为调节各部分的权重系数,a+b+c=1；dij为簇首i,j之间的距离；ei,ej分别为簇首i,j的当前能量；Si,Sj分别为簇首i,j所在簇的规模大小。

汇聚节点向全网簇首广播一个信号,各个簇首根据接收到的信号强度值确定各自到汇聚节点的大致距离。同理,簇首间相互发送信号,确定簇首间的距离。最终确定了网络中簇首与汇聚节点、簇首之间的距离。

根据Prim的最小生成树路由算法步骤如下：

步骤1 初始时将汇聚节点作为根节v0点添加到U集合中,此时U={v0},W,T为空集；

步骤2 根据权值公式计算G=(V,E)中所有边的权值并记录到W集合中,规定如果汇聚节点到某节点的距离d0i

步骤3 从根节点v0出发寻找权值最小的下一跳节点,并将找到的下一跳节点添加到U集合中,将权值最值最小所在的边添加进T集合中；

步骤4 重复步骤3,直到U=V,将集合U中的节点和集合T中的边形成一棵最小生成树。网络中的簇首节点按照最小生成树将数据传输至汇聚节点。

基于Prim算法建立的最小生成树路径忽略了各节点的负载问题,负载过高的节点能量消耗过快,使其过早失效,从而影响其他节点。在完成初始路由建立后,需要根据节点的负载情况来优化路由结构。假设有k个节点与某个节点通信,则视为该节点的负载为k,优化流程如图2所示。

图2 节点负载优化流程

4 仿真结果分析

4.1 仿真参数设置

本文采用MATLAB作为仿真工具对本文所提出的算法性能进行验证,仿真参数设置如表1所示。

表1 仿真参数

4.2 不同适应度函数权重的取值

均方差值反映一组数据的差异性,一组数据的均方差值越小,表明这组数据差异性越小,越均衡、越稳定。如图3采用不同的适应度函数权值进行迭代,根据节点剩余能量均方差值来评判权值选取的优越性。当a取值为0.5时,即能量因子和位置因子权值相同时,节点剩余能量均方差值最小,表明此时网络中的各个节点剩余能量差异最小,能量消耗越均衡,有利于延长网络的生命周期。

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

4.3 节点存活数量

由图4表明,网络中存活节点的个数随着运行轮数的增加不断减少。其中LEACH算法存活节点的减少速率最快,大约在305轮左右出现第一个节点死亡,直到1 300轮左右网络中的节点全部死亡。EEUC算法和NAPSO算法分别在400轮左右和510轮左右开始出现第一个节点死亡,直到1 480轮左右和1 700轮左右网络中的节点全部死亡。APSO-NUCR算法大约在600轮左右开始有节点死亡,比LEACH,EEUC,NAPSO分别延长了96.7 %,50 %,17.6 %,APSO-NUCR算法在2 200轮左右节点全部死亡,比LEACH,EEUC,NAPSO分别延长了69.2 %,48.6 %,29.4 %。

图4 不同路由算法的节点存活数对比

4.4 簇首能耗

如图5对比了4种路由算法的簇首能耗,由于LEACH算法在选择簇首的随机性,导致相比其他3种算法的簇首能耗要大一些,而且能耗波动较大。EEUC算法改进了LEACH的缺陷,簇间采用多跳传输数据方式,相比LEACH一定程度上缓解了簇首的能耗。NAPSO算法的簇首能耗基本上在0.02～0.05 J之间徘徊。本文APSO-NUCR算法在簇首能耗方面表现最为优秀,波动也较小,基本上在0.01～0.03 J 范围内。这是由于APSO-NUCR在簇首选举时,充分考虑到能量和簇首在网络中、簇内的位置关系,更加合理挑选出性能优越的节点。

图5 不同路由算法的簇首能耗对比

5 结 论

针对WSNs中出现的能量热区问题,本文提出一种基于自适应粒子群的WSNs非均匀分簇路由算法。通过粒子适应度值合理优化的惯性权重和学习因子,平衡全局搜索能力和局部探索能力。APSO-NUCR算法通过以能量和位置因子来评判候选簇首的性能,并确定最终簇首；建立了基于最小生成树的最优传输路径。仿真结果表明,APSO-NUCR算法能最大化利用网络能量,均衡网络中各区域的能耗,延长了网络的生存周期。