摘要：针对无线传感器网络（WSN）中以蒙特卡罗为基础的移动节点定位算法在采样效率和定位精度方面的不足，提出一种基于接收信号强度指示（RSSI）测距的蒙特卡罗盒定位（MCB）算法。通过对RSSI测距信息分区间管理来加强过滤条件，提高定位精度；同时采样阶段利用已满足过滤条件的样本点生成更有效的样本，从而提高采样效率；最后通过牛顿插值法预测节点运动轨迹，样本点与未知节点运动轨迹越接近则其权值越大，据此对样本点进行加权处理得到节点的最佳估计位置。仿真结果表明，改进方案在不同的锚节点密度、通信半径、运动速度等情况下均表现出良好性能，且定位精度与同等条件下的蒙特卡罗盒算法相比均有提高。
关键词：无线传感器网络；移动定位；蒙特卡罗盒定位；接收信号强度指示；运动预测
中图分类号：TP202.2；TP202.7
文献标志码：A
Abstract：To solve the shortcomings of sampling efficiency and positioning accuracy of the Monte Carlo localization algorithm in Wireless Sensor Networks （WSN）， a Monte Carlo localization Boxed （MCB） algorithm for mobile nodes based on Received Signal Strength Indication （RSSI） ranging was proposed. To improve the positioning accuracy， the filter conditions was strengthened by mapping the ranging information into different distance intervals. At the same time， the samples which had already met the filter conditions were used to create more effective samples so as to improve the sampling efficiency. Finally， the Newton interpolation was used to predict the nodes trajectory. The closer the trajectory between the sample and the node is， the greater the weight of the sample is， and the best estimate position could be obtained with these weighted samples. The simulation results indicate that the proposed algorithm has good performance in different density of anchor node， communication radius， and movement velocity etc.， and compared with the MCB algorithm， the proposed algorithm has higher positioning accuracy.
英文关键词Key words：Wireless Sensor Network （WSN）； mobil e localization； Monte Carlo localization Boxed （MCB）； Received Signal Strength Indication （RSSI）； motion prediction
0 引言
在无线传感器网络（Wireless Sensor Network， WSN）的许多应用中，不仅要求传感器节点提供监测信息，还需要其报告自身的位置信息，多数的监测信息若没有准确的位置信息将变得毫无价值。例如，军事应用中需要知道敌方车辆的运动情况，灾害救援应用中需要知道火灾或其他灾害发生的具体位置，野生动物监测应用中需要明确动物的活动区域等。高效、精确的位置服务是无线传感器网络众多应用得以实现和推广的基础，因此，研究WSN中的节点定位技术具有重要意义。
目前大多数WSN定位算法是针对静态网络而设计的，可以分为基于测距的算法和无需测距的算法两类[1-3]。基于测距的定位算法常用技术包括到达时间（Time Of Arrival，TOA）[4]、到达时间差（Time Difference Of Arrival，TDOA）[5]、接收信号强度指示（Received Signal Strength Indication， RSSI）[6]、到达角度（Angle Of Arrival，AOA）[7]等；该类算法需要在传感器节点安装测距设备，定位精度高，但成本代价也大。无需测距的定位算法常用技术包括质心定位[8]、近似三角形内点检测（Approximate PointIntriangulation Test， APIT）[9]、多维标度地图（Multidimensional ScalingMap， MDSMAP）[10]定位、距离矢量跳数 （Distance VectorHop，DVHOP）[11]等；这类算法虽然定位精度相对基于测距的算法较低，但成本低廉，获得了广泛应用。在一些现代化的应用中，传感器节点处于移动状态，例如车载自组网（Vehicular Ad Hoc NETwork， VANET）、军用自组网、移动目标跟踪等。当对某节点进行定位后，该节点的实际位置已经发生改变，因此，对WSN中移动节点的定位技术研究就非常重要。如何利用节点的移动性，设计出适合网络结构动态变化的移动无线传感器网络定位算法，也成为近些年的一个研究热点。
在移动无线传感器网络中，节点间的距离信息和网络拓扑结构不断变化，若将传统定位算法应用到移动传感器网络，只能用迭代计算的方法实现节点定位。这种做法无疑增加了网络的能耗，并且定位结果有时延，定位精度不高。文献引入在移动机器人定位领域常用的序贯蒙特卡罗思想，提出了适合移动传感器网络定位的蒙特卡罗定位（Monte Carlo Localization，MCL）算法。
MCL算法源于贝叶斯滤波，其主要思想是利用一系列带有权值的样本来估计节点的后验概率密度分布，并通过重要性采样不断更新样本集合[13-14]。MCL算法巧妙地利用了节点的移动性，提高了移动节点的定位精度，但在采样过程易出现粒子退化问题。为了提高算法性能，一些学者提出了基于MCL的改进算法：Stevens等[15]提出了Dual MCL和Mixture MCL算法，Dual MCL通过改变MCL算法的逻辑顺序来提高定位精度，Mixture MCL则是综合使用MCL算法和Dual MCL算法。Yi等[16]提出多跳蒙特卡罗定位（Multihopbased Monte Carlo Localization， MMCL）算法，利用测距信息来提高定位精度。Baggio等[17]提出了蒙特卡罗盒定位（Monte Carlo localization Boxed， MCB）算法，通过建立锚盒和采样盒来提高定位精度，但是当观测模型在锚盒内分布比重较低时，采样效率低，定位误差大。
总结以上算法中的优点和不足，本
文在蒙特卡罗盒思想的基础上，深入分析MCB算法各阶段的影响因素，提出了基于RSSI测距和运动预测的MCB（RSSI Motion Prediction MCB， RMMCB）算法，并进行了Matlab仿真。RMMCB算法继承了基于测距的定位算法定位精度高的优点，通过引入RSSI测距信息，使采样区域更加精确；同时利用已有样本信息生成新样本，弱化了粒子退化现象。在进行位置估计时，构建节点运动预测模型，利用节点运动轨迹信息对样本进行加权处理，进一步提高定位精度。
1 RMMCB算法
1.1 MCB算法
MCB算法通过将时间离散化，在每个时间段内对节点重定位实现对移动节点的实时定位。MCB算法是对MCL算法的一种改进，通过构建锚盒和采样盒，在锚节点通信覆盖范围相互重叠的区域采样，缩小了采样范围，提高了采样效率。
MCB算法主要包括以下5个阶段：
1）初始化阶段。首先未知节点判断是否到达定位时间，若是则转阶段2）并在未知节点的锚盒内随机采样，构成初始化样本集L={l1，l2，…，ln}；否则继续等待。
2）预测阶段。预测阶段包括锚盒和采样盒的构建。待定位节点根据侦听到的一跳和两跳锚节点通信范围的重叠部分构建锚盒，为简化计算将表示锚节点通信范围的圆形区域近似为圆的外切正方形。
如图1所示，以黑色圆点为中心的两个正方形重叠区域就是由一个一跳锚节点和一个两跳锚节点构成的锚盒B。设移动节点的最大移动速度为vmax，节点上一时刻的位置为lt-1，可以预测节点下一时刻的位置lt在以lt-1为圆心、vmax为半径的圆内，以lt-1为中心、2vmax为边长构建正方形区域A，则采样盒就是A和B的交集。图1中阴影区域代表采样盒。
3）过滤阶段。根据所侦听到的锚节点是一跳还是两跳，构建过滤条件，将所有不可能的位置lt从样本集Lt中移除。
4）重采样阶段。过滤之后的样本集中的样本点个数可能小于规定的最小样本数N，这时就需要进行重新采样，重复预测阶段和过滤阶段直到有效样本点数大于等于N，停止采样，进入5）。
5）位置估计。计算N个样本点的数学期望值作为未知节点的估计位置。
1.2 RMMCB算法
MCB算法较之前的MCL算法定位精度虽然有所改善，但仍然存在一些问题。首先，MCB算法中以边长为2r的正方形重叠区域作为锚盒，通信半径r的取值一般较大，因此以r为约束条件构建的锚盒区域也会较大，这就增加了未知节点位置的不确定性；其次，由于节点运动方向的随机性，需要在整个圆内进行采样，当采样盒面积较小时，就降低了采样效率；再次若样本数量小于阈值N，则重复进行预测阶段和过滤阶段，如果一直达不到样本数量的阈值N，算法会循环进行直到达到最大循环次数，这无疑增加了算法的计算量，降低了算法的运行效率。针对这3个问题，本文提出的RMMCB算法，分别对预测阶段、过滤阶段以及位置估计阶段进行了改进和优化，仿真实验结果表明，RMMCB算法能有效提高定位精度。
1.2.1 过滤条件优化
MCB算法的核心是预测和过滤阶段。理论上采样区域越小，则由该区域限定的样本越有效，进而可以获得较高的定位精度。过滤的实质就是进一步缩小样本区域，考虑到基于测距的定位算法有较高的定位精度，并且信号强度接收装置成本低容易实现，所以本文通过引入RSSI值构建分区间测距模型，对过滤条件进行优化。
1）RSSI测距模型。
在实际环境中，射频信号会受到非视距（NLOS）、多路径（MultiPath）、绕射等多种因素影响，并会随着通信距离增加逐渐衰减，衰减量也会因环境的不同而不同，基于以上因素，可以按照对数正态分布进行建模。在WSN中，式（1）表示的RSSI测距模型能精确描述实际信号的传播，并已成功应用于许多定位系统中。
2）过滤条件。
将由式（1）得到的RSSI值进行分级处理会使采样区域更加精确，考虑到不同传感器网络中节点通信半径不同，为了适应不同通信半径的网络，将锚节点的通信半径分成r/m（若为小数则根据四舍五入法则取整）个距离区间。根据定位系统的精度要求，m可以灵活取值，这样本文算法就能更好地适应不同通信半径的网络。
本文算法在仿真中，取r=30m，m=10m，则若某锚节点是一跳锚节点，则将0到r的距离分成r/m=3个区间，R1=[0，10），R2=[10，20），R3=[20，30]。若是两跳锚节点，则将r到2r的距离分为r/m=3个区间，Z1=[30，40），Z2=[40，50），Z3=[50，60]。
以锚节点所在位置为圆心、距离区间端点为半径画圆，则形成不同的圆环区域。未知节点根据式（1）估计出自己与锚节点的距离D， D落在哪个距离区间则未知节点落在该区间与锚节点所形成的圆环区域内的概率最大。如图2所示，阴影区域为两个一跳锚节点所限定的样本区域。
1.2.2 采样优化
过滤之后，当采集到的样本点数量不足阈值N时，一般的处理方法是重复进行预测和过滤阶段，直到取到足够的样本点，但如果采集到的样本点一直没有达到N，就有可能导致算法循环执行，效率降低。受遗传算法启发，本文提出利用已经采集到的有效样本点来生成新样本点的方法来提高采样成功率。满足过滤条件的样本点所在的区域都是未知节点后验概率密度分布较大的区域，在包含所有有效样本点的区域内进行重采样，可有效提高采样成功率。
为了简化运算，本文取能够包含所有已经满足过滤条件的样本点的最小矩形区域作为重采样区域，假如已经满足过滤条件的有效样本点有n（2 当仿真参数设置为表1所列各值的情况下，运行算法得到图3的仿真结果，初始时刻定位误差较大是因为未知节点将自己的位置初始化为仿真区域的中心，当经过一个定位周期，节点的定位误差迅速收敛。可以看出，随着时间的推移，两种算法的定位误差均能保持稳定，这是因为当节点位置的累积误差达到一定程度会导致如图1中的A和B两部分没有交集，无法构成采样盒，导致采样失败，此时直接在锚盒中进行采样，避免了累计误差的进一步增大，保证了节点定位误差稳定在一个较低水平。从图3也可看出，改进算法的定位精度明显优于原始MCB算法，定位精度提高约20%。
蒙特卡罗算法用节点最大运动速度作为预测节点位置的区域半径：一方面，节点运动速度越大，节点下一时刻的预测区域就越大；另一方面，节点移动越快，未知节点能够接收到的锚节点信息就越多，过滤掉的无效位置也
越多。两方面的原因，前者会使定位误差增大，后者会使定位误差降低，二者相互作用使节点运动最大速度对定位误差有较大影响。从图4可看出：随着速度的增大，节点的定位误差先降低，这是未知节点接收到的锚节点信息增多的效果。当节点运动速度超过10m/s，定位误差随着节点运动速度的增加而增大，这是由于节点运动速度的增加导致节点下一时刻的预测区域增大。两种算法的定位误差变化趋势相似，但随着节点运动速度增大，改进算法相对于MCB算法的优势越来越明显，定位精度提高超过20%。
由于未知节点利用一跳和两跳锚节点的信息进行定位，所以锚节点密度越大，则定位误差越小；并且，当锚节点密度较大时，由节点分布的不均匀性所带来的定位误差会大大降低。但是在无线传感器网络中，布置锚节点的成本较高，为了降低成本，需要找到一个平衡点，用较少的锚节点获得较高的定位精度。从图5可看出：当锚节点密度Sd=3时，MCB算法的定位误差约为0.3r，改进算法的定位误差约为0.2r，两种算法均在Sd=3时取得较低的定位误差，且改进算法比MCB算法的定位误差约降低0.1r。
通信半径对节点的定位精度也有较大影响，从图6可看出：随着通信半径的增大，两种算法的定位误差开始时都逐渐降低；当通信半径大于40m时，定位误差趋于稳定，MCB算法的定位误差稳定在0.35r左右，改进算法的定位误差稳定在0.25r左右。误差曲线的这种变化是由于当其他参数不变，只有通信半径增大时，待定位节点的一跳锚节点和两跳锚节点的数目增多，能够有效限定采样区域，提高定位精度。RMMCB算法利用了节点的接收信号强度信息，进一步限定了采样区域，并利用节点的历史位置信息，使未知节点的估计位置向后验概率密度较大的区域移动，故其平均定位误差较MCB算法小。
3 结语
本文提出了一种适用于无线传感器网络中移动节点的定位算法，以MCB算法为核心，对其关键阶段进行了优化改进。算法引入RSSI测距模型，有效降低了多径、绕射、非视距等因素对测距信息的影响，并将测距信息映射到不同的距离区间，进一步约束了采样区域。采样过程利用了已满足过滤条件的样本点，提高了采样成功率。同时根据样本与节点运动轨迹的接近程度不同，赋予样本不同的权值，使估计位置更接近真实位置。最后用Matlab进行了仿真，结果表明在相同条件和参数下与传统MCB算法相比，本文提出的改进方案能有效减小定位误差，提高定位精度。算法在实际环境中的性能表现，是未来工作的研究重点。
参考文献：
.通信学报， 2008， 29（11） ：62-66.）
