基于深度神经网络的WiFi室内定位算法研究

李志祥， 丁绪星， 陈兴盛， 冯友宏， 丁阁文， 周理政

(1.安徽师范大学 物理与电子信息学院，安徽 芜湖 241000，2.安徽华东光电技术研究所，安徽 芜湖 241000)

由于机场、养老院、医院、车站等诸多场所对位置服务的需求，室内定位已经渗透到人们生活的方方面面。目前WiFi已经覆盖了生活中大部分的公共区域及家庭，因此，基于WiFi的室内定位算法研究成为国内外的研究热点，也取得了很多成果，如KNN(K-Nearest-Neighbors)算法[1]、WKNN(Weighted K-Nearest Neighbors)算法[2]和K-Means(K-MeansClustering Algorithm)算法[3]等定位算法。WiFi的每个无线接入点(Access Point,AP)都有唯一的物理地址，并且在一段时间内，无线接入点(AP)的信号强度不会发生改变，WiFi终端可以持续扫描和收集周边AP信号，获取其信号强度(Received Signal Strength,RSS)，在室内WiFi定位场景中，基于位置指纹的定位方法被广泛研究和采用[4-6]。该方法是在室内放入一定数量的无线接入点，使得整个室内都被WiFi信号所覆盖，然后通过移动设备收集各个不同位置获得无线接入点的RSS和MAC地址，每个位置获取的来自各个AP的RSS组成一组向量，在不同位置会产生一个阵列RSS向量，将这些向量与室内位置进行匹配存储在数据库中。

基于WiFi的位置指纹定位算法一般分为离线和在线两个阶段[7]。离线阶段用于生成数据库，数据库用于估计在线阶段的位置。经典的算法如KNN，由于其选择一个测量点周围固定数量的最近K个邻点来计算测量点的位置，从而降低了定位精度，效率也不高。在文献[8]中，Changgeng Li等人提出了一种改进的加权KNN算法来计算测点的最终定位坐标，但其在线阶段需要与很多的位置指纹数据进行匹配定位，定位效率也较低。研究者试图用聚类算法来提高效率，如ChoRong Park在KNN算法中采用改进的K-Means聚类方法进行高效准确的分类[9]，H.Wang等人研究了空间聚类、K-Means聚类和亲和传播聚类(SAAP)三种聚类算法的定位性能[10]。这些成果在一定程度上提高了定位精度，降低了消耗，但仅提出单边方案。也有研究者试图用机器学习的算法来提高室内定位性能，如贝叶斯分类(Bayes Classification)算法[11]、AdaBoost算法[12]和支持向量机(Support Vector Machines,SVM)算法[13]等算法都应用于室内定位。但是对于这些传统的机器学习算法，当室内环境要求较高时，数据的训练效果较差，灵活性不强，相应的研究成果不多。

针对以上问题，本文提出了一种基于深度神经网络和泰森多边形的位置指纹定位算法DV-WKNN(Deep neural networks and Voronoi-WKNN)，该算法采用了深度学习算法和泰森多边形结合的方法来进行定位。利用深度学习算法较强的非线性学习能力对环境参数的训练、建模，实现待测点的物理位置预测。再将预测的物理位置点作为离散点构建泰森多边形，利用泰森多边形来确定定位区域。在定位区域内，通过计算已知点的平均环境偏差值来改进WKNN定位算法，从而实现了精确定位。

本文的主要贡献有3个方面：

1)本文引入了深度学习算法，利用其较强的非线性学习能力，实现对定位空间的信号强度特征的学习，及待测位置的预估计；

2)遍历时间，引入了泰森多边形，进行定位区域的动态划分，从而提高定位效率；

3)本文在精确定位时，加入了环境平均偏差值，在WKNN定位算法的基础上进行位置修正，从而提高了定位的精度。

1 DV-WKNN算法

图1 基于深度神经网络的WiFi室内定位算法流程图Fig.1 The process of indoor positioning algorithm for WiFi based on deep neural network

