I n d on e s i an   Jo u r n al   o El e c t r i c al   En gi n e e r i n g   an d   C o m p u te r   S c i e n c e   V o l .   15 ,   N o .   2 A ugus t   20 1 9 ,   pp .   879 ~ 887   IS S N :   2502 - 4752 ,   D O I :   10. 1 1591 / i j e e c s . v 1 5 .i 2 . pp 879 - 887             879       Jou r n al   h o m e pa ge ht t p: / / i ae s c or e . c om / j our na l s / i nde x . php/ i j e e c s   A n   o b st a c l e   a w a r e   m o b i l e   s i n k   p a t h   st r a t e g y   i n   W S N       T.   H .   F e i r o z   K h an 1 ,   D .   S i v K u m ar 2   1 D e pa r t m e n t   o f   C o m put e r   S c i e nc e   a nd   E ng i n e e r i ng ,   S a t hy a ba m a   I ns t i t u t e   o f   S c i e nc e   &   T e c hno l o gy ,   I ndi a   2 D e pa r t m e n t   o f   E l e c t r o ni c s   a nd   C o m m uni c a t i o E ng i n e e r i ng ,   E a s w a r i   E ng i ne e r i ng   C o l l e g e ,   I ndi a       A r ti c l e   I n fo     A B S TR A C T   Ar t i c l e   h i s t or y :   R e c e i v e O c t   11 ,   2018   R e v i s e F e b   10,   201 9   A c c e pt e M a r   21 ,   201 9       I n   W i r e l e s s   S e ns o r   N e t w o r k s ,   M o bi l e   S i n a c c o m pl i s h e s   c ons i d e r a b l e   a c hi e v e m e n t   o ne t w o r l i f e t i m e   i m p r o v e m e nt .   I s e ns i ng   e nv i r o nm e n t ,   m o r e   c ha nc e s   t o   pr e s e n t   t he   o bs t a c l e .   B u t ,   i t h e   m o bi l e   s i nk ,   ho w   t o   i de nt i f y   t he   o bs t a c l e   a nd  m a k e   t h e   o bs t a c l e   a w a r e   pa t s t r a t e gy   i s   a   c ha l l e n g i n g   t a s k.   T o   ov e r c o m e   t hi s   pr o bl e m ,   w e   p r o po s e   a O b s t a c l e   A w a r e   M o bi l e   s i nk  P a t S t r a t e gy   ( O A M P S )   t ha t   de t e c t s   a ny   o bs t a c l e s   w h i c e nt e r   w i t hi t h e   ne t w o r k   l i f e t i m e   a nd   de s i g a   s ho r t e s t   m o bi l e   s i n m o v e m e nt   pa t a v o i di n g   de t e c t e o bs t a c l e s .   I t hi s   s c he m e ,   t h e   m o bi l e   s i nk  c o l l e c t s   t he   s e n s i ng   da t a   f r o m   t he   s upe r   no de   t he n   i t   s e nd s   t he   da t a   t o   t he   ba s e   s t a t i o n.   H e r e ,   s t a t i c   o r   m o v i n o bs t a c l e s   a r e   pr e s e nt   w he n   t h e   m o bi l e   s i nk  m o v e s   t h e   p a t s c he dul i ng   by   s pa n ni ng   g r a ph .   T hi s   a l g o r i t hm   i s   i nt r o duc e t o   di s c o v e r i ng   t he   o bs t a c l e   a v o i di ng   s ho r t e s t   p a t h .   T h e   s o ur c e   s e l e c t s   t he   r o ut e   by   t he   upda t e c uc koo  s e a r c a l g o r i t hm .   T h e   s i m ul a t i o r e s ul t s   s ho w   t ha t   t he   O A M P S   i m pr o v e t he   t hr o ug hput   a nd   m i n i m i z e d   t he   de l a y   i n   t h e   ne t w o r k.   Ke y w or ds :   Cuc koo   s e a r c h   a l go r i t hm   w i r e l e s s   s e n s o r   n e t w o r k   M ob i l e   s i n k   O b s t a c l e   a w a r e   p a t s t ra t e gy   O b s t a c l e   de t e c t i o n   C opy r i gh t   ©   201 9   I n s t i t ut e   o f   A dv anc e E ng i ne e r i ng   and   S c i e nc e .     A l l   r i gh t s   r e s e r v e d .   Cor r e s pon di n g   Au t h or :   T .   H .   F e i r o z   K ha n ,     D e pa rt m e n t   o f   Co m put e S c i e n c e   &   E n gi n e e r i n g ,     S a t h y a b a m a   I n s t i t ut e   o f   S c i e n c e   &   T e c hn o l o g y ,     R a j i v   G a n d hi   S a l a i ,   J e ppi a a N a ga r,   C h e nna i ,   T a m i l   N a d 60 0119.   E m a i l :   f e i r o z k h a n36@ gm a i l . c o m       1.   I N TR O D U C TI O N   W i r e l e s s   S e n s o N e t w o r ks   (W S N s h a v e   e na b l e a   b r o a s p e c t r um   o f   a ppl i c a t i o n s   t hr o ug h   l o w - c os t   l o w - p ow e r   s e n s o n o de s ,   e . g. ,   ha b i t a t   m o ni t o ri n g ,   p r e c i s i o n   a g ri c ul t u r e ,   a nd  f o r e s t   f i r e   de t e c t i o n.   I t h e s e   a ppl i c a t i o n s ,   t h e   s e n s o r   n e t w o r w i l l   o pe r a t e   u nde r   a   f e w   h um a i nt e r v e nt i o n s   e i t h e b e c a us e   of   t h e   h o s t i l e   e n v i r o n m e n t   o r   hi g h   m a na ge m e n t   c o m pl e xi t y   f o r   m a n u a l   m a i n t e n a n c e .   S i n c e   s e n s o r   n o de s   h a v e   l i m i t e d   b a t t e r y   l i f e ,   e n e r gy   s a v i n i s   o f   pa ra m o un t   i m po rt a n c e   i t h e   de s i g n   o f   s e n s o r   n e t w o r p r o t o c o l s .   R e c e n t   r e s e a r c h   o n   da t a   c o l l e c t i o n   r e v e a l s   t h a t ,   ra t h e r   t ha n   r e po rt i ng  da t a   t hr o ug h   l o n g ,   m u l t i - h o p,   a nd  e rr o r - p r o n e   r o ut e s   t o   a   s t a t i c   s i n us i n t r e e   o r   c l us t e r   n e t w o r s t r uc t u r e ,   a l l o w i n a n l e v e r a gi n s i nk  m o b i l i t y   i s   m o r e   pr o m i s i n g   f o r   e n e r gy   e ff i c i e n t   d a t a   ga t h e ri n g .   M o b i l e   S i n ks   ( M S s ),   s u c a s   a ni m a l s   o r   v e hi c l e s   e qui ppe w i t ra di o   de v i c e s ,   a r e   s e nt   i nt o   a   f i e l a nd  c o m m u ni c a t e   di r e c t l y   w i t h   s e n s o r   n o de s ,   r e s ul t i n i n   s h o rt e r   da t a   t r a n s m i s s i o p a t h s   a n d   r e duc e e n e r gy   c o n s um pt i o n .   H ow e ve r ,   d a t a   g a t h e r i ng  us i ng  m o b i l e   s i n ks   i n t r o duc e s   n e w   c h a l l e n ge s   t o   s e n s o r   n e t w o r a ppl i c a t i o n s .   T o   be t t e r   b e n e f i t   f r o m   t h e   s i n k ’s   m o b i l i t y ,   m a ny   r e s e a r c h   e f fo r t s   ha v e   be e n   fo c us e o n   s t udy i n o r   s c h e dul i n m o ve m e n t   pa t t e rn s   o a   m o b i l e   s i n t o   v i s i t   s o m e   s pe c i a l   pl a c e s   i n   a   de pl oy e d   a r e a ,     t o   m i ni m i z e   da t a   g a t h e r i n t i m e .   I n   s uc h   a pp r o a c h e s ,   a   m o b i l e   s i n m o v e s   t pr e - de t e rm i n e   s o j o ur n   po i n t s   a n q ue r y   e a c h   s e n s o n o de   i n di v i du a l l y .   A l t h o ug h   s e v e r a l   m o b i l e   e l e m e nt s   s c h e dul i n (M E S p r o t o c o l s   ha v e   be e n   pr o po s e t o   a c h i e v e   e ff i c i e n t   da t a   c o l l e c t i o n   v i a   c o n t r o l l e s i nk  m o b i l i t y ,   de t e r m i ni n a n   o pt i m a l   m o v i n t ra j e c t o r y   fo r   a   m o b i l e   s i n i s   i t s e l f   a n   N P - ha r p r o b l e m ,   a n m a y   n o t   b e   a b l e   t o   a da pt   t o   c o n s t ra i n e a c c e s s   a r e a s   a n d   c ha n g i n g   f i e l s i t ua t i o n s .     E a rl y   ob s t a c l e   de t e c t i o n   a nd  a v o i da n c e   s c h e m e   [1]   f o r   de t e c t i n g   o b s t a c l e s   t h e n   m a ke   a n   o pt i m a l   pa t h.   T h i s   s c h e m e   de t e c t s   t h e   o b s t a c l e s   by   pa t h   o pt i m a l i t y   e v a l ua t i o n,   m a de   a t   t h e   n o de   l e v e l ,   gra du a l l y   ov e r   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   15 ,   N o .   2 A ugus t   2 019   :     879   -   887   880   t i m e .   T h us   t hi s   s c h e m e   i m p r o v e s   t h e   m e s s a ge   de l i v e r y   r a t e   a n m i n i m i z e s   t h e   o ve rh e a d .   O b s t a c l e   Re s i s t a nt   Ro bo t   D e pl oy m e n t   (O R R D a l go r i t hm   [2]  t ha t   m a n a ge s   n o de   pl a c e m e nt   po l i c y ,   a   s e r pe n t i n e   m o v e m e n t   po l i c y ,   a n o b s t a c l e   h a n d l i n r u l e s   i n   W S N .   T h i s   O R R D   h a n dl e s   t h e   u n p r e di c t e i rr e gul a r   o b s t a c l e s   i n   t h e   s i m ul a t i o e n v i r o nm e n t .   T h e   o b s t a c l e   i m pa c t s   b y   D e n i a l   o S e r v i c e   o r   c o n ge s t i o i a   W S N .   D e c e n t ra l i z e Bo un da r y   D e t e c t i o n   a l go ri t hm   [3]  f o r   r e c o gn i z i n p r e s e nt s   s e n s o r s   n e a r   o b s t a c l e   i n   t h e   W S N .   T h i s   a l go r i t hm   do e s   n o t   n e e a n y   a w a r e n e s s   o f   t h e   s e n s o r   l o c a t i o n s   a m o n t w o   n o de s .   H ow e v e r ,   t hi s   s c h e m e   r e qui r e s   kn o w l e d ge   of   t h e   t hr e e   h o n e i g h b o r s   i n   t h e   n e t w o r k.   O b s t a c l e   B o un da r y   D e t e c t i o n   A l go ri t hm   [4 de t e c t s   t h e   di s s i m i l a r   s h a pe o b s t a c l e .   H ow e ve r ,   t h i s   s c h e m e   de t e c t s   a o n l y   a   s t a t i c   o b s t a c l e   i n   t h e   n e t w o r k.   T h e   p r i m e   r e a s o f o r   us i n g   a n c h o r s   i s   f o r   c o m pa ra t i v e l y   l e s s   i n v o l v e m e nt   o f   s e n s o r s   i i t s   l o c a l i z a t i o n   a n o b s t a c l e   di s c ov e r y   pr o c e s s   c o n s i de ri n t h e   o pt i m a l   us e   o f   i t s   l i m i t e e n e r gy   r e s o ur c e s .   G o a   G o a l - S e e ki n O b s t a c l e   a n Co l l i s i o n   E v a s i o n   s c h e m e   ( G O CE [5]   i s   us e t o   de t e c t   t h e   o b s t a c l e   a n a v o i t h e   n e t w o r c o l l i s i o n   i t h e   n e t w o r k.   I n   o b s t a c l e   e v a s i o n ,   t h e   n o de s   a n pa c ke t s   e xc ha n ge   s t a t e   i n f o r m a t i o n   t o   c o m m u n i c a t e   t h e   e xi s t e n c e   of   bo t t l e n e c ks .   T h i s   s c h e m e   r e duc e s   bo t h   n e t w o r de l a y   a n b a n dw i dt h   c o n s um p t i o n .   H ow e ve r ,   du r i ng  h i g h   c o n ge s t i o n,   t h e   l a t e n c y   i s   i n c r e a s e d. T h e   M S   i s   us e t de c r e a s e   t h e   e n e r gy   ut i l i z a t i o n   o n o de s ,   a n i t   p r e v e n t s   t h e   c r e a t i o n   o e n e r gy   h o l e s   i n   W S N .   T h e s e   a r e   a l l   de pe n di n g   upo n   t h e   pa t h   w h i c h   i s   t a ke n,   e s pe c i a l l y   o n   de l a y - s e n s i t i v e   a ppl i c a t i o n s .   T h e   p r o po s e m e t h o h a s   ov e r c o m e   t h i s   p r o b l e m   by   fo r m i ng  a   h y b r i m o v i n pa t t e rn,   i n   t ha t   R e n de z v o us   P o i n t s   (R P s a r e   o n l y   v i s i t e d   by   m ob i l e   s i n n o de s .   T h e   p r i m a r y   di f f i c ul t y   t h e n   b e c o m e s   c o m put e   a   t o ur   t h a t   v i s i t s   a l l   t h e s e   R P s   i n   a   gi v e n   de l a y   bo un d.   W e i g ht e R e n de z v o us   P l a nni n i s   p r o p o s e d,   w h e r e by   e v e r y   s e n s o r   n o de   i s   a s s i g n e a   w e i gh t   a f t e r   i t s   h o di s t a n c e   f r o m   t h e   t o u r   a s   w e l l   a s   t h e   a m o u n t   o f   da t a   pa c ke t s   t ha t   i t   o n w a r ds   t o   t h e   n e i g h b o uri n R P .   T h e   e f f i c i e n c y   c a n   b e   i m p r o v e by   t a ki n a c c o un t   o f   da t a   w i t di s s i m i l a de l a y   n e e ds   [6] .   D e c e n t ra l i z e B o un da r y   D e t e c t i o n   (D B D a l go r i t h m   [7]  i s   p ro pos e fo r   i de n t i fy i n t h e   s e n s o r   n o de s   c l o s e   t o   a   h o l e   o r   o bs t r uc t i o n   i n   t h e   W S N .   T h i s   a l go ri t hm   do e s   n o t   n e e a n y   i n f o r m a t i o n   o f   t h e   n o de   l o c a t i o n   o r   s pa c e   a m o n t w o   n o de s .   T h e   m a i n   a dv a n t a ge   o f   us i n t h i s   a l go r i t hm   i s   t o   pr o v i de   l o c a t i o n - f r e e .     T h e   o ut c o m e s   e ff e c t i v e l y   d e t e c t   a l l   b o un da ri e s   i n   t h e   W S N s   w i t h   t h e   l e s s e r   c o n t r o l   o v e r h e a d .   O b s t a c l e   A vo i da n c e   i n   M o b i l e   Ro bo t i c   S e n s o r s   [8]  i n v e s t i ga t e s   o t he   i m po rt a n c e   o f   c o nn e c t i v i t y   a n r e s t o r a t i o n   o m o b i l e   r obo t i c   s e n s o r s   t h a t   w o r u n de r   ha r s h   e n v i r o nm e nt s .   T h e   e xi s t i n s y s t e m s   a vo i t h e   pr o b l e m   of  ob s t a c l e   a vo i da n c e .   T h e   pa pe r   s ugge s t s   a n   e ff e c t i v e   m e t ho do l o g y   n a m e d ,   o n l i n e   c o nn e c t i v i t y   r e s t o r a t i o s t ra t e gy ,   w h i c h   w i t h s t a nds   unde r   r e a l - w o r l w o r k i ng  c o n di t i o n s .   A u t o n o m i c   O b s t a c l e   D e t e c t i o n   a nd  A vo i da n c e   [9]  i n v e s t i ga t e   i n s t e a t h e   dy n a m i c   a n d   a u t o n o m i c   de t e c t i o n   o f   o bs t a c l e s   t ha t   m i g h t   s t a nd  w i t h i t h e   n e t w o r k.   T hi s   i s   a c c o m pl i s h e us i n t h e   e nha n c e c a rt o gra p h y   o pt i m i z e l i n s t a t e   r o ut i n w i t h   n o   e xt r a     s i g n a l l i ng  o v e r h e a d.   G e o gr a p h i c   R o ut i ng  i Cl us t e r e W S N s   a m o n g   O b s t a c l e s   [10]  p r o po s e d   a   c l us t e ri n t e c hn i q ue   i n   W S N s   na m e e n e rgy - e ff i c i e n t   h o m o ge n e o us   c l us t e r i n t h a t   pe r i o di c a l l y   s e l e c t s   t h e   c l us t e h e a ds   a c c o r di ng  t o   a   h y b r i of   t h e i r   r e s i dua l   e n e r gy   a n a   s e c o n da r y   pa r a m e t e r,   s uc h   a s   t h e   ut i l i t y   of   t h e   s e n s o r   t o   i t s   n e i g h b o ur s .   In   t hi s   w a y ,   t h e   s e l e c t e c l us t e r   h e a ds   h a v e   a n   e qu a l   n u m b e r   of   n e i gh b o ur s   a n r e s i du a l   e n e r gy .   V i rt ua l   Co o r di na t e - B a s e By pa s s i n V o i R o ut i n p r o t o c o l   [11]  i s   t o   t r a n s f o r m   a   ra n do m   s t r uc t u r e   c o m po s e of  vo i e dge s   i n t o   a   r e gul a r   o n e   by   m a ppi n e dge   n o de s   c o o r di n a t e s   t o   a   v i r t u a l   c i r c l e .   By   ut i l i z i n t h e   v i rt ua l   c i r c l e ,   t h e   g r e e d y   f o r w a r di n c a n   b e   pr e v e n t e f r o m   f a i l i n g ,   s o   t h a t   t h e r e   i s   n o   r o ut i n v o i i n   t h e   fo r w a r d i n g   pr o c e s s   f r o m   s o ur c e   t de s t i n a t i o n   a nd  c o n t r o l   ov e r h e a c a n   b e   r e duc e d.   F ur t h e r m o r e ,   t h e   v i r t u a l   c i r c l e   i s   b e n e f i c i a l   t o   r e duc e   t h e   a v e r a ge   l e n g t h   o r o ut i n pa t h s   a n de c r e a s e   t r a n s m i s s i o n   de l a y .   H ow e ve r ,   t hi s   m e t h o i n c r e a s e s   t h e   l o a w h e n   l a r ge   v o i d s   i n   t h e   n e t w o r k.     A n   o b s t a c l e - a w a r e   pa t h   l o s s   m o de l   [12]   is   us e d   t o   r e f l e c t   t h e   e ff e c t   of   t h e   ob s t a c l e s   o n   t h e   c o m m u n i c a t i o n   a m o n g   s e n s o r s .   It   m a i n t a i ni n a n   a c c e pt a b l e   e n e r gy   c o n s um p t i o n   a nd   pa c ke t   de l i v e r y   r a t i o   in   t h e   n e t w o r k.   A n   o b s t a c l e   a w a r e   c o nn e c t i v i t y   r e s t o r a t i o n   s t ra t e gy   [13]   i s   d e s i gn e f o r   o pt i m i z i ng   t h e   ob s t a c l e - a v o i di n m i ni m u m   s pa nni n t r e e   of   t h e   s e gm e n t s   a n de t e r m i n e   t h e   r e l a y s .   K   ve r t e x - di s j o i nt   s h o rt e s t   p a t h s   i W SN   [ 1 4 ]   t ha t   p r o c e dur e s   c o un t i ng  pa t h s   t o   di m i n i s h   t h e   r e l a y   n o de s   c o un t S w a r m   i n t e l l i ge n c e   o pt i m i z a t i o n   t e c hni que   [1 5 for   o bs t a c l e - a v o i da n c e   pa t h   p l a nni n g   i n   W S N s .   T hi s   pl a nni n i s   c o n s i de r e d   by   t w o   s w a r m   i nt e l l i g e n c e   a l go ri t hm s ,   t ha t   is   g r e y   w o l f   o pt i m i z e r   a nd  w h a l e   o pt i m i z a t i o n   a l go r i t hm .         2.   A N   O B S TA C L A WA R E   M O B I L S I N K   P A TH   S TR A TEG Y   In   r e c e n t   y e a r s ,   W S N s   a r e   e m pl oy i n c o l l e c t i n i n f o r m a t i o n   f r o m   v a ri o us   e n v i r o nm e n t s   v i a   s e n s o n o de s .   T o   pr o t e c t   t h e   s e n s o r   n o de   f r o m   t h e   e n e rgy   h o l e   pr obl e m ,   t h e   M S   i s   us e d.   T hi s   M S   m o v e s   t h e   s e n s i n g   e n v i r o n m e n t ,   a n i t   i s   g a t h e r i ng  i n f o r m a t i o n   t hr o ug h   s e n s o r   n o de s .   H ow e v e r ,   t h e   o bs t a c l e   pr e s e nt   t h e   s e n s i ng  e n v i r o n m e n t   t h e   M S   i s   c a n ’t   m o v e   r e gul a r l y .   T o   s o l v e   t h i s   p r o b l e m ,   w e   pr o po s e   A n   O b s t a c l e   A w a r e   M o b i l e   S i nk  P a t S t ra t e gy   i W S N .     F i gu r e   de m o n s t r a t e s   t h e   a r c h i t e c t u r e   o f   t h e   p r o po s e s c h e m e .   T h e   b a s e   s t a t i o n   i s   a o w n e r   o f   a   W S N .   H e r e ,   a   num b e r   o f   s e n s o r   n o de s   a r e   di s s e m i na t e o v e r   w h e r e   s o m e   ob s t a c l e s   e xi s t .   A l s o   pr e s e nt s   s o m e   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       A o bs t a c l e   aw ar e   m obi l e   s i n k   p at h   s t r at e gy   i W SN   ( T .   H .   F e i r oz   K han )   881   S upe r   n o de .   I t   ha s   a d di t i o na l   c o m m u ni c a t i o r a nge   a n d   e n e r gy .   It   c o l l e c t s   t h e   i n f o r m a t i o n   f r o m   t h e   s e n s o r   n o de ,   a n i t   s e n ds   t h e   i n f o r m a t i o n   t o   t h e   M S .   In i t i a l l y ,   t h e   M S   c o l l e c t s   t h e   s upe r   n o de   a n s e n s o r   n o de s   i n f o r m a t i o n   f r o m   t h e   b a s e   s t a t i o n.   T h e n   t h e   M S   s t a rt   da t a   ga t h e r i ng  p r o c e s s ;   t h e   M S   s e n ds   R R E Q   m e s s a ge   t t h e   S upe n o de .   T h e   s upe r   n o de   b r o a dc a s t   t h i s   m e s s a ge   t o   w i t h i c o m m u n i c a t i o n   ra n ge   s e n s o n o de s .     T h e t h e   s e n s o n o de s   s e n t h e   up da t e i n f o r m a t i o t o   M S   v i a   t h e   s upe n o de .   A n y   s e n s o r   n o de   c o m m u n i c a t e s   t h e   s e n s i n i n f o r m a t i o t o   t h e   b a s e   s t a t i o n   t hr o ug h   t h e   s upe n o de .   S uppo s e ,   t h e   s e n s o r   n o de   o r   s upe r   n o de   c a nn o t   b e   r e c e i v e o r   t ra n s m i t   w h i c h   i n f o rm a t i o a t   a   t i m e   t h e   s upe de c i de s   p o s s i b l e   t pr e s e n t   i n   t h e   o b s t a c l e .   T h e n   t h e   s upe t ra c ke t h e   o b s t a c l e   l o c a t i o n   a n i de nt i f i e t h e   ob s t a c l e   i s   s t a t i c   o r   m o v a b l e .   If  t h e   o b s t a c l e   i s   s t a t i c ,   t h e   M S   p a t h   i s   p r e de t e rm i n e d .   T h e   de t e c t e ob s t a c l e   i s   m o v a b l e   w h e n   f i n d i n g   o ut   t h e   o pt i m a l   p a t h.           F i gu r e   1 .   A r c h i t e c t ur e   o f   O bs t a c l e   A w a r e   S c h e m e       2. 1 .       S p an n i n g   G r ap h   A l go r i th m   In   t h i s   s c h e m e ,   w e   us e   t h e   m i n i m u m   s pa nni n t r e e   t o   di s c ov e r   a n   o b s t a c l e - a v o i di n s h o r t e s t   r o ut e   fo r   t h e   m o b i l e   s i n k .   T h e   o b s t a c l e - a vo i di n s p a nn i ng  g r a p h   i s   t h e   s e t   o f   e dge s   t h a t   c a n   b e   de s i gn e by   m a ki ng  a s s o c i a t i o n s   b e t w e e n   s e n s o r s   a n o b s t a c l e   b e n ds .   O n c e   a   s pa nni n g ra p h   i s   a s s e m b l e d,   t h e   u n b o un de po s s i b l e   s i t e s   fo r   t h e   M S   m ov e m e n t   w i l l   be   m i n i m i z e t o   a   l i m i t e s e t   o s i t e s .   T h e r e f o r e ,   t h e   a l go r i t hm   b a s e o n   t h e   s p a nni n g   g r a p m a ke s   i t   m o r e   e f f i c i e n t   t o   s c h e d ul e   f o r   t h e   M S .   T h e   o b s t a c l e - a vo i di n g   s pa nni n g   g ra p h   i s   t h e   s e t   o f   e dge s   t ha t   c a n   b e   f o r m e by   m a ki n g   c o nn e c t i o n s   b e t w e e n   t e r m i n a l s   a n o b s t a c l e   b e n ds .   O n c e   a   s p a nni n g r a p i s   c o n s t ruc t e d,   t h e   i n f i n i t e   po s s i b l e   s i t e s   fo r   t h e   m o b i l e   s i n k   m o ve m e n t   w i l l   b e   r e duc e t o   a   f i n i t e   s e t   o f   s i t e s .           F i gu r e   2 .   S e n s o r   V e r t i c e s   w i t o b s t a c l e   be n ds       F i gu r e   e xpl a i n s   t h e   s e n s o r   v e r t i c e s   a n s e pa ra t i o n   f o r   a n   ob s t a c l e   c o r n e r   c o r r e s po n d i n gl y .   In   t hi s   f i gur e ,   t h e   r e gi o n   R a n R ob s t a c l e   c o r n e r s   a r e   j o i n e t o   t h e   s pa nni n g r a p h .   H e r e ,   s o r t   e l e m e nt s   o t h e   l i s t   V   by   n o n - de c r e a s i n g   c o o r di na t e s .             M o b i l S i n k   S u p er   N o d e   S e n s o r   No d e   O b s t a c l e     B a s S t a t i o n     O4   O3   O2   O1   O b s t a c l e   R1   R2   R8   R7   R6   R5   R4   R3   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   15 ,   N o .   2 A ugus t   2 019   :     879   -   887   882   S i m i l a rl y ,   t h e   r e gi o R a n d   R a l s o   ob s t a c l e   c o r n e r s   b ut ,   h e r e   s o r t   e l e m e nt s   o f   t h e   l i s t   V   b y   n o n - de c r e a s i n y   c oo r di n a t e s   i n   t h e   r e g i o n   R a n R of   a l l   o bs t a c l e   c o r n e r s .   B e s i de s   t h e   r e g i o n   R a n R of  ob s t a c l e   c o r n e r s ,   t h e   r e gi o R a nd  R o f   j o i n   v e r t i c e s .   W e   s o r t   e l e m e n t s   o f   t h e   l i s t   V   b y   n o n - de c r e a s i ng  x   +   y   c oo r di n a t e s   i n   t h e   r e gi o n   R a n R of   ob s t a c l e   c o r n e r s   a nd  t h e   r e gi o n   R a n R o j o i n i n v e r t i c e s .   S i m i l a rl y ,   t h e   r e gi o n   R a nd  R o f   a l l   ob s t a c l e   c o rn e r s   a n t h e   r e gi o n   R a n R o f   j o i n   v e r t i c e s .   H e r e ,   t h e   e l e m e n t s   o t h e   l i s t   V   a r e   s o r t e by   n o n - de c r e a s i n y - c oor d i n a t e s .   A c c o r di n t o   t h e   qua d ra n t   pa rt i t i o n   f o r   a n   o bs t a c l e   c o r n e r   a nd  a   pi nn e v e r t e x,   w e   f i n a l l y   c o n s t r uc t   t h e   s pa nni n g ra p h.   A s   a   r e s ul t ,   t h e   M S   m o ve m e n t   di s t a n c e   c a n   b e   m i n i m i z e d.   I n   W S N ,   t h e   e n v i r o nm e nt   c o n s i s t s   o o bs t a c l e s   w i t h   d i f fe r e nt   s ha pe s   ow i n t o   t h e   i rr e gul a r   s ha pe   of   ob s t a c l e s .   T h us ,   t h e   s pa nni n g r a p h   a l go r i t hm   t o   di s c ov e r   a n   o b s t a c l e - a v o i di n g   s h o r t e s t   r o ut e   m i n i m i z e M S   m o v e m e n t   s t ra t e g y .     2. 2 .       S ta ti c   O b s tac l e   In  a   s t a t i c   o b s t a c l e   p r o t e s t i ng  s i t ua t i o n ,   o b s t a c l e s   l o c a t i o n s   a r e   pe rm a n e nt   w h e t h e   M S   s e e s   e v e r y   ob s t a c l e   bo un da r y   by   t r a v e l l i n s a l e s m a n   p r o b l e m .   T h e   e l a bo r a t e p r o c e s s   of   M S   m o t i o n   m e t h o i n   s t a t i c   ob s t a c l e   pr o t e s t i n s u rr o undi n i s   e xpl a i n e b e l ow :   i f   o n e   ob s t a c l e   e xi s t s   w i t hi n   t h e   a r e a ,   t h e n   s u pe r   n o de   i n f o r m s   M S   e a r l i e r   t ha n   v i s i t i n t h e   a r e a .   W hi l e   t h e   M S   i n i t i a t e s   da t a   ga t h e ri n w i t h i n   t h e   o b s t a c l e   a r e a ,   t h e   M S   m a ke   m i n i m u m   s pa nni n t r e e   t o   di s c ov e r   a o b s t a c l e - a v o i di n s h o r t e s t   r o ut e .   I n   o b s t a c l e   pr o t e s t i n g   s urr o u n di ngs ,   M S   c h o o s e s   e xa c t i n d a t a   ga t h e r i n po i nt s   w i t h i n   t h e   a r e a .   S upe r   n o de s   a r e   s e l e c t s   t h e   da t a   ga t h e r i ng  po i n t s   t h us   s e n s o r   t o   c o m m uni c a t e   d a t a   t o   M S   w i t h   l e a s t   e n e r gy   l o s s .   T h e M S   v i s i t s   s upe r   n o de   po i n t s   w i t h i t h e   a r e a   n e xt   e v e r y   s e n s o r   n o de   c o m m u n i c a t e   d a t a   t o   M S   w h i c h   s t o ppe v i a   a n y   ob s t a c l e .     2. 3 .       M o v i n O b s tac l e   In  m o v i n o b s t a c l e   pr o t e s t i ng  s u rr o undi n gs ,   o b s t a c l e   e xc h a n ge s   i t s   l o c a t i o n   w i t h   r e ga rd  t o   t h e   t i m e   pe r i o d.   A s   a   r e s ul t ,   M S   a l s o   c ha n ge s   i t s   m o t i o n   p a t hw a y   w i t h   r e ga r t o   ob s t a c l e   m o t i o n   po l i c y .     T h e   e l a b o r a t e p r o c e s s   of   M S   m o t i o n   m e t h o i m o v i n o b s t a c l e   p r o t e s t i n g   s u rr o u n di ng  i s   e xpl a i n e d   b e l ow :   If   ob s t a c l e   goe s   f r o m   o n e   a r e a   t o   a n o t h e r   a r e a   w i t h   M S   w i t h i t h e   s i m i l a r   s upe r   n o de ,   t h e n   M S   ov e r c o m e   t h e   ob s t a c l e   i f   t h i s   o b s t a c l e   i s   s t o ppe t h e   M S   m o t i o n   p a t h w a y .   T h e n,   t h e   s upe r   n o de   i n f o r m s   ob s t a c l e   e n t r o py   w i t h   a   de f i ni t e   t i m e   by   t h e   bo r de r   s e n s o r   n o de s   of   t h e   ob s t a c l e .   W h i l e   s upe r   n o de   ob t a i n s   upda t e   i n f o r m a t i o n   f o r   M S   m o t i o n ,   t h e n   M S   e xc h a n ge s   i t s   m o t i o n   pa t h w a y   i obs t a c l e   s t o ps   t h e   M S   m o t i o n s .   If   ob s t a c l e   goe s   w i t h   t h e   M S   a n d   a t t a i n s   t o   n e xt   v i s i t i n a r e a   w i t h   M S ,   t h e n   s upe r   n o de   do e s   n o t   a s s i g n   t hi s   a r e a   f o r   M S   t r a v e l .   In   t ha t   s i t ua t i o n ,   s upe r   n o de s   a s s i g n   di f fe r e n t   n e a r b y   n o n - v i s i t i n a r e a   a f t e r   t h a t   M S   de t e c t s   s pa nn i n g   g ra p a l go ri t hm   t o   o ve r c o m e   t h e   di s c o ve r e o b s t a c l e .       2. 4 .       R o u te   F o r m ati o n   A f t e r   de t e c t i ng  t h e   o b s t a c l e ,   a n t h e t h e   s o ur c e   n o de   f o r m   t h e   r o ut e   b a s e o n   t h e   Cuc ko o   S e a r c (CS A l go r i t h m .   CS   i s   a   h e u ri s t i c   s e a r c h   a l go r i t hm   t h a t   c uc koo s   s e l e c t   n e s t s   (n e i g h b o r   n o de s of   a n o t h e r   b i rd  t o   pl a c e   t h e i r   e ggs   ( n o de s ).   P r o v i de n t i a l l y ,   t h e   o t h e r   b i r e a s i l y   r e c o gn i z e s   t ha t   t h e   e ggs   a r e   n o t   i t s   pe r s o n a l   a n m a y   b e   d e s t r uc t s   t h e   c uc koo   e gg.   T h e r e f o r e ,   t h e   c uc koo   o r i g i n a t e e vo l ut i o n a l l y   ge n e r a t e s   e ggs   t ha t   a ppe a r   r e l a t e t o   t h e   h o s t   b i r ds .   T h us ,   t hr e e   s i g ni f i c a nt   s t a ge s   l e a a o pt i m i z a t i o n   p r o c e dur e ,   w hi c   i s   a s   f o l l ow s :   a)   Ini t i a l l y ,   t h e   e gg  o f   c uc koo   a c t s   a s   a   s e t   o f   s o l ut i o n s   t ha t   a r e   ra n do m l y   po s i t i o n e a t   d i f f e r e n t   n e s t s .   b)   N e xt ,   t h e   b e s t   e ggs   w i t h   s ui t a b l e   s o l ut i o n s   w i l l   b e   pe rm i t t e t o   s h i f t   i n t o   t h e   n e xt   s t e p.   c)   F i na l l y ,   o n e   of   t h e   e ggs   i s   r e c o gn i z e a s   e xt ra o r di na r y ,   t h e n   t ha t   s o l ut i o n   w i l l   b e   r e m o v e d,   a n d   t h e   l a t e s t   e gg  w i l l   r e s t o r e   t h i s   s t ra n ge   i n   a   n e w   n e s t .   T h e   p r o c e s s   of   t h e   CS   i s   e xp l a i n e d:   Ini t i a l l y   P o h o s t   n e s t s ,   a   r e s t   o f   po pul a t i o n . 1 p pop i i P   Ca l c ul a t e   f i t n e s s   o f   n e s t s   b a s e o n o de   e n e r gy 1 ( n e s t ) f ( p ) pop i i F i t   D o   It e r a t i o n s < M a x i m um   It e ra t i o n s   {   M a ke   a   c uc ko o   e gg  P o f   a   ra n do m   n e s t   Ca l c ul a t e   t h e   f i t n e s s   f (p’ i )   Ch e c p r e s e nt   e gg :   s e l e c t   a n o t h e a   r a ndo m   n e s t     If   f (p’ i <   p i {   P j = p’ i   }   Co n s t r uc t   f r e s n e s t s   ra n do m l y   a t   n e w   po s i t i o n s   }   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       A o bs t a c l e   aw ar e   m obi l e   s i n k   p at h   s t r at e gy   i W SN   ( T .   H .   F e i r oz   K han )   883   T h e   o r i gi na l   CS   i s   s t r a i g h t f o r w a rd,   a nd  i t   h a s   l e s s   pa r a m e t e r   t o   a dj us t   t h e r e fo r e   t h e r e   i s   a   l a r ge   po s s i b i l i t y   fo r   l o c a l   c o n ve r ge n c e   ge t t i ng  f e w e r   qua l i t y   r e s ul t s .   T h us   w e   u pda t e   t h e   CS   t e c hni que   by   t h e   di ff e r e n t   o pe r a t o t h a t   r a n do m l y   upda t e s   t h e   v a l ue s   a t   o n e   o m o r e   i n v e s t i g a t e   p l a c e s   o f   t h e   e l e c t e e ggs .     A l o n w i t h   t h i s   p r o c e s s ,   fo r   e ve r y   e gg 12 {p , p , ... . p } t in P 1 12 {p ' , p ' , . . . . p } t in P i t h e   po pul a t i o n   o f   th   i t e ra t i o n,   a   n e w   e gg 1 12 {p ' , p ' , . . . . p } t in P i s   f o r m e d   as :     p ( , p p ) , i f a r a n d (0 , 1 ) 0 . 5 ' p ( , p p ) , i f a r a n d (0 , 1 ) 0 . 5 k A k k k k R I P I   (1)     W h e r e     a nd  R   a r e   t h e   a c c e pt a n c e   po s s i b i l i t y   a n r e j e c t i n g   po s s i b i l i t y   r a t e s   o f   t h e   v a r i a b l e s     . T h e   a m o u n t   Δ(I, G e n e r a t e s   a r e a l   n u m b e r   i t h e   ra n ge [0 ,   i . e ,   Δ(I , )   a pp r o a c h e s   z e r o   a s   t h e   c o un t   o f   i t e ra t i o n s   ra i s e s .   T h e   a b ove   fo r m u l a   b ui l ds   t h e   f r e s h   e ggs   t o   i n v e s t i ga t e   t h e   s pa c e   e qua l l y   t hr o ug h   t h e   s t a r t   o f   t h e   r u n   w hi l e   i t e ra t i o n   qu a n t i t y   i s   s m a l l   a n a dj us t   t h e   s e a r c h   s pa c e   a s   t h e   i t e ra t i o n   n u m b e r   m o v e m e n t .   T hi s   p r o c e s s   r a i s e s   t h e   c ha n c e s   of   m a ki n g   f r e s e ggs   c l o s e   t o   i t s   b e s t - l i v e e ggs .   T h e   q ua nt i t y   Δ(I, )i s   c o m put e b y   t h e   s ub s e que n t   f u n c t i o n :     ( I , y ) 1 ( 1 t / T ) p y   (2)     W h e r e =   ra n do m   num b e a m o n g   [0 ,   1],     =   m a xi m um   n u m b e r   o f   i t e r a t i o n s ,   =   s y s t e m   pa r a m e t e t h a t   de t e r m i n e s   t h e   de gr e e   o f   de pe n de nc y .   T h e r e f o r e ,   U CS   w i l l   pr o duc e   t h e   f r e s h   n e s t s   a nd  t h e   f r e s h   e gg  s h o ul a c c o m pl i s h   a l l   t h e   r e s t ra i nt s .   T hi s   i s   unde r s t o o by   t a ki n g   i nt o   a c c o un t   t h e   f o l l o w i n c r i t e r i o n   a n d   i s   e xp l a i n e a s   f o l l ow s :   a)   If   t h e   e gg  s t r uc t u r e   i s   n e ga t i v e   o r   z e r o ,   t h e n   s ub s t i t ut e   t h e   f r e s h   e gg’s   c o m pl e t e   v a l ue   by   a   r e c e n t l y   y i e l de ra n do m   num b e w h i c h   f ul f i l l s   t h e   l i m i t a t i o n .   b)   If   n e w   e gg  s t r uc t u r e   i s   hi g h e r   t ha n   o n e ,   t h e n   r e p l a c e   t h e   n e w   e gg  s t r uc t u r e   by   o n e .   T h e n,   t h e   n e w   n e s t   i s   fo r m e d;   i t   i s   m e a s u r e by   t h e   f i t n e s s   f un c t i o n .       3.   S I M U LA TI O N   S E TTI N G S   In   t h i s   s e c t i o n,   w e   a ppl y   A n   O b s t a c l e   A w a r e   M ob i l e   S i n P a t h   S t ra t e gy   f o r   t h e   s e n s i n f i e l a n d   e v a l ua t e   t h e   pe r f o r m a n c e   o f   t h e   a l go r i t h m   b y   us i n n e t w o r s i m ul a t o r .   I n   t h i s   e xpe ri m e n t ,   w e   a s s um e   t h a t   50   s e n s o r   n o de s   a r e   r a ndo m l y   di s t r i b ut e o v e r   a   500x5 00 m   f i e l d.   S i m ul a t i o n   s e t t i n gs   a nd  E v a l u a t i o n   R e s ul t s     a r e   a s   f o l l ow s .     3. 1 .       P ac k e t   R e c e i v e d   R ate   P a c ke t   R e c e i v e R a t e   (P R R i s   d e f i n e a s   t h e   ra t e   o f   pa c k e t s   de l i v e r e t o   t h e   de s t i n a t i o n   n o de .   P D i s   m e a s u r e d   by   ( 3 ) .   W h e r e ,   num b e o f   s e n s o r   n o de s .     0 n Pa c k e t sDe l v PDR T i me   (3)     T h e   t o t a l   n u m b e r s   of   pa c ke t s   r e c e i v e i n   t h e   s e n s i n f i e l of   t h e   O A M P S   pl o t t e a ga i n s t   t h o s e   of  t h e   e xi s t i n p r o t o c o l   G O CE   i n   F i gu r e   r e s pe c t i v e l y .   H e r e ,   t h e   r e c o l o r   c ur v e   r e p r e s e n t s   t h e   pa c ke t   r e c e i ve d   ra t e   o f   G O CE   a nd  g r e e n   c o l o r   c u r v e   r e p r e s e n t s   t h e   O A M P S .   T h e   c h e c ki n g   o f   t h e   m e s s a ge s   fo r   e v e r y   da t a   t r a n s m i s s i o i G O CE   c a us e s   gr e a t e r   o v e r h e a d   a n d   pa c ke t   l o s s .   T h e r e f o r e   O A M P S   pe r f o r m s   b e t t e r   t ha t h e   G O CE   p r o t o c o l .       3. 2 .      P ac k e t   Lo s s   R ate   (P LR )   P a c ke t   L o s s   R a t e   i s   de f i n e a s   t h e   n u m b e r   o f   pa c ke t s   l o s t   pe u n i t   t i m e .   P L R   i s   m e a s u r e b y   ( 4 ) .     0 n Pa c k e t sL os t PL R T i me   (4)   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   15 ,   N o .   2 A ugus t   2 019   :     879   -   887   884   T h e   t o t a l   n um b e r s   o f   pa c ke t s   l o s t   of   t h e   O A M P S   a r e   pl o t t e a ga i n s t   t h e   c o rr e s po n di ng  G O CE   i F i gu r e   r e s pe c t i v e l y .   T h e   r e a s o n   f o r   t h e   p a c ke t   l o s s   i s   t h e   s a m e   a s   t ha t   o f   t h e   pa c ke t   de l i v e r y   i n   b o t h   t h e   c a s e s   of   W S N s   s i n c e   pa c ke t   l os s   o n l y   c o n t ra di c t s   t h e   pa c ke t   de l i v e r y .   T h e   n u m b e r   o pa c ke t s   r e c e i v e by   t h e   e xi s t i n m e t h o ds   i s   l e s s e r   due   t o   t h e   e n e r gy   c o n s um pt i o n   a nd  de l a y .   B ut   t h e   O A M P S   m e t h o i s   t o   r e duc e   t h e   pa c ke t   l o s s   c o m pa r e t o   t h e   G O CE .           F i gu r e   3 .   P a c ke t   R e c e i v e r a t e   o f   O A M P S   a n d   G O CE           F i gu r e   4 .   P a c ke t   L o s s   r a t e   o f   O A M P S   a n d   G O C E   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       A o bs t a c l e   aw ar e   m obi l e   s i n k   p at h   s t r at e gy   i W SN   ( T .   H .   F e i r oz   K han )   885   3. 3 .       A v e r age   D e l ay   T h e   di f f e r e n c e   o f   t i m e   a m o n t h e   c u rr e n t   pa c ke t s   r e c e i v e a n d   t h e   p r e v i o us   pa c ke t   r e c e i v e i s   c a l l e A v e r a ge   D e l a y .   It   i s   m e a s u r e by   t h e   ( 5 ) .   F i g u r e   i ndi c a t e s   t h a t   t h e   ra n ge   o f   de l a y   i s   s m a l l   f o r   t h e   p r o po s e d   m e t h o O A M P S   t h a n   t h e   e xi s t i ng  m e t h o G O CE .   T h e   de l a y   i n   t h e   n e t w o r m a y   l e a t o   l os i n t h e   i n f o r m a t i o n.     n 0 P kt R e c v d T im e - P kt S e nt T im e A D = n   (5)           F i gu r e   5 .   A v e r a ge   D e l a y   of   O A M P S   a nd  G O C E       3. 4 .       Th r o u gh p u t   T hr o ug h put   i s   de f i n e a s   t h e   a v e r a ge   pa c ke t s   de l i v e r e t o   t h e   de s t i na t i o n   s uc c e s s f ul l y .   T h e   t hr o ughput   i s   e s t i m a t e us i n g   ( 6 )     0 ( ) * * 8 1000 n P k ts R e c e iv e d n P k t Size T hro ug hp ut   (6)     T hr o ug h put   i s   m e a s u r e i n   t e rm s   o by t e s ,   a n h e n c e   t h e   o b t a i n e v a l ue   i s   m ul t i pl i e w i t h   8 ,   s o   t h a t   ob t a i n e v a l ue   i s   c o n v e r t e i n t o   b i t s .   T h e n   t h e   v a l ue   i s   a g a i n   di v i de by   1000  f o r   t h e   c o n v e r s i o p r o c e s s   f r o m   b i t s   i nt o   ki l o b i t s .   F i gu r e   i n di c a t e s   t h a t   t h e   p r o po s e pr o t o c o l   O A M P S   h a s   b e t t e r   t hr o ug h pu t   w h e n   c o m pa r e t o   t h e   e xi s t i n g   p r o t o c o l   G O CE .     3. 5 .       R e s i d u al   En e r gy   T h e   qua nt i t y   of   r e m a i n i ng  e n e r gy   i a   s e n s o r   n o de   a t   t h e   p r e s e nt   c a s e   o f   t i m e   i s   c a l l e a s   r e s i dua l   e n e r gy .   I n   t h e   n e t w o r o pe r a t i o n s ,   t h e   ra t e   o f   c o n s um e d   e n e r gy   i s   c a l c ul a t e b y   t h e   r e s i du a l   e n e r gy .     T h e   r e s i du a l   e n e r gy   i s   e s t i m a t e d   us i n g   ( 7 ) .     Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   15 ,   N o .   2 A ugus t   2 019   :     879   -   887   886       F i gu r e   6 .   T hr o ug h put   o f   O A M P S   a n G O C E           F i gu r e   7 .   R e s i dua l   E n e r gy   o f   O A M P S   a n d   G O CE       R e sE n I n itia lE n e rg y Cu rr E n e rg y    (7)   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       A o bs t a c l e   aw ar e   m obi l e   s i n k   p at h   s t r at e gy   i W SN   ( T .   H .   F e i r oz   K han )   887   F i gu r e   i n di c a t e s   t ha t   i t h e   n e t w o r t h e   r e s i dua l   e n e r gy   i s   e nha n c e f o r   t h e   p r o po s e pr o t o c o l   O A M P S   w h e n   c o m pa r e w i t h   t h e   e xi s t i n g   m e t h o G O CE .   In  G O CE ,   r e duc e   t h e   s e n s o r   n o de   w i l l   b e   de a a l s o   a s   l o n g   a s   t h e r e   i s   r e s i du a l   e n e r gy ,   t h e   n e t w o r w o ul h a v e   a e nha n c e n e t w o r l i f e t i m e   i t h e   n e t w o r k.         4.   C O N C LU S I O N   In   t h i s   s c h e m e ,   w e   b ui l t h e   s pa nni n g ra p h   f o r   s c h e dul i n t h e   m o b i l e   s i n pa t h   t o   di s c ov e r   t h e   ob s t a c l e - a vo i di n s h o r t e s t   r o ut e .   T h i s   s c h e m e   m a ke s   t h e   ob s t a c l e   a v o i di n pa t h   s c h e dul i n du ri n s t a t i c   a n d   m o v i n o bs t a c l e .   H e r e ,   w e   a r e   us i n t h e   m o b i l e   s i n a n s up e r   n o de s   t o   i m pr o v i n t h e   n e t w o r l i f e t i m e .   T h e   s upe r   n o de   i s   a c t i n a s   a   m o b i l e   s i n da t a   g a t h e r i ng  po i nt   t hus   m i n i m i z e s   t h e   s e n s o r   e n e r gy   e xpe n di t u r e .   T h e   s o ur c e   s e l e c t s   t h e   n e x t   h o by   upda t e c uc koo   s e a r c h   a l g o r i t hm   h e n c e   r e duc e   t h e   n e t w o r de l a y .   In   t hi s   s c h e m e ,   t h e   s i m ul a t i o n   r e s ul t s   a r e   d o n e   by   n e t w o r s i m ul a t o r - 2 ,   a nd  r e s ul t s   de m o n s t r a t e   t ha t   i m p r o v e   t h e   t hr o ughput   a nd  r e duc e   t h e   n e t w o r de l a y .       R EF ER EN C ES     [ 1]   L .   M o r a r u ,   e t   al . ,   " G e o g r a phi c   R o ut i ng   w i t E a r l y   O bs t a c l e s   D e t e c t i o a nd  A v o i da nc e   i D e ns e   W i r e l e s s     S e ns o r   N e t w o r ks , "   I I n t e r na t i o nal   C o nf e r e nc e   on  A d - H o c   N e t w or k s   an W i r e l e s s ,   S pr i ng e r ,   B e r l i n ,   H e i d e l be r g ,   pp.   14 8 - 161,   2 008 .   [ 2]   C .   Y .   C ha ng ,   e t   al . ,   " O bs t a c l e - R e s i s t a n t   D e pl o y m e nt   A l g o r i t hm s   f o r   W i r e l e s s   S e n s o r   N e t w o r k s , "     I E E E   T r an s a c t i on s   o V e h i c u l a r   T e c hn ol ogy ,   v o l .   58 ,   no .   6,   pp .   292 5 - 2941,   2 009 .   [ 3]   W .   C .   C hu ,   a nd  K .   F .   S s u ,   " D e c e nt r a l i z e B o und a r y   D e t e c t i o W i t ho ut   L o c a t i o I n f o r m a t i o i W i r e l e s s     S e ns o r   N e t w o r k s ," I W i r e l e s s   C om m uni c a t i o ns   and  N e t w or k i ng  C on f e r e nc e   ( W C N C ) ,   2012  I E E E   pp.   17 20 - 1724 ,   201 2.   [ 4]   S .   D a s ,   e t   al . ,   " S e ns o r   L oc a l i z a t i o a nd  O bs t a c l e   B o unda r y   D e t e c t i o A l go r i t hm   i W S N , "   I A dv anc e s   i n   C om put i ng   an C om m un i c a t i ons   ( I C A C C ) ,   201 T hi r d   I n t e r na t i on al   C on f e r e nc e   on  I E E E ,   pp .   4 12 - 415 ,   201 3.   [ 5]   J .   W e i   a nd  D .   K undu r ,   " G o a l i e :   G o a l - S e e ki ng   O bs t a c l e   a n C o l l i s i o E v a s i o f o r   R e s i l i e nt   M u l t i c a s t   R o ut i ng     i S m a r t   G r i d , "   I E E E   T r an s ac t i ons   on   Sm ar t   G r i d ,   v o l .   7 ,   no .   2 ,   pp .   567 - 57 9,   20 16 .   [ 6]   H .   S a l a r i a n ,   e t   a l . ,   " A E ne r gy - E f f i c i e nt   M o bi l e - S i n P a t S e l e c t i o S t r a t e gy   f o r   W i r e l e s s   S e n s o r   N e t w o r k s , "     I E E E   T r an s a c t i on s   o v e hi c ul a r   t e c hno l o gy ,   v o l .   63 ,   no .   5 ,   pp .   240 7 - 2419,   2 014 .   [ 7]   W .   C .   C hu ,   a nd  K .   F .   S s u ,   " D e c e n t r a l i z e B o und a r y   D e t e c t i o w i t ho ut   L oc a t i o I nf o r m a t i o i W i r e l e s s     S e ns o r   N e t w o r k s , "   I n   W i r e l e s s   C om m uni c a t i o ns   and  N e t w or k i ng  C on f e r e nc e   ( W C N C ) ,   2012  I E E E   pp.   17 20 - 1724 ,   201 2.   [ 8]   S .   A .   S e bi ,   a nd  D .   S u nny " O bs t a c l e   A vo i da nc e   i M o bi l e   R o bo t i c   S e ns o r s   a nd  E s t a b l i s h i ng   C o nne c t i o n, "     P r o c e di a   T e c hno l o gy ,   vo l .   25 ,   pp .   364 - 37 1.   [ 9]   A .   B e l g hi t h,   e t   a l . ,   " A ut o no m i c   O bs t a c l e   D e t e c t i o a nd  A v oi da nc e   i n   M A N E T s   D r i v e by   C a r t o g r a ph   E nha nc e d   O L S R , "   M ob i l e   I n f or m at i on   Sy s t e m s ,   2015 .   [ 10]   H .   P .   G up t a ,   e t   al . ,   " G e o g r a phi c   R o ut i ng   i C l us t e r e W i r e l e s s   S e n s o r   N e t w o r ks   A m o n g   O bs t a c l e s , "   I E E E   Se ns or s   J our nal , v o l .   15,   no .   5 ,   pp.   2 984 - 292 2.   [ 11]   D .   Z h a ng , a n E .   D o ng ,   " A   V i r t ua l   C o o r di n a t e - B a s e B y pa s s i ng   V o i R o ut i ng   f o r   W i r e l e s s   S e ns o r   N e t w o r k s , "   I E E E   s e ns o r s   j our n al ,   v o l .   15 ,   no .   7,   pp .   385 3 - 3862 ,   2015 .   [ 12]   R . E l ha by a n,   W .   S h i ,   a n M .     S t - H i l a i r e ,   M .   A O b s t a c l e - A w a r e   C l us t e r i ng   P r o t o c o l   f o r   W i r e l e s s   S e n s o r   N e t w o r ks   w i t h   I r r e g ul a r   T e r r a i n ,     I nt e r n at i on al   C onf e r e nc e   on   W i r e d/ W i r e l e s s   I nt e r ne t   C om m un i c a t i on ,   S p r i ng e r ,   C ha m ,   p p.   54 - 66.   20 18.   [ 13]   G . M a ,   e t   a l . ,   O bs t a c l e   a w a r e   c o nne c t i v i t y   r e s t o r a t i o f o r   di s j o i nt   w i r e l e s s   s e ns o r   ne t w o r ks   us i ng   a   m i o f   s t a t i o na r y   a n m o bi l e   no de s ,   I nt e r n at i ona l   J o ur na l   of   D i s t r i bu t e Se ns or   N e t w or k s ,   v o l . 12 , no . 5 ,   pp . 64 6934 1, 2 016 .   [ 14]   L . S i t a na y a h,   e t   al . ,   A   f a ul t - t o l e r a n t   r e l a y   pl a c e m e nt   a l g o r i t hm   f o r   e ns ur i ng   v e r t e x - d i s j o i nt   s ho r t e s t   p a t hs   i n   w i r e l e s s   s e ns o r   ne t w o r ks ,   A d   H oc   N e t w or k s ,   v o l . 2 3,   pp . 1 45 - 162 , 2 014 .   [ 15]   A. A l o m a r i ,   e t   a l . ,     S w a r m   i nt e l l i g e nc e   o pt i m i z a t i o t e c hni que s   f o r   o bs t a c l e - a v o i da nc e   m o bi l i t y - a s s i s t e d   l o c a l i z a t i o i w i r e l e s s   s e ns o r   ne t w o r ks ”,   I E E E   A c c e s s v o l . 6,   pp . 2 2368 - 223 85 , 2018 .     Evaluation Warning : The document was created with Spire.PDF for Python.