動態模糊匹配下的多元相似度定位算法

秦寧寧，吳憶松，楊 樂

(1.江南大學 輕工過程先進控制教育部重點實驗室，江蘇 無錫 214122；2.南京航空航天大學 電磁頻譜空間認知動態系統工信部重點實驗室，江蘇 南京 211106；3.坎特伯雷大學 電氣與計算機工程系，新西蘭 克賴斯特徹奇 8011)

目前，大部分室內定位方法是利用無線信號的相關特征來進行定位的，常用的技術有WiFi[1]、射頻識別[2]、超寬帶[3]和藍牙[4]等。室內環境的復雜性導致無線信號在傳播時容易引發多徑效應，很難對不同場景下的信號變換給出精準的數學模型。由于指紋匹配方法側重于接收信號強度(Received Signal Strength，RSS)的指紋特征，而非遍歷所有信號，因此可以通過匹配待定位點與指紋點的接收信號強度分布來獲取待定位點的位置。

基于近鄰點求平均位置的算法是最常見的指紋定位方法之一，微軟公司的雷達系統[5]中提出的信號空間中K最近鄰算法(K-Nearest Neighbors，KNN)，選取待定位點與指紋庫中匹配度最高的K個指紋點，以平均位置作為待定位點的位置。針對K最近鄰算法因平等對待近鄰點導致定位誤差較大的問題，文獻[6-7]引用了加權KNN算法(Weighted KNN，WKNN)，增加指紋點的歐氏信息作為權重，用體現位置相似度的加權平均替代均衡平均，提高了定位精度。但固定的K值依然無法避免選擇虛假的近似指紋點參與位置估計[8]。為了解決這個問題，文獻[9]引入動態K值概念，把歐氏相似度大于閾值的指紋點去除后，再求加權平均位置。

上述基于最近鄰指紋點的定位算法都具有簡單易行的優勢，但定位精度有限。近年來，為了提高定位精度，人們開始傾向于將復雜的機器學習方法引入到定位算法中，從而挖掘更深層次的信號特征。物理位置與信號強度的關聯度越高，則定位越容易[10]。因此，姚彪英等[11]提出一種基于改進支持向量回歸的室內定位方法，在訓練階段增加一個校正坐標z，提高二維位置信息與接收信號強度之間的關聯性。基于機器學習算法的定位方法雖然在定位精度方面表現優異，卻也帶來了計算復雜度高和定位時間長、效率低的問題。為減少匹配計算量的同時保證系統的實時性，田增山等[12]基于主成分分析法(Principle Component Analysis，PCA)給出在子空間內的匹配算法，基于在線信號從離線指紋庫中提取子指紋庫，利用主成分分析法對在線數據及子指紋庫進行降維和構建子空間。基于主成分分析法的子空間匹配方法能有效提升定位效率，但無法保證局部匹配的正確率，尤其當室內空間中的障礙物、人流量等干擾因素增加時，會嚴重拉低子空間匹配的正確率，可見一般的子空間匹配方法難以適應環境因素的波動而進行動態調整。

針對定位精度與定位時間的矛盾，論文提出了模糊匹配K近鄰定位算法(Fuzzy Matching KNN，FMKNN)。作為一種動態的局部指紋庫匹配方法，FMKNN通過可調的子空間匹配閾值，平衡匹配精度與計算復雜度之間的增益雙贏，結合多維相似度系數，引入權重調整參數進行位置估計，優化近鄰點集合的結構，突出鄰近點的作用。實驗驗證該方法在降低匹配時間的同時，依然能為待定位點提供較為精準的匹配指紋信息，所構建的位置估計算法，確實進一步提高了定位的精度。

1 系統模型

1.1 網絡空間模型

平面空間的場景內，部署N個基站：PA1，PA2，…，PAi，…，PAN，其中i=1，2，…，N。場景內布置K個指紋點作為采集指紋信息的位置。離線階段，在指紋點處采集來自N個基站的RSS與其物理位置共同組成指紋點信息，記第k個指紋點PFk的指紋信息為PFk=[(xk，yk)，(Rk1，Rk2，…，RkN)]，其中k=1，2，…，K。在線階段，在待定位點PT處采集來自N個基站的接收信號強度組成待定位點信號向量，記待定位點的信號向量為PT=[R1，R2，…，RN]，PT的物理位置坐標為(x，y)。PFk，PT以及PAi共同構成了論文的網絡空間模型。

