利用指纹稀疏性的室内定位技术

沈 昀 陈 爱

(中国科学院深圳先进技术研究院实时监测与传输技术研究中心 深圳 518055)

1 引 言

随着移动设备的发展与普及，基于信息的应用服务层出不穷。 用户信息中一个相当有价值的信息就是用户的位置信息，因而室内定位技术也成为了近年来的一个热点问题。由于室内定位信息可以广泛应用于医院、商场和展馆等各种大型室内场所，因此如何方便地获得准确的室内定位信息是一个十分值得研究的课题[1]。

随着 GPS(Global Positioning System)技术的不断完善，室外定位技术已发展得十分成熟。然而，由于在室内无法接收 GPS 信号及存在室内环境复杂等局限，室内定位技术尚面临着很多技术或成本上的难题。现有的相对成熟的室内定位技术主要基于 RFID(Radio Frequency Identification)[2]、超声波和 FM(Frequency Modulation)[3]等设备。尽管这种方法可以获得较高的精确度，但需要额外的信号发射或接收设备，所以一方面有着较高的成本限制，另一方面部署也费时费力。基于这些考虑，目前出现的低成本且成熟的室内定位技术则是基于无线网络信号强度(Received Signal Strength Indication，RSSI)的室内定位技术[4]。由于该技术可以利用当今主流移动设备普遍配备的无线网络信号接收模块以及大型室内场所普遍存在的无线网络信号，能做到近乎纯软件实现的室内定位，在目前的市场中拥有比较广大的应用场景。

基于 RSSI 的室内定位技术主要分为基于模型和基于指纹的两类主流算法。其中，基于模型的算法指的是通过现有的室内位置信息以及无线信号发射源信息，建立数学模型，根据模型由信号强度推算出相应的位置坐标。该类算法简单易实现，但由于室内环境较为复杂且无线网络信号容易被干扰和吸收，数学模型很难全面且动态地体现位置信息与信号强度间的关系，因而存在较大的定位误差。基于指纹的室内定位算法中，指纹指的是在某个地点，设备接收到的数个无线信号发射源发射的信号强度组成的向量。可以想象，由于信号强度随着距离衰减，每个点可以获得不同的指纹。因此应用指纹法时，首先采集一定密度的定位参考点的指纹信息，之后定位时再将实时指纹通过匹配算法匹配到对应的参考指纹上。指纹法可以获得较高的定位精度且可以做到纯软件实现。

目前比较常见的基于指纹的室内定位算法包括简单的 KNN 算法以及较为复杂的概率模型算法[4]。KNN 算法指直接用向量距离匹配指纹，而概率模型算法(如高斯模型法)则使用概率模型对指纹的分布概率进行估计，从而匹配指纹。但是，由于室内环境与室内设备的干扰，指纹并不完全稳定，容易受到噪声的干扰，导致定位精度下降。因此，本文引入稀疏表示方法[5]，提出一种指纹匹配算法，利用指纹的稀疏性，提取指纹的主要特征，从而分离指纹中的噪声，提高定位匹配精度。

2 利用指纹稀疏性的定位方法

2.1 指纹的稀疏表示

受到图像识别领域中特征脸方法的启发[6]，我们联想到提取指纹的特征来进行指纹分类。稀疏表示作为近年来特征脸方法的主流方法，以其简单、准确和扩展性强成为了一种有效、快速的特征提取方法。因此我们考虑引入稀疏表示方法提取指纹特征，同时去除噪声。

信号能够被稀疏表示，就是将信号投影到变换基时绝大部分变换系数的绝对值很小或为零，这样得到的信号被认为是稀疏的。因而信号的稀疏表示可看作是信号由一组不完备的基(基的个数小于 N)近似完整表示，这是原始信号的一种间接表达。

通过稀疏表示方法，具有相似特征的同一类信号可以被一组特定的不完备基间接表示，而无法被这组基近似完整表示的信号则不具有该特征，因而不属于该类。与此同时，噪声由于其本身存在的随机性而不具有特征，更不具有信号的特征，因此无法被稀疏表示。可见，利用稀疏表示方法的特征提取，既可以将信号进行分类，又具有很好的去噪能力。

本文利用稀疏表示算法进行指纹匹配，为了验证指纹具有稀疏性，我们引入主成分分析方法[7]进行了实验。主成分分析方法通过将原有信号的基进行旋转变换，以获得数量较少的重要基，这些基即代表了原有信号的主要成分。主成分的方向越少，则信号越稀疏。通过实验，我们采集了数个点的数百条指纹，对于每个定位点，分析出信号在其维度方向上仅具有一个能量极强的主成分(如图 1 所示)，因此可以说明指纹本身是具有稀疏性的。

