摘 要 hla已成为了现代分布式仿真应用的通用技术框架的核心，而作为其六大服务之一的数据分发管理则提供了有效的信息交互和传送机制以满足系统可扩缩性的要求。文章介绍了hla中数据分发管理ddm的过滤原理；研究并分析了目前几种实现ddm过滤机制的方法。关键词 高层体系结构hla；数据分发管理ddm ；数据过滤；适应性算法

引言

现代仿真应用已经从集中式仿真发展到分布式交互仿真，高层体系结构hla（high level architecture）也已成为了其通用技术框架的核心。而随着分布交互仿真系统规模和复杂度的增加，数据分发管理ddm(data distribution management)有效地减少了系统中的数据通信量，节省了网络带宽和处理机资源，同时也提高了系统的可扩缩性。 文章介绍了目前常用的ddm匹配算法和一些启发式规则；重点分析了基于排序的ddm算法并用一些新的标准来衡量和比较它们，利用这些标准有效地选取最适应的算法；最后总结了全文。

1 hla中的ddm数据过滤原理

hla是1995 年美国国防部建模与仿真主计划msld中开发建模和仿真通用技术框架中的首要内容, 其主要目的是促进仿真应用的互操作性和仿真资源的可重用性，并于2000年通过ieee标准。wwW.11665.comhla主要包括规则定义(rules)、对象模型模板(object model template )，接口规范说明( interface specification)三部分内容[1]。数据分发管理ddm是hla/rti最重要的功能之一，是根据仿真实体之间的数据供求关系实现的基于组播通信的数据过滤技术，为系统的可扩缩性提供了可能。实现ddm主要考虑的问题有：区域匹配问题，组播分配和组播实现问题，区域动态变化问题和降低区域匹配的损耗问题等，hla引进了路径空间rs(routing space)的概念[1] 来描述这种限制条件。一个路径空间是一个多维的坐标系统, 是联邦中属性值构成的数据空间。rs 包括以下几个概念:维(dimension)、范围( range)、限域(extent)、区域(region)。其中区域是路径空间的子集可分为两种区域:更新区域(update region)和订购区域(subscribe region)。区域是数据分发管理的核心概念。

2 实现ddm的几种方法

2.1基于区域的方法 (region-based)

在基于区域的数据分发管理中发布-订购对是以一种随机的顺序建立起来的，计算每对的交互情况直到非空交互被找到。这是一种最基本的方法，优点是应用直观且匹配精确，缺点是其性能随着非空交互出现的几率大小有着极其明显的变化。当所有的更新区域与所有的订购区域都有交互时，此方法是最有效的。但当根本没有交互时则其复杂度将变为平方级。算法本身存在着实现上的可扩展(scalability)问题，即当系统中仿真对象类数为n时，ddm中的更新区域和订购区域的匹配比较次数将与n平方成正比，即匹配次数的增长规模为o(n2)。该方法不适合大规模复杂系统中更新区域和订购区域数量都很大的情况。

2.2 表格划分法 (grid-based)

基于网格的方法提供了一种相对简单的区域匹配和确定网络连接的方法。路径空间都被分隔成网格，每个格子的维数等于路径空间的维数。订购区域与更新区域的比较不是直接进行，而是通过每个成员将其更新和订购区域映射到路径空间的网格上，通过判断区域是否覆盖了同一个网格来确定哪些订购区域和更新区域是相重叠的。对于重叠计算过程中产生冗余和虚假连接可以通过优化网格的尺寸g来获得更好的效果[4]。

如图1中c1(u1,s1)更新区域u1和订购区域s1实际上并不相交，但是由于它们分别都覆盖(覆盖的关系可以是部分的或完全的)了网格1，因此与u1关联的数据将通过组播组发往s1对应的联邦成员。即产生了虚假连接。冗余连接是指数据发送和接收双方之间存在一条以上的数据通道。当更新区域和订购区域覆盖了多于一个的相同网格时会产生冗余连接。如图2所示，u3和s2相交，二者之间建立一个发送接收关系即可。而在网格法它们之间存在四条通信通道c7(u3, s2)、c8(u3, s2) 、c11(u3, s2) 、c12(u3, s2)。表格划分法 (grid-based)的性能随着网格尺寸大小的变化有着显著的波动。当区域重叠率低时，细划分的网格算法性能较优，但随着重叠率的提高则会产生大量的冗余连接其性能急剧下降[4] ；而网格划分较少的情况下，此算法的性能对重叠率的变化显得不是十分敏感，对于一定范围内的重叠率的变化都可以得出较满意的结果。但是其组播地址利用率不高。另外，基于网格的ddm算法最大的缺点就是其组播地址利用率不高。

