基于線性內(nèi)插法改進(jìn)的室內(nèi)定位算法

張夢(mèng)丹，盧光躍，王宏剛，劉繼明

（西安郵電大學(xué)，陜西 西安710121）

基于線性內(nèi)插法改進(jìn)的室內(nèi)定位算法

張夢(mèng)丹，盧光躍，王宏剛，劉繼明

（西安郵電大學(xué)，陜西 西安710121）

針對(duì)室內(nèi)位置指紋定位技術(shù)存在的離線階段工作量大、定位精度有限、頑健性較差的缺點(diǎn)，提出了一種基于線性內(nèi)插法改進(jìn)的指紋定位匹配算法。與傳統(tǒng)位置指紋定位技術(shù)相比，該算法不僅降低了整體工作量，而且降低了多徑效應(yīng)造成的不利影響。最后搭建實(shí)驗(yàn)場(chǎng)景對(duì)該算法定位性能進(jìn)行測(cè)試。實(shí)驗(yàn)數(shù)據(jù)顯示，該算法與WKNN法相比，平均定位精度大約提高了34.25%，絕大部分待測(cè)點(diǎn)的定位誤差在0.4 m以內(nèi)，驗(yàn)證了所提算法在定位精度、頑健性和適應(yīng)環(huán)境變化方面的優(yōu)勢(shì)。

室內(nèi)定位；位置指紋；WKNN；PCA；線性內(nèi)插法

1 引言

隨著無(wú)線技術(shù)、移動(dòng)計(jì)算機(jī)和互聯(lián)網(wǎng)應(yīng)用的不斷增長(zhǎng)，人們對(duì)位置敏感系統(tǒng)及其服務(wù)的需求越來(lái)越高。在室外，GPS系統(tǒng)被廣泛用于提供定位信息與服務(wù)，其室外定位精度能夠達(dá)到美國(guó)E911標(biāo)準(zhǔn)。但在室內(nèi)復(fù)雜環(huán)境中，由于室內(nèi)物品的干擾、非視距等因素，一般不采用GPS系統(tǒng)進(jìn)行定位?，F(xiàn)在常用的室內(nèi)定位技術(shù)有Wi-Fi技術(shù)、藍(lán)牙技術(shù)[1]、紅外線室內(nèi)定位技術(shù)、超聲波定位技術(shù)等。這些技術(shù)有的成本較高、有的室內(nèi)定位精度低，均不利于室內(nèi)定位的廣泛推廣。而融入了藍(lán)牙4．0的新技術(shù)，不僅增強(qiáng)了信號(hào)的穩(wěn)定性及覆蓋范圍，而且降低了功耗，因此迅速成為室內(nèi)定位領(lǐng)域的優(yōu)選技術(shù)。

根據(jù)定位過(guò)程中是否需要實(shí)際測(cè)量節(jié)點(diǎn)間距離，室內(nèi)定位方式可分為兩類：即基于距離[2]和距離無(wú)關(guān)。目前，基于測(cè)距的定位技術(shù)主要有到達(dá)角度（angle of arrival，AOA）法、到達(dá)時(shí)間（time of arrival，TOA）法、到達(dá)時(shí)間差（time difference of arrival，TDOA）法等，而基于非測(cè)距定位主要是基于信號(hào)強(qiáng)度測(cè)量法定位[4]?；谛盘?hào)強(qiáng)度測(cè)量法定位可分為位置指紋定位法和信號(hào)傳輸損耗法[5]，而現(xiàn)有利用位置指紋進(jìn)行匹配的算法主要包括 WKNN（weighted K-nearest neighbor，加權(quán)K鄰近）算法、神經(jīng)網(wǎng)絡(luò)算法、概率算法和支持向量機(jī)（SVM）算法等。WKNN算法遍歷指紋點(diǎn)的接收信號(hào)強(qiáng)度指示（received signal strength indication，RSSI），找出最接近測(cè)試點(diǎn)RSSI的一個(gè)或多個(gè)指紋點(diǎn)，然后將這些指紋點(diǎn)位置的加權(quán)值作為測(cè)試點(diǎn)的估計(jì)位置。WKNN算法容易實(shí)現(xiàn)，但定位精度不高，且在實(shí)際的室內(nèi)環(huán)境中，無(wú)線信號(hào)在傳播過(guò)程中會(huì)受到多徑效應(yīng)的影響，因而在同一個(gè)位置上的接入點(diǎn)（access point，AP）的RSSI往往表現(xiàn)出復(fù)雜的時(shí)變特性，進(jìn)而進(jìn)一步降低了室內(nèi)定位的精度。為此，本文應(yīng)用主成分分析（principal component analysis，PCA）變換提取原始RSSI信號(hào)中的主要定位特征，以減少多徑效應(yīng)對(duì)定位的影響。另外，針對(duì)定位離線階段工作量大的問(wèn)題，本文應(yīng)用線性插值法來(lái)重構(gòu)離線指紋庫(kù)，并對(duì)測(cè)試點(diǎn)進(jìn)行定位。實(shí)驗(yàn)證明，所提算法具有較高的定位精度和較好的實(shí)時(shí)性，滿足了室內(nèi)定位的基本需求。

