基于AP加權(quán)的WKNN室內(nèi)定位算法

仲臣 韓雨辰 寧全可 余丹 謝世成

摘? 要：科技的發(fā)展帶動(dòng)了日常生活質(zhì)量的提升，給予了室內(nèi)定位廣闊的發(fā)展前景。由于定位過程中不同AP存在差異，造成室內(nèi)定位精度差、波動(dòng)大等問題，文章在原有指紋數(shù)據(jù)庫匹配算法的基礎(chǔ)上，提出一種基于AP加權(quán)的K近鄰算法，利用方差加權(quán)AP結(jié)合歐氏距離進(jìn)行相似度匹配。實(shí)驗(yàn)結(jié)果表明，該方法較經(jīng)典室內(nèi)定位算法，存在更高的定位精度及穩(wěn)定性。

關(guān)鍵詞：室內(nèi)定位;定位精度;穩(wěn)定性

中圖分類號(hào)：TN92;P228.4? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2020）22-0071-03

Indoor Positioning Algorithm of WKNN Based on AP Weighting

ZHONG Chen，HAN Yuchen，NING Quanke，YU Dan，XIE Shicheng

（School of Space Information and Surveying Engineering，Anhui University of Science and Technology，Huainan? 232001，China）

Abstract：The development of science and technology promotes the improvement of the quality of daily life，which gives a broad development prospect for indoor positioning. Due to differences between different APs in the positioning process，problems such as poor indoor positioning accuracy and large fluctuations are caused. Based on the original fingerprint database matching algorithm，this paper proposes a K-nearest neighbor algorithm based on AP weighting，which uses variance weighted AP combined with Euclidean distance for similarity matching. Experimental results show that this method has higher positioning accuracy and stability than the classical indoor positioning algorithm.

Keywords：indoor positioning;positioning accuracy;stability

0? 引? 言

如今，以GPS為主的室外定位技術(shù)已基本成熟且適用性極高，其定位精度可達(dá)米級(jí)，僅僅依靠隨身攜帶的移動(dòng)設(shè)備就可以滿足人們出行游玩方面的需求。隨著經(jīng)濟(jì)水平的不斷提高，一些企業(yè)的建筑規(guī)模愈發(fā)龐大。在某些車間中，人們需要對(duì)貴重的設(shè)備及工作人員進(jìn)行規(guī)劃管理;在醫(yī)院、幼兒園等特殊場所同樣需要對(duì)重點(diǎn)人群進(jìn)行軌跡定位。這使得人們對(duì)室內(nèi)定位服務(wù)的需求更加迫切[1]。早在1996年，室內(nèi)定位技術(shù)就被美國聯(lián)邦通信委員會(huì)所提出，至今仍是眾多學(xué)者的研究熱點(diǎn)。室內(nèi)定位的高精度實(shí)現(xiàn)相比室外定位而言更加復(fù)雜，首先GNSS信號(hào)很難通過墻體等障礙物傳遞到室內(nèi)，因此需要利用室內(nèi)的物理設(shè)備以及其他的信號(hào)介質(zhì)途徑進(jìn)行定位，這種技術(shù)也被稱為局域室內(nèi)定位技術(shù)。其中包含Wi-Fi技術(shù)、藍(lán)牙技術(shù)、紫蜂技術(shù)、超寬帶技術(shù)、慣性單元技術(shù)、超聲波定位技術(shù)、射頻識(shí)別技術(shù)、地磁定位技術(shù)、可見光定位技術(shù)、紅外線定位技術(shù)等[2]。其次，信號(hào)在室內(nèi)傳播過程中極易受到人群流動(dòng)、金屬物品等干擾，導(dǎo)致穩(wěn)定性受到影響。而且參與室內(nèi)定位的設(shè)備成本、普及性及損耗程度在研究過程中均需考慮。因此在上述局域室內(nèi)定位技術(shù)中，Wi-Fi室內(nèi)定位技術(shù)因其精度較高，覆蓋面較大，使用廣泛且成本較低等倍受關(guān)注，同樣在智慧城市建設(shè)、商場消費(fèi)引導(dǎo)等方面也有著極大的應(yīng)用前景[3]。

