基于區域網格劃分的SVM室內定位算法

賈春陽 郭之超

1(北京聯合大學智慧城市學院 北京 100101)2(北京航空航天大學計算機學院軟件開發環境國家重點實驗室 北京 100191)

0 引 言

位置服務LBS(Location Based Service)又稱為定位服務，是由衛星定位系統、廣域通信基站系統和室內定位系統等系統結合在一起提供綜合的定位服務。隨著通信設備的更新迭代和通信技術的不斷發展，定位服務技術也有了長遠發展，不再是初期只依靠定位衛星進行解算定位，而是發展成多種定位技術融合定位的階段，大大提高了定位精度，也不斷拓展了適用范圍，深刻影響了人們的生產生活[1]。

在室內定位技術方面，目前流行的定位技術主要有借助Wi-Fi定位、借助藍牙定位、借助廣域基站的附加信號定位等幾種方式進行定位。從基本技術原理上分析，所有的室內定位思路都基本相似，是通過不斷發送信號的固定基站或信標，為終端提供定位的手段，具體方法包括三角定位、無線頻譜定位等方式[3]。

基于IEEE 802.11 b/g/n協議的無線網絡在近年來得到迅速發展和普及，并廣泛應用于我們的生活場所中。支持Wi-Fi的終端也越來越多，智能手機、平板電腦、智能手表等物聯網設備也均包含了無線上網卡，這為Wi-Fi定位提供了必要的物質基礎與技術支持，使得基于Wi-Fi的無線定位成為可能[4]。由于室內信號傳播的復雜性，定位精度、維護成本、室內地圖等逐漸成為室內定位的約束條件[4]。

目前Wi-Fi應用于交通樞紐、機場、車站、商場等公共場所，具有廣泛的覆蓋面和普及面，并且智能手機都配有Wi-Fi通信功能。借助Wi-Fi的室內定位是網絡接入的附加功能，通過軟件實現定位，具有很好的復制應用能力。

1 手機Wi-Fi數據的信號特征

1.1 Wi-Fi信號強度的空間分布特征

室內定位的前提是移動設備接收到的RSSI信號強度值能夠反映其與AP的位置存在一定的相關性。在室內環境中，信號隨著距離信號源的距離增長會有一定程度的衰減。經過前人不斷的實驗證明，對數路徑損耗模型(Pass-Loss)經驗公式能夠符合Wi-Fi信號RSSI在空氣環境下的能量傳輸損耗，信號強度RSSI與AP的傳輸頻率f和信號的傳輸距離d相關，遵循以下公式：

(1)

式中:d0為所選取的參考點，PL(d0)為參考點d0處測量到的RSSI損耗值(記為A)，一般取d0=1，即選取距離AP一米處作為參考點。d為發射點到接收點的距離。n為路徑損耗指數，表示路徑損耗與距離增加的關系，它依賴于其所處的環境和建筑物是否有阻隔。PL(d0)為發射到接收間的損耗，通過實際測量得到PL(d0)[5]。在不同的環境下，路徑損耗指數可以從2變化到6，一般室內取值為從2到4。此外在障礙物多的地方，n通常有增長的趨勢,而d0的選擇通常也和不同的傳播環境相關。

圖1中的點線是對數路徑損耗模型經驗公式的擬合數據，無點線是一組在走廊中實際測量的數據。可以看出模型能反映總體趨勢，但和真實室內環境下的情況還是有較大區別。走廊是比較簡單的場景，如果在其他更復雜的場景下，有更多的信號遮擋、反射等因素存在，RSSI不僅和距離位置有關，還和周圍的各種障礙物有關系。

圖1 信號強度模型擬合和實際測量對比

1.2 Wi-Fi信號的強度波動特征

基于Wi-Fi信號的室內定位算法直接依靠AP的信號強度特征進行定位，因此AP信號強度的穩定性對于定位精度及可信度是至關重要的。本節將從穩定狀態、信道切換狀態和移動狀態對Wi-Fi信號強度的波動特性進行探究。

1.2.1 穩定狀態

穩定狀態指的是手機設備處于靜止狀態，并且連接Wi-Fi網絡，網絡信道未發生變化的狀態。穩定狀態下分析Wi-Fi信號強度的波動特性能夠反映出Wi-Fi信號在正常條件下的穩定性。

