基于克里金插值的自適應VIRE室內(nèi)定位算法研究

顧軍華 ，許 鵬 ，董 瑤，董永峰，白振東

1.河北工業(yè)大學 計算機科學與軟件學院，天津 300401

2.河北工業(yè)大學 電子信息工程學院，天津 300401

3.河北省大數(shù)據(jù)計算重點實驗室，天津 300401

1 引言

隨著普適計算的不斷深入和發(fā)展，基于位置信息的服務越來越受到人們的關注，基于RFID、802.11b、藍牙、超寬帶等技術(shù)的定位系統(tǒng)相繼被提出[1-3]?，F(xiàn)有的RFID定位算法大多是基于信號強度指示（Received Signal Strength Indicator，RSSI）來估計待定位物體的位置[4]，比較經(jīng)典的算法有LANDMARC[5]和VIRE[6]。LANDMARC采用了充當定位參考點的參考標簽輔助定位，VIRE在此基礎上引入了虛擬參考標簽，減小了參考標簽間的相互干擾[7-8]，提高了定位準確性。但VIRE算法的缺點在于擴充參考標簽的RSSI數(shù)據(jù)集時采用的是線性插值，而RSSI與距離之間并非線性關系[9]，并且虛擬標簽消除過程中的閾值參數(shù)需要通過反復調(diào)整實驗獲得，此方法過于復雜，當應用場景環(huán)境變化較大時，固定的閾值便會失效，導致誤差增大。

針對上述問題，本文提出一種對VIRE算法的改進算法——基于克里金插值的自適應VIRE算法。本文算法采用一種基于統(tǒng)計學方式計算的克里金插值法估計虛擬標簽[10-11]。采用變異函數(shù)為高斯模型的克里金插值法，不僅考慮待估計位置數(shù)據(jù)與已知位置數(shù)據(jù)的相互關系，而且還考慮變量的空間相關性，更準確估計虛擬標簽數(shù)據(jù)。本文算法還提出一種自適應閾值調(diào)整策略，通過預先估計虛擬標簽消除后鄰近標簽個數(shù)的范圍，逐步調(diào)整閾值大小，使鄰近標簽數(shù)量保持在最佳狀態(tài)，更準確排除干擾。最后通過對比實驗驗證本文提出的基于克里金插值的自適應VIRE算法更具有優(yōu)越性。

2 VIRE算法簡介

VIRE算法由經(jīng)典的LANDMARC算法改進而來，采用了充當定位參考的參考標簽輔助定位，并通過線性插值法擴充參考標簽密度，之后消除不可能的位置，由剩下的“鄰近標簽”[12]加權(quán)平均來校正待定位標簽的不確定性，使得算法在定位過程中受外界環(huán)境變化的影響較小，具有較高的穩(wěn)定性。VIRE具體實現(xiàn)如下：

在定位區(qū)域按長方形網(wǎng)格狀鋪設已知位置信息的參考標簽，將每4個實參考標簽所覆蓋的標簽網(wǎng)格單元進一步分成N×N（N為虛擬標簽密度）的等大虛擬網(wǎng)格單元，每個虛擬網(wǎng)格端點看成一個虛擬標簽。實參考標簽的RSSI通過閱讀器測得，坐標為已知量。設某一坐標(i,j)(i,j∈R)落在參考標簽網(wǎng)絡中，四周有4個實參考標簽所圍繞，實參考標簽的RSSI通過閱讀器獲得，通過線性插值在已知的實參考標簽的基礎上計算出該區(qū)域的虛擬標簽的坐標和RSSI。虛擬參考標簽在水平方向和垂直方向上的RSSI由式（1）和式（2）求出。

其中 p=i%N(0≤p≤N-1)為待估計虛擬參考標簽與已知起始標簽在X軸的間隔，q=j%N(0≤q≤N-1)為待估計虛擬參考標簽與已知起始標簽在Y軸的間隔；參數(shù) a=?i/N?，b=?j/N?，? ?表示向下取整。

