基于PCA-SMO的CSI指紋定位方法

孟俊劍，鄒進貴，趙胤植

(1.武漢大學 測繪學院，武漢 430079；2.桂林理工大學 廣西空間信息與測繪重點實驗室，廣西 桂林 541006)

0 引言

隨著移動互聯(lián)網技術及物聯(lián)網等的不斷發(fā)展，使得基于位置的服務(LBS)在人們生活中的重要性日益突出[1-4].在室外可以通過目前比較成熟的全球衛(wèi)星導航系統(tǒng)(GNSS)技術獲得亞米級的精度，然而在室內環(huán)境中，由于建筑物的遮擋現(xiàn)象比較嚴重，使得可利用的GNSS信號難以滿足室內定位的需求.在室內定位領域的眾多解決方案中，由于W i-Fi設備的普及率較高，W i-Fi信號廣泛存在于各種室內空間，使得W i-Fi信號成為一種比較理想的定位源[5-6].

傳統(tǒng)的基于W i-Fi接收信號強度指示(RSSI)的定位方法操作簡單，但由于RSSI易受多徑、時變等因素的影響[7]，基于RSSI的定位方法定位精度難以有效提升.隨著IEEE 802.11n系列無線局域網通訊協(xié)議中應用了多輸入多輸出(M IMO)和正交頻分復用(OFDM)等技術，使得收發(fā)端設備之間的信道特征即信道狀態(tài)信息(CSI)可以在物理層進行估計[8].CSI揭示了散射、衰落及功率隨距離衰減等綜合效應，是無線信號在空間傳播更為本質的描述，其為提升定位精度及改善多徑效應等問題提供了新途徑[9-10].

現(xiàn)有的基于CSI的室內定位方法大致可以分為指紋匹配、測角和測距三類[11]，其中基于指紋匹配的定位方法由于受多徑效應影響較小、易于實施等優(yōu)點而備受關注.相比于RSSI，CSI中包含更為豐富的特征信息，可以構建更高維的指紋庫[12-14]，但同時也導致構建的指紋庫存儲量大、構建定位模型所需的計算和時間開銷大及實時定位計算量大等問題[15].對此本文提出首先使用主成分分析(PCA)的方法對原始指紋信息進行降維得到主要特征，而后利用序列最小最優(yōu)化(SMO)算法構建指紋點主要特征與其位置的回歸模型并用于位置預測.

1 CSI指紋定位方法

基于指紋的定位方法通常分為離線階段和在線階段.在離線階段，首先將定位區(qū)域劃分為若干格網，而后分別在各個格網處利用終端采集來自各個接入點的無線信號，然后提取無線信號的特征構建指紋庫；在線階段利用同樣的方式得到待定點的指紋特征，將其與指紋庫中記錄逐條比對來確定待定點的位置.

1.1 CSI的獲取

CSI反映了無線通信鏈路的信道屬性，相比于MAC層的RSSI，物理層的CSI是一種更細粒度的信息.對于OFDM系統(tǒng)的窄帶平坦衰落信道，其信道模型可以表示為

式中：Y和X分別表示接收向量及發(fā)送向量；H為信道矩陣；N為高斯白噪聲.信道矩陣H可通過下式進行估計：

式中：p和q分別為發(fā)射和接收天線的個數(shù)；Hpq表示第p根發(fā)射天線和第q根接收天線組成的通信鏈路對應的信道矩陣，并且有

式中：n為OFDM系統(tǒng)中子載波個數(shù)；Hpq,i為鏈路Hpq第i個子載波對應的CSI信息，其可以表示為

1.2 CSI指紋數(shù)據(jù)預處理

使用CSI采集工具得到的原始CSI信息為形如a+bi型的復數(shù)值，幅值 |H|和相位 ∠H可按下式計算：

在數(shù)據(jù)采集過程中，由于硬件設備的不穩(wěn)定及人員走動等因素的影響使得采集的信號中難免會有一些異常值，因此有必要對其進行過濾和剔除.本文采用拉依達準則（3σ準則）剔除CSI幅值和相位數(shù)據(jù)中的異常值，而后通過均值濾波的方法得到該點的指紋特征.

1.2.1 CSI幅值預處理

按式(7)可計算出CSI的幅值，圖1給出了在同一位置采集的200個數(shù)據(jù)包的對應原始幅值，可以發(fā)現(xiàn)同一子載波的振幅大都集中在某一范圍內，但也存在少許偏差較大的異常值，圖2給出了利用3σ準則對異常值剔除之后的幅值，可以發(fā)現(xiàn)原始幅值中的異常值可被有效的剔除.

圖1 同一位置200個數(shù)據(jù)包的原始幅值

圖2 剔除異常值之后的幅值

