变尺度动态网格法在数据分发管理中的研究

・５６・　计算机应用研究　２００６钲　

变尺度动态网格法在数据分发管理中的研究　

窦志武　一，邓贵仕　（１．大连理工大学管理学院，辽宁大连１１６０２３；２．沈阳炮兵学院，辽宁沈阳１１０１６１）　

摘要：在分析高层体系结构下数据分发管理机制实现的各种静态和动态方法的基础上，指出了仿真过程中时　间开销与数据过滤率是一对矛盾的因素，提高数据过滤率必然导致时间开销的增加。一个仿真系统不能只采用　一种固定的网格单元尺寸，而要随系统的不同动态改变网格的单元尺寸，以达到在最短时间消耗情况下得到最　高的数据过滤率。由此提出了一种变尺度动态网格法，在深入分析网格单元尺寸与更新时间、数据过滤率、接收　时间及排队时间的关系后，给出了该算法的数据方程及实现过程；最后在一个应用实例中对该算法进行了验证，　说明了该算法的有效性。　关键词：数据分发管理；网格；动态网格法；组播　中图法分类号：ＴＰ３９１．９　文献标识码：Ａ　文章编号：１００１—３６９５（２００６）１１．００５６—０３　

Ｄｙｎａｍｉｃ　Ｇｒｉｄ．ｂａｓｅｄ　Ｍｅｔｈｏｄ　Ｒｅｓｅａｒｃｈ　ｉｎ　Ｄａｔａ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｍａｎａｇｅｍｅｎｔ　ＤＯＵ　Ｚｈｉ—ＷＵ　．ＤＥＮＧ　Ｇｕｉ—ｓｈｉ　（１．Ｃｏｌｌｅｇｅ　ｏｆＭａｎａｇｅｍｅｎｔ，Ｄａｌｉａｎ　ＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，ＤａｌｉａｎＬｉａｏｎｉｎｇ１１６０２３，Ｃｈｉｎａ；２．ＳｈｅｎｙａｎｇＡｒｔｉｌｌｅｒｙＣｏｌｌｅｇｅ，ＳｈｅｎｙａｎｇＬｉａｏ—　ｎｉｎｇ　１１０１６１，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｐｏｉｎｔｓ　ｏｕｔ　ｔｈａｔ　ｔｉｍｅ　ｃｏｎｓｕｍｉｎｇ　ａｎｄ　ｄａｔａ　ｆｉｌｔｅｒｉｎｇ　ａｒｅ　ａ　ｐａｉｒ　ｏｆ　ｅｌｅｍｅｎｔ　ｃｏｎｔｒａｄｉｃｔｉｏｎ　ｅａｃｈ　ｏｔｈｅｒ　ｉｎ　ｐｒｏｃｅｓｓ　ｏｆ　ｓｉｍｕｌａｔｉｏｎ，ａｎａｌｙｚｉｎｇ　ｓｔａｔｉｃ　ａｎｄ　ｄｙｎａｍｉｃ　ｍｅｔｈｏｄｓ　ｏｆ　ｄａｔａ　ｄｉｓｔｒｉｂｕｔｅｄ　ｍａｎａｇｅｍｅｎｔ　ｍｅｃｈａｎｉｓｍ　ｂａｓｅｄ　ｏｎ　ｈｉｇｈ　ｌｅｖｅｌ　ａｒ—　ｃｈｉｔｅｃｔｕｒｅ，ｔｈｅ　ｈｉｇｈｅｒ　ｒａｔｅ　ｏｆ　ｄａｔａ　ｆｉｌｔｅｒ　ｉｓ　ｉｍｐｒｏｖｅｄ，ｔｈｅ　ｍｏｒｅ　ｔｉｍｅ　ｗｉｌｌ　ｂｅ　ｃｏｎｓｕｍｅｄ，ｖｉｃｅ　ｖｅｒｓａ．Ａ　ｄｉｓｔｒｉｂｕｔｅｄ　ｓｉｍｕｌａｔｉｏｎ　ｓｙｓ—　ｔｅｍ　ｓｈｏｕｌｄ　ｈａｖｅ　ａ　ｄｙｎａｍｉｃ　ｇｒｉｄ—ｂａｓｅｄ　ｍｅｔｈｏｄ　ｉｎ　ｄａｔａ　ｄｉｓｔｒｉｂｕｔｅｄ　ｍａｎａｇｅｍｅｎｔ，ｂｕｔ　ｎｏｔ　ａ　ｓｔａｔｉｃ　ｇｒｉｄ，ｔｈｕｓ　ｔｈｅ　ｓｙｓｔｅｍ　ｃａｎ　ｇｅｔ　ａ　ｈｉｇｈ　ｒａｔｅ　ｏｆ　ｄａｔａ　ｆｉｌｔｅｒ　ｏｎ　ａ　ｌｏｗ　ｃｏｎｓｕｍｅ　ｏｆ　ｔｉｍｅ．Ｓｏ　ｔｈｅ　ａｒｔｉｃｌｅ　ｐｒｅｓｅｎｔｓ　ａ　ｍｅｔｈｏｄ　ｏｆ　ｄｙｎａｍｉｃ　ｇｒｉｄ—ｂａｓｅｄ　ｍｅｔｈｏｄ　ａｎｄ　ｔｈｅ　ｃｏｎ—　ｓｔｍｃｔｉｏｎ　ｅｑｕａｔｉｏｎ　ｏｆ　ｔｈｅ　ｍｅｔｈｏｄ　ａｎｄ　ｔｈｅ　ｐｒｏｃｅｓｓ　ｏｆ　ｄｅｖｅｌｏｐｉｎｇ　ｉｔ　ｂａｓｅｄ　ｏｎ　ｆｕｒｔｈｅｒ　ａｎａｌｙｚｉｎｇ　ｔｈｅ　ｒｅｌａｔｉｏｎｓｈｉｐ　ｂｅｔｗｅｅｎ　ｔｈｅ　ｕｐｄａｔｅ　ｔｉｍｅ　ａｎｄ　ｄａｔａ　ｆｉｌｅｒ，ｒｅｃｅｉｖｉｎｇ　ｔｉｍｅ　ａｎｄ　ｑｕｅｕｅ　ｔｉｍｅ，ａｎｄ　ｖｅｒｉｆｉｅｓ　ｔｈｅ　ａｖａｉｌａｂｉｌｉｔｙ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｕｓｉｎｇ　ａｎ　ｅｘａｍｐｌｅ．　Ｋｅｙ　ｗｏｒｄｓ：Ｄａｔａ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｍａｎａｇｅｍｅｎｔ（ＤＤＭ）；Ｇｒｉｄ；Ｄｙｎａｍｉｃ　Ｇｒｉｄ—ｂａｓｅｄ　Ｍｅｔｈｏｄ；Ｍｕｈｉｃａｓｔ　

