基于IMK-WLSSVR的WiFi室內定位算法*

張 震， 關維國， 鄒 穎

(遼寧工業大學 電子與信息工程學院，遼寧 錦州121001)

0 引 言

隨著移動通信技術的快速發展，基于位置的室內定位服務越來越受到人們的關注[1]。無線保真(wireless fidelity，WiFi)信號覆蓋范圍廣且WiFi通信模塊廣泛應用在智能終端上，使得基于WiFi的定位技術備受關注。WiFi定位方法主要包括幾何測距法和指紋識別法[2]。幾何測距法利用信號傳播模型進行位置估計，但信號模型受環境影響比較大，定位精度較低。位置指紋法通過創建信號強度與位置坐標的指紋庫進行定位，定位精度更高且易于部署，成為了研究的熱門方向[3]。

位置指紋法在離線階段建立接收信號強度指示(received signal strength indication，RSSI)與位置的數據庫，對在線測量的RSSI和數據庫進行匹配，從而完成定位。文獻[4]提出基于RSSI概率分布重疊面積的指紋相似度匹配算法實現定位，但需要建立準確的RSSI概率分布模型。文獻[5]采用K-means聚類算法對指紋數據初始分類，使用隨機森林算法進行二次分類，但算法計算量比較大。文獻[6]提出了基于最小二乘支持向量機(least square support vector machine，LSSVM)的定位方法，LSSVM由于其泛化性能強，算法定位效果較好，但沒有研究模型參數優化方法。文獻[7]采用最小二乘支持向量回歸機完成三維定位，通過粒子群算法對定位模型參數進行優化，具有不錯的定位效果,但粒子群算法全局尋優能力差，模型優化效果不明顯。

本文提出一種基于改進多核加權最小二乘向量回歸(improved multiple kernel weighted least square support vector regression，IMK-WLSSVR)的WiFi室內定位算法。針對傳統基于單核WLSSVR模型的定位效果不佳，選用多項式核函數和高斯徑向基核函數通過線性加權確定多核函數，依據模型擬合誤差為每個指紋樣本分配不同的權值，建立RSSI值與位置坐標的非線性映射；采用改進的模擬退火(improved simulated annealing，ISA)算法進一步優化模型參數，通過優化的定位模型進行定位，有效提高算法的定位精度。

1 IMK-WLSSVR算法

本文提出的基于IMK-WLSSVR的定位方法主要分為離線訓練階段和在線定位階段。離線訓練階段，在定位環境中選定指紋點，然后采集各個指紋點上的RSSI值，將指紋點RSSI樣本值和對應位置作為輸入樣本對，采用多項式核函數和高斯徑向基核函數構建多核函數，利用正態分布權值函數計算每個指紋點的權值，建立IMK-WLSSVR定位模型，并采用ISA算法確定IMK-WLSSVR參數，構造RSSI值和位置坐標的非線性映射。在線定位階段，在待定位點采集RSSI值，通過構造好的IMK-WLSSVR模型估算待定位點的實際位置。

1.1 多核函數構建

核函數可以解決非線性關系，但在室內環境中，RSSI受到多徑、陰影效應的影響，單核方法往往不能很好擬合RSSI，因此，為了提高定位精度，采用多核方法建立定位模型。為了更好擬合RSSI值與位置的非線性映射，本文選用全局性核函數即三階多項式核結合局部性核函數即高斯核,通過線性加權構建多核函數[8]

K=λ1Kpoly+λ2KRBF,

s.t.λ1+λ2=1

(1)

(2)

式中y(i)為第i個坐標y的真實值，y′(i)為相應的模型估計值,則每個基核函數的權重λm為

(3)

同理可得到坐標x的多核函數。

1.2 IMK-WLSSVR建模

定位問題的關鍵就是獲取RSSI值與位置坐標之間的映射關系，可以采用人工神經網絡和最小二乘支持回歸機擬合位置和信號強度的非線性映射[9]。本文利用基于多核的WLSSVR算法構造RSSI值與位置坐標的非線性關系，有效提高模型的定位精度。

支持向量回歸[10](support vector regression ，SVR)具有良好的非線性性能，但其訓練過程涉及二次規劃問題，導致訓練時計算復雜。作為SVR的擴展，最小二乘支持向量回歸(least square support vector regression，LSSVR)算法[11]利用最小二乘方法將二次規劃問題等價為線性方程組求解, 有效提高了SVR運算速度，但算法魯棒性能欠佳。Suykens J A K等人在LSSVR算法的基礎上提出加權最小二乘支持向量回歸(weighted least square support vector regression，WLSSVR)算法[12]，從而有效提高了LSSVR算法魯棒性能。

假設Pi=(pi1,pi2,…piM) 表示指紋點(xi,yi)處接收到來自M個WiFi熱點的RSSI向量，通過一個非線性映射φ，將RSS值映射到高維特征空間F，在高維空間中構造物理位置y與RSSI向量的最優回歸關系

(4)

式中Wk∈H為權系數，λk≥0為第k個核函數的系數，b為偏置矩陣。根據結構風險化最小原則，將二次規劃問題轉化為

(5)

建立式(5)對應的拉格朗日函數

(6)

分別求取式(6)關于各變量的偏微分

(7)

式(7)消去向量Wk,β和η，可得式(8)

(8)

(9)

解式(9)可得

α=(Ω+γ-1ω)-1(Y-b·E)

(10)

由式(10)可求出最優回歸函數

(11)

坐標x求解過程與上述方法類似，根據式(1)和式(11)，可得指紋點的RSSI向量與物理位置的非線性關系

