適用于Hadoop云平臺的洪水淹沒分析并行算法

劉小生 黃秋鋒 趙愛國

摘要：數(shù)字高程模型（Digital Elevation Model， DEM）特殊的數(shù)據(jù)結(jié)構(gòu)有利于數(shù)據(jù)在計算機中進行計算，但其數(shù)據(jù)量大，受計算機性能的限制，無法滿足大規(guī)模洪水淹沒分析的需要。針對單機計算能力有限以及有源淹沒分析遞歸算法占用計算機資源較多的問題，提出了一種利用Hadoop云平臺進行洪水淹沒分析的并行算法。該算法對研究區(qū)域DEM按規(guī)則格網(wǎng)的思想進行劃分，將大規(guī)模的研究區(qū)分割成多個規(guī)則的小區(qū)域。在指定水位下，對每個小區(qū)域進行數(shù)據(jù)壓縮，計算每個柵格單元的淹沒值，并將同一行中相連的淹沒柵格序列記為淹沒塊，每個淹沒塊包含該柵格序列所屬的區(qū)塊號、行號、起始列號、終止列號以及淹沒標記;當(dāng)不同行或不同區(qū)域中的淹沒塊相互連通時，需對其淹沒標記進行一致性設(shè)計。最終，根據(jù)淹沒點所在淹沒塊的淹沒標記提取出淹沒點所在的淹沒區(qū)，即為實際的淹沒范圍。實驗結(jié)果表明，在指定淹沒水位下，通過該算法可以快速提取淹沒范圍以及實現(xiàn)淹沒水深的計算。

關(guān) 鍵 詞：洪水淹沒分析; 并行運算; 圖像處理; Hadoop; 數(shù)字高程模型

1 研究背景

受到極端天氣的影響，洪澇災(zāi)害爆發(fā)率越來越高，其強大的破壞性嚴重地威脅著國民經(jīng)濟和人民財產(chǎn)安全，為此，開展準確的洪水淹沒分析可為防洪救災(zāi)工作提供強有力地科學(xué)依據(jù)[1]。如何高效率地進行洪水淹沒分析與預(yù)報，是防洪救災(zāi)工作的重要環(huán)節(jié)[2]。目前，國際上的洪水淹沒分析主要以兩種方式為主，包括分布式架構(gòu)的水文模型和數(shù)字高程模型（DEM）結(jié)合GIS技術(shù)[3]。分布式架構(gòu)水文模型考慮到了水循環(huán)的基本過程[4-5]，包括蒸散發(fā)量、植物截留、地表下滲和土壤飽和度等，能夠較真實地反映洪水的淹沒過程;但是其針對性較強，普適性較差，并受地區(qū)和環(huán)境等因素的限制，數(shù)據(jù)采集困難，而且模型構(gòu)建較為復(fù)雜。在數(shù)據(jù)缺失的地區(qū)，分布式架構(gòu)的水文模型的可用性更低。

相關(guān)研究者發(fā)現(xiàn)，地形因素是形成洪水淹沒區(qū)的主要因素，而數(shù)字高程模型能夠真實地表達地面起伏情況[6-8]。因此，利用數(shù)字高程模型和GIS 技術(shù)相結(jié)合的方式進行洪水淹沒分析，可以彌補分布式水文模型在數(shù)據(jù)缺少時的不足，而且數(shù)據(jù)采集更為容易，技術(shù)實現(xiàn)手段更為簡單。比如，劉仁義等[9]基于種子蔓延算法而提出的“無源淹沒”和“有源淹沒”算法;楊軍等[10]利用DEM數(shù)據(jù)進行的洪水淹沒分析和可視化表達。

