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

梅 举，陈 涤*，辛 玲

(1.山东大学信息科学与工程学院济南250199;2.济宁国家半导体及显示产品质量监督检验中心，山东济宁272000)

在无线传感器网络的许多应用中，节点的位置信息都是至关重要的。在大多数情况下，传感器节点所采集的数据信息，如果脱离了节点的位置信息，将会变得没有意义，例如，需要知道森林火灾的现场位置，战场上敌方车辆运动的区域，天然气管道泄露的具体地点等。无线传感器网络中的节点常常是随机布撒的，对于上述这些问题，传感器节点必须首先通过定位知道自身的地理位置信息，这是进一步采取措施和做出决策的基础。

无线传感器网络根据测距方式的不同分为range-based和range-free两种定位方式，也就是基于测距和无需测距两类。通常的测距技术主要有:接收信号强度指示RSSI(Received Signal Strength Indicator)，到达时间TOA(Time of Arrival)，到达时间差TDOA(Time Difference of Arrival)，到达角度 AOA(Angle of Arrival)。位置未知的节点在得到与锚节点之间的距离信息后，采用三边测量法或者极大似然估计法等方法，可以计算出自身的位置。rangebased定位精度较高，但是传感器节点依赖于专门的硬件设备，成本较高，而range-free定位无需距离或者角度信息，受环境影响较小，硬件成本低，适合大规模的传感器网络，因此也是目前受到普遍关注的定位机制［1－5］。典型的距离无关的定位算法有质心定位、DV-Hop、APIT、凸规划、MDS-MAP 等。

目前的无线传感器网络节点定位研究，大多都是针对静态WSN的，即节点保持静止不动的无线传感器网络类型［6－9］。但是在实际环境中，传感器节点处于运动状态的移动WSN应用十分广泛，比如在目标跟踪中，要对不断移动的目标进行实时的定位［10－11］。同时，传感器节点位置的移动能扩大其监测的范围，能够克服静态WSN中有节点死亡时会带来监听区域真空的现象，节点的移动性使网络能够更好的发现事件并观测事件，能为传感器节点提供更好的通信质量［12］。对于移动WSN节点定位的研究相对不足，而且绝大多数针对静态WSN定位的方法在移动WSN中并不适用，现在对移动WSN的定位研究已经成为一个研究热点［13］。

1 移动WSN定位研究的相关工作

目前对于移动WSN的定位研究，最具代表性的是基于统计方法的定位，主要通过使用序列蒙特卡洛方法(粒子滤波)对节点可能存在的位置进行采样和滤波，并用滤波得到的粒子估计出节点的位置，这也是移动WSN定位研究的一个热点方向，经典的算法主要有 MCL［14］、MCB［15］、MMCL［16］、MSL［17］、range-based-MCL［18］等。

MCL算法是由Hu和Evans提出来的移动WSN中距离无关的节点定位算法，该算法第一次将蒙特卡洛方法引入到移动WSN的节点定位中来，取得了比较理想的效果，节点的定位精度非但没有因为节点的移动特性受到破坏，反而利用移动性提高了定位精度，并减小了定位的代价。该算法的研究结果表明，序列蒙特卡洛方法能够有效的应用于移动WSN的节点定位中。MCL算法采用了粒子滤波方法，过程比一般的定位算法更复杂一些，文献［14］详细介绍和讨论了MCL算法。

在MCL算法的基础上，Baggio A等人改进提出了MCB(Monte-Carlo Localization Boxed)算法，如图1所示，待定位节点首先通过接收到的锚节点信息得到一个锚节点覆盖区域——锚盒子，即图1中阴影区域，然后根据上一时刻的采样粒子和节点自身的运动状态得到采样盒子，如图2中阴影区域所示，其中lt－1表示节点在上一时刻的采样粒子，Vmax为节点的最大运动速率，这里假设节点的运动服从随机行走模型RWP模型［19］，即节点的运动方向和速率未知，但是知道节点的最大运动速率，所以可以得到以上一时刻采样粒子lt－1为圆心，以Vmax为半径的运动圆来预测节点的位置，这个运动圆与锚盒子的交集就是最后的采样盒子。经过这样一个过程，就把采样区域限制在一个采样盒子里，提高了采样成功率，节约了计算量，大大节省了定位时间，提高了定位精度，性能比MCL算法有了较大的改善。

