一种网络跳距修正的分布式定位算法研究

　　无线传感器网络[1-2]WSN( Wireless Sensor Network)是由大量低成本、低功耗的微型传感器节点以无线通信的方式自组织形成的分布式网络。WSN由于具有感知能力、通信能力和计算能力，使其受到越来越多的关注与应用。但是，在大多数应用环境中需要知道传感器节点或监控目标的位置信息，否则，无线传感器网络感知的数据是无实际意义的，由此可知，节点的自定位对WSN 具有重要意义。

　　目前，国内外已经提出了很多种算法来解决无线传感器网络节点定位问题。WSN 根据是否测量节点间距离将算法分成两大类: 基于测距( Range-Based) 算法和无需测距( Range-Free) 算法[3-4]。Range-Based 算法需要实际测量节点间点到点的距离或角度信息来获得未知节点的位置，其中包括的定位技术[1]有TOA、TDOA、RSSI 和AOA 等，基于测距的算法对节点硬件的要求较高，使得该类定位算法在成本和节点规模大小都受到了限制。Range-Free 算法不需要测量节点间的距离或角度信息，对节点的硬件要求比较低，网络的功耗成本低，因此较适合于能量受限的无线传感器网络。目前已提出的无需测距算法有DV-Hop[5]、Amorphous、质心算法和APIT 算法[6]等算法。

　　在WSN 中，DV-Hop 算法是比较典型的一种定位方法。目前，有很多文章针对该算法定位误差大等缺点展开了研究，如文献[7-10]中分别对算法进行了改进，其中文献[7]是根据跳数来调节节点定位过程，并在局部范围内索取定位信息完成定位; 文献[8]提出了一种用跳数比值替代距离比值，并在单跳距离中引入RSSI 的改进方案; 文献[9]是对所有信标节点计算的平均每跳距离相加取平均来计算节点的位置; 文献[10]采用了对平均每跳距离进行加权处理修正的方法对算法进行了改进。本文主要参考文献[9-10]对DV-Hop 定位算法进行了研究，研究其定位误差来源，提出改进方案，并通过仿真实验，对改进算法与文献[9-10]中的改进方案进行了性能分析对比。

　　1 算法描述

　　1. 1 DV-Hop 定位算法

　　美国路特葛斯大学的Dragos Niculescu 等人利用距离矢量路由和GPS 定位的思想原理提出了一系列分布式定位算法，合称为自组织定位系统，即APS。其中包括DV-Hop、DV-Distance 和DVEuclidean等定位算法。而DV-Hop 定位算法的应用最为成功、最为广泛。

　　DV-Hop 算法由3 个阶段组成。第1 阶段，利用距离矢量交换协议，网络中的未知节点获得与锚节点之间的跳数，锚节点也知道了其他锚节点的坐标及跳数。第2 阶段，每个锚节点根据计算自己的平均每跳距离，并以泛洪的形式广播至整个网络。未知节点接收距离最近锚节点的平均每跳距离，然后再根据第1 阶段求出的跳数，计算与各锚节点之间的估计距离。第3 阶段，当未知节点获得3 个或3个以上锚节点的距离后，利用3 边测量法或极大似然估计定位。