基于改进的粒子群算法在WSN节点定位中的研究*

陈玲君

(绍兴职业技术学院,浙江 绍兴 312000)

基于改进的粒子群算法在WSN节点定位中的研究*

陈玲君

(绍兴职业技术学院,浙江 绍兴 312000)

如何能够减小无线传感中的节点定位误差一直都是研究的热点。提出一种基于改进的粒子群优化算法以修正DV-Hop误差的传感器节点定位方法,通过分析粒子间距离、双变异因子和权重设置改进了粒子群算法,改进后的粒子群算法减少了未知节点与锚节点间距离的估计误差。仿真实验表明，相对于DV-HOP算法,本文的算法可以有效地提高传感器节点定位精度。

DV-Hop算法;定位精度；估计误差

0 引言

如何能够在无线传感网中进行节点定位一直都是研究的热点,目前大多数的研究都是基于通过锚节点来计算相关未知节点的定位研究[1-2]。国内外学者对此进行了不断深入的研究。DV-Hop是一种应用最广泛的免测距方法,针对其定位精度较低的问题,许多学者对其进行了改进。文献[3-4]利用改进的粒子群优化算法对DV-Hop算法的位置估计进行校正,并利用该算法进行求解。文献[5]从两个方面提出改进:一是基于节点的通信半径对节点间的跳数进行修正;二是借助信标节点间的估计距离与实际距离的偏差对平均每跳的跳距进行修正,仿真实验取得了比较好的效果。文献[6-7]提出将加权运用到无线传感网的节点定位中,取得了比较好的效果。文献[8-9]提出采用其他的人工智能算法求解无线传感网中的节点定位算法,取得了一定的效果。

为了能够更好地提高节点定位的效果,本文首先描述了基本的定位算法,其次对粒子群算法进行了改进,分析了节点定位误差的原因,采用改进的粒子群算法对DV-Hop算法定位误差进行修正,最后通过仿真说明本文改进算法取得的效果。

1 基本算法描述

1.1 DV-Hop算法

DV-Hop节点定位算法只需要包含少量的锚节点,通过定位算法来确定未知节点的位置,它具有不需要通过具体测量距离、硬件要求低等优点,特别适合在硬件条件有限的无线传感网中的应用,具体的算法步骤如下:

(1)锚节点在通信网络范围内向邻居节点发送自己的位置信息。接收节点记录该节点到每个锚节点之间的最小跳数,同时删除同一个锚节点发送的最大跳数信息,然后跳数值加1，继续转发个下一个邻居节点。

(2)每一个锚节点会根据其他锚节点的坐标信息和跳数估算网络平均跳距距离,采用公式(1)表示。

(1)

式中,hopSij表示锚节点i和j之间的跳数。

锚节点将平均跳距发送到整个网络后,未知节点仅记录所收到的第一个平均跳距,通过公式(2)估算未知节点与锚节点的距离:

Li=Si×HopSize

(2)

(3)设P1(x1,y1),P2(x2,y2),…,Pn(xn,yn)表示n个锚节点的坐标位置,待定位节点D的位置为(x,y),其与锚节点的估计距离分别为d1,d2,…,dn，可以建立式(3)所示的方程。

(3)

每一个方程减去最后一个方程,得到如下公式:

(4)

使用线性方程组表示AL=b:

在实际的测距过程中,会产生一些不确定误差,因此线性方程组应该将误差考虑进去,变成AL+N=b,N为随机误差向量,通过最小二乘法得到的解为:

L=(ATA)-1ATb

(5)

1.2 粒子群算法

粒子群算法是一种模拟鸟群在觅食过程中的迁徙的一种群集行为的算法,假设在d维的空间搜索,粒子i的速度和位置分别为vi=(vi1,vi2,…,vid)和xi=(xi1,xi2,…,xid)粒子i自身的历史最优位置为pi=(pi1,pi2,…,pid),种群历史的最优位置为pg=(pg1,pg2,…，pgd),其速度和位置更新方式为:

(6)

(7)

式中,c1和c2分别为加速系数,r1和r2为[0,1]之间的随机数,k为迭代次数,ω为惯性权值。

粒子群算法具有算法结构简单、容易实现等优点,缺点是算法粒子容易发生早熟,易陷入局部最优。为了能够更好地实现粒子群算法在DV-Hop中的定位，本文对粒子群算法进行优化,使得优化后的粒子群算法能够解决粒子群算法陷入局部最优的缺陷,为节点定位提供理论支持。

2 改进的粒子群算法

2.1 粒子之间的平均距离

