无线自组网中一种蒙特卡罗定位新算法

王丹 齐理 王帅

【摘要】 在无线Ad Hoc网络中，本文提出一种基于测距的序列蒙特卡罗定位算法，使定位精度大大提高，对于比传感器节点能够携带更多硬件与电源的无线自组网节点来说，这种新的定位算法有很强的实用意义。

【关键词】 Ad Hoc 定位 蒙特卡罗 无线传感器网络

【Abstract】 A new algorithm of Sequential Monte Carlo localization based on distance measurement is presented in this paper. The localization accuracy is greatly improved. For the ad hoc nodes which can carry more hardware and electricity than wireless sensor network nodes. This new localization algorithm has a strong practical significance.

【Key words】 localization；Monte Carlo；wireless sensor networks

一、引言

目前除了蒙特卡罗定位算法，几乎没有专门为动态传感器网络设计的定位算法。在绝大多数文献中，为了支持动态传感器网络的定位，仅仅提出了将静态环境下适用的定位算法每间隔一段时间执行一次从而实现对动态节点的定位。在很多情况下，因为该方法会使那些需要依靠来自较远处的节点的信息的定位算法遭受到非常严重的数据延迟的限制，很有可能当远处节点所需的信息到达它时，整个网络的结构以及拓扑都发生了变化，这样节点的定位将失去精确性。因此，上述方法并不适用于动态环境下的传感器网络定位。分析发现，上述方法不适用于动态环境的主要原因并不是信息的稀缺或是算法本身的不精确，而是由于定位算法收集信息的方式，导致了定位算法的可靠性大大降低。为了提高定位算法的精确度和可靠性，本文基于蒙特卡罗方法提出一种序列蒙特卡罗定位方法，解决了在动态环境情况下传感器网络节点的定位问题。

二、序列蒙特卡罗算法原理

由于传感器节点以及定位精度的原因，使得移动无线自组网中的定位比机器人定位难得多。但是，使用这种定位方法，在网络中节点间可以通过合作来共享位置信息来实现定位。

将时间分成离散的时间片，因为节点都在相对于之前的位置移动，所以在每个时间单元内都需要对节点进行重新定位。想要得到节点可能位置的概率分布，从而协助定位。因为节点在网络中持续运动，之前的位置信息对目前的位置来讲将会越来越无用。从另一方面来说，可以根据从锚节点新收到的观察信息滤除不正确的估计位置估计。在移动并接收了观察信息之后，节点之前可能位置的概率分布就更难确定了。除了一些特殊的情况（线性高斯状态模型 卡尔曼滤波器），想要用数值法解出之前的分布几乎是不可能的。

序列蒙特卡罗法提供了一种基于仿真的方法用于估计之前的非线性离散时间动态模型的位置分布。序列蒙特卡罗法的核心思想就是通过一系列，N个带有权重的采样，使用“重要性采样”（importance sampling）法，递归的对这N个带有权重的采样进行更新。序列蒙特卡罗定位法已经成功地应用在目标跟踪，机器人定位与计算图形学中。

三、基于测距的序列蒙特卡罗定位算法

序列蒙特卡罗方法虽然相对于其它现有的定位算法更适于动态传感器网络，但是这种算法仍然存在定位精度较低的不足。针对这个问题，这部分基于序列蒙特卡罗算法，提出一种基于测距的蒙特卡罗定位算法，解决了动态传感器网络定位精度较低的问题。

基于以上的序列蒙特卡罗定位算法，再考虑到无线自组网节点相对于传感器节点存在着能够携带更多电能，机能相对强大等优势，在节点上加装测距模块的可行也相对更高，本文提出一种基于测距的序列蒙特卡罗算法，算法与传统序列蒙特卡罗算法类似，但由于位置生成步骤相对简单了许多，于是与前一步骤合并，故步骤分为三步：

⑴位置预测：根据滤波后的位置估计，对下一步可能位置进行预测，在N个估计点周围以本步估计位置为圆心，v为半径的圆形区域内生成N个预测点。

