The Geru project has ended, and the work initiated in the Geru project is continued in the PAHA project.
Introduction
The Geru project conducts fundamental algorithmic research on data gathering in wireless sensor networks. Our focus is on computationally efficient methods, computational complexity, and mathematically provable bounds of optimality. Basic information about the project is available on the project flyer. Some highlights of our recent work are shown in a poster on local algorithms.
The research project is funded by the Academy of Finland during the years 2007–2009. The project constitutes a continuation of the work undertaken in the Academy of Finland project Networking and Architecture in Proactive Systems (NAPS, 2003–2005).
Researchers
Researchers at Helsinki Institute for Information Technology HIIT, Department of Computer Science, University of Helsinki:
- Dr. Patrik Floréen, researcher in charge
- Dr. Jukka Suomela, researcher
- Dr. Petteri Kaski, affiliated researcher
- Dr. Valentin Polishchuk, affiliated researcher
Research program: Algorithmic Data Analysis, research group: Adaptive Computing.
Wireless sensor networks
Wireless sensor networks consist of miniature electromechanical devices with sensing, positioning, computing and communication capabilities. Such networks are special cases of ad hoc networks, i.e., data communication networks without a prearranged infrastructure. A typical task for a sensor network is to gather measurement data (e.g., data on temperature and humidity conditions) to a common sink node through multi-hop wireless communication. Prospective applications of sensor networks cover a wide range of domains, such as environmental monitoring, military surveillance, inventory tracking, smart spaces, and material fatigue monitoring.
In the field of wireless sensor networks, there are two different kinds of research challenges. Firstly, there are challenges related to engineering aspects; for example, making commercial sensor node hardware smaller, more energy-efficient, and less expensive. Secondly, there are challenges related to theoretical computer science; for example, paving the way for future large-scale sensor networks by studying the computational complexity and approximability of underlying graph-theoretical problems. Our research focuses on the latter part, fundamental algorithmic aspects.
Research problem
Our goal is to establish how sensor networks should be deployed and operated in order to maximise the expected utility in a specific application. The joint optimisation problem requires us to determine where to place the sensor nodes, how to pre-process and aggregate data in the nodes, how to route data in the network, and when each node and each link should be active. In most applications, limited battery capacity is one of the main constraints. The utility function may be defined by considering the cost of network installation and operation, together with the benefit and cost of correct and incorrect decisions.
Publications
Patrik Floréen, Petteri Kaski, and Jukka Suomela. A distributed approximation scheme for sleep scheduling in sensor networks. Proc. 4th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), San Diego, CA, USA, June 2007.
Abstract: We investigate the theoretical feasibility of near-optimal, distributed sleep scheduling in energy-constrained sensor networks with pairwise sensor redundancy. In this setting, an optimal sleep schedule is equivalent to an optimal fractional domatic partition of the associated redundancy graph. We present a set of realistic assumptions on the structure of the communication and redundancy relations; for the family of networks meeting these assumptions, we develop an efficient distributed approximation scheme for sleep scheduling. For any ε ≥ 0, we demonstrate that it is possible to schedule the sensing activities of the nodes in a local and distributed manner so that the ratio of the optimum lifetime to the achieved lifetime of the network is at most 1+ε. The computational effort (time, memory and communication) required at each node depends on ε and the parameters of the network family, but given so-called anchor nodes (a set of nodes meeting certain density constraints) and locally unique node identifiers, the effort is independent of the actual network at hand; in particular, the required effort at each node remains constant as the size of the network is scaled up.
Jukka Suomela. Approximability of identifying codes and locating-dominating codes. Information Processing Letters 103 (2007), pages 28–33.
Abstract: We study the approximability and inapproximability of finding identifying codes and locating-dominating codes of the minimum size. In general graphs, we show that it is possible to approximate both problems within a logarithmic factor, but sublogarithmic approximation ratios are intractable. In bounded-degree graphs, there is a trivial constant-factor approximation algorithm, but arbitrarily low approximation ratios remain intractable. In so-called local graphs, there is a polynomial-time approximation scheme. We also consider fractional packing of codes and a related problem of finding minimum-weight codes.
Patrik Floréen, Petteri Kaski, Topi Musto, and Jukka Suomela. Local approximation algorithms for scheduling problems in sensor networks. Proc. 3rd International Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors), Wrocław, Poland, July 2007.
Abstract: We study fractional scheduling problems in sensor networks, in particular, sleep scheduling (generalisation of fractional domatic partition) and activity scheduling (generalisation of fractional graph colouring). The problems are hard to solve in general even in a centralised setting; however, we show that there are practically relevant families of graphs where these problems admit a local distributed approximation algorithm; in a local algorithm each node utilises information from its constant-size neighbourhood only. Our algorithm does not need the spatial coordinates of the nodes; it suffices that a subset of nodes is designated as markers during network deployment. Our algorithm can be applied in any marked graph satisfying certain bounds on the marker density; if the bounds are met, guaranteed near-optimal solutions can be found in constant time, space and communication per node. We also show that auxiliary information is necessary—no local algorithm can achieve a satisfactory approximation guarantee on unmarked graphs.
Petteri Kaski, Aleksi Penttinen, and Jukka Suomela. Coordinating concurrent transmissions: A constant-factor approximation of maximum-weight independent set in local conflict graphs. Proc. 6th International Conference on Ad-Hoc Networks & Wireless (AdHoc-NOW), Morelia, Mexico, September 2007.
Abstract: We study the algorithmic problem of coordinating transmissions in a wireless network where radio interference constrains concurrent transmissions on wireless links. We focus on pairwise conflicts between the links; these can be described as a conflict graph. Associated with the conflict graph are two fundamental network coordination tasks: (a) finding a nonconflicting set of links with the maximum total weight, and (b) finding a link schedule with the minimum total length. Our work shows that two assumptions on the geometric structure of conflict graphs suffice to achieve polynomial-time constant-factor approximations: (i) bounded density of devices, and (ii) bounded range of interference. We also show that these assumptions are not sufficient to obtain a polynomial-time approximation scheme for either coordination task.
Patrik Floréen, Petteri Kaski, Topi Musto, and Jukka Suomela. Approximating max-min linear programs with local algorithms. Proc. 22nd IEEE International Parallel & Distributed Processing Symposium (IPDPS), Miami, FL, USA, April 2008.
Abstract: A local algorithm is a distributed algorithm where each node must operate solely based on the information that was available at system startup within a constant-size neighbourhood of the node. We study the applicability of local algorithms to max-min LPs where the objective is to maximise mink Σv ckvxv subject to Σv aivxv ≤ 1 for each i and xv ≥ 0 for each v. Here ckv ≥ 0, aiv ≥ 0, and the support sets Vi = { v : aiv ≥ 0 }, Vk = { v : ckv ≥ 0 }, Iv = { i : aiv ≥ 0 } and Kv = { k : ckv ≥ 0 } have bounded size. In the distributed setting, each agent v is responsible for choosing the value of xv, and the communication network is a hypergraph H where the sets Vk and Vi constitute the hyperedges. We present inapproximability results for a wide range of structural assumptions; for example, even if |Vi| and |Vk| are bounded by some constants larger than 2, there is no local approximation scheme. To contrast the negative results, we present a local approximation algorithm which achieves good approximation ratios if we can bound the relative growth of the vertex neighbourhoods in H.
Patrik Floréen, Marja Hassinen, Petteri Kaski, and Jukka Suomela. Tight local approximation results for max-min linear programs. Proc. 4th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors), Reykjavík, Iceland, July 2008.
Abstract: In a bipartite max-min LP, we are given a bipartite graph G = (V ∪ I ∪ K, E), where each agent v ∈ V is adjacent to exactly one constraint i ∈ I and exactly one objective k ∈ K. Each agent v controls a variable xv. For each i ∈ I we have a nonnegative linear constraint on the variables of adjacent agents. For each k ∈ K we have a nonnegative linear objective function of the variables of adjacent agents. The task is to maximise the minimum of the objective functions. We study local algorithms where each agent v must choose xv based on input within its constant-radius neighbourhood in G. We show that for every ε ≥ 0 there exists a local algorithm achieving the approximation ratio ΔI (1 − 1/ΔK) + ε. We also show that this result is the best possible – no local algorithm can achieve the approximation ratio ΔI (1 − 1/ΔK). Here ΔI is the maximum degree of a vertex i ∈ I, and ΔK is the maximum degree of a vertex k ∈ K. As a methodological contribution, we introduce the technique of graph unfolding for the design of local approximation algorithms.
Valentin Polishchuk and Jukka Suomela. Optimal backlog in the plane. Proc. 4th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors), Reykjavík, Iceland, July 2008.
Abstract: Suppose that a cup is installed at every point of a planar set P, and that somebody pours water into the cups. The total rate at which the water flows into the cups is 1. A player moves in the plane with unit speed, emptying the cups. At any time, the player sees how much water there is in every cup. The player has no information on how the water will be poured into the cups in the future; in particular, the pouring may depend on the player's motion. The backlog of the player is the maximum amount of water in any cup at any time, and the player's objective is to minimise the backlog. Let D be the diameter of P. If the water is poured at the rate of 1/2 into the cups at the ends of a diameter, the backlog is Ω(D). We show that there is a strategy for the player that guarantees the backlog of O(D), matching the lower bound up to a multiplicative constant. Note that our guarantee is independent of the number of the cups.
Alon Efrat, Sándor P. Fekete, Poornananda R. Gaddehosur, Joseph S. B. Mitchell, Valentin Polishchuk, and Jukka Suomela. Improved approximation algorithms for relay placement. Proc. 16th Annual European Symposium on Algorithms (ESA), Karlsruhe, Germany, September 2008.
Abstract: In the relay placement problem the input is a set of sensors and a number r ≥ 1, the communication range of a relay. The objective is to place a minimum number of relays so that between every pair of sensors there is a path through sensors and/or relays such that the consecutive vertices of the path are within distance r if both vertices are relays and within distance 1 otherwise. We present a 3.11-approximation algorithm, and show that the problem admits no PTAS, assuming P ≠ NP.
Petteri Kaski, Aleksi Penttinen, and Jukka Suomela. Coordinating concurrent transmissions: A constant-factor approximation of maximum-weight independent set in local conflict graphs. Ad Hoc & Sensor Wireless Networks 6 (2008), pages 239–263.
Abstract: We study the algorithmic problem of coordinating transmissions in a wireless network where radio interference constrains concurrent transmissions on wireless links. We focus on pairwise conflicts between the links; these can be described as a conflict graph. Associated with the conflict graph are two fundamental network coordination tasks: (a) finding a nonconflicting set of links with the maximum total weight, and (b) finding a link schedule with the minimum total length. Our work shows that two assumptions on the geometric structure of conflict graphs suffice to achieve polynomial-time constant-factor approximations: (i) bounded density of devices, and (ii) bounded range of interference. We also show that these assumptions are not sufficient to obtain a polynomial-time approximation scheme (PTAS) for either coordination task. There exists a PTAS if we make an additional assumption: (iii) bounded range of radio transmissions.
Valentin Polishchuk and Jukka Suomela. A simple local 3-approximation algorithm for vertex cover. Information Processing Letters 109 (2009), pages 642–645.
Abstract: We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required.
Patrik Floréen, Joel Kaasinen, Petteri Kaski, and Jukka Suomela. An optimal local approximation algorithm for max-min linear programs. Proc. 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Calgary, Canada, August 2009.
Abstract: In a max-min LP, the objective is to maximise ω subject to Ax ≤ 1, Cx ≥ ω1, and x ≥ 0 for nonnegative matrices A and C. We present a local algorithm (constant-time distributed algorithm) for approximating max-min LPs. The approximation ratio of our algorithm is the best possible for any local algorithm; there is a matching unconditional lower bound.
Matti Åstrand, Patrik Floréen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto. A local 2-approximation algorithm for the vertex cover problem. Proc. 23rd International Symposium on Distributed Computing (DISC), Elche, Spain, September 2009.
Abstract: We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.
Christoph Lenzen, Jukka Suomela, and Roger Wattenhofer. Local algorithms: self-stabilization on speed. Proc. 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Lyon, France, November 2009. Invited paper.
Matti Åstrand and Jukka Suomela. Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. Proc. 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Santorini, Greece, June 2010.
Abstract: 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.
Patrik Floréen, Petteri Kaski, Valentin Polishchuk, and Jukka Suomela. Almost stable matchings by truncating the Gale–Shapley algorithm. Algorithmica 58 (2010), pages 102–118.
Abstract: We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose–accept rounds executed by the Gale–Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance; for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds. We apply our results to give a distributed (2 + ε)-approximation algorithm for maximum-weight matching in bicoloured graphs and a centralised randomised constant-time approximation scheme for estimating the size of a stable matching.
Last updated on 17 Jun 2010 by Jukka Suomela - Page created on 22 Jan 2007 by Jukka Suomela