室内导航改进算法探究

敬远兵，李 奎

室内导航改进算法探究

敬远兵1，李 奎2

（1. 内江师范学院 地理与资源科学学院，四川 内江 641112；2. 西南交通大学 地球科学与环境工程学院，成都 611756）

针对室内导航最优路径传统A*算法研究绝大部分以2维空间路径规划为切入点，存在诸多局限且尚未解决室内3维空间（多楼层）复杂环境下导航定位的最优路径规划的问题，提出一种室内导航改进算法：在WiFi、二维码等技术应用于室内导航定位的基础上预先对室内兴趣点（POI）进行分层分类处理，并通过映射建立POI与寻路节点的联系；然后赋予电梯和楼梯联通节点不同的权重，采用2种数据结构来描述各层的寻路节点。实验结果表明：改进后的A*算法在室内多层空间节点导航中具有普适性和可靠性，可保证复杂地图环境下最优路径规划导航的唯一性，能够满足室内多层空间最优路径规划导航及其个性化的需求。

室内导航定位；最优路径；分层A*算法

0 引言

位置服务正迎来从室外导航向室内外无缝定位导航发展的新纪元，融合导航卫星与地面网络的天地一体化室内外无缝导航系统成为了国家重大发展战略[1]。目前，室内外高精度无缝导航定位已成为国内外研究热点，国内外众多学者在该领域进行了大量研究，其中部分关键技术已取得一定突破，提出了一些普适性较强的解决方案和算法[2-4]。虽然文献[5]对Okumura-Hata、Motley等多种适用性较好的室内无线定位信号源传播模型进行了详细介绍；但在室内环境，无线定位信号主要通过衍射、散射等形式传播，而楼层数量增加、墙壁类型的多样化，使得信号衰减明显，同时易受多径传播干扰，导致导航定位误差加大，继而起不到预想效果。因此，室内导航定位受到定位时间、精度以及复杂室内环境等条件限制，也受到多路径的影响，室内导航定位特别是个性化位置服务还存在诸多难题需要不断研究加以解决。近年来，在室内导航最优路径搜寻方面，文献[6-7]提出通过对节点归一化权值处理、调整A*算法代价函数值、增加寻路过程中用户感兴趣点备选可能性的方法提高室内导航定位精度；文献[8]提出了适用于不规则城市路网寻路的改进A*算法，该方法亮点是该算法克服了死循环搜索问题；文献[9-11]研究了搜寻多条最短路径问题和对其他不同应用环境分别提出了改进的A*算法。但上述文献大多针对电竞游戏和城市道路网寻路问题而主要在2维平面路径规划方面进行研究，故本文将室内3维空间跨楼层环境下的路径规划导航算法作为探究的重点。

1 室内无线定位方法

传统室内定位技术[12-13]定位原理主要为到达角(arrival of angle, AOA)、到达时(time of arrival, TOA)定位以及到达时间差(time difference of arrival, TDOA)定位；但在无线局域网(wireless local area networks, WLAN)环境中，由于无线信号接入点(access point, AP)密度较大，信号传输时延短，对终端探测设备灵敏度要求高，并且室内信号传播环境复杂，测量到的是在相位角和幅度有较大失真的复合信号，因此，上述定位方法均存在较大非视距误差(no line of sight error, NLOS)。当前，解决这一难题的主要方法是提交信号强度指示(received signal strength indication, RSSI)位置指纹匹配定位技术[14]，该方法首先在室内位置提取来自AP点的信号强度，通过去噪处理后，连同采样点位置信息一起作为特征参数存入指纹库，定位终端测量其接收到的信号强度，与指纹库进行匹配计算，进而计算出终端位置信息。这种方法最大的不足在于输出的结果存在不连续和不稳定问题，要实现对终端的连续平滑导航定位，需进一步对结果后端滤波处理。另一方面，智能手机大多带有惯性传感器，如加速度计、罗盘等，这使得融合WLAN与行人航迹推算(pedestrian dead reckoning, PDR)的组合室内导航定位成为可能，将显著提高定位精度和可靠性。此外，2维码技术近年来应用于室内导航定位，有效提升了终端初始化位置计算速度和精度，其提供的绝对位置信息直接解决了室内定位误差累计问题。对于室内用户而言，终端所处的高程（楼层信息）是一个短期不变量，在关键位置布设楼层切换信标节点，利用所接收到的RSSI信号，采用基于信号强度迟滞辅助的算法就能实现无缝楼层切换，当楼层信息确定后，终端的运动只需考虑和2个运动方向。完整的室内个性化位置服务包括定位和导航2个方面，而定位方面近年来的研究基本解决，其导航方面的关键是为用户快速规划出室内最优路径提供选择性服务，这是本文将探究解决的主要内容。

