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.

On the Benefits and Problems of the Object-Oriented Paradigm including a Finnish Study

Several researchers are of the opinion that there are many benefits in using the object-oriented paradigm in information systems development. If the object-oriented paradigm is used, the development of information systems may, for example, be faster and more efficient. On the other hand, there are also several problems with the paradigm. For example, it is often considered complex, it is often difficult to make use of the reuse concept and it is still immature in some areas. Although there are several interesting features in the object-oriented paradigm, there is still little comprehensive knowledge of the benefits and problems associated with it. The objective of the following study was to investigate and to gain more understanding of the benefits and problems of the object-oriented paradigm. A review of previous studies was made and twelve benefits and twelve problems were established. These benefits and problems were then analysed, studied and discussed. Further a survey and some case studies were made in order to get some knowledge on what benefits and problems with the object-oriented paradigm Finnish software companies had experienced. One hundred and four companies answered the survey that was sent to all Finnish software companies with five or more employees. The case studies were made with six large Finnish software companies. The major finding was that Finnish software companies were exceptionally positive towards the object-oriented information systems development and had experienced very few of the proposed problems. Finally two models for further research were developed. The first model presents connections between benefits and the second between problems.

Private and municipal forests and the forestry planning system in Japan - trends and problems after World War II.

XVIII IUFRO World Congress, Ljubljana 1986.

Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

We present a distributed algorithm that finds a maximal edge packing in O(Δ + log* W) synchronous communication rounds in a weighted graph, independent of the number of nodes in the network; here Δ is the maximum degree of the graph and W is the maximum weight. As a direct application, we have a distributed 2-approximation algorithm for minimum-weight vertex cover, with the same running time. We also show how to find an f-approximation of minimum-weight set cover in O(f2k2 + fk log* W) rounds; here k is the maximum size of a subset in the set cover instance, f is the maximum frequency of an element, and W is the maximum weight of a subset. The algorithms are deterministic, and they can be applied in anonymous networks.

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.

Pain among employees : risk factors and consequences

The overall objective of this study was to gain epidemiological knowledge about pain among employee populations. More specifically, the aims were to assess the prevalence of pain, to identify socio-economic risk groups and work-related psychosocial risk factors, and to assess the consequences in terms of health-related functioning and sickness absence. The study was carried out among the municipal employees of the City of Helsinki. Data comprised questionnaire survey conducted in years 2000-2002 and register data on sickness absence. Altogether 8960 40-60 year old employees participated to the survey (response rate 67%). Pain is common among ageing employees. Approximately 29 per cent of employees reported chronic pain and 15 per cent acute pain, and about seven per cent reported moderately or severely limiting disabling chronic pain. Pain was more common among those with lower level of education or in a low occupational class. -- Psychosocial work environment was associated with pain reports. Job strain, bullying at workplace, and problems in combining work and home duties were associated with pain among women. Among men combining work and home duties was not associated with pain, whereas organizational injustice showed associations. Pain affects functional capacity and predicts sickness absence. Those with pain reported lower level of both mental and physical functioning than those with no pain, physical functioning being more strongly affected than mental. Bodily location of pain or whether pain was acute or chronic had only minor impact on the variation in functioning, whereas the simple count of painful locations was associated with widest variation. Pain accounted for eight per cent of short term (1-3 day) sickness absence spells among men and 13 per cent among women. Of absence spells lasting between four and 14 days pain accounted for 23 per cent among women and 25 per cent among men, corresponding figures for over 14 day absence spells being 37 and 30 per cent. The association between pain and sickness absence was relatively independent of physical and psychosocial work factors, especially among women. The results of this study provide a picture of the epidemiology of pain among employees. Pain is a significant problem that seriously affects work ability. Information on risk groups can be utilized to make prevention measures more effective among those at high risk, and to decrease pain rates and thereby narrow the differences between socio-economic groups. Furthermore, the work-related psychosocial risk factors identified in this study are potentially modifiable, and it should be possible to target interventions on decreasing pain rates among employees.

Noncommutativity and Some of Its Present-Day Developments

