基于Wi-Fi指紋的改進(jìn)型室內(nèi)定位算法研究

秦國(guó)威， 孫新柱， 陳孟元

(安徽工程大學(xué) 安徽省電氣傳動(dòng)與控制重點(diǎn)實(shí)驗(yàn)室， 安徽 蕪湖 241000)

近幾年，伴隨著無(wú)線通訊技術(shù)、物聯(lián)網(wǎng)技術(shù)和高級(jí)移動(dòng)終端的飛速發(fā)展，人們愈發(fā)迫切地希望得到與所在位置相關(guān)的服務(wù)?；谖恢梅?wù)的室內(nèi)定位系統(tǒng)能夠準(zhǔn)確獲得用戶的位置信息，具備很好的發(fā)展和應(yīng)用前景。當(dāng)前，全球定位系統(tǒng)[1](Global Position System，GPS)是主流的定位和導(dǎo)航技術(shù)，在人們的生活和工作中運(yùn)用非常廣泛，其技術(shù)是通過(guò)衛(wèi)星獲取地理位置信息，但是在室內(nèi)環(huán)境下，由于衛(wèi)星信號(hào)易受障礙物、多徑效應(yīng)等因素的干擾，使得定位目標(biāo)和衛(wèi)星之間無(wú)法進(jìn)行視距內(nèi)的通信，因此，GPS用于室內(nèi)定位存在一定的局限性。

隨著Wi-Fi技術(shù)的成熟與普及，基于Wi-Fi的室內(nèi)定位技術(shù)逐漸成為當(dāng)前定位領(lǐng)域的研究熱點(diǎn)[2-4]。相比于其他定位技術(shù)(如藍(lán)牙[5]、Zigbee[6]定位)，Wi-Fi定位技術(shù)具有如下的優(yōu)勢(shì)：(1)無(wú)遮擋，覆蓋面廣，Wi-Fi信號(hào)覆蓋半徑可以達(dá)到約100 m，受非視距影響小；(2)傳輸速率快，能夠在短時(shí)間內(nèi)快速傳輸信息；(3)不存在激光、視覺(jué)等常見(jiàn)的特征提取和數(shù)據(jù)關(guān)聯(lián)困難的問(wèn)題等等。目前，常用的室內(nèi)定位方法可分為傳播模型法[7-8]和信號(hào)分布模型匹配法[9]。傳播模型法是指利用無(wú)線信號(hào)，得到手持設(shè)備和信號(hào)發(fā)射端(Access Points，AP)之間的距離信息，從而推算出目前此接收設(shè)備所處的位置。傳播模型法中常用的包括信號(hào)到達(dá)時(shí)間法[10](Time of Arrival，TOA)、信號(hào)到達(dá)時(shí)間差法[11](Time Difference of Arrival，TDOA)、信號(hào)到達(dá)角法[12](Angel of Arrival，AOA)。其中，使用TOA技術(shù)定位比較穩(wěn)定，但需要AP端和信號(hào)接收端的時(shí)鐘同步，對(duì)所有需要定位的接收設(shè)備皆進(jìn)行時(shí)鐘校準(zhǔn)顯然是不現(xiàn)實(shí)的。而TDOA方法雖不需要進(jìn)行AP和接收設(shè)備時(shí)鐘的同步校準(zhǔn)，但是將接收設(shè)備與AP之間的時(shí)間同步問(wèn)題轉(zhuǎn)化為了AP與AP之間的時(shí)間同步問(wèn)題，然而Wi-Fi的傳輸速率相當(dāng)快，瞬間的誤差將會(huì)導(dǎo)致測(cè)距上極大的偏差，為了提高測(cè)算位置的精度，此方法必需要對(duì)AP端進(jìn)行硬件改造，以獲得精準(zhǔn)的測(cè)量時(shí)間。另外，信號(hào)到達(dá)角法是通過(guò)接收設(shè)備接收到兩個(gè)信號(hào)發(fā)射端信號(hào)的角度來(lái)估計(jì)自身位置，這種方法一般需要一種特殊的天線來(lái)得到精確的角度信息，這無(wú)疑會(huì)增加接收器的成本及功耗，難以實(shí)現(xiàn)。因此，傳播模型法在實(shí)際應(yīng)用中存在較大的距離或角度誤差，難以完成室內(nèi)較大范圍內(nèi)的精確定位。信號(hào)分布模型匹配法通常分為兩個(gè)階段進(jìn)行：離線采集階段和在線定位階段。在離線階段利用信號(hào)特征建立信號(hào)指紋數(shù)據(jù)庫(kù)，將實(shí)時(shí)采集的信號(hào)特征信息與指紋數(shù)據(jù)庫(kù)中的特征信息進(jìn)行匹配，利用相應(yīng)的匹配算法，最終得出最優(yōu)的位置估計(jì)。此方法相對(duì)傳播模型法定位具有明顯的優(yōu)勢(shì)。