1.2 基于泰森多邊形的子指紋庫聚類方法

為提高定位速度，以基站作為基點，利用泰森多邊形[13-14]對PFk進行聚類，生成若干個以接收信號強度為參考量的子指紋庫，用以簡化定位階段的搜尋過程。PFk聚類的過程如下：

步驟1 區域分割。以N個基站為基點，對場景生成關于基站的泰森多邊形，包含N個子區域Ωi。

步驟2 指紋點數據錄入。記錄定位場景中K個指紋點的指紋信息PF1，PF2，…，PFK。

步驟3 指紋點聚類。以子區域為依據對指紋點進行聚類，若PFk位于PAi對應的子區域Ωi內部，則將PFk聚類到子指紋庫DSi中，即

PFk∈DSi， if(xk，yk)∈Ωi，

(1)

其中，DSi內記錄屬于子區域Ωi的所有指紋PFk。

以如圖1(a)中N=8個基站為例，生成以PAi(i=1，2，…，8)為基點的8個子區域。在場景中隨機放置一定量的指紋點，依據泰森多邊形單元格進行指紋聚類，得到相應的8個子指紋庫DSi，如圖1(b)所示。

(a) 區域劃分示意圖

(b) 指紋點聚類示意圖

1.3 相似度系數

通常借助評估指紋點與待定位點所接收到接收信號強度的相似程度，即相似度系數，來衡量指紋點與待定位點之間的相關性。已有研究將相似度系數分為以歐氏距離[15]為代表的整體相似度系數和以空間余弦量[16]為參考的局部相似度系數。

1.3.1 歐氏相似度

歐氏相似度以PT和PFk之間信號向量的空間距離作為參考量，定義系統整體相似程度，其歐氏相似度Ek計算式為

(2)

可見Ek越大，給定PT與PFk的接收信號強度在向量空間的距離越小。

1.3.2 余弦相似度

基于余弦的相似度系數以PT和PFk的信號向量空間方向為參考量，衡量兩者的向量夾角建立局部相似度模型為Ck，即

(3)

可見Ck越大，給定PT與PFk的RSS向量在空間中的夾角越小。

2 指紋的概率特征提取

室內信號傳播會受到同頻、多徑、障礙等多重因素的聯合影響。若以經典的以時間段為統計單位的平均信號強度，直接作為某指紋點的指紋信號，則無法體現同一位置上接收信號強度的不確定性和隨機波動特征。考慮到同一位置采樣得到的接收信號強度信號值的頻數分布近似符合高斯分布，則可以剔除出現概率較小的信號值，保留高概率信號的幾何均值作為該指紋點的接收信號強度特征值，以此克服環境干擾的影響。

(4)

(5)

3 模糊匹配

3.1 匹配思想

在指紋定位的搜尋近鄰點階段，通常會選擇遍歷所有的PFk來與PT進行匹配，這種保證搜尋范圍完整性的極度貪婪做法，極易導致計算量激增。可對大范圍指紋區域采用泰森多邊形方式切割，并將PFk聚類到相應的DSi中，以區塊匹配的方法，把全局的遍歷搜索轉換為局部的快速檢索過程，在保留全局搜索準確性的基礎上可以提升定位的時效性。

然而，對指紋庫進行“一刀切”式的劃分在簡單易行的同時，勢必會帶來匹配階段準確性不高的問題。對于一些受到信號波動影響較大的指紋點，簡單的局部匹配方式極有可能為其匹配到錯誤的子庫。論文提出由多個子庫組成局部指紋庫DP，在PT匹配階段對子區域進行模糊匹配，得到其對應的局部指紋庫，有條件地擴大PT的匹配范圍，犧牲有限的定位速度來彌補傳統局部匹配算法誤差概率大的缺陷。

3.2 模糊匹配

