一種快速收斂的RFID標簽定位算法

李　強，王　玫

(桂林電子科技大學 信息與通信學院，廣西 桂林　541004)

?

一種快速收斂的RFID標簽定位算法

李強，王玫

(桂林電子科技大學 信息與通信學院，廣西 桂林541004)

為了降低掃描次數和擺脫定位對RSSI值的依賴，提出了一種快速收斂的RFID標簽定位算法。通過手持RFID閱讀器掃描目標，以讀寫邊界的交點求得目標定位點，并結合組合數學求出滿足定位點的解集，以均值優化得到精確定位坐標。實驗結果表明，該算法呈現了快速的收斂性，且定位誤差低至8 cm。

RFID；室內定位；組合數學；均值優化

隨著人們對基于位置服務(location based service，簡稱LBS)的需求日益增加以及無線通信技術的快速發展，無線定位技術成為一個研究熱點。而很多室內定位技術定位精度不高，不能滿足室內定位的需求，這是由于定位節點和參考節點之間的無線通信信道十分復雜，無線電信號通過多徑傳播以及定位節點或周圍散射體的運動所引起的干擾造成的[1]。射頻識別技術(RFID)憑借非接觸、非視距、成本低且定位精度高的特點，得到越來越多的關注，成為優選的室內定位技術。RFID無源標簽自適應似然分布算法[2]是根據信號強度值(RSSI)把閱讀器讀寫區域分為3個可能性區域，以不同的概率描述不同區域，閱讀器通過重復移動的方式查找最可能的標簽位置。這種方法必須收集射頻標簽，得到許多區域分布數據，以提高RFID標簽的定位精度，并且監測RSSI需要的硬件成本難以控制。CRR標簽定位方法[3]首先確定閱讀器的RSSI通信距離模型，然后通過記錄點和斜率確定目標所在直線，2次測量得出2條直線的交點即為目標標簽的實際位置。該方法容易受到環境的干擾，定位精度波動大，穩定性較差。RFID動態定位方法[4]不斷讀取目標標簽和參考標簽，以閱讀器輻射邊緣的交點實現定位，無需記錄RSSI數據，但需要多點收集數據，操作復雜，定位誤差大。為此，提出一種快速收斂的RFID標簽定位算法，改進了通過移動RFID閱讀器和無源標簽進行RSSI定位的方法，無需記錄RSSI，只需記錄讀到標簽與否，對定位目標進行數次掃描，使定位目標計算值快速收斂，完成精確定位。

1　快速收斂算法

1.1定位模型

在倉庫或商店的地面、貨架上，有規律地部署一系列RFID標簽，這些參考標簽有自己的ID，每個ID對應一個絕對坐標，用來輔助目標貨物的定位。定位貨物也貼有標簽，放在場景的任意位置。RFID標簽覆蓋掃描定位場景如圖1所示。倉庫管理人員只需手持便攜式閱讀器，用相應的算法處理收集到的數據，即可實現對目標貨物的搜尋與定位。

圖1　RFID標簽覆蓋掃描定位場景Fig.1　RFID tag cover scanning scene

在3 m×3 m的實驗范圍內，該定位方法定位誤差小于8 cm。該系統僅運用一個讀寫器和參考標簽便可以定位，具有系統構成簡單、定位精度高、實用性強等特點。

1.2RFID天線輻射原理

閱讀器天線的輻射范圍(閱讀范圍)是RFID最重要的性能指標之一，它取決于很多物理和幾何參數，也決定定位算法的優劣。Friis自由空間公式[5]為：

(1)

(2)

