无线传感器网络中改进的DV-Hop定位算法*

李凤超，高美凤

(江南大学 轻工过程先进控制教育部重点实验室，江苏 无锡 214122)

0 引 言

目前，无线传感器网络节点自定位技术在理论上取得了很大进展，提出了很多定位算法。

距离矢量跳(distance vector hop,DV-Hop)定位算法是一种非测距定位算法，具有复杂度低、可扩展性好等优点[1]，但其定位精度较低，针对这一问题，进行了很多方面的改进和研究，例如：TMCD-DV-Hop算法[2]在传统DV-Hop定位算法中加入阈值机制进行锚节点筛选，并对平均每跳距离(简称平均跳距)进行校正。同一未知节点对不同的锚节点采用不同的平均跳距且利用Quasi-Newton方法对定位结果进行优化[3]。利用RSSI测距技术进行改进，通过将未知节点升级为次锚节点，根据非线性共轭梯度法进行逼近以减小误差，有效提高了定位精度[4,5]。对未知节点接收到的锚节点平均跳距加权处理以提高精度[6]。文献[7]使用蝙蝠算法(bat algorithm,BA)对DV-Hop定位的结果进行优化。文献[8]使用三角形内点测试(approximate point-in-triangulation test,APIT)与DV-Hop相结合以减小定位误差。上述改进算法存在的问题有：1)需要额外投入硬件成本;2)引入迭代算法增加了时间和能量的消耗，3)重点对锚节点平均跳距的改进而忽略了距离计算时的误差。

本文在DV-Hop定位算法的基础之上，通过对锚节点平均跳距、未知节点平均跳距的改进，同时利用平均跳距作用域减小计算未知节点与锚节点之间距离时产生的误差。仿真结果表明，本文所提改进算法在一定程度上提高了节点的定位精度。

1 传统DV-Hop定位算法[9]误差分析

1)平均跳距误差：锚节点通过无线传感器网络中的其他锚节点坐标和相互之间的跳数得到平均跳距，未知节点直接选取距离最近的锚节点的平均跳距作为本身的平均跳距；在这个过程中，传统DV-Hop算法并未对锚节点平均跳距计算以及未知节点平均跳距选取过程产生的误差作处理，直接参与最小二乘法的计算会造成误差累积。

2)距离计算误差：DV-Hop算法通过未知节点的平均跳距与最小跳数的乘积来估计未知节点和锚节点间的直线距离，在这个过程中误差的产生有2方面：利用折线距离代替直线距离所产生的不可消除误差；在计算折线距离时忽略每个跳段距离的差异，统一用未知节点的平均跳距代替所产生的误差。后者可以通过本文提出的平均跳距作用域减小或消除。

2 DV-Hop定位算法的改进

2.1 锚节点平均跳距的改进[10]

本文改进策略包括首先剔除会引入较大误差的锚节点，其次将参与计算的锚节点进行加权处理。

对于矩形分布区域来说，定义最大理想跳数k为

(1)

式中d1～d4为锚节点i距离矩形分布范围4个顶点的距离。在理想情况下平均跳距与通信半径接近，当锚节点接收到距离其他锚节点的最小跳数超出了节点分布范围的最大理想跳数说明该路径中锚节点间的共线度较低，将其剔除。

采用加权处理的方法计算锚节点i的平均跳距。定义

(2)

式中dij为锚节点i和j之间的实际距离；R为通信半径；hopsij为锚节点i和j之间的最小跳数。锚节点j在参与锚节点i平均跳距计算过程中，其权重为

(3)

式中m为参与锚节点i平均跳距计算的锚节点个数。锚节点i的平均跳距为

(4)

2.2 未知节点平均跳距的改进

本文基于文献[3，11]对未知节点平均跳距进行了改进，当锚节点和未知节点在一跳范围内时，未知节点直接取最近的锚节点的平均跳距作为自己的平均跳距；未知节点和锚节点间最小跳数在1～M跳之间时取M跳内的所有锚节点平均跳距的均值；未知节点和锚节点之间最小跳数在M跳之外，取全局平均跳距。即未知节点k的平均跳距为

(5)

式中m为未知节点k周围M跳范围内的锚节点个数；n为整个无线传感器网络中的锚节点个数。阈值M为

式中A为整个无线传感器网络覆盖区域面积；Lh为每个未知节点定位需要的平均锚节点个数；Tn为节点总数；Lp为锚节点比例；Hmax为锚节点和未知节点之间最小跳数的最大值。在满足网络中所有未知节点定位的情况下，M选取最小值参与运算；在节点分布不均的场合，阈值M需要选择略大一些，以满足整个网络的覆盖[11]。

按照式(5)，未知节点在不同情况下，根据与锚节点之间的最小跳数选择不同的平均跳距，克服了传统DV-Hop算法中单纯采用最近的锚节点的平均跳距带来的误差，同时，当未知节点和锚节点在1跳范围内时又保证了平均跳距的精度。

2.3 平均跳距作用域改进

