基于谱聚类的扇区划分*

高 伟，陈姝含，叶志坚，吕振华

（中国民航大学空中交通管理学院，天津 300300）

0 引言

随着航空运输业的不断发展，空中交通量持续增加，有限的民航空域资源要承担越来越多的飞行需求，飞行安全受到威胁的同时，管制员的工作量也不断增大［1］。面对日益饱和的民用航空空域，如何更好地利用空域资源已成为国内外许多学者和空中交通管制组织关注的焦点。终端区交通流密集、空域结构复杂且存在较多的交叉飞行，因此，终端区的合理规划对于提高机场运行效率和空中交通的安全性，以及平衡管制员的工作负荷具有重要意义［2］。

目前国内外许多学者对扇区的划分和优化展开了深入的研究，可以对管制空域以二维、三维以及功能性的形式进行划分，在当前阶段，研究重点围绕二维空域［1］。文献［2］基于终端区内交通流的特征提出了内扇功能性的概念。文献［3-4］在管制空域拓扑结构的基础上研究了扇区优化设计工作的理论基础。文献［5］利用空域的正六边形分割法，将给定空域分割为六边形空域单元，并将其作为输入量输入TAAM 仿真软件来求取管制员工作负荷。文献［6］以符合交通流特征为目标，利用二进制空间划分法BSP（Binary Space Partition）方法对民航高空管制空域进行划分，并在模型中加入管制员可选参数，将交通流的方向、交通流的特征作为扇区划分的主要考虑因素。文献［7］基于空域的内部结构与运行状态，定义了空中交通复杂度并以此来衡量管制员的工作负荷。文献［8］通过总结前人的经验，对动态扇区划分作出了调查研究，并将一天24 h 分为4 个时间段，对时间点生成过渡图来实现扇区的动态划分。

国内外的研究大多基于管制员工作负荷和空域复杂度对管制扇区进行划设。在基于图论的扇区划设研究中，多数研究对关键的航路点进行顶点融合后再设置保护区，导致空域结构的过度简化，不仅无法反映空域真实结构，还会产生自相矛盾的结果。并且以上研究多是以分割的多边形空域单元为单位进行研究，难以全面地反映空域实际情况，不符合实际需求。基于此，本文保留完整的空域结构，将空域结构细化为航段，全面地反映空域的实际情况；提出了点的靠近程度并对航空器航迹进行检测，对空域中关键点间的关系进行描述，并建立带有权重的空域图论模型，利用谱聚类算法对模型进行解算；利用voronoi 图生成扇区边界并对其进行几何修正，最后结合了一个实例对提出的扇区划分方法进行了验证。

1 管制扇区划设模型

扇区划分的过程需要考虑诸多因素［9］，如：扇区对应的空域结构、扇区内航空器状态、空域需求以及管制员的工作需求等。中国民用航空局在《民用航空使用空域办法》［10］中细述了扇区划分原则。利用谱聚类构图的思想，建立管制扇区划设模型，在进行构图时考虑了扇区的连续性原则、扇区间协调移交的限制。

1.1 空域网络结构

空域扇区划分的必要性主要是由影响交通安全的管制员工作负荷所决定的。Li［11］等人依据Eurocontrol 提出的影响管制员工作负荷的3 个因素，将管制员工作负荷量化为：

基于现实问题而假设的简化实例的空域示意图如图1 所示，假设关键点2 为机场。

图1 空域示意图

1.2 航迹识别

由于监视、运行等方面的限制，航迹检测半径r的取值大小会影响点迹检测的结果，需要根据实际情况确定其取值。若r 取值过大，会导致以关键圆产生重叠，进而使得到的交通量过大；若r 取值过小，会因监视设备的时间间隔检测不到航空器，丢失部分点迹，进而使得到的交通量过小。在进行管制扇区划设时，通过不断改变r 的大小，进行大量的划设试验，将得到的统计数据与空域内总交通量进行比对，认为在本文研究的情景下，r 在355.2 m 左右进行取值时，能反映最接近真实的情况。

1.3 点的靠近程度

文献［11，13］仅根据关键点间航空器数量即管制员的监视负荷作为图的权重，由此来表示图中点与边的关系。这并不能真实地代表管制员的工作负荷，且在聚类时，会导致航段上航空器数量相近的边聚在同一类中，出现扇区不连续的情况，这并不符合管制扇区划设的实际需求。扇区的连续性原则示意图如图2 所示。

图2 扇区连续性原则示意图

因此，在描述图中点之间的关系时，不仅要考虑到航段上的监视负荷，还要考虑关键点之间的地理位置关系。

式（5）为二维空间距离公式，仅用来计算空域中航段的长度，所以不采用三维空间距离公式；其中，x、y 分别代表关键点的横坐标和纵坐标，i，j=1，2，…，n。航空器在航路点上通常要向管制员进行航空器位置报告，而两扇区的管制员对航空器的移交需要需要时间。

