基于测距权重的蒙特卡罗定位改进算法

周春月, 张洪婷

(北京交通大学 电子信息工程学院，北京 100044)



基于测距权重的蒙特卡罗定位改进算法

周春月, 张洪婷

(北京交通大学 电子信息工程学院，北京 100044)

针对传统蒙特卡罗定位算法采样效率低，对锚节点密度要求高的特点，本文基于蒙特卡罗定位算法MCL提出一种改进的移动传感器网络的节点定位算法IMCB.该算法利用历史锚节点信息和RSSI测距,以及运动模型的改进对待定位节点的位置采样范围进行了进一步限制，对有效采样点的权重进行了区分.仿真结果表明：该算法的定位精度相比MCB算法提高了16.6%.

无线传感器网络；蒙特卡罗定位算法；接收信号强度指示；运动模型

无线传感器网络现今在很多需要监测与控制的环境中得到广泛应用，如环境监测、农业监测、智能交通和安全监控等.很多应用都依赖于传感器节点的位置信息，如应用中的一些监测信息，如果没有了位置信息就毫无意义.传感器节点定位即传感器节点确定自身位置的过程.最简单的办法就是在每个传感器节点上安装GPS，但由于无线传感器网络节点本身资源有限，对能耗限制苛刻，而且这种解决方案工程量大且成本高，在实际应用中不可行.大多数算法是基于锚节点的定位算法，在这种算法中，锚节点通过GPS或人工配置事先获得自身的位置，其余的未知节点则根据锚节点的位置及网络拓扑或者节点之间的距离信息推算出自己的位置.

无线传感器网络节点的定位算法可以分为基于测距的定位算法和非测距的定位算法两种：1)基于测距的定位算法通过TOA[1]、TDOA[2]、AOA[3]及

RSSI[4]等测距技术获得普通节点与锚节点之间的距离，然后利用空间几何规则通过三角定位算法、三边定位算法、多边定位算法和最大似然估计算法等推算出未知节点的位置.2)非测距的定位算法不需要测量节点之间的距离，而是通过未知节点与周围节点的连接度计算得到未知节点的位置，如质心定位[5]、DV-Hop[6]定位、凸规划[7]和APIT[8]定位等.

固定的无线传感器网络已有诸多相对成熟的定位算法,但不能直接应用于移动传感器网络.文献[9]针对无线移动传感器网络的节点定位提出了蒙特卡洛定位算法.在该算法中未知节点根据运动模型在自身可能存在的位置范围内进行位置采样，再依据网络中已知的锚节点位置信息过滤掉不符合实际条件的采样点，通过这一系列的位置采样来估计未知节点的位置.

鉴于蒙特卡罗定位算法的位置采样效率低，文献[10]在MCL算法的基础上提出了蒙特卡罗盒定位算法，该算法通过构造锚箱更快地获取有效位置采样，提高了节点定位的精度和效率.文献[11]提出了基于RSSI的蒙特卡罗定位算法，利用锚节点与未知节点间的RSSI测距缩小错箱范围.文献[12]提出权重蒙特卡罗定位(Weighted Monte Carlo Localization，WMCL)算法，充分利用普通邻居节点在t-1时刻的估计位置信息对t时刻的位置估计采样区域进行限制及对位置采样进行过滤.除了以上改进策略，还有诸多对基于蒙特卡罗定位算法的无线移动传感器网络节点定位算法的研究，如自适应权重[13]和虚拟锚节点[14]等.

本文作者基于蒙特卡罗定位算,提出了一种新的移动传感器网络的节点定位算法IMCB.该算法利用历史锚节点结合RSSI测距缩小待定位节点的位置采样范围，并通过当前邻居节点的RSSI测距区分了有效采样点的权重，此外，改进的运动模型有利于节点运动方向的预测.

1 MCL算法

1)初始化阶段，每个普通节点构造一个自身的可能位置采样集Lt.

(1)

3)过滤阶段，普通节点根据收到的一跳及两跳锚节点的观测值对Lt中的无效位置采样点进行过滤，收到消息的一跳邻居普通节点应当在以该锚节点为圆心，以r为半径的圆内，而两跳邻居普通节点应当在以该锚节点为圆心，半径为(r，2r)的圆环内，不符合该条件的位置抽样为无效采样，即：

(2)

(3)

2 基于MCL的改进算法——IMCB

