改进的LANDMARC定位算法

摘 要： 在基于射频识别的室内定位LANDMARC算法中，定位的精度受到参考标签个数的影响。针对这个问题，引用免疫克隆算法中的变异思想，将其与聚类思想相结合，改进LANDMARC定位算法。改进的算法在定位过程中会产生和待定位标签信号强度更接近的虚拟的参考标签，利用这些虚拟的参考标签进行定位。实验结果表明，与传统的LANDMARC算法相比，改进算法的定位的精度更高，更适宜用于精度要求很高的定位环境中。

关键词： 射频识别；LANDMARC算法；聚类；变异；参考标签；室内定位

中图分类号：TP3 文献标识码 A 文章编号：1671－7597（2012）0210185－03

0 引言

随着无线通信技术的发展，人们对室内定位业务的需求越来越多。现有的室内定位技术[1][2]在图书馆，体育馆，地下车库，货品仓库等已经可以实现对人员以及物品的快速定位。最近几年涌现出了很多学者对室内定位系统的开发研究。目前，提出了5种基本的方法：1）起源蜂窝小区技术；2）时间到达法（TOA）；3）时间到达差法（TDOA）[3]；4）信号强度法（RSSI）；5）到达角度差法（AOA）[4]。

常用的室内定位方法是利用TOA，TDOA，AOA，RSSI中的一种或者多种方法来进行联合定位。主要研究成果包括：在2003年，密歇根州立大学的Lionel M.Ni提出了LANDMARC系统[5]。LANDMARC系统通过引入参考定位标签，根据参考标签与待定位标签之间的信号差异，采用对定位坐标的加权算法，在降低了系统成本的同时，达到了提高定位整体准确性的目的。国内对定位技术的研究在国际上以及国内刊物发表了大量的研究成果，其中最具有代表性的有：西南交通大学的、范志平介绍了基于RFID技术的LANDMARC定位系统[6]，并在此基础上提出了一种最近邻居改进算法和基于误差多级处理的数据融合定位方法。本文主要是基于LANDMARC室内定位系统研究RFID室内定位[7]问题。由于LANDMARC算法定位精度受系统标签的密度分布和布局形状影响，针对这个缺点[7]，提出了一种在定位过程中虚拟改变参考标签布局提高定位精度的方法，弥补了LANDMARC算法的不足。

本文后续部分内容安排如下：首先会介绍研究的相关背景资料和本文的研究情况，然后介绍在基于LANDMARC基础之上提出的改进的LANDMARC的RFID定位算法以及算法的实验结果和算法的性能比较，最后是结论和参考文献部分。

1 算法设计

1.1 防碰撞设计和标签及阅读器布局设计

在此算法设计中，需要保证在定位算法中不会产生标签碰撞和阅读器冗余带来的影响。采用分时控制阅读器读取标签信息来防止碰撞[8][9]，如表1所示（采用向量形式 表示某阅读器范围之内可读取到的标签 ）。

在每个时刻，系统中只有一个阅读器可以接收到标签发送出来的信号，然后根据接收到的信号强度分析标签在哪个阅读器的读取范围，再利用这个阅读器读取范围之内的参考标签进行定位计算，最后得到待定位标签的位置信息。为了保证在一个系统中的阅读器个数最少，且覆盖所有标签范围，本文借鉴蜂窝原理布置阅读器[10]，如图1所示。

假设实验环境是图书馆的书架，根据图1，大的矩形可以看作是一个书架，带标签的书籍、参考标签都摆放在书架上，小的矩形可以看作是按照阅读器阅读半径划分的，如此一来，所有标签都会被覆盖到的，再按照标签防碰撞算法和冗余阅读器去除算法可以保障每个标签只能让一个阅读器所接收。假设书架高H，宽W，层高d；阅读器读取半径r；当r

1.2 LANDMARC定位算法

假设在本系统中每个阅读器的读取范围是r，且已知参考标签的位置和阅读器的位置。

1）采用LANDMARC算法，通过标签间信号强度差异的大小来表征标签间距离的远近。定义待定位标签的信号强度为SG。对于参考标签，定义相应的信号强度向量为 ，其中 表示参考标签

在此阅读器上的信号强度。

对于待定位标签P，定义待定位标签与参考标签 之间的RSSI值的欧氏距离可以表示为：

待定位标签离参考标签越近，其信号强度的差别就越小，因此，E值显示了参考标签和待定位标签之间位置关系。

2）通过求得 个和待定位标签的信号强度最接近的参考标签，可以推算出待定位标签的坐标为：

其中， 表示的是待定位标签的实际坐标位置； 表示的是理论求得的待定位标签坐标位置。

1.3 改进的LANDMARC算法

聚类[12]的过程主要是对特定的一些参考标签分组成一个特定的类，在这个类中的参考标签都和待定位标签有着相近的可接收信号强度。可以理解为，若是所有参考标签和待定位标签的位置都比较接近，对的定位会有很大的提高。

在免疫科隆算法中，变异是为了得到免疫力更强、稳定性更好的抗体（虽然参加变异的抗体已经有很高的免疫力）[13]，通过有限制的随机变异，可以让聚类产生的类中参考标签的可接收信号强度与待定位标签的信号强度更加接近。

通过1.2中（1）的过程，可以得到个和待定位标签的信号强度最接近的参考标签，LANDMAR算法此时就利用这些信息进行定位，不过定位的精度并不高。在改进的LANDMARC定位算法中，根据已经得到的k个和待定位标签的信号强度最接近的参考标签，将他们进行一系列的聚类和变异操作（此操作是一个迭代过程），最终会得到较优的参考标签，使得定位的结果更加精确。

