陳亦奇，周 蓉，滕 婧，周洪波，欒泉中

(華北電力大學(xué)控制與計(jì)算機(jī)工程學(xué)院，北京 102206)

0 引言

無線通信和移動設(shè)備的激增為室內(nèi)定位服務(wù)(Location-Based Services，LBS)帶來了廣泛的應(yīng)用前景。然而，與已經(jīng)通過全球定位系統(tǒng)(Global Positioning System，GPS)完美解決的室外定位問題不同，室內(nèi)定位的挑戰(zhàn)在于非視距(Non-Line of Sight，NLOS)問題，即由于屋頂、墻壁和一些其他障礙物的存在，GPS信號容易衰減或受到屏蔽使得GPS定位不再可靠。目前，實(shí)現(xiàn)高精度的室內(nèi)定位已經(jīng)成為定位領(lǐng)域的研究熱點(diǎn)，在現(xiàn)有的諸多室內(nèi)定位方法中，由于WiFi接入點(diǎn)(Access Point，AP)的廣泛部署和無處不在的智能設(shè)備(如智能手機(jī)、平板和筆記本電腦)，基于WiFi 指紋的室內(nèi)定位方法成為了最易于實(shí)現(xiàn)的室內(nèi)定位方法[1]。除此之外，指紋定位方法還具有以下優(yōu)點(diǎn)：無需額外的硬件輔助，定位精度高，定位成本低，適用于不同的室內(nèi)環(huán)境[2]。指紋定位算法包括2個(gè)階段：離線訓(xùn)練階段和在線定位階段。主要思想是將在線定位階段采集到的測試點(diǎn)(Test Point，TP)指紋與離線訓(xùn)練階段生成的指紋庫中各參考點(diǎn)(Reference Point，RP)指紋進(jìn)行匹配，根據(jù)指紋匹配結(jié)果預(yù)測TP的位置坐標(biāo)。目前，這2個(gè)階段的研究方向主要在于：更可靠的指紋特征值、更便捷的指紋庫構(gòu)建和更準(zhǔn)確的指紋匹配[3]，本文著重于實(shí)現(xiàn)最后一項(xiàng)。

常見的指紋匹配算法通過計(jì)算指紋在信號空間內(nèi)的歐氏距離來實(shí)現(xiàn)，歐氏距離越小，則指紋相似度越高，指紋在物理空間中的距離越近。一般情況下，指紋間的所有接收信號強(qiáng)度(Received Signal Strength，RSS)差值，無論大小均會被用于計(jì)算歐氏距離。但在實(shí)際環(huán)境下，即使在相同條件下，在同一位置，間隔很短一段時(shí)間采集的信號也具有波動性。這種波動性體現(xiàn)在RSS的持續(xù)變化上，通常由于采集時(shí)間、采集設(shè)備和環(huán)境的變化而導(dǎo)致。因此指紋間部分較小的RSS差值并不一定能反映指紋的不同，反而可能是信號波動性的結(jié)果。通常的處理方式是對RSS做均值濾波，但均值濾波后的RSS會損失一部分的信息，從而對定位精度產(chǎn)生影響。Fang給出的處理方案是將信號波動轉(zhuǎn)化為在信號強(qiáng)度對數(shù)域中的一個(gè)附加隨機(jī)變量，但實(shí)際上的信號波動并不是非常契合該模型，處理后的定位精度不佳[4]。Zhuang提出了基于擁有不變性的信號強(qiáng)度階代替RSS作為指紋匹配的特征，從而規(guī)避了信號波動的影響[5]。其他WiFi指紋定位算法都忽略了信號的波動性及其對定位精度的影響。

