基于區(qū)域分類(lèi)和電子地圖的室內(nèi)定位研究

牛福娟，滕 凱，楊 行，邢宗義

（南京理工大學(xué) 自動(dòng)化學(xué)院，南京 210094）

近年來(lái)智慧城市概念的興起和云計(jì)算技術(shù)的大規(guī)模應(yīng)用帶動(dòng)了基于位置信息服務(wù)（LBS, Location Based Service）產(chǎn)業(yè)的快速發(fā)展。地鐵作為現(xiàn)代社會(huì)出行工具的代表，以其安全、快速、便捷的優(yōu)勢(shì)受到視障人士的普遍青睞。研究地鐵環(huán)境中面向盲人服務(wù)的定位及導(dǎo)航技術(shù)，能夠有效地幫助視障人士獨(dú)立出行，促進(jìn)建立更為和諧、公平的社會(huì)環(huán)境。

大部分地鐵站不提供供電接口，且運(yùn)營(yíng)單位限制站內(nèi)設(shè)施改動(dòng)（如地面埋入接收器，屋頂、廊柱安裝接收器掛架等）?；趇Beacon 的低功耗藍(lán)牙定位技術(shù)具有組網(wǎng)方式簡(jiǎn)單、設(shè)備接入端不依賴(lài)外部供電、中遠(yuǎn)距離內(nèi)定位精度高的特點(diǎn)，非常適用于地鐵站內(nèi)定位。

目前，基于藍(lán)牙的室內(nèi)定位算法主要有基于接收信號(hào)強(qiáng)度指示（RSSI, Received Signal Strength Indication）的測(cè)距室內(nèi)定位[1]和基于信號(hào)指紋庫(kù)的匹配定位[2]。基于指紋匹配的定位方法不依賴(lài)路徑損耗模型，可有效降低藍(lán)牙信號(hào)的多徑效應(yīng)和非視距傳播對(duì)定位精度的影響；在離線訓(xùn)練階段，使用高效的機(jī)器學(xué)習(xí)算法，往往能夠獲得預(yù)期的定位精度；因而，該方法被廣泛地研究和使用[3]。目前，比較主流的一類(lèi)匹配算法是確定性方法，通過(guò)歐氏距離或馬氏距離，在指紋庫(kù)中選取距離最小的位置信息，常見(jiàn)的有NN（Nearest Neighbor）算法等，這類(lèi)方法對(duì)iBeacon 信號(hào)強(qiáng)度的精度和穩(wěn)定性要求較高，在實(shí)際場(chǎng)景中經(jīng)常出現(xiàn)定位節(jié)點(diǎn)非連續(xù)跳動(dòng)的問(wèn)題。另一類(lèi)匹配算法是統(tǒng)計(jì)分析法，此類(lèi)算法考慮信號(hào)的方差分布和條件分布等因素，并結(jié)合機(jī)器學(xué)習(xí)算法，能夠?qū)崿F(xiàn)2 m 左右的定位精度，如基于K-Means 的聚類(lèi)算法[4]、貝葉斯網(wǎng)絡(luò)算法[5]和粒子濾波算法[6]等。另外，融合傳感器信息和室內(nèi)地圖匹配的輔助技術(shù)也是提升室內(nèi)定位精度的一種有效方法，這種基于位置點(diǎn)的匹配算法可實(shí)現(xiàn)在直線道路、多邊形區(qū)域等各種路況下準(zhǔn)確的定位校準(zhǔn)，但在用戶(hù)位置出現(xiàn)間斷時(shí)，僅用該算法也很難實(shí)現(xiàn)準(zhǔn)確的位置匹配[7]。

本文研究的定位算法首先利用支持向量機(jī)（SVM,Support Vector Machine）算法，對(duì)待定位區(qū)域進(jìn)行離線分類(lèi)；在線匹配定位過(guò)程中利用滑動(dòng)窗口，對(duì)待定位區(qū)域進(jìn)行2 級(jí)分類(lèi)，進(jìn)一步控制誤差范圍；最后，結(jié)合站內(nèi)電子地圖，對(duì)乘客定位坐標(biāo)進(jìn)行糾偏。在實(shí)驗(yàn)室和地鐵站場(chǎng)景中的實(shí)驗(yàn)表明，該定位方法具有更好的定位效果。

