基于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)表示。

作者：乔峰，王思民 青岛科技大学   来源：山西电子技术