¹沈阳理工大学信息科学与工程学院，辽宁 沈阳

²沈阳市沈河区文萃小学，辽宁 沈阳

收稿日期：2023年1月12日；录用日期：2023年2月10日；发布日期：2023年2月17日

摘要

随着Wi-Fi和智能手机的愈发普及，基于Wi-Fi来进行定位是最近越来越受关注的一个研究领域。现有针对Wi-Fi定位所开展的研究工作本质上都是一种静态的方法。针对这一问题，提出一种基于AP RSSI特征向量相似度匹配的多尺度Wi-Fi定位方法，设计了一种面向目标地点的可探知AP接收信号强度指示符(RSSI)特征向量生成机制，重点研究了相似度度量和距离度量这两个指标，并依托这两个指标实现了一种AP RSSI特征向量之间相似度匹配算法，根据相似度匹配结果提供如楼宇级、楼层级、房间级等多尺度定位。基于Android环境开展实验，实验结果表明该方法在多种尺度下均能达到96%以上的定位正确率，能够提供准确、高效及低成本的定位服务。

关键词

Wi-Fi定位，AP RSSI特征向量，相似度匹配，多尺度，智能手机

Multi-Scale Wi-Fi Localization Method Based on AP RSSI Feature Vector Similarity Matching

Jiaxuan Wu¹, Zhi Li², Zeyu Wang¹

¹School of Information Science and Engineering, Shenyang Ligong University, Shenyang Liaoning

²Wencui Primary School, Shenyang Liaoning

Received: Jan. 12^th, 2023; accepted: Feb. 10^th, 2023; published: Feb. 17^th, 2023

ABSTRACT

Recently, Wi-Fi-based localization has gained increasing attention due to the popularity of Wi-Fi and smartphones. In terms of Wi-Fi localization, existing research is essentially static. To address this problem, a multi-scale Wi-Fi localization method based on AP RSSI feature vector similarity matching is proposed. It is designed to generate probable AP Received Signal Strength Indicator (RSSI) feature vectors based on two metrics, similarity metric and distance metric, and to implement a similarity matching algorithm between RSSI feature vectors based on these two metrics, and then to provide multi-scale localization services at the building, floor, and room levels based on similarity matching results. Experiments on the Android environment demonstrate that the localization method is capable of achieving more than 96% accuracy at different scales and is efficient, low-cost, and precise.

Keywords:Wi-Fi Positioning, AP RSSI Feature Vectors, Similarity Matching, Multi-Scale, Smartphone

Copyright © 2023 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

近年来，基于位置的服务(LBS)已广泛应用于各场景中，如室内用户导航、精准广告推送、个性化推荐，以及邻近通知等 [1] 。一般情况下，GPS可以很好地适用于各种定位需求。但在某些情况下，如为了节省能源或在室内环境下，GPS并不总是适用于某些用户，因此在本文中提出了一种替代方法，通过分析环境背景来区分多个主要位置，例如Wi-Fi接收信号强度指示器(RSSI)。随着新位置的访问，Wi-Fi AP的记录数量和特征数量都会增长。

现如今，几乎所有的智能手机都内置Wi-Fi AP扫描这个功能。通常，在大多数宽敞的公共区域(例如学校、图书馆、和教学楼)都可以检测到多个AP。因此，附近的AP的总数增加并且逐渐趋于大量。在一次实际的测试当中，受试者的智能手机在其2个月的使用期内不断扫描AP，总共主动扫描了超过5000个AP。不断增加的AP数量是本文工作面临的新挑战之一。本文研究工作的目标是提供多尺度的定位，这意味着它可以提供各种粒度的定位服务，例如楼宇级、楼层级或房间级。而越来越多的记录数量和不确定数量的特征数会给一些基于传统聚类算法来进行匹配的研究方法带来沉重的负担，例如，基于K-Means算法聚类所有示例中的所有特征 [2] 。

通过观察，当智能手机处于Wi-Fi环境中时，基本上存在以下四种不同的情景：

• 情景1：环境当中没有任何AP信息；

• 情景2：环境当中有许多AP，但不存在任何连接；

• 情景3：环境当中只有一个连接的AP，但没有其他AP信息；

