Online gathering algorithms for wireless networks

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 worst-case analysis, which reflects the uncertainty we have on future instances of the problem. There is a class of optimization problems, called NP-hard 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 NP-hard, 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 NP-hard, 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 near-optimal 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