(12)

在IMK-WLSSVR定位模型中，不同的定位誤差ηi對應不同的權重ωi，選取恰當的權重可以有效降低異常指紋數據對模型定位精度的影響，本文采用基于正態分布的加權函數表達式為：

|ηi|<0.2μ或|ηi|>0.8μ

(13)

1.3 多核模型參數優化

IMK-WLSSVR算法的定位性能與支持向量回歸機參數(懲罰因子γ、核參數σ、C)的選擇有著極為緊密的聯系。文獻[13]提出了基于網格搜索的SVR優化方法，但網格方法搜索模型參數的精度較低，優化性能不理想。為了提高IMK-WLSSVR定位模型的定位性能，本文改進模擬退火算法來優化模型參數。模擬退火算法[14,15]作為一種全局搜索算法，以一定的幾率接受差解，擴大了算法搜索范圍，避免尋優過程陷于局部最優，提高了算法得到全局最優解的概率。

本文將當前溫度值加入到擾動模型中，在接近最優解時能減緩擾動幅度；同時，增加一個最優參數變量，從而保證在退火過程中始終保持最優解。基于改進模擬退火算法的IMK-WLSSVR定位模型參數優化過程如下：

1)設定待優化參數γ,δ,C范圍，溫度T1和擾動步長V0，隨機生成γ,δ,C并作為當前優解γbest,δbest,Cbest。依據式(12)得到當前參數下的IMK-WLSSVR模型，計算位置預測值與真實值的均方根誤差S。

2)在溫度Tm下，根據式(14)擾動模型計算新參數γ1，δ1，C1，計算新參數下的位置坐標均方根誤差S′,選擇其中誤差最小的參數作為γbest,δbest,Cbest，然后與上一次的誤差S比較，若S′小，則接受新參數；若S大，則計算ΔS=S′-S，并生成一個(0,1)范圍的隨機值ρ，若exp(-ΔS/Tk)大于ρ，接受新參數，否則拋棄新參數，并對上一次參數重新擾動

(14)

式中θ為(0,1)范圍內的隨機數。

3)若到達規定迭代次數，則更新溫度Tm+1=Tm·α，迭代次數清零并跳至步驟(2)，否則直接跳轉至步驟(2)。若Tk小于最低溫度，算法終止，輸出待優化參數的最優值組合(γbest,δbest,Cbest)。

2 實驗結果及分析

2.1 實驗條件

室內定位環境選取學校3號教學樓8層實驗實訓室，如圖1所示。實驗選用6個型號為TL-WR886N的WiFiAP，AP固定高度為2 m,使用華為手機采集各WiFiAP的RSSI值，手機與地面相隔1.2 m。實驗布置了60個指紋點和60個測試點，指紋點的間距是3 m,每個指紋點位置采集50個樣本，每次間隔5 s，測試點位置隨機選取，每個位置采集10次。實驗選擇60組指紋數據作為訓練樣本建立IMK-WLSSVR定位模型，利用訓練好的模型對60組測試數據進行定位測試，實驗對比了WKNN，LSSVR及MK-WLSSVR算法。

圖1 室內定位測試

2.2 實驗結果分析

為了驗證本文的IMK-WLSSVR算法的有效性，分別采用WKNN、LSSVR、MK-WLSSVR和IMK-WLSSVR4種方法進行定位對比。其中，WKNN的近鄰數為4，LSSVR算法的核函數選取徑向基函數。構建等價核函數，利用式(3)計算每個基核函數的權重λ1=0.46，λ2=0.54，由式(13)確定各個指紋點的權值，建立LSSVR模型、MK-WLSSVR模型及IMK-WLSSVR模型， 3種模型的定位誤差如圖2所示。

圖2 不同模型定位誤差對比

從圖2可知，組合核函數MK-WLSSVR的總體預測性能較好，其預測誤差小于單一核函數LSSVR模型。IMK-WLSSVR模型具備較好的抗干擾性和較高的定位精度，通過調整模型誤差的權重，進一步減小了位置估計誤差，其定位誤差小于MK-WLSSVR的定位誤差，表明IMK-WLSSVR模型精度更高、泛化能力更強。根據圖2的模型定位誤差計算得到均方根誤差，IMK-WLSSVR的均方根誤差為1.54 m，優于LSSVR的1.86 m、MK-WLSSVR的1.68 m，可見本文算法的定位誤差受影響較小，抗噪性能良好。

同時，為了驗證ISA算法對IMK-WLSSVR參數尋優的有效性，分別使用網格搜索以及改進的模擬退火算法方法優化模型參數，利用IMK-WLSSVR模型來估計測試點位置。

圖3所示的是使用ISA優化算法平均定位誤差的對比，改進模擬退火算法的誤差相比網格搜索定位誤差明顯減小，說明了ISA算法對IMK-WLSSVR模型的參數優化可以有效減少定位誤差。對于通過IMK-WLSSVR構建RSSI值和物理位置的映射關系的過程中，ISA算法有著良好的全局優化IMK-WLSSVR算法參數的能力，使得IMK-WLSSVR有著更好的學習能力和泛化能力。

圖3 網格搜索法與ISA算法的誤差對比

3 結 論

將本文算法與WKNN算法、LSSVR算法及MK-WLSSVR算法進行定位對比。實驗結果表明：LSSVR算法因其泛化性好的優點，定位精度比WKNN較好；本文算法的平均誤差為1.54 m，最大誤差為3.3 m，在定位精度上相比于其他三種方法有明顯提高，定位精度得到明顯提升，可滿足實際室內定位需求。