ѧ
JOURNAL OF SOFTWARE 
1999 10 5 Vol.10 No.5 1999



ΪĶ̬ط㷨
¾ࡡ˼
ժҪ Ϊ빲⻷,һΪĶ̬ط㷨.㷨ۺϿ ĴͨԼΪ,Чصϵͳ,ûʵ ʱǰ,Ϊʵ.
ؼʡ⻷,û,Ϊģ,ط.
ͼšTP316
Dynamic Load Distribution Algorithm Based on Behavior
WANG Yong-junWANG Yi-jieLI Si-kunHU Shou-ren
Department of Computer ScienceChangsha Institute of Tech nologyChangsha410073
AbstractIn this paper, the complex behaviors are introduced into shared virtual environm ent and a dynamic load distribution algorithm based on behavior is proposed. Thi s algorithm can consider the processing capability of CPU, communication capabil ity of network and characteristic of behaviors, tune the system load efficiently to keep the behaviors' fidelity while promoting the real-time interactivity of users.
Key wordsShared virtual environment, multi-user, behavior modeling, load distributing.
Ŀǰ,ֲʽ⻷о༯ʵ豸ⳡͼνģʵ ʵʱܵĸơ绷жͨЭ,ֲʽ⻷ƽ̨ ṩûΪģϵͳʵֵĸַ߲֧ĹЧ.һЩϵ ͳ,AVIARY1,MR(minimal reality)2,BrickNet3ݵȻ нΪͨõĽģ,ЩģԽֽ֧Ϊ򵥵Ϊģͺ͵ͼ㸴Ӷȵ Ϊ.ҹ,Էֲʽ⻷ƽ̨оǿհ.㽭ѧȻչ˶ ֲʽ⻷ֵ֧о,Ҳڷֲʽͼδ4.
Ϊ˽ʵзḻɵʵ⻷бֳ,ڼ ˹ܵ򶼽о,һЩΪӵΪģͣ57. Ӧ,Ϊĸӳ̶Ƚϸ,ʵΪܴ,Ҫֲ ֧ʵĲԺʵڵĲ.ΪӦһ,˷ֲʽ⻷ ƽ̨YHVRP(YH virtual reality platform).ƽ̨ڵǰͨõӲƽ̨(PC ,վ)ƽ̨(NT,Unix)͸̫(100Mbps),ṩ⻷ģYHV MLиΪĽģ,ͬʱ,ԵĽֶ֧⻷״̬ʵĶ̬޸ġ ɾ.YHVRPû̬ؼ빲ͬһ⻷.
ӵиΪ⻷,㸺ش,û⻷Ķ̬޸Ҳ ˽ϴĸر仯,Ϊ˱֤ϵͳʵʱ,Լ㸺صĶ̬ԵҪ .,ڵǰֲʽ⻷ƽ̨֧ͨʵ״̬Ķ̬ı, ˼Ϊ,,ֻֻ֧򲿷ֻ֧ڿռ仮ֵʵĲ,û ʵĶ̬ط,AVIARY,DIVE(distributed interactive virtual environment )8ṩ˻ʵǨƻ,ƹӦÿ.WAVES(wate rloo virtual environment system)9ṩؾ⹦,ִԭΪ .ǴǰĹ10Ҳӿռӵı仯ǶΪϵͳĸ .
,һΪĶ̬ط㷨,ΪԷ ,ۺϿǽĴͨ,֧ӵиΪ⻷Ϊ㲢л ,ȱ֤⻷ʵʱԵǰ,֤Ϊʵ.
1Ϊ⻷
1.1 Ϊ
Ĺ۵,⻷ɹԺʵɵ.ʵ Ϊ;ֲ.νΪָ,ʵԹԡֲԻΪĲ. ھиΪ⻷,Ϊ⻷ļҪʵΪ.Ϊ ĳЩ¼ִܱ.Щ¼ʱ¼¼Ϊ¼ȵ.
1. ʵ弯.һ⻷VE,Nʵ,ʵ ϿɼΪEntity-set={Entityii=1,...,N}.
2. Ϊ.ΪbehaviorԼΪԪ飺InputAttrSet, OutputAttrSet,ProcessingProc.,ProcessingProcΪ ԼInputAttrSetΪʵԻ򹫹ԣԼInputAttrSet Ϊ޸ĵʵԻ򹫹.
ǽΪΪࣺ
(1) ΪʵԽвΪ,νָ,Ч й,άΡٶȡλõȣ
(2) ǱΪʵǱԽвΪ,,漰ԵΪ.
1.2Ϊ⻷
ǵ,⻷пԿһ沽ɵ,ÿ沽һ Կ3βɣ1,ûʵݣ2,㵱ǰڻԾ״ ̬ʵΪ,޸ӦʵԺ͹ԣ3,ָȤ(Ƶǰ ûҰڵʵ).ǵļӳʱֱInputLag,SimuLag,RenderLagʾ. ף11ݽûִһĻʾ֮ʱΪ˶ӳ(EndEndLag ),Ǹμӳʱ֮.
1.3⻷
⻷еҪʵʱԺʵ.ʵʱָ⻷Ҫ㹻 ,ʹûʵʱϷӳ,ӵı仯ĳ仯,ҪEndEn dLag,ΪضӦָʱ.Ϊ,⻷ʵָڦ,ʵ ΪΪʵ.
Ӧñͨ߼Ϊĸ沽ִ,,ÿΪһ޸ ,ν޸ʼ߼Ϊϴִеķ沽ĵ.,Ϊÿ ִ,޸Ϊ1.Ϊﵽ޸,ǾͳΪʵ.
2ΪĹ⻷̬ط
֪,ͳĸطҪĿǾĸ,ʵֲм,ԼС ƽӦʱ,Ӷʹϵͳӵ.,⻷ĸطһߵҪ ,ȱʵʱ,α֤Ϊһʵ.
2.1˼
ӵиΪ⻷,ڻԾ״̬Ϊڱؽ,ҲԱȵԶ ؽ,ǱֱΪֲΪԶΪ.ֲΪȷ޸,ܿ ʱ,ƻʵʱ.ԶΪĿͨеķͼʱ.Ϊ˱֤ ޸,ԶΪϢҪͬ,ǳƸԶΪΪͬΪ., ӵԭ,ͬΪĵȴʱܳ,ͬƻʵʱ., ,ԽӦԶΪ,ΪֲΪ.,ǾҪʵʱԺʵ֮ ѡ.
ʵʱԺʵͻʱ,ʵȡҪʵʱ,ĳЩԶ ΪϢԲͬȴ,ΪΪ첽Ϊ.ͨΪΪʱ г̶ȸ,ǱΪг̶ȵ,,ѭһԭǣ Ϊͬ,ǱΪ첽ȼ.
2.2ûһ
ûһ⻷ʱ,ÿû֪ĳͬ.,ͨͬ ĻԾʵΪҪ.ԶΪȡ⻷Ϣ,ͻ ֲΪ.⻷״̬һ.
Ȼ,ͬΪԱ֤ûڽÿһ沽״̬һ,Ǻܿƻʵ ʱԣ첽Ϊ״̬һ.ѭһԭǣΪȷǱ ΪҪһԳ̶ȸߣڷǱΪһͨΪû,, Ϊั.,ڸӲܵĲ,ƽٶȲͬ, ΪһҪĽͬķ,,ÿû EndEndLagĺ㶨.
2.3ظ
ÿʵΪΪࣺΪϺͷǱԼ.ʵEntityiΪ ֱΪPresentationBehSetEntityiNonPresentationBehSetEntityi.
һϹ⻷,ǽеĴͳһΪ.㼯Ͽɻ Ϊࣺû㼯UserNodeSetͷû㼯NonUserNodeSet.ûû ⻷Ĵ,ͨ,ûʵʱ⻷,ҿɶ⻷ж̬ .ͨû豸άꡢ̵ȣ豸߼ͼμٿ ʾȣ,⻷μûֵΪ.ûֶ֧ ⻷ķֲд,û޷ΪǨƵû .û㼯ϰ䵽ϵΪҲΪࣺǱΪ㼯NonPres entationBehNodeSetͱΪ㼯PresentationBehNodeSet.
⻷й,PϵʵEntityiڷ沽stһԾΪActiveB ehaviorTable(P,Entityi,st),ûϵĻԾΪִмڵĵص,ɷΪֲ ΪLocalBehSet(P,Entityi,st)ԶΪRemoteBehSet(P,Entityi,st). ûֻоֲΪ.ûϵԶΪϰȴֵķʽ, ΪͬΪSyncBehSet(P,Entityi,st)첽ΪAsyncBehSet(P,Entityi,st ).Ƶ,ûϵľֲΪϰȴֵķʽ,ΪͬΪSy ncBehSet(P,Entityi,st)첽ΪAsyncBehSet(P,Entityi,st).
3. Ϊ.ΪԼΪԪ飺CompCost(behavior ),CommCost(behavior).,ΪCompCostΪеָ㣻ΪͨCommCost Ϊ롢ֵ͵ĴС.
4. Ϊ.Ϊָ,ΪΪû ԶΪʱ,ÿһ沽Ҫûͨ,ɼΪ
OutputCost(behaviorij)=UserNumber(behaviorij,st)OutputAttrib uteCost(behaviori).
behaviorijʾEntityiĵjΪ,behaviorijLocBehSet(P,Entit yi,st)UserNumber(behaviorij,st)ʾΪbehaviorijڷ沽stʱ ΪԶΪûΪOutputAttributeCostΪ ֵ͵ĴС.
5. ͨ.ûPڷ沽stͨɼΪ