１　引言　高层体系结构（Ｈｉｇｈ　Ｌｅｖｅｌ　Ａｒｃｈｉｔｅｃｔｕｒｅ，ＨＬＡ）的数据分发　管理（Ｄａｔａ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｍａｎａｇｅｍｅｎｔ，ＤＤＭ）服务的基本目标是　减少消费数据仿真联邦成员的数据接收量。联邦成员指定他　们想要接收的数据类，通过使用声明管理服务来减少一定数量　的接收和发送，但在一个拥有大量对象或对象产生大量数据更　新的大规模仿真联邦中，声明管理服务并不能充分达到接收数　据的成员对数据减少的程度和时间的要求。在这种情况下成　员会利用数据分发管理服务来进一步限制成员对数据更新的　接收量。在大规模分布交互仿真中，ＨＬＡ指定的ＤＤＭ服务是　最新的减少数据流量的数据过滤机制。该机制还可以被称为　兴趣管理、相关过滤和数据分发　Ｊ。　过去的研究主要偏重于该机制的静态应用，目前的研究方　向主要是：①分布式动态结构；②灵活的通用目的过滤机制的　规范表述；③兴趣管理优化方法的研究，以降低其费用投入，特　别是通过组播技术。本文主要研究通过动态改变数据网格的　尺度，以优化ＤＤＭ服务的过滤能力，降低时间消耗。　

