基于飞行冲突网络最优支配集的冲突调配策略_吴明功.pdf

http:/DOI:10.13700/j.bh.1001-5965.2021.0233基于飞行冲突网络最优支配集的冲突调配策略吴明功1，2，毕可心1，2，温祥西1，2，*，孙继昆3(1.空军工程大学空管领航学院，西安710051；2.国家空管防相撞技术重点实验室，西安710051；3.中国人民解放军 93735 部队，天津301799)摘要：针对空中交通流量逐年上升、管制压力增大、飞行冲突难调配的问题，以航空器为节点，基于航空器之间的速度障碍关系建立飞行冲突网络。定义最优支配集的概念，通过移除飞行冲突网络的最优支配集节点，快速消解网络中的冲突，降低网络的复杂性。在使用粒子群（PSO）算法对网络最优支配集进行求解的过程中，引入免疫机制，设置节点和连边 2 种类型的抗原，保证对关键航空器和高风险冲突的优先调配。实验仿真表明：所提冲突调配策略相较于传统方法能够快速识别网络中的关键航空器节点，并对高风险的冲突连边具有较好的灵敏性，可为管制员和管制系统提供更加准确、可靠的信息和建议，在宏观上辅助进行飞行冲突的调配。关键词：复杂网络；最优支配集；冲突调配；粒子群算法；速度障碍法中图分类号：V355；O231.5文献标志码：A文章编号：1005-5965（2023）02-0242-12近年来，中国空中交通行业取得了空前的发展。到 2019 年底，中国共建成航路、航线 992 条，总里程数共计 234509km，超过 3 条以上航路交汇的航路点个数有 527 个1。与此同时，中国的空中交通系统变得越来越复杂，航空器在运行过程中面临的飞行冲突增多，空中交通管制压力巨大。采取有效的措施对航空器之间的飞行冲突进行调配，将能够缓解这一压力，保证空中交通运行的安全和顺畅性，并促进航空业的进一步发展。飞行冲突的相关研究一般可分为 2 种：一种是宏观上进行的冲突调配，另一种是针对具体问题的局部冲突解脱。宏观上的冲突调配关注空域整体的运行情况，该方法能够基于当前的空中态势，为管制员提供合理、可行的飞行冲突调配建议；而局部冲突解脱则面向具体冲突，对于既定类型的冲突事件，通过几何、概率、控制和博弈等理论分析，为航空器提供合理的机动意见2-5。本文主要研究宏观上的冲突调配。在这方面的研究中，Huang 等6提出了一种飞机流在航路交叉口的紧凑结构，以解决航空器流在交汇时的冲突问题，该方法能够保证更多的飞机安全通过固定区域，提高航路交汇处的空域容量；Hong 等7将冲突调配表述为航空器机动约束下的混合整数线性规划问题，采用 2 层结构解决飞机之间的冲突，避免了飞机之间的冲突，并保证飞机顺利过渡到相邻空域；Valenzuela 和 Rivas8提出了一种基于飞机意图参数化的冲突检测与解决方法，将冲突解决问题表述为有约束的参数优化问题，并据此进行调配；Cafieri 和 Rey9采用混合整数非线性规划进行建模，以最大限度地解决冲突的数量或保证无冲突飞机数量最大为目标，通过检测两机之间的冲突进行调配，使冲突模型得以减小，同时提高了计算的效率。航空器之间的冲突关系是复杂的、非线性的。近年来，学者们通过复杂网络理论分析和解决航空收稿日期：2021-05-07；录用日期：2021-06-11；网络出版时间：2021-07-1409：38网络出版地址： J.北京航空航天大学学报，2023，49（2）：242-253.WU M G，BI K X，WEN X X，et al.Conflict resolution strategy based on optimal dominating set of flight conflict networksJ.Journal ofBeijing University of Aeronautics and Astronautics，2023，49（2）：242-253（in Chinese）.2023年2月北京航空航天大学学报February2023第49卷第2期JournalofBeijingUniversityofAeronauticsandAstronauticsVol.49No.2器之间的冲突问题。王红勇等10根据航空器之间的迫近效应确定航空器集合的内禀复杂性，并依此构建复杂网络模型；吴明功等11以航空器为网络节点、航空器之间的机载防相撞系统（airbornecollisionavoidancesystem,ACAS）通信为连边建立飞行状态网络，通过对网络的拓扑指标分析找到空域中关键的航空器节点，为管制员提供飞行冲突调配方案；汤俊等12将复杂网络用于无人机集群的冲突解脱，通过边缘权重确定关键无人机，并使其朝着能够使网络鲁棒性降低的方向实施避撞。以上方法在构建网络连边时只考虑了航空器的位置信息，不能准确反映航空器之间的冲突关系。速度障碍法能将航空器的速度、航向和保护区信息结合起来，通过几何方法，提前预知飞行冲突13。本文使用速度障碍法判断航空器之间的冲突关系，构建冲突网络。冲突网络中，对航空器节点进行删除和调整，即对应实际中的飞行冲突调配，会对网络的结构和性能产生影响。通过对网络进行分析，找出调整后能快速降低空域复杂性的航空器，即关键节点，可以为管制员调配冲突提供宏观上的建议，将宏观上的冲突调配问题转化为冲突网络关键节点的识别问题。常用的复杂网络关键节点识别方法有度排序法、介数中心性或接近中心性排序法、K-shell 分解和 PageRank 法等14-16，这些方法对识别网络中的关键节点有较高的准确性。但在进行飞行冲突调配时，单纯的节点识别方法可能会忽略紧迫的飞行冲突连边，进而影响飞行安全，因此需要同时对网络中的关键节点和连边进行识别。李佳威等17将最小连通支配集（minimumconnecteddominatingset,MCDS）的概念用于复杂网络中，能同时识别网络中关键节点和连边，对研究网络抗毁性、构建骨干网络具有现实意义。但在实际的两机冲突中，管制员通常只需要调配其中一架航空器即可消解冲突，因此连通性在冲突调配问题中的意义是有限的。综上，本文提出了一种基于复杂网络最优支配集(optimaldominatingset,ODS)的冲突调配方案，通过最优性能指标优化飞行冲突网络支配集的结构，为管制员进行飞行冲突调配提供合理的建议。1飞行冲突网络G=(V,E,W)V=v1,v2,vnE=e1,e2,enW=w1,w2,wn飞行冲突网络是由航空器（节点）及航空器之间的冲突关系（连边）构成的复杂网络，表示为。其中，为网络中节点的集合，对应空域中的各个航空器；表示连边的集合，连边反映航空器之间的冲突关系；为网络边权的集合，连边的权值在飞行冲突网络中反映潜在冲突的紧迫程度。1.1连边规则Dl2DvDlDv飞行冲突网络的节点间构成连边，需要满足2 个条件：节点对应的航空器在位置上比较临近；通过速度障碍模型进行判定，满足速度障碍关系。如图 1 所示，在进行初次判定时，划定航空器的位置探测区为圆柱形区域，半径为，高为。取的值为 ACAS 通信应答距离 26km，的值为2 个高度层的高度 600m。当有航空器进入该区域时，需进行第二次判定。dldv航空器在运行时要求相互保持一定的垂直间隔或水平间隔，针对空中目标建立椭球形飞行保护区（见图 2），保护区的赤道半径 a=b=，极半径 c=。DlDv图1位置探测区Fig.1PositiondetectionareaBdldldv图2椭球形飞行保护区Fig.2Ellipsoidalflightprotectionzone(XB,YB,ZB)设航空器 B 的坐标为，则保护区椭球面的表达式为(xXB)2d2l+(yYB)2d2l+(zZB)2d2v=1（1）dldv当航空器间的垂直间隔大于 300m 时，不存在冲突，故取=10km，=300m。dlvAvBvrBvr=vAvB速度障碍法根据几何规则限定了目标在二维平面上潜在冲突的相对速度范围，当其相对于障碍物的速度处于该范围内时，判断其将会发生冲突。如图 3 所示，目标 A 和障碍物 B 之间的间隔为|AB|，障碍物 B 在平面上的安全保护区是以 B 为圆心、为半径的圆。目标 A 的速度为，障碍物 B 的速度为，A 相对 B 的速度为。过点 A 分别向两侧做切线，此时构成的区域称为速度障碍锥，当相对速度的方向在速度障碍锥内部时，认为 A 和 B 之间潜在冲突。第2期吴明功，等：基于飞行冲突网络最优支配集的冲突调配策略243vr=vAvBvr由于航空器运行的空域是三维空间，将速度障碍法拓展到三维，且保护区为椭球形的一般情况。如图 4 所示，相对速度可看作是航空器B 处于静止时，航空器 A 相对于航空器 B 的速度。当方向在三维速度障碍锥的角度范围之内时，说明若按照当前的运动状态不加以调配，航空器 A 将进入航空器 B 的飞行保护区，发生飞行冲突。vAvBvrBAdl图3速度障碍法Fig.3VelocityobstaclemethodvBvrvAAdldldvBC图4三维速度障碍模型Fig.43Dvelocityobstaclemodel(XA,YA,ZA)vr(vx,vy,vz)设航空器 A 的三维坐标为，的方向向量为，则根据三维直线的点向式，有xXAvx=yYAvy=zZAvz（2）(x1,y1,z1)(x2,y2,z2)vr AB 0vr联立式（1）和式（2），若方程组存在 2 个解，则直线和曲面存在 2 个交点 C1和 C2，其坐标分别为和；表示与位置向量的夹角，当同时满足，即时，的方向就在障碍锥内，2 个航空器之间潜在飞行冲突，判定节点对构成连边。cos =cos=vr AB|vr|AB（3）1.2网络边权tctc采用预计冲突时间 的负指数函数作为网络中节点间连边的权重。预计冲突时间 定义为：如果航空器保持原有的飞行状态不变，预计将发生冲突的时间。用模型中的参数表示为tc=|AC|vr（4）wij=exptc（5）wij式中：为节点 i 和节点 j 之间连边的权重；|AC|为航空器节点 A 和点 C 之间的距离，表示为|AC|=min|AC1|,|AC2|（6）vrlor其中：点 C1和点 C2为 A 在方向上直线与保护区椭球面的交点。tctctctc选取预计冲突时间 的负指数函数作为权值有以下优点：负指数函数在其定义域上为减函数，越长，权值越小，反映冲突强度较弱；在构成连边时，的取值都大于 0，故其负指数函数的值域为0,1，能够对权值起到单位化的作用；负指数函数斜率的绝对值随着自变量的减小逐渐增大，能够反映出潜在飞行冲突的紧迫程度在 减小的过程中变化激烈，这一特点与实际的冲突情况一致。如图 5 所示，有 6 架航空器运行在三维的空域中，1 号和 3 号航空器表示在上高度层内的航空器，其高度在图中表示为 0.3km，4 号和 6 号航空器表示在下一高度层的航空器，2 号和 5 号航空器表示处于高度层之间正在爬升或下降的航空器。从图 5中得到，1 号和 3 号航空器的潜在冲突数量为 2 个，2 号、4 号、5 号和 6 号航空器的潜在冲突数量为1 个。将航空器对在空域中的冲突关系抽象为网络，可得到其对应的飞行冲突网络。为便于表示和计算，用权值矩阵反映网络中节点和连边的关系，图 5 网络所对应的权值矩阵为W=00.2850.5710000.285000000.5710000.7450000000.726000.7450000000.726000500.14050z/km0.23040y/km30 x/km200.320101004231560.2850.5710.7450.726图5飞行冲突网络示意图Fig.5Schematicofflightcollisionnetwork2网络的最优支配集2.1支配集G=(V,E)S V支配集是图论中的概念，如图 6（a）所示。设存在无向图，其中，V 表示网络中节点的集合，E 表示连边的集合。在无向图 G 中，存在，244北 京 航 空 航 天 大 学 学 报2023年S#x V S，且对于，x 都与 S 中的