ѧ
JOURN AL OF SOFTWARE
1999ꡡ1010ڡVol.10No.101999



ֲлServerĲι˻ 
ʷ  ʿҢ ų
ժҪģֲԴ˺ܸߵҪ,ݹ˻ƿɴ󽵵ͶͼԴѹ,ϵͳ.ȻڸЧ˻,Ҫպʹ㹻ĹϢ.ϵͳģʱ,Ϣʹռ˹ļԴ,Ӱķ.һֻServerĲλ˻,˷ڵ޵.ͬʱ,µĻ÷ھֲ,Ϣ,ӶServerڲϢ.
ؼʡֲ,ݹ,·ռ,չ,HLA,鲥ͨ.
ͼšTP391

Server-based Hierarchical Filtering Scheme in Distributed Interactive Simulation
SHI Yang JIN Shi-yao ZHANG Chen-xi
(School of Computer Science National University of Defense Technology Changsha 410073)
Abstract Distributed interactive simulation requires high network bandwidth and computation capacity which caused by redundant data when the systems scale increases. This situation can be alleviated by data filtering to great extent. But the effective filtering scheme requires simulation hosts receiving accurate filtering information and high processing capability, this consumes too much computation resources when systems grow. In this paper, the authors propose a server-based hierarchical filtering scheme. New scheme frees the simulation hosts from the filtering processing and avails systems scalability. New scheme also exploits the potential locality of distributed interactive simulation, which reduces the amounts of filtering messages exchanged and filtering computation.
Key words Distributed interactive simulation, data filtering, routing space, scalability, HLA (high level architecture), multicast.
漼ԭϵͳϢӦרҵΪ,Լ͸ЧӦ豸Ϊ,ϵͳģͶʵʵĻеϵͳж̬ʵоһŶѧƵۺϼ.Լؼķչ,ɼʽչ˷ֲ[1],Чáȫŵܵиҵ,Ŀǰ㷺ӦھԼ񾭼õĸ.
ֲϵͳģ,ͽ˸ߵҪ.˻һЧĽ;,ЧĹ˻ռùķ㴦Դ,˹˴ĺô.һֻServerĲι˻.µĹ˻ƽĹתƵ˷,ʹϵͳģʱ,ִй˲Ӱ.ͬʱ,µĻƿ˷ľֲ,ĹϢServerڲ.µ1ڽһ漼HLA/RTI¹ԭԼֹ˻Ƶȱ,ЧʺͿԷй˻ƴڵ.2ڴ˻˻ServerĲλ˻Ƶģͺ㷨,˷ͱȽ.3ܽȫ.
1ֲݹԭ˻ƿ
1.1 ֲ滷¹˵ݼҪ
δķֲڹģӦǿ,ֳ֧ǧʵ[2].ŷֲģ,ȻӴ˷(ʵ)֮ݵ,Լ㴦ⲿϢƵ.ʹ˺ܸߵҪ,ӰϵͳĿ.ݷֲص,ʹݹ˻[3,4]Դ󻺽ԼԴ,ΪϵͳĿṩ˿.֧ݹ˵Ƿľֲ,κʱĳһʵֻϵͳʵӼ,ǳƴӼΪʵġȤ,Ȥڲʵ֮Ҫ״̬ͽϢ.ʵ,Ǻܳ,ģսеĽս̽ԼЭеĹ,ԹɸȤ.ڴģֲ,һʵĸȤһֻռʵ弯һС,Źģ,ȤĴСȶ[2].սװ׳ĶԿϰ,սζʵģ,ģ͵(Ұ̼ռ),ʵŹģӶȶ,ģ.ֲҪʹòݹ˻ƳΪ.˵ĿҪ:һǾܼٲݵĲ,Լռ;һǽͷʱĴ.ĿĶϵͳĿ.ͼ1ͼ2Ƚ˹˺ͷǹ,ͽƽϵͳģı仯.ϵͳn̨ڵ,ÿƽ10ʵģ,ʵ״̬ݰƽΪ1KByte,״̬Ϊ10pkt/s.1ΪͼʹõϵͳģʱȤģ.

ͼ1˺ͷǹ˻ͼ2˺ͷǹ˻ƽݴﵽ
1 ʵȤģ仯