This masters thesis explores some of the most recent developments in noncommutative quantum field theory. This old theme, first suggested by Heisenberg in the late 1940s, has had a renaissance during the last decade due to the firmly held belief that space-time becomes noncommutative at small distances and also due to the discovery that string theory in a background field gives rise to noncommutative field theory as an effective low energy limit. This has led to interesting attempts to create a noncommutative standard model, a noncommutative minimal supersymmetric standard model, noncommutative gravity theories etc. This thesis reviews themes and problems like those of UV/IR mixing, charge quantization, how to deal with the non-commutative symmetries, how to solve the Seiberg-Witten map, its connection to fluid mechanics and the problem of constructing general coordinate transformations to obtain a theory of noncommutative gravity. An emphasis has been put on presenting both the group theoretical results and the string theoretical ones, so that a comparison of the two can be made.

Modeling Efficient Classification as a Process of Confidence Assessment and Delegation

In visual object detection and recognition, classifiers have two interesting characteristics: accuracy and speed. Accuracy depends on the complexity of the image features and classifier decision surfaces. Speed depends on the hardware and the computational effort required to use the features and decision surfaces. When attempts to increase accuracy lead to increases in complexity and effort, it is necessary to ask how much are we willing to pay for increased accuracy. For example, if increased computational effort implies quickly diminishing returns in accuracy, then those designing inexpensive surveillance applications cannot aim for maximum accuracy at any cost. It becomes necessary to find trade-offs between accuracy and effort. We study efficient classification of images depicting real-world objects and scenes. Classification is efficient when a classifier can be controlled so that the desired trade-off between accuracy and effort (speed) is achieved and unnecessary computations are avoided on a per input basis. A framework is proposed for understanding and modeling efficient classification of images. Classification is modeled as a tree-like process. In designing the framework, it is important to recognize what is essential and to avoid structures that are narrow in applicability. Earlier frameworks are lacking in this regard. The overall contribution is two-fold. First, the framework is presented, subjected to experiments, and shown to be satisfactory. Second, certain unconventional approaches are experimented with. This allows the separation of the essential from the conventional. To determine if the framework is satisfactory, three categories of questions are identified: trade-off optimization, classifier tree organization, and rules for delegation and confidence modeling. Questions and problems related to each category are addressed and empirical results are presented. For example, related to trade-off optimization, we address the problem of computational bottlenecks that limit the range of trade-offs. We also ask if accuracy versus effort trade-offs can be controlled after training. For another example, regarding classifier tree organization, we first consider the task of organizing a tree in a problem-specific manner. We then ask if problem-specific organization is necessary.

Mining Cell Transition Data

Cell transition data is obtained from a cellular phone that switches its current serving cell tower. The data consists of a sequence of transition events, which are pairs of cell identifiers and transition times. The focus of this thesis is applying data mining methods to such data, developing new algorithms, and extracting knowledge that will be a solid foundation on which to build location-aware applications. In addition to a thorough exploration of the features of the data, the tools and methods developed in this thesis provide solutions to three distinct research problems. First, we develop clustering algorithms that produce a reliable mapping between cell transitions and physical locations observed by users of mobile devices. The main clustering algorithm operates in online fashion, and we consider also a number of offline clustering methods for comparison. Second, we define the concept of significant locations, known as bases, and give an online algorithm for determining them. Finally, we consider the task of predicting the movement of the user, based on historical data. We develop a prediction algorithm that considers paths of movement in their entirety, instead of just the most recent movement history. All of the presented methods are evaluated with a significant body of real cell transition data, collected from about one hundred different individuals. The algorithms developed in this thesis are designed to be implemented on a mobile device, and require no extra hardware sensors or network infrastructure. By not relying on external services and keeping the user information as much as possible on the user s own personal device, we avoid privacy issues and let the users control the disclosure of their location information.

Regional Integration and the State : The Changing Nature of Sovereignty in Southern Africa and Europe

