## ALGORITMA PENJADWALAN REQUEST PADA JARINGAN RADIO SINKRON

## Nola Marina
Fakultas Teknologi Industri, Universitas Gunadarma Jl. Margonda Raya no. 100, Depok 16424, Jawa Barat nolamarina@staff.gunadarma.ac.id

## Abstrak
Teknologi  jaringan  nirkabel  bertujuan  untuk  memudahkan  pertukaran  informasi antar  perangkat.  Jaringan  Radio  Sinkron  (JRS)  adalah    jaringan  nirkabel  yang menghubungan  perangkat  (simpul)  untuk  bertukar  data  melalui  media  gelombang radio  dan  bekerja  secara  sinkron.    Penggunaan  medium  radio  pada  JRS menimbulkan masalah berupa mudahnya terjadi interferensi data. Untuk menjamin agar  semua  pengiriman  data  berhasil  diterima  oleh  simpul  tujuan,  diperlukan suatu  penjadwalan  pengiriman  data  (penjadwalan  request)  berdasarkan  kendala pada  model  interferensi.  Penjadwalan  request  dikatakan  baik  jika  menggunakan total  slot  waktu  minimal  dan  menjamin  tidak  terjadi  interferensi.  Urutan  request yang dijadwalkan dan teknik pengalokasian slot waktu pada setiap request sangat berpengaruh  terhadap  total  slot  waktu  yang  digunakan  hingga  semua  pengiriman data  selesai.  Pada  penelitian  ini  dipelajari  algoritma  penjadwalan  request  pada JRS topologi rantai yang menggunakan pendekatan greedy dalam mencari urutan request terbaik dan mengalokasikan slot waktu pada setiap request. Algoritma ini diimplementasikan pada 8 data dan diperoleh bahwa algoritma dengan pendekatan greedy  memberikan  total  slot  waktu  10.18  %  lebih  baik  dibandingkan    algoritma tanpa pengurutan (trivial).

## Kata Kunci: Jaringan, Penjadwalan, Radio, Rantai.

## REQUEST SCHEDULING ALGORITHM ON THE SYNCHRONOUS RADIO NETWORK

## Abstract
Wireless network technology aims to facilitate the exchange of information between devices.  Synchronous  Radio  Network  (SRN)  is  a  wireless  network  that  connects devices (nodes) to exchange data through radio wave media and work in sync. The use  of  radio  medium  in  SRN  cause  problems  in  the  form  of  easy  interference  of data.  To  ensure  that  all  data  request  are  successfully  received  by  the  destination node,  a  data  scheduling  (request  scheduling)  is  required  based  on  constraints  on the interference model. The sequence of request and time slot allocation technique on  each  request  greatly  affects  to  the  total  time  slot  used  until  all  data transmissions  are  completed.  In  this  study  we  studied  the  request  scheduling algorithm  on  SRN  chain  topology  using  the  greedy  approach  in  finding  the  best sequence  and allocating time slot on each  request.  This  algorithm is  implemented on 8 data and it is found that algorithm with greedy approach gives total slot time of 10.18% better than algorithm without sequencing (trivial).
Keywords: Chain, Network, Radio, Scheduling.

