基于轉(zhuǎn)彎點(diǎn)聚類的航空器飛行軌跡分析*

鄭　樂　隋　東　張軍峰　武曉光

(南京航空航天大學(xué) 民航學(xué)院　江蘇　南京　210016)

基于轉(zhuǎn)彎點(diǎn)聚類的航空器飛行軌跡分析*

鄭樂隋東張軍峰武曉光

(南京航空航天大學(xué) 民航學(xué)院江蘇南京210016)

摘要：為滿足進(jìn)場(chǎng)航線設(shè)計(jì)適應(yīng)實(shí)際運(yùn)行需求,在分析實(shí)際運(yùn)行航跡數(shù)據(jù)特征基礎(chǔ)上,提出了通過轉(zhuǎn)彎點(diǎn)聚類策略分析航空器飛行軌跡的方法.并設(shè)計(jì)基于轉(zhuǎn)彎點(diǎn)最長(zhǎng)公共子序列的航跡聚類模型,同時(shí)給出了改進(jìn)的平均軌跡構(gòu)建算法,實(shí)現(xiàn)了盛行交通流的識(shí)別.將該方法應(yīng)用于上海浦東機(jī)場(chǎng)進(jìn)港航班雷達(dá)軌跡分析,仿真結(jié)果表明，提出的方法可以有效地從龐雜的雷達(dá)軌跡信息中識(shí)別盛行交通流.

關(guān)鍵詞：空中交通管制；空中交通流；軌跡；聚類分析；LCS算法

鄭樂(1990- ):男,碩士生，主要研究領(lǐng)域?yàn)榭罩薪煌ò踩治?/p>

0引言

目前，識(shí)別盛行交通流主要采用軌跡聚類的方法，如基于離散軌跡點(diǎn)的聚類，基于部分特征相似子軌跡識(shí)別的聚類和面向完整軌跡的聚類.上述方法的核心在于相似度度量模型的建立(包括基于歐式距離[1-2]、特征點(diǎn)提取[3]、最長(zhǎng)公共子序列[4],以及基于結(jié)構(gòu)相似度[5]等方法)和完備高效的軌跡聚類的算法(包括K-Means,BIRCH,DBSCAN和OPTICS等).其中，F(xiàn)rank[6]通過構(gòu)建進(jìn)場(chǎng)航跡的相似度矩陣，提出了基于不同軌跡間點(diǎn)對(duì)距離的層次聚類方法；趙恩來等[7]采用加權(quán)Manhattan距離與懲罰系數(shù)相結(jié)合的距離度量，提出一種基于密度的改進(jìn)航跡聚類算法；王明明等[8]借用信息論中最小描繪長(zhǎng)度(MDL)原理對(duì)特征點(diǎn)進(jìn)行劃分，再運(yùn)用改進(jìn)的模糊C-means算法實(shí)現(xiàn)了特征點(diǎn)聚類；Lee等[9]提出將一條軌跡分為一組粗線段，然后使用基于密度的聚類算法對(duì)相似的線段進(jìn)行聚類.

本文從航空器的實(shí)際運(yùn)行軌跡角度出發(fā)，將航空器的軌跡用其有限的轉(zhuǎn)彎點(diǎn)進(jìn)行表示，使用最長(zhǎng)公共子序列(LCS)算法進(jìn)行軌跡間的差異度測(cè)量，用層次聚類法對(duì)進(jìn)場(chǎng)航跡數(shù)據(jù)集進(jìn)行航跡差異度的聚類分析,并給出航跡聚類集的平均飛行航跡構(gòu)造方法.最后給出實(shí)例應(yīng)用分析，從中識(shí)別出盛行的交通流以及管制員的指揮意圖.

1航跡數(shù)據(jù)的特征分析