1.2.2 CSI相位預處理

與CSI幅值不同，利用式(8)計算得到的相位值不能直接利用，這是由于硬件設備的限制，使得發(fā)射端和接收端的同步誤差不能完全消除，使得接收端接收到的CSI中包含由時鐘同步誤差引起的采樣頻率偏移以及由不同載頻誤差引起的載波頻率偏移.這也使得CSI相位信息在室內定位中的應用受到限制，目前常用的一種做法是采用線性變換的方法對原始相位進行校正[16-17]，但由于測量得到的原始相位是纏繞相位，如圖3所示需要先對其進行解纏，然后對解纏后的相位進行校正.圖3是在同一位置處采集的200個數(shù)據(jù)包對應的原始相位，解纏后的相位如圖4所示.

圖3 同一位置200個數(shù)據(jù)包的原始相位

圖4 解纏后相位

線性變換的方法如下：設第i個子載波解纏后的相位為，則有

式中：φ為第i個子載波的真實相位；mi為第i個子載波的編號；N為快速傅里葉變換的大小，在802.11 a/g/n協(xié)議中N為64；?t為由采樣頻率偏移導致的時間偏差；β為由載波頻率偏移引起的相位偏移；Z為測量噪聲.由于?t和β均為未知量，故難以直接計算真實相位，但可以通過的線性變換消除這兩個未知量，這里引入兩個中間量k、l，其中：

圖5給出了經線性變換后的相位，圖6給出了使用3σ準則剔除異常值后的相位.

圖5 線性變換后相位

圖6 剔除異常值后相位

2 PCA-SMO定位算法

本文使用的算法首先在離線階段提取出指紋點CSI的幅值和相位特征構建原始指紋庫 (Fi,Li)，i=1,2,···,n，其中，F(xiàn)i=(fi1,fi2,···,fit)為原始指紋特征，t為原始指紋特征維數(shù)，Li=(xi,yi)為對應指紋點的坐標，n為指紋點的個數(shù)；而后對原始指紋庫進行PCA降維提取出主要特征，得到降維后的指紋庫其中，m為降維后的特征維數(shù)；然后利用SMO算法建立指紋點的主要特征與其位置的支持向量回歸(SVR)模型：并利用此關系模型對測試點的位置進行預測.

2.1 PCA變換

PCA作為一種重要的數(shù)據(jù)降維方法，已被廣泛應用于數(shù)據(jù)分析、圖像處理及機器學習等領域，用以減少數(shù)據(jù)冗余及數(shù)據(jù)去相關等[18].其核心思想是將原始數(shù)據(jù)通過線性變換投影到一個新的數(shù)據(jù)空間（即主成分空間），通過選取對原始數(shù)據(jù)方差貢獻最大的若干維主成分來實現(xiàn)數(shù)據(jù)的降維.本文利用PCA對原始CSI指紋特征進行降維基于這樣一種假設：由一對收發(fā)天線組成的通信鏈路上的各子載波信號從發(fā)射端到接收端的傳播路徑是趨于一致的，即受到多徑等因素的影響相當，故這組子載波的信號特征存在一定的相關性，可以通過降維減少數(shù)據(jù)冗余.原始數(shù)據(jù)與保留的主成分之間的轉換可以通過一個投影矩陣來實現(xiàn)，表1給出了PCA變換的偽代碼.

表1 PCA變換偽代碼

2.2 SMO算法

SMO算法是由Platt在1998年提出的用于訓練支持向量機(SVM)的一種快速算法[18].本文旨在利用SMO算法建立降維后的指紋點特征與對應位置坐標的SVR模型

進一步可得SVR的解的表達式：

式中，σ為高斯核函數(shù)的帶寬.

SVM的分類及回歸問題均可化為求解凸二次規(guī)劃的問題，此類問題具有整體最優(yōu)解，但在訓練樣本數(shù)量較大時，計算開銷正比于樣本量且實現(xiàn)較復雜，SMO算法的出現(xiàn)很好地解決了這一問題.SMO算法是一種啟發(fā)式算法，其基本思路是每次循環(huán)選出兩個需要更新的變量 αi,αj，并固定其余參數(shù)，利用解析的方法對式(16)快速求解并更新 αi,αj，循環(huán)將原問題分解為子問題并對子問題進行求解，最終達到求解原問題的目的.本文采用開源的機器學習及數(shù)據(jù)挖掘軟件Weka中提供的SMO回歸算法包構建回歸模型，選用的高斯核參數(shù)σ=0.015，本文算法的整體框架圖如圖7所示.

3 實驗與分析

3.1 實驗環(huán)境

