基于k-means及改進k近鄰的WiFi指紋定位算法

郭昕剛,　胡　朗

(長春工業大學 計算機科學與工程學院， 吉林 長春　130012)

0　引　言

近年來，隨著移動互聯網的快速發展以及無線WiFi的大量普及，基于位置的服務變得越來越流行。在室外環境中，全球定位系統(GPS)能夠很好地實現定位。在室內環境中，由于建筑物的復雜結構以及室內障礙物的干擾，使得GPS技術在室內環境中受到了很大的限制[1]。而無線WiFi作為一種室內廣泛分布的信號，其較強的穩定性以及傳播距離遠等特性，已經成為大量研究者青睞的對象。基于WiFi的定位技術中，常見的定位方法有：基于時間的定位(TOA)、基于角度定位(AOA)以及位置指紋定位[2]。位置指紋技術因不需要獲取WiFi接入點的位置，是室內定位最為廣泛的研究方法。位置指紋定位的主要問題是：離線數據庫的建立以及在線實時的位置匹配。對于上述問題，文中研究了指紋庫的建庫原理，并將k-means聚類分析方法引入到WiFi定位技術中，提出了一種基于k-means聚類和加權的k近鄰的位置指紋算法[3]。在離線建庫階段，采用k-means聚類方法將指紋庫劃分為不同的子類。在線定位階段，將實測指紋與子類的類中心匹配，找到距離最近的類，在該類中找到相似指紋與之匹配[4]。針對位置估計算法，對現有的k近鄰算法進行改進，引入了新的權重系數的計算方法。算法在定位環境下進行了仿真試驗，驗證了其有效性和實用性。

1　算法描述

1.1　離線指紋數據庫的構建

離線采集過程包括兩個階段[5-7]:

2)將采集到的指紋數據進行建庫，假設在特定區域有m個采樣點，可以檢測到有n個WiFi信號強度RSSI信息。這m個采集點的位置事先經測量后已知，把采集到的各個AP的信號經處理后組成一個位置指紋數據庫。這個指紋庫可以表示：

(1)

1.2　在線匹配定位

在線匹配階段，即將待測目標實時測得的各個AP熱點的信號強度與離線指紋數據庫進行匹配，找到與待測目標指紋信息相似的一個或多個參考指紋點，再利用一定的匹配算法將指紋參考點的位置信息進行計算，最終求得待測位置的物理坐標。

目前常用的匹配算法有最近鄰法(Nearest Neighbor)和k近鄰法(kNearest Neighbor)。

1.2.1最近鄰法

最近鄰法就是通過在實時位置上測得的RSSI信息，經處理后，找出與該實時定位位置歐式距離最小的指紋點，實時位置與第i參考點之間的歐式距離為：

(2)

最近鄰法是最基本的指紋定位算法，將最小歐式距離對應的指紋點的位置坐標作為目標位置的坐標。實際位置的坐標表示為：

(x,y)=mindi，i∈[1,m]

(3)

最近鄰法的定位原理簡單，耗費時間短，但該方法存在很大的定位誤差，由于信號采集的不穩定性，單純的從最短歐式距離的一個采樣點坐標作為定位目標勢必會造成結果的不準確。

1.2.2k近鄰法

k近鄰法是對最近鄰法的改進，即首先將實時指紋同數據庫中所有參考點遍歷計算歐氏距離，再對歐式距離從小到大進行排序，然后選出前k(k≥2)個歐式距離較小的點，并將k個指紋點對應的位置坐標求均值作為目標位置。實際位置的坐標表示為：

(4)

式中：(xi,yi)----指紋數據庫中第i個指紋點對應的位置坐標；

(x,y)----實際定位結果坐標。

k近鄰法相對于最近鄰法有一定的改進，但k近鄰法未考慮到不同參考點對待測目標的貢獻程度，即距離近的參考點對待測目標的位置估算貢獻程度大，距離相對較遠的參考點對待測目標的位置估算貢獻程度小。不同參考點對待測目標的影響程度并不相同，所以對每個參考點賦予相同的權重對估算后的位置精度勢必有一定的影響。

2　k-means聚類+改進的k近鄰算法

文中在對位置指紋算法的深入分析和研究下，提出了一種基于k-means聚類和改進的k近鄰融合算法。在指紋庫建庫階段，利用k-means聚類把指紋信息相似的參考點分成一類。在位置估算階段，實測指紋與聚類后的指紋類進行匹配，找到與實測指紋最相似的一類，然后運用改進的k近鄰算法計算待測目標位置。其具體的工作原理如圖1所示。

