基于跳距加权的DV-hop定位算法改进

赵小平，马嘉楠，饶 瑞，宫 婧

(南京邮电大学 理学院，江苏 南京 210023)

0 引 言

随着无线传感网络(WSN)的飞速发展，其在工业环境、智能交通、军事等领域应用广泛。在无线传感网络研究中，节点定位算法是一个至关重要的问题，同时也是一个技术难点。

节点定位算法，是根据已知坐标的锚节点(通过自身携带GPS定位)，对未知节点进行定位。节点定位算法可以分为基于测距和基于无测距的定位算法[1]，基于测距的定位算法，是根据硬件测量节点之间的距离，开销较大，如RSSI、TOA、TDOA等；而基于非测距的定位算法，是通过间接的手段来获取节点之间的距离，如Amorphous、APIT、DV-hop等。得到节点之间的距离后，利用最小二乘法、遗传算法、蚁群算法等优化算法来求解，得到未知节点的坐标。研究定位算法，主要考虑定位精度、能耗开销、硬件成本等。研究定位算法的改进目标就是通过更小的代价实现更高的定位精度。

文中重点研究DV-hop定位算法，通过对未知节点附近锚节点跳距进行加权得到未知节点到锚节点的跳距，权重由未知节点到信标节点的跳数，并结合信标节点跳距的可信度确定。信标节点可信度根据信标节点实际距离和通过算法求得的跳距乘以跳数得到的距离之间的误差得到。最后对算法精度进行验证。

1 经典DV-hop算法

DV-hop定位算法是一种分布式非测距算法[2]。算法受环境的影响较小，也不需要额外的硬件设备支持，所以适应于成本低、规模大、节点配置简单的无线传感网络[3]。

1.1 算法描述

经典DV-hop算法非常类似于传统网络中的距离向量路由机制，从而可以将其大致分为三步[4]：

(1)信标节点进行信息广播，计算未知节点与每个信标节点的最小跳数；

(2)计算未知节点与信标节点的实际跳距；

(3)根据求得的未知节点到信标节点的估计距离，计算未知节点自身坐标。

1.2 算法误差分析

DV-hop是一种完全依靠网络连通度来对未知节点进行定位的算法[5]，在定位的过程中，外部环境和定位算法本身都会产生一定的误差。产生误差的方面具体如下：

(1)镜像误差。

在定位过程中，由于用作未知节点定位的信标节点近似共线[6]，未知节点可能出现误判，如图1所示。

图1 镜像误差分析图

图中，A、B、C为信标节点，i为未知节点，由于信标节点近似共线，导致误判成为i'。这种现象称为镜像误差现象，经典DV-hop未考虑这种误差的影响。

(2)定位计算方法。

在求得未知节点与信标节点之间的距离之后，一般采用极大似然估计法或三边测量法等估算算法来计算未知节点的坐标[7]。主要是因为算法简单易实现，求得的结果都会有一定的误差，并且容易造成一定范围内的误差积累。

(3)无法定位节点(不良节点)。

无线传感网络中的节点是随机分布的，很容易造成分布不均[5]。如果未知节点周围的信标节点数量小于3个，无法对其进行定位，从而产生了定位盲点。

(4)跳数误差。

在节点跳数获取阶段，信标节点以通信半径R广播位置信息，收到该信息的节点均计为1跳。如图2所示，A、B节点均在信标节点S通信范围内,都能接收到信标节点的位置信息，并且跳数都为1跳，未知节点C在信标节点通信的边缘，但是收不到信标节点广播的信息，而是接收到节点B转发来的信标节点的位置信息，所以未知节点C的跳数为2跳。A靠近信标节点，B、C位置接近，而A到信标节点的距离与B相等，是C到信标节点的一半，显而易见，这样误差较大[8]。

图2 跳数误差分析图

(5)平均跳距误差。

当锚节点间的跳数严重偏离直线路径时[9]，采用公式计算误差较大，用来估计未知节点到锚节点之间的距离时误差也较大。

2 基于跳距加权的改进DV-hop算法