設(shè)進(jìn)場(chǎng)航跡集合為T={T1,T2,…,Ti,…,Tn}.其中：i為進(jìn)場(chǎng)航班，i=1,2,…,n，n為總航班數(shù).對(duì)于每架進(jìn)場(chǎng)航班，對(duì)應(yīng)軌跡Ti={Ti1,Ti2,…,Til,…,Timi}.其中：mi為雷達(dá)軌跡數(shù)據(jù)中離散航跡點(diǎn)的個(gè)數(shù).軌跡Ti為mi×4的矩陣，對(duì)于任意l∈{1,2,…,mi}，航跡點(diǎn)可以表示為Til=(til,xil,yil,zil).其中:(xil,yil,zil)是對(duì)應(yīng)航空器i的三維坐標(biāo)，til對(duì)應(yīng)于雷達(dá)刷新的時(shí)刻，坐標(biāo)系以機(jī)場(chǎng)基準(zhǔn)點(diǎn)為原點(diǎn)坐標(biāo)，正東方向?yàn)閤軸的正方向，正北方向?yàn)閥軸的正方向，z為飛行高度.

2基于聚類的飛行航跡分析

2.1非常規(guī)軌跡探測(cè)

對(duì)于與標(biāo)準(zhǔn)儀表進(jìn)場(chǎng)程序偏離較遠(yuǎn)的軌跡稱之為非常規(guī)軌跡.由于非常規(guī)軌跡在聚類時(shí)對(duì)于聚類的結(jié)果影響很大，因此需要將其剔除.此處采取了一種基于網(wǎng)格的方法實(shí)現(xiàn)非常規(guī)軌跡的探測(cè)，將終端空域在水平面的投影分成p×p的網(wǎng)格.每條雷達(dá)軌跡都會(huì)穿過若干網(wǎng)格，當(dāng)一條雷達(dá)軌跡穿過其中任一個(gè)網(wǎng)格時(shí)，記錄穿過該網(wǎng)格的航班號(hào).對(duì)于n條進(jìn)場(chǎng)航班，當(dāng)穿過任意網(wǎng)格的航班數(shù)少于N架次時(shí)則認(rèn)為該網(wǎng)格為稀有網(wǎng)格，若一條航班穿過的稀有網(wǎng)格數(shù)與其穿過的總網(wǎng)格數(shù)的比例超過閥值Q時(shí)，則認(rèn)為該航班為非常規(guī)軌跡.

2.2基于轉(zhuǎn)彎點(diǎn)的航跡聚類

當(dāng)航空器進(jìn)場(chǎng)時(shí)，通常按照公布的儀表進(jìn)場(chǎng)程序飛行，這些儀表進(jìn)場(chǎng)程序由一系列的航路點(diǎn)、直線航段與少量的轉(zhuǎn)彎航段構(gòu)成.因此，著眼于確定轉(zhuǎn)彎點(diǎn)的二維坐標(biāo)，有利于更精確的進(jìn)行聚類.本文提出的航跡聚類算法分為轉(zhuǎn)彎點(diǎn)識(shí)別、轉(zhuǎn)彎點(diǎn)聚類與航跡聚類3個(gè)步驟，見圖1.

圖1　基于轉(zhuǎn)彎點(diǎn)聚類的流程

2.2.1轉(zhuǎn)彎點(diǎn)識(shí)別

轉(zhuǎn)彎點(diǎn)即為航空器改變航向的位置，由于雷達(dá)數(shù)據(jù)提供的航向信息已做取整處理，滿足不了精度要求，故采取式(1)計(jì)算tl時(shí)刻的航向.

(1)

由于位置信息中存在噪聲污染，會(huì)影響轉(zhuǎn)彎點(diǎn)的識(shí)別，因此使用低通濾波器實(shí)現(xiàn)對(duì)航向的預(yù)處理，見式(2).

(2)

2.2.2轉(zhuǎn)彎點(diǎn)聚類

