Local systems, global impacts : Using life cycle assessment to analyse the potential and constraints of industrial symbioses

Human activities extract and displace different substances and materials from the earth s crust, thus causing various environmental problems, such as climate change, acidification and eutrophication. As problems have become more complicated, more holistic measures that consider the origins and sources of pollutants have been called for. Industrial ecology is a field of science that forms a comprehensive framework for studying the interactions between the modern technological society and the environment. Industrial ecology considers humans and their technologies to be part of the natural environment, not separate from it. Industrial operations form natural systems that must also function as such within the constraints set by the biosphere. Industrial symbiosis (IS) is a central concept of industrial ecology. Industrial symbiosis studies look at the physical flows of materials and energy in local industrial systems. In an ideal IS, waste material and energy are exchanged by the actors of the system, thereby reducing the consumption of virgin material and energy inputs and the generation of waste and emissions. Companies are seen as part of the chains of suppliers and consumers that resemble those of natural ecosystems. The aim of this study was to analyse the environmental performance of an industrial symbiosis based on pulp and paper production, taking into account life cycle impacts as well. Life Cycle Assessment (LCA) is a tool for quantitatively and systematically evaluating the environmental aspects of a product, technology or service throughout its whole life cycle. Moreover, the Natural Step Sustainability Principles formed a conceptual framework for assessing the environmental performance of the case study symbiosis (Paper I). The environmental performance of the case study symbiosis was compared to four counterfactual reference scenarios in which the actors of the symbiosis operated on their own. The research methods used were process-based life cycle assessment (LCA) (Papers II and III) and hybrid LCA, which combines both process and input-output LCA (Paper IV). The results showed that the environmental impacts caused by the extraction and processing of the materials and the energy used by the symbiosis were considerable. If only the direct emissions and resource use of the symbiosis had been considered, less than half of the total environmental impacts of the system would have been taken into account. When the results were compared with the counterfactual reference scenarios, the net environmental impacts of the symbiosis were smaller than those of the reference scenarios. The reduction in environmental impacts was mainly due to changes in the way energy was produced. However, the results are sensitive to the way the reference scenarios are defined. LCA is a useful tool for assessing the overall environmental performance of industrial symbioses. It is recommended that in addition to the direct effects, the upstream impacts should be taken into account as well when assessing the environmental performance of industrial symbioses. Industrial symbiosis should be seen as part of the process of improving the environmental performance of a system. In some cases, it may be more efficient, from an environmental point of view, to focus on supply chain management instead.  

Problems of Proto-Slavic Historical Nominal Morphology : On the Basis of Old Church Slavic

In this study I offer a diachronic solution for a number of difficult inflectional endings in Old Church Slavic nominal declensions. In this context I address the perhaps most disputed and the most important question of the Slavic nominal inflectional morphology: whether there was in Proto-Slavic an Auslautgesetz (ALG), a law of final syllables, that narrowed the Proto-Indo-European vowel */o/ to */u/ in closed word-final syllables. In addition, the work contains an exhaustive morphological classification of the nouns and adjectives that occur in canonical Old Church Slavic. I argue that Proto-Indo-European */o/ became Proto-Slavic */u/ before word-final */s/ and */N/. This conclusion is based on the impossibility of finding credible analogical (as opposed to phonological) explanations for the forms supporting the ALG hypothesis, and on the survival of the neuter gender in Slavic. It is not likely that the */o/-stem nominative singular ending */-u/ was borrowed from the accusative singular, because the latter would have been the only paradigmatic form with the stem vowel */-u-/. It is equally unlikely that the ending */-u/ was borrowed from the */u/-stems, because the latter constituted a moribund class. The usually stated motivation for such an analogical borrowing, i.e. a need to prevent the merger of */o/-stem masculines with neuters of the same class, is not tenable. Extra-Slavic, as well as intra-Slavic evidence suggests that phonologically-triggered mergers between two semantically opaque genders do not tend to be prevented, but rather that such mergers lead to the loss of the gender opposition in question. On the other hand, if */-os/ had not become */-us/, most nouns and, most importantly, all adjectives and pronouns would have lost the formal distinction between masculines and neuters. This would have necessarily resulted in the loss of the neuter gender. A new explanation is given for the most apparent piece of evidence against the ALG hypothesis, the nominative-accusative singular of the */es/-stem neuters, e.g. nebo 'sky'. I argue that it arose in late Proto-Slavic dialects, replacing regular nebe, under the influence of the */o/- and */yo/-stems where a correlation had emerged between a hard root-final consonant and the termination -o, on the one hand, and a soft root-final consonant and the termination -e, on the other.

