虚拟AP支持的室内非线性约束区域定位

薛卫星，李清泉，周宝定

1. 深圳大学广东省城市空间信息工程重点实验室，广东 深圳 518060； 2. 深圳大学土木与交通工程学院，广东 深圳 518060

位置信息服务[1]已经成为人们日常生活的基础需求。室外环境中，全球导航卫星系统(Global Navigation Satellite System，GNSS)为精确的位置服务提供了保障[2-6]。而当进入室内环境时，信号视距传播难以实现，基于GNSS的室内位置服务变得十分困难。相关研究表明，人们日常生活工作的80%以上是在室内[7-9]进行的，通过智能手机进行导航定位[10-11]已经逐渐成为人们不可或缺的生活方式。对于具有线性约束的室内狭窄区域，如室内走廊或狭窄通道，行人移动方向受到墙体等障碍物约束，只能沿着走廊或通道方向移动而不能横向穿越，使用行为地标和地图辅助的方法[12-17]，定位精度可以得到明显提高。但在开阔的室内非线性约束区域，如办公室或商铺，行人移动方向不受约束，可以向任何平面方向移动，惯性的累积误差无法根据约束进行修正，从而严重影响定位精度，很难使用行为地标和地图辅助的方法进行定位。由于无线信号的非视距传播和多路径传播，基于到达时间、到达时间差和到达角度的室内定位技术同样也遇到了巨大的挑战。而随着智慧城市[18]的建设，Wi-Fi网络快速普及，为基于Wi-Fi的室内定位[19-26]创造了有利条件。

对于非线性约束的室内区域，如何有效提高定位的精度，是技术研究的重点，也是实际应用的基础。具体而言，如何对位置指纹数据库进行聚类分隔，以更合理地反映出指纹点之间的空间几何关系；如何筛选出高质量AP，以显著减少在线定位的计算量并提高定位的精度。

指纹点聚类算法方面。为了减少在线阶段的搜索范围，文献[27—30]提出了基于指纹点聚类的Wi-Fi定位方法。但是，传统的指纹点聚类算法只在离线阶段对指纹点(reference points，RP)的几何邻近性进行分析；而且聚类的个数需要直接或间接地预先定义，用户需要仔细地调整参数以选择合适的聚类的个数，而不合适的聚类个数将会导致定位结果的估计误差。基于指纹点位置的聚类(reference points location clustered，RPLC)算法[28]，只在离线阶段对指纹点的几何邻近性进行聚类分析，聚类结果与在线阶段的测试点无关。而基于信号距离的聚类(signal distance clustered，SDC)算法[29]，仅根据Wi-Fi接收信号强度(received signal strength indication，RSSI)在信号空间的欧氏距离进行指纹点聚类，不考虑指纹点和测试点之间的几何距离。文献[30]利用K均值(K-means)聚类算法[30]提高了K邻近(K nearest neighbor，KNN)算法的性能，但仍然根据RSSI信号空间的距离进行近邻指纹点的选取。然而，RSSI在室内空间传播时，会存在RSSI信号空间的距离近而几何距离远的问题，所以，基于RSSI信号空间距离聚类的方法也可能存在错误选取邻近指纹点的问题。

AP选取算法方面。基于最大均值的AP选取算法[21]选取RSSI平均值最大的AP。但是，RSSI平均值只能在一定程度上反映该AP理论上的信号质量；RSSI平均值大的AP，也可能信号强度起伏较大而导致定位效果不佳。基于位置信息增益(information gain，InfoGain)的AP选取算法[31]选择最具位置辨别力的AP。基于在线互信息(online MI)的AP选取算法[32]采用在线互信息来度量AP之间的集体辨别能力。但是，AP位置识别能力高并不一定代表该AP的RSSI质量高；RSSI质量差的AP，由于信号微弱而更不稳定，可能会导致更多的位置差异。基于主成分分析(principal component analysis，PCA)的AP选取算法[24]采用主成分分析法的方法进行AP选取。但是，在Wi-Fi RSSI非视距传播和多径干扰严重的室内场景中，RSSI信号很可能无法形成主成分。近年来，一些新的AP选择算法被提出[33-36]。基于误差分析的AP选择算法[33]通过对用户定位结果的误差分析选择AP子集用于定位。基于RSSI区间重叠度(interval overlap degree，IOD)的AP选择算法[34]通过对指纹点的几何位置分析来选取AP。基于无须标定(AP selection based calibration-free，ASCF)的AP选择算法[35]选择RSSI差异较大的AP来构建指纹数据库。基于主梯度方向的算法[36]估计了每个AP的主梯度衰减方向。但是，无线信号经过反射、折射或衍射后，AP的传播方向会发生改变。因此，同一个AP在不同区域的衰减方向是不同的。

