基于K-Means和FCM的增強型Wi-Fi指紋定位策略①

陳 英,單文杰,楊豐玉

1(南昌航空大學(xué) 軟件學(xué)院,南昌 330063)

2(南昌航空大學(xué) 物聯(lián)網(wǎng)技術(shù)研究所,南昌 330063)

基于K-Means和FCM的增強型Wi-Fi指紋定位策略①

陳 英1,2,單文杰1,楊豐玉1

1(南昌航空大學(xué) 軟件學(xué)院,南昌 330063)

2(南昌航空大學(xué) 物聯(lián)網(wǎng)技術(shù)研究所,南昌 330063)

研究了通過數(shù)據(jù)處理算法以提高Wi-Fi指紋庫室內(nèi)定位性能的問題.首先采集Wi-Fi指紋樣本,將其放入MySQL數(shù)據(jù)庫中和R工程;其次將Wi-Fi指紋庫分成若干個簇,使用K-均值聚類(K-Means)和模糊C-均值聚類(FCM)對待定位的Wi-Fi指紋進行聚類分析;最后,提出增強型的聚類策略(ECS)應(yīng)用于Wi-Fi指紋匹配定位中.實驗結(jié)果表明,ECS較僅使用FCM算法,其定位耗時縮短約50%-80%,且定位精度上有所改善;ECS較僅使用K-Means算法,其定位精度提高約20%-40%,且定位穩(wěn)定性較強并自動更新Wi-Fi指紋庫.

Wi-Fi指紋;K-均值聚類;模糊C-均值聚類;增強型定位策略

隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展和移動互聯(lián)網(wǎng)的普及,無處不在的位置服務(wù)也越來越被人們需要.據(jù)諾基亞公司的數(shù)據(jù)表明,人們87%-90%的時間在室內(nèi)度過.但目前室內(nèi)定位還處于初級階段,無論在定位精度、速度、魯棒性等方面還都不能夠滿足日益增長的智能位置服務(wù)的需求.基于Wi-Fi指紋匹配的無線室內(nèi)定位技術(shù)[1]一定程度上解決了定位精度問題,且基礎(chǔ)設(shè)備應(yīng)用廣泛,成本較低,深受研究人員的關(guān)注.但由于Wi-Fi無線設(shè)備大多應(yīng)用于人類活動最為頻繁的室內(nèi)環(huán)境,無線室內(nèi)定位易受室內(nèi)布局變動、無線信號的多徑效應(yīng)等因素影響,其無線信號具有較強的波動性,嚴(yán)重影響定位性能.而基于Wi-Fi指紋匹配的定位方法首先通過不同位置上多次采集Wi-Fi RSSI信號建立指紋模型,然后利用匹配算法估計待定位點的具體位置,此方法避免了有信號特征轉(zhuǎn)化為距離帶來的誤差,故基于Wi-Fi指紋匹配的定位算法成為近年來室內(nèi)定位的研究熱點.

1 國內(nèi)外研究現(xiàn)狀

基于指紋匹配的無線室內(nèi)定位技術(shù)[2]是利用物理空間內(nèi)不同位置具有不同RSSI的特征,作為唯一識別此位置的方法,一般分為離線采樣和在線定位這兩個階段.離線采樣時通過采集在多個參考點(reference points,RP)的不同接入點的信號強度值,形成關(guān)于位置的指紋數(shù)據(jù)庫(RSSI與位置的映射關(guān)系).在線定位階段,采集待定位點信息,利用相關(guān)匹配算法與指紋庫中指紋進行匹配計算,來估計待定位點的最佳位置的坐標(biāo)點.

