基于改進(jìn)AP選擇和K最近鄰法算法的室內(nèi)定位技術(shù)

李新春，侯 躍

(1.遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院，遼寧 葫蘆島 125105； 2.遼寧工程技術(shù)大學(xué) 研究生院，遼寧 葫蘆島 125105)

基于改進(jìn)AP選擇和K最近鄰法算法的室內(nèi)定位技術(shù)

李新春1，侯 躍2*

(1.遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院，遼寧 葫蘆島 125105； 2.遼寧工程技術(shù)大學(xué) 研究生院，遼寧 葫蘆島 125105)

針對(duì)復(fù)雜的室內(nèi)環(huán)境和在傳統(tǒng)K最近鄰法(KNN)算法中認(rèn)為信號(hào)差相等時(shí)物理距離就相等兩個(gè)問(wèn)題，提出了一種新的接入點(diǎn)(AP)選擇方法和基于縮放權(quán)重的KNN室內(nèi)定位算法。首先,改進(jìn)AP的選擇方法，使用箱形圖過(guò)濾接收信號(hào)強(qiáng)度(RSS)的異常值，初步建立指紋庫(kù), 剔除指紋庫(kù)中丟失率高的AP, 使用標(biāo)準(zhǔn)偏差分析RSS的變化，選擇干擾較小的前n個(gè)AP; 其次，在傳統(tǒng)的KNN算法中引入縮放權(quán)重，構(gòu)建一個(gè)基于RSS的縮放權(quán)重模型; 最后，計(jì)算出獲得最小有效信號(hào)距離的前K個(gè)參考點(diǎn)坐標(biāo)，得到未知位置坐標(biāo)。定位仿真實(shí)驗(yàn)中，僅對(duì)AP選擇方法進(jìn)行改進(jìn)的算法平均定位誤差比傳統(tǒng)的KNN算法降低了21.9%，引入縮放權(quán)重算法的平均定位誤差為1.82 m，比傳統(tǒng)KNN降低了53.6%。

K最近鄰法算法；室內(nèi)定位；箱形圖；標(biāo)準(zhǔn)偏差；縮放權(quán)重；定位精度

0 引言

室內(nèi)定位近年來(lái)受到越來(lái)越多的關(guān)注。基于WiFi框架的室內(nèi)定位系統(tǒng)由于無(wú)需添加額外的硬件、低成本、廣泛部署等優(yōu)點(diǎn)已被廣泛應(yīng)用，因?yàn)閃iFi網(wǎng)絡(luò)在許多地方變得相當(dāng)普遍，因此，基于WiFi技術(shù)的服務(wù)和應(yīng)用越來(lái)越受歡迎。大多數(shù)WiFi室內(nèi)定位系統(tǒng)都利用指紋技術(shù)。基于WiFi的定位系統(tǒng)在室內(nèi)環(huán)境中采集檢測(cè)到的接入點(diǎn)(Access Point, AP)的接收信號(hào)強(qiáng)度(Received Signal Strength, RSS)值，建立射頻指紋庫(kù)，然后使用模式匹配的方法來(lái)估計(jì)用戶(hù)的位置。然而，并非所有收集的RSS值對(duì)估計(jì)過(guò)程都有顯著貢獻(xiàn)，受到多徑效應(yīng)的影響產(chǎn)生不穩(wěn)定的RSS值[1]，最終會(huì)降低定位精度。類(lèi)似地，并非所有檢測(cè)到的AP都要參與對(duì)未知位置的定位，一些檢測(cè)到的AP可能在指紋庫(kù)中丟失率較高或者受到干擾較大[2]，使得在位置估測(cè)中不僅不會(huì)提高定位精度反而會(huì)增加額外的計(jì)算開(kāi)銷(xiāo)。考慮到這些點(diǎn)，本文從指紋庫(kù)中去除那些無(wú)用的RSS值和AP。

K最近鄰法(KNearest Neighbor,KNN)算法廣泛應(yīng)用于室內(nèi)定位系統(tǒng)中，在傳統(tǒng)的KNN算法中，將信號(hào)強(qiáng)度定義為物理距離，即當(dāng)信號(hào)差相等時(shí)就被認(rèn)定為物理距離相等。然而在復(fù)雜的室內(nèi)環(huán)境中，并不能這樣認(rèn)定[3]。在文獻(xiàn)[4]中指出在不同距離區(qū)間內(nèi)，RSS 信號(hào)值衰減的幅度大小不同，即在各距離區(qū)間內(nèi)兩區(qū)間端點(diǎn) RSS信號(hào)差值與該距離區(qū)間長(zhǎng)度的斜率是不同的。為了提高定位精度，如何解決這一關(guān)鍵性問(wèn)題值得深入研究。

