shah WiOpt2005

Modeling and Analysis of opportunistic routing in low traffic scenarios: 

Modeling and Analysis of opportunistic routing in low traffic scenarios Rahul C. Shah, Jan Rabaey University of California, Berkeley Sven Wiethölter, Adam Wolisz Technical University, Berlin

Outline: 

Outline Opportunistic routing Motivation Region-based opportunistic routing Modeling opportunistic routing Motivation MAC layer Sleep discipline (duty cycling) Routing Comparison with simulations Conclusions

Outline: 

Outline Opportunistic routing Motivation Region-based opportunistic routing Modeling opportunistic routing Motivation MAC layer Sleep discipline (duty cycling) Routing Comparison with simulations Conclusions

Link Layer Measurements: 

Link Layer Measurements Zhao and Govindan: Used mica motes 50% links had 10% loss 33% links had 30% loss 50-80% energy is wasted on packet collisions and environmental effects

Link Layer Measurements: 

Link Layer Measurements Stutz and Rabaey: Used PicoRadio testbed Measured data over a 6 hour window Presence of people impacted channel

Exploiting Spatial Diversity: Opportunistic Routing: 

Exploiting Spatial Diversity: Opportunistic Routing Current node destination Nodes know: Their own location Destination location †R. C. Shah, S. Wiethölter, J. Rabaey and A. Wolisz, “When does opportunistic routing make sense?”, IEEE PerSens, Mar 2005.

Exploiting Spatial Diversity: Opportunistic Routing: 

Exploiting Spatial Diversity: Opportunistic Routing Current node destination Nodes know: Their own location Destination location Network layer specifies forwarding region MAC chooses next hop based on connectivity

Exploiting Spatial Diversity: Opportunistic Routing: 

Exploiting Spatial Diversity: Opportunistic Routing Current node destination Nodes know: Their own location Destination location Network layer specifies forwarding region MAC chooses next hop based on connectivity

Exploiting Spatial Diversity: Opportunistic Routing: 

Exploiting Spatial Diversity: Opportunistic Routing Current node destination Nodes know: Their own location Destination location Network layer specifies forwarding region MAC chooses next hop based on connectivity

Region-based opportunistic routing:Sleep Discipline (Cycled Receiver): 

Region-based opportunistic routing: Sleep Discipline (Cycled Receiver) Transmitter Initiated CyclEd Receiver† †En-yi Lin, J. Rabaey and A. Wolisz, “Power efficient rendezvous schemes for dense wireless sensor networks”, IEEE ICC, June 2004.

Region-based opportunistic routing:Sleep Discipline and Medium Access Control: 

Region-based opportunistic routing: Sleep Discipline and Medium Access Control Variant of TICER Use sensing slots for multiple forwarding nodes to back off Provides ability to choose among multiple candidate forwarding nodes Pick the first node that responds to the RTS Assume channel is stationary over the RTS-CTS-Data-ACK exchange

Other Opportunistic Protocols: 

Other Opportunistic Protocols Geographic Random Forwarding (M. Zorzi & R. Rao) Uses geographic location of nodes to find best node Divides forwarding region into priority regions MAC protocol signaling is fairly complex Extremely opportunistic routing (S. Biswas & R. Morris) Ranks forwarding nodes by number of hops Sender specifies priority of receiving nodes in the packet MAC layer anycast (R. Choudhary & N. Vaidya) Provides framework for choosing forwarding nodes at the MAC layer

Outline: 

Outline Opportunistic routing Motivation Region-based opportunistic routing Modeling opportunistic routing Motivation MAC layer Sleep discipline (duty cycling) Routing Comparison with simulations Conclusions

Motivation for modeling/analysis: 

Motivation for modeling/analysis Understand behavior of entire protocol stack Evaluate average case behavior Power consumption Delay Optimize certain parameters for improved performance Evaluate different protocol variants in a unified framework Region-based opportunistic routing Geographic Random Forwarding (GeRaF)

Modeling Opportunistic Routing: 

Modeling Opportunistic Routing

Overall Performance: 

Overall Performance Wakeup power Data power p is the probability of successful transmission of a data packet  is the packet arrival rate per node

MAC layer: 

MAC layer Nactive nodes awake within forwarding region M slots available for the active nodes to back off Since we assume there is no cross-traffic in the network, we evaluate the probability of no collision among CTS packets:

Sleep Discipline: 

Sleep Discipline p is the probability of successful RTS-CTS-Data-ACK exchange pch is the probability of a good channel Nfwd is the total number of nodes in the forwarding region Ton is the time a node remains awake in one cycle T is the cycle time Probability of k nodes being awake

Routing: 

Routing Optimal forwarding region – lens of all nodes closer to the destination Calculate: Average progress per hop  Packet arrival rate () The progress depends on the number of nodes awake in the forwarding region  find optimal value of duty cycle

Routing: 

Routing If <0.5, it is better to have only one active forwarder For region-based opportunistic routing, it is always better to have only one active forwarder For a baseline case of only 1 active forwarding node, Baseline case Power consumption normalized to case of 1 active forwarder Energy spent on data packets/Total energy

Outline: 

Outline Opportunistic routing Motivation Region-based opportunistic routing Modeling opportunistic routing Motivation MAC layer Sleep discipline (duty cycling) Routing Comparison with simulations Conclusions

Putting it all together:Region-based Opportunistic Routing: 

Putting it all together: Region-based Opportunistic Routing Node wakeup rate Node wakeup rate Power per node (mW) Per-hop delay (sec)

Optimum Wakeup Rates: 

Optimum Wakeup Rates Optimal to have ≤1 node awake in the forwarding region

Modeling GeRaF†: 

Modeling GeRaF† †M. Zorzi and R. R. Rao, “Geographic random forwarding (GeRaF) for ad hoc and sensor networks: energy and latency performance”, IEEE Transactions on Mobile Computing, Oct.-Dec. 2003. The approach can be used to model/analyze other opportunistic routing protocols as well Power per node (mW) Node wakeup rate

Results/Conclusion: 

Results/Conclusion Routing: Optimal forwarding shape – lens Use any node closer to the destination for forwarding Sleep discipline: Adjust duty cycle to have only 1 active forwarder Overall observations: Energy spent on wakeups > Energy spent on forwarding packets All opportunistic protocols proposed till now have about the same power & delay performance Framework that separates out different protocol components, making analysis easier