利用DBSCAN 優化船舶領域算法的實時碰撞預警模型

何 渡，肖絲雨，任俊偉，劉子恒，沈 昕，李凱文，陳智軍

（1.湖北省科技信息研究院，湖北武漢 430063；2.湖北大學 計算機與信息工程學院，湖北武漢 430062）

0 引言

船舶碰撞預警是近年來智能航道領域的研究熱點之一［1］。航船行駛極易受天氣、水域、航速等復雜多變因素的影響，從而導致船舶碰撞預警的時效性和準確性不高［2］。如何提高船舶預警的時效性和準確性，一直是船舶領域研究中的難點問題［3］。本文利用DBSCAN 算法核心思想，結合船舶實時地理信息以及船首向，對船舶進行碰撞預警。

船舶安全領域（Ship Safety Domain，簡稱SSD）是指為避免碰撞，每艘船舶前后左右會保持一個不受他船侵犯的區域［4］。本文根據船舶AIS 數據，改進了船舶領域SSD 計算方法，并運用DBSCAN 空間聚類思想，結合船舶實時地理信息及船首向，預測短時間內的船舶軌跡，最后對可能出現危險的船舶進行預警提示［5］。

目前已有大量學者針對該問題展開研究，國外的船舶領域模型比較具有代表性的有藤井模型、Goodwin 模型、橢圓領域模型等［6］。藤井在考慮了通航密度、潮流和船速等因素后，得出的船舶領域模型是一個長軸8L 與短軸3.2L構成的橢圓（L 為船舶長度）［7］；Goodwin 對開闊水域的船舶領域模型進行研究，在考慮了船長、操作性能、海域類型等因素后，得出的船舶領域模型是以目標船為中心的3 個扇形區域組合而成的；Tak 等專家結合前兩種模型的優點，提出變更中心船位和船首向的橢圓領域模型［8］。國內對于船舶領域的研究起步較晚，大連海事大學考慮了航行安全等因素，針對狹水道或航道中的船舶領域，在考慮了對遇和交叉會遇兩種會遇局面后，將領域模型確定為一橢圓［9］；賈傳熒［10］則綜合考慮船舶操縱性能、航行環境和航速等因素對船舶的影響，提出一種擁擠水域內的船舶領域模型。

針對船舶避碰預警的研究也從未停止。2000 年左右，大連海事大學便將專家系統與船舶AIS 技術相結合，提出一種基于AIS 的航海避碰系統［11-12］。在模糊推理算法方面，Perera 等［14-16］將模糊最大優先算法應用于船舶自動避碰，取得了一系列研究成果。近年來，基于神經網絡的避碰系統也成為智能避碰系統的重要發展方向之一，西南交通大學對其作了一系列研究，包括使用高斯混合模型和連續貝葉斯網絡分別進行軌跡預測［17-18］；大連海事大學也提出基于混合遺傳算法的船舶避碰路徑規劃方法［19］。

綜合來看，針對船舶避碰預警研究的算法很多，但大部分算法均存在計算量較大，難以廣泛應用推廣的問題。另外大多數實驗是基于仿真模擬環境進行的，對船舶航行過程中的復雜性考慮不夠，缺乏在真實環境中的模擬實驗［20-21］。

本文首先簡要介紹現有船舶碰撞預警方法的優缺點，給出船舶領域的明確定義，然后在此基礎上，利用DBSCAN空間聚類思想改進傳統船舶領域計算方法，提出實時航情預警模型，最后基于大規模真實的長江流域船舶AIS 數據進行模型測試及對比實驗。

本文主要貢獻包括：

（1）模型充分考慮了船舶行駛過程的復雜性，結合AIS數據中的船長、船速、船首向、地理位置以及行駛時間等動靜態因素，改進傳統船舶領域計算及軌跡預測方法，從而較大程度上提高了船舶預警的準確性。

（2）運用DBSCAN 空間聚類思想，基于改進的船舶領域范圍，結合船舶實時地理信息和船首向，對中心船和目標船進行船舶領域的相對位置判斷。與傳統方法相比，減少了大量實時計算工作量，提高了智能船舶碰撞預警的時效性。

