一种高效的船舶动态数据索引方法

2018-10-16张远强史国友

中国航海 2018年3期

张远强, 史国友

(1. 大连海事大学航海学院，辽宁大连 116026； 2. 宁波大学海运学院，浙江宁波 315211)

中国沿海和内河4级以上河段的船舶自动识别系统(Automatic Identification System, AIS)网络已实现覆盖[1]，这将极大地增加可接收到的AIS数据量。AIS数据具有数据量大、单船更新延迟和整体更新频繁等3个特性。AIS动态信息的更新时间根据船舶的速度和操纵情况为2～180 s，为保证AIS数据的更新和检索效率，同时防止数据检索时发生误检和漏检现象[2]，需建立高效的AIS数据索引机制。

船舶动态数据的检索，已有部分文献做过研究，如使用改进的3DR-Tree索引船舶位置的实时数据[3];使用四叉树算法对船位数据进行检索[4]，使用MongoDB对船舶实时数据进行检索[5]。这些方法都是假设船舶动态数据的更新近似于实时的，而忽略位置更新延迟所带来的误差。为此，本文采用基于移动数据索引方法构建船舶动态数据索引结构，以减小因时差带来的检索误差问题。

在空间数据检索方面，最常用的是文献[6]提出的R-tree方法。R-tree是一个高度平衡树，使用最小外包矩形组织空间物标。文献[7]的R*-tree是在R-tree基础上进行改进的，使用强制插入算法，避免因为节点溢出引起过多分裂。文献[8]的TPR-tree考虑了物标的速度对检索的影响，解决了运动物标位置随时间变化的检索问题。文献[9]的TRP*-tree在TPR-tree基础上对插入算法的代价模型进行了改进，提出更优化的最小外包矩形和查询区域扫测面积的求解方法，并使用优先插入队列寻找最优插入节点。本文在结合以上索引方法特点的基础上，建立适合于AIS数据的索引结构。

1 树结构

每艘船称为叶节点，包围叶节点的矩形称为非叶节点，非叶节点又被另外一个非叶节点包围，叶节点与非叶节点统称为节点。将这种带有运动和变化特性的外包矩形称为带时间参数的外包矩形(Time Parameterized Bounding Rectangle，TPBR)。每个节点都由其TPBR包围，除根节点外，规定了TPBR包围节点的上限数M和下限树m。一个树结构的平面示意见图1a)，其中共有O1～O12等12个叶节点，假设TPBR包围节点数的上限为3、下限为2，则可形成O13～O20等8个TPBR的非叶节点。

对应的结构示意见图1b)，与TPR*-tree不同的是，由于AIS数据更新较为频繁，为缩短在删除节点时的路径查找时间，增加一个Hash表，用于存储每艘船存放的节点路径信息，Hash表的键为船舶的MMSI号，值为船舶在树中的存放路径Pn(n∈N)。

2 构建索引树

2.1 坐标转换

船舶在AIS数据中的位置是以经纬度表示的，为适应TPR*-tree树的平面坐标系，可将经纬度坐标转换为墨卡托坐标。假设某船位的经纬度为(φ,λ)，其对应的平面坐标(x,y)为

(1)

式(1)中：r0为基准纬度圈半径；a为地球椭球长轴半径；q为等量纬度；e为椭球第一偏心率。

2.2 节点紧致

节点紧致算法是为在执行节点插入和删除操作时，重新调整节点的外包矩形，使其紧凑的包围子节点。节点Oi的坐标为(x(t)i-,x(t)i+,y(t)i-,y(t)i+,vxi-,vxi+,vyi-,vyi+)，x为横坐标轴，y为纵坐标轴，x(t)i-和x(t)i+分别为节点Oi在t时刻的下/上边界坐标，y(t)i-和y(t)i+分别为节点Oi在t时刻的下/上边界坐标；vxi-、vxi+、vyi-、vyi+分别表示节点Oi的速度在x轴和y轴上的下/上边界分量。向东为正，向西为负，向北为正，向南为负。

1) 对于非叶节点，TPBR在各象限的下边界位置和速度取所有包围物标的最小值，上边界位置和速度取所有包围物标的最大值。

