基于参考标签的射频识别定位算法研究与应用

王远哲，毛陆虹，刘辉，肖基诰

(1.天津大学 电子信息工程学院，天津 300072；2.香港大学 电机电子工程系，香港)

1 引言

室内定位就是要在室内环境下对目标进行追踪定位，且定位的误差在许可的范围之内。与室外环境不同，室内环境通常更为复杂，各种干扰因素更多，现有的很多定位技术，如GPS(global positioning system)定位，红外定位等，考虑到定位精度、成本、可行性等方面，并不适合于室内定位[1,2]。射频识别定位技术以其非接触、非视距、高灵敏度和低成本的优点，正在成为室内定位系统的优选技术，受到人们越来越多的关注[3～6]。

射频识别定位技术使用的定位依据包括入射信号的强度值、角度值和时间差等。GPS系统就是使用时间差进行定位[7]，但是这种方法成本较高，主要是用在大范围的定位，并不适合于空间狭小环境复杂的室内定位。使用信号角度值进行定位的原理是通过相邻天线接收到的信号的相位差计算信号的入射角度。但是这种方法需要天线阵列，硬件开销较大。基于接收信号的强度值的定位方法需要阅读器提供接收到的射频标签信号的强度值作为定位依据。这种方法具有低功率和低成本的优点，使得它已较多用于实际的定位系统中，如LANDMARC[3]、RADAR[8]、SpotOn[9]等。基于场强值进行定位的现有的算法主要包括解析算法[10]、估值算法[11,12]、基于参考标签的最近邻居算法[3]几大类。

最近邻居定位算法在 LANDMARC的定位系统中被采用。它在环境中按照一定的方式布置一定数目位置已知的参考标签作为定位的基准，通过比较阅读器测得目标标签场强值与阅读器测得参考标签场强值的相对大小来对目标标签进行定位。这种算法有以下几个优点。首先，这种算法采用多标签代替多阅读器，可以降低系统成本。其次，参考标签和目标标签处于同样的环境之中，可以有效地抵消环境因素的影响。第三，这种算法对于非视距的定位效果较好。

但是，LANDMARC系统提供的精度有限。LANDMARC系统使用的阅读器能够提供信号强度的8个等级，而本文中使用的阅读器能够提供256个等级，硬件条件的升级给优化算法提供了可能。同时，由于RFID标签读取不稳定的影响，经常会出现某些阅读器读取某些标签的场强值失败或者出错的情况。由于一个参考标签要同时被几个阅读器读取，而只要有其中一个阅读器的读取失败就会对这个参考标签参与定位造成很大影响，导致很多参考标签丧失了参考价值。另外，由于各个阅读器的增益不同或者离目标标签的距离不同，造成在目标标签处的各向异性，即各个方向上同样的距离反映出来的场强差不同，影响了最近邻标签的选取和权值的设定。在这些恶劣的情况下，现有的最近邻居算法定位精度不高，最大误差比较大。为此，提出了动态k值设定的方法，参考标签可信度的概念，最近邻标签偏差校正算法并采用了目标标签历史轨迹算法。

基于Intel的R1000射频识别开发平台，用多天线的时分复用代替多阅读器，搭建了一个定位系统，并且开发了相应的界面软件。通过实测，改进后定位算法提高了定位精度和恶劣环境下的适应能力。

2 最近邻居定位算法介绍[3,13,14]

下面简要介绍最近邻算法的具体实现。阅读器和标签的排列方式如图1所示。现假设共有m个阅读器和n个参考标签以及u个目标标签。m个阅读器分别读出n个参考标签和u个目标标签发送给阅读器的信号场强值，在LANDMARC系统中此场强值是1～8总共8个等级。把上述场强值写成向量的形式，记目标标签的场强值向量为-→=(T1,T2,…,Tm)，其中T代表第j个阅读器读到目标---标-→签的场强值；参考标签的场强值向量为Rj(i)=(R1(i),R2(i) ,…,Rm(i ))，其中 Rj(i)代表第j个阅读器读到参考标签i的场强值。为了判断参考标签与目标标签的近邻程度，对于每个目标标签p，p∈[1,u]，定义表征第i个参考标签与目标标签的距离大小，Ei越小表示距离越近，i∈[1,n]。

