基于IRF-PF算法的WLAN室内定位方法

柴海珑,王小鹏,龙 良

(兰州交通大学 电子与信息工程学院,兰州 730070)

随着无线网络、移动计算和普适计算等技术的普及,基于位置的服务引起了人们的广泛关注。虽然全球定位系统和北斗卫星导航系统已被广泛应用于室外定位[1],但在室内或者高层建筑密集的地区,无线电信号易受到建筑物墙壁的阻挡而被衰减或反射,导致全球卫星导航系统在室内的定位精度大幅下降,无法满足人们对定位服务精度的要求[2]。当前主流的室内定位技术有射频识别[3]、ZigBee[4]、超声波、超宽带[5]和无线局域网(wireless local area networks,WLAN)[6]等技术。随着WLAN广泛应用于居民、办公和商业区,基于WiFi的指纹定位成为最流行的室内定位技术之一[7]。该方法由离线阶段和在线阶段组成[8]:离线阶段通过在参考点(reference point,RP)标记其坐标并采集可检测到的接入点(access point,AP)的接收信号强度(received signal strength,RSS),构建由位置坐标和RSS组成的指纹库[9];在线阶段利用待定位点记录不同AP的实时RSS值,通过与离线指纹库互匹配估计待定位点的位置[10]。

目前常用的室内定位算法有K近邻(K-nearest neighbor,KNN)、神经网络和支持向量机等[11-13]。然而,这些方法存在一定的缺陷:KNN算法需要存储所有的RSS训练值且定位精度很大程度上依赖于K值;神经网络算法训练需要大量的数据和计算资源,且容易受到过拟合等问题的影响;支持向量机算法通过寻找最优的超平面,将RSS值映射到高维空间中进行分类,虽然具有较好的泛化能力和鲁棒性,但需要选择合适的核函数和正则化参数。Varma等[14]指出,随机森林(random forest,RF)算法相较于KNN、支持向量机和决策树等算法具有更好的位置匹配和定位偏差性能。然而,在实际的室内环境中,由于电磁干扰和障碍物造成AP的RSS值波动,传统的RF算法会将空间中所有AP的RSS值作为决策树候选划分点,并且忽略强弱决策树之间的差异性,给予决策树相同权重后进行投票决策,这将会影响RF算法的分类正确率。因此,李兵等[15]引入聚类思想中的自适应窗口,根据特征集合构造变异系数,自适应地调整窗口长度,以控制滑动均值的变化;然后计算各个滑动均值的基尼系数,并选取具有最优基尼系数的滑动均值作为决策树的划分点。另外,杨宏宇等[16]采用bagging方法,以剩余样本作为决策树性能的评价指标,并根据评价指标赋予决策树不同的投票权重,以增加算法模型的整体稳定性。针对室内定位的特殊应用环境,本文提出一种改进的随机森林算法(improved random forest,IRF)。该算法能选取有效AP作为指纹特征值,用于构建分类回归树模型(classification and regression tree,CART),并根据AP的重要性赋予不同的投票权重,从而提高位置映射模型的稳定性和准确性。此外,该算法还采用粒子滤波(particle filter,PF)算法对位置进行校正,以获得更为精确的二次定位坐标。

1 数据预处理

WLAN指纹定位离线阶段的主要任务是建立指纹库。为了建立健壮的指纹数据库,需要先对原始RSS值进行预处理,以消除异常数据和粗大误差。

假设R(i,j)是在j处的RP连续p次采集来自第i个AP的RSS,测量值集合S如式(1)所示。

(1)

测量值R(i,j)的平均值为:

(2)

(3)

计算剩余误差的标准偏差σ,如式(4)所示。

(4)

2 改进随机森林算法

RF算法首先采用bagging方法生成训练子集;然后选取基尼系数最小值作为节点分裂的最佳分类特征来构建二叉决策树;最后,将生成的决策树集成为CART分类器,通过投票机制取众数作为最终的定位结果[18]。在理想情况下,使用更多AP的RSS作为特征,可以提高定位精度;但是,在实际环境中,由于障碍物和多径效应的影响,RSS值波动较大,因此,将所有AP的RSS作为定位特征,反而会降低定位精度。此外,RF算法的投票决策过程决定了最终定位预测结果,然而RF算法忽略CART决策树强弱分类器差异,直接将单决策树预测结果取众数机制投票后作为最终定位结果。这种机制也会因为RSS波动的影响对室内定位系统整体判别性能造成一定偏差。因此,需要对随机森林算法进行优化,以满足室内高精度定位需求。