2) 对于叶节点可将x轴和y轴的下/上边界值设置为相等。

可看出TPBR的位置和大小会随着时间的变化而变化，在起始时刻时TPBR是包围节点的最小外包矩形，但之后却不一定是，这是为保证TPBR在任何时候都能够包围所含节点。节点分别沿x轴和y轴的分速度为

(2)

式(2)中：VSOG为船舶航速；VCOG为航向。

假设物标上一次更新时间为t0，因为TPBR的形状不会收缩，只会增长，所以在TPBR中不能出现早于更新时刻的节点信息。因此，需要在有船舶动态数据更新时，实时地调整对应的TPBR及其所含节点的参数。TPBR包含节点在更新时刻的调整过程为

(3)

式(3)中：tupd为更新时间。TPBR的x(t)-取所有包围物标的x轴最小值，x(t)+取所有包围物标的x轴最大值，y(t)-取所有包围物标的y轴最小值，y(t)+取所有包围物标的y轴最大值，vx-、vx+、vy-、vy+分别取所有包围物标速度在x轴和y轴上的最小值和最大值分别为

(4)

(5)

2.3 插入流程

船舶动态数据库的节点插入流程见图2，具体过程为

1) 在时间t0收到一艘船舶Oi的位置更新数据，运用式(2)对速度进行分解，设置节点的坐标值，将重插标识符设置为false，执行步骤2)。

2) 调用路径选择算法(见2.4节)找出O最适合插入的TPBR路径，执行节点紧致算法，将插入路径更新到Hash表中，执行步骤3)。

3) 判断TPBR包围的节点数是否超过上限M，如超过则进入步骤4)，如未超过则结束插入。

4) 判断节点重插标识符，如果为true，跳到步骤6)执行节点分裂算法，否则执行步骤5)选择重插节点。

5) 抽取30%的影响检索效率最大的节点，将重插标识符设置为true，对余下的节点执行节点紧致算法，对抽取的节点逐个执行步骤2)。

6) 调用节点分裂算法将节点分裂为两个新节点，将分裂后的路径更新到Hash表中，执行节点紧致算法，返回其父节点指针，执行步骤3)。

2.4 路径选择

当新数据或更新数据要被插入到树中时(更新数据需先调用删除算法对旧数据进行删除)，系统需选择最佳插入路径。为提高检索命中率，最佳路径应是在物标插入后，使TPBR在未来一段检索时间qT的扫描面积增加值最小，称为最小增加代价衰减。为实现这一目的，路径选择算法维护一个优先插入队列QP，记录检验过的备选插入路径选项。QP按照增加的代价衰减由小到大的顺序进行排序，当所有候选路径都被检索后，选择代价衰减增加最小的路径。代价衰减增加值等于增加后的代价衰减减去增加前的代价衰减，具体有

ΔA=A(Onew,H)-A(Oold,H)

(6)

式(6)中：H为检索时间长度，可根据具体情况进行设置；Onew和Oold分别为插入之后的节点和插入之前的节点；A(Onew,H)和A(Oold,H)则表示插入后和插入前节点O在H时间段上的扫描面积；ΔA表示插入前后的扫描面积增加值。

路径选择算法示意见图3。图3中有6个移动的物标，分别为a、b、c、d、e、f为静止物标，其余物标速度都为单位时间走10个单元，围成3个TPBR，分别是i、g、h，虚线表示TPBR在t0时刻的状态，a(0)、b(0)、c(0)、d(0)、e(0)、f(0)为6个物标在t0时刻的位置。在t0时刻收到一艘新船数据p，假设qT=3，通过式(6)可得插入路径分别为g、h和i的代价衰减增加值排序队列QP=[(g,0), (h,0), (i,2 600)], 小括号中的数值为p被插入到相应节点中的代价衰减增加值。由于i的值比g、h的值大，所以无须展开。p的插入并没有对原有g和h的TPBR有所改变，其代价衰减增加值为0。由于g和h相等，所以需要判断其下一层节点的代价衰减增加值。如果将p插入g，对于路径(a,g)和(b,g)的代价衰减增加值分别为1 500和1 800，此时QP={[(h)，0]，[(a，g)，1 500]，[(b，g)，1 800]，[(i)，2 600]}，(a，g)和(b，g)表示完整的节点路径。如果将p插入h后，QP={[(a，g)，1 500]，[(d，h)，1 500]，[(c，h)，1 500]，[(b，g)，1 800]，[(i)，2 600]}。(a，g)，(d，h)，(c，h)具有相同的代价衰减增加值。在P中选择最小值作为插入路径：如果具有2个衰减增加值相等的插入路径，则选择扫描面积最小的作为插入路径；如果扫描面积相等，则随机选择。由图3可知，节点h的扫描面积比g小，因此选择h作为最佳插入路径。