图1 MCB锚盒子

图2 MCB采样盒子

本文提出的 TSBMCL(Temporary Seed Based Monte Carlo Localization)算法，延用了MCB算法的蒙特卡洛盒思想，通过筛选出定位情况较好的节点作为临时锚节点，来辅助其他节点进行定位，从而实现全网节点的定位精度的优化，效果十分显著，下面具体介绍一下本算法。

2 TSBMCL算法详述

在移动无线传感器网络的节点定位过程中，有的节点会收到较多的锚节点信息，并具有相对较小的采样锚盒子，有的节点则收到较少的锚节点信息，甚至收不到锚节点的信息，从而导致定位误差较大或者不能进行位置估计。针对移动WSN中普遍存在的这种现象，本文提出了一种提高移动无线传感器网络节点定位精度的方法，即基于临时锚节点的蒙特卡洛定位方法——TSBMCL算法。临时锚节点，指的是自身定位精度较高而被临时用作锚节点的普通节点。节点在定位过程中不会知道自身的定位误差，但是可以通过一定的评判规则，将定位条件优等的节点筛选出来，这部分节点的定位精度也是最高的，可以充当临时锚节点，来优化其他节点的定位条件。因此，算法的核心思想是通过一定的评判标准选出定位精度高的节点，并将这部分节点用作临时锚节点，来协助其他节点进行定位，从而实现全网节点定位精度的优化。

TSBMCL算法，包括临时锚节点的选举产生过程，以及临时锚节点协助其他节点进行定位的过程。

临时锚节点的产生过程，具体步骤为:

Step 1:网络中的所有锚节点(即seed节点)在全网中洪泛自己的信息，这个被洪泛的数据帧包括(Xseed，Yseed)，IDseed，TTL，其中(Xseed，Yseed)表示锚节点的坐标值，IDseed表示该锚节点的序号，TTL是最大洪泛跳数，初始值设置为2.

Step 2:网络中待定位的普通节点(即node节点)在收到锚节点的洪泛信息之后，记录锚节点的坐标值和序号，如果TTL为2，则将其置为1并转发，如果TTL为1，则将其置零不再转发，从而保证锚节点的信息只被转发两次。

Step 3:锚节点信息洪泛完毕，所有node节点利用MCB算法中的方法得到自己的锚盒子anchor box，并根据锚盒子面积Sanchorbox，二跳以内锚节点数Nnos，计算本node能否成为临时锚节点的判断权值TA，

其中，r为节点的通信半径;Ns为网络中锚节点的个数;S为监测区域的面积;Sd为锚节点密度，表示一跳通信半径以内的平均锚节点数;Srefer为参照锚盒子面积，节点的锚盒子面积Sanchorbox将与之进行比对;α为校正因子，调整该参数可以设置参照锚盒子面积Srefer的缩放比例。

Step4:TA值低于1的节点暂时不进行自身定位，TA值高于1的节点采用MCB算法进行定位，并成为临时锚节点，向周围洪泛自身信息，内容包括，IDnode，TTL。其中表示node的定位位置，IDnode表示该node的序号，TTL为最大洪泛跳数，初始值设置为2，洪泛方式与锚节点相同。洪泛过程完毕以后，TA值低于1的节点，如果没有收到临时锚节点的信息，则依据原来的锚节点信息使用MCB算法进行定位，如果收到临时锚节点信息，则使用该信息进行定位。

临时锚节点协助TA值低于1的节点定位的过程，分为以下步骤:

Step 1:设待定位node在(t－1)时刻的粒子集为，在 t时刻收到 n 个临时锚节点信息后，通过以下公式确定临时锚节点盒子，

其中β为校准半径的调整因子，通过调整β的大小，可以调整rred的取值。

同时，该待定位node的锚节点盒子通过MCB算法得到，设为(xs_min，xs_max，ys_min，ys_max)，则该 node的最终锚盒子定义为下式，如图3所示，

从而得到采样盒子如下，

图3 临时锚节点覆盖图

