基于KNN算法的室內(nèi)定位系統(tǒng)的設(shè)計與實現(xiàn)

吳雅琴，軒興棟，張玉婷，秦龍斌，王雨豪，吳 桐，吳 彤

（中國礦業(yè)大學（北京） 機電與信息工程學院，北京 100083）

0 引 言

隨著科技水平的快速發(fā)展，人們生活水平的提高，人們對于位置服務(wù)的需求不斷增長[1]。室外定位技術(shù)有著GPS定位系統(tǒng)的幫助，已經(jīng)非常成熟，其廣泛應(yīng)用于交通、救援、農(nóng)業(yè)、軍事等領(lǐng)域。GPS是當前定位精度最穩(wěn)定、應(yīng)用最廣泛而且呈現(xiàn)市場壟斷狀態(tài)的衛(wèi)星導航系統(tǒng)[2]。近年來，中國自行研制的北斗衛(wèi)星導航系統(tǒng)（BDS）也成為繼GPS、GLONASS之后成熟的衛(wèi)星導航系統(tǒng)。在室外定位方面，北斗衛(wèi)星導航系統(tǒng)已經(jīng)廣泛應(yīng)用于交通運輸、測繪地理信息、應(yīng)急搜救等領(lǐng)域，逐步滲透到人們生活的方方面面，為全球經(jīng)濟和社會發(fā)展注入了新的活力。但由于衛(wèi)星信號容易受到障礙物的遮擋，與室外相比，室內(nèi)復(fù)雜多變的建筑墻體會極大削弱室外的衛(wèi)星信號，使衛(wèi)星定位技術(shù)無法在室內(nèi)準確可靠地工作。室外定位導航技術(shù)無法直接應(yīng)用于室內(nèi)環(huán)境，而隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展和普及，室內(nèi)定位技術(shù)不可或缺。

室內(nèi)定位的研究起步較早，目前的室內(nèi)定位技術(shù)主要有射頻標簽、超寬帶、ZigBee、藍牙、WiFi、紅外線、超聲波和可見光等技術(shù)[3]。其中，WiFi指紋定位技術(shù)有著廣泛運用。在室內(nèi)環(huán)境下，WiFi普及率較高，易部署，而且利用智能手機就能得到WiFi的RSSI信息，采集方便。該定位技術(shù)定位成本較低，能滿足大多數(shù)室內(nèi)場景的定位精度需求，所以基于WiFi指紋的室內(nèi)定位技術(shù)將成為主流的室內(nèi)定位方案。

目前，在蘋果、微軟、華為等國際互聯(lián)網(wǎng)巨頭的引領(lǐng)之下，WiFi室內(nèi)定位技術(shù)發(fā)展迅速，其發(fā)展方向和目標為高定位準確度和低功耗[4]。

現(xiàn)今，移動設(shè)備的計算能力和存儲能力已有跨越式提升，如何有效降低WiFi室內(nèi)定位的功耗也是當前研究的熱點問題。一方面，通過改進WiFi室內(nèi)定位算法，在保證定位準確度的前提下，減少信號采集頻率并降低算法的復(fù)雜度[5]；另一方面，通過使用低功耗藍牙和運動檢測傳感器等有助于定位的其他低功耗設(shè)備，研究多技術(shù)結(jié)合的融合算法，來達到降低功耗的目的。

本文對基于WiFi指紋的室內(nèi)定位系統(tǒng)進行了研究，并開發(fā)了基于Android平臺的室內(nèi)定位系統(tǒng)。本研究共分為三個部分，第一部分為指紋數(shù)據(jù)庫的創(chuàng)建過程，主要采集WiFi信號的接收信號強度指標（Received Signal Strength Indication, RSSI）[6]，該指標反映了當前位置收集的WiFi信號強度值，通過WiFi信號的獲取與劃定采集區(qū)域來生成WiFi信號指紋數(shù)據(jù)庫[7]；第二部分為室內(nèi)定位算法的實現(xiàn)，我們使用K-近鄰位置指紋算法[8]，通過取得實時在線位置數(shù)據(jù)，在離線指紋庫中的指紋中找到多個與在線數(shù)據(jù)相近的數(shù)據(jù)[9]，將在線數(shù)據(jù)與數(shù)據(jù)庫中挑選的數(shù)據(jù)進行匹配，最終確定在線用戶的位置；第三部分為安卓客戶端的開發(fā)過程。

