離散度WKNN位置指紋Wi-Fi定位算法

田洪亮，錢志鴻，梁 瀟，王義君，王 雪

(1. 吉林大學 通信工程學院，長春130012；2. 東北電力大學 信息工程學院，吉林 吉林132012；3.長春理工大學 電子信息工程學院，長春 130022)

離散度WKNN位置指紋Wi-Fi定位算法

田洪亮1,2，錢志鴻1，梁 瀟1，王義君3，王 雪1

(1. 吉林大學 通信工程學院，長春130012；2. 東北電力大學 信息工程學院，吉林 吉林132012；3.長春理工大學 電子信息工程學院，長春 130022)

為改善加權(quán)K近鄰位置指紋定位算法在室內(nèi)環(huán)境復雜時的定位性能，提出一種以位置指紋離散度作為權(quán)值參考的改進加權(quán)K近鄰位置指紋定位算法. 算法在離線位置指紋數(shù)據(jù)庫建立階段采用K-means聚類算法對位置指紋進行聚類，來降低搜索位置指紋庫的計算量. 從離線位置指紋庫中選取K個與在線實測Wi-Fi信號強度信息最相似的位置指紋，比較其離散程度，將離散程度小的位置指紋賦予較高的加權(quán)系數(shù)，以減小原加權(quán)K近鄰算法在室內(nèi)復雜環(huán)境信號強度隨距離變化較大情況下帶來的位置估算誤差. 對離散度加權(quán)K近鄰算法時間復雜度的分析表明，其計算量小于原加權(quán)K近鄰算法；實際環(huán)境實驗結(jié)果表明，離散度加權(quán)K近鄰算法具有更高的定位精度，且定位誤差波動較小.

無線定位；位置指紋；Wi-Fi；接收信號強度指示；離散度

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，無數(shù)智能節(jié)點通過無線通信技術(shù)連接在一起，形成了無所不能的物聯(lián)網(wǎng)[1]. 其中位置服務(wù)[1-2]是物聯(lián)網(wǎng)面向用戶的關(guān)鍵需求之一，而位置服務(wù)主要依賴于無線定位技術(shù). 無線定位技術(shù)從地理位置上可分為室內(nèi)定位以及室外定位. 室外定位一般通過衛(wèi)星導航系統(tǒng)輔助以AGPS進行定位，具有定位精度適中、定位速度快等優(yōu)點. 然而衛(wèi)星信號穿透能力弱，受到建筑物外墻的阻擋，無法為室內(nèi)設(shè)備提供定位服務(wù). 室內(nèi)無線信號環(huán)境相對于室外要復雜得多. 相對于室外環(huán)境，室內(nèi)環(huán)境有建筑物墻體、房間布局等帶來的無線信號多徑效應(yīng)影響以及多種室內(nèi)無線設(shè)備對定位信號帶來的干擾等，這與室外定位具有很大的不同.

隨著智能手機等內(nèi)置無線接入的設(shè)備普及率的提高，Wi-Fi信號已經(jīng)廣泛分布在大多數(shù)室內(nèi)環(huán)境，學者們提出了多種利用Wi-Fi信號進行室內(nèi)定位的技術(shù)[3-4]，包括到達角度(AOA)定位、到達時間(TOA)定位、到達時間差(TDOA)定位、信號強度(RSSI)定位、位置指紋定位[5]等. 上述室內(nèi)定位方法中，AOA定位需要硬件額外增加精確測量角度的硬件—天線，設(shè)備的廣泛適用性受到了限制；TOA和TDOA定位方法需要精準測量信號在空間中傳播的時間，這對設(shè)備硬件提出了很高的要求，成本受限的設(shè)備往往不適用；利用RSSI測距定位不需要額外的硬件，成本較低，但受到環(huán)境影響較大，在復雜的室內(nèi)環(huán)境中定位精度較差. 基于Wi-Fi技術(shù)的位置指紋定位利用多個無線接入點在室內(nèi)不同位置的信號強度值差異，預(yù)先建立位置坐標與離線信號強度的指紋數(shù)據(jù)庫，作為在線定位的依據(jù). 采用RSSI信息作為指紋數(shù)據(jù)庫的在線定位技術(shù)，定位時不需要額外增加硬件，在綜合應(yīng)用場景下具有成本和廣泛適用性的優(yōu)勢[6].