Kansallisvaltion teräsmiehestä valtakunnan sovittelijaksi : Poliisikulttuurin psykohistorialliset solmukohdat 1930-1997

From Steely Nation-State Superman to Conciliator of Economical Global Empire – A Psychohistory of Finnish Police Culture 1930-1997 My study concerns the way police culture has changed within the societal changes in Finnish society between 1930 and 1997. The method of my study was psycho-historical and post-structural analysis. The research was conducted by examining the psycho-historical plateaus traceable within Finnish police culture. I made a social diagnosis of the autopoietic relationship between the power-holders of Finnish society and the police (at various levels of hierarchical organization). According to police researcher John P. Crank, police culture should be understood as the cognitive processes behind the actions of the police. Among these processes are the values, beliefs, rituals, customs and advice which standardize their work and the common sense of policemen. According to Crank, police culture is defined by a mindset which thinks, judges and acts according to its evaluations filtered by its own preliminary comprehension. Police culture consists of all the unsaid assumptions of being a policeman, the organizational structures of police, official policies, unofficial ways of behaviour, forms of arrest, procedures of practice and different kinds of training habits, attitudes towards suspects and citizens, and also possible corruption. Police culture channels its members’ feelings and emotions. Crank says that police culture can be seen in how policemen express their feelings. He advises police researchers to ask themselves how it feels to be a member of the police. Ethos has been described as a communal frame for thought that guides one’s actions. According to sociologist Martti Grönfors, the Finnish mentality of the Protestant ethic is accentuated among Finnish policemen. The concept of ethos expresses very well the self-made mentality as an ethical tension which prevails in police work between communal belonging and individual freedom of choice. However, it is significant that it is a matter of the quality of relationships, and that the relationship is always tied to the context of the cultural history of dealing with one’s anxiety. According to criminologist Clifford Shearing, the values of police culture act as subterranean processes of the maintenance of social power in society. Policemen have been called microcosmic mediators, or street corner politicians. Robert Reiner argues that at the level of self-comprehension, policemen disparage the dimension of politics in their work. Reiner points out that all relationships which hold a dimension of power are political. Police culture has also been called a canteen culture. This idea expresses the day-to-day basis of the mentality of taking care of business which policing produces as a necessity for dealing with everyday hardships. According to police researcher Timo Korander, this figurative expression embodies the nature of police culture as a crew culture which is partly hidden from police chiefs who are at a different level. This multitude of standpoints depicts the diversity of police cultures. According to Reiner, one should not see police culture as one monolithic whole; instead one should assess it as the interplay of individuals negotiating with their environment and societal power networks. The cases analyzed formed different plateaus of study. The first plateau was the so-called ‘Rovaniemi arson’ case in the summer of 1930. The second plateau consisted of the examinations of alleged police assaults towards the Communists during the Finnish Continuation War of 1941 to 1944 and the threats that societal change after the war posed to Finnish Society. The third plateau was thematic. Here I investigated how using force towards police clients has changed culturally from the 1930s to the 1980s. The fourth plateau concerned with the material produced by the Security Police detectives traced the interaction between Soviet KGB agents and Finnish politicians during the long 1970s. The fifth plateau of larger changes in Finnish police culture then occurred during the 1980s as an aftermath of the former decade. The last, sixth plateau of changing relationships between policing and the national logic of action can be seen in the murder of two policemen in the autumn of 1997. My study shows that police culture has transformed from a “stone cold” steely fixed identity towards a more relational identity that tries to solve problems by negotiating with clients instead of using excessive force. However, in this process of change there is a traceable paradox in Finnish policing and police culture. On the one hand, policemen have, at the practical level, constructed their policing identity by protecting their inner self in their organizational role at work against the projections of anger and fear in society. On the other hand, however, they have had to safeguard themselves at the emotional level against the predominance of this same organizational role. Because of this dilemma they must simultaneously construct both a distance from their own role as police officers and the role of the police itself. This makes the task of policing susceptible to the political pressures of society. In an era of globalization, and after the heyday of the welfare state, this can produce heightened challenges for Finnish police culture.

