基于位置指纹和行人航位推算的溶洞内定位导航系统的设计与实现

陈炎清，陈金龙，刘忞劼，杨天乐

(桂林电子科技大学计算机与信息安全学院，广西 桂林 541004)

0 引言

溶洞景区每年会接待大量的游客。然而在溶洞内移动信号、GPS信号很弱，手机通信和定位导航等功能基本无法使用，当游客在溶洞中出现迷路，甚至脱离队伍等情况时，安保人员很难进行人员查找或者人员定位，并开展救援；此外，由于溶洞内道路狭窄，导游很难集中讲解，游客无法获取洞内景点信息，导致旅游体验较差。因此，设计一种能够在溶洞内使用的人员室内定位系统显得非常迫切。

在众多定位手段中，蓝牙定位因其价格低和信号相对稳定，逐渐成为室内定位的首选方法[1]。然而受传输距离的限制，蓝牙信号覆盖的范围较小，尤其在地形复杂的溶洞内部，信号的传播易受影响，容易发生位置跳跃的现象。如果只采用基于蓝牙信标的指纹定位方法，定位精度不能满足需求。行人航位推算(PDR)因无需部署信标节点、成本低廉的特点被广泛应用于室内定位中[2]。行人航位推算在短距离定位中有着较高的精度，但随着行走距离的增长，推算的误差会累积导致其精度严重降低。基于以上问题，采用互补滤波将两种定位方法融合，设计了一种基于位置指纹和行人航位推算的溶洞定位导航系统：一方面，利用行人航迹推算减少指纹匹配的开销，同时减少发生定位结果跳跃的现象，增强系统对环境的鲁棒性；另一方面，通过位置指纹法减小行人航迹推算产生的累计误差，并通过融合定位的结果进一步修正步长模型的参数。

1 溶洞内的定位导航原理

本文采用基于位置指纹和行人航位推算的融合定位方法，该方法分离线阶段与在线阶段两部分实施。离线阶段，先将整个溶洞地图划分区域，根据区域地形布置蓝牙信标，记录每个区域蓝牙信标反馈的信号强度，以此作为特征离线保存，并建立位置指纹库。在线阶段，通过加权KNN算法匹配指纹库中保存的信号强度特征，获取初始位置坐标；在初始坐标基础上结合行人航位推算，获取推算坐标posPDR；同时进行指纹定位，获取定位坐标posRSSI；使用互补滤波处理坐标posPDR与posRSSI，得到最终坐标posFinal，认定posFinal即为当前的位置；重复以上步骤，直至本次定位结束。

本文采用Dijkstra算法规划路径，采用TSP算法对途经点进行路径规划，为用户提供从起点到目的地的最优途径。将时间、距离和费用等数据信息作为地图的相关属性保存到数据库中，之后创建道路的拓扑网络结构，把道路电子地图变换为带权值的有向图，进而通过算法求解带权值的有向图的最短路径[3]。

2 系统关键算法的实现

2.1 指纹匹配算法

本文采用加权KNN算法实现指纹的匹配[4-5]。加权KNN算法是在KNN算法的基础上进一步优化，引入了K个相似指纹中距离越远对定位结果的贡献越小的考虑，基于权重处理位置坐标，使其计算出的定位结果比KNN算法直接取平均值计算出的定位结果更加精确。该算法首先计算待测点指纹与位置指纹之间的欧式距离，并按距离由小到大的顺序排列指纹数据。之后选取K个欧氏距离最小的位置指纹，取距离的倒数作为权重进行加权计算，从而获取待测点的位置坐标，记为posRSSI，计算公式为

(1)

式中：posRSSI表示待测点的坐标；posi表示K个距离最近的位置指纹的坐标；Li表示欧氏距离。

2.2 行人航位推算

行人航位推算能在无信标条件下，通过三轴加速度值和方向角感知行人在行进过程中的加速度和方向角，并利用这些数据对行走路线进行相对定位，从而达到对行人进行定位跟踪的目的，计算公式为：

(2)

式中：(xk,yk)为初试位置；(xk+1,yk+1)为下一步的位置；d为步长；θ为航向角。

PDR算法中误差的主要来源是对步长的估算不精确，步长主要受人员、环境、行走速度的影响等。本文采用改进的非线性步长估计模型[6]，降低快速行走时精度下降明显的问题，其计算公式为

(3)

式中：L表示估算步长；K1和K2为模型系数；Tstep为行走时间；aavg、amax和amin为一步内平均、最大和最小的加速度。

