动目标数据实时分析技术研究与实现

侯 博,聂 颖

(华北计算技术研究所地理与图形图像研发部,北京 100083)

0 引 言

动态目标数据不同于静态目标数据(矢量数据、栅格数据)，其随时间变化，并带有时间特性，可以归类为时变型数据。时变数据较静态数据而言具有连续性强、规模大、变量多等特点。针对动目标数据实时分析研究，应该把握时间特性、空间特性以及由时间和空间交叉所产生的运动特性。

在真实空间中，动目标数量大、种类丰富，本文主要针对典型的飞行目标[1]数据进行研究。区别于其他类型的目标(如海洋船只、陆地车辆)，其主要特点为：运动速度较快、运动范围广、运动限制少、体积较小。为了将飞行目标视为质点[2]进行路径预测，需要将地图中不可行区域进行膨胀操作[3]，膨胀半径R一般大于飞行目标长度的1/2。

针对轨迹预测问题，马国兵等人[4]采用BP神经网络算法和遗传算法相结合的一种混配策略，该方法以遗传算法为基础，将交叉、变异、选择操作中淘汰的基因再次与优良基因交配。此方法避免了轨迹预测计算中过早收敛的问题。Ying等人[5]提出了一种语义预测方法，该算法根据历史轨迹数据提前构建一个语义分析树，并通过对相似的目标进行聚类，计算轨迹点的置信度，从而预测下一个轨迹点。张尚剑等人[6]结合滑动窗口模型与多项式拟合提出了一种预测策略，该方法克服了误差随时间推移增大的问题，实现了运动目标实时预测跟踪。根据时间序列预测运动目标研究方面已经出现了许多策略[7-8]，但是仍然处于不断发展和完善的阶段。

针对飞行目标的实时分析，主要有以下要求：

1)实时预测速度要足够快，保证海量动目标数据能够及时处理。

2)实时预测准确率要尽可能高。

本文基于五点微分法与基于Storm的历史频次统计分析方法，模拟真实空间环境中飞行器的飞行状态，实时预测飞行器的下一位置点。此方法适用于飞行器、台风、船只等运动限制少、运动范围广的运动目标。

1 基于五点微分法的轨迹预测方法

本章重点介绍基于五点微分法的动目标轨迹预测方法。

1.1 五点微分法

五点微分法[9]是数值微分中的一种算法。下面首先给出一阶导数的五点数值微分公式[10]。

设f(x)为定义在区间[a,b]上的函数，给定f(x)在节点a≤x0

(1)

分别把t=0,1,2,3,4代入式(1)，即可得到节点xk(k=0,1,2,3,4)一阶导数[12]的五点数值微分公式：

16f(x3)-3f(x4) ]

(2)

6f(x3)+f(x4) ]

(3)

(4)

10f(x3)+3f(x4) ]

(5)

48f(x3)+25f(x4) ]

(6)

1.2 轨迹预测实现

利用五点微分公式，可以计算5个动目标点的经纬度速度，根据飞行的时间间隔计算下一时刻动目标的经纬度位置。通过上述信息可以得到合速度及合速度的方向。

程序中具体函数如下：

ListDiff5Point(List f , double t)

上述为计算五点微分的工具函数，其中，f为离散的5个函数值，t为2点之间的间距，返回值为五点的微分值。在实际预测中，f即为5个已知点的经度或者纬度位置，t即为动目标的刷新时间间隔，函数的返回值即为每点的经度或者纬度速度。利用下面的公式即可预测得到下一点的位置：

(7)

其中，(x1,y1)即为下一个预测点。

图1 位置速度预测图

在预测可视化展示系统中，真实的动目标经纬度坐标需要转化为屏幕坐标系予以展现。系统选用等距切圆柱投影，采用WGS84坐标系。具体实现效果在第3章展示。

2 基于Storm的历史频次统计分析方法

本章重点介绍基于Storm的历史频次统计分析的动目标轨迹预测方法。

2．1 Storm框架介绍

