基于区域划分和目标搜索的室内RFID三维定位算法

向祖权 靳 超 许慧文

(高性能船舶技术教育部重点实验室1) 武汉 430063) (武汉理工大学交通学院2) 武汉 430063)



基于区域划分和目标搜索的室内RFID三维定位算法

向祖权1,2)靳 超1,2)许慧文2)

(高性能船舶技术教育部重点实验室1)武汉 430063) (武汉理工大学交通学院2)武汉 430063)

为提高室内三维定位系统的性能，提出一种基于区域划分和目标搜索的室内RFID三维定位算法.通过布置在室内顶部和侧面的参考标签划分一个待定位标签所在的区域，选取该区域中心点作为目标搜索的初始点，向x，y，z轴正负方向对待定位标签进行搜索，通过不断逼近，最终确定待定位标签的坐标.仿真实验表明，该算法定位误差小，稳定性优良.

区域划分；目标搜索；射频识别；三维定位；室内定位

0 引 言

GPS定位系统适合室外空旷地域的定位，对于建筑物过多、遮挡较为严重的情况则会产生明显的定位误差，所以GPS定位方法并不适用于室内定位.Sun等[1]提出A-GPS方法用于改进GPS系统在室内环境中定位的效果.Lau等[2]对Zigbee技术在室内定位中的运用进行了相关研究.Yuen等[3]提出运用Wi-Fi技术对室内定位精度进行提高.但目前研究最多，运用最多的是RFID技术，它以识别距离远、响应速度快、非接触操作、成本低等特点成为室内定位研究的热点[4].

基于RFID技术的室内定位系统主要有Ling等[5]提出的LANDMARC定位系统，Hightower等[6]研究的SpotOn系统，Zhao等[7]在LANDMARC系统上改进得到的VIRE系统.常见的算法有解析算法[8]、估值算法[9]、最近邻居算法等.但是这些系统和算法主要针对室内平面二维定位，对室内三维空间定位的研究较少.虽然高锐等[10]提出的基于空间分割的无源RFID定位方法，以及董永峰等[11]针对空间分割方法的改进方法，可以对室内三维空间进行定位，但是他们方法中的参考标签一部分是布置在地面上，在实际环境中，由于室内大部分物体是布置在地面上的，所以会对参考标签产生严重的干扰，这样会降低定位的精确度.

文中提出一种新的参考标签布置方式，将传统方式中布置在空间底部的参考标签布置到空间的侧面，保留空间顶部的参考标签.利用空间顶部参考标签确定待定位标签的x，y坐标区域，用空间侧面参考标签确定待定位标签z坐标区域，再用目标搜索方法在定位区域内搜索待定位标签的坐标.该算法在不增加参考标签数量的情况下，通过算法的改良，提高了定位精度.

1 “最近邻居”参考标签选择

“最近邻居”参考标签就是指与待定位标签相邻的参考标签.通过计算参考标签与待定位标签之间RSSI(receive signal strength identification)值的欧式距离，选取距离最小的若干参考标签作为“最近邻居”参考标签，选择过程如下.

假设有m个阅读器，n个参考标签，p个待定位标签，每个阅读器都可以读到参考标签和待定位标签的信号强度值.

记某个待定位标签Pi在各个阅读器上的RSSI值构成如下矢量：Pi=(PiM1,PiM2,…,PiMm).式中：PiMs为该待定位标签Pi在第s个阅读器上的RSSI值，i∈(1,p)，s∈(1,m)；记某个参考标签Rj在各个阅读器上的RSSI值构成如下矢量:Rj=(RjM1,RjM2,…,RjMm).式中：RjMs为该参考标签Rj在第s个阅读器上的RSSI值，j∈(1,n).

待定位标签PiMs与参考标签RjMs之间RSSI值的欧式距离为

(1)

因为需要选出与待定位标签Pi邻近的若干个参考标签，所以对于待定位标签Pi来说，需要计算n个参考标签与其之间RSSI值的欧氏距离，它们组成一个集合Di.

(2)

通过比较Di,j的大小，可以选出k个与待定位标签邻近的参考标签，即为k个“最近邻居”参考标签.

2 RSSI损耗模型

在室内环视距环境下，阅读器接收到的标签的RSSI值会因信号传播距离远近和到达角度差异而产生不同程度的损耗.RSSI损耗值为

(3)

式中：PL(d)为传播路径损耗；L(θ)为到达角度损耗.

阅读器接收到的RSSI值为

(4)

式中：Pt为标签发射的信号强度.

