石雪军，纪志成

（江南大学物联网工程学院，江苏无锡214122）

基于改进粒子滤波的射频识别室内跟踪算法

石雪军，纪志成

（江南大学物联网工程学院，江苏无锡214122）

针对复杂室内环境下移动目标难以跟踪和粒子滤波容易丧失粒子多样性的问题，提出一种射频识别室内跟踪算法。将读写器接收到的信号强度指示样本值直接作为观测量建立非线性状态空间模型，给出一种带有马尔科夫链蒙特卡洛（MCMC）移动步骤的改进部分系统重采样算法，采用度量函数实现粒子集分类并进行重采样处理加入MCMC移动步骤，增加粒子多样性。应用该滤波算法对非线性单变量静态模型和上述非线性跟踪模型进行仿真，并与其他重采样滤波算法进行比较，实验结果表明，该滤波算法的滤波性能更好，跟踪精度更佳。

射频识别；室内跟踪；粒子滤波；马尔科夫链蒙特卡洛；部分系统重采样；度量函数

1 概述

近年来，随着物联网技术的蓬勃发展，基于位置信息的服务被普遍认为是一项不可或缺的关键技术，这些位置服务需要对复杂室内环境，如大型超市、地下停车场等进行精确定位；人们对室内移动目标位置的跟踪需求也与日俱增，矿井、仓库等都需要准确的目标跟踪，以实现用户对库存物资和可用空间的高效管理，室内无线跟踪技术正是基于此原因而出现并逐渐成为研究热点。有效的定位技术是位置跟踪服务的基础，目前常见的室内定位技术主要有超声波、蓝牙等，但室内环境中存在的多径效应［1］、非视距［2］等因素将会严重影响室内目标的定位精度。

射频识别（Radio Frequency Identification，RFID）是一种利用射频信号通过空间耦合实现非接触式双向通信并通过所传递的信息达到自动识别和定位目的的技术，具有极强的抗干扰能力和穿透性能；存储在标签内的数据可以进行加密保护，数据记忆容量大，在跟踪定位过程中可以提供丰富的信息，因此，在室内位置服务中，RFID具有很大的优势［3］。目前定位算法分为测距和非测距2种，其中测距定位需要周围节点提供距离或方位信息，如信号到达时间（Time of Arrival，TOA）、信号到达角（Angle of Arrival，AOA）和接收信号强度指示（Received Signal Strength Indication，RSSI）等，和非测距如近似三角形内点测试法、质心算法相比，这类算法对硬件要求高、能耗大，但具有较好的跟踪性能。由于RSSI定位方法是利用已有的无线传感网络设备和移动终端完成定位，无需额外的网络消耗和硬件支持，因此对基于RFID的位置服务，该方法十分适用［4］。

跟踪移动目标的位置信息时，为了使系统具有实时性，一般要在较短时间内估算出移动目标当前的位置，虽然RFID技术读取数据方便、识别速度快，但在进行实时跟踪时，阅读器获取的射频信号强度样本较少，此时直接计算移动目标位置得到的估算值方差较大，严重影响了定位精度。

本文通过研究粒子滤波，结合室内无线信道的特点对室内运动目标进行跟踪，针对粒子退化［5］和贫化［6］现象，提出一种改进的部分系统重采样粒子滤波算法。

2 问题描述

2.1 RSSI测距原理

在基于RSSI测距技术中，首先需要获得RFID标签的信号发射功率和阅读器接收功率，将两者差值作为无线射频信号在传输过程中的能量损耗值，根据对数分布传播损耗经验模型［7］将其转化为空间距离，当给定距离为d时，所有路径损耗的平均值为：

其中，X是一个以dBm为单位，平均值为0的高斯随机变量，反映了当距离一定时，接收能量的变化。因此，RFID阅读器的接收功率为：

其中，Pr（d）为阅读器接收信号强度；Gt为RFID标签天线增益；Pt为发射装置发射功率，单位均为dBm。

在式（1）～式（3）中，路径损耗系数n、发射功率Pt和天线增益Gt均已知，阅读器接收功率Pr（d）也易测量，从而可以计算出标签和阅读器间的距离d，再根据三边测量算法［8］就可以推算出移动目标的位置。

2.2 RFID室内跟踪系统模型

