基于有序聚類和MSKPCA的室內(nèi)定位算法

馬躍欣，馮秀芳

(1.太原理工大學 信息與計算機學院，山西 晉中 030600；2.太原理工大學 軟件學院，山西 晉中 030600)

0 引 言

隨著無線通信技術(shù)的發(fā)展和數(shù)據(jù)處理能力的提高，室內(nèi)環(huán)境下移動位置服務(wù)成為最具發(fā)展?jié)摿Φ幕ヂ?lián)網(wǎng)增值業(yè)務(wù)之一，廣泛地應用在環(huán)境監(jiān)測、智慧城市及商業(yè)推薦等諸多領(lǐng)域[1-6]。為減少噪聲對算法性能的影響，Lin等[7]將指紋向量歸一化后分為3類信號特征，降低了計算復雜度；Salamah等[8]提出基于動態(tài)特征子集選擇的主成分分析(principal component analysis，PCA)方法生成不相關(guān)空間，降低數(shù)據(jù)特征復雜性。為減小候選指紋搜索空間，有效提高定位算法性能，呂娜等[9]以接入點(access point，AP)為離散點生成泰森多邊形對參考點指紋聚類，具有較好的普適性；張萌等[10]基于密度峰值聚類選取數(shù)據(jù)樣本訓練隨機森林定位模型，預測誤差小且性能穩(wěn)定。

上述研究已取得了一定成果，但仍存在以下問題：提取的指紋特征不是最具辨識度且抗干擾性較弱；依據(jù)固定AP評估位置指紋相似性劃分區(qū)域，未充分利用現(xiàn)有AP且指紋聚類存在奇點，靈活性有待提升[11]。為解決上述問題，本文通過分析參考點(reference point，RP)可檢測AP序列的最長公共子序列衡量相似度，采用有序聚類將位置相鄰且指紋特征相似的RP劃分為一個子區(qū)域，通過粗定位降低計算復雜度。每個子區(qū)域內(nèi)根據(jù)指紋特征分布特性選取最優(yōu)尺度的核主成分分析(kernel principal component analysis，KPCA)模型提取指紋特征，提高定位精度。

1 指紋室內(nèi)定位模型及相關(guān)概念

1.1 指紋室內(nèi)定位算法

指紋室內(nèi)定位算法可分為離線階段和在線階段兩個階段。離線階段以RP的位置坐標及該點檢測到所有AP的RSSI值作為一個位置指紋向量，構(gòu)建離線指紋數(shù)據(jù)庫。在線階段通過K近鄰[12]、隨機森林[13]、深度學習[14]等機器學習算法將未知節(jié)點采集的位置指紋與離線數(shù)據(jù)庫進行模式匹配，從而預測目標節(jié)點位置。

1.1.1 離線階段

假設(shè)定位區(qū)域中部署了m個AP，布置n個參考點，構(gòu)建的指紋庫見表1，參考點位置坐標集合為L={l1,l2,…,ln}， 其中l(wèi)n=(xn,yn)， 每個參考點分別對應一個位置指紋F={F1,F2,…,Fn}， 其中Fi={Fi1,Fi2,…,Fim}，F(xiàn)im=RSSIi,m， 表示第i個參考點檢測到的第m個AP的RSSI值，RSSI值是信號沿多條路徑傳播的平均信號強度指示，獲取簡單，計算量小，降低了定位系統(tǒng)的成本和復雜性。

表1 離線指紋數(shù)據(jù)庫

由于室內(nèi)環(huán)境中的多徑效應和動態(tài)變化，指紋數(shù)據(jù)存在隨機噪音或顯著噪音。本文采用自適應卡爾曼濾波(adaptive Kalman filter，AKF)處理原始指紋數(shù)據(jù)，降低噪聲干擾。

1.1.2 在線階段

在線階段根據(jù)室內(nèi)不同位置處不同AP的信號強度差異性進行定位。首先獲取目標節(jié)點的指紋信息T={T1,T2,…,Tm}， 匹配數(shù)據(jù)庫中的所有記錄尋找相似指紋。指紋相似度采用距離或相關(guān)系數(shù)度量。選取k個指紋相似度較大的參考點采用加權(quán)K近鄰算法指紋(weighted k-nearest neighbour，WKNN)估計位置如式(1)所示

(1)

wi表示第i個參考點的權(quán)值，通過式(2)計算，其中disi表示第i個RP與目標節(jié)點指紋向量間的歐式距離

(2)

1.2 樸素貝葉斯加權(quán)K近鄰定位算法