针对以上问题，本文提出了虚拟AP支持的室内非线性约束区域的定位方法。

1 虚拟AP定位

一般说来，传播模型法需要以不同定位场景的路径衰减因子为基础，而位置指纹法则不考虑路径衰减因子。本文提出的虚拟AP定位，是位置指纹法和传播模型法的综合。虚拟AP定位，首先，需要解决不同定位场景中路径衰减因子简化的问题；然后，借鉴光反射、折射或衍射后形成虚拟光源，计算定位小区域AP的虚拟坐标；以Wi-Fi信号到达定位小区域视距传播前最后一次反射、折射或衍射的地方为起点，计算定位小区域AP的衰减方向；以定位小区域AP的视距传播为依据，采用RSSI计算指纹点和定位点到虚拟AP的几何距离。

1.1 不同定位场景中路径衰减因子的简化

对于传播模型法，为了确定具体定位场景中的路径衰减因子，需要大量的数据采集和处理；而且，某一定位场景中训练得到的路径衰减因子又很难应用到另一个类似的定位场景中。以定位点为中心的定位小区域的室内空间是在同一介质(即空气里，既不在墙里，也不在窗户里)的范围内，因此，本文首先对室内区域进行划分，当将室内区域划分为较小的区域后，定位空间中便只有一种传播介质，在该区域内就可以使用同一个路径衰减因子。

1.2 定位小区域AP的虚拟坐标和衰减方向

根据光的直线传播的定律，在同一种均匀的介质中光线是沿直线方式传播的。而当光线由一种介质传播到另一种介质时，会发生光线的反射和折射；当光线在传播过程中遇到障碍物时，它的传播方式将从该障碍物的缝隙或边界偏离直线传播，形成衍射。光的反射、折射和衍射具有一个共同特点：根据光线的直线传播定律推算出来的光源不是真实的光源，而是虚拟光源。

同样，无线信号在室内环境中传播，一般会经过反射、折射或衍射，然后到达定位小区域。而Wi-Fi信号在定位小区域信号视距传播的起始点，则是其最后一次反射、折射或衍射的地方(也可能是AP的实际位置)。这里，主要研究Wi-Fi信号经过最后一次反射、折射或衍射后，在定位小区域的传播情况。根据定位小区域Wi-Fi信号的视距传播情况，按照无线信号衰减公式和简化后的路径衰减因子推算AP的“虚拟位置”，称为定位小区域AP的虚拟坐标。根据定位小区域Wi-Fi信号的视距传播情况，按照定位小区域临近指纹点的聚类结果推算AP的衰减方向，称为定位小区域AP的衰减方向。接下来，就可以根据定位小区域AP的虚拟坐标进行指纹点的聚类，根据定位小区域AP的衰减方向进行AP的选取。虚拟AP支持的室内非线性约束区域定位流程如图1所示。

图1 虚拟AP支持的室内非线性约束区域定位流程Fig.1 Flowchart of the virtual AP based positioning method

2 基于虚拟AP坐标的指纹点聚类

基于AP虚拟坐标的指纹点聚类算法主要针对无线性约束区域的室内定位，该算法不需要预先设置聚类个数，不仅能实现聚类过程自动化，而且能保证离线阶段聚类方法与在线阶段定位方法的一致性。算法主要包括基于KNN算法的指纹库自检，定位小区域AP虚拟坐标的计算和基于AP虚拟坐标的指纹点聚类3部分。基于KNN算法的指纹库自检是为了获取该房间或大厅内定位误差最小时对应的K值。定位小区域AP虚拟坐标的计算是将简化后的路径衰减因子代入到无线信号衰减公式中来推算每个指纹点对应的AP的虚拟坐标。当路径衰减因子变化时，AP虚拟坐标总是以相同组群的方式同时变化；因此可以基于此组群分类的方式对指纹点进行聚类。

