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. 9

Yvonne-Anne Pignolet,

Algorithmic Challenges in Wireless Networks
Interference, Energy and Incentives

1^st 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

Series in Distributed Computing in http://www.hartung-gorre.de

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