孫寅博，王宏剛，李 波

(西安郵電大學 無線網(wǎng)絡安全技術國家工程實驗室，陜西 西安710061)

基于參考標簽的射頻識別室內(nèi)定位算法研究

孫寅博，王宏剛，李 波

(西安郵電大學 無線網(wǎng)絡安全技術國家工程實驗室，陜西 西安710061)

針對現(xiàn)有基于RFID的LANDMARC室內(nèi)定位系統(tǒng)會因外界環(huán)境因素導致優(yōu)良的鄰近參考標簽丟失、不良的參考標簽引入的問題，為此提出了一種改進的最近鄰居算法，通過篩選已選取的鄰近參考標簽，實現(xiàn)最近鄰標簽的最佳選取。實驗結果表明待測標簽的定位精度得到有效提高。該算法有效獲取到優(yōu)良的參考標簽，從而獲得了滿意的定位精度和定位性能。

室內(nèi)定位；LANDMARC系統(tǒng)；RFID

近年來，隨著物聯(lián)網(wǎng)的興起，工業(yè)、農(nóng)業(yè)、商業(yè)和軍事領域的研究者越來越關注基于無線傳感器網(wǎng)絡(Wireless Sensing Networks, WSN[1])和無線局域網(wǎng)(Wireless Local Area Networks, WLAN[2])等面向區(qū)域的定位技術。

對于某一節(jié)點，如果獲得其當前所在的空間位置信息，則可以實現(xiàn)許多實用的功能，比如大型超市，每個貨架放置一個WSN節(jié)點，購物車上安置一個收發(fā)器，顧客就可以根據(jù)自己的實時位置信息找到目標產(chǎn)品所在的貨架。在醫(yī)院內(nèi)部署WSN節(jié)點，給病人隨身攜帶一套生理指標監(jiān)視器，一旦健康狀況異常，醫(yī)生可在第一時間趕到病人身邊實施治療。另外，室內(nèi)定位在智能家居中的應用也越來越廣泛。這些重要的潛在應用價值，引起了廣泛的關注及研究。

根據(jù)應用場景的不同，定位分為室外定位和室內(nèi)定位，而室內(nèi)定位系統(tǒng)與室外定位系統(tǒng)因所處的環(huán)境條件不同而分別采用了不同的定位方法。對于室外定位，通常采用全球定位系統(tǒng)(GPS[3])，其需要直接視距通信衛(wèi)星[4]，而對于室內(nèi)環(huán)境來說，卻難以較好地實現(xiàn)。一方面衛(wèi)星信號受到嚴重遮擋和衰減，衛(wèi)星和接收機之間不存在視距傳輸通道；另一方面室內(nèi)的環(huán)境比室外更加復雜，比如家具布局、人的移動等造成的信號的反射、散射及多徑效應的問題，因此GPS無法提供足夠的室內(nèi)定位精度。

常見的室內(nèi)定位技術有很多種，如基于紅外[5]、超聲波[6]、藍牙[7]、射頻識別(RFID)[8-12]、超寬帶(UWB)[13]、WiFi[14]等定位技術。其中，基于RFID的定位技術優(yōu)勢明顯，如：非接觸、精度高、成本低等，為室內(nèi)定位提供了一種新的解決方案，因而使其關注度越來越高，從而更多的人對其進行了廣泛的深入研究。

當前基于RFID的室內(nèi)定位常用的有SpotON系統(tǒng)[15]、Cricket系統(tǒng)[16]以及LANDMARC系統(tǒng)[17]等。SpotON系統(tǒng)根據(jù)信號強度分析，利用積集算法對三維空間中的待測標簽進行定位，通過設計和定制的參考標簽的無線信號衰減獲取標簽間的距離信息，但定位精度不夠高，時效性也較差；Cricket是基于射頻和超聲波的TDOA定位系統(tǒng)，缺陷是：節(jié)點的坐標需要事先設置好，一旦環(huán)境改變，測量的定位誤差會增大；LANDMARC系統(tǒng)引入位置固定的有源參考標簽，通過它們提供檢測距離方位內(nèi)的標簽信號強度信息來輔助定位。定位精度與參考標簽的位置配置之間有很大關系，參考標簽越少，定位結果越差；但參考標簽越多，在一定程度上又增加了定位的成本，另外，增多的參考標簽也會增加標簽之間的干擾，從而降低定位的性能。但這種方法通過增加一些低成本的有源標簽，減少成本昂貴的閱讀器數(shù)量，在很大程度上降低了定位的成本，具有十分重要的價值，又因其可擴展性好，能適應較復雜的環(huán)境而被廣泛采納。