1.3.1 聚类过程

从得到的 个和待定位标签的信号强度最接近的参考标签

中选择两个和待定位标签信号强度较接近的参考标签作为聚类的边界 和 ，将它们和待定位标签组成一个类集

。

1.3.2 变异过程

根据在聚类过程中得到的标签集合进行变异。因为聚类的集合是由两个参考标签决定的，根据这两个参考标签的位置信息进行变异，使其坐标发生一些随机的变化（根据参考标签和待定位标签的信号强度，总是沿着待定位标签的方向进行改变）：

且变化的范围在聚类集合之内。最终会得到一个参考标签的集合：

。这些参考标签的信号强度和待定位标签的信号强度的接近程度比初始时的参考标签更加接近！根据最终变异后产生的参考标签进行定位计算。计算的过程和1.2中LANDMARC定位的计算过程相同。

1.4 改进的LANDMARC算法

算法过程如下（ 个阅读器， 个参考标签和 个待定位标签）：

1）分别获得阅读器 的待定位标签的信号强度

2 算法实验与分析

基于Microsoft Windows XP OS，Eclipse 3.2+JDK1.6+SWT Designer

6.0.搭建了定位的软件系统。实验模拟对书库中的书籍进行定位。在模拟实验中，采用8个参考标签，4个阅读器和1个待定位标签。所有的测量都要确保每个标签都可以被阅读器所接收，所有阅读器和标签之间都不存在信息碰撞。

表2和表3显示了实验的一些主要数据：其中，表2中显示了参考标签和阅读器的位置信息，阅读器可以接收到的标签会显示接收到的标签的位置信息以及此标签在此阅读器读取范围内的信号等级，用 表示，其中 分别表示标签的 坐标（单位是cm），level表示了标签的能量等级，否则用null表示。表3显示的是阅读器和待定位标签的位置信息，阅读器可以读取到的待定位标签，用 表示，其中

分别表示接收到的待定位标签的 坐标，level表示了此标签在此阅读器读取范围内的能量等级，否则用null表示。

从表3中可以看出阅读器4读取到标签的能量等级是3，而阅读器1读取到的等级是5，故选择阅读器4读取范围之内的参考标签（tag3，tag7）进行定位计算。

采用不同个数的参考标签进行模拟实验，对不同参考标签产生的结果和LANDMARC产生的结果进行比较分析。表4显示了不同数目的参考标签下不同定位算法的定位结果 分别表示定位到的待定位标签的坐标（待定位标签的实际坐标为166，119）。

表5显示了不同迭代次数下改进的LANDMARC算法的定位结果，分别表示定位到的待定位标签的坐标（待定位标签的实际坐标为166，119）。

总结上述图表，可以得出结论：LANDAMRC算法在室内定位算法中的最大绝对误差为2.3，最小为0.6；改进的LANDMARC定位算法在室内定位算法中的最大误差为1.9，而最小误差可达到0.2。很明显可以看出定位的精度有了很大的提高，尤其是对定位精度要求很高的场合更适合。

3 结论

基于LANDMARC算法，引入了改进的LANDMARC的概念，对LANDMARC定位算法进行了改进，并对其进行了模拟实验。主要创新点在于一般的改进算法都是通过增加参考标签的数目来提高定位的精度，而本文提出的算法在原有参考标签的基础之上，通过结合改进的LANDMARC，产生一些虚拟的和待定位标签信号强度相近的新参考标签，代替原来的参考标签，然后利用这些新参考标签估算待定位标签的位置。实验表明该算法在精度要求很高的室内定位中明显的提高了定位的精度。

上海市科委创新项目（No.08170511300）

上海海事大学校基金（No.2009445654）

参考文献：

[1]吕源、李军，室内环境下定位技术的研究[J].电子测试，2008，4：19-22.

[2]陈聪传、程良伦，区域细化的RFID室内定位算法[J].计算机应用与软件，2011，28（1）：50-52，60．

[3]Yang Wang, Yongqing Fu, ShunQi Si. Passive location based on the DOA and TOA[J], Surveying and mapping engineering, 2008（3）:13-15.

[4]，射频识别室内定位算法研究，2002.

[5]XingPeng Li, YongMei Hu, JiBo Song,etc. Indoor positioning simulation based on Landmarc system[J].The computer engineering and application,2008（27）:209-212.

[6]、范志平，射频识别技术及其在室内定位中的应用[J].计算机应用，2005，25（5）：1205-1208.

[7]Bao Xu；Wang Gang Random Sampling Algorithm in RFID Indoor Location System 2005.

[8]陈颖、张福洪、廖彬彬，一种新的RFID传感器系统的防碰撞算法的研究，传感技术学报，2009（6）.

[9]孙文胜、马建波，基于二进制搜索算法的RFID系统防碰撞算法[J].计算机应用与软件，2010，27（12）：268-269，287.

[10]范志平、邓平、刘林，蜂窝网无线定位[M].北京：电子工业出版社，2002：33-35.

[11]徐凤燕、石鹏、王宗欣，基于参数拟合的距离损耗模型室内定位算法，电路与系统学报，2007（01）.

[12]何清，模糊聚类分析理论与应用研究进展[J].模糊系统与数学，1998，12（2）：89-94.

[13]吴敏毓、刘恭植等，医学免疫学[M].合肥：中国科学技术大学出版社，1999.

作者简介：