© Hemanth

Mobility Prediction and Routing in

Ad Hoc Wireless Networks
William Su, Sung-Ju Lee,
and Mario Gerla - 2004

Hemanth Narra

Department of Electrical Engineering & Computer Science

ResiliNets Weekly Meeting Presentation

[email protected]

© 2010 – Hemanth
© Hemanth

Abstract

By exploiting non-random behaviors for the mobility patterns that mobile users
exhibit, we can predict the future state of network topology and perform route
reconstruction proactively in a timely manner. Moreover, by using the predicted
information on the network topology, we can eliminate transmissions of control
packets otherwise needed to reconstruct the route and thus reduce overhead. In this
paper, we propose various schemes to improve routing protocol performances by
using mobility prediction. We then evaluate the effectiveness of using mobility
prediction via simulation.

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 2

© Hemanth

Mobility Prediction & Routing

Outline
• Introduction
– Mobility Prediction Mechanisms
• Applying Mobility Prediction
– Unicast Routing Protocols
– Multicast Routing Protocols
• Analyzing the effects of prediction error
• Simulation Environment & Results
• Conclusion
• References

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 3

© Hemanth

Mobility Prediction Mechanisms

Based on GPS data

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 4

© Hemanth

Mobility Prediction Mechanisms

Based on GPS data

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 5

© Hemanth

Mobility Prediction Mechanisms

Based on Transmission Power Samples

• Transmission power samples are

– measured periodically from packets from node neighbors
– node computes rate of change of tx power level
– can compute time it takes for tx power to drop i.e. LET
• Main reason to choose power attenuation to GPS is
– Accuracy of the data

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 6

© Hemanth

Applying Mobility Prediction

Unicast Protocols – The On Demand approach

• Flow oriented Routing Protocol (FORP)

– Uses mobility prediction
– Used for real-time flow traffic in ad hoc networks
• Proposed scheme,
– maintains routes for active source/destination pairs
– routes are constructed on demand
– dst predicts topology change, determines time for re-routing

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 7

© Hemanth

Applying Mobility Prediction

Unicast Protocols – The On Demand approach

• Route Finding Approach

– verifies for unexpired route
– broadcasts FLOW-REQ message to find route to destination
• similar to Route-Request message in DSR
• seqno, src & dst address, list of intermediate nodes and LET
– Forwarding is done based on seqno
• forward req with higher seqno
• forward req with same seqno but better route (RET and hops)
– FLOW-REQ message at destination has entire route
• calculates RET (single link disconnection ≈ path disconnection)

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 8

© Hemanth

Applying Mobility Prediction

Unicast Protocols – The On Demand approach

• Source node A sends FLOW-REQ to destination F

• Nodes B,C,D and E will forward FLOW-REQ to node F
• Node F calculates RET
• It selects ABDEF as its
more stable
• F sends FLOW-SETUP,
• Intermediate nodes will
setup their flow states

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 9

© Hemanth

Applying Mobility Prediction

Unicast Protocols – The Distance Vector approach

• Most recent routing information by exchanging RT’s

• Two types of updates
– Periodic
• Entire updates/full RT is broadcasted periodically
– Trigger
• Updates generated whenever a node detects link change
• Attractive for networks with more senders
– overhead is constant even as number of senders increases
– no waiting time for route discovery
• Performance is very sensitive to periodic interval
– not suitable for highly mobile as well as low mobile scenario
16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 10
© Hemanth

Applying Mobility Prediction

Unicast Protocols – The Distance Vector approach

• Proposed protocol uses

– route expiration time as route selection metric
– packets are always sent on most stable paths
– eliminates trigger updates as routes are based on stability
– route update interval can now be relaxed
– frequent updates are also not required
– prior to route becoming invalid, better route is selected

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 11

© Hemanth

Applying Mobility Prediction

Unicast Protocols – The Distance Vector approach

• Example usage of MP in Distance Vector Protocols

• Node A sends its Rt to B and inturn receives from B

[SLG-2001]

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 12

© Hemanth

Applying Mobility Prediction

Multicast Protocols

• On Demand Multicast Routing Protocol (ODMRP)