1 LANDMARC室內(nèi)定位算法

LANDMARC是一種基于有源RFID的經(jīng)典室內(nèi)定位算法，它采用最近鄰居算法，其核心思想采用建立在RSSI之上的質(zhì)心算法，根據(jù)待測標簽和參考標簽之間的信號強度殘差加權算法進行定位。

1.1 LANDMARC的算法描述

假設有M個閱讀器、N個參考標簽、L個待測標簽，其中參考標簽是布設在室內(nèi)、位置已知的標簽，其坐標分別為(x1,y1),(x2,y2),…，(xN,yN)，而待測標簽則是需要通過參考標簽進行定位的標簽。分布在室內(nèi)中四角的閱讀器，負責讀取參考標簽和待測標簽的能量，并進行能量的量化(量化等級為8級)。定義閱讀器接收的參考標簽信號強度矩陣S∈RN×M為

(1)

式中：Sij表示第j個閱讀器接收到的第i個參考標簽的RSSI能量等級值。

定義閱讀器接收的待測標簽信號強度矩陣T∈RL×M為

(2)

式中：Tij表示第j個閱讀器接收到的第i個待測標簽的RSSI能量等級的值。

為了確定與待測標簽相近的參考標簽，以實現(xiàn)有效定位，需要定義待測標簽與參考標簽的關聯(lián)矩陣

(3)

(4)

式中：Eij表示第i個待測標簽與第j個參考標簽之間信號強度的歐幾里德距離。Eij越小，表明兩個標簽之間的空間距離越接近。

通過比較Eij值的大小，選出k個離待測標簽最近的參考標簽(即最近鄰標簽),k的值可以根據(jù)不同的應用環(huán)境進行設定。那么，第l個待測標簽位置坐標的估計為

(5)

式中：wli為第i個參考標簽在該待測標簽位置估計中的權重。

距離待測標簽較近的參考標簽應該對位置精度的估計起較大作用，權重系數(shù)設置與關聯(lián)度之間具有一定的關系。故權重設置為

(6)

可見，參考標簽對應的Eli越小，它的權重wli越大。于是，第l個待測標簽的定位誤差為

(7)

式中：(xl0,yl0) 為待測標簽的實際坐標；(xl,yl)是由式(5)計算的待測標簽的估計坐標；el表示第l個待測標簽的估計位置與其實際位置之間的誤差，el越小，即定位誤差越小，定位越精確。

1.2 LANDMARC中存在的問題

LANDMARC系統(tǒng)的定位精度很大程度上受到參考標簽密度的影響[18]， 另外RFID射頻信號在復雜的室內(nèi)環(huán)境下，會發(fā)生多徑效應、反射、衍射等情況，通過矩陣E選擇最近鄰標簽的時候，往往存在或多或少的偏差，從而導致LANDMARC系統(tǒng)定位中選擇參考標簽的隨機性和不可預估性，如果選擇到不良參考標簽作為最近鄰標簽，那么必然影響到定位的精度。

如果要提高定位的精度，就需要尋找最適合的參考標簽作為待測標簽的最近鄰標簽。針對此問題，提出一種改進的最近鄰居算法，優(yōu)化最近鄰標簽的選取，降低不良參考標簽的影響，進而改善LANDMARC系統(tǒng)的定位性能。

2 改進的最近鄰居算法

2.1 改進算法的思想

為提高最近鄰標簽選擇的精度，本文提出一種最近鄰標簽的篩選法，實現(xiàn)待測標簽對鄰近參考標簽更為準確的選取，從而消除選取的不良參考標簽造成的誤差影響，進而提高了定位的精度。

2.2 改進算法的具體實現(xiàn)

首先，由式(5)可獲得某個待測標簽的坐標(x,y)，這個待測標簽用tagA表示，其選取的k個參考標簽分別用tag1，tag2，…，tagk表示。