為了解決上述問(wèn)題，本文先對(duì)AP的選擇方法進(jìn)行了改進(jìn)，選取穩(wěn)定性高的RSS值和丟失率低、干擾小的AP。接著又提出了一種基于縮放權(quán)重的KNN算法(Scale WeightKNN, SW-KNN)，在估計(jì)兩個(gè)RSS向量的有效信號(hào)距離時(shí)，在不同的信號(hào)強(qiáng)度下給信號(hào)差值分配不同的權(quán)重。為了計(jì)算有效信號(hào)距離，建立了一個(gè)縮放權(quán)重模型。

1 傳統(tǒng)KNN算法

KNN是數(shù)據(jù)挖掘領(lǐng)域中普遍而強(qiáng)大的分類(lèi)算法，由于其簡(jiǎn)單性，已被廣泛應(yīng)用于許多領(lǐng)域。最近鄰算法首先由蓋和哈特在1967年提出[4]。KNN是一種簡(jiǎn)單、直觀的算法，適用于幾乎所有類(lèi)型的數(shù)據(jù)結(jié)構(gòu)。它第一次在無(wú)線(xiàn)電探測(cè)和測(cè)距(Radio Detection And Ranging，RADAR)[5]中用于室內(nèi)定位系統(tǒng)，首先計(jì)算未知位置的RSS向量和每個(gè)指紋之間的信號(hào)距離，然后返回K個(gè)最近鄰指紋。每個(gè)指紋是預(yù)先選擇的參考點(diǎn)，并且由從不同AP收集的平均RSS值的向量表示?；贙NN傳統(tǒng)的室內(nèi)定位通常由兩個(gè)階段組成：離線(xiàn)階段和在線(xiàn)階段[6]。

在離線(xiàn)階段，目標(biāo)區(qū)域通常覆蓋有一組預(yù)定的網(wǎng)格點(diǎn)(已知坐標(biāo))，稱(chēng)為參考點(diǎn)(Reference Point, RP)，參考點(diǎn)集合為L(zhǎng)={li=(xi,yi),i=1,2,…,l}，其中l(wèi)為RP總數(shù)，(xi,yi)表示第i個(gè)參考點(diǎn)的二維物理空間坐標(biāo)。n為待定區(qū)域內(nèi)AP總數(shù)，AP集合為A={AP1,AP2,…,APn}。在li處測(cè)量對(duì)各AP的RSS，獲得一個(gè)參考數(shù)據(jù)ri=(ri1,ri2,…,rij,…,rin)，其中rij代表在li處采集APj的RSS的均值。將(li,ri)存入指紋庫(kù)中，所有參考點(diǎn)重復(fù)上述步驟以完成射頻指紋庫(kù)的建立。

(1)

(2)

(3)

在KNN中，本文發(fā)現(xiàn)具有最小信號(hào)距離的RP可能不是具有最小幾何距離的RP。這是因?yàn)槭?1)認(rèn)為在某種程度上信號(hào)差異和物理距離之間的關(guān)系與實(shí)際的信號(hào)強(qiáng)度無(wú)關(guān)。相反，式(1)中只認(rèn)為，信號(hào)距離Di僅與RSS差值rij-oj有關(guān)。 因此，無(wú)論實(shí)際RSS值oj是什么，RSS差值的所有權(quán)重都被設(shè)置為1。

為了解決上述問(wèn)題，本文引入基于信號(hào)強(qiáng)度的縮放權(quán)重，用于計(jì)算不同信號(hào)強(qiáng)度的有效信號(hào)差異，作為比較信號(hào)之間相似性的新特征。

2 改進(jìn)算法

2.1 AP的選擇

