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.

Analysing local algorithms in location-aware quasi-unit-disk graphs

A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds; here r is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within r hops from the node. We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set. We also study local algorithms on quasi-UDGs, which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs.

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.

Kaaoksen kautta tai hitaasti kiiruhtaen : Pedagoginen muutosprosessi luokanopettajan näkökulmasta

The purpose of this study was to describe and get a deep understanding of pedagogical change process. The phases of pedagogical change process and the nature and the role of teacher s pedagogical thinking in it were mapped. The change process as a whole was also modeled. The previous research of teaching change process has had been scarce on an individual teacher level, but on a school level it has been investigated abundantly. The theoretical background of this study consists of theories of teacher s pedagogical thinking and action and how their thinking and action change and develop. Teacher change has been researched from the point of view of both school change and professional development. The basic principle in the theoretical frame is that change in teacher s thinking leads to change in action. Three men teachers and a woman teacher who have put change into practice took part in this study. The data consisted of two parts: teachers essays of their change process and interviews that were based on the essays. The data was analysed by content analysis. The categorizations of both parts of the data were made separately but they were interpreted together. In this way a deep understanding of pedagogical change process could be reached. The results of this study were descriptions of the phases of pedagogical change process and the nature and the role of teacher s pedagogical thinking in it. In addition a model of pedagogical change process was presented. Pedagogical change process started up because of disorder in teacher s pedagogical thinking and action. The disorder leads to an absolute necessity to change the activities. Change activities stabilize throughout intuitive experiments and reflection-on-action. The change in a teacher s thinking is a prerequisite for the start of the process but also, a teacher s thinking develops as a result of the process. Thus, the whole process results in a real, deep level change in instruction and in the teacher s thinking. That is why pedagogical change processes are visible, significant and they have wide and extensive effects. The study gives out information of controlling the change processes. Consequently, the results of this study encourage teachers to confront change and put their new ideas into practice. Keywords change, development, pedagogical thinking, pedagogical action, teaching-studying-learning process

Locality and order-invariant logics

Malli on logiikassa käytetty abstraktio monille matemaattisille objekteille. Esimerkiksi verkot, ryhmät ja metriset avaruudet ovat malleja. Äärellisten mallien teoria on logiikan osa-alue, jossa tarkastellaan logiikkojen, formaalien kielten, ilmaisuvoimaa malleissa, joiden alkioiden lukumäärä on äärellinen. Rajoittuminen äärellisiin malleihin mahdollistaa tulosten soveltamisen teoreettisessa tietojenkäsittelytieteessä, jonka näkökulmasta logiikan kaavoja voidaan ajatella ohjelmina ja äärellisiä malleja niiden syötteinä. Lokaalisuus tarkoittaa logiikan kyvyttömyyttä erottaa toisistaan malleja, joiden paikalliset piirteet vastaavat toisiaan. Väitöskirjassa tarkastellaan useita lokaalisuuden muotoja ja niiden säilymistä logiikkoja yhdistellessä. Kehitettyjä työkaluja apuna käyttäen osoitetaan, että Gaifman- ja Hanf-lokaalisuudeksi kutsuttujen varianttien välissä on lokaalisuuskäsitteiden hierarkia, jonka eri tasot voidaan erottaa toisistaan kasvavaa dimensiota olevissa hiloissa. Toisaalta osoitetaan, että lokaalisuuskäsitteet eivät eroa toisistaan, kun rajoitutaan tarkastelemaan äärellisiä puita. Järjestysinvariantit logiikat ovat kieliä, joissa on käytössä sisäänrakennettu järjestysrelaatio, mutta sitä on käytettävä siten, etteivät kaavojen ilmaisemat asiat riipu valitusta järjestyksestä. Määritelmää voi motivoida tietojenkäsittelyn näkökulmasta: vaikka ohjelman syötteen tietojen järjestyksellä ei olisi odotetun tuloksen kannalta merkitystä, on syöte tietokoneen muistissa aina jossakin järjestyksessä, jota ohjelma voi laskennassaan hyödyntää. Väitöskirjassa tutkitaan minkälaisia lokaalisuuden muotoja järjestysinvariantit ensimmäisen kertaluvun predikaattilogiikan laajennukset yksipaikkaisilla kvanttoreilla voivat toteuttaa. Tuloksia sovelletaan tarkastelemalla, milloin sisäänrakennettu järjestys lisää logiikan ilmaisuvoimaa äärellisissä puissa.

