一种基于区域分割和目标搜索的室内定位方法

向祖权　靳　超　郭纯轩　许慧文

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



一种基于区域分割和目标搜索的室内定位方法

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

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

基于参考标签的最近邻居思想提出区域分割和目标点搜索方法，对室内平面物体进行定位.对最近邻居参考标签围成的矩形定位区域进行两次连续分割，缩小定位区域范围，选取该范围中心点作为起始点，向x，y轴正负方向以规定步长进行目标搜索，找出与待定位标签信号强度值之间的欧氏距离满足精度要求的点作为最终定位点.仿真实验结果表明，在不改变硬件条件的基础上，改进算法的定位精度比传统LANDMARC方法提高了64%.

区域分割；目标搜索；射频识别；参考标签；室内定位

0　引　　言

室内定位技术是指在室内环境下对物品进行定位.由于建筑物的遮蔽，考虑到定位精度、成本等方面，GPS等室外定位方式不再适用[1]，需要一种新的定位方法来满足室内环境的要求.

射频识别(radio frequency identification，RFID)技术因其数据传递快、识别距离远、非接触数据传递等特点[2]，正在逐步被应用到室内定位中.Ling等[3]提出了一种基于RFID技术利用参考标签进行辅助定位的LANDMARC(location identification based on dynamic active rfid calibration)定位系统，但是该系统定位精度受到自身硬件条件的限制有一个上限值[4]，在定位精度要求较高的情况下此种定位方法不能够满足定位要求.

文中通过对最邻近参考标签所组成的定位区间进行分割[5]，在分割后区间内对目标点进行搜索，引入“距离-损耗”模型[6-8]，对区间内的点进行虚拟信号强度赋值，选出信号强度与待定位标签信号强度相同的点作为最终的定位结果.

1　LANDMARC定位系统

LANDMAC定位系统布置见图1.它通过引入参考标签进行辅助定位(参考标签坐标已知)提出“最近邻居”思想，通过与待定位标签邻近的若干参考标签的坐标进行加权运算得到待定位标签的坐标.现假设有m个阅读器，n个参考标签，p个待定位标签，每个阅读器都可以读到参考标签和待定位标签的信号强度(receive signal strength identification，RSSI)值.

图1　LANDMAC定位系统示意图

记某个待定位标签Pi在各个阅读器上的RSSI值构成如下矢量:Pi=(PiM1,PiM2,…,PiMm)

式中：PiMs为该待定位标签Pi在第s个阅读器上的RSSI值，i∈(1,p)，s∈(1,m).

记某个参考标签Rj在各个阅读器上的RSSI值构成如下矢量:Rj=(RjM1,RjM2,…,RjMm)

式中：RjMs为该参考标签Ri在第s个阅读器上的RSSI值，j∈(1,n)，s∈(1,m).

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

(1)

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

(2)

比较Di,j的大小，选出k个与待定位标签邻近的参考标签，通过计算可以得到待定位标签的坐标为

(3)

式中：j∈(1,k)，(xj,yj)为参考标签坐标，wj为第j个参考标签的权重，可通过下式计算得到.

(4)

系统的定位误差可以通过待定位标签的真实坐标与计算坐标进行比较得出

(5)

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

2　改进LANDMARC算法

2.1RSSI损耗模型

在不考虑室内环境干扰的情况下，阅读器接收到的标签的信号强度会因传播距离和信号到达角度而产生的损耗.RSSI损耗值为

(6)

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

阅读器接收到的RSSI值为

(7)

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

为了减少因信号到达角度而产生的损耗，可以扩大阅读器天线接收信号的角度，将阅读器的天线设计成球面.这样就可以忽略信号到达角度产生的损耗，将RSSI损耗模型简化为“路径-损耗”损耗模型.

(8)

(9)

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

2.2定位方法

首先利用LANDMARC定位系统可以得到k个与待定位标签最邻近的参考标签，取k=4，见图2，待定位标签位于a，b，c，d四个参考标签组成的区域中.以下分析中假设这4个参考标签与待定位标签之间RSSI值欧氏距离大小排序为：Da

图2　空间分割示意图

记正方形anom4个顶点的坐标为：{(xa,ya),(xn,yn),(xo,yo),(xm,ym)},其中：xn=(xa+xd)/2，yn=(ya+yd)/2；xo=(xa+xb)/2，yo=(ya+yd)/2；xm=xa，ym=(ya+yd)/2.取正方形中心点(x′,y′)作为搜索的初始点，其中：

(10)

(11)

