WSN中一种基于RSSI的移动节点改进定位算法*

黄海辉，李龙连

（重庆邮电大学 信息与通信工程，重庆400065）

WSN中一种基于RSSI的移动节点改进定位算法*

黄海辉，李龙连

（重庆邮电大学 信息与通信工程，重庆400065）

移动无线传感器网络的节点定位算法中，基于RSSI的MCL定位算法利用接收信号强度的对数正态模型对定位的预测和滤波过程进行了改进，改善了定位性能，但是仍存在计算量较大、功耗较大等不足。因为物体的运动状态不会发生突变，因而可以利用前几个时刻的轨迹，预测当前时刻的运动参数。采用Hermite插值法，对当前时刻的运动轨迹作了很好的预测。仿真结果表明，该算法与传统的算法相比，减小了采样范围，提高了采样准确率，从而提高定位精度，降低功耗。

无线传感器网络；节点定位；埃尔米特插值；蒙特卡洛；信号接收强度指标

0　引言

在无线传感器网络的关键支撑技术中[1]，定位技术是极其重要的组成部分，在其应用领域内，事件发生的位置信息是传感器节点监测消息中的重要信息，没有节点位置信息的感知数据是毫无意义的[1]。

无线传感器网络的定位算法根据节点间的测距要求，主要分为距离相关和距离无关两大类[2]。典型的距离相关的测距算法主要有：RSSI、TOA、TDOA、AOA等，分别利用三边测量法、三角测量法、极大似然估计法、最小二乘法等来进行节点定位；典型的距离无关算法主要有：质心算法、DV-HOP、MDS-MAP、APIT等。为提高定位精度，适宜采用距离相关的算法。在距离相关的几种测距算法中，通过表1可以看出：基于RSSI的定位算法具有成本低、容易实现等优点，在对定位精度不高的情况下得到了广泛的应用。另外，目前很多传感器节点都提供测量信号发射功率的功能，可以在节点广播消息包的同时完成RSSI测量值的获取，并且这种定位算法无需额外的硬件支持和复杂的数据处理，也不会增加通信开销，能有效减少节点的硬件成本和能量消耗，适用于无线传感器网络。

表1　基于距离的各种测距算法的优缺点

近十年来，WSN获得快速发展，人们研究的对象不仅仅针对静态WSN，而且渐渐地关注动态网络的节点定位技术，这样的要求就使得静态定位算法在移动环境下就变得无效了。经典的WSN移动节点定位算法主要有：MCL[3]、MCB[4]、MSL和MSL*[5]、MMCL[6]、rang-based-MCL[7]、RSS-MCL[8]、OTMCL[9]等。

弗吉尼亚大学的Hu和Evans首次提出了将蒙特卡洛定位算法应用于移动无线传感网络节点定位中[3]，其提高了定位精度，减少了定位开销；针对MCL采样效率低的问题 Baggio A和Langendoen K提出了蒙特卡洛盒子定位（Monte Carlo Localization Boxed，MCB）算法[4]；约克大学的Rudafshani M和Datta S提出了移动和静态传感网络定位算法MSL和 MSL*算法[5]；Dil B提出的Range-based-MCL[7]算法为基于距离的移动WSN定位，通过利用未知节点与锚节点之间的距离信息，可以滤波得到更精确的位置样本，提高了定位精度。特别需要指出的是，Wang[8]等人将MCL和RSSI定位算法相结合，提出了基于RSSI的MCL定位算法，利用接收信号强度的对数正态模型对定位的预测和滤波过程进行了改进，改善了定位性能。

上述算法中，基于RSSI的MCL定位算法效果良好，在定位技术的研究和实际运用方面都有很大的意义，但存在计算量较大、无运动预测性等不足。因此，本文在文献[3]和文献[8]的基础上，对移动无线传感器网络节点定位进行了深入研究，提出了一种基于RSSI的改进蒙特卡罗定位算法RSSI-IMCL。事实上，节点在运动过程中的运动参数一般不会突变，且基于RSSI的MCL算法没有考虑运动预测问题，因而可以利用前几个时刻的轨迹，预测当前时刻的运动参数，减小采样范围，提高采样准确率，从而提高定位精度，降低节点功耗。

1　基于RSSI的改进MCL算法

本文提出的算法是对基于RSSI的蒙特卡洛算法的一种改进，基本思想与经典MCL和基于RSSI的MCL算法相似。即首先建立与描述该问题有相似性的概率模型，然后对模型进行随机模拟或统计抽样，再利用所得的结果求出特征量的统计值作为原问题的近似解，并对解的精度作出某些估计。

1.1RSSI模型

一般的RSSI通信模型都认为网络中各节点为各向同性，例如自由空间传播模型、双射线模型、哈他模型等皆为各向同性，这类模型皆是按照式（1）的框架建立的模型。

