- 1 -
中国科技论文在线
基于 Monte Carlo 移动定位算法的研究与改
进
赵欣，李宁**
作者简介：赵欣（1986-），女，硕士研究生
通信联系人：李宁（1968-），女，副教授，主要研究方向：物联网
（北京邮电大学电子工程学院，北京 100876） 5
摘要：本文针对“无线传感器节点在移动中”的应用场合，结合Monte Carlo移动定位算法，
综合考虑了节点的运动特点，提出了基于Monte Carlo移动定位算法的改进算法。改进的算
法在节点位置的预测阶段使用二次曲线来模拟人的走动，在滤波阶段判断节点位置是否符合
人的移动规律，改进了节点位置的预测方法和滤波算法，达到了缩小样本空间的目的，最终
达到提高定位精度的结果。通过实验仿真将改进算法与基本的Monte Carlo移动定位算法进10
行了比较和分析，仿真结果表明，在改变锚节点数量、普通节点数量和移动速度三个变量的
情况下，改进的算法都比原算法提高了定位的精度。
关键词：电路与系统；无线传感器网络；预测；滤波；Monte Carlo
中图分类号：TN
15
Research and Improvement Based on Monte Carlo Mobile
Localization
ZHAO Xin, LI Ning
(School of Electronic Engineering, Beijing University of Post and Telecommunication, 100876)
Abstract: In this paper, an improved algorithm for mobile application is proposed, which combined 20
with Monte Carlo algorithm for mobile wireless sensor nodes and considered the characteristics of
mobile nodes. During the pridict period, quadratic curves are used for simulating human walking route.
During filter period, whether the node lacation is complied with the law of human walking is judged,
which is achieve the purpose to reduce the sample box, and ultimately improve the accuracy of the
results. This improved algorithm and the original one has simulated by computer. The simulation result 25
shows that in the case of changing the number of anchor nodes, the number of mobile nodes and speed,
improved algorithm is better than original one in accuracy.
Key words: circuits and systems; wireless sensor networks; pridict; filter; Monte Carlo
0 引言 30
在无线传感器网络的各类应用中，如环境监测、军事、病人监护等领域，如果没有无线
传感器的位置信息，获取到的数据将是没有意义的，因此，无线传感器节点定位技术已经逐
渐成为无线传感器网络中最重要的技术之一。
无线传感器定位算法主要分为基于测距的算法和无需测距的算法两大类[1]。基于测距的
定位算法通过测量节点之间的距离、角度等信息实现定位，常用的方法有三边测量法、三角35
测量法或最大似然估计法等[2]。无需测距的定位算法则不需要距离、角度等信息，利用节点
之间的相邻关系和连通性实现定位，缺点是定位精度较低，典型的无需测距的定位算法有基
于节点跳数信息的 DV-Distance算法[3]和 Amorphous算法[4]、求解几何重心的质心算法[5]等。
上述这些定位算法在传统的静止无线传感器网络中效果不错，但如果使用这些定位算法
计算移动的节点的位置，当结果计算出来以后，节点也已经因为移动离开了那个位置，这样40
- 2 -
中国科技论文在线
得出的将永远是已经过期的无效的位置信息。在某些特定应用场合中，虽然可以通过高频率
的运行为静态无线传感器网络设计的定位算法来近似“实时”的确定移动节点的位置，并且
可以取得一定的效果，但是会引起比较严重的信息衰减。
所以，在设计针对无线传感器网络移动节点的定位算法时，移动性应该被直接考虑到，
定位结果不应该因为移动性降低，而是应该通过利用移动性这一特点来帮助提高定位精度和45
定位效率。例如，可以通过已经获得的现有位置信息，比较精确的预测接下来的时刻的节点
位置，以提供比较实时的有效的当前位置信息。曾凡仔等人提出MCB算法，通过建立采样
盒子加快算法收敛速度[6]。Rudafshani提出通过改变传统Monte Carlo算法的结构提高定位
精度[7]。Wang提出可以利用测距信息来提高定位精度[8]。
1 Monte Carlo移动定位算法 50
Monte Carlo移动定位算法（MCL）是 1988年 Rubin提出的采样/重采样算法的一个演
化，关键想法是使用一个包含 N个带权值的样点的集合 来代替后验概率。
用 表示样点集中的样点，其中 为机器人所在位置， 为这个样点的权
值，类似于离散概率。通过假设 保持归一性。
Monte Carlo移动定位算法分为预测和滤波两个阶段[9]。 55
在预测阶段，因为约定待定位节点的运动速度不会超过某个最大值 Vmax，所以，若 是
待定位节点在 t-1 时刻的可能位置，那么在 t 时刻，该节点的位置就只可能在以 为圆心、
Vmax为半径的一个圆内。
在滤波阶段，待定位节点根据当前时刻接收到的观测值和约束条件丢弃掉那些不可能
存在的预测位置。最后得到的样点平均即为节点的定位位置。 60
图 1 直观的表示了 Monte Carlo 定位算法的效果，机器人从已知位置的某点（图中 A
点）出发，沿实线所示轨迹运动。随着时间的推移，样点集的不确定性增强。
图 1 Monte Carlo移动定位算法效果示意
Fig. 1 effect of Monte Carlo mobile localization 65
2 基于Monte Carlo移动定位算法的改进
本文的应用场景是人佩戴着无线传感器在某个范围内走动，很明显，采用没有任何规
律性的运动方向和速度是相互独立的随机运动模型并不合适，因为人的走动并不是完全独立
- 3 -
中国科技论文在线
的，现实中，人一般会以某种速度近似的匀速前进，即使速度出现变化也是渐变的，并且很70
少会出现或方向的大幅度改变。
同时，无线传感器节点所监听到的锚节点和一跳范围内其他的节点所监听到的锚节点
的信息可以在滤波阶段留下更多更可信的样点。
本文基于上述分析，设计了基于Monte Carlo移动定位方法的改进算法，在节点位置预
测阶段使用二次曲线来模拟人的移动，在滤波阶段判断节点位置是否符合人的移动规律，达75
到了缩小样本空间的目的，并通过实验仿真将改进算法与基本的Monte Carlo移动定位算法
的性能进行了比较。
应用场景描述
本研究内容是针对于人佩戴着无线传感器节点走动的移动节点的无线传感器网络定位
系统，应用场景如下： 80
在面积为 100m*100m的场地上，佩戴着无线传感器的人可以在这个范围内随意走动，
每个人可看作一个移动无线传感器节点。无线传感器网络周期性的对移动的节点的位置进行
跟踪定位，并通过无线传感器网络将位置信息传输到控制站。
算法描述
节点移动轨迹预测阶段 85
在初始化阶段，即 时刻，待定位的无线传感器节点对自己的位置未知。待定位的无
线传感器节点记录下自己的一跳范围内的所有锚节点为集合 OS，再记录一跳范围内的邻居
节点的一跳范围内的所有锚节点集合（即邻居节点的 OS 集合）为集合 TS。本算法只使用
了待定位节点两跳以内的锚节点，可以有效的减少能量的消耗并降低网络冲突的概率。
分别以 OS集合中的锚节点为圆心、通信半径 R为半径作圆，取所作的几个圆的交集，90
并作交集的外接矩形；再分别以 TS集合中的锚节点为圆心、二倍通信半径为半径作圆，取
所作的几个圆的交集，并作交集的外接矩形。取上述两个矩形的交集为 trustbox0。
例如，假设有待定位节点 P，在它的一跳范围内监听到两个锚节点和一个邻居节点，分别锚
节点 A、锚节点 B和普通节点 Y，即待定位节点 P的 OS集合为锚节点 A和锚节点 B。邻
居节点 Y在它的一跳范围内也监听到两个锚节点，分别为锚节点 a和锚节点 b，即待定位节95
点 P的 TS集合为锚节点 a和锚节点 b。如下图 2所示。
图 2 无线传感器节点位置示意
Fig. 2 position of wireless sensor nodes
100
分别作 OS集合中锚节点的外接圆，即分别以锚节点 A和锚节点 B为圆心、通信半径
R为半径作圆，并取两个圆相交部分的外接矩形。如下图 3所示。
- 4 -
中国科技论文在线
图 3 初始化过程示意
Fig. 3 initialization process 105
分别作 TS集合中锚节点的外接圆，即分别以锚节点 a和锚节点 b为圆心、二倍通信半
径 2R为半径作圆，并取两个圆相交部分的外接矩形，再取新作矩形与上一步所作矩形的交
集，即为 trustbox0。如图 4中所示灰色区域。
110
图 4 trustbox0生成示意
Fig. 4 genetation of trustbox0
在 trustbox0中随机取 20个样点，将 20个点的平均位置作为节点在初始时刻 的初始
预测位置 P0。 115
节点移动轨迹预测阶段
经过一个时隙后，即 时刻，无线传感器节点移动到了一个新的未知的位置 P’，用上
述方法作当前 时刻的 trustbox1。
作以样点为圆心、节点最大移动速度 Vmax为半径的圆的外接正方形，与当前 trustbox1
作交集，得到的矩形为 samplebox。如下图 5所示橙色区域。 120
- 5 -
中国科技论文在线
图 5 samplebox生成示意
Fig. 5 generation of samplebox
125
trustbox0中随机取的 20个样点均这样做，这样可以得到 20个 samplebox。
节点移动轨迹预测阶段
在 samplebox里随机取一个点，通过做矢量的运算判断该点是否符合预测的运动轨迹。
若符合条件，则将该点储存在 trustbox1’中，否则丢弃该点，重新在 samplebox 里随机选取
一个点进行上述滤波判断。直到得到符合条件的样点或达到最大尝试次数。若达到最大尝试130
次数后还是无法得到符合条件的样点，则放弃这个 samplebox，直接在 trustbox1中随机得到
一个样点储存在 trustbox1’中。
依次判断 20个样点，得到有 20个新的样点的 trustbox1’，取 20个样点的均值，即为
时刻的节点定位位置 P1。
循环往复预测阶段和滤波阶段，则可得到所有时刻对节点定位的位置结果。 135
3 实验模拟和结果分析
为了准确分析算法的性能，本文采用单一变量法，通过仿真模拟实验，修改实验中锚
节点密度、移动节点密度和移动节点运动最大速度这三个变量，将本算法与传统Monte Carlo
移动定位算法进行比较，检测算法的性能，主要的指标是移动传感器节点的定位精度，即定
位误差与无线传感器节点的信号传输半径。 140
实验模拟
仿真中相关的参数设置如下：场地范围为 100m*100m，节点通信半径 R 为 5m，节点
- 6 -
中国科技论文在线
最大移动速度 Vmax为 3m/s。各图中蓝线是传统Monte Carlo移动定位算法的定位精度曲线
图，绿线为改进算法的定位精度曲线图。
结果分析 145
定位精度与锚节点个数之间的关系
图 6 定位精度-锚节点个数关系仿真图
Fig. 6 relationship of accuracy and anchor node number
150
图 6为定位精度-锚节点个数关系仿真图。由曲线的走势可以看出，锚节点的个数对算
法的定位精度有着一定的影响。这主要是因为，基于Monte Carlo思想的定位算法都需要锚
节点信息来构建样点空间，才能有效定位。锚节点数量越多，待定位节点能监听到的约束信
息就越多，定位结果就会越准确。
定位精度与普通节点个数之间的关系 155
图 7 定位精度-普通节点个数关系仿真图
Fig. 7 relationship of accuracy and ordinary node number
- 7 -
中国科技论文在线
图 7为定位精度-普通节点个数关系仿真图。由曲线走势可以看出，普通节点的密度对
算法精度的影响非常显著。随着普通节点个数的增加，算法的定位精度也随之比较显著的提160
高。这主要是因为，待定位节点的一跳范围内的节点所能监听到的锚节点也能帮助定位，节
点越多，待定位节点所能监听到的节点（一跳节点）就越多，可用的信息也就越多，定位结
果就会越准确。
定位精度与节点最大移动速度之间的关系
165
图 8 定位精度-节点最大移动速度关系仿真图
Fig. 8 relationship of accuracy and Vmax of ordinary node number
图 8为定位精度-节点最大速度关系仿真图。由曲线走势可以看出，节点的最大速度越
大，定位精度越差。这是因为，移动节点的运动速度越大，算法中的 samplebox的范围就越170
大，所取的样点的不确定性也就越大，影响到定位的准确性。
4 结论
本文给出了基于Monte Carlo移动定位算法的改进算法，考虑到了节点的运动特点，在
节点位置预测阶段使用二次曲线来模拟人的移动，在滤波阶段判断节点位置是否符合人的移
动规律，达到了缩小样本空间的目的，最终达到提高定位精度的结果。 175
致谢
在论文完成之际，我要向给予我指导、关心和帮助过我的导师李宁副教授，我的同学
刘霄、林文亮、武君卓、戴晨、王川、徐超、李森等表示衷心的感谢。
180
[参考文献] (References)
[1] 张丽霞，汪文勇，李炯. 无线传感器网络的目标定位问题研究[J]. Journal of UEST of China，2006，35：
240-242.
[2] 王秉旻，石晓军. 无线传感器网络基于测距定位算法的实现[J]. 科技资讯，2006，2：143-144.
- 8 -
中国科技论文在线
[3] Niculescu D, Nath B. DV-Based Positioning in Ad-Hoc Networks[J]. Journal of Telecommunication Systems, 185
2003, 22: 267-280.
[4] Alberto Cerpa, Deborah Estrin Ascent. Adaptive Self-Configuring Sensor Network Topologies[J]. ACM
SIGCOMM Computer Communication Review, 2002, 32(1): 62
[5] Bulusu N, Heidemann J, Estrin D. GPS-less low-cost outdoor localization for very small devices[J]. IEEE
Personal Communications, 2007, 7(5): 28-34. 190
[6] 曾凡仔，孙正章，罗娟等. 无线传感器网络的节点定位方法[J]. 通信学报，2008，29（11）：62-66.
[7] Rudafshani M, Datta S. Localization in wireless sensor networks [C]. 6th International Symposium on ISPN.
Cambridge, MA, USA, 2007: 51-60.
[8] Wang W D, Zhu Q X. RSS-based Monte Carlo Localization for mobile sensor networks[J]. IET
Communications, 2008, 2(5): 673-681. 195
[9] Baggio A, Laugendoen K. Monte Carlo localization for mobile wireless sensor networks[J]. Ad hoc Networks,
2008, 6(5):718-733.