考虑一般的室内移动目标跟踪问题，采用有源电子标签作为被跟踪目标，阅读器作为RFID信号检测源，如图1所示，阅读器采用等边三角形［9］网格布局，即标签在任何位置都能被至少3个阅读器同时识别。

图1 RFID阅读器网格分布

假设带有RFID标签的移动目标在二维平面上运动，跟踪模型中的状态方程和观测方程可表示如下：

其中，向量xk=［xk，vxk，yk，vyk］T为k时刻运动目标的状态矢量；（xk，yk）和（vxk，vyk）分别表示k时刻的位置坐标和x，y轴方向上的速度分量；εk为相应的系统噪声；yk=［s1，s2，…，sn］表示k时刻的观测矢量si（i=1，2，…，n）表示第i个RFID阅读器接收到的信号强度值；nk为观测噪声。

3 改进的粒子滤波跟踪算法

3.1 标准粒子滤波

粒子滤波（Particle Filtering，PF）［10］是一种基于蒙特卡洛模拟仿真的递推贝叶斯估计方法，适用于任何状态空间模型，能有效地解决非线性、非高斯噪声环境下的状态估计问题，算法基本步骤如下［11］：

（1）粒子初始化

从先验概率密度函数p（x0）中产生粒子样本集｛xi0｝Nsi=1，令k=0，所有粒子权值均为1/Ns。

（2）预测

令k=k+1，在未得到k时刻的观测值时，由状态转移概率密度p（xk|xik-1）从粒子集｛xik｝Nsi=1中抽取Ns个新粒子，即通过产生噪声来得到新粒子。

（3）更新

利用当前测量值yk对先验状态估计p（xk|y1：k-1）进行修正，得到当前时刻的后验概率分布p（xk|y1：k），每个新粒子的权值可由式（6）和式（7）进行计算。

因观测模型具有马尔科夫性［12］，滤波时历史状态和观测值均无需保存，所以后验概率分布近似为：

（4）重采样

在k时刻采样得到新粒子并更新对应的权值后后验概率密度函数如式（8）所示，重采样就是在该分布中根据的原则重新采样Ns次得到新粒子集，且新粒子的权值均为1/Ns。

（5）状态估计

由更新阶段可知后验概率分布可近似为式（8）的形式，则状态向量的估计值为：

由式（8）和式（9）得状态估计：

令k=k+1，返回步骤（2）。

3.2 改进的部分系统重采样算法

粒子滤波在非线性和非高斯系统中表现出来的优越性决定了其应用范围十分广泛［13-14］，但其本身存在一个严重的缺陷，即粒子退化。重采样是解决粒子退化的主要方法，然而传统的重采样算法都是基于分层采样方法的，如多项式重采样、残差重采样、系统重采样等［15］，其中系统重采样就是通过简单地比较粒子权重和均匀分布的随机数之间的大小，消除权重较小的粒子，繁殖权重较大的粒子，这样会导致一些权重较大的粒子可能会被丢弃，同时一些权值较小的粒子会被保留下来；其次，对权重较大的粒子直接复制而不是产生新粒子，这样很容易出现样本贫化。因此，提出一种改进的部分系统重采样算法，采用一个表征粒子退化程度的度量函数来改进传统的系统重采样算法，与其相似的是，在新的重采样算法中首先生成2个序列：

第1个序列为粒子权值累积分布函数，记为｛Ci，i=1，2，…，Ns｝，其公式如下所示：

第2个序列为权值参考函数，记为｛rj，j=2，3，…，Ns｝，其公式如下所示：

其中，r1为［0～1/Ns］之间均匀分布的随机数。

图2形象地说明了2个序列之间的关系。其中，圆形粒子属于集合1；方形粒子属于集合2；三角形粒子属于集合3。竖线和横线分别表示序列｛Ci｝和｛rj｝，通过比较序列｛Ci｝和｛rj｝，产生用于表征粒子退化程度的测量函数M（i），函数M（i）伪代码如下所示：

图2 粒子权值分析图

测量函数M（i）包含了粒子权重信息，可以将其认为是粒子权重的非线性变换。当粒子权重增加时，M（i）的数值会变大，然而当粒子权重减小时，M（i）的数值会变小。根据粒子权重的大小，测量函数M（i）的值为0、1或者大于1的数，i=1，2，…，Ns。