其中：PRX,tag為標簽的接收功率；PTX,reader為閱讀器發射功率；Greader為閱讀器發射天線增益；Gtag為標簽接收天線增益；Tb為散射傳輸損耗；λ為波長；PRX,reader為閱讀器接收功率。由式(1)、(2)可知，閱讀范圍取決于閱讀器的發射功率、標簽的靈敏度、實際增益、天線的方向及周圍的場景等因素。對于無源超高頻RFID系統，無源標簽的靈敏度比閱讀器的靈敏度低得多，因此，閱讀器的輻射范圍至關重要，決定了整個系統的最大工作范圍。超高頻RFID閱讀器的閱讀區域在實際環境中近似為橢圓體[6]，具有方向性，其橢圓長軸是最大增益的1/2，短軸與天線主平面的波瓣寬度有關。圖2為自由空間的RFID閱讀區域幾何結構。天線放置在x=0處，朝x>0方向輻射。半功率帶寬點A坐標為：

其中：rmax為自由空間的最大閱讀距離；Wxz為閱讀器天線在xz平面的半功率波束寬度。

圖2　自由空間的RFID閱讀區域幾何結構Fig.2　Geometry of free space RFID reading area

根據RFID天線的結構特性可知，閱讀器的閱讀范圍在二維截面上近似橢圓，且具有旋轉對稱性。

1.3邊緣檢測

閱讀器的讀寫范圍由掃描覆蓋的參考標簽決定，只記錄目標落在閱讀器讀寫邊緣的標簽，因此，可采用邊緣檢測算子進行運算。拉普拉斯算子[7]是一種二階導數算子，被認為是微分法中利用平滑二階微分檢測圖像邊緣最成功的一種算子，它通過尋找圖像灰度值二階微分的過零點檢測邊緣點。一個二維圖像函數的拉普拉斯變換是各向同性的二階導數，定義為：

(3)

其原理是：一個代表灰度緩慢變化的圖像函數f(x,y)，經過一次微分形成單峰函數，峰值位置對應灰度變化最大的點，即邊緣點，若再進行一次微分，峰值點的微分值為0，而兩側的微分值為一正一負。很顯然，求解一個函數的二階導數的零點值就能找出邊緣點。

1.4曲線擬合

最小二乘法[8-9]是在隨機誤差為正態分布時，由最大似然法推出的一種最優估計技術，它可使測量誤差的平方和最小，因此，也被視為從一組測量值中求出一組未知量的最可信賴的方法之一。

設橢圓的一般式為：

ax2+bxy+cy2+dx+ey+f=0。

(4)

若經過邊緣檢測求得標簽覆蓋范圍的邊緣點為Ri(x,y)，i>5，直接對邊緣檢測后的離散點進行最小二乘處理，可得到方程(4)的各系數，即求目標函數的

(5)

最小值來確定各系數。由極值原理可知，欲使f(a,b,c,d,e,f)值為最小,必有

(6)

通過求解式(6)可得到橢圓系數，從而求出橢圓方程。

1.5橢圓匹配

組合數學[10]是以離散結構為主要研究對象的一門學科，它主要研究滿足一定條件的組態(一種安排)的存在性、計數及構造等方面的問題。概率論的組合分析方法和技巧能夠解算出更多滿足定位條件的點集，使定位值在多次迭代中快速收斂。

(7)

圖3為RFID掃描范圍旋轉定位模型。2個閱讀器邊界交點O作為目標定位點，T為閱讀器旋轉的位置。2個交點的區別在于：旋轉點T處于橢圓的長軸，距離橢圓幾何中心最遠，利用橢圓的這一幾何結構可以直接篩選出定位點O。由于信號在無線信道中的衰減規律呈非線性，RFID閱讀器對處于其邊緣標簽的成功通信也具有概率性，邊界的橢圓還原會有不同。圖3中實線的橢圓是待定位目標標簽剛進入閱讀器閱讀范圍時被還原出來的，虛線的橢圓是待定位目標標簽剛離開閱讀器閱讀范圍時被還原出來的。為了提高定位精度，可采用引入多次測量求平均值的方式。本研究引入組合概念是為了減少掃描次數，使定位誤差快速收斂于理想值。

