0 引言

室内定位近年来受到越来越多的关注。基于WiFi框架的室内定位系统由于无需添加额外的硬件、低成本、广泛部署等优点已被广泛应用，因为WiFi网络在许多地方变得相当普遍，因此，基于WiFi技术的服务和应用越来越受欢迎。大多数WiFi室内定位系统都利用指纹技术。基于WiFi的定位系统在室内环境中采集检测到的接入点(Access Point, AP)的接收信号强度(Received Signal Strength, RSS)值，建立射频指纹库，然后使用模式匹配的方法来估计用户的位置。然而，并非所有收集的RSS值对估计过程都有显著贡献，受到多径效应的影响产生不稳定的RSS值^[1]，最终会降低定位精度。类似地，并非所有检测到的AP都要参与对未知位置的定位，一些检测到的AP可能在指纹库中丢失率较高或者受到干扰较大^[2]，使得在位置估测中不仅不会提高定位精度反而会增加额外的计算开销。考虑到这些点，本文从指纹库中去除那些无用的RSS值和AP。

K最近邻法(K Nearest Neighbor, KNN)算法广泛应用于室内定位系统中，在传统的KNN算法中，将信号强度定义为物理距离，即当信号差相等时就被认定为物理距离相等。然而在复杂的室内环境中，并不能这样认定^[3]。在文献[4]中指出在不同距离区间内，RSS信号值衰减的幅度大小不同，即在各距离区间内两区间端点RSS信号差值与该距离区间长度的斜率是不同的。为了提高定位精度，如何解决这一关键性问题值得深入研究。

为了解决上述问题，本文先对AP的选择方法进行了改进，选取稳定性高的RSS值和丢失率低、干扰小的AP。接着又提出了一种基于缩放权重的KNN算法(Scale Weight KNN, SW-KNN)，在估计两个RSS向量的有效信号距离时，在不同的信号强度下给信号差值分配不同的权重。为了计算有效信号距离，建立了一个缩放权重模型。

1 传统KNN算法

KNN是数据挖掘领域中普遍而强大的分类算法，由于其简单性，已被广泛应用于许多领域。最近邻算法首先由盖和哈特在1967年提出^[4]。KNN是一种简单、直观的算法，适用于几乎所有类型的数据结构。它第一次在无线电探测和测距(Radio Detection And Ranging，RADAR)^[5]中用于室内定位系统，首先计算未知位置的RSS向量和每个指纹之间的信号距离，然后返回K个最近邻指纹。每个指纹是预先选择的参考点，并且由从不同AP收集的平均RSS值的向量表示。基于KNN传统的室内定位通常由两个阶段组成：离线阶段和在线阶段^[6]。

在离线阶段，目标区域通常覆盖有一组预定的网格点(已知坐标)，称为参考点(Reference Point, RP)，参考点集合为L={l_i=(x_i, y_i), i=1, 2, …, l}，其中l为RP总数，(x_i, y_i)表示第i个参考点的二维物理空间坐标。n为待定区域内AP总数，AP集合为A={AP₁, AP₂, …, AP_n}。在l_i处测量对各AP的RSS，获得一个参考数据r_i=(r_i1, r_i2, …, r_ij, …, r_in)，其中r_ij代表在l_i处采集AP_j的RSS的均值。将(l_i, r_i)存入指纹库中，所有参考点重复上述步骤以完成射频指纹库的建立。

在在线阶段，处于未知位置的移动设备将其从不同AP采样获得RSS值，表示为o=(o₁, o₂, …, o_n)，然后计算o和r_i的相似度获得估计位置$\hat{l}$，实际上，这是将定位看作基于RSS的模式识别。如式(1)所示，传统KNN算法通常使用信号空间欧氏距离来计算相似度，D_i越小相似度越高。根据D_i大小对指纹库中的(l_i, r_i)进行升序排序，选取前K个参考点的坐标，最后根据式(2)和式(3)得到估计的位置$\hat{l}$。

${{D}_{i}}=\sqrt{\sum\limits_{j=1}^{n}{{{\left( {{r}_{ij}}-{{o}_{j}} \right)}^{2}}}}$

(1)

$\hat{l}=\sum\limits_{i=1}^{K}{{{\omega }_{i}}}{{l}_{i}}$

(2)

${{\omega }_{i}}={{D}_{i}}^{-1}/\sum\limits_{j=1}^{K}{{{D}_{j}}^{-1}}$

(3)

在KNN中，本文发现具有最小信号距离的RP可能不是具有最小几何距离的RP。这是因为式(1)认为在某种程度上信号差异和物理距离之间的关系与实际的信号强度无关。相反，式(1)中只认为，信号距离D_i仅与RSS差值r_ij-o_j有关。因此，无论实际RSS值o_j是什么，RSS差值的所有权重都被设置为1。

