Vol. 14, No. 1,  87-92,  Juli  2017
Penggunaan Algoritma Genetika untuk Desain Topologi Mesh pada Jaringan Fisik Telekomunikasi

## Ridwansyah 

## Abstrak
Paper ini bertujuan untuk mendesain topologi mesh yang biasanya berada pada jaringan fisik telekomunikasi  level  atas.  Topologi  mesh  ini  menggunakan  pendekatan  desain  multi  ring, dimana  dalam  proses  desainnya  akan  ditentukan  jumlah  node  dan  ring  untuk  membentuk topologi mesh. Terdapat beberapa metode optimasi yang biasa digunakan dalam perencanaan jaringan  fisik  telekomunikasi,  salah  satu  metode  yang  dapat  digunakan  adalah  Algoritma Genetika.  Pada  jurnal  ini,  gen-gen  yang  digunakan  pada  desain  menggunakan  representasi kode biner.
Kata Kunci: Algoritma Genetika, Mesh, biner, gen, kromosom, node .

## Abstract
This paper aims to design a mesh topology which is usually located at the top level physical network telecommunications. This mesh topologies using multi-ring design approach, where in  the  design  process  will  be  determined  the  number  of  nodes  and  the  ring  to  form  a  mesh topology.  There  are  several  optimization  methods  commonly  used  in  physical  planning  of telecommunication  networks,  one  method  that  can  be  used  is  a  Genetic  Algorithm.  In  this journal, the genes used in the design using a binary code representation.
Keywords: Genetic Algoritm, mesh, biner, gen, kromosom, node.

## 1.   Pendahuluan
Perencanaan  jaringan  telekomunikasi  yang  optimal  memerlukan  pertimbangan  dari beberapa  solusi-solusi  yang  potensial.  Tujuan  dari  proses  perencanaan  itu  sendiri  adalah  untuk mendapatkan suatu desain optimal yang memenuhi kebutuhan berdasarkan batasan secara teknik dan ekonomi. Pada kondisi tertentu, sulit untuk memenuhi seluruh batasan yang ditetapkan secara optimal, sehingga terkadang dapat diperoleh lebih dari satu solusi.
Model jaringan telekomunikasi dapat digambarkan dengan node dan link yang digunakan untuk menghubungkan suatu node ke node lainnya. Penggambaran suatu jaringan telekomunikasi dinotasikan sebagai G = ( V , E ), dimana V = kumpulan node dan E = kumpulan link . Apabila i,j  V ,  berarti link yang  menghubungkan  titik i ke  titik j dituliskan  dengan  notasi  ( i,j ).  Jarak d ( i,j ) adalah merupakan jarak terpendek yang  menghubungkan kedua node i dan j , dan apabila kedua node tersebut tidak tersambung maka jaraknya  .
Pada penggambaran jaringan dengan adjacency matriks , suatu jaringan G dengan n node digambarkan  sebagai  matriks A : n x n ,  dimana  elemen a ij adalah  jumlah link yang menghubungkan node i dan node j. a ij berharga  1  apabila i dan j berhubungan,    sedangkan    0 apabila tidak. Sifat-sifat dari adjacency matriks adalah a ij = a ji (simetris dan biner), a ii = 0 apabila
 Jurusan Elektronika, Fakultas Teknik, Universitas Negeri Makassar.
Ridwansyah
jumlah  elemen  dari  baris i sama  dengan  valensi  dari node i, dan  dua  jaringan G 1 dan G 2 dapat sama meskipun label dari node berbeda.
Permasalahan  dalam  mengidentifikasi sub-network yaitu menemukan sub-network yang akan  meminimumkan cost jaringan  total  jika demand antara  pasangan node dan  sekumpulan interkoneksi link transmisi  antara  kedua node tersebut  disediakan.  Suatu sub-network adalah sebuah kumpulan entitas dari layer fisik ( node dan link ), maka masalah pemilihan jalan terbaik, seperti cost yang  minimum, dengan  menghubungkan  entitas fisik dari sebuah sub-network yang diberikan merupakan hal yang penting.
Algoritma  Genetika  menggunakan  konsep  kromosom  DNA  seperti  pada  reproduksi secara biologi, yaitu dengan cara mengkodekan problem dan solusi sebagai rangkaian dari suatu pengkodean. Deretan kode tersebut merupakan model kromosom yang akan direproduksi secara biologi.
Setiap rangkaian kode pada kromosom akan menggambarkan karakter-karakter dari suatu solusi.  Hal  tersebut  mirip  struktur  DNA  pada  setiap  individu  dan  merupakan  gambaran  gen pembawa dari individu tersebut.
Kumpulan  kromosom  merupakan  kandidat  yang  terpilih  secara  probabilistik  untuk  di reproduksi, sementara gen setiap orang tua akan diturunkan pada anaknya. Kromosom dari kode solusi yang baik, akan direproduksi dengan peluang yang lebih tinggi. Algoritma Genetika akan mengawinkan  pasangan  gen-gen  orang  tua  agar  menghasilkan  gen-gen  keturunan  dengan  cara memecah masing-masing vektor kedua orang tua pada bagian-bagian tertentu dan menyilangkan suatu  bagian  dari  vektor  orang  tua  pertama  dengan  bagian  yang  sama  dari  vektor  orang  tua lainnya dan sebaliknya.
Operator Genetika yang digunakan untuk mendapatkan populasi terpilih dengan kualitas baik  adalah Reproduksi,  Crossover dan Mutasi .  Fungsi  obyektif  menggunakan  aturan  apakah kromosom  tersebut  akan  tetap  hidup  atau  mati.  Kromosom  yang  mempunyai  harga  cukup  dari suatu fungsi objektif akan dipilih untuk proses reproduksi, sedangkan yang tidak akan tersingkir.

