一种基于蒙特卡洛的移动传感网节点定位的优化算法

李坤++何月顺

摘要：在无线传感网中，针对蒙特卡洛移动节点定位算法中通信半径无法确定这一缺陷，本文提出了一种结合跳＼距转换模型的蒙特卡洛定位改进算法。该算法首先利用实际中测得节点间的跳数信息得到节点的预估计坐标，进而精化出一个环形采样区域，提高了采样效率。仿真结果表明，优化之后的算法能够显著地减少定位采样次数，能够有效提高定位的准确性，并且能改善网络中低锚节点密度时的性能。

关键词：无线传感网 移动定位 蒙特卡洛 跳＼距转换模型 采样优化

中图分类号：TP212.9 文献标识码：A 文章编号：1007-9416（2014）08-0123-02

1 引言

无线传感技术在信息科技的各个领域已经得到越来越广泛的应用，传感器测得的数据要和它自身的位置信息相结合才有意义。如何更高效、更精准地获取无线传感网（wireless sensor network，WSN）中节点的位置信息是WSN研究的当务之急。大部分的定位算法都是针对静态WSN网络的，倘若将静态WSN定位算法应用于移动WSN络中，由于节点的运动性会导致定位的精度下降，节点能量消耗加快等问题，很多针对移动WSN定位的方法应运而生。HuLingxuan提出的蒙特卡洛定位算法（Monte Carlo Localization，MCL）充分利用了节点的移动性，能够取得较好的定位精度，得到了广泛的应用。以MCL为基础，很多专家提出MCB[3]，RSSI-MCL[4]，SOMCL[5]等定位方法。

由于在实际应用中传感器节点通信半径无法确定，且经典MCL采样过程繁琐，采样效率低下，本文提出了一种结合跳＼距转换模型的MCL优化算法，避免直接使用节点的通信半径确定采样区域，而且能够取得更好的定位效果。

2 蒙特卡洛定位算法

蒙特卡洛方法（Monte Carlo method）是一种以概率统计理论为指导的一类数值计算方法。它应用于移动WSN节点定位中可以描述为：

（1）结合未知节点上一时刻位置和运动模型，得到一个圆形的均匀采样区域进行采样。（2）利用未知节点与观测到的附近锚节点的距离信息对样本进行过滤，过滤条件为 ，其中、分别代表一、二跳锚节点，代表通信半径，代表采样坐标。（3）过滤掉一部分采样样本之后再重复进行上述步骤，直到得到足够数量的样本数，给每个样本赋予权值，就可以估算出未知节点的位置。但经典MCL在实际应用中并不能得到理想参数值，比如说节点通信半径会随着高度的变化而发生较大的改变。为了解决这些问题，我们需要对原算法进行一些改进使它能更好的应用于实际中。

3 一种新的蒙特卡洛定位改进算法

本文基于MCL提出了一种叫做HDMCL的定位算法，该算法利用节点间跳数信息估算未知节点的预估计坐标，再规划出一个精化的采样区域，解决了通信半径波动大的困难，且定位精度和采样效率上都有明显的提升。

3.1 跳＼距（H＼D）转换模型

H＼D转换模型可利用节点间的跳数信息得到节点间的距离信息，描述如下：

（1）网络中所有节点洪泛和接收其他节点的跳数信息；（2）锚节点在洪泛和接收跳数信息的同时还要传播坐标值。计算出与其他锚节点距离的和值及跳数的和值，分别记为、。它们的比值即为的平均跳距值，记为。（3）未知节点从与之跳数最小的一个锚节点获取平均跳距值，记为，用乘上它与其他锚节点的跳数值，即可以获得它与所有锚节点的距离。

3.2 环形采样区域确定

将每个未知节点与其他锚节点的距离，记为，表示未知节点，表示锚节点。假设未知节点的坐标为，锚节点坐标为，利用多边测量法即可计算出每个未知节点的预估计坐标，具体方法流程如下：

（1）未知节点与锚节点的欧氏距离表示为：

（2）分别用式1中第2至n个方程分别减去第1个方程：

用A表示方程组系数项

用b表示方程组常数项

（3）解出未知节点的预估计坐标值：

通过上述方法，得到各个未知节点的预估计坐标值，同时提取出未知节点周围锚节点信息，分别计算未知节点与其一、二跳锚节点的欧氏距离作为环形区域的参考半径，记为，m表示预估计坐标，n表示一、二跳锚节点坐标。参考半径分别乘上参数因子α和β，和分别作为环形区域内环和外环的半径，考虑到预估计坐标位置存在误差，且误差是在一定范围内服从均匀分布的，所以环形区域内环和外环是参考圆的等比缩小或者扩大，所以α和β可以表示为和，，只要选取合适的，就能用最小的代价换取最大的采样效率。结合上述信息可以构造出一个精化的定位采样环形区域，如图1所示，阴影处即为采样区域。

