基于區(qū)域劃分和目標(biāo)搜索的室內(nèi)RFID三維定位算法

向祖權(quán) 靳 超 許慧文

(高性能船舶技術(shù)教育部重點實驗室1) 武漢 430063) (武漢理工大學(xué)交通學(xué)院2) 武漢 430063)

?

基于區(qū)域劃分和目標(biāo)搜索的室內(nèi)RFID三維定位算法

向祖權(quán)1,2)靳 超1,2)許慧文2)

(高性能船舶技術(shù)教育部重點實驗室1)武漢 430063) (武漢理工大學(xué)交通學(xué)院2)武漢 430063)

為提高室內(nèi)三維定位系統(tǒng)的性能，提出一種基于區(qū)域劃分和目標(biāo)搜索的室內(nèi)RFID三維定位算法.通過布置在室內(nèi)頂部和側(cè)面的參考標(biāo)簽劃分一個待定位標(biāo)簽所在的區(qū)域，選取該區(qū)域中心點作為目標(biāo)搜索的初始點，向x，y，z軸正負(fù)方向?qū)Υㄎ粯?biāo)簽進(jìn)行搜索，通過不斷逼近，最終確定待定位標(biāo)簽的坐標(biāo).仿真實驗表明，該算法定位誤差小，穩(wěn)定性優(yōu)良.

區(qū)域劃分；目標(biāo)搜索；射頻識別；三維定位；室內(nèi)定位

0 引 言

GPS定位系統(tǒng)適合室外空曠地域的定位，對于建筑物過多、遮擋較為嚴(yán)重的情況則會產(chǎn)生明顯的定位誤差，所以GPS定位方法并不適用于室內(nèi)定位.Sun等[1]提出A-GPS方法用于改進(jìn)GPS系統(tǒng)在室內(nèi)環(huán)境中定位的效果.Lau等[2]對Zigbee技術(shù)在室內(nèi)定位中的運(yùn)用進(jìn)行了相關(guān)研究.Yuen等[3]提出運(yùn)用Wi-Fi技術(shù)對室內(nèi)定位精度進(jìn)行提高.但目前研究最多，運(yùn)用最多的是RFID技術(shù)，它以識別距離遠(yuǎn)、響應(yīng)速度快、非接觸操作、成本低等特點成為室內(nèi)定位研究的熱點[4].

基于RFID技術(shù)的室內(nèi)定位系統(tǒng)主要有Ling等[5]提出的LANDMARC定位系統(tǒng)，Hightower等[6]研究的SpotOn系統(tǒng)，Zhao等[7]在LANDMARC系統(tǒng)上改進(jìn)得到的VIRE系統(tǒng).常見的算法有解析算法[8]、估值算法[9]、最近鄰居算法等.但是這些系統(tǒng)和算法主要針對室內(nèi)平面二維定位，對室內(nèi)三維空間定位的研究較少.雖然高銳等[10]提出的基于空間分割的無源RFID定位方法，以及董永峰等[11]針對空間分割方法的改進(jìn)方法，可以對室內(nèi)三維空間進(jìn)行定位，但是他們方法中的參考標(biāo)簽一部分是布置在地面上，在實際環(huán)境中，由于室內(nèi)大部分物體是布置在地面上的，所以會對參考標(biāo)簽產(chǎn)生嚴(yán)重的干擾，這樣會降低定位的精確度.

文中提出一種新的參考標(biāo)簽布置方式，將傳統(tǒng)方式中布置在空間底部的參考標(biāo)簽布置到空間的側(cè)面，保留空間頂部的參考標(biāo)簽.利用空間頂部參考標(biāo)簽確定待定位標(biāo)簽的x，y坐標(biāo)區(qū)域，用空間側(cè)面參考標(biāo)簽確定待定位標(biāo)簽z坐標(biāo)區(qū)域，再用目標(biāo)搜索方法在定位區(qū)域內(nèi)搜索待定位標(biāo)簽的坐標(biāo).該算法在不增加參考標(biāo)簽數(shù)量的情況下，通過算法的改良，提高了定位精度.

1 “最近鄰居”參考標(biāo)簽選擇

“最近鄰居”參考標(biāo)簽就是指與待定位標(biāo)簽相鄰的參考標(biāo)簽.通過計算參考標(biāo)簽與待定位標(biāo)簽之間RSSI(receive signal strength identification)值的歐式距離，選取距離最小的若干參考標(biāo)簽作為“最近鄰居”參考標(biāo)簽，選擇過程如下.

假設(shè)有m個閱讀器，n個參考標(biāo)簽，p個待定位標(biāo)簽，每個閱讀器都可以讀到參考標(biāo)簽和待定位標(biāo)簽的信號強(qiáng)度值.

