一种改进的粒子群算法在WSN中的定位研究

傅 彬

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

一种改进的粒子群算法在WSN中的定位研究

傅 彬

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

针对无线传感网中的节点定位问题,采用RSSI测距技术测量未知节点之间的距离,并采用粒子群算法进行优化,针对粒子群算法的不足,首先通过引入动态扰动因子和惩罚函数提高算法的性能,其次采用距离误差修正和修正定位误差模型来优化节点定位的效果。通过仿真实验将所提算法与基本粒子群算法进行比较,结果表明所提算法在算法的收敛性能和定位精度上取得了比较好的效果,提高了节点的定位效果。

无线传感网；动态扰动因子；惩罚函数

0 引言

无线传感网中的节点定位是衡量无线传感网络数据传输效率高低的一个重要标准[1]。节点定位不但受到自然界中客观条件的影响,还容易受到来自自身节点传输信号强弱、传输距离以及节点能量等条件的限制,因此如何进行节点定位的优化一直都是学者们不断研究的方向。国内外学者从不同的角度对节点定位提出了自己的研究方向。文献[2]提出一种基于小波支持向量机(WSVM)的定位算法,取得了比较好的定位效果;文献[3]从全网平均每跳距离角度出发,分析每个信标节点的平均每跳距离误差,有效地提高了节点定位精度;文献[4]提出一种基于接收信号强度指示测距的蒙特卡罗盒定位算法;文献[5]提出采用人工蜂群算法来修正最小二乘定位误差的传感器节点定位算法,该算法能够有效地提高无线传感器节点的定位精度;文献[6]提出了一种改进粒子群算法与DV-Hop的融合算法。

本文在以上研究的基础上,采用粒子群算法对使用RSSI测距技术的节点之间的距离进行优化,通过对粒子群算法采用动态扰动因子、惩罚函数、误差修正和修正定位模型等方法提高算法的性能,提高算法定位的效果。

1 接收信号强度(RSSI)

在真实的无线传感网中，硬件设备是非常重要的必备工具，其优点是设计简单，缺点是处理能力有限,因此需要布置大量的传感器。而RSSI测距技术不需要复杂的硬件设备,它仅仅依靠节点发射信号的功率与接收信号功率之间的差值来初步估算两点之间的损耗,并转换为两个节点之间的距离,计算公式模型如下:

PR(d)=PtGtGrλ2/16π2d2L

(1)

式中,PR(d)表示接收节点与发射节点相距d的功率,Pt为发射节点的功率,Gt、Gr分别为发射节点和接收节点的增益,L为损耗定量,d为距离,λ为波长。

理论研究中，无线传感网中的节点定位模型都是在假设一定理论条件成立的情况下建立的,但在实际情况中,无线传感网络可能受到来自自然界中的温度、湿度、障碍物等影响,网络中传输的信号肯定会受到不同程度的影响,因此采用RSSI测量获得的节点的估计距离和真实距离具有一定的差距。因此如何降低误差成为了研究的主要方向。

2 改进的粒子群算法

2.1 粒子群算法简述

在一个D维的搜索空间中,种群由M个粒子组成,其中第i个粒子的位置为Xi=[xi1,xi2,…xiD],飞行速度为Vi=[vi1,vi2,…，viD],设定Pi是第i个粒子当前搜索的个体最佳位置,Pi=[pi1,pi2,…，pID]；Pg为当前搜索到的全局最优位置,Pg=[pg1,pg2,…，pgD],因此粒子的位置和速度的调整方向如下:

(2)

(3)

式中的k为迭代次数；r1和r2是0～1之间的随机数,用来保持种群具有的多样性；ω为惯性权重值；c1和c2是学习因子,用来掌握粒子个体的最优位置以及整个粒子群中的全局最优位置,合理地调节算法,提高算法的收敛速度。在粒子群算法中，对每一个粒子的个体来说,个体最优解Pi和粒子全局最优解Pg的更新如下:

(4)

f(Pg)=min[f(Pi)]

(5)

2.2 改进的粒子群算法

文献[7]证明粒子群算法在进化过程中与粒子的速度没有直接的关系,因此将粒子群优化算法的位置更新简化为如下形式:

(6)

2.2.1 引入动态扰动因子