2.5 节点删除

有2种情况会调用节点删除算法，一种是物标丢失，另一种是有更新数据到达时需删除旧的数据。系统通过保存的船舶插入路径Hash表定位到删除位置将节点删除。另外，在删除节点时只对插入路径上的TPBR使用节点紧致算法。其他与TPR*-tree的删除算法相同。

3 船舶动态数据检索

船舶动态数据检索是指查询当前或将来某一时刻或时间段内出现在查询位置一定距离范围内的船舶，查询位置可以是静态的，也可以是运动的。本文是在转换的闵可夫斯基和(Transformed Minkowski Sum，TMS)改进算法的基础上进行判断[10]。

3.1 船舶动态数据索引流程

船舶动态数据索引流程见图4，图4中实线箭头为数据流向，虚线箭头为发起查询请求。船舶动态数据通过AIS船站经过AIS岸站或卫星站传输给AIS解码服务器，AIS解码服务器将解码后的数据发送给数据管理服务器，数据管理服务器利用索引树构建方法建立索引树结构，并将船舶动态数据存入数据库，建立索引树后的效果见图5。监控客户端根据检索位置的查询时间和运动速度向数据管理服务器发起查询一定距离范围内的船舶请求，对监控船舶5 n mile范围内的他船进行查询(见图6)。数据管理服务器在收到查询请求后，找到满足查询条件的船舶，并使用MMSI号在数据库中找出船舶的详细信息返回给监控客户端。

3.2 距离查询

3.2.1坐标平移

用(xq,yq)表示本船位置Oq，(xr,yr)表示目标左下或右上角位置Or。假设Oq在t0时刻的坐标为(0, 0, 0, 0,-30,-30,-30,-30)，Or的坐标为(-4, -3, -3, -2, -10, 10, -10, 10)，使用式(4)将Or变换为相对于Oq的运动，此时的Oq坐标变为(0,0,0,0,0,0,0,0)，Or坐标变为(-4,-3,-3,-2,20,40,20,40)。

(i=x-,x+,y-,y+,vx-,vx+,vy-,vy+)

(7)

3.2.2闵可夫斯基和求取

根据闵可夫斯基和定理[11]，Or关于Oq的闵可夫斯基和等于Oq沿着Or的表面滚动一周，Oq中心的轨迹所包围的区域。这种方法实际上是通过Oq的半径将Or扩大，将Or关于Oq在t时刻的TMS表示为TMS(Or,Oq,t)。

TMS(Or,Oq,t)在H上可得到一个扫描阴影区(见图7)。如果扫描阴影区包含坐标原点，则Or与Oq在H相交。反之，不相交。

4 性能测试

本文算法的试验数据来源于天津海事数据中心，包括动态数据和历史轨迹数据，覆盖范围为(18°N, 104°E)到(43°N, 125°E)。动态数据时间段为2017年5月31日15：38：42—2017年5月31日15：44：42共6 min的数据，接收到的船舶总数为34 662艘。历史轨迹数据有10万条。

试验内容包括：H试验，M试验，检索精度试验，与R*-tree和TPR*-tree算法的比较试验。算法使用C++语言实现。为了保证检索算法能在大多数普通电脑上运行，所有的试验均运行在同一台普通台式机上，配置为Intel Core i5-3570 CPU 3.40 GHz and 4.00 GB RAM。

