Overlay networks for wireless ad hoc networks

Thursday, June 30, 2005 - 1:30pm - 2:30pm
EE/CS 3-180
Christian Scheideler (Johns Hopkins University)
In this talk I will give an overview of various techniques to organize Wireless nodes in an overlay network with near-optimal communication Paths between any pair of nodes. Many of these overlay network constructions are based on the theory of graph spanners. Spanners first appeared in computational geometry, were then discovered as an interesting tool for approximating NP-hard problems, and have recently also attracted a lot of attention in the context of routing and topology control in wireless ad hoc networks.

After introducing the concept of graph spanners and giving several Examples relevant for wireless ad hoc networks, I will discuss various distributed, self-stabilizing protocols for maintaining a spanner among the wireless nodes, using a very simple wireless communication model just to provide a proof of concept. Afterwards, I will also discuss a much more realistic wireless communication model that has just recently been published, and I will demonstrate how to design a self-stabilizing overlay network protocol within that model.