Review Wireless Ad-Hoc Routing

Bab ini membahas deskripsi dan cara kerja Wireless Ad-Hoc Routing

Reactive Routing Protocols (On-Demand):

• AODV: Ad hoc On-Demand Distance Vector

• DSR: Dynamic Source Routing

• ACOR: Admission Control enabled On-demand Routing

• ABR: Associatively-Based Routing

Proactive Routing Protocols (Table-Driven):

• OLSR: Optimized Link State Routing

• DSDV: Destination-Sequenced Distance Vector

• AWDS: Ad Hoc Wireless Distribution Service

• CGSR: Clusterhead Gateway Switch Routing

Hybrid Protocols:

• TORA: Temporally-Ordered Routing Algorithm

• ZRP: Zone Routing Protocol

• OORP: Order One Routing Protocol

Klasifikasi

Routing protokol untuk jaringan mobile ad-hoc dibagi menjadi 2 kategori:

1. Proaktif atau table-driven routing protokol 

Table-driven routing berusaha untuk menyediakan informasi routing
yang konsisten dan up-to-date di setiap node. Setiap node diharuskan
mempunyai satu atau lebih tabel untuk menyimpan informasi rout-
ing. Setiap node merespon perubahan dalam topologi jaringan den-
gan menjalarkan update informasi tabel routing ke seluruh node di
jaringan untuk memastikan konsistensi routing. Perbedaan-perbedaan
antar protokol berbasis table-driven terletak pada: struktur tabel rout-
ing yang digunakan dan metode bagaimana perubahan topologi jaringan
disebarkan. Contoh table-driven routing: DSDV (Destination-Sequenced
Distance-Vector), CGSR (Clusterhead Gateway Switch Routing), WRP
( Wireless Routing Protocol).
 

2. Reaktif atau on-demand routing protokol 

Pada pendekatan on-demand, routing hanya dibuat ketika node sum-
ber membutuhkannya. Saat node sumber membutuhkan routing ke
node tujuan, node sumber melakukan proses route discovery dalam
jaringan. Proses ini akan selesai jika rute telah ditemukan atau se-
mua permutasi rute telah diperiksa. Setelah didapat rute maka akan
dilakukan prosedur routing maintenance hingga node sumber tidak
menginginkan lagi atau node tujuan tidak bisa diakses lagi. Contoh
on-demand routing: AODV (Ad Hoc On-Demand Distance Vector),
DSR (Dynamic Source Routing), TORA (Temporally Ordered Rout-
ing Algorithm), SSR (Signal Stability Routing), ASR (Associativity-
Based Routing).
 

DSDV

DSDV merupakan table-driven routing protokol yang menggunakan algorit-
ma Bellman-Ford. Setiap node mempunyai table routing yang berisi: semua
kemungkinan tujuan yang dapat dituju (next hops), jumlah hops ke setiap
tujuan dan sequence number. Sequence number digunakan agar tidak terjadi
routing loops. Tabel routing ditransmisikan secara periodik untuk menjaga
konsistensi. Terdapat dua cara untuk transmisi: full dump dan incremen-
tal. Full dump jarang dilakukan. Incremental dilakukan hanya jika terjadi
perubahan. Struktur paket yang ditransmisikan terdiri dari: alamat node
tujuan, jumlah hops untuk mencapai node tujuan, sequence number dan
sequence number baru yang unik bagi broadcaster.

DSR

DSR termasuk dalam on-demand routing dan menggunakan konsep source
routing. Node diharuskan untuk memelihara route cache, entri pada route
cache akan diupdate sejalan dengan perubahan topologi. DSR tidak meng-
gunakan periodic message seperti pada AODV sehingga mengurangi band-
width overhead, menghemat baterai dan menghindari update routing dalam
ukuran yang besar. DSR menggunakan MAC layer untuk mengidentikasi
adanya kegagalan link.
Protokol DSR terdiri dari 2 fase utama: route discovery dan route main-
tenance. Jika sebuah node ingin mengirim paket ke node tujuan, pertama
node akan melihat route cache miliknya. Jika rute ke tujuan ada maka
node akan menggunakan informasi di route cache. Jika tidak tidak dite-
mukan informasi maka node memulai proses route discovery dengan cara
membroadcast paket request route. Paket request route berisi: alamat tu-
juan, alamat node sumber dan unik ID. Setiap node yang menerima paket
request route akan memeriksa route cache masing-masing. Jika node tidak
mengetahui node tujuan, maka node tersebut akan menambahkan alamat
node tersebut kedalam paket dan kemudian memforwardnya.Route reply
digenerate ketika route request mencapai node tujuan atau node perantara
yang mempunyai informasi node tujuan pada route cachenya. Node tersebut
akan menyampaikan paket route reply ke node selanjutnya hingga sampai
node sumbernya.
Route maintenance dicapai dengan route error packet dan acknowledge-
ment. route error packet digenerate oelh MAC layer jika terjadi kegagalan
transmisi link. Ketika route error packet diterima, hop akan dihapus pada
informasi cache route. Ack digunakan sebagai mekanisme tambahan untuk
memverifikasi link-link dalam rute.

