改進(jìn)K-means聚類的自適應(yīng)加權(quán)K近鄰指紋定位算法

鄔春明，齊森南

(東北電力大學(xué) 現(xiàn)代電力系統(tǒng)仿真控制與綠色電能新技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，吉林省 吉林市 132012)

0 引 言

隨著通信技術(shù)的發(fā)展、移動(dòng)網(wǎng)絡(luò)的普及和設(shè)備的興起，人們對室內(nèi)定位服務(wù)(indoor positioning service, IPS)的需求逐漸升高[1-2]。定位服務(wù)主要依賴無線通信技術(shù)，由于Wi-Fi接入點(diǎn)在室內(nèi)環(huán)境中隨處可見，并且?guī)缀跛幸苿?dòng)設(shè)備都具有內(nèi)置的Wi-Fi接收模塊[3-4]。因此，Wi-Fi室內(nèi)定位技術(shù)已成為現(xiàn)今的熱點(diǎn)研究課題[5]。

傳統(tǒng)室內(nèi)定位方法，如三邊定位法，雖然其算法理論簡單，實(shí)現(xiàn)方便，但易受到多徑效應(yīng)以及室內(nèi)環(huán)境的影響導(dǎo)致定位精度偏低[6-7]。近年來，國內(nèi)外學(xué)者多采用接收信號(hào)強(qiáng)度指示(received signal strength indication，RSSI)作為指紋信息進(jìn)行室內(nèi)定位研究[8-9]。相較于傳統(tǒng)室內(nèi)定位方法，指紋定位技術(shù)不受信號(hào)多徑效應(yīng)的影響，通過對定位場景的特殊信息進(jìn)行量化并建立數(shù)據(jù)集，選用合適的定位匹配算法計(jì)算出測試點(diǎn)與特征數(shù)據(jù)庫中最相似的采樣點(diǎn)，從而確定目標(biāo)位置。在多種定位匹配算法中，加權(quán)K近鄰算法(weighted K-nearest neighbor，WKNN)是目前使用頻率較高的一種算法，通過參考點(diǎn)相似度加權(quán)計(jì)算完成測試點(diǎn)定位[10-11]。

