基于區(qū)域網(wǎng)格劃分的SVM室內(nèi)定位算法

賈春陽 郭之超

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

0 引 言

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

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

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

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

1 手機Wi-Fi數(shù)據(jù)的信號特征

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

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

(1)

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

圖1中的點線是對數(shù)路徑損耗模型經(jīng)驗公式的擬合數(shù)據(jù)，無點線是一組在走廊中實際測量的數(shù)據(jù)?？梢钥闯瞿Ｐ湍芊从晨傮w趨勢，但和真實室內(nèi)環(huán)境下的情況還是有較大區(qū)別。走廊是比較簡單的場景，如果在其他更復(fù)雜的場景下，有更多的信號遮擋、反射等因素存在，RSSI不僅和距離位置有關(guān)，還和周圍的各種障礙物有關(guān)系。

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

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

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

1.2.1 穩(wěn)定狀態(tài)

穩(wěn)定狀態(tài)指的是手機設(shè)備處于靜止狀態(tài)，并且連接Wi-Fi網(wǎng)絡(luò)，網(wǎng)絡(luò)信道未發(fā)生變化的狀態(tài)。穩(wěn)定狀態(tài)下分析Wi-Fi信號強度的波動特性能夠反映出Wi-Fi信號在正常條件下的穩(wěn)定性。

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

圖2 穩(wěn)定狀態(tài)下信號波動分布圖

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

1.2.2 信號切換狀態(tài)

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

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

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

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

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

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

1.2.3 移動狀態(tài)

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

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

圖6 數(shù)據(jù)采集路線及AP位置圖

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

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

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

2 手機Wi-Fi數(shù)據(jù)預(yù)處理

2.1 無效AP的動態(tài)監(jiān)測與過濾

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

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

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

圖7 無效AP的動態(tài)監(jiān)測與過濾部署位置示意圖

2.2 數(shù)據(jù)篩選

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

2.3 數(shù)據(jù)修正

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

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

圖8 采樣數(shù)據(jù)與三種濾波方法的比較

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

3 基于區(qū)域網(wǎng)格劃分的SVM定位算法

3.1 區(qū)域網(wǎng)格劃分

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

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

圖9 區(qū)域網(wǎng)格劃分圖

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

3.2 支持向量機

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

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

g(x)=ω·x+b

(1)

若線性分類線能夠?qū)深悩颖緶蚀_分開，則應(yīng)當滿足如下條件：

(2)

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

(3)

最后可得到最優(yōu)分類函數(shù)為：

(4)

非線性SVM分類器使用適當?shù)暮撕瘮?shù)K(xi,xj)實現(xiàn)不同維度間的映射，在不增加計算復(fù)雜度的前提下達到線性分類的作用，如圖10所示。對應(yīng)的分類函數(shù)也變?yōu)椋?/p>

(5)

圖10 非線性情況下的最優(yōu)分類面

3.3 SVM離線訓(xùn)練

SVM離線訓(xùn)練步驟如下：

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

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

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

3.4 基于區(qū)域網(wǎng)格劃分的SVM室內(nèi)定位算法

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

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

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

第三步數(shù)據(jù)預(yù)處理。服務(wù)器網(wǎng)關(guān)部分經(jīng)過無效AP的動態(tài)監(jiān)測和過濾、數(shù)據(jù)篩選、數(shù)據(jù)修正等數(shù)據(jù)預(yù)處理工作。

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

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

4 定位測試

4.1 測試指標

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

(6)

(7)

4.2 測試結(jié)果

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

圖12 定位算法精度折線圖

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

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

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

5 結(jié) 語

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