因此，新重采样算法不是简单地通过对比序列｛Ci｝和｛rj｝来复制或者丢弃粒子，而是采用测量函数M（i）将粒子分类并进行相应处理。根据M（i）的数值可以将粒子分为3个集合：

（1）集合1：M（i）=0表示当前粒子的权值很小，和在它们之前的第1个粒子位于同一区间内，这些粒子被直接丢弃。

（2）集合2：M（i）=1表示当前粒子的权值大小中等，和在它们之前的第1个粒子不同，该粒子位于下一个区间内。将这些粒子跟它们前面第1个测量函数值为非0的粒子相比，如图2所示，权值较大的粒子被保留而权值较小的粒子被淘汰，即：

其中，M（j）≠0 and j＜i。

（3）集合3：M（i）＞1表示当前粒子的权值比较大，其所在的区间与它们前面的粒子所在的区间不相邻，和集合1、集合2中的粒子相比，这些粒子更加靠近真实值。最简单的方法就是直接复制这些权值较大的粒子，但是这种方法可能会导致粒子贫化；如果将其作为母粒子用于产生新粒子又会减缓收敛速度。为了解决这种问题，提出使用一个门限值Wth将集合3中的粒子分为集合3a和集合3b 2个子集，把权值足够大的粒子归入集合3a，权值次大的粒子存入集合3b。在图2中，较大的三角形粒子属于集合3a，另一个三角形粒子属于集合3b。

保留集合3a中的粒子并按以下方式进行复制：

其中，M（i）表示粒子复制的次数，各粒子相应的权值在复制过程中保持不变。

集合3b中的粒子被作为母粒子用于产生新的子粒子，当M（i）是基数时则新粒子的产生方式如式（15）所示：

相反，如果M（i）是偶数，那么新粒子产生方式如式（16）所示：

其中，m=M（i）；σ为误差，表示新生成的子粒子之间的密集程度。新粒子分布在母粒子的两侧，它们对应的权值为：

N个重采样粒子和其对应的权值可由上述方法获得，但是可能会出现某些粒子没有产生子粒子而有些粒子会产生大量的后代，这样就丧失了粒子的多样性，影响滤波器的性能，为此加入一个MCMC移动步骤［16］来增加粒子的多样性，步骤如下：

Step1 从建议分布函数p（xk|xik-1）中采样生成备用粒子，即：

Step2 产生一个（0，1）范围内服从均匀分布的随机数作为参考接收系数vi，则：

Step3 按照式（20）计算真实接收系数，即：

Step4 如果ρi≤vi，则按以下方式接收该移动步骤：

否则，拒绝该移动步骤，即：

Step5 归一化权值，获得新粒子：

为了避免繁琐的离线测量过程，本文采用对数正态分布模型来描述信号接收强度，选择状态转移概率密度分布作为建议分布，如果将k-1时刻的粒子记为，则k时刻的粒子可由式（5）得到。粒子是对标签的模拟，每个粒子都代表了移动标签可能的位置，此时粒子权值更新公式为：

4 仿真结果与分析

实验1 改进算法与系统重采样算法性能比较

为了验证改进部分系统重采样算法的有效性，考虑文献［6］中的非线性单变量静态模型：

其中，系统噪声wk和观测噪声vk为均值为0、方差分别为Qk=10和Rk=1的高斯噪声，即wk～N（0，Qk），vk～N（0，Rk），状态初值x0=0，仿真步数设为50。

图3是随时间变化，改进部分系统重采样和统系统重采样算法的状态估计与真实的运动轨迹之间的比较曲线。

图3 状态估计曲线

图4 给出了三者之间状态估计的误差标准差曲线，从中可以看出，本文提出的重采样算法精度较传统重采样算法有所改善，这可解释为系统重采样算法是完全重采样，导致大量的低权值潜力粒子消失，有损滤波精度，而本文提出的部分系统重采样算法很好地避免了这一问题。

图4 状态估计的误差标准差曲线

实验2 不同滤波器的室内目标跟踪性能分析

通过M atlab对本文提出的改进粒子滤波RFID室内跟踪算法进行仿真实验。参数设置如下：参考距离d0=1 m，环境系数n=2，目标的初始状态X0=［0，1，0，1］T，假定系统噪声和观测噪声的协方差分别为Q=diag（［0.01，0.01］）和R=2，误差σ= 0.25，标准差σb=1，采样时间T=1 s，粒子数N= 100，门限值Nth=0.75Ns，Wth为最大粒子权值，共进行10次蒙特卡洛实验。

