改进LANDMARC最近邻居算法在嵌入式系统的实现

张玉茹，谭丽萍，张晓兰，姜海涛，赵 明，李 云，苏晓东

(哈尔滨商业大学，计算机与信息工程学院，哈尔滨150028)

随着人性化计算研究的深入和发展，更多的应用需要知道目标的位置信息，基于位置的服务也越来越多地受到人们的关注.虽然GPS(Global Positioning System，全球定位系统)等定位技术在室外的应用已经非常成熟，但在室内环境中，由于电磁波屏蔽等因素，并不能满足用户的室内定位需求[1].而近些年来，基于无线网络、超声波以及RFID等技术的室内定位方法已经成为室内定位的主要研究方向.其中，RFID(Radio Frequency Identification，无线射频识别)技术是一种非接触式自动识别技术，利用射频信号通过空间耦合的方式实现信息的传递[2]，并可以通过射频信号自动识别单个或多个目标，因此在室内定位中具有较为明显的优势.

随着计算机网络的发展，以及现场总线等技术的广泛使用，串口通讯在各种场合的应用越来越广泛.在某些集中控制场合，现场数据大都是通过串口实现通信[3].

ARM芯片是目前嵌入式系统中最主流的芯片之一，其外围接口芯片支持串口通讯，并且其上可以运行嵌入式操作系统Windows CE、LINUX等，因此ARM在控制领域得到了越来越多的应用.

1 改进的最近邻居算法

LANDMARC系统的最近邻居算法的可扩展性好，能适应较复杂的环境，是较实用的RFID室内定位算法.但在一些封闭环境中，该算法易受信号的多路径效应影响[4]，从而导致其定位精度不高.改进的最近邻居算法在原算法中加入反馈校正值，可以得到更好的定位效果.

改进的最近邻居算法[5－6]的求解过程如下(假设有n个阅读器，m个参考标签和u个待定位标签):

1)定义待定位标签的信号强度矢量是S=(S1，S2，…Sn)，其中表示待定位标签在阅读器 i上的值，i∈(1，n)，对于参考标签，定义相应的信号强度矢量 θ =(θ1，θ2，…θn)，其中 θ 表示参考标签在阅读器i上的值，因此，对于每个待定位标签p，p∈(1，u)，得到与参考标签的欧几里得距离，如表达式(1)所示:

2)通过求得的E值，得到k个与待定位标签信号强度接近的参考标签，可以推算出待定位标签的坐标，如式(2)所示:

其中:(x，y)为待定位标签初始坐标，(xi，yi)分别为k个参考标签的坐标.wi表示的是第i个参考标签的权重，由公式(3)获得

3)得到待定位标签的初始坐标(x，y)后，根据第1)步所得的E值，选择具有最小择具有最小E值的参考标签为关键参考标签，记为Tkey，针对Tkey使用k－最近邻算法，先得到与它具有最小E值的k－1个参考标签坐标，同时加入刚计算所得到待定位标签初始位置坐标，从而得到距离Tkey最近的K个标签的坐标，最终得到Tkey的估计坐标，对比Tkey的真实位置和估计位置，得到坐标反馈校正值(Δx，Δy);

4)将反馈校正值(Δx，Δy)加入到刚才所得的参考标签初始坐标(x0，y0)，得到校正后的待定标签最终的估计坐标(x'，y');

5)通过比较待定位标签的实际坐标和理论所得坐标的比较，可以计算出它们之间的误差值，如式④所示:

其中:(x，y)表示待定位标签的真实坐标，(x'，y')表示待定位标签的估计坐标.

2 改进算法实现

2.1 改进算法在WINCE系统下的实现

WINCE系统是可以加载到ARM处理器上的一种嵌入式操作系统.在WINCE系统下，可以处理由ARM处理器串口设备接收到的外部数据.

在LANDMARC系统中，RFID读卡器将接收到的参考标签和待定位标签的UID号和它们各自对应的信号强度，通过串口发送到ARM处理器的串口端.在WINCE系统下，通过读取ARM处理器串口的数据，将数据进行解析，并通过改进的最近邻居算法处理，最终得到待定位标签的UID号及其位置坐标.

改进算法是用VS2005开发应用程序的形式实现的.首先，基于对话框类建立一个OpenPort()函数通过CreateFile()打开串口，SetCommState()配置串口，如图1所示.

