基于SALDE-UKF-SVM算法的WLAN室内定位方法

徐晓苏，吴晓飞，张 涛，闫琳宇

（1. 东南大学 仪器科学与工程学院，南京 210096；2. 东南大学 微惯性仪表与先进导航技术教育部重点实验室，南京 210096）

在室内定位技术中，WLAN室内定位系统因其完全基于现有的无线局域网设施，不需要引入其他昂贵的专用硬件设备，定位精度较高，成本低的优点而被国内外研究学者所关注[1-2]。

WLAN室内定位技术根据其测量原理可分为近似检测、几何测量和位置指纹分析。其中，基于接收信号强度指示（RSSI）的指纹识别定位方法具有对复杂环境适应性强的优点，是目前国内外的主要研究方向。

这种算法的本质是构建RSS信号与物理位置的非线性映射关系[3]。文献[4]和文献[5]分别提出了利用支持向量机（SVM）和人工神经网络（ANN）的方法对RSS信号进行识别，这些方法都忽视了RSS数据高维时变的特性，将会导致运算时间长且拟合的映射关系不适用。针对这一问题，文献[6][7]分别提出了利用特征提取算法[8-11]对RSS数据集进行预处理，减小数据维数和时变的影响，取得了一定的效果。但这些特征提取算法均是无监督的，对RSS样本数据集的类别标签不能充分利用起来，导致算法效果受到一定程度的影响。

针对上述问题，本文提出了一种具有监督能力的自适应局部线性判别嵌入算法（SALDE），并结合无迹卡尔曼滤波算法（UKF）将之前的定位结果融入到位置指纹的匹配过程中，在提高定位结果精度的同时增加系统的稳定性。

1 基于SALDE-UKF-SVM的室内定位算

本文设计的室内定位系统分为离线学习和在线定位两个阶段，如图1所示。

离线阶段，依据室内布局特征进行区域分类，然后在各类中采集适量接入点（AP）的RSS信号，构成训练样本数据，利用SALDE算法对样本数据进行降维，并增大类别间判别信息，最后对预处理后的数据进行SVM训练，建立物理坐标与特征映射关系函数。

在线定位阶段，采集用户所在位置的RSS信号集，利用建立的非线性映射预测位置坐标，并通过 UKF滤波器进行滤波处理，得到最终坐标。

图1 室内定位系统示意图Fig.1 Indoor positioning system diagram

2 有监督自适应局部线性判别算法

2.1 局部线性判别算法（LLDE）

步骤1 利用k-NN或ε-ball标准构造近邻域：

k-NN标准是以欧氏距离作为测度，寻找离样本点距离最小的k个点作为其近邻点，构造邻域。

ε- b all标准是将任何一个落在以样本点为球心，ε为半径的球内的点都可以看作近邻点。

步骤 2 计算样本点与其近邻点的最小重构权矩阵ijW ，通过极小化如下目标函数来进行计算：

其中：iε为样本点iX的线性重构误差，且ij≠；jsG是kk×维局部协方差矩阵，即

从式(2)可以看出，协方差矩阵是一个正定矩阵，若计算时出现非正定情况，可以按照下式对其进行变换使其正定：

其中：r为正则化参数，tr()G 为协方差矩阵的迹。

求式(1)的极小值，需要满足以下两个约束条件：

条件式(4)严格约束线性重构权值和为1，则得到如下约束目标函数：

式(5)是一个最小值优化问题，可采用拉格朗日乘数法求解，可得到最优权值矩阵如下：

步骤3 根据步骤2得到的重构权值矩阵W ，构建代价矩阵M和矩阵 X MXT：

根据最优权值矩阵W 计算保持样本局部几何结构的低维嵌入流形Y，可通过计算最小代价来获取，表达式如下：

式(7)等价为 ε ( Y ) = m in t r[Y(I - W )T( I -W)YT]。令代价矩阵 M = ( I -W )T(I -W )，引入线性变换 Y =ATX，则式(7)可以写成： J ( A) = mintr{ ATXMXTA}。

步骤 4 计算类间散度 SB与类内散度 SW的加权差矩阵SB-μSW：

根据最大边缘标准(MMC)及最优权值矩阵缩放不变的特性，需要计算 SB-μSW，计算方法如下：

其中：c为类别总数； pi为第i类输入点的先验概率分布密度；mi为第i类的输入点的均值；m为总均值；Si为第i类的类间散度；μ≥0为缩放因子。

