基于dynFWA-SVM的WiFi室內(nèi)定位算法*

沈西挺， 白振東， 董 瑤， 董永峰

(1.河北工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津300401；2.河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室，天津 300401)

0 引 言

基于WiFi信號(hào)的定位算法中通常采用位置指紋定位算法[1～3]，但由于室內(nèi)環(huán)境復(fù)雜，WiFi指紋定位的精度較低，且穩(wěn)定性較差，因此,Brunato M等人[4]提出了將支持向量機(jī)(support vector machine,SVM)應(yīng)用于位置指紋定位中，定位精度得到了極大的提高。但隨著定位面積的不斷加大，SVM的懲罰參數(shù)與核參數(shù)的選擇直接影響了定位效率和精度。而目前對(duì)SVM參數(shù)的優(yōu)化表現(xiàn)較好的粒子群優(yōu)化(particle swarm optimization,PSO)算法在優(yōu)化過(guò)程中時(shí)間復(fù)雜度較高、效率偏低[5,6]。因此，本文提出了動(dòng)態(tài)搜索煙花算法[7](dynamic search fireworks algorithm，dynFWA)優(yōu)化SVM參數(shù)，建立dynFWA-SVM的定位模型以提高優(yōu)化效率和定位精度。同時(shí)，由于無(wú)線信號(hào)在傳播過(guò)程中易受到噪聲、多徑傳播和非視距傳播等因素的影響[8]，采集的接收信號(hào)強(qiáng)度指示(received signal strength indication,RSSI)值與真實(shí)值之間必然存在較大誤差；并且研究發(fā)現(xiàn)當(dāng)使用不同移動(dòng)終端即使在相同的環(huán)境同一位置上采集的信號(hào)強(qiáng)度也會(huì)表現(xiàn)出明顯差異[9]，因此，本文采用高斯濾波[10]對(duì)采集到的信號(hào)進(jìn)行濾波處理從而增強(qiáng)信號(hào)的穩(wěn)定性，并引入信號(hào)強(qiáng)度差(signal strength difference,SSD)替代傳統(tǒng)的接收信號(hào)強(qiáng)度(received signal strength,RSS)指紋作為位置指紋庫(kù)，以減小不同硬件設(shè)備對(duì)定位結(jié)果造成的影響。

通過(guò)實(shí)驗(yàn)對(duì)比證明了dynFWA在參數(shù)尋優(yōu)過(guò)程中表現(xiàn)出更好的優(yōu)越性，dynFWA-SVM定位模型的定位精度更高，穩(wěn)定性更好。

1 位置指紋庫(kù)建立

1.1 高斯濾波

通過(guò)在某個(gè)參考點(diǎn)針對(duì)某一個(gè)接入點(diǎn)(access point,AP)進(jìn)行180次信號(hào)采集，發(fā)現(xiàn)RSSI值服從高斯分布。其概率密度函數(shù)計(jì)算如下

(1)

(2)

因此，可以采用高斯濾波舍棄高斯分布模型中小概率和大干擾的數(shù)據(jù)，選取高概率數(shù)值進(jìn)行均值處理，增強(qiáng)位置指紋的穩(wěn)定性和可靠性。即選取μ-σ≤RSSI≤μ+σ區(qū)間為高概率發(fā)生區(qū)域，將此區(qū)域內(nèi)的所有RSSI值取算數(shù)平均即可得到最終的位置指紋信號(hào)值

(3)

對(duì)采集數(shù)據(jù)進(jìn)行高斯濾波，使其更接近真實(shí)值，如圖1。

圖1 高斯濾波處理RSSI值

1.2 SSD位置指紋

設(shè)P(d),P(d0)為與AP距離為d,d0的任意點(diǎn)和參考點(diǎn)的信號(hào)強(qiáng)度，由對(duì)數(shù)正態(tài)陰影模型有

(4)

(5)

式中GMT為移動(dòng)終端的天線增益；PAP為AP的發(fā)射功率;GAP為AP的天線增益;λAP為AP的波長(zhǎng);L為系統(tǒng)損耗因子。將式(5)代入(4)可得P(d)點(diǎn)的RSS表達(dá)式，即

(6)

可以看出:RSS的值與移動(dòng)終端的天線增益因子GMT和AP的配置有關(guān)，且不同移動(dòng)終端的天線增益GMT各不相同，因此，即便是相同環(huán)境地點(diǎn)，不同移動(dòng)終端采集到的信號(hào)強(qiáng)度也各不相同。