• 情景4：环境当中有一个连接的AP，并且周围也有许多别的AP。

在现实生活的建筑物当中都具有许多承重墙等遮挡物，因此不能保证移动设备和AP之间的连接是直线型状态，也就不太可能获得移动设备与任何AP之间的高精度距离。因此，多边测量算法 [3] 并不适用于现实世界当中。

另一个主要挑战是，从无线电通信的性质来看，任何一个AP的Wi-Fi信号质量都不会持续的可靠，很容易观察到Wi-Fi信号质量一直在波动，这种性质破坏了定位精度，很可能将不同位置预测成同一个区域。

由于在一个环境空域中可以同时并存多个WLAN，因此使用服务集标识符(SSID，仅为1~32字节的字母数字名称)作为代表WLAN网络的唯一名称。一个WLAN中可以同时存在多个AP，使用基本服务集标识符(BSSID)作为每一个AP的唯一标识符，按照惯例使用AP的MAC地址作为BSSID。接收信号强度指示符(RSSI)用来表示接收的无线电信号的功率。RSSI值以负数形式表示(例如−91)，并且该值越接近0，则表示接收的信号越强。为了实施基于Wi-Fi的定位服务，智能手机会不断地收集周围环境中所有AP的信息，包括已连接的AP以及许多其他未连接的AP。从每个AP获取的信息由RSSI和BSSID组成，表示来自特定AP的信号强度，其中使用AP的MAC地址作为该AP的BSSID。因此，AP特征向量可以表示为以下格式： $\left[B_c:R_c;B_1:R_1;B_2:R_2;\cdots ;B_i:R_i\right]$ ，其中 $B_c$ 表示已连接AP的BSSID，而 $R_c$ 表示已连接的AP的RSSI。 $B_i$ 表示周围环境中未连接AP_i的BSSID， $R_i$ 则表示对应的RSSI。

本文提出了一种基于AP RSSI特征向量相似度匹配的多尺度Wi-Fi定位方法。首先，通过智能手机收集所处位置上所有可探知AP的接收信号强度指示符(RSSI)，并生成一个与该位置对应的AP RSSI特征向量，由于每一个位置上可探知AP的数量都是事先未知的，因此每一个AP RSSI特征向量中所包含的特征数都可能是不同的；随后，设计了一种基于AP RSSI特征向量相似度匹配算法，依托相似度度量和距离度量这两个指标将新地点的AP RSSI特征向量与事先标记地点的AP RSSI特征向量进行匹配，从而达到定位的目的。

2. 相关工作

文献 [4] 提出了一种基于单点智能手机捕获ADL的方法。通过分析Wi-Fi定位、声音以及方向的数据组合来识别室内ADL；文献 [5] 分析了基于Wi-Fi指纹算法定位的隐私问题，并提出了一种保护隐私的Wi-Fi指纹定位方案(PriWFL)，该方案既可以保护客户的位置隐私，也可以保护服务提供商的数据隐私；文献 [6] 设计了一个节能的室内定位系统，称为ZigBee辅助室内定位(ZIL)。该系统基于ZigBee干扰特征的Wi-Fi指纹算法来实现。他们提出了一种检测Wi-Fi Aps以从ZigBee接口收集的信号中形成Wi-Fi指纹的方法，并提出了一种指纹匹配算法来对齐指纹对；文献 [7] 提出了一种基于卡尔曼滤波框架的Wi-Fi、激光雷达与地图的融合定位方法；文献 [8] 提出了一种基于智能手机四向接收信号强度(RSS)指纹的室内定位方法，该方法在离线阶段收集指纹点信息，并在在线阶段使用改进的KNN分类算法将测试点与指纹点匹配；文献 [9] 提出一种以Wi-Fi与视觉信息相融合的指纹为位置表征的多尺度定位方法；文献 [10] 基于位置指纹的Wi-Fi定位方法，设计出一套适用于地下停车场的车辆实时定位系统；文献 [11] 提出了基于三边测量定位和信号强度(RSSI)的应用于大型场馆、复杂环境下的人群定位新方法；文献 [12] 提出一种融合WiFi与可穿戴惯导模块的室内定位方法，采用加权贝叶斯算法实现WiFi指纹定位，同时基于无迹卡尔曼滤波融合WiFi定位结果与PDR定位结果。

