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.

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.

Comparing type counts

This work is a case study of applying nonparametric statistical methods to corpus data. We show how to use ideas from permutation testing to answer linguistic questions related to morphological productivity and type richness. In particular, we study the use of the suffixes -ity and -ness in the 17th-century part of the Corpus of Early English Correspondence within the framework of historical sociolinguistics. Our hypothesis is that the productivity of -ity, as measured by type counts, is significantly low in letters written by women. To test such hypotheses, and to facilitate exploratory data analysis, we take the approach of computing accumulation curves for types and hapax legomena. We have developed an open source computer program which uses Monte Carlo sampling to compute the upper and lower bounds of these curves for one or more levels of statistical significance. By comparing the type accumulation from women’s letters with the bounds, we are able to confirm our hypothesis.

Functional genes and gene array analysis as tools for monitoring hydrocarbon biodegradation

Bioremediation, which is the exploitation of the intrinsic ability of environmental microbes to degrade and remove harmful compounds from nature, is considered to be an environmentally sustainable and cost-effective means for environmental clean-up. However, a comprehensive understanding of the biodegradation potential of microbial communities and their response to decontamination measures is required for the effective management of bioremediation processes. In this thesis, the potential to use hydrocarbon-degradative genes as indicators of aerobic hydrocarbon biodegradation was investigated. Small-scale functional gene macro- and microarrays targeting aliphatic, monoaromatic and low molecular weight polyaromatic hydrocarbon biodegradation were developed in order to simultaneously monitor the biodegradation of mixtures of hydrocarbons. The validity of the array analysis in monitoring hydrocarbon biodegradation was evaluated in microcosm studies and field-scale bioremediation processes by comparing the hybridization signal intensities to hydrocarbon mineralization, real-time polymerase chain reaction (PCR), dot blot hybridization and both chemical and microbiological monitoring data. The results obtained by real-time PCR, dot blot hybridization and gene array analysis were in good agreement with hydrocarbon biodegradation in laboratory-scale microcosms. Mineralization of several hydrocarbons could be monitored simultaneously using gene array analysis. In the field-scale bioremediation processes, the detection and enumeration of hydrocarbon-degradative genes provided important additional information for process optimization and design. In creosote-contaminated groundwater, gene array analysis demonstrated that the aerobic biodegradation potential that was present at the site, but restrained under the oxygen-limited conditions, could be successfully stimulated with aeration and nutrient infiltration. During ex situ bioremediation of diesel oil- and lubrication oil-contaminated soil, the functional gene array analysis revealed inefficient hydrocarbon biodegradation, caused by poor aeration during composting. The functional gene array specifically detected upper and lower biodegradation pathways required for complete mineralization of hydrocarbons. Bacteria representing 1 % of the microbial community could be detected without prior PCR amplification. Molecular biological monitoring methods based on functional genes provide powerful tools for the development of more efficient remediation processes. The parallel detection of several functional genes using functional gene array analysis is an especially promising tool for monitoring the biodegradation of mixtures of hydrocarbons.

Cervical headgear in Class II division 1 correction in children : Academic Dissertation

Class II division 1 malocclusion occurs in 3.5 to 13 percent of 7 12 year-old children. It is the most common reason for orthodontic treatment in Finland. Correction is most commonly performed using headgear treatment. The aim of this study was to investigate the effects of cervical headgear treatment on dentition, facial skeletal and soft tissue growth, and upper airway structure, in children. 65 schoolchildren, 36 boys and 29 girls were studied. At the onset of treatment a mean age was 9.3 (range 6.6 12.4) years. All the children were consequently referred to an orthodontist because of Class II division 1 malocclusion. The included children had protrusive maxilla and an overjet of more than 2mm (3 to 11 mm). The children were treated with a Kloehn-type cervical headgear as the only appliance until Class I first molar relationships were achieved. The essential features of the headgear were cervical strong pulling forces, a long upward bent outer bow, and an expanded inner bow. Dental casts and lateral and posteroanterior cephalograms were taken before and after the treatment. The results were compared to a historical, cross-sectional Finnish cohort or to historical, age- and sex-matched normal Class I controls. The Class I first molar relationships were achieved in all the treated children. The mean treatment time was 1.7 (range 0.3-3.1) years. Phase 2 treatments were needed in 52% of the children, most often because of excess overjet or overbite. The treatment decreased maxillary protrusion by inhibiting alveolar forward growth, while the rest of the maxilla and mandible followed normal growth. The palate rotated anteriorly downward. The expansion of the inner bow of the headgear induced widening of the maxilla, nasal cavity, and the upper and lower dental arches. Class II malocclusion was associated with narrower oro- and hypopharyngeal space than in the Class I normal controls. The treatment increased the retropalatal airway space, while the rest of the airway remained unaffected. The facial profile improved esthetically, while the facial convexity decreased. Facial soft tissues masked the facial skeletal convexity, and the soft tissue changes were smaller than skeletal changes. In conclusion, the headgear treatment with the expanded inner bow may be used as an easy and simple method for Class II correction in growing children.

2,1,3-Bentsoksadiatsolirakenteiset molekyylit antibakteerisina ja antiparasiittisina yhdisteinä

