基于LCS/GA-WKNN算法的指紋室內(nèi)定位聚類區(qū)域劃分及性能評(píng)估

劉 輝，沙立成，王澤眾，李 聰，樊 亮

（國(guó)網(wǎng)北京市電力公司，北京010000）

隨著智慧城市的發(fā)展，人們獲得了更優(yōu)的位置服務(wù)，促進(jìn)了與位置服務(wù)產(chǎn)業(yè)鏈快速拓展?？紤]到建筑物會(huì)對(duì)衛(wèi)星信號(hào)傳輸路徑造成遮擋，從而引起能量損耗，因此采用衛(wèi)星導(dǎo)航系統(tǒng)并不能實(shí)現(xiàn)對(duì)室內(nèi)的精確定位[1-3]?？紤]到室內(nèi)區(qū)域存在廣泛覆蓋的Wi-Fi 局域網(wǎng)，因此可以利用該方式來(lái)實(shí)現(xiàn)室內(nèi)定位的功能，從而顯著降低定位成本。大量智能終端設(shè)備也被持續(xù)開發(fā)出來(lái)，大幅提升了用戶覆蓋率，同時(shí)針對(duì)智能終端設(shè)備集成了大量的Wi-Fi 模塊。由于大部分建筑物中都設(shè)置了密集Wi-Fi 接入點(diǎn)，從而形成更多的RP 指紋特征維數(shù)，產(chǎn)生大量冗余數(shù)據(jù)，顯著增加了搜索過程的復(fù)雜性[4-7]。

由于Wi-Fi 信號(hào)會(huì)產(chǎn)生多徑效應(yīng)，從而引起RSSI 值發(fā)生波動(dòng)的現(xiàn)象，導(dǎo)致定位精度明顯降低。由于室內(nèi)環(huán)境一直發(fā)生動(dòng)態(tài)變化，從而形成了不確定的噪聲分布[8-11]。本文通過多尺度核主成分分析的過程提取得到定位區(qū)域內(nèi)RP 指紋特征，對(duì)WKNN室內(nèi)定位算法利用遺傳算法進(jìn)行優(yōu)化處理獲得目標(biāo)節(jié)點(diǎn)位置。采用上述方法能夠克服傳統(tǒng)室內(nèi)定位算法存在的限制，從而降低噪聲引起的定位偏差，實(shí)現(xiàn)定位精度的顯著提升。

1 定位架構(gòu)設(shè)計(jì)

圖1 給出了定位算法的具體架構(gòu)，包含離線指紋數(shù)據(jù)庫(kù)、指紋庫(kù)區(qū)域、最長(zhǎng)公共子序列（LCS）粗定位以及GA-WKNN 在線匹配算法[12-13]。

圖1 定位算法架構(gòu)圖Fig.1 Location algorithm architecture

（1）建立初始離線指紋數(shù)據(jù)庫(kù)。利用定位區(qū)內(nèi)的RP 測(cè)試AP 的RSSI 與MAC，并通過AKF 濾波與中值濾波方式對(duì)RSSI 數(shù)據(jù)實(shí)施預(yù)處理，達(dá)到噪聲去除的功能，同時(shí)記錄RP 位置參數(shù)。

（2）劃分離線指紋數(shù)據(jù)庫(kù)。根據(jù)RSSI 值完成指紋特征向量的排序，測(cè)試了RP 間指紋特征向量與AP 序列之間的LCS 相似度，利用聚類算法完成RP 的區(qū)域劃分。劃分得到子區(qū)域之后，各區(qū)域按照LCS 統(tǒng)一指紋特征向量維數(shù)建立分區(qū)指紋的數(shù)據(jù)庫(kù)。

（3）LCS 粗定位。采集目標(biāo)節(jié)點(diǎn)指紋，再計(jì)算此節(jié)點(diǎn)根據(jù)RSSI 值進(jìn)行排序得到的AP 序列和子區(qū)域?qū)?yīng)的LCS 相似度，選擇達(dá)到最高相似度的子區(qū)域，并跟指紋數(shù)據(jù)項(xiàng)保持統(tǒng)一維度。

（4）GA-WKNN 匹配算法。對(duì)子區(qū)域中形成的指紋特征進(jìn)行分析，選擇最佳尺度核主成分模型實(shí)現(xiàn)目標(biāo)節(jié)點(diǎn)指紋與子區(qū)域指紋庫(kù)的特征轉(zhuǎn)換，從中選擇穩(wěn)定且具備較大區(qū)分度的指紋特征子集實(shí)施定位。利用遺傳算法尋找的方式確保候選RP指紋特征線性目標(biāo)節(jié)點(diǎn)指紋特征達(dá)到最優(yōu)權(quán)值，根據(jù)該權(quán)值并利用WKNN 算法對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行預(yù)測(cè)。

2 基于遺傳算法優(yōu)化的WKNN 定位算法

