基于RSSI等级的蒙特卡罗定位算法应用研究

吴世通，陈良，李云飞，曹红飞

1.苏州大学计算机科学与技术学院，江苏苏州 215006

2.苏州大学机电工程学院，江苏苏州 215006

基于RSSI等级的蒙特卡罗定位算法应用研究

吴世通1，陈良2，李云飞1，曹红飞1

1.苏州大学计算机科学与技术学院，江苏苏州 215006

2.苏州大学机电工程学院，江苏苏州 215006

感知节点的定位是无线传感网应用的基础。现有的静态定位算法无法应用于动态传感网。针对一类目标节点移动而锚节点静止的传感网应用，提出了一种RRMCL（RSSI Rank Monte Carlo Localization）定位算法。该算法以蒙特卡罗算法为基础，利用RSSI（

Signal Strength Indication）值与距离的单调递减关系划分通信域，减少采样区域大小。为了避免锚节点共线出现定位失效的情况，引入共线影响角度，提出了一种约束策略。仿真结果表明，提出的RRMCL与现有的MCL和MCB定位算法相比，能有效缩小采样区域，提高了定位精度和速度。

无线传感网络；移动定位；蒙特卡罗；接收信号强度指示

1 引言

无线传感网已被大量运用于军事、工业控制、环境监测中。WSN是由大量感知节点组成的，其Ad-hoc通信方式导致WSN具有分布式架构，因此获得感知节点的准确位置较困难。然而，作为WSN应用的关键技术，节点的定位往往和数据本身一样重要；同时无线传感网的其他相关研究，如基于地理位置的信息路由技术，需要节点的位置作为支撑。因此，寻找WSN下合适的感知节点定位算法已成为许多高校和研究机构的研究热点。

目前，已有的文献方法多为静态定位算法，主要分为基于测距的定位[1]和无须测距的定位[2]。前者主要包括TOA（Time Of Arrival）定位[3]、TDOA（Time Difference Of A rrival）定位[4]、AOA（Angle Of A rrival）定位[5]、RSSI（Received Signal Strength Indicator）定位[6]等。无须测距定位算法主要包括Centroid定位算法[7]、DV-Hop定位算法[8]、Amorphous定位算法[9]等。然而，在实际的WSN应用中，存在大量移动传感节点。在该类网络中，静态算法由于没有考虑节点的移动性，易受环境扰动因素影响，定位效果不佳。

由于节点的移动，造成网络拓扑结构的频繁变化，通信和响应能力下降，使得定位更加困难。现有的移动目标定位算法主要有基于滤波方法的定位和基于Monte Carlo方法的定位。基于Monte Carlo方法的代表性算法有MCL（Monte Carlo Localization）和MSL（M obile and Static Sensor Network Localization）[10]以及其改进算法MCB（Monte Carlo Localization Boxed）[11]，该算法限制采样范围，解决了MCL算法中采样效率低的问题。

为了提出高效，易于应用的定位算法，对移动传感网进行分析，发现大部分网络存在如下特性，即锚节点固定，而未知节点移动，如机器人足球比赛、汽车移动物联网定位等。受此启发本文针对目标节点移动而锚节点静止的传感网应用，提出了一种基于RSSI等级的MCL感知定位算法RRMCL。主要思想是：将RSSI值运用到蒙特卡罗算法采样区域的计算过程中，作为初步定位；在此基础上通过采样和滤波进行细定位。同时考虑到RSSI值存在误差，当采样区域条件不匹配时，将采样区域的范围扩大一倍，减小RSSI值误差给定位结果带来的影响。相比MCL、MSL和MCB，RRMCL算法具有以下优势：（1）利用RSSI与距离的单调递减关系，将通信区域划分成M个同心圆，进一步缩小采样区域，提高了采样效率。（2）针对邻居锚节点共线或接近共线时容易产生定位失效的情况，引入共线影响角度，通过限制角度大小的方法，给出了一种约束策略。

2 Monte Car lo算法原理

