Optimisation problems in wireless sensor networks

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.

A simple local 3-approximation algorithm for vertex cover

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required. (c) 2009 Elsevier B.V. All rights reserved.

The Home of Hearing : George Lindbeck's understanding of community

The aim of this thesis was to examine the understanding of community in George Lindbeck s The Nature of Doctrine. Intrinsic to this question was also examining how Lindbeck understands the relation between the text and the world which both meet in a Christian community. Thirdly this study also aimed at understanding what the persuasiveness of this understanding depends on. The method applied for this task was systematic analysis. The study was conducted by first providing an orientation into the nontheological substance of the ND which was assumed useful with respect to the aim of this study. The study then went on to explore Lindbeck in his own context of postliberal theology in order to see how the ND was received. It also attempted to provide a picture of how the ND relates to Lindbeck as a theologian. The third chapter was a descriptive analysis into the cultural-linguistic perspective, which is understood as being directly proportional to his understanding of community. The fourth chapter was an analysis into how the cultural-linguistic perspective sees the relation between the text and the world. When religion is understood from a cultural-linguistic perspective, it presents itself as a cultural-linguistic entity, which Lindbeck understands as a comprehensive interpretive scheme which structures human experience and understanding of oneself and the world in which one lives. When one exists in this entity, it is the entity which shapes the subjectivities of all those who are at home in this entity which makes participation in the life of a cultural linguistic entity a condition for understanding it. Religion is above all an external word that moulds and shapes our religious existence and experience. Understanding faith then as coming from hearing, is something that correlates with the cultural-linguistic depiction of reality. Religion informs us of a religious reality, it does not originate in any way from ourselves. This externality linked to the axiomatic nature of religion is also something that distinguishes Lindbeck sharply from liberalist tendencies, which understand religion as ultimately expressing the prereflective depths of the inner self. Language is the central analogy to understanding the medium in which one moves when inhabiting a cultural-linguistic system because language is the transmitting medium in which the cultural-linguistic system is embodied. The realism entailed in Lindbeck s understanding of a community is that we are fundamentally on the receiving end when it comes to our identities whether cultural or religious. We always witness to something. Its persuasiveness rests on the fact that we never exist in an unpersuaded reality. The language of Christ is a self-sustaining and irreducible cultural-linguistic entity, which is ontologically founded upon Christ. It transmits the reality of a new being. The basic relation to the world for a Christian is that of witnessing salvation in Christ: witnessing Christ as the home of hearing the message of salvation, which is the God-willed way. Following this logic, the relation of the world and the text is one of relating to the world from the text, i.e. In Christ through the word (text) for the world, because it assumes it s logic from the way Christ ontologically relates to us.

Locally checkable proofs

This work studies decision problems from the perspective of nondeterministic distributed algorithms. For a yes-instance there must exist a proof that can be verified with a distributed algorithm: all nodes must accept a valid proof, and at least one node must reject an invalid proof. We focus on locally checkable proofs that can be verified with a constant-time distributed algorithm. For example, it is easy to prove that a graph is bipartite: the locally checkable proof gives a 2-colouring of the graph, which only takes 1 bit per node. However, it is more difficult to prove that a graph is not bipartite—it turns out that any locally checkable proof requires Ω(log n) bits per node. In this work we classify graph problems according to their local proof complexity, i.e., how many bits per node are needed in a locally checkable proof. We establish tight or near-tight results for classical graph properties such as the chromatic number. We show that the proof complexities form a natural hierarchy of complexity classes: for many classical graph problems, the proof complexity is either 0, Θ(1), Θ(log n), or poly(n) bits per node. Among the most difficult graph properties are symmetric graphs, which require Ω(n2) bits per node, and non-3-colourable graphs, which require Ω(n2/log n) bits per node—any pure graph property admits a trivial proof of size O(n2).

Planar subgraphs without low-degree nodes

We study the following problem: given a geometric graph G and an integer k, determine if G has a planar spanning subgraph (with the original embedding and straight-line edges) such that all nodes have degree at least k. If G is a unit disk graph, the problem is trivial to solve for k = 1. We show that even the slightest deviation from the trivial case (e.g., quasi unit disk graphs or k = 1) leads to NP-hard problems.