A Novel Convergence Algorithm for the Hybrid Strategy Model Packet Reduction Technique

ISSC 2005, Dublin, Sep embe 1- 2 A No el Con e gence Algo i hm o he Hyb id S a egy Model Packe Reduc ion Technique Declan Delaney° °° °, Seamus McLoone*, Tomas Wa d* *Dep . o Elec onic Enginee ing, NUI Maynoo h, Maynoo h, Co. Kilda e, I eland E-mail: [email protected] ° Dep . o Compu e Science, NUI Maynoo h, Maynoo h, Co. Kilda e, I eland E-mail: decla[email p o ec ed] __________________________________________________________________________________________ Abs ac – Se e al app oaches exis o main aining consis ency in Dis ibu ed In e ac i e Applica ions. Among hese a e echniques such as dead eckoning which use p edic ion algo i hms o app oxima e ac ual use beha iou and hus educe he numbe o upda e packe s equi ed o main ain spa ial consis ency. The Hyb id S a egy Model ope a es in a simila way, exploi ing long- e m pa e ns in use beha iou whene e possible. O he wise i simply adop s a sho - e m model. A majo p oblem wi h hese echniques is he econs uc ion o he local beha iou a a emo e node. Using he modelled dynamics di ec ly can esul in unna u al and sudden jumps in posi ion whe e upda es occu . Con e gence algo i hms a e hus equi ed o smoo hly econs uc emo e beha iou om discon inuous samples o he ac ual local beha iou . This pape makes wo impo an con ibu ions. P ima ily, i p oposes a no el con e gence app oach o he Hyb id S a egy Model. Secondly, and mo e undamen ally, i exposes a lack o sui able and quan i iable measu es o di e en con e gence echniques. In his pape he s anda d smoo hing algo i hm employed by DIS is used as a benchma k o compa ison pu poses. Keywo ds – Hyb id S a egy Model, Con e gence, Dis ibu ed In e ac i e Applica ions __________________________________________________________________________________________ I INTRODUCTION Techniques ha gene a e and ansmi app oxima e models o local use beha iou ha e been de eloped o educe he numbe o upda e packe s ha mus be ansmi ed be ween pa icipan s o Dis ibu ed In e ac i e Applica ions (DIAs). One such echnique is dead eckoning, which educes ne wo k a ic by p e en ing upda e packe s om being sen i he local pa icipan ’s posi ion has no a ied om a model o ha posi ion by a p e-es ablished h eshold (IEEE 1993; IEEE 1995). Howe e , dead eckoning igno es in o ma ion pe aining o he s uc u e o he en i onmen , he his o ical beha iou o use s wi hin he en i onmen and he objec i es o he use s wi hin he en i onmen . Consequen ly a echnique known as he Hyb id S a egy Model o HSM has ecen ly been de eloped which exploi s his in o ma ion by iden i ying long- e m pa e ns in use beha iou . By combining hese longe - e m models o s a egies wi h a sho e m model, such as dead eckoning, a educ ion in ne wo k a ic has been shown (Delaney e al. 2003b; Delaney e al. 2003a; Ma shall e al. 2004a; McCoy e al. 2005). An impo an issue a ising om his app oxima ion o local use beha iou is he econs uc ion o a ai h ul eplica ion a a emo e loca ion gi en his o en di e gen model o he local beha iou . I he ecei ed upda es a e ende ed di ec ly, he esul ing beha iou can be disjoin and unna u al. To o e come his p oblem, echniques a e employed o smoo hen he beha iou . These a e known as con e gence echniques. In he case o dead eckoning i s o de and cubic spline algo i hms a e used (IEEE 1993; Lin and Schab 1994). This pape add esses he issue o a sui able con e gence algo i hm o he HSM app oach. I p oposes a con e gence echnique based on he weigh ing o use beha iou al models using a sui able blending unc ion. This echnique is isually compa ed wi h he s anda d DIS smoo hing algo i hm (IEEE 1993). In ca ying ou his wo k, i was disco e ed ha he e is a dea h o objec i e measu es in e ec i ely e alua ing con e gence algo i hms (o a leas he au ho s a e unawa e o any exis ing objec i e c i e ia o e alua ing such algo i hms). The pape will ocus h oughou on use en i y mo ion dynamics, as such mo emen is esponsible o he ISSC 2005, Dublin, Sep embe 1- 2 majo i y o upda e packe s gene a ed in Dis ibu ed In e ac i e Applica ions. The s uc u e o he pape is as ollows. Sec ion II summa izes he Hyb id S a egy Model. Sec ion III desc ibes he no el con e gence algo i hm, based on he blending o use beha iou al models. The s anda d con e gence algo i hm used in DIS is also in oduced he e. Sec ion IV p esen s a se ies o g aphical simula ion esul s, compa ing ou pu s om he HSM algo i hm using (i) no con e gence, (ii) he s anda d DIS con e gnce and (iii) he p oposed con e gence echnique. Some concluding ema ks in addi ion o u u e wo k a e p esen ed in sec ion V. II THE HYBRID STRATEGY MODEL Dis ibu ed In e ac i e Applica ions in ol e po en ially housands o simul aneous pa icipan s. In an e o o educe he numbe o upda e packe s ansmi ed be ween use s, models o use dynamics a e employed so ha only samples o he dynamics need o be communica ed. Use dynamics can hen be econs uc ed emo ely using he samples as inpu o he model. The mos commonly used model is dead eckoning. This ope a es by main aining a sho - e m model o he beha iou o each en i y a each node. When he modelled and he ac ual beha iou o an en i y di e by a h eshold alue, an upda e packe indica ing i s cu en s a e is sen o all o he nodes. Be ween upda es he emo e nodes employ he same sho - e m dead eckoning model. Ou wo k o da e has shown ha long- e m beha iou may also be modelled o a g ea e o lesse ex en and ha he use o such a model would complemen he sho - e m model (Delaney 2005). This mo i a ed he de elopmen o he Hyb id S a egy Model (HSM) o u he educe he numbe o upda e packe s ha need o be ansmi ed. The hyb id model, M, o en i y dynamics is o he ollowing o m: Γ − + = )1( ppM χ (1) whe e χ is any con en ional dead eckoning model, Γ is one o se e al long- e m en i y s a egy models and p is a bina y weigh ing ac o go e ned by: p = 1 o θ ≥Γ−M = 0 o he wise (2) whe e θ ep esen s a dis ance measu e h eshold be ween he modeled beha io and he long e m model Γ. In his way a long- e m model, Γ, based on a p io i da a can be employed when he en i y mo emen is ‘close’ o such ajec o ies. The pa icula model used is dynamically chosen so ha imp o ed i s can be ob ained o e single model app oaches. A any ins an in ime he nea es model om he se a ailable is used in equa ion (1). Long- e m models can be gene a ed om his o ical da a and knowledge o he en i onmen . He e, long- e m models we e cons uc ed by eco ding ac ual use dynamics in wo sepa a e en i onmen s. To do so, use s na iga ed be ween a s a posi ion and a a ge posi ion wi h he objec i e o doing so in he sho es ime possible; each pa h aced ou by he use en i y is e e ed o as a ajec o y. The op imum beha iou o ealise an objec i e is e e ed o as a s a egy. A ajec o y ha a emp s o mi o he s a egy is called a s eady-s a e ajec o y. The sho - e m model employed in he HSM is dead eckoning. In his pape he models all ela e o use spa ial dynamics. III THE NOVEL CONVERGENCE ALGORITHM Each upda e packe gene a ed by he HSM echnique indica es ha a ansi ion has occu ed om one model o ano he . I his ansi ion is implemen ed ins an ly, he esul ing use mo emen may appea unna u al and disjoin . The con e gence algo i hm se es o smoo hen he ansi ion, hence inc easing he playabili y o he applica ion and imp o ing he ealism o he econs uc ed use dynamics. This is illus a ed in Figu e 1(a)-(b). Figu e 1(a)-(b): (a) A sudden jump in posi ion occu s when he e is a ansi ion be ween models; (b) Con e gence smoo hens he ansi ion, imp o ing mo emen ideli y. A sudden jump in use mo emen occu s Upda e packe Use s a egy model 1 Use mo emen – use ollows s a egy 1 Use mo emen – use ollows s a egy 2 Use s a egy model 2 (a) (b) Con e gence makes mo emen mo e na u al Upda e packe Use s a egy model 1 Use mo emen – use ollows s a egy 1 Use mo emen – use ollows s a egy 2 Use s a egy model 2 ISSC 2005, Dublin, Sep embe 1- 2 Weigh ed model con e gence blends wo models, he model ha was used up o he mos ecen upda e packe and he new model ha bes desc ibes he emo e use ’s beha iou . This is illus a ed in Figu e 2 whe e a ansi ion has jus occu ed om s a egy 1 o s a egy 2. (x1,y1) is he poin on s a egy 1 a which he en i y was loca ed when an upda e packe was ecei ed. S a ing om his poin he weigh ed model con e gence uses a sec ion o he s a egy 1 model up o poin (x4,y4). Likewise, a sec ion o s a egy 2 om poin (x3,y3) up o poin (x2,y2) is chosen. He e, (x3,y3) is ound by an o hogonal p ojec ion o (x1,y1) on o s a egy 2. Bo h sec ions a e equal in leng h and con ain he same numbe o poin s, N. These wo coo dina e da a se s a e hen blended acco ding o a weigh ing scheme o ob ain a smoo hened pa h. This p ocess o blending he wo long- e m models by an app op ia e weigh ing scheme is desc ibed by he ollowing equa ion: 21 )1( Γ − + Γ = ppW (3) whe e W is he model esul ing om he blending o Γ1 and Γ2; Γ 1 and Γ 2 a e long- e m models; p is a weigh ing ac o wi h 10 ≤ ≤ p. The weigh ing ac o , p, may be gene a ed by a sui able no malized weigh ing unc ion. A na u al blending o models sugges s gi ing mo e weigh ing when close o a s a egy model and co e ing he in e media e dis ance quickly. In ui i ely we wan a g adual smoo h change om he i s model, quickly head o he second model and hen g adually con e ge o he second model – see Figu e 1(b). This desi ed beha iou sugges ed he use o a sigmoid blending unc ion: )( 1 1 ),,( bxa e baxp −− + = (sigmoid) (4) whe e x ∈ [0,1]; a, b ∈ℜ. A a e o con e gence is also speci ied. This de e mines he speed wi h which he weigh ing unc ion begins using he new model and o ge s he old model. I is exp essed as a eal numbe be ween 0 and 1 and is an essen ial ac o o he con e gence p o ocol. In he simula ion es bed he x inpu alues o he con e gence unc ions depends on he a e o he con e gence pa ame e alue. Beginning om 0, x is inc emen ed by he a e o con e gence pa ame e alue on each clock cycle o he es bed (e e y 32ms). This con inues un il x eaches 1. In his pape , ou con e gence echnique is compa ed wi h he s anda d DIS con e gence app oach. In he la e case an in e pola ion algo i hm usually based on cubic splines is employed o in e pola e be ween he las modelled posi ion o he en i y and new posi ion communica ed in he upda e packe . The in e pola ion no mally speeds up he en i y so ha i con e ges o a ealis ic posi ion a he han jumping di ec ly o he posi ion indica ed in he upda e packe . IV SIMULATIONS AND RESULTS In his sec ion he ope a ion o wo con e gence algo i hms is examined: he s anda d DIS smoo hing algo i hm and he no el weigh ed con e gence algo i hm using a sigmoid blending unc ion. Da a was eco ded om a numbe o use s o wo dis inc en i onmen s as desc ibed in (Delaney e al. 2003b; Ma shall e al. 2004a; Ma shall e al. 2004b). Each use na iga ed om a ixed s a loca ion o a ixed end loca ion and he ajec o ies hey aced ou we e sampled using bo h dead eckoning and he HSM. These samples we e hen used o econs uc he ajec o ies using bo h con e gence algo i hms. To acili a e a isual compa ison be ween he a ious plo s p oduced, wo use ajec o ies (one om each o wo di e en en i onmen s) a e used o illus a ion h oughou : ajec o y T1 om es en i onmen 1 and ajec o y T2 om es en i onmen 2. These we e chosen because hey a e s eady s a e ajec o ies wi h in e es ing en i y dynamics. They hus p o ide se e al s a e upda e packe s and hence equi e he use o con e gence h oughou he ajec o y leng h. T1 and T2 a e indica ed as dashed lines in all Figu es. As a p elude o applying he con e gence algo i hm, HSM upda e packe s a e gene a ed o he wo ajec o ies. Figu e 2: Con e gence means ha he e is a smoo h ansi ion om one s a egy o ano he by blending mul iple poin s on each s a egy. S a egy 1 – S1 S a egy 2 – S2 S a egy 3 – S3 (x1,y1) (x3,y3) (x2,y2) (x4,y4) ISSC 2005, Dublin, Sep embe 1- 2 150 200 250 300 350 400 450 500 550 600 650 0 50 100 150 200 250 300 350 400 450 y x Con e gence Ra e: 0.015 These upda e packe s a e hen used o econs uc he ajec o ies a emo e use would econs uc and ende i he e was no con e gence. Figu e 3(a)-(b) shows he upda e packe s gene a ed o T1 and T2 by he HSM wi h a h eshold alue o 10 wo ld uni s and no con e gence algo i hm. S a s indica e he upda e packe s and he dashed line ep esen s he o iginal en i y ajec o y. The econs uc ed ajec o ies a e shown as solid lines and i can be seen ha al hough hey main ain he o e all shape o he o iginal use ajec o ies, hey a e qui e jagged and in ol e sudden jumps in posi ion each ime an upda e a i es. The sec ions p oduced a e simply segmen s o he s a egy models ha ma ch he o iginal ajec o y. The upda e packe s lie be ween hese segmen s and indica e a ansi ion om one long- e m model o ano he . Clea ly, he esul ing ajec o y ende ed o he emo e use is highly un ealis ic, wi h poo ideli y o he o iginal use ajec o y, pa icula ly in e ms o smoo hness. Hence he need o a con e gence algo i hm. The i s a emp a smoo hing he en i y’s emo e ajec o y o make i mo e ealis ic was based on poin - o- poin i s o de linea con e gence, he s anda d smoo hing algo i hm speci ied in he IEEE DIS s anda d (IEEE 1993; IEEE 1995). Applica ion o he con e gence algo i hm o he upda e packe s gene a ed by he HSM is shown in Figu e 4(a)-(b). The a e o con e gence was se o 0.015 and he con e gence dis ance was 10 wo ld uni s. I can be seen ha he gene al cha ac e o he o iginal local ajec o y indica ed by he dashed line is main ained in he econs uc ions. The gaps in Figu e 3(a)-(b) ha e been smoo hened o e . Howe e , he econs uc ion shown by he solid line is s ill somewha jagged wi h sudden, unna u al changes o di ec ion in se e al places. In Figu e 4(b) he boxed a ea indica es an inaccu a ely econs uc ed sec ion. This is a consequence o a cons an con e gence a e being employed ha is slowe han he eloci y o he en i y. This can be ixed by a ying he con e gence a e h oughou he simula ion. This was no implemen ed he e. (a) (b) Figu e 3(a)-(b): Plo s o he emo e econs uc ion o (a) T1 and (b) T2 using upda e packe s gene a ed by he HSM, wi h no con e gence algo i hm. The dashed line ep esen s he o iginal ajec o y. Figu e 4(a)-(b): Plo s o he emo e econs uc ion o (a) T1 and (b) T2 using upda e packe s gene a ed by he HSM, wi h he poin - o-poin con e gence. The dashed line ep esen s he o iginal ajec o y. En i onmen 1 Use 1 T ajec o y 3 x y En i onmen 1 Use 1 T ajec o y 3 x y En i onmen 1 En i onmen 2 Use 1 T ajec o y 3 x y En i onmen 2 Use 1 T ajec o y 3 x y En i onmen 2 0 100 200 300 400 500 600 0 50 100 150 200 250 300 350 y x Con e gence Ra e: 0.015 (b) (a) ISSC 2005, Dublin, Sep embe 1- 2 The no el weigh ed con e gence app oach is now conside ed. The HSM in ol es ansi ions be ween di e en models and each ansi ion in ol es wo models. The weigh ed sigmoid con e gence algo i hm blends he wo s a egy models acco ding o a sigmoid blending unc ion. Th ee pa ame e s can be a ied – he a e o con e gence and he wo pa ame e s ha de e mine he shape o he sigmoid cu e. Figu e 5(a)- (b) illus a es a econs uc ion using a ypical sigmoid blending unc ion wi h a = 15, b = 0.5 and he a e o con e gence = 0.015. The local ajec o y is shown as a dashed line. Once again he esul ing cu es show ha he gaps in Figu e 3(a)-(b) ha e been smoo hened o e . Howe e , he econs uc ion emains somewha jagged wi h some unna u al mo emen in he o m o oscilla ions as indica ed in Figu e 5(b). The pe o mance o he con e gence algo i hm is dependan on he pa ame e s o he sigmoid unc ion. In an e o o unde s and he impac o he sigmoid pa ame e s (i.e. a and b) on he econs uc ion, addi ional smoo hing es s we e ca ied ou . The b alue de e mines he poin a which bo h models a e gi en equal weigh ing in he ansi ion. High alues o b mean ha his poin is u he om he s a o he ansi ion and so he old s a egy cu e will be dominan in he blending p ocess. Lowe alues o b mean ha he new s a egy will domina e o mo e o he ansi ion. A alue o 0.5 esul s in bo h being weigh ed equally when he ansi ion is hal way comple e. Simula ions showed ha o he en i onmen s examined, he mos sui able b alue is 0.5. In mos applica ions i can be en isaged ha he in luence o he old long- e m model will dec ease and he new s a egy will inc ease a a cons an a e, wi h bo h models con ibu ing equally when he ansi ion is 50% comple e. The a alue de e mines he slope o he sigmoid – he g ea e he a alue he g ea e he slope. Simula ions show ha his alue has a di ec e ec on he oscilla ions no ed in Figu e 5(a)-(b). Low alues o a se e o Con e gence Ra e: 0.015 a = 15 b = 0.5 x y Con e gence Ra e: 0.015 a = 15 b = 0.5 x y oscilla ions (a) (b) (b) (a) Con e gence Ra e: 0.015 a = 5 b = 0.5 x y Con e gence Ra e: 0.015 a = 5 b = 0.5 x y Figu e 6(a)-(b): Plo s o he emo e econs uc ion o (a) T1 and (b) T2 using upda e packe s gene a ed by he HSM. Sigmoid weigh ed con e gence is used. Figu e 5(a)-(b): Plo s o he emo e econs uc ion o (a) T1 and (b) T2 using upda e packe s gene a ed by he HSM. Sigmoid weigh ed con e gence is used. ISSC 2005, Dublin, Sep embe 1- 2 a enua e he oscilla ions and as a inc eases, he se e i y o he oscilla ions inc eases. A high alue indica es a s eep slope and only se es o speed up he con e gence p ocess. Ea lie , in igu e 4 i was no ed ha he a e o con e gence was oo slow esul ing in poo accu acy in pa s o he ou pu . He e, he con e gence a e is he same bu he a alue can e ec i ely inc ease his a e and hence, he oscilla ions ob ained. Clea ly, a comp omise be ween model accu acy, ealism o a playe ’s mo emen and he game playabili y is equi ed o choose sui able alues o bo h pa ame e s a and he con e gence a e. Simula ions showed ha alues o a = 5 and b = 0.5 p oduced good esul s o a con e gence a e o 0.015. The associa ed plo s a e shown in Figu es 6(a)-(b). Visually compa ing hese plo s wi h hose in Figu es 4(a)-(b) would seem o indica e ha he o me ob ains a smoo he , mo e na u al ou pu a he expense o model accu acy. Howe e , om he emo e poin o iew his is an accep able ade-o in a wo ld whe e playabili y and he end use pe cep ual expe ience a e mo e impo an han achie ing absolu e consis ency. V CONCLUSIONS This pape has desc ibed a no el con e gence algo i hm based on he blending o long- e m beha iou al models using a sigmoid unc ion. The echnique was e alua ed by isually compa ing i o bo h he o iginal use en i y ajec o y and o he smoo hing algo i hm used in he IEEE DIS s anda d. I was ound ha he smoo hness o he econs uc ed beha iou using he weigh ed sigmoid con e gence algo i hm depends on he a e o con e gence, wi h a high a e o con e gence esul ing in a jagged econs uc ion and a low a e o con e gence esul ing in he loss o beha iou al de ail. The esul s also depend on he pa ame e s employed in he sigmoid unc ion. Reducing he a alue inc eases he na u alness o he econs uc ed cu e. A cen al b alue o 0.5 was ound o be mos sui able. The HSM echnique and he con e gence algo i hms in ol e a numbe o inpu pa ame e s ha de e mine he e icacy o he algo i hms. Ou wo k on con e gence algo i hms has highligh ed he lack o objec i e c i e ia o e alua ing he e ec i eness o such algo i hms. The e is he e o e a need o u he s udies o in es iga e possible objec i e e alua ion measu es in e ms o smoo hness and ideli y o he o iginal beha iou . In addi ion, he use o psycho- pe cep ual da a will be examined o measu e he impac o di e en con e gence algo i hms on he end use s. ACKNOWLEDGEMENT This wo k is suppo ed by Science Founda ion I eland and En e p ise I eland unde g an s no. SC/2002/129/ and IRCSET/SC/04/CS0289. REFERENCES Delaney, D., T. Wa d and S. Mc Loone (2003a). On Reducing En i y S a e Upda e Packe s in Dis ibu ed In e ac i e Simula ions using a Hyb id Model. 21s IASTED In e na ional Mul i-con e ence on Applied In o ma ics, Innsb uck, Aus ia, Feb ua y 10-13, 833-838. Delaney, D., T. Wa d and S. Mc Loone (2003b). Reducing Upda e Packe s in Dis ibu ed In e ac i e Applica ions using a Hyb id Model. 16 h In e na ional Con e ence on Pa allel and Dis ibu ed Compu ing Sys ems, Reno, USA, Augus 13-15, 417-422. Delaney, J. D. (2005). La ency Reduc ion in Dis ibu ed In e ac i e Applica ions using Hyb id S a egy- based Models. Elec onic Enginee ing. Na ional Uni e si y o I eland, Maynoo h. PhD. pages: 271 IEEE (1993). IEEE S anda d o Dis ibu ed In e ac i e Simula ion - Applica ion P o ocols. IEEE S d 1278-1993. I. C. Socie y. New Yo k, IEEE. IEEE (1995). IEEE S anda d o Dis ibu ed In e ac i e Simula ion - Applica ion P o ocols. IEEE S d 1278.1-1995 (Re ision o IEEE S d 1278-1993). I. C. Socie y. New Yo k, IEEE. Lin, K.-C. and D. E. Schab (1994). The pe o mance assessmen o he dead eckoning algo i hms in DIS. Simula ion 63(5): 318-325. Ma shall, D., D. Delaney, S. McLoone and T. Wa d (2004a). Explo ing he Spa ial Densi y o S a egy Models in a Realis ic Dis ibu ed In e ac i e Applica ion. In e na ional Symposium on Dis ibu ed SImula ion and Real- Time Applica ions (DS-RT '04), Budapes , Hunga y, Oc obe 21-23, IEEE, 210-213. Ma shall, D., A. McCoy, D. Delaney, S. McLoone and T. Wa d (2004b). A Realis ic Dis ibu ed In e ac i e Applica ion Tes bed o S a ic and Dynamic En i y S a e Da a Acquisi ion. I ish Signals and Sys ems Con e ence (ISSC), Bel as , June 30 - July 2, IEE, 83-88. McCoy, A., S. McLoone, T. Wa d and D. Delaney (2005). Dynamic Hyb id S a egy Models o Ne wo ked Mul iplaye Games. 19TH Eu opean Simula ion Mul icon e ence (SCS-ESM 2005), Riga , La ia, June 1 - 4, The Socie y o Modeling and Simula ion In e na ional, 727-732.