1 基于SVM 和滑動(dòng)窗口的位置匹配算法

Android 應(yīng)用端可接收到的iBeacon 信息包括：該模塊對(duì)應(yīng)的通用唯一標(biāo)識(shí)符（UUID, Universally Unique Identifier）、識(shí)別某個(gè)定位區(qū)域的區(qū)域號(hào)Major、識(shí)別區(qū)域內(nèi)各個(gè)iBeacon 的Minor、RSSI 值及接收端距藍(lán)牙模塊的距離d。d與RSSI 滿(mǎn)足對(duì)數(shù)路徑距離損耗模型：

其中，P(dB)為 在距離d處的接收功率，P(dEF)為在參考距離dEF（ 通常取值為1 m）處的接收功率，n為路徑損耗指數(shù)（一般在2～4 之間）， ξ為路徑損耗因子。

該位置指紋定位算法的實(shí)現(xiàn)分為離線訓(xùn)練和在線匹配2 個(gè)階段。在離線訓(xùn)練階段，對(duì)各觀察點(diǎn)采集的藍(lán)牙信號(hào)強(qiáng)度進(jìn)行特征分析，利用自適應(yīng)高斯算法進(jìn)行降噪，建立各觀察點(diǎn)的位置指紋特征，再通過(guò)SVM 算法將數(shù)據(jù)對(duì)象聚攏成M個(gè)簇。在線定位階段，選擇簇內(nèi)已匹配位置的周邊定位點(diǎn)構(gòu)建動(dòng)態(tài)窗口，進(jìn)一步降低移動(dòng)過(guò)程中位置匹配的時(shí)間復(fù)雜度；同時(shí)，利用ArcGIS 提供的導(dǎo)航接口，在路徑層糾正位置坐標(biāo)并顯示。該方法完整的算法流程包括數(shù)據(jù)預(yù)處理、離線訓(xùn)練、在線位置匹配與顯示，如圖1 所示。

圖1 定位算法流程

1.1 數(shù)據(jù)預(yù)處理

藍(lán)牙信號(hào)強(qiáng)度序列，在位置點(diǎn) (xi,yi)處的觀察數(shù)據(jù)記為(L;R)={L(xi,yi);rssi1,rssi2,···,rssii,···,rssiK}；其中，L(x,y)代 表由位置點(diǎn)序號(hào)組成的鄰接矩陣，K為位置點(diǎn)的最大序列號(hào)，rssii代表在位置點(diǎn) (xi,yi)處采集到的m維RSSI 序列（m為區(qū)域內(nèi)iBeacon 的數(shù)量，為保證采集到的RSSI 值具有代表性，要求 |rssii|≥100）。

將區(qū)域劃分為大小為1 m2的均勻網(wǎng)格，并按順序標(biāo)號(hào)。數(shù)據(jù)預(yù)處理階段包括RSSI 數(shù)據(jù)采集和濾波2 個(gè)過(guò)程。數(shù)據(jù)采集格式包含相應(yīng)位置點(diǎn)的序號(hào)以及對(duì)于信號(hào)微弱以至檢測(cè)不到的iBeacon 模塊，在m 維特征向量中將其對(duì)應(yīng)的信號(hào)強(qiáng)度值設(shè)為?200 dBm。