收稿日期：２００５—０９－１２；修返日期：２００５．１１－２８　基金项目：国家自然科学基金资助项目（７０２７２０５０）　２　数据分发管理服务实现方法的研究现状　２．１　数据分发管理静态方法及存在的问题　ＤＤＭ的目的是为联邦设计者提供比声明管理服务更精　确、更灵活的、用于确定联邦成员间信息流的工具　Ｊ，其最基　本的结构是路径空间。路径空间是一个多维坐标系统，通过该　坐标系统联邦成员（联邦是指分布交互仿真系统的一个仿真　子系统，联邦成员就是该系统中的仿真成员）既可以表达他喜　欢接收什么数据（订购），也可以声明他能送出什么样的数据　（公布）。ＤＤＭ是附加在声明管理服务上的，它通过区域（在　多维路径空间中的区域不是物理或地理上的区域，而是一个抽　象的多维体，它的维可以是任何有意义的量）进一步增加路径　空间的信息来实现对数据的过滤。ＤＤＭ的核心问题就是如何　进行区域匹配和组播地址的分配　。　ＤＤＭ使成员能够通过类或属性名来指定它们送出或接收　数据的类型，同时也缩小了特定数据实例的范围。联邦成员确　定联邦执行哪一个路径空间对它们是有意义的，并定义路径空　间的一部分为其特定区域或是成员特殊兴趣的逻辑范围　Ｊ。　这些区域的限定是通过在选择路径空间的一维或某些维，并通　过上下限来界定取值范围的。　成员指定一个订购区域，就是说成员通知ＲＴＩ（Ｒｕｎ　Ｔｉ

ｍｅ　维普资讯 http://www.cqvip.com 第１１期　窦志武等：变尺度动态网格法在数据分发管理中的研究　・５７・　

Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ，ＲＴＩ），他对落入该区域的数据感兴趣；成员指定　一个更新区域并与一个特定的对象实例相关联，就是成员向　ＲＴＩ承诺，他会保证当该实例的属性值发生变化时，这些更新　值能落入该更新区域。这暗示了成员会监视其当前拥有的属　性的变化。当对象的状态发生变化时，成员要么调整区域的上　下限，要么改变其关联的区域。　图１（ａ）显示了基于区域的静态方法中数据过滤的过程，　１为更新区域，Ｊｓ１，　为订购区域，这三个区域均处于同一个　二维的路径空间中。系统首先对更新与订购区域进行匹配，然　后ＲＴＩ对存在区域重叠的公布与订购方建立通信连接。在图　１中，　１与Ｊｓ１重叠，所以与　１关联对象的属性更新值会传给　创建区域ｓ１的成员；Ｕ１与Ｓ２没有重叠，则刨建区域Ｓ２的成　员将不会收到与　１关联对象的属性值更新。从这个过程可　以看出，这种基于区域的静态方法存在区域匹配次数过多、数　据过滤能力差及时间花费长的问题。Ｊｓ２虽然收不到从　１发　来的数据，取得了一定的发送方过滤，但是Ｊｓｌ仍然要接收大量　由　１发送来的不落在重叠区域内的无用数据，还需要花费大　量的时间处理无关数据，这促使了静态网格法的出现。静态网　格法是基于区域方法的扩充，在该方法中每个路径空间均被划　分为网格状，每个网格单元分配一个组播地址。对于更新与订　购区域有共同网格单元的才进行区域匹配，　１与　没有公共　网格单元所以不用进行匹配，这在一定程度上解决了区域次数　过多的问题。在数据过滤方面，只有重叠区域所覆盖的网格单　元的数据才发送给订购方。从图１（ｂ）可知，　１的更新数据只　有落在包含重叠区域的两个网格内的数据才发送给Ｊｓ１，而其　他数据则不会发送，可见在发送方的数据过滤率得到了进一步　的提高。但该方法存在一个问题：由于系统的组播地址是有限　的，随着系统的扩大，数据交换会随成员个数ｎ呈ｎ　增长，这　会造成系统组播地址的不足，从而引起组播地址的重用，这种重　用将会导致额外的接收方过滤。为了解决组播地址的重用问　题，有人提出了基于静态网格的动态组播地址分配方法。　匮　

