基于测距的蒙特卡罗定位算法研究

王迎云　鹿建银　谷敏玲

【摘 要】无线传感器网络已经对人们的生活产生了极大的影响，本文主要分析了无线传感器网络的定位关键技术，比较了传统蒙特卡罗定位算法及基于测距的RSSI蒙特卡罗定位算法，并通过实验验证了RSSI-MCL比MCL的定位准确性高。

【关键词】无线传感器网络；MCL；RSSI

中图分类号： TP212.9；TN929.5 文献标识码： A 文章编号： 2095-2457（2018）30-0107-003

DOI：10.19694/j.cnki.issn2095-2457.2018.30.046

Research on Monte Carlo Location Algorithm Based on Ranging

WANG Ying-yun1 LU Jian-yin2 GU Min-ling3

（1.Anhui Xinhua University，Hefei Anhui 230088，China

2.Chaohu University，Hefei Anhui 238000，China

3.Anhui Xinhua University，Hefei Anhui 230088，China）

【Abstract】Wireless sensor networks have a great impact on people's lives.This paper mainly analyzes the key technologies of wireless sensor networks positioning，compares the traditional Monte Carlo positioning algorithm and the RSSI Monte Carlo positioning algorithm based on ranging，and verifies the positioning accuracy of RSSI-MCL than MCL through experiments.

【Key words】Wireless Sensor Network；MCL；RSSI

0 引言

无线传感器网络WSN，即Wireless Sensor Network，是由大量部署在监控区域的低成本%低功耗的微型传感器节点组成，以无线通信方式组成的分布式自组织网络，传感器布置在监测区域内，能够自主采集和处理监测区域内的信息，并最终发送给观察者，是一种全新的信息获取和处理技术[1]。无线传感器网络中的每个节点都有能源、有限的计算能力和存储空间。且它们能够为获取信息的定位提供依据。

无线传感器网络最初由美国军方提出，最早被应用与国防军事后，在国内外的迅速发展，如今，WSN在环境监测、国家安全、天气预测、城市交通、医疗护理、智能家居、目标跟踪、生物研究、反恐救灾等领域都有着很广泛的应用，给人们的生活带来了极大的方便。对于大部分应用来说，采集到的数据必须知道传感器的具体位置，只有在知道了传感器位置信息的前提下，采集到的数据才有意义，才能知道事件所发生的位置[2]。

在传感器网络的各种应用中，监测到事件之后关心的一个重要问题就是该事件发生的位置[3]。如在城市交通应用中需要知道交通堵塞信息所对应的具体区域位置；在反恐救灾中需要知道灾害发生的现场位置等。在判断结果位置前，传感器节点必须要先精确定位自身所在的位置，然后才能为最终的结果判定提供依据。但是，在传感器網络中，传感器节点往往是处于移动的状态，如何在移动状态下能够精确定位出节点的位置信息，成为了大家关心热点。

全球定位系统GPS，采用卫星定位，虽然是一个定位精确、高效的定位技术，但其通常应用在空旷的外部环境中，且应用在传感器网络中成本很高，因此非常不适用，研究一种适用于无线传感器网络移动节点状态下的低成本、高效、精确定位的技术成为了无线传感网络的关键。

1 定位算法

2004年，Lingxuan Hu和Evans根据机器人定位技术中广泛应用的序列蒙特卡罗方法，将其应用在无线传感网络，并提出了一种移动传感器定位算法，即序列蒙特卡罗定位算法（称为MCL算法）[4]。该算法虽然能够实现移动节点的目标定位，但是算法采样次数非常多且成功率低。Baggio等人在MCL的基础上提出了蒙特卡罗盒定位MCB算法，该算法在锚箱里采样，相对于序列蒙特卡罗定位算法来说，采样范围变小了，采样成功率提高，但是当信标在锚箱内的分布密度很低时，绝大部分的采样都是无效的，成功率也会降低。后期又提出把测距信息应用到MCL算法中，但其具体测量又需要硬件的支持。

