基于改进粒子群算法的WSN节点定位技术研究

基于改进粒子群算法的WSN节点定位技术研究

（郑州大学 电气工程学院，河南 郑州 450001）

摘 要：针对传感器节点定位技术存在定位不准确和使用局限性等问题，采用一种改进的粒子群算法来对基于TOA的极大似然估计法进行优化处理，以提高定位精度。自适应变异的粒子群算法是依照群体适应度变化率自适应调节惯性权重值，根据当前种群的平均粒距对种群中部分粒子进行变异处理。通过仿真分析测距误差、未知节点个数和节点通信半径对定位精度的影响，结果表明，相同测试条件下，改进的算法定位更加精确，并且能够提升粒子群算法跳出局部最优的能力，有效的避免了标准粒子群优化算法易早熟、陷入局部最优的缺点，最大概率的寻找到全局最优解。

关键字：节点定位；改进粒子群算法；极大似然估计；全局最优 中图分类号：TP391.9 文献标志码：A

WSN Node Localization Technology Research Based On Improved

PSO

FENG Dong-qing，JIANG Xiao-xiao

(School of Engineering,Zhengzhou University,Zhengzhou Henan 450001,China)

ABSTRACT:In view of the sensor node positioning technology problems such as inaccurate positioning and use limitations,in order to improve positioning accuracy,an improved particle swarm optimization algorithm is used to optimize the maximum likelihood estimation method based on TOA.Adaptive Particle Swarm Optimization with Mutation(APSOwM)can adaptively adjust inertia weight value in accordance with the fitness rate of the group,then,it uses the current population average seed spacing to the particles which is part of the population for variation process.Through the simulation analysis of ranging error,unknown nodes and node communication radius of influence on positioning accuracy.The experimental results show that under same test conditions the improved algorithm can achieve more accurate positioning,enhance the ability of PSO to jump out of local optimum and maximum probability search for the global optimal solution,at the same time effectively avoid the shortcomings of the standard particle swarm optimization algorithm which is easy to premature and fall into local optimum.

KEYWORDS:Node localization;Improved PSO;Maximum likelihood estimation;global optimal

常，定位算法分为基于测距和无需测距两

1.引言

类。基于测距定位算法是通过给定位节点

随着信息技术的日新月异，无线传感配备额外的检测器件（例GPS）来测量节点网络取得了迅猛的发展。在无线传感器网间点到点的角度或距离信息，然后利用三边络中，传感器网络节点定位是通过获取各测量法、多边测量法、三角测量法或个传感器节点在平面或空间中的绝对或相Min-Max法计算出未知节点的坐标信息，常对位置信息，从而获得监测区域的某传感用的测距方法有：RSSI、TOA、TDOA和

[1]

器节点的其他信息，因此，节点的定位成AOA等，此种定为了无线传感器网络的关键技术之一。通

位算法对硬件要求比较高，但是测量精度也相对较高。无需测距定位方法是依靠网络的连通性和信标节点位置信息进行相对精确

的定位[2]

，无需测距的方法主要有：质心法、DV-Hop算法、凸规则定位法、APIT算法和MDS-MAP定位算法等，此种定位算法无需增设测量设备，不过测量较粗糙且使用领域具有局限性。

针对测距算法定位的特点和粒子群算法的不足，本文将一种改进的粒子群算法与TOA极大似然估计方法进行结合。新的定位算法是先采用TOA方法测得节点间距离，再使用极大似然估计法对未知节点坐标进行估算，并通过自适应变异的粒子群优化算法来对坐标进行精确定位。该方法能够解决传统粒子群优化算法易过早熟、陷入局部最优的缺点，使定位更精确、速度更快。通过实验仿真分析，此方法比标准粒子群算法和基本极大似然估计法均更能得到较精确的坐标解。 2.节点定位方法分析

节点定位是在二维（或三维）空间中，已知某一节点获得了到另外三个以上（包括三个）信标节点的距离信息后，确定该点的

坐标位置[3]

。通常使用最小二乘法来估计未知节点的坐标，多边测量法也称为极大似然估计法，如图1所示，假设某一未知节点u测得了到n(n≥3)个锚节点的距离，其中第i个锚节点的位置坐标为 xi,yi 且到未知节

点u的距离为di（i 1,2,...,i,...,n）。则可得方程组(1)：

(xestest1 x)2 (y1 y)2 d2

1 (xest2est222 x) (y2 y) d2

. (1)

