跨异构设备的室内Wi‑Fi 指纹定位方法

金施嘉珞，乐燕芬，许远航

（上海理工大学光电信息与计算机工程学院，上海 200093）

引 言

蓬勃发展的移动通信技术、感知计算技术和无线网络技术为实现物理世界与信息空间融合奠定了坚实的基础，同时随着人工智能和物联网技术的不断推广，基于位置的服务（Location based service，LBS）［1］已经成为人们工作生活的重要环节。在室外环境中，GPS 导航系统可以提供定位精度高、响应速度快的室外定位导航服务。而在室内环境中，由于GPS 信号在非视距条件下会发生严重衰落现象，使得现有GPS 定位技术难以满足用户的位置服务需求，因此室内定位技术应运而生。

室内定位算法主要分为两类，（1）基于测距的定位算法（Range⁃based），主要有到达时间法（Time⁃of⁃arrival，TOA）［2］、到达时间差法（Time difference of arrival，TDOA）［3］、到达角度法（Angle⁃of⁃arrival，AOA）［4］等。（2）基于接受信号接收强度（Received signal strength indicator，RSSI）值匹配的指纹定位算法［5⁃7］，最经典的算法包括K近邻算法（K⁃nearest neighbor，KNN）［8］、加权K近邻算法（WeightK⁃nearest neighbor，WKNN）［9］。这类算法包括离线和在线两个阶段，离线阶段在定位区域设置一定数量的位置参考点（Reference points，RP），并采集参考点的RSSI 信号特征，建立反映区域信号空间分布特征的位置指纹库；在线阶段基于目标实时采集的RSSI 信号，从指纹库中选取K个与其欧氏距离最小的参考点，根据该K个参考点对应坐标的均值或加权平均值作为目标的估计位置，实现定位。这类基于欧几里得距离的算法适用性高、计算复杂度小且算法精度较高，但在离线指纹数据和在线RSSI 信号使用异构设备采集时，由于不同设备的天线设计、硬件设计、驱动程序和环境等都会影响RSSI 值［10］，导致在线阶段采集的RSSI 信号与所建立的位置指纹库不能有效匹配，利用此类算法会导致较大的定位误差，因此如何在使用异构设备采集数据的情况下得到理想的定位精度成为了当前的研究热点之一。

目前解决设备异构性问题的方法主要分为校准法和免校准法两类。校准法的原理是在离线阶段构建不同设备采集的RSSI 之间的关系模型，在线阶段通过关系模型对目标设备采集的RSSI 进行转换。Tao 等［11］利用获取的在线设备和参考设备接收的RSSI 值的线性关系设计映射函数，将RSSI 值从在线设备转换为参考设备，来消除异构设备引入的定位误差。但是这种映射函数只表示特定的参考设备和在线设备的对应关系，不具有普遍性，不适用于大规模应用。文献［12］使用支持向量回归（Sup⁃port vactor regression，SVR）训练参考设备与在线设备之间的非线性关系模型，有效消除特定设备之间的异构性问题。通常校准法适用于固定参考设备和用户终端设备的情况，因此难以满足大规模异构设备的实时应用。免校准方法的原理主要是将参考设备和用户终端设备采集的RSSI 进行统一处理形成规范性指纹。Mahtab 等［13］提出信号强度差（Signal strength difference，SSD）算法，使用不同Wi⁃Fi 无线接入点（Access point，AP）采集的RSSI 差值作为新特征来消除信号传播模型中与硬件参数如天线增益有关的量，从而提高定位精度。但是文章假设定位区域内所有的AP 都有相同的硬件属性，使得该方法具有一定的局限性。刘勋［14］提出基于多维信息融合的位置指纹室内定位算法，通过信号强度差结合双曲线位置指纹（Hyperbolic location fingerprint，HLF）克服指纹的异构性，利用指纹之间的互补性构建复合指纹库。梁溪［15］提出了基于SVR 的RSSI 拟合方法以补偿终端的RSSI。Wei等［16］采用RSSI 比例法，计算一个接入点测量和每个其他接入点信号的比例；期望最大化（Expectation maximization，EM）［17］被用于联合定位和信号校准，系统测量两个设备的信号之间的偏移，然后通过迭代最小化指纹之间的欧几里得距离的偏移来学习信号差异。

