基于自适应修正曼哈顿距离的室内定位方法

陈亦奇，周 蓉，滕 婧，周洪波，栾泉中

(华北电力大学控制与计算机工程学院，北京 102206)

0 引言

无线通信和移动设备的激增为室内定位服务(Location-Based Services，LBS)带来了广泛的应用前景。然而，与已经通过全球定位系统(Global Positioning System，GPS)完美解决的室外定位问题不同，室内定位的挑战在于非视距(Non-Line of Sight，NLOS)问题，即由于屋顶、墙壁和一些其他障碍物的存在，GPS信号容易衰减或受到屏蔽使得GPS定位不再可靠。目前，实现高精度的室内定位已经成为定位领域的研究热点，在现有的诸多室内定位方法中，由于WiFi接入点(Access Point，AP)的广泛部署和无处不在的智能设备(如智能手机、平板和笔记本电脑)，基于WiFi 指纹的室内定位方法成为了最易于实现的室内定位方法[1]。除此之外，指纹定位方法还具有以下优点：无需额外的硬件辅助，定位精度高，定位成本低，适用于不同的室内环境[2]。指纹定位算法包括2个阶段：离线训练阶段和在线定位阶段。主要思想是将在线定位阶段采集到的测试点(Test Point，TP)指纹与离线训练阶段生成的指纹库中各参考点(Reference Point，RP)指纹进行匹配，根据指纹匹配结果预测TP的位置坐标。目前，这2个阶段的研究方向主要在于：更可靠的指纹特征值、更便捷的指纹库构建和更准确的指纹匹配[3]，本文着重于实现最后一项。

常见的指纹匹配算法通过计算指纹在信号空间内的欧氏距离来实现，欧氏距离越小，则指纹相似度越高，指纹在物理空间中的距离越近。一般情况下，指纹间的所有接收信号强度(Received Signal Strength，RSS)差值，无论大小均会被用于计算欧氏距离。但在实际环境下，即使在相同条件下，在同一位置，间隔很短一段时间采集的信号也具有波动性。这种波动性体现在RSS的持续变化上，通常由于采集时间、采集设备和环境的变化而导致。因此指纹间部分较小的RSS差值并不一定能反映指纹的不同，反而可能是信号波动性的结果。通常的处理方式是对RSS做均值滤波，但均值滤波后的RSS会损失一部分的信息，从而对定位精度产生影响。Fang给出的处理方案是将信号波动转化为在信号强度对数域中的一个附加随机变量，但实际上的信号波动并不是非常契合该模型，处理后的定位精度不佳[4]。Zhuang提出了基于拥有不变性的信号强度阶代替RSS作为指纹匹配的特征，从而规避了信号波动的影响[5]。其他WiFi指纹定位算法都忽略了信号的波动性及其对定位精度的影响。

针对该问题，本文提出了自适应修正算法来处理信号波动，并根据自适应修正后的曼哈顿距离进行指纹匹配。首先，根据AP选择算法降低了指纹维度，仅选用可靠AP对应的RSS；然后，在理论分析信号传播衰减公式和信号波动后，提出了基于自适应修正曼哈顿距离(Adaptive Correction Manhattan Distance，ACMD)计算指纹相似度的匹配算法；最后，结合加权K近邻(Weighted K Nearest Neighbor，WKNN)方法实现定位。在开放室内定位数据集Zenodo[6]上进行定位实验，结果表明，在WKNN框架下，基于ACMD的指纹匹配算法在定位精度上优于基于欧氏距离(Euclidean Distance，ED)、曼哈顿距离(Manhattan Distance，MD)、余弦距离(Cosine Distance，COSD)和Sorensen距离(Sorensen Distance，SD)的指纹匹配算法。

1 相关工作

1.1 指纹定位原理

指纹定位算法通过计算TP和RP指纹之间的相似度，得到一组与TP相似度较高的RP集合，然后基于集合中RP的坐标加权估计TP的坐标。如图1所示，该算法分为2个阶段：离线训练阶段和在线定位阶段。

图1 指纹定位算法流程图Fig.1 Flow chart of fingerprint positioning algorithm