Noviisiopettajana peruskoulussa : Aloittelevien opettajien autenttisia kokemuksia ensimmäisestä opettajavuodesta

As a Novice Teacher at Comprehensive School: The authentic experiences of the beginning teachers during their first year of teaching The aim of this study is to explicate the novice year of teaching in the light of teachers´ authentic experiences. The subject of this investigation is the teachers´ subjective world of experience during their first academic year of teaching and the sharing of these experiences in collaborative consulting meetings. The themes discussed in the meetings were introduced into the collaborative group by the novice teachers themselves, and the progress of discussion was con-trolled by them. The research data was gathered in a consultative working group where the way a novice teacher starts to interpret, analyze and identify his/her own complex and dynamic teaching situations was observed. The research data gathered in this way illuminates novice teachers´ world of experience and mental picture as well as the unconscious sides of school life. In a theoretical frame of reference, the work of a teacher is identified, according to systemic scientific thought, as a dynamic triangle in which the basic elements are the personality of the teacher, the role of the teacher and the school as an organization. These basic elements form a whole within which the teacher works. The dynamics of this triangle in a teacher’s work are brought to light through the study of the phenomena of groups and group dynamics since a teacher works either as a member of a group (working community), as a leader of a group (teaching situations) or in a network (parent – teacher cooperation). Therefore, tension and force are always present in teaching work. The main research problem was to explain how a novice teacher experiences his/her first working year as a teacher. The participants (n=5) were teaching at five different comprehensive schools in the city of Helsinki. This was their first long-term post as a teacher. The research data consists of seven collaborative consulting meetings, as well as recordings and transcripts of the meetings. A classificatory framework was developed for data analysis which enabled a sys-tematic qualitative content analysis based on theory and material. In addition to the consulting meetings, the teachers were interviewed at the beginning and at the end of the process of collecting the research material. The interviews were used to interpret the meanings of the content analysis based on raw data. The findings show that there is a gap between teacher education and the reality of school life, which causes difficulties for a novice teacher during his/her first teaching year. The gap is rather a global educational problem than a national one, and therefore it is independent of cultural factors. Novice teachers desire a well-structured theory of teacher education and a clear programme where the themes and content delve deeper and deeper into the subject matter during the study years. According to the novice teachers, teacher education frequently consists of sporadic and unconnected study and class situations. An individual content weakness of teacher education is the lack of insufficient initiation into evaluation processes. The novice teachers suggest that a student must be provided good-quality and competent guidance during the study years and during his or her induction. There should be a well-organized, structured and systematic induction program for novice teachers. The induction program should be overseen by an organization so that the requirements of a qualified induction can be met. The findings show that the novice teachers find the first year of teaching at comprehensive school emotionally loaded. The teachers experienced teaching as difficult work and found the workload heavy. Nevertheless, they enjoyed their job because, as they said, there were more pleasant than unpleasant things in their school day. Their main feeling at school was the joy of success in teaching. The novice teachers felt satisfaction with their pupils. The teachers experienced the more serious feelings of anger and disgust when serious violence took place. The most difficult situations arose from teaching pupils who had mental health problems. The toughest thing in the teacher´s work was teaching groups that are too heterogeneous. The most awkward problems in group dynamics happened when new immigrants, who spoke only their own languages, were integrated into the groups in the middle of the school year. Teachers wanted to help children who needed special help with learning but restated at the same time that the groups being taught shouldn’t be too heterogeneous. The teachers wished for help from school assistants so that they could personally concentrate more on teaching. Not all the parents took care of their children according to the comprehensive school law. The teachers found it hard to build a confidential relationship between home and school. In this study, novice teachers found it hard to join the teaching staff at school. Some of the teachers on staff were very strong and impulsive, reacting loudly and emotionally. These teachers provoked disagreement, conflicts, power struggles and competition among the other teachers. Although the novice teachers of the study were all qualified teachers, three of them were not interested in a permanent teaching job. For these teachers teaching at a primary school was just a project, a short period in their working life. They will remain in the teaching profession as long as they are learning new things and enjoying their teaching job. This study is an independent part of the research project on Interplay – Connecting Academic Teacher Education and Work, undertaken by the Department of Applied Sciences of Education at the University of Helsinki. Key words: novice teacher, emotions, groups and group dynamics, authority, co-operation between home and school, teacher community, leadership at school, induction, consulting