2.1 基于KNN算法的指纹库自检

在同一个非线性约束的室内区域，所有的指纹点依次作为测试点进行定位测试，从身份编号(identity，ID)最小的指纹点开始。所有的指纹点都分配了不同的ID号，并将指纹点ID编号与指纹点位置、AP名称和接收信号强度相关联。需要说明的是，指纹点ID编号的编号方式对算法的聚类结果没有影响，因为每个指纹点都将逐个独立地被作为测试点进行定位测试。此外，文献[37]使用众包的Wi-Fi RSSI数据来识别不同房间的指纹点从而实现了房间级的定位。这里，本文假设不同房间的指纹点已被成功识别，本节提出的聚类算法将主要针对某一房间内的指纹点的聚类。当某一指纹点被视为测试点时，而同一房间内的其他指纹点仍然是指纹点。

首先，设置不同的K值，如K=3、K=4或K=5。对于某一K值，例如，当K=3时，“测试点”的位置用KNN算法逐个估算。然后，得到相应的定位误差统计。对K的其他值，重复该过程。最后，以均方根误差(root mean square error，RMSE)为指标，选择定位误差最小的K值。

2.2 定位小区域AP虚拟坐标的计算

以1号指纹点为例。当RP1作为测试点时，同一房间内的其余指纹点仍作为指纹点使用。根据2.1节中确定的K值，用KNN算法得到该测试点对应的K个邻近指纹点。根据无线信号衰减模型[38]，Wi-Fi RSSI衰减公式为

(1)

式中，RSSI(d0)和RSSI(di)分别是距离AP信号源d0和di处的接收信号强度；η是路径衰减因子。d0和RSSI(d0)一般通过经验建模预先设定，本文中d0取值1 m，RSSI(d0)取值为-20 dB。因此，未知几何距离di可以通过RSSI(di)和η计算得到

(2)

同时，未知几何距离di也可以通过AP信号源的坐标和指纹点的坐标计算得到

(3)

式中，(xj，yj)是第j个AP的虚拟位置(virtual position，VP)；(xi，yi)是第i个RP的位置坐标。这里假设总共有M个AP和N个指纹点。把式(3)代入式(2)，然后把方程两边都平方。由于式(3)的右侧只是距离的估计值，引入用φi(xj,yj)表示的坐标残差

(4)

将路径衰减因子的数值设为固定值，简化无线信号衰减公式；使用这K个邻近指纹点，结合线性最小二乘平差，计算AP的虚拟坐标。对未知坐标参数(xj，yj)分别求偏导，系数矩阵B的元素为

(5)

使用线性最小二乘平差，得到坐标残差平方和并将其最小化

(6)

测试完该室内非线性约束区域内所有N个指纹点后，每个AP可以得到N个虚拟坐标，M个AP就有N×M个虚拟坐标。在同一个房间内，每个指纹点都可以接收房间内所有AP的信号；如果一个AP的信号无法被所有指纹点都接收，则剔除AP。指纹点与所有AP虚拟位置的对应关系见表1。

表1 指纹点与AP虚拟坐标的对应关系

2.3 基于AP虚拟坐标的指纹点聚类

图2为101房间试验点分布示意。由图2中第1列AP1开始，计算虚拟坐标VP11和与剩余N-1个虚拟坐标VPi1之间的距离。如果N-1个距离中的任何一个小于预先定义的阈值，则选择相应的RP，所有选定的RP和RP1都形成一个RP聚类。然后，在未聚类的其余RP中，选择ID号最小的RP(例如RPmid)，并计算VPmid1与剩余RP对应的VPi1之间的距离。同样，将距离小于阈值的VP相应的RP与RPmid形成第2个聚类。重复该过程，直到所有N个RP聚类结束。该过程是自动进行的，聚类的个数不需要预先设置。请注意，到目前为止，只完成了AP1对应的第1列的指纹点的聚类。继续从AP2对应的第2列开始，重复上述聚类过程。直到所有M列都聚类完成为止。

图2 101房间试验点分布示意Fig.2 Schematic diagram of test point distribution in room 101

