无线传感器网络中的DV—HOP定位改进算法

作者：时间：2014-01-23来源：网络收藏

引言
无线传感器网络是由大量随机分布的传感器节点组成，是一种分布式的、自组织的网络。其关键技术包括：网络拓扑控制、节点定位、时钟同步、数据融合、路由协议等。而节点定位问题则是无线传感器网络中的一个最为基本和重要的问题。目前，无线传感器网络定位算法可以分为基于测距和基于非测距的定位算法。基于测距定位常用的测量方法有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)来定位，这样不同的锚节点组肯定会产生不同的定位位置。