针对MCL算法的位置采样效率低的问题， MCB算法通过充分利用未知节点能“听”到的一跳(两跳)锚节点信息建立锚箱限制位置预测的采样范围，有效提高了节点定位的精度和效率[10].但是MCB仍然存在一些问题：1)在位置估计阶段，MCB将所有可用采样点进行平均得到最后估计位置，没有很好的区分各可用采样点的权重;2)MCB与MCL算法中所采用的运动模型均为改进的随机中间点运动模型(Random Waypoint Mobility Model)，节点在每个时隙内的运动方向任意选取，然而在实际的节点运动中，节点的运动方向范围应该是有限的.为了更进一步改善MCB算法的抽样效率和解决如上两个问题，本文作者利用历史锚节点更进一步缩小未知节点的位置采样区域；利用未知节点与邻居节点之间的接收信号强度指示信息，对采样集中的样点进行权重优化；并在采样阶段根据节点的可能运动方向对节点进行动态的运动预测.

2.1 建立采样箱

MCL进行位置采样时有两个区域：1)位置采样区域，即根据Lt-1和vmax建立的节点可能的运动范围，用于抽取待过滤的位置样点；2)有效样点区域，是根据一跳锚和两跳锚建立的节点实际位置存在的范围，用于过滤不合格的位置样点.当vmax增大时，位置采样区域面积变大，或者当锚节点密度增加时，可用样点区域面积减小，此时就会造成大量的无效采样.为了减少无效采样次数， Baggio 和 Langendoen[10]通过建立锚箱来减小位置采样区域，将位置采样范围限制在以未知节点能“听”到的一跳(两跳)锚节点为中心，边长为2r(4r)的矩形的重叠部分，即锚箱，如图1阴影部分.

本文将进一步缩小节点的位置采样区域.假设已经按MCB算法建立好了锚箱，根据待定位节点在t-1时刻的锚节点信息缩小节点的位置采样区域面积，从而进一步提高采样效率.如图2 (a)所示，nt-1是待定位节点在t-1时刻的位置，nt是待定位节点在t时刻的位置，st-1是待定位节点在t-1时刻的邻居锚节点.因为nt-1一定在st-1的通信范围内，即d(nt-1,st-1)一定小于r，且nt的最大移动距离为vmax，所以nt一定在以st-1为圆心，r+vmax为半径的圆内.

如图2(b)所示，通过接收信号强度可计算nt-1到st-1的距离drss，根据如上原理，可以将nt限制在以st-1为圆心，drss+vmax为半径的圆内，更进一步缩小了st-1对nt-1的限制范围.如此，与MCB同理，建立该圆的外切正方形，X(st-1,j),Y(st-1,j)分别为t-1时刻的第j个锚节点的横纵坐标，则可求其与锚箱的重叠部分如下：

(4)

式中,m是待定节点在t-1时刻邻居锚节点个数.

如上建立好采样箱之后，即可在采样箱中对待定位节点进行位置采样.

2.2 过滤

在过滤阶段，普通节点根据收到的一跳及两跳锚节点的观测值对Lt中的无效位置样本进行过滤，基本方法与MCL算法相同，加入历史锚节点的限制条件即：

(5)

式中：H表示历史锚节点集合.

关于运动模型对采样点的限制，见2.4节.为了获取足够的位置样本，当样本集中的无效样本被过滤后，重复前面的预测抽样和过滤过程，直到满足样本数或到达抽样轮次上限.

2.3 基于RSSI的采样权重优化

接收信号强度装置成本低且容易实现，因此，本文作者提出了基于RSSI的权重算法对已经获得的采样集中的有效采样点进行权重优化.

RSSI权重位置估计分为无权重位置估计和有权重位置估计两个阶段.在无权重位置估计阶段，普通节点根据已经过滤的有效采样点进行平均位置估计，并将该位置估计与其误差衡量发送给普通邻居节点；在有权重位置估计阶段，普通节点根据邻居锚节点信息及邻居节点的位置估计和其误差衡量通过RSSI距离计算权重，更新估计位置.

(6)

(7)

2.4 基于运动模型的采样预测优化

基于运动模型的采样预测优化的基本思想是：运动模型对节点的运动方向进行了限制，未知节点的预测采样点也应该限制在可能的运动方向范围内.

2.4.1 运动模型的改进

在MCL算法仿真中采用的运动模型是改进的随机中间点运动模型，该运动模型以节点的当前位置为起始位置，在节点部署区域范围内任意选取一个位置作为目的位置以确定节点的运动方向，以(最小速率，最大速率)范围内任意值作为节点的运动速率向目的位置运动.该算法认为在不同时间段内的运动是相互独立的，这就有可能造成节点有一些不切实际的运动行为，例如急转180°.为此，本文在随机中间节点运动模型的基础上对节点的运动模型进行改进，将节点的运动方向限制在一个可实现的范围内，即节点所选择的下一时刻的运动方向与原运动方向的夹角应小于可实现的最大夹角.见图5，图5中nt-2、nt-1分别是前两个时刻节点所在位置，nt是节点即将到达的位置.α是向量nt-1nt与nt-2nt-1的夹角，表示节点运动的转角，Δφ是α的最大值.由此将α限制在Δφ范围内，避免了节点在运动过程中出现不切实际的过大转角.

