基于拟物力导向的量子粒子群优化算法的WSN节点部署研究
摘要：节点部署是无线传感器网络（Wireless Sensor Network，简称 WSN）设计的一个重要方面，它将会影响网络的有效覆盖，连通性和能耗。粒子群算法（Particle Swarm Optimization，简称 PSO）可以提高目标区域无线传感器网络的覆盖率。然而该算法在优化过程中易早熟收敛，影响覆盖的优化效果，并且算法复杂度较高。针对该问题文章在量子粒子群算法（Quantum Particle Swarm Optimization，简称 QPSO）的基础上，结合拟物力导向的思想，提出了基于拟物力导向的量子粒子群优化算法。通过仿真实验得出，该算法加快了粒子的收敛速度，提高了 WSN 的覆盖率，同时算法的复杂度降低。
关键词：无线传感器网络；节点部署；量子粒子群，拟物力导向中图分类号：TP18；TP212.9；TN929.5 文献标识码：A 文章编号：1673-1131（2015）10-0032-03.
0 引言
无线传感器节点部署是使用各种算法合理部署检测区域的节点，提高无线传感器网络对待监测区域中目标的感知效果，最大化网络的覆盖率，最小化能耗，延长网络的生命周期。
利用粒子群算法可以提高网络的覆盖率，然而粒子群算法在空间搜索时，易陷入早熟现象。文献[1]提出了基于量子粒子群算法的移动节点覆盖优化，克服了粒子群算法易陷入局部最优的缺点，优化了覆盖效果。文献[2]提出了基于混沌粒子群算法的无线传感器网络覆盖优化，利用混沌运动的随机性和遍历性，解决已陷入局部最优的群点。文献[3]提出基于改进自适应 PSO 算法的 WSN 覆盖优化方法，提高了 WSN 的覆盖率。然而使用上述提出的算法，粒子在空间搜索过程中存在收敛速度慢、算法复杂度高等问题。
本文在量子粒子群算法的基础上，结合拟物力导向的思想，提出了基于拟物力导向的量子粒子群优化算法。
1 标准 PSO 算法和 QPSO 算法
1.1 标准 PSO 算法
1995 年，Eberhart and Kennedy 基于社会仿真模型提出了粒子群算法作为全局随机优化算法。PSO 算法的核心思想是利用搜索粒子群在优化问题的搜索空间区域随机移动，其思想来源于人工生命和进化计算理论,是一种优化算法，特点是模拟鸟的群体智能，以求解连续变量为优化背景。随着粒子群算法的不断改进，称带惯性因子的粒子群算法为标准粒子 群算法。
根据文献[4]，在迭代过程中，粒子群根据下列公式更新其速度与位置：
其中：i=1，2，…，m；d=1，2，…，n，d为目标搜索空间当前维数；k 为当前迭代次数；r1，r2 为[0,1]内服从均匀分布的随机数；c1，c2 为人为设定的学习因子，一般情况下，c1=c2=2，w 是惯性系数，w 的计算公式为：
（3）算法在区域中进行搜索的时候，很容易陷入局部最优，这样在一定程度上就限制了粒子的搜索程度，进而会影响覆盖率。
1.2 QPSO 算法
QPSO 算法是孙俊等人从量子力学的角度提出一种新的PSO 算法。在量子粒子群中，引入占势降，假设粒子在以点为中心的占势降中，因为粒子的速度和位置在量子空间中不能一起确定，所以粒子的状态用波函数 (其物理意义为：
波函数的平方是粒子在空间某一点出现的概率密度)来描述粒子的状态，并通过求解薛定谔方程得到粒子在空间某一点出现的概率密度函数。随后通过蒙特卡罗随机模拟的方式得到粒子的位置方程为： 式中：——收缩扩张系数，M ——粒子的数目，D ——粒子的维数，Pi ——第i 个粒子的 。最后得到粒子的位置方程为:
（7）量子粒子群算法比经典的粒子群收敛性能好，然而在处理高维复杂函数时收敛速度慢，并且易陷入局部极小。
2 拟物力导向的量子粒子群算法
拟物力算法最早是由黄文奇提出并利用，在文献[5]中，作者利用“拟万有引力”和“拟库仑力”两种拟物策略，优化 WSN节点部署问题。
2.1“拟万有引力“模型
按照文献[5]提出的万有引力模型，定义第 k 个“质点”vk对第 i 个“圆盘”Si 的“拟万有引力”函数如下[54]：
（8）其中djk表示“质点“和”圆盘“圆心之间的距离，rj2 充当”圆盘“的质量， 表示只有未被覆盖的“质点”才能对“圆盘”
产生引力，Rj>djk>rj 限制了引力的Ｓ作用范围。
2.2“拟库仑力”模型
按照文献[5]提出的“拟库仑力”,可以定义“圆盘”之间相互排斥的“拟库仑力”函数为[4-5]：
（9）其中 ri2 和 rj2 充当“圆盘“所带电量，dij 表示两个”圆盘“圆心之间的距离，dij<min{Ri，Rj}将排斥力的作用范围局限在邻居节点之间。
2.3 拟物力导向的量子粒子群算法
为加快粒子群的收敛速度，提高节点部署的覆盖率，本文将“拟万有引力模型”和“拟库仑力模型”结合量子粒子群算法，提出拟物力导向的量子粒子群算法。拟物力导向的量子粒子群算法中粒子的位置方程如下：
其中 0 为 的初始值，一般 0=1，1 为 gn 作用下的权重；2为 cn 作用下的权重。
gn 表示“拟万有引力”作用因子，计算如式如下：
Cn 表示“拟库仑力”作用因子，计算公式如下所示： 2.4 拟物力导向的量子粒子群的算法流程Step1：初始化种群；Step2：根据式(6)计算种群的平均最好位置 mbest;Step3：每个粒子的适应值与粒子个体最好位置 Pi 比较，若前者较好，则将其作为当前个体的最好位置；Step4：每个粒子的适应值与全局最好位置 Pg 比较，若前者较好，将其作为全局最好位置；Step5：根据拟物力导向量子粒子群算法的方程（10）计算粒子的新位置；Step6：判断周围是否完全覆盖,引入“拟万有引力”和“拟库仑力”z 作用因子;Step7：重复步骤 1-6，直至满足条件，然后结束。
3 仿真实验结果
3.1 实验设置
假设监测区域是边长为 20m 的正方形，在区域中部署了 20 个无线传感器节点，节点的感知半径为 2.5m，通信半径为 5m，0=1，maxnumber=400。采用主频为 1.73GHZ 的计算机在 Matlab 环境下仿真无线传感器网络覆盖优化。
3.2 算法性能分析
图 1 为初始节点布局，从图中可以看出节点分布不均匀，并且存在较多的覆盖盲区，覆盖重叠率很高。图 2 为使用粒子群优化后节点布局，明显可以看出，节点分布相对均匀，覆盖盲区减少。图 3 为基于拟物力导向的量子粒子群算法节点布局，节点分布更为均匀，覆盖重叠率相对减少许多。
4 结语
本文在量子粒子群的基础上，结合拟物力导向的思想，提出了基于拟物力导向的量子粒子群算法。该算法在量子粒子 群的优化函数中，引入了拟万有引力作用因子和拟库仑力作用因子，改进了量子粒子群的收敛扩张系数。仿真结果表明，该算法相比量子粒子群算法，避免了易陷入局部极小的问题，加快了算法的收敛速度，提高了算法精度，有效地改进了网络的覆盖率。
参考文献：
[1] 王建华,史明岳,王婷婷.基于量子粒子群算法的移动节点覆盖优化[J].微电子学与计算机,2012,29(6):96-99.
[2] 刘维亭，范洲远. 基于混沌粒子群算法的无线传感器网络覆盖优化[J].计算机应用,2011,31(2):338-340.
[3] 宋明智,杨乐. 基于改进自适应 PSO 算法的 WSN 覆盖优化方法[J].计算机应用研究,2013,30(11):3472-3475.
[4] Aziz N A B A,Mohemmed A W,Daya S B S.Particle SwarmOptimization and Voronoi Diagram for WirelessSensor Networks Coverage Optimization Intelligent and Advance Systems[C]//Proc.of ICIAS’07.Kuala Lumpur,Malaysia:[s.n.],2007.
[5] 程爱华,葛宝忠,季中恒.无线传感器网络区域覆盖的拟物