ϵͳģĿ1002003004005006007008009001000
ʵĿ1 0002 0003 0004 0005 0006 0007 0008 0009 00010 000
ȤģȤ(%)15108765.554.54.13.8
ȤС150200240280300330350360369380

 
ͼ1ͼ2֪,ù˻ƵݰʵҪԶСڷǹ˻.ǹ˻(,ͳDISЭù㲥ʽͨ)˷ʹԴ,ϵͳĿԺܲ,ù˻Լù˼鲥ͨ(multicast)[5]ݰ.ɴ˿ɼ,˻ƶϵͳĿܴ.
1.2 HLA¹ԭ
߼ϵṹHLA(high level architecture)[6](DoD)1995µķ漼,з漼(DISЭALSPЭ)Ĳ,ֲĻ(ͬͷӦ֮ļ)Ϳ(߷濪Ч).HLAȡDISЭΪһֲı׼[7].ֻ֧Ϳ,HLAҲΪݹ˵ĸЧʵṩ֧:DISԱ׼ʵ״̬ݰΪԪ,HLAֻ֧ʵ״̬ӼݵԪ.
HLA,֧ݹ˵Ļ·ռRS(routing space)[8],RSһĶάϵͳ,RSҪ:(1) ϵͳά;(2) ·,Ӧϵͳÿһά,ڱȤ(ꡢ˶ٶȵ);(3) ·ÿάϵĶ(絥λ̶ȡΧ).
ʵͨRSⲿ͵ĺʹⲿյݵ.ͨRSеӼռ(region)ʵ:ʵͨ(publish region)Ͷ(subscribe region)ⷢݺͽⲿݵԼ,ͻӳϵ.ͼ3ΪάRSռݹ붨ʾͼ.ÿʵķͺͽݶӳϵ,Ԫʽʾʵ塢ݼĹϵ:
Region, Entity, Attributes .

ͼ3·ݹ붨
һʵڶͬRSϲ,ÿRSһΨһıʶ,ͬһRSйͶķʵڴRSҪϴһ,Ա֤Ϣ໥(ͨһɷʵķʼļʵ).ͼ3й㷨ִн:ʵbĹκζཻ,˽ֹbݷ;ʵaĹʵcdĶཻ,Ϊʵaһ鲥ַa,ָʵcdӦ鲥ַ.
ͨԹͶƥ,ȷǷԷ,ԼշǷӦý.ǳƶ͹ϢΪϢ,ƥΪ˼.ڹϢĴԴһĿĵصĶӦϵ,ڴ˻õײ鲥(multicast)[5,9],ֻһζಥͼ,ͨ·Զƺ·,˷ͷͨſ,ͬʱҲ.
1.3 ˻ƵĿ
˻ʵ;,[3]˻(grid-based)Ĺ㷨.˼:·ռ仮ֳȵ,ΪÿԪһ鲥ַ,乫ཻӦ鲥ַ,߼䶨ཻӦ鲥ַ.㷨ʵּ,շ轻Ϣƥ,ȱ:(1) ȱٹϢ,ͷäĿйݶǷ붨ཻ;(2) 鲥ַĿ,˷;(3) ȵ¹˾ȷ̶.㷨˴ĺôۿ,Чʺ鲥ַʹϵͳģϴʱ.[4]˼ֻ񷨵ı,һ̶ϻ񾫶,ԹЧʵĸȴ.[10]˻ڽշ(receiver-based)Ĺ˻RBF,˼:ͷݵķָݵ·.ֹ˻̶ȵݷԴݵĲ,һָЧĹ˻.[8]о,ڽշ˻Ҫڻ˻,ƽµĹЧ.ڽշ˻ƵҪȱǷҪ㹻ĹϢ,ζŷⲿÿһ仯ƥ,Ҹݽָϵϱ仯ʵݷͺͽ.
øЧ˻ϵͳ,ǰҪ㹻ĹϢʹ.RBFûпϵͳģ仯Թ˿Ӱ.ֲص,ÿĴΪ1,ÿļԴҪ3:ʵģ͵ļ㿪CPUsimⲿݽմCPUcomm˻ƿCPUfilter,CPUsimCPUcommCPUfilter1.CPUsimģ͵ĸӶй,һһ̶Ͻ;CPUcommʵⲿĽ̶й,ͨЧĹ˻ƽݵĽս͵ͳ̶;CPUsim,CPUcommӦñزٵ,ռþ󲿷ִԴ.CPUfilterϢմ͹˼㿪,еҵƽ̨,ܲϵͳص,Ϣڼһƿ,һֱԼϵͳܷӵҪ.2г˼ֵǰͼƽ̨ݰ(OSЧʵй).漰OSں˵Ĳ,һΰռõCPUʱ൱ڼִָʱ.RBF,Ϣϵͳģ,CPUfilterҲϵͳģ.˵RBFƶĸų̶Ƚϴ,ϵͳģϴʱӰķִ.ɴ˿ɼ,Ӧù˻Ƽͽݰʵͬʱ,뿼ǹ˻ƿϵͳģĸӰ.
2 ֵҵԼƽ̨Ϣ