為此，本文選擇基于概率模型的信號(hào)分布模型匹配法進(jìn)行室內(nèi)定位。但是由于室內(nèi)環(huán)境的復(fù)雜性，數(shù)據(jù)庫(kù)指紋的非連續(xù)性，導(dǎo)致匹配精度還有很大的提升空間。同時(shí)目前利用的傳統(tǒng)的KNN、加權(quán)KNN[13]等算法，效率比較低，定位時(shí)間相對(duì)較長(zhǎng)。本文基于此運(yùn)用一種豐富位置指紋特征的方法以提高定位精度。此方法將手持設(shè)備的方向角和信號(hào)發(fā)射點(diǎn)的數(shù)目，加入指紋庫(kù)，豐富數(shù)據(jù)庫(kù)的位置特征。同時(shí)在線匹配過(guò)程中采用K-means[14-15]聚類加權(quán)KNN算法以提高匹配的效率。

1 位置指紋定位方法

在Wi-Fi等無(wú)線通訊技術(shù)定位領(lǐng)域，通常用到的測(cè)量參數(shù)有信號(hào)強(qiáng)度(RSSI)與信噪比(SNR)。RSSI指信號(hào)接收端接收到的Wi-Fi信號(hào)強(qiáng)度，在通信上用來(lái)判定鏈接質(zhì)量；SNR是指放大器的輸出信號(hào)電壓與同時(shí)輸出的噪聲電壓之比，很顯然，SNR越小表明信號(hào)中包含的噪聲越大。由于室內(nèi)環(huán)境的障礙物及多徑效應(yīng)等影響，室內(nèi)環(huán)境中RSSI值相比于SNR更為穩(wěn)定。因此，本文采用的Wi-Fi定位方法為位置指紋定位方法，此方法在常規(guī)的基于RSSI的位置指紋定位的基礎(chǔ)上，加入手持接收方向x和信號(hào)發(fā)射點(diǎn)數(shù)目R以擴(kuò)展位置指紋離線數(shù)據(jù)庫(kù)，進(jìn)而提高匹配的精度。其中，人體手持設(shè)備的朝向角θ可以通過(guò)手機(jī)自帶的電子羅盤(pán)測(cè)得。

1.1 離線采集階段

離線采集階段的主要任務(wù)是構(gòu)建一個(gè)位置指紋數(shù)據(jù)庫(kù)。首先繪制定位區(qū)域地圖，在定位區(qū)域合理規(guī)劃好一系列的測(cè)試參考點(diǎn)。之后依次測(cè)量各參考點(diǎn)來(lái)自各接入點(diǎn)AP的RSSI值(多次測(cè)量取平均值)，手持設(shè)備朝向角θ以及接入點(diǎn)AP的數(shù)量R，按一定的格式記錄在數(shù)據(jù)庫(kù)中，該數(shù)據(jù)庫(kù)就是離線位置數(shù)據(jù)庫(kù)。建立方法如下，在室內(nèi)定位環(huán)境下，按照一定的原則選取參考點(diǎn)，且在各個(gè)參考點(diǎn)上對(duì)每個(gè)接入點(diǎn)AP不間斷采樣一段時(shí)間，并保持手持設(shè)備的角度不變，得到每個(gè)AP的均值mLi存入數(shù)據(jù)庫(kù)中，構(gòu)成位置指紋圖IM：

