侯 博,聶 穎

(華北計算技術(shù)研究所地理與圖形圖像研發(fā)部,北京 100083)

0 引 言

動態(tài)目標數(shù)據(jù)不同于靜態(tài)目標數(shù)據(jù)(矢量數(shù)據(jù)、柵格數(shù)據(jù))，其隨時間變化，并帶有時間特性，可以歸類為時變型數(shù)據(jù)。時變數(shù)據(jù)較靜態(tài)數(shù)據(jù)而言具有連續(xù)性強、規(guī)模大、變量多等特點。針對動目標數(shù)據(jù)實時分析研究，應(yīng)該把握時間特性、空間特性以及由時間和空間交叉所產(chǎn)生的運動特性。

在真實空間中，動目標數(shù)量大、種類豐富，本文主要針對典型的飛行目標[1]數(shù)據(jù)進行研究。區(qū)別于其他類型的目標(如海洋船只、陸地車輛)，其主要特點為：運動速度較快、運動范圍廣、運動限制少、體積較小。為了將飛行目標視為質(zhì)點[2]進行路徑預(yù)測，需要將地圖中不可行區(qū)域進行膨脹操作[3]，膨脹半徑R一般大于飛行目標長度的1/2。

針對軌跡預(yù)測問題，馬國兵等人[4]采用BP神經(jīng)網(wǎng)絡(luò)算法和遺傳算法相結(jié)合的一種混配策略，該方法以遺傳算法為基礎(chǔ)，將交叉、變異、選擇操作中淘汰的基因再次與優(yōu)良基因交配。此方法避免了軌跡預(yù)測計算中過早收斂的問題。Ying等人[5]提出了一種語義預(yù)測方法，該算法根據(jù)歷史軌跡數(shù)據(jù)提前構(gòu)建一個語義分析樹，并通過對相似的目標進行聚類，計算軌跡點的置信度，從而預(yù)測下一個軌跡點。張尚劍等人[6]結(jié)合滑動窗口模型與多項式擬合提出了一種預(yù)測策略，該方法克服了誤差隨時間推移增大的問題，實現(xiàn)了運動目標實時預(yù)測跟蹤。根據(jù)時間序列預(yù)測運動目標研究方面已經(jīng)出現(xiàn)了許多策略[7-8]，但是仍然處于不斷發(fā)展和完善的階段。

針對飛行目標的實時分析，主要有以下要求：

1)實時預(yù)測速度要足夠快，保證海量動目標數(shù)據(jù)能夠及時處理。

2)實時預(yù)測準確率要盡可能高。

本文基于五點微分法與基于Storm的歷史頻次統(tǒng)計分析方法，模擬真實空間環(huán)境中飛行器的飛行狀態(tài)，實時預(yù)測飛行器的下一位置點。此方法適用于飛行器、臺風、船只等運動限制少、運動范圍廣的運動目標。

1 基于五點微分法的軌跡預(yù)測方法

本章重點介紹基于五點微分法的動目標軌跡預(yù)測方法。

1.1 五點微分法

五點微分法[9]是數(shù)值微分中的一種算法。下面首先給出一階導(dǎo)數(shù)的五點數(shù)值微分公式[10]。

設(shè)f(x)為定義在區(qū)間[a,b]上的函數(shù)，給定f(x)在節(jié)點a≤x0

(1)

分別把t=0,1,2,3,4代入式(1)，即可得到節(jié)點xk(k=0,1,2,3,4)一階導(dǎo)數(shù)[12]的五點數(shù)值微分公式：

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

(2)

6f(x3)+f(x4) ]

(3)

(4)

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

(5)

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

(6)

1.2 軌跡預(yù)測實現(xiàn)

利用五點微分公式，可以計算5個動目標點的經(jīng)緯度速度，根據(jù)飛行的時間間隔計算下一時刻動目標的經(jīng)緯度位置。通過上述信息可以得到合速度及合速度的方向。

程序中具體函數(shù)如下：

ListDiff5Point(List f , double t)