由于室內(nèi)環(huán)境復(fù)雜，例如其他無(wú)線(xiàn)設(shè)備的干擾，人體對(duì)信號(hào)強(qiáng)度的吸收和由于反射造成的多徑效應(yīng)[7]，都會(huì)對(duì)定位精度產(chǎn)生影響。20個(gè)移動(dòng)設(shè)備在同一個(gè)未知位置收集來(lái)自5個(gè)不同AP的RSS值，實(shí)驗(yàn)結(jié)果如圖1所示。在圖中可以觀察到，由于室內(nèi)環(huán)境的干擾，20個(gè)移動(dòng)設(shè)備在同一未知位置收集來(lái)自同一個(gè)AP的RSS值并不是相等的，有的甚至?xí)l(fā)生大幅度的突變，本文稱(chēng)其為RSS的異常值。RSS異常值會(huì)使定位精度降低，所以如何處理不穩(wěn)定的RSS值是指紋定位過(guò)程中需要解決的關(guān)鍵問(wèn)題之一。

圖1 不同移動(dòng)設(shè)備收集的RSS值的變化Fig. 1 Variations of RSS by 20 mobile devices for 5 APs

針對(duì)上述問(wèn)題，定位系統(tǒng)中使用箱形圖[8]的方法過(guò)濾RSS異常值。箱形圖計(jì)算過(guò)程如下：

1)收集在同一未知位置處來(lái)自同一個(gè)AP的20個(gè)RSS樣本值并按升序排列。

2)找到RSS樣本值的第一四分位和第三四分位，記為Q1和Q3。

3)計(jì)算間距范圍，四分位數(shù)的間距(Inter Quartile Range,IQR)為:IQR=Q3-Q1。

4)異常邊界設(shè)置為C1=Q1-1.5IQR，C2=Q3+1.5IQR。

RSS異常值濾波方法如圖2所示。

圖2 使用箱形圖過(guò)濾RSS異常值Fig. 2 RSS outlier filtering with box plot

如果RSS樣本值小于C1或者大于C2，系統(tǒng)將其認(rèn)定為異常值并丟棄。RSS異常濾波方法使得收集到的RSS樣本值均為正常值。

最后，計(jì)算RSS樣本值的均值作為指紋信息存儲(chǔ)到數(shù)據(jù)庫(kù)中，稱(chēng)為射頻指紋數(shù)據(jù)庫(kù), 在在線(xiàn)定位階段用于處理模式匹配。

在室內(nèi)環(huán)境中有很多可以檢測(cè)到的AP，由于每一個(gè)AP都可以提供指紋信息，所以在傳統(tǒng)的指紋定位系統(tǒng)中在定位區(qū)域部署了很多AP以提高定位精度，并且在在線(xiàn)定位階段使用所有可以檢測(cè)到的AP估計(jì)未知位置，然而，被多徑效應(yīng)影響的AP不僅不會(huì)提高定位精度反而會(huì)降低定位精度。此外，越多的AP用于定位，計(jì)算量也會(huì)越大。為了在提高定位精度的同時(shí)還能減少計(jì)算量，最好選擇丟失率低和干擾較小的AP。

每個(gè)參考點(diǎn)都不會(huì)觀察到定位區(qū)域內(nèi)的所有AP。任何一個(gè)AP的缺失值被定義為沒(méi)有觀察到該AP的指紋。 因此，丟失值百分比高的AP應(yīng)被丟棄，因?yàn)樗赡苁遣豢煽康腁P。在整個(gè)室內(nèi)定位環(huán)境中，缺失值百分比大于80%的AP應(yīng)被丟棄[9]。

為了選擇干擾較小的AP，可以通過(guò)在在線(xiàn)定位階段計(jì)算AP的RSS標(biāo)準(zhǔn)偏差(Standard Deviation, SD)。RSS標(biāo)準(zhǔn)偏差可以辨別每個(gè)AP的受干擾程度。較小的SD值表示從AP接收的RSS值偏離平均值小，AP的干擾也小，適合于處理模式匹配：首先，系統(tǒng)通過(guò)RSS異常過(guò)濾的方法過(guò)濾掉不正常的RSS；第二，丟棄丟失率高的AP；第三，計(jì)算來(lái)自每個(gè)AP的RSS值的SD，然后按照SD值將所有可用的AP按升序排列；最后，選擇前n個(gè)AP用于處理模式匹配。假定定位區(qū)域中當(dāng)前可用的AP總共為m，則SD計(jì)算如式(4)所示：

(4)

具有RSS標(biāo)準(zhǔn)偏差的AP選擇可以過(guò)濾掉受干擾大的AP,因此預(yù)測(cè)位置將更加穩(wěn)定和準(zhǔn)確。