然而，上述针对Wi-Fi定位所开展的研究工作本质上都是一种静态的方法，这些研究方法并不能完全适用于现实世界的情况。换句话说，现有的研究方法总是假设两种先决条件：1) 将许多AP作为锚点；2) 所有AP的精确位置都是事先已知的。而在现实环境中，需要考虑如下所述的两个问题：

• AP的数量是未知的；

• AP的具体位置是未知的。

3. AP RSSI特征向量相似度匹配算法

在本节中设计了一种适用于全域Wi-Fi定位的AP RSSI特征向量相似度匹配算法，其中每一个AP RSSI特征向量中所包含的特征数可能都不相同。随后，使用距离度量和相似度度量将新的AP RSSI特征向量实例映射到已标记的AP RSSI特征向量上。

3.1. 距离度量

基于AP RSSI特征向量的特性，可以总结出如下几点规则：

• 规则I：如果两个AP RSSI特征向量共享于一个相同的已连接的AP，则这两个实例很可能处于相同或接近的区域。

• 规则II：如果两个AP RSSI特征向量都具有它们自己的已连接的AP (或者说，其中一个AP的特征向量没有包括任何一个已连接的AP)，但这两个AP特征向量共享一部分AP BSSID，那么这两个实例仍然很可能处于相邻的区域。与共享BSSID相对应的RSSI是距离度量的因子。

• 规则III：如果两个AP RSSI特征向量都具有它们自己的已连接的AP (或者说，其中一个AP的特征向量没有包括任何一个已连接的AP)，但这两个AP特征向量不共享任何AP BSSID，那么这两个实例不应该在相邻区域中。

• 规则IV：如果两个AP RSSI特征向量共享的BSSID越多，则说明两个位置之间的距离越近。其中，每个AP的RSSI也应被视为信号强度的量化。并且RSSI的数值越高(负值)，则表示AP的信号越强。

• 规则V：已连接的AP的信号强度并不意味着强于AP特征向量中的其他AP，仅仅说明了客户端获得了该AP的许可。

3.2. 相似度度量

在本小节中定义了一个用于计算两个具有可变AP特征数量的实例之间相似性的距离函数。在此，使用Jaccard系数来测量有限样本集之间的相似性，具体的形式化表示如公式(1)所示。

$J\left(A,B\right)=\frac{\left|A\cap B\right|}{\left|A\cup B\right|}=\frac{\left|A\cap B\right|}{\left|A\right|+\left|B\right|-\left|A\cap B\right|}$ (1)

在公式(1)中，A，B代表从AP RSSI特征向量中提取的两个AP BSSID向量。 $J\left(A,B\right)$ 表示A，B之间的Jaccard系数，用于根据规则II和规则III度量相似性。

3.3. 定向精细尺度的RSSI计算

AP BSSID向量的Jaccard系数只能确定这两个位置是否在同一大区域，而无法做到精细粒度的区域定位。每一个AP的RSSI可以帮助将大区域划分成多个小区域。作为图1中所示的一个例子，图中所有的八个AP都被同一区域内的四个智能手机扫描，因此每两个AP RSSI特征向量之间的Jaccard系数总是达到 $J\left(A,B\right)=1$ 。为了简化情况，这里只考虑视距传播的情况。

图1. 多Access Point (AP)间手机定位

RF传播模型(例如，对数距离路径损耗(LDPL)模型)可用于在室内环境中的各个位置来预测Received Signal Strength (RSS) [13] 。

$p_{ij}=P_i-10{\gamma }_i\log d_{ij}+R$ (2)

公式(2)表示：当第j个智能手机位于距第i个AP的距离为 $d_{ij}$ (以米为单位)时，接收到的信号强度为 $p_{ij}$ (以dBm为单位)。 $P_i$ 表示距离为1米时第i个Access Point (AP)的RSS (以下称为发送功率)。路径损耗指数 ${\gamma }_i$ 用来反映第i个Access Point (AP)附近的RSS下降率。R是一个随机变量，由于多径效应，物理环境中信号的传播存在不对称性(例如，存在障碍物)以及模型本身中的其他缺陷而反映RSS中的变化。

