## PENJADWALAN TIPE DAWN-A DAN DAWN-B PADA JARINGAN RADIO SINKRON

## Nola Marina
Pusat Studi Komputasi Matematika, Universitas Gunadarma Jl. Margonda Raya no. 100, Depok 16424, Jawa Barat nolamarina@staff.gunadarma.ac.id

## Abstrak
Teknologi  jaringan  nirkabel  berkembang  sangat  pesat  karena  kebutuhan  akan mudahnya  komunikasi  data  jarak  jauh.      Jaringan  radio  adalah  jaringan nirkabel  dengan  gelombang  radio  sebagai  mediumnya.  Masalah  penjadwalan pada  Jaringan  Radio  Sinkron  (JRS)  adalah  bagaimana  memilih  slot  waktu pengiriman  suatu  data  dengan  rute  tertentu  (dari  simpul  sumber  ke  simpul tujuan)  dalam  suatu  jaringan  sedemikian  sehingga  jadwal  valid,  tidak  ada konflik  dan  jumlah  slot  waktu  yang  digunakan  minimal.  Pada  penelitian  ini dipelajari  dua  tipe  penjadwalan  pada  JRS  berdasarkan  cara  mengalokasikan slot  waktunya,  yaitu  tipe  DAWN-A  dan  DAWN-B.  Hasil  dari  penelitian  ini adalah  terdapat  dua  bagian  penting  dalam    masalah  penjadwalan  pada  JRS, yaitu  bagaimana  menentukan  urutan  request  dalam  mengelokasikan  slot  waktu dan bagaimana tipe mengalokasikan slot waktu pada setiap request yang dapat menghasilkan  penjadwalan  dengan  total  slot  waktu  minimal.  Berdasarkan simulasi juga diperoleh bahwa tipe DAWN-B menghasilkan solusi penjadwalan yang lebih baik daripada tipe DAWN-A untuk JRS topologi rantai.
Kata Kunci : Jaringan, radio, pendajwalan, rantai.

## DAWN-A AND DAWN-B TYPE OF SCHEDULING ON THE SYNCHRONOUS RADIO NETWORK

## Abstract
Wireless  network  technology  is  growing  very  rapidly  because  of  the  need  for easy  long  distance  data  communication.  Radio  networks  are  wireless  networks with  radio  waves  as  their  medium.  The  scheduling  problem  in  Synchronous Radio  Network  (SRN)  is  how  to  select  the  time  slot  for  sending  data  with  a particular route (from the source node to the destination node) in a network so that the schedule is valid, no conflicts and the minimum number of time slots is used. In this study we studied two types of scheduling on SRN based on how to allocate time slots, ie DAWN-A and DAWN-B types. The results of this study are two  important  parts  of  the  scheduling  problem  in  JRS:    how  to  determine  the order  of  request  in  allocating  time  slot  and  how  type  to  allocate  time  slot    on each request which can generate scheduling with minimum total time slot. Based on  the  simulation  results  obtained  that  the  DAWN-B  type  provides  a  better solution than the DAWN-A type for SRN  chain topology.
Keywords : Network, radio, scheduling, chain.

