## PERBANDINGAN ALGORITMA DSATUR DAN ALGORITMA VERTEX MERGE UNTUK MENENTUKAN CHANNEL WLAN

## Handrizal
Dosen STIKOM Tunas Bangsa Pematangsiantar, Sumatera Utara-Indonesia Jalan Sudirman Blok A No. 1, 2, 3  Pematangsiantar
E-mail : Handrizal_tanjung@yahoo.com

## Abstrak
Seiring  dengan  perkembangan  teknologi  maka  kebutuhan  akan  ketersedian  akses internet  melalui  wireless  lokal  area  network  (WLAN)  akan  ikut  meningkat.  Semakin bertambahnya jumlah WLAN maka akan mempengaruhi kualitas dari WLAN itu sendiri, untuk itu diperlukan cara mengatasi masalah tersebut. Algoritma Dsatur dan algoritma Vertex  Merge  adalah  dua  buah  algoritma  yang  dapat  digunakan  untuk  membantu masalah  diatas.  Kedua  algoritma  ini  bekerja  berdasarkan  konsep  pewarnaan  graf, setiap  vertex  dalam  graf  dianalogikan  sebagai  akses  point  dalam  WLAN.  Hasil penelitian  ini  menunjukkan  bahwa  Algoritma  Vertex  Merge  bekerja  lebih  baik dibandingkan  dengan  algoritma  Dsatur  dengan  menghasilkan  lebih  sedikit  jumlah channel yang diperlukan.
Kata kunci : Dsatur; vertex merge; channel; WLAN

## Pendahuluan
Kebutuhan akan jaringan wireless sekarang  ini  terus  meningkat,  baik dirumah,  kantor,  bahkan  tempat-tempat umum  seperti  restoran,  hotel,  dan  dan bahkan  pusat-pusat  kota  yang  telah banyak  dilengkapi  dengan  Akses  Point (AP)  untuk  menawarkan  konektivitas wireless. Pada saat  yang sama kepadatan peningkatan  jalur  akses  WLAN  mulai menyoroti kekurangan dari standar IEEE 802,11.  Sampai  saat  ini  belum  ada metode  standar  untuk  alokasi  channel pada  akses  point  WLAN.  Hal  ini mengarah  pada  situasi  di  mana  sebagian besar  AP  menggunakan  pengaturan channel  secara  default,  menyebabkan penggunaan  sangat  tidak  efisien  dari spektrum  yang  sudah  padat.  Situasi  ini penting pada pita 2,4 GHz, karena hanya sedikit  jumlah  non-overlapping  channel WLAN  yang  tersedia  dan  masalah berdekatan  dengan  beberapa  teknologi wireless lainnya.
Kekurangan  yang  terdapat  pada Industrial  Scientific  and  Medical  (ISM)
band  2.4GH  menurut  badan  pengawas Eropa  adalah  hanya  disediakan  13 channel,  yaitu  dimulai  dari  2.412  GHz (channel  1)  sampai  dengan  2.472  GHz (channel13),  seperti  ditunjukkan  pada Gambar  1.  Masing-masing  channel diberi  jarak  5MHz,  sedangkan  lebar bandwidth  sinyal  adalah  sekitar  24MHz, sehingga  hanya  memiliki  sebanyak  tiga channel yang tidak overlapping (1, 6 dan 11),  seperti  ditujukkan  pada  gambar  2. Dengan semakin berkembangnya teknologi wireless dan semakin pesatnya pertumbuhan  kebutuhan  akan  adanya jaringan  wireless,  maka  terlihat  jelas bahwa di daerah dengan kepadatan besar, tiga buah channel yang tidak overlapping akan  tidak cukup untuk mengatasinya
Gambar 1 . Alokasi channel pada wireless (Handrizal, 2012)
Gambar 2. Channel yang tidak overlapping pada wireless (Handrizal, 2012)
Penggunaan channel dengan overlapping  (misalnya,  channel  1  dan channel  2)  dalam  ruang  fisik  yang  sama akan  menyebabkan  interferensi  antara sistem,  sehingga  akan  menyebabkan penurunan drastis pada throughput.
Beberapa  artikel  penelitian  telah dipublikasikan  tentang  alokasi  channel. Diantara  mereka  adalah  Al  Mamun  dkk. (2009),  Andre  (2005),  Duan  dkk  (2010), Ming,  H.  dkk  (2009),  Juhos  (2006), Riihijarvi, dkk. (2006). Penelitian- penelitian  itu  mengungkapkan  bahwa alokasi  channel  untuk  wireless  adalah salah  satu  masalah  saat  ini  yang  masih belum terpecahkan.

