基于Spark的海量船舶密度分布計算系統設計與實現?

王 亮 陳春旭 蘇 云

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

1 引言

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

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

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

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

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

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

2 算法設計

2.1 Geohash編碼的使用

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

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

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

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

二是在誤差可接受的情況下，同一個Geohash網格內的數據記錄可以規約為一條數據，從而大幅降低數據的規模（即數據記錄規約）；

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

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

2.2 多層次時間編碼方案

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

表3 時間編碼規則及示例

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

時間編碼的算法如下：

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

2.3 船舶目標密度分布算法

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

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

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

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

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

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

inPeriod（r，period））

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

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

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

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

3 系統實現

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

圖2 系統總體架構

物理層：由服務器集群和客戶端組成，通過一臺千兆交換機相連。集群由3臺聯想服務器（Lenovo System x3650 M5）組成。每臺機器的配置：CPU為雙路14核，主頻2.6GHz；內存為256G；硬盤為1.2TB SAS盤，每臺7塊?？蛻舳藶榇鳡朠C機，內存為8G，硬盤為500GB固態盤。

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

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

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

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

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

4 測試結果與分析

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

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

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

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

5 結語

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

另外需要指出的是，雖然本文著重討論了船舶目標密度分布的計算過程，但是在此基礎上做適當的調整，很容易實現對船舶目標其他特征和規律的分析挖掘，例如航跡分布、異常發現和航道挖掘等。