Specifying Reuse Interfaces for Task-Oriented Framework Specialization

Reuse of existing carefully designed and tested software improves the quality of new software systems and reduces their development costs. Object-oriented frameworks provide an established means for software reuse on the levels of both architectural design and concrete implementation. Unfortunately, due to frame-works complexity that typically results from their flexibility and overall abstract nature, there are severe problems in using frameworks. Patterns are generally accepted as a convenient way of documenting frameworks and their reuse interfaces. In this thesis it is argued, however, that mere static documentation is not enough to solve the problems related to framework usage. Instead, proper interactive assistance tools are needed in order to enable system-atic framework-based software production. This thesis shows how patterns that document a framework s reuse interface can be represented as dependency graphs, and how dynamic lists of programming tasks can be generated from those graphs to assist the process of using a framework to build an application. This approach to framework specialization combines the ideas of framework cookbooks and task-oriented user interfaces. Tasks provide assistance in (1) cre-ating new code that complies with the framework reuse interface specification, (2) assuring the consistency between existing code and the specification, and (3) adjusting existing code to meet the terms of the specification. Besides illustrating how task-orientation can be applied in the context of using frameworks, this thesis describes a systematic methodology for modeling any framework reuse interface in terms of software patterns based on dependency graphs. The methodology shows how framework-specific reuse interface specifi-cations can be derived from a library of existing reusable pattern hierarchies. Since the methodology focuses on reusing patterns, it also alleviates the recog-nized problem of framework reuse interface specification becoming complicated and unmanageable for frameworks of realistic size. The ideas and methods proposed in this thesis have been tested through imple-menting a framework specialization tool called JavaFrames. JavaFrames uses role-based patterns that specify a reuse interface of a framework to guide frame-work specialization in a task-oriented manner. This thesis reports the results of cases studies in which JavaFrames and the hierarchical framework reuse inter-face modeling methodology were applied to the Struts web application frame-work and the JHotDraw drawing editor framework.

Computational Identification of Recessive Mutations in Cancers using High Throughput SNP-arrays

This thesis presents a highly sensitive genome wide search method for recessive mutations. The method is suitable for distantly related samples that are divided into phenotype positives and negatives. High throughput genotype arrays are used to identify and compare homozygous regions between the cohorts. The method is demonstrated by comparing colorectal cancer patients against unaffected references. The objective is to find homozygous regions and alleles that are more common in cancer patients. We have designed and implemented software tools to automate the data analysis from genotypes to lists of candidate genes and to their properties. The programs have been designed in respect to a pipeline architecture that allows their integration to other programs such as biological databases and copy number analysis tools. The integration of the tools is crucial as the genome wide analysis of the cohort differences produces many candidate regions not related to the studied phenotype. CohortComparator is a genotype comparison tool that detects homozygous regions and compares their loci and allele constitutions between two sets of samples. The data is visualised in chromosome specific graphs illustrating the homozygous regions and alleles of each sample. The genomic regions that may harbour recessive mutations are emphasised with different colours and a scoring scheme is given for these regions. The detection of homozygous regions, cohort comparisons and result annotations are all subjected to presumptions many of which have been parameterized in our programs. The effect of these parameters and the suitable scope of the methods have been evaluated. Samples with different resolutions can be balanced with the genotype estimates of their haplotypes and they can be used within the same study.

Synthesis of neoglycoconjugates and oligosaccharides with potential anti-Helicobacter pylori activity

