内容摘要：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计算出来的连通度的不同可以表示为
上一篇：电缆自动检测电路
