I nte rna t io na l J o urna l o f   Ro bo t ics a nd   Aut o m a t io n   ( I J RA )   Vo l.   5 ,   No .   4 ,  Dec em b er   2 0 1 6 ,   p p .   25 5 ~ 2 61   I SS N:  2089 - 4856          255       J o ur na l ho m ep a g e :  h ttp : //ia e s jo u r n a l.c o m/o n lin e/in d ex . p h p /I J RA   Ancho r Mo v e m e nt  St ra tegy  f o r C o nject ur e  G eo m et ry  Ba sed  Lo ca liz a tion Sc he m e  in  W ireless  S e nso r Net w o rk       Nira j   B   K a pa s e,   Sa nt o s h Sa lg a r,   M a hes h K   P a t il,  P ra s ha nt  P   Z ir m it e   El e c tro n ics   De p a rtm e n t ,   DK T E’s  T e x ti le an d   En g i n e e rin g   In stit u te  Ic h a lak ra n ji ,   In d ia       Art icle  I nfo     AB ST RAC T   A r ticle  his to r y:   R ec eiv ed   Sep   1 9 ,   2 0 1 6   R ev i s ed   No v   8 ,   2 0 1 6   A cc ep ted   No v   21 ,   2 0 1 6       L o ca lizatio n   o f   s e n s o r   n o d e  w it h   lea s t  er r o r   is   o n e  o f   th e  m aj o r   co n ce r n   i n   w ir eles s   s e n s o r   n et w o r k   a s   s o m e  o f   th e   ap p licatio n   r eq u ir e   s en s o r   n o d e  to   k n o w   t h eir   lo c atio n   w it h   h i g h   d eg r ee   o f   p r ec is io n .   Fo r   m o b ile  a n ch o r   b ased   lo ca lizatio n   m a n y   o f   t h e  p ath   p lan n in g   s ch e m e s   alr ea d y   d ev e lo p ed   w h ich   i n c lu d es  s ca n ,   d o u b le  s ca n ,   C ir c les  &   S -   C u r v es.  T h ese  p ath   p la n n in g   s ch e m es  h a v e  s o m e  li m itat io n s   li k e   lo ca lizatio n   er r o r ,   Nu m b er   o f   s en s o r   n o d es  co v er ed   in   t h e   n et w o r k ,   T r a j ec to r y   le n g th   o f   m o b ile   an ch o r   n o d e.     T h is   p ap er   r ep r esen ts   an ch o r   m o v e m e n t  s tr ate g y   w h ic h   is   b ased   o n   Scan   p ath ,   w it h   m o d i f icat io n s   ar e  m ad e  in   s u ch   a  w a y   t h at  it  s ati s f ie s   th e   r eq u ir e m en ts   o f   lo ca lizatio n   s ch e m e.     T h is   m o v e m en t   s tr ateg y   en s u r es  t h at  tr aj ec to r y   o f   m o b ile  a n c h o r   n o d e  w i ll  m i n i m ize   lo ca lizatio n   er r o r   an d   also   w i ll  co v er   m aj o r it y   o f   s e n s o r   n o d e  in   th e   en v ir o n m e n t.  T h e  lo ca lizati o n   er r o r   y ield ed   b y   Mo d if ied   Scan   alg o r ith m   is   i n   th e  r a n g e  o f   0 . 2   to   0 . 4 m   w h ich   i s   q u ite  lo w e r   th an   t h e  o th er   ex i s ti n g   m e n tio n ed   p ath   p lan n i n g   s tr ate g ies  p r o d u cin g   lo ca lizatio n   er r o r   in   th e  r an g e  0 . 6   to   1 . 8 m .     K ey w o r d :   Lo ca lizatio n   Mo b ile  an ch o r   n o d e   Mo d if ied   s ca n   al g o r ith m   W ir eless   s en s o r   n et w o r k   Co p y rig h t  ©   201 6   In s t it u te o f  A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e .    Al l  rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   Nir aj   B   Kap ase,   E lectr o n ics De p ar t m e n t,    DKT E ’ s   T ex tile a n d   E n g in ee r in g   I n s ti tu te  I c h ala k r an j i,  I n d ia   E m ail:  n ir aj b k ap ase@ d k te s . co m       1.   I NT RO D UCT I O N   T h e  T A   W I R E L E S S  Se n s o r   Net w o r k   ( W SN)   co n s is t  o f   h u n d r ed s   o r   th o u s a n d s   o f   s e n s o r   n o d es  an d   a  s m all  n u m b er   o f   d ata  co llect io n   d ev ices [ 1 ] .   T h e  s en s o r   n o d es a r e  d esig n ed   to   ca r r y   o u t s en s i n g   ap p licatio n s   in cl u d in g   e n v ir o n m e n tal  m o n ito r in g ,   m ili tar y   s u r v eilla n ce ,   f ir e  d etec tio n ,   a n i m al  tr ac k i n g ,   a n d   s o   o n .   T h e   s en s o r   n o d es  g ath er   th e  i n f o r m atio n   o f   i n ter est  lo ca ll y   a n d   th en   f o r w ar d   th e  s e n s ed   in f o r m atio n   o v er   a   w ir ele s s   m ed i u m   to   a  r e m o t e  d ata  co llectio n   d ev ice  ( s in k ) , w h er e  it  is   f u s ed   a n d   an a l y ze d   in   o r d er   to   d eter m in e  t h e  g lo b al  s tatu s   o f   th e  s e n s ed   ar ea .   I n   s o m e  W SN  ap p licat io n s ,   th e  s en s o r   n o d es  ar e   r eq u ir ed   to   k n o w   t h eir   lo ca tio n s   w it h   a  h ig h   d eg r ee   o f   p r ec is io n ,   s u ch   as   tr ac k in g   o f   g o o d s ,   f o r est   f ir e   d etec tio n ,   an d   etc.   L o ca lizatio n   f ea tu r e  w o r k   is   ca r r ied   o u t   at  n et w o r k   la y er .   Ma n y   lo ca li za tio n   m et h o d s   h av e  b ee n   p r o p o s ed   f o r   W SNs .   Her e  w e  ar e   g o in g   to   d ea l  w it h   m o b ile   an c h o r   b ased   lo ca lizat io n   s c h e m e   w h ic h   b elo n g s   to   R an g e  f r ee   lo ca lizat io n   ca te g o r y .   I n   t h is   s c h e m e   th e  GP S - en ab led   m o b ile  a n c h o r   n o d e  n a v ig a te  in   s e n s i n g   f ield   a n d   h elp s   o t h er   s e n s o r   n o d e  to f i n d   th eir   lo ca tio n s .   Ag ai n   d if f er e n t  lo c aliza tio n   al g o r ith m s   ar e  t h er e  u n d er   m o b ile  a n ch o r   b ased   l o ca lizatio n .   Se v er al   an ch o r   m o v e m en t   s tr ate g ies  h av e  b ee n   p r o p o s ed   f o r   all  th es e  alg o r ith m .   A s   th e  a n c h o r   m o v e m e n t  s tr ateg y   is   d ev elo p ed co n s id er in g   s p ec i f i c  lo ca lizatio n   alg o r ith m ,   th eir   co m p atib ilit y   w it h   o th er   alg o r ith m   i s   n o t   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 9 - 4856   IJ RA    Vo l.   5 ,   No .   4 ,  Dec em b er   2 0 1 6 :   25 5   –   2 61   256   g u ar a n teed .   I n   s p ec if ic  w e   ar e  g o in g   to   d ea l  w it h   m o b ile  a n ch o r   b ased   lo ca lizatio n   s ch e m e  w h ich   i s   b ased   o n   co n j ec tu r e  g eo m etr y .   So   s tr aig h t  a w a y   w ec an ’ t  u s e  e x i s tin g   p at h   p lan n i n g   s tr ate g ie s   s u ch   a s   S C A N,   DOUB L E   SC AN,   HI L B E R T ,   S -   C UR VE S   w h ic h   ar e  alr ea d y   d ev elo p ed   f o r   o th er   lo ca li za tio n   s c h e m e  as   t h eir   co m p atib ilit y   w it h   co n j ec tu r e  g eo m etr y   b ased   lo ca lizat io n   is   n o t a s s u r ed .   SC A N   ca n n o t  g u ar an tee  th at   th e  le n g th   o f   ea ch   ch o r d   ex ce ed s   a  ce r tai n   t h r es h o ld .   DOU B L E   S C A N  ca u s es   en er g y   an d   b ea co n   o v er h ea d . HI L B E R T ca n n o t  g u ar a n tee  t h at  ev e r y   s en s o r   n o d e  w ill  o b ta in   t h e  t h r ee   o r   m o r e  b ea co n   p o in ts   r eq u ir ed   to   co n s tr u ct  t w o   ch o r d s   o f   t h e  co m m u n icatio n   cir cle.   I n   ca s e  o f   C I R C L E ,   t h e  p ath   len g th   is   e x te n d ed ,   an d   th e  en er g y   co n s u m p t io n   is   i n cr ea s ed .  I n   S - C U R VE S,  th e  tr aj ec to r y   o f   t h e  m o b ile  an ch o r   ca n n o t g u ar an tee  t h at  e ac h   s e n s o r   n o d e  ca n   co n s tr u ct  t w o   v alid   ch o r d s .   A cc o r d in g l y   t h is   p ap er   p r esen ts   a n ch o r   m o v e m e n t  s tr ateg y   w h ic h   i s   co m p atib le  w it h   Mo b ile  an c h o r   b ased   lo ca lizatio n   w h ich   i s b ased   o n   co n j ec tu r e  g eo m e tr y   [ 2 ] .   T h e  p r o p o s ed   s tr ateg y   is   m o d i f ied   f o r m   o f   ex is t in g   Scan   alg o r it h m   w h ic h   w a s   t h er e  f o r   s o m e  o t h er   l o ca lizatio n   s c h e m e.   T h e  m o d if icatio n s   ar e  m ad e   co n s id er in g   th e  m et h o d o lo g y   o f   lo ca lizatio n .       2.   L O CAL I Z A T I O N  SCH E M E   I n   th e  l o ca l iza ti o n   s ch em e  [ 3 ] ,   a  s in g le  m o b ile  an ch o r   n o d e  m o v es  r an d o m ly   th r o u g h   th e  s en s in g   f ield   b r o ad ca s t in g   p e r i o d ic  b e ac o n   m ess ag es  co n t ain in g   its   cu r r en t  c o o r d in ates .   Fig .   1   s h o w s   th e  lo ca l iz ati o n   s ch em e  b as e d   o n   p e r p en d icu l a r   b is ec t o r   o f   ch o r d .           Fig u r e  1 .   B ea co n   P o in ts   an d   C h o r d   C o n s tr u ctio n       T h e  l o c ati o n s   o f   th e   in d iv i d u al  s en s o r   n o d es  ar e  d e te r m in ed   b y   ex p l o it in g   th e  f a c t  th at   th e  p e r p en d icu l ar   b is e ct o r   o f   a  c h o r d   o f   a  ci r c le  p ass es  th r o u g h   th e  ce n ter   o f   th e  cir cle .   I t   is   ass u m ed   th at  th e  co m m u n icatio n   r an g e  o v er   w h ich   a  s en s o r   n o d e  ca n   d et ec t  b r o a d c asts   f r o m   th e  m o b il e  an ch o r   n o d e  is   b o u n d e d   b y   a  cir cle  an d   th e  s en s o r   n o d e  is   lo c ate d   at  th e  c en te r   o f   th is   cir cle .   A s   th e  an ch o r   n o d e  m o v es  th r o u g h   th e   s en s in g   f ield ,   it  b r o ad ca s ts   its   co o r d in ates  p e r i o d i ca l ly ,   an d   e ac h   s en s o r   n o d e  ch o o s es  a p p r o p r i at e  lo ca ti o n s   o f   th e  an ch o r   n o d e   ( ca l le d   b e ac o n   p o in ts )   t o   f o r m   ch o r d s   o f   i ts   co m m u n icati o n   ci r c le .   On c e  t h r ee   b ea co n   p o in ts   ( i . e .   tw o   ch o r d s )   h av e  b ee n   c o n s tr u ct ed ,   th e  s en s o r   n o d e  d et er m in es  it  lo c ati o n   b y   ca lcu la t in g   th e  in ter s e cti o n   p o in t  o f   th e  tw o   p e r p en d icu l ar   b is e ct o r s   o f   th e  ch o r d s . T h is   m eth o d   p r o v id es  a  c o m p u tati o n ally   s tr aig h tf o r w ar d   m ea n s   o f   d et er m in in g   th e  s en s o r   l o c ati o n s .     Ho w ev er ,   th e  a cc u r ac y   o f   th e  lo c ali za t io n   r esu lts   is   d ep en d en t  o n   th e  len g th   o f   th e  ch o r d s .   I n   r ea lis ti c   en v ir o n m en ts ,   th e  s elec te d   b ea co n   p o in ts   m ay   n o t b e  ex ac t  o n   th e  co m m u n icatio n   ci r cl e.   B ase d   o n   th e  au th o r s ’   o b s e r v ati o n ,   w h en   th e  len g th   o f   th e  ch o r d   is   t o o   s h o r t ,   th e  p r o b a b il ity   o f   u n s u cc ess f u l lo c ali z ati o n   w ill in cr ea s e   r a p i d ly .   T h u s ,   th e  au th o r s   s u g g este d   th at  th e  l en g th   o f   ea ch   ch o r d   s h o u ld   ex ce e d   a  c e r ta in   th r esh o l d   in   o r d er   t o   m in i m ize  th e  lo ca l iza ti o n   er r o r .   H o w ev er ,   in   th ese  s ch em e  th e  m o b ile  an ch o r   m o v es  r an d o m ly   th r o u g h   th e   s en s in g   f ield   ( i. e. ,   in   ac c o r d an ce   w ith   th e  R an d o m   W ay p o in t  m o d el ) ,   an d   th u s   it  is   p o s s ib le  th a t  s o m e  o f   th e   s en s o r   n o d es  ca n n o t  b e  l o c ali z ed .   T h e r ef o r e,   th e  m o d if ie d   s c an   alg o r ith m   p r o p o s e d   in   th is   s tu d y   is   s p ec if ica lly   d esig n e d   to   b o th   m in i m ize  th e   lo ca l iz ati o n   e r r o r   o f   th e  in d iv i d u al   s en s o r   n o d es   an d   t o   m ax im ize  th e  n u m b er   o f   s en s o r   n o d e s   w h ich   ca n   d ete r m in e  th eir   l o ca ti o n s .       3.   E XI ST I N G   P AT H   P L A NNI NG   S T RA T E G I E S   I n   th i s   s ec tio n ,   it  is   e x p lai n ed   th e  r esu lts   o f   r esear ch   an d   at  th e  s a m e  ti m e  is   g iv e n   t h e   co m p r e h en s iv e   d is c u s s io n .   R e s u lt s   ca n   b e  p r ese n ted   i n   f i g u r es,  g r ap h s ,   tab le s   a n d   o th er s   t h at  m a k e  t h e  r ea d er   u n d er s ta n d   ea s il y   [ 2 ] ,   [ 5 ] .   T h e  d is cu s s io n   ca n   b e  m ad e  in   s e v er al  s u b - c h ap ter s .     Evaluation Warning : The document was created with Spire.PDF for Python.
IJ RA   I SS N:  2089 - 4856       A n ch o r   Mo ve men t S tr a teg y  f o r   C o n jectu r e  Geo metry  B a s ed   Lo ca liz a tio n   S ch eme   in   ...    ( N ir a j B   K a p a s e )   257   3 . 1 .    Sca n   I n   SC A N,   th e  m o b ile   an ch o r   n o d e  t r av e ls   al o n g   a   s in g l e  d im en s io n   ( e . g .   th e  x - ax is   o r   y - ax is   d i r e cti o n ) ,   an d   th e  d is tan c e  b et w ee n   t w o   n eig h b o r in g   s eg m en ts   o f   th e  n o d e  t r a jec to r y   d ef in e s   th e  r es o lu ti o n   o f   th e  tr a j e ct o r y   [ 4 ] .   SC A N  is   s im p le  an d   p r o v i d es  u n if o r m   co v e r ag e  t o   th e  en ti r e  n etw o r k .   H o w ev er ,   th e   co l lin e ar i ty   o f   th e  b ea c o n s   d e g r a d es  th e  a cc u r ac y   o f   th e  lo c aliz ati o n   r esu lts .   SC A N  ca n n o t  g u ar an te e  th at  th e   len g th   o f   e ac h   ch o r d   ex ce ed s   a   ce r t ain   th r esh o l d .     3 . 2 .    Do ub le  Sca n   I n   DOU B L E   SC A N,   th e  c o l li n ea r ity   p r o b lem   is   r es o lv ed   b y   d r iv in g   th e  an ch o r   in   b o th   th e   x -   an d   th e   y - d ir ec ti o n s   [ 4 ] .   H o w ev er ,   w h ils t  th is   s t r ateg y   im p r o v es  th e  lo c ali za ti o n   p er f o r m an ce   o f   th e  s en s o r   n o d es,   th e  p ath   len g th   is   d o u b l ed   c o m p ar ed   t o   th at  o f   SC A N,   an d   t h u s   th e  en e r g y   o v e r h ea d   in c r ea s es   a cc o r d in g ly .   DOU B L E   SC A N  in cr ea s es   th e   b ea co n   o v er h e a d   d u e   t o   th e  g e n er a ti o n   o f   r e d u n d an t   b e ac o n   p o in ts .     3 . 3 .    H ilb er t   I n   H I L B E R T ,   th e   m o b il e  an ch o r   n o d e   is   d r iv en   al o n g   a      cu r v ed   tr a j e ct o r y   s u ch   th at   th e   s e n s o r   n o d es   ca n   c o n s t r u ct  n on - co l lin e ar   b ea c o n   p o in ts   an d   th e  to tal  p ath   len g th   is   r e d u c ed   [ 4 ] .   T h e  r esu lts   p r esen t e d   s h o w ed   th at  th r o u g h   an   ap p r o p r iat e  s ett in g   o f   th e  cu r v e d   t r a ject o r y   p ar am eter s ,   a  s ig n if ica n t  r e d u cti o n   in   th e   lo c ali za ti o n   e r r o r   co u l d   b e  o b t ain e d   c o m p a r e d   t o   th e  c ase   in   w h ich   th e  an ch o r   n o d e  s im p l y   m o v ed   r an d o m l y   th r o u g h   th e  s en s in g   f iel d .   H I L B E R T   c an n o t  g u a r an te e  th at   ev er y   s en s o r   n o d e  w ill  o b tai n   th e  th r ee   o r   m o r e   b e ac o n   p o in ts   r eq u i r e d   t o   co n s tr u ct   tw o   ch o r d s   o f   th e   c o m m u n icati o n   ci r c le .     3 . 4 .    Circ le   I n   C I R C L E S ,   th e  m o b il e  an ch o r   f o ll o w s   a  s eq u en ce   o f   co n c en tr i c  ci r cu l ar   t r a jec to r i es  ce n t er ed   a t  th e  ce n te r   p o in t   o f   th e  d e p l o y m en t  ar ea   [ 5 ] .   C I R C L E S c an   o n ly   g u ar an te e  th at  th e  f o u r   c o r n e r s   o f   th e  s en s in g   f i el d   ar e  c o v e r e d   b y   ex p an d in g   th e  d iam ete r   o f   th e  c o n ce n t r i c  c ir cles .   A s   a  r esu l t,  th e  p ath   l en g th   is   ex ten d e d ,   an d   th e  en er g y   c o n s u m p tio n   is   in c r ea s e d .     3 . 5 .    S - Curv es   I n   S - C UR VE S,  th e  an ch o r   f o llo w s   an   S - s h ap ed   cu r v e  r ath er   th an   a  s im p le  s t r aig h t  lin e   as  in   th e  SC A N  m eth o d   [ 5 ] .   T h e  r esu lts   s h o w ed   th at  g iv en   a  tr a ject o r y   r es o lu ti o n   m u ch   lar g er   th an   th e  r a d i o   r an g e ,   b o t h   C I R C L E   an d   S - C UR VE   s ch e m es  co p e  ef f ec tiv ely   w ith   th e   co ll in ea r ity   p r o b l em   an d   p r o v id e  a  s ig n if ic an tly   b et te r   l o c ali za t io n   ac cu r a cy   an d   c o v e r ag e   th an   p r ev i o u s   s o lu tio n s . I n   S - C UR VE S,  th e  t r a je cto r y   o f   th e  m o b i le   an ch o r   ca n n o t g u a r an t ee   th at   e ac h   s en s o r   n o d e   ca n   c o n s t r u ct   t w o   v al id   ch o r d s .       4.   M O DIFIE D  S CAN  A L G O R I T H M   I n   o r d e r   to   g et  at   le ast  th r e e  b ea c o n   p o in ts   o n   th e   c o m m u n i ca ti o n   ci r cl e  o f   s en s o r   n o d e   t o   f o r m   tw o   ch o r d s   it   is   n ec ess a r y   th at   an ch o r   n o d e  m u s t th r o u g h   ci r c le   a r ea   at   le ast   tw o   tim es.           Fig u r e  2 .   Mo d if ied   Scan   A l g o r ith m       In   th e  m o d if ied   Sca n   alg o r it h m   p r o p o s ed   in   th is   s t u d y ,   t h e  d is tan ce   b et w ee n   t w o   s u cc e s s i v e  v er tical   s eg m e n ts   o f   t h e  a n ch o r   tr aj ec to r y   ( i.e .   t h e  r eso l u tio n   o f   th e   a n ch o r   tr aj ec to r y )   i s   s p ec if ied   a s   R −X ,   w h er e  R   i s   th e  co m m u n icatio n   r ad iu s   o f   t h e  m o b ile   an c h o r   n o d e  a n d   X  is   s et   i n   t h e  r an g e  0   <  X  ≤   R /3 .   T h is   is   b ec a u s e  if   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 9 - 4856   IJ RA    Vo l.   5 ,   No .   4 ,  Dec em b er   2 0 1 6 :   25 5   –   2 61   258   X  is   b i g g er   t h a n   R /3 ,   R   −   X  w il l  b e  s m aller   t h a n   2 R /3 .   He n ce ,   t h e  d is ta n ce   b et w ee n   f o u r   s u cc es s i v e  v er tical   s eg m e n ts   is   le s s   t h an   t h e  d ia m eter   o f   th e  co m m u n icatio n   cir cle  ( i.e .   2 R ) .   A s   a  r esu l t,  th e  m o b ile  a n ch o r   n o d e   w il l  p ass   t h r o u g h   t h e  cir cle  m o r e  t h an   t h r ee   ti m es.  I n   o t h er   w o r d s ,   in cr ea s in g   t h e  v al u e  o f   X  m a y   i n cu r   r ed u n d an t  b ea co n   p o in t s .   C o n v er s el y ,   d ec r ea s i n g   th e  v al u e  o f   X  m a y   ca u s e  t h e  ch o r d   len g th   to   f all  b elo w   t h e  m i n i m u m   t h r es h o ld   v alu e.   T h u s ,   i n   p r ac tice,   a  ca r ef u l  ch o ic e  o f   X  is   r eq u ir ed .   T o   d eter m i n e  th e  p o s itio n s   o f   th e  s e n s o r   n o d es  clo s e  to   th e  b o u n d ar y   o f   t h e  s en s i n g   f ield ,   th e  d i m en s io n s   o f   t h e  f ield   ar e  v ir tu a ll y   e x te n d ed   b y   a  d is ta n ce   o f   R   o n   ea c h   s id e,   as  s h o w n   i n   Fi g . 2 .   B y   e x te n d in g   t h e  s en s i n g   f iel d ,   an d   ch o o s in g   a n   ap p r o p r iate  v alu e  o f   X,   th e  p r o p o s ed   p ath   p lan n in g   s c h e m e  en s u r es  t h at  th e  m o b ile  an ch o r   n o d e  p ass es   th r o u g h   t h e  cir cle  o f   ea c h   s en s o r   n o d e  eith er   t w o   o r   th r ee   ti m es.   As s h o w n   i n   Fi g u r e  2 ,   th e  to ta l p ath   len g t h   D  is   g iv e n   as       (         )   ( ⌈               ⌉     ) + (       )   ( ⌈               ⌉ )             ( 1 )     As  th e  eq u a tio n   ( 1 )   in d icate s ,   th e  to tal  p ath   le n g th   co n s is ts   o f   t w o   co m p o n en t s   i.e .   Ver tical  p ath   an d   Ho r izo n tal  p ath .   T h e  v er tical   p ath   co m p r is e s   ⌈               ⌉       s eg m e n ts   o f   len g t h   (         )   an d   h o r izo n tal  p at h   co m p r is e s   ⌈               ⌉   s eg m e n t s   o f   le n g t h (       ) .     T h is   m o d if ied   s ca n   alg o r it h m s   f o r   m o b ile  an ch o r   b ased   lo ca lizatio n   g u ar an tees  f o llo w in g   c o n d itio n s   I.   T h e  ch o r d   len g th   e x ce ed s   2 R / 3   II.   A ll  s en s o r   n o d es c an   d eter m i n e  t h eir   lo ca tio n     5.   O B ST ACL E   R E SI ST A NCE   ST RA T E G Y   I n   a  r ea lis tic  e n v ir o n m e n t,  o b s tacle s   m a y   ap p ea r   in   t h e  s en s i n g   f ie ld   an d   th u s   o b s tr u ct  th e  r ad io   co n n ec ti v it y   b et w ee n   th e  a n c h o r   n o d e  an d   th e  s en s o r   n o d es.  T h e  o b s tacle - r esis tan t  tr aj e cto r y   o f   th e  a n c h o r   n o d e  is   i n tr o d u ce d   in   Fig .   3 .   h en   th e  a n c h o r   n o d e  m o v i n g   a lo n g   t h e  p r o p o s ed   tr a j e cto r y   d i s co v er s   a n   o b s tacle , .   Af ter   d eto u r in g ,   t h e  an ch o r   n o d e  r etu r n s   to   t h e  o r i g in a l  p r o p o s ed   tr a j ec to r y .   Ho w e v er ,   th e  o b s tacle - r esis ta n t  tr aj ec to r y   m a y   ca u s e  th at  s e n s o r   n o d es  o b tai n   b ea co n   p o in ts   w h ic h   ar e  n o t  o n   th e  cir cl e.   T h e   lo ca lizatio n   p er f o r m a n ce   w ill  b e  d eg r ad ed   d u e  to   in co r r ec t b ea co n   p o in ts .           Fig u r e  3 . Ob s tacle   R esi s ta n ce   Stra teg y       6.   P E RF O RM ANE E VA L UA T I O N   T h e  p e r f o r m an ce   o f   th e  m o d if ied   s c an   alg o r ith m   is   ev alu at e d   b y   p e r f o r m in g   a  s er i es  o f   s i m u latio n s   o n   th e  ns - 2   n etw o r k   s im u lat o r   [ 6 ] .   T h e   s im u latio n   ca r r ie d   o u t   f o r   v a r y in g   v alu e  o f   X.   1)   T h e  lo ca l iza ti o n   er r o r :  th e  av e r ag e  d is c r e p an cy   b etw ee n   th e  esti m ated   s en s o r   n o d e  lo ca t io n   an d   th e  ac tu al   s en s o r   n o d e  lo ca ti o n   f o r   all   th e   s en s o r   n o d es ;   2)   T h e  p e r c en tag e   o f   l o c ali ze d   s e n s o r   n o d e :  th e   r at io   o f   th e   n u m b er   o f   s u cc ess f u lly   lo c ali ze d   s en s o r   n o d es   t o   th e  t o t al   n u m b er   o f   s en s o r   n o d es;   3)   T h e  ch o r d   l en g th : th e  av e r ag e   ch o r d   l en g th   c o n s t r u cte d   b y   th e  s en s o r   n o d es.   Fig u r e  4   il lu s tr ates  th e  l o c ali z ati o n   er r o r   o f   th e  p r o p o s ed   s ch em e  f o r   v ar io u s   v alu es  o f   X  in   th e  r an g e  0 . 0 5   t o   0 . 3   R .   I t  ca n   b e  s e en   th at  th e  lo ca l iza ti o n   er r o r   m ain tain s   a  c o n s tan t  v alu e  o f   j u s t  0 . 2   ∼   0 . 4 5   m   as  th e  v alu e  o f   X  is   in c r e ase d .   T h e  lo w   v alu e  o f   th e  lo c ali za t io n   er r o r   a r is es  b ec au s e  th e  m o d i f ied   s c an   alg o r i th m   g u ar an te es  th at  th e   len g th   o f   all  th e  ch o r d s   c o n s tr u c te d   b y   th e  s en s o r   n o d es  ex ce e d s   2 R / 3   p r o v i d e d   th at  th e  v alu e  o f   X   is   l ess   th an   R / 3 .   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ RA   I SS N:  2089 - 4856       A n ch o r   Mo ve men t S tr a teg y  f o r   C o n jectu r e  Geo metry  B a s ed   Lo ca liz a tio n   S ch eme   in   ...    ( N ir a j B   K a p a s e )   259       Fig u r e  4 .   L o ca lizatio n   E r r o r   ( in   m eter )   Vs X       Fig .   5   s h o w s   th at  t h e  av er a g e  ch o r d   len g th   r ed u ce s   w it h a n   in cr ea s i n g   v al u e  o f   X.   Fro m   i n s p ec tio n ,   th e  av er a g e  ch o r d   len g th   v ar ie s   b et w ee n   2 5 . 7   an d   2 8 . 9   m ,   an d   is   th er ef o r e  g r ea ter   th a n   2 R / 3 =  1 3 . 3 m .           Fig u r e  5 .   C h o r d   len g th   ( in   m eter )   Vs X       Fig .   6   co m p a r es  th e   av er ag e  l o c ali za t io n   er r o r s   o f   th e  s ix   p ath   p lan n in g   s ch em es  in   ea ch   o f   th e  f if ty   s im u latio n   r u n s .   I t c an   b e  s ee n   th at  w h en   th e  p r esen t e d   m o b il e  an ch o r   b ase d   l o c aliz ati o n   is   i m p lem en ted   u s in g   m o d if ied   s c an   alg o r ith m ,   th e  l o c ali za t io n   er r o r   h as  a  co n s t an t  v alu e   o f   a p p r o x im ately   0 . 2   m   an d   is   l o w er   th an   th at  ac h i ev ed   b y   an y   o f   th e   o th er   s ch em es.           Fig u r e  6 .   L o ca lizatio n   er r o r   o f   all  m o v e m e n t stra te g ies       Fig u r e   7   s h o w s   th e  av er ag e  ch o r d   l en g th   o f   th e  s ix   p ath   p lan n in g   s tr ateg i es  in   ea ch   o f   th e  f if t y   s im u latio n   r u n s .   T h e   ch o r d s   co n s t r u ct ed   b y   th e  s en s o r   n o d es   w h en   u s in g   th e  H I L B E R T   an d   S - C UR V E S   s tr a teg ies  ar e  s ig n if ican tly   lo n g er   th an   th o s e  o b ta in ed   w h en   u s in g   th e  DOUB L E   SC A N,   C I R C L E S  an d   r an d o m   m o v e m en t sch em es.  T h e  ch o r d   len g th   o b ta in ed   w h en   u s in g   th e  m o d if ie d   s c an   alg o r i th m   h as a   c o n s tan t  v alu e  o f   ar o u n d   2 8 . 5   m   an d   is   c o m p ar a b l e  t o   th a t  o b tai n ed   w h en   u s in g   th e  HI L B E R T   an d   S - C UR V E S   m eth o d s .   Of   th e  s ix   s ch em es,   t h e  C I R C L E S   s ch em e  r esu lts   i n   th e  s h o r test   ch o r d   l en g th .     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 9 - 4856   IJ RA    Vo l.   5 ,   No .   4 ,  Dec em b er   2 0 1 6 :   25 5   –   2 61   260       Fig u r e  7 .   C h o r d   len g th   f o r   all   m o v e m en t stra teg i es       Fig u r e   8   s h o w s   th e  p e r ce n tag e  o f   s u cc ess f u lly   lo ca liz e d   s e n s o r   n o d es  in   e ac h   s im u latio n   r u n   w h en   u s in g   th e  s ix   d if f er en t  p a th   p lan n in g   s tr ateg i es.   I t  is   o b s e r v ed   th at  th e  m o v em en t  s tr a te g y   p r o p o s e d   in   th is   s tu d y   en ab l es  al l  o f   th e   s en s o r s   to   d ete r m in e  th ei r   l o ca ti o n s   in   ev er y   s im u latio n   r u n .   I t  ca n   b e  s ee n   th a t  DOU B L E   SC A N  also   r esu lts   in   h ig h   lo ca l iz ati o n   p er f o r m an ce   ( i. e. ,   9 8 %  ∼   9 9 %) .   T h e  r e m ai n in g   m o v e m en t  s tr a teg ies ,   i . e . ,   H I L B E R T ,   S - C UR VE S,  C I R C L E S,  an d   th e  o r ig in al  r an d o m   m o v e m en t  s tr at eg y ,   r esu lt  in   av er ag e  lo ca liz ati o n   p e r ce n tag es  o f   8 2 % ,   9 1 % ,   8 2 %,   an d   7 9 %,  r es p e ctiv el y.           Fig u r e  8 .   P er ce n tag e  o f   lo ca liz ed   s en s o r   n o d e       Fig u r e  9   d ep icts   th e   av e r ag e   l o c ali za t io n   e r r o r s   o f   th e   o b s t a cle - f r ee   an d   th e   o b s t ac l e  en v ir o n m en ts   in   ea ch   o f   th e  f if ty   s im u latio n   r u n s . A lth o u g h   th e  v ir tu a l  b ea c o n   p o in t   g en e r at io n   is   p r o p o s ed   to   d ete r m in e  th e   lo c ati o n s   o f   s en s o r   n o d es ,   th e   esti m ated   p o s it io n   o f   th e  v ir t u al  b e ac o n   p o in t  m a y   n o t  b e  co r r ec tly   lo ca t ed   o n   th e  ci r c le  an d   th u s   in cu r s   m o r e  e r r o r s   o n   l o c ali za t io n .   I t  ca n   b e  s ee n   th at  th e  l o c ali za t io n   e r r o r   o f   th e   o b s t ac le - f r ee   en v i r o n m en t k ee p s   a b o u t  0 . 2   m   an d   th e  o b s t ac l e  en v ir o n m en t h as a   lo ca l iz ati o n   er r o r   b etw ee n   0 . 6   t o   0 . 8 m.           Fig u r e  9 . L o ca lizatio n   er r o r   f o r   Ob s tacle   Fre e  an d   Ob s tacle   E n v ir o n m e n t ( i n   m eter )   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ RA   I SS N:  2089 - 4856       A n ch o r   Mo ve men t S tr a teg y  f o r   C o n jectu r e  Geo metry  B a s ed   Lo ca liz a tio n   S ch eme   in   ...    ( N ir a j B   K a p a s e )   261   Fig u r e  1 0   s h o w s   th at  th e  av e r ag e  ch o r d   l en g th   o f   th e  o b s t ac le - f r e e  an d   th e  o b s ta cle   en v ir o n m en ts   in   ea ch   o f   th e  f if ty   s im u latio n   r u n s .   T h e   av e r ag e  ch o r d   len g th   o f   th e   o b s t ac le  en v ir o n m en t  v ar i es  b e tw ee n   2 9 . 5   an d   3 0 . 8   m   an d   is   la r g e r   th an   t h at  o f   th e   o b s ta cle - f r ee   en v i r o n m en t           Fig u r e  1 0 .   C h o r d   len g t h   o f   o b s tacle   f r ee   a n d   o b s tacle   en v ir o n m e n t   ( i n   m e ter )       7.   CO NCLU SI O N   I n   th i s   p ap er ,   w e  h av e  p r ese n t ed   an ch o r   m o v e m e n t  s tr ate g y   m o d i f ied   s ca n   alg o r it h m   f o r   th e  m o b ile   an ch o r   n o d e  in   t h e  lo ca lizatio n   m et h o d   b ased   o n   co n j ec tu r e  g eo m etr y .   T h is   al g o r ith m   en s u r es  th a t  th e  ch o r d s   co n s tr u cted   b y   t h e  i n d iv id u al   s en s o r   n o d es  al w a y s   h a v e  a  len g th   g r ea ter   th a n   2 R /3 .   T h u s ,   t h e  s h o r t  ch o r d   p r o b lem   is   i s   r eso lv ed .   B esid es,  th e  m o d i f ied   m o v e m e n t  tr aj ec to r y   an d   th e  v ir tu al  b ea co n   p o in t  g e n er atio n   s ch e m e  ar e  p r esen ted   to   to ler ate  th e  o b s tacle s   i n   th e  s e n s i n g   f ield .   T h e  p er f o r m a n ce   o f   th e  m o d if ied   s ca n   alg o r ith m   is   co m p ar ed   n u m er icall y   w it h   th at  o f   f i v e  ex i s ti n g   p ath   p la n n i n g   s ch e m es,  n a m el y   DOUB L E S C A N,   C I R C L E S,  S - C UR VE S,  HI L B E R T ,   an d   th e  o r ig i n al  r an d o m   m o v e m en t  s tr ateg y .   Ov er all ,   th e  s i m u latio n   r esu l ts   h av e  s h o w n   th at  t h e  m o d i f ied   s ca n   al g o r ith m   o u tp er f o r m s   e x is t in g   m et h o d s   in   ter m s   o f   b o th   a  s m aller   lo ca lizat io n   er r o r   an d   a  h ig h er   p er ce n ta g e  o f   s u cc es s f u l l y   lo ca lized   s en s o r   n o d es.  T h e  lo ca lizatio n   er r o r   y ield ed   b y   Mo d if ied   Scan   alg o r it h m   is   in   th e  r an g e  o f   0 . 2   to   0 . 4 m   w h ic h   is   q u ite  lo w er   th a n   th e  o th er   ex is ti n g   m e n tio n ed   p ath   p lan n i n g   s tr ateg ie s   p r o d u cin g   lo ca liza tio n   er r o r   in   th e  r a n g e  0 . 6   to   1 . 8 m       8.   F UT UR E   SCO P E   T h e  im p r o v e m en t  in   ch o r d   len g t h   v ar iat io n   f o r   o b s tacle   en v ir o n m en t  ca n   b e  ac h iev ed   with   f u r t h er   m o d i f icat io n   i n   B ea co n   p o in t selec tio n   m ec h an i s m .       RE F E R E NC E S   [1 ]   I.   F .   A k y il d iz,  W .   S u ,   Y.  S a n k a ra su b ra m a n ia m ,   a n d   E.   Ca y irci,   " A   su rv e y   o n   se n so r  n e tw o rk s,"   IEE E  Co mm u n .   M a g . ,   v o l .   4 0 ,   n o .   8 ,   p p .   1 0 2 - 1 1 4 ,   A u g u e st 2 0 0 2 .   [2 ]   Ch ia - Ho   Ou ,   M e m b r,   IEE E,   a n d   W e i - L u n   He ,   " P a th   P lan n i n g   A lg o rit h m   f o r  M o b il e           A n c h o r - Ba se d   L o c a li z a ti o n   in   W irele ss   S e n so r  Ne tw o rk s,"   IE EE   S e n s o rs   J o u r n a l ,   v o l.   1 3 ,   n o .   2 ,   p p .   4 6 6 - 4 7 5 ,   F e b ru a ry   2 0 1 3 .   [3 ]   C.   H.  Ou ,   a n d   H.  C.   Jia u   K.  F .   S su ,   " L o c a li z a ti o n   w it h   m o b il e   a n c h o r  p o i n ts  i n   w irele ss   se n so r  n e tw o rk s, "   IEE E  T ra n s.  Veh .   T e c h n o l ,   v o l .   5 4 ,   n o .   3 ,   p p .   1 1 8 7 – 1 1 9 7 ,   M a y   2 0 0 5 .   [4 ]   S .   M .   Da s,  a n d   Y.  C.   Hu   D.  Ko u tso n ik o las ,   " P a t h   p lan n in g   o f   m o b il e   lan d m a rk s   f o r  lo c a li z a ti o n   in   w irele ss   se n so r   n e tw o rk s,"   Co m p u t.   Co m m u n ,   v o l.   3 0 ,   n o .   1 3 ,   p p .   2 5 7 7 – 2 5 9 2 ,   se p t.   2 0 0 7 .   [5 ]   R.   Hu a n g   a n d   G .   V .   Zaru b a ,   St a ti c   p a t h   p la n n i n g   fo r  m o b il e   b e a c o n s  to   lo c a li ze   se n so r  n e tw o rk s ,   in   P ro c .   I EE E  I n t .   Co n f .   P e rv a s.  Co m p u t.   Co m m u n .   W o rk sh o p s,  M a r.   2 0 0 7 ,   p p .   3 2 3 – 3 3 0 .   [6 ]   " T h e   Ne t w o rk   S i m u lato r  -   ns - 2 , "   h tt p : // ww w . isi. e d u /n s n a m /n s/,  (2 0 1 2 ).       Evaluation Warning : The document was created with Spire.PDF for Python.