– Comprises a request and reply phase
– JOIN DATA (Request ph) packet is broadcasted periodically
• to refresh membership information and update routes
• node receiving this packet stores upstream node id in its RT
• rebroadcasts the JOIN DATA packet again
• multicast receiver receiving this, creates JOIN TABLE packet
– JOIN TABLE (Reply ph) packet is broadcasted to neighbors
• node receiving this verifies next node id in the entries
• if found, it is in the path to source & part of forwarding group
• it sets the FG_FLAG & broadcasts its own JOIN TABLE

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 13

© Hemanth

Applying Mobility Prediction

Multicast Protocols

– multicast source receives this packet via shortest path

• This process builds paths from sources to receivers
– also builds a mesh of nodes, forwarding group
• Example - S1, S2 – sources; R1, R2, R3 – receivers

[SLG-2001]

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 14

© Hemanth

Applying Mobility Prediction

Multicast Protocols - Reliability

• Reliable transmission of JOIN TABLES is important

– it refreshes multicast routes and forwarding groups
– however in ODMRP JOIN TABLES are often
• broadcasted to more than one upstream neighbors
– verification cannot be done by MAC layer but by ODMRP
• Uses Passive Acknowledgement
– Node B transmits packet to C from A
– Node A overhears B’s tx to Node C
– used to verify delivery of JOIN TABLE's
– however source must send Active Ack
[SLG-2001]
16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 15
© Hemanth

Applying Mobility Prediction

Multicast Protocols - Reliability

• Route is invalidated if
– packet delivery cannot be verified by no of retransmissions
– alternate route must be found “on the spot”
– node broadcasts, “nexthop for these sources is unreachable”
– each neighbor receiving this
• builds and unicasts JOIN TABLE to nexthop if it has a route
• if it does not have a route, it re-broadcasts the message again

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 16

© Hemanth

Applying Mobility Prediction

Multicast Protocols – Adding Mobility Prediction

• Flooding is a major concern in ODMRP

– With mobility prediction, JOIN DATA is sent if route breaks
• Node’s location, speed & direction are also attached to this msg
• It also has a field for MIN_LET
– Node’s receiving this packet will
• populate their routing tables with information from this packet
• replace the previous node’s trajectory info with their own data
• update the MIN_LET value in the JOIN DATA packet
– Multicast members upon receiving this
• will create JOIN TABLE packet, populates it with calculated
value of RET and broadcasts it

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 17

© Hemanth

Applying Mobility Prediction

Multicast Protocols – Adding Mobility Prediction

– Forwarding nodes upon receiving JOIN TABLE packets

• will see if they are part of route
• if they receive multiple JOIN TABLE’s from different receivers
with different RET values,
– the node creates it own JOIN TABLE and updates with min RET
– Source upon receiving JOIN TABLE’s
• selects min RET among the JOIN TABLE’s received
– Source can thus send JOIN DATA before routes expire
– JOIN DATA & JOIN TABLE’s need not be sent periodically
• If mobility is high, routes expire quickly
– MIN_REFRESH_INTERVAL is used to contain this

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 18

© Hemanth

Applying Mobility Prediction

Multicast Protocols – Adding Mobility Prediction

• If mobility is low, routes don’t expire quickly

– if new node wants to join the network, it has to wait for long
– MAX_REFRESH_INTERVAL is used to contain this
• With mobility prediction, Route selection can be done
– with most stable paths (the one with largest RET)
– with min delay path (route that first received JOIN DATA)

[SLG-2001]

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 19

© Hemanth

Applying Mobility Prediction

Effects of Prediction Accuracy

• Our assumption was

– GPS position info is always accurate
– nodes has simple straight line mobility patterns
• However this assumption cannot hold true always
– in real world applications GPS might not be accurate
– inaccuracies can range from ±5m to ±100m
– nodes can accelerate, decelerate & change directions as well
• These effects are investigated in simulations

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 20

© Hemanth

Simulation Environment
Simulator Setup

• Simulator used was GloMoSim

• 50 mobile hosts placed within 1000m × 1000m area
• Radio Propagation range of 250m,
• Channel capacity 2Mb/s, simulation time is 600s
• Data packet size is 512B
• Free space propagation model
• 802.11 DCF was used as MAC protocol

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 21

