Routing in Mobile Ad hoc Networks

Routing in Mobile Ad hoc Networks

1. Routing in Mobile Ad hoc Networks
Sayed Chhattan Shah
Department of Information Communications Engineering
Hankuk University of Foreign Studies Korea
www.mgclab.com

2. Acknowledgements
Computer Networks, Routing protocols in ad hoc networks: A survey

3. Wireless Ad Hoc Network
A decentralized type of wireless networks
Ad hoc because it does not rely on a pre existing network
infrastructure such as routers or access points

4. Mobile Ad Hoc Network
A type of wireless ad hoc network
Infrastructureless network of mobile devices
Nodes are free to move independently in any direction
oLinks to other devices are changed frequently

5. Multi hop Mobile Ad Hoc Network
Nearby users directly communicate not only to exchange their own
data but also to relay the traffic of other network nodes that cannot
directly communicate

6. Routing
Routing process of selecting paths in a network along which to
send network traffic
Routing algorithms determine the specific choice of route

7. Design elements that contribute to a routing strategy Performance Criteria
Number of hops
Cost
Delay
Throughput

Decision Time
Packet (datagram)
Session (virtual circuit)

Decision Place
Each node (distributed)
Central node (centralized)
Originating node (source)
Network Information Source
None
Local
Adjacent node
Nodes along route
All nodes

Network Information Update Timing
Continuous
Periodic
Major load change
Topology change

8. Routing in MANET
No dedicated router nodes
Local node mobility
Global node mobility
Limited resources
Dynamic network environment
Limited power
Uncertainty of path quality

9. Routing in MANET
Basic goals of routing protocols
oMaximize
throughput
network capacity
network lifetime
oMinimize
packet loss and drop
control overhead
energy consumption
delay

10. Routing in MANET

11. Reactive routing protocols
Route is created only when the source requests a route to a
destination
oRoute discovery process
oRoute maintenance

12. Reactive routing protocols
Dynamic source routing
oRoute discovery process
Route request
oBroadcasts a route request packet to its neighbors
oEvery node within a broadcast range adds their node id to the route request
packet and rebroadcasts
oEvery node maintains route cache - If a route is found in the route cache,
the node will return a route reply message to the source node rather than
forwarding the route request message further
oDSR assumes that the path obtained is the shortest since it takes into
consideration the first packet to arrive at the destination node

13. Reactive routing protocols
Dynamic source routing
oRoute discovery process
Route reply messages
•Sent to the source which contains the complete route from the source to the
destination
•The source caches this route

14. Reactive routing protocols
Dynamic source routing
oRoute maintenance
Route error and acknowledgements packets
•DSR ensures the validity of the existing routes based on the
acknowledgements received from the neighboring nodes
•Acknowledgement packets also include passive
acknowledgements as the node overhears the next hop neighbor is
forwarding the packet along the route to the destination
•A route error packet is generated when a node encounters a
transmission problem which means that a node has failed to
receive an acknowledgement

15. Reactive routing protocols
Temporally ordered routing algorithm
oFinds multiple routes from a source to a destination in a highly dynamic
mobile networking environment
oReduces communication overhead
React only when necessary – not to every topological change
oThe protocol has three basic functions
Creation of a route from a source to a destination
Maintenance of the route
Deletion of the route when the route is no longer valid.

oTORA builds and maintains a Directed Acyclic Graph (DAG) rooted at a destination

16. Reactive routing protocols
Directed Acyclic Graph
oA directed graph with no cycles
oA DAG is rooted at the destination if the destination is the only node
with no downstream nodes - no links lead out of the destination. Such a
DAG is often called a destination oriented DAG
oCreation of such a DAG from a source to a destination would contain
multiple routes to the destination

17. Reactive routing protocols
Temporally ordered routing algorithm
oThe idea is to first build a DAG from the source to the destination
oThen as links fail, it might be necessary to re-compute a DAG in
order to find a route
oIf network gets partitioned, deletion of routes is required.
oTORA uses three kinds of messages
The QRY message for creating a route
The UPD message for both creating and maintaining routes
The CLR message for erasing a route

18. Reactive routing protocols
TORA protocol
oMultiple paths created
oGood in dense networks
oNot scalable by any means
oDoes not use a shortest path solution

19. Reactive routing protocols
Associativity-based routing
oRoute stability as the most important factor in selecting a route
oTo determine stability, each node maintains a tick value for each neighbors, which is
increased by one every time a HELLO message is received from the neighbor

Preemptive routing in ad hoc networks
oAttempts to initiate the discovery process of an alternate route just before the probable
route failure
oGenerates a preemptive warning when the signal power of the packet received drops
below a predefined preemptive threshold
oCorrect setting of the preemptive threshold is the main challenge

