HartungGorre Verlag
Inh.: Dr.
Renate Gorre D78465
Konstanz Fon:
+49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartunggorre.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 3866282796 and 9783866282797
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 graphbased models. These models typically define a
set of interferenceedges, containing pairs of nodes within a certain distance
to each other, thus modeling interference as a binary
and local property. The notion of an interferenceedge 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
signaltointerferenceplusnoiseratio (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 simulationbased evaluations of specific protocols, or has
focused on theoretical capacity bounds of specialcase 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 NPhard in the geometric physical
interference model. In this model, it is assumed that nodes live in the
Euclidean space, and pathloss 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 worstcase 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, NPhard, approximation algorithms
Series in Distributed Computing
Direkt bestellen
bei / to order directly from:
HartungGorre Verlag / D78465
Konstanz / Germany
Telefon: +49
(0) 7533 97227 Telefax: +49 (0) 7533
97228
http://www.hartunggorre.de eMail: verlag@hartunggorre.de