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

陳 英,單文杰,楊豐玉

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

2(南昌航空大學 物聯網技術研究所,南昌 330063)

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

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

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

2(南昌航空大學 物聯網技術研究所,南昌 330063)

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

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

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

1 國內外研究現狀

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

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

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

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

2.1 研究架構

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

圖1 架構流程圖

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

2.2 樣本采集及搭建數據庫

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

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

圖2 數據采集的實際場景的部分平面圖

表1 部分Wi-Fi信息

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

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

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

2.3 基于K-Means的定位過程

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

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

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

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

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

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

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

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

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

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

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

其中RSSMatch算法主要流程為:

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

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

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

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

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

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

2.4 基于FCM的定位過程

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

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

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

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

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

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

2.5 基于ECS的定位過程

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

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

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

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

3 實驗結果分析

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

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

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

表2 K-Means定位性能表

表3 FCM的定位性能表

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

表4 ECS的定位性能表

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

表5 ECS的較佳定位性能表

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

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

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

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

圖5 平均耗時比較

圖6 定位點誤差的標準方差比較

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

4 總結

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

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

2其寬.基于位置指紋的無線室內定位技術研究[碩士學位論文].秦皇島:燕山大學,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王鳳.基于聚類的射頻指紋定位技術研究[碩士學位論文].北京:北京郵電大學,2014.

6張勇,徐小龍,徐科宇.基于加權質心法的WLAN室內定位系統.電子測量與儀器學報,2015,29(7):1–4.

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

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

9田增山,代海鵬.基于曲面擬合的 WiFi指紋數據庫更新.計算機應用,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

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

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

10.15888/j.cnki.csa.005771