2.3 基于排序的算法 (sort-based)

在基于排序的方法中首先把区域投影到每个坐标轴上并单独计算重叠情况，若在所有的坐标方向上均有重叠则此发布-订购对重叠。算法将应用两个集合来存储信息：前订购域集合subscriptionsetbefore用来存储位于当前所处理的发布域坐标位置之前的定购域信息；后订购域集合subscriptionsetafter则用来存储位于当前所处理的发布域坐标位置之后的定购域信息。首先，把每个域的上界和下界在每个坐标方向上排序。当扫描排序的列表时，就可能得到当前点的前定购域集合和后订购域集合。因此，就能确切了解，对于每个更新区域是哪些订购区域在给定的坐标上与之匹配。 初始条件下，由于还没有任何扫描动作，假定所有的定购域信息均被存储与subscriptionafter集合中，所以subscriptionbefore集合为空集而subscriptionafter集合为全集。当处理到某一定购域的下界点时，说明其坐标位置肯定不能位于下一发布域之后，因此将之从subscriptionsetafter集合中取出，当处理到某一定购域的上界点时，说明其坐标位置肯定位于下一发布域之前，因此将之插入倒subscriptionsetbefore集合中。当处理到某个发布域的端点时，与此发布域的不重叠信息存储于subscriptionsetafter集合或subscriptionsetbefore集合中。例如图3所示，一系列点表示了在区域在x轴上投影后的边界情况。算法从左到右扫描列表并执行下列操作：

对于每个在路径空间中的限域ri作如下操作：

· {· 把ri的下界点插入到列表l· 把ri的上界点插入到列表l· }· 列表l进行排序· 定购域前集subscriptionsetbefore= · 把所有的定购域均插入定购域后集subscriptionsetafter· 对于列表l中的所有点pi作下列循环· {· ri=点pi所属域的标识

· if (ri 是订购域) · {· if (pi点是ri的下界点)· 从 subscriptionsetafter 中移去ri· else· 把ri插入到subscriptionsetbefore中· }· else (ri是更新域)· {· if(pi点是ri的下界点)· 则subscriptionsetbefore中的所有域均不与ri交互· else· 则subscriptionsetafter中的所有域均不与ri交互· }· } 可以对基于排序的算法进行一些有效的改进，例如可以用二进制向量来代替当前定购域集合，这样可以极大的降低每个更新域的匹配操作复杂度[3]。此算法的一个显著特性是其性能没有随着重叠率及限域数目的变化而显著变化。而且，在重叠率不是特别低、区域内所含限域数目不是特别多时其性能较其他算法而言是最优的[3]。重叠率很低时，网格划分法要优于排序的算法；而当重叠率很高且区域内含有的限域数目很大时，基于区域的算法的性能就会优于排序算法[2]。

2.4 其它的启发式规则

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

3 适应性算法 (adaptive approach)

3.1 问题的特性

ddm中最显著的属性是域的数量情况。但之前所分析的各种算法和一些启发式规则的效率随着区域在路径空间中的不同的分布有较大的变化，所以必须在给定的路径空间中更准确地定义域的分布情况。有两个首要的因素需要考虑，首先是重叠率（overlapping rate）：描述了域间重叠的可能性，是一个影响ddm算法效率的重要因素，定义为： 其次是每个区域内的限域的数目，因为ddm关心的是区域间的重叠而不是限域间的重叠情况。在实际情况下当面对大量的限域时，在整个空间中使用平均的重叠率是不现实的，很有可能在同一路径空间中存在重叠率高的区域，中等的区域以及重叠率很低的区域，且这些特性都是动态变化的值，ddm具体算法的选取需要计算和跟踪这些重要的属性。有两种方法可供选取：第一，首先把路径空间做初步的划分，当然为了达到某一局部重叠率的要求可以嵌套划分一直达到某一规定重叠率值或划分的网格数达到某要求为止。第二，用排序的方法。检测排序后的列表时就可以直接得到每个初始划分部分在此坐标方向上的局部重叠率情况，在每维上做同样的检测则可得到空间中的域是较平均分布的还是有聚集和稀疏的不均匀分布。

3.2算法的选取

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

4 结论

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

参考文献

[1] dmso. high level architecture interface specification ver 3,2 [eb/ol]. 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~673zhang xia, huang sha-bai. research of ddm in high level architecture. journal of system simulation 2003,15,670~673[7] 张霞，黄莎白.hla中基于agent的层次过滤机制.计算机仿真[8] 张霞，黄莎白.一种混合的动态ddm实现方法.计算机工程