流水线型局部加权回归RFID室内定位

张金艺， 张晶晶， 李若涵， 徐德政， 徐秦乐

1．上海大学特种光纤与光接入网省部共建教育部重点实验室，上海200072

2．上海大学微电子研究与开发中心，上海200072

3．上海大学教育部新型显示与系统应用重点实验室，上海200072

随着现代计算机技术及无线网络的飞速发展，人们逐步寻求一种可以随时随地提供用户需求的智能型服务，其中人们所处的位置是判断提供何种服务的重要信息之一[1].2012年8月，由Sony、Nokia、Samsung、Qualcomm等20多家厂商联手成立了室内定位联盟（In-Location Alliance），旨在发展高精确度室内定位（high accuracy indoor positioning,HAIP）技术和相关服务，共同推动室内定位的技术发展与应用普及.可见，室内定位已成为大家关注的热点，有望在未来的智能化服务方面衍生出庞大的商业模式与应用.全球定位系统（global positioning system,GPS）、伽利略卫星导航定位等是比较成功的室外定位技术，但受定位时间、定位精度、室内复杂环境等条件的限制，且对室内定位的精度要求较高，故GPS等室外定位系统不能满足室内定位的需求[2].

射频识别技术（radio frequency identif ication,RFID），又称电子标签，是利用射频方式进行非接触式双向通信数据交换，无需识别系统与特定目标之间建立机械或光学接触[3].使用RFID技术进行室内定位具有成本低、技术成熟、定位精度高等优点[4].在非视距（non light of sight,NLOS）条件下，读写器可以对读取范围内的标签进行快速读写，在智能识别领域有着非常好的发展前景.因此，研究高精度、低成本的RFID定位系统具有重要的意义.

根据传统理论模型，RFID读写器在水平平面内的读取范围近似于一个圆形.适当调整读写器的距离及其发射功率后，邻近读写器之间会有部分读取重叠的地方，于是可以通过读写器读取的重叠信息来判断出标签所在的区域范围.

在室内环境下，由于有墙壁、空调、电风扇等一系列物体，无线信号在传播过程中会受到相应物体的影响而发生折射传播、反射传播、阴影传播及衍射传播等，以致产生严重的多径效应.因此，在各位置处接收到的信号有着一定程度的不规则性，迄今为止还没有理想的室内环境下的信号传播模型[5].目前，室内RFID定位算法可分为两大类：基于测距的方式和非基于测距的方式.前者对于硬件要求较高，实现困难，并且受到非视距及多径干扰的影响比较大，在定位精确度上有一定的局限性；后者通常为基于场景的定位，也可称为位置指纹定位.信号的多径传播对环境具有很强的依赖性，因而对于每个位置而言，该位置上的信道的多径结构是唯一的，这样的多径特征可以认为是该位置的指纹.基于场景的定位为不同位置所接收的信号特征参数建立数据库，计算实际接收信号参数与数据库中的参考点信号参数，实现了移动目标的定位[5].常用的基于场景的定位算法有LANDMARK算法[6]和VIRE算法[7].LANDMARK算法采用额外的固定参考标签辅助定位，通过参考标签的信号强度值与待定位标签的信号强度值，采用最近邻距离权重思想，计算出待定位标签的坐标.室内信号会受到多径效应的影响，使得信号强度值有一定程度的不稳定性以及判断出的最近邻标签并非真正的最近邻标签，从而导致定位精度不高.VIRE算法是在LANDMARK算法的基础上通过线性插值的方法增加虚拟参考标签，但信号强度值随距离呈非线性变化，也会引起较大的误差.文献[8]提出了一种基于天线阵列的标签读取方式，在同一个地方放置多根天线，使得到的天线的读取范围接近于一个规整的圆，从而提高了准确率，但大大增加了系统成本.文献[9]提出了一种通过调节RFID读写器的发射功率以及改变读写器的读写范围来提高定位精度的方法.这种方法在定位过程中操作繁琐，并且增加了算法的复杂度.