Step 2:对采样粒子进行滤波，滤波公式为，

其中ot表示观测信息，S是一跳锚节点的集合，T是两跳锚节点的集合，STA是一跳临时锚节点的集合，TTA是两跳临时锚节点的集合，d(lt，s)是采样粒子lt与(临时)锚节点的欧几里德距离。

滤波完成以后，如果粒子数不足所需要的数目N，则进行重采样，并重复滤波过程，直到达到采样数N或者达到最大采样次数为止。

整个TSBMCL算法的流程如图4所示。

图4 TSBMCL算法流程图

3 仿真结果与分析

在仿真实验中，所有传感器节点被随机布撒在500 m×500 m的矩形区域中，通信半径r为100 m，所有传感器节点，包括普通节点和锚节点，均采用随机行走模型(RWP)［19］，RWP模型是移动WSN最常见的运动模型之一，该模型中，节点在每一运动时刻随机选择运动速率和运动方向，且节点不知道自身的运动速率和方向，但是知道自身的最大运动速率为Vmax，方向为360°任意选择，根据表1的参数，对TSBMCL与MCB两种算法用MATLAB仿真50次求平均值。

表1 仿真参数设置

首先来验证临时锚节点的遴选公式是否正确可行，图5显示，临时锚节点的定位误差要比其他节点小得多，这说明式(3)能够有效的选出定位效果最好的部分节点，并将它们用来协助其他节点进行定位。

图5 临时锚节点与其他节点的定位误差对比

网络中全部节点的定位误差对比情况如图6所示，TSBMCL算法对MCB算法的优化效果是十分明显的，整体定位精度提高了34%。

图6 全网节点在两种方法下的误差对比

临时锚节点个数的统计结果如图7所示，平均每一次定位产生31个临时锚节点。

图7 临时锚节点产生数量

利用临时锚节点信息协助定位的节点称为受助节点，这部分节点在全网所有节点中所占的比例如图8所示，平均每一次定位有72%的节点受到协助，可见，TSBMCL的优化范围是非常大的。

图8 节点优化比例

锚节点密度变化情况下的定位误差曲线如图9和图10所示，在锚节点密度Sd从0.5向5过渡的过程中，TSBMCL算法的定位精度始终高于MCB算法。图10反映出TSBMCL算法定位精度比MCB算法提高的比例，精度提高的比例最大可达34%，最低也在10%以上。之所以图10会呈现出先升后降的趋势，是因为在锚节点密度非常小的时候，由于网络中的锚节点太少，节点都很难获得足够好的锚节点信息，所以产生的临时锚节点也非常少，对网络定位优化的贡献不足，所以优化效果较差。当锚节点密度增大时，网络中有越来越多的节点定位情况变好而成为临时锚节点，并协助其他节点进行定位，所以对网络的优化效果更显著;但是当锚节点密度在3以上时，随着锚节点密度继续增大，网络中所有节点的定位情况都越来越好，MCB算法与TSBMCL算法的差距也在逐渐缩小，但TSBMCL算法在定位精度上始终比MCB算法提高20%以上。

节点密度变化情况下的定位误差曲线如图11和图12所示，随着节点密度的增大，TSBMCL算法对MCB算法的优化效果越显著，在Nd大于10时，定位精度提高的比例超过20%，当节点密度在40以上时，TSBMCL比MCB的定位精度提高了接近50%。

图9 锚节点密度变化情况下的误差对比

图10 锚节点密度变化情况下的定位精度提高比例

图11 节点密度变化情况下的误差对比

图12 节点密度变化情况下的定位精度提高比例

4 结束语

本文提出的TSBMCL算法，首先通过节点计算自身的权值来遴选出临时锚节点，并使用临时锚节点来协助其他节点进行定位，间接地增加了网络中锚节点的密度，从而优化了全网节点的定位效果，在定位精度上比MCB算法有了较大的提高。作为一种距离无关的定位算法，对硬件要求不高，能够满足低成本高精度的移动WSN的定位要求。

［1］ Niculescu D，Nath B.DV Based Positioning in Ad Hoc Networks［J］.Kluwer J.Telecommun.Syst，2003，22(1):267－280.