本文在对实际环境中多种异构设备采集的RSSI 信号特性进行分析的基础上提出一种免校准的信号处理流程与定位算法，能够有效降低异构设备性问题。首先考虑到实际楼宇内存在大量AP 可能引入信息冗余并增大定位算法复杂度的问题，提出了一种基于标准偏差（Standard deviation，SD）的AP 选择法，提取实验环境中相对稳定的AP 信号构建定位指纹库，其次利用普氏分析法（Procrustes analysis，PA）来消除异构设备带来的RSSI 信号偏差，最后采用基于余弦相似度（Cosine similarity，CS）的WKNN 算法进行定位。为验证所提算法的定位性能，在典型室内办公环境下采集、构建了异构指纹库并进行了定位实验。

1 信号特征分析

采用不同设备在同一位置、同一时刻采集RSSI 信号时通常也存在较大的差异。这种设备的异构性对所采集信号的影响主要是由于设备软硬件的差异引起的［18］。本文利用近几年发布的移动智能终端对设备异构带来的RSSI 信号的差异进行研究。表1 列出了实验所用的4 种异构设备包括iPhone 7p、iPhone XS Max、华为Mate30 和Mate30pro 的软硬件等信息。

表1 RSSI 信号采集设备Table 1 Information of RSSI signal collection devices

由表1 可知，4 种异构设备的软硬件都存在一定的差异。本文首先利用4 种异构设备在相同位置、同一时间采集不同AP 的RSSI 信号来研究异构设备的RSSI 信号特征。RSSI 信号由本文自主开发的微信小程序进行采集。图1 给出了在某一个位置采集的不同AP 的RSSI 信号值。值得注意的是，小程序提供的API 接口对于IOS 系统和安卓系统操作原理不同，IOS 系统采集到的Wi⁃Fi 信号RSSI 的返回值取值范围为0～1，而安卓系统的取值范围为0～100。

图1 4 种设备采集的RSSI 信号Fig.1 RSSI signals collected by four devices

从图1（a）中可观察到，iPhone 7p 设备采集的RSSI 值整体高于iPhone XS Max 设备，由图1（b）可知即使设备型号相近，设备采集的RSSI 值仍有较大不同，这意味着即使采集信号的位置和时刻相同，不同手机采集的RSSI 值波动范围也很大，这必然引起位置信息的模糊，从而影响定位性能。因此，如何消除设备异构性引入的误差成为了一个不可忽视的问题。

2 算法框架和设计

本文所提算法的框架如图2 所示，命名为基于标准差和普氏分析法的余弦相似度算法（Cosinesimi⁃larity algorithm based on standard deviation and proctoranalysis），本文使用SD⁃PA⁃CS 表示。

图2 SD-PA-CS 定位算法流程图Fig.2 Flow chart of SD-PA-CS location algorithm

定位算法分为离线与在线2 个阶段。离线阶段，在每个参考点采集所有能接收到的Wi⁃Fi 的RSSI信号，结合对应的位置坐标构成原始指纹数据库。接着采用归一化算法消除采集软件带来的量纲影响，保证了数据的可比较性；然后利用SD 算法进行AP 选择，提取监测区域内稳定的AP 信号以减少数据维度来降低定位阶段计算复杂度；最后进行PA 标准化处理消除指纹数据对异构设备的敏感性。在线阶段，根据离线阶段AP 选择后的AP 序列对在线RSSI 信号进行AP 同一性处理，经PA 算法标准化后利用CS 算法确定目标位置。

2.1 离线阶段指纹库处理

离线阶段在定位区域设置R个参考点，使用4 个异构设备在每个参考点同时采集楼宇内所有能接收到的Wi⁃Fi 信号，分别构成4 个原始指纹库。设共有M个AP 点，D表示其中任一设备构建的原始指纹库，如式（1）所示。

式中xi，yi，i=1，2，…，R是第i个参考点的位置坐标；RSSIi，j，i=1，2，…，R；j=1，2，…，M，表示该设备在第i个参考点接收到第j个AP 的S个RSSI 信号采样值的平均值。

2.1.1 基于SD 的AP 选择算法

通常，在覆盖有Wi⁃Fi 网络的楼宇内有大量的可检测AP 点，实验中也发现在一个楼层内能检测到超过200 个AP。在复杂的室内环境下，较多的AP 能提供更丰富的指纹信息，但数量过多尤其是信号不稳定的AP，不仅会引入无效和冗余信息，也会增加定位算法的计算复杂度［19］。

