о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 8 Vol.36 No.8 1999



ֲ鲥˻ƵһӦ²
ʷ衡ʿҢų
ժҪֲЧԡԡɿԡȫԵŵ㣬ھ¡̡ҵŹ㷺Ӧǰ.ŷӦڹȼϵķչķֲΪδķչƣٵҪսϵͳ.ݹ˻ǽϵͳԵҪ;ʵйЧʺ͹˿ƽϵ˻Ƶ.зԼϵͳԵҪأʵֵĹ۵һ˻Ƶۺ׼򣬲ڴ˻˹˻ƵӦ²ԣ˹˻ƵĹЧʺͿƽ.
ؼʡֲ棬ԣ·ռ䣬ݹˣ鲥ͨ
ͼšTP391.9
AN ADAPTIVE REGION UPDATING POLICY FOR MULTICAST-BASED FILTERING SCHEME IN 
DISTRIBUTED INTERACTIVE SIMULATION
SHI Yang, LING Yun-Xiang, JIN Shi-Yao, and ZHANG Chen-Xi
(Institute of Computer Science, National University of Defense Technology, Changsha 410073)
AbstractDistributed interactive simulation has broad applications in various fields, such as military, engineering, commerce etc. because of its advantages of efficiency, economy, safety and security. Large scale distributed interactive simulation based on Internet is the future direction. But it faces the problem of system scalability because of its requirements for high network bandwidth and computation capacity, which is caused by redundant data when the system's scale increases. This situation can be alleviated to great extent by data filtering based on multicast. In this paper the key factors are analyzed, which limit the system scalability from the point of view of system resources and determine a criterion which can be used to evaluate the performance of a filtering scheme. Based on the above work, a new scheme called adaptive region updating algorithm is proposed to balance the filtering spending and filtering efficiency. 
Key wordsdistributed interactive simulation, scalability, route space, data filtering, multicast
1
ֲ1ԭϵͳרҵԼ缼Ϊλ÷ֲͬ칹ķһͳһĻУʵ֮Ļض.ֲΪӡۺϵͳоơ֤ṩ˿.Ŀǰֲ㷺Ӧھ¼񾭼õĸϰģѵֲʽЭ̡нͨơϽϷ.
ϵͳԴ㴦ԴԼϵͳԵҪ.еӲԴ£ȡЧԴķģ̬ʹϵͳӦϴģǷֲĹؼ.鲥ͨŵĹ˻ʵϵͳԵҪ;ЧĹ˻ЧݵĲͽ,Ӷ󽵵ͶԴʹԴѹĹ˿һ棬һ³.з˹˻Ƶ׼ڴ˻˻Ӧ²ԵĹ˻RBF-ARUûܸݷеķݶ̬Ϣʣʹ˻µݹЧʺͿﵽƽ.
2ֲϵͳ⼰;
2.1ϵͳԼ鲥ͨŵݹ˻
δķֲǽϣҪֳ֧ǧʵУ2ݣٵһҪϵͳģĿ.ϵͳģҪϵͳԴҪԴԴƣдԴҪڷʵģͼ㡢շ紦ҪĹݹ˿ȣ.ŷֲģӣȻӴ˷֮Ϣ¶ԴʹԴļ.ͳDISЭù㲥ʽͨţκһʵϢ״̬ϢϢҪԹ㲥ʽbroadcast͵н㣬ֹ㲥ͨŷʽϵͳģ3.
ݷֲص㣬ʹù˻ƣ4ݿɴ󻺽ԼԴ.֧ݹ˵Ƿʵľֲԣ5ݣʱĳһʵֻϵͳвʵ巢ǳƴӼΪʵġȤȤڲʵ֮Ҫ״̬ͽϢ.ʵǺܳģģսеĽս̽ȣԹɸȤ.
ֲʵȤϵĴڣζһʵݱ뷢͸ʵ壬ͬʱ֤ⲿʵ岻մݣԼٷݵĽ.ֵ͵һԶͨģʽʺ鲥6ݣmulticastʹã鲥ͨŵĹ˻ƿɴﵽĿģһǾܼٲݵĲԼռãǽͷʱĴ.ĿĶϵͳĿԵ.
2.2HLA¹˻Ƶʵ֣Ѱַ·
˻ҪȷݷͷͽշӳϵΪѰַ.ڴ˻Ͻ鲥ַȷԴĿĵ·,ԿݵĴΧ.Ѱַ·ɿɲòͬķǵϹɲͬĹ˻ʵ.߲ϵṹHLA(high level architecture)141995һֲ漼ܣз漼(DISЭALSPЭ)Ĳ㣬ֲ滥ԺͿ.HLAȡDISЭΪһֲı׼.HLA֧ݹ˵Ļ·ռRSrouting space7.RSһĶάϵͳҪأ(1)ϵͳά(2)Ӧϵͳÿһά·ڱȤꡢ˶ٶȵȣ(3)·ÿάϵĶ壨緶Χλ̶ȵȣ.ʵͨRSⲿ͵ԼⲿյݵͨRSеӼռregionʵ֣ʵͨpublish regionͶsubscribe regionͺͽݵԼ.ÿʵͺͽյݶӳϵ.
Ѱַʱʵݹ֮ΪϢȷԴһĿ֮ӳϵͨ빫ƥжǷཻ·ݴӳϵಥַָͷ˵ַݣշӦ鲥ַ.
3˻
3.1˻´ɷ
洦ɣÿļΪlÿļԴҪ3ɣʵģ͵ļ㿪PsimݷͽմPcomm˻ƿPflt

