基于跳数修正和改进粒子群优化DV—Hop定位算法

熊欢 毛永毅

摘 要： 针对传统 DV?Hop算法在无线传感器网络中节点随机分布对定位结果造成较大誤差的问题，提出一种基于跳数修正的粒子群优化的定位算法HPDV?Hop。此算法通过对锚节点广播的跳数进行修正，让随机静态分布的锚节点移动并按密度分布二次部署以及用改进的粒子群（PSO）算法对定位中的迭代过程进行优化，实现传统DV?Hop定位算法的全面改进，以提高定位精度。仿真结果表明，改进的算法与传统算法相比，定位精度和算法的稳定性有明显提高。

关键词： DV?Hop定位； 锚节点； 最优跳数； 平均跳距； 粒子群优化； 跳数修正

中图分类号： TN711?34； TP393 文献标识码： A 文章编号： 1004?373X（2018）18?0076?04

DV?Hop positioning algorithm based on hop count correction and

improved particle swarm optimization

XIONG Huan1， MAO Yongyi2

（1. School of Communications and Information Engineering， Xian University of Posts and Telecommunications， Xian 710061， China；

2. School of Electronic Information Engineering， Xian University of Posts and Telecommunications， Xian 710061， China）

Abstract： In allusion to the problem that nodes in wireless sensor network are randomly distributed in the traditional DV?Hop algorithm， causing big errors of positioning results， an HPDV?Hop positioning algorithm based on hop count correction and particle swarm optimization is proposed. In this algorithm， the hop count broadcast by anchor nodes is corrected to make the static randomly?distributed anchor nodes moved and deployed a second time according to density distribution， and the iterative process during the positioning is optimized by using the improved particle swarm optimization （PSO） algorithm， so as to realize overall improvement of the traditional DV?Hop positioning algorithm， and improve positioning accuracy. The simulation results show that in comparison with the traditional algorithm， the improved algorithm has an obvious improvement in positioning accuracy and stability.

Keywords： DV?Hop positioning； anchor node； optimal hop count； average hop distance； particle swarm optimization； hop count correction

无线传感器网络[1]（WSN）节点定位中非测距的定位算法[2]不用测量距离，只利用各节点间相互通信实现未知节点的定位，因此备受关注。DV?Hop[3?4]算法用跳段距离代替实际距离[5]来估算未知节点与锚节点的距离。该算法节点不需具有测距功能，但是，定位精度会随网络拓扑结构的不规则和算法本身的缺陷而迅速下降。因此近年来已经有许多改进的DV?Hop算法，改进思路围绕平均跳距、最小跳数的修正和算法的迭代优化[6]三方面。本文针对节点随机分布的网络拓扑，对算法进行改进并通过仿真对改进方案的性能进行比较和验证。

1 DV?Hop算法相关理论

1.1 DV?Hop定位问题

DV?Hop定位算法三个步骤[7?8]中基于跳数修正和改进粒子群优化DV-Hop定位算法

熊 欢1， 毛永毅2

（1.西安邮电大学 通信与信息工程学院， 陕西 西安 710061； 2.西安邮电大学 电子信息工程学院， 陕西 西安 710061）

摘 要： 针对传统 DV?Hop算法在无线传感器网络中节点随机分布对定位结果造成较大误差的问题，提出一种基于跳数修正的粒子群优化的定位算法HPDV?Hop。此算法通过对锚节点广播的跳数进行修正，让随机静态分布的锚节点移动并按密度分布二次部署以及用改进的粒子群（PSO）算法对定位中的迭代过程进行优化，实现传统DV?Hop定位算法的全面改进，以提高定位精度。仿真结果表明，改进的算法与传统算法相比，定位精度和算法的稳定性有明显提高。

关键词： DV?Hop定位； 锚节点； 最优跳数； 平均跳距； 粒子群优化； 跳数修正

中图分类号： TN711?34； TP393 文献标识码： A 文章编号： 1004?373X（2018）18?0076?04

DV?Hop positioning algorithm based on hop count correction and

improved particle swarm optimization

