基于改进AP 选择的融合随机森林室内定位算法

牟平，凌铭，胡锐

( 上海工程技术大学 电子电气工程学院，上海 201620 )

0 引 言

随着无线局域网(WLAN)、云计算、智能终端以及传感器的普及与高速发展，对位置信息的需求正在不断增加. 位置信息的需求推动了基于位置服务(LBS)的高速发展，而定位技术是LBS 的核心. 目前室外定位采用全球卫星导航系统(GNSS)，包括GPS和我国的北斗卫星导航系统(BDS)等，定位方法相对完善. 然而，室内GNSS 卫星信号弱或者根本无信号，导致室内无法利用GNSS 卫星信号进行正常定位. 特别是一些公共区域，如大型商场、地下停车场、大型图书馆都需要较为精确的位置服务[1]，因此，对于室内定位精度的需求变得日益迫切.

自2000 年起，利用无线保真(Wi-Fi)位置指纹进行室内定位的概念被美国微软研究院率先提出，同时推出室内定位系统Radar[2]，由于Wi-Fi 的普及程度比超宽带(UWB)和一些无线射频识别(RFID)更为广泛且定位过程中无需部署[3]，所以近年来许多学者不断研究如何在现有的指纹匹配定位模型上改进已有算法来提升定位精度以及定位性能，影响模型定位精度的关键因素之一是接收信号强度(RSS). 文献[4]提出接入点(AP)选择法融合K最近邻算法(KNN)来进行室内定位，其融合效果比传统KNN 精度上有较大地提升，但在实际定位过程中由于数据量较大，利用KNN 时间复杂度将会提升，同时也会带来定位精度的下降. 文献[5]利用每个AP 在参考点的分组定位和加权质心算法相结合，多方位测距减小误差，以降低RSS 变化带来的影响. 文献[6]提出优化的随机森林(RF)，引入伯努利分布来减少选取训练集中的冗余特征，使得弱分类器之间的随机性和多样性降低.

基于此，本文提出稳定性优先的AP 选择方案来降低RSS 变化带来指纹向量维度和值不同的影响，这样能够保证离线数据库中的每个可用的AP 都是在定位过程中起重要作用的AP，同时融合集成学习中随机森林的多个弱分类器来提高定位精度并减少定位时间，从而增加定位效率.

1 室内定位整体流程

本文采用Wi-Fi 位置指纹来进行室内定位，主要可分为离线阶段和在线阶段[7]. 离线阶段需要移动终端获取待定位区域的RSS 信号值，并对定位区域进行合理的网格划分，将搜集到的RSS 数据发送至后台，形成初步的指纹数据库. 在后台对初步指纹数据库进行AP 选择，选择重要的AP，这里的重要AP 是指这些AP 的RSS 信号有利于定位，比如与地理位置的映射最为明显、位置分辨能力最高、样本波动小等，然后将所得指纹数据库作为训练集输入到RF 训练模型中[8]；在线定位阶段移动终端将搜集到的RSS 信息，根据离线阶段所选择出有用的AP，过滤掉在线搜集到的那些来源于其他AP 的RSS 信号，然后将过滤过后的信号发送至后台进入训练好的RF模型中得出最终的位置，其中介质访问控制(MAC)为每个AP 的唯一标识. 图1 为室内定位整体流程.

图1 室内定位整体流程

2 改进的AP 选择算法

2.1 AP 选择的基本理论

在基于指纹的无线室内定位中，定位的精度受RSS 信号的严重影响，并且处于不断波动的状态. 即使是在同一个位置上接收来自同一个AP 的RSS 信号也有可能随着环境发生变化. 在复杂的室内环境下，虽然可用的AP 很多，但是有很多AP 是无用的甚至会降低定位精度，因此需要选择合适的AP 数目来提升定位精度，以确保离线阶段数据库的构建更准确[9].

