一種改進的組合定權的指紋定位算法

曹曉祥，陳國良,2

(1. 中國礦業大學，江蘇 徐州 221116； 2. 國土環境與災害監測國家測繪地理信息局重點實驗室，江蘇 徐州 221116)

當前，室外位置服務隨著全球導航衛星系統[1](GNSS)的發展日趨成熟，然而對于室內場景，由于GNSS信號衰減與遮擋，GNSS難以滿足室內定位需求，因此，對室內定位技術的研究日益受到重視。

許多國內外研究機構、學者基于藍牙[2]、地磁[3]、射頻識別、超寬帶[4]、WLAN、計算機視覺[5]和可見光通信[6]等技術在室內定位技術研究上取得諸多成果。這其中WiFi定位技術由于成本低、定位結果可靠，成為研究熱點。WiFi定位技術主要包括特殊AP點定位、信號傳播模型法、信號指紋定位法。而其中信號指紋定位法由于具有較高的定位精度而被廣大學者所關注，大多數在算法簡單、易于實現的基于信號空間K最鄰近法的WiFi指紋定位算法上進行研究。如劉少偉[7]研究了鄰近點K值選取對指紋定位精度的影響；吳赟等[8]利用點位間信號強度余弦相似度作為匹配特性并以此對鄰近點進行定權求解坐標，有效解決了終端差異性問題；畢京學等[9]考慮到歐氏距離較小或為0的情況，提出了基于高斯函數定權的KNN室內定位算法；陳國良等[10]通過引入聚類分析方法，對指紋點進行分類預處理，極大地縮短了定位時間；王培重等[11]利用點位間AP的MAC匹配度，提出了一種動態設定K值的定位算法；劉春燕等[12]提出了針對信號不穩定的以幾何信息改進基于指紋庫的KNN(信號空間K最近鄰算法)定位算法。

但是，諸多算法[13-15]均面臨同樣一個問題：室內WiFi信號的不穩定性，可能會使鄰近點匹配出現偏差，一旦匹配出現偏差，將直接影響定位結果，同時也忽視了對鄰近點的分布結構的分析，理論上鄰近點中心與待定點幾何位置具有相關關系。本文就此提出一種改進的組合定權的指紋定位算法，在鄰近點匹配結束后，對鄰近點幾何結構進行分析，剔除偏離鄰近點中心較遠的點后，再利用選擇后的鄰近點與其中心點的幾何距離、待定點與指紋點歐氏距離組合定權,加權求取坐標，以提高定位精度。

1 WiFi指紋定位算法原理

WiFi指紋定位分為離線指紋點采集和在線定位兩個階段。其中，離線指紋點采集主要工作是采集設計的指紋點處接入點的RSSI信號特征值，通過采集大量指紋點數據構建指紋數據庫，其中指紋數據庫包含有指紋點位置與該點RSSI序列的映射關系；在線定位階段將未知點采集的RSSI序列與指紋庫中指紋點存儲的數據進行匹配，借助相關定位算法，解算得到未知點的位置坐標。其具體內容如圖1所示。

圖1 WiFi指紋定位原理

當前部分基于最近鄰法的WiFi指紋定位算法原理與優缺點比較見表1。

表1 不同WiFi指紋定位算法原理與優缺點

2 改進的基于組合定權指紋定位算法

本文提出的基于鄰近點二次選擇的指紋定位算法是對WKNN定位算法的改進，對依據待定點與指紋點歐氏距離匹配得到的K鄰近點的幾何結構進行分析，剔除其中偏離鄰近點中心較遠的點位后，再將待定點與鄰近點歐氏距離、鄰近點與K個鄰近點中心距離倒數組合，利用WKNN算法中定權方法，使用兩個距離倒數之和加權，計算定位結果。具體包括以下幾個步驟：

(1) 歐氏距離計算。首先將定位終端掃描的待定點的AP信號強度值與指紋庫中每個指紋點的存儲數據進行歐氏距離計算，利用歐氏距離確定待定點與指紋點匹配程度，其中歐氏距離計算公式為

(1)

式中，i=1,2,…,n；di表示待定點與指紋庫中第i個指紋點之間的歐氏距離；n1表示待定點掃描的AP中與第i個指紋點存儲的AP相同的個數；RSSIj為待定點掃描到的第j個AP的信號強度；RSSIij為第i個指紋點掃描到的第j個指紋點的信號強度值；n表示指紋庫中指紋點的個數。

