（计算机软件与理论专业论文）hla中数据分发管理算法的研究与实现.pdf

i 中中 文文 摘摘 要要 高层体系结构hla是美国建模与仿真办公室为了满足大规模复杂仿真系统的需求，提出的一种新型的仿真框架。该框架具有开放性、扩展性、交互性、分布性和可重用性的优点。在 2000 年 9 月被国际电气和电子工程师协会 ieee 接受为标准ieee1516。高层体系结构 hla 提供的数据分发管理服务 ddm 是实现系统可扩缩性的关键技术。其目的是为了减少仿真系统中无用数据的传送，降低仿真结点接收冗余数据的处理开销，减少网络带宽的占用，以提高仿真系统的运行效率，达到仿真系统可扩缩性的要求。 论文的研究内容与成果包括： （1）论述了高层体系结构的相关概念和组成、高层体系结构及数据分发管理服务的国内外研究现状、 该技术的发展应用； 论述了数据分发管理服务 ddm 的概念及实现原理，重点研究分析了经典的基于区域和基于网格的数据分发管理算法。 （2）分析了基于排序数据分发管理算法的实现原理，针对其相交信息矩阵占用的存储空间大和区域匹配判断的循环计算次数多的不足，提出了一种改进的排序数据分发管理算法。改进后的算法只建立一个相交信息矩阵降低了对存储空间的需求，同时减少了算法的循环次数且无须进行大量矩阵的“与”操作，提高了算法的执行效率。经过实例分析和实验验证，该算法在存储空间和执行时间上都优于原始的排序匹配算法，适用于区域比较多的大规模分布式仿真系统。 （3）实验数据表明每种数据分发管理算法的性能都会随着仿真应用场景属性的变化而在执行性能上表现出一定的波动。通过对影响算法执行性能的不同应用场景属性参数的设置，分别对基于区域的、基于网格的、基于排序的经典数据分发管理算法在执行时间和匹配精度上进行实验，并对实验结果进行分析，总结不同数据分发管理算法适用的应用场景属性参数，为不同应用场景下数据分发管理算法的自适应选择提供选取依据。在仿真应用运行前或者仿真运行过程中可以根据仿真场景的属性情况静态或者动态地选取不同的数据分发管理算法，以此来提高仿真系统运行的整体性能。 关键词：关键词：高层体系结构；数据分发管理；排序数据分发管理算法；自适应 iii abstract high level architecture which is proposed by modeling and simulation office of the united states is the latest simulation frame for reuse and interoperation of the complex large-scale simulation. high level architecture has five features: open, extensible, interactive, distributed and reusability. the framework of high level architecture is accepted by international electrical and engineers as the standard ieee 1516. data distribution management, one of six services, develops to provide scalability and reusability. data distribution management is responsible for limiting and controlling the data exchanged during a simulation, in order to decrease the network width and the required computer resource, to improve the efficiency of simulation system, to achieve the simulation system scalability requirements. it also aims at reducing the processing requirements of simulation hosts, or federates, by communicating updates regarding intractions and state information only to federates that require them. the contents and results of paper include: (1) discusses the concepts and components of high level architecture, current research status of high level architecture and data distribution management, the application of high level architecture; and also discusses the concepts and principle of data distribution management, analyses region-based and grid-based data distribution management methods in detail. (2) analyses the principle of sort-based ddm. based on the disadvantages of the overlapping information matrix with vast storage space and the overlapping computation with large number of multi-cycles, a new and improved sort-based ddm algorithm is proposed. the proposed method only needs one m*n matrix storing overlapping information. it reduces the number of multi-cycles and doesnt need an “and” operation. the proposed method is proved by experiments to be better than the original method in the iv storage space and time performance. it is suitable for an extended number of regions in large-scale distributed simulation system. (3) experiment results show that each ddm performance is affected by the attributes changing of the simulation application scenarios. through setting parameter which effect ddm method executing performance, comparing ddm executing time and matching precision of region-based ddm, grid-based ddm, sort-based ddm, and analysis the experiment results, we summarize different scene property parameters which affected different ddm methods. in the end, we proposed the adaptive selection strategy of ddm method. we can the statically or dynamical to select different ddm methods in the simulation application run before or simulation operation processing, in order to improve the overall performance of the simulation system operation. key words: high level architecture；data distribution management；sort-based data distribution management；adaptive data distribution management 承诺书 35承承 诺诺 书书 本人郑重声明：所呈交的学位论文，是在导师指导下独立完成的，学位论文的知识产权属于山西大学。 如果今后以其他单位名义发表与在读期间学位论文相关的内容，将承担法律责任。除文中已经注明引用的文献资料外， 本学位论文不包括任何其他个人或集体已经发表或撰写过的成果。 作者签名： 20 年 月 日 hla 中数据分发管理算法的研究与实现 36学位论文使用授权声明学位论文使用授权声明 本人完全了解山西大学有关保留、使用学位论文的规定，即：学校有权保留并向国家有关机关或机构送交论文的复印件和电子文档， 允许论文被查阅和借阅，可以采用影印、缩印或扫描等手段保存、汇编学位论文。同意山西大学可以用不同方式在不同媒体上发表、传播论文的全部或部分内容。 保密的学位论文在解密后遵守此协议。 作者签名： 导师签名： 20 年 月 日 第一章 绪论 1第一章第一章 绪绪 论论 1.11.1 论文的研究背景和意义论文的研究背景和意义 随着人类的进步和各种新技术的发展，各个应用领域内的系统待解决问题的规模和复杂程度也在不断增加，要求未来的仿真技术能够支持范围更广泛的仿真环境。但是受到软硬件资源的限制和现有仿真技术缺乏的条件下，当系统规模较大时会存在实现上的问题。这些实现上存在的问题就是分布交互仿真系统所面临的系统可扩缩性问题1,2。基于高层体系结构 hla（high level architecture）的分布式交互仿真技术方法应用而生。 hla 是用来构建大型复杂仿真系统的仿真技术， 通过将分布在世界各地的多个小型的仿真系统联合在一起构成一个大型复杂仿真系统，它支持地理分布的仿真平台之间的互操作，从而能满足仿真灵活性的要求，同时满足系统可扩缩性和可重用性的要求3,4。 hla 具有五个优点：开放性、扩展性、交互性、分布性和可重用性5。正由于这些优点的存在，hla 技术被应用在当今社会发展的各个领域，如军用、民用领域和医疗系统领域等。该技术被国际上一致认为是当今社会最有效且最经济的系统仿真框架，是推动科技进步的战略技术。 一个大型的复杂仿真系统内实体之间的联系和交互是错综复杂的，关系到大量的数据、事件和信息的传递，但是在网络上传递无关数据和冗余数据对系统的效率和成本有很大的影响，占用了网络带宽，增加了处理机资源的消耗。hla 中的数据分发管理 ddm（data distribution management）服务就是解决以上问题，实现系统可扩缩性的关键技术。ddm 的目的是根据仿真系统成员间的数据供求关系实现数据过滤，减少无关数据的传输，以减少网络带宽的占用，同时降低仿真结点接收冗余数据时的处理开销， 以增强系统的可扩缩性。 hla 中不同的数据过滤实现方式会有不同的数据过滤效果。因此可以按照接口定义开发出不同实现的 ddm 算法，或对现有的方法进行改进和完善，以提高数据过滤机制的执行能力，适应不同的仿真应用系统。ddm 实现的关键是发布区域和订购区域的匹配（区域重叠）判断。论文正是在这样的背景下提出来的。论文研究分析了 hla 中各种 ddm 算法的实现原理， 对其中的基于排序的 ddm 算法进行了改进， 达到提高数据过滤性能的目的；ddm 算法在不同的仿真应用中的执行效率各有差异，论文给出不同应用场景下选hla 中数据分发管理算法的研究与实现 2取 ddm 算法的策略，以增强对仿真环境的适应能力，使仿真系统达到最优。通过对 hla 中 ddm 的研究，有利于提高仿真系统的运行效率，降低系统的成本，达到提高系统的可扩缩性要求。 1.21.2 国内外研究现状国内外研究现状 hla 作为一种新型的仿真框架，世界各国纷纷启动了关于 hla 的研究计划。hla 的研究重点是其核心的运行支撑环境 rti（run-time infrastructure）的开发，世界各国对 rti 的研究自 1996 年以来，已有了较大的进展。 dmso（the defense modeling and simulation office）在其推出第一个经过全面测试的rti-ng1.3v2以后， 业界出现了多种rti版本， 主要代表6是以瑞典pitch ais 公司的 prti1516 和美国 mak 公司开发的 mak rti。英国国防部已自行研发出rti-lite 和全分布式的基于中间件 corba 的 ukrti。此外韩国、日本、新加坡、麻省理工学院、gmu 大学、甚至台湾中山大学也在积极从事 rti 的研制和开发工作7。 分布交互仿真技术在我国的研究起步比较晚，以国防科技大学、航天机电集团第二研究院、北京航空航天大学为代表的国内研究机构对 rti 的研究虽然取得了一定的成果，但并没形成可公开推广的商业产品，仅限于在某些领域中的特殊应用，不能很好的体现分布交互仿真可重用和互操作特性。国内最具代表性的 rti 是由北京航空航天大学开发的 863-hla/863-rti-1.3 和国防科技大学开发的 starlink8。另外，国防科大、北京航空航天大学和航天机电集团第二研究院研究实现的 windows平台下的 rti 是基于 corba 实现的9。基于 corba 实现的 rti 可以充分利用corba 的特性，具有实现简单的优点，但是这种中间件技术的引入，必然导致系统性能的降低。 虽然这些软件实现了 rti 接口服务的功能，但都存在一些缺点，有很多只实现了 rti 接口服务中的五大管理功能，并不支持 ddm 服务，如 starlink。因此，对ddm 服务还需要进行深入研究。 ddm 的基本思想是根据数据之间的供求关系实现数据过滤，目的是减少网络中的无关数据，降低仿真结点接受冗余数据时的处理能力，提高仿真系统的通信效率，增强系统的可扩缩性。 目前许多学者对 ddm 算法进行了研究， 其中经典的 ddm 算法有基于区域的、基于网格的和基于排序的 ddm 算法。基于区域 ddm 算法10是将路径空间中的发第一章 绪论 3布区域和订购区域进行区域重叠计算，这种算法匹配精确，易于实现。但当区域数目增多时，该方法的执行时间急剧增加，降低了仿真系统的可扩缩性。基于网格ddm 算法10,11是将路径空间划分成大小相同的格子，将发布区域和订购区域映射在网格上，当发布区域和订购区域覆盖同一个网格时，就认为这两个区域重叠。但是这种算法会产生虚假连接和冗余连接。基于排序的 ddm 算法12是将发布区域和订购区域在某一维上的高低坐标值在该维度上进行投影，若发布区域高低坐标范围和订购区域的高低坐标范围有重叠，就表明发布区域和订购区域在该维上相交。对所有的维进行上述处理，当且仅当发布区域和订购区域在所有维上都重叠，该发布区域和订购区域才相交。 另外，许多学者在对网格算法的研究中发现，网格划分的大小会影响仿真系统的数据过滤能力和 ddm 执行时间13。因此，窦志武等人提出了一种变尺度动态网格 ddm 算法14， 这种方法可以在仿真运行中自动改变对路径空间划分的网格大小，使系统达到最优，提高区域的匹配精度。dmso rti1.315提出了一种通过递归使用基于区域的 ddm 方法以实现 rti 的可扩展性。rti-s 的设计中使用的是多级网格的方法4。还有学者将基于区域和基于网格算法结合起来，提出了一种混合 ddm算法，这种算法先用基于网格进行粗略匹配，再采用基于区域进行精确匹配16，但在进行完网格匹配后，会产生冗余数据。因此张霞等人提出来一种混合动态ddm17， 有利于减少了冗余数据的产生， 提高了匹配精度。 boukerche 等人对 ddm 算法的运行性能进行了分析18。 1.31.3 基于基于 hla 分布式交互仿真的应用分布式交互仿真的应用 分布式仿真技术已经构成了一个综合性的专业技术体系，正发展成为一项通用性、战略性技术。hla 代表着分布式仿真发展的最新方向和业界标准，成为当今仿真领域的研究重点和热点。分布式交互仿真技术在军事、民用和紧急救援方面都得到了充分的应用，主要体现在以下几个方面： （1）军事领域的应用 随着各种新技术在武器装备、军事对抗中的应用，各国受国防经费、政治和环境的制约， 各国研究新的技术来境地经费。 分布式交互仿真在这种情况下应运而生。由于分布式交互仿真技术作为一种最先在军事领域发展起来的技术，具有无破坏性、可多次重复、安全、经济、可控、不受气候条件和场地时间限制等优点，因此可以极大的节省研制经费、 缩短研制周期， 提高研制质量， 被广泛应用在武器研制、hla 中数据分发管理算法的研究与实现 4武器对抗和作战模拟训练当中19。 近年来， hla 作为最新的分布式交互仿真技术为军事领域的仿真应用更是起了极大的推动作用。如多武器平台攻防对抗综合仿真示范系统(航天总公司二院)、装甲数字化营作战仿真系统(装甲兵工程学院)、陆军师联合登岛作战系统(国防科技大学)、鱼雷武器分布式仿真系统等等，但是还没有形成有效的体系系统。 国外仿真技术的发展已形成体系，尤其是在军事领域的应用，仿真技术的作用越来越显著。目前，美、英、法等国以仿真技术为核心，用高速计算机网络已将各种试验系统及有关研制机构联结起来形成一个完整的试验体系，即分布式仿真试验系统。例如，美国的国家试验台以设在法尔肯空军基地的“国际试验中心”为核心，将分布在美国各地的有关部门（如陆军空间与战略防御司令部、海军研究实验室、空军电子系统部、空军技术中心、能源部路斯阿莫斯国家实验室及其它国家实验室等）用网络联起来，组成分布式系统，用以承担论证、检验和鉴定战略防御方案和指挥控制软件等任务20,21。该系统能高度逼真地模拟战略防御系统的作战过程，可在系统内试验要验证和评价的硬件，允许单独试验战略防御系统的作战管理与指挥、控制、通信系统软件。这样的武器系统试验体系运用的核心技术就是分布交互仿真技术。 （2）民用仿真 虽然分布交互仿真技术最早被应用于军事领域，但由于其本身所许多优点，现已经被应用在许多民用领域，如在教育方面、自然科学研究方面、医疗、交通、娱乐、应急演练等。“网上练兵”、“虚拟主持人”等诸多与仿真应用有关的新名词不断涌现，也表明了仿真创新技术对社会进步的影响22。 在教育方面，由于分布交互仿真允许受训者参与，增强受训者的兴趣，从而可以充分调动受训者的学习机能，并充分发挥受训者的创造意识，极大的提高了受训者的学习效率。 在自然科学研究领域，通过仿真的手段在科学理论和知识经验的交互验证下，从整体的最佳角度出发制定设计方案。 在医疗方面，医疗单位在对严重受伤或危重病人进行实际治疗之前，可以在合成环境中进行虚拟医疗，验证医疗方案。 在购物方面，顾客可以在虚拟仿真环境中看、听、使用商品，充分考察商品的性能，分布交互仿真也可用于娱乐行业以及高度交互、引人入胜的游戏。 在交通方面，分布式交互仿真为交通管制、运行调度等的研究提供了有力的技第一章 绪论 5术支持。 在娱乐方面，分布式交互仿真可应用于网上视频、网络虚拟环境等商业产品的开发。 在紧急救援方面，充分利用分布交互仿真技术，提供能使各种救援机构进行指挥、控制和通信的人工合成环境，并在此环境中进行各种灾害演习，将有利于提高处理各种真实灾害的能力。 总之，分布式交互仿真被应用在社会的方方面面，极大的缩短了研制周期，减少了研究经费，使仿真获得了最佳的效果。因此，基于 hla 的分布式交互仿真在国内外受到了高度的重视，在国际上一致被认为是“仿真是迄今为止最有效的综合集成方法，是推动科技进步的战略技术”。 1.41.4 论文的主要工作与成果论文的主要工作与成果 本论文的研究目标是在分析 hla 的基础上，深入研究 ddm 算法的实现原理及存在的问题，提出相关的技术解决途径并进行实现、验证和分析。通过对 hla中 ddm 的研究，有利于提高仿真系统的运行效率，降低系统的成本，达到提高系统的可扩缩性要求。 论文的研究内容与成果包括： （1）阐述了论文研究的背景和意义、hla 及 ddm 的国内外研究现状、hla技术的应用。 （2）论述了 hla 的相关概念和组成、ddm 的概念及实现原理，重点研究分析了经典的基于区域和基于网格的 ddm 算法。 （3） 分析了基于排序 ddm 算法的实现原理， 针对其相交信息矩阵占用的存储空间大和区域匹配判断的循环计算次数多的不足，提出了一种改进的排序 ddm 算法。改进后的算法只建立一个相交信息矩阵降低了对存储空间的需求，同时减少了算法的循环次数且无须进行大量矩阵的“与”操作，提高了算法的执行效率。经过实例分析和实验验证， 该算法在存储空间和执行时间上都优于原始的排序 ddm 算法，适用于区域比较多的大规模分布式仿真系统。 （4） 实验数据表明每种 ddm 算法的性能都会随着仿真应用场景属性的变化而在执行性能上表现出一定的波动。通过对影响算法执行性能的不同应用场景属性参数的设置，分别对基于区域的、基于网格的、基于排序的经典 ddm 算法在执行时间和匹配精度上进行实验，并对实验结果进行分析，总结不同 ddm 算法适用的应hla 中数据分发管理算法的研究与实现 6用场景属性参数，为不同应用场景下 ddm 算法的自适应选择提供选取依据。在仿真应用运行前或者仿真运行过程中可以根据仿真场景的属性情况静态或者动态地选取不同的 ddm 算法，以此来提高仿真系统运行的整体性能。 1.51.5 论文组织结构论文组织结构 论文由五章组成，各章的主要内容如下： 第一章是绪论，主要阐述了论文的研究背景和意义、国内外研究现状以及应用领域。最后介绍了论文的主要内容和成果。 第二章在分析hla中ddm的相关概念和实现原理的基础上， 详细分析了ddm数据过滤的两类方法，重点研究分析了经典的基于区域和基于网格的 ddm 方法以及它们的优缺点。 第三章分析了基于排序 ddm 算法的实现原理及其优缺点，针对其占用存储空间大和算法执行时间多的缺点，提出了一种改进的排序 ddm 算法。最后给出了两种算法的实验结果与结论。 第四章通过对影响算法执行性能的不同应用场景属性参数的设置，分别对基于区域的、基于网格的、基于排序的 ddm 算法在执行时间和匹配精度上进行实验，并对实验结果进行分析，总结不同 ddm 算法适用的应用场景属性参数，为不同应用场景下 ddm 算法的自适应选择提供选取依据。在仿真应用运行前或者仿真运行过程中可以根据仿真场景的属性情况静态或者动态地选取不同的 ddm 算法，以此来提高仿真系统运行的整体性能。 第五章进行总结和展望，总结了论文已完成的工作和论文的创新之处，最后提出了今后的工作方向。 第二章 数据分发管理算法 7第二章第二章 数据分发管理算法数据分发管理算法 2.1 高层体系结构2.1 高层体系结构 hla 1996年8月美国建模与仿真办公室dmso （the defense modeling and simulation office）正式公布 hla 规范23；1996 年 9 月，dod 规定 hla 为美国国防部所有仿真标准技术结构24,25； 在 2000 年 9 月被国际电气和电子工程师协会 ieee 接受为标准ieee151626。 hla 中联邦和联邦成员的定义如下27,28,29： 联邦27,28,29（federation） ：由各个仿真子系统为实现某种特定仿真目的而组织在一起构成的系统。其运行的过程，称为联邦执行。 联邦成员27,28,29 (federate)：构成联邦的各个仿真子系统，简称邦员。真实实体仿真系统、构造或虚拟仿真系统、联邦运行管理控制器、数据收集器等都可以作为仿真系统的联邦成员。 图 2-1 是 hla 仿真系统的逻辑结构。hla 定义的联邦系统实质上是一个开放性的、具有可扩展性的分布式仿真系统。在这种结构中，rti 犹如“软总线”，满足一定要求的联邦成员可以在联邦运行过程中随时“插入”。 成员之间相互作用可通过 rti 提供的相关服务来实现。 hla 主要由三部分组成28,29：hla 规则、对象模型模板、接口规范。 （1）hla 规则（the rules）指联邦执行过程中，规定了所有联邦及其成员遵循的准则，以及实现邦员间的交互所必须遵循的原则和协定。hla 共规定了 10 条规则，其中前 5 条联邦规则，后 5 条是邦员规则。 （2）对象模型模板 omt（object model template） ：omt 定义的结构框架是用来描述 hla 对象模型信息，它提供的是一种标准的记录对象模型信息的格式。图 2-1 hla 仿真系统的逻辑结构通 信 网 络 运行时间支撑系统（rti） 联邦成员 rti 接 口联邦成员 rti 接 口联邦成员 rti 接 口hla 中数据分发管理算法的研究与实现 8目的是提高仿真系统的互操作性和可重用性。 （3）接口规范 (interface specification)：是对 rti 接口规范描述。它定义 rti的各项服务，并为仿真系统中每个邦员提供必须的回调功能。rti 接口服务主要提供的六大管理功能及其支持服务在内的 130 个接口服务。 hla 与其它技术关键的区别仅指定功能上的要求， 而不指定硬件、 软件和网络结构。它定义的是一种软件体系结构，因此研究人员可以对 hla 中的各个功能有不同的算法实现，不同算法的执行效率和性能也不相同。 2.2 分布交互仿真系统的可扩缩性2.2 分布交互仿真系统的可扩缩性 随着各个领域的仿真应用不断深入，仿真系统需要解决问题的规模和复杂程度也不断的增加，需要新的仿真技术或对现有技术改进以支持更大规模的仿真环境。但是受到软硬件资源的限制和现有仿真技术缺乏的条件下，当系统规模较大时会存在实现上的问题。这些实现上存在的问题就是分布交互仿真系统所面临系统可扩缩性问题。 系统可扩缩性指的是对系统的软硬件体系结构无需做较大的修改情况下，随着系统规模（仿真节点机或仿真实体数）的增加，对其计算和通信开销的增长不会影响仿真系统的正常运行30。 制约分布交互仿真系统可扩缩性的主要因素30： 处理机资源的制约。仿真结点机对数据进行必要的处理（数据的发送或接收、实体模型的计算） ，会影响到仿真系统的运行。 网络带宽的制约。在参与仿真的实体和结点规模增加的情况下，网络上传输的数据量会急剧增加，会产生数据延迟和冲突。 hla 提供的 ddm 服务就是根据数据的供求关系实现的数据过滤技术。 其目的主要是降低仿真结点接收冗余数据时引起的处理开销和尽可能减少无关数据的产生以减少网络带宽的占用。这两个目的都有助于系统的可扩缩性。 2.3 数据分发管理的相关概念2.3 数据分发管理的相关概念 维（dimension）由一对分别表示下界和上界数值的有序值对组成5,28,29。有序值对的第一个被称为下界，第二个被称为上界。 范围 （range） 指的是路径空间的某个维 （坐标轴） 上的一段连续的区间 5,28,29。 路径空间 rs（routing space）是一个维的命名序列，是一个归一化的多维坐标系统。rs 具有三个要素：坐标系统的维数、路径变量、路径变量在每维上的定义第二章 数据分发管理算法 9（如单位刻度、范围等） 5,28,29。 限域（extent）是一个有序排列的范围的集合，每一个范围对应于路径空间中的一维，且以维出现在路径空间中的顺序进行排列5,28,29。 区域（region）由同一个路径空间内的一组相关联的限域组成，是路径空间的一个子集5,28,29。 在数据分发管理服务中，区域总共有两类: （1）发布区域（publish region） ：邦员承诺发出进入该区域的属性值。 （2）订购区域（subscribe region） ：表明邦员希望接收到该区域的属性值或类实例。 图 2-2 范围、限域和区域 图 2-2 表示的是范围、限域和区域的关系。对复杂的区域的定义可以通过在区域里定义多个限域的集合来实现。 在仿真系统中， 区域可以随着仿真时间动态变化。 ddm 实现的关键是发布区域和订购区域的匹配（区域重叠）判断。通过对仿真系统中不同仿真节点上的仿真成员间的发布区域、订购区域的匹配判断，确定联邦成员间的数据交换范围，然后对有数据供求关系的邦员分配组播地址，最后在发布邦员和订购邦员间进行数据传送。 hla 中不同的数据过滤实现方式会有不同的数据过滤效果。 因此可以按照接口定义开发出不同实现的 ddm 算法，或对现有方法进行改进和完善，以提高算法的数据过滤能力，适应不同的仿真应用系统。 限域（extent）限域（extent）范围（range）范围（range）区域（region）hla 中数据分发管理算法的研究与实现 102.42.4 经典的经典的 ddm 算法算法 .1 基于区域基于区域 ddm 算法算法 基于区域的 ddm 算法中每个邦员的发布区域必须和所有其他邦员的订购区域进行直接匹配，判断区域是否相交。发布区域一旦发生改变时，新的发布区域必须和所有其他邦员的订购区域重新进行匹配31,32。 图 2-3 是一个二维路径空间，其中有发布区域 u1 和订购区域 s1、s2，根据基于区域的 ddm 方法的思想，p1 需要和 s1、s2 分别进行区域匹配，看是否存在区域重叠，经过匹配，p1 和 s1 存在区域重叠，p1 和 s2 没有区域重叠，因此 p1 的数据通过 rti 发送到 s1，而不发送到 s2 中。 基于区域的 ddm 方法的主要特点是实现简单，匹配精确。但该算法需要将每个发布区域必须和所有订购区域进行匹配，因此当仿真系统中区域数量为 n 时，ddm 中的发布区域和订购区域的匹配比较次数将与 n 平方呈正比，即算法的时间复杂度为 o(n2)。在系统的规模较大时，算法的执行性能降低，影响仿真系统的正常运行，不适合大规模复杂仿真系统。 .2 基于网格基于网格 ddm 算法算法 基于网格的 ddm 方法提供了一种相对简单的区域匹配和确定网络连接的方法33,34,35。该方法将路径空间划分成 n*n 的网格，每个网格的维数等于路径空间的维数，并为每一个网格分配一个组播地址。发布区域与订购区域的比较是通过将发布区域和订购区域映射到网格上，而不是直接匹配，当发布区域和订购区域覆盖了同一个网格，就确定发布区域和订购区域重叠，并通过该网格的组播地址进行数据传输。 p1 s1s2 图 2-3 基于区域的方法第二章 数据分发管理算法 110 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 图 2-4 是一个二维路径空间，被划分成大小相等的 4*4 网格。图中有五个发布区域 p1、p2、p3、p4 和 p5，一个订购区域 s1。根据基于网格的 ddm 算法思想，将所有的发布区域和订购区域映射到网格上，结果是：p1 覆盖了网格 c11，p2 覆盖了 c14，p3 覆盖 c4，p4 覆盖 c9、c10，p5 被映射到了网格 c2、c3、c6 和 c7，s1 覆盖了六个网格 c6、c7、c10、c11、c14、c15。根据区域是否覆盖相同的网格得到匹配结果 c6(p5,s1)、c7(p5,s1)、c10(p4,s1)、c11(p1,s1) 、c14(p2,s1)。 基于网格的 ddm 算法易于实现，且健壮性较好。这种方法对区域重叠不是直接判断，而是隐式地通过对固定划分的网格操作来实现区域匹配的判断，因此数据过滤计算开销低。 但网格法也存在不足之处34,35，具体如下： （1）存在虚假连接。由于受网格固有精度的限制，邦员有可能接收到不感兴趣的无关数据。如图 2-4 中，p4 与 s1 虽然覆盖了同一个网格 c10，但是实际上 p4与 s1 并没有重叠关系，但是发布区域 p4 的数据会通过 rti 发送给订购区域 s1，这样会降低数据过滤的精度。 （2）存在冗余连接。当发布区域和订购区域覆盖了一个以上的相同网格时会产生冗余连接。图 2-4 中 p5 与 s1 覆盖了一个以上的网格 c6，c7，因此发布区域p5 的数据会经两次传送给订购区域 s1，造成了网络资源和处理机资源的浪费。 网格划分的大小会影响算法的执行时间和匹配精度。网格划分过大会减少匹配次数加快执行速度但会降低匹配精度导致虚假链接的增多。减小网格划分会提高匹配精度，但计算量加大会降低执行速度同时会产生大量的冗余连接，增加数据的冗余传输量。 经过多年的研究，许多学者在以上两种经典算法的基础上提出了多种改进的方法： 分层 ddm 方法、 混合 ddm 方法、 变尺度动态网格 ddm 方法、 混合动态 ddm p3 p5 p4 p2 p1图 2-4 基于网格的方法 s1 hla 中数据分发管理算法的研究与实现 12方法等。 另一种经典 ddm 算法是由 c.razy 等人提出的基于排序 ddm 算法， 本文对其进行了改进，见第三章。 2.52.5 本章小结本章小结 本章论述 hla 的相关概念和组成，以及 ddm 服务的概念和实现原理。hla中不同的数据过滤实现方式会有不同的数据过滤效果。因此可以按照接口定义开发出不同实现的 ddm 算法，或对已有方法进行改进和完善，以提高数据过滤机制的执行能力，适应不同的仿真应用系统。本章重点研究分析了经典的基于区域和基于网格的 ddm 算法的实现原理及其优缺点。 第三章 改进的排序 ddm 算法 13第三章第三章 改进的排序改进的排序 ddm 算法算法 3.13.1 基于排序的基于排序的 ddm 算法算法 基于排序的 ddm 方法36,37是将发布区域和订购区域在某一维上的高低坐标值在该维度上进行投影，若发布区域高低坐标范围和订购区域的高低坐标范围有重叠，就表明发布区域和订购区域在该维上相交。对所有的维进行上述处理，当且仅当发布区域和订购区域在所有维上都重叠，该发布区域和订购区域才相交。 基于排序的 ddm 算法需要建立两个集合37,38：updateset 和 subscribeset。这两个集合用来处理当前处理结点所属区域的重叠信息。初始时，这两个集合为空集。若当前处理的是发布（或订购）区域的低结点，该发布（或订购）区域被添加到发布（或订购）区域集 updateset 中；若当前处理的是发布（或订购）区域的高结点，该发布（或订购）区域从 updateset（或 subscribeset）中删除，同时该发布（或订购）区域和 subscribeset（或 updateset）中的所有订购（或发布）区域重叠，重叠信息被记录在一个 m*n 矩阵中。这个 m*n 矩阵是用来存储发布区域和订购区域在同一维上的重叠信息。它的行代表发布区域的编号，列代表订购区域的编号。通过所有维上的区域相交信息矩阵进行“与”操作，判断发布区域和订购区域在所有维上是否相交。 图 3-1 是一个二维路径空间的示意图，图中有两个邦员 f1=(p1),(s1)，f2=(p2),(s2)。si 区域在 x 轴上的高低坐标表示为(xsi, xsi),在 y 轴上的高低坐标表示为(ysi, ysi)。 图 3-1 基于排序的 ddm 算法 ys1 yp1 yp2 yp2 ys1 yp1 ys2 ys2 xp2xs2 xp2 xs2 xs1xp1 xp1 xs1 y s1 p1 p2 s2 x hla 中数据分发管理算法的研究与实现 14基于排序的 ddm 算法实现过程如下： （1）将 x 维、y 维的坐标点由小到大进行排序： x 维： xs1, xp2, xs2, xp2, xs2, xs1, xp1, xp1 y 维： ys2, ys2, yp1, ys1, yp2, yp2, yp1, ys1 分别建立发布区域集 updateset 和订购区域集 subscribeset。 同时为 x 维和 y 维都建立一个 2*2 的矩阵，分别用来存储 x 维、y 维的区域相交信息，初始化为 0。 （2）首先处理 x 维，初始化 updateset=，subscribeset= 1 xs1:xs1是 s1 的低边界点，将 s1 加入 subscribeset，即 subscribeset=s1； 2 xp2:xp2是 p2 的低边界点，将 p2 加入 updateset，即 updateset=p2； 3 xs2:xs2是 s2 的低边界点， 将 s2 加入 subscribeset， 即 subscribeset=s1， s2； 4 xp2: xp2是 p2 的高边界点，将 p2 从 updateset 中删除，即 updateset=。同时 p2 和 subscribeset 中的所有区域都重叠，即 p2 与 s1、s2 都重叠。因此 x 维的2*2 相交信息矩阵为 ； 5 xs2:xs2是 s2 的 高 边 界 点 ， 将 s2 从 subscribeset 中 删 除 ， 即subscribeset=s1。同时 s2 和 updateset 中所有发布区域重叠，但 updateset=，则x 维的 2*2 相交信息矩阵不变，即 ； 6 xs1:xs1是 s1 的高边界点， 将 s1 从 subscribeset 中删除， 即 subscribeset=。同时 s1 和 updateset 中的所有区域重叠，但 subscribeset=，因此 x 维的 2*2 矩阵保持不变，即 ； 7 xp1: xp1是 p1 的低边界点，将 p1 加入 updateset，即 updateset=p1； 8 xp1:xp1是 p1 的高边界点，将 p1 从 updateset 中删除，即 updateset=。同时 p1 和 subscribeset 中的所有区域都重叠，而 subscribeset=，所以没有订购区域和 p1 重叠。因此 x 维的相交信息矩阵保持不变，即 ； （3） 同理y维也进行如步骤 （2） 中的处理， 则y维的2*2相交信息矩阵为 ； （4）x 维的 2*2 相交信息矩阵与 y 维的 2*2 相交矩阵进行“与”操作，最后的区域重第三章 改进的排序 ddm 算法 15叠信息为 ，即区域匹配信息是 p2 与 s1 相交。 基于排序的 ddm 算法是利用这种高低界值排序所隐含的区域相交信息得到各区域匹配关系的。该算法每一次匹配都要对各维的界点进行排序，然后扫描有序表，获得单维度的区域相交信息矩阵，再通过所有维上的区域相交信息矩阵的“与”操作，获得区域相交信息。当仿真结点数增加，区域数目规模较大，且复杂系统维数增多时，算法对每一维上所有区域都进行重叠信息的判断并为每一维的重叠信息建立相交信息矩阵，需要大量的系统存储空间，同时算法的循环匹配计算次数多，降低了算法的运行效率和仿真系统的可扩缩性。 3.23.2 改进的排序改进的排序 ddm 算法算法 为解决排序 ddm 算法的不足， 针对原算法在时间效率和存储空间上的不足提出了一种改进的排序 ddm 算法38,39。算法基于如下原理：对区域在第一维上进行重叠判断，处理完成后得到 m*n 矩阵，矩阵中的内容为 0 或 1。算法只建立一个 m*n相交信息矩阵，后续操作只对该矩阵进行修改。对区域在第 2 维上进行重叠判断时，只对处理第 1 维后的矩阵中相交信息为 1 的元素所对应的区域信息进行该维上的重叠判断， 如果重叠则将矩阵中对应的元素内容加 1， 否则不进行修改。 重复上述步骤，直至所有维上的区域重叠匹配完成，此时 m*n 矩阵中与维数相等的元素的行列值，就表示该行列对应的发布区域和订购区域相交。 .1 算法原理算法原理 以图 3-1 中的区域分布为例，处理 x 维后，2*2 相交信息矩阵的结果如下表： （1）处理 y 维时，对 2*2 矩阵中元素为 1 的区域（p2，s1，s2）在 y 维的坐标值排列顺序： ys2, ys2, ys1, yp2, yp2, ys1 （2）updateset= ，subscribeset= 1 ys2：ys2是 s2 的低边界点，将 s2 加入 subscribeset，即 subscribeset =s2； 2 ys2： ys2是 s2 的高边界点， 将 s2 从 subscribeset 中删除， subscribeset = ，同时 s2 与 updateset 中的所有发布区域重叠，而 updateset= ，则没有发布区域与s2 重叠。 3 ys1：ys1是 s1 的低边界点，将 s1 加入 subscribeset，即 subscribeset =s1； hla 中数据分发管理算法的研究与实现 164 yp2：yp2是 p2 的低边界点，将 p2 加入发布区域集，即 updateset=p2； 5 yp2：yp2是 p2 的高边界点，将 p2 从 updateset 中删除，即 updateset= ，同时 p2 与 subscribeset 中所有订购区域重叠，即 p2 与 s1 重叠，因此 2*2 相交信息矩阵中对应的元素加 1，则 2*2 矩阵为 ； 6 ys1：ys1是 s1 的高边界点，将 s1 从 subscribeset 中删除，即 subscribeset = 。同时 s1 与 updateset 中的所有发布区域重叠，而 updateset= ，则没有发布区域与 s2 重叠。 （3）处理完该二维路径空间后，相交信息矩阵的元素为 。 相交的发布区域和订购区域是相交信息矩阵中内容等于 2 的行与列的编号，即p2 与 s1 相交。 算法针对原算法中相交信息矩阵占用的存储空间大和区域匹配判断的循环计算次数多的不足进行了改进。在存储空间上，改进的排序 ddm 算法只建立一个 m*n相交信息矩阵，后续区域匹配操作只在该矩阵中进行修改，减少了算法对存储空间的使用。在算法执行时间上，在对第一维进行重叠判断建立相交信息矩阵后，后续操作只处理前 n-1 次矩阵中元素等于 n-1 的行列所对应的区域， 其他情况则不处理，减少了算法的循环次数，同时无需进行大量矩阵的“与”操作，降低了算法执行时间。该算法在存储空间和算法执行时间上都进行了改进，提高了仿真系统的运行效率，适用于区域比较多的大规模分布式仿真系统。 3.2.2 算法描述3.2.2 算法描述 算法中用到的数据结构： struct guishu int c_v