基于粒子群的射頻識別定位算法*

溫佩芝，蘇亭婷，李麗芳，張建軍

(1.桂林電子科技大學計算機科學與工程學院,廣西 桂林 541004；2.中國化工橡膠桂林有限公司,廣西 桂林 541004)

基于粒子群的射頻識別定位算法*

溫佩芝1，蘇亭婷1，李麗芳1，張建軍2

(1.桂林電子科技大學計算機科學與工程學院,廣西 桂林 541004；2.中國化工橡膠桂林有限公司,廣西 桂林 541004)

針對傳統(tǒng)室內(nèi)定位方法定位精度低、開銷大等問題，提出一種基于粒子群的射頻識別定位算法。首先采用高斯濾波對讀取到的信號強度指示RSSI進行預處理，以減少環(huán)境因素對信號的干擾，使RSSI值與標簽實際位置相符。其次，以網(wǎng)格排列的參考標簽作為輔助，通過引入粒子群優(yōu)化算法，經(jīng)多次迭代找出最優(yōu)值，計算出待定位標簽的估計坐標，提高定位精度。最后，采用拉格朗日插值法計算虛擬標簽的信號強度指示值，使其更接近于真實標簽的值。實驗表明，該算法可有效提高定位精度和效率，并減少開銷。

粒子群算法; 高斯濾波；RFID室內(nèi)定位； VIRE；拉格朗日插值

1 引言

隨著無線移動通信技術的發(fā)展及物聯(lián)網(wǎng)技術在各個行業(yè)的應用，室內(nèi)定位技術備受人們關注。目前主要的室內(nèi)定位技術有紅外線、超聲波、基于IEEE 802.11無線定位和射頻識別定位等。其中，射頻識別(RFID)以其低成本、非接觸、非視距且定位精度高等優(yōu)點，逐步成為室內(nèi)定位的優(yōu)選技術。而針對室內(nèi)環(huán)境復雜、多經(jīng)傳播和噪聲干擾較大等問題，如何實現(xiàn)精度高、速度快、開銷少的定位顯得尤為重要。

目前比較典型的RFID室內(nèi)定位方案主要有3D-ID[1]、SporON[2]、LANDMARC[3]和VIRE方法[4]。3D-ID[1]是由Pinpoint公司提出的使用射頻環(huán)形時間來測距，其定位精度可達1 m～3 m，但投資成本過大。SporON[2]是一種基于收信場強分析的聚合算法，可實現(xiàn)三維空間定位，但迄今仍沒有建成完整的SpotON系統(tǒng)。LANDMARC系統(tǒng)[3]是由Ni L M等提出的一種有源RFID室內(nèi)定位系統(tǒng)，采用額外的、便宜的RFID標簽代替以往算法中大量的使用昂貴的RFID閱讀器進行定位，節(jié)省了成本，但需要密集的參考標簽來輔助定位，增加了室內(nèi)信號傳播的干擾性。VIRE算法[4]由Zhao Yi-yang等人基于LANDMARC算法改進的定位方法，是基于接受信號強度指示RSSI(Received Signal Strength Indicator)進行定位的，該算法引入線性插值技術，通過采用虛擬網(wǎng)格坐標決定法和小概率位置排除法來達到更準確的定位。與上述方法相比，其主要優(yōu)點首先是引入虛擬參考標簽的概念，節(jié)省了成本并減少了室內(nèi)信號傳播的干擾；其次，相比于傳統(tǒng)的以檢測到的RSSI值估計測量距離進行定位，該方法以虛擬標簽作為輔助，能有效提高定位精度；最后，該方案較容易實現(xiàn)。但是，VIRE算法中虛擬參考標簽采用虛擬網(wǎng)格坐標決定法，導致邊界區(qū)域的定位誤差較高；同時，實際環(huán)境中信號強度值與距離是復雜的曲線關系，采用線性插值法來估計虛擬參考標簽的信號強度值將導致其估計值與實際值偏差較大，影響最終的定位準確率。針對VIRE算法中存在的問題，目前已有很多學者對其改進[5～7]：文獻[5]提出一種自適應的VIRE算法(AVIRE)，可自適應選取合適的門限值；文獻[6]采用非線性插值法計算虛擬標簽的RSSI值，并用自動獲取的動態(tài)閾值代替VIRE中的固定閾值；文獻[7]提出基于子區(qū)域動態(tài)二次回歸插值的VIRE改進算法(SDQRI)，該方法根據(jù)待定位標簽的位置在子區(qū)域中插入虛擬參考標簽，以縮小插入?yún)^(qū)域，并采用二次回歸曲線的插值方法估算虛擬標簽的RSSI值，最后利用歷史信息矯正待定位標簽位置。SDQRI算法相對VIRE可有效提高定位精度，但是該算法只適合于待定位標簽只有一個或多個位置較為集中的情況，當有多個位置分散的定位標簽時，其高階定位子區(qū)域的選取機制反而會增加算法復雜度和計算量。