为了解决上述问题，本文引入基于信号强度的缩放权重，用于计算不同信号强度的有效信号差异，作为比较信号之间相似性的新特征。

2 改进算法 2.1 AP的选择

由于室内环境复杂，例如其他无线设备的干扰，人体对信号强度的吸收和由于反射造成的多径效应^[7]，都会对定位精度产生影响。20个移动设备在同一个未知位置收集来自5个不同AP的RSS值，实验结果如图 1所示。在图中可以观察到，由于室内环境的干扰，20个移动设备在同一未知位置收集来自同一个AP的RSS值并不是相等的，有的甚至会发生大幅度的突变，本文称其为RSS的异常值。RSS异常值会使定位精度降低，所以如何处理不稳定的RSS值是指纹定位过程中需要解决的关键问题之一。

针对上述问题，定位系统中使用箱形图^[8]的方法过滤RSS异常值。箱形图计算过程如下：

1) 收集在同一未知位置处来自同一个AP的20个RSS样本值并按升序排列。

2) 找到RSS样本值的第一四分位和第三四分位，记为Q₁和Q₃。

3) 计算间距范围，四分位数的间距(Inter Quartile Range, IQR)为: IQR=Q₃-Q₁。

4) 异常边界设置为C₁=Q₁-1.5IQR，C₂=Q₃+1.5IQR。

RSS异常值滤波方法如图 2所示。

如果RSS样本值小于C₁或者大于C₂，系统将其认定为异常值并丢弃。RSS异常滤波方法使得收集到的RSS样本值均为正常值。

最后，计算RSS样本值的均值作为指纹信息存储到数据库中，称为射频指纹数据库, 在在线定位阶段用于处理模式匹配。

在室内环境中有很多可以检测到的AP，由于每一个AP都可以提供指纹信息，所以在传统的指纹定位系统中在定位区域部署了很多AP以提高定位精度，并且在在线定位阶段使用所有可以检测到的AP估计未知位置，然而，被多径效应影响的AP不仅不会提高定位精度反而会降低定位精度。此外，越多的AP用于定位，计算量也会越大。为了在提高定位精度的同时还能减少计算量，最好选择丢失率低和干扰较小的AP。

每个参考点都不会观察到定位区域内的所有AP。任何一个AP的缺失值被定义为没有观察到该AP的指纹。因此，丢失值百分比高的AP应被丢弃，因为它可能是不可靠的AP。在整个室内定位环境中，缺失值百分比大于80%的AP应被丢弃^[9]。

为了选择干扰较小的AP，可以通过在在线定位阶段计算AP的RSS标准偏差(Standard Deviation, SD)。RSS标准偏差可以辨别每个AP的受干扰程度。较小的SD值表示从AP接收的RSS值偏离平均值小，AP的干扰也小，适合于处理模式匹配：首先，系统通过RSS异常过滤的方法过滤掉不正常的RSS；第二，丢弃丢失率高的AP；第三，计算来自每个AP的RSS值的SD，然后按照SD值将所有可用的AP按升序排列；最后，选择前n个AP用于处理模式匹配。假定定位区域中当前可用的AP总共为m，则SD计算如式(4)所示：

$S{{D}_{j}}=\sqrt{\frac{1}{t-1}\sum\limits_{a=1}^{t}{{{\left( RS{{S}_{ja}}-{{\overline{RSS}}_{j}} \right)}^{2}}}}$

(4)

其中: SD_j表示第j个AP的标准偏差(1≤j≤m); RSS_ja是从第j个AP采集的第a个RSS值; RSS_j表示从第j个AP采集的所有RSS值的均值; t为RSS值的个数。

具有RSS标准偏差的AP选择可以过滤掉受干扰大的AP, 因此预测位置将更加稳定和准确。

2.2 SW-KNN

与经典KNN算法相比，SW-KNN具有以下两个增强功能。首先，通过引入缩放权重来计算不同信号强度的有效信号差异，从而建立基于RSS的缩放权重模型。其次，计算移动设备在未知位置测量获得的RSS和指纹库中每个指纹之间的有效信号差异，使用上述缩放权重来查找K个最近邻指纹。

基于RSS的缩放权重模型用于计算有效信号距离，式(1)可以改写为：