影響指紋定位算法定位效果的關(guān)鍵因素在于如何優(yōu)化離線指紋數(shù)據(jù)和WKNN算法中最優(yōu)K值的選擇問題?，F(xiàn)有研究多采用K-means聚類算法對離線指紋數(shù)據(jù)進(jìn)行優(yōu)化處理，但是聚類效果受初始中心的選擇和聚類數(shù)目的影響，算法容易陷入局部最優(yōu)狀態(tài)，同時(shí)容易導(dǎo)致聚類離散點(diǎn)的出現(xiàn)。為解決以上問題，很多學(xué)者進(jìn)行了研究與改進(jìn)。文獻(xiàn)[12]利用像素強(qiáng)度與距離約束準(zhǔn)則聯(lián)合概率最大化的概念來確定初始參考點(diǎn)間的相似度，降低了算法的聚類時(shí)間。文獻(xiàn)[13]提出一種基于K均值聚類的區(qū)域劃分方法，該方法采用高氏距離和處理分類值屬性離散需求機(jī)制，有效地劃分大量的眾包數(shù)據(jù)集，并解決了分類屬性不明和聚類離散點(diǎn)的問題。與以往基于優(yōu)化的方法相比，該方法對分區(qū)數(shù)據(jù)的并行處理和計(jì)算更加簡化，大大縮短了運(yùn)行時(shí)間。文獻(xiàn)[14]在K-means聚類距離計(jì)算公式中考慮了信號(hào)間屬性值的影響，更準(zhǔn)確地計(jì)算出不同對象之間的差異。通過測試不同信號(hào)的信號(hào)強(qiáng)度，建立每個(gè)房間位置的接入點(diǎn)(access point，AP)。實(shí)驗(yàn)結(jié)果表明，相對于硬聚類算法來說，改進(jìn)算法的定位精度有所提高。文獻(xiàn)[15]根據(jù)距離檢測方法對離群點(diǎn)進(jìn)行剔除，通過搜索相鄰子庫來縮小匹配范圍，解決了RSSI易受信號(hào)衰變和環(huán)境影響的問題。文獻(xiàn)[16]將聚類算法與線性回歸相結(jié)合，通過縮小數(shù)據(jù)庫和聚類中心之間的差異，確定最優(yōu)聚類大小。以上對離線指紋數(shù)據(jù)庫進(jìn)行聚類優(yōu)化處理的研究，對減少定位階段的指紋匹配時(shí)間和提高定位精度有很大作用。但由于Wi-Fi信號(hào)的傳播具有對稱性，在進(jìn)行指紋數(shù)據(jù)聚類預(yù)處理的過程中容易將參考點(diǎn)RSSI值相近，但實(shí)際物理坐標(biāo)較遠(yuǎn)的參考點(diǎn)歸為一類，造成最終定位結(jié)果的偏差。在關(guān)于WKNN算法研究的大部分文獻(xiàn)中，K值的選擇對于定位結(jié)果的影響較為關(guān)鍵。文獻(xiàn)[17]將曼哈頓距離引入WKNN算法，以區(qū)分不同參考節(jié)點(diǎn)的影響。同時(shí)，通過調(diào)整相鄰參考節(jié)點(diǎn)的權(quán)重，選擇合適的參考點(diǎn)參與最終的匹配定位，達(dá)到提高定位精度的目的。文獻(xiàn)[18]通過參考點(diǎn)間離散程度大小，對各參考點(diǎn)賦予不同權(quán)值，并對比K=1，2，3，…，7的不同情況下的定位誤差，最終選擇了固定值K=4。文獻(xiàn)[19]選擇固定值K=3進(jìn)行定位實(shí)驗(yàn)。文獻(xiàn)[20]根據(jù)空間信號(hào)的衰減規(guī)律提出加權(quán)歐氏距離，并與參考點(diǎn)的已知位置信息相結(jié)合，設(shè)計(jì)了近似位置距離，通過在3個(gè)數(shù)據(jù)庫上進(jìn)行的定位實(shí)驗(yàn)，并與8種不同的定位算法進(jìn)行了性能比較，表明算法達(dá)到了較好的定位精度。但該算法需要反復(fù)實(shí)驗(yàn)對比來優(yōu)選匹配參考點(diǎn)數(shù)目，且用于實(shí)驗(yàn)的指紋數(shù)據(jù)庫需要以大量的離線采集工作量為代價(jià)來獲取。以上關(guān)于WKNN算法K值的選擇問題多采用固定值或?qū)嶒?yàn)對比取最優(yōu)的方法，很難做到針對不同測試點(diǎn)選擇合理的匹配參考點(diǎn)數(shù)。

針對指紋數(shù)據(jù)K-means聚類預(yù)處理效果受聚類離散點(diǎn)影響，導(dǎo)致預(yù)處理效果不佳和WKNN算法采用固定K值進(jìn)行匹配定位的問題，本文采用基于坐標(biāo)相似度的K-means算法對離線指紋數(shù)據(jù)庫進(jìn)行預(yù)處理，減少聚類過程中出現(xiàn)參考點(diǎn)RSSI值與所屬類相近，但實(shí)際物理坐標(biāo)較遠(yuǎn)的問題。并結(jié)合改進(jìn)的自適應(yīng)加權(quán)K近鄰(adaption weighted k-nearest neighbor，AWKNN)算法，根據(jù)每個(gè)測試點(diǎn)的匹配參考點(diǎn)間實(shí)際距離的相似度特性動(dòng)態(tài)選擇K值，提高室內(nèi)定位精度。

1 位置指紋定位算法原理

