引入RSSI指纹抖动量的室内定位改进算法

邓 遂,邓瀚林,潘 强,刘海涛

(无锡物联网产业研究院,江苏无锡214213)

引入RSSI指纹抖动量的室内定位改进算法

邓 遂,邓瀚林,潘 强,刘海涛

(无锡物联网产业研究院,江苏无锡214213)

为提高接收信号强度指示(RSSI)指纹进行室内定位的准确性,提出一种利用RSSI指纹抖动量的虚拟标签定位改进算法。给出RSSI指纹抖动量计算方法,将其应用于待定位标签与参考标签的距离以及虚拟标签RSSI指纹的计算。在实际测试中,将RSSI指纹抖动量用于虚拟标签定位算法射频指纹(RFFP)的改进。测试结果表明,与RFFP算法和LANDMARC算法相比,改进算法的平均定位精度分别提高约0.35 m～0.88 m和0.38 m～0.94 m,算法耗时仅分别增加约1%和12%。

室内定位;无线射频识别;接收信号强度指示;指纹;虚拟标签;无线传感器网络

1 概述

近年来,随着室内无线设备的广泛应用,基于接收信号强度指示(Radio Frequency Identification, RSSI)的室内定位算法一直是研究的热点和难点。由于室内环境存在复杂和动态变化的特点,采用建模方法对室内无线信号的损耗进行分析带来的定位误差较大;而其他采用如超声波、超宽带等技术的室内定位方法[1]受成本、使用条件限制,难以满足普遍情况下的室内定位需求。RSSI指纹定位技术是利用一组位置已知的节点接收信号强度指标对待定位节点进行定位的方法;这一组位置已知的节点叫参考节点,其接收到的待定位节点的信号强度指标序列就叫做待定位节点的指纹。本文的节点泛指能进行无线信号传输的设备。RSSI指纹定位技术不需要额外增加硬件,不依赖室内无线信号传输损耗模型,也不受室内各种使用条件限制,是较理想的室内定位解决方案。

RSSI指纹定位技术一般包括离线学习和在线定位2个阶段[2]。在离线学习阶段,定位主机收集参考节点的RSSI指纹,建立RSSI指纹的空间分布关系;在线定位阶段,待定位节点的RSSI指纹与离线阶段建立的RSSI指纹的空间分布关系进行匹配,进而估计出待定位节点的空间位置。RSSI指纹定位技术的关键在于如何在RSSI指纹库中选择与待定位节点RSSI指纹接近的指纹,以及如何利用选择的RSSI指纹的空间分布关系估计待定位节点的位置。

微软在1998年提出的RADAR系统[3]是早期RSSI指纹定位技术的典型代表。RADAR室内定位系统在离线阶段存储70个不同位置的RSSI指纹,在线阶段则利用K近邻算法估算待定位节点的位置;在此基础上,美国马里兰大学研发的Horus系统[4]引入了RSSI指纹的概率模型;加利福尼亚大学研发的Nibble系统[5]采用接收信号信噪比指纹来代替RSSI指纹,并建立指纹库的连续分布概率模型;此外,采用神经网络训练方法、贝叶斯方法、蒙特卡罗方法、跟踪辅助定位等技术手段[6],均能在一定程度上提高RSSI指纹定位技术的定位精度。

LANDMARC是应用无线射频识别(Radio Frequency Identification,RFID)技术进行室内定位的系统[7],通过利用已知位置的有源参考标签实时RSSI指纹来动态反映环境信息;对待定位标签的定位则通过比对待定位标签与参考标签的RSSI指纹差异,利用残差加权算法进行计算实现。LANDMARC系统具有成本较低、容易实现和较强环境适应性特点,定位精度和稳定性相对较高。在LANDMARC系统基础上,国内外研究人员针对其不足进行了各方面改进。其中,通过引入虚拟参考标签的VIRE算法在不增加硬件设施前提下提高了定位准确性[8];其他改进方法包括构建虚拟参考标签空间[9]、引入高斯拟合动态权重[10]、虚拟标签RSSI插值方法优化等[11]。文献[12]提出了RFFP(Radio Frequency Fingerprints)虚拟标签定位算法,通过合理设计虚拟标签的布设位置和选择适当的插值方法,在降低虚拟标签定位算法计算量的前提下提高了定位准确性。

