基于折半查找的航班监视信息融合方法研究

杨 俊 汪万维 屈景怡 高 浩

1(中国民航大学天津市智能信号与图像处理重点实验室 天津 300300)2(中国民用航空华东地区空中交通管理局山东分局技术保障部 山东 济南 250107)

0 引 言

2014年3月8日，MH370航班失联以来，国际民航组织(International Civil Aviation Organization，ICAO)将全球航班追踪作为民航界优先任务。2015年6月，ICAO发布了全球航班追踪运行概念指导文件——全球航空遇险与安全系统[1]。2015年11月，ICAO修订了附件六《航空器运行》，强制要求航空承运人在2018年11月8日前实现对其海洋区域运行至少每15分钟通过自动报告对航空器位置进行追踪(4D/15追踪)。目前，中国民航约有97%的运输飞机已安装了航空器通信寻址报告系统(Aircraft Communications Addressing and Reporting System，ACARS)，因此，现阶段已经具备使用ACARS位置报数据对国际航班及运行于偏远地区的航班实施例行航空器追踪监控的硬件条件[2]。

在国内外，现行的航班监视信息融合方法主要是针对多源雷达数据的融合[3-6]、ADS-B与多点定位数据的融合[7]，以及雷达数据与ADS-B数据的融合[8-10]等，对于空管监视数据与ACARS位置报数据的融合研究比较少。文献[11]中提到了利用空管监视数据和ACARS位置报数据来做航班监控，但是并未对空管监视数据和ACARS位置报数据的融合处理进行详细的描述。空管监视数据的更新周期在4 s左右，ACARS位置报数据的更新周期在10 min左右，两者的更新周期相差较大；同时，空管监视数据主要覆盖了国内区域，而ACARS位置报数据在全球范围可覆盖，两者的覆盖范围不同。因此，采用传统的数据融合方法无法满足ACARS位置报数据和空管监视数据融合的需求。所以本文提出一种基于折半查找的航班监视信息的并行化融合方法，实现ACARS位置报数据和空管监视数据的互补融合和全空域范围内的航班监视信息的实时处理。

1 总体结构

图1为航班监视信息处理的总体结构，本文主要研究航班监视信息融合处理模块的数据融合方法及具体实现。空管系统主要通过一次雷达数据、二次雷达数据、ADS-B数据、多点定位数据等监视数据对管制空域范围内的航空器进行监视。图1中的空管监视信息融合处理模块用于对以上的监视数据进行融合处理，并将融合后得到的空管监视数据发送给航班监视信息融合处理模块，由航班监视信息融合处理模块实现空管监视数据和ACARS位置报数据的互补融合处理，输出融合数据。

图1 航班监视信息处理的总体结构

2 融合处理

针对空管监视数据和ACARS位置报数据的覆盖范围不一致、更新周期差别大等特性，本文提出一种航班监视信息互补融合方法。利用投影变换法实现空管监视数据和ACARS位置报数据的时间校准；提出基于时间的滑窗机制，实现多源航班监视信息的互补融合处理。

2.1 时间校准

由于空管监视数据和ACARS位置报数据的传输路线不同，以数据的接收时间作为数据融合的时间基准是不可靠的。同时，空管监视数据的原始数据生成时间是基于监视设备的时钟，ACARS位置报数据的原始数据生成时间是基于机载设备的时钟，在实际的应用中监视雷达的时间和机载设备的时间的准确性不是完全可靠的，所以以原始数据生成时间作为数据融合处理的时间基准也具有一定的不可靠性。

为了保障数据的有效融合，在数据融合处理前必须对两类数据的数据时间进行校准。本文以数据的实际接收时间为基础，以空管监视数据和ACARS位置报数据的位置信息为依据，通过统计分析的方法来计算空管监视数据和ACARS位置报数据的平均相对数据延时，并用平均相对数据延时来修正两类数据的接收时间，以修正后的接收时间作为数据融合的基准时间。如图2所示，A点和B点分别为某个航班在t1时刻和t3时刻接收到的空管监视数据的位置更新点，C点为该航班在t2时刻接收到的ACARS位置信息更新点，A点、B点和C点的位置坐标分别为(x1，y1，z1)、(x2，y2，z2)、(x3，y3，z3)。则A点与B点的距离如式(1)所示；该航班从A点飞到B点的平均速度可以表示为式(2)。C点到A点和B点的连线的投影点为C′，以A点的时间为基准，C′点对应的时间可以由式(3)计算得到。

图2 航空器位置信息示意图

(1)

(2)

(3)