2.3 融合算法

针对位置指纹法在离线阶段工作量大、信号易受溶洞地形干扰、定位结果会发生跳跃的现象，结合行人航位推算低成本、短距离定位精度高但存在累计误差的特点，本文采用互补滤波算法将指纹定位结果与行人航位推算结果融合，获得更加符合真实行走轨迹的持续稳定的定位结果：

posFinal=λposPDR+(1-λ)posRSSI

(4)

式中，λ为行人航位推算的权重，本文取0.75。

融合定位结果相较行人航位推算结果更加符合实际坐标，将此结果向行人航位推算模块反馈，以修正步长估计模型中设定的参数，使其自适应步长大小与行走速度的变化。

3 系统设计

本系统由蓝牙信标、客户端、服务器3部分组成。蓝牙信标参照溶洞地形规律部署，周期性地广播信号。客户端基于Android平台开发，由Eclipse、ADT、Android SDK搭建。服务器由Eclipse、Tomcat、MySQL组成。客户端和服务器之间采用HTTP协议进行数据交互。

本系统主要为游客游览溶洞景区设计，但其设计方法同样适用于大型商场、停车场等室内场景。根据游客真实需求，客户端App大致分成4种功能模式。普通模式主要提供用户注册登录以及地点信息介绍等功能。导航模式提供本系统的关键功能，通过位置指纹与行人航位推算的融合定位方法，获取游客实时位置，并通过最优路径的计算，提供导航线路。游客只需点击景点，即可实现精准导航，帮助游客顺利到达相应景点，从而达到“一触即达”的观览体验。救援模式同样基于定位方法，可实时查看安保人员位置和活动轨迹，当游客通过手机终端向控制中心发送求救信息时，控制中心可在第一时间派遣距离游客最近的安保人员赶往事发地点。游览模式则提供整个场景的推荐游览路线。客户端App功能结构见图1。

图1 客户端App功能结构

4 系统实现与测试

该系统测试应用于桂林芦笛岩景区。用户定位功能与线路导航功能测试如下。

4.1 用户定位功能测试

在总面积约388 m2的溶洞环境下部署iBeacon信标64个，手持装有本文系统的安卓手机进行多组定位实验，每组实验分别定位5、10、15、20、25次，计算定位结果与真实位置间的误差，如表1所列。

从表1可知，在定位次数不多时，基于位置指纹和行人航位推算的融合定位方法造成的定位误差波动较大，最大平均误差达到1.66 m，最小平均误差达到1.30 m。随试验次数的不断增加，最终误差稳定在1.42 m左右，该系统在溶洞复杂的地形环境下定位精度达标。

表1 不同实验次数下的定位误差

为验证本文算法相较同类定位算法在性能上的提升，进行以下对比实验。分别使用装有行人航位推算、位置指纹法和本文算法的定位系统的安卓手机在相同的轨迹上行走120 m，并在行走距离(设行走距离为S)为20、40、60、80、100 m处计算定位位置与真实位置之间的误差距离。为保证实验的可靠性，将以上对比实验进行5次，取5次实验在测量点的误差均值，结果见表2。

表2 3种定位算法在相同轨迹下的平均误差 m

由表2可知，行人航位推算在短距离内误差较低，随着行走距离的增加与溶洞内行走方向的多次改变，其定位误差越来越大，显然不符合溶洞定位系统的精度要求。位置指纹法的定位误差较稳定，但在单次实验中存在定位结果明显波动的地方，其最大定位误差达2.02 m。本文算法整体定位结果更加稳定，相较前两种定位算法有明显的精度提升，证明本文算法在环境复杂的溶洞内部仍具有较好的鲁棒性，符合定位需求。

4.2 线路导航功能测试

在线路导航功能测试中，设置当前位置为起点，大海螺景点为终点，形成最优导航路径。导航路径精确，满足导航需求，效果图如图2所示。

图2 线路导航效果图

5 结语

文章设计并实现了基于位置指纹和行人航位推算的溶洞内定位导航系统，提供了人员定位、线路导航、遇险救援等功能，在溶洞复杂的地形环境下定位精度稳定在1.42 m，导航路径精确，给游客提供了精准且全面的位置服务，提升了景区的服务质量。在后续工作中，将建立游客流量控制系统，引入热力图观测游客热衷区域，控制景区人流量，将游客的密集程度作为线路导航的参考因素，进一步增加游客游览质量。