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.

Power and Authority. Birgitta of Sweden and her Revelations

In the High Middle Ages female saints were customarily noble virgins. Thus, as a wife and a mother of eight children, the Swedish noble lady Birgitta (1302/3 1373) was an atypical candidate for sanctity. However, in 1391 she was canonized only 18 years after her death and became a role model for many late medieval women, who were mothers and widows. The dissertation Power and Authority Birgitta of Sweden and Her Revelations investigates how Birgitta went about establishing her power and authority during the first ten years of her career as a living saint, in 1340 1349. It is written from the perspectives of gender, authority, and power. The sources consist of approximately seven hundred revelations, hagiographical texts and other medieval documents. This work concentrates on the interaction between Birgitta and her audience. During her lifetime Birgitta was already regarded as a holy woman, as a living saint. A living saint could be given no formal papal or other recognition, for one could never be certain about his or her future activities. Thus, the living saint needed an audience for whom to perform signs of sanctity. In this study particular attention is paid to situations within which the power relations between the living saint and her audience can be traced and are open to critical analysis. Situations of conflict that arose in Birgitta s life are especially fruitful for this purpose. During the Middle Ages, institutional power and authority were exclusively in the hands of secular male leaders and churchmen. In this work it is argued, however, that Birgitta used different kinds of power than men. It is evident that she exercized influence on lay people as well as on secular and clerical authorities. The second, third, and fourth chapter of this study examine the beginning of Birgitta s career as a visionary, what factors and influences lay behind it, and what kind of roles they played in establishing her religious authority. The fifth, sixth, and seventh chapter concentrate on Birgitta s exercising of power in specific situations during her time in Sweden until she left on a pilgrimage to Rome in 1349. The central question is how she exercised power with different people. As a result, this book will offer a narrative of Birgitta s social interactions in Sweden seen from the perspectives of power and authority. Along with the concept of power, authority is a key issue. By definition, one who has power also has authority but a person who does not have official power can, nevertheless, have authority. Authority in action is defined here as meaning that a person was listened to. Birgitta acted both in situations of open conflict and where no conflict was evident. Her strategies included, for example, inducement, encouragement and flattery. In order to make people do as she felt was right she also threatened them openly with divine wrath. Sometimes she even used both positive persuasion and threats. Birgitta s power seems very similar to that of priests and ascetics. Common to all of them was that their power demanded interaction with other people and audiences. Because Birgitta did not have power and authority ex officio she had to persuade people to believe in her powers. She did this because she was convinced of her mission and sought to make people change their lives. In so doing, she moved from the domestic field to the public fields of religion and politics.

Essays on Microcredit in Rural Bangladesh

This thesis is a collection of three essays on Bangladeshi microcredit. One of the essays examines the effect of microcredit on the cost of crime. The other two analyze the functioning mechanism of microcredit programs, i.e. credit allocation rules and credit recovery policy. In Essay 1, the demand for microcredit and its allocation rules is studied. Microcredit is claimed to be the most effective means of supplying credit to the poorest of the poor in rural Bangladesh. This fact has not yet been examined among households who demand microcredit. The results of this essay show that educated households are more likely to demand microcredit and its demand does not differ by sex. The results also show that microcredit programs follow different credit allocation rules for male and female applicants. Education is an essential characteristic for both sexes that credit programs consider in allocating credit. In Essay 2, the focus is to establish a link between microcredit and the incidence of rural crime in Bangladesh. The basic hypothesis is that microcredit programs jointly hold the group responsibility which provides an incentive for group members to protect each other from criminal gang in order to safeguard their own economic interests. The key finding of this essay is that the average cost of crime for non-borrowers is higher than that for borrowers. In particular, 10% increase in the credit reduces the costs of crime by 4.2%. The third essay analyzes the reasons of high repayment rate amid Bangladeshi microcredit programs. The existing literature argues that credit applicants are able to screen out the high risk applicants in the group formulation stage using their superior local information. In addition, due to the joint liability mechanism of the programs, group members monitor each others economic activities to ensure the minimal misuse of credit. The arguments in the literature are based on the assumption that once the credit is provided, credit programs have no further role in ensuring that repayments are honored by the group. In contrast, using survey data this essay documents that credit programs use in addition organizational pressures such as humiliation and harassment the non-payer to recover the unpaid installments. The results also show that the group mechanisms do not have a significant effect in recovering default dues.

Causes and consequences of inbreeding in the ant Formica exsecta

