3.1 Model Matematika untuk masalah interferensi pada WLAN. Telah dijelaskan pada bab satu bahwa dengan teknologi dan kemudahan yang

BAB III Model Matematika

BAB III MODEL MATEMATIKA

3.1 Model Matematika untuk masalah interferensi pada WLAN Telah dijelaskan pada bab satu bahwa dengan teknologi dan kemudahan yang ditawarkan, teknologi WLAN masih memiliki kelemahan yang cukup mendasar, yaitu kemungkinan terjadinya interferensi antar access point yang mengakibatkan fasilitas WLAN akan terganggu. Hal ini dikarenakan teknologi WLAN menggunakan

pancaran

gelombang

radio

sebagai

pemancar

sinyalnya.

Permasalahan interferensi pada WLAN ini kemudian akan dimodelkan ke dalam bentuk graf G=(VG,EG) dan diselesaikan dengan menggunakan variasi pewarnaan titik yaitu T-Coloring.

Sebuah access point memiliki beberapa kanal frekuensi pilihan yang dapat dipilih sesuai kebutuhan penggunaan. Kanal yang kita pilih kemudian akan ditembakkan ke daerah sekelilingnya sampai kira-kira sejauh 48 m (untuk teknologi saat ini) yang kemudian sinyal/gelombang radio tersebut akan ditangkap oleh alat (PDA/laptop/HP,dsb) berkemampuan WLAN.

22 Pengalokasian Frekuensi pada WLAN dengan Menggunakan T-Coloring


Di bawah ini adalah tabel pembagian kanal frekuensi pada sebuah access point di beberapa negara : Channel Frequency Channel ID

(US/Canada) Equipment

1

2412 MHz

2

2417 MHz

3

2422 MHz

4

2427 MHz

5

2432 MHz

6

2437 MHz

7

2442 MHz

8

2447 MHz

9

2452 MHz

10

2457 MHz

11

2462 MHz

Tabel 3.1. Kanal frekuensi untuk peralatan Amerika Serikat dan Kanada Selain peralatan Amerika Serikat dan Kanada, maka terdapat kanal tambahan sebanyak dua buah yaitu : Channel Frequency Channel ID

(non US/Canada) Equipment

12

2467 MHz

13

2472 MHz

Tabel 3.2. Kanal frekuensi untuk peralatan non-Amerika Serikat dan Kanada.

Seperti yang telah dijelaskan sebelumnya, sebuah access point memberikan beberapa pilihan kanal frekuensi yang dapat dipilih sesuai kebutuhan. Berikut ini adalah beberapa gambar dan penjelasan dari penggunaan kanal frekuensi.



11 MHz

2401 MHz

11 MHz

2412 MHz

2423 MHz

22 MHz

Gambar 3.1. Kanal tunggal.

Gambar 3.1 menunjukkan sebuah kanal yang memancarkan frekuensi radio tanpa menimbulkan interferensi karena tidak ada frekuensi lain yang digunakan oleh access point lain. Tampak sebuah kanal yang dipilih sebenarnya memancarkan tambahan/pengurangan 22 Mhz.

11 MHz

11 MHz

11 MHz

2412 MHz

11 MHz

2437 MHz

11 MHz

11 MHz

2462 MHz

Gambar 3.2. 3 kanal ortogonal tanpa irisan frekuensi.

2412 MHz

2427 MHz

2442 MHz

24572 MHz

Gambar 3.3. 4 kanal ortogonal dengan irisan frekuensi.



Tampak pada Gambar 3.3, penggunaan 4 kanal pada suatu wilayah tertentudengan adanya “irisan frekuensi” . Hal inilah selanjutnya akan disebut saling berinterferensi. Sedangkan pada penggunaan 3 kanal pada Gambar 3.2, tidak terdapat irisan frekuensi.

Jika diperhatikan baik-baik maka terlihat bahwa jarak frekuensi tengah antar kanal hanyalah 5MHz (Tabel 3.1), padahal lebar total bandwidth sebuah pemancar Direct Sequence Spread Spectrum (DSSS) yang digunakan dalam WLAN adalah 22MHz. Oleh karena itu, pada kanal seperti pada Gambar 3.3 sinyal yang dipancarkan antar kanal akan saling menginterferensi satu sama lain (overlap). Akan tetapi untuk peralatan non-Amerika Serikat dan Kanada DSSS yang digunakan dapat diperkecil, sehingga DSSS-nya menjadi 20MHz.

Oleh karena itu, pada band 2.4GHz hanya ada maksimum 3 (tiga) kanal saja yang sinyalnya tidak saling overlap untuk peralatan Amerika Serikat dan Kanada yaitu: Kanal 1

2.412 GHz

Kanal 6

2.437 GHz

Kanal 11

2.462 GHz

dan 4 (empat) kanal pada peralatan non-Amerika Serikat dan Kanada yaitu : Kanal 1

