基于改進型KNN算法和Android平臺的室內定位技術研究

李昂　肖甫　李雷

摘 要：通過分析基于WiFi定位的傳統位置指紋算法的不足之處，文中提出了一種旨在提高精度并減小計算復雜度的改進型KNN算法。通過Android平臺對該算法進行實現和測試，分析比較K的取值、AP的位置及數量等因素對定位精度的影響。測試結果表明，該算法不但能夠保證位置指紋室內定位的精度，還能有效減小計算復雜度，具有一定的可行性。

關鍵詞：精度；計算復雜度；改進型KNN算法；Android平臺

中圖分類號：TP301；TN92 文獻標識碼：A 文章編號：2095-1302（2018）03-00-05

0 引 言

伴隨著互聯網應用的快速發展，人們在室內停留的時間越來越多，室內位置信息對人們的日常生活愈加重要，因此人們對室內定位有著愈發強烈的需求[1-3]。由于利用GPS和AGPS這兩種定位方式進行室內定位時，信號會受到各種障礙物的遮擋[4]，因此亟待出現新型的室內定位方式。

隨著無線局域網絡（Wireless Local Area Networks，WLAN）遍布各地，智能手機和平板電腦等個人電子設備發展迅速，這些設備幾乎都使用WiFi連接網絡，用戶可使用WiFi進行定位[5-7]。iOS，Android和WP是目前三大主流移動操作系統。其中，Android系統所占的市場份額日益增大，因此完全可以選擇Android系統作為載體，設計基于WiFi的室內定位系統[8-11]。本文基于Android平臺設計了一種基于改進的位置指紋算法，首先收集采樣點的信號強度值信息，并將其保存到數據庫中，然后將定位時的數據和數據庫相互對比進行估算，得到所要定位的坐標信息。

1 基于WiFi的室內定位技術簡介

雖然目前實現WiFi室內定位的方法有很多，但主要使用基于測距的定位方法。其中基于RSSI的定位方法最受關注[12-16]。基于RSSI的定位算法流程如圖1所示。

2 傳統位置指紋定位技術

目前，在研究基于WiFi的室內定位時，位置指紋定位技術使用較多[17-21]，受到了廣泛關注。

2.1 技術原理

基于位置指紋定位算法的原理圖如圖2所示。

從圖2可以看出，位置指紋定位算法主要包括離線工作階段和在線工作階段。離線階段即數據收集階段，首先選擇一個區域，從中選取多個采樣點，然后收集這些點WiFi信號的強度值RSSI，并將其作為位置指紋保存到指紋數據庫中。在這個指紋數據庫中，每個指紋都由一組RSSI值組成，且對應一個位置坐標。在線階段即定位階段，將待測目標定位的信息與指紋庫進行匹配，最后估算出當前位置坐標，完成定位[22]。在WiFi環境下，使用位置指紋定位算法RSSI定位工作過程如圖3所示。

在選取的定位區域中，l個采樣點可以收集n個RSSI值來表示一個指紋，遍歷所有采樣點并獲得各自的RSSI值，保存于指紋庫中。指紋庫內容如式（1）所示：

其中：RSSIji表示在第i個采樣點所測的WiFi信號的第j個RSSI值；FPi=（RSSI1i，RSSI2i，…，RSSImi）表示任意一個位置的指紋數據，同時該指紋數據也可用坐標（x，y）表示。因此，指紋數據與坐標相互對應，其坐標如式（2）所示：

位置指紋數據庫由式（1）和式（2）共同組成。

除了在離線階段創建一個比較準確的指紋數據庫，在線階段指紋庫的匹配算法也十分重要[23]。常用的匹配算法有最近鄰法、K近鄰法和加權K近鄰法。

（1）最近鄰算法（NN）

最近鄰算法是一種比較常用的匹配算法，當待測目標進入定位所選區域時，可獲得一個相關的指紋信息lf=（RSSI1，RSSI2，…，RSSIn），然后將這個指紋信息與指紋數據庫中的信息相匹配，再算出它們之間的距離，其距離如式（3）所示[24，25]，其中距離最小也就是相似度最大指紋信息min（d（lf，FPi）），即待測目標的位置。