為了從轉(zhuǎn)彎點(diǎn)集合S發(fā)現(xiàn)分布的規(guī)律，采用K-Means算法對(duì)轉(zhuǎn)彎點(diǎn)進(jìn)行聚類.K-Means算法的主要思想是將集合S分為k個(gè)聚類C={C1,C2,...,Ck}，其中k<|S|,聚類的結(jié)果應(yīng)滿足式(3)，其中tpmean是聚類Ci的平均值，稱為中心點(diǎn)，是一個(gè)聚類中所有元素的中心.

(3)

由于K-Means是一種啟發(fā)式算法，所以難以保證最終結(jié)果的全局最優(yōu)性，需要以不同的初始條件運(yùn)行多次得到相對(duì)最優(yōu)的解.通過設(shè)定式(3)中k的值，可以將轉(zhuǎn)彎點(diǎn)集合S分成k個(gè)子集合.通過對(duì)這k個(gè)子集合進(jìn)行編號(hào){1,2,…,k}，可以將每個(gè)轉(zhuǎn)彎點(diǎn)通過子集合的編號(hào)表示出來，每條航跡也可以通過轉(zhuǎn)彎點(diǎn)所屬的子集合的編號(hào)表示出來.

2.2.3航跡聚類

對(duì)于航空器i的軌跡，可以用一系列的轉(zhuǎn)彎點(diǎn)所屬于的子集合來描述，即wpi={cti1,…,ctis}.其中：ctis為第s個(gè)轉(zhuǎn)彎點(diǎn)所屬的子集合的編號(hào).這樣表示的目的是方便對(duì)對(duì)軌跡進(jìn)行差異度比較.本文使用最長(zhǎng)公共子序列(LCS)算法對(duì)任意兩條軌跡進(jìn)行差異度對(duì)比.LCS算法是為了在兩個(gè)集合中找出最長(zhǎng)的公共子序列，該方法允許兩個(gè)集合的長(zhǎng)度不相等.由于所有的航空都是從四邊轉(zhuǎn)彎進(jìn)入五邊來對(duì)準(zhǔn)跑道，所以最后一個(gè)轉(zhuǎn)彎對(duì)于軌跡來說并沒有意義，因此將所有軌跡的最后一個(gè)轉(zhuǎn)彎點(diǎn)剔除.

舉例說明，對(duì)于任意2架航空器i，j，設(shè)航空器i的軌跡表示為wpi={1,4,7,9,11}，轉(zhuǎn)彎點(diǎn)的個(gè)數(shù)|wpi|=5；航空器j的軌跡可以表示為 wpj={1,3,4,7,8,11}，轉(zhuǎn)彎點(diǎn)個(gè)數(shù)|wpj|=6；則兩者的最長(zhǎng)的公共子序列的個(gè)數(shù)|lcs|=4，最長(zhǎng)的公共子序列l(wèi)cs={1,4,7,11}.這2條軌跡的差異度通過式(4)進(jìn)行計(jì)算.2條航跡wpi和wpj的差異度系數(shù)R(i,j)數(shù)值越大,表示2條航跡之間的公共子序列越少, 2條軌跡越不相似.

(4)

對(duì)于總航班數(shù)為n航跡集合S，構(gòu)造式(5)所示的差異度矩陣Rd表示集合S中所有航跡相互之間的差異程度.

(5)

式中:R(i,j)(i≠j;i,j∈{1,2,…,n})表示2條不同航跡之間的差異度系數(shù)；R(i,i)=0(i∈{1,2,…,n})表示各條航跡與自身之間不存在偏差；R(i,j)=R(j,i)(i,j∈{1,2,…,n})表示此差異度矩陣是一個(gè)對(duì)角矩陣.通過構(gòu)建差異度矩陣Rd，可以從中發(fā)現(xiàn)每條軌跡和航跡集合S中其他所有軌跡的差異程度.

