基于多粒度建模的海量AIS數據三維可視化索引方法研究

杜 瑩，武玉國

(鄭州師范學院，河南 鄭州 450044)

為了適應當前航運事業蓬勃發展的新形勢，提高航運的安全性，改變以往的船舶通信方式，國際海事組織(IMO)、國際電工委員會(IEC)以及國際電信聯盟(ITU)等相關組織共同研究并推出了以信息和電子技術為核心的技術：船舶自動識別系統(Automatic Identification System，AIS)。該技術通過周期性地在固定的甚高頻頻率上廣播靜動態信息，實現船舶之間以及船舶和岸站間的信息交互，在船岸之間建立起一個固定的通信網絡，以實現自動識別船舶、提升船舶避碰能力[1-2]。

AIS數據由船舶行駛過程中周期性廣播自身位置產生，其廣播的每一幀AIS報文通常由及靜態信息(船名、呼號、船的大小、目的港等)和動態信息(如船的經緯度坐標、航速、航向等)構成。雖然單條AIS信息的數據量不大，通常在數十字節范圍內，但其更新頻率非常高(如表1所示，為AIS船位報告的頻率)。正常情況下，船舶每隔2～360 s就會廣播1次AIS信息，大量船舶不停廣播，導致海量AIS數據產生[5]。僅我國海事部門搜集近海船舶動態數據，單日數據量峰值就高達千萬條，3個月信息總量超過億條，其它船舶相關信息總量也在萬條以上[4]。這些海量AIS數據同時具有時空特性與大數據特征，即數據體量巨大、數據類型繁多、價值密度低、處理速度快。這就迫切需要一種有效的可視化方法來動態直觀表達大量船舶隨時間變換而發生的位置和狀態改變，以從中挖掘出船舶交通流中的潛信息。

表1 AIS船位報告的頻率

目前關于海量AIS數據可視化方法的研究，不少學者進行深入而有效地探討。文獻[1]和文獻[6]研究AIS與電子海圖ECDIS之間的串口通信，并在此基礎上實現AIS信息與ECDIS電子海圖的集成。文獻[3]對時空立方體模型進行改進，在傳統軌跡可視化模型的基礎上增加時間坐標軸并利用顏色通道對船舶航速進行編碼，使得分析者對異常數據識別，船舶停泊處識別及過彎行為模式更深刻的認識。文獻[7]針對目前船舶排污監測系統面臨的問題，對AIS系統提供的船舶信息的特點進行研究，根據船舶排污模型計算出各船舶實時排污情況，在電子海圖上顯示出港區船舶實時排污情況。文獻[8]為解決海量AIS航跡數據在ECDIS平臺上顯示效率低、實時性差等問題，設計一種基于Douglas-Peucker算法的AIS航跡數據壓縮算法。文獻[4]以船舶為對象建立時空立方體模型，采用改進的時空索引結構，在現有三維可視化組件的基礎上構建一個海上應急搜救信息查詢平臺，實現船舶屬性信息的查詢，以及船舶航行軌跡在球面三維環境中的顯示。

本文針對AIS數據數量多、位置及狀態更新頻繁等特點，利用基于“視點選擇法”的多粒度建模方法，構建面向移動對象的高效的空間索引，實現海量AIS數據的三維可視化。

1 面向AIS數據的多粒度建模

隨著AIS技術的飛速發展，實時接收到全球范圍內船舶的AIS數據已經完全成為可能，因此用戶有可能在不同情況下關注不同層面的AIS數據可視化效果，而多粒度建模恰好能契合這一需求。

多粒度建模的關鍵問題在于兩個方面：一是分析系統構成并選擇基本建模單元，即分析模型的粒度；二是針對不同粒度的建模單元實現多粒度模型的集成，即選擇多粒度建模方法[10-11]。

1.1 面向AIS數據的模型粒度分析

AIS是一種由岸基臺、船載臺、轉發臺、助航臺、機載臺組成的廣播式自動報告系統，它按照相關協議，把船舶名稱、呼號等靜態信息，以及航向、航速、位置等動態信息廣播至整個鄰近的海域，使得附近的其它船舶和岸站能夠獲取周圍海域所有船舶的信息，同時能夠自動接收附近移動臺站以及岸臺所發送的數據報文。這就意味著每一條AIS數據都可能被不同層面接收方進行解析和可視化。因此，需要根據可視化的目標和條件來選擇適宜的模型粒度。本文設計了粗、細兩種粒度的模型，它們在AIS數據可視化的運用中主要有如下兩種典型情況：

