Hartung-Gorre Verlag Inh.: Dr. Renate Gorre D-78465 Konstanz Fon: +49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartung-gorre.de

S

Series in Distributed Computing
edited by Roger Wattenhofer
Vol. 10

Olga Goussevskaia,

Computational Complexity and Scheduling Algorithms for
Wireless Networks

1^st edition/1. Aufl. 2009, XIV, 132 pages/Seiten, € 64,00.
ISBN 3-86628-279-6 and 978-3-86628-279-7

The main problem studied in this thesis is that of scheduling communication requests in a wireless network. Given a set of wireless links, comprised by sender and receiver nodes, distributed in an arbitrary manner in space, we want to know how much time it takes until all the links are scheduled successfully. This problem is a fundamental part of the more general problem of determining the throughput capacity of a given wireless network.

One of the most important issues when studying wireless network problems is the choice of the interference model. Traditionally, the algorithmic   community has focused on graph-based models. These models typically define a set of interference-edges, containing pairs of nodes within a certain distance to each other, thus modeling interference as a binary and local property. The notion of an interference-edge is a useful abstraction and allows for elegant algorithm design and analysis. It is, however, an oversimplification of the continuous and cumulative nature of the radio signal.

In contrast to the algorithmic community, researchers in information and communication theory have worked with fading channel models, such as the signal-to-interference-plus-noise-ratio (SINR) model, also referred to as the physical interference model. This model represents the physical reality more precisely, since the success of a signal reception depends on all concurrently scheduled transmissions. The analysis of algorithms in this model, however, is more challenging. Because of this increased complexity, the theoretical results in this model have been very limited. Most of the work has either consisted of heuristics and simulation-based evaluations of specific protocols, or has focused on theoretical capacity bounds of special-case networks, such as networks with grid topologies or random node distributions.

In this work we would like to gain a deeper understanding of the fundamental communication limits of wireless networks. This thesis covers several aspects of the problem of scheduling wireless requests. We start with the analysis of the problem's complexity and prove that it is NP-hard in the geometric physical interference model. In this model, it is assumed that nodes live in the Euclidean space, and path-loss is determined by the distances between nodes. Since this problem does not admit optimum solutions in polynomial time, unless P=NP, we concentrate on efficient approximation algorithms. In particular, we propose the first scheduling algorithm that computes a feasible solution in the SINR model in polynomial time with worst-case approximation guarantees for arbitrary network topologies. Besides studying the basic scheduling problem, we also address related problems, such as weighted versions of the scheduling problem, distributed algorithms, and scheduling in combination with analog network coding.

About the Author:

Olga Goussevskaia received her M.Sc degree in computer science from UFMG, Brazil, in 2005. In the same year she joined the Distributed Computing Group of Professor Roger Wattenhofer at ETH Zurich as a Ph.D student and research assistant. In 2009 she earned her Ph.D degree for her work on algorithms for wireless networks.

Keywords: wireless networks, complexity, algorithms, scheduling, physical interference model, NP-hard, approximation algorithms

Series in Distributed Computing

Direkt bestellen bei / to order directly from:

Hartung-Gorre Verlag / D-78465 Konstanz / Germany

Telefon: +49 (0) 7533 97227 Telefax: +49 (0) 7533 97228
http://www.hartung-gorre.de eMail: verlag@hartung-gorre.de