Human actions cause destruction and fragmentation of natural habitats, predisposing populations to loss of genetic diversity and inbreeding, which may further decrease their fitness and survival. Understanding these processes is a main concern in conservation genetics. Yet data from natural populations is scarce, particularly on invertebrates, owing to difficulties in measuring both fitness and inbreeding in the wild. Ants are social insects, and a prime example of an ecologically important group for which the effects of inbreeding remain largely unstudied. Social insects serve key roles in all terrestrial ecosystems, and the division of labor between the females in the colonies queens reproduce, workers tend to the developing brood probably is central to their ecological success. Sociality also has important implications for the effects of inbreeding. Despite their relative abundance, the effective population sizes of social insects tend to be small, owing to the low numbers of reproductive individuals relative to the numbers of sterile workers. This may subject social insects to loss of genetic diversity and subsequent inbreeding depression. Moreover, both the workers and queens can be inbred, with different and possibly multiplicative consequences. The aim of this study was to investigate causes and consequences of inbreeding in a natural population of ants. I used a combination of long-term field and genetic data from colonies of the narrow-headed ant Formica exsecta to examine dispersal, mating behavior and the occurrence of inbreeding, and its consequences on individual and colony traits. Mating in this species takes place in nuptial flights that have been assumed to be population-wide and panmictic. My results, however, show that dispersal is local, with queens establishing new colonies as close as 60 meters from their natal colony. Even though actual sib-mating was rare, individuals from different but related colonies pair, which causes the population to be inbred. Furthermore, multiple mates of queens were related to each other, which also indicates localized mating flights. Hence, known mechanisms of inbreeding avoidance, dispersal and multiple mating, were not effective in this population, as neither reduced inbreeding level of the future colony. Inbreeding had negative consequences both at the individual and colony level. A queen that has mated with a related male produces inbred workers, which impairs the colony s reproductive success. The inbred colonies were less productive and, specifically, produced fewer new queens, possibly owing to effects of inbreeding on the caste determination of female larvae. A striking finding was that males raised in colonies with inbred workers were smaller, which reflects an effect of the social environment as males, being haploid, cannot be inbred themselves. The queens produced in the inbred colonies, in contrast, were not smaller, but their immune response was up-regulated. Inbreeding had no effect on queen dispersal, but inbred queens had a lower probability of successfully founding a new colony. Ultimately, queens that survived through the colony founding phase had a shorter lifespan. This supports the idea that inbreeding imposes a genetic stress, leading to inbreeding depression on both the queen and the colony level. My results show that inbreeding can have profound consequences on insects in the wild, and that in social species the effects of inbreeding may be multiplicative and mediated through the diversity of the social environment, as well as the genetic makeup of the individuals themselves. This emphasizes the need to take into account all levels of organization when assessing the effects of genetic diversity in social animals.

The effects of eutrophication on alternative reproductive tactics in threespine sticklebacks

When organisms compete for mates and fertilisations, the process of sexual selection drives the evolution of traits that increase reproductive success. The traits targeted by selection, and the extent to which they change, are constrained by the local environment. Sexual selection due to female mate choice can be undermined by alternative reproductive tactics (ARTs), which refers to discontinuous variation in traits or behaviours used in reproduction. As human activities are rapidly changing our planet, this raises the question how ARTs will be affected. Fish show a bewildering diversity of ARTs, which make them good model organisms to answer these questions. One example of human-induced environmental change, which is affecting aquatic ecosystems around the world, is eutrophication, the over-enrichment of water bodies with nutrients. One of its effects is decreased underwater visibility due to increases in both turbidity and vegetation density. The aims of this thesis were to investigate the effects increased turbidity and vegetation density have on an ART in sticklebacks, a fish common to marine and fresh water bodies of the Northern hemisphere. I furthermore investigated how this affected sexual selection for male size, a trait commonly under selection. I used a combination of behavioural observations in microcosms, where I manipulated underwater visibility, with collection of genetic material to reconstruct parentage of broods, and thus identify sneak fertilisations. The results show that turbidity might have weak negative effects on the frequency of sneaking behaviour, although this behaviour was rather infrequent in these experiments, which complicates firm conclusions. In dense vegetation the number of sneak fertilisations decreased slightly, as fewer nesting males sneaked, while the number of non-nesting males sneaking remained constant. The paternity analyses revealed that a significantly smaller fraction of eggs was sneak fertilised under dense vegetation. Furthermore, amongst the nesting males that sneaked, the amount of eggs sneak fertilised correlated positively with courtship success. A reduction in sneaking by these males under dense vegetation equalised the distribution of fertilisation success, in turn contributing to a decrease in the opportunity for selection. Under dense vegetation significantly more males built nests, which has also been observed in previous field studies. In a separate experiment we addressed if such changes in the proportion of nesters and non-nesters, without changes in visibility, affected the incidence of sneak fertilisation. My results show this was not the case, likely because sneaking is an opportunistic tactic shown by both nesters and non-nesters. Non-nesters did sneak proportionately more when there were many of them, which could be due to changes in the cost-benefit ratio of sneaking. As nesters can only attack one intruder at a time, the costs and risks per sneaker will decrease as the number of sneakers increases. The defensive behaviours shown by the nesters before spawning shifted to a more aggressive form of nest defence. This could be because less aggressive behaviours lose their effectiveness when the number of intruders increases. It could also indicate that the risks associated with aggressive behaviours decrease when there are fewer fellow nesters, as other studies indicate nesters are competitive and aggressive individuals. Under turbid conditions I did not detect changes in the opportunity for selection, based on fertilisation success, nor was male size under significant selection under clear or turbid conditions. More thorough analyses under densely vegetated conditions across the nesting, courtship and fertilisation stages revealed a decrease in the opportunity for selection across all stages. A reduction in sneaking by nesters contributed to this. During the nesting stage, but not during later stages, body size was under significant directional selection under sparse, but not dense vegetation. This illustrates the importance of considering all selection stages to get a complete picture of how environmental changes affect sexual selection. Leaving out certain stages or subgroups can result in incomplete or misleading results.

