基于WiFi 信號(hào)的室內(nèi)外聯(lián)合定位技術(shù)研究*

唐 杰，黃 銘，林建喜，程 騁，楊晶晶

（1.云南大學(xué) 信息學(xué)院，云南 昆明 650091；2.云南省無線電監(jiān)測中心，云南 昆明 650228）

0 引言

基于WiFi 信號(hào)定位主要應(yīng)用于室內(nèi)場景，最近已有許多學(xué)者開始研究基于WiFi 基礎(chǔ)設(shè)施的無GPS 室外定位服務(wù)[1]。與超寬帶定位技術(shù)、藍(lán)牙定位技術(shù)和慣性導(dǎo)航技術(shù)等比較，基于WiFi 位置指紋定位技術(shù)無需額外添加其他設(shè)備，且部署簡單、成本較低、定位范圍廣、精度較高[2]。因此，基于WiFi 技術(shù)實(shí)現(xiàn)定位是一個(gè)較好的選擇。當(dāng)前解決室內(nèi)外聯(lián)合定位問題技術(shù)的大多是衛(wèi)星定位系統(tǒng)與室內(nèi)定位組合技術(shù)，而且主要是針對在室內(nèi)外過渡區(qū)域平滑切換定位方法問題，文獻(xiàn)[3]提出了坐標(biāo)標(biāo)定法，使得室內(nèi)外坐標(biāo)達(dá)到一致。在過渡區(qū)域中使用越區(qū)切換方法，實(shí)現(xiàn)基于北斗和超寬帶的室內(nèi)外聯(lián)合高精度定位。城市環(huán)境或園區(qū)內(nèi)衛(wèi)星信號(hào)較差，但是已經(jīng)大量部署WiFi 網(wǎng)絡(luò)，文獻(xiàn)[4]設(shè)計(jì)了一種基于WiFi 信號(hào)的室外人員定位系統(tǒng)，通過動(dòng)態(tài)選取k個(gè)錨節(jié)點(diǎn)建立定位模型，并且改進(jìn)接收信號(hào)強(qiáng)度指示(Received Signal Strength Indicator,RSSI)測距方法以提高定位精度。文獻(xiàn)[5]設(shè)計(jì)了基于WiFi 信號(hào)的園區(qū)定位與導(dǎo)航系統(tǒng),提供了園區(qū)內(nèi)高精度定位服務(wù)。針對定位延遲問題，文獻(xiàn)[6]提出了分級(jí)定位方案，首先通過漢明距離確定多個(gè)子區(qū)域，再在子區(qū)域內(nèi)通過k 近鄰算法進(jìn)行精定位?；谖恢弥讣y的定位精度與其采集的指紋密度有關(guān)，通過空間插值法對其他位置的定位信息進(jìn)行擴(kuò)充可以提高定位精度，而且能夠降低前期數(shù)據(jù)采集工作量[7]。最近有研究者從室內(nèi)位置信息與定位信息融合角度出發(fā)進(jìn)行定位研究[8?9]，提出了基于知識(shí)圖譜WiFi 定位方法，側(cè)重于有效整合室內(nèi)WiFi 數(shù)據(jù)和空間環(huán)境特征信息。

基于上述對室內(nèi)外聯(lián)合定位的研究，本文針對云南大學(xué)呈貢校區(qū)建立了基于WiFi 信號(hào)的室內(nèi)外聯(lián)合定位圖模型，將物理空間位置、媒體接入控制(Media Access Control,MAC)地址和RSSI 關(guān)聯(lián)起來，實(shí)現(xiàn)了基于WiFi信號(hào)的室內(nèi)外聯(lián)合定位。實(shí)驗(yàn)結(jié)果表明，通過相似度算法進(jìn)行一次定位時(shí)，數(shù)據(jù)采集間隔與定位精度為同一數(shù)量級(jí)，且定位速度快；為了提高室內(nèi)定位精度，由三次樣條插值對室內(nèi)數(shù)據(jù)擴(kuò)充，在Jaccard 相似度算法的基礎(chǔ)上結(jié)合加權(quán)K 近鄰(Weighted K-Nearest Neighbor,WKNN)算法進(jìn)行二次定位。分級(jí)定位不僅提高定位精度，而且降低系統(tǒng)延遲時(shí)間。最后設(shè)計(jì)開發(fā)了基于WiFi 信號(hào)的室內(nèi)外聯(lián)合定位系統(tǒng)，便于獲得直觀的可視化位置信息。