behaviorijRemoteBehSet(P,Entityi,st)behaviormnLocBehSet (P,Entitym,st);û״̬ͨUserStateCost(P,st)ʾPڷ沽stյĸ Ȥû״̬Ϣ.
ûPڷ沽stͨɼΪ
CommCost(P,st)=(CommCost(behaviorij)+OutputC ost(behaviorij)),
behaviorijLocBehSet(P,Entityi,st).
,ӳSimuLag.
6. ֲΪʱ.Pڷ沽stľֲΪʱLo cBehCompTimeɼΪ
LocBehCompTime(P,st)=iCompCost(behaviorij )/s(p),
behaviorijLocBehSet(Entityi,st);PָƽٶΪs(p)ָ /s.
7. Ϊȴʱ.ûP,Ϊbehaviorij ȴʱָ,Ӹ÷沽ʼϵõӦΪֵʱ.Էû P,Ϊbehaviorijĵȴʱָ,Ӹ÷沽ʼϵõһ ӦΪֵʱ.߶ɼΪWaitTime(behaviorij),behavi orijSyncBehSet(P,Entityi,st).
8. ͬΪȴʱ.Pڷ沽stͬΪȴʱ Ϊ
SynBehWaitTime(P,st)=Max(WaitTime(behaviorij)),
behaviorijSyncBehSet(P,Entityi,st).
9. ӳ.Pڷ沽stķӳSimuLagΪ 
SimuLag(P,st)Max(LocBehCompTime(P,st),SynBehWaitTime(P,st)).
10. 㿪.Pڷ沽stĿΪSimuLag(P,st),C ommCost(P,st).
Ϊʵе,ÿ㶼һӳʱMaxSimuLag, ʱ,ͻʵʱܵ½,ϵͨŸع,Ȼ ӳٺ̫£,,Ǹÿ綨һͨ MaxCommCost,߹ɽָ.
11. ָ.PָʽΪMaxSimuLag( P),MaxCommCost(P).
ûͷûеıΪķӳٵʱΪST, ûеķǱΪķӳٵʱΪST,ST>ST. 
12. Ǳ.Pڷ沽stǱǱ ͨǱ,ǱָӳʱֲΪʱĲMax SimuLag(P)LocBehCompTime(P,st);ͨǱָͨͨĲ MaxCommCost(P)CommCost(P,st).
2.4ΪĶ̬ط㷨
ڶû⻷,ΪĶ̬ط㷨һ㷨,ʱУû 롢˳⻷Լû⻷޸ĸر仯.ƪ,,ǽ ⻷йеĶ̬ط㷨.
⻷й,û⻷µʵıʵΪ,⻷ ʵĽµΪֹ˾ɵΪʱ,ûϵĸؽ仯. ķӳٳʱMaxSimuLag,ҪΪĶ̬ط㷨, ԭӦΪ.ǵȵΪΪʱΪ,Ϊ ΪĲԤ,еȽʹϵͳȶ.ϵͳʱжΪ ʱΪ.Ϊ˷ֹΪȵĶ,һʱֵ,ֻеķ SimuLagʱMaxSimuLag,ʱ䳬ֵ,ΪĶ̬ ط㷨.
ûPڷ沽st˻ΪĶ̬ط㷨.㷨£
(1) ȷʵڷ沽stĻԾΪActiveBehaviorTable(P,Entityi,st),i=1,..., N.
(2) IF LocBehCompTime(P,st)<ST/* ҪԭͬԶ Ϊĵȴʱ̫ */
THEN behavior,behaviorSyncBehSet(P,Entityi,st),WaitTime(behavior)> ST,DO
IF behaviorP,SimuLag(P,st+1)<ST
THEN ڱΪ,behaviorľֲڷǱ Ϊ,ԶΪΪ첽Ϊ
END DO
ELSE/* ҪԭǾֲΪļʱ.ƪ, ͬʱͬԶΪȴʱ̫.ѡΪʱ,ǱΪȱ Ϊȼ*/
1۷ǱΪĵݡ/* ǱΪ */
ʵоֲǱΪbehavior,CompCost(behavior)/CommCost(behavio r)ֵдӴС,DO
NonUserNodeSetѡµķǱԽQ,NonPresentationBehNodeSetеĽ 㰴ǱӴС˳ѡQ,behavior䵽Q,SimuLag(Q,st+1 )<STCommCost(Q,st+1)<MaxCommCost(Q)(ststӦQķ沽), behavior䵽Qϣ
IF SimuLag(P,st+1)<ST THEN 㷨 ELSE ѭ
END DO
2۱Ϊĵݡ/* Ϊܴ */
ʵоֲΪbehavior,CompCost(behavior)/CommCost(behavior) ֵдӴС,DO
IF behavior
THEN ѡͨǱĽQΪԶΪڽ㣻
IF CommCost(Q,st+1)<MaxCommCost(Q)(ststӦQ 沽)
THEN QϵԶbehavior㣻
IF SimuLag(p,st+1)<ST THEN 㷨 ELSE ѭ;
NonUserNodeSetѡµıԽQ,PresentationBehNodeSetеĽ㰴 ǱӴС˳ѡQ,behavior䵽Q,SimuLag(Q,st+1)<ST CommCost(Q,st+1)<MaxCommCost(Q)(ststӦQķ沽),behav ior䵽Qϣ
IF SimuLag(P,st+1)<ST THEN 㷨 ELSE ѭ;
END DO
(3) 㷨
3 
YHVMLдһ.һģͽΪ򵥵3Ϊ:һ ǱΪMOVETURN,һΪTHINK.MOVEһάռƶ,THINKǽ һݼϵ,ÿɹ,TURNıƶ.MOVEִʱ5ms ,TURNʱΪ1ms,THINKʱԼ30ms.ȡûSTΪ30ms,û STΪ50ms,⻷100Mbps̨̫PC586,120M hzƵ,32MBڴ,S3 64V+ͼμٿ.ڸԤʱ,THINK䵽û ,ȴʽΪ첽.MOVEʵʱԼΪ8ms,THINKʱΪ50ms,ʱ ԼΪ30ms40ms,˶ӳΪ45ms.ͨһ̨ͬõPCΪµû ,ͨط,µûϲMOVETURNΪ,ûʵ Ķͬ.µû,ֶ̬زһͬʵ, .,ʵTHINKΪҲ䵽û,MOVETURN û϶и,ûĶ˶ӳٶԼΪ70ms,ӾЧ.
Խ֤˻ΪĶ̬طۺϿǽĴͨԼ Ϊ,Чصϵͳ,ȱ֤⻷ʵʱԵĻ,ά Ϊʵ.Ҳ˵YHVRPֲַ֧ʽ⻷Ӧÿнϸߵ .

