Abstrak — Interferensi frekuensi radio  merupakan permasalahan umum  yang  di  hadapi  oleh  instansi  pemerintah  dalam pengelolaan frekuensi radio FM. Interferensi menjadi kelemahan dalam  pengelolaan  frekuensi  radio  FM  dimana  permasalahan yang  terjadi  adalah  adanya ‘ tubrukan ’ pada  dua  stasiun  radio dengan  frekuensi  yang  sama.  Interferensi  memberikan  dampak negatif  yang  signifikan  terhadap  kinerja  jaringan  nirkabel. Akibatnya  penerimaan  suara  pada  stasiun  radio  FM  di  Jawa Timur yang mengalami interferensi menghasilkan kualitas suara yang  buruk.  Pada  penelitian  ini,  dilakukan  penggunaan algoritma welch powell dalam menyelesaikan masalah interferensi  dan  mengoptimalkan  pengalokasian  frekuensi  radio FM.  Hasil  dari  penelitian  ini  menunjukan  Algoritma  Welch Powell dapat menyelesaikan masalah interferensi dan mengoptimalkan  pengalokasian  frekuensi  di  Jawa  Timur  tanpa adanya frekuensi yang bertubrukan, dengan  menggunakan  data real stasiun radio FM yang ada di Jawa Timur, Algoritma Welch Powell  menghasilkan  pengalokasian  frekuensi  yang  lebih optimal.  Karena  jumlah  frekuensi  yang  dihasilkan  dengan algoritma  Welch  Powell  lebih  minimum  dibandingkan  jumlah frekuensi yang digunakan data real.
Kata  Kunci — Interferensi,  Noise,  Pewarnaan  Graf,  Algoritma Welch Powell.

## I. PENDAHULUAN
ADIO  adalah  salah  satu  media  informasi  yang  masih digunakan  sampai  saat  ini.  Di  provinsi  jawa  timur terdapat  stasiun  berjumlah  115  radio  FM  [1].  Terdapat  radio yang  mempunyai  frekuensi  sama  namun  berbeda  kota,  yaitu radio  RRI  Surabaya  dan  radio  Purnama  Cipta  Prawira  di Blitar.  Kedua  radio  tersebut  mempunyai  frekuensi  yang  sama yaitu  pada  frekuensi  95.30  dan  kedua  radio  tersebut  berjarak 100  Km.  Hal  tersebut  dapat  mengakibatkan  interferensi  pada radius yang bertubrukan. Jangkauan frekuensi radio FM tidak sejauh  frekuensi  radio  AM.  Jangkauan  frekuensi  radio  AM mencapai  120  Km  dikarenakan  bantuan  oleh  lapisan  ionosfer (berada  diantara  80  Km  sampai  100  Km  dari  permukaan bumi).  Namun  frekuensi  radio  FM  dapat  mencapai  jarak maksimum  Coverage  Area  60  Km  sampai  70  Km  [2]. Terdapat  gelombang  frekuensi  FM  yang  dihantarkan  melalui lapisan  troposfer,  sehingga  siaran  FM  bisa  diterima  sampai jarak  yang  jauh  [3].  Dengan  jarak  Coverage  Area  yang mencapai  60  Km.  Terdapat  kemungkinan  terjadinya interferensi  pada  daerah  tertentu.  Interferensi  adalah  sebuah emisi  koheren  yang  memiliki  konten  spektral  relatif  sempit,
misalnya  radio  emisi  dari  pemancar  lain  di  sekitar  frekuensi yang  sama  dan  menghambat  penerimaan  sinyal.  Definisi  dari spektral  relatif  sempit  adalah  terbatasnya  panjang  spektrum frekuensi pada frekuensi FM.
Spektrum  frekuensi  radio  adalah  susunan  pita  frekuensi radio  yang  mempunyai  frekuensi  lebih  kecil  dari  3000  GHz. Spektrum  frekuensi  radio  merambat  dan  terdapat  dalam dirgantara  (ruang  udara  dan  antariksa).  Spektrum  frekuensi radio  merupakan  sumber  daya  alam  terbatas,  namun  saat  ini peminatnya semakin meningkat sementara jumlah ketersediaan  spektrum  tidak  bertambah.  Spektrum  frekuensi radio  digunakan  untuk  pemancar  frekuensi  radio.  Dalam  hal penggunaan  spektrum  frekuensi  radio  perlu  dilakukan koordinasi  antar  kota.  Interferensi  memberikan  dampak negatif  yang  signifikan  terhadap  kinerja  jaringan  nirkabel. Dalam  hal  ini  penulis  menganalisis  masalah  interferensi  dari sudut  pandang  teori  graf  dengan  menggunakan  metode pewarnaan graf.
Optimalisasi  frekuensi  radio  adalah  mengoptimalkan pengalokasian  frekuensi  radio  FM  sehingga  pengguna pemancar  frekuensi  sebanyak-banyaknya,  dengan  jumlah pemakaian  alokasi  frekuensi  sesedikit  mungkin.  Optimalisasi frekuensi  radio  bertujuan  menghindari  interferensi  frekuensi radio.  Permasalahan  interferensi  radio  di  jawa  timur  adalah terdapat  stasiun  radio  FM  yang  mempunyai  frekuensi  yang sama  dan  menyebabkan  terjadinya  tubrukan  radius  pancaran frekuensi  radio  di  daerah  tersebut.  Dampak  dari  interferensi tersebut  yaitu  dapat  mengakibatkan noise pada  frekuensi radio. Noise adalah  sinyal-sinyal  yang  tidak  diinginkan  yang selalu ada dalam suatu sistem transmisi. Noise mengakibatkan gangguan  kualitas  sinyal  untuk  proses  penerimaan  dan pengiriman  suara  [3].  Metode  pewarnaan  graf  dapat diimplementasikan  ke  dalam  permasalahan  interferensi frekuensi  radio  di  jawa  timur.  Dengan  mensimulasikan pengguna  radio  yang  relatif  terhadap  posisi  stasiun  radio diasumsikan  sebagai  node  dan  interferensi  yang  terjadi diasumsikan  menjadi  lintasan.  Pada  penelitian  ini  penulis menggunakan  algoritma  welch  powell  untuk  optimalisasi frekuensi radio agar tidak ada frekuensi sama yang mengalami interferensi. Algoritma welch powell adalah teknik pewarnaan simpul, dimana simpul yang bertetangga akan memiliki warna yang  berbeda.  Warna  di  sini  adalah  gambaran  dari  ferkuensi yang dimiliki suatu pemancar.

