HLA/RTI中区域匹配算法研究
|
摘要
分布交互仿真就是使同构和异构的仿真器在一个时间和空间相一致的环境中实现互操作，以完成特定的仿真任务。受应用需求的推动和相关技术的牵引，分布仿真技术有了很大的发展，正广泛应用于社会的各个领域。分布交互仿真经历了几个发展阶段。目前新一代的分布交互仿真体系结构—HLA被提了出来，它的目的是解决各类仿真应用之间的互操作以及仿真构件的可重用，以满足未来仿真高效灵活的需求。运行时间支撑结构RTI是HLA的核心，它提供了一系列用于仿真互联的服务，为实现分布交互仿真的可扩充性提供支撑。
复杂大系统的仿真通常是建立在网络环境上的，并且要求系统在规模上有良好的可扩缩性，即随着系统规模的增加，计算和通信的开销不会影响仿真系统的正常运行。而RTI中的数据分发管理DDM就是专门为实现数据过滤而设计的。它根据仿真实体之间的数据供求关系完成仿真应用之间的数据转发，减少了数据通信量，同时也降低了仿真节点机的数据处理开销，缓解了规模增长引起的系统资源耗费急剧上升的趋势。
从1995年10月，美国国防部DoD在其制订的建模与仿真主计划MSMP中提出HLA以来，HLA标准一直在不断的改进之中。目前较为成熟的两个版本是DoD HLA V1.3与IEEE 1516，并且IEEE1516有取代DoD HLA V1.3作为HLA的最终标准。本文首先分别列举了两种标准在规则、接口规范和对象模型模板三方面内容上的不同点，重点讨论了在DDM方面的改进，并分析了这些改进可能带来的好处。
DDM使用区域信息描述实体间的数据供求关系，通过区域匹配确定实体的感兴趣集合，因此区域匹配是实现数据过滤的基础，区域信息匹配计算的复杂度是影响过滤开销的一个关键因素。文中从纯算法的角度对区域匹配过程的复杂度作了详细的分析，并以IEEE1516标准为基础，结合其中区域的特点，提出了一种单维步进的区域匹配算法。这种算法充分利用了区域变化过程中的历史信息，对连续变化的区域可以大大减少匹配的次数，降低了区域匹配计算量。
由于PTI是一个整体，不可能把DDM服务单独拿出来进行实现，因此结合此课题积极开展了基于IEEE1516标准的RTI原型的设计与实现。本课题重点对DDM中的区域匹配算法进行了研究，并实现了DDM的接口服务及声明管理、对象管理等其他服务中与数据分发管理相关的接口服务。
DIS(Distributed Interactive Simulation) provide a common architecture for various simulations' cooperation to achieve a given goal. DIS has a great development and is applied to many fields.At present,the new generation architecture of the distributed interactive simulation,HLA, comes forth.lts purpose is to facilitate interoperation among simulations and promote reuse of simulations and their components. Run-time Infrastructure(RTI) software is the core of HLA.lt offers a set of services to support the HLA simulations.
The simulations of complex systems are commonly constructed based on the network. Moreover.the simulation systems must be easily scalable.That is to say, The consuming of computing and communicating resources will not affect the simulation systems' running as the expanding of the systems' scale.In RTI,DDM is specially designed to filter data.DDM tranmits the data according to the supply and demand relation among simulation entities.lt can largely reduce data traffic,and reduce the spending on data processing at the same time.
In October of 1995, the HLA specifications is developed by the U.S. Department of Defense(DoD) in M&S Master Plan and under changes from then on. Now there are two muture HLA versions: the new IEEE 1516 version of the HLA Specifications and the previous U.S. DoD HLA version 1.3 (HLA VI.3) specifications,and IEEE1516 will be the final vesion of HLA.This paper introduces the differences between two specifications,especially about DDM,and analyses the possible benefit because of these improvement.
DDM use region info to describe the supply and demand relation among simulation entities.confirm the aggregate which entities are interested in by region matching.Therefore region matching is the basic of data filtering.This paper discusses detailedly the complexity of region matching process from the point of view of the pure arithmetic and develops a rapid matching arithmetic according to the characteristic of region in IEEE1516.
RTI is an integral software system and DDM is only a component part.So this paper discusses the design of RTI prototype based on IEEE1516. We lay a strong emphasis on the study of region matching arithmetic, and implement the interface specification of DDM and some other related interface.
复杂大系统的仿真通常是建立在网络环境上的，并且要求系统在规模上有良好的可扩缩性，即随着系统规模的增加，计算和通信的开销不会影响仿真系统的正常运行。而RTI中的数据分发管理DDM就是专门为实现数据过滤而设计的。它根据仿真实体之间的数据供求关系完成仿真应用之间的数据转发，减少了数据通信量，同时也降低了仿真节点机的数据处理开销，缓解了规模增长引起的系统资源耗费急剧上升的趋势。
从1995年10月，美国国防部DoD在其制订的建模与仿真主计划MSMP中提出HLA以来，HLA标准一直在不断的改进之中。目前较为成熟的两个版本是DoD HLA V1.3与IEEE 1516，并且IEEE1516有取代DoD HLA V1.3作为HLA的最终标准。本文首先分别列举了两种标准在规则、接口规范和对象模型模板三方面内容上的不同点，重点讨论了在DDM方面的改进，并分析了这些改进可能带来的好处。
DDM使用区域信息描述实体间的数据供求关系，通过区域匹配确定实体的感兴趣集合，因此区域匹配是实现数据过滤的基础，区域信息匹配计算的复杂度是影响过滤开销的一个关键因素。文中从纯算法的角度对区域匹配过程的复杂度作了详细的分析，并以IEEE1516标准为基础，结合其中区域的特点，提出了一种单维步进的区域匹配算法。这种算法充分利用了区域变化过程中的历史信息，对连续变化的区域可以大大减少匹配的次数，降低了区域匹配计算量。
由于PTI是一个整体，不可能把DDM服务单独拿出来进行实现，因此结合此课题积极开展了基于IEEE1516标准的RTI原型的设计与实现。本课题重点对DDM中的区域匹配算法进行了研究，并实现了DDM的接口服务及声明管理、对象管理等其他服务中与数据分发管理相关的接口服务。
DIS(Distributed Interactive Simulation) provide a common architecture for various simulations' cooperation to achieve a given goal. DIS has a great development and is applied to many fields.At present,the new generation architecture of the distributed interactive simulation,HLA, comes forth.lts purpose is to facilitate interoperation among simulations and promote reuse of simulations and their components. Run-time Infrastructure(RTI) software is the core of HLA.lt offers a set of services to support the HLA simulations.
The simulations of complex systems are commonly constructed based on the network. Moreover.the simulation systems must be easily scalable.That is to say, The consuming of computing and communicating resources will not affect the simulation systems' running as the expanding of the systems' scale.In RTI,DDM is specially designed to filter data.DDM tranmits the data according to the supply and demand relation among simulation entities.lt can largely reduce data traffic,and reduce the spending on data processing at the same time.
In October of 1995, the HLA specifications is developed by the U.S. Department of Defense(DoD) in M&S Master Plan and under changes from then on. Now there are two muture HLA versions: the new IEEE 1516 version of the HLA Specifications and the previous U.S. DoD HLA version 1.3 (HLA VI.3) specifications,and IEEE1516 will be the final vesion of HLA.This paper introduces the differences between two specifications,especially about DDM,and analyses the possible benefit because of these improvement.
DDM use region info to describe the supply and demand relation among simulation entities.confirm the aggregate which entities are interested in by region matching.Therefore region matching is the basic of data filtering.This paper discusses detailedly the complexity of region matching process from the point of view of the pure arithmetic and develops a rapid matching arithmetic according to the characteristic of region in IEEE1516.
RTI is an integral software system and DDM is only a component part.So this paper discusses the design of RTI prototype based on IEEE1516. We lay a strong emphasis on the study of region matching arithmetic, and implement the interface specification of DDM and some other related interface.
引文
[1] 黄柯棣，张金槐等．系统仿真技术．国防科学技术大学出版社．1998
[2] IEEE Standard for Modeling and Simulation(M&S) High Level Architecture(HLA)—Frame and Rules. 1EEE Std 1516-2000, September 2000.
[3] IEEE Standard for Modeling and Simulation(M&S) High Level Architecture(HLA)—Federate Interface Specification. IEEE Std 1516.1-2000, September 2000.
[4] IEEE Standard for Modeling and Simulation(M&S) High Level Architecture(HLA)—Object Model Template(OMT) Specification. IEEE Std 1516.2-2000, September 2000.
[5] High Level Architecture Run-Time Infrastructure Programmer's guide 1.3 version 6, DMSO,Mar. 12, 1999
[6] U.S. DoD. High-Level Architecture—Framework and Rules, Version 1.3. February 1998.
[7] U.S. DoD, High-Level Architecture—Federate Interface Specification. February 1998.
[8] U.S. DoD. High-Level Architecture—Object Model Template Specification, Version 1.3.
[9] 史扬．新一代仿真技术框架HLA／RTI中数据过滤技术的研究与实现．国防科技大学博士学位论文．1999
[10] Mr. Gary M. Lightnet, Mr. Robert Lutz, Mr. Reed Little "The IEEE HLA Standards:The Evolution from U.S. DoD HLA V1.3", Proceedings of the Fall 2000 Simulation Interoperability Workshop, Orlando FL.
[11] Katherine L. Morse, "DDM Improvements for IEEE Standard 1516", 1999 Spring SIW
[12] Mikel D. Petty. "Geometric and Algorithmic Results Regarding HLA Data Distribution Management Matching". 2000 Fall SIW.
[13] Mikel D. Petty. "Computational Complexity of HLA Data Distribution Management".
[14] Mikel D. Petty, "Data Distribution Management Specifications 1.3 And 1516 Are Equivalently Powerful", Proceedings of the Spring 2001 Simulation Interoperability Workshop
[15] Katherine L.Morse, Jeffrey S.Steimnan. "Data Distribution Management in the HLA Multidimensional Regions and Physically Correct Filtering".
[16] 曲庆军，杨建池，黄柯棣。关于DDM1516与DDM 1.3的研究，计算机应用，2002．6
[17] 卢开澄．计算机算法导引．清华大学出版社．1996
[18] 林新，王行仁，彭晓源。运行时间框架(RTI)设计中数据管理的研究，系统仿真学报，2001．3
[19] 万江华，史军慧，姚益平，卢锡城，时向泉。一种基于历史的DDM实现方法，计算机工程与应用，2001．15
[20] 张立昂．可计算性与计算复杂性导引．北京大学出版社．1996
[21] 周培德．计算几何——算法分析与设计．清华大学出版社．2000
[21] 严蔚敏，吴伟民．数据结构．清华大学出版社．1997
[22] 钱能．C++程序设计教程．清华大学出版社．1999
[23] Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides.设计模式．机械工业出版社 2000
[24] Bill Helfinstine, Deborah Wilbert, Mark Torpey, Wayne Civinskas. "Experiences with Data Distribution Management in Large-Scale Federations" ,2001 Fall SIW
[2] IEEE Standard for Modeling and Simulation(M&S) High Level Architecture(HLA)—Frame and Rules. 1EEE Std 1516-2000, September 2000.
[3] IEEE Standard for Modeling and Simulation(M&S) High Level Architecture(HLA)—Federate Interface Specification. IEEE Std 1516.1-2000, September 2000.
[4] IEEE Standard for Modeling and Simulation(M&S) High Level Architecture(HLA)—Object Model Template(OMT) Specification. IEEE Std 1516.2-2000, September 2000.
[5] High Level Architecture Run-Time Infrastructure Programmer's guide 1.3 version 6, DMSO,Mar. 12, 1999
[6] U.S. DoD. High-Level Architecture—Framework and Rules, Version 1.3. February 1998.
[7] U.S. DoD, High-Level Architecture—Federate Interface Specification. February 1998.
[8] U.S. DoD. High-Level Architecture—Object Model Template Specification, Version 1.3.
[9] 史扬．新一代仿真技术框架HLA／RTI中数据过滤技术的研究与实现．国防科技大学博士学位论文．1999
[10] Mr. Gary M. Lightnet, Mr. Robert Lutz, Mr. Reed Little "The IEEE HLA Standards:The Evolution from U.S. DoD HLA V1.3", Proceedings of the Fall 2000 Simulation Interoperability Workshop, Orlando FL.
[11] Katherine L. Morse, "DDM Improvements for IEEE Standard 1516", 1999 Spring SIW
[12] Mikel D. Petty. "Geometric and Algorithmic Results Regarding HLA Data Distribution Management Matching". 2000 Fall SIW.
[13] Mikel D. Petty. "Computational Complexity of HLA Data Distribution Management".
[14] Mikel D. Petty, "Data Distribution Management Specifications 1.3 And 1516 Are Equivalently Powerful", Proceedings of the Spring 2001 Simulation Interoperability Workshop
[15] Katherine L.Morse, Jeffrey S.Steimnan. "Data Distribution Management in the HLA Multidimensional Regions and Physically Correct Filtering".
[16] 曲庆军，杨建池，黄柯棣。关于DDM1516与DDM 1.3的研究，计算机应用，2002．6
[17] 卢开澄．计算机算法导引．清华大学出版社．1996
[18] 林新，王行仁，彭晓源。运行时间框架(RTI)设计中数据管理的研究，系统仿真学报，2001．3
[19] 万江华，史军慧，姚益平，卢锡城，时向泉。一种基于历史的DDM实现方法，计算机工程与应用，2001．15
[20] 张立昂．可计算性与计算复杂性导引．北京大学出版社．1996
[21] 周培德．计算几何——算法分析与设计．清华大学出版社．2000
[21] 严蔚敏，吴伟民．数据结构．清华大学出版社．1997
[22] 钱能．C++程序设计教程．清华大学出版社．1999
[23] Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides.设计模式．机械工业出版社 2000
[24] Bill Helfinstine, Deborah Wilbert, Mark Torpey, Wayne Civinskas. "Experiences with Data Distribution Management in Large-Scale Federations" ,2001 Fall SIW