然而,室內(nèi)環(huán)境的復(fù)雜且多變導(dǎo)致了信號的非視距傳播,研究發(fā)現(xiàn)基于傳播模型的定位算法精度,一般情況為10米以上,而基于指紋匹配的定位方法通過獲取更多的樣本信息,在80%-90%的可信區(qū)間內(nèi),其定位精度可到5-8米左右.2000年微軟公司開發(fā)了基于Wi-Fi網(wǎng)絡(luò)的RADAR定位系統(tǒng)[3],此系統(tǒng)利用Wi-Fi指紋匹配的方法,使用K-NN算法,取最近k個鄰居的坐標(biāo)平均值為位置估計值,并基于RSSI信號的統(tǒng)計特性,采用貝葉斯原理,通過計算目標(biāo)位置的后驗概率分布進行定位.Zhou提出了基于本地信息熵的方法來實現(xiàn)Wi-Fi指紋匹配定位,研究表明增加接入點,可提高定位的精度[4].王鳳使用聚類的方法對射頻的接收信號強度進行時間、位置、設(shè)備異構(gòu)等因素進行聚類分析,并使用樸素貝葉斯模型,定位精度達4m,準(zhǔn)確率達80%,定位速度提高50%[5].張勇提出一種SVM和加權(quán)質(zhì)心相結(jié)合的算法,定位精度和準(zhǔn)確度較高,但定位時間較長[6].王超使用KNN方法實現(xiàn)基于指紋匹配的室內(nèi)定位,定位平均誤差達3.25m[7].周瑞提出將支持向量機(SVM)分類與回歸分析相結(jié)合的Wi-Fi指紋定位算法,以提高定位精度[8].田增山采用徑向基函數(shù)插值的方法,利用一部分 RSS被重新測量的參考點,擬合出接收信號強度曲面,估計出鄰近未知參考點 RSS值,從而更新指紋數(shù)據(jù)庫[9].Joaquín針對基于距離函數(shù)、RSS值的數(shù)據(jù)表現(xiàn)方式以及閾值策略的Wi-Fi指紋的機器學(xué)習(xí)和專家系統(tǒng)進行了探討[10].

綜上所述,目前國內(nèi)外學(xué)者的持續(xù)關(guān)注和深入研究運用機器學(xué)習(xí)方法來提高室內(nèi)定位精度、魯棒性、定位速度.但由于無線信號的波動性給高精度魯棒性定位帶來較大的挑戰(zhàn),基于Wi-Fi指紋的定位技術(shù)還需解決的核心問題包括數(shù)據(jù)的采集和數(shù)據(jù)的預(yù)處理,所以本文的主要研究內(nèi)容將包括:采集和搭建基于Wi-Fi RSSI的室內(nèi)定位指紋庫以及設(shè)計增強型的聚類算法對Wi-Fi指紋定位庫進行聚類分析,旨在使定位精度和定位速度達到平衡.

2 基于Wi-Fi指紋庫的定位算法研究

2.1 研究架構(gòu)

本文研究分為三個階段,分別是Wi-Fi指紋樣本采集并存儲、機器學(xué)習(xí)算法應(yīng)用和實驗結(jié)果及定位性能分析.本文的研究架構(gòu)如圖1所示.

圖1 架構(gòu)流程圖

其中Wi-Fi指紋樣本采集存儲階段主要功能為Wi-Fi RSSI信息的采集,其他因素的采集和與真實物理點建立映射關(guān)系,并將數(shù)據(jù)存于wifi_location數(shù)據(jù)庫中.定位階段主要功能是使用K-Means、FCM 對Wi-Fi指紋定位庫進行聚類分析,并使用自定義的匹配算法RSSMatch,對經(jīng)過K-Means的待定位點進行指紋匹配,得出最佳位置估計值.實驗結(jié)果及性能分析階段主要是通過對定位結(jié)果的分析,得到定位性能各類指標(biāo),并自動更新wifi_location數(shù)據(jù)庫.

2.2 樣本采集及搭建數(shù)據(jù)庫

數(shù)據(jù)采集的實際場景的部分平面圖如圖2所示.接入點(AP)覆蓋廣且密集,AP信號易受其他信號干擾(zigbee、藍牙等),網(wǎng)絡(luò)環(huán)境復(fù)雜.

如圖2所示,黃色方格為Wi-Fi的AP,每層約有18個左右的AP.實驗采用工具Xirrus Wi-Fi Inspector對實驗場地內(nèi)Wi-Fi信號的進行抓包處理,每個采樣位置點進行約10-20次采樣,其中每個方向按早中晚三個時間段進行3次采樣,得到如表1所示數(shù)據(jù).

圖2 數(shù)據(jù)采集的實際場景的部分平面圖

表1 部分Wi-Fi信息

其中“連接”為是否連接AP;SSID為AP的名稱;“強度”為接收信號值,其單位為dbm.

從采集后的數(shù)據(jù)分析可知,Wi-Fi RSSI在單個位置上存在約-10dbm的數(shù)據(jù)波動和某個短時間的數(shù)據(jù)跳變現(xiàn)象.但長時間內(nèi)在室內(nèi)環(huán)境無較大變化情況下,各AP的RSSI在某位置保持相對穩(wěn)定.于是將當(dāng)前此地點的各AP的Wi-Fi RSSI進行保存,生成Wi-Fi _network_report.csv文件作為Wi-Fi信號原始數(shù)據(jù).并通過wifi_location進行缺損值及非法變量進行過濾,得較完整的原始數(shù)據(jù).

