基于改进混合粒子群优化算法的移动节点部署研究*

朱正伟， 刁小敏， 郭 晓， 刘 晨

0 引 言

覆盖率是衡量无线传感器网络(wireless sensor networks,WSNs)[1]质量的重要指标。在WSNs中，数据采集节点分为静态节点和移动节点。移动节点部署能够在初始随机部署后，改变网络的拓扑结构，实现网络自组织，提高网络的覆盖质量。

Mateska A等人[2]设计了一种分布式算法用于提高网络连通性和网络覆盖率。刘继忠等人[3]提出了免疫粒子群算法通过在部署区域给定传感器节点数量，最大化网络覆盖率和在区域具有所需覆盖率的传感器节点数目最小化。周剑波等人[4]提出了一种虚拟力扰动指数权值递减型粒子群算法，用于加快算法收敛速度，提高覆盖率。袁曦等人[5]提出了改进蝙蝠算法，改善传感器节点的覆盖密度，使得分布相对比较均匀。

基于粒子群优化(particle swarm optimization,PSO)算法[6～10]的WSNs覆盖应用研究较多。本文将模拟退火算法[11，12]和改进粒子群优化算法[13]相结合即改进混合粒子群优化 (improved hybrid PSO,IM-HPSO) 算法优化移动节点的部署。同时在建立传感器节点部署模型时同时考虑了网络覆盖率和节点的移动能耗即多目标函数[14,15]，提高了网络服务质量。

1 传感器节点部署模型

移动传感器节点感知模型采用概率感知优化模型。

定义移动节点部署区域为W×W的二维区域并将其网格化，假设在该区域随机部署N个移动节点(N=n1,n2,…,ni,…,nN)，每个移动节点感知半径为R，通信半径为2R，以确保网络的连通性。移动节点ni覆盖二维区域的目标点Tj的概率如下

(1)

式中rθ为移动节点检测误差的范围;Ei0为节点初始能量大小;Eis为节点剩余能量大小;λ，β，β′为由传感器节点的物理特性决定的性能参数;α=D-(r-rθ)，α′=(r+rθ)-D;D(ni,Tj)为传感器节点ni=(xi,yi)到目标点Tj=(xj,yj)的距离

(2)

由于移动节点部署WSNs(mobile WSNs,MWSNs)由N个移动节点组成，则目标点Tj被所有移动节点覆盖概率为

(3)

WSNs在二维平面区域Q的覆盖率为

(4)

(5)

IM-HPSO算法通过重新调整位置来提高MWSNs的覆盖率，假设节点移动单位距离所需能量相同，移动距离为节点从初始位置移动到目标位置之间的距离，则MWSNs中网络能耗主要指所有移动节点的移动距离之和与单位距离消耗能量的乘积 ,即

(6)

式中k为单位距离能耗系数;D(ni,di)为移动节点ni从初始位置移动到最终位置di之间的线性距离。

在MWSNs节点部署模型中，设f为适应度函数，函数值设置为高覆盖率和少的能量消耗，公式如下

f=w×PC(N,Q)+(1+w)EN

(7)

式中w为无线传感网覆盖率和网络能耗在该函数中所占比重。

2 基于IM-HPSO算法的移动节点部署

2.1 IM_HPSO算法

1)改进粒子群算法

自适应权重粒子群算法根据粒子位置来改变权重系数，避免粒子的局部最优问题，权重系数变化如下

(8)

式中w为变化的惯性权重；wmax为粒子惯性权重的最大值；wmin为粒子惯性权重的最小值；f为当前粒子的适应度函数值；fmin为种群的最小函数值；favg为种群的平均函数值。

在自适应权重PSO算法中，引入收缩因子φ

(9)

φ用于改变粒子的速度，调整粒子的位置，实现局部最优和全局最优之间的平衡，避免算法陷入早熟收敛，粒子的速度和位置更新公式为

xij(t+1)=xij(t)+vij(t+1)

(10)

vij(t+1)=φ{w×vij(t)+c1r1(pbestij(t)-xij(t))+

c2r2(gbestij(t)-xij(t))}

(11)

式中vij(t+1)为第i个粒子在t次迭代后的速度；vij(t)为粒子当前的速度;c1，c2为学习因子，取2左右的随机数;pbestij(t)为第i个粒子在第t次迭代时的个体极值;gbestij为第i个粒子在第t次迭代时的全局极值。