XIONG Huan1， MAO Yongyi2

（1. School of Communications and Information Engineering， Xian University of Posts and Telecommunications， Xian 710061， China；

2. School of Electronic Information Engineering， Xian University of Posts and Telecommunications， Xian 710061， China）

Abstract： In allusion to the problem that nodes in wireless sensor network are randomly distributed in the traditional DV?Hop algorithm， causing big errors of positioning results， an HPDV?Hop positioning algorithm based on hop count correction and particle swarm optimization is proposed. In this algorithm， the hop count broadcast by anchor nodes is corrected to make the static randomly?distributed anchor nodes moved and deployed a second time according to density distribution， and the iterative process during the positioning is optimized by using the improved particle swarm optimization （PSO） algorithm， so as to realize overall improvement of the traditional DV?Hop positioning algorithm， and improve positioning accuracy. The simulation results show that in comparison with the traditional algorithm， the improved algorithm has an obvious improvement in positioning accuracy and stability.

Keywords： DV?Hop positioning； anchor node； optimal hop count； average hop distance； particle swarm optimization； hop count correction前两步骤即通过跳数（Hops）与平均跳距（Hopsize）的乘积求解未知节点的坐标，即式（1）。通过距离公式得到式（2）。

[di=hopsi×hopsizei] （1）

[d21-δ21≤（x-x1）2+（y-y1）2≤d21+δ21d22-δ22≤（x-x2）2+（y-y2）2≤d22+δ22 ?d2n-δ2n≤（x-xn）2+（y-yn）2≤d2n+δ2n] （2）

式中，[δ1，δ2，…，δn]为距离估计误差。

解不等式组求解[X（x，y）]的值，算法第三个步骤转化为约束性优化问题。函数[f（x，y）]取值最小时表示总的误差最小，此时坐标[（x，y）]即为最优解。

[f（x，y）=i=1m（x-xi）2+（y-yi）2-di] （3）

式中，m表示锚节点的数量。

1.2 算法定位误差的分析

1） 一跳距离引起的误差。未知节点X，Y都在锚节点A的通信辐射半径的圆内，DV?Hop算法在定位时，未知节点X，Y到锚节点A都认为一跳距离，实际中未知节点X，Y到锚节点的距离是有偏差的。一跳距离示意图如图1所示。

2） 节点静态部署带来的误差。无线传感器网络中的节点通常是随机静态部署在待定位区域中的，这种随机静态散布在待定位区域的部署方法会导致节点分布不均匀，网络中节点灵活性低，当网络中锚节点较少时，这种节点部署方式将会导致定位结果误差较大。

2 HPDV?Hop算法

2.1 锚节点间跳数的修正

针对跳数对定位结果造成误差的问题，引入最优跳数值（[Hij]）、真实偏离值（[Mij]）和跳数调整因子（[λij]）这3个参数来改进锚节点间跳数。3个参数定义式为：

[Hij=dijR] （4）

[Mij=hij-Hijhij] （5）

[λij=1-M2ij] （6）

式（7）用锚节点间的跳数调整因子来修正跳数：

[hij=λij×hij] （7）

2.2 “锚节点移动并按密度分布”思想二次部署锚节点

可移动锚节点的移动部署方式[9]有很多种，常用的有均匀分布、按密度分布和按间隔阈值分布。本文采用按密度的方法，把目标区域均匀分为4个子区域，假设目标区域锚节点总数为[N]，第i个区域锚节点数为[Ni]，则[Ni]满足式（8），即每个子区域平均应分配的锚节点个数为式（9）：

[N=N1+N2+N3+N4] （8）

[N=N4] （9）

式（9）的余数记为M，比较每个子区域锚节点数[Ni]与式（9）计算出的每个子区域平均应分配锚节点数[N]的大小：

1） 若[Ni>N]，表示该区域锚节点数冗余，需删除冗余的锚节点。方法是用两点间距离公式依次求该区域任意两个锚节点之间的距离，结果按从小到大进行排序，依次删除距离最小的对应锚节点，直至该区域的锚节点个数为[N]结束。

