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

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

基于AP加權(quán)的自適應(yīng)動(dò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é) 空間信息與測(cè)繪工程學(xué)院,安徽 淮南 232001；2. 安徽理工大學(xué) 礦山采動(dòng)災(zāi)害空天地協(xié)同監(jiān)測(cè)與預(yù)警安徽普通高校重點(diǎn)實(shí)驗(yàn)室,安徽 淮南 232001；3. 安徽理工大學(xué) 礦區(qū)環(huán)境與災(zāi)害協(xié)同監(jiān)測(cè)煤炭行業(yè)工程研究中心,安徽 淮南 232001）

針對(duì)傳統(tǒng)定位算法存在大量不同接入點(diǎn)（AP）的冗余信息，且在定位范圍較大時(shí)定位時(shí)效性差的問(wèn)題，提出一種基于卡方距離的AP加權(quán)自適應(yīng)動(dòng)態(tài)定位算法。指紋匹配階段利用卡方距離代替?zhèn)鹘y(tǒng)加權(quán)近鄰算法（WKNN）中的歐式距離，用AP方差對(duì)相似度進(jìn)行加權(quán)，從而自適應(yīng)調(diào)整距離閾值，并引入動(dòng)態(tài)值，精確提取數(shù)據(jù)庫(kù)信息。實(shí)驗(yàn)結(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)達(dá)到毫米級(jí)，但在大型建筑中進(jìn)行室內(nèi)定位，其精度仍不滿(mǎn)足要求。為了追求更加高效、智能的生活方式，基于位置服務(wù)（location based services, LBS）的室內(nèi)定位技術(shù)正展現(xiàn)著廣泛的應(yīng)用前景。室內(nèi)定位技術(shù)主要包括藍(lán)牙、地磁、射頻識(shí)別、無(wú)線保真（wireless fidelity,WiFi）定位、慣性導(dǎo)航、超寬帶、超聲波等方法。WiFi室內(nèi)定位憑借著精度相對(duì)較高、WiFi接入點(diǎn)部署簡(jiǎn)單和成本低等特點(diǎn)成為目前研究熱點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

圖1 定位流程

2 實(shí)驗(yàn)與結(jié)果分析

2.1 實(shí)驗(yàn)環(huán)境與方法

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

圖2 實(shí)驗(yàn)區(qū)域

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

2.2 實(shí)驗(yàn)結(jié)果分析

為驗(yàn)證本文算法定位精度，分別利用基于卡方距離的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），對(duì)同一指紋庫(kù)進(jìn)行待測(cè)點(diǎn)預(yù)測(cè)定位，分析每一個(gè)待測(cè)點(diǎn)的最大定位誤差、最小定位誤差與平均定位誤差。根據(jù)本文算法原理，三種方法待測(cè)點(diǎn)具體定位結(jié)果如圖3所示，顯然本文算法可準(zhǔn)確預(yù)測(cè)待測(cè)點(diǎn)實(shí)際位置，為未知點(diǎn)位的軌跡預(yù)測(cè)提供位置基礎(chǔ)。

圖3 預(yù)測(cè)點(diǎn)位

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

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

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

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

圖6 累計(jì)誤差分布

表1 誤差范圍比例

表2 算法誤差對(duì)比 單位：m

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

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

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

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

3 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

[8] 敬振宇, 熊興中, 張維, 等. 改進(jìn)動(dòng)態(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áng)工業(yè)大學(xué)學(xué)報(bào), 2021, 43(2): 203-207.

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

[12] 康靜怡, 韓中豪, 何玉美, 等. 一種基于WKNN定位的改進(jìn)算法[J]. 成都信息工程大學(xué)學(xué)報(bào), 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)動(dòng)態(tài)室內(nèi)定位方法[J]. 導(dǎo)航定位學(xué)報(bào), 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

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

仲臣（1997—）,男,安徽馬鞍山人,碩士研究生，研究方向?yàn)榭臻g信息與定位。

余學(xué)祥（1965—），男，安徽太湖人，博士，教授，研究方向?yàn)榭臻g信息與定位。