一种基于Monte Carlo的移动传感网络精确定位算法 汪炀12黄刘生12吴 ...

1、一种基于Monte Carlo的移动传感网络精确定位算法 汪炀1,2,黄刘生1,2,吴 .摘要： 汪炀 - 相关文章关键词：算法类别：专题技术来源：牛档搜索（Niudown ）本文系牛档搜索（Niudown ）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown ）赞成本文的内容或立场，牛档搜索（Niudown ）不对其付相应的法律责任！一种基于Monte Carlo的移动传感网络精确定位算法汪炀1,2,黄刘生1,2,吴俊敏1,2,徐宏力1,21 （中国科学技术大学计算机系，安徽，合肥，230027）2 （苏州

2、市下一代Web服务计算重点实验室，江苏，苏州，215123）E-mail: 摘 要：无线传感器网络作为一种全新的信息获取和处理技术，可以在广泛的应用领域内实现复杂的大规模监测和追踪任务。在传感器网络中，确定事件发生的位置或获取消息的节点位置是传感器最基本的功能和支撑技术。本文针对特定的应用场景，设计了适用于锚节点固定，节点自由移动的移动传感器网络的基于Monte Carlo方法的精确定位算法，并描述了其节点运动预测和位置选取模型，最后通过实验将本算法与以往研究成果中的代表性的移动传感器网络定位算法进行了模拟比较和分析。关键词：移动传感器网络定位；Mont

3、e Carlo；牛顿插值中图分类号：TP 文献标示码：A 文章编号:1000-1220（2005）02An Accurate Localization Algorithm Based on MCL for Mobile Sensor NetworksWANG yang1,2, HUANG Liusheng1,2, WU Junmin1,2, XU Hongli1,21 （Department of Computer & Technology, University of Science & Technology of China，Anhui，Hefei，230027,China）2 （Suzh

4、ou Key Lab of Next Generation Web Services Computing，Jiangsu，Suzhou，215123,China）Abstract: As a new technology of data-gathering, Wireless sensor networks can be widely used so as to realize massive monitoring and tracking. It is the most basic support function of WSNs to ensure the location of the

5、information. In this paper, an accurate localization algorithm based on MCL for mobile sensor networks is designed for special application scenes, Which include the movement prediction model and the location selection model. Finally, a simulation is processed to compare this algorithm with some othe

6、r typical methods.Key words: Mobile Sensor Networks, Monte Carlo, Newtown interpolation1 引言定位问题对于无线传感器而言是非常有意义的，因为其主要应用于布线和电源供给困难的区域、人员不能到达的区域、移动目标的跟踪和一些临时场合1。无线传感器网络要在这些特殊行业领域展开应用，首先要实现的就是节点自定位。此外，基于定位的路由协议能够显著的减小能耗2,3,4，系统安全性也会因此而得到提高5,6。现有的对于无线传感器网络定位问题的研究主要分为基于距离的定位算法和距离无关的定位算法7，基于信标节点的定位算法和无信标节

7、点的定位算法8等，但是他们都被如下的某些问题困扰着：依赖于特殊的硬件：基于信号强弱来测量距离的RSSI算法，例如RADAR9系统；基于到达时间TOA10算法，到达时间差的TDOA11,12算法和基于到达角度的AOA13算法都需要在无线传感器节点上增加额外的硬件，这对于节点来说，既增加成本又增加了节点的体积。需要明确的网络拓扑：大部分现有的算法都需要数量众多的信标节点并且被有效的撒布来覆盖整个网络。但是在很多无线传感器网络的应用中，信标节点的预先撒布都是不可能的。虽然基于跳数的定位技术14,15不需要大量的信标节点，但是它们要求节点的分布是密集统一的。我们着重研究了如何在更加普遍的网络环境中实现