1 定位圖模型與算法

1.1 定位圖模型

本文建立了基于WiFi 信號(hào)的室內(nèi)外聯(lián)合定位圖模型[10]，其表達(dá)式如式(1)所示。

定位圖模型框架如圖1 所示，主要分為數(shù)據(jù)采集節(jié)點(diǎn)與無線AP 節(jié)點(diǎn)兩部分。其中，Gt為t時(shí)刻的圖模型；t表示數(shù)據(jù)采集時(shí)間；Vt是數(shù)據(jù)采集節(jié)點(diǎn)集，N=|V|為數(shù)據(jù)采集節(jié)點(diǎn)數(shù)，數(shù)據(jù)類型包括MAC 地址、RSSI 和物理空間位置；Ut是無線AP 節(jié)點(diǎn)集，包含室外節(jié)點(diǎn)和室內(nèi)節(jié)點(diǎn)；Et是邊集，表示數(shù)據(jù)采集節(jié)點(diǎn)與無線接入點(diǎn)(Access Point,AP)節(jié)點(diǎn)的關(guān)系，用邊屬性表示，M=|E|為邊數(shù)；Xt用來表示節(jié)點(diǎn)屬性和邊屬性，室內(nèi)無線AP 節(jié)點(diǎn)屬性對應(yīng)樓層模型XYZ坐標(biāo)和MAC 地址，室外無線AP 節(jié)點(diǎn)屬性對應(yīng)經(jīng)緯度坐標(biāo)和MAC 地址，邊屬性對應(yīng)于RSSI。由于本文數(shù)據(jù)采集為同一時(shí)間段，物理空間中的幾何和物質(zhì)電磁特征基本不變，因此上述圖模型簡化為：G=(V,E,U,X)。

圖1 定位圖模型框架

RSSI 值進(jìn)行均值濾波處理后，按照定位圖模型中物理位置與WiFi 信息之間構(gòu)建的節(jié)點(diǎn)、邊及屬性關(guān)系，將數(shù)據(jù)存入Neo4j 圖數(shù)據(jù)庫中。由于采集的整個(gè)校園數(shù)據(jù)量較大，全部可視化不便于說明指紋庫中節(jié)點(diǎn)、關(guān)系及屬性之間的關(guān)聯(lián)，所以選取2 個(gè)室內(nèi)數(shù)據(jù)采集點(diǎn)和3 個(gè)室外數(shù)據(jù)采集點(diǎn)進(jìn)行解釋說明，圖模型指紋庫如圖2 所示。每一個(gè)圓圈為一個(gè)節(jié)點(diǎn)，連接兩個(gè)節(jié)點(diǎn)的線為邊，邊上的值為屬性。通過“ynu”節(jié)點(diǎn)將室內(nèi)外所有數(shù)據(jù)關(guān)聯(lián)整合在一起，“1”節(jié)點(diǎn)為室外部分，“0”節(jié)點(diǎn)為室內(nèi)部分。RSSI 為數(shù)據(jù)采集節(jié)點(diǎn)與無線AP 節(jié)點(diǎn)之間的邊屬性，同一個(gè)無線AP 節(jié)點(diǎn)可能與多個(gè)數(shù)據(jù)采集節(jié)點(diǎn)關(guān)聯(lián)。兩個(gè)節(jié)點(diǎn)間存在關(guān)系時(shí)，其鄰接矩陣的元素Aij取值為1，不存在關(guān)系時(shí)取值為0。在定位圖模型基礎(chǔ)上進(jìn)行一次、二次室內(nèi)外聯(lián)合定位。

圖2 定位圖模型指紋庫

1.2 定位算法

