基于子区域划分的室内定位算法研究

郭晓凤，徐志良

（南京机电职业技术学院 江苏南京 211135）

基于子区域划分的室内定位算法研究

郭晓凤，徐志良

（南京机电职业技术学院 江苏南京 211135）

文中基于提高射频识别定位系统中定位精度的目的，提出了一种改进的IMLANDMARC算法，该算法通过对待定位标签所在区域进行子区域划分，并增加虚拟参考标签的方法，对LANDMARC算法进行改进，使用Matlab软件对算法进行仿真试验，与射频识别定位系统中常用的LANDMARC算法、VIRE算法和BVIRE算法比较，结果表明在耗时增加较小情况下该算法有效的提高了定位精度。

LANDMARC算法；划分子区域；IMLANDMARC算法；定位精度

室内定位是指在室内环境中实现位置定位，主要应用在矿山救援、仓库货品定位、车库车辆位置定位等方面。采用的方法有超声波[1]、红外[2]、超宽带[3]、基于射频识别等定位技术[4]。射频识别技术（Radio Frequency Identification，RFID）具有非接触、非视距、成本低、定位精度高等优点，因此成为了优选的室内定位技术[5]。基于RFID定位[6-9]的典型算法主要有LANDMARC算法、VIRE算法、BVIRE算法。

文中在LANDMARC算法的基础上，通过划分子区域的方式，对LANDMARC算法进行了改进[9-14]（简称IMLANDMARC算法），并且进行了仿真，把仿真结果与LANDMARC算法、VIRE算法和BVIRE算法进行比较，结果表明相同条件下IMLANDMARC算法的定位精度较高。

1 LANDMARC算法简介

LANDMARC[15]算法采用参考标签来进行辅助定位，通过参考标签的信号强度值与待定位标签的信号强度值之间的比较，采用“最近邻距离”权重思想，计算出待定位各标签的坐标。

假设有M个参考标签，K个阅读器，和N个目标标签，（图1所示为M=25，N=5，K=4）。N个目标标签随机布置在M个参考标签周围。

图1 定位系统图例

WI是第I个邻居的权重（I=1，2，3，…，n＜M，n是M个欧氏距离EJ中最小的n个邻居，WI可根据经验公式得到：

定义误差:

其中（x，y）为估计出的待定位标签位置，（x0，y0）为待定位标签的实际位置。

LANDMARC算法的优点如下：

①参考标签的引入降低了阅读器的数量，进而减少了定位成本；

②参考标签和待定位标签处于同样的环境中，可以大大抵消很多环境因素的影响；

③定位的信息更加准确。

LANDMARC算法的不足：

①参考标签的分布直接影响到定位的精度；

②较高的定位精度完全依赖于较高的参考标签密度，而高的标签密度势必带来大的干扰，同时也会增加成本。

2 对LANDMARC算法的改进

从LANDMARC算法的优缺点可以看出，参考标签的密度对定位的精度影响较大。本文是在LANDMARC算法基础上做了改进，主要思路如下：

1）首先使用LANDMARC算法对待定位标签进行初步的位置估计，获取该定位标签对应的4个临近参考标签（矩形区域）；

2）将参考标签的区域划分成4个相同大小的子区域，如图2所示。

图2 子区域划分图

3）根据估计位置估算待定位标签所在的子区域，如图3所示，然后在选定子区域内将另外3个顶点作为虚拟参考标签，并根据3个参考虚拟标签和一个实体的参考标签来估算待定位标签的位置。

图3 参考标签选择

主要的定位流程如图4所示。

图4 改进后的定位算法流程

3 仿真结果分析

3.1 改进的IMLANDMARC算法

文中采用了500个随机样本进行了仿真（空间大小：12 m*12 m，M=25，N=500，K=4），并将结果与LANDMARC算法，VIRE算法，BVIRE算法进行了比较，IMLANDMARC算法的定位精度较LANDMARC算法，VIRE算法，BVIRE算法有所提高，如图5所示。

图5 4种算法误差比较图

从定位每个标签的时间耗时上来看IMLANDMRAC算法稍高于LANDMARC算法，但是明显低于VIRE算法和BVIRE算法。如图6所示。

图6 4种算法耗费时间比较

在测试过程中，每种算法选取整个定位区域内的500个点作为测试点，使用累计分布函数（Cumulative distribution function，CDF）对比分析4种算法获得的值，结果表1所示。

从表1可以看出，IMLANDMARC算法的误差累计分部最靠近纵轴，所以其定位精度相比LANDMARC算法，VIRE算法，BVIRE算法较高。

表1 误差累积分布比例

3.2 IMLANDMARC算法参考标签间隔的研究

在定位区域不变的情况下，对参考标签的间隔大小进行了测试，并且对参考标签不同间隔定位结果与LANDMARC算法，VIRE算法，BVIRE算法做了比较。

将参考标签的间隔由原来的2 m分别增加到3 m和4 m，定位误差的比较如图7和图8所示，从定位误差的结果可以看出：当参考标签间隔为3 m的时候，如表2所示，IMLANDMARC算法的误差要稍高于BVIRE算法（平均误差约高于BVIRE算法0.04 m），但是优于LANDMARC算法（平均误差约低于LANDMARC算法0.05 m），VIRE算法（平均误差约低于VIRE算法0.09 m）。