8、节点的自定位。在我们研究的环境中，信标节点的预先分布是未知的，信标节点的密度较低，节点分布是不规则的并且节点和信标节点都是可以自由移动的。本人针对这样的环境展开了研究，并提出了一种有效的针对移动传感器网络的定位算法，并与以往的研究成果相比，讨论了其精确性，最后总结全文并展望了移动传感器网络的精确定位算法的研究工作。2 移动传感器网络定位算法研究现状正如前文中所提到的，无线传感器网络的定位技术方面已有了不少类型的算法出现，他们其中包含了一些典型的具有代表性的算法，例如：Cricket系统、质心定位算法、SPA相对定位算法16、凸规划定位算法17,18、DV-Hop定位算法、DV-Distance

9、定位算法、Euclidean定位算法19以及MDS-MAP定位算法20等等，综合分析以上的定位算法，我们发现，每种系统和算法都有各自的特点和适用范围,没有哪一种是绝对最优的；但是，上面提及的以往的研究成果中的方法，虽然对于移动传感器网络它们可以不断的间隔性的获取节点的位置信息，但是没有一项是特别针对节点移动或是信标节点移动的情形而设计的，唯一的考虑到移动节点的情形的是2002年由Bergamo和Mazzini21提出的研究成果，但是他们的研究成果也并不是真正意义上的考虑移动节点的情形。另一方面，在机器人研究的领域里，移动定位的问题已经有了显著的成果。机器人定位问题一般假设地图已知并且试图通过其

10、运动和收集的数据来确定其位置。如果运动和测量模型都可以用高斯密度来描述并且初始数据同样吻合，那么可以用经典的卡尔曼滤波22来完成定位；相反的，如果模型是多模型的非高斯密度的，则可以使用基于网格的马尔科夫23,24定位方法。以往的研究中，有使用移动机器人定位的方法通过测定信号强弱值来改进传感器定位的精确程度的成果25,26。他们这一成果在确定的室内环境中工作的非常出色，但是这一成果需要假设固定的信标节点的位置且需要一个学习阶段，所以此成果在对于移动传感器网络的定位问题并不适用。蒙特卡罗定位（MCL）27,28也经常用于机器人定位或移动传感器网络应用。MCL是与机器人运动的概率模型有关的粒子滤波。

11、它的主要思想是用一组带权的采样值表示先验概率密度。每一个步骤又分为预测阶段和更新阶段。在预测阶段，机器人的运动使得位置的不确定性增加。在更新阶段，新的测量数据被融合及滤波，数据得到更新。这个过程不断重复，机器人持续地更新它的位置。在我们的工作中采用了有序的蒙特卡罗方法29来实现定位，然后在机器人定位和无线传感器网络节点定位方面有着非常大的差别。然而，在机器人定位和传感器网络节点定位之间有着本质的不同。首先，机器人定位是在预先定义的地图上定位，而传感器网络是在自由空间或未标明的区域上定位。第二，机器人对在预定义地图上的运动有着相对好的控制和了解。传感器节点很少或无法控制它的运动，而且对速度和方向

12、也不了解。第三，机器人可以从路标获得精确的范围信息，但传感器节点只能知道它是否在通信范围内。传感器节点的约束和范围的精确度决定了移动传感器节点的定位是比机器人定位更困难的问题。3 基于Monte Carlo方法的精准定位算法我们在本节提出了一种新的传感器网络节点的定位算法，关注了在更普遍的网络环境下实施的节点定位。在这种环境下，不需要特殊的测距硬件，锚节点分布密度较低，普通节点的分布没有规律，传感器节点可以不受控制的自由移动。虽然移动性令其他定位技术变得不精确，我们的方法利用了节点的移动性提高了精确度和减少了锚节点的数目。这里考虑的是锚节点静止，未知节点移动的情况。锚节点预先配置在固定位置，或

13、者通过GPS 确定位置。其他节点随机分布，位置未知。我们假设时间分为离散的时隙。因为一个节点可能离开它原来的位置，它需要在每个时隙进行重定位。我们更关心的是获得一个节点可能位置的概率分布。因为节点保持在网络中移动，前一个位置信息也变得不精确。且由于节点与锚节点之间通讯，以及节点和锚节点的计算都要花费一定的时间，每次确定当前时刻节点的位置时，该节点已经在下一个位置了。我们永远无法通过传统定位方法获得当前时刻节点的实际位置。因此尽量准确地预测下一个或几个时刻节点的位置就显得至关重要。在以往对Ad hoc网络和无线传感器网络中的研究中，通常的研究模型都是使用随机运动模型。他们认为在一段时间间隔内，节