指纹由一组采集到的不同AP的RSS组成，根据采集阶段的不同，指纹分为TP指纹和RP指纹。TP指纹在在线定位阶段测得，用于估计TP的位置坐标；而RP指纹在离线训练阶段测得，存储在数据库中，与坐标一起构成指纹数据库，起预定义参照标准的作用。

离线训练阶段的任务是构建指纹数据库，指纹数据库由预设RP点物理空间坐标和该RP点的指纹组成。RSS易受环境变化、行人走动或障碍物的影响，因此在训练阶段，通常在各个RP点进行多次RSS的采集以构建鲁棒的指纹库。假设RSSAPi(RPj)代表设备在RPj处采集到APi的RSS，AP总数为n，RP总数为m，指纹库FPDB以矩阵形式保存，如式(1)所示

FPDB=

(1)

在线定位阶段的任务是将在TP点采集的指纹与指纹库中不同RP点的指纹进行匹配，并根据匹配结果估计TP点位置以实现定位。在线定位阶段在TP点采集的指纹如式(2)所示

(2)

1.2 指纹匹配算法

常见的指纹匹配算法大多是基于KNN类的确定性算法，这类算法使用RSS均值或最大值作为信号特征。KNN算法由Bahl和Padmanabhan首次引入到室内定位中，通过在指纹空间中找到与TP欧氏距离最小的K个 RP，计算K个RP的平均坐标作为TP的预测坐标[7]。WKNN方法是对KNN算法的改进，基于K个RP与TP的欧氏距离分别赋予这K个RP相应的权重，并根据各RP的权重对坐标加权实现定位。其中权重通常取欧氏距离的倒数，Chen基于方差的加权距离改进WKNN算法，改善了该算法在信号波动幅度较大时的定位精度[8]。KNN类的匹配算法实现简单，定位精度较高，因此其应用范围很广。但是也有着如下几种问题：首先，算法使用RSS均值或最大值来表示WiFi的信号强度，这种简化会导致误差；其次，在信号空间内K个拥有最小欧氏距离的RP并不一定就是在物理空间内与TP距离最小的K个RP。

除了基于KNN类的确定性匹配算法之外，还有基于信号强度分布的概率性匹配算法，该类方法将信号强度的概率分布作为特征。Zhou将指纹数据库与物理近邻数据库相结合，根据2次使用贝叶斯推论选择拥有最大先验概率的RP实现定位[9]。Campos通过组合无监督聚类和多表决反向传播神经网络构建室内定位模型，提高了在跨越楼层的室内环境下的定位精度[10]。Calderoni结合RFID技术和随机森林分类，提出了一种能够抵御环境因素影响的定位系统，已经在部分印度医院投入使用[11]。概率性匹配算法相比确定性匹配算法避免了使用RSS均值导致的误差，但也存在模型训练时间长、需要样本数据量大的缺点[12]。

在基于KNN类的大多数指纹匹配算法中仅出现一些常见的度量距离，如欧氏距离、曼哈顿距离和马氏距离。Xie根据在同一位置采集的RSS大小排序基本稳定这一现象，使用斯皮尔曼距离匹配指纹[13]。Liu提出的M-WKNN方法是基于聚类指纹及改进WKNN的方法，采用一种指数函数方式衡量指纹间的相似度及指纹的权重[14]。Han针对信号采集设备不同这一问题，提出了基于余弦距离匹配指纹[15]。苗云龙等将指纹转换为包含32位16进制表示的MD5序列，在指纹匹配时直接匹配MD5序列[16]。Torres-Sospedra同样对不同的指纹匹配距离进行了比较，并在KNN框架下进行了定位比较，实验结果表明，欧氏距离并非指纹匹配的最佳距离，基于Sorensen距离的匹配算法定位精度最高[17]。

2 算法描述

2.1 数据预处理

为了建立鲁棒的指纹数据库，需要先对RSS组进行预处理，剔除异常数据和粗大误差。

假设向量rss是在RPj上收集到来自APi的连续p次测量的RSS，如式(3)所示

(3)

(4)

(5)