定位流程如圖3 所示，用戶上傳采集待測點(diǎn)的WiFi信息數(shù)據(jù)，將數(shù)據(jù)按照指紋庫指定格式存入數(shù)據(jù)庫中，先通過Jaccard 相似度算法估計(jì)用戶所在位置區(qū)域，區(qū)域標(biāo)簽判定室內(nèi)外位置，室外是標(biāo)簽1，室內(nèi)是標(biāo)簽0。若用戶在室外，則直接返回采用Jaccard 相似度算法計(jì)算的經(jīng)緯度坐標(biāo)；若用戶在室內(nèi)，則在相似度算法基礎(chǔ)上再通過機(jī)器學(xué)習(xí)算法進(jìn)行二次定位，進(jìn)一步得到用戶的具體位置。

圖3 定位流程圖

圖4 三次樣條插值原理圖

1.2.1 一次定位

Neo4j 擴(kuò)展包APOC(Awesome Procedures Of Cypher)和ALGO(Algorithms)提供高效的數(shù)據(jù)管理、查詢以及常用的圖算法。實(shí)驗(yàn)中通過Jaccard 相似度算法進(jìn)行一次定位，J(A,B)表示Jaccard 相似度系數(shù)，為兩個(gè)集合中相似元素占不重復(fù)元素的比例。將待測點(diǎn)A數(shù)據(jù)處理后存入指紋庫，與指紋庫中數(shù)據(jù)進(jìn)行組織、關(guān)聯(lián)，令指紋庫中的任意一個(gè)指紋點(diǎn)為指紋點(diǎn)B。待測點(diǎn)A和指紋點(diǎn)B數(shù)據(jù)形式分別為：

Jaccard 相似度算法計(jì)算方法如式(2)所示，其中Nm為待測點(diǎn)A中不同MAC 地址數(shù)量，Np為指紋點(diǎn)B中不同MAC 地址數(shù)量，Nh為待測點(diǎn)A與指紋點(diǎn)B相同MAC地址數(shù)量，計(jì)算出兩個(gè)指紋點(diǎn)中共同的MAC 地址數(shù)量與所有不重復(fù)MAC 地址數(shù)量的比值即為J(A,B)，再分別計(jì)算出待測點(diǎn)A與指紋庫中各個(gè)指紋點(diǎn)的相似度系數(shù)，系數(shù)最大的指紋點(diǎn)位置即為待測點(diǎn)A的估計(jì)位置。

1.2.2 二次定位

在Jaccard 相似度算法基礎(chǔ)上進(jìn)行一次定位后得到室內(nèi)樓層數(shù)據(jù)和位置區(qū)域，再通過機(jī)器學(xué)習(xí)算法進(jìn)行二次室內(nèi)定位。將RSSI 值作為輸入特征，(X,Y)位置坐標(biāo)作為輸出標(biāo)簽。數(shù)據(jù)結(jié)構(gòu)如表1 所示。

表1 指紋庫數(shù)據(jù)結(jié)構(gòu)

實(shí)驗(yàn)中先通過相似度算法獲取到樓層數(shù)據(jù)，不僅可以更加準(zhǔn)確地確定樓層信息，而且縮小定位范圍后，減小了機(jī)器學(xué)習(xí)定位時(shí)的數(shù)據(jù)量，從而減少系統(tǒng)定位時(shí)間。在機(jī)器學(xué)習(xí)算法中參數(shù)設(shè)置比較重要，直接關(guān)系到定位精度，支持向量機(jī)[11]和WKNN[12?14]兩種機(jī)器學(xué)習(xí)算法主要參數(shù)設(shè)置如表2 所示。

表2 SVM 和WKNN 主要參數(shù)設(shè)置

WKNN 算法是在KNN 算法的基礎(chǔ)上引入權(quán)重進(jìn)行改進(jìn)，使得定位誤差更小，主要分為以下四步：首先分別根據(jù)式(3)計(jì)算出在線RSSI 向量與指紋庫中第j個(gè)RSSI向量之間的歐式距離。

其中，RSSIi是在線待測數(shù)據(jù)的第i個(gè)RSSI 值；RSSIji是指紋庫中第j個(gè)指紋點(diǎn)的第i個(gè)RSSI 值；然后將所有指紋點(diǎn)距離大小排序后選取最小的前k個(gè)位置指紋{(X1,Y1),(X2,Y2),…,(Xk,Yk)}；再根據(jù)式(4)計(jì)算這k個(gè)位置指紋的加權(quán)平均值Wj。

