信號域距離對室內(nèi)WKNN 指紋定位精度的影響分析

畢京學(xué)，紀(jì)冬華，王志華，李亞宇，劉 曉，李秋琳

（1.山東建筑大學(xué)，濟(jì)南 250101；2.江蘇省基礎(chǔ)地理信息中心，南京 210013）

0 引言

加權(quán)K 近鄰（weighted K nearest neighbor， WKNN）指紋定位是基于無線保真(wireless fidelity， WiFi）室內(nèi)定位最常用的方法，其核心理念是依據(jù)測試指紋與參考指紋間的距離相似度篩選鄰近參考點以估計待定點位置。指紋定位中最常用的距離相似度是歐式距離[1-3]、曼哈頓距離[4-5]以及余弦相似度[6-7]，距離反映的是2 個指紋序列的間距長度，而余弦相似度計算的則是2 個向量夾角的余弦值，距離越小，或者余弦值越大，都表示2 個指紋序列越鄰近。

文獻(xiàn)[8] 利用加州大學(xué)歐文分校(The University of California Irvine， UCI)多建筑多樓層環(huán)境下的公共數(shù)據(jù)集對 53 種距離相似度進(jìn)行測試分析，采用索倫森（S?rensen）距離的定位精度最高；文獻(xiàn)[9]綜述了49 種距離相似度并利用公共數(shù)據(jù)集進(jìn)行定位精度評測，認(rèn)為洛倫茲（Lorentzian）、漢明（Hamming）、雅卡爾（Jaccard）距離定位性能最優(yōu)；文獻(xiàn)[10]采用斯皮爾曼（Spearman）距離實現(xiàn)較高精度定位，80%的誤差小于2.7 m；文獻(xiàn)[11]在多樓層環(huán)境中定位，利用歐式距離、曼哈頓距離和谷本（Tanimoto）距離進(jìn)行定位測試，實驗結(jié)果表明曼哈頓距離取得最好的定位效果；文獻(xiàn)[12]利用歐式距離、曼哈頓距離和馬氏距離進(jìn)行定位精度測試，結(jié)果表明在辦公室環(huán)境中，曼哈頓距離的定位精度最好，而在購物中心，馬氏距離的定位精度最好。

上述研究對比分析了不同距離相似度在不同室內(nèi)環(huán)境下的定位精度，但是沒有明確指出距離相似度的計算問題。文獻(xiàn)[13-14]為便于區(qū)分，將指紋定位中的距離分為信號域距離和空間域距離，文獻(xiàn)[15]提出1 種顧及信號感知概率的信號域距離，可以提高指紋定位精度和穩(wěn)定性。然而，上述文獻(xiàn)都沒有指出以何種指紋作為遍歷依據(jù)，沒有比較分析多種信號域距離對定位精度的影響。因此，本文依據(jù)遍歷指紋以及求和與求均值計算的差異對信號域距離進(jìn)行分類，并基于不同信號域距離在 3 200 m2的試驗場開展指紋定位測試，對比分析不同信號域距離對指紋定位精度的影響，可以為指紋定位相關(guān)研究和應(yīng)用提供參考。

1 信號域距離及其分類

1.1 信號域距離

介質(zhì)訪問控制（media access control， MAC）和對應(yīng)的接受信號強(qiáng)度（received signal strength， RSS）構(gòu)成鍵值對，多個鍵值對構(gòu)成指紋。在測試點采集的指紋稱為測試指紋，在參考點采集的指紋稱為參考指紋。為便于區(qū)分和表達(dá)，將2 列指紋所在空間點位之間的距離稱為空間域距離，即

式中：li和 lj分別為空間點位的位置，( xi， yi)為 li處的2 維坐標(biāo)。

將2 列指紋信號強(qiáng)度序列之間的距離稱為信號域距離，即

式中：Ri和 Rj分別為在位置 li和 lj處的指紋；Ri，k、Rj， k分別為在位置 li、 lj處接收到第k 個無線接入點（access points，AP）的RSS；m 為所有AP 的數(shù)目，當(dāng)p 為1 時，信號域距離為曼哈頓距離，當(dāng)p為2 時，信號域距離為歐氏距離。

本文采用歐式距離表征測試指紋和參考指紋間信號域距離，即

式中：l 為測試指紋的位置；dsig( li，l )為參考位置li處指紋與測試指紋的信號域距離；n 為2 處指紋相同AP 的個數(shù)； rk為測試指紋中對應(yīng)AP 的RSS。

測試指紋與參考指紋的關(guān)系如圖1 所示，在理想情況或測區(qū)面積比較小的區(qū)域內(nèi)，測試指紋與參考指紋中的AP 數(shù)目一致，且對應(yīng)的MAC 都相同，如圖1（a）所示，測試指紋與參考指紋中的鍵值對一一對應(yīng)，雙箭頭線段為測試指紋與參考指紋中對應(yīng)MAC 的距離；然而在實際應(yīng)用中或范圍較大的測區(qū)內(nèi)，由于存在信號丟失、新AP 和移動熱點的出現(xiàn)，測試指紋與參考指紋之間的關(guān)系通常如圖1（b）所示，測試指紋和參考指紋中都包含彼此沒有的指紋數(shù)據(jù)，AP 數(shù)目并不一致，對應(yīng)的MAC 數(shù)量相對較少。

圖1 測試指紋與參考指紋的關(guān)系

因此，為了公平比較距離相似度，文獻(xiàn)[14]引 入相同AP 數(shù)目求得1 種改進(jìn)信號域距離，本文稱之為平均信號域距離，并將式（3）計算得到的距離稱為求和信號域距離。平均信號域距離的計算公式為

2）遍歷參考/測試指紋交集的信號域距離 （ dsig-tfi）。遍歷參考指紋與測試指紋MAC 序列的交集，利用交集中同一MAC 對應(yīng)的RSS 進(jìn)行計算，如圖2（a）所示。利用式（3）和式（4）分別求得遍歷參考/測試指紋交集的求和信號域距離（ dsig-tfi-sum）和遍歷參考/測試指紋交集的平均信號域距離（ dsig-tfi-avg）。

由于指紋采集過程中監(jiān)測到的AP 個數(shù)是動態(tài)變化的，因而，根據(jù)遍歷指紋的不同，信號域距離也存在差異。遍歷指紋的依據(jù)如圖2 所示。

圖2 遍歷指紋依據(jù)

3）遍歷參考/測試指紋并集的信號域距離（ dsig-tfu）。遍歷參考指紋與測試指紋MAC 序列交集，對參考指紋和測試指紋中沒有的MAC 對應(yīng)的RSS 賦值為-100 dB·m，利用同一MAC 對應(yīng)的RSS進(jìn)行計算，如圖2（c）所示，參考指紋和測試指紋中分別插入彼此沒有的鍵值對。利用式（3）和式（4）分別求得遍歷參考/測試指紋并集的求和信號域距離（ dsig-tfu-sum）和遍歷參考/測試指紋并集的平均信號域距離（ dsig-tfu-avg）。

圖2（a）表示以測試指紋和參考指紋的交集為遍歷依據(jù)；圖2（b）表示以測試指紋為遍歷依據(jù)；圖2（c）表示以測試指紋和參考指紋的并集為遍歷依據(jù)。對測試指紋和參考指紋中缺失的RSS 均賦值為-100 dB·m。

1.2 信號域距離的分類

由于遍歷測試指紋的求和與平均信號域距離相同，因此，根據(jù)遍歷指紋依據(jù)以及求和與求平均計算將信號域距離分為5 類，如圖3 所示。

圖3 信號域距離分類

具體表述如下：

1）遍歷測試指紋的信號域距離（sig-ttfd ）。遍歷測試指紋的MAC 序列，將參考指紋中沒有的MAC對應(yīng)的RSS 賦值為-100 dB·m，與測試指紋中對應(yīng)MAC 的RSS 一并參與式（3）計算，求得遍歷測試指紋的信號域距離，用 sig-ttfd 表示。如圖2（b）所示，參考指紋中插入MAC 和RSS 的鍵值對，用紅色方框表示。

2 實驗與分析

為了研究不同信號域距離和信號缺失補(bǔ)償值對定位精度的影響，本文采用無聚類的WKNN 算法進(jìn)行定位解算，并引入平均誤差（mean error，ME）和均方根誤差（root mean square error，RMSE）作為定位精度的評價指標(biāo)。

2.1 實驗描述

中國礦業(yè)大學(xué)環(huán)測學(xué)院4 樓室內(nèi)定位試驗場如圖4 所示。在該試驗場內(nèi)開展實驗，場景為4 段走廊，長約211 m，寬約2.4～3 m，面積約為3 200 m2，部署有56 個2.4 GHz 單頻AP，352 個參考點以1.2 m間距均勻分布，用黑色正方形表示，82 個測試點呈“S”形分布，用綠色實心點表示。測試點數(shù)目與參考點數(shù)目比值大于23%，且均勻分布在整個試驗場，能夠較準(zhǔn)確地反映試驗場的指紋定位精度。在每個參考點處以1 Hz 的頻率采樣60 次，均值處理后共生成5 489 個MAC 與RSS的鍵值對。在測試點處以相同的頻率采樣10 次，得到820 個樣本用于精度評估。利用WKNN 算法，分別基于上述5 種不同信號域距離開展定位計算，統(tǒng)計不同信號域距離與不同K 值時的定位誤差，K 取值為1～9。在計算機(jī)輔助設(shè)計（computer aided design， CAD）中選取建筑物左下角為坐標(biāo)原點，保證建筑物內(nèi)所有坐標(biāo)均為正值，在CAD 上規(guī)劃所有參考點和測試點，并拾取坐標(biāo)用于后續(xù)精度評定。

圖4 室內(nèi)定位試驗場

2.2 實驗結(jié)果分析

采用不同信號域距離取得最佳定位性能時對應(yīng)的定位誤差統(tǒng)計結(jié)果如表1 所示。

表1 采用不同信號域距離時的定位誤差統(tǒng)計

遍歷測試指紋的信號域距離（ dsig-ttf）的平均定位誤差為2.398 m，采用遍歷測試指紋和參考指紋并集的信號域距離（ dsig-tfu）的平均定位誤差約為3 m，而采用遍歷測試指紋和參考指紋交集的信號域距離（ dsig-tfi）具有高達(dá)84 m 的平均定位 誤 差。與 采 用 dsig-tfu-sum和 dsig-tfu-avg的 定 位 方 法 相比，采用 dsig-ttf的平均定位誤差分別減小了0.632 m和0.617 m，均方根誤差分別減小了0.773 m 和0.583 m。

當(dāng)K 為5 時，dsig-ttf、dsig-tfu-avg和 dsig-tfu-sum分別取得了最佳定位性能，而前2 者要優(yōu)于后者。2 種信號域距離的定位誤差的累積概率分布如圖5 所示，紅色實心點線和藍(lán)色空心點線分別表示當(dāng)K 為5時基于 dsig-tfu-avg和 dsig-ttf的定位誤差累積分布。從圖5中可以看出，藍(lán)色點線高于紅色點線，基于 dsig-ttf指紋定位誤差小于2 m 的概率為 60%，而基于dsig-tfu-avg的概率為50%。因此，采用遍歷測試指紋信號域距離的指紋定位精度要優(yōu)于其他信號域距離。

圖5 2 種信號域距離的定位誤差的累積概率分布

2 種信號域距離的定位誤差如圖6 所示，紅色實心點線和藍(lán)色空心點線分別表示當(dāng)K 為5 時基于 dsig-tfu-avg和 dsig-ttf的定位誤差，從圖6 中可以看出，藍(lán)色空心點線的波動性要小于紅色實心點線，即基于 dsig-ttf指 紋定位的 穩(wěn) 定性要強(qiáng)于 dsig-tfu-avg。

圖6 2 種信號域距離的定位誤差

綜上所述，基于遍歷測試指紋信號域距離的指紋定位精度和穩(wěn)定性要優(yōu)于其他信號域距離。除此以外，從表1 中還可以看出，采用并集形式計算的信號域距離的定位精度要優(yōu)于交集形式，采用均值形式計算的信號域距離的定位精度要優(yōu)于求和形式。

3 結(jié)束語

本文根據(jù)遍歷指紋、求和與均值計算對信號域距離進(jìn)行分類，并在3 200 m2的試驗場分別開展了定位測試，對比分析了不同信號域距離對定位精度的影響。基于遍歷測試指紋的信號域距離指紋定位具有最高定位精度和穩(wěn)定性，平均定位誤差為2.398 m，相比于其他信號域距離定位精度提高了至少0.6 m。通過實驗驗證了基于遍歷測試指紋的信號域距離指紋定位具有較高定位精度，可以為室內(nèi)指紋定位相關(guān)應(yīng)用和研究提供參考和依據(jù)。

在本文研究過程中，忽略了信號缺失對信號域距離計算的影響，在后續(xù)研究中將探索信號缺失動態(tài)補(bǔ)償方法，對比分析不同的信號缺失補(bǔ)償值對定位精度的影響，并采用不同機(jī)器學(xué)習(xí)方法研究室內(nèi)指紋定位。此外，本文采用了自主采集的實驗數(shù)據(jù)集進(jìn)行驗證和分析，后續(xù)研究將進(jìn)一步使用開源的大規(guī)模指紋定位數(shù)據(jù)集進(jìn)行多場景的性能評測。