摘要：DV-Hop算法是无线传感器网络中一种典型的基于非测距的定位算法。针对DV-Hop存在的定位精度低的缺陷，本文提出了改进的算法。该算法中的平均跳距利用全网平均跳距与单个锚节点估计的平均跳距的均值来修正，并且根据连通度不同，选取最优的3个锚节点进行三边定位计算。
关键词：无线传感器网络；DV—Hop算法；平均跳距；连通度的不同；三边定位；定位精度
引言
无线传感器网络是由大量随机分布的传感器节点组成，是一种分布式的、自组织的网络。其关键技术包括：网络拓扑控制、节点定位、时钟同步、数据融合、路由协议等。而节点定位问题则是无线传感器网络中的一个最为基本和重要的问题。目前，无线传感器网络定位算法可以分为基于测距和基于非测距的定位算法。基于测距定位常用的测量方法有TOA、TDOA、AOA、RSSI，尽管这些技术相对精度高，但是对硬件要求很高。基于非测距定位常用的测量方法有：DV-Hop、质心、APIT、MDS—MAP。
DV—Hop为典型的基于非测距定位，其对硬件要求低，实现简单。它的不足之处在于计算平均跳距及定位坐标时会产生误差。因此针对DV—Hop算法的缺陷，提出了一系列的改进算法，参考文献对原始算法中的平均跳距进行改进，使用多个锚节点估算平均距离并且采用归一化加权的平均跳距。参考文献提出了基于几何学的定位算法，利用几何学中的斜率方法来判断锚节点间的位置关系，从中选取最优的锚节点序列，从而更精确地确定未知节点。参考文献引入共线度的概念，利用共线度参数，动态地调节未知节点可以收集的邻居锚节点的距离阈值，挑选网络中好的锚节点组进行位置估计，最后再用加权估计机制来得到最终的节点位置估计。这些方法都在一定程度上提高了定位精度。
本文针对DV—Hop算法中计算平均跳距和三边定位两方面存在的定位误差，提出了改进的算法。首先利用全网平均跳距来纠正单个锚节点的平均跳距，然后在最后计算三边定位时，利用节点间连通度的不同，选择最优组合的3个锚节点来参与定位，进一步提高定位精度。
1 DV—Hop算法介绍美国路特葛斯大学的Dragos Niculescu等人利用距离矢量路由和GPS定位原理提出一系列分布式定位算法，合称APS，DV—Hop算法就是其中的一种。
DV—Hop分为3个步骤实现：
①锚节点i广播自身的位置信息IDi。初始跳数0，每发送一个节点信息，跳数就加1，然后转发，直到网络中所有的节点都收到锚节点的信息包。如果节点收到同一个锚节点不同的跳数信息，只取最小的跳数信息。
②当锚节点i接收到其他锚节点的位置和最小跳数信息后，就可以计算出平均每跳距离(Average Hop Distance，AHD)的计算公式：
2．2．1 基本规则用未知节点与每个锚节点的最小跳数来定义连通度，用数组来表示。比如N1到所有锚节点的连通度为[1，1，2，5]。这样图1中的所有的未知节点的连通度可以用数组表示，如表1所列。
用未知节点之间连通度差的绝对值的和来定义连通度的不同，比如N1与N2之间连通度的不同为|1—2|+|1—1|+|2—1|+|5—4|=3。这样可以计算N1到其他所有未知节点的连通度的不同，如表2所列。
由表2可以得出，N2、N3到N1连通度不同为3、4，而N4、N5到N1连通度不同为9、11。说明N1离N2、N3更近。这一点也可以从图1中看出。
2．2．2 确定最优的3个锚节点选择性锚节点的节点分布图如图2所示。未知节点Nx代表未知节点的实际位置，N(i,j,k)为根据3个锚节点组合所估算的位置，R为节点的通信半径，An是离N(i,j,k)最近的锚节点，Am为通信范围R之外的任意锚节点。
An的位置情况有3种：在0．5R的通信范围内；在0．5R～R的通信范围内；在R通信范围之外。这样计算AHD(i,j,k)，m就有3种可能：
在同等条件下，改进的测距误差始终是低于原DV—Hop算法的，且不同的通信半径对测距误差也会产生不同的结果。图3中，通信半径为10 m，改进后的算法平均测距误差比原算法降低1．45 m；图4中，通信半径为20m，改进后的算法平均测距误差比原算法降低1．67 m。这是因为随着通信半径的变化，会对节点间的跳数和平均跳距产生影响。由于本文改进后的算法是用全网的平均跳距代替单个节点的平均跳距，这样使得对平均跳距的估计更为准确，估算距离也就越准确，越接近实际的距离。
3．2 定位误差定位误差(Localization Error，LE)是指通过定位算法测量估计的坐标与实际坐标之间的差值，用这种差值除以节点的通信半径，就是定位误差率。计算方法如下：
图5中，当锚节点的比例为30％时，DV—Hop的定位误差率为43．25％，参考文献算法的定位误差率为33．37％，而本文改进算法的定位误差率为28．34％。图6中，当锚节点的比例为30％时，DV—Hop的定位误差率为26．89％，参考文献算法的定位误差率为14．95％，而本文改进算法的定位误差率为10．21％。由此说明，本文的改进算法要优于其他两种算法。这是因为在参考文献中，只考虑了平均跳距一个因素对定位误差的影响，而本文改进算法则是从平均跳距的改进和利用连通度的不同选取锚节点两个方面考虑，使其定位误差进一步地减小。
结语本文首先介绍了DV—Hop算法的基本思想，针对经典的DV—Hop算法中存在的定位精度不高的缺陷，提出了两点改进：
单个锚节点所估计的平均跳距来代替全网的平均跳距，会产生很大的误差，因此平均跳距利用全网平均跳距与单个锚节点估计的平均跳距的均值来修正；
根据连通度的不同选择最优的三个锚节点进行三边定位计算，以提高定位精度。
仿真实验数据表明，改进后的算法降低了测距误差，与参考文献等提出的算法比较，定位误差率进一步降低，从而提高定位精度。且在改进的过程中，没有添加硬件成本。
