基于无须测距的定位算法应用实例

基于测距的定位系统算法虽然能够实现精确定位,但往往也对硬件要求较高,导致硬件成本增加,不利于大面积、多领域、广角度的使用。无须测距的定位算法使用起来比较简单,只需要利用未知节点到参考节点之间的估计距离值或其他位置信息,然后用三边测量法或极大似然估计法来计算出未知节点的坐标信息。无须测距定位算法由于不需要精确测量节点间的距离信息,极大地降低了对节点硬件的要求。现有的基于无须测距的定位算法主要有:DV-HOP算法、质心算法、Amorphous算法、APIT算法、凸规划算法和MDS-MAP算法等。

(1)质心定位算法(Centroid)

在传感器网络中,质心是指多边形的几何中心。质心定位算法是University of Southern California的Nirupama Bulusu等提出的,该算法适用于室外节点密度较高情况下的定位,它是基于网络的连通性(Connectedness)实现对节点的定位。其基本思想是:未知节点根据自身设定的门限值来接收周围信标节点所发出的包含节点位置和ID的信息来确定其所在的区域,根据其接收到的信标节点的ID及位置信息计算所在区域的质心,并把这个区域的质心作为自身的定位结果。该算法简单易行,对硬件要求较低,不需要额外任何硬件设备,但在定位过程中需要较多的信标节点,另外该算法在定位过程中都假设节点拥有理想的无线信号传输模型,这与实际的情况还有很大的差别,因此影响了Centroid的定位精度。

(2)不定型定位算法(Amorphous)(www.xing528.com)

Amorphous是基于连通性的定位算法,它需要预先知道网络的连通度。算法实现过程中,首先未知节点计算与每个信标节点之间的最小跳数;然后计算未知节点到每个信标节点的跳段距离,其中假设网络中节点的通信半径相同;最后再利用Trilateration或MLE等算法来进行定位计算。Amorphous实现起来比较简单,但定位精度不是很高,另外还有两个显著的缺点:一是需要预先知道网络的连通度;二是定位过程中需要较高的节点密度。

(3)近似三角形内点测试法(APIT)

APIT(Approximate Point-in-Triangulation Test)算法能够以较高的定位精度适应于复杂的地理环境。APIT定位算法在实现过程中未知节点首先通过收集邻居节点的节点标识符、位置信息、发射信号功率的大小等信息来确定该节点是否位于不同的信标节点所组成的三角形内,然后统计包含未知节点的三角形区域,并把这些三角形区域的交集构成一个多边形,这个多边形基本上确定了未知节点所在的区域并缩小了未知节点所在的范围,最后计算这个多边形区域的质心,并将质心作为未知节点的位置,这样就实现了未知节点的定位。