. . (xest2yest)2 d2n x) (yn n

其中(xest,yest)是未知节点u的坐标。对问题进行线性化，分别将方程组(1)的前(n-1)个方程减去最后一个方程，得：

x21 x2n 2xest(x1 x2n) y1 y2n 2yest(y1 yn) d21 d2

n x22 x2est2222

n 2x(x2 xn) y2 yn 2yest(y2 yn) d2 dn

.

. .

x22est

2222

n 1 xn 2x(xn 1 xn) yn 1 yn 2yest(yn 1 yn) dn 1 dn (2)

将式(2)转换为AXest b形式，其中

2(x1 xn)

2(y1 yn)

.. A

.

.

， ..

2(xn 1 xn)2(yn 1 yn)

x2x2222

2 1 n y1 yn dn d1 .

b .

.

x21 x2n

y2 y2 d2 d2n n 1nnn 1

上述方程可用最小二乘法解得

X (ATA) 1ATb

，即未知节点的坐标估计值。

锚节点

未知节点

图1 多边测量法示意图

由于测距过程中存在的一些原因务必会使测得的di存在一定的误差，从而导致所求出的未知节点位置坐标的不准确，设未知节点位置坐标误差为：

E n

(xest x2est2

i) (y yi) di

i 1

(3)

由于测距di的不精确，因此我们在此设定一个阈值ε，令取得的(xest,yest)点能够使E ，则ε越小，(xest,yest)越接近未知节点的真实坐标值。

3.自适应变异的粒子群算法研究

粒子群优化算法(Particle Swarm Optimization PSO)是由Kennedy和Eberhart博士1995年在模拟鸟群觅食过程中的迁徙和群集行为时，提出了一种基于群体智能的

演化计算技术[4]

。该算法可以较大概率的找到问题的全局最优解，并且计算效率比传统的随机方法高。其最大的优势在于编程简单、易实现、收敛速度快。但是，基本粒子群优化算法在高维函数中，针对有多个局部极值点的函数的情况，容易发生早熟，易陷入局部最优等现象，从而导致寻

找不到最优的点[5]

。

针对传统PSO易早熟收敛的缺点，本文采用一种将自适应变异策略和粒子群算法结合的带变异的自适应粒子群优化算法(Adaptive Particle Swarm Optimization with

Mutation，APSOwM)[6]

，该方法的思想是：在粒子群优化的过程中，APSOwM依据最优的适应度变化率，自适应修改惯性权重的取值，灵敏地操控算法的全局和局部搜索能力，而且当粒子群的平均粒距小于限定值，或全局最优解在多次迭代中没有显著地变化时，对粒子群中的某些粒子进行变异处理来提高粒子群的多样性，让粒子群能够继续进化，更大概率的追寻到全局最优解。 3.1 标准粒子群算法

在粒子群算法中，每个个体称为一个“粒子”，代表一个潜在的解。假设，在D维的测量空间中，每一个粒子当做测量空间内的一个节点。设群体由m个粒子构成，m也称为群体规模。每个粒子个体能够通过设定的规则估计自身位置的适应值，并且记住自己当前所找到的最好位置，称为“局部最优值pbest”；此外还能记住群体中所有粒子找到的最好位置，称

为“全局最优值gbest”。这两个最优变量使得粒子在某种程度上朝着这些方向靠近。

设 i (zi1,zi2,...,zid,...,ziD

)为第i个粒子(i 1,2,...,m)的D维位置矢量坐标，通过设定的适应值函数得出Zi现在的适应值，可以判定粒子位置定位的优劣；

Vi (vi1,vi2,...,vid,...,viD

)为粒子i的飞行速度，即粒子移动的距离；

Pi (pi1,pi2,...,pid,...,piD

)为粒子迄今为止搜索到的最优位置；Pg (pg1,pg2,...,pgd,...,pgD)为整个粒子群迄今为止搜索到的最优位置。

在每次迭代中，粒子根据式(4)和式(5)更新速度和位置信息：

vk 1id

vkid c1r1(pid zkid) c2r2(pkgd zid

) (4) zk 1id zk

id vk 1

id (5)

其中，i 1,2,...,m，d 1,2,...,D，k是迭代的次数，r1和r2是[0,1]之间的随机数，这两个参数是用来保持群体的多样性，

c1和c2是学习因子，即加速因子，它赋予粒子具有自我总结和向群体中优秀个体学习的能力，从而使粒子向自己的历史最优点和群体的历史最优点靠拢，vid取

[vmin,vmax]，当速度超过这个范围时取边界值，同样zid取[zmin

,zmax]，

0.1 0.8是惯性权重系数，它的作用是权衡局部最优能力和全局最优能力[7]

。

设为一个随时间线性减小的函数，函数形式为：

max min

K

k (6)

其中， max为初始权重； min为最终权重；K为最大迭代次数；k为当前迭代次数。

式(4)的第二项是“认知部分”（Cognition part），表示粒子对自身的学习能力；第三项是“社会部分”（Social part），表示粒子的协作能力。式(4)是粒子参考其前一次迭代的速度、其当前位置信息和自身最好经验点，与群体最好经验点之间的距离来更新速度。然后粒子根据式(5)

飞向新的位置[8]

。

由于本论文考虑的是实际工作环境的三维空间即D=3，因此由式(3)设定适应度函数为：

F(xest,yest,zest)(xest x)2 (yest y)2 (zest z)2jjjjijiji di

i 1

(7) 3.2 自适应变异的粒子群优化算法

由于粒子群算法是通过寻找群体的最优粒子方式进行迭代寻优的，在迭代过程中，如果一个粒子发现了当前的最优位置，其他的粒子就会向它靠拢，但是如果粒子寻找到的最优位置是一个局部的最优位置，就会导致整个粒子群陷入一个局部最优，算法就会过早收敛。经过分析知道，粒子群优化算法寻优过程中，粒子都会聚集到一个范围之内，使粒子群失去了多样性的特点，从而导致粒子群早熟。

文献[6]采用粒子群的平均粒距代表粒子群的多样性。定义第k次迭代时种群的平均粒距d(k)为：

D

d(k) 1m

est

m L Z

jd

d) (8)

