鄭　樂　隋　東　張軍峰　武曉光

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

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

鄭樂隋東張軍峰武曉光

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

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

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

鄭樂(1990- ):男,碩士生，主要研究領(lǐng)域為空中交通安全分析

0引言

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

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

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

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

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

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

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

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

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

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

2.2.1轉(zhuǎn)彎點識別

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

(1)

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

(2)

2.2.2轉(zhuǎn)彎點聚類

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

(3)

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

2.2.3航跡聚類

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

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

(4)

對于總航班數(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òu)建差異度矩陣Rd，可以從中發(fā)現(xiàn)每條軌跡和航跡集合S中其他所有軌跡的差異程度.

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

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

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

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

3仿真驗證

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

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

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

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

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

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

圖6　飛行軌跡盛行交通流

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

4結(jié)束語

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

參 考 文 獻(xiàn)

[1]王超,徐肖豪,王飛.基于航跡聚類的終端區(qū)進(jìn)場程序管制適用性分析[J]. 南京航空航天大學(xué)學(xué)報, 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é)報,2011,32(9):03-110.

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

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

[8]王超,王明明,王飛.基于改進(jìn)的模糊C-Means航跡聚類方法研究[J].中國民航大學(xué)學(xué)報,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.

中圖法分類號：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é)基金項目(批準(zhǔn)號：BK20130814)、波音-中國商飛聯(lián)合資助課題(批準(zhǔn)號：2012-TR-012)、中央高?；究蒲袠I(yè)務(wù)費專項資金項目(批準(zhǔn)號：NS2013064)、南京航空航天大學(xué)研究生創(chuàng)新基地開放基金資助項目(批準(zhǔn)號：kfjj130127)資助