鉴于此，本文基于RFID技术及场景算法，提出了一种流水线型局部加权回归定位算法.首先分析链路收包率与信号强度之间的关系，并考虑到实时性要求，提出了流水线方式的收包率获取方法.通过分析室内环境下各位置的信号接收情况，提出了流水线型局部加权回归定位算法.在边缘等定位误差相对较高的地方，可采用增加采样点的方法来进一步提高定位精度.经实验验证，本文提出的流水线型局部加权回归定位算法相对于LANDMARK算法，定位精度提高了56.56%，相对于VIRE算法，定位精度提高了36.73%，实现了实时的低成本、高精度室内定位，且在多目标情况下也可以实现实时精确的定位.

1 流水线收包率信息处理

1.1 链路质量研究

在无线通信环境下，通信模式在本质上是广播形式.通信中信道的竞争必定会产生信号之间的相互干扰，干扰信号被称为噪声.当天线与标签之间的距离增大时，接收处接收到的信号逐渐减小，当距离超出天线某个特定的范围时，信噪比（signal to noise,SNR）就无法达到维持可靠通信所需的阈值，说明射频定位系统的定位范围是受限的[10].文献[11]认为：信号接收情况，即链路质量衡量指标大致有收包率（packet reception rate,PRR）、接收信号强度指示值（received signal strength indicator,RSSI）、链路质量指示值（link quality indicator,LQI）3种.本文研究的是PRR和RSSI之间的关系.

1.1.1 RSSI的测距原理

无线信号传输中普遍采用的信号传播损耗模型如下[12]：

式中，P(d)表示距离信号发射处为d时接收端接收到的RSSI值；P(d0)表示距离信号发射处为d0时接收端接收到的RSSI值；d0为参考距离；n为路径损耗指数，一般根据实际环境而定，环境中的障碍物越多，n值越大，也就是接收处接收到的能量随着距离的增加而加速下降;R是一个均值为0、方差为σ2的高斯随机变量，能反映噪声对接收信号的影响程度,其单位为d Bm.

然而，由于室内环境的复杂性，信号在传播过程中会受到多径效应、衰退效应、反射效应、阴影效应等的影响，信号接收值具有不确定性，受外界环境的影响较大.这些影响都会使得以RSSI值作为接收信号的定位系统产生较大的定位误差.

1.1.2 PRR与RSSI的链路质量比较

PRR是指一段时间内接收器成功收到的包数量占发送器已发送包数量的比例，是反映链路质量最直观的指标[12]，其计算公式为

式中，v为发包速率，g为T时间内实际收到包的数目.本试验中读写器发出的信号频率是固定的，读写器相应读到的标签的次数反映了此时标签与读写器天线所在位置的链路情况，即以固定时间内读到的标签次数来表示标签所在位置的收包率情况.

文献[13]指出：在发射功率恒定的情况下，PRR与RSSI存在着较高的线性关系.从PRR和RSSI的定义来看：RSSI反映的是链路瞬时状态的信号强度值，在复杂的室内环境下容易受到多径效应的影响，尤其不稳定，如图1所示.在同一处测量的RSSI值具有较大的不稳定性，如果作为定位信号参数，将使后续的定位结果产生较大的误差；而PRR是一段时间内对接收消息数量的统计值.由图1可知，相对于RSSI而言，PRR的稳定性好，是一个相对稳定的反映链路质量的参数，可以作为定位信号参数，有利于定位算法的精确定位.

图1 RSSI和PRR信息Figure 1 RSSI and PRR

1.2 流水线收包率信息提取

本文提出的流水线型局部加权回归定位算法是以数据链路指标PRR作为参数进行运算的.由于PRR是一个累加量，在统计PRR的时间方面有一定的累计要求；又由于天线的发射信号是等间隔发射的，在固定时间内读到的标签次数可以反映链路的情况.如图2中的（a）所示，假设定位信号参数是通过统计2 s内的读取次数取得的，则信号的表达式如式（3）和（4）所示：

第1次信号为

第2次信号为

