BAB II TEORI DASAR 2.1
Teknologi Long Term Evolution LTE (Long Term Evolution) adalah sebuah nama baru dari layanan yang
mempunyai kemampuan tinggi dalam sistem komunikasi bergerak (mobile). LTE merupakan standar komunikasi dasar nirkabel tingkat tinggi yang didasarkan pada jaringan GSM/EDGE. Teknologi LTE adalah langkah evolusi lanjutan dari 3GPP (Third Generation Partnership Project) menuju generasi 4G dari teknologi radio yang dirancang untuk meningkatkan kapasitas dan kecepatan jaringan telepon mobile. LTE memberikan kemampuan dalam pengiriman data mencapai kecepatan 300 Mbit/s untuk downlink dan 75 Mbit/s untuk uplink. Bandwidth LTE beroperasi pada 1,4 MHz hingga 20 MHz. Kecepatan ini dapat dicapai dengan menggunakan Orthogonal Frequency Division Multiplexing (OFDM) pada downlink dan Single Carrier Frequency Division Multiplex (SC-FDMA) pada uplink, yang digabungkan dengan penggunaan MIMO. Teknologi LTE dirancang untuk menyediakan efisiensi spektrum yang lebih baik, peningkatan kapasitas radio, latency dan biaya operasional yang rendah bagi operator serta layanan pita lebar nirkabel bergerak kualitas tinggi untuk pengguna. Parameter LTE dapat dilihat pada Tabel 2.1
5
http://digilib.mercubuana.ac.id/
Tabel 2.1 Parameter LTE [8]
2.1.1 Arsitektur Jaringan Long Term Evolution Arsitektur jaringan Long Term Evolution (LTE) dirancang untuk tujuan mendukung trafik paket switching dengan mobilitas tinggi, Quality of Service (QOS), dan latency yang kecil. Pendekatan paket switching ini memperbolehkan semua layanan termasuk layanan voice menggunakan koneksi paket. Oleh karena itu pada arsitektur jaringan LTE dirancang sesederhana mungkin, yaitu hanya terdiri dari dua node yaitu eNode B dan Mobility Management Entity/Gateway (MME/GW). Hal ini sangat berbeda dengan arsitektur teknologi GSM dan UMTS yang memiliki struktur lebih kompleks dengan adanya Radio Network Controller (RNC). Beberapa keuntungan yang dapat diperoleh dengan hanya adanya single node pada jaringan akses adalah pengurangan latency dan distribusi beban proses RNC untuk beberapa eNode B. Bentuk arsitektur LTE dapat dilihat pada Gambar 2.1.
6
http://digilib.mercubuana.ac.id/
Gambar 2.1 Bentuk Arsitektur LTE [8]
Jaringan LTE terdiri tiga komponen penting yaitu User Equipment (UE), Evolved Universal Terrestrial Radio Access Network (E-ULTRAN) dan Evolved Packet Core (EPC). Berikut ini adalah penjelasan dari masing-masing komponen jaringan LTE. 1. User Equipment (UE) User Equioment (UE) adalah perangkat komunikasi yang terletak paling ujung dan dekat dengan pengguna. Dua bagian penyusun UE yaitu Mobile Equipment (ME) dan Universal Integrated Circuit Card (UICC). 2. Evolved UMTS Terrestrial Radio Access Network (E-UTRAN) Evolved UMTS Terrestrial Radio Access Network (E-UTRAN) adalah sistem arsitektur jaringan LTE yang berfungsi menangani sisi radio akses dari UE ke jaringan core. E-UTRAN memiliki satu komponen penting yaitu Evolved Node B (eNode B). eNode B adalah antar-muka jaringan LTE dengan pengguna. Pada jaringan GSM dikenal sebagai BTS. Pada eNode B memungkinkan dilakukan protocol air interface user plan dan control plane secara bersama-sama dalam satu unit tersebut.
7
http://digilib.mercubuana.ac.id/
eNode B mempunyai dua interface yaitu S1 dan X2. Interface S1 digunakan untuk hubungan dengan EPC. Sedangkan interface X2 digunakan untuk hubungan langsung antar eNode B. Interface X2 merupakan suatu logical interface yang berfungsi untuk mendukung akses komunikasi dan penerusan paket trafik pada saat UE melakukan handover. Ada dua tugas penting dari sebuah eNode B, yaitu sebagai radio pengirim (transmitter) dan penerima (reciever), serta mengontrol low-level operation semua mobile user dengan cara mengirim suatu sinyal tertentu berupa pesan seperti pada saat handover. 3. Evolved Packet mobile, karena Core (EPC) Core Network pada Evolved Packet Core (EPC) menggunakan all-IP yaitu sebuah kerangka konvergensi yang berbasis packet realtime dan layanan non-realtime yang dibentuk oleh 3GPP Release 8 standar. Pada generasi kedua (2G) dan ketiga (3G), EPC menyediakan fungsionalitas core mobile yang memiliki dua bagian terpisah sub-domain yaitu Circuit-Switch (CS) untuk voice dan Packet-Switch (PS) untuk data. Sedangkan pada LTE, pengolahan dan switching antara mobile voice dan data akan bersatu dalam sebuah IP tunggal. LTE akan menjadi sistem dari end-to-end nya akan menggunakan IP yaitu dari eNode B, EPC, dan sampai domain aplikasi (IMS atau non-IMS). Dengan adanya EPC yang memiliki performansi yang tinggi dan kapasitas yang besar pada all-IP di core network membuat LTE mampu memberikan layanan realtime yang lebih baik dan layanan media yang dapat meningkatkan Quality of Experience (QoE). EPC dengan arsitektur jaringan all-IP dalam mobile network akan berimplikasi pada: 1. Layanan semua komunikasi baik suara, data dan media akan menjadi satu pada protokol IP. 2. Interworking arsitektur baru. 3. Skalabilitas yang besar untuk mengatasi peningkatan jumlah besar untuk koneksi langsung ke pengguna, pelipatan penggunaan bandwidth, serta mobilitas terminal yang bergerak dinamis.
8
http://digilib.mercubuana.ac.id/
EPC terdiri dari beberapa bagian sebagai berikut: 1. eNode B Jaringan akses pada LTE terdiri dari suatu elemen, yaitu eNode B. eNode B merupakan interface dengan UE (User Equipment). eNode B berfungsi untuk Radio Resurce Management (RRM) dan sebagai transceiver. RRM sendiri berfungsi untuk mengontrol dan mengawasi pengiriman sinyal yang dibawa oleh sinyal radio, berperan dalam autentikasi atau mengontrol kelayakan data yang akan melewati eNode B serta mengatur scheduling.
Gambar 2.2 eNode B [5]
2. Mobility Management Entity (MME) Mobility Management Entity (MME) merupakan pengontrol setiap node pada jaringan akses LTE. MME dapat dianalogikan sebagai MSC pada jaringan GSM. Pengoperasiannya hanya pada control plane dan tidak meliputi user plane. MME memiliki koneksi control plane secara langsung pada UE. Koneksi tersebut digunakan primary control channel antara UE dan Jaringan. MME memiliki tiga fungsi utama yaitu Authentication dan Security, mobility Management (menjaga jalur lokasi semua yang berada pada service area) dan Managing Subcription dan Service Connectivity (bertanggung jawab mendapatkan kembali profil pelanggan dari home network). MME bertanggung jawab untuk prosedur paging untuk idle mode UE termasuk retransmisi dan dalam proses aktivas/daktivasi dan autentikasi user (dengan bantuan HSS). MME juga berfungsi untuk mengatur handover, yaitu
9
http://digilib.mercubuana.ac.id/
memilih MME lain untuk handover dengan MME lain atau memilih SGSN untuk handover dengan jaringan akses 2G / 3G.
Gambar 2.3 MME [5]
3. Serving Gateway (S-GW) Serving Gateway (SGW) terdiri dari dua bagian yaitu 3GPP Anchor dan SAE Anchor. 3GPP Anchor berfungsi sebagai gateway paket data yang berasal dari jaringan 3GPP, sedangkan SAE Anchor berfungsi sebagai gateway jaringan non3GPP. SGW merutekan dan memforward paket data user, ini juga berfungsi sebagai mobility anchor saat handover antar eNode B dan untuk menghubungkan LTE dengan jaringan lain yang sudah ada. Serving Gateway (S-GW) berfungsi sebagai jembatan antara manajemen dan switching user plane. Sebagai fungsi pengontrolan, S-GW hanya bertanggung jawab pada sumbernya sendiri dan mengalokasikannya berdasarkan permintaan MME, P-GW atau PCRF yang memerlukan set up, modifikasi, atau penjelasan pada UE. Pada LTE, S-GW berfungsi mengatur jalan dan meneruskan paket dari setiap user, penghubung UE dengan eNode B pada saat terjadi inter-handover dan penghubung teknologi LTE dengan teknologi 3GPP yang lain (2G dan 3G).
10
http://digilib.mercubuana.ac.id/
Gambar 2.4 S-GW [5]
4. Home Subscriber Server (HSS) Home Subcriber Server (HSS) merupakan sistem database yang menyimpan data pelanggan untuk semua data permanen user. Selain itu, HSS juga menyimpan lokasi user pada level yang dikunjungi node pengontrol jaringan. HSS menyimpan copy master profil pelanggan yang berisi informasi tentang layanan yang layak untuk user, termasuk informasi koneksi PDN apakah roaming ke jaringan tertentu atau tidak. Kunci permanen yang digunakan untuk menghitung pada arah authentication yang dikirim ke jaringan yang dituju untuk authentication user dan memperoleh serangkaian kunci untuk enkripsi dan perlindungan secara integritas yang disimpan pada Authentication Center (AuC). 2.1.2
Long Term Evolution Air Interface Pada sisi air interface transmisi dalam arah downlink dan uplink berbeda.
Pada arah downlink teknik akses yang digunakan adalah Orthogonal Frequency Division Modulation Access (OFDMA) dan pada arah uplink teknik akses yang digunakan adalah Single Carrier Frequency Division Multiple Access (SC-FDMA). OFDMA adalah variasi dari Orthogonal Frequency Division Modulation (OFDM). Pada teknik OFDM subcarrier adalah orthogonal sehingga akan menghemat
11
http://digilib.mercubuana.ac.id/
spektrum frekuensi dan setiap subcarrier tidak akan saling mempengaruhi. MIMO (Multiple Input Multiple Output ) digunakan untuk meningkatkan data rate pada teknologi seluler untuk menyediakan peningkatan tingkat efesiensi, MIMO multiple
menggunkan
antena
pada
receiver
transmitter
dan
untuk
memanfaatkan multi-path effect yang selalu ada untuk mentrasmisikan data tambahan. Akan tetapi salah satu kelemahan teknik akses ini adalah tingginya Peak Average Power Ratio (PAPR) yang dibutuhkan. Tingginya PAPR dalam OFDM membuat 3GPP melihat skema teknik akses yang berbeda pada arah uplink karena akan sangat mempengaruhi konsumsi daya sehingga pada arah
uplink LTE
menggunakan
teknik
teknik
SC-FDMA.
SC-FDMA
dipilih
karena
ini
mengkombinasikan keunggulan PAPR yang rendah dengan daya tahan terhadap gangguan lintasan jamak dan alokasi frekuensi yang fleksibel dari OFDMA.
2.2
Perencanaan Sel Long Term Evolution
2.2.1
Perencanaan Berdasarkan Kapasitas
Berikut ini tahapan dalam perencanaan kapasitas sel LTE: 1. Menentukan lokasi dan potensi wilayah serta permintaan pelanggan yang akan dicakup oleh LTE. 2. Menentukan jumlah pelanggan layanan Long Term Evolution Jaringan yang dibangun digunakan dalam kurun waktu yang lama. Dalam periode tertentu, untuk mengantisipasi pertumbuhan pelanggan yang semakin meningkat maka diperlukan estimasi pertumbuhan pelanggan dengan persamaan sebagai berikut : Un = Uo (1 + fp)n...................................................................(2.1) [8] Keterangan : Un
= Jumlah total pengguna setelah tahun ke-n
Uo
= Jumlah pengguna saat perencanaan
fp
= Faktor pertumbuhan
n
= Jumlah tahun prediksi
12
http://digilib.mercubuana.ac.id/
3. Menentukan kapasitas trafik LTE berdasarkan Offered Bit Quantity (OBQ) Pada tahap memperkirakan besar kebutuhan suatu trafik merupakan hal yang penting dalam jaringan radio. Di dapatnya besar kebutuhan suatu trafik selanjutnya memudahkan dalam perencanaan kapasitas suatu jaringan optimal yang nantinya akan dibangun, selain itu dapat diketahui juga seberapa banyak perangkat eNode B yang diperlukan untuk memenuhi kebutuhan trafik pada suatu daerah. Perhitungan total kebutuhan trafik yang diperlukan dapat dihitung menggunakan metode Offered Bit Quantity (OBQ). OBQ merupakan total bit throughput per km2 pada jam sibuk. Dimana persamaan perhitungan OBQ adalah sebagai berikut : OBQ = σ.p.d.BHCA.BW.......................................................(2.2) [8] Keterangan : σ
= kepadatan pelanggan potensial dalam suatu daerah (user/km2)
p
= penetrasi pengguna tiap layanan
d
= durasi atau lama panggilan efektif (s)
BHCA = Busy Hour Call Attempt (call/s) = Bandwidth tiap layanan (Kbps)
BW 4. Pendimensian sel
Pada tahap pendimensian suatu sel ini bertujuan untuk menentukan berapa jumlah sel yang dibutuhkan dalam suatu daerah untuk satu frekuensi carrier. Pendimensian sel meliputi : a.
Luas Cakupan Satu Sel Untuk menentukan luas cakupan satu sel dapat di hitung dengan menggunakan persamaan berikut : .................................................................(2.3)[8] Keterangan : L
= luas cakupan satu sel (km2)
KSel = kapasitas informasi tiap sel
13
http://digilib.mercubuana.ac.id/
OBQ = Offered Bit Quantity b. Penentuan Jumlah Sel Untuk menentukan berapa jumlah sel yang dibutuhkan untuk memberi cakupan yang optimal pada suatu wilayah sesuai kebutuhan trafik pada wilayah tersebut dapat dihitung dengan menggunakan persamaan berikut : …...............................................................(2.4)[8] Keterangan : J
= jumlah sel
LW = luas area atau luas wilayah (km2) L c.
= luas cakupan satu sel
Penentuan Radius Sel Untuk menentukan radius yang dihasilkan dari setiap sel dapat dihitung dengan menggunakan persamaan berikut : ….................................................................(2.5)[8] Keterangan : Rsel = radius sel L
2.2.2
= luas cakupan satu sel
Perencanaan Berdasarkan Coverage
Berikut ini tahapan – tahapan dalam perencanaan coverage sel LTE 1. Link Budget Link budget merupakan sebuah cara untuk menghitung mengenai semua parameter dalam transmisi sinyal, mulai dari gain dan losses dari Tx sampai Rx melalui media transmisi. Link merupakan parameter dalam merencanakan suatu jaringan yang menggunakan media transmisi berbagai macam. Link budget 14
http://digilib.mercubuana.ac.id/
dihitung berdasarkan jarak antara transmitter (Tx) dan receiver (Rx). Link budget dihitung karena adanya penghalang antara Tx dan Rx misal gedung atau pepohonan. Link budget juga dihitung dengan melihat spesifikasi yang ada pada antena. 2. Path Loss Model Path Loss adalah loss yang terjadi ketika data/sinyal melewati media udara dari antena ke penerima dalam jarak tertentu. Path loss mengakibatkan penurunan level daya pada sisi penerima yang secara umum diakibatkan dengan adanya difraksi, refleksi, dan scattering. Selain itu path loss juga dipengaruhi oleh kondisi lingkungan, kontur wilayah, jarak antara transmitter dan receiver, serta tinggi dan penempatan antena. Model Propagasi Okumura Hata Model propagasi Okumura Hata adalah empiris dari rugi-rugi propagasi yang telah diajukan. Rugi-rugi propagasi rata-rata didaerah urban dinyatakan dengan persamaan : LProp City=69,55 + 26,16 log f – 13,83 log htx – a(Hrx) + (44,9 – 6,55 log htx) log rsel…....................................................................(2.6)[8] Keterangan : L
= Maximum allowable pathloss (dB)
f
= Frekuensi (MHz)
htx
= Tinggi antena tx (m)
a(Hrx) = Penguatan path loss (dB) rsel
= Jari-jari sel (Km)
15
http://digilib.mercubuana.ac.id/
3. Penentuan jumlah eNode B. Penentuan jumlah eNode B dapat dilakukan setelah mengetahui radius
luas
cakupan dari masing – masing sel. Penentuan jumlah eNode B dapat dilakukan dengan persamaan : …………….(2.7)[8]
2.3
Perancangan Elemen Jaringan pada EPC Pada saat penelitian ini dilakukan, provider belum menggunakan IP
Multimedia Subsystem (IMS), dan belum menggunakan Voice over LTE (VoLTE). Dalam penelitian ini batasan masalahnya dimensioning elemen network yang termasuk dalam Evolved Packet Core (EPC) baik yang menggunakan 4G LTE atau CS fallback. Beberapa elemen jaringan pada EPC dan proses dimana dimensioningnya dijabarkan sebagai berikut : 2.3.1 MSS Dalam dimensioning MSS, ada beberapa hal yang diperlukan adalah sebagai berikut : MSS = Max
……………..(2.8) [7]
2.3.2 HSS Untuk menentukan jumlah HLR yang diperlukan adalah sebagai berikut : Jumlah HSS
……………………………….(2.9) [7]
2.3.3 MME Untuk menentukan jumlah MME yang diperlukan, perlu dipertimbangakan tiga aspek penting adalah sebagai berikut : MME = Max
…………..(2.10) [7]
16
http://digilib.mercubuana.ac.id/
2.3.4 SGW-PGW Penentuan jumlah S/PGW yang diperlukan adalah sebagai berikut : SGW-PGW = Max
………….(2.11) [7]
2.4
Routing
2.4.1
Konsep dasar routing Routing merupakan proses pencarian jalur dari satu jaringan ke jaringan
lainnya, dimana proses pencarian jalur tersebut harus mempertimbangakan faktor efisiensi dalam proses transmisi. Proses pencarian rute tersebut menggunakan sebuah perangkat yang disebut router. Gambar dibawah mengilustrasikan fungsi sebuah router.
Gambar 2.5 ilustrasi fungsi router [2]
Suatu data yang dikirimkan oleh suatu komputer/stasiun dari sebuah jaringan lokal, akan diteruskan oleh router komputer/stasiun lain pada jaringan lokal tersebut, jika komputer yang dituju berada dalam satu jaringan lokal yang sama dengan pengirim. Akan tetapi, jika alamat yang dituju berada pada jaringan lain, di luar jaringan lokal pengirim, maka router akan meneruskan paket data tersebut ke jaringan lainnya yang merujuk pada alamat yang dituju. Dalam proses pengiriman
17
http://digilib.mercubuana.ac.id/
paket data tersebut, router akan mencari rute terbaik untuk mencapai alamat yang dituju. Setidaknya, ada tiga komponen penting dalam proses routing, yakni: 1. Algoritma Yakni, alur logika dari proses transmisi data, sehingga menghasilkan rute yang paling efisien. Ada beberapa algoritma dalam proses routing. 2. Basis data Yakni, informasi yang tersimpan di dalam routing tabel. 3. Protokol Yakni, cara untuk mendistribusikan dan menyatukan paket data yang dikirim. Routing Tabel Bahwa dalam jaringan WAN kita sering mengenal yang namanya TCP/IP (Transmission Control Protocol/ Internet Protocol) sebagai alamat sehingga pengiriman paket data dapat sampai ke alamat yang dituju (host tujuan). TCP/IP membagi tugas masing-masingmulai dari penerimaan paket data sampai pengiriman paket data dalam sistem sehingga jika terjadi permasalahan dalam pengiriman paket data dapat dipecahkan dengan baik. Berdasarkan pengiriman paket data routing dibedakan menjadi routing lansung dan routing tidak langsung.
Routing langsung merupakan sebuah pengalamatan secara langsung menuju alamat tujuan tanpa melalui host lain. Contoh: sebuah komputer dengan alamat 192.168.1.2 mengirimkan data ke komputer dengan alamat 192.168.1.3
Routing tidak langsung merupakan sebuah pengalamatan yang harus melalui alamat host lain sebelum menuju alamat hort tujuan. (contoh: komputer dengan alamat 192.168.1.2 mengirim data ke komputer dengan alamat 192.1681.3, akan tetapi sebelum menuju ke komputer dengan alamat 192.168.1.3, data dikirim terlebih dahulu melalui host dengan alamat 192.168.1.5 kemudian dilanjutkan ke alamat host tujuan. Dalam melakukan proses transmisi data, sebuah router menggunakan routing
tabel, yakni sebuah tabel yang berisi informasi mengenai topologi jaringan yang ada di sekitar router tersebut, sehingga router dapat menentukan rute transmisi ke suatu alamat yang dituju.
18
http://digilib.mercubuana.ac.id/
Ketika suatu paket data ingin dikirimkan dari stasiun A ke stasiun B, maka router C yang terhubung dengan jaringan lokal dimana stasiun A berada akan melakukan pengecekan terhadap paket data yang dikirimkan, sehingga akan diketahui kemana paket data tersebut akan dikirimkan. Apabila destinasi yang ingin dituju, yakni stasiun B terhubung secara langsung dengan router C, maka router akan melakukan pengiriman langsung ke stasiun B. Namun, jika tidak, maka router C akan mencari rute lain yang yang bisa menghubungkan dirinya dengan router lain yang memiliki
koneksi
dengan
alamat
yang
ingin
dituju.
Gambar
dibawah
mengilustrasikan sebuah routing tabel.
Gambar 2.6 ilustrasikan sebuah routing tabel [2]
Berdasarkan cara pengelolaan routing tabel, routing terbagi menjadi dua macam, yakni static routing dan dynamic routing. Static routing merupakan teknik routing yang routing tabel-nya dikelola secara manual oleh administrator/user. Administrator harus melakukan update pada routing tabel jika terjadi perubahan topologi jaringan. Dynamic routing adalah teknik routing yang routing tabel-nya dikelola sendiri oleh router secara otomatis. Dynamic routing umumnya digunakan untuk jaringan komputer yang luas dan kompleks. 1. Static Routing
19
http://digilib.mercubuana.ac.id/
Routing dapat merujuk kepada sebuah metode penggabungan beberapa jaringan sehingga paket-paket data dapat hinggap dari satu jaringan ke jaringan selanjutnya. Routing dibangun pada jaringan yang memiliki banyak gateway jenis ini hanya memungkinkan untuk jaringan kecil dan stabil. static route akan berfungsi sempurna jika routing tabel berisi suatu route untuk setiap jaringan di dalam internetwork yang mana dikonfigurasi secara manual oleh administrator jaringan. Setiap host pada jaringan harus dikonfigurasi untuk mengarah kepada default route atau default gateway agar cocok dengan IP address dari interface local router, di mana router memeriksa routing tabel dan menentukan router yang mana digunakan untuk meneruskan paket. Cara kerja routing statis dapat dibagi menjadi 3 bagian: 1. Administrator jaringan yang mengkonfigurasi router 2. Router melakukan routing berdasarkan informasi dalam tabel routing 3. Routing statis digunakan untuk melewatkan paket data 4. Seorang administrator harus menggunakan perintah IP route secara manual untuk mengkonfigurasi router dengan routing statis. Langkah-langkah untuk melakukan konfigurtasi routing statis adalah sebagai berikut: 1. Tentukan dahulu prefix jaringan, subnet mask dan address. Address bisa saja interface local atau next hop address yang menuju tujuan. 2. Masuk ke mode global configuration. 3. Ketik perintah IP route dengan prefix dam mask yang diikuti dengan address seperti yang sudah ditentukan di langkah 1. Sedangkan untuk administrative distance bersifat tambahan, boleh digunakan boleh tidak. 4. Ulangi langkah 3 untuk semua jaringan yang dituju yang telah ditentukan pada langkah 1. 5. Keluar dari mode global configuration. 6. Gunakan perintah copy running-config startup-config untuk menyimpan konfigurasi yang sedang aktif ke NVRAM.
20
http://digilib.mercubuana.ac.id/
2. Routing Dinamis Routing protocol adalah berbeda dengan router protocol. Routing protocol adalah komunikasi antara router-router. Routing protocol mengijinkan routerrouter untuk sharing informasi tentang jaringan dan koneksi antar router. Router menggunakan informasi ini untuk membangun dan memperbaiki tabel routingnya. Seperti pada gambar 2.8 Router protocol digunakan untuk trafik user langsung. Router protocol menyediakan informasi yang cukup dalam layer address jaringannya untuk melewatkan paket yang akan diteruskan dari satu host ke host yang lain berdasarkan alamatnya. Contoh router protocol : 1. Internet Protocol (IP) 2. Internetwork Packet Exchange (IPX)
Gambar 2.7 Contoh router protocol dan routing protocol [2]
Contoh routing protocol: 1. Routing Information Protocol (RIP) 2. Interior Gateway Routing Protocol (IGRP) 3. Enhanced Interior Gateway Routing Protocol (EIGRP) 4. Open Shortest Path First (OSPF) 5. Klasifikasi Routing Protocol
21
http://digilib.mercubuana.ac.id/
Sebagian besar algoritma routing dapat diklasifikasikan menjadi satu dari dua kategori berikut : 1. Distance Vector Routing distance vector bertujuan untuk menentukan arah atau vector dan jarak ke link-link lain dalam suatu internetwork. Sedangkan link-state bertujuan untuk menciptakan kembali topologi yang benar pada suatu internetwork.
Gambar 2.8 routing distance vector [2]
Algoritma routing distance vector secara periodik menyalin tabel routing dari router ke router. Perubahan tabel routing ini di-update antar router yang saling berhubunganpada saat terjadi perubahan topologi. Algoritma distance vector juga disebut dengan algoritma Bellman-Ford. Setiap router menerima tabel routing dari router tetangga yang terhubung langsung. Pada gambar di bawah ini digambarkan konsep kerja dari distance vector.
22
http://digilib.mercubuana.ac.id/
Gambar 2.9 konsep kerja dari distance vector [2]
Router B menerima informasi dari Router A. Router B menambahkan nomor distance vector, seperti jumlah hop. Jumlah ini menambahkan distance vector. Router B melewatkan tabel routing baru ini ke router-router tetangganya yang lain, yaitu Router C. Proses ini akan terus berlangsung untuk semua router. Algoritma
ini
mengakumulasi jarak jaringan sehingga dapat digunakan untuk memperbaiki database informasi mengenai topologi jaringan. Bagaimanapun, algoritma distance vector tidak mengijinkan router untuk mengetahui secara pasti topologi internetwork karena hanya melihat router-router tetangganya. Setiap router yang menggunakan distance vector pertama kali mengidentifikasi router- router tetangganya. Interface yang terhubung langsung ke router tetangganya mempunyai distance 0. Router yang menerapkan distance vector dapat menentukan jalur terbaik untuk menuju ke jaringan tujuan berdasarkan informasi yang diterima dari tetangganya. Router A mempelajari jaringan lain berdasarkan informasi yang diterima dari router B. Masing-masing router lain menambahkan dalam tabel routingnya yang mempunyai akumulasi distance vector untuk melihat sejauh mana jaringan yang akan dituju. Seperti yang dijelaskan pada gambar di bawah :
23
http://digilib.mercubuana.ac.id/
Gambar 2.10 akumulasi distance vector [2]
Update tabel routing terjadi ketika terjadi perubahan toplogi jaringan. Sama dengan proses discovery, proses update perubahan topologi step-by-step dari router ke router. Gambar dibawah menunjukkan algoritma distance vector memanggil ke semua router untuk mengirim ke isi tabel routingnya. Tabel routing berisi informasi tentang total path cost yang ditentukan oleh metric dan alamat logic dari router pertama dalam jaringan yang ada di isi tabel routing, seperti yang diterangkan
oleh
gambar
di bawah ini.
Gambar 2.11 Algoritma distance vector memanggil ke semua router untuk mengirim ke isi tabel routingnya [2]
24
http://digilib.mercubuana.ac.id/
Analogi distance vector dapat digambarkan dengan jalan tol. Tanda yang menunjukkan titik menuju ke tujuan dan menunjukkan jarak ke tujuan. Dengan adanya tanda-tanda seperti itu pengendara dengan mudah mengetahui perkiraan jarak yang akan ditempuh untuk mencapai tujuan. Dalam hal ini jarak terpendek adalah rute yang terbaik. 2. Link State Algoritma link-state juga dikenal dengan algoritma Dijakarta atau algoritma shortest path first (SPF). Algoritma ini memperbaiki informasi database dari informasi topologi. Algoritma distance vector memiliki informasi yang tidak spesifik tentang distance network dan tidak mengetahui jarak router. Sedangkan algortima link-state memperbaiki pengetahuan dari jarak router dan bagaimana mereka inter-koneksi. Fitur-fitur yang dimiliki oleh routing link-state adalah: 1. Link-state advertisement (LSA) - adalah paket kecil dari informasi routing yang dikirim antar router 2. Topological database - adalah kumpulan informasi yang dari LSA-LSA 3. SPF algorithm - adalah hasil perhitungan pada database sebagai hasil dari pohon SPF 4. Routing tabel - adalah daftar rute dan interface
Gambar 2.12 Fitur-fitur yang dimiliki oleh routing link-state [2]
25
http://digilib.mercubuana.ac.id/
2.4.2
Proses discovery dari routing link-state Ketika router melakukan pertukaran LSA, dimulai dengan jaringan yang
terhubung langsung tentang informasi yang mereka miliki. Masing-masing router membangun database topologi yang berisi pertukaran informasi LSA. Algoritma SPF menghitung jaringan yang dapat dicapai. Router membangun logical topologi sebagai pohon (tree), dengan router sebagai root. Topologi ini berisi semua rute-rute yang mungkin untuk mencapai jaringan dalam protokol link-state internetwork. Router kemudian menggunakan SPF untuk memperpendek rute. Daftar rute-rute terbaik dan interface ke jaringan yang dituju dalam tabel routing. Link-state juga memperbaiki database topologi yang lain dari elemen-elemen topologi dan status secara detail.
Gambar 2.13 informasi routing dikirim ke semua router [2]
Router
pertama
yang
mempelajari
perubahan
topologi
link-state
melewatkan informasi sehingga semua router dapat menggunakannya untuk proses update. Gambar 2.14 adalah informasi routing dikirim ke semua router dalam internetwork. Untuk mencapai keadaan konvergen, setiap router mempelajari routerrouter tetangganya. Termasuk nama dari router-router tetangganya, status interface dan cost dari link ke tetangganya. Router membentuk paket LSA yang mendaftar informasi ini dari tetangga-tetangga baru, perubahan cost link dan link-link yang tidak
26
http://digilib.mercubuana.ac.id/
lagi valid. Paket LSA ini kemudian dikirim keluar sehingga semua router-router lain menerima itu.
Gambar 2.1 4 inisialisasi paket flooding link-state [2] Pada saat router menerima LSA, ia kemudian meng-update tabel routing dengan sebagian besar informasi yang terbaru. Data hasil perhitungan digunakan untuk membuat peta internetwork dan lagoritma SPF digunakan untuk menghitung jalur terpendek ke jaringan lain. Setiap waktu paket LSA menyebabkan perubahan ke database link-state, kemudian SPF melakukan perhitungan ulang untuk jalur terbaik dan meng-update tabel routing. Titik berat yang berhubungan dengan protokol link-state : 1. Processor overhead 2. Kebutuhan memori 3. Konsumsi bandwidth Router-router yang menggunakan protokol link-state membutuhkan memori lebih dan proses data yang lebih daripada router-router yang menggunakan protokol distance vector. Router link-state membutuhkan memori yang cukup untuk menangani semua informasi dari database, pohon topologi dan tabel routing. Gambar 2.15 menunjukkan inisialisasi paket flooding link-state yang mengkonsumsi bandwidth. Pada proses inisial discovery, semua router yang menggunakan protokol routing link-state mengirimkan paket LSA ke semua router tetangganya. Peristiwa ini
27
http://digilib.mercubuana.ac.id/
menyebabkan pengurangan bandwidth yang tersedia untuk me-routing trafik yang membawa data user. Setelah inisial flooding ini, protokol routing link-state secara umum membutuhkan bandwidth minimal untuk mengirim paket-paket LSA yang menyebabkan perubahan topologi.
Gambar 2.15 Pengolahan dan persyaratan memori meningkat untuk link state routing [2]
2.4.3
Penentuan Jalur
Router menggunakan dua fungsi dasar yaitu: 1. Fungsi penentuan jalur 2. Fungsi switching Penentuan jalur terjadi pada layer network. Fungsi penentuan jalur menjadikan router untuk mengevaluasi jalur ke tujuan dan membentuk jalan untuk menangani paket. Router menggunakan tabel routing untuk menentukan jalur terbaik dan kemudian fungsi switching untuk melewatkan paket. Konsep Link State Dasar algoritma routing yang lain adalah algoritma link state. Algoritma link state juga bisa disebut sebagai algoritma Dijakarta atau algoritma shortest path first (SPF).
28
http://digilib.mercubuana.ac.id/
2.4.4
Konfigurasi Routing Untuk menghidupkan protokol routing pada suatu router, membutuhkan
seting parameter global dan routing. Tugas global meliputi pemilihan protokol routing seperti RIP, IGRP, EIGRP atau OSPF. Sedangkan tugas konfigurasi routing untuk menunjukkan jumlah jaringan IP. Routing dinamis menggunakan broadcast dan multicast untuk berkomunikasi dengan router-router lainnya. Router
pertama
yang
mempelajari
perubahan
topologi
link-state
melewatkan informasi sehingga semua router dapat menggunakannya untuk proses update. Gambar 2.14 adalah informasi routing dikirim ke semua router dalam internetwork. Untuk mencapai keadaan konvergen, setiap router mempelajari routerrouter tetangganya. Termasuk nama dari router-router tetangganya, status interface dan cost dari link ke tetangganya. Router membentuk paket LSA yang mendaftar informasi ini dari tetangga-tetangga baru, perubahan cost link dan link-link yang tidak lagi valid. Paket LSA ini kemudian dikirim keluar sehingga semua router-router lain menerima itu.
2.5
Algoritma Genetika Algoritma Genetika pertama kali ditemukan oleh John Holland pada tahun
1960-an dan kemudian dikembangkan bersama murid-murid dan rekan kerjanya di Universitas Michigan pada tahun 1970-an. Dasar Algoritma Genetika adalah teori evolusi Darwin, yang menjelaskan prinsip dasar terciptanya banyak spesies makhluk hidup yang ada di dunia sekarang ini. Makhluk hidup yang dapat beradaptasi dengan lebih baik terhadap lingkungannya akan mempunyai kesempatan yang lebih besar untuk bertahan hidup dan bereproduksi sehingga mempengaruhi jumlah populasi spesies yang bersangkutan di waktu-waktu selanjutnya. Dimana mendefinisikan algoritma genetika ini sebagai metode algoritma pencarian pada mekanisme seleksi alam dan genetika alam. Algoritma genetika adalah teknik pencarian heuristik yang didasarkan pada gagasan evolusi seleksi alam dan genetik. Algoritma Genetika ini banyak dipakai pada aplikasi bisnis, teknik maupun pada bidang keilmuan. Keberagaman pada evolusi biologis adalah variasi dari kromosom antar individu
29
http://digilib.mercubuana.ac.id/
organisme. Variasi kromosom ini akan mempengaruhi laju reproduksi dan tingkat kemampuan organisme untuk tetap hidup. pada dasarnya ada 4 kondisi yang sangat mempengaruhi proses evaluasi yaitu : 1. kemampuan organisme untuk melakukan reproduksi 2. keberadaan populasi organisme yang bisa melakukan reproduksi 3. keberagaman organisme dalam suatu populasi 4. perbedaan kemampuan untuk survive Individu yang lebih kuat (fit) akan memiliki tingkat survival dan tingkat reproduksi yang lebih tinggi jika dibandingkan dengan individu yang kurang fit. Pada kurun waktu tertentu (sering dikenal dengan istilah generasi), populasi secara keseluruhan akan lebih banyak memuat organisme yang fit. Pada algoritma ini teknik pencarian dilakukan sekaligus atas sejumlah solusi yang munngkin, dikenal dengan istilah populasi. Di dalam populasi tersebut terdapat individu yang disebut dengan istilah kromosom. Kromosom-kromosom terolusebut merupakan suatu solusi yang masih berbentuk simbol, biasanya disebut bilangan biner. Kromosom-kromosom ini akan mengalami evolusi melalui sejumlah interasi yang disebut dengan generasi. Dalam setia generasi kromosom akan mengalami proses evaluasi dengan menggunakan alat ukur yang disebut dengan fungsi fitness. Dalam algoritma genetik, istilah kromosom suatu merujuk pada kandidat solusi dari masalah, sering dilambangkan sebagai sebuah string yang terdiri dari bit. Gen adalah suatu bit tunggal atau sebuah blok yang terdiri dari bit-bit yang berdampingan melabangkan elemen tertentu dari kandidat solusi. 2.5.1
Struktur Umum Algoritma Genetika Pada algoritma teknik pencarian dilakukan sekaligus atas sejumlah solusi
yang mungkin yang dikenal dengan populasi. Individu yang terdapat dalam satu populasi disebut istilah kromosom. Kromosom ini merupakan suatu solusi yang masih berbentuk simbol. Populasi awal dibangun secara acak, sedangkan populasi berikutnya merupakan hasil evolusi kromosom - kromosom melalui iterasi yang
30
http://digilib.mercubuana.ac.id/
disebut dengan istilah generasi. Pada setiap generasi, kromosom akan melalui proses evaluasi dengan menggunakan alat ukur yang disebut dengan fungsi fitness. Nilai fitness dari suatu kromosom akan menunjukkan kualitas kromosom dalam populasi tersebut. Generasi berikut dikenal dengan istilah anak (offspring) terbentuk dari gabungan 2 kromosom generasi sekarang yang bertindak sebagai induk (parent) dengan menggunakan operator penyilangan (crossover). Selain operator penyilangan, suatu kromosom juga dapat dimodifikasi dengan menggunakan operator mutasi. Populasi generasi yang baru dibentuk dengan cara menyeleksi nilai fitness dari kromosom induk (parent) dan nilai fitness dari kromosom anak (offspring), serta menolak kromosom-kromosom yang lainnya sehingga ukuran populasi (jumlah kromosom dalam suatu populasi) konstan. Setelah melalui beberapa generasi, maka algoritma ini akan konvergen ke kromosom terbaik. Goldberg (1989) mengemukakan bahwa algoritma genetika mempunyai karakteristik karakteristik yang perlu diketahui sehingga dapat terbedakan dari prosedur pencarian atau optimasi yang lain yaitu: 1. Algoritma genetik bekerja dengan pengkodean dari himpunan solusi permasalahan berdasarkan parameter yang telah ditetapkan dan bukan parameter itu sendiri. 2. Algoritma genetik melakukan pencarian pada sebuah populasi dari sejumlah individu - individu yang merupakan solusi permasalahan bukan hanya dari sebuah individu. 3. Algoritma genetik merupakan informasi fungsi objektif (fitness), sebagai cara untuk mengevaluasi individu yang mempunyai solusi terbaik, bukan turunan dari suatu fungsi. 4. Algoritma genetik menggunakan aturan-aturan transisi peluang, bukan aturanaturan deterministik. Variabel dan parameter yang digunakan pada algoritma genetika adalah:
31
http://digilib.mercubuana.ac.id/
1. Fungsi fitness (fungsi tujuan) yang dimiliki oleh masing-masing individu untuk menentukan tingkat kesesuaian individu tersebut dengan kriteria yang ingin dicapai. 2. Populasi jumlah individu yang dilibatkan pada setiap generasi. 3. Probabilitas terjadinya pindah silang (crossover) pada suatu generasi. 4. Probabilitas terjadinya mutasi pada setiap individu. 5. Jumlah generasi yang akan dibentuk yang menentukan lama dari penerapan algoritma genetika. 2.5.2
Komponen-komponen Utama Algoritma Genetika
Terdapat 6 komponen utama dalam algoritma genetika, yaitu : 1. Teknik Pengkodean Teknik pengkodean adalah bagaimana mengkodekan gen dari kromosom dimana gen merupakan bagian dari kromosom. Satu gen biasanya akan mewakili satu variable. Agar dapat diproses melalui algoritma genetik, maka alternative tersebut harus dikodekan terlebih dahulu kedalam bentuk kromosom masing – masing kromosom berisi sejumlah gen yang mengkodekan informasi yang disimpan di dalam kromosom. Gen dapat dipresentasikan dalam bentuk: string bit, pohon, array bilangan real, daftar aturan, elemen permutasi, elemen program, atau representasi lainnya yang dapat diimplementasikan untuk operator genetika. 2. Prosedur Inisialisasi Inisialisasi adalah proses membangkitkan sejumlah individu secara acak atau melalui prosedur tertentu. Membangkitkan kromosom (sesuai dengan ukuran populasi) untuk menjadikan anggota pupulasi awal. Ukuran untuk populasi tergantung pada masalah yang akan dipecahkan dan jenis operator genetika yang akan diimplementasikan. Setelah ukuran populasi ditentukan, kemudian harus dilakukan pembangkitan populasi awal. Inisialisasi kromosom dilakukan secara acak, namun demikian harus tetap memperhatikan domain solusi dan kendala permasalahan yang ada. 32
http://digilib.mercubuana.ac.id/
3. Fungsi Evaluasi Setiap kromosom pada populasi dihitung nilai fitnessnya berdasarkan fungsi fitness. Fungsi yang digunakan untuk mengukur nilai kecocokan atau derajat optimalitas suatu kromosom disebut fungsi fitness (fitness function). Nilai fitness suatu kromosom menggambarkan kualitas kromosom dalam populasi tersebut. Proses ini akan mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom dan mengevaluasinya sampai terpenuhi kriteria berhenti. Ada 2 hal yang harus dilakukan dalam melakukan evaluasi kromosom, yaitu: evaluasi fungsi objektif (fungsi tujuan) dan konversi fungsi objektif kedalam fungsi fitness. Secara umum, fungsi fitness diturunkan dari fungsi objektif dengan nilai tidak negatif. Apabila ternyata fungsi objektif memiliki nilai negatif, maka perlu ditambahkan suatu konstanta C agar nilai fitness yang terbentuk menjadi tidak negatif. 4. Seleksi Seleksi merupakan proses pemilihan individu - individu mana saja yang akan dipilih untuk proses pindah silang (crossover) atau mutasi. Proses pemilihan tersebut biasanya dipilih berdasarkan probabilitas dari individu yang terbaik dalam populasi. Individu terbaik ditentukan berdasarkan nilai fitness masing – masing dari tiap – tiap individu. Seleksi digunakan untuk mendapatkan calon induk yang baik. “induk yang baik akan menghasilkan keturunan yang baik”. Dalam proses reproduksi setiap individu, populasi pada suatu generasi diseleksi berdasarkan nilai fitness-nya untuk berproduksi guna menghasilkan keturunan. Semakin tinggi nilai fitness suatu individu maka semakin besar kemungkinan untuk terpilih. Probabilitas terpilihnya suatu individu untuk berpoduksi adalah sebesar nilai fitness individu tersebut dibagi dengan nilai fitness seluruh individu dalam populasi. 5. Operator Genetika Ada 2 operator genetika, yaitu: a. Operator untuk melakukan rekombinasi, yang terdiri dari :
33
http://digilib.mercubuana.ac.id/
1. Operator untuk melakukan rekombinasi bernilai real - Rekombinasi diskrit - Rekombinasi intermediate - Rekombinasi garis - Rekombinasi garis yang diperluas 2. Rekombinasi bernilai biner (crossover) - Crossover satu titik - Crossover banyak titik - Crossover seragam b. Mutasi, yang terdiri dari : 1. Mutasi bernilai real 2. Mutasi bernilai biner 6. Penentuan parameter Parameter adalah parameter kontrol algoritma genetika, yaitu: ukuran populasi (popsize), peluang crossover (Pc) dan peluang mutasi (Pm). Nilai parameter ini ditentukan juga berdasarkan permasalahan yang akan dipecahkan. 2.6
Perancangan Operator - Operator Algoritma Genetika
2.6.1
Reproduksi Reproduksi merupakan sebuah string individu disalin kembali menjadi
individu baru yang akan dipersiapkan menjadi orang tua. Kegunaan dari penyeleksian orang tua dalam algoritma genetika yaitu agar mendapatkan anggota populasi yang terbaik. Prinsip kerja dari operator reproduksi yaitu membangkitkan nilai-nilai random gen dari individu sebelumnya (parent) untuk ditempatkan dalam kromosom baru (offspring) yang mewakili satu individu pada generasi selanjutnya. Berikut ini adalah ilustrasi dari cara kerja operator reproduksi :
34
http://digilib.mercubuana.ac.id/
Gambar 2.16 ilustrasi dari cara kerja operator reproduksi
2.6.2
Crossover Pada crossover (pindah silang) adalah operator dari algoritma genetik yang
melibatkan dua induk untuk membentuk kromosom baru. Crossover akan dipilih secara acak dua individu dan tempat pertukaran, dimana kromosom yang ditandai diantara kedua tempat pertukaran akan bertukar tempat satu sama lain. Proses crossover akan membangkitkan offspring baru dengan mengganti sebagian informasi dari
parents.
Tujuan
dari
proses
crossover
adalah
untuk
menambahkan
keanekaragaman individu dalam populasi dengan mengawinkan individu - individu pada populasi sehingga menghasilkan keturunan berupa individu - individu baru untuk ditempatkan pada populasi selanjutnya. Prosedur untuk memilih parent mana yang akan di crossover melalui tahap berikut ini : 1. Menetukan titik crossover secara random berdasarkan panjang kromosom parent 2. Untuk dua kromosom parent yang sudah ditentukan titik potongnya masingmasing dilakukan pertukaran gen atau penyilangan gen. Dalam algoritma genetika dikenal beberapa tipe dari crossover, antara lain : 1. One Cut Point Crossover Pada One Point Crossover hanya ada satu titik potong yang ditentukan secara acak. kromosom offspring di peroleh dengan menukar potongan kromosom sisi kanan dari parent pertama dengan parent kedua. Untuk lebih jelasnya, dapat dilihat melalui tahapan - tahapan berikut ini : a. Hitung panjang kromosom yaitu banyak gen yang ada dalam kromosom b. Buat titik crossover dengan cara membangkitkan nilai random antara 1 sampai dengan panjang individu (1-, misalnya nilai randomnya n).
35
http://digilib.mercubuana.ac.id/
c. Pertukarkan gen yang ke n sampai ke total gen dari parent 1 dengan yang ke n sampai ke total gen dari parent 2
Gambar 2.17 Contoh Single Point Crossover
2. Order Based Crossover Crossover membangkitkan offspring baru dengan menggantikan sebagian informasi dari parents. Offspring yang dihasilkan hanya satu hasil dari kombinasi kedua parent.
Gambar 2.18 Contoh Order Based Crossover
2.6.3
Mutasi Mutasi merupakan proses untuk mngubah nilai dari satu atau beberapa gen
dalam suatu kromosom. Operasi mutasi yang dilakukan pada kromosom dengan tujuan untuk memperoleh kromosoom – kromosom baru sebagai kandidat solusi pada
36
http://digilib.mercubuana.ac.id/
generasi mendatang dengan fitness yang lebih baik dan lama – kelamaan menuju solusi optimum yang diinginkan. Mutasi berfungsi untuk menggantikan gen yang hilang dari populasi selama proses seleksi serta menyediakan gen yang tidak ada dalam populasi awal. Sehingga mutasi akan meningkatkan variasi populasi. Proses ini merubah sedikit komposisi penyusun individual tersebut dan menambah suatu karakteristik tertentu secara acak. Shif mutation dilakukan dengan cara :
Menentukan dua site secara random.
Site pertama ditempatkan ke site kedua, untuk selanjutnya digeser ke kiri seperti terlihat pada gambar berikut :
Gambar 2.19 Contoh Shift Mutation
2.7
Evolutionary Programming Pada intinya, evolutionary programming memproses suatu populasi dari
individual dimana setiap individual merupakan suatu kandidat solusi (candidate solution) untuk permasalahan yang ingin dipecahkan. Pada setiap generasi, individual dievaluasi berdasarkan suatu fungsi kesesuaian (fitness function). Individual terbaik akan terpilih untuk proses reproduksi dan melanjutkan ke proses pindah silang (crossover) dan mutasi untuk memproduksi keturunan (offspring) atau candidate solution baru yang mewarisi sebagian sifat dari induknya. Proses evolutionary dilakukan secara iteratif sampai kriteria tertentu terpenuhi, misal jumlah iterasi tertentu terpenuhi atau solusi optimal telah tercapai. Dalam prosesnya, evolutionary programming melibatkan komponen-komponen antara lain: individual, fitness function, metode seleksi, operator genetik dan populasi. 2.7.1 Individual Dalam evolutionary programming, individual adalah kandidat solusi untuk permasalahan yang ingin dicari solusinya. Karakteristik suatu individual diwakili oleh
37
http://digilib.mercubuana.ac.id/
kromosom atau genome, digambarkan dengan suatu pita gen, dimana setiap gen merupakan bagian kecil dari kandidat solusi. Kromosom terdiri dari dua kelas, yaitu genotype
dan phenotype.
Individual
membentuk
populasi.
Individual
merepresentasikan kemungkinan solusi untuk masalah yang ditangani, dan biasanya juga disertakan informasi lainnya seperti parameter strategi (strategy parameter) dan kesesuaian idnividual (individual’s fitness). 2.7.2
Fitness Function Fitness function merupakan komponen yang penting dalam suatu evolutionary
programming. Tujuan Fitness function adalah untuk memetakan representasi kromosom ke suatu nilai skalar. Fitness function digunakan untuk mengevaluasi seberapa baik suatu individual dapat digunakan dalam memecahkan masalah yang dikehendaki, fitness function juga berperan untuk menentukan individual mana yang akan bereproduksi dan sebagian materi genetiknya (yaitu bagian dari kandidat solusinya) akan diwariskan kepada penerusnya/generasi berikutnya. Semakin besar kesesuaian (fitness) suatu individual, semakin tinggi peluang individual tersebut terpilih untuk operasi reproduksi, pindah silang (crossover), dan mutasi. Idealnya, suatu fitness function bisa mengukur kualitas suatu individu (candidate solution) seakurat mungkin, namun desain dari fitness function juga akan memiliki batasan tentang processing power, latar belakang pengetahuan dan persyaratan yang ditentukan user. 2.7.3 Metode Seleksi Metode seleksi yang dimaksud untuk mencakup mekanisme seleksi induk (parents)
dan
mekanisme
seleksi
survivor.
Peran
pemilihan parents dalam
evolutionary programming adalah untuk membedakan antara individual berdasarkan kualitasnya
dan
memberi
kesempatan
individual
yang
lebih
baik
untuk
menjadi parents bagi generasi berikutnya. Semakin baik tingkat kesesuaian (dalam ukuran kualitas) suatu individual, semakin tinggi peluang individual tersebut untuk terpilih.
38
http://digilib.mercubuana.ac.id/
Seperti pemilihan parents, pemilihan survivor juga berperan berperan untuk membedakan individual berdasarkan kualitasnya, perbedaannya hanya pada proses keduanya dilakukan pada tahap yang berbeda. Pemilihan survivor dilakukan setelah proses penciptaan offspring dari parents terpilih. Terdapat beberapa metode seleksi menurut Kusumadewi, yaitu seleksi ranking (rank-based fitness assignment), seleksi roulette wheel (Roulette Wheel Selection), stochastic universal sampling, seleksi lokal (local selection), seleksi dengan pemotongan (truncation selection) dan seleksi dengan turnamen (tournament selection). Skripsi ini menggunakan metode Roulette Whee. Metode seleksi stochastic sampling with replacement atau yang lebih dikenal dengan nama Roulette Wheel Selection, merupakan salah satu metode yang paling sederhana dan sering dipakai pada berbagai algoritma berbasis multi agen seperti Algoritma Genetika, Bee Colony Optimization dan lain lain. Metode ini digunakan dalam proses seleksi/pengambilan keputusan dan memastikan agar individu atau
node-node dengan fitness/fungsi
objektif yang lebih baik akan memiliki peluang lebih besar untuk dipilih. Cara kerja metode ini adalah sebagai berikut: 1. Hitung nilai fitness dari masing-1. masing individu 2. Hitung total fitness dari semua individu 3. Hitung probabilitas masing-masing individu 4. Dari probabilitas tersebut, hitung jatah masing-masing individu pada angka 1 sampai 100 5. Bangkitkan bilangan acak antara 1-100 6. Dari bilangan acak yang dihasilkan, tentukan individu mana yang terpilih dalam proses seleksi. 2.7.4
Operator Genetik Operator genetik berperan untuk menciptakan individual baru dari individual
lama (parents) atau tujuan akhirnya adalah membangkitkan candidate solutions baru. Operator genetik terbagi menjadi dua, yaitu mutasi dan rekombinasi. Rekombinasi disebut juga sebagai pindah silang atau crossover.
39
http://digilib.mercubuana.ac.id/
2.7.5
Populasi Populasi memiliki peran sebagai representasi dari segala kemungkinan solusi.
Populasi merupakan kumpulan individual atau populasi merupakan multiset dari genotypes. Genotypes adalah sejumlah karakter yang diwariskan yang tetap terkandung dalam seluruh proses reproduksi populasi. Jika ukuran populasi kecil, agar tetap mencakup sebagian besar dari search space, maka keragaman populasi (population diversity) harus diperhatikan. Jika diperlukan, dalam evolutionary programming populasi bisa memiliki struktur spasial tambahan, yaitu dengan ukuran jarak atau hubungan antar tetangga (neighbourhood relations). Untuk menjaga keragaman populasi, operator mutasi sering disarankan menjadi solusi. Evolutionary programming memiliki kemampuan optimisasi yang powerful meski dengan ukuran populasi yang relatif kecil. Dalam kasus populasi kecil, evolutionary programming dapat digunakan untuk mengeksplorasi search space yang lebih besar, yaitu dengan meningkatkan tingkat mutasi (mutation rate). 2.8
Penelitian Sebelumnya Tabel 2.2 Penelitian Sebelumnya
No. 1.
Judul Jurnal Genetic Routing GSM
Kesimpulan yang diambil routing
1. Proses
(pencarian
jalur
komunikasi) dapat mempermudah dalam mencari lokasi, dimana client dan client bisa saling berhubungan dan saling bertukar informasi melalui jalur yang telah disediakan pada telekomunikasi. 2. Masalah dalam algoritma dapat dalam fungsi tujuan, yang dikenal dengan fungsi fitness. Dimana semakin besar nilai
fitness,
maka
dihasilkan semakin baik.
40
http://digilib.mercubuana.ac.id/
sistem
yang
3. Simulasi algoritma
optimasi
routing
genetika
berfungsi
menggambarkan
proses
berbasis untuk
terjadinya
komunikasi anatar dua buah stasiun. 4. Tujuan dilakuakan algoritma genetik ini adalah untuk mempermudah menghitung waktu yang dibutuhkan dalam usaha pencarian rute terpendek antara eNode B asal ke eNode B tujuan. 5. Berdasarkan
hasil
routing
simulasi
dengan menerapkan algoritma genetik maka didapat sebagai berikut :
Pencarian
rute
pada
jalur
komunikasi semakin cepat karena adanya penginisialisasian awal.
Rute pada proses hand-over sama dengan rute terjadi koneksi awal.
Dengan
menerapkan
algoritma
genetika maka jarak tempuh dari sebuah
komunikasi
tidak
membutuhkan waktu yang cukup lama. 2.
LTE
Long
Term
Evolution
(LTE)
adalah teknologi sistem komunikasi selular di masa depan yang kini pembangunannya yang telah dilakukan besar besaran. LTE memiliki banyak keunggulan dibandingkan yang sebelumnya dari segi bandwidth yang lebar, kecepatan transmisi data yang tinggi,
41
http://digilib.mercubuana.ac.id/
delay yang lebih rendah dan fleksibel dalam hal penggunaan spektrum. 3.
Self
Adaptive
Genetic
1. Node memiliki fungsi routing dimana ia
Alogarith for LTE
berkomunikasi
dengan
meneruskan
paket melalui node intermediate. Jika dua node berada dalam jangkauan transmisi
satu
sama
lain,
mereka
berkomunikasi secara langsung. Jika tidak, node lain yang diperlukan untuk meneruskan paket mereka. MANET ditandai dengan mobilitas non-terbatas dan penyebaran yang mudah.
2. Algoritma
yang
diusulkan
berlaku
operasi crossover dan mutasi langsung pada pohon, yang menyederhanakan operasi
coding
dan
menghilangkan
proses coding/decoding. 4.
Genetic Alogaritm for Energy MME bertanggung jawab untuk semua Efficient
QoS
Multicast fungsi kontrol dari pengguna dan sesi
Routing
manajemen, yang setara dengan control plane dari SGSN dalam sistem 2G/3G. SGW terutama bertanggung jawab untuk pesawat pengguna transfer data, forwarding dan routing,
yang setara
dengan
pengguna
pesawat dari SGSN dalam sistem 2G/3G. 5.
Studi Perencanaan Jaringan
1. Hasil penelitian menunjukkan bahwa
Long Term Evolution (LTE)
jumlah eNode B
Area Jabodetabek Studi Kasus
dipengaruhi oleh frekuensi.
PT. Telkomsel
yang dibutuhkan
2. Semakin besar frekuensi yang digunakan
42
http://digilib.mercubuana.ac.id/
maka semakin banyak eNode B yang dibutuhkan. 3. Jumlah eNode B yang dibutuhkan untuk membangun jaringan LTE pada daerah Jabodetabek dengan jumlah pelanggan yang dilayani. 6.
Perencanaan Jaringan Inti 4G
Menerapkan 4G LTE menggunakan CS
LTE di Bandung
Fllback membuthkan minimum 6 MMS, 1 HSS, 2 MME, 1 SGW-PGW. Kondisi trafik data pada jaringan telkomsel di Bandung hamper berimbang dengan pelaggan non data.
43
http://digilib.mercubuana.ac.id/