假設(shè)室內(nèi)定位環(huán)境中隨機(jī)分布著n個(gè)AP和m個(gè)參考點(diǎn)(reference point，RP)。對每個(gè)RP收集n個(gè)AP的RSSI值，表示為

RSSIi=(RSSIi1,RSSIi2,…,RSSIin)

(1)

(1)式中:RSSIi代表第i個(gè)RP采集到的指紋信息，i=1,2,3,…,m；RSSIin代表第i個(gè)RP采集到的第n個(gè)AP的RSSI值。將采集到的參考點(diǎn)的RSSI值與相應(yīng)的物理坐標(biāo)相結(jié)合，形成唯一的位置指紋信息得

FPi=[xi,yi,RSSIi1,RSSIi2,…,RSSIin]

(2)

(2)式中，(xi,yi)表示第i個(gè)參考點(diǎn)的坐標(biāo)。將采集的所有指紋信息按行向量方式存儲(chǔ)，構(gòu)建離線指紋數(shù)據(jù)庫得

(3)

在位置匹配階段，WKNN算法計(jì)算出測試點(diǎn)實(shí)時(shí)RSSI值與指紋庫參考點(diǎn)處RSSI值之間的相似性。選擇K個(gè)相似度最大的參考點(diǎn)，完成匹配和定位。測試點(diǎn)采集的實(shí)時(shí)指紋數(shù)據(jù)為rssi=(rssi1,rssi2,…,rssin)。

相似度大小與RSSI值間的歐氏距離有關(guān)，參考點(diǎn)與測試點(diǎn)歐氏距離越近，此參考點(diǎn)相應(yīng)的權(quán)重因子越高[21]。歐氏距離計(jì)算式為

(4)

每個(gè)參考點(diǎn)的權(quán)重因子與RSSI值的歐氏距離的倒數(shù)成正比。測試點(diǎn)位置坐標(biāo)的計(jì)算式為

(5)

位置指紋定位算法原理如圖1。

圖1 位置指紋定位算法原理Fig.1 Principle of fingerprint location algorithm

2 改進(jìn)K-means的AWKNN定位算法

2.1 基于坐標(biāo)相似度的K-means算法

在Wi-Fi室內(nèi)定位環(huán)境中，K-means聚類算法多以信號(hào)RSSI值之間的歐氏距離作為相似度測量標(biāo)準(zhǔn)。首先從m個(gè)參考點(diǎn)中隨機(jī)選擇k個(gè)參考點(diǎn)作為聚類計(jì)算的初始聚類中心，分別計(jì)算剩余m-k個(gè)參考點(diǎn)到各聚類中心點(diǎn)的歐氏距離，傳統(tǒng)K-means算法中第i個(gè)參考點(diǎn)與第k個(gè)聚類中心點(diǎn)的RSSI值相似度計(jì)算式為[12]

(6)

計(jì)算剩余RP到這k個(gè)初始聚類中心產(chǎn)生k個(gè)歐氏距離值，取這個(gè)k個(gè)歐氏距離中最小的值，并將這個(gè)RP劃歸到RSSI距離最小的聚類簇中。對于每一個(gè)剩余RP進(jìn)行相同的遍歷計(jì)算，直到所有的指紋點(diǎn)聚類完成。

聚類完成后需要重新計(jì)算這k個(gè)類簇的聚類中心，假設(shè)第s個(gè)類簇中包含M個(gè)指紋點(diǎn)，則計(jì)算第s個(gè)類簇的新聚類中心點(diǎn)處RSSI值表示為

(7)

(7)式中：RSSIs表示新的聚類中心點(diǎn)處的接收信號(hào)強(qiáng)度值；RSSIsp表示第s個(gè)類簇中第p個(gè)參考點(diǎn)的接收信號(hào)強(qiáng)度值。

