基于無源RFID的最小包容圓自適應(yīng)定位法

邊江南，劉洪武

(南昌航空大學(xué)信息工程學(xué)院，江西 南昌 330063)

0 引言

無線傳感器網(wǎng)絡(luò)的飛速發(fā)展使得人們對(duì)室內(nèi)定位的需求不斷增長。RFID定位技術(shù)具有非接觸式和非視距操作的特點(diǎn)，除了安全性和靈敏度很高以外，還可利用標(biāo)簽傳遞大量的信息，因此它被廣泛應(yīng)用在室內(nèi)定位領(lǐng)域。

LANDMARC定位法[1]利用參考標(biāo)簽輔助定位的方法可以減少閱讀器的數(shù)量，降低成本的同時(shí)又可以提高定位精度。通過K臨近法來建立信號(hào)強(qiáng)度和能量級(jí)別之間的關(guān)系，可以降低環(huán)境因素對(duì)系統(tǒng)定位性能的影響。文獻(xiàn)[2]將LANDMARC定位法中的有源參考標(biāo)簽用成本更低廉的無源參考標(biāo)簽取代，使得在不增加系統(tǒng)成本的情況下增加參考標(biāo)簽的數(shù)量，提高了定位精度。文獻(xiàn)[3]對(duì)參考標(biāo)簽布設(shè)的拓?fù)浣Y(jié)構(gòu)進(jìn)行分析，得出了一種減小定位區(qū)域的參考標(biāo)簽布設(shè)方法，可以有效提高定位的精度。文獻(xiàn)[4]的自適應(yīng)K臨近算法提高了系統(tǒng)對(duì)環(huán)境的應(yīng)變能力，使得定位效果更加穩(wěn)定可靠。

在K臨近法消除一定原因造成的基礎(chǔ)上，隨機(jī)誤差使得定位的估計(jì)位置隨環(huán)境變化呈現(xiàn)出隨機(jī)分布的現(xiàn)象，本文提出的利用最小包容圓[6]的圓心估計(jì)待測定位置的方法可以有效地減小這種隨機(jī)誤差，進(jìn)一步提高定位的精確度。

1 LANDMARC定位法

1.1 LANDMARC 原理

LANDMARC(Location Identification Based on Dynamic Active RFID Calibration)是基于有源RFID參考標(biāo)簽輔助定位的一種室內(nèi)定位法。其閱讀器、參考標(biāo)簽和待測標(biāo)簽的布設(shè)如圖1所示。

圖1 LANDMARC系統(tǒng)閱讀器和標(biāo)簽布設(shè)結(jié)構(gòu)

假設(shè)有n個(gè)閱讀器，m個(gè)參考標(biāo)簽，u個(gè)待測標(biāo)簽。對(duì)于同一個(gè)參考標(biāo)簽，定義讀寫器測得的待測標(biāo)簽的信號(hào)強(qiáng)度矢量為:

對(duì)于每個(gè)待測標(biāo)簽p，p∈(1，u)，信號(hào)強(qiáng)度的歐式距離rj為:

然后用K臨近算法計(jì)算待測標(biāo)簽的坐標(biāo)。該算法從極限原理的角度出發(fā)，用一個(gè)樣本在特征空間中的K個(gè)最相似樣本來判別該樣本的所屬類別。對(duì)于待測標(biāo)簽的坐標(biāo)來說，以參考標(biāo)簽的坐標(biāo)為特征空間，選擇信號(hào)強(qiáng)度特征與之最相似的K個(gè)點(diǎn)來判別待測標(biāo)簽所在位置:

其中加權(quán)值wi為:

1.2 LANDMARC算法的評(píng)估

