基于区域分类和电子地图的室内定位研究

牛福娟，滕 凯，杨 行，邢宗义

（南京理工大学 自动化学院，南京 210094）

近年来智慧城市概念的兴起和云计算技术的大规模应用带动了基于位置信息服务（LBS, Location Based Service）产业的快速发展。地铁作为现代社会出行工具的代表，以其安全、快速、便捷的优势受到视障人士的普遍青睐。研究地铁环境中面向盲人服务的定位及导航技术，能够有效地帮助视障人士独立出行，促进建立更为和谐、公平的社会环境。

大部分地铁站不提供供电接口，且运营单位限制站内设施改动（如地面埋入接收器，屋顶、廊柱安装接收器挂架等）。基于iBeacon 的低功耗蓝牙定位技术具有组网方式简单、设备接入端不依赖外部供电、中远距离内定位精度高的特点，非常适用于地铁站内定位。

目前，基于蓝牙的室内定位算法主要有基于接收信号强度指示（RSSI, Received Signal Strength Indication）的测距室内定位[1]和基于信号指纹库的匹配定位[2]。基于指纹匹配的定位方法不依赖路径损耗模型，可有效降低蓝牙信号的多径效应和非视距传播对定位精度的影响；在离线训练阶段，使用高效的机器学习算法，往往能够获得预期的定位精度；因而，该方法被广泛地研究和使用[3]。目前，比较主流的一类匹配算法是确定性方法，通过欧氏距离或马氏距离，在指纹库中选取距离最小的位置信息，常见的有NN（Nearest Neighbor）算法等，这类方法对iBeacon 信号强度的精度和稳定性要求较高，在实际场景中经常出现定位节点非连续跳动的问题。另一类匹配算法是统计分析法，此类算法考虑信号的方差分布和条件分布等因素，并结合机器学习算法，能够实现2 m 左右的定位精度，如基于K-Means 的聚类算法[4]、贝叶斯网络算法[5]和粒子滤波算法[6]等。另外，融合传感器信息和室内地图匹配的辅助技术也是提升室内定位精度的一种有效方法，这种基于位置点的匹配算法可实现在直线道路、多边形区域等各种路况下准确的定位校准，但在用户位置出现间断时，仅用该算法也很难实现准确的位置匹配[7]。

本文研究的定位算法首先利用支持向量机（SVM,Support Vector Machine）算法，对待定位区域进行离线分类；在线匹配定位过程中利用滑动窗口，对待定位区域进行2 级分类，进一步控制误差范围；最后，结合站内电子地图，对乘客定位坐标进行纠偏。在实验室和地铁站场景中的实验表明，该定位方法具有更好的定位效果。

1 基于SVM 和滑动窗口的位置匹配算法

Android 应用端可接收到的iBeacon 信息包括：该模块对应的通用唯一标识符（UUID, Universally Unique Identifier）、识别某个定位区域的区域号Major、识别区域内各个iBeacon 的Minor、RSSI 值及接收端距蓝牙模块的距离d。d与RSSI 满足对数路径距离损耗模型：

其中，P(dB)为 在距离d处的接收功率，P(dEF)为在参考距离dEF（ 通常取值为1 m）处的接收功率，n为路径损耗指数（一般在2～4 之间）， ξ为路径损耗因子。

该位置指纹定位算法的实现分为离线训练和在线匹配2 个阶段。在离线训练阶段，对各观察点采集的蓝牙信号强度进行特征分析，利用自适应高斯算法进行降噪，建立各观察点的位置指纹特征，再通过SVM 算法将数据对象聚拢成M个簇。在线定位阶段，选择簇内已匹配位置的周边定位点构建动态窗口，进一步降低移动过程中位置匹配的时间复杂度；同时，利用ArcGIS 提供的导航接口，在路径层纠正位置坐标并显示。该方法完整的算法流程包括数据预处理、离线训练、在线位置匹配与显示，如图1 所示。

图1 定位算法流程

1.1 数据预处理