2.2 SW-KNN

與經(jīng)典KNN算法相比，SW-KNN具有以下兩個(gè)增強(qiáng)功能。首先，通過(guò)引入縮放權(quán)重來(lái)計(jì)算不同信號(hào)強(qiáng)度的有效信號(hào)差異，從而建立基于RSS的縮放權(quán)重模型。其次，計(jì)算移動(dòng)設(shè)備在未知位置測(cè)量獲得的RSS和指紋庫(kù)中每個(gè)指紋之間的有效信號(hào)差異，使用上述縮放權(quán)重來(lái)查找K個(gè)最近鄰指紋。

基于RSS的縮放權(quán)重模型用于計(jì)算有效信號(hào)距離，式(1)可以改寫(xiě)為：

(5)

式中n為經(jīng)過(guò)AP選擇后參與位置估計(jì)的AP數(shù)，其余各變量與式(1)中的含義相同。新提出的縮放權(quán)重函數(shù)w(·)，它的值隨移動(dòng)設(shè)備在未知位置處采樣的實(shí)際RSS值oj而變化。由于引入基于信號(hào)強(qiáng)度差的縮放權(quán)重，由式(5)計(jì)算出的有效信號(hào)距離可以比式(1)更精確地表示移動(dòng)設(shè)備與第i個(gè)參考點(diǎn)之間的信號(hào)距離。

接下來(lái)，討論如何獲得縮放權(quán)重函數(shù)w(·)，這是SW-KNN算法的關(guān)鍵部分，包含兩個(gè)步驟：確定縮放權(quán)重函數(shù)形式和調(diào)整參數(shù)。

2.2.1 確定縮放權(quán)重函數(shù)形式

由于室內(nèi)復(fù)雜的無(wú)線(xiàn)電環(huán)境，很難為w(·)給出一個(gè)固定的形式。為了處理這種復(fù)雜的情況，本文將整個(gè)RSS空間劃分為b個(gè)相等的非重疊間隔，并嘗試為每個(gè)RSS間隔找到一個(gè)常量縮放權(quán)重。因此，本文將RSS值換算成縮放權(quán)重，如式(6)所示：

(6)

其中：x是真實(shí)的RSS值，w(x)表示在信號(hào)強(qiáng)度為x處實(shí)際信號(hào)差的縮放權(quán)重。讓Ac表示第c個(gè)RSS間隔(1≤c≤b)。αc是區(qū)間Ac的系數(shù)，χc(x)是區(qū)間Ac的指標(biāo)函數(shù)，得到式(7)：

(7)

例如，移動(dòng)設(shè)備采集的RSS值屬于間隔Ac。根據(jù)式(7)，χc(x)的值為1，將所有其他的χ(x)值設(shè)置為零。然后計(jì)算w(x)的結(jié)果等于αc，αc是在RSS值為x處用于計(jì)算有效信號(hào)距離的縮放權(quán)重。

2.2.2 調(diào)整參數(shù)

現(xiàn)在的問(wèn)題是如何調(diào)整間隔數(shù)b和間隔系數(shù)α的值，構(gòu)建縮放權(quán)重模型，以實(shí)現(xiàn)提高定位精度，圖3為縮放權(quán)重模型。

圖3 縮放權(quán)重模型Fig. 3 Scale weight model

間隔數(shù)b越小，定位精度越高，但是計(jì)算開(kāi)銷(xiāo)也越大。本文先將間隔數(shù)假定為b，在實(shí)驗(yàn)中確定b值。

這部分主要探討如何調(diào)整間隔的系數(shù)，這通常是參數(shù)優(yōu)化問(wèn)題。本文使用模擬退火法(Simulated Annealing, SA)[10]來(lái)調(diào)整系數(shù)。圖4給出了調(diào)整系數(shù)的流程。

圖4 調(diào)整系數(shù)流程Fig. 4 Flow chart of coefficient adjustment

根據(jù)流程可以看出主要的工作流程分為4個(gè)部分：準(zhǔn)備、評(píng)估、優(yōu)化和驗(yàn)證。關(guān)于4個(gè)部分如何工作的細(xì)節(jié)描述如下：