本文在RFFP算法基础上,引入RSSI指纹抖动量对邻近节点的权重进行重新分配,以提高虚拟标签定位算法的准确性和稳定性。

2 LANDMARC系统和虚拟标签定位算法

LANDMARC系统由多个位置固定且已知的有源RFID标签和若干个阅读器组成。假设系统中有n个阅读器和m个参考标签,待定位标签个数为u,参考标签j的位置坐标为(xj,yj,zj);在时刻t阅读器i接收到标签j(包括参考标签和待定位标签)的无线信号接收强度为si,j,t,则标签j在时刻t的RSSI指纹为Sj,t=(s1,j,t,s2,j,t,…,sn,j,t),时刻t待定位标签k与参考标签j的RSSI指纹距离定义为:

从m个参考标签中,挑选出与待定位标签k最近的N个,即从{Ek,1,t,Ek,2,t,…,Ek,m,t}中选出最小的N个,记为{Ek,g1,t,Ek,g2,t,…,Ek,gN,t},然后对标签{g1,g2,…,gN}的位置坐标进行加权求和,得到待定位标签k在时刻t的估计位置:

其中:

VIRE算法在LANDMARC系统的基础上,引入了虚拟参考标签进行辅助定位,但是由于采取的是全景式虚拟标签插入方法,计算复杂度太大,且提高的定位精度有限。RFFP算法在VIRE算法的基础上,主要从虚拟标签的布设方式和RSSI指纹计算方法2个方面进行了改进。

VIRE算法是在整个定位区域内所有真实标签之间布设虚拟标签,这样带来了计算量大的问题;而RFFP算法不同,先找出与待定位标签RSSI指纹距离最小的N个真实参考标签,然后在这个参考标签覆盖的区域内布设K个虚拟标签,如图1所示,在与待定位标签RSSI指纹距离最小的3个参考标签连线上,等距布设6个虚拟标签,然后选择2组虚拟标签,在其连线上等距布设4个参考标签,这样原则上与待定位标签RSSI差值越小的参考标签附近虚拟标签的布设密度越大。

图1 VIRE算法和RFFP算法的虚拟标签布设方式

对于虚拟标签的RSSI指纹计算方法,VIRE算法采用线性插值,RFFP算法则采用动态线性插值方法,两者本质上都是基于空间位置关系的线性差值方法。

3 引入RSSI指纹抖动量的改进算法

本文在RFFP算法的基础上,引入RSSI指纹抖动量对选中参考标签的权重进行重新分配,即对于与待定位标签k距离最小的N个参考节点{g1,g2,…,gN},分析其RSSI指纹在一段时间内的抖动特性。对参考标签j,定义其RSSI指纹抖动量为:

其中,σi,j,t表示时刻t参考标签j与阅读器i之间的RSSI抖动量,计算方法如下:

在计算待定位标签k与参考标签j的距离Ek,j,t时,引入参考标签j的RSSI指纹抖动量Δj,t,即将式(1)修改为:

其中,α是常数;r是(-1,1)之间均匀分布的随机数;然后从修正后待定位标签与参考标签的距离{Ek,1,t,Ek,2,t,…,Ek,m,t}中选出最小的N个,记为{Ek,g1,t,Ek,g2,t,…,Ek,gN,t};按照RFFP算法的虚拟标签布设方式,在选中的参考标签{g1,g2,…,gN}覆盖的区域内进行虚拟标签布设;虚拟标签的RSSI指纹则通过利用参考标签{g1,g2,…,gN}的RSSI指纹进行动态线性插值得到,需要说明的是,应用动态线性插值方法前需要对输入的参考标签{g1,g2,…,gN}的RSSI指纹进行随机抖动处理,如下式:

其中,α是与式(6)中α相同的常数;r是(-1,1)之间均匀分布的随机数;j∈{g1,g2,…,gN}。然后从选中的N个真实参考标签{g1,g2,…,gN}和K个虚拟参考标签中,选择与待定位标签的距离最小的M个,利用式(2)和式(3)进行权重计算和加权求和,得到待定位标签的位置。

为了进一步降低由于标签RSSI指纹抖动带来的定位误差,采用固定长度窗口对得到的待定位标签位置进行平滑处理,最终得到的待定位标签的位置为:

从算法复杂度角度分析,LANDMARC算法的时间复杂度为O(umn),VIRE算法时间复杂度为O(umnq2)(其中q为每2个真实参考标签之间的虚拟标签个数);相对于VIRE算法,RFFP算法增加的虚拟标签个数为常数项,因此其时间复杂度为O(umn);本文提出的改进算法在RFFP算法基础上仅增加了RSSI指纹抖动量的计算,时间复杂度为O((u+T)mn)。

4 仿真与测试结果分析

为了对本文提出的改进算法进行测试,本文在实验室环境下搭建了一个RSSI指纹采集系统,其中,RFID标签和阅读器分别采用自主研发的无线传感器网络(Wireless Sensor Networks,WSN)节点和中继器代替,测试场景分为检测器单层布设和双层布设2种方式,如图2和图3所示。

图2 检测器单层布设示意图

图3 检测器双层布设示意图

在单层布设方式中,共布设16个节点,检测器间距为2 m,布设高度为1.5 m;中继器分别置于测试区域的4个顶点及4条边的中点上,布设高度为1.5 m。

在双层布设方式中,共布设18个检测器,每层9个;检测器间距为2 m,布设高度为0.5 m和1.5 m;中继器分别置于测试区域的4个顶点及4条边的中点上,布设高度为1m。

为了保证测试的一致性,RFFP算法和改进算法都采用了固定窗口对待定位标签位置进行平滑处理,固定窗口大小为30。测试中,大约每500 ms记录一次各参考节点和待定位节点与各中继器之间的RSSI值,形成RSSI指纹,连续记录了30 min;利用记录的RSSI指纹对RFFP算法和改进算法进行测试,算法参数α为5;算法仿真实验在一台Thinkpad R400上进行,2.2 GHz双核CPU,2 GB物理内存,仿真软件为Matlab R2012b。

图4和图5分别是单层和双层布设方式的测试结果,图6是2种布设方式、3种算法耗时结果比较。

图4 单层布设方式的测试结果

图5 双层布设方式的测试结果

图6 算法耗时结果对比

从以上测试结果可以看出,在单层布设方式的测试结果中,引入RSSI指纹抖动量的改进算法约94%的定位误差在1.5 m以内,而RFFP算法仅约5%的误差在1.5 m以内;双层布设方式中,引入RSSI指纹抖动量的改进算法约70%的误差在1m以内,而RFFP算法仅约5%的误差在1m以内。从图中定位误差也可计算出,相较于RFFP算法,改进算法的平均定位精度提高了约0.35 m～0.88 m,而相较于LANDMARC算法,改进算法的平均定位精度提高了约0.38 m～0.94 m。从3种算法的耗时结果比较来看,RFFP算法和本文提出的改进算法运算耗时相对于LANDMARC算法平均高出约12%,本文提出的改进算法运算耗时相对于RFFP算法平均高出仅约1%。

5 结束语

本文通过引入RSSI指纹抖动量对虚拟标签定位算法进行改进,在不增加硬件和计算量的前提下,能有效抵消由于环境等因素导致的RSSI指纹随机抖动问题,提高了定位精度。如何进一步分析RSSI指纹抖动量与定位误差之间的关联,是今后的研究方向。

[1] Luo Xiaowei,O’Brien W J,Julien C L.Comparative evaluation of Received Signal-Strength Index(RSSI) Based Indoor Localization Techniques for Construction Jobsites[J].Advanced Engineering Informatics,2011, 25(2):355-363.