基于DEM數(shù)據(jù)的特殊結(jié)構(gòu)和數(shù)據(jù)量較大的特點，許多學(xué)者在進行洪水淹沒分析時，大多采用了遞歸算法，比如種子點蔓延法或八鄰域蔓延法[11]、分塊種子蔓延法[12]以及條帶壓縮法等[13]。盡管這些算法具有許多眾所周知的優(yōu)點，但是由于算法運行時占用的計算機資源較多，而且當(dāng)遞歸深度達到一定時，計算效率就會大幅下降，不穩(wěn)定性就會越來越高，因此無法滿足大規(guī)模DEM數(shù)據(jù)處理的需要。為此，本文利用Hadoop云平臺能夠動態(tài)地擴展數(shù)據(jù)處理節(jié)點和支撐海量數(shù)據(jù)處理的特點[14-15]，提出了一種基于DEM數(shù)據(jù)和GIS技術(shù)進行大規(guī)模洪水淹沒分析的并行算法。

2 算法描述

本文構(gòu)建的Hadoop云平臺下的洪水淹沒分析并行算法，以解決大規(guī)模DEM數(shù)據(jù)在洪水淹沒分析中的應(yīng)用問題為目的。針對大范圍研究區(qū)，首先按規(guī)格格網(wǎng)的方法對其進行劃分，按從左到右、從上往下的順序?qū)ζ溥M行編號;當(dāng)研究區(qū)足夠大，可以環(huán)繞整個地球、首尾相連時，需要考慮同一行首尾兩個數(shù)據(jù)塊的連通性。由于數(shù)據(jù)量巨大，考慮到計算不便等問題，采用數(shù)據(jù)壓縮的方式對數(shù)據(jù)的每一行進行壓縮;在給定淹沒水位的情況下，計算每個柵格的淹沒水深，將同一行的淹沒柵格序列記為一個淹沒塊，該淹沒塊包含淹沒柵格序列所屬的淹沒塊編號、行號、起始列號、終止列號以及淹沒塊標記等。將相互連通的淹沒塊的淹沒標記設(shè)置成一樣，從而將研究區(qū)分割成不相連的幾個區(qū)域。對于有源淹沒分析，根據(jù)給定的淹沒點源，由其所在淹沒塊的淹沒標記提取出所屬的淹沒區(qū)域，并確定最終的淹沒范圍。其核心理論與關(guān)鍵步驟詳述如下。

2.1 DEM數(shù)據(jù)分塊

在進行大規(guī)模洪水淹沒分析時，用單一的DEM數(shù)據(jù)塊表示，其數(shù)據(jù)量巨大，無法在計算機中進行有效的處理。因此，為滿足大規(guī)模DEM數(shù)據(jù)在計算機中處理的需要，有必要對DEM數(shù)據(jù)進行劃分。本文采用規(guī)則格網(wǎng)的方式對研究區(qū)進行劃分。南北方向以赤道為界，記為dx，向北為正，向南為負，緯度每增加1°，dx加1;東西方向以本初子午線為界，記為dy，向東為正，向西為負，經(jīng)度每增加1°，dy加1。此時，當(dāng)研究區(qū)域在東經(jīng)180°附近，同時跨越東西半球時，需要對不同DEM分塊之間的連通性進行判斷。

第7期? ?劉小生，等：適用于Hadoop云平臺的洪水淹沒分析并行算法? ? 人 民 長 江2019年 2.2 淹沒塊

淹沒塊Cell作為區(qū)域感染法的最小單位，記錄的是同一行中相連淹沒柵格所在的行號、起始列號、終止列號以及淹沒標記，用（x， startY， endY，floodMark）表示。其中，淹沒標記floodMark需具有唯一性，除了記錄淹沒塊所在的行列號，還應(yīng)記錄該淹沒塊所在的DEM在研究區(qū)域中的行列號，用dx：dy：x：startY：endY表示。假設(shè)某區(qū)域存在潛在淹沒區(qū)如圖1所示，其中顏色較深的部分代表潛在的淹沒區(qū)，數(shù)字代表潛在的淹沒水深，整個DEM數(shù)據(jù)塊左上角坐標為（25，120）。