节点定位算法分为距离相关的定位算法和距离无关的定位算法两类，距离相关的定位算法（range-based），是指通过直接或间接的获取节点之间的距离信息或角度信息，使用三边、三角或极大似然等定位算法来估计未知节点的坐标值[5]。主要的测距算法有：接收信号强度指示（Received Signal Strength Indication，RSSI）、到达时间（Angle of Arrival，AOA）、到达时间差（Time Difference of Arrival，TDOA）等，RSSI算法通过信号衰减模型将信号衰减转化为与之相匹配的距离，算法相对简单且其成本较低，而其他距离相关的方法都需要额外配备昂贵的硬件模块来接收信号极大增加了投资成本，基于RSSI算法进行测距的定位系统主要有：Calamari、Microsoft's RADAR、SpotON；距离无关的定位算法无需测量距离和角度信息，根据网络连通度、多跳路由等信息来实现节点定位，其成本较低但定位精度不高，常用的距离无关的算法有：质心、APIT（Approximate Point-In-Triangulation Test）、DV–Hop、DV-Distance、凸规划等定位算法。

2 RSSI-MCL算法

RSSI-MCL算法主要有三个步骤：

（1）位置预测阶段

设定某一位置未知节点处于不停移动的状态，根据节点的移动特性，可以用m ～P（m |m ）表示该节点在前一时刻的位置为m 时，当前时刻位置在m 的概率，该概率分布称为转移分布。

若该节点随机从最大速度vmax和最小速度vmin之间选取某一个值作为运动速度，并随机从0，2？仔中选取某一个值作为运动方向，那么转移分布P（m |m ）便形成了一个以mk-1为圆心，vmin为内半径，vmax为外半径的圆环，表示如下：

在位置预测阶段，利用前一时刻的位置信息对当前时刻的位置进行预测，节点可能的位置从上述的圆环形区域中随机采样获得，圆环区域就是采样区域。

根据k时刻观测值位置信息，未知的节点滤除不满足条件的样本，并根据权值更新剩余样本中的位置数据。使用n ～P（n |m ）描述在给定位置的RSSI的测量值的概率分布，该概率为观测分布。

具体地，设定位置未知节点从采样区域中采集一组样本m ，i=1，2，L，N，其中N是样本数量。每一个样本都存在一个非负的权值w ，其定义为：

式中w 表示样本i在k时刻的权重，根据观测分布，其计算公式为：

根据样本和对应权值的集合 ，可以得到节点位置的后验分布为：

通过节点位置预测和权值更新的反复计算之后，可得到最终的后验分布 。

（3）重采样阶段

计算当前的位置需要反复进行上述的预测和滤波阶段，但在多次迭代之后，由于算法退化问题的存在，可能出现大多数样本的权值都趋近0，而只有一个样本的权值趋近1的现象。退化现象意味着大量的计算浪费在了那些对后验分布贡献很小的粒子上，為了避免这种现象的发生，需要检测算法是否发生退化现象，并在检测到算法退化的时候，进行重采样。

3 仿真分析

4 总结

RSSI-MCL算法虽然能够在一定程度上提高算法的定位精度，但是以牺牲算法的运算效率为代价的，这使得数据量较大时，对于节点的定位时间花销较高，今后将从提高算法的运算效率、降低时间复杂度入手进行研究，以更进一步优化算法。

【参考文献】

[1]游晓鹏等.RSSI辅助的蒙特卡罗盒定位算法[J].计算机 技术与发展，2013，12（23）：11-15.

[2]徐彦.基于WSN的目标定位技术的研究[D].南京：南京航空航天大学，2016.

[3]孙正章.基于蒙特卡罗的无线传感器网络移动节点定位算法研究[D].长沙：湖南大学.2009.

[4]姚放吾.WSN中一种基于重叠区域的蒙特卡罗定位算法[J].计算机技术与发展.2012，5（22）：165-168.

[5]李建坡，钟鑫鑫，徐纯.无线无线传感器网络静态节点定位算法综述[J].东北电力大学学报，2015，02：73-82.