通过比较Ei值的大小，选出k个离目标标签最近的参考标签称为最近邻标签，其标签序号组成集合Κ。其中k值的大小可以根据不同的应用环境人为设定。定义这k个最近邻标签的权值为

这样，目标标签的位置可以由式(2)得出

LANDMARC系统使用16个参考标签，4个阅读器（阅读器可以得到信号强度的 8个等级值），参考标签之间距离约为 1～2m。在这种情况下，得到的定位误差最大约为2m，平均误差约为1m。

图1 定位系统标签摆放示意图

3 参考标签算法不同参数设定对于定位精度的影响

3.1 参考标签分布和最近邻数目 k值的设定对于定位精度的影响

目标标签位置的确定是根据一定数目的（k个）参考标签的位置加权得到的，故而参考标签的排列方式和最近邻数目 k值的设定会对定位的结果产生极大的影响。在实际的应用系统中，根据具体的定位需要，参考标签的分布和k值的设定可能大不相同。比如在空旷的环境中对物体进行定位，一般采取网格式的参考标签排列方法。在生产流水线或者运输路线中对于货物进行定位，货物一般来说不会脱离流水线或者道路，故而只需要进行一维的定位，参考标签一般沿着流水线或者道路线形排列，而k值一般取2（或者 3）。在仓库中对货物进行定位，货物一般会位于某一个货架上，故可以在每一个货架的四周布置 4个参考标签，k值设置为4，就可以通过定位算法找到货物所在的具体货架，如图2所示。

图2 仓库内参考标签摆放示意图

3.2 权值定义方法对于定位精度的影响

最近邻标签权值的确定有很多种方法，但是必须满足2个基本的条件：1) 离目标标签越近的参考标签（即E值越小），权值W必须越大。即W(E)必须是单调的减函数；2) 权值之和必须为1，即 W1+W2+…Wk=1。（注W的下标对第2节中w的下标进行了重排。）除了最近邻居算法中的二阶权值的设定方法，还有一阶权值和对数权值的设定方法，如下所示。

为了考察不同权值设定方法对结果的影响，定义单一标签依赖程度 ξ=(Wi)max，表征定位结果与距目标标签最近的一个参考标签的接近程度。ξ越大代表距目标最近的标签的权重越大，定位结果也就越接近这个标签。

下面用一个具体的例子分析3种权值设定方法的单一标签依赖程度。假设K=5，5个最近邻标签的E值分别为其中x＜40，故剩下的4个标签E＞40。在x的不同取值下分别使用3种权值设定方法计算W值，得到3个不同的ξ，如图3所示。由图3可见，二阶权值设定方法的单一标签依赖程度最高，一阶权值次之，对数权值最低。在实际应用中要根据不同的环境选择不同的方法。如果信号强度随着距离的增加衰减严重的话，一般采用单一标签依赖程度低的权值设定方法，否则目标会完全定位到最近的一个参考标签的位置；如果信号强度随着距离的增加衰减较小的话，一般可以采用单一标签依赖程度高的权值设定方法，否则目标会完全定位在几个最近邻标签的几何中心。

图3 不同的权值设定方法单一标签依赖程度曲线

4 基于最近邻居提出的新型定位算法

4.1 目标标签历史轨迹算法

该改进来源于文献[14]，由于在实际测试中发现加入该改进对精度有一定作用，故予以采用。为了叙述的完整性，在这里进行了简要的描述。详细内容可以参考文献[14]。

由于目标标签的运动速度有限，在一段很小的时间内目标标签的位置不可能发生很大的变化。因此，可以利用目标标签的历史位置加权估计当前位置，这样做的好处是可以减小随机误差和随机电磁干扰对定位精度的影响。

设要获取当前时刻目标标签的位置。在t0时刻和t0时刻之前与t0接近的s个时刻 t1,t2,t3,…,ts，分别进行测量，每一次的测量均用上面所述的算法得到一个估计值。设当前时刻估计值为(x0,y0)，设第i次历史测量得到的估计值为(xi,yi)，i=1,2,…,s，考虑历史轨迹后得到的估计值为(x,y)。考察残差加权函数[11]：

当Q值取得极小值的时候，可以得到最佳的估计位置(x,y)。为此，上式对x和y分别求偏导数，令偏导数等于0，可以解出(x,y)值如下：