為了兼顧局部指紋庫的匹配速度和準確率，需要根據場景特性調整匹配的模糊程度。為此，論文引入模糊參數f，在判斷PT與子區塊相關性時靈活地調整匹配包容度，找到具有場景獨特性的模糊參數值。

在線定位階段，待定位點匹配對應的局部指紋庫，匹配步驟如下：

步驟1 分割線標簽。根據泰森多邊形的特性可知，區塊分割線處于相鄰兩個基站連線的垂直平分線上。因此比較來自分割線兩側基站的接收信號強度大小，即可獲得以分割線為區分粒度的標簽。若泰森多邊形子區域Ωi由J條分割線切割而成，賦予每條分割線一個標簽，記第j條分割線(j=1，2，…，J)的標簽為

(6)

步驟2 子指紋庫標簽。當一塊區域的分割線標簽都已確定，該區域對應的DSi是否與PT匹配成功由J條分割線共同決定，則判斷子指紋庫標簽可表示為

(7)

步驟3 匹配局部指紋庫。前文已經提到，局部指紋庫由所有匹配成功的子指紋庫共同構成。因此，PT的局部指紋庫由標簽為1的子指紋庫組成，可表示為

(8)

多區塊的匹配結果既保證了PT不會被誤分類，又防止了全局匹配的低效性，是匹配速度和質量的一個折中辦法，同時削弱了兩種極端方法的缺陷。

3.3 模糊參數分析

模糊參數f的引入使得匹配過程中的模糊程度可調，因而保證了不同的定位空間及定位時間下都能做到模糊匹配的準確率與匹配量動態平衡。為了比較f的取值對算法匹配指紋點數量的影響，如圖2所示，將不同f取值下的DP匹配結果進行對比。由圖2(a)可見，當f=0即不采用模糊匹配時，DP是由單個DSi構成，且容易匹配到錯誤的結果；圖2(b)和圖2(c)中，當f>0，待定位點處的DP由多個子指紋庫組成，并且隨著f增大，匹配結果的區塊數量增加。

(a) f=0 (b) f=5 (c) f=10

4 位置計算

歐氏相似度表示空間中兩點的直線距離，作為一種最基本的相似性度量方法，由于算法簡單，其成為KNN的核心方法。在室內指紋定位技術中，待定位點PT與指紋點PFk的物理距離越近，得到的Ek就越大。而在實際中，由于接收設備的型號不同或環境差異，會造成在線階段對PT接收到的信號強度存在偏差；在這種情況下，采用歐氏距離進行近鄰點權重計算，會造成不同接收設備針對同一近鄰點權重不一致，進而產生較大的定位誤差。因此，論文引入多個層面的相似度考量方式，以此彌補單一相似度系數帶來的衡量偏差。

4.1 基于多元相似度的近鄰點集合

經研究發現，不同設備接收基站的接收信號強度向量存在差異性，終端差異會使得基于歐氏距離的定位精度降低，甚至會出現定位失敗的情況。終端差異雖然會引起接收信號強度向量在空間距離上的大幅浮動，但這些浮動的方向性改變較小，因此引入余弦相似度來衡量PT與PFk的相似性。利用歐氏相似度和余弦相似度對空間距離與角度不同的敏感性，定義基于空間距離和向量方向聯合作用下的多元相似度系數為

(9)

其中，Gk表示PT與PFk的多元相似度，Gk值越大，認為PT與PFk的物理距離越小。附加項ε>0且存在ε→0，避免了分母為0。

在位置計算階段采納多元相似度最高的S個指紋點，其中1≤S≤K，并以此生成具有多元性和時效性的近鄰點集合U={PFU1，PFU2，…，PFUs，…，PFUS}，s=1，2，…，S。由多元相似度確定的近鄰點集合綜合了整體與局部的特征，更加真實地反映出待定位點的物理位置特征。

4.2 近鄰點權重配置

考慮到環境因素對定位的影響較大，僅以Gk作為近鄰點權重的依據無法突出定位場景的個體特征，不同環境下的權值應進行適當調整。引入環境參量v，調節近鄰點對PT位置(x，y)計算的權重占比WFUs，確定具有場景特性的新權重量綱。WFUs可表示為

