Optimisation Problems in Wireless Sensor Networks : Local Algorithms and Local Graphs

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.

Basic Income Grant in Namibia, a Viewpoint on the Proposal and on the Work of the BIG Coalition

This thesis studies the basic income grant proposal in Namibia. The proposal suggests a monthly grant of N$100 (approximately 10€) to all those Namibian citizens who do not receive the state pension. This thesis concentrates on the Basic Income Grant (BIG) Coalition and on its work. The formation and transformation of the coalition during the time period between 2003 and 2009 is analyzed with the help of data collected during two field work periods in 2008 and 2009. The data includes interviews, newspaper articles, observations and other background material. The analysis of this material is mainly conducted from organizational viewpoint. The final part of the thesis applies the results to the theory of Mosse, whose propositions about policy and practice will be discussed in relation to the basic income grant pilot project. The thesis argues that social legitimacy has been a vital resource for the work of the BIG Coalition and it has sought for it in various ways. The concept of social legitimacy originates from the resource dependence perspective of Pfeffer and Salancik, who propose that organizations are dependent on their environments, and on the resources provided by the surrounding environment. This thesis studies the concept of social legitimacy in the context of resource dependence theory. Social legitimacy is analyzed in the relations between the coalition and its environment, in the formation of the coalition, in the responses towards criticism, and finally in relation to the propositions concerning policy and practice. The work of the coalition in the pilot project will be analyzed through the propositions of Mosse concerning policy and practice. The results will describe and analyze key events in the formation of the BIG Coalition from the South African proposal until the end of the basic income pilot project. This BIG pilot project conducted in 2008-2009 is one of the most well-known activities of the coalition. The clashes between the coalition and its environment will be analyzed through four case studies. It will be shown that the project has been conducted in order to gain more legitimacy to the basic income grant proposal. The conclusion questions the legitimacy of the BIG Coalition as a research and development organization, and requests for more transparent research on the basic income proposal in Namibia.

Compression of Weighted Graphs

We propose to compress weighted graphs (networks), motivated by the observation that large networks of social, biological, or other relations can be complex to handle and visualize. In the process also known as graph simplication, nodes and (unweighted) edges are grouped to supernodes and superedges, respectively, to obtain a smaller graph. We propose models and algorithms for weighted graphs. The interpretation (i.e. decompression) of a compressed, weighted graph is that a pair of original nodes is connected by an edge if their supernodes are connected by one, and that the weight of an edge is approximated to be the weight of the superedge. The compression problem now consists of choosing supernodes, superedges, and superedge weights so that the approximation error is minimized while the amount of compression is maximized. In this paper, we formulate this task as the 'simple weighted graph compression problem'. We then propose a much wider class of tasks under the name of 'generalized weighted graph compression problem'. The generalized task extends the optimization to preserve longer-range connectivities between nodes, not just individual edge weights. We study the properties of these problems and propose a range of algorithms to solve them, with dierent balances between complexity and quality of the result. We evaluate the problems and algorithms experimentally on real networks. The results indicate that weighted graphs can be compressed efficiently with relatively little compression error.