圖3　RFID掃描范圍旋轉定位模型Fig.3　Rotary positioning model of RFID scanning range

(8)

作為定位優解。其中：(xi,yi)為滿足定位條件的點的解集；(x0,y0)為優化定位點。不進行組合配對時，定位優解為：

(9)

1.6算法流程

算法包含了采集標簽信息、邊緣檢測、曲線擬合、組合分析等。其中，采集標簽信息包括采集待定位目標標簽剛進入和剛離開閱讀器閱讀范圍時的所有參考標簽信息。邊緣檢測算法使用拉普拉斯算子。曲線擬合是把邊緣點擬合成橢圓的形狀。組合分析是為了在較低的掃描次數下也能解算出更多滿足定位的點集，點數越多均值優化后定位精度越高。算法流程如圖4所示。

圖4　算法流程Fig.4　Flow chart of algorithm

2　實驗與結果分析

2.1實驗設計

實驗儀器為1個超高頻RFID(915 MHz)讀寫器、幾十個電子標簽、PC機和定位系統軟件。借助參考標簽在小型的室內場景(3 m×3 m)均勻分布，其中正方形單元的間距L為40、60 cm，待定位標簽放在定位場景的任意位置，不考慮閱讀器和標簽體積的大小(作為質點處理)，定位場景如圖1所示。在定位場景中移動閱讀器，通過串口線將數據傳給計算機處理，本實驗的優勢是不需要收集、處理RSSI值，只需記錄、處理掃描到的標簽的ID，一旦目標標簽進入RFID閱讀器的最長通信范圍，就可以估計目標的位置，計算其與真實值的誤差。距離誤差用歐式距離計算，

(10)

其中：(xreal,yreal)為目標標簽真實坐標；(x0,y0)為目標定位優解坐標。

2.2組合后與組合前的定位結果對比

本實驗是組合前后的定位誤差對比，重點是收斂速度的對比。不同參考標簽間距L的定位誤差如圖5所示。

圖5　不同參考標簽間距的定位誤差Fig.5　Positioning error in different reference tags intervals

由圖5可知：1)定位精度隨著掃描次數的增加而提高，為提高定位精度，可以適當增加掃描次數；2)參考標簽間距L越小精度越高，這與閱讀器天線的輻射有關，輻射越遠，覆蓋邊界在多徑效應的影響下越不規則；3)組合后得到的定位結果快速逼近目標，第2次掃描得到的定位精度可與組合前的第4、5次掃描得到的精度媲美，所以，本算法只需掃描2次就可得到較高的定位精度。

2.3與其他定位方法對比

實驗設定掃描次數為2，參考標簽間距L=60 cm。圖6為4種定位算法在誤差范圍內的定位成功率。

圖6　不同算法的定位成功率Fig.6　Positioning rate of different algorithms

從圖6可看出，自適應似然分布算法誤差為80 cm時的定位成功率達到100%，誤差為20 cm時的定位成功率達到80%，即該算法成功定位時誤差都低于80 cm，并且有80%的概率把誤差控制在20 cm內，定位性能比較好，但是該定位算法用機器掃描，且定位過程復雜。動態定位方法誤差為20、40、60、80 cm時的定位成功率分別為7%、24%、50%、82%，誤差波動大，算法有待優化。VIRE算法[11]沒有成功定位到20 cm的誤差，在40 cm內的定位成功率也僅為10%，該算法使用RSSI參數定位，而RSSI易受到環境的干擾，影響了定位精度。本算法定位性能最好，誤差在20、40、60、80 cm時定位成功率分別為88%、90%、97%、100%。雖然實驗場景相比其他定位方法小，但是該算法可以通過增加參考標簽的數量來拓展定位范圍。

