基于IMK-WLSSVR的WiFi室内定位算法*

2019-12-24关维国

传感器与微系统 2019年12期

张震，关维国，邹颖

(辽宁工业大学电子与信息工程学院，辽宁锦州121001)

0 引言

随着移动通信技术的快速发展，基于位置的室内定位服务越来越受到人们的关注[1]。无线保真(wireless fidelity，WiFi)信号覆盖范围广且WiFi通信模块广泛应用在智能终端上，使得基于WiFi的定位技术备受关注。WiFi定位方法主要包括几何测距法和指纹识别法[2]。几何测距法利用信号传播模型进行位置估计，但信号模型受环境影响比较大，定位精度较低。位置指纹法通过创建信号强度与位置坐标的指纹库进行定位，定位精度更高且易于部署，成为了研究的热门方向[3]。

位置指纹法在离线阶段建立接收信号强度指示(received signal strength indication，RSSI)与位置的数据库，对在线测量的RSSI和数据库进行匹配，从而完成定位。文献[4]提出基于RSSI概率分布重叠面积的指纹相似度匹配算法实现定位，但需要建立准确的RSSI概率分布模型。文献[5]采用K-means聚类算法对指纹数据初始分类，使用随机森林算法进行二次分类，但算法计算量比较大。文献[6]提出了基于最小二乘支持向量机(least square support vector machine，LSSVM)的定位方法，LSSVM由于其泛化性能强，算法定位效果较好，但没有研究模型参数优化方法。文献[7]采用最小二乘支持向量回归机完成三维定位，通过粒子群算法对定位模型参数进行优化，具有不错的定位效果,但粒子群算法全局寻优能力差，模型优化效果不明显。

本文提出一种基于改进多核加权最小二乘向量回归(improved multiple kernel weighted least square support vector regression，IMK-WLSSVR)的WiFi室内定位算法。针对传统基于单核WLSSVR模型的定位效果不佳，选用多项式核函数和高斯径向基核函数通过线性加权确定多核函数，依据模型拟合误差为每个指纹样本分配不同的权值，建立RSSI值与位置坐标的非线性映射；采用改进的模拟退火(improved simulated annealing，ISA)算法进一步优化模型参数，通过优化的定位模型进行定位，有效提高算法的定位精度。

1 IMK-WLSSVR算法

本文提出的基于IMK-WLSSVR的定位方法主要分为离线训练阶段和在线定位阶段。离线训练阶段，在定位环境中选定指纹点，然后采集各个指纹点上的RSSI值，将指纹点RSSI样本值和对应位置作为输入样本对，采用多项式核函数和高斯径向基核函数构建多核函数，利用正态分布权值函数计算每个指纹点的权值，建立IMK-WLSSVR定位模型，并采用ISA算法确定IMK-WLSSVR参数，构造RSSI值和位置坐标的非线性映射。在线定位阶段，在待定位点采集RSSI值，通过构造好的IMK-WLSSVR模型估算待定位点的实际位置。

1.1 多核函数构建

核函数可以解决非线性关系，但在室内环境中，RSSI受到多径、阴影效应的影响，单核方法往往不能很好拟合RSSI，因此，为了提高定位精度，采用多核方法建立定位模型。为了更好拟合RSSI值与位置的非线性映射，本文选用全局性核函数即三阶多项式核结合局部性核函数即高斯核,通过线性加权构建多核函数[8]

K=λ1Kpoly+λ2KRBF,

s.t.λ1+λ2=1

(1)

(2)

式中y(i)为第i个坐标y的真实值，y′(i)为相应的模型估计值,则每个基核函数的权重λm为

(3)

同理可得到坐标x的多核函数。

1.2 IMK-WLSSVR建模

定位问题的关键就是获取RSSI值与位置坐标之间的映射关系，可以采用人工神经网络和最小二乘支持回归机拟合位置和信号强度的非线性映射[9]。本文利用基于多核的WLSSVR算法构造RSSI值与位置坐标的非线性关系，有效提高模型的定位精度。

支持向量回归[10](support vector regression ，SVR)具有良好的非线性性能，但其训练过程涉及二次规划问题，导致训练时计算复杂。作为SVR的扩展，最小二乘支持向量回归(least square support vector regression，LSSVR)算法[11]利用最小二乘方法将二次规划问题等价为线性方程组求解, 有效提高了SVR运算速度，但算法鲁棒性能欠佳。Suykens J A K等人在LSSVR算法的基础上提出加权最小二乘支持向量回归(weighted least square support vector regression，WLSSVR)算法[12]，从而有效提高了LSSVR算法鲁棒性能。

假设Pi=(pi1,pi2,…piM) 表示指纹点(xi,yi)处接收到来自M个WiFi热点的RSSI向量，通过一个非线性映射φ，将RSS值映射到高维特征空间F，在高维空间中构造物理位置y与RSSI向量的最优回归关系

(4)

式中Wk∈H为权系数，λk≥0为第k个核函数的系数，b为偏置矩阵。根据结构风险化最小原则，将二次规划问题转化为

(5)

建立式(5)对应的拉格朗日函数

(6)

分别求取式(6)关于各变量的偏微分

(7)

式(7)消去向量Wk,β和η，可得式(8)