式中，n1，n2,···,nm表示读写器1,2,···,m在2 s内所读到的标签次数，即2 s内的收包情况.由式（3）和（4）可知：对于定位信号参数，需2 s才能够得到一组，显然不能很好地满足实时性要求；如果目标在2 s内有大幅度的位置变化，则定位结果不能显示其中的细节位置.

本文采用一种流水线方式的收包率获取方法，很好地满足了定位算法的实时性要求和定位细节要求.流水线方式的收包率是通过对时间段的划分来得到相应时间段的收包率，如图（2）b所示.假设2 s内要求有5组收包率数据，则将时间段以0.4 s进行划分，后一个2 s是以前一个2 s的0.4 s处为起始时间，可得信号的表达式如式（5）和（6）所示：

第1次信号为

第2次信号为

图2 收包率信息Figure 2 Packet reception information

由式（5）和（6）可知：在相同的时间下，信息的采集频率提高了5倍，即定位的实时性提高5倍.相应地在移动目标的轨迹图中，有更多的位置细节数据点，可使得轨迹更精确.

2 RFID天线数据分析

2.1 RFID天线的读取数据分析

RFID天线的读取范围一般与天线的发射功率有关，当发射功率固定时，天线的读取范围也可以固定.在理想模型中，RFID天线在平面内的读取范围是一个圆形.本文将多读写器天线所得的信息进行融合，以判定目标的位置；将读写器天线根据有一定重叠区域的读取范围进行适当的摆放，则读写器天线读取范围的理想情况如图3中的（a）所示.然而，室内环境很复杂，存在多径效应、反射、折射现象，且受到噪声等因素的影响，使读写器天线的读取范围存在一定程度的不规则性.实际情况如图3中的（b）所示，读取范围并不是一个规整的圆形.

由此可知，在距读写器天线相同距离处收到的天线发出的信号，其强度值也必定存在一定程度的偏差.在基于RSSI的定位算法中，目标位置是根据接收到的信号强度值进行计算的，并没有将室内环境的一些特殊性考虑进去，从而使最后的定位结果存在一定的偏差.

本文在一个如图4中的（a）所示的7 m×5 m的室内环境中布置4个RFID读写器天线，并在相同时间内统计标签在各个位置处的读取总数，如图4中的（a）～（e）所示.各读写器天线在其读取范围内的读取情况与理想模型区别很大，根据理想模型有：在离读写器天线越远处，接收到的信号越弱，即标签读到的次数越少；距读写器天线相同距离处，所接收的信号强度应该是相同的，即标签读到的次数相同.而在实际情况中，由于室内环境存在的综合影响，读写器天线的读取情况呈现较大的不规则性和特殊性，而传统的信号传播衰减模型无法恰当地描述室内信号的变化规律.

图3 RFID读写器读取模型Figure 3 Read pattern of RFID readers

2.2 读取数据过滤分析

尽管RFID信号的传播模型并不能很好地解释RFID的信号衰减情况，但对于RFID读写器天线的读取范围，由图4中的（b）～（e）可知是连续的.本文通过判断哪些读写器天线读到目标物体所带的标签来进行一种位置过滤处理.如图（5）所示，当目标物体所在位置只能被天线3和4检测到时，在天线3和4以外的地方是不太可能在目标标签附近的[6]，于是过滤掉天线3和4读取范围之外的参考标签，只让天线3和4读取范围内的参考标签进入下一步的精确定位运算.过滤运算不但减小了所需的系统资源和运算复杂度，而且排除了无关点的信息.由文献[6]可知，对于基于场景的定位算法，排除无关信息点可以提高定位算法的精确度.

图4 读写器在各个位置的读取情况Figur e 4 Cover pattern of RFID readers

图5 位置过滤处理Figur e 5 Position f iltration process

3 室内RFID局部加权回归定位算法

为了更好地将室内环境的特殊性考虑进去，需寻求一种能较好地符合标签位置与其信号参数之间的关系.本文针对标签在读写器天线上的流水线型的收包率信息，提出了一种局部加权回归（locally weighted regression,LWR）定位算法.首先需要进行数据训练，通过采集室内定位区域的参考点处的信号特征参数，形成位置信号参数数据库（本文采集的是各天线在2 s内的读取标签的次数，即可看作收包率）.判断目标位置时，将实际接收到的信号参数通过局部加权回归定位算法得到目标物体的位置.