У

NlNrֱΪԶʵĿOlOrֱΪʵԶʵģ͸أOintΪԶʵ彻ÿ.ģͼʵȤģƣķģ͸Psimһһ̶Ͻ.

ֱΪͺͽյϢOsndOrcvֱΪһηͺͽϢĴ.
PfltϢմ͹˼㿪ɱʾΪ

,ֱΪͺͽյĹϢOcalΪڹϢƥ㿪ǵĺ.
3.2˻ۺ׼
˻ƵʹýͨſPcommȴ˹˿Pflt˹˻ʵʱۺϿǹʹ֮ƽ.ЧĹ˻ڴPcommͬʱӦʹPfltӹ˴ĺô.ڿǹ˻Чʺʹ۵£Ƕ˻´Ϊ

УΪ˻ݷ͡ΪϢ͡OcalΪ˻Ƶļ㿪FsndFrcvĺOnetΪһݷͻ͵紦.
ִƽ̨УܲϵͳӰ죬ͨſΪԼϵͳܵҪƿֲ΢ķٷչ.Ϊ򻯷ǺOcalҪ翪ϵͳӰ죨ʵƥķϲȣƪۣ.нƵĴۺ翪

ʽ6ʵطӳ˻صĴ۹˻Ƶ.
4Ӧ¹˻RBF-ARU
4.1͹˻Ʒ
ף8˻(grid-based)Ĺ˻GBF˼ǣ·ռ仮ֳȵ񣬲Ϊÿһ鲥ַ빫ཻӦ鲥ַݣ߼붨ཻӦ鲥ַ.GBFʵּ򵥣շ轻Ϣƥ㣬ȱǣ ȱٹϢͷäĿ͹ݶǷ붨ཻļ޹ף ͬһӦ鲥ַظͬݣܳ鲥ͨŵŵ㣻 Ӱƥ侫ȣӰЧʣ ಥַϴ󣨸άĿ˻ʵ.ƵȱǲӦڹģϴķϵͳ.
ף9˻ڽշ(receiver-based)Ĺ˻RBF˼ǣͷⲿʵݵķָݵ·.GBFͬRBFҪ佻Ϣ˫ݹϢƥָݵķͺͽ.RBFƵŵǣɸݹ˫ԸݷͶݲͬһݵԪֻһ鲥ͣ鲥ַнϸߵʹЧ.ȱҪϢƥ.ף9ϸȽGBFRBFֻƵĹЧ.
4.2Ч˿Ȩ
˻ƵһҪָǹЧʣĳһĹЧʶΪ

ΪݽݣΪù˻ʵݽ.
ϵͳģƽЧΪ

