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

李寶山 岳 康

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

李寶山 岳 康

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

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

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

0 引 言

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

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

1 LANDMARC定位算法

1.1 算法的定位原理及步驟

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

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

(1)

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

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

(2)

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

(3)

1.2 性能分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2) 計(jì)算初次定位坐標(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 錯(cuò)選標(biāo)簽判別圖

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

(7)

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

(8)

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

(9)

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

(10)

則B為無(wú)誤的鄰居標(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}。

此時(shí)求出修正后的鄰居標(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)可計(jì)算得修正的待定位標(biāo)簽m′的坐標(biāo)。

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

2.2 修正算法定位流程

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

圖3 修正算法定位流程圖

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

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

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

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

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

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

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

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

圖6 平均誤差對(duì)比圖

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

圖7 累積誤差對(duì)比圖

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

3 結(jié) 語(yǔ)

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

[1] 邱奉美,游曉鵬,李懷忠.幾種無(wú)需測(cè)距定位算法定位性能仿真研究[J].計(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的制造車(chē)間實(shí)時(shí)定位算法研究[J].機(jī)械設(shè)計(jì)與制造工程,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] 楊輝,蔡堅(jiān)勇,高杰星.基于LANDMARC定位算法復(fù)雜度的分區(qū)算法改進(jìn)[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2013,22(5):103-106,121.

[9] 徐輝霞,包建軍,譚達(dá)克.基于RFID的LANDMARC井下定位技術(shù)研究[J].工礦自動(dòng)化,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)域：射頻識(shí)別系統(tǒng)及應(yīng)用。岳康，碩士生。

TP39

A

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