根据文献[10]研究发现,粒子群算法的早熟收敛问题与种群的多样性密切相关,粒子群算法在后期的执行过程中,整个过种群多样性会逐步收敛,种群的多样性也在不断地丧失。本文采用粒子间的平均距离来衡量种群的多样性,如下:

(8)

2.2 双变异因子

本文基于对文献[11]的研究，结合遗传算法的变异概念，提出了双变异因子来对目标粒子进行跟随,双变异因子由最优因子Ybest和惰性因子Yworst组成,前者主要用来跟随每次迭代中的适应度函数值最优的粒子,后者主要是用来跟随每次迭代中适应度函数值最差的粒子。当进行迭代的时候对两个因子进行高速变异,对最优因子采用公式(9)进行变异,这样有利于在局部最优解的附近的范围内提高搜索精度,对惰性因子跟踪的粒子按照公式(10)进行变异,这样有利于扩大种群的范围,持续更新种群的“生命力”。

Yworsti+1=Yworsti(1+0.621*random)

(9)

Ybesti+1=Ybesti(1+0.5*random)

(10)

其中,random∈Gauss(0,1)。

2.3 权重因子的设置

为了保证粒子群算法具有很好的收敛性,本文提出了在粒子速度上引入权重因子w,通过权重因子的调整来降低粒子在全局和局部最优中调节粒子的速度,从而保证粒子能够获得最优解。

(1)全局解-线性微分策略

在粒子群算法中,伴随着迭代次数的不断增加,粒子的速度会呈现不同的变化,本文采用典型的线性递减策略,权重系数根据迭代次数的更新如下:

(11)式中,wmin表示权值系数的最小值,T为最大迭代次数,t为当前迭代次数。通过使用比较大的惯性权重能够快速定位最优解,伴随着算法的迭代次数不断增大,粒子的速度逐渐减慢,收敛速度加快,算法性能提高,但在算法的初始阶段,会随着惯性权值的减少,搜索能力逐渐变弱,因此局部搜索能力变强,促使算法陷入局部最优。为了避免这种情况的发生,使用如下微分递减的策略来进行惯性权重的更新:

(12)

(2)局部解-非线性策略

权重系数通过线性递减策略改进后,算法的性能已经有了很大的提高,但由于线性递减策略自身的特性导致算法容易陷入局部最优,因此采用非线性策略来解决局部最优解:

(13)

3 基于改进的粒子群算法在节点定位中的研究

3.1 节点定位误差分析

设锚节点(xi,yi)(i=1,2,…,n)与未知节点(x,y)的实际距离为ri,i=1,2,…,n,测距误差为εi,那么|ri-di|<εi,i=1,2,…，n。根据式(2)可知,(x,y)应该满足如下约束条件：

(14)

求解(x,y)使得

(15)

式中如果f(x,y)的值最小,则未知节点的解与真实值之间的偏差就最小,而此时的坐标(x,y)为最优解,即满足下式的未知节点坐标。

fitness(x,y)

(16)

式(16)是一个非线性最优化问题,因此将它作为粒子群的目标函数,通过改进的粒子群算法来提高整个粒子群之间的信息交流能力,求出最优解,从而实现未知节点坐标的计算。

3.2 粒子群算法的修正误差的步骤

(1)通过分析,将无线传感网中的节点定位问题转换为非线性优化问题。

(2)设置粒子群算法的相关参数 。

(3)计算每一个粒子的速度和位置,并根据式(15)计算其适应度值,将适应度最大的对应的粒子的位置保存pi中,将子群体的最优位置保存到Pkg(表示第 k个子群的最优位置)中。

(4)根据式(8)计算当前粒子群的粒子之间的平均距离averagedistance,根据公式(9)和(10)对粒子进行变异。

(5)根据公式(10)和公式(11)计算权重,从而代入式(6)和(7)进行计算。

(6)每个粒子位置与自身的历史最优位置pi对比,选择出最优的粒子位置。

(7)每个粒子位置与所在子群的历史最位置 Pkg进行比较,选择出种群的最优位置Pkg。

(8)当次数达到最大迭代次数,算法循环截止,计算每个子群的最优位置对应的适应度值,选取整个子群对应的最优位置为pg=min(P1g,P2g,…，Pkg,…，PNg)；否则转至步骤(4)继续迭代。

(9)输出pg对应粒子的坐标作为待定位的传感器定点坐标。

4 仿真实验