3.1 算法模型定义

如图6所示，x为标签信号，y为标签位置.局部加权回归定位算法首先通过训练样本信息和目标信息X来拟合算法，计算位置信息时检查数据集合，对目标信息X周围区域内的样本信息作算法处理.局部加权回归算法注重对邻近点的精确拟合，同时忽略那些离得较远的样本点的贡献.拟合后可得到读写器天线读到的信号参数和位置的关系，于是可以在任意位置处根据读写器天线得到的信号参数信息来计算目标标签所在的位置.由图6可知，定位算法的设计是获得精确定位的关键.

图6 定位算法框图Figure 6 Flowchart of the positioning algorithm

3.2 局部加权回归定位算法步骤

定义标签在各读写器天线上的信号参数信息为

式中，x1,x2,···,xm表示标签在天线1,2,···,m上被读取到的情况.定义标签在室内的位置信息为

式中，loc x和loc y分别表示标签在室内的横坐标和纵坐标.假设标签信号参数X与位置Y的关系为

此处为便于书写，将x0定义为1.h(x)就定义了从输入到输出的一个转化关系，其中θT称为权重参数，表示此线性函数的空间映射.

为了使得局部加权回归定位算法的预测在训练样本数据上尽可能准确，应使预测值和实际值的平方差尽可能小，定义代价函数

式中，n表示训练样本的数目；i表示第i个训练样本；w(i)为权重参数，表示目标信号和样本信号的近似程度.如果近似程度越高，则w(i)越大，在局部加权回归定位算法中的权重越大，相当于给所有的样本信号加权.在确定目标的位置时，与目标信号越近的样本信号参与的比例越大.定义权重参数w(i)为

式中，τ为带宽参数，控制了权值随距离下降的速度；x1,x2,···,xm是天线1,2,···,m实际检测到的信号值，是第i个样本信号在天线1,2,···,m的检测值.假如

由式（11）可知，权值函数w(i)是一个钟形函数.当τ较小时，会得到一个比较窄的钟形函数，即选取较少的邻近参考样本信息进入拟合算法；当τ较大时，得到的钟形函数较宽，会取得较多的邻近参考样本信息进入拟合算法.τ的选取要适当，否则会陷入欠拟合或过拟合的情况，导致算法的精确度下降.

对于θ参数的选取，可通过最小化代价函数J(θ)来获得.由J(θ)函数的表达式可知，一定存在一个全局最小值.本文由梯度下降算法获得θ值，给θ一个初始值，再由式（14）不断更新θ值，直到J(θ)收敛，则可认为找到了最符合条件的θ参数

式中，参数α为学习速度，即每一次更新的幅度.

通过矩阵推导可得出θ的闭式解形式为

式中，X为经过位置过滤处理后在可能范围内的参考位置的信号参数向量，Y为参考位置所对应的坐标向量，W为各参考位置在确定目标位置时的权重贡献向量.最后将θ参数向量代入式（9），得到待定位目标在室内的精确位置(loc x,loc y).

若在室内采用局部加权回归定位算法定位目标物体，则可以通过对室内环境的学习以及提取室内各位置处的特征信息来提高定位精度.在原本误差就高的边缘地区，可增加参考位置信息，进一步提高待定位目标的位置精度.本系统是在一个7 m×5 m的空间中，每隔0.6 m进行一个位置信息采样，而边缘地区的参考点数量较少，如图7中的点所示.为了提高边缘地区的定位精度，本文采用了增加边缘地区采样点信息的方法，在相邻采样点的中点处也进行标签信号的采集，如图8所示.

图7 参考标签位置 Figur e 7 Reference label position

图8 边缘参考标签位置Figur e 8 Edge reference label position

4 系统构建和实验结果分析

4.1 系统构建