ϵͳCPUʱ(MHz)ϵͳϢƽ(m s)
Pentium II200Linux 2.0.1641
SUN SU2/2170167Solaris 2.5.166
SGI Indigo2250IRIX 5.3106
DEC Alpha266OFS 3.2C113

 
2ServerĲʽ˻
2.1 ṹģ
ֲַ֧ģĹ˻ӦǸЧ,Чӻͷʵļ,ͬʱ,Ч˻ƶԷĸų̶ȲӦϵͳģ.ĿǰڵҪìǹЧʵִ֮ì,һìҪɷִй˻ɵ.Ϊ˽Чϵͳģ֮ì,˻ڷֲʽServerĲλ˻SBHF(server-based hierarchical filtering),ͼ4ʾ.ֲһ㽨绷Ļ,Ϊʧһ,Ǽֲ滷ɸվ(),ÿվɷ(host)һ(server).

ͼ4ڷֲʽServerĹ˽ṹģ

2.2 ServerڲλϢ
ServerڽLANڲڵĹϢִй㷨(ƥ).,Server֮佻ϢԱ֤ÿȫֹϢ.Ϊ˿ʱֲԵؼServerϢͼ,ǽϢ֯ɾ.ϢδԭʼϢ,ϢھϢϺϲĹϢ.ÿServerάϢ,оϢԱڲĹ붨Ϣ,ϢⲿϺϲĹϢ.Ϣ.
ϢϢ<RSk,Hi,Ei,j,Sk>͹Ϣ< RSk,Hi,Ei,j<Pk> .RSkʾk·ռ,Hiʾi,Ei,jʾiϵkʵ,Sk릲PkֱʾʵRSkϵĶ򼯺Ϻ͹򼯺.
ֹϢϢ<RSk,SVRm,Sk>͹Ϣ< RSk,SVRm,Pk>.SVRmʾվmServer,SkʾվmڲRSk϶ϲļ,PkʾϲĹ.ϲĿǼٹϢ,Լٹƥ.ϲж;,ļϲСǼ.Ϣ֯Ժܺõhashķʽʵ.
2.3 ˻
ͼ5ΪServerĲλ˻ʾͼ.

ͼ5Serverڲλ˻ʾͼ
ServerڲhostĹϢ(빫Ϣ),γɴ֡Ϣ,Server֮佻Ϣ.ĳһʵĶs仯ʱ,µĶϢ͵Server,ºϲϢ,ͬʱϲϢ͵Server.ServerִвιϢƥ.,s뱣ⲿServerĺϲϢƥ(ƥ),ֻƥɹ,ŽsཻServerһⲿServerڵľȷϢһƥ,ƥָӦ㿪ʼֹͣ(˳Ӧ鲥ַ).RBF,SBHF˲ƥ.p仯ʱ,㷨ϸ(㷨еķźͬǰ):
㷨. Server-based Hierarchical Filtering Algorithm
/* 㷨SVRi,±iʾվڲ, jʾⲿ,ij */
/* s(p)ʾ仯Ķ(򹫲)Ϣ */
Loop
t=0/* ʼʱ */
wait to receive msg/* SVRiϢ */
If msg=si (pi )/* si(pi )ΪڲµĹϢ */
Si=si{ SiCsi}( Pi=pi { PiCpi});/* ±ؾϢ */
Si={ Si} (Pi={Pi});/* ϢϲɴϢ */
send Pi(Si) to other Server;/* ʹϢվ */
For all Pj(Sj) of SVRj stored in SVRi
If si {Pj}٦ /* ƥɹ,ϢӦServerһƥ */
send si (pi ) to SVRj;
endfor
If msg=Sj (Pj) /* Sj (Pj )ΪⲿSVRjĴֹϢ */
update Sj (Pj );  /* SVRiϵĴֹϢ */
If msg=sj (pj ) /* sj (pj )ΪⲿSVRjƥɹĹϢ */
For all pi(si) in  Si( Pi)
If sj (pj )pi(si)٦ա /* 뱾ؾϢƥ,ָӦ㷢() */
direct hosts (internal hosts of SVRi ) start to send(receive) data;
send sj (pj ) match success report to SVRj;
endfor
If msg=match success report/* ⲿƥɹ */
direct hosts which generate si (pi ) start to receive(send) data;
For all pi(si) in  Si( Pi) /* ڲ֮ƥ */
If si (pi )pi(si)٦ա/* ƥɹ,ָӦڲ㷢 */
direct hosts (internal hosts of SVRj) start to send(receive) data;
request t advance; /* ʱƽ */
Endloop
Ҫָ,ʵһҪСʵ״̬,ʵ֮Ľһһʱ,仯ĳһֵʱ,ʵ巢,[8]ϸ.SBHF㷨ɼɵHLAݷֲ(DDM)[10],ʱͬRTIṩʱʵ[11].ƪ,Ĳ.
2.4 Է
ǷֻƶϵͳԵӰ.ĿǰĴ֮ž޴Ĳ,Ϊϵͳƿ,΢ķٷչ,ֲ໹ڼӴ,,ǱȽֻµĹϢʶϵͳӰ.Ϊ˷,ǿǶԳ͵ϵͳ,ϵͳmվ,ÿվn,ÿsʵ,ʵϢ仯Ϊr.
RBF˻,ÿmnC1ⲿ,,ĹϢΪr(mnC1)s.SBHF,㲻ԭʼϢĽպʹ,ֻServerָϢ,ֻ˽صı仯ű֪ͨ,,ϢΪr(mnC1)sph, phǹģΪmnʱĸȤ.ͼ6Ϊֻ·ĹϢ,m=100,200,,1000;n=10;s=1;r=0.2/s.
ͼ6ɼ,SBHF½ϢԶСRBF,ϵͳģӰС,˵SBHF˻ƶԷ㴦ԴռúС,ϵͳģ仯,˾кܺõĿ.Ҫָ,SBHFƲÿվֻһServer,֧վжServerĴ:ڷ߼,ÿServerһ,ƽ⸺,ӶӦģϴվ.վڲServerʹ÷Լڷִ,ӦִԽԽڸӻ(Ӿȷķģ͡ĸͼʾ)Ҫʵ.

