LANDMARC定位算法的修正與優化

李寶山 岳 康

LANDMARC定位算法的修正與優化

李寶山 岳 康

(內蒙古科技大學信息工程學院 內蒙古 包頭 014010)

LANDMARC作為基于RFID技術室內定位的一項傳統定位算法，在相關定位系統的研究中得到了廣泛的應用。然而在實際的定位和應用過程中，LANDMARC定位算法仍存在著一些缺點和不足。針對算法定位過程中錯選鄰居標簽概率較高造成誤差較大的情況,提出一種基于LANDMARC的修正與優化算法，算法主要通過幾何運算比較來排除并校正錯選的鄰居標簽。實驗結果表明，在不同的定位環境條件下，修正與優化后算法其錯選鄰居標簽的概率大大降低，結果使定位誤差有了明顯的減小。

RFID 室內定位 LANDMARC算法 修正算法

0 引 言

基于RFID技術的室內定位算法可分為兩大類：基于測距的定位算法和與距離無關的定位算法?；跍y距的定位算法其基本思想是利用信號傳播的時間、接收信號的角度或強度信息來計算出相關的距離信息，然后通過三邊測量法、三角測量法、最小二乘法或最大似然估計法來計算估計出定位目標的位置。典型的測距方法有基于信號到達角(AOA)法、基于信號到達時間(TOA)法、基于信號到達時間差 (TDOA)法以及基于接收信號強度 (RSSI)法。與測距無關的定位算法可分為質心、Dv-Hop、凸規劃、APS、APIT以及SeRLoc法等[1-3]?；跍y距的定位算法往往比與測距無關的定位算法具有更高的定位精度，但是由于前者在定位時需要復雜精確的測距及計算，這往往使得定位過程過于復雜，定位的適時性降低，而后者卻不需要大量繁瑣的測距和計算過程。

LANDMARC算法結合了基于測距和與測距無關的定位算法。首先利用RSSI信息求出最近鄰居標簽，然后根據加權質心算法求解待定位標簽的位置坐標[2]。但LANDMARC算法典型的缺點是由于定位環境影響，信號在傳播過程中會發生各種情況的反射、衍射和多徑效應。這樣就造成LANDMARC算法易錯選鄰居標簽[4]。大量的實驗研究表明LANDMARC算法錯選鄰居標簽的概率高達65%，這樣必然使得定位結果誤差較大，定位精度降低[5]。針對此問題本文提出一種LADMARC算法優化和修正方法，通過理論分析與實驗驗證，修正與優化后算法的定位精度有明顯的提高和改善。

1 LANDMARC定位算法

1.1 算法的定位原理及步驟

LANDMARC算法作為一種基于有源RFID技術的室內定位算法[6]，其基本原理思想是利用標簽的信號強度信息(RSS)找到與待定位標簽信號強度值相近的K個鄰居參考標簽，然后利用權重質心法求出待定位標簽的位置[7]。典型的基于LANDMARC算法的定位系統中有若干讀寫器和參考標簽，一個或多個待定位標簽，且參考標簽均按照正方形的規則進行布放[8, 9]，其定位步驟如下：

(3) 計算待定位標簽j與參考標簽i之間的歐幾里德距離Eij：

(1)

(4) 根據k近鄰算法，找到Eij中k個最小值及其對應的參考標簽的位置坐標(xp，yp)，其中0

(5) 求得K個參考標簽對應的權重系數值wk：

(2)

(6) 由權重質心法求得待定位標簽的坐標為：

(3)

1.2 性能分析

LANDMARC定位算法并沒有將接收到的RSSI值轉化為距離信息，而是采用位置固定的參考標簽來輔助定位，這樣就克服了傳統的基于RSSI測距定位算法的不足。但傳統的LANDMARC定位算法仍然存在著大量的缺點和不足[9]，可總結為以下幾點：

(1) 算法的定位精度與參考標簽和閱讀器的布放密度和布放位置密切相關，過低或過高的密度都不會達到最佳的定位效果；

(2) 最近鄰居K值的選取是一個關鍵因素；

(3) LANDMARC定位算法不能很好地克服信號在傳播過程中遇到的多徑、衍射、反射等現象；

(4) 當待定位標簽位于參考標簽的布放區域邊緣時，定位精度明顯下降；

(5) 定位時要檢測并比較每個參考標簽與待定位標簽的值并選出K個近鄰標簽，這樣使得算法的計算量大大增加；

(6) 大量的實驗研究表明，在K個鄰居標簽的選取過程中，定位算法錯選鄰居標簽的概率高達65%。

針對上述LANDMARC算法存在的缺點和問題，相關的學者已經提出了許多對應的優化方案和解決方法。比如提出對參考標簽進行等邊三角形布放或正方形布放；通過適當增加參考標簽的數量來提高定位精度；針對不同的定位環境通過實驗選擇適當數量的閱讀器和最近鄰居標簽數量；對處于邊緣的待定位標簽定位精度偏低的問題提出了BVIRE算法；針對定位的計算冗余問題，提出了區域劃分等方法。雖然這一系列的改進算法在一定范圍內提高了算法的定位精度，但在進行定位過程中其錯選鄰居標簽概率較高的問題并沒有得到很好的解決。