Spatial ecology of a specialist insect herbivore : the leaf-mining moth Tischeria ekebladella on the pedunculate oak Quercus robur

Herbivorous insects comprise a major part of terrestrial biodiversity, and their interactions with their host plants and natural enemies are of vast ecological importance. A large body of research demonstrates that the ecology and evolution of these insects may be affected by trophic interactions, by abiotic influences, and by intraspecific processes, but so far research on these individual aspects has rarely been combined. This thesis uses the leaf-mining moth Tischeria ekebladella and the pedunculate oak (Quercus robur) as a case study to assess how spatial variation in trophic interactions and the physical distribution of host trees jointly affect the distribution, dynamics and evolution of a host-specific herbivore. With respect to habitat quality, Tischeria ekebladella experiences abundant variation at several spatial scales. Most of this variation occurs at small scales notably among leaves and shoots within individual trees. While hypothetically this could cause moths to evolve an ability to select leaves and shoots of high quality, I did not find any coupling between female preference and offspring performance. Based on my studies on temporal variation in resource quality I therefore propose that unpredictable temporal changes in the relative rankings of individual resource units may render it difficult for females to predict the fate of their developing offspring. With respect to intraspecific processes, my results suggest that limited moth dispersal in relation to the spatial distribution of oak trees plays a key role in determining the regional distribution of Tischeria ekebladella. The distribution of the moth is aggregated at the landscape level, where local leaf miner populations are less likely to be present where oaks are scarce. A modelling exercise based on empirical dispersal estimates revealed that the moth population on Wattkast an island in south-western Finland is spatially structured overall, but that the relative importance of local and regional processes on tree-specific moth dynamics varies drastically across the landscape. To conclude, my work in the oak-Tischeria ekebladella system demonstrates that the local abundance and regional distribution of a herbivore may be more strongly influenced by the spatial location of host trees than by their relative quality. Hence, it reveals the importance of considering spatial context in the study of herbivorous insects, and forms a bridge between the classical fields of plant-insect interactions and spatial ecology.

The Emerging Phenotype: Ecological Genetics of Color, Form and Sex in the Common Frog

One of the main aims of evolutionary biology is to explain why organisms vary phenotypically as they do. Proximately, this variation arises from genetic differences and from environmental influences, the latter of which is referred to as phenotypic plasticity. Phenotypic plasticity is thus a central concept in evolutionary biology, and understanding its relative importance in causing the phenotypic variation and differentiation is important, for instance in anticipating the consequences of human induced environmental changes. The aim of this thesis was to study geographic variation and local adaptation, as well as sex ratios and environmental sex reversal, in the common frog (Rana temporaria). These themes cover three different aspects of phenotypic plasticity, which emerges as the central concept for the thesis. The first two chapters address geographic variation and local adaptation in two potentially thermally adaptive traits, namely the degree of melanism and the relative leg length. The results show that although there is an increasing latitudinal trend in the degree of melanism in wild populations across Scandinavian Peninsula, this cline has no direct genetic basis and is thus environmentally induced. The second chapter demonstrates that although there is no linear, latitudinally ordered phenotypic trend in relative leg length that would be expected under Allen s rule an ecogeographical rule linking extremity length to climatic conditions there seems to be such a trend at the genetic level, hidden under environmental effects. The first two chapters thus view phenotypic plasticity through its ecological role and evolution, and demonstrate that it can both give rise to phenotypic variation and hide evolutionary patterns in studies that focus solely on phenotypes. The last three chapters relate to phenotypic plasticity through its ecological and evolutionary role in sex determination, and consequent effects on population sex ratio, genetic recombination and the evolution of sex chromosomes. The results show that while sex ratios are strongly female biased and there is evidence of environmental sex reversals, these reversals are unlikely to have caused the sex ratio skew, at least directly. The results demonstrate that environmental sex reversal can have an effect on the evolution of sex chromosomes, as the recombination patterns between them seem to be controlled by phenotypic, rather than genetic, sex. This potentially allows Y chromosomes to recombine, lending support for the recent hypothesis suggesting that sex-reversal may play an important role on the rejuvenation of Y chromosomes.