2.412 GHz

Kanal 5

2.432 GHz

Kanal 9

2.452 GHz.



Kanal 13

2.472 GHz

Secara garis besar pemodelan yang digunakan dalam masalah WLAN ini adalah : Graf G merupakan suatu wilayah tertentu di mana terdapat access point beserta hotspot-nya. Titik menunjukkan letak access point. Sisi menunjukkan irisan dua atau lebih hotspot yang dipancarkan oleh access point. Warna menunjukkan jenis kanal frekuensi yang diberikan kepada access point.

Sebagai contoh, misalkan suatu sistem WLAN pada suatu tempat digambarkan sebagai berikut :

Gambar 3.4. Access point pada suatu tempat. Sistem WLAN pada Gambar 3.4 akan dimodelkan ke dalam bentuk graf G = (VG , EG ) . Langkah awal proses pemodelannya adalah menentukan himpunan VG, yaitu titik di mana access point berada, sehingga titik-titik pada graf yang 26 Pengalokasian Frekuensi pada WLAN dengan Menggunakan T-Coloring


diperoleh berdasarkan Gambar 3.4 adalah VG = {v1 , v 2 , v3 } . Himpunan sisi yang diperoleh yaitu EG = {e1 , e2 , e3 } dengan e1 = v1v 2 , e2 = v 2 v3 , dan e3 = v3 v1 .

Graf yang bersesuaian dengan masalah pada Gmbar 3.4 adalah

v1

v2

v3 Gambar 3.5. Graf yang bersesuaian dengan Gambar 3.4.

T-Coloring digunakan untuk menyelesaikan masalah interferensi pada WLAN yaitu dengan menentukan himpunan T = {0, 1, 2, 3, 4} untuk peralatan Amerika Serikat dan Kanada, dan T = {0, 1, 2, 3} untuk peralatan non-Amerika Serikat dan Kanada. Selanjutnya himpunan T yang digunakan adalah T = {0, 1, 2, 3} karena memungkinkan penggunaan kanal yang lebih banyak. Warna yang digunakan sebanyak 4 warna yaitu : Warna 1 yang mewakili kanal 1 (2412 MHz). Warna 5 yang mewakili kanal 5 (2432 MHz). Warna 9 yang mewakili kanal 9 (2452 MHz). Warna 13 yang mewakili kanal 13 (2472 MHz).



Algoritma DSATUR digunakan untuk mencari jumlah warna yang dipakai pada proses pewarnaan titik pada suatu graf. Misalkan graf G = (VG , EG ) ditunjukkan seperti gambar di bawah ini :

1

3

2

4

5

7 13

6

12 8

14

9 11

10 Gambar 3.6. Graf G

Buat derajat saturasi semua titik menjadi nol dengan menjadikan semua titik tidak berwarna. Pilih titik yang memiliki derajat saturasi terbesar. Jika terdapat lebih dari satu titik dengan degs(x) terbesar, maka pilih titik dengan derajat terbesar yaitu titik v6, warnai titik tersebut.



1 3

2

4

5

7 13

6

12 8

14

9 11

10 Gambar 3.7. Graf G

Update derajat saturasi titik yang belum diwarnai, maka didapat : degS(v1)= degS(v2)= degS(v4)= degS(v10)= degS(v11)=0 dan degS(v3)= degS(v5)= degS(v7)= degS(v8)= degS(v9)=1. Titik v3, v5, v7, v8, v9 mempunyai derajat saturasi terbesar yang sama yaitu 1. Pilih titik dengan jumlah tetangga terbanyak. Jika terdapat lebih dari satu titik yang derajat saturasinya sama dan jumlah tetangganya sama, maka pilih titik dengan indeks terkecil.

Dengan mengulangi langkah-langkah di atas sampai semua titik berhasil diwarnai, maka graf pada Gambar 3.6 dan Gambar 3.7 menjadi sebagai berikut :



Gambar 3.8. Proses pewarnaan titik pada graf G dengan algortima DSATUR

Berdasarkan Gambar 3.8, graf G dapat diwarnai dengan menggunakan 4 buah warna yaitu warna 1 (merah), warna 2 (kuning), warna 3 (biru), dan warna 4 (hijau). Yang menjadi pertanyaan: apakah graf tersebut dapat diwarnai dengan menggunakan warna yang lebih sedikit?



Untuk menjawab pertanyaan tersebut, kita gunakan algoritma BSC (Backtracking Sequencial Coloring). Himpunan warna bebas dari suatu titik x, dinotasikan dengan U = freeColors(x), adalah himpunan bagian dari warna {1,2,…, li+1} yang tidak muncul pada tetangga x, dengan li adalah warna yang telah digunakan saat itu. Urutkan titik berdasarkan derajat secara tidak naik, yaitu A=[ v2, v6, v10, v11, v4, v1, v3, v5, v7, v8, v9, v13, v12, v14]. Dengan menggunakan algoritma DSATUR, hitung nilai freeColors(x), ∀x ∈ EG .