在完成聚类过程后，将在每个聚类内的所有指纹点的RSSI取平均值，形成一个单独的RSSI，作为该聚类的代表

(7)

3 基于八阵图的AP选取

在室内传播的无线信号，经过墙壁、门窗和室内大型家具等障碍物后会发生反射、折射或衍射现象，其传播方向会发生变化。而在测试点周围的小定位区域内，AP信号可以认为是视距传播，其衰减方向可以通过该测试点邻近指纹点的RSSI信号聚类来计算。这样，同一个AP在房间内不同测试点的AP衰减方向就可能不同，因此，不同测试点的AP子集的选取情况也可能不同，这就是本文方法与传统AP选取算法的主要区别。

八阵图由均匀间隔45°的8个基本方向组成。定位误差可分解为X轴定位误差和Y轴定位误差，通过最小二乘估计可以使X轴和Y轴方向的残差最小。为了严格控制定位误差，本文采用八阵图的8个基本方向的45°间隔为标准，选取定位小区域衰减方向组合最优的4个AP用于在线定位。主要包括定位小区域AP衰减方向的计算和基于八阵图方向组合的AP选取两部分。

3.1 定位小区域AP衰减方向的计算

首先，根据KNN算法选择K个邻近指纹点；然后，用K-means算法对RSSI值聚类，将这K个邻近指纹点聚成两类。最后，用这两个聚类的坐标中心来计算AP的衰减方向。AP衰减方向计算的具体过程如下：

(1) 选择一个AP。

(2) 随机选择两个不相邻的指纹点，取该AP在这两个指纹点处的RSSI(如RSSI1和RSSI2)作为聚类中心。

(3) 计算其余(K-2)指纹点的RSSI值与这两个RSSI中心之间的差值，记为ΔRSSI1i和ΔRSSI2i

(8)

比较ΔRSSI1i和ΔRSSI2i的大小，并将对应的邻近指纹点分配到差值较小的那一类，直到所有邻近指纹点及其RSSI分配完毕；

(4)重新计算并更新聚类中心

(9)

式中，假设第1个聚类中有L1个邻近指纹点；第2个聚类中有L2个邻近指纹点；C1和C2分别是这两个RSSI聚类的聚类中心。

(5) 重复步骤(3)—(4)，直到两个聚类中心不再变化为止。

(10)

(7) 计算该AP的衰减方向

(11)

(8)选择下一个AP并重复步骤(2)—(7)，直到所有M个AP的衰减方向都计算出来。

3.2 基于八阵图方向组合的AP选取

(1)计算每两个AP衰减方向之间的夹角

(12)

第3个轴的方向可以根据这两个轴的方向来初步确定

(13)

(2) 计算其余M-3个AP衰减方向和axis3′之间的差，选取与axis3′差值最小的AP衰减方向作为axis3。同理，根据axis4和axis3的垂直关系来确定axis4

(14)

(3) 选择这4个轴对应的4个AP进行在线定位。

4 试验验证

为了验证基于虚拟AP坐标的指纹点聚类算法和基于八阵图的AP选取算法的性能，分别在武汉大学测绘学院和深圳大学科技楼进行了试验验证。试验分析时，RSSI滤波均采用基于最大平均值的算法[39]对RSSI数据进行预处理，定位计算采用经典的加权K近邻(weighted k nearest neighbor，WKNN)算法。

4.1 基于虚拟AP坐标的指纹点聚类算法定位效果分析

为了验证基于虚拟AP坐标的指纹点聚类算法的性能，在武汉大学测绘学院一楼101房间进行了试验。图2显示了101房间的平面图，定位区域为0.65 m×0.65 m的网格，其中6个AP用三角形表示，63个指纹点用圆点表示。然后在101房间的定位区域内随机选择63个测试点。每个指纹点用1 s的采样率采集RSSI约5 min，每个测试点用0.2 s的采样率采集RSSI 5 s。为了确保一致性，所有数据都是使用同一部手机收集的。为方便起见，在每个房间也建立了独立的坐标系。

4.1.1 不同K值对定位精度的影响