考虑到室内环境中人员活动会引起RSSI 采样值的变化。基于SD 的AP 选择算法采用RSSI 的标准差反映接收到的RSSI 的变化情况，SD 值越小，从AP 点接收到的RSSI 信号更稳定，对应的AP 更适合进行模式匹配［20］。具体过程如下：计算离线阶段每个AP 在各参考点所采集的RSSI 信号的标准差SD，根据SD 值对所有AP 点进行降序排列，选取前N个AP 点用于构建指纹库。SD 计算表示为

式中：RSSIi，j，s，i=1，2，…，R；j=1，2，…，M为在第i个RP 点接收到的来自第j个AP 的第s个采样值，共有S个采样值；SDi，j表示相应的第j个AP 在第i个RP 的SD 值；RSSIi，j表示设备在第i个参考点接收到第j个AP 的所有RSSI 信号采样值的平均值，如式（2）所示。

对每个AP 点取其最小的SD 值为

式中：SDj，j=1，2，…，M为第j个AP 点在所有参考点的RSSI 信号的SD 最小值。将SDj从小到大排列，选取前N个SD 值对应的AP 点组成AP 集为{AP1，AP2，…，APN}，并从原始指纹库提取相应的指纹。

2.1.2 Min⁃max 归一化

由于微信小程序中所提供的API 接口对于IOS 系统和安卓系统操作原理不同，使得不同系统采集到Wi⁃Fi信号RSSI的返回值不同，因此本文采用Min⁃max 归一化确保数据在同一数量级下进行比较。给定设备接收到的RSSI信号经AP 选择后为fi=(RSSIi，1，RSSIi，2，…，RSSIi，N)，i=1，2，…，R，计算公式为

式中：min(fi)，max(fi)分别为第i个指纹中最小和最大的RSSI值，Pi=(pi，1，pi，2，…，pi，N)，i=1，2，…，R为归一化后的第i个RSSI值。图3 给出了两种设备采集的RSSI 信号归一化前后的分布。

图3 归一化前后RSSI 分布图Fig.3 RSSI distribution before and after normalization

2.1.3 PA 标准化

从图1 中可观察到由于采集设备软硬件的不同，即使在实际环境中同一时间、同一位置采集的RS⁃SI 信号也会呈现不同的分布。因此本文使用PA［21］对指纹数据进行标准化操作，以消除异构设备对信号采样值的影响。PA 法是一种在形状统计分析领域用来进行图形比较来寻找标准形状的方法。该算法通过不断迭代，寻找对给定对象最优的平移，缩放和旋转，以便得到标准形状，继而寻找每个对象形状到这个标准形状的仿射变化方式。使用普氏分析法处理指纹库，可以将RSSI 分布处理为标准正态分布，使异构设备采集的RSSI 信号有相同分布，更接近一个标准信号。由于RSSI 信号为一维对象，只需要对其进行平移和均匀缩放操作，就能得到接近标准的信号。

对归一化后的每个RSSI 信号Pi作平移处理

式中：为设备在第i个参考点上的标准化RSSI 信号。对离线指纹库每一参考点的RSSI 信号强度进行上述处理，得到标准化数据库N为第j个AP 经过上述处理后的RSSI 值。同样的，在线目标采集的RSSI 信号也需要标准化处理。图4 给出了4 种不同设备在随机选择的10 个位置点同时采集的RSSI 值PA 标准化前后的结果。

从图4 中可知基于PA 的数据标准化算法可以使异构设备的RSSI 分布近似趋于同一标准，这能有效消除异构设备带来的影响，提高定位精度。

图4 4 种设备的测试点序号与标准化RSSI 值曲线Fig.4 Test point serial number and standardized RSSI value curves of four kinds of equipments

2.2 在线定位阶段

在线定位阶段首先将目标点采集的RSSI 信号经AP 筛选后做归一化与标准化处理，再使用CS 算法对目标点进行位置估计。

WKNN 算法通常采用欧式距离来衡量两个RSSI 向量间的差异度，距离越小表示两个向量越相似，即RSSI 向量对应的两个位置在空间上邻近。而实际室内环境中每个AP 信号的覆盖区域是很有限的。图5 给出了从指纹库中随机抽取的2 个AP 在各RP 点的分布情况。从图5 中可看出两个AP 的覆盖范围不同，圆形所代表的AP1主要覆盖区域为Y轴0～8 m，X轴20～60 m，而箭头所代表的AP2则为Y轴4～12 m，X轴0～60 m，重合区域主要在中间部分，即定位区域中的大厅。

