基于自适应粒子群优化算法的节点定位研究

王洪元 焦筱悛 王天成

(常州大学，江苏 常州 213164)

无线传感器网络是由大量小型低功耗、低成本并具有感知、计算和通信功能的传感器组成的[1]，通过无线通信方式形成一个自组织网络系统，现已被广泛应用于环境监测、军事应用及科学研究等领域。无线传感器网络最基本的功能之一是适时地获知事件发生的位置信息或获取信息的节点位置。比如，矿井人员定位系统及公共交通管理系统等应用中需要获取位置信息。所以说节点定位技术是无线传感器网络在应用中的关键技术之一[2,3]。

无线传感器定位可分为基于测距的定位算法和无需测距的定位算法，其主要区别在于是否需要距离信息。基于测距的定位算法中节点需使用测距技术获得距离信息，优点是定位精度高但需要额外的硬件设备，常用的测距技术有接收信号强度RSSI、信号到达时间TOA、信号到达时间差TDOA及信号到达角度AOA等；无需测距的定位算法仅依靠相邻节点间的连通关系进行定位，无需基础网络设施的支持，但定位精度较低[4]。

传统的节点定位算法常采用最小二乘法求解非线性方程组，很容易受到测距误差的影响。为了进一步提高定位精度，笔者将自适应策略引入到粒子群优化节点定位算法中，有效地克服了粒子群优化(Particle Swarm Optimization,PSO)算法容易产生种群的趋同效应，出现早熟收敛、易陷入局部极值、在搜索后期停滞不前而导致种群的优化性能不佳的问题。

1 粒子群优化算法①

粒子群优化(Particle Swarm Optimization,PSO)算法是由Kennedy和Eberhart在1995年提出的。PSO算法是一种模拟鸟群迁徙和觅食行为的群体智能全局随机优化计算方法，通过种群中个体间的竞争与协调，搜索复杂空间的最优解。PSO算法将种群中的每个个体看成一个质量和体积都为零的粒子，粒子根据自身历史最优位置和种群历史最优位置不断更新自身的速度和位置，从而实现进化[5]。

在PSO算法中，种群中共有N个粒子，每个粒子可以看成优化问题在D维搜索空间的一个潜在解。每一个粒子都有一个由目标函数决定的适应度值，该值的大小决定了粒子的优劣程度。通过所有粒子的适应度值可以判定出每个粒子的自身最佳位置和全局最佳位置，同时每个粒子还有一个决定其飞行方向和距离的速度。所有的粒子以一定的规则在搜索空间中搜索最优解。每次迭代时，粒子通过局部极值和全局极值来更新自己的信息。局部极值就是粒子本身到目前为止所找到的最优位置，而全局极值就是整个种群到目前为止所找到的最优位置。假设一个种群有N个粒子随机地分布在D维搜索空间中，其中第i个粒子在搜索空间中的位置向量可表示为：

Xi=(xi1,xi2,…,xiD),i=1,2,…,N

(1)

第i个粒子的飞行速度向量可表示为：

Vi=(vi1,vi2,…,viD),i=1,2,…,N

(2)

第i个粒子到目前为止搜索的局部极值表示为：

Pbest=(pi1,pi2,…，piD),i=1,2,…,N

(3)

整个种群的全局极值可表示为：

gbest=(pg1,pg2,…,pgD)

(4)

每个粒子按如下公式更新自己的速度向量和位置向量：

(5)

(6)

式中c1、c2——加速因子，根据经验通常都取2；

k——迭代次数；

rand()——在(0,1)范围内的随机数；

ω——惯性权重。

式(5)右边可分为3个部分，第一部分称为“惯性部分”，反映粒子维持先前速度的程度；第二部称为“认知部分”，反映粒子本身历史最佳位置对现在的影响；第三部分称为“社会部分”，反映种群对粒子的影响，粒子有向全局最佳位置靠拢的趋势。为了防止粒子飞出搜索空间，通常对粒子的速度进行一定的限制。

在PSO算法中存在粒子向种群全局历史最佳位置和自身局部历史最佳位置聚集时容易产生种群趋同效应的现象，并导致早熟收敛、易陷入局部极值、在搜索后期停滞不前而导致种群的优化性能不佳的问题，同时，PSO算法的优化性能还依赖于参数的取值情况。为克服这些不足，文献[6]提出了用指数变化的惯性权重取值方法来优化复杂的非线性方程组，笔者在此基础上进一步简化算法，提出了一种基于自适应策略的粒子群优化节点定位算法，该算法从惯性权重和全局最优位置两个方面对原有的PSO算法进行改进，实现了在不增加额外硬件的条件下对无线传感器网络节点定位在定位精度和计算耗时上的进一步优化。

2 自适应策略

笔者提出的基于自适应策略的改进算法主要包括两个方面:一是惯性权重的自适应取值方法；二是从适应度值进行改进的全局最优位置的自适应变异操作。

2.1 惯性权重的自适应取值方法

惯性权重ω是PSO算法中最重要的改进参数，其反映了粒子先前的飞行速度对现在值的影响。当其取值较大时，全局搜索能力强，收敛速度快，但缺点是得到的解精度不够；当取值较小时，局部搜索能力强、得到的解的精度高，但存在收敛速度较慢且可能陷入局部极值的缺点。合适的ω值能够平衡算法的全局搜索能力和局部搜索能力，从而得到最佳的优化解。