本文旨在根據(jù)已有的基于WiFi指紋的室內(nèi)定位技術(shù)思路，借助WiFi指紋數(shù)據(jù)庫構(gòu)建算法、室內(nèi)定位算法，搭建一套個人安卓客戶端的室內(nèi)定位系統(tǒng)。

1 算法的設(shè)計與實現(xiàn)

指紋技術(shù)的定位過程分為兩個階段，分別為離線采集階段和在線定位階段。在離線采集階段，需要獲取定位區(qū)域內(nèi)的信息并存儲到相應(yīng)數(shù)據(jù)庫中，以完成指紋庫的構(gòu)建。使用的采集設(shè)備為安卓手機，將數(shù)據(jù)庫直接部署在SQLite中，高效利用安卓資源。

在采集過程中，首先創(chuàng)建需要采集的區(qū)域信息（通過區(qū)域信息區(qū)分不同區(qū)域，以此正確匹配不同區(qū)域的WiFi指紋數(shù)據(jù)庫）；接著創(chuàng)建AP信息，采用錄入mac的方式進行；采集WiFi強度時只采集WiFi信號強度。根據(jù)確定的區(qū)域，確定原點坐標，再將此區(qū)域人工劃分為多個小部分，每個小部分對應(yīng)一個坐標點。在采集時，需要輸入該位置的坐標點；然后到相應(yīng)坐標點輸入信息進行采集，數(shù)據(jù)存入SQLite數(shù)據(jù)庫。一次測量的點的信息作為一組數(shù)據(jù)，最終通過多次測量得出平均值，即得到該點的WiFi指紋點。指紋采集流程如圖1所示。

圖1 指紋采集流程

定位算法的實現(xiàn)，我們選擇K-近鄰位置指紋算法（KNN）?；贙NN的指紋定位方法，是通過計算在線接收的RSS向量S=(s1, s2, s3, ..., sn)與數(shù)據(jù)庫中各參考點采集的RSS向量Ri=(ri1, ri2, ..., rin)間的歐氏距離進行匹配。兩者之間的歐式距離記為：

式中，i=1, 2, 3, ..., m, m是參考點總數(shù)。當D越小時表示S與對應(yīng)參考點R之間的匹配度越高，即用戶位置越接近參考點的位置。

根據(jù)以上原理，計算在線接收的向量S與每一個參考點向量的歐氏距離并根據(jù)歐氏距離進行從小到大的排序。取前k個參考點的位置信息，求得的均值即為用戶當前位置：

式中，(xi, yi)表示所選出的k個歐氏距離最小的參考點對應(yīng)的位置坐標。

在仿真與分析階段，我們利用PyCharm對算法進行仿真實驗，以驗證該算法的有效性，并與NN算法進行對比。本文進行了誤差分析實驗來評價KNN的定位精度。

為避免前K個最近的“鄰居”中所屬類別數(shù)相同而導致算法無法判別的情況，K值只取奇數(shù)。不同K值對定位精度的影響結(jié)果如圖2所示。從圖2可以看出，K取偶數(shù)值時定位精度優(yōu)于3 m的概率分布變化較不規(guī)則，不穩(wěn)定；K取奇數(shù)值時隨著K值增大，算法收斂加快，但是當K值增大到一定程度時，算法收斂又逐漸減慢。從圖中可以看出，當K=11時，定位效果最佳。

圖2 K值對定位精度的影響

本實驗設(shè)定K值為11，對定位區(qū)域采用KNN和NN算法進行定位誤差估計比較，并通過定位誤差范圍與誤差百分率進行體現(xiàn)，其結(jié)果如圖3所示。測試數(shù)據(jù)中每個點的定位誤差情況如圖4所示。