針對該問題，本文提出了自適應(yīng)修正算法來處理信號波動，并根據(jù)自適應(yīng)修正后的曼哈頓距離進(jìn)行指紋匹配。首先，根據(jù)AP選擇算法降低了指紋維度，僅選用可靠AP對應(yīng)的RSS；然后，在理論分析信號傳播衰減公式和信號波動后，提出了基于自適應(yīng)修正曼哈頓距離(Adaptive Correction Manhattan Distance，ACMD)計(jì)算指紋相似度的匹配算法；最后，結(jié)合加權(quán)K近鄰(Weighted K Nearest Neighbor，WKNN)方法實(shí)現(xiàn)定位。在開放室內(nèi)定位數(shù)據(jù)集Zenodo[6]上進(jìn)行定位實(shí)驗(yàn)，結(jié)果表明，在WKNN框架下，基于ACMD的指紋匹配算法在定位精度上優(yōu)于基于歐氏距離(Euclidean Distance，ED)、曼哈頓距離(Manhattan Distance，MD)、余弦距離(Cosine Distance，COSD)和Sorensen距離(Sorensen Distance，SD)的指紋匹配算法。

1 相關(guān)工作

1.1 指紋定位原理

指紋定位算法通過計(jì)算TP和RP指紋之間的相似度，得到一組與TP相似度較高的RP集合，然后基于集合中RP的坐標(biāo)加權(quán)估計(jì)TP的坐標(biāo)。如圖1所示，該算法分為2個(gè)階段：離線訓(xùn)練階段和在線定位階段。

圖1 指紋定位算法流程圖Fig.1 Flow chart of fingerprint positioning algorithm

指紋由一組采集到的不同AP的RSS組成，根據(jù)采集階段的不同，指紋分為TP指紋和RP指紋。TP指紋在在線定位階段測得，用于估計(jì)TP的位置坐標(biāo)；而RP指紋在離線訓(xùn)練階段測得，存儲在數(shù)據(jù)庫中，與坐標(biāo)一起構(gòu)成指紋數(shù)據(jù)庫，起預(yù)定義參照標(biāo)準(zhǔn)的作用。

離線訓(xùn)練階段的任務(wù)是構(gòu)建指紋數(shù)據(jù)庫，指紋數(shù)據(jù)庫由預(yù)設(shè)RP點(diǎn)物理空間坐標(biāo)和該RP點(diǎn)的指紋組成。RSS易受環(huán)境變化、行人走動或障礙物的影響，因此在訓(xùn)練階段，通常在各個(gè)RP點(diǎn)進(jìn)行多次RSS的采集以構(gòu)建魯棒的指紋庫。假設(shè)RSSAPi(RPj)代表設(shè)備在RPj處采集到APi的RSS，AP總數(shù)為n，RP總數(shù)為m，指紋庫FPDB以矩陣形式保存，如式(1)所示

FPDB=

(1)

在線定位階段的任務(wù)是將在TP點(diǎn)采集的指紋與指紋庫中不同RP點(diǎn)的指紋進(jìn)行匹配，并根據(jù)匹配結(jié)果估計(jì)TP點(diǎn)位置以實(shí)現(xiàn)定位。在線定位階段在TP點(diǎn)采集的指紋如式(2)所示

(2)

1.2 指紋匹配算法

常見的指紋匹配算法大多是基于KNN類的確定性算法，這類算法使用RSS均值或最大值作為信號特征。KNN算法由Bahl和Padmanabhan首次引入到室內(nèi)定位中，通過在指紋空間中找到與TP歐氏距離最小的K個(gè) RP，計(jì)算K個(gè)RP的平均坐標(biāo)作為TP的預(yù)測坐標(biāo)[7]。WKNN方法是對KNN算法的改進(jìn)，基于K個(gè)RP與TP的歐氏距離分別賦予這K個(gè)RP相應(yīng)的權(quán)重，并根據(jù)各RP的權(quán)重對坐標(biāo)加權(quán)實(shí)現(xiàn)定位。其中權(quán)重通常取歐氏距離的倒數(shù)，Chen基于方差的加權(quán)距離改進(jìn)WKNN算法，改善了該算法在信號波動幅度較大時(shí)的定位精度[8]。KNN類的匹配算法實(shí)現(xiàn)簡單，定位精度較高，因此其應(yīng)用范圍很廣。但是也有著如下幾種問題：首先，算法使用RSS均值或最大值來表示W(wǎng)iFi的信號強(qiáng)度，這種簡化會導(dǎo)致誤差；其次，在信號空間內(nèi)K個(gè)擁有最小歐氏距離的RP并不一定就是在物理空間內(nèi)與TP距離最小的K個(gè)RP。