Apache Storm[13]是一个分布式流处理计算框架。它自创建了“Spouts”和“Bolts”来定义数据源与拓扑[14]操作，以便于满足对海量流数据进行分布式处理与批处理。

Storm程序由一个有向无环图(DAG)的“拓扑”形状构成，其中“Spouts”和“Bolts”充当有向无环图的节点。图上的边被称为数据流，与此同时，几层拓扑结构充当数据管道[15]进行数据转化计算。从表面上看，Storm的拓扑结构类似于MapReduce的Job，但是Storm与MapReduce的主要区别在于数据流[16]是实时处理的，而不是单个批处理的。此外，Storm拓扑[17]无限期地被运行，直到被用户主动杀死，而MapReduce的Job处理完一批数据就会自动结束。

在实际应用过程中，需要自行设计数据分组策略，即拓扑结构。Storm中有几种常用的分组策略：按字段分组(Field Grouping)、随机分组(Shuffle Grouping)、不分组(No Grouping)。Storm编程模型如图2所示。

图2 Storm编程模型

Topology：Storm中运行的实时应用程序的名称。

Spout：在一个Topology中获取源数据流的组件。

Bolt：接收数据流执行处理的组件。

Tuple：一次消息传递的基本单元。

Stream：表示数据流的流向。

2．2 历史频次统计方法拓扑结构设计

在本文框架中，Storm负责读取大批量动目标数据、进行数据预处理、统计网格内动目标出现的次数、计算出现频率、预测下一个航点位置，并对预测结果进行实时分析等操作。针对时序性动目标数据，图3展示了本文框架的拓扑示意图。

图3 本文框架拓扑示意图

图3由可以分布式并发执行的多个Spout和多组Bolt组成，其中多组Bolt又由不同功能的Bolt组成。首先，Spout发射的元组是由不同时段内航班的航班号、经纬度、高度、航向等数据所组成的键值对，采用按地域字段分组策略，这使得每组Bolt只接收特定数据进行处理。例如，某组Bolt只负责北京空域的航班数据处理，而“忽略”其他空域数据。采用按地域分组策略的好处在于，可以将海量且种类繁多的动目标数据较平均地分配到拓扑的多组Bolt上进行并发处理，在加快计算速度的同时，也在一定程度上保证多个计算单元的计算负载均衡。

2．3 分布式实时预测框架

为满足海量动目标实时预测的需求，本文设计一种基于Storm的分布式预测框架[18]，如图4所示。

图4 预测框架示意图

本框架由数据源发生器提供数据输入(数据源发生器为不间断发送连续动目标数据的工具)，数据的收集与处理分别由Storm中的Spout与Bolt组件负责。

由于动目标数据量大，数据连续发送时间长，需要保证Spout收集的数据较为平均，防止局部拥塞[19]的发生。每组Bolt选用按地域分片Spout收集的数据进行处理。

2．3．1 Spout处理机制

本文框架中主要调用Spout的nextTuple()方法与数据源接口进行通信，实现动目标数据的读取，并以先进先出的队列顺序发射给Bolt。其处理流程如图5所示。

图5 Spout处理流程图

图5中构建数据序列、序列缓冲机制，数据序列发送构成了nextTuple()方法。其中构建数据序列的方法如图6、图7所示。

图6 初始化动目标数据序列构建

图7 运行时动目标数据序列构建

2．3．2 Bolt处理机制

本文框架利用多组Bolt，把从Spout发出的元组数据进行预处理、统计预测、误差计算。其中主要调用Bolt的execute()方法按区域分组策略相应处理接收到的元组数据[20]。每组各Bolt的处理方法如下所示，其中Predict()方法的预测主要由历史数据在目标航点出现的频率大小决定。

预处理Bolt：

1)Receive_tuples()；//获取发来的元组数据

秦虹路现状东西向下穿宁芜铁路，涵洞车道规模（双向两车道）与限高（仅3m）均收到较大制约，极易造成拥堵。优化后，将铁路走廊改造为城市支路和绿道，同时对该节点竖向进行优化，消除净空不足的安全隐患，也与周边地块竖向实现良好衔接。同时对新平面交叉口进行渠化设计，合理分配机动车与慢行空间路权。