## Landasan Teori
Pada  bagian  ini  akan  bahas mengenai  alokasi  channel  untuk  WLAN dalam hal teori pewarnaan graf. Menurut (Diestel,  2010)  yang  menarik  dalam konteks  alokasi  channel  misalkan,  diberi graf  sederhana  G  =  (V,  E),  yaitu  graf yang terdiri dari satu himpunan vertex V dan  himpunan  edge  E.  Loop  dan multiedge
antara vertex tidak
diperbolehkan.  Kemudian  pewarnaan vertex dari G adalah pemetaan: V (G) → F,  dimana  F  adalah  satu  himpunan warna,  biasanya  beberapa  bagian  kecil dari bilangan bulat positif. Sebuah vertex dapat  diwarnai,  jika  C  (V i )  =  C  (V j ) untuk semua V i dan V j berdekatan (yaitu, untuk  vertex  yang  terhubung  dengan sebuah  edge.  Dalam  pewarnaan  graf, tidak  hanya  sekedar  mewarnai  vertex- vertex  dengan  warna  yang  berbeda
dengan  warna  vertex  tetangganya  saja, akan  tetapi  juga  diinginkan  agar  jumlah warna yang digunakan sesedikit mungkin.  Jumlah  warna  minimum  yang dapat digunakan untuk mewarnai vertex- vertex  disebut  bilangan  kromatik  dari graf G yang disimbolkan dengan χ(G).

## Interferensi Graf
Sekarang  akan  bahas  mengenai alokasi  channel  dalam  hal  terminologi yang  telah  diperkenalkan  pada  bagian sebelumnya.  Misalkan,  {v i }  adalah himpunan  dari  akses  point,  itu  akan membentuk sebuah grafik gangguan G = (VG,  EG)  sebagai  berikut.  Himpuan vertex  V  hanya  diidentifikasi  dengan himpunan  {v i }.  Himpunan  edge  E dibangun dengan gabungan dari pasangan  {v k ,  v l }  dari  vertex,  yang sesuai dengan akses point v k dan v l yang akan  mengganggu  lalu  lintas  radio masing-masing jika mereka harus menggunakan channel yang sama. Akhirnya F merupakan himpunan "warna",  untuk  menjadi  koleksi  channel yang  tersedia  untuk  akses  point.  Tentu saja  ukuran  himpunan  warna  sangat tergantung  dari  teknologi  dan  undang- undang  yang  berlaku  disuatu  negara.  Di kebanyakan  negara  Eropa,  F  =  {1,  2  ...
13}  sedangkan  sub  himpunan  F'=  {1,  6,
11} untuk channel yang tidak overlapping.

## Matrix Kedekatan
Misalkan  G  adalah  graf  dengan  m vertex dan misalkan vertex telah diurutkan,  katakanlah,  vi,  vj,  ...,  vm. Seperti  ditunjukkan  pada  Gambar.  3 . Kemudian  Matrik  kedekatan  A  (G)  = [aij]  dari  graf  G  adalah  matrik  m  ×  m yang didefinisikan dengan:
Gambar 3. Contoh graf
Matrik kedekatan A dari graf G tidak tergantung  pada  urutan  dari  vertex  G, yaitu,  pengurutan  yang  berbeda  dari vertex  menghasilkan  matrik  kedekatan yang  berbeda.  Namun,  setiap  dua  matrik berdekatan  tersebut  terkait  erat,  dimana yang  satu  dapat  diperoleh  dari  yang  lain hanya dengan menukar  baris dan  kolom, seperti terlihat pada gambar 4.
Gambar 4. Matrik kedekatan graf

## Metode Penelitian
Pada bagian ini akan dibahas dua buah  metode  yang  akan  dibandingkan dalam  penelitian  ini  yaitu  algoritma Dsatur dan algoritma Vertex Merge