本文提出的IRF算法加入了特征选择、样本权重调整机制:通过特征选择算法可以自动选择与定位相关的特征,以提高模型的精度;而样本权重调整则可以对不同的决策树赋予不同的权重,从而更好地处理不平衡RSS的问题。

2.1 改进CART决策树

假设μ(m,n)表示从预处理集合S*中第m处坐标为(xm,ym)的RP采集到的第n个AP的RSS,用RP坐标和AP的RSS构建用于定位的位置指纹数据库F,如式(5)所示。

(5)

将第m个RP所接收到的μ(m,n)值降序排列,得到集合Pm={μ(m,1),μ(m,2),…,μ(m,n)}。滑动窗口长度ω从初始值开始滑动,窗口内的特征均值为:

(6)

特征均值增长率为:

c=|aj-aj-1|/|aj-1|

(7)

假设特征均值增长率阈值域为[F1,Fh)。当c

采用bagging取样方法,从位置指纹样本训练集中有放回地随机抽取新的样本子集,作为决策树的训练子集D,Q为RSS向量集。在训练子集中,创建不同决策树,利用式(8)递归计算各候选划分点的基尼系数G(D)。选取基尼系数G(D)的最小值作为划分点,建立决策树T(Q),生成CART模型。

(8)

其中:pb为b位置样本的概率,B为b位置样本数量。

在传统的随机森林算法中,每个CART决策树都是基于所有特征进行构建的,这可能导致决策树在处理噪声和重叠特征时出现过拟合或欠拟合的情况。改进的随机森林算法采用了特征选择策略,选择最相关的特征来构建决策树,减少特征空间的噪声,从而提高室内定位的精度。

2.2 改进的投票决策

在使用bagging方法从训练集中训练生成决策树的过程中,每个样本未被抽取到的概率为E=(1-Z-1)Z,Z为样本总数。当样本总数Z无限大时,即lim(1-Z-1)Z=0.368,说明对于单个决策树而言,大约有37%的训练数据未参与该决策树的训练生成,称这部分数据为袋外数据(out-of-bag data,OOBD)。

T为已完成训练的决策树集。因单个决策树对应的OOBD样本位置已知,故可以利用OOBD检验所对应的单个决策树分类的正确率At。将分类正确率作为决策树的权重,可以增强决策树之间的差异性,提高RF算法总判别性能。图1为改进的投票决策流程。

图1 改进的投票决策流程

随机森林算法是一种集成学习方法,通过组合多个决策树的结果来减少误差。在传统的随机森林算法中,每个决策树的结果是相互独立的,这可能增加集成结果的方差。改进的随机森林算法采用了样本权重调整策略,通过引入权重来增加决策树之间的差异性,从而减少集成结果的方差。

3 融合PF的IRF定位算法

首先,通过改进的随机森林位置估计模型将待定位点的RSS与离线阶段建立的位置指纹库中的RSS进行互匹配,得出初步的定位结果;然后,采用PF算法进行二次定位,对初步定位结果进行位置修正和滤波,以获得更为精确的目标点位置。

3.1 IRF匹配定位模型

在待定位点采集能够接收到AP的RSS,构建RSS向量Q,利用IRF算法将向量Q与离线阶段建立的位置指纹数据库F进行互匹配,计算待定位点的位置坐标。利用IRF算法对待定位点的RSS进行定位的步骤如下:

步骤1：对于位置指纹数据库F,利用式(6)和阈值域计算候选划分点,并利用式(1)递归计算各候选划分点的基尼系数。选取基尼系数的最小值作为划分点,建立v棵决策树集T(Q),将得到的v棵决策树组成一个CART森林决策系统。

