LANDMARC定位算法的修正與優(yōu)化

李寶山 岳 康

LANDMARC定位算法的修正與優(yōu)化

李寶山 岳 康

(內(nèi)蒙古科技大學(xué)信息工程學(xué)院 內(nèi)蒙古 包頭 014010)

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

RFID 室內(nèi)定位 LANDMARC算法 修正算法

0 引 言

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

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

1 LANDMARC定位算法

1.1 算法的定位原理及步驟

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

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

(1)

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

(5) 求得K個參考標(biāo)簽對應(yīng)的權(quán)重系數(shù)值wk：

(2)

(6) 由權(quán)重質(zhì)心法求得待定位標(biāo)簽的坐標(biāo)為：

(3)

1.2 性能分析

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

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

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

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

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

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

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

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

2 改進(jìn)的LANDMARC定位算法

2.1 改進(jìn)算法思想

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

圖1 修正算法的標(biāo)簽布放及定位原理

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

(1) 根據(jù)LANDMARC定位算法求得最近鄰標(biāo)簽A、B、C、D，由此四個鄰居標(biāo)簽結(jié)合加權(quán)質(zhì)心算法得到待定位標(biāo)簽初次定位坐標(biāo)m′(xm′,ym′)。

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

(4)

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

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

dmax=dBm′

(5)

dmax

(6)

圖2 錯選標(biāo)簽判別圖

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

(7)

則由圖2知，標(biāo)簽B必在Q1處，m′必在ANCDA內(nèi)，此時存在錯選鄰居標(biāo)簽B。若存在式：

(8)

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

(9)

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

(10)

則B為無誤的鄰居標(biāo)簽。

若 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}。

此時求出修正后的鄰居標(biāo)簽坐標(biāo)。

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

(11)

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

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

2.2 修正算法定位流程

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

圖3 修正算法定位流程圖

2.3 改進(jìn)算法的仿真測試

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

圖4 定位系統(tǒng)布置圖

針對各種不同的情況，分析其對應(yīng)環(huán)境下的定位結(jié)果，并用MATLAB軟件進(jìn)行定位結(jié)果的仿真。實驗結(jié)果如下：

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

圖5 錯選鄰居標(biāo)簽概率對比圖

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

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

圖6 平均誤差對比圖

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

圖7 累積誤差對比圖

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

3 結(jié) 語

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

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

[2] 趙剛.基于RFID的室內(nèi)定位算法研究[D].南昌:南昌航空大學(xué),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] 閆振強(qiáng),郭宇,張小瑞.一種基于RFID的制造車間實時定位算法研究[J].機(jī)械設(shè)計與制造工程,2014,43(3):52-56.

[5] 潘爵雨.基于RFID的室內(nèi)定位技術(shù)及其應(yīng)用研究[D].廣州:華南理工大學(xué),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定位算法復(fù)雜度的分區(qū)算法改進(jìn)[J].計算機(jī)系統(tǒng)應(yīng)用,2013,22(5):103-106,121.

[9] 徐輝霞,包建軍,譚達(dá)克.基于RFID的LANDMARC井下定位技術(shù)研究[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。李寶山，教授，主研領(lǐng)域：射頻識別系統(tǒng)及應(yīng)用。岳康，碩士生。

TP39

A

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