(8)

(9)

解式(9)可得

α=(Ω+γ-1ω)-1(Y-b·E)

(10)

由式(10)可求出最优回归函数

(11)

坐标x求解过程与上述方法类似，根据式(1)和式(11)，可得指纹点的RSSI向量与物理位置的非线性关系

(12)

在IMK-WLSSVR定位模型中，不同的定位误差ηi对应不同的权重ωi，选取恰当的权重可以有效降低异常指纹数据对模型定位精度的影响，本文采用基于正态分布的加权函数表达式为：

|ηi|<0.2μ或|ηi|>0.8μ

(13)

1.3 多核模型参数优化

IMK-WLSSVR算法的定位性能与支持向量回归机参数(惩罚因子γ、核参数σ、C)的选择有着极为紧密的联系。文献[13]提出了基于网格搜索的SVR优化方法，但网格方法搜索模型参数的精度较低，优化性能不理想。为了提高IMK-WLSSVR定位模型的定位性能，本文改进模拟退火算法来优化模型参数。模拟退火算法[14,15]作为一种全局搜索算法，以一定的几率接受差解，扩大了算法搜索范围，避免寻优过程陷于局部最优，提高了算法得到全局最优解的概率。

本文将当前温度值加入到扰动模型中，在接近最优解时能减缓扰动幅度；同时，增加一个最优参数变量，从而保证在退火过程中始终保持最优解。基于改进模拟退火算法的IMK-WLSSVR定位模型参数优化过程如下：

1)设定待优化参数γ,δ,C范围，温度T1和扰动步长V0，随机生成γ,δ,C并作为当前优解γbest,δbest,Cbest。依据式(12)得到当前参数下的IMK-WLSSVR模型，计算位置预测值与真实值的均方根误差S。

2)在温度Tm下，根据式(14)扰动模型计算新参数γ1，δ1，C1，计算新参数下的位置坐标均方根误差S′,选择其中误差最小的参数作为γbest,δbest,Cbest，然后与上一次的误差S比较，若S′小，则接受新参数；若S大，则计算ΔS=S′-S，并生成一个(0,1)范围的随机值ρ，若exp(-ΔS/Tk)大于ρ，接受新参数，否则抛弃新参数，并对上一次参数重新扰动

(14)

式中θ为(0,1)范围内的随机数。

3)若到达规定迭代次数，则更新温度Tm+1=Tm·α，迭代次数清零并跳至步骤(2)，否则直接跳转至步骤(2)。若Tk小于最低温度，算法终止，输出待优化参数的最优值组合(γbest,δbest,Cbest)。

2 实验结果及分析

2.1 实验条件

室内定位环境选取学校3号教学楼8层实验实训室，如图1所示。实验选用6个型号为TL-WR886N的WiFiAP，AP固定高度为2 m,使用华为手机采集各WiFiAP的RSSI值，手机与地面相隔1.2 m。实验布置了60个指纹点和60个测试点，指纹点的间距是3 m,每个指纹点位置采集50个样本，每次间隔5 s，测试点位置随机选取，每个位置采集10次。实验选择60组指纹数据作为训练样本建立IMK-WLSSVR定位模型，利用训练好的模型对60组测试数据进行定位测试，实验对比了WKNN，LSSVR及MK-WLSSVR算法。

图1 室内定位测试

2.2 实验结果分析

为了验证本文的IMK-WLSSVR算法的有效性，分别采用WKNN、LSSVR、MK-WLSSVR和IMK-WLSSVR4种方法进行定位对比。其中，WKNN的近邻数为4，LSSVR算法的核函数选取径向基函数。构建等价核函数，利用式(3)计算每个基核函数的权重λ1=0.46，λ2=0.54，由式(13)确定各个指纹点的权值，建立LSSVR模型、MK-WLSSVR模型及IMK-WLSSVR模型， 3种模型的定位误差如图2所示。

图2 不同模型定位误差对比

从图2可知，组合核函数MK-WLSSVR的总体预测性能较好，其预测误差小于单一核函数LSSVR模型。IMK-WLSSVR模型具备较好的抗干扰性和较高的定位精度，通过调整模型误差的权重，进一步减小了位置估计误差，其定位误差小于MK-WLSSVR的定位误差，表明IMK-WLSSVR模型精度更高、泛化能力更强。根据图2的模型定位误差计算得到均方根误差，IMK-WLSSVR的均方根误差为1.54 m，优于LSSVR的1.86 m、MK-WLSSVR的1.68 m，可见本文算法的定位误差受影响较小，抗噪性能良好。

同时，为了验证ISA算法对IMK-WLSSVR参数寻优的有效性，分别使用网格搜索以及改进的模拟退火算法方法优化模型参数，利用IMK-WLSSVR模型来估计测试点位置。

图3所示的是使用ISA优化算法平均定位误差的对比，改进模拟退火算法的误差相比网格搜索定位误差明显减小，说明了ISA算法对IMK-WLSSVR模型的参数优化可以有效减少定位误差。对于通过IMK-WLSSVR构建RSSI值和物理位置的映射关系的过程中，ISA算法有着良好的全局优化IMK-WLSSVR算法参数的能力，使得IMK-WLSSVR有着更好的学习能力和泛化能力。