位置指紋定位方法包括離線建立位置指紋數(shù)據(jù)庫和在線位置指紋數(shù)據(jù)匹配估算位置兩個階段. 典型的位置指紋數(shù)據(jù)匹配算法包括最近鄰法(Nearest Neighbor, NN)[7]、K近鄰法(K-NN)[8]和加權(quán)K近鄰法(Weighted KNN,WKNN)[9-12]等. 在以上典型位置指紋定位的方法中，學者們針對優(yōu)化離線指紋數(shù)據(jù)庫和改進在線定位匹配算法兩方面同時展開研究：文獻[13]利用核函數(shù)、文獻[14]利用Kalman濾波等對離線數(shù)據(jù)進行分析及優(yōu)化，從位置指紋數(shù)據(jù)來源上使定位所需匹配數(shù)據(jù)更加精確；文獻[15]利用多高斯混合模型構(gòu)建離線指紋數(shù)據(jù)庫，并用期望最大值作為估計模型參數(shù)的算法，增加了系統(tǒng)定位的精度；文獻[16]利用最小二乘法對位置指紋信息擬合成高斯多項式連續(xù)分布曲線，對于信號強度分布較為平滑的室內(nèi)空間具有較高的定位精度. 以上位置指紋定位算法的改進和優(yōu)化，在對離線位置指紋數(shù)據(jù)庫的分析優(yōu)化和提高采樣值精度方面作了相應(yīng)的改進，提高了定位精度.

由于室內(nèi)墻壁、門及其他物體的隔擋，室內(nèi)各Wi-Fi信號RSSI衰落分布并不一定都很平滑，基于歐氏距離的加權(quán)K近鄰算法會因此帶來一定誤差. 本文從位置指紋數(shù)據(jù)與實際采樣值的相關(guān)性入手，首先通過聚類算法對離線位置指紋數(shù)據(jù)進行分類，排除與實測采樣值差別較大的數(shù)據(jù)，增大位置指紋數(shù)據(jù)與采樣值的相關(guān)性，降低位置匹配算法的計算量；然后通過數(shù)據(jù)相關(guān)性對指紋數(shù)據(jù)進行分析，根據(jù)與實測采樣值位置指紋數(shù)據(jù)的離散程度，對離散程度不同的位置指紋數(shù)據(jù)賦予不同的權(quán)值，利用加權(quán)K近鄰法估計待定位位置.

1 基于K-means算法的離線位置指紋庫建立及聚類

位置指紋定位方法首先要做的是建立基于位置和信號參數(shù)的離線位置指紋數(shù)據(jù)庫. 本文所采用的離線指紋數(shù)據(jù)是定位區(qū)域內(nèi)已知位置上設(shè)備能夠獲得的環(huán)境中各個無線接入點的信號強度采樣值，即RSSI. 然而指紋數(shù)據(jù)若選取不當，會增大在線匹配位置時的誤差. 利用K-means聚類算法將離線指紋數(shù)據(jù)進行聚類，實測采樣值只與聚類后的聚類中心歐氏距離最短的一些離線指紋數(shù)據(jù)進行RSSI值近似匹配，可減小估計誤差. 假設(shè)各個無線接入點無線信號發(fā)射功率不變但位置未知，假設(shè)定位空間為二維平面.

1.1 初始位置指紋數(shù)據(jù)庫的建立

設(shè)某一定位區(qū)域離線位置指紋數(shù)據(jù)庫的建立需要D個采樣點數(shù)據(jù)，每個采樣點的二維空間位置可以表示為(xi,yi)，i=1, … ,D. 在每個采樣點能夠獲得N個無線接入點的信號強度值，可以用向量形式表示，如式(1)所示：

FRSSNi= (fi1,fi2, … ,fiN) ,i=1, … ,D.

(1)

該組信號強度值的組合對應(yīng)的二維空間坐標如式(2)所示：

Si= (xi,yi) ,i=1, … ,D.

(2)