14、点是以一定的速度朝一定的方向运动的，而不同的时间间隔的运动之间都是相互独立的。换而言之，这样的模型会生成一些不切实际的运动行为，例如急速转弯或者突然停止等。另一些成果利用了改进的随机运动模型，例如文献30就是一种对随机运动模型的拓展，在这一研究中，节点在某一时刻处于某一位置，并在下一时刻以任意选择的方向和0到MaxSpeed的区间内均匀分布的速度来运动。文献31中的马尔科夫过程模型也是另一种对随机运动模型的延伸。还有许多其他的研究也都涉及到这方面，但是所有的这些研究都只是试图生成一个节点的运动的轨迹来进行模拟，没有一个在其中包含了真正的节点位置预测，进而预先估计无线传感网络的拓扑变化。在本文的

15、算法中，我们利用对节点前几个点的位置进行插值得到大致的运动轨迹来预测节点的运动方向。这样可以大大地减小节点可能的范围和预测的工作量；并且因为大部分的节点跟踪定位需求都还是连续近似平滑的运动，所以定位的精度也有可能大大的提高。3.1 节点运动预测假设在一个二维平面上，有一个移动节点Nmobile。我们已知该节点时刻0，时刻1，时刻2时刻k-1的位置：, ，现在要通过前k-1个点的运动轨迹预测该节点在时刻k的位置和运动方向。已知前k个时刻的位置，可以利用三维插值的方法预测出k时刻的位置，但考虑节点的运算能力和节能，可以利用两次二维牛顿插值来代替。分别对前k+1个时刻的和做插值(0ik)。我们假设函

16、数f(t)在k1个相异的时刻上的函数值分别为：即，那么根据牛顿插值多项式，我们可以利用前k1个时刻的即来预测第k+2个时刻的，其公式如下： 公式1 公式2 公式3同样： 公式4由公式1和公式4 ，我们可以预测得到在第K+1时刻，节点在x方向和y方向的速度和分别是： 公式5 公式6由插值预测得出的节点在x方向和y方向的运动速度，我们可以在假设在t=k的时刻节点的位置为原点的前提下得到节点的运动方向，用直线方程表述为： 公式7节点的运动速度为： 公式8其中在插值点的选取方面，即f(t)在前K+1个相异时刻的函数值，我们应该遵循以下的原则：1. 始终维持一个包括K+1个样本点的采样窗口，用来对节点的

17、运动轨迹进行插值。2. 这K+1个采样点可以是节点前K+1个时刻的预测位置的修正值。时间间隔可以任取，而不一定是连续的时间间隔。原则上，越靠近当前时刻所取得时间间隔应密集。3. 采用时间和准确度两个标准对窗口中的样本点进行维护。判断方法如下：l 得到滤波后的修正值之后，比较修正值和插值所得点的位置，如果两者方向不同（运动趋势偏移较大），则舍弃前K+1个采样点，从此刻开始插值。l 如果两者方向一致，距离相差不大（小于一定阈值），则无需更新采样窗口。减小计算量。l 否则，更新采样窗口。将当前时刻的修正值加入，在窗口中选择插值点和修正值差别最小的点来替换。l 每隔一段时间强制更新一次。3.2 节点位

18、置预测我们在前文中曾经就以往的节点运动模型进行了详细的分析归类，我们发现，原有的运动模型并不能对现实应用中的绝大部分运动轨迹实现很好的拟合。因为在现实应用环境中，跟踪的目标或节点的移动轨迹总是相对平滑的，因为通常的运动物体的运动轨迹都还是比较规则的。通过我们对本文的应用背景的矿山井下定位的节点运动轨迹进行统计分析，我们可以发现对于本文应用背景中涉及到的运动轨迹，所有的运动都是沿巷道做运动的，而井下的巷道中95%以上都是平滑的，换而言之，95%的巷道都可以用二次曲线来描述其形状，所以95%以上的运动轨迹都可以用二次曲线来拟合。所以我们在选择预测的节点位置是可以采取以下的方式：1. 取以为半径，节

