馬躍欣，馮秀芳

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

0 引 言

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

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

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

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

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

1.1.1 離線階段

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

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

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

1.1.2 在線階段

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

(1)

wi表示第i個(gè)參考點(diǎn)的權(quán)值，通過(guò)式(2)計(jì)算，其中disi表示第i個(gè)RP與目標(biāo)節(jié)點(diǎn)指紋向量間的歐式距離

(2)

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

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

(3)

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

(4)

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

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

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

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

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

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

(5)

(3)對(duì)協(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)積運(yùn)算轉(zhuǎn)換為核函數(shù)運(yùn)算K=φ(Fj)φ(Fi) 得式(9)，K是計(jì)算高維特征空間中向量?jī)?nèi)積的核函數(shù)，ωik表示第i個(gè)系數(shù)的第k個(gè)特征值

(9)

輸出：μ個(gè)較大特征值對(duì)應(yīng)的特征矩陣即投影后的低維特征空間。

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

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

圖1 定位算法框架

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

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

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

(10)

(11)

(12)

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

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

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

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

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

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

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

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

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

2.2.1 多尺度核主成分分析

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

(13)

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

(14)

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

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

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

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

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

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

(15)

(4)選取μ個(gè)較大特征值對(duì)應(yīng)的特征向量作為降維后的低維空間進(jìn)行位置估計(jì)。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境

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

圖2 實(shí)驗(yàn)環(huán)境及參考點(diǎn)布局

3.2 性能分析

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

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

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

圖4 誤差曲線

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

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

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

4 結(jié)束語(yǔ)

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