The study explores the role of the state in regional integration processes. The question is approached through theoretical discussion and two case-studies - SADC (Southern African Development Community) and the EU. The main research question of the study is, what are the possibilities and problems of the integration process in Southern Africa and how do they differ from the possibilities and problems of the integration process in Europe. The undelrying question of the study is why do states decide to participate in an integration process where they have to limit their sovereignty. Review of the theoretical discussion of the integration studies shows that the integration process is affected by several factors on different levels of the international system. But the state plays a central role in integration processes - integration processes are inititated and carried on by the participatig states. The European integration process shows that the interests of the state can change over time. At the beginning of the integration process, the objective was to strengthen participating states. Later EU member states have decided that it is in their interest to deepen the process even if it has meant limitation of their sovereignty. The determinant factor has been that the member states have considered it to be in their interst to deepen the process. In Southern Africa the integration process is only at the beginning. SADC aims to establish a free trade area by 2008. The biggest challenge is how to implement the integration process so that it benefits all member states in a region that is economically dominated by South Africa. In practice this can be achieved through establishment of corrective mechanisms, which ensure equitable distribution of benefits. This would require deeper integration and South Africa to adapt responsibility towards its regional partners. African integration processes in general have not been as successful as for example the EU. African states have been reluctant to limit their sovereignty in favour of regional organisations.This can be explained by the differences between European and African states. The EU member states have been democracies while African states have been characterised by concentration of power in the executive branch. Furthermore the political systems in Africa have been characterised by vertical clientelist reltionships. As a result it has not been in the interest of the political elite to limit the state sovereignty in favour of regional organisations. In recent years SADC has been relatively succesful in its integration process and reforms, but a lot remains to be done before the implementation of the free trade area can be succesful. The institutional structure and treaties of SADC differ from the structures of the EU. Member states are the main actors of the integration processes. Their differences are reflected in the process and produce different kinds of integration in different parts of the world.

Phylogenetics of Myrmica ants and their social parasites

Understanding the overwhelming diversity of life calls for complex organisational schemes. The field of systematics may thus be seen as the cornerstone of evolutionary biology. In the last few decades, systematics has been rejuvenated through the introduction of molecular methods such as DNA barcoding and multi-gene phylogenetic approaches. These methods may shed new light on established taxonomic ideas and problems. For example, the classification of ants has aroused much debate due to reinterpretation of morphological characters or contradictions between molecular data and morphology. Only in the last few years a consensus was reached regarding the phylogeny of ant subfamilies. However, the situation remains deplorable for lower taxonomic ranks such as subfamilies, tribes and genera. This thesis describes the systematics and evolution of the Holarctic ant genus Myrmica and the tribe to which it belongs, Myrmicini. Using barcoding, molecular-phylogenetic data and divergence time estimations, it addresses questions regarding the taxonomy, morphology and biogeography of this group. Furthermore, the interrelationships between socially parasitic Myrmica species and their hosts (other species in the genus) were inferred. The phylogeny suggests that social parasitism evolved several times in Myrmica. Finally, this thesis investigated whether coevolution shaped the phylogeny of socially parasitic Maculinea butterflies that live inside Myrmica colonies. No evidence was found for coevolution.

Growing Flowers in the Frost: Civic Activity, Citizenship and Gender in Russia