對于組G中的每一個參考標簽的位置，可以通過待測標簽和其他k-1個參考標簽來計算出它的坐標。如tag1的坐標可以通過tagA，tag2，…，tagk這k個標簽來確定，tag2的坐標可以通過tagA，tag1，tag3，…，tagk這k個標簽來確定，同理依次可以獲得tag3，tag4，…，tagk的坐標。

分別對比這k個參考標簽的真實位置，獲得它們各自對應的誤差err1，err2，…，errk。比較k個參考標簽的誤差，選取k′個誤差值較小的參考標簽為待測標簽最終選取的鄰近參考標簽(k′

(8)

式中：errli表示對于待測標簽l，第i個參考標簽相對待測標簽l的估計誤差。

最后通過式(5)計算出待測標簽的最終位置(xfinal,yfinal)。整個算法流程如圖1所示。

圖1 算法流程圖

3 仿真模型和結果

仿真中，因為是根據(jù)標簽的RSSI值來估計待測標簽的位置，在這里選擇的路徑損耗模型為

(9)

式中：d0是參考距離；P0是距離為d0時接收到的信號強度，即單位距離的自由空間損耗；d是真實距離；ζ是遮蔽因子，其均值0；標準差為σdB的正態(tài)隨機變量；P是接收時衰減的信號強度；n是路徑損耗指數(shù)。

通過對LANDMARC算法及其對應的改進的最近鄰居算法分別進行仿真，進而評估改進算法的定位效果。仿真中使用研究報告中的參數(shù)[19]，在9m×9m的室內(nèi)環(huán)境中，在4個角落放置4個閱讀器，在定位區(qū)域內(nèi)將16個參考標簽按4×4均勻分布，參考標簽之間的間隔為2m，20個待測標簽隨即分布在室內(nèi)，k=6, k′=4，仿真結果如圖2所示。

圖2 LANDMARC算法與改進算法的誤差累積分布圖

由圖2可見，兩種算法在定位誤差為0.5m內(nèi)的標簽分別占待測標簽總數(shù)的10%，30%；定位誤差在1m以內(nèi)時，兩種算法所定位的標簽分別占待測標簽總數(shù)的50%，90%。改進的算法對于定位精度的提高是非常明顯的。

針對每個待測標簽，兩種算法的比較如圖3所示。

圖3 LANDMARC算法與改進算法的比較

大多數(shù)待測標簽的定位精度得到了改善，部分待測標簽的定位精度提升明顯。而6，12，14，17，20這5個待測標簽的改進算法的誤差稍微偏高。其主要因為標簽密度所造成的影響。通過加入虛擬標簽的方法，對這些待測標簽的定位能提供一定的幫助，具體的實現(xiàn)會在今后做進一步的研究。

4 小結

LANDMARC系統(tǒng)中的最近鄰居定位算法，提出了相應的改進算法。通過對最近鄰居參考標簽選取的優(yōu)化，避免不良標簽的引入而造成對待測標簽的影響。實驗表明，改進的算法在對待測標簽的定位精度有了很大的提高。

[1]KWONOH，SONGHJ，PARKS.Theeffectsofstitchingordersinpatch-and-stitchWSNlocalizationalgorithms[J].IEEETrans.ParallelandDistributedSystems，2009，20(9)：1380-1391.

[2]IVANOVS，NETTE，SCHEMMERS.AutomaticWLANlocalizationforindustrialautomation[C]//Proc.IEEEInternationalWorkshoponFactoryCommunicationSystems.Dresden：IEEEPress，2008：93-96.

[3]ENGEP，MISRAP.Specialissueonglobalpositioningsystem[J].ProceedingsoftheIEEE，1999，87(1)： 3-15.

[4]BOONTRAID，JINGWANGSAT，CHERNTANOMWONGP.IndoorlocalizationtechniqueusingpassiveRFIDtags[C]//Proc. 9thInternationalSymposiumonCommunicationsandInformationTechnology.Icheon：IEEEPress，2009：922-926.

[5]WANTR，HOPPERA，F(xiàn)ALCOV，etal.Theactivebadgelocationsystem[J].ACMTrans.InformationSystems，1992，10(1)：91-102.

[6]SMITHA，BALAKRISHNANH，GORACZKOM，etal.Trackingmovingdeviceswiththecricketlocationsystem[C]//Proc. 2ndACMInternationalConferenceonMobileSystems，Applications，andServices.Boston：MobiSysPress，2004：190-202.

[7]EDWARDR，JELLINEKL.Informationexchangeviabluetoothservicediscoveryprotocolservicerecords：US，8074481B2[P]. 2011-11-17.

[8]BASSMA.Radiofrequencyidentification(Rfid)systemformanufacturingdistributionandretailingofkeys：US，8074481B2 [P]. 2011-12-13.

[9]WANTR.AnintroductiontoRFIDtechnology[J].IEEEPervasiveComputing，2006，5(1)：25-33.

[10]SHIREHJINIAAN，YASSINEA，SHIRMOHAMMADIS.EquipmentlocationinhospitalsusingRFID-basedpositioningsystem[J].IEEETrans.InformationTechnologyinBiomedicine，2012，16(6)：1058-1069.

[11]SHOARINEJADK，SOLTANM，MOSHFEGHIM.Rfidlocationsystemsandmethods：US，8754752B2 [P]. 2014-06-17.

[12]LIUYongbo，DUHuaichang，XUYe.TheresearchanddesignoftheindoorlocationsystembasedonRFID[C]//Proc.FourthInternationalSymposiumonComputationalIntelligenceandDesign.Hangzhou：IEEEPress，2011：87-90.

[13]TANLin，JINLong，YANGGuoqing.Acompactultra-wideband(UWB)bandpassfilterusingmicrostripT-shapedstub[C]//Proc.InternationalConferenceonComputationalProblem-Solving.Chengdu：IEEEPress，2011：382-384.

[14]NOBUOK.WiFilocationinformationsystemforbothindoorsandoutdoors[C]//Proc. 10thInternationalWork-ConferenceonArtificialNeuralNetworks.Salamanca：SpringerBerlinHeidelbergPress，2009：638-645.

[15]HIGHTOWERJ，WANTR，BORRIELLOG.SpotON：anIndoor3DlocationsensingtechnologybasedonRFsignalstrength[R].Seattle：[s.n.]，2000.

[16]PRIYANTHANBCHAKRABORTYA，BALAKRISHNANH.Thecricketlocation-supportsystem. [C]//Proc. 6thAnnualInternationalConferenceonMobileComputingandNetworking(MOBICOM).NewYork：ACMPress，2000：32-43.

[17]NILM，LIUYH，LAUYC，etal.LANDMARC：indoorlocationsensingusingactiveRFID[C]//Proc. 1stIEEEInternationalConferenceonPervasiveComputingandCommunications.FortWorth：IEEEPress，2003：407-415.

[18]閆保中，姜琛，尹偉偉. 基于RFID技術的室內(nèi)定位算法研究[J]. 計算機仿真，2010，27(2)：320-324.

[19]BEKKALIA，SANSONH，MATSUMOTOM.RFIDindoorpositioningbasedonprobabilisticRFIDmapandKalmanfiltering[C]//Proc. 3rdIEEEInternationalConferenceonWirelessandMobileComputing，NetworkingandCommunications.WhitePlains，NY：IEEEPress，2007：21.

孫寅博(1984— )，碩士生，主研無線通信；

王宏剛(1977— )，講師，博士，主研無線通信、射頻識別、無線傳感器網(wǎng)絡等；

李 波(1980— )，講師，博士，主研寬帶無線通信。

責任編輯：許 盈

Research of RFID Indoor Location Algorithm Based on Reference Tags

SUN Yinbo, WANG Honggang, LI Bo

(NationalEngineeringLaboratoryforWirelessSecurity,Xi’anUniversityofPostsandTelecommunications,Xi’an710061,China)

Due to the miss of fine nearest neighbors and misuse of bad neighbors because of the environmental factors, the performance of the LANDMARC RFID-based indoor location system will be degraded significantly. An improved LANDMARC locating algorithm via selecting the nearest neighbor reference tags among the selected ones is proposed, and the experimental results show that performance of the proposed algorithms is improved. This algorithm can effectively get the nearest neighbors and achieve a better performance for location sensing.

indoor location; LANDMARC system; RFID

陜西省國際合作項目(2013KW01-03)

TN92

A

10.16280/j.videoe.2015.01.028

2014-09-05

【本文獻信息】孫寅博，王宏剛，李波.基于參考標簽的射頻識別室內(nèi)定位算法研究[J].電視技術,2015，39(1).