本文的室内定位验证系统采用4个读写器天线来完成，且将这4个读写器天线作为一个基本单元在空间上进行扩展.

本定位系统的硬件由中央处理器、路由器、超高频电子标签四合一读写器、超高频读写器天线以及无源标签组成，系统架构如图9所示.读写器工作频率范围为902～928 MHz，输出功率范围为0～30 dBm.为了使4个读写器天线的读取范围适当覆盖室内实验环境，将读写器功率调整为25 dBm.

图9 室内定位验证系统架构Figure 9 Indoor positioning verif ication system architecture

4.2 实验结果与分析

本文提出的流水线型局部加权回归定位算法是在VS2010平台下实现的.为验证定位算法的有效性，在7 m×5 m的空间搭建整个定位系统，并随机选取几个位置.在这些位置处进行多次定位算法验证，验证结果如图10所示.图中的“×”表示目标人员实际所在的位置，“◦”表示通过本定位算法所计算出的人员位置.从图中可以看出，流水线型局部加权回归定位算法在室内环境下取得了较高的定位精度，使得误差范围控制在0.8 m之内.

图10 流水线型局部加权回归定位算法结果的分布图Figure 10 Positioning results of the pipelined locally weighted regression algorithm

本文通过定位误差来衡量定位算法的性能.定位误差表示估计的定位结果与实际位置之间的差距，定位误差越小，定位性能越好.本文将提出的流水线型局部加权回归定位算法与LANDMARK算法、VIRE算法进行比较，以验证所提出的算法的优越性.在7 m×5 m的定位区域内随机选取10个位置，经20次运算得到这20次定位结果的误差，再将误差取平均值，得到如图11所示的结果.

图11 定位误差结果比较Figure 11 Positioning error of different methods

由实验结果可知，本文提出的流水线型局部加权回归定位算法与传统的LANDMARK定位算法和VIRE定位算法相比，有着较为显著的优势.由于室内环境的复杂性，在室内环境下的信号传播模型不能清楚地表示信号在各个位置的接收情况，其多径效应、反射、折射等因素会使得在每一个位置都有其独特的信号接收情况，于是本文以流水线方式获取的收包率信息作为定位信号参数，其相对稳定的性质有利于精确定位.根据局部加权回归定位算法学习室内环境对各位置处接收信号参数的影响，并将其融入定位算法中，可得到更准确的定位信息，降低定位的误差.由图11的实验结果可以看出：LANDMARK定位算法的最小定位误差为0.83 m，最大定位误差为1.22 m，平均定位误差为1.059 m；VIRE算法的最小定位误差为0.46 m，最大定位误差为0.98 m，平均定位误差为0.727 m；流水线型局部加权回归定位算法的最小定位误差为0.12 m，最大定位误差为0.83 m，平均定位误差为0.46 m.与前两种算法相比，流水线型局部加权回归定位算法的定位精度分别提高了56.56%和36.73%.

本文所提出的流水线型局部加权回归定位算法是以流水线方式获取的收包率信息作为定位信号参数，大大改善了稳定性和实时性.由于天线是布置在天花板上的，信号遮挡这种情况发生的概率比较小.因此，当人员在室内移动时，只要人员之间没有特别的位置关系（如遮挡）时，天线可以采集到各个人员佩戴的标签的信息.并且由实验可知，在多目标情况下，本文提出的定位算法仍然可以比较精确地得到多目标物体的运动轨迹.如图12所示，在室内环境中的两个目标各自随意在室内运动，本定位算法可以精确地跟踪目标的运动，且将延时控制在0.5 s以内.

图12 多目标定位结果Figure 12 Multi-targets positioning result

5 结语