20. Reactive routing protocols
Ad hoc QoS on-demand routing protocol
oObjective is to provide QoS support in terms of bandwidth and end-to-end delay
oSupports following features
Accurate measurement of bandwidth availability in the shared wireless channel
and accurate measurement of end-to-end delay
Distributed routing algorithm that adapts with the dynamic environment
Resource reservation that guarantees the available resources
Efficient resource release upon route adjustment
Instant QoS violation detection
Fast and efficient route recovery

21. Reactive routing protocols
Ad hoc QoS on-demand routing
oBandwidth control
Because of the shared medium, a node can successfully use the channel only
when all its neighbors do not transmit and receive packets at the same time
Neighborhood traffic and topology information
•B, the raw data rate of the node
•Total amount of traffic in node’s wireless channel
•The amount of bandwidth that should be reserved
oAssumes all the nodes have identical data rate and transmission range

22. Reactive routing protocols
Ad hoc QoS on-demand routing
oBandwidth estimation
In order to estimate available bandwidth, existing total channel traffic load is
calculated

23. Reactive routing protocols
The flow oriented routing protocol
oFORP aims to transmit real-time data streams
oUses mobility information of nodes to determine future route changes
Each node appends its own ID and the Link Expiration Time LET of the last
link in which the message was received before forwarding to the next hop
Destination contains the list of all the routes travelled and the LETs for each
hop which is used to calculate route expiration time
Intermediate nodes continue adding the LETs to the forwarded packets to
enable the destination to keep track of the RET prediction
The nodes are assumed to have a common time reference from GPS

24. Reactive routing protocols
QoS routing with traffic distribution
oQoS is a collection of characteristics or constraints that a connection must guarantee
to meet the requirements of an application
oAssumes heterogonous network environment
oMakes use of a mobile routing backbone to dynamically distribute traffic within the network
and to select the route that can support best a QoS connection between a source and its
destination
oNodes are classified as either QoS routing nodes (QRN), simple routing nodes (SRN) or
transceiver nodes (TN)
A mobile routing backbone is created using all nodes having routing capabilities
QoS support is realized by relaying packets having special requirements to nodes rich
in resources and connected through stable links

25. Reactive routing protocols
QoS routing with traffic distribution
oFour QoS support metrics are used to differentiate nodes in the network and
identify the ones that can take part in the MRB
A node’s Static resources capacity SRC computed by the weighted sum of the
size of the node packet queues, speed of the CPU, power of the battery and the
maximum available bandwidth.
Dynamic resources availability DRA indicates the current load in the resource
usage of a node. The usage rate of the static resources are used to calculate the
available dynamic resources.
Neighborhood quality NQ the number of nodes in the neighborhood of a node
which can successfully forward packets.
Link quality and stability LQS the power of signal received and the statistical
stability of its links.

26. Reactive routing protocols
Source routing with local recovery
oRoute discovery in on-demand routing is typically performed via network-
wide flooding, which consumes a substantial amount of bandwidth
oTo address the problem three types of approaches have been proposed
Limited broadcast: route discovery is initiated by relay nodes. The
broadcast range is limited and does not flood the whole network
Multipath routing: Multiple routes are discovered and cached in a single
route discovery
Local error recovery: Route errors are handled at a relay node instead
of relying on end-to-end error recovery at the sender

27. Reactive routing protocols
Source routing with local recovery
Utilizes both route caches and local error recovery
To recover from a route failure, a node first salvages a route by searching its
route cache for an alternate route to the destination
If the node is not able to repair the route from its route cache, it initiates bypass
recovery by querying its neighbors to see if they have a link to any nodes on the
downstream route to the destination

28. Table-driven routing protocols
Maintain up-to-date information of routes from each node to every
other node in the network
Routing information is stored in the routing table of each node and
route updates are propagated throughout the network to keep the
routing information as recent as possible

29. Table-driven routing protocols
Destination-Sequenced Distance-Vector
oEvery mobile node maintains a routing table which contains the possible
destinations in the network together with their distance in hop counts
oRouting updates are periodically forwarded throughout the network
A full dump sends the entire routing table to the neighbors
Incremental updates are smaller and are used to transmit those entries
from the routing table which have changed since the last full dump
update
oWhen a network is stable, incremental updates are forwarded and full dump
are usually infrequent

30. Table-driven routing protocols
Optimized link state routing
oEach node selects a subset of nodes in its neighborhood, which
retransmits its messages
oThese selected nodes are named Multi Point Relays - MPRs
oThe selection condition is the following:
Each two hop neighbor node must have at least one bidirectional link toward a node
inside the MPR set
So the MPR nodes must permit to reach all the two hop neighbors
oA node retransmits a received message only if it is part of the MPRs

31. Table-driven routing protocols
Optimized link state routing

32. Hybrid routing protocols
Zone routing protocol
oProactive mechanism of node discovery within a node’s
immediate neighborhood while inter-zone communication is
carried out by using reactive approaches
oEach node individually creates its own neighborhood which it
calls a routing zone
The zone is defined as a collection of nodes whose minimum distance in
hops from the node in question is no greater than a value that is called the
“zone radius”
Note that routing zones of nodes might overlap heavily

