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

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

Free Preview:

Download extract

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 (pb)
 
ISBN: 978-1-60198-405-0
104 pp. $100.00
Buy E-book (.pdf)
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