为了进一步保持种群中粒子多样性，在自适应权重粒子群算法中融入自然选择操作机理。按照粒子群更新之后的函数值大小排序，用函数值较好的粒子根据比例进行替换函数值较差的粒子，并记录每个粒子的历史个体最优值。

2)模拟退火算法

3)IM-HPSO算法

将SA算法引入改进PSO算法提出了IM-HPSO。当粒子群陷入局部极值时，该算法能够根据Metropolis准则以一定的概率修改该极值，从而继续搜索，跳出局部极值，寻找整体最优解。

由式(11)可知，算法采用了全局最优位置，粒子群所有个体向该位置靠近，此时，如果处于局部极小值，则所有粒子陷入局部极值，导致种群全局搜索能力变差，根据IM-HPSO算法，能够根据Metropolis准则以一定的概率修改该局部极值,则概率如下

(12)

式中f(pi)为当前粒子的最优目标函数值;f(g)为粒子群最优目标函数值。

vij(t+1)=φ{w×vij(t)+c1r1(pbestij(t)-xij(t))+

xij(t))}

(13)

因此，IM-HPSO算法能够跳出局部极值，继续搜索，寻找全局最优解，提高算法的收敛速度，避免陷入局部最优以及早熟收敛。

2.2 移动节点部署策略

策略如下：

1)根据式(1)～ 式(7)，在WSNs移动节点模型中定义适应度为网络覆盖率以及能量消耗的多目标函数。

2)确定种群数量M，随机分布各个粒子群体。

3)通过适应度函数评价每个粒子的适应度值，确定粒子的个体最优值pbest，以及从所有个体最优中选择全局最优值gbest。

4)确定初始温度

t0=f(pbestij(t))/ln 5

(14)

5)根据式(12)确定当前温度下各粒子的适应值。

6)从适应值中选择全局最优值的替换值 ，根据式(8)～式(13)更新各粒子的位置，速度和权重。

7)计算各个粒子新的适应度，并与个体最优值比较，再与全局最优值比较，更新结果。

8)按照更新后的适应值大小来排序，适应值较好的粒子根据比例替换适应值较差的粒子，并记录每个粒子的历史个体最优值。

9)退温操作，退温方式为

tk+1=mtk,m∈(0,1)

(15)

10)当迭代次数达到设定值或者连续若干解未被接受，输出MWSNs节点部署最优位置，WSNs覆盖率以及能量消耗;否则,返回步骤(4)。

3 仿真结果

在MATLAB R2014a仿真工具上进行实验。设置待部署区域为40×40的网格点，初始时随机部署40个移动节点，传感器节点的参数设置如下：传感半径R=4，通信半径2R=8，λ=1，rij=0.8，β=1，β′=0.5。

为了消除算法的随机性，每次仿真运行10次，计算结果的平均值。算法参数值设置如下:种群数目为M=100，c1=c2=2，wmax=0.8，wmin=0.6，迭代次数为300，初始能量Ei0=0.5 J。

覆盖模型为以“*”为传感器节点位置，r为半径的圆形区域，覆盖率为圆形区域所占面积在矩形区域所占比例，初始时刻随机分布的传感器节点如图1(a)所示。

在传感器节点部署模型下，应用IM-HPSO算法进行MWSNs的传感器节点部署，则最终节点部署如图1(b)所示。

图1 IM-HPSO算法节点布置

从图1对比，可以看出:覆盖率得到大幅地提升。为了评估文中算法的覆盖效果和能耗，在相同情况下，将IM-HPSO算法与量子PSO (quantum PSO,QPSO) 算法和 PSO 算法进行对比，结果如表1和图2。

表1 覆盖率和移动能耗对比结果

从表1看出，IM-HPSO算法的移动距离少于QPSO和PSO算法，从而IM-HPSO算法的移动能耗少于QPSO算法，QPSO算法的移动能耗少于PSO算法。

图2 不同算法的覆盖率对比

从图2可以看出，初始时，覆盖率提升较为明显，随着迭代次数的增多，覆盖率提升较为缓慢，迭代200次后，逐渐趋于稳定。初始时， QPSO算法覆盖率提升幅度大于PSO算法，且收敛性能优于PSO算法，而IM-HPSO算法覆盖率提高幅度优于QPSO算法，且收敛性能优于QPSO算法。当迭代300次后，IM-HPSO算法覆盖率为90.83 %，QPSO算法覆盖率为85.89 %，PSO算法覆盖率为78.97 %。结果表明：在提高网络覆盖率及收敛性能方面，IM-HPSO算法均优于QPSO算法和PSO算法。

