TELKOM NIKA , Vol.11, No .3, March 2 0 1 3 , pp. 1652 ~ 1664   ISSN: 2302-4 046         1652      Re cei v ed  No vem ber 5, 20 12; Re vised Janua ry 2 6 , 20 13; Accepted  February 8, 2 013   A Novel QoS Routing Algorithm in Wireless Mesh  Networks       Liu Hui   Jian g x i Un ivers i t y  of Scie nce a nd T e chnol og y  Ganzho u, Chi n a  e-mail: l x yl iu hu i@16 3.com       A b st r a ct   W i th the rapid deve l op ment o f  informati on techno logy, pe op le ’ s  da ily life be comes more a nd mor e   dep en dent on  w i reless technol ogi es. W i reless mes h  net w o rk consists  of a numb e r of characteristi c s   associ ated w i th the return path,  w i th  a strong fault toleranc e,  stability, w i d e ly used by  the light to the ci ty   netw o rk constr uction,  mi litary  app licati ons,  and k e y servic e prov ider s  an d other fi elds.  Co mp ared w i t h   traditio nal w i re d commu n ic ati on techno lo gie s , how to  provide qu alifi ed QoS routing ser v ice is a prima r y   p r o b l e m  fo r wire l e ss  me sh  ne two r ks wa i t i n g  fo r e ffe cti v e so l u tio n .  Re ga rd in g  th i s  p r ob l e m ,  th i s   p aper  app lys the theory of Evolution a ry Game to QoS  routing algorit hm fo r  w i reless me sh netw o rks a n d   prop osed  a n o v el a l gor ith m  c a lle d EGW R A  w h ich can  not   only  improv e the p e rfor ma nce of traditi on al  QoS   routin g protoc o l s but also b e  a b le to re d u ce t he cost of the routin g al gorith m .      Ke y w ords : w i reless tech no lo gy; QoS routin g; me s h  netw o rks; evolutio nar y game theory     Copy right  ©  2013 Un ive r sita s Ah mad  Dah l an . All rig h t s r ese rved .       1. Introduc tion  Wirel e ss loca l area netwo rks are con s id ered a s  one of the  viable solutio n s for providin g   Internet conn ectivity to mobile users. Th e comm ercial  wirele ss LA Ns tod a y, e.g., IEEE 802.11 ,  provide si ngl e hop wirel e ss con n e c tion to the infrastructure. All th e mobile use r s need to re si de  within the a c cess point’ s  re ach, i.e., within the  basi c  service  set wit h  a radiu s  of  100 ~30 0 met e rs.   In order to provide full coverag e  in relatively  large size area s we n eed to deploy a large number  of access poi nts (AP). Thu s , the conve n t ional infr a s tructure-ba s ed  wirele ss LA Ns d o  not scale  well with the t a rget coverag e  area a nd n u mbe r  of nod es.   We ca n cla s sify wirele ss networkin g architec tu re  as follows 1 )   point-to-m u ltipoint  infras t r uc ture-aided approac h  lik e  wireless  s i ngle hop net work s   (e.g., IEEE 8 02.11 wireless  LAN) a nd 2)    peer-to-p e e r  multihop ap proac h  e.g., mobile ad h o c  netwo rks (MA N ETs).   The differen c e between m e sh  netwo rks and conv ent ional infrastru c ture  wi rele ss LANs  is the fa ct that mesh  net works result in a   multiho p  topology  which  req u ire s  decentrali ze d  coo r din a tion. The differen c e between m e sh net wo rks and the mobile ad hoc networks re side s in   the existence  of the infrastructu re conn ection.  The a c cess point s deploye d  can  act both as a   peer of the internal wi rele ss ad ho c ne twork and  th e bridge to the wire d network. To pro v ide   s u ffic i ent infras truc ture acc e s s   b and wi dth, multiple acce ss p o in t s  ca n be de ployed withi n  th e   netwo rk. T r af fic balan cin g  can b e  achie v ed by  the underlyin g me sh ro uting p r otocol. The  mesh  netwo rk featu r es p r e s e n ted  above lend t hemselves to  easy scala b il ity.      Wirel e ss me sh networks  seaml e ssly integrat e the s e two network architectu res. This  integratio n is  obtaine d by the propo sed  WM R prot o c o l , implemente d  in ea ch wi reless no de. T he  con n e c tivity to the wi red  backb one i s   provide d   by the wirele ss  infrast r u c ture  acce ss p o in ts.  Each no de in  the network is both a se rvice pr ovid er and a servi c e con s um er, i.e., each no de  has forwa r di n g  ability similar to the nod es’ fun c tionali t y in MANETs.     As a new type of wirele ss netwo rk, wi rele ss me sh  netwo rk [1, 2, 19, 31-34]  con n e c t  mesh n ode s throug h wirel e ss links to construc t a dynamic topol o g y, self-org a n izin g and m u lti- hop wi rele ss interco nne cted netwo rk.  Compa r ed  with the tra d itional sin g l e -ho p  wirele ss   netwo rks, it can extend co verage,  enh a n ce  robu stn e ss, redu ce deployme nt cost and incre a se   cap a city. Co mpared to the traditional  switch ed  n e tworks, wireless Me sh netwo rk  cabl ing  betwe en nod es rem o ved need s, but still has a di strib u ted netwo rk  provide s  red u ndan cy and re- routing. In the  wirele ss Mesh netwo rk, if you w ant to add a new d e vice, simply pl ug in the power  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     A Novel  QoS Routin g Algorithm  in Wirele ss M e sh Net w orks (Li u  Hu i)  1653 on it,  it can automatically config ure itse lf,  and determine the best multi-hop transmi ssion p a th.  Add or mobil e  device, the network top o logy  cha nge s can auto m atically find and automatically  adju s t the tr affic routing in orde r to  obtain t he most efficient transmissio n  path. A typ i cal   Wirel e ss me sh netwo rk  ca n be de scribe d like Figu re 1 .   Wirel e ss m e sh network’s  b u sin e ss i s  usually  gathe re d in the Me sh Ro uter o r   Gateway,  easily lead to local network conge stion,  makin g  it difficult to maintain network  globally opti m al  routing. Th us routing p r ot ocol s mu st b e  able to  ad apt to this sit uation so a s  to provide b e tter  QoS for the  use r s. So, the rese arch o f  wireless  m e sh net work routing p r oto c ol is of gre a t  signifi can c e.           Figure 1. Typical st ru cture  of wirele ss m e sh n e two r k      2. Related Works  Reg a rdi ng th e Qo s proble m  of Routin g  Algorit hm for Wireless  Mes h   Networks , lots  of   schola r s in thi s  filed have  made some a c hievem ents.  Some of them with rep r e s entatives can  be   listed a s  follo ws. Vo, Hu ng  Quoc [3, 4, 16, 17, 18]  pro pose a novel  approa ch to control the traf fic   to avoid cong estion  by de couplin g forwa r ding  proc ess from the  rout ing p r o c ess.  The p r op osal  is  intere sted in  provisi onin g   quality of se rvice gu ara n tees fo r pla n n ed Wi rele ss  Mesh  Net w o r ks  whi c h are bei ng used wi de ly as a bro a d band  wirel e ss acce ss net work. Zho u , Hao [5, 6, 12,  13]  focu se s on  QoS ro uting  with ba nd wi dth co nst r ai nt in multi-radio multi-channel WMN, and  prop oses  a n e w multimet ri c and  a QoS  routing p r ot ocol MM QR.  The ro uting  metric h a s t w o   advantag es.  First, it repla c es the tra n smissi on rate  of ETT with available ban d w idth so that the  node s  with light load a r e  more li kely to  be sel e cte d . Secon d , it take s the  chan nel diversity into   accou n t and assign s a wei ght to each link acco rdin g to the channe ls of links within the range  o f   three ho ps. Sun, Xuemei  [7, 8, 14, 1 5 ] propo se s a QoS routin g algorithm b a se d on cult ure - particl e swa r m optimizatio n algo rithm s . The alg o rith m use s  th e  dual-evolutio n  mechani sm  of  culture algo ri thms and a c hieves furth e r  impr ovem e n t on global  optimum location mutati on   particl e swa r m optimizatio n algorith m s  (MPSO) by  i n trodu cin g  the con c e p t of inertia weig ht.  Zhou, Ha o [21, 22, 23] propo se s a ne w multim etri c and a QoS routing p r oto c ol MMQ R. The  routing  metri c  has t w o a d vantage s. First ,  it repl aces t he tran smi s si on rate  of ETT with availa ble  band width so  that the nodes with light l oad are mo re  likely to be selecte d . In additional, it takes  the chan nel diversity into accou n t and assign s a  we ight to each link acco rdin g to the chann els  of links withi n  the range  of three hop s. Agarwal,  Anjali [24, 25,  26] propo se s an Ants-in-Mesh  (AIM) ro uting  proto c ol for  wirel e ss me sh netwo rks,  whi c h is b a sed on ide a s  from the nat ure - inspi r ed Ant Colo ny Optimization  (ACO) frame w o r k. AIM agent distribut e s  forward ants  on   deman d to search for the route s  to the  desti n a tion and then activates co rrespo nding ba ckward   ants to  confirm the ro utes and  up date  the phe rom one. AIM en able s  only th e de stination  to  Evaluation Warning : The document was created with Spire.PDF for Python.
             ISSN: 2302-4 046   TELKOM NIKA  Vol. 11, No . 3, March 20 13 : 1652 – 1 664   1654 cho o se k mu ltiple paths b a se d on Ants Phero m on e ,  which is ba sed on  several link-releva nt  Quality of Se rvice  (QoS )  metrics. Ron g  Bo [ 27, 2 8 ,  29, 30] p r o pose a  novel  netwo rk g r a p h   prep ro ce ssin g app roa c h t o  enabl e traf fic engin e e r i ng and  enh a n ce th e pe rforma nce of QoS  multica s t ro uting alg o rithm s . In this  app roa c h,  we e m ploy pri o riti zed  admi s sio n  co ntrol  sch e me   and devel op  a utility-con s traine d optima l  priority gain  policy.   Traditio nal Q o S routing al gorithm s like  the  achievem ents listed ab ove  only conside r ed  singl e obje c ti ve perfo rman ce p a ra meters, su ch a s  d e lay boun d  or ba nd width  limitations,  or  static multi-o b jective con s train ed  situ ati on. WM N can not m eet the nee ds of Ge ne ral  Req u ire m ent s for  som e   busi n e ss li ke  dynamic m u lti-obje c tive  perfo rman ce,  su ch a s  d e l a y,  band width a n d  Freq uen cy con g e s tion.   This  pape r  applie s the t heory of Ev olutiona ry G a me to Q o S routing  algo rithm for  wirel e ss m e sh networks which  ca n not  only improv e  the pe rform a nce  of traditio nal QoS  routi ng  proto c ol s but also b e  able t o  redu ce  the  co st of the ro uting algo rith m.  We a r e g o ing  to extract a  stable core i n  MANET in terms of mobilit y in the goal t o  se rve  QoS-aware  routing to ta ke network m obility to  fi nd  the sp eci fi c resou r ces.  S u ch an  extra c tion   can de fi n e  a sub s et of MNsin the netwo rk whe r e hi s  mobility is low and the lin ks b e twe en them  are reliable i n  time. Therefore, the sel e cted p a th  throug h this co re is mo re st able in term s of  mobility, and con s e que ntly the require d  QoS are mo re guaranteed . Indeed, we can  fi nd a pa th   that reque sts our requi rem ent in QoS such a s  band width, but the mobility of some interme d iate   MNs  con s i s ting of this path is high. Taking in to acco unt the coope ration bet wee n  MNs in terms  of mobility is  a promisi ng i dea to  fi n d  th e ade quate  stable core an d co nsequ ent ly a stabl e pa th.  In this asse ssment so a s  to extract this co re, we use a co ope rative game theory. For this  obje c tive, we consi der M N s in MANE T as players, and we try to  fi nd a coo perative co ali t ion   (partition) of players that minimizes  the mobility criteria in the net work.       3. Summar y   of EGWRA  3.1. The fra m e w o r k o f  EGWRA  EGWRA, our propo se d archite c ture, is  desig ned to  take full ad vantage of WM N  architectu re.  EGWRA mixes p r oa ctive route co mputa t ion for route r s and o n -de m and path  se tup   for clients. This design  eases the  management of  client m obility and reduces routing table  si ze.  Proa ctive rou t e comp utatio n is pe rform e d usin g a Di stance Ve ctor  (DV)  app roa c h. On-d eman d  path setup i s  perform ed b y  new extensions introdu c ed in the rou t ing proto c ol in orde r to take  advantag e of the architectu re of WM Ns.   In EGWRA, the ba ckbon e  beco m e s  totally tr anspare n t to the clie nts, whi c h do  not  need to emb ed any new feature. Thi s  mean s that  if two clients a s soci ated to different WM Rs  wish to com m unicate, the set of WMRs will forward the traf fi c at  the IP level and not at the  link  level. To obtain su ch a b ehavior, WM Rs h a ve to be more tha n  a simple fo rwarde r and  more  than a simpl e  router. In particul a r, on the client  su b netwo rk inte rface, whi c h can be descri bed   like figure 2.          Figure 2.The  frame w ork of  EGWRA    Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     A Novel  QoS Routin g Algorithm  in Wirele ss M e sh Net w orks (Li u  Hu i)  1655   The  WMR acts in  such a  way to let local c lie nts thin kthat remote  client s a r e in  the  local WLAN. Then, it is up to the WMRs to  fi nd out to which WM R the  client is asso ciated  and  route the pa ckets a c co rdin gly.  The ba sic ta sk of the Enha nce d  DV mo dule is to mai n tain pro a ctiv ely a route toward   any other WMR pre s e n t in the backbo ne sub net wo rk. Thi s  Enh anced DV m odule is a n  IPv6   impleme n tation of DSDV , based  on  existing  IPv4 code. Som e  enha ncem ents have  b een  introdu ce d in order to co o perate  with the Client Ma nage r modul e. This modu le is the only one  that accesse s  the kernel ro uting table.   The  NDP-P roxy module  provide s  the  WM R with t heability to a c t like  a Nei ghbo r  Discove r y Protocol  proxy.This  allo ws t o  tran sp are n tly forwa r d  p a ckets towa rd the  WM R  the   destin a tion cli ent is associ a t ed with. In  this  way, no particula r mech anism s are nece s sary on the   client side, in order to communi cate with remo te cli ents. The NDP-proxy module will correctly  answe r to the ICMPv6 requ est se nt by the local  client s.  The IPv6 Forwarde r modul e enca p sulates all  IPv6 pa ckets in anot her IPv6 packet, in   orde r to ship  packets toward the de stination c lie nt.  This solution,  though intro duci ng a ce rtain   amount of overhe ad, avoid s  kee p ing sta t e in t he WMRs alo ng the path bet we en  clients. Inde ed,  only the WMRs at the edges of the path must be  aware that the two client s are communi ca ting.  Another sig n i fi cant advantage is the robustn ess to  mobilit y. If a  client chang es the WMR to  whi c h it is asso ciated, onl y the  WMRs at the  edges of the path must updat e the information  (3   WM Rs in tot a l). WM Rs  al ong the path  do not nee d  to make an y update, wh ile contin uing  to   relay pa ckets.  The Cli ent M anag er m odu le is respon si ble  for di scov ering  whi c h  client is a s so ciated  to which WMR in an  on -dem and fa shion. Wh en  a local  client  wish es to  communi cate  to a   remote  clie nt (a ssoci a ted  to anothe r  WMR), it  sen d s  a m u ltica s t  req u e s t in o r de r to di sco v er   whe r e the  cli ent is. Th e result of thi s   query i s   st ored in the  Foreign  Client T able. The  Cli ent  Manag er mo dule also ma nage s the reply to  reque st s sent by other WM Rs. Fu rtherm o re, since  Mesh DV mu st be a w a r e  of the clie nts that are  a ssociate d  to th e WM R, the  Client Ma nag er  module m onit o rs the  set of client s asso ci ated to wl anI  and sto r e s  them in the Local Client Tabl e.    3.2. Summary   of Ev o l utionar y  Game T h eor y      yy   Non - coop erative gam e  theory is the deci s io n-m a kin g  in a distribute d  envi r onm ent,  the analysi s  of individual utility maximi zation Playe r  for the optimal policy ch oice. Evolutio nary  game, no n-coope rative g a me, a bran ch of a g a m e strategy  for furthe r a nalysi s  of g a me   popul ations i n  a lon g -te r m  stability. Evolution of  the  Na sh e quilib rium (all Pl ayer of the  opti m al   strategy ) with groups  of st ability, which is executed  when  the other Player  bal anced strategy,  any Player can not be balanced by a u n ilateral de pa rture from the strategy  for more effec t ive;  Mean while, the implem en tation of a balan ced  strat egy can  reve al the individ ual pro p o r tio n  of  total populati on.  As the n o vel  achi evement  in the resea r ch   field of n on-coo p e r ative gam e theo ry [9,  10, 11, 20],  the rese arch  on evolutionary game t heory attract s  great attentions in not only  aca demy but  also in du stry field. Integration  of ev olutiona ry ga me theo ry, eco nomi cs  a n d   evolutiona ry biology of rati onal thought,  no longer h u man mod e l into the game supe r-ratio nal  side, that the human is usually achieve d  th rough tria l and erro r method of game balance, and  biologi cal evolution  i s  co mmon,  the choice  Th e  ba lance is the  balan cing  pro c e ss to  a c hie v e a  balan ce d function, and th us the histo r i c al, inst itutio nal factors a nd the balan cing p r o c e s s are   some of the details of the game will a ffect the choice of multiple equilibria.   Set the evolution game lo cated in an N-node  MA NET ,  any node wi th M, that except  the node i ot her than the  colle ction.  i N - denotes the d a ta packet s  ge nerate d  by source no de i  whi c h is  calle d i's group. Data betwe en  sou r ce  and d e stinatio n no des transmit a compl e te d a ta  servi c e is cal l ed a sessio n; the node mobility w ill l ead to chan ges in netwo rk topolo g y, the  compl e tion of  a sessio n re quire s multipl e   routing p a th s to create dif f erent group s.  The othe r p a ram e ter M  trust set up  in all the  main co mpo nents of the  set of  strategi es for the real number field o n  an in terval  X, strategy  by the probability densi t y  distrib u tion f (x) to ch ara c te rize  and  de si gn the fitne s s function (, ) ux l   is a  contin uou s fu nction i n   domain  X ´L , which is the envi r onm ental pa ramete rs,  a s  Environme n t, the probabili ty density.  Evaluation Warning : The document was created with Spire.PDF for Python.
             ISSN: 2302-4 046   TELKOM NIKA  Vol. 11, No . 3, March 20 13 : 1652 – 1 664   1656 Note the pro bability densi t y  function of the com posi t ion of all  th e set. The evolution of th e  netwo rk  confi guratio n soft ware, game  evolutiona ry  sele ction i s  linke d with fitness. Whe n  gi ven   the definition  of the condi tions of envir onmental p a rameters sele ction op erato r   : X X TD D l ®   and the ave r age  sele ctio n operator  : XX TD D l ® , the environ ment, the average fitne s s   function.   Acco rdi ng to the statements listed ab ov e. The evolution game  for WNN can be  defined. So t hat G =  (I, P, U).  Whe r e: I = { N i, N-i }  for  the Player  col l ection,  Ni sai d  nod e i, and  Ni  indicates that  the netwo rk  node s in ad di tion to a ll the node s outsi d e  i; P is the strategy set P =   {pi, p-i}, 1 p a c ket tran smission, refused  to transmi t a messag e to 0 .  U is the utili ty function, the   utility  function with Ui (si,  s- i) to represent. It proceeds B (si,  s-i)> 0 from the i (the correct  transmissio n) and cost s C (si, s- i) <0 (energy con s umption )  of two part s . No de i can be the  watchdo g or  other mo nitori ng and fee d b a ck mechani sms, that messag e tran smi ssi on to the n e xt  node if there  are Byzanti ne errors . Whether the b enefits or  co st s i have a  strategy with  all  relevant pa rticipa n ts, this is a strategy g a me  or actio n  nodes are the embodim e n t  of interactio n,  about the Byzantin e fault-tolera nt  WMN classic pri s o ner' s  dilemm a problem s a nd to link the  two  adja c ent Betwee n nod es  Ni and  Nj pri s oner's dil e m m a sho w n in  Table1.       Table 1. The  game Matrix  betwe en lab o r node s in WNN   successfu l   failur e   The packet reac hs node Nj  ( B ,C )   ( 0 , C )   The packet not r eachs node Nj  ( B, 0)   ( 0, 0 )       3.3. Summary   of Ev o l utionar y  Game T h eor y   Assu ming th e  initial time in the game, th e us e of tech nical  coo p e r a t ion in su pply - sid e   strategy  of p opulatio n rati o of p( 01 p ££ ). The  pro portio n  o f  non-co ope rative strate gi es u s in g   (1-p).Te ch nol ogy used i n  co ope rati on de man d -side  strateg y  of popul ation ratio  of  q( 01 q ££ ).The prop ortion of non -co ope rative strategi es u s i ng 1-q. The t e ch nical coo peratio n   strategy for the sele ction  of  side popul ation expecte d to pay  for can be expre s sed with eq u a tion  1.    1 1 11 11 11 1 [( 1 ) ] ( 1 ) ( ) uq a v c q a v c av q a v c p p =+ - + - -          =   + -  (1)     Tech nolo g y sup p liers ex pect to pay  for the average p opul ation, whi c h can be   descri bed with  equatio n2.     11 12 11 1 1 11 1 (1 ) () ( 1 ) q Up u p u p av q a v c p a v av q p c p av p p =+ - = +- + - = -+  (2)     Similarly you can cal c ula t e the demand-side tech nology coo p e ration with  non- coo perative populatio n exp e cted to pay 21 u ,  22 u , and the average expe cted  payoff .    21 2 1 2 22 2 [( 1 ) ] ( 1 ) ( ) u p av c p av c av p a v c p p =+ - + - - =                 + -                                                        (3)     22 2 2 2 (1 ) up a v p a v a v =+ - =  (4)     Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     A Novel  QoS Routin g Algorithm  in Wirele ss M e sh Net w orks (Li u  Hu i)  1657 21 1 1 2 11 1 1 22 2 (1 ) () ( 1 ) Uq u q u q a v q av c q av av p q c q a v p p =+ - = +- + - =         - +  (5)     Therefore, the network eq uation s  for the  dynamic re plicatio n can be descri bed  with  equatio n (6 ).    11 1 1 1 1 11 1 11 21 2 2 2 22 2 2 22 () ( ) ( 1 )( ), () ( ) (1 ) ( ) dp pu U p tv q a v c dt tv q p c p a v pp a v q c dq qu U q t v p a v dt ct v p q c q a v qp a v p c p p p p p p ì ï ï =- = + - - ï ï ï ï             + - = ï ï ï ï            - - ï ï í ï ï =- = + - ï ï ï ï ï               - + - = ï ï ï               - - ï ï î  (6)     Equation (6) descri bed  the grou p  dynamic,  to solve thi s  euq ation s . Set  0 dp dt = , 0 dq dt = ,five  steady points can be rea c he d, whi c h ca n be listed as follows.  1 (0 , 0 ) E = ,  2 (0 , 1 ) E = ,  3 (1 , 0 ) E = ,  4 (1 , 1 ) E = ,  21 5 21 (, ) cc E av a v pp = .  With  0, 1 pq ££ , when  2 2 1 c av p > a nd  1 1 1 c av p > ,  5 E   does n o t exist. The Jaco bi Matrix  can   be ca cul a ted  accordingly.     11 1 22 2 (1 2 ) ( ) (1 ) (1 ) ( 1 2 ) ( ) pa v q c p p a v J qq a v q a v p c pp pp é ù -- - ê ú = ê ú -- - ê ú ë û  (7)     Whe n   de t 0 J ¹ , The matrix is non sing ular, the r e is a uniq ue  solutio n .  (1) In ste a d y  point  1 (0 , 0 ) E = ,  1 2 0 0 c J c éù - êú = êú - êú ëû , 12 de t 0 , 0 Jc c t r J => < ,  and the poi nt  1 (0 , 0 ) E =  is proven at  steady state.   (2)  In th e st eady point  2 (0 , 1 ) E = , 11 2 0 0 av c J c p éù - êú = êú êú ëû , 12 de t 0 , 0 Jc c t r J => < , and the p o in t  2 (0 , 1 ) E =  is proven at  steady state.   (3) In the  steady poi n t 3 (1 , 0 ) E = , 1 22 0 0 c J av c p é ù ê ú = ê ú - ê ú ë û ,  12 2 de t ( ) J ca v c p =- , when   2 2 01 c av p << , 3 (1 , 0 ) E =   is not the steady point  of the system,  whe n   2 2 1 c av p > , 3 (1 , 0 ) E = is the steady   point of syste m .  (4) In th e p o i nt  4 (1 , 1 ) E = ,  11 22 0 0 ca v J ca v p p é ù - ê ú = ê ú - ê ú ë û , simila rl y, when  2 2 0 c av p > and   1 1 1 c av p < , 4 (1 , 1 ) E = is the stead y point of  the system.  when  2 2 1 c av p > and  1 1 1 c av p >  then   4 (1 , 1 ) E =  is   not the stead y state of the  system.    (5) fo r the  21 5 21 (, ) cc E av a v pp = , o n ly when  2 2 0 c av p > and   1 1 1 c av p < ,  5 E can  be con s ide r ed th e  steady poi nt.  Evaluation Warning : The document was created with Spire.PDF for Python.
             ISSN: 2302-4 046   TELKOM NIKA  Vol. 11, No . 3, March 20 13 : 1652 – 1 664   1658 Evolutionary stable strategy (ESS) is a   descr i p tion of the evolution of  the game i n  the  evolution of the con c e p t of steady  state, dynamic system to de scri be the local stability analysis  of the above balan ce.   (1) When  1 1 1 c av p > and   2 2 1 c av p > , this system has four ste ady points  1 234 ,, , E EE E . W h er e  1 E   is stabl e no d e , (coope rate , coop erate )   a syste m  of  evolutiona rily st able  strate gy, the other  three eq uilibri um points a r e unstabl e. At this  point,  military and civilian technol ogy, supply-side  and de mand -side p opul ations th rou gh l ong-te rm ev o l ution of the popul ation wi ll stabilize in  the  (non -coo pera t ion, non-coo perative )  stra t egy, which do es not form a  netwo rk.   (2)Wh en  1 1 0 c av p > and  2 2 1 c av p < , this system has four ste ady points  12 3 4 ,, , E EE E . W h er e  E1 and E4  for the stabl e node, (co operate, co o perate )  an d  (co,  co) i s  the system  of  evolutiona rily stable  strate gy, E2 and E 3  for the   un st able n ode, E 5  for the  sad d le poi nt. At this   point, network techn o logy,  network syst ems and  de mand -si de su pply-si de pop ulation s  throu gh  long-te rm ev olution of the  populatio n to E5 acco rdi ng to the initial value for the sa ddle p o i nt  were stable  at different (non-co ope rati on, non-c o o peratio n) an d (co ope rati on, coop eration)  strategy.   Tech nolo g y  sup p ly-si de  and d e man d - sid e   spe c ie s po pulatio n s  un de r different  techn o logie s   to get their investment  co st and te chn o logy ben efits of te ch nolo g y, the ratio of  benefit-co s t ratio can b e  descri bed a s  technol ogy,w hi ch is u n d e r certain te chni cal b ene fits  comm uni cat i on co st s.   Figure 3 Describe d in the plane S system  techn o logy for military and civilian   popul ations side an d dem and-sid e  dyn a mics of ga m e  pop ulation s . The sy stem  has five p a rt ial  equilib rium p o int, the two  unsta ble e q u ilibriu m  poin t  E2 and E3  and E5  con necte d into t he  sad d le-point line for the different  states the system  conv e r ge s to the critical line, that line  the   uppe r right (E2, E5, E3, E4 part)  system  converg e n c e  in partnershi p , in  the line  of the lower left  (El, E2, E5,  E3 part) the  system will converge  to the co-operati ve relationshi p. Because the   system' s  evol ution is a long proc ess, probably in a very long time   to maintain a  coo perative and  comp etitive coexisten c e.       2 (0 , 1 ) E   4 (1 , 1 ) E 3 (1 , 0 ) E   1 (0 , 0 ) E   21 5 21 (, ) cc E av a v      Figure 3. The  evolutionary  model for me sh net work g a me       4. Work flo w   of EGW R A   We co nsi d e r  the dynamic nat ure of MANET as a game with N players, and  we call  about coalitio n all non-emp t y party S of  N.  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     A Novel  QoS Routin g Algorithm  in Wirele ss M e sh Net w orks (Li u  Hu i)  1659 4.1. The Co mmunicatin g Step of EG WRA  Traf fi c  fl owi n g in a mesh n e twork  can b e  cla ssi fi ed into three types:    a) traf fi c bet ween two  client s asso ciate d   with the sam e  WM R.  b) traf fi c bet ween two  client s asso ciate d  with different  WM Rs.    c )  traf fi c b e tween a cli ent a nd a gate w ay . All types of traf fi c are deta iled belo w .   Client s asso ciated with the  same  WM R. In this ca se,  client s do n o t need a n y pa rticula r   attention, sin c e the wl anI interf ace aut omatically b r i dge s the traf fi c b e twe en them. This i s  an  embed ded fe ature of the HostAP mode  of wirele ss ca rd drive r s.     4.2. Working  Step of EG WRA  The packa ge  S may be an element or equal to N.  It is assume d given on parts of N, a   function  whi c h com Acco rding to the definition  of evolution gam e  , we can de sign the working   st ep s of  E G WRA  a s  f o llo ws.     /* Step 1 ： Finding Availab l e EGWRA-Neighb or */   TCBT C- N(u )     Φ ； T D (u )  Φ ； p( u)    p0 ； α  =  π /3  while ( p ( u )  <  P and gap - α (TD ( u))  )  begin           bc as t (u, p(u), (Hello, p(u))  )             u rec e ives  Ack  (ack , p(u)) mess age from v  if v’s game score is m o re th an the  thre sh old   u cal c ulate s  the dire ction o f  discove red  neigh bor v dir(u, v),  the tran smitting po wer a n d  the directio n deter mi ne s the neigh bor v(  p(u ) , dir(u, v) )  TCBT C- N(u )  =  TCBT C- N ( u )   ∪  { v | disco vered nei ghb or v }  TCBT C- D(u )  =  TCBT C- D ( u )   ∪ {dir(u, v) | discovered n e ighb or v }  Pow(u) =  Pow(u)  ∪  { p(u, v) | discove re d neigh bor v }   p(u )    Incre a s e(p(u))  end   /* Step 2 ： Finding Availab l e DT-Nei ghb or  */  k is the up per bound of no d e  degree, k = 6    Sort all qualifi ed neig hbo rs  found in Step 1 in orde r of increa sing di stance o r  po wer      Pow = { p 1 , p2, p3, ……, pm } ， p1 ≤  p2 ≤  p3 ≤  ……  ≤ pm       while (payoff value>th re sh old)    begin          for( i= 1; i  ≤ m;  i++ )             begin   u transmits  with power pi, 1 ≤ i ≤ m  dra w  a pe rpe ndicular bi se ctor betwe en u  and the nod e  corre s po ndin g  to the powe r  pi            end    end   T D T- N( u )  =   TD T - N ( u )   ∪∈  { v | v   TCBTC-N(u) a nd v has corre s po n d ing Voronoi  Edge }   T D T- D( u )  =   TD T - N ( u )   ∪∈  { v | v   TCBTC-N(u) a nd v has corre s po n d ing Voronoi  Edge }   /* Step 3 ： Filling the  α -gap   */   Sort TCBTC-N(u )  an d TDT - N(u) in o r d e r of increa sin g  directio n   if gap- α   ( TDT-N(u )  )  then  α    the  smalle r direct ion of the gap   β    the larg e r  dire ction of the gap   if dp, dq, dr  ∈ TCBT C-N(u )  and  dp  ≤  dq  ≤  dr and dp  = α , dr = β  then d q  is dro ppe d in Step  2 and can fill the  α -g ap   TN(u) =  TDT - N(u )   ∪  { v | th e dire ction of v is dq }  TD(u) =  TDT - D(u )   ∪  { dir(u, v) | the directi on of v is dq }   Pow(u) =  Pow(u)  ∪  { p(u, v) | the directi on of v is dq }  /*  Step 4 ： Edge Removal   */  Suppo se no d e  v, w ∈ N(u )   s e nd(u, p(u, v), relation(v, w), v)  recv (u, relatio n (v , w), v )   Evaluation Warning : The document was created with Spire.PDF for Python.
             ISSN: 2302-4 046   TELKOM NIKA  Vol. 11, No . 3, March 20 13 : 1652 – 1 664   1660 if relation (v , w) i s   “Y” a n d  | TN( u ) |  - 1   ≥  3  th en T N (u )  =T N(u )   - {v}   P r o c e dure  ga p- α (T D( u) )     Suppo se T D (u) = { d1,d2,d 3 ,…,dn} Sort  dire ction s  in TD(u) in in cre a sin g  ord e r  TD(u)  =  {dk 1 , d k 2 ,dk 3 ,…,dkn}, dk 1 ≤ dk 2 ≤ dk3 ≤ … ≤ dk n ,  1 ≤ ki ≤ n, 1 ≤ i ≤ n  for( i=1; i  ≤ n;  i++  )    begin     if dki+1  - dki  ≤  2 π /3  then contin ue   end     The aim of the genetic o perato r s is to  generate a secon d  gen eration po pul ation of  solutio n s fro m  those sel e cted thro ugh  geneti c  ope rators: cro s so ver, and/or m u tation. For e a ch   new  sol u tion  to be p r od uced, a pai r of  ”pa r ent” solut i ons i s   sele ct ed for  bre edi ng from  the p ool  sele cted p r ev iously. By produ cing a ”child” solu tion  usin g the ab ove method s of crossove r an d   mutation, a new solution  is create d  whi c h typica ll y share s  ma ny of the chara c teri stics of its  ”pa r ent s”. Ne w parents a r e sele cted fo r each ch il d, and the pro c e ss  contin u e s until a ne w  popul ation of solutio n s of a ppro p ri ate si ze is gen erate d .    4.3. Qos Violation Dete cti on  The route bre a k ca n not be detected e a sily . The co mmon app ro ach u s ed in most of  existing ad h o c ro uting p r otocol s is by  waiting for a  neighb or tim eout, i.e., the  hello messa ge  from a n e igh bor  doe s not  arrive to th e  node  on  tim e . Whe n  nei g hbor tim eout  is di scovere d ,  a   route e r ror m e ssag e is  se nt to the sou r ce notif ying a bout the brea k. Ho weve r this ki nd of ro ute   brea k  detecti on meth od n o rmally ta ke s seve ral  se co nds,  whi c h i s   not de sira ble  to time se nsit ive   QoS flows. In our app roa c h, we utilize  the bandwid th rese rvatio n timeout at the destin a tio n  to   sign al possibl e route brea ks. If the destination fails  to  receive d a ta  packets of a n  active flow 21   before it s reservation timeout, r oute recovery  will be  triggered at  the destination. Usi ng  this  method, we  can dete c t b o th types of QoS vi olations at the same time an d handle the m   identically. The neig hbo r l o st dete c tion  will also  be  use d  in case  the destin a tion that initiated  instant  re cov e ry can n o t reach t he  so u r ce  be ca use  of netwo rk pa rtition or pa cket loss. Whe n  a   node dete c ts  that the down link nod e of a rese rved r o u t e is lost, it will send a ro ute erro r pa cke t ,  with its curre n t route  seq uen ce nu mb er, to the co rre sp ondi ng  uplin k nod e. The route e r ror  packet is then forwa r ded  upward s  to the sou r ce to  indicate the occurren ce of the route bre a k.  As a consequence, the reserved  bandwi dth of the flow will be re leased at the forwardi ng nodes.     4.3. QoS Violation Recov e r y   To provide in stant route a dapt ivity, we  use de stinati on initiated route recovery . After   the QoS violations a r e de tected, the d e stinatio n will  incre a se its route sequ en ce num be r and  broa dcast an unsolicite d  ro ute reply packet, also  call e d  route updat e packet, back to the source.  The route u pdate p a cket  is tre a ted i n  the sa me  manne r a s   a route  re qu est pa cket  with  admissio n  co ntrol an d loo p  preve n tion  mech ani sm,  but in the reverse di re ction  from de stina t ion   to source. Upon re ceivin g the first in time  route update p a cket with appropriate  seq u ence   numbe r, the  sou r ce switches the flo w  in que st ion  to the reverse route o n  which the  upd ate   arriv e s.    On the othe r  hand, a late  route upd ate  packet  o r  a route erro r pa cket, with the  valid   route sequ en ce, sign als th e occurren ce  of QoS  violation and the  failure of route recovery. In  su ch case, the appli c ation  can eith er d e c ide to  contin ue tran smittin g  the flow wit h  the ab sen c e   of QoS guara n tee or  suspe nd the flow a nd try later.      5. Simulation Experimen t  of EGWRA  5.1. The Desi gn of Simulation Experim e nt  We u s e the  simulation software mad e  b y  a  Ns 2.30  pairs rel a y co operation st rategy  to con s truct t he expe rime nt. The topol ogy of ex pe ri ment WNN can be  de scri bed li ke figu re 4,  whi c h divided  into two part s , mesh network a nd un de rlay netwo rk.  The MA C lay e r of   each m obile node  or  AP model uses the default IEEE 802.11 DCF  module  provided by   OPNET with mo di fication s  for  multihop  con nectio n  supp ort. Each  mo bile   node or AP has the same  transmissio n rang e of  200 meters and  raw data rate  of 2Mb/s. Th e   WM R mod u le  is in sert ed o n  top of the M A C layer m o d u le. In the WMR mo dule,  we impl eme n t ed  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     A Novel  QoS Routin g Algorithm  in Wirele ss M e sh Net w orks (Li u  Hu i)  1661 a send er buff e r of 64 packets to buffer data packet s  waiting for a route, e.g., packets for wh ich   route di scove r y  has sta r te d, but no repl y has ar rived  yet. Upon discovery failu re , the source  will  back-off for  a dou ble tim e  interval a n d  try agai n  until the retry limit of 3 is rea c hed. T h e   maximum pa cket size u s e d  in the tempora r y  band wi dth reservati on is set to 1024 Bytes. The   hello interval  of 1 second i s  used with n e ighb or timeo u t set to 3 se con d s.   All the node s are  stationa ry during th e   simu latio n  pe riod of 3 00  seco nd s. The r e are  10 external flows with the sou r ce node s sp re ad ran d o mly among the 40 node s. Since we are   intere sted in the perfo rma n c e of WM R in  a mesh  ne two r k ,  th e   c o nne c t io ns  to  th e w i r e d  ne tw ork   are n o t inclu ded in the  si mulation. Th e traffic  sin k  module in t he AP model  will re ceive  the  external data  packet s  as if they are forwa r ded to the wi red net wo rk.   To simul a te stream me dia  appli c ation s   we  u s e CBR (co n sta n t  bit-rate)  flo w s wi th  10   packet s  per seco nd and fixed data pa cket size of  102 4 bytes. The sou r ces  will keep gen erating   data pa ckets  at the fixed ra te throug hout  the si mul a tio n . All the flows have th e sa me end -to-en d   delay bou nd.           Figure 4.The  topology of e x perime n t network      Simulation is using  ro utin g EGWRA. Collabo ration  d e fined level i ndex nod e fo r the   netwo rk in a n y  of NARMea ning the a c tu al relay nod e s  and the n u m ber of pa ckets followi ng  th e   packet in  whi c h the  numb e r of  requi re dVolume  rati o. NAR  ∈  [0, 1 ], the great er the valu e  of a   node' s  NAR.  HelpT he  high er the  deg re e  of coll abo rati on involved i n  rel a y.Simulation sce n a r i o  is  set as follows. number of node s N for a  50, each sect ion Point spe ed in the 10  ~ 20m/ s were  evenly distrib u ted within the mobile ra nge Wai as a  500m × 50 0m, each no de in a session  immediately after the end ofInitiate another sess ion  carved, and th e duration of each se ssi on  5- 10swere  unif o rmly di stributed withi n . These  setti ngs will ensure  th at each node in t h e   netwo rkInte ra ction b e twe e n  the hig her t he proba bilit y of the relay.  Each  se ssi on  is a fixed-sp eed  transmissio n R ate of 1 Mb / s data stream, pa ck e t  size is 5 1 2by t e .  E a ch  simulat i on t r ue  contin uou s 9 00s, 50 time s in the implement ation of the statisti cal  averag e dem and.     5.2. Result  Analy s is of Simulation   Accrodi ng to  the pa ramete r we sta r t the   experim ent and  the sim u l a tion  re sult can  be  descri bed li ke figure  4. At fixed interva l s of  time, t = 1-75, move ment occu rs  by updating t h e   spe ed an d d i rectio n of each M N .We have ch oo se  the tuning para m eter u s ed to vary  the  rand omn e ss.  the speed a nd dire ction  are cho s en from a ran d o m  Gaussia n  distrib u tion with   mean eq ual to zero and  standa rd deviat i on equal to  o ne. For a ra n dom ch osen i n stant t in total  simulatio n  time, our pro p o se d approa ch extra c t 21 MNs as a st able co re in term s of mobility  whi c h is ma rked with a re a d  dot.  Evaluation Warning : The document was created with Spire.PDF for Python.