当K值取不同值时，会对定位精度产生影响。为了选择最佳K值，表2显示了不同K值对WKNN算法的定位误差统计，K值范围从2到10。从表2可以看出，当K值从2到10变化时，WKNN定位误差的平均误差和均方根误差RMSE均随K的增大先减小后增大；当K等于5时，RMSE和平均定位误差均为最小值。因此K设为5。

表2 K值从2到10变化时对WKNN算法的定位误差统计

4.1.2 不同路径衰减因子对定位精度的影响

根据式(4)，当路径衰减因子取值不同时，可能会对AP的虚拟坐标产生影响。一般来说，无线信号在空气中的路径衰减因子是2，在有混凝土墙和走廊隔开的办公楼中的路径衰减因子大约是3。表3显示了路径衰减因子范围从2到4变化时对AP的虚拟坐标(以AP1的X坐标为例)的影响。

表3 路径衰减因子从2到4变化时对虚拟AP1的X坐标的影响

由表3可以看出，当路径衰减因子取不同值时，路径衰减因子对AP的虚拟坐标的影响是显著的。然而，当路径衰减因子在2到4之间变化时，AP虚拟坐标总是以相同组群的方式同时变化，因此可以基于此组群分类的方式对相应的指纹点(视为测试点)进行聚类分隔。

4.1.3 定位精度比较

采用位置误差的累积分布函数(cumulative distribution function，CDF)，分析4种不同算法对定位精度的影响，即WKNN算法、指纹点位置聚类算法(RPLC)[28]、信号距离聚类算法(SDC)[29]和基于AP虚拟坐标(virtual AP coordinates，VAPC)的指纹点聚类算法。分别选择了0.3 m、0.5 m、0.8 m、1 m、1.5 m、2 m、2.5 m和3 m等8个不同的位置误差阈值。

由图3所示的结果可以看出，基于AP虚拟坐标的指纹点聚类算法的定位误差也比其他算法小得多。例如，当误差阈值为1 m和2 m，该定位算法的CDF分别为50.79%和93.65%，高于WKNN算法的30.16%和74.60%，RPLC算法的31.75%和69.84%，以及SDC算法的30.16%和71.43%。表4显示了相应的定位误差的统计结果。

图3 4种算法定位精度比较Fig.3 Comparison of location accuracy of four different algorithms

表4 4种算法的定位误差统计

由表4中可以看到，基于AP虚拟坐标的指纹点聚类算法定位结果定位误差的RMSE为0.63 m，优于WKNN算法的0.83 m、RPLC算法的0.94 m和WKNN算法的0.88 m。

4.2 基于八阵图的AP选取算法定位效果分析

为了验证基于八阵图的AP选取算法的性能，在深圳大学科技楼14楼进行了试验，如图4所示。手机接收了超过50个Wi-Fi热点的RSSI数据。科技楼14楼整体建立了指纹点数据库，相邻指纹点间距约为2 m，定位区域内63个测试点采用1 m×1 m格网采用。采用1 s的采样率，每个指纹点采集RSSI约60 s，每个测试点采集RSSI约25 s。

图4 科技楼14楼大厅的试验平面图Fig.4 Floor plan of two halls in the fourteenth floor

4.2.1 不同AP数量对定位精度的影响

为了获得良好的定位性能，需要根据平均定位误差为每种算法选择合适数量的AP个数。图5显示了当AP数量从1到20变化时，北大厅和南大厅中MaxMean、InfoGain、PCA、online MI、IOD和ASCF 6种AP选取算法的平均位置误差。通过对比分析可知，MaxMean、InfoGain、PCA、online MI、IOD和ASCF算法在不同的试验区域中的最优AP数目是不同的(表5)。以PCA算法为例，在2个大厅中最优AP数目分别为11和17。而本文提出的基于八阵图的AP选取算法只需要4个AP，因此在实际应用中具有更好的场景适应性。

表5 6种算法在南北两个大厅最合适的AP个数统计

图5 MaxMean、InfoGain、PCA、online MI、IOD和ASCF算法在不同大厅的平均误差Fig.5 Mean error of MaxMean, InfoGain MaxMean、InfoGain、PCA、online MI、IOD and ASCF in different halls

4.2.2 定位精度比较