换言之，移动设备和AP之间的距离 $d_{ij}$ 只能基于先验知识 $P_i$ 和 ${\gamma }_i$ 从RSS值推断出来，具体如公式(3)所示。

$d_{ij}={10}^{\frac{P_i+R-p_{ij}}{10{\gamma }_i}}$ (3)

在理想环境中，信号强度与距离负相关，即距离越近信号强度越强，反之则越弱。在如图1所示的情况下，智能手机接收的每个AP的RSSI值应该完全不同。距离较远的AP的RSSI值小于距离较近的AP的RSSI值。因此，从智能手机1 (SP1)的角度来看，RSSI值从最大到最小排序的AP向量可能是：[AP1; AP5; AP4; AP2; AP6; AP3; AP7; AP8]；而智能手机3 (SP3)的AP向量可能是：[AP3; AP2; AP7; AP6; AP4; AP8; AP5; AP1]。该区域中的每个移动设备都有属于自己的基于RSSI值的AP向量，因此可以将这个大区域定向分成几个小区域。

3.4. 定向精细尺度距离的RSSI计算

本小节将计算从智能手机到所有可见AP的距离总和，以便区分出对应于规则IV的更精细区域。假设图1中不存在AP1和AP5，正如上文提到的那样，SP1和SP2收集到的AP向量均以相同的形式来表示，即表示为[AP4; AP2; AP6; AP3; AP7; AP8]，因为这些AP的相对位置都是相似的。为了区分SP1和SP2所在的具体位置，将采用如公式(4)所示的距离求和公式：

$S_i={\displaystyle \underset{j}{\sum }{d}_{ij}^2}$ (4)

在公式(4)中， $S_i$ 表示SP_i与所有可见AP的距离总和，i表示智能手机的ID，j表示AP的ID。通过公式(4)可以计算出智能手机SP_i到所有可见AP [AP1; AP2; ∙∙∙; APj]的距离总和。因此，如上例所示， $S_1$ 应大于 $S_2$ ，这就意味着SP1与所有可见的AP之间的距离较SP2与所有可见的AP之间的距离要更大。

图2. 基于RSSI计算距离差异

图2表明了基于RSSI计算进行精细区域区分的基本原理。在图2所示的情况下，两部智能手机并存于包含三个AP的Wi-Fi环境中。在两部智能手机之间画一条直线(参考线)，并使用这条参考线作为计算的基础。 $h_j$ 表示APj和参考线之间的一条垂直线； $d_{ij}$ 表示智能手机SPi到APj的距离； $h_j$ 、 $d_{ij}$ 以及参考线的一部分构成一个三角形，可以观察到这个三角形的斜边就表示一个给定的智能手机到一个AP的距离。

根据勾股定理，在直角三角形中，三角形两条直角边长度的平方和等于三角形斜边长度的平方和。所以：