因此每組指紋信息的數(shù)據(jù)結(jié)構(gòu)可以表示為如式(3)所示的形式：GRSSNi= (Si,FRSSNi) = (xi,yi,fi1,fi2, … ,fiN) ,i=1, 2 , … ,D.

(3)

將采集到的位置指紋數(shù)據(jù)以行形式存儲，得到全部離線位置指紋的數(shù)據(jù)庫，如式(4)所示：

(4)

這是位置指紋數(shù)據(jù)庫的初始狀態(tài).

1.2 基于K-means算法的離線位置指紋數(shù)據(jù)聚類

為了降低從位置指紋數(shù)據(jù)庫中查找匹配指紋的計算量，采用基于K-means的聚類算法進行聚類，得到聚類后的位置指紋數(shù)據(jù)庫. 具體的聚類過程如下.

1)在1.1節(jié)中離線位置指紋數(shù)據(jù)庫中的D個指紋信息FRSSNi作為待聚類的原始指紋信息，其維度為檢測到無線接入點RSSI值的個數(shù)N. 同時指定需要聚類的數(shù)目K(K≤D)；從D個指紋信息中任意選取K個指紋為初始的聚類中心集合C，如式(5)所示：

C= (FRSSN1,FRSSN2, … ,FRSSNk) .

(5)

2)計算剩余的D-K個指紋與C中各個聚類中心的歐氏距離Eij(i=1,2,…,D-K,j=1,2,…,K)，找到距離該指紋最近的聚類中心Ci，將該指紋歸類到該聚類中，得到總共含有D個指紋信息的K個聚類C1,C2,…,CK，每個聚類中的指紋信息個數(shù)定義為nck.

(6)

4)重復步驟2)-3)，直至重新計算出的聚類中心值與上一步的聚類中心相等，即聚類收斂到極值，至此聚類結(jié)束，得到最終的離線位置指紋信息聚類.

2 離散程度相關(guān)的位置指紋定位算法及定位流程

2.1 算法描述

WKNN算法相對于K近鄰算法能夠有效利用k個離線位置指紋的權(quán)重，實現(xiàn)更精確的位置估算，對k個位置指紋數(shù)據(jù)權(quán)重系數(shù)值的選取決定了定位誤差的大小. 本文提出一種基于參考位置指紋離散程度的WKNN定位算法(DiscreteDegreeWKNN,DD-WKNN). 在離線位置指紋數(shù)據(jù)中選取與在線實測RSSI值歐氏距離最短的K個離線位置指紋數(shù)據(jù)，依據(jù)離線位置指紋離散程度對位置估算的參考權(quán)重進行權(quán)值設(shè)定，離散程度用這k個位置指紋的變異系數(shù)表示，然后借鑒WKNN算法進行歸一化加權(quán)求和，權(quán)重系數(shù)的大小與實測采樣值所參考的K個位置指紋的離散程度成反比. 對于參考的離散程度較小的位置指紋數(shù)據(jù)，說明其位置附近RSSI值分布較為平滑，估測待測定位置時給予較大參考權(quán)值，離散程度較大的位置說明RSSI在該位置附近有較大的變化，參考價值較低，估測待測定位置時給予較低的參考權(quán)值. 因此，此方法應(yīng)用在室內(nèi)環(huán)境復雜、Wi-Fi信號強度衰落不均衡的環(huán)境中，可以增加定位的精確度，降低定位誤差波動. 具體算法如下.

1)待定位位置RSSI實測采樣值記為FRSSNLoc，選取k個與FRSSNLoc歐氏距離最小的k個離線位置指紋集合，記為LFk，可表示為如式(7)的形式.

(7)

(i=1,…,k)

(8)

(9)

4)根據(jù)得到的權(quán)重系數(shù)，對各個參考位置進行加權(quán)求和，估算位置坐標. 具體如式(10)所示：

(10)

以上為整體的DD-WKNN算法描述.

2.2 定位實現(xiàn)流程

定位的實現(xiàn)基于三個步驟：位置指紋庫的采集和聚類，對測量點位置的估計.