Monte Carlo定位算法是一种贝叶斯滤波算法，将移动定位分为离散的时间段，若设t表示定位时刻，St表示t时刻节点位置分布，Wt表示从t-1时刻到t时刻收集到的锚节点的信息，条件概率p(st|st-1)表示从t-1时刻到t时刻位置预测的概率，p(st|wt)表示通过收集到的锚节点信息所预测的节点位置分布的可能性。一般来说，预测节点位置应利用所有以前阶段的观测值，即p(st|w0，w1，…，wt)，达到滤波的目的。

在预测阶段，假设节点可能的最大速度为vmax，节点t-1时刻位置为St-1，则节点t时刻位置分布只可能是以St-1为中心，以vmax为半径的圆，圆中采样点符合均匀分布即

其中，d(st|st-1)表示点st到st-1的欧式距离。由式（1）可以得到采样点集合。

过滤阶段，未知节点进行广播，若该节点能与锚节点进行直接通信，即获得未知节点的一跳路由，如图1所示。

图1 MCL一跳滤波区域选择

使用T代表此集合，对位置信息有如下过滤条件：

若节点与锚节点不能直接通信，但为两跳邻居，使用Q代表与该节点为两跳距离的锚节点集合，如图2所示。则对位置信息有过滤条件式（3）：

图2 MCL两跳滤波区域选择

满足上述条件的采样点则保留，不满足上述条件的则从集合filt(s)中去除，若集合中的采样点数目不满足要求则重新采样，重新过滤，直到达到要求为止，最后求出集合中采样点组成的多边形的重心坐标即为未知点的坐标。

3 RRMCL算法描述

RRMCL算法是MCL的一种改进算法，其基本思想是：首先将一跳和两跳锚节点的通信区域根据RSSI值递减划分成M个同心圆；其次，选择其中若干个锚节点，根据圆环的重叠区域计算采样区域；最后在采样区域采样，使用MCL算法定位。

3.1 利用RSSI等级确定采样区域

文献[12]给出了ROCRSSI算法，其是指用RSSI排序的方法将以通信半径为半径的圆划分成诸多圆环，通过求若干圆环的交集方式，得到未知节点的位置，属于静态定位算法。本文将此思想运用到移动定位中，建立同心圆模型后，利用未知节点移动的特征（远离锚节点或者靠近锚节点），以及t-1时刻的RSSIt-1值，选择RSSI1和RSSI2的同心圆组成圆环，其中RSSI1＜RSSIt-1＜RSSI2且彼此最邻近，则未知节点的下一位置在此圆环中。使用多个锚节点的RSSI值形成多个圆环，圆环的重叠区域即为采样区域。

3.1.1 RSSI同心圆模型建立

基于RSSI测距的定位算法，是无线定位技术中代表性算法。文献[13]给出的RSSI与距离的经验对应关系式，如下所示：

其中p(d)表示未知节点接收到锚节点的信号强度，p(d0)表示在距离锚节点为d0处的信号强度，k表示传输距离和信号强度损耗之间的比例因子，该值一般和所处环境和传输媒介相关，d表示未知节点和锚节点间的距离度量，nW表示锚节点与未知节点间需要穿过墙壁的数目，C表示事先确定信号能穿过墙壁个数的阈值，WAF表示信号穿透墙壁的衰减比例因子，该值和墙壁材料和结构相关。于是，在得到某RSSI强度后，可用上述经验公式反推出节点间的距离。本文不直接利用RSSI值求出的距离值来定位，而是作为MCL算法中缩小采样区域的手段。另外无线传感网中，节点往往计算能力和资源有限，因此本文采用广泛接受的近似关系式（5），降低计算复杂度，提高定位效率。

p(d)=-(10n lg 10d+p(1))（5）其中d表示未知节点到锚节点的距离，p(1)表示1 m距离的RSSI值。使用式（5）计算出距离，继而用此距离作为参数，将锚节点的通信区域分为M个不同半径的同心圆，其中各个圆环等距，从而将通信区域分为各个RSSI等级区域，如图3所示。

图3 RSSI等级区域图

为了控制计算复杂度，保证样本覆盖率，同时考虑节点移动速度。因此等级区域不能过多，本文经过大量实验验证，选定M=100vmax，其中vmax为节点最大移动速度。

3.1.2 采样区域的计算

为了描述方便，令S为两跳范围内的锚节点集合，则根据锚节点情况，可以分为以下四种情况讨论：