記某個待定位標(biāo)簽Pi在各個閱讀器上的RSSI值構(gòu)成如下矢量：Pi=(PiM1,PiM2,…,PiMm).式中：PiMs為該待定位標(biāo)簽Pi在第s個閱讀器上的RSSI值，i∈(1,p)，s∈(1,m)；記某個參考標(biāo)簽Rj在各個閱讀器上的RSSI值構(gòu)成如下矢量:Rj=(RjM1,RjM2,…,RjMm).式中：RjMs為該參考標(biāo)簽Rj在第s個閱讀器上的RSSI值，j∈(1,n).

待定位標(biāo)簽PiMs與參考標(biāo)簽RjMs之間RSSI值的歐式距離為

(1)

因為需要選出與待定位標(biāo)簽Pi鄰近的若干個參考標(biāo)簽，所以對于待定位標(biāo)簽Pi來說，需要計算n個參考標(biāo)簽與其之間RSSI值的歐氏距離，它們組成一個集合Di.

(2)

通過比較Di,j的大小，可以選出k個與待定位標(biāo)簽鄰近的參考標(biāo)簽，即為k個“最近鄰居”參考標(biāo)簽.

2 RSSI損耗模型

在室內(nèi)環(huán)視距環(huán)境下，閱讀器接收到的標(biāo)簽的RSSI值會因信號傳播距離遠(yuǎn)近和到達(dá)角度差異而產(chǎn)生不同程度的損耗.RSSI損耗值為

(3)

式中：PL(d)為傳播路徑損耗；L(θ)為到達(dá)角度損耗.

閱讀器接收到的RSSI值為

(4)

式中：Pt為標(biāo)簽發(fā)射的信號強(qiáng)度.

通過擴(kuò)大閱讀器天線接收信號的角度可以減少因信號到達(dá)角度而產(chǎn)生的損耗.因此，可以將閱讀器的天線設(shè)計成球面，這樣就可以有效接受各個方向到達(dá)的信號，從而減少信號因到達(dá)角度而產(chǎn)生的損耗.在忽略到達(dá)角度損耗之后可以將RSSI損耗模型簡化為“路徑-損耗”模型.

(5)

所以：

式中：PL(d0)為傳播距離為d0時，信號在自由空間中的路徑損耗；Xσ為陰影衰落(遮蔽因子)，它是均值為0，方差為σ的高斯隨機(jī)變量；n為路徑損耗指數(shù)，與所處環(huán)境相關(guān).

3 環(huán)境布置

傳統(tǒng)參考標(biāo)簽布置方式為對稱式雙層參考標(biāo)簽布置，見圖1，在空間頂部與底部對應(yīng)位置布置參考標(biāo)簽，這一布置方式在空間有較多障礙物時會產(chǎn)生較大誤差，因為空間障礙物主要存在于地面上，會對參考標(biāo)簽產(chǎn)生遮擋，對參考標(biāo)簽的信號強(qiáng)度產(chǎn)生嚴(yán)重干擾，不利于空間物體的定位.

圖1 對稱式雙層參考標(biāo)簽布置

本算法在參考標(biāo)簽的布置上作出改變，分別在空間頂部和側(cè)面布置參考標(biāo)簽，見圖2.頂部參考標(biāo)簽用于對物體進(jìn)行水平方向的位置定位，側(cè)面參考標(biāo)簽用于對物體進(jìn)行垂直方向的位置定位，通過水平方向和垂直方向的定位可以得到待定位物體在空間的位置.

圖2 垂直式立體參考標(biāo)簽布置

頂部參考標(biāo)簽等間距布置，側(cè)面參考標(biāo)簽可以根據(jù)實際環(huán)境進(jìn)行布置.如果空間高度較低，可以在側(cè)面布置3層參考標(biāo)簽將空間分成2層；如果空間高度較高，可以側(cè)面布置4層參考標(biāo)簽將空間分成3層.閱讀器布置在空間的4個角落(頂部A，B點，底部C，D點)，這樣布置可以在占用空間最少的情況下獲取最大范圍的信號覆蓋.

4 三維空間定位算法

4.1 空間分割

圖2為一個長、寬、高為9m×9m×4m的室內(nèi)空間.空間頂部均勻布置16個參考標(biāo)簽，相鄰參考標(biāo)簽之間距離3m.側(cè)面均勻布置12個參考標(biāo)簽，高度方向上參考標(biāo)簽距離2m，寬度方向上參考標(biāo)簽距離3m.一共布置4個閱讀器，分別位于頂部的A，B點和底部的C，D點.圖3～4為頂部和側(cè)面參考標(biāo)簽空間劃分.