The significance of carbohydrate-protein interactions in many biological phenomena is now widely acknowledged and carbohydrate based pharmaceuticals are under intensive development. The interactions between monomeric carbohydrate ligands and their receptors are usually of low affinity. To overcome this limitation natural carbohydrate ligands are often organized as multivalent structures. Therefore, artificial carbohydrate pharmaceuticals should be constructed on the same concept, as multivalent carbohydrates or glycoclusters. Infections of specific host tissues by bacteria, viruses, and fungi are among the unfavorable disease processes for which suitably designed carbohydrate inhibitors represent worthy targets. The bacterium Helicobacter pylori colonizes more than half of all people worldwide, causing gastritis, gastric ulcer, and conferring a greater risk of stomach cancer. The present medication therapy for H. pylori includes the use of antibiotics, which is associated with increasing incidence of bacterial resistance to traditional antibiotics. Therefore, the need for an alternative treatment method is urgent. In this study, four novel synthesis procedures of multivalent glycoconjugates were created. Three different scaffolds representing linear (chondroitin oligomer), cyclic (γ-cyclodextrin), and globular (dendrimer) molecules were used. Multivalent conjugates were produced using the human milk type oligosaccharides LNDFH I (Lewis-b hexasaccharide), LNnT (Galβ1-4GlcNAcβ1-3Galβ1-4Glc), and GlcNAcβ1-3Galβ1-4GlcNAcβ1-3Galβ1-4Glc all representing analogues of the tissue binding epitopes for H. pylori. The first synthetic method included the reductive amination of scaffold molecules modified to express primary amine groups, and in the case of dendrimer direct amination to scaffold molecule presenting 64 primary amine groups. The second method described a direct procedure for amidation of glycosylamine modified oligosaccharides to scaffold molecules presenting carboxyl groups. The final two methods that were created both included an oxime-linkage on linkers of different length. All the new synthetic procedures synthesized had the advantage of using unmodified reducing sugars as starting material making it easy to synthesize glycoconjugates of different specificity. In addition, the binding activity of an array of neoglycolipids to H. pylori was studied. Consequently, two new neolacto-based structures, Glcβ1-3Galβ1-4GlcNAcβ1-3Galβ1-4Glcβ1-Cer and GlcAβ1-3Galβ1-4GlcNAcβ1-3Galβ1-4Glcβ1-Cer, with binding activity toward H. pylori were discovered. Interestingly, N-methyl and N-ethyl amide modification of the GlcAβ1-3Galβ1-4GlcNAcβ1-3Galβ1-4Glcβ1-Cer glucuronic acid residue resulted in more effective H. pylori binding epitopes than the parent molecule.

Anti-TNF treatment in juvenile idiopathic arthritis and associated uveitis : Clinical perspectives on growth, uveitis, and drug survival