当锚节点和未知节点附近的节点密度差别较大时，二者的平均跳距差别较大，单纯采用未知节点的平均跳距计算距离会造成较大误差。本文提出了平均跳距作用域，根据前述得到锚节点平均跳距和未知节点平均跳距，在计算未知节点到锚节点的距离时靠近未知节点的一半跳数采用未知节点平均跳距计算距离，另一半采用锚节点平均跳距。计算过程如下

dik=Hopsizei×hopsit+Hopsizek×hopstk

(6)

式中Hopsizei为锚节点i的平均跳距；Hopsizek为未知节点k的平均跳距，且满足

hopsit=hopstk=hopsik/2

改进后的DV-Hop定位算法具体步骤如下：

1)锚节点通过未知节点的转发得到其他锚节点的坐标及与其他锚节点间的最小跳数；

2)按照2.1节的筛选原则选取参与平均跳距计算的锚节点并进行加权处理得到锚节点平均跳距；

3)按照2.2节的选取原则决定每个未知节点的平均跳距；

4)根据平均跳距作用域计算未知节点到锚节点的距离；

5)未知节点利用最小二乘法完成定位。

3 仿真分析

为了验证本文算法的有效性，在MATLAB平台仿真分析，同时与文献[3，11]中的改进策略进行对比。仿真模型为100个节点随机分布于100 m×100 m的区域内，考虑不同锚节点比例、节点通信半径对定位误差的影响。未知节点k的定位误差为

(7)

每个实验重复进行100次，取平均值作为最终结果，在通信半径R=30 m时比较锚节点比例对定位误差的影响，结果如图1所示。随着锚节点比例的增大，4种算法的定位误差均减小；锚节点比例较小时，无线传感器网络区域中锚节点分布不均匀，随机性大，文献[3，11]改进方案中大部分未知节点选取全局平均跳距作为自身跳距，而本文算法通过1跳和阈值M的双重分割具有明显效果。当锚节点比例在15 %～30 %时，文献[11]中利用阈值M的定位效果优于文献[3]中单纯1跳分割的方案，而本文算法在阈值基础上再次分开处理，效果更好。锚节点比例超过30 %时，定位误差随着锚节点增大不再明显减小，本文算法仍优于其他算法。

图1 不同锚节点比例下的定位误差

在锚节点比例为20 %时，比较通信半径对定位误差的影响，结果如图2所示。随着通信半径的增大，各种算法的定位误差均减小；当通信半径小于25 m时，1跳距离小，文献[3]相比本文改进算法和文献[11]有更多的未知节点选取全局平均跳距作为自身平均跳距带来了误差的累积，当通信半径大于28m时，锚节点经过筛选与加权后得到平均跳距取得了较好的效果，同时，平均跳距作用域进一步减小了误差，本文算法相比其他改进算法均有不同程度的优势。

图2 不同通信半径下的定位误差

4 结束语

针对无线传感器网络中节点自定位误差较大的问题，对传统DV-Hop定位算法进行了改进，仿真结果表明：在锚节点比例适中、通信半径较小的情况下本文算法可以减小定位误差，提高定位精度，适用于低功耗、大范围的无线传感器网络环境。

[1] Niculescu D,Nath B.Ad hoc positioning system (APS) using AOA[C]∥The Twenty-Second Annual Joint Conference of the IEEE Computer and Communications,IEEE Societies,INFOCOM 2003,LEEE,2003:1734-1743.

[2] 向满天,王 胜,杨友华.基于阈值机制与距离校正的 WSN s改进 DV-Hop 定位算法[J].传感技术学报,2016,29(6):920-926.

[3] Shi Q,Zhou J,Zhang J,et al.An improved scheme for DV-Hop in WSNs[C]∥11th International Conference on Wireless Communications,Networking and Mobile Computing,WiCOM 2015,IET,2015:1-4.

[4] 宋倩雯,郭松涛,柏艾林,等.无线传感器网络中一种改进的DV-Hop定位算法[J].重庆大学学报,2015,38(4):128-136.

[5] Shen S,Yang B,Qian K,et al.An efficient localization algorithm in wireless sensor networks[C]∥International Symposium on Computing & Networking,IEEE,2015:291-294.

[6] 赵芝璞,吴 栋,王 艳,等.基于平均跳距和位置优化的改进 DV-Hop 定位算法[J].系统仿真学报,2016,28(6):1273-1280.

[7] 白 伟,李凤英,郑海洋,等.基于BADV-Hop的无线传感器网络节点定位方法[J].传感器与微系统,2014,33(10):118-120.

[8] 何登平,范茂林.一种基于APIT的无线传感器网络混合型定位算法[J].传感器与微系统,2015,34(2):133-135.

[9] Kumar S,Lobiyal D K.An advanced DV-Hop localization algorithm for wireless sensor networks [J].Wireless Personal Communications,2013,71 (2):1365-1385.

[10] Wang Y,Qian K.An improved DV-Hop positioning algorithm based on Hop distance correction[C]∥2014 11th International Computer Conference on Wavelet Active Media Technology and Information Processing (ICCWAMTIP),IEEE,2014:415-418.

[11] Hu Y,Li X.An improvement of DV-Hop localization algorithm for wireless sensor networks[J].Telecommunication Systems,2013,53(1):13-18.