OPTIMASI PENENTUAN ZONA PADA PROTOKOL ROUTING HOPNET DENGAN TEKNIK MIN-SEARCHING
Pembimbing : Prof. Ir. Supeno Djanali, M.Sc, Ph.D Co-Pembimbing : Ir. Muchammad Husni, M.Kom Oleh: Surateno, NRP. 5108 201 021
Algoritma Routing pada MANET
Proactive Reactive Hybrid
2
Algoritma : Proactive (1)
Setiap node secara periodik membroadcast routing tabelnya ke tetangga Keuntungannya: waktu respon pendek pada penentuan jalur dari sumber ke tujuan Kerugian: broadcast informasi agar node up to date menyebabkan pemborosan bandwidth 3
Algoritma : Reactive (2)
Diharapkan mereduksi beban kontrol paket Tiap node akan mencari jalur routing hanya jika membutuhkan (on demand) Proses on demand memiliki 2 fase:
Route discovery Route maintenance 4
Algoritma : Hybrid (3)
Mengombinasikan fitur algoritma proactive dan reactive
5
Algoritma yang terkait HOPNET
Ant Colony Optimization (ACO) Zone Routing Protocol (ZRP)
6
ACO
Merupakan algoritma hybrid berdasarkan ant routing algoritma Secara reaktif mencari jalur tujuan sesuai permintaan (on demand) Secara proaktif memelihara dan memperbaiki jalur yang ada atau mengekplorasi jalur yang lebih baik 7
Zone Routing Protocol (ZRP)
Juga merupakan algoritma hybrid Tiap node secara proaktif memelihara tabel routing internal dari link informasi node yang berada dalam variabel zona routing dengan radius γ Routing reaktif digunakan untuk menemukan jalur diluar zona-nya 8
Kerja ZRP
Paket di-broadcast dalam zona node, ini untuk menghindari banjir paket dalam jaringan Waktu responnya cepat untuk menentukan jalur dalam zona Untuk menemukan jalur diluar zona, node mengirimkan paket query pada border node dalam zona 9
HOPNET
Algoritma HOPNET menggunakan routing protocol proactive dalam mencari node terdekat / sekitar dan menggunakan algoritma reactive dalam berkomunikasi antar node tersebut. Jaringan / network dibagi menjadi zona-zona yang terdiri dari beberapa node terdekat. Ukuran suatu zona tidak berdasarkan posisi / tempat tetapi berdasar panjang radius dengan satuan hops . Oleh karena itu routing suatu zona terdiri dari node dengan spesifikasi panjang radius . Node dapat dikategorikan menjadi node bagian luar ( boundary) dan bagian dalam ( interior ). Node bagian luar merupakan node dengan jarak terjauh dari pusat node sedang node bagian dalam adalah yang kurang dari radius . 10
Zona dalam HOPNET
Pada Node A dengan nilai Radius 2 dari zona , didapatkan : Boundary Node : C,E,H,J Interior Node : I,B,G,D,F Exterior Node ( Node diluar zona ) : Node lain Dalam membangun sebuah zona, sebuah node membutuhkan informasi tentang node terdekat yang didapat dari balasan pesan hello dari tiap node.
11
Contoh Pencarian Rute
Diasumsikan node asal adalah A , dengan node tujuan U . Node U berada tidak dalam satu zona dengan node A. A akan mengirim external forward ant menuju node peripheral (C,E,H,J) menggunakan route yang terdapat pada table IntraRT. Ketika ant sampai pada C,E dan H , ant akan dihancurkan karena peripheral node tidak mempunyai tetangga untuk melanjutkan paket keluar . 12
Pada node J, dilakukan pengecekan pada tabel IntraRT apakah U berada dalam satu zona.
Pada contoh ini U tidak terdapat dalam table . Oleh karena itu , J akan mengirim ant ke node peripheral ( O,M ) .
Diperhatikan J tidak akan mengirim ant pada node peripheral yang lain (A ) karena ant datang dari A-F-J , dimana akan dihancurkan ant yang dikirim dari node tersebut .
Ini adalah mekanisme pengaturan routing ( duplikasi dan beban routing yang penuh ) . Mekanisme ini akan membantu ant berjalan langsung dari node asal . Demikian mekanisme ini mencegah ants flooding pada jaringan . 13
Dengan cara yang sama , O tidak dapat menemukan U pada zona tersebut . Karena itu node O mengirim ant ke node peripheral (Q,T) . T mengetahui bahwa U berada dalam zona, maka T mengirim ant ke U menggunaka jalur yang diketahui dari tabel IntraRT. Backward ant melewati jalur kebalikan (U,T,O,J,A) menuju node asal dari node tujuan U.
14
Jika radius diubah?
15
Permasalahan
Radius r merupakan hal krusial yang perlu diperhatikan, bagaimana mendapatkan r yang optimal.
16
Tujuan / Kontribusi
Tujuan penelitian ini adalah menghasilkan sebuah perbaikan pada penentuan radius zona pada HOPNET dengan memanfaatkan teknik min
searching
17
Teknik Min-searching
Teknik min-searching telah digunakan oleh Donggeon Noh dalam megembangkan protokol SPIZ (a service Ad/D-advertisement and
discovery protocol with independent zones, yang menekankan pada keefektifan layanan proses discovery pada MANET 18
Penentuan Radius Optimal
19
Penentuan Radius Optimal
Inisiasi pada radius / hop 1 20
Penentuan Radius Optimal
radius 1 naikkan radius / hop ke 2 21
Penentuan Radius Optimal
Trafic pada radius 2 < radius 1 naikkan radius / hop ke 3 22
Penentuan Radius Optimal
Trafic pada radius 3 < radius 2 naikkan radius / hop ke 4 23
Penentuan Radius Optimal
Trafic pada radius 4 > radius 3 turunkan radius / hop ke 3 24
Penentuan Radius Optimal
Hop 3 ditetapkan sebagai radius optimal 25
Desain Protokol ACO
ZRP
26
Desain Protokol ACO
ZRP HOPNET Radius ??
27
Desain Protokol ACO
ZRP HOPNET Radius ??
Min-searching 28
Desain Protokol ACO
ZRP
HOPNET Radius dengan Min-searching
Min-searching 29
Mulai
Max_Hop=7; Max Node=500; Input Jumlah Node; Hop=1; Min=0; T
Hop <= Max_Hop? Y
Generate distribusi Node / topologi jaringan
Output Radius zona optimal
Selesai
Hitung traffic IntraRT
Hitung traffic InterRT
Trafic=InterRT+IntraRT
Y
Hop=1?
Min=Trafic Hop=Hop+1
T Y
Trafic < Min
Min=Trafic Hop=Hop+1
T
Min=Min Hop=Hop+1
30
Pengembangan pada Glomosim
Initialization Function. Fungsi ini akan digunakan untuk mengalokasikan dan menginisialisasi model protokol yang ditambahkan. Finalization Function. Fungsi ini akan membangkitkan keluaran statistic dari simulasi yang sudah berjalan pada model ini. Simulation Event Handling Function. Fungsi ini yang akan menangani proses simulasi dan penjadwalan aksi setiap kejadian. 31
Lingkungan Ujicoba
SIMULATION-TIME 5M TERRAIN-DIMENSIONS (1500, 1500) NUMBER-OF-NODES 25 #50,100 NODE-PLACEMENT RANDOM MOBILITY RANDOM-WAYPOINT MOBILITY-WP-PAUSE 30S MOBILITY-WP-MIN-SPEED 0 MOBILITY-WP-MAX-SPEED 10 MAC-PROTOCOL 802.11 NETWORK-PROTOCOL IP NETWORK-OUTPUT-QUEUE-SIZE-PER-PRIORITY 100 ROUTING-PROTOCOL HOPNETOR ZONE-RADIUS 1 #2,3,4,5,6 32
Contoh Tampilan Hasil
33
Tampilan GUI
34
Trafik HOPNET 25 node
35
Trafik HOPNET 50 node
36
Trafik HOPNET 100 node
37
Penjelasan-1
terlihat bahwa pada nilai hop / radius yang rendah didominasi oleh nilai trafik routing antar zona, sedangkan untuk hop / radius dengan nilai yang lebih besar didominasi oleh trafik routing dalam zona.
38
Penjelasan-2
Hop=1 beban trafik yang dihitung hanya untuk beban trafik antar zona. Hop=1 tiap node tidak punya tetangga dalam zona. Yang dimiliki hanyalah node periferal / border. Tidak ada proses routing proaktif dalam zona tetapi hanya routing reaktif antar zona 39
Tabel Zona Optimal (huruf tebal) JUMLAH NODE
25
50
100
HOP
TRAFIK DALAM ZONA
TRAFIK ANTAR ZONA
TOTAL TRAFIK
1
0
1890
1890
2 3 4 5 6
257 414 480 532 530
970 450 200 50 0
1227 864 680 582 530
1
0
5690
5690
2
1711
3740
5451
3
2988
2200
5188
4
3986
940
4926
5
4881
200
5081
6
5420
0
5420
1
0
33690
33690
2
14486
18690
33176
3
21813
10090
31903
4
26537
7220
33757
5
30558
2050
32608
6
32965
0
32965
40
Grafik Zona Optimal
41
Penentuan waktu (5m 2m)
42
Kesimpulan
Penentuan hop / radius zona secara manual pada algoritma sebelumnya (HOPNET) berpotensi menghasilkan beban trafik yang tidak optimal karena pengguna tidak mengetahui apakah nilai hop/radius yang dimasukkan tersebut menghasilkan trafik yang tinggi atau tidak. Algoritma yang diusulkan (HOPENTOR) memberikan alternatif pemecahan untuk masalah tersebut dimana pengguna tidak perlu melakukan penyetelan nilai hop / radius zona. Algoritma akan menemukan sendiri hop / radius yang optimal untuk kondisi saat itu. Hal yang cukup penting diperhatikan adalah penyetelan waktu simulasi. Penyetelan waktu yang terlalu kecil(kurang dari 2 menit) diduga menyebabkan konvergensi jaringan tidak optimal. Sedangkan penyetalan waktu yang terlalu besar (lebih dari 5 menit) menjadikan proses menjadi lama dan menjadi kurang 43 adaptif terhadap perubahan lingkungan semisal perubahan jumlah node dan lainnya.
DAFTAR PUSTAKA
Abolhasan,M, Wysocki,T, dan Dutkiewicz,E. 2003, “A review of routing protocols for mobile ad hoc networks”, www.sciencedirect.com Beijar, N, 2002. “Zone Routing Protocol”, http://www.tct.hut.fi/ opetus/s38030/k02/Papers/08-Nicklas.pdf Friedman,R, Shotland,A, Simon,G.2008” Efficient route discovery in hybrid networks”, www.sciencedirect.com Haas,Z. 1997, “ A new routing protocol for the reconfigurable wireless Networks”, www.sciencedirect.com Kadono,D, Izumi,T, Ooshita,F, dan Kakugawa,H. 2009, “Toshimitsu Masuzawa An Ant Colony Optimization Routing based on Robustness for Ad Hoc Networks with GPSs”, www.sciencedirect.com Noh,D, Shin,H.2007, “SPIZ: An Effective Service Discovery Protocol for Mobile Ad Hoc Networks”, EURASIP Journal onWireless Communications and Networking, Article ID 25167. Wang,J, Osagi,E, dan Thulasiraman,P. 2008, “HOPNET: A hibrid ant colony optimization routing algorithm for mobile ad hoc network”, 44 www.sciencedirect.com
TERIMAKASIH
45