IM={Z,A,M,Maci,θ}，

(1)

1.2 在線定位階段

在線定位階段是利用手持設(shè)備測(cè)得在某一位置處的Wi-Fi信號(hào)強(qiáng)度RSSI值，通過(guò)相應(yīng)的匹配算法，將實(shí)測(cè)的數(shù)據(jù)信息與離線數(shù)據(jù)庫(kù)中的指紋信息進(jìn)行類比，將會(huì)在離線數(shù)據(jù)庫(kù)中獲得一組相似的Wi-Fi指紋信息。 手持設(shè)備朝向角由手機(jī)電子羅盤(pán)自動(dòng)測(cè)得，從而完成定位。目前常用的在線匹配算法主要有K近鄰算法(KNN)和K加權(quán)近鄰算法(WKNN)等。

1.2.1 K近鄰算法

K近鄰算法的主要思想是將實(shí)測(cè)的Wi-Fi強(qiáng)度信息與離線指紋數(shù)據(jù)庫(kù)中指紋信息進(jìn)行匹配，通過(guò)一一計(jì)算實(shí)時(shí)測(cè)量的RSSI樣本數(shù)據(jù)與離線指紋數(shù)據(jù)庫(kù)中所有的RSSI值之間的歐幾里得距離，進(jìn)而找出與實(shí)時(shí)定位點(diǎn)相似度最高的K個(gè)指紋點(diǎn)，最終將這K個(gè)點(diǎn)的質(zhì)心作為定位估計(jì)結(jié)果。K近鄰算法定位流程如圖1所示。

圖1 K近鄰算法定位流程圖

(1)取第i個(gè)實(shí)時(shí)采樣點(diǎn)與指紋點(diǎn)之間的歐幾里德距離為di，計(jì)算式如下

(2)

(2)將實(shí)時(shí)采樣點(diǎn)與所有參考點(diǎn)的RSSI值的歐氏距離進(jìn)行排序，逐一比較，可以得出歐氏距離最小的K個(gè)參考點(diǎn)，然后計(jì)算出它們的質(zhì)心為

(3)

1.2.2 K加權(quán)近鄰算法

根據(jù)上述的K近鄰算法可以清晰找出RSSI值歐氏距離最小的K個(gè)指紋參考點(diǎn)，再對(duì)此K個(gè)指紋參考點(diǎn)的位置坐標(biāo)按照相似度屬性賦予不同的權(quán)重系數(shù)ωi，表達(dá)式為

(4)

最終將這個(gè)指紋參考點(diǎn)的位置坐標(biāo)加權(quán)求和，得出定位結(jié)果：

(5)

其中(x，y)是待定點(diǎn)的坐標(biāo)，(xi，yi)是指紋點(diǎn)的坐標(biāo)。

2 基于聚類的K加權(quán)近鄰Wi-Fi定位算法

2.1 K-means聚類算法

K-means聚類算法首先要從數(shù)據(jù)集中隨機(jī)選定K個(gè)聚類中心，形成隨機(jī)的K個(gè)簇;其次按照最近鄰的原則分配樣本，將各個(gè)數(shù)據(jù)對(duì)象分配到相應(yīng)的簇中；接著，將每個(gè)簇中的所有數(shù)據(jù)對(duì)象的質(zhì)心作為新的聚類中心，進(jìn)而計(jì)算準(zhǔn)則目標(biāo)函數(shù)的值；重復(fù)迭代該步驟，直到聚類中心點(diǎn)恒定為止。在迭代過(guò)程中，一次次中心點(diǎn)的更新會(huì)使得準(zhǔn)則目標(biāo)函數(shù)的值逐漸減小，最終收斂至一個(gè)固定的值。

K-means算法與其他聚類算法相比具備的優(yōu)勢(shì)在于，它不可能出現(xiàn)多重聚類中心的情況，因此在很大程度上可以規(guī)避聚類中心模糊問(wèn)題。

K-means算法的準(zhǔn)則目標(biāo)函數(shù)為

(6)

其中K表示簇的個(gè)數(shù)，Ci表示第i個(gè)簇，ci表示簇Ci的聚類中心，θk表示簇內(nèi)標(biāo)準(zhǔn)差，x表示任意的數(shù)據(jù)對(duì)象。

