改進LANDMARC最近鄰居算法在嵌入式系統(tǒng)的實現(xiàn)

張玉茹，譚麗萍，張曉蘭，姜海濤，趙 明，李 云，蘇曉東

(哈爾濱商業(yè)大學，計算機與信息工程學院，哈爾濱150028)

隨著人性化計算研究的深入和發(fā)展，更多的應用需要知道目標的位置信息，基于位置的服務也越來越多地受到人們的關注.雖然GPS(Global Positioning System，全球定位系統(tǒng))等定位技術在室外的應用已經非常成熟，但在室內環(huán)境中，由于電磁波屏蔽等因素，并不能滿足用戶的室內定位需求[1].而近些年來，基于無線網絡、超聲波以及RFID等技術的室內定位方法已經成為室內定位的主要研究方向.其中，RFID(Radio Frequency Identification，無線射頻識別)技術是一種非接觸式自動識別技術，利用射頻信號通過空間耦合的方式實現(xiàn)信息的傳遞[2]，并可以通過射頻信號自動識別單個或多個目標，因此在室內定位中具有較為明顯的優(yōu)勢.

隨著計算機網絡的發(fā)展，以及現(xiàn)場總線等技術的廣泛使用，串口通訊在各種場合的應用越來越廣泛.在某些集中控制場合，現(xiàn)場數(shù)據(jù)大都是通過串口實現(xiàn)通信[3].

ARM芯片是目前嵌入式系統(tǒng)中最主流的芯片之一，其外圍接口芯片支持串口通訊，并且其上可以運行嵌入式操作系統(tǒng)Windows CE、LINUX等，因此ARM在控制領域得到了越來越多的應用.

1 改進的最近鄰居算法

LANDMARC系統(tǒng)的最近鄰居算法的可擴展性好，能適應較復雜的環(huán)境，是較實用的RFID室內定位算法.但在一些封閉環(huán)境中，該算法易受信號的多路徑效應影響[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)后，根據(jù)第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 改進算法實現(xiàn)

2.1 改進算法在WINCE系統(tǒng)下的實現(xiàn)

WINCE系統(tǒng)是可以加載到ARM處理器上的一種嵌入式操作系統(tǒng).在WINCE系統(tǒng)下，可以處理由ARM處理器串口設備接收到的外部數(shù)據(jù).

在LANDMARC系統(tǒng)中，RFID讀卡器將接收到的參考標簽和待定位標簽的UID號和它們各自對應的信號強度，通過串口發(fā)送到ARM處理器的串口端.在WINCE系統(tǒng)下，通過讀取ARM處理器串口的數(shù)據(jù)，將數(shù)據(jù)進行解析，并通過改進的最近鄰居算法處理，最終得到待定位標簽的UID號及其位置坐標.

改進算法是用VS2005開發(fā)應用程序的形式實現(xiàn)的.首先，基于對話框類建立一個OpenPort()函數(shù)通過CreateFile()打開串口，SetCommState()配置串口，如圖1所示.

在打開并配置好串口后，函數(shù)CommRecvTread(LPVOID lparam)通過ReadFile(pDlg－＞m_hComm，recvBuf，1024，＆dwLength，NULL)接收串口數(shù)據(jù)并將數(shù)據(jù)放入recvBuf緩沖區(qū)，在成功接收數(shù)據(jù)后調用回調函數(shù)OnCommRecv(CWnd*pWnd，char*buf，int buflen)將接收到的串口數(shù)據(jù)通過PostMessage(WM_RECV_SERIAL_DATA，WPARAM(pRecvBuf)，buflen)發(fā)送給與 WM_RECV_SERIAL_DATA消息關聯(lián)的串口接收數(shù)據(jù)處理函 數(shù) OnRecvSerialData(WPARAM wParam，LPARAM lParam)，在該函數(shù)中對接收到的數(shù)據(jù)進行解析，提取待定位標簽的UID號及其信號強度，并用C語言編程實現(xiàn)改進的定位算法，最終處理結果如圖2所示.