## Algoritma Dsatur
Algoritma  Degree  of  Saturation (Dsatur)  diperkenalkan  oleh  Brelaz  pada tahun  1979  (Brelaz,  1979).  Algoritma Dsatur  adalah  algoritma  pewarnaan  graf berdasarkan derajat (degree) suatu
vertex.  Pada  tahun  2006,  Riihijarvi (Riihijarvi,  2006)  telah  menerapkan algoritma Dsatur untk menentukan alokasi channel. Algoritma ini menentukan  channel  berdasarkan  degree paling tinggi dari pada AP. Algoritma ini tidak selalu memberikan jumlah minimum channel yang diperlukan untuk AP.  Algoritma  ini  hanya  cukup  praktis untuk  graf  sederhana.  Namun,  algoritma ini  tidak  cukup  praktis  untuk  graf  yang lebih  komplek.  Berikut  ini  adalah langkah-langkah algoritma Dsatur
selengkapnya:
1. Susun  vertex  berdasarkan  penurunan jumlah derajat.
2. Warnai  vertex  berderajat  maksimal dengan warna 1
3. Pilih  vertex  dengan  derajat  kejenuhan maksimal.  Jika  ada  yang  sama,  pilih vertex  dengan  derajat  maksimal  dalam subgraph yang belum diwarnai.
4. Warnai  vertex  yang  sudah  dipilih dengan warna yang paling memungkinkan
5. Jika  seluruh  vertex  sudah  diwarnai, berhenti.  Jika  tidak,  kembali  ke langkah 3.

## Algoritma Vertex Merge
Algoritma  Vertex  Merge  adalah algoritma yang didasarkan pada
deterministik, karena bertentangan
dengan  algoritma  acak  yang  banyak diusulkan.  Hal  ini  diperlukan  karena akses  point  secara  alami  harus  setuju pada  channel  yang  telah  dialokasikan (Handrizal, 2012). Algoritma Vertex Merge menggunakan beberapa metode heuristik untuk memilih vertex yang akan diwarnai, Heuristik yang digunakan oleh algoritma  ini  adalah  untuk  menemukan sub himpunan dari vertex dengan derajat tertinggi,  yaitu,  vertex  dengan  jumlah perbedaan edge terbesar dengan tetangga.  Jika  sub  himpunan  ini  hanya berisi  satu  vertex,  ia  dipilih  menjadi berwarna.  Jika  lebih  dari  satu  vertex tetap  di himpunan,  pemilihan ini kemudian dibuat dalam urutan penurunan  jumlah  tetangga  yang  belum diwarnai.  Berikut  ini  adalah  langkah demi langkah algoritma Vertex Merge:
1. Susun  vertex  berdasarkan  penurunan jumlah derajat.
2. Pilih  vertex  pertama  yang  belum diwarnai didalam himpunan.
3. Warnai  vertex  yang  sudah  dipilih dengan warna yang paling
memungkinkan
v 1 v 2 v 3 v 4 v 1 0 1 1 0 v 2 1 0 0 1
v 3 1 0 0 1 v 4 0 1 1 0         G j i G j i ij E v v E v v a , 0 , 1
4. Gabungkan  vertex  dengan  vertex pertama yang tidak bertetangga.
5. Warnai  vertex  yang  sudah  dipilih dengan  warna  yang  sama.  Jika  tidak ada lagi vertex yang tidak bertetangga, kembali kelangkah 2.
6. Jika  seluruh  vertex  sudah  diwarnai. Berhenti.  Jika  tidak,  kembali  ke langkah 2.