（1）S为空，则采样区域为以未知节点上一时刻(t-1)的坐标为圆心，以vmax为半径的圆。

（2）若S中为一个锚节点，记为s1，则未知节点选取收到此锚节点上一时刻的RSSI值，根据3.1.1节中的同心圆模型查询最邻近RSSI1和RSSI2(RSSI1＜RSSI＜RSSI2)，确定未知节点所在的RSSI等级圆环即为此时的采样区域，如图4（a）所示。

（3）若1＜S＜4，首先如（2）中所述，计算出各自的等级区域，然后，计算出这些等级圆环的重叠区域，即为采样区域。如图4（b）和（c）。

（4）若S≥4，计算等级区域的代价太大，不适合无线传感网中的节点，此外，锚节点过多会出现采样区域获取失败情况。因此，本文只考虑（1）、（2）、（3）三种情况。

若上述均定位失效，则将RSSI等级圆环扩大一倍，重新采样。

图4 采样区域的计算图

图4（c）表明：区域覆盖时会产生无效的交点，会影响采样区域的确定，本文使用如下步骤，排除无效交点。

（1）任选两个锚节点，求出其相交的区域所形成的圆环段。

（2）判断第三个锚节点形成的交点是否在圆环段内，若否，则排除无效交点。

（3）重复（2）操作直至排除所有无效节点。

3.2 共线约束策略

计算采样区域时，会发生锚节点共线导致定位失效的情况。文献[14]中采用四种方法描述了共线问题，但没有提出一种系统化的解决方案，文献[15]提出了一种锚节点共线解决方案，引入共线限制因子（Collinearity Lim iting Factor，CLF），根据CLF的值，改变锚节点分布。但需要比较各边长度，计算复杂，同时本文研究以锚节点静止为前提从而难于运用。因此本文提出一种新的共线约束策略，通过向量公式求夹角，引入共线影响角度（Collinearity Im pact Angle，CIA）降低了计算复杂度.同时若锚节点共线或接近共线，重新选择锚节点，提高采样区域成功率，具体方法如下：

选取三个锚节点A，B，C，任选其中两个节点组成向量，如图5所示，假设为AB，AC向量，其夹角即为共线影响角度（CIA）。若三点共线，则CIA值为0或者180，若不共线，则其取值范围为(0＜CIA＜180)，当(0＜CIA＜90)时，随着CIA的增加，共线度越低。当(90＜CIA＜180)时，随着CIA的增加，共线度越高，为了保持统一，此时采用（180-CIA）。

图5 共线度影响角度取值范围图

其中CIA由向量点乘公式（6）、式（7）求得：

在锚节点固定的情况下，选取某个共线影响角度作为最小阈值，计算一跳和两跳内的锚节点的共线影响角度，若小于阈值，则重新选择锚节点，重新判断，直至CIA大于阈值。

3.3 RRMCL算法

MCL算法过程可分为预测、采样和滤波三个阶段，RRMCL算法针对预测和采样阶段进行改进，通过减少采样区域，提高采样阶段成功率。算法初始化，即t=0时刻，使用RSSI值所得出的同心圆所相交的区域作为采样区域S0，未知节点从S0中选取N个样本，将这N个样本加权平均得到初始坐标值。当t＞0时，根据上一时刻未知节点坐标、锚节点信息、节点最大速度预测下一时刻位置节点的坐标。算法代码如下：

上述算法分为采样区域计算、样本获取、样本过滤和未知节点坐标的计算四个过程；其中采样区域计算过程中讨论了四种可能（见3.1.2节），并结合3.2节所讨论的锚节点共线影响角度，最终得出采样区域。样本获取即从已计算过的采样区域中随机选择若干个样本。样本过滤是根据MCL算法中的滤波条件（式（2）、式（3））将不符合条件的样本去除。最终将符合条件的样本点加权平均得到未知节点的坐标。

4 仿真实验分析

为了验证本算法的性能，基于MCL算法仿真器MCL-SIMULATOR（文献[10-11]均使用此仿真器）进行了仿真研究，250个节点随机地分布在400×400的矩形区域内，其中锚节点数为50，锚节点以及未知节点的通信半径为40 m，RSSI取值范围为（-95，-10）（单位：dB），其中-10 dB为距离为1 m时的RSSI值，-95 dB为距离40 m时的值。vmax表示未知节点移动的最大速度，算法的样本数目为40，系统每次仿真时间为600个时间单位。定位误差如式（8）所示：

