基于粒子群的射频识别定位算法*

2014-09-14温佩芝苏亭婷李丽芳张建军

计算机工程与科学 2014年5期

关键词：阅读器信号强度定位精度

温佩芝，苏亭婷，李丽芳，张建军

(1.桂林电子科技大学计算机科学与工程学院,广西桂林 541004；2.中国化工橡胶桂林有限公司,广西桂林 541004)

基于粒子群的射频识别定位算法*

温佩芝1，苏亭婷1，李丽芳1，张建军2

(1.桂林电子科技大学计算机科学与工程学院,广西桂林 541004；2.中国化工橡胶桂林有限公司,广西桂林 541004)

针对传统室内定位方法定位精度低、开销大等问题，提出一种基于粒子群的射频识别定位算法。首先采用高斯滤波对读取到的信号强度指示RSSI进行预处理，以减少环境因素对信号的干扰，使RSSI值与标签实际位置相符。其次，以网格排列的参考标签作为辅助，通过引入粒子群优化算法，经多次迭代找出最优值，计算出待定位标签的估计坐标，提高定位精度。最后，采用拉格朗日插值法计算虚拟标签的信号强度指示值，使其更接近于真实标签的值。实验表明，该算法可有效提高定位精度和效率，并减少开销。

粒子群算法; 高斯滤波；RFID室内定位； VIRE；拉格朗日插值

1 引言

随着无线移动通信技术的发展及物联网技术在各个行业的应用，室内定位技术备受人们关注。目前主要的室内定位技术有红外线、超声波、基于IEEE 802.11无线定位和射频识别定位等。其中，射频识别(RFID)以其低成本、非接触、非视距且定位精度高等优点，逐步成为室内定位的优选技术。而针对室内环境复杂、多经传播和噪声干扰较大等问题，如何实现精度高、速度快、开销少的定位显得尤为重要。

目前比较典型的RFID室内定位方案主要有3D-ID[1]、SporON[2]、LANDMARC[3]和VIRE方法[4]。3D-ID[1]是由Pinpoint公司提出的使用射频环形时间来测距，其定位精度可达1 m～3 m，但投资成本过大。SporON[2]是一种基于收信场强分析的聚合算法，可实现三维空间定位，但迄今仍没有建成完整的SpotON系统。LANDMARC系统[3]是由Ni L M等提出的一种有源RFID室内定位系统，采用额外的、便宜的RFID标签代替以往算法中大量的使用昂贵的RFID阅读器进行定位，节省了成本，但需要密集的参考标签来辅助定位，增加了室内信号传播的干扰性。VIRE算法[4]由Zhao Yi-yang等人基于LANDMARC算法改进的定位方法，是基于接受信号强度指示RSSI(Received Signal Strength Indicator)进行定位的，该算法引入线性插值技术，通过采用虚拟网格坐标决定法和小概率位置排除法来达到更准确的定位。与上述方法相比，其主要优点首先是引入虚拟参考标签的概念，节省了成本并减少了室内信号传播的干扰；其次，相比于传统的以检测到的RSSI值估计测量距离进行定位，该方法以虚拟标签作为辅助，能有效提高定位精度；最后，该方案较容易实现。但是，VIRE算法中虚拟参考标签采用虚拟网格坐标决定法，导致边界区域的定位误差较高；同时，实际环境中信号强度值与距离是复杂的曲线关系，采用线性插值法来估计虚拟参考标签的信号强度值将导致其估计值与实际值偏差较大，影响最终的定位准确率。针对VIRE算法中存在的问题，目前已有很多学者对其改进[5～7]：文献[5]提出一种自适应的VIRE算法(AVIRE)，可自适应选取合适的门限值；文献[6]采用非线性插值法计算虚拟标签的RSSI值，并用自动获取的动态阈值代替VIRE中的固定阈值；文献[7]提出基于子区域动态二次回归插值的VIRE改进算法(SDQRI)，该方法根据待定位标签的位置在子区域中插入虚拟参考标签，以缩小插入区域，并采用二次回归曲线的插值方法估算虚拟标签的RSSI值，最后利用历史信息矫正待定位标签位置。SDQRI算法相对VIRE可有效提高定位精度，但是该算法只适合于待定位标签只有一个或多个位置较为集中的情况，当有多个位置分散的定位标签时，其高阶定位子区域的选取机制反而会增加算法复杂度和计算量。

