无线传感器网络DV-Hop定位改进算法

　　无线传感器网络(Wireless Sensor Networks)是当前在国际上备受关注的、涉及多学科高度交叉、知识高度集成的前沿热点研究领域 .对于传感器网络来说， 传感器节点的位置信息至关重要， 事件发生的位置或获取信息的节点位置是传感器节点监测消息中所包含的重要信息， 没有位置信息的监测数据往往毫无意义。因受成本、功耗、扩展性等问题的限制， 为每个传感器安装GPS模块等这些传统定位手段并不实际， 甚至在某些场合可能根本无法实现， 而且GPS定位在定位精度、实时性方面有时并不能满足特定的需求， 因此针对具体的定位需求， 必须采用一定的算法机制来实现传感器节点的定位。

　　无线传感器网络节点按定位过程中是否需要测距信息， 可分为无需测距的定位方法和基于测距技术的定位方法。近年来， 关于传感器网络节点定位技术研究成为无线传感网络技术的一重要研究热点并取得大量的研究成果。其中， 具有代表性算法研究成果有： 凸规划算法及其改进算法 , APS 算法、Cooperative Ranging 、AHLos 算法、nHopMultilateratiON Primitive 算法、MDS-MAP 算法等。

　　无需测距的定位方法被认为是一类具有好的成本效益的解决方案。在无需测距定位方法中， DV-Hop( DiSTance Vector-Hop) 节点定位方法由于对信标节点比例要求较少， 定位精度较高， 目前已成为一种经典的无需测距定位方法。

　　DV-Hop定位方法的主要思想是引入最短路径算法到信标节点的选择过程中， 从而在未知节点的位置估计过程中可以有效利用多跳信标节点的位置信息， 这种方法可以大大减少实现网络定位所需信标节点的比例(密度)， 从而大大降低网络的布置成本。

　　本文就DV-Hop算法的误差成因进行了分析，在DV-Hop 定位算法优点的基础上， 针对该算法只适用于各向同性网络的不足， 对DV Hop 算法进行局部优化， 使得改进后的DV-Hop 算法减少了数据包发送量， 提高了定位精度， 并且对于不规则形状的节点分布具有较强的适应性。

　　1 DV-Hop 定位算法

　　DV-Hop定位算法是APS算法系列中使用最为广泛的定位方法， 其定位过程不依赖于测距方法， 利用多跳信标节点信息来参与节点定位， 定位覆盖率较大。DV-Hop 算法非常类似于传统网络中的距离向量路由机制， 在该定位机制中， 未知节点首先计算与信标节点的最小跳数， 然后估算平均每跳距离， 利用最小跳数乘以平均每跳距离， 估算得到未知节点与信标节点之间的距离， 再利用三边测量法或极大似然估计法计算未知节点的坐标。

　　DV-Hop定位算法可以分为以下3个阶段：