新闻中心

EEPW首页 > 设计应用 > 基于IMCL算法的无线传感器网络节点定位

基于IMCL算法的无线传感器网络节点定位

作者:郑君刚 陈莉 陈彪时间:2015-12-09来源:电子产品世界收藏
编者按:节点定位是无线传感器网络的一个基本和关键的问题。针对无线传感器网络移动节点定位方法计算量大,硬件要求高和信标节点数目需较多等难点。本文研究蒙特卡洛定位方法,并提出一种改进的蒙特卡罗节点定位方法(IMCL),利用插值法预测运动轨迹结合采样盒来进行采样。仿真结果表明,该方法能够提高采样的效率,提高节点的定位精度。

摘要:节点定位是的一个基本和关键的问题。针对定位方法计算量大,硬件要求高和信标节点数目需较多等难点。本文研究蒙特卡洛定位方法,并提出一种改进的节点定位方法(IMCL),利用插值法预测运动轨迹结合采样盒来进行采样。仿真结果表明,该方法能够提高采样的效率,提高节点的定位精度。

本文引用地址:http://www.eepw.com.cn/article/283523.htm

引言

  随着网络技术的发展,的应用越来越广泛,而无线传感器网络的研究和应用依赖于整个系统对节点的准确位置信息的获取,位置的精度直接影响着网络的性能和优化的手段。在无线传感器网络的许多应用中节点定位算法扮演着非常重要的角色[1-2]。目前无线传感器网络节点定位研究大部分针对静态无线传感器网络,但在实际应用中传感器节点处于动态的应用却十分广泛,如监视动物的移动、医院病人的监护等。因此,定位技术的研究对无线传感器网络技术具有重要的理论意义和应用价值。在移动无线传感器网络的实际应用中如何实现低成本、低功耗和高精度的节点定位,已成为节点研究的重点问题[3-5]。针对无线传感器网络的一些定位算法:如DLS定位算法、DRL定位算法等,由于存在计算量大、硬件要求高和需要较多信标节点数目等特点,难以满足实际的应用。文献[6]借鉴机器人领域中的定位方法,并将其应用到无线传感器网络中移动节点的定位。定位方法(Monte Carlo Localization,简称MCL)利用节点的移动性来帮助定位,能够提高定位的精度,减小定位的代价,给移动无线传感器网络节点定位问题的解决提供了一个新的思路,使越来越多的研究者在此算法的基础上衍生出自己的改进方法。Baggio提出了MCB定位算法[7] (Monte Carlo Localization Boxed),该算法通过信标节点盒子和样本盒子把采样区域限制在一个样本盒子中,提高采样成功率,从而改善定位性能;于是Dual-MCL和Mixer-MCL定位算法[8]被提出,通过限制样本的采样范围等方法在预测和阶段进行改进,改进了原有MCL定位算法;RSS-Based MCL定位方法[9]研究了将MCL与RSSI测距信息相结合。李敏等提出了一种基于参考节点选择模型的蒙特卡罗定位算法[10],能够在较少信标节点的情况下利用相邻节点参与定位,但定位误差较大。

  本文研究了一种改进的蒙特卡罗定位算法(IMCL),该方法利用插值法预测节点的运动轨迹并结合采样盒来进行采样,该方法能够提高节点采样的效率,提高节点定位的精度。

1 IMCL定位方法实现

1.1 方法概述

  MCL定位算法中,Vmax越大,则采样的区域越大,节点位置的不确定性也随之增大。由于事先不知道节点运动方向,需要在整个圆内采样,这也增加了节点的不确定性。通过构建节点运动模型,选取节点的位置和采样盒相结合来进行过滤,以此来减小节点可能的范围和预测工作量,来提高节点定位精度和工作效率。


1.2 节点的运动模型和运动预测

  节点在移动过程中使用的移动模型对算法定位精度有密切关系,不同的移动模型导致不同的节点移动轨迹,在无线传感器网络中常用的移动模型有:Random Walk移动模型、Rand Waypoint移动模型、Random Direction移动模型[8]、Reference Point Mobility model、Voltage of mobile model、高斯-马尔科夫模型。本算法假设是应用在一个二维的平面上,节点的运动平滑而连续,因此可以借助历史的位置数据,利用插值法对节点的运动进行预测。开始时让每个移动节点根据MCL算法获取自己的前几个时刻位置信息,并存放在一个历史的记录队列里,然后根据记录来预测移动节点下一时刻的运动趋势。假设节点存储了先前n-1个时间点的位置信息。t1,t2…tn-1时刻的位置分别为(x1, y1)、(x2, y2)…(xn-1,yn-1)。采用拉格朗日插值法[7]可以得到节点在tn时刻x方向和y方向的运动预测计算式。分别为:

 (1)

