曾衍华,单志龙,2,陈之彧

1(华南师范大学 计算机学院,广州 510631)

2(华南师范大学 网络教育学院,广州 510631)

1 引 言

在各种移动终端设备广泛普及的物联网时代,人们开始将目光聚焦于基于位置的服务(Location-Based Service,LBS)[1].人类通常有超过80%的时间在室内活动,医院、商城、矿井等各种室内场景都有大量的定位需求[2].但由于室内环境的复杂多变,GPS、北斗等成熟的卫星定位技术难以应用到室内定位中.常用的室内定位技术有红外、蓝牙、超宽带[3]、Wi-Fi[4]、地磁[5]、惯性导航等,其中Wi-Fi定位技术具有无需额外设备、信号覆盖广、采集成本低等特点,是室内定位领域中一个主要的研究方向.

Wi-Fi室内定位主要有两大类:基于测距的方法和基于指纹的方法.前者通过Wi-Fi信号传播模型计算待定位节点到若干Wi-Fi接入点(Access Point,AP)的距离,然后用三边定位等几何算法进行定位;后者则把定位环境的每个位置都用一个唯一的“指纹”来表示,并用特定的指纹匹配算法确定目标位置.前者需要预先知道AP的位置并使用额外设备精准测距,难以应用于实际环境[6];而后者只通过采集若干指纹即可进行定位.指纹定位算法的流程主要有离线指纹库构建阶段和在线阶段,离线阶段将定位区域进行划分成若干网格点,并在每个网格点上采集由若干AP发送的RSSI作为指纹,不同位置的指纹构成离线指纹库;在线阶段首先采集待定位区域的RSSI指纹,然后使用指纹定位算法将其和离线指纹库中的指纹进行匹配,得到节点的位置估计.

目前常用的指纹匹配算法有K近邻(K-Nearest Neighbors,KNN)[7]、加权K近邻(Weighted K-Nearest Neighbors,WKNN)[8]和支持向量机(Support Vector Machine,SVM)[9]等,但由于RSSI指纹波动性较大且存在噪声,这类经典机器学习算法难以实现较高的定位精度[10].深度学习作为机器学习的一个分支,可以更好地拟合RSSI指纹与特定位置之间的非线性映射关系[11].因此,人们将许多深度学习方法运用到室内定位当中,如人工神经网络(Artificial Neural Network,ANN)[12]、堆叠自动编码器(Stacked Auto Encoder,SAE)[13]、卷积神经网络(Convolutional Neural Network,CNN)[14]和循环神经网络(Recurrent Neural Network,RNN)[15]等.其中,RNN擅长处理序列数据,由于用户在室内环境中的移动速度有限,RNN可以借助指纹中的时序信息来区分指纹相似的不同位置,提高定位精度.Chen等人[16]使用Wi-Fi路由器以50hz的高频率扫描手机获取RSSI时间序列,并使用深层RNN网络来进行定位,但该方法需要特定的路由器,且在线定位时间长.文献[17]基于长短期记忆网络(Long Short-Term Memory,LSTM)、门控循环单元(Gate Recurrent Unit,GRU)等RNN变体提出了P-MIMO模型,利用连续的RSSI测量值和轨迹信息提高精度,达到了最低0.75m的平均误差,该方法需要获取用户的初始位置,实际情况中难以实现.

上述算法具有较好定位效果的前提是离线和在线阶段使用相同的设备,而当在线阶段使用与离线阶段不同的移动终端设备(即设备存在异质性)时,在相同位置采集的RSSI指纹会产生较大变化,进而降低定位精度[18].目前针对设备异质性问题有两种主流方案:1)在离线阶段使用不同的转换函数来校准RSSI指纹[19],但难以适应实际场景中大量型号各异的终端设备;2)采用无校准的方法.Zou等人[20]根据不同设备采集的RSSI指纹形状相似这一现象,对原始指纹进行标准化后得到标准位置(Standard Location,SL)指纹,并使用WKNN进行定位.但由于实际场景中RSSI存在缺失值,不同手机的RSSI采样值的形状不一定相似,该方法不能很好地缓解设备异质性问题.文献[21]使用相邻AP之间RSSI的差值构造信号强度差(Signal Strength Difference,SSD)指纹,SSD指纹的缺点是只考虑了相邻AP的差异,且会丢失部分信息.