2 改進的LANDMARC定位算法

2.1 改進算法思想

利用LANDMARC算法進行定位，造成定位精度較低的一個重要原因是由于定位環境和信號傳播特性的影響，K鄰居標簽的錯選概率較高。改進的LANDMARC定位算法在已有的改進算法基礎上對參考標簽的擺放位置和相互間的幾何關系運用數學理論進行相關分析，找到有效降低由于錯選鄰居標簽造成的定位誤差影響的方法。其標簽布放和定位方法如圖1所示。

圖1 修正算法的標簽布放及定位原理

如圖1所示，假設參考標簽以正方形進行布放，正方形的邊長為a，最佳鄰居標簽個數K值為4，最佳讀寫器個數為4，其擺放位置在定位區域的四個頂角上。根據LANDMARC算法，理想的情況下參考標簽A、B′、C、D信號強度與待定位標簽m信號強度的歐氏距離最小，即其與待定位標簽的真實坐標位置最接近。而在實際的定位過程中，由于信號傳播特性和傳輸路徑的影響，信號在傳播過程中易出現多徑、反射、衍射等現象，使得定位系統易錯選鄰居標簽。在最近鄰居標簽的選取上，相關研究表明其錯選一個鄰居標簽的概率遠遠高于其錯選多個標簽的概率，所以本文只對出現一個錯選鄰居標簽進行分析研究。假設最近鄰居標簽B′被錯選為鄰居標簽,那么定位結果便由參考標簽A、B、C、D決定，這樣就會造成定位結果出現較大的偏差。對于此情況，改進的算法主要步驟如下：

(1) 根據LANDMARC定位算法求得最近鄰標簽A、B、C、D，由此四個鄰居標簽結合加權質心算法得到待定位標簽初次定位坐標m′(xm′,ym′)。

(2) 計算初次定位坐標m′與最近鄰居標簽A，B，C，D之間的幾何距離分別為dAm′、dBm′、dCm′、dDm′。其中鄰居標簽A與初次定位坐標m′之間的距離可表示為：

(4)

同理可求得距離dBm′、dCm′、dDm′。

(3) 比較初次定位標簽與各鄰居標簽之間的距離，求出最大的距離dmax。假設有：

dmax=dBm′

(5)

dmax

(6)

圖2 錯選標簽判別圖

則由圖2知，標簽B必在Q2處，m′必在AQ2CPA內,此時不存在錯選的鄰居標簽，B即為B′。若存在式：

(7)

則由圖2知，標簽B必在Q1處，m′必在ANCDA內，此時存在錯選鄰居標簽B。若存在式：

(8)

則由圖2知，若B在Q1處，m′必在AQ2NA內，若B在Q2處，即B為B′時，m′必在APCDA內。為了確定是否存在誤選標簽可分兩種情況進行判斷。比較參考標簽B與鄰居參考標簽A、C、D之間的距離dBA、dBC、dBD并找出最大值,判斷dBmax是否滿足式：

(9)

若滿足，則B為錯選的鄰居標簽。反之，若dBmax滿足式：

(10)

則B為無誤的鄰居標簽。

若 xB≤min{xA，xC，xD}，則有 xB′=min{xA，xC，xD}；若 xB≥max{xA，xC，xD}，則有 xB′=max{xA，xC，xD}；若 yB≤min{yA，yC，yD}，則有 yB′=min{yA，yC，yD}；若 yB≥max{yA，yC，yD}，則有 yB′=max{yA，yC，yD}。

此時求出修正后的鄰居標簽坐標。

由修正后鄰居標簽A、B′、C、D,由加權質心算法求得修正的待定位標簽坐標m″(xm″，ym″)：

(11)

其中修正后的鄰居標簽B′的權重為wB′=wB。由式(11)可計算得修正的待定位標簽m′的坐標。

(5) 同理，若錯選鄰居標簽為A、C、D同理采用此方法來修正待定位標簽的坐標。

2.2 修正算法定位流程

修正算法定位流程圖如圖3所示。

圖3 修正算法定位流程圖

2.3 改進算法的仿真測試

為了驗證修正后算法具有更加優良的定位精度，本文采用433 MHz的有源RFID搭建室內定位系統，定位系統中選用4個讀寫器、16個參考標簽和若干個待定位標簽。參考標簽按正方形(邊長為a單位為m)規則進行布放。讀寫器分別放置于定位區域的四個頂角，在定位區域內隨機擺放若干桌椅等障礙物來模擬定位的非理想環境，定位時由若干人在定位區域內走動來模擬定位環境的隨機性，定位系統和障礙物布放如圖4所示。

圖4 定位系統布置圖

針對各種不同的情況，分析其對應環境下的定位結果，并用MATLAB軟件進行定位結果的仿真。實驗結果如下：

