TELKOM NIKA , Vol.14, No .1, March 2 0 1 6 , pp. 319~3 2 5   ISSN: 1693-6 930,  accredited  A  by DIKTI, De cree No: 58/DIK T I/Kep/2013   DOI :  10.12928/TELKOMNIKA.v14i1.2743    319      Re cei v ed Se ptem ber 26, 2015; Revi se d De ce m ber  29, 2015; Accepted Janu ary 18, 201 6   A Contention-Based Routing Protocol for VANET       Deling Hu an g* 1,2 , Yusong Yan 1   1 Colle ge of Info rmation Sci enc e and T e chno l o g y , South w e s t Jiaotong U n iv ersit y ,    Che ngd u 61 00 31, Sichu an, C h in a   2 Colle ge of Sof t w ar e Eng i n eer ing, Ch on qin g  Univers i t y   of Posts and T e lecommunic a tio n ,   Cho ngq in g 40 0 065, Ch in a   *Corres p o ndi n g  author, em ail :  huang dl@c qu pt.edu.cn       A b st r a ct   In VANET s, vehicl es  as n o d e s are  se lf-org ani z e d  an d i n ter-co m mun i cat ed w i tho u t ce ntrali z e d   author ity. T h e  topol ogy for m ed by  ve h i cles  chan ges  qu ic kly, w h ich  ma kes routi ng  be come i n stabi lit y.  Po si ti on -b a s e d  ro u t in g ,  com p a r e d  wi th  tra d i t i o na l  ro u t in g ,  is mo re sca la ble  an d fe a s ib le . Th u s   i t  ha s  b een  prove n  stab ler  for VANET s t han  conv enti o nal r outi ng. H o w e ver, the fr equ ently  c h a n ged  topo lo gy  and   nod es d ens ity  coul d br eak t h e p a th a  p a ck et is fol l ow in g. T hus  desi gni n g  a r o b u st mul t i-hop   routi ng i n   VANET  is c hal len g in g. T h is  p aper  pro pos es  an  e nha nce d  positi on-b a se d   rout i ng protoc ol  c a ll ed CBG R ,  which takes into account th e  velocity a nd  directi on of ve hicles  in VAN ET . Simul a tion  results show  tha t   CBGR achiev e s  a high lev e l  of routing p e rformanc e  in terms of hop co u n ts, netw o rk latency and p a c k et  deliv ery ratio b o th in de nse or  sparse veh i cul a r ad-h o c netw o rks.    Ke y w ords : VANET , routing pr otocol, gre edy  forw arding, loc a l opti m al     Copy right  ©  2016 Un ive r sita s Ah mad  Dah l an . All rig h t s r ese rved .       1. Introduc tion  Vehicul a r Ad  hoc  Network (VANET s)  [1] is a mea n s of inte r-v ehicl e co mm unication,  usin g for safe  driving, drive r  assista n ce and  traffic ma nagem ent. In VANETs, vehicle s  a s  nod e s   are self-o rga n ize d , they communi catio n  in a di strib u ted fashio n with no ce ntralize d  autho ri ty.  More over, the vehicle s  are move fast, the t opology formed by them ch ang e s  qui ckly. Hi ghly  dynamic topo logy ma ke s  data tra n smi ssi on le ss rel i able ，   sin c e  the highly dy namic topolo g y  may re sult in  netwo rk di sconne ct fre q u ently. So  the  key p r obl em  of desi gn  a routing p r oto c ol is  kee p ing it a s  stable  as  po ssi ble, trying  to ke e p  the  link b e twe e n  two vehi cle s  while th ey a r e   transmitting i n formatio n.  Beside,  nod e s  in  VANET s are n o t subj ected  to  storage  and  po wer  limitation as i n  wirele ss  se nso r  net works. Vehi cl es  a s  no de in VA NET, are  su p posed to hav e   ample comp uting po wer and ene rg y. Howeve r, efficient multi-hop  routi ng in VANE T  is  chall engin g , due to the freque ntly cha nged to polog y. VANET routing protoco l s mu st ope rate   reliably in sce nario s em bra c ing hi gh spe ed nod es.   Significant V A NET protocol s have  bee n pro p o s ed,  and they ’re classified a s  topolo g y- based  and  p o sition -ba s e d [ 2]. Topolo g y-ba sed  rout in g  p r oto c ol s perfo rm pa cket  forwarding ,  usin g links’ i n formatio n th ey colle ct fro m  the  network. They find  out a path to  the de stinati on  before  rel a y the pa cket. Position -ba s e d  (ge ographi c)  routin gs  perf o rm p a cket f o rwarding, u s ing   the po sition  i n formatio n of  the  ultimate  destin a tion  a nd of  the  one -hop  n e ighb o r s.  Usually th ey  are  statele s s, with no n eed to  keep  the lin k inf o rmatio n ab out the wh o l e network. An   interme d iate  node forwa r d s  a pa cket to its neighb or   with the clo s est dista n ce to the positio n  of  the destinatio n. These day s, it is comm on that  vehicl es get a GPS unit on board, from wh ere   vehicle s   can  get their l o catio n  informati on. It has m ade  p o sition -ba s e d  routin g ea sy   impleme n ted  and  po pula r .Literatu r e s   have  con d u c ted evalu a tio n  stu d y of t opolo g y-ba se d   routing p r oto c ol s and po si tion-ba se d o nes[3, 4]. Un able to cop e  up with nod es’ high mo b ility    and mi nimu m tran smi ssi on del ay, topology-ba s ed   routin g p r ot ocol s p e rfo r m una ccepta b ly in   VANETs  [5, 6].   Position -ba s e d  routing, a s  is used by pro t ocol s like G r eedy Perimet e r Stateless  Routin g  (GPSR) [7] and Ge og ra phic  Routin g  Protocol (G RP) [8], is well suited fo r highly dyna mic   environ ment s such as VANET.    Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA   Vol. 14, No. 1, March 2 016 :  319 – 3 2 5   320 Intermedi ate  node i n   GP SR forwa r d s   a pa cket to a  radi o nei ghb or  whi c h i s  cl ose s t to  the de sinatio n. This ap pro c a c h i s   calle d  gre edy forwardin g . It is a s sumee d  that  ea ch n ode  can   determi ne its own po sitio n  usin g a GPS. Nodes e x chan ge thei r locatio n s  wi th neihbo rs,  and  obtain the  po sition of d e sti nation by a l o cation  se rvice. In som e  case s, the r e  might be  no  next- hop  whe n  greedly forwa r ding, GPSR  introdu ce s a   strate gy, ca lled pe rimete r ro uting. Ma ny     resea r ch [9-1 2] have improved GPSR, most of  whi c h worke d  on  plana rized g r aph s, whi c h  are  requi re d in  p e rimete r m o d e . Ho weve r t hese  schem e s  al way s  invo lve sig n ifica n t overhead s,  a n d   thus re du ce the efficien cy  of position - ba sed routing.   Nod e  in GRP  maintain s a neigh bor tabl e by perio dically broad ca sting Hello m e ssage. It   is a s sume d t hat ea ch  no d e  can  determ i ne its o w n  p o sition  u s ing   a GPS. Th e  positio ns of o t her   node s  are  de termine d  thro ugh flo oding   [13]. The  wh ole n e two r k i s  divid ed i n to  qua dra n ts  with   different level s . They  are  d eployed i n  a  hiera r chy ma nner.  Fou r  lo w level s   com pose a  high l e vel,   thus provide a distrib u ted locati o n  se rvice. This sched ule makes it overcomin g  GPSR and m any   other p o sitio n  based p r oto c ol. G R P forwards  pa ck ets in a n  g r eed y mode until i t  gets stu c k i n  a   local optim u m , where there are no ne w node s to  forward the packet to. It use s  a backtra cki ng  mech ani sm,  whe r e the  pa cket is  return ed to the p r e v ious h op a n d  a ne w n e xt hop  sele ction  can  be made.   The afo r em e n tioned  wo rki ng  sch edul e  of GRP m a kes it a  suitab le ro uting p r o t ocol fo r  VANET, but t here are  still  some short c omings.  T he  packet forwarding algorithm  is too si mpl e ,  that it only m a kes  use of  the location information to f o rward  the packets. T he  m obility of packet’s  sou r ce an d  destin a tion a r e  con s ide r e d , while th e  interme d iate  node’ s mov e ment isn’t  well  con s id ere d   when  sel e ctin g  next h op. A s  the i n te rm ed iate no de  mo ving, the li nk  betwe en th em  will probably vanish,  whi c h result  in the  routing instabil i ty. This  generates a routing rebuilt, whi c h  bring  mo re  n e twork  overh ead a nd  co st . Thus G R P  may not p e rf orm  as  effici ent a s  expe cted   whe n  deploy ed in VANET, where vehicl es are always in a relatively high mobility.   In the next section, a  ge ogra phi c rout ing  p r oto c ol  calle d CB RG  is p r op osed , which   improve the forwarding de cisi on s throu gh cont e n tion  among nod e s . CBGR i s  propo se d ba sed   on G R P to  o p timize th e e fficiency, it rede sign s th e  forwarding  a nd b a cktra c ki ng al gorith m   of  GRP, Th e pu rpo s e  of CB GR i s  to im prove the  p a cket delivery  ra tios  while  red u ce  the n e twork  delay. CBG R  keep s the a d vantage s  of  GRP.Furth e r more, it inco rpo r ate s  geo grap hic l o cati on   with no de’ s  mobile velo ci ty and dire cti on, to  be th e pre c o nditio n  for  cho o sin g  the next h op.  Simulation  re sults sh ow th at CBG R  a c hi eves a  hig h  l e vel of ro utin g pe rform a n c e in terms of  hop   cou n ts, net work l a ten c y a nd pa cket de livery ratio b o th in den se  or sparse v ehicular  ad-h o c  netwo rks.       2.  Contentio n -Based Ge ographic Ro uting  (CBGR)  2.1 ． Con t en tion-bas e d F o r w a r ding   We  notice th at, Locations  Service s  a n d  Forw a r din g   algorith m  a r e  the two  key  probl em s   in routing  pro t ocol s ba sed  on geo gra phi c location,  wh ich would aff e ct the ro utin g perfo rma n ces.   The hi erarch y locatio n   se rvice  empl oyed in  G R P o v erco me s m any othe r  ro uting p r oto c o l s in   usin g the d e s tination  zo n e  inste ad of  destin a tion l o catio n . Thi s  makes  GRP  be on e of t h e   highe st effici ent po sition-b a se d ro uting  proto c ol s, as  it can d e crea se the l o cation indete r mina cy   cau s e  by th e mobility of  the de stinat ion. CB G R   keep s this ad vantage, an d  red e si gns the   forwa r di ng al gorithm, imp o sin g  an ad ditional co nte n tion in spe ed and direction. Meanwhile,  CBGR  p r op o s e a rep a ir strategy  when  a  pa cket get s  stuck i n  a   local optimum,  while GRP  si mply  gives the pa cket ba ck to th e previou s  forwarde r.     2.1.1. Conte n tion Ba sed  on Speed   Priority i s  int r odu ce d in   CBGR. A  nod e calcul ate s   the p r iority o f  its n e ighb or befo r e   forwa r d it. We use th e pri o rity to sele ct the mo st suita b le nod e to relay, rather t han ma ke a  p u re  gree dy forwarding sele ction .   Stability is an impo rtant requireme nt of rout ing in  a  wirel e ss n e twork. A hig h  mobility  may cause the route fail ure if we use pure greedy  forwardi ng. To i n crease   reliability, GRP reads  the velocity of each nod e, and sel e ct reliable  nod es  with the lowe r velocity, abando ning oth e rs  even if they  are cl oser to the  destinatio n. On the other han d, nod es with lo wer velocity wou l d  make  a  sma ller lo cation  cha nge s  whil e exch angi n g  Hell o me ssag e, this  will prolo ng th e   neigh bor tabl e’ lifetime.    Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       A Contention - Based  Routin g Protocol for VANET (Deli ng Hu ang )  321 There a r e two app roa c h e s to get the n e i ghbo r’s vel o ci ty. One can   write it s o w n  spe ed in   hello me ssag e, thereby th e spe ed is  known by  others  along  with the bro a d c asting of hell o   messag e. Another way is that, each node  can  cal c ulate the ve locity of its neigh bor by  the   following formula:     （ node _lat  _ lat  node _long  _long)                                                                                          (1)    Whe r e no de_ lat, node_lon g and timest amp j  are the  latitude, longi tude and tim e  of the   neigh bor at time j respe c tively, and nbr_lat, nbr_lo n g  and timesta m p I  are the l a titude, longit ude  and time of the neig hbo r  at time i read  from  neig h b o r table.  We  add an  additi onal field n a m ed  velocity to the neigh bor ta ble. To minim i ze  the  comp uting co st wh en rel a y a pa cket, each  no de  doe s this calculation when  receiving the  hello  me ssag e, and upd ate s  the neig hbo r table.  Whe n  forwa r ding p a cket s, we  use P v  to de cide  the  prio rity of the  neigh bo rs. F o rmul a 2  defi ne  the veloc i ty priority:    1                                                                                                                                           (2)    Thus CB GR  sele cts the n e xt hop b a se d on  a  conte n tion of  spe e d . The  one  of the   lowe st sp eed  will get a high est velocity priority.    2.1.2. Conte n tion Ba se o n  Direc t ion   Becau s e  of the ob sta c les,  node s in diff erent  road s cannot commu nicate with  e a ch other  unle ss  one  is an  exten s i on of the  other .  Con s id e r  sce nari o  in  Figure 1,  Node  N1  i s  at  the  cro s sing. At t hat mom ent,  the current fo rwa r d e r  C  wil l   pic k   N 1  a s  t he n e xt hop   with a  differe nt  moving direct ion. Ho weve r, since th e n ode is  alway s  moving fa st in VANET,  N 1   may be o u t of  C’ s radio  ra n ge. In fa ct it  woul d b e  b e tter if  C  ch oo s e s  N 2  at  that  time. So it’s  necessa ry for the  neigh bou r to  content b a se on the mo ving dire ctio n .  For a long -lasting lin k, the one  with  the  same di re ctio n as the curre n t forwa r de r will be a go od  candi date.       Figure 1. Jun c tion no de s moving towa rds differe nt directio n         As discusse d before, we can u s e the l o catio n  at two different m o ments to cal c ulate the   dire ction of a node.         node_lat  node_lat  node_long  node_long                                                     (3)    Whe r e  no d e_la t  and  n ode_ long  a r e the  coordi nate s , a n d  t1  an d  t2   are two different time  points. In ord e r to red u ce the impact o n  relay pa cket, node cal c ulates  Dir  wh en re ceiving  the   Hello me ssag e, and then u pdate s  its nei ghbo r table. Let  P d   stand for the prio rity base d  on no de  moving direct ion, we defin e P d  as the following fo rmul a:      1 |  |                                               (4)        N o de  r e ad   P d   from neigh bo r table to deci de a better n e xt-hop befo r e forwa r di ng.   Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA   Vol. 14, No. 1, March 2 016 :  319 – 3 2 5   322 2.2 ． De al  w i t h  Dead -en d  Problem  Sometimes  when g r ee dy forwarding p a c kets, it  ca n lead to blo c ke d route s   whe r e the r e   are n o  next h ops to forwa r d the pa cket to. GRP  ado pts ba ckt ra cki n g , which retu rn the pa cket to   the p r eviou s  nod e  whe r e  a n e w next  hop  sele ctio n can  be  m ade [8]. T h is me chani sm   will  prob ably increase the hop s to the desti nation,  theref ore in cre a se the transmission delay. Th e   long-kn own d ead-end p r o b l em is  depi cte d  in Figure 2.      Figure 2 ． No de  x ’s   voi d   with res p ec t to  D.      The di stan ce  betwe en D a nd x is the ra dius  of the a r c aroun d nod e D. The a r c  arou nd x   stand s fo r its  radio  ra nge.  Although th ere are two exi s ting  path s  to  D,  x-y-z-D  a nd x-w-v-D, x  will  cho o se n e ith e r  of them  u s ing g r e edy fo rwa r di ng  [7]. There need s  to be some o t her mechani sm  for x to forward pack e t s  in this  s i tuation.   Cla ssi cal pro t ocol  GPS R  use s   pe r i me te r  fo rw ar d i ng  to solve the local  optimal. When  there i s   no  n e w  nod e to  relay in  gre e d y  mode, th e  l ong-kn own  right ha nd  rule  is i n trod uced  to  find a path around the  void . Perimeter forwa r di ng will  come b a ck to  greedy forwardin g  as  soo n   as a  ne w nod e  ap pea rs, which   is geo graphi cally  cl oser to th e p a cket’s d e stin ation than th e n o d e   swit ch to  pe rimeter mo d e . The  short c omin g of  p e rimete r fo rwarding  is p l anar g r ap hs are  requi re d. An  algorith m  fo r rem o ving  e dge s from th e g r ap h that  are n o t p a rt  of the   Relativ e   Neig hbo rho o d  G r ap h  or   Gabri e l Gra p h  a r e  also  re quire d to   yie l d a  network  with n o   crossing  links [14, 15]. This will defi n it ely increase the routing  cost.  GRP, as men t ioned befo r e ,  use a backt rackin g mech anism to retu rn the pa cke d  to the   previou s  no d e , where a n e w next hop  sele ction  u s in g gree dy mo de ca n be m ade. Thu s  no  new  mech ani sm i n trodu ce d to solve the p r o b lem. A node  will eliminate  local o p timal  neighb ors o n e   by one until  a valid neig h bor i s  foun d  or the p a ck et -life co me s to the en d. This trial  and  error  method will p r oba bly incre a se the h op counts a nd the  network late ncy.          Figure 3 ． C  i s  the local opti m al node of s with destin a tion  D       The intuitio n  behin d   CBG R  i s  eve n  if  we can’t  g e t an y clo s er to th e de stinatio n, we  won’t  go far  away from it. So we go b a ck, b u t neithe r  ret u rn s that mu ch to th e pre v ious h op a s  in   GRP, no r fol l ow a  fixed  cou n ter  wi se  seq uen ce  a r oun d the  vo id  as in GP SR. We let the  neigh bors of the local opti m al node co ntent again.  The one cl osest to the destination got  the  highe st p r io r. If  C  get m o re  than  on e nei ghb ors with th e  sa me  clo s est   distan ce  to t he  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       A Contention - Based  Routin g Protocol for VANET (Deli ng Hu ang )  323 destin a tion, t he o ne  whi c h  is furthe st to   C   will  win the contention.  T h is i s   because there i s   a  void   ahea d; the further the n o d e  is away fro m   C , the easi e r it can byp a ss the  voi d . See Figure 3  for  an exam ple.  N 1   and   N 2   lies on th e a r c  wi th the  sam e   distan ce  to n ode  D.  Note t hat in th e figu re,   N 2   is mo re sui t able than  N 1   to be the next hop.    2.3 ． Combini ng All Conte n tions   We  no w p r e s ent th e full  CBG R   routi ng al gorith m , whi c h  com b ine s  all  the  above   mentione d co ntention s  tog e ther.    Step 1.  Whe n  a so urce n ode o r  an int e rme d iate  no de send s pa ckets, it ch ecks i n  it s  neigh bor tabl e, to find o u t  the entry   of the pa cket’s u l timate de stin ation. If there  is a n  e n try, the  packet  will be delivered  directly to the  destinati on  successfully, and CB GR  ends. If there i s n’t  any entry, th e sende r  will  sel e ct a  no d e  in it s si ngl e-ho p radio   neigh bor,  whi c h i s  g eog ra phic  clo s e s t to the destinatio n. This  step loo p s an d quits  whe n  the followin g  two ca se sho w  up:   Ca se 1: if there a r e mo re  than one no des, wh ich form a set  call ed set_ 1, sat i sfy the  rule, goe s ste p  2;  Ca se 2: if there are no no d e s  satisfy the rule, goe s ste p  4;  Step 2.  Cont end  b a sed  o n   velocitie s . The send er cal c ulate  P v  , usin g form ul a 2, for  each  can d ida t es in  set_1,  cho o ses the  one  with hi gh est P v   as the  next ho p. Th e alg o rithm  g oes  to step 1. If  there a r e two n ode s and ab o v e, which form a set calle d set_2, sati sfy the rule, goes  step 3;   Step 3.  Co ntend ba se d on  dire ction. Th e sen d e r  cal c ulates P d,  u s i ng formul a 4,   for eac h   can d idate in  set_2, choo ses the on e with highe st  P d  as the next hop, and the  algorithm g o e s  back to  step  1; If there  a r e  still mo re  than on e  n o des sati sfy the rule, the  sen der pi cks one   rand omly, an d the algorith m  goes b a ck  to step 1.  Step 4.  B r ea k throug h d e a d -en d . Th e sende r relays the pa ck, u s in g sch edule  prese n te d   in se ction  3.3 .  If there is  n o  neig hbo r e x cept  the  on e wh ere the  packet i s  fro m , the se nde r will   carry the pa cked u n til there is a fre s h  hello me ssag e or expi re T T L, then the  algorith m  go es  bac k t o  st ep 1 .   By competitions, no de can pick up  a be tter next-hop tha n  G R P in vehicl e ad hoc  netwo rk.  We  must  cla r ify there  i s  rarely po ssi b ility for ou r al gorith m  de gene rat ed to  pu re  greedy   without co ntention. We  define  th e t w o  nod es wi th the  sam e  dista n ce fro m  send er, if  the  differen c e i s   within  10 m e ters. So  there will  always be  co ntentio ns, e s p e ci all y  in cro s sro a d ,  whe r e the di rection  conte n t ion is highly required.   Re call that  al l nod es  main tain a n e igh b o r tabl e, whi c h  stores the  location s, velocitie s   and directio n s  of their si ng le-ho p   ra dio n e ighb ors. Thi s  table p r ovid es all informa t ion requi re d for   CBGR’ s  fo rwardin g  d e ci si ons, b e yond   the pa cket s t hemselves. F r om thi s  p o in t of view, CB GR  make a n egli g ible spa c e cost to improv e the routing  perfo rman ce  of GRP.    3. Simulation Resul t   In this section we will com pare the performance  of CBGR  with GRP. The ex perim ents  were  conducted on OP Net model er. M edium  ac cess cont rol (M AC)  i s   IEEE 802.11g,  with a  radio rang e of 250m. The mobility trac e s  we re gen erated on an area of 3000m  1000m u s ing   VANetMobiSi m [16], a  vehicul a r t r affic gener ator. The mi cro-mobility is controll ed  by  IDM_IM[17].      Table 1.  Simulation Para meters  Parameter Value  Net w ork simulator  OPNet 14 .5   Mobility  simulator   VANetMobisim  Dimension 3000m×1000m   Simulation time   600s  Routing Protocol   GRP, CB GR   Average vehicle speed  50 km/hr   Transmission pow e r   0.005 w  802.11g r a te   11Mbps  Source-destination  Pairs  Random   Packet interval  0.2s  Packet size   500B y t e   Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA   Vol. 14, No. 1, March 2 016 :  319 – 3 2 5   324 For ea ch  sim u lation run, 2 0 % sen der-recei ve r pai rs from the net work  were ra ndomly   sele cted. Ea ch p a ir ex ch ange 2 0  pa ckets  over  5  seco nd s. We  measured th e pa cket d e li very  rate (PDR) versus the n u m bers of veh i cle s  parti ci p a te in (Figu r e  4). Each poi nt in the gra phs  come s  out from 10  inde p ende nt ru ns.  PDR  sh ow s  good  re sult s  for ou r a p p r o a ch  co mpa r e d  to  GRP. This is becau se  CBGR select s the best suit a b le node, u s i ng the mobili ty information, to   relay the  pa cket to.  We  ca n see i n  the   very le ft  pa rt,  wh en network  i s  relatively  sp arse, CBRG   has ove r whel ming adva n ta ge over G R P  in PDR, t han ks fo r allo win g  ca rrying  pa cket whe n  th ere  is no n ode to  be delivered . The figure il lustrate s  CBGR i s  stabl e with a hig h  PDR a bove 9 0 % ,  neverthel ess  the netwo rk i s  den se o r  sp arse.            Figure 4. PDR vs. Nod e  d ensity   Fi gure 5. Hop  count vs. No de den sity      Figure 5  sho w s th e ave r a ge nu mbe r  of  hop s for  a p a cket du ring   routing  to its  ultimate  destin a tion  compa r e  with  GRP. The  re ductio n  in h o p  co unt for  CBGR i s  du e to not ba cktra cki ng   whe n   come  t o  the  dea d-e nd. CB GR ke eps the  pr ogress the  pa cket ha s m ade   by last  hop,   while   CBGR obliterate  it.    Figure 6 de picts the  en d-to-end d e l a y. The sho r ter laten c y  for GRP e a rly in the   simulation is the result of small PDR. Packets  that  do  not get d e livered to th e de stination  do n o t   contri bute to  the latency.  Thus  CBG R  gets l a rg e r  PDR.  Ho w e v e r it is b e tter to re ce ive  somethi ng th an nothi ng.  Whe n  no de  cou n t rea c h e s  mo re tha n   100, CB GR  gets le ss lat ency  becau se of th e more  re aso nable  choi ce  of the interm ediate no de s  unde r compa r able P DR  wi th  GRP. Recall  that althoug h the choi ce  is ba se d on  som e  extra  com puting,  we a r rang e the   cal c ulatin g at the time receiving a Hello  mess age rather than the time relaying t he packet. Th us  the comp utation co st ra rely  contrib u tes t o  the latency.            Figure 6.  Latency vs. No d e  den sity      Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       A Contention - Based  Routin g Protocol for VANET (Deli ng Hu ang )  325 4. Conclusio n   This  work ai ms at i m proving the  rout e st ability in vehicular ad-hoc  networks.  The  simulatio n  re sults  have  proved the  pro posed al gor it hm ad apts it self to VANET  in varying  n ode  den sities. In f u ture,  we pl a n  to ma ke th e forwarding  deci s io n with  an ove r lap  o f  city map. T hat  will make our algorithm perf o rm  better in variou s scenarios.    Ackn o w l e dg ements   This  wo rk wa s  sup porte d  by Natio nal  Natural S c ien c e F oun datio n of  China  (Grant  No.   6130 9032 )Progra m  fo r I nnovation  T eam Buil din g   at In stitutions of  High er Ed ucation  in   Cho ngqin g   (Grant  No. KJT D 201 310 ).  Scientifi c  a nd T e chnolo g ical  Research P r og ram  of   Cho ngqin g  M unici pal Edu c ation Com m ission (K J1 400 431)      Referen ces   [1]    F an Li, Yu W ang. Ro uting i n  Vehic u lar A d  Hoc Net w or ks: A Surve y .  IEEE Vehicul a r Technol ogy   Maga z i ne . 2 0 0 7 ; 2(2): 12-22.   [2]    K Katsaros, M   Dian a ti, Z  S un.  Surve y   of  Rou t ing Pr otoco l s i n  Ve hicu lar  Ad  Hoc  Net w o r ks . Advanc es   in Veh i cul a r Ad -Hoc Netw orks: Develo p m ent s and Ch all e n g e s . 2010: 1 49- 170 .  [3]    Loch e rt C, H a r t enstein  H, T i an J,  F u ssl er H,  Herma nn,  D,  Mauve, M.   A r outin g strate gy  for ve hicu lar  ad hoc n e tw orks in city envir on me nts. 2003 .  Proceedi ngs  of IEEE Intelligent Veh i cl es S y mp osi u m .   200 3:   156- 161.   [4]    Naum ov V, B a uman n R, Gro ss T .   An eval u a tion  of Inter-V ehicl e A d   Hoc  Netw orks Base d o n  R e a listi c   Vehic u lar T r ac es.   Proc. ACM MobiH o c’0 6  C onf. 200 6: 108- 119.   [5]    Sanj a y   K, Dhur and her, Moh a mmad S Obai d a t.  GROOV: A  Geogra phic  Ro uting Over VA NET s  and Its   Performanc e E v alu a tion.  Gl ob ecom 2 0 1 2 -Co mmunicati ons   QoS, Reli ab ilit y  and  Mod e l i ng  S y m posi u m.   201 2: 167 0-16 75   [6]    R Hussey ,  E Huff,  Z  Shinw a ri, V Hnat yshin.  A comp arative study  of proactive a nd reactiv e   geo grap hic a l r outin g protoc ol s for MANET .   Procee din g s of  12th Int. Conf.  on W i rel e ss N e t w .  20 13 : 1 - 6.  [7]    B Karp, HT  Kung.  GPSR: gr e edy p e ri meter  stateless r outin g for w i rel e ss  netw o rks.  Proc . ACM/IEEE   MOBICOM. 20 00: 243- 25 4.  [8]   Z  Li.  Geogr ap hic ro utin g pr o t ocol  and  si mu latio n .  Proce e d in gs of  2nd  Int. W o rkshop  on C o mp ute r   Scienc e an d Engi neer in g. 20 09: 404- 40 7.   [9]    Kim YJ, Govindan R, KARP B, Shenker S.  On the Pitfalls of  Geograph ic Routin g.  Proc. of the 3rd   Internatio na l W o rksho p  on DI ALM-POMC .  2005: 34- 43.   [10]    H F r e y , I Sto j menov ic.  On d e livery  gu ara n tees of fac e  a n d   co mb in ed  greedy-fac e ro uti ng i n  a d  h o c   and se nsor net w o rks.  Proceedin g s of the 12th ann ual i n te rnatio nal co nfe r ence o n  Mobi l e  computi n g   and n e t w orki ng . 2006: 23- 29.   [11]    Y Kim, R Gov i ndan, B Kar p ,  S Shenker.  L a z y  cr oss-li nk re mov a l f o r g eog raph ic ro uting.  Procee din g s   of the 4th inter natio nal c onfer ence o n   Embe dde d net w o rke d  sensor s y ste m s. 2006,    [12]    W ang Yin g , Xu Hui- bin, C h a Dai-fe ng. A  Novel  Routi n g Protoco l  for VANET S . TE LKOMNIKA  Indon esi an Jou r nal of Electric al Eng i ne eri ng.   2013; 1 1 (4): 2 195- 219 9.   [13]   OPNET  Model er. Riverb ed T e chn o lo g y , Inc.   [14]    Agabr iel  K, So kal R.  A n e w   s t atisti cal  appr o a ch to  g eogr ap hic v a riati on  an al ysis . Syste m atic Z o o l ogy .  196 9; 18: 259 – 278.   [15]    T oussaint G.  The rel a tive ne i ghb orho od gr a ph of a finitep l anar set.  Pattern Recog n iti on.  1980; 12( 4):  261- 268.   [16]   VANetMobisim home.  http://V ANet.eureeom. f r/.   [17]   Vaib hav Go db ol. Intell ige n t D r iver Mob ilit y M ode l an d T r affic Pattern Gen e r ation  base d  O p timizati on of  Reactiv e  Proto c ols for V e h i c u lar A d h o c N e t w orks .   Inter n a t iona l Jo urna l  of Informatio n   and  Netw ork   Security.  201 3;  2(3): 207-2 15.     Evaluation Warning : The document was created with Spire.PDF for Python.