基于WiFi 信号的室内外联合定位技术研究*

唐 杰，黄 铭，林建喜，程 骋，杨晶晶

（1.云南大学 信息学院，云南 昆明 650091；2.云南省无线电监测中心，云南 昆明 650228）

0 引言

基于WiFi 信号定位主要应用于室内场景，最近已有许多学者开始研究基于WiFi 基础设施的无GPS 室外定位服务[1]。与超宽带定位技术、蓝牙定位技术和惯性导航技术等比较，基于WiFi 位置指纹定位技术无需额外添加其他设备，且部署简单、成本较低、定位范围广、精度较高[2]。因此，基于WiFi 技术实现定位是一个较好的选择。当前解决室内外联合定位问题技术的大多是卫星定位系统与室内定位组合技术，而且主要是针对在室内外过渡区域平滑切换定位方法问题，文献[3]提出了坐标标定法，使得室内外坐标达到一致。在过渡区域中使用越区切换方法，实现基于北斗和超宽带的室内外联合高精度定位。城市环境或园区内卫星信号较差，但是已经大量部署WiFi 网络，文献[4]设计了一种基于WiFi 信号的室外人员定位系统，通过动态选取k个锚节点建立定位模型，并且改进接收信号强度指示(Received Signal Strength Indicator,RSSI)测距方法以提高定位精度。文献[5]设计了基于WiFi 信号的园区定位与导航系统,提供了园区内高精度定位服务。针对定位延迟问题，文献[6]提出了分级定位方案，首先通过汉明距离确定多个子区域，再在子区域内通过k 近邻算法进行精定位。基于位置指纹的定位精度与其采集的指纹密度有关，通过空间插值法对其他位置的定位信息进行扩充可以提高定位精度，而且能够降低前期数据采集工作量[7]。最近有研究者从室内位置信息与定位信息融合角度出发进行定位研究[8−9]，提出了基于知识图谱WiFi 定位方法，侧重于有效整合室内WiFi 数据和空间环境特征信息。

基于上述对室内外联合定位的研究，本文针对云南大学呈贡校区建立了基于WiFi 信号的室内外联合定位图模型，将物理空间位置、媒体接入控制(Media Access Control,MAC)地址和RSSI 关联起来，实现了基于WiFi信号的室内外联合定位。实验结果表明，通过相似度算法进行一次定位时，数据采集间隔与定位精度为同一数量级，且定位速度快；为了提高室内定位精度，由三次样条插值对室内数据扩充，在Jaccard 相似度算法的基础上结合加权K 近邻(Weighted K-Nearest Neighbor,WKNN)算法进行二次定位。分级定位不仅提高定位精度，而且降低系统延迟时间。最后设计开发了基于WiFi 信号的室内外联合定位系统，便于获得直观的可视化位置信息。

1 定位图模型与算法

1.1 定位图模型

本文建立了基于WiFi 信号的室内外联合定位图模型[10]，其表达式如式(1)所示。

定位图模型框架如图1 所示，主要分为数据采集节点与无线AP 节点两部分。其中，Gt为t时刻的图模型；t表示数据采集时间；Vt是数据采集节点集，N=|V|为数据采集节点数，数据类型包括MAC 地址、RSSI 和物理空间位置；Ut是无线AP 节点集，包含室外节点和室内节点；Et是边集，表示数据采集节点与无线接入点(Access Point,AP)节点的关系，用边属性表示，M=|E|为边数；Xt用来表示节点属性和边属性，室内无线AP 节点属性对应楼层模型XYZ坐标和MAC 地址，室外无线AP 节点属性对应经纬度坐标和MAC 地址，边属性对应于RSSI。由于本文数据采集为同一时间段，物理空间中的几何和物质电磁特征基本不变，因此上述图模型简化为：G=(V,E,U,X)。

图1 定位图模型框架

RSSI 值进行均值滤波处理后，按照定位图模型中物理位置与WiFi 信息之间构建的节点、边及属性关系，将数据存入Neo4j 图数据库中。由于采集的整个校园数据量较大，全部可视化不便于说明指纹库中节点、关系及属性之间的关联，所以选取2 个室内数据采集点和3 个室外数据采集点进行解释说明，图模型指纹库如图2 所示。每一个圆圈为一个节点，连接两个节点的线为边，边上的值为属性。通过“ynu”节点将室内外所有数据关联整合在一起，“1”节点为室外部分，“0”节点为室内部分。RSSI 为数据采集节点与无线AP 节点之间的边属性，同一个无线AP 节点可能与多个数据采集节点关联。两个节点间存在关系时，其邻接矩阵的元素Aij取值为1，不存在关系时取值为0。在定位图模型基础上进行一次、二次室内外联合定位。

图2 定位图模型指纹库

1.2 定位算法

定位流程如图3 所示，用户上传采集待测点的WiFi信息数据，将数据按照指纹库指定格式存入数据库中，先通过Jaccard 相似度算法估计用户所在位置区域，区域标签判定室内外位置，室外是标签1，室内是标签0。若用户在室外，则直接返回采用Jaccard 相似度算法计算的经纬度坐标；若用户在室内，则在相似度算法基础上再通过机器学习算法进行二次定位，进一步得到用户的具体位置。