¾,1971,ʿ,оԱ,ҪоΪʵ Ͳзֲ.
,Ů,1971,ʿ,оԱ,Ҫо Ϊݿ,зֲ.
˼,1941,,ʿʦ, ҪоΪCAD,ʵ.
,1926,,ʿ ʦ,ҪоΪܻϵṹ,зֲ.
ͨѶϵˣ¾,ɳ 410073,ɳѧԺϵ606
ߵλɳѧԺϵɳ410073
ο
[1]Snowdon D N. AVIARY: design issues for future large-scale virtual environments. Presence: Teleoperators and Virtual Environments, 1994,3(4 ):220241
[2]Chris S, Mark G et al. Decoupled simulation in virtua l reality with the MR toolkit. ACM Transactions on Information systems, 1993,11( 3):287317
[3]Singh G, Serra l, Pug W et al. BrickNet: a software t oolkit for network-based virtual worlds. Presence: Teleoperators and Virtual En vironments, 1994,3(1):1934
[4]Pan Zhi-geng, Shi Jiao-ying, Zhang Ming-min. Distributed graphic s support for virtual environments. Computers and Graphics, 1996,20(2):191197
[5]Bruce M B, Tinsley A G. Multi-level direction of autonomous creatu res for real-time virtual environments. In: Robert Cook ed. Computer Graphics P roceedings, Annual Conference Series. New York: ACM SIGGRAPH, 1995. 4754
[6]Tu X Y, Demetri T. Artificial fishes: physics, locomotions, percept ion, behavior. In: Andrew S G, Mike K eds. Computer Graphics Proceedings, Annual Conference Series. New York: ACM SIGGRAPH, 1994. 4350
[7]Johnson M B. WAVESworld Ph.D. Thesis. Massachusetts Institute o f Technology, 1995
[8]Carlsson C, Hagsand O. DIVE--a platform for multi-user virtual e nvironments. Computers and Graphics, 1993,17(6):663669
[9]Kazman R. Load balancing, latency management and separation of conc erns in a distributed virtual world. In: Zomaya A ed. Parallel Computer-Pardigm s and Applications. Van Nostrand, 1996. 443454
[10]¾,.⻷ļֲ.ѧ,1997,20() :2833
(Wang Yong-jun, Hu Shou-ren. Computation distribution and scheduling of networ ked virtual envrionment. Chinese Journal of Computers, 1997,20(supplement):2833 )
[11]Wloka M M. Lag in multiprocessor virtual reality. Presence: Teleope rators and Virtual Environments, 1995,4(1):5063

1998-03-16յԭ,1998-05-28յ޸ĸ