（3）采用大規模真實的長江航道船舶AIS 數據進行實驗建模，并對模型的可靠性和有效性進行客觀、真實的評價。

1 相關工作

1.1 船舶領域相關概念

AIS 是船舶自動識別系統（Automatic Identification Sys?tem）的簡稱，船舶AIS 系統能實時接收其它船和平臺發送的AIS 信息，并對相關信息進行解析、處理、存儲與顯示［5］。船舶AIS 數據能夠實現實時船舶地理位置定位、船舶動態信息展示以及船舶信息獲取等功能。船舶AIS 數據包括MMSI、船名、呼號、船舶類型等靜態信息［19］，以及經度、緯度、船首向等動態信息［17］。

對船舶領域的影響因素可劃分為人為因素、環境因素和船舶因素［6］。人為因素來自于船員航行經驗及目測，但該方法過于依賴于船員個人素質，存在很強的不確定性；在環境因素中，自然條件、水文條件、航道條件等都會影響船舶領域大小；船舶因素則受船舶尺寸大小、船舶可操縱性等影響。

1.2 常用船舶避碰方法介紹

（1）碰撞點時間估計（Time to Collision Point Estima?tion）。該模型給出了TTCP（Time to Collision Point）用于獲得碰撞點時間。此類判別方法對于體積較小、速度較快且穩定的船舶比較適用，但對于大型船舶的適用性較差。由于船舶的長度相對較長，無法忽略船長帶來的影響［22］。

（2）會遇距離判別（DCPA）。一旦發現有發生碰撞的可能性，馬上采取規避碰撞風險的措施，以達到碰撞預警效果。此類預警模式對船舶AIS 數據的時效性有較高要求，計算所需參數為：最近會遇時間（TCPA）、最近會遇距離（DCPA）、兩船船首向夾角、兩船之間距離。輸出內容是目標船舶的船首向和速度，此類方法也是根據對船舶相遇點的計算考慮是否存在碰撞風險［23］。

（3）船舶領域判別（SSD）。船舶領域是指在該范圍內，目標船舶不會與周圍船舶發生碰撞的安全區域，即當周圍船舶“侵犯”到目標船舶的船舶領域，則認為目標船舶存在碰撞風險，從而進行碰撞預警。船舶領域的判別指標受多種因素影響，SSD 的形狀和大小也隨著指標度量結果的變化而改變。通過SSD 進行預警，船舶之間的關系非常清晰，并且SSD 的形狀與大小在不同情況下可使用不同參數作為控制因素，但也因為SSD 的形狀與大小受多種因素控制，各個控制因素之間的比重很難確定，這也是SSD 所面臨的問題之一。

1.3 DBSCAN 算法

DBSCAN（Density-Based Spatial Clustering of Applica?tion with Noise）是一種經典的基于密度的聚類算法，其將“簇”定義為密度相連點的最大集合，能夠將具有足夠高密度的區域劃分為簇，并可在噪聲的空間數據庫中發現任意形狀的聚類。

DBSCAN 算法被廣泛應用于密度聚類、熱點挖掘等領域，主要應用于空間數據聚類。本文借鑒DBSCAN 算法中的聚類思想和遍歷思想，將其應用于改進的船舶領域實時航情避碰算法。

2 實時碰撞預警模型

2.1 算法整體設計

船舶碰撞預警利用船舶實時航情AIS 數據中的船長、船速、船首向以及地理位置經緯度作為輸入參數，結合船舶領域SSD 的思想模式，計算出形狀為橢圓的船舶領域SSD，并根據橢圓SSD 進一步計算出菱形SSD，接下來根據DBSCAN 空間聚類思想，通過各個船舶的實時AIS 數據進行船舶領域SSD 之間關系的判斷，完成中心船舶碰撞風險判斷，以達到船舶碰撞預警的目的。

實時航情碰撞預警模型算法流程如圖1 所示。

Fig.1 Real-time air traffic collision warning model圖1 實時航情碰撞預警模型算法流程

2.2 利用DBSCAN 優化船舶領域算法

2.2.1 實時航情定義