在測試環境中，將手機放置在某一位置不動，連接上測試環境Wi-Fi，并開啟手機Wi-Fi傳感器數據記錄功能，將手機靜止放置30分鐘。同時在AP端設置固定的信道，防止出現AP自動掃描信道，進行信道切換的情況。記錄完成后，將數據匯總，繪制成如圖2所示的折線圖。

圖2 穩定狀態下信號波動分布圖

從圖2我們不難發現，即使手機處于穩定狀態，AP也沒有發生信道變化，移動設備采集到的AP信號強度仍然具有一定的波動性，但是波動幅度不大，幅度基本在5 dB的范圍之內，這是由信號傳播的過程中可能發生的多徑效應以及反射、繞射等原因造成的。

1.2.2 信號切換狀態

目前市面上的大部分AP都具是雙頻的，分別提供2.4 GHz和5 GHz雙頻段的通信模式，而且每個頻段下根據頻率的不同劃分了不同的信道。為了減少信道的通信壓力，充分利用帶寬特點，大部分AP在出廠時會被默認設置成自動選擇信道，即AP會在不同的信道上定時發送探測報文探測信道的使用率，如果當前工作信道使用率較高經常發生擁塞時，自動選擇一個較為空閑的信道繼續完成傳輸數據的工作。

信道的切換有兩種情況，一種是同一頻段下不同信道的切換(例如5 GHz頻段內某信道的切換)，另一種是不同頻段下信道的切換(例如5 GHz頻段內某信道切換到2.5 GHz的某信道)。根據Path-Loss損耗模型公式得知，頻率對于信號強度有一定影響。圖3、圖4也反映了信道切換時信號強度會發生一定改變。

圖3 2.4 GHz頻段下信道1切換到信道9信號強度變化圖

圖4 5 GHz頻段下下信道44切換到2.4 GHz頻段 下信道6信號強度變化圖

實驗表明，信道切換會造成同一位置的同一設備信號強度不同，有一定的波動性。同一頻段下信號強度變化波動較小，大約在10 dBm左右；不同頻段下造成的信號強度變化波動較大，大于20 dBm。而且兩種信道切換發生時都有比較大的瞬時波動。

故信道切換對于室內定位精度具有非常大的影響。對于Wi-Fi信號的頻率高度復合，應做好相應的信道頻率規劃。2.4 GHz的波段內選用1、6、11信道作為固定信道，關閉AP的自動信道選擇功能，防止頻繁的更改信道。

1.2.3 移動狀態

用戶在室內的移動狀態分為慢速行走、常速行走和快速行走。手持手機，分別以三種不同速度進行測試。圖5為三種速度下信號強度隨移動位置的變化情況，圖6為該段測試數據的采集起始點、經過路徑以及AP的實際位置。

圖5 不同速度下信號強度變化情況

圖6 數據采集路線及AP位置圖

圖5表示了分別以慢速、常速和快速三種速度行走所感知到的某一具體AP的信號強度變化情況，圖6表示行走的起止點、移動方向和AP的具體位置。從數據上看，由于用戶是先靠近AP所在位置，然后再遠離AP所在位置，三種速度在整體趨勢是一致的，但是隨著速度的增加，折線圖的斜率越大，即表明波動越大。從微觀上分析，由于人行走的速度在0～2 m/s的范圍內，室內定位的計算速度在1 s內至少能夠完成一次定位，所以行走狀態可以在微觀上認為是靜止的。

1.3 Wi-Fi信號的無線廣播特征

Wi-Fi信號的廣播特性指的是，Wi-Fi信號發射端廣播發射beacon信號讓無線信號接收端(如手機)的無線接收模塊搜索到該發射端的無線信號，以便于連接該無線網上網，如果關閉了那么就無法搜索到該無線信。故Wi-Fi信號發射端需要高頻率的、定期的發射beacon信號。在實際應用中，由于AP之間主動廣播和接收beacon幀和物理環境不可控等因素，定位服務器會接收到很大一部分信號強度數據為無效的報文數據，即系統內部自身AP之間的信號強度數據和系統外部AP的信號強度數據，據統計該類數據量約占數據總量的70%以上，極大浪費了物理存儲資源和實時計算資源，導致定位引擎計算壓力大、定位響應不及時的問題。

2 手機Wi-Fi數據預處理

