Transcript Mobile Wireless Ad Hoc Network (MANET)

Mobile Ad Hoc Network
(MANET)
PERTEMUAN KESEMBILAN
Jaringan Wireless secara umum:

Jaringan Wireless umumnya bekerja berdasarkan salah satu topology
konfigurasi baik jaringan Ad-Hoc ataupun jaringan Infrastructure.
Topologi pada Jaringan terdiri dari
1.
Topologi Ad-Hoc
2.
Topologi Infrastruktur
Topologi Ad-Hoc

Jaringan wireless Ad hoc adalah kumpulan node (atau router)
wireless mobile yang secara dinamis keberadaannya tanpa
menggunakan jaringan infrastruktur yang ada atau administrasi
yang terpusat.

Jaringan wireless Ad Hoc dapat juga dikatakan sebagai
desentraslisasi jaringan wireless.

Jaringan ad-hoc merupakan bentuk komunikasi jaringan wireless
yang paling sederhana.
Topologi Ad-Hoc (2)

Pada jaringan Ad Hoc, router dapat dengan bebas melakukan
organiasi jaringan yang berakibat topologi akan berubah dengan
cepat dan sulit untuk diprediksi. Dengan fitur ini, jaringan Ad Hoc
mengalami beberapa tantangan antara lain,
 Multihop
 Mobility
 Kombinasi jaringan yang besar dengan berbagai peralatan
yang berbeda
 Bandwidth
 Keterbatasan konsumsi battery
Topologi Ad-Hoc (3)

jaringan Ad Hoc juga memerlukan protokol routing karena setiap
node memerlukan pertukaran data.

Berbeda dengan jaringan infrastruktur, jaringan ad-hoc tidak
membutuhkan sebuah wireless LAN untuk menghubungkan
masing-masing komputer dan topologi jaringan yang terbentuk
adalah jaringan mesh.
Topologi Ad-Hoc (4)

Berikut adalah beberapa keuntungan dari sebuah
jaringan wireless ad-hoc:
1.
2.
3.
Jaringan wireless Ad-Hoc sangat sederhana dalam mensetup nya. Tancapkan adapter wireless ke pada laptop /
computer, configure softwarenya, dan andapun sudah bisa
melakukan komunikasi antar laptop
Jaringan Ad-Hoc adalah murah karena anda tidak
memerlukan sebuah wireless access point.
Jaringan Ad-Hoc adalah cepat. Rate throughputnya antar
adapter dua kali lebih cepat daripada anda menggunakan
wireless access point dalam topology infrastcruture.
Topologi Infrastruktur

konsep jaringan infrastruktur dimana untuk membangun jaringan ini diperlukan
wireless LAN sebagai pusat.

Wireless LAN memiliki SSID (Service Set Identifier) sebagai nama jaringan
wireless tersebut, dengan adanya SSID maka wireless LAN itu dapat dikenali.
Pada saat beberapa komputer terhubung dengan SSID yang sama, maka
terbentuklah sebuah jaringan infrastruktur.

terlihat bahwa beberapa komuputer dihubungkan oleh satu wireless lan, disini
toplogi jaringan yang terbentuk adalah topologi star.
Topologi Infrastruktur (2)

Dengan jaringan topology Infrastcruture memungkinkan anda untuk:
1.
Terhubung kepada jaringan kabel LAN. Sebuah wireless access
point memungkinkan anda memperluas Jaringan LAN anda
dengan kemampuan koneksi secara wireless.
2.
Komputer pada jaringan kabel dan komputer dengan koneksi
wireless bisa saling berkomunikasi satu sama lain. Hal ini lah yang
menjadi kekuatan utama dari topology wireless infrastructure.
3.
Memperluas jangkauan wireless anda. Dengan jalan meletakkan
sebuah wireless access point diantara dua wireless adapters
memperpanjang jangkauan menjadi dua kali lipat.
Topologi Infrastruktur (4)
4. Menggunakan
kemampuan
roaming.
Jika
anda
menggunakan beberapa wireless access point seperti
halnya dalam sebuah kantor yang besar atau rumah yang
sangat luas, user bisa melakukan roaming antara dua cell
access point yang saling terikat, tanpa harus kehilangan
koneksi kepada jaringan walau melompat dari satu access
point ke access point lainnya. Modus dari wireless access
point dengan kemampuan roaming seperti ini disebut WDS
(Wireless distribution system)
5. Dengan infrastructure topology, anda bisa berbagi
sambungan internet. Mungkin perangkat yang sangat
praktis untuk berbagi sambungan internet broadband dari
sambungan ADSL adalah wireless modem-router