圖1定位工作原理圖

2.1　k-means聚類算法對指紋庫進行優化

位置指紋庫初步建成之后，文中將對指紋庫進行聚類處理[8]。k-means聚類方法的具體執行過程如下：

1) 輸入m個指紋和聚類個數k(k≤m)；從m個指紋中任意選取k個指紋作為初始聚類中心。

2) 對于剩下的(m-k)個指紋，計算每個指紋到各個聚類中心的距離dij，dij表示第i個指紋點到第j個聚類中心的距離，找出指紋點到各個聚類中心的最小距離dmin，并將該指紋點劃分到與其距離最小的聚類中心所在的類。

3) 重復步驟2)，直到將所有剩余的指紋點劃分到屬于自己的類中，組成k個聚類(G1,G2，…,Gk)，每個類都包含其聚類中心及其對應的指紋點。

4) 計算各個類中的聚類質心，如果求得的質心和聚類中心相同，表示聚類結束。否則令聚類質心為其新的聚類中心，重新對各個指紋點進行聚類，直到最后的質心等于上一次的聚類中心為止。

5) 輸出聚類結果。

k-means聚類的算法流程如圖2所示。

圖2　k-means聚類流程圖

2.2　改進的KNN算法

為了有效解決KNN算法存在的參考指紋單一、定位結果不準確的問題，文中提出了一種改進的KNN算法。其具體操作過程如下：引入權重系數ωi，其表示不同參考點對待測定位點的貢獻程度，一般來說，距離遠的參考點對待測定位點的貢獻程度小，距離近的參考點對待測定位點的貢獻程度大[9]。權重系數的推導公式如下：

(6)

σi----第i個參考點指紋的標準差。

令

(7)

則權重系數為：

(8)

目標位置的估計坐標為：

(9)

3　定位誤差的評價指標

算法的定位效果一般采用兩種指標來表示[10]：一種是定位誤差累計概率；一種是均方根誤差。定位誤差累計概率一般表示為

P(e)=p(e≤e0)

0≤P(e)≤1

其分布曲線的收斂速度表示定位誤差的大小，收斂速度越迅速，表示誤差越小，反之定位誤差越大。

均方根誤差的計算公式為：

(10)

式中：(xest,yest)----待測位置的估計坐標。

均方根誤差越小，表示待測位置的計算越準確，反之表示計算的待測位置越不精確。

4　實驗仿真與分析

為了驗證k-means聚類和改進的k近鄰融合算法的性能，文中運用MATLAB軟件對算法進行了仿真，并對原有的KNN算法和NN算法進行了比較，驗證了改進后算法的優勢[11-14]。

4.1　實驗環境的搭建

實驗選擇的定位區域為長春工業大學南湖校區老圖書館3樓西側走廊，在走廊區域能夠檢測到設置的AP熱點。選擇走廊中2.5 m×60 m的方形區域，走廊地面鋪設有正方形瓷磚(規格為0.8 m×0.8 m)，以3302和3303門口為起點，每隔兩塊瓷磚(1.6 m)作為一個采樣點，共設置100個采集點，左右各50個。信號強度監測裝置采用智能手機APP，手機型號為MG4J2CH/A,處理器為雙核1.4 GHz,系統為iOS 11.2.1，APP為WiFi信號強度檢測器。在每個采樣點上每隔1 s采集1次數據，采集30次。定位區域平面圖如圖3所示。

圖3定位區域平面圖

4.2　k-means聚類算法對指紋庫的優化

為了驗證經k-means聚類算法優化后的指紋庫的定位效果比未經優化的指紋庫定位效果好，文中首先在同一區域采集相同的指紋點，采用相同的匹配算法，在同一定位點處分別采取兩種方法進行多次實驗，并對記錄結果進行對比分析。

經單次k-means聚類后的效果對比圖如圖4所示。

圖4實驗樣本空間數據聚類前后對比圖

指紋庫優化前后使用同一種算法實驗的誤差對比圖如圖5所示。

圖5　指紋庫優化前后誤差概率對比圖

經對比分析發現，通過k-means聚類后的指紋庫能有效地把具有相似特征的指紋點聚成一類，圖4中將離散的數據點分成了三類，并定義了每個類別的中心，有效地降低了在線匹配的搜索空間。圖5表明，使用同一種匹配算法，指紋庫聚類和指紋庫沒有聚類的差別，經指紋聚類后的算法誤差平均誤差概率提高了20%，比沒有聚類前的算法效果更好。