（ａ）　（ｂ）　更新区域　订购区域　Ｉ重叠区域　图ｌ二维路径空间及区域　文献［４］中提出了一种基于静态网格进行区域匹配及基　于公布方动态分配组播地址的算法。该算法的思想是，在静态　网格算法的基础上对组播地址的分配采用基于公布方的组播　地址分配的方案，只有公布方的订购者非空时才为该公布方分　配组播地址。该算法在一定程度上减少了区域的匹配次数，有　效地利用了组播地址这种稀缺资源。但它存在网格单元尺寸　的优化问题，静态网格单元尺寸的大小对区域匹配次数和数据　的过滤率均有明显的影响。通过对原问题的研究分析，本文提　出了一种基于匹配次数和数据过滤率的成本函数优化算法来　动态划分网格，以求得对不同仿真系统的最优网格单元尺寸，　从而在降低匹配次数的同时达到最佳的数据过滤效果。　２　２基于延迟时间ｆｍ。　的动态组播地址分配法数据分发管理　该算法的思想来源于组播是介于点对点传播消息与广播　方式传播消息之间的一种方式。点对点方式消息传播准确，没　有无用数据传播，不需数据过滤，但数据传播费时；广播方式传　播消息则是另一个极端，消息传播快，但接收方需要处理大量　无用数据。该算法将最大的潜在延迟时间ｔｍａｘ作为算法的衡　量标准，其目标是对于一个有ｎ节点的系统，当分成ｍ个组播　时，消息到达其接收节点时的时间不超过ｔ…，即　ｔ　ｍａｘ≥ｔ　＋ｔＰ＋ｔｒ＋ｔｇ　其中，ｔｍａｘ为最大潜在延迟时间；ｔ　为消息送出时间，并假设每　个成员的消息送出时间是相等的；ｔ，为消息接收时间，并假设　每个成员接收一个消息与处理一个无用消息的时间是相等的；　ｔ　（　，　）为消息的传递时间，／＝，　分别代表分布和订购成员；　ｔ　为消息的排队时间；ｔ　为送出时的消息延迟时间。　通过该算法来动态分配组播地址进行数据分发，可以达到　每个消息到达其接收成员时均不超过一个既定的时间，对于实　时仿真有一定的作用。但在该算法的设计过程中并未考虑数　据过滤问题，所以仿真系统的实际数据过滤情况如何并未给出　一个详细的描述，因此有必要对该算法在数据过滤方面进行进　一步的研究。　３　变尺度动态网格法的提出　３．１　变尺度动态网格法的思想　通过前面各种算法的分析可知，提高仿真系统数据分发的　无关数据过滤率与时间的消耗是一对相互矛盾的因素。过滤　率的提高必然导致系统的时间消耗增加，数据传输延迟也就相　应增加，这在一定程度上会使数据的到达远远落后于系统的推　进，导致数据不可用，仿真误差增加　“　。为此本文提出了基　于时间与系统过滤率的变尺度动态网格法。该算法的最佳网　格单元尺寸的判别标准为ｔ…，所要达到的目标是在尽可能地　提高系统的数据过滤率的情况下降低系统的时间消耗。为了　叙述上和直观上对问题的描述简便，本文将路径空间和区域抽　象为一个二维矩形，事实上路径空间是一个多维体，区域是有　序数据对的集合，区域的每一对数据描述了该区域在路径空间　一维上的上下限。算法的参数有：ｔ　为单个消息排队时间，与　队列长短无关；ｔ，为数据接收时间，并假设接收成功；ｔ　为网格　单元的更新时间；ｔ　为单次区域匹配时间；ｔ　为数据发送时间；　ｔｐ为数据传输时间；Ｓ　为路径空间面积；ｎ为路径空间的横向　划分网格数；ｍ为路径空间的纵向划分网格数。　成员处理一个无关数据的时间与接收一个相同数据的时　间概略相等。　对于一个面积固定的路径空间，当网格划分得越多时，网　格的更新时间也就越长，而公布区域与订购区域同在一个网格　的几率也就越小；同样发送方的数据过滤率也会相应提高，则　在组播数据包中发送的无关数据就会相应减少，从而接收方消　耗在数据接收上的时间就会减少，数据的排队时间也会降低。　通过对一个面积固定的路径空间划分不同网格时进行仿　真，可得出整个路径空间网格单元的更新时间与网格单元数基　本成正比：胁×ｔ　，而匹配次数与网格单元的面积近似成正比，　则匹配时间可近似为ｋ　Ｘ　Ｓ　ｔ　／肌，ｋ为系数。仿真结果如图２　所示。　在发送方，

即公布数据的仿真成员方的数据过滤率是与网　维普资讯 http://www.cqvip.com