Adhoc wireless networks for the mobile computing

Adhoc wireless networks

1. CS 15-849E: Wireless Networks (Spring 2006)

Ad Hoc Routing
Discussion Leads:
Abhijit Deshmukh Sai Vinayak
Srinivasan Seshan
Dave Andersen

2. Papers
“Outdoor Experimental Comparison of
Four Ad Hoc Routing Algorithms”
Gray, Dubrovsky, Masone,
Kotz, Fiske, McGrath,
Newport, Liu, Yuan
“A Performance Comparison of
Multi-Hop Wireless Ad Hoc Network Routing Protocols”
Broch, Maltz, Johnson, Hu, Jetcheva
“Link-level Measurements from an 802.11b Mesh Network”
Aguayo, Bicket, Biswas, Judd, Morris

3. Outline
•Motivation
•Outdoor Experimental Comparison
•APRL
•ODMRP
•AODV
•STARA
•Performance Comparison
•DSDV
•TORA
•DSR
•AODV
•Link-level Measurements, Mesh Networks
•RoofNet
•Temporal and Spatial Variation
•Take Aways
•Q & A

4. Motivation
•Infrastructureless Networks
•Ad Hoc Routing Algorithms?
•Issues coupled with Wireless Ad Hoc?
•Dynamic Nature
•Limited Transmission Range
•Node as a router
•No Maintenance
•Tradeoff: Link state maintenance & Messaging complexity

5. Ad Hoc Network Routing Protocols

6. AdHoc Routing Algorithms (1)
•APRL
•STARA
•AODV
•ODMRP
Proactive Reactive
APRL STARA AODV ODMRP

7. APRL
•Proactive Routing
•Periodic Beaconing
•Ping Destination Via Neighbor (PDVN)
•Features
•Loopless routing
•Any path (not necessarily the shortest)

8. STARA
•Proactive Scheme
•Periodic broadcast of neighborhood probe
packets NP and NP_ACKs
•Probabilistically chooses neighbor thru which to
route packet
•First uniform, then based on end to end latency
•Sends dummy data packets (DDPS) to update
latency information of alternate routes

9. AODV
•Reactive Scheme
•Route request (RREQ) packet to explore route
to destination
•Route response (RREP) along reverse route
•Link failure detection?
•Periodic Hello messages
•Link layer detection

10. ODMRP
•Reactive routing protocol
•Route establishment Similar to AODV
•Sender broadcasts JoinQuery
•Interested parties respond with JoinReplies
•Sender piggybacks data packet along with
JoinQuery

11. Outdoor Evaluation-Experimental Setup
•All 4 algos implemented at the user level
•Apps use virtual interface, Routing algos use physical
interface
•UDP Traffic + Multicast IP
•Traffic Generator
•Packet Number + sizes  2 Gaussian Distributions
•Delay b/w packet streams  2 Exponential Distributions
•Destination Laptops  1 Uniform Distribution

12. Analysis
•Message Delivery Ratio
•Communication Efficiency
•Hop Count

13. Analysis (Contd.)
•Zero Hop Failures
•Stara-S  88%
•APRL  63%
•AODV  25%

14. Final Verdict
•AODV
•Good in limited bandwidth or energy resources
•OMDRP
•If bandwidth and energy resources are plentiful &
data packets are small and reliability is crucial
•Reactive is better than proactive
•Tradeoff in AD-HOC algorithms
•Efficiency vs. Reliability

15. DSDV (Destination-Sequenced Distance Vector)
•Distance Vector Routing Protocol
•Tag Route with Sequence Number
•Updates
•Periodically
•Infinite-metric route
•DSDV vs. DSDV-SQ
•Change == new metric
•Triggered update == New sequence number
•Overhead vs. packet delivery ratio

16. DSDV (Destination-Sequenced Distance Vector)
•Advantages
•loop-free fewest-hop path
•Disadvantages
•Periodic updates
•Maintaining routes in the presence of mobility
•Route info. may be expensive and unnecessary

17. TORA (Temporally Ordered Routing Algorithm)
•Highly adaptive, loop-free distributed algorithm
•Link-reversal
•Maintain a mesh
•Local Adaptation
•Key Design Concept
•localization of control messages to a very small set of
nodes near the occurrence of a topological change.
•Three basic steps
•Route creation
•Route maintenance
•Route erasure

18. Link Reversal
A FB
C E G
D
G
Any node, other than the destination,
that has no outgoing links reverses all its incoming links.
Node G has no outgoing links
F
E G
Represents a link that
was reversed recently
B
E
A B

19. Link Reversal
A FB
C E G
D
Now all nodes (other than destination D) have an outgoing link

20. TORA
•QUERY packet propagation
•UPDATE packet
•subsequent height increase of neighbors
•CLEAR packet
•Incase of a network partition

21. TORA
•Advantages
•Loop free paths
•Establish routes quickly, before topology changes
•Able to detect network partitions very quickly
•Disadvantages
•Temporary oscillations (count to infinity type)
•Needs synchronization

22. DSR (Dynamic Source Routing)
•Source Routing
•On-demand
•Two mechanisms
•Route Discovery
•ROUTE REQUEST (propagating , non-propagating)
•Route Maintenance

23. DSR (Dynamic Source Routing)
Route RequestRoute Reply

24. DSR (Dynamic Source Routing)
•Advantages
•Reactive: only active routes
•Route caching : reduce route discovery overhead
•Disadvantages
•Packet header size
•Collisions between route requests and route reply?

25. Evaluation
•DSR vs. AODV-LL
•Similar shape, yet AODV has greater overhead?
•Propagation of route discovery packets to all nodes
•2200 route discoveries
•DSR: 950 non-propagating + 300 propagating
•DSDV-LL : 110,000 ROUTE REQUEST

26. Evaluation
•TORA
•Congestive Collapse
•Positive feedback loop
•MAC-layer collisions

27. Evaluation
•DSDV-SQ
•Constant Overhead
•Periodic update with new sequence number

28. Link Level Measurements in Mesh Networks
•Analyze cause of packet loss
•Neighbor Abstraction
•Ability to hear control packets or No Interference
•Strong correlation between BER and S/N
•RoofNet pairs communicate
•At intermediate loss rates
•Temporal Variation
•Spatial Variation

29. Roofnet Node Map
1 kilometer

30. Typical Rooftop View

31. A Roofnet Self-Installation Kit
Computer ($340)
533 MHz PC, hard
disk, CDROM
802.11b card ($155)
Engenius Prism 2.5,
200mW
Software (“free”)
Our networking
software based on
Click
Antenna ($65)
8dBi, 20 degree
vertical
Miscellaneous ($75)
Chimney Mount,
Lightning Arrestor, etc.
50 ft. Cable ($40)
Low loss (3dB/100ft)
Takes a user about 45 minutes to install on a flat roof
Total: $685

32. RoofNet
Implies failure of Neighbor Abstraction

33. RoofNet (Spatial Distribution of Loss Rates)
Reasons for Differences ?
•Different Antenna Heights
•Multi-path fading

34. RoofNet (Effect of Signal-to-Noise Ratio)
•High S/N == high delivery probabilities
•Range of S/N values > 3 db

35. RoofNet (Effect of Power Level)
•10  40 milliwatts  doubles delivery

36. RoofNet (Effect of Multi-Path)
•Significant losses  inter-node distance
•Reflected signal delayed by a microsecond
•Approx 300 meters

37. Q & A