Aikaisemman tutkimuksen perusteella tiedettiin tiettyjen 2,1,3-bentsoksadiatsolirakenteisten molekyylien olevan aktiivisia Chlamydia pneumoniae –bakteeria vastaan. Tutkimusta lähdettiin jatkamaan ja 2,1,3-bentsoksadiatsolimolekyylien rakenne-aktiivisuusuhteista haluttiin saada lisätietoa. Tarkoituksena oli kehittää 2,1,3-bentsoksadiatsolimolekyyleille ja sen avulla muodostaa molekyylikirjasto. Syntetisoidut molekyylit haluttiin testata sekä Chlamydia pneumoniae -bakteeria että Leishmania donovani –parasiittia vastaan. Chlamydia pneumoniae –bakteeri aiheuttaa akuutteja ylä- ja alahengitystieinfektiota, kuten keuhkoputkentulehdusta. Akuutissa tulehduksessa oireet vaihtelevat huomattavasti. Chlamydia pneumoniae –bakteerilla on myös taipumus aiheuttaa kroonisia tulehduksia. Nämä ovat useissa tutkimuksissa yhdistetty kansantaloudellisesti merkittäviin sairauksiin, kuten ateroskleroosiin ja astmaan. Leishmanioosi on toiseksi yleisin loissairaus ihmisellä malarian jälkeen. Leishmania donovani –parasiitti voi aiheuttaa tappavaa viskeraalista leishmanioosia. Vuodessa leishmanioosiin kuolee yli 50 000 ihmistä. Viime vuosina leishmanioosin lääkehoidossa on esiintynyt monenlaisia ongelmia. Osat lääkkeistä ovat menettäneet tehonsa ja osalla esiintyy vakavia haittavaikutuksia. 2,1,3-Bentsoksadiatsolirakenteisille yhdisteille saatiin kehitettyä toimiva synteesireitti. Lähtöaineena käytettiin 4-amino-2-nitrobentsoehappoa, josta saatiin hapettavalla renkaansulkeutumisreaktiolla 2,1,3-bentsoksadiatsoli-5-karboksyylihappoa. Karboksyylihaposta syntetisoitiin amidi-välituotteen kautta 2,1,3-bentsoksadiatsoli-5-karbonitriiliä. Hydroksyyliamiini hydrokloridin avulla 2,1,3-bentsoksadiatsoli-5-karbonitriilistä muodostettiin vastaavaa karboksimidamidia, joka oli synteesireitin yhteinen välituote kaikille molekyyleille. Viimeisessä vaiheessa N´-hydroksidi-2,1,3-bentsoksadiatsoli-5-karboksimidamidin annettiin reagoida joko fenyyli-isosyanaatin tai fenyyli-isotiosyanaatin kanssa, jolloin saatiin lopputuotetta. Synteesireitin kehittäminen osoittautui haastavaksi ja loppujen lopuksi saatiin ainoastaan kolme lopputuotetta syntetisoitua. Yksi lopputuotteista testattiin C. pneumoniae –bakteeria vastaan Åbo akademissa Turussa. Testattavaa yhdiste ei sisältänyt 2,1,3-bentsoksadiatsoliarengasta ja bioaktiivisuuskokeen tulos oli odotusten mukainen. Yhdiste ei ollut aktiivinen C. pneumoniae –bakteeria vastaan alhaisilla konsentraatioilla ja tuloksesta voitiin todeta 2,1,3-bentsoksadiatsolirengaan olevan tärkeä aktiivisuuden kannalta. Kaksi lopputuotetta saatiin testaukseen Leishamania donovani –parasiittia vastaan Israeliin. Ainoastaan toinen molekyyleistä sisälsi 2,1,3-bentsoksadiatsolirakenteen. Bioaktiivisuuskokeiden tulokset olivat erittäin rohkaisevia. Yhdisteet olivat aktiivisia parasiittia vastaan jo alhaisilla konsentraatioilla. Kuitenkin 2,1,3-bentsoksadiatsolirakenteinen molekyyli oli aktiivisempi, joten tämäkin aktiivisuuskokeen perusteella huomattiin rengasrakenteen olevan tärkeä aktiivisuuden kannalta.

Immunodeficiencies, pathogens and sex in upper respiratory diseases

In the first part of this thesis the association of different forms of sinonasal diseases and plasma concentrations of C3, C4, immunoglobulins, immunoglobulin G subclasses, C4A and C4B gene numbers were studied in 287 adult patients and 150 sex-matched adult controls. Patients were well characterized and stratified into groups using strict clinical criteria and females and males were also studied as separate groups. Severe primary antibody antibody deficiencies were rare in patients coming to sinonasal operations. Female patients had more recurrent sinusitis and other mucosal infections and males had more nasal polyposis. Upregulation of complement activity was seen in acute rhinosinusitis patients (high levels of plasma C3, C4, and complement classical pathway activity CH50) and male patients coming to sinonasal operations (high levels of plasma C3 and C4). In females, total and partial C4B deficiencies and lower levels of IgG1 and IgG3 were associated with rhinosinusitis leading to sinonasal operations. C4A deficiencies were found to predispose to severe chronic rhinosinusitis in females and males. In female patients with chronic or recurrent rhinosinusitis with nasal polyposis C4B deficiencies seem to predispose to the disease, but in males with a similar disease C4B deficiencies seem to be protective. This suggests a different pathophysiology between sexes in this form of sinonasal disease. In the second part of this thesis work 213 children coming to elective tonsillectomy were studied and compared with 155 randomly selected school children. An association with recurrent upper respiratory tract infections and hypersensitivity disorders was seen especially in children under 7 years of age. However, this association was not seen in levels of specific IgE to respiratory allergens in the same age group. Both symptomatic respiratory allergy and specific IgE to respiratory allergens became more common in boys than girls over 7 years of age. We were able to show that although both rhinoviruses and bacterial pathogens were found in the tonsils, no association between their presence and clinical forms of tonsillar disease was seen. The ability of GAS to bind complement regulators FH and C4BP did not differ between strains causing tonsillar diseases or septicemia, suggesting that other virulence mechanisms of the bacteria are more important.