得到新的聚類中心后，再次對每個(gè)RP進(jìn)行聚類計(jì)算，直到新的聚類中心點(diǎn)和前一次迭代產(chǎn)生的聚類中心相同或偏差較小時(shí)，則可判定K-means聚類結(jié)果趨于穩(wěn)定，聚類中心不會(huì)再發(fā)生任何變化，確定最終的k個(gè)聚類中心以及各聚類簇中所包含的指紋點(diǎn)。指紋數(shù)據(jù)庫經(jīng)K-means聚類后如圖2。

圖2 指紋數(shù)據(jù)庫經(jīng)K-means聚類算法效果Fig.2 Fingerprint clustering effect of K-means algorithm

圖2中，經(jīng)過K-means聚類處理的某一類簇中存在其他類的參考點(diǎn)，聚類效果不理想。主要原因是傳統(tǒng)K-means聚類只計(jì)算參考點(diǎn)間RSSI值的相似度，導(dǎo)致部分RSSI值相似度高但實(shí)際物理距離遠(yuǎn)的參考點(diǎn)聚為一類，如果這些遠(yuǎn)距離參考點(diǎn)在匹配過程中被選中，則會(huì)導(dǎo)致定位結(jié)果誤差增大，所以傳統(tǒng)的K-means算法需要進(jìn)一步改進(jìn)。

對傳統(tǒng)K-means算法的改進(jìn)，考慮在參考點(diǎn)間相似度計(jì)算中引入?yún)⒖键c(diǎn)物理坐標(biāo)相似度，基于坐標(biāo)相似度的K-means(coordinate similarity k-means，CS-K-means)算法的相似度計(jì)算式為

SIM(RSSIi,RSSIj)=

(8)

(8)式中：RSSIik和RSSIjk表示第i個(gè)RP和第j個(gè)聚類中心采集k個(gè)AP的信號(hào)強(qiáng)度；(xi,yi)和(xj,yj)表示第i個(gè)參考點(diǎn)和第j個(gè)聚類中心的物理坐標(biāo)；SIM(RSSIi,RSSIj)表示參考點(diǎn)與某一聚類中心點(diǎn)的相似度。

參考點(diǎn)間相似度越高，SIM(RSSIi,RSSIj)值越大[22]。CS-K-means算法在對指紋數(shù)據(jù)進(jìn)行聚類時(shí)，綜合考慮參考點(diǎn)RSSI值和物理位置2種因素對聚類效果的影響，通過計(jì)算參考點(diǎn)與已有聚類中心的雙重相似度，避免將遠(yuǎn)距離參考點(diǎn)劃為非所屬類的現(xiàn)象發(fā)生。

2.2 自適應(yīng)WKNN算法

WKNN算法是應(yīng)用較廣的一種匹配定位算法，它充分考慮了與測試點(diǎn)相似度高的參考點(diǎn)在匹配過程中的貢獻(xiàn)，對其坐標(biāo)賦予不同權(quán)重進(jìn)行定位計(jì)算，但是WKNN算法需要進(jìn)行反復(fù)試驗(yàn)對比來選擇最近鄰匹配點(diǎn)數(shù)目K。當(dāng)K值過小，用于定位的匹配點(diǎn)不足，導(dǎo)致定位結(jié)果易受單一參考點(diǎn)影響；當(dāng)K過大，易選中遠(yuǎn)距離參考點(diǎn)參與定位，造成定位誤差增大，這是選用固定K值的弊端。

由于室內(nèi)定位環(huán)境復(fù)雜多變，不同測試點(diǎn)周圍的參考點(diǎn)分布情況不盡相同，需對每個(gè)測試點(diǎn)自適應(yīng)地選擇最優(yōu)K值，將與測試點(diǎn)相匹配的K個(gè)參考點(diǎn)，按相似度由大到小的順序排列，K個(gè)參考點(diǎn)的坐標(biāo)分別為(x1,y1),(x2,y2),…(xK,yK)。其中，(x1,y1)為相似度最大的參考點(diǎn)坐標(biāo)，(xK,yK)為相似度最小的參考點(diǎn)坐標(biāo)。用d1j表示其他K-1個(gè)參考點(diǎn)與最大相似度參考點(diǎn)間坐標(biāo)的歐氏距離得