This study analyzes civic activity, citizenship and their gendered manifestations in contemporary Russia. It is based on a case study conducted in the city of Tver , located in the vicinity of Moscow, during 2001-2005. The data consists of interviews with civic activists and municipal and regional authorities; observations of civic organizations; and a quantitative survey conducted among local civic groups. The theoretical and methodological framework of the study draws upon a micro perspective on organization, discourse analysis, gender and citizenship theories and Pierre Bourdieu s theory of fields and capital. This study develops theoretical understanding of the characteristics and logic of civic organization in Russia. It shows that social class centrally structures the field of civic activity. Organizations can be seen as a vehicle of the educated class to advocate their interests, help themselves and seek both social and individual-level change. The study also argues that civic organizations founded during the post-Soviet era are often an institutionalized form of informal social networks. Networks, which were a central element of everyday interaction in Soviet society, are a resource and often the only resource available that can be made use of in contemporary organizational activities. The study argues that gender operates as a key structuring principle in the Russian socio-political community. Civic activity is often discursively associated with femininity and institutional politics with masculinity. Women tend to participate more than men in civic organizations, while men dominate the formal political domain. The study shows that civic organizations are important loci of communality. This communality, however, differs from the communality envisioned in the communitarian and social capital debates in the West. It is selective communality , as it is restricted to the members of the organizations and does not create generalized reciprocity and trust. Civic organizations tend to build upon and reproduce the traditional Russian organizational form of circles , kruzhki. Along with the analysis of civic activities, the study also examines the redefinition of the role and functions of the state. The authorities interviewed in this study understand civic organizations as serving those goals and interests determined by the authorities, instead of viewing them as sites of citizens self-organization around interests and problems citizens themselves deem important, or as a counterforce to the state. By contrast, civic activists understand the core of organizational activity to be advocacy of their interests and rights, tackling social problems, the pursuit of wider social change and self-help. Co-operation between authorities and organizations tends to be personified and based upon unequal, hierarchical patron-client arrangements, which inhibits the development of democratic governance. The study will be published in Routledge Contemporary Russia and Eastern Europe Series later this year.

A Recursive Perspective on Discursive Legitimation and Organizational Action in Mergers and Acquisitions

This paper challenges the predominant view that legitimation is merely a specific phase in merger or acquisition processes. We argue that a better understanding of postmerger organizational dynamics calls for conceptualization of discursive legitimation as an inherent part of unfolding merger processes. In particular, we focus on the recursive relationship between legitimation and organizational action. We have two objectives: to outline a theoretical model that helps one to understand the dynamics of discursive legitimation and organizational action in postmerger organizations, and to examine a revealing case to distinguish the inherent risks and problems in discursive legitimation. Our case analysis focuses on the merger between the French pharmaceutical companies BioMérieux and Pierre Fabre. We adopt a critical multimethod approach and distinguish specific discursive dynamics and pathological tendencies in this case. The analysis highlights the unintended consequences of discursive legitimation, the central role of sensegiving and sensehiding in discursive legitimation, the inherently political nature of legitimation and the risks associated with politicization, the special problems associated with fashionable discourses and the role of the media, the use of specific discursive strategies for legitimation and delegitimation, and the crucial role of actual integration results. This analysis adds to the existing research on mergers and acquisitions by treating discursive legitimation as part of the merger dynamics. In particular, our case analysis provides a new explanation for merger failure. We also believe that the recursive model connecting discursive legitimation and delegitimation strategies to concrete organizational action makes a more general contribution to our understanding of organizational legitimation.

A recursive perspective on discursive legitimation and organizational action in mergers and acquisitions

This paper challenges the predominant view that legitimation is merely a specific phase in merger or acquisition processes. We argue that a better understanding of postmerger organizational dynamics calls for conceptualization of discursive legitimation as an inherent part of unfolding merger processes. In particular, we focus on the recursive relationship between legitimation and organizational action. We have two objectives: to outline a theoretical model that helps one to understand the dynamics of discursive legitimation and organizational action in postmerger organizations, and to examine a revealing case to distinguish the inherent risks and problems in discursive legitimation. Our case analysis focuses on the merger between the French pharmaceutical companies BioMérieux and Pierre Fabre. We adopt a critical multimethod approach and distinguish specific discursive dynamics and pathological tendencies in this case. The analysis highlights the unintended consequences of discursive legitimation, the central role of sensegiving and sensehiding in discursive legitimation, the inherently political nature of legitimation and the risks associated with politicization, the special problems associated with fashionable discourses and the role of the media, the use of specific discursive strategies for legitimation and delegitimation, and the crucial role of actual integration results. This analysis adds to the existing research on mergers and acquisitions by treating discursive legitimation as part of the merger dynamics. In particular, our case analysis provides a new explanation for merger failure. We also believe that the recursive model connecting discursive legitimation and delegitimation strategies to concrete organizational action makes a more general contribution to our understanding of organizational legitimation.