yee. judul yang keren ya. Ini untuk mengingat kembali bahwa artificial intelligence sangat membantu manusia, apalagi yang juga terkait dengan mesin. Berikut saya copas dari makalah Proceeding, Seminar of Intelligent Technology and Its Applications (SITIA 2001) Institut Teknologi Sepuluh Nopember, Surabaya, May 1, 2001.
1
Unit Pengelola Network Regional Jawa Timur, PT. Telekomunikasi
Indonesia,
E-mail
: sinung@telkom.co.id
2
Teknik Elektro, Institut Teknologi Bandung,
E-mail
: asa@isrg.itb.ac.id, waskita@itb.ac.id
3
Manajemen Performansi Network, PT. Telekomunikasi Indonesia,
E-mail
: sugengw@telkom.co.id
Penelitian yang dilaporkan pada makalah ini difokuskan pada
pembuatan tabel rute network
telekomunikasi yang adaptif dengan menggunakan algoritma genetik. Suatu model network 12 sentral telepon yang
saling dihubungkan oleh 411 trunk
group dipilih sebagai objek penelitian. Rancangan rute adaptif dibuat
berdasar data trafik bulk setiap 5 menit yang diterima oleh Network Traffic Management Center.
Algoritma genetik menerapkan prinsip evolusi mahluk hidup.Kromosom
dalam populasi menyatakan nomor-nomor trunk
group pembentuk tabel rute pada model network. Pada populasi dilakukan operasi genetik
(seleksi, rekombinasi, mutasi, regenerasi) untuk memperoleh kromosom baru yang
mempunyai fitness lebih baik. Melalui serangkaian uji coba, dipilih parameter
yang sesuai untuk menyelesaikan masalah ini, yakni: laju rekombinasi sebesar
0.9; laju mutasi sebesar 0.1 dan besar populasi
10 dengan regenerasi sebanyak 14.
Efektivitas rute adaptif diukur melalui besarnya network loss pada simulator network. Simulasi dilakukan dengan beban trafik per
5 menit selama 7 hari yang terjadi pada model network. Penerapan rute adaptif menghasilkan network loss sebesar 0.919%, lebih baik dibandingkan
dengan network loss sebesar 5.975%
pada penerapan rute statis. Pengujian melalui penambahan beban trafik
menunjukkan bahwa kecilnya network loss dapat
dipertahankan oleh rute adaptif walaupun trafiknya meningkat hingga 117.59%.
KATA KUNCI: rute adaptif,
algoritma genetik, network telekomunikasi, trafik bulk, network loss
1. Pendahuluan
Antisipasi
terhadap dinamika beban trafik pada network telekomunikasi sudah banyak
dilakukan secara terpusat oleh Network Traffic Management (NTM),
misalnya dengan pengubahan tabel rute pada sentral telepon[1]. Pengubahan tabel
rute dari NTM dapat dilakukan secara manual, menggunakan preplan atau
menggunakan scheduler[1]. Preplan diaktifkan oleh threshold yang
dipasang terhadap parameter network yang diterima NTM. Scheduler diaktifkan
oleh waktu. Pengubahan tabel rute oleh preplan maupun oleh scheduler dirancang
berdasarkan hal-hal yang telah diperkirakan. Untuk mengatasi hal-hal yang
diluar perkiraan diperlukan rute adaptif.
2. Pembatasan Masalah dan
Asumsi
Model network yang dipergunakan
dalam penelitian ini terdiri dari 12 sentral yang saling dihubungkan secara mesh
oleh 411 trunk group. Sentral-sentral tersebut dihubungkan ke NTM dan
mengirimkan data kondisi sentralnya ke NTM setiap 5 menit. Sentral-sentral
tersebut juga dapat diperintah untuk mengubah tabel rutenya melalui NTM. Data sentral yang dikirimkan di antaranya
adalah jumlah panggilan dan besar trafik pada setiap sentral dan trunk group,
keberhasilan dan kegagalan panggil pada setiap sentral dan trunk group,
serta informasi kondisi sentral dan trunk group itu sendiri[1].
Rute adaptif yang diusulkan diterapkan
pada simulator network, dengan data trafik secara bulk. Simulator
telah dibuat dengan pemrograman berorientasi objek. Untuk menghitung besaran
trafik yang akan dibuang akibat kekurangan dimensi trunk group,
digunakan rumus Erlang-B[1][2][3]. Pelimpahan trafik diperhitungkan
mengguna-kan metode Wilkinson[1][2][3]. Penggabungan trafik yang satu tujuan
dari beberapa sentral dilakukan melalui penambahan besar trafik dan jumlah
panggilan. Trunk group pada model network hanya memuat trafik
satu arah (one way).
Gbr
1. Model network telekomunikasi
Data dummy dipergunakan pada
distribusi trafik per tujuan panggil, 411 trunk group, 48228 sirkit
penyusun trunk group, tabel rute statis. Beban trafik sebesar 110%, 125%
dan 150% dari aslinya dipergunakan untuk pengujian model.
3. Tabel Rute dan Matrik
Trafik
Tabel 1. Contoh tabel rute
|
Asal |
Tujuan panggilan |
Urutan |
Tujuan ogTgrp |
OgTgrp |
|
JKT2 |
BD
|
1 |
BD
|
hotd |
|
JKT2 |
BD
|
2 |
BD
|
2oto |
|
JKT2 |
BD
|
3 |
BD
|
foto |
|
JKT2 |
BD
|
4 |
JKT3
|
fotp |
Tabel rute yang ada pada setiap sentral,
dipergunakan sebagai pedoman penyaluran trafik. Tabel 1 adalah contoh tabel
rute pada sentral JKT2, yang menunjukkan 4 pilihan trunk group untuk
menyalurkan trafik dari JKT2 ke BD dengan urutan hotd, 2oto, foto dan fotp.
Tiga trunk group pertama adalah trunk group langsung JKT2 -BD,
sedangkan yang terakhir adalah trunk group transit melalui JKT3.
Matrik trafik menggambarkan potensi
trafik yang hendak dilewatkan dari satu sentral ke sentral lainnya[2][3].
4. Network Loss
Sebagai ukuran
efektivitas penerapan rute adaptif dipilih parameter network loss. Network
loss adalah perbandingan antara jumlah panggilan yang tidak dapat
diteruskan ke sentral tujuan, karena jalur yang ditunjuk tidak mencukupi untuk
dilewati, terhadap jumlah panggilan yang hendak diteruskan[1].
5. Algoritma Genetik
Dalam algoritma genetik, himpunan solusi
yang mungkin dikodekan dalam format yang sesuai, dan disebut sebagai populasi.
Setiap solusi yang merupakan satu set rute disebut individu[4][5]. Algoritma
genetik menggunakan operasi genetik (rekombinasi dan mutasi) dan proses evaluasi dan seleksi
terhadap populasi tersebut. Suatu fungsi fitness akan dipergunakan untuk
menentukan individu yang dapat hidup dalam proses regenerasi berikutnya, hingga
diperoleh individu yang terbaik. Individu yang terbaik ini akan diterjemahkan
kembali menjadi satu set rute sebagai solusi permasalahan.
5.1 Proses Algoritma Genetik
Gbr. 2. Proses Algoritma Genetik
5.2 Fungsi Fitness
Fitness menggambarkan kesesuaian individu
dengan masalah yang dihadapi[4][5]. Dalam hal ini fitness dirumuskan pada
persamaan (1).
Fitness=1-LossNet
(1)
Jika sebuah individu diterapkan pada network
sebagai tabel rute, maka pada setiap sentral dapat dihitung jumlah panggilan
yang dapat dilewatkan per jurusan panggil. Subfitness merupakan perbandingan
jumlah panggilan yang berhasil diteruskan dari satu sentral ke suatu tujuan
panggil.
5.3 Populasi Awal
Populasi awal dibuat dengan lebih dahulu
memilih trunk group yang langsung, baru dilengkapi dengan trunk group
yang tidak langsung untuk setiap jurusan pada setiap sentral. Tabel rute yang
sedang aktif juga menjadi salah satu individu dalam populasi awal.
5.4 Proses Rekombinasi
Berdasar subfitness, bagian-bagian
individu induk akan dikelompokkan untuk membentuk individu baru. Proses
rekombinasi diperlihatkan pada gambar 3.
Gbr 3. Proses rekombinasi
5.5 Proses Mutasi
Proses mutasi
dilakukan dengan menggunakan prosedur reciprocal
exchange mutation pada bagian dari
individu. Proses mutasi diperlihatkan pada gambar 4.
Gbr 4. Proses mutasi
5.6 Audit Rute
Agar individu
yang dihasilkan dalam proses genetik tidak menjadi tabel rute yang salah, maka
diperlukan prosedur audit rute. Prosedur audit rute ini adalah memeriksa dan
mengoreksi agar tidak terjadi pengulangan pada urutan nomor trunk group dalam
tabel rute ataupun tersisipnya bilangan yang bukan nomor trunk group.
Perhitungan fitness individu
dilakukan setelah individu tersebut diaudit.
5.7 Regenerasi
Dalam regenerasi
dipilih individu dengan fitness yang
paling baik di antara populasi generasi awal dan generasi baru. Karena jumlah
individu pada setiap generasi adalah tetap, maka individu yang memiliki fitness rendah akan dibuang.
6. Parameter Algoritma Genetik
Parameter
algoritma genetik yang penting adalah
laju mutasi, laju rekombinasi besar populasi dan banyaknya regenerasi. Dengan
cara empiris diperoleh laju mutasi 0.1, laju rekombinasi 0.9, besar populasi 10
dan regenerasi 14 sebagai parameter yang terbaik untuk pembuatan tabel rute
yang adaptif pada model network yang dipergunakan.
7. Pengujian
Data pengujian
adalah data trafik pada model network yang dikumpulkan oleh NTM setiap 5
menit selama 7 hari. Pengujian pertama dilakukan dengan membandingkan loss
network pada network yang menerapkan rute statis dengan loss
network yang menerapkan rute adaptif, dengan beban yang sama. Jumlah
panggilan telepon dari data pengujian adalah 74.281.363 call.
Total loss
call dengan tabel rute dummy yang statis selama satu minggu
adalah 4.438.475 call, atau 5.98%
terhadap potensi panggilan yang hendak dilewatkan. Penerapan rute adaptif
dengan algoritma genetik pada network dengan beban yang sama menurunkan loss
call menjadi 682.801 call, atau 0.92% terhadap potensi
panggilan yang hendak dilewatkan.
Pengujian rute
adaptif pada network beban trafik yang ditingkatkan hingga menjadi 110%,
125% dan 150% menghasilkan loss call
sebesar 1.699.539 call, 9.914.717 call, 18.399.356 call atau 2.04%, 10.68%, 16.51% terhadap potensi panggilan yang
hendak dilewatkan.
Waktu komputasi untuk mengatur tabel rute adaptif pada saat beban trafik 100% secara rata-rata adalah 138 detik, dengan maksimal 1077 detik. Pada saat beban trafik 125% waktu komputasi secara rata-rata adalah 387 detik, dengan maksimal waktu 1672 detik.
Gbr 5. Network loss pada rute adaptif
Tabel 2. Network loss akibat penambahan
beban trafik
|
LossNetwork |
Origin |
Traf100 |
Traf110 |
Traf125 |
Traf150 |
|
loss>1% |
1381 |
108 |
126 |
667 |
1208 |
|
|
68.5% |
5.4% |
6.3% |
33.1% |
59.9% |
|
loss>3% |
1126 |
106 |
126 |
664 |
1179 |
|
|
55.9% |
5.3% |
6.3% |
32.9% |
58.5% |
|
loss>5% |
830 |
106 |
126 |
662 |
1149 |
|
|
41.2% |
5.3% |
6.3% |
32.8% |
57.0% |
|
loss>10% |
61 |
60 |
116 |
603 |
923 |
|
|
3.0% |
3.0% |
5.8% |
29.9% |
45.8% |
|
AvrgLoss |
5.975% |
0.919% |
2.036% |
10.676% |
16.511% |
Tabel 3. Parameter
statistik akibat penam-bahan beban trafik
|
|
Origin |
Traf100 |
Traf110 |
Traf125 |
Traf150 |
|
Stdev |
0.033884 |
0.023746 |
0.051854 |
0.111342 |
0.117002 |
|
Mean |
0.039903 |
0.005548 |
0.012557 |
0.068565 |
0.106625 |
|
stdev12 |
|
0.000922 |
0.00138 |
0.002592 |
0.002713 |
|
Z |
|
37.28135 |
19.82229 |
-11.0574 |
-24.594 |
|
Z90 |
|
1.281551 |
1.281551 |
1.281551 |
1.281551 |
|
Z95 |
|
1.644853 |
1.644853 |
1.644853 |
1.644853 |
|
Z99 |
|
2.326342 |
2.326342 |
2.326342 |
2.326342 |
Parameter
statistik menunjukkan dengan sangat nyata bahwa rute adaptif dapat memperkecil loss
network pada penambahan beban trafik hingga 110% dibandingkan dengan rute
statis.
Perhitungan
interpolasi menghasilkan informasi bahwa loss network menggunakan
rute adaptif yang diusulkan akan tetap lebih kecil dibandingkan dengan rute
statis meskipun beban trafiknya ditambah hingga 117.59% dari beban trafik
semula.
8. Penutup
Hasil pengujian
menunjukkan bahwa rute adaptif menggunakan algoritma genetik dapat menurunkan
loss network, dan dapat mempertahankan kecilnya loss network
meskipun beban network ditambah hingga 117.59%.
Penerapan rute adaptif menggunakan
algoritma genetik pada network telekomunikasi yang sesungguhnya memerlukan
beberapa pertimbangan, di antaranya adalah: kecepatan komputasi oleh mesin agar
dapat menghasilkan tabel rute yang tepat dengan cepat; keandalan perangkat NTM
sebagai sarana pengumpul data network dan pemberi perintah pengubahan
rute pada sentral-sentral telepon.
9. Daftar Referensi
[1] Gerald
R. Ash, Dynamic routing in telecommunication network, McGraw-Hill, Inc., 1998.
[2] Aaron Kershenbaum,
Telecommunications network design algorithms, McGraw-Hill, Inc., 1993.
[3] Andre
Girard, Routing and dimensioning in circuit-switched neworks, Addison-Wesley,
1990.
[4] Mitsuo
Gen & Runwei Cheng, Genetic algorithms and engineering design, John Wiley
& Sons, Inc., 1997.
[5] Zbigniew
Michalewicz, Genetic algorithms + data structures = evolution program, 3rd,
revised & extended edition, Springer-Verlag Berlin Heidelberg, NY, 1996.