由于经典DV-hop算法的误差较大，于是考虑从跳距方面进行改进。文中通过对未知节点周围信标节点的跳距进行加权，从而得到比较准确的跳距。影响一个锚节点对未知节点的重要性因素，主要分为锚节点到未知节点的距离和锚节点跳距的可信度。而锚节点到未知节点的距离可以用两者之间的跳距来衡量，锚节点跳距的可信度可用锚节点之间真实距离与估算距离两者的误差来度量，两者误差越大，可信度越低。

2.1 信息广播和跳数计算

信标节点通过洪范方式广播自身的坐标信息[10]，设初始跳数为0。未知节点记录收到每一个信标节点的最小跳数，同时忽略同一信标节点其他跳数较大的路径，然后将跳数值加1，继续转发给邻居节点，这样每一未知节点可以得到信标节点的最小跳数。

2.2 信标节点跳距计算

设信标节点Sk的坐标为(xk,yk),它的邻居节点Si(i=1,2,…,N)的坐标为(xi,yi)。每个信标节点根据获得的到其他信标节点的坐标和到其的最小跳距[11]求得跳距，公式如下：

(1)

其中，hik为信标节点Si和Sk之间的最小跳数。

2.3 未知节点到锚节点的跳距

信标节点到未知节点的跳距越大，即相距越远，信标节点对未知节点的贡献越小。为了提高定位精度，应充分利用网络中的信息，并赋予近距离锚节点较大的权重，故利用反距离加权处理平均每跳距离[12]，表示为：

(2)

其中，Hopij为锚节点Si和Sj之间的跳距。

2.4 信标节点跳距可信度

利用信标节点误差来度量其跳距可信度[13]。首先，利用经典DV-hop算法求得的跳距来估算锚节点之间的距离；其次，与实际距离比较，求出误差值；最后，利用误差大小来确定跳距的权重。

(1)计算锚节点误差。

利用经典DV-hop算法中第二步求得的跳距乘以最小跳数，求得估算距离，从而实际距离与估算距离之间的误差为：

(3)

其中，Dij为锚节点Si和Sj之间的实际距离；Hopsizej为锚节点Sj的跳距；Hopij为锚节点Si和Sj之间的跳距。

(2)权重确定。

用误差的倒数作为权重，并进行归一化，如下：

(4)

(5)

其中，KHopi为距未知节点跳距小于k跳的锚节点。

2.5 计算最终平均跳距

结合信标节点可信度和信标节点离未知节点的跳距，确定最终权重，如下：

ωj=αγj+(1-α)βj

(6)

其中，α为系数，用来衡量信标节点可信度和信标节点与未知节点之间的跳距两者的重要性。

未知节点使用距其k跳(经典DV-hop所求)的锚节点跳距并结合上述权重进行加权，作为最终的跳距，公式如下：

(7)

其中，HopSizej为未知节点Xi的修正跳距。

2.6 未知节点定位

利用得到的跳距乘以跳数得到节点之间的距离，结合最小二乘法[14]进行求解，得到未知节点的坐标。

首先，计算未知节点到锚节点的距离，利用未知节点到锚节点的最小跳数和信标节点的跳距，得到如下公式：

dij=reHopSize×hij

(8)

其中，dij为未知节点Xi到锚节点Sj的距离；hij为未知节点Xi到锚节点Sj的跳数。

然后，设未知节点坐标为(x,y),锚节点Sj的坐标为(xj,yj)，得到未知节点到信标节点之间的距离di。利用欧氏距离公式有：

(9)

把上式转化为线性方程组，形式如下：

AX=b

(10)

从而解得未知节点X的坐标:

X=A+b=(ATA)-1ATb

(11)

其中：

(12)

(13)

3 仿真结果与分析

为了验证基于跳距加权的改进DV-hop算法的性能，利用MATLAB对DV-hop算法和改进DV-hop算法进行对比，并用仿真数据进行分析。实验中的参数设置如表1所示。

表1 仿真参数设置

仿真中，锚节点和未知节点随机分布在1000m×1000m的区域内，信标节点和未知节点都是随机生成的，在有些区域信标节点比较密集，有些地方信标节点数量较少，从而会导致一定的定位误差，尤其在信标节点稀疏区域，误差较大。