在打开并配置好串口后，函数CommRecvTread(LPVOID lparam)通过ReadFile(pDlg－＞m_hComm，recvBuf，1024，＆dwLength，NULL)接收串口数据并将数据放入recvBuf缓冲区，在成功接收数据后调用回调函数OnCommRecv(CWnd*pWnd，char*buf，int buflen)将接收到的串口数据通过PostMessage(WM_RECV_SERIAL_DATA，WPARAM(pRecvBuf)，buflen)发送给与 WM_RECV_SERIAL_DATA消息关联的串口接收数据处理函 数 OnRecvSerialData(WPARAM wParam，LPARAM lParam)，在该函数中对接收到的数据进行解析，提取待定位标签的UID号及其信号强度，并用C语言编程实现改进的定位算法，最终处理结果如图2所示.

图1 WINCE下串口配置程序

图2 WINCE下算法处理结果

2.2 改进算法在LINUX系统下的实现

嵌入式LINUX系统也是一种可以加载到ARM处理器上的嵌入式操作系统，因其源码开放，故日益成为主流的嵌入式操作系统之一.

在加载LINUX操作系统的ARM处理器上，LINUX系统不仅可以读取ARM处理器串口中的数据，同时可以对串口中的数据进行解析处理，因此改进的最近邻居算法也是可以在LINUX操作系统下实现的.

在LINUX系统下，设备的操作如同普通文件的操作一样，所以打开ARM处理器的串口设备可以使用open()函数，该函数的返回值为－1时，说明打开串口设备失败.在打开串口设备后，需要对串口进行配置，以使其能够正确接收到外部数据，对串口的配置包括保存原先串口配置、设置波特率、字符大小、奇偶校验位、停止位、本地连接和接收使能、设置最少字符和等待时间、清空串口缓冲以及激活最新配置使最新的串口配置生效等，当外部有数据发送到ARM处理器的串口设备时，LINUX操作系统需要执行读串口操作来获得串口数据.和读普通文件一样，使用read()函数即可，该函数将读取到的串口数据放入缓冲区buff中，如图3所示.

图3 LINUX下串口配置程序

接下来对接收缓冲区的数据进行解析，解析出改进后算法所需的数据，包括UID号和待定位标签的信号强度值，将解析数据所得的有用的数据应用到算法程序中，通过C语言编程改进后算法，最终得到待定位标签的位置坐标以及待定标签的UID号.

在编写完打开串口、配置串口、读取串口、解析串口数据、改进算法程序后，在LINUX系统中还需要编写MAKEFILE文件，如图4所示.使得上述编写的程序可以通过arm－linux－gcc编译成可执行程序，运行在ARM处理设备中.

图5中，x值为标签所在位置的横坐标值，y值为标签所在位置的纵坐标值，与WINCE系统下算法处理结果是一样的.

3 结语

本文在介绍改进后最近邻居算法的基础上，给出改进后算法在嵌入式操作系统WINCE及LINUX中实现的步骤，包括了WINCE操作系统下对串口设备的配置、读操作以及回调函数、数据处理函数以及算法处理的编写，操作系统下对串口设备的配置、读操作、数据算法处理以及MAKEFILE文件的编写.最终开发了可在 WINCE系统和LINUX系统下执行的算法应用程序.从而给改进后算法被应用于基于ARM的RFID室内定位系统提供了依据.

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

[2] 朱凤娟.射频识别(RFID)技术的室内定位算法研究[D].广州:华南理工大学，2010.

[3] 王海洋，陈美君.基于ARM9的串口扩展的设计[J].计算机与现代化，2008(12):84－87.

[4] KYUWON H，SUNG H C.Advanced LANDMARC with adaptive k－nearest algorithm for RFID location system[C]//Wireless and Optical Communications Conference(WOCC) ，[S.l.]:[s.n.]2010(19):1 －5.

[5] ZHANG Y R，TAN L P，JIANG H T.The Simulation and Improved K－nearest Neighbors Algorithm of LANDMARC for Books Positioning[C]//2012 International Conference on Measurement，Information and Control(MIC)，[S.l.]:[s.n.]，2012(5):410－414.

[6] 张玉茹，陈德龙，李彬彬.动态帧时隙算法的研究与改进[J].哈尔滨商业大学学报:自然科学版，2011，27(6):834－836.