基于谱回归核判别分析的候机楼室内快速定位算法

丁建立 穆涛 王怀超

摘 要：针对机场候机楼客流量大、室内环境复杂多变的特点，提出了一种基于谱回归核判别分析（SRKDA）的室内定位算法。在离线阶段，采集已知位置的接收信号强度（RSS）数据，使用SRKDA算法提取原始位置指纹（OLF）的非线性特征生成新的特征指纹库;在线阶段，先使用SRKDA对待定位点的RSS数据进行处理，进而使用加权K最近邻（WKNN）算法进行位置估计。定位仿真实验中，在两个不同的定位场景中，所提算法在1.5m定位精度下的误差累积分布函数（CDF）和定位准确率分别达到91.2%和88.25%，相对于核主成分分析法（KPCA）+WKNN模型分别提高了16.7个百分点和18.64个百分点，相对于KDA+WKNN模型分别提高了3.5个百分点和9.07个百分点;在大量离线样本（大于1100条）的情况下，该算法数据处理时间远小于KPCA和KDA。实验结果表明，所提算法能够提高室内定位精度，同時节省了数据处理时间，提高了定位效率。

关键词：谱回归核判别分析;室内定位算法;接收信号强度;位置指纹;非线性特征提取

中图分类号： TP393.17

文献标志码：A

Abstract： Aiming at the characteristics of large passenger flow， complex and variable indoor environment in airport terminals， an indoor positioning algorithm based on Spectral Regression Kernel Discriminant Analysis （SRKDA） was proposed. In the offline phase， the Received Signal Strength （RSS） data of known location was collected， and the non-linear features of the Original Location Fingerprint （OLF） were extracted by SRKDA algorithm to generate a new feature fingerprint database. In the online phase， SRKDA was firstly used to process the RSS data of the point to be positioned， and then Weighted K-Nearest Neighbor （WKNN） algorithm was used to estimate the position. In positioning simulation experiments， the Cumulative Distribution Function （CDF） and positioning accuracies of the proposed algorithm under 1.5m positioning accuracy are 91.2% and 88.25% respectively in two different localization scenarios， which are 16.7 percentage points and 18.64 percentage points higher than those of the Kernel Principal Component Analysis （KPCA）+WKNN model， 3.5 percentage points and and 9.07 percentage points higher than those of the KDA+WKNN model. In the case of a large number of offline samples （more than 1100）， the data processing time of the proposed algorithm is much shorter than that of KPCA and KDA. The experimental results show that， the proposed algorithm can effectively improve the indoor positioning accuracy， save data processing time and enhance the positioning efficiency.

Key words： Spectral Regression Kernel Discriminant Analysis （SRKDA）; indoor positioning algorithm; Received Signal Strength （RSS）; location fingerprint; nonlinear feature extraction

0 引言

随着信息技术的蓬勃发展，人们对基于位置服务（Location-Based Service， LBS）的要求也日益增多，定位应用随之普及。而手机、平板电脑、笔记本电脑甚至以小型无线传感器节点为代表的移动计算终端随着无线通信技术的发展迅速普及，目前已成为互联网最主要的终端设备形态。因此，无线定位技术成为人们关心的兴趣点、工业界的应用重点，以及学术界的研究热点[1]。

机场候机楼是值机托运、安检通行、候机登机等民用航空业务集散交互的大型关键场所。由于机场候机区存在室内环境复杂、人员易走失等问题，严重影响机场的服务质量，因此，面向机场候机楼的室内定位方法研究显得尤为重要。目前对于机场候机楼室内定位[2]的研究较少，并且其中大多是将现有的室内定位方法引入到候机楼环境中，没有抽取出候机楼的特点。在候机楼环境中，由于人流量较大、定位环境复杂，旅客对于定位的需求较大，因此需要一种针对候机楼复杂环境的快速定位方法。

