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.

The Finnish Competition State and Entrepreneurial Policies in the Helsinki Region

The thesis examines the intensification and characteristics of a policy that emphasises economic competitiveness in Finland during the 1990s and early 2000s. This accentuation of economic objectives is studied at the level of national policy-making as well as at the regional level through the policies and strategies of cities and three universities in the Helsinki region. By combining the analysis of state policies, urban strategies and university activities, the study illustrates the pervasiveness of the objective of economic competitiveness and growth across these levels and sheds light on the features and contradictions of these policies on a broad scale. The thesis is composed of five research articles and a summary article. At the level of national policies, the central focus of the thesis is on the growing role of science and technology policy as a state means to promote structural economic change and its transformation towards a broader, yet ambivalent concept of innovation policy. This shift brings forward a tension between an increasing emphasis on economic aspects – innovations and competitiveness – as well as the expanding scope of issues across a wide range of policy sectors that are being subsumed under this market- and economy oriented framework. Related to science and technology policy, attention is paid to adjustments in university policy in which there has been increasing pressure for efficiency, rationalisation and commercialisation of academic activities. Furthermore, political efforts to build an information society through the application of information and communication technologies are analysed with particular attention to the balance between economic and social objectives. Finally, changes in state regional policy priorities and the tendency towards competitiveness are addressed. At the regional level, the focus of the thesis is on the policies of the cities in Finland’s capital region as well as strategies of three universities operating in the region, namely the University of Helsinki, Helsinki University of technology and Helsinki School of Economics. As regards the urban level, the main focus is on the changes and characteristics of the urban economic development policy of the City of Helsinki. With respect to the universities, the thesis examines their attempts to commercialise research and thus bring academic research closer to economic interests, and pays particular attention to the contradictions of commercialisation. Related to the universities, the activities of three intermediary organisations that the universities have established in order to increase cooperation with industry are analysed. These organisations are the Helsinki Science Park, Otaniemi International Innovation Centre and LTT Research Ltd. The summary article provides a synthesis of the material presented in the five original articles and relates the results of the articles to a broader discussion concerning the emergence of competition states and entrepreneurial cities and regions. The main points of reference are Bob Jessop’s and Neil Brenner’s theses on state and urban-regional restructuring. The empirical results and considerations from Finland and the Helsinki region are used to comment on, specify and criticise specific parts of the two theses.

The Tourism-Development Nexus in Namibia : A Study on National Tourism Policy and Local Tourism Enterprises' Policy Knowledge

The tourism development nexus in southern Africa involves highly topical issues related to tourism planning, power relations, community participation, and natural resources. Namibia offers a particularly interesting context for the study of these issues due to its colonial legacy, vast tourism potential, recently adopted tourism policy and community-based approaches to tourism and natural resource management. This study is an interdisciplinary endeavour to analyse the role of tourism in Namibia s post-apartheid transformation process by focusing on Namibian tourism policy and local tourism enterprises' policy knowledge. Major attention is paid to how the tourism policy's national development objectives are understood and conceptualised by the representatives of different tourism enterprises and the ways in which they relate to the practical needs of the enterprises. Through such local policy knowledge the study explores various opportunities, challenges and constraints related to the promotion of tourism as a development strategy. The study utilises a political economy approach to tourism and development through three current and interrelated discourses which are relevant in the Namibian context. These are tourism, power and inequality, tourism and sustainable development, and tourism and poverty reduction. The qualitative research material was gathered in Namibia in 2006-2007 and 2008. This material consists of 34 semi-structured interviews in 16 tourism enterprises, including private trophy hunting farms and private lodges, small tour operators and community-based tourism enterprises. In addition, the research material consists of observations in the enterprises, and 37 informal and 23 expert interviews. The findings indicate that in the light of local tourism enterprises the tourism policy objectives appear more complex and ambiguous. Furthermore, they involve multiple meanings and interpretations which reflect the socio-economic stratification of the informants and Namibian society, together with the professional stratification of the tourism enterprises and restrictions on the capacity of tourism to address the development objectives. In the light of such findings it is obvious that aspects of power and inequality affect the tourism development nexus in Namibia. The study concludes that, as in the case of other southern African countries, in order to promote sustainable development and reduce poverty, Namibia should not only target tourism growth but pay attention to who benefits from that growth and how. From a political economy point of view, it is important that prevailing structural challenges are addressed equally in the planning of tourism, development and natural resource management. Such approach would help the Namibian majority to enjoy the benefits of increasing tourism in the country.

