Series in Distributed
Computing
edited
by Roger Wattenhofer
Vol.
9
Yvonne-Anne Pignolet,
Algorithmic Challenges in
Wireless Networks
Interference, Energy and Incentives
1st edition/1. Aufl.
2009, X, 170 pages/Seiten, € 64,00.
ISBN 3-86628-265-6 and 978-3-86628-265-0
Over the past few decades
wireless networks have permeated our lives. We use mobile phones, we operate a
WLAN at home, our laptops connect to our printers using the Bluetooth protocol,
to name but a few examples. This thesis investigates some of the theoretical possibilities
and limitations of wireless networks.
The characteristics of wireless communication pose some challenges not present
in wired networks. E.g., mutual interference impairs the quality of the signals
received and might even prevent the correct reception of messages. Efficient
power control and scheduling algorithms that coordinate the transmissions are
therefore essential for the operation of wireless networks. Moreover, due to
the shared nature of the communication medium, harmful adversarial attacks are
easier to implement, e.g., by jamming a frequency band. Thus, algorithms that
guarantee communication despite such disruptions are necessary. This thesis addresses
these exigent problems and provides lower bounds and algorithms to meet these
challenges. Another difficulty is caused by the fact that wireless devices are
typically equipped with a battery as a source of energy. Recharging this
battery may be tedious or even impossible. In order to prolong the lifetime of
a network, energy-efficient algorithms for wireless networks are needed. We
offer answers to the question of how messages can be aggregated with the twofold
objective of minimizing delay and energy consumption simultaneously.
Usually, wireless devices of a network are assumed to collaborate on a common
application such as environmental monitoring. However, similar to agents in
socio-economic systems, the participants of a large network may operate on a
decentralized control regime just as often, and represent various stake-holders
with conflicting objectives. In many distributed systems, the rules of
interaction cannot be changed. However, a system designer may be able to
influence the agents' behavior by offering payments for certain outcomes. Thus,
a designer faces the following optimization problem: How can a desired outcome
be implemented at minimal cost? And to what extent can the social welfare be
influenced within the bounds of economic rationality, that is, by taking the
implementation cost into account? In this thesis, we aim to lay the
computational and algorithmic foundations of a solution to this problem.
Besides considering classic, benevolent mechanism designers, this thesis
analyzes how malicious mechanism designers can deteriorate the participants'
situation to a larger extent than the amount of money invested.
About the author:
Yvonne
Anne Pignolet received her M.Sc. degree in
computer science from ETH Zurich, Zurich, Switzerland in 2006. 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, Algorithms, Distributed Systems, Interference, Jamming, Scheduling,
Energy, Leverage, Game theory, Aggregation
Direkt
bestellen bei / to order directly from: Hartung.Gorre@t-online.de
Series in Distributed Computing in http://www.hartung-gorre.de
Direkt bestellen bei / to order directly from: Hartung.Gorre@t-online.de
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