基于多視角聚類的WiFi指紋定位方法研究?

馬宗方呂麗萍田鴻朋王 艷

(西安建筑科技大學(xué)信息與控制工程學(xué)院，陜西 西安 710055)

據(jù)調(diào)查研究表明，人類有70%以上的活動(dòng)時(shí)間是在室內(nèi)。室外定位導(dǎo)航可由全球定位系統(tǒng)(Global Positioning System，GPS)定位技術(shù)得到有效解決[1]，而室內(nèi)定位技術(shù)相較于室外定位技術(shù)還不成熟。近幾年，很多學(xué)者已在室內(nèi)定位領(lǐng)域進(jìn)行研究，常用的3類技術(shù)為:①鋪設(shè)相關(guān)特殊設(shè)備實(shí)現(xiàn)定位。例如射頻識(shí)別、無(wú)載波通信等[2－5]；②利用傳感器獲取相關(guān)位置信息。例如加速度計(jì)、陀螺儀等[6－8]；③借助已有的WiFi網(wǎng)絡(luò)覆蓋環(huán)境。例如指紋定位、測(cè)距技術(shù)等[9－10]。第3類技術(shù)相較于第1類和第2類技術(shù)，即節(jié)省了購(gòu)買設(shè)備與搭建測(cè)試環(huán)境的費(fèi)用，開(kāi)發(fā)過(guò)程也十分便捷，相對(duì)更容易實(shí)現(xiàn)。同時(shí)，WiFi無(wú)線信號(hào)具有傳輸速率快、功耗低、通信能力強(qiáng)的優(yōu)點(diǎn)。因此，對(duì)于WiFi指紋定位技術(shù)的深入研究具有重要的科研意義與工程應(yīng)用價(jià)值。

目前很多學(xué)者從WiFi接收信號(hào)強(qiáng)度指示(Received Signal Strength Indication，RSSI)、信號(hào)穩(wěn)定性校準(zhǔn)、離線建庫(kù)方法等方向進(jìn)行改進(jìn)。比如，文獻(xiàn)[11]提出了一種根據(jù)環(huán)境變化動(dòng)態(tài)更新指紋庫(kù)的方法，在降低成本的同時(shí)，有效提高了系統(tǒng)的穩(wěn)定性與自適應(yīng)性，但其定位精度準(zhǔn)確度相對(duì)較低；文獻(xiàn)[12]提出了改進(jìn)的K-means算法位置指紋定位技術(shù)，通過(guò)優(yōu)化函數(shù)來(lái)獲取較優(yōu)的指紋庫(kù)初始類中心，有效提高了分類效果和定位精度。文獻(xiàn)[13]提出了一種基于位置聚類結(jié)果的指紋定位算法，糾正了信號(hào)強(qiáng)度聚類的不合理，有效提高了算法性能，但指紋定位原理是采用實(shí)際采集的WiFi信號(hào)強(qiáng)度與指紋庫(kù)數(shù)據(jù)進(jìn)行匹配，進(jìn)而獲取位置，單純采用位置聚類會(huì)影響定位效果。綜上所述，以上方法均屬于單視角聚類定位，且對(duì)于定位系統(tǒng)的精度貢獻(xiàn)不明顯，即現(xiàn)有方法無(wú)法解決現(xiàn)存實(shí)際問(wèn)題。

針對(duì)該類單視角聚類定位方法中普遍存在的聚類結(jié)果不合理性與聚類視角單一化問(wèn)題，本文提出基于位置坐標(biāo)信息與信號(hào)強(qiáng)度信息的多視角聚類方法，該方法選擇N個(gè)無(wú)線接入點(diǎn)(Access Point，AP)樣本，通過(guò)對(duì)樣本集進(jìn)行閾值－均值濾波后，結(jié)合Kmeans聚類算法對(duì)多視角信號(hào)(強(qiáng)度和位置)進(jìn)行區(qū)域劃分，并建立離線指紋庫(kù)，實(shí)時(shí)獲取待定位位置。一方面糾正信號(hào)強(qiáng)度聚類結(jié)果的不合理，另一方面解決位置聚類結(jié)果參考性小，準(zhǔn)確度低的問(wèn)題。