再计算残差的均方根误差σ，如式(6)所示

(6)

2.2 AP选择

在理想环境下，指纹定位的精度会随着定位所使用AP数量的增加而持续升高。然而，在实际环境下，任何AP发出的信号都会受到障碍物和多径效应的影响，不经筛选地使用所有AP不仅不会提高定位精度反而还会增加额外的计算负担。因此，为了在提高定位精度的同时减少计算负担，挑选出受干扰程度小和出现频率高的AP参与指纹匹配是一种可行的方案。

在稳定的室内环境下，使用RSS均值做信号特征的定位精度不如使用RSS最大值做信号特征的定位精度[18]。同时较大的RSS也意味着信号接收装置与AP间的距离较小，信号受到多径效应的干扰程度也较小。所以信号的受干扰程度指标M(APi)RPj与在RPj处接收到APi的最大RSS值maxAPi(RPj)相关，如式(7)所示

(7)

其中，U是未接收到信号对应的预设RSS，通常取-105dBm，M(APi)RPj越大，RPj处的APi就越可靠。

在离线训练阶段的一个采样周期中，假设在RPj处某一AP的信号出现频率较高，则在在线定位阶段中在RPj处也会有较大概率接收到该AP的信号。如式(8)所示，信号的出现频率指标P(APi)RPj用于表示在离线阶段的一个采样周期中，在RPj处接收到APi信号的出现频率

(8)

对于一个采样周期来说，SRPj是在RPj处信号采集的总次数，pAPi(RPj)是在RPj处接收到APi信号的次数，ε是一个极小的正数，避免分母为0。P(APi)RPj越大，对应的APi在RPj处出现的频率越高，也相应越可靠。

AP选择算法的标准R(APi)RPj由上述2个指标综合而得，反映了APi在RPj处的可靠程度，如式(9)所示

R(APi)RPj=M(APi)RPj×P(APi)RPj

(9)

基于AP的可靠程度对RPj处所有AP(下标为1～n)进行排序，保存可靠度最高的前L个AP的集合。在TP指纹与RPj指纹进行匹配时，仅使用RPj对应的L个可靠AP(下标为L1～LL)，过程如图2所示。与普通的AP选择算法所不同的是，该算法会在各RP处给出相对应的优选AP集合，根据RP对应的AP集合进行指纹匹配，匹配结果更为可靠。

图2 基于AP选择处理指纹的示意图 Fig.2 Schematic diagram of modified fingerprint based on AP selection

2.3 相似度度量

在指纹匹配算法介绍中提到，常见算法的相似度度量距离是欧氏距离，但欧氏距离并非用于指纹匹配的最佳度量距离。WiFi信号强度衰减模型如式(10)所示[19]

(10)

其中，RSSd是距离WiFi接入点距离为d的信号采集点处采集到的RSS，η是路径损耗参数,X代表由采集设备、时间或者环境不同引起的RSS波动。由于d0、RSS(d0)、η均为预设模型参数，在采集到RSS(di)后，根据式(10)可以计算出WiFi接入点到信号采集点之间的未知距离di,如式(11)所示

(11)

对于同一个AP、RP和TP之间的物理距离Δd与RP和TP采集到的RSS差值成正相关，如式(12)所示

Δd=d(RP)(APi)-d(TP)(APi)

∝RSSd(RP)(APi)-RSSd(TP)(APi)+X(X1,X2)

(12)

由于WiFi信号差值与它们之间的物理距离正相关，因此，可以基于同一AP的RP和TP之间的RSS差来估计它们之间的物理距离，这是使用曼哈顿距离来进行指纹匹配的理论基础。X(X1,X2)代表联合信号波动，下面引入自适应修正对信号波动进行处理。

2.4 自适应修正

在常见的指纹匹配方法中，指纹间的所有RSS差值无论大小均会被用于计算指纹的相似度。然而，即使是在相同位置连续采集的RSS也会持续变化，本文将这种RSS的持续变化称为RSS波动。因此在指纹匹配时，指纹间的RSS差值应包含实际的RSS差异和RSS波动，部分较小的RSS差值可能完全是RSS波动的结果。RSS波动如图3所示，若没有接收到某AP的信号，则将该AP对应的RSS记作-105dBm。