樸素貝葉斯算法使用概率統(tǒng)計原理將離線階段構(gòu)建的指紋數(shù)據(jù)庫作為先驗知識與在線階段收集的新數(shù)據(jù)相結(jié)合預測未知節(jié)點位于定位區(qū)域中各參考點位置的概率進而估計目標節(jié)點最終位置，比確定性方法得到的結(jié)果更準確。將每個位置指紋看作一個隨機變量。根據(jù)貝葉斯定理即可求得在已知目標節(jié)點位置指紋的前提下落在區(qū)域內(nèi)每個參考點的后驗概率P(Li|F) 如式(3)所示

(3)

式中：n為定位區(qū)域參考點總數(shù)，P(F|Li) 為在給定已知位置Li的條件下觀測到位置指紋F的概率，F(xiàn)含有m個特征向量，P(F|Li)=P(F1,F2,…,Fm|Li)， 即在該位置中出現(xiàn)與當前指紋向量F完全相同的概率，假設(shè)Fi之間相互獨立，P(F1,F2,…,Fm|Li)=P(F1|Li)*P(F2|Li)*…*P(Fm|Li)，P(Fm|Li) 為在位置Li處第m個AP的RSSI值為Fm的概率。P(Li) 服從均勻分布，參考點Li處某一AP的RSSI值Fm近似服從高斯分布，其概率密度函數(shù)為式(4)，μ和σ為RSSI值的均值和標準差

(4)

將該區(qū)域內(nèi)所有參考點的概率降序排序，選出前k個采用1.1.2節(jié)中介紹的加權(quán)K近鄰算法確定目標節(jié)點位置。

1.3 基于核主成分分析的特征提取

核主成分分析是一種非線性降維分析方法，將高維非線性特征空間內(nèi)積的計算轉(zhuǎn)化為原空間核函數(shù)的計算，大大降低了計算量。為增強非線性處理能力，通過選取的核函數(shù)將原始指紋特征向量非線性映射到恰當?shù)牡途S空間，訓練指紋數(shù)據(jù)的協(xié)方差矩陣，可提取信息量較大的關(guān)鍵特征子集，降低指紋特征維數(shù)并增加區(qū)分度，減少動態(tài)環(huán)境中噪聲對定位結(jié)果的影響，降低AP之間的多重相關(guān)性。KPCA算法描述如下：

輸入：n個RP的指紋數(shù)據(jù)集F=[F1,F2,…,Fn]，F(xiàn)∈Rm×n， 低維空間維數(shù)μ。

(1)將此訓練樣本映射到高維特征空間Z=[φ(F1),φ(F2),…,φ(Fn)]，F(xiàn)i∈Rm，m為該子區(qū)域的公共AP數(shù)，n為參考節(jié)點數(shù)， φ(Fi) 隱式非線性函數(shù)。

(2)計算訓練樣本映射后的特征空間協(xié)方差矩陣CZ，如式(5)所示

(5)

(3)對協(xié)方差矩陣CZ做特征值分解，特征為λ，特征向量為v，即式(6)，左右兩邊分別乘φ(Fj)， 得式(7)

λv=CZv

(6)

λ(φ(Fj)v)=φ(Fj)CZv

(7)

(4)協(xié)方差矩陣CZ的特征向量v可由φ(Fi) 線性表示如式(8)所示，ωi為系數(shù)

(8)

(5)將內(nèi)積運算轉(zhuǎn)換為核函數(shù)運算K=φ(Fj)φ(Fi) 得式(9)，K是計算高維特征空間中向量內(nèi)積的核函數(shù)，ωik表示第i個系數(shù)的第k個特征值

(9)

輸出：μ個較大特征值對應的特征矩陣即投影后的低維特征空間。

2 LCS-MSKPCA指紋室內(nèi)定位算法

本文結(jié)合最長公共子序列(longest common subsequence，LCS)有序聚類和多尺度核主成分分析方法，整體的定位算法框架如圖1所示。離線階段采集室內(nèi)各RP可檢測AP的RSSI值，使用AKF過濾原始Wi-Fi指紋數(shù)據(jù)，連同RP位置坐標構(gòu)建離線位置指紋數(shù)據(jù)庫。通過計算RP指紋向量間的LCS相似度，使用有序聚類算法將指紋庫劃分為若干子區(qū)域。聚類過程中，各子區(qū)域內(nèi)所有RP連通。聚類后的各子區(qū)域內(nèi)參考點物理位置相鄰，可有效剔除位置奇點，保證指紋特征向量相似的參考點的物理位置也相鄰。在線階段計算AKF預處理后的目標節(jié)點指紋與各子區(qū)域聚類中心的LCS相似度進行粗定位，確定節(jié)點所在子區(qū)域，降低在線階段搜索復雜度。分析子區(qū)域指紋特征分布，選取最優(yōu)尺度KPCA模型對子區(qū)域指紋庫及目標節(jié)點指紋進行特征變換，提取穩(wěn)定且區(qū)分度大的指紋特征子集，通過樸素貝葉斯WKNN算法預測目標節(jié)點位置。