圖3 頂部參考標(biāo)簽空間劃分

圖4 側(cè)面參考標(biāo)簽空間劃分

當(dāng)需要對待定位標(biāo)簽進(jìn)行定位時，首先，利用式(2)計算空間頂部參考標(biāo)簽和待定位標(biāo)簽之間RSSI值的歐氏距離，對歐氏距離進(jìn)行升序排列，選出與待定位標(biāo)簽距離最近的4個參考標(biāo)簽作為“最近鄰居”標(biāo)簽，如圖3中的a，b，c，d 4個參考標(biāo)簽，它們在空間底部的投影為a′,b′,c′,d′，所以待定位標(biāo)簽就被定位在長方體abcd a′b′c′d′中.然后，再利用式(2)計算空間側(cè)面參考標(biāo)簽和待定位標(biāo)簽之間RSSI值的歐氏距離，對歐氏距離進(jìn)行升序排列，選出與待定位標(biāo)簽距離最近的4個參考標(biāo)簽作為“最近鄰居”標(biāo)簽，如圖4中的e，f，g，h 4個參考標(biāo)簽，它們在空間另一側(cè)面的投影為e′，f′，g′，h′，所以待定位標(biāo)簽就被定位在長方體efgh e′f′g′h′中.因此，兩個長方體相交部分就是待定位標(biāo)簽所在區(qū)域，即長方體abcd a″b″c″d″(見圖5).所以待定位標(biāo)簽坐標(biāo)滿足如下條件.

(7)

圖5 待定位區(qū)域

4.2 目標(biāo)搜索

目標(biāo)搜索的起始點可以為長方體abcd a″b″c″d″中任意一點，這里選取長方體abcd a″b″c″d″中心點o為目標(biāo)搜索起始點，見圖6.o點坐標(biāo)可由式(8)計算得到.

圖6 目標(biāo)搜索

(8)

以o點為起始點，向x軸、y軸、z軸正負(fù)方向分別前進(jìn)步長s，得到第一次搜索的6個點，它們的坐標(biāo)為

(9)

利用式(6)計算式(9)6個點在4個閱讀器上的虛擬RSSI值，再通過式(1)計算這6個點與待定位標(biāo)簽之間RSSI值的歐氏距離，對歐式距離進(jìn)行升序排列，選出距離最小的點作為下一次搜索的起始點.重復(fù)上訴步驟，直到搜索點與待定位標(biāo)簽之間RSSI值的歐氏距離滿足精度要求，則該搜索點即為最終的定位點.

4.3 算法流程

綜合以上方式，算法的最終流程見圖7.

圖7 算法流程

5 仿真實驗

運(yùn)用MATLAB進(jìn)行仿真，實驗環(huán)境設(shè)置參見4.1.取“最近鄰居”參考標(biāo)簽為4個，即k=4；搜索步長為0.01，即s=0.01m；定位精度要求為0.1，即e=0.1dB.現(xiàn)對該環(huán)境中的8個參考標(biāo)簽(坐標(biāo)見表1)進(jìn)行定位，并用式(10)計算定位誤差.利用式(11)計算標(biāo)準(zhǔn)差.

式中：(x,y,z)為計算坐標(biāo)；(x0,y0,z0)為真實坐標(biāo).

(11)

表1 待定位標(biāo)簽坐標(biāo) m

定位結(jié)果見表2，誤差見圖8.空間分割區(qū)域內(nèi)目標(biāo)點搜索路徑和搜索過程中誤差見圖9～16.

表2 定位結(jié)果 m

圖8 定位誤差

圖9 點(1.2,4.7,0.7)搜索路徑

圖10 點(2.4，3.5,1.6)搜索路徑

圖11 點(3.3,5.9,2.4)搜索路徑

圖12 點(4.1,6.4,0.9)搜索路徑

圖13 點(5.6,2.1,3.5)搜索路徑

圖14 點(6.9,1.7,2.3)搜索路徑

圖15 點(7.4,8.3,1.1)搜索路徑

圖16 點(8.5,7.6,3.1)搜索路徑

從定位的結(jié)果來看，定位點基本在待定位標(biāo)簽附近很小的范圍內(nèi).定位誤差最大不超過0.25 m，最小誤差僅為0.07 m，平均誤差為0.13 m，標(biāo)準(zhǔn)差為0.06.相比于其他室內(nèi)三維定位算法的誤差(CPS算法誤差為0.16～1.4 m，標(biāo)準(zhǔn)差為0.33；空間分割算法誤差為0.27～1.32 m，標(biāo)準(zhǔn)差為0.34；改進(jìn)空間分割算法誤差為0.07～0.76 m，標(biāo)準(zhǔn)差為0.19)有更好的定位精度和算法穩(wěn)定性.精度能夠滿足室內(nèi)空間三維定位的要求.