(9)

(9)式中，j=2,…,K。將所得K-1個(gè)坐標(biāo)的歐氏距離取均值得

(10)

根據(jù)得到的均值計(jì)算K-1個(gè)d1j的標(biāo)準(zhǔn)差σ得

(11)

圖3 基于改進(jìn)K-means聚類的自適應(yīng)WKNN算法流程圖Fig.3 Flow chart of adaptive WKNN algorithm based on improved k-means clustering

根據(jù)已取得標(biāo)準(zhǔn)差σ對選中的K個(gè)參考點(diǎn)進(jìn)行二次篩選，刪除d1j大于σ的參考點(diǎn)，保留d1j小于或等于σ的參考點(diǎn)作為最后參與定位的最近鄰匹配點(diǎn)。自適應(yīng)WKNN算法的K值等于所保留的參考點(diǎn)數(shù)，對于每個(gè)測試點(diǎn)，算法根據(jù)參考點(diǎn)間實(shí)際距離的均值和標(biāo)準(zhǔn)差而動(dòng)態(tài)變化，計(jì)算所需K值并得到一組全新的參考點(diǎn)數(shù)據(jù)?；诟倪M(jìn)K-means聚類的自適應(yīng)WKNN算法流程如圖3。

3 實(shí)驗(yàn)對比與分析

3.1 實(shí)驗(yàn)環(huán)境設(shè)置

為驗(yàn)證基于坐標(biāo)相似度的K-means算法的效果，在10 m×10 m×5 m的室內(nèi)空間中隨機(jī)分布有6個(gè)Wi-Fi熱點(diǎn)信號(hào)發(fā)射源，實(shí)驗(yàn)環(huán)境內(nèi)分布有100個(gè)參考點(diǎn)。采集指紋數(shù)據(jù)時(shí)忽略室內(nèi)障礙物以及人員走動(dòng)的影響，在每個(gè)參考點(diǎn)處分別采集6個(gè)Wi-Fi熱點(diǎn)的RSSI值，將30次的采樣值取平均值后存入指紋數(shù)據(jù)庫。室內(nèi)定位環(huán)境如圖4。

圖4 室內(nèi)定位環(huán)境圖Fig.4 Indoor location environment

3.2 改進(jìn)的K-means算法實(shí)驗(yàn)分析

采用傳統(tǒng)K-means聚類算法與CS-K-means聚類算法對離線指紋數(shù)據(jù)庫進(jìn)行聚類處理，根據(jù)各參考點(diǎn)RSSI值和實(shí)際物理坐標(biāo)的雙重相似度進(jìn)行聚類，將指紋庫分成若干“子區(qū)域”，考慮實(shí)際定位環(huán)境與參考點(diǎn)個(gè)數(shù)等因素的影響，設(shè)定聚類“子區(qū)域”數(shù)為4，指紋庫聚類優(yōu)化效果如圖5。

對比圖5a、圖5b可知，經(jīng)過CS-K-means聚類處理后的指紋庫，邊界分類明顯，該算法將被分到其他類中的遠(yuǎn)距離參考點(diǎn)強(qiáng)制同化為其他類參考點(diǎn)。如圖5a所示，假設(shè)在定位階段，測試點(diǎn)的RSSI值與黑色參考點(diǎn)相近，如果處于其他類中的遠(yuǎn)距離黑色參考點(diǎn)被選中參與匹配定位，將導(dǎo)致定位精度出現(xiàn)嚴(yán)重誤差。而在圖5b中，將離散的黑色參考點(diǎn)強(qiáng)制劃歸到其他類之后，再次進(jìn)行匹配定位時(shí)，離散的黑色參考點(diǎn)將不會(huì)對最終定位結(jié)果產(chǎn)生影響。因離散參考點(diǎn)數(shù)目較少，經(jīng)過坐標(biāo)相似度處理后的指紋數(shù)據(jù)庫各聚類中心出現(xiàn)輕微偏移，對整體聚類效果影響不大。