自由空间传播是电波在真空中无阻挡视距传播的一种理想状态。其模型可以表示为式（2）：

式(2)中，Lfs为传输损耗，d为节点距离，k为路径衰减因子，一般取值为2，频率单位以MHz计算。

在实际传输过程中，多径现象不可避免，信号在传输时可能被一些障碍物吸收，或是发生反射、散射或衍射。这时我们可以采用不规则无线电模型来模拟实际应用环境，该模型在不同方向的路径损耗是不同的。图1表示的是自由模型和不规则电模型下RSSI值的比较。不规则电模型公式为式（3）：

式(3)中，Pr(d)为接收功率，Pt为发送功率，PL(d0)为参考距离时的路径损耗。

图1　自由模型和不规则电模型下RSSI值的比较

1.2基于RSSI的MCL算法

蒙特卡洛定位其实就是一个粒子滤波算法，每一个定位时刻都被分为了预测和更新两部分。在预测阶段，根据节点速度信息和在上一定位时刻的粒子集确定采样区域，并随机采样得到粒子；在滤波阶段，根据收到的锚节点信息，对预测阶段的粒子进行筛选，滤除不符合观测条件的，并用满足滤波条件的粒子的均值来估计节点的位置，如果滤波得到的粒子数没有达到定位所需的粒子数，则执行重采样和滤波过程，直到得到足够数量的粒子或者达到最大采样次数为止。

以下三个步骤详细说明了基于RSSI的MCL算法的定位过程。假设整个无线网络中，有一个未知的移动节点和M个位置已知的锚节点随机分布在整个区域中。

（1）预测阶段

在预测阶段，传感器节点需要根据前一时刻的粒子集Lt-1和运动模型确定当前时刻的粒子集Lt。假设节点按照随机行走模型（RWP）进行移动，该模型中，节点在任何时刻都不知道自己的运动速度和方向，仅仅知道自身的最大运动速率为 vmax，方向为360°任意选择。那么转移分布p(mk|mk-1)便形成了一个以mk-1为圆心，以 vmax为半径的圆。表示如式（4）

在MCL算法的预测阶段，基于前一时刻位置对当前时刻位置进行预测，节点可能的位置从上述的圆形区域随机采样获得，该圆形区域就是采样区域。

（2）滤波阶段

在滤波阶段，节点将根据新的观测信息，将不符合网络连通度条件的位置样本滤除掉。如果样本满足滤波条件，则概率分布为1，否则为0。如果满足滤波条件的粒子数达到了定位所需数量，则将这些粒子取均值作为节点的估计位置；如果粒子数不足，则重复预测和滤波过程，直到得到足够数量的粒子或达到最大采样次数为止。在MCL算法中，为方便计算，选择状态转移概率密度函数为重要性函数，则每一时刻粒子的重要性权值可通过下列方法递归计算：

式(5)为预测阶段，节点可以在前一时刻可能位置的基础上预测当前时刻的可能位置。式(6)为更新阶段，节点可以根据接收到的观测信息更新当前时刻的粒子权值。然后用式(7)对权值进行归一化，从而可以用一组带权值的样本集(，)来估计节点位置的后验概率分布。

（3）重采样阶段

计算当前的位置需要重复进行预测和更新，将不可避免地出现粒子退化现象。因此需要重采样，将权重值小的样本淘汰，将权重值大的保留，用式（8）定义有效粒子数 Neff，当 Neff小于设定的门限值 Nthreshold时，就需要进行重采样。

基于RSSI的MCL算法相比于经典的MCL算法，较大幅度地提高了定位精度，取得了良好的效果，但计算量较大，节点功耗过快，需要改进。

1.3基于RSSI的改进MCL算法

针对基于RSSI的MCL算法的不足，本文提出了一种基于RSSI的改进MCL算法。在基于RSSI的MCL算法的预测阶段，k时刻的位置概率分布只与k-1时刻的位置及速度有关，没有考虑k-1时刻之前的运动情况的影响，本文采用基于历史轨迹的运动预测机制来提高先验概率的准确性，也就是意味着可能更高的定位精度和可能更少的迭代次数，从而降低节点的功耗。

Newton插值法和 Lagrange插值法虽然构造比较简单，但是存在插值曲线在节点处有尖点、不光滑、插值多项式在节点处不可导等缺点，因此本文选择Hermite插值法。一般，Hermite插值多项式Hk(x)的次数k如果太高会影响收敛性和稳定性称为 runge现象。本文中，就采用前两个时刻的位置信息，因此不会出现runge现象。

设 f(x)在节点 x0、x1处的函数值为 y0、y1，在节点 x0、x1处的一阶导数值为，两个节点最高可用3次 Hermite多项式H3(x)作为插值函数。H3(x)应满足的插值条件为。设H3(x)的插值基函数H3(x)=a0h0(x)+a1h1(x)+a2h2(x)+a3h3(x)，即。

