一种虚拟信标节点机制的DV-Hop定位改进算法

◆胡平霞 龚静 丁锋 张玉平

一种虚拟信标节点机制的DV-Hop定位改进算法

◆胡平霞 龚静 丁锋 张玉平

（湖南环境生物职业技术学院 湖南 421001）

本文为提高无线传感器网络中非测距定位算法DV-Hop的定位精度，特提出一种通过信标节点移动形成虚拟信标节点的VADV-Hop改进算法，优化信标节点部署位置，使用网络平均跳距校正信标节点平均跳距。仿真实验表明VADV-Hop算法在不增加信标节点数量上表现出较稳定的定位精度。

无线传感器网络；定位；平均跳距；虚拟信标节点

无线传感器网络（Wireless Sensor Network， WSN）是由静止或移动的传感器节点以自组织和多跳的方法组成的无线网络，是一种集感知数据、采集数据、处理数据、传输数据等技术实现物理世界与信息世界数据交互的一种分布式网络系统。传感器节点返回的数据包含位置信息，没有位置的数据实用价值很低，因此传感器节点定位技术是WSN的关键技术之一，其定位精度直接影响WSN的发展和应用。

根据定位过程中是否要测量未知节点和信标节点间的距离，把定位方法划分为基于测距定位（Range-based）方法和免测距定位（Range-free）方法[1]。其中免测距定位方法由于其低成本、易实现等特点得到很多研究者关注。常用免测距定位方法有DV-Hop算法[2]、质心算法[3]、APIT（Approximate Point-in-Triangulation Test）算法[4]、凸规划（Convex）算法[5]等，它们都是通过已知节点位置信息实现对未知节点的定位。

1 DV-Hop算法

美国Lutegesi大学的Dragons Niculescu等人在2003年提出DV-hop（Distance Vector-Hop）算法采用距离矢量路由机制定位，是一种基于多跳测距的免距离测距方法[2]。DV-Hop算法是目前研究较多的免测距算法，该算法通过信标节点位置估算未知节点位置，然后信标节点的数量在实际应用中受到成本限制，因此本文在DV-Hop算法思想上提出一种基于虚拟信标节点技术的改进算法。

1.1 定位过程

DV-Hop算法节点定位过程[6]如下：

（1）确定信标节位置及最小跳数

通过信标节点广播的数据包，信标节点确定其他信标节点坐标及最小跳数，未知节点确定信标节点坐标及最小跳数。

（2）确定平均跳据，估算距离

使用信标节点的位置坐标及信标节点间的最小跳数，通过公式1来计算信标节点的平均跳距，使用平均跳距结合公式2计算未知节点到信标节点的距离。

节点的坐标表示为（x，y），节点的坐标表示为（x，y），、均为网络中的信标节点。信标h表示二节点、间的最小跳数，表示、间的跳距平均值。

HopSize是未知节点选用最邻近信标节点的跳距平均值，hop是未知节点到信标节点的最小跳数值。

（3）确定未知节点位置

未知节点在获得2个以上跟信标节点的参考距离后，使用相应信标节点坐标（x，y）及d，转换成线性方程，通过数学方法（最小二乘法）计算得到未知节点位置坐标。

图1 DV-Hop估算示意图

图1中U为需要定位的未知节点，通过已知节点即信标节点BBB的位置信息来测算U的位置。首先BBB通过洪泛算法进行广播，各节点保存最小跳数信息。其次BBB节点计算自身平均跳距，U使用最邻近的节点B平均跳距作为自身跳距平均值分别计算到信标节点的距离。最后建立位置矩阵，通过最小二乘法计算U的坐标。

1.2 算法分析

1.2.1客观条件分析

现实应用场景的无线传感器网络，存在以下客观条件：

（1）异常节点问题

异常节点是部署在边缘的节点或是被孤立的节点，这些节点的位置信息影响定位精度。

（2）节点密度问题

由于受节点分布密度的影响，最小跳数和平均跳距误差造成的差异会造成节点定位累积误差，从而影响算法定位精度[7]。

1.2.2定位误差分析

DV Hop算法定位误差主要有：

（1）节点跳数产生的误差

在DV-Hop定位过程中使用节点间的最小跳数来估算距离，误差主要产生在以下两个方面，一是跳数值越小表示距离越近，实则不然；二是可感知的邻节点间的跳数为一跳，默认估算距离相等，实际上由于节点分布不均，相邻节点间的距离并不相等。

（2）平均跳距产生的误差

在DV-Hop定位过程中信标节点间的平均跳距通过最小跳数计算得到，由于最小跳数存在误差，平均跳距也将存在误差；未知节点使用最邻近信标节点跳距均值作为自身跳距均值，本身就存在一定算法允许内的误差。

（3）计算定位误差

使用数学方法（最小二乘法）求未知节点位置时，由于计算公式中的估算距离存在误差，因此计算结果也会存在误差。

2 提出改进算法

根据DV-Hop算法定位过程中存在的客观条件和误差分析，结合MADV-Hop[9]算法思想提出一种改进算法VADV-Hop，通过信标节点一定轨迹运动形成虚拟信标节点，未知节点参考多个信标节点信息估算位置坐标，然后取平均值。通过全网平均跳距校正节点平均跳距，在减少信标节点开销的同时提高定准精度。

2.1 基于虚拟信标节点的改进

在DV-Hop算法基础上，部署少量信标节点，信标节点按一定轨迹运动，每到一个新的位置形成一个新的信标节点，称为虚拟信标节点，计算该信标节点位置，通过多个虚拟信标节点位置信息平均值降低计算误差。