通過Node.js和Express搭建web服務(wù).此web服務(wù)為用戶提供輸入當(dāng)前坐標(biāo)值、方向、運動速率、是否遮蔽和是否為熱點路徑的數(shù)據(jù)接口,并使用MySQL數(shù)據(jù)庫對數(shù)據(jù)進行存儲,并過濾非法數(shù)據(jù).將Wi-Fi的_network_report.csv數(shù)據(jù)和通過web服務(wù)得到的數(shù)據(jù)加載在基于MySQL的wifi_location數(shù)據(jù)庫中.使用RODBC組件,將數(shù)據(jù)庫wifi_location中數(shù)據(jù)導(dǎo)入到R工程中,數(shù)據(jù)庫數(shù)據(jù)導(dǎo)入R工程.

2.3 基于K-Means的定位過程

由于Wi-Fi指紋庫中數(shù)據(jù)量龐大,直接使用指紋匹配算法會導(dǎo)致計算量激增,耗時嚴(yán)重,并且定位精度低.本文首先基于K-Means方法對Wi-Fi指紋庫進行聚類分析,具體實現(xiàn)步驟為:

(1)對當(dāng)前Wi-Fi指紋庫提取指紋信息,包括RSSI、位置、AP名稱、AP的MAC、方向、是否遮蔽等信息,加載于矩陣wifio中;

(2)使用R中K-Means算法,以歐式距離作為距離函數(shù)模型,分別選取不同的聚類數(shù)對RSSI、位置、AP名稱、AP的MAC等進行聚類分析處理;

(3)比較得到不同的聚類中心,選擇最優(yōu)的聚類中心保存于wifidata中;

(4)使用RSSMatch算法將聚類中心與待定位點的指紋進行匹配,得到位置的估計值;

(5)與真實的位置點進行比較,評估定位性能.在定位階段,對當(dāng)前待測點的Wi-Fi RSSI和其他因素使用K-Means方法,進一步減少計算量,加快定位時間,并在聚類后,剔除部分異常數(shù)據(jù),提高定位精度.具體實現(xiàn)如下:

(1)對待測點進行每0.25s采集一次樣本,采集2s,共4次樣本;

(2)將樣本導(dǎo)入R工程中,進行K-Means聚類;

(3)提取各聚類中心中子集數(shù)最多的2個簇中心,作為當(dāng)前此位置Wi-Fi指紋;

(4)使用自定義匹配算法RSSMatch,與Wi-Fi指紋庫中的已完成的聚類中心進行匹配,估計當(dāng)前位置坐標(biāo)值;

(5)與該地點的真實坐標(biāo)值進行比較,得出定位結(jié)果、精度誤差和定位時間.

其中RSSMatch算法主要流程為:

(1)將wifidata中的RSSI進行歸一化處理;

(2)將指紋庫中的聚類中心、當(dāng)前Wi-Fi指紋和遞歸步長輸入,一般為0.1;

(3)通過閾值計算,分別用Wi-Fi指紋的各因素與聚類中心進行比較;

(4)得到5個及以上的位置估計點,則轉(zhuǎn)(6);

(5)以步長進行遞歸操作,直到得到5個及以上的位置估計點;

(6)得到的位置估計點,再次進行數(shù)據(jù)過濾,得到真正的位置估計點,輸出.

2.4 基于FCM的定位過程

由于K-Means存在不能發(fā)現(xiàn)大小差別很大的簇或非凸形狀的簇,對離群點和噪聲比較敏感等缺點,本文接著基于FCM算法對Wi-Fi指紋定位庫進行聚類分析.具體實現(xiàn)步驟為:

(1)對當(dāng)前Wi-Fi指紋庫提取指紋信息,包括RSSI、位置、AP名稱、AP的MAC、方向、是否遮蔽等信息,加載于矩陣wifio中;

(2)使用FCM算法,選擇歐式距離作為距離模型,設(shè)置單一簇最大子集數(shù),一般為100,設(shè)置初始簇數(shù).分別選取不同的聚類數(shù)對RSSI、位置、AP名稱、AP的MAC、方向等進行聚類分析處理;

(3)分別得到不同的聚類中心,并進行比較,選擇最優(yōu)的聚類中心保存于wifidata中;

(4)使用RSSMatch算法將聚類中心與待定位點的指紋進行匹配,得到位置的估計值;

