基于局部敏感哈希改進的WKNN室內定位算法

姚永倫，肖佩卿，劉 忱，金仁成

(大連理工大學 遼寧省微納米技術及系統重點實驗室，遼寧 大連 116024)

0 引言

近年來，基于藍牙、射頻、UWB等技術的室內定位技術發展較快，但因其需要額外部署定位設備并未得到廣泛應用。而室內廣泛部署的無線接入點(AP)在為用戶提供上網服務的同時，其形成的覆蓋區域可以為位置指紋提供定位服務[1]。基于WIFI的室內定位技術一般采用指紋法進行定位，選擇接收信號強度(RSSI)作為特征。指紋法一般采用WKNN算法進行指紋庫匹配[2]，WKNN算法理論較為成熟，但當指紋向量特征較大或指紋庫規模較大時，WKNN算法計算量將會增大，實時性差[3]。

為了提高在線定位的實時性，一些學者提出了基于降維的WKNN算法。Liu等[4]提出了基于PCA降維的WKNN算法，但是對于規模較大的指紋庫，該算法依然需要遍歷指紋庫，并不能顯著提高在線定位的實時性。高思遠等[5]對定位場景進行區域劃分，建立二級指紋以提高定位的實時性，但當定位區域較大時，劃分區域工作量較大，且采用二級指紋需要進行二次查找，實時性較差。本文提出一種基于局部敏感哈希(LSH)改進的WKNN算法(LSH-WKNN)，該算法可在保證定位精度的前提下顯著提高定位實時性。

1 室內定位算法

1.1 接收信號強度

接收信號強度(RSSI)隨著接收機與發射機的距離增大而減小，一般采用路徑對數模型進行表示，即：

Pr(d)=Pt(d0)+10nlgd/d0+X.

(1)

其中：Pr(d)為接收機接收到的RSSI，d為歐氏距離；Pt(d0)為距離發射機d0時的RSSI；n為路徑損耗因子，與環境有關；X為噪聲，一般可以忽略。

1.2 WKNN算法

WKNN算法是對K近鄰(KNN)算法的改進。WKNN計算目標指紋與指紋庫內每條指紋的相似度，選取相似度最高的K個參考點，將其坐標進行距離加權平均，得到目標點的估算位置。

指紋相似度一般用歐氏距離表示：

(2)

假如相似度最高的K個參考點集合是R={R1,R2,…,RK}，其對應的位置坐標為：

{(x1,y1),(x2,y2),…,(xK,yK)}.

(3)

WKNN將距離反比對K個參考點位置進行加權平均得到待測點位置：

(4)

1.3 基于LSH改進的WKNN算法

1.3.1 LSH

LSH是一種適用于從大規模數據庫中快速檢索目標數據近似K近鄰的算法，其基本思想為將原始空間的數據通過LSH函數族進行映射后分桶，原始空間中相近的點投影后在同一個桶的概率會比較大。LSH函數一般滿足以下兩個條件：

(1) 如果d(x,y)≤d1,則h(x)=h(y)的概率至少為p1。

(2) 如果d(x,y)≥d2,則h(x)=h(y)的概率至多為p2。

其中，d(x,y)表示x和y之間的距離；d1

滿足上述條件的哈希函數稱為(d1,d2,p1,p2)敏感。滿足(d1,d2,p1,p2)敏感的哈希函數構成了LSH函數族。

LSH包括離線建立索引和在線查找兩步：

(1) 離線階段：首先選取哈希函數將原始空間中的海量數據轉換到漢明空間形成“簽名矩陣”。隨后將“簽名矩陣”中的數據通過滿足(d1,d2,p1,p2)敏感的哈希函數族映射到不同的桶中，形成一張哈希表。可以根據對查找結果準確度及查找時間的要求，通過And和Or操作選擇哈希表的張數。

(2) 在線查找階段：首先通過LSH確定桶號，計算待查詢數據與該桶中數據的相似度，選擇前K個滿足條件的近似最近鄰數據作為結果。