4.1 H试验

文献[8]给出H的最佳取值为H=UI/2+W，UI为物标的更新周期，W为预测检索时间长度。AIS数据的UI为15～120 s[12]。本文通过统计试验发现，在AIS基站信号较好的水域，96%的UI在22 s以内，因此，将UI定为22 s。

在对船舶进行检索时，既要保证AIS的W不宜过长，又要保证不会发生过多船舶丢失的现象。W在30～360 s的检索试验(见图8)。具体是每插入5 000艘船，对最后插入的100艘船舶执行距离为10 n mile的检索试验，直到将34 663艘船全部插入。由图可知，W对检索时间影响较小。本文在后续试验中将W设置为360 s，则H=371 s。

4.2 M试验

通过观察不同M的取值对插入时间的影响，m取为40%M(见图9)。取M为4～40中的8个值，统计插入时间。试验发现，当M>40时，插入时间明显增长，因此对于M>40的值没有在图上标出。试验使用10万条历史数据，每插入1万条数据记录一次时间间隔。可知，当M=10时的插入耗时最小，且随着M的增加插入耗时增长。

M为4～150时，检索距离为1 n mile的几个具有代表性的检索时间试验结果(见图10)。由图10可知，M=150最好，其次是M=10或15。检索距离r在2～10 n mile时，检索时间的变化曲线图(见图11)。由图11可知，随着检索距离增大，所需检索时间虽有所增加，但增幅较小。以上两试验的检索方法同W对检索时间的影响试验。

综合以上5个试验，当H<371 s，M=10时的插入和检索效率总体最优。

1) 分析H在短时间内对检索时间影响不大的原因，主要是船舶航速相对于其他交通工具要慢，因此，H在差异不大的情况下，不会增加过多检索到的节点。同时，由于船舶航向和航速相对稳定，可将预测时间相应增长，以增加对未来形式判断的效果。

2)M对插入和检索时间的影响较大，尤其是插入时间，分析原因主要是AIS更新数据量较大，船舶分布范围较广，较小的M可形成较小的TPBR，减少插入计算量和检索节点数，但太小时反而会增加插入和检索代价。

4.3 检索精度试验

本文使用MATLAB程序将所有船舶按当前航向航速推算到检索时间位置，再使用distance函数计算检索中心与其他所有船舶间的距离，与检索结果进行比较。试验方法是从2～10 n mile每隔2 n mile进行一次检索，船舶总数为34 663艘，随机选取100艘船的船位作为检索中心，检索结果发现与MATLAB计算结果基本一致，证明本算法是可靠的。

4.4 比较试验

将本文算法与R*-tree，TPR*-tree在插入时间、检索时间和检索精度等3个方面进行比较试验。

1) 插入时间比较是用相同的数据分别插入到3种算法中，比较插入时间。

2) 检索时间比较是比较在同等条件下进行相同次数检索所需的检索时间。

3) 检索精度比较是分别将3种算法的检索结果与MATLAB计算结果进行比较。

插入时间比较结果见图12。由图12可知本算法的插入时间与R*-tree相当，与TPR*-tree相比，有较大幅度的降低，主要原因是本算法使用一个Hash表存储船舶数据在TPR*-tree中的节点位置，提高了船舶数据的更新效率。本算法平均处理每条AIS数据约需3.2 ms。据统计，目前中国沿海每秒能接收到的AIS数据约为250条，因此，本算法可保证数据得到及时处理。

距离检索时间与R*-tree，TPR*-tree的窗口检索时间比较结果见图13，3种算法的检索速度相当。但R*-tree，TPR*-tree只有窗口检索，本算法既可进行窗口查询，也可进行距离查询。

对3种算法执行100次检索，将结果与MATLAB计算结果进行比较发现，本算法与TPR*-tree的检索结果一样，但R*-tree的误检率(误检次数除以检索次数)和漏检率(漏检次数除以检索次数)分别为20%和22%。从试验来看，如果要追求精确的检索结果，必须在建立的索引结构中考虑AIS数据的更新延迟时间和船舶速度。