虛擬標簽網(wǎng)格建立后對應的可得到第l個閱讀器讀取的參考標簽信號強度矩陣Sl，將該矩陣每個元素與第l個閱讀器讀取的待定位標簽信號強度θl做差，如結(jié)果在特定閾值以下，記1，反之記0，得到的矩陣稱為鄰近圖（proximity map）[6]。取全部L個鄰近圖的交集為待定位標簽所在的可能性最大的區(qū)域。引入兩個權(quán)重因子ω1i、ω2i。

其中Rl(Ti)是第l個閱讀器得到第i個虛擬參考標簽的RSSI值，Rl(θ)是第l個閱讀器讀取待定位標簽的RSSI。

將連接在一起的標簽位聚為一類，nci是第i類中的標簽數(shù)，na是聚類后的類數(shù)，得到權(quán)值ω2i。ωi=ω1i×ω2i作為最終權(quán)值，得待定位標簽坐標為：

3 基于克里金插值的自適應VIRE算法

3.1 基于克里金插值的虛擬標簽計算

克里金（Kriging）插值法[10-11]是建立在變異函數(shù)理論分析基礎上，對有限區(qū)域內(nèi)的變量取值進行最優(yōu)線性無偏估計的一種方法?？死锝鸱ú粌H考慮待估計位置數(shù)據(jù)與已知位置數(shù)據(jù)的相互關系，而且還考慮變量的空間相關性，試用克里金插值法計算虛擬參考標簽RSSI。

設Xi是定位區(qū)域中第i(1≤i≤M)個參考標簽位置，各標簽特征屬性RSSI為R(Xi)，那么，虛擬標簽點X0的RSSI值的無偏估計可用下式表示：

λi為該實參考標簽對插值點的權(quán)重。普通克里金插值的權(quán)重系數(shù)由以下兩個方程決定：

式中，C0為塊金常數(shù)，C為拱高，變程h=當C0=0，C=1時，稱為標準高斯模型。

通過上式求得各變異函數(shù)值γ(h)代入方程組（7），可得拉格朗日乘數(shù)μ和加權(quán)系數(shù)λi，再代入式（6）可得虛擬標簽點X0的RSSI估計值。

式中γ(Xi,Xj)是R(X0)在實參考標簽Xi和Xj之間的半方差[11]，γ(X0,Xi)是R(X0)在實參考標簽點Xi和虛擬標簽點X0和之間的半方差，這些量都從適宜的變異函數(shù)計算得到。μ是極小化處理時的拉格朗日乘數(shù)。在內(nèi)插計算過程中，為減少計算量，通常采用理論模型來擬合變異函數(shù)，擬合模型分為球型模型、環(huán)狀模型、指數(shù)模型和高斯模型。高斯模型更符合標簽RSSI與距離的關系，在這里采用高斯模型：

3.2 自適應閾值調(diào)整策略

閾值S作為VIRE算法中一個至關重要的參數(shù)，本文提出一種自適應閾值調(diào)整策略，步驟如下：

（1）估計虛擬參考標簽消除過程后鄰近標簽數(shù)量nV的范圍是最大鄰近標簽數(shù)，L是定位區(qū)域的閱讀器數(shù)量，M為實參考標簽總數(shù)，V為虛擬參考標簽總數(shù)，最小鄰近標簽數(shù)取最大鄰近標簽數(shù)的0.3倍。

（2）遍歷虛擬標簽矩陣，找到L個閱讀器讀取到待定位標簽的L個RSSI值與虛擬標簽矩陣中的RSSI值的最大差值，最大差值作為初始閾值S。

（3）進行虛擬參考標簽消除過程，統(tǒng)計最終鄰近圖中剩余的鄰近標簽數(shù)量nV。

（4）判斷nV是否滿足鄰近標簽數(shù)量范圍，如果nV>Nmax，則減小閾值返回第（3）步；如果nV<0.3?Nmax，則增大閾值，返回第（3）步。

