仲 臣，余學(xué)祥，邰曉曼，肖星星，韓雨辰，劉清華

基于AP加權(quán)的自適應(yīng)動態(tài)室內(nèi)定位方法

仲 臣1,2,3，余學(xué)祥1,2,3，邰曉曼1,2,3，肖星星1,2,3，韓雨辰1,2,3，劉清華1,2,3

（1. 安徽理工大學(xué) 空間信息與測繪工程學(xué)院,安徽 淮南 232001；2. 安徽理工大學(xué) 礦山采動災(zāi)害空天地協(xié)同監(jiān)測與預(yù)警安徽普通高校重點實驗室,安徽 淮南 232001；3. 安徽理工大學(xué) 礦區(qū)環(huán)境與災(zāi)害協(xié)同監(jiān)測煤炭行業(yè)工程研究中心,安徽 淮南 232001）

針對傳統(tǒng)定位算法存在大量不同接入點（AP）的冗余信息，且在定位范圍較大時定位時效性差的問題，提出一種基于卡方距離的AP加權(quán)自適應(yīng)動態(tài)定位算法。指紋匹配階段利用卡方距離代替?zhèn)鹘y(tǒng)加權(quán)近鄰算法（WKNN）中的歐式距離，用AP方差對相似度進行加權(quán)，從而自適應(yīng)調(diào)整距離閾值，并引入動態(tài)值，精確提取數(shù)據(jù)庫信息。實驗結(jié)果表明，與傳統(tǒng)定位算法相比，該算法更有利于去掉冗余的AP，使定位誤差范圍縮小，可顯著提高定位精度與穩(wěn)定性。

室內(nèi)定位；自適應(yīng)加權(quán)近鄰；指紋匹配；定位精度

0 引言

隨著科學(xué)技術(shù)的高速發(fā)展，衛(wèi)星定位系統(tǒng)在室外導(dǎo)航應(yīng)用上極其廣泛，定位精度已經(jīng)達到毫米級，但在大型建筑中進行室內(nèi)定位，其精度仍不滿足要求。為了追求更加高效、智能的生活方式，基于位置服務(wù)（location based services, LBS）的室內(nèi)定位技術(shù)正展現(xiàn)著廣泛的應(yīng)用前景。室內(nèi)定位技術(shù)主要包括藍牙、地磁、射頻識別、無線保真（wireless fidelity,WiFi）定位、慣性導(dǎo)航、超寬帶、超聲波等方法。WiFi室內(nèi)定位憑借著精度相對較高、WiFi接入點部署簡單和成本低等特點成為目前研究熱點。

文獻[1]提出基于數(shù)據(jù)庫擴充的-均值（-means）聚類結(jié)合加權(quán)近鄰（weighted-nearest neighborhood，WKNN）算法，解決了WiFi信號波動大和抗干擾能力差的問題。文獻[2]針對環(huán)境易變性引起的WiFi信號不穩(wěn)定性，在數(shù)據(jù)庫中添加接收信號強度（received signal strength，RSS）均值和二階矩陣，提出一種基于中心距加權(quán)改進的WKNN匹配算法。文獻[3]利用最小值動態(tài)補償處理RSS的室內(nèi)定位方法，提高了WKNN算法的定位精度和穩(wěn)定性。文獻[4]在原始近鄰（-nearest neighborhood，KNN）基礎(chǔ)上，融合樸素貝葉斯概率算法，對指紋庫匹配定位誤差大、穩(wěn)定性差做出了改進。對于經(jīng)典歐氏距離僅考慮到各RSS之間的絕對距離，忽略了相對距離的影響，文獻[5]提出一種基于卡方距離賦予各接入點（access point, AP）權(quán)重的室內(nèi)定位算法；文獻[6]將自適應(yīng)修正曼哈頓距離代替歐氏距離作為相似性距離，再利用AP選擇算法，采用干擾程度小且出現(xiàn)頻率高的AP下的RSS，使定位結(jié)果更穩(wěn)定。在傳統(tǒng)近鄰KNN算法中，使用偏差大的參考點匹配鄰近點導(dǎo)致待測點誤差大，文獻[7]通過鄰近點的幾何結(jié)構(gòu)去除幾何中心較遠參考點，提出改進的組合定權(quán)室內(nèi)定位算法。