除了基于KNN類的確定性匹配算法之外，還有基于信號強(qiáng)度分布的概率性匹配算法，該類方法將信號強(qiáng)度的概率分布作為特征。Zhou將指紋數(shù)據(jù)庫與物理近鄰數(shù)據(jù)庫相結(jié)合，根據(jù)2次使用貝葉斯推論選擇擁有最大先驗(yàn)概率的RP實(shí)現(xiàn)定位[9]。Campos通過組合無監(jiān)督聚類和多表決反向傳播神經(jīng)網(wǎng)絡(luò)構(gòu)建室內(nèi)定位模型，提高了在跨越樓層的室內(nèi)環(huán)境下的定位精度[10]。Calderoni結(jié)合RFID技術(shù)和隨機(jī)森林分類，提出了一種能夠抵御環(huán)境因素影響的定位系統(tǒng)，已經(jīng)在部分印度醫(yī)院投入使用[11]。概率性匹配算法相比確定性匹配算法避免了使用RSS均值導(dǎo)致的誤差，但也存在模型訓(xùn)練時(shí)間長、需要樣本數(shù)據(jù)量大的缺點(diǎn)[12]。

在基于KNN類的大多數(shù)指紋匹配算法中僅出現(xiàn)一些常見的度量距離，如歐氏距離、曼哈頓距離和馬氏距離。Xie根據(jù)在同一位置采集的RSS大小排序基本穩(wěn)定這一現(xiàn)象，使用斯皮爾曼距離匹配指紋[13]。Liu提出的M-WKNN方法是基于聚類指紋及改進(jìn)WKNN的方法，采用一種指數(shù)函數(shù)方式衡量指紋間的相似度及指紋的權(quán)重[14]。Han針對信號采集設(shè)備不同這一問題，提出了基于余弦距離匹配指紋[15]。苗云龍等將指紋轉(zhuǎn)換為包含32位16進(jìn)制表示的MD5序列，在指紋匹配時(shí)直接匹配MD5序列[16]。Torres-Sospedra同樣對不同的指紋匹配距離進(jìn)行了比較，并在KNN框架下進(jìn)行了定位比較，實(shí)驗(yàn)結(jié)果表明，歐氏距離并非指紋匹配的最佳距離，基于Sorensen距離的匹配算法定位精度最高[17]。

2 算法描述

2.1 數(shù)據(jù)預(yù)處理

為了建立魯棒的指紋數(shù)據(jù)庫，需要先對RSS組進(jìn)行預(yù)處理，剔除異常數(shù)據(jù)和粗大誤差。

假設(shè)向量rss是在RPj上收集到來自APi的連續(xù)p次測量的RSS，如式(3)所示

(3)

(4)

(5)

再計(jì)算殘差的均方根誤差σ，如式(6)所示

(6)

2.2 AP選擇

在理想環(huán)境下，指紋定位的精度會隨著定位所使用AP數(shù)量的增加而持續(xù)升高。然而，在實(shí)際環(huán)境下，任何AP發(fā)出的信號都會受到障礙物和多徑效應(yīng)的影響，不經(jīng)篩選地使用所有AP不僅不會提高定位精度反而還會增加額外的計(jì)算負(fù)擔(dān)。因此，為了在提高定位精度的同時(shí)減少計(jì)算負(fù)擔(dān)，挑選出受干擾程度小和出現(xiàn)頻率高的AP參與指紋匹配是一種可行的方案。

在穩(wěn)定的室內(nèi)環(huán)境下，使用RSS均值做信號特征的定位精度不如使用RSS最大值做信號特征的定位精度[18]。同時(shí)較大的RSS也意味著信號接收裝置與AP間的距離較小，信號受到多徑效應(yīng)的干擾程度也較小。所以信號的受干擾程度指標(biāo)M(APi)RPj與在RPj處接收到APi的最大RSS值maxAPi(RPj)相關(guān)，如式(7)所示

(7)

其中，U是未接收到信號對應(yīng)的預(yù)設(shè)RSS，通常取-105dBm，M(APi)RPj越大，RPj處的APi就越可靠。