⑵收取观测信息：由于是基于测距的定位算法，故未知节点可直接测得在自身测距半径d内的锚节点到自己的距离r，并将此距离保存。

⑶位置滤波与位置生成：根据以上观察信息，将不可能的位置估计从估计矩阵中删除，删除后根据观测信息将删除的估计点数与预测点数补齐，假设r为测得距离，e为测距误差，删除与预测策略如下：

Ⅰ.若在自身测距半径d内只有一个锚节点，则将预测中不在以该锚节点为圆心，r为半径，e为测距误差的圆环上的预测点及下步位置估计删除，并在该圆环中随机生成本步估计点坐标，并根据运动模型预测下步坐标。

Ⅱ.若在自身测距半径d内有两个锚节点，则根据两圆相交关系可求出该未知节点的两个可能存在的位置，将位置预测中不在以这两个位置为圆心，测距误差为半径的小圆外的预测点及下步位置估计删除，并在这两个小圆内生成位置估计点坐标，并根据运动模型预测下步坐标。

Ⅲ.若在自身测距半径d内有两个以上锚节点，根据多圆相交关系，可以确定出未知节点的位置，再将以该位置为圆心，测距误差为半径的小圆外的预测点及下步位置估计删除，并在此小圆内生成位置估计点坐标，并根据运动模型预测下步坐标。

Ⅳ.若没有任何消息，则不删除位置估计与位置预测。

四、基于测距的序列蒙特卡罗定位算法仿真分析

在仿真环境中，节点被随机的撒在一个250m x 250m的矩形区域，我们给节点设定一个固定的通信半径r，锚节点与未知节点的通信半径r都等于25m，节点采用自由随机运动模型，可以变化的各项参数如下：

⑴锚节点与未知节点最大速度v：每个节点的速度都服从[0，v]的均匀分布

⑵未知节点密度：在1倍通信半径范围内的平均未知节点数。可以用下式计算：

由以上一组图可以发现，在锚节点密度较低，如sd=1时，定位精度较差，结果并不比传统非测距序列蒙特卡罗算法好很多，但当锚节点密度提高时，定位精度增加比较明显，在其他条件不变，sd=4时，其定位精度13.13%要远好于传统序列蒙特卡罗方法的40%左右，虽然由于测距模块的引进可能引起网络节点的体积增加以及耗电量增大等结果，但对于通常情况下的无线自组网节点，如PDA，笔记本电脑等来说，这样的体积增加与耗电量增大一般来说是可以接受的，故这种定位算法具有较强的实用性。

3.2测量误差

当sd=4，nd=10，v=d=25，N=10，e=0时，如图4所示。

由返回误差数据计算得到，当测距误差为0时，定位稳定后的平均定位误差约为13.13%。

当sd=4，nd=10，v=d=25，N=10，e=5%时，如图5所示。

由返回误差数据计算得到，当测距误差为5%时，定位稳定后的平均定位误差约为24.95%。

当sd=4，nd=10，v=d=25，N=10，e=15%时，如图6所示。

由返回误差数据计算得到，当测距误差为15%时，定位稳定后的平均定位误差约为31.90%。

由以上一组图以及数据可以发现，测距误差也是影响定位精度的一个重要参数，当测距误差提高后，精度下降的比较明显，原因是很显然的，如果测距出现误差，那么之后的对节点位置计算估计等都会出现误差，由于误差的重叠积累导致了结果的误差，所以高精度测距模块的选择也是提高定位精度的一个有效方法。

五、结语

本文在传统序列蒙特卡罗定位算法的基础上提出了一种基于测距的序列蒙特卡罗定位算法，从而在条件相似的情况下，明显地提高了动态传感器网络节点的定位精度。仿真结果表明，这部分提出算法的定位精度将远高于序列蒙特卡罗算法，从而有效解决了动态传感器网络定位精度较低的问题。