QPSO在无线网络位置优化中的应用

高 薇

（闽南理工学院 信息管理学院，福建 石狮362700）

粒子 群 优 化 算 法 （particle swarm optimization，PSO）是一种全局优化算法，因其流程简单，能够在群体较小的情况下快速收敛，在图像处理和数值优化等领域得到了广泛应用［1-3］。随着物联网设备的广泛部署和发展，作为物联网研究领域的重要研究内容之一，位置服务受到了国内外研究者的广泛关注。但是，目前基于几何方法的位置计算误差较大，因此许多研究者都引入智能优化算法对位置信息进行优化，以尽可能减小位置信息的误差。

大多数物联网设备都有低功耗的特点，故如何利用计算量较小的算法进行位置优化，并且将这些算法嵌入到低功耗芯片中直接计算成为利用智能算法进行位置优化的技术瓶颈之一。粒子群算法具有能够在种群规模较小的情况下快速收敛的特点，因此利用粒子群及其相关改进算法进行位置优化成为基于智能优化的位置服务领域的优先选取的技术之一。

标准粒子群算法已经被证明不能在所有问题的解决过程中都收敛于全局最优解，故孙俊在文献［3］中提出了一种具有量子行为的粒子群算法（quantum particle swarm optimization，QPSO），与标准粒子群算法相比，QPSO不再利用实数位置初始化种群，而是利用粒子位置的分布模型对位置进行初始化，增加了位置的不确定性，提高了全局搜索能力。另外，QPSO利用随机采样的方式对群体进行更新，提高了粒子群的收敛速度。如何将粒子群算法引入到位置信息优化问题中来尽可能降低位置优化的能耗是目前亟待解决的重要问题之一，并由此产生了很多改进版本的量子粒子群算法，如文献［4-10］中提到的算法。

针对上述问题，笔者提出了基于量子粒子群算法的无线网络位置优化方法，并以DV-Hop算法的优化问题为例对基于QPSO的位置优化算法进行了仿真。

1 DV-Hop基本原理及误差分析

1.1 DV-Hop算法原理

DV-Hop算法是利用无线传感器网络节点之间的路由关系，通过信标节点的位置信息来推断未知节点的位置信息的。DV-Hop算法的主要步骤如下：

1）计算未知节点到所有锚节点（包括信标节点和未知节点）之间的最小跳数。每个信标节点都广播自己的位置信息，而周围节点收到广播信息后，就按照最小跳数原则更新自己的路由表，更新后再将信息继续广播到邻居节点。这样，每个节点都记录了到所有信标节点的最小跳数。

2）计算平均跳距。平均跳距主要是根据信标节点之间的跳数-距离关系推导的计算方法为

其中，hj表示信标节点i到信标节点j的最小跳数，（xi，yi）和（xj，yj）分别表示信标节点 i和 j的位置信息，i≠j。信标节点将平均跳距信息通过广播的方式传递给未知节点，未知节点u通过

计算自己与信标节点 i之间的估计距离。式（2）中 tu，i是未知节点u和信标节点i之间的最小跳数。

3）计算未知节点的位置坐标。若未知节点能与3个信标节点连通，则采用三遍测距法估算未知节点的位置信息。假设未知节点的坐标信息为（x，y），附近3个信标节点的坐标分别是（xA，yA）、（xB，yB）和（xC，yC），则未知节点和信标节点的位置关系可用

表示。

为了提高节点的定位精确度，假设周围有n个锚节点，则未知节点与信标节点的关系为

由以上步骤可以看出：影响DV-Hop算法精确度的主要参数是未知节点到信标节点的估计距离di。下面分析DV-Hop误差的量化结果，讨论如何利用量子粒子群算法提高di的精确度。

1.2 DV-Hop算法误差分析

DV-Hop算法的主要误差是由平均跳距引起的。为了测量平均跳距引入的误差大小，选取节点分布面积为100 m×100 m，节点总数为100，锚节点数为20，通信半径R为30 m，求得实际跳距和估计跳距之间的距离差，如图1所示，误差的分布情况如图2所示。从图1中实际跳距和估计跳距的差值的绝对值可以看出估计跳距与实际跳距具有2~14 m的误差。若有多个信标节点，则引入的累积误差更大，加之最小二乘法还会引入额外的误差，导致DV-Hop算法的实际误差可能达到30%。因此，如何利用轻量级的智能优化算法对DV-Hop算法进行位置信息优化具有重要的意义。

