Early congestion detection and adaptive routing in MANET


  
Wireless merupakan teknologi yang memungkinkan pengguna untuk  mengakses informasi dan layanan terlepas dari posisi geografis. Dalam jaringan tersebut terdapat node-node yang saling terhubung dan berkomunikasi. Congestion dapat terjadi pada sembarang intermediate node dan dapat terjadi pada intermediate node mana saja, seringkali karena terbatasnya sumberdaya yang dimiliki pada jaringan adhoc tersebut. Metode congestion control pada jaringan biasa tidak cukup memadai untuk diterapkan pada jaringan adhoc, disebabkan karakteristik jaringan adhoc yang memiliki mobilitas node yang tinggi dan tingginya frekuensi perubahan topologi. Jaringan adhoc memiliki karakteristik khusus, yakni mobilitas node yang tinggi dan topologi jaringan yang sering berubah. Kebanyakan routing protocol merupakan congestion non-control type. Maka diperlukan pendeteksian dini terhadap congestion yang bisa meminimalkan kehilangan data.



Penelitian ini mengusulkan proses deteksi dini congestion menggunakan teknik  EDAPR (Early Congestion Detection and Adaptive Routing) mengusulkan pencarian jalur alternatif menggunakan bantuan NHN (Non-congested Two-hop Neighbors). Teknik ini mudah memilih alternatif node yang tidak terdapat congestion, kemudian menemukan jalur alternatif untuk mengontrol congestion. Teknik ini menggunakan algoritma menajemen antrian dengan optimalisasi random early detection (RED) yang mengukur secara langsung pada jaringan. Pada penelitian sebelumnya metode EDAODV (Early Congestion Detection and Control Routing) diusulkan untuk melakukan prediksi congestion dan pencarian jalur alternatif secara bi-directional. Selain itu, tedapat juga metode untuk self-cure routing yaitu EDCSCAODV yang dapat memperbaiki kemacetan dalam jaringan secara mandiri.

Untuk memonitor status congestion pada node level, salah satunya dengan mengamati average queue. Metode ini dilakukan setiap detik untuk mengamati average queue dari tiap node. Hal ini dilakukan untuk mengestimasi congestion pada node tersebut. Terdapat 3 parameter yang digunakan dalam perhitungannya, antara lain minth, maxth, dan wq . minth dan maxth adalah queue threshold sedangkan wq merupakan weight parameter. Dimana nilainya akan berubah secara dinamis berdasarkan banyaknya lalu lintas aliran data.
 Minth = 25% buffer_size
 Maxth = 3 * Minth
 Avgque = (1 - wq) * Avgque + Inst_Que * wq
 Queue_status = Inst_que – Avgque
 wq = 0.002


Dengan menggunakan average queue, maka status dari sebuah node dapat dibagi menjadi 3 zona, antara lain :
  • Zona 1 (Safe Zone) 
          Jika Queue_status < minimum threshold
  • Zona 2 (Likely to be in Congestion Zone)
          Jika Queue_status > minimum threshold dan Ins_Que < maximum threshold
  • Zona 3 (Congested Zone) 
          Jika Inst_que > maximum threshold
Pada sebuah jaringan buffer berperan penting sebagi daerah memori yang menyimpan data ketika data tersebut ditransfer antara dua perangkat atau antara sebuah perangkat dan sebuah aplikasi. Buffer digunakan dalam jaringan karena beberapa alasan, antara lain untuk mengatasi perbedaaan kecepatan antara pengirim dan penerima dari sebuah aliran data, untuk menyesuaikan antara perangkat-perangkat yang mempunyai perbedaan ukuran transfer data, untuk mendukung copy semantic pada aplikasi.

Pada penelitian ini dilakukan modifikasi AODV (Ad hoc On-Demand Distance Vector) menjadi CADV (congestion aware distance vector). Modifikasi ini bertujuan untuk penundaan antrian pendek yang ditambahkan kedalam rute tujuan. Selain itu juga dapat meningkatkan kualitas jalur yang dilalui. Akan tetapi, masalah delay yang lama dan overhead yang tinggi ketika ada jalur baru belum ditemukan penyelesaiannya. CADV bersifat not congestion adaptive dimana tidak dapat mengulangi ketika rute yang ada menjadi sangat padat. Selain itu, terdapat DLAR (Dynamic load-aware routing protocol) yang bersifat seperti CADV. Perbedaannya adalah pada node dengan beban routing yang rendah lebih disukai,  untuk dimasukkan dalam jalur routing selama fase penemuan rute.

EDAODV (early detection congestion and control routing), bersifat bidirectional path discovery yang menemukan jalur secara dua arah untuk mendeteksi kemacetan diawal dan menemukan jalur alternatif yang tidak terdapat kemacetan. Setiap node memiliki dua tabel routing, primary table (dilambangkan sebagai PRT) dan alternate path routing table (dilambangkan sebagai ART). Sebuah primary table dari sebuah node akan memprediksi status kemacetannya dan secara berkala akan menyebarkannya.