在離線訓(xùn)練階段的一個(gè)采樣周期中，假設(shè)在RPj處某一AP的信號出現(xiàn)頻率較高，則在在線定位階段中在RPj處也會有較大概率接收到該AP的信號。如式(8)所示，信號的出現(xiàn)頻率指標(biāo)P(APi)RPj用于表示在離線階段的一個(gè)采樣周期中，在RPj處接收到APi信號的出現(xiàn)頻率

(8)

對于一個(gè)采樣周期來說，SRPj是在RPj處信號采集的總次數(shù)，pAPi(RPj)是在RPj處接收到APi信號的次數(shù)，ε是一個(gè)極小的正數(shù)，避免分母為0。P(APi)RPj越大，對應(yīng)的APi在RPj處出現(xiàn)的頻率越高，也相應(yīng)越可靠。

AP選擇算法的標(biāo)準(zhǔn)R(APi)RPj由上述2個(gè)指標(biāo)綜合而得，反映了APi在RPj處的可靠程度，如式(9)所示

R(APi)RPj=M(APi)RPj×P(APi)RPj

(9)

基于AP的可靠程度對RPj處所有AP(下標(biāo)為1～n)進(jìn)行排序，保存可靠度最高的前L個(gè)AP的集合。在TP指紋與RPj指紋進(jìn)行匹配時(shí)，僅使用RPj對應(yīng)的L個(gè)可靠AP(下標(biāo)為L1～LL)，過程如圖2所示。與普通的AP選擇算法所不同的是，該算法會在各RP處給出相對應(yīng)的優(yōu)選AP集合，根據(jù)RP對應(yīng)的AP集合進(jìn)行指紋匹配，匹配結(jié)果更為可靠。

圖2 基于AP選擇處理指紋的示意圖 Fig.2 Schematic diagram of modified fingerprint based on AP selection

2.3 相似度度量

在指紋匹配算法介紹中提到，常見算法的相似度度量距離是歐氏距離，但歐氏距離并非用于指紋匹配的最佳度量距離。WiFi信號強(qiáng)度衰減模型如式(10)所示[19]

(10)

其中，RSSd是距離WiFi接入點(diǎn)距離為d的信號采集點(diǎn)處采集到的RSS，η是路徑損耗參數(shù),X代表由采集設(shè)備、時(shí)間或者環(huán)境不同引起的RSS波動。由于d0、RSS(d0)、η均為預(yù)設(shè)模型參數(shù)，在采集到RSS(di)后，根據(jù)式(10)可以計(jì)算出WiFi接入點(diǎn)到信號采集點(diǎn)之間的未知距離di,如式(11)所示

(11)

對于同一個(gè)AP、RP和TP之間的物理距離Δd與RP和TP采集到的RSS差值成正相關(guān)，如式(12)所示

Δd=d(RP)(APi)-d(TP)(APi)

∝RSSd(RP)(APi)-RSSd(TP)(APi)+X(X1,X2)

(12)

由于WiFi信號差值與它們之間的物理距離正相關(guān)，因此，可以基于同一AP的RP和TP之間的RSS差來估計(jì)它們之間的物理距離，這是使用曼哈頓距離來進(jìn)行指紋匹配的理論基礎(chǔ)。X(X1,X2)代表聯(lián)合信號波動，下面引入自適應(yīng)修正對信號波動進(jìn)行處理。

2.4 自適應(yīng)修正

在常見的指紋匹配方法中，指紋間的所有RSS差值無論大小均會被用于計(jì)算指紋的相似度。然而，即使是在相同位置連續(xù)采集的RSS也會持續(xù)變化，本文將這種RSS的持續(xù)變化稱為RSS波動。因此在指紋匹配時(shí)，指紋間的RSS差值應(yīng)包含實(shí)際的RSS差異和RSS波動，部分較小的RSS差值可能完全是RSS波動的結(jié)果。RSS波動如圖3所示，若沒有接收到某AP的信號，則將該AP對應(yīng)的RSS記作-105dBm。

(a)

(b)