2 基于RSSI的位置指紋定位算法

2.1 指紋算法描述

位置指紋定位算法包括兩個(gè)階段：離線階段和在線階段。離線階段的工作是在待定位區(qū)域內(nèi)按照一定的間隔距離確定若干參考點(diǎn)，形成一個(gè)采樣網(wǎng)格圖，并將每個(gè)節(jié)點(diǎn)測(cè)得的信號(hào)強(qiáng)度值及其位置信息按照＜指紋，地點(diǎn)＞的格式存儲(chǔ)在數(shù)據(jù)庫(kù)中；在線階段，通過(guò)移動(dòng)終端對(duì)各個(gè)AP發(fā)出的信號(hào)強(qiáng)度進(jìn)行實(shí)時(shí)采集，通過(guò)特定的匹配算法實(shí)現(xiàn)對(duì)移動(dòng)設(shè)備位置的估計(jì)[7,8]。

2.2WKNN算法

WKNN法屬于典型的確定性定位算法[9]。其定位思路為：首先構(gòu)建離線指紋庫(kù)，F(xiàn)i=(fi1,fi2,fi3,…,fin)，fin表示在第i個(gè)參考點(diǎn)處接收到第n個(gè)AP的指紋信息，其次，移動(dòng)終端用戶獲取在待測(cè)點(diǎn)位置處各個(gè)AP的信號(hào)強(qiáng)度值，記為向量 Rt=(r1,r2,r3,…,rn)，rn為移動(dòng)設(shè)備接收到的第 n個(gè) AP的信號(hào)強(qiáng)度，最后計(jì)算此向量與指紋庫(kù)中向量的歐氏距離，為：

選擇距離最小的前K個(gè)采樣點(diǎn)，并按照每個(gè)參考點(diǎn)對(duì)待測(cè)點(diǎn)的貢獻(xiàn)程度計(jì)算每個(gè)參考點(diǎn)的權(quán)值 wj[10]，如式（3）所示，定位點(diǎn)的估計(jì)位置是這K個(gè)點(diǎn)的加權(quán)質(zhì)心。其中，K值可根據(jù)定位環(huán)境選取[11]。

其中，Dj表示第j個(gè)參考點(diǎn)與待測(cè)點(diǎn)的歐氏距離。由式（3）知，歐氏距離Dj越大，wj越?。幌喾礆W氏距離Dj越小，wj越大。

3 改進(jìn)的定位估計(jì)匹配算法

WKNN算法雖然能基本滿足人們對(duì)位置的需求，但是仍存在一些問(wèn)題：增加參考標(biāo)簽數(shù)目可以提高室內(nèi)定位精度，但會(huì)增加額外的成本；在密集環(huán)境下，多徑效應(yīng)會(huì)給定位結(jié)果帶來(lái)一定的影響。因此提出了一種基于子區(qū)域插值改進(jìn)的指紋定位匹配算法。

3.1 主成分分析法

