改進(jìn)的RFID室內(nèi)定位算法

段本亮，李建雄，陳明省，毛陸虹

（1.天津工業(yè)大學(xué) 電子與信息工程學(xué)院，天津 300387；2.天津大學(xué) 電子信息工程學(xué)院，天津 300072）

近年來(lái)，隨著移動(dòng)通信技術(shù)、無(wú)線技術(shù)的飛速發(fā)展，更多的應(yīng)用需要確定物體的位置信息，定位技術(shù)越來(lái)越受到人們的關(guān)注.根據(jù)環(huán)境的不同，定位可以分為室外定位和室內(nèi)定位.目前最常用的室外定位誤差主要有衛(wèi)星定位和蜂窩網(wǎng)定位技術(shù)2種，其定位方法都在米數(shù)量級(jí)，在室外環(huán)境中可以較好地滿足用戶需求，然而建筑物的屏蔽作用令其室內(nèi)定位精度大打折扣，而且高昂的成本使其直接應(yīng)用于室內(nèi)環(huán)境也存在困難.為了更好的實(shí)現(xiàn)室內(nèi)定位，必須采用新的方法與技術(shù).目前較常用的室內(nèi)定位技術(shù)主要有超聲波、紅外線、藍(lán)牙、超寬帶（UWB）和射頻識(shí)別（RFID）[1].紅外線和超寬帶定位技術(shù)造價(jià)昂貴、系統(tǒng)復(fù)雜；藍(lán)牙定位技術(shù)定位精度較差；而RFID技術(shù)以其非接觸、非視距、成本低且定位精度高等優(yōu)點(diǎn)，逐漸成為了室內(nèi)定位領(lǐng)域的優(yōu)選技術(shù)，被業(yè)界公認(rèn)為是本世紀(jì)最有價(jià)值的應(yīng)用技術(shù)之一[2-4].RFID定位系統(tǒng)一般由閱讀器、標(biāo)簽和應(yīng)用軟件系統(tǒng)3部分組成，通過(guò)檢測(cè)到的標(biāo)簽反射回來(lái)的信號(hào)強(qiáng)度來(lái)表征閱讀器與標(biāo)簽之間的幾何距離，是一種基于接收信號(hào)強(qiáng)度指示（received signal strength indicator，RSSI）的定位技術(shù)[5].本文首先介紹現(xiàn)有的2種基于RFID的室內(nèi)定位算法即RSSI線性定位算法和LANDMARC算法，分析其優(yōu)缺點(diǎn)，結(jié)合2種算法給出了改進(jìn)的RFID室內(nèi)定位算法，并進(jìn)行了仿真分析和總結(jié).

1 RSSI線性定位算法

1.1 傳播路徑信號(hào)損耗模型

基于理論和測(cè)試的傳播路徑模型指出，經(jīng)過(guò)多徑信道接收到的信號(hào)強(qiáng)度一般服從對(duì)數(shù)正態(tài)分布.常用的對(duì)數(shù)距離路徑損耗模型遵從公式[6]:

式中:P（d）表示經(jīng)過(guò)距離 d 后的路徑損耗值；P（d0）表示經(jīng)過(guò)距離d0后的路徑損耗值，d0為參考距離，一般取值為1 m；n表示路徑損耗指數(shù)，表示路徑損耗隨距離增長(zhǎng)的速率，它主要受周圍環(huán)境和建筑物的影響，取值范圍一般為2～4；Xσ是均值為0、標(biāo)準(zhǔn)差為δ的高斯分布隨機(jī)數(shù)，δ的范圍一般為4～10.

路徑損耗P（d）與閱讀器接收到的信號(hào)強(qiáng)度Pr（d）及系統(tǒng)發(fā)射功率Pt之間存在以下關(guān)系:

為了得到閱讀器接收到的信號(hào)強(qiáng)度與距離之間的關(guān)系，將式（1）代入式（2），整理可得對(duì)數(shù)距離路徑損耗模型的另一表達(dá)式:

式中:Pr（d）表示閱讀器在距離標(biāo)簽d時(shí)接收到的信號(hào)強(qiáng)度，即RSSI，單位為dBm；Pr（d0）表示閱讀器在參考點(diǎn)d0時(shí)接收到的信號(hào)強(qiáng)度.本文采用式（3）對(duì)閱讀器接收到的RSSI進(jìn)行處理得到距離關(guān)系.

1.2 RSSI線性定位算法