藍(lán)牙信號(hào)在傳輸過(guò)程中受到多徑效應(yīng)和非視距傳輸?shù)挠绊?，RSSI 值隨時(shí)間的波動(dòng)較大，跨度高達(dá)20 dBm。故采用高斯函數(shù)擬合的方式對(duì)測(cè)量數(shù)據(jù)進(jìn)行處理，能夠有效減少一些小概率、大干擾事件對(duì)整體測(cè)量的影響，明顯減小測(cè)距誤差。自適應(yīng)高斯濾波算法（AGF, Adaptive Gaussian Filtering）通過(guò)迭代尋優(yōu)，選擇適合RSSI 序列特征的最優(yōu)濾波模板，與固定濾波模板值的傳統(tǒng)高斯濾波相比，具有更好的降噪和平滑效果。

自適應(yīng)高斯濾波使用高斯函數(shù)，即正態(tài)分布的概率密度函數(shù)：

其中， σ表示待測(cè)點(diǎn)的RSSI 序列標(biāo)準(zhǔn)差， μ表示一維信號(hào)濾波模板的大小。

在預(yù)處理階段，檢測(cè)不同 μ對(duì)應(yīng)的均值誤差，均值誤差error定義為：

其中，N為在序號(hào)為i的位置點(diǎn)處測(cè)量的總次數(shù)，在經(jīng)過(guò)高斯濾波后的值， δ 為rssiik的均值。通過(guò)迭代優(yōu)化，選取errormin對(duì) 應(yīng)的 μ值作為高斯濾波的最優(yōu)模板。

在實(shí)驗(yàn)室環(huán)境下，利用AGF 算法對(duì)采集的樣本數(shù)據(jù)濾波，圖2 為濾波前后的效果。

圖2 采集樣本AGF 算法濾波前后的效果

分別采用GF 和AGF 濾波后的數(shù)據(jù)建立指紋數(shù)據(jù)庫(kù)，并利用相同的算法進(jìn)行在線位置匹配，在各個(gè)位置點(diǎn)計(jì)算誤差小于1.5 m 的位置匹配正確率，定位精度對(duì)比如圖3 所示。采用GF 濾波算法時(shí)，各個(gè)位置點(diǎn)匹配正確率的均值為83.7%，當(dāng)使用AGF 算法時(shí)該值為87.5%。

圖3 2 種濾波方法的定位精度對(duì)比

1.2 支持向量機(jī)模型

支持向量機(jī)是一種2 類(lèi)分類(lèi)模型，其基本模型定義為特征空間上間隔最大的線性分類(lèi)器，學(xué)習(xí)策略是間隔最大化。對(duì)樣本信號(hào)強(qiáng)度集合組成的m維特征向量，可利用非線性函數(shù) φ(x)將輸入空間數(shù)據(jù)映射到高維特征空間，并在該空間構(gòu)造最優(yōu)分類(lèi)超平面[8]：

其中， ω為權(quán)值矢量，b為 偏差， ω和b確 定分類(lèi)面的位置。為找到式（4）對(duì)應(yīng)的最優(yōu)分類(lèi)超平面，需求解帶約束的最大值問(wèn)題[9]：

其中，C是懲罰因子，與SVM 分類(lèi)對(duì)錯(cuò)誤樣本的重視程度成正比。求解這類(lèi)待約束的最小值問(wèn)題，需要應(yīng)用拉格朗日方程，經(jīng)過(guò)一系列變換可將該2次規(guī)劃問(wèn)題轉(zhuǎn)化為相應(yīng)的對(duì)偶問(wèn)題[10]，即：

1.3 基于滑動(dòng)窗口的在線指紋匹配

將RSSI 變化的范數(shù)的倒數(shù)作為當(dāng)前狀態(tài)的估計(jì)值：

通常取p=2，即用Euclid 距離的倒數(shù)來(lái)表征觀測(cè)特征向量X與位置指紋向量的相似度。

SVM 多分類(lèi)器要在M個(gè)子區(qū)域中訓(xùn)練分類(lèi)器模型，將X代入各分類(lèi)器模型，目標(biāo)值ci=+1對(duì)應(yīng)的子區(qū)域即為當(dāng)前位置所屬的子區(qū)域。