(2) 初始鄰近點選擇。各個指紋點與待定點歐氏距離計算完成后，對距離序列進行排序，得到K個與待定點距離最近的指紋點，即初始K個鄰近點。其中K值設定借助試驗手段，判斷最優K值的選取，一般在單個房間內，K取值為5～8個，或動態地對K值進行判斷，選取最優K值。

(3) 初始鄰近點幾何結構分析。借助式(2)、式(3)分析初始鄰近點的幾何結構，依據AP發射的信號傳播規律，原則上匹配的鄰近點應環繞分布于待定點周圍，以待定點為中心呈放射狀分布，因此可以通過式(3)計算每個鄰近點與初始K個鄰近點中心的距離，剔除偏離鄰近點中心較遠的點位，其中具體剔除個數也需借助試驗進行動態分析，一般為了保持鄰近點的幾何結構，剔除個數通常設置為1～2個，另外初始鄰近點中心利用式(2)進行計算。

(2)

(3)

式中，xcenter,ycenter,zcenter、(xi,yi,zi)分別表示初始鄰近點的中心點坐標和第i個鄰近點的坐標；lic表示第i個鄰近點與初始鄰近點中心的幾何距離。

(4) 初始鄰近點二次選擇。各個鄰近點與中心點距離計算完成后，對距離序列進行排序，得到K′個與中心點距離最近的鄰近點，K′值的確定由初始鄰近點個數K和鄰近點剔除個數共同決定。

(5) 距離組合定權。由無線信號傳播規律可知，鄰近點與待定點的歐氏距離越小，鄰近點幾何位置與待定點的幾何位置關系越大；同樣，二次選擇后鄰近點理論上環繞分布于待定點四周，二次選擇后鄰近點中心理論上近似與待定點重合。因此，鄰近點到中心點的距離在一定程度上反映了其對待定點位置的影響，該鄰近點距離鄰近點中心越小，其對待定點幾何位置影響越大。因此，可結合以上兩種距離對待定點位置的影響規律進行組合定權。具體定權方式為

(4)

式中，i=1,2,3,…,K′；pi表示第i個鄰近點對定位結果影響權值；K′為鄰近點二次選擇后的個數。

(6) 加權均值。利用式(4)求得的權值及K′個鄰近點坐標，依照下式加權求均值

(5)

3 算法試驗及分析

3.1 試驗環境

試驗場設置在中國礦業大學環境與測繪學院樓四樓A409，其中測試樓道與房間均布設有所需AP，在7 m×9 m房間按1.2 m×1.2 m(由于室內有辦公桌椅，并不是嚴格按照1.2 m間隔取點)格網均勻布置36個參考點，如圖2所示。

圖2 室內指紋點與測試點分布圖

離線指紋點采集階段，利用自主開發的WiFi指紋點采集與定位軟件進行數據采集與定位工作，采集定位界面如圖3所示。每個指紋點間隔6 s采集AP信號強度，采集10次，取平均值存入指紋庫。如圖2所示，在測試房間內選取37個測試點進行靜態測試，并建立相對坐標系，用于點位誤差檢核。

圖3 WiFi指紋點采集與定位軟件

3.2 試驗結果與分析

圖4給出某一測試點連續進行60次信號強度采集后，任選其中掃描的4個AP信號強度變化。由圖可以看出，室內環境復雜多變，引起AP信號強度變化起伏，在利用鄰近點算法時，極易造成鄰近點匹配出現偏差，影響定位結果。

圖4 某測試點任選4個AP信號強度變化

對30個靜態測試點進行定位計算時，初始匹配鄰近點個數K設置為7[7]，對30個點的掃描結果分別利用KNN算法、WKNN算法及本文改進算法進行處理，比較定位結果并進行分析。

表2是對初始鄰近點K值取值進行試驗分析的結果,分別對K=3,4,5,…,8的定位效果進行統計。結果表明，當K=5時,誤差小于3 m的概率達到94.4%,因此,試驗中設計初始鄰近點個數為7個,設計鄰近點二次選擇中剔除個數為2。

圖5分別從37個測試點中隨機選取23個點，對每個點位利用WKNN算法和本文改進算法得到的定位結果在X軸、Y軸上的誤差進行描述，可以看出，不論是X軸，還是Y軸上的定位誤差，本文改進算法的誤差均小于WKNN算法產生的誤差(由于人員走動頻繁，個別點位結果較差)。圖6則是對兩種算法點位誤差進行描述，同樣，本文改進算法定位效果均優于WKNN算法。

表2 初始鄰近點個數K值定位誤差概率統計 (%)

圖5 WKNN算法與本文改進算法在X、Y軸方向上的誤差比較(任選23個測試點)

圖6 WKNN算法與本文改進算法點位誤差比較(任選23個測試點)