那么，在C点的ACARS位置报数据与空管监视数据的相对延时为：

τ1=t2-(t1+Δt1)

(4)

平均相对延时可以表示为该航班的若干个ACARS位置数据点处的相对延时的平均值：

(5)

最后，通过平均相对时延对C点处的ACARS位置报数据进行修正，得到修正后的接收时间，如式(6)所示，从而实现了空管监视数据和ACARS位置报数据的时间校准。

(6)

2.2 滑窗机制

由于空管监视数据更新频率比ACARS位置报数据更新频率要高，本文采用以空管监视数据的更新周期T为计数单位的滑窗机制来对空管监视数据和ACARS位置报数据进行融合，图3为在时间轴上计数的滑窗机制示意图。

图3 在时间轴上计数的滑窗机制示意图

本文提出的滑窗机制采用滑窗计数的方法实现窗口在时间轴上的移动，窗口大小随着空管监视数据的更新状态的变化而不断变化。当某个航班的空管监视数据不更新时，每过一个空管监视数据的更新周期，滑窗的计数值加1，如果该航班的空管监视数据一直未更新，滑窗的计数值会不断增大，也就是滑窗大小会不断增大；当该航班的空管监视数据开始更新时，滑窗的计数值清零，如果该航班的空管监视数据一直在更新，滑窗会沿时间轴移动，同时滑窗的计数值始终为零，对应的滑窗大小始终为零。图3展示了某个航班从t0时刻到t0+(n+2)T时刻的滑窗变化情况，该航班的空管监视数据在t0时刻和t0+T时刻有数据更新，滑窗A在这两个时刻的计数值为零；该航班的空管监视数据在t0+T时刻和t0+nT时刻无数据更新，滑窗B在t0+nT时刻的计数值为n，由于该航班在t0+(n+1)T时刻有数据更新，则在t0+(n+1)T时刻滑窗的计数值清零，滑窗位置移动到t0+(n+1)T时刻；该航班的空管监视数据在t0+(n+1)T时刻和t0+(n+2)T时刻都有数据更新，滑窗C的计数值在这两个时刻都为零。

2.3 信息融合

在空管监视数据的覆盖区域，主要采用空管监视数据对航班进行监控，ACARS位置报数据主要用于提供相关数据的补充；在空管监视数据无法覆盖的沙漠、海洋和国外区域，采用ACARS位置报数据对航班进行监控，以实现全空域范围的航班实时监控。数据融合方法如式(7)所示，数据融合处理流程见图4。

图4 数据融合处理流程

P融合=kP空管+(1-k)PACARS

(7)

式中：P融合为融合后航班位置；P空管为空管监视数据的航班位置；PACARS为ACARS位置报的航班位置；k为融合系数。

系统为每个航班维护一个基于时间的滑窗(具体见2.2节)，当k=1时，融合后的位置信息采用空管监视数据中的位置信息，并在收到ACARS位置报数据后，提取ACARS位置报数据中除位置信息之外的油量、风速、风向等信息，并对这些数据项进行更新；当k=0时，融合后的位置信息采用ACARS位置报数据中的位置信息，提取空管监视数据中除位置信息之外的相关信息，并对这些数据项进行更新。

3 基于折半查找的融合方法

各空管局的空管自动化系统只关注与其管制空域相关的航班，系统接入和处理的空管监视数据的数据量不大；各航空公司只关注其自身运营的航班的动态，其监视系统接入和处理的ACARS位置报数据的数据量也不大；对于小范围内的少量航空器的监控，所接入和处理的空管监视数据和ACARS位置报数据的数据量也不大。因此，在以上三种情况下，航班的监视信息的融合处理可在单线程内完成。但是，要对全球范围的我国航空器以及国外飞境内的航空器进行实时监控，引接和处理的空管监视数据和ACARS位置报数据的数据量较大，采用单线程对空管监视数据和ACARS位置报数据进行融合处理无法满足系统对数据处理的实时性需求。因此，提出一种基于折半查找的单线程融合处理方法，在融合数据链表中对航班号进行折半查找，快速定位和获取对应航班的前一个更新时刻的航班监视信息的融合数据，并将其与当前时刻接收的航班监视信息进行融合处理，提高融合的处理速率。在此基础上，提出一种处理速率更快的基于折半查找的并行化融合处理方法，利用多线程机制实现航班监视信息的并行化融合。最后，通过实验验证这三种融合处理方法的处理速率，并对实验结果进行对比分析。

3.1 基于折半查找的单线程融合处理方法

图5为基于折半查找的单线程融合处理示意图。

