Efficiency of Wireless Networks: Approximation Algorithms for the Physical Interference Model
By Olga Goussevskaia, ETH Zurich, Switzerland, golga@tik.ee.ethz.ch | Yvonne-Anne Pignolet, IBM Research Zurich Laboratory, Switzerland, yvo@zurich.ibm.com | Roger Wattenhofer, ETH Zurich, Switzerland, wattenhofer@tik.ee.ethz.ch
Abstract
In this monograph we survey results from a newly emerging line of research that targets algorithm analysis in the physical interference model. In the main part of our monograph we focus on wireless scheduling: given a set of communication requests, arbitrarily distributed in space, how can these requests be scheduled efficiently? We study the difficulty of this problem and we examine algorithms for wireless scheduling with provable performance guarantees. Moreover, we present a few results for related problems and give additional context.
Efficiency of Wireless Networks
Efficiency of Wireless Networks surveys results from a newly emerging line of research that targets algorithm analysis in the physical interference model. The primary focus is on wireless scheduling: Given a set of communication requests, arbitrarily distributed in space, how can these requests be scheduled efficiently? It looks at the difficulty of this problem and examines algorithms for wireless scheduling with provable performance guarantees. An abiding fundamental challenge for designers of wireless networks is how to bridge the gap between protocol designers and communication theorists. Efficiency of Wireless Networks delves into this hot topic for the wireless network community and will be of interest to both theoreticians and practitioners