1 研究方法

1.1 WiFi指紋定位原理

WiFi指紋定位[14]技術(shù)的工作過(guò)程一般為兩個(gè)階段，離線建庫(kù)與在線匹配。其基本原理及工作流程如圖1所示。

圖1 指紋定位基本原理示意圖

離線建庫(kù)實(shí)際是預(yù)先將所有參考點(diǎn)的指紋錄入數(shù)據(jù)庫(kù)的過(guò)程。通常確定待定位區(qū)域后，需合理劃分待測(cè)區(qū)域空間并選擇M個(gè)參考點(diǎn)，每個(gè)參考點(diǎn)的中心點(diǎn)坐標(biāo)即為指紋的參考點(diǎn)坐標(biāo)，在每個(gè)參考點(diǎn)處采集WiFi信號(hào)強(qiáng)度，記錄參考點(diǎn)坐標(biāo)與WiFi信號(hào)強(qiáng)度一一對(duì)應(yīng)的值[15]。

假設(shè)在參考點(diǎn)m處檢測(cè)到了N個(gè)AP[16]，則參考點(diǎn)m的指紋庫(kù)可以表示為式(1):

式中:RPm為參考點(diǎn)m的指紋庫(kù)表示，xm，ym為參考點(diǎn)m的位置坐標(biāo)，RSSIm1，RSSIm2，…，RSSImn，…，RSSImN為第m個(gè)參考點(diǎn)的N個(gè)AP對(duì)應(yīng)的信號(hào)強(qiáng)度值，對(duì)應(yīng)錄入相應(yīng)WiFi指紋庫(kù)，得到離線指紋庫(kù)，可表示為式(2):

在線匹配時(shí)，每個(gè)定位點(diǎn)的位置估計(jì)可由實(shí)時(shí)采集的待定位目標(biāo)的信號(hào)強(qiáng)度RSSI與指紋庫(kù)數(shù)據(jù)去唯一確定。具體過(guò)程是實(shí)時(shí)獲取待定位目標(biāo)的RSSI值，并與離線指紋庫(kù)中的信號(hào)強(qiáng)度信息進(jìn)行匹配得到估計(jì)的位置坐標(biāo)，從而實(shí)現(xiàn)定位。其中最常用的方法為K近鄰(K-Nearest Neighbor，KNN)[17－18]匹配算法。其主要原理為計(jì)算實(shí)測(cè)點(diǎn)的信號(hào)強(qiáng)度與每個(gè)參考點(diǎn)的信號(hào)強(qiáng)度的距離，找到距離臨近的K個(gè)點(diǎn)，進(jìn)一步進(jìn)行實(shí)測(cè)點(diǎn)位置估計(jì)，也常用加權(quán)K近鄰[19－20]。

1.2 數(shù)據(jù)的濾波處理

為保證數(shù)據(jù)的有效性與后期算法的處理效果，本文采用閾值濾波與取平均值的方法對(duì)原始數(shù)據(jù)進(jìn)行處理。由于原始數(shù)據(jù)量較大且無(wú)明顯規(guī)律，通過(guò)分析歸納后，統(tǒng)一歸一化處理測(cè)試樣本的經(jīng)緯度信息；刪除信號(hào)強(qiáng)度信息微弱的AP點(diǎn)，RSSI值為－127表示W(wǎng)iFi信號(hào)幾乎沒(méi)有，用自然數(shù)100來(lái)代替WiFi信號(hào)微弱的點(diǎn)；經(jīng)處理后的參考點(diǎn)數(shù)據(jù)波動(dòng)較大，存在干擾點(diǎn)與異常點(diǎn)，需進(jìn)一步閾值濾波處理，使得處理后的數(shù)據(jù)相對(duì)分布集中。每次對(duì)比新值與上次值的差值，差值記為δ，閾值記為A，并判斷:①δ≤A，新值有效；②δ>A，取新值與上次值的平均值；重復(fù)上述步驟直到?jīng)]有新值出現(xiàn)；最后對(duì)每一個(gè)參考點(diǎn)的20組數(shù)據(jù)求平均，確定每個(gè)參考點(diǎn)對(duì)應(yīng)一組數(shù)據(jù)，并保存預(yù)處理后的數(shù)據(jù)。