圖1 定位算法框架

2.1 LCS有序聚類子區(qū)域劃分

2.1.1 基于LCS的指紋相似系數(shù)

序列Z=[z1,z2,…,zn] 為序列X=[x1,x2,…,xn] 的子序列，當且僅當X存在嚴格遞增下標序列 [i1,i2,…,ik]， 對于所有的j=1,2,…,k， 都有xij=Zj。 在子區(qū)域劃分過程中，將指紋按RSSI值的大小降序排列，相鄰指紋間AP的服務(wù)集標識符(service set identifier，SSID)序列的最長公共子序列可用來衡量參考點的相似度。為便于計算，可將各AP的SSID映射為單字符。指紋Fi和Fj間的相似系數(shù)Sij定義如式(10)所示

(10)

(11)

(12)

式(10)中P、R分別由式(11)、式(12)計算，LCS(Fi,Fj) 為指紋Fi和Fj中AP序列最長公共子序列的長度，m為指紋Fi的維數(shù)，n為指紋Fj的維數(shù)。

2.1.2 有序聚類子區(qū)域劃分

將定位區(qū)域進行合理劃分，可以快速建立目標節(jié)點測定的接收信息強度與離線指紋數(shù)據(jù)庫的匹配，無需對整個指紋數(shù)據(jù)庫進行逐項匹配，有效地降低指紋數(shù)據(jù)庫搜索復雜度，提高定位性能。接入點的部署是為了覆蓋信號，通過無線信號傳輸進行局域網(wǎng)通信。目前室內(nèi)環(huán)境的AP覆蓋率呈爆發(fā)式增長，密集的AP為室內(nèi)定位帶來了新的挑戰(zhàn)：每個參考點能掃描到的AP數(shù)量較多且每個位置都不盡相同；隨著可利用AP的數(shù)量增加，位置指紋特征維數(shù)增加，定位精度相應提升，但并不是線性增加，易造成數(shù)據(jù)冗余，并影響計算速度；此外，密集的AP很有可能導致物理位置相近的各AP的RSSI信息相關(guān)性較大，導致聚類過程中出現(xiàn)一些物理距離較遠的參考節(jié)點可能與目標節(jié)點的位置指紋具有較高的相似度，選取此類參考點確定目標節(jié)點位置，易造成較大的定位誤差。

本文結(jié)合AP信號的傳播模型和所處環(huán)境，小范圍覆蓋區(qū)域內(nèi)不同時間測量的一組AP的RSSI值差異性較大但排名保持相同或相似，通過計算物理位置相鄰參考點指紋AP間相關(guān)系數(shù)，對參考點進行有序聚類劃分空間區(qū)域。傳統(tǒng)的聚類方法如K-Means、K-Medoids等劃分子區(qū)域時只考慮了指紋特征，由于環(huán)境的多樣性，同一個區(qū)域的指紋點不一定會被聚到同一個簇，因此要根據(jù)室內(nèi)幾何布局結(jié)構(gòu)對區(qū)域劃分進行約束和修正，從而對每個子區(qū)域的AP進一步分析和研究，動態(tài)選出可用的有效AP。有序聚類根據(jù)實際問題考慮樣本次序，對樣本按照物理位置進行排序且在聚類過程中樣本次序不發(fā)生變更，通過計算相鄰位置樣本間的相似度根據(jù)確定的閾值進行分裂。具體的算法步驟如下：

(1)將n個參考點的n個指紋F={F1,F2,…,Fn} 構(gòu)成一個子區(qū)域。

(2)計算相鄰參考點指紋間AP序列的最長公共子序列，構(gòu)建相似指標向量：S=(S1,2,S1,3,…,S1,n)，Sij由式(10)計算。

(3)結(jié)合定位區(qū)域的幾何形狀和指標數(shù)據(jù)分布情況確定相似度閾值α，根據(jù)此閾值進行區(qū)域劃分。F1-Fi為一個區(qū)域，F(xiàn)i-Fn為另一個區(qū)域，其中當j≥i時，S1,j≥α， 當j