4 仿真与分析

本文使用MATLAB R2013B仿真软件对算法进行分析，仿真环境如表1所示。

4.1 定位精度

图2中两条曲线分别描述WSN所有节点分别运行MCL算法和HDMCL算法得到的平均定位误差情况，本方案模拟前10个时间步的误差情况。可以看出由于在定位过程中精化了滤波条件，HDMCL算法中节点的平均定位误差相比于经典的MCL算法的平均定位误差有所减小，优化的比例是3%至8%不等，定位精度平均优化了5.01%。

4.2 采样效率

图3为HDMCL算法中采样次数由100减为50，MCL采样次数仍为100，其他定位条件不变的节点定位误差对比图，可以看出相比于传统MCL算法，节点定位精度仍然平均优化了3.57%，这是由于在HDMCL算法中，采样区域是由若干个环形区域的交集精化而来的，取代了传统MCL通过通信半径确定的采样区域，所以采样效率有明显的改善。

4.3 锚节点密度

锚节点密度是WSN节点定位的重要参考指标，本文对网络中锚节点不同个数情况下的未知节点定位情况进行分析，锚节点个数分别为7至25个不等，由图4可以看出平均定位误差是随着锚节点密度的增加而减小，HDMCL算法中，锚节点密度越低时，定位精度相比于经典MCL算法优化效果更明显。这说明在低锚节点密度情况下HDMCL有着更好的定位效果。

5 结语

本文提出了一种基于蒙特卡洛算法的移动WSN定位改进算法，该算法利用节点间相互感知的跳数信息和锚节点信息得到一个精化的环形采样区域，取得了较好的定位效果。仿真表明该算法相比于蒙特卡洛方法有更好的定位精度，此外，在采样效率方面有了很大的改善，并且在锚节点密度较低的WSN环境下有更显著的优化效果。目前该能很好的应用于规则的网络环境，但并不能很好的应用于复杂地形，这一点还有待研究。

参考文献

[1]Hu Lingxuan， David Evans Localization for Mobile Sensor Net works[C].Proceedings of the 10th Annual International Conference on Mobile Computing and Networking Philadelphia， PA，NewYork， USA： ACM Press，2004.

[2]Lyudmila Mihaylova， Donka Angelova and Anna Zvikhachevskaya. Sequential Monte Carlo Methods for Localisation inWireless Networks[J]，2012.

[3]Baggio A，Langendoen K.Monte Carlo Localization for Mobile Wireless Sensor Network[J].Lecture Notes in computer Science，2006.

[4]朱海平.动态无线传感器网络的改进蒙特卡罗定位算法[J].传感技术学报，2012.

[5]孙燕.基于采样优化的蒙特卡罗移动节点定位算法[J].系统工程与电子技术，2010.endprint

摘要：在无线传感网中，针对蒙特卡洛移动节点定位算法中通信半径无法确定这一缺陷，本文提出了一种结合跳＼距转换模型的蒙特卡洛定位改进算法。该算法首先利用实际中测得节点间的跳数信息得到节点的预估计坐标，进而精化出一个环形采样区域，提高了采样效率。仿真结果表明，优化之后的算法能够显著地减少定位采样次数，能够有效提高定位的准确性，并且能改善网络中低锚节点密度时的性能。

关键词：无线传感网 移动定位 蒙特卡洛 跳＼距转换模型 采样优化

中图分类号：TP212.9 文献标识码：A 文章编号：1007-9416（2014）08-0123-02

1 引言

无线传感技术在信息科技的各个领域已经得到越来越广泛的应用，传感器测得的数据要和它自身的位置信息相结合才有意义。如何更高效、更精准地获取无线传感网（wireless sensor network，WSN）中节点的位置信息是WSN研究的当务之急。大部分的定位算法都是针对静态WSN网络的，倘若将静态WSN定位算法应用于移动WSN络中，由于节点的运动性会导致定位的精度下降，节点能量消耗加快等问题，很多针对移动WSN定位的方法应运而生。HuLingxuan提出的蒙特卡洛定位算法（Monte Carlo Localization，MCL）充分利用了节点的移动性，能够取得较好的定位精度，得到了广泛的应用。以MCL为基础，很多专家提出MCB[3]，RSSI-MCL[4]，SOMCL[5]等定位方法。