在給定的淹沒水位下，從DEM數(shù)據(jù)塊的第一行開始，依次判斷每一行中的柵格單元高程值是否小于指定淹沒水位。若該柵格單元的高程值不小于淹沒水位，則跳過當(dāng)前的柵格，繼續(xù)判斷下一個柵格單元的高程值，直到遇到一個柵格單元高程值小于淹沒水位時，新建一個淹沒塊，并標記該淹沒塊的行號x為當(dāng)前柵格所在的行號;該淹沒塊的起始列號startY為該柵格所在的列號，然后繼續(xù)判斷下一個柵格單元P的高程值;若P為該行最后一個柵格單元且其高程值小于淹沒水位時，記錄該淹沒塊的終止列號endY為P所在的列號;若P的高程值大于或等于淹沒水位，則標記該淹沒塊的終止列號為P所在列號減1。

2.3 淹沒塊連通域判讀

（1） 單個DEM數(shù)據(jù)塊中，若2個淹沒塊位于第i行和第i+1行中，而且存在其中一個淹沒塊的終止列號在另一個淹沒塊的起始列號和終止列號之間，則判定這2個淹沒塊連通，否則認為這2個淹沒塊彼此相互分離。

（2） 當(dāng)2個淹沒塊位于不同的2個DEM數(shù)據(jù)塊（dem1和dem2）時，若dem1與dem2左右相鄰，2個淹沒塊所處的行號相同，而且左淹沒塊的終止列號等于左DEM數(shù)據(jù)塊的寬度減1，右淹沒塊的起始列號等于0，則認為2個淹沒塊連通。

（3） 若dem1與dem2上下相鄰，且上淹沒塊的行號等于上DEM數(shù)據(jù)塊的高度減1，下淹沒塊的行號等于0，而且存在某個淹沒塊的終止列號在另一個淹沒塊的起始列號和終止列號之間，則判定這2個淹沒塊連通。

2.4 淹沒區(qū)分割

不同的淹沒區(qū)通過淹沒標記進行劃分，對具有相同淹沒標記的淹沒塊劃分為同一淹沒區(qū)。在同一塊DEM數(shù)據(jù)中，對第i行中的每一個淹沒塊，分別判斷其與第i+1行的每一個淹沒塊的連通情況，將相互連通的淹沒塊的淹沒標記改成相同的標記。如圖3所示，以第一個淹沒塊（1，6，7，25∶120∶1∶6∶7）為淹沒源，分別遍歷下一行的每一個淹沒塊，當(dāng)遇到與淹沒源相連通的淹沒塊（2，7，8，25∶120∶2∶7∶8）時，將DEM數(shù)據(jù)中所有具有淹沒源標記（25∶120∶1∶6∶7）的淹沒塊的標記改成與淹沒源相連通的淹沒塊的淹沒標記（25∶120∶2∶7∶8）。最終形成如圖4所示淹沒區(qū)。

當(dāng)存在多個DEM數(shù)據(jù)塊時，若2個DEM數(shù)據(jù)塊左右相鄰，分別提取左DEM每行的最后一個淹沒塊，右DEM每行的第一個淹沒塊，分別判斷所提取的左DEM數(shù)據(jù)塊中的淹沒塊是否與右DEM數(shù)據(jù)塊中淹沒塊是否相互連通。若連通，則將DEM數(shù)據(jù)中每個具有與淹沒源標記相同的淹沒塊改成與淹沒源相連通淹沒塊的標記;若兩個DEM數(shù)據(jù)塊上下相鄰，則分別提取上DEM最后一行的淹沒塊以及下DEM第一行的淹沒塊，若存在相連通的2個淹沒塊，則將具有淹沒源標記的淹沒塊的標記改成與淹沒源相連通淹沒塊的標記，其算法如圖5所示。

3 算法實現(xiàn)

傳統(tǒng)的洪水淹沒分析算法建立在單機環(huán)境中，受計算機性能的限制，無法滿足大規(guī)模DEM數(shù)據(jù)處理的需要。本文采用Hadoop云計算平臺的MapReduce框架[16-18]，采用分而治之的方法。將研究區(qū)域劃分成一序列規(guī)則的DEM數(shù)據(jù)塊，以每一塊DEM數(shù)據(jù)塊作為一個分片，設(shè)計相應(yīng)的map和reduce函數(shù)[19]，其處理流程如圖6所示。

