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
Direkt bestellen
bei / to order directly from: Hartung.Gorre@tonline.de
Series in Distributed Computing in
http://www.hartunggorre.de
Direkt bestellen bei / to order directly from: Hartung.Gorre@tonline.de
HartungGorre Verlag / D78465
Konstanz / Germany
Telefon: +49
(0) 7533 97227 Telefax: +49 (0) 7533
97228
http://www.hartunggorre.de eMail: verlag@hartunggorre.de