## 2.   Jaringan Mesh Menggunakan Algoritma Genetika
Pada  umumnya  node-node  yang  akan  dihubungkan  dengan  jaringan  telekomunikasi topologi mesh adalah node-node yang mempunyai total trafik tertinggi dari node-node yang lain dari masing-masing klaster ( cluster ). Node-node ini mempunyai fungsi khusus untuk interkoneksi jaringan dengan klaster lainnya.
Sebagaimana  yang  telah  diketahui  sebelumnya  bahwa  topologi  ring  merupakan  acuan dalam  perencanaan  jaringan  karena  faktor  kehandalannya,  sehingga  banyak  tulisan  yang membahas masalah tersebut dengan berbagai tinjauan spesifik (White et al. , 1997; Morley et al ., 1999;  Grover et  al. ,  2001).  Berdasarkan  hal  tersebut  maka  pada  perencanaan  jaringan  mesh  ini menggunakan  pendekatan  desain  multi-ring.  Struktur  kromosom  yang  digunakan  adalah representasi biner dan panjang setiap kromosom adalah sama dengan nilai ( N * S ) seperti terlihat pada Gambar 1. Parameter-parameter berikut yang harus diperhatikan adalah
(1)   Total node ( N ) adalah jumlah node hub,
(2)   Jumlah sub-jaringan ( S ) yang diinginkan,
(3)   Jumlah minimum ( N S min ) node setiap sub-jaringan ( S ) dan (4)   Setiap nilai satu dapat menjadi milik lebih dari sub jaringan.