图3 定位流程图

图4 三次样条插值原理图

1.2.1 一次定位

Neo4j 扩展包APOC(Awesome Procedures Of Cypher)和ALGO(Algorithms)提供高效的数据管理、查询以及常用的图算法。实验中通过Jaccard 相似度算法进行一次定位，J(A,B)表示Jaccard 相似度系数，为两个集合中相似元素占不重复元素的比例。将待测点A数据处理后存入指纹库，与指纹库中数据进行组织、关联，令指纹库中的任意一个指纹点为指纹点B。待测点A和指纹点B数据形式分别为：

Jaccard 相似度算法计算方法如式(2)所示，其中Nm为待测点A中不同MAC 地址数量，Np为指纹点B中不同MAC 地址数量，Nh为待测点A与指纹点B相同MAC地址数量，计算出两个指纹点中共同的MAC 地址数量与所有不重复MAC 地址数量的比值即为J(A,B)，再分别计算出待测点A与指纹库中各个指纹点的相似度系数，系数最大的指纹点位置即为待测点A的估计位置。

1.2.2 二次定位

在Jaccard 相似度算法基础上进行一次定位后得到室内楼层数据和位置区域，再通过机器学习算法进行二次室内定位。将RSSI 值作为输入特征，(X,Y)位置坐标作为输出标签。数据结构如表1 所示。

表1 指纹库数据结构

实验中先通过相似度算法获取到楼层数据，不仅可以更加准确地确定楼层信息，而且缩小定位范围后，减小了机器学习定位时的数据量，从而减少系统定位时间。在机器学习算法中参数设置比较重要，直接关系到定位精度，支持向量机[11]和WKNN[12−14]两种机器学习算法主要参数设置如表2 所示。

表2 SVM 和WKNN 主要参数设置

WKNN 算法是在KNN 算法的基础上引入权重进行改进，使得定位误差更小，主要分为以下四步：首先分别根据式(3)计算出在线RSSI 向量与指纹库中第j个RSSI向量之间的欧式距离。

其中，RSSIi是在线待测数据的第i个RSSI 值；RSSIji是指纹库中第j个指纹点的第i个RSSI 值；然后将所有指纹点距离大小排序后选取最小的前k个位置指纹{(X1,Y1),(X2,Y2),…,(Xk,Yk)}；再根据式(4)计算这k个位置指纹的加权平均值Wj。

最后根据赋予不同指纹点的权重值计算得到待测点估计坐标(X,Y)，计算公式如式(5)所示。

1.2.3 三次样条插值

通过三次样条插值对室内数据进行扩充，三次样条插值[15]是一种改进的分段三次函数插值法。其主要思想是由多个小分段的三次多项式组成一个表面，使其满足最优平滑原则。三次样条插值基本原理如4 所示。

定义一个三次样条函数S(x)，如式(6)所示，而且该函数满足以下三个条件：

一是满足三次函数：将整个区间[a,b]分成多个小区间，每一个小的区间都是一个三次函数，如式(7)所示。

二是满足插值条件，即所有插值点都在一条曲线上；三是曲线光滑，即函数S(x)、其一阶导数S'(x) 以及二阶导数S''(x)在[a,b]上都连续。假定曲线上共有n个点，则分成n+1 个小区间，中间n−2 个点，则i=2,3,…,n−1，满足第二和第三条件的公式表达式如式(8)所示。

边界条件再补充两个方程即可求解出三次样条函数。三次样条函数的每一个小区间都是一个平滑的曲线，能够对插值区域进行平滑化处理，对于空间属性连续性较好的区域的插值精度高。

2 系统开发设计

定位系统是在Django 框架基础上，再结合Three.js技术以及前端开发技术实现。系统总体架构[8]如图5 所示，主要由数据采集、服务端和可视化三部分组成。数据采集部分按照场景规划采集路线，并在不同密度下采集物理空间位置信息和WiFi 信息；服务端由指纹库构建和在线定位两个模块构成，首先将物理空间位置信息与WiFi 信息组织关联起来建立定位图模型，并将数据存入Neo4j 图数据库构建位置指纹库，再通过相似度算法和二次定位方法进行在线定位。可视化部分通过SketchUp 和Three.js 技术,在导入的卫星地图基础上对云南大学呈贡校区进行校园三维建模，通过前端开发技术结合校园三维模型将在线定位返回的结果进行可视化。最后将定位测试系统部署在腾讯云服务器上，网址为http://114.132.53.243:8000/。

图5 系统设计框图

3 实验测试与分析

3.1 实验环境

云南大学呈贡校区已实现WiFi 信号全覆盖，实验环境为校园室外主要道路以及信息学院室内楼层，校园室内外无线AP 部署如图6 所示，主要部署在室内楼道、房间内和室外墙上。通过软件GetSensorData 2.0 进行数据采集，频率为50 Hz，每个点采集时长约30 s。主要分为室内和室外两部分，室外采集规划：室外采集根据实际环境进行疏密区分，对信息学院外围道路进行密采集，两个采集点间隔约5.5 m，格物楼、图书馆和软件学院等建筑外围道路采集间隔约11 m，建筑较少的宽阔区域采集间隔较大约30 m，共875 个数据采集点。室内采集规划：以信息学院大门处为原点，1 区走廊为X轴，2 区走廊为Y轴，空间楼层为Z轴建立三维立体坐标系。沿着室内楼层走廊间隔3 m 采集一次，每层楼约60 个采集点，共234 个数据采集点。