1)準(zhǔn)備。為了調(diào)整縮放模型的參數(shù)，本文使用holdout方法[11]將無(wú)線(xiàn)電圖分成兩個(gè)部分：訓(xùn)練集、測(cè)試集1和測(cè)試集2。訓(xùn)練集中是已知坐標(biāo)的參考點(diǎn); 測(cè)試集1用于在不斷調(diào)整系數(shù)的過(guò)程中評(píng)估定位精度，最終實(shí)現(xiàn)提高定位精度的目的;測(cè)試集2用于對(duì)獲得系數(shù)進(jìn)行驗(yàn)證。

2)評(píng)估。在隨機(jī)獲得一組新的系數(shù)后，將測(cè)試集1輸入到縮放權(quán)重模型中，以生成測(cè)試集1中每個(gè)位置的估計(jì)坐標(biāo)，通過(guò)式(8)計(jì)算距離誤差的總和來(lái)評(píng)估定位精度。

(8)

3)優(yōu)化。使用模擬退火法搜索定位精度更高的一組系數(shù)。設(shè)置初始溫度T0=100，最大迭代次數(shù)fmax=1 000。在每次迭代過(guò)程中，部分系數(shù)是隨機(jī)變化的。如果新的誤差較小，則新系數(shù)將成為當(dāng)前的系數(shù); 如果不是，在一定的概率下新系數(shù)還將成為當(dāng)前系數(shù)。該過(guò)程一直持續(xù)到迭代次數(shù)達(dá)到最大為止。

4)驗(yàn)證。在這個(gè)階段，本文進(jìn)一步使用測(cè)試集2來(lái)驗(yàn)證從前一階段獲得系數(shù)的縮放權(quán)重模型的性能。

2.3 SW-KNN算法工作流程

基于SW-KNN的室內(nèi)定位算法同樣主要由兩部分組成。在離線(xiàn)階段，首先，本文使用箱形圖去除接收來(lái)自AP的RSS樣本的異常值，以穩(wěn)定RSS值；然后，剔除丟失率高的AP。在在線(xiàn)階段，首先過(guò)濾RSS異常值并使用SD來(lái)分析RSS的變化，并選擇干擾較小的前n個(gè)AP；接著使用縮放權(quán)重模型計(jì)算未知位置的RSS和指紋庫(kù)中每個(gè)指紋之間的有效信號(hào)距離；最后收集導(dǎo)致最小有效信號(hào)距離的前K個(gè)參考點(diǎn)坐標(biāo)，從而得到未知位置坐標(biāo)。算法框架流程如圖5所示。

圖5 SW-KNN算法流程Fig. 5 Flow chart of SW-KNN algorithm

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

3.1 實(shí)驗(yàn)準(zhǔn)備

本文在學(xué)校實(shí)驗(yàn)室進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)室大小是10 m×15 m，面積150 m2。實(shí)驗(yàn)室中有20套桌椅，人在實(shí)驗(yàn)室走動(dòng)不頻繁。訓(xùn)練集中有45個(gè)參考點(diǎn)，且每個(gè)參考點(diǎn)之間間隔1.5 m。測(cè)試集有280個(gè)參考點(diǎn)，每個(gè)參考點(diǎn)間的距離為0.5 m。所有的參考點(diǎn)均分布在13×25的網(wǎng)格交叉點(diǎn), 如圖6所示。此設(shè)置確保訓(xùn)練集和測(cè)試集中參考點(diǎn)不重疊，模擬現(xiàn)實(shí)場(chǎng)景。測(cè)試集隨機(jī)分為兩個(gè)：測(cè)試集1和測(cè)試集2。在每個(gè)參考點(diǎn)采樣獲得50個(gè)RSS值的向量。

本文使用三星手機(jī)作為信號(hào)測(cè)量的移動(dòng)設(shè)備。在離線(xiàn)階段檢測(cè)到22個(gè)不同的AP，實(shí)驗(yàn)中所有的AP都是預(yù)先存在的，并不會(huì)部署其他AP，其硬件類(lèi)型和位置是未知的。最鄰近點(diǎn)選擇太多可能降低定位的準(zhǔn)確性，因?yàn)橐恍┳罱狞c(diǎn)可能距離當(dāng)前位置太遠(yuǎn)。KNN算法的K值一般選取3或4將產(chǎn)生最佳結(jié)果[12]，所以本文將為實(shí)驗(yàn)設(shè)置K=3。為了便于比較，本文把基于改進(jìn)AP選擇的傳統(tǒng)KNN算法定義為A-KNN。本文將使用平均定位誤差和累積分布函數(shù)(Cumulative Distribution Function, CDF)作為評(píng)估指標(biāo)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行驗(yàn)證。