## PENDAHULUAN
Teknologi  jaringan  nirkabel  ber- tujuan  untuk  memudahkan  komunikasi data  antar  perangkat,  terutama  komu- nikasi  data  jarak  jauh    Salah  satu  jenis jaringan  nirkabel  adalah  jaringan  radio, yaitu  jaringan  nirkabel  dengan  gelom- bang radio sebagai mediumnya.
Jaringan  radio adalah  kumpulan dari  stasiun  (simpul)  pengirim  dan penerima  yang  berkomunikasi  antara satu  dengan  lainnya  melalui  link  multi- hop.    Penggunaan  medium  radio  pada jaringan  radio  menyebabkan  adanya karakteristik  berikut:  1)  ketika  simpul mengirim  data,  semua  simpul  dalam jangkauan  transmisinya  dapat  menerima sinyal  transmisi.  2)  Data  yang  dikirim dapat  mencapai  simpul  lebih  dari  satu hop  dari  simpul  asal.  3)  Karena  semua simpul  memiliki  frekuensi  yang  sama, tabrakan data dapat terjadi jika dua atau lebih  simpul  tetangga  mengirim  data secara bersamaan. [3]
Jaringan  radio  bersifat multihop karena  memiliki  jangkauan  terbatas sehingga  terdapat  pengiriman  data  antar dua  simpul  yang  harus  melalui  simpul perantara  terlebih  dahulu.  Selain  itu, jaringan  radio  pada  penelitian  ini  di- asumsikan bersifat omnidirectional , sim- pul  mengirim  data  secara  sinkron  dan pada suatu slot setiap simpul dapat men- jadi  pengirim  atau  penerima  ( Half duplex ). Penelitian  terdahulu  tentang  pen- jadwalan  pada  jaringan  radio  diantara- nya :     A Lower bound for radio broad- cast  [1], Request Satisfication  Problem in  Synchronous  Radio  Network  [3], Scheduling  broadcast  in  multihop  radio networks [4]  dan  Scheduling  Algorithm for Multihop Radio  Networks  [6]. Berdasarkan  penelitian  terdahulu  terse- but  didefinisikan  masalah  penjadwalan pada Jaringan Radio Sinkron (JRS) pada penelitian  ini:  bagaimana  memilih  slot waktu  pengiriman  suatu  data  dengan
rute  tertentu  (dari  simpul  sumber  ke simpul  tujuan)  dalam  suatu  jaringan sedemikian  sehingga  jadwal  valid,  tidak ada  konflik  dan  jumlah  slot  waktu  yang digunakan  minimal.  Secara  umum, masalah  penjadwalan request pada  JRS adalah  NP- hard (kelas  masalah  yang sulit secara komputasi) [3].
Pada  penelitian  ini  dipelajari  dua tipe  penjadwalan  pada  JRS  berdasarkan cara  mengalokasikan  slot  waktunya, yaitu tipe DAWN-A dan DAWN-B.

## METODE PENELITIAN
Suatu  jaringan  radio  direpresen- tasikan  oleh  graf  tak  berarah 𝐺 dimana himpunan vertex 𝑉(𝐺) merepresentasi- kan  himpunan  simpul  dalam network . Sisi 𝑒 = {𝑢, 𝑣} ∈ 𝐸(𝐺) menggambarkan bahwa simpul 𝑢 berkomunikasi langsung  dengan  simpul 𝑣 dan  seba- liknya.
Request 𝒓 adalah pasangan (𝑠, 𝑡), 𝑑𝑖𝑚𝑎𝑛𝑎  𝑠, 𝑡  ∈ 𝑉(𝐺) , 𝑠 adalah simpul asal dan 𝑡 adalah simpul tujuan. Path panjang 𝑘 pada graf 𝐺 adalah urutan (𝑣 0 , 𝑣 1 , … . , 𝑣 𝑘 ) dimana 𝑣 𝑖 ∈ 𝑉(𝐺) untuk  setiap 𝑖 ∈ [0, 𝑘] sedemikian sehingga  edge (𝑣 𝑖 , 𝑣 𝑖+1 ) ada  di 𝐸(𝐺) untuk  setiap 𝑖 ∈ [0, 𝑘 − 1] ,  dan  setiap edge adalah berbeda. Pada penelitian ini path  yang  diteliti  dibatasi  pada  simple path,  yaitu  path  yang  setiap vertex nya dikunjungi  paling  banyak  sekali.  Path merepresentasikan jalan komunikasi data  pada  jaringan.  Misalkan 𝑃 adalah fungsi  routing pada 𝑅 yang  berasosiasi dengan  setiap 𝑟 = (𝑠, 𝑡) ∈ 𝑅 .  Path 𝑷(𝒓) atau 𝑷 𝒓 di 𝐺 dimulai  dari  simpul asal 𝑠 dan berakhir pada simpul tujuan 𝑡 . Diberikan graf 𝐺 , kumpulan request 𝑅 ,  dan  fungsi  routing 𝑃 ,  maka didefinisikan date  assignment 𝑑 adalah fungsi  dari 𝑟 = (𝑠, 𝑡) ∈ 𝑅 dan 𝑥 ∈ 𝑃 𝑟 ( 𝑥 ≠ 𝑡 )  yang  mengembalikan  nilai 𝒅(𝒓, 𝒙) . Nilai 𝑑(𝑟, 𝑥) ini berko- respondensi  dengan  suatu  slot  waktu, yang  artinya 𝑥 mengirim  data  dari 𝑟 ke
hop  berikutnya  selama  slot  waktu  ter- sebut.
Suatu  assignment  dikatakan valid jika  untuk  setiap request 𝑟 = (𝑥 0 , 𝑥 𝑘 )
dengan fungsi routing 𝑃 𝑟 = (𝑥 0 , 𝑥 1 , … . , 𝑥 𝑘 ) , memenuhi syarat: 𝑑(𝑟, 𝑥 0 ) < 𝑑(𝑟, 𝑥 1 ) < ⋯ . < 𝑑(𝑟, 𝑥 𝑘−1 ) < 𝑑(𝑟, 𝑥 𝑘−1 ) .
Suatu assignment dikatakan bebas konflik jika  untuk  setiap 𝑑(𝑟, 𝑥 𝑖 ) ≠ 𝑑(𝑟 ′ , 𝑦 𝑗 )dan 𝑟 ≠ 𝑟 ′ , memenuhi ketiga syarat berikut:
1. Setiap transmisi hanya boleh mengirim satu data   : 𝑥 𝑖 ≠ 𝑦 𝑗
2. Suatu simpul tidak dapat mengirim dan menerima data secara bersamaan dalam satu slot waktu : .
𝑥 𝑖+1 ≠ 𝑦 𝑗 dan 𝑥 𝑖 ≠ 𝑦 𝑗+1 3. Tidak boleh terjadi tabrakan/ collide: { 𝑥 𝑖 , 𝑦 𝑗+1 } ∉ 𝐸(𝐺) ∧ {𝑦 𝑗 , 𝑥 𝑖+1 } ∉ 𝐸(𝐺)