1

freecolor(v6) freecolor(v3) freecolor(v2) freecolor(v10) freecolor(v5) 4 freecolor(v1) freecolor(v7) freecolor(v ) 13 freecolor(v11 4) freecolor(v9) freecolor(v13) freecolor(v8) freecolor(v12) freecolor(v14)

3

2 5

12

7 6 8

9

14 10

=[] =[] = [3] = [3] =[] = [4] = [4] = [4] = [4] =[] = [4, 5] = [3, 4, 5] = [3, 4, 5] = [3, 4, 5]

11

Gambar 3.9. Graf G dengan nilai freecolor untuk setiap titiknya

Pilih titik yang mengandung warna 4 (hijau) yaitu v9, kemudian hapus warna pada titik tersebut, dan hapus freecolor yang mengandung warna lebih besar atau sama dengan 4.



1 3

2 5

12

7 6 8

9

14 10

11

freecolor(v6) freecolor(v3) freecolor(v2) freecolor(v10) 4 freecolor(v5) freecolor(v1) freecolor(v7) 13 freecolor(v11) freecolor(v4) freecolor(v9) freecolor(v13) freecolor(v8) freecolor(v12) freecolor(v14)

=[] =[] = [3] = [3] =[] =[] =[] =[] =[] =[] =[] = [3] = [3] = [3]

Gambar 3.10. Graf G yang telah di-update.

Lakukan proses backtracking ke titik v8, hapus warna pada titik tersebut, beri warna menggunakan warna yang ada pada freecolor(v8), yaitu warna 3 (biru). Pindah ke titik v9, karena freecolor(v8)=[ ] maka v9 tidak dapat diwarnai, bactracking ke v8. Freecolor(v8)=[ ] hapus warna pada titik tersebut, lakukan proses bactracking ke titik v7. Freecolor(v7)=[ ] hapus warna pada titik tersebut, lakukan proses bactracking ke titik v5. Freecolor(v5)=[ ] hapus warna pada titik tersebut, lakukan proses bactracking ke titik v3. Freecolor(v3)=[ ] hapus warna pada titik tersebut, lakukan proses bactracking ke titik v1. Freecolor(v1)=[ ] hapus warna pada titik tersebut, lakukan proses bactracking ke titik v4. Freecolor(v4)= [ ] hapus warna pada titik tersebut, lakukan proses bactracking ke titik v11. Freecolor(v11)=[ ] hapus warna pada titik tersebut, lakukan proses bactracking ke titik v10. 32 Pengalokasian Frekuensi pada WLAN dengan Menggunakan T-Coloring


Gambar 3.11. Graf G yang telah di-update.

Freecolor(v10)=[3], oleh karena itu warnai titik v10 dengan warna 3 (biru) sehingga freecolor(v10)=[ ]. Gunakan algoritma DSATUR didapat titik v5 dengan freecolor(v5)=[1, 2, 3]. Warna 1 dan warna 2 telah digunakan oleh tetangga v5, gunakan warna 3 (biru) untuk mewarnai titik v5. Gunakan algoritma DSATUR didapat titik v1 dengan freecolor(v1)=[1, 2, 3]. Warna 1 dan warna 2 telah digunakan pada tetangga v1, gunakan warna 3 (biru) untuk mewarnai titik v1. Gunakan algoritma DSATUR didapat titik v7 dengan freecolor(v7)=[1, 2, 3]. Warna 1 dan warna 3 telah digunakan pada tetangga v7, gunakan warna 2 untuk mewarnai titik v7. Gunakan algoritma DSATUR didapat titik v11 dengan freecolor(v11)=[1, 2, 3]. Warna 2 dan warna 3 telah digunakan pada tetangga v11, gunakan warna 1 (merah) untuk mewarnai titik v11. Gunakan algortima DSATUR didapat titik v9 dengan freecolor(v9)=[1,2,3]. Warna 1 dan warna 3 telah digunakan pada tetangga v9, gunakan warna 2 (kuning). Gunakan algoritma 33 Pengalokasian Frekuensi pada WLAN dengan Menggunakan T-Coloring


DSATUR didapat titik v4 dengan freecolor(v4)=[1, 2, 3]. Warna 1 dan warna 2 telah digunakan pada tetangga v4, gunakan warna 3 (biru) untuk mewarnai titik v4. Gunakan algoritma DSATUR didapat titik v3 dengan freecolor(v3)=[1, 2, 3]. Warna 1 dan warna 3 telah digunakan pada tetangga v3, gunakan warna 2 (kuning) untuk mewarnai titik v3. Gunakan algoritma DSATUR didapat titik v8 dengan freecolor(v8)=[1, 2, 3]. Warna 1 dan warna 3 telah digunakan pada tetangga v8, gunakan warna 2 (kuning) untuk mewarnai titik v8. Gambar 3.12 menunjukkan pewarnaan titik pada graf G dengan menggunakan algoritma BSC.