## Hasil dan Pembahasan
Pada  bagian  ini  akan  dibahas hasil dan diskusi dari simulasi perbandingan  algoritma  Dsatur  dan
algoritmaVertex  Merge  dengan  inputan berupa  tiga  buah  graf  komplek  yaitu graf1 dengan 10 vertex yang diberi label V =  {1,  2,  3,  4,  5,  6,  7,  8,  9,  10},  graf2 dengan  14  vertex  yang  diberi  label V = {1,  2,  3,  4,  5,  6,  7,  8,  9,  10,  11,  12,  13, 14},    dan  graf3  dengan  17  vertex  yang diberi label V = {1, 2, 3, 4, 5, 6, 7, 8, 9,
10,  11,  12,  13,  14,  15,  16,  17},  untuk setiap  vertex  didalam  graf  merupakan akses point didalam wireless.
Hasil  simulasi  dengan  inputan
berupa  tiga  buah  graf  komplek  akan  di tampilkan pada tabel 1 dibawah ini:
Tabel 1: Input graf untuk simulasi Input Output Algoritma Dsatur Algoritma Vertex Merge
graf1 Jumlah Channel χ(G) = 6
C (1,5)=channel 1,
C (7,9)=channel 4,
C (3,4)=channel 7,
C (2,8)=channel 9,
C (10)=channel 11,
C (6)=channel 13.
χ(G) = 5
C (1,2)= channel 1,
C (3,4)=channel 4.
C (5,6)=channel 7
C (7,9)=channel 10, C (8,10)=channel 13.
Jumlah Channel
Jumlah Channel χ(G) = 8
C(1,4)=channel 1, C(2,11)=channel 3, C(9,14)=channel 5, C(5,10)=channel 7, C(6,7)=channel 9, C(8)=channel 11, C(12,13)=channel 12, C(3)=channel 13.
χ(G) = 7
C(1,4)=channel 1, C(2,3)=channel 3. C(5,6)=channel 5 C(7,8)=channel 7, C(9,10)=channel 9 C(11,12)=channel 11, C(13,14)=channel 13.
graf3
Jumlah Channel χ(G) = 8
C(1,6,13)=channel 1, C(5,10,15)=channel 3, C(2,9,14)=channel 5, C(11,17)=channel 7, C(4,7)=channel 9, C(3,8)=channel 11, C(16)=channel 12, C(12)=channel 13.
χ(G) = 6
C(1,4,7)=channel 1, C(2,5,8)=channel 4,
C(3,6,9)=channel 7 C(10,13,16)=channel 9,
C(11,14,17)=channel 11,
C(12,15)=channel 13.
Dari  hasil  simulasi  tiga  buah  graf pada tabel 1 dapat dilihat bahwa :
1. Untuk input graf1 dapat dilihat bahwa output  simulasi  memberikan  hasil yang  berbeda  untuk  kedua  algoritma, diperlukan  6  warna  untuk  algoritma Dsatur  dan  5  warna  untuk  algoritma
Vertex Merge, itu berarti diperlukan 6 channel  untuk  algoritma  Dsatur  dan  5 channel untuk algoritma Vertex Merge, yaitu:
a. Algoritma Dsatur:
- channel 1 untuk AP1 dan AP5
- channel 4 untuk AP7 dan AP9
- channel 7 untuk AP3 dan AP4
- channel 9 untuk AP2 dan AP8 - channel 11 untuk AP10
- channel 13 untuk AP6 b. Algoritma Vertex Merge : - channel 1 untuk AP1 dan AP2
- channel 4 untuk AP3 dan AP4 - channel 7 untuk AP5 dan AP6
- channel 10 untuk AP7 dan AP9
- channel 13 untuk AP8 dan AP10
2. Untuk input graf2 dapat dilihat bahwa output  simulasi  memberikan  hasil yang  berbeda  untuk  kedua  algoritma, diperlukan  8  warna  untuk  algoritma Dsatur  dan  7  warna  untuk  algoritma Vertex Merge, itu berarti diperlukan 8 channel untuk  algoritma Dsatur dan 7 channel untuk algoritma Vertex Merge, yaitu:
a. Algoritma Dsatur:
- channel 1 untuk AP1 dan AP4 - channel 3 untuk AP2 dan AP11 - channel 5 untuk AP9 dan AP14
- channel 7 untuk AP5 dan AP10
- channel 9 untuk AP6 dan AP7 - channel 11 untuk AP8 - channel 12 untuk AP12 dan AP13 - channel 13 untuk AP3 b. Algoritma Vertex Merge: - channel 1 untuk AP1 dan AP4 - channel 3 untuk AP2 dan AP3
- channel 5 untuk AP5 dan AP6
- channel 7 untuk AP7 dan AP8
- channel 9 untuk AP9 dan AP10
- channel 11 untuk AP11 dan AP12
- channel 13 untuk AP13 dan AP14
3. Untuk input graf3 dapat dilihat bahwa output  simulasi  memberikan  hasil yang  berbeda  untuk  kedua  algoritma, diperlukan  8  warna  untuk  algoritma
Dsatur  dan  6  warna  untuk  algoritma Vertex Merge, itu berarti diperlukan 8 channel  untuk  algoritma  Dsatur  dan  6 channel untuk algoritma Vertex
Merge, yaitu:
a.Algoritma Dsatur:
- channel 1 untuk AP1, AP6 dan AP13
-  channel  3  untuk  AP5,  AP10 dan AP15 - channel 5 untuk AP2, AP9 dan AP14 -  channel  7  untuk  AP11  dan AP17 - channel 9 untuk AP4 dan AP7 -  channel  11  untuk  AP3  dan AP8 - channel 12 untuk AP16 - channel 13 untuk AP12
b. Algoritma Vertex Merge:
- channel 1 untuk AP1, AP4 dan AP7
-  channel  4  untuk  AP2,  AP5 dan AP8 -  channel  7  untuk  AP3,  AP6 dan AP9 - channel 9 untuk AP10, AP13 dan AP16
-  channel  11  untuk  AP11, AP14 dan AP17
-  channel  13  untuk  AP12  dan AP15
Dari tabel perbandingan antara algoritma Dsatur dan algoritma Vertex Merge  diatas  dapat  buat  grafik perbandingannya  seperti  terlihat  pada
gambar 5 dibawah ini:
Grafik 1.  Grafik perbandingan algoritma Dsatur  dan  algoritma  Vertex Merge

