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

楊 俊 汪萬維 屈景怡 高 浩

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位置報數據的接收時間進行校準。為每個航班維護一個基于時間的滑窗，采用基于折半查找的航班監視信息的并行化融合方法實現航班監視信息的互補融合。基于折半查找的航班監視信息的并行化融合方法，采用折半查找算法實現需要融合的航班數據的快速定位，采用自適應均衡的并行化處理機制實現航班監視信息的并行化處理，二者相結合可以顯著提高海量航班監視信息的融合處理的速度。但是，單個節點的計算和存儲能力始終有限，在未來的研究工作中，將利用多個節點實現海量航班監視信息的分布式并行處理，以進一步提高海量航班監視信息融合處理速率。