由于在实际应用中传感器节点通信半径无法确定，且经典MCL采样过程繁琐，采样效率低下，本文提出了一种结合跳＼距转换模型的MCL优化算法，避免直接使用节点的通信半径确定采样区域，而且能够取得更好的定位效果。

2 蒙特卡洛定位算法

蒙特卡洛方法（Monte Carlo method）是一种以概率统计理论为指导的一类数值计算方法。它应用于移动WSN节点定位中可以描述为：

（1）结合未知节点上一时刻位置和运动模型，得到一个圆形的均匀采样区域进行采样。（2）利用未知节点与观测到的附近锚节点的距离信息对样本进行过滤，过滤条件为 ，其中、分别代表一、二跳锚节点，代表通信半径，代表采样坐标。（3）过滤掉一部分采样样本之后再重复进行上述步骤，直到得到足够数量的样本数，给每个样本赋予权值，就可以估算出未知节点的位置。但经典MCL在实际应用中并不能得到理想参数值，比如说节点通信半径会随着高度的变化而发生较大的改变。为了解决这些问题，我们需要对原算法进行一些改进使它能更好的应用于实际中。

3 一种新的蒙特卡洛定位改进算法

本文基于MCL提出了一种叫做HDMCL的定位算法，该算法利用节点间跳数信息估算未知节点的预估计坐标，再规划出一个精化的采样区域，解决了通信半径波动大的困难，且定位精度和采样效率上都有明显的提升。

3.1 跳＼距（H＼D）转换模型

H＼D转换模型可利用节点间的跳数信息得到节点间的距离信息，描述如下：

（1）网络中所有节点洪泛和接收其他节点的跳数信息；（2）锚节点在洪泛和接收跳数信息的同时还要传播坐标值。计算出与其他锚节点距离的和值及跳数的和值，分别记为、。它们的比值即为的平均跳距值，记为。（3）未知节点从与之跳数最小的一个锚节点获取平均跳距值，记为，用乘上它与其他锚节点的跳数值，即可以获得它与所有锚节点的距离。

3.2 环形采样区域确定

将每个未知节点与其他锚节点的距离，记为，表示未知节点，表示锚节点。假设未知节点的坐标为，锚节点坐标为，利用多边测量法即可计算出每个未知节点的预估计坐标，具体方法流程如下：

（1）未知节点与锚节点的欧氏距离表示为：

（2）分别用式1中第2至n个方程分别减去第1个方程：

用A表示方程组系数项

用b表示方程组常数项

（3）解出未知节点的预估计坐标值：

通过上述方法，得到各个未知节点的预估计坐标值，同时提取出未知节点周围锚节点信息，分别计算未知节点与其一、二跳锚节点的欧氏距离作为环形区域的参考半径，记为，m表示预估计坐标，n表示一、二跳锚节点坐标。参考半径分别乘上参数因子α和β，和分别作为环形区域内环和外环的半径，考虑到预估计坐标位置存在误差，且误差是在一定范围内服从均匀分布的，所以环形区域内环和外环是参考圆的等比缩小或者扩大，所以α和β可以表示为和，，只要选取合适的，就能用最小的代价换取最大的采样效率。结合上述信息可以构造出一个精化的定位采样环形区域，如图1所示，阴影处即为采样区域。

4 仿真与分析

本文使用MATLAB R2013B仿真软件对算法进行分析，仿真环境如表1所示。

4.1 定位精度

图2中两条曲线分别描述WSN所有节点分别运行MCL算法和HDMCL算法得到的平均定位误差情况，本方案模拟前10个时间步的误差情况。可以看出由于在定位过程中精化了滤波条件，HDMCL算法中节点的平均定位误差相比于经典的MCL算法的平均定位误差有所减小，优化的比例是3%至8%不等，定位精度平均优化了5.01%。

4.2 采样效率

图3为HDMCL算法中采样次数由100减为50，MCL采样次数仍为100，其他定位条件不变的节点定位误差对比图，可以看出相比于传统MCL算法，节点定位精度仍然平均优化了3.57%，这是由于在HDMCL算法中，采样区域是由若干个环形区域的交集精化而来的，取代了传统MCL通过通信半径确定的采样区域，所以采样效率有明显的改善。

4.3 锚节点密度

锚节点密度是WSN节点定位的重要参考指标，本文对网络中锚节点不同个数情况下的未知节点定位情况进行分析，锚节点个数分别为7至25个不等，由图4可以看出平均定位误差是随着锚节点密度的增加而减小，HDMCL算法中，锚节点密度越低时，定位精度相比于经典MCL算法优化效果更明显。这说明在低锚节点密度情况下HDMCL有着更好的定位效果。

