摘要：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)的核算公式：
其间，(xi，yi)、(xj，yj)分别为锚节点i、j的坐标；hij为两个锚节点之间的跳数。不知道节点只接纳离它最近的锚节点的AHDi，hopi为不知道节点离最近锚节点的跳数，再依据跳数信息，即可算得不知道节点与锚节点的间隔P：
P=AHDi×hopi (2)
③当不知道节点取得3个或许更多的锚节点信息时，可以运用三边定位或许最大似然类似求出不知道节点的方位。(x，y)为不知道节点的坐标，(xi，yi)为已知锚节点的坐标。依据式(2)即可算出不知道节点的坐标：
2 改善后的DV—Hop算法
本文主要对DV—Hop算法里的第2步和第3步进行改善，第1步与原算法相同。原算法中，在第2步核算均匀跳距的时分，不知道节点接纳来自最近的锚节点的均匀跳距。可是由于网络节点散布的不均匀性，导致单个锚节点核算的均匀跳距存在着必定的差错，因而本文引进全网均匀跳距与单个锚节点均匀跳距的均值来批改原算法中的均匀跳距。在第3步中，锚节点的方位信息对定位精度影响很大，本文运用节点间连通度的不同，选取最优的3个锚节点，以减小定位差错。
2．1 均匀跳距的改善
将全网均匀跳距与单个锚节点预算出来的AHDi取均匀来替代经典算法中的均匀跳距，这样不知道节点既有全网的预算信息，也具有离它最近的锚节点的预算均匀跳距AHDi的部分信息。全网均匀跳距公式为：
其间，n为网络中的锚节点的个数。
批改后的均匀跳距AHD公式为：
AHD=(AHDall+AHDi)／2 (5)
2．2 依据挑选性的3个锚节点
依据挑选性的锚节点的定位算法运用连通度的不同，在三边节点定位时，挑选最优的3个锚节点定位，使其定位差错最小。节点散布图如图1所示。不知道节点N1运用三边定位时可以用不同的3个锚节点组(P1，P2，P3)、(P1，P2，P4)、(P2，P3，P4)、(P1，P3，P4)来定位。而用最大似然估量核算时，则选用(P1，P2，P3，P4)来定位，这样不同的锚节点组肯定会发生不同的定位方位。
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种或许：
其间，AHD(i,j,k),m为依据3个锚节点组合所预算的方位节点与锚节点Am之间的均匀跳距，AHDn,m为锚节点An与锚节点Am之间的均匀跳距，AHDm为锚节点Am的均匀跳距。
N(i,j,k)与锚节点Am之间的间隔P(i,j,k)，m可以核算出来，那么就可以算出N(i,j,k)与锚节点Am之间的跳数hop(i,j,k)，m，公式为：
假定一共有n个锚节点，这样N(i,j,k)与Nx核算出来的连通度的不同可以标明为
Nx选出最小的连通度不同的节点是最为挨近Nx的节点(即定位的差错最小)。
3 算法仿真试验
为了验证算法理论的可行性，在100 m×100 m的区域中，对提出的改善的DV—Hop算法用Matlab7．0进行试验仿真，将试验成果与原DV—Hop算法和参考文献的算法进行比照剖析。仿真数据随机运转50次，终究取均匀值。
3．1 测距差错
测距差错是指节点间的预算间隔与实践间隔的差值。在100 m×100 m的区域中，随机散布100个节点进行仿真试验，其间有一部分布置的是锚节点，是可以获悉本身方位信息的节点，且锚节点和不知道节点具有相同的通讯半径。经过设置不同的锚节点份额和节点通讯半径，比较改善的算法与原DV—Hop算法对测距差错的影响。图3为通讯半径为10 m时的测距差错，图4为通讯半径为20 m时的测距差错。
在同等条件下，改善的测距差错始终是低于原DV—Hop算法的，且不同的通讯半径对测距差错也会发生不同的成果。图3中，通讯半径为10 m，改善后的算法均匀测距差错比原算法下降1．45 m；图4中，通讯半径为20m，改善后的算法均匀测距差错比原算法下降1．67 m。这是由于跟着通讯半径的改变，会对节点间的跳数和均匀跳距发生影响。由于本文改善后的算法是用全网的均匀跳距替代单个节点的均匀跳距，这样使得对均匀跳距的估量更为精确，预算间隔也就越精确，越挨近实践的间隔。
3．2 定位差错
定位差错(Localization Error，LE)是指经过定位算法丈量估量的坐标与实践坐标之间的差值，用这种差值除以节点的通讯半径，便是定位差错率。核算办法如下：
其间，(x，y)为不知道节点的实践坐标，(xi，yi)为定位算法所估量出来的坐标；R为节点的通讯半径。
图5和图6是节点总数分别为100和300、节点通讯半径为10 m时，本文改善算法、DV—Hop算法和参考文献中的算法三者在锚节点份额不一起的定位差错比较成果。从两幅图中可以看出，在相同的半径和锚节点的环境下，改善算法的定位差错率要低于DV—Hop算法和参考文献中的算法。可是在锚节点份额较低的状况下，节点的定位差错较大。这是由于锚节点较少时，不知道节点与锚节点之间的间隔变远，导致核算均匀间隔时会发生很大的差错。因而跟着锚节点份额的增加，可以有效地减小定位差错。
图5中，当锚节点的份额为30％时，DV—Hop的定位差错率为43．25％，参考文献算法的定位差错率为33．37％，而本文改善算法的定位差错率为28．34％。图6中，当锚节点的份额为30％时，DV—Hop的定位差错率为26．89％，参考文献算法的定位差错率为14．95％，而本文改善算法的定位差错率为10．21％。由此阐明，本文的改善算法要优于其他两种算法。这是由于在参考文献中，只考虑了均匀跳距一个要素对定位差错的影响，而本文改善算法则是从均匀跳距的改善和运用连通度的不同选取锚节点两个方面考虑，使其定位差错进一步地减小。
结语
本文首要介绍了DV—Hop算法的根本思想，针对经典的DV—Hop算法中存在的定位精度不高的缺点，提出了两点改善：
单个锚节点所估量的均匀跳距来替代全网的均匀跳距，会发生很大的差错，因而均匀跳距运用全网均匀跳距与单个锚节点估量的均匀跳距的均值来批改；
依据连通度的不同挑选最优的三个锚节点进行三边定位核算，以进步定位精度。
仿真试验数据标明，改善后的算法下降了测距差错，与参考文献等提出的算法比较，定位差错率进一步下降，然后进步定位精度。且在改善的过程中，没有增加硬件本钱。