(a)

(b)

图3(a)和图3(b)分别代表了2个不同位置的情况，DATA1代表从某一位置采集到40个AP的RSS，DATA2代表间隔2s后在与DATA1相同条件下采集到的RSS，绘制在每张图顶部的RSS-DIFF代表DATA1与DATA2的RSS绝对差值，用于反映RSS的波动。根据图3可以观察到，即使在相同位置间隔极短时间采集的RSS也会有最大10dBm左右的波动，随着信号强度的衰减，波动的频率和最大值也逐渐增大。该现象的原因是RSS越小意味着采集设备距离AP越远，RSS受到环境内障碍物和信号多径传播效应的影响也越大，若对该种波动不加以处理会影响指纹匹配的结果。

通过上面的分析，本文提出了使用自适应修正的方式处理在不同RSS大小下的RSS波动，下文提及的RSS差值均指差值的绝对值。修正的含义是给予指纹匹配时的RSS差值一个波动上限T，当RSS差值小于等于波动上限时，认为该RSS差值是RSS波动的结果，并将该RSS差值置为0；当RSS差值大于波动上限时，认为该RSS差值代表了指纹的差异，将该RSS差值减去波动上限后保留。具体的规则如式(13)所示

(13)

其中，diff代表初始RSS差值，T代表波动上限，c_diff代表修正后的RSS差值。

之前的研究表明，RSS波动更容易在距离AP较远的位置出现，且波动的范围也更大。因此，引入自适应函数A对各RSS值对应的波动上限T做相应的调整,该过程在离线训练阶段实现，不会影响定位的实时性，具体如式(14)所示

ATAPi(RPj)=A(RSSAPi(RPj))·T

(14)

其中，ATAPi(RPj)是指纹库中信号强度RSSAPi(RPj)对应的波动上限，自适应函数A的实现如式(15)和式(16)

(15)

(16)

其中，U是未接收到信号对应的信号强度，通常取-105dBm，all_rss以矩阵形式存储了经过式(15)变换后的所有rss，底数α用于改变自适应系数的变化范围。某位置的RSS值越大，意味着该位置距离AP越近，出现波动的可能性和波动的变化范围越小，因此波动上限T也越小，对RSS波动的界定也越严格，修正程度也更小。自适应修正RSS差值的规则与修正RSS差值的规则类似，如式(17)所示

(17)

其中，AT代表自适应的波动上限。

此外，RSS的数值实际上表示接收信号功率Power与1mW参考功率之间的比例，如式(18)所示

(18)

在不同的信号强度下，信号强度差与信号功率差不适合用线性关系来转化。举例来说，信号强度-50dBm与-60dBm之间的信号功率差是9×10-6mW，信号强度-90dBm与-100dBm之间的信号功率差是9×10-10mW;然而在现有的指纹定位算法中，上面2组信号的RSS差值被认为是相同的10dBm，实际上2组信号的功率差相差整整104倍，仅靠RSS差值计算指纹相似度无疑会引入误差。因此，设置RSS差值的调整函数M，基于信号强度给予RSS差值相应的调整系数，M函数通过式(19)获得

(19)

通过M函数调整RSS差值，使得较大信号强度对应的RSS差值在指纹相似度计算的过程中具有更大的系数，但调整系数的变化范围同样不宜设置过大，避免破坏指纹数据的真实性，影响指纹匹配的结果。

综上所述，首先采用自适应修正的方式解决指纹匹配中的信号波动问题，然后基于信号强度的大小对相应的RSS差值作出调整。在进行RPj指纹和TP指纹的匹配时，指纹间的自适应修正曼哈顿距离如式(20)所示，即L个优选AP(下标L1～LL)对应的修正RSS差值的总和

(20)

2.5 基于ACMD-WKNN的定位算法

基于ACMD-WKNN的定位算法的思想是：在完成数据预处理和AP选择之后，基于ACMD进行指纹匹配，用WKNN方法实现位置估计，具体流程图如图4所示。