船舶發送AIS 數據的時間間隔根據船舶的船速、所處狀態與航行方向而有所不同，但將AIS 數據作為實時船舶運行記錄是目前較為合理的方式。在數據存儲時使用最新替換方法，保證當前時刻實時航情庫內所有船舶數據均為最新的AIS 數據，從而確保AIS 數據的時效性。采用該方法可以減少實時航情庫的數據總量，提高讀取速度，從而提高算法的實用性。

實時航情數據的意義有兩點：①可以將實時數據與歷史數據分開存放，方便分析實時數據是否存在問題，提高對實時數據的處理速率；②在對船舶進行碰撞預警時，加快對實時數據的獲取速度，從而縮短船舶碰撞預警算法運算時間，能更高效地計算出船舶碰撞預警結果，提高碰撞預警的時效性。

2.2.2 最大限值假想范圍

最大限值假想范圍即假定一個最大數值，使得所有對象的數值都小于該值，將該值作為數據獲取范圍的上限，以此剔除不需要的其它數據。算法輸入參數為一個包含中心船舶與周邊船舶AIS 數據的對象集合A（Aggregate），通過最大限值假想范圍獲取周邊船舶，可減少計算量，提高計算效率。

根據資料顯示，商用、民用船舶速度一般不會超過30nm/h，即54km/h（15m/s），船長一般不會超過300m。因此，本文在中心船舶的橢圓SSD 領域基礎上，再外接多個以最大速度54km/h 和最大船長300m 作為參數計算出來的橢圓領域（1 145.455），并與中心船舶領域相結合，即為選取對象集合A 的范圍（最大限值假想范圍）。接下來根據計算得到的SSD，以中心船舶為原點，找出對象集合A。最大限值假想范圍如圖2 所示。

Fig.2 The hypothetical range of maximum limit圖2 最大限值假想范圍

2.2.3 船舶領域計算

船舶在行駛過程中，船舶速度、船長、船首向（船舶移動的方向）是重要的影響因素。本文根據船舶運行速度V（單位m/s）與船舶長度L（單位m）計算船舶領域SSD。SSD 可根據不同情況定義不同形狀，因此本文將船舶領域SSD 定義為一個規則橢圓，橢圓長軸方向與船首向相同，橢圓長軸長度LAL（Long axis length）是短軸長度SAL（Short axis length）的兩倍。具體長軸長度LAL 計算公式如下：

2.2.4 利用DBSCAN 思想判斷船舶領域空間關系

（1）判斷中心船舶SSD 中包含的船舶。根據目標船舶領域面積與其它船舶位置，在集合A 中將直接包含于中心船舶領域內的船舶記為對象集合I（in），所需數據有：中心船舶SSD 長軸長LAL 與短軸長SAL、中心船舶經緯度位置（sx，sy）、周邊船舶經緯度（x，y）。

利用公式（2）計算Result，若Result=1，該船在SSD 的橢圓上；若Result≤1，該船在SSD 的橢圓內；若Result＞1，該船在SSD 的橢圓外。即當Result≤1 時，該船必定與中心船舶有碰撞風險。

（2）判斷中心船舶SSD 與剩余船舶SSD 的關系。經過步驟（1）的計算后，可得到在中心船舶SSD 之外的對象集合O（out）。根據DBSCAN 的思想依次循環遍歷，找出對象集合O 中船舶SSD 與中心船舶SSD 存在相交或相切的對象，并聚類在集合中。所需數據如下：中心船舶領域長軸長centricLal、中心船舶領域短軸長centricSal、中心船舶經緯度位置（sx，sy）、中心船舶船首向（角度α）、周邊船舶長軸長otherLal、周邊船舶短軸長otherSal、周邊船舶經緯度位置（x，y）、周邊船舶船首向（角度β）。

（3）以中心船舶經緯度為原點，得到中心船舶關于橢圓SSD 的橢圓方程：

（4）根據中心船舶與周邊船舶的位置關系，得出周邊船舶的橢圓SSD，接下來對該橢圓SSD 進行優化改進，在橢圓SSD 內計算出一個菱形SSD，并得出該菱形SSD 4 條邊的線性表達式：

γ=90-船首向差值（進行判定的船舶β-中心船舶α）