针对RFID信号在室内传播的不规则性导致定位精度不高的问题，本文提出了一种流水线型局部加权回归定位算法.在合理布置室内读写器天线的基础上，对目标位置所获取的定位信号参数进行过滤计算，以提高算法的效率；根据流水线型局部加权回归定位算法将室内环境对各位置的影响融合进去，实现目标的精确定位.本文将无线信号的链路收包率作为定位信号参数，可以降低由无线信号的不确定性导致的误差.因为链路收包信息是一个累计量，相对于瞬时信号，更具稳定性.在实时性方面，本文采用了流水线方式获取收包率信息，通过流水线复用链路收包信息使得定位的实时性提高了5倍.经实验验证，本算法在不增加系统复杂度以及参考数据的存储复杂度的情况下，提高了定位精度.与LANDMARK算法和VIRE算法相比，分别提高了56.56%和36.73%，实现了低成本、高精度并且实时的室内定位.在运算复杂度方面，相对于LANDMARK和VIRE定位算法有一定程度的增加.本文提出的基于RFID的定位模型和算法易于推广和普及，为今后实现海量目标的定位跟踪以及多技术整合定位，如蓝牙技术[14]等，奠定了基础.

[1]ZHOU J H,GILMAN E,YLIANTTILA M,RIEKKI J．Pervasive service computing:visions and challenges[C]//IEEE International Conference on Computer and Information Technology(CIT),2010: 1335-1339．[2]DEDESG,DEMPSTERA G．Indoor GPSpositioningchallenges and opportunities[C]//Vehicular Technology Conference，2005:412-415．

[3]闫保中，张帅，张宇．基于RFID的室内人员定位系统的设计与实现[J]．应用科技，2011,38（11）:39-42,53．

YAN Baozhong,ZHANG Shuai,ZHANG Yu．Design and implementation of the indoor personnel positioning system based on RFID[J]．Applied Science and Technology,2011,38（11）:39-42,53．

[4]SAAD S S,NAKAD Z S A．Standalone RFID indoor positioning system using passive tags[J]．IEEE Transactions on Industrial Electronics,2011,58（5）:1961-1970．

[5]李魏峰．基于RFID的室内定位技术研究[D].上海：上海交通大学，2010．

[6]JIN Guangyao,LU Xiaoyi．An indoor localization mechanism using active RFID tag[C]//Proceedings of the IEEE International Conference on Sensor Networks,Ubiquitous,and Trustworthy Computing,2006.

[7]ZHU Fengjuan,WEI Zongheng,HU Binjie,CHEN Jianguang, GUO Zimin．Analysis of indoor positioning approaches based on active RFID[C]//International Conference on Wireless Communications,Networking and Mobile Computing,2009:1-4．

[8]WANG C,WU H Y,TZENG N F．RFID-based 3-D positioning schemes[C]//IEEE International Conference on Computer Communications,2007:1235-1243．

[9]PARK Y S,LEE J W,KIM S W．Improving position estimation on RFID tag f loor localization using RFID reader transmission power control[C]//IEEE International Conference on Robotics and Biomimetics,2009:1716-1721．

[10]王一乐．基于RFID的室内定位方法研究与应用[D].西安：西安理工大学，2010．

[11]DHANANJAY L,MANJESHwAR A,HERRMANN F,UYSAL-BIYIKOGLU E, KESHAVARZIAN A.Measurement and characterization of link quality metrics in energy constrained wireless sensor networks[C]//Global Telecommunications Conference,2003:446-452．

[12]KHOSHGOFTAAR T M,PANDYA A S,LANNING G D L．Application of neural networks for predicting defects[J]．Annals of Software Engineering,1995,1(1):141-154．

[13]LIN S,ZHANG J,ZHOUQ G,GU L,STANKOVIC J A,HE T．ATPC:adaptive transmission power control for wireless sensor networks[C]//Proceedings of the 4th International Conference on Embedded Networked Sensor Systems,2006:223-236．

[14]李娟娟，张金艺，张秉煜，周荣俊，唐夏.蓝牙4.0标准规范下的模糊指纹定位算法[J].上海大学学报：自然科学版，2013,19(2):126-131.

LI Juanjuan,ZHANG Jinyi,ZHANG Bingyu,ZHOU Rongjun,TANG Xia.Fuzzy f ingerprint location for bluetooth specif ication version 4.0[J].Journal of Shanghai University:Natural Science,2013,19(2):126-131.(in Chinese)