式中：RSSIj和RSSIji分別為定位點和指紋點的強度值；n是WiFi信號的個數。

最近鄰算法操作十分簡單，且容易實現，但是其可選擇的參考點較為單一，定位時容易產生誤差，精度不高。

（2）K近鄰算法（KNN）

相較于最近鄰算法，K近鄰算法可選擇的參考點有所增多。匹配待測目標的指紋信息，并找出與指紋數據庫中最近鄰的K（K>2）個指紋信息，通過計算坐標的平均值就可以估算出待測目標的位置，其位置如式（4）所示[26，27]：

式中：（xi，yi）是被選擇的第i個指紋數據庫中的信息所對應的坐標。

（3）加權K 近鄰法（WKNN）

加權K近鄰法是對K近鄰法的一種改進。K近鄰法選取的K個最小距離對最后的定位結果貢獻相同，取平均值，但距離越小對定位結果坐標的貢獻越大。因此，對所取的K個最小距離進行權值分配，距離越小，權值越大。K個權值ωk之和為1。ωk可自行設定，也可由式（5）計算得出[28，29]：

2.2 技術性能與存在的問題

當前的位置指紋算法雖然可以實現室內定位，但該算法依然存在一些問題，主要體現在以下方面：

（1）算法模型過于簡單，僅能滿足較為簡單的室內環境的定位要求。當室內環境較為復雜，如家具等陳設較多、有移動物體或人走動時，該傳統算法的定位精度無法滿足要求。

（2）該算法在線工作階段的運算量較大，尤其當AP個數較多或K取值較大時，運算量急劇增長，無疑增加了該算法的運行成本和復雜度。

3 一種改進的KNN算法

考慮到上述傳統位置指紋算法存在的問題，對傳統位置指紋算法作如下改進：

（1）面對更復雜的室內環境，應當建立更加符合實際的模型。傳統位置指紋算法的模型主要采用MK模型，如式（6）所示：

L（d）=L+10nlgd+NωLω+NfLf （6）

其中：L表示距離發射端1 m處的傳播損耗；n是路徑傳播損耗系數；d是發射端到接收端的距離；Nω和Nf分別是傳播路徑上穿過的墻壁和地板個數；Lω和Lf 分別是墻壁和地板的損耗系數。可見，傳統模型對于室內環境只考慮了墻壁和地板，而對于更復雜的情況沒有考慮。

因此提出一種新的更符合實際的模型，充分考慮了除墻壁和地板外包括人在內的其他障礙物，如式（7）所示：

式（7）與式（6）的不同之處在于最后一項，假設共有m種障礙物，Pi表示遇到第i種障礙物的概率，可以通過最小二乘法計算得出；Ni表示穿過第i種障礙物的個數，Li表示第i種障礙物的損耗系數。

（2）針對運算量較大的問題，提出一種減少運算復雜度的新方法。經試驗證明，在RSSI算法中，信號強度的衰減速度與傳輸距離成指數關系，即距離小時衰減快，距離大時衰減慢。尤其當到達一定距離后，其衰減速度趨于平緩，即信號強度變化較小。因此，如果按照傳統KNN算法讓所有的RSSI值都參與到計算中，勢必會造成較大的冗余開銷。

基于上述現象，需確定一個距離閾值，大于該距離時RSSI變化較小，可以舍棄，而小于該距離時則為有效點，應予以采納。由此可較大程度地減小運算量。在實際仿真中發現，該門限距離取8 m和10 m時定位精度差距不大，但運算量減小了約50%。

對于運算和精度有同樣重要影響的還有AP的個數與算法中K的取值。仿真試驗表明，AP的個數對于精度和運算量影響巨大。當AP數量增加且分布較均勻時，定位的精度較高，但同時運算量較大。而K的取值對于精度和運算量的影響則呈現出不同的規律，并非K的取值越大精度越高。因此，AP的個數與K的取值應當在精度和運算量之間權衡。

綜合上述兩個方面的改進，本文提出了一種用于室內定位的改進KNN算法。