圖3(a)和圖3(b)分別代表了2個(gè)不同位置的情況，DATA1代表從某一位置采集到40個(gè)AP的RSS，DATA2代表間隔2s后在與DATA1相同條件下采集到的RSS，繪制在每張圖頂部的RSS-DIFF代表DATA1與DATA2的RSS絕對差值，用于反映RSS的波動。根據(jù)圖3可以觀察到，即使在相同位置間隔極短時(shí)間采集的RSS也會有最大10dBm左右的波動，隨著信號強(qiáng)度的衰減，波動的頻率和最大值也逐漸增大。該現(xiàn)象的原因是RSS越小意味著采集設(shè)備距離AP越遠(yuǎn)，RSS受到環(huán)境內(nèi)障礙物和信號多徑傳播效應(yīng)的影響也越大，若對該種波動不加以處理會影響指紋匹配的結(jié)果。

通過上面的分析，本文提出了使用自適應(yīng)修正的方式處理在不同RSS大小下的RSS波動，下文提及的RSS差值均指差值的絕對值。修正的含義是給予指紋匹配時(shí)的RSS差值一個(gè)波動上限T，當(dāng)RSS差值小于等于波動上限時(shí)，認(rèn)為該RSS差值是RSS波動的結(jié)果，并將該RSS差值置為0；當(dāng)RSS差值大于波動上限時(shí)，認(rèn)為該RSS差值代表了指紋的差異，將該RSS差值減去波動上限后保留。具體的規(guī)則如式(13)所示

(13)

其中，diff代表初始RSS差值，T代表波動上限，c_diff代表修正后的RSS差值。

之前的研究表明，RSS波動更容易在距離AP較遠(yuǎn)的位置出現(xiàn)，且波動的范圍也更大。因此，引入自適應(yīng)函數(shù)A對各RSS值對應(yīng)的波動上限T做相應(yīng)的調(diào)整,該過程在離線訓(xùn)練階段實(shí)現(xiàn)，不會影響定位的實(shí)時(shí)性，具體如式(14)所示

ATAPi(RPj)=A(RSSAPi(RPj))·T

(14)

其中，ATAPi(RPj)是指紋庫中信號強(qiáng)度RSSAPi(RPj)對應(yīng)的波動上限，自適應(yīng)函數(shù)A的實(shí)現(xiàn)如式(15)和式(16)

(15)

(16)

其中，U是未接收到信號對應(yīng)的信號強(qiáng)度，通常取-105dBm，all_rss以矩陣形式存儲了經(jīng)過式(15)變換后的所有rss，底數(shù)α用于改變自適應(yīng)系數(shù)的變化范圍。某位置的RSS值越大，意味著該位置距離AP越近，出現(xiàn)波動的可能性和波動的變化范圍越小，因此波動上限T也越小，對RSS波動的界定也越嚴(yán)格，修正程度也更小。自適應(yīng)修正RSS差值的規(guī)則與修正RSS差值的規(guī)則類似，如式(17)所示

(17)

其中，AT代表自適應(yīng)的波動上限。

此外，RSS的數(shù)值實(shí)際上表示接收信號功率Power與1mW參考功率之間的比例，如式(18)所示

(18)

在不同的信號強(qiáng)度下，信號強(qiáng)度差與信號功率差不適合用線性關(guān)系來轉(zhuǎn)化。舉例來說，信號強(qiáng)度-50dBm與-60dBm之間的信號功率差是9×10-6mW，信號強(qiáng)度-90dBm與-100dBm之間的信號功率差是9×10-10mW;然而在現(xiàn)有的指紋定位算法中，上面2組信號的RSS差值被認(rèn)為是相同的10dBm，實(shí)際上2組信號的功率差相差整整104倍，僅靠RSS差值計(jì)算指紋相似度無疑會引入誤差。因此，設(shè)置RSS差值的調(diào)整函數(shù)M，基于信號強(qiáng)度給予RSS差值相應(yīng)的調(diào)整系數(shù)，M函數(shù)通過式(19)獲得

(19)