為消除移動(dòng)終端天線增益GMT因子對(duì)定位精度的影響，假設(shè)P(d1)和P(d2)分別表示同一移動(dòng)終端在同一位置i處接收到的與其距離為d1的AP1的信號(hào)強(qiáng)度和距離為d2的AP2的信號(hào)強(qiáng)度，將P(d1)與P(d2)相減可得i點(diǎn)的信號(hào)強(qiáng)度差SSDi值

(7)

因此，由式(7)得出的信號(hào)強(qiáng)度差SSD指紋可以有效緩解不同硬件引起的差異。

2 基于dynFWA-SVM的無(wú)線室內(nèi)定位模型

2.1 SVM在室內(nèi)定位中的應(yīng)用

通過(guò)非線性映射函數(shù)φ(x)將樣本數(shù)據(jù){(xi,di),i=1,2,…,n}映射到高維空間得到超平面對(duì)樣本線性分類

f(x)=w·φ(xi)+b

(8)

式中xi∈Rd為輸入向量，di∈R為輸出量；w為權(quán)重；b為闕值。為使分類超平面最優(yōu)，需求解約束的最優(yōu)化問(wèn)題

(9)

s.t.yi(w·φ(xi)+b)≥1,i=1,2,…,n

(10)

式(9)為優(yōu)化目標(biāo)函數(shù)，式(10)為約束函數(shù)。極小化式(9)可求得將樣本分開的最優(yōu)超平面。引入松弛變量ξ=(ξ1,ξ2,…,ξn)及懲罰參數(shù)C將目標(biāo)函數(shù)轉(zhuǎn)化為

b)≥1-ξi,i=1,2,…，n

(11)

從而求得對(duì)于不可分情況的軟間隔分類。選用徑向基核函數(shù)(radial basis function,RBF)作為映射函數(shù)

k(x,xi)=exp(-γ|x-xi|2)

(12)

式中γ為核參數(shù)，則此分類超平面可表示為

(13)

與分類器相應(yīng)的決策樹函數(shù)為

(14)

同樣采用非線性映射的方法得到一個(gè)關(guān)于信號(hào)強(qiáng)度和坐標(biāo)位置的非線性關(guān)系，回歸問(wèn)題與上述分類問(wèn)題本質(zhì)一樣，但需要在控制VC維的條件下極小化經(jīng)驗(yàn)風(fēng)險(xiǎn)，即等價(jià)于

(15)

求解式(15)得出的結(jié)果即為回歸的結(jié)果。綜上可得，為使目標(biāo)函數(shù)取得最優(yōu)值即最小值，需要對(duì)參數(shù)C和γ進(jìn)行優(yōu)化，從而提高定位的精度。

2.2 dynFWA尋優(yōu)策略

其優(yōu)化過(guò)程具體包括以下幾個(gè)步驟：

1)可行域范圍內(nèi)初始化煙花種群及其最大迭代次數(shù)，同時(shí)設(shè)定SVM參數(shù)C范圍和γ的取值范圍，每一個(gè)煙花代表一組參數(shù)(C,γ)。

2)通過(guò)適應(yīng)度函數(shù)計(jì)算每個(gè)煙花個(gè)體的適應(yīng)度值f(xi),i=0,1,…,n，并由爆炸算子計(jì)算產(chǎn)生火花。其中核心煙花的爆炸半徑ACF由優(yōu)化過(guò)程的局部信息確定，非核心煙花的爆炸半徑由Ai確定；爆炸火花數(shù)目由Si確定

(16)

(17)

式中m為常數(shù)；Ymax=maxf(xi)為當(dāng)前種群中適應(yīng)度最大值;Ymin=minf(xi)為當(dāng)前種群中適應(yīng)度最小值;為最大的爆炸幅度;ε為一極小常數(shù)。

3)采用模運(yùn)算映射規(guī)則將越界火花映射到可行域內(nèi)

(18)

4)選出適應(yīng)度值最小火花作為下一代核心煙花，并更新其爆炸半徑ACF，其余N個(gè)煙花采用輪盤賭博方式選取作為下一代煙花，xi被選取的概率公式如下

(19)

5)若達(dá)到迭代次數(shù)，輸出最優(yōu)煙花的適應(yīng)度值和與其對(duì)應(yīng)的SVM參數(shù)(C,γ);否則,執(zhí)行步驟(2)。

2.3 dynFWA-SVM分類回歸定位模型

dynFWA-SVM的分類回歸定位模型如圖2所示。

圖2 dynFWA-SVM分類回歸定位模型