滑動(dòng)窗口可理解為：在2 次在線匹配的時(shí)間間隔內(nèi)，盲人乘客的行走距離有限，可選擇前一個(gè)定位點(diǎn)鄰近的位置點(diǎn)作為下一個(gè)的匹配區(qū)域；隨著乘客移動(dòng)，窗口范圍在不斷發(fā)生變化。窗口的形狀定義為：

其中，窗口的大小可調(diào)整，并在子區(qū)域邊界舍棄部分鄰近點(diǎn)。最后，在窗口中選取K(K≥2)個(gè)w值較小的位置點(diǎn)，作為最后定位的參考點(diǎn)，并將其對(duì)應(yīng)坐標(biāo)的平均值作為位置估計(jì)的結(jié)果，稱(chēng)為KNN（K-Nearst Neighbors）算法[11]，計(jì)算公式為：

由此可避免在子區(qū)域中進(jìn)行全局搜索，降低了時(shí)間復(fù)雜度，并減少定位點(diǎn)不連續(xù)的情況。

2 室內(nèi)電子地圖與地圖糾偏

不同于室外地圖，室內(nèi)地圖尚未形成統(tǒng)一行業(yè)標(biāo)準(zhǔn)，相同的室內(nèi)場(chǎng)景可能具有不同風(fēng)格的地圖表現(xiàn)形式[12]。計(jì)算機(jī)中主要有4 種地理數(shù)據(jù)表示方法：柵格表示法、矢量表示法、柵格和矢量數(shù)據(jù)的圖層表示法、面向?qū)ο蟊硎痉ā１鞠到y(tǒng)中采用混合矢量和柵格的圖層表示法，圖層按類(lèi)型主要?jiǎng)澐譃? 種：點(diǎn)、線和面。每一層（Layer）是某一類(lèi)元素的集合，表示某一類(lèi)地圖信息，如盲道、電梯、問(wèn)詢(xún)臺(tái)等。此外，還有一些擴(kuò)展應(yīng)用圖層，如網(wǎng)格要素圖層、導(dǎo)航連接點(diǎn)層以及標(biāo)注層等[13]。

網(wǎng)格要素圖層是為數(shù)據(jù)采集而添加的圖層，該圖層中每個(gè)網(wǎng)格存儲(chǔ)當(dāng)前網(wǎng)格的坐標(biāo)和位置序號(hào)等屬性，用于為數(shù)據(jù)采集階段提供每個(gè)網(wǎng)格的屬性信息，以及在線定位階段進(jìn)行位置糾偏[14]。本系統(tǒng)利用ArcGIS 軟件的ArcCatalog 生成網(wǎng)絡(luò)數(shù)據(jù)集（Network Dataset)和地址定位器，將各圖層信息加入到指定地圖中，為程序提供可調(diào)用的導(dǎo)航接口[15]。

定位系統(tǒng)在Android 應(yīng)用端實(shí)現(xiàn)，App 會(huì)根據(jù)盲人乘客選擇的目的地為其規(guī)劃路徑（盡量沿盲道）。網(wǎng)格層記錄路徑層對(duì)應(yīng)的位置序號(hào)，當(dāng)盲人乘客的定位坐標(biāo)偏離路徑時(shí)，將其“拉”回既定路徑，定位點(diǎn)糾偏模型如圖4 所示。a為前一時(shí)刻盲人乘客的位置坐標(biāo)，b為 當(dāng)前時(shí)刻的實(shí)際坐標(biāo)，c為在線位置匹配結(jié)果；判斷c是否偏離既定路徑，若是則計(jì)算其“投影”在既定路徑上所對(duì)應(yīng)的位置序號(hào)，以進(jìn)一步降低KNN 算法的定位偏差。

圖5 為利用ArcGIS 軟件制作的廣州地鐵蘇元站地下一層站廳層的電子導(dǎo)航地圖（局部）。

圖5 廣州地鐵蘇元站站廳層電子地圖（局部）

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