步骤2：使用bagging方法得到训练样本集Du。对CART进行训练时,将OOBD检验生成的决策树的正确率At作为单个决策树的权重,以增强定位分类器间的差异性。

步骤3：将待定位点的RSS向量Q作为IRF模型的输入,利用IRF计算出位置分类结果决策树集。依据OOBD对不同决策树赋予不同权重值,通过加权投票,最终计算出的定位结果为:

(9)

3.2 PF优化的定位结果

粒子滤波是一种基于蒙特卡洛仿真的近似贝叶斯递归滤波算法[19],可以处理线性高斯噪声,也可以处理非线性和非高斯噪声。利用粒子滤波算法对位置一次定位结果进行校正,可以降低由室内障碍物和多径现象引起的RSS突变波动带来的定位误差。粒子滤波优化一次定位的算法步骤如下:

(10)

预测位置和观测位置之间距离的标准差为dstd,利用式(11)计算第k次预测位置与观测位置的欧式距离的概率密度。

(11)

(12)

步骤3：自由化重采样。根据式(13)计算有效粒子数Ne。

(13)

(14)

4 仿真分析

4.1 实验场景

本文使用的Zenodo数据集是从西班牙Universitat Jaume I的图书馆由专业人士从第3层和第5层分别测量得到[21]。数据集包含了多个采样点,其中每个RP都记录了WLAN接入点的RSS值和位置。由于图书馆第3层和第5层结构相同,所以本文选用第3层数据集对提出的定位方法进行性能研究。

图2中三角形代表无线网络设备,数据测量范围是在如图3所示的书架区域。该数据集在48个RP(每层24个RP)连续采集25个月来自不同网络设备的RSS(每个无线网络设备有多个以MAC地址和SSID唯一标识的AP),为了防止测量的随机误差,在每个RP处共采集RSS值的次数L=6。

图2 无线网络设备位置拓扑图

图3 数据采集点空间位置图

图3中,矩形位置代表书架区域,菱形位置表示训练集和测试集的数据采集位置。RP间距最大约为4.2 m,最小约为1.8 m。

4.2 算法参数分析

在本研究中,将第3层书架区域划分为由x轴和y轴组成的平面空间坐标系。针对指纹数据集中第3层第15个月的trn01数据库,对RP采集编号为7的AP短时连续RSS进行可视化分析,如图4所示,可以看出,在同一位置下的同一AP短时间内的RSS值会存在最大约19 dBm的波动。这种波动会在指纹匹配时造成较大的定位误差,从而影响定位精度。因此,特征维度并不是越高,定位精度就越高。为提高定位精度,需要剔除RSS波动较大的AP。这个过程通过使用本文提出的改进CART决策树方法来实现,使得数据更加平滑,减少噪声的影响。

图4 RSS波动图

图5显示了指纹数据库中第3层第15个月的trn01数据集的部分数据。在指纹库中,如果RP处没有检测到AP的RSS值,则该位置的RSS设置为-105 dBm。通过对图5中的数据进行分析可知:在同一RP处接收到不同AP的RSS的最小差约为1 dB,增长率约为2.0%,最大差值约为62 dB,增长率约为59.0%。基于以上分析及实验验证,滑动窗口平均增长率阈值设置为4.7%～9.5%之间,将有助于滤除RSS值变化过大的AP。

图5 RP接收的RSS

本文所提出的算法中,滑动窗口长度会对有效AP的数量产生影响,进而影响指纹匹配定位的结果。若滑动窗口长度过大,则会减小有效AP的指纹特征数量;若滑动窗口长度过小,则会增大无效AP的指纹特征数量。因此,在实验中,将滑动窗口长度初始值从1开始增加,观察定位误差的变化,分析最优初始滑动窗口长度值。实验结果如图6所示。

图6 不同滑动窗口长度的定位误差

由图6可知:随着滑动窗口长度ω由1逐渐增大时,定位误差值逐渐减小;当滑动窗口长度ω=8时,定位误差有最大的改善,75%概率误差和平均误差分别为1.983 m和1.632 m;然而,当滑动窗口长度继续增大时,定位误差反而增大。这是因为窗口增大时,有效AP指纹特征数量减少,影响了定位精度,因此,ω=8是该环境下的最佳值。