当参考标签间隔为4m的时候，如表3所示，IMLANDMARC算法的误差比较大，明显高于LANDMARC算法，VIRE算法，BVIRE算法。

误差累计分布（Cumulative distribution function，CDF）比较如表 2、表3所示，从误差累计结果可以看出[16]：当参考标签间隔为3 m的时候，小于0.3 m的比例，IMLANDMARC算法约为83%，低于BVIRE算法93%，但是高于LANDMARC算法78%，VIRE算法55%。

图7 4种算法误差比较-参考标签间隔为3 m

图8 4种算法误差比较-参考标签间隔为4 m

表2 误差累积分布比例-参考标签间隔为3m

当参考标签间隔为4 m的时候，小于0.3 m的比例，IMLANDMARC算法约为27%，低于BVIRE算法93%，LANDMARC算法78%，VIRE算法55%。

表3 误差累积分布比例-参考标签间隔为4 m

从前面仿真结果可以看出，参考标签的间隔在3 m左右的时候，IMLANDMARC算法定位精度较BVIRE算法要差一些（平均误差约高于BVIRE算法 0.04 m，误差小于0.3 m的占比约低于BVIRE算法7%左右），但是好于LANDMARC算法和VIRE算法，如果要降低参考标签的数量又兼顾定位精度，IMLANDMARC算法也具有一定的使用价值。

参考标签的间隔在4M左右的时候，IMLANDMARC算法定位精度较LANDMARC算法、VIRE算法和BVIRE算法3种算法要差一些，不建议采用。

4 结束语

文中提出的IMLANDMARC算法从仿真结果上来看，在相同参考标签间隔的情况下，IMLANDMARC算法定位精度相对于LANDMARC算法有所提升，虽然耗时也相对增加一些，但是明显低于VIRE算法和BVIRE算法；当参考标签的间隔是LANDMARC算法、VIRE算法和BVIRE算法3种算法1.5倍的时候，仍具有较好的精度，可以在一定程度上降低工程实施的成本；综上，IMLANDMARC算法具有一定的参考价值和工程可实施性。

[1]Sanpechuda T， Kovavisaruch L.A review ofRFID localization: applications and techniques [C].Electrical Engineering/Electronics，Computer，Telecommunications and Information Technology，2008.ECTI-CON 2008.5th International Conference on 2008.

[2]蒋婷婷，郑国莘，郑瑞杰．IR-UWB测距在多径信道下的时延性能分析[J]应用科学学报，2007，25（3）:327-330.

[3]Curran K，Furey E，Lunney T，et al.An evaluation of indoor location determination technologies[J].Journal of Location Based Services，2011，5（2）:61-78.

[4]Tesoriero R， TebarR， Gallud J.Improving location awareness in indoor spaces using RFID technology[J].Expert Systems with Applications，2010，37（1）:894-898.

[5]周悖，胡方明，胡华鹏，等.基于牛顿插值的RFID室内定位算法.电子科技，2015，26（9）:34-40.

[6]蒋华勤，李静.基于LANDMARC的RFID室内定位算法优化[J].科技通报，2013，29（6）:206-207

[7]俱莹.基于RFID的室内定位算法研究[D].天津大学，2010.

[8]王远哲，毛陆虹，刘辉，等.基于参考标签的射频识别定位算法研究与应用[J].通信学报.2010，31（2）:86-92.

[10]李军怀，张果谋，于蕾，等.具有环境自适应性的虚拟参考标签定位方法[J].应用科学学报，2013，31（4）:402-410.

[11]陈家琪，严梓乘.一种Newton插值的RFID室内定位改进算法[J].计算机系统应用，2011，21（1）:45-48.

[12]李鹏，马宁，杨拥军，等.基于RFID的边界虚拟参考标签改进算法[J].计算机应用研究，2013，30（1）:158-160.

[13]段本亮，李建雄，陈明省，等.改进的RFID室内定位算法[J].天津工业大学学报，2013，32（4）:66-70.

[14]杨辉，蔡坚勇，高杰星，等.基于LANDMARC定位算法复杂度的分区算法改进[J].计算机系统应用，2012，22（5）:103-106.

[15]Lionel MN，Liu Yun Hao，Lau Y C，et a1.LANDMARC: Indoor location sensing using active RFID[J].WirelessNetworks，2004，10（6）:701-710.

[16]雷震，李怡，付琳琳.液氧主容器温度测量误差分析与改进方法[J].火箭推进，2015(6)：105.

Research on indoor localization algorithm based on dividing sub-area

GUO Xiao-feng，XU Zhi-liang
（Nanjing Institute of Mechatronic Technology，Nanjing 211135，China）

Based on the purpose of improving the positioning accuracy of radio frequency identification system，an improved IMLANDMARC algorithm is proposed.This algorithm is improved by dividing sub-area of target tag area and adding virtual reference tags.The Matlab is being used to simulate the algorithm，IMLANDMARC algorithm effectively enhances the localization accuracy with shorter time consumption increase by comparing with LANDMARC algorithm，VIRE algorithm and BVIRE algorithm.

LANDMARC algorithm；dividing sub-area；IMLANDMARC algorithm；localization accuracy

TN99

A

1674－6236（2016）24-0025-04

2015-12-11 稿件编号：201512134

江苏省高等职业院校国内高级访问学者计划资助项目（2014FX043）

郭晓凤（1979—），女，辽宁葫芦岛建昌人，硕士研究生，讲师。研究方向：电子信息技术。