圖3 定位誤差范圍百分率分布圖

圖4 測試點定位誤差情況圖

從圖3中可以看出，KNN算法約77.8%的概率定位誤差在3 m以內(nèi)，而NN算法約72.57%的概率定位誤差在3 m以內(nèi)；從誤差分布情況分析，KNN算法收斂更快，KNN算法最大誤差小于NN算法。

兩種算法的定位誤差比較見表1所列。從定位誤差來看，NN算法最小值誤差為1 m，而KNN算法最小誤差達到0.15 m，能較好滿足室內(nèi)環(huán)境的定位需求。

表1 不同方法的定位誤差比較

2 客戶端設(shè)計與實現(xiàn)

關(guān)于本論文開發(fā)的室內(nèi)定位系統(tǒng)，我們利用WiFi進行定位，無需進行外部硬件設(shè)備的部署，方便且節(jié)約成本。我們開發(fā)的這個程序十分適合大型室內(nèi)場景，此程序依靠WiFi的RSSI特征，離線階段建立指紋數(shù)據(jù)庫，在線階段使用KNN算法進行匹配定位，可以達到不錯的定位效果。我們設(shè)計的室內(nèi)定位系統(tǒng)由數(shù)據(jù)采集系統(tǒng)和定位系統(tǒng)組成。完整功能模塊設(shè)計如圖5所示。

圖5 室內(nèi)定位系統(tǒng)功能模塊

指紋采集系統(tǒng)的主要功能為采集WiFi指紋和查看周圍已經(jīng)錄入?yún)^(qū)域的AP點。圖6為該系統(tǒng)的主界面。

圖6 指紋采集系統(tǒng)

我們在建立WiFi指紋數(shù)據(jù)庫時，在指定區(qū)域輸入x、y坐標值，提供該參考點位置。為使數(shù)據(jù)更加精確，我們進行了多次測量，減小誤差。且測量時間間隔可自由設(shè)定，使用方便。WiFi指紋采集成功后會錄入SQLite數(shù)據(jù)庫存儲，后續(xù)進行統(tǒng)一管理。圖7所示為錄入?yún)⒖键c信息界面。

圖7 指紋采集過程示意圖

在系統(tǒng)“查看周圍已經(jīng)錄入?yún)^(qū)域的AP點”功能中，我們可以查看已經(jīng)錄入的AP點，并查看AP點的強度信號，也可以進行管理，實現(xiàn)區(qū)域內(nèi)AP點的增加和刪除。

我們還開發(fā)了定位系統(tǒng)。在程序中介入了建成的指紋數(shù)據(jù)庫，來獲取參考點坐標的指紋強度。系統(tǒng)會在其中錄入地圖，根據(jù)手機接收的信號強度與指紋數(shù)據(jù)庫相匹配，實現(xiàn)定位，并在地圖中標記當前用戶位置，誤差較小，可以達到較好的定位效果。為驗證程序可以正確進行，我們劃定了實驗區(qū)域，測試了本系統(tǒng)，如圖8所示。

圖8 室內(nèi)定位系統(tǒng)測試

3 結(jié) 語

本文首先對KNN算法與NN算法進行對比，通過誤差分布情況得出KNN算法較NN算法更為精準，且收斂更快的結(jié)論。同時，又進一步確定了k值，并在實驗中驗證了該算法的正確性[10]。

開發(fā)設(shè)計了一套基于WiFi指紋的室內(nèi)定位系統(tǒng)。本系統(tǒng)利用室內(nèi)已有的WiFi路由設(shè)備，無需額外部署，系統(tǒng)定位精度高。相較于RFID射頻識別技術(shù)和藍牙技術(shù)，成本較低，部署量較少，使用方便。與UWB技術(shù)相比，設(shè)備部署和操作都更為簡潔，能夠?qū)崿F(xiàn)更高的普及率。通過使用系統(tǒng)多次進行數(shù)據(jù)采集、定位實驗和數(shù)據(jù)校正，取得了理想的定位準確率。