图5 RSSI 分布情况Fig.5 RSSI distribution

因此目标测试点实际采集的RSSI 信号中能接收到的AP 与指纹库中各RP 能接收的AP 并不一致。大部分情况下两者只有部分交集。为了减小未接收的AP（本采集系统中设为0 dBm）对两个RSSI 向量相似度的影响，采用了余弦相似度来选取与目标在线RSSI 距离最小的若干指纹。

计算公式为

图6 基于欧式距离和余弦相似度的最近邻比较Fig.6 Nearest neighbor comparison based on Euclidean distance and CS

得到RSSI 信号后，对所有参考点对应的余弦相似度进行降序排列，选取前L个参考点，将选取的L个参考点对应的位置坐标作均值处理，估算出目标点在待测区域的位置坐标，即

3 实验场景的建立与算法性能分析

3.1 实验场景

为了研究本文所提算法在真实环境中的定位性能，选择了具有典型室内环境布局的两处实验地点，分别为上海理工大学光电大楼的8 楼实验层和9 楼办公层，记为区域A 和区域B。区域A 和区域B分别如图7（a）和7（b）所示。

图7 实验定位区域Fig.7 Experimental positioning area

定位区域A 选取8 楼的所有走廊，该区域人员众多，走动频繁，且存在较强环境因素干扰，如墙壁、不稳定信号源等，使其能代表人员密集型的室内环境，如超市、医院等。定位区域B 选取9 楼办公层的所有走廊及中间休息大厅，该区域人员数量适中、存在少量的人员走动，且包含有一块环境因素干扰较小的区域，使其能代表人员相对稀疏的室内环境，如办公楼、体育馆等。实验定位区域面积都为66.6 m×12.6 m。离线阶段，区域A 与区域B 中每隔1.8 m 部署一个参考点，分别设置了88 个和136 个参考点。

本文利用4 种异构设备采集楼宇内所有路由器发送的Wi⁃Fi 信号。由于API 接口对于IOS 系统和安卓系统操作原理不同，在实验后续操作阶段，将无法接收到的Wi⁃Fi 信号RSSI 值设为0。在线阶段，在区域A 和区域B 中每隔3.6 m 均匀部署36 个和44 个目标点，采集的RSSI 信号均值化后用于在线定位。

3.2 算法性能分析

3.2.1 总体性能分析

首先，本文研究在区域A 和区域B 中采用相同或不同设备进行实验时各算法的性能。同构设备中，离线指纹库和在线指纹均采用iPhone 7p 采集；异构设备中，离线阶段使用iPhone 7p 采集的指纹库，在线阶段使用Mate30 采集的在线指纹，其他设备组合将在下文讨论。不同算法的性能结果如表2 所示。

表2 不同算法的性能比较Table 2 Performance comparison of different algorithms

表2 中PA⁃SD⁃CS为本文所提的定位算法，SD⁃WKNN为采用SD算法的WKNN定位算法，SSD⁃WKNN 为RSSI 信号强度差的WKNN 定位算法。在定位区域A 中，WKNN 及相关算法中K取3，CS 算法中的L取3，且因为环境因素干扰较强，AP 选择个数N设为80（共可采集到100～150 个AP 点）；在区域B 中，K取7，L取7，N设为90（共可采集到150～200 个AP 点）。

由表2 可以看出，在同一定位区域，不管采用何种定位方法，与同构设备相比较，采用异构设备时定位精度均有不同程度的下降。但本文所提算法在区域A 和区域B 中的定位精度均最高，同构设备下分别是2.34 m 和1.89 m，而WKNN 是2.75 m 和2.03 m，提高了14.9%和6.9%；异构设备下分别为2.96 m和2.29 m，而WKNN 是3.76 m 和2.92 m，提高了21.3%和21.6%。并且区域A 中方差均小于4，区域B中均小于2，相较于其他算法，本算法方差最小，稳定性最高。以上说明本文的定位算法可以有效提高定位的精度和鲁棒性，适用于多种室内环境。

3.2.2 AP 选择个数对定位性能的影响

