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.

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.

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.

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.

Seismic Tomography and Earthquake Mechanism Beneath the Central Fennoscandian Shield

The aim of this thesis was to study the seismic tomography structure of the earth s crust together with earthquake distribution and mechanism beneath the central Fennoscandian Shield, mainly in southern and central Finland. The earthquake foci and some fault plane solutions are correlated with 3-D images of the velocity tomography. The results are discussed in relation to the stress field of the Shield and with other geophysical, e.g. geomagnetic, gravimetric, tectonic, and anisotropy studies of the Shield. The earthquake data of the Fennoscandian Shield has been extracted from the Nordic earthquake parameter data base which was founded at the time of inception of the earthquake catalogue for northern Europe. Eight earlier earthquake source mechanisms are included in a pilot study on creating a novel technique for calculating an earthquake fault plane solution. Altogether, eleven source mechanisms of shallow, weak earthquakes are related in the 3-D tomography model to trace stresses of the crust in southern and central Finland. The earthquakes in the eastern part of the Fennoscandian Shield represent low-active, intraplate seismicity. Earthquake mechanisms with NW-SE oriented horizontal compression confirm that the dominant stress field originates from the ridge-push force in the North Atlantic Ocean. Earthquakes accumulate in coastal areas, in intersections of tectonic lineaments, in main fault zones or are bordered by fault lines. The majority of Fennoscandian earthquakes concentrate on the south-western Shield in southern Norway and Sweden. Onwards, epicentres spread via the ridge of the Shield along the west-coast of the Gulf of Bothnia northwards along the Tornio River - Finnmark fault system to the Barents Sea, and branch out north-eastwards via the Kuusamo region to the White Sea Kola Peninsula faults. The local seismic tomographic method was applied to find the terrane distribution within the central parts of the Shield the Svecofennian Orogen. From 300 local explosions a total of 19765 crustal Pg- and Sg-wave arrival times were inverted to create independent 3-D Vp and Vs tomographic models, from which the Vp/Vs ratio was calculated. The 3-D structure of the crust is presented as a P-wave and for the first time as an S-wave velocity model, and also as a Vp/Vs-ratio model of the SVEKALAPKO area that covers 700x800 km2 in southern and central Finland. Also, some P-wave Moho-reflection data was interpolated to image the relief of the crust-mantle boundary (i.e. Moho). In the tomography model, the seismic velocities vary smoothly. The lateral variations are larger for Vp (dVp =0.7 km/s) than for Vs (dVs =0.4 km/s). The Vp/Vs ratio varies spatially more distinctly than P- and S-wave velocities, usually from 1.70 to 1.74 in the upper crust and from 1.72 to 1.78 in the lower crust. Schist belts and their continuations at depth are associated with lower velocities and lower Vp/Vs ratios than in the granitoid areas. The tomography modelling suggests that the Svecofennian Orogen was accreted from crustal blocks ranging in size from 100x100 km2 to 200x200 km2 in cross-sectional area. The intervening sedimentary belts have ca. 0.2 km/s lower P- and S-wave velocities and ca. 0.04 lower Vp/Vs ratios. Thus, the tomographic model supports the concept that the thick Svecofennian crust was accreted from several crustal terranes, some hidden, and that the crust was later modified by intra- and underplating. In conclusion, as a novel approach the earthquake focal mechanism and focal depth distribution is discussed in relation to the 3-D tomography model. The schist belts and the transformation zones between the high- and low-velocity anomaly blocks are characterized by deeper earthquakes than the granitoid areas where shallow events dominate. Although only a few focal mechanisms were solved for southern Finland, there is a trend towards strike-slip and oblique strike-slip movements inside schist areas. The normal dip-slip type earthquakes are typical in the seismically active Kuusamo district in the NE edge of the SVEKALAPKO area, where the Archean crust is ca. 15-20 km thinner than the Proterozoic Svecofennian crust. Two near vertical dip-slip mechanism earthquakes occurred in the NE-SW junction between the Central Finland Granitoid Complex and the Vyborg rapakivi batholith, where high Vp/Vs-ratio deep-set intrusion splits the southern Finland schist belt into two parts in the tomography model.

Musculoskeletal disorders and psychosocial factors at work : Effects of a participatory ergonomics intervention in a cluster randomized controlled trial