圖6 實(shí)驗(yàn)室布局Fig. 6 Layout of the laboratory

3.2 調(diào)整間隔數(shù)

本文使用不同數(shù)量的間隔來(lái)探討間隔數(shù)對(duì)SW-KNN性能的影響。表1總結(jié)了這些設(shè)置下的定位精度和優(yōu)化時(shí)間。 可以看出，隨著間隔數(shù)的增加，平均定位誤差呈下降趨勢(shì)，但在20個(gè)間隔后下降趨勢(shì)不明顯, 優(yōu)化時(shí)間沒(méi)有顯著變化。所以為了實(shí)現(xiàn)提高定位精度的同時(shí)，運(yùn)算量也不會(huì)太大，本文選取間隔數(shù)n=20。

表1 間隔數(shù)量對(duì)定位精度和時(shí)間的影響Tab. 1 Impact of number of intervals on positioning precision and time

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

表2為測(cè)試集1獲得的系數(shù)，本文使用測(cè)試集1中獲得的系數(shù)對(duì)測(cè)試集2進(jìn)行操作，以評(píng)估它們是否適合于其他測(cè)量環(huán)境中的參考點(diǎn)。定位精度為在測(cè)試集2中偏離實(shí)際位置距離的平均定位誤差?；跍y(cè)試集2，對(duì)KNN、A-KNN與SW-KNN算法進(jìn)行比較。

表2 不同間隔的系數(shù)值Tab. 2 Coefficient values for different intervals

表3顯示了三種算法平均定位誤差的比較?？梢钥吹紸-KNN比KNN低21.9%，而SW-KNN比KNN低53.6%。

如圖7所示，表示三種不同算法距離誤差的累積分布函數(shù)。很顯然，SW-KNN算法的定位精度最高，而且改進(jìn)AP選擇的方法也提高了KNN算法的定位精度，從而使得 SW-KNN算法的定位精度更高。以分布概率為0.8為例，SW-KNN算法的誤差距離大概在2 m左右，而KNN的誤差距離超過(guò)了 5 m。

表3 三種算法的平均定位誤差比較Tab. 3 Comparison of average positioning error by three algorithms

圖7 三種算法誤差距離的累積分布概率(實(shí)驗(yàn)150 m2)Fig. 7 CDF of error distances by three algorithms in 150 m2 laboratory

通過(guò)測(cè)試集2驗(yàn)證，SW-KNN算法使定位精度有了顯著提高，接下來(lái)本文將該算法應(yīng)用到實(shí)際環(huán)境中，驗(yàn)證其是否適用于其他室內(nèi)環(huán)境。如圖8所示，實(shí)驗(yàn)區(qū)域?yàn)橐粋€(gè)約1 500 m2的典型室內(nèi)環(huán)境，包括1個(gè)教室、2個(gè)辦公室、8個(gè)實(shí)驗(yàn)室、1個(gè)娛樂(lè)區(qū)和1個(gè)走廊。區(qū)域內(nèi)可見(jiàn)AP總數(shù)為53個(gè)。離線(xiàn)階段和在線(xiàn)階段的數(shù)據(jù)采集使用同一部三星手機(jī)。離線(xiàn)階段在實(shí)驗(yàn)區(qū)域內(nèi)共選定了120個(gè)參考點(diǎn)。兩個(gè)最近鄰參考點(diǎn)間距最小為1 m，最大為5.2 m。參考點(diǎn)最少有3個(gè)AP可見(jiàn)，最多有15個(gè)AP可見(jiàn)。在每個(gè)參考點(diǎn)采樣獲得50個(gè)RSS值的向量，首先過(guò)濾掉RSS異常值并將其余數(shù)據(jù)取平均值得到一條參考數(shù)據(jù)與位置信息組成一條射頻指紋存入射頻指紋庫(kù)，再剔除指紋庫(kù)丟失率高的AP建立最終的指紋庫(kù)。

圖8 實(shí)驗(yàn)區(qū)域平面圖Fig. 8 Experimental area plan