2.4.2 基于运动模型的采样点预测优化

定义估计最大转向角Δφ为实际最大转向角Δφ与修正角θ的和：

Δφ=Δφ+θ

(8)

(9)

σ1+σ2=1

(10)

3 IMCB定位算法仿真结果

本文基于文献[9]的蒙特卡罗定位算法仿真器MCL-simulator对第2节提出的IMCB定位算法进行了仿真验证，并将其性能与MCL和MCB进行了对比.仿真节点分布在500 m×500 m的正方形区域内，区域内随机分布320个节点，其中包含若干个锚节点，锚节点数量根据仿真需要的锚节点密度而定，其余为普通节点.假设所有节点的通信半径恒定为50 m.节点依据如2.4节的优化运动模型在部署区域内随机运动，实际最大转向角Δφ=60°.进行方向预测时,取σ1=0.8，σ2=0.2，k=1.本文设定δ=120°，即当mt-2mt-1σ1+gt-2gt-1σ2=0时，由于参考方向准确度太低，估计最大转向角Δφ=Δφ+θ=180°.执行运动模型时，节点从(0,vmax)内随机选择.sd是锚节点密度，表示在节点的一跳通信范围内的平均锚节点数为

(11)

式中：seed_num表示部署区域内的锚节点总数；S是部署区域的总面积；本文仿真S等于500×500 m2,r等于50 m.

3.1 定位误差

节点的定位误差ER用节点的估计位置坐标与真实位置坐标的距离表示，计算方法如下

(12)

图7为vmax= 0.2r，sd=1时节点定位误差随时间的变化曲线.节点的定位分为初始化阶段和稳定阶段.在初始化阶段，节点的定位误差迅速降低，IMCB和MCB算法相对MCL更快进入稳定阶段，IMCB定位误差有明显改善.此外，在第45时隙之后定位误差呈上升趋势，MCL由于误差累积容易导致节点定位预测样点数目不足，而使定位误差继续增加.相反，MCB和IMCB由于在位置预测时有锚箱的限制，防止了节点定位误差的恶化. IMCB利用了历史锚节点限制条件并对节点的运动方向进行了预测，使抽样范围进一步减小，同时RSSI权重优化有效区分了位置采样点接近真实位置的可能性，从而获得比MCB更准确的定位精度，定位误差平均降低了16.6%.

3.2 最大速率对定位误差的影响

误差值是对特定速率值进行多次定位后的平均误差.图8为sd=1时节点的定位误差随节点运动速率的变化曲线.可以看出，随着vmax增大，在0.2r～0.4r区间，定位误差有明显的下降,之后MCB和MCL定位误差都有明显的上升趋势;虽然本文算法的定位误差也随之增大，但趋势明显较缓.这是因为MCB和MCL的位置预测采样范围都会因为vmax增大而增大，而对于IMCB，除了锚箱和vmax的限制，还增加了方向预测，方向预测是与vmax无关的预测，当vmax增大到对限制位置预测采样范围无效时，也就是说当根据vmax构造的正方形完全覆盖锚箱时，方向预测的范围限制作用仍然有效.因此，随着vmax增加，IMCB的定位误差上升趋势平缓，且定位精度优于MCB.

3.3 锚节点密度对定位误差的影响

图9为vmax= 0.2r时节点定位误差随锚节点密度变化的曲线图，提高锚节点密度有利于降低定位误差，但是这无疑也会增加网络的部署成本.由图9可见，IMCB定位误差低于MCB.这是因为锚节点数量的增加一方面使基于RSSI的权重优化更加有效；另一方面，锚节点的增加提高了定位精度，也使得在下一时刻定位时的方向预测角范围更小，从而缩小了位置预测范围，进一步提高定位精度.此外，历史锚节点的条件限制使得IMCB在锚节点密度较低时，定位精度优于MCL和MCB.

3.4 采样次数

基于MCL的定位算法中大部分的能量消耗来自于为了获得足够有效位置采样点而产生的采样次数，降低采样次数有利于降低能量消耗，提高节点的定位效率.图10为vmax= 0.2r，sd=1时节点定位采样次数随时间变化的曲线图.如图10可见，IMCB算法通过历史锚节点和运动模型对采样范围的限制明显降低了节点定位所需的采样次数.相比MCB算法，IMCB平均定位采样次数降低了74%.

4 总结