最后根據(jù)賦予不同指紋點(diǎn)的權(quán)重值計(jì)算得到待測點(diǎn)估計(jì)坐標(biāo)(X,Y)，計(jì)算公式如式(5)所示。

1.2.3 三次樣條插值

通過三次樣條插值對室內(nèi)數(shù)據(jù)進(jìn)行擴(kuò)充，三次樣條插值[15]是一種改進(jìn)的分段三次函數(shù)插值法。其主要思想是由多個(gè)小分段的三次多項(xiàng)式組成一個(gè)表面，使其滿足最優(yōu)平滑原則。三次樣條插值基本原理如4 所示。

定義一個(gè)三次樣條函數(shù)S(x)，如式(6)所示，而且該函數(shù)滿足以下三個(gè)條件：

一是滿足三次函數(shù)：將整個(gè)區(qū)間[a,b]分成多個(gè)小區(qū)間，每一個(gè)小的區(qū)間都是一個(gè)三次函數(shù)，如式(7)所示。

二是滿足插值條件，即所有插值點(diǎn)都在一條曲線上；三是曲線光滑，即函數(shù)S(x)、其一階導(dǎo)數(shù)S'(x) 以及二階導(dǎo)數(shù)S''(x)在[a,b]上都連續(xù)。假定曲線上共有n個(gè)點(diǎn)，則分成n+1 個(gè)小區(qū)間，中間n?2 個(gè)點(diǎn)，則i=2,3,…,n?1，滿足第二和第三條件的公式表達(dá)式如式(8)所示。

邊界條件再補(bǔ)充兩個(gè)方程即可求解出三次樣條函數(shù)。三次樣條函數(shù)的每一個(gè)小區(qū)間都是一個(gè)平滑的曲線，能夠?qū)Σ逯祬^(qū)域進(jìn)行平滑化處理，對于空間屬性連續(xù)性較好的區(qū)域的插值精度高。

2 系統(tǒng)開發(fā)設(shè)計(jì)

定位系統(tǒng)是在Django 框架基礎(chǔ)上，再結(jié)合Three.js技術(shù)以及前端開發(fā)技術(shù)實(shí)現(xiàn)。系統(tǒng)總體架構(gòu)[8]如圖5 所示，主要由數(shù)據(jù)采集、服務(wù)端和可視化三部分組成。數(shù)據(jù)采集部分按照場景規(guī)劃采集路線，并在不同密度下采集物理空間位置信息和WiFi 信息；服務(wù)端由指紋庫構(gòu)建和在線定位兩個(gè)模塊構(gòu)成，首先將物理空間位置信息與WiFi 信息組織關(guān)聯(lián)起來建立定位圖模型，并將數(shù)據(jù)存入Neo4j 圖數(shù)據(jù)庫構(gòu)建位置指紋庫，再通過相似度算法和二次定位方法進(jìn)行在線定位?？梢暬糠滞ㄟ^SketchUp 和Three.js 技術(shù),在導(dǎo)入的衛(wèi)星地圖基礎(chǔ)上對云南大學(xué)呈貢校區(qū)進(jìn)行校園三維建模，通過前端開發(fā)技術(shù)結(jié)合校園三維模型將在線定位返回的結(jié)果進(jìn)行可視化。最后將定位測試系統(tǒng)部署在騰訊云服務(wù)器上，網(wǎng)址為http://114.132.53.243:8000/。

圖5 系統(tǒng)設(shè)計(jì)框圖

3 實(shí)驗(yàn)測試與分析

3.1 實(shí)驗(yàn)環(huán)境