2)Preproccess_tuples()；//预处理数据以便统计分析

统计预测Bolt：

1)Statistic()；//统计网格内动目标出现的频次

2)Calculate_frequency()；//计算每个网格动目标出现的频率

3)Predict()；//预测下一时刻的数据

误差计算Bolt：

Calculate_error()；//将预测数据与当前时刻的真实数据比较并计算误差

3 实验与结果分析

本次实验所使用的数据来源于FlightAware网站上航班的飞行数据。笔者在爬取数据后，已经对航班数据做了一定的数据清洗，数据完整、有效，可以模拟真实动目标数据。

3．1 样本容量对预测结果的影响

使用Storm频次统计方法进行预测，需要前期的样本容量(即N值)越大越好。由于爬取的数据数量有限，本次分析将针对样本容量N(本次实验中N代表数据的天数)对实验预测结果进行对比分析[21]。

将爬取的400天北京飞往其他省会城市的飞行数据平均分为4组，分别计算其平均相对误差(Mean Relative Error， MRE)，见式(8)，结果如图9所示。

图8 动目标轨迹预测展示界面

(8)

图9 样本容量与预测误差的关系图

由图9可以看出，随着样本容量N值的不断增大，预测的准确率趋于平滑，当N大于50时，准确率大致趋于一定值。所以在使用基于历史频次统计的预测方法时，应该尽量保证样本容量的充足，最少不低于50，这样可以在预测实时性的基础上，尽量保证目标轨迹预测的准确性。

3．2 准确率分析

为验证2种方法的预测准确性，本节分别对2种方法的预测准确性进行分析。

3．2.1 五点微分法准确率分析

表1 五点微分法预测数据比较 单位：°

比较内容时间点01234567891011实际0.7560.8691.0451.3431.5211.7342.0342.4652.7543.0323.3453.675预测000001.9052.1562.5122.8452.9783.2983.701

选用所有被测点中的12个位置点。表1数据来自目标运动速度在1°/s～60°/s之间，按0.5 s采样得到的位置值。由于在这一段时间内目标运动是线性的，所以误差在-0.2°±0.02°之间。五点微分预测法在预测飞机线性飞行时预测准确率较高，但是如果飞机遭遇突发情况(如天气恶化、气流变化、塔台突发调度)，预测准确率会变低。

3．2.2 基于Storm历史频次预测方法准确率分析

图10 基于Storm历史频次预测方法误差统计图

将样本容量N选择为50天，随机选择100个时间点对预测结果进行相对误差计算，令相对误差为(预测值-真实值)/真实值。相对误差统计图如图10所示，设定误差阈值为±8%，其中超过阈值的点约占总点数的14%。使用基于Storm的历史频次预测方法对动目标位置进行预测，预测值基本分布在真实值两侧，结果基本符合预期效果。

3．3 实时性分析

由于爬取的真实航班数据读入量约等于2条/min，速度较慢，检验目标预测的实时性需要发送时间间隔在100 ms左右的数据较为合适。所以本次实验进行了数据的压缩处理，将30 s发送一条数据压缩到100 ms一条。本次实验尽量选择航行时间较长(大于5 h)的飞机进行测试。

图11为五点微分法与基于Storm的历史频次统计方法的延迟对比。

图11 预测延迟对比图

从图11可知，五点微分法由于是单线程运行的，当数据量大时，预测延迟急剧增高，但是在数据量较小时，预测延迟低于Storm法。Storm法的延迟在数据量增大时，保持一定的预测稳定性。

4 结束语

本文采用五点微分法和基于Storm的历史频次统计分析方法，实现了二维虚拟场景中动目标的实时轨迹分析[22]，效果较好。在后期研究中，将在Bolt的预测[23]环节结合神经网络算法，在按地域分段预测方面结合MPI编程，构建并行消息传递模型，实现更加准确的动目标实时轨迹数据分析。