綜上，K-means聚類算法的目標(biāo)即是使得準(zhǔn)則目標(biāo)函數(shù)值J(C)最小。K-means的K值會(huì)影響最小J值。K-means算法的核心在于如何確定聚類數(shù)，保證目標(biāo)函數(shù)最小。K-means算法的流程如圖2所示。

圖2 K-means算法流程圖

2.2 基于K-means的K加權(quán)近鄰Wi-Fi定位算法

在Wi-Fi室內(nèi)定位中，基于聚類和KNN結(jié)合的Wi-Fi定位算法CKNN同樣分為離線(訓(xùn)練)和在線(推理)定位兩個(gè)階段完成。首先在離線階段，將所有的參考樣本進(jìn)行聚類，進(jìn)而確定每個(gè)類別的中心以及每個(gè)數(shù)據(jù)對(duì)象所對(duì)應(yīng)的簇。其次在推理定位階段，先是查找出目標(biāo)樣本與聚類中最相似的簇，然后通過(guò)類比，再找到最相似簇中K個(gè)最相似的鄰參考樣本，接著對(duì)這K個(gè)參考樣本所對(duì)應(yīng)的位置加權(quán)取平均，最終可得到需預(yù)測(cè)的目標(biāo)樣本所對(duì)應(yīng)的位置。

(7)

按照此步驟依次計(jì)算，計(jì)算r向量與其他簇聚類中心RSSI的cosine相似度，可以得到w個(gè)cosine相似度(T1，T2，…，Tw)，其中T值最大的即為Dw與r是最相似的。由上式可確定最相似類別Dw與r向量最相似的k個(gè)樣本rk1，rk2，…，rkk，其對(duì)應(yīng)的位置坐標(biāo)為(xk1，yk1)，(xk2，yk2)，…，(xkk，ykk)。進(jìn)一步對(duì)相似度進(jìn)行歸一化處理，將其影響權(quán)重定義為{wk1，wk2，…，wkk}，計(jì)算如下：

(8)

將求得的樣本坐標(biāo)按上述的權(quán)重加權(quán)，最終確定的目標(biāo)位置的坐標(biāo)如下：

(9)

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

本實(shí)驗(yàn)是在安徽工程大學(xué)行政樓A座的三樓檔案室完成的，實(shí)驗(yàn)中采用的移動(dòng)站接收設(shè)備是一款華為榮耀8手機(jī)，共布置有4個(gè)AP，使用的都是普通型號(hào)的路由器DIR-629。下載一種基于Android平臺(tái)的Wi-Fi信號(hào)網(wǎng)絡(luò)RSSI測(cè)量軟件。實(shí)驗(yàn)過(guò)程中，每個(gè)時(shí)段均采用1 s的采樣率采集數(shù)據(jù)3 min，分別采集34個(gè)指紋點(diǎn)和20個(gè)待定位點(diǎn)。其具體的分布如圖3所示。

圖3 指紋采集區(qū)域圖

3.1 AP個(gè)數(shù)與匹配精度的相關(guān)性

利用上述方法完成離線采集的數(shù)據(jù)以后，圖4給出了不同接入點(diǎn)AP個(gè)數(shù)對(duì)K加權(quán)近鄰法(WKNN)與基于K-means加權(quán)的K近鄰法(CKNN)定位的精度影響。

圖4 不同AP個(gè)數(shù)精度對(duì)比圖

由圖4可以清晰看出，當(dāng)信號(hào)發(fā)射端AP數(shù)目為1～4個(gè)時(shí)，定位的精度都在不斷提高，與此同時(shí)，兩種算法定位的精度差別并不大。當(dāng)AP個(gè)數(shù)為2～3個(gè)時(shí)，定位精度迅速提高，此后，當(dāng)AP個(gè)數(shù)為3～4個(gè)時(shí)，雖然精度還在不斷提高，但是變化已經(jīng)很緩慢，基本上趨于相同，最終的定位精度在1.5 m以下。由此可知，信號(hào)發(fā)射端AP個(gè)數(shù)對(duì)Wi-Fi定位的精度有很重要的作用，不可忽視。綜合考慮，本文以下所做的對(duì)比實(shí)驗(yàn)采用的AP個(gè)數(shù)為4個(gè)。