## HASIL DAN PEMBAHASAN
Model  interferensi  digunakan untuk  mendefinisikan  jenis  gangguan yang  perlu  dihindari  pada  jaringan karena  mengakibatkan    transmisi  data tidak  berhasil  dilakukan,  data  tidak sampai  ke  simpul  tujuan  atau  data diterima  tetapi  tidak  sesuai  dengan  data
yang  dikirim.  Berdasarkan  syarat  bebas konflik  yang  dijelaskan  sebelumnya, model  interferensi  pada  JRS  yang digunakan pada penelitian ini adalah : 1. Jika  suatu node mengirim  lebih  dari satu  data  dalam  slot  waktu    yang sama.  Pada  Gambar  1  (a)  simpul tujuannya  sama,  sedangkan  pada Gambar 1 (b) simpul tujuan berbeda.
2. Jika  suatu  simpul  mengirim  dan menerima  data  secara  bersamaan dalam  satu  slot  waktu.  Pada  Gambar 2  (a)  simpul 𝑢 mengirim  dan menerima  data  ke  dan  dari  simpul yang sama  , sedangkan pada  Gambar 2  (b)  simpul 𝑢 mengirim  dan menerima  data  ke  dan  dari  simpul yang berbeda.
3. Jika  terdapat  dua  atau  lebih  tetangga dari  suatu  simpul  yang  mengirimkan data  pada  waktu  yang  sama.  Pada Gambar  3  (a) node 𝑣 dan node 𝑤 mengirim  data  ke node 𝑢 dalam  slot waktu  yang  sama,  sedangkan  pada Gambar  3  (b) node 𝑣 mengirim  data ke node 𝑢 dan node 𝑤 mengirim data ke node 𝑥 dalam  slot  waktu  yang sama. Maka sinyal dari node 𝑤 juga akan  diterima  oleh node 𝑢 sehingga terjadi tabrakan data pada node 𝑢 .
(a)
(b)
Gambar 1.  Model Interferensi Pertama
(a) (b)
Gambar 2.  Model Interferensi Kedua
(a) (b)
Gambar 3. Model Interferensi Ketiga
Pada  penelitian  ini,  dipelajari  dua tipe  mengalokasikan  slot  waktu  untuk setiap request pada  masalah  pen- jadwalan request JRS, yaitu :
1. DAWN- A Pada DAWN-A , jadwal dikatakan valid jika memenuhi:
𝑑(𝑟 𝑖 , 𝑥 0 ) < 𝑑(𝑟 𝑖 , 𝑥 1 ) < ⋯ < 𝑑(𝑟 𝑖 , 𝑥 𝑘−1 ) < 𝑑(𝑟 𝑖 , 𝑥 𝑘−1 ) dan cara  mengalokasikan  slot  waktu dilakukan  dengan  menjadwalkan setiap request sesegera  mungkin dengan  slot  waktu  terkecil  yang available .  Dengan  kata  lain,  satu slot waktu dialokasikan untuk sebanyak  mungkin request hingga kapasitas  penuhnya,  dengan  syarat valid dan tidak konflik.
Pertama, 𝑑(𝑟 𝑖 , 𝑥 0 ) dijadwalkan untuk  setiap 𝑖 ,  kemudian 𝑑(𝑟 𝑖 , 𝑥 1 ) dijadwalkan  untuk  setiap 𝑖 ,  dan seterusnya  hingga  semua request berhasil dijadwalkan.
2. DAWN- B
Pada DAWN- B, jadwal
dikatakan valid jika  memenuhi: 𝑑(𝑟 𝑖 , 𝑥 𝑗 + 1) =  𝑑(𝑟 𝑖 , 𝑥 𝑗 ) + 1
Cara  mengalokasikan  slot  waktu dilakukan  dengan  menjadwalkan satu request sesegera  mungkin dengan  slot  waktu  terkecil  yang available , terus-menerus hingga sampai  ke node tujuan,  baru kemudian  menjadwalkan request berikutnya.
Pertama,  dijadwalkan request
urutan pertama 𝑑(𝑟 1 , 𝑥 0 ), 𝑑(𝑟 1 , 𝑥 1 ), … . , 𝑑(𝑟 1 , 𝑥 𝑘−1 ) , kemudian 𝑑(𝑟 2 , 𝑥 0 ), 𝑑(𝑟 2 , 𝑥 1 ), … . , 𝑑(𝑟 2 , 𝑥 𝑘−1 ) dijadwalkan setelahnya, dan seterusnya  hingga request terakhir 𝑑(𝑟 𝑚 , 𝑥 0 ), 𝑑(𝑟 𝑚 , 𝑥 1 ), … . , 𝑑(𝑟 𝑚 , 𝑥 𝑘−1 ) .