本文作者设计出一种基于历史锚节点并结合RSSI测距的权重定位算法——IMCB，它具有如下优点：1)利用历史锚节点及历史RSSI测距进一步缩小了未知节点的位置采样范围，在一定程度上缓解了锚节点密度的问题；2)基于RSSI的权重优化有效区分了采样点的权重；3)对运动模型的改进有利于节点在定位中进行方向预测，缩小了节点定位时预测采样的范围.最终，IMCB算法比MCB算法的定位精度提高了16.6%，平均定位采样次数降低了74%.

[1] JAMALABDOLLAHI M， ZEKAVAT S. Time of arrival estimation in wireless sensor networks via OFDMA [C] .Vehicular Technology Conference, 2015:1-5.

[2] WANG Y, HO K C. TDOA source localization in the presence of synchronization clock bias and sensor position errors[J]. IEEE Transactions on Signal Processing, 2013, 61(18):4532-4544.

[3] CUI W, WU S C, WANG Y Z. A gossip-based AOA distributed localization algorithm for wireless sensor networks [J]. Applied Mechanics and Materials,2014, 577:841-846.

[4] YAGHOUBI F, ABBASFAR A A，MAHAM B. Energy-efficient RSSI-based localization for wireless sensor networks [J].IEEE Communications Letters, 2014, 18(6)：973-976.

[5] BAI Y, LI C M, XUE Y. A centroid localization algorithm for wireless sensor networks based on RSSI[J]. Applied Mechanics & Materials, 2013, 303-306;197-200.

[6] AGASHE A A, AGASHE A A, PATIL R S. Evaluation of DV hop localization algorithmin wireless sensor networks[C]. International Conference on Advances in Mobile Network, Communication and ITS Applications，2012:79-82.

[7] REN P, LIU W, SUN D， et al. Node localization based on convex optimization in wireless sensor networks [C].Fuzzy Systems and Knowledge Discovery , 2015: 2169-2173.

[8] ZHANG A, YE X, HU H. Point in triangle testing based trilateration localization algorithm in wireless sensor networks [J]. Internet and Information Systems, 2012, 6: 2567-2586.

[9] HU L, EVANS D. Localization for mobile sensor networks [J]. Wireless Communication, 2004:45-57.

[10] BAGGIO A, LANGENDOEN K. Monte-Carlo localization for mobile wireless sensor networks[M]. Berlin: Springer Berlin Heidelberg, 2006:718-733.

[11] ZHU H, ZHONG X , YU Q, et al. A localization algorithm for mobile wireless sensor networks [C]. International Conference on Intelligent System Design and Engineering Applications, 2013: 81-85.

[12] ZHANG S, CAO J, CHEN L J, et al. Accurate and energy-efficient range-free localization for mobile sensor networks[J]. IEEE Transactions on Mobile Computing, 2010, 9(6):897-910.

[13] 李建坡, 时明, 钟鑫鑫. 自适应蒙特卡罗无线传感器网络移动节点定位算法[J]. 吉林大学学报(工学版), 2014, 44(4):1191-1196. LI Jianpo, SHI Ming, ZHONG Xinxin. Self-adaptive Monte Carlo localization algorithm of mobile nodes in WSN[J]. Journal of Jilin University(Eng and Technol Ed), 2014, 44(4):1191-1196. (in Chinese)

[14] LUAN J, ZHANG R, ZHANG B， et al. An improved Monte Carlo localization algorithm for mobile wireless sensor networks [C]. 7th International Symposium on Computational Intelligence and Design , 2014: 477-480.

An improved Monte Carlo localization algorithm based on ranging weights

ZHOUChunyue,ZHANGHongting

(School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044,China)

Traditional Monte Carlo localization (MCL) algorithms for mobile wireless sensor networks (WSNs) usually suffer from low sampling efficiency or high anchor density for high localization accuracy. To address these issues, a new localization algorithm based on MCL which called IMCB (Improved Monte Carlo Localization Boxed) is proposed. IMCB fully utilizes the historical anchors information, RSSI ranging, and the improved motion model to further constrain the sampling area and distinguish weights of the effective samples. Simulation results show that the positioning accuracy of the proposed algorithm is improved by 16.6% compared with MCB (Monte Carlo Localization Boxed) algorithm.

wireless sensor networks; Monte Carlo localization; received signal strength indication; motion model

2016-05-10

北京市教育委员会共建项目资助(W15H100040)

周春月(1973—)，女，黑龙江大庆人，高级工程师，博士.研究方向为下一代通信网络技术和信息安全. email：chyzhou@bjtu.edu.cn.

TP393

A

1673-0291(2016)05-0063-07

10.11860/j.issn.1673-0291.2016.05.011