Whose ETSIP? National and local ownership of Namibia's education and training sector improvement programme

Tämä työ tarkastelee kansallista ja paikallista omistajuutta Namibian opetussektorin kehittämisohjelmassa. Opetussektorin kehittämisohjelma ETSIP on 15-vuotinen sektoriohjelma vuosille 2005-2015 ja sen tavoitteena on edesauttaa Namibian kehittymistä tietoyhteiskunnaksi. Tutkimuksen tarkoituksena on selvittää miten kansallinen ja paikallinen omistajuus on toteutunut ETSIP prosessin aikana. Erityisesti pyritään selvittämään paikallistason opetussektorin virkamiesten näkemyksiä ETSIP prosessista, heidän roolistaan siinä ja siitä millaisia vaikuttamisen ja hallinnan mahdollisuuksia heillä on ollut prosessin aikana. Tutkimuksen lähtökohta on laadullinen ja lähestymistapa konstruktionistinen: tutkimus tarkastelee todellisuutta ihmisten kokemusten, näkemysten ja toiminnan kautta. Tutkimusaineisto koostuu haastatteluista, epävirallisista keskusteluista, lehtiartikkeleista ja ETSIP dokumenteista. Tutkimus osoittaa että kansallinen omistajuus on epämääräinen käsite sillä kansallisia toimijoita ja näkemyksiä on useita. Tutkimus vahvistaa Castel-Brancon huomion siitä, että omistajuutta on tarkasteltava kontekstissaan: muuttuvana ja kilpailtuna. ETSIPin rinnalle ollaan valmistelemassa uutta strategista ohjelmaa opetusministeriölle mikä saattaa muuttaa omistajuutta ETSIPiin. ETSIP dokumenttien omistajuusretoriikka myötäilee kansainvälisiä sitoumuksia avun vaikuttavuuden parantamiseksi mutta niistä puuttuu syvällisempi analyysi siitä, miten kansallinen ja paikallinen omistajuus toteutuisi käytännössä. Avunantajien näkemys omistajuudesta on suppea: omistajuus nähdään lähinnä sitoutumisena ennalta määrättyyn politiikkaohjelmaan. Haastatteluaineistosta nousee esiin Whitfieldin ja Frazerin jaottelu suppeista ja laajoista omistajuuskäsityksistä. Sitoutumista ETSIP ohjelmaan pidetään tärkeänä mutta riittämättömänä määritteenä omistajuudelle. Paikallisella tasolla sitoutuminen ETSIP ohjelman periaatteisiin ja tavoitteisiin on toteutunut melko hyvin mutta jos omistajuutta tarkastellaan laajemmin vaikutusvallan ja hallinnan käsitteiden kautta voidaan todeta että omistajuus on ollut heikkoa. Paikallisella tasolla ei ole ollut juurikaan vaikutusvaltaa ETSIP ohjelman sisältöön eikä mahdollisuutta hallita ohjelman toteutusta ja päättää siitä mitä hankkeita ohjelman kautta rahoitetaan. Tujanin demokraattisen omistajuuden käsite kuvaa tarvetta muuttaa ja laajentaa omistajuusajattelua huomioiden paikallisen tason paremmin. Tämä tutkimus viittaa siihen että omistajuuden toteutuminen paikallisella tasolla edellyttäisi institutionaalisen kulttuurin muutosta ja institutionaalisen legitimiteetin vahvistamista. Omistajuuden mahdollistamiseksi paikallisella tasolla tarvittaisiin poliittista johtajuutta, luottamusta, vastuullisuuden kulttuurin kehittämistä, tehokkaampaa tiedonjakoa, laajaa osallistumista, vuoropuhelua ja yhteistyötä. Ennen kaikkea tarvittaisiin paikallisen tason vaikutusvaltaa päätöksenteossa ja kontrollia resurssien käytöstä. Tälle muutokselle on selvä tarve ja tilaus.