(10)

參量v與環境相關，需要確定定位場景的最佳環境變量。可針對離線階段得到的指紋庫，取場景中坐標均勻分散的位置，通過與指紋庫的計算匹配，進行離線獲取使定位誤差最小的v作為環境參量取值。

4.3 位置匹配

(11)

其中，WFU表示U中的近鄰點序列的權重，xU和yU分別表示PFU的物理橫坐標和縱坐標。

5 FMKNN流程

論文提出的FMKNN定位算法的步驟流程如圖3所示。離線階段，相比于一般的指紋定位步驟，FMKNN在生成離線指紋庫后增加指紋點聚類過程，建立N個子指紋庫，為在線階段的局部指紋庫模糊匹配做好準備。在線階段設置二次權重分配，是為了進一步加強近鄰點權重，新的權重WFUs使權重配置更符合環境特征。

圖3 FMKNN算法流程圖

6 實驗與結果分析

6.1 測試場景與數據處理

為了評估所提算法的性能，以江南大學物聯網工程學院某會議室為實景測試場地，場地俯視圖為11.5 m×5.5 m的矩形。圖4(a)給出該場地的環境布置以及基站信號源位置與指紋點排布平面圖。場景中布置低功耗藍牙節點作為無線基站 (N=4)，且位置隨機。指紋信息采用網格取點的方式，將矩形定位區域均勻劃分成0.5 m×0.5 m的網格，取網格中心點為指紋點位置，共計生成K=160個指紋點。為了保證待定位點數據兼顧均勻性與隨機性，待定位點的選取是在基于0.8 m×0.8m的網格內隨機選取，共獲得78個備選待定位點。

在待定位點與指紋點數據的采集過程中，為體現算法對設備差異的透明性，對離線與在線階段分別選用平板電腦和智能手機作為數據采集工具。信號采集以2 s為間隔時間，連續采集2 min，構建生成包含60組數據。將采集的接收信號強度以信號熱圖的形式呈現，如圖4(b)所示。

(a) 場景示意圖

(b) 場景信號熱圖

為了驗證實驗場景的接收信號強度數據符合高斯分布，不失一般性，隨機選取k=34時PFk的信號情況進行分析。由圖5所示的PF34處各個基站的采樣信號概率分布圖可見，樣本數據總體趨于高斯分布，符合文中算法的應用條件。面對概率優先的數據處理方法，本實驗場景取p0=7%，可達到濾除偏差數據的目的。經特征提取后得到指紋點接收信號強度向量，與其物理位置共同構建指紋數據庫。

(a) 接收信號強度PA1 (b) 接收信號強度PA2 (c) 接收信號強度PA3 (d) 接收信號強度PA4

6.2 實驗參數配置

6.2.1 模糊參數

模糊參數f影響著局部指紋庫匹配的包容程度，f越大，局部指紋庫匹配的正確率越高；但同時，f增大會提升匹配結果為多子塊的概率，增加計算負擔。因此具體的定位場景可通過實驗確定最佳模糊參數f，在提高DP匹配正確率的同時，盡可能削弱多子庫匹配帶來的指紋點匹配量增大的弊端。

實驗對比了FMKNN在不同f值下，局部指紋庫匹配正確率的變化情況，同時對比了指紋點匹配數量在全局匹配的占比變化。實驗結果如圖6所示，可以看到，當f取9及以上時，局部指紋庫匹配正確率已經可以達到100%，同時需要匹配的指紋點數量僅為全局匹配的38.8%，計算復雜度也有明顯降低。因此，不失一般性，設置本實驗場景的模糊參數f=9。

6.2.2 環境參量

定義平均定位誤差Δ來衡量定位精度：

(12)

其中，Q為測試的待定位點數量。為驗證v對定位精度的正向作用，實驗對比了不同的v取值對Δ的影響。如圖7所示，根據實驗數據擬合，確定v和Δ的函數關系G，從而得出定位場景的最佳環境參量，即

v=G-1[(Δ)min] 。

(13)