图4 基于ACMD-WKNN的定位算法流程图Fig.4 Flow chart of positioning algorithm based on ACMD-WKNN

假设计算得到K个相似度最大的参考点，下标j的变化范围是[1,K]，TP指纹与RPj指纹的ACMD是ACMDRPj，对应的权重WRPj如式(21)所示，M为一较大数，这里暂取100

(21)

参考点RPj的坐标是(Xj，Yj),TP的位置(X，Y)可通过式(22)估计获得

(22)

3 定位实验

3.1 实验环境与步骤

本文使用学者Mendoza-Silva G、Richter P及Torres-Sospedra J等提供的开放室内定位数据集-10.5281/zenodo.1066040作为实验数据集。该数据集从一幢图书馆的3层与5层分别采集获得，采集区域为各层面积为125.4m2的书架区域，实验数据集包含总共15个月的测量数据，该数据集存储了共448个以MAC地址为唯一区分的AP(单路由器上有多AP)，在每层24个共48个RP处的信号强度值。此外，采集时会预先给各RP设置序号，并根据序号进行采集，为了避免偶然性带来的误差，在各采集点上均进行6次采集。每月的数据集通常包含1组训练集与5组测试集，数据采集点的分布如图5所示。

图5 数据采集点的位置及分布情况Fig.5 Position and distribution of data collection points

图5中,黑色矩形是书柜，横向来看，每2排书柜间有3个采集点，从上至下依次属于测试集2、训练集(测试集1、测试集5)和测试集3；纵向来看，每2排书架间的采集点属于测试集4，按照序号升序和降序的顺序先后各进行1次测量。选择该数据集进行实验的原因有二点：1)该数据集提供长达15个月的信号强度数据，大数据量的实验结果保证了定位算法的可靠性与鲁棒性；2)在该数据集中包含有大量可用于模拟用户持续移动的测试点，如测试集2和测试集4对应模拟用户在书架间行走和走道上行走的不同状态，方便后续展开基于目标跟踪的研究。在本次实验中选用第3层全部月份所有训练集和测试集的指纹数据进行定位实验。

3.2 波动上限T的影响

自适应修正算法中波动上限T的变化会导致修正后的RSS发生变化，进而影响指纹匹配结果。若T过大，会导致对RSS波动的过度修正，将较多相似度并不高的指纹保留下来；若T过小，算法会退化成无修正算法，无法实现对RSS波动的平滑。在实验中取T为 0dBm、5dBm和10dBm，结果如图6所示。

图6 基于不同波动上限T的误差CDF Fig.6 Error CDF based on different fluctuation upper limit T

图6以误差累计概率分布函数(Cumulative Distribution Function，CDF)的形式给出结果，当T=0dBm时，即基于无修正曼哈顿距离的定位精度并不如T=5dBm或10dBm的定位精度。因此，基于自适应修正曼哈顿距离的算法相比无修正的算法的确能够提升定位精度。除此之外，T=10dBm时的定位精度并不如T=5dBm时的定位精度，即定位精度并不会随着T的增加而不断提高。根据图6基本确定了最佳T在5dBm附近，进一步缩小了T的测试范围到3～7dBm，基于不同T的定位误差如表1所示。由于T相近时CDF图也较为接近，故不再依靠误差CDF图分析实验结果。

表1 基于不同T(3～7dBm)的定位误差

通过表1可以得到，当T=3～7dBm时，平均误差及75%概率误差均在T=6dBm时取到最小，故在本文的实验中取T=6dBm，实验结果也从侧面证明了处理信号波动能够提高定位精度。

3.3 底数α的影响

底数α用于生成自适应的波动上限T，波动上限T随RSS值的大小自适应发生改变，图7是基于不同的底数α的值所绘制的RSS与自适应波动上限AT的关系图，其中初始波动上限T取6dBm，e为自然对数。

图7 基于不同α的RSS与AT的关系图 Fig.7 Relationship between RSS and AT based on different α