5 结语

本文提出了一种基于蒙特卡洛算法的移动WSN定位改进算法，该算法利用节点间相互感知的跳数信息和锚节点信息得到一个精化的环形采样区域，取得了较好的定位效果。仿真表明该算法相比于蒙特卡洛方法有更好的定位精度，此外，在采样效率方面有了很大的改善，并且在锚节点密度较低的WSN环境下有更显著的优化效果。目前该能很好的应用于规则的网络环境，但并不能很好的应用于复杂地形，这一点还有待研究。

参考文献

[1]Hu Lingxuan， David Evans Localization for Mobile Sensor Net works[C].Proceedings of the 10th Annual International Conference on Mobile Computing and Networking Philadelphia， PA，NewYork， USA： ACM Press，2004.

[2]Lyudmila Mihaylova， Donka Angelova and Anna Zvikhachevskaya. Sequential Monte Carlo Methods for Localisation inWireless Networks[J]，2012.

[3]Baggio A，Langendoen K.Monte Carlo Localization for Mobile Wireless Sensor Network[J].Lecture Notes in computer Science，2006.

[4]朱海平.动态无线传感器网络的改进蒙特卡罗定位算法[J].传感技术学报，2012.

[5]孙燕.基于采样优化的蒙特卡罗移动节点定位算法[J].系统工程与电子技术，2010.endprint

摘要：在无线传感网中，针对蒙特卡洛移动节点定位算法中通信半径无法确定这一缺陷，本文提出了一种结合跳＼距转换模型的蒙特卡洛定位改进算法。该算法首先利用实际中测得节点间的跳数信息得到节点的预估计坐标，进而精化出一个环形采样区域，提高了采样效率。仿真结果表明，优化之后的算法能够显著地减少定位采样次数，能够有效提高定位的准确性，并且能改善网络中低锚节点密度时的性能。

关键词：无线传感网 移动定位 蒙特卡洛 跳＼距转换模型 采样优化

中图分类号：TP212.9 文献标识码：A 文章编号：1007-9416（2014）08-0123-02

1 引言

无线传感技术在信息科技的各个领域已经得到越来越广泛的应用，传感器测得的数据要和它自身的位置信息相结合才有意义。如何更高效、更精准地获取无线传感网（wireless sensor network，WSN）中节点的位置信息是WSN研究的当务之急。大部分的定位算法都是针对静态WSN网络的，倘若将静态WSN定位算法应用于移动WSN络中，由于节点的运动性会导致定位的精度下降，节点能量消耗加快等问题，很多针对移动WSN定位的方法应运而生。HuLingxuan提出的蒙特卡洛定位算法（Monte Carlo Localization，MCL）充分利用了节点的移动性，能够取得较好的定位精度，得到了广泛的应用。以MCL为基础，很多专家提出MCB[3]，RSSI-MCL[4]，SOMCL[5]等定位方法。

由于在实际应用中传感器节点通信半径无法确定，且经典MCL采样过程繁琐，采样效率低下，本文提出了一种结合跳＼距转换模型的MCL优化算法，避免直接使用节点的通信半径确定采样区域，而且能够取得更好的定位效果。

2 蒙特卡洛定位算法

蒙特卡洛方法（Monte Carlo method）是一种以概率统计理论为指导的一类数值计算方法。它应用于移动WSN节点定位中可以描述为：

（1）结合未知节点上一时刻位置和运动模型，得到一个圆形的均匀采样区域进行采样。（2）利用未知节点与观测到的附近锚节点的距离信息对样本进行过滤，过滤条件为 ，其中、分别代表一、二跳锚节点，代表通信半径，代表采样坐标。（3）过滤掉一部分采样样本之后再重复进行上述步骤，直到得到足够数量的样本数，给每个样本赋予权值，就可以估算出未知节点的位置。但经典MCL在实际应用中并不能得到理想参数值，比如说节点通信半径会随着高度的变化而发生较大的改变。为了解决这些问题，我们需要对原算法进行一些改进使它能更好的应用于实际中。

3 一种新的蒙特卡洛定位改进算法

本文基于MCL提出了一种叫做HDMCL的定位算法，该算法利用节点间跳数信息估算未知节点的预估计坐标，再规划出一个精化的采样区域，解决了通信半径波动大的困难，且定位精度和采样效率上都有明显的提升。