33. Hybrid routing protocols
Zone routing protocol

34. Hybrid routing protocols
Zone routing protocol
oLocal
oRemote
Route request sent to border nodes
•Border nodes reply if they know a route
Otherwise border node bordercasts to it's border nodes

35. Hybrid routing protocols
Zone routing protocol

36. Hybrid routing protocols
Zone routing protocol

37. Hybrid routing protocols
Zone routing protocol

38. Location-aware routing protocols
Location-aware routing schemes in mobile ad hoc networks assume
that the individual nodes are aware of the locations of all the nodes
within the network

39. Location-aware routing protocols
Location-aided routing
oUtilizes location information to minimize the search space for
route discovery towards the destination node
oRelies on GPS
Based on location of the destination node and its mobility characteristics
such as the direction and speed, source sends route requests to nodes only
in the expected zone of the destination node
If the source node has no information about the speed and the direction of
the destination node, the entire network is considered as the expected zone

40. 40
Basic Idea
Route discovery using flooding algorithm:
C
D
B
S
E
A
X

41. 41
Basic Idea
Location information
oMinimize the search zone
oReduce the number of routing messages

Speed and direction information
oMore minimization of the search zone
oIncreases the probability to find a node

42. 42
Each node knows its current location

Uses last known location information and average speed to create
oan expected zone for destination
region where source node S thinks that the destination node D may
contained at some time t – only an estimate made by S
oa request zone for flooding of routing message

Basic Idea

43. 43
Expected zone
oS knows the location of D at time t
0
oCurrent time is t
1
oThe location of D at t
1 is the expected zone
Basic Idea

44. 44
Request zone
oFor route request
oNode forwards a route request only if it belongs to the request
zone
oIf a route is not discovered within the timeout period, S initiates a
new route discovery with expanded request zone
Basic Idea

45. 45
Request Zone

46. 46
LAR Scheme 1
The request zone is rectangular in shape
Assume S knows that the node D was at location (X
d, Y
d) at time t
0
Assume S knows the average speed v with which D can move
From above two, S defines the expected zone at time t
1 with radius
R = v(t
1- t
0) centered at location (X
d, Y
d)
The request zone is the smallest rectangle that includes current
location S and the expected zone such that the sides of the rectangle
are parallel to the X and Y axes

47. Example 1
Network Space
Expected
zone
A (X
s, Y
d+R)
(X
d, Y
d)
Request
zone
B (X
d+R, Y
d+R)
S (X
s, Y
s)
D (X
d+R, Y
s)
R
Source node outside the expected zone
I (X
i, Y
i) J (X
j, Y
j)
D

48. Example 2
Network Space
Expected
zone
A (X
d-R, Y
d+R)
(X
d, Y
d)
S (X
s, Y
s)
Request zone
B (X
d+R, Y
d+R)
C (X
d-R, Y
d-R)
D (X
d+R, Y
d-R)
R
Source node within the expected zone
D

49. Multipath protocols
Multipath routing protocols create multiple routes from source to
destination
Ad hoc on-demand multipath distance vector routing AOMDV
oeach route request and route reply packet arriving at a node is
potentially using a different route from the source to the
destination.

50. Hierarchical protocols
Hierarchical ad hoc routing protocols build a hierarchy of nodes,
typically through clustering techniques
Nodes at the higher levels of the hierarchy provide special services,
improving the scalability and the efficiency of routing
oCreation of cluster
oElection of cluster head

51. Geographical multicast protocols
Geographical multicast routing is a variant of multicast where the
goal is to route the packets coming from a source to destinations
located within a specific geographical region

52. Power Aware Protocols
Create a efficient route between source node and destination node
oActive
Transmission power control
Load distribution
oInactive period
Sleep mode or simply turns it off when there is no data to
transmit or receive

53. Energy aware routing protocol
Aims to design an efficient energy aware routing scheme for MANETS
Uses variable range transmission
Friis equation: ??????
??????=
????????????
????????????????????????
4????????????
??????
2




53
Receiving RREP
Store the location
N_hop x and N_hop Y (node 4)
1
2
3
4
D

54. PLR routing protocol
Aims to minimize transmission power
Assumes that a source node has neighbor node and destination’s
location


54

55. Power-aware source routing protocol for mobile ad hoc networks
Based on DSR routing protocol

Solves the problem of finding a route ?????? ??????� ����� ��������?????? ���� � ���� ��??????� ��� ��������� cost
function is minimized


55

56. Route discovery
oAll nodes except the destination calculate their link cost
Add it to the path cost in the header of the RREQ packet














a
b
c
f
e
Min-cost=a-b-e
Timer
Min-cost=a-b-e-d d
Power-aware source routing protocol for mobile ad hoc networks

57. Online Power-aware routing
57