Wi-Fi室內(nèi)定位方法主要有兩種：利用無線傳播模型定位技術(shù)和指紋庫匹配定位技術(shù)。在無線傳播模型方法中，通過信號(hào)達(dá)到時(shí)間（TOA）、信號(hào)到達(dá)時(shí)間差（TDOA）、信號(hào)達(dá)到角（AOA）等模型估計(jì)AP和移動(dòng)臺(tái)之間的距離。雖然這種方法有助于距離估計(jì)，但由于Wi-Fi信號(hào)容易受周圍環(huán)境的影響，相關(guān)參數(shù)波動(dòng)較大而無法提供準(zhǔn)確的定位。相比之下，指紋庫匹配定位技術(shù)具有無需考慮接入點(diǎn)（Access Point，AP）位置無需計(jì)算視距、受信號(hào)強(qiáng)度（Received Signal Strength，RSS）波動(dòng)影響小、容錯(cuò)率高等優(yōu)點(diǎn)，定位精度甚至比無線傳播模型定位技術(shù)高。

本文以安徽理工大學(xué)空間信息與測繪工程學(xué)院為分析案例，通過對(duì)比當(dāng)前主要的室內(nèi)定位方法，初步討論了基于AP加權(quán)K近鄰算法的實(shí)用性及穩(wěn)定性，對(duì)室內(nèi)定位研究進(jìn)行展望。

1? 傳統(tǒng)室內(nèi)定位算法

5G技術(shù)發(fā)展逐漸成熟、衛(wèi)星導(dǎo)航定位系統(tǒng)組網(wǎng)成功以及Wi-Fi硬件的更新?lián)Q代使得室內(nèi)定位服務(wù)精度需求得以實(shí)現(xiàn)。從21世紀(jì)初期指紋數(shù)據(jù)庫匹配技術(shù)初步應(yīng)用于Wi-Fi室內(nèi)定位至今，指紋數(shù)據(jù)庫匹配定位技術(shù)一直是研究的熱點(diǎn)，具有低成本、高精度、良好的穿透力等優(yōu)點(diǎn)。

指紋數(shù)據(jù)庫匹配定位技術(shù)[4]包括兩個(gè)階段：離線數(shù)據(jù)庫建立階段和在線數(shù)據(jù)定位階段。離線數(shù)據(jù)庫建立階段，實(shí)驗(yàn)區(qū)域進(jìn)行網(wǎng)格劃分構(gòu)建位置坐標(biāo)，在每一個(gè)坐標(biāo)點(diǎn)進(jìn)行RSS采集并進(jìn)行預(yù)處理，篩除波動(dòng)較大的RSS，將位置坐標(biāo)和多個(gè)AP的RSS組成有序向量作為參考點(diǎn)存儲(chǔ)入數(shù)據(jù)庫;在線數(shù)據(jù)定位階段，定位目標(biāo)通過儀器實(shí)時(shí)采集RSS，采用匹配算法與數(shù)據(jù)庫中參考點(diǎn)數(shù)據(jù)進(jìn)行相似度匹配，再將匹配點(diǎn)通過均值、加權(quán)等方法計(jì)算定位目標(biāo)的實(shí)際位置。

加權(quán)K近鄰算（WKNN）法是由最早的最近鄰定位（NN）算法到K近鄰（KNN）算法一步步演變來的，一般以歐氏距離作為RSS向量間相似度的比較，決定指紋庫匹配點(diǎn)的位置[5]。歐氏距離常用來表示兩向量之間的絕對(duì)距離。兩向量之間的歐氏距離如式（1）所示：

其中，A1（x1，x2，…，xn）和A2（y1，y2，…，yn）為兩向量，d為歐氏距離。

在指紋數(shù)據(jù)庫離線匹配階段，若在定位區(qū)域布設(shè)i個(gè)參考點(diǎn)并通過設(shè)備采集每一個(gè)參考點(diǎn)的RSS值，將RSS值與位置坐標(biāo)組成指紋存儲(chǔ)入指紋庫中，構(gòu)建完成所需指紋庫。

若使用歐式距離表示待測點(diǎn)與i個(gè)參考點(diǎn)之間的相似度，則式（1）改為式（2）：