图6 室内外AP 分布图

通过定位图模型将采集的物理位置信息与WiFi 信息关联整合在一起，定位图模型中节点数量及其属性如表3 所示，共建立1 109 个数据采集节点，11 651 个无线AP 节点和62 176 个节点属性。

表3 图模型节点及其属性

3.2 系统功能测试

用户通过手机软件采集待测点WiFi 信号数据，将数据上传本系统后可直接显示用户位置信息。图7 是室内定位结果可视化，待测点位置显示在信息学院4 楼3407房间外面。

图7 定位结果可视化

3.3 实验结果与分析

室外通过相似度算法进行一次定位，在室外采集间隔11 m 时选取20 个测试点，采集间隔5.5 m 时选取25个测试点，室内采集间隔3 m 时，随机选取20 个测试点，得到相似度系数和平均定位误差如表4 所示，可以看出，数据采集密度、相似度系数和定位精度是一个数量级。数据采集间隔越小，相邻数据采集点采集到的共同MAC 地址越多，则Jaccard 相似度系数越大，定位精度越高。

表4 不同采集密度定位结果

通过相似度算法实现一次定位后，在其基础上再通过机器学习算法进行二次定位，进一步提高室内定位精度。其中，k值参数对WKNN 算法定位结果影响较大，设定k值较小时容易受指纹库中个别奇异值影响，较大时则会受指纹库中距离较远的指纹点影响，造成较大定位误差。实验中选取33 个样本测试点分别计算出k值取1 到10 时的平均定位误差，从图8 可以看出k=3 时平均误差相比较其他k值平均误差最小，所以本文中WKNN 算法中参数k为3。

图8 不同k 值定位误差

为了避免个别特殊测试点对定位结果造成影响，测试点选取应从样本容量、与离线位置是否重复以及不同区域多方面考虑。为了进一步提高室内定位精度，对室内指纹库进行三次样条插值扩充，不同算法插值前后定位平均误差如表5 所示。

表5 不同算法平均定位误差

样本N1 和N2 中的测试点采集位置与离线指纹库中采集位置不重复，样本N3 是在转折区域位置进行采集，所以样本N1、N2 和N3 平均误差较大，样本N4 则是与离线指纹库中数据位置重复采样，定位平均误差较小。从表5 可以看出，通过三次样条插值后定位精度都有所提高，其中WKNN 算法插值前定位平均误差为1.97 m，插值后3B-WKNN 算法定位平均误差为1.66 m，平均误差减小0.31 m。

对于室内外过渡区域，选取信息学院入口区域为实验场景，以门为边界，向内和向外分别采集15 和20 个测试点，实验结果如图9 所示，门外部区域仅采用一次定位粗略估计以及门和墙壁遮挡，使得其定位误差变化较大。过渡区域最大定位误差为4.69 m，平均定位误差为1.91 m，实验表明本文定位方法在过渡区域较为稳定，而且避免了频繁切换的问题。

图9 过渡区域定位结果

通过相似度算法先确定待测点楼层位置信息，后续通过机器学习进行二次定位时只需要用到确定的某一楼层的RSSI 值，其余楼层数据对定位精度不影响，减小了机器学习的计算时长。不同定位方法所需时间如表6所示。

表6 分级定位计算时间比较 （s）

从表6 中一次定位时间对比可知，相同数据量Jaccard 算法定位时长远小于WKNN 算法，针对较大定位场景比较有优势。由于WKNN 算法需要所有指纹点的数据维度一致，采集的指纹点增加以及无线AP 增多时，需要补充大量−110 dBm 数据，导致其定位时间较长难以达到实时定位要求，而定位图模型将室内外物理空间位置和WiFi 信息融合在一起，结合Jaccard 相似度算法高效计算、分析以及处理能力，可以极大地节约定位时间。但是结合表4 和表5 分析可知，Jaccard 相似度算法定位精度与数据采集密度较为密切，且定位精度小于WKNN算法。因此，基于定位图模型的二次定位方法不仅可以提高室内定位精度，而且减小了系统延时。

4 结论

本文针对云南大学呈贡校区建立了基于WiFi 信号室内外联合定位图模型，有效地将室内外物理位置信息与WiFi 信息融合在一起，通过二次定位提高定位精度、减小系统延时，最后设计开发了基于WiFi 信号的室内外联合定位系统，避免了组合定位技术在过渡区域切换定位方式的问题。下一步工作将从定位精度和系统功能两方面对定位系统进行改进和扩充，定位精度可以通过融合其他传感器信息，如加速度传感器、陀螺仪和气压计等；本文定位方法可以降低系统延迟，但是后期还需进一步完善系统、提高系统整体响应能力，以及丰富系统功能，如添加导航功能等。