1)基于粗粒度模型的大范圍AIS數據可視化：一般而言，對大范圍甚至全球范圍內的AIS數據進行可視化的主要目的，是通過在宏觀層面上反映船舶密度和歷史軌跡，為航運管理部門實施有效管控和合理避讓提供科學的參考信息；

2)基于細粒度模型的局部AIS數據可視化及船舶信息查詢：若以局部范圍內或單個船舶的AIS數據為可視化和查詢對象，往往需要準確展現船舶在指定時刻的位置和狀態，這樣才能有效實施諸如應急搜救、緊急避讓等精細化操作。

那么，如何將這兩種粒度的模型有機地結合起來，并有效解決多粒度模型之間的一致性問題呢？這就是本文接下來要重點解決的問題：多粒度建模方法。

1.2 面向AIS數據的多粒度建模方法

目前國內外關于多粒度建模的方法，具有代表性的有聚合解聚法(Aggregation-Disaggregation)、視點選擇法(Selective Viewing，也稱為優化選擇法)和一體化層次化法(IHVR，Integrated Hierarchical Variable Resolution Modeling)等，三者的區別如表2所示[9]。

表2 三種多粒度建模方法的比較

由于各類AIS數據的典型特點是單條信息并不復雜，但更新頻率高，因此適合于復雜仿真系統的“聚合解聚法”并不適合本文所研究的AIS數據；此外，各類AIS數據的更新頻率并不相同，從2～360 s不等，因此在可視化過程中對模型一致性的要求也比較高。綜合以上分析結果，本文選擇視點選擇法來完成AIS數據的多粒度建模。但從表2可看出，雖然視點選擇法具有一致性好等優勢，但其最大的問題在于資源消耗高，因此本文的另一個重點就放在如何構建高效的空間索引方法，以提高海量AIS數據的顯示效率。此外，為更好解決多粒度模型之間的一致性問題，本文又在粗、細粒度模型內部分別細分為兩級，如圖1所示。

圖1 基于視點選擇法的AIS多粒度建模

2 面向AIS數據的空間索引

視點選擇法只有聚合沒有解聚，算法相對簡單，且多個粒度之間的一致性較好，最關鍵的是要解決資源消耗大的問題。本文采用空間索引網格法為AIS數據構建各個粒度的模型。

2.1 面向粗粒度模型的空間索引

在粗粒度層面上，用戶重點關注的是某個較大范圍內(包括全球范圍內)船舶的空間密度差異，因此本文以全球范圍為根節點構建空間索引，將全球劃分為若干等經差、等緯差的網格，作為子節點掛接在該根節點下。兩級密度的網格分別使用不同的經差和緯差。網格索引編碼的約束規則：從(-180°,-90°)處開始編號為0，行序優先。

若以dL和dB分別表示某級密度的網格的經差和緯差，以(L,B)表示船舶在某一時刻的地理坐標，則該船舶所在的網格索引的編碼方式為

row=|(B+90)/dB|,

col=|(L+180)/dL|,

code=row×|360/dL|+col.

其中，row和col分別表示網格在全球根節點中的行號和列號，code表示網格在全球根節點中的唯一編碼。這是一種基于整數的編碼方案，之所以不采用類似“row-col”這樣比較直觀的基于字符串的編碼方案，主要是基于對二者編碼與解碼效率的考慮。如表3和表4所示，為整數與字符串編碼與解碼速度進行比較的實驗結果。實驗環境為華碩ROG S5VT6700筆記本，Intel Core i7-6700HQ 2.6 GHz四核CPU，16G內存，Nvidia GeForce GTX 970M 顯卡，Windows7 64位操作系統。

表3 用32位整數和字符串對網格編碼的速度對比實驗結果

表4 用32位整數和字符串對網格解碼的速度對比實驗結果

從表3—表4中實驗結果可看出，整數編碼方案無論在編碼速度還是解碼速度上，都比字符串具有明顯的優勢。而AIS數據的典型特點就是每艘船舶的信息更新頻繁且船舶數目眾多，需要有高效率的編碼方案，這就是本文采用整數方式對網格進行編碼的主要原因。

此外，從上述編碼式可看出，網格的經差dL和緯差dB是兩個非常重要的參數，直接決定著網格的總數，那么該如何設置這兩個參數呢？基本原則如下：首先，網格總數不能太多，否則會影響網格在哈希表中的查找效率；其次，網格總數也不能太少，否則無法體現出船舶在空間密度上的差異，影響可視化效果。綜合考慮上述因素，本文經過反復實驗，將一級網格的經差和緯差均設置為1°，將二級網格的經差和緯差均設置為0.5°，這樣就可以在可視化的效率和效果之間找到一個較好的平衡。如圖2所示，為本文構建的兩級密度的網格，網格中的數字表示該網格中目前的船舶數量。實驗環境與上文相同，實驗數據為某時間段內的AIS壓縮信息，數據量大小170 M字節，船舶總數為67 833艘，記錄總數為3 413 867條，平均幀速為40幀/s，更新與繪制時間的平均占比為1∶3。