6 結(jié) 束 語

文中提出的算法中，考慮到實際環(huán)境中室內(nèi)物體主要布置在地面，會對地面參考標(biāo)簽產(chǎn)生干擾，因此將地面參考標(biāo)簽取消，在空間側(cè)面和頂部布置參考標(biāo)簽.通過空間頂部參考標(biāo)簽確定待定位標(biāo)簽x、y坐標(biāo)值的區(qū)域范圍，空間側(cè)面參考標(biāo)簽確定待定位標(biāo)簽z坐標(biāo)值的區(qū)域范圍.在確定的區(qū)域內(nèi)，對待定位標(biāo)簽進(jìn)行目標(biāo)點的搜索.仿真結(jié)果表明，本算法的定位精度比CPS方法、空間分割算法和改進(jìn)空間分割算法的定位精度都要高，而且算法的穩(wěn)定性也優(yōu)于上述3種算法.

[1]SUN GL, CHEN J, GUO W， et al. Signal processing techni-ques in network-aided positioning: a survey of state-of-art positioning designs[J]. IEEE Signal Processing Magazine, 2005, 22(4) : 12-23.

[2]LAU S Y, LIN T, HUANG T, et al. A measurement study of Zigbee-based indoor localization systems under RF interference[C]. Proc of the 4th ACM International Workshop on Experimental Evaluation and Characterization, International Confer-ence on Mobile Computing and Networking. New York: ACM Press, 2009: 35-42.

[3]YUEN C W, BALASUBRAMANIAM N, DIN N M. Improvement of indoor location sensing algorithm using wireless local area network(WLAN)IEEE 802[C]. Proc of the 9th IEEE Malaysia International Conference on Communications. Kuala Lumpur: IEEE Press, 2009: 857-862．

[4]NAN L, BURCIN B G. Performance-based evaluation of RFID- based indoor location sensing solutions of the built environment[J]. Advanced Engineering Informatics, 2011, 24 (3): 535-546.

[5]LING W, LI Y H. Improvement of location methods based on RFID[J]. The Journal of China Universities of Posts and Telecommunications, 2013, 20 (6): 36-41.

[6]HIGHTOWE R J, VAKILI C, GAETANO. Design and calibration of the SponON AD hoc location sensing system[D].Washington: University of Washington, 2001.

[7]ZHAO Y Y, LIU Y H, NI L M. VIRE: active RFID-based localization using virtual reference elimination[C].Proc of International Conference on Parallel Processing,IEEE Press, 2007: 56-63．

[8]KRISHNAKUMAR A, KRISHNAN P. The theory and practice of signal strength-based location estimation[C].Collaborative Computing: Networking, Applications and Worksharing, 2005 International Conference on. San Jose, CA, USA, 2005:10-19.

[9]XIONG J, WANG W, ZHU Z. A new TDOA algorithm based-on taylor series expansion in cellular networks[J]. Journal on Communications, 2005, 25(4): 144-150.

[10]高銳,程良倫,胡莘.一種基于空間分割的無源RFID室內(nèi)定位方法[J].計算機(jī)應(yīng)用研究,2012,9(1):184-186.

[11]董永峰,周艷聰,曹瑩.基于RFID的虛擬參考標(biāo)簽三維室內(nèi)定位算法[J].計算機(jī)工程設(shè)計,2015,36(6):1535-1539.Three-dimensional Indoor RFID Localization Algorithm Based on Region Division and Target Searching

XIANG Zuquan1,2)JIN Chao1,2)XU Huiwen2)

(KeyLaboratoryofHighPerformanceShipTechnology,MinistryofEducation,Wuhan430063,China)1)(SchoolofTransportation,WuhanUniversityofTechnology,Wuhan430063,China)2)

To improve the performance of three-dimensional indoor RFID positioning system, three-dimensional interior positioning algorithm is proposed based on the region division and target searching. Firstly, an area is divided where the target label will be by the reference labels which are arranged at the top and side in the room. Secondly, the central point of the area is picked as a starting point to search target with fixed step along the coordinate axis inX,YandZdirections. By the successive approximation, the coordinates of the target label are found. The simulation results show that the algorithm has small errors in positioning and is more accurate.

region division; target searching; RFID; three-dimensional localization; indoor localization

2016-08-16

TP399 doi:10.3963/j.issn.2095-3844.2016.05.003

向祖權(quán)(1973- )：男，博士，副教授，主要研究領(lǐng)域為船舶先進(jìn)制造技術(shù)