## PENDAHULUAN
Jaringan terdiri atas stasiun ( node ) dan  konektivitasnya  ( link ).  Jaringan nirkabel  adalah    jaringan  yang  meng- hubungan  perangkat-perangkat (simpul) untuk  bertukar  data  tanpa  menggunakan media  kabel,  melainkan  media  berupa gelombang  radio,  infra  merah  atau  ge- lombang  mikro.  Pemanfaatan  jaringan nirkabel  terutama  terdapat  pada  bidang telekomunikasi,  seperti    jaringan  paket radio,  jaringan  telepon  seluler,  jaringan area  lokal  nirkabel,  jaringan  satelit,  dan jaringan sensor.
Jaringan nirkabel yang mengguna- kan media gelombang radio elektromag- netik  disebut  jaringan  radio.  Jaringan radio  merupakan  kumpulan  dari  simpul pengirim dan penerima yang berkomuni- kasi  antara  satu  dengan  lainnya  melalui link multihop .  Transmisi  data  adalah pengiriman data dari simpul pengirim ke simpul  penerima.  Permintaan  transmisi suatu  data  dengan  rute  tertentu  disebut dengan request .
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 [1].
Pada  penelitian  ini  jaringan  radio diasumsikan  bersifat omnidirectional , sinkron,  dan half  duplex .  Beberapa  mo- del interferensi diberikan pada penelitian [1,  2,  3,  4].  Pada  penelitian  ini,  model interferensi  yang  digunakan  adalah  ber- dasarkan  [1]  dan  [4],  yaitu  interferensi terjadi  jika:  1)  suatu  simpul  mengirim lebih dari satu data dalam satu waktu, 2) suatu  simpul  mengirim  dan  menerima data  secara  bersamaan,  3)  terdapat  dua
atau  lebih  simpul  tetangga  yang  mengi- rimkan data dalam waktu yang sama.
Untuk  menjamin  agar  data  yang dikirimkan  berhasil  diterima  dengan baik  dan  untuk  mengetahui  perkiraan waktu  yang  dibutuhkan  hingga  data berhasil  diterima,  diperlukan  suatu  pen- jadwalan request (pengiriman  data). Penjadwalan request merupakan  masa- lah  yang  sangat  penting  dalam  jaringan radio.
Pada  penelitian  ini  didefinisikan masalah  penjadwalan  pada  Jaringan  Ra- dio  Sinkron  (JRS)  adalah  bagaimana pengalokasian slot waktu pada sejumlah request dengan rute masing-masing (dari simpul  sumber  ke  simpul  tujuan)  dalam suatu  jaringan  sedemikian  sehingga jadwal  valid, tidak ada konflik dan  total slot waktu yang digunakan minimal.
Penjadwalan  yang  baik  dipeng- aruhi  oleh  urutan  kumpulan request yang  dijadwalkan  dan  cara  mengalo- kasikan slot waktu untuk  setiap request .
Jika  urutan request dalam  proses  meng- alokasikan  slot  waktu  berbeda  maka total  slot  waktu  yang  digunakan  dapat berbeda    pula.    Berdasarkan  hal  ini,  sa- lah satu bagian dari masalah penjawalan request pada  JRS  adalah  bagaimana menemukan  urutan request yang  meng- hasilkan  penjadwalan  dengan    total  slot waktu  minimal  dan  bagaimana  teknik mengalokasikan  slot  waktu  pada  setiap request .  Pada  penelitian  ini  dipelajari algoritma penjadwalan request pada JRS topologi  rantai  yang  memperhatikan masalah tesebut.