圖1 WINCE下串口配置程序

圖2 WINCE下算法處理結果

2.2 改進算法在LINUX系統(tǒng)下的實現(xiàn)

嵌入式LINUX系統(tǒng)也是一種可以加載到ARM處理器上的嵌入式操作系統(tǒng)，因其源碼開放，故日益成為主流的嵌入式操作系統(tǒng)之一.

在加載LINUX操作系統(tǒng)的ARM處理器上，LINUX系統(tǒng)不僅可以讀取ARM處理器串口中的數(shù)據(jù)，同時可以對串口中的數(shù)據(jù)進行解析處理，因此改進的最近鄰居算法也是可以在LINUX操作系統(tǒng)下實現(xiàn)的.

在LINUX系統(tǒng)下，設備的操作如同普通文件的操作一樣，所以打開ARM處理器的串口設備可以使用open()函數(shù)，該函數(shù)的返回值為－1時，說明打開串口設備失敗.在打開串口設備后，需要對串口進行配置，以使其能夠正確接收到外部數(shù)據(jù)，對串口的配置包括保存原先串口配置、設置波特率、字符大小、奇偶校驗位、停止位、本地連接和接收使能、設置最少字符和等待時間、清空串口緩沖以及激活最新配置使最新的串口配置生效等，當外部有數(shù)據(jù)發(fā)送到ARM處理器的串口設備時，LINUX操作系統(tǒng)需要執(zhí)行讀串口操作來獲得串口數(shù)據(jù).和讀普通文件一樣，使用read()函數(shù)即可，該函數(shù)將讀取到的串口數(shù)據(jù)放入緩沖區(qū)buff中，如圖3所示.

圖3 LINUX下串口配置程序

接下來對接收緩沖區(qū)的數(shù)據(jù)進行解析，解析出改進后算法所需的數(shù)據(jù)，包括UID號和待定位標簽的信號強度值，將解析數(shù)據(jù)所得的有用的數(shù)據(jù)應用到算法程序中，通過C語言編程改進后算法，最終得到待定位標簽的位置坐標以及待定標簽的UID號.

在編寫完打開串口、配置串口、讀取串口、解析串口數(shù)據(jù)、改進算法程序后，在LINUX系統(tǒng)中還需要編寫MAKEFILE文件，如圖4所示.使得上述編寫的程序可以通過arm－linux－gcc編譯成可執(zhí)行程序，運行在ARM處理設備中.

圖5中，x值為標簽所在位置的橫坐標值，y值為標簽所在位置的縱坐標值，與WINCE系統(tǒng)下算法處理結果是一樣的.

3 結語

本文在介紹改進后最近鄰居算法的基礎上，給出改進后算法在嵌入式操作系統(tǒng)WINCE及LINUX中實現(xiàn)的步驟，包括了WINCE操作系統(tǒng)下對串口設備的配置、讀操作以及回調函數(shù)、數(shù)據(jù)處理函數(shù)以及算法處理的編寫，操作系統(tǒng)下對串口設備的配置、讀操作、數(shù)據(jù)算法處理以及MAKEFILE文件的編寫.最終開發(fā)了可在 WINCE系統(tǒng)和LINUX系統(tǒng)下執(zhí)行的算法應用程序.從而給改進后算法被應用于基于ARM的RFID室內定位系統(tǒng)提供了依據(jù).

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

[2] 朱鳳娟.射頻識別(RFID)技術的室內定位算法研究[D].廣州:華南理工大學，2010.

[3] 王海洋，陳美君.基于ARM9的串口擴展的設計[J].計算機與現(xiàn)代化，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] 張玉茹，陳德龍，李彬彬.動態(tài)幀時隙算法的研究與改進[J].哈爾濱商業(yè)大學學報:自然科學版，2011，27(6):834－836.