ISSN : 2302-3805
Seminar Nasional Teknologi Informasi dan Multimedia 2015 STMIK AMIKOM Yogyakarta, 6-8 Februari 2015
EVALUASI PENGGUNAAN ALGORITMA GENETIKA UNTUK MENYELESAIKAN PERSOALAN PENGALOKASIAN RESOURCE BLOCK PADA SISTEM LTE ARAH DOWNLINK Josia Ezra1), Arfianto Fahmi2), Linda Meylani3) 1), 2), 3)
School of Electrical Engineering, Telkom University Jl Telekomunikasi No. 1, Bandung, 40257 Email :
[email protected]),
[email protected]),
[email protected])
Abstrak Pada penelitian ini dievaluasi proses alokasi resource pada sistem OFDMA arah downlink yang terdapat pada teknologi LTE. Algoritma yang digunakan untuk melakukan alokasi resource adalah Algoritma Genetika. Algoritma Genetika adalah metode pemecahan masalah dalam masalah optimasi dengan menggunakan prinsip seleksi alam. Penggunaan Algoritma Genetika pada pengalokasian Resource Block bertujuan untuk meningkatkan efisiensi penggunaan resource sehingga dapat menyediakan bandwidth yang lebih lebar kepada user dan meningkatkan throughput sistem. Dari hasil simulasi terlihat bahwa dengan penggunaan Algoritma Genetika, sistem dengan bandwidth 20MHz memiliki efisiensi 74,286% lebih tinggi 21,715% dibanding dengan penggunaan bandwidth 10 MHz yang memiliki efisiensi 52,571%. Kata kunci:OFDMA, resource allocation, Algoritma Genetika. 1. Pendahuluan Pesatnya peningkatan kebutuhan komunikasi bergerak mengakibatkan adanya tuntutan untuk meningkatkan kualitas layanan komunikasi. Pengembangan teknologi komunikasi menjadi solusi guna memenuhi kebutuhan tersebut. Teknologi yang sedang berkembang saat ini adalah teknologi bernama LTE (Long Term Evolution), dimana teknologi ini menyediakan kualitas layanan dengan kecepatan akses yang tinggi dan kapasitas bandwidth yang besar. Pada teknologi ini digunakan teknik multiplexing berupa OFDM(Orthogonal Frequency-Division Multiplexing)[1]. Dibutuhkan suatu teknik pengalokasian untuk mengoptimasi performa sistem LTE karena adanya keterbatasan sumber daya radio. Pada penelitian ini digunakan Algoritma Genetika sebagai teknik pengalokasian sumber daya radio. Algoritma Genetika merupakan metode untuk mencari nilai optimasi dengan menggunakan prinsip seleksi alam[5]. Dengan memanfaatkan prinsip Algoritma Genetika yaitu dengan menerapkan proses pindah silang dan mutasi untuk mendapatkan individu terbaik, persoalan pada
pengalokasian resource dipecahkan[4].
pada
sistem
LTE
dapat
Pada penelitian sebelumnya yang telah dilakukan oleh Hsien-Wei Tseng[4], telah dilakukan penggunaan algoritma genetika untuk meningkatkan efisiensi sumber daya radio serta meningkatkan throughput dan data rate pada sistem. Selain pada operasi single-carrier, alokasi resource menggunakan Algoritma Genetika juga diaplikasikan pada operasi multicarrier. Dari hasil pengalokasian didapatkan bahwa pada operasi multicarrier proses alokasi resource akan menjadi lebih efektif. Penelitian ini mengevaluasi simulasi algoritma alokasi resource berdasarkan pada[4] pada sistem OFDMA arah downlink pada sistem LTE FDD. Parameter yang akan dianalisis pada penelitian ini adalah throughput dan efisiensi sistem dengan menggunakan bandwidth 10 MHz dan 20 MHz. Penelitian ini tersusun dari beberapa bagian. Bagian 2 memperkenalkan sistem LTE dengan struktur radio frame mengacu pada [1][2][3]. Pada bagian 3 dibahas tentang Algoritma Genetika dan komponen yang terdapat didalamnya[5]. Bagian 4 mempelajari bagaimana penggunaan Algoritma Genetika sebagai proses alokasi resource pada penelitian ini[4]. Pada bagian 5 dilakukan pengujian dan analisis terhadap hasil simulasi proses alokasi resource menggunakan Algoritma Genetika, dan kesimpulan dipaparkan pada bagian 6. 2. Sistem LTE Sistem LTE adalah sebuah set spesifikasi sistem yang dikembangkan oleh 3GPP (Third-Generation Partnership Project). LTE menggunakan OFDMA (Orthogonal Frequency Division Multiple Access) sebagai teknologi multiple access pada arah downlink dan SC-FDMA pada arah uplink. Frekuensi yang digunakan pada sistem LTE berkisar antara 1.4 MHz sampai 20 MHz. Antena yang digunakan pada sistem LTE dibuat dapat mendukung multi-input multi-output (MIMO) dan sistem LTE juga mendukung mode TDD (time division duplex), FDD (frequency division duplexing), dan H-FDD (half-duplex frequency division duplex) [1].
5.5-43
Seminar Nasional Teknologi Informasi dan Multimedia 2015
ISSN : 2302-3805
STMIK AMIKOM Yogyakarta, 6-8 Februari 2015
Pada sistem LTE, informasi diatur dalam domain frekuensi dan waktu menggunakan resource grid. Sebuah RE (Resource Element) memiliki rentang 1 symbol dan 1 subcarrier yang membawa physical channel bits yang besarnya tergantung pada modulasi yang digunakan. Kumpulan dari beberapa RE membentuk RB (Resource Block). Sebuah RB memiliki rentang 0.5 ms (1 slot) dan 180KHz (12 subcarriers). Pada sebuah slot terdapat 7 OFDM symbol pada normal CP (cyclic prefix) atau 6 OFDM symbol pada extended CP[1].
menggunakan metode Roullete Wheel Selection atau metode Tournament Selection. Metode Roullete Wheel Selection mirip dengan permainan Russian Roullete[5].
Gambar 3.Metode Roullete Wheel Selection[4] Seperti terlihat pada gambar 3, semakin besar nilai fitness suatu kromosom maka kemungkinan terpilih kromosom tersebut akan semakin tinggi. Pindah Silang adalah salah satu komponen pada Algoritma Genetika yang paling penting. Pindah Silang dilakukan dengan “mengawinkan” kedua kromosom yang terpilih pada proses seleksi orang tua. Komponen Algoritma Genetika berikutnya adalah mutasi. Mutasi dapat dilakukan dengan memanipulasi nilai pada kromosom. Pada gambar 4 terlihat proses mutasi 1 titik pada kromosom tipe binary[4]. Gambar 1.Resource Grid dan Resource Block [1] Struktur radio frame pada LTE FDD dibagi menjadi kumpulan subframe dan frame. Sebuah radio subframe terdiri dari 2 slot berdurasi masing-masing 0.5 ms dan sebuah frame terdiri dari 10 subframe berdurasi masingmasing 1 ms[1]. Untuk lebih jelasnya dapat dilihat pada gambar 2. Pada mode FDD, user device dapat mengirim dan menerima secara bersamaan [4].
Gambar 2.Struktur Radio Frame pada mode FDD [1] 3. Algoritma Genetika Algoritma Genetika (AG) merupakan metode yang digunakan untuk mencari nilai optimasi pada sebuah sistem. Algoritma ini menggunakan prinsip seleksi alam, yakni seleksi dan evolusi untuk menghasilkan beberapa solusi dari masalah yang ada[5]. Pada Algoritma Genetika terdapat beberapa komponen salah satunya adalah fitness. Nilai fitness menunjukkan ukuran performansi, semakin besar nilai fitness maka semakin besar kemungkinan individu itu terpilih menjadi orang tua untuk generasi berikutnya. Terdapat 2 metode yang biasanya dilakukan untuk seleksi orang tua yaitu
5.5-44
Gambar 4.Mutasi pada Kromosom Tipe Binary [4]
ISSN : 2302-3805
Seminar Nasional Teknologi Informasi dan Multimedia 2015 STMIK AMIKOM Yogyakarta, 6-8 Februari 2015
4. Algoritma Pengalokasian Resource Block Menggunakan Algoritma Genetika Mulai
Inisiasi Populasi
Gambar 6.Inisialisasi Populasi Cek Fitness
b.
Cek Fitness
Nilai fitness adalah banyaknya sisa resource yang dihitung dengan metode back-calculation, dimulai dari resource paling akhir hingga bertemu dengan user [4].
Seleksi Orang Tua
Pindah Silang
Mutasi
Gambar 7.Fungsi Nilai Fitness ya
c.
Generasi <= 20
Untuk Seleksi Orang Tua digunakan metode Roullete Wheel seperti pada [4]. Semakin besar fitness kromosom maka kemungkinan terpilih sebagai orang tua untuk generasi berikutnya akan semakin besar seperti terlihat pada gambar 3.
tidak
Pemilihan Kromosom Terbaik
d. User berikutnya masuk
user <= 50
Pindah Silang
Pindah Silang dilakukan dengan cara memilih user secara acak dari masing-masing kromosom orang tua yang terpilih. Lakukan pemindahan lokasi user pada kedua kromosom, user kromosom 1 sesuai dengan lokasi user yang sama pada kromosom 2 dan sebaliknya dengan tetap mempertahankan bentuk masing-masing user(pemakaian RB oleh user)[4]. Gambar 8 menunjukkan proses pindah silang antar user 1 pada kromosom 1 dengan user 1 pada kromosom 2.
ya
tidak End
Gambar 5.Flowchart Sistem Terlihat pada gambar 5 proses pengalokasian RB menggunakan Algoritma Genetika. Langkah-langkah yang harus dijalani adalah : a.
Seleksi Orang Tua
Inisialisasi Populasi
Sebuah populasi terdiri dari beberapa kromosom dengan solusi permasalahan yang berbeda-beda[5]. Contoh Inisialisasi Populasi dapat dilihat pada gambar 6.
5.5-45
ISSN : 2302-3805
Seminar Nasional Teknologi Informasi dan Multimedia 2015 STMIK AMIKOM Yogyakarta, 6-8 Februari 2015
Gambar 11.Generasi Baru g.
Penginputan User berikutnya
Setelah proses Algoritma Genetika selesai, berikutnya dapat masuk kedalam sistem[4].
user
Gambar 8.Proses Pindah Silang e.
Mutasi
Proses Mutasi dilakukan dengan cara memilih user secara acak, setelah itu lokasi user ini dipindahkan secara acak dengan dengan tetap mempertahankan bentuk user (pemakaian RB oleh user)[4]. Pada gambar 9 ditunjukkan contoh mutasi user 1 pada kromosom 1.
Gambar 12.Proses Masuknya User Berikutnya Setelah Kalkulasi Algoritma Genetika
Gambar 9.Proses Mutasi f.
Pemilihan Kromosom Terbaik
Semua proses diatas dilakukan hingga akhirnya didapatkan hasil kromosom dengan penempatan data user yang lebih rapat[4]. 5. Pengujian dan Analisis Pengujian dilakukan dengan membandingkan nilai throughput dengan bandwidth yang berbeda. Pengujian dilakukan hanya pada arah downlink. Tabel 1 menunjukkan tipe layanan, data rate, dan probabilitas layanan. Tabel 2 menunjukkan parameter simulasi dengan mode FDD.
Gambar 10.Proses Pemilihan Kromosom Terbaik Dilakukan proses pemilihan kromosom terbaik untuk mendapatkan generasi baru. Kromosom terbaik diambil dari kromosom dengan nilai fitness tertinggi[5]. Terlihat pada gambar 10, kromosom 1 memiliki nilai fitness lebih kecil dari fitness kromosom 2 sehingga kromosom 2 yang terpilih menjadi generasi baru seperti pada gambar 11.
Tabel 1.Tabel Tipe Layanan dan Rasio Transmisi Data[4] Layanan VOIP Video FTP HTTP Stream (DL) Data rate 64 256 2000 128 (kbps) Rasio 50 20 10 20 (%)
5.5-46
ISSN : 2302-3805
Seminar Nasional Teknologi Informasi dan Multimedia 2015 STMIK AMIKOM Yogyakarta, 6-8 Februari 2015
Tabel 2.Parameter Simulasi[4] Parameter Simulasi Jumlah User 50 Generasi 20 Bandwidth 10 MHz ; 20MHz Jumlah Subcarrier 600 ; 1200 Jumlah RB 50 ; 100 Subcarrier Spacing 15 KHz Duplex FDD Modulasi QPSK Coding Rate 1/3 Cyclic Prefix Normal Konfigurasi Antena MIMO 2x2
Setelah mendapatkan data rate per PRB, maximum throughput dapat diketahui dengan menggunakan persamaan (2) mengacu pada [7] : ℎ
Analisis efisiensi sistem dapat dilakukan dengan mengetahui maximum throughput sistem. Untuk mendapatkan maximum throughput yang pertama dilakukan adalah menghitung data rate per PRB menggunakan persamaan (1) seperti pada [6] :
( )
)
∑
( )
( )
.....(2)
×
=
ℎ
ℎ
/
ℎ
ℎ
.....(3)
Tabel 3.Perbandingan Throughput Sistem Dengan Bandwidth 10 MHz dan 20 MHz (FDD mode, 50 users) Bandwidth Throughput Efisiensi (MHz) (kbps) (%) 10 4416 52,571 20 12480 74,286 Dari hasil simulasi yang dilakukan terlihat bahwa semakin besar bandwidth yang digunakan, maka akan semakin besar pula throughput sistem. Hal ini disebabkan karena dengan menggunakan Algoritma Genetika, penggunaan resource menjadi semakin efektif sehingga sistem dapat menyediakan resource lebih banyak. Semakin rapatnya data user membuat data user yang dapat masuk ke dalam sistem menjadi lebih banyak dan akhirnya meningkatkan throughput sistem. Penggunaan bandwidth yang semakin lebar juga mempengaruhi efisiensi sistem. Semakin besar bandwidth yang digunakan maka efisiensi sistem akan semakin tinggi.
Semakin besarnya bandwidth yang disediakan mengakibatkan semakin banyaknya user yang bisa dilayani. Penggunaan Algoritma Genetika pada proses alokasi resource membuat posisi user lebih rapat sehingga mengakibatkan resource yang tersedia untuk melayani user meningkat. Hal ini mengakibatkan adanya peningkatan throughput sistem saat Algoritma Genetika diaplikasikan pada proses alokasi resource.
(
×
Setelah maximum throughput diketahui, efisiensi sistem dapat diketahui dengan menggunakan persamaan (3):
Gambar 13.LTE FDD throughput dengan BW 10 MHz dan 20 MHz
( )
=
Dimana N merupakan jumlah RB dan Rtx merupakan jumlah antenna MIMO yang digunakan.
Gambar 11 menunjukkan hasil simulasi untuk LTE FDD saat Algoritma Genetika digunakan untuk pengalokasian RB pada bandwidth 10 MHz dan 20 MHz.
=
ℎ
......(1)
adalah subcarrier yang dapat digunakan untuk membawa data. merupakan OFDM symbol dalam domain waktu. adalah code rate dimana ∈ {1,2, … . . , } dan J adalah total MCS. merupakan ukuran konstelasi dan merupakan OFDM symbol.
6. Kesimpulan Pada penelitian ini dilakukan analisis pengaruh penggunaan Algoritma Genetika pada pengalokasian RB pada sistem LTE terhadap performansi sistem. Terbukti bahwa penggunaan Algoritma Genetika meningkatkan efektivitas penggunaan resource dengan cara merapatkan data user. Penggunaan Algoritma Genetika juga meningkatkan performansi sistem. Tabel 3 memperlihatkan perbandingan throughput sistem menggunakan bandwidth 10 MHz dan 20 MHz. Terlihat bahwa pada proses pengalokasian RB menggunakan Algoritma Genetika, semakin besarnya bandwidth mengakibatkan peningkatan pada throughput dan efisiensi sistem. Sistem dengan bandwidth 20MHz memiliki efisiensi 74,286% lebih tinggi 21,715% dibanding dengan penggunaan bandwidth 10 MHz yang memiliki efisiensi 52,571%. Daftar Pustaka
5.5-47
[1] C. Cox, An introduction to LTE : LTE, LTE-advanced, SAE and 4G mobile communications, Wiley, 2012.
Seminar Nasional Teknologi Informasi dan Multimedia 2015 STMIK AMIKOM Yogyakarta, 6-8 Februari 2015
[2] "Physical Layer Procedurces(Release 8)," 3GPP TS 36.213 v8.6.0, Apr.2009. [3] "Base Station (BS) radio tranmission and reception(Release 8)," 3GPP TS 36.104 v8.5.0, Mar.2009. [4] W.-C. L. C.-R. S. Y.-H. L. Y.-G. J. Hsien-Wei Tseng, "Applying Genetic Algorithms to the Data Traffic Scheduling and Performance Analysis of a Long-Term Evolution System," 2012. [5] Suyanto, Algoritma Genetika dalam MATLAB, Yogyakarta: ANDI, 2005. [6] N. Guan, Y. Zhou, L. Tian, G. Sun and J. Shi, "QoS Guaranteed Resource Block Allocation Algorithm for LTE Systems,"IEEE 7th International Conference on Wireless and Mobile Computing, Networking and Communications, pp. 307-312, 2011 [7] N. M. N. C. S. M. Sonia Rathi, "Throughput for TDD and FDD 4G LTE Systems," vol. 3, no. 12, 2014.
Biodata Penulis Josia Ezra, Jurusan Teknik Telekomunikasi Universitas Telkom Bandung. Saat ini menjadi mahasiswa di Universitas Telkom Bandung. Arfianto Fahmi,memperoleh gelar Sarjana Teknik (S.T), Jurusan Teknik Telekomunikasi Telkom University Bandung, lulus tahun 1998. Memperoleh gelar Magister Teknik (M.T), Jurusan Teknik Elektro Institut Teknologi Bandung, lulus tahun 2004. Memperoleh gelar Doktor (Ph.D), Jurusan Teknik Elektro Universitas Indonesia Depok, lulus tahun 2013. Saat ini menjadi Dosen di Telkom University Bandung. Linda Meylani, menyelesaikan pendidikan sarjana tahun 2002 dan magister pada tahun 2006 di Sekolah Tinggi Teknologi Telkom jurusan Teknik Elektro Telekomunikasi. Saat ini menjadi salah satu dosen pada Universitas Telkom, Bandung.
5.5-48
ISSN : 2302-3805