2.1 遺傳算法

GA 算法根據(jù)遺傳學(xué)以及自然選擇的原理，利用適應(yīng)度函數(shù)對(duì)參數(shù)候選對(duì)象優(yōu)劣性進(jìn)行判斷，從而在確定參數(shù)空間內(nèi)以混合重組的方式建立多種參數(shù)組合方式，進(jìn)化得到高質(zhì)量后代，經(jīng)過多個(gè)周期進(jìn)化后直至滿足預(yù)定義適應(yīng)度，計(jì)算多維目標(biāo)函數(shù)最大值[14]。

2.2 GA-WKNN 算法

以GA 算法作為候選RP 搜索線性表達(dá)目標(biāo)節(jié)點(diǎn)指紋最優(yōu)權(quán)值并計(jì)算目標(biāo)節(jié)點(diǎn)的位置，以下為算法的實(shí)現(xiàn)步驟：

（1）根據(jù)式（1）計(jì)算出F 跟RP 之間的指紋相似度，選擇k 個(gè)達(dá)到最大相似度的候選RP，對(duì)RP 按照隨機(jī)初始化的方式計(jì)算權(quán)值。

（2）構(gòu)建目標(biāo)模型（2），通過GA 算法搜尋的方式使候選RP 指紋特征獲得目標(biāo)節(jié)點(diǎn)指紋最佳權(quán)值，以RSSI 表示目標(biāo)節(jié)點(diǎn)對(duì)應(yīng)的指紋特征向量，RSSIi表示第i 個(gè)候選RP 對(duì)應(yīng)的向量。

（3）根據(jù)步驟（2）獲得的權(quán)值通過式（3）計(jì)算得到目標(biāo)節(jié)點(diǎn)所在的部位。

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

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

本文在室內(nèi)環(huán)境下開展測(cè)試，完成定位算法性能的評(píng)價(jià)，圖2 給出了實(shí)驗(yàn)環(huán)境的平面布局及其區(qū)域布置結(jié)構(gòu)。

圖2 實(shí)驗(yàn)環(huán)境及參考點(diǎn)布局圖Fig.2 Experimental environment and reference point layout

此樓層發(fā)生了人員的大量流動(dòng)，同時(shí)環(huán)境呈現(xiàn)無(wú)規(guī)則動(dòng)態(tài)改變的特征。測(cè)試過程在2.4 m×38 m 尺寸的走廊內(nèi)完成，測(cè)試區(qū)面積接近90 m2。在圖3 中以黑點(diǎn)表示間距固定的參考點(diǎn)，通過這些參考點(diǎn)組成平行四邊形。為實(shí)驗(yàn)區(qū)構(gòu)建坐標(biāo)系時(shí)選擇西南角作為原點(diǎn)，沿正東作為正方向。其中，首個(gè)參考點(diǎn)坐標(biāo)（1，1.7），設(shè)定最后一個(gè)參考點(diǎn)坐標(biāo)（37，1.7）。此區(qū)域中各參考點(diǎn)約能夠檢測(cè)出的10～15 個(gè)AP，各AP 都按照2.4 GHz 頻段并以IEEE802.11n 模式運(yùn)行，每個(gè)AP 都存在唯一SSID 以及對(duì)應(yīng)的MAC 地址。

3.2 數(shù)據(jù)采集

AP 按照周期性方式進(jìn)行廣播，實(shí)現(xiàn)Wi-Fi 信息幀的發(fā)送，在信息幀中存在AP 的MAC 地址、時(shí)間戳、SSID、RSSI、通信模式等多項(xiàng)內(nèi)容。因?yàn)镽SSI存在一定的時(shí)變性，最終考慮對(duì)各參考點(diǎn)分別進(jìn)行2 min 數(shù)據(jù)采集，保存各項(xiàng)信息與RP 位置坐標(biāo)，以此作為原始指紋特征參數(shù)。

利用逐一測(cè)量的方式對(duì)圖2 定位區(qū)域部署的RP 實(shí)施采樣。本次測(cè)試的智能手機(jī)上安裝了無(wú)線信號(hào)探測(cè)軟件，由此實(shí)現(xiàn)Wi-Fi 指紋信號(hào)的采集，能夠?qū)Ω鱾€(gè)信道進(jìn)行掃描并可以訪問AP，測(cè)試的手機(jī)型號(hào)是RedmiNote7。對(duì)各參考點(diǎn)分別測(cè)試2 min的時(shí)間，同時(shí)各AP 共收集60 個(gè)初始RSSI。以自適應(yīng)卡爾曼濾波的方式計(jì)算RSSI 均值，再利用參考點(diǎn)位置坐標(biāo)建立得到離線指紋庫(kù)。以隨機(jī)方式從實(shí)驗(yàn)區(qū)域選擇20 個(gè)未知節(jié)點(diǎn)實(shí)施定位分析，分別從不同維度采用本文定位方法評(píng)價(jià)室內(nèi)環(huán)境定位特性。