## Kesimpulan
Hasil dari simulasi tiga buah graf yang  sudah  dilakukan  dapat  dilihat bahwa  dengan  menggunakan  algoritma Dsatur diperlukan 6 channel untuk graf1, 8  channel  untuk  graf2  dan  graf3. Sedangkan dengan menggunakan algoritma  Vertex  Merge  diperlukan  5 channel  untuk  graf1,  7  channel  untuk graf2  dan  6  channel  untuk  graf3.  Dari hasil  ini  dapat  disimpulkan  bahwa algoritma Vertex Merge berhasil memberikan jumlah channel yang diperlukan  lebih  sedikit  dibandingkan dengan  algoritma  Dsatur,  yang  berarti bahwa  algoritma  Vertex  Merge  lebih baik  dibandingkan  dengan  algoritma Dsatur.

## Daftar Pustaka
Al  Mamun,  K.M.A.  dkk.  2009.  An Efficient Variable Channel Allocation  Technique  for  WLAN IEEE 802.11 Standard, in
Proceedings  Conference  on  Circuits,
0 2 4 6 8 10 graf1 graf2 graf3 Ju m lah C h an n el Grafik Perbandingan algoritma Dsatur dan algoritma Vertex Merge
Algoritma
Dsatur
Algoritma Vertex
Merge
Communication  and  System,  pp.92- 95. André, M., G. Pesant dan S. Pierre, 2005.
A  Variable  Neighborhood  Search
Algorithm  for  Assigning  Cells  to Switches  in  Wireless  Networks.  J. Comput. Sci., 1: 175-181.
Brelaz,  D.  1979.  New  Methods  to  Color the Vertices of a graph, on
Communication  of  the  ACM,  no.22, pp.251-256 Diestel, R., 2006. Graph Theory (Graduate  Texts  and  Mathematics). 3rd  Edn.,  Springer,  USA.,  ISBN:10:
3540261834, pp: 415.
Duan,  Z.  dkk.  2010  Optimal  Channel Assignment  for  Wireless  Networks
Modelled  as  Hexagonal  and  Square Grids.    International  Conference  on Networks Security Wireless Communications and Trusted Computing. Handrizal,dan Heri Santoso, 2012. Algoritma vertex merge untuk
menentukan  alokasi  channel  pada akses  point  wireless  LAN.  Seminar
Nasional Ilmu Komputer 2012 Juhos  dan  Jano,  I.  2006.    Increasing  the efficiency of graph coloring
algorithms  with  a  representation based  on  vector  operations.  J. Software, pp: 1. Ming, H. dkk. 2009. Hierarchical genetic algorithm for dynamic channel units allocation  in  td-cdma/tdd  system. International  Journal  of  Wireless  & Mobile  Networks  (IJWMN),  Vol  1, No 2. pp.103-116. Riihijarvi,  J.  dkk.  2006.  Performance Evaluation of Automatic Channel Assignment Mechanism for IEEE 802.11  Base  on  Graph  Coloring, in  Proceedings  The  17 th Annual IEEE  International  Symposium on  Personal,  Indoor  and  Mobile Communications, pp.1-5.