Gambar 3.12. Graf G yang telah diwarnai dengan menggunakan algoritma BSC.



Algoritma BSC memberikan hasil yang lebih baik dalam menentukan jumlah warna minimum yang dapat digunakan pada proses pewarnaan graf G. Gambar 3.12 menunjukkan bahwa graf G dapat diwarnai dengan menggunakan 3 buah warna saja, tetapi tidak dapat dapat diwarnai dengan menggunakan 2 warna. Algoritma BSC berhenti apabila freecolor dari setiap titik sudah tidak ada lagi, dengan kata lain sudah tidak ada warna lagi yang dapat digunakan.

Terakhir kita gunakan T-Coloring pada graf dari Gambar 3.12. Dengan T={0, 1, 2, 3} diperoleh : f : VG → {1,2,...,13}

v1 a 3 v2 a 2 v3 a 1 v4 a 3 v5 a 2 v6 a 1 v7 a 2 v8 a 2 v9 a 2 v10 a 3 v11 a 1 v12 a 3 v13 a 2 v14 a 1



3.2 Model Matematika untuk Kasus WLAN di Gedung Labtek 3 Berdasarkan pengamatan yang dilakukan di lapangan, sistem WLAN yang ada di Gedung Labtek 3 adalah sebagai berikut :

5 6

7 8

2

9

1

4

3

Gambar 3.13. Sistem WLAN di Labtek 3

Dari Gambar 3.13 terdapat 9 buah AP (access point) yang terdapat di Gedung Labtek 3 yaitu : AP 1 yang bernama ITB-hotspot. AP 2 yang bernama AP-Math. AP 3 yang bernama Lab-Math. AP 4 yang bernama Pluto-TI. AP 5 yang bernama Saturnus-TI. AP 6 yang bernama Merkurius-TI. AP 7 yang bernama Bumi-TI. AP 8 yang bernama LSIK. AP 9 yang bernama Mars-TI.



Kemudian akan dimodelkan sistem WLAN pada Gambar 3.13 ke dalam bentuk graf G = (VG , EG ) . Sebagai langkah awal, akan dimodelkan lintasan pada Gambar 3.13 sebagai titik pada graf. Diperoleh titik-titik sebagai berikut : VG = (v1 , v2 , v3 , v4 , v5 , v6 , v7 , v8 , v9 ). Sisi EG untuk graf G = (VG , EG ) ada jika terdapat irisan hotspot dari dua buah access point, sehingga diperoleh sisi-sisi sebagai berikut : E G = (v1v 2 , v1v6 , v1v7 , v1v8 , v1v9 , v 2 v3 , v 2 v 4 , v 2 v6 , v 2 v7 , v 2 v9 , v3 v 4 , v5 v7 , v6 v7 , v6 v8 , v7 v8 ) Matriks ketetanggaan dari graf G = (VG , EG ) adalah v1 v1 v2 v3 v4 v5 v6 v7 v8 v9

1 0 0 0 1 1 1 1

v2 1 1 1 0 1 1 0 1

v3 0 1 1 0 0 0 0 0

v4 0 1 1 0 0 0 0 0

v5 0 0 0 0 0 0 0 0

v6 1 1 0 0 0 1 1 0

v7 1 1 0 0 1 1 1 0

v8 1 0 0 0 0 1 1

v9 1 1 0 0 0 0 0 0

0

Tabel 3.3. Matriks ketetanggaan graf G.



Graf G yang terbentuk adalah : V8 V7 V9

V6 V1 V5 V2 V4 V3

Gambar 3.14. Graf yang bersesuaian dengan sistem WLAN di Labtek 3

Dengan menggunakan algoritma BSC maka diperoleh solusi dari graf pada Gambar 3.16 yaitu : V8 V7 V9

V6 V1 V5 V2 V4 V3

Gambar 3.15. Graf G yang telah diwarnai.



Berdasarkan Gambar 3.15 didapat χ G = 4 . Selanjutnya gunakan T-Coloring pada graf tersebut sehingga diperoleh : Untuk T = {0,1,2,3}, maka : Kanal 1 (2.412 GHz) : Kanal 5 (2.432 GHz) : Kanal 9 (2.452 GHz) : Kanal 13 (2.412 GHz) Jadi untuk sistem WLAN di Gedung Labtek 3 tidak mengalami interferensi karena warna yang digunakan berjumlah 4.


3.1 Model Matematika untuk masalah interferensi pada WLAN. Telah dijelaskan pada bab satu bahwa dengan teknologi dan kemudahan yang

Recommend Documents