## Deskripsi Penjadwalan JRS
Untuk  mendeskripsikan  masalah penjadwalan request pada  JRS  secara umum, diberikan contoh masalah penjadwalan request pada  JRS  topologi sembarang.
Masalah  1:  Diberikan  masalah penjadwalan request pada  JRS  dengan input (𝐺, 𝑅, 𝑃) , 𝐺(𝑉, 𝐸) graf  tidak berarah, kumpulan request 𝑅 = {𝑟 1 , 𝑟 2 , 𝑟 3 } , 𝑟 1 = (𝐴, 𝐹), 𝑟 2 = (𝐶, 𝐸), 𝑑𝑎𝑛 𝑟 3 = (𝐸, 𝐺) dan fungsi routing 𝑃(𝑟 1 ) = (𝐴, 𝐵, 𝐷, 𝐹), 𝑃(𝑟 2 ) = (𝐶, 𝐷, 𝐸), 𝑑𝑎𝑛 𝑃(𝑟 3 ) = (𝐸, 𝐹, 𝐺) . Beberapa  solusi  yang  valid  dan  bebas konflik diberikan pada Tabel 1.
Pada  Tabel  1  dapat  dilihat  cara menemukan  penjadwalan  sebuah  JRS. Kolom  pertama  adalah  urutan request yang  menyatakan  urutan request yang dijadwalkan  terlebih  dahulu.  Kolom kedua  adalah  ilustrasi  langkah-langkah menemukan penjadwalan yang valid dan bebas konflik. Kolom ketiga adalah total slot waktu penjadwalan.
Pada DAWN-A, syarat 𝑑(𝑟 𝑖 , 𝑥 0 ) < 𝑑(𝑟 𝑖 , 𝑥 1 ) < ⋯ < 𝑑(𝑟 𝑖 , 𝑥 𝑘−1 ) < 𝑑(𝑟 𝑖 , 𝑥 𝑘−1 ) harus dipenuhi. Untuk urutan request 𝑟 1 , 𝑟 2 , 𝑟 3 ,  langkah  pertama, 𝑑(𝑟 𝑖 , 𝑥 0 ) dijadwalkan  untuk  ketiga request dengan urutan 𝑟 1 , 𝑟 2 ,  kemudian 𝑟 3 . Request 𝑟 1 ditransmisikan  dari node 𝐴 ke node 𝐵 pada  slot  waktu  1,  kemudian  slot  waktu 1  dicoba  dialokasikan  untuk request dengan  urutan  berikutnya,  yaitu 𝑟 2 dan 𝑟 3 . Request 𝑟 2 dapat  ditransmisikan  dari node 𝐶 ke node 𝐷 pada  slot  waktu  1, namun 𝑟 3 tidak dapat ditransmisikan dari node 𝐸 ke node 𝐹 pada  slot  waktu  1 karena menyebabkan konflik data dengan 𝑟 2 yang  dikirim  dari node 𝐶 ke node 𝐷 (melanggar syarat bebas konflik yang  ketiga). Request 𝑟 3 ditransmisikan dari node 𝐸 ke node 𝐹 pada  slot  waktu yang available terkecil, yaitu slot 2.