为了更好地缓解设备异质性问题并提高定位精度,本文将RSSI指纹变换为差分矩阵(Difference Matrix,DM)指纹,使用CNN来提取差分矩阵的特征,并引入RNN结合历史位置信息进行定位.本文的主要工作如下:

1)针对SSD指纹只考虑相邻AP且会丢失特征的问题,构造了一种能更好地缓解设备异质性问题的差分矩阵指纹;

2)基于RSSI指纹的分布特点提出了一种数据增强算法,在每个网格点上生成大量和原始指纹分布接近的新指纹,减少离线阶段指纹采集工作量;

3)提出了一种基于CNN和RNN的室内定位模型CRDM(CNN-RNN based indoor localization model using difference matrix),该模型可以有效结合CNN和RNN两者的优势,在使用不同型号的设备进行定位时亦能达到较高的定位精度;

4)根据行人在室内环境中的移动规律提出了一种轨迹生成算法,以每个网格点为起点随机生成大量轨迹作为CDRM模型的训练数据,然后在一个真实的室内环境中进行了一系列实验,验证了CRDM模型的性能.

2 RSSI信号特征分析

2.1 RSSI信号分布

Wi-Fi信号在自由空间传播的过程可以用自由传播模型描述[22],而在复杂的室内环境中,由于障碍物遮挡、多径效应等的存在,一般使用对数正态模型[23]来建模Wi-Fi信号的衰减.某点上的RSSI采样值可计算如下:

(1)

2.2 RSSI信号的设备异质性

根据信号的自由空间传播模型[22],有:

(2)

其中,PAPi,GAPi,λAPi分别为AP的传递功率、天线增益以及发射载波的波长,L为系统损耗因子,Gdevice则是终端设备的天线增益.将式(2)代入式(1)中可以发现,当终端设备不同时,不同的Gdevice会在相同的位置测量到不同的RSSI值,从而产生设备异质性问题.

3 定位系统描述

本文提出的定位系统的整体工作流程如图1所示.离线阶段构建RSSI指纹库,并使用轨迹生成算法随机生成大量轨迹供模型训练.在线阶段加载训练好的模型,使用终端设备采集待定位区域的RSSI指纹,并结合模型上一时刻的预测坐标,给出当前时刻的位置.

图1 系统框图Fig.1 System block diagram

3.1 离线阶段

3.1.1 指纹库构建

离线阶段首先将待定位区域均匀划分为若干个网格点,然后在每个网格点上记录其真实坐标,并使用移动终端设备按照指定的采样频率采集若干RSSI值,得到离线指纹库.令网格点数为Ngrid,每个点上采集RSSI指纹的次数为Nrss,AP个数为Nap,则指纹库D及D中第i个网格点Ii=(xi,yi)对应的指纹Di可表示为:

D=(D1,D2,…,DNgrid)

(3)

(4)

(5)

3.1.2 数据增强

数据增强(Data Augmentation)通过扩充原始数据提升模型性能,并引入噪声数据提高模型的泛化能力.文献[25]中的实验表明,数据增强可以提高基于深度学习的室内定位方法的定位精度.在实际定位过程中,部分型号较旧的智能手机搭载的低版本Android系统(如Android 7、 Android 8)无法修改RSSI的采样频率,无法获取大量数据训练模型,进而影响模型的定位精度.

实际情况中,由于人员流动等环境变化,RSSI容易出现缺失值,图2是使用Redmi K40手机在一个位置上采集2分钟得到的RSSI采样数据(缺失数据用-100dBm填充):

图2 某个指纹点上RSSI采样值的分布Fig.2 Distribution of RSSI sampling values on a fingerprint point

可以看出,每个AP的RSSI采样值都有缺失,而在不考虑缺失值的情况下,RSSI采样值近似正态分布.基于2.1节对RSSI分布的理论分析及实际数据的分布特点,本文在保证原始数据分布整体不变的情况下,按如下步骤进行数据增强:

1)对指纹库D中某个网格点的指纹Di,初始化新指纹RSSI_Newi;

3)对Di中每个AP的采样值执行②,得到RSSI_Newi;

4)对任意Di执行Naug次①～③,得到增强后的指纹库.

3.1.3 SSD指纹和差分矩阵指纹

