Indonesian J ournal of Ele c trical Engin eering and  Computer Sci e nce   Vol. 1, No. 2,  February 20 1 6 , pp. 390 ~  398   DOI: 10.115 9 1 /ijeecs.v1.i2.pp39 0-3 9 8        390     Re cei v ed Se ptem ber 21, 2015; Revi se d Jan uary 8, 2016; Accept ed Ja nua ry 2 8 , 2016   Prolonging the Lifetime of Wireless Sensor Networks  using LPA-star Search Algorithm       Ahm e d A.  Alkathm a w e e * 1 , Lusong Fe ng 2 , Imad S.   Alsha w i 3  1,2 School of computer scie n ce  and tech nol og y,  Hu azho ng U n iversit y , W u h an, Hub e i, Chi n a     3 Computer Sci ence a nd Infor m ation T e chno lo g y , Un iversit y  of Basra, Basra, IRAQ  *Corres p o ndi n g  author, e-ma i l : ahmed ad el1 949 @gma il.co m* 1 , lusongfe n g @h ust.edu.cn 2 ,  emad alsh a w i @ gmai l.com 3      A b st r a ct   Since  sens ors  hav e l i m ited  pow er r e so u r ces,  en ergy consu m ption  has beco m e a  critic a l   chall e n g e  to W i reless  Se nsor   Netw orks (W SNs). Most of t h e ro uting  pr oto c ols  prop ose d   to trans mit  dat a  packets thro ug h paths w h ic h consu m e low  e nergy a i m si mply to red u ce b a ttery pow er consu m ption. T h i s   can l ead t o  l ead to  netw o rk partitio n  a nd re duce   ne tw ork lifetime. T herefor e, to  bal ance  en e r gy   consu m ption  a nd ext end  n e tw ork lif eti m e  w h ile  mi ni mi z i ng p a cket  del i v ery de lay; th i s  pap er  prop o s es a   new  ener gy-ro uting pr otoco l  usin g the  life l o ng pl an nin g  A- star (LPA-star) search al gor ithm. T h is a l g o ri th m  is used to fin d  an opti m u m  forw arding p a th b e tw een  the so urce no de a nd  the sink. T he o p timu m path c a n   be sel e cted  de pen din g  o n  hi ghest res i du al  sensor  ener gy , the shortest d i stance to th e  sink an d l o w e st   traffic load. S i mu lati on res u lt s ind i cate th at the pr opos ed  protoco l  i n cre a sed th e l i feti me  of the  net w o rk  compar ed w i th the A-star  routi ng (EERP) prot ocol.        Ke y w ords : LP A-star algor ith m , netw o rk lifet ime,  routin g, w i reless se nsor n e tw orks    Copy right  ©  2016 In stitu t e o f  Ad van ced  En g i n eerin g and  Scien ce. All  rig h t s reser ve d .       1. Introduc tion  Gro w ing  adv ances in  wireless  com m unication a n d  ele c tro n ics  make th e  Wirel e ss  Senso r  Net w orks  (WSNs) have come   u nder  inten s iv e  rese arch  o v er the  la st years. it h a ve  the   enormou s   a pplication p o tentials in  defen se   a nd civilian related   ap pli c ation s  su ch   as  environ menta l  monitori ng,  military field  and bi omedi cal ob se rvation [1-3]. In  su ch a ppli c atio ns,  WSN is a di stributed wi rel e ss network comp ri si ng of  many numb e r of low-co st devices  call ed  sen s o r  no de s, which a r e i n telligent e n o ugh to  sen s e ,  calculate a nd commu nication with  ea ch   other to  colle ct and t r an sm it the data fro m  the env iron ment and  pa sse s  it at a ce ntric  node  kn ow  as the ba se  station (sin k n ode) [4].   The sen s or n ode s in WS Ns have resou r ce  co nstraint s, inclu d ing  short commun i cation  rang e, limited pro c e ssi ng , small mem o ry, low ban dwidth, and  limited energ y  resou r ce [5].  Indeed, sen s or  b a tterie s  powere d   by finite  ene rgy  pre s e n t difficultie s in  bei ng repla c ed   or   recha r ge d. Therefo r e, ene rgy resou r ce con s trai ned a nd scarcity is an acute ch alleng e in WSN  appli c ation s . On the other hand, tran smissi on an d reception inf o rmatio n sp e nd most en e r gy  quickly du rin g  co mmuni cation an d m a y be con s id ered th e maj o r  sou r ces  o f  sen s o r  en e r gy  con s um ption  [6]. In one -ho p  tra n smi s sio n , the  sen s o r  nod es lo cate d farth e r  awa y  from the   si nk  drain  high er  energy due t o  the long tra n smi ssi on d a ta ran ge, and  may die out first. On the  other  hand, m u lti-h op tra n smissi on  which exp end s le ss  po wer at e a ch  hop i s  m o re   energy-effici e n t  than di re ct  transmissio n  [7]. Ho wev e r, multi- hop  tran smi ssi o n  is u s ed  i n  many -to-o n e   comm uni cati on, and in thi s  communi ca tion pattern, t he clo s e r  sen s or to th e sin k  may ru n ou t of  energy soon er d ue to  ha ving the  high est lo ad  of  p a ckets,  and  thus there i s   Uneve n  Ene r gy  Con s um ption  (UEC) am o ng  sen s o r  n o des [8].Fi gure1  sho w s a n  example  of  UEC proble m  in  multi-ho p tra n smi ssi on.Th e se nsors n eare s t to  th e sin k  a r e o v erbu rde ned  becau se of  the  expulsi on of  other  se nso r s data to the  sink. As  a con s eq uen ce, n e a re r sen s ors  con s um e mu ch  more  en ergy  and  die m u ch  faste r , which  re sult s in  net work  pa rtition  pro b lem,  en ergy h o le s, a n d   incom p lete  p a cket d e livery  [8]. Therefore, UE C  i s  a n   innate  dra w b a ck d e scri be d by a  ma ny-one  traffic pattern and multi - hop  routin g  which re d u c e s  the lifetime of a wirele ss n e twork  signifi cantly.    Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS   ISSN:  2502-4 752     Prolon ging th e Lifetim e  of  Wirel e ss Sen s or   Networks usin g… (Ahm ed A. Alkathm a wee)  391     Figure 1. Une v en energy  consumption i n  WSN multi - hop tran smi s sion       The ro uting  algorith m s in  WSNs are  desi g ne d to prolo n g net work lifetime  and to  enha nce bala n ce d ene rgy con s um ption  throug h data  forwa r din g  [9]. As seen i n  Figure 2, the   routing  proto c ol s sel e ct th e best p a ths  for forwar din g  the data pa cket from the  sou r ce nod e  to  the si nk.  Furt herm o re, th e  same  route  p a th is u s ed  continuo usly t hen th e exi s ting n ode s  on t hat  route path  will die, which results in network  partitioning. Therefore,  the bal anci ng energy  con s um ption  of sen s o r  n o des  with  an o p timizing  ro uting meth od i s  a ne w  chall e nge p r e s e n te d   in many routi ng proto c ol s for WS Ns.       Figure 2. Dea t h the centri c  node s in WS N lead to Network pa rtition  proble m       In this  pap er, a ne w  ene rgy efficie n t  routing  p r oto c ol,  calle d t he LPA-sta r  routin g   proto c ol, i s   propo sed. It  uses  an  optimal  agg re gat ed   co st fun c tion,  and  the  lifel ong  plan ning   A- star (LPA-sta r) search al g o rithm to find  an  optimum  forwa r di ng p a th betwe en  the sou r ce n o d e   and th e d e sti nation. T he  L PA-star alg o rithm is an  in cre m ental  ve rsio n of  A-sta r  al gorithm  th a t   reu s e s   information  from previou s  sea r ch path s  to find a ne w routing path  without re-ru n nin g   from the  sta r t nod e. The  propo sed  proto c ol ta ke s the   followin g  pa rameters i n to  con s id eratio n  to   sele ct an  opti m um routing  path:  i) hi ghe st re sid ual  se nso r  n ode  en ergy; ii) l o we st traffic lo ad ;  and iii) minim u m hop count s.         The remain der of the  pa per i s  organi zed  as follo ws: Section  2  pre s ent s relat ed work  for the  routin g algo rithm  o n  improving t he maxi mu m  netwo rk lifetime. The  pap er int r odu ce s  and   provide s  a  bri e f backg rou n d  to the LPA-star al go rithm  in Section  3. Section 4  prese n ts the  L PA- star routin g  p r otocol.  The  perfo rman ce  evolution  i s  d i scusse d in  Section  5. Fi nally, Section  6   pre s ente d  the  con c lu sion to  this pape r.       2. Relate d Work   In the traditio nal routing  al gorithm s, the   inte re st in  mi nimizin g  e n e r gy co nsumed  witho u t  con s id eratio n  to bal ance e nergy  co nsu m ption fo r  th e whole  network lea d  to  a  netwo r k pa rtition  probl em and  hence  will reduce net wo rk lifetime. Therefore, the el i m ination of  UEC in order t o   prolo ng the n e twork lifetim e has b e com e  a criti c al issue in WSNs.   In the re ce nt past, ma ny  energy-effici e n t ro utin g al gorithm s h a ve bee n p r op ose d  to  improve and  extend  the n e twork  lif etim e of WS Ns. In [10] an d [1 1], the autho rs  propo se t w o  different ap proache s that  distrib u te the  traffi c loa d  throu gh the  n o de s which  have re maini ng  Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 25 02-4 752                   IJEECS  Vol.  1, No. 2, February 201 6 :  390 – 398   392 energy to en sure the  stab ility of sen s or node s fo r ex tending  wirel e ss net wo rk l i fetime. In [12],  the authors p r opo se a rout ing method to redu ce t he  hop co unt extent of a  routing path so a s  to   redu ce  the p o we r  con s um ption of e nd  to end t r an smissi on. All o f  the above  routing p r oto c ols  usin g fixed routing p a ths  focu s on  obt aining  ene rgy   effic i enc y . As  a  res u lt of  this , trans m itt i ng   data via spe c i f ic routing p a ths might d r ai n node s po wer qui ckly.   In [13], WSNHA-GA HR i s   a gree dy and  A-star  h euri s tic routing  alg o rithm for  WSNs in  home autom ation. The algorithm mini mize s the nu mber of hop s for data tran smissio n  by usin g  the greedy fo rwa r di ng te ch nique. F u rt he rmore, the p r otocol  uses t he A-star  se a r ch  alg o rithm  to  overcome  th e lo cal mi ni mum p r obl e m . The  WS NHA -GAHR  proto c ol  doe s n o t con s i der  remai n ing  en ergy in  se nso r  no de s whe n  sel e ct in g th ese  nod es fo r ro uting  data  packet s . Th us,  this may depl ete sele cted  node s en erg y  quickly. Re na et al. [14] prop osed an  efficient routi n g   algorith m   whi c h  used  an  A-sta r   sea r ch  algorith m  to  pick o u t an  o p timum  routi ng p a th from  the   sou r ce n ode i n to the  sin k , whi c h  wa s ba sed  on  a no d e ’s mi nimum  energy level  value to exte nd   the lifetime  o f  WSNs.Thi s  routing  p r oto c ol  defin e d  t he th re shold   as th e mi nim u m e nergy le ve l  value se nsor  node s. Co nseque ntly, a node will b e  ex clud ed from t he routin g op eration  whe n  the  energy value  of this n ode i s  le ss than th e thre sh old v a lue. Th e aut hors of [15]  p r opo se d OF F I S  (optimi z ed fo rwa r di ng by fuzzy inferen c e sy stems)  for flat sensor n e two r ks to extend the     lifetime of WSNs. T h is protocol  fa v our s  crit e r ia ju st   as  sh ort e st  p a t h  wit h  sm al l hop s,  max i mum   remai n ing b a ttery powe r  i n  ord e r to se lect the  be st  can d idate n o de inthe forwardin g  path s .   In   [16], the auth o rs  propo sitio n  is of  a  hybrid multi-h op routing p r oto c ol so  as to  o p timize e n e r gy  con s um ption  and to exte nd the  WSNs lifetime by  combi ned  h i era r chical a nd flat multi-hop   routing  al gori t hms  with  a  data  colle ctio n sch e me. In  [17], the  aut hors  pre s e n ted a  n o vel  sl eep   sched uling  m e thod to  ma ximize  netwo rk lifetim e  ca lled Virtu a l B a ckbo ne S c h edulin g (VBS ).  This u s e s  on ly backb one s to forward d a ta packet s , and the othe r remai n ing n ode s halt their  radio s  so as  to con s erve  and save en ergy. Al G haffari et al. [18] propo se d an  energy effici ent  routing  (EE R P) p r oto c ol t o  extend   WSNs lifet ime  a nd b a lan c e  e nergy  con s u m ption. In th eir  prop osed m e thod, the rout ing meth od u s ed  an A - st a r  sea r ch al gorithm to achie v e an o p timu m  forwa r di ng p a th betwe en  sou r ce nod e  and si nk by  developin g  p a ram e ters to cho o se the n e xt  hop in the ro uting ope rati on. This ro uting proto c ol  rerun s  the se arch algo rith m from the start  node  every round to  find  an optim um  path with out  usin g info rma t ion from th e  previou s   sea r ch  operation.  M o reove r ,  thi s  approa ch do es not  in clu d e  a w ay of  ch ecking  its  cu rrent  path to  select   a new  path, whi c h will  result in  increased search  eff o rt. Hence, the inevitable  consequence is   highe r co nsu m ption of ene rgy.  From the revi ewe d  literature, it can be conc l ude that a numbe r of different metrics a r e   use d  to avert netwo rk p a rtition and  prolo ng WS Ns lifetime, su ch a s  bal anci ng ene rgy  con s um ption,  sho r te st pat h to the  sin k   and b a lan c in g load  traffic.  In this p ape r, we p r op ose  a   new  ene rgy-efficient ro uting protoc ol u s ing  LPA-sta r  sea r ch alg o rithm. The LP A-sta r  algo rit h m  repe atedly uti lize s  a  simila r optim um forwarding  path  from  sou r ce  node to  si nk.  It recalculat es  the new o p timum path u s ing d a ta fro m  its prev io us sea r ch re sults. Th e propo sed p r oto c ol   sele cts th e o p timum routin g path  depe n d ing o n  the  a bove criteri a  (resi dual  ene rgy sen s o r  n o de,  distan ce  to t he  sin k  of  a  node  an d tra ffic l oad  in th e no de  queu e). Fu rthe rm ore, the  routi ng  proto c ol  bala n ce s  betwee n  the s e  pa ra meters to  pr o t ract th e n e twork lifetim e  with lowes t  effort  and time as f a r as p o ssibl e .      3. Lifelong Planning A-star Search  Algorithm   Lifelong Pla n n ing A-sta r  (LPA-sta r) i s   an in cr e m ent al version  of the A-star a l gorithm   introdu ce d in  200 1 by S v en an d Ma xim as a  co mbination  of  the h e u r isti c A-sta r   sea r ch   algorith m , wh ich  sp eed s  u p  sho r test  st atic p a th pl a nning  an d  Dynamic SWSF -FP in creme n t a l   sea r ch algo rit h m, which sp eed s up re pla nning [19, 20]   LPA-sta r  em ploys h euri s ti c kno w led ge  to fo cu s the  search a nd  sel e ct the o p tim u m path  from the  sta r t node  to the  goal n ode  wh ile the e n viro nment dyn a m i cally chan gin g  over time [2 0].  Furthermore,  LPA-star  utilize  increm ental techni que to  reus e inform ation from  previous  sea r che s  op e r ation to find   a ne w optimu m  path  wi tho u t rerunni ng t he alg o rithm f r om  scrat c h. In   fact, LPA-sta r  is repeat edl y select s sim ilar opt imu m  path every time the nod e s  state remai n s  without ch an ges an d alwa ys efficiently recal c ul at es a n  optimum pa th from only those node s that  have cha nge d to the goal node rather t han re com p u t ing the path from the start  node [19]. As a  result, LPA-star de crea se s the nu mbe r  of sta r t no des  whi c h n eed to be  recom puted  a nd  Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS   ISSN:  2502-4 752     Prolon ging th e Lifetim e  of  Wirel e ss Sen s or   Networks usin g… (Ahm ed A. Alkathm a wee)  393 decrea s e s  th e sea r ch effort for determining t he n e w path to the goal. The  LPA-star  se arch  algorithm uses the key val ue (k(n))  with two co m ponents to sel e ct  the next node whi c h will  be   expand ed ba sed o n  the followin g  equati ons:     )) ( 2 ), ( 1 ( ) ( n k n k n k                                                             (1)    ) ( )) ( ), ( min( ) ( 1 n h n RHS n g n k                                  (2)    )) ( ), ( min( ) ( 2 n RHS n g n k                                                (3)    Whe r e g  (n )   and h  (n) va lues  are th e  actual  co st p a th from the  start no de to  node n  and t h e   estimated  co st of the optimum path  from node  n to the target no de (d estinatio n no de)  respe c tively. Also, the  Rig h t-Ha nd -Side  (RHS  (n )) va lue i s  the  min i mum valu e o f  the path  costs  comp uted  fro m  the  nod e’s neig hbo ring   node  n.  T he  RHS -value  is a  way fo r  no de that  chan ged   its key value  to notify nei ghbo ring  no d e s. the  com pone nts  of the  keys (k1   and  k2 )  can   be  thought of as identical to the f-value s  a nd g-valu es u t ilized by the A-sta r  algo rithm re spe c tively,   becau se b o th  the g-val u e s   and  RHS -val ues fo r the  compon ent of  keys  (k1 a nd  k2  ) in th e LP A- star  algo rith m co rrespon d to the  g-val ues u s ed i n  t he A-star alg o rithm  and th e h-val u e s  of  the  LPA-sta r  alg o rithm  corre s pond  dire ctly to the h- val ues i n  the  A-sta r  algo rit h m [21-25]. As  con s e que ntly, the key(k(n ) ) evaluati on f unctio n s  can  be rep r e s e n ted as:     )) ( 2 ), ( 1 ( ) ( n k n k n k                ( 4 )     ) ( ) ( ) ( 1 n h n g n k                               (5)    ) ( ) ( 2 n g n k                               (6)    Gene rally, LPA-star alg o rithm maintain s a prio rity queue to ke ep  track of the node s to  detect the  ne xt node with   pick the  small e st key val ue.  More  sp ecifi c ally, the no d e  expan ds i n   the   prio rity queu e  whe n  it ha s  smalle st  k1-v alue a nd if th ere  are  many  node s  with  same  smalle st  k1  value, finally,  the node  sele cted when  it has the  small e st k2 -value.       4. LPA-s t ar  Rou t ing Protocol   In  this  pap er,   the WSN  to pology  i s  ab stract s  a s  a  di recte d  gra ph G  (N, D), wh ere   N  is  the set of n  node s a nd  D is the  set of  dire ct  radio   comm uni cati on lin ks bet ween the  no de s.  A  dire ct link d =  (v, u), d   ∈   D exists if the Euclide an  distan ce b e twee n node v  and u insid e  th e   domain  of   r,  whe r e  r i s  the  radi us of the  tran sm i ssi on  ran ge  of no d e s. T he Ba se  station  (BS) i s   respon sibl e f o r  sen s o r y d a t a gathe red  from all  othe r n ode s in  the  n e twork  within   its tran smi s si o n   rang e [13], [26-27]. The p r oce dure of finding an opt im um path from  the source n ode to the BS is   rega rd  to  so me pa ram e te rs i n  e a ch  se nso r  n ode  like the  re sidu a l  ene rgy, traff i c lo ad a nd t h e   distan ce to the sink. The B S  must kno w  the curr ent le vel for the criteria of each sensor no de so  as to find the optimum path. Therefo r e, the BS  send queri e s to all sen s o r  nod es in the network  at the first ro und an d ea ch sen s o r  nod e sen d s  a b o v e param eter to the BS.  At the remai n ing   roun d, only the sen s o r  has  data to send  appe nd s it s param eters wit h  the dat a pa cket toward the   BS. The BS  sho u ld  cal c ul ate an d b r o a d ca st a n  o p timum  routin g  sched ule to  e a ch  sen s o r  n ode   [17].  The mod e l of the prop osed  method a s su mes  that WS N ha s the followin g  pro pert i es:   1.  All sensor n o des that rand om ly distrib u ted insi de the  area.    2.  All se nso r   no des have  the   same  initial  e nergy  and  th e same  maxi mum tran smi ssi on   rang e.  3.  Each sen s o r  node  kno w s the location of  BS as well a s  its own and  its neigh bors.   4.  Each  sen s o r   node  ha s the  different qu a n tities of traffi c   loa d  in sid e  its qu eue  when   the traffic loa d  ma de  by the a ppli c atio n an d the  n o de h a s al rea d y co mmitted  to  forward.     Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 25 02-4 752                   IJEECS  Vol.  1, No. 2, February 201 6 :  390 – 398   394 The mai n  g oals  of this pape r d e si gn a n e w e fficiency rout ing  p r otocol   that  will  enha ncement  and  extend t he lifetime  of the WS Ns t h rou gh limitin g ene rgy  co st as  well  as the  egalitari an di stributio n of  power  con s u m ption wi th  minimizi ng d a ta pa cket d e livery time. To   reali z e thi s , the ne w m e th od u s e s  the L PA-star  algo ri thm with all  a f oreme n tione d ro uting  crite r ia  (re sid ual ene rgy, distan ce  to the BS and traffi c loa d  amount ) for each se nso r  node to fin d  an   optimum forwardin g  path from the sou r ce node to  the  BS. The can d idate no de to rep r e s ent the   optimum  routi ng p a th de pe nds on  the la rge s t ke y-val ue  whi c h u s e d  the  evaluati on fun c tion  (k1  (n)) to find th e larg est  k1 -value.The  nod e ha s t he la rgest  k2-val ue  sele cted  wh en there is  m o re   than one n o d e  with the sa me larg est k1 -value. The e v aluation fun c tion s we u s e d  are given a s :    )) ( 2 ), ( 1 ( ) ( n k n k n k                ( 7 )     )) ( / 1 ( ) ( ) ( 1 n h n g n k              ( 8 )     ) ( ) ( 2 n g n k                               (9)    Whe r e h  (n ) i s  the di stan ce from n ode  n to the BS a nd g (n) i s  the  co st f o r nod e  n, whi c h  take s valu e [ 0 …1] a nd  d e termin e by  the fitnes s fu nction.  The f i tness eval ua tion fun c tion  is  con s id ere d  for the amou nt of residu al energy  and  the traffic loa d  of node n to determin e  the  optimum cost  value for the node n. The  cost functio n  g  (n) we used i s  given a s :    ) ( ) ( ) ( ) Re( ) ( n Bt n Bf n Et n n g                   ( 1 0 )     Whe r ea s  Re (n) an d Et(n )  a r e  refe r to the initia l and  re sid u a l ene rgy  of nod e n   respe c tively, and Bf(n) an d Bt(n ) a r e  refer to  the  cu rre nt an d m a ximum traffic  load s of  nod e n   r e spec tively.  α  and  β  a r e consta nt value s .   The candi dat e node th at h a s the m a ximize po we r an d lowe st traffi c load  amou n t  as well  as the shortest di stance to t he BS (mi n i m um hop  counts)  will be  selected as the better node for   the ro uting p a th to the BS. As a  re sult, these pa ra m e ters play a vit a l role  for b a l ance the e n e r gy  con s um ption  and the  app ropriate  di strib u tion of n e twork loa d  for  a ll node s in  order to  prolog  the  netwo rk lifeti m e.   Our  ro uting p r otocol fo r th e propo se d  model  ch eck  the existin g  n ode s in th e o p timum     path  with thei r nei ghbors  after  every packet send s and re-use t he  same path while its nodes still  have the  la rg est  key-val u e .  Furthe rmo r e, ou r m e tho d  get s to  be n e fit from th e  previou s  path  to   recalculate th e new o p timu m path from  curre n t node  that have ch ange d in whi c h key-valu e to  the BS by select its neigh b o rs t hat have  the largest key-value with out re-run nin g  from the start  node s.   The p r op ose d  metho d  d epen ded  on  the thre sh old value fo r no de e nergy. The   comm uni cati on between t he se nsor n o de and th e BS through  ro uting path  will brea k while  the   sen s o r  no de  energy is le a s t than the  th reshold val u e .  Therefo r e, t he propo se d  algorith m  trie s to   find alte rnate  ro ute p a th  b y  run n ing  the  algo rithm  fro m  the  sta r t n ode to  avoi d  cho o se the  l o w  energy node s in orde r to prolong the n e twork lifet ime. The flow  cha r t of propo sed  method to find  optimum ro uting path  from  start nod e to the BS is sho w n in Figu re  3.      5. Performan ce Ev aluation   In this  se ctio n, the pe rformance of the  pr o p o s ed  al gorithm i s  in vestigated  ag ainst the   EERP protocol in [1 7] to d e mon s trate  o p timization  m e thod s in  terms  of averag e resid ual  en ergy   as well as ma ximizing net work lifetime.     5.1. Simulation Ev aluation  We a dopt M A TLAB for executin g the  si mulation.Th e  simulatio n  a r ea is  200  × 2 0 0   2 m with 50  se nsor n ode s ran domly depl oyed in thi s  top ogra phi cal a r ea. The i n itial ene rgy for e v ery   sen s o r  nod e in the netwo rk is set to 5 Jo ules, with ma ximum sen s e d  transmissio n rang e at 80 m.  The traffic l o ad is  gen erat ed ra ndo mly betwe en [0...10] for e a ch  sen s o r  no de.  There is  a si ngle  base station  located at  the t op right -han d co rn er of the  simulated area  (200 m, 200  m).  Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS   ISSN:  2502-4 752     Prolon ging th e Lifetim e  of  Wirel e ss Sen s or   Networks usin g… (Ahm ed A. Alkathm a wee)  395 Furthe rmo r e;  a radio mod e l discu sse d in [28]  is use d  for the pro posed metho d . Based on  this  model; th e  se nder no de  ex pend s  ene rgy  to run  ra di o  electroni cs a nd a  po we r  a m plifier. O n  t h e   other h and, the re ceive r  n ode spen ds  energy to run  the radio el e c troni cs. In orde r to tran smit  numbe r  of bit s  p e r  pa cket (k)  over the  dista n ce (d) between   se nder an d  re ceiver n ode s,  the   dissipate e n e r gy of a node  is ch ara c te rized by:    2 ) ( d k E k E k T E amp elec n             ( 1 1 )     And the power co nsumpti on of a node   for re ceivin g this messa ge is charact e rized by   the expre ssi o n s:      k E k R E elec n ) (              ( 1 2 )         Figure 3. Flow-cha rt of the LPA-star  sea r ch al go rithm       The ele c troni cs  ene rgy Eel e c i s  affected  by seve ral factors such a s  filtering, mod u lation,  digital codin g ,  and  spreadi ng of the  sig nal. In addi tio n , the amplifi e r e nergy Ea mp is i n fluen ced   by facto r s like the  dista n ce d  bet ween  sen der  an d receive r   n ode s  a nd acce ptable bit-e rro r rate.   Simulation s a r e m ade  u s in g value s   100   pJ/bit/m 2  an d  50 n J /bit for  Eelec  and  Ea mp respe c tively.  The sim u latio n  para m eters are presente d  in Table 1  whi c h follo ws.        Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 25 02-4 752                   IJEECS  Vol.  1, No. 2, February 201 6 :  390 – 398   396 Table 1. Simulation Para meters  Parameter Value  Topographical Area  200 × 200 m 2   Location  of BS (meters)  (200 × 200 )  Number of  nodes   50  Transmission range (mete rs)  80  Initial energ y  of n ode  5 J  Eamp  100 pJ/bit/ m 2   Eelec 50  nJ/bit  Data Packet size   4k bit  Number of  trans mission packet s   2 × 10 4   Maximum traffic  node’s  10  α ,  β  0.65,  0.35       5.2. Simulati on Results  The n u mbe r   of node s  still l i ve is give n a s  a fu nctio n  o f  roun ds by u s ing th e two  different  approa che s  p r esented in F i gure 4. The  grap h indi cat e s that the propo s ed meth od outpe rforms  the EERP protocol.  Whe n  all pa ckets a r e  sent, the  n e twork lifetim e increa se d  with the LPA-star  algorith m  by roughly 2 5 % o v er that obtai ned fro m   EERP  protocol.  Furthe rmo r e, we can se e  that  the numbe r  of active nod es of the LPA-sta r  algo rithm is co nsi s t ently higher t h an that of the   EERP proto c ol.   The different  duratio n of time co rre sp o nding  to the first dea d nod e, compute d  usin g two  different a p p r oache s is list ed in  Tabl e  2. Obviou sly, the time  bef ore th e first  node  die s  in   th e   prop osed met hod is mu ch  greate r  than t hat taken  by the first nod e to die in the EERP method.    From Fig u re 4 and Tabl e  2, it is clear t hat the pro p o s ed met hod  outperfo r m s  the EERP  method in terms of maximi zation of net work  lifetime  and bal a n c in g energy con s umptio n.        Figure 4. Number of no des still alive as a function of ro unds based on the  two approaches  (LPA-s t ar and EERP)      Table 2. Nu m ber of Ro und s with the First Dea d  No de   Approaches  EERP  LPA-star  Round first node  dies  2743   5895       The simul a tio n  results in Figure 5 sho w  the avera ge remainin g ene rgy of the network for  both p r oto c ol s a s   a fun c ti on of t r an smi ssi on  rou n d s . Ou r p r op ose d  metho d  al ways re peate d ly  re-uses  opti m um path s   with minim u m hop  cou n t while th e ene rgy nod es i n   the route  pat h are  better tha n  th eir alte rnative  node s to  ro ute the  d a ta  packet s . The r efore, the p r opo sed  meth od  perfo rms  better than the E E RP proto c ol  in term s of  saving n ode  energy. This  indicates that  a   good e nergy balan ce i s  achieved in  a WSN throu gh o u r propo se d method.   Many appli c a t ions in WS Ns req u ire a timely  respon se, includin g  for example fi re ala r m  system s.The delay  in  tran smissi on  of a data pa cket from the sen s i ng nod es to the ba se stati o n   depe nd s on  the tra n smi s si on time, a nd  it shoul d b e   sho r t, whi c h  lead s to a  fast respon se  wi th  high  quality o f  se rvice.  The  co mpa r ison  betwe en t w o different app r oache s  i s  sh own   in Figu re 6.  Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS   ISSN:  2502-4 752     Prolon ging th e Lifetim e  of  Wirel e ss Sen s or   Networks usin g… (Ahm ed A. Alkathm a wee)  397 it can be  see n  that the pro posed alg o rit h m ha s  the shorte st delay  more 5 0 % than that obtai ned  by the EERP proto c ol.             Figure 5. Average n e two r k remai n ing en ergy  as a fun c tion  of transmi ssi on rou n d   Figure 6. dela y  in transmi s sion of a data  packet in the  two app roa c h e s (LPA -sta r  and  EERP)      6. Conclusio n    Energy re so u r ce  con s traint s are o ne of the mo st critical challenges  for wirele s s  sen s o r   netwo rks  (WSNs). In spit e of the fact  routing  sel e ction i s  quite  difficult as  a  result of en ergy  con s trai ned,  but thi s  i s  strongly  rel a ted to   extendin g net w ork lifetime.  Un even  en ergy  con s um ption  is an  inn a te p r oble m  in  WS N which le ad  to red u ce the  netwo rk lifetime. To p r olo n g   the lifetime of the wh ole  netwo rk   an d eliminate t he chan ce  o f  network  pa rtition, we h a ve  prop osed a n e w efficient routing  protocol called LPA – star p r oto c o l . The new m e thod u s e s  the  LPA-sta r  al g o rithm to  re peatedly fin d  an  optimu m  ro uting  pat h.The  optimu m  path  can   b e   sele cted  by favoring  the h i ghe st re sid u a l ene rgy,  mi nimum h o p  count an d lo west traffic loa d .  The LPA - sta r  proto c ol  al ways reu s e s  t he p a rt  of th e previou s   search  ope rati on to  re comp uted   the ne w o p timum routing  path with out runnin g  the al gorithm f r om  the scratch.Si mulation  re su lts  sho w  the app rop r iaten e ss and better p e r forma n ce of new p r oto c ol again s t EERP protocol wi th  rega rd s to en han ceme nt of the WSNs lifetime and  b a l anced en ergy con s um ption  with fast dat a   transmissio n across the ne twork.       Referen ces   [1]  Cha ndir a sek a ran D, T  Jay a barath i . W e rel e ss s enser N e t w o r ks No de  Local izatio n-A  Performan c e   Comp ariso n   of Shuffle d  F r o g  Le api ng  a nd  F i refl y Al gorith m  in  La bVIEW . T E LKO M NIKA Indo nes i a n   Journ a l of Elec trical Eng i ne eri ng.   201 5; 14(3 ) : 516-52 4.  [2]  Itu Snigdh, Ni sha G upta . Energy An d Evalu a ting Q u asi  Rand o m  Dep l oy me nt in Z i gbe e Bas e d   W i reless S ens or N e tw orks . 10th T E LKO M NIKA Indo nesi a n Jo urna l  of  E l ectrical  En gin eeri ng. 2 0 1 5 ;   15(1): 14 2-1 5 0 .      [3]  Rani a Kh ad im , Mohamme d  Erritali, Ab de lhakim  Maa d e n . Ran g -F ree  Loca lizati on  Schemes fo r   W i reless S ens or N e t w orks.  T E LKO M NIKA Indo nesi a n  Jo u r nal  of El ectric al E ngi ne erin g . 20 15;  16(2) :   323- 332.   [4]  Soro S, W end i B He inze lma n . Cluster  He ad El ectio n  T e chn i qu es F o r  Cover age Pr eservati on  I n   W i reless Se ns or Net w orks.  A d  Hoc Netw ork s , 2009; 7: 955 -972.   [5]  Selcuk  O ,  Cel a l O ,  Derv is K a rab oga.  A C o mp arativ e Stu d y o n  D i fferent ial Ev ol ution  B a sed  Ro utin g   Im plem entations for Wire less  Sensor Netw o r ks.  IEEE  Int.  Conf. Innovati o ns in Intelli ge nt S y stems and   Appl icatio ns (INIST A); 2012: 837- 844.   [6]  Z hang  H, Sh e n  H, T an Y.  O p timal E ner gy  Bala nced  Data  G a therin g i n   W i reless S ens or Netw orks .  IEEE Int. Conf. Parall el an d Di stributed Proc e ssing S y mp osi u m (IPDPS). 2007.   [7]  W u  X, Che n  G ,  Das S. Avo i din g  Ener g y   Holes i n  W S Ns  w i th N o n unif o rm Nod e  Dist ributi on.  IE EE  T r ansactio n s o n  Paral l el a nd  Distribut ed Sys t ems . 20 08; 19 : 710-72 0.   [8]  Jia J, Z h a ng  G ,  W u  X, Ch e n  J. O n  the P r obl em of En e r g y  Bal anc ed  Rela y  Se nsor  Placem ent i n   W i reless Se ns or Net w orks.  In ternatio nal J o u r nal of Distri but ed Sens or Net w orks.  2013.  Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 25 02-4 752                   IJEECS  Vol.  1, No. 2, February 201 6 :  390 – 398   398 [9]  W  Xu, et a l . D i stribute d  Opti mal Rat e -Re lia bilit y-L i fetime  T r adeoff In  T i me-Var yin g  W i reless S enso r   Net w orks.  IEEE Transactions  on Wireless Comm uninction.  2 014; 13( 9): 483 6-48 47.   [10]  Park J, Sahni  S. An Online  Heuristic F o r  Maxi mum Lifet i me Routi ng i n  W i reless Sen s or Net w ork.  IEEE Transactions on Com p uters . 2006; 5 5 (8 ): 1048-1 0 5 6 .  [11]  W u  C, Yuan   R, Z hou H.  A  Nove l Lo ad  Bala nced  And  Lifeti me M a xi mi z a t i o n  Ro uti ng Protoc ol  in   WSNs . Procee din g  IEEE Vehi cular T e chnol o g y  C onf. Sing a pore. 20 08: 11 3-11 7.  [12]  T s ai M, Yang H, Huan g W .   Axis-Based  Virtual C oord i nate Assi gn ment Protoco l  And De livery- Guarante ed R outin g Protoco l  in W S Ns . Proc. IEEE Int. Conf. Comput. Commun. 200 7: 2 234- 224 2.   [13]  Li X, Hon g   S, F ang  K.  W S N H A–GAHR: A   Greed y A nd  A  He uristic R o u t ing A l gor ithm  F o r W i reles s   Sensor N e t w or ks in Home Aut o matio n .  IET C o mm . 20 11; 5( 13): 179 7-1 805 .  [14]  Ran a  K, Z a veri M. A-star  algorithm for ener g y  effici ent rou t ing in  w i r e less  sensor net w o r k .  T r ends in   Netw ork and C o mmunic a tio n s . Springer. 20 1 1 : 232-2 41.   [15]  MJ T s ai, HY  Yang, W Q  Hu ang.  Axis- bas ed virtu a l co or din a te a ssi gn me nt protoc ol  and  del ivery- guar ante ed rou t ing protoc ol i n  W S Ns . Proc. IEEE Int. Conf.  Comp ut. Commun. 200 7: 22 34-2 242.   [16]  Abdu lla A, Ni shi y am a H, Y ang J, Ansari  N, Kato N.  H y m n : A Novel H y bri d  Mult i-Hop R outi n g   Algorit hm T o  Improve T he Long evit y  Of W S Ns.  IEEE Tr ansactions on Wireless Comm unications .  200 7; 11(7): 25 31-2 541.   [17]  Z hao Y, W u  J,  Li  F ,  Lu  S. On Ma ximizi ng  T he Lifetime  Of W i reless  Sen s or N e t w orks  Using  Virtu a l   Backbo ne Sch edu lin g.  IEEE Transactions on Parallel  and Distributed System s . 20 12;  23(8): 15 28- 153 5.  [18]  Ghaffari A. An Energ y  Effici e n t  Routing Pr oto c ol for W i reles s  S ensor Net w orks usin g A-star Algor ithm.   Journ a l of App l ied R e searc h  a nd T e chn o l ogy . 2015; 12( 4): 815-8 22.   [19]  Koen ig S, Likh achev M.  In crem en ta l  A . Proc eed ings  of the Neura l  Information Proc essi ng S y stems .   Vanco u ver, Bri t ish Col u mbi a , Can ada. 2 002.   [20]  Liu Y, Koen ig  S, David F . Spee din g  Up T he Calc ul ation  Of Heuristics F o r Heuristic  Search-B as e d   Plan nin g . Proc. the Nation al C onfere n ce o n  Artificial Intel lig e n ce. 200 2: 484 -491 .  [21]  Koen ig S, Likh achev M,  F u rcy D. Lifel o n g  Pl ann ing A.  Artificial Intelligence . 2004; 1 55(2 004): 93- 14 6.   [22] Yao J, Lin C, Xi e X, W a n g  A, Hung C.  Path  Plann ing F o r  Virtual Hu man  Motion Usi ng I m pr ove d -Star  Algorit h m .  Seventh Intern atio nal C onfere n c e  on Informa ti on T e chnol og y: Ne w  Ge nerat ions (IT N G).  201 0: 115 4-11 58.   [23]  Aine S,  Lik hac hev M.  T r uncated Incr ementa l  Search: F a ste r  Rep l an ni ng B y  E x plo i tin g  Su b Optimal i t y .   T r uncated Incr ementa l  Searc h : F a ster R epl ann ing  by Expl oitin g  Sub opti m a lity . 201 3.  [24]  Yoon  S, Shim  D SLPA. Sh ap e-A w ar e L i felo ng  Pl an nin g  A *  for D i fferenti a l W h e e l ed V e hicles.  IEEE  T r ansactio n s o n  Intelli ge nt Systems . 20 15; 1 6 (2): 730- 74 0.  [25]  Lu Y,  Hu o  X,  Arslan  O, T s iotras P.  Multi-S c ale  LPA *  w i th  Low  W o rst-C a se  Co mp lexit y  Guara n tees .  IEEE/RSJ Internatio nal C onfer ence o n  Intell ig ent  Rob o ts and  S y stems (IROS). 2011: 35 07 -351 2.  [26]  Park J, Sah n i  S. An Onli ne  Heuristic  F o r  Maxi mum  Lifet i me R outi ng i n  W i reless  Sen s or Net w o r ks .   IEEE Trans. On Com p uters . 200 6; 55(8): 10 48-1 056.   [27]  W u  C, Yuan   R, Z hou H.  A  Nove l Lo ad  Bala nced  And  Lifeti me M a xi mi z a t i o n  Ro uti ng Protoc ol  in   WSNs . Proc. IEEE Vehicu lar  T e chnolog y  C o nf erenc e. Sing apor e. 200 8: 113-1 17.   [28]  Heinz e lm an W ,  Chan drak asa n  A, Bal a krish nan  H.  Ener g y  Efficient C o mmu n icati on  Protocol F o r   Wireless Micro Sensor Networks . Proc. 33rd Ann. Ha w a ii Int .  Conf. S y st. Sci. 2000: 1-1 0 .       Evaluation Warning : The document was created with Spire.PDF for Python.