通过扩大阅读器天线接收信号的角度可以减少因信号到达角度而产生的损耗.因此，可以将阅读器的天线设计成球面，这样就可以有效接受各个方向到达的信号，从而减少信号因到达角度而产生的损耗.在忽略到达角度损耗之后可以将RSSI损耗模型简化为“路径-损耗”模型.

(5)

所以：

式中：PL(d0)为传播距离为d0时，信号在自由空间中的路径损耗；Xσ为阴影衰落(遮蔽因子)，它是均值为0，方差为σ的高斯随机变量；n为路径损耗指数，与所处环境相关.

3 环境布置

传统参考标签布置方式为对称式双层参考标签布置，见图1，在空间顶部与底部对应位置布置参考标签，这一布置方式在空间有较多障碍物时会产生较大误差，因为空间障碍物主要存在于地面上，会对参考标签产生遮挡，对参考标签的信号强度产生严重干扰，不利于空间物体的定位.

图1 对称式双层参考标签布置

本算法在参考标签的布置上作出改变，分别在空间顶部和侧面布置参考标签，见图2.顶部参考标签用于对物体进行水平方向的位置定位，侧面参考标签用于对物体进行垂直方向的位置定位，通过水平方向和垂直方向的定位可以得到待定位物体在空间的位置.

图2 垂直式立体参考标签布置

顶部参考标签等间距布置，侧面参考标签可以根据实际环境进行布置.如果空间高度较低，可以在侧面布置3层参考标签将空间分成2层；如果空间高度较高，可以侧面布置4层参考标签将空间分成3层.阅读器布置在空间的4个角落(顶部A，B点，底部C，D点)，这样布置可以在占用空间最少的情况下获取最大范围的信号覆盖.

4 三维空间定位算法

4.1 空间分割

图2为一个长、宽、高为9m×9m×4m的室内空间.空间顶部均匀布置16个参考标签，相邻参考标签之间距离3m.侧面均匀布置12个参考标签，高度方向上参考标签距离2m，宽度方向上参考标签距离3m.一共布置4个阅读器，分别位于顶部的A，B点和底部的C，D点.图3～4为顶部和侧面参考标签空间划分.

图3 顶部参考标签空间划分

图4 侧面参考标签空间划分

当需要对待定位标签进行定位时，首先，利用式(2)计算空间顶部参考标签和待定位标签之间RSSI值的欧氏距离，对欧氏距离进行升序排列，选出与待定位标签距离最近的4个参考标签作为“最近邻居”标签，如图3中的a，b，c，d 4个参考标签，它们在空间底部的投影为a′,b′,c′,d′，所以待定位标签就被定位在长方体abcd a′b′c′d′中.然后，再利用式(2)计算空间侧面参考标签和待定位标签之间RSSI值的欧氏距离，对欧氏距离进行升序排列，选出与待定位标签距离最近的4个参考标签作为“最近邻居”标签，如图4中的e，f，g，h 4个参考标签，它们在空间另一侧面的投影为e′，f′，g′，h′，所以待定位标签就被定位在长方体efgh e′f′g′h′中.因此，两个长方体相交部分就是待定位标签所在区域，即长方体abcd a″b″c″d″(见图5).所以待定位标签坐标满足如下条件.

(7)

图5 待定位区域

4.2 目标搜索

目标搜索的起始点可以为长方体abcd a″b″c″d″中任意一点，这里选取长方体abcd a″b″c″d″中心点o为目标搜索起始点，见图6.o点坐标可由式(8)计算得到.

图6 目标搜索

(8)

以o点为起始点，向x轴、y轴、z轴正负方向分别前进步长s，得到第一次搜索的6个点，它们的坐标为

(9)

利用式(6)计算式(9)6个点在4个阅读器上的虚拟RSSI值，再通过式(1)计算这6个点与待定位标签之间RSSI值的欧氏距离，对欧式距离进行升序排列，选出距离最小的点作为下一次搜索的起始点.重复上诉步骤，直到搜索点与待定位标签之间RSSI值的欧氏距离满足精度要求，则该搜索点即为最终的定位点.

4.3 算法流程

综合以上方式，算法的最终流程见图7.

图7 算法流程

5 仿真实验

运用MATLAB进行仿真，实验环境设置参见4.1.取“最近邻居”参考标签为4个，即k=4；搜索步长为0.01，即s=0.01m；定位精度要求为0.1，即e=0.1dB.现对该环境中的8个参考标签(坐标见表1)进行定位，并用式(10)计算定位误差.利用式(11)计算标准差.

式中：(x,y,z)为计算坐标；(x0,y0,z0)为真实坐标.

(11)

表1 待定位标签坐标 m

定位结果见表2，误差见图8.空间分割区域内目标点搜索路径和搜索过程中误差见图9～16.

