基于RSSI信號(hào)特征的室內(nèi)分區(qū)指紋定位算法

高思遠(yuǎn)，馮秀芳

(太原理工大學(xué) 信息與計(jì)算機(jī)學(xué)院，山西 晉中 030600)

0 引 言

常用的基于WiFi的室內(nèi)定位技術(shù)主要有傳播模型法和基于WiFi的RSSI(received signal strength indicator)位置指紋法。基于RSSI的位置指紋定位方法在實(shí)際環(huán)境中有更好的定位效果，且易于部署，因此受到更多學(xué)者的青睞，國(guó)內(nèi)外學(xué)者相繼提出了許多基于WiFi的RSSI位置指紋定位方法。Li Changgeng等將曼哈頓距離引入到WKNN算法中，并根據(jù)RSSI值各維的差異是否小于某一特定常數(shù)，增大或減小每個(gè)維度的RSSI差異[3]，該方法在一定程度上提高了算法與實(shí)際物理環(huán)境的相似性。XueWeixing等提出了一種利用最大RSSI觀測(cè)值的平均值來(lái)改進(jìn)RSSI觀測(cè)值的算法，通過平滑度指數(shù)來(lái)評(píng)價(jià)RSSI信號(hào)的質(zhì)量，從而選擇合適的RSSI觀測(cè)值[4]。李華亮等提出了一種基于核函數(shù)特征提取的室內(nèi)定位算法，通過使用核函數(shù)特征提取方法訓(xùn)練原始位置指紋，并有效地利用各個(gè)接入節(jié)點(diǎn)的接收信號(hào)強(qiáng)度信息，減少了RSSI信號(hào)采集次數(shù)和AP個(gè)數(shù)，降低了平均定位誤差[11]。

本文在現(xiàn)有研究的基礎(chǔ)上，從離線指紋庫(kù)構(gòu)建、子區(qū)域劃分以及在線位置估計(jì)等方面提出了改進(jìn)的基于RSSI的位置指紋定位方法。

1 基于WiFi的RSSI位置指紋定位算法

基于WiFi的RSSI位置指紋定位算法主要分為兩個(gè)階段，離線階段以及在線階段[15]。

1.1 離線階段

構(gòu)建離線指紋數(shù)據(jù)庫(kù)。在待定位區(qū)域根據(jù)室內(nèi)環(huán)境分布情況，均勻的選取a個(gè)參考點(diǎn)RP，標(biāo)記為RP1、RP2、RP3、…、RPa；b個(gè)WiFi信號(hào)可接收點(diǎn)AP，標(biāo)記為AP1、AP2、AP3、…、APb[15]。 在第i個(gè)參考點(diǎn)RPi處采集到來(lái)自第j個(gè)APj的RSSI值標(biāo)記為：RSSIij=(RSSIi1,RSSIi2,…,RSSIij,…,RSSIib)， 將該參考點(diǎn)所在的區(qū)域、物理位置及其RSSI值共同構(gòu)成一個(gè)位置指紋，所有參考點(diǎn)的位置指紋構(gòu)成離線指紋數(shù)據(jù)庫(kù)見表1[15]。

表1 離線指紋庫(kù)

1.2 在線階段

在位置指紋定位研究領(lǐng)域中，關(guān)于RSSI向量匹配算法的研究成果比較豐富，諸如歐氏距離、概率分布、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)、稀疏表示等等[14]。本文采用的匹配算法為歐氏距離法。傳統(tǒng)的WKNN算法通常使用歐氏距離進(jìn)行相似度度量。在線階段，通過歐式距離(如式(1)所示)計(jì)算得出待定位點(diǎn)與離線指紋數(shù)據(jù)庫(kù)中所有參考點(diǎn)指紋的歐氏距離

(1)

然后使用KNN算法選擇指紋庫(kù)中與待定位點(diǎn)的歐氏距離最小的K個(gè)參考點(diǎn)的物理位置，利用式(2)進(jìn)行位置估計(jì)

(2)

2 基于RSSI信號(hào)特征的分區(qū)指紋定位算法

