一種基于位置指紋定位的K-均值聚類算法的改進

孔港港,楊力,孫聃石,吳雨

(1.信息工程大學 導航與空天目標工程學院,鄭州,450001;2.北斗導航應用技術河南省協同創新中心,鄭州 450001)

?

一種基于位置指紋定位的K-均值聚類算法的改進

孔港港1,2,楊力1,2,孫聃石1,2,吳雨1,2

(1.信息工程大學 導航與空天目標工程學院,鄭州,450001;2.北斗導航應用技術河南省協同創新中心,鄭州 450001)

位置指紋定位的K-均值聚類算法將參考點分為K個子類,將相似對象聚集在一起,從而減少指紋搜索空間,提高效率。本文在K-均值聚類算法的基礎上對選取的子類中鄰近點進行加權計算,提高高相關性參考點的計算比重,從而達到提高定位精度的目的。實驗結果表明,改進后的算法具有更高定位精度,其精度提高了18.5%。

指紋定位;K-均值聚類;加權

0 引 言

隨著無線局域網基礎設施的不斷增加,Wi-Fi熱點現在正廣泛布設于商場、校園、車站等公共場所,據統計,2015年全球公共Wi-Fi熱點總數已達5000萬[1]。人們對Wi-Fi的研究也開始由組網能力擴展到定位應用等方面,Wi-Fi定位的定位過程可分為信號采集階段和坐標解算階段。而位置指紋定位方法由于其無需測距的優點成為了Wi-Fi定位中常用的方法之一,對于Wi-Fi定位的研究具有重要意義[2]。本文在位置指紋定位方法中的K-均值(K-means)聚類算法的基礎上對所選子類中的鄰近點加權,提升高相關點坐標所占比重,實驗結果表明:改進后的算法定位精度更優,達到了預期目的。

1 K均值聚類算法

1.1 位置指紋定位原理

位置指紋定位分為離線建立指紋庫和在線定位兩個階段[3]。離線階段,在實驗區域內建立二維直角坐標系,根據定位精度的要求和實驗區的實際環境按照一定間隔選擇L個參考點并記錄坐標(xi,yi),i=1,2,…,L,并采集參考點處接收到的信號強度(RSSI)形成指紋并構建指紋庫,然后采集參考點處收到的M個無線端口(AP)的RSSI樣

本RSSi,1,…,RSSi,M形成該參考點處的指紋并建立指紋庫,庫中每個指紋表示其對應的參考點RSSI信息。在線階段,將待測目標的RSSI信息與指紋庫中參考點的RSSI信息進行匹配,取RSSI信息的歐氏距離相近的點作為坐標計算基準,進一步計算獲得待測點坐標。位置指紋定位的原理如圖1所示。

圖1 位置指紋定位原理

1.2 位置指紋庫

假設在實驗區域內選擇了L個參考點,參考點處可以獲取M個AP的RSSI,即每個指紋包含M個RSSI值,采集所有參考點的指紋即可形成指紋庫。

(1)

(2)

(3)

其中: RSSi,j表示在第i個參考點處獲取的第j個AP的RSSI信息; FDi表示第i個參考點的指紋。

假設每個參考點的坐標用(x,y)表示,那么,指紋庫對應的坐標信息為

(4)

1.3 K-均值聚類

K-均值聚類算法首先要對指紋庫內的參考點進行分類處理,即隨機選擇k個參考點,每個被選參考點代表一個子類的初始中心,其余的參考點根據其與各初始中心的歐氏距離,歸納到歐氏距離最近的中心,形成k個子類。然后重新計算每個子類的新均值,不斷重復該過程至其準則函數收斂[4-5]。通常采用平方誤差準則,定義為

(5)

K-聚類算法流程如圖2所示。

圖2 K-聚類流程圖

聚類完成之后,將待測點歸納到信息相接近的子類中,將子類作為一個指紋庫,在子類內利用K-鄰近(KNN)算法計算坐標[6-7],

(6)

式中: (xe,ye)為待測點坐標;k1為K-鄰近算法選擇的k值; (xi,yi)為最鄰近點坐標。

2 加權K-聚類算法定位

加權K-聚類算法是在聚類完成、待測點歸納入信息相似的子類之后。將該子類中參考點信息作為一獨立的數據庫,在該數據庫的基礎上,用加權K-鄰近(WKNN)算法計算坐標。

假設選取了k1個最鄰近點,即:

Fp*=(Fp*1,Fp2,…,Fp*k1)T,

(7)

Fpi*=(RSSi*,1,RSSi*,2,…,RSSi*,M),

i*=1,2,…,k,

(8)

式中:Fpi*表示第i*個鄰近點。

假設待測點的RSSI信息為

Fpe=(RSS1,RSS2,…,RSSM).

(9)

分別計算每個鄰近點與待測點指紋信息的歐氏距離。

(10)

圖3 加權K-鄰近算法流程圖

(11)

那么待測目標的位置計算為

(12)

式中,(xi*,yi*)表示第i*個鄰近點的坐標。