RBFƾнϸߵĹЧʣҪȱǷҪ㹻ĹϢζŷнϸߵĹ˿ⲿϢմӦƥ㣩.ڹϢԹ㲥ʽ͸н㣬ĳЩʵĹϢƵʹʱ¹ϢļӶRBFƵŵۿ.͹Ϣһ;ͨ򱣻Խʣ³ʱһϢķͣף10ϸ.RBFнϸߵݹЧʣҲ˹˿.Ϊǲģֶо˹Ч˿֮Ĺϵģ⻷5ڣģϵͳģΪN=100ʵٶȹ̶䣩.
ͼ1RBFűߴ磨KMӣЧ½ζŸݽգͼ2ڱߴʱݽշϢı仯.ͼ2ɼЧʺ͹˿ɷȹϵ.ͼ3ʾ˴ۺϿ乹ɳɷ汣ߴ仯.ͼ3ɼǹЧԽԽãűļСϢӵ¹Ϣʹܿ.˵ֻѡȡʵ򱣻ߴ磬ʹ˻Ƶ.


ͼ1ߴԹЧʵӰ


ͼ2ߴݼϢӰ


ͼ3򱣻ʱ翪
4.3Ӧ¹˻ԭ
4.2ڵķ֪ҪʹЧ˿ﵽƽ;Ϊʵѡȡʵ򱣻ӶЧؿʣʹ˻´ܿС.ڷӦʵĶԺͶ̬ԣ11ݣΪÿʵѡһ̶Һʵı.ΪЧϢĸʣʹЧ˿ﵽƽ⣬һֻӦ²ԣadaptive region updateĹ˻RBF-ARU. RBF-ARUԭǸʱķݶ̬ÿʵ򱣻ߴ磬Կĸ.߼ṹͼ4ʾ.


ͼ4RBF-ARUʾͼ
RBF-ARUÿһΪRUCAregion update control agentḶ̌RUCAԵؼرʣռָؼԶʵʵı仯.RUCA¼ݰݷͽ仯Ϣ仯ԼЧʱ仯.ͳֵÿʵ򱣻Сʹ˻ƵۺЧ.RUCAԵͳݣ㵱ǰշ翪͹Ϣ翪жϵǰ򱣻ߴǷʣǰ翪ӳһֵҹϢɷӸշɷ˵Ϣ仯̫죬ߴСӱߴ磻֮ݹЧ½̫µܿӣС򱣻ߴ.Ӧ㷨£
/* 㷨Adaptive Region Updating Algorithm(ARU) */
/* 㷨ÿϣÿNʵ */
/* Ҫ 
TRUCAڣ
ʵiܿ仯
ʵiշ仯
ʵiĹϢ仯. */
Loop 
t=0;/* ʱʼ */
collect various data of each entity;/* ռÿʵй */
if( t mod T = 0 ) { /* RUCA */
for (i =1; i<=N; i++) {
calculate ; calculate;/* ʵڱе翪仯 */
calculate ;/* ʵڱеշ仯 */
calculate  /* ʵڱеĹϢ仯 */
}
for (i=1; i<=N; i++)
if ( ) {/* 翪һֵһж
 */
if ( )/* ˿ӹ죬ӱߴ */
Belti=Belti+;/* ʵ屣ߴ */
else if ( )/* Ч½죬ٱߴ */ 
Belti=Belti-;/* ʵ屣ߴ */
}
}
advance t;/* ƽʱ */
Endloop
4.4 ģ
÷泡ѡף12ݣģһս˫װ׳ʵ壩սǶ䣺ϵͳNN=10,, 100ɣÿһʵ壻ʵ·ɼͿƣλƲ򣩣ģʱΪ˫໥ӽ˫Ӵһ׶.ʵλһάĵУ޶սΧΪ5050kmʵݴ̽ʵ弯ϣʿɲöάRSʵѰַ·.ΪģǼʵ̽ⷶΧΪ55km.ʵ״̬ݸʷÿ0.215ľȷֲ͵ʵ״̬ݸʣ11ݣ.ϵͳģʵĿʾ.ģ⻷üݴѧɼУUCLAParsecģ⹤ߣ13.
4.2ģͬΪģʵĶԺͶ̬ԣڷԵصʵ˶ٶ.ζͬ򱣻ߴ£ʵٶԽԽߣӦĴ翪ҲԽ.ģĿΪ˿RBF-ARUƶԲͬӦõӦ.ͼ5Ϊϵͳģʱƽ翪λʱϢRBF-1.5RBF-2.5RBF-4.5ֱʾ򱣻̶Ϊ1.5km2.5km4.5kmʱRBFƣRBF-ARUʵ屣ʼֵΪ5.0kmߴΪ0.2km.ͼ5ʾ̶ֹߴ磬RBF-ARUµƽ翪15%35%(N=100ʱ).