基于WiFi的RSSI位置指紋定位算法在取得較高定位精度的同時(shí)也存在一定的缺陷。首先，不同類型的AP發(fā)射功率不同，在同一位置處的RSSI值存在差異性；同時(shí)，在線定位過程中通常使用KNN算法進(jìn)行位置估計(jì)，需要對(duì)指紋庫(kù)中的所有數(shù)據(jù)進(jìn)行搜索，計(jì)算量較大，搜索效率較低；其次，在定位過程中極易使用兩個(gè)歐式距離較小而物理距離較大的點(diǎn)進(jìn)行位置估計(jì)從而增大定位誤差。為減少以上現(xiàn)象對(duì)定位精度的影響，提出基于RSSI信號(hào)衰減率(RSSIRATE-SVM)的分區(qū)聚類指紋定位算法。算法的主要流程為，首先在離線階段對(duì)待定位區(qū)域進(jìn)行子區(qū)域劃分，然后使用各參考點(diǎn)處的RSSI信號(hào)變化率構(gòu)建離線指紋數(shù)據(jù)庫(kù)；在線定位階段中，使用SVM算法對(duì)待定位點(diǎn)進(jìn)行區(qū)域劃分，再使用二級(jí)指紋定位算法進(jìn)行精確定位。

2.1 離線階段

2.1.1 子區(qū)域劃分

傳統(tǒng)的位置指紋定位算法中在線定位階段使用KNN算法進(jìn)行位置估計(jì)，需將待定位點(diǎn)處的信號(hào)指紋與指紋庫(kù)中的所有指紋進(jìn)行對(duì)比，根據(jù)其差異性進(jìn)行位置估計(jì)。由于人為對(duì)待定位區(qū)域進(jìn)行劃分時(shí)忽略了RSSI信號(hào)的分布特性，因此為了提高搜索效率，減少隨機(jī)性因素的干擾以及減少樣本搜索數(shù)量，本文依據(jù)RSSI信號(hào)分布特性提出了基于RSSI信號(hào)衰減率的子區(qū)域劃分法[15]。

(1)粗略劃分

由于RSSI信號(hào)容易受多徑傳播以及室內(nèi)環(huán)境的影響而不穩(wěn)定，通常使用對(duì)數(shù)路徑模型來(lái)描述其在室內(nèi)環(huán)境中的傳播，如式(3)所示[15]。其中RSSI(d0) 表示距離信號(hào)發(fā)射點(diǎn)d0m處(通常為1 m)的信號(hào)強(qiáng)度值；n表示路徑損耗系數(shù)，受周圍環(huán)境影響，Xσ表示無(wú)線信號(hào)發(fā)送節(jié)點(diǎn)到接收節(jié)點(diǎn)之間的遮蔽影響因子，它受室內(nèi)環(huán)境所影響，是標(biāo)準(zhǔn)差為σ的高斯分布隨機(jī)變量，d表示待定位節(jié)點(diǎn)與信號(hào)發(fā)射節(jié)點(diǎn)間的距離[15]

(3)

根據(jù)式(3)可得，RSSI信號(hào)與信號(hào)發(fā)射裝置間的距離存在一定的映射關(guān)系。研究表明，來(lái)自同一AP的RSSI均值在不同物理位置處的表現(xiàn)力不同，盡管RSSI值存在波動(dòng)，但整體趨勢(shì)是越靠近AP的位置接收到的RSSI值越強(qiáng)。我們使用RSSI信號(hào)衰減率描述RSSI信號(hào)隨距離的變化情況，根據(jù)式(3)可構(gòu)建RSSI信號(hào)衰減率模型，如式(4)所示[15]

rate(d)=-10nd0·(d·ln10)-1

(4)