在离线阶段和在线阶段均可以执行AP 选择. 此外，AP 选择过程可以为所有参考点选择AP 的统一子集，可以是整个区域或由粗略定位选择的子集，被称为统一AP 选择. 相反，基于参考点的选择方法单独为每个参考点选择一组AP. 这样，每个参考点可以包含与其他AP 不同的AP 集合[10]. 本文考虑改进离线阶段的统一AP 选择，利用AP 稳定性优先来衡量AP 质量，同时对于AP 选择定义如下：对于定位区域中AP 集合P={P1,P2,···,Pn} ，我们需要找到其中的一个子集P′使得在该子集上完成定位的精度最高，即

式中：Φi为除选定的AP 索引之外的所有索引归零来定义所选AP；L′为子集P′的基数；Φ为选择矩阵用来选择众多AP 中有用的AP.

2.2 改进的AP 选择算法

传统的基于信息增益(IG) AP 选择算法[11]，虽然考虑到AP 之间的相关性，但是并没有考虑AP 的RSS 样本数据的稳定性.因此，本文提出一种基于稳定性优先的AP 选择算法，其中稳定性包含：每个AP的RSS 样本的方差；在同一位置下AP 所出现的频率.

在定位区域中，同一位置采集到来自同一AP 的RSS 样本可能会随时间以及环境的变化而变化. 对于参考点L，会接收到来自n个AP 的RSS 信号，AP 集合表示成 {AP1,AP2,···,APn} ，为了使指纹数据库能更好地反映数据特征和数据维度以及减少在线阶段的计算量.本文通过稳定性优先的AP 选择算法从这n个AP 中选择出合适的m个AP，主要流程如图2所示.

图2 改进AP 算法流程

在采样点L上接收到第i个AP 的n次采样数据为 {RSS1,RSS2,···,RSSn} ，于是该AP 的RSS 数据波动幅度可以通过方差计算得到，即

式中，RSS为n次RSS 数据的均值. 此处的n与上述保持一致，每个AP 的RSS 样本方差实际上就反映了数据波动，同时考虑到方差可能为0，所以加入拉普拉斯平滑引入 ε 以避免方差为0 的情况，与此同时考虑到每个AP 在整个采样点出现的频率，结合数据波动与出现的频率衡量RSS 样本的稳定性，即

计算出稳定度之后对稳定度进行排序，选择稳定度最高的前m个AP 用来作为AP 选择的结果，并以此来构建指纹数据库，根据对AP 数目对室内定位产生影响的相关研究[12-13]，本文选择AP 数目为5 个.

3 RF 算法

RF[14]模型是在2001 年提出的一种基于决策树分类的集成学习算法，通过对训练集进行N次有放回取样构建基分类器. 在RF 中，训练集中的样本就是在离线阶段所采集到的一条RSS 数据，其中的特征则是经过AP 选择后离线数据库中的每个AP 在采样点对应的RSS 值，标签是每个采样点的位置信息. 随机抽样从特征中随机选取几个特征，因此基分类器是随机的，最终N个随机且彼此独立的分类器决策树构成随机森林，当实时定位阶段用户发来经过筛选的RSS 信号后，进入随机森林模型中，所有的基分类器产生预测结果，最终投票结果的众数作为输出位置.图3 为随机森林算法流程.

图3 RF 算法

RF 算法流程为：

输入：离线数据库中的所有样本和位置标签作为初始训练集，记为D.

输出：对于待测样本xt，N棵决策树的输出，即最终移动终端的.

开始

Fori=1，2，···，Ntree

1) 对初始训练集D进行随机抽样，生成每个分类器的对应的训练集Si；

2) 使用训练集Si生成所对应的决策树Ti，并从每棵决策树结点上随机选取最优特征，不断的分裂树至树生长到最大.

在线阶段发送经AP 筛选的RSS 信号进入随机森林模型中得出最后移动终端的位置.

结束

随机森林分类是指当训练集的因变量是不连续变量时，此时输出最终位置用式(5)表示为

4 实验验证与分析

4.1 实验环境