在指紋庫的采集和聚類階段，需要對選定的已知位置錨節(jié)點進行坐標測量，然后對該點多次測量各個無線接入點的RSSI值，求得平均值作為該點的離線位置指紋數(shù)據(jù)；按照上述方法對多個錨節(jié)點進行上述測量，將各個錨節(jié)點的離線位置指紋數(shù)據(jù)依次錄入數(shù)據(jù)庫. 然后利用K-means算法對全部獲得的離線指紋數(shù)據(jù)進行聚類，得到特征相似的位置指紋數(shù)據(jù)聚類.

在位置估計階段，首先將實測點坐標上測得的各個無線接入點的RSSI值與離線位置指紋數(shù)據(jù)庫中的聚類質(zhì)心RSSI值相比較，選取與離線指紋聚類質(zhì)心歐氏距離最短的聚類. 然后在該聚類中計算各個錨點RSSI值與實測RSSI值的歐氏距離，選取K個歐氏距離最短的錨節(jié)點數(shù)據(jù). 利用改進的WKNN算法估算出實測數(shù)據(jù)點的位置. 整體定位實現(xiàn)流程如圖1所示.

2.3 定位過程計算量分析

分別對基于K-means的位置指紋庫數(shù)據(jù)聚類和實測值位置估計兩方面對DD-WKNN算法時間復雜度進行分析.K-means算法的時間復雜度上界為Ocluster(n*K*t)，其中n為位置指紋庫中指紋數(shù)據(jù)的個數(shù)，K為需要聚類的類個數(shù)，t為迭代次數(shù). 當n和K一定時，算法迭代次數(shù)越多，聚類需要的計算量越大，此時聚類結(jié)果更精確. 一般來說，為了得到較為可靠定位數(shù)據(jù)時需要迭代次數(shù)大于100次. 但該聚類工作是建立位置指紋庫過程的一部分，在對實測數(shù)據(jù)進行定位時并不需要重復計算，因此帶來的計算量增加成本可以無需考慮. 并且位置指紋數(shù)據(jù)經(jīng)過聚類后，在實測數(shù)據(jù)與位置指紋數(shù)據(jù)進行比對時，僅僅需要與K個聚類的聚類中心進行比對，所需的比對計算量是減少的，相對于將實測數(shù)據(jù)與全部位置指紋數(shù)據(jù)進行比對的算法，需要比對的數(shù)據(jù)數(shù)量減少了n-K-k個，其中k為參考位置指紋個數(shù). 在對k個參考位置指紋數(shù)據(jù)進行處理時，以經(jīng)典歐氏距離WKNN算法作對比，歐氏距離WKNN計算K個數(shù)據(jù)與實測數(shù)據(jù)的歐氏距離，DD-WKNN計算K個數(shù)據(jù)的變異系數(shù)，這兩種算法的計算量相當.

綜上所述，該算法在位置指紋庫建立階段需要計算量較大，但在實測數(shù)據(jù)與位置指紋數(shù)據(jù)比對時計算量小，位置估算階段計算量與經(jīng)典歐氏距離WKNN相當. 一般情況關(guān)注的是定位計算量，因此DD-WKNN算法具有實際應(yīng)用上的優(yōu)勢.

圖1 基于DD-WKNN算法的定位流程

3 實驗驗證及分析

通過實際室內(nèi)場景對算法性能進行測試，并與其他位置指紋定位算法進行對比，來評估DD-WKNN算法的性能.

3.1 場景及參數(shù)設(shè)置