(1) 參考標簽以正方形規則布放(如圖4所示)，在同一a值下，對15個待定位標簽分別運用LANDMARC定位算法和修正后算法進行10次定位實驗并分析計算錯選鄰居標簽的標簽數及錯選標簽的概率。分別選用不同的a值，計算并分析統計其對應條件下錯選鄰居標簽的概率。兩種算法下錯選鄰居標簽概率比較圖5所示。

圖5 錯選鄰居標簽概率對比圖

(2) 正方形邊長a取2時，隨機定位15個待定位標簽，其擺放位置如圖4所示。分別運用LANDMARC定位算法和修正后算法計算15個待定位標簽的坐標。在同樣的定位環境下，在不同時間內進行10次重復定位實驗并記錄相應的定位坐標。然后分別求得15個待定位標簽在10次定位過程的平均定位誤差。算法修正前后平均定位誤差對比如表1、圖6所示。

表1 算法修正前后誤差比較

圖6 平均誤差對比圖

(3) 正方形邊長a取2時，在圖4所示的定位系統環境中，對30個不同位置的待定位標簽進行1次定位實驗，計算并分析算法修正前后其累積誤差分布關系，如圖7所示。

圖7 累積誤差對比圖

分析上述實驗，由圖5得修正后算法其錯選鄰居標簽的概率比LANDMARC算法有了明顯的提高；由表1和圖6得修正后算法的定位誤差離散度較小，其平均定位誤差減小約44%，特別是在待定位標簽位于障礙物密集的情況下，修正后的算法比LANDMARC算法具有更高的定位精度，如標簽號為3、10、12的待定位標簽定位結果所示；由圖7可以看出，修正后算法誤差范圍集中在0.6～0.8 m，誤差小于1 m的概率約為86%，對比LANDMARC算法其定位穩定性有了很大的提高。

3 結 語

LANDMARC是基于有源RFID室內定位系統的經典算法，在LANDMARC算法中最近鄰居標簽的選取對系統的最終定位精度有較大的影響。本文針對傳統的LANMARC算法在定位過程中易錯選鄰居標簽的問題，提出了一種LANDMARC修正算法。算法基本原理是根據經典的LANDMARC算法求得定位坐標，然后由初次定位坐標和其與參考標簽的幾何關系，計算并找出明顯出錯的鄰居標簽和修正后的鄰居標簽，然后進行二次坐標定位求出修正的待測標簽位置。

[1] 邱奉美,游曉鵬,李懷忠.幾種無需測距定位算法定位性能仿真研究[J].計算機仿真,2014,31(4):285-289,363.

[2] 趙剛.基于RFID的室內定位算法研究[D].南昌:南昌航空大學,2013.

[3] Ali Motamedi,Mohammad Mostafa Soltani,Amin Hammad.Localization of RFID-equipped assets during the operation phase of facilities[J].Advanced Engineering Informatics,2013,27(8):566-579.

[4] 閆振強,郭宇,張小瑞.一種基于RFID的制造車間實時定位算法研究[J].機械設計與制造工程,2014,43(3):52-56.

[5] 潘爵雨.基于RFID的室內定位技術及其應用研究[D].廣州:華南理工大學,2012.

[6] Jiang T,Huang Y,Wang Y.Study on improved LANDMARC node localization algorithm[M].Beijing,China:Springer Verlag,2012.

[7] Yeh C,Su S.Enhance LANDMARC from the fundamentals[C]//Tainan,Taiwan:IEEE Computer Society,2013：23-27.

[8] 楊輝,蔡堅勇,高杰星.基于LANDMARC定位算法復雜度的分區算法改進[J].計算機系統應用,2013,22(5):103-106,121.

[9] 徐輝霞,包建軍,譚達克.基于RFID的LANDMARC井下定位技術研究[J].工礦自動化,2014,40(5):18-21.

AMENDMENT AND OPTIMISATION OF LANDMARC LOCALISATION ALGORITHM

Li Baoshan Yue Kang

(SchoolofInformationEngineering,InnerMongoliaUniversityofScienceandTechnology,Baotou014010,InnerMongolia,China)

As a traditional localisation algorithm based on RFID indoor localisation technique, LANDMARC has been widely used in the research of related positioning system. However, in practical processes of positioning and application, LANDMARC localisation algorithm still has some shortcomings and deficiencies, typically, in the process of locating, the wrong selection of neighbour label has higher probability, and causes lower accuracy. Aiming at this problem, this paper proposes a LANDMARC-based amendment and optimisation algorithm. The algorithm eliminates and corrects the wrongly selected neighbour labels mainly through geometrical calculation comparison. Experimental results show that in different positioning environment conditions, the amended and optimised algorithm has a much lower probability in choosing wrong neighbour labels. As the result, the positioning error is reduced obviously.

RFID Indoor localisation LANDMARC algorithm Amendment algorithm

2014-11-03。李寶山，教授，主研領域：射頻識別系統及應用。岳康，碩士生。

TP39

A

10.3969/j.issn.1000-386x.2016.04.024