其中l表示实际位置，li表示估计位置，r表示通信半径。

本文是MCL算法的改进算法，同时主要针对采样区域进行改进，因此本实验选择MCL和MCB算法与RRMCL算法作比较，从共线度、采样次数、节点移动速度、节点密度四个方面分析性能。

4.1 共线度影响角度

RRMCL算法的核心在于缩小采样区域，锚节点共线对计算采样区域影响较大，为了分析控制共线度影响角度对节点定位的影响，通过改变CIA的值，分析定位效果。

图6描述了共线影响角度对定位误差的影响，由于MCL算法中采样区域不受共线影响角度的影响，本文只分析了CIA对MCB和RRMCL算法的影响。由图6可知，当CIA＜30时，CIA对定位影响较大；当CIA＞45时，定位误差趋于稳定，CIA的值继续增大，对定位结果影响较小。故本文下面的仿真约定CIA的值为45（其下限阈值为30）。

图6 共线影响角度与定位误差

4.2 采样次数

设定采样样本数量后，MCL、MCB、RRMCL定位算法达到满足定位要求的样本数量时，所要采样的次数如图7所示。MCB算法和RRMCL算法均采用缩小采样区域手段，故采样次数明显比MCL算法少。RRMCL算法因为采用RSSI等级将采样区域进一步缩小，同时控制共线影响角度，减少共线所造成的定位失效情况。故采样次数少于MCB算法。

图7 不同方法的采样次数

4.3 节点移动速度

本文研究的是移动节点的定位，则节点的移动速度对算法的影响是衡量RRMCL好坏的关键。图8给出了节点移动速度vmax(vmax≤2 m/s)对定位精度的影响，从仿真结果可以看出，RRMCL算法优于MCB算法和MCL算法，定位精度和可靠性更好。这是由于MCL算法采样时，所选择的采样区域是以vmax为半径的圆，随着速度的增加，采样区域也随着增加，采样成功率降低。MCB算法虽然采用区域也会增大，但使用了锚盒子缩小采样区域，较MCL算法定位更好。RRMCL算法使用RSSI等级圆环计算采样区域，速度对其采样区域影响较小。故RRMCL优于MCB和MCL算法。

图8 节点速度与定位误差

4.4 锚节点密度的影响

在保持速度一致前提下，图9反映了节点密度与定位误差的关系，从图9可以看出，MCL、MCB、RRMCL算法随着锚节点密度的增加，定位精度都在提高。当节点密度很小时，定位误差较大，但节点密度达到0.1之后，则定位精度保持稳定。同样的节点密度时，RRMCL算法精度高于MCB和MCL算法，计算复杂度较低，定位效率高。

图9 节点密度与定位误差

5 总结

本文提出一种MCL改进算法RRMCL，给出一种计算采样区域的方法（RSSI等级圆环法）；同时讨论了锚节点数目变化时不同的计算方案。通过改变不同的仿真条件，分别分析了三种算法的定位精度和稳定性，RRMCL算法均表现出了良好的定位效果。另外，本文引入共线度影响角度(CIA)，并分析了CIA对定位效果的影响。仿真结果显示，通过控制CIA的大小，减少了锚节点共线的可能，继而减少了定位失效的可能，使得算法在锚节点数目较少和速度较大时表现出了良好的适应性。

[1]Frankie K W，So H C.Accurate distributed range-based positioning algorithm for wireless sensor networks[J]. IEEE Transactions on Signal Processing，2009，57（10）：4100-4105.

[2]Wang Y，Wang X D，Wang D M，et al.Range-free localization using expected hop progress in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed System，2009，20（10）：1540-1552.

[3]Ward A，Jones A，Hopper A.A new location for the active office[J].IEEE Personal Communication，1997，4（5）：42-47.

[4]Savvides A，Han C C，Srivastava M B.dynamic fine-grained localization in Ad-hoc networks of sensors[C]//Annual International Conference on Mobile Computing and Networking，New York，USA，2001：166-179.