其中，lij为两关键点间的距离；u＞1，可以根据实际情况进行设定，目的是强化距离小于8.5 km 的两关键点之间的联系，避免其在聚类时聚在不同的簇中，使划设的管制扇区满足协调移交的时间限制。u过小，达不到强化的目的；u 过大会导致该航段的两关键点联系过于紧密，在聚类时有很大概率将其单独聚类为一类。

文献［14］明确指出，若两个航路点之间的距离小于8.5 km，那么该航段上不应存在扇区的边界点；即距离较近的关键点，应尽可能地划分在相同的扇区内，连接航段的两关键点应在同一扇区中，边界线应尽可能切割距离足够长、流量小的航段。不同关键点之间的距离越小，靠近程度越大，关键点的靠近程度pij作为地理信息，反映了空域内关键点的静态联系。

1.4 空域图关系的描述

通过对关键点位置信息的统计和航空器航迹数据的识别，分别得到了空域内关键点的静态联系和动态联系。关键点之间距离越近，靠近程度越大，静态联系越大；关键点之间航空器数量越多，动态联系越大。用关键点之间的权值wij来描述空域中关键点之间的关系，

图1 中标注了由式（7）计算出的假设空域的关键点之间权值wij。

2 谱聚类算法及扇区划分

对建立的管制扇区划设模型利用谱聚类算法进行聚类，即得到属于不同扇区的关键点。借助voronoi图生成扇区边界并进行几何修正，完成扇区划分。

文献［11］没有考虑到扇区间监视负荷的差异；文献［13］没有考虑到协调负荷，且设计的算法找不到可行解，不符合管制扇区划设的实际情况。基于此，本文利用谱聚类切图方法，旨在将空中交通的航班量更均衡分配给不同扇区，同时还要保证不同扇区间的航班协调移交量尽量小。

2.1 谱聚类算法

谱聚类算法是建立在谱图理论基础之上的一种新型聚类算法，它能够在任意形状的样本空间上进行聚类，且收敛于全局最优解［15］。其基本思想为：首先利用高斯核函数计算数据之间的欧式距离，并构建相似度矩阵，将聚类问题转换为图分割问题；再根据相似度矩阵来获取拉普拉斯矩阵，并利用一种连续的松弛形式将图分割问题转化为拉普拉斯矩阵的谱分解问题；最后对拉普拉斯矩阵建立广义特征值问题，当将样本聚为K 类时，即取拉普拉斯矩阵前K 个最小的特征值对应的特征向量，利用经典的聚类算法（如K-means 算法）对其进行聚类。

1.4 节中构造的权重矩阵W 是对空域中关键点之间关系的描述，实际上即为谱聚类算法中的相似度矩阵。对建立好的空域结构图论模型执行谱聚类算法，谱聚类具体过程为：

1）计算度矩阵D：将权重矩阵W 中同行的元素相加得到度矩阵D，公式为：

2.2 谱聚类切图

在对空域内的关键点进行谱聚类时，不但要使长度较短的航段不被扇区边界所分割，还要使不同扇区间关键点的联系程度尽可能小。因此，管制扇区划设问题的两个目标是各扇区内的关键点联系程度接近和各扇区间联系程度小，分别表现为扇区间流量的均衡以及总的协调负荷小。实际上，这是一个谱聚类Ncut（Normaized cut）切图问题。

再利用K-means 聚类方法对其进行聚类，得到最终的聚类结果。

谱聚类Ncut 切图执行结果使得连接不同聚类间边的权重之和尽可能小，而同一聚类内的边权重和尽可能大。这意味着不同聚类之间顶点联系程度尽可能小，实现了切割代价尽可能小，切割代价越小，则代表着扇区间移交航空器需要精力越少，管制员的协调负荷越小；同一聚内类顶点联系程度越高，则代表这扇区间的流量越均衡，实现了管制员监视负荷的差异越小。

图3 为本文管制扇区划分的流程图。

图3 管制扇区划分的流程图

图4 为对第1.1 节假设的空域进行谱聚类的结果示意图（K=2），其中，实心圆点和空心圆点表示属于不同扇区的关键点。

图4 谱聚类结果

对空域中的关键点生产voronoi 图，即可得到初步的扇区边界。图5 为voronoi 分扇结果。

图5 voronoi 分扇结果

3 算例分析

谱聚类算法的构图以及切图思想可以很好地与扇区划分的数学模型相匹配，是一种专门解决带有权重的无向图切割问题的方法，其在处理稀疏矩阵以及高维度数据方面的优势，使得谱聚类算法很适合用来解决扇区划分问题。相较应用于扇区划分中传统的聚类方法，该方法有利于在扇区划分模型中加入对管制员的协调工作负荷的考量，有利于不同扇区间的流量均衡，避免了大协调移交量的出现。本文提出的谱聚类算法执行划设的时间在15 s 左右，算法的高效满足了动态扇区划设的实时性需求。用该方法，以太原武宿机场为例，进行管制空域的扇区划设，并基于TAAM 软件，进行仿真验证。