1.3 多視角K-means聚類算法離線建庫(kù)

假設(shè)多視角聚類數(shù)據(jù)集為X，則多視角K-means聚類的目標(biāo)函數(shù)為式(3):

式中:V為視角個(gè)數(shù)，C為聚類的類別個(gè)數(shù)，M為樣本個(gè)數(shù)，p為權(quán)重指數(shù)，通常取2，為第v個(gè)視角的權(quán)重向量，δim非0即1，當(dāng)xm屬于第i類時(shí)為1，否則為0，x為樣本xm的第v個(gè)視角向量為第v個(gè)視角的第i類聚類中心向量。

利用拉格朗日乘子最優(yōu)化方法最小化式(3)，得到多視角聚類算法的聚類中心，其迭代表達(dá)式如式(4):

權(quán)重向量wv的迭代表達(dá)式，如式(5):

式中:為樣本xm的第v′個(gè)視角向量，為第v′個(gè)視角的第i的中心向量。

多視角K-means聚類算法流程如表1所示。

表1 多視角K-means聚類算法流程

該表中輸入包括視角個(gè)數(shù)V，聚類個(gè)數(shù)C，樣本集X，權(quán)重指數(shù)p，值取2，迭代閾值τ。輸出為劃分聚類指數(shù)δ，類中心矩陣z，權(quán)重矩陣w。隨機(jī)初始化C個(gè)類中心，設(shè)定初始權(quán)重＝1/v；計(jì)算每個(gè)樣本到其類中心的歐式距離，按照最小距離分配標(biāo)簽的原則，給所有樣本劃分標(biāo)簽，確定劃分聚類指數(shù)δ，并利用式(4)更新迭代聚類中心矩陣z；利用式(5)更新計(jì)算權(quán)重矩陣w；利用式(3)更新計(jì)算目標(biāo)函數(shù)JH；如果‖Jt＋1－Jt‖<τ，算法結(jié)束，輸出結(jié)果，否則重新利用式(4)更新迭代聚類中心矩陣z。

1.4 WKNN算法在線匹配

實(shí)時(shí)定位階段，每個(gè)測(cè)試樣本在選擇自己所屬類別時(shí)，用基礎(chǔ)分類器依據(jù)信號(hào)強(qiáng)度信息對(duì)待測(cè)樣本進(jìn)行分類，選用KNN分類器。而后用WKNN算法實(shí)現(xiàn)類間找K個(gè)最近的距離，輔以權(quán)重W確定實(shí)際定位位置。

上述WKNN算法分類過(guò)程主要涉及三個(gè)步驟:K值選擇、距離計(jì)算、權(quán)重決策規(guī)則。

①K值選取

在WKNN分類算法中，近鄰個(gè)數(shù)K的選取對(duì)定位結(jié)果的穩(wěn)定性有一定程度的影響，K值過(guò)大可能會(huì)導(dǎo)致選擇的近鄰中包含有噪聲數(shù)據(jù)，而K值過(guò)小可能無(wú)法找到真正的近鄰，因此本文K值的選擇區(qū)間為[3，7]，默認(rèn)取值為3。

②距離計(jì)算

WKNN的距離度量標(biāo)準(zhǔn)為式(6):

式中:N為AP的個(gè)數(shù)，即特征向量的維數(shù)，其中p取2，表示歐氏距離，當(dāng)然也可用其他距離度量方式。d m為某個(gè)待測(cè)點(diǎn)信號(hào)強(qiáng)度與所屬類中第m個(gè)參考點(diǎn)信號(hào)強(qiáng)度的距離，在求取待測(cè)點(diǎn)與類內(nèi)所有參考點(diǎn)的距離后，選取K個(gè)最近距離。

