基于索引排序的快速动态区域匹配算法

《基于索引排序的快速动态区域匹配算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《计算机学报》2009年7期基于索引排序的快速动态区域匹配算法姚益平1)张颖星1)陈欣2)季立春1)1)（国防科技大学计算机学院长沙410073）2)（北京邮电大学计算机学院北京100876）摘要：数据分发管理实现基于值的过滤，可进一步减少大规模仿真中盟员接收冗余数据的可能性和网络中的数据流量。数据分发管理实现的关键是区域匹配算法的实现，高效、精确的区域匹配一直是数据分发管理追求的目标。现有的区域匹配算法如直接匹配法、网格法、基于分类的算法等都不很理想，或者过滤效果不佳，或者耗时较大，难以适应大规模分布式仿真的需

2、要。论文针对在区域比较多的大规模分布式仿真系统中，区域大都需要随着仿真的推进而频繁地被动态修改的实际特点，提出了一个基于索引排序的快速动态区域匹配算法——IOBM算法，该算法将范围的上下界分别各用一个节点表示，使用指针数组来索引每一维上的范围节点，数组元素的下标值表示对应的节点值，利用区域范围更新前后的信息，将匹配限定在移动区间之内，通过对移动区间之内的链表进行直接操作来完成匹配工作，因而大大减少了匹配计算的时间，实现了高效、精确的动态匹配。该算法尤其适合区域比较多的大规模分布式仿真的需要。关键词：高层体系结构（

3、HLA）；运行支持环境（RTI）；数据分发管理（DDM）；区域匹配；动态中图分类号：TP391.9文献标识码：ADynamicRegionMatchingAlgorithmBasedonIndex-OrderYAOYiping1)ZHANGYingxing1)CHENXin2)JILichun1)1)(ComputerCollegeofNationalUniversityofDefenseTechnology，Changsha410073，P.R.China)2)(SchoolofComputerSciencea

4、ndTechnology,BeijingUniversityOFPostsandCommunicationsBeijing100876,P.R.China)ABSTRACT:TheHLADataDistributionManagement(DDM)serviceprovidesanabstract,application-drivendatafilteringcapability.Itcanreducethetransmissionandreceptionofirrelevantdata.Thekeyproble

5、mofitsimplementationisregionmatchingalgorithm.Thecurrentalgorithmssuchasdirectlymatching,grid-based,andsort-basedapproachareallnotsoperfect.Theyareeithertimeconsumingorinaccuracyinfiltering,andaredifficulttosupportlarge-scalesimulation.Aimingatthecharacterist

6、icoffrequentlyregionchanginginlarge-scalesimulationsystems,amoreeffectivematchingalgorithmbasedonintersectinginformationofregionmovingisproposed.Itrepresentstheupperboundandlowerboundofarangewithtwonodes,andusestwoindexedorderedtablestostorethepublicationands

7、ubscriptionnodesofadimensionrespectively.Itusesrangeintersectinginformationduringarangemoving,andlimitsthematchingcomputingonlyintheareaofmoving.Therebyitcangreatlydecreasethecandidaterangesthatneedtodomatchingcomputing,thuscandecreasethematchingcomplexitygre

8、atly,andreachprecisematchingwithhighperformance.Thisalgorithmisextremelyfitfortheneedoflarge-scaledistributedsimulationthathasalargenumberofregions.KEYWORDS:HighLevelArchitecture;RuntimeI