ͼ5ϵͳģʱƽ翪
5ܡ
漼ŻĴģֲ淽չϵͳԴƿǷֲϵͳٵһҪ⣬鲥ͨŵĹ˻ЧϵͳԴĺķģ̬.RBF˻鲥ͨŵŵֿڲֲԣܵԴ˼ݵķͣս紦ͬʱ鲥ݵĸתӵ.RBFƵʵְŹ˿ЧԽζŸĹ˿ӶӰ˻ƵۺЧ.о򱣻ߴԹЧʡ˿Ӱ죬ָЧʲǹ˻ƵΨһб׼˹˻Ƶһۺ۱׼.ԷֲӦôڵʵԼ̬Եص㣬һӦ²RBF-ARU.RBF-ARUݷйеķݣ̬򱣻ߴ磬ʵֹЧʺ͹˿֮ƽ.ģRBF-ARUܽϺõӦʵĶԺͶ̬.
߼飺ʷУ19717,ʿоҪоΪֲ桢ֲд.裬У 197210ʿоҪоΪֲ桢ֲд.ʿҢ,У19379,ʿʦоΪܻϵṹֲ桢۵.ų,У19609,ʿʦоΪܻϵṹֲдֲ
ߵλʷ衡ʿҢųءѧѧѧԺɳ410073
ο
1Fullford D. Distributed interactive simulation: Its past, present, and future. In: Proc of Winter Simulation Conference. Coronado, CA: ACM Press, 1996. 179186
2Swaine S, Stapf M. Large DIS exercises100 entities out of 100000. In: Proc of 16th Interservice/Industry Training Systems and Education Conference. Orlando, FL: IEEE Computer Society Press, 1994. 413
3Stone S, Zyda M, Brutzman D, Falby J. Mobile agents and smart networks for distributed simulation. In: Proc of 14th DIS Workshop. Orlando, FL:IEEE Computer Society Press, 1996. 1115
4Van Hook D J, Rak S J, Calvin J O. Approach to relevance filtering. In: Proc of 11th Distributed Interactive Simulation Workshop. Orlando, FL:IEEE Computer Society Press, 1994. 367372
5Macedonia M. Exploiting reality with multicast groups: A network architecture for large scale virtual environments. IEEE Computer Graphics and Application, 1995, 15(5): 3845
6High Level Protocol used with IP Multicast, An IP Multicast Initiative White Paper, Stardust Technologies, Inc. http://www.ipmulticast.com/techcent.htm
7Cohen D, Kemkes A. Using DDMAn application perspective. In: Proc of Spring Simulation Interoperability Workshop. Orlando, FL:IEEE Computer Society Press, 1997. 107114
8Rak S J, Van Hook D J. Evaluation of grid-based relevance filtering for multicast group assignment. In: Proc of 15th Distributed Interactive Simulation Workshop. Orlando, FL:IEEE Computer Society Press, 1996. 739747
9Van Hook D J, Rak S J, Calvin J O. Approaches to RTI implementation of HLA data distribution management service. In: Proc of the 15th Distributed Interactive Simulation Workshop. Orlando, FL:IEEE Computer Society Press, 1996. 535544
10Morse K L, Steinman J S. Data distribution management in the HLA: Multidimensional regions and physically correct filtering. In: Proc of Spring Simulation Interoperability Workshop. Orlando, FL:IEEE Computer Society Press, 1997. 343352
11Cheung S E, Loper M. Traffic characterization of manned-simulators and computer generated forces in DIS exercises. In: Proc of 5th Annual Conference on AI, Simulation, and Planning in High Autonomy Systems. Gainesville, FL:IEEE Computer Society Press, 1994. 7076
12Olszewski J, Mellon L. HLA testbed data distributed management experiments. In: Proc of 15th DIS Workshop on Standards for the Interoperability. Orlando, FL: IEEE Computer Society Press, 1995. 631639
13Meyar R A. Parsec User Manual: Release 1.1. UCLA Parallel Computing Laboratory. http://pcl.cs.ucla.edu/projects/parsec
14High level architecture baseline definition, Defense Modeling & Simulation Office(DMSO), 1996, http://hla.dmso.mil/hla/tech
յڣ1998-11-02
޸ڣ1999-02-12