2 室内最优路径导航算法

2.1 A*算法

路径规划算法核心思路主要是计算寻路节点图中当前节点(CN)与起始节点(IN)和目标节点(GN)通路估价函数值。在个性化导航中，估价函数考虑用户特定需求计算出综合加权值；因此本文讨论最优路径。常用寻路算法有2类：①只计算CN到IN代价函数，如Dijkstra、Floy算法；②带有启发式搜索算法，当前最适合室内导航的A*算法属于这一类。其估价函数为

2.2 启发函数特性分析

2.3 改进的分层A*算法

传统A*算法中，启发函数通常采用的曼哈顿或欧式距离无法实现室内个性化寻路，其对复杂室内地图环境适应性较弱，同时存在搜索速率不高等缺陷。为实现室内多层空间最优路径规划，在此提出改进的同时含有方向和距离约束的分层A*算法，其计算方法为

3 室内地图数据处理

表1 节点表数据结构

4 实验与结果分析

4.1 算法搜索步骤

4.2 模拟计算

利用搜集的某办公楼建筑平面计算机辅助设计(computer aided design, CAD)图为实验对象（如图1），在CAD图上预先标记POI点，根据室内地图的复杂程度与POI点密集程度定义寻路节点，根据POI点与寻路节点的相对位置确定映射关系，即各POI点映射在与之距离最近的寻路节点中。在统一平面坐标系下制作室内多层寻路节点图（如图2），使之在有效覆盖整个地图的同时，最大限度减少寻路节点数据量，把POI点与寻路节点分开表示，并通过映射关系联系，以此达到降低寻路图规模和提高搜索速率的目的。

图1 楼层平面图

在寻路节点图中选取起点01009、终点04018，利用改进后的分层A*算法计算与验证。本次采用Python3.4编程计算结果：第一层计算完成后，OPEN集合给出的最优路径需要通过的联通节点为[01009, 01017, 04017, 04018]；第二层计算执行后，OPEN集合分别给出的节点为[01009, 01008, 01021, 01020, 01019, 01018, 01017]；[04017, 04018]。经过节点回溯，最终路径为：01009→01008→01021→01020→ 01019→01017→01017→04017→ 04018。

4.3 结果分析

为进一步检验算法鲁棒性和适用性，选取同楼层不同位置起终节点、跨单楼层不同位置起终节点和跨多楼层不同位置起终节点多次计算，将现场规划出的最优路径与改进后A*算法计算得到的路径相比较，发现改进后的分层A*算法总能快速搜寻一条通路，其寻得的路径与人工实地预设的最优路径基本一致。图3给出了改进后分层A*算法寻得的4条代表性最优路径计算结果。

图3 仿真结果

仅以距离约束方面考虑（由图2可知），01009点到01017点还存在另一条最优路径：01009→ 01008→01007→01006→01005→01004→01017，该条路径相较于前者，在01009点和01004点有2次直角转向，而前者只在01021点有一次直角转向。由于改进的启发函数包含方向约束信息，使得第二条路径的估价函数值大于第一条，从而最终计算出的最优路径为第一条。对于01002点到02002点的寻路结果，因为起终点均靠近楼梯节点且只跨单楼层，算法给出的联通节点不是与起终点距离较远的电梯节点。可以看出：本次实验对电梯和楼梯节点赋予的权重是合理有效的。通过实验结果分析得出改进后算法具有以下基本优点：

1）在估价函数中加入方向约束后，有效保证了最优路径的唯一性，同时实现了复杂室内地图环境下用户直行的个性化需求，进一步增强了算法对复杂室内地图环境的适应性。

2）传统A*算法启发函数通常只考虑距离启发信息且均采用单次计算，其应用主要为2维平面的寻路，改进后的A*算法采用分层计算的思想，实现了室内3维空间跨楼层的最优路径寻路。

5 结束语

本文通过分析传统导航算法，对3维空间下多楼层最优路径导航算法进行改进探究，采用改进的分层A*算法进行了仿真模拟实验导航，解决了跨楼层节点最优路径规划问题；综合室内复杂地图环境下用户对距离最短和直行的需求，在第二层计算中，引入同时考虑方向和距离启发信息的启发函数，把POI点与寻路节点分开处理，以映射的方式建立联系，有效避免了直接搜寻POI节点数据量大、速率低的问题。仿真实验结果表明，改进的分层A*算法能以较好的鲁棒性应用于跨楼层最优路径规划，具有较强可靠性，无论是改进前还是改进后的算法，其运算速率取决于节点的数量和算法本身的复杂度。本次实验仅对室内地图数据进行合理的处理，建立POI点与寻路节点映射关系后，较好地提高了A*算法搜索速率。对于室内POI点密集程度高且不规则的大型城市建筑而言，其POI点和寻路节点数多达数千个，如何提高室内寻路算法运算速率还需进一步研究。

