基于k-means及改進(jìn)k近鄰的WiFi指紋定位算法

郭昕剛,　胡　朗

(長春工業(yè)大學(xué) 計算機(jī)科學(xué)與工程學(xué)院， 吉林 長春　130012)

0　引　言

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

1　算法描述

1.1　離線指紋數(shù)據(jù)庫的構(gòu)建

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

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

(1)

1.2　在線匹配定位

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

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

1.2.1最近鄰法

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

(2)

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

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

(3)

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

1.2.2k近鄰法

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

(4)

式中：(xi,yi)----指紋數(shù)據(jù)庫中第i個指紋點對應(yīng)的位置坐標(biāo)；

(x,y)----實際定位結(jié)果坐標(biāo)。

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

2　k-means聚類+改進(jìn)的k近鄰算法

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

圖1定位工作原理圖

2.1　k-means聚類算法對指紋庫進(jìn)行優(yōu)化

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

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

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

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

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

5) 輸出聚類結(jié)果。

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

圖2　k-means聚類流程圖

2.2　改進(jìn)的KNN算法

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

(6)

σi----第i個參考點指紋的標(biāo)準(zhǔn)差。

令

(7)

則權(quán)重系數(shù)為：

(8)

目標(biāo)位置的估計坐標(biāo)為：

(9)

3　定位誤差的評價指標(biāo)

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

P(e)=p(e≤e0)

0≤P(e)≤1

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

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

(10)

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

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

4　實驗仿真與分析

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

4.1　實驗環(huán)境的搭建

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

圖3定位區(qū)域平面圖

4.2　k-means聚類算法對指紋庫的優(yōu)化

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

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

圖4實驗樣本空間數(shù)據(jù)聚類前后對比圖

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

圖5　指紋庫優(yōu)化前后誤差概率對比圖

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

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

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

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

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

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

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

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

實驗使用的數(shù)據(jù)指紋庫都是經(jīng)k-means聚類后的同一指紋庫。

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

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

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

5　結(jié)　語

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

參考文獻(xiàn)：

[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].長春：吉林大學(xué)，2015.

[3]楊帆.基于改進(jìn)KNN算法的室內(nèi)WiFi定位技術(shù)研究[D].西安：西北工業(yè)大學(xué)，2016.

[4]毛永毅，楊強(qiáng)強(qiáng)，徐萍.基于WiFi的一種改進(jìn)的室內(nèi)定位算法[J].測控技術(shù)，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ìn)[J].計算機(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的自適應(yīng)匹配預(yù)處理WKNN算法[J].信號處理，2015,31(9)：1068-1072.

[9]王青.WiFi室內(nèi)定位系統(tǒng)的設(shè)計與實現(xiàn)[D].北京：北京交通大學(xué),2014.

[10]陳斌濤，劉任任，陳益強(qiáng)，等.動態(tài)環(huán)境中的WiFi指紋自適應(yīng)室內(nèi)定位方法[J].傳感技術(shù)學(xué)報,2015(5):729-738.

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

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

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

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