Optimisation Problems in Wireless Sensor Networks : Local Algorithms and Local Graphs

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.

Optimisation problems in wireless sensor networks

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating–dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating–dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs – these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating–dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.

From Creative Ideas to New Emerging Ventures: Entrepreneurial Processes among Finnish Design Entrepreneurs

This study focuses on self-employed industrial designers and how they emerge new venture ideas. More specifically, this study strives to determine what design entrepreneurs do when they create new venture ideas, how venture ideas are nurtured into being, and how the processes are organized to bring such ideas to the market in the given industrial context. In contemporary times when the concern for the creative class is peaking, the research and business communities need more insight of the kind that this study provides, namely how professionals may contribute to their entrepreneurial processes and other agents’ business processes. On the one hand, the interviews underlying this study suggest that design entrepreneurs may act as reactive service providers who are appointed by producers or marketing parties to generate product-related ideas on their behalf. On the other hand, the interviews suggest that proactive behaviour that aims on generating own venture ideas, may force design entrepreneurs to take considerable responsibility in organizing their entrepreneurial processes. Another option is that they strive to bring venture ideas to the market in collaboration, or by passing these to other agents’ product development processes. Design entrepreneurs’ venture ideas typically emerge from design related starting points and observations. Product developers are mainly engaged with creating their own ideas, whereas service providers refer mainly to the development of other agents’ venture ideas. In contrast with design entrepreneurs, external actors commonly emphasize customer demand as their primary source for new venture ideas, as well as development of these in close interaction with available means of production and marketing. Consequently, design entrepreneurs need to address market demand since without sales their venture ideas may as well be classified as art. In case, they want to experiment with creative ideas, then there should be another source of income to support this typically uncertain and extensive process. Currently, it appears like a lot of good venture ideas and resources are being wasted, when venture ideas do not suite available production or business procedures. Sufficient communication between design entrepreneurs and other agents would assist all parties in developing production efficient and distributable venture ideas. Overall, the findings suggest that design entrepreneurs are often involved simultaneously in several processes that aim at emerging new product related ventures. Consequently, design entrepreneurship is conceptualized in this study as a dual process. This implies that design entrepreneurs can simultaneously be in charge of their entrepreneurial processes, as they operate as resources in other agents’ business processes. The interconnection between activities and agents suggests that these kinds of processes tend to be both complex and multifaceted to their nature.