下面主要分析如何利用量子粒子群算法对DVHop算法进行位置优化以及位置优化的性能。

图1 实际平均跳距和估计平均跳距的对比

图2 跳距误差的分布情况

2 QPSO算法的基本原理

QPSO是将量子力学粒子运动的基本原理引入粒子群算法提出的一种更易收敛于全局最优解的优化算法，与PSO算法的主要区别是：QPSO利用波函数代替PSO中用实数表示的粒子位置，用薛定谔方程取代PSO中的速度定义来定义粒子的位置变化方法。粒子的位置计算方法为

其中：p是通过薛定谔方程得到的粒子在空间任何一个位置出现的概率密度函数；u是［0,1］之间的随机数；L为势阱的特征长度，计算方法为

式（7）中，m=1，n=0.5，K 为最大迭代次数。

QPSO的位置更新方程为

其中：d表示第i个粒子的位置；u为［0，1］之间的随机数；mb（t）为种群在第t次迭代中的平均最佳位置，计算方法为

pid（t）的计算方法为

其中pgd（t）为t时刻的全局最优解。通过上述方法就可以在所有粒子群中找到最优化的未知节点位置。

3 QPSO-DV-Hop算法设计

假设未知节点k附近一跳范围内的锚节点有m个，节点k可以通过接收信号强度估计距离锚节点t的距离。估计方法为

进而得到

要对未知节点k进行优化，就需要对任意粒子i到达锚节点t的距离与估计距离hk，t的误差进行最小化处理。假设粒子群的大小为N，目标函数的定义为

其中，（xi1，xi2）为粒子i的初始坐标，（xt1，xt2）为锚节点 t的坐标，利用目标函数调整粒子的坐标值和速度值，直到达到迭代次数或者满足性能要求为止。

4 仿真实验及结果分析

为了验证QPSO算法的性能，下面对基于QPSO的DV-Hop算法进行分析，主要包括对比算法介绍、仿真实验参数设置以及仿真实验结果分析等。

4.1 对比算法和参数设置

本文将基于QPSO算法的性能与传统的DV-Hop算法、基于标准PSO的改进型DV-Hop算法进行了比较，这三种算法的参数设置如表1所示。

表1 实验参数设置情况

如表1所示，本文所提出的算法和传统的DVHop算法的参数设置均为：节点的分布面积为100 m×100 m；总节点数目为100个，其中有20个信标节点，80个未知节点；通信半径为30 m。其中种群大小为40个、最大迭代次数为100次，粒子的坐标变化范围是-100~100 m。

4.2 仿真实验结果分析

根据表1的参数对节点进行随机部署，仿真结果如图3所示。在图3所示的分布情况下统计了DVHop算法、PSO-DV-Hop算法以及QPSO-DV-Hop算法的定位误差 （图4），同时分析了PSO算法和QPSO算法的收敛性能（图5）。

从图3可以看出，仿真实验中节点的分布具有随机性，与实际的实验环境相符，仿真实验结果具有现实参考意义。

从图4可以看出：基于PSO算法和QPSO优化的算法的定位误差比传统的DV-Hop算法的定位误差小。基于PSO算法的定位误差与基于QPSO算法的定位误差相差不大。

图3 节点的分布情况

图4 DV-Hop算法、PSO-DV-Hop算法以及QPSO-DV-Hop算法的定位误差分析

图5 PSO算法和QPSO算法的收敛性能分析

从图5可以看出，在PSO-DV-Hop算法和QPSODV-Hop算法定位误差相当的前提下，QPSO算法经过10次迭代就达到了收敛，收敛速度较快，而PSO算法要经过50次迭代，且这种差距在节点规模越大的情况下会表现得越明显。

上述实验结果表明：基于QPSO算法的DV-Hop算法优化方式在保证定位精确度的前提下，由于迭代次数减少，降低了节点的计算量，适用于计算能力较低的传感器中。

5 结论

本文针对基于PSO的位置优化算法定位能耗较高的问题，引入了基于QPSO的定位优化算法，并以DV-Hop算法的优化为例进行了性能分析。分析结果表明：基于QPSO的定能算法能够快速收敛，其收敛速度是基于PSO算法的5倍左右，减小了计算量，适用于计算能力较低的传感器节点。