AODV

AODV hampir merupakan perpaduan antara DSR dan DSDV. AODV mem-
punyai karakteristik seperti DSR yaitu hanya melakukan route discovery
bila dibutuhkan (kategori on-demand routing). Akan tetapi AODV meng-
gunakan routing table tradisional (satu entri per tujuan), berbeda dengan
DSR yang multiple route dan menggunakan route cache. Seperti DSDV,
AODV menjamin tidak adanya loops akan tetapi AODV tidak menggunakan
periodic routing advertisement. Fitur utama yang membedakan AODV
adalah kemampuannya memberikan kounikasi unicast, multicast dan broad-
cast. AODV menggunakan komunikasi broadcast untuk route discovery dan
kemudian menggunakan unicast untuk route reply.

TORA

TORA adalah protokol routing yang sangat adaptif, efisien dan skalabel
berbasis konsep link reversal. TORA termasuk dalam kategori on-demand
routing protokol. Keunggulan dan keunikan utama TORA adalah TORA
menyediakan multiple rute ke node tujuan sehingga perubahan topologi
jaringan tidak berpengaruh besar kepada TORA. TORA hanya akan bereak-
si apabila semua rute ke node tujuan tidak ada. Multiple rute dapat dicapai
karena menggunakan control message yang terlokalisasi dalam kumpulan
node yaitu node hanya menjaga informasi routing disekitarnya (one hops).
Protokol TORA mempunyai 3 fungsi utama: route creation, route mainte-
nance dan route erasure.

OLSR

Optimized Link State Routing (OLSR) termasuk dalam kategori proak-
tif. OLSR menggunakan 2 jenis paket control: paket "hello" dan paket
"TC(Topology Control)". Paket hello digunakan untuk membangun node-
node tetangga dan pada saat yang sama digunakan untuk menghitung "mul-
tipoint relay". OLSR menggunakan periodic broadcast (paket hello) untuk
mengetahui node tetangga dan sekaligus memverifikasi kesimetrisan link ra-
dio. Paket hello yang dikirim berisi status radio link antara node dengan
node-node tetangganya. Status tersebut: asymmetric, symmetric atau mul-
tipoint relay.
Pada inisialisasi, ketika node A menerima paket hello dari tetangganya
(node B), node B akan mencatat node A sebagai Asymmetric. Kemudian,
jika node B mengirim kembali paket hello maka paket hello yang berisi sta-
tus node A adalah Asymmetric. Saat node A menerima paket hello dari
node B (dengan status node A adalah asymmetric), node A akan mencatat
bahwa node B sebagai symmetric. A kemudian mengirim paket hello ke B
dan B akan mengupdate status A ke sysmmetric. Multipoint relay adalah
kasus khusus node, ia adalah relay yang menghubungkan 2 node. Jika Paket
hello dibroadcast ke 1 hop, paket TC dibroadcast ke seluruh jaringan. Paket
TC berisi daftar multipoint relay.

GRP

Ide dasar dari GRP(Geographic Routing Protocol): node sumber mengirim
pesan ke lokasi geografis node tujuan dan bukan alamat node tujuan seperti
routing pada umumnya. GRP bekerja menggunakan 2 asumsi berikut:
• Setiap node dapat menentukan lokasi geografis dirinya sendiri dan
mengetahui posisi node-node tetangganya.
• Node source menyadari/mengetahui node tujuan. Dengan informasi
ini, pesan dapat di rutekan tanpa perlu mengetahui topologi jaringan
dan route discovery sebelumnya.
GRP cukup menarik karena dapat beroperasi tanpa adanya routing ta-
ble. Terlebih lagi, ketika posisi node tujuan diketahui, semua operasi akan
berjalan lokal yaitu: setiap node hanya harus memelihara node-node tetang-
ganya langsung. Terdapat 3 pendekatan routing: greedy routing (GR), face
routing (FR) dan adaptive face routing(AFR). Pada algoritma greedy rout-
ing, pesan di routing ke node yang paling dekat dengan tujuan. Lakukan
langkah tersebut hingga pesan sampai node tujuan.