4.3 算法性能对比分析

IRF算法通过优化的CART准则,选取对预测定位结果有重要贡献的AP特征,剔除RSS信号受干扰较大的AP。通过OOBD对决策树投票加权,提高算法对关键特征的识别能力。在传统RF算法中,各个决策树对关键特征的识别能力可能存在差异。有些决策树可能对某些关键特征的识别能力较弱,导致这些特征的重要性得不到充分体现。IRF算法通过对决策树进行投票加权,可以对这些决策树的影响进行削弱,从而提高算法对关键特征的识别能力。融合粒子滤波的IRF-PF算法先利用改进的随机森林算法对WiFi信号进行特征选择和分类,然后将分类结果作为粒子滤波的观测量,利用粒子滤波对目标位置进行估计和预测。具体来说,改进的随机森林算法可以剔除一些噪声较大的WiFi信号,提高分类准确率,从而为粒子滤波提供更加准确的观测量,同时粒子滤波可以对WiFi信号的时空特性进行建模,对随机森林算法中可能存在的误差进行校正,从而进一步提高定位精度。

为了验证本文提出的IRF-PF算法相较于传统RF、IRF算法的优越性,在选取的16个目标定位测试点进行定位精度对比实验。图7为基于这3种算法计算出的位置与目标定位测试点的定位误差。图8为基于RF算法和IRF-PF算法的估计位置与目标位置定位对比图。

图7 定位误差

图8 位置估计对比图

由图7可知:RF算法的定位误差浮动较大,说明定位精度受环境影响较大;相比之下,融合粒子滤波的IRF-PF算法的定位误差浮动较小,平均定位误差约为1.72 m。进一步观测图8可以看出:IRF-PF定位算法的估计位置与目标位置更接近,聚集度更高。实验结果表明:本文所提出的算法能够有效平滑RSS波动带来的定位误差,并且具有较高的定位精度和良好的稳定性,进一步证明了本文所提算法的优越性和实用性。

为了验证本文算法与其他主流定位算法的性能差异,在上述实验环境中25个月以来所测量的数据集中,每个月选取24个测试点,将本文的IRF-PF算法与其他常见的4种算法在随机选取的600个测试样本中进行定位性能对比分析。图9为岭回归(ridge regression,RR)、KNN、贝叶斯岭回归(Bayesian ridge regression,BRR)、RF和IRF-PF等5种定位算法的估计误差累计分布函数性能比较。表1为5种定位算法的性能统计分析,其中:n为指纹样本数量,m为特征维度,d为树的最大深度,t为粒子数。

表1 误差统计

由图9和表1可以看出:相较于RR、KNN、BRR和RF算法,本文提出的IRF-PF算法将定位平均误差分别降低了约40.93%、38.06%、35.34%、14.33%,且中值误差更小,75%的概率误差达到了1.983 m;结合各个算法的时间复杂度可以看出, 基于IRF-PF的定位算法在实时性方面表现良好。综上所述,基于IRF-PF的室内定位算法较其他方法性能较优。

5 结论

针对AP的RSS波动导致定位精度不高的问题,提出了一种基于RSS特征选择的WLAN室内定位算法。该算法利用滑动窗口思想选取RSS信号波动较小的AP作为构造CART的候选划分节点,依据OOBD已知的空间位置信息,赋予决策树不同的权值,增大单个决策树之间的差异性;同时,引入PF算法,对IRF的一次定位结果进行校正解算,得到目标位置的二次定位结果,进一步提升了算法的精度。仿真结果表明:IRF-PF方法的平均定位误差为1.632 m,能有效弥补RF算法定位缺陷;与其他方法相比,也具有更好的定位精度,能够满足室内环境中的目标定位需求。

考虑到不同室内环境中AP的RSS值波动不一致情况,后续实验将在不同的室内环境中验证本文算法的可靠性。同时,未来的研究将进一步探索如何挖掘RSS的高阶特征,建立低复杂度的指纹库,以减少定位误差。这些研究工作将进一步提高算法的性能和实用性,为室内定位技术的应用提供更加可靠和精准的解决方案。