19、点运动方向顺时针与逆时针各展开角（045）的一个扇型；2. 以节点的运动方向为切线，随机生成d条二次曲线；3. 在此d条二次曲线上在扇形内的线段上任意随机选取N个点做预测值；4. 如果滤波后符合要求的点个数不够N。可以将扇形的角度加倍后用1相同方法重新进行选点和滤波(随机选取的点数变为重采样数)，直到找到满足要求的点。所以可以描述满足上述情况节点集合为： 公式93.3 滤波算法在预测阶段我们获得第k+2时刻的N个预测值，它们的集合为S,我们对以后的算法做出如下定义：定义0邻节点：在Nmobile通信半径内的未知节点，称为Nmobile的邻节点定义1内锚点(Innor,D)：当前时刻在Nmobi

20、le通讯半径内的锚点，则在当前时刻这些锚点称为Nmobile内锚点定义2邻锚点(Neighboor,I)：当前时刻在NNmobile的邻居节点通讯半径内的锚点，则在当前时刻这些锚点称为Nmobile的邻锚点。在k到k+1时刻Nmobile接受到以下广播信息：l 锚点向通讯半径内广播当前时刻位置坐标l 普通节点向通讯半径内广播其所侦听到的锚节点位置将根据在时刻k到k+1观测到的广播信息，把Nmobile的在时刻k到k+1的内锚点集合记为IS，邻锚点集合记为NS，用代表N个预测值中的某一点，很显然，我们可以总结Nmobile在时刻k+1的位置到它的内锚点s的距离小于等于R，到邻锚点的距离大于R小于

21、等于2R，所以我们可以描述下列滤波公式：公式10根据公式10的滤波公式，滤掉不满足要求的预测值后，保留满足要求的预测值。我们假设满足滤波公式的预测值的权值为1，否则为0，设预测值的权值为，那么我们需要重新预测采样的数目N为： 公式11根据上文所述的节点预测采样规则，重新采样的N个节点，然后重复上述过程直到找到N个满足要求的值为止。因为找到每个节点的权重都是一致的，所以对找到的N个节点进行平均，得到Nmobile在时刻k+1也就是第k+2个时刻的预测修正值： 公式12 公式134 实验模拟类似本文的工作包括文献32中提出的一种基于MCL的定位方法和文献33中提出的CDL方法，因为本文采用的定位方

22、法和上述两篇文章中提出的定位算法都是非测距的定位方法。其中文献32中提出的方法只是一个基本的MCL方法，并没有针对真实应用中可能出现的运动模型进行进一步分析。我们在下文中将称文献32中提出的方法为“传统MCL”，称文献33中提出的方法为“CDL”，而将本文中提出的算法称为“精准MCL”。本文的研究背景是基于煤矿井下的移动定位提出的，所以模拟实验的环境也应该尽量的类似的煤矿井下的井筒的形态。在此我们利用本文作者的办公楼中交错的走廊来模拟井筒，具体的实验场地见图1和图2：图1 实验场地示意图Fig1. Sketch map of experiment filed图2 实验场地实景图Fig2. Sn

23、apshot of experiment field其中图中灰色描出的部分为办公楼的走廊，我们将利用这些部分来做为我们实验模拟的场地。图中所示走廊宽度为3米，长度分别为38米，19米，4米和8米，总实验面积为207米2。由于节点的移动即煤矿井下的节点和人员的移动，所以我们在实验中采用了多人携带传感器在走廊自由走动的方式来模拟井下节点的移动，也就是说节点的移动带上了人的主观行为，不会频繁的出现突然急停和快速转弯的过程，我们假设人员移动的最大速度为最小运动速度为。下面是我们给出的一些实验相关参数的定义：l 锚节点密度（）：在一跳传输半径内的平均锚节点的个数；l 时间间隔（t）：移动定位算法的定位周