實際上，本算法也受RSSI的影響，只是影響較小，因為不需要RSSI參數定位。圖7為無線信號在多徑傳播及衰減后進行4次掃描的定位模型。由于多徑環境以及節點和周圍物體的干擾，其并不遵循圖3所示的標準旋轉模型，但仍可以結合橢圓中心的幾何性質解算出橢圓交點的點集。以實體無源標簽在真實環境中的響應擬合RFID閱讀器的覆蓋范圍，能夠反應真實的環境，比虛擬標簽更具有可行性。

圖7　實際環境中的定位模型Fig.7　Positioning model in actual environment

3　結束語

為降低掃描次數和擺脫定位對RSSI值的依賴，提出一種快速收斂的RFID標簽定位算法。該算法簡單，成本低廉，結合概率論的組合匹配，實現了理想的定位效果。實驗結果表明，該方法在控制成本、提高精度等方面具有巨大的優勢。未來將繼續深入研究該算法，將其拓展到三維空間，滿足更高的定位需求。

[1]顧宗海.基于RSSI測距的室內定位算法研究[D].鄭州：鄭州大學，2011:6-11.

[2]OTA Y,HORI T,ONISHI T,et al.An adaptive likelihood distribution algorithm for the localization of passive RFID tags[J].Ieice Transactions on Fundamentals of Electronics Communications & Computer,2008,91A(7):1666-1675.

[3]WADA T,UCHITOMI N,OTA Y,et al.A novel scheme for spatial localization of passive RFID tags; communication range recognition (CRR) Scheme[J].Ieice Transactions on Fundamentals of Electronics Communications & Computer Sciences,2010,93A(9):1660-1669.

[4]李程，錢松榮.射頻識別動態定位方法[J].通信學報，2013(4):144-148.

[5]JUNG J Y,KIM H,LEE H S,et al.An UHF RFID tag with long read range[C]//2009 EuMC Microwave Conference,2009:1113-1116.

[6]MARROCCO G,GIAMPAOLO E D,ALIBERTI R.Estimation of UHF RFID reading regions in real environments[J].IEEE Antennas & Propagation Magazine,2010,51(6):44-57.

[7]魏偉波，芮筱亭.圖像邊緣檢測方法研究[J].計算機工程與應用，2006,30:88-91.

[8]FITZGIBBON A,PILU M,FISHER R B.Direct least square fitting of ellipses[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1999,21(5):476-480.

[9]閆蓓，王斌，李媛.基于最小二乘法的橢圓擬合改進算法[J].北京航空航天大學學報，2008,34(3):295-298.

[10]毛俊超.概率方法在組合數學中的應用[D].青島：中國海洋大學，2007:1-3.

[11]SEYYEDI S,AKBARI B,ARAB E,et al.Using virtual reference tags to improve the accuracy of active RFID-Based positioning systems[C]//2014 Fourth International Conference on Communication Systems and Network Technologies,2014:1078-1081.

編輯：翁史振

A rapid convergent RFID localization algorithm

LI Qiang, WANG Mei

(School of Information and Communication Engineering, Guilin University of Electronic Technology, Guilin 541004, China)

In order to reduce the number of scan, and do not use the RSSI value, a rapid convergent RFID localization algorithm is proposed. It scans the target tag with a handheld RFID reader. The target locating point can be obtained by the intersection of the reader’s reading boundary. The algorithm combines the combination mathematics to find all the solutions of the fixed point, and average optimization is used to get accurate positioning coordinate. The experimental results show that this algorithm converges fast, and the positioning error is as low as 8 cm.

RFID; indoor positioning; combination mathematics; average optimization

2016-02-25

國家自然科學基金(61172054)

王玫(1963-)，女，山西太原人，教授，博士，研究方向為擴頻通信、混沌通信、超寬帶通信和室內定位。E-mail:mwang@guet.edu.cn

TN911.23

A

1673-808X(2016)04-0265-05

引文格式：李強，王玫.一種快速收斂的RFID標簽定位算法[J].桂林電子科技大學學報，2016,36(4):265-269.