③權(quán)重決策規(guī)則

當(dāng)找到距離最臨近的K個(gè)點(diǎn)后，通過(guò)式(7)來(lái)計(jì)算這K個(gè)點(diǎn)對(duì)實(shí)測(cè)點(diǎn)位置估計(jì)的重要程度，即權(quán)值:

式中:wk為類內(nèi)第k個(gè)參考點(diǎn)對(duì)待測(cè)位置的重要程度的體現(xiàn)，

最后，根據(jù)式(8)可求得實(shí)測(cè)的位置。

式中:，為實(shí)際的定位位置，xk，yk為K近鄰的位置信息。

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

2.1 數(shù)據(jù)濾波分析

實(shí)驗(yàn)選用UJIndoorLoc數(shù)據(jù)集，其為一個(gè)多建筑多樓層的室內(nèi)WiFi指紋定位數(shù)據(jù)庫(kù)，該數(shù)據(jù)集分為兩部分，訓(xùn)練樣本TrainingData與測(cè)試樣本ValidationData。本文選取第0棟建筑的第0層數(shù)據(jù)來(lái)驗(yàn)證本文的定位方法。

數(shù)據(jù)濾波過(guò)程為:歸一化測(cè)試樣本的經(jīng)緯度信息；剔除沒(méi)有強(qiáng)度信號(hào)的AP點(diǎn)，用－127替換信號(hào)強(qiáng)度為100的值；對(duì)一個(gè)參考點(diǎn)的數(shù)據(jù)進(jìn)行閾值濾波，使得濾波后的數(shù)據(jù)相對(duì)集中；對(duì)一個(gè)參考點(diǎn)的20組數(shù)據(jù)求平均，確定一個(gè)參考點(diǎn)對(duì)應(yīng)一組數(shù)據(jù)。

由于WiFi信號(hào)強(qiáng)度的不穩(wěn)定性，選取一個(gè)采樣點(diǎn)的20組數(shù)據(jù)進(jìn)行閾值處理，如圖2濾波前－后對(duì)比圖所示，圖中方形與三角形表示濾波之后的數(shù)據(jù)，可以看出信號(hào)強(qiáng)度波動(dòng)較大的參考點(diǎn)AP3與AP9進(jìn)行閾值濾波后，其RSSI值的變化程度減小，使得同一采樣點(diǎn)的數(shù)據(jù)更加平滑、可靠，最后針對(duì)閾值濾波數(shù)據(jù)進(jìn)行均值處理，保留每個(gè)參考點(diǎn)的一組預(yù)處理完的數(shù)據(jù)。

圖2 采樣點(diǎn)濾波前－后對(duì)比圖

2.2 多視角K-means聚類結(jié)果對(duì)比分析

為了驗(yàn)證采樣點(diǎn)多視角聚類對(duì)于定位精度的影響，實(shí)驗(yàn)過(guò)程分別對(duì)信號(hào)強(qiáng)度、位置以及多視角的聚類結(jié)果進(jìn)行分析，在K-means聚類算法中，聚類中心個(gè)數(shù)K的選取對(duì)聚類結(jié)果有不同程度的影響，通過(guò)對(duì)不同K值聚類結(jié)果分析，最終選擇K取值為4。

