As ad-hoc wireless and sensor networks have become more prevalent, fundamentally new algorithmic questions and ideas have arisen. In this talk, these are categorized as follows:
(a) how does one model wireless and sensor networks so that the models are realistic and at the same time mathematically tractable?
(b) how does one abstract as algorithmic problems, design considerations such as minimizing collisions and interference, minimizing energy consumption, and maximizing throughput, while taking advantage of any available geographic information?
(c) since the problems have combinatorial and geometric aspects, how does one combine techniques from combinatorial optimization and
computationalgeometry and implement these efficiently in a distributed setting?
This talk will focus on graph-theoretic models for wireless networks such as unit ball graphs (UBGs) in Euclidean space, quasi-UBGs, UBGs in metric space of low doubling dimension, and growth-bounded graphs. Time permitting, more general models that consider collisions and carrier sensing, will also be discussed. The algorithmic problems considered in the talk will include spanner construction for topology control, domatic partitions for interference-free scheduling, and graph planarization for geometric routing. Algorithmic techniques discussed in this talk will include distributed net-tree construction, distributed LP-rounding, and localized construction of geometric proximity structures.