基于轉彎點聚類的航空器飛行軌跡分析*

鄭　樂　隋　東　張軍峰　武曉光

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

基于轉彎點聚類的航空器飛行軌跡分析*

鄭樂隋東張軍峰武曉光

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

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

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

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

0引言

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

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

1航跡數據的特征分析

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

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

2.1非常規軌跡探測

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

2.2基于轉彎點的航跡聚類

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

圖1　基于轉彎點聚類的流程

2.2.1轉彎點識別

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

(1)

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

(2)

2.2.2轉彎點聚類

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

(3)

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

2.2.3航跡聚類

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

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

(4)

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

(5)

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

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

2.3聚類的平均航跡構造

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

圖2　改進的LR-1算法示意圖

3仿真驗證

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

圖3　上海浦東機場非常規軌跡

對剩余的405條航跡進行轉彎點識別，設定為φf=0.025 rad=1.43°，該閾值的設定既可以發現到很小的航向變化，還能消除航向擾動.當航向偏轉連續6次超過φf時，則辨別出一個轉彎點.圖4中是4條來自不同進港點的雷達軌跡，轉彎點用藍色的點進行標示.

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

圖4　使用K-Means算法對轉彎點進行聚類的結果

圖5　使用層次聚類法對航跡進行聚類的結果

圖6　飛行軌跡盛行交通流

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

4結束語

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

參 考 文 獻

[1]王超,徐肖豪,王飛.基于航跡聚類的終端區進場程序管制適用性分析[J]. 南京航空航天大學學報, 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]袁冠,夏士雄,張磊,等.基于結構相似度的軌跡聚類算法[J].通信學報,2011,32(9):03-110.

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

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

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

*江蘇省自然科學基金項目(批準號：BK20130814)、波音-中國商飛聯合資助課題(批準號：2012-TR-012)、中央高校基本科研業務費專項資金項目(批準號：NS2013064)、南京航空航天大學研究生創新基地開放基金資助項目(批準號：kfjj130127)資助