从图7中可以看出，基于不同底数α的RSS-AT曲线在RSS最小时均取到最大波动上限，但随着底数α的增大，AT的变化范围也逐渐增大，在RSS取到最大值-46dBm时，底数α取1.1、e和10对应的波动上限分别为5.405dBm、2.207dBm和0.645dBm。根据3.2节的结论，过小的波动上限无法实现对RSS波动的平滑，且波动上限T在6dBm附近取得最小的定位误差，因此自适应的波动上限AT也应在6dBm附近变化。当α取1.1时能够满足上述要求，此时波动上限T的变化范围是[5.405，6]，在给予大RSS值小波动上限的同时保证了对全部RSS的修正效果。

3.4 AP选择数量L的影响

AP选择算法的目标是在选出更可靠、受干扰更小的AP的同时减轻计算负担。因此，确定AP选择算法所选AP数量L的重要性不言自明，实验中将选择AP数量L设置为10～70，用于分析L对定位精度的影响；同时与无AP选择的算法进行对比，用于验证AP选择算法对于定位精度的改进效果，结果如图8所示。实验中AP的总数为448个，横轴上的“NO-Selection”代表无AP选择(L=448)的情况。

图8 基于不同AP选择数量L的误差Fig.8 Error based on different AP selection number L

根据图8可知，当L小于50时，随着用于定位的AP数量L的增大，定位精度也随之提升；当L达到50后，定位精度最佳，且优于无AP选择算法的定位精度；当L超过50后，算法选择的L个AP中不可靠AP的数量增多，定位精度反而有所下滑。因此，AP选择算法能够在减少指纹匹配计算量的同时提高定位精度，本文设置AP选择数量L为50。

3.5 基于不同距离的匹配算法比较

实验中实现了基于ACMD和基于欧氏距离、曼哈顿距离、余弦距离及Sorensen距离的指纹匹配算法，并在WKNN框架下进行了定位实验。根据定位结果进行比较和分析，基于不同距离的匹配算法对应的定位精度如图9所示，WKNN方法中的K取3。

图9 基于不同距离的匹配算法定位误差Fig.9 Positioning error based on matching algorithm of different distance

首先，基于不同距离的匹配算法从平均定位误差、67%累积概率误差、95%累积概率误差、定位误差标准差和精度提升比5个方面进行了比较，结果如表2所示。

表2 基于不同距离的定位误差

其次，基于不同距离的匹配算法在固定精度要求下的误差累积概率如表3所示。

表3 在固定精度要求下的误差累积概率表

综上所述，基于ACMD的匹配算法相对基于其他距离的匹配算法在定位精度上有显著提升,且定位误差的标准差更小，定位误差在2m和3m内的概率分别达到了62.41%和83.23%。

4 结论

本文针对常见的指纹匹配算法中所忽略的信号波动问题，提出了一种基于自适应修正曼哈顿距离的WiFi指纹匹配算法，并结合AP选择算法简化了指纹匹配过程，最后基于WKNN方法实现定位。算法分析与实验结果表明：

1)在实际环境下，由环境因素、采集设备或采集时间差异导致的信号波动总是存在，并会对定位结果产生影响。本文所提出的自适应修正算法在指纹匹配时，根据信号强度自适应地对指纹间的信号强度差值进行修正，减少信号波动对指纹匹配的影响，为后续研究处理信号的波动性问题提供了新的思路。修正过程的自适应参数在离线阶段获得，不会对匹配和定位带来额外的计算负担。

2)基于自适应修正曼哈顿距离的指纹匹配算法相比基于其他几种常见距离的指纹匹配算法定位误差更小，定位更稳定，同时证实了欧氏距离并非指纹匹配时的最佳相似度度量距离。本文的算法实现了在面积为125.4m2的定位区域内，平均定位误差1.85m,62.41%的定位误差在2m以内和83.23%的定位误差在3m以内的定位效果。

3)本文提出的基于自适应修正曼哈顿距离的指纹匹配算法还缺乏与更多相似度度量距离的比较，因此在后续工作中会增加更多用于对比的相似度度量距离。目前仅在Zenodo数据集上进行了定位实验，后续将在更多知名的定位数据集和真实环境中进行测试。