在室内环境中，由于无线局域网（Wireless Local Area Network， WLAN）技术的广泛应用，以及其布设简单、价格低廉等优点，所以基于WLAN的定位方法更加适用于室内环境。基于WLAN的室内定位方法包括基于测距模型[3]的定位方法和基于位置指纹模型的定位方法，其中，基于位置指纹模型的定位方法由于其定位精度更高，成为了主流方法和研究热点。基于Wi-Fi信号的指纹定位方法主要包括基于接收信号强度（Received Signal Strength， RSS）指纹[4-5]的定位方法、基于信道冲击响应（Channel Impulse Response， CIR）指纹[6-7]的定位方法等。由于基于信道冲击响应的指纹定位方法需要特殊设备，所以现在更多的是基于RSS的定位方法。基于RSS位置指纹定位模型如图1所示。

传统的基于位置指纹的定位模型，其定位精度很大程度上取决于离线数据和在线所采集的数据是否属于同一个分布模型。而在实际的室内WLAN 环境中，往往所采集到的数据与理想情况有出入，在离线采集的来自各个无线访问接入点（Access Point， AP）的RSS信号复杂多变，进而影响室内定位算法的精度。

针对上述的问题，Bahl 等[8]提出了使用K最近邻（K-Nearest Neighbors， KNN）算法进行定位，该算法使用KNN将在线采集数据与指纹数据库匹配，将获得的结果作为目标的位置。该算法有一个缺点，在定位时，不考虑RSS数据受干扰的情况，在实际的室内环境中，由于RSS数据的复杂多变，这种定位方法会增加定位误差。

Zhang 等[9]提出了使用核判别分析（Kernel Discriminant Analysis， KDA）-KNN的Wi-Fi定位算法，该算法在离线阶段使用KDA变换对离线位置指纹进行训练，在在线阶段使用KNN进行位置预测。与KNN及其改进算法相比，该算法有效提高了定位精度，但是由于KDA变换所需时间较多，导致定位效率低下。

李华亮等[10]提出一种基于核主成分分析法（Kernel Principal Component Analysis， KPCA）的室内定位算法。该算法在离线阶段时使用KPCA训练位置指纹数据，在在线阶段提出了一种改进K近邻算法进行位置预测。由于KPCA算法的无监督特性，其定位性能相比KDA较差，且定位效率低。

针对机场候机楼客流量大、室内环境复杂多变的特点，本文提出一种基于谱回归KDA（Spectral Regression KDA， SRKDA）[11]的室内定位算法。在离线阶段，使用SRKDA方法训练位置指纹数据，KDA方法可以有效提取数据间非线性特征，而SRKDA是将KDA代入到谱回归（Spectral Regression， SR）的回归框架中，降低了时间复杂度，并且可以引入L1、L2范数，提高泛化能力;在在线阶段，使用加权KNN（Weighted KNN， WKNN）算法进行位置估计。本文算法使用的RSS 数据来自真实WLAN 环境，实验结果表明该算法优于其他几种WLAN环境下的室内定位算法。

1 SRKDA

线性判别分析（Linear Discriminant Analysis， LDA）是一种分类算法。LDA通过对历史數据进行投影，以保证投影后同一类别的数据尽量靠近，不同类别的数据尽量分开，投影向量通常通过最大化类间协方差矩阵同时最小化类内协方差矩阵来获得。LDA是一种监督学习的降维技术，而主成分分析法（Principal Component Analysis， PCA）是不考虑样本类别输出的无监督降维技术。

KDA方法通过非线性映射函数将原始空间映射到特征空间F上，在特征空间进行LDA，这里的非线性映射函数采用核方法。核方法是一系列数据处理方法的总称，它们的共同特征都是采用核函数进行映射。通过使用核方法，可以使在低维空间不可分的数据在高维空间中实现可分。

SR是一种用于高效正则子空间学习的新型回归框架。SR将嵌入函数学习问题转化为回归框架，避免了稠密矩阵的特征分解。随着回归作为构建模块，各种正则化技术可以很容易地纳入到SR中，这使得它更加灵活，泛化能力更强。

