In this talk I present two recent results in the area of ad-hoc routing. In the first part I discuss the only local (thus practical in a mobile ad-hoc network environment) dominating set construction with non-trivial worst-case guarantees. Having a small dominating set is an important stepping stone for reactive ad-hoc routing algorithms such as AODV or DSR. In the second part of the talk I present GOAFR, a geometric (a.k.a. geographic, location- or position-based) routing algorithm. Simulations show that GOAFR is the most efficient geometric routing algorithm; in addition, GOAFR is also the only algorithm that is asymptotically optimal in the worst case. It is widely believed that understanding ad-hoc routing will lead to a deeper understanding of routing in general.
The first part is joint work with Fabian Kuhn; the second part with Aaron Zollinger and Fabian Kuhn.
Speaker Biography
Roger Wattenhofer received his doctorate in computer science in 1998 from ETH Zurich, Switzerland. From 1999 to 2001 he was in the USA, first at Brown University in Providence, RI, then at Microsoft Research in Redmond, WA. Currently he is an assistant professor at ETH Zurich. Roger Wattenhofer’s research interests include a variety of algorithmic aspects in networking and distributed computing; in particular, peer-to-peer computing and ad-hoc networks.