基于SALDE-UKF-SVM算法的WLAN室內定位方法

徐曉蘇，吳曉飛，張 濤，閆琳宇

（1. 東南大學 儀器科學與工程學院，南京 210096；2. 東南大學 微慣性儀表與先進導航技術教育部重點實驗室，南京 210096）

在室內定位技術中，WLAN室內定位系統因其完全基于現有的無線局域網設施，不需要引入其他昂貴的專用硬件設備，定位精度較高，成本低的優點而被國內外研究學者所關注[1-2]。

WLAN室內定位技術根據其測量原理可分為近似檢測、幾何測量和位置指紋分析。其中，基于接收信號強度指示（RSSI）的指紋識別定位方法具有對復雜環境適應性強的優點，是目前國內外的主要研究方向。

這種算法的本質是構建RSS信號與物理位置的非線性映射關系[3]。文獻[4]和文獻[5]分別提出了利用支持向量機（SVM）和人工神經網絡（ANN）的方法對RSS信號進行識別，這些方法都忽視了RSS數據高維時變的特性，將會導致運算時間長且擬合的映射關系不適用。針對這一問題，文獻[6][7]分別提出了利用特征提取算法[8-11]對RSS數據集進行預處理，減小數據維數和時變的影響，取得了一定的效果。但這些特征提取算法均是無監督的，對RSS樣本數據集的類別標簽不能充分利用起來，導致算法效果受到一定程度的影響。

針對上述問題，本文提出了一種具有監督能力的自適應局部線性判別嵌入算法（SALDE），并結合無跡卡爾曼濾波算法（UKF）將之前的定位結果融入到位置指紋的匹配過程中，在提高定位結果精度的同時增加系統的穩定性。

1 基于SALDE-UKF-SVM的室內定位算

本文設計的室內定位系統分為離線學習和在線定位兩個階段，如圖1所示。

離線階段，依據室內布局特征進行區域分類，然后在各類中采集適量接入點（AP）的RSS信號，構成訓練樣本數據，利用SALDE算法對樣本數據進行降維，并增大類別間判別信息，最后對預處理后的數據進行SVM訓練，建立物理坐標與特征映射關系函數。

在線定位階段，采集用戶所在位置的RSS信號集，利用建立的非線性映射預測位置坐標，并通過 UKF濾波器進行濾波處理，得到最終坐標。

圖1 室內定位系統示意圖Fig.1 Indoor positioning system diagram

2 有監督自適應局部線性判別算法

2.1 局部線性判別算法（LLDE）

步驟1 利用k-NN或ε-ball標準構造近鄰域：

k-NN標準是以歐氏距離作為測度，尋找離樣本點距離最小的k個點作為其近鄰點，構造鄰域。

ε- b all標準是將任何一個落在以樣本點為球心，ε為半徑的球內的點都可以看作近鄰點。

步驟 2 計算樣本點與其近鄰點的最小重構權矩陣ijW ，通過極小化如下目標函數來進行計算：

其中：iε為樣本點iX的線性重構誤差，且ij≠；jsG是kk×維局部協方差矩陣，即

從式(2)可以看出，協方差矩陣是一個正定矩陣，若計算時出現非正定情況，可以按照下式對其進行變換使其正定：

其中：r為正則化參數，tr()G 為協方差矩陣的跡。

求式(1)的極小值，需要滿足以下兩個約束條件：

條件式(4)嚴格約束線性重構權值和為1，則得到如下約束目標函數：

式(5)是一個最小值優化問題，可采用拉格朗日乘數法求解，可得到最優權值矩陣如下：

步驟3 根據步驟2得到的重構權值矩陣W ，構建代價矩陣M和矩陣 X MXT：

根據最優權值矩陣W 計算保持樣本局部幾何結構的低維嵌入流形Y，可通過計算最小代價來獲取，表達式如下：

式(7)等價為 ε ( Y ) = m in t r[Y(I - W )T( I -W)YT]。令代價矩陣 M = ( I -W )T(I -W )，引入線性變換 Y =ATX，則式(7)可以寫成： J ( A) = mintr{ ATXMXTA}。

步驟 4 計算類間散度 SB與類內散度 SW的加權差矩陣SB-μSW：

根據最大邊緣標準(MMC)及最優權值矩陣縮放不變的特性，需要計算 SB-μSW，計算方法如下：

其中：c為類別總數； pi為第i類輸入點的先驗概率分布密度；mi為第i類的輸入點的均值；m為總均值；Si為第i類的類間散度；μ≥0為縮放因子。