本文提出的定位方法主要通过神经网络算法和泰森多边形结合的方法来实现位置的估计，利用神经网络对已建立的指纹数据库进行训练，根据每次测试集的推理结果，动态调整相应的网络结构，以获得最优网络参数。在位置估计阶段，将采集的RSS值，通过已保存的神经网络模型，推理得到其对应在数据库中的物理位置坐标，将此物理位置坐标作为初位置估计点。为了得到更精确的物理位置，则以初位置估计点建立泰森多边形，将整个定位区域划分为若干个小区域，再在每个包含初略位置估计点的小区域内通过改进的WKNN算法，获得最终精确的物理坐标。具体流程如下：

该方法主要通过收集无线接入点(AP)的RSS值来进行当前位置的确定，定位的步骤分为线下训练和线上定位两个阶段。线下训练阶段即离线阶段，通过仿真平台获取到RSS值并建立指纹数据库，将指纹进行滤波以及预处理，再将处理的数据作为构建的深度神经网络的输入，进行训练。线上定位即在线阶段时，系统接收来自AP的实时数据，通过定位模型的预测坐标建立泰森多边形区域，在设定的区域内通过改进的WKNN算法预测用户的位置。算法流程如图1所示。

1.1 深度学习模型的构建和训练

本文算法中采用深度神经网络的主要目的是获得待测用户的初位置估计点，因建立的指纹数据库中不可能包含待测区域中所有的RSS值及其对应的物理坐标点，故采用采用神经网络算法，可以快速定位到待测点所在区域，为下一步的精确定位增加了可靠性。

相比较传统的定位算法，本文引用神经网络模型结构，一是提取RSS值的基本特征，二是对室内定位问题进行回归。回归分析的目的是实现学习本地化功能，使用神经网络近似指纹映射到该点的估计位置。与传统的KNN等定位算法相比，该方法将模式匹配和后处理相结合，一次定位。另一方面，接收到的RSS值没有取平均值，只是归一化处理作算法的输入，可以防止在平均处理中造成的信息损失。

图2 深度神经网络模型训练步骤Fig.2 The training model of deep neural network

将处理后的RSS数据集，拆分为训练集和测试集，经过多轮训练，获得可靠的神经网络参数模型，训练步骤如图2所示。深度神经网络的模型相关参数如表1所示，主要由6层构成，其每个隐藏层的神经元由10-20-20-20-20-10构成，因本文所使用数据集类型较为简单，若直接引用现有的成熟网络模型，将大大的浪费训练开销。因此，本文根据RSS数据类型设计相适应的网络架构，经过每次测试集获得的推理结果，调整网络层数及相应层数的神经元数量，以保证预测正确率的同时减少推理时间。因数据集在进行训练之前已归一化预处理，故本文在每一层隐藏层之间采用了ReLU(Rectified Linear Unit)激活函数[15]，解决RSS数据之间的非线性可分问题且防止梯度消失的出现。在每层的优化算法上选择NWM-Adam算法[16]，与传统的优化算法相比，其利用非单一的学习率来更新权重，提升系统的学习效率。在输出层，采用了Softmax函数[17]，实现多分类效果，保证所有输出神经元的概率之和为1，每个输出对应的[0,1]区间的数值就是该输出的概率。在应用时取概率最大的输出作为最终的预测，将其预测结果作为初位置估计点。

经过合适的epoch设定，调用Tensorflow的可视化工具tensorboard观察发现，当epoch为1800时，loss函数达到收敛的状态，其预测准确率达到98.6%，损失率接近于0.038，即得到可靠的深度神经网络模型，结果如图3、4所示。

1.2 基于预测点构建泰森多边形

利用深度学习算法获得的初位置估计点，作为泰森多边形的离散点进行区域的划分。泰森多边形是指在特定的二维空间内，给定一个点集，根据该点集将空间划分为多个多边形集合，在每个多边形内有且仅有一个该点集中的点，并且多边形内的任何一个点到相应点集中的点的距离最近，该多边形称之为该点的Voronoi区域。本文将深度神经网络算法模型获得的预测点作为构建泰森多边形的离散点，再根据文献[18]所述的泰森多边形的具体实现步骤，实现区域的泰森多边形分割，结果如图5所示。