（5）以中心船舶位置為原點建立直角坐標系，得到周邊船舶的坐標（x，y）；通過長軸otherLal 與短軸otherSal 計算出長軸、短軸與橢圓相交的4 個頂點（A、B、C、D），如圖3所示。

（6）根據兩點成線的定理，可得到AC、AD、BC、BD 4 條線組成的菱形。對所得菱形SSD 4 條邊的直線方程分別與中心船舶橢圓SSD 的關系進行判斷，將菱形SSD 4 條邊所得的4 條直線方程分別與中心船舶的橢圓SSD 方程聯立，得到4 個一元二次方程。

Fig.3 Four points inside the ellipse圖3 橢圓內4 點

（7）通過判別式Δ=n^2-4mp 求解直線與橢圓是否有交點，若Δ＞1，即有兩個交點；Δ=1，即有一個交點；Δ＜1，即沒有交點。

若有交點，下一步判斷交點是否在船舶領域內。通過求根公式x=（-n±√Δ）/2m，判斷x 是否在x1與x2的范圍內。若在范圍內，則直線與橢圓SSD 相交，即中心橢圓與當前周圍船舶的橢圓相交；若不在范圍內，則繼續判斷菱形SSD 的下一條邊是否與橢圓相交。只要存在一條相交的直線，即判斷兩橢圓相交，若4 條直線均未與目標橢圓相交，則判斷兩橢圓不相交，把相交的船舶歸類于對象集合IT（intersects）中，如圖4 所示。

Fig.4 The interchange of the marine field and other marine fields圖4 船舶領域與其它船舶領域交匯

船舶實時航情碰撞預警的計算使用了船舶實時AIS數據中的船長、船速、船首向以及地理坐標位置經緯度，通過本文設計的模型判斷出在最大限值假想范圍內所有與中心船舶具有碰撞風險的船舶，并返回有碰撞風險的船舶信息。在此基礎上，對危險船舶的位置進行標記，實現船舶碰撞預警可視化，從而實現更加靈活的碰撞預警效果。

3 實驗設計與分析

3.1 實驗數據

本文實驗使用長江流域真實的AIS 數據，時間跨度范圍為2017 年5 月16 日0 點0 分-2017 年5 月16 日0 點49 分，時間長度為49′31″，所有數據記錄數為64 999 條。AIS 數據分為動態數據與靜態數據。

本文實驗使用的數據主要為船舶AIS 數據中的動態信息，由于數據并未隨著真實時間的改變而改變，所以從實驗數據中的最早時間（2017 年5 月16 日0 點0 分）開始，每隔3min 為一個時間間隔片段，存儲動態信息與靜態信息相結合的船舶實時航情數據。

3.2 數據預處理

船舶AIS 數據在初始階段（進行數據處理前），每一條信息都是一段有規律的字符串片段，字符串是由數據對應的編號、代號、縮寫組成的。因此，需要對原始數據進行數據轉換，轉變成本文所需的鍵值對形式。

對原始數據進行數據分析、數據轉換及數據清洗等操作，最后得出的實驗數據如圖5、圖6 所示。

Fig.5 Experimental data 1圖5 實驗數據1

Fig.6 Experimental data 2圖6 實驗數據2

3.3 實驗設計

本次實驗使用的AIS 數據包括船舶的唯一標識碼MMSI、船舶經度、船舶緯度、船長、船速與船首向。其中，船舶經緯度為WGS84 下地理坐標系的數值，船長單位為米（m），船速單位為nm/h，船首向單位為度（°）。選取的數據如表1 所示。

Table 1 Experimental data表1 實驗數據

實驗分為兩組進行，第一組實驗以1 號船舶為中心船舶進行船舶碰撞預警，通過本文算法得出可能與1 號船舶有碰撞風險的船舶；第二組實驗是利用第一組實驗結果，對實驗一中可能與1 號船舶存在碰撞風險的其它船舶進行反向碰撞預警檢測，以判斷船舶碰撞預警的準確性與相互性。

3.3.1 第一組：可行性實驗

在第一組實驗中，可以發現中心船舶的危險程度較高，與中心船舶可能發生碰撞的船舶數目較多。其中，2 號船舶在中心船舶（1 號）的船舶領域SSD 橢圓范圍內，3、4、6號船舶的SSD 與中心船舶有相交情況。本次實驗從數據獲取到計算得出實驗結果，共用時0.86s，其中模型計算花費時間0.39s，具體結果如表2、圖7 所示。