實驗地點選取吉林大學南湖校區(qū)一教辦公區(qū)3樓走廊—可以感知到多個Wi-Fi接入點RSSI值的區(qū)域. 為體現(xiàn)算法的適應(yīng)性，不考察無線接入點位置的影響. 從該走廊中選取一塊2 m*20 m的條狀區(qū)域，該區(qū)域內(nèi)可以同時獲得至少8個未知地點發(fā)出的AP信號,并能夠測得其RSSI值. 感知無線接入點的設(shè)備選用基于android系統(tǒng)的智能手機，型號為MI2SC，在手機上安裝Wi-Fi檢視儀APP作為無線接入點RSSI值獲取工具. 采樣點選取在測試區(qū)域的兩條長邊上，從起點開始每隔1.5 m設(shè)置一個采樣點，坐標從(0,0)～(20,0)和(0,2)～(20,2)共計28個采樣點. 在每個采樣點對8個無線接入點的RSSI值進行采樣，采樣20次后求出均值，將各個RSSI數(shù)值錄入離線位置指紋數(shù)據(jù)庫. 根據(jù)錨節(jié)點數(shù)目及算法中參考位置指紋數(shù)目的合理性，K-means算法聚類數(shù)目K取值為3. 雖然智能手機中的Wi-Fi天線參數(shù)性能等并不統(tǒng)一，但由于絕大多數(shù)定位應(yīng)用都是將智能手機作為終端，因此本文對天線帶來的影響不作考慮. 同時在一般室內(nèi)環(huán)境中，各個房間人員走動、房間門的開關(guān)對AP的RSSI值也會帶來一定影響，但一般室內(nèi)定位應(yīng)用場景中也會具有同樣問題，因此雖然在離線位置指紋數(shù)據(jù)采集過程中對指紋數(shù)據(jù)進行多次采樣求平均值，但本文對該環(huán)境影響也不作考慮.

3.2 無線接入點數(shù)目對定位誤差的影響

從8個無線接入點信息中選取4～8個無線接入點的離線位置指紋數(shù)據(jù)進行定位，對比算法為NN算法. 每間隔1 min定位一次. 實測定位點坐標從(0,1)到(20,1)，間隔1 m，共定位21次. 統(tǒng)計定位結(jié)果誤差分布如圖2所示，每組數(shù)據(jù)左側(cè)為NN算法，右側(cè)為DD-WKNN算法.

圖2 位置指紋中無線接入點數(shù)目對算法的影響Fig.2 The number of APs in location fingerprints’ influence on the algorithm

從圖2可以看出，隨著位置指紋庫中參考AP數(shù)量的增加，NN算法和DD-WKNN算法定位精度皆有不同程度的增加，說明參考AP數(shù)量對于位置指紋定位具有一定的影響，且為正相關(guān). 同時通過觀察每組數(shù)據(jù)可知，在相同參考AP數(shù)量的前提下，DD-WKNN算法定位精度較NN算法大，且定位誤差波動較小，說明DD-WKNN算法在本實驗環(huán)境中定位性能要優(yōu)于NN算法.

3.3 參考位置指紋數(shù)目k對定位誤差的影響

采用DD-WKNN算法，選取8個無線接入點RSSI值作為離線位置指紋數(shù)據(jù)，分別在參考位置指紋數(shù)目K取值為1～7的情況下進行測試對比，選取21個采集點的均方根誤差平均值作為誤差平均值，得出結(jié)果如圖3所示.

圖3 參考位置指紋數(shù)目對定位結(jié)果的影響

Fig.3 The number of reference point’s influence on location results

由圖3可以看出，K取值在低于3時誤差較大，說明參考位置指紋數(shù)目少時定位信息不足，定位精度容易受到單個參考位置指紋的影響而產(chǎn)生誤差. 在K取值為3～5時定位精度較好，說明在參考位置指紋數(shù)目適當時，DD-WKNN算法能夠達到較高的定位精度. 而在K取值大于5時定位誤差又開始增大，這是由于過多的參考位置指紋中，部分指紋信息與實測采樣值的偏差較大，容易帶來不必要的影響，而且這種情況也會增大算法的計算量.

根據(jù)實際測試結(jié)果，K值在取3時能達到較好的定位精度，同時算法的計算量適中.

3.4 與現(xiàn)有算法的性能比較

選取NN，歐氏距離WKNN與本文提出的DD-WKNN算法進行性能比較，分別在測試區(qū)域的(0,0.5)～(20,0.5)和(0,1.5)～(20,1.5)坐標點之間每間隔1 m進行RSSI值采集及定位，共計42個實測采集點. 每個采樣點對各無線接入點RSSI值采集10次，采集間隔1 min，最終結(jié)果取10次采集值的均值，將其定位結(jié)果與實際位置進行比較，分析誤差. 圖4為各算法的誤差累積概率分布圖.