針對VIRE算法使用參考標簽數(shù)量大、邊界定位等缺點，本文對其進行改進，運用高斯濾波算法對讀取到的信號強度指示RSSI進行平滑處理，減少因環(huán)境干擾等因素造成的信號強度值上下波動產(chǎn)生的誤差，使其與RFID標簽的實際位置相符；同時，提出基于粒子群算法PSO(Particle Swarm Optimization)的RFID定位算法，避免了VIRE算法的邊界待定位標簽定位誤差大的問題，且此算法可調(diào)參數(shù)少，容易實現(xiàn)；最后，對虛擬參考標簽的信號強度指示RSSI的計算采用拉格朗日插值法，使其更接近于真實標簽的值。

2 基于粒子群的射頻識別定位算法

2.1 預處理

在實際環(huán)境中，某一時間段內(nèi)一個標簽在同一個位置可以接收到n個RSSI值，由于非視距和多徑的影響，室內(nèi)射頻信號具有較高的噪聲污染，導致這些RSSI值具有很大的波動性。理論上，閱讀器獲取到的標簽的RSSI值與兩者之間的距離應該滿足路徑損耗模型[8]，如式(1)、式(2)所示：

(1)

(2)

其中，PL是路徑損耗；n是路徑損耗指數(shù)；d是閱讀器與標簽之間的距離；d0是指參考距離，一般為1 m；PL(d0)是相距d0時的路徑損耗；Xσ是均值為0的高斯隨機變量；Pr指發(fā)射功率。

RSSI值隨距離變化的理論值與受環(huán)境噪聲干擾的實際值分別如圖1所示。

Figure 1 Distance vs. RSSI圖1 RSSI值與距離的關系

高斯濾波[9]能較好地處理高斯噪聲，為了得到更加精確的RSSI值，采用高斯濾波對獲取的RSSI值進行預處理。根據(jù)高斯分布函數(shù)對RSSI進行處理，則信號強度的密度函數(shù)[9]如式(3)所示：

(3)

其中，

根據(jù)工程經(jīng)驗，選擇0.6作為函數(shù)分布值臨界點，則有：

0.6≤F(rssi)≤1

(4)

對滿足公式(4)范圍的RSSI值計算其幾何平均值，即得到最后的優(yōu)化值，即為最終的RSSI值。

2.2 粒子群算法(PSO)

粒子群優(yōu)化算法PSO最早是由Kennedy J和Eberhart R于1995年提出的一種全局優(yōu)化算法[10],是一種智能估計IE(Intelligence Estimation)算法,其源于對鳥群群體運動行為的研究。PSO作為一種高效的優(yōu)化算法，算法簡單，易于實現(xiàn)，可調(diào)參數(shù)少，運行效率高。

2.2.1 粒子群優(yōu)化算法(PSO)原理

PSO算法的基本思想是在一個D維空間中，隨機初始化N個粒子，將每個粒子看作優(yōu)化問題中的一個可行解，每個粒子都在可行解空間中飛行，且有一個速度決定粒子的飛行方向和距離。然后，粒子追隨當前的最優(yōu)粒子在解空間中進行搜索，經(jīng)過多次迭代后，得到最優(yōu)解。在每一次迭代搜索中，粒子主要通過兩個極值更新自己：一個是粒子本身搜索到的最優(yōu)解Pibest；另一個是全部粒子的全局最優(yōu)解Pgbest。

粒子的位置、速度更新公式如下：

(5)

(6)

(7)

其中,tmax是最大迭代次數(shù)，wstart=0.95,wend=0.4。

當?shù)竭_最大迭代次數(shù)T或是其它迭代條件時，得出全局最優(yōu)解為Pgbest及最優(yōu)位置Xgbest。

2.2.2 基于粒子群的射頻識別定位

