Ant-Colony Based Routing Algorithm (ARA) for MANETs

Rionando Jepri (21060112130107)

Pendahuluan

• Masalah utama dalam jaringan mobile ADHOC adalah cara mencari route antara dua end point telekomunikasi. Ada banyak algoritma routing pada jaringan Mobile ADHOC.

• Pada presentasi dibawah ini kita akan membahas tentang Ant-Colony Based Routing Algorithm (ARA) for MANETs. Protokol Routing ARA ini bedasarkan tingkah laku koloni semut (Swarm Intelegence). Metode ini digunakan karena kemampuan semut yang dapat menyelesaikan suatu *masalah yang rumit bedasarkan kerja sama.

Tingkah laku semut dalam mencari makanan

MENGAPA Ant-Colony Based Routing Algorithm (ARA) Untuk ADHOC?

• Dynamic topolgy . Algoritma ini bekerja bedasarkan sistem agent dan bekerja dengan semut secara induvidual. Menyebabkan adaptasi yang baik pada topologi jaringan yang ada.

• Link quality. Memungkinkan menentukan kualitas link dengan komputasi dari konsentrasi pheromon, terutama proses evaporation . Hal ini akan meningkatkan pemilihan jalur bedasarkan kualitas dari link.

• Support for multi-path setiap node mempunyai routing table ke semua node tetangga yang juga mencantumkan nilai dari konsentrasi pheromon dari node yang tersedia. Pemilihan node berikutnya bedasarkan konsentrasi pheromon , yang mana menyediakan kemungkinan untuk setiap link . Maka dari itu Algoritma ini mendukug multipath routing.

Ant-Colony Based Routing Algorithm (ARA)

• The Ant colony Routing Algorithm sangat mirip dengan algoritma koloni semut mencari jalan terpendek untuk sampai pada makanan.

• Sama seperti algoritma lainnya ARA terdiri dari 3 fase yaitu:

1. Route Discovery Phase2. Route Maintenance3. Route Failure Handling

Route Discovery Phase

• Pada fase ini route baru akan dibuat dengan batuan forward ant (FANT) dan backward and (BANT). FANT adalah agent yang membentuk jalur pheromon ke node sumber, sedangkan BANT membentuk jalur pheromon menuju node tujuan. FANT dan BANT adalah packet kecil dengan urutan nomor urutan yang unik. Sehingga node bisa membedakan packet bedasarkan nomor urutan dan alamat sumber dari FANT dan BANT

Route Discovery Phase

node tujuan Next Hop Pheromone

Node S Node S

Sumber node :S

Route Discovery Phase

Route Maintenance

• Pada fase route maintenance ini , bertanggung jawab perkembangan dari route selama komunikasi. ARA tidak membutuhkan packet special untuk mantenance route. Karena sekali FANT dan BANT membangun jalur pheromon antara node sumber dan tujuan, berikutnya packet data akan digunakan untuk mempertahankan jalurnya. Sama seperti dialam, jalur yang telah terbangun tidak akan membiarkan nilai pheromon awal tetap untuk selamanya. Nilai dari pheromon akan bertambah bila jalur tersebut selalu dilewati packet, sementara nilainya akan berkurang seiring persamaan berikut

Route Maintenance

Route Maintenance

• Untuk mencegah loop yang tidak diinginkan setiap packet yang melewati node yang sama 2 kali, dapat dideteksi bedasarkan alamat sumber dan nomor urutan di packet tersebut. Lalu node ini akan memberikan flag DUPLICATE_error dan mengirimkan packet ke node sebelumnya. lalu Node sebelumnya akan mematikan link yang menuju node ini. Sehingga data tidak akan melewati jalur tersebut.

Route Failure Handling

Simulasi dari ant routing algoritma

Simulasi play