[2] Robles J J,Deicke M,Lehnert R.3D Fingerprint-based Localization forWirelessSensorNetworks[C]// Proceedingsofthe7thWorkshoponPositioning NavigationandCommunication.Dresden,Germany: IEEE Press,2010:77-85.

[3] Bahl P,Padmanabhan V N.RADAR:An in Building RF-based UserLocationandTrackingSystem[C]// Proceedings of the19th Annual Joint Conference of the IEEEComputerandCommunicationsSocieties. [S.1.]:IEEE Press,2000:775-784.

[4] Youssef M,Agrawala A.Handling Samples Correlation in the Horus System[C]//Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies.Hong Kong,China:IEEE Press,2004:1023-1031.

[5] Battiti B,NhatTL,VillaniA.Location-aware Computing:A Neural Network Model for Determining Location in Wireless LANs[R].Information Engineering andComputerScience,TechnicalReport:DIT-02-083,2002.

[6] 史伟光.基于射频识别技术的室内定位算法研究[D].天津:天津大学,2011.

[7] Ni L M,Liu Yunhao,Lau Y C,et al.LANDMARC: Indoor Location Sensing Using Active RFID[J]. Wireless Networks,2004,10(6):701-710.

[8] Zhao Yiyang,Liu Yunhao,Ni L M.VIRE:Active RFID-basedLocalizationUsingVirtualReferenceElimination[C]//Proceedings of International Conference on Parallel Processing.Xi’an,China:[s.n.],2007:56.

[9] 李军怀,张果谋,于 蕾,等.面向室内环境的RFID定位方法分析与仿真[J].计算机工程,2012,38(14): 276-279.

[10] 詹 杰,刘宏立,刘述钢,等.基于RSSI的动态权重定位算法研究[J].电子学报,2011,39(1):82-88.

[11] 李 鹏,马 宁,杨拥军,等.基于RFID的边界虚拟参考标签改进算法[J].计算机应用研究,2013,30(1): 158-160.

[12] Alfadhl Y,Chai K K,Chen Yue,et al.Indoor Location Sensing SystemsBasedonRadioChannelFingerprinting[J].China Communications,2011,8(8):1-12.

编辑 索书志

Improved Indoor Localization Algorithm of Introducing RSSI Fingerprints Jittering

DENG Sui,DENG Hanlin,PAN Qiang,LIU Haitao
(Wuxi SensingNet Industrialization Research Institute,Wuxi 214213,China)

In order to improve the accuracy of indoor localization using Received Signal Strength Indicator(RSSI) fingerprints,a new method of introducing the jittering of RSSI fingerprints is proposed,which defines the calculating method of the RSSI fingerprints jittering,and applies it to measure the distance between the reference tags and tags that are being tracked,and computes the RSSI fingerprints of the virtual tags.Test results show that the average localization accuracy is about 0.35 m～0.88 m higher by the improved algorithm than RFFP,and 0.38 m～0.94 m higher than LANDMARC while the time-consuming increases by only1%and12%respectively.

indoor localization;Radio Frequency Identification(RFID);Received Signal Strength Indicator(RSSI); fingerprint;virtual tag;Wireless Sensor Network(WSN)

邓 遂,邓瀚林,潘 强,等.引入RSSI指纹抖动量的室内定位改进算法[J].计算机工程, 2015,41(2):81-84.

英文引用格式:Deng Sui,Deng Hanlin,Pan Qiang,et al.Improved Indoor Localization Algorithm of Introducing RSSI Fingerprints Jittering[J].Computer Engineering,2015,41(2):81-84.

1000-3428(2015)02-0081-04

:A

:TP391

10.3969/j.issn.1000-3428.2015.02.016

江苏省自然科学基金资助项目(BK2011035);江苏省省级现代服务业(软件产业)发展专项引导基金资助重点项目(CYE11C1116)。

邓 遂(1985-),男,博士,主研方向:无线传感器网络,信号处理;邓瀚林、潘 强,博士;刘海涛,研究员、博士生导师。

2014-01-21

:2014-04-28E-mail:dengsui@wsn.cn