上述為計算五點微分的工具函數(shù)，其中，f為離散的5個函數(shù)值，t為2點之間的間距，返回值為五點的微分值。在實際預(yù)測中，f即為5個已知點的經(jīng)度或者緯度位置，t即為動目標的刷新時間間隔，函數(shù)的返回值即為每點的經(jīng)度或者緯度速度。利用下面的公式即可預(yù)測得到下一點的位置：

(7)

其中，(x1,y1)即為下一個預(yù)測點。

圖1 位置速度預(yù)測圖

在預(yù)測可視化展示系統(tǒng)中，真實的動目標經(jīng)緯度坐標需要轉(zhuǎn)化為屏幕坐標系予以展現(xiàn)。系統(tǒng)選用等距切圓柱投影，采用WGS84坐標系。具體實現(xiàn)效果在第3章展示。

2 基于Storm的歷史頻次統(tǒng)計分析方法

本章重點介紹基于Storm的歷史頻次統(tǒng)計分析的動目標軌跡預(yù)測方法。

2．1 Storm框架介紹

Apache Storm[13]是一個分布式流處理計算框架。它自創(chuàng)建了“Spouts”和“Bolts”來定義數(shù)據(jù)源與拓撲[14]操作，以便于滿足對海量流數(shù)據(jù)進行分布式處理與批處理。

Storm程序由一個有向無環(huán)圖(DAG)的“拓撲”形狀構(gòu)成，其中“Spouts”和“Bolts”充當有向無環(huán)圖的節(jié)點。圖上的邊被稱為數(shù)據(jù)流，與此同時，幾層拓撲結(jié)構(gòu)充當數(shù)據(jù)管道[15]進行數(shù)據(jù)轉(zhuǎn)化計算。從表面上看，Storm的拓撲結(jié)構(gòu)類似于MapReduce的Job，但是Storm與MapReduce的主要區(qū)別在于數(shù)據(jù)流[16]是實時處理的，而不是單個批處理的。此外，Storm拓撲[17]無限期地被運行，直到被用戶主動殺死，而MapReduce的Job處理完一批數(shù)據(jù)就會自動結(jié)束。

在實際應(yīng)用過程中，需要自行設(shè)計數(shù)據(jù)分組策略，即拓撲結(jié)構(gòu)。Storm中有幾種常用的分組策略：按字段分組(Field Grouping)、隨機分組(Shuffle Grouping)、不分組(No Grouping)。Storm編程模型如圖2所示。

圖2 Storm編程模型

Topology：Storm中運行的實時應(yīng)用程序的名稱。

Spout：在一個Topology中獲取源數(shù)據(jù)流的組件。

Bolt：接收數(shù)據(jù)流執(zhí)行處理的組件。

Tuple：一次消息傳遞的基本單元。

Stream：表示數(shù)據(jù)流的流向。

2．2 歷史頻次統(tǒng)計方法拓撲結(jié)構(gòu)設(shè)計

在本文框架中，Storm負責讀取大批量動目標數(shù)據(jù)、進行數(shù)據(jù)預(yù)處理、統(tǒng)計網(wǎng)格內(nèi)動目標出現(xiàn)的次數(shù)、計算出現(xiàn)頻率、預(yù)測下一個航點位置，并對預(yù)測結(jié)果進行實時分析等操作。針對時序性動目標數(shù)據(jù)，圖3展示了本文框架的拓撲示意圖。

圖3 本文框架拓撲示意圖

圖3由可以分布式并發(fā)執(zhí)行的多個Spout和多組Bolt組成，其中多組Bolt又由不同功能的Bolt組成。首先，Spout發(fā)射的元組是由不同時段內(nèi)航班的航班號、經(jīng)緯度、高度、航向等數(shù)據(jù)所組成的鍵值對，采用按地域字段分組策略，這使得每組Bolt只接收特定數(shù)據(jù)進行處理。例如，某組Bolt只負責北京空域的航班數(shù)據(jù)處理，而“忽略”其他空域數(shù)據(jù)。采用按地域分組策略的好處在于，可以將海量且種類繁多的動目標數(shù)據(jù)較平均地分配到拓撲的多組Bolt上進行并發(fā)處理，在加快計算速度的同時，也在一定程度上保證多個計算單元的計算負載均衡。

2．3 分布式實時預(yù)測框架

