• 查询稿件
  • 获取最新论文
  • 知晓行业信息
官方微信 欢迎关注

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

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

牛福娟, 滕凯, 杨行, 邢宗义. 基于区域分类和电子地图的室内定位研究[J]. 铁路计算机应用, 2020, 29(9): 1-5, 15.
引用本文: 牛福娟, 滕凯, 杨行, 邢宗义. 基于区域分类和电子地图的室内定位研究[J]. 铁路计算机应用, 2020, 29(9): 1-5, 15.
NIU Fujuan, TENG Kai, YANG Hang, XING Zongyi. Research on indoor location based on region classification and electronic map[J]. Railway Computer Application, 2020, 29(9): 1-5, 15.
Citation: NIU Fujuan, TENG Kai, YANG Hang, XING Zongyi. Research on indoor location based on region classification and electronic map[J]. Railway Computer Application, 2020, 29(9): 1-5, 15.

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

基金项目: 国家重点研发计划课题(2017YFB1201203)
详细信息
    作者简介:

    牛福娟,在读硕士研究生

    滕 凯,在读硕士研究生

  • 中图分类号: U231.4 : TP39

Research on indoor location based on region classification and electronic map

  • 摘要: 为辅助盲人独立乘坐地铁出行,解决传统室内定位法易产生定位点跳跃和定位实时性差等问题,提出一种融合区域分类和电子地图的方法。该方法分为离线区域分类和在线定位2个阶段:在离线阶段通过迭代寻优,为蓝牙传感器产生的RSSI序列寻找最佳高斯滤波模板,采用滤波后的序列均值构建位置指纹库,并利用支持向量机模型对位置指纹库进行1级分类;在线阶段,采用滑动窗口对待定位区域进行2级分类,在窗口范围内采用基于欧氏距离的KNN算法求取位置坐标,并利用电子地图的路径层信息对定位坐标纠偏,进一步控制误差范围,提高定位效率。实验表明:该滤波方法将定位精度提高近4%,使用该定位算法最终能达到1.59 m定位精度。
    Abstract: In order to assist blind people to travel independently by subway and solve the problems of hopping discontinuity of location points and poor real-time location in traditional indoor location methods, a method by fusing region and electronic map is proposed. The method can be divided into two stages: offline region classification and online location. In the stage of offline region classification, the best Gauss filtering template is searched for RSSI sequences generated from Bluetooth sensors by iterative refinement and the filtered sequence means are used to construct location fingerprint database, and the support vector machine model is used to classify the location fingerprint database at the first level. In the stage of online location, a sliding window is used to classify the regions to be located at the second level, a KNN algorithm based on Euclidean distance is used to calculate the location coordinates within the range of the sliding window, and the path layer data in a electronic map is used to reduce the deviation of location coordinates so as to further control the error margin and improve the efficiency of location. The tests in a subway station hall show that the filtering method can improve the accuracy of location by nearly 4% and finally the accuracy of location can reach 1.59 m by using this location algorithm.
  • 近年来智慧城市概念的兴起和云计算技术的大规模应用带动了基于位置信息服务(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级分类,进一步控制误差范围;最后,结合站内电子地图,对乘客定位坐标进行纠偏。在实验室和地铁站场景中的实验表明,该定位方法具有更好的定位效果。

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

    $$P({\rm{d}}B) = P({d_{{\rm{EF}}}}) + 10n\lg \left(\frac{d}{{{d_{{\rm{EF}}}}}}\right) + \xi $$ (1)

    其中,$P({\rm{d}}B)$为在距离$d$处的接收功率,$P({d_{EF}})$为在参考距离${d_{EF}}$(通常取值为1 m)处的接收功率,$n$为路径损耗指数(一般在2~4之间),$\xi $为路径损耗因子。

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

    图  1  定位算法流程

    将区域划分为大小为1 m2的均匀网格,并按顺序标号。数据预处理阶段包括RSSI数据采集和滤波2个过程。数据采集格式包含相应位置点的序号以及蓝牙信号强度序列,在位置点$({x_i},{y_i})$处的观察数据记为$(L;R) = \{ {{{L}}_{({x_i},{y_i})}};\;{{rss}}{{{i}}_{{1}}},{{rss}}{{{i}}_{{2}}},\cdots,{{rss}}{{{i}}_{{i}}},\cdots,{{rss}}{{{i}}_K}\}$;其中,${{{L}}_{(x,y)}}$代表由位置点序号组成的邻接矩阵,$K$为位置点的最大序列号,${{rss}}{{{i}}_{{i}}}$代表在位置点$({x_i},{y_i})$处采集到的$m$维RSSI序列($m$为区域内iBeacon的数量,为保证采集到的RSSI值具有代表性,要求$|{{rss}}{{{i}}_{{i}}}| \geqslant 100$)。对于信号微弱以至检测不到的iBeacon模块,在m维特征向量中将其对应的信号强度值设为−200 dBm。

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

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

    $$f(x) = \frac{1}{{\sigma \sqrt {2{\text{π}} } }}exp \left({\rm{ - }}\frac{{{{(x - \mu )}^2}}}{{2{\sigma ^2}}}\right)$$ (2)

    其中,$\sigma $表示待测点的RSSI序列标准差,$\mu $表示一维信号滤波模板的大小。

    在预处理阶段,检测不同$\mu $对应的均值误差,均值误差$error$定义为:

    $$error = \sum\limits_{k = 1}^N {(rssi'_{ik} - \delta )} $$ (3)

    其中,$N$为在序号为$i$的位置点处测量的总次数,$rssi_{ik}^{'}$$rss{i_{ik}}$在经过高斯滤波后的值,$\delta $$rss{i_{ik}}$的均值。通过迭代优化,选取$erro{r_{\min }}$对应的$\mu $值作为高斯滤波的最优模板。

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

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

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

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

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

    $$f(x) = {\bf{\omega }}\varphi (x) + b = 0$$ (4)

    其中,${\bf{\omega }}$为权值矢量,$b$为偏差,${\bf{\omega }}$$b$确定分类面的位置。为找到式(4)对应的最优分类超平面,需求解带约束的最大值问题[9]

    $$\left\{ \begin{array}{l} {min} (\dfrac{1}{2}{\left\| {\bf{\omega }} \right\|^2} + C\displaystyle\sum\limits_{i = 1}^n {{\xi _i}} ) \\ s.t.\;\;{y_i}(wr_i^T + b) \geqslant 1 - {\xi _i},i = 1,2,\cdots,n \\ C > 0 \\ {\xi _i} \geqslant 0 \\ \end{array} \right.$$ (5)

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

    $$\left\{ \begin{array}{l} {max} (\dfrac{1}{2}\displaystyle\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{\alpha _i}{\alpha _j}{y_i}{y_j}({x_i} \cdot {x_j}) + \displaystyle\sum\limits_{i = 1}^N {{\alpha _i})} } } \\ s.t.\;\;\displaystyle\sum\limits_{i = 1}^N {{\alpha _i}{y_i} = 0,\;\;{\alpha _j} \geqslant 0\;(j = 1,2,\cdots ,N)} \\ \end{array} \right.$$ (6)

    计算可得最优解${\tilde{\bf \alpha }} = ({\tilde \alpha _1},{\tilde \alpha _2},\cdots{\tilde \alpha _N})$,以及分隔超平面的最优权值向量${{\omega}}$和最优偏移量$\tilde b$,最终可以使用决策函数f(x)来判断样本的类别:

    $$f(x) = {{sgn}} (\sum\limits_{i = 1}^N {{{\tilde \alpha }_i}{y_i}({x_i} \cdot x) + \tilde b} )$$ (7)

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

    $$w = \frac{1}{{{{\left\| {{{x}} - {{rssi}}} \right\|}_p}}}$$ (8)

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

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

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

    $$W = \left[ {\begin{array}{*{20}{c}} 1&1&1&1&1 \\ 1&1&1&1&1 \\ 1&1&0&1&1 \\ 1&1&1&1&1 \\ 1&1&1&1&1 \end{array}} \right]$$ (9)

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

    $$(x,y) = \frac{1}{K}\sum\limits_{i = 1}^K {({x_i},{y_i})} $$ (10)

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

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

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

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

    图  4  定位点纠偏模型示意

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

    图  5  广州地铁苏元站站厅层电子地图(局部)

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

    图  6  Android应用端操作界面

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

    表  1  3种定位算法的定位误差距离统计
    定位算法定位误差概率/%平均误差距离/m
    <1 m<2 m<3 m<4 m
    KNN25.3%73.1%94.2%98.7%2.087
    KNN+SVM27.1%79.5%95.0%98.7%1.997
    本文算法55.0%87.1%98.6%99.5%1.598
    下载: 导出CSV 
    | 显示表格

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

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

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

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

  • 图  1   定位算法流程

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

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

    图  4   定位点纠偏模型示意

    图  5   广州地铁苏元站站厅层电子地图(局部)

    图  6   Android应用端操作界面

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

    定位算法定位误差概率/%平均误差距离/m
    <1 m<2 m<3 m<4 m
    KNN25.3%73.1%94.2%98.7%2.087
    KNN+SVM27.1%79.5%95.0%98.7%1.997
    本文算法55.0%87.1%98.6%99.5%1.598
    下载: 导出CSV
  • [1] 詹 杰,吴伶锡,唐志军. 无线传感器网络RSSI测距方法与精度分析 [J]. 电讯技术,2010,50(4):83-87. DOI: 10.3969/j.issn.1001-893x.2010.04.018
    [2] 卢恒惠,刘兴川,张 超,等. 基于三角形与位置指纹识别算法的WiFi定位比较 [J]. 移动通信,2010,34(10):72-76. DOI: 10.3969/j.issn.1006-1010.2010.10.017
    [3] 朱 敏. 室内定位技术分析 [J]. 现代计算机(专业版),2008(2):79-81.
    [4] 徐超蓝,高军礼,张小花,等. 基于K-means和SVM的蓝牙室内定位算法 [J]. 传感器与微系统,2019,38(2):133-135, 139.
    [5]

    Hongyu Wang, Yan Yu, Minglu Jin, et al. Toward Robust Indoor Localization Based on Bayesian Filter Using Chirp-Spread-Spectrum Ranging [J]. IEEE Transactions on Industrial Electronics, 2012, 59(3): 1622-1629. DOI: 10.1109/TIE.2011.2165462

    [6] 李志强. 基于粒子滤波和电子地图融合的室内定位技术研究[D]. 成都: 电子科技大学, 2016.
    [7] 余彦培. 一种融合地图与传感器信息的室内地图匹配新算法 [J]. 电讯技术,2014(12):1656-1662. DOI: 10.3969/j.issn.1001-893x.2014.12.013
    [8] 桑 楠,袁兴中,周 瑞. 基于SVM分类和回归的WiFi室内定位方法 [J]. 计算机应用研究,2014,31(6):1820-1823. DOI: 10.3969/j.issn.1001-3695.2014.06.052
    [9]

    Chriki A, Touati H, Snoussi H. SVM-based indoor localization in Wireless Sensor Networks[C]// 13th International Wireless Communications and Mobile Computing Conference (IWCMC), 2017: 1144-1489.

    [10]

    Ling P, Jingbin L, Robert G, et al. Using LS-SVM Based Motion Recognition for Smartphone Indoor Wireless Positioning [J]. Sensors, 2012, 12(5): 6155-6175. DOI: 10.3390/s120506155

    [11] 邓 晨,夏 青,林 雕,等. 基于空间认知的移动室内地图设计新模式 [J]. 系统仿真学报,2014,26(9):2097-2103.
    [12] 莫 倩,熊 硕. 基于蓝牙4.0的接近度分类室内定位算法 [J]. 宇航计测技术,2014(6):66-70. DOI: 10.3969/j.issn.1000-7202.2014.06.015
    [13] 盛 庆,邓中亮,徐连明,等. 基于GIS室内定位和导航的电子地图设计与应用 [J]. 北京联合大学学报:自然科学版,2012,26(1):23-27.
    [14] 李慧姝,廖文锋,彭小河. 基于ArcGIS平台制作矢量电子地图的方法探讨 [J]. 测绘与空间地理信息,2014,37(7):144-146. DOI: 10.3969/j.issn.1672-5867.2014.07.045
    [15] 马海兵,黄智伟,黄乐乐,等. 基于ArcGIS的室内地图服务系统的设计与实现 [J]. 测绘与空间地理信息,2015,38(3):92-94. DOI: 10.3969/j.issn.1672-5867.2015.03.029
  • 期刊类型引用(1)

    1. 刘爱群,于健,王瑞,陈广泰,杜海宾. 基于Git技术的机车车载应用软件集中控制系统研究. 铁道运输与经济. 2022(02): 52-58 . 百度学术

    其他类型引用(0)

图(6)  /  表(1)
计量
  • 文章访问数:  139
  • HTML全文浏览量:  61
  • PDF下载量:  24
  • 被引次数: 1
出版历程
  • 收稿日期:  2020-02-17
  • 刊出日期:  2020-09-24

目录

/

返回文章
返回