圖3為單視角與多視角聚類結(jié)果圖，圖中劃分到不同類的樣本用不同的符號(hào)標(biāo)記。由于單視角聚類中的信號(hào)強(qiáng)度聚類在結(jié)果上存在不合理性，實(shí)際距離比較遠(yuǎn)而強(qiáng)度信號(hào)差異較小的會(huì)聚成一類，如圖3(a)信號(hào)強(qiáng)度聚類所示，圖中橢圓圈出為一類，分布于兩個(gè)小區(qū)域，理論上各數(shù)據(jù)不屬于同一類，但其與強(qiáng)度信號(hào)類中心的距離決定了各數(shù)據(jù)屬于同一類，所以聚類結(jié)果明顯存在不合理性。而位置聚類在聚類結(jié)果上沒(méi)有表現(xiàn)出明顯的不合理性，但指紋定位最后需要用在線采集的信號(hào)強(qiáng)度RSSI值來(lái)匹配指紋庫(kù)，進(jìn)而確定待定位點(diǎn)的位置信息，這個(gè)過(guò)程會(huì)使其定位精度降低，如圖3(b)位置聚類所示，不能滿足定位精度要求。而從圖3(c)多視角聚類結(jié)果可以看出相近的點(diǎn)隸屬相同的類別，距離較遠(yuǎn)的點(diǎn)分屬不同的類別，相應(yīng)的彌補(bǔ)了信號(hào)強(qiáng)度與位置聚類的劣勢(shì)，聚類結(jié)果相對(duì)較好。由圖3分析可得，相對(duì)于單視角聚類而言，多視角聚類結(jié)果更合理、效果更好。

圖3 聚類結(jié)果

2.3 定位結(jié)果

為了更好的驗(yàn)證本文算法的性能，對(duì)測(cè)試樣本進(jìn)行了多次綜合試驗(yàn)。分別對(duì)單視角信號(hào)(信號(hào)強(qiáng)度或位置)與多視角(信號(hào)強(qiáng)度與位置)信號(hào)進(jìn)行聚類并建立離線指紋庫(kù)，使用基礎(chǔ)分類器WKNN對(duì)實(shí)測(cè)信號(hào)分類，待測(cè)信號(hào)依據(jù)分類結(jié)果在其所屬區(qū)域內(nèi)估計(jì)K個(gè)鄰近信號(hào)點(diǎn)，用近鄰以及相應(yīng)的權(quán)重值綜合確定該信號(hào)的實(shí)際位置。圖4為不同聚類方法定位結(jié)果的累積概率分布圖，從結(jié)果分析可知:本文的多視角聚類定位算法精度恒高于單視角(強(qiáng)度聚類或位置聚類)聚類定位算法，并且定位精度在4 m以內(nèi)的概率為83%，相比于信號(hào)強(qiáng)度聚類和位置聚類定位的結(jié)果，定位精度在4 m內(nèi)的概率提高了12%。圖5為本文算法定位的實(shí)際位置與真實(shí)位置的分布圖，結(jié)果證明本文算法基本滿足了定位場(chǎng)景的實(shí)際需求。

圖4 不同聚類方法定位結(jié)果的累積概率分布

圖5 定位位置與實(shí)際位置對(duì)比

3 結(jié)果與討論

本文針對(duì)指紋定位中方法單一及定位準(zhǔn)確度低的問(wèn)題，采用多視角(信號(hào)強(qiáng)度和位置)聚類方法實(shí)現(xiàn)了定位，得出多視角與單視角分類結(jié)果及其相對(duì)應(yīng)的累積概率分布與最終解算出的實(shí)際位置。通過(guò)對(duì)比分析實(shí)驗(yàn)結(jié)果，得出以下結(jié)論:

①多視角聚類糾正了WiFi信號(hào)強(qiáng)度聚類結(jié)果的不合理性，提高了位置聚類的分類準(zhǔn)確度。相比較而言，基于多視角聚類的WiFi指紋定位方法可靠性更強(qiáng)。

②通過(guò)實(shí)驗(yàn)對(duì)比，本文算法定位精度在4 m以內(nèi)的概率為83%，相比于信號(hào)強(qiáng)度聚類和位置聚類定位的結(jié)果，定位精度在4 m以內(nèi)的概率提高了12%，基本滿足了實(shí)際定位場(chǎng)景的應(yīng)用需求。

③該研究的數(shù)據(jù)集采用公共數(shù)據(jù)集，考慮到定位系統(tǒng)的實(shí)用價(jià)值，后期可針對(duì)實(shí)際應(yīng)用場(chǎng)景搭建實(shí)際的數(shù)據(jù)采集測(cè)試環(huán)境，進(jìn)行更深入的應(yīng)用研究修正。