《空管仿真中关于确定飞机位置的数据结构的研究》由会员分享，可在线阅读，更多相关《空管仿真中关于确定飞机位置的数据结构的研究（5页珍藏版）》请在金锄头文库上搜索。
1、空管仿真中关于确定飞机位置的数据结构的研究 刘科科 李春锦 （北京航空航天大学 空中交通管制中心 100083） 摘 要摘 要 本文通过对空中交通管理仿真中几种可用于确定飞机位置的数据结构的比较，选择 了一种最适合应用于空中交通管理仿真的数据结构线性四叉树结构。同时为了便于仿真 计算，本文还结合仿真中飞机位置的变化给出了对应的线性四叉树的构造、更新和删除结点 的算法。 关键字关键字 线性四叉树 指针四叉树 线性 PR 四叉树 在对空中交通管理仿真的过程中，模拟一个与复杂的数据链接网络相连的空域环境需 要处理大量的数据。为了减少计算的数据量，需要设计一个适当的数据结构和有效的算法。 这种数据结构
2、应能使飞机在空中和地面 ADS-B(自动监视广播)的控制范围之内。同时，这 种数据结构还必须满足空中交通管制规则。本文将线性四叉树结构及其相应的算法用于空 中交通管理仿真系统中，用以确定飞机的位置，提高仿真过程中的计算效率。 1 数据结构的选择 1 数据结构的选择 理想的数据结构是将自然地理数据与具体的数据结构的形式相联系。飞机的位置数据 可以用一些基本的数据结构来进行组织，如队列、链表等。但这些简单的数据结构不能满 足空中交通管理仿真的要求，因此这些数据结构都不予以考虑。可用于确定飞机地理位置 的标准数据结构主要有二叉树、四叉树和八叉树。相比较而言，四叉树结构最适合应用于 确定飞机的地理位置
3、。 四叉树是一种可以用来描述区域等级的数据结构。它主要基于对区域进行分解，可以 利用二维地表表示法将地面分解到合适的大小。这样任何地理地区都可以被重复分解，直 到达到所需的等级。一般最多可将地理区域分解到 1012 个等级。在每个等级的区域中， 最多允许的飞机数目可通过计算每个区域中能够容纳代表飞机最小水平间隔的圆形区域的 数目来加以近似。如图 1 所示： 尽管二叉树也能用于代表地理区域，但会产生更多的等级来表示同一区域，因而不是 很适合。而八叉树则是分解的区域数目太多。方程(1)、(2)给出了四叉树与八叉树区域数 目的计算方法，L 表示分解的等级。可以看到表示同样的区域，十级的八叉树所分解的
4、区 域数目是四叉树所分解的区域数的 1024 倍。 4 L N= 四叉树 (1) 8 L N= 八叉树 (2) 2 四叉树选择 2 四叉树选择 四叉树作为地理和空间信息的表示方法应用的非常广泛。机器人运动时障碍物位置的 确定和三维图形的有效存取方面都应用了四叉树。图 2 描绘了一个简单的四叉树的结构。 四叉树由三类结点组成：双亲结点、叶子结点、空结点。每个双亲结点必须包含四个子结 点，子结点要么是叶子结点，要么是空结点。每个叶子结点与特定的地理区域相联系，并 包含了这个区域的相关飞行数据，如飞机位置等。每个空结点同样与特定的地理区域相联 系，只是没有存储任何数据。总的结点数可利用方程(3)来计
5、算。L 表示分解的等级数。 (3) 1 4 L L i n = = 常用的四叉树主要有指针四叉树和线性四叉树。指针四叉树中每个结点包含了双亲结 点和四个孩子结点的指针。在遍历四叉树时，可以利用结点指针，通过先遍历源结点再遍 历儿子结点的方法来遍历整个树。指针四叉树的优点就在于它在遍历树的过程中不需要其 他的索引标识。线性四叉树将所有的叶子结点存储在一个索引数组中。每个结点在索引数 组中的序号可由方程(4)、 (5)来确定。 其中 C I表示子结点的序号， P I表示双亲结点的序号。 C (4) 1,4 P IInn=+ (4) ()/4 1,4 PC IInn= (5) 在指针四叉树中，由于每
6、个结点保存了五个结点的指针：四个子结点和一个双亲结点， 因此需要增加存储空间。但是由于在用于空中交通管制仿真的稀疏四叉树中，仅有一小部 分结点包含数据，因此指针四叉树比线性四叉树需要的存储空间要小得多。例如，在一个 分为 10 级的包含 5000 个结点的四叉树中，假定每个叶子结点需要 16B 的存储空间，每个 指针需要 4B 的空间。指针四叉树的大小由 5000 个指针叶子结点(36B)构成。线性四叉树的 大小由 5000 个叶子结点(16B)加上索引数组的大小。索引数组的大小依赖于四叉树的等级 (由方程(3)来决定)。加上在每个等级上还有很多空结点，显然线性树比指针树需要更多的 存储空间。
7、但是，线性四叉树在通过索引数组来遍历四叉树上能提供一些方便，在访问叶 子结点时比指针四叉树要快，而且方便计算结点的位置。例如：访问一个十级的结点，对 指针四叉树来说，需要逐级查找。而对线性四叉树则只需两步。首先计算出结点的索引号， 然后按照索引号访问就可以了。 在空中交通管制仿真应用中，显然指针四叉树能减少存储空间，但是由于线性四叉树 的大小在当前桌面电脑允许的存储能力内。考虑到计算效率对仿真性能的影响，因此使用 线性四叉树来进行仿真。 3 线性四叉树实现 3 线性四叉树实现 线性四叉树根据四叉树所代表的区域作进一步的细分， 可分为区域四叉树和点四叉树。 区域四叉树如图 1 所示，区域的大小依
8、赖于四叉树所分的等级而不依赖于飞机的位置。点 四叉树如图 3 所示，它的大小由飞机位置决定而与四叉树所分的等级无关。 采用这些结构的目的在于能快速的确定飞机在给定区域内的位置。考虑到飞机的数目 和相对位置是变化的，最好的方法是采用 PR(Point-Region)四叉树。它是一种用于专门存 储点数据的特殊形式的区域四叉树。在 PR 四叉树中，每个子树所代表的地理区域都是父树 所代表区域的 1/4，因此利用 PR 树来进行计算非常方便。而且 PR 树的结构不受结点加减 的限制，这与在仿真过程中飞机在某个区域的进出是随机的相一致。 在仿真中采用的是线性 PR 四叉树。这种四叉树由两部分组成，索引数
9、组和叶子结点 记录。索引数组是一个可变数组，如果是叶子结点，那么索引数组记录的是一个包含了叶 子结点信息的指针；如果是双亲结点和空结点则是一个空的记录。这样索引数组所需的存 储空间将大大减少。 每架飞机由一个叶子结点记录来表示。叶子结点记录包含了飞机状态数组指针和控制 状态数组指针，此外还包含了一个与同一四叉树中所有飞机记录组成的链表相连的指针。 与飞机状态数组相联系，使在更新四叉树时不需进行额外的计算。由于所采用的四叉树是 PR 四叉树，仅仅较低等级的叶子结点包含多架飞机，也就是说，所有等级高的叶子结点只 包含一架飞机，因为如果有另外一架飞机进入的话，将该区域进行下一级的分解。这些叶 子结点
10、记录保存在一个链表中，它只能通过索引数组来进行访问。 4 基本算法 4 基本算法 由于四叉树是一个动态的数据结构，飞机在四叉树中是随机的添加和删除的，而且飞 机从一个区域进入另一个区域也是随机的。因此建立一个计算效率较高的基本算法来构造 和配置四叉树就显得非常重要。 4.1 线性 PR 四叉树的构造和新结点的插入 线性 PR 四叉树将在仿真的初始化阶段加以构造。当一个新的飞机加入到四叉树内时， 将动态分配一个新的叶子结点记录，相应的四叉树索引数组中的索引记录将转换成一个叶 子结点，同时产生一个新的指向叶子结点记录的指针。根据飞机所在区域的位置，通过遍 历索引数组查找对应区域的叶子结点或空结点的
11、索引序号。如果结点是空的，则将索引记 录转换成叶子结点并产生一个新的指针指向该结点。 如果飞机所在区域所对应的结点已经被一个叶子结点所占据，那么需要将这个叶子结 点转换成一个双亲结点，然后将叶子结点所在的区域加以扩展。例如，一个位于区域 9 的 飞机加入到四叉树中，如图 4 所示。新的叶子结点遍历到结点 2 时。由于结点 2 是一个叶 子结点，通过扩展区域 2，这个叶子结点转换成一个双亲结点，先前的叶子结点移到下一 级的区域 10。然后通过遍历结点 2 的下一级结点，新的叶子结点被设置在位于区域 9 的空 结点处。但是，如果原先的在区域 2 的叶子结点后来位于区域 9，那么将进行进一步扩展 和
12、重置结点，直到到达仿真允许划分区域的最高等级。 4.2 线性 PR 四叉树的更新 一旦四叉树被创建以后，由于飞机的运动，它必须进行周期性的更新，使四叉树能准 确代表飞机的位置。更新的频率由使用四叉树实现相应功能所需的精度来决定。例如为了 与当前的 ATC 雷达精度相一致，四叉树需要每 12 秒更新一次。然而如果飞机较少而且飞行 较慢，在不影响 ATC 和数据链接功能的情况下，更新的速度可以相应的减慢。 更新四叉树包括三个阶段：首先查找四叉树中哪些飞机已经飞离其所在区域的边界； 然后删除发生改变的飞机所对应的四叉树索引数组中的叶子结点的指针，并将指针对应的 叶子结点记录暂时存放在一个链表中；最后
13、将这个链表中的所有飞机记录根据更新后飞机 所在位置重新插入到四叉树中。在整个过程中，实际的叶子结点记录并没有发生改变，仅 仅指向这些记录的指针发生了改变。 4.3 删除飞机记录 为了减小内存的占用量，将在飞机进入仿真时给树结点分配空间，在飞机移出仿真时 释放内存空间。因此，由四叉树结点所代表的飞机将在其到达目的地或仿真结束时从四叉 树中移出。由于飞机可能在任何时候移出，因此在将飞机从四叉树中移出之前应先更新四 叉树以使所有的飞机在合适的区域内。 将飞机从四叉树中移出首先应确定飞机在四叉树中的位置。当找到飞机以后，相应的 四叉树结点的内存将被释放，将四叉树索引队列中的叶子结点指针设为 Null，
14、相应的叶子 结点记录设为空结点。 但是，如果要移出的飞机所代表的叶子结点记录仅仅有一个兄弟结点。那么这个兄弟 结点将向上移动一级，直到它不是唯一的子结点为止。例如，在图 4 中，如果有一架位于 区域 9 的飞机将被移出，这样结点 10 将成为唯一的子结点，这时结点 10 将向上移动一级， 索引记录中的第 10 个点将转成空结点，索引记录第 2 个结点将转换成一个叶子结点，指向 剩下的飞机的叶子结点记录。 5 小结 5 小结 本文为在空中交通管理仿真中确定飞机的实时位置提出了线性四叉树的数据结构，并 根据仿真过程中飞机位置不断发生变化的特点设计了相应的线性四叉树结点的构造、更新 和删除的算法。为
15、在仿真过程中监控飞机运动，实现飞机间的数据通讯提供了方便。同时 还大大简化了仿真中数据的计算量，提高了计算效率。 参考文献 参考文献 1 崔宏伟等 空间数据结构M 北京：中国科学技术出版社，1995 2 Samet,H Design and Analysis of Spacial Data StructuresJ,College Park ,Maryland,2002 3 Samet,Hanan. The design and analysis of spatial data structuresM Reading, Mass. : Addison-wesley,c1990. 4 Samet, H. Neighbor Finding Techniques for Images Represented by QuadtreesJ.Computer Graphics and Image Processing, 1982 18(1):37-57
