利用DBSCAN 优化船舶领域算法的实时碰撞预警模型

2021-03-12肖丝雨任俊伟刘子恒李凯文陈智军

软件导刊 2021年2期

何渡，肖丝雨，任俊伟，刘子恒，沈昕，李凯文，陈智军

（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 所示。