图1 RSSI 指纹的主成分分析Fig. 1. PCA of RSSI fi ngerprints

2.2 基于指纹稀疏表示的室内定位算法

通过上述分析，我们研究出了一个利用指纹稀疏表示的室内定位算法。该算法利用指纹构建稀疏表示所需要的不完备稀疏字典，进而使用稀疏字典对需要被定位的指纹进行稀疏表示。通过稀疏表示一方面对指纹进行了分类，另一方面在一定程度上将指纹中的高维噪声分离出来。整个算法流程可以大致分为两个过程：训练过程和定位匹配过程。

在训练过程中，首先采集各个参考点的训练指纹，然后利用训练指纹训练出每个参考点的稀疏字典，并且得到该点的主特征指纹及其稀疏表示形式。

在定位匹配过程中，我们将实时指纹向每个参考点的稀疏字典进行投影，获得相应的可以被表示部分的稀疏表示形式以及不能被表示的残差[8]。残差越大，代表该指纹与该参考点处的特征指纹不相似程度越大，而稀疏表示形式的近似程度也在一定程度上代表了指纹的相似程度。因此本方法通过一个权重系数调整残差与稀疏表示形式近似程度对于匹配结果的影响，从而获得优化的近似程度。最终最大程度上象征了指纹与其对应参考点的匹配程度。

由于指纹本身具有稀疏性，而环境导致的随机噪声由于其随机性，而不具有稀疏性，因此使用稀疏表示方法表示出的特征指纹可在一定程度上去除噪声，从而提高定位精度以及定位算法的鲁棒性。

2.2.1 训练过程

训练过程中首先要采集训练指纹。在一个定位环境中，我们对设备可到达的区域每隔一定距离设置一个参考点 P1, P2, …, PN表示。之后，在每个参考点，分别用 Pi(i＝1, 2, …, N)均采集 M条训练指纹 Fi1, Fi2, …, FiM存入指纹库中。指纹库中记录着每个定位点的坐标(xi, yi)，以及对应的 M 条指纹 Fi1, Fi2, …, FiM。

对于每个参考点，我们使用稀疏表示方法提取它的特征指纹，首先需要获得稀疏表示中的稀疏字典，字典元素可以由采集到的训练指纹构成。获取稀疏字典的求解过程原本是一个 NP 困难(即无法在多项式时间内求解)的问题，因此我们使用贪心算法获得该问题的次优解。正交匹配追踪法是稀疏表示中比较流行的一种方法[9]，鉴于它速度快、复杂度低，我们也采取这种算法进行稀疏字典的选取。稀疏字典由该点部分训练指纹构成，可以以线性方式近似表示该点的所有指纹，并且字典大小小于指纹维度[10]。

获得参考点 i 的大小为 k 的稀疏字典的具体过程如图 2 所示。

图2 获取参考点 i 稀疏字典的流程图Fig. 2. Flow chart of fi nding the sparse dictionary of position i

在求得稀疏字典后，需要得到该点的特征指纹以及其稀疏表示。我们使用训练指纹的平均指纹作为噪声较小的主指纹，之后将平均指纹向其字典 Di构成的空间上进行投影，获得投影系数向量 Ci＝(ci1, ci2, …, cik)以及残差 r，其中残差作为噪声直接丢弃。投影系数作为稀疏表示的表现形式与该点的稀疏字典一起存储在指纹库中。

至此，训练过程结束，我们得到了每个定位点特征指纹的稀疏表示形式以及相应的稀疏字典。

2.2.2 定位匹配过程

匹配过程中，获得需要进行定位的实时指纹后，需要计算该指纹与每个参考点特征指纹的近似程度。其中，近似程度由两部分组成：一是指纹间稀疏表示的相似程度；二是不能被表示的残差的大小。我们通过添加一个权重参数来调整这两部分对近似程度的影响，而这个权重参数由另外采集的一部分训练指纹通过训练得出。最终，我们将选取近似程度最大的参考点作为定位结果。

首先我们需要获得要进行定位的实时指纹的稀疏表示形式。对于需定位的指纹 ft，将其往Pi(i＝1, 2, …, N)的每个参考点的字典 Di上进行最小二乘投影，获得对应的系数 Cit＝(cit1, cit2, …,citk)与残差 rt。之后使用距离公式(见公式(2))计算指纹与每个定位点的距离。