为了说明本文算法在节点定位中具有的有效性,本文选择在MATLAB2010平台上进行仿真实验。选择计算机硬件配置为:酷睿i3 CPU,4GB DDR3内存,500 GB硬盘;软件环境为Windows Xp。选取250个节点随机分布在边长为100 m的区域中,锚节点和未知节点的坐标位置随机产生。将DV-Hop算法和本文算法在锚节点数量和测距误差两个方面进行对比。

4.1 锚节点数量下的比较

设定锚节点所占的比例不超过10%,即不超过25, DV-Hop算法和本文算法锚节点数量与定位误差变化曲线如图1所示。从图1可知,伴随着锚节点个数的不断增大,两种算法的平均定位误差均逐渐减小,本文算法的定位误差明显小于 DV-Hop算法的定位误差,减少了19.17%。

图1 粒子群算法与本文算法的在锚节点定位误差变化曲线

4.2 测距误差下的定位性能比较

在实际的定位中测距误差是无法避免的,DV-Hop 算法和本文算法定位误差变化和测距误差的关系曲线如图2所示。从图2可知,随着测距误差的不断增多,两种算法的定位误差逐渐增大,相对于Dv-Hop算法而言,本文算法的定位误差分别减少了9.25%。

图2 粒子群算法与本文算法的测距误差变化曲线

5 结论

本文分析WSN中基于DV-Hop定位算法精度低的原因,提出一种基于粒子群的DV-Hop算法，通过对粒子群算法的改进,使得算法的性能得到提高。将改进后的算法运用到了节点定位中，仿真实验结果表明,相比于DV-Hop 算法,本文算法在定位精度方面具有明显优势,是一种简单实用的无线传感器网络节点定位方法。

[1] Li Mo,Liu Yunhao. Rendeved path: range-free localization in anisotropic sensornetworks with holes[J].IEEE/ACM Transactions on Networking,2010,18(1):320-332.

[2] LAZOS L,POOVENDRAN R.High-resolution robust localization for wireless sensor networks[J].IEEE Journal on Selected Areas in Communications,2006,24(2):233-246.

[3] 魏玉宏,田杰,高志强.基于混合粒子群优化的DV-Hop定位算法[J].计算机测量与控制,2015,23(12):4214-4216.

[4] 欧阳丹彤,何金胜,白洪涛.一种约束粒子群优化的无线传感网络节点定位算法[J].计算机科学,2011,38(7):46-50.

[5] 夏少波.无线传感器网络DV-Hop定位算法的改进[J].计算机应用,2015,35(2):340-344.

[6] 周杭霞,崔晨,叶佳骏.一种基于加权处理和误差修的DV-Hop定位算法研究[J].传感技术学报,2014,27(12):1699-1703.

[7] 周彦,文宝,李建勋.无线传感器网络节点近点加权质心定位方法[J].计算机工程与应用,2012,48(1):87-89.

[8] 程超,钱志鸿,付彩欣.一种基于误差距离加权与跳段算法选择的遗传优化DV-Hop定位算法[J].电子与信息学报,2015,37(10):2418-2422.

[9] 江涛.基于混合人工蜂群策略的改进DV-Hop定位算法[J],电子器件,2014,37(5):912-915.

[10] LIU F, LIU G Z.Markov chain analysis and the convergence speed of genetic algorithms[J].Systems Engineering Journal,1998, 13(4): 79-85

[11] Xue Wentao, Wu Xiaobei, Xu Zhiliang. An immune network algorithm based on double mutation operators[J]. Controland Decision,2008,23(12):1417-1422.

Research of improved particle swarm algorithm in WSN node positioning

Chen Lingjun

(Shaoxing Vocational & Technical College,Shaoxing 312000, China)

How to reduce errors of positioning nodes in wireless sensing has always been the research hotspot. This paper proposes an improved particle swarm optimization algorithm to modify the DV-Hop error sensor node positioning methods, and improve the particle swarm algorithm through analyzing distance between particles, double mutation factors and weight setting. The improved particle swarm algorithm can reduce the estimated errors between unknown nodes and anchors, and simulation experiment shows that compared with DV-HOP algorithm, algorithm in this paper can effectively improve the efficiency of sensors in positioning nodes.

DV-Hop algorithm; positioning efficiency; estimated errors

浙江省教育厅科研课题(Y201534905)

TP393

A

10.19358/j.issn.1674- 7720.2016.24.020

陈玲君. 基于改进的粒子群算法在WSN节点定位中的研究[J].微型机与应用，2016,35(24)：70-72，76.

2016-07-29)

陈玲君(1983-),女,硕士,讲师,主要研究方向：智能控制。