j 1

(d 1

其中，L是搜索空间对角最大长度，d是所有粒子第d维坐标均值。平均粒距展示了粒子群中每个粒子之间分布的离散程度，平均粒距越小，说明粒子群越聚集。

定义最优适应值变化率g：

g

F(k) F(k 5)F(k 5)

(9)

其中，F(k)是群体第k代的最优适应度值；g代表群体在连续5代迭代中的最优适应度值的相对变化率。设定惯性权重系数 的值根据g的取值自适应选取，遵循表达式(10)

r1 2,g 0.05

r

2,g 0.05

(10) 2其中r取[0,1]之间的任意数， 1 2，根据经验取 1 0.6， 2 0.2。当g≥0.05时，表示群体在迭代过程中最优适应度值的波

动比较强，群体还未寻找到聚拢方向，此情况下 1

r

2

益于算法的收敛；当g<0.05时，表示群体在迭代过程中最优适应度值趋于一定值，群体进入开发时期，此情况下

r

2 2

益于群体寻找到较准确的解。

定位算法步骤：

1) 通过TOA技术测得未知节点与锚节点建的距离，利用极大似然估计算法估算出未知节点的大致坐标；

2) 初始化算法中各个参数，设最大迭代次数为K次，对粒子的位置和速度进行初始化设定，平均粒距最小阈值dmin；

3) 根据算式求出群体的平均粒距d(k)和每个粒子的适应度值，如果d(k)小于最小阈值dmin，进行变异操作，否则进行第4)步；4) 根据适应度函数式(7)计算每个粒子的适应值；

5) 比较粒子j当前位置的适应度值和其目前搜索到的最优位置的Pj，如果较好，则将此粒子此时的位置作为当前最优的位置并更新Pj；否则，保持Pj不变；

6) 比较粒子j当前位置的适应度值和群体目前搜索到的最优位置的Pg，如果较好，则将此粒子此时的位置作为当前群体最优的位置并更新Pg；否则，保持Pg不变。

若Pg一段时间内无显著变化，则进行变异操作；

7) 计算最新几代的最优适应值变化率g，按照(10)式改变权重系数 ，然后按照式(4)和(5)更新粒子的速度和位置，生成新一代种群；

8) 若达到最大迭代次数K则结束循环，否则转至第3)继续，直至达到最大迭代次数结束定位。 4.仿真研究

为了验证自适应变异的粒子群优化算法结合基于TOA的极大似然估计法的定位效果，本文采用Matlab7.0进行仿真。设定仿真区域为100m 100m 100m

的三维空间。粒子群各个参数设定为：学习因子

c1 c2 1.518，最大迭代次数K=200次，

重复计算次数

100，最大步长

V区域边长1010010

10m，惯性权重 0.76

。设定定位空间随机分配20个粒子。