4 改進KNN算法的Android實現與測試

本文所設計的定位系統包括收集部分和定位部分，客戶端為Android移動端APP，在運行時用戶首先通過收集模塊將采樣點信號的信息提交給數據庫，然后定位時將定位信息與數據庫進行匹配，即可估算出位置。這款軟件的理論設計內容如圖4所示。

4.1 實現

（1）收集模塊設計

當位置指紋定位算法處于離線收集階段時，首先需要選取合適的區域進行信息收集，理論上需要在選取的區域內放置4個無線路由器，其WiFi信號的強度值RSSI比較穩定，測試結果誤差較小，但本文的收集模塊選用4個隨機WiFi信號以及各自對應的強度值作為參考點。然后在區域內選取若干個采樣點，其位置已知，將檢測到的每個采樣點的4種信號強度值均放入創建的指紋數據庫中，此時指紋庫中的每個采樣點將由一系列RSSI值組成[30]。如果此時的室內環境發生變化，那么RSSI值也將發生變化且定位出現誤差[31]。收集模塊流程如圖5所示。

（2）定位模塊設計

當位置指紋定位算法處于在線定位階段時，首先獲取待測目標位置的RSSI值，然后使用本文提出的改進KNN算法即可估算出待測目標的位置。定位模塊流程如圖6所示。

（3）指紋數據庫設計

考慮到數據量并不龐大，因此選擇SQLite數據庫。創建的數據庫如圖7所示。

4.2 測試方案與結果分析

（1）測試方案

在本次測試中選取了C104，C108，C112三間教室和大廳作為測試場地。

在這三間教室中，C112面積最大，約10 m×10 m；C104與C108面積較小且相近，約7 m×7 m；而大廳面積與C112相近，但較為空曠，如圖8、圖9所示。計劃每間教室分別選取4個角落位置作為采樣點，三間教室共12個采樣點；而大廳內計劃選取6個采樣點，如圖10所示。本測試主要檢測在面積大小、AP個數、K取值和室內環境均不相同的條件下，所提出的改進KNN算法的性能。

（2）測試結果

教室C104，C108和C112測試結果見表1所列。

從表1可知，由教室C104和C108所測得的4組數據的誤差系數明顯小于C112的數據。

教室C108內有人時的測試結果見表2所列。

由表2可知，相較于無干擾時的結果，有干擾時得出的定位誤差系數大，即誤差較大。大廳測試結果見表3所列。

由表3可知，相較于環境復雜的教室，在較為空曠的大廳所獲得的誤差系數較小，較準確。

（3）測試結果分析

a.同一間教室有無干擾時的結果對比分析

根據在教室C108測得的兩組數據，對采樣點的真實位置和定位結果進行對比分析，如圖11所示。

在圖11中，實心圓表示采樣點的真實位置，空心圓表示教室內無干擾時定位的結果，空心三角形表示教室內有干擾時定位的結果。真實位置和定位結果兩點相連，其連線直觀地顯示了兩點間的差距，這種差距即定位誤差。相較于教室內有干擾時的定位結果，無干擾時產生的誤差明顯較小。

b.大小相近的教室與空曠空間的結果對比分析

在教室測試的數據里隨機抽取6組并與在大廳測試的數據進行對比分析，如圖12所示。

在圖12中，折線1表示教室內采樣點的測試誤差系數，折線2表示大廳內采樣點的測試誤差系數。可以很明顯地看出，折線1的誤差系數整體比折線2大，因此，在大廳內產生的誤差較小。

5 結 語

本文針對基于WiFi的室內定位常用的傳統KNN算法中存在的問題，提出了一種改進型KNN算法，在面對更復雜的室內環境時可以保證精度，并有效降低運算復雜度。基于Android平臺對這一改進算法進行了實現和測試，測試結果表明，該算法達到了預期效果，具有一定的可行性。

參考文獻

[1] 姜樂水.淺談無線局域網（WLAN）技術[J].信息技術與信息化，2012（5）：64-67.

[2] 潘焱，田華，魏安全.無線通信系統與技術[M].北京：人民郵電出版社，2011：147-148.