## Implementasi Metode Pewarnaan Graf Menggunakan Algoritma Welch Powell untuk Simulasi Penerapan Frekuensi Radio di Jawa Timur
Fadhlan Septianto Eka Putra, Darmaji, dan Soetrisno Departemen Matematika, Fakultas Matematka dan Ilmu Pengetahuan Alam, Institut Teknologi Sepuluh Nopember (ITS)
e-mail : soetrisno@matematika.its.ac.id
R
Pewarnaan  graf  adalah  pemberian  warna  terhadap  simpul sedemikian  sehingga  dua  simpul  yang  berdampingan mempunyai  warna  yang  berlainan.  Jumlah  minimum  warna yang  dibutuhkan  disebut  bilangan  khromatik  dari  graf  G, dimana khromatik dari graf G adalah jumlah warna minimum yang  diperlukan  untuk  mewarnai  graf  G,  dan  dilambangkan dengan  χ(G).  Dengan  menggunakan  metode  pewarnaan  graf yang dapat diterapkan dalam permasalahan interferensi sinyal radio,  akan  menghindari  interferensi  yang  terjadi  di  spektrum frekuensi radio. FM
Permasalahan interferensi tidak hanya terjadi pada jaringan nirkabel  seperti  telepon  seluler,  namun  juga  terjadi  pada jaringan  nirkabel  siaran  radio.  Maaly  A.  Hassan  dan  Andrew Chickadel  pada  tahun  2011  melakukan  penelitian  yang berjudul A  Review  of  Interference  Reduction  in  Wireless Networks  Using  Graph  Coloring  Methods .  Pada  penelitian tersebut  dibahas  mengenai  Interferensi  yang  terjadi  pada jaringan  nirkabel.  Penggunaan  beberapa  metode  seperti metode  weighted  coloring,  metode  dynamic  channel assignment,  metode  location-oblivious  untuk  menyelesaian permasalahan  interferensi.  Dalam  pembahasan  penelitian tersebut dijelaskan bahwa metode dynamic channel assignment  adalah  metode  yang  optimal  dalam  pembahasan penelitian  tersebut.  Selanjutnya,  pada  tahun  2010,  telah dilakukan  penelitian  oleh  Margaretha  Siahaan  yang  berjudul Studi  Pewarnaan  Graf  pada Radio  Frequency  Assignment Problem . Pada penelitian ini  dibahas  mengenai  sebuah  model frequency assignment problem untuk mengoptimalisasi bidang frekuensi dengan  menggunakan pewarnaan simpul dan teknik kromatik  polynomial  dengan  mencari  jumlah  warna  paling sedikit untuk pewarnaan graf. Frequency Assignment Problem pada  dasarnya  merupakan  cara  untuk  mencari  jarak  terkecil antara dua buah pemancar agar pemancar tersebut tidak saling berinterferensi  dan  dapat  memancarkan  gelombang  melalui saluran-saluran  yang  tersedia.  Frequency  assignment  problem pertama  kali  muncul  di  tahun  1960.  Perkembangan  dari layanan  nirkabel  seperti  telepon  selular  pertama  memulai proses kelangkaan frekuensi dalam spectrum radio. Frequency Assignment  Problem  yang  juga  dikenal  sebagai  channel assignment problem, berkembang dengan cukup cepat. Teknik pewarnaan  graf  dapat  diimplementasikan  untuk  menemukan nomor  warna  yang  paling  kecil  yang  menghubungkan  kedua pemancar yang direpresentasikan sebagai node.
Berdasarkan  penelitian  diatas,  penerapan  pewarnaan  graf sudah  banyak  digunakan  dalam  kehidupan  sehari-hari.  Oleh karena  itu,  pada  Tugas  Akhir  ini  akan  digunakan  pewarnaan graf  menggunakan  Algoritma Welch  Powell untuk  simulasi interferensi  frekuensi  radio  di  Jawa  Timur.  Sehingga  dapat meminimalisasikan interferensi frekuensi radio di Jawa Timur.

