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

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

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

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

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

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

1 指紋定位算法

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

圖1 指紋定位算法流程圖

1.1 離線訓練階段

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

圖2 指紋定位算法示意圖

1.2 在線定位階段

移動終端將利用某種匹配算法在測試點（TP，圖2中紅色菱形點）接收到的RSS值與指紋庫數(shù)據(jù)進行匹配，從而得到當前位置。本文以近鄰算法（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向量與數(shù)據(jù)庫中的指紋進行最佳匹配。通常采用歐氏距離作為衡量準則，其原理簡單，只需少量計算。在WiFi定位系統(tǒng)中，歐氏距離是指RP與TP向量在信號空間上的距離。對于每個RP而言，歐氏距離可被定義為：

式中，i=1,2,…,n，n為RP的數(shù)量；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個最近的歐氏距離的倒數(shù)作為每個RP的權值，表達式為：

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

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

2 基于灰色關聯(lián)度的改進WKNN定位算法

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

圖3 基于灰色關聯(lián)度的改進WKNN算法流程圖

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

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

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

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

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

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

4）求取關聯(lián)度。關聯(lián)度的計算公式為：

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

式中，ε為很小的正數(shù)，防止分母出現(xiàn)0。

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

3 實驗結(jié)果與分析

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

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

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

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

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

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

圖5 實驗場景平面示意圖

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

圖7 iPad 2018的累積誤差概率

圖8 Acer E1的累積誤差概率

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

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

4 結(jié) 語

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