基于區域劃分和目標搜索的室內RFID三維定位算法

向祖權 靳 超 許慧文

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

?

基于區域劃分和目標搜索的室內RFID三維定位算法

向祖權1,2)靳 超1,2)許慧文2)

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

為提高室內三維定位系統的性能，提出一種基于區域劃分和目標搜索的室內RFID三維定位算法.通過布置在室內頂部和側面的參考標簽劃分一個待定位標簽所在的區域，選取該區域中心點作為目標搜索的初始點，向x，y，z軸正負方向對待定位標簽進行搜索，通過不斷逼近，最終確定待定位標簽的坐標.仿真實驗表明，該算法定位誤差小，穩定性優良.

區域劃分；目標搜索；射頻識別；三維定位；室內定位

0 引 言

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

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

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

1 “最近鄰居”參考標簽選擇

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

假設有m個閱讀器，n個參考標簽，p個待定位標簽，每個閱讀器都可以讀到參考標簽和待定位標簽的信號強度值.

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

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

(1)

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

(2)

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

2 RSSI損耗模型

在室內環視距環境下，閱讀器接收到的標簽的RSSI值會因信號傳播距離遠近和到達角度差異而產生不同程度的損耗.RSSI損耗值為

(3)

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

閱讀器接收到的RSSI值為

(4)

式中：Pt為標簽發射的信號強度.

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

(5)

所以：

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

3 環境布置

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

圖1 對稱式雙層參考標簽布置

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

圖2 垂直式立體參考標簽布置

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

4 三維空間定位算法

4.1 空間分割

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

圖3 頂部參考標簽空間劃分

圖4 側面參考標簽空間劃分

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

(7)

圖5 待定位區域

4.2 目標搜索

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

圖6 目標搜索

(8)

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

(9)

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

4.3 算法流程

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

圖7 算法流程

5 仿真實驗

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

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

(11)

表1 待定位標簽坐標 m

定位結果見表2，誤差見圖8.空間分割區域內目標點搜索路徑和搜索過程中誤差見圖9～16.

表2 定位結果 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)搜索路徑

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

6 結 束 語

文中提出的算法中，考慮到實際環境中室內物體主要布置在地面，會對地面參考標簽產生干擾，因此將地面參考標簽取消，在空間側面和頂部布置參考標簽.通過空間頂部參考標簽確定待定位標簽x、y坐標值的區域范圍，空間側面參考標簽確定待定位標簽z坐標值的區域范圍.在確定的區域內，對待定位標簽進行目標點的搜索.仿真結果表明，本算法的定位精度比CPS方法、空間分割算法和改進空間分割算法的定位精度都要高，而且算法的穩定性也優于上述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室內定位方法[J].計算機應用研究,2012,9(1):184-186.

[11]董永峰,周艷聰,曹瑩.基于RFID的虛擬參考標簽三維室內定位算法[J].計算機工程設計,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

向祖權(1973- )：男，博士，副教授，主要研究領域為船舶先進制造技術