（5）如果滿足鄰近標簽數(shù)量范圍0.3?Nmax

算法流程如圖1所示。

3.3 改進后的算法流程

基于克里金插值的自適應VIRE室內(nèi)定位算法流程如下：

（1）獲取實參考標簽RSSI矩陣。

（2）利用克里金插值擴充矩陣以獲得大量虛擬參考標簽。

（3）采用虛擬標簽RSSI與待定位標簽的最大差值作為初始閾值，通過本文提出的自適應閾值調(diào)整策略迭代計算最佳閾值。

（4）當取得最佳閾值的同時也獲得了對應鄰近標簽的集合，最后計算鄰近標簽權(quán)重因子，待定位標簽的估計坐標即為所有鄰近標簽坐標的加權(quán)和。

4 實驗環(huán)境構(gòu)建

本文采用探感物聯(lián)公司生產(chǎn)的433 MHz有源RFID設備進行實驗，閱讀器采用R701型全向天線閱讀器，標簽采用T702型有源標簽，有源標簽由于自身攜帶電源，可主動向閱讀器發(fā)信，并且在室內(nèi)環(huán)境下有效讀取半徑可達50 m。

模擬搭建辦公室實驗環(huán)境，定位區(qū)域為4.5 m×4.5 m，將4個閱讀器置于區(qū)域四角，16個標簽放置成4×4陣列作為參考標簽，實驗測試了50個待定位，選取9個有代表性的待定位標簽做詳細說明，如圖2所示。閱讀器將采集的RSSI和標簽序號等數(shù)據(jù)通過局域網(wǎng)傳輸?shù)截撠煍?shù)據(jù)處理的PC端，算法通過Matlab軟件編程實現(xiàn)。

為驗證基于克里金插值的自適應VIRE算法的優(yōu)越性，設計對比實驗，實驗選取經(jīng)典VIRE算法、基于牛頓插值的VIRE算法與本文算法做對比。若待定位標簽的真實坐標為(x0,y0)，進行定位計算得到的坐標為(x',y')，則定義誤差來描述算法性能。

經(jīng)典的多項式插值法主要有拉格朗日插值、牛頓插值等。由插值多項式的存在唯一性定理可知，實際上這兩種插值法式同一種方法的兩種變形，其構(gòu)造擬合函數(shù)的思路是相同的，兩者計算結(jié)果也相同[13-14]。拉格朗日插值計算過程中增加一個節(jié)點時需要重新計算全部基函數(shù)，而牛頓插值法具有繼承性，在插值節(jié)點增加后，只需在原有基礎上計算均差表中新的一行即可，且插值余項也較容易，所以實驗中對比的基于多項式插值的改進算法中選擇了基于牛頓插值法的VIRE算法。

由于閱讀器采集到的標簽RSSI數(shù)據(jù)受多徑效應的影響而存在波動，為此，每個待定位標簽位置采集150次數(shù)據(jù)，進行高斯濾波處理，計算該組數(shù)據(jù)的均值μ和方差σ，公式如下：

構(gòu)建高斯概率密度函數(shù)，遍歷RSSI數(shù)據(jù)，選擇概率密度值大于最大值0.6倍的數(shù)據(jù)存入新的數(shù)組，如式（11），取新數(shù)組的算術(shù)平均值為該待定位標簽的RSSI值。

5 實驗結(jié)果對比分析

5.1 不同插值方法和插值密度對比實驗

為測試不同插值方法對VIRE算法定位精度的影響，設計實驗一，分別選取線性插值、牛頓插值、克里金插值作為VIRE算法的插值方法，閾值均為9，同時測試虛擬標簽密度對定位精度的影響。虛擬標簽密度定義為任意兩個實參考標簽之間新增的虛擬標簽數(shù)，設虛擬標簽密度從1到9變化，記錄三種算法在不同插值密度下的平均定位誤差，實驗結(jié)果如圖3所示。

圖3 不同插值法和插值密度下對定位精度的影響