无线传感网络节点定位机制和算法的性能会直接影响到它的实用性，而定位精度就是定位技术最重要的评价指标，一般是用误差值和节点通信半径的比例来表示，其表达为(11)。

n

(xreal xest)2 (yreal yest)2

(zreal zest)2

jj

jj

jj

j n r

(11)

real real , z real

式中，(xj,yjj)为第j个未知节点的真实坐标位置，(xest

j

,yestest

j,zj)是其计算

出的坐标位置，n是未知节点的个数，r是无线传感网络通信半径[9]

。

本实验在仿真环境下设定有100个传感器节点随机分布于仿真区域中，其中锚节点个数20，未知节点个数n=80。 4.1 测距误差对定位的影响

由公式(3)所知，测距误差的大小会影响定位的精度，从而影响定位误差的大小。设定未知节点个数为80个，锚节点个数为20个，节点通信半径为30m。图2为三种算法下平均定位误差随测距误差变化的曲线图。

图2 平均定位误差随测距误差变化曲线图

由图2分析得出，粒子群算法的定位效果优于极大似然估计法，而自适应变异的粒子群优化算法更优于标准粒子群算法。随着测距误差的增大，自适应变异的粒子群算法的平均定位误差上升的幅度比其他两种方法都小。可见，自适应变异的粒子群优化算法抗误差性更优。

4.2 未知节点的个数对定位的影响

由平均定位误差公式(11)知，未知节点数n也会影响平均定位误差。设定节点通信半径为30m，测距误差10%。图3为三种算法下平均定位误差随未知节点个数变化的曲线图。

图3 平均定位误差随未知节点个数变化曲

线图

由图3分析得出，在未知节点个数变化的情况下，APSOwM的平均定位误差略低

于粒子群优化算法的平均定位误差，但都远远低于极大似然估计法。可见，自适应变异的粒子群优化算法在此种情况下收敛性更优，定位精度更优。

4.3 节点通信半径对定位的影响

由平均定位误差公式(11)知，节点通信半径r也会影响定位误差，因此，在通信半径变化的情况下，设定未知节点个数为80个，测距误差10%。图4为三种算法下平均定位误差随节点通信半径变化的曲线图。

图4 平均定位误差随节点通信半径变化曲

线图

由图4分析得出，在APSOwM算法下，节点通信半径对定位精度的影响低于标准的粒子群算法，两种算法均比极大似然估计法的定位误差更优，尤其是在节点通信半径较小的情况下APSOwM算法的平均定位误差最小，优势更明显。可见，APSOwM算法搜索能力更强，更能精确定位。 5.结论

在无线传感网络中，最关键的是节点的定位，本文在分析各种定位技术特点的基础上，提出了基于TOA测距的自适应变异的粒子群优化极大似然估计定位算法，并在Matlab2012中进行编程仿真，在不同测距误差、不同未知节点个数和不同通信半径三种条件下进行三种方法的平均定位误差对比，结果表明，在各种情况下APSOwM算法的定位精度均优于极大似然估计算法，并且比标准的粒子群算法定位更加精确。

参考文献

[1] 许力.无线传感器网络的安全和优化

[M].北京：电子工业出版社，2010:191-202.

[2] 李体红，丰树谦.室内无线传感网络差

分定位算法研究[J].计算机仿真，2010,27(7):102-104.

[3] A.Nasipuri and K.Li.A Directionality

Based Location Discovery Scheme for Wireless Sensor Networks[J].Prco.First ACM Int`l Workshop Wireless Sensor Networks and Application.pp.105-111，Sept.2002. [4] Jeffrey Hightower，Gaetano

Borriello.Location systems for ubiquitous computing[j].IEEE Computer，August 2001,34(8):57-66.

[5] 刘志坤，刘忠，唐小明.基于改进型粒

子群优化的节点自定位算法[J].中南大学学报(自然科学版)，2012,43(4):1371-1376.

[6] 阳春华，谷丽姗，桂卫华.自适应变异

的粒子群优化算法[J].计算机工程，2008,34(16):188-190.

[7] Parham H. Namin，Mohammad A.

Tinati.Node Localition Using Particle Swarm Optimization[J] .IEEE Networks，2011:288-293.

[8] 朱世娟，朱庆保.求解函数优化的分群

粒子群算法研究[D].南京师范大学，2012.

[9] 欧阳丹彤，何金胜，白洪涛.一种约束

粒子群优化的无线传感网络节点定位算法[J].计算机科学，2011,38（7）:46-50.

本文来源：https://www.bwwdw.com/article/lry1.html