WiFi指紋定位中改進的加權k近鄰算法

王博遠，劉學林，蔚保國，賈瑞才，甘興利，黃 璐

(1.哈爾濱工程大學 信息與通信工程學院，黑龍江 哈爾濱 150001；2.中國電子科技集團公司第五十四研究所，河北 石家莊 050081；3.衛星導航系統與裝備技術國家重點實驗室，河北 石家莊 050081)

由于室內環境中衛星導航信號的可用性無法得到保證，全球導航衛星系統在室內定位領域的應用受到限制[1]，因此建立一套準確可靠的室內定位系統以滿足室內位置服務的需求非常重要。隨著智能手機的快速發展，WiFi信號接收模塊已內置于智能手機中，同時在一些公共場所，如辦公樓、車站、商場等，無線局域網也已經實現了廣泛的覆蓋，WiFi信號指紋定位已成為目前最流行的室內定位方案之一。WiFi指紋定位可大體分為離線階段和在線階段。在離線階段，工作人員在實際場地采集WiFi指紋，包括每個參考點的位置坐標及每個參考點處的接收信號強度值。每一對接收信號強度值和位置坐標確定了一個獨一無二的參考點，并按照一定的數據格式存入指紋數據庫中[2]。在在線階段，用戶在接收端獲得當前位置的信號強度，通過搜索指紋庫找到與信號強度讀數最匹配的幾個參考點，將匹配到的參考點坐標進行平均或者加權平均，估計出用戶當前的位置坐標。

現存的WiFi指紋定位方法大都采用確定性方法，包括最近鄰算法，k近鄰算法和加權k近鄰算法。微軟公司設計的RADAR系統[3]是較早使用WiFi指紋定位的室內定位系統，其利用k近鄰算法使得系統可以滿足房間級別的定位精度。為了提高WiFi指紋定位系統的定位精度和系統穩定性，研究人員提出了許多WiFi指紋定位算法。文獻[4]針對定位系統因多路徑效應等因素所導致定位精度降低的問題，提出了一種基于到達時差的混合定位算法。文獻[5]根據位置距離使用相似性傳播聚類對最近鄰參考點進行聚類。通過比較聚類中心和在線接收信號強度讀數之間的信號距離以及參考點的數目，保留可能性最大的參考點類別，然后使用加權k近鄰算法估計用戶位置。文獻[6]通過對室內環境的分析，利用信號傳播損耗模型建立了似然函數模型，運用馬爾可夫蒙特卡羅算法對似然函數中的位置坐標進行了估計，具有快速收斂和高精度的優勢。文獻[7]采用k均值算法把在每個參考點處來自每個無線接入點的一組信號作為一個類進行計算，將不屬于該類的數據剔除掉，從而提高了WiFi指紋數據庫的質量。文獻[8]指出在WiFi指紋定位中小的接收信號強度值具有和大的接收信號強度值同等的意義，以用來表示與無線接入點距離的不同，因此不應該簡單地將數值小的接收信號強度舍掉。文獻[9]設計了3種不同加權距離的k近鄰算法，發現基于曼哈頓距離的k近鄰算法性能最好。文獻[10]通過實驗證明，傳統的加權k近鄰算法將參考點接收信號強度與測試點接收信號強度差值的倒數作為參考點的權值進行加權平均，這并不符合WiFi信號具有不均勻空間分辨率的特性，因而降低了定位精度。根據上述提到的方法可知，現存的基于最近鄰機制的定位方法大都利用不同點間的信號距離來判斷相互之間的物理距離，并將其作為指紋匹配和位置估計的依據。然而，由于室內環境會受到反射、折射以及多徑效應的影響，WiFi信號具有很強的波動性，這將給信號距離的計算帶來誤差。同時根據WiFi信號的損耗模型可知，接收信號強度的變化值與傳播距離呈對數關系，即兩者的關系是非線性的[11]。因此，為了解決WiFi指紋定位系統中由于WiFi信號的波動性和衰減特性導致傳統的信號距離不能很好地反映物理距離的問題，筆者提出了一種改進的加權k近鄰算法。將WiFi信號的波動性以及接收信號強度與物理距離的非線性關系引入到信號距離的計算中，給不同的信號強度差值分配不同的加權系數，使用信號的加權歐氏距離作為加權k近鄰算法的距離度量，提高傳統的加權k近鄰算法的定位精度。

