Foundations and Trends® in Networking > Vol 4 > Issue 3

Efficiency of Wireless Networks: Approximation Algorithms for the Physical Interference Model

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
 
Suggested Citation
Olga Goussevskaia, Yvonne-Anne Pignolet and Roger Wattenhofer (2010), "Efficiency of Wireless Networks: Approximation Algorithms for the Physical Interference Model", Foundations and TrendsĀ® in Networking: Vol. 4: No. 3, pp 313-420. http://dx.doi.org/10.1561/1300000019

Published: 16 Dec 2010
© 2010 O. Goussevskaia, Y.-A. Pignolet and R. Wattenhofer
 
Subjects
Modeling and Analysis
 

Free Preview:

Article Help

Share

Download article
In this article:
1 Introduction
2 Models and Definitions
3 Scheduling Without Power Control
4 Scheduling With Power Control
5 Related Problems
6 Alternative Interference Models
7 Conclusions
References

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.

DOI:10.1561/1300000019
ISBN: 978-1-60198-404-3
104 pp. $75.00
Buy book
 
ISBN: 978-1-60198-405-0
104 pp. $100.00
Buy E-book
Table of contents:
1. Introduction
2. Models and Definitions
3. Scheduling Without Power Control
4. Scheduling With Power Control
5. Related Problems
6. Alternative Interference Models
7. Conclusions
References

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

 
NET-019