在進行無源淹沒分析時，各數(shù)據(jù)塊彼此獨立，不需要考慮其關(guān)聯(lián)性，通過Map過程，可以很好地實現(xiàn)DEM數(shù)據(jù)的并行處理問題。在進行有源淹沒分析時，由于同一個淹沒區(qū)可能跨越多個DEM數(shù)據(jù)塊，在對研究區(qū)域進行分解處理后，需要考慮其關(guān)聯(lián)性，即實現(xiàn)Reduce過程。但由于每個DEM文件的數(shù)據(jù)量都比較大，當(dāng)傳輸?shù)酵粋€Reduce節(jié)點時，其處理效率類似于在單機中進行處理。為了減少數(shù)據(jù)遷移成本和計算量，本文在進行有源淹沒分析時，通過Map過程提取淹沒塊、并對淹沒塊進行壓縮的方式，減少了數(shù)據(jù)量，從而實現(xiàn)了更大量DEM數(shù)據(jù)的計算問題。考慮到MapReduce的處理流程，首先對淹沒塊和DEM數(shù)據(jù)類進行設(shè)計，然后實現(xiàn)MapReduce鍵值對的設(shè)計。

3.1 淹沒塊設(shè)計

作為洪水淹沒分析的最小單位，淹沒塊是實現(xiàn)DEM數(shù)據(jù)壓縮的關(guān)鍵。為了識別淹沒塊在研究區(qū)域中的具體位置以及對不同淹沒塊進行比較，對每個淹沒塊需要標記淹沒塊所在的行號、起始列號、終止列號和屬于不同淹沒區(qū)的淹沒標記等信息，而且需要繼承Comparable接口以實現(xiàn)淹沒塊大小的比較，其基本結(jié)構(gòu)如圖7所示。

3.2 DEM類設(shè)計

以geotiff格式存儲在HDFS中的DEM數(shù)據(jù)無法像訪問本地文件系統(tǒng)一樣進行訪問?；贖DFS流式數(shù)據(jù)訪問模式，本文將每個DEM數(shù)據(jù)塊以BytesWritable的方式讀取到內(nèi)存中，讀取DEM數(shù)據(jù)塊的基本信息，如坐標信息、投影信息與像素值等。其基本結(jié)構(gòu)如圖8所示。

3.3 MapReduce的鍵值對設(shè)計

MapReduce處理的是形式的數(shù)據(jù)，并不能直接對文件流進行處理，只有經(jīng)過序列化的類型才能夠充當(dāng)這個框架中的鍵或者值。只有繼承Hadoop的序列化接口Writable才可以作為值類型，而繼承自WritableComparable接口的類型既可以作為鍵類型，也可以作為值類型。由于淹沒塊在數(shù)據(jù)處理時只做內(nèi)部分析用，而且DEM數(shù)據(jù)的數(shù)據(jù)量太大，因此無論是淹沒塊還是DEM都無法直接作為鍵值對。在進行洪水淹沒分析時，以DEM數(shù)據(jù)塊的路徑作為Map的輸入key，以DEM數(shù)據(jù)塊的數(shù)據(jù)流作為Map的輸入value，將處理后的每個DEM數(shù)據(jù)塊的所有淹沒塊Table作為map過程的輸出value。其基本結(jié)構(gòu)如圖9所示。

圖9中，fileName代表DEM數(shù)據(jù)塊在HDFS中的文件名，dx、dy代表其所在的行列號，Row代表每行所有淹沒塊的集合。在Reduce過程中，進行淹沒區(qū)的合并，并根據(jù)淹沒源Point所在淹沒塊的淹沒標記來提取淹沒源所屬的淹沒區(qū)，舍去不包含淹沒區(qū)的Table，并將余下的Table傳遞到下一個Map過程中;由fileName讀取DEM數(shù)據(jù)，根據(jù)淹沒塊及淹沒水位修改其像素值，并輸出到指定的位置。

4 算法測試分析