1 指紋數據庫構建

(1)

(2)

表1 指紋庫數據格式

2 改進的WiFi指紋定位算法

根據室內WiFi信號的波動性、接收信號強度與物理距離的非線性關系，使用信號加權歐氏距離作為加權k近鄰定位算法的距離度量，提出了一種改進的加權k近鄰算法。現存的加權k近鄰算法大多利用參考點和測試點之間的信號歐氏距離來判定其間的物理距離di,可表示為

(3)

(4)

(5)

經典信號對數損耗模型[12]可表示為

PL(d)=PL(d0)-10ηlg(d/d0)+χσ,

(6)

其中，PL(d)表示距離無線接入點為d處的信號強度值；d0為參考距離，一般設為1 m；PL(d0)為參考距離處的信號強度值；η為路徑損耗指數；χσ代表標準差為σ的高斯隨機變量。

圖1 接收信號強度與物理距離的關系示意圖

理想WiFi信號環境下的信號損耗曲線如圖1所示，其中d0=1 m，PL(d0)=-31.7 dBm，路徑損耗指數η=2.76[13]。如式(3)所示，現存的信號歐氏距離只考慮了信號強度差值。然而從圖1可以看出，信號強度差值與物理距離關系是非線性的，隨著離無線接入點的距離的增加，信號衰減速度變慢，相同大小的信號強度差值也可以代表不同的物理距離。因此要想使信號距離更準確地反映物理距離，不僅要考慮信號強度的差值，還要考慮每一對位置點信號強度值的總體大小。因此，文中設計了一種加權歐氏距離，通過給不同的信號強度差值分配不同的權值來平衡信號距離和物理距離之間的差異，計算如下：

(7)

(8)

(9)

根據測試點與所有參考點的信號加權歐氏距離的大小，選出距離最小的k個參考點作為最近鄰參考點估計用戶的位置：

(10)

(11)

其中，(X,Y)為估計的位置坐標，(Xi,Yi)為第i個參考點位置坐標，ωi為第i個參考點位置坐標的權重。相比于現存的加權k近鄰算法，使用加權歐氏距離選出的最近鄰參考點以及參考點的坐標權重更加合理，可以大大提高定位精度。

為了確定提出的算法滿足實時定位需求，可計算算法的時間復雜度：

(1)計算測試點與N個參考點的信號強度平均值以及來自不同無線接入點的信號強度差值的加權系數，時間復雜度為O(N+NM)，即O(NM)。

(2)計算測試點與N個參考點的加權歐氏距離，時間復雜度為O(N)。

(3)對所有加權歐氏距離排序，時間復雜度為O(NlbN)。

(4)計算k個最近鄰參考點的坐標權重以及對最近鄰參考點坐標進行加權平均，時間復雜度為O(k)。

傳統的加權k近鄰算法的時間復雜度為O(NlbN)+O(k)。因此，只有當M>lbN時，所提出算法的時間復雜度O(NM)+O(k)才會大于傳統的加權k近鄰算法的，但仍可以滿足實時定位的需求。在其他情況下，文中所提出的算法的時間復雜度為O(NlbN)+O(k)，與傳統算法處于同一個量級。

此外，為了更直觀地說明所提出的加權歐氏距離的優勢，筆者基于仿真數據對比了改進的加權k近鄰算法與傳統的加權k近鄰算法。考慮一維坐標系中的2個無線接入點、2個參考點和5個測試點，根據式(6)的信號對數損耗模型，可以得到不同距離處的各點接收信號強度值，模型參數設置與圖1相同。表2列舉了5個測試點與2個參考點間的信號歐氏距離和信號加權歐氏距離，以及每個測試點與2個參考點的兩種信號距離的比值。可以看出，相比于傳統的信號歐氏距離，測試點與兩個參考點的信號加權歐氏距離的比值更接近于相應的物理距離的比值。這說明加權歐氏距離更能反映位置點間的物理距離，因此在尋找最近參考點以及計算不同參考點的坐標權重的過程中，其定位性能優于傳統的加權k近鄰算法的。

表2 基于仿真數據的測試點與參考點間信號歐氏距離和信號加權歐氏距離

3 實驗結果及評估

3.1 實驗環境及實驗設置

圖2 WiFi指紋定位實驗環境