從圖7可以看出，本文改進算法定位精度優于3 m的概率達到94.6%；另外，WKNN算法和本文改進算法定位精度優于1 m的概率分別為45.9%和56.8%。

圖7 定位誤差累積概率分布

從表3可以看出，KNN算法、WKNN算法和本文改進算法誤差最大值均高于5.3 m，該測試點位于房間邊緣，且桌椅遮擋嚴重，從而導致較大誤差。從定位誤差均值來看，本文改進算法的定位誤差較小，定位效果要優于KNN算法和WKNN算法。

表3 定位誤差對比 m

由以上可知，本文改進的基于鄰近點二次選擇算法相較于KNN算法和WKNN算法雖然增加了部分計算量，但是其定位效果和定位穩定性均有提升。

4 結 語

本文改進的幾何距離與歐氏距離組合定權的指紋定位算法是在WKNN基礎上，對利用指紋點與待定點歐氏距離匹配得到的K個鄰近點幾何結構進行分析，剔除鄰近點中偏離鄰近點中心較遠的點位，得到K′個鄰近點后，再將待定點與鄰近點歐氏距離、鄰近點與K個鄰近點中心距離倒數組合，利用WKNN算法中定權方法，使用兩個距離倒數之和加權求均值。與KNN算法和WKNN算法相比，本文改進算法避免在定位計算中使用匹配出現偏差的點位，提升了定位穩定性和精度。指紋庫幾何位置邊緣定位誤差還需進一步研究。

[1] 寧津生，姚宜斌，張小紅.全球導航衛星系統發展綜述[J].導航定位學報,2013,1(1)：3-8.

[2] ZHOU S，POLLARD J K.Position Measurement Using Bluetooth[J].IEEE Transactions on Consumer Electronics，2006，52(2):555-558.

[3] INDOORATLAS.Ambient Magnetic Field-based Indoor Location Technology:Bringing the Compass to the Next Level[EB/OL].2017-09-08.www.doc88.com/p-1187544632856.html.

[4] ZAPATER A，KYAMAKYA K.A UWB-based Indoor Positioning Concept: Problem Formulation，System Design and Feasibility Analysis[C]∥International Conference on Wireless Networks.Las Vegas：[s.n.]，2003:114-118.

[5] YAN L，XU Z.Quality Analysis of Vehicle-based Sequence Images Relative Orientation Based on Computer Vision[J].ISPRS-International Archives of the Photogrammetry，Remote Sensing and Spatial Information Sciences，2012(XXXIX-B3):443-446.

[6] YOSHINO M,HARUYAMA S,NAKAGAWA M.High-accuracy Positioning System Using Visible LED Lights and Image Sensor[C]∥2008 IEEE Radio and Wireless Symposium.Orlando：IEEE，2008:439-442.

[7] 劉少偉，花向紅，邱衛寧，等．WiFi指紋定位中AP個數對定位精度的影響[J].測繪工程,2017,26(2)：33-36．

[8] 吳赟，蔣新華，齊雁飛，等.基于加權余弦相似度的WiFi指紋室內定位[J].上海師范大學學報(自然科學版)，2017,46(1)：124-128.

[9] 畢京學，甄杰，汪云甲,等.高斯函數定權的改進KNN室內定位方法[J].測繪通報，2017(6)：9-12.

[10] 陳國良，張言哲，汪云甲，等．WiFi-PDR室內組合定位的無跡卡爾曼濾波算法[J].測繪學報，2015，44(12):1314-1321．

[11] 王培重，鄭南山，張言哲．基于動態K值及AP MAC地址篩選的室內定位算法[J].計算機科學，2016，43(1):163-165．

[12] 劉春燕，王堅.基于幾何聚類指紋庫的約束KNN室內定位模型[J].武漢大學學報(信息科學版)，2014，39(11)：1287-1292.

[13] GE X，QU Z.Optimization WiFi Indoor Positioning KNN Algorithm Location-based Fingerprint[C]∥2016 7th IEEE International Conference on Software Engineering and Service Science.Beijing:IEEE，2016.

[14] LI D，ZHANG B，LI C.A Feature-scaling-based S|kS|-Nearest Neighbor Algorithm for Indoor Positioning Systems[J].IEEE Internet of Things Journal，2016，3(4):590-597.

[15] LU X，QIU Y，YUAN W，et al.An Improved Dynamic Prediction Fingerprint Localization Algorithm Based on KNN[C]∥2016 Sixth International Conference on Instrumentation & Measurement，Computer，Communication and Control.Harbin：IEEE，2016.