侯 博,聶 穎

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

0 引 言

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

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

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

針對飛行目標(biāo)的實(shí)時(shí)分析，主要有以下要求：

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

2)實(shí)時(shí)預(yù)測準(zhǔn)確率要盡可能高。

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

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

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

1.1 五點(diǎn)微分法

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

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

(1)

分別把t=0,1,2,3,4代入式(1)，即可得到節(jié)點(diǎn)xk(k=0,1,2,3,4)一階導(dǎo)數(shù)[12]的五點(diǎn)數(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ù)測實(shí)現(xiàn)

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

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

ListDiff5Point(List f , double t)

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

(7)

其中，(x1,y1)即為下一個(gè)預(yù)測點(diǎn)。

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

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

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

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

2．1 Storm框架介紹

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

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

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

圖2 Storm編程模型

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

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

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

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

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

2．2 歷史頻次統(tǒng)計(jì)方法拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)

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

圖3 本文框架拓?fù)涫疽鈭D

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

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

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

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

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

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

2．3．1 Spout處理機(jī)制

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

圖5 Spout處理流程圖

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

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

圖7 運(yùn)行時(shí)動目標(biāo)數(shù)據(jù)序列構(gòu)建

2．3．2 Bolt處理機(jī)制

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

預(yù)處理Bolt：

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

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

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

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

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

2)Calculate_frequency()；//計(jì)算每個(gè)網(wǎng)格動目標(biāo)出現(xiàn)的頻率

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

誤差計(jì)算Bolt：

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

3 實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

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

(8)

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

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

3．2 準(zhǔn)確率分析

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

3．2.1 五點(diǎn)微分法準(zhǔn)確率分析

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

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

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

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

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

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

3．3 實(shí)時(shí)性分析

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

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

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

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

4 結(jié)束語

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