VADV-Hop算法信标节点分布见图2，在R x R的监测范围中部署9个信标节点，确定位置，其中B-B为可移动信标节点，B为静态信标节点，位置信息描述如下：

表1 m×m的区域中信标节点位置坐标

图2 VADV-Hop信标节点分布

2.2 平均跳距校正

得到信标节点平均跳距以后，计算全网平均跳距误差，利用该误差值修正平均跳距。

h是信标节点和信标节点之间的跳数最小值，是每跳距离平均值：

为校正权值，取值为区间为（-0.5，0.5），使用校正后的平均跳距计算未知节点到信标节点的距离估值，使其更接近真实值。

2.3 VADV-Hop算法定位流程

VADV-Hop算法定位方法描述如图3所示，未具体描述的环节保持跟DV-Hop算法一致，重点对从计算平均跳距后有变动的定位步骤进行描述。

（1）开始定位。

（2）信标节点使用洪泛算法广播发送位置信息数据包，广播次数为4次。

（3）邻节点处理到达的数据包。

（4）计算跳距均值并校正，校正方法如公式3、公式4。

（5）计算节点间距值，使用校正后的平均跳距利用公式5计算未知节点与信标节点的距离。

（6）计算未知节点位置。

（7）信标节点按△d沿预设运动轨道运动形成虚拟信标节点，判断位置是否重复，不重复则确定当前位置为有效位置，更新位置后返回第（2）步。

（8）在未知节点取3次以上自身坐标平均值。

图3 VADV-Hop算法描述

3 VADV-Hop算法性能分析

3.1 仿真场景说明

使用Matlab软件进行仿真实验，仿真参数见表2。针对VADV-Hop算法的仿真实验均进行了100次，每一次仿真实验在相同仿真场景前提下对原算法也进行了对比实验，使用100次定位结果的位置均值进行对比分析。未知节点在R x R的监测范围内呈随机分布，如图4所示。

表2 VADV-Hop 仿真实验参数设置

3.2 仿真实验结果分析

（1）定位误差分析

通过在相同模拟网络场景下的对比实验发现，基于虚拟信标节点的改进算法性能相对原算法有所提升。如图5所示，改进后的算法定位误差在3%到24%之间，误差曲线基本保持在10%到20%之间，误差震荡较小。

（2）通信半径对定位结果影响分析

在相同模拟场景下，调整通信半径，保持其他参数不变，对改进算法定位精度进行仿真实验。仿真数据结果显示，VADV-Hop算法和原算法在改变通信半径后定位精密度都受到了影响，其中原算法和VADV-Hop算法在较小通信半径下定位精密度较低，VADV-Hop算法在半径值达到一定值时（本实验中的数值为30 m）后，表现出较稳定的定位精度。

（3）未知节点数量对定位结果影响分析

在相同模拟场景下，改变投放的未知节点数量，其他参数不做调整，进行仿真实验。

布置的信标节点数量未做调整，DV-Hop算法和VADV-Hop算法的定位精密度都随着未知节点的数量发生变化。VADV-Hop算法由于采用了虚拟信标节点技术，增加了位置参考信息，在125个未知节点前定位性能较好，继续增大未知节点数量后，定位误差显著上升。

图7 未知节点数量对定位精度影响分析

4 结语

VADV-Hop算法在传统DV-Hop算法的基础上，通过信标节点的运动形成多个虚拟信标节点，一定程度上增加了未知节点的参考信息，通过模拟场景下的仿真实验表示，VADV-Hop算法跟原算法比，在不增加信标节点的基础上，算法性能稳定，定位精度较有所提升，算法复杂性增加。

由于实验都是在仿真环境下特定的网络场景中估算未知节点的位置，未知节点数量保持在100附近。实际应用中的WSN都是三维空间，网络场景差异性很大，通信条件、户外干扰等问题都会对算法的性能产生影响，因此后续将对三维场景的VADV-Hop算法进行研究。

[1]CHENG XIUZHEN，SHU HAWING，LIANG QILIAN，et al. Silent positioning in underwater acoustic sensor networks[C]//IEEE Transactions on Vehicular Technology. IEEE，2008：1756-1766.

[2]Niculescu D，Nath B.DV Based Positioning in Ad Hoc Networks[J]. Telecommunication Systems，2003，22（1-4）：267-280.

[3]Bulusu N，Heidemann J，Estrin D. GPS-less Low Cost Outdoor Localization for Very Small Devices [J].Institute of Electrical and Electronics Engineers Personal Communications Magazine，2000（5）：28-34.

[4]Wang Z J，Jin H. Improvement on APIT Localization Algorithms for Wireless Sensor Networks：Networks Security， Wireless Communications And Trusted Computing，2009[C].International Conference on IEEE，2009（1）：719-723.

[5]Doherty L，El Ghaoui L. Convex Position Estimation in Wireless Sensor Networks [C].Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies，2001：1655-1663.

[6]Lv X，Sun X，Zhou X，et al. DV-hop-MSO Based Localization Algorithm in Wireless SensorNetworks[M]//Advances in Wireless Sensor Networks. Springer Berlin Heidelberg，2014：312-316.

[7]于泉.无线传感器网络中DV-Hop改进算法的研究[D].江南大学，2016.

[8]冯友兵，马艳，魏玉婷.基于移动锚节点的改进DV-Hop算法[[J].计算机科学，2015，42（s2）：277-279.

衡阳市科技计划项目（2016KJ20）、湖南省教育厅科学研究项目（16C0565）、衡阳市社会科学联合会（2017D107）、湖南环境生物职业技术学院支柱工程项目（湘环院教字〔2017〕46号）。