由上述學(xué)者對于指紋數(shù)據(jù)庫的研究可知，目標區(qū)域WiFi信號波動及來自不同AP的RSS值穩(wěn)定性差別引起的定位誤差依然需要深入研究。因此，為更好地描述參考點與待測點的相似度、實現(xiàn)加權(quán)近鄰算法無需再調(diào)試值，本文提出一種自適應(yīng)動態(tài)值A(chǔ)P加權(quán)定位算法。通過實驗驗證，本文算法有效提高了定位精度和待測點的預(yù)測能力，可完成自適應(yīng)調(diào)整值。

1 WiFi指紋庫匹配定位技術(shù)

在指紋庫匹配研究方向中，以指紋向量相似度匹配研究為主，算法包括多種改進近鄰算法、反向傳播（back propagation, BP）神經(jīng)網(wǎng)絡(luò)、高斯過程回歸模型、概率分布、支持向量機等，因近鄰定位算法運算速度快、精度較高，眾多學(xué)者一直以此為研究熱點。

1.1 加權(quán)K近鄰算法

加權(quán)近鄰算法是由最近鄰定位算法到近算法一步步演變來的，一般以歐氏距離作為RSS向量間相似度的比較，決定指紋庫匹配點的位置[8]。加權(quán)近鄰算法已基本滿足室內(nèi)定位精度要求，但仍然存在技術(shù)問題。就相似度表示而言，WKNN算法中使用歐氏距離，僅考慮了參考點與待測點RSS值之間的絕對距離，忽略了RSS向量之間的相對距離；就AP權(quán)重分配而言，不同AP之間的穩(wěn)定性不同，使得不同AP下的RSS信號準確度不同，最終導(dǎo)致會因AP不同造成的誤差；就值而言，值不同，定位精度也不同，需進行多次調(diào)試才能尋找到最佳值。因此，在已有的研究基礎(chǔ)上，仍能改進WKNN算法，減小誤差提高室內(nèi)定位精度。

1.2 基于AP加權(quán)的自適應(yīng)動態(tài)WKNN

針對WKNN算法存在的問題，本文提出基于AP加權(quán)的自適應(yīng)動態(tài)WKNN算法。由于使用不同的距離表示相似度，會對參考點分類有所影響。相對于歐氏距離，卡方距離并不是絕對距離，它表示向量間的相對距離，對向量間的特性差值和向量中特征值相對于距離的變化有較好的說明，能有效反映參考點與待測點的實際位置。本文選取卡方距離代替歐氏距離，可明顯發(fā)現(xiàn)參考點與待測點的相似度。相似度可表示為

在指紋數(shù)據(jù)庫匹配定位中，每個AP具有不同的穩(wěn)定性，穩(wěn)定性高的AP對于待測點位置坐標的預(yù)測影響大。因此，將穩(wěn)定性高的AP賦予數(shù)值大的權(quán)值，反之，賦予數(shù)值小的權(quán)值[9]。對同一點多次采集RSS值，通過計算不同AP的方差來表示每個AP的穩(wěn)定性，方差小的AP穩(wěn)定性高，方差大的AP穩(wěn)定性低。AP采集RSS的方差的計算公式為

由AP加權(quán)后的卡方距離計算坐標權(quán)值ω為

基于AP加權(quán)的自適應(yīng)動態(tài)室內(nèi)定位算法實現(xiàn)如圖1所示。通過計算點與點之間的卡方距離與方差，確定權(quán)值及相似度，由排序確定閾值，獲取自適應(yīng)動態(tài)值，提取數(shù)據(jù)庫相應(yīng)坐標，計算待測點位置。

圖1 定位流程

2 實驗與結(jié)果分析

2.1 實驗環(huán)境與方法

構(gòu)建算法后需進行實驗驗證算法精度，選取安徽理工大學(xué)空間信息與測繪工程學(xué)院如圖2所示的一間長為11 m、寬為11 m教室作為實驗區(qū)域，并將其劃分為1 m×1 m組成的格網(wǎng)進行數(shù)據(jù)采集，圖1中黑色圓點為AP位置。

圖2 實驗區(qū)域

筆記本電腦作為信號接收器，實測指紋數(shù)據(jù)信息為4個AP的RSS值組成的向量，將實測指紋信息存儲進數(shù)據(jù)庫，采用5折交叉驗證[10]，保證定位結(jié)果的準確性。在網(wǎng)格交點處采集數(shù)據(jù)，隨機選取實測數(shù)據(jù)作為待測點，設(shè)置18個待測點和72個參考點，18個待測點即為驗證集，占所有數(shù)據(jù)的20%，可避免隨機誤差影響定位精度的準確性，記錄所有點位的位置坐標。選擇網(wǎng)格內(nèi)中間任意一點位采集100次數(shù)據(jù)，計算4個AP的方差，以此作為每個AP的穩(wěn)定性。利用上述自適應(yīng)動態(tài)值原理，計算基于卡方距離的AP方差加權(quán)后的相似度值，得到待測點的位置坐標[11-12]。