主成分分析法的基本原理是：根據(jù)K-L變換在測(cè)試空間中找到一組能最大限度表示出原始數(shù)據(jù)信息的正交向量，把原始數(shù)據(jù)從原來(lái)的空間投影到這組正交向量組成的空間上，其投影系數(shù)便構(gòu)成新的特征矢量，從而完成對(duì)維數(shù)的壓縮。

設(shè)T={(S1,L1),(S2,L2),…,(Sp,Lp),}，Sp∈Rm為參考點(diǎn)處的信號(hào)集。Sp為在位置p處接收到的AP的信號(hào)強(qiáng)度，Lp為位置p的二維位置坐標(biāo)。假設(shè) X=[S1,S2,…,Sp]T，則PCA變換為：Z=AT(X-E[X])，A=[u1,u2,…,uk]，A中的uk是由X的協(xié)方差矩陣CX=E{(X-X)(X-X)T}的特征值λk對(duì)應(yīng)的特征向量按從大到小的順序排列組成。經(jīng)過(guò)PCA變換，Z中各個(gè)矢量間的相似性基本消除，其中，Z中前m個(gè)主成分占據(jù)了X的絕大部分信息，Z′=[S1′,S2′,…,Sp′]T，因m＜d，因此完成了對(duì)指紋數(shù)據(jù)維數(shù)的壓縮。

3.2 線性內(nèi)插法

線性內(nèi)插法的基本思想是：在待定位區(qū)域內(nèi)按照一定的間隔距離確定若干采樣點(diǎn)，形成一個(gè)采樣網(wǎng)格圖，在網(wǎng)格圖內(nèi)進(jìn)一步劃分，將每個(gè)由4個(gè)參考標(biāo)簽覆蓋的網(wǎng)格分為N×N個(gè)大小相同的虛擬網(wǎng)格單元，由于參考標(biāo)簽坐標(biāo)已知，虛擬參考標(biāo)簽易得到，同時(shí)采用線性插值方法來(lái)獲得虛擬參考標(biāo)簽的信號(hào)強(qiáng)度值。下面將詳細(xì)地對(duì)該算法進(jìn)行介紹。線性內(nèi)插法原理如圖1所示。

圖1 線性內(nèi)插法原理

如圖1所示，其中，白色圓圈代表采樣點(diǎn)，4個(gè)組成采樣網(wǎng)格圖，然后把網(wǎng)格劃分成N×N個(gè)小網(wǎng)格，灰色圓圈代表劃分好的虛擬參考點(diǎn)。根據(jù)實(shí)際參考點(diǎn)位置坐標(biāo)可求得虛擬參考點(diǎn)的坐標(biāo)。最后采用線性插值可以得到虛擬參考點(diǎn)處的接收信號(hào)強(qiáng)度值。

水平方向上的虛擬參考點(diǎn)接收信號(hào)強(qiáng)度值可以由式（4）求出：

垂直方向上的虛擬參考點(diǎn)接收信號(hào)強(qiáng)度值可以由式（5）求出：

其中，Sk(Ti,j)表示在第k個(gè)參考點(diǎn)坐標(biāo)位置為(i,j)處讀到的接收信號(hào)強(qiáng)度值，a=「i/n」，b=「j/n」，「」表示向下取整，0≤p=i%n≤n-1，0≤q=j%n≤n-1，n=N-1。

3.3 N值的選擇

實(shí)際上，參考點(diǎn)處的RSSI值與距離的關(guān)系非線性，室內(nèi)環(huán)境信道的大尺度衰落服從對(duì)數(shù)正態(tài)分布的特性，選用對(duì)數(shù)距離路徑損耗模型獲取虛擬參考點(diǎn)的RSSI值?！熬嚯x—損耗”計(jì)算式為：

其中，d0是參考距離；dij是第i個(gè)參考點(diǎn)到第 j個(gè)AP的實(shí)際距離；P0是終端和 AP的距離為 d0時(shí)接收到的RSSI；P是距離為 dij時(shí)接收到的 RSSI；n是路徑損耗指數(shù)；ζ為遮蔽因子，是均值為0、標(biāo)準(zhǔn)差為σ的正態(tài)隨機(jī)變量。

由此，可以得出：必然存在一個(gè)使定位誤差達(dá)到最小的N值，下面將進(jìn)一步進(jìn)行理論論證。