笔者提出的自适应的惯性权重取值方法，其设计思想主要有两个过程：在定位算法迭代前期ω取较大值，实现快速收敛到最优解附近，后期则取较小值求高精度解；同时该算法在适应度值越大时全局搜索能力越高，从而加快向全局最优位置的聚集速度，粒子适应度值较小时局部搜索能力越高，从而得到高精度的解。笔者提出的惯性权重的自适应取值公式如下：

(7)

其中当ω2>ω1时，一般取ω1=0.3、ω2=0.8，T为当前迭代次数，Tmax为最大迭代次数。为了防止ω(i)在迭代后期取值过小，笔者对ω(i)的值设置了下限0.2，当ω(i)低于下限值时ω(i)=0.2。f(i)为第i个粒子的适应度值，fmax、fmin为所有种群中粒子适应度值的最大值和最小值，相应的粒子速度更新公式变为下式：

(8)

2.2 全局最优位置的自适应变异操作

粒子的适应度值可以反映粒子当前位置的优劣程度，把种群所有粒子的当前适应度值看作一个样本，这个样本的方差就可以用来定量描述整个种群的聚集程度。种群越密集，表明整个种群的群居搜索能力变差，此时就需要对全局最优位置进行变异操作，保证整个种群能跳出当前的搜索区域。粒子群的种群适应度值方差δ2的计算公式为：

(9)

其中favg为种群中所有粒子适应度值的平均值；F为归一化因子，通常F=max(1,|f(i)-favg|)。其全局最优位置发生变异的概率计算公式如下：

(10)

其中pmax、pmin分别为gbest进行变异操作概率的最大值和最小值，通常取pmax=0.4，pmin=0.3。全局最优位置变异操作的公式为：

gbest_k=gbest_k(1+0.4η),η∈N(0,1)

(11)

通过增加一个随机扰动来对gbest进行变异操作，其中gbest_k是gbest的第k维分量。

2.3 基于自适应策略的节点定位流程

(12)

其值越小，对该点的定位就越精确。节点定位的具体流程如下：

a. 在搜索空间(目标区域)随机部署一定数目的锚节点和未知节点，节点启动后锚节点以周期T向相邻节点发送自己的信息(主要包括节点ID、位置信息)；

b. 未知节点根据邻居连通锚节点的相关信息和RSSI模型公式计算出自身到锚节点间的距离；

c. 存在邻居连通锚节点的未知节点在自身处运行笔者改进后的PSO算法，计算自身定位结果。

3 实验仿真

在MATLAB R2008a中对基于自适应策略的粒子群优化节点定位算法的性能进行验证，并与常用的极大似然估计(Maximum Likelihood，ML)进行对比分析。

在本实验中，假设无线传感器节点部署在100m×100m的二维平面区域中，在此区域内随机分布5个传感器节点，其中4个为锚节点，其坐标分别为A(22.23,48.64)、B(62.48,2.46)、C(44.60,80.42)、D(85.22,70.48)，未知节点的实际坐标为E(82.24,46.32)。

基于自适应策略的粒子群优化定位算法中的参数设置为：ω1=0.3、ω2=0.8，pmax=0.4，pmin=0.3，ω(i)min=0.2，c1=c2=2。种群粒子总数大小N=30，总的迭代次数T=100，粒子每维最大位置为100m，最大速度为10m/s。为了减少实验中随机误差的干扰，进行100次定位实验得到最终的实验数据。在无线传感器节点定位过程中，测距误差直接决定着定位的进度和稳定度。因此，本实验以测距误差作为实验的前提条件，在不同测距误差的条件下比较ML算法和笔者算法的性能优劣。在引入相同测距误差的条件下，分别对两种算法做100次的定位运算，并在不同测距误差的情况下，重复进行上述定位运算。两种算法定位结果分别见表1、2。

表1 ML算法的定位结果

表2 笔者算法的定位结果

图1、2分别反映了测距误差对平均定位误差和定位方差的影响，图3为适应度值与迭代次数的关系。

图1 测距误差对平均定位误差的影响

图2 测距误差对定位方差的影响

图3 适应度值与迭代次数的关系

通过实验数据可以得到：

a. 从图1可看出，在给定的5种测距误差条件下，笔者算法的平均定位误差要比ML算法小，说明该算法的定位精度要高于ML算法的。从图2可以看出，笔者算法的定位方差要比ML算法小，说明该算法的稳定性要高于ML算法的。

b. 从图1、2可以进一步发现，当系统测距误差较小时，两种定位算法的性能相差无几，但随着距离误差变大，笔者算法的优良定位性能就凸显出来，说明该算法在一定程度上可以减轻测距误差对定位精度的影响。

c. 图3是笔者算法在测距误差为5%时的一次定位过程，从图中可以看出算法在迭代不到10次时就可以收敛到一个精度较高的优化解，收敛速度较快，能耗较低，适合应用在对能耗有较高要求的无线定位系统中。

4 结束语

笔者针对基本粒子群优化算法在无线传感器网络定位中的不足之处，在文献[8]中用指数变化的惯性权重取值方法来优化复杂的非线性方程组的基础上进一步简化算法，提出了一种基于自适应策略的粒子群优化节点定位算法，该策略从惯性权重和全局最优位置两个方面对原有的PSO算法进行改进，实现了在不增加额外硬件的条件下对无线传感器网络节点定位在定位精度和计算耗时上的进一步优化。通过与极大似然估计定位算法的定位结果进行对比，证明了笔者算法具有收敛快、能耗小、精度高和稳定性好的优点，适合应用在无线传感器网络的定位中。