综上，IM-HPSO算法的覆盖率和网络能耗优于其他2种算法。

在相同网络环境，对比IM-HPSO算法的网络生命周期与另外2种算法进行了对比，结果如图3所示。

图3 存活节点数对比

图3显示了3种算法运行200轮时的存活节点数对比。由于存活节点数受剩余能量的影响，说明存活节点数越多，剩余能量越多，能量消耗越少，网络生命周期越长。从图中可以看出：初始时，在相同轮数时，QPSO算法存活节点数多于PSO算法，PSO算法稳定运行80轮，存活节点数开始衰减，而QPSO 算法稳定运行123轮，存活节点数才开始衰减，说明QPSO在相同模型下，算法性能优于PSO算法，但随着运行轮数的增加，QPSO算法能量消耗较多，存活节点数较小，后期衰败较快。而IM-HPSO能够稳定运行131轮，网络生命周期为182轮。结果表明，IM-HPSO算法在能耗，网络覆盖率，网络生命周期方面均优于QPSO算法和PSO算法。

4 结 论

通过减少移动节点的移动距离减少网络能量消耗。仿真结果表明：IM-HPSO算法可达到较高的覆盖率，较低的移动消耗，并延长网络生命周期。未来将在此基础上结合其他群智能算法进行优化，进一步提高MWSNs覆盖率等。

参考文献:

[1] Abo-Zahhad M,Sabor N,Sasaki S,et al.A centralized immune-Voronoi deployment algorithm for coverage maximization and energy conservation in mobile wireless sensor networks[J].Information Fusion,2016,30(C):36-51.

[2] Mateska A,Gavrilovska L.WSNs coverage & connectivity improvement utilizing sensors mobility[C]∥Wireless Conference 2011—Sustainable Wireless Technologies,2011:1-8.

[3] Liu J Z,Wang B L,Ao J Y,et al.An immune-swarm intelligence based algorithm for deterministic coverage problems of wireless sensor networks[J].Journal of Central South University,2012,19(11):3154-3161.

[4] 周剑波,刘宏立,徐 琨.一种结合粒子群和虚拟力的动态节点部署策略[J].计算机工程与应用,2016,52(10):118-123.

[5] 袁 曦,张曦煌.基于改进蝙蝠算法的无线传感器网络的移动节点部署[J].传感器与微系统,2016,35(3):144-146.

[6] 王 霞,陈 洁.混合无线传感器网络节点覆盖优化[J].计算机仿真,2013,30(4):204-207.

[7] 陈乐瑞，潘秋萍，李甜甜.基于遗传粒子群的微机运动网络优化研究[J].自动化技术与应用，2016,35(8)：13-17.

[8] 王建华,史明岳,王婷婷.基于量子粒子群算法的移动节点覆盖优化[J].微电子学与计算机,2012,29(6):96-99.

[9] 艾 兵,董明刚.基于高斯扰动和自然选择的改进粒子群优化算法[J].计算机应用,2016,36(3):687-691.

[10] 谢世龙，周玉国，刘 真.一种基于神经网络的粒子滤波算法设计[J].自动化技术与应用，2017,36(11)：1-4.

[11] 岳 翀,熊 芝,薛 彬.基于模拟退火—粒子群算法的wMPS布局优化[J].光电工程,2016,43(7):67-73.

[12] 黄 炯,艾剑良,万 婧.基于模拟退火粒子群算法的飞机气动参数辨识[J].复旦学报:自然科学版,2016,55(3):336-341.

[13] 丁婷婷，高美凤.改进粒子滤波的无线传感器网络目标跟踪算法[J].传感器与微系统，2016,35(7)：140-142.

[14] Luo C Y,Chen M Y,Li H.Advances in swarm and computational intelligence[M].Berlin Haidelberg:Springer International Publishing,2015:479-486.

[15] Tian J,Gao M,Ge G.Wireless sensor networks node optimal coverage based on improved genetic algorithm and binary ant colony algorithm[J].Eurasip Journal on Wireless Communications & Networking,2016,2016(1):1-11.