圖1描述了隨著距離的變化RSSI信號(hào)的變化率情況。根據(jù)RSSI信號(hào)隨著距離變化的分布情況可以看出，隨著距離的不斷增大RSSI信號(hào)強(qiáng)度值逐漸減小，其信號(hào)變化幅度逐漸減弱；由RSSI信號(hào)變化率分布圖可以看出存在一個(gè)點(diǎn)p，p點(diǎn)處與信號(hào)發(fā)射點(diǎn)AP的距離為rm,在該點(diǎn)處RSSI信號(hào)變化率發(fā)生明顯變化，我們稱點(diǎn)p為最優(yōu)衰減率特征點(diǎn)[15]。

根據(jù)圖1可以看出，當(dāng)與AP的物理距離d≥r時(shí)，RSSI信號(hào)變化率逐漸趨于平緩，信號(hào)變化幅度不明顯，對(duì)RSSI信號(hào)空間距離度量的貢獻(xiàn)度較小。因此以最優(yōu)衰減率特征點(diǎn)p處對(duì)應(yīng)的距離r為半徑進(jìn)行區(qū)域劃分以實(shí)現(xiàn)最優(yōu)分區(qū)，使得RSSI特征較相似、RSSI信號(hào)變化明顯的參考節(jié)點(diǎn)更為集中。

圖1 RSSI信號(hào)衰減率變化

以各AP為中心，特征點(diǎn)p處對(duì)應(yīng)的距離r為半徑進(jìn)行粗略區(qū)域劃分，將室內(nèi)定位區(qū)域劃分為l個(gè)圓形分類區(qū)areal,l∈[1,n]， 如圖2所示[15]。

圖2 區(qū)域劃分

(2)精確劃分

由于粗略劃分階段，采用圓形分類區(qū)進(jìn)行子區(qū)域劃分，因此存在部分參考點(diǎn)未被劃分進(jìn)任一子區(qū)域，稱這部分參考點(diǎn)為孤點(diǎn)；精確劃分階段，采用SVM算法對(duì)孤點(diǎn)進(jìn)行精確分類[15]。

將已分類的參考節(jié)點(diǎn)作為訓(xùn)練集對(duì)SVM進(jìn)行多分類訓(xùn)練，得出最優(yōu)分類模型，訓(xùn)練樣本集為 {(xi,ci)},i∈[1,n]， 若xi屬于areal，則標(biāo)記c=1否則標(biāo)記c=0， 超平面方程為[15]

f(x)=?·φ(x)+b

(5)

(6)

2.1.2 離線指紋庫(kù)建立

傳統(tǒng)的位置指紋定位算法中使用各參考節(jié)點(diǎn)處的RSSI值建立信號(hào)指紋數(shù)據(jù)庫(kù)，然而復(fù)雜的室內(nèi)環(huán)境使得RSSI信號(hào)極易受到干擾，在線更新指紋數(shù)據(jù)庫(kù)需要耗費(fèi)大量的人力物力；同時(shí)不同型號(hào)的AP其信號(hào)穩(wěn)定程度及發(fā)射功率不同，很容易影響定位精度。因此本文提出使用各參考點(diǎn)處的RSSI信號(hào)變化率構(gòu)建離線指紋數(shù)據(jù)庫(kù)。

由式(4)可以看出，信號(hào)衰減率與環(huán)境影響因子Xσ無(wú)關(guān)，因此，使用各參考點(diǎn)處的信號(hào)衰減率構(gòu)建離線指紋數(shù)據(jù)庫(kù)可以忽略環(huán)境影響因子Xσ對(duì)定位結(jié)果的影響。

在各參考節(jié)點(diǎn)處采集來(lái)自各AP的RSSI信號(hào)值，通過式(4)計(jì)算RSSI信號(hào)衰減率。參考點(diǎn)RPm處的信號(hào)衰減率指紋為ratem=(rate1,rate2,…，raten)， 所有參考點(diǎn)處的信號(hào)衰減率及其物理位置構(gòu)成離線指紋數(shù)據(jù)庫(kù)，見表2[15]。

表2 RSSI-RATE指紋庫(kù)

2.2 定位階段

在線定位階段首先使用SVM算法確定待定位點(diǎn)所屬子區(qū)域，其次使用二級(jí)指紋定位算法對(duì)待定位點(diǎn)進(jìn)行位置估計(jì)。

2.2.1 RSSID指紋