SRKDA是在KDA的基础上引入SR方法，通过使用谱图分析，SRKDA将判别分析转化为回归框架，该框架有助于高效计算和正则化技术的使用。具体来说，SRKDA只需要解决一组正则化回归的问题，并且不涉及特征向量计算，有效节省了计算成本。

2 基于SRKDA的室内快速定位方法

针对候机楼这种复杂定位环境，本文提出了一种基于SRKDA的快速室内定位算法，定位流程如图2所示。定位流程分为离线和在线两个阶段。离线阶段主要是进行位置指纹数据的采集以及建立指纹库，为在线阶段作数据准备;在线阶段通过相应的匹配算法将获取的指纹数据与离线阶段建立的指纹库作匹配，查找待定位节点的指纹所对应的物理位置信息，以估计待定位节点位置。使用KDA方法进行数据处理可以解决候机楼定位环境复杂、RSS信号波动大这一问题;而在KDA基础上引入SR框架可以解决候机楼客流量大、定位需求多时定位效率低下的问题。在候机楼待定位区域布置N个参考节点（Reference Point， RP），每个参考节点的物理位置已知，为li（xi，yi），所有参考节点的物理位置信息共同构成位置空间L=（l1，l2，…，lN）T。在离线阶段，在各个参考节点上采集到n个非视距AP的RSS信号及媒体访问控制（Media Access Control， MAC）地址信息（MAC 作为不同AP 的标识），在每个参考节点上都要进行p次采集，将RSS信息和该点的物理位置信息作为这个参考节点li（xi，yi）的原始位置指纹信息，这个原始位置指纹信息是一个n维向量Xi=（rss1，rss2，…，rssn）T，i∈（1，N），将全部参考节点的原始位置指纹信息存储在相关数据库中，构成一个N×n维的原始位置指纹空间X（X=（X1，X2，…，XN）T），矩阵X中的每个行向量代表一个参考节点的原始位置指纹向量。通过SRKDA方法，提取原始位置指纹数据的定位特征，这些定位特征构成特征位置指纹空间X′= （X′1，X′2，…，X′N）T，X′与L相对应，即X′i是li（xi，yi）的特征位置指纹。在在线阶段，在测试节点（Test Point， TP）采集各个AP 的实时RSS 信号，构成在线指纹向量Y，对Y进行SRKDA处理，得到在线特征指纹向量Y′，使用WKNN方法估计出位置。

2.2 WKNN位置估计

本文算法在离线阶段使用SRKDA对原始位置指纹进行处理生成特征指纹库，并生成模型;在在线阶段，使用该模型对在线获取的信息进行处理，然后使用WKNN的方法将处理后的在线数据与特征指纹库中的数据进行匹配。

2.3 算法的时间复杂度分析

本文算法的时间复杂度主要包括SRKDA算法的时间复杂度以及WKNN算法的时间复杂度两部分。WKNN算法时间复杂度为O（Nm），其中m为TP数量。而SRKDA算法运算量主要包括以下几个方面：首先是施密特正交化，运算量为Nc2-c3/3次;其次是Cholesky分解法，运算量为N3/6次;然后是求解c-1线性方程，运算量为N2c次;最后是计算核矩阵需要O（N2n）次运算量。因此SRKDA算法运算量为N3/6+N2c+O（N2n）+Nc2-c3/3次，由于Nc，可以简化为N3/6+N2c+O（N2n）次。由于N>n，N>m，Nc，因此本文所提算法时间复杂度为O（N3）。

3 实验结果与仿真分析

3.1 实验设置