3.1 跳＼距（H＼D）转换模型

H＼D转换模型可利用节点间的跳数信息得到节点间的距离信息，描述如下：

（1）网络中所有节点洪泛和接收其他节点的跳数信息；（2）锚节点在洪泛和接收跳数信息的同时还要传播坐标值。计算出与其他锚节点距离的和值及跳数的和值，分别记为、。它们的比值即为的平均跳距值，记为。（3）未知节点从与之跳数最小的一个锚节点获取平均跳距值，记为，用乘上它与其他锚节点的跳数值，即可以获得它与所有锚节点的距离。

3.2 环形采样区域确定

将每个未知节点与其他锚节点的距离，记为，表示未知节点，表示锚节点。假设未知节点的坐标为，锚节点坐标为，利用多边测量法即可计算出每个未知节点的预估计坐标，具体方法流程如下：

（1）未知节点与锚节点的欧氏距离表示为：

（2）分别用式1中第2至n个方程分别减去第1个方程：

用A表示方程组系数项

用b表示方程组常数项

（3）解出未知节点的预估计坐标值：

通过上述方法，得到各个未知节点的预估计坐标值，同时提取出未知节点周围锚节点信息，分别计算未知节点与其一、二跳锚节点的欧氏距离作为环形区域的参考半径，记为，m表示预估计坐标，n表示一、二跳锚节点坐标。参考半径分别乘上参数因子α和β，和分别作为环形区域内环和外环的半径，考虑到预估计坐标位置存在误差，且误差是在一定范围内服从均匀分布的，所以环形区域内环和外环是参考圆的等比缩小或者扩大，所以α和β可以表示为和，，只要选取合适的，就能用最小的代价换取最大的采样效率。结合上述信息可以构造出一个精化的定位采样环形区域，如图1所示，阴影处即为采样区域。

4 仿真与分析

本文使用MATLAB R2013B仿真软件对算法进行分析，仿真环境如表1所示。

4.1 定位精度

图2中两条曲线分别描述WSN所有节点分别运行MCL算法和HDMCL算法得到的平均定位误差情况，本方案模拟前10个时间步的误差情况。可以看出由于在定位过程中精化了滤波条件，HDMCL算法中节点的平均定位误差相比于经典的MCL算法的平均定位误差有所减小，优化的比例是3%至8%不等，定位精度平均优化了5.01%。

4.2 采样效率

图3为HDMCL算法中采样次数由100减为50，MCL采样次数仍为100，其他定位条件不变的节点定位误差对比图，可以看出相比于传统MCL算法，节点定位精度仍然平均优化了3.57%，这是由于在HDMCL算法中，采样区域是由若干个环形区域的交集精化而来的，取代了传统MCL通过通信半径确定的采样区域，所以采样效率有明显的改善。

4.3 锚节点密度

锚节点密度是WSN节点定位的重要参考指标，本文对网络中锚节点不同个数情况下的未知节点定位情况进行分析，锚节点个数分别为7至25个不等，由图4可以看出平均定位误差是随着锚节点密度的增加而减小，HDMCL算法中，锚节点密度越低时，定位精度相比于经典MCL算法优化效果更明显。这说明在低锚节点密度情况下HDMCL有着更好的定位效果。

5 结语

本文提出了一种基于蒙特卡洛算法的移动WSN定位改进算法，该算法利用节点间相互感知的跳数信息和锚节点信息得到一个精化的环形采样区域，取得了较好的定位效果。仿真表明该算法相比于蒙特卡洛方法有更好的定位精度，此外，在采样效率方面有了很大的改善，并且在锚节点密度较低的WSN环境下有更显著的优化效果。目前该能很好的应用于规则的网络环境，但并不能很好的应用于复杂地形，这一点还有待研究。

参考文献

[1]Hu Lingxuan， David Evans Localization for Mobile Sensor Net works[C].Proceedings of the 10th Annual International Conference on Mobile Computing and Networking Philadelphia， PA，NewYork， USA： ACM Press，2004.

[2]Lyudmila Mihaylova， Donka Angelova and Anna Zvikhachevskaya. Sequential Monte Carlo Methods for Localisation inWireless Networks[J]，2012.

[3]Baggio A，Langendoen K.Monte Carlo Localization for Mobile Wireless Sensor Network[J].Lecture Notes in computer Science，2006.

[4]朱海平.动态无线传感器网络的改进蒙特卡罗定位算法[J].传感技术学报，2012.

[5]孙燕.基于采样优化的蒙特卡罗移动节点定位算法[J].系统工程与电子技术，2010.endprint