(5)與真實的位置點進行比較,評估定位性能.

2.5 基于ECS的定位過程

實驗結(jié)果表明,由于FCM在定位精度優(yōu)于K-Means,但在消耗時間方面,卻明顯劣于K-Means.本文結(jié)合FCM和K-Means各自的優(yōu)勢,提出增強型的聚類算法(ECS)應(yīng)用于Wi-Fi指紋匹配定位中,旨在使定位精度和定位速度達到平衡.具體實現(xiàn)步驟如下:

(1)對Wi-Fi指紋定位庫進行K-Means分析,其中簇數(shù)Nk為300-5000,得簇中心點{Rk1,Rk2...Rkn},其中kn=Nk;

(2)對簇中心{Rk1,Rk2...Rkn}使用FCM 分析,其中簇數(shù)Nf為20-100,得簇中心{Rf1,Rf2...Rfn},其中fn=Nf;

(3)使用自定義匹配算法RSSMatch與簇中心{Rf1, Rf2...Rfn},其中fn=Nf,進行匹配,得到定位估計值,并評估定位性能.

3 實驗結(jié)果分析

使用R繪制的聚類效果如圖3所示.從該圖可知, FCM的聚類效果要好于K-Means的聚類效果,ECS的聚類效果最佳.

圖3 Wi-Fi指紋聚類中心圖

當(dāng)Wi-Fi指紋定位庫聚類數(shù)分別為10,20,50,75, 100,150,200,300時,表2和表3分別為基于K-Means和FCM得到定位性能表.如表可知,當(dāng)指紋庫的聚類數(shù)為50-100時均得到較好的定位效果,定位精度和定位速度均較好.在定位精度上FCM總體優(yōu)于K-Means,但消耗時間要明顯劣于K-Means算法.在聚類數(shù)為75時,估計點為1個,精度誤差為0.9966m,為最佳定位效果.

表2 K-Means定位性能表

表3 FCM的定位性能表

ECS的定位性能如表4所示,從該表的數(shù)據(jù)可知,隨著聚類數(shù)的增加,運行時間也增加,但整體提高了定位性能.較僅使用FCM算法,ECS算法的時間縮短約50%-80%,且定位精度上有所改善;在定位精度方面,較僅使用K-Means算法,ECS算法的定位精度提高約20%-40%,且定位穩(wěn)定性較強.

表4 ECS的定位性能表

為了進一步確定K-Means和FCM選取的初始最佳聚類數(shù),本文將估計位置個數(shù)少于4,平均精度小于8.000m,最小精度小于 1.5000m,最大精度小于10.000m,進行數(shù)據(jù)整理,得到的數(shù)據(jù)如表5所示.

表5 ECS的較佳定位性能表

由表5的數(shù)據(jù)可知,在K-Means聚類數(shù)較小時,定位精度較高且定位速度較快.而FCM的聚類數(shù)一般保持在50左右,定位效果最佳.其中當(dāng)K-Means的聚類數(shù)為300,FCM的聚類數(shù)為50時,估計位置個數(shù)為1個,平均精度為0.6884m,運行時間為1.38s.為了達到定位精度和定位速度的平衡,本文在結(jié)合K-Means和FCM優(yōu)勢的實驗過程中,以K-Means為主,FCM為輔的策略,一般選擇K-Means的聚類數(shù)為300-1000, FCM聚類數(shù)為50-75.這策略的平均精度可達4m以內(nèi),最小精度誤差達1m以內(nèi),并且估計位置數(shù)較少,運行時間較少.

本文使用K-Means聚類數(shù)為300,FCM聚類數(shù)為75,在實際場景中,隨機定位50次,驗證此策略的準(zhǔn)確性.圖4為部分待定位點的定位性能表.

圖4 部分待定位點的定位性能分析

由實驗可知,各待定點的定位效果不盡相同,84%的定位點的平均誤差小于8m,71%的定位點的最小誤差小于5m,28%的定位點的平均誤差小于2m,平均聚類數(shù)為1.53個.實驗發(fā)現(xiàn),各待定位點的定位性能與該待定位點在Wi-Fi指紋定位庫中的指紋的稀疏程度有關(guān),如果待定位點附近的指紋越密集,定位效果越好,如待定位點(-27,40)和(0,0);反之,如果待定位點附近指紋稀疏,則定位效果較差,如待定位點(-36,-82)和(10,-65).

圖5 平均耗時比較

圖6 定位點誤差的標(biāo)準(zhǔn)方差比較