## Tabel 1. Beberapa Solusi Masalah 1
DAWN-A Urutan request Ilustrasi penjadwalan JRS Max (d) 𝑟 1 , 𝑟 2 , 𝑟 3 6
𝑟 1 , 𝑟 3 , 𝑟 2 5
DAWN - B Urutan request Ilustrasi penjadwalan JRS Max (d) 𝑟 1 , 𝑟 2 , 𝑟 3 7
𝑟 3 , 𝑟 1 , 𝑟 2 6
Langkah kedua, 𝑑(𝑟 𝑖 , 𝑥 1 ) dijadwalkan untuk ketiga request .
Request 𝑟 1 tidak  ditransmisikan  dari node 𝐵 ke node 𝐷 pada  slot  waktu  2 karena  akan  terjadi  konflik  data. Akibatnya 𝑟 1 ditransmisikan dari node 𝐵 ke node 𝐷 pada slot waktu 3. Request 𝑟 2 tidak  dapat  ditransmisikan  dari node 𝐷 ke node 𝐸 pada  slot  waktu  2,  dan  3 sehingga ditransmisikan pada slot waktu 4. Request 𝑟 3 tidak dapat ditransmisikan dari node 𝐹 ke node 𝐺 pada slot waktu 3
dan 4  sehingga ditransmisikan pada slot waktu  5.  Langkah  berikutnya,  di- jadwalkan 𝑑(𝑟 𝑖 , 𝑥 2 ) untuk request 𝑟 1 . Request 𝑟 1 tidak  dapat  ditransmisikan dari node 𝐷 ke node 𝐹 pada slot waktu 4 dan 5  sehingga ditransmisikan pada slot waktu 6.
Dari  penjadwalan  ini  diperoleh total  slot  waktu  agar  semua request berhasil  dijadwalkan  adalah  6.  Pada DAWN-A dengan  urutan 𝑟 1 , 𝑟 3 , 𝑟 2 , dilakukan  penjadwalan  dengan  cara yang sama seperti di atas. Dengan urutan tersebut, diperoleh total slot waktu yang lebih kecil, yaitu 5.
Pada  DAWN-B , syarat (𝑟 𝑖 , 𝑥 𝑗 + 1) =  𝑑(𝑟 𝑖 , 𝑥 𝑗 ) + 1 harus dipenuhi.
Untuk urutan request 𝑟 1 , 𝑟 2 , 𝑟 3 , 𝑑(𝑟 1 , 𝑥 0 ), 𝑑(𝑟 1 , 𝑥 1 ), 𝑑(𝑟 1 , 𝑥 2 ) dijadwalka n terlebih dahulu, kemudian 𝑑(𝑟 2 , 𝑥 0 ), 𝑑(𝑟 2 , 𝑥 1 ) , dan 𝑑(𝑟 3 , 𝑥 0 ), 𝑑(𝑟 3 , 𝑥 1 ) .  Langkah  pertama, request 𝑟 1 ditransmisikan dari node 𝐴 ke node 𝐵 pada  slot  waktu  1,  dari node 𝐵 ke node 𝐷 pada  slot  waktu  2,  dan  dari node 𝐷 ke node 𝐹 pada slot waktu 3. Langkah  kedua, request 𝑟 2 tidak dapat  ditransmisikan  dari node 𝐶 ke node 𝐷 pada  slot  waktu  1,2  dan  3 sehingga ditransmisikan pada slot waktu 4.  Kemudian 𝑟 2 ditransmisikan dari node 𝐷 ke node 𝐸 pada slot waktu 5. Langkah ketiga, request 𝑟 3 tidak  dapat  ditrans- misikan dari node 𝐸 ke node 𝐹 pada slot waktu  1,2,3,4,  dan  5,    sehingga  ditrans- misikan pada slot waktu 6.  Kemudian 𝑟 3 ditransmisikan  dari node 𝐹 ke node 𝐺 pada slot waktu 7.
Dari  penjadwalan  ini  diperoleh total  slot  waktu  agar  semua request berhasil  dijadwalkan  adalah  7.  Pada DAWN-B dengan  urutan 𝑟 3 , 𝑟 1 , 𝑟 2 ,  di- lakukan  penjadwalan  dengan  cara  yang sama  seperti  di  atas.  Dengan  urutan  in diperoleh total slot waktu 6. Berdasarkan  deskripsi  masalah
JRS  pada  Tabel  1,  dapat  disimpulkan bahwa:
a. Untuk  menjadwalkan  kumpulan
request  yang  sama,  jika  urutan request dalam proses mengalokasikan slot waktu berbeda  maka    total  slot  waktu  yang digunakan  dapat  berbeda  pula.    Ber- dasarkan  hal  ini,  salah  satu  bagian  dari masalah  penjawalan  request  pada  JRS adalah  bagaimana  menemukan  urutan request yang menghasilkan  penjadwalan dengan  total slot waktu minimal.
b. Perbedaan  tipe  pengalokasian slot waktu yang digunakan  dapat meng- hasilkan  total  slot  waktu  yang  berbeda pula.  Dalam  hal  ini,  yang  diteliti  adalah 2 tipe saja, yaitu DAWN-A dan DAWN- B.  Untuk  contoh  masalah    JRS  topologi sembarang  ini,  tidak  dapat  disimpulkan tipe yang lebih baik di antara keduanya.