本文的实验场地选在上海工程技术大学实训楼四楼，实验环境保持不变，测试环境周围的AP 是利用学校布置的AP 点，不会随意更改AP 或者加入其他AP. 其中测试区域结构如图4 所示，信号采集所用的装置为华为P20，采用的AP 是学校已有的AP，通过自主开发的软件采集RSS 信息，其中每个网格点大小设置为1.5 m×1.5 m，并在每个网格点东南西北四个方向共采集100 组信号，采集的频率为1 Hz.

图4 测试区域结构

实验中采样点共有205 个，为将定位结果量化，利用真实值与测量值之间的距离定义为误差

4.2 实验结果分析

本文利用改进的AP 选择方法融合RF 来对位置做出更精确的估计，同时与基于IG 的AP 选择融合RF，未经AP 选择的RF 和改进的AP 选择融合加权的K近邻算法(WKNN)进行实验对比. 本实验中参数设置为：AP 最佳数目选择为5，RF 分类器个数为500 个，WKNN 的K值选择为4，对于权重的选择为欧氏距离的倒数. 实验所需的部分数据采集如表1所示.

表1 实验采集的部分RSS 数据dBm

如图5 所示，为了直观显示上述算法在定位误差上的表现，统计了多组实验求取平均定位误差用来衡量算法的好坏. 由图5 可知，改进的AP 和RF 算法的平均定位误差为1.26 m，要比IG+RF、RF、改进的AP+WKNN 分别降低17.2%、29.3%、23.2%.

图5 四种不同算法的平均定位误差

图6 为不同定位算法定位误差的累计概率分布.由图6 可知，改进的AP 选择和RF 算法有78%的概率保证定位误差在1.5 m 以内，90%的概率保证定位误差在2 m 以内； IG+RF 有60%的概率保证定位误差在1.5 m 以内，80%的概率定位误差在2 m 以内；改进的AP+WKNN 有50%的概率定位误差在1.5 m以内，63%的概率定位误差在2 m 以内；RF 有42%的概率定位误差在1.5 m 以内，57%的概率定位误差控制在2 m 以内. 综上可知，在定位精度上，本文提出的算法与其余三种算法相比有明显提升.

图6 各种算法的定位误差累积概率分布

由于RF 在离线阶段需要训练出RF 模型，所以需要一些时间，但定位系统实时性衡量的是在线定位阶段是否能实时反映移动终端的位置信息. 因此，本文考虑的是在线定位阶段上述算法的定位时间. 如图7 所示，以6 个待定位点为例，展示上述算法在在线定位阶段的定位时间. 验证算法从图7 可以看出，改进的AP+RF 的定位时间平均0.98 s，对于改进的AP+WKNN 而言数据量大的情况下，需要在线定位阶段遍历数据库进行比对，通过统计100 组实验下的平均定位时间分析可知，其定位时间比改进的AP+RF 长；由于RF 未经AP 选择所以数据库中包含有大量对定位结果无用甚至有害的AP，所以导致在线定位时间平均在1.3 s；IG+RF 算法利用信息增益最大化选择AP 考虑到了AP 之间的相关性，但并未考虑数据稳定性，其中会存在一些不稳定AP 加大在线定位阶段的计算量，导致定位时间平均在1.15 s.

图7 各个算法的定位时间

5 结束语

本文提出了改进的AP 选择融合RF 的算法. 首先对初始指纹数据库进行AP 选择，根据每个AP 的RSS 样本的稳定度来选取前5 个AP 作为定位AP，然后将处理好的指纹数据库作为数据集进行RF 的训练，形成RF 模型. 在在线定位阶段通过离线阶段已经选好的5 个AP 对RSS 数据筛选，然后经过RF模型投票得出最后的结果. 实验结果表明：本文提出的算法在定位误差以及定位时间方面优于其他算法，且改进AP+RF 的平均定位误差稳定在1.26 m，在线定位时间平均也只有0.98 s；在Wi-Fi 室内定位中一定程度地减小了定位误差和降低定位时间，在室内定位技术中有一定的意义.