步骤 5 对 { [X MXT- ( SB-μSW)],XXT}进行广义特征值分解，求其d个最小特征值，最小特征值对应的特征向量组成的矩阵V为所求的变换矩阵，即Y=VTX。

2.2 本文自适应LLDE算法

基于监督学习的思想，提出有监督自适应局部线性判别算法(SALDE)，采用距离因子突出不同类别间的距离，实时调整样本点邻域图。这在一定程度上能够加大不同类别间的差异，从而得到更好的分类效果。

本文采取的监督自适应措施是对LLDE算法中步骤一近邻域的构造方法进行调整，距离调整修正公式如下：

其中： dij为两个样本点的欧氏距离，两样本点属于同一类； δ ( Xi, Xj)取0，否则取1。

此距离计算公式将两类之间的距离引入，采用Sigmoid函数作为距离引入量的判别标准，能有效保持样本点间距适中，不会导致类别之间交叉严重的现象。

3 基于UKF的SVM定位算法

3.1 SVM多分类模型

SVM 是建立在统计学理论的 VC维理论和结构风险最小原理的基础上[13]。相比于以降低经验风险为目标的机器学习方法，SVM具有更强的泛化能力。

设样本数据集为(x,y ) , i = 1,2,… ,N ， x ∈Rd，

i i y∈{-1, +1}是样本数据的所属类别标号。在线性可分的情况下，SVM寻找一个最优的分类超平面，使几何间隔达到最大，超平面如式(9)所示：

其中：ω表示权向量，b表示偏置向量，x表示输入向量。为了寻找分类超平面，可以通过求解下式目标函数获得：

式(10)是一个具有约束条件的二次函数优化问题，可以通过拉格朗日对偶法求解，化简得下式：

其中，α为拉格朗日乘子。

将式(11)中的α固定，分别对ω和b求偏导数，令它们的偏导数为零，将结果回带式(11)，化简得：

由式(12)(13)可以看出，拉格朗日函数式中已经没有ω、b两个变量了，只需要根据式(13)求出iα的值，便可以回带式(12)得到ω的值，b的值可以通过支持向量解得，即拉格朗日乘子iα不为零所对应的样本。

对于非线性可分问题，需要引入一个映射()φ⋅，将非线性数据样本映射到一个高维空间，使其变得线性可分。本文通过引入高斯核函数来解决室内定位的非线性分类问题。RSS信号存在噪声干扰会导致个别支持向量偏离正确数据，因此需要通过引入松弛变量来解决这个问题。式(14)为非线性拉格朗日函数的化简形式：

其中：C为引入松弛变量后的参数，称为惩罚因子，它的取值直接影响学习机的拟合性能；高斯核函数σ为函数宽度。相应的非线性分类函数为

SVM本质是二值分类器，本文采用一对一法处理多分类问题。在任意两类样本之间设计一个 SVM 模型，则k个类别就需要设计 k (k - 1 )2个 SVM。当需要对一个样本进行分类时，将分类器分别测试该样本，获得分类票数最多的类别即为该样本类别。

本文在基于SVM进行分类缩小定位区域之后，利用支持向量机回归（SVR）进行非线性拟合，构建映射函数。支持向量机回归与 SVM 原理基本相同，这里直接给出SVR的回归模型：

3.2 UKF优化定位结果

实时测量的RSS信号受到噪声干扰，具有突变特性，会对定位结果造成影响，而行动轨迹的定位结果之间是相关的，连续的，不存在突变的。因此，本文利用UKF算法实时跟踪定位结果，利用之前的位置预测下一时刻位置出现的置信区间，从而降低RSS信号突变带来的影响[14-16]。

UKF是一种非线性滤波方法，适合于SVR建立的非线性模型。该方法使用确定性采样方法对状态量进行处理。本文选取位置坐标 X =[x,y ]T作为状态量，由于状态量的变化相对于运算速度是缓慢的，或者说变化过程是一个平稳过程，则UKF滤波的状态方程与量测方程如下：

其中： Wk、 Vk为过程噪声和量测噪声；m为所选取之前位置点个数。则UKF计算过程如下：

1）初始化：

式中： Xa=[XTWTVT]为系统状态增广状态变量。

2）参数计算：

式中：n为增广状态向量的维数；α为刻度因数，可取 1 0-4≤α≤1；对于高斯分布，取β=2为最优值；κ为第三刻度因数，取κ=0。