通过仿真的形式对所提的定位算法进行了实验分析，所使用的数据来源于真实的环境，数据采集实验在天津滨海国际机场T2航站楼出发层进行。综合考虑诸多因素，选择航站楼出发层的一块休息区作为实验区域。从采集的数据来看，在这个休息区内，在同一位置的多次数据采集由于人员走动的影响波动很大。在这个环境下采集的RSS 数据可以有效地表明本文算法的性能，相比于目前大多数的室内定位方法更加贴合实际，其地形如图3所示。每隔1m取一个RP，共计10个参考节点，作为RP分布，如图3中圆点所示;又在实验区域选择10个位置点，作为TP分布，如图3中星点所示，TP 的实际位置已知。在线定位时，实时采集各个TP上来自各个AP 的RSS 信号，构成在线位置指纹，通过定位算法得到TP的估计位置，将TP的估计位置与TP 的实际位置进行比较，来评价定位算法的性能。

借助机场现有的WLAN 基础设施，在移动过程中，共可以在数据采集实验区域检测到122个AP，所有AP 在数据采集区域内都是非视距的，实验中忽略了AP 位置因素以及AP硬件对算法的影响;RSS信号采集的终端设备使用华为Mate7手机，处理器为四核1.8GHz，操作系统EMUI 3.0，每个参考节点和测试节点的RSS 数据都是连续采集100次，得到原始位置指纹数据，部分数据如表1所示。表1 中的数据为原始位置指纹，一般情况下可以直接用来定位;由于空间有限，表1只列出部分位置来自前6个AP的RSS数据。

将原始位置指纹经过SRKDA处理，高斯核宽度按照经验设置为1。原始位置指纹数据库中的数据为设备的RSS 值，KDA 是一个非线性过程，变换后的数据便不具有实际的物理意义，仅作为特征位置指纹数据使用。

定位算法的软件环境为Matlab 2016a， Windows 10，硬件环境为 Intel Xeon E3-1231v3 3.4GHz CPU，8GB內存的PC。

实验采用平均误差（Mean Error， ME）、定位准确率和误差的累积分布函数（Cumulative Distribution Function， CDF）为标准来比较4 种算法SRKDA、WKNN、KDA与KPCA，由于在室内环境中一般以1.5m就能区分待定位目标，所以认为1.5m为可接受误差，本实验中的定位准确率即在1.5m误差范围内的定位准确率。

3.2 岭回归参数对定位准确率的影响

在实验中，SRKDA所选择的回归框架是岭回归，岭回归是一种专用于共线性数据分析的有偏估计回归方法，实质上是一种改良的最小二乘估计法，通过放弃最小二乘法的无偏性，来获得更可靠的回归系数。采用岭回归这种回归框架可以有效防止过拟合的发生，提高模型的泛化能力。在应用岭回归的过程中，参数选择是很重要的一步，图4是岭回归参数对定位准确率的影响，图中横轴是参数的大小，参数选择从10-5到105，纵轴是在误差距离为1.5m内（精度1.5m下）的定位准确率。

3.3 不同定位场景下的定位准确率

为了验证本文算法的鲁棒性，本文在图3中4个不同定位场景中进行实验，通过对比各算法在不同场景中的定位准确率，来验证本文所提算法在不同场景中的定位性能。本实验在取所有离线样本数量和AP数量的情况下，验证不同场景下不同定位算法的定位准确率，结果如表2所示。

从表2可以看出，在4个定位场景中，虽然不同场景下各算法的定位准确率变化各不相同，但是相比于其他算法，本文所提SRKDA+WKNN定位算法在4个场景中的定位性能更优，表明本文所提算法的鲁棒性更好。由于空间有限，不能列举所有场景下的实验，因此以下实验均在场景一下进行。

3.4 离线样本数量对定位准确率的影响

在指纹定位算法中，离线样本数量会对算法性能产生重大影响，离线样本数量代表离线阶段采集的数据量。它反映了离线阶段采集数据的时间消耗，而离线数据采集往往耗费大量时间，因此有必要比较不同离线样本数量对定位准确率的影响。离线样本数量对定位准确率的影响如图5所示，图中反映了样本数量从100到1000变化的过程中各算法的定位准确率。