SSD指纹使用相邻AP的RSSI值的差来缓解设备异质性问题.令某点上的RSSI指纹为RSSI=(r1,r2,…,rNgrid),根据式(1)和式(2),则该点上APi和APj的SSD值,以及所有相邻AP构成的SSD指纹可分别表示如下:

(6)

SSD=(r1-r2,r2-r3,…,rNap-1-rNap)

(7)

可以看出,相比式(1)的RSSI值,式(6)不包含Gdevice,这表明SSD指纹可以缓解设备异质性的影响.但SSD指纹相比原始RSSI指纹缺失了一维特征,这意味着当离线和在线阶段的终端设备相同时,定位精度会降低.为了扩展SSD指纹的维度以更好环境设备异质性问题,本文将原始RSSI指纹转换成差分矩阵(Difference Matrix,DM)指纹:

(8)

相比SSD指纹,DM指纹还考虑了不相邻AP之间的RSSI差值,拥有更多的特征,当在线阶段使用不同的设备进行定位时具有更好的鲁棒性.

3.1.4 轨迹生成

为了利用定位目标的历史位置信息,本文提出的定位模型中引入了RNN结构,其训练数据为轨迹上点的坐标及对应的RSSI指纹.由于目标的移动速度有限,离目前位置越近的点被选作轨迹的下一个点的概率越大.基于此规律,本文取RSSI采样周期Δt=1s,行人最大移动速度vmax=1.8m/s,采样周期内的最大移动距离σ=vmax×Δt=1.8m,按如下的步骤生成大量轨迹数据:

1)对指纹库中每个网格点li=(xi,yi)计算其它网格点lj=(xj,yj)到该点的欧氏距离dij,得到欧氏距离矩阵d;

(9)

(10)

③使用矩阵p生成轨迹.对当前点li,在矩阵p的第i行中,按概率选择轨迹的下一个点lj.pij越大,则lj成为下一个点的概率就越大;

④以每个网格点为起点重复步骤①～步骤③,生成若干长度为的轨迹.

3.1.5 CRDM定位模型

CRDM定位模型使用CNN提取差分矩阵指纹的隐含特征,并引入RNN考虑移动目标的历史位置信息进行定位.其中,CNN模型的结构基于轻量级的卷积神经网络LeNet-5[26].由于差分矩阵的维度(本文为11×11)较小,为了防止池化操作丢失指纹信息,本文去除了LeNet-5中的池化层,并在卷积层之间添加批归一化层(Batch Normalize Layer)以加快模型收敛速度;RNN单元为门控循环单元GRU,GRU解决了RNN的梯度爆炸等问题,且相比于LSTM的计算复杂度更低.模型结构如图3所示,本文实验环境中AP个数为11,模型的定位流程如下:

图3 模型结构Fig.3 Model structure

输入层:将当前时刻采集的指纹RSSIt(大小为1×11)按式转换为大小为11×11、通道数为1的差分矩阵指纹,然后输入卷积层C1;

卷积层C1,包含6个大小为3×3、移动步长为1的卷积核,输出特征图的大小为6×9×9;

卷积层C2:包含16个大小为3×3、移动步长为1的卷积核,输出特征图的大小为16×7×7;

展平特征图:将特征图展平成大小为1×784的一维特征向量,输入到全连接层F1;

全连接层F1:包含80个神经元;

全连接层F2:包含11个神经元;

RNN层:该层包含两个GRU单元,GRU的隐含层神经元个数为100,输出为1×13的特征向量;

全连接层F3:包含2个神经元,输出为当前时刻的定位坐标.

CRDM模型使用轨迹数据集进行训练,训练步骤如下:

1)对数据集中任意一条轨迹l上某时刻t对应的轨迹点lt,将模型上一时刻t-1的预测坐标cort-1进行标准化:

(11)

其中μ和σ分别为网格点中所有坐标的均值和标准差;

4)对上的全部点重复步骤①～步骤③,并对轨迹上每个点的误差求平均,作为模型在该条轨迹上的预测误差;

5)按上述步骤,对所有轨迹数据进行训练,视为一次迭代.使用自适应调节学习率的Adam优化器更新模型参数,迭代若干次直至模型收敛.

3.2 在线阶段

根据图1,在线阶段的定位过程如下:

1)采集待定位区域的RSSI指纹,并将指纹转换为DM指纹;

2)加载模型参数,并获取模型上一时刻的定位坐标,将标准化后的坐标与指纹一同输入到CRDM模型中进行定位.初次定位时,将初始位置的DM指纹输入到CNN模型中以进行初始位置估计;

3)得到当前定位结果并保存,待下一时刻定位时使用.

4 实验环境和结果分析

为了验证CRDM模型的有效性,项目组开发了一个基于Android手机的室内定位APP,使用智能手机Redmi K40、Redmi K30i、Honor V8及Vivo Nex3采集数据并作为定位终端,并在一台服务器上训练及部署定位模型.定位终端和服务器的配置分别如表1、表2所示.

表1 定位终端配置Table 1 Locate terminal configuration

表2 服务器配置Table 2 Server configuration

4.1 实验环境

本文的所有实验在华南师范大学石牌校区计算机学院3楼某实验室中进行,实验室的平面图如图4所示.实验环境的面积为260m2,其中部署了50个大小1.8m×1.8m的网格点,以及11个型号参数不同的路由器.为保证实验数据的可靠性,每个网格点以1秒为周期,采集120次RSSI值.该室内环境包含若干办公设备、书架、学生工位等障碍物,是日常生活中较为常见的一种室内环境.此外,在实验过程中,大量实验室成员在区域内正常活动.

图4 实验环境平面图Fig.4 Plan of the experimental environment

4.2 实验步骤

1)对每个网格点使用四台智能手机采集RSSI构成指纹库,并以当前点为起点随机生成若干轨迹数据,构成轨迹数据集;

2)训练模型.选取Redmi K40和Vivo Nex3为训练设备,使用分层采样的方式将训练设备对应的指纹库D按4∶1的比例划分为训练指纹库Dtrain和测试指纹库Dtest,然后在服务器上使用训练集的数据训练并保存模型;

3)评估模型.为了保证训练和测试指纹库之间不存在重复数据,训练和测试设备相同时,在Dtest上评估;否则在测试设备对应的原始指纹库上评估.

本文选取CRDM、CNN(使用卷积神经网络提取差分矩阵指纹的特征进行定位)、P-MIMO[17](使用RNN模型,给定初始位置并结合历史位置信息进行定位)、WKNN(经典的加权K近邻定位算法)、WKNN-SL[20](使用标准位置(SL)指纹结合WKNN算法进行定位)、WKNN-SSD[21](使用信号强度差(SSD)指纹结合WKNN算法进行定位)等定位算法进行对比实验,实验参数如表3所示.

表3 实验参数Table 3 Experimental parameters

4.3 实验结果分析

4.3.1 加入模型上一时刻预测坐标对定位精度的影响

本节在设备组合Redmi K40和Vivo Nex3上探究加入模型上一时刻预测坐标cort-1对CRDM、P-MIMO模型定位精度的影响,实验结果如图5所示.

图5 加入上一时刻预测坐标前后模型的定位误差Fig.5 Localization error of the model before and after the predicted coordinates at the last moment is used

显然,两个模型在加入cort-1后,平均和最大定位误差都明显下降,说明该操作可以让模型更好地将定位结果限定在某一区域内,缓解设备异质性问题.此外,由于CNN模型可以给出较准确的初始位置(平均定位误差1.977m),CRDM-2在无需初始位置的情况下,平均定位误差和CRDM-3接近.基于上述结论,在接下来的实验中,本文使用的CRDM模型均为CRDM-2.

4.3.2 数据增强对定位精度的影响

本节在设备组合Honor V8和Redmi K40进行实验.由于Honor V8系统版本为Android 8.0,无法修改RSSI采样频率,每个网格点在2分钟内只采集了10个不重复的RSSI值.使用3.1.2节所述的数据增强算法对每个网格点生成120个新指纹,并在CRDM、P-MIMO模型上对比数据增强前后的定位精度,实验结果如图6所示.

可以看出,两个模型在训练数据增加后,平均、最大定位误差明显降低,说明数据增强可以缓解RSSI采样值过少对定位精度的影响,减少指纹采集工作量并提升模型性能.

4.3.3 轨迹长度对定位精度的影响