通過(guò)硬件設(shè)施完成信號(hào)的接收及信號(hào)強(qiáng)度的測(cè)量，根據(jù)上述建立的傳播路徑信號(hào)損耗模型計(jì)算出各個(gè)閱讀器與待定位標(biāo)簽之間的距離，然后根據(jù)距離方程組使用最小二乘法便可計(jì)算出待定位標(biāo)簽的坐標(biāo).假設(shè)共有n個(gè)閱讀器，坐標(biāo)分別為（xi，yi），（i=1，2，…，n），各個(gè)閱讀器與待定位標(biāo)簽之間計(jì)算出的距離為di，待定位標(biāo)簽的坐標(biāo)為（x，y），所列出的距離方程組如下:

將方程組的前（n－1）個(gè)方程分別減去第n個(gè)方程，從而達(dá)到把二次方程線性化的目的，得到下列方程組:

則（5）式可寫為:

用最小二乘法（LS）求解可得:

向量θ里的元素即為計(jì)算出來(lái)的待定位標(biāo)簽的坐標(biāo)值（x，y）.

RSSI線性定位算法[7]是目前最常用的室內(nèi)定位算法之一，其原理簡(jiǎn)單，數(shù)據(jù)處理量小，系統(tǒng)實(shí)時(shí)性好.當(dāng)然RSSI線性算法也存在著一些不足，最大的缺點(diǎn)就是定位精度不是很高，要想進(jìn)一步提高定位精度，就需要增加閱讀器的數(shù)目，從而導(dǎo)致成本的提高.根據(jù)文獻(xiàn)[8]所述，閱讀器與標(biāo)簽距離越遠(yuǎn)，測(cè)距誤差就越大.由此可知，當(dāng)定位邊緣區(qū)域的標(biāo)簽距離個(gè)別閱讀器較遠(yuǎn)時(shí)，測(cè)距誤差較大，從而定位誤差變大，甚至有時(shí)無(wú)法實(shí)現(xiàn)定位.所以非常有必要對(duì)此算法進(jìn)行改進(jìn)，解決邊緣區(qū)域定位差的問題，從而使該算法更具有適用性.

2 LANDMARC算法

LANDMARC （location identification based on dynamic active rfid calibrarion）定位算法[9]是一種經(jīng)典的基于有源RFID系統(tǒng)的室內(nèi)定位算法，設(shè)計(jì)思想是采用固定參考標(biāo)簽輔助定位，通過(guò)待定位標(biāo)簽的信號(hào)強(qiáng)度值與參考標(biāo)簽的信號(hào)強(qiáng)度值之間的比較，采用“最近鄰居”權(quán)重思想，計(jì)算出定位標(biāo)簽的坐標(biāo).LANDMARC算法具有較高的定位精度，可擴(kuò)展性好，能處理比較復(fù)雜的環(huán)境，是一種非常實(shí)用的定位算法.

假設(shè)有n個(gè)閱讀器、m個(gè)參考標(biāo)簽和u個(gè)待定位標(biāo)簽.待定位標(biāo)簽的坐標(biāo)為（xi，yi），（i=1，2，…，u）.閱讀器分別讀出所有參考標(biāo)簽和待定位標(biāo)簽的場(chǎng)強(qiáng)值.待定位標(biāo)簽坐標(biāo)求解過(guò)程如下:

（1）定義待定位標(biāo)簽的信號(hào)強(qiáng)度矩陣S:

式中:Sij（i=1，2，…，u；j=1，2，…，n）表示第j個(gè)閱讀器讀取到第i個(gè)待定位標(biāo)簽的信號(hào)強(qiáng)度.定義參考標(biāo)簽的信號(hào)強(qiáng)度矩陣θ:

式中:θpj（p=1，2…，m；j=1，2…，n）表示第j個(gè)閱讀器讀取到第p個(gè)參考標(biāo)簽的信號(hào)強(qiáng)度.

定義待定位標(biāo)簽與參考標(biāo)簽的歐幾里德距離矩陣E:

Eip越小說(shuō)明它們之間的距離越近.

（2）為了計(jì)算出待定位標(biāo)簽的坐標(biāo)，人為地選擇k個(gè)參考標(biāo)簽，其坐標(biāo)記為（x'r，y'r）（r=1，2，…，k），這些參考標(biāo)簽與待定位標(biāo)簽i的歐幾里德距離是（Ei1，Ei2，…，Eim）中最小的k個(gè)值，記為E'ir（r=1，2，…，k）.待定位標(biāo)簽i的坐標(biāo)可以通過(guò)這k個(gè)參考標(biāo)簽的坐標(biāo)及其權(quán)重得到

