基于Spark的海量船舶密度分布計算系統(tǒng)設計與實現(xiàn)?

王 亮 陳春旭 蘇 云

（1.海軍參謀部指揮保障大隊 北京 100841）（2.江蘇自動化研究所 連云港 222061）

1 引言

海上船舶目標的分布情況對海軍的航路規(guī)劃、海上試驗區(qū)選擇等任務具有重要意義。船舶密度是指某一瞬時單位面積水域內(nèi)的船舶數(shù)，它能夠反映水域中船舶的密集程度［1］。對于一段比較長的時間間隔，船舶密度可以通過對時間求平均得到。船舶目標的數(shù)據(jù)量非常龐大，通過傳統(tǒng)數(shù)據(jù)手段和工具，難以對其進行快速有效的處理和分析。例如，渤海灣在2016年的AIS（Automatic Identification System，船舶自動識別系統(tǒng)）動態(tài)數(shù)據(jù)，就多達26億條。船舶目標數(shù)據(jù)是一種典型的時空數(shù)據(jù)，如表1所示。

Spark是一種快速通用的集群計算系統(tǒng)［2］。它以RDD（Resilient Distributed Datasets，彈性分布式數(shù)據(jù)集）為核心模型，提供轉(zhuǎn)換和行動兩種操作，支持Java、Scala、Python和R等版本的高級API，以及支持通用執(zhí)行圖的優(yōu)化引擎。它還支持一組豐富的高級工具，包括用于SQL和結構化數(shù)據(jù)處理的Spark SQL，用于機器學習的MLlib，用于圖形處理的GraphX和用于流計算的Spark Streaming。

表1 船舶目標的部分屬性列表

Spark具有運行速度快、通用性和易用性強等特點［3］；與MapReduce不同，Spark可以將中間結果保存在內(nèi)存中，無需輸出到磁盤上［4］；Spark采用了事件驅(qū)動的方式啟動任務，能夠顯著減少線程啟動和切換的開銷［5］。

傳統(tǒng)計算船舶密度分布的方法，通常將船舶數(shù)據(jù)存儲到Oracle等關系數(shù)據(jù)庫，采用非分布式編程模式實現(xiàn)計算過程，在數(shù)據(jù)達到海量或計算長時間和大范圍的密度分布時面臨性能問題［6］。

本文在計算密度分布時，為了提高效率，對空間和時間分別進行了離散化并建立索引。對于空間，采用著名的Geohash編碼方案；對于時間，本文提出一種多層次時間編碼方案。在此基礎上，借助Spark的RDD模型將計算過程在時空兩個維度上并行化，有效提高了船舶目標密度分布的計算效率。

2 算法設計

2.1 Geohash編碼的使用

