基于MCL算法的无线传感网络节点定位技术

引言

无线传感器网络的应用中，位置信息是节点采集数据时不可缺少的部分，没有位置信息的监测信息通常是毫无意义的。确定事件发生的位置或采集数据的节点位置是无线传感器网络最基本的功能之一。为了能够提供有效的位置信息，随机布置的传感器节点在网络部署完成后必须能够确定自身所在的位置。一般的定位算法分类为基于距离定位算法和距离无关定位算法。基于距离的定位能够实现节点的精确定位，但往往对节点的硬件要求较高。出于硬件成本、能耗等方面的考虑，使用距离无关(Range-free)的节点定位技术可不需要测量节点之间的绝对距离或者方位，降低了对节点的硬件要求，但定位误差相应有所增加。

无线传感器网络的节点定位策略通常使用少量位置已知的信标节点．其它位置未知的普通节点从它们接收到的信息估计自己所处的位置。现有节点定位方法大多采用上述策略，典型的Range-free定位算法主要包括：质心定位、A-morphous、SPA(self-positioning algorithm)、凸规划、APS(adhoc positioning system、APIT等。然而这些方法都没有考虑节点(包括普通节点和信标节点)具有位置移动性的网络情形。节点的移动性会导致定位过程变得更加困难而且复杂。本文使用Monte Carlo定位(MCL)算法来解决节点具有移动性的无线传感器网络的节点定位问题，并针对MCL算法的一些应用限制进行了改进。

l MCL定位算法

MCL算法的核心思想是利用一系列加权采样值表示可能位置的后验概率分布，目的在于确定节点所在可能位置的后验概率分布。算法每一步都包括位置预测和位置更新两个阶段。位置预测阶段是利用m个加权采样值对后验概率分布进行描述的过程，位置更新阶段则是通过重要性采样操作对其进行及时不断更新，采样值的权重值从O和l中取值。

MCL，定位算法的基本步骤：

1．1 位置估计

无线传感器网络节点的移动定位问题可以在如下状态空间内描述。以￡表示离散时间，lt表示f时刻节点的位置分布，Dt表示节点在t-1t时刻到t时刻之间接收到的来自信标节点的观测值。转换方程p(lt|lt-1)表示基于节点先前位置对其当前所在位置的估计。观测方程p(lt，Ot，)表示在给定观测值的情况下节点位于位置lt的概率。算法的目标是对节点位置的滤波分布p(lt|O0,O1,…，Ot)随时间进行反复估计。用一组采样值Lt(N个)表示节点的位置分布lt，而且每一时间段内算法要对采样序列进行反复计算，由于Lt-1是对先前所有观测值的一个集中反映，因此仅使用Lt-1和Ot就可以计算出lt。

位置估计算法的实现流程：

(1)初始化。节点最初不具备任何关于其自身所在N个位置的先验知识，需要对其进行初始化操作(N表示算法执行过程中所要维持的采样数)。

L0=[节点部署区域内随机选择的N个可能位置]

(2)循环计算。根据Lt-1、上一时间段内节点的可能位置序列以及新的观测值Ot计算出节点新的可能位置Lt。

预测：

在算法起始阶段节点对其所在的位置没有任何先验知识。因此可由质心算法估计初始位置。质心算法的核心思想是：普通节点以所有在其通信范围内的信标节点的几何质心作为自己的估计位置。其实现过程非常简单：信标节点向邻居节点广播一个信标信号，信号中包含有信标节点自身的ID和位置信息。当位置未知的普通节点接收到来自信标节点的信标信号数量超过某一个预设的门限值后，该节点认为与此信标节点连通，并将自身位置确定为所有与之连通的信标节点所组成的多边形的质心。

初始位置确定后的每一时间段内．位置序列都会根据节点的运动和新的观测信息进行更新。节点位置的估计可以通过计算集合L内节点的所有可能位置的平均值获得。

1．2 位置预测

在MCL算法位置预测阶段，节点从前一阶段计算出的一组可能位置Lt-1开始，对每个采样值应用节点移动模型从而获得一组新的采样值Lt。假设节点的移动速度和方向未知，而只知道其速度值小于Vmax那么，如果lit-1是节点的一个可能位置，那么节点所在的当前可能位置则位于以lit-1为圆心、半径为Vmax的圆形区域内。如果用d(l1,l2)表示两点l1和l2之间的欧几里德几何距离．而且节点的移动速度在区间[0，Vmax]上服从均匀分布，那么节点基于先前位置的当前位置估计的概率分布可以通过以下均匀分布的形式给出。

因此，在预测阶段计算出的节点可能位置序列R就是以点集Lt-1中的任意一点为圆心且半径为Vmax的圆形区域。

1．3 位置滤波

在滤波阶段，节点需要根据所获得的新观测值滤除不可能的位置信息。为了便于描述和分析，假设在t时刻每个位于信标节点无线射程范围内的节点都可以侦听到来自信标节点的位置信息广播。在实际的网络部署情况下，需要考虑网络冲突并解决消息丢失的问题。

如图l，节点在t0时刻由位置l0开始移动，并在t1时刻到达位置l1，节点离开区域I并到达区域Ⅱ，但始终在区域Ⅲ内。到达节点和离开节点都为节点的位置估计提供信息，节点知道在t0时刻位于以如为圆心且半径为r的圆形区域内的信标节点，在t1时刻并不在l1为圆心且半径为r的圆形区域内。

图2描述了节点的位置滤波条件。图中。S表示节点N能侦听到的所有信标节点分组。T表示节点N的邻居节点可以侦听到而节点N本身无法侦听到的全部信标节点。因此，节点位置l的滤波条件可以由式(2)表示。

###NextPage###

如果滤波条件为假，那么节点位置的概率分布p(lt|Ot)值为零，否则p(lt Ot)将符合均匀分布，这样．就可以从节点的所有可能位置集合中去除那些与观测值不一致的位置。经滤波后，节点剩余的可能位置也许会少于N个。预测过程和滤波过程将不断重复进行，并结合已经发现的节点可能位置,直至获得节点的至少N个可能位置。

1．4 重要性采样

算法的最终目标是估计节点可能位置的后验概率分布p(lt|O0,O1，…Ot)。首先，通过一个标准化重要性采样函数π获得一系列相互独立的节点位置采样值；然后，对每个采样值的权重值进行调整并且使用这些权重值对节点所在可能位置的后验概率分布作出估计。算法采用了下列递归式重要性函数。

式(3)表示节点的位置预测，节点借助先前所在的可能位置预测其当前的可能位置。式(4)表示节点的位置更新，节点根据获得的观测值对新的采样值不断进行权重值更新与调整。然后。通过式(5)对权重值Wit；进行归一化处理得到Wit用权重值序列(lit,wit)对节点位置的后验概率分布作出估计。通过式(3)和式(4)的反复计算，很容易地确定概率值p(lk|lk-1)和p(l1|Ot)的大小。

2 MCL算法优化

传感器节点在计算资源与存储资源等方面一般比较紧缺，可通过多边形内点测试法首先近似确定节点的运行方向，该方法完全基于节点间的连通性，仅需要信标节点的跳数位置广播信息，因此对节点没有额外的功耗和硬件需求。图3为多边形内点测试法的一种情况，如图3(a)假设M获得与A之间的跳数为4，则节点1与A之间的跳数为3，节点2与A之间跳数为5；M获得与B之间的跳数为3，则节点2与B之间的跳数为2，节点1与B之间的跳数为4。当M移动到节点1位置，则可以得出节点M靠近了节点A远离了节点B，可以得出节点M不能同时靠近或远离三个顶点，必定在三角形内部，当节点M同时靠近或远离三个顶点．必定在三角形外部。对图3(b)当节点M从三角形ABC内离开进人三角形ABD中时，即可得到节点的大致运行方向。则式(2)的滤波条件可简化为

此处的T'为节点N在区域ABD内的邻居节点可以侦听到而节点N本身无法侦听到的全部信标节点。

对节点运行方向的估计可大大减少MCL算法的位置预测和位置滤波阶段的计算量，节省了节点的能耗。并且更加容易滤除与观测值不一致的位置．提高定位精度。

3 算法性能评价

在一定的通讯开销和硬件配置条件下，评价一种节点定位方法优劣的重要标准是位置估计精度的高低。通过仿真对MCL．定位算法、改进后的MCL，定位算法和质心定位(Centroid)算法进行了比较。

仿真实验过程中，无线传感器网络、节点以及算法的相关参数都是不断变化的。节点随机部署在一个500 m×500 m的矩形区域内。而且假定信标节点与普通节点的无线传输距离为恒定值r(r=50 m)，节点的位置信息广播之间的时间间隔为固定值tu并且以节点在每一时间段tu内移动的距离r表示节点移动速度。

由图4(a)可以看出，MCL定位算法的精度在初始阶段会随着时间变化提升很快并进入稳定阶段，在稳定阶段，节点新的观测值(位置滤波器)与由于节点移动带来的不确定性对定位精度的影响达到某种平衡，位置估计误差将最终稳定在一个最小值上下波动。可以看出MCL算法的定位精度与质心定位算法相比有着相当大的优势。

图4(b)中可以看出改进后的MCL定位算法能够更快的达到稳定，并且定位精度也有了少许提升。

4 结语

本文提出了将MCL算法应用于无线传感器网络节点定位中。在节点随机运动的情况下，不需要配备额外的硬件设施，就可以获得较高的定位精度,解决了具有移动性的无线传感器网络中的节点定位问题。并在算法初始阶段结合质心算法进行定位．通过估计节点方向来简化算法，优化了MCL算法的定位性能。