2.2 實驗結(jié)果分析

為驗證本文算法定位精度，分別利用基于卡方距離的WKNN算法（WKNN algorithm based on Chi square distance，CS-WKNN）和基于卡方距離AP加權(quán)的WKNN算法（WKNN algorithm based on Chi square distance AP weighting，CSW-WKNN），對同一指紋庫進行待測點預(yù)測定位，分析每一個待測點的最大定位誤差、最小定位誤差與平均定位誤差。根據(jù)本文算法原理，三種方法待測點具體定位結(jié)果如圖3所示，顯然本文算法可準確預(yù)測待測點實際位置，為未知點位的軌跡預(yù)測提供位置基礎(chǔ)。

圖3 預(yù)測點位

由圖4可知，通過選擇不同值對同一指紋數(shù)據(jù)庫進行待測點位置預(yù)測，當值為4時，CS-WKNN算法和CSW-WKNN算法平均定位誤差存在最低值。本文算法處理同一數(shù)據(jù)集時，值存在自適應(yīng)變化（如圖5所示），有利于去掉冗余的AP，使定位誤差范圍縮小。為減少算法計算量，將最優(yōu)（=4）值代入實驗，分析累計誤差分布如圖6所示。

對比三種算法的定位誤差范圍占比、具體誤差數(shù)值以及算法完成所需時間，驗證本文算法的可行性，如表1至表3所示。

圖4 不同K值平均定位精度

圖5 自適應(yīng)K值大小

圖6 累計誤差分布

表1 誤差范圍比例

表2 算法誤差對比 單位：m

表3 算法完成所需執(zhí)行時間 單位：s

分析表1可知，本文算法和CSW-WKNN算法誤差均在4 m以內(nèi)，1 m以內(nèi)誤差占比過半。結(jié)合圖6分析，CS-WKNN算法定位誤差集中在2～4 m，說明不同AP確實存在穩(wěn)定性差別，對室內(nèi)定位結(jié)果存在影響。

通過表2的最大定位誤差、最小定位誤差和平均定位誤差比較，本文算法平均定位誤差較CSW-WKNN算法降低了5.8%，較CS-WKNN算法降低了41.9%；此外，最大定位誤差較CSW-WKNN算法降低了4.6%，較CS-WKNN算法降低了35.2%；但本文算法誤差多集中于1 m以內(nèi)，且平均誤差為1.2346 m，誤差波動較小。

三種算法完成定位所需時間（如表3所示）均滿足實際工程需求，當定位范圍較大且數(shù)據(jù)庫信息復(fù)雜時，本文算法更有利于去除冗余的AP信息，解決定位時效性差的問題。綜合分析，本文算法定位精度與CSW-WKNN算法接近且有所提升，對于值存在更高的穩(wěn)定性且降低了分析匹配最佳值的時間。

3 結(jié)束語

針對傳統(tǒng)WKNN算法中固定值和AP穩(wěn)定性不同導(dǎo)致的定位精度低，本文提出一種基于卡方距離的AP加權(quán)自適應(yīng)動態(tài)值WKNN算法。通過參考點與待測點之間的距離差，給予不同AP不同權(quán)值，決定相似度距離的閾值，由閾值剔除由于空間結(jié)構(gòu)引起的誤差點，自適應(yīng)獲得個參考點，精確計算待測點真實位置坐標，實現(xiàn)了動態(tài)值室內(nèi)定位算法。實驗結(jié)果表明，相比CSW-WKNN、CS-WKNN算法采用固定值，本文算法可避免疏遠參考點和AP不同穩(wěn)定性引起的偏差，有效提高了室內(nèi)定位的穩(wěn)定性和定位精度，能更好地應(yīng)用于實際生活中。

[1] 秦國威, 孫新柱, 陳孟元. 基于Wi-Fi指紋的改進型室內(nèi)定位算法研究[J]. 陜西理工大學(xué)學(xué)報(自然科學(xué)版), 2018, 34(3): 28-34.

[2] 于洋, 陳光, 單志勇, 等. 基于中心矩改進的WiFi室內(nèi)定位算法[J]. 計算機應(yīng)用與軟件, 2018, 35(2): 130-133, 160.