以(x′,y′)为中心，s为步长，分别向坐标轴x，y的正负方向搜索，得到4个点，见图3，它们坐标分别是：{(x′+s,y′),(x′,y′+s),(x′-s,y′),(x′,y′-s)}.每个点与各个阅读器之间的距离通过两点之间距离公式可以得到，将距离带入公式(9)可以得到该点在阅读器上的虚拟RSSI值.

图3　目标点搜索示意图

例：点(x+s,y)与各个阅读器之间的距离为{d1,d2,…,dm}，将di带入式(9)可以得到点(x′+s,y′)在阅读器i上的虚拟RSSI值Prec(i)，同理可以得到其在每个阅读器上的RSSI值，记为：{Prec(1),Prec(2),…,Prec(m)}，计算该点与待定位标签之间RSSI值之间的欧氏距离.对其余3个点重复上述计算，选出4个点中与待定位标签之间RSSI的欧氏距离最小的点作为下次搜索的起点.不断重复上述步骤，直到搜索出的点与待定位标签之间RSSI值欧氏距离满足精度要求e为止，该点即为最后的定位点.改进算法流程见图4.

图4　改进算法流程图

3　仿真实验及分析

仿真实验环境设置为11 m×11 m的室内空间，见图5，布置有36个参考标签(相邻2个参考标签之间间距2 m)，4个阅读器(相邻2个阅读器之间间距4 m).取最近邻参考标签为4个，即k=4；搜索步长为0.01，即s=0.01；定位精度要求为1，即e=1.现对该环境中的10个参考标签(坐标见表1)，分别利用LANDMARC算法和改进算法进行定位计算，并比较2种算法的定位误差和标注差.

(12)

图5　仿真实验环境布置

表1　待定位标签坐标

利用LANDMARC算法和改进算法对待定位标签进行定位仿真的结果见图6～7.对比两图可以看出改进算法的定位结果比LANDMARC算法更接近待定位标签的实际坐标.改进算法中目标点搜索过程见图8.

由图9可知，LANDMARC算法定位误差在0.14～0.74 m之间波动；改进算法的定位误差在0.01～0.18 m之间波动，由图9中可知改进算法在定位误差范围方面优于LANDMARC定位算法.

图6　LANDMARC算法定位结果

图7　改进算法定位结果

对10个待定位标签进行计算，利用LANDMARC算法定位的平均误差为0.39，标准差为0.21；利用改进算法定位的平均误差为0.14，标准差为0.05.从计算结果可以看出改进算法定位精度和定位稳定性都要优于传统的LANDMARC算法.

图8　改进算法目标点搜索过程

图9　定位误差

4　结 束 语

文中提出的算法在传统的LANDMARC算法基础上，对最近邻参考标签围成的定位区域进行两次连续分割，在分割后的区域中进行目标点搜索，找出目标点虚拟RSSI值与待定位标签RSSI值之间欧氏距离最小的点作为最终的定位结果.通过对比分析，该算法在不改变传统LANDMARC定位算法硬件系统的基础上，通过对算法的改进，将定位精度提高了64%，扩大了定位系统的应用范围.

[1]ALI M, OSAMA M. RFID indoor location identification for construction projects[J]. Automation in Construction.,2014,39(1):167-179.

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

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

[4]李婧.RFID室内三维定位算法研究[D].成都：电子科技大学,2010.

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

[6]SAMER S S, ZAHI S. A standalone RFID indoor positioning system using passive tags[J]. Ieee Transactions on Industrial Electronics,2011,58(5):1961-1970.

[7]陈勇,石南,陈永光.基于RFID和无线传感的矿井实时定位预警系统[J].电子设计工程,2012(21):55-58.

[8]黄双欢,程良伦.一种拓扑约束的RFID三维定位方法[J].计算机应用研究,2012(1):77-80.

An Indoor Positioning Method Based on the Region Division and Target Search

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

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

Based on the nearest neighboring theory, a method of region division and target searching is proposed for the positioning of interior plane objects. Firstly, two consecutive divisions of the rectangular region enclosed by the nearest neighboring reference labels are conducted to reduce the searching ranges. By picking the central point of the range as the starting point, target searching is conducted in both positive and negative directions ofxandyaxes with a fixed step. Finally, the final positioning point is determined based on the condition that the Euclid distance of signal intensity between the label to be positioned and the final positioning point meets the accuracy requirement. Simulation results show that the algorithm in this paper improves the positioning accuracy of about 64% compared to the traditional LANDMARC methods without changing the hardware conditions.

region division; target search; RFID; reference label; indoor positioning

2016-05-30

TP399

10.3963/j.issn.2095-3844.2016.04.022

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