基于Hadoop的GIS网络最短路径算法研究

发布时间：2018-09-03 19:58

【摘要】：最短路径分析作为GIS中最重要的空间分析功能之一,已经广泛地应用于路径导航、管网优化设计、交通疏导等方面。随着交通路网、管道网络等设施的规模逐年扩大,由这些现实设施抽象出来的空间网络数据的规模也逐渐趋向于海量化。如何使大规模空间网络得到快速处理是GIS中最短路径算法所要面对的一个巨大挑战。单机环境下GIS平台的最短路径分析处理大规模网络数据会出现计算效率较低的情况,有时甚至会造成GIS软件运行崩溃。云计算平台Hadoop在处理大数据方面,具有运算效率高和应用成熟、稳定的优势。为此,本文对基于Hadoop的GIS网络最短路径算法进行了研究。(一)本文研究了GIS网络矢量数据在HBase中的存储与管理。根据GIS网络的数据结构进行解析,并通过适当的HBase表结构设计,解决了GIS网络在Hadoop下的存储问题,为GIS网络在Hadoop云平台中进行最短路径并行计算创造了前提条件。并且通过设计相关HBase表,实现了动态权重的赋值问题,使得最短路径算法能够延伸为最优路径算法。(二)本文设计了基于MapReduce的邻接表结构生成算法。该算法的设计结合了邻接表结构的特点与MapReduce的运行原理,在Hadoop平台下能有效地解决大规模GIS网络的邻接表结构生成问题。通过该算法过程得到的邻接表数据结构给本文最短路径算法提供了数据结构保障。(三)本文提出了基于Hadoop的GIS网络最短路径并行算法(H_PGNSP)。该算法流程除了上文所述的计算过程外,还包括改进的最短路径算法计算过程。改进的算法以Lin J提出的广度优先最短路径并行算法(PBFS_SP)为思想基础,进行改进设计。通过搭建Had oop云平台,将改进的算法与PBFS_SP算法和Dijkstra算法进行了实验对比分析。实验表明改进算法在网络规模达到一定程度时相较Dijkstra算法计算效率得到了较大的提高,在大规模的网络下,三个算法中改进算法计算效率最高。(四)最后,在模拟的应急场景下,将本文算法H_PGNSP用于救援路径的制定。算法计算结果通过GIS技术能与相关GIS平台无缝结合,且易于实现最短路径的空间可视化。研究结果表明,与单机GIS平台相比,本文算法可解决求解大规模网络最短路径的效率问题。而且相较于其他并行最短路径算法,本文算法能与相关GIS平台兼容,在空间可视化表达上具有一定的优势,效率也得到了较好的提高。
[Abstract]:As one of the most important spatial analysis functions in GIS, shortest path analysis has been widely used in path navigation, pipe network optimization design, traffic diversion and so on. With the scale of transportation network, pipeline network and other facilities expanding year by year, the scale of spatial network data abstracted from these practical facilities also gradually tends to Yu Hai quantification. How to quickly process large scale space networks is a huge challenge for the shortest path algorithm in GIS. The analysis and processing of the shortest path of the GIS platform in a single computer environment will result in the low computational efficiency of large scale network data, and sometimes even lead to the GIS software running crash. Cloud computing platform Hadoop has the advantages of high efficiency, mature application and stability in dealing with big data. Therefore, the shortest path algorithm of GIS network based on Hadoop is studied in this paper. (1) this paper studies the storage and management of GIS network vector data in HBase. By analyzing the data structure of GIS network and designing the appropriate HBase table structure, the storage problem of GIS network under Hadoop is solved, which creates the precondition for GIS network to parallel compute the shortest path in the Hadoop cloud platform. By designing the related HBase table, the dynamic weight assignment problem is realized, which makes the shortest path algorithm extend to the optimal path algorithm. (2) in this paper, the algorithm of building adjacent table structure based on MapReduce is designed. The design of the algorithm combines the characteristics of the adjacent table structure and the operation principle of MapReduce, and it can effectively solve the problem of generating the adjacent table structure of large-scale GIS network under the Hadoop platform. The data structure of the adjacency table obtained by the algorithm provides the data structure guarantee for the shortest path algorithm in this paper. (3) A parallel shortest path algorithm (H_PGNSP) for GIS networks based on Hadoop is proposed. In addition to the calculation process described above, the algorithm also includes the improved shortest path algorithm. The improved algorithm is based on the breadth-first shortest path parallel algorithm (PBFS_SP) proposed by Lin J. By building Had oop cloud platform, the improved algorithm is compared with PBFS_SP algorithm and Dijkstra algorithm. The experimental results show that the improved algorithm is more efficient than the Dijkstra algorithm when the network size reaches a certain degree. In the large-scale network, the improved algorithm has the highest computational efficiency. (4) finally, in the simulated emergency scenario, the H_PGNSP algorithm is used to make the rescue path. The result of the algorithm can be seamlessly combined with the related GIS platform by GIS technology, and it is easy to realize the spatial visualization of the shortest path. The results show that the proposed algorithm can solve the efficiency problem of solving the shortest path of large-scale network compared with the single GIS platform. Compared with other parallel shortest path algorithms, this algorithm is compatible with related GIS platforms, and has some advantages in spatial visualization, and its efficiency is also improved.
【学位授予单位】：江西理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：P208

【参考文献】