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.

Short- and long-term consequences of food resources on Ural owl Strix uralensis reproduction

Life-history theory states that although natural selection would favour a maximisation of both reproductive output and life-span, such a combination can not be achieved in any living organism. According to life-history theory the reason for the fact that not all traits can be maximised simultaneously is that different traits compete with each other for resources. These relationships between traits that constrain the simultaneous evolution of two or more traits are called trade-offs. Therefore, during different life-stages an individual needs to optimise its allocation of resources to life-history components such as growth, reproduction and survival. Resource limitation acts on these traits and therefore investment in one trait, e.g. reproduction, reduces the resources available for investment in another trait, e.g. residual reproduction or survival. In this thesis I study how food resources during different stages of the breeding event affect reproductive decisions in the Ural owl (Strix uralensis) and the consequences of these decisions on parents and offspring. The Ural owl is a suitable study species for such studies in natural populations since they are long-lived, site-tenacious, and feed on voles. The vole populations in Fennoscandia fluctuate in three- to four-year cycles, which create a variable food environment for the Ural owls to cope with. The thesis gives new insight in reproductive costs and their consequences in natural animal populations with emphasis on underlying physiological mechanisms. I found that supplementary fed Ural owl parents invest supplemented food resources during breeding in own self-maintenance instead of allocating those resources to offspring growth. This investment in own maintenance instead of improving current reproduction had carry-over effects to the following year in terms of increased reproductive output. Therefore, I found evidence that reduced reproductive costs improves future reproductive performance. Furthermore, I found evidence for the underlying mechanism behind this carry-over effect of supplementary food on fecundity. The supplementary-fed parents reduced their feeding investment in the offspring compared to controls, which enabled the fed female parents to invest the surplus resources in parasite resistance. Fed female parents had lower blood parasite loads than control females and this effect lasted until the following year when also reproductive output was increased. Hence, increased investment in parasite resistance when resources are plentiful has the potential to mediate positive carry-over effects on future reproduction. I further found that this carry-over effect was only present when potentials for future reproduction were good. The thesis also provides new knowledge on resource limitation on maternal effects. I found that increased resources prior to egg laying improve the condition and health of Ural owl females and enable them to allocate more resources to reproduction than control females. These additional resources are not allocated to increase the number of offspring, but instead to improve the quality of each offspring. Fed Ural owl females increased the size of their eggs and allocated more health improving immunological components into the eggs. Furthermore, the increased egg size had long-lasting effects on offspring growth, as offspring from larger eggs were heavier at fledging. Limiting resources can have different short- and long-term consequences on reproductive decisions that affect both offspring number and quality. In long-lived organisms, such as the Ural owl, it appears to be beneficial in terms of fitness to invest in long breeding life-span instead of additional investment in current reproduction. In Ural owls, females can influence the phenotypic quality of the offspring by transferring additional resources to the eggs that can have long-lasting effects on growth.

Molecular Tuning of Rhodopsins for High Visual Sensitivity in Different Light Environments : Variation in Absorbance Spectrum and Opsin Sequence within and between Species

Visual pigments of different animal species must have evolved at some stage to match the prevailing light environments, since all visual functions depend on their ability to absorb available photons and transduce the event into a reliable neural signal. There is a large literature on correlation between the light environment and spectral sensitivity between different fish species. However, little work has been done on evolutionary adaptation between separated populations within species. More generally, little is known about the rate of evolutionary adaptation to changing spectral environments. The objective of this thesis is to illuminate the constraints under which the evolutionary tuning of visual pigments works as evident in: scope, tempo, available molecular routes, and signal/noise trade-offs. Aquatic environments offer Nature s own laboratories for research on visual pigment properties, as naturally occurring light environments offer an enormous range of variation in both spectral composition and intensity. The present thesis focuses on the visual pigments that serve dim-light vision in two groups of model species, teleost fishes and mysid crustaceans. The geographical emphasis is in the brackish Baltic Sea area with its well-known postglacial isolation history and its aquatic fauna of both marine and fresh-water origin. The absorbance spectrum of the (single) dim-light visual pigment were recorded by microspectrophotometry (MSP) in single rods of 26 fish species and single rhabdoms of 8 opossum shrimp populations of the genus Mysis inhabiting marine, brackish or freshwater environments. Additionally, spectral sensitivity was determined from six Mysis populations by electroretinogram (ERG) recording. The rod opsin gene was sequenced in individuals of four allopatric populations of the sand goby (Pomatoschistus minutus). Rod opsins of two other goby species were investigated as outgroups for comparison. Rod absorbance spectra of the Baltic subspecies or populations of the primarily marine species herring (Clupea harengus membras), sand goby (P. minutus), and flounder (Platichthys flesus) were long-wavelength-shifted compared to their marine populations. The spectral shifts are consistent with adaptation for improved quantum catch (QC) as well as improved signal-to-noise ratio (SNR) of vision in the Baltic light environment. Since the chromophore of the pigment was pure A1 in all cases, this has apparently been achieved by evolutionary tuning of the opsin visual pigment. By contrast, no opsin-based differences were evident between lake and sea populations of species of fresh-water origin, which can tune their pigment by varying chromophore ratios. A more detailed analysis of differences in absorbance spectra and opsin sequence between and within populations was conducted using the sand goby as model species. Four allopatric populations from the Baltic Sea (B), Swedish west coast (S), English Channel (E), and Adriatic Sea (A) were examined. Rod absorbance spectra, characterized by the wavelength of maximum absorbance (λmax), differed between populations and correlated with differences in the spectral light transmission of the respective water bodies. The greatest λmax shift as well as the greatest opsin sequence difference was between the Baltic and the Adriatic populations. The significant within-population variation of the Baltic λmax values (506-511 nm) was analyzed on the level of individuals and was shown to correlate well with opsin sequence substitutions. The sequences of individuals with λmax at shorter wavelengths were identical to that of the Swedish population, whereas those with λmax at longer wavelengths additionally had substitution F261F/Y in the sixth transmembrane helix of the protein. This substitution (Y261) was also present in the Baltic common gobies and is known to redshift spectra. The tuning mechanism of the long-wavelength type Baltic sand gobies is assumed to be the co-expression of F261 and Y261 in all rods to produce ≈ 5 nm redshift. The polymorphism of the Baltic sand goby population possibly indicates ambiguous selection pressures in the Baltic Sea. The visual pigments of all lake populations of the opossum shrimp (Mysis relicta) were red-shifted by 25 nm compared with all Baltic Sea populations. This is calculated to confer a significant advantage in both QC and SNR in many humus-rich lakes with reddish water. Since only A2 chromophore was present, the differences obviously reflect evolutionary tuning of the visual protein, the opsin. The changes have occurred within the ca. 9000 years that the lakes have been isolated from the Sea after the most recent glaciation. At present, it seems that the mechanism explaining the spectral differences between lake and sea populations is not an amino acid substitution at any other conventional tuning site, but the mechanism is yet to be found.