24、期；l 节点密度（）：在一跳传输半径内的平均节点个数；l 精度评价指标：实际位置与算法结果位置之间的距离除以通讯半径R得出的商。由此我们可以得出实验相关的参数如下表：表1 模拟实验相关参数表Table1. Parameters of simulations参数值范围区域面积207m2移动节点速度,节点传输半径2米MCL相关算法样本数50算法执行时间50t定位时间间隔t图3所示的是三种算法在锚节点密度；以及节点密度的情况下算法精度评价指标和算法执行时间之间的关系，图中横坐标为算法执行的时间，用时间片的个数来衡量；图的纵坐标表示算法的定位精度评价指标。由于两项和MCL方法相关的算法能够利用过去的位

25、置信息，所以其精度随着时间变化有着明显的变化而CDL方法不能利用过去的相关信息，所以时间变化对其结果影响不明显。所以我们可以发现，虽然在算法执行的早期，CDL算法明显好于本文提出的算法，但是随着算法的执行，本文的算法由于充分的利用的历史信息并透彻的分析了节点的运动模型，所以本文提出的算法很快的在精度上赶超了CDL算法，而同传统MCL算法相比较，虽然在算法早期两者的精度类似，但是当算法执行到一定程度，由于本文提出的算法在节点运动和位置预测阶段明显的由于传统的MCL方法，所以算法在执行后期精度提高的非常迅速。图3 算法精度比较Fig3. Accuracy comparison图4表示了锚节点的密度

26、对参加评价比较的三个算法的定位精度的影响情况，该项实验在固定且节点密度的情形下进行。我们可以发现，由于CDL算法是从所有的锚节点那里收集信息的而基于MCL算法只是收集其通讯半径内和其邻居通讯半径内锚节点的信息，所以两项基于MCL的算法的精度受锚节点密度的变化影响都较大。图中的横坐标表示为锚节点密度的值，纵坐标描述了算法精度的衡量指标。图4 锚节点密度对算法精度的影响Fig4. Impact of seed density节点的密度在无线传感器网络节点定位中扮演着非常重要的角色，由于在算法的滤波部分中，需要节点的邻居节点提供锚节点的相关信息，所以当节点密度越高时，算法的精度也就同样会越高。同时，

27、由节点分布不均匀所造成的算法精度差的可能性将随节点密度的提高而大大的降低。该实验是在固定且的情况下进行的，我们可以发现三种算法的精度都会随着节点密度的增加而明显增加，但是我们可以发现，在节点密度相同的情况下，三种算法的优劣性总是保持一致，这说明虽然节点密度对于三种算法的精度来说都有提高的作用，但是节点密度并不能影响到算法的优劣。 图5 节点密度对算法精度的影响Fig5. Impact of node density5 结论本文综合分析了无线传感器网络定位算法和其某些应用场景中的运动模型的定义，给出了一种基于MCL方法的适用于煤矿井下定位等运动规模带有明显人为特征的精准的移动传感器网络定位算法，

28、利用了牛顿插值分析来进行运动轨迹的分析预测，最后还针对以往成果中的移动传感器网络定位算法，包括一些同样利用MCL方法来进行定位的算法，展开了全面的模拟实验比较。最终实验结果表明，本文提出的方法在某些应用场景下，其实用性要好于以往的算法。6 参考文献1 Sohrabi K, Gao J, Ailawadhi V, et al. Protocols for Self-organization of a Wireless Sensor Network. IEEE Personal Communications, 2000,7 (5): 16-272 Brad Karp and H. T. Kung.

29、 Greedy Perimeter Stateless Routing. MobiCom 2000.3 Young-Bae Ko and Nitin H. Vaidya. Location-Aided Routing (LAR) in Mobile Ad Hoc Networks. MobiCom 1998.4 Martin Mauve, Jrg Widmer,et al. A Survey on Position-Based Routing in Mobile Ad-Hoc Networks. IEEE Network Magazine. 2001.5 Yih-Chun Hu, Adrian

