基于區域分類和電子地圖的室內定位研究

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

（南京理工大學 自動化學院，南京 210094）

近年來智慧城市概念的興起和云計算技術的大規模應用帶動了基于位置信息服務（LBS, Location Based Service）產業的快速發展。地鐵作為現代社會出行工具的代表，以其安全、快速、便捷的優勢受到視障人士的普遍青睞。研究地鐵環境中面向盲人服務的定位及導航技術，能夠有效地幫助視障人士獨立出行，促進建立更為和諧、公平的社會環境。

大部分地鐵站不提供供電接口，且運營單位限制站內設施改動（如地面埋入接收器，屋頂、廊柱安裝接收器掛架等）。基于iBeacon 的低功耗藍牙定位技術具有組網方式簡單、設備接入端不依賴外部供電、中遠距離內定位精度高的特點，非常適用于地鐵站內定位。

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

本文研究的定位算法首先利用支持向量機（SVM,Support Vector Machine）算法，對待定位區域進行離線分類；在線匹配定位過程中利用滑動窗口，對待定位區域進行2 級分類，進一步控制誤差范圍；最后，結合站內電子地圖，對乘客定位坐標進行糾偏。在實驗室和地鐵站場景中的實驗表明，該定位方法具有更好的定位效果。

1 基于SVM 和滑動窗口的位置匹配算法

Android 應用端可接收到的iBeacon 信息包括：該模塊對應的通用唯一標識符（UUID, Universally Unique Identifier）、識別某個定位區域的區域號Major、識別區域內各個iBeacon 的Minor、RSSI 值及接收端距藍牙模塊的距離d。d與RSSI 滿足對數路徑距離損耗模型：

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

該位置指紋定位算法的實現分為離線訓練和在線匹配2 個階段。在離線訓練階段，對各觀察點采集的藍牙信號強度進行特征分析，利用自適應高斯算法進行降噪，建立各觀察點的位置指紋特征，再通過SVM 算法將數據對象聚攏成M個簇。在線定位階段，選擇簇內已匹配位置的周邊定位點構建動態窗口，進一步降低移動過程中位置匹配的時間復雜度；同時，利用ArcGIS 提供的導航接口，在路徑層糾正位置坐標并顯示。該方法完整的算法流程包括數據預處理、離線訓練、在線位置匹配與顯示，如圖1 所示。

圖1 定位算法流程

1.1 數據預處理

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

將區域劃分為大小為1 m2的均勻網格，并按順序標號。數據預處理階段包括RSSI 數據采集和濾波2 個過程。數據采集格式包含相應位置點的序號以及對于信號微弱以至檢測不到的iBeacon 模塊，在m 維特征向量中將其對應的信號強度值設為?200 dBm。

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

自適應高斯濾波使用高斯函數，即正態分布的概率密度函數：

其中， σ表示待測點的RSSI 序列標準差， μ表示一維信號濾波模板的大小。

在預處理階段，檢測不同 μ對應的均值誤差，均值誤差error定義為：

其中，N為在序號為i的位置點處測量的總次數，在經過高斯濾波后的值， δ 為rssiik的均值。通過迭代優化，選取errormin對 應的 μ值作為高斯濾波的最優模板。

在實驗室環境下，利用AGF 算法對采集的樣本數據濾波，圖2 為濾波前后的效果。

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

分別采用GF 和AGF 濾波后的數據建立指紋數據庫，并利用相同的算法進行在線位置匹配，在各個位置點計算誤差小于1.5 m 的位置匹配正確率，定位精度對比如圖3 所示。采用GF 濾波算法時，各個位置點匹配正確率的均值為83.7%，當使用AGF 算法時該值為87.5%。

圖3 2 種濾波方法的定位精度對比

1.2 支持向量機模型

支持向量機是一種2 類分類模型，其基本模型定義為特征空間上間隔最大的線性分類器，學習策略是間隔最大化。對樣本信號強度集合組成的m維特征向量，可利用非線性函數 φ(x)將輸入空間數據映射到高維特征空間，并在該空間構造最優分類超平面[8]：