圖4 三種算法的實測性能比較

Fig.4 The measured performance comparison of three algorithms

從圖4的實測比較結(jié)果可以看出：NN算法定位誤差較大，誤差累積函數(shù)收斂最慢，且其最大誤差值也較大；傳統(tǒng)WKNN算法的定位精度優(yōu)于NN算法，最大誤差值在2.5 m左右；DD-WKNN算法定位精度最優(yōu)，誤差累積函數(shù)收斂最快，且最大定位誤差值在1.6 m左右. 因此，本文提出的DD-WKNN算法在定位精度和誤差波動范圍上皆具有優(yōu)勢.

4 結(jié) 論

DD-WKNN算法將K個與待定位位置實測Wi-Fi熱點RSSI值歐氏距離最接近的位置指紋數(shù)據(jù)作為位置估計的參照位置，以參考的位置指紋數(shù)據(jù)離散度作為權(quán)重系數(shù)的依據(jù)，利用WKNN算法的思想對K個位置指紋數(shù)據(jù)進行加權(quán)求和，對待定位位置進行估計. 通過實際場景的測試表明，該算法在定位精度上優(yōu)于原有的以歐氏距離作為權(quán)重系數(shù)的WKNN算法，且誤差波動較小. 同時實驗表明參考位置指紋數(shù)目k對本算法的定位精度有一定影響，在K取值為3～5時定位精度高，而且此時算法計算量適中.

[1] 李德毅,張?zhí)炖?黃立威.位置服務(wù):接地氣的云計算[J].電子學報,2014,42(4):786-790.DOI:10.3969/j.issn.0372-2112.2014.04.025.

LI Deyi, ZHANG Tianlei, HUANG Liwei. A down-to-earth cloud computing: location-based service[J]. Acta Electronic Sinica, 2014,42(4):786-790.

[2] JUNGLAS I A, WATSON R T. Location-based services[J]. Communications of the ACM, 2008, 51(3):65-69.DOI:10.1145/1325555.1325568.

[3] 李建坡,鐘鑫鑫,徐純.無線傳感器網(wǎng)絡(luò)動態(tài)節(jié)點定位算法綜述[J].東北電力大學學報,2015,35(1):53-58.

LI Jianpo, ZHONG Xinxin, XU Chun. Review of dynamic node localization algorithm for wireless sensor networks[J]. Journal of Northeast Dianli University, 2015,35(1)53-58.

[4] 李建坡,鐘鑫鑫,徐純.無線傳感器網(wǎng)絡(luò)靜態(tài)節(jié)點定位算法綜述[J].東北電力大學學報,2015,35(2):73-82.

LI Jianpo, ZHONG Xinxin, XU Chun. Review of statics node localization algorithm for wireless sensor networks[J]. Journal of Northeast Dianli University, 2015,35(2)73-82.

[5] HE S, CHAN S H G. Wi-Fi fingerprint-based indoor positioning: recent advances and comparisons[J]. IEEE Communications Surveys & Tutorials, 2016, 18(1):466-490. DOI:10.1109/COMST.2015.2464084.

[6] 楊錚,吳陳沭,劉云浩.位置計算:無線網(wǎng)絡(luò)定位與可定位性[M].北京:清華大學出版社,2014:113-115.

[7] GEZICI S. A Survey on wireless position estimation[J]. Wireless Personal Communications, 2008, 44(3):263-282. DOI:10.1007/s11277-007-9375-z

[8] BAHL P, PADMANABHAN V N. RADAR: an in-building RF-based user location and tracking system[C]// Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Tel Aviv: IEEE Press, 2000:775-784.

[9] CHAN E C L, BACIU G, MAK S C. Using Wi-Fi signal strength to localize in wireless sensor networks[C]// WRI International Conference on.Kuming: IEEE Computer Society, 2009:538-542.

[10]WU D, XU Y, MA L. Research on RSS based indoor location method[C]// Knowledge Engineering and Software Engineering 2009. Shenzhen: IEEE, 2009:205-208.

[11]MADIGAN D, EINAHRAWY E, MARTIN R P, et al. Bayesian indoor positioning systems[C]// Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Miami: IEEE Press, 2005:1217-1227.

