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

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

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

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

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

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

無(wú)線定位；位置指紋；Wi-Fi；接收信號(hào)強(qiáng)度指示；離散度

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

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

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

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

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

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

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

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

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

(1)

該組信號(hào)強(qiáng)度值的組合對(duì)應(yīng)的二維空間坐標(biāo)如式(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ù)以行形式存儲(chǔ)，得到全部離線位置指紋的數(shù)據(jù)庫(kù)，如式(4)所示：

(4)

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

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

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

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

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

(5)

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

(6)

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

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

2.1 算法描述

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

1)待定位位置RSSI實(shí)測(cè)采樣值記為FRSSNLoc，選取k個(gè)與FRSSNLoc歐氏距離最小的k個(gè)離線位置指紋集合，記為L(zhǎng)Fk，可表示為如式(7)的形式.

(7)

(i=1,…,k)

(8)

(9)

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

(10)

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

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

定位的實(shí)現(xiàn)基于三個(gè)步驟：位置指紋庫(kù)的采集和聚類，對(duì)測(cè)量點(diǎn)位置的估計(jì).

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

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

2.3 定位過(guò)程計(jì)算量分析

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

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

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

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

通過(guò)實(shí)際室內(nèi)場(chǎng)景對(duì)算法性能進(jìn)行測(cè)試，并與其他位置指紋定位算法進(jìn)行對(duì)比，來(lái)評(píng)估DD-WKNN算法的性能.

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

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

3.2 無(wú)線接入點(diǎn)數(shù)目對(duì)定位誤差的影響

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

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

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

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

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

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

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

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

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

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

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

圖4 三種算法的實(shí)測(cè)性能比較

Fig.4 The measured performance comparison of three algorithms

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

4 結(jié) 論

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

[1] 李德毅,張?zhí)炖?黃立威.位置服務(wù):接地氣的云計(jì)算[J].電子學(xué)報(bào),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ú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)節(jié)點(diǎn)定位算法綜述[J].東北電力大學(xué)學(xué)報(bào),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ú)線傳感器網(wǎng)絡(luò)靜態(tài)節(jié)點(diǎn)定位算法綜述[J].東北電力大學(xué)學(xué)報(bào),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] 楊錚,吳陳沭,劉云浩.位置計(jì)算:無(wú)線網(wǎng)絡(luò)定位與可定位性[M].北京:清華大學(xué)出版社,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].電子與信息學(xué)報(bào),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]朱明強(qiáng),侯建軍,劉穎,等.基于尺度優(yōu)化IUKF濾波的室內(nèi)定位估計(jì)方法[J].北京郵電大學(xué)學(xué)報(bào), 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].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版),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].計(jì)算機(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

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

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

錢志鴻，dr.qzh@163.com

TP

A

0367-6234(2017)05-0094-06