EDCSCAODV (early detection congestion and self cure routing), berifat self cure routing. Setiap node memiliki dua routing table, yaitu primary table (PRT) dan neighbors table (NRT). Pada EDCSAODV mengirimkan CSP ke semua node tetangga dan tidak mengirimkan particular warning, sedangkan pada EDAODV mengirimkan CSP ke semua node tetangga secara periodik tetapi mengirimkan hanya mengirimkan peringatan (warning) pada node pendahulu dan penggantinya.

Berikut ini contoh proses yang terjadi :
 

Metode yang digunakan pada penelitian :

  • Semua jalur node utama dihitung secara periodik berupa queue_status pada node level.

  • Ketika terjadi early congestion detection technique, maka node akan mendeteksi kemacetan yang terjadi kemudian mengirimkan pesan peringatan NHN (Non-Congested Neighbors). Pada node pendahulunya akan menyadari situasi ini dan menemuakn alternatif jalur tujuan dengan segera dengan mengimplementasi mekanisme jalur adaptif.

  • Proses ini akan mengurangi kemacetan pada jaringan dengan meminimalisasi kepadatan traffic,  menemukan jalur yang tidak ada kemacetan antara sumber dan tujuan yang akan dicapai.

  • Ketika sumber akan mengirimkan paket data ke tujuan, proses yang dilakukan sebagai berikut.

o   Pertama bangun set NHN yang menghubungkan kedua lintasan.

o   Inisialisai route discovery procedure dengan mengguankan NHN yang telah dibuat untuk menemukan jalur yang tidak ada kemacetan menuju tujuan yang akan dicapai.

o   Setelah itu paket data bisa dikirim ke tujuan.

  • Langkah yang dilakukan

1.      NHN set construction

2.      Route discovery

3.      Adaptive routing


1. NHN set construction

  • Setiap mobile host memilih NHN dari aliran jaringan dengan tingkat kemacetan yang tidak padat.
  • Secara berkala NHN menginisialisasi prosedur, masing-masing mobile host secara periodik menghitung data kemacetan dengan algoritma deteksi dini kemacetan.
  • Setiap mobile host menyiarkan status kemacetan yang mungkin dialami dengan menggunakan sebuah paket CSP (congetion status packet) pada satu hop ketetanggan di jaringan.
  • Setiap mobile host belajar mengenali kemacetan dan mencatat informasi ke dalam daftar list.
  • Setiap mobile host akan saling bertukar informasi, mobile host akan meneruskan lalu lintas broadcast untuk node tetangga yang bertujuan meminimalikan kepadatan jaringan.
  • Setiap mobile host akan memperbarui semua informasi dalam tabel routing.
2.  Route discovery
  • Pada penelitian ini metode yang digunakan dengan mengganti CFS menjadi NHN.
3.   Alternate path routing
  • Ketika node NHN tetangga menerima paket dari CSP yang padat maka akan menyadari adanya kemungkinan status kemacetan.
  • Sehingga node tetangga penerima CSP tersebut akan menentkan CSP baru untuk node tujuan dan menginformasikan ke node tetangga lainnya.

Berikut ini cara menemukan jalur alternatif untuk mengurangi kemacetan
 


        Ujicoba Dilakukan

Uji coba dilakukan dengan menggunakan Network Simulator (Ns2.34).  konfigurasi dari simulasi yang dilakukan terdapat 100 node dalam 1400 x 1400 m, jangkauan radio 250 m dengan besar bandwidth 2 Mbps. Jumlah koneksi 10 - 50, CBR sending rate 4 packets/s, maximum node speed 10 m/s, pause time 30 s.

Uji coba dengan membandingan performa EDAPR ke EDAODV dan EDCSCAODV routing protocol dalam MANET yang dibuat. Sedangkan perbandingan yang digunakan mencakup 3 aspek : 

1.   Packet Delivery Ratio (PDR)
Perbandingan antara jumlah paket yang diterima dinode tujuan  dengan paket yang dikirim oleh node sumber. 

2.   End-to-end Delay 
Waktu yang dibutuhkan untuk mengirimkan paket data dari node sumber ke node tujuan. 

3.   Routing Overhead 
Jumlah paket kontrol yang dikirim selama simulasi

Beberapa skenario yang pada uji coba yang dilakukan  :

1.   Variasi jumlah koneksi antara node asal dan node tujuan
      Dari hasil yang didapatkan bisa dilihat bahwa ketiga grafik memiliki karakteristik yang sama yakni menunjukan hasil yang sama saat memiliki jumlah flow sebanyak 10. Sedangkan jumlah kontrol paket paling banyak dicapai jika menggunakan metode EDAODV.


2.   Variasi jumlah paket data
      Dari hasil yang didapatkan bisa dilihat bahwa grafik memiliki karakteristik yang sama yakni ketiga metode menunjukkan hasil yang sama saat CBR bernilai 4. Ketika CBR bernilai 4 kemungkinan belum terjadi kemacetan pada jaringan, semua node berada pada kondisi aman.