## II. TINJAUAN PUSTAKA

## A. Pewarnaan Graf
Pewarnaan  graf  merupakan  pemberian  warna  pada  simpul graf sedemikian sehingga dua simpul bertetangga mempunyai warna  yang  berbeda.  Ada  3  macam  pewarnaan  graf,  yaitu pewarnaan  simpul,  pewarnaan  sisi,  dan  pewarnaan  wilayah.
Berikut  akan  dibahas  pewarnaan  simpul  saja.  Pewarnaan simpul  adalah  memberi  warna  pada  simpul-simpul  di  dalam graf  sedemikian  sehingga  setiap  dua  simpul  bertetangga mempunyai  warna  yang  berbeda.  Di  dalam  persoalan pewarnaan  graf,  kita  tidak  hanya  sekedar  mewarnai  simpul- simpul  dengan  warna  berbeda  dari  warna  simpul  tetangganya saja,  namum  kita  juga  menginginkan  jumlah  macam  warna yang  digunakan  sesedikit  mungkin.  Kita  dapat  memberikan sembarang warna pada simpul-simpul asalkan berbeda dengan simpul-simpul tetangganya.

## B. Algoritma Welch Powell
Algoritma Welch  Powell merupakan  salah  satu  algoritma pewarnaan  graf  yang  melakukan  pewarnaan  berdasarkan derajat  tertinggi  dari  simpul-simpulnya  atau  disebut  largest degree  ordering  (ldo).  Algoritma  ini  dapat  digunakan  untuk mewarnai sebuah graf secara efisien. Akan tetapi algoritma ini tidak  selalu  memberikan  jumlah  minimum  warna  yang diperlukan  untuk  mewarnai.  Walaupun  demikian,  algoritma ini  praktis  untuk  digunakan  dalam  mewarnai  simpul  graf. Algoritma Welch Powell ini dinyatakan sebagai berikut : 1. Urutkan  simpul-simpul  dari  graf  G  dalam  derajat  yang menurun  (urutan  seperti  ini  tidak  mungkin  tidak  unik karena beberapa simpul mungkin berderajat sama).
2. Gunakan  satu  warna  untuk  mewarnai  simpul  pertama (yang  mempunyai  derajat  tertinggi)  dan  simpul-simpul lain (dalam  urutan  yang berurut)  yang tidak bertetangga dengan simpul pertama ini.
3. Mulai lagi dengan simpul derajat tertinggi berikutnya di dalam  daftar  terurut  yang  belum  diwarnai  dan  ulangi proses  pewarnaan  simpul  dengan  menggunakan  warna kedua.
4. Ulangi  penambahan  warna-warna  sampai  semua  simpul telah diwarnai.