Cancer survivors at work : Work-related problems and factors associated with their employment, work ability and social support from the work community

Due to the improved prognosis of many forms of cancer, an increasing number of cancer survivors are willing to return to work after their treatment. It is generally believed, however, that people with cancer are either unemployed, stay at home, or retire more often than people without cancer. This study investigated the problems that cancer survivors experience on the labour market, as well as the disease-related, sociodemographic and psychosocial factors at work that are associated with the employment and work ability of cancer survivors. The impact of cancer on employment was studied combining the data of Finnish Cancer Registry and census data of the years 1985, 1990, 1995 or 1997 of Statistics Finland. There were two data sets containing 46 312 and 12 542 people with cancer. The results showed that cancer survivors were slightly less often employed than their referents. Two to three years after the diagnosis the employment rate of the cancer survivors was 9% lower than that of their referents (64% vs. 73%), whereas the employment rate was the same before the diagnosis (78%). The employment rate varied greatly according to the cancer type and education. The probability of being employed was greater in the lower than in the higher educational groups. People with cancer were less often employed than people without cancer mainly because of their higher retirement rate (34% vs. 27%). As well as employment, retirement varied by cancer type. The risk of retirement was twofold for people having cancer of the nervous system or people with leukaemia compared to their referents, whereas people with skin cancer, for example, did not have an increased risk of retirement. The aim of the questionnaire study was to investigate whether the work ability of cancer survivors differs from that of people without cancer and whether cancer had impaired their work ability. There were 591 cancer survivors and 757 referents in the data. Even though current work ability of cancer survivors did not differ between the survivors and their referents, 26% of cancer survivors reported that their physical work ability, and 19% that their mental work ability had deteriorated due to cancer. The survivors who had other diseases or had had chemotherapy, most often reported impaired work ability, whereas survivors with a strong commitment to their work organization, or a good social climate at work, reported impairment less frequently. The aim of the other questionnaire study containing 640 people with the history of cancer was to examine extent of social support that cancer survivors needed, and had received from their work community. The cancer survivors had received most support from their co-workers, and they hoped for more support especially from the occupational health care personnel (39% of women and 29% of men). More support was especially needed by men who had lymphoma, had received chemotherapy or had a low education level. The results of this study show that the majority of the survivors are able to return to work. There is, however, a group of cancer survivors who leave work life early, have impaired work ability due to their illness, and suffer from lack of support from their work place and the occupational health services. Treatment-related, as well as sociodemographic factors play an important role in survivors' work-related problems, and presumably their possibilities to continue working.

Debunking Weak Sustainable Consumption : Towards Strong Sustainable Consumption Governance

Achieving sustainable consumption patterns is a crucial step on the way towards sustainability. The scientific knowledge used to decide which priorities to set and how to enforce them has to converge with societal, political, and economic initiatives on various levels: from individual household decision-making to agreements and commitments in global policy processes. The aim of this thesis is to draw a comprehensive and systematic picture of sustainable consumption and to do this it develops the concept of Strong Sustainable Consumption Governance. In this concept, consumption is understood as resource consumption. This includes consumption by industries, public consumption, and household consumption. Next to the availability of resources (including the available sink capacity of the ecosystem) and their use and distribution among the Earth’s population, the thesis also considers their contribution to human well-being. This implies giving specific attention to the levels and patterns of consumption. Methods: The thesis introduces the terminology and various concepts of Sustainable Consumption and of Governance. It briefly elaborates on the methodology of Critical Realism and its potential for analysing Sustainable Consumption. It describes the various methods on which the research is based and sets out the political implications a governance approach towards Strong Sustainable Consumption may have. Two models are developed: one for the assessment of the environmental relevance of consumption activities, another to identify the influences of globalisation on the determinants of consumption opportunities. Results: One of the major challenges for Strong Sustainable Consumption is that it is not in line with the current political mainstream: that is, the belief that economic growth can cure all our problems. So, the proponents have to battle against a strong headwind. Their motivation however is the conviction that there is no alternative. Efforts have to be taken on multiple levels by multiple actors. And all of them are needed as they constitute the individual strings that together make up the rope. However, everyone must ensure that they are pulling in the same direction. It might be useful to apply a carrot and stick strategy to stimulate public debate. The stick in this case is to create a sense of urgency. The carrot would be to articulate better the message to the public that a shrinking of the economy is not as much of a disaster as mainstream economics tends to suggest. In parallel to this it is necessary to demand that governments take responsibility for governance. The dominant strategy is still information provision. But there is ample evidence that hard policies like regulatory instruments and economic instruments are most effective. As for Civil Society Organizations it is recommended that they overcome the habit of promoting Sustainable (in fact green) Consumption by using marketing strategies and instead foster public debate in values and well-being. This includes appreciating the potential of social innovation. A countless number of such initiatives are on the way but their potential is still insufficiently explored. Beyond the question of how to multiply such approaches, it is also necessary to establish political macro structures to foster them.