式中:ωir為待定位標(biāo)簽i的第r個(gè)鄰居參考標(biāo)簽的權(quán)重（r=1，2，…，k），距離越近的標(biāo)簽所占的權(quán)重越大.ωir可根據(jù)經(jīng)驗(yàn)公式得到:

（3）定義估計(jì)誤差:通過(guò)比較待定位標(biāo)簽的估算坐標(biāo)與實(shí)際坐標(biāo)，可以計(jì)算出他們之間的誤差值:

式中:（xi，yi）為估算的待定位標(biāo)簽坐標(biāo)位置；（xi0，yi0）為待定位標(biāo)簽的實(shí)際坐標(biāo)位置.

LANDMARC算法具有以下3個(gè)方面的優(yōu)勢(shì):

（1）采用多個(gè)廉價(jià)的參考標(biāo)簽代替了昂貴的閱讀器，降低了整個(gè)定位系統(tǒng)的成本；

（2）待定位標(biāo)簽和參考標(biāo)簽處于同樣的環(huán)境中，環(huán)境因素的影響可以很大程度地抵消；

（3）定位精度較高.

但是，它也有一些不足之處:

（1）定位精度與參考標(biāo)簽密度有關(guān)，要想獲得更高的定位精度，必須布置更多的參考標(biāo)簽，一方面增加了系統(tǒng)成本和標(biāo)簽布局難度，另一方面太多的參考標(biāo)簽還會(huì)造成標(biāo)簽之間的信號(hào)干擾；

（2）該算法在確定鄰近參考標(biāo)簽時(shí)，需要計(jì)算所有的參考標(biāo)簽與待定位標(biāo)簽之間的歐幾里德距離，從而會(huì)導(dǎo)致大量的不必要的計(jì)算而影響定位實(shí)時(shí)性.

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

3.1 改進(jìn)方法

RSSI線性定位算法的定位誤差雖然比LANDMARC算法要大一些，但其不需要布置大量的參考標(biāo)簽，既可以節(jié)省一部分成本，又避免了特殊空間難以布置參考標(biāo)簽的問題，所以在精度要求不太高的場(chǎng)合仍有著較大的應(yīng)用價(jià)值.由前文分析可知RSSI線性定位算法邊緣區(qū)域定位誤差較大，所以本文借鑒LANDMARC算法定位精度較高的優(yōu)勢(shì)，在定位邊緣區(qū)域布置少量參考標(biāo)簽，并在布置參考標(biāo)簽的區(qū)域采用LANDMARC算法，而其他區(qū)域仍采用RSSI線性定位算法.這樣不僅解決了RSSI線性定位算法邊緣區(qū)域定位誤差大的問題，而且相比整個(gè)區(qū)域全部使用LANDMARC算法降低了一些成本，減少了算法運(yùn)行時(shí)間.該算法流程圖如圖1所示.

圖1 改進(jìn)算法流程圖Fig.1 Improved algorithm flow chart

3.2 仿真與分析

在路徑損耗指數(shù)n=2.2、標(biāo)準(zhǔn)差δ=5的環(huán)境下，按照?qǐng)D2（a）所示位置在20 m×20 m的空間邊緣區(qū)域放置68個(gè)參考標(biāo)簽，參考標(biāo)簽間距為2 m，4個(gè)閱讀器位于空間邊界的角上，并在定位區(qū)域設(shè)置10個(gè)待定位標(biāo)簽.圖2（b）除了沒有放置參考標(biāo)簽以外，其它條件與圖2（a）相同.圖2（c）是在所有的區(qū)域都放置上參考標(biāo)簽，總數(shù)為117個(gè)，其它條件與圖2（a）和圖2（b）完全相同.

由圖 2 可知，待定位標(biāo)簽 Tag1、Tag2、Tag3、Tag4、Tag5、Tag6、Tag7位于邊緣區(qū)域，待定位標(biāo)簽 Tag8、Tag9、Tag10位于非邊緣區(qū)域.

采用MATLAB數(shù)學(xué)軟件分別對(duì)RSSI線性定位算法、LANDMARC算法和本文改進(jìn)算法仿真50次.定義計(jì)算出來(lái)的待定位標(biāo)簽的坐標(biāo)為（xt，c，yt，c）（t=1，2，…，10；c=1，2，…，50），待定位標(biāo)簽的實(shí)際坐標(biāo)為（xt，y）t（t=1，2，…，10），計(jì)算出來(lái)的坐標(biāo)與實(shí)際坐標(biāo)的歐式距離為et，c=（t=1，2，…，10；c=1，2，…，50）.利用每個(gè)待定位標(biāo)簽的平均誤差=（t=1，2，…，10）和所有標(biāo)簽的平均誤差=（t=1，2，…，10）評(píng)估本文提出的算法性能，結(jié)果如圖3所示.