下面分别给出系统重采样粒子滤波、自适应部分系统重采样粒子滤波［17］和本文提出的改进部分系统重采样粒子滤波移动目标的跟踪性能比较。

图5和图6分别显示了移动目标的位置和速度估计误差，在100个采样周期内，改进的部分系统重采样滤波算法、系统重采样滤波算法和自适应部分系统重采样滤波算法的位置和速度估计误差分别为0.377 1 m，3.333 8 m，1.528 8 m和0.341 4 m/s，1.945 2 m/s和0.879 5 m/s。

图5 室内移动目标位置误差

从图5和图6中可以看出，本文提出的改进部分系统重采样粒子滤波算法的跟踪精度相对最好，传统重采样滤波器性能最差。这是因为传统系统重采样滤波算法可能会丢弃一些权重较大的粒子，与此同时权值较小的一些粒子会被保留下来；它只是简单地对权重较大的粒子直接进行复制而不是产生新粒子，很容易使粒子失去多样性；文献［17］中的滤波器对粒子进行部分重采样处理，有助于缓解粒子贫化问题，但效果有限，而本文提出的改进滤波在对粒子进行部分重采样的基础上加入了MCMC移动步骤，提高了粒子细化能力，增加了粒子的多样性，有效改善了RFID室内移动目标的跟踪性能。

表1给出了100个采样周期内，3种滤波算法的位置和速度估计误差的统计结果。和其他2种滤波器相比，改进的部分系统重采样滤波算法的跟踪性能相对最好。

表1 3种滤波器的跟踪性能

表2和表3分别从定性和定量的角度分析了3种滤波器的时间复杂度和空间复杂度。U表示生成的随机数，n表示第几次循环，k表示粒子被分解的次数，i1：Ns表示各粒子最终被分解的个数。Nh1和Nh2分别表示2种算法中需要重采样的粒子数，Sh1表示部分需要重采样的粒子的权值和，wl和wh分别表示权值下限和上限值。

表2 3种滤波器的运算性能分析

表3 3种滤波器的运行时间s

由表2和表3的分析不难看出，文献［17］中的滤波算法和本文提出的重采样滤波算法均比系统重采样滤波算法运行时间短，这是因为它们在重采样阶段只需要部分粒子参加重采样过程，这不仅缓解了粒子贫化问题而且降低了计算执行时间；但本文提出的改进滤波算法相比文献［17］中的算法运行时间稍长而且空间复杂度最高，这是因为本文算法对随机数的计算较为复杂并且加入了马尔科夫链蒙特卡洛移动，需要更复杂的步骤。改进的部分系统重采样算法复杂度反而增加了。

5 结束语

本文对粒子滤波技术进行详细研究，结合RFID室内定位技术，提出一种改进的粒子滤波RFID室内跟踪算法。该算法将读写器接收到的RSSI样本值直接作为观测量建立非线性空间模型，将带有MCMC移动步骤的部分系统重采样算法应用到RFID室内移动目标定位跟踪过程中。和其他滤波算法相比，该算法克服了重采样后粒子贫化严重的问题，有效改善了粒子滤波性能，取得了较好的目标跟踪精度，为解决复杂室内环境下移动目标难以跟踪的问题，提供了一种有效的解决方案。然而本文算法存在占用存储空间大、运算时间较长的问题，当使用大量粒子滤波时，滤波时效性会变差，如何提高滤波实时性、减少计算量将是今后研究的重点。

［1］ Ahmed B T.Multipath Effect on the WCDMA Uplink Capacity of Highways Cigar-shaped Microcells with Users within Cars and Buses［J］.Wireless Personal Communications，2013，71（3）：1649-1662.

［2］ Tai C S，Tan S Y，Seow C K.A Robust Non-line-of sight Localization System in an Indoor Environment［J］. Electronics Letters，2010，46（8）：593-595.

［3］ 李 程，钱松荣.射频识别动态定位方法［J］.通信学报，2013，34（4）：144-148.

［4］ Zhou Junyi，Shi Jing.RFID Localization Algorithm s and Applications——A Review［J］.Journal of Intelligent Manufacturing，2009，20（6）：695-707.

