ANALISIS PENGALOKASIAN KANAL PADA KOMUNIKASI SELULER DENGAN ALGORITMA SIMULATED ANNEALING Elisabeth Bestiana Siregar Dosen Pembimbing : Rahmad Fauzi,ST. MT Konsentrasi Teknik Telekomunikasi, Departemen Teknik Elektro Fakultas Teknik Universitas Sumatera Utara (USU) Jl. Almamater, Kampus USU Medan 20155 INDONESIA e-mail:
[email protected] or
[email protected]
ABSTRAK Saat ini perkembangan teknologi telekomunikasi semakin meningkat, pengguna telepon selular pun semakin bertambah pesat. Pada waktu tertentu permintaan kanal akan maksimal bahkan melebihi kapasitas saluran yang tersedia, hal tersebut dapat mengakibatkan banyak panggilan tidak dapat dilayani atau diblok. Pada nilai tertentu tingkat kegagalan masih dapat diterima namun selebihnya diperlukan solusi pemecahan akan masalah tersebut, salah satunya adalah pengoptimalan kanal. Tulisan ini membahas pengalokasian kanal pada GSM dengan menggunakan Algoritma Simulated Annealing sebagai metode penyelesaiannya. Alokasi kanal merupakan masalah optimasi yang meminimalkan interferensi yang ditimbulkan oleh adjacent channel dan co-channel. Dalam hal ini algoritma Simulated Annealing digunakan sebagai metode untuk mengimplementasikan channel assignment problem (CAP) pada sistem komunikasi seluler. Salah satu parameter dalam algoritma ini adalah state (solusi). Adapun state yang dipakai untuk implementasi CAP adalah urutan sel dimana kanal akan dialokasikan pada sel tersebut, dengan nilai cii atau jarak pemisah antar kanal dalam satu sel bernilai 5 dan 6. Dari pengalokasian kanal yang dilakukan panggilan yang ditolak berkurang setelah dilakukan update state. Dimana jumlah kanal yang dapat dialokasikan pada state awal dengan cii=5 sebesar 126 kanal, terdapat 85 panggilan yang ditolak. Kemudian setelah update state dengan cii=6, jumlah kanal yang dialokasikan sebesar 151 kanal dan total panggilan yang ditolak menjadi 15 panggilan.
Kata kunci : Alokasi kanal, Simulated Annealing, adjacent channel, co-channel dikategorikan dalam Fixed Channel Allocation (FCA), Dynamic Channel Allocation (DCA) ataupun gabungan dari keduanya. FCA dan DCA ataupun gabungan keduanya memerlukan metode ataupun algoritma untuk dapat mengoptimalkan pengalokasian kanal pada sistem komunikasi seluler. Salah satu algoritma yang digunakan adalah algoritma Simulated Annealing. Algoritma ini dikembangkan dengan analogi dari prinsipprinsip kristalisasi pada logam dengan proses pendinginan dan pembekuan, sehingga diperoleh energi yang minimum. Dalam tulisan ini penulis tertarik untuk menganalisis penggunaan Algoritma Simulated Annealing untuk mengoptimalkan pengalokasian kanal pada sistem komunikasi seluler GSM.
1. PENDAHULUAN Seiring semakin berkembangnya teknologi membuat kebutuhan akan teknologi semakin meningkat juga. Karena kebutuhan akan komunikasi seluler semakin tinggi, maka timbul satu permasalahan yaitu kanal yang terbatas yang mengakibatkan banyak panggilan yang diblok atau tidak dilayani. Dari keterbatasan kanal tersebutlah diperlukan upaya untuk mengatasinya yaitu dengan pengalokasian kanal. Pengalokasian kanal dimaksudkan untuk mendapatkan alokasi kanal yang tepat, guna untuk meminimalkan panggilan yang ditolak dengan memperhatikan kualitas sinyal yang tetap terjaga baik (bebas dari interferensi). Ada banyak cara yang diusulkan untuk alokasi kanal radio dalam sistem seluler yang dapat -97-
copyright @ DTE FT USU
SINGUDA ENSIKOM
2.
VOL. 9 NO. 2/November 2014 seluruh kanal terduduki maka sel akan diblok dan kadang digunakan strategi peminjaman kanal dari sel tetangga [3].
CHANNEL ASSIGNMENT PADA SISTEM KOMUNIKASI SELULER
2.1 Sistem Komunikasi Seluler 2.2.2 Sistem komunikasi seluler adalah sistem komunikasi yang digunakan untuk memberikan layanan jasa telekomunikasi bagi pelanggan bergerak. Sistem komunikasi seluler dapat melayani banyak pengguna pada cakupan area geografis yang cukup luas dalam frekuensi yang terbatas. Komunikasi seluler dikatakan sistem seluler karena daerah layanannya dibagi menjadi daerahdaerah kecil yang disebut sel. Setiap sel mempunyai daerah cakupannya masing-masing dan beroperasi secara khusus. Jumlah sel pada suatu daerah geografis adalah berdasarkan pada jumlah pelanggan yang beroperasi di daerah tersebut. Bentuk sel yang terdapat pada sistem komunikasi bergerak selular digambarkan dengan bentuk hexagonal karena semua daerah dapat dicakup tanpa adanya gap sel satu dengan yang lain[2].
Dynamic channel allocation merupakan teknik yang tidak ada kanal yang dialokasikan secara tetap di dalam sel. DCA merupakan salah satu staregi untuk megatasi penambahan beban trafik dalam sistem seluler. Konsep dasar dari strategi DCA adalah bila beban trafik tidak merata dalam tiap sel maka pemberian kanal frekuensi pada tiap sel akan sering tidak terpakai dalam sel yang kurang padat, dan terjadi bloking pada sel dengan beban trafik padat. Teknik DCA dapat mengalokasi kanal frekuensi bila hanya beban trafik meningkat dan melepaskan kanal frekuensi bila beban trafik menurun [3]. 2.3 Perumusan Channel Assignment Problem Permasalahan channel assignment (CAP) muncul dalam jaringan telepon seluler yakni rentang frekuensi diskrit dengan spektrum frekuensi radio tersedia yang disebut sebagai kanal, dipelukan untuk dialokasikan ke daerah lain guna meminimumkan bentangan frekuensi total, tergantung pada permintaan (demand) dan pembatas bebas interferensi (interference-free constraint). Umumnya, penugasan kanal harus memiliki beberapa batasan electromagnetic compatibility (EMC), yang ditentukan melalui jarak minimum dimana dua kanal harus dipisahkan agar rasio S/I diterima kuat dalam wilayah yang salurannya telah ditugaskan. Hal tersebut dapat ditunjukkan melalui matrik N x N yang disebut matriks C. Ada tiga jenis kendala (constraint) dalam penugasan kanal, yaitu [4] : a. Cochannel Constraint (CCC) – cij dengan nilai = 1 atau 0 Dimana kanal pada sel yang berjauhan dapat dialokasikan pada satu kanal yang sama atau dengan jarak 1 kanal dengan kanal selanjutnya. b. Adjacent Channel Constraint (ACC) - cij dengan nilai = 2 Dimana kanal yang berdekatan tidak dapat dialokasikan untuk sel radio yang berdekatan secara bersamaan.
2.2 Prinsip Kerja Channel Assignment Secara umum strategi penempatan kanal adalah untuk peningkatan kapasitas kanal dari setiap sel dan meminimalkan interferensi sesuai dengan yang diinginkan. Strategi penempatan kanal yang telah dikembangkan untuk memenuhi tujuan mengurangi panggilan yang ditolak dan meminimalkan interferensi, dapat dikelompokkan menjadi fixed atau dinamic. Pemilihan strategi penempatan kanal dapat mempengaruhi kinerja dari sistem, terutama pengaturan panggilan saat sebuah pengguna berpindah dari satu sel ke sel yang lain. Channel assignment dapat dibagi menjadi Fixed Channel Allocation (FCA) dan Dynamic Channel Allocation (DCA). 2.2.1
Dynamic Channel Allocation (DCA)
Fixed Channel Allocation (FCA)
Fixed channel allocation merupakan teknik pengalokasian kanal dimana pada setiap sel dialokasikan secara tetap. Karena setiap sel dialokasikan secara tetap maka dalam sistem ini diperlukan management kanal yang tetap. Bila -98-
copyright @ DTE FT USU
SINGUDA ENSIKOM
VOL. 9 NO. 2/November 2014
c. Cosite Constraint (CSC) - cii dengan nilai = α Dimana setiap pasangan kanal yang ditetapkan dalam sel yang sama harus memiliki jarak kanal minimum α. Nilai α merupakan nilai positif mulai dari 0 ditugaskan ke sel i. Nilainya tergantung pada standar komunikasi yang digunakan. Pada umumnya nilai α dimulai dengan 5 untuk menyatakan jarak antar kanal dalam satu sel. Nilai cij merupakan jarak pemisah kanal antara kanal pada sel a dengan kanal pada sel b (jarak kanal pada sel yang berlainan). Sedangkan cii merupakan nilai jarak pemisah antar kanal dalam satu sel.
minimum yang diijinkan agar dapat menjamin tidak terjadi interferensi. Pada wilayah tersebut terdapat R buah kanal yang dapat digunakan. Pada sel ke-i terdapat ci jumlah panggilan. Dimana total panggilan untuk seluruh sel didefinisikan dengan [5]: Ncall = ∑ (1) i Dimana : Ncall = Jumlah Panggilan ci = Jumlah panggilan ke-i Masalah yang harus diselesaikan dalam hal ini adalah bagaimana mengatur kanal yang digunakan untuk melayani setiap panggilan pada masing-masing sel agar dapat meminimalkan jumlah panggilan yang diblok. Jadi tujuan dari penggunaan metode Simulated annealing adalah meminimalkan energi. Dalam hal ini energi yang dimaksud adalah jumlah panggilan yang dibloking. Blocking (energi) dihitung dengan rumus (2) dan (3) sebagai berikut [5] :
2.4 Algoritma Simulated Annealing Simulated annealing (SA) adalah salah satu algoritma untuk untuk optimisasi yang bersifat generik. Masalah yang membutuhkan pendekatan SA adalah masalah-masalah optimisasi kombinatorial, dimana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahan itu. Publikasi tentang pendekatan ini pertama kali dilakukan oleh S.Kirkpatrick, C.D.Gelatt dan M.P.Vecchi, diaplikasikan pada desain optimal hardware komputer, dan juga pada salah satu masalah klasik ilmu komputer yaitu Traveling Salesman Problem. Annealing adalah satu teknik yang dikenal dalam bidang metalurgi, digunakan dalam mempelajari proses pembentukan kristal dalam suatu materi. Agar dapat terbentuk susunan kristal yang sempurna, diperlukan pemanasan sampai suatu tingkat tertentu, kemudian dilanjutkan dengan pendinginan yang perlahan-lahan dan terkendali dari materi tersebut. Pemanasan materi di awal proses annealing, memberikan kesempatan pada atom-atom dalam materi itu untuk bergerak secara bebas, mengingat tingkat energi dalam kondisi panas ini cukup tinggi. Proses pendinginan yang perlahan-lahan memungkinkan atom-atom yang tadinya bergerak bebas itu, pada akhirnya menemukan tempat yang optimum, di mana energi internal yang dibutuhkan atom itu untuk mempertahankan posisinya adalah minimum [6]. Diketahui N buah sel pada komunikasi wireless yang mengkover satu wilayah tertentu. Arsitektur dari setiap sel didefinsikan dengan M={mi,j} dimana mi,j adalah selisih kanal
CallN = ∑ ServN = ∑
( ) ( )
(2) (3)
Dari persamaan (2) dan (3) nilai bloking merupakan selisih dari total panggilan dan total panggilan yang dilayani, seperti pada rumus (4) dan (5) berikut [5]: BlockN = CallN – ServN Energi = BlockN
(4) (5)
Dimana : CallN = Total seluruh panggilan ServN = Total panggilan yang dilayani BlockN =Total panggilan yang tidak dilayani (terblok) 2.4.1
Simulated Annealing pada Channel Assignment
Setelah dilakukan pembagian kanal pada setiap sel, untuk mendapatkan hasil yang optimal maka akan diproses dengan menggunakan algoritma Simulated Annealing. Berikut penjelasan dari Algoritma Simulated Annealing pada pengalokasian kanal : a) Definisi State Tujuan dari alokasi kanal dinamik adalah untuk menentukan kanal-kanal yang melayani panggilan, dan dapat meminimalkan terjadinya -99-
copyright @ DTE FT USU
SINGUDA ENSIKOM
VOL. 9 NO. 2/November 2014 kanal dengan menggunakan algoritma simulated annealing.
blocking. Sehingga state dalam pengalokasian ini didefinisikan sebagai urutan sel, dimana kanal akan dialokasikan pada sel tersebut. b) Definisi Energi Dalam Simulated Annealing selalu meminimalkan nilai energi. Sehingga pada pengalokasian kanal berfungsi untuk meminimalkan jumlah panggilan yang dibloking. c) Update State Membangkitkan kembali urutan sel dengan tujuan untuk mendapatkan nilai bloking untuk dibandingkan dengan nilai bloking yang sebelumnya agar diketahui state mana yang lebih baik. Pada proses update state ada beberapa hal yang harus dilakukan, yaitu : 1. Memilih bagian mana saja untuk dirandom lagi. 2. Lakukan random pada bagian yang sudah dipilih, kemudian hitung berapa jumlah energi (E1) dari random tersebut, energi ini kemudian dibandingkan dengan energi yang sebelumnya (E0). 3. Membandingkan energi E0 dengan E1. a) Apabila E0 > E1, maka E1 yang akan dipilih b) Setelah E1 terpilih maka akan diterima bila memenuhi syarat dengan menghitung nilai probabilitasnya (p=exp(-(∆E/T)) Pada langkah ini energi E1 diterima bila random > probabilitas, dan akan ditolak (diblok) apabila tidak memenuhi syarat pada point update state. d) Temperatur Sebagai ruang untuk mendapatkan nilai bloking lebih optimal pada setiap iterasinya. Umumnya temperatur ini tidak berhubungan langsung dengan aplikasi yang dijalankan, namun erat kaitannya dengan iterasi guna untuk mendapatkan nilai function yang lebih minimum (optimal).
3.
3.1 Parameter Kerja Pengalokasian Kanal Beberapa parameter yang digunakan dalam pengalokasian kanal ini antara lain : 1. Layout Sel Layout sel yang digunakan diambil dari peta kota Medan untuk dapat melihat contoh lebih sederhana karena penulis berdomisili di daerah Medan, sehingga dapat melihat dan mengetahui daerah yang digunakan. Daerah yang digunakan untuk pemodelan layout ini hanya 15 kecamatan dari kota Medan. Tidak semua daerah dimasukkan sebagai input untuk membuat layout selnya. Sel yang dimodelkan pada layout sel Medan sekitar 17 sel, dapat dilihat pada Gambar 1.
Gambar 1. Layout Sel yang Digunakan Pembagian layout sel ini jelas sangat berbeda dengan layout di lapangan. Hal ini dimaksdukan untuk mempermudah pengalokasian kanal yang tidak memiliki terlalu banyak sel, yaitu 17 sel. 2. Pola Interferensi Sel Dari layout sel yang digunakan dapat dihasilkan pola interferensi sel. 3. Matriks Cij Matriks Cij didapatkan setelah melihat layout yang digunakan dan telah disesuaikan dengan kaidah EMC. 4. Call demand Call demand yang digunakan pada optimasi alokasi kanal dinamik ini merupakan panggilan yang ditawarkan pada setiap sel. Call demand pada setiap sel berbeda-beda.
PEMODELAN ALOKASI KANAL DENGAN ALGORITMA SIMULATED ANNEALING
Dalam hal ini proses pengalokasian kanal dilakukan setelah parameter kerja optimasi berupa layout sel, jumlah call demand, dan kendala interferensi telah ditentukan. Kemudian dari parameter tersebut dilakukan proses penugasan
-100-
copyright @ DTE FT USU
SINGUDA ENSIKOM
VOL. 9 NO. 2/November 2014
3.2 Flowchart Algoritma Simulated Annealing pada Penugasan Kanal Gambar 2 merupakan flowchart dari penugasan kanal menggunakan algoritma simulated annealing. Sebelum dilakukan pengalokasian kanal perlu ditentukan inisialisasi terlebih dahulu yaitu jumlah sel, jumlah kanal, nilai call demand, dan suhu. Setelah semua kanal teralokasikan dihitung nilai kanal (panggilan) yang dibloking. Nilai sementara ini disimpan untuk dibandingkan dengan nilai bloking dengan proses update selanjutnya. Prinsip dari algoritma simulated annealing untuk mendapatkan nilai bloking yang lebih kecil, sehingga nilai bloking yang dipakai setelah proses update adalah nilai yang paling kecil.
4.
HASIL DAN PEMBAHASAN
4.1
Hasil Simulasi Pengalokasian Kanal
Tabel 1 pengalokasian kanal Dari tabel 1 dapat dialokasikan tanpa yang ada.
merupakan tabel hasil dengan menggunakan cii=6. dilihat semua kanal dapat melanggar batasan matriks
Tabel 1.Hasil Algoritma Simulated Annealing untuk Jarak Kanal cii=6
MULAI
Inisialisasi : 1. Jumlah S el 2. Jumlah K anal (cii(D-1)+1) 3. Nilai Call D emand 4. Suhu
Inisialisasi : 1 . Jumlah S el 2. Jumlah K anal ( (a+1)(D-1)+1)) 3. Nilai Call Demand 4. Suhu
Berikan U rutan S el
Update U rutan sel
Alokasikan Kanal (dengan cii =a ;a =5 )
Iterasi (n) = n+1
Hitung Jumlah panggilan yang dibloking (E0)
Alokasikan K anal (dengan cii=a+1 )
Sim pan E 0
Hitung Jumlah panggilan yang dibloking (E1) Hitung S elisih Panggilan yang dibloking (? E)=E1-E0
Apakah E0>E1?
5.
Tidak
Ya
Dari hasil pemodelan dan hasil analisis yang dilakukan maka dapat ditarik kesimpulan, antara lain : 1. Alokasi kanal menggunakan algoritma Simulated Annealing ini dipengaruhi oleh nilai jarak kanal dalam satu sel dan nilai call demand. 2. Keadaan yang diterima adalah keadaan yang menghasilkan nilai bloking yang lebih kecil. 3. Sebelum dilakukan update nilai bloking yang didapat sebesar 85 panggilan. Setelah dilakukan update nilai bloking sebanyak 15 panggilan yang menunjukkan kinerja. 4. Pemanfaatan kanal pada cii=6 merupakan yang lebih baik dengan persentase 94,78%.
Pilih E 1
Apakah E1<exp (-? E/T) ?
Tidak
Ya Sesuaikan Temperatur T=T0(TN/T0)^(i/N)
Tidak
Apakah N ilai T= TN ? Ya
Tidak
Apakah iterasi maxim um ? Ya SELESAI
Gambar
2.
Flowchart Annealing
Algoritma
KESIMPULAN
Simulated
-101-
copyright @ DTE FT USU
SINGUDA ENSIKOM
6.
VOL. 9 NO. 2/November 2014
DAFTAR PUSTAKA
[1] Fuadi Arimal.2009.Konsep Dasar Telekomunikasi Seluler. http://fuadiarimal.blogspot.com/2009/05/konsep-dasartelekomunikasi-seluler.html. Diakses pada 3 Oktober 2013.Medan. [2] Sirait.2008.Modul3 Komunikasi Bergerak. http://siraits.files.wordpress.com/2008/03/mo dul-3-komunikasi-bergerak.pdf. Diakses pada 3 Oktober 2013.Medan. [3] Anonim. http://www.google.com/search?q=penugasan +kanal&ie=utf-8&oe=utf&aq=t&rls=org.mozilla:enUS:official&client =firefox&channel=sb#channel=sb&q=strateg i+pengalokasian+kanal+pada+seluler&rls=or g.mozilla:en-4. US:official. Diakses pada 3 Oktober 2013.Medan. [4] Sivarajan.KN.1990.Dynamic Channel Assignment in Celluler Radio.http:// http://authors.library.caltech.edu/31390/1/SI Vvtc90.pdf. Diakses pada 10 Oktober 2013.Medan. [5] Usmardi.2012.Jurnal1. http://usmardi70.files.wordpress.com/2012/0 2/jurnal1.pdf. Diakses pada 11 November 2013.Medan. [6] Wikipedia.Simulated_annealing. http://id.wikipedia.org/wiki/Simulated_anneal ing. Diakses pada 21 Januari 2014.Medan. [7] Basuki Ahmad,Budi Tri Santoso,dan Hada Miftahul.Modeling dan Simulasi.IPTAQ Mulia Media.Cetakan pertama.2001.Jakarta Selatan
-102-
copyright @ DTE FT USU