蓝牙信号强度序列，在位置点 (xi,yi)处的观察数据记为(L;R)={L(xi,yi);rssi1,rssi2,···,rssii,···,rssiK}；其中，L(x,y)代 表由位置点序号组成的邻接矩阵，K为位置点的最大序列号，rssii代表在位置点 (xi,yi)处采集到的m维RSSI 序列（m为区域内iBeacon 的数量，为保证采集到的RSSI 值具有代表性，要求 |rssii|≥100）。

将区域划分为大小为1 m2的均匀网格，并按顺序标号。数据预处理阶段包括RSSI 数据采集和滤波2 个过程。数据采集格式包含相应位置点的序号以及对于信号微弱以至检测不到的iBeacon 模块，在m 维特征向量中将其对应的信号强度值设为−200 dBm。

蓝牙信号在传输过程中受到多径效应和非视距传输的影响，RSSI 值随时间的波动较大，跨度高达20 dBm。故采用高斯函数拟合的方式对测量数据进行处理，能够有效减少一些小概率、大干扰事件对整体测量的影响，明显减小测距误差。自适应高斯滤波算法（AGF, Adaptive Gaussian Filtering）通过迭代寻优，选择适合RSSI 序列特征的最优滤波模板，与固定滤波模板值的传统高斯滤波相比，具有更好的降噪和平滑效果。

自适应高斯滤波使用高斯函数，即正态分布的概率密度函数：

其中， σ表示待测点的RSSI 序列标准差， µ表示一维信号滤波模板的大小。

在预处理阶段，检测不同 µ对应的均值误差，均值误差error定义为：

其中，N为在序号为i的位置点处测量的总次数，在经过高斯滤波后的值， δ 为rssiik的均值。通过迭代优化，选取errormin对 应的 µ值作为高斯滤波的最优模板。

在实验室环境下，利用AGF 算法对采集的样本数据滤波，图2 为滤波前后的效果。

图2 采集样本AGF 算法滤波前后的效果

分别采用GF 和AGF 滤波后的数据建立指纹数据库，并利用相同的算法进行在线位置匹配，在各个位置点计算误差小于1.5 m 的位置匹配正确率，定位精度对比如图3 所示。采用GF 滤波算法时，各个位置点匹配正确率的均值为83.7%，当使用AGF 算法时该值为87.5%。

图3 2 种滤波方法的定位精度对比

1.2 支持向量机模型

支持向量机是一种2 类分类模型，其基本模型定义为特征空间上间隔最大的线性分类器，学习策略是间隔最大化。对样本信号强度集合组成的m维特征向量，可利用非线性函数 φ(x)将输入空间数据映射到高维特征空间，并在该空间构造最优分类超平面[8]：

其中， ω为权值矢量，b为 偏差， ω和b确 定分类面的位置。为找到式（4）对应的最优分类超平面，需求解带约束的最大值问题[9]：

其中，C是惩罚因子，与SVM 分类对错误样本的重视程度成正比。求解这类待约束的最小值问题，需要应用拉格朗日方程，经过一系列变换可将该2次规划问题转化为相应的对偶问题[10]，即：

1.3 基于滑动窗口的在线指纹匹配

将RSSI 变化的范数的倒数作为当前状态的估计值：

通常取p=2，即用Euclid 距离的倒数来表征观测特征向量X与位置指纹向量的相似度。

SVM 多分类器要在M个子区域中训练分类器模型，将X代入各分类器模型，目标值ci=+1对应的子区域即为当前位置所属的子区域。

滑动窗口可理解为：在2 次在线匹配的时间间隔内，盲人乘客的行走距离有限，可选择前一个定位点邻近的位置点作为下一个的匹配区域；随着乘客移动，窗口范围在不断发生变化。窗口的形状定义为：

其中，窗口的大小可调整，并在子区域边界舍弃部分邻近点。最后，在窗口中选取K(K≥2)个w值较小的位置点，作为最后定位的参考点，并将其对应坐标的平均值作为位置估计的结果，称为KNN（K-Nearst Neighbors）算法[11]，计算公式为：

由此可避免在子区域中进行全局搜索，降低了时间复杂度，并减少定位点不连续的情况。

2 室内电子地图与地图纠偏