其中，di為待測點(diǎn)與第i個(gè)參考點(diǎn)之間的歐氏距離，Rij為定位區(qū)域中第i個(gè)參考點(diǎn)上采集的第j個(gè)AP的RSS值;Sj為待測點(diǎn)上采集的第j個(gè)AP的RSS值;n為定位區(qū)域內(nèi)所有的AP個(gè)數(shù)。

在指紋數(shù)據(jù)庫匹配在線階段，典型WKNN算法中歐氏距離通過計(jì)算待測點(diǎn)與指紋庫中每個(gè)參考點(diǎn)的距離，距離越近表示兩點(diǎn)相似度越明顯，利用距離大小排序，選擇距離最小參考點(diǎn)，此方法稱為NN算法，只能描述出待測點(diǎn)大致位置，無法真正表示點(diǎn)的實(shí)際位置坐標(biāo)[6]。

由于距離相當(dāng)于相似度，若取K（K≥2）個(gè)參考點(diǎn)作為預(yù)定位點(diǎn)，求取多個(gè)預(yù)定位點(diǎn)位置坐標(biāo)的平均作為待測點(diǎn)的實(shí)際位置坐標(biāo)，則此方法稱為KNN算法，相對(duì)NN算法精度較高，選取K個(gè)參考點(diǎn)進(jìn)行定位。計(jì)算方法如式（3）所示：

其中，（x，y）為KNN算法的定位坐標(biāo)，（xi，yi）為第i個(gè)參考點(diǎn)的實(shí)際位置坐標(biāo)。

KNN算法仍然不能滿足室內(nèi)定位精度要求，考慮到不同參考點(diǎn)對(duì)待測點(diǎn)位置預(yù)測的貢獻(xiàn)程度不同，給予K個(gè)參考點(diǎn)位置坐標(biāo)不同的權(quán)值即可獲得精度更高的預(yù)測坐標(biāo)，此方法稱為WKNN算法，WKNN算法計(jì)算簡單，是指紋數(shù)據(jù)庫匹配中的常用算法，計(jì)算方法如式（4）所示：

其中，ωi為預(yù)定位參考點(diǎn)的第i個(gè)權(quán)值，ω的數(shù)值根據(jù)參考點(diǎn)與待測點(diǎn)之間的歐氏距離大小變化而變化，是決定待測點(diǎn)定位精度的重要參數(shù)。計(jì)算方法如式（5）所示：

若ωi的數(shù)值為 ，即為K近鄰方法。傳統(tǒng)室內(nèi)定位僅僅考慮到不同參考點(diǎn)對(duì)待測點(diǎn)的影響，并沒有考慮到數(shù)據(jù)源對(duì)定位結(jié)果的影響。

2? 改進(jìn)室內(nèi)定位算法

室內(nèi)定位中不同AP傳輸信號(hào)穩(wěn)定性不同，造成定位精度并不準(zhǔn)確，不可以統(tǒng)一權(quán)值進(jìn)行計(jì)算相似度。利用不同AP差異性進(jìn)行距離加權(quán)，使不同AP對(duì)定位的貢獻(xiàn)程度不同，提升定位精度及穩(wěn)定性[7]。

在上述傳統(tǒng)WKNN算法基礎(chǔ)上，在同一點(diǎn)采集多次數(shù)據(jù)，計(jì)算每個(gè)AP的方差，匹配點(diǎn)的相似度利用方差表示，如式（6）所示：

其中，σj為第j個(gè)AP采集RSS的方差;t為在同一點(diǎn)采集RSS值的次數(shù);rj（k）為第j個(gè)AP采集的第k個(gè)RSS值; 為在同一點(diǎn)采集第j個(gè)AP所有RSS的平均值。從而計(jì)算AP加權(quán)值vj和距離相似度Di，求取待測點(diǎn)位置坐標(biāo)：

3? 實(shí)驗(yàn)分析

選取安徽理工大學(xué)空間信息與測繪工程學(xué)院二層某一教室進(jìn)行實(shí)驗(yàn)驗(yàn)證。該定位區(qū)域面積約為20 m×20 m，教室內(nèi)有隔墻、桌椅以箱子等干擾因素。此樓層設(shè)置4個(gè)采用TP-Link型號(hào)熱點(diǎn)的AP點(diǎn)并用小米手機(jī)進(jìn)行信號(hào)采集。