基于RNN的定位模型在每个训练时间戳都会更新模型的权值和隐含状态,较大的轨迹长度L可以让模型结合更多历史信息,也会累计更多的历史定位误差[27],进而影响定位精度.图7显示了在设备组合Redmi K40和Vivo Nex3上不同的L对CRDM模型定位精度的影响.

图7 不同轨迹长度下CRDM模型的定位误差Fig.7 Localization error of CRDM model with different trajectory lengths

可以看出,随着L的增加,历史定位误差的累计增大了模型的最大定位误差,进而使平均定位误差略微增加.故本文选取L=5为最优轨迹长度.

4.3.4 模型对比

为了评估离线和在线阶段的定位设备相同或不同时CRDM模型的定位性能,本节将CRDM模型与CNN、P-MIMO、WKNN、WKNN-PA、WKNN-SSD模型按4.2节的步骤进行对比实验.根据前文的实验结果,对每个网格点使用数据增强生成120条新指纹,并以每个点为起点分别随机生成240、20条长度为5的轨迹进行训练、测试.各模型的平均定位误差如表4所示.

表4 不同模型在不同设备上的平均定位误差(m)Table 4 Average localization error of different models on different devices(m)

可以看出,训练和测试设备相同时,CRDM、CNN和P-MIMO这3个深度学习模型都能实现较高的定位精度,优于WKNN等算法.说明当设备相同时,深度学习模型可以有效的提取指纹特征以进行定位.此外,使用WKNN算法进行定位时,SL和SSD指纹在相同设备上的定位精度均低于原始指纹,且SSD指纹和原始指纹相比丢失了一维特征,定位精度下降幅度更大.

当训练和测试设备不同时,SL、SSD及DM指纹都能一定程度上缓解设备异质性问题,且使用DM指纹的CNN模型与WKNN-SL、WKNN-SSD算法相比具有更好的定位性能.P-MIMO模型在给定初始位置及结合历史预测坐标的情况下,可以缓解设备异质性造成的指纹空间模糊性问题,提升定位精度.而CRDM模型结合了DM指纹和RNN模型的优势,并在无需得知初始位置的前提下借助模型上一时刻的预测坐标修正当前定位结果,进一步降低了设备异质性的影响,达到了最低1.356m的平均定位误差,且在所有异质设备上的表现都明显优于其他定位算法.

4.3.5 定位实时性分析

本节从定位时间的角度评估CRDM模型的性能,在同一台计算机上计算各算法的平均定位时间,实验结果如表5所示.

表5 不同模型的平均定位时间(ms)Table 5 Mean localization time of different models

其中WKNN、WKNN-SL和WKNN-SSD算法耗时最短,且WKNN-SL由于需要计算原始指纹的均值及标准差以进行标准化操作,耗时稍长;SSD指纹相比原始指纹减少了一维特征,故定位时间更短.WKNN算法需要匹配指纹库中的所有指纹并计算欧式距离,令n和k分别为指纹库中的网格点数和AP个数,则WKNN算法的时间复杂度为O(n×k).当定位区域较大或AP个数较多时,其在线定位时间会明显提高.相比于WKNN算法,CRDM、CNN和P-MIMO等深度学习模型定位时间较长.其中CRDM模型由于模型结构相对复杂,定位时间最长.但CRDM等深度学习模型经训练后,只需加载模型参数进行一次前向传播即可定位,无需匹配指纹库,对定位区域大小不敏感,且从时间数值上看,其定位时间亦能满足实时定位的需求.

5 结 论

本文提出了一种基于差分矩阵指纹的室内定位模型CRDM.CRDM使用CNN处理差分矩阵指纹以缓解设备异质性问题,并使用RNN考虑用户移动轨迹上一系列RSSI测量值之间的相关性,将定位过程等效为轨迹预测问题.在离线阶段,为解决部分手机难以大量获取RSSI采样值的问题,使用数据增强算法扩充指纹库,并使用轨迹生成算法获取大量轨迹供模型训练,在减少指纹库构建工作量的同时提高模型的泛化能力.在线定位阶段,CRDM结合当前位置对应的差分矩阵指纹及模型上一时刻的预测坐标进行定位,并使用CNN进行初次估计以摆脱对初始位置的依赖.实验表明,CRDM模型在保证实时定位的前提下,离线、在现阶段使用相同或不同设备时,定位精度均优于P-MIMO、WKNN等算法.