通過M函數(shù)調(diào)整RSS差值，使得較大信號強(qiáng)度對應(yīng)的RSS差值在指紋相似度計(jì)算的過程中具有更大的系數(shù)，但調(diào)整系數(shù)的變化范圍同樣不宜設(shè)置過大，避免破壞指紋數(shù)據(jù)的真實(shí)性，影響指紋匹配的結(jié)果。

綜上所述，首先采用自適應(yīng)修正的方式解決指紋匹配中的信號波動問題，然后基于信號強(qiáng)度的大小對相應(yīng)的RSS差值作出調(diào)整。在進(jìn)行RPj指紋和TP指紋的匹配時(shí)，指紋間的自適應(yīng)修正曼哈頓距離如式(20)所示，即L個(gè)優(yōu)選AP(下標(biāo)L1～LL)對應(yīng)的修正RSS差值的總和

(20)

2.5 基于ACMD-WKNN的定位算法

基于ACMD-WKNN的定位算法的思想是：在完成數(shù)據(jù)預(yù)處理和AP選擇之后，基于ACMD進(jìn)行指紋匹配，用WKNN方法實(shí)現(xiàn)位置估計(jì)，具體流程圖如圖4所示。

圖4 基于ACMD-WKNN的定位算法流程圖Fig.4 Flow chart of positioning algorithm based on ACMD-WKNN

假設(shè)計(jì)算得到K個(gè)相似度最大的參考點(diǎn)，下標(biāo)j的變化范圍是[1,K]，TP指紋與RPj指紋的ACMD是ACMDRPj，對應(yīng)的權(quán)重WRPj如式(21)所示，M為一較大數(shù)，這里暫取100

(21)

參考點(diǎn)RPj的坐標(biāo)是(Xj，Yj),TP的位置(X，Y)可通過式(22)估計(jì)獲得

(22)

3 定位實(shí)驗(yàn)

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

本文使用學(xué)者M(jìn)endoza-Silva G、Richter P及Torres-Sospedra J等提供的開放室內(nèi)定位數(shù)據(jù)集-10.5281/zenodo.1066040作為實(shí)驗(yàn)數(shù)據(jù)集。該數(shù)據(jù)集從一幢圖書館的3層與5層分別采集獲得，采集區(qū)域?yàn)楦鲗用娣e為125.4m2的書架區(qū)域，實(shí)驗(yàn)數(shù)據(jù)集包含總共15個(gè)月的測量數(shù)據(jù)，該數(shù)據(jù)集存儲了共448個(gè)以MAC地址為唯一區(qū)分的AP(單路由器上有多AP)，在每層24個(gè)共48個(gè)RP處的信號強(qiáng)度值。此外，采集時(shí)會預(yù)先給各RP設(shè)置序號，并根據(jù)序號進(jìn)行采集，為了避免偶然性帶來的誤差，在各采集點(diǎn)上均進(jìn)行6次采集。每月的數(shù)據(jù)集通常包含1組訓(xùn)練集與5組測試集，數(shù)據(jù)采集點(diǎn)的分布如圖5所示。

圖5 數(shù)據(jù)采集點(diǎn)的位置及分布情況Fig.5 Position and distribution of data collection points

圖5中,黑色矩形是書柜，橫向來看，每2排書柜間有3個(gè)采集點(diǎn)，從上至下依次屬于測試集2、訓(xùn)練集(測試集1、測試集5)和測試集3；縱向來看，每2排書架間的采集點(diǎn)屬于測試集4，按照序號升序和降序的順序先后各進(jìn)行1次測量。選擇該數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)的原因有二點(diǎn)：1)該數(shù)據(jù)集提供長達(dá)15個(gè)月的信號強(qiáng)度數(shù)據(jù)，大數(shù)據(jù)量的實(shí)驗(yàn)結(jié)果保證了定位算法的可靠性與魯棒性；2)在該數(shù)據(jù)集中包含有大量可用于模擬用戶持續(xù)移動的測試點(diǎn)，如測試集2和測試集4對應(yīng)模擬用戶在書架間行走和走道上行走的不同狀態(tài)，方便后續(xù)展開基于目標(biāo)跟蹤的研究。在本次實(shí)驗(yàn)中選用第3層全部月份所有訓(xùn)練集和測試集的指紋數(shù)據(jù)進(jìn)行定位實(shí)驗(yàn)。