為了驗證本文所提出的洪水淹沒分析并行算法的有效性，采用的實驗系統(tǒng)配置環(huán)境如下：Centos7操作系統(tǒng)由2個2.6GHz的IntelR Core TM i7-6700HQ的CPU、4G的運行內(nèi)存和100G的磁盤構(gòu)成，運行的Hadoop云計算平臺包含一個主節(jié)點hqf0和2個子節(jié)點hqf1和hqf2，其中的主節(jié)點hqf0開啟NameNode、JobHistoryServer和ResourceManager服務(wù);第一個子節(jié)點hqf1開啟SecondNameNode、DataNode和NodeManager服務(wù);第二個子節(jié)點開啟DataNode和NodeManager服務(wù)。由于集群節(jié)點在同一個機架上，而且數(shù)據(jù)節(jié)點只存在2個，因此，將文件塊的副本數(shù)設(shè)置為1。盡管DEM數(shù)據(jù)在HDFS中能夠進行分塊存儲，但DEM數(shù)據(jù)量巨大，受子節(jié)點計算性能的限制，大DEM數(shù)據(jù)塊在單個節(jié)點中的處理效率低下。因此，在Hadoop集群中對DEM數(shù)據(jù)進行處理時，有必要對DEM數(shù)據(jù)進行分割。本文采用地理空間數(shù)據(jù)云上按規(guī)則劃分的DEM數(shù)據(jù)，其分辨率為30 m，尺寸大小為360 1×360 1。

在開展洪水淹沒分析時，對每一個DEM數(shù)據(jù)塊啟動一個Map任務(wù)進行處理，將處理完的淹沒塊數(shù)據(jù)在同一個Reduce任務(wù)中進行匯總，根據(jù)淹沒點的淹沒標記提取相連的淹沒區(qū)，重置DEM數(shù)據(jù)的淹沒值，并由Map任務(wù)將屬于淹沒區(qū)的DEM數(shù)據(jù)寫入到指定的位置。其詳細的運行情況如表1所示。

由于每個DEM數(shù)據(jù)塊中淹沒塊的數(shù)量各不相同，在運行環(huán)境一致的情況下，其處理時間各不相同。淹沒塊多的DEM數(shù)據(jù)塊，壓縮率低，洪水淹沒范圍較大，淹沒區(qū)情況復(fù)雜，連通性較差，所需要的處理時間較多。受壓縮率的影響，當(dāng)淹沒塊數(shù)據(jù)量超過Reduce計算節(jié)點的計算能力時，需分批執(zhí)行DEM數(shù)據(jù)的處理。在Reduce節(jié)點計算性能允許的情況下，對大規(guī)模DEM數(shù)據(jù)的處理，適當(dāng)增加子節(jié)點，可以減少淹沒塊計算與淹沒區(qū)提取的總時間，但其數(shù)據(jù)匯總時間并不會減少;在子節(jié)點一定的情況下，若DEM數(shù)據(jù)量少于或等于子節(jié)點數(shù)，其Map過程所需要的時間與淹沒塊最多的DEM數(shù)據(jù)塊處理所需要的時間成正比，其Reduce過程隨著DEM數(shù)據(jù)量的增加而增加，而且受到DEM數(shù)據(jù)塊中淹沒塊數(shù)量的影響。

以江西省內(nèi)的青嵐湖、軍山湖、陳家湖和鄱陽湖為例，提取出8 m和10 m淹沒水位下的淹沒范圍，結(jié)合某個時期（2010年3月）的遙感影像，對其淹沒效果進行模擬并對其淹沒范圍的變化情況進行分析，如圖10～12所示。

由表1以及圖10～12的淹沒分析結(jié)果可知，本文研究過程中，對較大規(guī)模的流域或者研究區(qū)所采用的方法具有較好的模擬效果，并且該方法能夠較好地識別出湖中的孤島，如圖13所示。

5 結(jié) 論

本文針對DEM數(shù)據(jù)量大、單機環(huán)境計算力有限，以及現(xiàn)存洪水淹沒分析算法無法滿足分布式洪水淹沒分析的需要，提出了一種能夠適用于Hadoop云平臺的洪水淹沒分析并行算法。該算法具有以下優(yōu)勢：

（1） 能夠解決在Hadoop云平臺上利用大規(guī)模DEM數(shù)據(jù)進行洪水淹沒分析時所存在的問題。