圖5 指紋庫聚類優(yōu)化效果圖Fig.5 Effect diagram of fingerprint databaseclustering optimization

通過改進(jìn)聚類算法預(yù)處理后，離散參考點(diǎn)將不再出現(xiàn)，在線定位過程的計(jì)算量明顯減小，定位時(shí)間也會(huì)在一定程度上降低。隨機(jī)選取20個(gè)待定位點(diǎn)在K-means算法和CS-K-means算法處理過的指紋庫下進(jìn)行定位實(shí)驗(yàn)，記錄定位結(jié)果，進(jìn)行比對分析，定位算法為WKNN，定位結(jié)果如圖6。

從圖6可以看出，在CS-K-means聚類算法優(yōu)化后的指紋數(shù)據(jù)庫中進(jìn)行在線定位的誤差遠(yuǎn)小于傳統(tǒng)K-means聚類算法，這是因?yàn)镃S-K-means算法的指紋聚類效果相對集中，排除了離散參考點(diǎn)的干擾，特別是對誤差較大的待定位點(diǎn)有很好的改進(jìn)效果。

圖6 2種聚類算法下定位誤差圖Fig.6 Location errors of two clustering algorithms

3.3 自適應(yīng)WKNN算法實(shí)驗(yàn)分析

為獲取定位效果最佳的WKNN算法的對比實(shí)驗(yàn)數(shù)據(jù)，選用3.2節(jié)中經(jīng)改進(jìn)的K-means聚類處理后的指紋庫進(jìn)行匹配定位，坐標(biāo)點(diǎn)之間每間隔1 m進(jìn)行RSSI值采集，共計(jì)100個(gè)實(shí)測參考點(diǎn)。每個(gè)參考點(diǎn)對各無線接入點(diǎn)的RSSI值采集30次，采集時(shí)間間隔1 min，最終結(jié)果取30次采集值的均值，進(jìn)行定位實(shí)驗(yàn)，進(jìn)而求得WKNN算法中最近鄰樣本點(diǎn)數(shù)目K最優(yōu)的情況。WKNN算法定位實(shí)驗(yàn)中最近鄰樣本點(diǎn)數(shù)目K對定位誤差的影響如圖7。

圖7 最近鄰樣本點(diǎn)數(shù)目K與定位誤差關(guān)系Fig.7 Relationship between the point number K of the nearest neighbor sample and the positioning error

如圖7所示，當(dāng)K值小于4時(shí)，WKNN算法定位誤差較大，因?yàn)樽罱彉颖军c(diǎn)數(shù)目少，使得用于定位的指紋信息不足，定位精度受某一參考點(diǎn)的影響較大；當(dāng)K值大于5時(shí)，由于選擇的最近鄰樣本點(diǎn)數(shù)目過多，使得遠(yuǎn)距離樣本點(diǎn)被選中，造成WKNN算法定位誤差增大；當(dāng)K值為4或5時(shí)，WKNN算法定位誤差相對較小，說明此時(shí)的最近鄰樣本點(diǎn)數(shù)目合理，在此實(shí)驗(yàn)環(huán)境下算法定位效果最好。綜上，選擇K=4的WKNN算法進(jìn)行實(shí)驗(yàn)對比。

上一節(jié)中，在兩種不同聚類算法處理過的指紋數(shù)據(jù)庫上，采用WKNN算法對20個(gè)測試點(diǎn)進(jìn)行定位實(shí)驗(yàn)。雖然CS-K-means算法的指紋聚類效果相對集中，排除了離散參考點(diǎn)的干擾，使得實(shí)驗(yàn)整體定位效果有所提高，但對于部分測試點(diǎn)的定位誤差仍然較大。這是因?yàn)閃KNN算法選用固定K匹配參考點(diǎn)，造成部分測試點(diǎn)定位誤差較大。分別選取上一節(jié)中定位誤差較大的第2，8，10，14，20個(gè)待定位點(diǎn)進(jìn)行分析。表1為這5個(gè)待定位點(diǎn)在WKNN 算法下所匹配的參考點(diǎn)坐標(biāo)以及最終的定位結(jié)果。