Si, CdTe and CdZnTe radiation detectors for imaging applications

The structure and operation of CdTe, CdZnTe and Si pixel detectors based on crystalline semiconductors, bump bonding and CMOS technology and developed mainly at Oy Simage Ltd. And Oy Ajat Ltd., Finland for X- and gamma ray imaging are presented. This detector technology evolved from the development of Si strip detectors at the Finnish Research Institute for High Energy Physics (SEFT) which later merged with other physics research units to form the Helsinki Institute of Physics (HIP). General issues of X-ray imaging such as the benefits of the method of direct conversion of X-rays to signal charge in comparison to the indirect method and the pros and cons of photon counting vs. charge integration are discussed. A novel design of Si and CdTe pixel detectors and the analysis of their imaging performance in terms of SNR, MTF, DQE and dynamic range are presented in detail. The analysis shows that directly converting crystalline semiconductor pixel detectors operated in the charge integration mode can be used in X-ray imaging very close to the theoretical performance limits in terms of efficiency and resolution. Examples of the application of the developed imaging technology to dental intra oral and panoramic and to real time X-ray imaging are given. A CdTe photon counting gamma imager is introduced. A physical model to calculate the photo peak efficiency of photon counting CdTe pixel detectors is developed and described in detail. Simulation results indicates that the charge sharing phenomenon due to diffusion of signal charge carriers limits the pixel size of photon counting detectors to about 250 μm. Radiation hardness issues related to gamma and X-ray imaging detectors are discussed.

Optical Tweezers for Single Molecule Biology

Molecular machinery on the micro-scale, believed to be the fundamental building blocks of life, involve forces of 1-100 pN and movements of nanometers to micrometers. Micromechanical single-molecule experiments seek to understand the physics of nucleic acids, molecular motors, and other biological systems through direct measurement of forces and displacements. Optical tweezers are a popular choice among several complementary techniques for sensitive force-spectroscopy in the field of single molecule biology. The main objective of this thesis was to design and construct an optical tweezers instrument capable of investigating the physics of molecular motors and mechanisms of protein/nucleic-acid interactions on the single-molecule level. A double-trap optical tweezers instrument incorporating acousto-optic trap-steering, two independent detection channels, and a real-time digital controller was built. A numerical simulation and a theoretical study was performed to assess the signal-to-noise ratio in a constant-force molecular motor stepping experiment. Real-time feedback control of optical tweezers was explored in three studies. Position-clamping was implemented and compared to theoretical models using both proportional and predictive control. A force-clamp was implemented and tested with a DNA-tether in presence of the enzyme lambda exonuclease. The results of the study indicate that the presented models describing signal-to-noise ratio in constant-force experiments and feedback control experiments in optical tweezers agree well with experimental data. The effective trap stiffness can be increased by an order of magnitude using the presented position-clamping method. The force-clamp can be used for constant-force experiments, and the results from a proof-of-principle experiment, in which the enzyme lambda exonuclease converts double-stranded DNA to single-stranded DNA, agree with previous research. The main objective of the thesis was thus achieved. The developed instrument and presented results on feedback control serve as a stepping stone for future contributions to the growing field of single molecule biology.

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.