## METODE PENELITIAN
Jaringan  radio  umumnya  direpre- sentasikan  dalam  bentuk  graf.  Pende- katan graf sangat penting dalam menye- lesaikan  masalah  penjadwalan request pada JRS dan menentukan kompleksitas masalahnya.
Suatu  jaringan  radio  direpresenta- sikan  oleh  graf  tak  berarah 𝐺 dimana
himpunan vertex 𝑉(𝐺) merepresentasi- kan  himpunan  simpul  dalam  jaringan. Sedangkann sisi 𝑒 = {𝑢, 𝑣} ∈ 𝐸(𝐺) menggambarkan bahwa simpul 𝑢 berkomunikasi  langsung  dengan  simpul 𝑣 dan sebaliknya.
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.  Path  merepresen- tasikan  jalan/rute  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  berkores- pondensi  dengan  suatu  slot  waktu,  yang artinya 𝑥 mengirim  data  dari 𝑟 ke  hop berikutnya selama slot waktu tersebut.
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  meng- irim 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 } ∉ 𝐸(𝐺) Total  waktu  suatu  penjadwalan adalah  jumlah  slot  waktu  yang  di- gunakan  agar  semua request sampai  ke simpul tujuan dinotasikan dengan:
max(𝑑) = max (r∈R,x∈V(G) 𝑑(𝑟, 𝑥)
yaitu slot waktu terbesar dari semua slot yang telah dialokasikan.
Masalah penjadwalan request ada- lah masalah optimasi yang termasuk NP- hard. NP- hard adalah  kelas  masalah yang  sulit  secara  komputasi  [5].  Algo- ritma greedy dikenal  sebagai  algoritma sederhana  yang  efektif  untuk  menye- lesaikan  masalah  optimasi.  Algoritma greedy adalah  algoritma  yang  meme- cahkan  masalah  langkah  per  langkah, pada  setiap  langkah  mengambil  pilihan yang  terbaik  yang  dapat  diperoleh  pada saat  itu  tanpa  memperhatikan  konse- kuensi  ke  depan  dan  berharap  bahwa dengan  memilih  optimum  lokal  pada setiap  langkah  akan  berakhir  dengan optimum global.
Pada  penelitian  ini  dibangun  al- goritma penjadwalan untuk penjadwalan request pada JRS topologi rantai  meng- gunakan pendekatan greedy. Pendekatan greedy digunakan  untuk  menentukan urutan request yang  dijadwalkan  dan juga  dalam  mengalokasikan  slot  waktu pada setiap request .

## HASIL DAN PEMBAHASAN
Diketahui  sebuah  jaringan  berupa sebuah graf tak berarah berbentuk rantai, dengan  C= [1,2, . . 𝑛] dan  kumpulan request 𝑅 = {𝑟 𝑖 = (𝑠 𝑖 , 𝑡 𝑖 )|1 ≤ 𝑖 ≤ 𝑚} . Banyak vertex adalah 𝑛 dan  banyak request adalah 𝑚 .  Model  eksperimental JRS  topologi  rantai  direpresentasikan dalam  bentuk  matriks 𝐷 𝑚𝑥𝑛−1 (𝑖, 𝑗) , dengan 𝑖 = request ke  - 𝑖 dan 𝑗 = edge (𝑗, 𝑗 + 1) , 𝑀 = [1,2, . . , 𝑚], 𝑁 = [1,2, . . , 𝑛] , 𝐷(𝑖, 𝑗) = slot waktu pengiriman request - 𝑖 ke  simpul  beri- kutnya.
Kendala  yang  harus  dipenuhi  oleh penjadwalan  diberikan  oleh  model  be- rikut:
a. Jadwal valid Secara  formal,  suatu  jadwal dikatakan  valid  jika  setiap request 𝑟 = (𝑥 0 , 𝑥 𝑘 ) dengan  fungsi  routing 𝑃 𝑟 = (𝑥 0 , 𝑥 1 , … . , 𝑥 𝑘 ) , memenuhi syarat: 𝑑(𝑟, 𝑥 0 ) < 𝑑(𝑟, 𝑥 1 ) < ⋯ . < 𝑑(𝑟, 𝑥 𝑘−1 ) < 𝑑(𝑟, 𝑥 𝑘−1 ) . Hal ini dapat direpresentasikan dengan syarat berikut pada matriks 𝐷(𝑖, 𝑗) :
1. 𝐷(𝑖, 𝑗) < 𝐷(𝑖, 𝑗 + 1) < ⋯ < 𝐷(𝑖, 𝑗 + 𝑘 − 1), ,  untuk 𝑖 dimana 𝑠 𝑖 < 𝑡 𝑖
2. 𝐷(𝑖, 𝑗) < 𝐷(𝑖, 𝑗 − 1) < ⋯ < 𝐷(𝑖, 𝑗 + 𝑘 − 1), untuk 𝑖 dengan 𝑠 𝑖 > 𝑡 𝑖
b. Jadwal bebas konflik Suatu  jadwal  dikatakan  bebas konflik  jika  untuk  setiap 𝑑(𝑟, 𝑥 𝑖 ) = 𝑑(𝑟 ′ , 𝑦 𝑗 ) dan 𝑟 ≠ 𝑟 ′ , memenuhi ketiga syarat berikut: 1. 𝑥 𝑖 ≠ 𝑦 𝑗 2. 𝑥 𝑖+1 ≠ 𝑦 𝑗 dan 𝑥 𝑖 ≠ 𝑦 𝑗+1
3. 𝑥 𝑖+1 ≠ 𝑦 𝑖+1 ∧  {𝑥 𝑖 , 𝑦 𝑗+1 } ∉ 𝐸(𝐺)  ∧   {𝑦 𝑗 , 𝑥 𝑖+1 } ∉ 𝐸(𝐺)
Ketiga syarat jadwal bebas konflik di atas dapat direpresentasikan dengan  syarat  berikut  pada  matriks 𝐷(𝑖, 𝑗) model eksperimental:
Untuk 𝑟 𝑘 yang searah dengan 𝑟 𝑖 , ∀𝑖, 𝑘 ≠ 𝑖 dengan 𝑖 ∈ 𝑀 dan 𝑘 ∈ 𝑁 .
1. 𝐷(𝑖, 𝑗) ≠ 𝐷(𝑘, 𝑗), syarat bebas konflik ke-1
2. 𝐷(𝑖, 𝑗) ≠ 𝐷(𝑘, 𝑗 + 1), syarat bebas konflik ke-2
3. 𝐷(𝑖, 𝑗) ≠ 𝐷(𝑘, 𝑗 + 2), syarat bebas konflik ke-3
Untuk 𝑟 𝑘 yang beda arah dengan 𝑟 𝑖 , ∀𝑖, 𝑘 ≠ 𝑖 dengan 𝑖 ∈ 𝑀 dan 𝑘 ∈ 𝑁 .
1. 𝐷(𝑖, 𝑗) ≠ 𝐷(𝑘, 𝑗 + 1), syarat bebas konflik ke-1
2. 𝐷(𝑖, 𝑗) ≠ 𝐷(𝑘, 𝑗), syarat bebas konflik ke-2
3. 𝐷(𝑖, 𝑗) ≠ 𝐷(𝑘, 𝑗 + 1), syarat bebas konflik ke-3 Syarat  diatas  dapat  digabungkan penulisannya  dan  menjadi  syarat bebas  konflik  pada  model  ekspe- rimental, yaitu:
1. 𝐷(𝑖, 𝑗) ≠ [𝐷(𝑘, 𝑗 − 2), 𝐷(𝑘, 𝑗 − 1), 𝐷(𝑘, 𝑗), 𝐷(𝑘, 𝑗 + 1), 𝐷(𝑘, 𝑗 + 2) ], untuk 𝑟 𝑘 yang searah dengan 𝑟 𝑖 , 𝑘 ≠ 𝑖 dan
2. 𝐷(𝑖, 𝑗) ≠ [𝐷(𝑘, 𝑗 − 1), 𝐷(𝑘, 𝑗), 𝐷(𝑘, 𝑗 + 1) ], untuk 𝑟 𝑘 yang tidak searah dengan 𝑟 𝑖 , 𝑘 ≠ 𝑖 , dengan 𝑖 ∈ 𝑀 dan 𝑘 ∈ 𝑁 .
Algoritma Penjadwalan dengan
Pendekatan Greedy
Algoritma  untuk  penjadwalan re- quest pada  JRS  topologi  rantai    meng- gunakan pendekatan greedy untuk mengalokasikan  slot  waktu  pada  setiap request dan  menentukan  urutan request yang dijadwalkan.
Cara  mengalokasikan  slot  waktu dengan  pendekatan greedy dilakukan dengan  menjadwalkan  satu request se- segera  mungkin  dengan  slot  waktu terkecil  yang available ,  terus-menerus hingga  sampai  ke  simpul  tujuan,  baru kemudian menjadwalkan request berikutnya.
Berikut  adalah  algoritma untuk mengalokasikan  slot  waktu  pada  setiap request dalam  penjadwalan request pada  JRS  topologi  rantai  dengan pendekatan greedy .  Jika  diketahui  A adalah  himpunan  slot  yang  terurut  naik dan bebas konflik jika dialokasikan pada kolom 𝑥 0 , maka:
1. Nilai  dari 𝐷(𝑖, 𝑥 0 ) dipilih  dari  slot yang  bebas  konflik  pertama  atau A( 1 ).
2. 𝐷(𝑖, 𝑥 𝑗 + 1) =  𝐷(𝑖, 𝑥 𝑗 ) + 1 ,
3. 𝐷 𝑖 _𝑡𝑒𝑚𝑝 = [𝐷(𝑖, 𝑥 0 ), 𝐷(𝑖, 𝑥 0 ) + 1, … . , 𝐷(𝑖, 𝑥 0 ) + 𝑘 − 1] .
4. Jika  pada 𝐷 𝑖 _𝑡𝑒𝑚𝑝 terdapat  slot waktu yang tidak bebas konflik, maka ulangi  penjadwalan 𝐷(𝑖, 𝑥 0 ) dengan
memilih  slot  yang  bebas  konflik kedua  atau  A( 2) .  Begitu  seterusnya
hingga  ditemukan 𝐷 𝑖 _𝑡𝑒𝑚𝑝 yang bebas konflik.
5. Maka, 𝐷 𝑖 = 𝐷 𝑖 _𝑡𝑒𝑚𝑝 Dengan  menerapkan  aturan  ini, maka  penjadwalan  pada  suatu  urutan request JRS  topologi  rantai  memenuhi syarat  valid  dan  bebas  konflik.    Se- dangkan  untuk  mencari  urutan request yang  dijadwalkan  yang  dapat    meng- hasilkan  jadwal  dengan  total  slot  waktu sekecil  mungkin,  pendekatan greedy yang  digunakan  adalah  dengan  cara mengurutkan  kumpulan request dengan urutan berdasarkan panjang path request dan nomor dari simpul sumber.
Deskripsi  Penjadwalan  Request  Pada JRS Topologi Rantai dengan Beberapa Jenis Pengurutan Request Masalah  1:  Diketahui  sebuah jaringan  dengan  topologi  rantai,  banyak vertex =7 dan banyak request = 3, yaitu 𝑟 1 = (1,4), 𝑟 2 = (3,6), 𝑑𝑎𝑛 𝑟 3 = (7,3) . Request 𝑟 1 dan 𝑟 2 adalah  searah, sedangkan request 𝑟 3 berbeda  arah dengan 𝑟 1 dan 𝑟 2 . Maka solusi sementara masalah  ini  menggunakan  algoritma greedy dengan  jenis  pengurutan:  1) terkiri dan terpanjang, 2) terpanjang dan terkiri,  dan  3)  terpendek  dan  terkanan diberikan pada Tabel 1.
Pada  Tabel  1  nomor  ke-3, menggunakan  algoritma greedy dengan pengurutan request yang  panjang path nya  terpendek  dan  nomor  simpul  yang terbesar  atau  terkanan  posisinya.  Urutan request diperoleh  dengan  cara  meng- urutkan request dari  yang  terpendek lebih  dulu.  Jika  terdapat  beberapa request yang  simpul  sumbernya  sama, urutkan request tersebut  dari  yang  ter- kanan  lebih  dulu.  Di  antara 𝑟 1 = (1,4),  𝑟 2 = (3,6), 𝑑𝑎𝑛 𝑟 3 = (7,3) urutan request yang terkiri dan terpanjang adalah 𝑟 2 , 𝑟 1 , 𝑟 3 . Penjadwalan  untuk 𝑟 2 , 𝑟 1 , 𝑟 3 dilakukan dengan  urutan  seperti  berikut: 𝐷 1 = [𝑑(𝑟 2 , 3), 𝑑(𝑟 2 , 4), 𝑑(𝑟 2 , 5)] , 𝐷 2 = [𝑑(𝑟 1 , 1), 𝑑(𝑟 1 , 2)𝑑(𝑟 1 , 3)] dan
berikutnya 𝐷 3 = [𝑑(𝑟 3 , 7), 𝑑(𝑟 3 , 6), 𝑑(𝑟 3 , 5), 𝑑(𝑟 3 , 4)] , dengan 𝑑(𝑟, 𝑥) adalah  slot  waktu  untuk mengirimkan request 𝑟 dari simpul 𝑥 ke simpul  berikutnya  dalam  fungsi  routing 𝑟 .    Pada  masalah  ini, request 𝑟 1 dan 𝑟 2 searah  sedangkan 𝑟 3 berbeda  arah dengan 𝑟 1 dan 𝑟 2 . Langkah penjadwalan:
1. Jadwal request 𝑟 2 : 𝐷 1 = [𝑑(𝑟 2 , 3), 𝑑(𝑟 2 , 4), 𝑑(𝑟 2 , 5)] = [1, 2, 3] 2. Jadwal request 𝑟 1 : 𝐷 2 = [𝑑(𝑟 1 , 1), 𝑑(𝑟 1 , 2)𝑑(𝑟 1 , 3)]
Untuk menentukan slot waktu 𝑑(𝑟 1 , 1), dimisalkan  A    adalah  him- punan  terurut  naik  dari  slot  waktu yang available jika  dialokasikan pada kolom 1 ( transmisi dari simpul 1 ke simpul 2). A=  [{  1,2,.., max(AssignedSlot)+ 1}- ConflictSlot ] A= [ {1,2,3,4}-{1}] = [2,3,4] Misalkan 𝑑(𝑟 1 , 1) = 𝐴(1) = 2 . Dengan  menggunakan 𝑑(𝑟, 𝑥 𝑗+1 ) = 𝑑(𝑟, 𝑥 𝑗+1 ) + 1 , diperoleh: 𝐷 2 _𝑡𝑒𝑚𝑝 = [𝑑(𝑟 1 , 1), 𝑑(𝑟 1 , 2)𝑑(𝑟 1 , 3) = [2,3,4] 𝐷 2 _𝑡𝑒𝑚𝑝[2,3,4] bebas  konflik sehingga 𝐷 2 =   𝐷 2𝑡𝑒𝑚𝑝 = [2,3,4] 3. Jadwal request 𝑟 3 : 𝐷 3 = [𝑑(𝑟 3 , 7), 𝑑(𝑟 3 , 6), 𝑑(𝑟 3 , 5), 𝑑(𝑟 3 , 4)] Untuk menentukan slot waktu 𝑑(𝑟 3 , 7), dimisalkan  A  adalah  him- punan  terurut  naik  dari  slot  waktu yang available untuk  dialokasikan pada  kolom  6  (transmisi  dari  simpul 7 ke simpul 6). A= [ {1,2,...,5}-{3}] = [1,2,4,5] Misalkan 𝑑(𝑟 3 , 7) = 𝐴(1) = 1 Dengan menggunakan 𝑑(𝑟, 𝑥 𝑗+1 ) = 𝑑(𝑟, 𝑥 𝑗+1 ) + 1 , diperoleh :
𝐷 3 _𝑡𝑒𝑚𝑝 = [𝑑(𝑟 3 , 7), 𝑑(𝑟 3 , 6), 𝑑(𝑟 3 , 5), 𝑑(𝑟 3 , 4)] = [1,2,3,4]
𝐷 3 _𝑡𝑒𝑚𝑝 = [1,2,3,4] konflik  pada  slot 2,3 dan 4 sehingga 𝐷 3 ≠   𝐷 3 _𝑡𝑒𝑚𝑝
Misalkan 𝑑(𝑟 3 , 7) = 𝐴(2) = 2 Dengan      menggunakan 𝑑(𝑟, 𝑥 𝑗+1 ) =
𝑑(𝑟, 𝑥 𝑗+1 ) + 1 , diperoleh : 𝐷 3 _𝑡𝑒𝑚𝑝 = [𝑑(𝑟 3 , 7), 𝑑(𝑟 3 , 6), 𝑑(𝑟 3 , 5), 𝑑(𝑟 3 , 4)] = [2,3,4,5]
𝐷 3 _𝑡𝑒𝑚𝑝 = [2,3,4,5] konflik  pada  slot
3,4 dan 5 sehingga 𝐷 3 ≠   𝐷 3 _𝑡𝑒𝑚𝑝
Misalkan 𝑑(𝑟 3 , 7) = 𝐴(3) = 4
Dengan menggunakan 𝑑(𝑟, 𝑥 𝑗+1 ) = 𝑑(𝑟, 𝑥 𝑗+1 ) + 1 , diperoleh : 𝐷 3 _𝑡𝑒𝑚𝑝 = [𝑑(𝑟 3 , 7), 𝑑(𝑟 3 , 6), 𝑑(𝑟 3 , 5), 𝑑(𝑟 3 , 4)] = [4,5,6,7]
𝐷 3 _𝑡𝑒𝑚𝑝 = [4,5,6,7] bebas konflik sehingga 𝐷 3 =   𝐷 3𝑡𝑒𝑚𝑝 = [4,5,6,7 ].
Tabel 1. Beberapa Solusi Sementara Masalah 1
1. Menggunakan Pengurutan request yang terkiri dan terpanjang Urutan request Ilustrasi Jadwal max (d) 𝑟 1 , 𝑟 2 , 𝑟 3 10 2. Menggunakan pengurutan request yang terpanjang dan terkiri Urutan request Ilustrasi Jadwal max (d) 𝑟 3 , 𝑟 1 , 𝑟 2
9
3. Menggunakan pengurutan request yang terpendek dan terkanan Urutan request Ilustrasi Jadwal max (d) 𝑟 2 , 𝑟 1 , 𝑟 3
7 𝑟 3 :                                                 7                  6                 5                    4
𝑟 2 :                                                   1                 2                3 𝑟 1 :              2 3             4 1 2 3 4 5                 6                   7
𝑟 2 :                                                   7                 8                9
𝑟 1 :              4 5             6
1 2 3 4 5                 6                   7 𝑟 3 :                                                    4 3 2                  1
𝑟 2 :                                                  4                 5               6
𝑟 1 :              1
2             3 1 2 3 4 5                 6                   7 𝑟 3 :                                                  10               9                8                  7
Dari  penjadwalan  ini  diperoleh total  slot  waktu    7.    Dengan  cara  yang sama,    algoritma greedy dengan  peng- urutan  terkiri  dan  terpanjang  meng- hasilkan  urutan request 𝑟 1 , 𝑟 2 , 𝑟 3 dan total  slot  waktu  10.  Kemudian,    algo- ritma greedy dengan pengurutan terpanjang  dan  terkiri  menghasilkan urutan request 𝑟 3 , 𝑟 1 , 𝑟 2 dan  total  slot waktu  9.  Solusi  terbaik  dari  3  solusi sementara  adalah  7  dengan  urutan re- quest terpendek dan terkanan. Untuk  selanjutnya  dipelajari  22
jenis  pengurutan  dengan  pendekatan
greedy dalam  mengalokasikan  slot waktu  untuk  setiap request pada penjadwalan request JRS topologi rantai.
Implementasi Algoritma Greedy
untuk data DawnC01
Data  DawnC01  terdiri  atas  kum- pulan request sebanyak  10 request (m) pada    JRS  topologi  rantai  yang  terdiri atas 10 node (n), dengan simpul sumber (s)  dan  simpul  tujuan  (t)  untuk  setiap request diberikan oleh Tabel 2.
Tabel 2.  Kumpulan Request DawnC01
Kumpulan request No s t 1 9 2 2 8 5 3 7 4 4 5 8 5 10 9 6 7 10 7 7 8 8 9 3 9 2 9 10 5 8
Dari hasil dari penjadwalan meng- gunakan  algoritma  greedy  untuk  data DawanC01  tanpa  pengurutan  (trivial) diperoleh total slot waktu  26.
Sedangkan  implementasi  algo- ritma greedy dengan 22 jenis pengurutan untuk  data  DawnC01  menghasilkan  22 solusi  sementara,  dengan  urutan request dan  total  slot  waktu  untuk  setiap  jenis pengurutan dapat dilihat pada Tabel 3. Dari  Tabel  3  dapat  disimpulkan bahwa  solusi  algoritma greedy untuk data  DawnC01  adalah  solusi  sementara yang  menghasilkan  total  slot  waktu terkecil,  yaitu  21.  Pada  kasus  ini  solusi yang  menghasilkan  total  slot  waktu  21,
dipenuhi oleh jenis pengurutan ke-4, 10, 13,  dan  19.    Pada  Tabel  4  diberikan solusi  algoritma greedy dengan  peng- urutan  jenis  ke-19,  yaitu request ter- kanan  dan  terpanjang  untuk  data DawnC01  berupa  urutan request yang dijadwalkan,  penjadwalan  dan  total  slot waktu.
Pada  Tabel  5  diberikan  perban- dingan  hasil  dari  penjadwalan  menggu- nakan algoritma tanpa pengurutan request (trivial)  dan  algoritma  dengan pengurutan ( greedy ) untuk beberapa data dengan  banyak  simpul  (n)  dan  banyak request (m) yang bervariasi.
Tabel 3. Urutan Request dan Total Slot Waktu dari 22 Solusi Sementara Algoritma Greedy untuk Data DawnC01
Jenis pengurutan greedy Urutan Request untuk 22 jenis pengurutan Total slot waktu 1 9 4 10 6 7 5 3 2 8 1 25 2 1 8 3 2 5 7 4 10 6 9 23 3 9 4 10 3 7 6 2 1 8 5 24 4 5 1 8 2 3 7 6 4 10 9 21 5 9 6 4 10 7 5 2 3 8 1 27 6 1 8 2 3 5 7 6 4 10 9 23 7 5 8 1 2 6 7 3 4 10 9 24 8 9 4 10 3 7 6 2 1 8 5 24 9 9 4 10 3 6 7 2 1 8 5 25 10 5 1 8 2 3 6 7 4 10 9 21 11 9 4 6 10 7 5 2 3 8 1 26 12 1 8 2 3 5 7 4 6 10 9 23 13 9 1 8 4 10 3 6 2 7 5 21 14 7 5 4 10 3 6 2 8 9 1 32 15 9 4 10 7 3 6 2 8 1 5 25 16 5 8 1 2 7 3 6 4 10 9 24 17 1 9 8 2 3 6 4 10 5 7 22 18 5 7 2 3 6 4 10 8 1 9 30 19 5 1 8 2 3 6 7 4 10 9 21 20 9 4 10 7 3 6 2 8 1 5 25 21 1 9 8 2 3 4 6 10 5 7 22 22 5 7 2 3 4 6 10 8 1 9 30
Tabel 4. Solusi Penjadwalan DawnC01
Tabel 5.  Total Slot Waktu Hasil Algoritma Trivial dan Algoritma Greedy untuk Data DawnC01- DawnC08

## SIMPULAN DAN SARAN
Pada  penelitian  ini  telah  dibuat algoritma penjadwalan yang dapat menyelesaikan  dua  bagian  masalah penjadwalan  pada  JRS  topologi  rantai, yaitu  bagaimana  menentukan  urutan request dalam  mengelokasikan  slot waktu  dan  bagaimana  teknik  meng- alokasikan  slot  waktu  pada  setiap re- quest yang  dapat  menghasilkan  penjad- walan  dengan  total  slot  waktu  minimal. Untuk  8  data  (DawnC01  –  DawnC08) diperoleh bahwa algoritma greedy menghasilkan  jadwal  yang  lebih  baik (total  slot  waktu  lebih  sedikit)  daripada algoritma  tanpa  pengurutan request (trivial),  dengan  peningkatan  rata-rata 10,18 %.

## DAFTAR PUSTAKA
[1] [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.
[2] [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, No. 2, pp. 290 – 298.
[3] [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.
[4] [Ramanathan  dan  Lloyd,  1993]
Ramanathan,  S.  dan  Lloyd,  E., 1993.  “Scheduling  Algorithm  fo Multihop Radio Networks”. IEEE/ACM Transactions on Networking , Vol. 1, pp. 166 – 177.
[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.
n m Data Total Slot Waktu Trivial Greedy 10 10 DawnC01 26 21 10 20 DawnC02 35 32 10 50 DawnC03 90 71 20 10 DawnC04 35 21 20 20 DawnC05 43 34 30 20 DawnC06 65 47 50 30 DawnC07 149 92 100 20 DawnC08 206 124