在線定位階段引入SSD(single strength difference，SSD)的思想。即利用同一物理位置處，各分量RSSI之間的信號(hào)強(qiáng)度差構(gòu)建RSSID信號(hào)序列。

根據(jù)式(3)有

(7)

(8)

由式(7)、式(8)可得

(9)

根據(jù)式(9)可得ΔRSSI與Xσ無(wú)關(guān)。即Xσ的變化不會(huì)對(duì)同一位置處不同AP的信號(hào)強(qiáng)度差值ΔRSSI產(chǎn)生影響，可提高RSSID指紋的穩(wěn)定性。RSSID指紋構(gòu)造公式如下

RSSIDi,j=RSSIi,j-RSSIi,j+1,j∈[1,n-1]
RSSIDi=(RSSIDi1,RSSIDi2,…,RSSIDi,n-1)

(10)

2.2.2 二級(jí)指紋精確定位

在待定位點(diǎn)所屬區(qū)域中首先使用KNN算法計(jì)算出離線指紋庫(kù)中與待定位點(diǎn)的RSSI信號(hào)變化率指紋距離最小的ak個(gè)參考點(diǎn)集RPa

RPa={RPa1,RPa2,…,RPak}
RPa?RP,1≤ak

(11)

其次，使用KNN算法求出與待定位點(diǎn)的RSSID指紋距離最小的前bk個(gè)參考點(diǎn)集RPb

RPb={RPb1,RPb2,…,RPbk}
RPb?RP,1≤k≤m

(12)

根據(jù)參考點(diǎn)集RPa、RPb求出最相似參考點(diǎn)集RPsim=RPa∩RPb， 最后使用KNN算法利用最相似參考點(diǎn)集對(duì)待定位點(diǎn)進(jìn)行位置估計(jì)。

本文所提算法流程如圖3所示。

圖3 算法流程

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

為驗(yàn)證本文所提算法的有效性，使用MATLAB R2014b進(jìn)行仿真實(shí)驗(yàn)與分析。本次實(shí)驗(yàn)在一面積為11 m×7 m的實(shí)驗(yàn)場(chǎng)地進(jìn)行，在室內(nèi)布置3個(gè)信號(hào)發(fā)射裝置，物理位置分別為 (2.5,3),(6,5),(9.5,2.5)。 在房間內(nèi)部以 1 m 為間隔設(shè)置60個(gè)參考節(jié)點(diǎn)，在房間邊緣處以0.5 m為間隔設(shè)置72個(gè)參考點(diǎn)。離線階段在參考點(diǎn)處采集RSSI信號(hào)序列建立離線指紋庫(kù)，隨機(jī)生成20個(gè)待定位點(diǎn)的指紋數(shù)據(jù)作為測(cè)試數(shù)據(jù)。將本文所提算法與基于KNN算法、WKNN算法以及貝葉斯算法的定位效果進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如下所示。

3.1 r的選取

通過實(shí)驗(yàn)對(duì)子區(qū)域劃分半徑r的選取進(jìn)行了分析。實(shí)驗(yàn)測(cè)定了當(dāng)子區(qū)域劃分半徑分別為2 m、2.5 m、3 m、3.5 m、4 m以及4.5 m時(shí)，使用KNN算法對(duì)待測(cè)點(diǎn)進(jìn)行位置估計(jì)時(shí)的定位誤差，實(shí)驗(yàn)結(jié)果見表3[15]。

表3 子區(qū)域劃分半徑及定位誤差