分析7种不同算法对定位精度的影响，即MaxMean[20]、InfoGain[31]、PCA[24]、online MI[32]、IOD[34]和ASCF[35]算法和基于八阵图(Eight-Diagram，ED)的AP选取算法。7种算法在南北大厅定位的位置误差CDF如图6所示。由图6所示的结果可以看出，基于八阵图的AP选取算法的性能明显优于其他算法。以北大厅为例，当误差阈值为1 m和2 m时，基于八阵图的AP选取算法的误差CDF分别为50.00%和82.50%，优于MaxMean算法的30.00%和72.50%，InfoGain算法的27.50%和72.50%，PCA算法的22.50%和72.50%，online MI算法的32.50%和80.00%，IOD算法的27.50%和65.00%，以及ASCF算法的20.00%和62.50%。同样，在南大厅，当误差阈值为1 m和2 m时，基于八阵图的AP选取算法的误差CDF分别为35.56%和80.00%，优于MaxMean算法的28.89%和68.89%，InfoGain算法的20.00%和71.11%，PCA算法的22.22%和62.22%，online MI算法的28.89%和80.00%，IOD算法的17.78%和64.44%，以及ASCF算法的22.22%和57.78%。

图6 7种不同AP选取算法定位精度比较Fig.6 Location accuracy comparison of sevendifferent AP selection algorithms

相应的位置误差统计结果见表6。表6所示的北大厅结果表明，基于八阵图的AP选取算法定位结果定位误差的RMSE为1.52 m，优于MaxMean算法的1.82 m、InfoGain算法的1.82 m、PCA算法的1.83 m、online MI算法的1.66 m、IOD算法的1.87 m和ASCF算法的2.15 m。同样，基于八阵图的AP选取算法在南大厅定位结果定位误差的RMSE为1.56 m，优于MaxMean算法的1.94 m、InfoGain算法的1.85 m、PCA算法的2.08 m、online MI算法的1.60 m、IOD算法的1.99 m和ASCF算法的2.20 m。

表6 7种算法的定位误差统计

4.3 虚拟AP支持的室内非线性约束区域定位效果分析

为了验证虚拟AP支持的定位算法在室内非线性约束区域的综合定位性能，将离线阶段的基于虚拟AP坐标的指纹点聚类算法和在线阶段的基于八阵图的AP选取算法用在同一个定位场景进行定位分析。以深圳大学科技楼14楼大厅的两个试验为例，基于虚拟AP坐标的指纹点聚类算法(VAPC)、基于八阵图的AP选取算法(ED)以及二者融合后的算法(VAPC-ED)在南北大厅定位的位置误差CDF如图7所示。从图7所示的结果可以看出，二者融合后算法的性能优于VAPC和ED算法。当误差阈值为1 m和2 m时，二者融合后算法在北大厅的误差CDF分别为80.00%和90.00%，在南大厅的误差CDF分别为64.44%和91.11%，表现出了良好的定位效果。

图7 3种不同算法定位精度比较Fig.7 Location accuracy comparison of three different algorithms

相应的位置误差统计结果见表7。表7所示的北大厅结果表明，融合后的算法定位结果定位误差的RMSE为1.10 m，优于VAPC算法的1.70 m和ED算法的1.52 m。同样，融合后的算法在南大厅定位结果定位误差的RMSE为1.17 m，优于VAPC算法的1.62 m和ED算法的1.56 m。

表7 3种算法的定位误差统计

5 结 论

针对目前室内非线性约束区域的定位精度较低、存在大量冗余AP、无法使用行为地标和室内地图校正等问题，本文提出虚拟AP定位。离线阶段，以定位小区域AP的虚拟坐标为依据，提出一种基于虚拟AP坐标的指纹点聚类算法；算法无须预先设定聚类个数即可实现指纹点聚类的自动化，提高了定位精度并降低了在线阶段指纹匹配的计算量。在线阶段，以定位小区域AP的衰减方向为依据，提出了一种基于八阵图的AP选取算法；算法利用AP方向组合控制约束信息进行AP选取，显著减少在线定位的AP数量，提高了定位精度并降低了用户定位的计算量。虚拟AP支持的两种算法融合后，在室内非线性约束区域表现出了更好的定位效果。从而提高室内非线性约束区域定位的精度和稳健性，促进室内定位技术在行人导航、智能交通及智慧城市等领域的应用。