Work-related well-being of Finnish anesthesiologists

Anesthesiologists, according to some studies, are highly stressed, die at a significantly earlier age than their colleagues and the general population,and are among the leaders in physicians' suicide records. Data are,however, sparse and contradictory. The aim of this study was to discover details of the work-related well-being of Finnish anesthesiologists. In 2004, a cross-sectional postal survey including all 550 working Finnish anesthesiologists produced a total of 328 responses (60%); 53% were men. The anesthesiologists had the greatest on-call workload among Finnish physicians. Their average in-hospital on-call period lasted 24 hours (range 14 to 38). Over two-thirds felt stressed. The most important causes of stress were work and combining work with family. Their main worries at work were: excessive workload and time constraints, especially being on call, organizational problems, and fear of harming patients. On-call workload correlated with burnout. Being frequently on call was correlated with severe stress symptoms--symptoms associated with sick leaves. Women were more affected by stress than men. High job control and organizational justice seemed to mitigate hospital-on-call stress symptoms. The respondents enjoyed fairly high job and life satisfaction. Job control and organizational justice were the most important correlates of these wellness indicators. Work-related factors were more important in males, whereas family life played a larger role in the well-being of female anesthesiologists. Women had less job control, fewer permanent job contracts, and a higher domestic workload. Of the respondents, 31% were willing to consider changing to another physician's specialty and 43% to a profession other than medicine. The most important correlates for these job turnover attitudes were conflicts at the workplace, low job control, organizational injustice, stress, and job dissatisfaction. One in four had at some time considered suicide. Respondents with poor health, low social support, and family problems were at the highest risk for suicidality. The highest risks at work were conflicts with co-workers and superiors, on-call-related stress symptoms, and low organizational justice. If a respondent had several risk factors, the risk for suicidality doubled with each additional factor. On-call work-burden, job control, fairness of decision-making procedures,and workplace relationships should be the focus in attempts to increase the work-related well-being of anesthesiologists.

Local numerical modelling of magnetoconvection and turbulence - implications for mean-field theories

During the last decades mean-field models, in which large-scale magnetic fields and differential rotation arise due to the interaction of rotation and small-scale turbulence, have been enormously successful in reproducing many of the observed features of the Sun. In the meantime, new observational techniques, most prominently helioseismology, have yielded invaluable information about the interior of the Sun. This new information, however, imposes strict conditions on mean-field models. Moreover, most of the present mean-field models depend on knowledge of the small-scale turbulent effects that give rise to the large-scale phenomena. In many mean-field models these effects are prescribed in ad hoc fashion due to the lack of this knowledge. With large enough computers it would be possible to solve the MHD equations numerically under stellar conditions. However, the problem is too large by several orders of magnitude for the present day and any foreseeable computers. In our view, a combination of mean-field modelling and local 3D calculations is a more fruitful approach. The large-scale structures are well described by global mean-field models, provided that the small-scale turbulent effects are adequately parameterized. The latter can be achieved by performing local calculations which allow a much higher spatial resolution than what can be achieved in direct global calculations. In the present dissertation three aspects of mean-field theories and models of stars are studied. Firstly, the basic assumptions of different mean-field theories are tested with calculations of isotropic turbulence and hydrodynamic, as well as magnetohydrodynamic, convection. Secondly, even if the mean-field theory is unable to give the required transport coefficients from first principles, it is in some cases possible to compute these coefficients from 3D numerical models in a parameter range that can be considered to describe the main physical effects in an adequately realistic manner. In the present study, the Reynolds stresses and turbulent heat transport, responsible for the generation of differential rotation, were determined along the mixing length relations describing convection in stellar structure models. Furthermore, the alpha-effect and magnetic pumping due to turbulent convection in the rapid rotation regime were studied. The third area of the present study is to apply the local results in mean-field models, which task we start to undertake by applying the results concerning the alpha-effect and turbulent pumping in mean-field models describing the solar dynamo.