不同于室外地图，室内地图尚未形成统一行业标准，相同的室内场景可能具有不同风格的地图表现形式[12]。计算机中主要有4 种地理数据表示方法：栅格表示法、矢量表示法、栅格和矢量数据的图层表示法、面向对象表示法。本系统中采用混合矢量和栅格的图层表示法，图层按类型主要划分为3 种：点、线和面。每一层（Layer）是某一类元素的集合，表示某一类地图信息，如盲道、电梯、问询台等。此外，还有一些扩展应用图层，如网格要素图层、导航连接点层以及标注层等[13]。

网格要素图层是为数据采集而添加的图层，该图层中每个网格存储当前网格的坐标和位置序号等属性，用于为数据采集阶段提供每个网格的属性信息，以及在线定位阶段进行位置纠偏[14]。本系统利用ArcGIS 软件的ArcCatalog 生成网络数据集（Network Dataset)和地址定位器，将各图层信息加入到指定地图中，为程序提供可调用的导航接口[15]。

定位系统在Android 应用端实现，App 会根据盲人乘客选择的目的地为其规划路径（尽量沿盲道）。网格层记录路径层对应的位置序号，当盲人乘客的定位坐标偏离路径时，将其“拉”回既定路径，定位点纠偏模型如图4 所示。a为前一时刻盲人乘客的位置坐标，b为 当前时刻的实际坐标，c为在线位置匹配结果；判断c是否偏离既定路径，若是则计算其“投影”在既定路径上所对应的位置序号，以进一步降低KNN 算法的定位偏差。

图5 为利用ArcGIS 软件制作的广州地铁苏元站地下一层站厅层的电子导航地图（局部）。

图5 广州地铁苏元站站厅层电子地图（局部）

3 实验与结果分析

实验场景为广州地铁苏元站地下一层，定位区域面积2 600 m2。在此区域内，以3 m间隔距离，横纵方向均匀地部署iBeacon（支持BLE4.0 协议）；采用华为荣耀6X Android 手机完成应用端的数据采集、指纹匹配和位置显示等功能，图6 为App 操作界面。

图6 Android 应用端操作界面

将定位区域划分为2 436 个参考点进行信号采集，采集的蓝牙信号指纹数据格式为：位置点序号、位置点相对坐标、传感器类型标识和RSSI 数组；将iBeacon 广播频率设置为10 Hz，每个参考点上采集200 组数据构造训练集。表1 为使用3 种定位算法分别处理实验导航定位数据得出的定位误差距离统计。

表1 3 种定位算法的定位误差距离统计

从表1 可知，基于KNN 的传统指纹匹配算法的定位误差集中分布于≥2 m 的范围，误差为1 m 左右的观测点很少；利用SVM 对定位区域进行分类训练后，可提高误差距离在2 m 左右的观察点占比，但并未改善整体的定位效果。与之相比，本文提出的算法将定位精度在1 m 以内的观测点提升到55%，整体定位精度的提高较为明显。同时，该算法采用2级分类，将在线定位时间复杂度由O(n)降低为其中，n为 数据对象总数，M为子区域的数目，|W|为滑动窗口规模。

综上所述，该算法具有快速和高精度的特点，非常适用于地铁站内面向盲人乘客服务的实时定位。

4 结束语

针对地铁站内多径效应严重及iBeacon 节点的RSSI 值波动较大的问题，提出一种迭代寻优的自适应高斯滤波模型，用于对采集的信号强度数据进行预处理，利用滤波后的采样数据均值建立采集点位置的特征向量；在离线阶段，利用支持向量机模型对待定位区域进行1 级分类，将其划分为若干子区域；在线定位时，仅需遍历子区域一次，并利用KNN 算法确定初始位置，利用滑动窗口进一步缩小待匹配区域，实现对待定位区域的2 级分类，可有效降低匹配算法的时间复杂度，解决定位点非连续跳跃的问题；利用Android 手机端的电子地图路径层信息，对行走路径上的错误定位点纠偏，进一步降低KNN 算法带来的定位偏差。

实验结果及数学分析表明：该定位算法的定位精度和实时性可满足地铁站内面向盲人乘客定位服务的要求。