## C. Bilangan Kromatik
Jumlah  warna  minimum  yang  dapat  digunakan  untuk mewarnai  simpul  yang  ada  pada  graf 𝐺 disebut bilangan kromatik ,  disimbolkan  dengan 𝜒 𝐺 .  Suatu  graf  G  yang mempunyai  bilangan  kromatik 𝑘 dilambangkan  dengan 𝜒 𝐺 = 𝑘 , sehingga graf berikut ini memiliki 𝜒 𝐺 = .
Beberapa  graf  tertentu  dapat  langsung  ditentukan  bilangan kromatiknya, yaitu : a. Graf  kosong 𝐺 = 𝑁 memiliki 𝜒 𝐺 = ,  karena  semua simpul tidak terhubung, jadi untuk mewarnai semua simpul cukup dibutuhkan satu warna saja. b. Graf  lengkap 𝐺 = 𝐾 memiliki 𝜒 𝐺 = 𝑛 ,  karena  smeua simpul saling terhubung sehingga diperlukan 𝑛 buah warna. c. Graf  bipartit 𝐺 = 𝐾 , memiliki 𝜒 𝐺 = ,  satu  untuk simpul-simpul  di  himpunan 𝑉 dan  satu  lagi  untuk  simpul- simpul di 𝑉 . d. Graf  lingkaran 𝐺 dengan 𝑛 ganjil  memiliki 𝜒 𝐺 = , sedangkan jika 𝑛 genap maka 𝜒 𝐺 = . e. Sembarang pohon T memiliki 𝜒 𝑇 =
f. Untuk  graf-graf  yang  lain  tidak  dapat  dinyatakan  secara umum bilangan kromatiknya.

## D. Spektrum Frekuensi Radio
Spektrum  frekuensi  radio  adalah  susunan  pita  frekuensi radio  yang  mempunyai  frekuensi  lebih  kecil  dari  3000  GHz sebagai  satuan  getaran  gelombang  elektromagnetik  yang merambat  dan  terdapat  dalam  dirgantara  (ruang  udara  dan antariksa).  Pengalokasian  Spektrum  Frekuensi  Radio  di Indonesia mengacu kepada alokasi frekuensi radio internasional  untuk  region  3.  Region  3  (wilayah  3)  sesuai dengan  peraturan  radio  yang  ditetapkan  oleh  International Telecommunication
Union (ITU) atau Himpunan Telekomunisai  Internasional.  Penepatan  jalur  Spektrum frekuensi  radio  ini  bertujuan  untuk  menghindari  terjadinya interferensi  (Interference)  dan  untuk  menetapkan  protokol demi keserasian antara pemancar dan penerima.

## E. Frekuensi Radio FM
Frekuensi  radio  FM  adalah  proses  mengirimkan  sinyal Frekuensi  rendah  dengan  menggunakan  FM  (Frequency Modulation).  Metode  modulasi  frekuensi  memvariasikan frekuensi  untuk  mengantarkan  gelombang  frekuensi  radio. Frekuensi  radio  FM  pertama  kali  ditemukan  oleh  Edwin Howard  Amstrong  pada  tahun  1936,  dimana  frekuensi  radio FM  memiliki  kelebihan  tahan  terhadap  noise  dibandingkan Frekuensi AM. Jarak tempuh frekuensi radio FM mencapai 60
Km  dari  pusat  pemancar  sinyal.  Jarak  tempuh  frekuensi  FM lebih  kecil  dibandingkan  frekuensi  AM.  Frekuensi  radio  AM dapat  mencapai  jarak  100  Km  dari  pusat  pemancar  sinyal, dikarenakan  sinyal  frekuensi  radio  AM  dipantulkan  oleh ionosfer [8]. Interval frekuensi radio FM adalah 15 Hz sampai 50 Hz. Frekuensi radio FM dialokasiskan pada range frekuensi 88  MHz  sampai  108  MHz.  Range  frekuensi  tersebut  relatif baik terhadap gangguan atmosfir maupun cuaca.
Gambar 3. Frekuensi Radio FM.