图6展示了在20m*20m的定位环境中，通过泰森多边形划分的定位区域，以满足下一步的精确定位。其中，红色“+”代表参考点RPs，绿色“☆”表示待测点经神经网络模型获得的预测点TPs，TPs作为构建泰森多边形的离散点，蓝色“o”表示无线接入点Aps。

表1 深度神经网络相关参数Table 1 Related parameters of deep neural network

1.3 改进的WKNN算法

加权K近邻算法是WiFi定位中比较常用的算法，计算在线采集的RSS向量与指纹数据库中的RSS向量之间的欧式距离，选择K个最近距离的参考点作为定位标签，并根据距离的权重作为该标签的权重值，得到估计的坐标作为结果[19]，如公式(1)，公式(2)和公式(3)：

(1)

其中，N是AP的数量，RSSi是第i个AP中接收到的待测点的信号强度，RSSij是第i个AP接收到的第j个RP的信号强度，Dj是待测点信号强度与第j个RP信号强度之间的欧氏距离。

(2)

(3)

其中，wi为所选第i个RP的权值，η为修正系数，(xi,yi)为所选的第i个RP的位置，(x,y)为测点位置。

图3 accuracy的变化曲线

图4 loss的变化曲线

图5 基于预测点构建泰森多边形图

图6 20m*20m的环境区域划分图

在加权K近邻算法中，目标标签选择K个最近的参考邻居标签，再根据距离权重的比例来计算坐标位置。在改进的加权K近邻算法中，本文首先得到具有K个最近参考邻居标签的目标位置，对已知位置的K个参考点进行加权K近邻计算，得到他们的定位坐标，然后计算原始位置与定位位置之间的误差，将偏差值相加并取平均值，如公式(4)：

(4)

(xi′,yi′)代表参考点的K个近邻点通过WKNN算法计算的位置坐标；

(xi,yi)代表参考点的实际坐标；

(△x,△y)表示当前环境下的平均偏差值。

在划分的泰森多边形的各个区域内，通过WKNN算法计算出目标点的位置坐标，再将此坐标加上该网络的平均偏差值，获得最终位置坐标，如公式(5)：

(x,y)=(x′,y′)+(△x,△y),

(5)

(x′,y′)代表待测点的K个近邻点通过WKNN算法计算的位置坐标；

(x,y)代表的最终定位位置坐标。

2 仿真结果和分析

2.1 指纹数据的采集及处理

室内环境由于墙壁和室内遮挡物等存在，实际的信号接收值比理想传播模型要小，根据文献[14]的研究结果，采用对数正态模型可以更好模拟室内无线信号损耗，如式(6)：

(6)

其中，PL(d),PL(d0)接收信号强度与参考距离d0米处接收信号强度，单位为dB。

n：环境衰减系数。

Xσ：零均值的高斯分布随机变量，其标准差为σ，用于模拟噪声误差，单位为dB。

将其转化为接收信号强度，可表示为公式(7)：

(7)

其中RSS(d)，RSS(d0)接收信号强度与d0米处接收信号强度，单位为dB。

n：路径损耗系数。

Xσ：零均值的高斯分布随机变量，其标准差为σ，用于模拟噪声误差，单位为dB。

本文的仿真实验均采用上述对数路径损耗模型。经过多次实验发现，变量取值如表3所示时，路径损耗模型可以较好模拟存在障碍物的室内环境。

通过仿真收集的数据，所获得的RSS信号的范围在-101dB与-60dB之间。由图7可知，直接获取的RSS值波动较大且存在奇异值，不适合作为深度神经网络的输入。用公式(8)做归一化处理，将RSS值设置于0-1之间。如图8所示。

表2 对数路径损耗模型参数Table 2 Logarithmic path loss model parameters

(8)