图5 基于折半查找的单线程融合处理示意图

基于折半查找的单线程融合处理方法的航班监视信息的融合处理在单个融合处理线程内执行。融合处理线程主要由融合数据链表和融合处理模块组成。融合数据链表用于存放融合后的航班监视信息；融合后的航班监视信息按航班号由小到大的顺序存储在融合数据链表中。融合处理模块用于进行航班监视信息的融合处理，具体融合处理流程见图6。

图6 基于折半查找的单线程融合处理流程

当航班监视信息到达时，融合处理模块会提取航班监视信息中的航班号，并在融合数据链表中对该航班号进行折半查找，具体的折半查找流程见图7。

图7 折半查找流程

如果折半查找算法无法找到与指定航班号对应的融合数据时，该航班号被认为是新航班号，其对应的航班位置信息作为该航班监视信息融合数据直接插入到融合数据链表的最后查询位置处，实现对航班位置信息融合数据按航班号由小到大进行排序的目的，为折半查找提供数据基础；如果折半查找算法找到航班号对应的融合航迹时，从融合数据链表中提取航班号对应的航班监视信息融合数据，实现数据融合处理，并对融合数据链表中对应的融合数据进行更新。

基于折半查找的单线程融合处理方法在融合数据链表中对该航班号进行折半查找，可同时完成已有航班号的航班监视信息融合数据的快速获取和新航班号的航班监视信息的按序插入，与顺序查找方法相比可有效降低航班监视信息融合数据的查询时间，提高融合处理速率。该方法的优点是对于小范围内的少量航班监视信息的融合处理实现简单，处理速率较快，且易于编程实现。缺点是：所有航班监视信息的融合处理在单线程中按照到达时间的先后依次进行查询、获取和融合处理；在大批量航班监视信息到达时，单位时间内融合处理线程的数据的接收量会大于融合处理量，容易造成线程堵塞的现象，而导致航班数据无法实时更新。

3.2 基于折半查找的并行化融合处理方法

图8为基于折半查找的并行化融合处理示意图。基于折半查找的并行化融合处理方法结合了折半查找算法和并行化处理方法，以提高航班监视的融合处理速率。该方法主要由映射线程和并行化融合处理模块组成。

图8 基于折半查找的并行化融合处理示意图

映射线程由映射链表和映射处理模块组成。映射链表用于存放航班号和融合处理线程的映射关系数据，映射关系数据按航班号由小到大按序存储在映射链表中。当航班监视信息到达时，映射处理模块提取航班监视信息中的航班号，并在映射链表中对该航班号进行折半查找；无法找到对应的航班号时，该航班号被认为是新航班号，该航班号映射给当前处理的航班量最少的融合处理线程，并将航班监视信息发送给对应的融合处理线程，同时把映射关系数据插入到映射链表的最后查询位置处，实现映射关系数据按航班号由小到大进行排序的目的；找到对应的航班号时，从映射链表中提取航班号对应的映射关系数据，并将航班监视信息分发给该航班号对应的融合处理线程。具体处理流程见图9。

图9 航班号和融合处理线程的映射关系数据处理流程

并行化融合处理模块包含多个融合处理线程，每个融合处理线程主要由融合数据链表和融合处理模块组成。与基于折半查找的单线程融合处理方法类似，融合后的航班监视信息按航班号由小到大的顺序存储在融合数据链表中。融合处理模块接收映射线程分发的航班监视数据，并在融合数据链表中对该航班号进行折半查找。如果折半查找算法无法找到对应的航班号，则该航班号被认为是新航班号，其对应的航班监视信息作为该航班的航班监视信息融合数据直接插入到融合数据链表的最后查询位置处；如果折半查找算法找到对应的航班号，则从融合数据链表中提取航班号对应的航班监视信息融合数据，实现数据融合处理，并对数据链表中对应的融合数据进行更新。具体处理流程与图6一致。

基于折半查找的并行化融合处理方法与基于折半查找的单线程融合处理方法相比，数据融合处理的压力由多个并行执行的融合处理线程共同分担，有效提高了融合处理速率。同时，由一个独立的映射线程对航班号和融合处理线程的映射关系进行维护，通过折半查找的方法实现了航班号到融合处理线程的快速映射，并将新航班号映射给当前处理的航班量最少的融合处理线程，实现了各融合处理线程的负载均衡。并行化融合处理的缺点是并行化处理需要多核处理器的支持，在一定程度上提高了系统的硬件成本。

4 实 验

为证明基于折半查找的航班监视信息的并行化融合处理方法相对于其他两种方法的优势性，开展相关的实验研究和对比分析。

