I n d on e s ian   Jou r n al   o f   E lec t r ica l   E n gin e e r in g  a n d   Com p u t e r   S c ience   Vo l .   3 6 ,   N o .   3 ,  De c e m b e r   20 24 ,   pp.   1 938 ~ 1 949   I S S N:  2 502 - 4 7 52 ,   DO I :  10 . 11591/i j e e cs .v 3 6 . i 3 . pp 1 938 - 1 949             1938     Jou r n al  h o m e page :  ht tp: // ij e e cs . iaes c or e . c om   U t il iz in g  m i n i m u m  sp a n n in g  t r e e s f o r  e f f e c t i v e  m ob il e  si n k   r ou t in g i n  w ir e le ss s e n sor  n e t w o r k s       Anas   Abu   T al e b ,  Am m a r   Od e h   D e pa r tm e nt   of  C o mput e r  S c i e n c e ,  K in g  H us s e in   S c h oo l  of   C omput in g S c i e n c e s ,   P r in c e s s  S uma y a  U ni ve r s it y   f or   T e c hn o l o g y ,     A mm a n, J o r da n       Ar t ic l e   I n f o     AB S T RA CT   A r ti c le  h is tor y :   R e c e i ve d  A pr   27 ,   202 4   R e vi s e d  A ug   22 ,  202 4   A c c e pt e d  A ug   31 ,   202 4       W i t h   m a n y   p rac t i c a l   ap p l i c at i o n s ,   w i r e l e s s   s en s o r   n e t w o r k s   (W S N s )  re p re s e n t   an   i m p o rt an t   f i e l d   o f   s t u d y .   R e a l - w o rl d   ap p l i c at i o n s   o f   W S N s   i n c l u d e  s m art   h o me   a u t o m at i o n ,   h e al t h c ar e ,   ag ri cu l t u r e,   i n d u s t ri al   au t o m at i o n ,   an d   en v i ro n me n t al   mo n i t o ri n g .   W SN s   p re s en t   c o u n t l e s s   ch an ce s   fo r  c r e at i v e   s o l u t i o n s   ac r o s s   v ari o u s   i n d u s t r i e s   as   t h ey   d ev e l o p   an d   b ec o me  mo re  s o p h i s t i c at ed .   Bu t   b ec au s e   t h ey   ar e  u n at t e n d e d ,   w e  mu s t   d e v i s e  w a y s   t o   m ak e   t h em   w o rk   b e t t e r  w i t h o u t   u s i n g   t h e   s e n s o r  n o d e s ’   m o s t   i m p o rt an t   re s o u r ce — b at t e r y   p o w e r .   A   u n i q u e   s i n k   mo b i l i t y   mo d el   fro m  a  d e p l o y ed   W SN   i s   p ro p o s ed   i n   t h i s   p ap e r,   b as e d   o n   co n s t ru c t i n g   a  m i n i m a l   Sp an n i n g   t re e.   T h e   p ro p o s e d   ap p ro a c h   d e ri v e s   a  c o n t ro l l e d   mo v eme n t   m o d e l   f o r  t h e  mo b i l e   s i n k   b as ed   o n   mi n i m al   s p an n i n g   t r ee   (MST )  fe a t u re s .   Co n s e q u en t l y ,   fi x e d   n o d e s   w i l l   b e   s c h ed u l e d   a n d   v i s i t ed   t o   s av e   ro u t i n g   o v e rh e a d   an d   i m p ro v e   n e t w o r k   e ffi ci e n cy .   U s i n g   t h e   p ro p e rt i e s   o f  t h e   mi n i m al   s p an n i n g   t re e,   t h e   m o v i n g   s i n k   n o d e   c a n   v i s i t   i mmo b i l e   s e n s o r   n o d e s ,   w h i c h   i s   t h e  mo s t   e ff ec t i v e  ap p ro ach   t o   g at h e r   d at a  a n d   s e n d   i t   t o   t h e  b as e   s t at i o n .   T h e  e ff ec t i v en e s s   o f  W SN s   w as   e x ami n ed   w h e n   i m p l eme n t i n g   t h i s   mo b i l i t y   mo d e l ,   a n d   w e  u s e d   t h e  N S - 2   s i mu l at o r   t o   r u n   s i m u l at i o n s   t o   as s e s s   h o w   e ffi ci e n t l y   t h e   s u g g e s t e d   s t rat e g y   p e rfo r med .   O u r  fi n d i n g s   d em o n s t rat e   t h at   W SN   p e rf o r m an ce  c an   b e  s i g n i f i c an t l y   en h a n ce d   b y   i m p l em e n t i n g   t h e  p ro p o s e d   me t h o d .   K e y w o r d s :   M o bi l e   s i nk   M o bi li t y   m o de l   P a t h   pl a nni ng   P r i m ’ s   a l go r i t hm   W i r e l e s s   s e ns o r   n e t w o r ks   Th i s   i s   a n   o p en   a c ces s   a r t i c l e  u n d e r   t h e  CC  B Y - SA   l i cen s e.     C or r e s pon din g  A u th or :   An a s   Ab u  T a l e b   De pa r t m e n t   o f   C o m put e r   S c i e n c e ,   Ki ng  Hus s e i n  S c h o o l   o f   C o m put i n g  S c i e nc e s   P r i nc e s s   S u m a y a   U ni ve r s i t y   f o r   T e c hn o l o g y   Al - J u b e i ha   11941,   Amm a n ,   J o r da n     E m a i l :  a . a b ut a l e b@ ps ut . e du. j o       1.   I NT RODU C T I ON   W i r e l e s s   s e ns o r   n e t w o r ks   ( W S N s )   c o m e   a c r o s s   c h a ll e n g e s   i n   t h e i r   e m p l o ym e n t .   T o   s upp o r t  m o bil i t y - de pe n d e n t   a ppl i c a t i o ns ,   l i ke   e m e r ge n c y   a n d  s e i s mi c   r e c o v e r y ,   f i e l d  s ur v e il l a nc e   i n   c o m b a t,   a ni m a l   m o ni t o r i n g,   a n d  a pp l i c a t i o n s   f o r   l a w  e nf o r c e m e n t .   On e   us e   c a s e   f o r   W S N s   t h a t  us e s   5G  i n t e r n e t   of   t hi ngs   ( I o T )   t e c hn o l o g y   i s   ps y c h o a c o us t i c   m o ni t o r i n g.   T he r e f o r e ,   a   dy n a mi c   a n d  a da pt i v e   W S N   s uppo r t i n g  m o bil i t y   i s   n e e d e d  to   e n a bl e   d e pe n da bl e   c o m m u ni c a t i o n ,   c o n s i s t e n t   n e t wor k  c o n n e c t i vi t y ,   e n e r g y   s a vi ng s ,   a n d  a   l o n ge r   ne t wor k  l i f e s pa n   f o r   t h e s e   a pp li c a t i o n s   [1 ] ,  [ 2] .   T h e r e f o r e ,   s e l f - o r ga ni z i ng  a n d  f a u l t - to l e r a n c e   c a pa bi li t i e s   m u s t   b e   pr e s e r v e d  f o r   t h e s e   ne t wor ks   to  o pe r a t e   pr o pe r l y   [3 ] - [ 6] .   B e c a us e   s t a c k  m o bil i t y   va r i a t i o n s   s i g ni f i c a n t l y   im pa c t   W S Ns ’   c a pa c i t y   to  s c a l e   a n d  s a v e   e ne r g y ,   e n e r g y - e f f i c i e n t   de vi c e s   m u s t   b e   m a de   a va i l a bl e .   P e r f o r m a n c e   de te r i or a t i o n   a n d   e r r a t i c   b r oke n   l i n ks   m us t  t h us   b e   e x a m i n e d  to  d e l i v e r   a   tr u s tw or t h y   m o bi l i t y   m o de l   [ 1 ] ,   [ 7] ,   [ 8 ] .   Evaluation Warning : The document was created with Spire.PDF for Python.
I n do n e s i a n   J   E l e c   E n g  &   C o m p  S c i     I S S N:   2 5 0 2 - 4 7 52       Util iz ing  minimum  s panning  tr e e s   f or   e ff e c ti v e   mo bil e   s ink  r outi ng  in  w ir e les s   s e ns o r   …  ( A nas   A bu  T aleb )   1939   Nu m e r o us   m o de l s   h a v e   be e n   pr e s e n t e d  a n d  a r e   c on s i d e r e d  g oo d  c h o i c e s   f o r   ad - h o c   n e t w o r ks .   B u t  i n  W S N s ,   t h e y   b e h a v e   d i f f e r e n t l y ,   l e a d i ng  to  l o we r   qua l i t y   o f   s e r vi c e   ( Qo S )   r a t i n g s   a n d  hi g h e r   e n e r g y   u s a ge .   S t a t e d  di f f e r e n t l y ,   s e n s o r   n e t wo r ks   c a n   t r a n s m i t   m u l t i p l e   da t a   t y pe s ,   i nc l ud i n g  vi de o .   A s   a   r e s u l t ,   bi t s t r e a m   a n d  o t h e r   Q o S   c r i t e r i a   m us t   b e   f u l f il l e d.   I n t e r e s t i ng l y ,   Qo S   i n   W S N s   i s   d i s t i n gu i s he d  i n t o   t w o   g r o u ps :  n o de   r e a d i n g,   c o v e r a ge ,   de p l o y m e n t ,   a n d  n u m b e r   o f   a li ve   n o de s ;   t h e   f o r m e r   i s   r e li a n t   o n   t h e   n e t wor k,   whil e   t h e   l a t t e r   i s   de pe n d e n t   o n   t h e   a pp l i c a t i o n .   T h e   s e c o n d  gr o up  f o c us e s   o n   e f f i c i e n t l y   u s i ng  e ne r g y ,   b a n dw i dt h ,   t h r o ugh put,   a n d  pa c ke t   de l i ve r y   r a t i o .   S t a t e d  di f f e r e n t l y ,   t h e   r a n do m   wa y po i n t   m o bil i t y   m o de l   ( R W )   pe r f o r m s   we ll   i n   a d  h o c   n e t wo r ks .   Ne v e r t h e l e s s ,   i t   i s   n o t   a   g oo d  a l t e r n a t i v e   i n   W S Ns   due   to  i t s   unif o r m   d i s t r i b ut i o n   a n d  poo r   v e l o c i t y   s e l e c t i o n  [9 ] - [ 13 ] .   As   a n   a l t e r n a t i v e ,   t h e   n o m a d i c   c o m m u ni t y   m o bil i t y   m o de l   w a s   de v e l o pe d  t o  s o l v e   t h e   l im i t a t i o n s   o f   t h e   R W   m o de l .   T h e   r a n do m   r o a m i ng  o f   n o de s   b e t we e n   s i t e s   m a ke s   t hi s   a r c hi t e c t ur e   a ppr o pr i a t e   f o r   m o bil e   c o m m u ni c a t i o n s   i n  c o nf e r e n c e s   a n d  a pp li c a t i o ns   s uppo r t i n g  mi li t a r y   o pe r a t i o ns .   B a s e d  o n   t h e   gr o up ’ s  c o l l e c t i v e   m o t i o n ,   a   r e f e r e n c e   po i n t   i s   a l s o   e s t a bl i s h e d  f o r   e a c h   m o m e n t .   T hi s   m e t h o d  r e qui r e s   L a r ge   a m o un t s   o f   e ne r g y   t o  l o c a t e   o r   f i nd  a   s i n g l e   n o de   [ 14 ] ,  [ 15] .   A   c i r c u l a r   m o bil i t y   m o de l   b a s e d  o n   ge o gr a phi c a l   i nf o r m a t i o n   wa s   t h us   i n t r o duc e d  to   m a n a g e   t h e   m o bil i t y   o f   s i n k  n o de s .   Da t a   i s   c o l l e c t e d  by   t hi s   m o de l   u s i ng  a   f i xe d,   c i r c u l a r   po i n t - b a s e d  t r a c k.   T h e   n o de s   m us t   s t a y   i d l e   f o r   e i g h t   o r   s i x t e e n   c y c l e s ,   a   s i g nif i c a n t   c o n s t r a i n t .   P r e m i   a n d  S h a ji   [ 14] ,   a   m o de l   o f   w i n d   m o v e m e n t   us i n g  e i g h t   d i r e c t i o n s   wa s   pu bli s h e d  t o  pr o l o n g  t h e   n e t wo r k ’ s   l if e s pa n .   He n c e ,   to   de t e r mi ne   o n e   n ode ’ s   l oc a t i o n ,   a   g r oup   o f   n o de s   m us t   m o v e   a n d   e x p e n d  e n e r g y   [ 15 ] .   Hi gh   n e t w or k  pe r f or m a n c e   i s   r e qui r e d  f r o m   t h e   w i n d  m o bi l i t y   m o d e l   a tt r i b u t a bl e   to  th e   a ddi t i o n a l   pa us e   t i m e ,   n ode   s p e e d ,   a n d   i n t e r d e pe n d e n c i e s   [ 1 6 ] .   M o r e o v e r ,   t h r e e   s u b s y s t e m s   a r e   a l s o   pr e s e n t   i n  s e n s o r   n o de s :  c o m m u ni c a t i o n ,   pr o c e s s i n g,   a n d   s e n s i ng.   B e c a u s e   t h e   a m o u n t   o f   e n e r g y   r e qu i r e d  t o   c o n v e y   a   m e s s a ge   de p e n d s   o n   t h e   d i s t a n c e   be twe e n   t he   s o ur c e   a n d  de s t i n a t i o n   n o de s ,   t h e   c o m m u ni c a t i o n s   s ubs y s t e m   i s   a l s o   t h e   m a i n  e n e r g y - c o n s u mi ng  s o ur c e   [ 17 ] ,  [ 18] .   T h e r e f o r e ,   c o m pa r e d  to   s i n g l e - h o p  c o m m u nica t i o n ,   m u l t i - h o p  c o m m u ni c a t i o n   c a n   s h o r t e n   t r a n s m i s s i o n  d i s t a nc e s ,   b ut   a t  t h e   c o s t  o f   l o n g e r   de l a y s   [ 17 ] ,  [ 19] .   A dd i t i o n a ll y ,   I E E E   802 . 15. 4   g o v e r n s   c o m muni c a t i o n  b e t we e n   s e n s o r   n o de s ,   wi t h   t h e   pr e m i s e   t h a t   e a c h   s e n s o r   n o de ’ s   e n e r g y   de t e r m i ne s   t h e   c o m m u ni c a t i o n   r a n ge .   T y p i c a ll y ,   i t   i s   u n de r   100  m e t e r s   [ 20] .   T h e   s o l ut i o n   t o   t h i s   pr o bl e m   h a s   b e e n   s ugge s t e d  us i n g  a   m o bi l e   de vi c e   r i c h   i n   e n e r g y   s i nk  n o de s   or   n o de s .   W i t h   t hi s   s t r a t e gy ,   da t a   i s   c o l l e c t e d  f r o m   f i xe d  s e ns o r   n o d e s   a n d  s e n t   to   t h e   b a s e   s t a t i o n   ( B S )   vi a   a   m o bil e   s i nk  t h a t   f o l l o w s   a   s pe c i f i e d  m o bil i t y   mo de l   o r   m o ve s   r a n do m ly .   Us i ng  a   m o v a bl e   s i nk   f ur t h e r   im pr o v e s   t h e   pe r f o r m a n c e s   o f   W S N s   by   r e du c i ng  t h e   di s t a n c e   a t   whi c h   a   f i xe d  n o de   m us t   b r o a d c a s t   da t a ,   mi n im i z i ng  t h e   o v e r a l l   n u m be r   o f   n o de s   t h a t   a c t   a s   i n t e r m e d i a r i e s ,   i m pr o vi n g  n e t wor k  t h r o ugh put,   a n d  pr o vi d i n g  c o v e r a ge   f o r   d i s t a n t   l o c a t i o n s   [ 3] .   B e s i de s   ut i l i z i ng  a   m o bil e   s i nk  or   s i n k s ,   r e s e a r c h e r s   h a v e   pr o p o s e d  di f f e r e n t   wa y s   to  i m pr o v e   W S N   pe r f o r m a n c e .   F o r   e x a m p l e ,   a   c l us t e r e d  r o u t i n g  pr oto c o l   wa s   de f i ne d  i n   t h e   wo r k  p r o p o s e d  i n   [ 21] .   A   c l us t e r   h e a d  i s   c h o s e n   a c c o r di n g  to   t h e   c e n t r o i d  po s i t i o n ,   a n d  t h e   ga t e wa y   i s   s e l e c t e d  f r o m   w i t hi n   t h e   c l us t e r .   T h e   s t udy   t h a t   t hi s   pa pe r   s ugge s t s   de pe n d s   o n   de r i vi n g  a n   M S T   f r o m   a   r a n do m ly   d e p l o y e d  ne t wor k.   T h e n ,   t h e   m o bil e   s i n k  ( M S )   wi ll   a do pt  t h e   o r de r   a c c o r di n g  to  whi c h   n o de s   we r e   a dde d   to   t h e   M S T   a s   t h e   pa t h   to  b e   a do p t e d  to   vi s i t   f i xe d  n o de s   a n d  c o l l e c t   da t a .   T hi s   a r t i c l e   pr o po s e s   c o m bi n i ng  m u l t i - h o p  a n d  s in g l e - h o p  r o u t i n g  t o  a c hi e v e   hi g h   n e t wo r k   pe r f o r m a nc e   a n d  mi n im i z e   l a t e n c y .   T o  s um m a r i z e ,   n o t   us i n g  a   m o bil e   s i nk  w i ll   i nc r e a s e   t h e   us e   o f   m u l t i - h o p  r o u t i n g ;   t h us ,   m e s s a ge s   w i ll   s u f f e r   f r o m   hi g h   de l a y s   i n   b e i ng  de li ve r e d  to  t h e   B S .   On   t h e   ot h e r   h a n d,   r e l yi ng  o n   s i n g l e - h o p  r o u t i n g   e nh a nc e s   t h e   pe r f o r m a nc e   r e ga r d i n g  o n e - wa y   de l a y .   Ho we v e r ,   s t a t i o n e r y   n o de s   mi g h t   n e e d  t o  wa i t   l o n g  f o r   t h e   M S   to  vi s i t   t h e m   a n d  s e n d  t h e m   da t a .   A s   a   r e s u l t ,   s t a t i o n   n o de s   m i g h t   s u f f e r   f r o m   b u f f e r   o v e r f lo w,   a n d  t h e   da t a   r e p o r t e d   to   t h e   m o bil e   s i nk  m i g h t   b e   o u t da t e d.     T o  r e s o l v e   t h e s e   i s s ue s ,   t h i s   pa pe r   s ugge s t s   us i n g  a   s i n g l e   e n e r g y - r i c h   M S   t h a t  wi ll   m o v e   w i t hi n   t h e   W S N  ba s e d  o n   a   pa r t i c u l a r   m o bil i t y   m o de l   t o  ga t h e r   i nf o r m a t i o n   f r o m   s t a t i o n a r y   s e ns o r   n o de s .   T h e   m o bil i t y   pa r a d i g m   t hi s   s t ud y   s ugge s t s   i s   pr e d i c a t e d  o n   de r i vi ng  a   mi n i m u m   s pa nni ng  t r e e   to  b u i l d  t h e   pr e c i s e   r o u t e   t h e   M S   w i ll   t a ke   to   vi s i t   s t a t i o na r y   s e n s o r   n o de s   to   c o l l e c t   i nf o r m a t i o n   f r o m   t h e m .   Al s o ,   t h e   pr o p o s e d  m o de l   r e l i e s   o n   h a vi ng  a   s t a t i o n a r y   n o de   t h a t  us e s   m u l t i - h o p  r o u t i n g  t o  s e n d  m e s s a g e s   to   t h e   M S   w h e n   i t   i s   im po s s i bl e   to   us e   s i n g l e - h o p  r o u t i n g  b e c a us e   t h e   M S   i s   n o t   i n   c o m m u ni c a t i o n   r a n g e .   Ut i li z i ng  th e   NS - 2  s i m u l a t o r ,   o n e   m a y   im i t a t e   t h e   s ugge s t e d  m o bil i t y   m o de l ,   a n d  i t s   pe r f o r m a n c e   i s   e x a mi ne d  a c r o s s   va r i o us   M S   s pe e ds   a n d  n e t wo r k  s i z e s .   T h e   m o bi li t y   m o de l   de s c r i be d  i n   t hi s   wo r k   i s   s t ud i e d  us i ng  t h r e e   pa r a m e t e r s :  pa c ke t   de l i ve r y   r a t i o ,   a v e r a ge   o n e - wa y   de l a y ,   a n d  n e t wo r k   t h r o ugh put.   T o  f ur t h e r   e x p l a i n ,   t hi s   pa pe r ’ s   pr i m a r y   c o n t r i b ut i o n   c a n   be   s u m m e d  up  a s   f o l l o w s :   a)   I n t r o duc i n g  a   n e w  s t r a t e gy   to   s i n k  m o bi li t y   t h a t   c a n   b e   ut i li z e d  to   ga t h e r   i nf o r m a t i o n   f r o m   s t a t i o n a r y   s e n s o r   n o de s .   b)   C o m bi n i ng  t h e   us a ge   o f   m u l t i - h o p  a n d  s i n g l e - ho p   r o u t i n g  t e c h ni que s   to  i m pr o v e   pe r f o r m a n c e   by  r e duc i n g  de l a y   a n d  e ns ur i n g  t i m e ly   de li ve r y   o f   i nf o r m a t i o n   f r o m   s t a t i c   n o de s   to  t h e   m o bil e   s i nk.   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 5 0 2 - 4 7 52   In do n e s i a n   J   E l e c   E n g   &   C o m p  S c i ,  Vo l .   3 6 ,   N o .   3 ,  De c em b e r   20 24 :   1938 - 1949   1940   c)   S i m u l a t i n g  t h e   s ugge s t e d  wor k  a n d  e x a m i n i n g  t h e   n e t wor k ’ s   pe r f o r m a n c e   i n   li g h t   o f   s e ve r a l   pe r f o r m a n c e   m e a s ur e s .   C o n s e que n t l y ,   a n   a n a ly s i s   o f   t h e   i m pa c t   o f   t h e   m o ve m e n t   m o de l   b e i ng  pr o p os e d  w i ll   be   c o n duc t e d.   A dd i t i o n a l ly ,   t h e   i de a l   c i r c u m s t a n c e s   c a n   b e   i de n t i f i e d,   s uc h   a s   t h e   s i z e   o f   t h e   s e ns o r   n e t wo r k   a n d  t h e   s pe e d  o f   t h e   m o bi l e   s i n k  m o de .   T hi s   pa pe r   w i ll   be   o r ga ni z e d  i n t o   t h e   f o l l o w i ng  s e c t i o ns .   A   b r i e f   e x p l a na t i o n   o f   M S T   i s   g i ve n   i n  s ubs e c t i o n   2. 1 .   A   s ur v e y   o f   pr e vi o us   m o de l s ’   l i t e r a t u r e   i s   i nc l ude d  i n   s u bs e c t i o n   2. 2 .   T h e   m e t h o d  a n d  t h e   s ugge s t e d  m o bil i t y   m o d e l   a r e   e x p l a i ne d  i n   s e c t i o n   2,   a l o n g  w i t h   t h e   pe r f o r m a n c e   m e t r i c s   a n d  s im u l a t e d  s c e n a r i o s ,   to   e x a m i ne   t h e   e f f i c a c y   o f   t h e   pr o p o s e d   w o r k .   T h e   s i m u l a t i o n ’ s  r e s u l t s   a r e   de s c r i be d  i n   s e c t i o n   3,   a l o n g  w i t h   a   c o m pa r i s o n   w i t h   t h e   ot h e r   t h r e e   m o de l s .   I n   s e c t i o n   4,   t h e   l a s t   o b s e r va t i o ns   a r e   c o v e r e d.       2.   M E T HO D   2. 1.    Over view   of   p r i m ’ s   m in im u m   s p an n in g  t r e e   As   s t a t e d  i n   [ 22] ,   P r i m ’ s   a l go r i t hm   i s   gr e e d y   f o r   de t e r m i ni ng  a n   u n d i r e c t e d,   we i g h t e d  gr a ph ’ s  mi n im a l   s pa nni ng  t r e e   ( M S T ) .   T h e   s ubs e t   o f   e dge s   i n   a   gr a ph   t h a t   j o i n s   a l l   v e r t i c e s   t o  m i n im i z e   th e   e dge s ’   o v e r a l l   we i g h t   w i t h o u t   c r e a t i n g  a   c y c l e   i s   k n o w n   a s   a   M S T .   R e m e m be r   t h a t   t h e r e   m u s t   n ot   b e   a   c y c l e   i f   y o u   us e   P r i m ’ s   a ppr o a c h   to  de t e r m i ne   t h e   M S T   o f   a   gr a ph .   A s   s t a t e d   ot h e r w i s e ,   i f   n o de   o n e   l i nks   to  n o de   t w o  a n d  n o de   t w o  to   n o de   3,   n o de   t h r e e   c a nn o t  l i nk  to   n o de   o n e   a ga i n   s i nc e   t h a t   w o ul d  c r e a t e   a   l o o p .   An o t h e r   t e r m   f o r   c o s t  t h a t  i s   f r e que n t l y   u s e d  i s   t h e   tot a l   we i g h t   o f   t h e   e dge s .   P r i m ’ s   a ppr o a c h   a l s o   a i m s   t o   f i n d  t h e   s m a ll e s t   c o s t   tr e e   t h a t   c o v e r s   a ll   o f   t h e   gr a ph ’ s  v e r t i c e s   w i t h o ut   o m i t t i n g  a ny   o f   t h e m .     T h us ,   a n o t h e r   c o n s i de r a t i o n   i s   t h a t   a l l   v e r t i c e s   m us t  b e   i nv o l v e d  to   o b t a i n   t h e   M S T .   P r i m ’ s   a l go r i t hm ,   a l s o   r e f e r r e d  to  a s   J a r ní k ’ s   a l go r i t hm ,   i t   wa s   i ni t i a ll y   d e v e l o pe d  i n   1930  by   C z e c h  m a t h e m a t i c i a n   Vo j t ě c h   J a r ní k.   P r i m ’ s   a l go r i t hm  g ot  i t s   n a m e   a f t e r   R o b e r t  C .   P r i m   r e d i s c o v e r e d  i t   a n d  publi s h e d  i t   i n   1957  [ 22] .   P r i m ’ s   a l go r i t hm   o pe r a t e s   by   s t a r t i n g  a t  a ny   ve r t e x ,   a ddi n g  t h e   e dge   w i t h   t h e   s m a l l e s t   we i g h t   b e t we e n   i t   a n d  t h e   n e x t   v e r t e x   i n  t h e   tr e e ,   a n d  c o n t i n u i ng  u n t i l   a ll   v e r t i c e s   a r e   i n c l ude d   a s   s h o w n   i n   F i gur e   1 .   T o   c l a r i f y ,   c o n s i de r   t h e   r a n do m   gr a ph   pr e s e n t e d  i n   F i gur e   1 ( a ) .   T h e   M S T   t h a t   r e s ul t s   f r o m   s t a r t i n g  a t   n o de   f o ur   i s   s h o w n   i n   F i gur e   1 ( b ) .   I n   oth e r   wo r ds ,   t h e   M S T   ge n e r a t e d  s t a r t i n g  f r o m   n o de   f o ur   w i l l   a dd  n o de   3.   Af t e r   t h a t ,   n o de   o n e   i s   a dde d.   T h e n ,   no de   t w o   i s   a dde d - c o n s e qu e n t l y ,   t h e   a l go r i t hm   a dds   n o de s   7,   6,   a n d  5,   r e s pe c t i v e ly .             ( a )   ( b )     F i gur e   1 .   C o n s t r uc t i n g  M S T   f r o m   a   r a n do m   g r a p h   ( a )   r a n do m   gr a ph   r e pr e s e n t i n g  a   n e t wo r k     a n d  ( b )   t h e   de r i v e d  m i n im u m   s pa nni ng  t r e e       2 . 2.     M ob il it y  m od e l s   S e v e r a l   a c a d e m i c   a r t i c l e s   h a v e   pr o po s e d  m o de l s   o r   m e t h o ds   t h a t   f a c il i t a t e   m o bi li t y   i n  W S Ns .   No de   m o bil i t y   i n   W S Ns   de s c r i be s   a   n o de ’ s   c a pa c i t y   t o  m o v e   i t s e lf   a f t e r   de p l o y m e n t ,   a c c o r di n g  to   [ 23] .   T h e r e f o r e ,   t h e   m o bil i t y   a l go r i t hm s   o r   s e n s o r   n o de   m o de l s   c a n   be   c l a s s i f i e d  i n to   t w o  m a i n   t y pe s .   W he r e a s   t h e   s e c o n d  a ppr o a c h   i s   pr e d i c a t e d  o n   a l l o w i ng  e v e r y   s e ns o r   n o de   to  m o v e ,   t h e   f i r s t   i nv o l v e s   us i ng  M S s   t h a t   c a n   a c c e pt   da t a   f r o m   f i xe d  s e n s o r   n o de s   whi l e   i n   m o t i o n .   S i nc e   t hi s   d i r e c t l y   pe r t a i n s   t o  t h e   pr o p o s e d  m o de l ,   o u r   r e vi e w   w i ll   f o c u s   o n   s t udi e s   i nv o l v i ng  o nl y   o n e   M S   t h a t  t r a v e l s   t o   ge t  da t a   f r o m   f i xe d  n o de s .   T o  r e duc e   b ot h   t h e   r a n ge   o f   c o m m u ni c a t i o n   a n d  t h e   M S ’ s   t r a v e l   d i s t a n c e ,   a   pa t h   pl a nni ng - b a s e d  da t a   c o l l e c t i o n   t e c hni qu e   wa s   i m p l e m e n t e d  i n   t h e   s t udy   s ugge s t e d  i n   [ 24] .   A n   i nn e r   c e n t e r   pa t h   p l a nni ng   a l go r i t hm   wa s   e m p l o y e d  to   m i nim i z e   t h e   d i s t a nc e   a n   M S   h a s   t o  c o v e r .   A   b a c k - r o u t i n g  t e c hni que   wa s   a l s o   Evaluation Warning : The document was created with Spire.PDF for Python.
I n do n e s i a n   J   E l e c   E n g  &   C o m p  S c i     I S S N:   2 5 0 2 - 4 7 52       Util iz ing  minimum  s panning  tr e e s   f or   e ff e c ti v e   mo bil e   s ink  r outi ng  in  w ir e les s   s e ns o r   …  ( A nas   A bu  T aleb )   1941   i n t r o duc e d  to   s o l ve   t h e   m o v e m e n t   r o u t e   b a c k  pr o pa ga t i o n   i s s ue .   F o r   t h e   M S   to  m o ve   a ppr o pr i a t e l y ,   t h e   s ugge s t e d  de s i g n   m us t   a l l o w  i t   to   m a ke   a da pt i v e   de c i s i o n s .   F ur t h e r m o r e ,   to   l o we r   e n e r g y   us a g e   a n d  i nc r e a s e   t h e   l o n ge vi t y   o f   W S N s ,   t h e   r e s e a r c h   i n   [ 25]   r e c o m m e n de d  a ddr e s s i ng  t h e   r e l a y   s e l e c t i o n   pr o bl e m .   As   s uc h ,   t h e   s ugge s t e d  s t udy   s p li t s   t h e   n e t wo r k   i n t o  c l u s t e r s   u t i li z i ng  t h e   k - m e a ns   a l go r i t hm .   A   c l u s t e r   h e a d  s e l e c t i o n   t e c hni que   b a s e d  o n   m o va bl e   s in ks   wa s   pr o p o s e d  to  i m pr o v e   e n e r g y   c o n s u m pt i o n   i ns i de   th e   c l u s t e r .   T o  c o l l e c t   da t a   a n d  s a v e   e n e r g y   d i s s i p a t i o n   f o r   b o t h   t h e   c l u s t e r   h e a d  a n d  s t a t i c   s e n s o r   n o de s ,   t h e   M S   n o de   wi ll   a c t   a s   a   c l u s t e r   h e a d  n e a r   i mm o bil e   s e ns o r s .   K o h o n e n ’ s   s e lf - o r ga ni z a t i o n   m a p  ( S OM )   pr o vi de d  t h e   b a s i s   f o r   t h e   m o bil i t y   m o de l   t h e   r e s e a r c h  a ut h o r s   r e p o r t e d   i n   [ 26] .   T h e i r   r e s e a r c h   us e s   K o ho n e n   S OM   to  de t e r m i ne   t h e   r o u t e   t a ke n   by   t h e   M S .   T h us ,   t h e   M S   m o v e s   w hi l e   i t   i s   m o vi ng  a n d  s t o ps   wh e n   i t  i s   pa us i ng.   Dur i n g  t h e   h a l t   pe r i o ds ,   t h e   m o v a bl e   s i n k  w i ll   e n dur e   w h e r e   i t   i s   f o r   a   pa r t i c u l a r   pe r i o d  b e f o r e   s t a r t i n g  t o   m i gr a t e   to   a   n e w  s i t e   s e l e c t e d  by   t h e   K o h o n e n  S OM ,   a n d  s o  f o r t h ,   un t i l   c h a n ge s   i n   t o p o l o g y   a r i s e   f r o m   t h e   e xh a us t i o n   o f   e ne r g y .   T hi s   w i ll   l e a d  to  a   f r e s h  K o h o n e n   S OM   c o m put a t i o n   o f   t h e   m o bil i t y   r o u t e .   M o r e o v e r ,   a   c oo pe r a t i ve   s t r a t e gy   wa s   i n t r o duc e d   i n   [ 27]   to  m o ni t o r   t h e   e n vi r o nm e n t   f ur t h e r   a n d   de t e c t   a b n o r m a li t y   i n  W S Ns .   T h e   s ugge s t e d  a pp r o a c h   c o n s i s t s   m o s t l y   o f   t wo   pa r t s .   F i r s t   a n d  f o r e m o s t ,   a   we i g h t e d  Ga us s i a n   c o v e r a ge   t e c hni que   w i ll   b e   u s e d  to   de pl o y   t h e   f i xe d  s e n s o r   n o de s   c o l l a b o r a t i v e l y .   I n   c o n t r a s t ,   t h e   s e c o n d  po r t i o n   de a l s   w i t h   r o u t e   pl a nni ng  f o r   t h e   M S .   I t  r e l i e s   o n   a l t e r i n g  a n   a n o m a ly   s e a r c h   a n d   a c t i v e   s ur v e il l a nc e   m e c h a ni s m   t h a t   us e s   a   M a r k o v   de c i s i o n   pr o c e s s   m o de l .   T h e   m a i n  go a l   i s   t o   de t e c t  a bn o r m a li t i e s   i n   t h e   e nvi r o nm e n t   qu i c k l y   s o   t h a t   t h e   m o bil e   m o de   c a n   r e a c t   p r o pe r l y   u s i ng  a   c um u l a t i v e   r e wa r d  f u n c t i o n .   T o  i m pr o v e   W S N s   pe r f o r m a n c e   a n d  i nc r e a s e   t h e ir   l if e s pa n ,   a n o t h e r   s t udy   i s   s ugge s t e d  i n   [ 28]   t h a t  s p l i t s   t h e   n e t wor k  i n t o   z o n e s .   T h e   M S   w il l   pa s s   c l o s e   t o  t h e   hi g hly   l a de n   a r e a .   R e m e m be r i n g  t h a t   a   f uz z y  l o g i c   s y s t e m   i s   e m p l o y e d  to   c h oo s e   t h e   z o n e   u n de r go i n g  s u b s t a n t i a l   l o a d  to  a c c o un t  f o r   a ny   pot e n t i a l   un c e r t a i n t i e s   i s   c r uc i a l .   Ya l c i n   a n d  E r de m   [ 29]   s ugge s t s   a n   a da pt a bl e   m o bil e   r o u t i n g  m e t h o do l o g y   f o r   b ur s t  t r a f f ic   i de n t i f i c a t i o n .   I n   a ddi t i o n ,   t h e   n e t w o r k   a r c hi t e c t ur e   t h a t  i s   b e i ng  s ugge s t e d   i s   pr e d i c a t e d  o n   de pl o yi ng  t w o  m o v a bl e   s i nks ,   a n d  t h e   m e t h o d  r e l i e s   o n   s p l i t t i n g  t h e   c l u s t e r s   i n   t h e   n e t wor k  i n to   t w o  g r o ups .   S ub s e que n t l y ,   e v e r y   s e ns o r   n o de   wi ll   o ve r s e e   a   s i ng l e   gr o up   a n d  i n t e r a c t   wi t h   t h e   c l u s t e r   m a s t e r s .   F ur t h e r m o r e ,   t h e   M S   w i l l  pa y   pa r t i c u l a r   vi s i t s   t o   t h e   c l us t e r   h e a ds   i n  t h e   gr o up .   C o n ve r s e ly ,   w h e n   a   t r a f f i c   b ur s t   i s   o bs e r v e d,   t h e   m o v a bl e   s i n k  w il l   m o v e   n e a r   t h e   h e a vil y   l o a de d  c l us t e r   h e a d  a n d  i g n o r e   t h e   s e que n c e   o f   vi s i t s   to   t h e     c l u s t e r   h e a ds .   Wu   e t  al.   [ 30] ,   a n   e n d - to - e n d  da t a - ga t h e r i n g  m e t ho d  s t r a t e gy   ba s e d  o n   o p t i mi z i ng  a n t   c o l o ni e s   wa s   a l s o   i n t r o duc e d.   T h e   s ugge s t e d  a pp r o a c h   i s   pr e d i c a t e d  o n   c o n s t r uc t i n g  a   da t a   f o r wa r di n g  t r e e   a n d  s e l e c t i n g   da t a   c o l l e c t i o n   l o c a t i o ns   r a n do m ly .   C o n s e que n t l y ,   a   pr e di c t e d  a n d  de t a i l e d  i t i ne r a r y   o f   t h e   M S   i s   pr o vi de d.   T a l eb   [ 3 1 ] ,   a   m o d e l   b a s e d   on   a   g e n e t i c   a l g or i t hm s   m ode l   i s   i n tr oduc e d .   T h e   M S ’ s   op t i m a l   di r e c t i o n   o f   m o v e m e n t  i s   de te r m i n e d  by   t h e   m o bi l i t y   m o de l   wi t h   t h e   a ppl i c a t i o n   o f   ge n e t i c   a l g or i t hm s .   S ub s e que n t l y ,   t h e   M S   wi l l   e m p l o y   s i n g l e - h op   f or w a r di n g   to  r e a c h   t h e   n ode s   i n   t h e   c o n s tr uc te d   pa th   a n d   a c q u i r e   da ta   f r o m   t h e m .   H ow e v e r ,   n ode s   n ot  i n c l ude d   i n   th e   M S   tr a v e l   p a t h   us e   m u l t i - h op   r ou t i n g  to  c o n v e y   pa c k e t s   to  th e   M S .   A ddi t i o n a l l y ,   to  i m pr o v e   da ta   tr a n s f e r   a n d   m i ni m i z e   r ou t i n g   pa t h   m od i f i c a t i o n s ,   th e   m o v e m e n t  o f   t h e   MS   i s   s p l i t   b e twe e n   m o v e m e n t  a n d   pa us e   i n te r v a l s .   I n   oth e r   wor d s ,   d u r i n g  t h e   m o v e m e n t  ph a s e ,   t h e   M S   m i gr a tes   to  n e w  pl a c e s   de te r m i n e d   by   t h e   s u gge s te d   a l g or i t hm   wh i l e   r e m a i ni n g   i n   i t s   p r e s e n t  p o s i t i o n   du r i n g   t h e   pa us e   i n t e r v a l .   I n   a dd i t i o n ,   a   m o de l   c e n t e r e d  o n   e s t a b l i s hi ng  m o bil e   c ha nn e l s   f o r   t h e   M S   to  r e duc e   e n e r g y   d i s s i pa t i o n   a n d  de l a y   wa s   pr o p o s e d  by   [ 32] .   T h e   a l go r i t hm   o pe r a t e s   i n   f o ur   s t a ge s :  s e l e c t i n g  a   m e e t i n g  p l a c e ,   c r e a t i n g  a   t r a j e c t o r y ,   ga t h e r i n g  da t a ,   a n d  s e n d i ng   da t a .   A   ge o g r a phi c   r o ut i n g  s t r a t e gy   b a s e d  o n   MS s   wa s   c r e a t e d   i n   [ 33] .   T hi s   i nv e s t i ga t i o n   ut i l i z e d  t w o  m o bi l e   s i n k s   to  a c qui r e   da t a   f r o m   s e n s o r s   l o c a t e d  i n   c e l l s   o r   ge o gr a phi c a l   a r e a s .   T h us ,   da t a   i s   ga t h e r e d  by   e a c h   c e ll ’ s   n o de s   a n d  t r a n s mi t t e d  to  t h e   M S .   I t   i s   i mpo r t a n t  to  r e m e m be r   t h a t   s e n s o r   n o de s   c a n   c o n n e c t   to  t h e   M S   vi a   s i n g l e - h o p  a n d  m u l t i - h o p  r o u t i n g.   F ur t h e r m o r e ,   a   m o bil i t y   m o de l   ba s e d  o n   bi p a r t i t e   gr a ph s   wa s   pr e s e n t e d  by   t h e   a ut h o r s   o f   [ 34] .   T h e   s ugge s t e d  m o de l   de t e r m i ne s   t h e   m o v e m e n t   pa t h   o f   t h e   M S   by   ut i l i z i ng  t h e   f e a t ur e s   o f   a   bi pa r t i t e   gr a ph .   I n  a dd i t i o n ,   t h e   pr o p o s e d  a ppr o a c h   i s   pr e d i c a t e d  on   b u il d i ng  a   bi pa r t i t e   gr a ph   f r o m   a   r a n do m ly   d is t r i b ut e d  n e t wo r k .   T h e   n e t wo r k ’ s   n o de s   wi ll   c o n s e qu e n t l y   b e   s p li t   i n t o  t w o   di s t i n c t   gr o ups .   T h e   M S   wi ll   t he n   pr o c e e d   to  vi s i t   t h e   f i r s t   gr o up ’ s   n o de s   i n   a   b r e a dt h - f i r s t   m a nn e r .   T h e   M S   wi l l   vi s i t   e a c h   n o de   i n   t h e   gr o u p  b e f o r e   m o vi ng  o n   to  t h e   n o de s   i n   t h e   s e c o n d  gr o up   s i mi l a r l y .   C o n s e que n t l y ,   a   v a r i e t y   o f   m o de l s   a r e   d i s c u s s e d  i n   t h e   r e s e a r c h   l i t e r a t ur e .   S o m e   us e   t h e   m o v a bl e   s i n k ’ s   c ur r e n t   l o c a t i o n   to   c h oo s e   a   n e w  s i t e ,   whil e   ot h e r s   r e l y   o n   r a n do m   m o bil i t y .   T h e   wo r k  pr e s e n t e d  i n   t hi s   s t udy   t a ke s   a n   a l t e r n a t i v e   a ppr o a c h   to  t a c kl i ng  t h e   M S   pa t h   pl a nni ng  pr o bl e m .   B y   b u il d i ng  a n   M S T   o f   t h e   n e t wo r k ,   t h e   s ugge s t e d  m e t h o d  s e e ks   to   l e v e r a ge   t h e   n e t wo r k   to p o l o g y   a n d  t h e   n o de   n e i g hb o r h o o d   to  ge n e r a t e   a   l o gi c a l   to p o l o g y .   S ub s e qu e n t l y ,   t h e   m o v a bl e   s i nk  w i ll   vi s i t   a l l   n o de s   i n   t h e   s e r i e s   o f   o r de r s   t h a t  t h e   M S T   i s   b u il t .     Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 5 0 2 - 4 7 52   In do n e s i a n   J   E l e c   E n g   &   C o m p  S c i ,  Vo l .   3 6 ,   N o .   3 ,  De c em b e r   20 24 :   1938 - 1949   1942   2. 3.     T h e   p r op os e d   m ob il it y  m od e ls   T h e   wo r k   pr e s e n t e d  i n   t hi s   s t ud y   i s   b a s e d  o n   r a n d o m ly   d i s pe r s e d  W S N s   c o n s i s t i n g  o f   o n e   M S   n o de   ( M )   a n d  s e ve r a l   f i xe d  s e n s o r   n o de s   ( N) .   A f t e r   th e   n e t wor k  i s   de p l o y e d,   t h e   M S   a n d  f i xe d  s e n s o r   n o de s ’   l o c a t i o ns   a r e   s e n t   to   t h e   B S .   A s   a   r e s u l t ,   t h e   B S   c o m put e s   t h e   M S T ,   t a ki n g  t h e   n e a r e s t   f i xe d  s e ns o r   n o de   to  t h e   M S   a s   t h e   r oot  o f   t h e   M S T .   A f t e r   t h a t,   t h e   B S   s e n ds   t h e   o r de r   a c c or di n g  t o  whi c h   t h e   M S T   i s   c o n s t r uc t e d   to   t h e   M S .   C o n s e que n t l y ,   t hi s   s e que n c e   w il l   s e r v e   a s   t h e   m o ve m e n t   pa t h   f o r   t h e   M S   wh e n   i t   vi s i t s   n o de s   a n d   ga t h e r s   da t a .   N ot e w o r t hy   i s   t h a t   t h e   p o r t a bl e   s i nk  i s   n o t  f a c t or e d  i n t o  t hi s   c o m put a t i o n   b e c a u s e   i t s   pur po s e   i s   to  s e e   f i xe d  s e n s o r   n o de s   a n d  c o l l e c t   da t a .   T o  c l a r i f y ,   f r o m   F i gur e   1  pa r t   ( A ) ,   a s s u m e   t h a t   t h e   c l o s e s t   n o de   to   t h e   M S   i s   n o de   4.   T h us ,   n o de   f o ur   w i ll   b e   c o n s i de r e d  a s   t h e   r o ot  o f   t h e   M S T .   Af t e r   t h a t ,   t h e   n e x t   n o de   to   b e   a dde d  to  t h e   M S T   i s   n o de   th r e e ,   a n d   s o   f o r t h .   A s   a   r e s u l t ,   us i n g  P r i m ’ s   a l go r i t hm   t o   c on s t r uc t   t h e   M S T   w i l l   r e s u l t   i n  a dd i ng  n o de s   to   t h e   M S T   in  t h e   f o l l o w i ng  o r de r :  4 ,   3,   1,   2 ,   7 ,   6,   5.   C o n s e que nt l y ,   t h e   s e que n c e   o r   o r de r   a c c or di n g  to  whi c h   n o de s   we r e   a dde d  to  t h e   M S T   i s   s e n t   to  t h e   M S   to  b e   a do p t e d   a s   t h e   m o v e m e n t   pa t h .   T h e r e f o r e ,   t h e   M S   wi ll   pr o c e e d  by   vi s i t i ng  n o de   4,   n o de   t h r e e ,   a n d  s o  o n   un t i l   t h e   l a s t   n o de   i n   t h e   s e que n c e ,   n o de   5,   i s   vi s i t e d.     I t  i s   c r uc i a l   t o  r e m e m be r   t h a t   whi l e   t h e   M S   vi s i t s   f i xe d  n o de s   i n   t h e   b u i l t   M S T ,   i t   wi ll   b e   i n   t h e   c o m m u ni c a t i o n   r a n ge   o f   o t h e r   f i x e d  n o de s   t h a t  i t   wi ll   vi s i t   l a t e r .   A s   a   r e s ul t ,   t h e s e   n e i g hb o r i n g  no de s   c a n   c o m m u ni c a t e   wi t h   t h e   M S   a n d  pr o vi de   da t a   to  i t .   A s   a   r e s u l t ,   i t   c a n   b e   gua r a n t e e d   t h a t  n o de s   w i ll   n o t  e x pe r i e n c e   b u f f e r   o v e r f l o w  a n d  t h a t   t h e   M S   wi ll   r e c e i v e   t h e   s e ns e d  da t a   qui c k ly .   A dd i t i o n a ll y ,   t h e r e   a r e   t w o  ph a s e s   to  t h e   m o bil e   s i nk ’ s   m o v e m e n t :  s o j o ur n   a n d  m o v e m e n t .   Dur i n g   t h e   s o j o ur n   pha s e ,   t h e   M S   s to ps   i n   i t s   pr e s e n t   l o c a t i o n   f o r   a   s pe c i f i e d  t i m e .   I t   wi ll   t h e n   s t a r t   tr a ve l i ng  a t   a   pr e de t e r m i ne d  s pe e d  to wa r d  a   n e w  s i t e .   T h e   s o j o ur n   pe r i o d  s t a r t s   o v e r   wh e n   t h e   M S   ge t s   to  t h e   n e x t   a r e a   a n d   c o n t i n ue s   t h e r e   f o r   t h e   s a m e   a m o u n t   o f   t i m e .   B e l o w  i s   a n   a l go r i t hm   t h a t   e x p l a i ns   t h e   m o bil i t y   m o de l  t h a t   t h i s   s t udy   pr o po s e s .   I n   ot h e r   wor ds ,   t h e   n e a r e s t   n o de   to   t h e   M S   i s   s e l e c t e d  to   b e   t h e   r oot  o f   t h e   M S T .   T h us ,   t h e   M S   s t a r t s   i t s   j o ur n e y   by   i ni t i a t i n g  t h e   s o j o ur n   pe r i o d  a n d  r e m a i ni ng  i n  i t s   c ur r e n t   p o s i t i o n   f o r   a   pr e de t e r m i ne d   a m o un t   o f   t i m e   to   v i s i t   t h e   r oot  o f   t h e   M S T ,   n o de   4  i n   o ur   pr e vi o us   e x a m p l e ,   a n d  c o l l e c t   i nf o r m a t i o n  f r o m   i t .   On c e   t h e   s o j o ur n   pe r i o d  e n ds ,   t h e   m o ve m e n t   i n t e r v a l   i s   i n i t i a t e d,   a n d  t h e   M S   wi ll   m o v e   a t   a   s pe c i f i c   s pe e d  to   vi s i t   t h e   n e x t   n o de   i n   t h e   s e que n c e   o f   t h e   M S T   c o n s t r uc t i o n s ,   n o de   3.   Af t e r   r e a c hi ng  i t s   n e w  l o c a t i o n ,   t h e   M S   i n i t i a t e s   t h e   s o j o ur n   i n t e r v a l   t o   ga t h e r   i nf o r m a t i o n .   T h e   s a m e   pr o c e s s   i s   r e pe a t e d  un t i l   e v e r y   n o de   i n   t h e   n e t wo r k   ge t s   vi s i t e d  a c c o r di n g  t o  t h e   s e que n c e   i n   whi c h   t h e   M S T   i s   c o n s t r uc t e d .   T o  e l a b o r a t e ,   a f t e r   c o n s t r uc t i n g  t h e   M S T ,   t h e   M S   w i l l   t r a v e r s e   i t   a c c o r di n g  t o   whi c h   i t   wa s   b u il t .   W h e n   vi s i t i n g  t h e   f i r s t   n o de ,   t h e   M S   e n t e r s   a   pa us e   or   s o j o ur n   pe r i o d  i n   o r de r   to   c o l l e c t   i nf o r m a t i o n   f r o m   t h e   n o de   b e i n g  vi s i t e d  vi a   s i n g l e - h o p  r o u t i n g.   Al s o ,   th e   M S   c a n   c o l l e c t   i nf o r m a t i o n   f r o m   t h e   n e i g hb o r s   o f   t h e   vi s i t e d  n o de   vi a   m u l t i - h o p  r o u t i n g.   A t   t h e   e x p i r y   o f   t h e   s o j o ur n   t i m e ,   t h e   M S   w i ll   s t a r t   m o vi ng,   a t   a   s pe c i f ic   s pe e d,   to wa r ds   t h e   n e x t   n o de   to  b e   vi s i t e d  a c c o r d i n g  to   t h e   M S T   c o n s t r uc t i o n   o r de r .   Up o n   a r r i v a l   a t   t h e   n e w   l o c a t i o n ,   t h e   m o v e m e n t   pe r i o d  e x p i r e s ,   a n d  t h e   s oj o ur n   pe r i o d  i s   i ni t i a t e d  a ga i n   to  c o l l e c t   i nf o r m a t i o n   i n   t h e   s a m e   m a nne r   m e n t i o n e d  b e f o r e .   T h us ,   i t   c a n   b e   c o n c l ude d  t h a t   t h e   m o v e m e n t   o f   t h e   M S   i s   s p li t   i n t o   s o j o ur n  i n t e r v a l s   whe r e   t h e   M S   m u s t   s t a y   i n   i t s   pr e s e n t   l o c a t i o n   f o r   a   s pe c i f i c   pe r i o d.   M e a n w hil e ,   i n   t h e   m o v e m e n t   i n t e r v a l s ,   t h e   M S   m o v e s   to  a   pr e de t e r m i ne d  l o c a t i o n   a t  a   pr e de t e r m i ne d  s pe e d.   T h e   m o bi li t y   m o d e l   to  b e   a do p t e d  by   t h e   M S   i s   i ll u s t r a t e d  i n   Al go r i t hm   1 .     Al go r i t hm   1 .   P r o p o s e d  m o bil i t y   m o de l   1.   Start   2.   Initialize a set of nodes: N = {n 0 , n 1 , n 2 , … n n - 1 }   3.   Initialize mobile sink: MS =   {n n }   4.   Initialize MST = {}   5.   From N, select the node closest to MS to be the root of MST.   6.   Add n to MST.    7.   While MST is not Empty   7.1.   Find all edges connecting the current node to any node in N.   7.2.   Select the edge with minimum weight.   7.3.   if the selected edge does not  form a cycle   7.3.1 Add the edge with minimum weight to MST, connecting the current node to the  new node n.    7.3.2.   Remove node n from N.   7.4.   End if    8.   End While   9.   Generate a mobility path to MS based on MST   Stop     I n   t h e   f o l l o w i ng  s u bs e c t i o n s ,   t h e   s c e n a r i o s   us e d   to   c o n duc t   t h e   s i m u l a t i o n   a n d  t h e   pe r f o r m a n c e   m e t r i c s   a do p t e d  to  a s s e s s   t h e   pe r f o r m a n c e   o f   t h e   pr o p o s e d  wo r k   a r e   p r e s e n t e d.     Evaluation Warning : The document was created with Spire.PDF for Python.
I n do n e s i a n   J   E l e c   E n g  &   C o m p  S c i     I S S N:   2 5 0 2 - 4 7 52       Util iz ing  minimum  s panning  tr e e s   f or   e ff e c ti v e   mo bil e   s ink  r outi ng  in  w ir e les s   s e ns o r   …  ( A nas   A bu  T aleb )   1943   2. 4 .    E x p e r im e n t s   2. 4. 1.   S c e n ar ios   T h e   s ugge s t e d  m o bil i t y   m o de l ’ s   e f f i c a c y   wa s   t h or o ughl y   e v a l u a t e d  t h r o ugh   a   s e r i e s   o f   s im u l a t i o ns   us i n g  t h e   NS - 2  s i m u l a t o r .   T hi s   d i s c r e t e   e v e n t   s i m u l a t i o n   too l   i s   s pe c i f i c a ll y   de s i g ne d  f o r   c o m muni c a t i o n  n e t wo r k   r e s e a r c h   a n d  s uppo r t s   a   di v e r s e   r a n ge   o f   bot h   wi r e l e s s   a n d  w i r e d  n e t wo r k   pr oto c o l s   [3 5] ,  [ 36 ] .   I n   t h e   s i m u l a t i o n ,   t h e   a d  h o c   o n - de m a n d  d i s t a n c e   v e c to r   ( A OD V)   r o u t i n g  pr oto c o l   wa s   e m p l o y e d  to  m a n a g e   m e s s a ge   de li ve r y   t o   t h e   a ppr o p r i a t e   r e c i p i e n t s .   F ix e d  s e n s o r   n o de s   we r e   c o nf i gur e d  t o   ge n e r a t e   tr a f f i c   a t   a   co n s t a n t   bi t   r a t e   ( C B R ) ,   a l l o w i ng  f o r   a   s t e a dy   f l o w  o f   da t a .   T h e   A OD V  pr oto c o l   wa s   c h o s e n   f o r   i t s   r e a c t i ve   n a t ur e ,   whi c h   l im i t s   t h e   a m o un t   o f   r o u t i n g  i nf o r m a t i o n   s to r e d  i n   t h e   r o u t i n g  t a bl e   a n d  t h e r e by  r e duc e s   m e m o r y   us a g e   a n d  pr o c e s s i n g  t i m e .   T h e   pr oto c o l   o nl y   a c qu i r e s   r o u t i n g  i nf o r m a t i o n   o n - de m a n d,   e nh a n c i ng   e f f i c i e nc y   [ 17] .   T o   a s s e s s   t h e   pr o p o s e d  m o de l   u n de r   c o n d i t i o n s   o f   h e a vy   t r a f f i c ,   t h e   C B R   wa s   ut i li z e d  t o   s i m u l a t e   c o n t i n uo us   da t a   f l o w  f r o m   s t a t i c   s e ns o r   n o de s .   T h e   s im u l a t i o n   c o v e r e d  n e t wo r ks   wi t h   26,   51 ,   76,   a n d  101  r a n do m ly   d i s t r i b ut e d  n o de s   w i t hi n   a   1000  ×   1000  gr i d.   I n   e a c h   ne t wor k,   t h e r e   we r e   N  s t a t i c   s e n s o r   n o de s ,   n u m be r e d  s e que n t i a ll y   f r o m   0  to   n − 2,   wi t h   o n e   a dd i t i o n a l   n o de ,   n u m b e r e d  n − 1,   s e r vi ng  a s   t h e   m o bil i t y   s i nk.   F o r   e x a m p l e ,   i n   t h e   ne t wor k  wi t h   26  n o de s ,   t h e   s tat i on a ry   s e n s o r   n o de s   we r e   n u m be r e d  f r o m   0  to   2 4,   whi l e   n o de   25  a c t e d  a s   a n   e n e r g y - r i c h   m o bil i t y   s i nk  t h a t   m o v e d  a m o n g  t h e   s t a t i c   n o de s .   T h e   pr o p o s e d  m o de l   wa s   t e s t e d  a c r o s s   di f f e r e n t   m o bil i t y   s i nk  s pe e d s - s pe c if i c a ll y   5,   10,   15,   a n d  20  m /s - t o  e v a l ua t e   i t s   pe r f o r m a nc e   i n   v a r i o us   s c e n a r i o s .   T hi s   t e s t i n g  a im e d  to  de t e r m i ne   h o w  c h a n ge s   i n   t h e   m o bil i t y   s i nk ’ s   s pe e d  a f f e c t e d  t h e   o v e r a l l   e f f i c i e n c y   a n d  e f f e c t i v e ne s s   o f   t h e   pr o p o s e d  m o de l   i n   m a n a g i ng   n e t wo r k  tr a f f i c   a n d  m a i n t a i ni ng  c o nne c t i vi t y .   T h r o ugh   t h e s e   s im u l a t i o ns ,   i n s i g h t s   we r e   ga i n e d  i n t o   t h e   m o de l ’ s   a bil i t y   t o  h a n d l e   d y na mi c   n e t wo r k   c o n d i t i o n s   a n d  i t s   pot e n t i a l   b e n e f i t s   i n   r e a l - wo r l d  a pp li c a t i o n s .   F o r   e x a m p l e ,   a f t e r   r a n do m ly   de p l o yi ng  t h e   26 - n o d e   n e t wor k,   t h e   m o bil i t y   m o de l ’ s   pe r f o r m a n c e   w i ll   b e   s t ud i e d  w hi l e   t h e   M S   m o v e s   a c c o r di n g  to   5   m /s   s pe e d.   Af t e r   t h a t ,   t h e   s pe e d  a c c o r di n g  to   whi c h  t h e   M S   m o v e s   w i ll   b e   i nc r e a s e d  t o  10  m /s   f o r   t h e   s a m e   n e t wo r k   s i z e   a n d  s o   o n   f o r   15   a n d  20  m /s   s p e e d s .   Af t e r   s t udy i ng  t h e   pe r f o r m a n c e   o f   t h e   26  n o de s   n e t w o r k  un de r   a l l   t h e   pr e vi o us ly   m e n t i o n e d  s pe e ds ,   t h e   n e t wo r k   s i z e   i s   c ha n ge d  to  51   n o de s   n e t w o r k   t h a t  wi ll   b e   r a n do m ly   de p l o y e d,   a n d  t h e   pe r f o r m a n c e   o f   t h e   pr o p o s e d   m o de l   i s   s t ud i e d  by   v a r yi ng  t h e   M S   s pe e d  i n   t h e   s a m e   a ppr o a c h   a do p t e d   f o r   t h e   pr e vi o us   n e t wor k  s i z e .   I t  i s   im po r t a n t   to  n ot e   t h a t   e a c h   c a s e   wa s   r un   t e n   t i m e s ,   a n d  t h e   r e s u l t s   o b t a i n e d  f r o m   a l l   t h e   t r i a l s   we r e   a v e r a ge d   to  ge t   m o r e   a c c ur a t e   r e s ul t s .   T h e   pa r a m e t e r s   w i t h   whi c h   t h e   s im u l a t i o n   wa s   c o n duc t e d  a r e   s h o wn   i n   T a bl e   1.       T a bl e   1.   P a r a m e t e r s   f o r   s i m u l a t i o n   P a r a me t e r  na m e   U s e d v a lu e   P e r i o d  of   s im ul a ti o n   500 s e c o nds   N e tw o r k  s iz e   26, 51, 76, 101   S in k  s to p t im e   5 S e c o nds   D e pl oy m e nt   a r e a  s iz e   1000* 1000   G e ne r a te d  t r a f f i c  t y p e   C B R   M ov e m e nt   s p e e d   5, 10, 15, 20 m/ s   S iz e   of   p a c ke t  ( b y t e s )   512       2. 4. 2.   E x p e r im e n t   m e t r ics   T h e   a ve r a ge   o n e - wa y   de l a y ,   pa c ke t   de l i ve r y   r a t i o ,   a n d  t h r o ugh put   m e t r i c s   a r e   us e d  to   e x a m i ne   t h e   n e t wo r k ’ s   pe r f o r m a n c e   un d e r   t h e   s ugge s t e d  m o bi li t y   pa r a d i g m .   T h e   a v e r a g e   o n e - wa y   de l a y   i s   t h e   a m o u n t   o f   t i m e   a   pa c ke t   t a ke s   to  g o   f r o m   o n e   p l a c e   t o  a n o t h e r .   T h e   a v e r a ge   o n e - wa y   de l a y   f o r   t h e   n e two r k   i s   de t e r m i ne d  by   t a k i n g  t h e   a ve r a ge   t i m e   r e qu i r e d  t o  s e n d  e a c h   pa c ke t   b e t we e n   e a c h   s o ur c e   a n d  e a c h   de s t i n a t i o n  i ns i de   t h e   n e t wor k  [ 37 ] - [ 39] .  In   ( 1)   i s   us e d  to  de t e r mi ne   t h e   a v e r a ge   o n e - wa y   de l a y :     =   ∑ ( − )   = 1   ( 1)     i n  ( 1) ,   H i r   a n d  H i t   r e pr e s e n t   t h e   r e c e i v e d  t r a n s mi t t e d  c o py   o f   a   pa c ke t ,   r e s pe c t i v e ly ,   a n d  N  i s   t h e   t ot a l   n u m be r   o f   de l i ve r e d  pa c ke t s .   T h e   pa c ke t   de l i ve r y   r a t e   i s   de t e r m i ne d  by   d i v i d i ng  t h e   tot a l   n u m be r   o f   pa c ke t s   t r a n s m i t t e d  by   t he   r a t i o   o f   s uc c e s s f u ll y   r e c e i ve d  pa c k e t s ,   a s   s t a t e d  i n   ( 2)   [ 37 ] - [ 40 ] :           =    ∑ = 1       ( 2)     P rs   i s   t h e   tot a l   n u m be r   o f   s uc c e s s f u l ly   r e c e i ve d  pa c ke t s ,   a n d  p s e n t   i s   t h e   o v e r a l l   n u m be r   o f   s e n t   pa c ke t s .   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 5 0 2 - 4 7 52   In do n e s i a n   J   E l e c   E n g   &   C o m p  S c i ,  Vo l .   3 6 ,   N o .   3 ,  De c em b e r   20 24 :   1938 - 1949   1944   T h e   t hi r d  m e a s ur e   o f   pe r f o r m a n c e   c o n s i de r e d  i s   t h r o ugh put,   whi c h   i s   de f i ne d  a s   t h e   tot a l   n u m be r   o f   pa c ke t s   t h a t   we r e   c o r r e c t l y   r e c e i ve d  dur i n g  a   g i ve n   pe r i o d.   C o n s e que n t l y ,   t h r o ugh put   i s   c a l c u l a t e d  i n   o ur   s i m u l a t i o n   us i ng  ( 3) ,   whi c h   s t a t e s   t h a t   t h r o ugh put  i s   c o m put e d  by   d i v i d i ng  t h e   tot a l   n u m be r   o f   pa c ke t s   s uc c e s s f u l ly   r e c e i ve d  by   t h e   w h o l e   s im u l a t i o n   dur a t i o n   [ 37 ] - [ 40] .     ℎ  ℎ  =          ∗    ∗ 8         ( 3)       3.   RE S UL T S   AN D  DI S CU S S I ON   T h e   r e s u l t s   o b t a i n e d  f r o m   us i ng  t h e   s i m u l a t e d  s c e n a r i o s   a r e   d i s p l a y e d  a n d  d i s c us s e d  i n  t hi s   s e c t i o n .   T e n   tr i a l s   f o r   e v e r y   s c e na r i o   we r e   c o n duc t e d   to  o b t a i n   m o r e   t h o r o ugh   r e s u l t s .   F or   e a c h   c a s e ,   t h e   r e s u l t s   o f   t h e   t e n   r un s   we r e   a v e r a ge d  t o  ge t   t h e   s i m u l a t i o n   r e s u l t s .   T h e   a v e r a ge   o n e - wa y   de l a y   f i nd i ngs   f o r   d i f f e r e n t   n e t wo r k  s i z e s   a n d  M S   m o v e m e n t   s pe e ds   a r e   s h o w n   i n   F i gur e   2.   T h e   b e s t   o v e r a l l   o n e - wa y   de l a y   r e s u l t s   we r e   o b t a i n e d  by   n e t wo r ks   wi t h   51  a n d  76  n o de s ,   pa r t i c u l a r l y   w he n   t h e   M S   s pe e d  wa s   t e n   m /s .   T hi s   k i n d  o f   b e h a vi o r   c a n   b e   a t t r i b ut e d  to   t h e   f a c t   t h a t   th e   M S   is   o pe r a t i n g  a t   a   pa c e   t h a t   i s   de e m e d  m o de r a t e ,   m e r g i n g  t h e   ut i li z a t i o n   o f   s i ng l e - h o p  a n d  m u l t i - h o p  tr a n s mi s s i o n  to  a c hi e v e   l o w  o n e - wa y   de l a y   va l ue s .   M o r e o v e r ,   F i gur e   2  de m o n s t r a t e s   t h a t  n e t w o r ks   w i t h   26  a n d  101  n o de s   h a d  t h e   wo r s t  pe r f o r m a n c e   c o m pa r e d  t o   a l l   ot h e r   n e t wo r ks .   T hi s   c a n   b e   e x p l a i ne d  by   t h e   f a c t   t h a t   m u l t i - h o p  r o u t i n g  i s   o f t e n   us e d  to   ge t  pa c k e t s   to  t h e i r   de s t i na t i o n .   S t a t e d  di f f e r e n t l y ,   t h e   M S   h a s   a   r e l a t i v e ly   s h o r t   r o a d  to  a d o p t i o n .   C o n s e que n t l y ,   m o s t   o f   t h e   i mm o bil e   s e ns o r   n o de s ’   r o u t i n g  pa t h s   w i ll   b e   im pa c t e d  by   t h e   M S ’ s   m o t i o n .   A s   a   r e s u l t ,   pa c ke t s   de l i ve r e d  f r o m   f i xe d  s e n s o r   n o de s   wi l l   m a ke   s e v e r a l   h o ps ,   s o m e   o f   whi c h   a r e   c a us e d  by   r o u ti ng  pa t h   a l t e r a t i o n s   o r   m o d i f i c a t i o n s .   A s   a   r e s u l t ,   i t ’ s   po s s i bl e   t h a t  t h o s e   pa c ke t s   we r e   r o u t e d   m u l t i p l e   t i m e s   f r o m   t h e   s a m e   n o de   to  a c c o m m o da t e   r o u t i n g  pa t h   m o d i f i c a t i o n s   be f o r e   r e a c hi n g  t h e   M S .   On   t h e   ot h e r   h a n d,   f o r   a   101 - n o de   n e t wo r k ,   t h e   pa t h   to  b e   f o l l o we d  by   t h e   M S   i s   l o n g,   a n d  t h e   r o ut i n g  pa t h s   a do pt e d  to  c o n v e y   m e s s a ge s   to   t h e   M S   us i n g  m u l t i - h o p  r o u t i n g  a r e   l o n g,   too .   As   a   r e s u l t ,   m e s s a ge s   w i ll   s u f f e r   f r o m   a   hi g h   o n e - w a y   de l a y  i n   ge t t i n g  to  t h e   M S .   Al s o ,   c h a n ge s   i n   t h e   r o u t i ng  pa t h s   t h a t  r e s ul t   f r o m   M S   r e l o c a t i o n   c a us e   e v e n   l o n ge r   r o u t i n g  pa t h s   t o  b e   c o n s t r uc t e d  a n d  f o l l o we d  t o  de l i ve r   m e s s a g e s .   B e c a us e   n o t  e v e r y   n o de   i n   t h e   n e t wo r k   wa s   i m p a c t e d   by   t h e   r o u t i n g  pa t h   a d j us t m e n t s ,   b e tt e r   r e s u l t s   we r e   o b t a i n e d  f o r   ot h e r   n e t wor ks .   A s   a   r e s ul t ,   pa c ke t s   di d  n ot  h a v e   to  tr a v e l   o v e r   t h e   n e t wor k   o r   pa s s   t h r o ugh   a ny   dup li c a t e d  i n t e r m e d i a t e   n o de s .   A s   a   r e s u l t ,   f e we r   h o ps   we r e   r e qu i r e d  f o r   pa c ke t s   to   r e a c h   th e   M S .   S m a ll e r   o n e - wa y   de l a y   r e s u l t s   we r e   t h e r e f o r e   a tt a i n e d.   F i gur e   3  d i s p l a y s   t h e   pa c k e t   de l i ve r y   r a t i o   o b s e r va t i o n s   o b t a i n e d.   I t   i s   c l e a r   f r o m   t hi s   da t a   t h a t  t h e   s ugge s t e d  m o bil i t y   m o de l   a c hi e ve d  u n s we r vi ng  p e r f o r m a n c e   a c r o s s   v a r i o us   n e t wo r k  s i z e s .   C o n s i s t e n t   w i t h  t h e   f i nd i ngs   f r o m   F i gur e   2,   t h e   n e t wor ks   o f   5 1  a nd  76  n o de s   de m o n s t r a t e d   t h e   b e s t   pe r f o r m a n c e   i n   t e r m s   o f   pa c ke t   de l i ve r y   r a t i o   a c r o s s   a l l   M S   s pe e ds .           F i gur e   2.   A v e r a ge   o n e - wa y   de l a y       F i gur e   3.   P a c ke t   de l i ve r y   r a t i o       Evaluation Warning : The document was created with Spire.PDF for Python.
I n do n e s i a n   J   E l e c   E n g  &   C o m p  S c i     I S S N:   2 5 0 2 - 4 7 52       Util iz ing  minimum  s panning  tr e e s   f or   e ff e c ti v e   mo bil e   s ink  r outi ng  in  w ir e les s   s e ns o r   …  ( A nas   A bu  T aleb )   1945   T o  f ur t h e r   e x p l a i n,   t hi s   n e t wo r k   wi ll   a c hi e v e   t h e   b e s t   r e s ul t s   f o r   t h e   pa c ke t  de l i ve r y   r a t i o   s i nc e   i t   o b t a i n e d  t h e   be s t   r e s u l t s   f o r   o n e - wa y   de l a y   f o r   t h e   s a m e   r e a s o n   s t a t e d  wh e n   pr e s e n t i n g  t h e   r e s u l t s   o f   F i gur e   2.   F ur t h e r m o r e ,   F i gur e   3  s h o ws   h o w  t h e   M S ’ s   v e l o c i t y   i nc r e a s e d  t o   20   m /s ,   w hi c h   i m pa c t e d  a n d  s o m e w h a t   de c r e a s e d  t h e   pe r f o r m a n c e   o f   a l l   ne t wor ks .   A c c o r di n g l y ,   r a p i d  a n d  f r e que n t   m o d i f i c a t i o n s   to  t h e   r o u t i n g   pa t h wa y s   w il l   o c c ur   f o r   s m a ll   n e t wo r ks   wh e n  t h e   M S   t r a v e l s   a t   hi g h   s p e e ds ,   r e s u l t i ng  i n   a   dr o p   in  pe r f o r m a n c e .   Al s o ,   i t   w o n ’ t   b e   e a s y   to  c o m p l e t e   da t a   t r a n s f e r   b e t we e n   t h e   M S   a n d  t h e   f i xe d  s e n s o r   n o de s   s i nc e   t h e   M S   w i l l   a l s o   b e   t r a v e l i ng  qu i c k ly .   Ho we v e r ,   c o m pa r e d  to   m e d i u m -   a n d  l a r ge - s i z e d  ne t w o r ks ,   t h e   e x pe c t e d  m o bil i t y   p a t h   o f   t h e   M S   i s   s h o r t e r   f o r   s m a l l e r   n e t wor k  s i z e s .   T hi s   m e a ns   th a t   t h e   s t a t i c   s e n s o r   n o de s   a n d  t h e i r   n e i g hb o r s   wi ll   b e   im pa c t e d  i f   t h e   M S ’ s   s pe e d  i s   i n c r e a s e d  t o  20  m /s .   A s   a   r e s u l t ,   pa c ke t s   m us t   b e   r o u t e d  vi a   m u l t i - h o p  r o u t i n g   to   r e a c h   t h e i r   d e s t i n a t i o n   b e c a u s e   t h e s e   n o de s   w i ll   n ot   h a ve   e n o ugh   t i m e   t o   s e n d  t h e m   t o   t h e   M S .     T o  a c c o m m o da t e   t h e   f r e que n t   m o d i f i c a t i o n s   i n   t he   r o u t i n g  pa t h ,   pa c ke t s   wi l l   a l s o   m a ke   e x t r a   a n d  n e e d l e s s   h o ps   be f o r e   r e a c hi ng  t h e   M S .   T h e   n e t wo r k  t h r o ug h put   r e s u l t s   a r e   d i s p l a y e d  i n  F i gur e   4  f o r   d i f f e r e n t   n e t wo r k   s i z e s   a n d  s pe e d s   wh e n   t h e   M S   t r a v e l e d  by   t h e   r e c o mm e n de d  m o bi li t y   m o d e l .   B e c a us e   t h e   l e n gt h   o f   t h e   r o u t i n g  pa t h   i s   c o n s i s t e n t   w i t h   t h e   s pe e ds   a t   whi c h   t h e   M S   i s   m o vi n g,   F i gur e   4  s h o ws   t h a t  t h e   s ugge s t e d  m o bil i t y   a c hi e ve d  hi g h   a n d  s t a bl e   pe r f o r m a n c e   f o r   t h e   n e t w o r k   c om pr i s i ng   51  n o de s   un d e r   a l l   o f   t h e   m o v a bl e   s i nk ’ s   s pe e d s .   C o n s e que n t l y ,   de c r e a s i n g  t h e   f r e que n c y   o f   upda t e s   a n d   pot e n t i a l   m o d i f i c a t i o ns   to   t h e   r o u t i n g  pa t h w a y s .   F i xe d  s e ns o r   n o de s   w i l l   a l s o   ha v e   e n o ugh   t i m e   t o  tr a n s mi t   da t a   a n d  c o n n e c t   w i t h   t h e   M S   pr o pe r l y .   Due   t o   t h e   f a i r   l e n gt h   o f   t h e   r o u t i n g   pa t h s ,   t h e   pa c ke t   di d  n o t  h a v e   t o   pa s s   t h r o ugh   m a ny   h o ps   to   b e   de l i ve r e d,   m a k i ng  t h e   51 - n o de   n e t wor k  t h e   m o s t   pe r f o r m a n t   a n d  s t a bl e   i n  a ll   s c e n a r i o s .   B e c a u s e   t h e   M S   us e d  a   s o m e w h a t   l o n g   m o v e m e n t   pa t h ,   f i xe d  s e ns o r   n o de s   we r e   n o t   r e qu i r e d  to  upda t e   t h e i r   r o u t i n g  t a bl e s   r e gu l a r l y ,   l e a d i ng  to   s upe r i o r   pe r f o r m a n c e   o ut c o m e s .   O n   t h e   o t h e r   h a n d,   f o r   s m a ll - s i z e   ne t wor ks ,   c h a n g e s   i n   t h e   r o ut i n g  pa t h   r e s u l t i n g  f r o m   r e l o c a t i n g  t h e   M S   c a u s e   f r e que n t   upda t e s   th a t   m a y   r e s u l t   i n   m e s s a ge s   c i r c u l a t i n g  t h r o ugh   t h e   n e t w o r k  by   pa s s i ng  t h r o ugh   m a ny   u nn e c e s s a r y   h o ps .   A s   a   r e s u l t ,   t h e   n e t w o r k   ge t s   c o n ge s t e d   e a s i ly ,   whi c h   a f f e c t s   th e   n e t wo r k   pe r f o r m a n c e   i n   t e r m s   o f   t h r o ugh put.   M o r e o v e r ,   t h e   r o u t i n g  pa t h s   a r e   l o n g  f o r   l a r ge   n e t wo r k   s i z e s ,   a n d  m e s s a ge s   s u f f e r   f r o m   hi g h   o n e - wa y   de l a ys   due   to  m u l t i - h o p   r o u t i n g.   T hi s   s i t ua t i o n   i s   m a de   e v e n   wo r s e   wh e n   r e l o c a t i n g  t h e   M S .   C o n s e que n t l y ,   m o s t   t r a f f i c   w il l   b e   r e d i r e c t e d  a n d  c o n c e n t r a t e d  o n   a   s pe c i f i c   p a t h   i n  t h e   n e t wo r k ,   c a us i n g  b ott l e ne c ks   a n d  c o n g e s t i o n .   T h us ,   pa c ke t s   ge t  dr o ppe d ,   a n d  n e t wor k  pe r f o r m a n c e   i s   a f f e c t e d.           F i gur e   4.   Ne t w o r k   t h r o ugh put       I n   c o n c l us i o n ,   i t   c a n   b e   o bs e r v e d  t h a t   t h e   e f f e c t i v e n e s s   o f   v a r i o us   n e t wor k  s i z e s   r e m a i ne d  n e a r l y  c o n s t a n t   f o r   a l l   o t h e r   s c e n a r i o s   o f   M S   s pe e ds ,   b ut   i t  wa s   n ot   a s   g oo d   a s   t h e   n e t wor ks   wi t h   51  n o de s .   E i t he r   o f   t w o   r e a s o n s   a pp l i e d  to   t hi s .   F i r s t ,   t h e   s pe e d  o f   t h e   M S   m i g h t   n ot   b e   a ppr o p r i a t e   f o r   t h e   s i z e   o f   t h e   n e t wo r k .   T o  pu t   i t   a n ot h e r   wa y ,   b e c a u s e   o f   pa c ke t   l o s s   a nd  n e t wor k  c o n ge s t i o n ,   l o w  a n d  hi g h   s pe e d s   m i g ht  n ot   b e   s u i t a bl e   f o r   l a r ge r   or   s m a ll e r   n e t wo r ks ,   r e s pe c t i v e ly .   S e c o n d,   t h e   r o u t i n g  pa t h s   m i g h t   b e   e x t r e m e ly   l o n g  f o r   l a r ge   n e t wo r k  r o u t i n g  a t   l o w  s pe e ds .   T hi s   c o u l d  l e a d  to  c o n ge s t i o n   i n   s o m e   a r e a s   o f   t h e   n e t wo r k   a n d  pa c ke t   dr o ppi n g.   C o n v e r s e l y ,   i n   s m a ll   n e t wo r ks   wi t h   hi g h  M S   s pe e ds ,   pa c ke t   l o s s   m a y   o c c ur   f r o m   f r e que n t   to p o l o g y   a n d  r o ut i n g  pa t h   c h a n ge s .   Upda t i n g  t h e   pa t h s   r e qu i r e s   a   s i g ni f i c a n t   a m o un t   o f   b a n dw i dt h ,   de gr a d i n g  n e t wo r k   pe r f o r m a n c e   a n d  r a i s i ng  t h e   n u m be r   o f   dr o ppe d  pa c ke t s .   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 5 0 2 - 4 7 52   In do n e s i a n   J   E l e c   E n g   &   C o m p  S c i ,  Vo l .   3 6 ,   N o .   3 ,  De c em b e r   20 24 :   1938 - 1949   1946   F ur t h e r m o r e ,   m a ny   pa c k e t s   c o ul d  m a ke   e x t r a   h o p s   to  b e   de l i ve r e d ;   a s   a   r e s u l t ,   t h e   pa c ke t ’ s   c o un t e r   o r   t i m e   t o   l i ve   t i m e r   m a y   e x p i r e ,   c a u s i ng  t h e   pa c ke t s   to   b e   d i s c a r de d.   A dd i t i o n a ll y ,   i t   c a n   b e   o b s e r v e d  t h a t   m e d i u m - s i z e   ne t wor ks ,   51   n o de s ,   a c hi e v e   a c c e pt a bl e   r e s u l t s   i n   a l l   c a s e s   un de r   d i f f e r e n t   pa r a m e t e r s .   I n   ot h e r   wo r ds ,   t h e   n e t wor k  t h a t   h a s   a c hi e v e d  go o d  pe r f o r m a n c e   r e s u l t s   i n   t e r m s   o f   o n e - wa y   de l a y   m a na ge d  to  a c hi e ve   hi g h   p e r f o r m a n c e   i n  t e r m s   o f   P DR   a n d  t h r o ugh put   b e c a us e   t h e   o n e - wa y   de l a y   d i r e c t l y   im pa c t s   t h e   ot h e r   t w o   pa r a m e t e r s ,   e s pe c i a ll y   w h e n   t a ki n g  s i nk  m o bil i t y   i n t o   a c c o un t.     Us i n g  t h e   s a m e   pe r f o r m a n c e   m e a s ur e s ,   t h e   s ugge s t e d   m o de l ’ s   pe r f o r m a n c e   wa s   a l s o   c o n t r a s t e d  wi t h   t h a t  o f   t h r e e   ot h e r   m o bil i t y   m o de l s ,   n a m e ly ,   t h e   De pt h   F i r s t - b a s e d  m o bil i t y   m o de l   ( D F ) ,   t h e   Ga us s   M a r ko v   m o bil i t y   m o de l   ( GM ) ,   a n d  t h e   r a n do m   wa y po i n t   m o bi li t y   m o de l   ( R W ) .   All   m o de l s   we r e   r un   t h r o ugh   t h e   s i m u l a t i o n   s c e n a r i o s   o ut l i ne d  i n   s u bs e c t i o n   2. 2 . 1  to  ga t h e r   da t a   a n d  c o m pa r e   t h e   m o de l s   i n  t h e   s a m e   c o n d i t i o n s .   T h e   f o ur   m o de l s ’   pe r f o r m a n c e s   a r e   c o n t r a s t e d  i n   T a bl e s   2 - 4.   I t   i s   wo r t h   b r i e f ly   de s c r ibi ng  t h e   m o bil i t y   m o de l s   a do pt e d  f o r   pe r f o r m a nc e   c o m pa r i s o n   w i t h   t h e   m o bil i t y   m o de l   pr o po s e d  i n   t hi s   pa pe r .   T h us ,   s ubs e c t i o ns   3 .1 – 3 . 3   di s c us s   t h e   m o bil i t y   m o de l s   ut i li z e d  i n   t h e   c o m pa r i s o n .   I t  i s   wo r t h   n ot i n g  t ha t  t h e s e   m o de l s   we r e   s e l e c t e d  f o r   c o m pa r i s o n   b e c a u s e   t h e y  h a v e   a   s i mi l a r   b e h a vi o r   f o r   t h e   M S   a s   t h e   pr o p o s e d  m o de l ,   wh e r e   t h e   m o v e m e n t   o f   t h e   M S   i s   d i v i de d  i n t o   m o v e m e n t   pe r i o ds   a n d  s o j o ur n   pe r i o ds .   T h e y   d if f e r   i n  t h e   wa y   o r   m e c ha ni s m   a c c o r di n g  t o  whi c h   t h e   n e w  l o c a t i o n  f o r   t h e   M S   i s   s e l e c t e d  o r   c a l c u l a t e d .     3. 1.     RW  m od e l   T h e   m o v a bl e   s i nk ’ s   m o t i o n   i n   t h i s   m o de l   i s   s p l i t   i n t o  r o un ds   o f   pa us e   a n d  m o v e m e n t .   T h e   M S   wi ll   f i r s t   pa us e   f o r   a   p r e de t e r m i ne d  a m o un t   o f   t i m e .   T h e   m o v e m e n t   r o un d  b e g i ns   wh e n   t h e   pa us e   r o un d  e n d s   a n d   t h e   m o v a bl e   s i nk  w il l   r a n do m ly   c h o o s e   a n ot h e r   l o c a t i o n .   I t   wi l l   s t a r t   tr a v e li ng  t h e r e   a t   a   p r e de t e r m i n e d  s pe e d.   A   n e w  pa us e   r o un d  b e g i ns   w h e n   t h e   M S   r e a c h e s   it s   de s t i n a t i o n ,   r e m a i ns   t h e r e   f o r   a   pr e de t e r m i ne d  t i m e ,   a n d   s o   o n   [ 37 ] ,  [ 41] .   Gi v e n   t hi s   m o d e l ’ s   b e h a vi o r   i s   c o m pa r a bl e   t o   t h e   m o de l   s ugge s t e d  i n   t hi s   wo r k,   i t   wa s   s e l e c t e d  f o r   c o m pa r i s o n .   S t a t e d  di f f e r e n t l y ,   t h e   M S ’ s   m o ve m e n t   i n   b o t h   m o de l s   i s   s p li t   be t we e n   mo v e m e n t   a n d  pa us e   i n t e r v a l s .     3. 2.     G M   m od e l   T hi s   m o de l   wa s   pr o p o s e d  to   c o n s i de r   va r i o us   a m o un t s   o f   un pr e d i c t a bil i t y   a n d  m a ke   t h e   m o de l   m o r e   r e a l i s t i c .   A   m o v a bl e   n o de   i n   t hi s   f r a m e wo r k  c a n   a d j us t   i t s   d i r e c t i o n   a n d  s pe e d  a s   ne e de d.   T h e   m o bi le  n o de   i s   i n i t i a ll y   g i ve n   t h e   di r e c t i o n   a n d  s pe e d  o f   m ot i o n   a n d  m o v e s   f o r   a   c e r t a i n   a m o un t   o f   t i m e   by   t h e s e   pa r a m e t e r s .   Af t e r wa r d,   a   n e w  c o ur s e   a n d  v e l o c i t y   a r e   de t e r m in e d   us i ng  t h e   v a l ue s   f r o m   t h e   pr e vi o us   i t e r a t i o n   wh e n   t h e   t i m e r   e n d s   [ 17 ] ,  [ 33 ] ,  [ 35 ] .   S i n c e   t hi s   m o de l   s t a r t s   w i t h   de s i g n a t e d  s pe e d  a n d  d i r e c t i o n   va l ue s ,   i t   wa s   i nc l ude d   i n   t he   c o m pa r i s o n .   S t a r t i n g  w i t h   a   s i ng l e   s u bs e t ,   t h e   n e w  l o c a t i o n s   a r e   c h o s e n   by   c o n s i de r i ng  b o t h   t h e   c l o s e s t  a n d  pr e s e n t   n e i g hb o r s .     3. 3.     DF   m od e l   I n   s uc h   a   c a s e ,   a   gr a ph ’ s  de pt h   f i r s t   t r a v e r s a l   a l go r i t hm   w il l   de t e r m i ne   h o w  t h e   M S   m o v e s   t h r o ugh   t h e   n e t wo r k .   C o n s e que n t l y ,   t h e   m o ve m e n t   o f   t h e   M S   i s   d i v i de d   as   h a l t   a n d  m o t i o n   pha s e s ,   w i t h   t h e   s t a r t i n g   n o de   c h o s e n   a t   r a n do m .   Af t e r   s e l e c t i n g  t h e   b e g i nni ng  po i n t ,   t h e   M S   wi ll   t r a v e l   a t   a   pr e de t e r m i ne d  s pe e d  to  t h e   n e w  p l a c e .   I t  wi ll   r e m a i n   t h e r e   f o r   a   pr e de t e r m i ne d  t i m e   whe n   i t   ge t s   to  t h e   n e w  p l a c e .   S ub s e que n t l y ,   t h e   M S   m o v e s   t o wa r d   t h e   n e x t   l o c a t i o n ,   whi c h   i s   de t e r m i ne d  us i ng  t h e   de pt h - f i r s t   t r a v e r s a l   a l go r i t h m   [ 42] .    DF   m o de l   wa s   c h o s e n   b e c a us e   i t   b e ha v e s   s im il a r ly   t o   t h e   m o de l   s ugge s t e d  i n   t hi s   wo r k:   t h e   M S   m o v e s   i n   r o un ds ,   a n d  i t s   n e w  l o c a t i o n   i s   de t e r m i ne d  us i ng  a   pr e de t e r m i ne d  pr o c e dur e .   I t  a l s o   us e s   t h e   n o de s   ‘   l o c a t i o ns   a l o n g  w i t h   t h e   pr o pe r t i e s   o n   t h e   to p o l o g y   o r   g r a ph .     3. 4.     P e r f o r m an c e   c om p a r is on   r e s u l t s   Af t e r   s im u l a t i n g  t h e   f o ur   m o bil i t y   m o de l s ,   i t   c a n   b e   o bs e r ve d  t h a t   t h e   s ugge s t e d  m o bil i t y   m o de l   i n  t hi s   r e s e a r c h   pe r f o r m e d  b e t t e r   t h a n   a ll   t h r e e   m o bil i t y   m o de l s   u n de r   v a r i o us   MS   ve l o c i t i e s   a n d  n e t wor k  s i z e s ,   a c c o r di n g  t o  T a bl e s   2 - 4.   T a bl e s   2 - 4  s h o w  t h e   r e s u l t s   o b t a i ne d  f o r   o n e - wa y   de l a y .   T h e   a c qu i r e d  r e s u l t s   a r e   c o n s i s t e n t   wi t h   t h e   f i nd i n g s   o b t a i n e d  i n  F i gur e   2,   w h e r e   n e t wor ks   m a de   up  o f   51  a n d  76  n o de s   f o r   t h e   pr o p o s e d  m o de l   i n  t hi s   wo r k   r e c e i v e d  t h e   b e s t   r e s ul t s   wh e n   t h e   M S   s pe e d  wa s   e qua l   to  10  m /s .   Al s o ,   t h e   s ugge s t e d   m o de l ’ s   o v e r a ll   pe r f o r m a n c e   w i t h   v a r i o us   n e t wo r k  s i z e s   a n d  M S   s pe e ds   wa s   b e t t e r   t h a n   t h e   ot h e r   t h r e e   m o de l s   be c a us e   t h e   M S   m o v e m e n t   pa t h   i s   c a l c u l a t e d  a n d  pr e de t e r m i n e d.   I n   c o n t r a s t ,   i n   t h e   R W   m o de l ,   t h e   n e w  l o c a t i o n   a nd   s pe e d  o f   t h e   m o bil e   s i n k  a r e   s e l e c t e d  r a n do m ly .   Al s o ,   t h e   s e l e c t i o n   o f   t h e   pa r a m e t e r s   f o r   a   s pe c i f i c   r o un d  i n  t h e   GM   m o de l   de pe n d s   o n   pr e vi o us   r o un ds ,   whi c h  m a y   c a u s e   pr o bl e m s   f o r   n e w  r o un ds .   C o m pa r e d  to  t h e   DF  M o de l ,   t h e   pr o p o s e d  m o de l   p e r f o r m e d  b e t t e r   un de r   a l l   n e t wo r k  s i z e s   a n d   s p e e ds   f o r   t h e   M S .   T he   r e a s o n  b e hi nd  s uc h   o b s e r v a t i o n   c a n   b e   r e ga r de d  a s   t h e   m e c h a ni s m   f o r   ge n e r a t i n g  t h e   M S   m o v e m e n t .   I n   ot h e r   w or ds ,   t h e   pr o p o s e d  m o de l   i s   b a s e d  o n   b u il d i ng  a n   M S T   t h a t   a i m s   t o  r e duc e   t h e   c o s t   a n d  t i m e   o f   vi s i t i n g  s t a t i c   Evaluation Warning : The document was created with Spire.PDF for Python.
I n do n e s i a n   J   E l e c   E n g  &   C o m p  S c i     I S S N:   2 5 0 2 - 4 7 52       Util iz ing  minimum  s panning  tr e e s   f or   e ff e c ti v e   mo bil e   s ink  r outi ng  in  w ir e les s   s e ns o r   …  ( A nas   A bu  T aleb )   1947   s e n s o r   n o de s ,   wh i c h   r e s u l t s   i n   a   pr o pe r   wa y   o f   vis i t i n g  n o de s .   On   t h e   ot h e r   h a n d,   t h e   DF   m o de l   i s   b a s e d  o n   c o n s t r uc t i n g  t h e   r o u t i n g  pa t h   b a s e d  o n   t h e   l o c a t i o ns   o f   t h e   n o de s ,   i . e . ,   n e i g hb o r h o o d ,   whi c h   m i g h t   a f f e c t   ot h e r   pa r t s   or   n o de s   i n   t h e   n e t wo r k   a n d  c a us e   pe r f o r m a nc e   p r o b l e m s .       T a bl e   2.   On e - wa y   de l a y   pe r f o r m a n c e   c o m pa r i s o n   M o de l  n a m e   S pe e d   N e tw o r k s iz e  ( N o d e s )   26 - N o d e   51 - N o d e   76 - N o d e   101 - N o d e   P r o p o s e d  m o d e l   5   104.99   169.78   27.22   77.61   10   256.36   34.60   30.87   87.13   15   220.48   120.40   51.75   346.04   20   655.19   77.59   212.51   150.58   R W   m o de l   5   1070.78   3590.09   5344.26   7348.23   10   1069.12   4247.96   4665.35   6904.05   15   811.182   3507.06   5812.7   4860.76   20   993.193   3535.66   6268.34   6077.27   G M   m o de l   5   578.377   4642.27   6166.82   6084.23   10   231.716   3631.09   4142.33   7122.23   15   461.982   2907.25   3492.46   4196.06   20   579.801   3803.8   5322.32   6334.38   D F   m o d e l   5   153.439   2790.29   7334.31   12043.8   10   116.511   3152.62   5937.32   11173   15   145.011   3335.92   6229.31   11422.9   20   392.171   3718.6   5352.08   11506.4       T a bl e   3.   P a c ke t  de l i ve r y   r a t i o   pe r f o r m a n c e   c o m pa r i s o n   M o de l  na m e   S pe e d   N e tw o r k s iz e  ( N o d e s )   26 - N o d e   51 - N o d e   76 - N o d e   101 - N o d e   P r o p o s e d  m o d e l   5   91.70   96.64   99.88   99.57   10   98.55   98.71   99.75   95.12   15   93.45   98.42   99.07   90.07   20   90.78   96.21   98.93   94.08   R W   m o de l   5   59.76   34.80   20.76   14.84   10   53.55   31.82   19.16   13.32   15   38.51   19.91   15.17   5.70   20   39.72   26.49   13.85   9.47   G M   m o de l   5   51.27   29.19   20.92   14.29   10   49.71   22.36   18.24   15.53   15   35.44   22.18   15.42   11.47   20   29.95   19.94   15.11   10.75   D F   m o d e l   5   55.91   37.62   19.38   9.06   10   56.92   34.54   19.93   10.64   15   55.33   35.48   17.62   7.39   20   53.08   33.62   18.34   7.19       T a bl e   4.   Ne t w or k  t h r o ugh put   pe r f o r m a n c e   c o m pa r i s o n   M o de l  n a m e   S pe e d   N e tw o r k s iz e  ( N o d e s )   26 - N o d e   51 - N o d e   76 - N o d e   101 - N o d e   P r o p o s e d  m o d e l    5   16.06   31.91   13.28   13.32   10   17.83   31.90   13.35   12.59   15   15.07   31.58   13.28   12.09   20   13.96   31.83   13.06   12.49   R W   m o de l   5   2.44   2.85   2.55   2.43   10   2.19   2.60   2.35   2.18   15   1.57   1.62   1.86   1.18   20   1.62   2.12   1.70   1.55   G M   m o de l   5   2.09   2.39   2.56   2.34   10   2.03   1.83   2.24   2.54   15   1.51   1.81   1.89   1.87   20   1.22   1.63   1.85   1.76   D F   m o d e l   5   2.28   3.07   2.37   1.48   10   2.32   2.82   2.45   1.74   15   2.27   2.90   2.16   1.21   20   2.18   2.75   2.25   1.18       4.   CONC L USI ON   T hi s   r e s e a r c h   de v e l o pe d  a   s i nk  m o bi li t y   m o de l   ba s e d  o n   b u il d i ng   a   M S T   o f   t h e   c ur r e n t   n e t w o r k .   Af t e r   i n t r o duc i n g  t h e   c o n c e pt   o f   M S T ,   t h e   s ugge s t e d   m o bil i t y   m o de l   wa s   d i s c u s s e d.   F ur t h e r m o r e ,   a   n u m b e r   Evaluation Warning : The document was created with Spire.PDF for Python.