Samenvatting
This thesis addresses optimization problems in wireless communication networks.
An optimization problem describes a situation in which one wants to find an optimal
solution among all solutions. Mathematicians study an optimization problem to find
a general method that provides an answer to each instance of the problem. We call
such a method an algorithm. In particular we are interested in finding an efficient
algorithm, an algorithm that provides an answer fast.
We use complexity theory to classify a problem based on the existence of an
efficient algorithm for this problem. Complexity theory focuses on a worstcase
analysis, which reflects the uncertainty we have on future instances of the problem.
There is a class of optimization problems, called NPhard problems, for which
mathematicians do not know whether there exists an efficient algorithm, and it is
widely believed that such an algorithm does not even exist. Therefore, for this class
of problems we are interested in finding efficient approximation algorithms that
provide an approximate optimal solution.
Wireless networks have become an important means of communication, and the
use of wireless networks is likely to increase in future years. A main optimization
problem in these wireless networks is to communicate data over the network to a
central node. This is called data gathering. The quality of a solution depends on
multiple criteria, which include the energy costs of communication, and the delay
in communication.
In this thesis we formulate mathematical models for several gathering problems
in wireless networks. The problems we consider are online and distributed by nature;
i.e. problem information becomes known over time, and the problem information is
distributed over the network. Therefore we focus on online distributed algorithms,
which take these restrictions into account. An online approximation algorithm that
provides a good approximate solution is also called competitive.
For each of the problems we consider, we analyze the theoretical complexity of
the problem, we devise online algorithms, and we analyze the quality of the solutions
of these algorithms.
In Chapter 1 we introduce general concepts and definitions related to optimization
problems, and their mathematical formulation. Also, we outline the wireless
communication problems addressed in this thesis, and our results.
In Chapter 2 we give a background on wireless networks, introducing definitions,
concepts and common problems in this field. These problems form the motivation for
the optimization problems which we describe and analyze in the following chapters.
Chapters 3 and 4 discuss a gathering problem in a wireless network, with constraints
on packet latency, and the possibility of data aggregation. Nodes may delay
messages in order to aggregate multiple messages into a single packet, and forward
this packet to the sink. This aggregation reduces the communication costs at the expense
of an increased message latency. We are interested in finding online algorithms
that minimize both the message latencies, and the network communication costs,
i.e. the energy use of the nodes.
In Chapter 3 we focus on the problem with arbitrary latency constraints which
are modeled as hard constraints. The objective is to minimize the maximum communication
costs of a node. Our main results are the following. We prove that the
problem is NPhard, and we provide offline and online approximation algorithms.
We show that our algorithms are robust, in the sense that they have similar competitive
ratios in case we choose as objective to minimize the sum of communication
costs, in case we assume the cost function to be concave, or in case we limit the
possibilities of aggregation.
In Chapter 4 we consider the same problem, but focus on constant latencies which
are modeled as soft constraints. We use bicriteria optimization to find solutions with
both low costs and small packet latencies. The main contributions of this chapter
are that we present a constant competitive online distributed algorithm for this
problem, in case the latency constraints are not too strict, and an analysis of the
almost synchronous time model, a new time model.
Chapters 5 and 6 discuss a gathering problem in a wireless network with interference.
Interference influences the design of communication algorithms, because it
prevents nodes within the same region to communicate simultaneously. We are interested
in finding online algorithms that send packets to the sink as fast as possible,
explicitly taking into account interference constraints. We use completion times and
flow times as performance measures for the solution.
In Chapter 5 we analyze the problem with objective to minimize completion
times. We focus on minimizing the maximum completion time. We prove that this
problem is NPhard, even in a special case, solving an open problem. We present a
class of constant competitive online algorithms.
In Chapter 6 we consider the wireless gathering problem with objective to minimize
flow times, the time packets are in the network. We classify the problem with
objective minimizing maximum flow times, and with objective minimizing average
flow times; our results indicate that it is unlikely to find efficient algorithms for these
problems. Then we present an online distributed algorithm which is nearoptimal
in case the algorithm can send packets at a faster speed than currently available;
the speed factor gives an indication of the effect of faster communication devices on
the quality of the solution.
Originele taal2  Engels 

Kwalificatie  Doctor in de Filosofie 
Toekennende instantie 

Begeleider(s)/adviseur 

Datum van toekenning  17 apr 2008 
Plaats van publicatie  Eindhoven 
Uitgever  
Gedrukte ISBN's  9789038612379 
DOI's  
Status  Gepubliceerd  2008 
Vingerafdruk Duik in de onderzoeksthema's van 'Online gathering algorithms for wireless networks'. Samen vormen ze een unieke vingerafdruk.
Citeer dit
Korteweg, P. (2008). Online gathering algorithms for wireless networks. Technische Universiteit Eindhoven. https://doi.org/10.6100/IR633780