其中wi值如下，表示每个历史位置的权值：

由wi的表达式可见，如果历史位置(xi, yi)与当前位置(x0,y0)之间距离越近，则wi越大，它在估计值中的权重也就越大。实践表明，在进行上述修改之后，算法能够更好地克服随机干扰的影响，准确度和稳定性得到了提高。

4.2 动态k值设定方法

在实际的测量中经常会出现某些参考标签的场强向量有一个或几个分量读不到的情况，如果这些标签正好离目标标签最近，就可能导致目标标签最近邻标签选择的极大偏差，从而导致定位结果偏离。例如在网格形的参考标签排列方式中，如果目标标签周围的4个标签同侧2个有场强没有读到，则最近邻标签很可能选成目标标签另一侧的网格4角的4个标签，导致定位结果误差很大。为了避免这种状况发生，可以增大k值的设定，使更多的最近邻标签参与到目标标签定位的加权中去，以减小定位误差。

在定位程序的初始化时，可以先给k设一个初始值k0。在硬件操控程序中，对于读不到的场强值分量，可以将其人为的设定成一个固定的场强值（一般可以设成一个负的大值）。在定位程序中，检测出现了人为设定的场强值的标签的个数，即场强向量中有某一或几个分量没读到的标签的个数。如果检测到c个，则修正k值为 k=k0+c 。

4.3 参考标签可信度的概念

在实际测量过程中发现，在阅读器读取每个标签的场强时，总会出现个别场强值出错（过大或过小），或者甚至读不到的情况（读不到时一般由程序设置为负的一个大值）。而只要有一个参考标签的场强值偏离特别大，而偏离值恰好与目标标签场强值接近的话，这个标签就会被选为最近邻标签从而使定位出现极大的偏差。为了防止这种误差，定义了参考标签的可信度的概念。一般来说，一个参考标签在某个阅读器上的场强值会在它周围的4标签在这个阅读器上场强值之间。假设共有m个阅读器，则某个参考标签在各个阅读器上会有m个场强值，它上下左右4个标签在各个阅读器上也各有m个值。设x(j)为某个参考标签在第j个阅读器上的场强值，min(j)为在第j个阅读器上此标签上下左右4个标签场强值的最小值，max(j)为最大值(j=1,2,…,m）。设使 x(j)∈[min(j),max(j)]的j值共有M个。现分段定义可信度Y如下：

Y在0到1之间取值，越大表示可信度越高。如果对于任意 j有 min(j)＜x(j)＜max(j)则 Y值取 1。在选择最近邻标签时，通过比较选择 的值最小的k个标签。同时最近邻标签的权值修正为

在实际的应用中，由于各种原因可能导致某些参考标签失效，或者位置偏离了设定的位置（尤其是在野外），或者读取时失败或者出错的情况。进行这种改进之后，能有效地防止个别参考标签读取出错对于结果的影响。

4.4 最近邻标签偏差的自校正

阅读器读到的标签的场强值随距离的变化关系并不是线性的，而是一条类似于负指数的曲线。在距离近的时候，场强值随距离的变化比较快（场强对距离导数的绝对值大）；在距离远的时候，场强值随距离的变化比较慢（场强对距离导数的绝对值小）。这样，如果目标标签的位置离某一个阅读器较近而离其他的阅读器较远时，近处的阅读器读到的标签场强值变化陡峭，导致这个阅读器的方向上的距离差L对于E值的贡献大于其他3个方向上同样的距离差L对于E值的贡献。这样会导致最近邻标签选取的偏差和权值的偏差，对定位结果造成影响。或者由于各个方向上阅读器的增益不同，导致各个方向上同样距离读到的场强值不同，也会导致各向异性，对定位结果造成影响。

为了解决这种各向异性导致的定位偏差，可以用最近邻标签的定位偏差作为校正。具体操作如下。首先采用 4.1节中的方法选择出 k个最近邻标签，然后分别把这k个参考标签作为目标标签，把剩下的n-1个参考标签作为参考标签，使用 4.1节中的方法进行计算，得到每一个最近邻参考标签的估计位置，记为(xi′,yi′)，i=1,2,…,k。然后把这k个最近邻标签的估计位置和它们的实际位置作比较，得到修正值：

最后使用这个修正值对目标标签的估计位置进行校正，得到：

4.5 算法的最终流程

综合以上几点改进，算法的最终流程如图4所示。

下面是对算法流程的详细说明。

1) 设置各个参数的值，如阅读器数目m，参考标签数目n，最近邻标签数目k，历史值读取次数s；

