基于剖分网格的空域冲突检测方法*

刘智奇 南 英 谢如恒

（1.南京航空航天大学 南京 211106）（2.空中交通管理系统与技术国家重点实验室 南京 211106）

1 引言

随着现代空中交通运输业的发展，空管系统面临的压力随之增大。空域冲突检测功能虽然在空管系统中发挥着重要作用，但其性能却有待提升。

对于空域冲突检测的研究开始于20世纪40年代～50年代，国内外学者提出了多种相关模型和算法，目前使用最广泛的是几何浮点计算，即通过每个空域使用计划所确定空域的边进行交叉判定[1～6]，该方法虽然可以准确计算得到空域冲突及其范围，但对于大规模的冲突检测存在着计算量大、算法复杂度高、计算时间长、求解效率低下等问题。

本文基于剖分网格对需要进行检测的空域进行网格化表征，使用含有空域网格表征信息的多叉树对不同使用计划所涉及的空域进行冲突检测。仿真结果表明，在求解大规模空域使用计划冲突的问题上，本文提出的方法能提高较检测效率、缩短计算时间。

2 几何空域的网格剖分

2.1 网格表征方法及应用现状

地球剖分网格（Earth Tessellation Grid，ETG）是一种可以无限细分，但又不改变形状的地球拟合格网，当细分到一定程度时，可以达到模拟地球的目的，而其离散性、层次性和全球连续性特征，恰好符合计算机对数据离散化处理的要求[7-8]。军用网格参考系统（Military Grid Reference System，MGRS）于20世纪40年代由美军根据欧洲网格化地图修改得到[9～10]，该系统可在经纬度坐标与网格坐标之间建立对应关系，简化士兵之间的位置报告和协调；全球区域参考系统（Global Area Reference Systems，GARS）由美国地理空间情报局于2006年提出，其网格采用等经纬度网格剖分方法被划分为不同大小的3个层级，主要用于联合作战中地理位置相关的表述[11～14]。

北京大学程承旗教授团队提出的GeoSOT-3D地球剖分框架以其全球性、层次性、多尺度性等特性吸引了国内外学者的关注，该框架在空间对象表达上得到了应用[15]；空域网格模型也已经在某些空管领域得到了应用，如空域调度、流量管控、气象影响预估、无人机编队等研究领域[16～19]，但目前在空域冲突的检测及确定方面还没有相应的研究。

2.2 空域网格剖分编码方法

第一步，全球空域网格化建模。利用正轴圆柱等距离投影，将地表空间投影到一矩形平面，投影后经纬线形成两组相互垂直的平行直线。然后剖分空域，在经纬方向将平面逐级按照8*8规格的六十四等分进行剖分，形成各层级相互包容且无缝隙的经纬投影平面网格，最高剖分10个层级；同样地，在高度方向按八等分逐级剖分，最高剖分9个层级，且高度方向第一层级高度上不剖分；最后将平面剖分和高度剖分的网格相组合形成网格化的空域结构，如图1所示为一空域的剖分效果。

图1 全球网格剖分示意图（局部）

第二步，空域网格数字编码。编码由经纬方向和高度方向编码组成。经纬方向采用双位八进制编码，同时按层级由低到高（网格尺寸由大到小）嵌套编码获得第1～10层级编码；高度方向则按高度由低到高进行编码，但高度第1层不编码，也采用八进制得到第2～10层级高度编码；最后将经纬投和高度编码按对应层级合形成空域网格的三维编码。这一过程的前两层编码方法如图2所示。

图2 第一到第二层级网格经纬及高度编码示意图

3 利用编码多叉树进行冲突检测

3.1 多叉树的构建

构建空域网格编码多叉树的过程如下。

第一步，根据空域下底面任意一点经纬高个坐标，计算与之存在交集的第1层级网格，并将该网格在经纬方向扩展，获得全部与该空域下底面存在交集的第1层级网格，并生成这些第1层级网格的经纬编码，然后以该空域ID或编码为根节点、存在交集的第1层级经纬编码为子节点构建空域网格表征多叉树。

第二步，将第1层级网格向下一层级分解，获取第2层级与空域底部存在交集的网格并生成第2层级经纬编码，同时在高度方向扩展并生成第2层级高度编码。依此逐层分解至目标层级（例如，目标层级经纬方向分解到第10层级，则高度网格也分解至第10层级）。最后将由低到高层级的经纬和高度编码组合，形成各子节点并插入网格编码多叉树对应的节点。全部剖分过程及构造的的多叉树结构如图3所示。

图3 几何空域的网格表征

从图中可以看出，第1层级由于不进行高度网格剖分，因此编码中只含经纬网格编码，第2层和更高层级网格编码则由经纬和高度两种编码结合而成。第2层级第一个节点网格编码中的xy2即表示经纬方向第2层级编码，其后数字码为经纬方向网格数字编码；编码z1表示高度方向第1层级编码，其后数字码为高度方向网格数字编码。对于更高层级网格编码则同理进行，同时相应编码也按照规则写入上述多叉树更深层次的子结点中，最终可将空域完整表示为图中结构。

3.2 多叉树检测原理

由于空域已经通过空间网格及其编码构成的多叉树进行表示，因此可将检测原理表示在图4中。不难看出这种检测结构具有如下两个特点。

图4 多叉树冲突检测原理

1）实际的空域冲突区可以用多个空域中编码相同的网格来表示，其显然就是这些编码所代表的空间网格集合；

2）虽然网格有层级和尺寸跨度的大小之分，但是对于存在冲突的空域而言，若某一层级的网格存在多空域共用现象，则包含该网格的低层级网格也一定存在多空域共用现象。