首先對(duì)實(shí)驗(yàn)區(qū)域進(jìn)行網(wǎng)格劃分，離線階段對(duì)所有參考點(diǎn)進(jìn)行采集并記錄相關(guān)位置坐標(biāo)，建立指紋數(shù)據(jù)庫，并在中心某一點(diǎn)多次采集，為后期AP加權(quán)提供數(shù)據(jù)基礎(chǔ);在線階段把待測點(diǎn)RSS用歐氏距離進(jìn)行加權(quán)表示相似度，再用WKNN算法求解位置坐標(biāo)，將解算坐標(biāo)與實(shí)際坐標(biāo)運(yùn)算得出誤差值，分析累計(jì)誤差分布。實(shí)驗(yàn)操作流程如圖1所示。

由表1可得，基于AP加權(quán)的WKNN算法相較于傳統(tǒng)的WKNN算法平均定位誤差由3.1 m減小到了2.9 m，提升了5.2%;最大定位誤差由9.3 m減小到8.5 m，提升了8.9%;最小定位誤差由0.14 m減小到0.11 m，提升了21.9%。定位精度明顯由于傳統(tǒng)的WKNN算法。

圖2表示的是改進(jìn)后的算法與WKNN、KNN算法之間定位累積概率誤差。由圖可得，基于AP加權(quán)的WKNN算法在定位誤差概率分布上均優(yōu)于WKNN算法且誤差80%在4 m以內(nèi)，定位的穩(wěn)定性明顯優(yōu)于傳統(tǒng)室內(nèi)定位算法。

4? 結(jié)? 論

分析了室內(nèi)定位指紋匹配階段存在的各種問題，進(jìn)而提出一種基于AP加權(quán)的WKNN算法來提升室內(nèi)定位精度。將AP差異性利用方差進(jìn)行表示并作為權(quán)值加入定位算法的相似度計(jì)算中，有效的解決了AP不同而造成的衡量指標(biāo)的差異。實(shí)驗(yàn)表示，該方法提高了定位精度和指紋匹配的穩(wěn)定性，且易實(shí)現(xiàn)具有一定的實(shí)用價(jià)值。

但是，基于指紋庫匹配的室內(nèi)定位仍需改進(jìn)。數(shù)據(jù)方面，信道狀態(tài)信息相對(duì)于信號(hào)強(qiáng)度更穩(wěn)定，但是適用于信道狀態(tài)信息的裝置仍未普及;KNN算法中，K值仍然需要調(diào)試，無法進(jìn)行算法自適應(yīng)，達(dá)不到最高精度;預(yù)處理階段，參考點(diǎn)信號(hào)波動(dòng)引起誤差，進(jìn)行粗差處理后重組數(shù)據(jù)，可明顯提高定位穩(wěn)定性。這些問題都是今后值得研究的方向。

參考文獻(xiàn)：

[1] 陳空，宋春雷，陳家斌，等.基于改進(jìn)WKNN的位置指紋室內(nèi)定位算法 [J].導(dǎo)航定位與授時(shí)，2016（4）：58-64.

[2] 李新春，王歡.基于稀疏指紋采集和改進(jìn)WKNN的定位算法 [J].重慶郵電大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，31（4）：451-459.

[3] 吳虹，王國萍，彭鴻釗，等.一種基于KNN的室內(nèi)位置指紋定位算法 [J].南開大學(xué)學(xué)報(bào)（自然科學(xué)版），2020，53（6）：5-9.

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

[5] 朱正偉，蔣威，張貴玲，等.基于RSSI的室內(nèi)WiFi定位算法 [J].計(jì)算機(jī)工程與設(shè)計(jì)，2020，41（10）：2958-2962.

[6] 康曉非，李夢夢，喬威.基于WiFi指紋的高精度室內(nèi)定位融合算法 [J].西安科技大學(xué)學(xué)報(bào)，2020，40（3）：470-476.

[7] 黨小超，馬平川，郝占軍.基于CSI的改進(jìn)KNN室內(nèi)定位方法 [J].傳感器與微系統(tǒng)，2019（10）：51-53.

作者簡介：仲臣（1997—），男，漢族，安徽馬鞍山人，碩士在讀，研究方向：室內(nèi)定位。