基于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.