Ad-Hoc and sensor networks: worst-case vs. average-case

Ad-hoc and sensor networks are rapidly growing areas of research which study the problems arising when small and feeble devices build a communication infrastructure. A vast majority of researchers in the field make strong average-case assumptions about these networks, for example that the devices are distributed uniformly at random. To system builders on the other hand many of these assumptions appear suspicious. In this paper we advocate an algorithmic (worst-case) approach to ad-hoc and sensor networking. We survey a few also worst-case efficient algorithms for topology control, clustering, and routing.