從圖3可以看出三種算法的平均定位誤差隨虛擬標簽密度值從1到9增大時均呈現(xiàn)下降趨勢，當虛擬標簽密度參數(shù)取值大于4時，采用三種插值方法的算法的平均定位誤差都趨于穩(wěn)定不再降低，此時繼續(xù)增加虛擬標簽密度會使算法時間復雜度迅速上升，但定位精度也不再提高?？梢钥闯霰疚牟捎每死锝鸩逯档乃惴ㄆ骄ㄎ徽`差隨著虛擬標簽密度的增大下降的最快，穩(wěn)定后的平均定位誤差最小，為0.81 m，并且在同等定位精度的前提下，克里金插值法所需標簽數(shù)最小，減少了定位成本。

5.2 自適應閾值調(diào)整策略實驗

閾值作為VIRE算法的重要參數(shù)，其值的選取直接關系定位精度的高低?，F(xiàn)通過實驗設閾值取0至40之間的整數(shù)，分別測試50個點的待定位標簽，記錄不同待定位標簽的定位誤差隨閾值變化的曲線，隨機選取標簽A、B、C的結(jié)果如圖4所示。

可從圖4的實驗結(jié)果中找到不同標簽的最佳閾值，需要注意的是，這樣找出最佳閾值的前提是在已知待定位標簽位置的情況下進行的，是為了評價本文提出的自適應閾值調(diào)整策略的計算結(jié)果，但實際定位過程中無法計算定位誤差，因此，采用經(jīng)典VIRE算法也就無法獲得最佳閾值。為此，本文提出自適應閾值調(diào)整策略以期估計最佳閾值。

圖4 測試標簽定位誤差隨閾值的變化

為測試自適應閾值調(diào)整策略找到恰當閾值的所需時間和結(jié)果，采用自適應閾值調(diào)整策略，測試同一組50個待定位標簽的數(shù)據(jù)，記錄自適應迭代次數(shù)和閾值計算結(jié)果。標簽A、B、C采用自適應閾值的計算結(jié)果如圖5所示。

圖5 測試標簽閾值隨自適應迭代次數(shù)的變化

可以看出標簽閾值在迭代初期下降較快，在接近迭代停止條件時下降速度變緩，最終滿足停止條件，獲得最佳閾值。其中標簽A、B在第6代時結(jié)束計算，標簽C在第7代時結(jié)束，不同標簽的自適應閾值調(diào)整迭代次數(shù)和閾值不盡相同。

從圖4對應的實驗中提取標簽最佳閾值情況下和自適應閾值調(diào)整后對應的平均定位誤差，從圖5對應的實驗中提取待定位標簽自適應閾值調(diào)整的結(jié)果，如表1所示。自適應閾值調(diào)整后的定位誤差在一定程度上逼近了最佳閾值情況下的計算結(jié)果。

表1 最佳閾值下與自適應閾值下定位誤差對比

5.3 基于克里金插值的自適應VIRE算法性能試驗

為驗證本文算法的性能，設計實驗三，分別測試本文提出的基于克里金插值的自適應VIRE算法、經(jīng)典VIRE算法和基于牛頓插值的VIRE算法在相同實驗環(huán)境下的平均定位誤差。其中經(jīng)典VIRE算法和基于牛頓插值的VIRE算法的閾值經(jīng)實驗設定為9。圖2中標注的9個有代表性位置的標簽誤差計算結(jié)果如圖6所示。

圖6 不同定位算法定位誤差

從圖6可以看出采用本文算法估計的待定位標簽平均定位誤差最小。在全部50個待定位標簽中，VIRE算法的平均定位誤差為0.897 6 m，基于牛頓插值的VIRE算法的平均誤差為0.811 2 m，基于克里金插值的自適應VIRE算法的平均定位誤差為0.647 3 m，較前兩者分別降低了27.88%和20.20%。

將實驗結(jié)果按不同定位誤差所占比重劃分，得到三種算法的定位誤差累計分布如圖7所示，自變量為最大定位誤差限，因變量的含義為待定位標簽定位誤差小于對應的自變量定位誤差限的數(shù)量所占全部測試標簽數(shù)量的比例。

圖7 不同算法的定位誤差累計分布

從圖7可以看出，采用本文算法的實驗結(jié)果中有49%的標簽定位誤差小于0.6 m，全部標簽的定位誤差控制在1 m以內(nèi)；采用基于牛頓插值法改進的VIRE算法中有30%的標簽定位誤差小于0.6 m，最差定位誤差在1.2 m以內(nèi)，采用經(jīng)典VIRE算法計算的標簽中僅有14%的定位誤差小于0.6 m，最差定位誤差為1.4 m。從結(jié)果中可以看出本文算法提高了定位結(jié)果的精度和穩(wěn)定性。

6 結(jié)束語

本文在VIRE算法的基礎上進行改進，提出一種基于克里金插值的自適應VIRE算法，通過實驗驗證了采用克里金插值法計算虛擬參考標簽的RSSI相比采用線性插值和牛頓插值的定位誤差更小，并且提出的自適應閾值調(diào)整策略在一定程度上逼近了最佳閾值情況下的計算結(jié)果。改進后的算法可以在不增加參考標簽數(shù)量的情況下，進一步提高定位精度和定位結(jié)果的穩(wěn)定性，節(jié)省了成本。

[1]Zhang Y J，Chen E X.An approximate sphere of the four anchor nodes positioning method based on RSSI[J].Sensors&Transducers，2015，186（3）：85-92.

[2]Li N，Becerik-Gerber B.Performance-based evaluation of RFID-based indoor location sensing solutions for the built environment[J].Advanced Engineering Informatics，2011，25（3）：535-546.

[3]Jiang X，Liu Y，Wang X.An enhanced approach of indoor location sensing using active RFID[C]//WASE International Conference on Information Engineering，2009，1：169-172.

[4]Zhao Y，Hong W，Cheung S C.The impact of reader to tag collision on RFID tag identification[C]//International Conference on Wireless Algorithms，Systems，and Applications.Berlin，Germany：Springer，2010：115-119.

[5]Ni L M，Liu Y，Lau Y C，et al.LANDMARC：Indoor location sensing using activeRFID[J].WirelessNetworks，2004，10（6）：701-710.

[6]Zhao Y，Liu Y，Ni L M.VIRE：Active RFID-based localization using virtual reference elimination[C]//2007 International Conference on Parallel Processing，2007：56.

[7]姜麗芬，盧桂章，辛運幃.射頻識別系統(tǒng)中的防碰撞算法研究[J].計算機工程與應用，2007，43（15）：29-32.

[8]Ahn H S，Yu W.Environmental-adaptive RSSI-based indoor localization[J].IEEE Transactions on Automation Science and Engineering，2009，6（4）：626-633.

[9]周彥，文寶，李建勛.無線傳感器網(wǎng)絡節(jié)點近點加權(quán)質(zhì)心定位方法[J].計算機工程與應用，2012，48（1）：87-89.

[10]徐愛萍，胡力，舒紅.空間克里金插值的時空擴展與實現(xiàn)[J].計算機應用，2011，31（1）：273-276.

[11]李方，王鐵成，佟為明.基于空間變異理論的電子地圖構(gòu)建方法[J].哈爾濱工程大學學報，2012（6）：715-719.

[12]王遠哲，毛陸虹，劉輝，等.基于參考標簽的射頻識別定位算法研究與應用[J].通信學報，2010，31（2）：86-92.

[13]李慶揚，王能超，易大易.數(shù)值分析[M].5版.北京：清華大學出版社，2010：23-35.

[14]徐楊杰，王艷，嚴大虎，等.基于Newton插值與混合灰狼優(yōu)化SVR的RFID定位算法[J].系統(tǒng)仿真學報，2017，29（9）：1921-192.