针对VIRE算法使用参考标签数量大、边界定位等缺点，本文对其进行改进，运用高斯滤波算法对读取到的信号强度指示RSSI进行平滑处理，减少因环境干扰等因素造成的信号强度值上下波动产生的误差，使其与RFID标签的实际位置相符；同时，提出基于粒子群算法PSO(Particle Swarm Optimization)的RFID定位算法，避免了VIRE算法的边界待定位标签定位误差大的问题，且此算法可调参数少，容易实现；最后，对虚拟参考标签的信号强度指示RSSI的计算采用拉格朗日插值法，使其更接近于真实标签的值。

2 基于粒子群的射频识别定位算法

2.1 预处理

在实际环境中，某一时间段内一个标签在同一个位置可以接收到n个RSSI值，由于非视距和多径的影响，室内射频信号具有较高的噪声污染，导致这些RSSI值具有很大的波动性。理论上，阅读器获取到的标签的RSSI值与两者之间的距离应该满足路径损耗模型[8]，如式(1)、式(2)所示：

(1)

(2)

其中，PL是路径损耗；n是路径损耗指数；d是阅读器与标签之间的距离；d0是指参考距离，一般为1 m；PL(d0)是相距d0时的路径损耗；Xσ是均值为0的高斯随机变量；Pr指发射功率。

RSSI值随距离变化的理论值与受环境噪声干扰的实际值分别如图1所示。

Figure 1 Distance vs. RSSI图1 RSSI值与距离的关系

高斯滤波[9]能较好地处理高斯噪声，为了得到更加精确的RSSI值，采用高斯滤波对获取的RSSI值进行预处理。根据高斯分布函数对RSSI进行处理，则信号强度的密度函数[9]如式(3)所示：

(3)

其中，

根据工程经验，选择0.6作为函数分布值临界点，则有：

0.6≤F(rssi)≤1

(4)

对满足公式(4)范围的RSSI值计算其几何平均值，即得到最后的优化值，即为最终的RSSI值。

2.2 粒子群算法(PSO)

粒子群优化算法PSO最早是由Kennedy J和Eberhart R于1995年提出的一种全局优化算法[10],是一种智能估计IE(Intelligence Estimation)算法,其源于对鸟群群体运动行为的研究。PSO作为一种高效的优化算法，算法简单，易于实现，可调参数少，运行效率高。

2.2.1 粒子群优化算法(PSO)原理

PSO算法的基本思想是在一个D维空间中，随机初始化N个粒子，将每个粒子看作优化问题中的一个可行解，每个粒子都在可行解空间中飞行，且有一个速度决定粒子的飞行方向和距离。然后，粒子追随当前的最优粒子在解空间中进行搜索，经过多次迭代后，得到最优解。在每一次迭代搜索中，粒子主要通过两个极值更新自己：一个是粒子本身搜索到的最优解Pibest；另一个是全部粒子的全局最优解Pgbest。

粒子的位置、速度更新公式如下：

(5)

(6)

(7)

其中,tmax是最大迭代次数，wstart=0.95,wend=0.4。

当到达最大迭代次数T或是其它迭代条件时，得出全局最优解为Pgbest及最优位置Xgbest。

2.2.2 基于粒子群的射频识别定位

