李新春，侯 躍

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

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

李新春1，侯 躍2*

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

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

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

0 引言

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

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

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

1 傳統(tǒng)KNN算法

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

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

(1)

(2)

(3)

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

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

2 改進算法

2.1 AP的選擇

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

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

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

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

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

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

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

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

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

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

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

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

每個參考點都不會觀察到定位區(qū)域內(nèi)的所有AP。任何一個AP的缺失值被定義為沒有觀察到該AP的指紋。 因此，丟失值百分比高的AP應(yīng)被丟棄，因為它可能是不可靠的AP。在整個室內(nèi)定位環(huán)境中，缺失值百分比大于80%的AP應(yīng)被丟棄[9]。

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

(4)

具有RSS標準偏差的AP選擇可以過濾掉受干擾大的AP,因此預測位置將更加穩(wěn)定和準確。

2.2 SW-KNN

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

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

(5)

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

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

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

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

(6)

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

(7)

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

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

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

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

間隔數(shù)b越小，定位精度越高，但是計算開銷也越大。本文先將間隔數(shù)假定為b，在實驗中確定b值。

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

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

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

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

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

(8)

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

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

2.3 SW-KNN算法工作流程

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

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

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

3.1 實驗準備

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

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

圖6 實驗室布局Fig. 6 Layout of the laboratory

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

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

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

3.3 實驗結(jié)果及分析

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

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

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

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

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

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

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

圖8 實驗區(qū)域平面圖Fig. 8 Experimental area plan

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

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

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

4 結(jié)語

本文提出了WiFi室內(nèi)定位的AP選擇方法。首先使用箱形圖來減少多徑效應(yīng)的影響，然后又剔除了指紋庫中丟失率高的AP，最后使用標準差來分析RSS的變化，并選擇具有較小干擾的前n個AP進行位置估計。實驗結(jié)果表明，本文提出的A-KNN算法的性能優(yōu)于KNN算法。通過文獻[3]發(fā)現(xiàn)在經(jīng)典KNN算法中將信號強度定義為物理距離。因此，本文在改進AP選擇方法的同時構(gòu)建了一個基于RSS的縮放權(quán)重模型，提出了一種基于縮放權(quán)重的K最近鄰算法，以提高定位精度。實驗結(jié)果表明，本文提出的SW-KNN算法在相同的室內(nèi)環(huán)境下定位精度比KNN好得多。最后，又將SW-KNN算法應(yīng)用于其他室內(nèi)環(huá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] 李新春,劉杰.防接入點丟失的KNN室內(nèi)定位算法[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] 楊小亮,葉阿勇,凌遠景.基于閾值分類及信號強度加權(quán)的室內(nèi)定位算法[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] 原志強,趙春艷.兩種改進的模擬退火算法求解大值域約束滿足問題[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—)，男，遼寧朝陽人，高級工程師，主要研究方向：無線傳感器網(wǎng)絡(luò)、嵌入式系統(tǒng)、數(shù)字圖像處理； 侯躍(1992—)，女，河北唐山人，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)。

1001- 9081(2017)11- 3276- 05

10.11772/j.issn.1001- 9081.2017.11.3276

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

TP393.1

A