4.3　改進的k近鄰算法(WKNN)對k近鄰(KNN))和近鄰算法(NN)的提高效果

由于k-means聚類算法與改進的k近鄰算法(WKNN)以及k近鄰算法都涉及到k值的選取問題，所以,首先對k-means聚類算法和k近鄰算法中k值大小對定位誤差的影響作出探究，找到能使定位誤差達到最小的k值。下面是一組采用原始數據而k取值不同時的誤差分析,見表1。

表1　k-means-KNN平均定位誤差表

由表1可見，在k-means聚類算法k取3，KNN算法k取4時，達到的平均定位誤差最小。在接下來驗證試驗中，我們將取同樣的k值去進行實驗。為了驗證文中改進后算法的定位效果，在圖4表示的定位場景中，分別使用3種不同的定位算法(WKNN、KNN、NN)進行實驗:

1)算法是文中提出改進的k近鄰算法(簡稱WKNN算法);

2)原始的KNN算法，其被選取的k個參考點均被賦予相同的權值1/k；

3)近鄰算法(NN)，選取歐式距離最小的點的位置作為待測目標的位置。

實驗使用的數據指紋庫都是經k-means聚類后的同一指紋庫。

利用上述3種方法對50個定位點處采集的數據進行仿真實驗，分析計算得到的定位誤差累計概率圖如圖6所示。

圖6　WKNN/KNN/NN三種算法定位精度對比圖

從圖6可以看出，文中提出WKNN算法收斂距離在1.25 m左右，而KNN算法的收斂距離在1.5 m左右，NN算法收斂距離在1.8 m左右。WKNN算法引入了權重系數之后，定位結果的誤差有所降低，定位精度獲得了一定的提高，說明了提出WKNN算法具有一定的可行性。

5　結　語

針對傳統的指紋定位算法定位精度不高以及指紋庫匹配搜索范圍大的問題，進行了深入的分析，提出了一種基于k-means聚類分析方法以及WKNN的在線匹配算法，并在現實場景中進行了實驗驗證，結果表明，提出的定位算法在精度以及穩定性方面具有一定的提升，對基于位置指紋的室內定位研究提供了一定的參考作用。

參考文獻：

[1]Xia Mingzhe, Chen Jiabin, Song Chunlei, et al. The indoor positioning algorithm research based on improved location fingerprinting[A]. Chinese Control and Decision Conference(CCDC)[C].2015.

[2]王淑婷.基于位置指紋的WiFi定位算法研究[D].長春：吉林大學，2015.

[3]楊帆.基于改進KNN算法的室內WiFi定位技術研究[D].西安：西北工業大學，2016.

[4]毛永毅，楊強強，徐萍.基于WiFi的一種改進的室內定位算法[J].測控技術，2017,36(8)：26-30.

[5]Leu J S, Yu M C, Tzeng H J. Improving indoor positioning precision by using received signal strength fingerprint and footprint based on weighted ambient Wi-Fi signals[J]. Computer Networks,2015,91:329-340.

[6]吳澤泰，蔡仁欽，徐書燕，等.基于K近鄰法的WiFi定位研究與改進[J].計算機工程，2017,43(3)：289-293.

[7]Wang F, Huang Z, Yu H, et al. EESM-Based fingerprint algorithm for Wi-Fi indoor positioning system[C]//Ieee/cic International Conference on Communications in China,2013:674-679.

[8]王磊，周慧，蔣國平，等.基于WiFi的自適應匹配預處理WKNN算法[J].信號處理，2015,31(9)：1068-1072.

[9]王青.WiFi室內定位系統的設計與實現[D].北京：北京交通大學,2014.

[10]陳斌濤，劉任任，陳益強，等.動態環境中的WiFi指紋自適應室內定位方法[J].傳感技術學報,2015(5):729-738.

[11]郭昕剛，李航，宮鴻,等.基于邊界過濾和鄰域均值濾波的室內定位算法[J].長春工業大學學報，2017,38(5):426-432.

[12]孫苑瑩.無線網絡的移動節點定位方法研究[J].長春工業大學學報，2015,36(1)：57-60.

[13]唐洋，白勇，馬躍，等.基于WiFi的指紋匹配法在室內定位中的應用研究[J].計算機科學,2016，43(5)：73-75.

[14]劉志鵬，袁敏.一種基于WiFi的改進型室內位置指紋定位方法[J].計算機與現代化,2016(4):36-39.