［2］ He T，Huang C，Blum B M，et al.Range-free Localization Schemes for Large Scale Sensor Networks［C］//Proceedings of The 9th annual international conference on Mobile computing and networking，San Diego，CA，2003:81－95.

［3］ Liu C，Wu K.Performance Evaluation of Range-Free Localization Methods for Wireless Sensor Networks［C］//Proceedings of The 24th IEEE International Performance，Computing，and Communications Conference，Phoenix，Arizona，2005:59－66.

［4］ Liu Jicheng，Wang Wenxiu，Shang Yintong.An Improving Localization Algorithm for Wireless Sensor Networks Based on DV-Hop［C］//Proceedings of the International Conference on Measurement，Information and Control，Harbin，2012(1):511－515.

［5］ Hu Tianyou.A Range-free Wireless Sensor Networks Localization Algorithm［C］//Proceedings of The 2nd International Conference on Engineering and Industries，Korea，2011:54－58.

［6］ Liu C，Wu K，He T.Sensor Localization with Ring Overlapping Based on Comparison of Received Signal Strength Indicator［C］//Proceedings of IEEE Int’l Conf.Mobile Ad-Hoc and Sensor Systems(MASS)，Fort Lauderdale，USA，2004:516－518.

［7］ Sheu J P，Chen P C，Hsu C S.A Distributed Localization Scheme for Wireless Sensor Networks with Improved Grid-Scan and Vector-Based Refinement［J］.IEEE Transactions on Mobile Computing，2008，7(9):1110－1123.

［8］ 丁江鹏，陈曙.一种基于跳数比的无线传感器网络定位算法［J］.传感技术学报，2009，22(12):1823－1827.

［9］ 朱博，陈曙.一种无线传感器网络质心定位改进算法［J］.传感技术学报，2010，23(6):868－872.

［10］ Sheu J P，Hu W K，Lin J C.Distributed Localization Scheme for Mobile Sensor Networks［J］.IEEE Transactions on Mobile Computing，2010，9(4):516－526.

［11］ Isaac Amundson，Xenofon D Koutsoukos.A Survey on Localization for Mobile Wireless Sensor Networks［C］//Proceedings of the 2th International Workshop on Mobile Entity Localization and Tracking in GPS-less Environments，Orlando，2009:235－254.

［12］ Mrityunjay Singh，Monika sethi，Niranjan Lal，et al.A Tree Based Routing Protocol for Mobile Sensor Networks(MSNs)［J］.International Journal on Computer Science and Engineering，2010，2(1S):55－60.

［13］ Zhang Shigeng，Cao Jiannong，Chen Lijun，et al.Accurate and Energy-Efficient Range-Free Localization for Mobile Sensor Networks［J］.IEEE Transactions on Mobile Computing，2010，9(6):897－910.

［14］ Hu L，Evans D.Localization for Mobile Sensor Networks［C］//Proceedings of the 10th International Conference on Mobile Computing and Networking，Philadelphia，USA，2004:45－57.

［15］ Baggio A，Langendoen K.Monte-Carlo Localization for Mobile Wireless Sensor Networks［J］.Journal of Ad Hoc Networks，2006，6(5):718－733.

［16］ Yi Jiyoung，Won YangSung，Cha Hojung.Multi-hop-based Monte Carlo Localization for Mobile Sensor Networks［C］//Proceedings of The 4th Annual IEEE Communications Society Conference on Sensor，Mesh and Ad Hoc Communications and Networks，San Diego，California，USA，2007:163－171.

［17］ Rudafshani M，Datta S.Localization in Wireless Sensor Networks［C］//Proceedings of the 6th International Symposium on Information Processing in Sensor Networks，Cambridge，MA，USA，2007:51－60.

［18］ Dil B，Dulman S，Havinga P.Range-based Localization in Mobile Sensor Networks［C］//Proceedings of Wireless Sensor Networks-Third European Workshop，Zurich，Switzerland，2006，3868(LNCS):164－179.

［19］ Camp T，Boleng J，Davies V.A Survey of Mobility Models for Ad Hoc Networks Research［J］.Journal of Wireless Communications and Mobile Computing，2002，2(5):483－502.