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

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

在室內(nèi)定位技術(shù)中，WLAN室內(nèi)定位系統(tǒng)因其完全基于現(xiàn)有的無線局域網(wǎng)設(shè)施，不需要引入其他昂貴的專用硬件設(shè)備，定位精度較高，成本低的優(yōu)點而被國內(nèi)外研究學者所關(guān)注[1-2]。

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

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

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

1 基于SALDE-UKF-SVM的室內(nèi)定位算

本文設(shè)計的室內(nèi)定位系統(tǒng)分為離線學習和在線定位兩個階段，如圖1所示。

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

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

圖1 室內(nèi)定位系統(tǒng)示意圖Fig.1 Indoor positioning system diagram

2 有監(jiān)督自適應(yīng)局部線性判別算法

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

步驟1 利用k-NN或ε-ball標準構(gòu)造近鄰域：

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

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

步驟 2 計算樣本點與其近鄰點的最小重構(gòu)權(quán)矩陣ijW ，通過極小化如下目標函數(shù)來進行計算：

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

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

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

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

條件式(4)嚴格約束線性重構(gòu)權(quán)值和為1，則得到如下約束目標函數(shù)：

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

步驟3 根據(jù)步驟2得到的重構(gòu)權(quán)值矩陣W ，構(gòu)建代價矩陣M和矩陣 X MXT：

根據(jù)最優(yōu)權(quán)值矩陣W 計算保持樣本局部幾何結(jié)構(gòu)的低維嵌入流形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與類內(nèi)散度 SW的加權(quán)差矩陣SB-μSW：

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

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

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

2.2 本文自適應(yīng)LLDE算法

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

本文采取的監(jiān)督自適應(yīng)措施是對LLDE算法中步驟一近鄰域的構(gòu)造方法進行調(diào)整，距離調(diào)整修正公式如下：

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

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

3 基于UKF的SVM定位算法

3.1 SVM多分類模型

SVM 是建立在統(tǒng)計學理論的 VC維理論和結(jié)構(gòu)風險最小原理的基礎(chǔ)上[13]。相比于以降低經(jīng)驗風險為目標的機器學習方法，SVM具有更強的泛化能力。

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

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

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

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

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

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

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

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

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

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

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

3.2 UKF優(yōu)化定位結(jié)果

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

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

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

1）初始化：

式中： Xa=[XTWTVT]為系統(tǒng)狀態(tài)增廣狀態(tài)變量。

2）參數(shù)計算：

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

3）計算Sigma采樣點，即：

4）時間更新方程：

5）量測更新方程：

4 仿真實驗與結(jié)果分析

4.1 仿真環(huán)境

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

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

圖2 室內(nèi)仿真環(huán)境示意圖Fig.2 Indoor simulation environment diagram

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

AP信道衰減模型采用標準室內(nèi)對數(shù)路徑損耗模型：

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

4.2 本文SALDE算法效果驗證

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

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

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

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

4.3 UKF-SVM定位算法仿真

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

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

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

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

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

5 結(jié) 論

對于室內(nèi)無線定位，由于復(fù)雜環(huán)境與信號高維時變特性，傳統(tǒng)方法不能很好地解決室內(nèi)定位精度的問題。為了提高定位精度，本文提出一種特征提取和改進支持向量機的定位方法，該方法能夠適應(yīng)室內(nèi)復(fù)雜環(huán)境，對干擾源不敏感，只依賴于場域分布。仿真結(jié)果表明。在數(shù)據(jù)量較少的情況下，該算法與傳統(tǒng)的匹配算法相比，定位精度得到大幅度提高，能夠?qū)⒍ㄎ徽`差控制在一定范圍內(nèi)。

（

）：

[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] 朱宇佳, 鄧中亮, 劉文龍, 等. 基于支持向量機多分類的室內(nèi)定位系統(tǒng)[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室內(nèi)定位方法[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室內(nèi)定位技術(shù)研究[D]. 哈爾濱: 哈爾濱工業(yè)大學, 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] 李波. 基于流形學習的特征提取方法及其應(yīng)用研究[D].中國科學技術(shù)大學, 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] 嚴恭敏, 嚴衛(wèi)生, 徐德明. 簡化UKF濾波在SINS大失準角初始對準中的應(yīng)用[J]. 中國慣性技術(shù)學報, 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優(yōu)化配置的室內(nèi)行人導航方法[J]. 中國慣性技術(shù)學報, 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.