表3從定位誤差以及計(jì)算量等方面對(duì)子區(qū)域劃分半徑的定位效果進(jìn)行了分析。根據(jù)表3可以看出，以2 m為子區(qū)域劃分半徑時(shí)平均定位誤差為3.13 m，以2.5 m為子區(qū)域劃分半徑時(shí)其平均定位誤差為1.26 m，相比劃分半徑為2 m時(shí)的定位誤差下降了約60%，數(shù)據(jù)計(jì)算量是初始計(jì)算量的1.73倍；以3 m為子區(qū)域劃分半徑時(shí)其平均定位誤差為0.88 m，相比以2.5 m為半徑進(jìn)行子區(qū)域劃分時(shí)定位誤差下降了約21%，數(shù)據(jù)計(jì)算量是初始計(jì)算量的2.5倍；以3.5 m為子區(qū)域劃分半徑時(shí)，其平均定位誤差為0.77 m，數(shù)據(jù)計(jì)算量是初始計(jì)算量的3.13倍；以4 m為半徑進(jìn)行子區(qū)域劃分時(shí)，平均定位誤差為0.75 m，數(shù)據(jù)計(jì)算量是初始計(jì)算量的4.18倍；以4.5 m為半徑進(jìn)行子區(qū)域劃分時(shí)，平均定位誤差為0.71 m，數(shù)據(jù)計(jì)算量是初始計(jì)算量的4.78倍[15]。

圖4描述了以不同半徑進(jìn)行子區(qū)域劃分時(shí)的定位誤差，可以看出當(dāng)子區(qū)域劃分半徑小于3 m時(shí)，定位誤差較大且變化較為明顯；當(dāng)子區(qū)域劃分半徑大于3 m時(shí)，定位誤差較小且變化逐漸趨于平穩(wěn)。根據(jù)實(shí)驗(yàn)結(jié)果，選擇以3 m為半徑進(jìn)行子區(qū)域劃分，可在計(jì)算量較小的情況下取得較高的定位精度[15]。

圖4 子區(qū)域劃分半徑及其誤差分布

圖5描述了以不同半徑進(jìn)行子區(qū)域劃分時(shí)的誤差累計(jì)分布圖。根據(jù)圖5可以看出子區(qū)域劃分半徑大于3 m時(shí)的定位效果明顯優(yōu)于子區(qū)域劃分半徑小于3 m時(shí)的情況[15]。

圖5 以不同半徑進(jìn)行子區(qū)域劃分的誤差累計(jì)分布

3.2 RSSIRATE-SVM算法性能驗(yàn)證

圖6為使用本文所提算法RSSIRATE-SVM與使用RSSI信號(hào)指紋結(jié)合KNN、WKNN、Bayes算法的定位誤差分布圖。根據(jù)圖6可以看出，本文所提RSSIRATE-SVM算法定位誤差與其它3種算法相比誤差較小。

圖6 RSSIRATE-SVM、KNN、WKNN、Bayes算法定位誤差分布

表4從最大誤差、最小誤差以及平均誤差等方面對(duì)RSSIRATE-SVM、KNN、WKNN、Bayes算法的定位效果進(jìn)行了對(duì)比。結(jié)合表4可得，KNN算法的平均定位誤差為1.85 m，WKNN算法的平均定位誤差為1.64 m，Bayes算法的平均定位誤差為1.37 m，RSSIRATE-SVM算法的平均定位誤差為0.91 m。由此可得，本文提出的基于RSSI信號(hào)變化率的區(qū)域劃分算法及二級(jí)指紋定位算法可以有效降低定位誤差，提高定位匹配度。

表4 RSSIRATE-SVM、KNN、WKNN、Bayes定位誤差對(duì)比

4 結(jié)束語(yǔ)

本文提出的基于RSSI信號(hào)衰減率的分區(qū)聚類室內(nèi)指紋定位算法，通過使用RSSI信號(hào)衰減率選擇最優(yōu)區(qū)域劃分半徑，降低了定位過程中出現(xiàn)兩個(gè)點(diǎn)RSSI指紋歐式距離較小而物理距離較大的情況對(duì)定位精度的影響；同時(shí)區(qū)別于傳統(tǒng)的使用RSSI信號(hào)值建立離線指紋庫(kù)的方法，提出使用不同參考點(diǎn)處的RSSI信號(hào)衰減率建立離線指紋庫(kù)，降低了定位過程中由于環(huán)境變化干擾RSSI信號(hào)而引起的誤差。下一步將對(duì)離線指紋數(shù)據(jù)庫(kù)的實(shí)時(shí)更新進(jìn)行深入研究。