郑　乐　隋　东　张军峰　武晓光

(南京航空航天大学 民航学院　江苏　南京　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)资助