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

杜 瑩，武玉國

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

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

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

表1 AIS船位報告的頻率

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

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

1 面向AIS數(shù)據(jù)的多粒度建模

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

多粒度建模的關(guān)鍵問題在于兩個方面：一是分析系統(tǒng)構(gòu)成并選擇基本建模單元，即分析模型的粒度；二是針對不同粒度的建模單元實現(xiàn)多粒度模型的集成，即選擇多粒度建模方法[10-11]。

1.1 面向AIS數(shù)據(jù)的模型粒度分析

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

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

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

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

1.2 面向AIS數(shù)據(jù)的多粒度建模方法

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

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

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

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

2 面向AIS數(shù)據(jù)的空間索引

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

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

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

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

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

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

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

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

表3 用32位整數(shù)和字符串對網(wǎng)格編碼的速度對比實驗結(jié)果

表4 用32位整數(shù)和字符串對網(wǎng)格解碼的速度對比實驗結(jié)果

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

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

圖2 面向AIS數(shù)據(jù)的粗粒度模型可視化效果

2.2 面向細(xì)粒度模型的空間索引

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

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

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

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

2.2.1 子線程：更新線程

子線程主要面向用戶開啟，由用戶根據(jù)船舶AIS數(shù)據(jù)的更新頻率，向系統(tǒng)發(fā)送船舶的實時位置和姿態(tài)，并記錄到待繪制隊列中。

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

2.2.2 主線程：繪制線程

主線程由系統(tǒng)內(nèi)部控制，主要負(fù)責(zé)兩項工作：一是計算視相關(guān)參數(shù)，二是從待繪制隊列中取出并繪制船舶。

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

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

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

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

圖4 卸載網(wǎng)格時需要對視場范圍適度外擴(kuò)

3 結(jié) 論

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