摘 要

论文详细说明了系统的实现和测试过程，针对封闭区域导航系统的特点及环境因素对定位的影响，提出了多项导航算法优化和改进方法，使得系统在寻路速度和定位精度上有了进一步提高，能够满足用户对诸如室内导航、实时定位等功能的需求。

在实现A*寻路算法的基础上，论文提出了开闭列表的最小堆优化、粗网格、地图信息预处理、相同F值的两种优化、H值加权这五项优化措施，使得搜索步数和算法执行时间大幅减少。论文详细说明了这些优化方法的具体实现过程，并介绍如何通过测试确定优化算法中的关键因子。

论文详细介绍了使用iBeacon定位实现的过程，在分析beacon协议和原理基础上，构建系统的定位模块体系结构，即由物理层、协议层、应用层组成得三层式体系结构。对各层的实现给出了详细的分析和代码实现。除此之外，论文对使用iBeacon设备进行室内定位开发的一些关键技术进行探讨，包括三边质心算法、接收的信号强度(RSSI)噪音的高斯滤波、beacon布局拓扑设计等技术等。

关键词：封闭区域 导航系统 iBeacon A*

Design and Implementation of Closed Area Accurate Navigation System Based on iBeacon -- Implementation and Testing

Abstract

This paper describes the implementation and testing of the system in detail. According to the characteristics of the closed navigation system and the influence of the environmental factors on the location, a number of methods are proposed to optimize and improve navigation algorithms, which makes the system further improved and meets the needs of users such as indoor navigation and real-time locating.

Based on the implementation of A * path finding algorithm, the paper puts forward the five optimization measures, such as the minimum heap optimization, coarse grids, map information preprocessing, the same F value optimization and H value weighting, which makes the search step and algorithm execution time greatly reduced. The paper describes the specific implementation of these optimization methods and how to determine the key factors in the optimization algorithm by testing.

In this paper, the process of iBeacon localization is introduced in detail. Based on the analysis of beacon protocol and principle, the architecture of the locating module is constructed by three layers : physical layer, protocol layer and application layer. The implementation of each layer gives a detailed analysis and code implementation. In addition, some key techniques for the development of indoor locating using iBeacon equipment are discussed, including three-dimensional centroid algorithm, Gaussian Filtering of Received Signal Strength Indication (RSSI) noise, and beacon layout topology design.

Key Words: Closed Area; Navigation System; iBeacon; A*

目 录

摘 要 I

Abstract II

第一章 绪论 1

1.1 课题的背景及意义 1

1.2 国内外研究现状 1

1.3 本文的主要研究工作 3

1.4 本章小结 3

第二章 开发工具及相关技术 4

2.1 开发平台介绍 4

2.2 Java和Android简介 4

2.3 iBeacon简介 5

2.4 A*算法简介 5

2.5 三边质心算法简介 6

2.6 本章小结 8

第三章 系统实现 9

3.1 封闭区域导航系统的功能概述 9

3.2 A*算法的实现和优化 10

3.2.1 A*基础算法实现 10

3.2.2 开闭列表的最小堆优化 11

3.2.3 粗网格 13

3.2.4 地图信息预处理 13

3.2.5 相同F值的两种优化 14

3.2.6 H值加权 15

3.3 Beacon定位实现 16

3.3.1 物理层：Beacon硬件 16

3.3.2 协议层：iBeacon 17

3.3.3 应用层：三边质心定位算法 18

3.4 Beacon定位优化 19

3.4.1 RSSI的高斯滤波 19

3.4.2 Beacon拓扑 21

3.5 本章小结 21

第四章 系统测试 22

4.1 测试概要 22

4.1.1 测试目标 22

4.1.2 测试用例设计 22

4.1.3 测试环境与配置 33

4.1.4 测试方法和工具 33

4.2 测试内容和执行情况 33

4.3 功能 34

4.3.1 定位模块 34

4.3.2 绘制路径模块 35

4.3.3 数据库模块 35

4.3.4 规划路径模块 36

4.3.5 UI模块 37

4.3.6 语音导航模块 37

4.4 性能（效率） 37

4.4.1 测试用例 38

4.4.2 H值的加权测试 38

4.4.3 相同F值不同处理方式测试 39

4.4.4 不同粗网格大小gridsize测试 39

4.5 易用性 39

4.6 兼容性 40

4.7 安装和手册 40

4.8 覆盖分析 40

4.9 本章小结 40

第五章 总结和展望 41

5.1 本文工作总结 41

5.2 下一步工作展望 42

参考文献 43

致谢 45

1. 绪论

1.1 课题的背景及意义

当前，个人智能手机终端普及，智能手机也给人们的生活带来各种各样的便利。手机上的地图app满足了人们对室外定位和导航的需求，室内封闭区域如机场、商场、医院等大型公共区域人流复杂，寻找一条路径并不直观。随着无线传感器的发展，为室内定位提供了成本和功耗更低的设备，让室内定位和导航不在遥远，为用户提供各种基于位置的服务。

本文所解决的重点就是设计一种用于封闭区域精确导航的系统。目前主流的定位导航系统是GPS，然而GPS虽然在室外有较高的定位精度（10m），却无法应用于室内封闭区域的导航。WiFi定位虽然可以用于室内导航，但其耗电量较高且具有一定的安全隐患。蓝牙低能耗(BLE)技术，在满足低功耗的同时，也有较好的定位精度（1-5m）。因此本系统采用Apple iBeacon标准的BLE设备作为用于定位的物理设备。

相关图片展示：