步驟 5 對 { [X MXT- ( SB-μSW)],XXT}進行廣義特征值分解，求其d個最小特征值，最小特征值對應的特征向量組成的矩陣V為所求的變換矩陣，即Y=VTX。

2.2 本文自適應LLDE算法

基于監督學習的思想，提出有監督自適應局部線性判別算法(SALDE)，采用距離因子突出不同類別間的距離，實時調整樣本點鄰域圖。這在一定程度上能夠加大不同類別間的差異，從而得到更好的分類效果。

本文采取的監督自適應措施是對LLDE算法中步驟一近鄰域的構造方法進行調整，距離調整修正公式如下：

其中： dij為兩個樣本點的歐氏距離，兩樣本點屬于同一類； δ ( Xi, Xj)取0，否則取1。

此距離計算公式將兩類之間的距離引入，采用Sigmoid函數作為距離引入量的判別標準，能有效保持樣本點間距適中，不會導致類別之間交叉嚴重的現象。

3 基于UKF的SVM定位算法

3.1 SVM多分類模型

SVM 是建立在統計學理論的 VC維理論和結構風險最小原理的基礎上[13]。相比于以降低經驗風險為目標的機器學習方法，SVM具有更強的泛化能力。

設樣本數據集為(x,y ) , i = 1,2,… ,N ， x ∈Rd，

i i y∈{-1, +1}是樣本數據的所屬類別標號。在線性可分的情況下，SVM尋找一個最優的分類超平面，使幾何間隔達到最大，超平面如式(9)所示：

其中：ω表示權向量，b表示偏置向量，x表示輸入向量。為了尋找分類超平面，可以通過求解下式目標函數獲得：

式(10)是一個具有約束條件的二次函數優化問題，可以通過拉格朗日對偶法求解，化簡得下式：

其中，α為拉格朗日乘子。

將式(11)中的α固定，分別對ω和b求偏導數，令它們的偏導數為零，將結果回帶式(11)，化簡得：

由式(12)(13)可以看出，拉格朗日函數式中已經沒有ω、b兩個變量了，只需要根據式(13)求出iα的值，便可以回帶式(12)得到ω的值，b的值可以通過支持向量解得，即拉格朗日乘子iα不為零所對應的樣本。

對于非線性可分問題，需要引入一個映射()φ?，將非線性數據樣本映射到一個高維空間，使其變得線性可分。本文通過引入高斯核函數來解決室內定位的非線性分類問題。RSS信號存在噪聲干擾會導致個別支持向量偏離正確數據，因此需要通過引入松弛變量來解決這個問題。式(14)為非線性拉格朗日函數的化簡形式：

其中：C為引入松弛變量后的參數，稱為懲罰因子，它的取值直接影響學習機的擬合性能；高斯核函數σ為函數寬度。相應的非線性分類函數為

SVM本質是二值分類器，本文采用一對一法處理多分類問題。在任意兩類樣本之間設計一個 SVM 模型，則k個類別就需要設計 k (k - 1 )2個 SVM。當需要對一個樣本進行分類時，將分類器分別測試該樣本，獲得分類票數最多的類別即為該樣本類別。

本文在基于SVM進行分類縮小定位區域之后，利用支持向量機回歸（SVR）進行非線性擬合，構建映射函數。支持向量機回歸與 SVM 原理基本相同，這里直接給出SVR的回歸模型：

3.2 UKF優化定位結果

實時測量的RSS信號受到噪聲干擾，具有突變特性，會對定位結果造成影響，而行動軌跡的定位結果之間是相關的，連續的，不存在突變的。因此，本文利用UKF算法實時跟蹤定位結果，利用之前的位置預測下一時刻位置出現的置信區間，從而降低RSS信號突變帶來的影響[14-16]。

UKF是一種非線性濾波方法，適合于SVR建立的非線性模型。該方法使用確定性采樣方法對狀態量進行處理。本文選取位置坐標 X =[x,y ]T作為狀態量，由于狀態量的變化相對于運算速度是緩慢的，或者說變化過程是一個平穩過程，則UKF濾波的狀態方程與量測方程如下：

其中： Wk、 Vk為過程噪聲和量測噪聲；m為所選取之前位置點個數。則UKF計算過程如下：

1）初始化：

式中： Xa=[XTWTVT]為系統狀態增廣狀態變量。

2）參數計算：

式中：n為增廣狀態向量的維數；α為刻度因數，可取 1 0-4≤α≤1；對于高斯分布，取β=2為最優值；κ為第三刻度因數，取κ=0。