圖2 不同算法情況下的閱讀器與標(biāo)簽布局圖Fig.2 Reader and Tag layout diagram on different algorithms

圖3 標(biāo)簽定位誤差對(duì)比圖Fig.3 Tag positioning error comparison diagram

由圖3可知，相對(duì)于RSSI線性定位算法，采用改進(jìn)算法后，邊界待定位標(biāo)簽 Tag1、Tag2、Tag3、Tag4、Tag5、Tag6、Tag7的定位誤差得到了顯著下降，精確度得到有效提高.7個(gè)邊界待定位標(biāo)簽的估計(jì)誤差與RSSI線性算法相比降低了35.8%～60.4%.使用RSSI線性定位算法、LANDMARC算法和本文改進(jìn)算法時(shí)的所有標(biāo)簽平均定位誤差分別為1.97、1.23、1.25，由此可見本文改進(jìn)算法與LANDMARC算法的定位精度非常接近.3種算法相比較，RSSI線性定位算法用時(shí)0.004398 s，LANDMAR算法用時(shí)0.040603 s，改進(jìn)算法用時(shí)0.029161 s.RSSI線性定位算法定位誤差最大，但用時(shí)最少，LANDMARC算法比改進(jìn)算法的定位精度稍高，但算法執(zhí)行時(shí)間更長(zhǎng)，并且需要更多的參考標(biāo)簽，所以改進(jìn)的算法相比LANDMARC算法而言實(shí)時(shí)性更好，成本更低一些.

4 結(jié)束語(yǔ)

本文提出的改進(jìn)算法在沒有增加太多成本的基礎(chǔ)上解決了RSSI線性定位算法在邊緣區(qū)域定位精度差的問題，提高了整體系統(tǒng)的定位精度，擴(kuò)大了該算法的適用范圍.由于該算法只是在邊緣區(qū)域布置參考標(biāo)簽，所以與LANDMARC算法相比，減少了參考標(biāo)簽的使用數(shù)目進(jìn)而降低了系統(tǒng)成本和減小了系統(tǒng)布局的難度.由于該算法只是在邊緣區(qū)域才使用LANDMARC算法，所以算法計(jì)算量比單純使用LANDMARC算法減少了許多，從而提高了系統(tǒng)的實(shí)時(shí)性.在定位精度要求不太嚴(yán)格的場(chǎng)合，該改進(jìn)算法有很大的使用價(jià)值.

[1]張文錦，李建雄，毛陸虹.基于多波束切換的便攜式RFID閱讀器設(shè)計(jì) [J].天津工業(yè)大學(xué)學(xué)報(bào)，2013，31（1）:52-56.

[2]SHIRAISHI T，KOMURO N，UEDA H.Indoor location estimation technique using UHF band RFID[C]//Information Networking，2008 International Conference.Busan:[s.n]，2008:1-5.

[3]SHIH S，HSIEH K，CHEN P.An improvement approach of indoor location sensing using active RFID[C]//Innovative Computing，Information and Control，2006 First International Conference.Beijing:[s.n]，2006:453-456.

[4]DAI H，SU D.Indoor location system using RFID and ultrasonic sensors[C]//Personal，Indoor and Mobile Radio Communications，2006 IEEE 17th International Symposium.Kunming:[s.n]，2006:1179-1181.

[5]陳永光.基于信號(hào)強(qiáng)度的室內(nèi)定位技術(shù)[J].電子學(xué)報(bào)，2004，32（9）:1456-1458.

[6]楊大成.移動(dòng)傳播環(huán)境理論基礎(chǔ)、分析方法和建模技術(shù)[M].北京:機(jī)械工業(yè)出版社，2003.

[7]顧宗海.基于RSSI測(cè)距的室內(nèi)定位算法研究[D].鄭州:鄭州大學(xué)，2011.

[8]黃濤.物聯(lián)網(wǎng)短距離定位算法研究 [D].大連:大連理工大學(xué)，2011.

[9]NI L，LIU Y，LAU Y，et al.LANDMARC:Indoor location sensing using active RFID [C]//Proceedings of the First IEEE International Conference on Pervasive Computing and Communications（Per-Com2003）.Dallas:[s.n]，2003:407-415.