(2)

  由式(1)和(2)分别对时间t求导,可以预测到tn时刻节点在x方向和y方向的运动速度。分别为:

(3)

(4)

  由式(1)和(3)可得到节点在tn时刻的运动速度为:

(5)

  有x轴和y轴方向上的速度,可以得到节点在tn的运动方向为:

(6)

1.3 节点位置的选取

  在构建采样区域时,为了计算方便,使用通信圆的外切正方形代替理想圆周通信模型。采样盒可以消除部分通信覆盖范围并不是一个理想圆所带来的影响。采样盒示意图如图1所示。

  采样盒由(xmin, xmax)和(ymin, ymax)计算得到,其中xmin、xmax、ymin和ymax由公式(7)得到。

(7)

  (xj, yj)为信标节点的坐标。为了获取较大的采样盒,来获取较为丰富的样本,在保证定位精度的前提下,尽量选择距离定位节点较近的信标节点来构成采样盒,在同等均匀的分布下,距离定位节点较远的信标节点构成采样区域小于距离节点较近的信标节点构成的采样区域。由于节点运动的连续性,本文利用上一刻的值预测节点的位置并结合采样盒来进行采样。在预测节点位置时采用以下的方式,如图2所示。

  以上一时刻为坐标原点,以Vmax为半径,沿节点运动方向的顺时针和逆时针各展开θ角的一个扇形(θ值由公式(6)得到);在图2扇形和图1采样盒交集的区域随机选取N个点作为预测值;如果后符合要求的预测点的个数达不到N,可以将扇形的θ角加倍后用上面相同的方法重新进行选取和,直到找到满足要求的点。所有满足上述情况的节点集合为:

(8)

1.4 滤波计算

  滤波阶段,节点根据当前接收到的观测值来去掉那些不满足要求的预测位置。节点使用上一时刻的节点预测位置结合节点运动模型来进行滤波。信标节点向通信半径内广播其当前时刻的位置坐标,待定位的未知节点在通信半径内接收信标节点的位置并转播。根据在时刻k到k+1观测到的广播信息,如果Ds为1跳信标节点的集合,Is为2跳信标节点的集合,则滤波公式为:

(9)

  根据公式(8)进行滤波,滤掉不满足要求的粒子后,保留满足要求的粒子,如满足要求的粒子数达不到要求,则继续在采样区域内采样、滤波,直到找到满足要求的粒子数目。假设满足滤波公式的预测值的权值为1,不满足的权值为0。设预测值的权值为ωi,则需要重新预测采样的数目N’:

(10)

  利用上面的采样规则,重新采样N’,然后重复上面的过程直到找到满足的粒子数,因为找到的 每个粒子的权重都一致,所以有:

 (11)

  最后计算得到待定位节点的坐标:

(12)

2 仿真实验与结果分析

  为了验证IMCL定位算法的有效性,根据MCL定位算法,对MCL-Simulator仿真器进行扩展,利用扩展的仿真器来验证IMCL算法的性能,设置仿真区域大小为200×200正方形,所有节点随机分布在其中,信标节点与待定位的节点的通信半径r为20m。本文主要研究信标节点静止且均匀分布,未知节点移动的模型采用了Rand Waypoint移动模型,为了控制节点的移动范围不超过传感区域的边界,节点移动的最大移动速度在0.2r~2r之间,且不考虑移动节点的运动方向。

  本文从以下几个方面对IMCL算法进行仿真分析:

  (1) 采样数目的选择。不同的采样数目对应的定位精度和需要的存储条件不同,需要选择合理的采样数目。

  (2) 研究信标节点的密度对定位误差的影响。

  (3) 研究移动节点的最大运动速度对定位误差的影响。

  (4) 研究信标节点的比例对节点定位覆盖率的影响。

  利用蒙特卡罗方法定位时,采样数目的选取与定位的定位误差有很大的关系,采样数目越多,得到的节点定位的精度就越高。但是采样数目多意味着存储空间的增大和计算量的加大,但是节点本身的存储不可能做得很大。为了不占用更大的存储空间和计算时间,需要同时保证定位精度的要求,因此选择合理的采样数目很关键。图3 显示了采样数目与节点定位误差的关系,由此可以看出随着采样数目的增加,节点的定位误差在下降。当采样数目在100左右时,节点的定位误差就开始变得平缓,直到采样数目达到1000,定位误差变化也不大。本文仿真实验的采样数目选择了100个,这样既能保证节点定位的精度要求,又能够减少节点的存储空间和计算的时间。



上一页 1 2 下一页

评论


相关推荐

技术专区

关闭