云南大學(xué)呈貢校區(qū)已實(shí)現(xiàn)WiFi 信號(hào)全覆蓋，實(shí)驗(yàn)環(huán)境為校園室外主要道路以及信息學(xué)院室內(nèi)樓層，校園室內(nèi)外無線AP 部署如圖6 所示，主要部署在室內(nèi)樓道、房間內(nèi)和室外墻上。通過軟件GetSensorData 2.0 進(jìn)行數(shù)據(jù)采集，頻率為50 Hz，每個(gè)點(diǎn)采集時(shí)長約30 s。主要分為室內(nèi)和室外兩部分，室外采集規(guī)劃：室外采集根據(jù)實(shí)際環(huán)境進(jìn)行疏密區(qū)分，對信息學(xué)院外圍道路進(jìn)行密采集，兩個(gè)采集點(diǎn)間隔約5.5 m，格物樓、圖書館和軟件學(xué)院等建筑外圍道路采集間隔約11 m，建筑較少的寬闊區(qū)域采集間隔較大約30 m，共875 個(gè)數(shù)據(jù)采集點(diǎn)。室內(nèi)采集規(guī)劃：以信息學(xué)院大門處為原點(diǎn)，1 區(qū)走廊為X軸，2 區(qū)走廊為Y軸，空間樓層為Z軸建立三維立體坐標(biāo)系。沿著室內(nèi)樓層走廊間隔3 m 采集一次，每層樓約60 個(gè)采集點(diǎn)，共234 個(gè)數(shù)據(jù)采集點(diǎn)。

圖6 室內(nèi)外AP 分布圖

通過定位圖模型將采集的物理位置信息與WiFi 信息關(guān)聯(lián)整合在一起，定位圖模型中節(jié)點(diǎn)數(shù)量及其屬性如表3 所示，共建立1 109 個(gè)數(shù)據(jù)采集節(jié)點(diǎn)，11 651 個(gè)無線AP 節(jié)點(diǎn)和62 176 個(gè)節(jié)點(diǎn)屬性。

表3 圖模型節(jié)點(diǎn)及其屬性

3.2 系統(tǒng)功能測試

用戶通過手機(jī)軟件采集待測點(diǎn)WiFi 信號(hào)數(shù)據(jù)，將數(shù)據(jù)上傳本系統(tǒng)后可直接顯示用戶位置信息。圖7 是室內(nèi)定位結(jié)果可視化，待測點(diǎn)位置顯示在信息學(xué)院4 樓3407房間外面。

圖7 定位結(jié)果可視化

3.3 實(shí)驗(yàn)結(jié)果與分析

室外通過相似度算法進(jìn)行一次定位，在室外采集間隔11 m 時(shí)選取20 個(gè)測試點(diǎn)，采集間隔5.5 m 時(shí)選取25個(gè)測試點(diǎn)，室內(nèi)采集間隔3 m 時(shí)，隨機(jī)選取20 個(gè)測試點(diǎn)，得到相似度系數(shù)和平均定位誤差如表4 所示，可以看出，數(shù)據(jù)采集密度、相似度系數(shù)和定位精度是一個(gè)數(shù)量級(jí)。數(shù)據(jù)采集間隔越小，相鄰數(shù)據(jù)采集點(diǎn)采集到的共同MAC 地址越多，則Jaccard 相似度系數(shù)越大，定位精度越高。

表4 不同采集密度定位結(jié)果

通過相似度算法實(shí)現(xiàn)一次定位后，在其基礎(chǔ)上再通過機(jī)器學(xué)習(xí)算法進(jìn)行二次定位，進(jìn)一步提高室內(nèi)定位精度。其中，k值參數(shù)對WKNN 算法定位結(jié)果影響較大，設(shè)定k值較小時(shí)容易受指紋庫中個(gè)別奇異值影響，較大時(shí)則會(huì)受指紋庫中距離較遠(yuǎn)的指紋點(diǎn)影響，造成較大定位誤差。實(shí)驗(yàn)中選取33 個(gè)樣本測試點(diǎn)分別計(jì)算出k值取1 到10 時(shí)的平均定位誤差，從圖8 可以看出k=3 時(shí)平均誤差相比較其他k值平均誤差最小，所以本文中WKNN 算法中參數(shù)k為3。

圖8 不同k 值定位誤差

為了避免個(gè)別特殊測試點(diǎn)對定位結(jié)果造成影響，測試點(diǎn)選取應(yīng)從樣本容量、與離線位置是否重復(fù)以及不同區(qū)域多方面考慮。為了進(jìn)一步提高室內(nèi)定位精度，對室內(nèi)指紋庫進(jìn)行三次樣條插值擴(kuò)充，不同算法插值前后定位平均誤差如表5 所示。

