基于自適應修正曼哈頓距離的室內定位方法

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

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

0 引言

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

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

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

1 相關工作

1.1 指紋定位原理

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

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

指紋由一組采集到的不同AP的RSS組成，根據采集階段的不同，指紋分為TP指紋和RP指紋。TP指紋在在線定位階段測得，用于估計TP的位置坐標；而RP指紋在離線訓練階段測得，存儲在數據庫中，與坐標一起構成指紋數據庫，起預定義參照標準的作用。

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

FPDB=

(1)

在線定位階段的任務是將在TP點采集的指紋與指紋庫中不同RP點的指紋進行匹配，并根據匹配結果估計TP點位置以實現定位。在線定位階段在TP點采集的指紋如式(2)所示

(2)

1.2 指紋匹配算法

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

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

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

2 算法描述

2.1 數據預處理

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

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

(3)

(4)

(5)

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

(6)

2.2 AP選擇

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

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

(7)

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

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

(8)

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

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

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

(9)

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

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

2.3 相似度度量

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

(10)

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

(11)

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

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

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

(12)

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

2.4 自適應修正

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

(a)

(b)

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

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

(13)

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

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

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

(14)

其中，ATAPi(RPj)是指紋庫中信號強度RSSAPi(RPj)對應的波動上限，自適應函數A的實現如式(15)和式(16)

(15)

(16)

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

(17)

其中，AT代表自適應的波動上限。

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

(18)

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

(19)

通過M函數調整RSS差值，使得較大信號強度對應的RSS差值在指紋相似度計算的過程中具有更大的系數，但調整系數的變化范圍同樣不宜設置過大，避免破壞指紋數據的真實性，影響指紋匹配的結果。

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

(20)

2.5 基于ACMD-WKNN的定位算法

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

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

假設計算得到K個相似度最大的參考點，下標j的變化范圍是[1,K]，TP指紋與RPj指紋的ACMD是ACMDRPj，對應的權重WRPj如式(21)所示，M為一較大數，這里暫取100

(21)

參考點RPj的坐標是(Xj，Yj),TP的位置(X，Y)可通過式(22)估計獲得

(22)

3 定位實驗

3.1 實驗環境與步驟

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

圖5 數據采集點的位置及分布情況Fig.5 Position and distribution of data collection points

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

3.2 波動上限T的影響

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

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

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

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

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

3.3 底數α的影響

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

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

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

3.4 AP選擇數量L的影響

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

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

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

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

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

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

首先，基于不同距離的匹配算法從平均定位誤差、67%累積概率誤差、95%累積概率誤差、定位誤差標準差和精度提升比5個方面進行了比較，結果如表2所示。

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

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

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

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

4 結論

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

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

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

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