2) 各个阅读器读取各个标签的场强值；

3) 检测2中读到的场强值中设定值的数量（即读取失败的场强值的数量），修正k值；

4) 计算各个参考标签的E值；

5) 计算各个参考标签的可信度Y；

6) 根据E值和Y值选择k个最近邻标签；

7) 计算各个最近邻标签的权值；

8) 最近邻标签位置加权得到估计值；

9) 以每个最近邻标签当做目标标签，其他n-1个参考标签作为参考标签，重复4)～8)的步骤，得到各个最近邻标签位置估计值，并计算其偏差；

10) 用偏差值对目标标签估计值进行校正，得到新的估计值；

11) 重复2)～10)的步骤s+1次，最后一次的估计值为当前值，前s次的估计值为历史值；

12) 计算各个历史位置的权值；

13) 加权得到最后的目标标签位置估计值。

5 硬件系统和实际测试结果

基于Intel的R1000射频识别开发平台，搭建了定位的硬件系统。硬件系统的主要构件包括Intel R1000射频识别开发平台、PC机、远距离阅读器天线、XCTF-8030a型无源RFID标签等。该系统可以读出0～255共256个等级的信号强度值（远大于LANDMARC系统的8个等级[3]），使用3对天线的分时复用代替多阅读器，用PC机作为主机。还根据上面提出的算法开发了界面软件，搭建了软硬件协同的定位系统。软件的界面如图5所示。

图5 定位界面软件

分别在空旷的大厅和开放实验室内搭建了定位系统，参考标签按照界面上的排列方式摆放，网格的边长为0.7m。定义测量误差[3]为其中(x,y)是目标标签的估计，(x˜,y˜)表示目标标签的实际位置。使用统计学概率分布函数的方法，e为实际测量中的定位误差（单位为 m），L为概率分布函数的横坐标（单位也是m），定义测量误差e小于横坐标 L的测量结果出现的次数占总测量次数的百分比为P(e＜L)，如P(e＜0.5)即为所有测量误差结果中，小于0.5m的e出现的次数占总测量次数的百分比。在连续10h内进行了大量的测量，根据测量结果绘制出 P(e＜L)的曲线。

为了研究各种参数的设置对于定位精度的影响，使用本文提出的算法，在其他条件相同的情况下，分别改变k0值设定和权值设定方法，对结果进行分析。在空旷大厅中，采用本文提出的算法，权值设定为二阶权值，分别令k0等于3、4、5进行实验，得到的结果如图6所示。可见k0=4时定位效果最好，k0=5次之，k0=3较差。

图6 不同k0值的设定对于定位结果的影响

图7 不同的权值设定方法对于定位结果的影响

在空旷大厅中，采用本文提出的算法，k0设置为 4，分别采用一阶、二阶和对数的权值设定方法进行实验，得到的结果如图7所示。可见二阶权值设定方法精度最好，一阶权值在误差较小的时候定位精度高于二阶权值，但是当环境恶劣时定位精度下降严重，最大定位误差大于一阶权值。对数权值定位精度较差。在最理想的情况下（k0设置为4，权值取二阶权值），分别在开放实验室和空旷大厅内进行实验，结果分别用原有的最近邻居算法和本文提出的改进后的算法进行计算。其中原有的最近邻居定位算法的测量也是在上面提出的 256等级的硬件系统上进行的，因此排除了硬件不同的影响，原算法和改进算法得到的不同结果均是由于算法改进而非硬件升级造成的。得到的结果如图8和图9所示。由图可见，在同样的256等级的硬件平台上，采用新提出的改进算法比使用现有的最近邻居算法定位精度明显提高。不论是在空旷大厅还是在开放实验室，均可看出2条曲线在L值较小的时候拟合较好，在L值比较大时有明显分离。这表明在比较理想的测试结果中，2种算法定位结果的偏差不大。在测试结果情况比较恶劣的情况下，本文提出的算法的精确度显著高于最近邻居算法，说明本文提出的算法在恶劣环境条件下会显示出更精确与稳定的定位结果。

图8 空旷大厅内定位误差分布曲线