[1] PRIYANTHA N B, CHAKRABORTY A, BALAKRISHNAN H. The cricket location-support system[C]//Association for Computing Machinery(ACM).Proceedings of the 6th Annual International Conference on Mobile Computing and Networking. Boston,Massachusetts:Association for Computing Machinery,Inc., 2000:32-43.

[2] KUSHKI A, PLATANIOTIS K N, VENETSANOPOULOS A N. Kernel-based positioning in wireless local area networks[J]. IEEE Transactions on Mobile Computing, 2007, 6(6): 689-705.

[3] FANG S H, LIN T N, LIN P C.Location fingerprinting in a decorrelated space[J].IEEE Transactions on Knowledge and Data Engineering, 2008, 20(5): 685-691.

[4] FANG S H, LIN T N. Projection-based location system via multiple discriminant analysis in wireless local area networks[J]. IEEE Transactions on Vehicular Technology, 2009, 58(9): 5009-5019.

[5] 邓中亮, 余彦培, 徐连明, 等. 室内外无线定位与导航[M]. 北京: 北京邮电大学出版社,2013.

[6] 卞维骏. 个性化室内导航研究[D]. 武汉: 武汉理工大学, 2015.

[7] 史辉, 曹闻. A*算法的改进及其在路径规划中的应用[J]. 测绘与空间地理信息, 2012, 32(6): 209-211.

[8] 漆阳华, 杨战平. A*的改进路径规划算法[J]. 信息与电子工程, 2009, 7(4): 327-329.

[9] 王树西, 李安渝. Dijkstra算法中的多邻接点与多条最短路径问题[J]. 计算机科学, 2014,41(6): 217-221.

[10] 谭宝成, 王培. A*路径规划算法的改进及实现[J].西安工业大学学报, 2012, 32(4):325-329.

[11] 武雪玲, 李清泉, 任副.基于分层分块数据组织的双向A*算法[J]. 测绘信息工程, 2006, 31(6): 1-3.

[12] 颜俊杰. 基于WIFI的室内定位技术研究[D]. 广州:华南理工大学, 2013.

[13] 范霄. 基于WIFI的无线室内定位[D]. 青岛: 山东科技大学, 2013.

[14] BAHL P, PADMANABHAN V N.Radar:an in-building RF-based user location and tracking system[C]//The Institute of Electrical and Electronic Engineers(IEEE).Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies. Tel Aviv, Israel: IEEE, 2000: 775-784.

[15] 熊伟, 张仁平. A*算法及其在地理信息系统中的应用[J]. 计算机系统应用, 2007, 22(4): 15-17.

[16] 钟敏. A*算法估价函数特性分析[J]. 武汉工程职业技术学院学报, 2006, 18(2): 32-33.

Discussion on improved algorithm of indoor navigation

JING Yuanbing1, LI Kui2

（1.Shcool of Geography and Resources Science, Neijiang Normal University, Neijiang, Sichuan 641112, China;2.Faculty of Geosciences and Environmental Engineering, Southwest Jiaotong University, Chendu 611756, China）

Aiming at the problems that there exists limitation in the study on traditional A* algorithm for the optimal path-planning of indoor navigation which usually starts from two-dimensional spatial path-planning, and it is still unsolved for optimal path-planning of indoor navigation under the complex environment of three-dimensional space (multi-floor), the paper proposed an improved algorithm of indoor navigation: the hierarchical classification of indoor POI nodes was carried out with the technology of WiFi and QR-code, and the connection between POI points and route-seeking nodes was established by mapping; by assigning different weights to elevator and staircase connection nodes respectively, two kinds of data structures were used to describe the path finding nodes of each layer. Experimental result showed that the improved A* algorithm would be universal and reliable in the indoor navigation with multi-layer space nodes, and the uniqueness of the optimal path-planning navigation under complex map environment could be guaranteed, which could meet the requirements of optimal path-planning navigation in indoor multi-layer space for personalized needs.

indoor navigation and positioning; optimal path; hierarchical A* algorithm

P228

A

2095-4999(2019)04-0037-05

敬远兵，李奎.室内导航改进算法探究[J].导航定位学报,2019,7(4): 37-41.（JING Yuanbing，LI Kui.Discussion on improved algorithm of indoor navigation[J].Journal of Navigation and Positioning,2019,7(4): 37-41.）

10.16547/j.cnki.10-1096.20190407.

2019-02-16

四川省教育厅资助科研项目（18ZB0320)。

敬远兵（1977—），四川安岳人，本科，高级工程师，研究方向为卫星导航定位应用。