在在線(xiàn)階段，選取50個(gè)測(cè)試點(diǎn)(含測(cè)試起點(diǎn)和測(cè)試終點(diǎn))。每次測(cè)試由測(cè)試起點(diǎn)開(kāi)始，以一條固定的路徑在實(shí)驗(yàn)區(qū)域內(nèi)移動(dòng)，每經(jīng)過(guò)一個(gè)測(cè)試點(diǎn)采集一個(gè)觀測(cè)值并將對(duì)應(yīng)的位置信息保存以便計(jì)算定位誤差，進(jìn)入房間后均以原路返回。一次測(cè)試中所有測(cè)試點(diǎn)均被經(jīng)過(guò)2次，共進(jìn)行10次測(cè)試，在每個(gè)測(cè)試點(diǎn)得到20個(gè)RSS向量。同樣過(guò)濾RSS異常值后求均值再將離線(xiàn)階段未剔除的AP依據(jù)SD值進(jìn)行選取用于處理模式匹配。最后，根據(jù)之前實(shí)驗(yàn)中獲得的縮放權(quán)重系數(shù)，為每一個(gè)RSS值分配權(quán)重，用式(5)、式(2)和式(3)即可得到估計(jì)位置。

如圖9所示，在該實(shí)驗(yàn)環(huán)境下，對(duì)KNN、A-KNN和SW-KNN三種算法的定位精度進(jìn)行了比較，實(shí)驗(yàn)結(jié)果表明，SW-KNN算法定位精度最高，該算法適用于其他的室內(nèi)環(huán)境。

圖9 三種算法誤差距離的累積分布概率(1 500 m2實(shí)驗(yàn)區(qū)域)Fig. 9 CDF of error distances by three algorithms in 1 500 m2 experimental area

4 結(jié)語(yǔ)

本文提出了WiFi室內(nèi)定位的AP選擇方法。首先使用箱形圖來(lái)減少多徑效應(yīng)的影響，然后又剔除了指紋庫(kù)中丟失率高的AP，最后使用標(biāo)準(zhǔn)差來(lái)分析RSS的變化，并選擇具有較小干擾的前n個(gè)AP進(jìn)行位置估計(jì)。實(shí)驗(yàn)結(jié)果表明，本文提出的A-KNN算法的性能優(yōu)于KNN算法。通過(guò)文獻(xiàn)[3]發(fā)現(xiàn)在經(jīng)典KNN算法中將信號(hào)強(qiáng)度定義為物理距離。因此，本文在改進(jìn)AP選擇方法的同時(shí)構(gòu)建了一個(gè)基于RSS的縮放權(quán)重模型，提出了一種基于縮放權(quán)重的K最近鄰算法，以提高定位精度。實(shí)驗(yàn)結(jié)果表明，本文提出的SW-KNN算法在相同的室內(nèi)環(huán)境下定位精度比KNN好得多。最后，又將SW-KNN算法應(yīng)用于其他室內(nèi)環(huán)境中，實(shí)驗(yàn)結(jié)果表明，該算法在室內(nèi)環(huán)境下都可以提高定位精度。

References)

[1] JHUANG F M, HUNG C F, TUAN C C, et al. An AP selection with RSS standard deviation for indoor positioning in WiFi[C]// Proceedings of the 2015 9th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing. Piscataway, NJ: IEEE, 2015: 403-407.