从图5可以看出，随着离线样本数量的变化，各定位算法准确率皆有所提升，其中本文算法在定位准确率方面优于其他算法，并且本文算法在样本数量为700时就能得到较高准确率，而其他算法想要得到同样的准确率需要更多离线样本。

3.5 AP数量对平均误差的影响

在指纹定位算法中，由于主要依靠RSS数据来进行定位，而RSS数据的维度也就是AP的数量是一个影响定位性能的重要参数，显然，AP数量越多，定位效果越好。本文按照表1中的数据依次选取前n个AP对应的RSS数据作为参数。在这个实验中，取AP数量从10到120变化区间，用平均误差来验证算法的性能。

从图6中可以看出，本文算法在同样的平均误差下所需的AP数量更少，并且当AP数量达到120时，本文算法定位的平均误差达到0.783m，优于其他算法。

3.6 误差的CDF曲线

CDF又叫分布函数，是概率密度函数的积分，能完整描述一个实随机变量的概率分布。在众多室内定位论文中，误差CDF曲线都作为验证算法优劣的重要指标。在这个实验中，采用完整的离线样本以及来自所有AP的RSS数据，来验证各算法在实际环境中定位的效果优劣，各算法的CDF曲线如图7所示。

从图7中可以很明显看出，在1.5m的精度下，本文算法所对应的CDF为91.2%，优于KDA+WKNN的87.7%、KPCA+WKNN的74.5%、WKNN的66.1%，以及KNN的59.8%。

3.7 不同算法在其他环境中的定位性能比较

通过以上实验可以看出，本文算法在上述环境中，定位性能优于其他算法。为了验证本文算法在其他环境中的定位性能，第二组实验采用文献[12]的数据集，该数据集被多篇论文引用，是一个比较权威的数据集，在该数据集上进行实验更能说明算法的优劣;同时该数据集也是在真实环境中采集的数据，所以数据更有说明性。该数据集包括训练集14300条，测试集5060条，在该数据集上使用SRKDA算法更能体现出其计算上的优越性，极大地节省了计算时间。离线样本数量对数据处理时间的影响如图8所示，离线样本数量对定位准确率的影响如图9所示。

横轴代表图8中，每组离线样本有110条数据，当组数达到130，也就是离线样本数量达到14300条时，SRKDA处理时间为21.13s，远小于KPCA的190.61s、KDA的302.75s。从图8中可以看出，SRKDA在对数据处理时能够有效节省处理时间。而图9从误差为1.5m的定位准确率方面验证了本文算法的定位性能优于其他算法。从图9可以看出，在误差为1.5m下这两处的描述不妥当，如何从图9看出来？请调整语句描述。误差从哪里可以看出来？是图错了，还是描述错了，请作相应调整。

回复：现向您解释如下：由于在3.1實验设置部分最后说明了1.5m为可接受误差，本文实验中的定位准确率都是在1.5m误差范围内的定位准确率，因此在描述图9中的定位准确率时，用到了误差1.5m这一条件。

4 结语

针对候机楼这种复杂定位环境，本文提出了一种基于SRKDA的室内定位算法。该算法在离线阶段使用SRKDA训练原始指纹数据，提取原始位置指纹的非线性特征，作为新的位置指纹数据库，同时生成一个模型;在线阶段，使用该模型对在线数据进行处理，然后使用WKNN方法将在线数据与指纹数据库中的数据作匹配进行位置估计。实验结果表明，本文所提的算法优于其他几种对算法，降低了平均误差，提高了定位准确率，同时减少了数据的处理时间，提高了定位效率。但是本文在实验过程中未考虑AP部署的位置对信号的影响，对于不同AP部署位置环境下的定位情形有待下一步解决。

参考文献 （References）

[1] LIU Y H， YANG Z， WANG X P， et al. Location， localization， and localizability [J]. Journal of Computer Science and Technology， 2010， 25（2）： 274-297.