文献[12]采用粒子群算法求解无线传感器中节点定位问题，受其启发，将粒子群算法引入RFID定位中，使用粒子群算法计算待定位标签的坐标信息。随机初始化N个粒子，把每一个粒子当成一个虚拟参考标签，通过用VIRE算法中的线性插值法[4]及参考标签的RSSI值，计算每一个粒子的RSSI值。与VIRE算法中采用网格式的固定模式插入虚拟参考标签的方式相比，更具有灵活性，且不具有VIRE算法中边界待定位标签的定位误差大的问题。

假设有K个阅读器，待定位标签u的估计位置坐标为(xu,yu)，第k个阅读器的位置坐标为(xk,yk)，待定位标签和参考标签的RSSI值可由室内路径损耗模型[8]模拟获得。假设第k个阅读器读取的待定位标签的信号强度值为rssik，由插值法计算出第k个阅读器读取第n个粒子的信号强度值为rssikn，定义待定位标签与第n个粒子的欧氏距离为：

(8)

即表示该粒子与待定位标签的距离关系，Ek越小，则该粒子与待定位标签越接近。文献[10]中采用测距距离计算待定位标签坐标，使得待定位坐标的定位误差随测距误差的增加而增加，因此本文提出的PSO算法，以固定位置的参考标签作为辅助，以式(8)中欧氏距离Ek为目标函数，以提高定位精度。本文以欧氏距离Ek与阅读器的总数K的比值即Ek/K表示适应度函数f(x,y)，然后应用PSO算法计算出最佳适应度值fgbest和种群全局最优解为Pgbest，即为u的估计坐标位置。

若已知待定位标签的实际坐标为(x , y)，为了评价算法性能，则采用下式描述定位误差e。

(9)

2.3 改进的虚拟标签坐标计算

VIRE算法中对虚拟参考标签的RSSI值计算采用线性插值的方法，而实际环境中，RSSI值与距离是复杂的曲线关系，如图1所示。文献[11]中的拉格朗日插值法能较好地模拟复杂的非线性曲线，因此采用拉格朗日插值法计算虚拟参考标签的RSSI值将更接近于实际环境中的值，从而减少定位误差。但是，由于非线性插值存在计算量大的缺点，因此提出区域化的拉格朗日插值法计算虚拟参考标签的RSSI值，可在一定程度上减少计算量。

假设有NUM个参考标签，与虚拟标签相距为L的参考标签数量为N，为了减少计算量及提高定位精度，我们选取这N个参考标签计算虚拟标签的RSSI值。L作为可调参数，若L取值过大会造成计算量及误差大，若L取值较小则粒子的RSSI值估算不够精确引起定位误差大，因此选取合理的L值较为重要。采用公式(10)计算虚拟参考标签的信号强度值：

(10)

其中，rssikm表示第k个阅读器读取的第m个虚拟参考标签的信号强度值；rssiki表示第k个阅读器读取的第i个参考标签的信号强度值；d表示第k个阅读器与第m个虚拟参考标签的距离；dkj表示第k个阅读器与第j个参考标签的距离；N是NUM个参考标签中离待定位标签较近的参考标签个数。

为了测试算法的定位性能，分别模拟不同室内空间进行实验，如表1所示，实验环境中四个阅读器与邻接的边界参考标签的距离都为1 m。在实验环境Evn1和Evn2中随机生成八个待定位标签坐标，如表2所示。

Table 1 Experimental environments

图2即为算法对表2中待定位标签的定位结果。

序号6、7、8的待定位标签为边界标签，由图2可见，VIRE算法对边界待定位标签的定位误差明显较大，影响整体的定位效果；SDQRI定位精度虽然有所提高，但其不适于大量标签定位；本文算法能有效提高定位精度，在Evn1(a)实验环境下，上述八个待定位标签的定位误差接近于0，并且随着空间大小及参考标签间距的变化，都具有较好的定位效果。

Table 2 Coordinates of tracking tags

Figure 2 Comparison of positioning error in different conditions图2 定位误差比较

3 本文算法流程

