基于dynFWA-SVM的WiFi室內定位算法*

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

(1.河北工業大學 計算機科學與軟件學院，天津300401；2.河北省大數據計算重點實驗室，天津 300401)

0 引 言

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

通過實驗對比證明了dynFWA在參數尋優過程中表現出更好的優越性，dynFWA-SVM定位模型的定位精度更高，穩定性更好。

1 位置指紋庫建立

1.1 高斯濾波

通過在某個參考點針對某一個接入點(access point,AP)進行180次信號采集，發現RSSI值服從高斯分布。其概率密度函數計算如下

(1)

(2)

因此，可以采用高斯濾波舍棄高斯分布模型中小概率和大干擾的數據，選取高概率數值進行均值處理，增強位置指紋的穩定性和可靠性。即選取μ-σ≤RSSI≤μ+σ區間為高概率發生區域，將此區域內的所有RSSI值取算數平均即可得到最終的位置指紋信號值

(3)

對采集數據進行高斯濾波，使其更接近真實值，如圖1。

圖1 高斯濾波處理RSSI值

1.2 SSD位置指紋

設P(d),P(d0)為與AP距離為d,d0的任意點和參考點的信號強度，由對數正態陰影模型有

(4)

(5)

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

(6)

可以看出:RSS的值與移動終端的天線增益因子GMT和AP的配置有關，且不同移動終端的天線增益GMT各不相同，因此，即便是相同環境地點，不同移動終端采集到的信號強度也各不相同。

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

(7)

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

2 基于dynFWA-SVM的無線室內定位模型

2.1 SVM在室內定位中的應用

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

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

(8)

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

(9)

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

(10)

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

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

(11)

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

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

(12)

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

(13)

與分類器相應的決策樹函數為

(14)

同樣采用非線性映射的方法得到一個關于信號強度和坐標位置的非線性關系，回歸問題與上述分類問題本質一樣，但需要在控制VC維的條件下極小化經驗風險，即等價于

(15)

求解式(15)得出的結果即為回歸的結果。綜上可得，為使目標函數取得最優值即最小值，需要對參數C和γ進行優化，從而提高定位的精度。

2.2 dynFWA尋優策略

其優化過程具體包括以下幾個步驟：

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

2)通過適應度函數計算每個煙花個體的適應度值f(xi),i=0,1,…,n，并由爆炸算子計算產生火花。其中核心煙花的爆炸半徑ACF由優化過程的局部信息確定，非核心煙花的爆炸半徑由Ai確定；爆炸火花數目由Si確定

(16)

(17)

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

3)采用模運算映射規則將越界火花映射到可行域內

(18)

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

(19)

5)若達到迭代次數，輸出最優煙花的適應度值和與其對應的SVM參數(C,γ);否則,執行步驟(2)。

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

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

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

1)離線階段采集WiFi信號獲取RSSI值，對信號進行高斯濾波去除奇異值操作，并計算每個信號采集點的SSD值作為訓練樣本，通過dynFWA對SVM的目標函數進行優化求得最優解，并得到與之對應的最優參數組合 ，從而建立分類回歸定位模型；

2)在線階段用戶隨機選取位置坐標采集RSSI值并計算出其對應的SSD值，將采集的數據樣本通過離線階段訓練得出的定位模型計算出采集點位置坐標，并與真實的位置坐標進行誤差計算，得出定位精度。

3 實驗結果及分析

3.1 實驗場景

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

圖3 實驗場景

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

f(x)=1-g(x)

(20)

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

3.2 實驗結果分析

3.2.1 位置指紋庫

選用聯想G460和戴爾INS15PD-2648B兩臺計算機采集RSS，選定相同環境的20個參考點采集信號，每個點采集一次。如圖4、圖5所示。

圖4 兩臺計算機采集RSS指紋示意

圖5 兩臺計算機采集SSD指紋示意

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

3.2.2 dynFWA算法對SVM參數尋優

對SVM參數進行尋優時，分別采用當前優化效果較好的PSO算法、煙花算法(fireworks algorithm,FWA)算法[11]與本文采用的dynFWA算法對比，參數優化過程如圖6。

圖6 3種優化算法迭代尋優過程

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

表1 3種優化算法得出的最優參數值

3.2.3 定位精度對比

離線階段采用聯想G460筆記本采集信號，在線測試階段采用戴爾INS15PD-2648B筆記本采集信號。采用PSO-FWA定位模型、FWA-SVM定位模型和本文提出的dynFWA-SVM定位模型對比，隨機在每個子區域各采集106個點共530個測試點進行定位測試，其定位結果概率分布如圖7、圖8所示。

圖7 基于RSS位置指紋的定位結果

圖8 基于SSD位置指紋的定位結果

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

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

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

表4 3種定位模型平均定位誤差對 m

4 結 論

提出了基于dynFWA-SVM的WiFi室內定位算法，并通過高斯濾波對信號進行處理，采用SSD指紋替代傳統的RSS指紋，通過對比實驗可知：相較于傳統的RSS指紋經高

斯濾波處理過后的SSD指紋具有更高的穩定性；dynFWA算法相對于PSO算法和FWA算法對SVM的參數尋優效率更高，具有更好的優越性；基于dynFWA-SVM的WiFi室內定位模型的定位精度較PSO-SVM模型和FWA-SVM模型更高，誤差更小。

參考文獻:

[1] 王建平,李程程,李奇越,等.基于WiFi的動態室內定位方法研究[J].傳感器與微系統,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] 唐 瑞,孫冰潔,周禮爭,等.基于RSSI的KNN-PIT室內自適應定位算法[J].傳感器與微系統,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] 李軍懷,賈金朋,王懷軍,等.基于信號強度差的RFID室內定位研究[J].計算機科學,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.