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

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

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

0 引 言

隨著科技水平的快速發(fā)展，人們生活水平的提高，人們對于位置服務(wù)的需求不斷增長[1]。室外定位技術(shù)有著GPS定位系統(tǒng)的幫助，已經(jīng)非常成熟，其廣泛應(yīng)用于交通、救援、農(nóng)業(yè)、軍事等領(lǐng)域。GPS是當(dāng)前定位精度最穩(wěn)定、應(yīng)用最廣泛而且呈現(xiàn)市場壟斷狀態(tài)的衛(wèi)星導(dǎo)航系統(tǒng)[2]。近年來，中國自行研制的北斗衛(wèi)星導(dǎo)航系統(tǒng)（BDS）也成為繼GPS、GLONASS之后成熟的衛(wèi)星導(dǎo)航系統(tǒng)。在室外定位方面，北斗衛(wèi)星導(dǎo)航系統(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)準(zhǔn)確可靠地工作。室外定位導(dǎo)航技術(shù)無法直接應(yīng)用于室內(nèi)環(huán)境，而隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展和普及，室內(nèi)定位技術(shù)不可或缺。

室內(nèi)定位的研究起步較早，目前的室內(nèi)定位技術(shù)主要有射頻標(biāo)簽、超寬帶、ZigBee、藍(lán)牙、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ā)展方向和目標(biāo)為高定位準(zhǔn)確度和低功耗[4]。

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

本文對基于WiFi指紋的室內(nèi)定位系統(tǒng)進行了研究，并開發(fā)了基于Android平臺的室內(nèi)定位系統(tǒng)。本研究共分為三個部分，第一部分為指紋數(shù)據(jù)庫的創(chuàng)建過程，主要采集WiFi信號的接收信號強度指標(biāo)（Received Signal Strength Indication, RSSI）[6]，該指標(biāo)反映了當(dāng)前位置收集的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ū)域，確定原點坐標(biāo)，再將此區(qū)域人工劃分為多個小部分，每個小部分對應(yīng)一個坐標(biāo)點。在采集時，需要輸入該位置的坐標(biāo)點；然后到相應(yīng)坐標(biāo)點輸入信息進行采集，數(shù)據(jù)存入SQLite數(shù)據(jù)庫。一次測量的點的信息作為一組數(shù)據(jù)，最終通過多次測量得出平均值，即得到該點的WiFi指紋點。指紋采集流程如圖1所示。

圖1 指紋采集流程

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

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

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

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

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

為避免前K個最近的“鄰居”中所屬類別數(shù)相同而導(dǎo)致算法無法判別的情況，K值只取奇數(shù)。不同K值對定位精度的影響結(jié)果如圖2所示。從圖2可以看出，K取偶數(shù)值時定位精度優(yōu)于3 m的概率分布變化較不規(guī)則，不穩(wěn)定；K取奇數(shù)值時隨著K值增大，算法收斂加快，但是當(dāng)K值增大到一定程度時，算法收斂又逐漸減慢。從圖中可以看出，當(dāng)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算法最小誤差達(dá)到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算法進行匹配定位，可以達(dá)到不錯的定位效果。我們設(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坐標(biāo)值，提供該參考點位置。為使數(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ù)庫，來獲取參考點坐標(biāo)的指紋強度。系統(tǒng)會在其中錄入地圖，根據(jù)手機接收的信號強度與指紋數(shù)據(jù)庫相匹配，實現(xiàn)定位，并在地圖中標(biāo)記當(dāng)前用戶位置，誤差較小，可以達(dá)到較好的定位效果。為驗證程序可以正確進行，我們劃定了實驗區(qū)域，測試了本系統(tǒng)，如圖8所示。

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

3 結(jié) 語

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

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