hla中数据分发管理的探究

1 / 8HLA 中数据分发管理的探究摘 要 HLA 已成为了现代分布式仿真应用的通用技术框架的核心，而作为其六大服务之一的数据分发管理则提供了有效的信息交互和传送机制以满足系统可扩缩性的要求。文章介绍了 HLA 中数据分发管理 DDM 的过滤原理；研究并分析了目前几种实现 DDM 过滤机制的方法。 关键词 高层体系结构 HLA；数据分发管理 DDM ；数据过滤；适应性算法引言 现代仿真应用已经从集中式仿真发展到分布式交互仿真，高层体系结构 HLA 也已成为了其通用技术框架的核心。而随着分布交互仿真系统规模和复杂度的增加，数据分发管理 DDM(Data Distribution Management)有效地减少了系统中的数据通信量，节省了网络带宽和处理机资源，同时也提高了系统的可扩缩性。 文章介绍了目前常用的DDM 匹配算法和一些启发式规则；重点分析了基于排序的DDM 算法并用一些新的标准来衡量和比较它们，利用这些标准有效地选取最适应的算法；最后总结了全文。1 HLA 中的DDM 数据过滤原理 HLA 是 1995 年美国国防部建模与仿真主计划 MSLD 中开发建模和仿真通用技术框架中的首要内容, 其主要目的是促进仿真应用的互操作性和仿真资源的可重用性，并于 2000 年通过 IEEE 标准。HLA 主要包括规则定义(Rules)、对象模型模板(Object Model Template )，接口2 / 8规范说明( Interface Specification)三部分内容1。数据分发管理 DDM 是 HLA/RTI 最重要的功能之一，是根据仿真实体之间的数据供求关系实现的基于组播通信的数据过滤技术，为系统的可扩缩性提供了可能。实现 DDM 主要考虑的问题有：区域匹配问题，组播分配和组播实现问题，区域动态变化问题和降低区域匹配的损耗问题等，HLA 引进了路径空间 RS(Routing Space)的概念1 来描述这种限制条件。一个路径空间是一个多维的坐标系统, 是联邦中属性值构成的数据空间。RS 包括以下几个概念:维(dimension)、范围( range)、限域(extent)、区域(Region)。其中区域是路径空间的子集可分为两种区域:更新区域(Update Region)和订购区域(Subscribe Region)。区域是数据分发管理的核心概念。2 实现 DDM 的几种方法基于区域的方法 (Region-based) 在基于区域的数据分发管理中发布-订购对是以一种随机的顺序建立起来的，计算每对的交互情况直到非空交互被找到。这是一种最基本的方法，优点是应用直观且匹配精确，缺点是其性能随着非空交互出现的几率大小有着极其明显的变化。当所有的更新区域与所有的订购区域都有交互时，此方法是最有效的。但当根本没有交互时则其复杂度将变为平方级。算法本身存在着实现上的可扩展(Scalability)问题，即当系统中仿真对象类数为 N 时，DDM 中的更新区域和订购区域的匹配比3 / 8较次数将与 N 平方成正比，即匹配次数的增长规模为 O(N2)。该方法不适合大规模复杂系统中更新区域和订购区域数量都很大的情况。 表格划分法 (Grid-based) 基于网格的方法提供了一种相对简单的区域匹配和确定网络连接的方法。路径空间都被分隔成网格，每个格子的维数等于路径空间的维数。订购区域与更新区域的比较不是直接进行，而是通过每个成员将其更新和订购区域映射到路径空间的网格上，通过判断区域是否覆盖了同一个网格来确定哪些订购区域和更新区域是相重叠的。对于重叠计算过程中产生冗余和虚假连接可以通过优化网格的尺寸 g 来获得更好的效果4。如图 1 中 C1(U1,S1)更新区域 U1 和订购区域 S1 实际上并不相交，但是由于它们分别都覆盖(覆盖的关系可以是部分的或完全的)了网格 1，因此与 U 1 关联的数据将通过组播组发往 S1 对应的联邦成员。即产生了虚假连接。冗余连接是指数据发送和接收双方之间存在一条以上的数据通道。当更新区域和订购区域覆盖了多于一个的相同网格时会产生冗余连接。如图 2 所示，U3和 S2 相交，二者之间建立一个发送接收关系即可。而在网格法它们之间存在四条通信通道 C7(U3, S2)、C8(U3, S2) 、C11(U3, S2) 、C12(U3, S2)。表格划分法 (Grid-based)的性能随着网格尺寸大小的变化有着显著的波动。当区域重4 / 8叠率低时，细划分的网格算法性能较优，但随着重叠率的提高则会产生大量的冗余连接其性能急剧下降4 ；而网格划分较少的情况下，此算法的性能对重叠率的变化显得不是十分敏感，对于一定范围内的重叠率的变化都可以得出较满意的结果。但是其组播地址利用率不高。另外，基于网格的 DDM 算法最大的缺点就是其组播地址利用率不高。基于排序的算法 (sort-based) 在基于排序的方法中首先把区域投影到每个坐标轴上并单独计算重叠情况，若在所有的坐标方向上均有重叠则此发布-订购对重叠。算法将应用两个集合来存储信息：前订购域集合SubscriptionsetBefore 用来存储位于当前所处理的发布域坐标位置之前的定购域信息；后订购域集合SubscriptionsetAfter 则用来存储位于当前所处理的发布域坐标位置之后的定购域信息。首先，把每个域的上界和下界在每个坐标方向上排序。当扫描排序的列表时，就可能得到当前点的前定购域集合和后订购域集合。因此，就能确切了解，对于每个更新区域是哪些订购区域在给定的坐标上与之匹配。 初始条件下，由于还没有任何扫描动作，假定所有的定购域信息均被存储与 SubscriptionAfter 集合中，所以 SubscriptionBefore 集合为空集而SubscriptionAfter 集合为全集。当处理到某一定购域的下5 / 8界点时，说明其坐标位置肯定不能位于下一发布域之后，因此将之从 SubscriptionsetAfter 集合中取出，当处理到某一定购域的上界点时，说明其坐标位置肯定位于下一发布域之前，因此将之插入倒 SubscriptionsetBefore 集合中。当处理到某个发布域的端点时，与此发布域的不重叠信息存储于 SubscriptionsetAfter 集合或SubscriptionsetBefore 集合中。例如图 3 所示，一系列点表示了在区域在 x 轴上投影后的边界情况。算法从左到右扫描列表并执行下列操作：对于每个在路径空间中的限域 Ri 作如下操作： 把 Ri 的下界点插入到列表 L 把 Ri 的上界点插入到列表 L 列表 L 进行排序 定购域前集Subscriptionsetbefore= 把所有的定购域均插入定购域后集 Subscriptionsetafter 对于列表 L 中的所有点Pi 作下列循环 R i=点 Pi 所属域的标识 if (Ri 是订购域) if (Pi 点是 Ri 的下界点) 从 Subscriptionsetafter 中移去 Ri else 把 Ri 插入到 Subscriptionsetbefore 中 else (Ri 是更新域) if(Pi 点是 Ri 的下界点) 则 Subscriptionsetbefore 中的所有域均不与 Ri 交互 else 则 Subscriptionsetafter 中的所有域均不与Ri 交互 可以对基于排序的算法进行一些有效的改6 / 8进，例如可以用二进制向量来代替当前定购域集合，这样可以极大的降低每个更新域的匹配操作复杂度3。此算法的一个显著特性是其性能没有随着重叠率及限域数目的变化而显著变化。而且，在重叠率不是特别低、区域内所含限域数目不是特别多时其性能较其他算法而言是最优的3。重叠率很低时，网格划分法要优于排序的算法；而当重叠率很高且区域内含有的限域数目很大时，基于区域的算法的性能就会优于排序算法2。 其它的启发式规则 边界区域 (Bounding Boxes)：此方法是计算每个域的边界区域是否有重叠，如果交互为空则无须再计算边界框内的域的重叠，反之，再在边界框区域内重新计算域间的重叠情况。暂时连续性 (Temporal Coherence)：这一规则充分利用了在许多仿真中事物是逐渐变化的规则，即在仿真中两个相邻时间状态下很多区域并不会有明显的移动2。从而进一步减少区域匹配的次数。 3 适应性算法 (Adaptive Approach) 问题的特性 DDM中最显著的属性是域的数量情况。但之前所分析的各种算法和一些启发式规则的效率随着区域在路径空间中的不同的分布有较大的变化，所以必须在给定的路径空间中更准确地定义域的分布情况。有两个首要的因素需要考虑，首先是重叠率：描述了域间重叠的可能性，是一个影响 DDM算法效率的重要因素，定义为：7 / 8其次是每个区域内的限域的数目，因为 DDM 关心的是区域间的重叠而不是限域间的重叠情况。在实际情况下当面对大量的限域时，在整个空间中使用平均的重叠率是不现实的，很有可能在同一路径空间中存在重叠率高的区域，中等的区域以及重叠率很低的区域，且这些特性都是动态变化的值，DDM 具体算法的选取需要计算和跟踪这些重要的属性。有两种方法可供选取：第一，首先把路径空间做初步的划分，当然为了达到某一局部重叠率的要求可以嵌套划分一直达到某一规定重叠率值或划分的网格数达到某要求为止。第二，用排序的方法。检测排序后的列表时就可以直接得到每个初始划分部分在此坐标方向上的局部重叠率情况，在每维上做同样的检测则可得到空间中的域是较平均分布的还是有聚集和稀疏的不均匀分布。算法的选取 重叠率的取值范围较大并且算法的选择不需要精确的重叠率值，因此在大多数情况下对其作粗略估计即可。在不知道待解问题的具体特性时，一般选取基于排序的 DDM 算法2，通常情况下此算法效率较高并且除匹配操作以外对问题分析和预操作的复杂度较低3。除此之外，一些启发式规则也可应用到系统中来，但需要一种机制来针对路径空间中的不同区域优选具体的算法。细划分的基于网格的算法适用于限域重叠率较低的情况 2。基于区域的算法则适用于重叠率较高的情况。其他情况通常选取基于排序的8 / 8DDM 算法。但是当限域在路径空间中移动时，问题的属性会发生变化，可以在平均重叠率超过某一阈值时重新计算划分并在局部范围内重新选区 DDM 算法。另外，对于路径空间内区域重叠率不是均匀分布的情况可以通过多种 D