© Hemanth

Simulation Results
Metrics Evaluated

• Metrics evaluated are

– Packet delivery Ratio
– Number of control bytes per data byte delivered
– No of total packets transmitted per data packet delivered

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 22

© Hemanth

Simulation Environment
Scenarios – Unicast Routing Evaluation

• Compared following with rate of 20 packets/s

– FORP (Flow Oriented Routing Protocol)
• with mobility enhancement as explained
– LAR (Location Aided Routing)
• An On-Demand protocol that uses GPS
– DV-MP (Distance Vector Protocol with Mobility Prediction)
• with mobility enhancement as explained
– WRP (Wireless Routing Protocol)
• a distance vector protocol for Ad Hoc Networks
• All schemes evaluated as function of
– speed, number of unicast UDP data sessions

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 23

© Hemanth

Simulation Environment
Scenarios – Unicast Routing Evaluation

• With varied speed, number of sessions was set to 5

– speed was varied from 0-72km/h
• With varied number of sessions,
– speed was fixed at 36km/h
– data sessions were varied from 5 to 30

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 24

© Hemanth

Simulation Results
Scenarios – Unicast Routing Evaluation

• PDR as function of speed, no of sessions

– WRP performed poorly because of
• trigger updates, ack’s
• also led to further collisions, congestion, contention & drops

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 25

© Hemanth

Simulation Results
Scenarios – Unicast Routing Evaluation

• Control overhead as function of speed, no of sessions

– control packets for DV-MP are periodically triggered - flat

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 26

© Hemanth

Simulation Environment
Scenarios – Multicast Routing Evaluation

• Compared following with rate 10 packets/s

– ODMRP-MP – with mobility prediction
– ODMRP – without mobility prediction
• Network conditions that vary are
– speed, multicast group density, number of multicast source
– with varied speed, multicast group size of 10 with 1 sender
• sender sends CBR traffic with varying speed from 0–72 km/h
– with varied multicast group density, speed fixed at 36km/h
• multicast group size varied from 3 to 20 with only 1 sender
– with varied multicast source, group size is fixed at 10
• number of senders varied from 1 - 10

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 27

© Hemanth

Simulation Results
Scenarios – Multicast Routing Evaluation

• Effect of mobility speed on performance

• PDR and control overhead as function of speed
– route reconstruction prior to breakage – no packets dropped

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 28

© Hemanth

Simulation Results
Scenarios – Multicast Routing Evaluation

• Effect of multicast group density on performance

• PDR and control overhead as function of group size
– as group density increases forwarding mesh increases

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 29

© Hemanth

Simulation Environment
Scenarios – Effect of Prediction Error

• Goal is to determine enhancement’s

– dependency on accuracy of Mobility Prediction
• Protocols used for simulation are
– DV-MP and DV
• Network conditions varied are
– GPS accuracy, frequency of direction changes
– way point distance in Random Way Point mobility model

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 30

© Hemanth

Simulation Results
Scenarios – Effect of Prediction Error

• Effect of GPS accuracy on performance

– Ratio in prediction scheme decreases as accuracy becomes
worse due to
• low mobility nodes are relatively stationary
• thus increasing deviation randomly leads to smaller hops

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 31

© Hemanth

Simulation Results
Scenarios – Effect of Prediction Error

• Effect of changing direction on performance of

– PDR and control overhead bytes tx/data packets delivered
– PDR in no prediction scheme is not at all affected

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 32

© Hemanth

Mobility Prediction & Routing

Conclusions

• Paper studied the use of mobility prediction

– to anticipate topology changes
– perform re-routing prior to route breaks
• Applied this approach to different classes of protocols
• Results indicate with Mobility Prediction
– more data packets are delivered to destination
– control packets were utilized more efficiently
– most stable routes are selected

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 33

© Hemanth

Mobility Prediction & Routing

References
• [SLG-2001] - William Su, Sung-Ju Lee, and Mario Gerla,
“Mobility prediction and routing in Ad Hoc wireless networks”,
International Journal of Network Management,
vol. 11, iss. 1, 2001, pp.3–30.

16 July 2010 Mobility Prediction and Routing in Ad Hoc Wireless Networks 34