為滿足海量動目標實時預(yù)測的需求，本文設(shè)計一種基于Storm的分布式預(yù)測框架[18]，如圖4所示。

圖4 預(yù)測框架示意圖

本框架由數(shù)據(jù)源發(fā)生器提供數(shù)據(jù)輸入(數(shù)據(jù)源發(fā)生器為不間斷發(fā)送連續(xù)動目標數(shù)據(jù)的工具)，數(shù)據(jù)的收集與處理分別由Storm中的Spout與Bolt組件負責。

由于動目標數(shù)據(jù)量大，數(shù)據(jù)連續(xù)發(fā)送時間長，需要保證Spout收集的數(shù)據(jù)較為平均，防止局部擁塞[19]的發(fā)生。每組Bolt選用按地域分片Spout收集的數(shù)據(jù)進行處理。

2．3．1 Spout處理機制

本文框架中主要調(diào)用Spout的nextTuple()方法與數(shù)據(jù)源接口進行通信，實現(xiàn)動目標數(shù)據(jù)的讀取，并以先進先出的隊列順序發(fā)射給Bolt。其處理流程如圖5所示。

圖5 Spout處理流程圖

圖5中構(gòu)建數(shù)據(jù)序列、序列緩沖機制，數(shù)據(jù)序列發(fā)送構(gòu)成了nextTuple()方法。其中構(gòu)建數(shù)據(jù)序列的方法如圖6、圖7所示。

圖6 初始化動目標數(shù)據(jù)序列構(gòu)建

圖7 運行時動目標數(shù)據(jù)序列構(gòu)建

2．3．2 Bolt處理機制

本文框架利用多組Bolt，把從Spout發(fā)出的元組數(shù)據(jù)進行預(yù)處理、統(tǒng)計預(yù)測、誤差計算。其中主要調(diào)用Bolt的execute()方法按區(qū)域分組策略相應(yīng)處理接收到的元組數(shù)據(jù)[20]。每組各Bolt的處理方法如下所示，其中Predict()方法的預(yù)測主要由歷史數(shù)據(jù)在目標航點出現(xiàn)的頻率大小決定。

預(yù)處理Bolt：

1)Receive_tuples()；//獲取發(fā)來的元組數(shù)據(jù)

秦虹路現(xiàn)狀東西向下穿寧蕪鐵路，涵洞車道規(guī)模（雙向兩車道）與限高（僅3m）均收到較大制約，極易造成擁堵。優(yōu)化后，將鐵路走廊改造為城市支路和綠道，同時對該節(jié)點豎向進行優(yōu)化，消除凈空不足的安全隱患，也與周邊地塊豎向?qū)崿F(xiàn)良好銜接。同時對新平面交叉口進行渠化設(shè)計，合理分配機動車與慢行空間路權(quán)。

2)Preproccess_tuples()；//預(yù)處理數(shù)據(jù)以便統(tǒng)計分析

統(tǒng)計預(yù)測Bolt：

1)Statistic()；//統(tǒng)計網(wǎng)格內(nèi)動目標出現(xiàn)的頻次

2)Calculate_frequency()；//計算每個網(wǎng)格動目標出現(xiàn)的頻率

3)Predict()；//預(yù)測下一時刻的數(shù)據(jù)

誤差計算Bolt：

Calculate_error()；//將預(yù)測數(shù)據(jù)與當前時刻的真實數(shù)據(jù)比較并計算誤差

3 實驗與結(jié)果分析

本次實驗所使用的數(shù)據(jù)來源于FlightAware網(wǎng)站上航班的飛行數(shù)據(jù)。筆者在爬取數(shù)據(jù)后，已經(jīng)對航班數(shù)據(jù)做了一定的數(shù)據(jù)清洗，數(shù)據(jù)完整、有效，可以模擬真實動目標數(shù)據(jù)。

3．1 樣本容量對預(yù)測結(jié)果的影響

使用Storm頻次統(tǒng)計方法進行預(yù)測，需要前期的樣本容量(即N值)越大越好。由于爬取的數(shù)據(jù)數(shù)量有限，本次分析將針對樣本容量N(本次實驗中N代表數(shù)據(jù)的天數(shù))對實驗預(yù)測結(jié)果進行對比分析[21]。