其中，RSSij为参考点的原始信号强度数据，RSSij′为归一化处理后的信号强度数据，RSSmin为数据库中收集到的最小信号强度值；RSSmax为数据库中收集到的最大信号强度值。

图7 原始的RSS值

图8 处理后的RSS值

2.2 权值w的最优修正系数η选取

针对公式(2)的η选取，设定了20m*20m，30m*30m的仿真环境，记录50个待测点的平均误差。由图9可知，在20m*20m的网络中，最优修正系数η为1.3，在30m*30m的网络中，最优系数η为1.5。实验表明，选择η为1.3作为本文验证算法的最优修正系数频率较高。

2.3 算法的定位性能比较

本节中，将采用本文2.1给出的路径损耗模型进行数据采集和处理，模拟和验证本文所提出的算法(DV-WKNN)的性能。

在仿真场景中，测试空间的网络环境大小分别设为20m*20m,30m*30m和50m*50m，相邻RP之间的距离间隔为2米，在网络空间的四角分别放上四个AP，将本文提出的DV-WKNN算法与KNN算法、WKNN算法和基于K-Means聚类的KNN指纹定位算法进行性能比较。

表3、图10为不同网络中不同算法之间的平均误差的具体数值表与条形图，可知DV-WKNN算法明显优于KNN、K-Means聚类的KNN和WKNN算法，其中KNN算法性能最差。结果表明，与K-Means、WKNN和KNN相比，DV-WKNN的平均位置误差分别降低了9.5%至13.1%，16.5%至18.9%和33.1%至48.5%。

表4、图11为不同网络中不同算法之间的最大误差的具体数值表及条形图，结果表明，DV-WKNN算法在室内环境下的性能较好，相较于K-Means、WKNN和KNN分别降低了9.8%至17.9%，23.6%至28.8%和43.1%至63.9%。

图9 η参数选取实验仿真结果

图10 不同算法的平均位置误差

表3 不同算法的平均位置误差(单位：m)Table 3 Average position error of different algorithms (Unit:m)

表4 不同算法的最大位置误差(单位：m)Table 4 Maximum position error of different algorithms (Unit:m)

图11 不同算法的最大位置误差

图12 不同算法的平均误差和最大误差

图13 50m*50m区域定位误差累积分布Fig.13 Cumulative percentage in 50m*50m network

图12为不同算法在相同条件下得到的位置误差。仿真结果表明，DV-WKNN的定位精度明显高于其他算法。与K-Means、WKNN和KNN算法相比，DV-WKNN算法的平均位置误差分别降低了10.2%、18.9%和38.9%，最大误差分别降低了17.6%、28.8%和43.3%。

图13是在50m*50m的网络环境中的仿真结果，当两个相邻的RPs之间距离为2.5m时，不同算法在该区域下的定位误差累积分布情况。上述四种算法中定位精度较差的是KNN算法，在1米以下的累积分布仅为60%，WKNN算法和K-Means算法分别为73%和77%，DV-WKNN算法为85%。

3 总结

本实验通过对WKNN的改进，并且与深度神经网络算法相结合的方法，在准确性和效率上都有所提高。引入深度神经网络算法增强对复杂的室内环境的非线性学习能力，使待测点的预测位置更加接近于准确位置，有利于泰森多边形对多个定位目标做动态划分定位区域，可以减少在线定位时全局遍历时间，从而提高了定位效率。在每个定位区域内利用WKNN算法定位时，加入环境平均偏差值，有效的提高了定位精度。

仿真结果表明，通过与KNN、WKNN和基于K-Means聚类的KNN算法比较，本文改进的算法(DV-WKNN)平均定位误差最小。与KNN、WKNN和K-Means相比，在平均位置误差上降低了38.9%、18.9%和10.2%左右，在最大定位误差上最高降低了43.3%左右。

通过对本文所提算法实现流程及结果的分析，其在实现多目标定位上有很好的应用前景，如在养老院多位老人的位置同时跟踪、智能物流分拣间的多台物流机器人同时定位等场景，能够有效的解决相关实际问题。