實驗地點在武漢大學測繪學院114實驗室(7.0m×6.5m)，實驗室擺有桌椅等雜物.實驗選取大小為4.8m×4.8m的方形區(qū)域，布設41個指紋點，如圖8實心點所示，圖中格網邊長為0.6m，另外隨機選取30個測試點用于算法的精度評估.實驗使用一臺不設密碼型號為TL-WDR5620的雙發(fā)雙收四天線路由器，接收終端為一臺裝有Intel 5300無線網卡（三個接收天線）的筆記本，CSI采集工具為安裝在Ubuntu 14.04操作系統(tǒng)上的linux-80211n-csitool開源工具包[19].數(shù)據(jù)采集過程中路由器放于地面，采集者首先操作筆記本連接路由器，然后依次站在設定的位置利用ping命令進行數(shù)據(jù)包的采集.同時為模擬真實環(huán)境，實驗過程中保持實驗區(qū)域有人員走動，每個指紋點和測試點均采集250個數(shù)據(jù)包.數(shù)據(jù)采集完成后，利用文獻[19]中提供的linux-80211n-csitool-supplementary工具包對各個點位的原始.dat文件進行解析，得到原始的CSI信息.

圖8 實驗區(qū)域指紋點布設示意圖

3.2 實驗結果分析

根據(jù)實驗配置，離線階段構建的原始指紋特征維數(shù)為60，通過PCA變換選擇保留原始指紋95%的主成分信息，得到新指紋特征的維數(shù)為4.經過PCA變換之后的指紋庫存儲量約為原始指紋庫的1/15.顯然，在建立降維后的特征與對應坐標的回歸模型時所需的計算開銷及時間成本也將大大減少，這一點對于以手機為代表的計算資源有限的移動定位終端來說具有重要意義.

經過PCA變換，原始指紋信息不可避免的存在一定程度的損失.文章首先探究了先進行PCA變換再通過SMO算法建立降維后指紋特征與對應位置的回歸模型以及直接利用SMO算法建立原始指紋特征與對應位置的回歸模型兩種方式對定位精度的影響，圖9給出了在分別利用25、50、100、150、200及250個數(shù)據(jù)包對測試點進行定位時PCA-SMO與SMO算法的平均定位誤差.

圖9 PCA-SMO與SMO算法平均定位誤差對比

從圖中可以看出，SMO算法的定位精度整體上均優(yōu)于PCA-SMO算法，但隨著定位所利用的數(shù)據(jù)包數(shù)量逐漸增多，兩者定位誤差的差距逐漸縮小，最終穩(wěn)定在5 cm之內.總的來看，在綜合考量離線階段建模的計算及時間開銷、定位的實時性等因素時，PCA變換帶來的精度損失是可接受的，尤其是在以手機端為代表的消費級室內定位應用場景中，因此進行PCA變換是有必要的.

此外，本文還在相同實驗條件下對比了PCA-SMO算法與鄰近算法（KNN）、WKNN、FIFS[20]及CSI-M IMO[21]等算法的定位效果.圖10給出了上述幾種定位算法的定位誤差累積分布函數(shù).

圖10 定位誤差累計分布函數(shù)

由圖10可得：本文算法整體是最優(yōu)的且可靠性要高于其它幾種算法；當定位誤差小于等于1.5 m時，本文算法的累計概率為70%，而KNN、WKNN、FIFS及CSI-M IMO算法的累計概率分別為53%、35%、57%、43%；PCA-SMO算法在2m之內定位誤差的累計概率可以達到97%，其它幾種算法的累計概率依次為80%、70%、77%、87%.

最后，表2統(tǒng)計了上述幾種算法的定位誤差.其中本文PCA-SMO算法的平均定位誤差為1.25m，其它幾種定位算法的平均定位誤差分別為1.52m、1.60m、1.56m、1.57m，相比于其它幾種算法，本文算法的平均定位精度分別提升了21.6%、28.0%、24.8%、25.6%.

表2 幾種定位算法的定位誤差統(tǒng)計 m

4 結束語

W i-Fi作為室內定位領域的重要定位源之一，傳統(tǒng)的基于RSSI的指紋定位方法由于可利用的特征信息有限，導致其定位精度受到限制.而CSI中包含豐富的特征信息，可以在一定程度上改善由于指紋特征不足帶來的精度問題，但與此同時，離線階段構建的指紋庫存儲量變大、構建定位模型的計算和時間開銷以及定位的實時性等問題也應受到關注.對此，本文提出的PCA-SMO算法首先對原始指紋特征進行PCA降維，然后通過SMO算法構建降維后指紋與對應位置的回歸模型，能夠在保證定位精度的前提下，較好地克服上述問題.另外，在實時定位過程中由于人員流動等因素的影響，會使得CSI特征發(fā)生變化，尋找一種有效的異常值探測算法有待進一步研究.