30、 Perrig ,et al. Packet Leashes: A Defense against Wormhole Attacks in Wireless Ad Hoc Networks. IEEE InfoCom 2003. April 2003.6 Chris Karlof and David Wagner. Secure Routing in Sensor Networks: Attacks and Countermeasures. First IEEE International Workshop on Sensor Network Protocols and Application

31、s, May, 2003.7 He T, Huang C, Blum B M,et al. Range-free localization schemes for large scale sensor networks. In: proc 9th Annual Intl Conf on Mobile Computing and Networking (MobiCom), San Diego, CA., 2003. 81958 Priyantha N B, Balakrishnma H,et al. Anchor-free distributed localization in sensor n

32、etworks. Technical Report MIT-LCS-Tr-892, MIT Lab for computer Science, April 20039 Bahl P, Padmanabhan V N. RADAR: An in-building RF-based user location and tracking system. In: Proc of INFOCOM 2000, Tel Aviv, Israel. 2000, Vol.2：77578410 Griod L, Estrin D. Robust Range Estimation using Acoustic an

33、d Multimodal SensingC.In:Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS01),Maui,Hawaii,USA:IEEE Computer Society,2001;3:1312132011 Priyantha N，Chakraborty A ,et al. The cricket location-support systemACMConference Oil Mobiil Computing and Networking J1MA，2000

34、(6)12 Andreas Savvides, Chih-Chieh Han ,et al. Dynamic Fine-Grained Localization in Ad-Hoc Networks of. Sensors. Networked and Embedded Systems Lab. Department of Electrical Engineering. University of Calfornia, Los Angeles13 Niculescu D,Nath B.Ad Hoc Positioning System (APS)Using AOA,IEEE INFOCOM 2

35、003,San Francisco,CA,USA,2003.14 Radhika Nagpal, Howard Shrobe,et al. Organizing a Global Coordinate System from Local Information on an Ad Hoc Sensor Network. 2nd International Workshop on Information Processing in Sensor Networks (IPSN). April 2003.15 Dragos Niculescu and Badri Nath. DV Based Posi

36、tioning in Ad hoc Networks. Kluwer Journal of Telecommunication Systems. 2003.16 Capkun S, Hamdi M, et al. GPS-Free positioning in mobile ad-hoc networks. Cluster Computing, 2002,5(2):157.167.17 Doherty L, Pister KSJ,et al. Convex position estimation in wireless sensor networks. In: Proc. of the IEE

37、E INFOCOM 2001. Vol.3, Anchorage: IEEE Computer and Communications Societies, 2001. 1655.1663. 18 Doherty L. Algorithms for position and data recovery in wireless sensor networks. Berkeley: University of California, 2000.19 Nicolescu D, Nath B. Ad-Hoc positioning systems (APS). In: Proc. of the 2001

38、 IEEE Global Telecommunications Conf. Vol.5, San Antonio: IEEE Communications Society, 2001. 2926.2931. 20 Shang Y, Ruml W,et al.Localization from mere connectivity. In: Proc. of the 4th ACM Intl Symp. on Mobile Ad Hoc Networking & Computing. Annapolis: ACM Press, 2003. 201.212. 21 P. Bergamo and G.

39、 Mazzini. Localization in Sensor Networks with Fading and Mobility. IEEE PIMRC. September 2002.22 Peter Maybeck. Stochastic Models. Estimation and Control, Volume 1. Academic Press, New York, 1979.23 Wolfram Burgard, Dieter Fox,et al. Estimating the Absolute Position of a Mobile Robot Using Position

40、 Probability Grids. 14th National Conference on Artificial Intelligence (AAAI). 1996.24 Wolfram Burgard, Andreas Derr,et al. Integrating Global Position Estimation and Position Tracking for Mobile Robots: The Dynamic Markov Localization Approach. IEEE/RSI International Conference on Intelligence Robots and Systems (IROS). 1998.25 Andrew M. Ladd, Kostas E.,et al. Robotics-Based Location