（2） 在沒有指定淹沒點時，該算法能夠同時而且快速地提取出研究區(qū)中所有的淹沒區(qū);在給定淹沒點時，該算法能夠較快地提取出淹沒點所在的淹沒區(qū)。

（3） 在進行洪水淹沒分析時，該算法能夠快速地計算出每個淹沒柵格的淹沒水深并提取出洪水的最終淹沒范圍。

參考文獻：

[1] 唐震，李勇，茅昌平，等.基于ArcGIS Engine的洪水淹沒模擬系統(tǒng)構(gòu)建[J].人民長江，2016，47（S2）：1-3，51.

[2] 王嘉芃，劉婷，俞志強，等.基于COSMO-SkyMed和SPOT-5的城鎮(zhèn)洪水淹沒信息快速提取研究[J].遙感技術(shù)與應(yīng)用，2016，31（3）：564-571.

[3] 李瓊，廖蔚.基于開源Hadoop的洪水淹沒[J].江西測繪，2017（4）：61-64.

[4] 王船海，閆紅飛，馬騰飛.分布式架構(gòu)水文模型[J].河海大學(xué)學(xué)報：自然科學(xué)版，2009（5）：550-555.

[5] 芮孝芳.論流域水文模型[J].水利水電科技進展，2017，37（4）：1-7.

[6] 郭利華，龍毅.基于DEM的洪水淹沒分析[J].測繪通報，2002（11）：25-27，30.

[7] 張東華，劉榮，張詠新，等.一種基于DEM的洪水有源淹沒算法的設(shè)計與實現(xiàn)[J].東華理工大學(xué)學(xué)報（自然科學(xué)版），2009，32（2）：181-184.

[8] 湯國安，李發(fā)源，劉學(xué)軍.數(shù)字高程模型教程（第3版）[M].北京：科學(xué)出版社，2016.

[9] 劉仁義，劉南.基于GIS的復(fù)雜地形洪水淹沒區(qū)計算方法[J].地理學(xué)報，2001（1）：1-6.

[10] 楊軍，賈鵬，周廷剛，等.基于DEM的洪水淹沒模擬分析及虛擬現(xiàn)實表達[J].西南大學(xué)學(xué)報（自然科學(xué)版），2011（10）：143-148.

[11] 趙秀英，王耀強，李洪玉，等.基于DEM的有源淹沒算法設(shè)計與實現(xiàn)：以種子蔓延法為例[J].科技導(dǎo)報，2012（8）：61-64.

[12] 楊啟貴，王漢東.一種大區(qū)域洪水淹沒范圍快速提取的分塊種子蔓延算法[J].華中師范大學(xué)學(xué)報（自然科學(xué)版），2015，49（4）：603-607.

[13] 周佳.時間序列無失真壓縮算法的研究[D].西安：西安電子科技大學(xué)，2011.

[14] 陳吉榮，樂嘉錦.基于Hadoop生態(tài)系統(tǒng)的大數(shù)據(jù)解決方案綜述[J].計算機工程與科學(xué)，2013（10）：25-35.

[15] 李倩，施霞萍.基于Hadoop MapReduce圖像處理的數(shù)據(jù)類型設(shè)計[J].軟件導(dǎo)刊，2012，11（4）：182-183.

[16] 于金良，朱志祥，李聰穎.Hadoop MapReduce新舊架構(gòu)的對比研究綜述[J].計算機與數(shù)字工程，2017（1）：83-87.

[17] 劉義，陳犖，景寧，等.利用MapReduce進行批量遙感影像瓦片金字塔構(gòu)建[J].武漢大學(xué)學(xué)報（信息科學(xué)版），2013（3）：278-282.

[18] 黃山，王波濤，王國仁，等.MapReduce優(yōu)化技術(shù)綜述[J].計算機科學(xué)與探索，2013（10）：885-905.

[19] Miss J Vini，Rachel Nallathamby，Rene Robin C R.A Novel Approach for Replica Synchronization in Hadoop Distributed File Systems[J].Procedia Computer Science，2015（50）：590-595.

（編輯：趙秋云）