[3] 張瑞生，劉曉輝.無線局域網搭建與管理[M].電北京：子工業出版社，2011：14.

[4] 劉智敏，陽凡林，獨知行.衛星定位原理及應用的教學改革與實踐[J].測繪工程，2010，19（3）：77-80.

[5] 袁晶.大規模軌跡數據的檢索、挖掘和應用[D].合肥：中國科學技術大學，2012.

[6] 王建平，余根堅，李曉穎，等.無線網絡技術[M].北京：清華大學出版社，2013：180-181.

[7] 黎連業，王安，李龍.無線網絡與應用技術[M].北京：清華大學出版社，2013：104-105.

[8] 姜莉.基于WiFi室內定位關鍵技術的研究[D]. 大連：大連理工大學，2010.

[9] 陳典全.LBS中基于軌跡的用戶行為特征分析[J].全球定位系統，2011，36（6）：58-61.

[10] 羅紀清，萬恩秀.超聲引導下不同定位方法在體外碎石中的應用[J].檢驗醫學與臨床，2017，14（2）：261-263.

[11] 宋偉清，周廉，白濤，等.基于逐元暗電流抑制的紅外線探測器讀出電路研究[J].紅外，2015，36（4）：13-19.

[12] 熊永平，孫利民，牛建偉，等.機會網絡[J].軟件學報，2009，20（1）：124-137.

[13] 龔世雄.淺析RFID技術及其應用[J].中國科技信息，2013（3）：52-53.

[14] 高仁強，張曉盼，熊艷，等.模糊數學的WiFi室內定位算法[J].測繪科學，2016，41（10）：142-148.

[15] 盧恒惠，劉興川，張超，等.基于三角形與位置指紋識別算法的WiFi定位比較[J].移動通信，2010，34（10）：72-76.

[16] 李揚.WiFi技術原理及應用研究[J].科技信息，2010（6）：241.

[17] 賀遠華，黎洪生.距離幾何的TOA無線定位算法[J].計算機工程與應用，2010，46（12）：112-114.

[18] 魯丹宇，高春利，劉浩然.基于無線時鐘同步的超寬帶TDOA定位系統設計[J].節能， 2017，36（1）：66-68.

[19] S TOMIC，M BEKO， D RUI，et al. Distributed RSS-AoA based localization with unknown transmit powers[J].IEEE wireless communication letters， 2016，5（4）：1.

[20] 薛衛星，邱衛寧，花向紅，等.RSSI信號特征值對WiFi室內定位精度的影響分析[J].測繪地理信息，2016，41（4）：23-26.

[21] 孫學康，劉勇.無線傳輸與接入技術[M].北京 ：人民郵電出版社，2010：298-301.

[22] 趙小東.Android平臺下基于無線信號強度的定位系統的實現[D]. 哈爾濱：哈爾濱工業大學，2011.

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

[24] CHEN L， L? M， QIAN Y. A personal route prediction system based on trajectory data mining[J].Information sciences an international journal. 2011，181（7）：1264-1284.

[25] 王陽，葉芝慧，馮奇，等. 基于Android的室內WiFi定位系統設計與實現[J].電子測量技術，2016，39（9）：16-19.

[26] 王考杰，鄭雪峰，宋一丁，等.面向軌跡數據流的KNN近似查詢[J].計算機工程，2011，37（16）：17-20.

[27] 李偉.Android中人為改變程序生命周期的研究[J].計算機應用與軟件，2013，30（9）：205-207.

[28] 羅利.基于Android的WiFi室內定位技術研究[D].成都：西南交通大學，2014.

[29] 卞國龍，黃海松，葛至崢，等.無線傳感器網絡節點定位技術的優化[J].激光雜志，2017，38（3）：69-74.

[30] 張建平.基于WiFi的室內定位系統設計和算法研究[J].自動化技術與應用，2016，35（12）：53-56.

[31] MAHAJAN R，BALASUBRAMANIAN A，VENKATARAMANI A，et al. Interactive WiFi connectivity for moving vehicles[J].Proceeding of sigcomn，2013， 38（4）：427-438.