如圖1所示，LANDMARC算法沒有對(duì)參考標(biāo)簽布設(shè)的拓?fù)浣Y(jié)構(gòu)進(jìn)行分析，而實(shí)際上它的拓?fù)浣Y(jié)構(gòu)對(duì)定位精度有一定的影響。LANDMARC算法在運(yùn)用K臨近法選取臨近參考標(biāo)簽時(shí)的K值是由大量對(duì)現(xiàn)時(shí)實(shí)驗(yàn)環(huán)境的測試來確定的，這種方法對(duì)于復(fù)雜變動(dòng)的實(shí)驗(yàn)環(huán)境存在著很大的局限性。LANDMARC算法可以配合其它優(yōu)化算法使得定位精度得以進(jìn)一步提高。

2 自適應(yīng)定位法

本文所采用的自適應(yīng)RFID定位法用無源RFID參考標(biāo)簽在室內(nèi)環(huán)境內(nèi)布設(shè)，采用優(yōu)化的拓?fù)浣Y(jié)構(gòu)，構(gòu)成定位系統(tǒng)的已知固定條件，然后以原始LANDMARC算法為基礎(chǔ)，使用自適應(yīng)K臨近法進(jìn)行K值的選取，來估計(jì)待測標(biāo)簽的坐標(biāo)，使得算法具有智能性，再將多次估計(jì)的坐標(biāo)點(diǎn)所構(gòu)成的點(diǎn)集用最小圓包容算法找到其點(diǎn)集的最小包容圓所在的圓心，來作為最終的待測標(biāo)簽的估計(jì)坐標(biāo)。自適應(yīng)定位法的系統(tǒng)構(gòu)成如圖2所示。

圖2 自適應(yīng)定位法系統(tǒng)構(gòu)成

2.1 拓?fù)浣Y(jié)構(gòu)優(yōu)化

LANDMARC定位法利用參考標(biāo)簽輔助定位，其參考標(biāo)簽的布設(shè)結(jié)構(gòu)稱之為參考標(biāo)簽的拓?fù)浣Y(jié)構(gòu)。一般要在計(jì)算待測點(diǎn)坐標(biāo)前選取K個(gè)最鄰近點(diǎn)來輔助估計(jì)結(jié)果。LANDMARC定位法的參考標(biāo)簽拓?fù)浣Y(jié)構(gòu)如圖3中的矩形網(wǎng)絡(luò)形式所示。定義由所選取的最鄰近的K個(gè)參考標(biāo)簽所圍成區(qū)域?yàn)榇郎y標(biāo)簽的定位誤差分布區(qū)域。文獻(xiàn)[3]中分析其矩形的形狀和定位誤差分布區(qū)域以及定位精度三者的關(guān)系得出兩點(diǎn)結(jié)論:(1)當(dāng)所選定的K值確定后，存在爭議的最鄰近點(diǎn)的替換不能改變待測標(biāo)簽的誤差分布區(qū)域大小。如當(dāng)K值為4，選擇最鄰近的4個(gè)點(diǎn)是BOFH或HODF兩種方案的定位誤差分布區(qū)域是相同的;(2)隨著矩形邊長的增加，待測標(biāo)簽的定位誤差分布區(qū)域也相對(duì)增大，使得定位精確度降低。當(dāng)矩形為正方形，K值為4時(shí)，定位誤差分布區(qū)域有2/3的概率為矩形，另外1/3概率為等腰三角形。

圖3 兩種參考標(biāo)簽的拓?fù)浣Y(jié)構(gòu)

若參考標(biāo)簽的拓?fù)浣Y(jié)構(gòu)布設(shè)成如圖3中的正三角形網(wǎng)絡(luò)的形式，毫無疑問與待測標(biāo)簽P最鄰近的3個(gè)點(diǎn)不存在爭議，定位誤差分布區(qū)域?yàn)镺FE圍成的三角區(qū)域。由于不會(huì)增加待測標(biāo)簽的定位誤差分區(qū)區(qū)域，所以可以相對(duì)提高定位精確度。

2.2 自適應(yīng)K臨近算法

