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

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

0 引言

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

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

1 定位圖模型與算法

1.1 定位圖模型

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

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

圖1 定位圖模型框架

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

圖2 定位圖模型指紋庫

1.2 定位算法

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

圖3 定位流程圖

圖4 三次樣條插值原理圖

1.2.1 一次定位

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

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

1.2.2 二次定位

在Jaccard 相似度算法基礎上進行一次定位后得到室內樓層數(shù)據(jù)和位置區(qū)域，再通過機器學習算法進行二次室內定位。將RSSI 值作為輸入特征，(X,Y)位置坐標作為輸出標簽。數(shù)據(jù)結構如表1 所示。

表1 指紋庫數(shù)據(jù)結構

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

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

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

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

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

1.2.3 三次樣條插值

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

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

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

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

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

2 系統(tǒng)開發(fā)設計

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

圖5 系統(tǒng)設計框圖

3 實驗測試與分析

3.1 實驗環(huán)境

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

圖6 室內外AP 分布圖

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

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

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

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

圖7 定位結果可視化

3.3 實驗結果與分析

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

表4 不同采集密度定位結果

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

圖8 不同k 值定位誤差

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

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

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

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

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

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

表6 分級定位計算時間比較 （s）

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

4 結論

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