3）计算Sigma采样点，即：

4）时间更新方程：

5）量测更新方程：

4 仿真实验与结果分析

4.1 仿真环境

为验证本文算法的定位效果，依据作者所在实验室的实际环境设置，使用 MATLAB构建虚拟仿真场景。如图2所示，仿真场景大小为16 m × 20 m的长方形区域，共分为6块定位区域，设置8个AP。

仿真选取224个指纹点和100个测试点，其中A、B、E区域选取42个指纹点，C、D、E分别选取18、54、26个指纹点，指纹点均匀分布于定位区域，测试点随机选取，如图3所示。

图2 室内仿真环境示意图Fig.2 Indoor simulation environment diagram

图3 参考点与测试点分布情况Fig.3 Distribution of reference points and test points

AP信道衰减模型采用标准室内对数路径损耗模型：

式中： PL(d0)为1 m处的信号强度，通常设置为经验值-45 dBm；路径损耗因子 η ∈ [1 . 6,3.3]；Xσ为均值为0，标准差为 σ ∈ [ 2 ,14.1]的高斯白噪声。

4.2 本文SALDE算法效果验证

为验证 SALDE算法对数据集特征提取的有效性，分别与改进前 LLDE和其他四种数据处理方法LE、LPP、NPE和SNE进行比较。为方便直观地显示处理效果，约减维数选取二维平面，即 d = 2 ，近邻K = 12，六种算法数据处理效果如图 4所示。由图中可以很直观地看出，SALDE、LLDE、LE、SNE的降维效果较好，有效地将采集点的RSS分类特征保留下来，LPP和NPE则出现了类别间相互交叉的现象。而SALDE相较于LLDE、LE、SNE，由于将类间距离引入，并且依据类间距离大小自行调整其引入值，SALDE类间距离能够保持得基本一致，较为平稳，其他算法则是过于接近或者松散。

为进一步验证算法性能，使用SVM分类器对降维结果进行分类，令N为训练样本总数，分别考查选取 N1= N / 3 、 N2= 2N / 3 、 N3=N 三种情况的分类效果，随机选取250个测试样本。从表1可以看出，在情况1~3时，SALDE分类精度优于LLDE，略好于LE算法，相比于直接使用 SVM 分类器得到的结果，分类精度分别提高了 7.2%、5.6%和 5.8%。从时间复杂度上看，SALDE也优于直接使用SVM进行分类。仿真结果证明使用 SALDE算法对数据进行预处理能够有效提高分类精度与运行时间。

图4 特征提取效果对比Fig.4 Comparison of feature extraction effects

表1 分类精度对比Tab.1 Classification accuracy comparison

4.3 UKF-SVM定位算法仿真

针对上述仿真环境，选取一条从定位区域D经F到达A区域的路线，每隔0.1 m选取一个测试点，共250个测试样本。图5为本文提出的算法与SVM回归算法的对比仿真结果。UKF仿真参数如下：β=2，κ=0，α=0.01,X0=[10,4]T, RW= 1 ， RV= 0 .5，

图5(a)为轨迹点散点分布图，图中UKF-SVM算法的散点分布相较于 SVM 回归更加贴近轨迹线。图5(b)为轨迹x轴坐标曲线图，SVM回归算法定位结果浮动较大，本文算法较为平滑，也更接近真实坐标。图 5(c)为坐标误差曲线图，本文算法误差基本保持在5 m以内，精度高，稳定性好。

图5 两种方法定位结果对比Fig.5 Comparison on positioning results of the two methods

图6 为本文算法、LLDE-SVM、SVM回归算法和神经网络算法（ANN）的定位精度对比图，图中表明本文算法在定位精度上相比于其他三种方法有明显提高。ANN算法由于在数据量较小，定位区间大的情况下，学习泛化能力差，定位精度最低。SVM算法因其泛化性好的优点，定位精度比ANN较好。LLDE-SVM 算法由于对数据进行了一定的降噪处理，精度相比于SVM提高较多，但仍达不到定位需求精度。本文算法进一步对数据特征进行挖掘，在定位误差2 m范围内，精度达到72.4%，相比于其他三种算法分别提高了 3.7%、18.2%、23.5%，在定位误差4 m范围内，精度高达95.8%，相比于其他三种算法分别提高了8.3%、17.7%、27.2%，定位精度得到明显提升，基本满足定位需求。

图6 定位误差对比图Fig.6 Comparison of positioning errors