Suomen maatalouden tuottamat kasvihuonekaasujen päästöt eri politiikkaskenaarioissa

Climate change is the single biggest environmental problem in the world at the moment. Although the effects are still not fully understood and there is considerable amount of uncertainty, many na-tions have decided to mitigate the change. On the societal level, a planner who tries to find an eco-nomically optimal solution to an environmental pollution problem seeks to reduce pollution from the sources where reductions are most cost-effective. This study aims to find out how effective the instruments of the agricultural policy are in the case of climate change mitigation in Finland. The theoretical base of this study is the neoclassical economic theory that is based on the assumption of a rational economic agent who maximizes his own utility. This theoretical base has been widened towards the direction clearly essential to the matter: the theory of environmental eco-nomics. Deeply relevant to this problem and central in the theory of environmental economics are the concepts of externalities and public goods. What are also relevant are the problems of global pollution and non-point-source pollution. Econometric modelling was the method that was applied to this study. The Finnish part of the AGMEMOD-model, covering the whole EU, was used for the estimation of the development of pollution. This model is a seemingly recursive, partially dynamic partial-equilibrium model that was constructed to predict the development of Finnish agricultural production of the most important products. For the study, I personally updated the model and also widened its scope in some relevant matters. Also, I devised a table that can calculate the emissions of greenhouse gases according to the rules set by the IPCC. With the model I investigated five alternative scenarios in comparison to the base-line scenario of Agenda 2000 agricultural policy. The alternative scenarios were: 1) the CAP reform of 2003, 2) free trade on agricultural commodities, 3) technological change, 4) banning the cultivation of organic soils and 5) the combination of the last three scenarios as the maximal achievement in reduction. The maximal achievement in the alternative scenario 5 was 1/3 of the level achieved on the base-line scenario. CAP reform caused only a minor reduction when com-pared to the base-line scenario. Instead, the free trade scenario and the scenario of technological change alone caused a significant reduction. The biggest single reduction was achieved by banning the cultivation of organic land. However, this was also the most questionable scenario to be real-ized, the reasons for this are further elaborated in the paper. The maximal reduction that can be achieved in the Finnish agricultural sector is about 11 % of the emission reduction that is needed to comply with the Kyoto protocol.

Struggles over resources and representations in territorial conflicts in the Northern Autonomous Atlantic Region (RAAN), Nicaragua

Territoriality is a central issue in indigenous peoples struggles. The territorial struggles involve struggles over the control of natural resources and over political participation and representation, but also over the perception of territorial rights and the symbolic representation of the territory. These struggles are carried through both in material and symbolic ways through recurring to different discourses and representations that provide legitimation for the territorial claims of the group. The study is located in the Northern Autonomous Atlantic Region of Nicaragua. The study concerns the territorial strategies, conceptions and practices of the indigenous people and other actors. Territorial conflicts exist between the autonomous region and the central government of Nicaragua, between mestizo settlers and indigenous people, between different indigenous groups, and between these and development agents such as conservation projects. The study focuses on how territorial discourses and representations are used to legitimate territorial control. Environmental, historical and cartographical discourses are the most important discourses recurred to. The influence of discourses and representations on the territorial practices and policies of the different actors, the links between the local struggles and global processes, and the broader structural factors impacting on the territorial struggles are also analysed. Among the structural factors are the problems related to land tenure and management and the use of natural resources, the advance of the agricultural frontier, the institutional weaknesses of the central and regional governments and the legislative processes. The territorial discourses are both recurred to in a strategic way and also grounded in local ideals and practices. The discourses have produced real effects for example in legislation, land tenure systems, political representation and environmental practices. Although the use of discourses and representations are an important power tool in territorial struggles, territorial control cannot be effectively accomplished merely through representing territorial claims in a legitimate way or through reforming legislation, as the conflicts are also largely a result of structural factors affecting the region. The fieldwork was carried out during a total of twelve months between 2000 and 2002. The research methods used were semi-structured interviews, participant observation and participatory research methods. A broad range of literary sources were also used to collect data. The study is located within the field of critical political geography with a discursive political ecology approach. It can be called a critical realist approach to the discursive analysis of indigenous territoriality.