## Deskripsi  Penjadwalan  JRS  Topologi Rantai
Masalah  2:  Diketahui  sebuah jaringan  berupa  sebuah  graf  tak  berarah berbentuk  rantai,    dengan  C= [1,2, . .7] dan  kumpulan request 𝑅 = {𝑟 1 , 𝑟 2 , 𝑟 3 } . Banyak vertex 𝑛  = 7 dan banyak request 𝑚 =  3 ,  yaitu 𝑟 1 = (3,7) , 𝑟 2 = (2,5), 𝑑𝑎𝑛 𝑟 3 = (1,3) .  Beberapa  solusi penjadwalan  yang  valid  dan  bebas konflik diberikan pada Tabel 2.
Untuk  DAWN-A  dengan  urutan request 𝑟 1 , 𝑟 2 , 𝑟 3 ,  pada  langkah  pertama, 𝑑(𝑟 𝑖 , 𝑥 0 ) dijadwalkan  untuk  ketiga request . Request 𝑟 1 ditransmisikan  dari simpul 3 ke  simpul 4 pada  slot  waktu 1, request 𝑟 2 dapat  ditransmisikan  dari simpul 2 ke simpul 3 pada slot waktu 2, dan 𝑟 3 ditransmisikan  dari  simpul 1 ke simpul 2 pada slot waktu 3. Langkah  kedua, 𝑑(𝑟 𝑖 , 𝑥 1 ) dijad- walkan  untuk ketiga request . Request 𝑟 1 ditransmisikan dari simpul 4 ke simpul 5 pada  slot  waktu  3. Request 𝑟 2 ditrans- misikan dari simpul 3 ke simpul 4 pada slot  waktu  4. Request 𝑟 3 ditransmisikan dari  simpul 2 ke  simpul 3 pada  slot waktu  5.  Langkah  berikutnya,  dijad- walkan 𝑑(𝑟 𝑖 , 𝑥 2 ) untuk request 𝑟 1 dan 𝑟 2 . Request 𝑟 1 ditransmisikan dari simpul
5 ke  simpul 6 pada  slot  waktu  5. Request 𝑟 2 ditransmisikan  dari  simpul 4 ke  simpul 5 pada  slot  waktu  6. Kemudian  dijadwalkan 𝑑(𝑟 𝑖 , 𝑥 3 ) untuk
request 𝑟 1 . Request 𝑟 1 ditransmisikan dari  simpul 6 ke  simpul 7 pada  slot waktu 7.
Tabel 2. Beberapa Solusi Masalah 2
DAWN- A Urutan request Ilustrasi penjadwalan JRS max (d) 𝑟 1 , 𝑟 2 , 𝑟 3 7
𝑟 3 , 𝑟 1 , 𝑟 2 9 DAWN - B Urutan request Ilustrasi penjadwalan JRS Max (d) 𝑟 1 , 𝑟 2 , 𝑟 3 6
𝑟 3 , 𝑟 1 , 𝑟 2
7
𝑟 2 :                              3 4 5
𝑟 3 :       5                 6
𝑟 1 :                                                1 2                                    3
4 1                 2 3 4 5                 6                   7 𝑟 2 :                              5 6 7
𝑟 3 :       1                2
𝑟 1 :                                                3 4                                  5
6 1                 2 3 4 5                 6                   7
𝑟 2 :                              2 4 6 𝑟 3 :       3                 5
𝑟 1 :                                                1
3                                  5 7 1 2 3 4 5                 6                   7 𝑟 2 :                              3 6 8
𝑟 3 :        1                4 𝑟 1 :                                                2 5                                7 9
1 2 3 4 5                 6                   7
Dari  penjadwalan  ini  diperoleh total  slot  waktu  (max  (d))  agar  semua request berhasil  dijadwalkan  adalah  7. Pada DAWN-A  dengan urutan 𝑟 3 , 𝑟 1 , 𝑟 2 , dilakukan  penjadwalan  dengan  cara yang sama seperti di atas. Dengan urutan tersebut, diperoleh total slot waktu (max (d))  9.
Untuk    DAWN-B  dengan urutan request 𝑟 1 , 𝑟 2 , 𝑟 3 , 𝑑(𝑟 1 , 𝑥 0 ), 𝑑(𝑟 1 , 𝑥 1 ), 𝑑(𝑟 1 , 𝑥 2 ), 𝑑𝑎𝑛 , 𝑑(𝑟 1 , 𝑥 3 ) dijadwalkan  terlebih  dahulu,  kemudian 𝑑(𝑟 2 , 𝑥 0 ), 𝑑(𝑟 2 , 𝑥 1 ), 𝑑(𝑟 2 , 𝑥 2 ) , dan 𝑑(𝑟 3 , 𝑥 0 ), 𝑑(𝑟 3 , 𝑥 1 ) .  Langkah  pertama, request 𝑟 1 ditransmisikan  dari  simpul 3 ke  simpul 4 pada  slot  waktu  1,  dari simpul 4 ke simpul 5 pada slot waktu 2, dari  simpul 5 ke  simpul 6 pada  slot waktu  3,  dan  dari  simpul 6 ke  simpul 7 pada slot waktu 4.
Langkah kedua, request
𝑟 2 ditransmisikan dari simpul 2 ke simpul 3 pada  slot  waktu  3,  dari  simpul 3 ke simpul 4 pada  slot  waktu  4,  dan  dari simpul 4 ke simpul 5 pada slot waktu 5. Langkah  ketiga, request 𝑟 3 ditrans- misikan  dari simpul 1 ke simpul 2 pada slot  waktu  5,  dan  dari  simpul 2 ke simpul 3 pada slot waktu 6.
Dari  penjadwalan  ini  diperoleh total  slot  (max  (d))    waktu  agar  semua request berhasil  dijadwalkan  adalah  6.
Pada DAWN-B  dengan urutan 𝑟 3 , 𝑟 1 , 𝑟 2 , dilakukan  penjadwalan  dengan  cara yang sama seperti di atas. Dengan urutan ini  diperoleh  total  slot  waktu  (max  (d)) 7.  Berdasarkan  deskripsi  masalah  JRS pada  Tabel  2,  dapat  disimpulkan  bahwa cara  mengalokasikan  slot  waktu  pada setiap request untuk  masalah  penjad- walan  request  pada  JRS  topologi  rantai, lebih tepat menggunakan tipe DAWN-B karena  menghasilkan  solusi  yang  selalu lebih baik daripada tipe DAWN-A.