文獻[12]采用粒子群算法求解無線傳感器中節(jié)點定位問題，受其啟發(fā)，將粒子群算法引入RFID定位中，使用粒子群算法計算待定位標簽的坐標信息。隨機初始化N個粒子，把每一個粒子當成一個虛擬參考標簽，通過用VIRE算法中的線性插值法[4]及參考標簽的RSSI值，計算每一個粒子的RSSI值。與VIRE算法中采用網(wǎng)格式的固定模式插入虛擬參考標簽的方式相比，更具有靈活性，且不具有VIRE算法中邊界待定位標簽的定位誤差大的問題。

假設有K個閱讀器，待定位標簽u的估計位置坐標為(xu,yu)，第k個閱讀器的位置坐標為(xk,yk)，待定位標簽和參考標簽的RSSI值可由室內(nèi)路徑損耗模型[8]模擬獲得。假設第k個閱讀器讀取的待定位標簽的信號強度值為rssik，由插值法計算出第k個閱讀器讀取第n個粒子的信號強度值為rssikn，定義待定位標簽與第n個粒子的歐氏距離為：

(8)

即表示該粒子與待定位標簽的距離關系，Ek越小，則該粒子與待定位標簽越接近。文獻[10]中采用測距距離計算待定位標簽坐標，使得待定位坐標的定位誤差隨測距誤差的增加而增加，因此本文提出的PSO算法，以固定位置的參考標簽作為輔助，以式(8)中歐氏距離Ek為目標函數(shù)，以提高定位精度。本文以歐氏距離Ek與閱讀器的總數(shù)K的比值即Ek/K表示適應度函數(shù)f(x,y)，然后應用PSO算法計算出最佳適應度值fgbest和種群全局最優(yōu)解為Pgbest，即為u的估計坐標位置。

若已知待定位標簽的實際坐標為(x , y)，為了評價算法性能，則采用下式描述定位誤差e。

(9)

2.3 改進的虛擬標簽坐標計算

VIRE算法中對虛擬參考標簽的RSSI值計算采用線性插值的方法，而實際環(huán)境中，RSSI值與距離是復雜的曲線關系，如圖1所示。文獻[11]中的拉格朗日插值法能較好地模擬復雜的非線性曲線，因此采用拉格朗日插值法計算虛擬參考標簽的RSSI值將更接近于實際環(huán)境中的值，從而減少定位誤差。但是，由于非線性插值存在計算量大的缺點，因此提出區(qū)域化的拉格朗日插值法計算虛擬參考標簽的RSSI值，可在一定程度上減少計算量。

假設有NUM個參考標簽，與虛擬標簽相距為L的參考標簽數(shù)量為N，為了減少計算量及提高定位精度，我們選取這N個參考標簽計算虛擬標簽的RSSI值。L作為可調(diào)參數(shù)，若L取值過大會造成計算量及誤差大，若L取值較小則粒子的RSSI值估算不夠精確引起定位誤差大，因此選取合理的L值較為重要。采用公式(10)計算虛擬參考標簽的信號強度值：

(10)

其中，rssikm表示第k個閱讀器讀取的第m個虛擬參考標簽的信號強度值；rssiki表示第k個閱讀器讀取的第i個參考標簽的信號強度值；d表示第k個閱讀器與第m個虛擬參考標簽的距離；dkj表示第k個閱讀器與第j個參考標簽的距離；N是NUM個參考標簽中離待定位標簽較近的參考標簽個數(shù)。

為了測試算法的定位性能，分別模擬不同室內(nèi)空間進行實驗，如表1所示，實驗環(huán)境中四個閱讀器與鄰接的邊界參考標簽的距離都為1 m。在實驗環(huán)境Evn1和Evn2中隨機生成八個待定位標簽坐標，如表2所示。

Table 1 Experimental environments

圖2即為算法對表2中待定位標簽的定位結(jié)果。

序號6、7、8的待定位標簽為邊界標簽，由圖2可見，VIRE算法對邊界待定位標簽的定位誤差明顯較大，影響整體的定位效果；SDQRI定位精度雖然有所提高，但其不適于大量標簽定位；本文算法能有效提高定位精度，在Evn1(a)實驗環(huán)境下，上述八個待定位標簽的定位誤差接近于0，并且隨著空間大小及參考標簽間距的變化，都具有較好的定位效果。

Table 2 Coordinates of tracking tags

Figure 2 Comparison of positioning error in different conditions圖2 定位誤差比較

3 本文算法流程