將爬取的400天北京飛往其他省會城市的飛行數(shù)據(jù)平均分為4組，分別計算其平均相對誤差(Mean Relative Error， MRE)，見式(8)，結(jié)果如圖9所示。

圖8 動目標軌跡預(yù)測展示界面

(8)

圖9 樣本容量與預(yù)測誤差的關(guān)系圖

由圖9可以看出，隨著樣本容量N值的不斷增大，預(yù)測的準確率趨于平滑，當N大于50時，準確率大致趨于一定值。所以在使用基于歷史頻次統(tǒng)計的預(yù)測方法時，應(yīng)該盡量保證樣本容量的充足，最少不低于50，這樣可以在預(yù)測實時性的基礎(chǔ)上，盡量保證目標軌跡預(yù)測的準確性。

3．2 準確率分析

為驗證2種方法的預(yù)測準確性，本節(jié)分別對2種方法的預(yù)測準確性進行分析。

3．2.1 五點微分法準確率分析

表1 五點微分法預(yù)測數(shù)據(jù)比較 單位：°

比較內(nèi)容時間點01234567891011實際0.7560.8691.0451.3431.5211.7342.0342.4652.7543.0323.3453.675預(yù)測000001.9052.1562.5122.8452.9783.2983.701

選用所有被測點中的12個位置點。表1數(shù)據(jù)來自目標運動速度在1°/s～60°/s之間，按0.5 s采樣得到的位置值。由于在這一段時間內(nèi)目標運動是線性的，所以誤差在-0.2°±0.02°之間。五點微分預(yù)測法在預(yù)測飛機線性飛行時預(yù)測準確率較高，但是如果飛機遭遇突發(fā)情況(如天氣惡化、氣流變化、塔臺突發(fā)調(diào)度)，預(yù)測準確率會變低。

3．2.2 基于Storm歷史頻次預(yù)測方法準確率分析

圖10 基于Storm歷史頻次預(yù)測方法誤差統(tǒng)計圖

將樣本容量N選擇為50天，隨機選擇100個時間點對預(yù)測結(jié)果進行相對誤差計算，令相對誤差為(預(yù)測值-真實值)/真實值。相對誤差統(tǒng)計圖如圖10所示，設(shè)定誤差閾值為±8%，其中超過閾值的點約占總點數(shù)的14%。使用基于Storm的歷史頻次預(yù)測方法對動目標位置進行預(yù)測，預(yù)測值基本分布在真實值兩側(cè)，結(jié)果基本符合預(yù)期效果。

3．3 實時性分析

由于爬取的真實航班數(shù)據(jù)讀入量約等于2條/min，速度較慢，檢驗?zāi)繕祟A(yù)測的實時性需要發(fā)送時間間隔在100 ms左右的數(shù)據(jù)較為合適。所以本次實驗進行了數(shù)據(jù)的壓縮處理，將30 s發(fā)送一條數(shù)據(jù)壓縮到100 ms一條。本次實驗盡量選擇航行時間較長(大于5 h)的飛機進行測試。

圖11為五點微分法與基于Storm的歷史頻次統(tǒng)計方法的延遲對比。

圖11 預(yù)測延遲對比圖

從圖11可知，五點微分法由于是單線程運行的，當數(shù)據(jù)量大時，預(yù)測延遲急劇增高，但是在數(shù)據(jù)量較小時，預(yù)測延遲低于Storm法。Storm法的延遲在數(shù)據(jù)量增大時，保持一定的預(yù)測穩(wěn)定性。

4 結(jié)束語

本文采用五點微分法和基于Storm的歷史頻次統(tǒng)計分析方法，實現(xiàn)了二維虛擬場景中動目標的實時軌跡分析[22]，效果較好。在后期研究中，將在Bolt的預(yù)測[23]環(huán)節(jié)結(jié)合神經(jīng)網(wǎng)絡(luò)算法，在按地域分段預(yù)測方面結(jié)合MPI編程，構(gòu)建并行消息傳遞模型，實現(xiàn)更加準確的動目標實時軌跡數(shù)據(jù)分析。