I n t e r n a t i o n a l   J o u r n a l   o f   E l e c t r i c a l   a n d   C o m p u t e r   E n g i n e e r i n g   ( I J E C E )   V o l . 2 ,   N o . 4 ,   A u g u s t   2 0 1 2 ,   p p .   4 5 2 ~ 4 5 5   I S S N :   2 0 8 8 - 8 7 0 8             4 5 2       J o u r n a l   h o m e p a g e :   h t t p : / / i a e s j o u r n a l . c o m / o n l i n e / i n d e x . p h p / I J E C E   F u n d a m e n t a l   M e t r i c 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   l o c a l i z a t i o n       J a v a d   R e z a z a d e h ,   M a r j a n   M o r a d i ,   A b d u l   S a m a d   I s m a i l   D e p a r t m e n t   o f   Co m p u t e r   S y s t e m s   a n d   C o m m u n i c a t i o n ,   U n i v e r s i t i   T e k n o l o g i   M a l a y s i a   U T M ,   8 1 3 1 0 ,   J o h o r ,   M a l a y s i a   e - m a i l :   { r e z a z a d e h ,   M a r j a n } @ l i v e . u t m . m y   ,   a b d s a m a d @ u t m . m y       A r t i c l e   I n f o     A B S T R A C T     A r t i c l e   h i s t o r y :   R e c e i v e d   J a n   3 1 ,   2 0 1 2   R e v i s e d   J u l   1 7 ,   2 0 1 2   A c c e p t e d   J u l   2 6 ,   2 0 1 2       D u r i n g   t h e   l a s t   d e c a d e ,   L o c a l i z a t i o n   i n   w i r e l e s s   s e n s o r   n e t w o r k s   ( W S N s )   i s   a   b r o a d   t o p i c   t h a t   h a s   r e c e i v e d   c o n s i d e r a b l e   a t t e n t i o n   f r o m   t h e   r e s e a r c h   c o m m u n i t y .   T h e   a p p r o a c h e s   s u g g e s t e d   t o   e s t i m a t e   l o c a t i o n   a r e   i m p l e m e n t e d   w i t h   d i f f e r e n t   c o n c e p t s ,   f u n c t i o n a l i t i e s ,   s c o p e s   a n d   t e c h n o l o g i e s .   T h i s   p a p e r   i n t r o d u c e s   a   m e t h o d o l o g i c a l   a p p r o a c h   t o   t h e   e v a l u a t i o n   o f   l o c a l i z a t i o n   a l g o r i t h m s   a n d   c o n t a i n s   a   d i s c u s s i o n   o f   e v a l u a t i o n   c r i t e r i a   a n d   p e r f o r m a n c e   m e t r i c s   f o l l o w e d   b y   s t a t i s t i c a l /   e m p i r i c a l   s i m u l a t i o n   m o d e l s   a n d   m e t r i c s   t h a t   a f f e c t   t h e   p e r f o r m a n c e   o f   t h e   a l g o r i t h m s   a n d   h e n c e   t h e i r   a s s e s s m e n t .   T h e   m a j o r   c o n t r i b u t i o n   o f   t h i s   p a p e r   i s   t o   a n a l y z e   a n d   i d e n t i f y   r e l e v a n t   m e t r i c s   t o   c o m p a r e   d i f f e r e n t   a p p r o a c h e s   o n   t h e   e v a l u a t i o n   o f   l o c a l i z a t i o n   s c h e m e s .   K e y w o r d :   E v a l u a t i o n   L o c a l i z a t i o n   M e t r i c s   W i r e l e s s   S e n s o r   N e t w o r k s     Co p y r i g h t   ©   2 0 1 x   I n s t i t u t e   o f   A d v a n c e d   E n g i n e e r i n g   a n d   S c i e n c e .     A l l   r i g h t s   r e s e r v e d .   C o r r e s p o n d i n g   A u t h o r :   J a v a d   R e z a z a d e h ,     D e p a r t m e n t   o f   Co m p u t e r   S y s t e m s   a n d   C o m m u n i c a t i o n ,   U n i v e r s i t i   T e k n o l o g i   M a l a y s i a ,   U T M ,   8 1 3 1 0 ,   J o h o r ,   M a l a y s i a .   E m a i l :   r e z a z a d e h @ l i v e . u t m . m y         1 .   I N T R O D U C T I O N     A   W i r e l e s s   S e n s o r   N e t w o r k   ( W S N )   i s   f o r m e d   b y   h u n d r e d s   o f   s m a l l ,   l o w - c o s t   n o d e s   w h i c h   h a v e   l i m i t a t i o n s   i n   m e m o r y ,   e n e r g y ,   a n d   p r o c e s s i n g   c a p a c i t y   [ 1 ] .   I n   t h i s   t y p e   o f   n e t w o r k s ,   o n e   o f   t h e   m a i n   p r o b l e m s   i s   t o   l o c a t e   e a c h   n o d e .   T h e   v i s i o n   o f   m a n y   r e s e a r c h e r s   i s   t o   c r e a t e   s m a r t   e n v i r o n m e n t s ,   c o n t r o l l e d   t h r o u g h   p l a n n e d   o r   a d - h o c   d e p l o y m e n t   o f   a   p o t e n t i a l l y   l a r g e   s e t   o f   s e n s o r   n o d e s ,   e a c h   w i t h   t r a n s c e i v e r s   f o r   w i r e l e s s ,   s h o r t - r a n g e   c o m m u n i c a t i o n ,   c a p a b l e   o f   d e t e c t i n g   e n v i r o n m e n t   c o n d i t i o n s   s u c h   a s   t e m p e r a t u r e ,   m o v e m e n t ,   l i g h t ,   a c o u s t i c   e v e n t s   o r   t h e   p r e s e n c e   o f   c e r t a i n   o b j e c t s .   W S N   w i l l   e n a b l e   f i n e - g r a i n e d   o b s e r v a t i o n   a n d   c o n t r o l   o f   t h e   p h y s i c a l   w o r l d .   T h e   f u t u r i s t i c   s c e n a r i o   i n   s e n s o r   n e t w o r k s   a p p e a r s   i n   l a r g e   n u m b e r s   o f   u n a t t e n d e d   a u t o n o m o u s   n o d e s   w h i c h   o p e r a t e   i n   a   d y n a m i c   e n v i r o n m e n t .   T h i s   k i n d   o f   s e n s o r   w i l l   b e   a b l e   t o   o r g a n i z e   i t s e l f .   I t   w i l l   b e   a w a r e   o f   i t s   p h y s i c a l   p o s i t i o n .   T h e   s e n s o r   n o d e s   w i l l   c a r r y   o u t   d y n a m i c   t a s k s   i n   a   d i s t r i b u t e d   f o r m ,   v e r y   f r e q u e n t l y   c o n f r o n t i n g   c h a n g e   i n   t h e   t o p o l o g y   n e t w o r k   a n d   f a i l u r e s   i n   t h e   n e t w o r k   n o d e s   d u e   t o   t h e   l a c k   o f   p o w e r ,   p h y s i c a l   d a m a g e   o r   e n v i r o n m e n t a l   i n t e r f e r e n c e s .   T h e s e   n o d e s   w i l l   r e p o r t   e n v i r o n m e n t   e v e n t s   l i k e   t e m p e r a t u r e ,   p r e s s u r e ,   h u m i d i t y ,   v e h i c u l a r   m o v e m e n t ,   n o i s e   l e v e l s ,   l i g h t i n g   c o n d i t i o n s ,   t h e   p r e s e n c e   o r   a b s e n c e   o f   c e r t a i n   k i n d s   o f   o b j e c t s ,   a c o u s t i c   e v e n t s ,   a n d   m e c h a n i c a l   s t r e s s   l e v e l s   o n   a t t a c h e d   o b j e c t s ,   a n d   s o   o n .   W e   c a n   s a y   t h a t   l o c a l i z a t i o n   w i l l   a c t   a s   a   b r i d g e   b e t w e e n   t h e   v i r t u a l   a n d   p h y s i c a l   w o r l d   [ 2 ] .   E v a l u a t i n g   t h e   r e l a t i v e   p e r f o r m a n c e   o f   l o c a l i z a t i o n   a l g o r i t h m s   i s   i m p o r t a n t   f o r   r e s e a r c h e r s ,   e i t h e r   w h e n   v a l i d a t i n g   a   n e w   a l g o r i t h m   a g a i n s t   t h e   p r e v i o u s   s t a t e   o f   t h e   a r t ,   o r   w h e n   c h o o s i n g   e x i s t i n g   a l g o r i t h m s   w h i c h   b e s t   f i t   t h e   r e q u i r e m e n t s   o f   a   g i v e n   W S N   a p p l i c a t i o n .   H o w e v e r ,   t h e r e   i s   a   l a c k   o f   u n i f i c a t i o n   i n   t h e   W S N   f i e l d   i n   t e r m s   o f   l o c a l i z a t i o n   a l g o r i t h m   e v a l u a t i o n   a n d   c o m p a r i s o n .   I n   a d d i t i o n ,   n o   s t a n d a r d   m e t h o d o l o g y   e x i s t s   t o   t a k e   a n   a l g o r i t h m   t h r o u g h   m o d e l i n g ,   s i m u l a t i o n   a n d   e m u l a t i o n   s t a g e s ,   a n d   i n t o   r e a l   d e p l o y m e n t .   A s   a   r e s u l t   i t   c a n   b e   h a r d   t o   q u a n t i f y   e x a c t l y   h o w   a n d   u n d e r   w h a t   c i r c u m s t a n c e s   o n e   a l g o r i t h m   i s   b e t t e r   t h a n   a n o t h e r .   M o r e o v e r ,   d e c i d i n g   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I S S N :   2 0 8 8 - 8 7 0 8         F u n d a m e n t a l   M e t r i c 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   l o c a l i z a t i o n   ( R e z a z a d e h   J )   4 5 3 w h a t   p e r f o r m a n c e   c r i t e r i a   l o c a l i z a t i o n   a l g o r i t h m s   a r e   t o   b e   c o m p a r e d   o r   e v a l u a t e d   a g a i n s t   i s   i m p o r t a n t   f o r   t h e   s u c c e s s   o f   t h e   r e s u l t i n g   i m p l e m e n t a t i o n   g i v e n   t h a t   d i f f e r e n t   a p p l i c a t i o n s   w i l l   h a v e   d i f f e r i n g   n e e d s .   S i n c e   l o c a l i z a t i o n   a l g o r i t h m s   a r e   e x p e c t e d   t o   b e   u s e d   i n   r e a l   a p p l i c a t i o n s ,   i t   i s   n o t   c o n c l u s i v e   t o   v e r i f y   t h e i r   p e r f o r m a n c e   i n   s i m u l a t i o n   o n l y .       2 .   L M P O R T A N C E   O F   L O C A L I Z A T I O N   S e n s o r s   a r e   u s e d   f o r   g a t h e r i n g   e n v i r o n m e n t a l   d a t a   s u c h   a s   t e m p e r a t u r e ,   p r e s s u r e ,   h u m i d i t y ,   r a d i o s i t y .   T h e   c o l l e c t e d   d a t a   a s s i s t   i n   p r e d i c t i n g   l i k e l y   o c c u r r e n c e   o f   e v e n t s   s u c h   a s   b u s h   f i r e ,   r a d i o - a c t i v e   l e a k s ,   f a i l u r e s   i n   s t r u c t u r e s ,   a n d   m a n y   o t h e r   i m p e n d i n g   d i s a s t e r s   i n c l u d i n g   e a r t h q u a k e s ,   f l o o d s ,   a n d   w e a t h e r   c h a n g e s .   E a r l y   p r e d i c t i o n   o f   s u c h   e v e n t s   h e l p s   i n   p l a n n i n g   a d e q u a t e   r e s p o n s e   s y s t e m   t h a t   m a y   e i t h e r   p r e v e n t   t h o s e   e v e n t s   o r   m i t i g a t e   t h e   c o n s e q u e n t i a l   d a m a g e s .   T h e   r e s p o n s e   s y s t e m   s h o u l d   h a v e   t h e   a b i l i t y   t o   e x t r a c t   c o n t e x t   f r o m   t h e   g a t h e r e d   s e n s o r y   d a t a   i f   i t   w e r e   t o   p r e d i c t   t h e   e v e n t s   c o r r e c t l y   a n d   o p e r a t e   a t   t h e   e x p e c t e d   l e v e l   o f   e f f i c i e n c y .   A   c o n t e x t   i s   d e f i n e d   b y   a m b i e n c e s   a m o n g   w h i c h   l o c a t i o n   ( b o t h   s p a t i a l   a n d   t e m p o r a l )   i s   t h e   m o s t   c r i t i c a l   i n g r e d i e n t   [ 3 ] .   W S N s   w i t h   s e n s i n g   c a p a b i l i t i e s   c a n   g a t h e r   v i t a l   s e c u r i t y - r e l a t e d   m e t r i c s   s u c h   a s   r a d i o   c o m m u n i c a t i o n ,   s i g n s   o f   a c c e l e r a t e d   a c t i v i t i e s ,   o r   v i g o r o u s   m o v e m e n t s   i n   a n   a r e a   t o   a i d   i n   d e v e l o p i n g   a   s e c u r i t y   r e s p o n s e   a n d   a d v a n c e d   w a r n i n g   s y s t e m .   B u t   t h e s e   s e n s e d   m e t r i c s   a r e   u s e l e s s   u n l e s s   t h e y   a r e   a c c o m p a n i e d   b y   c o r r e s p o n d i n g   l o c a t i o n   i n f o r m a t i o n .   A l t h o u g h   l o c a t i o n   i n f o r m a t i o n   c a n   b e   f e d   m a n u a l l y ,   i t   m a y   n o t   b e   f e a s i b l e   i n   a   l a r g e   d e p l o y m e n t   a r e a .   S o   i t   i s   n e c e s s a r y   t o   d e v e l o p   a   s y s t e m   t h a t   c a n   a u t o m a t i c a l l y   u p d a t e   l o c a t i o n   i n f o r m a t i o n   o f   a l l   n o d e s   i n   t h e   d e p l o y m e n t   a r e a .   N a v i g a t i o n   a n d   v e h i c l e   t r a c k i n g   i s   a n o t h e r   a r e a   w h e r e   t h e   u s e   o f   W S N s   i s   f o u n d   t o   b e   e x t r e m e l y   u s e f u l .   V e h i c l e   t r a c k i n g   w i t h   a u t o n o m o u s   i n t e r c e p t i o n   m e c h a n i s m   c a n   b e   d e p l o y e d   i n   a n   o u t d o o r   a r e a .   I t   s e n s e s   e n t r y   a s   w e l l   a s   m o v e m e n t   o f   a n   o f f e n d i n g   e v a d e r   i n   t h e   a r e a .   A   c o o p e r a t i v e   m o b i l e   a g e n t   m a y   b e   d i s p a t c h e d   f o r   i n t e r c e p t i n g   t h e   e v a d e r   a s   s o o n   i t   g e t s   d e t e c t e d   b e f o r e   a n y   d a m a g e   i s   d o n e .   T h e   s u c c e s s f u l   r e a l i z a t i o n   o f   s u c h   a   t r a c k i n g   a n d   i n t e r c e p t i o n   s y s t e m   i s   d e p e n d e n t   o n   t h e   l o c a t i o n   i n f o r m a t i o n   i n   t w o   t i e r s .   F i r s t ,   t h e   s e n s o r s   m u s t   b e   a b l e   t o   d e t e c t   t h e   e v a d e r   a s   s o o n   a s   i t   e n t e r s   t h e   a r e a   a n d   b e   a b l e   t o   t r a c k   i t   w h i l e   t h e   e v a d e r   c o n t i n u e s   t o   m o v e   a r o u n d   i n   t h e   a r e a   u n d e r   o b s e r v a t i o n .   S e c o n d ,   t h e   u p d a t e   o n   t h e   l o c a t i o n   i n f o r m a t i o n   o f   t h e   e v a d e r   m u s t   b e   r o u t e d   t o   i n t e r c e p t i n g   m o b i l e   a g e n t   s o   l o n g   a s   i t   c o n t i n u e s   t o   p u r s u e   t h e   e v a d e r .   A p a r t   f r o m   c o n t e x t - r e l a t e d   c o m p u t a t i o n s   i n   a p p l i c a t i o n   l e v e l   t a s k s   d i s c u s s e d   a b o v e ,   t h e   k n o w l e d g e   o f   s e n s o r   l o c a t i o n s   i s   a l s o   e s s e n t i a l   f o r   n e t w o r k   l e v e l   o p e r a t i o n s   i n   W S N s .   I n   t h i s   p a p e r ,   w e   a t t e m p t   t o   r e v i e w   t h e   e x i s t i n g   l i t e r a t u r e   w i t h   e m p h a s i s   o n   t h e   m e t r i c   o f   s e n s o r   l o c a l i z a t i o n   t e c h n i q u e s .       3 .   M E T R I C S   I N   L O C A L I Z A T I O N   F o r   t h e   d i f f e r e n t   w a y s   o f   e s t i m a t i n g   l o c a t i o n   i n f o r m a t i o n ,   w e   h a v e   t o   n a m e   m e t r i c s   t o   d i s t i n g u i s h   t h e   s i m i l a r i t i e s   a n d   d i v e r g e n c e s   b e t w e e n   d i f f e r e n t   a p p r o a c h e s .   I n   t h i s   s e c t i o n   w e   p r e s e n t   t h e   m o s t   t y p i c a l   m e t r i c s   t o   c l a s s i f y   d i f f e r e n t   t e c h n i q u e s .     3 . 1 .     L o c a l i z a t i o n   A c c u r a c y   T h e   m o s t   i m p o r t a n t   m e t r i c   f o r   l o c a l i z a t i o n   t e c h n i q u e s   i s   a c c u r a c y   a n d   p r e c i s i o n   [ 3 ] .   W e   c a n   d e f i n e   a c c u r a c y   a s   h o w   m u c h   t h e   e s t i m a t e d   p o s i t i o n   d e v i a t e d   f r o m   t h e   t r u e   p o s i t i o n   i s .   P r e c i s i o n   i n d i c a t e s   h o w   o f t e n   w e   e x p e c t   t o   g e t   a t   l e a s t   t h e   g i v e n   a c c u r a c y   f o r   e x a m p l e   2 0   c m   a c c u r a c y   a c r o s s   9 5 %   o f   t h e   t i m e .   A c c u r a c y   o f   e s t i m a t e d   l o c a t i o n s   o b t a i n e d   f r o m   v a r i o u s   l o c a l i z a t i o n   s c h e m e s .   A c c o r d i n g   t o   t h e   l o c a l i z a t i o n   p r o c e s s ,   t h e   s o u r c e s   o f   l o c a l i z a t i o n   e r r o r   m a y   i n c l u d e   p h y s i c a l   s o u r c e s ,   l o c a l i z a t i o n   a l g o r i t h m s ,   a n d   r e f i n e m e n t   p r o c e s s   [ 4 ,   5 ] .   T h e   e r r o r s   d u e   t o   p h y s i c a l   s o u r c e s   a r e   r e p r e s e n t e d   b y   w i d e   r a n g e   o f   n o i s e s   a n d   q u a n t i z a t i o n   l o s s e s .   R a n g i n g   t e c h n i q u e s   v a r y   f r o m   u l t r a s o n i c   t o   r a d i o ,   a n d   t o   l a s e r ,   e t c .   A   s u m m a r y   o n   t h e   r a n g e   a c c u r a c y   w a s   p r e s e n t e d   i n   [ 6 ] .   T h e   m o s t   a t t r a c t i v e   a m o n g   s i m u l a t i o n s   a r e   t h e   o n e s   w i t h   l o w - c o s t   a n d   r e a d y - t o - u s e   f e a t u r e s   l i k e   t i m e   o f   a r r i v a l   ( T O A )   o f   u l t r a s o n i c   s i g n a l   a n d   r a d i o   s i g n a l   s t r e n g t h   ( R S S )   o r   r a d i o   s i g n a l   s t r e n g t h   i n d i c a t i o n   ( R S S I ) .   T h e   o n l y   c o n c e r n   a b o u t   t h e s e   t e c h n i q u e s   i s   t h a t   t h e y   p r o d u c e   h i g h l y   n o i s y   m e a s u r e m e n t s   a n d   a r e   o v e r   s e n s i t i v e   t o   e n v i r o n m e n t a l   e f f e c t s   [ 7 ] .   L o c a l i z a t i o n   a l g o r i t h m s   e n c o u n t e r   t w o   t y p e s   o f   e r r o r   s o u r c e s .   O n e   i s   s y s t e m   e r r o r ,   w h i c h   c o m e s   f r o m   t h e   l o c a l i z a t i o n   a l g o r i t h m s   t h e m s e l v e s   t h a t   w o r k   w i t h   u n d e r l y i n g   a s s u m p t i o n   o f   a c c u r a t e   r a n g e   m e a s u r e m e n t   o r   r a n g e - f r e e   f e a t u r e s .   T h e   o t h e r   s o u r c e   o f   e r r o r   i s   r e l a t e d   t o   c o n n e c t i v i t y   a n d   t h e   f r a c t i o n   o f   n o d e s   s e r v i n g   a s   a n c h o r s .   T h e   l a s t   t w o   m e t r i c s   h a v e   s i g n i f i c a n t   i m p a c t s   o n   t h e   p e r f o r m a n c e   o f   l o c a l i z a t i o n   a l g o r i t h m s .   T h e   e f f e c t   o f   s y s t e m   e r r o r   b e c o m e s   m a n a g e a b l e ,   w h e n   b o t h   d i s t a n c e   a n d   a n g l e   w i t h   o r i e n t a t i o n   a r e   a v a i l a b l e .   B u t   t h e   s i z e   a n d   t h e   c o s t   o f   t h e   h a r d w a r e   c a p a b l e   o f   m e a s u r i n g   d i s t a n c e   a n d   a n g l e   p r e v e n t   s u c h   s y s t e m   f r o m   i m p l e m e n t a t i o n ,   e s p e c i a l l y   f o r   d e n s e   W S N s   [ 8 ] .   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 8 - 8 7 0 8   I J E C E   V o l .   2 ,   N o .   4 ,   A u g u s t   2 0 1 2   :   4 5 3     4 5 5   4 5 4 I t   i s   o f   p a r t i c u l a r   i n t e r e s t   t o   s t u d y   t h e   i m p a c t   o f   r a n g e   e r r o r s   o n   t h e   p e r f o r m a n c e   o f   l o c a l i z a t i o n   a l g o r i t h m s ,   b e c a u s e   r a n g e   e r r o r s   a r e   i n h e r e n t   t o   W S N s   e m p l o y i n g   s i m p l e   a n d   l o w - c o s t   r a n g e   m e a s u r e m e n t   h a r d w a r e .   A c c o r d i n g   t o   t h e   e m p i r i c a l   s t u d y   o n   t h e   i m p a c t   o f   r a n g e   e r r o r s   o n   m u l t i h o p   l o c a l i z a t i o n s   [ 9 ] ,   h i g h   d e n s i t y   a n d   G a u s s i a n   n o i s e s   a r e   t h e   t w o   p r e r e q u i s i t e s   f o r   t h e   n o i s y   d i s k   m o d e l   t o   w o r k .   T h e   s t u d y   a l s o   s u g g e s t s   s t a t i s t i c a l   a p p r o a c h e s   f i x   t h e   p r o b l e m   r e s u l t e d   f r o m   r a n g e   e r r o r s .   C r a m e r R a o   l o w e r   b o u n d   ( C R L B )   i s   c o m m o n l y   a d o p t e d   i n   t h e   e r r o r   a n a l y s i s   o f   t h e   l o c a l i z a t i o n   s c h e m e s .   I t   i s   a   l o w e r   b o u n d   o n   t h e   v a r i a n c e   o f   t h e   e s t i m a t o r   t h a t   e s t i m a t e s   t h e   l o c a t i o n s .   G i v e n   t h e   k n o w l e d g e   o n   t h e   d i s t r i b u t i o n   o f   m e a s u r e m e n t s ,   i t   i s   s h o w n   i n   [ 1 0 1 2 ]   t h a t   t h e   b o u n d   o n   t h e   l o c a l i z a t i o n   e r r o r   c a n   b e   o b t a i n e d   t h r o u g h   c a l c u l a t i n g   t h e   C R L B .   T h e r e f o r e ,   t h e   l o c a l i z a t i o n   s c h e m e s   a r e   a b l e   t o   e v a l u a t e   t h e i r   p e r f o r m a n c e s   b y   c o m p a r i n g   t h e   l o c a l i z a t i o n   a c c u r a c y   w i t h   t h e   c o r r e s p o n d i n g   C R L B .     3 . 2 .   S c a l a b i l i t y   a n d   A u t o n o m y   A   l o c a t i o n - s e n s i n g   s y s t e m   m a y   b e   d e v e l o p e d   t o   f i n d   t a g s ,   o b j e c t s ,   p e o p l e ,   a s s e t s   o r   a n i m a l s   o n   t h e   s u r f a c e   o f   t h e   e a r t h ,   i n   a   c i t y ,   b u i l d i n g s   o r   i n   a   s i n g l e   r o o m .   W e   c a n   c l a s s i f y   t h e   l o c a t i o n - s e n s i n g   s y s t e m s   i n   a   r o u g h   m a n n e r   i n t o   s y s t e m s   w h i c h   w o r k   o u t s i d e   a n d   i n s i d e   a r e a s   [ 1 3 ] .   T h i s   c l a s s i f i c a t i o n   l e t s   u s   i d e n t i f y   s p e c i a l   p r o b l e m s   t h a t   t h e   s y s t e m   w i l l   h a v e   t o   a d d r e s s   s u c h   a s   d i f f r a c t i o n ,   m u l t i p a t h   a n d   i n t e r f e r e n c e   p r o b l e m s .   B e s i d e s ,   t h e   n u m b e r   o f   o b j e c t s   i n   t h e   s y s t e m   p l a y s   a n   i m p o r t a n t   r o l e   b e c a u s e   e v e r y   s y s t e m   h a s   i t s   o w n   l i m i t   t o   f i n d   a   n u m b e r   o f   o b j e c t s   p e r   t i m e   w i t h   a   g i v e n   a m o u n t   o f   i n f r a s t r u c t u r e   p e r   a r e a .   A n   i m p o r t a n t   c o n s i d e r a t i o n   i n   t h e   l o c a t i o n - s e n s i n g   s y s t e m s   i s   t o   s e l e c t   t h e   b e s t - f i t   r a d i o   f r e q u e n c y   t e c h n o l o g y ,   s i n c e   t h e   i n c r e a s e   o f   t h e   o b j e c t s   t o   b e   l o c a l i z e d   i n   t h e   n e t w o r k ,   d e m a n d s   f o r   m o r e   c o m m u n i c a t i o n   a n d   t h a t   c a n   c o n g e s t   t h e   c h a n n e l   i f   t h e   t h r e s h o l d   i s   e x c e e d e d .   T h i s   c h a r a c t e r i s t i c   i s   a l s o   k n o w n   a s   r e s p o n s i v e n e s s   o r   s a m p l i n g   [ 2 ]   a n d   i s   d e f i n e d   a s   h o w   q u i c k l y   t h e   l o c a t i o n   s y s t e m   o u t p u t s   t h e   l o c a t i o n   i n f o r m a t i o n .   T h e   d e g r e e   o f   a u t o n o m y   h a s   s o m e   o f   t h e   m o s t   s i g n i f i c a n t   c o n s e q u e n c e s   i n   t h e   s y s t e m   d e s i g n ;   t h i s   m e t r i c   i s   c l o s e l y   r e l a t e d   t o   t h e   s c a l a b i l i t y   o f   t h e   s y s t e m .   W e   c a n   s a y   t h a t   a   s y s t e m   h a s   h i g h   a u t o n o m y   w h e n   t h e r e   i s   l i t t l e   o r   n o   h u m a n   i n t e r v e n t i o n   n e c e s s a r y   t o   o p e r a t e   t h e   s y s t e m   a n d   t h e   n o d e s   a c t   a s   t o t a l l y   i n d e p e n d e n t   e n t i t i e s   [ 1 4 ] .   T h e   a u t o n o m y   o f   a   s y s t e m   i s   a c h i e v e d   t h r o u g h   t h e   u s e   o f   e x t e n s i v e   a n d   s o p h i s t i c a t e d   i n t e r n a l   p r o c e s s e s   t h a t   m a k e   t h e i r   o w n   c o o r d i n a t i o n   p o s s i b l e .   T h e   s e l f - c o o r d i n a t i o n   o f   t h e   n e t w o r k   i s   i m p o r t a n t   b e c a u s e   i t   i s   c l o s e l y   r e l a t e d   t o   t h e   p o s s i b i l i t y   t o   e x t e n d   t h e   s y s t e m .   W e   c l a s s i f y   t h e   a u t o n o m y   a n d   s e l f - o r g a n i z a t i o n   i n t o   c e n t r a l i z e d   o r   d i s t r i b u t e d   s y s t e m   i n   a   r o u g h   m a n n e r ,   t h a t   m e a n s ,   t h e   s y s t e m   c o u l d   o r   m a y   n o t   r e q u i r e   t h e   h e l p   o f   a   c e n t r a l   e n t i t y   t o   m o n i t o r   a n d   c o n t r o l   t h e   a c t i v i t i e s   o f   t h e   e l e m e n t s .     3 . 3 .   C o m m u n i c a t i o n   C o s t s   W e   c a n   e v a l u a t e   t h e   c o s t   o f   t h e   l o c a t i o n   s e n s i n g   s y s t e m   i n   d i f f e r e n t   w a y s ;   i n c l u d i n g   c o s t   i n   t e r m s   o f   t i m e   s p e n d   f o r   i n s t a l l a t i o n ,   m o n e y ,   c o m p u t a t i o n a l   e f f o r t   o r   e n e r g y   [ 1 5 ] .   T h e   t i m e   c o s t   o f   t h e   s y s t e m   i n c l u d e s   f a c t o r s   s u c h   a s   t h e   l e n g t h   o f   t h e   i n s t a l l a t i o n   p r o c e s s   a n d   t h e   n e e d s   f o r   s y s t e m   a d m i n i s t r a t i o n .   T h e   c a p i t a l   c o s t   o f   t h e   s y s t e m   c a n   b e   d i r e c t l y   m a p p e d   t o   t h e   m o n e y   n e e d e d   t o   s e t   u p   a n d   o p e r a t e   t h e   s y s t e m   s u c h   a s   t h e   a m o u n t   o f   i n f r a s t r u c t u r e   i n s t a l l e d ,   t h e   s a l a r i e s   o f   s u p p o r t   p e r s o n n e l   a n d   t h e   m a i n t e n a n c e   o f   t h e   s y s t e m .   T h e   c o m p u t a t i o n a l   c o s t   i s   a   c r u c i a l   m e t r i c   a n d   i s   c l o s e l y   r e l a t e d   t o   t h e   l o c a t i o n   a l g o r i t h m   o f   t h e   s y s t e m .   I t   d e t e r m i n e s   t h e   a r c h i t e c t u r e   o f   t h e   l o c a t i o n - s e n s i n g   s y s t e m   w h i c h   c a n   b e   o r g a n i z e d   e i t h e r   i n   a   c e n t r a l i z e d   o r   a   d i s t r i b u t e d   m a n n e r   [ 1 6 ] .   T h e   c e n t r a l i z e d   s y s t e m s   c o n t r o l   a n d   m o n i t o r   t h e   s y s t e m   f u n c t i o n s   w i t h   t h e   h e l p   o f   a   c e n t r a l   e n g i n e .   T h e   s y s t e m s   w h e r e   t h e   l o c a t i o n   a l g o r i t h m   i s   p u t   i n t o   e a c h   n o d e   o f   t h e   n e t w o r k   t o   c o m p u t e   i t s   o w n   p o s i t i o n   i s   c a l l e d   d e c e n t r a l i z e d   o r   d i s t r i b u t e d   s y s t e m .   A s   e n e r g y   e f f i c i e n c y   i s   c r i t i c a l   t o   W S N s ,   i t   i s   n e c e s s a r y   t o   c o n s i d e r   t h e   c o m p u t a t i o n   a n d   c o m m u n i c a t i o n   c o s t s   o f   t h e   l o c a l i z a t i o n   p r o c e s s   i n   t h e   e v a l u a t i o n   o f   l o c a l i z a t i o n   s c h e m e s .   C e n t r a l i z e d   a l g o r i t h m s   l i k e   t h e   S D P   o r   M D S - M A P   [ 1 7 ]   d e m a n d   r a n g e   m e a s u r e m e n t s   f r o m   a l l   t h e   n o d e s .   T h i s   i s   e x p e n s i v e   i n   t e r m s   o f   f o r w a r d i n g   t h e   m e a s u r e m e n t s   t o   t h e   p r o c e s s i n g   p o i n t   a n d   s o l v i n g   t h e   h i g h - d i m e n s i o n   m a t r i x .   D i s t r i b u t e d   a l g o r i t h m s ,   o n   t h e   o t h e r   h a n d ,   r e q u i r e   c o l l a b o r a t i o n s   a m o n g   n e i g h b o r i n g   n o d e s   t o   s o m e   e x t e n t .   I n   p a r t i c u l a r ,   t h e   m u l t i h o p   l o c a l i z a t i o n   f a c e s   t h e   t r a d e - o f f   b e t w e e n   t h e   c o m m u n i c a t i o n   c o s t   o n   p r o p a g a t i n g   t h e   a n c h o r   l o c a t i o n s   a n d   t h e   d e g r e e   o f   a c c u r a c y .   F o r   t h e   r e f i n e m e n t   o n   l o c a t i o n   e s t i m a t i o n s ,   t h e   n u m b e r   o f   i t e r a t i o n s   i s   a p p a r e n t l y   i n   t h e   c e n t e r   o f   t h e   t r a d e - o f f   b e t w e e n   t h e   e n e r g y   c o n s u m p t i o n   f o r   r e f i n e m e n t   o f   l o c a l i z a t i o n   r e s u l t s   a n d   t h e   d e g r e e   o f   a c c u r a c y   a c h i e v a b l e   t h r o u g h   r e f i n i n g .     3 . 4 .   N e t w o r k   a n d   A n c h o r s   D e n s i t y   I t   i s   w o r t h   n o t i c i n g   t h a t   l o c a l i z a t i o n   a l g o r i t h m s   a l w a y s   r e q u i r e   a   c e r t a i n   l e v e l   o f   c o n n e c t i v i t y   [ 1 8 ] .   S o ,   l o c a l i z a t i o n   s c h e m e s   a r e   b a s e d   o n   c o n n e c t i v i t y ,   r a n g e   m e a s u r e m e n t s ,   a n g l e   i n f o r m a t i o n ,   o r   a n y   c o m b i n a t i o n s   t h e r e o f .   T h e   d i s c u s s i o n s   o n   t h e   l o c a l i z a t i o n   a l g o r i t h m s   s u g g e s t   t h a t   d e n s e   n e t w o r k s   l e a d   t o   b e t t e r   l o c a l i z a t i o n   p e r f o r m a n c e .   H o w e v e r ,   a   d e n s e   n e t w o r k   d o e s   n o t   n e c e s s a r i l y   g u a r a n t e e   h i g h   a c c u r a c y   i n   l o c a t i o n   e s t i m a t i o n s .   T h e   d e n s i t y   o f   t h e   n e t w o r k   i s   u s u a l l y   r e p r e s e n t e d   b y   t h e   n u m b e r   o f   n o d e s   w i t h i n   a n   a r e a   o r   t h e   r a d i o   r a n g e   o f   n o d e s .   T h e   a n c h o r - b a s e d   l o c a l i z a t i o n   s c h e m e s ,   a i m i n g   a t   p r o v i d i n g   a b s o l u t e   l o c a t i o n s ,   r e q u i r e   a   h i g h   d e n s i t y   o f   a n c h o r s   t o   e n s u r e   l o w   l e v e l   o f   l o c a l i z a t i o n   e r r o r s   [ 1 9 ] .     Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I S S N :   2 0 8 8 - 8 7 0 8         F u n d a m e n t a l   M e t r i c 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   l o c a l i z a t i o n   ( R e z a z a d e h   J )   4 5 5 4 .   C O N C L U S I O N     I n   t h i s   p a p e r   w e   p r e s e n t e d ,   d i f f e r e n t   m e t h o d s   t o   i m p l e m e n t   l o c a l i z a t i o n   a n d   t h e   m a i n   m e t r i c s   t h a t   a   s y s t e m   d e s i g n e r   h a s   t o   t a k e   i n t o   a c c o u n t   t o   u n d e r s t a n d   a n d   v a l u e   t h e   d i f f e r e n t   l o c a t i o n - s e n s i n g   s y s t e m s .     I n   t h e   s i m u l a t i o n   r e s u l t s   o f   v a r i o u s   l o c a l i z a t i o n   s c h e m e s ,   w h e r e   t h e   a c c u r a c y   w a s   e x a m i n e d   t h r o u g h   t h e   t r a d e - o f f s   b e t w e e n   a c c u r a c y   a n d   m e a s u r e m e n t   p e r f o r m a n c e ,   p e r c e n t a g e   o f   a n c h o r s ,   d e p l o y m e n t   o f   a n c h o r s ,   d e n s i t y   o f   n o n   a n c h o r s ,   e t c .   B e s i d e s   r a n d o m l y   g e n e r a t e d   n e t w o r k s ,   a   t y p i c a l   d e p l o y m e n t   o f   n o d e s   i s   t h e   g r i d   o f   n o n - a n c h o r   n o d e s   w i t h i n   a   p a r t i c u l a r   a r e a .   T h e   l o c a l i z a t i o n   a c c u r a c y   o f   a   s o l u t i o n   i s   u s u a l l y   q u a n t i f i e d   u s i n g   t h e   a v e r a g e   E u c l i d e a n   d i s t a n c e   b e t w e e n   t h e   e s t i m a t e d   l o c a t i o n s   a n d   t h e   t r u e   l o c a t i o n s   n o r m a l i z e d   t o   t h e   r a d i o   r a n g e   o r   o t h e r   s y s t e m   m e t r i c s .   F o r   m o b i l i t y - a s s i s t e d   l o c a l i z a t i o n ,   t h e   e f f e c t   o f   n o d e   d e n s i t y   i s   n o t   a s   i m p o r t a n t   a s   i n   s t a t i c   l o c a l i z a t i o n   s c e n a r i o s .   I n   a d d i t i o n ,   c o m m u n i c a t i o n /   c o m p u t a t i o n   c o s t   m a y   n o t   b e   o f   s a m e   i m p o r t a n c e   t o   t h e   o f f - l i n e   s i m u l a t i o n s   a s   t o   t h e   r e a l   i m p l e m e n t a t i o n s .       R E F E R E N C E S     [ 1 ]   I .   F .   A k y i l d i z ,   W .   S u ,   Y .   S a n k a r a s u b r a m a n i a m ,   a n d   E .   C a y i r c i ,   A   s u r v e y   o n   s e n s o r   n e t w o r k s   I E E E   Co m m u n i c a t i o n s   M a g a z i n e ,   v o l .   4 0 ,   n o .   8 ,   p p .   1 0 2 1 1 4 ,   2 0 0 2 .   [ 2 ]   E s t r i n ,   D . ,   C u l l e r ,   D . ,   P i s t e r ,   K . ,   S u k h a t m e ,   G . :   Co n n e c t i n g   t h e   p h y s i c a l   w o r l d   w i t h   p e r v a s i v e   n e t w o r k s .   P e r v a s i v e   Co m p u t i n g ,   I E E E   1   ( 2 0 0 2 )   5 9 - 6 9   [ 3 ]   H i g h t o w e r ,   J . ,   Bo r r i e l l o ,   G . :   L o c a t i o n   s y s t e m s   f o r   u b i q u i t o u s   c o m p u t i n g .   C o m p u t e r   3 4   ( 2 0 0 1 )   5 7 - 6 6   [ 4 ]   S .   S l i j e p c e v i c ,   S .   M e g e r i a n ,   a n d   M .   P o t k o n j a k .   L o c a t i o n   e r r o r s   i n   w i r e l e s s   e m b e d d e d   s e n s o r   n e t w o r k s :   s o u r c e s ,   m o d e l s ,   a n d   e f f e c t s   o n   a p p l i c a t i o n s .   S I G M O B I L E   M o b i l e   C o m p u t i n g   C o m m u n i c a t i o n s   R e v i e w ,   6 ( 3 ) : 6 7 7 8 ,   2 0 0 2 .   [ 5 ]   H .   A .   O l i v e i r a ,   E .   F .   N a k a m u r a ,   A .   A .   F .   L o u r e i r o ,   a n d   A .   Bo u k e r c h e .   E r r o r   a n a l y s i s   o f   l o c a l i z a t i o n   s y s t e m s   f o r   s e n s o r   n e t w o r k s ,   G I S   2 0 0 5 :   T h e   1 3 t h   A n n u a l   A CM I n t e r n a t i o n a l W o r k s h o p   o n   G e o g r a p h i c   I n f o r m a t i o n   S y s t e m s ,   p a g e s   7 1 7 8 ,   2 0 0 5 .   [ 6 ]   A .   S a v v i d e s , W .   G a r b e r ,   R.   M o s e s ,   a n d   M .   S r i v a s t a v a .   A n   a n a l y s i s   o f   e r r o r   i n d u c i n g   p a r a m e t e r s   i n   m u l t i h o p   s e n s o r   n o d e   l o c a l i z a t i o n .   I E E E   T r a n s a c t i o n s   M o b i l e   Co m p u t i n g ,   4 ( 6 ) : 5 6 7 5 7 7 ,   N o v . - D e c .   2 0 0 5 .   [ 7 ]   G .   M a o ,   B.   F i d a n ,   a n d   B.   A n d e r s o n ,   W i r e l e s s   s e n s o r   n e t w o r k   l o c a l i z a t i o n   t e c h n i q u e s ,   Co m p u t e r   N e t w o r k s ,   v o l .   5 1 ,   n o .   1 0 ,   p p .   2 5 2 9 - 2 5 5 3 ,   J u l .   2 0 0 7 .   [ 8 ]   L .   W a n g   a n d   Q .   X u ,   G P S - F r e e   L o c a l i z a t i o n   A l g o r i t h m   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 ,   S e n s o r s ,   v o l .   1 0 ,   n o .   6 ,   p p .   5 8 9 9 - 5 9 2 6 ,   J u n .   2 0 1 0 .   [ 9 ]   K .   W h i t e h o u s e ,   C.   K a r l o f ,   A .   W o o ,   F .   J i a n g ,   a n d   D .   Cu l l e r .   T h e   e f f e c t s   o f   r a n g i n g   n o i s e   o n   m u l t i h o p   l o c a l i z a t i o n :   a n   e m p i r i c a l   s t u d y .   I P S 2 0 0 5 :   T h e   4 t h   I n t e r n a t i o n a l   S y m p o s i u m   o n   I n f o r m a t i o n   P r o c e s s i n g   i n   S e n s o r   Ne t wo r k s ,   p a g e s   7 3 8 0 ,   2 0 0 5 .   [ 1 0 ]   N .   P a t w a r i ,   I .   A . O .   H e r o ,   M .   P e r k i n s ,   N .   Co r r e a l ,   a n d   R.   O D e a .   Re l a t i v e   l o c a t i o n   e s t i m a t i o n   i n   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 a n s .   S i g n a l   P r o c e s s i n g   ,   5 1 ( 8 ) : 2 1 3 7 2 1 4 8 ,   2 0 0 3 .   [ 1 1 ]   C.   Ch a n g   a n d   A .   S a h a i .   E s t i m a t i o n   b o u n d s   f o r   l o c a l i z a t i o n .   S E C O 2 0 0 4 :   T h e   1 s t   I E E E   Co m m u n i c a t i o n s   S o c i e t y   Co n f e r e n c e   o n   S e n s o r   a n d   A d   H o c   Co m m u n i c a t i o n s   a n d   Ne t wo r k s ,   p a g e s   4 1 5 4 2 4 ,   2 0 0 4 .   [ 1 2 ]   S .   V e n k a t e s h   a n d   R .   M .   Bu e h r e r .   M u l t i p l e - a c c e s s   i n s i g h t s   f r o m   b o u n d s   o n   s e n s o r   l o c a l i z a t i o n   P e r v a s i v e   M o b i l e   Co m p u t i n g ,   4 ( 1 ) :   3 3 6 1 ,   2 0 0 8 .     [ 1 3 ]   M .   J a d l i w a l a ,   S .   J .   U p a d h y a y a ,   a n d   J . - P .   H u b a u x ,   S e c u r e   D i s t a n c e - Ba s e d   L o c a l i z a t i o n   i n   t h e   P r e s e n c e   o f   Ch e a t i n g   Be a c o n   N o d e s ,   I E E E   T r a n s a c t i o n s   o n   M o b i l e   C o m p u t i n g ,   v o l .   9 ,   n o .   6 ,   p p .   8 1 0 - 8 2 3 ,   J u n .   2 0 1 0 . .   [ 1 4 ]   J .   W a n g ,   R.   K .   G h o s h ,   a n d   S .   K .   D a s ,   A   s u r v e y   o n   s e n s o r   l o c a l i z a t i o n ,   v o l .   8 ,   n o .   1 4 ,   p p .   2 - 1 1 ,   2 0 1 0 .   [ 1 5 ]   J .   Re z a z a d e h ,   M .   M o r a d i ,   A .   S .   I s m a i l , "   E f f i c i e n t   l o c a l i z a t i o n   v i a   M i d d l e - n o d e   c o o p e r a t i o n   i n   w i r e l e s s   s e n s o r   n e t w o r k s "   I n   I n t e r n a t i o n a l   Co n f e r e n c e   o n   E l e c t r i c a l ,   Co n t r o l   a n d   Co m p u t e r   E n g i n e e r i n g   ( I N E CCE ,   2 0 1 1 ) ,   p p .   4 1 0 - 4 1 5 ,     2 0 1 1 .   [ 1 6 ]   Z .   Y a n g   a n d   Y .   L i u ,   Q u a l i t y   o f   T r i l a t e r a t i o n :   Co n f i d e n c e - Ba s e d   I t e r a t i v e   L o c a l i z a t i o n ,   I E E E   T r a n s a c t i o n s   o n   P a r a l l e l   a n d   D i s t r i b u t e d   S y s t e m s ,   v o l .   2 1 ,   n o .   5 ,   p p .   6 3 1 - 6 4 0 ,   M a y .   2 0 1 0 .   [ 1 7 ]   S .   Y . Ru m l ,   I m p r o v e d   M D S - b a s e d   l o c a l i z a t i o n .   I n   I N F O CO M ,   p p .   2 6 4 0 - 2 6 5 1 ,   2 0 0 4 .   [ 1 8 ]   J .   J e o n g ,   S .   G u o ,   T .   H e ,   a n d   D .   D u ,   A P L :   A u t o n o m o u s   P a s s i v e   L o c a l i z a t i o n   f o r   W i r e l e s s   S e n s o r s   D e p l o y e d   i n   Ro a d   N e t w o r k s ,   2 0 0 8   I E E E   I N F O CO M   -   T h e   2 7 t h   Co n f e r e n c e   o n   Co m p u t e r   Co m m u n i c a t i o n s ,   p p .   5 8 3 - 5 9 1 ,   A p r .   2 0 0 8 . .   [ 1 9 ]   N .   Bu l u s u ,   J .   H e i d e m a n n ,   D .   E s t r i n ,   a n d   T .   T r a n .   S e l f - c o n f i g u r i n g   l o c a l i z a t i o n   s y s t e m s :   D e s i g n   a n d   e x p e r i m e n t a l   e v a l u a t i o n .   T r a n s a c t i o n s   o n   E m b e d d e d   C o m p u t i n g   S y s t e m s ,   3 ( 1 ) : 2 4 6 0 ,   2 0 0 4 .         Evaluation Warning : The document was created with Spire.PDF for Python.