3.1 扇区划分

选取该地区某日上午7：00～12：00 的103 架航空器的历史运行数据以及空域结构数据，利用matlab 软件绘图，将航迹数据投射在地图上，得到空域内关键点和所有航空器运行的点迹，如图6 所示。

根据1.1 节画出空域示意图，结合空域的边界以及航路结构，建立关键点和航路结构的无向图图论模型，得到空域结构信息；按照1.2、1.3 节中提出的方法进行数据处理，对航空器点迹数据进行插值、检测得到空域中的动态流量信息，对关键点位置信息进行运算，得到空域中的静态地理信息；并根据1.4 节的式（7），对空域内关键点之间的关系进行描述，即动态信息与静态信息的整合，得到权重矩阵W；再根据2.2 节的方法构造拉普拉斯矩阵并对其标准化，按照谱聚类切图的思想对关键点进行聚类，最后通过生成voronoi 图将分扇结果呈现出来。

此时获得的扇区边界线还较为曲折，考虑到扇区边界的规则性，为了避免航空器重复进入同一扇区的情况，对于连接不同扇区的航段，取其中点依次相连，在voronoi 图基础上进行几何修正，结合专家定性分析，适度调整边界的走向，然后得到分扇结果。图9 为进行几何修正后的最终分扇结果，修正后的扇区边界显然较未修正的更清晰、更有利于扇区间的协调移交工作。

图9 最终分扇结果

3.2 结果分析

按照本文提出的方法，当将空域分为两个扇区时，关键点4、5、6 和9 属于同一个扇区，关键点1，2，3，7，8，10 和11 属于另一个扇区，此时总协调负荷小，两个扇区的监视负荷的差异不大，且扇区边界与空域中航路结构不会造成冲突，结构合理。当将空域分为3 个扇区时，扇区间监视负荷的差异与协调负荷均最大，不能将其作为管制扇区划设的方案，分析出现这种情况的原因可能是当前太原地区的空中交通流量还不是很高，两个扇区就能满足其空中交通流量的需求，分为3 个扇区反而会造成管制资源的浪费。

表1 为3 种管制扇区划设方案下对空中交通量的统计结果对比。

表1 分扇结果对比

目前管制扇区的划设虽然不同扇区的监视负荷相同，但由图8 可以看出，其存在关键点到扇区边界距离过小的情况，易导致关键点冲突解决工作负荷和移交工作负荷增加，且关键点5、6 之间的航段上存在扇区边界点，当航空器由关键点5 飞至关键点6 时，存在管制责任不明确的情况，容易造成管制过程中扇区之间频繁移交，增添额外的协调工作负荷，即空域内航路与扇区边界存在结构冲突，不符合管制扇区划设的实际需求。

图8 太原分扇示意图

可见在当前的流量下，按照本文的方法将空域分为如图9 的两个扇区时，管制员的工作负荷与空域结构都比目前划设的扇区更为合理；若日后流量增大，需要进行参数调整，同时考虑划设更多的管制扇区。

3.3 TAAM 仿真

全空域与机场建模工具软件TAAM（Total Airspace and Airport Modeller）是一个从机位到机位的快速仿真工具，可以对空中交通管理过程进行仿真。将太原武宿机场的基本信息、目前扇区边界以及通过本文方法得到的扇区边界输入TAAM 中，建立空域仿真模型，以同一天的航班时刻表为基础进行仿真验证，TAAM 输出的过扇架次、协调负荷、总工作负荷以及平均过扇时间的仿真结果如表2所示。由表2 可知，利用本文提出的扇区划设的方法将太原终端区空域分成两个扇区时，得到的过扇架次、扇区内管制员协调负荷以及总的工作负荷相较于其他两种情况都更加均衡；其中，仿真得到的过扇架次和协调负荷，明显优于目前划设的管制扇区，虽然平均过扇时间相差接近60 s，可能由此带来管制员监视负荷的差异，但反映在管制员总工作负荷中差异不大。本文进行的管制扇区划分结果与仿真结果一致，说明模型是有效的。

表2 TAAM 仿真结果对比

4 结论

从管制空域的航路网络结构图出发，提出空域顶点间动态静态双联系的计算方法，构建空域的无向图模型，并利用谱聚类切图的思想建立了管制扇区划设的数学模型，再利用谱聚类算法进行求解，得到扇区间流量更为均衡、协调工作负荷尽量小的结果，同时扇区边界布局合理，满足管制扇区划设的要求。进行实例分析并结合软件仿真验证本文提出方法的有效性，将结果与当前存在的扇区进行对比分析，验证了基于谱聚类算法进行扇区划分方法的合理性和高效性。对基于谱聚类的管制扇区划设的研究，下一步将利用谱聚类建模的思想，建立最优化问题，采用智能算法进行解算。