HLA中数据分发管理的探究(2)

·                 if   (R_i 是订购域)

·                 {

·                     if (P_i点是R_i的下界点)

·                         从 Subscriptionsetafter 中移去R_i

·                     else

·                         把R_i插入到Subscriptionsetbefore中

·                 }

·                 else (R_i是更新域)

·                 {

·                     if(P_i点是R_i的下界点)

·                          则Subscriptionsetbefore中的所有域均不与R_i交互

·                      else

·                          则Subscriptionsetafter中的所有域均不与R_i交互

·                 }

·             }

    可以对基于排序的算法进行一些有效的改进，例如可以用二进制向量来代替当前定购域集合，这样可以极大的降低每个更新域的匹配操作复杂度^[3]。此算法的一个显著特性是其性能没有随着重叠率及限域数目的变化而显著变化。而且，在重叠率不是特别低、区域内所含限域数目不是特别多时其性能较其他算法而言是最优的^[3]。重叠率很低时，网格划分法要优于排序的算法；而当重叠率很高且区域内含有的限域数目很大时，基于区域的算法的性能就会优于排序算法^[2]。

    边界区域 (Bounding Boxes)：此方法是计算每个域的边界区域是否有重叠，如果交互为空则无须再计算边界框内的域的重叠，反之，再在边界框区域内重新计算域间的重叠情况。暂时连续性 (Temporal Coherence)：这一规则充分利用了在许多仿真中事物是逐渐变化的规则，即在仿真中两个相邻时间状态下很多区域并不会有明显的移动^[2]。从而进一步减少区域匹配的次数。

    DDM中最显著的属性是域的数量情况。但之前所分析的各种算法和一些启发式规则的效率随着区域在路径空间中的不同的分布有较大的变化，所以必须在给定的路径空间中更准确地定义域的分布情况。有两个首要的因素需要考虑，首先是重叠率（overlapping rate）：描述了域间重叠的可能性，是一个影响DDM算法效率的重要因素，定义为：

    其次是每个区域内的限域的数目，因为DDM关心的是区域间的重叠而不是限域间的重叠情况。在实际情况下当面对大量的限域时，在整个空间中使用平均的重叠率是不现实的，很有可能在同一路径空间中存在重叠率高的区域，中等的区域以及重叠率很低的区域，且这些特性都是动态变化的值，DDM具体算法的选取需要计算和跟踪这些重要的属性。有两种方法可供选取：第一，首先把路径空间做初步的划分，当然为了达到某一局部重叠率的要求可以嵌套划分一直达到某一规定重叠率值或划分的网格数达到某要求为止。第二，用排序的方法。检测排序后的列表时就可以直接得到每个初始划分部分在此坐标方向上的局部重叠率情况，在每维上做同样的检测则可得到空间中的域是较平均分布的还是有聚集和稀疏的不均匀分布。

    重叠率的取值范围较大并且算法的选择不需要精确的重叠率值（重叠率接近某一阈值时，选取不同的算法对DDM性能无明显影响），因此在大多数情况下对其作粗略估计即可。在不知道待解问题的具体特性时，一般选取基于排序的DDM算法^[2]，通常情况下此算法效率较高并且除匹配操作以外对问题分析和预操作的复杂度（O( )）较低^[3]。除此之外，一些启发式规则也可应用到系统中来，但需要一种机制来针对路径空间中的不同区域优选具体的算法。细划分的基于网格的算法适用于限域重叠率较低（重叠率为0.01或者更低）的情况 ^[2]。基于区域的算法则适用于重叠率较高的情况。其他情况通常选取基于排序的DDM算法。但是当限域在路径空间中移动时，问题的属性会发生变化，可以在平均重叠率超过某一阈值时重新计算划分并在局部范围内重新选区DDM算法。另外，对于路径空间内区域重叠率不是均匀分布的情况可以通过多种DDM算法的综合使用从一定程度上得以解决。如：先对路径空间作一简单的划分，再针对每个网格内的具体情况选取适当的DDM算法，则可以达到更好的数据过滤的效果。

    高层体系结构HLA中的DDM适应大规模复杂仿真系统的要求实现了进一步的数据过滤，满足了系统可扩缩性的要求。本文探讨了目前几种流行的DDM数据过滤机制并用一些新的标准（如overlaprate等）对其进行了比较，分析了如何利用这些标准动态地选出DDM适应性算法，对于DDM最优算法的研究具有一定的积极意义。

[1] DMSO. High Level Architecture Interface Specification Ver 3,2 [EB/OL]. http://www.dmso.mil/

[2] RACZY C., YU J., TAN G., TAY S. C. ,and AYANI R. Adaptive data distribution management for HLA RTI. In Proceedings of 2002 European Simulation Interoperability Workshop (London, UK). June 2002

[3] Come Raczy, Gary S. H. Tan, Jun Yu. A sort-based DDM matching algorithm for HLA. ACM Trans. Model. Comput. Simul. 15(1): 14-38 (2005)

[4] Azzedine Boukerche, Kaiyuan Lu: Optimized Dynamic Grid-Based DDM Protocol for Large-Scale Distributed Simulation Systems. IPDPS 2005

[5] Petty M. D. and K. L. Morse. The Computational Complexity of the High Level Architecture Data Distribution Management Matching and Connecting Processes, Simulation Modeling Practice and Theory, Accepted 2003

[6] 张霞，黄莎白.高层体系结构中DDM实现方法的研究.系统仿真学报，2003，15：670~673

ZHANG Xia, HUANG Sha-bai. Research of DDM in High Level Architecture. Journal of System Simulation 2003,15,670~673

[7] 张霞，黄莎白.HLA中基于Agent的层次过滤机制.计算机仿真

[8]  张霞，黄莎白.一种混合的动态DDM实现方法.计算机工程