為了驗證文中提出的定位方法性能，在某實驗樓2樓進行WiFi指紋室內定位實驗。如圖2所示，實驗場地內共布置7個無線接入點，200個參考點和50個測試點，相鄰參考點的距離為1.2 m。實驗設備為小米MIX 2智能手機，WiFi信號采樣頻率為1 Hz。每個測試點處采集接收信號強度數據的時間為60 s，并取其平均值作為在線接收信號強度量測值。

3.2 實驗結果分析

為了驗證WiFi信號的衰減特性，筆者采集了所有無線接入點在不同距離處的信號強度值，每個距離處采集時間為60 s，平均后的信號強度值如圖3所示。

圖3 無線接入點1～3在不同距離處的信號強度值

圖4 無線接入點4～7在不同距離處的信號強度值

從圖3和圖4可以看出，由于在室內環境中WiFi信號受到反射、折射、繞射以及多徑效應的影響，實測的接收信號強度值呈現出波動性，但仍然可以很好地逼近WiFi信號損耗模型曲線，即隨著距離無線接入點距離的增加，信號衰減速率變慢。這證明了筆者提出的信號加權歐氏距離能夠適用于真實的定位場景。

為了更直觀地展示改進的加權k近鄰算法在搜索最近鄰參考點和位置加權估計的優勢，隨機選擇了5個參考點，比較了改進的加權k近鄰算法和基于歐氏距離的加權k近鄰算法的最近鄰參考點選擇以及定位誤差。表3根據參考點與測試點信號距離由小到大的順序，列舉了前4個最近鄰參考點以及相應的歸一化物理距離。可以看出，對于基于歐氏距離的加權k近鄰算法所選擇的最近鄰參考點，其與測試點的物理距離排序與信號歐氏距離的排序并不一致。而對于改進的加權k近鄰算法所選擇的最近鄰參考點，其與測試點的物理距離排序與信號加權歐氏距離的排序基本一致。話句話說，信號加權距離越小代表物理距離也就越小。因此，使用加權歐氏距離可以提高指紋匹配的準確度，賦予最近鄰參考點坐標更合理的權重，可提高位置估計的精度。

表3 兩種加權k近鄰算法的最近鄰參考點選擇和定位誤差

為了驗證所提出的算法能夠顯著提高定位精度，比較了3種基于不同距離度量的加權k近鄰算法的定位誤差：基于歐氏距離的加權k近鄰算法、基于曼哈頓距離的加權k近鄰算法和文中提出的基于加權歐氏距離的改進的加權k近鄰算法。3種算法在選取不同數量的最近鄰參考點下的平均定位誤差如圖5所示，選取的最近鄰參考點個數等于4時的定位誤差累計概率分布如圖6所示。可以看出，所提出的改進的加權k近鄰算法的定位誤差明顯小于其他兩種算法的。

圖5 不同最近鄰參考點個數下的平均定位誤差

圖6 最近鄰參考點個數為4時定位誤差累計概率分布

表4改進的加權k近鄰算法和傳統的加權k近鄰算法的定位誤差統計m

方法50%定位誤差75%定位誤差平均定位誤差均方根定位誤差改進的加權k近鄰算法1.352.481.821.51基于歐氏距離的加權k近鄰算法1.762.912.291.95基于曼哈頓距離的加權k近鄰算法1.813.692.612.14

從表4列出的定位誤差統計值中可以得出同樣的結論，即相比于傳統的基于歐氏距離和曼哈頓距離的加權k近鄰算法，所提出的改進的加權k近鄰算法具有更小的定位誤差。相比于基于歐氏距離的算法，其平均定位誤差提升了20.5%，均方根誤差提升了22.6%。相比于基于曼哈頓距離的算法，其平均定位誤差提升了30.3%，均方根誤差提升了29.4%。

4 結束語

筆者通過分析室內WiFi信號的波動性,在信號距離計算中引入了接收信號強度方差，并根據WiFi信號的衰減特性給不同的接收信號強度差值分配權值，提出了一種改進的加權k近鄰算法。實驗結果表明，所提出的信號加權歐氏距離能夠更準確地反映各位置點間的物理距離，提高了指紋匹配的準確度和定位精度。改進的加權k近鄰算法的平均定位誤差可達1.82 m，相比于傳統的基于歐氏距離和曼哈頓距離的加權k近鄰算法，其平均定位誤差分別約提升了20.5%和30.3%，能夠滿足用戶在室內的高精度定位需求。