室外定位技术目前最常用的是全球定位系统(Global Position System,GPS)，在室外空旷的环境下，GPS的精度能够得到较好的保证^[1].然而，由于建筑物的遮挡，卫星信号在室内环境中不能正常传输，导致GPS接收器难以接收到无线信号，无法实现正常的定位和导航功能.

无线WiFi是目前广泛使用的一种移动互联网技术，被部署在很多教学楼、家庭、办公室、商场等室内环境中.同时，随着计算机技术的发展，智能移动终端的成本不断降低，移动互联网在人们日常生活中得到普及，使得利用WiFi技术进行室内定位具有可操作强、成本低以及覆盖性广等优点，被广泛应用在自动化、自动行走技术^[2]、地理信息处理技术^[3]及作为其他定位系统的辅助部分^[4].

1 基于无线网络技术的室内定位算法

目前，基于无线网络的室内定位算法主要分为3种：几何法^[5]、近似法^[6]和场景分析法^[7].Wang等人^[8]对信号的衰减进行建模，得到了信号传播的距离与强度的关系，并通过模拟实验建立了信号穿墙的损失函数.根据目标所获得的无线信号强度，可以估计出其位置，从而实现定位.但是，这种方法需要严格控制室内环境的无线网络部署，限制了其适用性.Battiti等人^[9]通过使用统计学习理论建立接收信号强度(Receive Signal Strength Indication,RSSI)与位置的关系模型来实现室内目标定位，但是他们的实验只在小范围内进行，样本较少，不具有普遍性.De Moraes等人^[10]提出了一种无须离线训练的WiFi定位方法，定位精度可达到2 m左右，但是这种方法定位区域大小有限，因此推广困难.桑楠等人^[11]提出了一种基于SVM分类和回归的WiFi室内定位方法，该方法对室内区域进行分割，形成多个相互独立的小区域，使用支持向量机建立每个区域的接收信号强度和位置的非线性模型，并以此来对待测点的位置进行估计.但是，当室内存在较多的障碍物时，这种方法得到的RSSI与位置的非线性关系并不准确，定位误差较大.Chen等人^[12]提出使用卡尔曼滤波算法建立RSSI和位置的关系，并以此实现目标的定位.

目前，位置指纹^[13]被广泛用于室内定位算法中.这类算法主要包含两个阶段：离线阶段指纹采集及在线阶段指纹匹配.离线阶段，采集参考点从接入点(Access Point,AP)所接收的RSSI，并将这些RSSI按特定的顺序存放，构成该参考点的位置指纹.采集所有参考点处的位置指纹，并建立位置指纹数据库存放所有参考点的位置指纹及其对应的坐标信息.在线阶段，获取待测点处的位置指纹，并将其与指纹数据库中的位置指纹进行匹配，用匹配所得到的位置指纹所对应的坐标信息来对待测点的位置进行估计，从而实现定位.从指纹匹配的角度来看，定位问题可被转换为一个多分类问题.

近来，稀疏表示^[14]因对信号重构的高效性和准确性，被广泛用于计算机视觉领域，如目标检测^[15]、目标跟踪^[16]、图像分类^[17]等.基于此，本文提出了一种基于位置指纹和稀疏表达的WiFi室内定位算法.在离线采集阶段，首先在待测区域内选取若干参考点，对于每个参考点，多次测量其位置指纹，作为该位置训练样本的位置指纹，并将所有参考点的位置指纹组成稀疏字典.在匹配阶段，首先获取待测点的位置指纹，根据待测点位置指纹在稀疏字典上投影的不同将待测点与参考点进行匹配，从而对其位置进行估计.算法流程图如图 1所示.

2 稀疏字典构建

在室内区域内部署m个AP，并选取N个参考点.对于第n (n=1,2,…,N)个参考点采集m个AP的信号强度形成一个M维矢量作为指纹信息f:

其中:f为第n个参考点的指纹矢量;s_i为第i个AP的信号强度.在第n个参考点上采集p次指纹，组成的矩阵可以表示该位置的指纹库F_n:

其中:f_j(j=1,2,…,p)表示第n个参考点上第j次采集的指纹.将N个参考点的位置指纹组成数据字典:

式中:F_n表示N个参考点位置的指纹库;A为N个参考点的数据字典.

3 基于稀疏表示的室内定位算法

待测点的指纹信息y可表示为如下形式：