在獲取虛擬參考標簽的信號強度值以后，我們可以按照本文提出的基于粒子群的定位算法計算出待定位物品的具體坐標。

假設有K個閱讀器，N個參考標簽，初始化M個粒子(即虛擬參考標簽)。采用本文算法計算待定位標簽的坐標，算法流程如圖3所示。

4 實驗評價

4.1 算法參數(shù)分析

為了評價本文算法性能，采用C++對100個隨機坐標進行多次實驗。實驗數(shù)據(jù)根據(jù)經(jīng)典的室

Figure 3 Flow-chart of the proposed approach圖3 本文算法流程圖

內(nèi)路徑損耗模型仿真得到，采用室內(nèi)路徑損耗模型來模擬信號傳播[8]。

圖4為本文算法中適應度函數(shù)值隨迭代次數(shù)變化曲線圖，為了更明確看出適應度函數(shù)值隨迭代次數(shù)的變化，本圖的適應度函數(shù)值采用公式(8)中的歐氏距離Ek比上閱讀器的總數(shù)K，即Ek/K。由圖4可知，當?shù)螖?shù)達到10后，定位誤差幾乎不再變化，而VIRE算法中需要900個虛擬標簽才能達到較好的定位效果，相比之下，本文算法計算量并不大。

Figure 4 Iterations vs. fitness value圖4 適應度值隨迭代次數(shù)的變化

圖5為采用拉格朗日插值法計算虛擬標簽RSSI值時定位誤差隨距離L的變換曲線圖。

Figure 5 Positioning errors vs. L圖5 定位誤差隨距離L的變化

可見，合理的L取值可減少計算量和提高定位精度。

4.2 實驗結(jié)果分析

通過對100個隨機標簽的多次實驗，計算得出平均定位誤差，將本文算法與VIRE算法[4]、SDQRI算法[7]比較，結(jié)果如表3所示。實驗結(jié)果表明，本文算法可有效提高定位精度、減少參考標簽使用量，并且在不同室內(nèi)實驗環(huán)境下魯棒性較強。

Table 3 Comparison of average positioning errors

5 結(jié)束語

本文針對目前室內(nèi)定位效果較好的VIRE算法中存在的不足，提出了一種基于粒子群的RFID室內(nèi)定位算法。實驗結(jié)果表明，本文算法能有效克服VIRE的不足，使用相對較少的參考標簽實現(xiàn)高效穩(wěn)定的高精度定位。但是，由于實驗條件的限制，本文實驗數(shù)據(jù)是通過室內(nèi)路徑損耗模型來獲取，并未在真實環(huán)境中驗證，如何使本算法能夠在真實的不同復雜程度的實際環(huán)境中應用，是我們下一步研究的重點。

[1] Werb J, Lanzl C. Designing a positioning system for finding things and people indoors[J]. Journal of IEEE Spectrum, 1998, 35(9):71-78.

[2] Hightower J, Want R, Borriello G. SpotON:An indoor 3D location sensing technology based on RF signal strength[R]. UW CSE 00-02-02. Seattle, WA:University of Washington, 2000.

[3] Ni L M, Liu Yun-hao, Lau Y C, et al. LANDMARC:Indoor location sensing using active RFID[J]. Wireless Networks,2004,10(6):701-710.

[4] Zhao Yi-yang, Liu Yun-hao, Ni L M. VIRE:Active RFID-based localization using virtual reference elimination[C]∥Proc of International Conference on Parallel Processing, 2007:56.

[5] Zhu Feng-juan.Research of indoor positioning algorithm based on the RFID technology[D].Guangzhou:South China University of Technology, 2010.(in Chinese)

[6] Chen Bing. The design of passive RFID location system and improvement of VIRE algorithm[D]. Tianjin:Tianjin University, 2012.(in Chinese)

[7] Shi Wei-guang. Research of indoor localization algorithm based on radio frequency identification technology[D]. Tianjin:Tianjin University, 2012.(in Chinese)

[8] Seidel S Y, Rappaport T S. 914 MHz path loss prediction models for indoor wireless communications in multifloored buildings[J]. IEEE Transactions on Antennas and Propagation,1992,40(2):207-217.

[9] Zhang Jian-wu, Zhang Lu, Ying Ying, et al. Research on distance measurement based on RSSI of ZigBee[J]. Chinese Journal of Sensors and Actuators, 2009, 22(2):285-288.(in Chinese)

[10] Kennedy J, Eberhart R. Particle swarm optimization[C]∥Proc of IEEE International Conference on Neural Networks, 1995:1942-1948.