表2 定位结果 m

图8 定位误差

图9 点(1.2,4.7,0.7)搜索路径

图10 点(2.4，3.5,1.6)搜索路径

图11 点(3.3,5.9,2.4)搜索路径

图12 点(4.1,6.4,0.9)搜索路径

图13 点(5.6,2.1,3.5)搜索路径

图14 点(6.9,1.7,2.3)搜索路径

图15 点(7.4,8.3,1.1)搜索路径

图16 点(8.5,7.6,3.1)搜索路径

从定位的结果来看，定位点基本在待定位标签附近很小的范围内.定位误差最大不超过0.25 m，最小误差仅为0.07 m，平均误差为0.13 m，标准差为0.06.相比于其他室内三维定位算法的误差(CPS算法误差为0.16～1.4 m，标准差为0.33；空间分割算法误差为0.27～1.32 m，标准差为0.34；改进空间分割算法误差为0.07～0.76 m，标准差为0.19)有更好的定位精度和算法稳定性.精度能够满足室内空间三维定位的要求.

6 结 束 语

文中提出的算法中，考虑到实际环境中室内物体主要布置在地面，会对地面参考标签产生干扰，因此将地面参考标签取消，在空间侧面和顶部布置参考标签.通过空间顶部参考标签确定待定位标签x、y坐标值的区域范围，空间侧面参考标签确定待定位标签z坐标值的区域范围.在确定的区域内，对待定位标签进行目标点的搜索.仿真结果表明，本算法的定位精度比CPS方法、空间分割算法和改进空间分割算法的定位精度都要高，而且算法的稳定性也优于上述3种算法.

[1]SUN GL, CHEN J, GUO W， et al. Signal processing techni-ques in network-aided positioning: a survey of state-of-art positioning designs[J]. IEEE Signal Processing Magazine, 2005, 22(4) : 12-23.

[2]LAU S Y, LIN T, HUANG T, et al. A measurement study of Zigbee-based indoor localization systems under RF interference[C]. Proc of the 4th ACM International Workshop on Experimental Evaluation and Characterization, International Confer-ence on Mobile Computing and Networking. New York: ACM Press, 2009: 35-42.

[3]YUEN C W, BALASUBRAMANIAM N, DIN N M. Improvement of indoor location sensing algorithm using wireless local area network(WLAN)IEEE 802[C]. Proc of the 9th IEEE Malaysia International Conference on Communications. Kuala Lumpur: IEEE Press, 2009: 857-862．

[4]NAN L, BURCIN B G. Performance-based evaluation of RFID- based indoor location sensing solutions of the built environment[J]. Advanced Engineering Informatics, 2011, 24 (3): 535-546.

[5]LING W, LI Y H. Improvement of location methods based on RFID[J]. The Journal of China Universities of Posts and Telecommunications, 2013, 20 (6): 36-41.

[6]HIGHTOWE R J, VAKILI C, GAETANO. Design and calibration of the SponON AD hoc location sensing system[D].Washington: University of Washington, 2001.

[7]ZHAO Y Y, LIU Y H, NI L M. VIRE: active RFID-based localization using virtual reference elimination[C].Proc of International Conference on Parallel Processing,IEEE Press, 2007: 56-63．

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

[9]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.

[10]高锐,程良伦,胡莘.一种基于空间分割的无源RFID室内定位方法[J].计算机应用研究,2012,9(1):184-186.

[11]董永峰,周艳聪,曹莹.基于RFID的虚拟参考标签三维室内定位算法[J].计算机工程设计,2015,36(6):1535-1539.Three-dimensional Indoor RFID Localization Algorithm Based on Region Division and Target Searching

XIANG Zuquan1,2)JIN Chao1,2)XU Huiwen2)

(KeyLaboratoryofHighPerformanceShipTechnology,MinistryofEducation,Wuhan430063,China)1)(SchoolofTransportation,WuhanUniversityofTechnology,Wuhan430063,China)2)

To improve the performance of three-dimensional indoor RFID positioning system, three-dimensional interior positioning algorithm is proposed based on the region division and target searching. Firstly, an area is divided where the target label will be by the reference labels which are arranged at the top and side in the room. Secondly, the central point of the area is picked as a starting point to search target with fixed step along the coordinate axis inX,YandZdirections. By the successive approximation, the coordinates of the target label are found. The simulation results show that the algorithm has small errors in positioning and is more accurate.

region division; target searching; RFID; three-dimensional localization; indoor localization

2016-08-16

TP399 doi:10.3963/j.issn.2095-3844.2016.05.003

向祖权(1973- )：男，博士，副教授，主要研究领域为船舶先进制造技术