Overlay networks for wireless ad hoc networks

Motivation

Outline

Wireless ad hoc network

Overlay network

Unit disk graph

Unit disk graph

Sparsification is not trivial!

Goals of Sparsification

Assumptions

Distance

UDG Spanners

UDG Spanners

Spanners

UDG Spanners

Spanner Properties

Spanners

Proximity graphs

Example

Proximity graphs

Relative neighborhood graphs

Relative neighborhood graphs

Relative neighborhood graphs

Routing in RNGs

Sector-based spanners

Sector based spanners

Sector based graphs

Delaunay-based spanners

Delaunay-based spanners

Relative neighborhood graph

RNG for path loss

Delaunay-based spanners

Delaunay-based spanners

Delaunay-based spanners

Routing in planar graphs

Slide 36

Problem: Unit Disk Model

Reality

Realistic wireless model

Problem: GPS

Problem: Cost Model

Solution

Problem: Contention

Solution

Problem: Mobility

Problem: Protocol Design

Realistic wireless model

Realistic wireless model

Physical carrier sensing

Future problems

References

References

References

References

References

References