Mobile Ad Hoc Network (MANET) indicates a wireless network of
mobile nodes that have no fixed routers.
The nodes in this network also serve as routers that are responsible
for finding and dealing with the route to every node in the network.
Some characteristics of MANET are:
 dynamic network configuration,
 limited bandwidth
 power constraints for each operation,
 low overheads,
 and an adaptive system able to handle packet loss.
The MANET network layer has two parts, namely the network layer
and the transport layer.
In the network layer of MANET is the IP (Internet protocol) and the
ad hoc routing layer uses the AODV protocol (ad hoc on demand
distance vector)
Mobile ad hoc networks



Standard Mobile IP needs an infrastructure

Home Agent/Foreign Agent in the fixed network

DNS, routing etc. are not designed for mobility
Sometimes there is no infrastructure!

remote areas, ad-hoc meetings, disaster areas

cost can also be an argument against an infrastructure!
Main topic: routing

no default router available

every node should be able to forward
Solution: Wireless ad-hoc networks

Network without infrastructure
Use components of participants for networking

Examples
Single-hop: All partners max. one hop apart
Bluetooth piconet, PDAs in a room,
gaming devices…
 Multi-hop: Cover larger distances,
circumvent obstacles
Bluetooth scatternet, TETRA police network,
car-to-car networks…
Internet: MANET (Mobile Ad-hoc Networking) group
Manet: Mobile Ad-hoc Networking
Problem No. 1: Routing
Highly dynamic network topology
 Device mobility plus varying channel quality
 Separation and merging of networks possible
 Asymmetric connections possible
Traditional routing algorithms
Distance Vector



Periodic exchange of messages with all physical neighbors that contain information
about who can be reached at what distance
Selection of the shortest path if several paths available
Every node maintains the distance of each destination
Link State



Periodic notification of all routers about the current state of all physical links
Router get a complete picture of the network
Each node maintains a view of the network topology
Example
 ARPA packet radio network (1973), DV-Routing
 every 7.5s exchange of routing tables including link quality
 updating of tables also by reception of packets
 routing problems solved with limited flooding
Distance-Vector

Known also as Distributed Bellman-Ford or RIP (Routing Information
Protocol)

Every node maintains a routing table


all available destinations

the next node to reach to destination

the number of hops to reach the destination
Periodically send table to all neighbors to maintain topology
Distance Vector (Tables)
A
Dest. Next Metric …
A
A
0
B
B
1
C
B
3
1
B
Dest. Next Metric …
A
A
1
B
B
0
C
C
2
2
C
Dest. Next Metric …
A
B
3
B
B
2
C
C
0
Distance Vector (Update)
B broadcasts the new routing
information to his neighbors
Routing table
is updated
(A, 1)
(B, 0)
(C, 1)
1
A
Dest. Next Metric
A
A
0
B
B
1
C
B
3 2
…
(A, 1)
(B, 0)
(C, 1)
1
B
Dest. Next Metric
A
A
1
B
B
0
C
C
1
…
C
Dest. Next Metric
A
B
3 2
B
B
1
C
C
0
…
Distance Vector (New Node)
broadcasts to update
tables of C, B, A with
new entry for D
(A, 1)
(B, 0)
(C, 1)
(D, 2)
(A, 2)
(B, 1)
(C, 0)
(D, 1)
1
A
Dest. Next Metric
A
A
0
B
B
1
C
B
2
D
B
3
1
B
…
(D, 0)
Dest. Next Metric
A
A
1
B
B
0
C
C
1
D
C
2
1
C
…
Dest. Next Metric
A
B
2
B
B
1
C
C
0
D
D
1
D
…
Link-State

Like the shortest-path computation method

Each node maintains a view of the network topology with a cost
for each link

Periodically broadcast link costs to its outgoing links to all other
nodes such as flooding
Link-State
A
link costs
F
H
B
E
C
D
G
Routing in ad-hoc networks
 The big topic in many research projects
 Far more than 50 different proposals exist
 The most simplest one: Flooding!
 Flooding is a simple routing technique in computer networks where
a source or node sends packets through every outgoing link.
 Flooding, which is similar to broadcasting, occurs when source
packets (without routing data) are transmitted to all attached
network nodes.
 Because flooding uses every path in the network, the shortest path
is also used. The flooding algorithm is easy to implement.
Problems of traditional routing algorithms
Dynamic of the topology
• frequent changes of connections, connection quality, participants
Limited performance of mobile systems
 periodic updates of routing tables need energy without
contributing to the transmission of user data, sleep modes difficult
to realize
 limited bandwidth of the system is reduced even more due to the
exchange of routing information
 links can be asymmetric, i.e., they can have a direction
dependent transmission quality
Types of routing



Flat Proactive Routing