[3] 畢京學(xué), 汪云甲, 紀冬華, 等. RSS最小值動態(tài)補償?shù)氖覂?nèi)WKNN指紋定位方法[J]. 測繪科學(xué), 2020, 45(12): 22-27.

[4] 何志爽, 萬亞平, 趙慶, 等. WiFi的室內(nèi)定位技術(shù)的改進研究[J]. 南華大學(xué)學(xué)報(自然科學(xué)版), 2018, 32(3): 60-64.

[5] 陶崢, 王洪玉. 基于卡方距離改進的WLAN室內(nèi)定位算法[J]. 計算機技術(shù)與發(fā)展, 2016, 26(9): 50-55.

[6] 陳亦奇, 周蓉, 滕婧, 等. 基于自適應(yīng)修正曼哈頓距離的室內(nèi)定位方法[J]. 導(dǎo)航定位與授時, 2019, 6(6): 94-102.

[7] 曹曉祥, 陳國良. 一種改進的組合定權(quán)的指紋定位算法[J]. 測繪通報, 2018(2): 6-10.

[8] 敬振宇, 熊興中, 張維, 等. 改進動態(tài)K的WKNN的室內(nèi)定位方法[J]. 現(xiàn)代電子技術(shù), 2021, 44(7): 22-27.

[9] 仲臣, 韓雨辰, 寧全可, 等. 基于AP加權(quán)的WKNN室內(nèi)定位算法[J]. 現(xiàn)代信息科技, 2020, 4(22): 71-73.

[10] 趙芳. 基于參考位置指紋離散程度的WKNN定位方法[J]. 沈陽工業(yè)大學(xué)學(xué)報, 2021, 43(2): 203-207.

[11] 徐逸軒, 余松森, 蘇海, 等. 基于差分修正的WKNN室內(nèi)定位方法[J]. 電腦知識與技術(shù), 2020, 16(4): 256-258.

[12] 康靜怡, 韓中豪, 何玉美, 等. 一種基于WKNN定位的改進算法[J]. 成都信息工程大學(xué)學(xué)報, 2018, 33(1): 8-12.

Adaptive dynamic indoor positioning method based on AP weighting

ZHONG Chen1,2,3, YU Xuexiang1,2,3, TAI Xiaoman1,2,3, XIAO Xingxing1,2,3, HAN Yuchen1,2,3, LIU Qinghua1,2,3

(1. School of Geomatics, Anhui University of Science and Technology, Huainan, Anhui 232001, China；2. Key Laboratory of Aviation-aerospace-ground Cooperative Monitoring and Early Warning of Coal Mining-induced Disasters of Anhui Higher Education Institutes, Anhui University of Science and Technology, Huainan, Anhui 232001, China；3. Coal Industry Engineering Research Center of Mining Area Environmental And Disaster Cooperative Monitoring, Anhui University of Science and Technology, Huainan, Anhui 232001, China)

In view of the redundant information of different Access Points (AP) in traditional location algorithm, and the time-effective error of location in the large location range, an AP weighted adaptive dynamic location algorithm based on the square distance is proposed. In fingerprint matching stage, the chi square distance is used to replace the European distance in the traditional Weighted-Nearest Neighborhood (WKNN) algorithm, and the AP variance is weighted to the similarity, so as to adjust the distance threshold adaptively, and dynamicvalue is introduced to extract the database information accurately. The experimental results show that the algorithm is more advantageous to remove redundant AP, reduce the range of positioning error and improve the positioning accuracy and stability.

indoor location; adaptive weighted-nearest neighbor; fingerprint matching; positioning accuracy

P228

A

2095-4999(2022)02-0053-05

仲臣，余學(xué)祥，邰曉曼，等. 基于AP加權(quán)的自適應(yīng)動態(tài)室內(nèi)定位方法[J]. 導(dǎo)航定位學(xué)報, 2022, 10(2): 53-57.（ZHONG Chen, YU Xuexiang, TAI Xiaoman, et al. Adaptive dynamic indoor positioning method based on AP weighting[J]. Journal of Navigation and Positioning, 2022, 10(2): 53-57.）

10.16547/j.cnki.10-1096.20220207.

2021-06-30

國家自然基金面上項目（41474026）；安徽省自然科學(xué)基金項目（2008085MD114）。

仲臣（1997—）,男,安徽馬鞍山人,碩士研究生，研究方向為空間信息與定位。

余學(xué)祥（1965—），男，安徽太湖人，博士，教授，研究方向為空間信息與定位。