公式(6)虽然进行了简化,但仍然可以发现该算法具有收敛速度快、容易陷入局部最优解的可能。为了解决这个问题,首先引入扰动因子概念,当个体的最优解和全局最优解停滞的时候,使用扰动因子对其进行扰动,使得算法远离当前搜索区域,向其他区域扩散。因此扰动因子设置如下:

(7)

(8)

式中,t0和tg分别表示个体最优解和全局最优解的停滞次数,而T0和Tg分别对应个体最优解和全局最优解的停滞的阈值。

从以上分析中发现，当t0>T0,tg>Tg的时候,算法停滞,当算法再次执行的时候只有在局部获得最优值后才可以执行,从而可以对当前个体极值和全局极值进行扰动,因此算法必须停滞T0或者Tg步之后才能进行下一次迭代运算。虽然设置了扰动因子，但存在两个问题：一个问题是加速了节点定位过程中节点产生的额外消耗,从而降低传感器的寿命；另一个问题是扰动因子有可能让算法从一个局部最优收敛到另一个局部最优,这样降低了算法的时间效率和空间效率。因此为了避免以上出现的问题,针对式(7)和式(8)提出了动态扰动因子的概念,如下:

(9)

(10)

式中,rand1()是一个(0,1)之间的随机数,rand2()是一个(1,kmax)之间的随机数,k为当前迭代次数,kmax为最大迭代次数。因此公式(6)的变化如下:

(11)

2.2.2 惩罚函数

粒子群算法的最优解的确定是算法的关键,而可行解都需要加上一定的约束条件,为了尽可能地缩小最优解的搜索范围,避免算法进行不相关的盲目搜索,降低算法搜索时间,需要将粒子产生最优解问题转换为无约束的优化问题。当粒子满足约束条件的时候,惩罚值会很小；反之,则会很大。对于不满足约束条件的粒子赋予数值较大的惩罚函数数值,这样可以有效地降低目标函数,后续的粒子就会远离无解的区域。

粒子群算法中的粒子最优解获得是在一定约束条件下使得某个度量值达到最小。记f为表示问题的目标函数,A为可行解,gi(x)为约束域,得到:

minf(x),x∈A

A={x|gi(x)≥0,i=1,2,…，m}

(12)

将公式(12)中的不等式约束转换为等式约束问题:

minf(x),x∈A

s.t.min(0,gi(x))=0

(13)

(14)

式(14)中,F(x,M)为惩罚函数,当F(x,M)的最优解逼近约束问题最优解的时候,可行解的约束条件gi(x)的值必须达到很小,反之则很大,因此惩罚项Mp(x)对于非可行解进行了惩罚,这样能够有效地保证约束问题可以转化为非约束优化问题。

3 改进的粒子群算法的定位优化

3.1 距离误差修正

根据2.2.2节描述,在总结了无线传感网的能量消耗后,应该最大限度地降低未知节点的可行解的范围,进而降低未知节点所在区域限制,从而可能加快算法达到最优,引入文献[8]中的修正系数来进行限定。首先,通过RSSI技术得到未知节点X(x,y)到锚节点之间的距离为d1,d2,…，dm,其次,从这些锚节点中选取三个锚节点作为参考节点来计算一个未知节点的距离。

(15)

(16)

因此得到的定位模型的约束条件为:

(17)

3.2 构造约束定位模型

目标函数为:

(18)

根据公式(17)得到两个约束条件为:

(19)

因此构造后惩罚函数为:

(20)

4 仿真实验

4.1 实验环境

4.2 算法的收敛性比较

两种定位算法的收敛性比较如图1所示。从图中发现,本文算法与基本粒子群算法相比收敛速度更快,定位函数值更快。本文算法当迭代次数为90的时候,算法基本收敛,而基本粒子群算法迭代次数为130次才收敛,因此算法的效率提高了30.76%。究其原因是在本文算法中进一步简化了算法粒子的速度项，这样降低了由于算法的速度引起算法收敛的问题，通过动态扰动因子和惩罚函数，有效降低算法的局部收敛可能性，使得算法能够以更快的速度获得全局最优解。

图1 两种定位算法收敛比较

两种算法误差比较如表1所示。由表1看出,在测距误差不断变大的情况下,本算法的定位误差远远小于基本粒子群算法,这主要是因为距离误差的修正使得算法缩小了可行解的搜索范围,使得算法定位更加精确,同时动态扰动算子解决了算法的局部收敛,避免了算法过早产生最优解,最终使得算法能够找到最优解。

表1 两种算法误差比较

4.3 平均定位误差比较