[12]DAWES B, CHIN K W. A comparison of deterministic and probabilistic methods for indoor localization[J]. Journal of Systems & Software, 2011, 84(3):442-451.DOI:10.1016/j.jss.2010.11.888.

[13]徐玉濱,鄧志安,馬琳.基于核直接判別分析和支持向量回歸的WLAN室內(nèi)定位算法[J].電子與信息學報,2011,33(4):896-901. DOI:10.3724/SP.J.1146.2010.00813.

XU Yubin, DENG Zhian MA Lin. WLAN Indoor positioning algorithm based on KDDA and SVR[J]. Journal of Electronics & Information Technology, 2011,33(4):896-901.

[14]朱明強,侯建軍,劉穎,等.基于尺度優(yōu)化IUKF濾波的室內(nèi)定位估計方法[J].北京郵電大學學報, 2013,36(4): 65-70. DOI:10.13190/jbupt.201304.66.049.

ZHU Mingqiang, HOU Jianjun, LIU Ying, et al. Indoor localization estmation based on scaled iterated unscented Kalman filter[J]. Journal of Beijing University of Posts and Telecommunications,2013,36(4): 65-70.

[15]陳淼.基于多高斯混合模型的WLAN室內(nèi)定位系統(tǒng)[J].華中科技大學學報(自然科學版),2012,40(4):67-71. DOI:10.13245/j.hust.2012.04.019.

CHEN Miao. WLAN indoor location system based on multi-Gaussian mixture model[J]. Journal of Huazhong University of Science and Technology(Natural Science Edition), 2012, 40(4):67-71.

[16]韋燕華,周彥,王冬麗.基于LS-SVM的位置指紋室內(nèi)定位[J].計算機工程與應(yīng)用,2016,52(9):122-125. DOI:10.3778/j.issn.1002-8331.1402-0208.

WEI Yanhua, ZHOU Yan, WANG Dongli. Location fingerprints based indoor positioning using least squares support vector machines[J]. Computer Engineering and Applications,2016,52(9):122-125.

(編輯 王小唯， 苗秀芝)

DiscretedegreeWKNNlocationfingerprintingalgorithmbasedonWi-Fi

TIANHongliang1,2,QIANZhihong1,LIANGXiao1,WANGYijun3,WANGXue1

(1.SchoolofCommunicationEngineering,JilinUniversity,Changchun130012,China;2.SchoolofInformationEngineering,NortheastDianliUniversity,Jilin132012,Jilin,China;3.SchoolofElectronicandInformationEngineering,ChangchunUniversityofScienceandTechnology,Changchun130022,China)

To improve the localization performance of the WKNN location fingerprinting algorithm when the indoor environment is complex, an improved WKNN location fingerprinting algorithm—Discrete Degree Weighted K-Nearest Neighbor (DD-WKNN) is proposed, which takes the dispersion of location fingerprints as the weight reference. The K-means clustering algorithm is used to cluster the location fingerprints when the offline location fingerprint database is established, which reduces the computational complexity of searching the location fingerprint database. K location fingerprints which are most similar to online measured RSSIs are selected from the offline location fingerprint database, and the discrepancy degrees are compared. A higher weighting coefficient is assigned to the position fingerprint with a small degree of dispersion, which reduces the error of position estimation caused by the original WKNN algorithm when the signal strength of the indoor environment changes greatly with distance. The analysis of the time complexity of DD-WKNN algorithm shows that its computational complexity is less than that of the original WKNN algorithm. The experimental results show that the DD-WKNN algorithm has a higher positioning accuracy and the positioning error fluctuates less.

wireless localization; location fingerprint; Wi-Fi;

signal strength indicator (RSSI); discrete degree

10.11918/j.issn.0367-6234.201610104

2016-10-24

國家自然科學基金(61371092, 61401175, 61540022); 吉林大學研究生創(chuàng)新基金(2016091)

田洪亮(1981—)，男，博士研究生，講師; 錢志鴻(1957—)，男，教授，博士生導師

錢志鴻，dr.qzh@163.com

TP

A

0367-6234(2017)05-0094-06