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 .   19 ,   N o .   2 A ugus t   20 20 ,   pp .   91 7 ~ 93 0   IS S N :   25 02 - 4752 ,   D O I :   10. 1 1591 / i j e e c s . v 19 .i 2 . pp91 7 - 93 0             917       Jou r n al   h o m e pa ge ht t p: / / i j e e c s . i a e s c or e . c om   D e t e r m i n a t i o n   o f   t h e   K - o p t i m a l   n u m b e r   o f   c h a i n s - b a s e d   r o u t i n g   p r o t o c o l   f o r m e d   b y   t h e   K - M e a n a l g o r i t h m   f o r   t h e   W S N       S am ah   A l n ajd i ,   F u ad   B ajab e r   D e pa rt m e n t   o f   In f o r m a t i o n   T e c hn o l o g y ,   F a c ul t y   o f   C o m put i n g   a nd  I n f o rm a t i o T e c hn o l o g y ,     K i n A b dul a z i z   U n i v e r s i t y ,   K i ngdo m   o f   S a udi   A r a b i 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 D e c   12 ,   2019   R e v i s e F e b   1 5 ,   20 20   A c c e pt e F e b   29,   202 0       W i r e l e s s   s e ns o r   n e t w o r k s   c o m pr i s e   o f   a   l a r g e   num be r   o f   l i g ht w e i g ht   a nd   r e l a t i v e l y   l o w - c o s t   c om put a t i o na l   no de s   w hi c t he i r   m a i t a s i s   t o   s e ns e     t he   s ur r o undi ng   e nv i r o nm e nt   a nd  c o l l e c t   t he   i nf o r m a t i o t o   s e n i t   w i r e l e s s l y   t o   a   c e nt r a l   po i nt   t o   t a ke   t he   a pp r o pr i a t e   a c t i o ns .   A l t ho ug t h e s e   ne t w o r ks   ha be e n   u s e d   i n   v a r i o us   a p pl i c a t i o ns ,   a c hi e v i ng   t h i s   t a s k   i s   c ha l l e ng i ng   due   t o   t he   m a ny   c o ns t r a i n t s   o f   s e ns o r   no de s   i nc l u di ng   t h e i r   l i m i t e pr o c e s s i ng   po w e r ,   c o m m uni c a t i o b a ndw i d t h ,   a n po w e r   s up pl y .   T he r e f o r e ,   a e n e r g y   e f f i c i e nt   r o ut i ng   pr o t o c o l s   ha t o   be   d e v e l o pe s pe c i f i c a l l y   f o r   s e ns o r   ne t w o r k s   t o   i ns u r e   l o ng e r   l i f e t i m e   a nd  r e a s o na b l e   pe r f o r m a nc e   o f   t he   ne t w o r k .   I t hi s   w o r k,   w e   pr o po s e   a e ne r g y   e f f i c i e nt   h i e r a r c h i c a l   r o ut i ng   pr o t o c o l   us i ng   c ha i n - ba s e c l u s t e r i ng .   B y   s i m u l a t i o n   o M A T L A B ,     t he   p r o po s e p r o t o c o l   p r o v e t o   e n h a nc e   t h e   pe r f o r m a nc e   a s   i t   p r o l o ng s     t he   l i f e t i m e   o f   t h e   n e t w o r a n de c r e a s e s   t h e   e n e r g y   c o ns u m p t i o n ,     t he   t r a n s m i s s i o d e l a y ,   a n t h e   o v e r h e a d   c o m p a r e t o   o t h e r   e x i s t i ng   p r o t o c o l s   as   i t   d e pe n d s   o s o m e   a dv a nc e m e t ho d s   i nc l u d i ng   dy na m i c   s e l e c t i o n     o f   num be r   o f   c ha i n s   m e t ho d ,   k - m e a n s   c l u s t e r i ng   m e t ho d ,   a dv a nc e g r e e dy   c ha i n   c o n s t r uc t i o n   m e t ho d ,   a n d   m u l t i - f a c t o r   ba s e d   l e a d e r   s e l e c t i o n   m e t ho d .   Ke y w or d s :   Cha i n - b a s e c l us t e ri n g   E n e rgy   c o n s um pt i o hi e ra r c h i c a l   r o ut i ng  p r o t o c o l s   K - m e a n s   a l go r i t hm   N e t w o r l i f e t i m e   O pt i m a l   k   O v e r h e a d   W S N s   C opy r i gh t   ©   2020   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 :   S a m a A b dul l a A l na j di ,   D e pa rt m e n t   o f   In f o r m a t i o n   T e c hn o l o g y ,     F a c ul t y   of   Co m put i n g   a n d   I n f o r m a t i o T e c hn o l o gy ,   K i n A b dul a z i z   U n i v e r s i t y ,   E m a i l :   a l na j di s a m a h @ gm a i l . c o m       1.   I N TR O D U C TI O N     A   w i r e l e s s   s e n s o r   n e t w o r (W S N i s   a   s pe c i a l i z e n e t w o r t ha t   c o n s i s t s   o f   a   n um b e r   o f   l i gh t w e i ght   n o de s   kn o w n   a s   s e n s o r s .   T h e   s e n s o r s   a r e   r a ndo m l y   de pl oy e i n   t h e   a f f e c t e a r e a   t o   m o ni t o r   t h e   e n v i r o nm e n t   a n g a t h e r   t h e   r e qu i r e i n f o r m a t i o n ,   s uc h   a s   m o v e m e n t ,   l i g ht s ,   o r   t e m pe ra t u r e   [1] .   M o r e o v e r ,   t h e y   m us t   w o r c oo pe r a t i v e l y   a n c o m m u ni c a t e   t o   s e n t h e   ga t h e r e i n f o r m a t i o n   t o   a   m o r e   po w e r f ul   n o de   t o   be   us e fo r   us e f ul   pur po s e s .   A l t h o ug h   t h e   W S N s   ha b e e n   w i de l y   us e i n   v a ri o us   a ppl i c a t i o n s   due   t o   t h e   s e n s i ng   a b i l i t y   of   t h e   s e n s o r s ,   t h e   t i n y   s i z e   t h a t   a l l o w s   t h e   s e n s o r   t o   b e   de p l oy e i n   h a rd - to - r e a c h   p l a c e s ,   t h e   l o w   c o s t s   a n d   t h e   s e l f - o r ga n i z i n g   b e h a v i o r   o f   t h e   s e n s o r   n o de s ,   t h e r e   a r e   m a n y   i s s ue s   i n   W S N s   due   t o   t h e   l i m i t e f u n c t i o n s   of   s e n s o r s .   T h e   s e n s o r s   n o r m a l l y   h a v e   l i m i t e p r o c e s s i n c a pa c i t y ,   l i m i t e c o m m u ni c a t i o n   b a n dw i dt h,   l i m i t e d   m e m o r y ,   a n d,   m o s t   i m po r t a n t l y ,   a   l i m i t e po w e r   s up pl y   s i n c e   t h e y   h a v e   un - r e c h a rge a b l e   b a t t e r i e s .     Co n s i de r i n t h e   l i m i t a t i o n s   o f   s e n s o r   n o de s   t ha t   a r e   di s c us s e a b ove ,   a ppl y i n a e ff i c i e n t   r o ut i n g   m e c h a ni s m   i s   o n e   o f   t h e   m a i n   c r i t i c a l   i s s ue s   i n   W S N s .   A s   r o ut i n i n   W S N s   di f fe r s   f r o m   c o n v e n t i o na l   n e t w o r ks ,   m a n y   r o ut i ng  a l go r i t h m s   a nd  p r o t o c o l s   pr o pos e s pe c i f i c a l l y   fo r   W S N s   b e l o n t o   v a r i o us   c a t e go r i e s .   F o r   i n s t a n c e ,   t h e s e   i n c l u de   l o c a t i o n - b a s e p r o t o c o l s ,   m o b i l i t y - b a s e pr o t o c o l s ,   h e t e r o ge n e i t y   b a s e pr o t o c o l s ,   qua l i t y   of   s e r v i c e   (Q oS ) - b a s e pr o t oc o l s ,   hi e ra r c hi c a l   p r o t o c o l s ,   m ul t i p a t h - b a s e p r o t o c o l s ,   a n d a t a - c e n t ri c   p r o t o c o l s   [2].   H i e ra r c hi c a l   r o ut i n i s   t h e   m o s t   us e r o ut i n g   m e c h a ni s m   i n   W S N s   a s   i t   m a i nl y   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 .   19 ,   N o .   2 A ugus t   20 20  :     91 7   -   93 0     918   a i m s   t o   e s t a b l i s h   e ff i c i e n t   e n e r gy   c o n s um pt i o n   us i n t h e   s e n s o r   n o de s   a n t h e   o ve r a l l   l o ng  l i f e t i m e   o t h e   n e t w o r k.   Cl us t e r i ng  i s   pe r f o r m e i n   hi e r a r c h i c a l   r o ut i ng  w h e r e   t h e   n e t w o r i s   b r o ke n   i nt o   l a y e r s .   T h e   f i r s t   l a y e r   pr e s e n t s   a l l   t h e   n o de s   s i n c e   t h e y   t oo   a r e   pa r t i t i o n e i nt o   c l us t e r s   b a s e o n   s o m e   c l us t e r i n a l go ri t hm s .   In   e a c h   c l us t e r,   o n e   n o de   i s   e l e c t e t o   m a na ge   t h e   c l us t e r   a n i s   kn o w n   a s   t h e   c l us t e r   h e a d .   A l l   t h e   c l us t e h e a ds   t o ge t h e r e p r e s e n t   t h e   s e c o n l a y e r   o f   t h e   n e t w o r t h a t   i s   r e s po n s i b l e   f o r   s e n d i n g   o v e r   f a r t h e di s t a n c e s ,   s uc h   a s   t o   t h e   B S .   H ow e v e r ,   h i e ra r c hi c a l   r o ut i n p r o t o c o l s   t h e m s e l v e s   h a v e   di f fe r e n t   t y pe s   of   c l us t e r i n g :   c l us t e r - b a s e d,   c ha i n - b a s e d,   o t r e e - b a s e c l us t e r i ng.   In   c l us t e r - b a s e r o ut i n p r o t o c o l s ,   t h e   n o de s   i n   e a c h   c l us t e r   a r e   m e a n t   t o   o n l y   c o m m u n i c a t e   a n fo r w a r d   t h e   d a t a   d i r e c t l y   t o   t h e i r   c l us t e h e a d .   F o t r e e - b a s e r o ut i ng  p r o t o c o l s ,   t h e   r o ut i n g   pa t h   i s   b ui l t   i   a   p a r e nt - c h i l m a nn e r,   a n e a c n o de   a l w a y s   fo r w a r ds   t o   i t s   pa r e nt   n o de .   O n   t h e   o t h e ha n d,   c h a i n - b a s e d   r o ut i ng  p r o t o c o l s   c o n n e c t   t h e   n o de s   t o ge t h e r   t o   fo r m   a   c ha i n,   a n t h e   da t a   a r e   f o r w a r de a l o n t h e   c h a i n   t o   t h e   B S .   I n   t hi s   p a pe r,   w e   r e v i e w   m o s t   o f   t h e   e xi s t i n g   c ha i n - b a s e pr o t o c o l s   a n d   p r o po s e   o ur   v e r s i o n   o   t h e   i m p r o v e c h a i n - b a s e r o ut i n g   by   i n c l ud i n s o m e   a dv a n c e a l go ri t hm s   du ri n t h e   d i f fe r e n t   p ha s e s   of    t h e   r o ut i ng  p a t h   de v e l o pm e n t   p r o c e s s ,   i n c l udi n g   f i n d i n t h e   o pt i m u m   n u m b e r   o f   c l us t e r s   i n   t h e   c a s e   of   c h a i n - b a s e c l us t e r i n g.   T h e   pa pe r   o r g a n i z e a s   f o l l ow s .   T h e   l i t e r a t u r e   r e v i e w   i n   S e c t i o n   i s   f o l l ow e by   o ur   n e t w o r a n t h e   us e c o m m uni c a t i o n   ra di o   m o de l   i n   S e c t i o n   3 .   T h e   p r o po s e pr o t o c o l   i s   gi v e n   i n   S e c t i o n   4 ,   a n i t s   pe r f o r m a n c e   e v a l ua t i o n   i n   c o m pa ri s o w i t h   o t h e p r o t o c o l s   i n   a ddi t i o t o   s t a t i s t i c a l   a n a l y i s i s   i s   pr o v i de i S e c t i o n   5 .   F i na l l y ,   t h e   c o n c l us i o n s   a r e   g i v e n   i n   S e c t i o n   6.       2.   LI TER A TU R R EV I EW   Co nn e c t i n t h e   s e n s o r   n o de s   i n   a   c ha i n - l i ke   t o po l o g y   w o ul h i g hl y   be n e f i t   t h e   e n e r gy   c o n s um pt i o n   c o m pa r e w i t h   o t h e r   c l us t e r i ng  a pp r o a c h e s .   T hus ,   m o r e   s t ud i e s   h a v e   b e e n   c a rri e o ut   t o   i m p r o v e   t h e   r o ut i ng  pr o c e s s   us i n c h a i n - b a s e c l us t e r i ng.   W e   re v i e w   m o s t   o f   t he s e   r o u t i ng  p r o t o c o l s   b y   fo c us i ng  o t he i r   c ha i c o n s t ruc t i o a l go ri t hm s   a nd   de p l o y m e nt   a r e a   di v i s i o m e t h o ds .   T a b l e   1   s u m m a ri z e s   a l l   t he   r e v i e w e d   p r o t o c o l s .         T a b l e   1 .   C ha i n - b a s e h i e r a r c h i c a l   r o ut i n g   p r o t o c o l s   Ro u t i n g   p ro t o c o l   N e t w o rk   t y p e   N u m b e r   o f   c h a i n s   N u m b e r   o f   c h a i n s   Ch a i n   c o n s t ru c t i o n   m e t h o d   L e a d e r   s e l e c t i o n   P E G A S IS   [3 ]   h o m o g e n e o u s   s i n g l e   S t a t i c   G re e d y   a l g o ri t h m   I n   t u rn ,   i n   ro u n d - ro b i n   m a n n e r   E E CB   [4 ]   h o m o g e n e o u s   s i n g l e   S t a t i c   G re e d y   a l g o ri t h m   w i t h   d i s t a n c e   t h r e s h o l d   Co n s i d e r s   b o t h   t h e   r e s i d u a l   e n e r g y   o f   t h e   n o d e   a n d   t h e   d i s t a n c e   t o   B S   IE E P [5 ]   h o m o g e n e o u s   s i n g l e   S t a t i c   A d v a n c e d   g r e e d y   a l g o ri t h m   U s e s   w e i g h t i n g   m e t h o d   t h a t   c o n s i d e r s   b o t h   t h e   r e s i d u a l   e n e r g y   o f   n o d e s   a n d   t h e   d i s t a n c e   f ro m   n o d e   t o   B S .   S CBC   [6 ]   h e t e ro g e n e o u s   M u l t i p l e   S t a t i c   G re e d y   a l g o r i t h m   b u t   S CBC  s t a rt s   w i t h   t h e   n e a re s t   a n d   t h e   L e a d e n o d e   w i t h   t w o   d i ffe r e n t   c h a i n s   t o   fo r m   o n e   c h a i n .   T h e   re s i d u a l   e n e r g y   a n d   c o s t   f u n c t i o n   a r e   c o n s i d e r e d .   S e c o n d a r y   l e a d e n o d e s   a r e   s e l e c t e d   t o   s e n d   t o   t h e   BS   G h o s h   e t   a l .   [8 ]     h o m o g e n e o u s   s i n g l e   S t a t i c   A n t   Co l o n y   O p t i m i z a t i o n   [7 ]   Co n s i d e r s   b o t h   t h e   r e m a i n i n g   e n e r g y   o f   t h e   n o d e   a n d   t h e   d i s t a n c e   t o   B S   G u p t a   a n d   S a ra s w a t   [9 ]   h o m o g e n e o u s   s i n g l e   S t a t i c   G re e d y   a l g o r i t h m   w i t h   t h e   s e n s o n o d e s   a l l o w e d   t o   o p t   v i s i t e d   n o d e s   a g a i n   i t h e y   a r e   t h e   n e a r e s t   o n e   f ro m   t h o s e   s e n s o r   Co n s i d e r s   t h e   d e g r e e   o n o d e s   i n   a d d i t i o n   t o   t h e   re s i d u a l   e n e r g y   a n d   d i s t a n c e   f r o m   t h e   BS   E P E G A S I S   [1 0 ]   h o m o g e n e o u s   M u l t i p l e   S t a t i c   G re e d y   a l g o ri t h m   In   t u rn ,   i n   ro u n d - ro b i n   m a n n e r   CH IRO N [1 1 ]   h o m o g e n e o u s   m u l t i p l e   S t a t i c   G re e d y   a l g o ri t h m   Co n s i d e r s   t h e   r e s i d u a l   e n e r g y   o n l y .   S h e k h   e t   a l .   i n   [1 3 ]   h o m o g e n e o u s   M u l t i p l e   S t a t i c   G re e d y   a l g o ri t h m   Co n s i d e r s   t h e   n o d e s   d e n s i t y   i n   a d d i t i o n   t o   t h e   r e s i d u a l   e n e r g y   a n d   d i s t a n c e   f ro m   t h e   BS   H a d j i l a   e t   a l .   [1 4 ]   h o m o g e n e o u s   m u l t i p l e   S t a t i c   N o d e s   i n   e a c h   g r o u p   f o r m s   a   s i n g l e   c h a i n   a n d   s o rt e d   a c c o r d i n g   t o   t h e i r   o rd i n a t e s .   F i r s t   n o d e   i n   t h e   c h a i n ,   i . e .   c l o s e s t   t o   t h e   BS   i s   t h e   l e a d e r   n o d e .   J a w a d   a n d   A l i   [1 5 ]   h o m o g e n e o u s   m u l t i p l e   S t a t i c   G re e d y   a l g o ri t h m   Co n s i d e r s   b o t h   t h e   r e s i d u a l   e n e r g y   o f   t h e   n o d e   a n d   t h e   d i s t a n c e   t o   B S   Ru a n   e t   a l .   [1 6 ]   h o m o g e n e o u s   m u l t i p l e   S t a t i c   A n t   Co l o n y   O p t i m i z a t i o n   U s e s   t h e   n e u ra l   n e t w o rk   t o   s e l e c t   t h e   l e a d e n o d e 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       D e t e r m i nat i on   of   t h e   K - op t i m a l   num be r   of   c ha i ns - bas e r ou t i ng  pr ot o c ol   f or m e b y   ( Sam ah  A l na j di )   919   Ro u t i n g   p ro t o c o l   N e t w o rk   t y p e   N u m b e r   o f   c h a i n s   N u m b e r   o f   c h a i n s   Ch a i n   c o n s t ru c t i o n   m e t h o d   L e a d e r   s e l e c t i o n   P a t e l   a n d   M u n j a n i   [1 7 ]   h o m o g e n e o u s   m u l t i p l e   S t a t i c   G re e d y   a l g o ri t h m   In   t u r n   In   r o u n d - r o b i n   m a n n e r   Bh a t t i   a n d   Ra i n a   [1 8 ]   H o m o g e n e o u s   S i n g l e   S t a t i c   M o d i fi e d   G re e d y   a l g o r i t h m   w i t h   f u z z y   s y s t e m   a n d   c u c k o o   s e a rc h   a l g o ri t h m   In   t u r n   In   r o u n d - r o b i n   m a n n e r   P E G A S IS - IN L   [1 9 ]   H o m o g e n e o u s   S i n g l e   S t a t i c   G re e d y   a l g o ri t h m   Ba s e d   o n   t h e   m e a s u r e d   RS S I   v a l u e   P E G - B BO   [2 0 ]   H o m o g e n e o u s   S i n g l e   S t a t i c   Bi o g e o g ra p h y - Ba s e d   O p t i m i z a t i o n   x   IE CBS N   [2 1 ]   H o m o g e n e o u s   m u l t i p l e   S t a t i c   F o r m s   m u l t i p l e   c h a i n s   P ,   w h e r e   P   e q u a l s   N / M   a s   N   t h e   i n i t i a l   n u m b e r   o n o d e s   a n d   M   t h e   c h a i n s   l e n g t h .   S t a rt i n g   f r o m   t h e   c l o s e s t   n o d e   t o   t h e   BS .   Co n s i d e r s   b o t h   t h e   r e s i d u a l   e n e r g y   o f   t h e   n o d e   a n d   t h e   d i s t a n c e   t o   B S   H o p   P E G A S I S   [2 2 ]   H o m o g e n e o u s   m u l t i p l e   S t a t i c   F o r m s   fi v e   c l u s t e r s   s t a rt i n g   f r o m   t h e   c l o s e s t   t o   t h e   BS .     x       2. 1 .   C h ai n   c o n s tr u c ti o n   T h e   n o de s   i n   c ha i n - b a s e c l us t e r i n a r e   s uppo s e t o   i n v o l v e   m ul t i - h o c o m m u n i c a t i o n   w h e r e   t h e   da t a   pa c ke t s   a r e   t r a n s m i t t e o v e r   s e ve r a l   n o de s   i n   o r de r   t o   re a c h   t h e   f i na l   de s t i na t i o n.   H ow e v e r ,   t h e   di s t a n c e   b e t w e e n   e a c h   n o de   a n t h e i r   n e i g h b o r   n o de   i n   t h e   c ha i n   pl a y s   a   m a j o r   r o l e   i n   e n e r gy   c o n s um pt i o n   (a   l a r ge r   di s t a n c e   m e a n s   m o r e   e n e r gy   c o n s um pt i o n   f o r   t ra n s m i t t i n g) .   T h e   f i r s t   a n m o s t - us e a l go ri t hm   i c ha i n - b a s e r o ut i ng  pr o t o c o l s   fo r   c o nn e c t i n t h e   n o de s   t o ge t h e r   i s   t h e   gr e e dy   a l go r i t hm .   I n   t h e   gr e e d y   a ppr o a c h,   l o c a l   o pt i m i z a t i o n   i s   pe r f o r m e i n   w h i c h   e a c h   n o de   ge t s   c o n n e c t e t o   t h e   n e a r e s t   a v a i l a b l e   n o de   de s pi t e   t h e   f i n a l   r e s ul t .   A s   a   r e s ul t ,   a   c h a i n   o f   n o de s   i s   c o n s t r uc t e d ,   b ut   a s   t h e   pr o c e s s   pr o gr e s s e s ,   t h e   c o m m u n i c a t i o n   d i s t a n c e   ge t s   l o n ge r,   a s   s h o w n   i n   F i gu r e   1 (a ) .   T h e   f i r s t   us e   of   t h i s   a l go r i t hm   i n   hi e ra r c h i c a l   r o ut i n w a s   i   t h e   P E G A S IS   p r o t o c o l   pr o po s e b y   L i n ds e y   a n R a g h a v e n d r a   [3].   O t h e r   s c h o l a r s   s ugge s t e s o m e   m o di f i c a t i o n s   t o   s o l ve   t h e   l o n l i n p r o b l e m   (L L c a us e by  t h e   g r e e d y   a l go r i t h m   w h e r e   t h e   da t a   pa c ke t   ha s   t o   b e   t r a n s m i t t e t hr o ug h   ha l v e   of   t h e   n o de s   i n   t h e   c h a i n   i n   b e s t   c a s e   s c e n a ri o   t o   r e a c h   t h e   l e a de n o de ,     a n t hr o ug h   a l l   t h e   n o de s   i n   w o r s t   c a s e   s c e n a ri o   i f   t h e   l e a de n o de   i s   l o c a t e a t   t h e   e n o f   t h e   c h a i n .   I n   E E CB   pr o t o c o l   [4],   a ppl y i n a   t hr e s h o l di s t a n c e   w a s   pr o po s e t h a t   i f   t h e   di s t a n c e   b e t w e e n   a   n o de   a n i t s   " r e a dy   t b e "   n e i gh b o r   n o de   e x c e e d s   a   t hr e s h o l v a l ue ,   t h e   t w o   n o de s   w i l l   n o t   b e   a l l o w e t o   c o n n e c t .   I n s t e a d,   t h e   l a t t e n o de   w i l l   s e a r c t h e   c h a i o f   a l r e a dy   c o nn e c t e n o de s   a n d   c o nn e c t   t o   t h e   n e a r e s t   o n e   o f   t h e m .     A   m o r e   a dv a n c e m o di f i c a t i o n   o f   t h e   gr e e d y   a l go r i t hm   w a s   pr e s e n t e i n   t h e   IE E P B   p r o t o c o l   [5].     In   t h e   I E E P B ,   a l l   n o de s   ge t   t h e   c h a n c e   t o   s e a r c h   t h e   a l r e a dy   fo r m e c h a i n   o f   n o de s   t o   c o nn e c t   t o   t h e   n e a r e s t   o n e   of  t h e m .   T h e r e f o r e ,   t h e   c o m m u n i c a t i o n   di s t a n c e   w a s   f ur t h e r   r e duc e i n   c o m pa r i s o n   t o   t h e   P E G A S I S   a n d   E E CB   a l go ri t hm s .   F i gu r e   1 (b s h o w s   a   c h a i n   c o n s t ruc t e b a s e o n   t h e   A dv a n c e G r e e dy   A l go r i t h m   p r o po s e d   i n   t h e   IE E P B .   F u r t h e rm o r e ,   t h e   S CB pr o t o c o l   [6]  e xpa n d e t h e   r e s e a r c h   l i s t   f o r   t h e   n o de s   by   s t a rt i n t h e   c o n s t r uc t i o n   o f   t w o   c h a i n s   a t   t h e   s a m e   t i m e .   T h e r e f o r e ,   a s   t h e   pr o c e s s   pr o gr e s s e s ,   t h e   n o de s   w i l l   h a v e   t w a l r e a dy   fo r m e c ha i n s   t o   s e a r c f o r   t h e i r   n e a r e s t   n o de .   A n o t h e r   k n o w n   a l go ri t hm   us e f o r   c h a i n   c o n s t ruc t i o i s   A n t   Co l o n y   O pt i m i z a t i o n   (A CO [7] .   T h e   a l go r i t hm   gua ra nt e e s   t h e   o pt i m um   c o m m u ni c a t i o n   pa t h   b e t w e e n   t h e   n o de s   a n d   w a s   a ppl i e i [8]  b y   G h o s h   e t   a l .   N e v e r t h e l e s s ,   c o n n e c t i ng  a l l   t h e   n o de s   i n t o   a   s i n gl e   c h a i n   i s   n o t   t h e   m o s t   s uff i c i e n t   w a y   o f   r o ut i n g .   T h e   l e n g t h   o f   t h e   r o ut i n pa t i n   t e rm s   o f   t h e   num b e r   o f   h o ps / n o de s   a f fe c t s   t h e   t r a n s m i s s i o n   de l a y   s i n c e   e a c h   n o de   i n   t h e   pa t h   ha s   t o   w a i t   t o   r e c e i ve   t h e   da t a   f r o m   i t s   p r e v i o us   n e i g h b o r ,   a gg r e ga t e s   t h e   r e c e i ve da t a   w i t h   i t s   ow n   s e n s e da t a ,   a nd  t h e n   t r a n s m i t s   i t   t o   t h e   n e xt   n e i g h b o r i n g   n o de .   M o r e o ve r ,   t h e   l e a de r   n o de ,   w h i c h   i s   t h e   o n e   s e n di n t o   t h e   B S ,   c o ul b e   a t   a n y   pl a c e   o n   t h e   c h a i n   a nd  o c c a s i o n a l l y   f a r t h e r   f r o m   t h e   B S   t h a o t h e r   n o de s .   T h e r e f o r e ,   r e du nda nt   d a t a   t ra n s m i s s i o o c c ur s   w h e n   t h e   c l o s e r   n o de s   h a v e   t s e n t h e i r   da t a   i n   t h e   di r e c t i o n   o f   t h e   l e a de r   n o de   t o   be   s e n t   a ga i n   by     t h e   l e a de r   i n   t h e   di r e c t i o n   o f   t h e   B S .   G upt a   a n S a r a s w a t   i n   [9]  s ugge s t e t h a t   t o   o r de r   t h e   n o de s   f r o m     t h e   f a r t h e s t   t o   c l o s e s t   f r o m   t h e   B S   dur i ng  t h e   c ha i c o n s t r uc t i o n   p ha s e ,   t h e   n o de s   a r e   o n l y   a l l o w e t o   c o n n e c t   w i t t h e   n o de s   t ha t   a r e   c l o s e t o   t h e   B S   s o   t h e   d a t a   t ra n s m i s s i o n   i s   m o r e   o f t e n   i t h e   B S   di r e c t i o n.           (a )   (b )     F i gu r e   1 .   C ha i o f   n o de s   c o n s t r uc t e b a s e o t h e   g r e e d y   a l g o r i t hm ;   (b A   c ha i o f   n o de s   c o n s t r uc t e d   b a s e o n   t h e   a dv a n c e g r e e dy   a l go r i t hm   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 .   19 ,   N o .   2 A ugus t   20 20  :     91 7   -   93 0     920   2. 2 .   N e tw o r k   p ar t i ti o n   In  a dd i t i o n   t o   t h e   t ra n s m i s s i o de l a y   a n d   t h e   r e du nda nt   d a t a   t ra n s m i s s i o p r o b l e m s ,   c o n s t r uc t i n g   a   s i ngl e   c ha i i n c l ud i n a l l   t h e   n o de s   c a us e s   h i g e n e r gy   c o n s um pt i o n,   e s pe c i a l l y   i n   hi g h - de n s i t y   n o de   s i t ua t i o n s .   T h e   p r o b a b i l i t y   of   h a v i n m o r e   c o nn e c t i o n s   f o r   t h e   n o de s   m e a n s   hi g h e r   e n e r gy   c o n s um e fo r   r e c e i v i n da t a   f r o m   t h e   m ul t i p l e   c h i l n o de s .   T h e r e f o r e ,   s om e   pr o t o c o l s   a r e   foc us e o n   f i n di ng  t h e   o pt i m u m   m e t h o ds   t o   di v i de   t h e   n o de s   i nt o   m ul t i p l e   c ha i n s .   O n e   o f   t h e   e a rl i e s t   e f fo r t s   w a s   t h e   E P E G A S IS   p r o t o c o l   [10]  i n   w h i c h   di v i di ng  t h e   de pl oy m e n t   a r e a   i n t o   l e v e l s   us i n a   c o n c e n t r i c   c l us t e r i ng  s c h e m e   w a s   s ugg e s t e d,     a s   p r e s e n t e i n   F i g u r e   2 (a ) .   P e r   e a c h   l e v e l ,   a   s e pa r a t e   c h a i n   i s   c o n s t ruc t e b a s e o n   t h e   g r e e d y   a l go r i t hm .     T h e   di v i s i o m e t h o i s   f ur t h e e nha n c e by   t h e   CH IR O N   pro t oc o l   [11]  t o   s l i g h t l y   c o n t r o l   t h e   l e n g t h s   o f   t h e   c h a i n s   by   a ppl y i n t h e   B e a m S t a r   t e c hni que   [12]  a n d i v i di n e a c h   l e v e l   i n   ha l f .   M o r e o ve r ,   S h e kh   e t   a l .     i n   [1 3]  w a n t e t o   c o n t r o l   t h e   l e ngt h s   o f   c h a i n s   e v e n   m o r e   i t h e   f a r t h e s t   g r o ups   by   di v i di n e a c h   l e v e l   i nt o     a   f i xe s i z e g r o up .   T h e   r e s ul t   o f   t h e   pa rt i t i o ni n g   m e t h o pe rfo r m e b y   S h e kh  e t   a l .   i s   s h o w n   i F i g u r e   2 (b ).     In   a ddi t i o n,   o t h e r   p r o t o c o l s   pe r fo r m e v e r t i c a l   pa rt i t i o ni n i n s t e a d.   F o r   i n s t a n c e ,   t h e   S CB pr o t o c o l   di v i de t h e   a r e a   i n t o   s e c t o r s   w i t h   t h e   B S   a s   t h e   h e a o f   di v i s i o n ,   a s   s h o w n   i F i gu r e   2 (c ).   Co n v e r s e l y ,   H a dj i l a   e t   a l . ' s   pr o t o c o l   [14]  di v i de t h e   a r e a   i n   a   pa ra l l e l   m a nn e r .   H ow e v e r ,   a l l   t h e   pr e v i o us   di s c us s e w o r ks   pe r f o r m e t h e   pa rt i t i o ni n i n   t e r m s   o f   t h e   a r e a   s pa c e ,   r e ga rdl e s s   of   t h e   a c t u a l   l o c a t i o n s   o f   t h e   de pl o y e s e n s o r   n o de s .   F o r   r a ndo m   de pl oy m e n t ,   t h i s   c o ul p r o duc e   unn e c e s s a r y   e n e r gy   c o n s um p t i o n   s i n c e   t h e   n o de s   m a y   be   fo r c e t o   be   a s s i g n e t o   g r o ups   w i t h   f a rt h e n o de s   t o   c o nn e c t   w i t h   i n s t e a o f   c l o s e r   a v a i l a b l e   n e i g h b o r s .   T h e r e f o r e ,   pa rt i t i o n i n g   t h e   n o de s   b a s e o n   t h e i r   l o c a t i o ns   w o ul s a v e   s i gni f i c a nt   e n e rgy ,   a n d   o n e   o   t h e   k n o w n   a ppl i e m e t h o ds   i o t h e r   hi e ra r c h i c a l   p r o t o c o l s   i s   k - m e a n s   c l us t e r i n g .   J a w a a n A l i   a pp l i e   t h e   m e t h o f o r   c ha i n - b a s e r o ut i ng  i n   [15] .               (a )   (b )   (c )     F i gu r e   2 .   ( a )   Co n c e nt r i c   c l us t e ri n g   s c h e m e ;   (b N e t w o r pa rt i t i o n i n g   by   S h e k h   e t   a l . ;     (c S e c t o r s   s c h e m e   i S CB C       2. 3 .   Le ad e r   n o d e s   s e l e c ti o n   In   h i e ra r c hi c a l   r o ut i n g ,   t h e   n o de   t ha t   i s   gi v e n   t h e   l e a de r   r o l e   w i l l   b e   r e s po n s i b l e   f o r   r e c e i v i n a l l     t h e   c o l l e c t e da t a   f r o m   t h e   r e s t   o f   t h e   n o de s   a n f o r w a r d i n g   i t   t o   t h e   B S .   A l t h o ug h   t h e   s i z e s   o f   t h e   r e c e i v e d   da t a   pa c ke t s   a r e   us ua l l y   f i xe due   t o   da t a   f us i o n   a n a gg r e ga t i o n   e xe c ut i o n   o n   e v e r y   n o de ,   t h e   l e a de r   n o de   w o ul s t i l l   e xpe n m o r e   e n e rgy   t h a n   t h e   o t h e r   n o de s   d ue   t o   t h e   of t e n   l a rge   di s t a n c e   t o   t h e   B S .   T h e r e f o r e ,     t h e   s e l e c t i o n   of   t h e   l e a de r   n o de   h a s   t o   b e   a   c a r e f ul   pr o c e s s   i n   o r de r   t o   n o t   o ve r - c o n s um e   t h e   n o de ' s   e n e r gy .   S o m e   f r e que n t l y   us e f a c t o r s   f o r   l e a de r   s e l e c t i o n   a r e   t h e   r e s i du a l   e n e rgy   of   t h e   c a ndi d a t e   n o de   a nd  i t s   di s t a n c e   f r o m   t h e   B S .   I n   a dd i t i o n,   s o m e   m e t h o ds   c o n s i de t he   n u m b e r   o f   c o n n e c t i o n s   o c hi l d   n o de s .       3.   N ETWO R K   A N D   R A D I O   M O D EL     3. 1 .   N e tw o r k   m o d e l   In  o ur  w o r k,   w e   a s s um e   t h e   f o l l ow i n g .   a)   S e n s o r   n o de s   a r e   s t a t i o na r y   a n d   ra n do m l y   di s t r i b ut e i a   s q ua r e   f i e l d.   b)   T h e   B S   i s   s t a t i o na r y   a s   w e l l   a n d   de pl oy e o ut s i de   of   t h e   s e n s i n f i e l d   o o n e   o f   t h e   s y m m e t r i c   a xe s .     c)   T h e   n e t w o r i s   h o m o ge n e o us   s i n c e   a l l   s e n s o n o de s   ha v e   t h e   s a m e   r e s o ur c e s   c a pa b i l i t i e s .   d)   T h e   B S   i s   n o t   e n e r gy   c o n s t ra i n e d.     e)   E a c h   n o de   ha s   t h e   c a pa b i l i t y   t o   c o m m uni c a t e   w i t B S   di r e c t l y .     F i gu r e   3   s h o w s   a   r e p r e s e n t a t i o o f   o ur   n e t w o r m o de l .     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       D e t e r m i nat i on   of   t h e   K - op t i m a l   num be r   of   c ha i ns - bas e r ou t i ng  pr ot o c ol   f or m e b y   ( Sam ah  A l na j di )   921       F i gu r e   3 .   N e t w o r m o de l       3. 2 .   R ad i o   m od e l   T h e   s a m e   r a di o   m o de l   de s c ri b e i n   [23 24]   i s   a do pt e h e r e .           In  t hi s   m o de l ,   t o   t ra n s m i t   a L   b i t   m e s s a ge   a   d i s t a n c e   o f   d,   t he   ra di o   e xpe n ds   t h e   f o l l ow i n g:             (       )                                             (1)     T o   r e c e i v e   t h e   L   b i t   m e s s a ge ,   i n   t h e   m o de l ,   t h e   r a di o   e xpe n d s   t h e   f o l l ow i n g:         (   )                           (2)     T h e   s e n s o di s s i pa t e s               o r u nni n t h e   t ra n s m i t t e r ’s   o t h e   r e c e i v e r ’s   c i r c u i t r y .   I n   t h e   t r a n s m i s s i o n,   t h e   s e n s o w o ul a l s o   di s s i pa t e          ,   a nd   t h e   v a l ue   de pe n ds   o t h e   d i s t a n c e   b e t w e e n   t h e   s e n s o r   a n t h e   r e c e i v e r   n o de .   I n   a dd i t i o n ,   t h e   s e n s o w i l l   d i s s i pa t e   a ddi t i o na l   e n e r gy   i n   t h e   c a s e   o f   t r a n s m i s s i o n.     In  o ur   a do pt e c o m b i n e m o de l ,   i f   t h e   di s t a n c e   b e t w e e n   t h e   s e n s o r   a n t h e   r e c e i v i n n o de   i s   s m a l l ,   t h e   f r e e   s pa c e   m o de l   i s   us e d,   a nd  t h e   s e n s o w o ul di s s i pa t e                   ,   w he r e                     100  pJ / b i t / m 2   O t h e r w i s e ,   t h e   m ul t i p a t f a d i n g   m o de l   i s   us e d,   a nd  t h e   s e n s o w o ul di s s i p a t e                   ,   w h e r e                =   0 . 001 pJ / b i t / m 4.           4.   TH E   P R O P O S ED   S C H E M   O ur   I m p r o v e M ul t i - C h a i n   R o ut i ng  P r o t o c o l   (IM CRP c o n s i s t s   o s e ve r a l   p ha s e s   t h a t   a r e   e xe c ut e d   c oo pe r a t i v e l y   by   t h e   B S   a n s e n s o r   n o de s   t hr o ugh o ut   t h e   n e t w o r k’s   l i f e t i m e .   F i gu r e   s h o w s   t h e   IM CR P   e xe c ut i o n   m o de l   f r o m   t h e   s t a rt   t o   t h e   e n d   o f   t h e   n e t w o r k’s   l i f e t i m e .     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 .   19 ,   N o .   2 A ugus t   20 20  :     91 7   -   93 0     922       F i gu r e   4 .   P ha s e s   o f   IM CR P   pr o t o c o l       5. 1 .   D e c i s i o n   ab ou th e   n u m b e r   o c h ai n s   F o r m i n g   t h e   ri g ht   n u m b e r   o f   c h a i n s   (K i s   a i m po rt a nt   s t e i n   hi e r a r c h a l   r o ut i n p r o t o c o l s   s i n c e   i t   m a na ge s   l e s s   e n e r gy   c o n s um pt i o n .   T h e   o pt i m a l   K   v a l ue   i s   a f fe c t e by   m a n y   f a c t o r s ,   i n c l udi ng  t h e   us e e n e r gy   m o de l ,   t h e   n o de s ’  de n s i t y ,   t h e   B S   l oc a t i o n,   t h e   s i z e   of   t h e   s e n s i n f i e l a n o t h e r   f a c t o r s   [25] .   I n   o ur  pr o t o c o l ,   w e   a do pt e a n   a na l y t i c a l   m o de l   t ha t   i s   a pp l i c a b l e   t o   o ur   n e t w o r a n e n e r gy   m o de l s   t h a t   w e r e   de r i v e by   N .   A m i n i   e t   a l .   i [24] .   T h e   m o de l   gi v e s   a   ra n ge   o f   t h e   o pt i m a l   K   v a l ue s   b y                                          (                                    )   (3)     w h e r e   M   i s   t h e   s i de   o f   a   s qua r e   s e n s i ng  f i e l a n R   i s   t h e   di s t a n c e   f r o m   t h e   B S   t o   t h e   c e n t e r   o   t h e   s e n s i ng  f i e l d,   a s   p r e s e n t e i n   F i gu r e .   3.   T h e   m i ni m um   a n d   m a xi m u m   v a l ue s   a r e   gi v e by   t h e   f o l l ow i n g   e qua t i o n s ,   w h i c h   a r e   b a s e o t h e   f r e e   s pa c e   a n d   t h e   m u l t i pa t r a di o   m o de l s ,   r e s pe c t i v e l y .               (        )                          (      (             )                )   (4)           (        )                          (      (                                     )                )           (5)     T o   f i n t h e   o pt i m a l   K   v a l ue   a m o n t h e   gi v e n   ra n ge ,   a   s i m ul a t i o n   h a s   t o   b e   p e r f o r m e o n     t h e   n e t w o r b e fo r e   t h e   a c t u a l   de pl oy m e n t   o f   t h e   p r o t o c o l .   H ow e ve r ,   F i gu r e   s h o w s   t h a t   o u r   s i m ul a t i o n   w i t di f fe r e nt   s c e n a ri o s   a n a l l   t h e   v a r i o us   K   v a l ue s   g a v e   s i m i l a r   n e t w o r l i f e t i m e s .   T h e r e f o r e ,   t o   dy n a m i c a l l y   f i n t h e   o pt i m a l   K   v a l ue   by   t h e   B S   dur i ng  t h e   n e t w o r o p e r a t i o n,   w e   c a l c ul a t e   t h e   o pt i m a l   K   v a l ue   i n   o ur  pr o t o c o l   a s   t h e   a v e r a ge   o f            gi v e n   by   T o   f i n t h e   o pt i m a l   K   v a l ue   a m o n g   t h e   r a nge   gi v e n   by   t h e   pe r v i o us   e qua t i o n s ,   a   s i m u l a t i o n   ha s   t o   b e   pe r fo r m e o n   t h e   n e t w o r be f o r e   t h e   a c t ua l   de pl o y m e n t   o t h e   pr o t o c o l .   H ow e ve r ,   w e   c o n duc t e a   s i m ul a t i o n   w i t h   d i f fe r e nt   n e t w o r s i z e s   us i n g   a l l   t h e   v a ri o us   K   v a l ue s .   F i gu r e s   5   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       D e t e r m i nat i on   of   t h e   K - op t i m a l   num be r   of   c ha i ns - bas e r ou t i ng  pr ot o c ol   f or m e b y   ( Sam ah  A l na j di )   923   a n s h o w   t h e   r e s ul t s   w h e r e   a l l   t h e   v a l ue s   i n   t h e   r a n ge   re s ul t   i n   s i m i l a n e t w o r l i f e t i m e s .   A c c o r di n g   t o     t h e   r e s ul t s ,   t h e   o pt i m a l   K   v a l ue   v a r y   a s   t h e   n o de s   de n s i t y   c h a n ge .   T h e r e fo r e ,   t o   dy n a m i c a l l y   f i n d   t h e   o pt i m a l   K   v a l ue   by   t h e   B S   dur i n t h e   n e t w o r o pe r a t i o n ,   w e   c a l c ul a t e   t h e   o pt i m a l   K   v a l ue   i n   o u r   p r o t o c o l   a s     t h e   a v e ra ge   o f              gi v e n   b y :               (            (         )               (         )   )   (6)     N o t e   t ha t   t he   K   v a l u e   w i l l   c ha ng e   t h ro u g ho u t   t he   ne t w o rk   l i f e t i m e   d e p e nd i ng   o nu m b e o f   l i v e   no d e s   N .           (a )     (b )     (c )     F i gu r e   5 .   T h e   l i f e t i m e   o f   1002  m e t e n e t w o r v s .   t h e   n u m b e o f   c o n s t r uc t e c h a i n s :   (a )   100 - n o de   n e t w o r k;   (b 200 - n o d e   n e t w o r k;   (c 30 0 - n o de   n e t w o r k         (a )     (b )     (c )     F i gu r e   6 .   T h e   l i f e t i m e   o f   2002  m e t e n e t w o r v s .   t h e   n u m b e o f   c o n s t r uc t e c h a i n s :   (a )   100 - n o de   n e t w o r k;   (b 200 - n o de   n e t w o r k;   (c 30 0 - n o de   n e t w o r k       5. 2 .   N o d e s   d i v i s i o n     T h e   K - m e a n s   c l us t e r i ng  a l go r i t hm   i s   us e i n   t h i s   p r o t o c o l   t o   di v i de   t h e   n o de s   i n   t h e   a r e a   i nt o   K   gr o ups   b a s e o n   t h e   E uc l i de a di s t a n c e s   b e t w e e n   t h e   n o de s .   T h e r e f o r e ,   t h e   r e s ul t   o f   t hi s   c l us t e r i ng  a l go r i t hm   i s   e a c h   n o de   j o i n i n i t s   n e a r e s t   g r o up  o f   n o de s .   A t   f i r s t ,   K   ra n do m   v i rt u a l   po i nt s   a r e   c h o s e n   t o   b e   t h e   i n i t i a l   c e n t r o i po i n t s ,   a n e a c h   c e n t r o i w i l l   p r e s e nt   a   g r o up.   T h e n,   t h e   E uc l i de a n   di s t a n c e   b e t w e e n   n o de s   a n a l l   K   c e n t r o i po i n t s   i s   c a l c u l a t e d   i n   o r de r   f o r   e a c n o de   t o   j o i n   t h e   g r o up  w i t t h e   n e a r e s t   c e n t r o i d .   N o t e   t h a t   t h e   E uc l i de a d i s t a n c e   i n   t h e   t w o - di m e n s i o na l   s pa c e   b e t w e e n   p o i n t s       (           )     n     (           )   i s   gi v e by :       (       )   (           )     (           )           (7)     W h e n   a l l   n o de s   a r e   i ni t i a l l y   a s s i gn e i n t o   t h e   K   gr o ups ,   a   l oo i s   e x e c ut e w h e r e   t h e   po s i t i o n s   o   t h e   c e n t r o i po i nt s   a r e   r e c a l c u l a t e d   i n   e a c i t e ra t i o n   b a s e o t h e   l o c a t i o n s   o f   t h e   m e m b e r   n o de s   of   t h e   g r o up.   N o de   a s s i gn m e n t s   ke e c ha n g i n s i n c e   t h e   n e a r e s t   c e nt r o i i de n t i t y   m a y   c h a n ge   du ri n t h e   p r o c e s s .   T h e   l o o p   e n ds   w h e n   n o   f urt h e c ha n ge s   i n   t h e   c e nt r o i po i n t s ’  po s i t i o n s   o c c ur   a n t h e   f i na l   a s s i g nm e nt   o f   K   gr o ups   i s   b r o a dc a s t e o ve r   t h e   n e t w o r k.   T h e   c e n t r o i o f   a   g r o up  o f   s   m e m b e r   n o de s   i s   gi v e by :   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 .   19 ,   N o .   2 A ugus t   20 20  :     91 7   -   93 0     924               (       )   (                                   )       (8)     N o t e   t h a t   t h e   w h o l e   p r o c e s s   of   n o de s   di v i s i o n   i s   pe r f o r m e r e m o t e l y   by   t h e   B S   n o de   a t   t h e   s t a r t   of  t h e   n e t w o r o pe r a t i o a n r e - e xe c ut e i c a s e   o f   t h e   c ha n ge   of   t h e   o pt i m a l   k   v a l ue .         Algorithm: N etwork division using k - means   1   Choose K random points as the initial centroid points      2   Assign a group ID to each centroid   3   for   each node i in {List of all alive nodes}  do   4           Calculate distance between node i and all K centroid points.    5           Assign node i to the group of nearest centroid point       6   end   for   7   for   each group j in {List of all K groups}  do     8           Recalculate  the  centroid  point  position  based  on  the  coordinates of group j’s nodes. Equation 5 applied.    9   end for    1 0:   Compare the last and pervious centroid points positions.   1 1:   Repeat steps 3 - 10 until no changes in the centroid points position.        5. 3 .   C h ai n   c o n s tr u c ti o n   In   c o n t ra s t   t o   p r e v i o us   ph a s e s ,   t h e   c ha i n   c o n s t r uc t i o n   i s   a   d i s t ri b ut e pr o c e s s   i n   w h i c h   a l l   t h e   n o de s   ha v e   t o   c o m m u n i c a t e   a n c o o pe r a t e   t o   c o n s t r uc t   t h e   c h a i n   o f   t h e i g r o up.   H ow e ve r ,   t h e   n o de s   c o m m uni c a t i o n   du ri n g   t hi s   p ha s e   i s   l i m i t e t o   o n l y   i n s i de   t h e i r   g r o up,   a nd  e a c h   c h a i i s   c o n s t r uc t e i n de pe n de n t l y   of   t h e   r e s t   of   t h e   K   c h a i n s .   T h e   c h a i n i ng  m e c h a ni s m   i s   do n e   us i n a n   e nha n c e gr e e d y   a l go ri t hm   [5] .   T h e   a l go r i t h m   a l l o w s   t h e   n o de   t o   h a v e   m ul t i p l e   c o n n e c t i o n s ,   a n m o r e   n o de s   j o i n i ng  t h e   c h a i n   l e a ds   t o   b e t t e r   c h o i c e s   fo r   t h e   r e m a i n i ng  n o de s   t o   c o n n e c t .   M o r e o ve r ,   i n   t h e   c a s e   o f   n o de   de a t h,   o nl y     t h e   a f f e c t e c h a i i s   r e - c o n s t r uc t e d .         Algorithm: Chain formation by enhanced greedy algorithm   1   for   each group i in {List of K groups}  do   2          Set the node which is nearest to centroid as EndNode   3          for   each node j in {List of nodes didn’t join the chain}  do   4                Calculate distance between node j and EndNode   5          end   for   6          Select the nearest node to be NextNode   waiting to join the chain   7          for   each node h in {List of nodes joined the chain} do   8                Calculate distance between node h and NextNode   9          end   for   1 0:              NextNode  join  chain  by  connecting  to  nearest  node  on  chain  i   1 1:              EndNode ← NextNode   1 2:             Repeat steps 3 - 10 until all nodes in the group join the chain   1 3:   end   for       5. 4 .   Le ad e r s   an d   h e ad   l e ad e r   s e l e c ti o n     T o   c h oo s e   b e t t e r - f i t t i ng  n o de s   t o   be   t h e   c h a i n   l e a de r s   (CL ),   t h e   s e l e c t i o n   m e t h o de pe n ds   o n     t h e   w e i gh t   o f   t h e   n o de   t h a t   c o n s i de r s   t w o   pa r a m e t e r s :   t h e   di s t a n c e   o f   t h e   n o de   t o   t h e   B S   a n i t s   r e s i dua l   e n e r gy ,   a s   s h o w n   i n   ( 9 ) .   I n   e v e r y   r o un d ,   t h e   c o m b i n e w e i ght   o e a c h   n o de   i s   c o m pa r e w i t h   o t h e r   n o de s   i n   t h e   s a m e   c ha i n,   a n d   t h e   n o de   w i t t h e   m i n i m u m   w e i ght   i s   s e l e c t e a s   t h e   c h a i l e a de r   o f   t h e   r o u n d.                  (   )                                     (   )                         (   )               (9)     F urt h e rm o r e ,   o n e   l e a de r   n o de   o ut   o t h e   K   c h a i n   l e a de r s   i s   s e l e c t e a s   t h e   h e a l e a de r   (H L t o   be   r e s po n s i b l e   f o r   s e n di ng  d a t a   t o   t h e   B S .   T h e   H L   c o l l e c t s   t h e   da t a   f r o m   o t h e r   l e a de r s   t hr o ug h   a   c h a i n   t o po l o g y   t h a t   w a s   f o r m e a n d   s t a rt e f r o m   t h e   H L   i t s e l f .     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       D e t e r m i nat i on   of   t h e   K - op t i m a l   num be r   of   c ha i ns - bas e r ou t i ng  pr ot o c ol   f or m e b y   ( Sam ah  A l na j di )   925     Algorithm: Leaders and head leader selection   1 :   for   each chain i in {List of K chains}  do   2 :          for   each node j in {List of nodes in chain i}  do   3 :                Calculate weight of node i.                  weight[i]=residual energy[i]/distanceToBS[i]   4 :          end   for            5 :          Select the node with minimum(weight) to be LeaderNode of chain i   6 :   end for   7 :   S e l e c t   t h e   l e a d e r   n o d e   w i t h   m i n i m u m ( w e i g h t )   t o   b e   H e a d L e a d e r   o f   network       5.   EV A LU A TI O N   A N D   S I M U LA TI O N   R ES U LTS   5. 1 .   S i mu l ati o n   p ar am e te r s   T o   e v a l ua t e   t h e   pe r f o r m a n c e   of   t h e   IM CR P ,   w e   s i m ul a t e t h e   IM CR P ,   IE E P B ,   a n P E G A S IS   pr o t o c o l s   by   us i n g   M A T L A B   2017 a .   T h e   e v a l ua t i o c ri t e r i a   a do pt e i t hi s   p a pe r   a r e   t h e   f o l l ow i n g:     a)   N e t w o r l i f e t i m e     b)   D e l a y     c)   O v e r h e a d   T h e   n e t w o r a nd  e n e r gy   pa ra m e t e r s   us e d   i t hi s   s i m u l a t i o a r e   s h o w n   i T a b l e   2 .         T a b l e   2 .   S i m u l a t i o p a r a m e t e r s   P a ra m e t e r   V a l u e   N u m b e r   o d e p l o y e d   n o d e s   (N )   1 0 0 ,   2 0 0 ,   a n d   3 0 0   D e p l o y m e n t   a r e a   1 0 0   *   1 0 0   m   Ba s e   S t a t i o n   l o c a t i o n   (5 0 , 1 7 5 )   In i t i a l   e n e r g y   0 . 5   J               5 0   n J / b i t          1 0 0   p J / b i t / m 2          0 . 0 0 1 3 p J / b i t / m 4   T h re s h o l d   d i s t a n c e               S i z e   o d a t a   p a c k e t   2 0 0 0   b i t s   D a t a   a g g r e g a t i o n   e n e r g y   5   n J / b i t       5. 2 .   S i mu l ati o n   r e s u l ts     T h e   r e s ul t s   p r e s e nt e a r e   b a s e o n   t h e   a v e ra ge   o f   10  s i m u l a t i o n s .   T h e   s i m u l a t i o n s   a r e   pe r f o r m e w i t h   t hr e e   s c e n a r i o s   r e ga rdi ng  t h e   n u m b e r   o f   de pl oy e s e n s o r   n o de s .   T h e r e f o r e ,   t h e   n u m b e r   o f   c h a i n s   i   t h e   IM CR P   pr o t o c o l   v a r i e s   fo r   e a c h   s c e n a ri o   s i n c e   t h e   nu m b e r   o f   n o de s   a ff e c t s   t h e   o pt i m a l - K   v a l ue ,   a s   m e nt i o n e d   i S e c t i o 4 .         5. 2 . 1.   N e tw o r k   Li f e ti m e     T h e   n e t w o r l i f e t i m e   m a y   be   de f i n e i t w o   w a y s :     a)   T h e   t i m e   f r o m   w h e n   t h e   n e t w o r b e gi n s   o pe r a t i ng  u nt i l   t h e   d e a t h   o f   t h e   f i r s t   n o de ,   o r     b)   T h e   t i m e   f r o m   w h e n   t h e   n e t w o r b e gi n s   o pe r a t i ng  u nt i l   t h e   d e a t h   o f   t h e   l a s t   n o de .     H ow e ve r ,   w e   a do pt   t h e   s e c o n de f i n i t i o n   i n   t hi s   p a pe r   a nd  t h e   r e s u l t s   a r e   a s   f o l l ow s .   In   F i gu r e   7 ( a ),   t h e   s i m u l a t i o n   o f   t h e   1 00 - n o de   n e t w o r s h o w s   t ha t   P E G A S I S   o pe r a t i o n   e n ds   a t   1664   r o unds   a nd  t h e   IE E P e n ds   a t   1881 .   M e a n w hi l e ,   o u r   IM CR P   p r o t o c o l   c o n t i nue f o r   1970  r o u n ds   w i t h   a   4. 7 i m p r o v e m e n t   o v e r     t h e   IE E P B   a n d   a n   18. 4 o v e r   t h e   P E G A S IS .   I n   F i gu r e   7 (b ),   t h e   s i m ul a t i o n   o f   t h e   200 - n o de   n e t w o r s h o w s   t h a t   t h e   l i f e t i m e   o f   P E G A S IS   s t a y s   t h e   s a m e   a s   i n   t h e   100 - n o de   n e t w o r w i t h   16 63  r o un ds   a nd  t h e   IE E P o pe r a t i o n   e n de a t   1831  w i t h   2. 7%  l e s s   pe r fo r m a n c e   i n   c o m pa r i s o n   w i t h   t h e   100 - n o de   s c e n a ri o .   O n   t h e   o t h e ha n d ,   t h e   IM CR P ’s   l i f e t i m e   i n c r e a s e a s   e xpe c t e a nd  c o n t i nue t o   2258   r o u n ds ,   t h us   gi v i n g   a   23. 3%  i m p r o v e m e n t   o v e r   t h e   IE E P B .   F i g u r e   7 (c s h o w s   t h e   l a s t   s c e n a r i o   w i t h   t h e   300 - n o de   n e t w o r k’s   l i f e t i m e   r e s ul t s .   T h e   P E G A S IS   p r o t o c o l   a ga i n   g a v e   a   s i m i l a r   pe r f o r m a n c e   a s   i n   100  a n 2 00 - n o de   n e t w o r s c e n a ri o s .   F o r   t h e   I E E P B ,   t h e   l i f e t i m e   e n ds   a t   o nl y   1785  r o u n ds ,   w h i c h   pr o v e s   t h a t   t h e   IE E P B   pe r f o r m a n c e   de c r e a s e s   a s   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 .   19 ,   N o .   2 A ugus t   20 20  :     91 7   -   93 0     926   t h e   n u m b e r   o f   n o de s   i n c r e a s e s .   T h e   hi g h   n o de   de n s i t y   i n   t h e   IE E P B   c a us e s   l a r ge r   e n e r gy   c o n s um pt i o n   by   s e n s o r   n o de s   s i n c e   e a c h   n o de   w i l l   ha v e   a   gr e a t e r   num b e r   o f   c o n n e c t e n o de s   o r   c h i l n o de s .   T h e r e f o r e ,     t h e   e n e r gy   s pe n t   i r e c e i v i n da t a   i n c r e a s e s   a s   w e l l .   H ow e ve r,   t h e   IM CR P   do e s   n o t   h a v e   t h i s   p r o b l e m   due   t o   t h e   o pt i m a l - K   m o de l   t ha t   t a ke s   i n t o   c o n s i de ra t i o n   t h e   n o d e s ’  de n s i t y .   T h e   pr o po s e pr o t o c o l   ga ve   2034   r o u n ds   w i t h   t h e   300 - n o de   n e t w o r k,   t h us   gi v i n a   9 i m p r o v e m e n t   o ve r   t h e   IE E P B   a n 17. 4%  o v e r     t h e   P E G A S IS .   T h e   f i gu r e s   s h o w   t ha t   a s   s o o n   a s   s o m e   n o de s   s t a r t i ng  t o   di e ,   t h e   r e s t   o f   n o de s   s t a r t   t o   l o s e   m o r e   e n e r gy   a n di e   a s   w e l l .   T hi s   ha ppe n   due   t h e   di s t a n c e   be t w e e n   t h e   n o de s   i n   t h e   c h a i n   ge t t i ng  l a rge r   t h e r e f o r e   l o s i n e n e rgy   be c o m e s   h i g h e r.   T h e r e f o r e ,   t h e   r e - c l us t e r i ng  o f   t h e   n e t w o r a s   i n   IM CR P   h e l a   l o t   i n   t hi s   c a s e   w h e r e   t h e   s t i l l   a l i v e   n o de s   g e t   t h e   o ppo r t u n i t y   t o   j o i n   t h e i r   ne a r e s t   a l i v e   n o de s   c l us t e r   a f t e r   t h e   de a t h   o f   t h e i r   n e a r e s t   de a d   n o de s .           (a )         (b )     (c )     F i gu r e   7 .   T h e   n e t w o r l i f e t i m e   o f   1002  m e t e n e t w o r k:   (a )   1 00 - n o de   n e t w o r k;   (b 200 - n o d e   n e t w o r k;     (c 300 - n o de   n e t w o r k       5. 2 . 2.   D e l ay   W e   m e a s ur e t h e   t ra n s m i s s i o n   de l a y   a s   t h e   m a xi m u m   n u m b e r   o f   h o ps   o r   " n o de s "   t ha t   a   da t a   pa c ke t   t r a v e l s   i n   o r de r   t o   r e a c h   t h e   c h a i l e a de r .   T h e   s i m ul a t i o i n v o l v e t h e   de l a y   i n   t h e   IE E P B   a nd  IM CR P   pr o t o c o l s   i n   w h i c h   t h e   f i r s t   i s   a   s i n g l e - c h a i n   p r o t o c o l   a nd  t h e   l a t t e r   i s   a   m ul t i p l e - c h a i n   p r o t o c o l .   T h us ,     t h e   de l a y   r e s ul t   i n   t h e   I E E P B   i s   v e r y   l a rge   i n   a l l   t hr e e   s c e na r i o s   c o m pa r e t o   t h e   IM CR P   due   t o   t h e   s i n gl e   c h a i n   r o ut i n g ,   a s   s h o w n   i n   F i gu r e   8.   I n   t h e   100 - n o de   n e t w or k ,   t h e   IM CR P   n e t w o r w i l l   s t a rt   w i t di v i d i ng  t h e   100  n o de s   i n t o   c h a i n s   b a s e o n   ( 3 ) ,   ( 4 ) ,   a n ( 5 )   w hi l e   t h e   IE E P B   n e t w o r w i l l   f o r m   a   s i ngl e   c h a i n   c o n t a i ni n a l l   t h e   100  a l i v e   n o de s .   T h e r e f o r e ,   F i gu r e   8 (a s h o w s   t h a t   t h e   IE E P B   h a s   a n   a v e r a ge   de l a y   o 40   h o ps   a n t h a t   t h e   IM CR P   ha s   a n   a v e r a ge   de l a y   of   18  h o ps   due   t h e   s m a l l e r   l e ngt h   o f   c h a i n s   c o m pa r e t o   Evaluation Warning : The document was created with Spire.PDF for Python.