表1 基于CS-K-means的WKNN算法匹配參考點(diǎn)坐標(biāo)

WKNN算法分別為上述5個(gè)測試點(diǎn)都分配相同數(shù)目的參考點(diǎn)，從最終的定位結(jié)果來看，WKNN算法定位誤差較大。5個(gè)測試點(diǎn)定位誤差分別為1.87，2.13，2.21，1.74和1.94 m。在基于CS-K-means聚類處理過的指紋數(shù)據(jù)庫基礎(chǔ)上使用AWKNN算法對上述5個(gè)測試點(diǎn)重新進(jìn)行定位計(jì)算。表2為AWKNN算法匹配參考點(diǎn)坐標(biāo)值。

表2 基于AWKNN算法匹配參考點(diǎn)坐標(biāo)

使用AWKNN算法后，這5個(gè)測試點(diǎn)的定位誤差分別為1.69，1.83，1.97，1.58和1.73 m。定位精度較基于CS-K-means的WKNN算法分別提高了9.6%，14.1%，10.9%，9.2%和10.8%?？梢娡ㄟ^自適應(yīng)方式選擇合適的匹配參考點(diǎn)個(gè)數(shù)對匹配定位精度有一定的提高。

為驗(yàn)證所提AWKNN算法比其他已有算法在定位精度上的優(yōu)化效果，選用WKNN(K=4)算法、文獻(xiàn)[14]中的離散度加權(quán)K近鄰(discrete degree weighted K-nearest neighbor，DD-WKNN)算法和AWKNN算法對室內(nèi)空間中隨機(jī)分布的100個(gè)待定位點(diǎn)進(jìn)行實(shí)驗(yàn)。其中，DD-WKNN算法是從離線指紋庫中選取K個(gè)與在線實(shí)測接入點(diǎn)信號(hào)強(qiáng)度信息最相似的位置指紋，比較其離散程度，將離散程度小的位置指紋賦予較高的加權(quán)系數(shù)。定位算法優(yōu)化結(jié)果對比如表3。

表3 3種算法定位誤差分析

對表3的實(shí)驗(yàn)結(jié)果進(jìn)行分析:WKNN(K=4)平均定位誤差較大；DD-WKNN相較于WKNN(K=4)算法定位精度有所提高；AWKNN算法相對于其他兩類算法來說，考慮了匹配參考點(diǎn)間實(shí)際距離的均值和標(biāo)準(zhǔn)差，對每個(gè)測試點(diǎn)自適應(yīng)選擇所需參考點(diǎn)數(shù)目，既避免了遠(yuǎn)距離參考點(diǎn)的選入，又保證了匹配參考點(diǎn)數(shù)目的準(zhǔn)確性，因此該算法平均定位誤差最小，同時(shí)提高了匹配定位時(shí)間，解決了因使用固定K值所帶來的定位精度差的影響。WKNN(K=4)、DD-WKNN和AWKNN 3種定位算法的誤差累計(jì)分布函數(shù)如圖8。

從圖8的對比結(jié)果可以看出：在同等優(yōu)化指紋庫的基礎(chǔ)上，WKNN(K=4)算法的誤差累積函數(shù)收斂最慢；而DD-WKNN算法的定位精度優(yōu)于WKNN(K=4)算法；AWKNN算法，定位誤差最小，誤差累積函數(shù)收斂速度快，定位精度比其他兩種算法分別提高了44%，25%左右。