3.2 波動上限T的影響

自適應(yīng)修正算法中波動上限T的變化會導(dǎo)致修正后的RSS發(fā)生變化，進(jìn)而影響指紋匹配結(jié)果。若T過大，會導(dǎo)致對RSS波動的過度修正，將較多相似度并不高的指紋保留下來；若T過小，算法會退化成無修正算法，無法實(shí)現(xiàn)對RSS波動的平滑。在實(shí)驗(yàn)中取T為 0dBm、5dBm和10dBm，結(jié)果如圖6所示。

圖6 基于不同波動上限T的誤差CDF Fig.6 Error CDF based on different fluctuation upper limit T

圖6以誤差累計(jì)概率分布函數(shù)(Cumulative Distribution Function，CDF)的形式給出結(jié)果，當(dāng)T=0dBm時(shí)，即基于無修正曼哈頓距離的定位精度并不如T=5dBm或10dBm的定位精度。因此，基于自適應(yīng)修正曼哈頓距離的算法相比無修正的算法的確能夠提升定位精度。除此之外，T=10dBm時(shí)的定位精度并不如T=5dBm時(shí)的定位精度，即定位精度并不會隨著T的增加而不斷提高。根據(jù)圖6基本確定了最佳T在5dBm附近，進(jìn)一步縮小了T的測試范圍到3～7dBm，基于不同T的定位誤差如表1所示。由于T相近時(shí)CDF圖也較為接近，故不再依靠誤差CDF圖分析實(shí)驗(yàn)結(jié)果。

表1 基于不同T(3～7dBm)的定位誤差

通過表1可以得到，當(dāng)T=3～7dBm時(shí)，平均誤差及75%概率誤差均在T=6dBm時(shí)取到最小，故在本文的實(shí)驗(yàn)中取T=6dBm，實(shí)驗(yàn)結(jié)果也從側(cè)面證明了處理信號波動能夠提高定位精度。

3.3 底數(shù)α的影響

底數(shù)α用于生成自適應(yīng)的波動上限T，波動上限T隨RSS值的大小自適應(yīng)發(fā)生改變，圖7是基于不同的底數(shù)α的值所繪制的RSS與自適應(yīng)波動上限AT的關(guān)系圖，其中初始波動上限T取6dBm，e為自然對數(shù)。

圖7 基于不同α的RSS與AT的關(guān)系圖 Fig.7 Relationship between RSS and AT based on different α

從圖7中可以看出，基于不同底數(shù)α的RSS-AT曲線在RSS最小時(shí)均取到最大波動上限，但隨著底數(shù)α的增大，AT的變化范圍也逐漸增大，在RSS取到最大值-46dBm時(shí)，底數(shù)α取1.1、e和10對應(yīng)的波動上限分別為5.405dBm、2.207dBm和0.645dBm。根據(jù)3.2節(jié)的結(jié)論，過小的波動上限無法實(shí)現(xiàn)對RSS波動的平滑，且波動上限T在6dBm附近取得最小的定位誤差，因此自適應(yīng)的波動上限AT也應(yīng)在6dBm附近變化。當(dāng)α取1.1時(shí)能夠滿足上述要求，此時(shí)波動上限T的變化范圍是[5.405，6]，在給予大RSS值小波動上限的同時(shí)保證了對全部RSS的修正效果。

3.4 AP選擇數(shù)量L的影響

AP選擇算法的目標(biāo)是在選出更可靠、受干擾更小的AP的同時(shí)減輕計(jì)算負(fù)擔(dān)。因此，確定AP選擇算法所選AP數(shù)量L的重要性不言自明，實(shí)驗(yàn)中將選擇AP數(shù)量L設(shè)置為10～70，用于分析L對定位精度的影響；同時(shí)與無AP選擇的算法進(jìn)行對比，用于驗(yàn)證AP選擇算法對于定位精度的改進(jìn)效果，結(jié)果如圖8所示。實(shí)驗(yàn)中AP的總數(shù)為448個(gè)，橫軸上的“NO-Selection”代表無AP選擇(L=448)的情況。