(4)根據(jù)指定的子區(qū)域數(shù)目k，對其劃分的子區(qū)域返回(1)進行進一步劃分，逐步減小子區(qū)域訓練樣本的數(shù)量，劃分的子區(qū)域數(shù)目達到預設(shè)值k時，迭代過程停止。

2.2 多尺度核主成分分析特征提取模型

2.2.1 多尺度核主成分分析

KPCA方法可有效進行特征提取，但存在一定的不足，特征空間映射嚴重依賴核函數(shù)，核函數(shù)一般選取高斯徑向基函數(shù)，如式(13)所示，核函數(shù)參數(shù)σ的選取及模型構(gòu)建沒有充分考慮指紋數(shù)據(jù)的分布情況及參考點位置

(13)

單一的KPCA模型不能夠充分提取動態(tài)環(huán)境下指紋特征空間的有效特征向量。不同的子區(qū)域特征維度及數(shù)據(jù)分布各不相同。因此，我們使用多尺度核函數(shù)來解決單一核函數(shù)模型中存在的問題。通過子空間變化的統(tǒng)計量衡量核函數(shù)的尺度，使用寬度參數(shù)不同的高斯核函數(shù)提取特征，如式(14)所示，i為子區(qū)域的編號，wi為寬度參數(shù)，wi=cnσ2， c為常數(shù)，n為該子區(qū)域特征維度

(14)

2.2.2 多尺度核主成分分析特征提取模型

當建筑物室內(nèi)陳列擁擠、人員流動大且移動復雜混亂無規(guī)則時，同一位置不同時間的RSSI值存在一定的波動。溫度、濕度、人體遮擋、門和窗戶的打開和關(guān)閉等因素會產(chǎn)生不同的噪音進而干擾RSSI值?？臻g的多徑效應使得Wi-Fi信號反射、衍射和能量吸收而無規(guī)則衰減，信號通過不同的路徑產(chǎn)生不同的組成成分。人類的活動阻礙了發(fā)射器和接收器之間的無線電信號通路，視距和非視距都會有影響。因此RSSI值是時變和不可靠的，利用波動的RSSI值來估計目標位置，會造成系統(tǒng)的較大誤差和較差的定位決策。

核主成分分析選取的是方差最大的特征向量，為提取鑒別性大的指紋特征，降低相鄰節(jié)點間的相關(guān)性，本文綜合考慮核函數(shù)尺度及主成分的數(shù)量構(gòu)建多尺度核主成分分析特征提取模型，去除冗余數(shù)據(jù)，降低噪聲干擾，使所選的主成分信息熵最大化，具體的指紋特征提取算法描述如下：

(1)根據(jù)式(10)計算的LCS相似度對目標節(jié)點進行粗定位，由式(14)確定該子區(qū)域的最優(yōu)尺度核函數(shù)。

(2)使用(1)確定的核函數(shù)對粗定位的子區(qū)域參考點的指紋特征空間進行非線性變換。

(3)映射到特征空間的主成分個數(shù)μ由特征值累積方差貢獻百分比確定，計算公式如式(15)所示，η為界限閾值，是介于0到1之間的常數(shù)，反映噪聲對指紋數(shù)據(jù)的影響

(15)

(4)選取μ個較大特征值對應的特征向量作為降維后的低維空間進行位置估計。

3 實驗結(jié)果與分析

3.1 實驗環(huán)境

本文實驗環(huán)境選取真實的室內(nèi)環(huán)境，在實際辦公區(qū)域中評估算法性能，實驗環(huán)境平面圖及區(qū)域布置細節(jié)如圖2所示，該樓層包括2個會議室，3個實驗室，10個辦公室，人員流動較大，環(huán)境存在無規(guī)則的動態(tài)變化。實驗在2.4 m*38 m的走廊區(qū)域中進行，總面積約90 m2。選取25個均勻分布的參考點，如圖2中黑點所示，間距為1.5 m，參考點間構(gòu)成若干平行四邊形。實驗區(qū)域坐標系以西南角為原點，正東為正方向。第一個參考點位置坐標為(1，1.7)，最后一個參考點位置坐標為(37，1.7)。該區(qū)域內(nèi)每個參考點可檢測到的AP數(shù)量約為10個-15個，所有AP都工作在2.4 GHz頻段及IEEE 802.11n模式下，每個AP都有唯一的SSID和物理地址。使用一部安裝有無線信號測試Android應用程序的智能手機作為接收端收集Wi-Fi指紋數(shù)據(jù)，此程序可掃描所選環(huán)境的所有信道和可訪問AP，手機型號為Redmi Note 7。每個參考點測量2 min，每個AP收集60個原始RSSI值。傳統(tǒng)的原始指紋數(shù)據(jù)處理方法是使用卡爾曼濾波器和均值濾波器來減少數(shù)據(jù)的波動，過濾噪聲，但在真實場景中，噪聲服從高斯分布的假設(shè)是不符合實際情況的。因此本文采用自適應卡爾曼濾波，在預測和觀測中計算出一個最優(yōu)的估計值，有效減少多徑效應的影響。將AKF濾波后的RSSI值求均值，同參考點的物理位置坐標構(gòu)建離線指紋庫。在實驗區(qū)域隨機選取15個未知節(jié)點進行測試，從多個維度評估本文定位方法在實際室內(nèi)環(huán)境中的定位性能。

