I nte rna t io na l J o urna l o f   E lect rica l a nd   Co m p ute E ng in ee ring   ( I J E CE )   Vo l.   7 ,   No .   1 Feb r u ar y   201 7 ,   p p .   3 0 9 ~ 3 1 5   I SS N:  2 0 8 8 - 8708 DOI : 1 0 . 1 1 5 9 1 / i j ec e . v7 i 1 . p p 3 0 9 - 3 1 5          309       J o ur na l ho m ep a g e h ttp : //ia e s jo u r n a l.c o m/o n lin e/in d ex . p h p /I JE C E   I m pro v e m en a Netw o rk  P la nnin g  using  H eu ristic  Alg o rith m   to M ini m i z Co st  o Dista nce  bet w een Nodes  in  Wir el ess  Mes Netw o rk s       Sh iv a n Q a s i m   A m ee n,  Ra v ie  Cha nd re n M un iy a nd i   S OFT A M   De p a rtme n t,   F a c u lt y   o In f o rm a ti o n   S c ien c e   a n d   T e c h n o l o g y ,   Un iv e rsiti   Ke b a n g sa a n   M a lay sia ,   M a la y sia       Art icle  I nfo     AB ST RAC T   A r ticle  his to r y:   R ec eiv ed   Oct  1 2 ,   2 0 1 6   R ev i s ed   Dec   2 0 ,   2 0 1 6   A cc ep ted   J an   4 ,   2 0 1 7       W irele ss   M e sh   Ne t w o rk s   ( W M N)  c o n sists   o f   w ir e les sta ti o n th a a re   c o n n e c ted   w it h   e a c h   o th e i n   a   s e m i - sta ti c   c o n f ig u ra ti o n .   De p e n d in g   o n   th e   c o n f ig u ra ti o n   o f   a   W M N,  d iff e r e n p a th s b e tw e e n   n o d e o ff e d iffere n lev e ls   o f   e ff icie n c y .   On e   a re a o f   re se a rc h   w it h   re g a rd   to   W M is  c o st   m in i m iza ti o n .   M o d if ied   Bin a ry   P a rti c le  S wa r m   Op ti m iza ti o n   (M B P S O)   a p p ro a c h   w a u se d   to   o p ti m ize   c o st.  Ho w e v e r,   m in im iz e d   c o s d o e n o t   g u a ra n tee   n e tw o rk   p e r f o r m a n c e .   T h is  p a p e th u s,  m o d if ied   th e   m i n im iza ti o n   f u n c ti o n   to   tak e   in to   c o n si d e ra ti o n   t h e   d ista n c e   b e tw e e n   th e   d if f e r e n n o d e s   so   a to   e n a b le  b e tt e p e rf o rm a n c e   w h il e   m a in tain in g   c o st  b a l a n c e .   T h e   re su lt we re   p o siti v e   w it h   th e   P DR  sh o w in g   a n   a p p ro x i m a te  i n c re a se   o 1 7 . 8 3 %   w h e re a s th e   E2 d e lay   sa w   a n   a p p ro x im a te d e c re a se   o f   8 . 3 3 % .   K ey w o r d :   Heu r is tic  al g o r it h m   MB P SO   Min i m ize  co s t o f   d is tan ce   R o u ter s   W ir eless   m e s h   n et w o r k s   Co p y rig h ©   2 0 1 7   In stit u te o A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e   Al rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   Sh i v a n   Qasi m   Am ee n ,     SOFT A Dep ar te m e n t,   Facu lt y   o f   I n f o r m a tio n   Scie n c an d   T ec h n o lo g y ,   Un i v er s it y   Keb an g s aa n   Ma la y s ia  ( UKM ),     J alan   R ek o ,   B ar u B an g i,  Sela n g o r   Dar u l E h s an   4 3 6 0 0 ,   Ma la y s ia .   E m ail: S h v an _ 8 9 9 0 @ y a h o o . co m       1.   I NT RO D UCT I O N   W ir eless   Me s h   Ne t w o r k   ( W MN )   is   d ef in ed   as  s e m i - s t atic  t y p o f   m u lti - h o p   w ir ele s s   n et w o r k   w h er n u m b er   o f   w ir eles s   s t atio n s   ar co n n ec ted   to   o n o r   m o r g a te w a y s .   T h i m p o r ta n ce   o f   ( W MN )   led   to   b u s ed   in   s ev er al  ar ea s   s u c h   as  [ 1 - 1 2 ] .   T h ese  w ir eless   s ta tio n s   in   ( W MN )   ar k n o w n   to   h av v er y   li m i ted   m o b il it y   o r   n o   m o b ilit y   at  al [ 1 3 ] .   B y   u s i n g   m e s h   n et w o r k   p r o to co l,  th s tatio n s   wh ich   ar co m m o n l y   p o w er ed   b y   b atter y   co m m u n i ca te  w it h   ea c h   o t h er   to   b r o ad ca s m es s ag e s   a n d   ex ec u te   o th er   tas k s .   T h er ar t w o   t y p e s   o f   n o d es  in   W MN m es h   r o u ter s   a n d   m e s h   clie n ts .   I n   o r d er   to   s u p p o r m e s h   n et w o r k i n g ,   m es h   r o u ter s   h a v e   ad d itio n al  r o u t i n g   f u n ctio n s   s u c h   a s   i ts   m u l tip le  b u ilt - n o   w ir eles s   i n ter f a ce   to   i m p r o v e   t h f le x ib ilit y   o f   t h n et w o r k   a n d   its   lo w   tr an s m is s io n   p o w er   th r o u g h   m u lt i - h o p   co m m u n icatio n .   A   W MN   is   al s o   r eliab le  an d   o f f er s   r ed u n d a n c y .   I f   o n e   n o d f ails   to   o p er ate,   th r e s o f   t h n o d es  i n   n et w o r k   ca n   s ti ll   co m m u n icate   w i th   o n a n o th e r   as  its   n ei g h b o r   w il s i m p l y   f i n d   an o t h er   r o u te.   D u to   d y n a m ic  r o u t in g ,   n o d es  h av t h ca p ab ilit y   to   ch o o s e   th q u ic k es p ath   to   s e n d   in f o r m atio n .   I n   f u l m e s h   to p o lo g y ,   ev er y   n o d e   in ter ac ts   a n d   co m m u n icate s   w it h   ea c h   o th er   n o j u s b ac k   an d   f o r th   to   t h ce n tr al  r o u ter   an d   t h is   h elp s   co n f i g u r r o u tes in   m o r d y n a m ic  m a n n er .   I is   e v id en th at   W MN s   ar s elf - co n f i g u r i n g   an d   s el f - h ea li n g .   Ho w e v er ,   t h er a r i m m i n en t   is s u e s   th at  t h e s n et w o r k s   f ac e.   lar g n u m b er   o f   o p en   r ese ar ch es  d is c u s s   W MN   li m itat io n s   s u c h   a s   lo ad   b alan cin g ,   en er g y   o p ti m iza ti o n ,   r o u te  o p tim izat io n ,   co s t   m in i m iza tio n ,   u n s p lit tab le  f lo w ,   an d   li m ited   r eso u r ce s .   T h is   w o r k   f o c u s es  o n   co s m i n i m izatio n   f o r   estab lis h in g   n et w o r k   b y   u s i n g   h e u r is tic  al g o r ith m s .   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2 0 8 8 - 8708     I mp r o ve men t a t Netw o r P la n n in g   u s in g   Heu r is t ic  A lg o r ith to   Min imiz C o s t o f D is ta n ce     ( S h iva n   Q. A . )   310   I n   m e s h   n et w o r k   co m m u n i ca tio n ,   th d e v ices   ca n   b g en er all y   ca teg o r ized   in to   th r e e;  clien t s ,   r o u ter s   an d   g ate w a y s .   Gate wa y s   p r o v id s er v ice s   f o r   th e   n et w o r k   w h i le  r o u ter s   r ela y   t h d at t h at  tr av el s   b et w ee n   g ate w a y s   a n d   th n et w o r k   s u b s cr ib er s .   Fi g u r 1 ,   s h o w s   t h i n f r a s tr u ct u r o f   W MN .           Fig u r 1 .   W MN   in f r astr u ct u r e.   A d ap ted   f r o m   [ 1 4 ]       I n   Fig u r 1 ,   th d as h ed   an d   s o lid   lin es  i n d icate   w ir eles s   an d   w ir ed   lin k s   r esp ec ti v el y .   Fo r   m ed i u m   ac ce s s   co n tr o l,  th in f r astr u ct u r ca n   b r ed u ce d   to   b ase,   r ela y   an d   s u b s cr ib er .   I n   t h is   ca s e,   it  is   ass u m ed   th a in f o r m atio n   o r   d ata  p ac k e m u s t   tr av el   f r o m   a   b ase   s tatio n   ( B S)  to   s u b s cr ib er   s tat io n   ( SS )   v ia  r ela y   s tatio n   ( R S)  in   a n   u n s p litt ab le  f lo w   al th o u g h   it is   p o s s ib le  to   r o u te  t h p ac k et  i n   m u lti - p ath   m a n n er .   No d es  m a y   in ter f er w ith   o n e   an o th er   w h e n   th e y   ar r eb r o a d ca s tin g   at  th s a m ti m w it h in   s m al l   r eg io n   o n   t h s a m c h a n n el.   T h is   is   ca lled   d en s m e s h   n et w o r k   d ile m m a.   Am o n g   t h wa y s   to   r eso l v th is   is s u is   s p litt i n g   n et w o r k   r eso u r ce s   i n   th eir   o w n   ch a n n el  s u c h   as  s p lit tin g   ti m i n   ti m ch a n n el  a n d   f r eq u e n c y   in   f r eq u e n c y   c h a n n el  [ 1 5 ] .   No w   th at  t h er ar r eso u r ce s   n ee d   to   b h an d led ,   q u esti o n   o f   h o w   to   allo ca te  th ese  a v ailab le  r eso u r ce s   ar i s e s   w h ile  ta k i n g   o th er   f ac to r s   i n t o   co n s id er atio n   as  w ell.   I n   w ir ele s s   n et w o r k   r o u te  p la n n i n g ,   r eso u r ce   allo ca tio n   p la y s   an   i m p o r tan r o le  to   g iv a   co s t - an d - en er g y - e f f icie n s o l u tio n .   He u r is tic  ap p r o ac h   to   s o lv p ath   p lan n in g   in   w ir ele s s   n e t w o r k   is   s e en   as  o n o f   th e   m o s t p o p u lar   r esear ch   ar ea s   i n   th r ec en y ea r s   [ 1 6 ] .   P r o p o s ed   h eu r i s tic  al g o r ith m   to   m i n i m ize  th e   n u m b er   o f   tr an s m is s io n   tr ee   a n d   in d ir ec tl y   co n s er v e   b an d w id t h .   T h p r o p o s ed   alg o r ith m   h o w ev er   w as  b u ilt  to   a llo w   m u lticas p r o to co in s tead   o f   s in g le - p ath .   I n   an o th er   p ap er   [ 1 7 ] ,   im p le m e n ted   an co lo n y   o p ti m izatio n   i n t o   th eir   an y ca s r o u t in g   p r o to co in   th ai m   to   s elec p r o p er   ac ce s s   g ate w a y   in   W MN .   C o m b in in g   d is tr i b u ted   co m p u ti n g   w i th   h eu r i s t ic  s ea r ch i n g   o f   a n t   co lo n y   al g o r it h m ,   th e   g ate w a y   s elec tio n   w a s   tr ea ted   a s   a n   an y ca s t   s er v ice   [ 1 8 . A n al y z ed   d if f er e n t   m eta - h eu r i s tic  m et h o d s   to   co n s id er   th p lace m e n o f   m es h   r o u te r s   in   W MN s .   T ak i n g   co n n ec t iv it y   a n d   co v er ag e   p r o b lem s ,   v ar io u s   s ch e m e s   i n clu d in g   g e n etic  a lg o r it h m ,   s i m u lated   a n n ea l in g ,   tab u   s ea r c h ,   a n d   h ill  cl i m b i n g   w er u s ed   to   an al y ze   t h eir   b eh av io r s .   T h au t h o r s   th e n   u s e d   Frie d m a n   test   to   co m p ar th s i m u latio n   r esu l ts .   Her e,   it  h as  b ee n   f o u n d   t h at  d if f er e n al g o r ith m s   w o r k   b et ter   th an   th o t h er s   w h e n   s u b j ec ted   to   d if f er en t   s itu a tio n s   [ 1 9 ] .   I n   th eir   e f f o r to   m ax i m ize  t h s er v iced   n u m b er   o f   clie n t s   o r   s u b s cr ib er s   in   W MN ,   th e y   d ev elo p ed   lo ad - b ased   g r ee d y   al g o r ith m   i n te g r ated   w ith   lo ad - b ased   MCM  al g o r ith m   to   o f f er   d ela y - co n tr ain ed   a n d   i n ter f er e n ce - f r ee   s o lu t io n   to   co n s tr u ct  m u ltic ast  tr ee s   f o r   t h n et w o r k   [ 2 0 ] .   P r o p o s ed   g en et ic   alg o r ith m   to   s o l v n o d p lace m en t p r o b lem   i n   w ir eles s   m esh   n et w o r k .   B y   e m p lo y i n g   d i f f er en m u tatio n   a n d   s elec tio n   o p er ato r s   as  w el as   s ize  o f   g ia n co m p o n e n t,  t h e   au t h o r s   co n s id er ed   W eib u ll   d is tr ib u tio n   f o r   th e   m es h   clien ts   [ 2 1 ] C o m b in ed   m u lti - o b j ec tiv P ar ticle  Sw ar m   Op ti m izatio n   an d   Ge n etic  A l g o r ith m   to   d ev is a   s w ar m - b ased   al g o r ith m   to   s o l v W MN   p lan n i n g   p r o b le m s   o f   th r ee   m o d el s .   T h th r ee   m u lti - o b j ec tiv m o d el s   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I J E C E   Vo l.  7 ,   No .   1 Feb r u ar y   2 0 1 7   3 0 9     315   311   ar lo ad - b alan ce d ,   in ter f er e n c an d   f lo w - ca p ac it y   m o d els   [ 2 2 ] .   A d ap ted   n e w   ap p r o ac h   o f   p laci n g   m es h   r o u t er   n o d es  in   W MN   t h r o u g h   h e u r is t ic  tab u   s ea r c h .   A ck n o w led g i n g   t h at  W MN   o p tim izatio n   p r o b lem   i s   o f ten t i m e s   NP - co m p lete,   t h au th o r s   e x p lo r th s o lu t io n   s p ac at  th s a m ti m a v o id   g ettin g   s t u ck   i n   lo ca l   m i n i m b y   m a x i m izi n g   th s iz o f   g ia n t c o m p o n e n ts .       2.   P RE VIOU S AP P RO ACH   C r itical  d es ig n   f ac to r s   o f   W MN s   b r in g   f o r th   d i f f er e n c h alle n g i n g   i s s u es   r an g i n g   f r o m   th e   p h y s ica l   la y er   to   th ap p licatio n   la y er   an d   it  is   ap p ar en t h at  m a n y   p r o b lem s   s till   r e m ain   [ 1 5 ] .   P r esen ted   v ar io u s   h eu r i s tic  m e th o d s   to   estab lis h   w ir eless   m es h   n e t w o r k   in   I E E E   8 0 2 . 1 6 in   an   ec o n o m ic al  w a y .   T h w o r k   p r o p o s ed   lo w   co s R a n d   B in   o r d er   t o   co m p en s ate  f o r   b an d w id th   d e m a n d   o f   th cl ien ts .   A lt h o u g h   th e   m et h o d s   ap p ea r   r o b u s t,  th e y   s u f f er   f r o m   s ev er al  l i m itatio n s .   Af ter   ca r e f u o b s er v a tio n s ,   it  h as  b ee n   f o u n d   t h at   [ 1 5 ]   f ailed   to   r ef lect  th e   s i g n i f ica n ce   o f   d is ta n ce   b et w ee n   s tatio n s   in   th e   n e t w o r k .   Fo r   e x a m p le,   i f   n o d is   d ed icate d   to   b r o u tin g   s ta ti o n   o r   b ase  s tatio n   to   s er v o n s u b s cr ib er ,   ig n o r i n g   t h n o d e' s   d is ta n ce   f r o m   th s u b s cr ib er   m i g h i m p ac t h q u ali t y   o f   co m m u n ica tio n   i f   t h s u b s cr ib er s   d i s tan ce   f r o m   t h n o d is   s m all   ev en   i f   th co s is   h i g h er .   Fi g u r 2 ,   is   g r ap h   s h o w i n g   p o s s ib le  lin k s   b et w ee n   n o d es  w h er th b est  s o lu tio n   is   e m b o ld en ed .           Fig u r 2 .   E x a m p le  o f   a n   o p ti m al  s o lu tio n .   A d o p ted   f r o m   [ 1 5 ]       I is   k n o w n   t h at  d i g ital  s ig n al  atten u ates  d u r in g   tr an s m is s io n .   I n   i n s ta n ce s   w h er t h e   d is tan ce   b et w ee n   t w o   n o d es  g et s   lar g er ,   th atte n u atio n   also   g r o ws  b ig g er .   I n   t h eir   ef f o r to   m in i m ize  t h co s o f   estab lis h in g   th e   n et w o r k ,   t h e y   o v er lo o k ed   th e   a f f ec t   t h at  it  d o es   n o t   al w a y s   g u ar an tee  g etti n g   b est   p er f o r m a n ce   in s id th n et w o r k .   Su c h   tr ad e - o f f   is   co m m o n   i n   o p ti m izatio n   p r o b le m s .   T h is   p ap er   p r o p o s es  an   i m p r o v e m en t   f o r   t h m et h o d   i n   n et w o r k   p la n n in g   u s i n g   h eu r is tic  al g o r ith m   w h er t h p r i m ar y   p u r p o s is   to   m i n i m ize  th co s t b y   tak i n g   in to   ac co u n t th d i s tan ce   b et w ee n   n o d es i n   W MN .       3.   P RO P O SE   AP P RO ACH   T h p r o b lem   at   h a n d   is   b i n ar y   o p ti m iza tio n   p r o b le m .   W h a v d ec id ed   to   ap p r o ac h   t h p r o b le m   u s i n g   Mo d if ied   B i n ar y   P ar tic le  S w ar m   Op ti m izatio n   ( MB P SO) .   MB P SO  w as   ch o s e n   a s   it  o v er co m es   th e   u n r ea s o n ab le  b eh a v io r   o f   it s   p r ed ec ess o r ,   B P SO  [ 2 3 ] .   Su p p o s th at  t h n u m b er   o f   SS s   i s       ,   th n u m b er   o f   R Ss   i s       ,   an d   th n u m b er   o f   B S s   is       .   T h s u m   o f   co m p o n e n t s   i n   ea ch   p ar ticle  is   eq u a l to   [ 1 5 ] ,                                                                                                ( 1 )     W h en e v er   n e w   p ar ticle   is   g en er ated ,   w h et h er   it  i s   r an d o m l y   g e n er ated   ( in i tializatio n   p h ase  o r   d u e   to   m u tatio n )   o r   d u to   th alg o r ith m s   p r o g r ess io n ,   it  m u s b ch ec k ed   f o r   v alid it y .   I f   s tatio n   p r esen ted     ( b y   1 ‖)   is   i n v alid   i n   r ea l li f d u to   it b ein g   o u t o f   t h co v e r ag ar ea ,   it  m u s t b r e m o v ed   f r o m   t h m a tr ix   t h at   r ep r esen ts   it ( b y   t u r n i n g   i t in to   0 ‖) .   T h ai m   o f   s o lv i n g   t h p r o b lem   i s   to   m in i m ize   t h co s t   o f   e s tab lis h in g   n et w o r k .   T h f it n es s   v alu e   o f   n et w o r k   i s   as f o llo w s ,                                                                                                                                ( 2 )   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2 0 8 8 - 8708     I mp r o ve men t a t Netw o r P la n n in g   u s in g   Heu r is t ic  A lg o r ith to   Min imiz C o s t o f D is ta n ce     ( S h iva n   Q. A . )   312   Ho w e v er ,   p er f o r m an ce   is   n o g u ar a n teed   j u s b y   m in i m izi n g   t h co s o f   e s tab lis h i n g   n e t w o r k   w it h   r eg ar d   to   m etr ics  s u c h   a s   P DR   an d   E 2 E   d ela y .   [ 1 5 ]   ap p r o a ch ed   th p r o b le m   f r o m   t h p e r s p ec tiv o f   co s b u t   it  i g n o r ed   cr u cial  f ac to r   i n   n et w o r k   p er f o r m a n ce ,   i.e . ,   t h e   d is tan ce   b et w ee n   n et w o r k   s tat io n s .   D ig i tal  s ig n al s   atten u ate  d u r i n g   tr a n s m is s io n   w it h   r esp ec to   d i s tan ce .   T h g r ea ter   t h d is tan ce ,   th e   g r ea ter   th a tten u atio n .   T h u s ,   ig n o r in g   s u ch   co n s id e r atio n   is   d etr i m e n tal  to   th p er f o r m a n ce   o f   n et w o r k .   T h m at h e m atica m o d el,   M o d el  B ased   o n   Flo w   C o n s er v atio n   an d   C ap ac it y ‖  p r o p o s ed   b y   [ 1 5 ]   is   g o o d   an d   w e   h a v ad ap ted   it  f o r   th e   r esear ch   at   h a n d .   D is tan ce   w as  ta k e n   i n to   ac co u n d u r i n g   n e t w o r k   p lan n i n g   b y   u p d ati n g   t h o b j e ctiv f u n ctio n   2   as f o llo w s ,                                                                                                                                                                                                                                                                                                                                                                                                          ( 3 )     Op ti m izatio n   w i ll  h elp   m i n i m ize  th e   p r ev io u s   f u n c tio n ,   w h i ch   w o u ld   b alan ce   m i n i m izin g   co s a n d   th to tal  d is tan ce   p o s s ib le  b et w ee n   n et w o r k   s tatio n s .   T h u s ,   i m p r o v i n g   th o v er all  p er f o r m an ce   o f   t h e   n et w o r k .       4.   E XP E R I M E NT S AN RE S UL T S   T h is   s ec tio n   d is c u s s es   th e   r es u lts   f r o m   t h co n d u cted   e x p e r i m en ts   in   d etail.   A   tr ip ar tite  g r ap h   w a s   u s ed   as t h s i m u latio n   m o d el  i n   M A T L A B   an d   is   s h o w n   i n   F ig u r 3 .           Fig u r 3 .   T r ip ar tite g r ap h   r ep r esen tat io n   o f   s a m p le  p r o b lem .   A d o p ted   f r o m   [ 1 5 ]       Firstl y ,   MB P SO  h ad   to   b e v a lu ated   f o r   w h ic h   t h M A T L A B   en v ir o n m e n w a s   c h o s e n .   T h o r ig i n al  o b j ec tiv f u n c tio n   w as  u s ed   a n d   th r es u lt p r esen ted   as a            m atr ix ,                                                                                                       T h r esu lt h ad   th f o llo w i n g   p atter n                                    ,   w h er ele m en ts :   1   an d   2   r ep r esen     .   3   an d   4   r ep r esen     .   5   to   1 0   r ep r esen      .   1 1   to   1 6   r e p r esen      .   1 7   to   2 0   r e p r esen      .   See  T ab le  1 .       T ab le  1 .   P ar ticle  S w ar m   Op ti m izatio n   p ar a m eter s   an d   c h o s en   v al u es   N o .   o f   El e me n t s   20   N o .   o f   R e su l t   M a t r i c e s   50   V e l o c i t y   R a n g e   [       ]   N o .   o f   I t e r a t i o n s   6 0 0   C1   1   C2   0 . 5            0 . 3             0 . 9   M u t a t i o n   R a t e   0 . 1   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I J E C E   Vo l.  7 ,   No .   1 Feb r u ar y   2 0 1 7   3 0 9     315   313   T h alg o r ith m   g e n er ated   s o lu tio n   w i th   a n   estab li s h m e n t c o s t o f   2 5 ,   as f o llo w s :     [                                         ]     w h er       [     ]       [     ]        [             ]        [             ] ,   an d          [         ] .   I n   t h is   s o lu tio n ,   B S 1   an d   R S 2   f o r m   t h b ac k b o n o f   t h n et w o r k ,   w h er B 1   s er v es  R S 2 ,   w h ich   i n   t u r n   s er v es S Ss   1 ,   2 ,   an d   3 .   Up o n   u p d atin g   t h o b j ec tiv f u n ctio n ,   MB P SO  w as  p e r f o r m ed   w it h   th s a m p ar am eter s .   I n   o r d er   to   p er f o r m   co m p ar is o n   b et w ee n   o u r   ap p r o ac h   an d   [ 1 5 ] ,   th d is tan ce s   b et w ee n   t h d i f f er e n n et w o r k   s tatio n s   h av to   b k n o w n .   T h ese  d is tan ce s   h a v b ee n   as s u m ed   an d   ar p r esen ted   in   T ab les  ( 2 - 3 ) .   T h d is tan ce   b et w ee n   R S 1   an d   S S 2   ( 3 0 )   is   less   t h an   t h at  b et w ee n   R S 2   a n d   SS   2   ( 8 0 ) .       T ab le  2 .   Dis tan ce s   b et w ee n   B Ss   an d   R Ss   a n d   SS s                 d i st a n c e               d i st a n c e   C o v e r a g e   Z o n e   R a d i u s   B S   1   [     ]   [         ]   1   75   1 5 0   B S   2   [     ]   [         ]   3   75   1 5 0       T ab le  3 .   Dis tan ce s   b et w ee n   R Ss   an d   SS s                 d i st a n c e   C o v e r a g e   Z o n e   R a d i u s   R S   1   [       ]   [          ]   1 0 0   R S   2   [       ]   [          ]   1 0 0       T h ex p er im e n y ield s   t h f o ll o w i n g   s o lu tio n   w it h   an   e s tab li s h m e n t c o s t o f   3 5 ,     [                                         ]     w h er       [     ]       [     ]        [             ]        [             ]   an d          [         ] .   T h b ac k b o n o f   th e   n et w o r k   ac co r d in g   to   th is   s o lu tio n   i s   f o r m ed   b y   B 1   a n d   R 1 ,   w h er R S   1   t h en   s er v e s   S Ss   1 ,   2 ,   an d   3 .   T h r o u tes  b et w ee n   s tatio n s   f o r   r esu lt s   o b tain ed   u s in g   t h o r ig i n al  an d   u p d ated   o b j ec tiv f u n ctio n s   ar p r esen ted   in   T ab les ( 4 - 5 ) .       T ab le  4 .   R o u tes u s i n g   o r ig i n al   o b j ec tiv f u n ct io n   S u b s c r i b e r   S t a t i o n   R o u t e   S S   1   RS     B S   1   S S   2   R S   1     B S   1   S S   3   R S   1     B S   1       T ab le  5 .   R o u tes u s i n g   th u p d ated   o b j ec tiv f u n ctio n   S u b s c r i b e r   S t a t i o n   R o u t e   S S   1   R S   2     B S   1   S S   2   R S   2     B S   1   S S   3   R S   2     B S   1         Seco n d l y ,   r ea l - w o r ld   p er f o r m an ce   h ad   to   b e v al u ated   u s i n g   th e   P DR   an d   E 2 E   d ela y   m etr ics.  s i m u lat io n   o f   r ea n et w o r k   w a s   ca r r ied   o u i n   M A T L A B .   E v er y   SS   w o u ld   g e n er ate  d at p ac k ets  to   b s e n t   to   th allo ca ted   B S.  T h n u m b er   o f   d ata  p ac k ets an d   th i n te r v al  o f   g en er atio n   w er d eter m i n ed   u s i n g   P o is s o n   r an d o m   v ar iab les.  T h n u m b e r   o f   d ata  p ac k e ts   h ad   a   m ea n   v alu o f   6   w h er ea s   th e   in ter v al   o f   g e n er atio n   h ad   m ea n   o f   6   s ec .   W h a v a s s u m ed   t h at  ea c h   B h as   m ec h a n is m   f o r   d etec ti n g   er r o r s   in   r e ce iv ed   d ata  p ac k et s .   I f   er r o r s   ex is t,  t h B w ill  s en d   m es s a g to   th s o u r ce   s tatio n   s o   th at  it  m a y   r e - s en d   th af f ec ted   d ata  p ac k ets  w h ile   t h elap s ed   ti m is   less   t h an   t h p ac k et   li f t i m ( 0 . 5   s ec ) .   T h c h an n el s   b et w ee n   SS     R S,    SS    B S,  an d   R   B ar b ased   o n   th Gillb er t - E llio m o d el.   T h q u alit y   o f   ch an n el  i s   in d ir ec tl y   p r o p o r tio n al  to   th d i s tan ce   b et w ee n   a n y   t w o   s tat io n s .   T w o   e x p er i m e n ts   w er ca r r ied   o u to   co m p ar t h e   p er f o r m a n ce   o f   th n et w o r k   w it h   r e g ar d   to   P DR   an d   E 2 E   d elay .   T h d u r atio n   o f   ea c h   e x p er i m e n w a s   1 5 0 0   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2 0 8 8 - 8708     I mp r o ve men t a t Netw o r P la n n in g   u s in g   Heu r is t ic  A lg o r ith to   Min imiz C o s t o f D is ta n ce     ( S h iva n   Q. A . )   314   s ec   o f   w h ic h   2 5   s ec   w as  u s ed   f o r   d ata  lo g g in g .   6 0   s a m p le s   f o r   P DR   an d   E 2 E   d ela y   v alu e s   w er lo g g ed   an d   th r esu lts   ar d is c u s s ed   i n   th e   f o llo w in g   s ec tio n .     5.   E VA L UA T I O AND  D I SC USSI O N   Fig u r es  ( 4 - 5 )   clea r l y   s h o w   t h at  ta k i n g   d i s tan ce   in to   co n s id er atio n   h as   p o s iti v i m p ac o n   t h e   p er f o r m a n ce   o f   th e   n et w o r k .   T h P DR   v alu e s   ar b etter   s i n ce   R 1   is   u s ed   i n s tead   o f   R 2 t h d is ta n ce   b et w ee n   SS   2   an d   r o u tin g   s t atio n   is   les s   an d   t h u s   s i g n a q u alit y   w it h   r eg ar d   to   SS   2   is   im p r o v ed .   T h is   also   h as  a   p o s iti v e f f ec o n   t h E 2 E   d ela y i m p r o v ed   s ig n al   q u al it y   d ec r ea s e s   t h p r o b ab ilit y   o f   er r o r s   i n   r ec ei v ed   s ig n al s   w h ich   in   tu r n   d ec r ea s es  t h n u m b er   o f   ac k n o w le d g m e n ts   an d   r e - s e n d in g   o f   d ata  p ac k ets,  t h u s   r ed u cin g   E 2 E   d elay   ti m e.             Fig u r 4 .   P DR   co m p ar is o n   b etw ee n   o r ig i n al  an d   m o d i f ied   o b j ec tiv f u n ctio n     Fig u r 5 .   E 2 E   Dela y   co m p ar is o n   b et w ee n   o r ig in al  a n d   m o d if ied   o b j ec tiv f u n ctio n       Fin all y ,   t h f i n d in g   o f   t h i s   s t u d y   i s   b ased   o n   t h r es u lt   as  s h o w n   i n   F ig u r es  ( 4 - 5 ) ,   th i s   s tu d y   h a s   a   p o s iti v e f f ec o n   p er f o r m a n c o f   th n et w o r k   t h r o u g h   t h q u alit y   o f   s i g n al  o f   r o u t in g   s t atio n   is   le s s .   Ot h er   h an d ,   r ed u cin g   th ti m d ela y   t h r o u g h   d ec r ea s es  th n u m b er   o f   ac k n o w led g m en t s   an d   r e - s en d i n g   o f   d ata  p ac k ets.       6.   CO NCLU SI O N   C o s o p ti m izatio n   is   an   ar ea   o f   r esear ch   w it h   r eg ar d   to   W MN s .   T h is   r esear ch   w as  b ased   u p o n   i m p r o v i n g   t h s o lu tio n   p r o p o s ed   b y   [ 1 5 ]   in   th is   r eg ar d .   T h e y   h av co n s id er ed   co s o p t i m izatio n   w ith o u tak i n g   d is tan ce   b et w ee n   n o d e s   in to   co n s id er atio n .   T h is   r es ea r ch   co n s id er ed   th p r o b le m   u s i n g   Mo d if ied   B in ar y   P ar ticle  S w ar m   Op ti m izatio n   ( MB P SO)   ap p r o ac h   b y   u p d ati n g   th o p ti m izatio n   f u n ct io n   to   ta k i n to   co n s id er atio n   t h d is ta n ce s   b e t w ee n   t h d if f er e n n o d es.  T h r esu lt s   w er p o s itiv a n d   t h i s   ap p r o ac h   s h o w ed   n o ticea b le  i m p r o v e m en co m p ar ed   to   th b en ch m ar k .   T h P DR   s h o w ed   an   ap p r o x i m ate  in cr ea s o f   1 7 . 8 3 w h er ea s   t h E 2 E   d elay   s a w   an   ap p r o x im ate  d ec r ea s o f   8 . 3 3 %.       ACK NO WL E D G E M E NT   T h is   w o r k   i s   s u p p o r ted   b y   M in is tr y   o f   E d u ca tio n   o f   Ma la y s ia,   Gr an n o F R GS/  1 2 0 1 5 I C T 0 4 /   UKM / 0 2 / 3       RE F E R E NC E S   [1 ]   J.  Co im b ra ,   G .   S c h ü tz,  a n d   N.  Co rre ia.  A   g a m e - b a se d   a lg o rit h m   f o f a ir  b a n d w id th   a ll o c a ti o n   in   F ib re - W irele ss   a c c e s s n e tw o rk s,  Op ti c a S wit c h i n g   a n d   Ne two rk in g ,   v o l.   1 0 ,   p p .   1 4 9 - 1 6 2 ,   2 0 1 3 .   [2 ]   J.  Co im b ra ,   G .   S c h ü tz,  a n d   N.  Co rre ia.  En e rg y   e ff ici e n ro u t in g   a lg o rit h m   f o f ib e r - w irele ss   a c c e ss   n e tw o rk s:  n e tw o rk   f o rm a ti o n   g a m e   a p p ro a c h ,   Co m p u ter   Ne tw o rk s ,   v o l.   6 0 ,   p p .   2 0 1 - 2 1 6 ,   2 0 1 4 .   [3 ]   F . L .   Kh a lee l.   Re c ru it m e n a n d   Jo b   S e a rc h   A p p li c a ti o n ,   U n ive rs it i   Uta ra   M a l a y sia ,   2 0 1 1 .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I J E C E   Vo l.  7 ,   No .   1 Feb r u ar y   2 0 1 7   3 0 9     315   315   [4 ]   F . L .   Kh a lee l,   N.S .   A sh a a ri,   T . S .   M e riam ,   T .   W o o k ,   a n d   A .   Is m a il .   T h e   stu d y   o g a m i f ica ti o n   a p p li c a ti o n   a rc h it e c tu re   f o p ro g ra m m in g   lan g u a g e   c o u rse ,   in   Pr o c e e d in g s   o f   th e   9 t h   I n ter n a ti o n a l   Co n fer e n c e   o n   Ub i q u it o u s   In fo rm a t io n   M a n a g e m e n t   a n d   C o mm u n ica ti o n ,   2 0 1 5 a ,   p .   1 7 .   [5 ]   F . L .   Kh a lee l,   N.S .   A sh a a ri,   T . S .   M e riam ,   T .   W o o k ,   a n d   A .   Ism a il .   Us e r - En jo y a b le  L e a rn in g   En v iro n m e n Ba se d   o n   G a m i f ica ti o n   El e m e n ts,   in   In ter n a ti o n a C o n fer e n c e   o n   Co mp u ter ,   Co mm u n ica ti o n ,   a n d   Co n tro T e c h n o l o g y   ( I4 CT   2 0 1 5 ) ,   Ku c h i n g ,   S a ra w a k ,   M a la y sia ,   2 0 1 5 b ,   p .   2 2 1 .   [6 ]   F. L .   Kh a lee l,   N.S .   A sh a a ri,   T . S .   M e riam ,   T .   W o o k ,   a n d   A .   Ism a il .   T h e   A rc h it e c tu re   o f   D y n a m i c   Ga m i f ica ti o n   El e m e n ts  Ba se d   L e a rn in g   Co n ten t,   J o u r n a l   o C o n v e rg e n c e   I n fo rm a ti o n   T e c h n o l o g y ,   v o l.   1 1 ,   p p .   1 6 4 - 1 7 7 ,   2 0 1 6 a .   [7 ]   F . L .   Kh a lee l,   T . S . M . T .   W o o k ,   N.S .   A sh a a ri,   a n d   A .   Is m a il .   Ga m i f ic a ti o n   El e m e n ts  f o L e a rn in g   A p p li c a ti o n s ,   In ter n a t io n a J o u rn a o n   Ad v a n c e d   S c ien c e ,   E n g in e e rin g   a n d   I n f o rm a ti o n   T e c h n o l o g y ,   in   p re ss ,   2 0 1 6 b .   [8 ]   G .   M a ,   R.   G o n g ,   Q.  L i,   a n d   G .   Ya o .   A   I m p r o v e d   P a rti c le  S w a r m   Op ti m iza ti o n   A lg o rit h m   w it h   Dy n a m i c   A c c e lera ti o n   Co e ff icie n ts,   Bu ll e ti n   o f   El e c trica E n g in e e rin g   a n d   I n fo rm a t ics ,   v o l.   5 ,   2 0 1 6 .   [9 ]   S . M .   A li ,   P . S .   Ba b u ,   a n d   B.   G u ru se k h a r.   Re c o n f ig u ra ti o n   w it h   S im u lt a n e o u DG   in sta ll a ti o n   t o   Im p ro v e   th e   Vo l tag e   P ro f il e   in   Distrib u ti o n   N e tw o rk   u sin g   Ha r m o n y   S e a r c h   Alg o rit h m ,   Bu ll e ti n   o El e c trica E n g i n e e rin g   a n d   In fo rm a t ics ,   v o l.   4 ,   p p .   2 5 7 - 2 7 3 ,   2 0 1 5 .   [1 0 ]   S .   M i d d h a   a n d   P .   S i n g h .   C h a n n e A ss i g n m e n w it h   G re e d y   A l g o rit h m   f o W irele ss   M e sh   Ne t wo rk ,   Bu l letin   o f   Ele c trica En g in e e rin g   a n d   In f o r ma ti c s ,   v o l.   5 ,   2 0 1 6 .   [1 1 ]   X .   Zh a n g   a n d   L .   Hu a n g .   A   De n sity   Co n tro l   Ba se d   A d a p ti v e   He x a h e d ra M e sh   G e n e ra ti o n   A lg o rit h m ,   In d o n e si a n   J o u rn a o El e c trica En g in e e rin g   a n d   I n fo rm a t ics   ( IJ EE I) ,   v o l.   4 ,   2 0 1 6 .   [1 2 ]   M .   A n u sh a ,   S .   V e m u ru ,   a n d   T .   G u n a se k h a r.   T ra n s m issio n   p ro to c o ls  in   C o g n it iv e   Ra d i o   M e sh   Ne tw o rk s,  In ter n a t io n a J o u rn a o E lec trica a n d   C o mp u ter   En g in e e rin g ,   v o l.   5 ,   2 0 1 5 .   [1 3 ]   Y.  Be jera n o ,   K.T .   L e e ,   S . J.  Ha n ,   a n d   A .   Ku m a r.   S in g le - p a th   r o u ti n g   f o li f e   ti m e   m a x i m i z a ti o n   in   m u lt i - hop  w irele ss   n e tw o rk s,  W ire les s Ne tw o rk s ,   v o l.   1 7 ,   p p .   2 6 3 - 2 7 5 ,   2 0 1 1 .   [1 4 ]   I. F .   A k y il d iz  a n d   X .   W a n g .   A   s u rv e y   o n   w irele s m e sh   n e t w o rk s,  IEE Co mm u n ica ti o n ma g a zi n e ,   v o l.   4 3 ,   p p .   S 2 3 - S 3 0 ,   2 0 0 5 .   [1 5 ]   S. M .   Kh a led .   He u risti c   a lg o rit h m f o w irele ss   m e sh   n e tw o rk   p lan n in g ,   L e th b r id g e ,   A lt a . Un ive rs it y   o L e th b rid g e ,   De p t.   o f   M a th e ma t ics   a n d   C o mp u ter   S c ien c e ,   c 2 0 1 2 ,   2 0 1 2 .   [1 6 ]   R.   M a tam   a n d   S .   T rip a t h y .   I m p ro v e d   h e u risti c f o m u lt ica st  ro u ti n g   in   w irele ss   m e sh   n e tw o rk s,  W ir e les n e two rk s v o l.   1 9 ,   p p .   1 8 2 9 - 1 8 3 7 ,   2 0 1 3 .   [1 7 ]   S .   L in g ,   C.   Jie ,   a n d   Y.   X u e - j u n .   M u l ti - p a t h   a n y c a st  ro u ti n g   b a se d   o n   a n c o lo n y   o p ti m iza ti o n   i n   m u lt i - g a te wa y   W M N,  in   Co m p u ter   S c ie n c e   a n d   Ed u c a ti o n   ( ICCS E),   2 0 1 0   5 t h   In te rn a ti o n a Co n fer e n c e   o n ,   2 0 1 0 ,   p p .   1 6 9 4 - 1 6 9 8 .   [1 8 ]   T .   Od a ,   Y.  L iu ,   S .   S a k a m o to ,   D.   El m a z i,   L .   B a ro ll i,   a n d   F .   Xh a f a .   A n a l y sis   o f   m e sh   ro u ter  p lac e m e n in   w irele ss   m e sh   n e tw o rk u sin g   F ried m a n   tes c o n sid e rin g   d if f e r e n m e ta - h e u risti c s,  In ter n a ti o n a l   J o u rn a o Co mm u n ica ti o n   Ne two rk s a n d   Distrib u ted   S y ste ms ,   v o l.   1 5 ,   p p .   8 4 - 1 0 6 ,   2 0 1 5 .   [1 9 ]   W. L .   Ya n g ,   C. C.   Ka o ,   a n d   C. H.  T u n g .   He u risti c   A lg o rit h m s   f o Co n str u c ti n g   In terf e re n c e - F re e   a n d   De lay - Co n stra in e d   M u lt ica st T re e f o W irele ss   M e sh   Ne t w o rk s,  T IIS ,   v o l.   5 ,   p p .   2 6 9 - 2 8 6 ,   2 0 1 1 .   [2 0 ]   A .   Ba ro ll i,   T .   Od a ,   F .   X h a f a ,   L .   Ba ro ll i,   P .   P a p a jo rg ji ,   a n d   M .   T a k iza w a .   W M N - GA   S y ste m   f o N o d e   P lac e m e n i n   W M Ns P e rf o rm a n c e   Ev a lu a ti o n   f o W e ib u ll   Distri b u ti o n   o f   M e sh   Cli e n ts,   in   I n fo rm a t io n   T e c h n o lo g y   Co n v e rg e n c e ,   e d S p ri n g e r 2 0 1 3 ,   p p .   2 2 3 - 2 3 1 .   [2 1 ]   D.  Be n y a m in a ,   A .   Ha f id ,   N.  Ha ll a m ,   M .   Ge n d re a u ,   a n d   J.  M a u re ira.  A   h y b rid   n a tu re - in sp ire d   o p ti m ize f o w irel e ss   m e sh   n e tw o rk s d e sig n ,   Co mp u ter   Co mm u n ica ti o n s ,   v o l .   3 5 ,   p p .   1 2 3 1 - 1 2 4 6 ,   2 0 1 2 .   [2 2 ]   F .   Xh a f a ,   A .   B a ro ll i,   a n d   M .   T a k iza w a .   tab u   s e a rc h   a l g o rit h m   f o e ff ici e n n o d e   p lac e m e n in   w ir e les m e sh   n e tw o rk s,  in   In telli g e n Ne tw o rk in g   a n d   Co ll a b o ra ti v e   S y ste m (I NCo S ),   2 0 1 1   T h ird   In ter n a ti o n a l   Co n fer e n c e   o n 2 0 1 1 ,   p p .   5 3 - 5 9 .   [2 3 ]   J.  Ya n g ,   H.  Zh a n g ,   Y.  L in g ,   C.   P a n ,   a n d   W .   S u n .   T a sk   a ll o c a ti o n   fo w irele s s se n so n e t w o rk   u sin g   m o d if ied   b in a r y   p a rti c le sw a r m   o p ti m iz a ti o n ,   IEE S e n so rs   J o u rn a l ,   v o l.   1 4 ,   p p .   8 8 2 - 8 9 2 ,   2 0 1 4 .   Evaluation Warning : The document was created with Spire.PDF for Python.