希望该函数与Lagrange和 Newton插值一样简单，重新假设：

在算法预测阶段，利用历史轨迹，提高了当前位置预测的准确性，减小了采样范围，提高了采样准确率，从而降低节点功耗。

2　仿真分析

仿真实验使用MATLAB进行，该仿真实验是在一个14 m×10 m的矩形平面区域进行的。信标节点随机地分布在平面区域内，其位置是固定不变的且坐标是已知的；未知节点方向和速度大小都随机移动，且其移动速度不会超过设定的最大速度。网络中使用的参数设定如下：节点的最大移动速度取 10 m/s，信标节点和未知节点的通信半径相等且都取3 m。

图2和3显示的是MCL定位算法和基于RSSI改进的定位算法的定位仿真图，可以看出，改进的算法定位的轨迹更接近实际轨迹，定位精度有明显的提高。

图2　MCL定位算法仿真图

图3　基于RSSI的改进MCL定位算法仿真图

定位误差用于描述定位结果的精确程度，本文用到的定位误差的定义如下：

其中，(xi，yi)为未知节点的实际位置，为用算法估计出来的坐标位置。如图4可知，随着时间的推移，定位次数的增加，定位误差也在减小。

图4　定位误差与定位次数的仿真图

3　结论

本文对基于RSSI的蒙特卡洛无线传感定位算法进行了深入研究，并在此基础上提出了一种基于RSSI的改进蒙特卡洛定位算法。该算法在定位精度、计算量、对锚节点密度的要求和对粒子样本集的要求等性能都有所提升，且通过仿真实验证明该算法在移动的WSN中是一个高效的定位算法。

[1]冯砚毫，曾孝平，江禹生.无线传感器网络节点定位技术研究[D].重庆：重庆大学，2011.

[2]黄俊霖，杨刚.基于 RSSI分级的 WSN节点定位算法研究[D].西安：西安电子科技大学.2013.

[3]Hu Lingxuan，EVANS D.Localization for mobile sensor networks[C].Proc of the 10th Annual International Conference on Mobile Computing and Networking(Mobicom04)，Philadelphia，Pennsylvania：USA，2004：45-57.

[4]BAGGIO A，LANGENDOER K.Monte carlo iocalization for mobile wireless sensor networks[C].Proceedings of the 2nd International Conference on Mobile Ad-hoc and Sensor Networks(MSN′06)，Dec 13-15，2006，Hong Kong，China. LNCS 4325.Berlin，Germany：Springer-Verlag，2006：718-733.

[5]RUDAFSHANI M，DATTA S.Localization in wireless sensor networks[C].Information Processing in Sensor Networks，2007.IPSN 2007.6th International Symposium on，pp. 51，60，25-27 April 2007.

[6]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.

[7]DIL B，DULMAN S，HAVINGA P.Range-based localization in mobile sensor networks[J].Wireless Sensor Networks，2006：164-179.

[8]WANG W D，ZHU Q X.RSS-based Monte Carlo localization for mobile sensor networks[J].Communications，IET，2008，2(5)：673-681.

[9]MARTINS M H T，CHEN H，SEZAKI K.OTMCL：Orientation tracking-based Monte Carlo localization for mobile sensor networks[C].Proceedings of the 6thInternational Conference on Networked Sensing Systems(INSS)，2009：1-8.

[10]李伟，丁勇，于春娣，等.一种基于 RSSI的改进蒙特卡罗定位算法[J].计算机应用与软件，2013(12)：280-283.

An improved localization algorithm based on RSSI in WSN

Huang Haihui，Li Longlian
（Chongqing University of Posts and Telecommunications，Information and Communication Engineering，Chongqing 400065，China）

Among the localization algorithms for mobile wireless sensor network nodes,the RSSI-based MCL location algorithm using the

signal strength of the lognormal model improved prediction and filtering process oflocalization,and also improved positioning performance.However,there are still large amount of calculation and large power consumption,etc.Because the movement state of the object is not a mutation,it is possible to use the first few moments of the trajectory and the motion parameters of the current time could be predicted.This paper uses a Hermite interpolation method,the trajectory of the current moment made a good prediction.Simulation results show that compared with the conventional the algorithm,the sampling range is reduced，the sumpling accuracy is improved，and then the localization accurary is improved，the power consumption of the nodes is reduced.

wireless sensor network；localization；hermite monte carlo algorithm；

signal strength indication

TP393

A

0258-7998(2015)01-0086-04

10.16157/j.cnki.0258-7998.2014061902241

国家自然科学基金项目（61171190）

2014-06-03)

黄海辉(1969-)，男，主要研究方向：物联网和 3D图像处理。

李龙连(1989-)，女，硕士研究生，主要研究方向：无线传感器网络。