在获取虚拟参考标签的信号强度值以后，我们可以按照本文提出的基于粒子群的定位算法计算出待定位物品的具体坐标。

假设有K个阅读器，N个参考标签，初始化M个粒子(即虚拟参考标签)。采用本文算法计算待定位标签的坐标，算法流程如图3所示。

4 实验评价

4.1 算法参数分析

为了评价本文算法性能，采用C++对100个随机坐标进行多次实验。实验数据根据经典的室

Figure 3 Flow-chart of the proposed approach图3 本文算法流程图

内路径损耗模型仿真得到，采用室内路径损耗模型来模拟信号传播[8]。

图4为本文算法中适应度函数值随迭代次数变化曲线图，为了更明确看出适应度函数值随迭代次数的变化，本图的适应度函数值采用公式(8)中的欧氏距离Ek比上阅读器的总数K，即Ek/K。由图4可知，当迭代次数达到10后，定位误差几乎不再变化，而VIRE算法中需要900个虚拟标签才能达到较好的定位效果，相比之下，本文算法计算量并不大。

Figure 4 Iterations vs. fitness value图4 适应度值随迭代次数的变化

图5为采用拉格朗日插值法计算虚拟标签RSSI值时定位误差随距离L的变换曲线图。

Figure 5 Positioning errors vs. L图5 定位误差随距离L的变化

可见，合理的L取值可减少计算量和提高定位精度。

4.2 实验结果分析

通过对100个随机标签的多次实验，计算得出平均定位误差，将本文算法与VIRE算法[4]、SDQRI算法[7]比较，结果如表3所示。实验结果表明，本文算法可有效提高定位精度、减少参考标签使用量，并且在不同室内实验环境下鲁棒性较强。

Table 3 Comparison of average positioning errors

5 结束语

本文针对目前室内定位效果较好的VIRE算法中存在的不足，提出了一种基于粒子群的RFID室内定位算法。实验结果表明，本文算法能有效克服VIRE的不足，使用相对较少的参考标签实现高效稳定的高精度定位。但是，由于实验条件的限制，本文实验数据是通过室内路径损耗模型来获取，并未在真实环境中验证，如何使本算法能够在真实的不同复杂程度的实际环境中应用，是我们下一步研究的重点。

[1] Werb J, Lanzl C. Designing a positioning system for finding things and people indoors[J]. Journal of IEEE Spectrum, 1998, 35(9):71-78.

[2] Hightower J, Want R, Borriello G. SpotON:An indoor 3D location sensing technology based on RF signal strength[R]. UW CSE 00-02-02. Seattle, WA:University of Washington, 2000.

[3] Ni L M, Liu Yun-hao, Lau Y C, et al. LANDMARC:Indoor location sensing using active RFID[J]. Wireless Networks,2004,10(6):701-710.

[4] Zhao Yi-yang, Liu Yun-hao, Ni L M. VIRE:Active RFID-based localization using virtual reference elimination[C]∥Proc of International Conference on Parallel Processing, 2007:56.

[5] Zhu Feng-juan.Research of indoor positioning algorithm based on the RFID technology[D].Guangzhou:South China University of Technology, 2010.(in Chinese)

[6] Chen Bing. The design of passive RFID location system and improvement of VIRE algorithm[D]. Tianjin:Tianjin University, 2012.(in Chinese)

[7] Shi Wei-guang. Research of indoor localization algorithm based on radio frequency identification technology[D]. Tianjin:Tianjin University, 2012.(in Chinese)

[8] Seidel S Y, Rappaport T S. 914 MHz path loss prediction models for indoor wireless communications in multifloored buildings[J]. IEEE Transactions on Antennas and Propagation,1992,40(2):207-217.

[9] Zhang Jian-wu, Zhang Lu, Ying Ying, et al. Research on distance measurement based on RSSI of ZigBee[J]. Chinese Journal of Sensors and Actuators, 2009, 22(2):285-288.(in Chinese)