[11] Mathews J H, Fink K D. Numerical methods using MATLAB[M]. 4th edition. Zhou Lu,Chen Yu, Qian Fang, et al, translation. Beijing:Electronic Industry Press, 2005.(in Chinese)

[12] Chuang P J, Wu Cheng-pei. An effective PSO-based node localization scheme for wireless sensor networks[C]∥Proc of the 9th International Coference on Parallel and Distributed Computing, Applications and Technologies,2008:187-194.

[13] Chen Gui-min, Jia Jian-yuan, Han Qi. Study on the strategy of decreasing inertia weight in particle swarm optimization algorithm[J]. Journal of Xi’an Jiaotong University, 2006,40(1):53-56.(in Chinese)

附中文參考文獻：

[5] 朱鳳娟. 射頻識別(RFID)技術的室內(nèi)定位算法研究[D]. 廣州:華南理工大學, 2010.

[6] 陳冰. 無源RFID 定位系統(tǒng)搭建與VIRE算法優(yōu)化[D]. 天津:天津大學, 2012.

[7] 史偉光. 基于射頻識別技術的室內(nèi)定位算法研究[D]. 天津:天津大學, 2012.

[9] 章堅武,張璐,應瑛,等. 基于ZigBee的RSSI測距研究[J]. 傳感技術學報,2009, 22(2):285-288.

[11] Mathews J H, Fink K D. 數(shù)值方法(MATLAB版)[M].第四版.周璐,陳渝,錢方，等譯. 北京:電子工業(yè)出版社,2005.

[13] 陳貴敏,賈建援,韓琪. 粒子群優(yōu)化算法的慣性權值遞減策略研究[J]. 西安交通大學學報,2006,40(1):53-56.

WENPei-zhi,born in 1963,post doctor,professor,her research interests include internet of things, graphic and image processing, and target detection and recognition.

蘇亭婷(1988-),女,河南周口人，碩士，研究方向為物聯(lián)網(wǎng)。E-mail:suting1222@163.com

SUTing-ting,born in 1988,MS,her research interest includes internet of things.

李麗芳(1978-),女,廣西恭城人，碩士，高級工程師，研究方向為信息處理。E-mail:lilifang@guet.edu.cn

LILi-fang,born in 1978,MS,senior engineer,her research interest includes information processing.

張建軍(1970-),男,遼寧阜新人，高級工程師，研究方向為供應鏈管理和特種輪胎。E-mail:xmrs1011@sina.com

ZHANGJian-jun,born in 1970,senior engineer,his research interests include supply chain management, and special tyre.

PSO-basedRFIDpositioningalgorithm

WEN Pei-zhi1,SU Ting-ting1,LI Li-fang1,ZHANG Jian-jun2

(1.School of Computer Science and Engineering,Guilin University of Electronic Technology,Guilin 541004；2.China National Chemical Rubber Guilin Corporation Limited,Guilin 541004,China)

In order to solve low positioning accuracy and high cost in traditional positioning methods, the PSO-based RFID positioning approach is proposed. Firstly,aiming at the interference of environmental factors on the signals,Gaussian Smoothing Filter is adopted to preprocess RSSI(

Signal Strength Indicator) values.Secondly,based on grid-style reference tags,PSO algorithm is introduced to estimate the optimal positions of tracking tags by several iterations,thus improving the positioning accuracy.Finally,the RSSI values of virtual reference tags are calculated by Lagrange interpolation,so as to be more close to the values of real tags.Experimental results demonstrate that the proposed approach has excellent accuracy,high efficiency and low cost in indoor positioning.

PSO;Gaussian filtering;RFID indoor positioning;VIRE;Lagrange interpolation

1007-130X(2014)05-0917-06

2012-11-23;

：2013-03-29

廣西科技計劃資助項目(桂科攻11107006-10)；廣西自然科學基金資助項目(桂科自0991240)

TP391.45

：A

10.3969/j.issn.1007-130X.2014.05.022

溫佩芝(1963-),女,廣西靈山人，博士后，教授，研究方向為物聯(lián)網(wǎng)、圖形圖像處理和目標檢測識別。E-mail:wpzsia@163.com

通信地址：541004 廣西桂林市桂林電子科技大學計算機科學與工程學院

Address:School of Computer Science and Engineering,Guilin University of Electronic Technology,Guilin 541004,Guangxi,P.R.China