多類智能終端基于灰色關聯度的WKNN定位效果分析

王 威，陳正宇，張 帥，胡紀元

（1.中國能源建設集團江蘇省電力設計院有限公司，江蘇 南京 211102；2.武漢大學 測繪學院，湖北 武漢 430079）

近年來，隨著無線通信技術的發展以及用戶對基于位置服務（LBS）需求的增長，出現了很多室內外定位技術。全球衛星導航系統（GNSS）已廣泛應用于室外定位[1]，但在室內環境中，衛星信號很難到達室內定位終端，難以提供有效的室內定位精度，因此在過去的20多a里出現了很多室內定位系統（IPSs），以提高室內定位的可靠性和精度[2]。相較于其他無線室內定位技術，WiFi室內定位無需額外布設硬件，可利用建筑物中已有的WiFi網絡基礎設施，如以WiFi路由器為定位信號源；更重要的是，幾乎每種現有的移動設備都支持WiFi接收功能，因此該技術得以廣泛應用。

雖然WiFi信號接收設備接收信號的強度和信號發射器與接收器之間的距離有關，但在復雜的室內環境下很難用簡單的公式描述，因此有研究者提出了以WiFi的RSS值為位置指紋的定位技術[3]。在室內定位環境不變的情況下，離線階段和定位階段采用相同的設備將得到較高的定位精度；但在定位階段不同類型和品牌的設備測量的RSS值與所建立的指紋庫不能有效匹配，將導致定位精度下降，因此找到一種穩健的指紋定位技術來提供精確、可靠的室內定位服務十分緊迫和必要。

Park J G[4]等發現不同設備的RSS值之間存在線性模型，可利用回歸分析得到兩種設備之間的線性校準模型，但需要大量的信號采集和模型訓練；FANG S H[5]等比較了幾種不同的免校準方法，但這些方法在相同設備下的定位效果通常不如傳統算法好；Tsui A W[6]和HAN S[7]等分別利用皮爾森相關系數和余弦相似度衡量了指紋和測試階段RSS值之間的相關程度，在一定程度上消除了設備接收信號的差異性。本文提出了以灰色關聯度取代歐氏距離的改進WKNN算法，無需任何校準工作和復雜計算，且適用于不同的智能終端。實驗結果表明，相較于傳統WKNN算法，基于灰色關聯度的改進WKNN算法降低了不同智能終端對WiFi定位精度的影響。

1 指紋定位算法

指紋定位算法是WiFi室內定位中經常使用的一種算法，包括離線訓練和在線定位兩個階段。實現過程如圖1所示。

圖1 指紋定位算法流程圖

1.1 離線訓練階段

在定位區域均勻布設參考點（RP，圖2中綠色圓點），RP的密度應控制在一個合理的范圍內，密度太小會影響定位精度，密度太大則會在建立指紋庫時增加人工采集和計算的成本。移動終端在RP采集多個接入點（AP）的RSS值時，連同對應的MAC值和RP位置信息記錄在指紋庫中。AP的RSS值受環境和AP自身影響存在波動，因此在錄入指紋庫前需對RSS值進行預處理。

圖2 指紋定位算法示意圖

1.2 在線定位階段

移動終端將利用某種匹配算法在測試點（TP，圖2中紅色菱形點）接收到的RSS值與指紋庫數據進行匹配，從而得到當前位置。本文以近鄰算法（NN）[8]為例：

假設利用終端設備在第i個RP處從m個AP采集到RSS的向量為Ri=(ri1,ri2,ri3,…,rim)，用戶在某個TP處從m個AP在線采集到RSS的向量為S=(s1,s2,s3,…,sm)，其中ri和s為每個AP的RSS值。通過某些準則，將用戶接收到的RSS向量與數據庫中的指紋進行最佳匹配。通常采用歐氏距離作為衡量準則，其原理簡單，只需少量計算。在WiFi定位系統中，歐氏距離是指RP與TP向量在信號空間上的距離。對于每個RP而言，歐氏距離可被定義為：

式中，i=1,2,…,n，n為RP的數量；Di為RP與TP向量之間的歐氏距離，Di越小，RP和TP之間的距離越短，通常與TP信號距離最短的那個RP點的坐標即為用戶的位置。

K最近鄰算法（KNN）與WKNN算法、NN算法類似，是以與TP歐氏距離最短的K個RP坐標的平均值為TP位置，表達式為：

式中，(xi,yi)為第K個RP的坐標。

WKNN算法考慮了K個RP坐標上對應的權值，需從TP與每個RP的歐氏距離中選取K個最近的歐氏距離的倒數作為每個RP的權值，表達式為：

式中，wi為第K個RP坐標中第i個坐標的權值。

NN算法、KNN算法和WKNN算法是WiFi指紋定位中的常用算法，即基于歐氏距離的定位算法；其他指紋定位方法包括極大似然估計（ML）、支持向量機（SVM）、線性判別分析、神經網絡和典型相關分析（CCA）等[9-13]。

2 基于灰色關聯度的改進WKNN定位算法