## III. HASIL DAN PEMBAHASAN
Interferensi  merupakan  permasalahan  yang  menjadi tinjauan  dalam  penelitian  ini.  Interferensi  disebabkan  oleh radio  yang  memiliki  frekuensi  sama  saling  berdekatan, mengakibatkan  dampak  negatif  yang  signifikan  terhadap kinerja  jaringan  nirkabel.  Meminalisasi  interferensi  frekuensi radio  adalah  mengurangi  terjadinya  interferensi  frekuensi radio  pada  frekuensi  yang  sama.  Minimalisasi  interferensi frekuensi radio bertujuan menghilangkan interferensi frekuensi radio pada radius  yang bertubrukan, sehingga dapat mengurangi  interferensi  frekuensi  radio  di  Jawa  Timur. Algoritma  Welch  Powell  yang  digunakan  dalam  pewarnaan graf  ternyata  dapat  diterapkan  pada  masalah  interferensi penggunaan frekuensi radio. Misalkan pemancar dengan suatu frekuensi  tertentu  adalah  suatu  simpul.  Pemancar  yang memungkinkan akan berinterferensi dihubungkan dengan sisi, kita sebut kedua simpul yang dihubungkan sisi sebagai simpul yang  bertetangga.  Sesuai  dengan  algoritma  Welch  Powell, simpul  yang  bertetangga  akan  memiliki  warna  yang  berbeda. Warna  di  sini  adalah  gambaran  dari  ferkuensi  yang  dimiliki suatu pemancar. Artinya, jika warna pemancar (simpul) adalah sama, maka pemancar tersebut seharusnya memiliki frekuensi radio  yang  sama.  Jika  pengaturan  penggunaan  frekuensi seperti ini digunakan, maka akan tercapai tujuan mengoptimalkan  frekuensi  radio,  dengan  mengakomodasikan pengguna frekuensi radio sebanyak-banyaknya dengan jumlah frekuensi yang digunakan sesedikit mungkin.

## A. Pengujian Program dengan Case Data Real
Berikut ini akan dijelaskan pengujian perangkat lunak, user akan  menguji  beberapa  poin  permasalahan  yang  dapat diterapkan  di  dalam  program.  Hasil  implementasi  pengujian tersebut  akan  menjadi  kajian  dalam  pengembangan  dan pemeliharaan  perangkat  lunak.  Program  akan  diuji  dengan  4
Gambar 2. Graf yang memiliki 𝝌 𝑮 = 𝟑 .
case. Dimana setiap case memiliki hasil inputan yang berbeda beda.  Case  1  adalah  setiap  inputan  posisi  stasiun  radio  FM tidak  mengalami  interferensi.  Case  2  adalah  setiap  inputan posisi stasiun radio FM mengalami interferensi. Case 3 adalah terdapat  beberapa  stasiun  radio  yang  mengalami  interferensi. Case 4 adalah case menggunakan data real posisi stasiun radio FM di Jawa Timur.