[10] Kennedy J, Eberhart R. Particle swarm optimization[C]∥Proc of IEEE International Conference on Neural Networks, 1995:1942-1948.

[11] Mathews J H, Fink K D. Numerical methods using MATLAB[M]. 4th edition. Zhou Lu,Chen Yu, Qian Fang, et al, translation. Beijing:Electronic Industry Press, 2005.(in Chinese)

[12] Chuang P J, Wu Cheng-pei. An effective PSO-based node localization scheme for wireless sensor networks[C]∥Proc of the 9th International Coference on Parallel and Distributed Computing, Applications and Technologies,2008:187-194.

[13] Chen Gui-min, Jia Jian-yuan, Han Qi. Study on the strategy of decreasing inertia weight in particle swarm optimization algorithm[J]. Journal of Xi’an Jiaotong University, 2006,40(1):53-56.(in Chinese)

附中文参考文献：

[5] 朱凤娟. 射频识别(RFID)技术的室内定位算法研究[D]. 广州:华南理工大学, 2010.

[6] 陈冰. 无源RFID 定位系统搭建与VIRE算法优化[D]. 天津:天津大学, 2012.

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

[9] 章坚武,张璐,应瑛,等. 基于ZigBee的RSSI测距研究[J]. 传感技术学报,2009, 22(2):285-288.

[11] Mathews J H, Fink K D. 数值方法(MATLAB版)[M].第四版.周璐,陈渝,钱方，等译. 北京:电子工业出版社,2005.

[13] 陈贵敏,贾建援,韩琪. 粒子群优化算法的惯性权值递减策略研究[J]. 西安交通大学学报,2006,40(1):53-56.

WENPei-zhi,born in 1963,post doctor,professor,her research interests include internet of things, graphic and image processing, and target detection and recognition.

苏亭婷(1988-),女,河南周口人，硕士，研究方向为物联网。E-mail:suting1222@163.com

SUTing-ting,born in 1988,MS,her research interest includes internet of things.

李丽芳(1978-),女,广西恭城人，硕士，高级工程师，研究方向为信息处理。E-mail:lilifang@guet.edu.cn

LILi-fang,born in 1978,MS,senior engineer,her research interest includes information processing.

张建军(1970-),男,辽宁阜新人，高级工程师，研究方向为供应链管理和特种轮胎。E-mail:xmrs1011@sina.com

ZHANGJian-jun,born in 1970,senior engineer,his research interests include supply chain management, and special tyre.

PSO-basedRFIDpositioningalgorithm

WEN Pei-zhi1,SU Ting-ting1,LI Li-fang1,ZHANG Jian-jun2

(1.School of Computer Science and Engineering,Guilin University of Electronic Technology,Guilin 541004；2.China National Chemical Rubber Guilin Corporation Limited,Guilin 541004,China)

In order to solve low positioning accuracy and high cost in traditional positioning methods, the PSO-based RFID positioning approach is proposed. Firstly,aiming at the interference of environmental factors on the signals,Gaussian Smoothing Filter is adopted to preprocess RSSI(

Signal Strength Indicator) values.Secondly,based on grid-style reference tags,PSO algorithm is introduced to estimate the optimal positions of tracking tags by several iterations,thus improving the positioning accuracy.Finally,the RSSI values of virtual reference tags are calculated by Lagrange interpolation,so as to be more close to the values of real tags.Experimental results demonstrate that the proposed approach has excellent accuracy,high efficiency and low cost in indoor positioning.

PSO;Gaussian filtering;RFID indoor positioning;VIRE;Lagrange interpolation

1007-130X(2014)05-0917-06

2012-11-23;

：2013-03-29

广西科技计划资助项目(桂科攻11107006-10)；广西自然科学基金资助项目(桂科自0991240)

TP391.45

：A

10.3969/j.issn.1007-130X.2014.05.022