Distributed optimization algorithms for multihop wireless networks

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Aalto-yliopiston teknillinen korkeakoulu | Doctoral thesis (monograph)
Checking the digitized thesis and permission for publishing
Instructions for the author
Date
2010
Major/Subject
Mcode
Degree programme
Language
en
Pages
Verkkokirja (1330 KB, 151 s.)
Series
TKK dissertations in information and computer science 22
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.
Description
Supervising professor
Orponen, Pekka, Prof.
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
Other note
Citation