圖2 實驗環(huán)境及參考點布局

3.2 性能分析

利用LCS有序聚類對實驗區(qū)域進行子區(qū)域劃分，聚類的簇數(shù)k選擇1，2，3，4分別進行測試，15個測試節(jié)點的定位誤差概率密度函數(shù)如圖3所示，平均定位誤差隨著k的增加先減少后增加。當k取3時概率密度曲線整體與Y軸距離最近，平均定位誤差最小，性能更好，因此實驗區(qū)域劃分為3個子區(qū)域。WKNN中的k值取決于未知節(jié)點所在子區(qū)域中參考點分布情況，根據(jù)該子區(qū)域參考點的個數(shù)及指紋結(jié)構(gòu)特征動態(tài)選定參數(shù)k值。

圖3 定位誤差概率密度函數(shù)

使用本文提出的LCS-MSKPCA算法與MSKPCA-WKNN、KPCA-WKNN、WKNN算法分別對15個測試點進行定位，定位誤差曲線如圖4所示，LCS-MSKPCA算法的整體性能最優(yōu)，平均誤差為0.98 m，最大定位誤差為2.36 m。表2對4種定位算法的性能進行了比較，WKNN算法的平均誤差為2.47 m，KPCA-WKNN算法的平均誤差為1.55 m，MSKPCA-WKNN算法的平均誤差為1.13 m。WKNN算法的平均定位時間為1.06 s，KPCA-WKNN算法的平均定位時間為1.25 s，MSKPCA-WKNN算法的平均定位時間為1.17 s，LCS-MSKPCA算法的平均定位時間為0.76 s，通過比較4種算法的平均定位時間可知，LCS有序聚類劃分子區(qū)域可減少在線匹配的指紋空間和計算量，與MSKPCA-WKNN相比，LCS-MSKPCA的平均定位時間減少了35%，可有效減少定位時間。經(jīng)實驗驗證，MSKPCA通過提取穩(wěn)定的指紋特征，可有效減少噪聲對定位結(jié)果的影響，提高定位準確度和穩(wěn)定性，減小信號波動的影響，降低最大定位誤差，誤差標準差也有所下降，與KPCA-WKNN相比，MSKPCA-WKNN平均定位誤差降低了27.1%。為進一步驗證定位精度，圖5給出了定位誤差累積分布函數(shù)圖，LCS-MSKPCA在1 m以下的位置估誤差約66.7%，而MSKPCA-WKNN為40%。

圖4 誤差曲線

表2 4種定位算法的性能比較

圖5 誤差累積分布函數(shù)

實驗環(huán)境中，相鄰兩個RP之間的距離為1.5 m，本文提出的算法估計誤差范圍為0.38 m-2.36 m，86.7%的定位誤差在1.2 m以內(nèi)。因此，實驗驗證了該方法的有效性和合理性。與KPCA-WKNN方法相比，該方法具有一定的優(yōu)越性。

4 結(jié)束語

本文充分利用環(huán)境已部署AP，以各參考點可掃描AP序列的LCS相似系數(shù)衡量指紋相似性，通過有序聚類劃分子區(qū)域，分析子區(qū)域參考點指紋數(shù)據(jù)特征分布，使用最優(yōu)尺度的KPCA映射到不相關(guān)空間提取位置信息，可有效過濾噪聲并提取密集AP指紋特征向量中區(qū)分度較大的位置特征，降低計算復雜度，提高定位精度。該算法適用于AP密集且環(huán)境動態(tài)變化的場所，未來可進一步研究環(huán)境噪聲對指紋特征及定位精度的影響，提高算法魯棒性和時效性。