同時,在機器配置為Intel core i3 3.4G CPU和4G內(nèi)存的情況下,把本文的策略和已發(fā)表算法就定位處理的平均耗時和定位點誤差的標(biāo)準(zhǔn)方差進行算法的性能比較,得到如圖5和圖6所示的結(jié)果,從圖中可以看出,相對于其它的算法,本文所提出的策略具有更有的定能性能.

4 總結(jié)

本文基于Wi-Fi指紋庫,研究了基于Wi-Fi指紋匹配方法的室內(nèi)定位技術(shù).此研究提高了室內(nèi)定位的精度,減少定位的時間,增強定位的穩(wěn)定性,達到了預(yù)期的效果.但隨著采樣數(shù)據(jù)的增加,指紋庫不斷變化和越發(fā)龐大,使用K-Means和FCM都需要提前確定簇數(shù),如何動態(tài)自適應(yīng)選擇簇數(shù),來盡可能實現(xiàn)更好的聚類分析,提供可靠的位置估計值,提高定位性能,是下一階段的研究重點.同時,如何較均勻地采集Wi-Fi指紋,以進一步提高定位性能,也是以后研究的方向.

1顏俊杰.基于Wi-Fi的室內(nèi)定位技術(shù)研究[碩士學(xué)位論文].廣州:華南理工大學(xué),2013.

2其寬.基于位置指紋的無線室內(nèi)定位技術(shù)研究[碩士學(xué)位論文].秦皇島:燕山大學(xué),2015.

3 Bahl P,Padmanabham V.RADAR:An in-buliding RF-based user location and tracking system.Institute of Electrical& Electronics Engineers Inc,2000,2:775–784

4 Zhou M,Tian Z,Xu K,Yu X,Wu H.Theoretical entropy assessment of fingerprint-based Wi-Fi localization accuracy. Expert Systems withApplications,2013,40(15):6136–6149.

5王鳳.基于聚類的射頻指紋定位技術(shù)研究[碩士學(xué)位論文].北京:北京郵電大學(xué),2014.

6張勇,徐小龍,徐科宇.基于加權(quán)質(zhì)心法的WLAN室內(nèi)定位系統(tǒng).電子測量與儀器學(xué)報,2015,29(7):1–4.

7王超.基于WLAN室內(nèi)定位的分類算法研究與實現(xiàn)[碩士學(xué)位論文].北京:北京郵電大學(xué),2015.

8周瑞,袁興中,黃一鳴.基于卡爾曼濾波的WiFi-PDR融合室內(nèi)定位.電子科技大學(xué)學(xué)報,2016,45(3):399–404.

9田增山,代海鵬.基于曲面擬合的 WiFi指紋數(shù)據(jù)庫更新.計算機應(yīng)用,2016,36(5):1192–1195.

10 Joaquín TS,Raúl M,Sergio T.Comprehensive analysis of distance and similarity measures for Wi-Fi fingerprinting indoor positioning systems.Expert Systems with Applications, 2015,42(23):9263–9278.

Enhanced Positioning Strategy Based on K-Means and FCM for Wi-Fi Fingerprint

CHEN Ying1,2,SHAN Wen-Jie1,YANG Feng-Yu1

1(School of Software,Nanchang Hangkong University,Nanchang 330063,China)
2(Internet of Things Technology Institute,Nanchang Hangkong University,Nanchang 330063,China)

The data processing algorithm is studied to improve Wi-Fi fingerprint indoor positioning performance.Firstly, Wi-Fi fingerprint samples are collected and then are put into MySQL database and R project.Secondly,the Wi-Fi fingerprint data is divided into several clusters,and the K-mean clustering(K-Means)and fuzzy C-means clustering (FCM)are used to cluster the Wi-Fi fingerprint respectively.Finally,an enhanced clustering strategy(ECS)is proposed to for Wi-Fi fingerprint matching.Experimental results show that ECS reduces the positioning time-consuming about 50%-80%than that consumed by only using FCM and the positioning accuracy is also improved;ECS improves about 20%-40%than that obtained by only using K-Means in terms of positioning accuracy and it proves positioning stability and can automatically update the Wi-Fi fingerprint database.

Wi-Fi fingerprint;K-Means;FCM;enhanced positioning strategy

江西省自然科學(xué)基金(20161BAB212034);南昌航空大學(xué)博士啟動基金(EA201520009)

2016-09-01;收到修改稿時間:2016-10-12

10.15888/j.cnki.csa.005771