[2] 王续乔，王瑾琨.基于D-S证据理论的室内组合定位算法[J].计算机应用，2017，37（4）：1198-1201.（WANG X Q ，WANG J K. Integrated indoor positioning algorithm based on D-S evidence theory [J]. Journal of Computer Applications， 2017， 37（4）： 1198-1201.）

[3] CHIPUTA M， LI X Y. Real time Wi-Fi indoor positioning system based on RSSI measurements： a distributed load approach with the fusion of three positioning algorithms [J]. Wireless Personal Communications， 2018， 99（1）： 67-83.

[4] ABUSARA A， HASSAN M S， ISMAIL M H. RSS fingerprints dimensionality reduction in WLAN-based indoor positioning [C]// Proceedings of the 2016 Wireless Telecommunications Symposium. Piscataway， NJ： IEEE， 2016： 1-6.

[5] ETEMADYRAD N， NELSON J K. A sequential detection approach to indoor positioning using RSS-based fingerprinting [C]// Proceedings of the 2016 Global Conference on Signal and Information Processing. Piscataway， NJ： IEEE， 2016： 1127-1131.

[6] CHEN C， CHEN Y， LAI H Q， et al. High accuracy indoor localization： a WiFi-based approach [C]// Proceedings of the 2016 IEEE International Conference on Acoustics， Speech and Signal Processing. Piscataway， NJ： IEEE， 2016： 6245-6249.

[7] LIN Y P， TSENG P H， FENG K T. Compressive sensing based location estimation using channel impulse response measurements [C]// Proceedings of the IEEE 25th Annual International Symposium on Personal， Indoor， and Mobile Radio Communication. Piscataway， NJ： IEEE， 2015： 2066-2070.

[8] BAHL P， PADMANABHAN V N. RADAR： an in-building RF-based user location and tracking system [C]// Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway， NJ ： IEEE， 2000： 775-784.

[9] ZHANG M， SHEN W B， ZHU J H. WIFI and magnetic fingerprint positioning algorithm based on KDA-KNN [C]// Proceedings of the 2016 Chinese Control and Decision Conference. Piscataway， NJ ： IEEE， 2016： 5409-5415.

[10] 李華亮，钱志鸿，田洪亮.基于核函数特征提取的室内定位算法研究[J].通信学报，2017，38（1）：158-167.（ LI H L， QIAN Z H， TIAN H L. Research on indoor localization algorithm based on kernel principal component analysis [J]. Journal on Communications， 2017， 38（1）： 158-167.）

[11] CAI D， HE X F， HAN J W. Speed up kernel discriminant analysis [J]. The VLDB Journal， 2011， 20（1）： 21-33.

[12] KING T， HAENSELMANN T， EFFELSBERG W. On-demand fingerprint selection for 802.11-based positioning systems [C]// Proceedings of the 2008 International Symposium on a World of Wireless， Mobile and Multimedia Networks. Piscataway， NJ ： IEEE， 2008： 1-8.

[13] 田洪亮，钱志鸿，梁潇，等.离散度WKNN位置指纹Wi-Fi定位算法[J].哈尔滨工业大学学报，2017，49（5）：94-99.（TIAN H L， QIAN Z H， LIANG X， et al. Discrete degree WKNN location fingerprinting algorithm based on Wi-Fi [J]. Journal of Harbin Institute of Technology， 2017， 49（5）： 94-99.）

[14] TORTEEKA P， XIU C. Indoor positioning based on Wi-Fi fingerprint technique using fuzzy K-nearest neighbor[C]// Proceedings of the  2014 International Bhurban Conference on Applied Sciences and Technology. Piscataway， NJ ： IEEE， 2014：461-465.

[15] GE X， QU Z. Optimization WIFI indoor positioning KNN algorithm location-based fingerprint [C]// Proceedings of the 2017 IEEE International Conference on Software Engineering and Service Science. Piscataway， NJ： IEEE， 2017： 135-137.