3.2 定位誤差比較

為了驗(yàn)證本文提出的將手持設(shè)備方向角加入離線數(shù)據(jù)庫(kù)中能夠提高定位的精度，本文選擇若干個(gè)測(cè)試點(diǎn)測(cè)試該方法的性能。定位性能通常由均方根誤差和定位誤差累積概率作為參考標(biāo)準(zhǔn)。

3.2.1 均方根誤差

在目前實(shí)際的定位系統(tǒng)中，不管采用何種定位方法，最終的估計(jì)位置和理想位置總會(huì)存在一定程度的偏差，這即為定位系統(tǒng)的位置誤差。

假設(shè)待定位點(diǎn)的實(shí)際位置為(xa，ya)，估計(jì)位置為(xe，ye)，定位系統(tǒng)的均方根誤差為

(10)

3.2.2 定位誤差累積概率

定位誤差的累積概率表示位置誤差小于或等于某個(gè)值的概率，可表示為

P=P(e≤ea)。

(11)

位置誤差累積概率分布曲線從左至右趨勢(shì)是上升的，而且是收斂的，曲線收斂的速率表征定位誤差的大小，速率越快表明定位誤差越小，反之，誤差越大。

離線階段分別采用常規(guī)指紋庫(kù)和擴(kuò)展指紋庫(kù)，在線階段采用加權(quán)KNN算法的定位性能測(cè)試如圖5所示。

圖5 定位誤差對(duì)比圖

圖6 定位精度對(duì)比圖

圖7 定位時(shí)間對(duì)比圖

3.3 算法性能對(duì)比

在相同型號(hào)和配置的計(jì)算機(jī)上運(yùn)行K加權(quán)近鄰算法和基于聚類的K加權(quán)近鄰算法，從以下3個(gè)指標(biāo)對(duì)兩種算法進(jìn)行對(duì)比并作評(píng)價(jià)。3個(gè)指標(biāo)分別為最大誤差、誤差平均值、定位誤差的方差，對(duì)比的結(jié)果如表1所示，定位的精度對(duì)比如圖6所示。

表1 算法性能對(duì)比

由表1看出，同一種算法在不同指紋庫(kù)的最大誤差和誤差的平均值還是有差距的，然而不同的算法在同一個(gè)指紋庫(kù)的最大誤差和誤差平均值相差無(wú)幾，進(jìn)而得出兩種算法在同一種離線指紋庫(kù)下進(jìn)行在線計(jì)算的精度差距很小，同種算法在擴(kuò)展指紋庫(kù)比在常規(guī)指紋庫(kù)下定位的精度得到了很大提升。同時(shí)在圖6中可以清晰地看出擴(kuò)展指紋庫(kù)定位的精度明顯高于離線指紋庫(kù)，所以離線擴(kuò)展指紋庫(kù)更有利于提高Wi-Fi定位的精度。

3.4 實(shí)時(shí)性對(duì)比

由3.3節(jié)可知，K加權(quán)近鄰算法(WKNN)和基于聚類的K加權(quán)近鄰算法(CKNN)在同種離線數(shù)據(jù)庫(kù)的狀態(tài)下，精度相差無(wú)幾，因此，實(shí)時(shí)性成為評(píng)價(jià)兩種算法優(yōu)劣的決定性因素。二者定位時(shí)間如圖7所示。

不難看出，基于聚類的K加權(quán)近鄰算法(CKNN)幾乎要比K加權(quán)近鄰算法(WKNN)定位要快一倍。因此，基于聚類的K加權(quán)近鄰算法更具有實(shí)時(shí)性。

4 結(jié) 論