最终选取最小的 distance 对应的参考点坐标作为定位结果。

3 定位实验设置

选取一个 16 m×7 m 的办公区域(图 3)进行实验。我们在该区域布置了 9 个无线信号发射源，使用 MOTO XT702 手机进行训练与测试的工作。

在该区域里共设置 141 个参考点。对于每个参考点，采集 30 条训练指纹，其中 25 条用于训练稀疏字典，5 条用于训练参数。之后选择了图3 两条路径上的 80 个点作为测试点，每个点采集了 20 次指纹作为测试指纹。

最后计算定位结果与实际点的坐标距离作为定位误差。后面将对整个定位区域的定位效果做分析。

4 实验结果与分析

经过实验，本算法在实验区域的平均定位精度达到 2.78 米，结果如图 4 所示。相对于传统的常见算法—KNN 定位算法与高斯模型法，本方法的误差累计分布图表现明显优于两者，平均精度提高 20% 以上。

图4 中，KSR 代表本文提出的算法，CDF为误差累计分布函数(cumulative distribution function)的英文缩写，根据图中的图例，我们可以清晰的区分出三种算法得到的定位误差的表现：本方法的定位结果可以使 80% 的定位点误差都在 4 米左右，而另外两种传统方法则要达到6 米左右，并且本算法中 50% 的定位点定位误差为约 2.5m，而另外两种算法则达到 4 米以上。分析误差出现的原因，主要是由于室内定位环境的复杂性，导致无线信号容易受到干扰或被吸收，导致定位时的无线信号强度包含了一部分噪声。而本文提出的主要想法就是将无线信号强度构成的指纹的主要特征提取出来，利用主要特征进行定位，从而减弱噪声的影响。

从实验结果上看，本文相对于另外两种传统算法，减弱了噪声的影响，并且提高了精度，一定程度上达到了预想的效果。不过本算法还存在改进的空间，如指纹构成的灵活性。

5 结 论

本文提出了一种基于指纹稀疏表示的室内定位算法。通过稀疏表示方法中的低维稀疏字典来将指纹中的高维噪声进行一定程度上的消除。通过降低噪声的影响来提高定位算法的鲁棒性以及对于实际室内环境的抗噪能力。实际环境中的实验表明本文算法较传统算法具有更高的定位精度。

目前本文算法中利用的指纹是由可以接收到的整个空间的所有信号强度构成，在今后的实验中，我们会考虑筛选较为稳定，并且特征较为明显的信号构成定位指纹。并且，由于稀疏表示方法并不要求字典元素之间有严格的比例关系，我们考虑在未来加入除无线网络信号以外的信号来提高定位效果。

[1]Gu YY, Lo A, Niemegeers I. A survey of indoor positioning systems for wireless personal networks[J]. IEEE Communications Surveys and Tutorials,2009, 11(1): 13-32.

[2]Ni LM, Liu YH, Lau YC, et al. LANDMARC: indoor location sensing using active RFID [C]// Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, 2003:407-415.

[3]Chen Y, Lymberopoulos D, Liu J, et al. FM-based indoor localization [C]// Proceedings of the 10th International Conference on Mobile Systems,Applications and Services, 2012: 169-182.

[4]Kaemarungsi K, Krishnamurthy P. Modeling of indoor positioning systems based on location fingerprinting [C]// Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, 2004, 2: 1012-1022.

[5]Baraniuk RG. Compressive sensing [J]. IEEE Signal Processing Magazine, 2007, 24(4): 118-121.

[6]Wright J, Yang AY, Ganesh A, et al. Robust face recognition via sparse representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2): 210-227.

[7]Jolliffe IT. Principal Component Analysis [M].Chichester: John Wiley & Sons, Inc., 2005.

[8]Zhang L, Yang M, Feng XC. Sparse representation or collaborative representation: which helps face recognition? [C]// 2011 IEEE International Conference on Computer Vision, 2011: 471-478.

[9]Tropp JA, Gilbert AC. Signal recovery from random measurements via orthogonal matching pursuit [J].IEEE Transactions on Information Theory, 2007,53(12): 4655-4666.

[10]Gribonval R, Nielsen M. Sparse representations in unions of bases [J]. IEEE Transactions on Information Theory, 2003, 49(12): 3320-3325.

[11]Lawson CL, Hanson RJ. Solving Least Squares Problems [M]. New Jersey, Englewood Cliffs,:Prentice-hall, 1974.