由G的曲線變化可以發現，當v>0時，平均定位誤差相比不引入v大幅降低。另一方面，v過大會引發過度調參，導致定位誤差反彈。考慮到v過大或過小都無法達到有效調節權重的目的，以Δ=0.8 m為上限，得到v的經驗取值范圍[2.1，6.4]，同時確定本場景最佳的v=3.2。

圖6 局部指紋庫匹配結果對比

圖7 環境參量與平均定位誤差的關系曲線

6.3 定位誤差的對比分析

考慮到論文提出的FMKNN算法以提升匹配速率為目標，選用同樣具有快速易行的傳統WKNN[6]、增強加權K最近鄰算法(Enhanced Weighted K-Nearest Neighbors，EWKNN)[17]、改進的支持向量回歸算法(Improved Support Vector Regression，ISVR)[11]作為對比，用以測試FMKNN算法的工作性能。圖8顯示了近鄰點數量S對4種算法定位誤差的影響。可以看到總體上隨著近鄰點個數的增加，4種算法的Δ都呈下降趨勢，其中EWKNN和ISVR下降速率較慢，而FMKNN最快。

從最優近鄰點數量下的平均誤差來看，FMKNN相較于其余算法具有最低的誤差值。其中WKNN定位誤差最高，比FMKNN高出0.27 m；同時FMKNN的Δ也比EWKNN和ISVR分別降低0.15 m和 0.13 m，占比20.21%和17.74%，可見FMKNN定位效果良好。但另一方面，也發現當S≤3時，FMKNN的平均定位誤差相對較高，且降低速率較小，原因是近鄰點個數過少，環境參量v的調節作用不大。近鄰點個數較少時，存在權重誤調節的情況，反而使物理距離較遠的近鄰點分配到更大的權重。當S≥9時，過多的權重被分配到離待定位點物理距離較遠的近鄰點上，從而導致4種基于KNN的算法定位誤差開始反彈增長。

6.4 誤差累計概率分析

在應用給定的定位誤差容忍范圍內，通過實驗可確定各定位算法的估算結果滿足該容忍范圍的概率，記為誤差累計概率pΔ。本實驗中給出了在不同的誤差容忍范圍下，WKNN、EWKNN、ISVR和FMKNN定位結果的pΔ對比情況。從圖9可以看出，4種算法的pΔ均隨誤差容忍范圍擴大而升高，最終達到100%。當給定Δ≤0.5 m時，由于允許誤差小于一個單位的指紋點間隔距離，因而4種算法的pΔ相差不大且都較低，此時的誤差水平受到指紋點設定影響。而誤差容忍范圍繼續擴大后，FMKNN的pΔ曲線表現出最快的上升速率。當Δ≤1 m，FMKNN的pΔ已經達到95.4%，可見該場景下FMKNN的平均定位誤差基本能夠控制在2倍指紋點間隔距離以內，具備良好的定位穩定性。而相對上升趨勢最慢的WKNN在Δ≤1 m條件下，pΔ為54.4%，比FMKNN低43%，EWKNN和ISVR的pΔ曲線則始終介于前兩者之間。

通過以上對比得知FMKNN的平均定位誤差集中于小范圍的誤差區間，可見其定位穩定性優于另外三者。此實驗證明FMKNN在處理由環境變化和設備差異帶來的信號波動時具有明顯的優勢，主要原因是多元的相似度計算模型可以更全面地衡量待定位點與指紋點的物理距離，從而更好地抵抗環境噪聲影響。

圖8 近鄰點個數S對平均定位誤差的影響

圖9 目標定位誤差的累計概率對比

7 結束語

論文針對基于K近鄰的算法存在定位精度低，以及大多智能算法計算復雜度高的問題，對指紋定位的各個步驟提出了改善方法。基于模糊參數的局部指紋庫匹配有效減少了定位過程中指紋點的匹配數量，加快了定位效率；新的相似度計算方式，彌補了近鄰點匹配過程中指標單一的不足；最后經過權重再分配機制降低定位誤差。實驗表明，論文提出的算法在定位速度和定位精度兩個方面都優于傳統的全局K近鄰定位算法。