3.3 聚類區(qū)域劃分分析

3.3.1 RP 間隔確定

圖3 顯示了對(duì)0.8 m～1.6 m 間距測(cè)試所得的結(jié)果?？梢钥吹?，逐漸增加RP 間距后，發(fā)生了定位誤差先降低再上升的變化趨勢(shì)，其中，RP 間距為1.2 m時(shí)，達(dá)到了最低平均定位誤差，因此本文設(shè)定RP 間距為1.2 m。

圖3 RP 間隔對(duì)定位精度的影響Fig.3 Influence of RP interval on positioning accuracy

3.3.2 子區(qū)域個(gè)數(shù)確定

利用LCS 聚類算法對(duì)離線指紋庫(kù)RP 實(shí)施區(qū)域分類，設(shè)定聚類簇?cái)?shù)k 依次為1、2、3、4 的條件再對(duì)其實(shí)施測(cè)試，圖4 給出了各測(cè)試節(jié)點(diǎn)對(duì)應(yīng)的定位誤差概率密度測(cè)試結(jié)果，可以看到，當(dāng)k 增大后，平均定位誤差發(fā)生了先降低再上升的變化規(guī)律。其中，k為3 時(shí)，形成了與Y 軸相距很近的概率密度曲線，達(dá)到了最小平均定位誤差，顯著改善了控制性能，因此將實(shí)驗(yàn)區(qū)域劃總共分成3 個(gè)子區(qū)域。

圖4 子區(qū)域劃分?jǐn)?shù)對(duì)定位精度的影響Fig.4 Influence of sub region partition number on positioning accuracy

3.4 結(jié)果分析

以隨機(jī)方式選擇20 個(gè)測(cè)試點(diǎn)，分別以LCSGAWKNN、PCA-WKNN、WKNN、PCA-GAWKNN 算法完成定位，測(cè)試得到的定位誤差見圖5。

圖5 定位誤差圖Fig.5 Positioning error diagram

從表1 中可以看到分別以最小定位誤差Emin、最大定位誤差Emax、誤差均值A(chǔ)VG、標(biāo)準(zhǔn)差A(yù)VEDEV、定位時(shí)間Time 對(duì)各算法進(jìn)行定位的情況。

表1 四種定位算法的性能比較Tab.1 Performance comparison of four localization algorithms

采用WKNN 算法得到的誤差均值為2.44 m，以PCA-WKNN 算法得到誤差均值為1.301 m，最大定位誤差由3.82 m 減小至2.17 m，經(jīng)分析發(fā)現(xiàn)采用PCA指紋特征提取模型能夠提取得到精確位置指紋特征，從而降低定位結(jié)果受到噪聲因素的影響，實(shí)現(xiàn)定位精度以及穩(wěn)定性的顯著提升。采用PCA-GAWKNN算法得到的誤差均值是1.225 m，GAWKNN 算法是以GA 算法作為候選指紋計(jì)算得到最優(yōu)權(quán)值，獲得更高定位精度，同時(shí)減小了定位誤差的標(biāo)準(zhǔn)差。采用LSC-GAWKNN 算法獲得的誤差均值是0.95 m，最大與最小定位誤差分別是2.2 m 與0.37 m，總共經(jīng)過0.76 s 完成定位過程，經(jīng)測(cè)試發(fā)現(xiàn)，以LCS 聚類方法進(jìn)行定位區(qū)域分類能夠顯著降低在線定位階段與離線指紋空間進(jìn)行匹配時(shí)的計(jì)算量，相對(duì)于PCA-GAWKNN，能夠縮短約35%的定位時(shí)間。測(cè)試階段控制相鄰兩個(gè)RP 距離為1.5 m，本文設(shè)計(jì)的算法估計(jì)誤差區(qū)間介于0.37 m～2.35 m，其中，比例為86.6%的定位誤差可以控制在1.2 m 以內(nèi)。

4 結(jié)語(yǔ)

以隨機(jī)方式從實(shí)驗(yàn)區(qū)域選擇20 個(gè)未知節(jié)點(diǎn)實(shí)施定位分析，分別從不同維度采用本文定位方法評(píng)價(jià)室內(nèi)環(huán)境定位特性。經(jīng)過參數(shù)優(yōu)化確定：RP 間距為1.2 m，子區(qū)域個(gè)數(shù)3 個(gè)是最優(yōu)的。

采用PCA 指紋特征提取模型能夠提取得到精確位置指紋特征，從而降低定位結(jié)果受到噪聲因素的影響，實(shí)現(xiàn)定位精度以及穩(wěn)定性的顯著提升。本文設(shè)計(jì)的算法估計(jì)誤差區(qū)間介于0.37 m～2.35 m，其中，比例為86.6%的定位誤差可以控制在1.2 m 以內(nèi)。