This study examined the efficacy of a participatory ergonomics intervention in preventing musculoskeletal disorders (MSDs) and changing unsatisfactory psychosocial working conditions among municipal kitchen workers. The occurrence of multiple-site musculoskeletal pain (MSP) and associations between MSP and psychosocial factors at work over time were studied secondarily. A cluster randomized controlled trial was conducted during 2002-2005 in 119 municipal kitchens with 504 workers. The kitchens were randomized to an intervention (n = 59) and control (n = 60) group. The intervention lasted 11 to 14 months. The workers identified strenuous work tasks and sought solutions for decreasing physical and mental workload. The main outcomes were the occurrence of and trouble caused by musculoskeletal pain in seven anatomical sites, local musculoskeletal fatigue after work, and musculoskeletal sick leaves. Psychosocial factors at work (job control, skill discretion, co-worker relationships, supervisor support, mental strenuousness of work, hurry, job satisfaction) and mental stress were studied as intermediate outcomes of the intervention. Questionnaire data were collected at three months intervals during the intervention and the one-year post-intervention follow-up. Response rates varied between 92 % and 99 %. In total, 402 ergonomic changes were implemented. In the control group, 80 changes were spontaneously implemented within normal activity. The intervention did not reduce perceived physical workload and no systematic differences in any health outcomes were found between the intervention and control groups during the intervention or during the one-year follow-up. The results suggest that the intervention as studied in the present trial was not more effective in reducing perceived physical workload or preventing MSDs compared with no such intervention. Little previous evidence of the effectiveness of ergonomics interventions in preventing MSDs exists. The effects on psychosocial factors at work were adverse, especially in the two of the participating cities where re-organization of foodservices timed simultaneously with the intervention. If organizational reforms at workplace are expected to occur, the execution of other workplace interventions at the same time should be avoided. The co-occurrence of musculoskeletal pain at several sites is observed to be more common than pain at single anatomical sites. However, the risk factors of MSP are largely unknown. This study showed that at baseline, 73 % of the women reported pain in at least two, 36 % in four or more, and 10 % in six to seven sites. The seven pain symptoms occurred in over 80 different combinations. When co-occurrence of pain was studied in three larger anatomical areas (neck/low back, upper limbs, lower limbs), concurrent pain in all three areas was the most common combination (36 %). The 3-month prevalence of MSP (≥ 3 of seven sites) varied between 50 % and 61 % during the two-year follow-up period. Psychosocial factors at work and mental stress were strong predictors for MSP over time and, vice versa, MSP predicted psychosocial factors at work and mental stress. The reciprocality of the relationships implies either two mutually dependent processes in time, or some shared common underlying factor(s).

Domestic labour relations in India : Vulnerability and gendered life courses in Jaipur

This study explores labour relations between domestic workers and employers in India. It is based on interviews with both employers and workers, and ethnographically oriented field work in Jaipur, carried out in 2004-2007. Combining development studies with gender studies, labour studies, and childhood studies, it asks how labour relations between domestic workers and employers are formed in Jaipur, and how female domestic workers trajectories are created. Focusing on female part-time maids and live-in work arrangements, the study analyses children s work in the context of overall work force, not in isolation from it. Drawing on feminist Marxism, domestic labour relations are seen as an arena of struggle. The study takes an empirical approach, showing class through empiria and shows how paid domestic work is structured and stratified through intersecting hierarchies of class, caste, gender, age, ethnicity and religion. The importance of class in domestic labour relations is reiterated, but that of caste, so often downplayed by employers, is also emphasized. Domestic workers are crucial to the functioning of middle and upper middle class households, but their function is not just utilitarian. Through them working women and housewives are able to maintain purity and reproduce class disctinctions, both between poor and middle classes and lower and upper middle classes. Despite commodification of work relations, traditional elements of service relationships have been retained, particularly through maternalist practices such as gift giving, creating a peculiar blend of traditional and market practices. Whilst employers of part-time workers purchase services in a segmented market from a range of workers for specific, traditional live-in workers are also hired to serve employers round the clock. Employers and workers grudgingly acknowledged their dependence on one another, employers seeking various strategies to manage fear of servant crime, such as the hiring of children or not employing live-in workers in dual-earning households. Paid domestic work carries a heavy stigma and provide no entry to other jobs. It is transmitted from mothers to daughters and working girls were often the main income providers in their families. The diversity of working conditions is analysed through a continuum of vulnerability, generic live-in workers, particularly children and unmarried young women with no close family in Jaipur, being the most vulnerable and experienced part-time workers the least vulnerable. Whilst terms of employment are negotiated informally and individually, some informal standards regarding salary and days off existed for maids. However, employers maintain that workings conditions are a matter of individual, moral choice. Their reluctance to view their role as that of employers and the workers as their employees is one of the main stumbling blocks in the way of improved working conditions. Key words: paid domestic work, India, children s work, class, caste, gender, life course