$\{\begin{array}{l}{S}_1=d_{11}^2+d_{12}^2+d_{13}^2\\ S_2=d_{21}^2+d_{22}^2+d_{23}^2\end{array}$ (5)

$\begin{array}{c}{S}_1-S_2=\left(d_{11}^2-d_{21}^2\right)+\left(d_{12}^2-d_{22}^2\right)+\left(d_{13}^2-d_{23}^2\right)\\ =\left[\left(b_{11}^2+h_1^2\right)-\left(b_{21}^2+h_1^2\right)\right]+\left[\left(b_{12}^2+h_2^2\right)-\left(b_{22}^2+h_2^2\right)\right]+\left[\left(b_{13}^2+h_3^2\right)-\left(b_{23}^2+h_3^2\right)\right]\\ =\left(b_{11}^2-b_{21}^2\right)+\left(b_{12}^2-b_{22}^2\right)+\left(b_{13}^2-b_{23}^2\right)\\ =\left(b_{11}+b_{21}\right)\left(b_{11}-b_{21}\right)+\left(b_{12}+b_{22}\right)\left(b_{12}-b_{22}\right)+\left(b_{13}+b_{23}\right)\left(b_{13}-b_{23}\right)\\ =d_x\left(b_{11}-b_{21}\right)+d_x\left(b_{12}+b_{22}\right)+d_x\left(b_{13}+b_{23}\right)\\ =d_x\left(d_x-2b_{21}\right)+d_x\left(d_x+2b_{22}\right)+d_x\left(d_x+2b_{23}\right)\\ =d_x\left(3d_x+2\left(-b_{21}+b_{22}+b_{23}\right)\right)\end{array}$ (6)

矢量 $b_{21}$ 的方向与矢量 $b_{22}$ 和 $b_{23}$ 的方向相反。因此，公式(6)中 $b_{21}$ 项之前有一个负号。通过总结公式(6)，可以得到如公式(7)所示的内容：

$S_1-S_2=d_x\left(N{d}_x+2\left|{\displaystyle \underset{j=1}{\overset{N}{\sum }}{b}_{2j}}\right|\right)$ (7)

在公式(7)中，N表示环境中所有Access Point (AP)的总数， $d_x$ 表示智能手机SP1和SP2之间的距离。

此外，公式(8)实现了一种通用模式，表明两部智能手机的RSSI差异是参考智能手机之间的物理距离和与智能手机与所有AP之间2倍的平均总距离决定的。由于所有AP总是围绕着手机，即智能手机与所有AP之间的矢量和趋向于零。因此，两部智能手机的RSSI差异与两部智能手机之间距离的平方成正

比。需要注意的是， $d_x$ 如果远大于 $\frac{2}{N}\left|{\displaystyle \underset{j=1}{\overset{N}{\sum }}{b}_{2j}}\right|$ ，那这两部手机不能扫描同一组AP。

$\left(S_1-S_2\right)/N=d_x\left(d_x+\frac{2}{N}\left|{\displaystyle \underset{j=1}{\overset{N}{\sum }}{b}_{2j}}\right|\right)$ (8)

3.5. 算法实现

信号空间中的最近邻居(NNSS) [14] 是用于比较多个记录位置并从中选择出与观测到的信号强度最佳匹配的一个度量。其思想是在一组固定位置计算观测集 $\left(p_{1i};p_{2i};p_{3i}\right)$ 和记录集 $\left(p_{1j};p_{2j};p_{3j}\right)$ 之间的距离(在信号空间中)，并从中选择具有最小化距离的位置。一般使用欧几里得距离作为距离的度量，即 $\sqrt{{\left(p_{1i}-p_{1j}\right)}^2+{\left(p_{2i}-p_{2j}\right)}^{\text{2}}+{\left(p_{3i}-p_{3j}\right)}^{\text{2}}}$ 。然而，信号的强度与距离的对数成正比。具有较强RSSI的AP较RSSI较弱的AP有更大的贡献，因为RSSI较强的差异比RSSI较弱的差异具有更强的代表性(因为信号指数不是线性的)。为了表示该特性，将引入权重系数 $\mu$ 。

$p_{ki}-p_{kj}=10{\gamma }_k\log d_{kj}-10{\gamma }_k\log d_{ki}=10{\gamma }_k\log \frac{d_{kj}}{d_{ki}}$ (9)

$\frac{d_{ki}}{d_{kj}}={10}^{\frac{-\left(p_{ki}-p_{kj}\right)}{10{\gamma }_k}}$ (10)

$\mu \left(p_{ki},p_{kj}\right)={10}^{\frac{-\left(p_{ki}-p_{kj}\right)}{10{\gamma }_k}}\cdot \left|p_{ki}+p_{kj}\right|$ (11)

通过使用曼哈顿距离度量，可以计算出每个基站信号强度水平加权的的绝对差的总和。具体如公式(12)所示：

$\begin{array}{c}strength\_distance\left(p_{ki},p_{kj}\right)=\mu \left(p_{ki},p_{kj}\right)\cdot \left|p_{ki}-p_{kj}\right|\\ ={10}^{\frac{-\left(p_{ki}-p_{kj}\right)}{10{\gamma }_k}}\cdot \left|p_{ki}+p_{kj}\right|\cdot \left|p_{ki}-p_{kj}\right|\\ ={10}^{\frac{-\left(p_{ki}-p_{kj}\right)}{10{\gamma }_k}}\cdot \left(p_{ki}^2-p_{kj}^2\right)\end{array}$ (12)

在公式(12)中， $p_{ki}$ 表示观测集中SP_i收集到AP_k的RSSI信号强度。 $p_{kj}$ 表示记录集中SP_j收集到AP_k的RSSI信号强度。 $\mu \left(p_{ki},p_{kj}\right)$ 表示 $p_{ki}$ 和 $p_{kj}$ 之间的权重系数 $\mu$ ，用于提高强RSSI差异的相似性匹配贡献度。

算法1显示了位置匹配算法的详细内容，用于根据AP的RSSI特征向量来确定两个智能手机是否在同一区域。在算法1中，算法的前几段会检查一些前提条件以达到减少执行时间的目的。具体而言就是，在第1~2行，基于规则III进行筛选；在第3~5行，基于规则IV进行筛选。

在匹配步骤中，将每个观测到的APRSSI特征向量与RSSI特征向量种子数据库中的每一个特征向量进行匹配，一旦它与任何种子向量成功匹配，则将该观测到的特征向量分类到对应的组中，因此将该特征向量标记为匹配的区域ID。否则，将新的特征向量添加到种子数据库中，并标记为新的区域ID。

算法1. 相似度计算(判断两台智能手机是否在同一个位置)

4. 实验讨论

利用基于Android开发的记录APP和后台的日常生活活动(ADL)监测大数据平台 [15] 来支持本文的实验。自2017年以来，ADL监测大数据平台逐步收集和存储了受试者的ADL数据。每个ADL记录APP用户每天生成近5000条记录，并上传到日ADL监测大数据平台，不断增长的数据量无疑为本文的目标提供了合适的数据源。

通过本章提出的基于AP RSSI特征向量相似度匹配算法，并依托已标记的数据(包含超过4万条记录)，可以为用户提供不同粒度(城市级、校园级、楼宇级和房间集)的定位服务。表1显示的是为验证本章提出的Wi-Fi定位方法有效性所开展的实验结果。

表1. 多尺度Wi-Fi定位结果

在表1中，通过7种不同定位粒度的实验来验证本章提出的定位方法。可以看出，定位粒度越精细则定位精度越低，但所有的实验都能取得96%以上的定位正确率。此外，由于本文所提出的方法无需部署额外基础设施，仅仅依托于智能手机就能实现多尺度区域定位服务。因此，通过表1的实验结果可以充分表明本文提出的基于AP RSSI特征向量相似度匹配的多尺度Wi-Fi定位方法的有效性。

5. 结论

随着Wi-Fi和智能手机的越发普及，基于Wi-Fi来进行定位是最近越来越受关注的一个研究领域。然而，可以观察到许多关于Wi-Fi定位的研究工作都是静态的，换言之，此类方法都是将许多AP作为锚点，并且AP的精确位置都是事先已知的。然而，这些方法并不完全适用于现实世界，因为AP的数量或放置位置通常是事先未知的。因此在本文中提出了一种基于AP RSSI特征向量相似度匹配的多尺度Wi-Fi定位方法，该方法适用于AP RSSI特征向量记录数不断增加且AP RSSI特征向量中特征数各异情况下的多尺度Wi-Fi定位。基于该定位方法可以以不同的粒度准确地获取用户的位置信息，从而有助于为用户提供个性化LBS。通过设置Android环境和ADL监测大数据平台对本章提出的定位方法开展了实验讨论，实验讨论结果表明了本文提出的方法能够为用户提供准确、高效及低成本的定位服务。

基金项目

辽宁省教育厅科学研究面上青年人才项目(LJKZ0266)。

文章引用

吴嘉轩,李 智,王泽雨. 基于AP RSSI特征向量相似度匹配的多尺度Wi-Fi定位方法
Multi-Scale Wi-Fi Localization Method Based on AP RSSI Feature Vector Similarity Matching[J]. 软件工程与应用, 2023, 12(01): 59-67. https://doi.org/10.12677/SEA.2023.121007

参考文献