## SIMPULAN DAN SARAN
Hasil  dari  penelitian  ini  adalah terdapat  dua  bagian  penting  dalam
masalah  penjadwalan  pada  JRS,  yaitu bagaimana  menentukan  urutan request dalam  mengelokasikan  slot  waktu  dan bagaimana  tipe  mengalokasikan  slot waktu  pada  setiap request yang  dapat menghasilkan  penjadwalan  dengan  total slot  waktu  minimal.  Dari  pembahasan diperoleh  bahwa  tipe  DAWN-B  meng- hasilkan  solusi  penjadwalan  yang  lebih baik  daripada  tipe  DAWN-A  untuk  JRS topologi  rantai,  namun  tidak  dapat disimpulkan  untuk  JRS  topologi  sem- barang.

## DAFTAR PUSTAKA
[1] [Alon,  et  al,  1991]  Alon  N.,  Bar- Noy  A.,  Linial  N.,  dan  Peleg  D. 1991.  “A  Lower  bound  for  radio broadcast”. J.  Comput.  Syst.  Sci. , Vol. 43(2), pp. 290 – 298.
[2] [Chlamtac  dan  Kutten,  1985]
Chlamtac,I.  dan  Kutten,  S.  1985.
“On broadcasting in radio networks-problem  analysis  and protocol design”. IEEE
Transations  on  Communications , Vol. 33, pp. 1240 – 1246.
[3] [Darties,  et  al,  2008]  Darties,  B.,
Sylvain,  D.,  dan  Jerome,  P.  2008. Request  Satisfication  Problem  in Synchronous Radio Network. ADHOC-NOW'08: 7th
International  Conference  Ad-Hoc, Mobile  and  Wireless  Networks,
Sophia Antipolis, Nice, France.
[4] [Ephemides  dan  Truong,  1990] Ephemides  A.  dan  Truong  T. 1990.  “Scheduling  broadcast  in multihop  radio  networks”. IEEE Transactions  on  Communications , Vol. 38, pp. 456 – 461.
[5] [Garey  dan  Johnson,  1979]  Garey M.  R.  dan  Johnson  D.S.  1979. Computer  and  Intractability:  A guide  to  the  theory  of  NP- completeness. Freeman
[6] [Ramanathan  dan  Lloyd,  1993] Ramanathan,  S.  dan  Lloyd,  E.,
1993.  “Scheduling  boradcasts  in multi-hop radio
networks”.
IEEE/ACM Transactions on Networking , Vol. 1, pp. 166 – 172.
[7] [Ramanathan  dan  Lloyd,  1993] Ramanathan,  S.  dan  Lloyd,  E.
1993 . On  the  Complexity  of  Link Scheduling  in  Multi-hop  Radio Networks.  Dept. of Computer and Information  Sciences,  University of Delaware, USA.