其中:x表示待测点的指纹信息在数据字典上的投影系数.如果待测点的指纹信息与第n个参考点的位置指纹匹配，则其投影系数中只有与第n个参考点指纹库相关的系数不为零.这表明，y的投影系数x具有稀疏性.根据文献^[18]，可通过解l₁优化问题来求解稀疏解:

但是，在实际问题中通常存在噪声，需加入误差阈值，可将式(5)改写为

式中：x^*为x的近似值；ε是误差阈值.对式(6)进行求解，得到了x的近似解x^*.然而，建模误差和噪声的存在，使得投影系数x并不是理想值.为判别待测点所属的指纹库，定义向量δ_n(x^*)为向量x^*中只与第n个参考点的指纹库相关的非零行.因此，若y属于第n个参考点的指纹库，则y的近似值可表示如下：

其中，y^*_n表示y在第n个参考点指纹库上的近似值.两者差值越小，y与第n个参考点指纹库相匹配的可能性越高，采用如下判别函数：

如何求解l₁最小化范数是稀疏表示的关键.Deedell等人^[19]提出了一种ROMP算法.对稀疏度为K的信号，若余量与字典相关系数为g∈R^M×1，选出K个最大的相关系数存入候选集J，将J进行分组，对于任意分组Q，若满足所有i,j∈Q，则

选择能量最大的一组子集Q作为最终的索引值集，选取该索引值集对应的原子集λ_Q，根据最小二乘法计算信号逼近x′及更新余量r_new：

传统的ROMP算法需要把信号的稀疏度作为求解条件，而信号的稀疏度往往是未知的.为此，文献^[20]对传统ROMP算法进行了改进，提出了一种正则化二次筛选正交匹配追踪算法，该算法不需要预知信号的稀疏度，且求解速度比传统ROMP更快.

4 实验 4.1 仿真实验

本文首先利用仿真实验对算法的性能进行估计.信号强度通过常用的对数距离路径损耗模型进行模拟：

式中：γ表示多径衰弱，服从Rayleigh分布；p₀为1m处的信号强度，p₀=－45dbm；n为路径损耗指数，n=2.326；ξ为阴影衰弱，服从均值为0、标准差为5.2的正态分布.

参考点的位置指纹由接入点的个数决定.一般地，接入点越多，位置指纹所包含的信息越丰富，定位结果越精确，但随之定位成本也将提高.本文采用不同个数的接入点进行仿真试验，结果见图 2.

从图 2中可知，接入点个数越多，定位精度越高.接入点数量达到一定后，定位精度趋于稳定.综合考虑定位精度和成本，本文算法使用9个接入点.

4.2 实验环境

实验场地设置在面积为144 m²的开放教学楼(12 m×12 m)，包含2个走廊、4个教室，每个教室包含2条走道和若干排座位.离线采集阶段，将整个区域均匀分割为1m×1m的单元格，在每个单元格中心采集位置指纹10次，用于构建数据字典.指纹匹配阶段，在实验场地随机选取600个待测点，并测量位置指纹，使用本文算法来估计待测点的位置.为了更好验证算法性能，将本文算法与基于SVM的定位算法^[21]进行比较.本文算法中需要确定的参数为重构的误差阈值ε，设置为ε=0.15.比较结果如图 3所示.由图 3可知，本文算法在定位误差为2m和4 m时的累计概率分别为45.7%和95.3%，明显优于SVM定位算法.

4.3 实验分析

为了取得较好的定位结果，SVM中的多个参数需要进行多次调解和优化，而且所得到的分类器并不能综合利用全局参考点的信息，导致最终的定位结果不够精确.本文提出的基于稀疏表示指纹定位算法能够充分利用位置指纹冗余信息，对待测点的位置指纹进行重构，并根据重构的误差来对待测点所属类别进行有效分类，从而实现定位.此外，本文算法只需要确定误差阈值，不需要对参数进行多次优化，提高了定位效率.

5 结论

本文提出的一种基于稀疏表示的室内定位算法，可以有效实现室内定位.首先在室内区域选择若干个参考点，多次测量参考点从接入点接收到的WiFi信号强度，构建稀疏数据字典.通过稀疏表示方法，用参考点的指纹矢量对待测点处的指纹矢量进行重构，根据重构误差来估计待测点的位置.实验结果表明，本文方法能够有效实现室内定位.