$D_{i}^{'}=\sqrt{\sum\limits_{j=1}^{n}{{{\left( {{r}_{ij}}-{{o}_{j}} \right)}^{2}}}\times w\left( {{o}_{j}} \right)}$

(5)

式中n为经过AP选择后参与位置估计的AP数，其余各变量与式(1)中的含义相同。新提出的缩放权重函数w(·)，它的值随移动设备在未知位置处采样的实际RSS值o_j而变化。由于引入基于信号强度差的缩放权重，由式(5)计算出的有效信号距离可以比式(1)更精确地表示移动设备与第i个参考点之间的信号距离。

接下来，讨论如何获得缩放权重函数w(·)，这是SW-KNN算法的关键部分，包含两个步骤：确定缩放权重函数形式和调整参数。

2.2.1 确定缩放权重函数形式

由于室内复杂的无线电环境，很难为w(·)给出一个固定的形式。为了处理这种复杂的情况，本文将整个RSS空间划分为b个相等的非重叠间隔，并尝试为每个RSS间隔找到一个常量缩放权重。因此，本文将RSS值换算成缩放权重，如式(6)所示：

$w\left( x \right)=\sum\limits_{c=1}^{b}{{{\alpha }_{c}}{{\chi }_{c}}\left( x \right)}$

(6)

其中：x是真实的RSS值，w(x)表示在信号强度为x处实际信号差的缩放权重。让A_c表示第c个RSS间隔(1≤c≤b)。α_c是区间A_c的系数，χ_c(x)是区间A_c的指标函数，得到式(7)：

${{\chi }_{c}}\left( x \right)=\left\{ \begin{array}{*{35}{l}} 1, & x\in {{A}_{c}} \\ 0, & x\notin {{A}_{c}} \\ \end{array} \right.;1\le c\le b$

(7)

例如，移动设备采集的RSS值属于间隔A_c。根据式(7)，χ_c(x)的值为1，将所有其他的χ(x)值设置为零。然后计算w(x)的结果等于α_c，α_c是在RSS值为x处用于计算有效信号距离的缩放权重。

2.2.2 调整参数

现在的问题是如何调整间隔数b和间隔系数α的值，构建缩放权重模型，以实现提高定位精度，图 3为缩放权重模型。

间隔数b越小，定位精度越高，但是计算开销也越大。本文先将间隔数假定为b，在实验中确定b值。

这部分主要探讨如何调整间隔的系数，这通常是参数优化问题。本文使用模拟退火法(Simulated Annealing, SA)^[10]来调整系数。图 4给出了调整系数的流程。

根据流程可以看出主要的工作流程分为4个部分：准备、评估、优化和验证。关于4个部分如何工作的细节描述如下：

1) 准备。为了调整缩放模型的参数，本文使用holdout方法^[11]将无线电图分成两个部分：训练集、测试集1和测试集2。训练集中是已知坐标的参考点; 测试集1用于在不断调整系数的过程中评估定位精度，最终实现提高定位精度的目的; 测试集2用于对获得系数进行验证。

2) 评估。在随机获得一组新的系数后，将测试集1输入到缩放权重模型中，以生成测试集1中每个位置的估计坐标，通过式(8)计算距离误差的总和来评估定位精度。

$error=\sum\limits_{i=1}^{{{L}_{1}}}{\sqrt{{{\left( {{x}_{i}}-x_{i}^{'} \right)}^{2}}+{{\left( {{y}_{i}}-y_{i}^{'} \right)}^{2}}}}$

(8)

其中：(x_i, y_i)是第i个参考点的真实坐标，(x_i^′, y_i^′)是第i个参考点的估计坐标，L₁是测试集1中参考点总数。在评估过程中，测试集1中的参考点实际上被认为其位置是未知的，在位置估计过程中以训练集为参考点，估测测试集1中的未知位置。显然，使公式中的函数返回零的系数是最优解。

3) 优化。使用模拟退火法搜索定位精度更高的一组系数。设置初始温度T₀=100，最大迭代次数f_max=1000。在每次迭代过程中，部分系数是随机变化的。如果新的误差较小，则新系数将成为当前的系数; 如果不是，在一定的概率下新系数还将成为当前系数。该过程一直持续到迭代次数达到最大为止。

4) 验证。在这个阶段，本文进一步使用测试集2来验证从前一阶段获得系数的缩放权重模型的性能。

2.3 SW-KNN算法工作流程

基于SW-KNN的室内定位算法同样主要由两部分组成。在离线阶段，首先，本文使用箱形图去除接收来自AP的RSS样本的异常值，以稳定RSS值；然后，剔除丢失率高的AP。在在线阶段，首先过滤RSS异常值并使用SD来分析RSS的变化，并选择干扰较小的前n个AP；接着使用缩放权重模型计算未知位置的RSS和指纹库中每个指纹之间的有效信号距离；最后收集导致最小有效信号距离的前K个参考点坐标，从而得到未知位置坐标。算法框架流程如图 5所示。

3 实验与结果分析 3.1 实验准备