基于LANDMARC定位法的原始K臨近算法的K值是在特定實(shí)驗(yàn)環(huán)境下所測得的適合值。但是在復(fù)雜多變的實(shí)際應(yīng)用環(huán)境中，系統(tǒng)的最佳K值不是一個(gè)常數(shù)。為了提高實(shí)時(shí)定位的精確度，選取的K值應(yīng)該適合實(shí)時(shí)的環(huán)境條件。

圖4 自適應(yīng)K臨近法的拓?fù)渚植拷Y(jié)構(gòu)(K=3，4，5，6)

如圖4所示，在三角形拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)中，待測標(biāo)簽P的定位誤差分布區(qū)域?yàn)檎切?。?dāng)選擇K=3時(shí)，定位誤差分布區(qū)域?yàn)槿切蜛OF;當(dāng)選擇K=6時(shí)，定位誤差分布區(qū)域?yàn)槿切蜧BE。而選擇自適應(yīng)K值時(shí)的擬待測標(biāo)簽O在K=6時(shí)對(duì)應(yīng)的定位誤差分布區(qū)域?yàn)檎呅蜛BCDEF?？紤]到最佳K值可能在不同時(shí)刻有不同值，將K的可能值設(shè)置為4到6之間的可變值，其算法流程如圖5所示。

圖5 自適應(yīng)K臨近算法流程

自適應(yīng)K臨近算法不但充分利用了三角形拓?fù)渚W(wǎng)絡(luò)的有利條件，而且對(duì)變動(dòng)的應(yīng)用環(huán)境有了更強(qiáng)的適應(yīng)性，提高了實(shí)時(shí)定位精確度。

2.3 點(diǎn)集最小包容圓定位法