基于上述的差異度矩陣, 使用層次聚類方法對(duì)航跡集合S進(jìn)行聚類.對(duì)于總航班數(shù)為n航跡集合S，首先將每條航跡歸為一類，根據(jù)差異度矩陣即可確定類與類之間的距離，通過反復(fù)的合并，即可得到聚類結(jié)果樹形圖.建立起了航跡數(shù)據(jù)的聚類樹之后,通過對(duì)聚類樹進(jìn)行剪枝即可得到航跡的聚類.

2.3聚類的平均航跡構(gòu)造

本文提出的平均軌跡算法是對(duì)LR-1算法改進(jìn)，首先找出航跡聚類中航跡點(diǎn)最少的一條航跡Ti：Ti=(Ti1,Ti2,…,Timt)作為基礎(chǔ)航跡點(diǎn)集，mt為航跡聚類中航跡點(diǎn)最少的一條航跡的航跡點(diǎn)數(shù).然后采用改進(jìn)的LR-1算法構(gòu)造出一個(gè)新的航跡聚類Ci'，Ci'和原來的聚類航跡數(shù)相同，且所有航跡的航跡點(diǎn)數(shù)都與Ti相同.最后通過求取Ci'中具有相同序號(hào)的航跡點(diǎn)的平均值即可得到平均航跡M，M={mp1,mp2,…,mpi,…,mpmt}.其中"i∈{1,…,mt}為航跡點(diǎn)的編號(hào)，M的航跡點(diǎn)的個(gè)數(shù)等于航跡點(diǎn)最少的一條航跡是為了保證平均航跡中每一個(gè)航跡點(diǎn)的構(gòu)造都包含了所有航跡的信息.改進(jìn)的LR-1算法的基本思想如下：(1)對(duì)于聚類Ci中任意一條航跡Tj，設(shè)其航跡點(diǎn)數(shù)據(jù)集為：Tj=(Tj1,Tj2,…,Tjmj).其中:mt≤mj.如圖2a)所示，計(jì)算基礎(chǔ)航跡點(diǎn)集最后一個(gè)點(diǎn)和Tj最后3個(gè)點(diǎn)之間的距離，將距離的最小值記為新的航跡Tj'中最后一個(gè)點(diǎn)Tjmt；(2)如圖2b)所示，計(jì)算基礎(chǔ)航跡點(diǎn)集最后一個(gè)點(diǎn)的前一個(gè)點(diǎn)和步驟(1)中距離最小值點(diǎn)的前3個(gè)點(diǎn)的距離，將距離的最小值記為新的航跡Tj'中倒數(shù)第二個(gè)點(diǎn)Tjmt-1；(3)重復(fù)上述步驟，直到比較完所有的基礎(chǔ)航跡點(diǎn)集.此時(shí)即可得到新的航跡Tj'，Tj'與Ti具有相同的航跡點(diǎn)數(shù)，且具有相同序號(hào)的航跡點(diǎn)具有較好的局部相似性.通過上述方法對(duì)聚類中其他的軌跡進(jìn)行相同的操作即可得到新的航跡聚類Ci'.

圖2　改進(jìn)的LR-1算法示意圖

3仿真驗(yàn)證

應(yīng)用上述航跡聚類方法，對(duì)浦東機(jī)場(chǎng)2013年1月2日北向運(yùn)行的418條進(jìn)場(chǎng)飛行軌跡進(jìn)行了實(shí)例分析研究.在所有的進(jìn)場(chǎng)軌跡中，最小的離散航跡點(diǎn)數(shù)mi為155,最大為566.浦東機(jī)場(chǎng)的主要進(jìn)港點(diǎn)有4個(gè)DUMET,PIONT,VMB,BK.設(shè)定p=20，將上海終端空域在水平面的投影分成20×20的網(wǎng)格.當(dāng)穿過任意網(wǎng)格的航班數(shù)少于N=20架次時(shí)，則認(rèn)為該網(wǎng)格為稀有網(wǎng)格.若一條航班穿過的稀有網(wǎng)格數(shù)與其穿過總網(wǎng)格數(shù)的比例超過10%時(shí)(Q=10%)，則認(rèn)為該航班為非常規(guī)軌跡.如圖3所示，共探測(cè)出非常規(guī)軌跡13條，從圖中可以看出主要是從BK和DUMET進(jìn)港點(diǎn)進(jìn)來的航班.