Juvenile idiopathic arthritis (JIA) is a heterogeneous group of childhood chronic arthritides, associated with chronic uveitis in 20% of cases. For JIA patients responding inadequately to conventional disease-modifying anti-rheumatic drugs (DMARDs), biologic therapies, anti-tumor necrosis factor (anti-TNF) agents are available. In this retrospective multicenter study, 258 JIA-patients refractory to DMARDs and receiving biologic agents during 1999-2007 were included. Prior to initiation of anti-TNFs, growth velocity of 71 patients was delayed in 75% and normal in 25%. Those with delayed growth demonstrated a significant increase in growth velocity after initiation of anti-TNFs. Increase in growth rate was unrelated to pubertal growth spurt. No change was observed in skeletal maturation before and after anti-TNFs. The strongest predictor of change in growth velocity was growth rate prior to anti-TNFs. Change in inflammatory activity remained a significant predictor even after decrease in glucocorticoids was taken into account. In JIA-associated uveitis, impact of two first-line biologic agents, etanercept and infliximab, and second-line or third-line anti-TNF agent, adalimumab, was evaluated. In 108 refractory JIA patients receiving etanercept or infliximab, uveitis occurred in 45 (42%). Uveitis improved in 14 (31%), no change was observed in 14 (31%), and in 17 (38%) uveitis worsened. Uveitis improved more frequently (p=0.047) and frequency of annual uveitis flares was lower (p=0.015) in those on infliximab than in those on etanercept. In 20 patients taking adalimumab, 19 (95%) had previously failed etanercept and/or infliximab. In 7 patients (35%) uveitis improved, in one (5%) worsened, and in 12 (60%) no change occurred. Those with improved uveitis were younger and had shorter disease duration. Serious adverse events (AEs) or side-effects were not observed. Adalimumab was effective also in arthritis. Long-term drug survival (i.e. continuation rate on drug) with etanercept (n=105) vs. infliximab (n=104) was at 24 months 68% vs. 68%, and at 48 months 61% vs. 48% (p=0.194 in log-rank analysis). First-line anti-TNF agent was discontinued either due to inefficacy (etanercept 28% vs. infliximab 20%, p=0.445), AEs (7% vs. 22%, p=0.002), or inactive disease (10% vs. 16%, p=0.068). Females, patients with systemic JIA (sJIA), and those taking infliximab as the first therapy were at higher risk for treatment discontinuation. One-third switched to the second anti-TNF agent, which was discontinued less often than the first. In conclusion, in refractory JIA anti-TNFs induced enhanced growth velocity. Four-year treatment survival was comparable between etanercept and infliximab, and switching from first-line to second-line agent a reasonable therapeutic option. During anti-TNF treatment, one-third with JIA-associated anterior uveitis improved.

Cultural Trauma and Life Stories

The purpose of this work is to use the concepts of human time and cultural trauma in a biographical study of the turning points in the recent history of Estonia. This research is primarily based on 148 in-depth biographical interviews conducted in Estonia and Sweden in 1995-2005, supplemented by excerpts from 5 collections and 10 individually published autobiographies. The main body of the thesis consists of six published and of two forthcoming separate refereed articles, summarised in the theoretical introduction, and Appendix of the full texts of three particular life stories. The topic of the first article is the generational composition and the collective action frames of anti-Soviet social mobilisation in Estonia in 1940-1990. The second article details the differentiation of the rites of passage and the calendar traditions as a strategy to adapt to the rapidly changed political realities, comparatively in Soviet Estonia and among the boat-refugees in Sweden. The third article investigates the life stories of the double-minded strategic generation of the Estonian-inclined Communists, who attempted to work within the Soviet system while professing to uphold the ideals of pre-war Estonia. The fourth article is concentrated on the problems of double mental standards as a coping strategy in a contradictory social reality. The fifth article implements the theory of cultural trauma for the social practice of singing nationalism in Estonia. The sixth article bridges the ideas of Russian theoreticians concerning cultural dialogue and the Western paradigm of cultural trauma, with examples from Estonian Russian life stories. The seventh article takes a biographical look at the logic of the unraveling of cultural trauma through four Soviet decades. The eighth article explores the re-shaping of citizen activities as a strategy of coping with the loss of the independent nation state, comparatively in Soviet Estonia and among Swedish Estonians. Cultural trauma is interpreted as the re-ordering of the society s value-normative constellation due to sharp, violent, usually political events. The first one under consideration was caused by the occupations of the Republic of Estonia by the Soviet army in 1940-45. After half a century of suppression the memories of these events resurfaced as different stories describing the long-term, often inter-generational strategies of coping with the value collapse. The second cultural trauma is revealed together with the collapse of the Soviet power and ideology in Estonia in 1991. According to empirical data, the following three trauma discourses have been reconstructed: - the forced adaptation to Soviet order of the homeland Estonians; - the difficulty of preserving Estonian identity in exile (Sweden); - the identity crisis of the Russian population of Estonia. Comparative analyses of these discourses have shown that opposing experiences and worldviews cause conflicting interpretations of the past. Different social and ethnic groups consider coping with cultural trauma as a matter of self-defence and create appropriate usable pasts to identify with. Keywords: human time, cultural trauma, frame analysis, discourse, life stories