无线传感器网络定位技术综述

3) 极大似然估计法。如图4 所示， 已知n 个点的坐标和它们到未知节点的距离， 列出坐标与距离的n 个方程式， 从第1 个方程开始， 每个方程均减去最后一个方程， 得到n?1 个方程组成的线性方程组，最后用最小二乘估计法可以得到未知节点的坐标。

图4 极大似然估计法原理示意图

4) 极小极大定位算法， 在无线传感器网络定位中也被广泛使用。如图5 所示， 计算未知节点与锚节点的距离， 接着锚节点根据与未知节点的距离d, 以自身为中心， 画以2d 为边长的正方形， 所有锚节点做出的正方形中重叠的部分的质心就是未知节点的坐标。针对极小极大定位算法对锚节点密度依赖过高的问题， 有学者利用锚节点位置信息提出了分步求精定位算法， 该算法在只利用适量的锚节点的情况下可达到较高定位精度。

图5 极小极大定位算法原理示意图

文献[35]在12 m×19.5 m 的范围内对上述三边测量法、极大似然估计法和极小极大法方法的计算量和精度进行了测试。实验表明， 极大似然估计法的计算量最大， 锚节点小于10 个时， 极小极大法的计算量最小， 在锚节点较少情况下， 三边法和极小极大法的精确度较高， 而当锚节点超过6 个时， 极大似然估计法精确度更高。因此， 在计算坐标时要根据实际情况合理选择坐标计算方法。另外， 针对现存的定位算法都是假设信标节点不存在误差， 与真实情况不符的情况， 文献[36]提出信标优化选择定位算法(OBS)， 即通过减小定位过程中的误差传递来提高定位精度。

3.2 基于非测距的算法

基于非测距的算法与测距法的区别在于前者不直接对距离进行测量， 而是使用网络的连通度来估计节点距锚节点的距离或坐标， 由于方法的不确定性， 基于非测距的方法众多。下面按时间顺序，介绍部分典型非测距定位算法。

Bulusu 等人提出了一个单跳， 低功耗的算法，它利用锚节点的连通性来确定坐标。未知节点的坐标通过计算无线电范围内所有节点的质心获得。节点将自己定位在与它们表现相近节点的质心处， 该算法虽然简单， 但误差较大， 需要的锚节点密度较高。约90%节点的定位精度在锚节点分布间距的1/3以内。

He 等人提出了APIT 算法， 目标节点任选3 个相邻锚节点， 测试未知节点是否位于它们所组成的三角形中。使用不同锚节点组合重复测试直到穷尽所有组合或达到所需定位精度。最后计算包含目标节点的所有三角形的交集质心， 并以这一点作为目标节点位置， 该算法需要较高的锚节点密度， 其定位精度为40%。

Niculescu 等人提出了DV-Hop 定位算法， 它从网络中收集相邻节点信息， 计算不相邻节点之间最短路径。DV-Hop 算法使用已知位置节点的坐标来估测一个跳跃距离， 并使用最短路径的跳跃距离估计未知节点和锚节点的距离， 该算法仅适用于各向同性的密集网络， 当锚节点密度为10%时， 定位误差为33%。

Radhika 等人提出的Amorphous Positioning 算法，使用离线的跳跃距离估测， 同DV-Hop 算法一样， 通过一个相邻节点的信息交换来提高定位的估测值，需要预知网络连通度， 当网络连通度为15 时， 定位精度20%。

Savvides 等人介绍了一种N-Hop multilateration算法， 使用卡尔曼滤波技术循环求精， 该算法避免了传感器网络中多跳传输引起的误差积累并提高了精度， 节点通信距离为15 m, 当锚节点密度为20%,测距误差为1 cm 时， 定位误差为3 cm。

Capkun 等人提出了self-positioning algorithm(SPA)， 该算法首先根据通信范围在各个节点建立局部坐标系， 通过节点间的信息交换与协调， 建立全局坐标系统， 网络中的节点可以在与它相隔N 跳的节点建立的坐标系中计算自己的位置。

综上可知， 非测距算法多为理论研究， 其定位精度普遍较低并且与网络的连通度及节点的密集程度密切相关， 因此， 其适用范围有一定的局限性， 在进行无线传感器网络定位技术研究过程中应更多地考虑基于测距的定位算法。