2.1 無效AP的動態監測與過濾

位置指紋定位方法的定位流程是定位服務器接收AP或者移動設備發送來的定位原始數據和定位請求，由定位引擎通過一定的搜索匹配算法匹配位置指紋信息，結合室內地圖資源，將定位結果返回給定位請求者。

但是在實際應用中，由于AP之間主動廣播和接收beacon幀和物理環境不可控等因素，定位服務器會接收到很大一部分信號強度數據為無效的報文數據，即系統內部自身AP之間的信號強度數據和系統外部AP的信號強度數據。該類數據量約占數據總量的70%以上，極大浪費了物理存儲資源和實時計算資源，導致定位引擎計算壓力大、定位響應不及時等問題。

因此需要克服目前WIFI室內定位無效報文多、存儲的無效數據多、定位引擎計算壓力大、定位請求響應不及時等問題，需要在預處理、定位引擎定位計算之前設計一種方法進行無效AP的動態檢測與過濾。這種方法能夠有效動態檢測出無效AP，在定位服務器的網關部分及時將無效數據過濾掉，避免定位引擎進行無效計算，提高移動設備定位請求的響應及時性。無效AP的動態監測與過濾部署位置如圖7所示。

圖7 無效AP的動態監測與過濾部署位置示意圖

2.2 數據篩選

手機能夠探測到的最小AP信號強度為-100 dBm。當信號強度小于-95 dBm，根據路徑損耗模型以及實驗測試得知，距離至少在30米之外。因此，即使是穩定的信號數據，對于提高定位精度的影響已經十分微小，不能滿足定位的需求，所以在數據篩選時，應當將低于-95 dBm的數據刪除。

2.3 數據修正

數據修正主要以濾波為主。常用的濾波方法有卡爾曼濾波法、Alpha-Beta濾波法、滑動平均濾波法等。

從定量角度進行分析，用同一段數據對卡爾曼濾波法、Alpha-Beta濾波法和滑動平均濾波法進行比較和評價如圖8所示。

圖8 采樣數據與三種濾波方法的比較

卡爾曼濾波法對信號有很好的平滑效果，但在信號波動較大的采樣時刻，濾波效果較差，不能對大范圍波動進行有效抑制。Alpha-Beta濾波法可以反映信號的時間變化，但平滑效果較差，不推薦使用。滑動平均濾波器在平滑性和實時性方面優于前兩種濾波方法。

3 基于區域網格劃分的SVM定位算法

3.1 區域網格劃分

當待測區域較大，定位區域包含大量采樣點時，采用全局SVM定位算法依次遍歷每個采樣點，然后進行匹配判斷，大大增加了定位所需的時間。此外，將所有采樣點模型加載進內存會增加所使用的內存量。在定位相應的時間及時性和內存空間使用量上不能滿足類似于交通樞紐這樣的大面積、多樓層場景下的定位需要。

解決上述問題的一個方法是對室內整體進行區域網格劃分，見圖9。將待測區域的大面積劃分為多個較小的子區域。在定位過程中，首先確定移動設備所在的子區域及相鄰的幾個區域，然后在該區域內進行精確的SVM定位。

圖9 區域網格劃分圖

劃分好區域后，從“位置指紋”數據庫中參考點屬于該區域的數據中取出每個參考點“位置指紋”向量中信號強度RSSI最大一項的AP的MAC地址，作為該點的代表，然后與該區域內所有代表點的AP的MAC的并集作為該區域的特征集合。

3.2 支持向量機

支持向量機SVM方法建立在統計學習VC維(VC dimension)理論和結構風險最小(structural risk minimization)原理基礎上，根據有限的樣本信息在分類能力(對任意樣本進行無錯誤分類)和模型的復雜性(對特定樣本的學習精度，Accuracy)之間尋求折衷，以期使分類器獲得最好的推廣能力(Generalization Ability)。它是一種非參數化的有監督分類器[6]。

假設當前存在一個線性樣本集(xi,yi)，i=1，2,…，n，x∈R2其中y是類別標號且y∈{-1,1}，d維空間中的線性判別函數為：

g(x)=ω·x+b

(1)

若線性分類線能夠將兩類樣本準確分開，則應當滿足如下條件：

(2)

αi[yi(ω·xi+b)-1]=0

(3)

最后可得到最優分類函數為：

(4)