本文從灰色關聯度的角度出發，提出了一種替代傳統WKNN算法來衡量TP與指紋庫中RP相似度的方法。在傳統WKNN算法中，RSS值之間的歐氏距離越大，RSS的差異性就越大，但當遇到不同類型智能終端時，TP與RP的RSS值之間的小差異將造成歐氏距離的較大偏差，若忽略了RSS向量的內在特征和變化趨勢，將導致定位精度的嚴重下降甚至定位失敗[14]。歐氏距離僅在參考設備與用戶設備相同時可達到滿意的定位精度。本文利用灰色關聯度替代了傳統信號空間上的歐氏距離，灰色關聯度可通過灰色關聯分析（GRA）獲得。GRA可分析不同終端RSS向量的關聯程度。不同終端設備采集的RSS向量各對應元素的值之間可能有很大差異，但向量之間的變化趨勢和形狀具有很大的相似度，可利用灰色關聯度代替歐氏距離匹配測試數據與指紋庫的離線數據，從而得到TP坐標。灰色關聯度的具體實現流程如圖3所示[15]。

圖3 基于灰色關聯度的改進WKNN算法流程圖

1）確定參考序列與比較序列。將在線階段TP采集的m個AP信號強度RSS視為參考序列，即

將離線階段n個RP采集的m個AP信號強度RSS視為比較序列，即

2）對參考序列與比較序列進行均值化處理。參考序列和所有TP序列構成比較矩陣，即

對S中所有元素進行均值化處理，即每個元素除以該元素所在列的均值。該處理方式能保留各變量差異性信息，得到新的矩陣。

從R1′開始到Rn′每列都減去R0′對應元素，再求絕對值，得到式（8）的關聯矩陣；然后求絕對值，得到關聯矩陣。

3）求參考序列與比較序列之間的灰色關聯系數。首先求解關聯矩陣H中所有元素的最大值hmax和最小值hmin；然后利用關聯系數公式對H中的每個元素作以下處理：

4）求取關聯度。關聯度的計算公式為：

指紋庫中采集的第i個RP第j個AP的RSS值的方差為D(i,j)，方差越大，權值越小，則的計算公式為：

式中，ε為很小的正數，防止分母出現0。

5）關聯度排序。對指紋庫中i個RP的γi大小進行排序，并將得到的排序結果代替歐氏距離，從而對傳統WKNN算法進行改進。

3 實驗結果與分析

在利用本文提出的基于灰色關聯度的改進WKNN算法對多類智能終端進行定位前，需對不同終端接收到的RSS值進行分析與比較。不同的智能終端具有不同WiFi芯片型號、不同的WiFi信道、不同的天線位置以及不同的操作系統，這些都會影響RSS值的大小[16]。

三星S7、紅米Note1、iPad2018、Acer E1四種終端的WiFi模塊情況如表1所示，本文對利用這些設備在同一位置接收到的6個AP的RSS值進行對比，結果如圖4所示，可以看出，不同終端設備在同一位置接收到的6個AP的RSS值有很大差別，如三星S7與紅米Note1采集的平均RSS值差異可達11 dBm；但4種設備的RSS折線圖保持著相同的趨勢。通過這種趨勢的關聯度分析可得到測試設備與指紋庫建立所用參考設備采集的RSS值的關聯度比較。

表1 不同智能終端的WiFi模塊情況

圖4 4種設備的6個AP接收信號強度值

為了驗證基于灰色關聯度的改進WKNN算法的定位效果，在長10 m、寬6 m的房間進行了實驗，如圖5所示，在場地內布置6個WiFi路由器作為信號接入點，利用三星S7采集48個RP（綠色圓點），RP之間的橫向距離為1.6 m、縱向距離為0.8 m，在每個RP手持設備面向同一個方向采集60 s作為指紋庫數據；選取35個點作為TP（紅色圓點），在每個TP利用不同設備采集15 s作為測試數據，采樣頻率均為1 Hz。為了保證只有終端設備這一個變化量，本文選擇在機房環境穩定時進行數據采集，且采集人為同一個人。

將基于灰色關聯度的改進WKNN算法與傳統WKNN算法的定位結果進行對比，一般K=4時的定位精度較好[17]。紅米Note1、iPad2018、Acer E1分別利用兩種方法的累積誤差分布如圖6～8所示，可以看出，本文提出的算法在2 m定位精度內的概率分別提升了21%、18%和14%；且紅米Note1和Acer E1的最大誤差分別下降了約0.5 m和1 m。

圖5 實驗場景平面示意圖

圖6 紅米Note1的累積誤差概率

圖7 iPad 2018的累積誤差概率

圖8 Acer E1的累積誤差概率

為了充分驗證定位結果的普適性，對3種終端的不同K取值進行分析，結果如圖9所示，可以看出，不同K值下，基于灰色關聯度的改進WKNN算法比傳統算法的定位中誤差小，定位精度更高，且在K值較小的情況下，定位精度改進效果更好。

圖9 不同K值情況下兩種方法的定位效果

4 結 語

隨著智能手機和其他終端設備的廣泛使用，不同設備的RSS值差異成為影響WiFi室內定位精度的一個重要因素。為了減少設備不同對定位精度的影響，本文分析了不同智能終端的RSS差異性和共同點，提出了基于灰色關聯度的改進WKNN算法，并將改進后的定位算法與傳統算法進行了對比。實驗結果表明，利用不同設備進行WiFi定位時，相較于傳統WKNN算法，基于灰色關聯度的改進WKNN算法在定位精度上有很大提升，有效提高了不同終端的定位精度和普適性。