1)離線階段采集WiFi信號(hào)獲取RSSI值，對(duì)信號(hào)進(jìn)行高斯濾波去除奇異值操作，并計(jì)算每個(gè)信號(hào)采集點(diǎn)的SSD值作為訓(xùn)練樣本，通過(guò)dynFWA對(duì)SVM的目標(biāo)函數(shù)進(jìn)行優(yōu)化求得最優(yōu)解，并得到與之對(duì)應(yīng)的最優(yōu)參數(shù)組合 ，從而建立分類回歸定位模型；

2)在線階段用戶隨機(jī)選取位置坐標(biāo)采集RSSI值并計(jì)算出其對(duì)應(yīng)的SSD值，將采集的數(shù)據(jù)樣本通過(guò)離線階段訓(xùn)練得出的定位模型計(jì)算出采集點(diǎn)位置坐標(biāo)，并與真實(shí)的位置坐標(biāo)進(jìn)行誤差計(jì)算，得出定位精度。

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

3.1 實(shí)驗(yàn)場(chǎng)景

選取4間實(shí)驗(yàn)室和走廊部分22 m×18 m的矩形區(qū)域，以及6個(gè)位置未知的AP熱點(diǎn)，將區(qū)域網(wǎng)格化為1 m×1 m大小且劃分為5個(gè)子區(qū)域，則共有437個(gè)參考點(diǎn)，如圖3所示。設(shè)參考點(diǎn)采集的樣本表示為(dk,(i,yi),γi),其中dk(k=1,2,…,5)為子區(qū)域標(biāo)志，γi=(RSSI1,RSSI2,…,RSSI6)為參考點(diǎn)的信號(hào)強(qiáng)度。

圖3 實(shí)驗(yàn)場(chǎng)景

訓(xùn)練定位模型時(shí)，使用計(jì)算機(jī)端的WiFi信號(hào)采集器對(duì)每個(gè)參考點(diǎn)采集12次數(shù)據(jù)，每秒1次，共采集到5 244條數(shù)據(jù)作為訓(xùn)練樣本。dynFWA參數(shù)設(shè)定為：種群初始大小為5，最大火花數(shù)目為120，最小火花數(shù)目為6，放大系數(shù)為1.2，縮小系數(shù)為0.9，迭代次數(shù)為1 000，函數(shù)評(píng)估最大值為5 000，為在開始階段保持高探索能力，將ACF初始化為搜索空間的大小，選用如下函數(shù)作為適應(yīng)度函數(shù)

f(x)=1-g(x)

(20)

式中g(shù)(x)為SVM的分類回歸準(zhǔn)確率。SVM的懲罰參數(shù)C∈[1,100]，核參數(shù)γ∈[0,20]。

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

3.2.1 位置指紋庫(kù)

選用聯(lián)想G460和戴爾INS15PD-2648B兩臺(tái)計(jì)算機(jī)采集RSS，選定相同環(huán)境的20個(gè)參考點(diǎn)采集信號(hào)，每個(gè)點(diǎn)采集一次。如圖4、圖5所示。

圖4 兩臺(tái)計(jì)算機(jī)采集RSS指紋示意

圖5 兩臺(tái)計(jì)算機(jī)采集SSD指紋示意

由圖4、圖5可知，兩臺(tái)計(jì)算機(jī)的RSS的均值差為9.6 dB，SSD的均值差為1.58 dB，2臺(tái)不同計(jì)算機(jī)SSD的差異相比于RSS減小了83.1 %。由此可知，SSD的一致性好于RSS，在不同硬件上的差異性表現(xiàn)更好。

3.2.2 dynFWA算法對(duì)SVM參數(shù)尋優(yōu)

對(duì)SVM參數(shù)進(jìn)行尋優(yōu)時(shí)，分別采用當(dāng)前優(yōu)化效果較好的PSO算法、煙花算法(fireworks algorithm,FWA)算法[11]與本文采用的dynFWA算法對(duì)比，參數(shù)優(yōu)化過(guò)程如圖6。

圖6 3種優(yōu)化算法迭代尋優(yōu)過(guò)程

可知:PSO及FWA算法分別在迭代45次和25次后逐漸達(dá)到平穩(wěn)最優(yōu)狀態(tài)，而dynFWA在迭代17次后即尋得最優(yōu)參數(shù)，較前兩者在收斂速度上分別提高了62.2 %和32 %，且dynFWA算法的適應(yīng)度值最佳，其值為0.069，PSO的適應(yīng)度值最差，其值為0.093。3種優(yōu)化算法優(yōu)化得出的最優(yōu)參數(shù)組合如表1所示。