［5］ Hong Shaohua，Shi Zhiguo，Wang Lin，et al.Adaptive Regularized Particle Filter for Synchronization of Chaotic Colpitts Circuits in an AWGN Channel［J］.Circuits，System s，and Signal Processing，2013，32（2）：825-841.

［6］ 左军毅，张怡哲，梁 彦.自适应不完全重采样粒子滤波器［J］.自动化学报，2012，38（4）：647-652.

［7］ 陈得昌，吴介军，王庆林，等.基于粒子滤波的RFID室内节点定位跟踪研究［J］.信息技术，2011，（8）：77-80.

［8］ 高 雷.基于三边测量的分簇目标跟踪算法［J］.计算机应用，2014，34（6）：1578-1581.

［9］ 朱 剑，赵 海，孙佩刚，等.基于RSSI均值的等边三角形定位算法［J］.东北大学学报：自然科学版，2007，28（8）：1094-1097.

［10］ Zuo Junyi，Jia Yingna，Zhang Wei，et al.Particle Filter with Importance Density Function Generated by Updated System Equation［J］.Journal of Central South University，2013，20（10）：2700-2707.

［11］ 宋越明.基于粒子滤波的跟踪方法研究［D］.郑州：解放军信息工程大学，2010.

［12］ 任子晖，王 坚，高岳林.马尔科夫链的粒子群优化算法全局收敛性分析［J］.控制理论与应用，2011，28（4）：462-466.

［13］ Yan Zhenya，Zheng Baoyu，Xu Li，et al.Collaborative Tracking via Particle Filter in Wireless Sensor Networks［J］.Journal of Electronics，2008，25（3）：311-318.

［14］ Wang Yongli，Qian Jiangbo.Measuring the Uncertainty of RFID Data Based on Particle Filter and Particle Swarm Optimization［J］.Wireless Networks，2012，18（3）：307-318.

［15］ 冯 驰，王 萌，汲清波.粒子滤波器重采样算法的分析与比较［J］.系统仿真学报，2009，21（4）：1101-1105.

［16］ Fan Y，Peters G W，Sisson S A.Automating and Evaluating Reversible Jump MCMC Proposal Distributions［J］. Statistics and Computing，2009，19（4）：409-421.

［17］ 刘文静，于金霞，汤永利.粒子滤波自适应部分系统重采样算法研究［J］.计算机应用研究，2011，28（3）：912-914.

编辑 顾逸斐

Radio Frequency Identification Indoor Tracking Algorithm Based on Improved Particle Filtering

SHI Xuejun，JI Zhicheng
（School of Internet of Things Engineering，Jiangnan University，Wuxi 214122，China）

To address the problem that mobile target is difficult to track in complex indoor environment and the particle diversity is losing after the resampling step，a Radio Frequency Identification（RFID）indoor tracking algorithm is proposed.It treats Received Signal Strength Indication（RSSI）sample values received by readers as observation parameter directly to establish a nonlinear state space model，while a new adaptive partial systematic resampling algorithm with Markov Chain Monte Carlo（MCMC）move step is presented.The new algorithm resamples after classifying the particles with a measure function and the MCMC move step is joined after resampling steps to improve the diversity of particles. Applying this proposed algorithm to simulate the nonlinear single variable static model and nonlinear tracking model mentioned above，and com pared with other resampling algorithms，the results show that the new algorithm has a better filtering performance and tracking accuracy.

Radio Frequency Identification（RFID）；indoor tracking；Particle Filtering（PF）；Markov Chain Monte Carlo（MCMC）；partial systematic resampling；measure function

石雪军，纪志成.基于改进粒子滤波的射频识别室内跟踪算法［J］.计算机工程，2015，41（11）：308-313.

英文引用格式：Shi Xuejun，Ji Zhicheng.Radio Frequency Identification Indoor Tracking Algorithm Based on Improved Particle Filtering［J］.Computer Engineering，2015，41（11）：308-313.

1000-3428（2015）11-0308-06

A

TP301.6

10.3969/j.issn.1000-3428.2015.11.053

国家“863”计划基金资助项目（2013AA 040405）。

石雪军（1989-），男，硕士，主研方向：射频识别，控制理论与控制工程；纪志成，教授、博士、博士生导师。

2014-09-18

2014-11-29 E-m ail：956003055@qq.com