图中多叉树的根层级（矩形表示）代表一待检测空域，空心节点表示该空域划分的网格中所在层级存在与其他空域冲突的网格，实心节点则不与其他空域冲突，按照上述特点，则显然实心节点下的深层节点中也一定存在实心节点。因此，从低层级向高层级遍历，且遇到不存在冲突的网格（实心节点）则停止向高级遍历，这样即可在检测中省去不必要的遍历步骤。

3.3 冲突检测算法

应用以上原理，将基于网格的空域冲突检测算法流程列出如图5所示，接下来对该过程进行详细说明。

图5 冲突检测方法流程图

一般空域冲突检测需同时考虑时间和空间上的冲突，冲突检测算法首先对待检测的两空域进行时间排斥检测。显然若在占用时间上无重叠，则两空域即使存在空间交集也不存在冲突可能性，因此不发生空域冲突；再对两空域进行空间排斥检测，这需要对比两空域的经纬高边界，若这三个维度中存在不重叠的维度，则空域也不可能存在冲突区。

如果以上情况均未发生，则利用网格编码多叉树结构计算冲突空域。获取两待检测空域的第1层级经纬编码并求交集，然后在空域编码多叉树中分别获取两空域第1层级交集网格下的第2层级经纬编码，计算下一层级交集网格经纬编码并依此直至获取最高层级的交集网格经纬编码。以相同方法逐级求得各交集网格的高度编码，并将交集网格经纬和高度编码组合成网格编码，则网格编码所对应的网格集合就代表了空域的冲突区域。

4 仿真分析

通过使用不同检测方法，对同一区域内总数不同的空域执行冲突检测仿真，分析在不同空域总数以及不同冲突空域数量条件下的算法检测时长，验证基于剖分网格的冲突检测算法的计算效率。

首先构建实验条件与场景，建立一系列规模大且位置、形状都具有随机性的多边形空域，显然这些空域会存在冲突。以此为基础多次生成随机空域，其总数依次设定为100，150，200，……，500，每次分别使用传统方法和本文方法进行冲突检测、最后分析冲突检测信息及每种方法的运行耗时。

4.1 传统检测算法

传统空域冲突检测算法输出的冲突空域显示如图6所示，图中对应总空域数量为100个，同时将空域冲突信息输出在图中重叠区域。表1给出了传统算法仿真得出的冲突检测信息和计算时间。

图6 传统冲突检测方法输出的冲突结果

表1 传统方法空域冲突计算耗时

由表1可知，随着需要分析的空域总数增加，与之相对应的可能存在冲突的空域数量就会增多，而冲突检测算法运行所需要的时间也就会不断增长。

4.2 基于剖分网格的检测算法

基于剖分网格的空域冲突检测算法输出的冲突空域如图7所示，图中对应总空域数量为100个，该算法输出的检测信息和计算时间如表2所示。

图7 基于剖分网格检测法输出冲突结果

表2 基于剖分网格法对空域冲突的计算时长

由图6和图7对比可知，基于剖分网格的冲突检测算法与传统算法对相同的空域冲突情况检测结果一致，因此本文方法能够同样有效地进行空域冲突检测。

4.3 算法效率对比

将本文的检测方法耗时数据与传统方法进行对比，可以得到本文方法相对于传统冲突检测算法计算消耗时间的缩短比例，如表3所示。

表3 不同方法冲突计算耗时对比结果

图8所示为传统的空域冲突检测算法和本文算法的检测时间变化情况。从图中可以看出，随着每次实验需要检测的空域数量增加，两种方法计算所需时间都有所增加，但本文算法耗时明显少于传统算法，且其随空域总数增长而产生的计算时长的增速也明显小于传统的空域冲突检测算法。

图8 不同空域总数下两种方法检测时长结果

图9所示为本文算法相对于传统冲突检测算法计算时长节省比例随空域总数变化的特性图，从图中可以看到，尽管每次实验中需要检测的空域数在不断增加，但是本文方法的计算时长相对传统方法的节省比例一直能够保持在不低于50%的水平。也就是说，基于剖分网格的冲突检测法效率要明显高于传统检测算法。

图9 剖分网格检测方法缩短计算时长情况

由上述仿真分析结果可知，本文提出的基于地球剖分网格的空域冲突检测算法能够有效检测空间内存在冲突的空域，并且该方法在计得到与传统算法相同结果的情况下，能够将原来的计算时长缩短50%以上，大大提高了大规模空域冲突的检测效率。这主要是因为在考察的区域已经确定时，该区域对应的网格剖分方法及其规模是确定的，因此新方法的多叉树遍历规模和上限就可以确定，且不随区域内总的检测空域数增多而变化；但对传统方法而言，由于判断方法的根本是依据每一块空域的几何参数依次计算，因此实际运算量会随区域内总的检测空域数增多而增大，综前所述，新的判断方法避免了空域数量规模对检测过程的影响。

5 结语

本文基于地球剖分网格模型对待检区域的冲突空域进行描述并利用多叉树结构计算冲突空域。由此构建的新的空域冲突检测方法与传统的空域检测方法同时进行试验，得到两种方法对于空域冲突检测的计算时间。根据实验结果分析得到如下结论。

1）对于相同数量的若干空域进行冲突检测，基于剖分网格的冲突检测方法可以得到和传统的几何浮点计算方法一样的空域冲突检测结果。

2）利用传统方法和本文提出的基于剖分网格的检测方法对同样的冲突产生区域进行检测可以发现，本文提出的新方法相对于传统检测方法的计算时长可缩短50%以上。显然，该方法在计算性能上优于传统方法。