图9 开放实验室内定位误差分布曲线

经过计算，在同样的256等级的硬件平台上，在空旷大厅内，使用最近邻居算法定位的平均误差是0.404 6m，最大误差是0.72m；使用新型改进算法定位的平均误差是0.331 0m，最大误差是0.60m。在开放实验室内，使用最近邻居算法定位的平均误差是0.441 6m，最大误差是0.81m；使用新型算法平均误差是0.379 2m，最大误差是0.69m。

6 结束语

本文基于最近邻居定位算法，提出了新型的改进算法。基于R1000射频识别开发平台，使用多天线分时复用代替多阅读器搭建了定位的硬件系统，并且开发了定位的软件界面。本文的测量都是在人员走动、物品摆放、电磁干扰等情况都未加限制的情况下进行的，贴近实际的应用环境。通过实际测量，本文提出的改进算法在恶劣环境下的适应能力和稳定度显著提高，定位的最大误差减小，且平均精度比最近邻居算法有了20%左右的提高。

[1] YAMASAKI R,OGINO A,TAMAKI T.TDOA: location system for IEEE 802.11b WLAN[A].Wireless Communications and Networking Conference,2005 IEEE[C].New Orleans,LA,USA,2005.2338-2343.

[2] HEADLEY W,DASUVA C,BUEHRER R M.Indoor location positioning of non-active objects using ultra-wideband radios[A].Radio and Wireless Symposium,2007 IEEE[C].Long Beach,CA,USA,2007.105-108.

[3] NI L,LIU Y,LAU Y,PATIL A.LANDMARC: indoor location sensing using active RFID[A].Proceedings of the First IEEE International Conference on Pervasive Computing and Communications(Per-Com2003)[C].Dallas,Texas,USA,March 2003.407-415.

[4] SHIRAISHI T,KOMURO N,UEDA H.Indoor location estimation technique using UHF band RFID[A].Information Networking,2008 International Conference on[C].Busan,Korea,2008.1-5.

[5] SHIH S,HSIEH K,CHEN P.An improvement approach of indoor location sensing using active RFID[A].Innovative Computing,Information and Control,2006 First International Conference on[C].Beijing,China,2006.453-456.

[6] DAI H,SU D.Indoor location system using RFID and ultrasonic sensors[A].Personal,Indoor and Mobile Radio Communications,2006 IEEE 17th International Symposium on[C].Kunming,China,2006.1179-1181.

[7] GERTEN G.Protecting the global positioning system[J].Aerospace and Electronic Systems Magazine,IEEE,2005,20(11):3-8.

[8] BAHL P,PADMANABHAN V.RADAR: an in-building rf-based user location and tracking system[A].Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies,Proceedings IEEE[C].TelAviv,Israel,2000.775-784.

[9] HIGHTOWER J,WANT R,BORRIELLO G.SpotON: An Indoor 3D Location Sensing Technology Based on RF Signal Strength[R].Seattle,WA: UW CSE,2000.

[10] KRISHNAKUMAR A,KRISHNAN P.The theory and practice of signal strength-based location estimation[A].Collaborative Computing:Networking,Applications and Worksharing,2005 International Conference on[C].San Jose,CA,USA,2005.10-19.

[11] NI W,SHEN G,LENG X,GUI L.An indoor location algorithm based on taylor series expansion and maximum likelihood estimation[A].Personal,Indoor and Mobile Radio Communications,2006 IEEE 17th International Symposium on[C].Helsinki,2006.1-4.

[12] 熊瑾煜,王巍,朱中梁.基于泰勒级数展开的蜂窝 TDOA 定位算法[J].通信学报,2005,25(4):144-150.XIONG J,WANG W,ZHU Z.A new TDOA algorithm based-on taylor series expansion in cellular networks[J].Journal on Communications,2005,25(4): 144-150.

[13] BAHL P,PADMANABHAN V,BALACHANDRAN A.Enhancements to the RADAR User Location and Tracking System[R].Microsoft Research Technical Report,2009.

[14] 孙瑜,范平志.射频识别技术及其在室内定位中的应用[J].计算机应用,2005，(5):1205- 1208.SUN Y,FAN Z P.RFID technology and its application in indoor positioning[J].Journal of Computer Applications,2005,(5):1205- 1208.