## Ridwansyah
Gambar 1. Struktur Kromosom Jaringan Mesh.
Populasi awal kromosom dihasilkan dengan cara memilihan node dengan cara acak tetapi menjamin bahwa jumlah node N dalam setiap sub-jaringan S minimal sama dengan N S min . Pada  penentuan  fungsi  obyektif  jaringan  mesh  digunakan  pendekatan  fungsi  obyektif pada  jaringan  ring.  Oleh  karena  hasil  itu  jaringan  mesh  yang  dibentuk  terdiri  dari  beberapa jaringan  ring,  sehingga  fungsi  obyektifnya  adalah  jumlah  total  biaya  dari  ring  dengan mempertimbangkan  trafik  yang  terjadi  pada  jaringan  serta  biaya  investasi  dari  link  antara  dua node. Apabila total trafik adalah aliran trafik dari i ke j dan dari j ke i ( bidirectional ) maka
u ( i,j ) = t ( i,j ) + t ( j,i ) untuk j > i , d ( i,j ) = jarak antara node i dan j .
Fungsi obyektifnya adalah
Z(T) =    i i j T j i d j i u ) , ( ). , ( min  .

## 3.   Metode Penelitian
Desain  menggunakan  asumsi  bahwa  hubungan  antara node - node adalah fully-meshed , dengan  tujuan  agar  seluruh  kemungkinan  solusi  dapat  diselidiki.  Pada  desain  jaringan  ini dianggap  bahwa  tidak  tersedianya  sumber  daya  pada  jaringan  sehingga  digunakan  pendekatan greenfield yang umumnya digunakan untuk perencanaan jangka panjang. Perencanaan  ini  menggunakan  10 node dan  data  jarak  antar node berdasarkan  letak georafis  masing-masing  kota  tersebut  yang  merupakan  sentral-sentral  telekomunikasi  di  seluruh Indonesia.  Pemilihan  node-node  tersebut  berdasarkan  jumlah  trafik  masuk  dan  keluar  terbesar pada satu wilayah.

## 4.   Hasil dan Pembahasan
Pada  Gambar  2  diperlihatkan  sebaran  10  node  yang  digunakan  untuk  pembentukan jaringan telekomunikasi topologi mesh. Ini merupakan kondisi awal sebelum perencanaan.
1 2  3  4  5 ...
1 1 1 1
1 0 0 0 0 1 Sub jaringan #1 N = 6 Node pada sub jaringan #1: 1, 3 dan 5 Node pada sub jaringan #3: 2, 3 dan 4 6 1 2  3  4 6 0 5 0 S = 3 N s min = 1, N s max = 3 Sub jaringan #3
Gambar 2.  Sebaran 10 Node.
Setelah  mengetahui  keseluruhan  node-node,  maka  kemudian  ditentukan  matrik  hasil perkalian  matriks  trafik  dan  matriks  jarak  antar  node-node  tersebut.  Keseluruhan  node  ini  akan dibentuk jaringan mesh yang terdiri dari 3 ring. Sehingga hasil yang diperoleh menggambarkan hubungan fisik antar node tersebut.
Pada  pembentukan  jaringan  mesh  ini  menggunakan  5  kromosom  pada  setiap  populasi, dengan  jumlah  iterasi  sebanyak  200.  Berdasarkan  grafik  hasil  yang  diperoleh  pada  Gambar  3, terlihat bahwa harga optimumnya adalah 33306.69.
Gambar 3. Proses Algoritma Genetika Jaringan Mesh 10 Node.
Node-node yang membentuk jaringan mesh untuk setiap siklis ring adalah
- Siklis 1, node : 4, 3, 2, 9, 6, 5
- Siklis 2, node : 7, 3, 2, 9, 8
- Siklis 3, node : 2, 9, 10, 1
Gambar 4 berikut memperlihatkan hasil dari siklis node di atas yang membentuk topologi mesh.

## Ridwansyah
Gambar 4. Hasil proses Jaringan Mesh 10 Node.
Berdasarkan  hasil  penelitian,  terlihat  bahwa  desain  topologi  mesh  menggunakan  Algoritma Genetika berhasil dengan baik dengan membentuk jaringan mesh berdasarkan desain multi ring.

## 5.   Kesimpulan
Dari proses simulasi yang dilakukan dapat diambil beberapa kesimpulan sebagai berikut 1. Hasil  proses  pembentukan  jaringan  telekomunikasi  topologi  mesh  dengan  10 node dengan iterasi sebanyak 200 kali, diperoleh nilai optimum sebesar 33306.69.
2. Metode  Algoritma  Genetika  dapat  digunakan  untuk  mendesain  topologi  mesh  jaringan fisik  telekomunikasi.  Ini  dapat  dilihat  dari  hasil  penelitian  yang  menghasilkan  topologi mesh yang berdasarkan dari tiga topologi ring.
3. Perlunya  kehati-hatian  untuk  menentukan  representasi  biner  yang  akan  digunakan  pada Algoritma Genetika, dimana hal tersebut akan menggambarkan hasil yang akan dicapai.

## Daftar Pustaka
Chartrand,  G.  dan  Oellermann,  O.R.,  1993. Applied  and  Algorithmic  Graph  Theory .  McGraw- Hill, USA.
Gen,  M.  dan  Cheng,  R.,  1997. Genetic  Algorithms  &  Engineering  Design .  John  Wiley  &  Sons Inc., Canada.
Grover, W.D. dan Doucette, J., 2001, “Increasing the efficiency of span-restorable mesh networks on  low-connectivity  graphs”, 3rd  International  Workshop  on  Design  of  Reliable Communication Networks ( DRCN ), Hungary.
Hanselman, D. dan Littefield, B., 2001. Matlab, Bahasa Komputasi Teknik .            Penerbit Andi, Yogyakarta.
Karunanithi,  N.  dan  Carpenter,  T.,  1997,  “  Sonet  ring  sizing  with  Genetic  Algorithms”, Computers Ops Res., Vol. 24, No.6.
Morley, G.D. dan Grover, W.D., 1999, “ Current approaches in the design of ring-based optical networks”, Proceedings  of  the  IEEE  Canadian  Conference  on  Electrical  and  Computer Engineering , Canada.

## Ridwansyah
Seuranen,  E.,  2003,  “Travelling  Salesman  Problem  (TSP)  with  Genetic  Algorithms”,  Website: http://www.hut.fi/~eseurane/projects/TSP/ , diakses Januari 2008.
Stidsen, T. dan Glenstrup, A.J., 2004, “ Quantifying optimal mesh and ring design costs”, Naval Research Logistics , Vol. Preprint, 1 – 14.
Sugiharto,  J.,  2003. Optimasi  topologi  jaringan  telekomunikasi  menggunakan  Algoritma Genetika, Tesis Magister Sistem Informasi Telekomunikasi.
White, A.R.P.,  Mann  J.W., dan Smith, G.D., 1997. Genetic Algorithms and Network Ring Design .