非線性SVM分類器使用適當的核函數K(xi,xj)實現不同維度間的映射，在不增加計算復雜度的前提下達到線性分類的作用，如圖10所示。對應的分類函數也變為：

(5)

圖10 非線性情況下的最優分類面

3.3 SVM離線訓練

SVM離線訓練步驟如下：

(1) 初始化離線采樣標準數據類型 首先需要對每條原始采樣數據標定各自的類型。對于SVM的原始數據而言，因為需要進行具體到每個位置點的定位，所以對于某個采樣位置點采集的數據，標定的類型應該是其采樣的位置點編號。

(2) 分類器構建 由于SVM是一種典型的兩類分類器，但根據需求需要將類型擴展為多個，實現多分類的功能。因此需要對SVM分類方式進行擴展。目前，構造SVM多分類器主要有兩種方式，一種是直接分類，另一種是間接分類。對于間接分類法，可能會出現“數據集偏斜”問題，即正類別數遠小于負類別數，造成分類精度降低。所以使用直接分類法實現SVM多分類。

(3) SVM參數的選取 同其他機器學習方法一樣，SVM分類器的性能也受到多種參數的影響，主要是懲罰參數C和核函數參數γ。其中C代表對誤差的容忍度，C值越高，說明對錯誤分類容忍度越低，分類器泛化能力越低；γ是核函數內的一個參數，該參數一定程度上影響了數據映射到新的特征空間后的分布。本文在這兩個參數的選取上采用二維網格劃分法，以便使分類器效果最佳，如圖11所示。

3.4 基于區域網格劃分的SVM室內定位算法

在線階段的主要工作步驟如下：

第一步數據獲取移動設備主動掃描當前環境中能夠探測到的所有AP，并解析出其MAC地址、信號強度、信道、采集時間等信息。

第二步定位請求。手機客戶端軟件請求定位服務，將第一步中收集到的數據作為參數進行定位POST請求。

第三步數據預處理。服務器網關部分經過無效AP的動態監測和過濾、數據篩選、數據修正等數據預處理工作。

第四步基于區域網格的初定位。服務器定位引擎將上報的所有數據按信號強度降序排列，選取信號強度最好的K個。然后根據這K個AP的MAC地址從區域網格中匹配所屬區域。區域有可能一個，也可能多個。一般情況下K=3，如果室內環境比較復雜則應增大K值以提高定位成功率，但是相應的會延長定位的響應時間。

第五步在區域網格內進行SVM精確定位。第四步已經將定位范圍縮小到某一個或者某幾個區域網格內，則此時只需在區域網格內進行SVM定位，確定用戶更精確的位置坐標。該過程使用SVM分類器對測試樣本數據進行類型預測，且只挑選出定位所包含的位置點對應的二分類器組。最終通過投票法確定移動終端的位置。若投票得出的位置點為多個，則選取這幾個位置點幾何上的中心點作為定位結果。

4 定位測試

4.1 測試指標

假設計算得到的定位點的坐標為(xe,ye),而其真實的位置點坐標為(xi,yi),那么定位誤差E為：

(6)

(7)

4.2 測試結果

本文使用KNN定位算法與基于區域網格劃分的SVM定位算法分別計算包含46個測試點的數據集，其定位算法精度如圖12所示。

圖12 定位算法精度折線圖

兩種定位算法的精確度綜合比較如表1所示。

表1 定位算法精確度綜合比較

基于區域劃分的SVM定位算法在46個點的整體定位誤差為3.29 m，比基于KNN的定位算法提高了37.45%，并且在絕大多數點的誤差基本小于5 m，如果再結合室內地圖匹配，基本能夠滿足室內高精度定位需求。

5 結 語

本文首先對手機Wi-Fi數據的信號特征進行了分析，具體分析了Wi-Fi信號的空間分布特征、強度波動特征、無線廣播特征。然后針對具體特征進行了預處理，包含無效AP的動態監測與過濾、數據篩選、數據修正，以得到真實有效的定位數據。最后進行基于區域網格化分的SVM室內定位算法。實驗結果證明，采用本文的定位算法能夠有效降低實驗環境隨機噪聲帶來的波動影響，在不降低定位實時性的前提下，大幅度提高了定位準確度。非常適合類似于交通樞紐、購物廣場等客流量大的室內定位場景。