計算流程如圖3所示。

3 實驗結果分析

為了驗證改進后算法的定位效率及定位精度,選取學校某俱樂部、會議室及附屬走廊31.6m×15.2m的空間,以2m×2m為間隔,選定了16×8個參考點建立數據庫,參考點布設如圖4所示。

圖4 試驗區參考點布設

圖5 參考點聚類結果

根據場地實際環境,實驗將K-均值聚類的k值取3,聚類結果如圖5所示,聚類結果顯示子類歸屬與空間格局具有很高相關性。

試驗區域內掃描到的AP信息如表1所示,本實驗選取6個AP,即每個指紋有6個RSSI信息。

表1 實驗區域AP信息

以左下角點為原點建立二維直角坐標系,在試驗區域內選擇8個待測點,坐標如表2所示。

待測點坐標分別利用加權K-鄰近(WKNN)、K-聚類(K-means)、加權K-聚類(WK-means)(最鄰近點數取3)三種算法計算,定位坐標如表3所示。所耗時間及定位精度分別如圖6、圖7所示。其中,定位耗時在MATLAB平臺下測量,MATLAB運行在聯想Z470筆記本上,其硬件配置為:英特爾i5-2410M 2.3 GHz處理器,4G內存。

表2 待測點真實坐標

表3 三種定位方法計算的點坐標

圖6 三種定位方法平均耗時比較

圖7 三種定位方法定位誤差比較

根據圖6、圖7可以看出:

1) 加權K-means算法與K-means算法相比,在定位耗時上分別為0.82 s和0.61 s,慢了34.4%;定位誤差平均值0.53 m和0.65 m,定位精度提高了18.5%.

2) 加權K-means算法與WKNN算法相比,定位耗時分別為0.82 s和1.32 s,定位速度提高了22.7%.定位誤差平均值分別為0.53 m和0.45 m,定位精度降低了17.8%.

因此,綜合定位的精確度和定位速度兩方面考慮,本文結合了加權的K-聚類算法在較高定位性能的基礎上取得了較好的定位結果,定位效果優于單純的WKNN算法和K-聚類算法。

4 結束語

本文在K-聚類算法的基礎上,結合提高高相關性點權重的思想,提出K-聚類結合WKNN計算待測點坐標的算法,在聚類完成后、待測點歸類之后,在歸入的子類中用WKNN算法計算待測點坐

標。實驗結果表明,改進后的算法能夠在保持高效定位的基礎上提高定位精度。由于場地及設備限制,實驗環境較為簡單并且定位結果僅是二維坐標上的定位,繼續改進算法并實現三維空間上的定位是今后研究的重點。

[1] 王淑婷. 基于位置指紋的WiFi定位算法研究[D].吉林:吉林大學,2015.

[2] 孫永亮. 基于位置指紋的WLAN室內定位技術研究[D].哈爾濱:哈爾濱工業大學,2014.

[3] 張明華. 基于WLAN的室內定位技術研究[D].上海:上海交通大學,2009.

[4] 毛紅文. 基于模糊聚類的位置指紋室內定位優化技術研究[D].昆明:云南大學,2014.

[5] 陳望,賈振紅,覃錫忠,等. 基于改進K-means聚類算法的室內WLAN定位研究[J]. 激光雜志,2014(7):11-14.

[6] 于睿,陸南. 基于K均值聚類算法的位置指紋定位技術[J]. 信息技術,2015(10):185-188,191.

[7] 湯麗. 基于模糊聚類KNN的室內WLAN定位算法研究[D].哈爾濱:哈爾濱工業大學,2009.

Research on an Algorithm of Fingerprint Location Based on K-means and WKNN

KONG Ganggang1,2,YANG Li1,2,SUN Danshi1,2,WU Yu1,2

(1.CollegeofNavigationandAerospaceEngineering,InformationEngineeringUniversity,Zhengzhou450001,China;2.BeiDouNavigationTechnologyCollaborativeInnovationCenterofHenan,Zhengzhou450001,China)

K-mean clustering algorithm based on fingerprint is divided the reference point into K subclass. The similar objects are clustered together to reduce the search space and improve the efficiency. In this paper, we weighted the nearest neighbor of the choose subclass based on the K-means clustering algorithm. Increase the proportion of high correlation reference point while calculating, so as to achieve the purpose of improving the accuracy of location. The experimental results show that the accuracy of the new algorithm has improved 18.5 percent.

Fingerprint localization; K-means clustering; weighting

10.13442/j.gnss.1008-9268.2016.05.018

2016-03-15

P228.4

A

1008-9268(2016)05-0089-04

孔港港 (1993-),男，碩士生,主要從事導航、制導與控制研究。

楊力 (1965-),男，教授,主要從事衛星精密定軌研究。

孫聃石 (1990-),男，碩士生,主要從事WLAN室內定位研究。

吳雨 (1992-),男，碩士生,主要從事無線傳感器定位研究。

聯系人： 孔港港 E-mail: 1171470624@qq.com