ڵĿ
ͼ6ֻĹϢ

3
Ŵģֲչ,ӦҪ:ϽϷѵҵѵЭԼӹģ͵ķֲ.δķһǷֲͽ,ڹģǿ.˻ƿľֲԴ󻺽˹ģʱʹݰԴĸ.ЧĹ˻ҪϸߵϢʹԴ,ڹģϴʱӰִ,Υ˹˵ĳ.ĻServerĲλ˻ڲ͹ϢȷȵĻ,˸Ч˻ܷƵ,ͬʱ÷ֲڵľֲ,֡ϢԼϵĹϢ͹˼,һֿԺõĹ˻.һоServer㷨ʵŻ,ServerڲϢϲԵоߴƥľ,Լ㷨ĲԳüƽ̨Ĳд.
עͣоõȻѧ
߼飺ʷ 1971,ʿ,ҪоΪֲ/д
ʿҢ1937,,ʿʦ,ҪоΪϵͳṹ,,

ųأ1960,,ʿʦ,ҪоΪֲ/д
ߵλѧѧѧԺ ɳ 410073
ο
Fullford D. Distributed interactive simulation: its past, present and future. In: Brunner D ed. Proceedings of the Winter Simulation Conference. San Diego, CA: ACM SIGSIM, 1996. 179186 
Swaine S, Stapf M. Large DIS exercises-100 entities out of 100000. In: Medin L ed. Proceedings of the 16th Interservice/Industry Training Systems and Education Conference. Orlando, FL: IEEE Computer Society, 1994. 413 
Van Hook D J, Rak S J, Calvin J O. Approach to relevance filtering. In: Miller D C ed. Proceedings of the 11th Distributed Interactive Simulation Workshop. Orlando, FL: IEEE Computer Society Press, 1994. 367372 
Macedonia M. Exploiting reality with multicast groups: a network architecture for large scale virtual environments. IEEE Computer Graphics and Application, 1995,15(5):385 
Pullen J M. The IETF, reliable multicast, and distributed simulation. No. 98S-SIW-208. http://siso.sc.ist.ucf.edu/siw/98spring/ docs/papers 
Defense Modeling & Simulation Office (DMSO). High level architecture baseline definition. 1996. http://www.dmso.mil 
Miller D. The DoD HLA and the Next Generation of DIS. In: Miller D ed. Proceedings of the 14th Distributed Interactive Simulation Workshop. Orlando, FL: IEEE Computer Society Press, 1996. 799806 
Morse K L, Steinman J S. Data distribution management in the HLA: multidimensional regions and physically correct filtering. In: Miller D C ed. Proceedings of the Spring Simulation Interoperability Workshop. Orlando, FL: IEEE Computer Society Press, 1997. 343352 
Powell E T. The use of multicast and interest management in DIS and HLA application. In: Miller D C ed. Proceedings of the 15th Distributed Interactive Simulation Workshop. Orlando, FL: IEEE Computer Society Press, 1996. 251260 
Van Hook D J, Rak S J, Calvin J O. Approaches to RTI implementation of HLA data distribution management service. In: Miller D C ed. Proceedings of the 15th Distributed Interactive Simulation Workshop. Orlando, FL: IEEE Computer Society Press, 1996. 535544 
Fujimoto R M, Weatherly R M. Time management in the DoD high level architecture. In: Wayne L, Bruno P eds. Proceedings of the 10th Workshop on Parallel and Distributed Simulation. Philadelphia, PA: ACM Press, 1996. 6066 
ո:1998-06-29޸:1998-10-16
