一種改進(jìn)的組合定權(quán)的指紋定位算法

曹曉祥，陳國良,2

(1. 中國礦業(yè)大學(xué)，江蘇 徐州 221116； 2. 國土環(huán)境與災(zāi)害監(jiān)測國家測繪地理信息局重點(diǎn)實(shí)驗(yàn)室，江蘇 徐州 221116)

當(dāng)前，室外位置服務(wù)隨著全球?qū)Ш叫l(wèi)星系統(tǒng)[1](GNSS)的發(fā)展日趨成熟，然而對于室內(nèi)場景，由于GNSS信號衰減與遮擋，GNSS難以滿足室內(nèi)定位需求，因此，對室內(nèi)定位技術(shù)的研究日益受到重視。

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

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

1 WiFi指紋定位算法原理

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

圖1 WiFi指紋定位原理

當(dāng)前部分基于最近鄰法的WiFi指紋定位算法原理與優(yōu)缺點(diǎn)比較見表1。

表1 不同WiFi指紋定位算法原理與優(yōu)缺點(diǎn)

2 改進(jìn)的基于組合定權(quán)指紋定位算法

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

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

(1)

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

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

(3) 初始鄰近點(diǎn)幾何結(jié)構(gòu)分析。借助式(2)、式(3)分析初始鄰近點(diǎn)的幾何結(jié)構(gòu)，依據(jù)AP發(fā)射的信號傳播規(guī)律，原則上匹配的鄰近點(diǎn)應(yīng)環(huán)繞分布于待定點(diǎn)周圍，以待定點(diǎn)為中心呈放射狀分布，因此可以通過式(3)計算每個鄰近點(diǎn)與初始K個鄰近點(diǎn)中心的距離，剔除偏離鄰近點(diǎn)中心較遠(yuǎn)的點(diǎn)位，其中具體剔除個數(shù)也需借助試驗(yàn)進(jìn)行動態(tài)分析，一般為了保持鄰近點(diǎn)的幾何結(jié)構(gòu)，剔除個數(shù)通常設(shè)置為1～2個，另外初始鄰近點(diǎn)中心利用式(2)進(jìn)行計算。

(2)

(3)

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

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

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

(4)

式中，i=1,2,3,…,K′；pi表示第i個鄰近點(diǎn)對定位結(jié)果影響權(quán)值；K′為鄰近點(diǎn)二次選擇后的個數(shù)。

(6) 加權(quán)均值。利用式(4)求得的權(quán)值及K′個鄰近點(diǎn)坐標(biāo)，依照下式加權(quán)求均值

(5)

3 算法試驗(yàn)及分析

3.1 試驗(yàn)環(huán)境

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

圖2 室內(nèi)指紋點(diǎn)與測試點(diǎn)分布圖

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

圖3 WiFi指紋點(diǎn)采集與定位軟件

3.2 試驗(yàn)結(jié)果與分析

圖4給出某一測試點(diǎn)連續(xù)進(jìn)行60次信號強(qiáng)度采集后，任選其中掃描的4個AP信號強(qiáng)度變化。由圖可以看出，室內(nèi)環(huán)境復(fù)雜多變，引起AP信號強(qiáng)度變化起伏，在利用鄰近點(diǎn)算法時，極易造成鄰近點(diǎn)匹配出現(xiàn)偏差，影響定位結(jié)果。

圖4 某測試點(diǎn)任選4個AP信號強(qiáng)度變化

對30個靜態(tài)測試點(diǎn)進(jìn)行定位計算時，初始匹配鄰近點(diǎn)個數(shù)K設(shè)置為7[7]，對30個點(diǎn)的掃描結(jié)果分別利用KNN算法、WKNN算法及本文改進(jìn)算法進(jìn)行處理，比較定位結(jié)果并進(jìn)行分析。

表2是對初始鄰近點(diǎn)K值取值進(jìn)行試驗(yàn)分析的結(jié)果,分別對K=3,4,5,…,8的定位效果進(jìn)行統(tǒng)計。結(jié)果表明，當(dāng)K=5時,誤差小于3 m的概率達(dá)到94.4%,因此,試驗(yàn)中設(shè)計初始鄰近點(diǎn)個數(shù)為7個,設(shè)計鄰近點(diǎn)二次選擇中剔除個數(shù)為2。

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

表2 初始鄰近點(diǎn)個數(shù)K值定位誤差概率統(tǒng)計 (%)

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

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

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

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

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

表3 定位誤差對比 m

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

4 結(jié) 語

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

[1] 寧津生，姚宜斌，張小紅.全球?qū)Ш叫l(wèi)星系統(tǒng)發(fā)展綜述[J].導(dǎo)航定位學(xué)報,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] 劉少偉，花向紅，邱衛(wèi)寧，等．WiFi指紋定位中AP個數(shù)對定位精度的影響[J].測繪工程,2017,26(2)：33-36．

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

[9] 畢京學(xué)，甄杰，汪云甲,等.高斯函數(shù)定權(quán)的改進(jìn)KNN室內(nèi)定位方法[J].測繪通報，2017(6)：9-12.

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

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

[12] 劉春燕，王堅.基于幾何聚類指紋庫的約束KNN室內(nèi)定位模型[J].武漢大學(xué)學(xué)報(信息科學(xué)版)，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.