表1 3種優(yōu)化算法得出的最優(yōu)參數(shù)值

3.2.3 定位精度對(duì)比

離線階段采用聯(lián)想G460筆記本采集信號(hào)，在線測(cè)試階段采用戴爾INS15PD-2648B筆記本采集信號(hào)。采用PSO-FWA定位模型、FWA-SVM定位模型和本文提出的dynFWA-SVM定位模型對(duì)比，隨機(jī)在每個(gè)子區(qū)域各采集106個(gè)點(diǎn)共530個(gè)測(cè)試點(diǎn)進(jìn)行定位測(cè)試，其定位結(jié)果概率分布如圖7、圖8所示。

圖7 基于RSS位置指紋的定位結(jié)果

圖8 基于SSD位置指紋的定位結(jié)果

3種定位模型在各個(gè)區(qū)間的概率分布對(duì)比及其定位精度對(duì)比如表2～表4所示，本文提出的定位模型在基于RSS指紋庫(kù)時(shí)，平均定位誤差為1.79 m，較其他2種定位模型的平均定位誤差分別低0.37 m和0.15 m；基于SSD指紋庫(kù)時(shí)，平均定位誤差為1.63 m，較其他2種定位模型的平均定位誤差分別低了0.27 m和0.14 m。當(dāng)3種定位模型基于不同的位置指紋時(shí)，基于SSD位置指紋的定位精度較基于RSS位置指紋的定位精度分別高0.26，0.17，0.16 m。

表2 基于RSS位置指紋的概率分布

表3 基于SSD位置指紋的概率分布

表4 3種定位模型平均定位誤差對(duì) m

4 結(jié) 論

提出了基于dynFWA-SVM的WiFi室內(nèi)定位算法，并通過(guò)高斯濾波對(duì)信號(hào)進(jìn)行處理，采用SSD指紋替代傳統(tǒng)的RSS指紋，通過(guò)對(duì)比實(shí)驗(yàn)可知：相較于傳統(tǒng)的RSS指紋經(jīng)高

斯濾波處理過(guò)后的SSD指紋具有更高的穩(wěn)定性；dynFWA算法相對(duì)于PSO算法和FWA算法對(duì)SVM的參數(shù)尋優(yōu)效率更高，具有更好的優(yōu)越性；基于dynFWA-SVM的WiFi室內(nèi)定位模型的定位精度較PSO-SVM模型和FWA-SVM模型更高，誤差更小。

參考文獻(xiàn):

[1] 王建平,李程程,李奇越,等.基于WiFi的動(dòng)態(tài)室內(nèi)定位方法研究[J].傳感器與微系統(tǒng),2017,36(2):49-52.

[2] Feng C,Au W S A,Valaee S,et al.Received-signal-strength-based indoor positioning using compressive sensing[J].IEEE Transactions on Mobile Computing,2012,11(12):1983-1993.

[3] 唐 瑞,孫冰潔,周禮爭(zhēng),等.基于RSSI的KNN-PIT室內(nèi)自適應(yīng)定位算法[J].傳感器與微系統(tǒng),2015,34(7):128-131.

[4] Brunato M,Battiti R.Statistical learning theory for location fingerprinting in wireless LANs[J].Computer Networks,2005,47(6):825-845.

[5] Subasi A.Classification of EMG signals using PSO optimized SVM for diagnosis of neuromuscular disorders[J].Computers in Biology & Medicine,2013,43(5):576-586.

[6] Lei N,Jiang J,Yong P.Leak location of pipelines based on tran-sient model and PSO-SVM[J].Journal of Loss Prevention in the Process Industries,2013,26(6):1085-1093.

[7] Zheng S,Janecek A,Li J,et al.Dynamic search in fireworks algorithm[C]∥IEEE Evolutionary Computation Conference，2014:3222-3229.

[8] Ma R,Guo Q,Hu C,et al.An improved WiFi indoor positioning algorithm by weighted fusion[J].Sensors,2015,15(9):21824-21843.

[9] 李軍懷,賈金朋,王懷軍,等.基于信號(hào)強(qiáng)度差的RFID室內(nèi)定位研究[J].計(jì)算機(jī)科學(xué),2015,42(11):154-157.

[10] Wang C,Wu F,Shi Z,et al.Indoor positioning technique by combining RFID and particle swarm optimization-based back propagation neural network[J].Optik—International Journal for Light and Electron Optics,2016,127(17):6839 -6849.

[11] Tan Y,Zhu Y.Fireworks algorithm for optimization[C]∥International Conference on Advances in Swarm Intelligence,Springer-Verlag,2010:355-364.