Problems and Algorithms for Sequence Segmentations

The analysis of sequential data is required in many diverse areas such as telecommunications, stock market analysis, and bioinformatics. A basic problem related to the analysis of sequential data is the sequence segmentation problem. A sequence segmentation is a partition of the sequence into a number of non-overlapping segments that cover all data points, such that each segment is as homogeneous as possible. This problem can be solved optimally using a standard dynamic programming algorithm. In the first part of the thesis, we present a new approximation algorithm for the sequence segmentation problem. This algorithm has smaller running time than the optimal dynamic programming algorithm, while it has bounded approximation ratio. The basic idea is to divide the input sequence into subsequences, solve the problem optimally in each subsequence, and then appropriately combine the solutions to the subproblems into one final solution. In the second part of the thesis, we study alternative segmentation models that are devised to better fit the data. More specifically, we focus on clustered segmentations and segmentations with rearrangements. While in the standard segmentation of a multidimensional sequence all dimensions share the same segment boundaries, in a clustered segmentation the multidimensional sequence is segmented in such a way that dimensions are allowed to form clusters. Each cluster of dimensions is then segmented separately. We formally define the problem of clustered segmentations and we experimentally show that segmenting sequences using this segmentation model, leads to solutions with smaller error for the same model cost. Segmentation with rearrangements is a novel variation to the segmentation problem: in addition to partitioning the sequence we also seek to apply a limited amount of reordering, so that the overall representation error is minimized. We formulate the problem of segmentation with rearrangements and we show that it is an NP-hard problem to solve or even to approximate. We devise effective algorithms for the proposed problem, combining ideas from dynamic programming and outlier detection algorithms in sequences. In the final part of the thesis, we discuss the problem of aggregating results of segmentation algorithms on the same set of data points. In this case, we are interested in producing a partitioning of the data that agrees as much as possible with the input partitions. We show that this problem can be solved optimally in polynomial time using dynamic programming. Furthermore, we show that not all data points are candidates for segment boundaries in the optimal solution.

Construction of a global map of human gene expression : the process, tools and analysis

This thesis studies human gene expression space using high throughput gene expression data from DNA microarrays. In molecular biology, high throughput techniques allow numerical measurements of expression of tens of thousands of genes simultaneously. In a single study, this data is traditionally obtained from a limited number of sample types with a small number of replicates. For organism-wide analysis, this data has been largely unavailable and the global structure of human transcriptome has remained unknown. This thesis introduces a human transcriptome map of different biological entities and analysis of its general structure. The map is constructed from gene expression data from the two largest public microarray data repositories, GEO and ArrayExpress. The creation of this map contributed to the development of ArrayExpress by identifying and retrofitting the previously unusable and missing data and by improving the access to its data. It also contributed to creation of several new tools for microarray data manipulation and establishment of data exchange between GEO and ArrayExpress. The data integration for the global map required creation of a new large ontology of human cell types, disease states, organism parts and cell lines. The ontology was used in a new text mining and decision tree based method for automatic conversion of human readable free text microarray data annotations into categorised format. The data comparability and minimisation of the systematic measurement errors that are characteristic to each lab- oratory in this large cross-laboratories integrated dataset, was ensured by computation of a range of microarray data quality metrics and exclusion of incomparable data. The structure of a global map of human gene expression was then explored by principal component analysis and hierarchical clustering using heuristics and help from another purpose built sample ontology. A preface and motivation to the construction and analysis of a global map of human gene expression is given by analysis of two microarray datasets of human malignant melanoma. The analysis of these sets incorporate indirect comparison of statistical methods for finding differentially expressed genes and point to the need to study gene expression on a global level.

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.