分析经典DV-hop算法和改进DV-hop算法的定位精度，得到的误差图如图3和图4所示。

图3 经典DV-hop误差图

图4 改进DV-hop误差图

由图可知，改进DV-hop的每个未知节点的估计位置偏离真实位置要比经典算法小，从而表明改进DV-hop的精度要比经典DV-hop精度高。而且在信标节点较为密集的区域，误差较小；而在信标节点较为稀疏的区域，定位误差较大。下面从误差值来考虑。定义平均误差[15]，即所有未知节点的估计位置与真实位置的偏离之和除以通信半径和未知节点数量，公式如下：

(14)

利用平均误差公式，计算得到原始DV-hop和改进DV-hop定位算法10次实验的平均误差，并作图进行对比，如图5所示。

图5 改进DV-hop和经典DV-hop的误差对比

由图可知，改进DV-hop的平均定位误差明显比经典DV-hop的低，并且改进定位算法的平均误差相对比较稳定。因为改进的DV-hop算法考虑未知节点附近参考信标节点的可信度和信标节点到未知节点的跳距，这样使离未知节点越远的信标节点对其定位起的作用较小。同理信标节点的可信度越低，对未知节点定位时赋予其较小的权重。这样使得未知节点得到的跳距更接近真实值，从而减小误差。

4 结束语

对无线传感网络的节点定位进行了简要分析，对DV-hop定位算法的原理和实现过程进行了详细陈述，并就其定位误差进行分析。利用加权的思想对DV-hop的跳距进行修正，提高了精度。最后通过仿真实验对改进DV-hop和经典DV-hop进行对比，得出改进DV-hop的误差有较大的优化。

[1] 申屠明.无线传感器网络定位算法研究[D].杭州:浙江大学,2007.

[2] 马淑丽,赵建平.多通信半径的无线传感器网络DV-Hop定位算法[J].传感技术学报,2016,29(4):593-600.

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

[4] 刘 啸,刘玉龙.一种改进的无线传感器网络节点定位算法[J].计算机技术与发展，2014，24(4):92-95.

[5] 李 冬.基于DV-Hop的无线传感器网络定位算法研究与改进[D].南京:南京理工大学,2013.

[6] LI Changyun,ZHAO Peizhe,ZENG Yu.Improved DV-Hop localization algorithm for wireless nodes in the smart grid[C]//26th Chinese control and decision conference.[s.l.]:IEEE,2014:4535-4540.

[7] 顾亦然，蒋璐璐.一种改进无线传感器网络的DV-Hop定位算法[J].计算机技术与发展，2012,22(12):109-112.

[8] 潘琢金,刘文春,罗 振,等.无线传感器网络DV-Hop定位算法的改进[J].计算机工程与设计,2016,37(7):1701-1704.

[9] 王小辉，李圣普，吕海莲.基于布谷鸟算法的WSN节点定位研究[J].计算机技术与发展，2014,24(12):208-211.

[10] ZHOU Gongqian,YANG Lujing,LIU Zhong.Wireless sensor network node localization based on error bound DV-Hop algorithm[C]//28th Chinese control and decision conference.[s.l.]:IEEE,2016：2390-2396.

[11] ZHANG Ying,ZHU Zhuling.A novel DV-Hop method for localization of network nodes[C]//Proceeding of the 35th Chinese control conference.[s.l.]:[s.n.],2016：8346-8351.

[12] 刘士兴，黄俊杰，刘宏银，等.基于多通信半径的加权DV-Hop的定位算法[J].传感技术学报,2015,28(6):883-887.

[13] WANG Ying,FANG Zhiyi,CHEN Lin.A new type of weighted DV-Hop algorithm based on correction factor in WSNs[J].Journal of Communications，2014，9(9):699-705.

[14] ZHENG Jiuhu, QIAN Huanyan, WANG Lie.An improved DV-Hop positioning algorithm for wireless sensor network[C]//IEEE international conference on progress in information and computing.[s.l.]:IEEE,2015：492-497.

[15] 侯志伟,包理群,安丽霞.基于残差加权的三维DV-Hop改进WSN定位算法[J].计算机应用与软件,2016,33(1):112-115.