圖3　上海浦東機(jī)場(chǎng)非常規(guī)軌跡

對(duì)剩余的405條航跡進(jìn)行轉(zhuǎn)彎點(diǎn)識(shí)別，設(shè)定為φf=0.025 rad=1.43°，該閾值的設(shè)定既可以發(fā)現(xiàn)到很小的航向變化，還能消除航向擾動(dòng).當(dāng)航向偏轉(zhuǎn)連續(xù)6次超過φf時(shí)，則辨別出一個(gè)轉(zhuǎn)彎點(diǎn).圖4中是4條來自不同進(jìn)港點(diǎn)的雷達(dá)軌跡，轉(zhuǎn)彎點(diǎn)用藍(lán)色的點(diǎn)進(jìn)行標(biāo)示.

使用K-Means算法對(duì)所有航跡的轉(zhuǎn)彎點(diǎn)進(jìn)行聚類，k值設(shè)定為14，聚類的結(jié)果見圖4.將所有的航跡用一系列的轉(zhuǎn)彎點(diǎn)所屬的子集合的編號(hào)來表示，通過LCS算法計(jì)算兩兩航跡之間的差異度系數(shù)，構(gòu)成差異度矩陣Rd.通過層次聚類法對(duì)所有的航跡進(jìn)行聚類，考慮到聚類的結(jié)果和進(jìn)場(chǎng)程序的相似性，通過剪枝共得到10個(gè)聚類，航跡的聚類結(jié)果見圖5.

圖4　使用K-Means算法對(duì)轉(zhuǎn)彎點(diǎn)進(jìn)行聚類的結(jié)果

圖5　使用層次聚類法對(duì)航跡進(jìn)行聚類的結(jié)果

圖6　飛行軌跡盛行交通流

使用改進(jìn)的LR-1算法對(duì)所得到的10個(gè)航跡聚類求取其平均軌跡M，結(jié)果見圖6.圖6即為識(shí)別出來的10條盛行交通流.對(duì)比浦東機(jī)場(chǎng)的北向運(yùn)行的進(jìn)場(chǎng)程序和盛行交通流可以發(fā)現(xiàn)，由于從BK進(jìn)場(chǎng)的航班只有一條進(jìn)場(chǎng)程序，因此從BK進(jìn)場(chǎng)的三條盛行交通流存在明顯的差異.粉色的盛行交通流路徑最短，這可能在是不繁忙時(shí)段，管制員引導(dǎo)航班越過幾個(gè)航路點(diǎn)以節(jié)省燃油以及運(yùn)營(yíng)成本.另外兩條盛行交通流分別向東和向西偏離，最后在FAF點(diǎn)匯聚，這可能是繁忙時(shí)段管制員為了對(duì)航班進(jìn)行合理的排序，而令部分航班繞飛以保證航班之間的具有足夠的安全間隔；從VMB進(jìn)場(chǎng)的兩條盛行交通流和標(biāo)準(zhǔn)儀表進(jìn)場(chǎng)程序基本相一致，這可能是由于VMB的進(jìn)場(chǎng)程序總長(zhǎng)度較長(zhǎng)，管制員可以通過給出速度限制和高度限制對(duì)航班進(jìn)行調(diào)配；從PINOT和DUMET進(jìn)場(chǎng)的盛行軌跡在轉(zhuǎn)四邊時(shí)大多采取小半徑轉(zhuǎn)彎，這可能是管制員為了避免和BK進(jìn)場(chǎng)的航班出現(xiàn)沖突.

4結(jié)束語