圖8 基于不同AP選擇數(shù)量L的誤差Fig.8 Error based on different AP selection number L

根據(jù)圖8可知，當(dāng)L小于50時(shí)，隨著用于定位的AP數(shù)量L的增大，定位精度也隨之提升；當(dāng)L達(dá)到50后，定位精度最佳，且優(yōu)于無AP選擇算法的定位精度；當(dāng)L超過50后，算法選擇的L個(gè)AP中不可靠AP的數(shù)量增多，定位精度反而有所下滑。因此，AP選擇算法能夠在減少指紋匹配計(jì)算量的同時(shí)提高定位精度，本文設(shè)置AP選擇數(shù)量L為50。

3.5 基于不同距離的匹配算法比較

實(shí)驗(yàn)中實(shí)現(xiàn)了基于ACMD和基于歐氏距離、曼哈頓距離、余弦距離及Sorensen距離的指紋匹配算法，并在WKNN框架下進(jìn)行了定位實(shí)驗(yàn)。根據(jù)定位結(jié)果進(jìn)行比較和分析，基于不同距離的匹配算法對應(yīng)的定位精度如圖9所示，WKNN方法中的K取3。

圖9 基于不同距離的匹配算法定位誤差Fig.9 Positioning error based on matching algorithm of different distance

首先，基于不同距離的匹配算法從平均定位誤差、67%累積概率誤差、95%累積概率誤差、定位誤差標(biāo)準(zhǔn)差和精度提升比5個(gè)方面進(jìn)行了比較，結(jié)果如表2所示。

表2 基于不同距離的定位誤差

其次，基于不同距離的匹配算法在固定精度要求下的誤差累積概率如表3所示。

表3 在固定精度要求下的誤差累積概率表

綜上所述，基于ACMD的匹配算法相對基于其他距離的匹配算法在定位精度上有顯著提升,且定位誤差的標(biāo)準(zhǔn)差更小，定位誤差在2m和3m內(nèi)的概率分別達(dá)到了62.41%和83.23%。

4 結(jié)論

本文針對常見的指紋匹配算法中所忽略的信號波動問題，提出了一種基于自適應(yīng)修正曼哈頓距離的WiFi指紋匹配算法，并結(jié)合AP選擇算法簡化了指紋匹配過程，最后基于WKNN方法實(shí)現(xiàn)定位。算法分析與實(shí)驗(yàn)結(jié)果表明：

1)在實(shí)際環(huán)境下，由環(huán)境因素、采集設(shè)備或采集時(shí)間差異導(dǎo)致的信號波動總是存在，并會對定位結(jié)果產(chǎn)生影響。本文所提出的自適應(yīng)修正算法在指紋匹配時(shí)，根據(jù)信號強(qiáng)度自適應(yīng)地對指紋間的信號強(qiáng)度差值進(jìn)行修正，減少信號波動對指紋匹配的影響，為后續(xù)研究處理信號的波動性問題提供了新的思路。修正過程的自適應(yīng)參數(shù)在離線階段獲得，不會對匹配和定位帶來額外的計(jì)算負(fù)擔(dān)。

2)基于自適應(yīng)修正曼哈頓距離的指紋匹配算法相比基于其他幾種常見距離的指紋匹配算法定位誤差更小，定位更穩(wěn)定，同時(shí)證實(shí)了歐氏距離并非指紋匹配時(shí)的最佳相似度度量距離。本文的算法實(shí)現(xiàn)了在面積為125.4m2的定位區(qū)域內(nèi)，平均定位誤差1.85m,62.41%的定位誤差在2m以內(nèi)和83.23%的定位誤差在3m以內(nèi)的定位效果。

3)本文提出的基于自適應(yīng)修正曼哈頓距離的指紋匹配算法還缺乏與更多相似度度量距離的比較，因此在后續(xù)工作中會增加更多用于對比的相似度度量距離。目前僅在Zenodo數(shù)據(jù)集上進(jìn)行了定位實(shí)驗(yàn)，后續(xù)將在更多知名的定位數(shù)據(jù)集和真實(shí)環(huán)境中進(jìn)行測試。