[5]Niculescu D，Naith B.Ad-hoc Positioning System（APS）using AOA[C]//ACM INFOCOM，California，USA，2003，3：1734-1743.

[6]Bahl P，Padmanabhan V.RADAR：an in-building RF-based user location and tracking system[C]//ACM INFOCOM，Tel Aviv，Israel，2000，2：775-784.

[7]Bulusu N，Heidemann J，Estrin D.Density adaptive algorithm s for beacon placement in wireless sensor networks[C]//IEEE ICDCS，2001：489-498.

[8]Bulusu N，Heidemann J，Estrin D.GPS-less low-cost outdoor localization for very small devices[J].IEEE Personal Communications，2000，7（5）：28-34.

[9]Nagpal R，Shrobe H，Bachrach J.Organizing a global coordinate system from local information on an ad-hoc sensor network[J].Information Processing in Sensor Networks，2003，2634：333-348.

[10]Hu L，Evans D.Localization for mobile sensor networks[C]//Proceedings of the 10th Annual International Conference on Mobile Com puting and Networking，2004：45-47.

[11]A line B，Koen L.Monte-carlo localization for mobile wireless sensor networks[C]//Lecture Notes in Computer Science，2006，4325：1317-1328.

[12]Liu C，Wu K，He T.Sensor localization with ring overlapping based on comparison of received signal strength indicator[C]//Mobile Ad-hoc and Sensor System s，2004：516-518.

[13]Akyildiz I F，Su W，Sankarasubramaniam Y，et al.Wireless sensor networks：a survey[J].Computer Networks，2002，38（4）：393-422.

[14]Fidan B，Drake S P，Anderson B D O，et al.Collinearity problems in passive target localization using direction finding sensors[C]//5th International Conference on Intelligent Sensors，Sensor Networks and Information Processing，Melbourne，Australia，2009：114-220.

[15]刘克中，崔永强，张金奋，等.基于Monte Carlo的多能量级移动节点定位算法研究[J].计算机科学，2011：61-64.

WU Shitong1,CHEN Liang2,LI Yunfei1,CAO Hongfei1

1.School of Computer Science & Technology, Soochow University, Suzhou, Jiangsu 215006, China
2.School of Mechanical and Electric Engineering, Soochow University, Suzhou, Jiangsu 215006, China

The localization of perceptive nodes is the foundation for WSN（Wireless Sensor Network）applications. The existing static localization algorithms can not be used in dynamic sensor networks. In this paper, the so-called RRMCL（RSSI Rank Monte Carlo Localization）localization algorithm is proposed, which is about WSN applications where target nodes are moving while anchor nodes are static. The algorithm based on MCL divides communication region to reduce the size of sampling area by using the monotonic decreasing relation between RSSI value and the distance. In order to avoid localization failure caused by anchor node collinearity, the algorithm puts forward a constraint strategy which brings collinearity impact angle. The simulation results show that the proposed RRMCL can effectively reduce sampling area and improve the localization accuracy and speed, comparing with existing MCL and MCB algorithms.

Wireless Sensor Network（WSN）; mobile localization; Monte Carlo; Received Signal Strength Indication（RSSI）

WU Shitong, CHEN Liang, LI Yunfei, et al. Application and research on Monte Carlo localization algorithm based on RSSI rank. Computer Engineering and Applications, 2014, 50（17）：114-119.

A

TP391

10.3778/j.issn.1002-8331.1210-0074

国家自然科学基金（No.60775045，No.61003259）；江苏省科技计划项目（No.BC2011084）；苏州市科技计划项目（No. SG201101）。

吴世通（1989—），男，硕士生，主要研究领域为无线传感网；陈良（1981—），男，博士，副教授，研究方向为基于物联网的优化与控制；李云飞（1958—），男，教授，研究方向为无线传感网和虚拟现实；曹红飞（1987—），男，硕士研究生，研究方向为虚拟现实。E-mail：liyf@suda.edu.cn

2012-10-10

2012-12-20

1002-8331（2014）17-0114-06

CNKI网络优先出版：2013-01-11,http://www.cnki.net/kcm s/detail/11.2127.TP.20130111.0951.007.htm l