以圖1參考點(diǎn)為例進(jìn)行線性插值，假設(shè)該網(wǎng)格的4個(gè)參考點(diǎn)為T1、T2、T3和T4，假設(shè)Rik為第i個(gè)參考點(diǎn)（包括實(shí)際參考點(diǎn)和虛擬參考點(diǎn)）處接收到的第k（k=1,2,3,4,5,6）個(gè)AP的RSSI值，Epk為相鄰參考點(diǎn)RSSI的差值，p=0,1,2,…,N-1，則：為在參考點(diǎn)T1處接收到的節(jié)點(diǎn)APk的RSSI，R2k為在參考點(diǎn)T2處接收到的節(jié)點(diǎn)APk的RSSI，R0k為在位置d0處接收到的節(jié)點(diǎn)AP1的RSSI，參考點(diǎn)T1的坐標(biāo)為(x1,y1)，T2的坐標(biāo)為(x2,y1)，APk的坐標(biāo)為(ak,bk)。

對(duì)Epk求N-1的導(dǎo)數(shù)，并令導(dǎo)數(shù)為零，可得：

其中

假設(shè)k=1，此時(shí)(ak,bk)=(a1,b1)=(0,0)，若p取1，分別遍歷(x1,y1)和(x2,y1)，并將各個(gè)參數(shù)的值代入式（9）中，最終得到N值變化如圖2所示。實(shí)驗(yàn)面積為14 m×10 m，參考點(diǎn)數(shù)為7×5，可見，理論上當(dāng)N為5～6時(shí)，用線性內(nèi)插法的誤差達(dá)到最小值。

圖2 N值變化折線

3.4 定位步驟

對(duì)于室內(nèi)位置指紋定位算法來(lái)說(shuō)，離線階段數(shù)據(jù)庫(kù)的構(gòu)建以及室內(nèi)環(huán)境存在多徑效應(yīng)的特點(diǎn)都對(duì)定位產(chǎn)生嚴(yán)重的影響。下面將詳細(xì)介紹改進(jìn)的定位估計(jì)匹配算法的步驟。對(duì)應(yīng)的匹配算法流程如圖3所示。

圖3 基于線性內(nèi)插和PCA改進(jìn)的指紋定位匹配算法流程

步驟1 選取試驗(yàn)場(chǎng)景，搭建測(cè)試環(huán)境，并多次采集每個(gè)參考點(diǎn)處的RSSI值求平均，構(gòu)建離線指紋數(shù)據(jù)庫(kù)。

步驟2 選取N值，確定虛擬參考點(diǎn)的劃分結(jié)構(gòu)，利用第3.2節(jié)介紹的線性內(nèi)插法求解虛擬參考點(diǎn)的位置坐標(biāo)和各個(gè)虛擬參考節(jié)點(diǎn)的RSSI值，重新構(gòu)建離線指紋數(shù)據(jù)庫(kù)。

步驟3 對(duì)構(gòu)建的離線指紋數(shù)據(jù)庫(kù)進(jìn)行主成分分析，去掉多徑效應(yīng)對(duì)信號(hào)造成的干擾，構(gòu)建特征數(shù)據(jù)庫(kù)。

步驟4 選取待測(cè)點(diǎn)，并用移動(dòng)終端讀取待測(cè)點(diǎn)的RSSI值，對(duì)待測(cè)點(diǎn)測(cè)量的數(shù)據(jù)進(jìn)行PCA變換，提取特征，假設(shè)變換后的向量為Z′=[S1′,S2′,…,Sp′]T。

步驟5 選取指紋定位算法WKNN的K值，這里令K=4，然后計(jì)算Z′與特征數(shù)據(jù)庫(kù)中每個(gè)參考點(diǎn)的歐氏距離，選取歐氏距離最小的前4個(gè)參考點(diǎn)，并分別計(jì)算對(duì)應(yīng)的加權(quán)值wj。

步驟6 按照式（3）估算移動(dòng)端的位置，實(shí)現(xiàn)對(duì)移動(dòng)端的實(shí)時(shí)定位。