表5 不同算法平均定位誤差

樣本N1 和N2 中的測試點(diǎn)采集位置與離線指紋庫中采集位置不重復(fù)，樣本N3 是在轉(zhuǎn)折區(qū)域位置進(jìn)行采集，所以樣本N1、N2 和N3 平均誤差較大，樣本N4 則是與離線指紋庫中數(shù)據(jù)位置重復(fù)采樣，定位平均誤差較小。從表5 可以看出，通過三次樣條插值后定位精度都有所提高，其中WKNN 算法插值前定位平均誤差為1.97 m，插值后3B-WKNN 算法定位平均誤差為1.66 m，平均誤差減小0.31 m。

對于室內(nèi)外過渡區(qū)域，選取信息學(xué)院入口區(qū)域?yàn)閷?shí)驗(yàn)場景，以門為邊界，向內(nèi)和向外分別采集15 和20 個(gè)測試點(diǎn)，實(shí)驗(yàn)結(jié)果如圖9 所示，門外部區(qū)域僅采用一次定位粗略估計(jì)以及門和墻壁遮擋，使得其定位誤差變化較大。過渡區(qū)域最大定位誤差為4.69 m，平均定位誤差為1.91 m，實(shí)驗(yàn)表明本文定位方法在過渡區(qū)域較為穩(wěn)定，而且避免了頻繁切換的問題。

圖9 過渡區(qū)域定位結(jié)果

通過相似度算法先確定待測點(diǎn)樓層位置信息，后續(xù)通過機(jī)器學(xué)習(xí)進(jìn)行二次定位時(shí)只需要用到確定的某一樓層的RSSI 值，其余樓層數(shù)據(jù)對定位精度不影響，減小了機(jī)器學(xué)習(xí)的計(jì)算時(shí)長。不同定位方法所需時(shí)間如表6所示。

表6 分級(jí)定位計(jì)算時(shí)間比較 （s）

從表6 中一次定位時(shí)間對比可知，相同數(shù)據(jù)量Jaccard 算法定位時(shí)長遠(yuǎn)小于WKNN 算法，針對較大定位場景比較有優(yōu)勢。由于WKNN 算法需要所有指紋點(diǎn)的數(shù)據(jù)維度一致，采集的指紋點(diǎn)增加以及無線AP 增多時(shí)，需要補(bǔ)充大量?110 dBm 數(shù)據(jù)，導(dǎo)致其定位時(shí)間較長難以達(dá)到實(shí)時(shí)定位要求，而定位圖模型將室內(nèi)外物理空間位置和WiFi 信息融合在一起，結(jié)合Jaccard 相似度算法高效計(jì)算、分析以及處理能力，可以極大地節(jié)約定位時(shí)間。但是結(jié)合表4 和表5 分析可知，Jaccard 相似度算法定位精度與數(shù)據(jù)采集密度較為密切，且定位精度小于WKNN算法。因此，基于定位圖模型的二次定位方法不僅可以提高室內(nèi)定位精度，而且減小了系統(tǒng)延時(shí)。

4 結(jié)論

本文針對云南大學(xué)呈貢校區(qū)建立了基于WiFi 信號(hào)室內(nèi)外聯(lián)合定位圖模型，有效地將室內(nèi)外物理位置信息與WiFi 信息融合在一起，通過二次定位提高定位精度、減小系統(tǒng)延時(shí)，最后設(shè)計(jì)開發(fā)了基于WiFi 信號(hào)的室內(nèi)外聯(lián)合定位系統(tǒng)，避免了組合定位技術(shù)在過渡區(qū)域切換定位方式的問題。下一步工作將從定位精度和系統(tǒng)功能兩方面對定位系統(tǒng)進(jìn)行改進(jìn)和擴(kuò)充，定位精度可以通過融合其他傳感器信息，如加速度傳感器、陀螺儀和氣壓計(jì)等；本文定位方法可以降低系統(tǒng)延遲，但是后期還需進(jìn)一步完善系統(tǒng)、提高系統(tǒng)整體響應(yīng)能力，以及豐富系統(tǒng)功能，如添加導(dǎo)航功能等。