The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
|
|
|
Distributed Optimization Algorithms for Multihop Wireless Networks
André Schumacher
Doctoral dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the Faculty of Information and Natural Sciences for public examination and debate in Auditorium M1 at the Aalto University School of Science and Technology (Espoo, Finland) on the 17th of December 2010 at 12 noon.
Dissertation in PDF format (ISBN 978-952-60-3481-2) [1330 KB]
Dissertation is also available in print (ISBN 978-952-60-3480-5)
Abstract
Recent technological advances in low-cost computing and communication hardware design have led to the feasibility of large-scale deployments of wireless ad hoc and sensor networks. Due to their wireless and decentralized nature, multihop wireless networks are attractive for a variety of applications. However, these properties also pose significant challenges to their developers and therefore require new types of algorithms. In cases where traditional wired networks usually rely on some kind of centralized entity, in multihop wireless networks nodes have to cooperate in a distributed and self-organizing manner. Additional side constraints, such as energy consumption, have to be taken into account as well.
This thesis addresses practical problems from the domain of multihop wireless networks and investigates the application of mathematically justified distributed algorithms for solving them. Algorithms that are based on a mathematical model of an underlying optimization problem support a clear understanding of the assumptions and restrictions that are necessary in order to apply the algorithm to the problem at hand. Yet, the algorithms proposed in this thesis are simple enough to be formulated as a set of rules for each node to cooperate with other nodes in the network in computing optimal or approximate solutions. Nodes communicate with their neighbors by sending messages via wireless transmissions. Neither the size nor the number of messages grows rapidly with the size of the network.
The thesis represents a step towards a unified understanding of the application of distributed optimization algorithms to problems from the domain of multihop wireless networks. The problems considered serve as examples for related problems and demonstrate the design methodology of obtaining distributed algorithms from mathematical optimization methods.
Keywords: ad hoc network, approximation algorithm, distributed algorithm, lifetime maximization, network optimization, network utility maximization, optimization algorithm, primal-dual algorithm, routing, sensor network, sleep scheduling, wireless communication
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
© 2010 Aalto University School of Science and Technology
Last update 2011-05-26