Wi-Fi室內(nèi)定位是目前的研究熱點(diǎn)之一，本文將信號(hào)發(fā)射端AP的數(shù)目和手持設(shè)備的方向角加入到Wi-Fi位置指紋數(shù)據(jù)庫(kù)中，實(shí)驗(yàn)表明，加入手持設(shè)備的方向角和接入點(diǎn)的數(shù)量改進(jìn)后的指紋數(shù)據(jù)庫(kù)與常規(guī)數(shù)據(jù)庫(kù)相比，精度有了明顯的提升。在線定位階段采用將K-means聚類算法與加權(quán)K近鄰算法相結(jié)合的算法，與加權(quán)的K近鄰算法相比，Wi-Fi指紋定位的精度有了明顯改善，定位時(shí)間明顯縮短，定位速率明顯加快。因此，離線階段建立擴(kuò)展指紋庫(kù)，在線階段運(yùn)用基于聚類的K加權(quán)近鄰算法不僅使得Wi-Fi定位精度得到很好的改善，實(shí)用性也得到了明顯的改進(jìn)。雖然，本文Wi-Fi定位性能得到了明顯的改善，但是算法性能還有待提高，相似度公式較繁雜等，這將是接下來(lái)要集中精力研究的方面。

[ 參 考 文 獻(xiàn) ]

[1] AFRAIMOVICH E L.GPS global detection of the ionospheric response to solar flares.Radio Science，2016，35(6)：1417-1424.

[2]ZHOU Zi-mu，WU Chen-shu，YANG Zheng，et al.Sensorless Sensing with Wi-Fi.Tsinghua Science and Technology，2015，20(1)：1-6.

[3]ZHU Nan，ZHAO Hong-bo，F(xiàn)ENG Wen-quan，et al.A novel particle filter approach for indoor positioning by fusing Wi-Fi and inertial sensors.Chinese Journal of Aeronautics，2015，28(6)：1725-1734.

[4]陳斌濤，劉任任，陳益強(qiáng)，等.動(dòng)態(tài)環(huán)境中的Wi-Fi指紋自適應(yīng)室內(nèi)定位方法.傳感技術(shù)學(xué)報(bào)，2015，28(5)：729-738

[5]HALLBERG J，NILSSON M.Positioning with Bluetooth，IrDA and RFID.Lule?：Lule? University of Technology，2016.

[6]ROY U K.Modified source-routing for large-scale pseudo-linear ZigBee networks//IEEE International Conference on Research in Computational Intelligence and Communication Networks.Kolkata：IEEE，2016：85-89.

[7]劉光.基于無(wú)線傳感器的移動(dòng)機(jī)器人定位研究.天津：南開(kāi)大學(xué)，2010.

[8]YUAN J，HUANG Y，TAO F S T.Active exploration using a scheme for autonomous allocation of landmarks.Robotica，2014，32(5)：757-782.

[9]路飛，田國(guó)會(huì)，劉國(guó)良，等.智能空間下基于Wi-Fi指紋定位與粒子濾波的服務(wù)機(jī)器人復(fù)合全局定位系統(tǒng)設(shè)計(jì).機(jī)器人，2016，38(2)：178-184.

[10] PAK J M，AHN C K，PENG S，et al.Distributed Hybrid Particle/FIR Filtering for Mitigating NLOS Effects in TOA Based Localization Using Wireless Sensor Networks.IEEE Transactions on Industrial Electronics，2016(99)：1.

[11] XIONG H，CHEN Z，AN W，et al.Robust TDOA localization algorithm for asynchronous wireless sensor networks.International Journal of Distributed Sensor Networks，2015，2015：10.

[12] WANG Y，HO K C.An Asymptotically Efficient Estimator in Closed-Form for 3-D AOA Localization Using a Sensor Network.IEEE Transactions on Wireless Communications，2015，14(12)：6524-6535.

[13] MAILLO J，RAMIREZ S，TRIGUERO I，et al.kNN-IS：An Iterative Spark-based design of the k-Nearest Neighbors Classifier for Big Data.Knowledge-Based Systems，2017，117：3-15.

[14] 吳夙慧，成穎，鄭彥寧，等.K-means算法研究綜述.現(xiàn)代圖書(shū)情報(bào)技術(shù)，2011(5)：28-35.

[15] 白雪峰，蔣國(guó)棟.基于改進(jìn)K-means聚類算法的負(fù)荷建模及應(yīng)用.電力自動(dòng)化設(shè)備，2010，30(7)：80-83.