TELKOM NIKA , Vol.13, No .1, March 2 0 1 5 , pp. 202~2 1 0   ISSN: 1693-6 930,  accredited  A  by DIKTI, De cree No: 58/DIK T I/Kep/2013   DOI :  10.12928/TELKOMNIKA.v13i1.790        202     Re cei v ed O c t ober 1 5 , 201 4; Revi se d Ja nuary 13, 20 1 5 ; Acce pted Janua ry 2 8 , 20 15   Modified Greedy Physical Link Scheduling Algorithm  for Improving Wireless Mesh Network Performance      Nach w a n Mu fti Adria n s y ah*, Muhama d Asv i al, Bagio Budiardj o   Electrical E ngi neer ing D e p a rtment, Univers i tas Indon esi a   Kampus Bar u  UI Depok 1 6 4 2 4 , Indon esia   *Corres p o ndi n g  author, e-ma i l : nach w a n .muf ti@ui.ac.i d       A b st r a ct   T he alg o rith m  to alloc a te  me sh active l i nk t o  radi o reso ur ce timeslot i n   w i reless  mesh  netw o rk  (W MN) is inve stigated. T h is  pap er pr o pose s  the nove l  me thod to al locat e  multip le li nks  in on e timeslo t  for  improvi ng the  w i reless mes h  netw o rk throug hp ut vi a spatia l time div i sion  mu ltip le  access (ST D MA)   protoco l . T h e  throu ghp ut i m p r ove m e n t is  o b tain ed  by   mo difyin g gr ee dy  bas ed  al gorit hm that  is w i d e ly   know n as  a  l o w  complex i ty a l gorit hm.  W e   p r opos e  and  i n v e stigate  n e w  p a ra meters  in  t he  gre edy  bas ed  alg o rith m th at can b e  us ed  a s  sched uli ng c ontrol  par am et ers, i.e. interfe r ence  w e i ght, sched uli ng  w e i ght,   and th e su m  of link ’ s  degr e e . Simulati on  results in dic a te that this ap proxi m ati on i n creases n e tw ork   perfor m a n ce i n  throug hput a n d  len g th of sch edu lin g per f o rma n ce cl ose d   to the up per b oun d perfor m a n ce   that is achiev e d  by the al gorit hm th at  uses the phys i cal i n terferenc e mod e l.        Ke y w ords : W M N, ST DMA, g r eedy a l gor ith m , link sch ed ul ing       1. Introduc tion  The me sh o r  multi-hop to pology cure n t ly is  seen a s  a strong  candid a te top o logy to   improve  wire less net work cap ability and ha s  a n u m ber  of advantage s an d  use d  for m any  appli c ation s  [ 1 ]–[3].   R e ce ntly, w i r e les s   me s h  n e t w o rk  ha s   e m er ge d  as  an  in ter e s t ing   r e se ar c h   area  an d  gai ning  attention  from  re se archer to imp r ov e this tipical  n e twork in  different  a s pe cts [1]  [4][5].   Specifically to improve r adio resource efficiency utilization  in the multi-hop wireless mesh  netwo rk  (WM N ), Nelson a nd Kleinrock  [6] introdu ce  the spatial ti me division  multiple acce ss  (STDMA ). Th e STDMA p r o t ocol a c cess  enabl es to all o cate m u ltipl e  links o r  nod e tran smi ssio n s  in one  time sl ot as long  a s  those  con c u rre nt  tran smi ssi on s do  no t degrade  si g nal qu ality. The  mesh lin k scheduli ng prob lem is prove d  as NP har d probl em [7] and there a r e  many algo rithms  develop ed in STDMA proto c ol acce ss [7]–[11]. T he crucial obj ectiv e  of the mesh  link sched uli ng  optimizatio n probl em is to  maximize the  numbe r of  links t hat  is all o cat ed in t i me slot  re sou r ce s.    Gupta a nd  Kumar [1 2] introdu ce t w o  interferen ce  model s for the link  scheduli n g   cap a city eval uation, i.e. p r otoc ol an d  physi cal inte rferen ce m o d e l. Due to it s sim p licity, the   proto c ol  inte rfere n ce m o del i s   widel y use d  by  rese arche r s t o  devel op t he ST DMA  link  sched uling  al gorithm s [1 3]–[15]. On  the  otherh and,   th e alg o rithm s  t hat a r e  devel oped  in  physi cal   interferen ce  model i s  pro v en to  have better  pe rf orma nce tha n  the other  algorith m s  wi th   comparable  developed i n  protocol  i n terference  model [16],[ 17], but always in  higher  comp utationa l co mplexity. For thi s   re ason, we n eed  to de sig n  m e sh lin k  sched ul ing al gorith m   in   physi cal interf eren ce m odel  with low com put ational  co mplexity and a good p e rfo r mance.   Gree dy ba se d algo rithm i s  kno w n to  have  a lo w  compl e xity algorithm fo r reso urce   allocation. Brar et al int r od uce  gre edy p h ysical  algo ri thm [18] as  STDMA alg o rithm in physi cal   interference  model [19],[20]. T he best performance  of physi cal S T DMA lin k scheduli ng given by  Gore  et  al [1 0], namely  si gnal to  inte rfe r en ce  ratio  g r aph li nk sch e dule  (SGLS )   algorith m . S G LS  algorith m  p r o v ide the  be st  perfo rman ce   of me sh li nk  sched uling  by  iterativ ely  ch eck SINR fo r  all  links that  sch edule d  in  the  same  time slo t, so th at  this  algorith m  h a ve hig h e s t net work thro ugh put     kno w n  so far.  The time co mputational  complexity of  SGLS algorit hm is re porte d  .   In this pa per,  we p r op ose  a ne w ap pro a ch i n  the g r eedy ba se d  STDMA lin k  sched uling  algorith m  tha t  can be u s e d  to improve  mesh n e two r k perfo rma n ce. The impro v ement of mesh   netwo rk th ro ughp ut is a c hieve d  by i n trodu ci n g  n e w  sched uli ng pa ram e te rs th at ca n  be   controlled. Th e target of propo sed alg o ri thm is  highe r network thro ughp ut than gree dy physi cal   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Modified Greedy  Phy s i c a l  Link   Scheduling Algorithm  for Improv ing  ....  (Nac hwan Mufti A.)   203 algorith m  [18 ]  and  clo s ed  to to the  be st re sult  th at is give n by  physi cal inte rferen ce  ba se d   sched uling p e rform a n c e [21].   The p r o b lem  formulatio n of  STDMA li nk  sched uling  is  descri bed  a s   follows. The  i nput of  link sched ulin g algorithm is a communication grap h  , , i.e. the  mesh topolo g y that  con s i s ts  of all the n o d e s a nd th e a c tive co mmu nicatio n  lin ks with  signal  to noi se  ratio  (SNR)  above  the   minimum threshold,  . The set of nodes is rep r e s en ted by   , ,…,  and the set of  active comm unication links is represen ted by   , ,…, . The  link sched ulin g algorithm s  intend to  allocate th e dif f erent me sh  active  com m unication li nks  , that is geog ra phica lly   sep a rate d, to  the  certai n ti meslot.  S o  t hat the  si gn al   to  interfe r e n ce and   noi se ratio (SINR) o f   all  links in thi s  ti meslot  sh oul d sati sfy the  minimum th re shol d  . If link     is all o cated i n  the  same  times l ot with  link    , this  con d ition mu st always  satisfy of ph ysical i n terfe r en ce m odel  requi rem ent [12],        ij ij c o kV kj ki P d SI NR P N d  (1)     The o u tput o f  the mesh li nk  sched ulin g algo rithm i s  the m e sh l i nk  sched ule   . , , ,…, , where   is the numbe r of time slots to complete the schedul ing task. In  wirel e ss me sh netwo rk lin k sche duling  optimizatio n probl em, we  have an obje c tive function  to  maximize  net work th rou g h put (2 ). The  constraint s are :  all links a r e  sched uled  at least o ne al o ng  the length  of sched uling  (3 ), ea ch n ode  can not tr an smit and recei v e in one tim e  slot  (4), a  n ode   can  tran smit/ r eceive o n ly to/from on e  other  nod e  in  one tim e  sl o t  (5-6), a nd a ll tran smissio n s  must satisfy physical interfe r en ce mo del requireme nt (7).   The inte ge r li near p r og ram m ing  (ILP)  re pre s entatio n of  STDMA  li n k  sched uling  probl em  as  follows :   Objective:      max  (2)     Con s trai nts:     ∑   1    ∀  ∈  (3)       ∑   ∈ ∑   ∈ 1   ∈ , ∈  (4)       ∑  ∈ 1   ∀ ∈ ,∀    (5)       ∑  ∈ 1    ∀ ∈ ,∀  (6)         ∑   ∈ ∖    ∀  ∈ , ∀  (7)     This pa pe r is org ani zed  as follows. In se ction 1, we provid e  related works in the   research area and probl em form ulation. In se ction 2 and  3, we illust rate the proposed l i nk  sched uling al gorithm d e scription an d then followe d  by resea r ch  method. Fin a lly, simulation  results an d di scussio n , and  con c lu sion a r e  presented i n  se ction 4 a nd 5 re spe c ti vely.        Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 16 93-6 930   TELKOM NIKA   Vol. 13, No. 1, March 2 015 :  202 – 2 1 0   204 2. The Propo sed Algori t h m    The b a si c of t he g r ee dy ph ysical  algo rith m for ST DM A proto c ol  acce ss  (GP - ST DMA) i s   introdu ce d b y  Brar et al [18]. The princi ple  of this algo rithm is to perfo rm sch eduli n g by  interferen ce  evaluation  fo r ea ch  lin k. To  analyze  interfe r en ce , the GP-ST D MA al gorit hm   transfo rm s the commu nica tion grap h into a conflict g r aph. The lin k with the largest num ber  of  interference will  be scheduled  firs t  after link’s interfer ence sorting. The lin k’s interference i n   comm uni cati on gra ph is  repre s e n ted b y  degree  of  node in the co nflict gra ph. Gree dy algo ri thm  is  kno w n to  p r ovide l o w co mputational  complexity , bu t not provide  optimal p e rfo r man c e.  On t he  otherh and, G o re et al [10]  introdu ce S G LS-ST D MA  algorithm th at is provid e the near  opti m al  perfo rman ce  but high er in  compl e xity. In this p ape r, we  sho u ld a c hieve  netwo rk p e rfo r ma n c e   near to the p e rform a n c e a c hieve d  by  [10]  but with lowe r algo rith m compl e xity.   In this sectio n, the improved  greedy p h y sical  sp atial time division  multiple a c cess  i s   prop osed. In contrast with  the  basi c  gre edy physi cal algorith m  in  [18], the prop ose d  algo rith m    do not pe rform the grap h tran sform a tion . The c onfli ct free sch eduli ng is gu ara n t eed an d de ci ded  based on three interfe r en ce pa ramet e rs: the block  p a rtition evalu a tion, the su m of link’s de gree   evaluation, a nd the sched uling wei ght evaluation. After that, the  physi cal interference model is  use d  to guara n tee SINR re quire ment.   From  th e co mmuni cation grap h  , , the set of active  comm uni cati on lin ks   are   evaluated  so  that the can d idate of  lin ks that ca n be  allocate d in  one time slot can b e  defin ed.  The area of the me sh net work i s  divide d to some  bl o c ks pa rtition, whe r e thi s  pa rtition method  is  use d  p r eviou s ly in [22][23 ]. The num b e r of bl ock t hat is  use d  i n  this  pape r  is  10 10 100   partition blo c ks. Norm atively, the link    can b e  allo cated in the same timesl ot with link    if  satisfy re quirements a s  fol l ows (Fig.1 ):  -  Nod e     in different blo c k p a rtition with its interfe r en ce  node s (no de  , and node  )   -  Nod e     in different bl ck p a rtition with its interferen ce n ode s (no de   and nod e  )       i v j v ij e kl e k v l v     Figure 1. Mesh active link i n  four blo ck p a rtition       For inte rfere n ce q uantificati on, the su m of link’s d egre e      and  the interfere n ce   weig ht      are  defined. T h e  sum  of link’ s de gre e  of  link    is defin ed a s        whe r e   is d egree of n ode  . The lin ks with  highe r    mea n s that th ose  links on  den se network  topology in th e evaluated  a r ea b e cau s e t h is lin k is  c o n necte d with  many of the li nks. So that, the   links with hig her    is given prio rity sch ed uling firstly in a gree dy way .     The oth e r qu antification  of  interfe r en ce  is rep r e s ente d  by the i n terferen ce  wei g ht that is  derived from the distance of two links. For link    dan link   , the inte rfere n ce weig ht     is   defined a s :          m a x   ,      (8)     So that, the sche duling  wei ght can b e  de fined as follo ws,       ′   1      (9)   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Modified Greedy  Phy s i c a l  Link   Scheduling Algorithm  for Improv ing  ....  (Nac hwan Mufti A.)   205 The sch eduli ng wei ght  ′   , is used a s  th e interferen ce paramete r  whe r e hig h e r   ′    means lon g e r dista n ce  of two links,  so that the link with high  ′    have a  high   prob ability to  sched ule. To  give high  lin k sch edul i ng  efficien cy, scheduli ng  start s  from  lin k wi th  minimum scheduling weight to maximum value.   The final  eval uation i s  to  g uara n tee SI NR of lin ks that  are  allo cate d  in pa rticular timeslot  sho u ld b e   satisfying mini mum thresh old of SINR. Con s id er to  node  re ceiv er   for SINR  guarantee  with physi cal int e rferen ce mo del, E quation  10 ca n be de rived from Equation 7.            (10 )     whe r e th e total interfe r e n ce  expe rien ced i n  n ode    so urced  from a n u mb er  of  node    r e pr es e n t ed  a s    as  follows,        ∑      (11 )     So that, with sub s titute (1 0) to (11 )  ca n be found t he req u ireme n t of link allo cation to satisfy  physi cal interf eren ce  con s train in Equatio n 7, as follows:      ∑        (12 )                         The pseud ocode of the propo sed  al gori t hm is de scri bed bel ow,     Proposed Algorit hm:   Input:    , → , ,…, ,   Output:    Transmission schedule    , ,… ,   Steps of algorith m :    1. Sort  , ,…,  in decreasing orde r based o n  interference d e g ree      2.  Candidate links generation  w i th bl ock partition criteria evaluation  3. Initializat ion:   ;        4.  ∅   5.  Select one link from    , i.e.    ; allocate    in    ;  ←    6. Sort    in increasin g order  ′    7.  Select one candi date e.g.     to be  e v aluated  w i th the  Ph y s ical Interfe r ence Model.   If     , allocate     to   , then    ⋃     8.  Return to  follow i ng candidates, re peat step 7 to 8  until all candidat es for    are evalu a ted    9.   , repeat step 5 t o  9  w here       until lin k scheduling co mpleted  10.  Compute link scheduling perform a n ce        The a s ympt otic time  co mplexity ana lysis i s  u s e d  to an alyze the  comp utational   compl e xity param eter in the ce rtain time con s tr aint . In the propose d  algo rith m, computati onal  compl e xity can be analy z e d  from ea ch p r ocess in the  algorith m .  The set of active links   is sorted ba se d on the su m of the link’s deg ree re q u ire s   Oe log e   operation s . The so rting result is defin ed as     as the input of th e sch edulin g  algorith m . For each link el ement    in    ,  block partition  evaluation is  perfo rmed in  orde r to   gene rate ca n d idate links that can be allocate d con c urrently with  link   . The block partition  evaluation  requi re s    e  operatio ns. T he cal c ulatio n of sche dul ing weig ht take s   e   operation s . So that, the in put of link  scheduli ng ge n e ration  re quires  el o g e e e  e   operation s .   In the alg o rit h m, the first step i s  to  sel e ct a li nk i n      with a l a rg e sum of the li n k ’s  degree to all o cate to the  first time sl ot and  re ad  its can d idate  links. Thi s   pro c e ss  req u i res   | | . Furthermore, sortin g the  can d idate li nks  an d sel e ct one lin k  with highe st sche duling   Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 16 93-6 930   TELKOM NIKA   Vol. 13, No. 1, March 2 015 :  202 – 2 1 0   206 weig ht to be   SINR evaluat ed requi re s   | e | log | e |  time, where  | e | | e |  a nd in the worst case  | e | e .   The phy sical  interfere n ce  evaluation for  m  candidat e links req u ire com p lexity   m   whe r e  m  is the numbe r of links that is a llocated to  the same timeslot and  m | e | . This   pro c e ss i s   re peated  until a ll links have b een  compl e te ly assi gned.  So that, the complexity of this  p r oc es s  is    . .   The time  co mplexity in o ne cy cle al go rithm is  | |  | | log | |  . , w h er e  | | ~ . This process repeated for all links in   .  So that,  the  total time c o mplexity is     log  . F u rthe rmo r e, i n  the  wo rst  case  of the to t a l computatio nal  compl e xity is ap proximated  to  e ee l o g em ≅ e log e ≅ Oe .      3. Rese arch  Metho d   The m odel  of link  sche duli ng p r o c e s s d epicte d  in  Fig u re  2. The  pu rpo s e li nk scheduli n g   in the wirel e ss me sh net works i s  to maximize the  nu mber of lin ks  that are allo cated in a time slot  as a ra dio resource.           Figure 2. Mesh link sch edul ing simul a tion  modeling       In this p ape r, the wi rele ss  mesh  net work  pe rforman c e mea s u r ed i n  length  of scheduli n g   and network throug hput.T he  le ngth of sched uling   is  define d  a s   multiplicatio n  of the  num b e r of  timeslot that is req u ired to compl e te sch edulin g ( ), with the timeslot  duration  ( ), as  follows :          (13 )     If   is the number of links that sch e dule  concurrently in timeslot  , the n  link sche dul e in  times l ot   represe n ted by   , ,…, .  Link sch edul e repeat s pe riodi cally with  the fixe d   pattern  alo n g  the  network ope ratio n , so that  a p a ir of transmitter-rec e iver that trans m its  in  times l ot   will communi cate  again in time slot   ,  2 …  and so o n .   Usi ng the Sh anno n’s form ula [24], the achi evable d a ta rate for link  ∈ , i.e.   ha s  the uppe r bo und value a s :      l o g 1   (bps)  (14 )     Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Modified Greedy  Phy s i c a l  Link   Scheduling Algorithm  for Improv ing  ....  (Nac hwan Mufti A.)   207 So that, the amount of bit s  tran sfe rre d  in one time sl ot is   , where    is timesl ot  duratio n and    is the bandwidth allo ca tion for wirel e ss mesh ne twork. Such that, average  throug hput fo r all tran smission lin ks as f o llows:        ∑  ∑ ∑∑ ,     (bps)  (15 )     whe r e   is the numbe r of active comm u n icatio n links  and   ,  is the upper b oun d o f  data rate   times l ot-  and   is the numbe r of links tran smi tted concurrently in timeslot- .  The me sh  lin k  scheduli ng  perfo rman ce   is obt ai ned  b y  Monte-Ca rl o sim u lation  method.  The statio na ry node po siti ons  are  ran d o mly gene rat ed in a  squ a re are a  for e a ch iteration a n d   then the process to evalu a te t he cu rre nt mesh top o l ogy is sta r te d. For ea ch t opolo g y in one  iteration, all  of active lin ks a r e  sched uled  b a sed  on the al go rithm whi c h i s  evaluated.  The   simulatio n  was  repe ated i n  100 0 iterations  with  the  different p o si tions of n ode s an d differe nt   netwo rk top o l ogie s .       4. Results a nd Discu ssi on  For comp ari s on, the basi c   TDMA an d some al go rith ms that are  p r eviou s ly pro posed for  STDMA prot ocol a c ce ss  are u s ed a s   the perfo rma n ce referen c e. The arb o ri cal lin k sche dule  (ALS-ST D MA ) algo rithm is base d  on p r otocol  inte rfe r en ce mo del  and propo sed in [13]. The   gree dy phy si cal  (GP-ST DMA) alg o rith m  is  ba sed  o n  physi cal  int e rferen ce m o del an d p r op ose d   in [18]. The SINR graph l i nk sch edule  (SGLS- ST DMA) algo rithm is based on pure phy sical  interferen ce  model an d propo sed in [10 ].    From p r evio us work, the evaluation  of link sch edulin g algo rithm with si mulation   para m eter  se tting in Table  1 gen erally  starts  from 30  node s, be ca u s e the  com m unication g r a p h    ,   not formed  completely in the num ber of  node s belo w  than 30 no d e s. Gen e ral simulation   para m eter  se tting is sho w n  in Table 1.      Table 1. Simulation pa ram e ters  setting   Parameters  S y mbol V alue Band w i dth   W  10 MHz  Frame d u ration     T f   10 ms  OFDM  s y mbol d u ration    T s   25 µs  Transmission pow e r     P  10 mW  Path loss expone nt  β   4  Noise po w e r    N 0   -90 dBm   Communication threshold    c   20 dB  Interfer ence thre shold  i   10 dB  Ar ea cover e d  R  x  R   886 x 8 86 m 2       The sim u lati on re sults  sh ow that the SG LS-ST D M A  algorithm  has b e tter th roug hput  than the oth e r  algo rithm s  that are  sim u lated (Fi gur e  3). Thi s  is  du e to this alg o r ithm iterative l y  che c ks SINR and efficient ly utilize the interferen ce  margi n  for in cre a si ng the  mesh net wo rk   cap a city. Th e rang e of  the SG LS-ST D MA th ro u g h put  value s   a r e between  9.504 Mbp s  (30   node s) to  0.961 Mb ps  (1 10 no de s). T hat is a n  up per b oun d capa city of throug hput in t h e   physi cal int e rf eren ce  mo del .  Fro m  Fig.  3 ,  also  can  be  see n  the  wi re less me sh  ne twork  cap a cit y   decrea s e   in e x ponentially negative cha r acteri stic. Th i s  i s  b e cause  the net work  capa city network  is divided o n  a numbe r of active links in  the network.    The GP-ST D MA algorithm  that also u s i ng t he phy sical interferen ce model i s  proved ha s  better p e rfo r mance in  through put a nd  length  of  sch edulin g than   the ALS-ST DMA that is u s ing  the protocol i n terferen ce  model . F r om   Figure 3  an d  Figure 4  al so  ca n b e   see n  that the ST DMA  algorith m s p r ovides bette r perform an ce  than TDMA  as the ba sic  acce ss p r oto c ol in wirele ss   me s h  ne tw ork .    In the throug hput and le n g th of sched u ling pa ramete r, the pro p o s ed algo rithm  provide s   the perfo rma n ce b e tter th an co nventio nal GP-S T D MA algorithm  and clo s e t o  SGLS-ST D MA  algorith m  pe rforman c e a s   the best  re su lt in this  re se arch area  so  far. The p r op ose d  algo rith m  Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 16 93-6 930   TELKOM NIKA   Vol. 13, No. 1, March 2 015 :  202 – 2 1 0   208 provide s  th ro ughp ut in a n   averag e 7.5 1  % better tha n  GP-ST D M A  algo rithm a nd 7.4 8 % wo rse   than SGLS -STDMA al gorit hm pe rform a nce. In th e a v erage  length  of sched ulin g pa ramete r,  the  prop osed alg o rithm provid es 9.98% lo wer than  the G P -STDMA an d 8.99% high er than SGL S - STDMA. F r o m  this re sult,  the p r o p o s e d  alg o ri thm  i s  p r ove n  to  have b e tter  p e rform a n c e  than  GP-STDMA algorithm a nd  clo s ed to SG LS -STDMA algorithm p e rfo r man c e.            Figure 3. Net w ork throug h put perfo rma n ce           Figure 4. Len gth of sch edu ling perfo rma n ce       30 40 50 60 70 80 90 10 0 11 0 0 1 2 3 4 5 6 7 8 9 10 N u m ber  of  nod es N e t w or k  T h r oughput  ( M bps )     TD M A AL S-ST D M A GP - S T D M A SG L S -ST D M A P r opo s e d  a l gor i t h m   30 40 50 60 70 80 90 100 110 0 1 2 3 4 5 6 N u m ber  of  nod es Le ngt h  os sch edu l i n g  ( m s)     TD M A AL S-ST D M A GP - S T D M A SG L S -ST D M A P r opos ed algor it hm   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Modified Greedy  Phy s i c a l  Link   Scheduling Algorithm  for Improv ing  ....  (Nac hwan Mufti A.)   209 The adva n ta ge of our  alg o rithm is i n  the aspe ct of comp utationa l compl e xity.  From the   compl e xity analysi s  in Section 2, we  obtain  that the propo sed algorith m  have compl e xity  log ≅ . We can state that the ne w sched uling  para m eters that are introd uce d  in the  algorith m  ca n improve th e ba sic gree dy algo ri thm  without  add  com p lexity signifi cantly. For  comp aration referen c e, ALS-STDMA al gorithm com p lexity is   log  as reporte d in   [13] , where    is the numb e r  of link,   is the numbe r of node,   is the thickne ss of  grap h, and    is the maxim u m nod e de g r ee. Th e GP-STDMA alg o rithm com p lex i ty is    and th e SGLS- STDMA complexity is    [10]. So, it can be co ncl ude d that the propo sed al go rithm giving  perfo rman ce  better than t he conventio nal greedy p h ysical algo ri thm in simila r co mputatio nal   compl e xity. In othe rsi de, t he p e rfo r man c e  of t he  pro posed  algo rithm cl osed to  the b e st  re sult   that is achi eved in the SGL S -STDMA alg o rithm in lo wer co mplexity.      5. Conclusio n   This pa per shows th e o p portunity to  i n crea se  wi rel e ss m e sh n e t work  perfo rmance via  improvin g greedy physi ca l algorithm fo r STDMA p r o t ocol a c cess.  The improve m ent of network  throug hput a nd length of  sched uling in  low com put ational compl e xity can be  achi eved by an   extensio n of interferen ce p a ram e ters th at is  de rived from ge ometri cal no de p o si tions. We sh o w   that three pa ramete rs that  are intro d u c ed in th is pa per can be e x ploited in a gree dy way to   improve  wirel e ss network perfo rman ce  clo s e to t he b e st re sult of mesh lin k sch edulin g algo ri thm  performanc e  in lower c o mplexity.        Ackn o w l e dg ement  The first aut hor is a le ct ure r  in Unive r sita s Tel k o m  that pursu ing do ctoral  degree in  Universitas Indonesia. Thi s  work  is partly financed by Dikti  through  BPPDN schol arship schem e .      Referen ces   [1]  IF  Akyild iz, X  W ang, W  W ang. W i reless m e sh n e t w orks:  a surve y .  Els e vier J. Com p ut. Networks .  200 5; 47: 445 – 487.   [2]  R Brun o, M C onti, E Gre gori .  Mesh N e t w or ks: Commodit y  Multihop  Ad  Hoc Net w orks.   C o mm un.  Mag. IEEE . 2005: 123 –1 31.   [3]  MH Satria, J Yunus, E Supr i y anto. Emerg enc y Pr en atal  T e lemonitori ng  S y stem in W i reless Mes h   Net w ork.  TEL K OMNIKA . 2014 ; 12(1): 123 –13 4.  [4]  L Hui. A Nov e l  QoS Routi ng A l gorit hm in Wir e less Mes h  Ne t w orks.  T E LKO M NIKA Indon e s . J. Electr.  Eng.  201 3; 11( 3): 1652 –1 664.   [5] E  Borcoci.  W i reless Mes h  Ne tw orks T e chnol ogi es: Architec tures , Protocol s , Resource M ana ge me nt  and  Appl icatio ns . 200 9. [Online].  Avail abl e:  http:// w w w . i a ri a.org/confer en ces20 09/fil e sICW MC 09/Eu g enBorc o ciT u torial.p df. [Accessed: 10-Oct- 201 4].  [6]  R Nelso n , L Kleinr ock. Spati a l T D MA: A  Collis io n-Free multih op Ch an n e l Access Protocol.  IEEE   T r ans. Commu n.  1985; COM- 33(9).   [7]  P Bjorklund, V  Peter, D Y u an.  Res ource  Opti mi z a t i o n  of S p atial  T D MA i n   Ad H o c R adi o  Netw orks: A   Colu mn Ge ner ation  Ap proac h . INF O COM 200 3. T w e n t y - S econ d A nnu a l  Joi n t C onfer ence  of th e   IEEE Compute r  and Comm un icatio ns . IEEE  Societi e s. 200 3; 00(C).  [8] J  Gronkvist.  Assign ment Met hods for S pati a l R euse T D M A . Mo b i le  an d Ad  H o c  N e t w o r ki ng  a n d  Comp uting (M obiHOC). 2 000 : 119–1 24.   [9]  O Somarriba,  J Z ander.  Rob u st ST DMA sched uli ng i n  Mu lti-ho p W i reles s  Netw orks for singl e-no d e   positi on p e rturbatio ns.  200 9 IEEE 20th Int. S y mp. Pers. In door Mo b. Rad i o Commu n .  20 09: 566 –5 71.   [10]  AD Gore, A Karan d ikar. Li nk  Schedu lin g Al gorithms for W i reless Mes h  Net w orks.  Comm un. Surv.   Tutorials, IEEE . 2011; 13( 2): 258– 27 3.  [11]  W  Chen, C  L ea. A No de-B a sed T i me Sl ot Assignm ent  Algorit hm for  ST DMA W i re less Mes h   Net w orks.  IEEE Trans. Veh. Technol.  201 3; 62(1): 272 –2 8 3 .  [12]  P Gupta, PR Kumar. T he  Capacit y  of W i rel e ss Net w o r ks.  IEEE Trans. Inf. Theory.  2000;  46(2): 388 – 404.   [13]  S Rama natha n, EL Ll o y d.  Sched uli ng  alg o rithms for m u ltih op ra di o n e t w o r ks.  IEEE/ACM Trans.   Netw .  1993; 1(2): 166– 17 7.  [14]  T  Moscibroda,  R W a ttenhof er. Col o rin g   Unstru cture d   Radi o N e t w or ks Categ o ries  and S ubj ect  Descript o rs.  Distrib. Comput.  200 5; 21(4): 27 1–2 84.   Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 16 93-6 930   TELKOM NIKA   Vol. 13, No. 1, March 2 015 :  202 – 2 1 0   210 [15]  A Behzad, I Rubi n. On t he Performanc e o f  Graph-base d  Schedu lin g Al gorithms for Packet Rad i o   Net w orks.  IEEE Glob. Telecomm un. Conf.  2 003; 6: 34 32– 3 436.   [16]  J Grönkvist, A Hanss on.  Co mp ariso n  b e tw een gra p h - base d  an d i n terferenc e-b a s ed ST DMA   sched uli n g . Proc. 2nd ACM Int. Sy m p . Mob.  ad hoc Net w .  Comp ut. - MobiHoc ’0 1. 20 01:  255.   [17]  K Jain, J P a d h y e, V N  Pa dma nab ha n, L Qiu.   Im pact Of Interference On  M u lti-h op Wire le ss Netw ork  Performanc e.  Procee din g  AC M Mobicom. 2 003: 66 –8 0.  [18]  G Brar, DM Blou gh, P Santi .   Comp utatio n a lly Efficie n t Sched uli ng w i th the Physical  Interference   Mode l for T h roug hp ut Impro v ement in W i r e less Mes h  N e tw orks.  Proceedi ngs of the  12th a nnu a l   intern ation a l co nferenc e on M obil e  comp utin g and n e t w ork i ng (ACM). 200 6: 2–13.   [19]  L Bad i a, A Ert a , L L enzi n i, F  Rossetto, M Z o rzi.  A Physic a l Mod e l Sc hed uler for M u lti-H op W i re less   Netw orks Base d on Loc al Info rmati o n . 5th IEEE Int. Conf. M ob. Ad Hoc Sens. S y st .  2008:  213– 22 2.  [20]  D Yang,  X F ang, N Li, G Xue.  A Simple  Greedy Alg o rit h m for Li nk Sched uli ng w i th  the Physica l   Interference M ode l . Globa l T e lecommu nic a ti ons Co nfere n c e  (GLOBECOM). IEEE. 2009 .  [21] AD  Gore.  On W i reless Li nk  Sched uli ng a n d  F l ow  Control . Indian Institut e of T e chnolo g y  B o mba y .  200 8.  [22]  O Goussevska ia, YA Os w a ld,  R Wattenhofe r .  Comp lexity i n  geo metric SINR.  Proc. ACM MobiHoc.   200 7: 100 –1 09 .  [23]  W  Liu,  D Mi ao,  X C hen,  W  W ang. A  N o vel  L i nk  Sc hed ul ing  Alg o rithm for   Spatia l R eus e  in W i re les s   Net w orks. IEEE Veh. T e chnol. Conf. (V T C  Fall). 20 12: 1– 5.  [24]  CE Sh an non.   A Mathem atic al T heor y  of  Commun i cati o n .  Bell Syst.  Tech. J.  1 948 : 27(Ju l y   and   October): 379 – 423,6 2 3 –65 6.     Evaluation Warning : The document was created with Spire.PDF for Python.