Table 2 The first set of experimental results表2 第一組實驗結果

Fig.7 Experimental results圖7 實驗結果

3.3.2 第二組：準確性實驗

第二組實驗共進行3 次，分別以2、4、6 號船舶為中心船舶，1 號船舶作為周圍船舶進行實驗。實驗結果表明，中心船與周圍船舶之間仍存在碰撞風險。

Table 3 The second set of experimental results表3 第二組實驗結果

Fig.8 Ship experiment results centered on ship 2圖8 以2 號船為中心船舶實驗結果

Fig.9 Ship experiment results centered on ship 4圖9 以4 號船為中心船舶實驗結果

Fig.10 Ship experiment results centered on ship 6圖10 以6 號船為中心船舶實驗結果

3.3.3 第三組：與碰撞點時間估計法的對比實驗

前文介紹了船舶碰撞預警的碰撞點時間估計法，本組實驗使用該方法進行對比實驗。實驗使用的數據為第一組實驗使用的數據，中心船舶的選取點也與第一組實驗相同。使用船舶碰撞預警的碰撞點時間估計法進行碰撞預警，實驗結果如表4 所示。

Table 4 Collision point time estimation experiment results表4 碰撞點時間估計實驗結果

實驗結果顯示，第一組實驗結果與采用碰撞點時間估計法的實驗結果差別在于6 號船舶的預警結果。通過對比可以發現，碰撞點時間估計法未對6 號船舶進行預警。碰撞點時間估計法將船舶看作質點，根據船舶速度與方向的關系實現對船舶的碰撞預警，一旦兩艘船舶方向相同或相反，并且不位于同一條直線內，碰撞點時間估計法則認為它們不存在碰撞風險。但在實際航行中，若航道發生改變，也可能發生碰撞事故，因此本文所作的碰撞預警比該預警方法效果更好、更全面。

3.4 結果分析

由實驗結果可知，本文模型預警準確性較高，但模型計算時間相比對比模型慢0.11s，且時間差別隨著數據量的增長而增長。碰撞點時間估計法將船舶視為質點，只需判斷點與線的關系，根據兩艘船舶速度與船首向的關系實現碰撞預警，因此模型計算速度稍快。但若航道發生改變，該算法則無法識別風險（如6 號船），且模型計算速度與本文模型相差極小。因此，在實際碰撞預警應用中，本算法優勢明顯。

實驗結果展示了基于船舶AIS 數據的船舶碰撞預警的準確性，只需在數據處理時確保AIS 數據的正確更新，即能保證船舶實時航情碰撞預警的準確性。

利用本文的碰撞預警模型，在某船舶時空大數據系統上實現了船舶碰撞預警功能，模型應用效果如圖11、12 所示。

Fig.11 Model application圖11 模型應用效果

Fig.12 The local magnification effect of model application圖12 模型應用局部放大效果

圖11 中的內容包括中心船舶以及與中心船舶可能發生碰撞風險的其它船舶，用不同顏色標注展示在系統上，綠色標記為中心船舶，紅色標記為可能與中心船舶發生碰撞的其它船舶。圖12 為該時空大數據系統的局部放大圖，能更清晰地看出模型應用效果。由此證明了本文模型的可用性與實用性。

4 總結與展望

本文借鑒DBSCAN 空間聚類方法，基于大規模船舶實時AIS 數據，考慮到船舶行駛速度、船舶形狀、船首方向等因素，提出基于DBSCAN 改進船舶領域算法的實時碰撞預警模型。該模型能對船舶行駛實時航情進行航情監測及碰撞風險預警，為保障水上交通安全提供了一種有效、可行的風險預警方法。

現階段有關船舶碰撞預警的方法較多，均有不同的優缺點。如何對其進行改進，使得船舶碰撞預警方法更加科學、實用，對智能航道的實現至關重要。本文模型后續應考慮更多可能影響船舶領域的因素，如船舶類型、水下地形等，以進一步提高船舶碰撞預警的精準度和實用性。