两种算法的平均定位误差比较如图2所示。从图中发现,当测距误差所占的比例逐渐增大的时候,两种算法的平均定位误差都在呈现上升的趋势。另外，在同一个测距误差比例的条件下,本文算法的平均定位误差要明显小于基本粒子群算法,并且测距误差所占比例不断地增大的时候,两者之间的定位误差也在增大,这说明从整体上本文算法都要小于基本粒子群算法,说明了本文算法定位精度较高。图中曲线的平缓度从另一个侧面说明了本文算法的定位精度波动较小。这主要是因为通过粒子的位置去控制算法的进化过程,导致了算法在后期的运算过程中收敛速度变慢，特别是动态扰动因子的引入，进一步防止了算法的局部收敛,有效地提高了算法性能,减少了找到节点位置的时间,距离误差修正系数的引入,保证了可行解产生的区域,降低了搜索消耗的时间,更加准确地找到节点的位置。

图2 两种算法平均定位误差比较

4.4 定位均方差比较

两种算法的定位均方差比较如图3所示。从图中发现,当测距误差比例逐渐增大的时候,两种算法的定位均误差都在不断地增加。两种算法的曲线都比较平缓,在相同的测距误差比例下,本文定位算法误差都要小于基本粒子群算法。伴随着定位误差值的不断增大,本文均方误差增长速度减慢,说明算法定位稳定性很高。这主要是因为避免了速度选项所带来的影响,采用位置来控制算法的进化,距离误差修正系数的引入限定了算法的搜索范围,使得算法更加稳定。

图3 两种算法定位均方差比较

5 结论

如何能够降低节点定位带来的误差是无线传感网中研究的主要方向,本文使用传统的RSSI测距技术来获得未知节点的位置,并采用改进后的粒子群算法对未知节点的位置进行优化,取得了比较好的效果。通过仿真实验说明本文的算法优于基本的粒子群算法的定位,算法效果明显。

[1] 叶阿勇,马建峰,裴庆祺.无线传感器网络节点定位安全研究进展[J].通信学报,2009,30(S1):74-84.

[2] 梁娟,吴媛.采用WSVM的三维无线传感器网络节点定位[J].华侨大学学报(自然科学版),2016,37(1):79-83.

[3] 宋西军，吴梅梅.一种改进的DV-Hop无线传感器网络节点定位算法研究[J].科技通报,2016,32(7):143-145.

[4] 武晓琳,单志龙,曹树林.基于接收信号强度指示测距的蒙特卡罗盒移动节点定位算法[J].计算机应用,2015,34(4):916-920.

[5] 程丽玲.基于ABC-LS的传感器节点定位算法[J].计算机应用与软件,2015,32(5):258-261.

[6] 于泉,孙顺远,徐保国.基于改进粒子群算法的无线传感器网络节点定位[J].计算机应用,2015,35(6):1519-1522.

[7] 胡旺,李志蜀.一种更简单而高效的粒子群优化算法[J].软件学报,2007,18(4): 861-868.

[8] 石莹.基于粒子群的无线传感器网络定位技术的研究[D].哈尔滨:哈尔滨工程大学,2010.

[9] GEETHA V, PRANESH V, KALLAPURB. Clustering in wireless sensor networks: performance comparison of LEACH & LEACH-C protocols using NS2[J]. Procedia Technology, 2012(4): 163-170.

Research on the positioning of an improved particle swarm algorithm in WSN

Fu Bin

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

Aiming at node positioning in wireless sensor network, this paper adopts RSSI measuring technology to measure the distance between unknown nodes, and uses particle swarm algorithm for optimization. Aiming at the deficiency of particle swarm algorithm, this paper firstly introduces dynamic disturbance factors and penalty functions to improve the performance of the algorithm, and then it adopts the distance error modification and modification positioning error model to optimize the effect of node optimization. Through comparing basic particle swarm algorithm in the simulation experiment, good effects have been achieved in the algorithm’s convergence performance and positioning accuracy, improving the positioning effect of the node.

wireless sensor network; dynamic disturbance factor; penalty function

TP393

A

10.19358/j.issn.1674- 7720.2017.08.020

傅彬.一种改进的粒子群算法在WSN中的定位研究[J].微型机与应用，2017,36(8)：63-66.

2016-11-20)

傅彬(1980-),男,硕士,讲师,主要研究方向：信息安全,无线传感。

________________________