為充分驗(yàn)證CS-K-means算法的實(shí)際應(yīng)用性，將圖4所示的室內(nèi)空間中隨機(jī)分布的6個(gè)Wi-Fi熱點(diǎn)信號(hào)發(fā)射源增加到8個(gè)，在每個(gè)指紋采集參考點(diǎn)處進(jìn)行50次的獨(dú)立采樣，將50次的采樣值取平均值后存入指紋數(shù)據(jù)庫。表4為不同信號(hào)采集環(huán)境下的定位結(jié)果。

圖8 定位誤差累積分布函數(shù)圖Fig.8 Cumulative distribution function of location error

表4 不同信號(hào)采集環(huán)境下的定位結(jié)果

由表4中的實(shí)驗(yàn)對比數(shù)據(jù)可知，在Wi-Fi熱點(diǎn)信號(hào)發(fā)射源個(gè)數(shù)相同的情況下，指紋采樣次數(shù)的增加，有效減小了信號(hào)的多徑傳播效應(yīng)和同頻干擾對Wi-Fi熱點(diǎn)RSSI采樣值的影響，使得所求采樣平均值更接近于信號(hào)實(shí)際的RSSI值，保證了指紋數(shù)據(jù)的可靠性，其最終定位時(shí)間和定位誤差相對較低，定位效果較好；在指紋采樣次數(shù)相同的情況下，隨著室內(nèi)Wi-Fi熱點(diǎn)信號(hào)發(fā)射源個(gè)數(shù)的增加，指紋數(shù)據(jù)更加豐富，定位信息充足，其定位時(shí)間和定位誤差也相應(yīng)降低。30個(gè)待定位點(diǎn)在4種不同信號(hào)采集環(huán)境下的定位誤差結(jié)果，如圖9。

從圖9可知，隨著Wi-Fi熱點(diǎn)信號(hào)發(fā)射源個(gè)數(shù)和采樣次數(shù)的增加，待定位點(diǎn)的定位誤差波動(dòng)范圍由黑色折線的0.482～2.012 m逐漸降至紅色折線的0.258～1.317 m，誤差波動(dòng)范圍不斷減小，趨于穩(wěn)定，由此可以說明，CS-K-means算法適用于Wi-Fi信號(hào)熱點(diǎn)信號(hào)源多，信號(hào)傳播環(huán)境復(fù)雜的室內(nèi)空間，該方法能夠有效減小或消除室內(nèi)環(huán)境噪聲對指紋數(shù)據(jù)采集帶來的不利影響，保證了指紋數(shù)據(jù)的穩(wěn)定性和準(zhǔn)確性，有效降低室內(nèi)定位誤差，提高定位精度，更具有實(shí)用性。

圖9 不同信號(hào)采集環(huán)境下的定位誤差圖Fig.9 Positioning error diagram under different signal acquisition environments

4 結(jié) 論

Wi-Fi技術(shù)的迅猛發(fā)展為室內(nèi)定位研究提供了全新的技術(shù)支持，針對指紋數(shù)據(jù)庫在K-means聚類中易將遠(yuǎn)距離參考點(diǎn)聚為一類的問題，研究采用基于坐標(biāo)相似度的方法進(jìn)行改進(jìn)，在計(jì)算聚類相似度過程中加入物理坐標(biāo)參考因素，將遠(yuǎn)距離參考點(diǎn)劃歸其他類中。針對WKNN 算法采用固定K值的問題，本研究可以根據(jù)每個(gè)測試點(diǎn)的匹配參考點(diǎn)間實(shí)際距離的相似度特性動(dòng)態(tài)選擇K值。所提改進(jìn)算法僅需使用現(xiàn)有指紋數(shù)據(jù)，通過在實(shí)際定位環(huán)境內(nèi)所進(jìn)行的大量數(shù)據(jù)實(shí)驗(yàn)表明，改進(jìn)算法的定位精度比傳統(tǒng)的WKNN算法提高了44%左右?；谝陨蟽?yōu)點(diǎn)，提出的算法將更適用于實(shí)際應(yīng)用。