3）計算Sigma采樣點，即：

4）時間更新方程：

5）量測更新方程：

4 仿真實驗與結果分析

4.1 仿真環境

為驗證本文算法的定位效果，依據作者所在實驗室的實際環境設置，使用 MATLAB構建虛擬仿真場景。如圖2所示，仿真場景大小為16 m × 20 m的長方形區域，共分為6塊定位區域，設置8個AP。

仿真選取224個指紋點和100個測試點，其中A、B、E區域選取42個指紋點，C、D、E分別選取18、54、26個指紋點，指紋點均勻分布于定位區域，測試點隨機選取，如圖3所示。

圖2 室內仿真環境示意圖Fig.2 Indoor simulation environment diagram

圖3 參考點與測試點分布情況Fig.3 Distribution of reference points and test points

AP信道衰減模型采用標準室內對數路徑損耗模型：

式中： PL(d0)為1 m處的信號強度，通常設置為經驗值-45 dBm；路徑損耗因子 η ∈ [1 . 6,3.3]；Xσ為均值為0，標準差為 σ ∈ [ 2 ,14.1]的高斯白噪聲。

4.2 本文SALDE算法效果驗證

為驗證 SALDE算法對數據集特征提取的有效性，分別與改進前 LLDE和其他四種數據處理方法LE、LPP、NPE和SNE進行比較。為方便直觀地顯示處理效果，約減維數選取二維平面，即 d = 2 ，近鄰K = 12，六種算法數據處理效果如圖 4所示。由圖中可以很直觀地看出，SALDE、LLDE、LE、SNE的降維效果較好，有效地將采集點的RSS分類特征保留下來，LPP和NPE則出現了類別間相互交叉的現象。而SALDE相較于LLDE、LE、SNE，由于將類間距離引入，并且依據類間距離大小自行調整其引入值，SALDE類間距離能夠保持得基本一致，較為平穩，其他算法則是過于接近或者松散。

為進一步驗證算法性能，使用SVM分類器對降維結果進行分類，令N為訓練樣本總數，分別考查選取 N1= N / 3 、 N2= 2N / 3 、 N3=N 三種情況的分類效果，隨機選取250個測試樣本。從表1可以看出，在情況1~3時，SALDE分類精度優于LLDE，略好于LE算法，相比于直接使用 SVM 分類器得到的結果，分類精度分別提高了 7.2%、5.6%和 5.8%。從時間復雜度上看，SALDE也優于直接使用SVM進行分類。仿真結果證明使用 SALDE算法對數據進行預處理能夠有效提高分類精度與運行時間。

圖4 特征提取效果對比Fig.4 Comparison of feature extraction effects

表1 分類精度對比Tab.1 Classification accuracy comparison

4.3 UKF-SVM定位算法仿真

針對上述仿真環境，選取一條從定位區域D經F到達A區域的路線，每隔0.1 m選取一個測試點，共250個測試樣本。圖5為本文提出的算法與SVM回歸算法的對比仿真結果。UKF仿真參數如下：β=2，κ=0，α=0.01,X0=[10,4]T, RW= 1 ， RV= 0 .5，

圖5(a)為軌跡點散點分布圖，圖中UKF-SVM算法的散點分布相較于 SVM 回歸更加貼近軌跡線。圖5(b)為軌跡x軸坐標曲線圖，SVM回歸算法定位結果浮動較大，本文算法較為平滑，也更接近真實坐標。圖 5(c)為坐標誤差曲線圖，本文算法誤差基本保持在5 m以內，精度高，穩定性好。

圖5 兩種方法定位結果對比Fig.5 Comparison on positioning results of the two methods

圖6 為本文算法、LLDE-SVM、SVM回歸算法和神經網絡算法（ANN）的定位精度對比圖，圖中表明本文算法在定位精度上相比于其他三種方法有明顯提高。ANN算法由于在數據量較小，定位區間大的情況下，學習泛化能力差，定位精度最低。SVM算法因其泛化性好的優點，定位精度比ANN較好。LLDE-SVM 算法由于對數據進行了一定的降噪處理，精度相比于SVM提高較多，但仍達不到定位需求精度。本文算法進一步對數據特征進行挖掘，在定位誤差2 m范圍內，精度達到72.4%，相比于其他三種算法分別提高了 3.7%、18.2%、23.5%，在定位誤差4 m范圍內，精度高達95.8%，相比于其他三種算法分別提高了8.3%、17.7%、27.2%，定位精度得到明顯提升，基本滿足定位需求。