通常情况下，楼宇内部署有大量发射Wi⁃Fi 信号的路由器，必定存在对定位性能提高帮助不大甚至降低定位性能的AP 点。因此本文在区域A 和区域B 中研究AP 选择个数对定位性能的影响，各参数保持不变，实验结果如图8 所示。图8 为区域A 中平均定位误差随AP 数量变化分布图，离线阶段使用iPhone 7p 采集，在线阶段使用Mate30 采集。可以看出，算法的平均定位误差随着AP 数量的增大总体趋势逐渐减少，在AP 数量为90 个时，PA⁃SD⁃CS、SSD⁃WKNN、SD⁃WKNN 及WKNN 的定位精度分别为2.66 m，3.5 m，3.47 m 和4.57 m。在区域B 中也可观察到类似的结果，由此可知，本文所提的算法可以应用于AP 点数量众多的场合且有较高的定位精度。

图8 平均定位误差随AP 数量变化分布Fig.8 Distribution of average positioning er⁃ror with the number of AP

3.2.3 离线阶段指纹库的稀疏性对定位性能的影响

离线指纹库中参考点的分布密度决定了离线阶段的人力成本，同时指纹库的稀疏性也会影响到定位的精度，因此实验也研究了离线指纹库网格大小对定位精度的影响，并使用平均定位误差为参考标准，如表3 所示。从表3 可以看出，随着指纹库网格的增大，各算法的平均定位误差也随之增大，并且在相同网格大小下，PA⁃SD⁃CS 的定位精度最高。同样的，在达到相同的精度的情况下，PA⁃SD⁃CS 所需的网格密度更大。如区域B 中，达到3 m 左右的定位精度，PA⁃SD⁃CS只需5.4 m×1.8 m 的网格大小，而WKNN、SD⁃WKNN 都需要更密的3.6 m×1.8 m 网格。由此可见，本文所提算法可应用于稀疏指纹库的定位，且保持了较好的定位精度。

表3 网格大小对定位精度的影响（离线阶段：iPhone 7p，在线阶段：Mate30）Table 3 Influence of grid size on positioning accuracy（off‑line：iPhone 7p，on‑line：Mate30）

3.2.4 CS 算法选取最近邻个数对定位性能的影响

CS 算法将L个选取出的参考点对应坐标的均值作为目标点位置坐标，则选取个数L会影响定位性能。如图9 所示，在区域A 与区域B 中，定位误差随最近邻选取个数L的变化而改变。在区域A 中，L的选择区间为3～4 时算法的定位性能相对更好，这可能与区域A 包含有狭长走廊的实验环境有关；而在区域B 包含有走廊和大厅的实验环境中，L的选择区间可为4～7 能保证良好的定位效果。

图9 最近邻个数对定位性能的影响Fig.9 Influence of the number of elements on positioning performance

3.2.5 不同异构设备组合对定位性能的影响

上述实验中的离线参考指纹库和在线指纹使用iPhone 7p 和Mate30 设备组合采集，但是不同异构设备组合采集的RSSI 信号具有差异性，会在一定程度上影响定位性能，因此本文研究不同异构设备组合对定位性能的影响。图10 给出了各算法在不同异构设备组合下的误差累计分布函数（Cumulative distribution function，CDF），图10（a）为离线指纹库与在线信号分别由iPhone XS Max 和Mate30pro 设备组合（记为组合1）采集，图10（b）则使用Mate30pro 和iPhone 7p 设备组合（记为组合2）采集。

图10 不同异构设备组合对定位性能的影响Fig.10 Influence of different heterogeneous device combinations on positioning performance

图10（a，b）中，PA⁃SD⁃CS 算法在累积分布为50%时，定位误差分别为2.16 m 和1.92 m，WKNN 则分别为2.77 m 和2.39 m，分别提高了22%和19.7%。由此可知，在不同异构设备组合下，相较于其他算法，本文算法都具有较高的定位精度，较为有效地解决了异构设备引入的误差，具有一定的普遍适用性。

4 结束语

本文针对离线阶段和在线阶段使用异构设备采集RSSI 数据时引入的固有误差的问题，提出了一种基于余弦相似度的数据处理算法。该方法在离线阶段采用普氏分析法将异构设备采集的数据标准化，形成标准化离线指纹库。定位阶段使用CS 算法，选取余弦相似度最大的前L个参考点，将其对应的坐标均值作为目标点的位置坐标实现定位。本文研究两个典型室内环境下，AP 数量、离线指纹库稀疏度等因素对算法性能的影响。实验结果表明，本文所提的算法在降低计算复杂度的同时能保持较高的定位精度，算法具有一定的鲁棒性。后续工作可以集中在进一步提高算法的定位精度。