實(shí)驗(yàn)場(chǎng)景為廣州地鐵蘇元站地下一層，定位區(qū)域面積2 600 m2。在此區(qū)域內(nèi)，以3 m間隔距離，橫縱方向均勻地部署iBeacon（支持BLE4.0 協(xié)議）；采用華為榮耀6X Android 手機(jī)完成應(yīng)用端的數(shù)據(jù)采集、指紋匹配和位置顯示等功能，圖6 為App 操作界面。

圖6 Android 應(yīng)用端操作界面

將定位區(qū)域劃分為2 436 個(gè)參考點(diǎn)進(jìn)行信號(hào)采集，采集的藍(lán)牙信號(hào)指紋數(shù)據(jù)格式為：位置點(diǎn)序號(hào)、位置點(diǎn)相對(duì)坐標(biāo)、傳感器類(lèi)型標(biāo)識(shí)和RSSI 數(shù)組；將iBeacon 廣播頻率設(shè)置為10 Hz，每個(gè)參考點(diǎn)上采集200 組數(shù)據(jù)構(gòu)造訓(xùn)練集。表1 為使用3 種定位算法分別處理實(shí)驗(yàn)導(dǎo)航定位數(shù)據(jù)得出的定位誤差距離統(tǒng)計(jì)。

表1 3 種定位算法的定位誤差距離統(tǒng)計(jì)

從表1 可知，基于KNN 的傳統(tǒng)指紋匹配算法的定位誤差集中分布于≥2 m 的范圍，誤差為1 m 左右的觀測(cè)點(diǎn)很少；利用SVM 對(duì)定位區(qū)域進(jìn)行分類(lèi)訓(xùn)練后，可提高誤差距離在2 m 左右的觀察點(diǎn)占比，但并未改善整體的定位效果。與之相比，本文提出的算法將定位精度在1 m 以?xún)?nèi)的觀測(cè)點(diǎn)提升到55%，整體定位精度的提高較為明顯。同時(shí)，該算法采用2級(jí)分類(lèi)，將在線定位時(shí)間復(fù)雜度由O(n)降低為其中，n為 數(shù)據(jù)對(duì)象總數(shù)，M為子區(qū)域的數(shù)目，|W|為滑動(dòng)窗口規(guī)模。

綜上所述，該算法具有快速和高精度的特點(diǎn)，非常適用于地鐵站內(nèi)面向盲人乘客服務(wù)的實(shí)時(shí)定位。

4 結(jié)束語(yǔ)

針對(duì)地鐵站內(nèi)多徑效應(yīng)嚴(yán)重及iBeacon 節(jié)點(diǎn)的RSSI 值波動(dòng)較大的問(wèn)題，提出一種迭代尋優(yōu)的自適應(yīng)高斯濾波模型，用于對(duì)采集的信號(hào)強(qiáng)度數(shù)據(jù)進(jìn)行預(yù)處理，利用濾波后的采樣數(shù)據(jù)均值建立采集點(diǎn)位置的特征向量；在離線階段，利用支持向量機(jī)模型對(duì)待定位區(qū)域進(jìn)行1 級(jí)分類(lèi)，將其劃分為若干子區(qū)域；在線定位時(shí)，僅需遍歷子區(qū)域一次，并利用KNN 算法確定初始位置，利用滑動(dòng)窗口進(jìn)一步縮小待匹配區(qū)域，實(shí)現(xiàn)對(duì)待定位區(qū)域的2 級(jí)分類(lèi)，可有效降低匹配算法的時(shí)間復(fù)雜度，解決定位點(diǎn)非連續(xù)跳躍的問(wèn)題；利用Android 手機(jī)端的電子地圖路徑層信息，對(duì)行走路徑上的錯(cuò)誤定位點(diǎn)糾偏，進(jìn)一步降低KNN 算法帶來(lái)的定位偏差。

實(shí)驗(yàn)結(jié)果及數(shù)學(xué)分析表明：該定位算法的定位精度和實(shí)時(shí)性可滿(mǎn)足地鐵站內(nèi)面向盲人乘客定位服務(wù)的要求。