圖2 面向AIS數據的粗粒度模型可視化效果

2.2 面向細粒度模型的空間索引

在細粒度層面上，用戶重點關注的是單艘船舶的信息，包括靜態信息、動態信息、歷史軌跡等。為保持模型之間的一致性，本文對細粒度模型構建空間索引時，沿用了粗粒度模型的空間索引方案，即用一定經差和緯差的空間網格來對其范圍內的船舶進行管理，方案的設計遵循如下規則：

1)以全球范圍為根節點構建空間索引，將全球劃分為經差和緯差均為15′的網格，作為子節點掛接在該根節點下，網格中記錄位于所有位于其中的船舶在整個集合中的序號；

2)船舶在可視化時，又細分為兩級模型：視點較遠時采用一級模型，用不帶方向的點狀符號表示，只展現船舶的位置，不支持交互查詢；視點較近時采用二級模型，用帶方向的四邊形符號表示，同時展現船舶的位置和姿態，且支持交互查詢。

基于上述規則，本文設計了基于多線程的面向細粒度模型的空間索引算法，如圖3所示。

2.2.1 子線程：更新線程

子線程主要面向用戶開啟，由用戶根據船舶AIS數據的更新頻率，向系統發送船舶的實時位置和姿態，并記錄到待繪制隊列中。

需要說明的是，此處為什么要為每艘船舶額外生成一個序號并作為其在網格中的索引號，而不直接使用船舶的MMSI編號？這是因為船舶需要頻繁更新位置和姿態，如果用MMSI編號，就必須用數據結構中的關聯型容器(如map)存儲船舶信息，眾所周知，當關聯型容器中元素個數較多時，查詢的速度相當慢。而如果改用序號方法記錄船舶，則可使用數據結構中的序列型容器(如vector)，查詢時通過下標直接尋址，速度相當快。當然，這需要在內存中維護一個映射表，建立船舶MMSI號與其序號之間的映射關系。實驗結果表明，這種“以空間換時間”的做法，是完全可行的。

2.2.2 主線程：繪制線程

主線程由系統內部控制，主要負責兩項工作：一是計算視相關參數，二是從待繪制隊列中取出并繪制船舶。

1)計算視點相關參數。出于繪制效率和內存容量的考慮，系統中不可能同時繪制或存儲用戶提交的所有船舶，因此需要根據視點參數，動態加載視場范圍以內的船舶，同時卸載視場范圍以外的船舶。在本文設計的空間索引算法中，船舶是以索引號形式存儲在其父節點中的，即細粒度索引網格中，這就要求算法要以網格為單位完成船舶的動態加載與卸載。

需要注意的是，在卸載視場范圍以外的船舶時，需要以視場范圍為中心，對其進行適度外擴(如圖4所示)，以便保留一定數量的視場范圍以外的網格，否則會因為視點的微小變動而引起網格的頻繁加載與卸載，影響繪制效率與可視化效果。

2)從待繪制隊列中取出并繪制船舶。本文采用樹狀場景圖結構存儲并繪制各個節點，只有當節點的狀態發生改變時(如添加、刪除、修改)，才需要重新處理。因此，本文此處的待繪制隊列僅指那些因狀態發生該變而需要重新繪制的船舶。

待繪制隊列的數據來源，為用戶在子線程中提交的船舶信息，但這并不意味著這些船舶統統需要系統立即進行處理，因為某些船舶有可能距離視場范圍很遠，根本不需要進行可視化。這就需要利用空間索引算法對待繪制隊列進行篩選，也就是圖3中“計算視點相關參數”的主要工作內容。圖4為本文實驗環境和實驗數據實現的細粒度模型，平均幀速為30幀/s，更新與繪制時間的平均占比為3∶1(此處的更新時間包括了視相關參數的計算時間)。

圖4 卸載網格時需要對視場范圍適度外擴

3 結 論

AIS數據的典型特點是數量眾多、位置及狀態更新頻繁，如果沒有一套合理高效的建模及可視化方案，很難滿足多方面用戶對于三維可視化高效、直觀的要求。本文在詳細分析AIS數據的模型粒度的基礎上，設計并實現基于“視點選擇法”的多粒度建模方法，通過構建面向移動對象的動態空間索引，實現海量AIS數據的三維可視化，并通過實驗驗證算法的可行性。