4 實(shí)驗(yàn)性能比較與結(jié)果分析

4.1 測(cè)試平臺(tái)

本實(shí)驗(yàn)軟件平臺(tái)是基于Andriod開發(fā)的手機(jī)應(yīng)用軟件BLE Scanner，用于實(shí)現(xiàn)離線及在線階段的RSSI數(shù)據(jù)采集。硬件平臺(tái)采用的是iPhone 5和蘋果公司的iBeacon產(chǎn)品。實(shí)驗(yàn)環(huán)境位于西安郵電大學(xué)長(zhǎng)安區(qū)3號(hào)實(shí)驗(yàn)樓523房間。實(shí)驗(yàn)軟件、硬件平臺(tái)和實(shí)驗(yàn)場(chǎng)地實(shí)景如圖4所示。實(shí)驗(yàn)環(huán)境參數(shù)選取見表1。

圖4 軟件、硬件平臺(tái)和實(shí)驗(yàn)場(chǎng)地實(shí)景

表1 實(shí)驗(yàn)環(huán)境參數(shù)選取

4.2 性能比較與仿真分析

由第2.2節(jié)的介紹可知，當(dāng)測(cè)試環(huán)境和K值一定的情況下，影響WKNN算法定位結(jié)果的主要因素是：離線階段的參考點(diǎn)的數(shù)量太少，則造成定位精度下降；數(shù)量太大，耗時(shí)耗力，造成定位成本的增加。因此要根據(jù)具體的實(shí)驗(yàn)場(chǎng)景，合理地選擇參考點(diǎn)的數(shù)量。對(duì)這種算法的參考點(diǎn)的數(shù)量選取不同的值進(jìn)行MATLAB仿真，參考點(diǎn)的數(shù)量的選取及定位誤差見表2，仿真結(jié)果如圖5所示。由仿真結(jié)果可知，定位誤差隨著參考點(diǎn)數(shù)量的增加而減少。

表2 WKNN參考點(diǎn)數(shù)量的選取及定位誤差

同理，由第3.2節(jié)對(duì)線性內(nèi)插法的介紹可知，為了在不增加定位成本的情況下提高定位精度，在WKNN算法的基礎(chǔ)上提出了線性內(nèi)插法。當(dāng)測(cè)試環(huán)境、K值以及參考點(diǎn)數(shù)量一定的情況下，影響基于線性內(nèi)插法改進(jìn)的WKNN算法定位結(jié)果的因素主要是N值的選?。篘值太小，造成定位精度提高得不明顯；N值太大，由于位置和接收信號(hào)強(qiáng)度的非線性關(guān)系造成定位精度降低。因此要根據(jù)具體的實(shí)驗(yàn)場(chǎng)景，合理地選擇N值的大小。對(duì)這種改進(jìn)算法的參考點(diǎn)數(shù)量取35個(gè)，對(duì)N選取不同的值進(jìn)行MATLAB仿真，N的選取及定位誤差分別見表3，仿真如圖6所示。由仿真結(jié)果可知，定位誤差并不是隨著N的增大而增大，而是有一個(gè)最佳值，因此要根據(jù)試驗(yàn)場(chǎng)景，合理地選擇N的大小，從而達(dá)到最佳定位效果。

圖5 WKNN法不同參考點(diǎn)數(shù)量仿真結(jié)果對(duì)比

表3 基于線性內(nèi)插法的WKNN不同N值及定位誤差

圖6 基于線性內(nèi)插法的WKNN不同N值仿真結(jié)果對(duì)比

最后，根據(jù)第3.1節(jié)對(duì)PCA的介紹可知，為了減少多徑效應(yīng)對(duì)定位造成的影響，在基于線性內(nèi)插法改進(jìn)的WKNN算法的基礎(chǔ)上增加了PCA，先對(duì)離線指紋庫(kù)數(shù)據(jù)進(jìn)行降維，去除干擾，再進(jìn)行定位，此時(shí)，選擇K=5，K=4，參考點(diǎn)的數(shù)目為35個(gè)，待測(cè)點(diǎn)數(shù)量為20個(gè)，并用MATLAB對(duì)比WKNN法和基于線性內(nèi)插法改進(jìn)的WKNN法，仿真結(jié)果如圖7所示，各個(gè)算法的定位誤差見表4。由仿真結(jié)果可知，PCA能進(jìn)一步提高定位的精確度，精度提高了4%左右。