本文介紹了基于轉(zhuǎn)彎點(diǎn)進(jìn)行航跡聚類的方法，可以從龐雜的RNAV進(jìn)場(chǎng)軌跡提取出盛行的交通流軌跡，并從中發(fā)現(xiàn)管制員的指揮意圖.但是在軌跡聚類之前需要進(jìn)行非常規(guī)軌跡的探測(cè)，剔除掉影響聚類的個(gè)別航班，而對(duì)于軌跡異常的原因并沒有進(jìn)行進(jìn)一步探討.此外，從歷史雷達(dá)軌跡中發(fā)現(xiàn)管制員如何通過速度和高度限制來對(duì)航班進(jìn)行調(diào)配需要進(jìn)一步的研究.

參 考 文 獻(xiàn)

[1]王超,徐肖豪,王飛.基于航跡聚類的終端區(qū)進(jìn)場(chǎng)程序管制適用性分析[J]. 南京航空航天大學(xué)學(xué)報(bào), 2013,45(1):130-139.

[2]AGRAWAL R,FALOUTSOS C,SWAMI A.Efficient similarity search in sequence databases[M].Springer Berlin Heidelberg,1993.

[3]PERNG C S,WANG H,ZHANG S R,et al. Landmarks:a new model for similarity-based pattern querying in time series databases[C]∥Data Engineering,2000.Proceedings.16th International Conference on. IEEE,2000:33-42.

[4]GARIEL M,SRIVASTAVA A,FERON E.Trajectory clustering and an application to airspace monitoring [J].Intelligent Transportation Systems,2011,12(4):1511-1524.

[5]袁冠,夏士雄,張磊,等.基于結(jié)構(gòu)相似度的軌跡聚類算法[J].通信學(xué)報(bào),2011,32(9):03-110.

[6]REHM F.Clustering of Flight Tracks[C].AIAA Infotech,Aerospace,2010:155-164.

[7]趙恩來,郝文宇,趙飛,等.改進(jìn)的基于密度的航跡聚類算法[J].計(jì)算機(jī)工程,2011,37(9):270-272.

[8]王超,王明明,王飛.基于改進(jìn)的模糊C-Means航跡聚類方法研究[J].中國(guó)民航大學(xué)學(xué)報(bào),2013,31(3): 14-18.

[9]LEE J G,HAN J,WHANG K Y.Trajectory clustering:A partition-and-group framework [C]∥Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data,Beijing,China:ACM Press,2007:593-604.

中圖法分類號(hào)：V355

doi:10.3963/j.issn.2095-3844.2015.01.032

收稿日期：2014-08-20

Analysis of the Aircraft Flight Path Based on Turning Points Clustering

ZHENG YueSUI DongZHANG JunfengWU Xiaoguang

(CollegeofCivilAviation,NanjingUniversityofAeronauticsandAstronautics,Nanjing210016,China)

Abstract：In order to meet the needs of design of the arrival routes adjust to the actual operation, an analysis method of the aircraft flight path based on turning points clustering, which is on the basis of the analysis of real flight trajectories data, is proposed. We also design a flight trajectory clustering model based on the longest common subsequence of the turning points, meanwhile a modified mean flight trajectory method is proposed to realize the identification of the prevalent air traffic flow. Finally, the method is applied to the analysis of the radar tracks of the arrival flights in Shanghai Pudong airport. With the simulations, it is shown that the prevalent air traffic flow can be extracted from the numerous and disorderly flight trajectories by the method.

Key words：air traffic control; air traffic flow;trajectory;clustering analysis; LCS algorithm

*江蘇省自然科學(xué)基金項(xiàng)目(批準(zhǔn)號(hào)：BK20130814)、波音-中國(guó)商飛聯(lián)合資助課題(批準(zhǔn)號(hào)：2012-TR-012)、中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(批準(zhǔn)號(hào)：NS2013064)、南京航空航天大學(xué)研究生創(chuàng)新基地開放基金資助項(xiàng)目(批準(zhǔn)號(hào)：kfjj130127)資助