2） [Ni=N] 表示此区域锚节点数目刚好，不需要删除和增加。

3） [Ni

4） 当M[≠]0时，把M个锚节分配到随机生成的M个对应位置。

2.3 采用改进的粒子群算法优化定位结果

2.3.1 粒子群算法原理

1995年，R.Eberthart博士和J.Kennedy博士经过大量研究提出了粒子群[10]优化（Particle Swarm Optimization，PSO）算法，其原理为：待定位区域里的每个粒子的速度和位置通过“位置+速度”不断更新式（10）和式（11）。其中式（10）速度更新公式是与粒子初始速度（[vi]）、个体最优值[（Pbest）]和全局最优值[（Gbest）]有关的函数，粒子i运动的速度是这三个影响速度的和速度。[vit+1=w?vit+c1?r1Pbesti-xit+ c2?r2Gbest-xit] （10）

[xi（t+1）=xi（t）+vi（t+1）] （11）

式中：[w]为惯性权重；[c1]，[c2]为学习因子；[r1]，[r2]服从[0，1]的均匀分布。

用粒子群算法优化定位结果的过程如图2所示，最优位置为P点，各粒子均按照“位置+速度”模型来更新位置和速度，不断地靠近P，第i个粒子受到3个因素的共同影响不断地搜索迭代向最优点P移动。

2.3.2 改进的粒子群优化算法实现步骤

1） 初始化粒子群，包括两个最优值设初值，设初始速度。其中未知节点初值设置为全局最优解。

2） 利用式（12）计算每个粒子的适应度[11]。[fitnessi=1mj=1m（xi-xj）2+（yi-yj）2-dj] （12）

3） 以适用度函数为标准来更新两个最优值，即：

[Pbestt+1=Xt+1， fitness（Xt+1）≤fitness（Pbest）Pbestt，fitness（Xt+1）>fitness（Pbest）] （13）

[Gbestt+1=Pbestt+1，fitness（Pbestt+1）≤fitness（Gbestt）Gbestt， fitness（Pbestt+1）>fitness（Gbestt）] （14）

4） 更新粒子位置和速度。

5） 当达到迭代次数时，退出迭代。否则重新比较所有粒子的个体最优值，释放粒子群中和最优解之间距离最大的粒子，然后继续进行步骤2）。

HPDV?Hop算法流程图如图3所示。

3 仿真分析

3.1 仿真参数与环

本文用归一化的平均定位误差[12]作为算法精度的衡量标准，计算式为：

[error=1NRKk=1Ki=1N（xi-xki）2+（yi-yki）2 ] （15）

1） 不同未知节点数量的情况。如图4所示，通信半径[R=]25 m，取总节点数的10%为锚节点数，图中横坐标节点总数在[100，350]区间变化时，3种算法的归一化平均定位误差都呈下降趋势，节点数量大于200后，仿真曲线趋于平稳状态，当横坐标相同时，HPDV?Hop 算法定位误差始终最小，且较这两种算法分别平均减小16.69%和13.24%。

2） 不同通信半径的情况。总节点数[M=]100，锚节点数[N=]20，通信半径[R]分别取 15 m，20 m，25 m，30 m，35 m，40 m时，对半径归一化的平均定位误差的结果如图5所示。3种算法对半径的归一化的平均定位误差都与通信半径成反比，在通信半径相同时，HPDV?Hop算法的歸一化平均定位误差最小，而且相比其他两种算法的定位算法分别平均减小16.31%和10.53%。

3） 不同锚节点数量。当[M]=100，[R=]25 m时，锚节点数[N]分别取为5，10，15，20，25，30，35，40时，3种算法的归一化平均定位误差随锚节点数变化关系如图6所示。由图6曲线可知，在[N≥15]时，定位误差变化较小曲线波动不大。

4 结 语

本文为了提高定位的准确率和定位精度提出了HPDV?Hop算法。通过定义3个参数修正了跳数，而且移动使有规则分布的锚节点增大了算法的灵活性。从仿真结果可以看出，本文算法明显降低了无线传感器网络的定位误差，使得定位算法的精度和稳定性都有所提高。因此对于节点随机分布的无线传感器网络来说，该算法是一种更好的定位方案。

r

参考文献

[1] 谢涛.无线传感器网络中DV?Hop算法的改进[D].重庆：西南大学，2012.

XIE Tao. Improved DV?Hop algorithm for wireless sensor network [D]. Chongqing： Southwest University， 2012.

[2] DELIN K A， JACKSON S P. Sensor web： a new instrument concept [C]// Proceedings of the SPIE. San Jose： SPIE， 2001： 1?9.

[3] 王新生，赵衍静，李海涛.基于DV?Hop定位算法的改进研究[J].计算机科学，2011，38（2）：76?78.

WANG Xinsheng， ZHAO Yanjing， LI Haitao. Improved study based on DV?Hop localization algorithm [J]. Computer science， 2011， 38（2）： 76?78.

[4] 刘少强，庞新苗，樊晓平，等.一种有效提高节点定位精度的改进DV?Hop算法[J].传感技术学报，2010，23（8）：1179?1183.

LIU Shaoqiang， PANG Xinmiao， FAN Xiaoping， et al. Improved DV?Hop algorithm for higher positioning accuracy [J]. Chinese journal of sensors and actuators， 2010， 23（8）： 1179?1183.

[5] GUO F， HU Y， XIU L， et al. A hierarchical P2P model and a data fusion method for network security situation awareness system [J]. Wuhan University journal of natural sciences， 2016， 21（2）： 126?132.

[6] KENNEDY J， EBERHART R C. Particle swarm optimization [C]// Proceedings of IEEE International Conference on Neural Networks. Perth： IEEE， 1995： 1942?1948.

[7] 涂巧玲，宋佳，胡涛.一种加权的DV?Hop定位改进算法[J].通信技术，2013，46（9）：58?60.

TU Qiaoling， SONG Jia， HU Tao. A weighted improved DV?Hop localization algorithm [J]. Communications technology， 2013， 46（9）： 58?60.

[8] 林金朝，陈晓冰，刘海波.基于平均跳距修正的无线传感器网络节点迭代定位算法[J].通信学报，2009，30（10）：107?113.

LIN Jinchao， CHEN Xiaobing， LIU Haibo. Iterative algorithm for locating nodes in WSN based on modifying average hopping distances [J]. Journal on communications， 2009， 30（10）： 107?113.

[9] 刘锋，张翰，杨骥.一种基于加权处理的无线传感器网络平均跳距离估计算法[J].电子与信息学报，2008，30（5）：1222?1225.

LIU Feng， ZHANG Han， YANG Ji. An average one?hop distance estimation algorithm based on weighted disposal in wireless sensor network [J]. Journal of electronics & information technology， 2008， 30（5）： 1222?1225.

[10] 李新春，郭欣欣.基于最优跳距和改进粒子群的DV?Hop定位算法[J].计算机应用研究，2017，34（12）：3775?3778.

LI Xinchun， GUO Xinxin. DV?Hop localization algorithm based on best average hop distances and improved particle swarm [J]. Application research of computers， 2017， 34（12）： 3775?3778.

[11] 秦鹏程，颜文，解培中.基于区域划分锚节点移动的DV?Hop定位算法：CN105848283A[P].2016?08?10.

QIN Pengcheng， YAN Wen， XIE Peizhong. DV?Hop （distance vector?hop） positioning method based on region partition anchor node movement： CN105848283A [P]. 2016?08?10.

[12] YANG X S， DEB S. Cuckoo search via lévy flights [C]// Proceedings of World Congress on Nature & Biologically Inspired Computing. Coimbatore： IEEE， 2010： 210?214.

[13] 王玉芳，毛永毅.一种基于改进布谷鸟算法的WSN节点定位算法[J].计算机应用研究，2017，34（11）：3412?3415.

WANG Yufang， MAO Yongyi. WSN node localization based on improved cuckoo search algorithm [J]. Application research of computers， 2017， 34（11）： 3412?3415.