表4 不同算法相同條件情況下的定位誤差

圖7 不同算法相同條件下定位誤差累計(jì)分布仿真對(duì)比

另外，對(duì)于WKNN法、基于線性內(nèi)插法改進(jìn)的WKNN法以及基于線性內(nèi)插和PCA改進(jìn)的WKNN法分別進(jìn)行20次測(cè)試，定位誤差對(duì)比如圖8所示。由圖8可知，基于線性內(nèi)插和PCA的WKNN匹配算法的定位誤差明顯比WKNN法的定位誤差低。

由上述對(duì)算法的仿真結(jié)果可知，基于線性內(nèi)插和PCA改進(jìn)的WKNN法能在減少定位成本的同時(shí)提高定位精度，該算法與WKNN法相比，平均定位精度大約提高了34.25%，但是，由于離線指紋庫(kù)是根據(jù)線性內(nèi)插法構(gòu)建，計(jì)算勢(shì)必帶來(lái)定位時(shí)間的消耗，進(jìn)而影響定位效率，用MATLAB中的tic和toc語(yǔ)句分別對(duì)WKNN法、基于線性內(nèi)插法改進(jìn)的WKNN法以及基于線性內(nèi)插和PCA改進(jìn)的WKNN法的效率進(jìn)行仿真，仿真時(shí)間見表5，結(jié)果顯示，該算法雖然以犧牲時(shí)間為代價(jià)提高定位精度，但消耗的時(shí)間處于可接受的范圍內(nèi)，說(shuō)明在滿足人們對(duì)定位的要求的同時(shí)提高了定位精度。

圖8 不同算法相同條件下各個(gè)待測(cè)點(diǎn)處定位誤差對(duì)比

表5 不同算法相同條件情況下的仿真時(shí)間

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

本文針對(duì)增加參考點(diǎn)耗時(shí)耗力以及多徑干擾問(wèn)題，在位置指紋定位算法的基礎(chǔ)上提出一種基于線性內(nèi)插和PCA改進(jìn)的WKNN定位方法。該算法將劃分好的網(wǎng)格點(diǎn)進(jìn)行進(jìn)一步的劃分，利用線性內(nèi)插法重新構(gòu)建離線指紋數(shù)據(jù)庫(kù)，并引入主成分分析法，減少多徑效應(yīng)對(duì)定位造成的影響。所提算法使用匹配定位估計(jì)，在減少定位成本的同時(shí)提高了定位精度。由仿真分析可知，所提算法的最大定位誤差為0.391 9 m，最小定位誤差為0.026 6 m，對(duì)于長(zhǎng)14 m、寬10 m的定位環(huán)境而言，最大誤差處于可接受范圍內(nèi)。

[1]陳錫劍,程良倫.基于RSSI的功率匹配定位算法的研究與實(shí)現(xiàn)[J].傳感技術(shù)學(xué)報(bào),2013,26(5):710-714. CHEN X J,CHENG L L.Research and implementation of power matching algorithm based on RSSI[J].Chinese Journal of Sensors and Actuators,2013,26(5):710-714.

[2]LU Y H,LAI C F.Path loss exponent estimation for indoor wireless sensor positioning[J].KSII Transactions on Internet and Information Systems,2010,4(3):243-256.

[3]PATWARI N,HERO A O,PERKINS M.Relative location estimation in wireless sensor networks[J].IEEE Transactions on Signal Processing,2003,51(8):2137-2147.

[4]葉蔚.室內(nèi)無(wú)線定位的研究[D].廣州:華南理工大學(xué),2010. YE W.Study on indoor wireless location[D].Guangzhou:South China University of Technology,2010.

[5]楊東勇,顧東袁,傅曉婕.一種基于RSSI相似度的室內(nèi)定位算法[J].傳感技術(shù)學(xué)報(bào),2009,22(2):264-268. YANG D Y,GU D Y,FU X J.An indoor location algorithm based on RSSI-similarity degree[J].Chinese Journal of Sensors and Actuators,2009,22(2):264-268.

