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

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

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

3.河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室，天津 300401

1 引言

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

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

2 VIRE算法簡介

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

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

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

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

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

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

3 基于克里金插值的自適應(yīng)VIRE算法

3.1 基于克里金插值的虛擬標(biāo)簽計(jì)算

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

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

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

式中，C0為塊金常數(shù)，C為拱高，變程h=當(dāng)C0=0，C=1時(shí)，稱為標(biāo)準(zhǔn)高斯模型。

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

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

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

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

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

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

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

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

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

算法流程如圖1所示。

3.3 改進(jìn)后的算法流程

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

（1）獲取實(shí)參考標(biāo)簽RSSI矩陣。

（2）利用克里金插值擴(kuò)充矩陣以獲得大量虛擬參考標(biāo)簽。

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

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

4 實(shí)驗(yàn)環(huán)境構(gòu)建

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

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

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

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

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

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

5 實(shí)驗(yàn)結(jié)果對比分析

5.1 不同插值方法和插值密度對比實(shí)驗(yàn)

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

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

從圖3可以看出三種算法的平均定位誤差隨虛擬標(biāo)簽密度值從1到9增大時(shí)均呈現(xiàn)下降趨勢，當(dāng)虛擬標(biāo)簽密度參數(shù)取值大于4時(shí)，采用三種插值方法的算法的平均定位誤差都趨于穩(wěn)定不再降低，此時(shí)繼續(xù)增加虛擬標(biāo)簽密度會(huì)使算法時(shí)間復(fù)雜度迅速上升，但定位精度也不再提高。可以看出本文采用克里金插值的算法平均定位誤差隨著虛擬標(biāo)簽密度的增大下降的最快，穩(wěn)定后的平均定位誤差最小，為0.81 m，并且在同等定位精度的前提下，克里金插值法所需標(biāo)簽數(shù)最小，減少了定位成本。

5.2 自適應(yīng)閾值調(diào)整策略實(shí)驗(yàn)

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

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

圖4 測試標(biāo)簽定位誤差隨閾值的變化

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

圖5 測試標(biāo)簽閾值隨自適應(yīng)迭代次數(shù)的變化

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

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

表1 最佳閾值下與自適應(yīng)閾值下定位誤差對比

5.3 基于克里金插值的自適應(yīng)VIRE算法性能試驗(yàn)

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

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

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

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

圖7 不同算法的定位誤差累計(jì)分布

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

6 結(jié)束語

本文在VIRE算法的基礎(chǔ)上進(jìn)行改進(jìn)，提出一種基于克里金插值的自適應(yīng)VIRE算法，通過實(shí)驗(yàn)驗(yàn)證了采用克里金插值法計(jì)算虛擬參考標(biāo)簽的RSSI相比采用線性插值和牛頓插值的定位誤差更小，并且提出的自適應(yīng)閾值調(diào)整策略在一定程度上逼近了最佳閾值情況下的計(jì)算結(jié)果。改進(jìn)后的算法可以在不增加參考標(biāo)簽數(shù)量的情況下，進(jìn)一步提高定位精度和定位結(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]姜麗芬，盧桂章，辛運(yùn)幃.射頻識別系統(tǒng)中的防碰撞算法研究[J].計(jì)算機(jī)工程與應(yīng)用，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)絡(luò)節(jié)點(diǎn)近點(diǎn)加權(quán)質(zhì)心定位方法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（1）：87-89.

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

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

[12]王遠(yuǎn)哲，毛陸虹，劉輝，等.基于參考標(biāo)簽的射頻識別定位算法研究與應(yīng)用[J].通信學(xué)報(bào)，2010，31（2）：86-92.

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

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