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

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

0 引言

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

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

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

1 信號(hào)域距離及其分類

1.1 信號(hào)域距離

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 信號(hào)域距離的分類

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

圖3 信號(hào)域距離分類

具體表述如下：

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

2 實(shí)驗(yàn)與分析

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

2.1 實(shí)驗(yàn)描述

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

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

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

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

表1 采用不同信號(hào)域距離時(shí)的定位誤差統(tǒng)計(jì)

遍歷測試指紋的信號(hào)域距離（ dsig-ttf）的平均定位誤差為2.398 m，采用遍歷測試指紋和參考指紋并集的信號(hào)域距離（ dsig-tfu）的平均定位誤差約為3 m，而采用遍歷測試指紋和參考指紋交集的信號(hào)域距離（ 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 時(shí)，dsig-ttf、dsig-tfu-avg和 dsig-tfu-sum分別取得了最佳定位性能，而前2 者要優(yōu)于后者。2 種信號(hào)域距離的定位誤差的累積概率分布如圖5 所示，紅色實(shí)心點(diǎn)線和藍(lán)色空心點(diǎn)線分別表示當(dāng)K 為5時(shí)基于 dsig-tfu-avg和 dsig-ttf的定位誤差累積分布。從圖5中可以看出，藍(lán)色點(diǎn)線高于紅色點(diǎn)線，基于 dsig-ttf指紋定位誤差小于2 m 的概率為 60%，而基于dsig-tfu-avg的概率為50%。因此，采用遍歷測試指紋信號(hào)域距離的指紋定位精度要優(yōu)于其他信號(hào)域距離。

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

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

圖6 2 種信號(hào)域距離的定位誤差

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

3 結(jié)束語

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

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