其中， ω為權值矢量，b為 偏差， ω和b確 定分類面的位置。為找到式（4）對應的最優分類超平面，需求解帶約束的最大值問題[9]：

其中，C是懲罰因子，與SVM 分類對錯誤樣本的重視程度成正比。求解這類待約束的最小值問題，需要應用拉格朗日方程，經過一系列變換可將該2次規劃問題轉化為相應的對偶問題[10]，即：

1.3 基于滑動窗口的在線指紋匹配

將RSSI 變化的范數的倒數作為當前狀態的估計值：

通常取p=2，即用Euclid 距離的倒數來表征觀測特征向量X與位置指紋向量的相似度。

SVM 多分類器要在M個子區域中訓練分類器模型，將X代入各分類器模型，目標值ci=+1對應的子區域即為當前位置所屬的子區域。

滑動窗口可理解為：在2 次在線匹配的時間間隔內，盲人乘客的行走距離有限，可選擇前一個定位點鄰近的位置點作為下一個的匹配區域；隨著乘客移動，窗口范圍在不斷發生變化。窗口的形狀定義為：

其中，窗口的大小可調整，并在子區域邊界舍棄部分鄰近點。最后，在窗口中選取K(K≥2)個w值較小的位置點，作為最后定位的參考點，并將其對應坐標的平均值作為位置估計的結果，稱為KNN（K-Nearst Neighbors）算法[11]，計算公式為：

由此可避免在子區域中進行全局搜索，降低了時間復雜度，并減少定位點不連續的情況。

2 室內電子地圖與地圖糾偏

不同于室外地圖，室內地圖尚未形成統一行業標準，相同的室內場景可能具有不同風格的地圖表現形式[12]。計算機中主要有4 種地理數據表示方法：柵格表示法、矢量表示法、柵格和矢量數據的圖層表示法、面向對象表示法。本系統中采用混合矢量和柵格的圖層表示法，圖層按類型主要劃分為3 種：點、線和面。每一層（Layer）是某一類元素的集合，表示某一類地圖信息，如盲道、電梯、問詢臺等。此外，還有一些擴展應用圖層，如網格要素圖層、導航連接點層以及標注層等[13]。

網格要素圖層是為數據采集而添加的圖層，該圖層中每個網格存儲當前網格的坐標和位置序號等屬性，用于為數據采集階段提供每個網格的屬性信息，以及在線定位階段進行位置糾偏[14]。本系統利用ArcGIS 軟件的ArcCatalog 生成網絡數據集（Network Dataset)和地址定位器，將各圖層信息加入到指定地圖中，為程序提供可調用的導航接口[15]。

定位系統在Android 應用端實現，App 會根據盲人乘客選擇的目的地為其規劃路徑（盡量沿盲道）。網格層記錄路徑層對應的位置序號，當盲人乘客的定位坐標偏離路徑時，將其“拉”回既定路徑，定位點糾偏模型如圖4 所示。a為前一時刻盲人乘客的位置坐標，b為 當前時刻的實際坐標，c為在線位置匹配結果；判斷c是否偏離既定路徑，若是則計算其“投影”在既定路徑上所對應的位置序號，以進一步降低KNN 算法的定位偏差。

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

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

3 實驗與結果分析

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

圖6 Android 應用端操作界面

將定位區域劃分為2 436 個參考點進行信號采集，采集的藍牙信號指紋數據格式為：位置點序號、位置點相對坐標、傳感器類型標識和RSSI 數組；將iBeacon 廣播頻率設置為10 Hz，每個參考點上采集200 組數據構造訓練集。表1 為使用3 種定位算法分別處理實驗導航定位數據得出的定位誤差距離統計。

表1 3 種定位算法的定位誤差距離統計

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

綜上所述，該算法具有快速和高精度的特點，非常適用于地鐵站內面向盲人乘客服務的實時定位。

4 結束語

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

實驗結果及數學分析表明：該定位算法的定位精度和實時性可滿足地鐵站內面向盲人乘客定位服務的要求。