本文在学校实验室进行实验。实验室大小是10 m×15 m，面积150 m²。实验室中有20套桌椅，人在实验室走动不频繁。训练集中有45个参考点，且每个参考点之间间隔1.5 m。测试集有280个参考点，每个参考点间的距离为0.5 m。所有的参考点均分布在13×25的网格交叉点, 如图 6所示。此设置确保训练集和测试集中参考点不重叠，模拟现实场景。测试集随机分为两个：测试集1和测试集2。在每个参考点采样获得50个RSS值的向量。

本文使用三星手机作为信号测量的移动设备。在离线阶段检测到22个不同的AP，实验中所有的AP都是预先存在的，并不会部署其他AP，其硬件类型和位置是未知的。最邻近点选择太多可能降低定位的准确性，因为一些最近的点可能距离当前位置太远。KNN算法的K值一般选取3或4将产生最佳结果^[12]，所以本文将为实验设置K=3。为了便于比较，本文把基于改进AP选择的传统KNN算法定义为A-KNN。本文将使用平均定位误差和累积分布函数(Cumulative Distribution Function, CDF)作为评估指标对实验结果进行验证。

3.2 调整间隔数

本文使用不同数量的间隔来探讨间隔数对SW-KNN性能的影响。表 1总结了这些设置下的定位精度和优化时间。可以看出，随着间隔数的增加，平均定位误差呈下降趋势，但在20个间隔后下降趋势不明显, 优化时间没有显著变化。所以为了实现提高定位精度的同时，运算量也不会太大，本文选取间隔数n=20。

3.3 实验结果及分析

表 2为测试集1获得的系数，本文使用测试集1中获得的系数对测试集2进行操作，以评估它们是否适合于其他测量环境中的参考点。定位精度为在测试集2中偏离实际位置距离的平均定位误差。基于测试集2，对KNN、A-KNN与SW-KNN算法进行比较。

表 3显示了三种算法平均定位误差的比较。可以看到A-KNN比KNN低21.9%，而SW-KNN比KNN低53.6%。

如图 7所示，表示三种不同算法距离误差的累积分布函数。很显然，SW-KNN算法的定位精度最高，而且改进AP选择的方法也提高了KNN算法的定位精度，从而使得SW-KNN算法的定位精度更高。以分布概率为0.8为例，SW-KNN算法的误差距离大概在2 m左右，而KNN的误差距离超过了5 m。

通过测试集2验证，SW-KNN算法使定位精度有了显著提高，接下来本文将该算法应用到实际环境中，验证其是否适用于其他室内环境。如图 8所示，实验区域为一个约1500 m²的典型室内环境，包括1个教室、2个办公室、8个实验室、1个娱乐区和1个走廊。区域内可见AP总数为53个。离线阶段和在线阶段的数据采集使用同一部三星手机。离线阶段在实验区域内共选定了120个参考点。两个最近邻参考点间距最小为1 m，最大为5.2 m。参考点最少有3个AP可见，最多有15个AP可见。在每个参考点采样获得50个RSS值的向量，首先过滤掉RSS异常值并将其余数据取平均值得到一条参考数据与位置信息组成一条射频指纹存入射频指纹库，再剔除指纹库丢失率高的AP建立最终的指纹库。

在在线阶段，选取50个测试点(含测试起点和测试终点)。每次测试由测试起点开始，以一条固定的路径在实验区域内移动，每经过一个测试点采集一个观测值并将对应的位置信息保存以便计算定位误差，进入房间后均以原路返回。一次测试中所有测试点均被经过2次，共进行10次测试，在每个测试点得到20个RSS向量。同样过滤RSS异常值后求均值再将离线阶段未剔除的AP依据SD值进行选取用于处理模式匹配。最后，根据之前实验中获得的缩放权重系数，为每一个RSS值分配权重，用式(5)、式(2)和式(3)即可得到估计位置。

如图 9所示，在该实验环境下，对KNN、A-KNN和SW-KNN三种算法的定位精度进行了比较，实验结果表明，SW-KNN算法定位精度最高，该算法适用于其他的室内环境。

4 结语

本文提出了WiFi室内定位的AP选择方法。首先使用箱形图来减少多径效应的影响，然后又剔除了指纹库中丢失率高的AP，最后使用标准差来分析RSS的变化，并选择具有较小干扰的前n个AP进行位置估计。实验结果表明，本文提出的A-KNN算法的性能优于KNN算法。通过文献发现在经典KNN算法中将信号强度定义为物理距离。因此，本文在改进AP选择方法的同时构建了一个基于RSS的缩放权重模型，提出了一种基于缩放权重的K最近邻算法，以提高定位精度。实验结果表明，本文提出的SW-KNN算法在相同的室内环境下定位精度比KNN好得多。最后，又将SW-KNN算法应用于其他室内环境中，实验结果表明，该算法在室内环境下都可以提高定位精度。