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.

Marking one-summer old whitefish with fluorescent pigment spraying method and results of whitefish stockings in the Gulf of Bothnia

Anadromous whitefish is one of the most important fish species in the Finnish coastal fisheries in the Gulf fo Bothnia. To compensate the lost reproduction due to river damming and to support the fisheries, several million one-summer old whitefish are released yearly into the Gulf of Bothnia. Since there are naturally reproducing whitefish in the Gulf as well, and the wild and stocked fish can not be separated in the catch, stocking impact can only be estimated by marking the stocked fish. Due to the small size and large number of released whitefish, the scattered fishery and large area where the whitefish migrate, most of the traditionally used fish marking methods were either unsuitable (e.g. Carlin-tags) or proved to be too expensive (e.g. coded wire tags). Fluorescent pigment spraying method offers a fast and cost-effective method to mass-mark young fish. However, the results are not always satisfactory due to low long-time retention of the marks in some species. The method has to be tested and proper marking conditions and methods determined for each species. This thesis is based on work that was accomplished while developing the fluorescent pigment spraying method for marking one-summer old whitefish fingerlings, and it draws together the results of mass-marking whitefish fingerlings that were released in the Gulf of Bothnia. Fluorescent pigment spraying method is suitable for one-summer old whitefish larger than 8 cm total length. The water temperature during the marking should not exceed 10o C. Suitable spraying pressure is 6 bars measured in the compressor outlet, and the distance of the spraying gun nozzle should be ca 20 cm from the fish. Under such conditions, the marking results in long-term retention of the mark with low or no mortality. The stress level of the fish (measured as muscle water content) rises during the marking procedure, but if the fish are allowed to recover after marking, the overall stress level remains within the limits observed in normal fish handling during the capture-loading-transport-stocking procedure. The marked whitefish fingerlings are released into the sea at larger size and later in the season than the wild whitefish. However, the stocked individuals migrate to the southern feeding grounds in a similar pattern to the wild ones. The catch produced by whitefish stocking in the Gulf of Bothnia varied between released fingerling groups, but was within the limits reported elsewhere in Finland. The releases in the southern Bothnian Bay resulted in a larger catch than those made in the northern Bothnian Bay. The size of the released fingerlings seemed to have some effect on survival of the fish during the first winter in the sea. However, when the different marking groups were compared, the mean fingerling size was not related to stocking success.

USING FLUORESCENT AND NON-FLUORESCENT STEROLS TO STUDY RAFTS AND INTRACELLULAR CHOLESTEROL TRANSPORT IN MAMMALIAN CELLS

Cholesterol is an essential component in the membranes of most eukaryotic cells, in which it mediates many functions including membrane fluidity, permeability and the formation of ordered membrane domains. In this work a fluorescent and a non-fluorescent cholesterol analog were characterized as tools to study cholesterol. Next, these analogs were used to study two specific cell biological processes that involve cholesterol, i.e. the structure and function of ordered membrane domains/rafts and intracellular cholesterol transport. The most common method for studying ordered membrane domains is by disrupting them by cholesterol depletion. Because cholesterol depletion affects many cellular functions besides those mediated by membrane domains, this procedure is highly unspecific. The cellular exchange of cholesterol by desmosterol as a tool to study ordered membrane domains was characterized. It turned out that the ability of desmosterol to form and stabilize membrane domains in vitro was weaker compared to cholesterol. This result was reinforced by atomistic scale simulations that indicated that desmosterol has a lower ordering effect on phospholipid acyl chains. Three procedures were established for exchanging cellular cholesterol by desmosterol. In cells in which desmosterol was the main sterol, insulin signaling was attenuated. The results suggest that this was caused by desmosterol destabilizing membrane rafts. Contrary to its effect on ordered membrane domains it was found that replacing cholesterol by desmosterol does not change cell growth/viability, subcellular sterol distribution, Golgi integrity, secretory pathway, phospholipid composition and membrane fluidity. Together these results suggest that exchanging cellular cholesterol by desmosterol provides a selective tool for perturbing rafts. Next, the importance of cholesterol for the structure and function of caveolae was analyzed by exchanging the cellular cholesterol by desmosterol. The sterol exchange reduced the stability of caveolae as determined by detergent resistance of caveolin-1 and heat resistance of caveolin-1 oligomers. Also the sterol exchange led to aberrations in the caveolar structure; the morphology of caveolae was altered and there was a larger variation in the amount of caveolin-1 molecules per caveola. These results demonstrate that cholesterol is important for caveolar stability and structural homogeneity. In the second part of this work a fluorescent cholesterol analog was characterized as a tool to study cholesterol transport. Tight control of the intracellular cholesterol distribution is essential for many cellular processes. An important mechanism by which cells regulate their membrane cholesterol content is by cholesterol traffic, mostly from the plasma membrane to lipid droplets. The fluorescent sterol probe BODIPY-cholesterol was characterized as a tool to analyze cholesterol transport between the plasma membrane, the endoplasmic reticulum (ER) and lipid droplets. The behavior of BODIPY-cholesterol was compared to that of natural sterols, using both biochemical and live-cell microcopy assays. The results show that the transport kinetics of BODIPY-cholesterol between the plasma membrane, the ER and lipid droplets is similar to that of unesterified cholesterol. Next, BODIPY-cholesterol was utilized to analyze the importance of oxysterol binding protein related proteins (ORPs) for cholesterol transport between the plasma membrane, the ER, and lipid droplets in mammalian cells. By overexpressing all human ORPs it turned out that especially ORP1S and ORP2 enhanced sterol transport from the plasma membrane to lipid droplets. Our results suggest that the increased sterol transport takes place between the plasma membrane and ER and not between the ER and lipid droplets. Simultaneous knockdown of ORP1S and ORP2 resulted in a moderate but significant inhibition of sterol traffic from the plasma membrane to ER and lipid droplets, suggesting a physiological role for these ORPs in this process. The two phenylalanines in an acidic tract (FFAT) motif in ORPs, which mediates interaction with vesicle associated membrane protein associated proteins (VAPs) in the ER, was not necessary for mediating sterol transport. However, VAP silencing slowed down sterol transport, most likely by destabilizing ORPs containing a FFAT motif.

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.