圖6 定位誤差對比圖Fig.6 Comparison of positioning errors

5 結 論

對于室內無線定位，由于復雜環境與信號高維時變特性，傳統方法不能很好地解決室內定位精度的問題。為了提高定位精度，本文提出一種特征提取和改進支持向量機的定位方法，該方法能夠適應室內復雜環境，對干擾源不敏感，只依賴于場域分布。仿真結果表明。在數據量較少的情況下，該算法與傳統的匹配算法相比，定位精度得到大幅度提高，能夠將定位誤差控制在一定范圍內。

（

）：

[1] Zou H, Luo Y W, Lu X X. A mutual information based online access point selection strategy for WIFI indoor localization[C]//Proceedings of the 2nd International Conference on Information Science and Control Engineering. 2015: 769-773.

[3] Zhang G W, Xu Z H, Liu D. Research and improvement on indoor localization based on RSSI fingerprint database and K-nearest neighbor points[C]//International Conference on Communications, Circuits and Systems. Chengdu, 2013: 68-71.

[4] 朱宇佳, 鄧中亮, 劉文龍, 等. 基于支持向量機多分類的室內定位系統[J]. 計算機科學, 2012, 39(4): 32-35.Zhu Y J, Deng Z L, Liu W L, et al. Multi-classification algorithm for indoor positioning based on support vector machine[J]. Computer Science, 2012, 39(4): 32-35.

[5] Rahman M S, Park Y, Kim K D. RSS-based indoor localization algorithm for wireless sensor network using generalized regression neural network[J]. Arabian Journal for Science and Engineering, 2012, 37(4): 1043-1053.

[6] 張勇, 黃杰, 徐科宇. 基于PCA-LSSVR算法的WLAN室內定位方法[J]. 儀器儀表學報, 2015, 36(2): 408-414.Zhang Y, Huang J, Xu K Y. Indoor positioning algorithm for WLAN based on principal component analysis and least square support vector regression[J]. Chinese Journal of Scientific Instrument, 2015, 36(2): 408-414.

[7] 鄧志安. 基于學習算法的 WLAN室內定位技術研究[D]. 哈爾濱: 哈爾濱工業大學, 2012.Deng Z A. Research on learning based WLAN indoor positioning techniques[D]. Harbin: Harbin Institute of Technology, 2012.

[8] Tenenbaum J, Silva V, Langford J. A global geometric framework for nonlinear dimensionality reduction[J].Science, 2000, 290: 2319-2323.

[9] Roweis S, Saul L. Nonlinear dimensionality reduction by locally linear embedding[J]. Science, 2000, 290: 2323-2326.

[10] Kokiopoulou E, Chen J, Saad Y. Trace optimization and eigenproblems in dimension reduction methods[R]. University of Minnesota, 2010: 1-36.

[11] 谷瑞軍. 基于流形學習的高維空間分類器研究[D]. 無錫: 江南大學, 2008.Gu R J. A study on classifiers in high-dimensional space based on manifold learning[D]. Wuxi: Jiangnan University,2008.

[12] 李波. 基于流形學習的特征提取方法及其應用研究[D].中國科學技術大學, 2008.Li B. The study of the manifold learning based feature extraction methods and their applications[D]. Anhui:University of Science and Technology of China, 2008.

[13] Xu Y, Chen X Y, Wang Y M, et al. Improved indoor pedestrian navigation method using low-cost foot-mounted AHRS and shoulder- mounted compass[J]. Journal of Chinese Inertial Technology, 2016, 24(3): 325-329.

[14] 嚴恭敏, 嚴衛生, 徐德明. 簡化UKF濾波在SINS大失準角初始對準中的應用[J]. 中國慣性技術學報, 2008,16(3): 253-264.Yan G M, Yan W S, Xu D M. Application of simplified UKF in SINS initial alignment for large misalignment angles[J]. Journal of Chinese Inertial Technology, 2008,16(3): 253-264.

[15] Gustafsson F, Hendeby G. Some relations between extended and unscented Kalman filters[J]. IEEE Transactions on Signal Processing, 2012, 60(2): 545-555.

[16] 曾慶化, 王敬賢, 孟騫, 等. 基于 UWB優化配置的室內行人導航方法[J]. 中國慣性技術學報, 2017, 25(2):186-191.Zeng Q H, Wang J X, Meng Q, et al. Indoor pedestrian navigation method based on optimal allocation of UWB[J]. Journal of Chinese Inertial Technology, 2017,25(2): 186-191.