LANDMARC算法的優(yōu)點(diǎn)在于，它是基于極限趨近思想的一種算法，通過對(duì)選區(qū)的K個(gè)臨近點(diǎn)加權(quán)計(jì)算，得到待測標(biāo)簽的坐標(biāo)。由于參考標(biāo)簽和待測標(biāo)簽有著相同的物理結(jié)構(gòu)，這樣就在一定程度上消除了參考標(biāo)簽和待測標(biāo)簽?zāi)承┕餐蛩匾鸬恼`差，即相對(duì)誤差。但是估計(jì)出的待測標(biāo)簽的坐標(biāo)還存在著隨機(jī)誤差。如果采用極限的思想考慮，當(dāng)對(duì)一個(gè)位置固定的待測標(biāo)簽重復(fù)測定位置的次數(shù)趨近于無窮大，那么估計(jì)坐標(biāo)描點(diǎn)后的分布區(qū)域?yàn)橐粋€(gè)以實(shí)際待測標(biāo)簽坐標(biāo)為圓心的圓形區(qū)域。

采取逆向思想考慮問題，將多次估計(jì)出的待測標(biāo)簽的坐標(biāo)點(diǎn)集用一個(gè)最小包容圓將它們?nèi)ζ饋?，令其圓心作為估計(jì)的待測標(biāo)簽的坐標(biāo)。這樣就可以將定位隨機(jī)誤差大大的削減。該算法的步驟為:

(1)在估計(jì)點(diǎn)集中任取3個(gè)點(diǎn)A、B、C;

(2)作一個(gè)包含A、B、C三點(diǎn)的最小圓，圓周可能通過這3個(gè)點(diǎn)，也可能只通過其中兩個(gè)點(diǎn)，但圓包含第3點(diǎn);

(3)在點(diǎn)集中找出距離(2)所建圓圓心最遠(yuǎn)的點(diǎn)D，若D點(diǎn)在圓內(nèi)或圓上，則該圓即為所求圓，算法結(jié)束，否則執(zhí)行(4);

(4)在A、B、C、D中選3個(gè)點(diǎn)，使由它們生成的一個(gè)包含這4點(diǎn)的圓為最小，這3點(diǎn)成為新的A、B、C三點(diǎn)，返回繼續(xù)執(zhí)行(2)，一直到找到所求最小包容圓。

3 仿真分析

本文的自適應(yīng)定位法也是一種基于RSSI的算法，所以有必要建立讀寫器接收到的功率和距離間的映射模型。在此基礎(chǔ)上，用Matlab2011a搭建系統(tǒng)的軟件仿真平臺(tái)，分析本文的算法是否能夠有效提高定位的精確度。

3.1 模型

本文采用文獻(xiàn)[5]中所描述的對(duì)數(shù)正態(tài)路徑損耗模型，建立讀寫器的接收功率和距離間的映射關(guān)系。路徑損耗PL(d)表示為:

其中，d為測定點(diǎn)到發(fā)射點(diǎn)的距離，d0為參考距離，PL(d0)為發(fā)射點(diǎn)到參考距離間經(jīng)歷的路徑損耗，n為路徑損耗指數(shù)，Xσ均值為0，方差為σ2的高斯隨機(jī)變量。在本文的仿真中，令讀寫器的發(fā)射功率為30dBm，路徑損耗指數(shù)為1.8，標(biāo)準(zhǔn)差 σ =5.2 dB。

3.2 仿真和調(diào)試

表1 仿真環(huán)境的組建

模擬一個(gè)長寬均為12米的室內(nèi)環(huán)境，將參考標(biāo)簽、讀寫器和待測標(biāo)簽均設(shè)置在其中。實(shí)驗(yàn)涉及的因素如表1所示。布設(shè)結(jié)構(gòu)如圖6所示，首先將讀寫器放置在矩形4個(gè)角，將參考標(biāo)簽在矩形范圍內(nèi)布設(shè)成三角形拓?fù)浣Y(jié)構(gòu)，最后將待測標(biāo)簽放置在矩形區(qū)域的任意點(diǎn)處。

圖6 自適應(yīng)定位法仿真

(1)初始化標(biāo)簽坐標(biāo)，待測標(biāo)簽出現(xiàn)在圖6所示的定位區(qū)域中的(1，1)處，進(jìn)入由參考標(biāo)簽組成的正三角形拓?fù)浣Y(jié)構(gòu)的輔助定位網(wǎng)絡(luò)，開始接收讀寫器發(fā)出的信號(hào)，并反向散射出應(yīng)答信號(hào)，讀寫器在模擬室內(nèi)環(huán)境的4個(gè)角處接收參考標(biāo)簽和待測標(biāo)簽的應(yīng)答信號(hào)。

(2)仿真利用對(duì)數(shù)正態(tài)路徑損耗模型將標(biāo)簽到讀寫器的距離映射成讀寫器接收到的RSSI功率值，讀寫器接收到標(biāo)簽的RSSI值的同時(shí)用標(biāo)簽返回的ID信息，辨認(rèn)出哪些是已知的參考標(biāo)簽，哪些是未知的待測標(biāo)簽。

(3)閱讀器利用接收到標(biāo)簽的RSSI信息計(jì)算所有參考標(biāo)簽和待測標(biāo)簽在功率特征上的歐式距離，找出離待測未知標(biāo)簽距離最近的一個(gè)參考標(biāo)簽進(jìn)行演習(xí)式定位，分別選取K=3，4，5，6用K臨近算法對(duì)該參考標(biāo)簽定位并計(jì)算出定位誤差，選擇定位誤差最小也就是最佳K值，利用該K值對(duì)待測未知標(biāo)簽定位。

(4)待測標(biāo)簽位置不變，在相同的仿真條件下重復(fù)進(jìn)行100次定位，圖6中的小黑點(diǎn)就是對(duì)待測標(biāo)簽100次定位的估計(jì)位置，用一個(gè)最小圓將這些估計(jì)點(diǎn)包容起來，其圓心就是待測點(diǎn)的坐標(biāo)。

仿真結(jié)果如圖6所示，最小包容圓定位法估計(jì)到的位置和真實(shí)位置間的誤差得到了很大程度的削減，使得定位精度得到顯著提高。

為了驗(yàn)證本文的這種最小包容圓自適應(yīng)定位法的定位性能，筆者收集了100組只利用自適應(yīng)K臨近法的定位數(shù)據(jù)，另外收集100組在采用自適應(yīng)K臨近法基礎(chǔ)上運(yùn)用最小包容圓定位法的定位數(shù)據(jù)。比較這兩組數(shù)據(jù)和真實(shí)待測坐標(biāo)之間的距離誤差后，得到兩組誤差數(shù)據(jù)。從圖7的誤差距離百分比累積曲線可以看出，同等概率下，加上最小包容圓算法的定位誤差距離更小。由此可以驗(yàn)證，最小包容圓自適應(yīng)K臨近算法可以有效地提高定位性能。

圖7 誤差距離的百分比累積曲線

4 結(jié)束語

本文基于對(duì)LANDMARC算法的改進(jìn)，從參考標(biāo)簽的拓?fù)浣Y(jié)構(gòu)、K值的自適應(yīng)選擇和最小包容圓定位法三方面進(jìn)行設(shè)計(jì)和仿真。仿真結(jié)果表明，本文提出的這種最小包容圓自適應(yīng)定位法相對(duì)于一般基于LANDMARC算法的定位系統(tǒng)而言，定位性能更好，精確度更高。

[1]Ni L M，Liu Yunhao，Lau Y C，et al.LANDMARC:Indoor location sensing using active RFID[J].Wireless Networks，2004，10(6):701-710.

[2]Farhan Manzoor，Yi Huang，Karsten Menzel.Passive RFID-based indoor positioning system，an algorithmic approach[C]//IEEE International Conference on RFID-Technology and Applications.2010:112-117.

[3]Huang Yihua，Lv Shilei，Liu Zongyuan，et al.The topology analysis of reference tags of RFID indoor location system[C]//The 3rd IEEE International Conference on Digital Ecosystems and Technologies(DEST).2009:313-317.

[4]Kyuwon Han，Sung Ho Cho.Advanced LANDMARC with adaptive k-nearest algorithm for RFID location system[C]//The 2nd IEEE International Conference on Network Infrastructure and Digital Content(IC-NIDC 2010).2010:595-598.

[5]Rappaport T.Wireless Communications:Principle and Practice[M].Prentice Hall，1996:138-140.

[6]汪衛(wèi)，王文平，汪嘉業(yè).求一個(gè)包含點(diǎn)集所有點(diǎn)的最小圓的算法[J].軟件學(xué)報(bào)，2000，11(9):1237-1240.

[7]Hamey L G C，Priest C.Automatic number plate recognition for Australian conditions[C]//Proceedings of Digital Image Computing Techniques and Applications.Queensland，Australia，2005:14.

[8]Wolfgang D，Wilhehn G.Interoperable 5.8GHz DSRC system as basis for European wide ETC implementation[C]//European Microwave Conference.Jerusalem，1997:139-145.

[9]劉保衛(wèi).基于RFID原理的交通目標(biāo)搜索與定位技術(shù)研究[D].大連:大連理工大學(xué)，2007.

[10]傅常倫.基于車輛定位系統(tǒng)的數(shù)據(jù)融合及其在城市交通中的應(yīng)用[D].上海:同濟(jì)大學(xué)，2008.

[11]Guvenc I，Chong Chia-Chin.A survey on TOA-based wireless localization and NLOS mitigation techniques[J].IEEE Communications Surveys ＆ Tutorials 2009，11(3):107-124.

[12]Wang Zhong-hai，Zekavat S A.A novel semidistributed localization via multinode TOA—DOA fusion[J].IEEE Transactions on Vehicular Technology，2009，58(7):3426-3435.

[13]高建立.基于RFID與DSP技術(shù)的車輛定位算法研究[D].大連:大連理工大學(xué)，2008.

[14]Hata M.Empirical formula for propagation loss in land mobile radio services[J].IEEE Transactions on Vehicular Technology，1980，29(3):317-325.