## B. Pengujian dengan Case Data Real
Berdasarkan penjelasan pengujian dengan Kasus data real, maka posisi stasiun radio yang dipilih pemancar stasiun radio FM  di  Jawa  Timur.  Pada  input  posisi  stasiun  radio  node berwarna  hitam,  diasumsikan  bahwa  pada  tahap  input  setiap stasiun  radio  memiliki  frekuensi  yang  sama.  Sehingga  hasil input ditunjukan pada Gambar 4.
Gambar 4. Input Case Data Real.
Berdasarkan  hasil  input,  selanjutnya  input  tersebut  akan diperoleh  dan  diproses  menjadi  sebuah  graf.  Pemberian  input posisi stasiun radio FM kasus data real menghasilkan beberapa node  yang  memiliki  lintasan  dengan  node  yang  lain.  Hal tersebut  dikarenakan  beberapa  node  mengalami  interferensi. Dan hasil represesntasi graf dapat dilihat pada Gambar 5.
Gambar 5. Representasi Graf Case Data Real.
Berdasarkan  hasil  representasi  graf,  selanjutnya  input tersebut  akan  diolah  dan  diproses  menjadi  hasil  pewarnaan graf. Pemberian input posisi stasiun radio FM kasus data real menghasilkan  terdapat  node  memiliki  lintasan  dengan  node yang lain. Hal tersebut dikarenakan beberapa node mengalami interferensi.  Maka  hasil  pewarnaan  graf  pada  kasus  data  real memiliki n warna, hal tersebut menunjukan bahwa pada Kasus
data  real  memiliki  warna  yang  bervariasi.  Dan  hasil pewarnaan graf dapat dilihat pada Gambar 6.
Gambar 6. Pewarnaan Graf Case Data Real.
Berdasarkan  hasil  pewarnaan  graf,  selanjutnya  input tersebut  akan  diolah  dan  diproses  menjadi  hasil  rekomendasi frekuensi  radio  FM.  Pemberian  input  posisi  stasiun  radio  FM kasus  data  real  menghasilkan  beberapa  stasiun  radio  FM memiliki  frekuensi  yang  berbeda-beda.  Hal  tersebut dikarenakan  beberapa  node  mengalami  interferensi  dan beberapa  node  tidak  mengalami  interferensi.  Maka  hasil rekomendasi  frekuensi  pada  kasus  data  real  memiliki  33 frekuensi.  Rekomendasi  frekuensi  dikatakan  optimum  karena dengan  jumlah  stasiun  pemancar  yang  banyak  hanya memerlukan  beberapa  alokasi  frekuensi  untuk  dapat diterapkan.  Hasil  rekomendasi  frekuensi  menggunakan perangkat  lunak  menunjukan  bahwa  jumlah  frekuensi  yang digunakan  sebanyak 33 frekuensi berbeda dan lebih optimum dibandingkan  data  real  yang  berjumlah  54  frekuensi  berbeda. Hasil rekomendasi frekuensi dapat dilihat pada Gambar 7 .
Gambar 7. Hasil Rekomendasi Frekuensi Case Data Real.

## IV. KESIMPULAN/RINGKASAN
Berdasarkan  analisis  terhadap  hasil  pengujian  program, maka dapat diambil kesimpulan sebagai  berikut :
1. Metode  pewarnaan  graf  telah  berhasil  diterapkan  untuk menghindari  interferensi  frekuensi  radio  FM  di  Jawa Timur.
2. Algoritma Welch Powell dapat mengoptimalkan pemakaian frekuensi radio FM yang relatif terhadap posisi
dan coverage  area stasiun  radio  FM  tanpa  adanya interferensi .. 3. Untuk  pengujian  pada  kasus  1  dimana  semua  pengguna tidak  mengalami  interferensi,  Kasus  2  dimana  semua pengguna mengalami, Kasus 3 dimana beberapa pengguna mengalami  interferensi,  menunjukan  bahwa  perangkat lunak dapat digunakan untuk mengakomodasi stasiun radio sebanyak-banyaknya,  dengan  jumlah  frekuensi  seminimal mungkin.
4. Untuk  pengujian  pada  kasus  data  real  dimana  data  yang digunakan adalah data asli tahun 2006 menunjukan bahwa
perangkat  lunak  dapat  menghasilkan  pengalokasian frekuensi  yang  lebih  optimal  dibandingkan  data  frekuensi yang digunakan pada tahun 2006

## DAFTAR PUSTAKA
[1]  Ditjen  Postel, “ Master  Plan  Penetapan  Frekuensi  Kanal  Radio  Siaran Fm, ” Jakarta, 2016.
[2]  A. . . Hassan and A. Chickade, “ A Review Of  Interference Reduction In Wireless Networks Using Graph Coloring Methods, ” Villanova, 2011. [3]  Z.  Ning  and  Y.  Yao, “ Interference-Aware  Spectrum  Sensing Mechanismsin Cognitive Radio Networks, ” Shenyang.