4.1 实验环境

实验在HP Z800高性能工作站中进行，实验中使用的HP Z800工作站的关键配置见表1。

表1 HP Z800工作站的关键配置

航班监视信息模拟软件用于仿真实验所需的航班监视信息。可以根据实验需要通过配置文件配置模拟的航班数、模拟的航班监视信息的更新周期等。

4.2 实验设置

航班监视信息模拟软件分别仿真出500、1 000、1 500、2 000、2 500、3 000、3 500、4 000、4 500、5 000、5 500和6 000个航班的航班监视信息。

在融合处理软件中分别实现单线程融合处理方法、基于折半查找的单线程融合处理方法和基于折半查找的并行化融合处理方法；融合处理软件接收航班监视信息模拟软件发送的航班监视信息，并对每批数据的处理时间进行记录，记录结果用于实验结果分析；基于折半查找的并行化融合处理方法，分别完成从2个并行化融合处理线程到10个并行化融合处理线程的实验。

4.3 实验结果

计算融合处理方法处理每批数据所需要的平均处理时间，并从以下两个方面对实验结果进行分析：1) 三种融合处理方法的处理结果的分析和对比；2) 基于折半查找的多线程融合处理方法在采用不同的融合处理线程数量时的处理结果分析与对比。

表2为三种融合处理方法的处理结果记录表。可以分析得出：1) 单线程融合处理方法处理每批数据耗费的时间最多，随着航班数的增加，每批数据的平均处理时间呈指数上升趋势；以处理6 000个航班为例，每批数据的平均处理时间需要279 462 ms。2) 基于折半查找的单线程融合处理方法，采用折半查找算法实现对航班融合数据快速查找，与单线程融合处理方法相比，融合处理速率得到显著提升。以处理6 000个航班为例，每批数据的平均处理时间降到了6 487 ms，相对于单线程融合处理方法，处理速度提高了42.08倍。3) 基于折半查找的并行化融合处理方法与基于折半查找的单线程融合处理方法相比进一步提升了融合处理速率。以处理6 000个航班为例，对于具有2个融合处理线程的并行化融合处理方法，每批数据的平均处理时间为1 891 ms，与基于折半查找的单线程融合处理方法相比，加速比达到3.43；对于具有4个融合处理线程的并行化融合处理方法，每批数据的平均处理时间为796 ms，与基于折半查找的单线程融合处理方法相比，加速比达到8.15。

表2 三种融合处理方法的处理时间结果记录表

图10为基于折半查找的并行化融合处理方法在采用不同融合处理线程个数时，对应处理结果的分析对比图，横坐标为融合处理线程数，纵坐标为每批数据的平均处理时间。6条曲线分别为基于折半查找的并行化融合处理方法在采用不同融合处理线程数对1 000、2 000、3 000、4 000、5 000和6 000个航班的监视信息进行融合处理时，每批数据的平均处理时间曲线。可以分析得出：1) 随着融合处理线程个数的增加，融合处理的速率在不断提升，随着融合处理线程数继续增加，融合处理的速率的提升不断放缓，当融合处理线程个数达到一定数量时，继续增加融合处理线程个数对处理速率的提升不再明显。这是由于并行化处理的融合处理线程数超过了处理器的并行化处理能力后，多出的线程数会在处理器中切换执行，因此并不能提高融合处理速率。2) 在航班数不多的情况下，每批数据的平均处理时间并不大。如果每批数据的平均处理时间达到了航班监控的基本要求，为节省工作站的计算资源，可适当减少融合处理线程数。

图10 采用不同融合处理线程数的处理结果分析与对比图

5 结 语

本文对基于折半查找的航班监视信息的融合方法进行研究，用于解决全空域范围内的海量航班监视信息的数据融合问题，对于航班位置的实时监视，防止航空事故来说具有重要的意义。该方法采用投影变换法对空管监视数据和ACARS位置报数据的接收时间进行校准。为每个航班维护一个基于时间的滑窗，采用基于折半查找的航班监视信息的并行化融合方法实现航班监视信息的互补融合。基于折半查找的航班监视信息的并行化融合方法，采用折半查找算法实现需要融合的航班数据的快速定位，采用自适应均衡的并行化处理机制实现航班监视信息的并行化处理，二者相结合可以显著提高海量航班监视信息的融合处理的速度。但是，单个节点的计算和存储能力始终有限，在未来的研究工作中，将利用多个节点实现海量航班监视信息的分布式并行处理，以进一步提高海量航班监视信息融合处理速率。