Geohash編碼方案在需要對空間數(shù)據(jù)進行索引的場景下得到了廣泛的應用［7～12］。它通過特定規(guī)則，將地理位置（通常用經(jīng)度、緯度表示）轉(zhuǎn)換為一個由字母和數(shù)字組成的字符串。這個過程實際上是有損的，如表2所示。但是在實際應用中，通過控制Geohash的級別，能夠?qū)⒄`差控制在可以接受的范圍內(nèi)。

表2 部分級別的Geohash編碼的誤差

本文中，在對數(shù)據(jù)預處理時選擇了6級Geohash，最大誤差為610m；在計算船舶目標分布時，根據(jù)所選計算區(qū)域的大小，可以選擇4～6級Geohash作為計算船舶數(shù)的網(wǎng)格。使用Geohash主要為了達到以下幾個目的：

一是將經(jīng)度和緯度兩個屬性合并為Geohash編碼這一個屬性，達到數(shù)據(jù)降維（即維規(guī)約）的目的；

二是在誤差可接受的情況下，同一個Geohash網(wǎng)格內(nèi)的數(shù)據(jù)記錄可以規(guī)約為一條數(shù)據(jù)，從而大幅降低數(shù)據(jù)的規(guī)模（即數(shù)據(jù)記錄規(guī)約）；

三是由于每個Geohash編碼實際上代表一個空間網(wǎng)格，可以用這個網(wǎng)格作為密度統(tǒng)計的基本單元；

四是Geohash是一種前綴編碼，即具備一個重要性質(zhì)：如果一個短編碼是另一個長編碼的前綴，那么后者代表的網(wǎng)格一定是前者代表的網(wǎng)格的子區(qū)域。這個性質(zhì)在船舶目標密度分布的計算過程中具有兩個方面的作用：首先，根據(jù)用戶指定的區(qū)域?qū)Υ澳繕藬?shù)據(jù)進行過濾時，只需要計算出該區(qū)域的Geohash編碼列表，然后與經(jīng)過編碼的AIS船舶目標動態(tài)數(shù)據(jù)進行連接，連接時只要兩個集合中的Geohash編碼滿足前綴條件即可；其次，在對經(jīng)過編碼的AIS船舶目標動態(tài)數(shù)據(jù)進行分組時，只需要取其Geohash編碼的前N位（N根據(jù)最終結果選取的Geohash確定），將結果相同的數(shù)據(jù)歸為一組即可。

2.2 多層次時間編碼方案

與經(jīng)緯度類似，船舶目標的時間屬性也是連續(xù)的，為了降低數(shù)據(jù)規(guī)模，選擇小時為最小時間單元，對原始數(shù)據(jù)進行記錄規(guī)約。同時為方便按照不同的時間尺度對數(shù)據(jù)進行統(tǒng)計，采取了月、周、天、時四種尺度對時間進行編碼，類似于Geohash的不同級別。時間編碼規(guī)則，如表3所示。

表3 時間編碼規(guī)則及示例

該時間編碼的優(yōu)點如下：1）編碼和解碼規(guī)則簡單，容易高效實現(xiàn)；2）時間編碼是連續(xù)的整數(shù)，可以直接進行加減，易于通過SQL或其他編程語言進行操作。例如，對2018年6月份的數(shù)據(jù)進行篩選時，可以簡單地表示為［581，582）。

時間編碼的算法如下：

其中，TS是時間戳，即從1970年01月01日00時00分00秒開始算起的毫秒數(shù)；HOUR_MIL是一小時的毫秒數(shù)；HOUR_DIFF是當前時區(qū)與零時區(qū)的小時差，例如東八區(qū)為-8；中括號表示向下取整；HourId、DayId、WeekId和MonthId分別是時、天、周和月四種級別的時間編碼。

2.3 船舶目標密度分布算法

船舶目標密度分布算法的關鍵在于將計算過程利用Spark模型進行并行化。具體的算法流程如圖1所示。

第一步，將原始AIS船舶目標動態(tài)數(shù)據(jù)，進行空間離散化和時間離散化。這一步實際是數(shù)據(jù)的預處理工作，是一個一次性過程。空間離散化采用Geohash編碼算法，級別選擇6級；時間離散化采用多層次時間編碼方案，級別選擇小時。處理結束后形成中間結果表，原始數(shù)據(jù)中的LON和LAT合并為ZONEID，TIME轉(zhuǎn)化為TIMEID。由于進行了數(shù)據(jù)規(guī)約，中間結果表與原始數(shù)據(jù)相比，記錄數(shù)大大減少。后續(xù)過程從這個中間結果表開始。此過程在Spark中是一個Map操作，用偽代碼表示為

rdd.map（r-＞geohash（r，6））

rdd.map（r-＞toHourId（r））

第二步，根據(jù)用戶指定的時間段period（例如從某天開始連續(xù)的10天）和空間范圍zone（例如整個渤海灣或某個較小海域），對艦船目標進行篩選。目的是根據(jù)用戶的具體需求降低計算量，從而減少計算時間。此過程在Spark中是一個Filter操作，用偽代碼表示為

rdd.filter（r-＞inZone（r，zone）&&

inPeriod（r，period））

第三步，將同一個時間單元（例如同一天）和同一個空間網(wǎng)格（例如Geohash 5級）內(nèi)的數(shù)據(jù)分為一組、去重、計數(shù)。此過程在Spark中是一個GroupBy操作，同時進行了Distinct和Count操作，用偽代碼表示為：

rdd.groupBy（r-＞（substr（r.zoneId，5），toTime（r，DAY）））.distinct（r-＞r.mmsi）.count（）

圖1 船舶目標密度分布算法流程

最終得到的結果是一個二維數(shù)組的序列，表示在某個時間段內(nèi)（例如一天或一小時）、在某個空間網(wǎng)格內(nèi)的船舶目標數(shù)。計算結果可以利用適當?shù)腢I組件進行可視化，以更加直觀地向用戶呈現(xiàn)船舶的分布情況，例如網(wǎng)格圖或熱力圖等。

3 系統(tǒng)實現(xiàn)

系統(tǒng)總體架構分為三層：物理層、服務層和應用層，如圖2所示。

圖2 系統(tǒng)總體架構

物理層：由服務器集群和客戶端組成，通過一臺千兆交換機相連。集群由3臺聯(lián)想服務器（Lenovo System x3650 M5）組成。每臺機器的配置：CPU為雙路14核，主頻2.6GHz；內(nèi)存為256G；硬盤為1.2TB SAS盤，每臺7塊。客戶端為戴爾PC機，內(nèi)存為8G，硬盤為500GB固態(tài)盤。

服務層：主要提供數(shù)據(jù)存儲服務、數(shù)據(jù)計算服務和圖形用戶界面。其中的服務組件主要包括Hadoop Yarn 2.7.1、HBase 1.1.6、Phoenix 4.7.0 和Spark 1.6.2等。

數(shù)據(jù)存儲服務由Phoenix提供，它是一個構建于HBase之上的開源數(shù)據(jù)庫，既繼承了HBase分布式和列式存儲等優(yōu)點，又提供了對標準SQL的支持，利用它可以簡化對海量數(shù)據(jù)的操作。同時，Phoenix提供了一個符合Spark Data Sources API標準的數(shù)據(jù)接口，使Spark能夠高效地從Phoenix中分布式地讀寫數(shù)據(jù)。

數(shù)據(jù)計算服務由Spark提供，它是整個系統(tǒng)的核心，用以實現(xiàn)船舶目標密度分布的算法。它支持三種部署模式：獨立調(diào)度器模式、使用Yarn部署以及使用Mesos部署。本文采用了Yarn Cluster模式部署，可以最大程度地利用服務器集群的資源，以提升計算性能。

圖像用戶界面為用戶提供可視化的操作界面，便于用戶提交計算任務、接收和顯示計算結果。其中使用了ChartDirector組件繪制密度分布的熱力圖。

應用層：在服務層的基礎上，原始數(shù)據(jù)、中間數(shù)據(jù)和結果數(shù)據(jù)存放于Phoenix數(shù)據(jù)表中。Spark中運行的代碼，負責從Phoenix讀取艦船目標原始數(shù)據(jù)、進行空間和時間離散化處理以及完成密度分布計算，最終將計算結果存儲到Phoenix中。客戶端代碼負責從Phoenix中獲取結果，然后通過可視化組件將結果呈現(xiàn)給用戶。

4 測試結果與分析

以渤海灣區(qū)域2016年的AIS船舶目標為原始數(shù)據(jù)，在上述的服務器集群上進行了實測。典型地，以2016年8月份為例，得到的密度分布熱力圖如圖3所示。直觀地看，圖中的船舶情況是與實際相符的。從圖中可以明顯地觀察到港口（例如大連港、天津港、東營港等）和航道（例如從營口港經(jīng)大連附近出海的航道）。

圖3 渤海灣2016年8月AIS密度分布熱力圖

另外，為了驗證本文中方案的高效性，同時采取了另外兩種方式計算船舶目標密度分布，并將結果進行了對比，如表4所示。其中，方式一即本文采取的方式；方式二與方式一相比，既沒有使用Geohash進行空間編碼，也沒有使用時間編碼；方式三與方式一相比，沒有使用Spark集群，而是使用了傳統(tǒng)的單節(jié)點計算方式。從三種方式的耗時可以明顯看出，本文采用基于時空編碼對數(shù)據(jù)進行離散化以及采用Spark分布式計算的方式，大大提升了密度分布計算的效率。

表4 不同方式下密度分布計算耗時對比

5 結語

對水面船舶目標的密度、流量和航道等特征進行分析計算時，在傳統(tǒng)的單機模式下，當數(shù)據(jù)量極大時，計算時間會大大延長。本文采用基于HBase的分布式存儲Phoenix和Spark分布式計算引擎，輔以Geohash編碼和多層次時間編碼技術，實現(xiàn)了船舶目標密度計算的并行化。經(jīng)實測，計算效率顯著提升。

另外需要指出的是，雖然本文著重討論了船舶目標密度分布的計算過程，但是在此基礎上做適當?shù)恼{(diào)整，很容易實現(xiàn)對船舶目標其他特征和規(guī)律的分析挖掘，例如航跡分布、異常發(fā)現(xiàn)和航道挖掘等。