[2] 李新春,劉杰.防接入點(diǎn)丟失的KNN室內(nèi)定位算法[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(8):90-96. (LI X C, LIU J. Access point lost prevented KNN indoor positioning algorithm [J]. Computer Engineering and Applications, 2016, 52(8): 90-96.)

[3] BAHL P, PADMANABHAN V N. Radar: an in-building RF-based user location and tracking system [C]// Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway, NJ: IEEE, 2000: 775-784.

[4] 楊小亮,葉阿勇,凌遠(yuǎn)景.基于閾值分類(lèi)及信號(hào)強(qiáng)度加權(quán)的室內(nèi)定位算法[J].計(jì)算機(jī)應(yīng)用,2013,33(10):2711-2714. (YANG X L, YE A Y, LING Y J. Indoor localization algorithm based on threshold classification and signal strength weighting [J]. Journal of Computer Applications, 2013, 33(10): 2711-2714.)

[5] COVER T, HART P. Nearest neighbor pattern classification [J]. IEEE Transactions on Information Theory, 1967, 13(1): 21-27.

[6] ZANG B, HUANG R C, WANG L, et al. An improved KNN algorithm based on minority class distribution for imbalanced dataset[C]// Proceedings of the 2016 International Computer Symposium. Piscataway, NJ: IEEE, 2016: 696-700.

[7] WANG F, HUANG Z, YU H, et al. EESM-based fingerprint algorithm for WiFi indoor positioning system [C]// Proceedings of the 2013 IEEE International Conference on Communications in China. Piscataway, NJ: IEEE, 2013: 674-679.

[8] 林子.用Dundas制作箱形圖Box Plot [EB/OL]. (2007- 09- 04) [2017- 04- 25]. http://www.cnblogs.com/linfuguo/archive/2007/09/04/878345.html. (LIN Z. Make box plot with Dundas [EB/OL]. (2007- 09- 04) [2017- 04- 25]. http://www.cnblogs.com/linfuguo/archive/2007/09/04/878345.html.)

[9] SAMIH E, JOAO P, FILIPE M. Removing useless APs and fingerprints from WiFi indoor positioning radio maps [C]// Proceedings of the 2013 International Conference on Indoor Positioning and Indoor Navigation. Piscataway, NJ: IEEE, 2013: 1-7.

[10] 原志強(qiáng),趙春艷.兩種改進(jìn)的模擬退火算法求解大值域約束滿(mǎn)足問(wèn)題[J].計(jì)算機(jī)應(yīng)用研究,2017,34(12):1-9.(YUAN Z Q, ZHAO C Y. Two improved simulated annealing algorithms for solving constraint satisfaction problems with large domains [J]. Application Research of Computers, 2017, 34(12): 1-9.)

[11] DEVIJVER P A, KITTLER J. Pattern recognition: a statistical approach [J]. Image and Vision Computing, 1985, 3(2): 87-88.

[12] LI B, SALTER J, DEMPSTER A G, et al. Indoor positioning techniques based on wireless LAN [C]// Proceedings of the 2006 IEEE International Conference on Wireless Broadband and Ultra Wideband Communications. Piscataway, NJ: IEEE, 2006: 13-16.

LIXinchun, born in 1963, senior engineer. His research interests include wireless sensor network, embedded system, digital image processing.

HOUYue, born in 1992, M. S. candidate. Her research interest include wireless sensor network.

IndoorpositioningtechnologybasedonimprovedaccesspointselectionandKnearestneighboralgorithm

LI Xinchun1, HOU Yue2*

(1.SchoolofElectricsandInformationEngineering,LiaoningTechnicalUniversity,HuludaoLiaoning125105,China;2.GraduateSchool,LiaoningTechnicalUniversity,HuludaoLiaoning125105,China)

Since indoor environment is complex and equal signal differences are assumed to equal physical distances in the traditionalKNearest Neighbor (KNN) approach, a new Access Point (AP) selection method andKNN indoor positioning algorithm based on scaling weight were proposed. Firstly, in the improved AP selection method, box plot was used to filter

Signal Strength (RSS) outliers and create a fingerprint database. The AP with high loss rate in the fingerprint database were removed. The standard deviation was used to analyze the variations of RSS, and TOP-NAPs with less interference were selected. Secondly, the scaling weight was introduced into the traditionalKNN algorithm to construct a scaling weight model based on RSS. Finally, the firstKreference points which obtained the minimum effective signal distance were calculated to get the unknown position coordinates. In the localization simulation experiments, the mean of error distance by improved AP selection method is 21.9% lower than that byKNN. The mean of error distance by the algorithm which introduced scaling weight is 1.82 m, which is 53.6% lower than that byKNN.

KNearest Neighbor (KNN) algorithm; indoor positioning; box plot; standard deviation; scaling weight; positioning accuracy

2017- 05- 04;

2017- 06- 27。

李新春(1963—)，男，遼寧朝陽(yáng)人，高級(jí)工程師，主要研究方向：無(wú)線(xiàn)傳感器網(wǎng)絡(luò)、嵌入式系統(tǒng)、數(shù)字圖像處理； 侯躍(1992—)，女，河北唐山人，碩士研究生，主要研究方向：無(wú)線(xiàn)傳感器網(wǎng)絡(luò)。

1001- 9081(2017)11- 3276- 05

10.11772/j.issn.1001- 9081.2017.11.3276

(*通信作者電子郵箱839714953@qq.com)

TP393.1

A