1.3.2 LSH-WKNN

LSH-WKNN算法通過離線建立索引和在線定位兩步完成，離線階段通過LSH生成多張表，作為指紋庫；在線定位階段將查詢數據通過相同的哈希函數映射得到桶號，計算待查詢指紋與該桶中指紋的歐式距離進行升序排序，選擇前K個指紋對應的參考點作為近似K近鄰參考點，最后通過式(4)估算待測點位置坐標。LSH-WKNN算法示意圖如圖1所示。

圖1 LSH-WKNN算法示意圖

2 實驗環境

2.1 實驗場景

實驗在大連理工大學機械工程學院5樓和6樓開展。依據走廊形狀，以4 m為間隔均勻采集參考點，每個參考點采樣10次，共采集參考點254個。參考點地圖如圖2所示。

圖2 參考點地圖

2.2 實驗設備

實驗采用室內本身存在的AP作為RSSI發射裝置，實驗場景內廣泛部署的AP為室內定位提供了豐富的指紋特征。通常情況下，每個位置可以接收到15個～40個AP的RSSI信號。實驗采用Android設備作為RSSI收集裝置，為了提高RSSI收集效率，自主設計了一款基于Android的WIFI掃描工具，采用AP的MAC地址作為標識AP唯一性的特征。

2.3 指紋庫擴增

本文為了模擬具有大規模指紋庫的室內定位場景，將原有指紋庫進行擴增，即在原有指紋庫中增加一些不存在的AP，同時大規模增加模擬參考點，所有AP的RSSI均為-127 dBm。經過模擬擴增，指紋庫共有64 769個參考點、627個AP。

3 實驗結果與分析

為了體現本文算法的優越性，分別采用經典WKNN算法、PCA降維的WKNN算法和基于LSH改進的WKNN算法進行定位，通過定位結果比較定位精度與實時性。三種定位方式的最近鄰點K值均取為4，PCA-WKNN主成分分析后取前100個特征作為主要特征，LSH-WKNN采用E2LSH近鄰搜索算法，設置30個哈希表，取80個特征，表制作好以后每個表約有100個～400個桶。

3.1 定位精度分析

三種定位算法定位結果地圖如圖3所示。整體來看，WKNN算法和PCA-WKNN算法定位誤差概率相當，LSH-WKNN欠佳，甚至出現誤差超過10 m的點。若不考慮LSH-WKNN在10 m以上定位誤差的參考點，三種定位算法的平均定位誤差如下：WKNN算法為1.92 m，PCA-WKNN算法為1.84 m，LSH-WKNN算法為1.97 m。為了更準確地衡量三種定位方式的定位精度，繪制了三種定位算法定位誤差CDF圖，如圖4所示。

圖3 三種定位算法定位結果地圖

圖4 三種定位算法誤差CDF圖

綜上所述，LSH-WKNN定位算法會概率性地出現誤差較大的點，但95%的情況下定位誤差在10 m以內。若不考慮個別定位誤差較大的點，LSH-WKNN整體定位精度與WKNN和PCA-WKNN相當，可以滿足大部分的定位需求。

3.2 定位實時性分析

表1為三種算法運算時間對比。由表1可以看出，WKNN算法和PCA-WKNN算法定位時間分別是LSH-WKNN算法的9.5倍和4.4倍，說明了LSH-WKNN算法在定位實時性方面的優越性。

表1 三種算法運算時間

4 結論

本文提出了一種基于LSH改進的WKNN室內定位算法。在定位精度方面，LSH-WKNN算法定位正確率超過95%，且平均定位誤差為1.97 m，定位精度與WKNN算法和PCA-WKNN算法相當。在定位實時性方面， LSH-WKNN算法表現出巨大的優勢。因此在某些實時性要求較高的大規模指紋庫定位場景下，采用LSH-WKNN算法可以大幅度提高定位實時性。