5 结 论

对于室内无线定位，由于复杂环境与信号高维时变特性，传统方法不能很好地解决室内定位精度的问题。为了提高定位精度，本文提出一种特征提取和改进支持向量机的定位方法，该方法能够适应室内复杂环境，对干扰源不敏感，只依赖于场域分布。仿真结果表明。在数据量较少的情况下，该算法与传统的匹配算法相比，定位精度得到大幅度提高，能够将定位误差控制在一定范围内。

（

）：

[1] Zou H, Luo Y W, Lu X X. A mutual information based online access point selection strategy for WIFI indoor localization[C]//Proceedings of the 2nd International Conference on Information Science and Control Engineering. 2015: 769-773.

[3] Zhang G W, Xu Z H, Liu D. Research and improvement on indoor localization based on RSSI fingerprint database and K-nearest neighbor points[C]//International Conference on Communications, Circuits and Systems. Chengdu, 2013: 68-71.

[4] 朱宇佳, 邓中亮, 刘文龙, 等. 基于支持向量机多分类的室内定位系统[J]. 计算机科学, 2012, 39(4): 32-35.Zhu Y J, Deng Z L, Liu W L, et al. Multi-classification algorithm for indoor positioning based on support vector machine[J]. Computer Science, 2012, 39(4): 32-35.

[5] Rahman M S, Park Y, Kim K D. RSS-based indoor localization algorithm for wireless sensor network using generalized regression neural network[J]. Arabian Journal for Science and Engineering, 2012, 37(4): 1043-1053.

[6] 张勇, 黄杰, 徐科宇. 基于PCA-LSSVR算法的WLAN室内定位方法[J]. 仪器仪表学报, 2015, 36(2): 408-414.Zhang Y, Huang J, Xu K Y. Indoor positioning algorithm for WLAN based on principal component analysis and least square support vector regression[J]. Chinese Journal of Scientific Instrument, 2015, 36(2): 408-414.

[7] 邓志安. 基于学习算法的 WLAN室内定位技术研究[D]. 哈尔滨: 哈尔滨工业大学, 2012.Deng Z A. Research on learning based WLAN indoor positioning techniques[D]. Harbin: Harbin Institute of Technology, 2012.

[8] Tenenbaum J, Silva V, Langford J. A global geometric framework for nonlinear dimensionality reduction[J].Science, 2000, 290: 2319-2323.

[9] Roweis S, Saul L. Nonlinear dimensionality reduction by locally linear embedding[J]. Science, 2000, 290: 2323-2326.

[10] Kokiopoulou E, Chen J, Saad Y. Trace optimization and eigenproblems in dimension reduction methods[R]. University of Minnesota, 2010: 1-36.

[11] 谷瑞军. 基于流形学习的高维空间分类器研究[D]. 无锡: 江南大学, 2008.Gu R J. A study on classifiers in high-dimensional space based on manifold learning[D]. Wuxi: Jiangnan University,2008.

[12] 李波. 基于流形学习的特征提取方法及其应用研究[D].中国科学技术大学, 2008.Li B. The study of the manifold learning based feature extraction methods and their applications[D]. Anhui:University of Science and Technology of China, 2008.

[13] Xu Y, Chen X Y, Wang Y M, et al. Improved indoor pedestrian navigation method using low-cost foot-mounted AHRS and shoulder- mounted compass[J]. Journal of Chinese Inertial Technology, 2016, 24(3): 325-329.

[14] 严恭敏, 严卫生, 徐德明. 简化UKF滤波在SINS大失准角初始对准中的应用[J]. 中国惯性技术学报, 2008,16(3): 253-264.Yan G M, Yan W S, Xu D M. Application of simplified UKF in SINS initial alignment for large misalignment angles[J]. Journal of Chinese Inertial Technology, 2008,16(3): 253-264.

[15] Gustafsson F, Hendeby G. Some relations between extended and unscented Kalman filters[J]. IEEE Transactions on Signal Processing, 2012, 60(2): 545-555.

[16] 曾庆化, 王敬贤, 孟骞, 等. 基于 UWB优化配置的室内行人导航方法[J]. 中国惯性技术学报, 2017, 25(2):186-191.Zeng Q H, Wang J X, Meng Q, et al. Indoor pedestrian navigation method based on optimal allocation of UWB[J]. Journal of Chinese Inertial Technology, 2017,25(2): 186-191.