[6]劉鵬,盧潭城,高翔.基于射頻識(shí)別的室內(nèi)定位技術(shù)綜述[J].太赫茲科學(xué)與電子信息學(xué)報(bào),2014(2):195-201. LIU P,LU T C,GAO X.A survey of indoor location technology based on radio frequency identification[J].Terahertz Science and Electronic Information,2014(2):195-201.

[7]梁瑩.INS/地磁匹配組合導(dǎo)航系統(tǒng)技術(shù)研究 [D].哈爾濱:哈爾濱工程大學(xué),2010. LIANG Y.Study ofINS/geomagnetic matching integrated navigation system technology [D].Harbin:Harbin Engineering University,2010.

[8]王欣.基于地磁場(chǎng)和RSSI的室內(nèi)定位算法設(shè)計(jì)與實(shí)現(xiàn)[D].杭州:杭州電子科技大學(xué),2014. WANG X.Design and implementation of indoor location algorithm based on geomagnetic field and RSSI[J].Hangzhou:Hangzhou University of Electronic Science and Technology,2014.

[9]JIANG S Y,PANG G S,WU M L.An improved K-nearest-neighbor algorithm for text categorization[J].Expert Systems with Applications,2012,29(1):1503-1509.

[10]詹杰,劉宏立,劉述鋼,等.基于RSSI的動(dòng)態(tài)權(quán)重定位算法研究[J].電子學(xué)報(bào),2011,39(1):82-88. ZHAN J,LIU H L,LIU S G,et al.Study algorithm based RSSI’s dynamic weights location[J].Journal of Electronics, 2011,39(1):82-88.

[11]HUANG C N,CHAN C T.ZigBee-based indoor location system by k-nearest neighbor algorithm with weighted RSSI[J].Procedia Computer Science,2011(5):58-65.

An improved indoor location algorithm based on linear interpolation

ZHANG Mengdan,LU Guangyue,WANG Honggang,LIU Jiming
Xi’an University of Posts and Telecommunications,Xi’an 710121,China

Aiming at the shortcomings of heavy workload in the off-line phase,limited positioning accuracy and poor robustness of indoor location fingerprint positioning technology,an improved fingerprint matching algorithm based on linear interpolation was proposed.Compared with the traditional location fingerprint positioning technology,it reduced the overall workload as well as the bad effects caused by muti-path effect.At last,a lab scene was set up to test the positioning performance of this algorithm.It is shown by the test that the average positioning accuracy of this algorithm has been improved by 34.25%compared with that of WKNN method,and the positioning accuracy error ratio of most points to be test is within 0.4 m,the positioning accuracy,robustness and adaptability in environment change were demonstrated.

indoor location,location fingerprint,weighted K-nearest neighbor,principal component analysis,linear interpolation

TN961

A

10.11959/j.issn.1000-0801.2017020

張夢(mèng)丹（1990-），女，西安郵電大學(xué)碩士生，主要研究方向?yàn)橥ㄐ啪W(wǎng)技術(shù)。

盧光躍（1971-），男，博士，西安郵電大學(xué)通信工程學(xué)院教授，主要研究方向?yàn)楝F(xiàn)代移動(dòng)通信中信號(hào)處理。

王宏剛（1977-），男，博士，西安郵電大學(xué)講師，主要研究方向?yàn)槲锢韺幽茉葱屎屯ㄐ艆f(xié)議的設(shè)計(jì)、RFID和無(wú)線定位。

劉繼明（1964-），男，博士，西安郵電大學(xué)教授，主要研究方向?yàn)橄乱淮浗粨Q核心技術(shù)。

2016-07-29；

2017-01-10

陜西省工業(yè)科技攻關(guān)項(xiàng)目（No.2014K05-09）；陜西省教育廳科學(xué)研究計(jì)劃項(xiàng)目（No.14JK1660）

Foundation Items：Shaanxi Industrial Science and Technology Project(No.2014K05-09),Shaanxi Science Research Program of Education Department(No.14JK1660)