【摘要】：最短路徑分析作為GIS中最重要的空間分析功能之一,已經(jīng)廣泛地應(yīng)用于路徑導(dǎo)航、管網(wǎng)優(yōu)化設(shè)計、交通疏導(dǎo)等方面。隨著交通路網(wǎng)、管道網(wǎng)絡(luò)等設(shè)施的規(guī)模逐年擴大,由這些現(xiàn)實設(shè)施抽象出來的空間網(wǎng)絡(luò)數(shù)據(jù)的規(guī)模也逐漸趨向于海量化。如何使大規(guī)�？臻g網(wǎng)絡(luò)得到快速處理是GIS中最短路徑算法所要面對的一個巨大挑戰(zhàn)。單機環(huán)境下GIS平臺的最短路徑分析處理大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)會出現(xiàn)計算效率較低的情況,有時甚至?xí)斐蒅IS軟件運行崩潰。云計算平臺Hadoop在處理大數(shù)據(jù)方面,具有運算效率高和應(yīng)用成熟、穩(wěn)定的優(yōu)勢。為此,本文對基于Hadoop的GIS網(wǎng)絡(luò)最短路徑算法進行了研究。(一)本文研究了GIS網(wǎng)絡(luò)矢量數(shù)據(jù)在HBase中的存儲與管理。根據(jù)GIS網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)進行解析,并通過適當?shù)腍Base表結(jié)構(gòu)設(shè)計,解決了GIS網(wǎng)絡(luò)在Hadoop下的存儲問題,為GIS網(wǎng)絡(luò)在Hadoop云平臺中進行最短路徑并行計算創(chuàng)造了前提條件。并且通過設(shè)計相關(guān)HBase表,實現(xiàn)了動態(tài)權(quán)重的賦值問題,使得最短路徑算法能夠延伸為最優(yōu)路徑算法。(二)本文設(shè)計了基于MapReduce的鄰接表結(jié)構(gòu)生成算法。該算法的設(shè)計結(jié)合了鄰接表結(jié)構(gòu)的特點與MapReduce的運行原理,在Hadoop平臺下能有效地解決大規(guī)模GIS網(wǎng)絡(luò)的鄰接表結(jié)構(gòu)生成問題。通過該算法過程得到的鄰接表數(shù)據(jù)結(jié)構(gòu)給本文最短路徑算法提供了數(shù)據(jù)結(jié)構(gòu)保障。(三)本文提出了基于Hadoop的GIS網(wǎng)絡(luò)最短路徑并行算法(H_PGNSP)。該算法流程除了上文所述的計算過程外,還包括改進的最短路徑算法計算過程。改進的算法以Lin J提出的廣度優(yōu)先最短路徑并行算法(PBFS_SP)為思想基礎(chǔ),進行改進設(shè)計。通過搭建Had oop云平臺,將改進的算法與PBFS_SP算法和Dijkstra算法進行了實驗對比分析。實驗表明改進算法在網(wǎng)絡(luò)規(guī)模達到一定程度時相較Dijkstra算法計算效率得到了較大的提高,在大規(guī)模的網(wǎng)絡(luò)下,三個算法中改進算法計算效率最高。(四)最后,在模擬的應(yīng)急場景下,將本文算法H_PGNSP用于救援路徑的制定。算法計算結(jié)果通過GIS技術(shù)能與相關(guān)GIS平臺無縫結(jié)合,且易于實現(xiàn)最短路徑的空間可視化。研究結(jié)果表明,與單機GIS平臺相比,本文算法可解決求解大規(guī)模網(wǎng)絡(luò)最短路徑的效率問題。而且相較于其他并行最短路徑算法,本文算法能與相關(guān)GIS平臺兼容,在空間可視化表達上具有一定的優(yōu)勢,效率也得到了較好的提高。
[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.
【學(xué)位授予單位】：江西理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：P208

【參考文獻】

相關(guān)期刊論文 前10條

1 王少華;;超圖平臺軟件創(chuàng)新:超圖在線GIS平臺(SuperMap Online)技術(shù)簡介[J];地球信息科學(xué)學(xué)報;2016年09期

2 尹鵬程;付麗莉;蔡先孌;鄧玉鋒;紀國平;;不動產(chǎn)統(tǒng)一登記信息平臺建設(shè)探討[J];測繪科學(xué);2016年11期

3 閆春望;黃瑋;王勁松;;一種并行模糊神經(jīng)網(wǎng)絡(luò)最短路徑算法[J];計算機應(yīng)用研究;2016年11期

4 王凱;曹建成;王乃生;郭朝陽;張哲;;Hadoop支持下的地理信息大數(shù)據(jù)處理技術(shù)初探[J];測繪通報;2015年10期

5 徐建閩;王鈺;林培群;;大數(shù)據(jù)環(huán)境下的動態(tài)最短路徑算法[J];華南理工大學(xué)學(xué)報(自然科學(xué)版);2015年10期

6 鈕亮;張寶友;;基于云計算求解城市物流配送最短路徑研究[J];科技通報;2015年05期

7 張文金;許愛軍;;基于云計算的混合并行遺傳算法求解最短路徑[J];電子技術(shù)應(yīng)用;2015年03期

8 孫文彬;譚正龍;王江;趙帥陽;;基于多粒度通訊的Dijkstra并行算法優(yōu)化[J];中國礦業(yè)大學(xué)學(xué)報;2014年05期

9 楊慶芳;梅朵;鄭黎黎;馬明輝;王偉;;基于云計算的城市路網(wǎng)最短路徑遺傳算法求解[J];華南理工大學(xué)學(xué)報(自然科學(xué)版);2014年03期

10 范建永;龍明;熊偉;;基于Hadoop的云GIS體系結(jié)構(gòu)研究[J];測繪通報;2013年11期

相關(guān)碩士學(xué)位論文 前4條

1 李寬;基于HDFS的分布式Namenode節(jié)點模型的研究[D];華南理工大學(xué);2011年

2 霍樹民;基于Hadoop的海量影像數(shù)據(jù)管理關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2010年

3 盧照;基于城市路網(wǎng)最短路徑并行搜索算法的研究[D];陜西師范大學(xué);2010年

4 朱珠;基于Hadoop的海量數(shù)據(jù)處理模型研究和應(yīng)用[D];北京郵電大學(xué);2008年

，

本文編號：2221014