Link state Fish-Eye Routing, GSR, OLSR.

Table driven: Destination-Sequenced Distance Vector (DSDV), WRP)
On-Demand or Reactive Routing

Ad hoc On-demand Distant Vector (AODV)

Dynamic Source Routing (DSR)
Hybrid Schemes

Zone Routing ZRP, SHARP (proactive near, reactive long distance)

Safari (reactive near, proactive long distance)

Geographical Routing

Hierarchical: One or many levels of hierarchy

Routing with dynamic address

Dynamic Address RouTing (DART)
Proactive Protocols

Proactive: maintain routing information independently
of need for communication

Update messages send throughout the network
periodically or when network topology changes.

Low latency, suitable for real-time traffic

Bandwidth might get wasted due to periodic updates

They maintain O(N) state per node, N = #nodes
On-Demand or Reactive Routing

Reactive: discover route only when you need it

Saves energy and bandwidth during inactivity

Can be bursty -> congestion during high activity

Significant delay might occur as a result of route discovery

Good for light loads, collapse in large loads
Hybrid Routing

Proactive for neighborhood, Reactive for far away (Zone
Routing Protocol, Haas group)

Proactive for long distance, Reactive for neighborhood
(Safari)

Attempts to strike balance between the two
Hierarchical Routing

Nodes are organized in clusters

Cluster head “controls” cluster

Trade off


Overhead and confusion for leader election

Scalability: intra-cluster vs intercluster
One or Multiple levels of hierarchy
Geographical Routing

Nodes know their geo coordinates (GPS)

Route to move packet closer to end point

Protocols DREAM, GPSR, LAR

Propagate geo info by flooding (decrease frequency for long
distances)
Proactive: DSDV - Destination-
Sequenced Distance Vector Algorithm


By Perkins and Bhagvat
Based on Bellman Ford algorithm



Every node knows “where” everybody else is


Exchange of routing tables
Routing table: the way to the destination, cost
Thus routing table O(N)
Each node advertises its position
Sequence number to avoid loops
 Maintain fresh routes

DSDV details

Routes are broadcasted from the “receiver”



Nodes announce their presence: advertisements
Each broadcast has

Destination address: originator

No of hops

Sequence number of broadcast
The route with the most recent sequence is used
Dynamic source routing II
Route Discovery
B
RREQ FORMAT
Initiator ID
A-B-D-G
A-B-D-G
Initiator seq#
G
Target ID
A-B
A
A-B-D-G
A-B-D
D
A
Partial route
A-C-E
A
H
E
A-B-C
A-C-E
A-C-E
C
A-C
Route Request (RREQ)
A-B-C
F
Route Reply (RREP)
Route Discovery is issued with exponential back-off intervals.
Route Discovery: at source A
A need to send to G
Lookup Cache for route A to G
Start Route
Discovery
Protocol
wait
Route
Discovery
finished
no
Buffer
packet
Continue
normal
processing
Route
found
?
yes
yes
Packet
in
buffer?
Write route in
packet header
no
done
Send
packet to
next-hop
DSR: Route Discovery
DSR: Route Discovery
DSR: Route Discovery
DSR: Route Discovery
DSR: Route Discovery
DSR: Route Discovery
DSR: Route Discovery
DSR: Route Discovery
Dynamic source routing III
Route Maintenance

Route maintenance performed only while route is in use

Error detection:
 Monitors
the validity of existing routes by passively listening to
data packets transmitted at neighboring nodes
 Lower

level acknowledgements
When problem detected, send Route Error packet to
original sender to perform new route discovery
 Host
detects the error and the host it was attempting;
 Route
Error is sent back to the sender the packet – original src
Route Maintenance
B
RERR
RERR
G
D
G
A
Route Cache (A)
G: A, B, D, G G:
A, C, E, H, G
F: B, C, F
H
E
C
F
Interference-based routing
Examples for interference based routing
Reactive: Ad-Hoc On-demand
Distance Vector Routing (AODV)


By Perkins and Royer
Sender tries to find destination:





broadcasts a Route Request Packet (RREQ).
Nodes maintain route cache and use destination sequence number
for each route entry
State is installed at nodes per destination
Does nothing when connection between end points is still valid
When route fails

Local recovery

Sender repeats a Route Discovery
Route Discovery in AODV 1
2
7
5
Source 1
3
4
8
6
Propagation of Route Request (RREQ) packet
Destination
Route Discovery in AODV 2
2
7
5
Source 1
3
4
8
6
Path taken by Route Reply (RREP) packet
Destination
In case of broken links…

Node monitors the link status of next hop in active routes

Route Error packets (RERR) is used to notify other nodes if link is broken

Nodes remove corresponding route entry after hearing RERR