NCCR - MICS - Publications

home > Publications > Search

Found 121 publications with these criteria

Roland Flury and Roger Wattenhofer [FluryW:10] [published]
Slotted Programming for Sensor Networks
International Conference on Information Processing in Sensor Networks (IPSN), Stockholm, 12-16 Apr 10
We advocate a novel programming approach we call slotted programming that not only addresses the specic hardware capabilities of sensor nodes, but also facilitates coding through a truly modular design. The approach is based on the temporal decoupling of the dierent tasks of a sensor node such that at any time at most one task is active. In contrast to traditional sensor network programming, slotted programming guarantees that each of these tasks can be implemented as an independent software module, simplifying not only the coding and testing phase, but also the code reuse in a dierent context. In addition, we believe that the proposed approach is highly qualied for energy ecient and real time applications. To substantiate our claims, we have implemented slotos, an extension to TinyOS that supports slotted programming. Within this framework, we demonstrate the advantages of the slotted programming paradigm. [pdf]
Johannes Schneider and Roger Wattenhofer [SchneiderW:10] [published]
An Optimal Maximal Independent Set Algorithm for Bounded-Independence Graphs
Journal of Distributed Computing, 2010
Christoph Lenzen, Thomas Locher, Philipp Sommer, and Roger Wattenhofer [LenzenLSW:10] [published]
Clock Synchronization: Open Problems in Theory and Practice (Invited Paper)
36th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Splinderuv Mlyn, 23-29 Jan 10
Clock synchronization is one of the most basic building blocks for many applications in computer science and engineering. The purpose of clock synchronization is to provide the constituent parts of a distributed system with a common notion of time. While the problem of synchronizing clocks in distributed systems has already received considerable attention from researchers and practitioners alike, we believe that there are many fascinating problems that remain unsolved. In this paper, we give a brief overview of previous work in this area, followed by a discussion of open clock synchronization problems in theory and practice.
Thomas Locher, David Mysicka, Stefan Schmid, and Roger Wattenhofer [LocherMSW:10] [published]
Poisoning the Kad Network
11th International Conference on Distributed Computing and Networking (ICDCN), Kolkata, 3-6 Jan 10
Since the demise of the Overnet network, the Kad network has become not only the most popular but also the only widely used peer-to-peer system based on a distributed hash table. It is likely that its user base will continue to grow in numbers over the next few years as, unlike the eDonkey network, it does not depend on central servers, which increases scalability and reliability. Moreover, the Kad network is more efficient than unstructured systems such as Gnutella. However, we show that today’s Kad network can be attacked in several ways by carrying out several (well-known) attacks on the Kad network. The presented attacks could be used either to hamper the correct functioning of the network itself, to censor contents, or to harm other entities in the Internet not participating in the Kad network such as ordinary web servers. While there are simple heuristics to reduce the impact of some of the attacks, we believe that the presented attacks cannot be thwarted easily in any fully decentralized peerto- peer system without some kind of a centralized certification and verification authority.
Christoph Lenzen, Thomas Locher, and Roger Wattenhofer [LenzenLW:10] [published]
Tight Bounds for Clock Synchronization
Journal of the ACM, Volume 57, Number 2, Jan 2010
We present a novel clock synchronization algorithm and prove tight upper and lower bounds on the worst-case clock skew that may occur between any two participants in any given distributed system. More importantly, the worst-case clock skew between neighboring nodes is (asymptotically) at most a factor of two larger than the best possible bound. While previous results solely focused on the dependency of the skew bounds on the network diameter, we prove that our techniques are optimal also with respect to the maximum clock drift, the uncertainty in message delays, and the imposed bounds on the clock rates. The presented results all hold in a general model where both the clock drifts and the message delays may vary arbitrarily within pre-specified bounds. Furthermore, our algorithm exhibits a number of other highly desirable properties. First, the algorithm ensures that the clock values remain in an affine linear envelope of real time. A better worst-case bound on the accuracy with respect to real time cannot be achieved in the absence of an external timer. Second, the algorithm minimizes the number and size of messages that need to be exchanged in a given time period. Moreover, only a small number of bits must be stored locally for each neighbor. Finally, our algorithm can easily be adapted for a variety of other prominent synchronization models. [pdf]
Christoph Lenzen, Philipp Sommer, and Roger Wattenhofer [LenzenSW:09] [published]
Optimal Clock Synchronization in Networks
7th ACM Conference on Embedded Networked Sensor Systems (SenSys), Berkeley, 4-6 Nov 09
Having access to an accurate time is a vital building block in all networks; in wireless sensor networks even more so, because wireless media access or data fusion may depend on it. Starting out with a novel analysis, we show that orthodox clock synchronization algorithms make fundamental mistakes. The state-of-the-art clock synchronization algorithm FTSP exhibits an error that grows exponentially with the size of the network, for instance. Since the involved parameters are small, the error only becomes visible in midsize networks of about 10-20 nodes. In contrast, we present PulseSync, a new clock synchronization algorithm that is asymptotically optimal. We evaluate PulseSync on a Mica2 testbed, and by simulation on larger networks. On a 20 node network, the prototype implementation of PulseSync outperforms FTSP by a factor of 5. Theory and simulation show that for larger networks, PulseSync offers an accuracy which is several orders of magnitude better than FTSP. To round off the presentation, we investigate several optimization issues, e.g. media access and local skew.
Nicolas Burri, Roland Flury, Silvan Nellen, Benjamin Sigg, Philipp Sommer, and Roger Wattenhofer [BurriRFNSSW:09] [published]
YETI - An Eclipse Plug-in for TinyOS 2.1
7th ACM Conference on Embedded Networked Sensor Systems (SenSys), Berkeley, 4-6 Nov 09
We present YETI, an Eclipse plug-in providing support for TinyOS development. YETI provides features wellknown from development environments for other languages such as syntax highlighting, code completion and error detection. Furthermore, it includes an additional set of tools which are designed to ease the TinyOS development process for both newcomers and experienced developers. The plugin seamlessly integrates with the existing TinyOS toolchain and provides debugging support on the target platform using a JTAG hardware adapter.
Lars Schor, Philipp Sommer, and Roger Wattenhofer [SchorSW:09] [published]
Towards a Zero-Configuration Wireless Sensor Network Architecture for Smart Buildings
First ACM Workshop On Embedded Sensing Systems For Energy-Efficiency In Buildings (BuildSys), Berkeley, 3 Nov 09
Today’s buildings account for a large fraction of our energy consumption. In an effort to economize scarce fossil fuels on earth, sensor networks are a valuable tool to increase the energy efficiency of buildings without severely reducing our quality of life. Within a smart building many sensors and actuators are interconnected to form a control system. Nowadays, the deployment of a building control system is complicated because of different communication standards. In this paper, we present a web services-based approach to integrate resource constrained sensor and actuator nodes into IP-based networks. A key feature of our approach is its capability for automatic service discovery. For this purpose, we implemented an API to access services on sensor nodes following the architectural style of representational state transfer (REST). We implemented a prototype application based on TinyOS 2.1 on a custom sensor node platform with 8 Kbytes of RAM and an IEEE 802.15.4 compliant radio transceiver.
Christoph Lenzen, Jukka Suomela, and Roger Wattenhofer [LenzenSW:09] [published]
Local Algorithms: Self-Stabilization on Speed (Invited Paper)
11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Lyon, 3-6 Nov 09
Thomas Locher, David Mysicka, Stefan Schmid, and Roger Wattenhofer [LocherMSW:09] [published]
A Peer Activity Study in eDonkey and Kad (Invited paper)
International Workshop on Dynamic Networks: Algorithms and Security (DYNAS), Wroclaw, 5 Sep 09
Although several fully decentralized peer-to-peer systems have been proposed in the literature, most existing systems still employ a centralized architecture. In order to compare these two paradigms, as a case study, we conduct measurements in the eDonkey and the Kad network—two of the most popular peer-to-peer systems in use today. We reengineered the eDonkey server software and integrated two modified servers into the eDonkey network in order to monitor traffic. Additionally, we implemented a Kad client exploiting a design weakness to spy on the traffic at arbitrary locations in the ID space. The goal of this study is to provide insight into the spacial and temporal distributions of the peers’ activities and also examine the searched contents. Finally, we discuss problems related to the collection of such data sets and investigate techniques to verify the representativeness of the measured data.
Raphael Eidenbenz, Roger Wattenhofer [EidenbenzW:09] [published]
Brief Announcement: Selfishness in Transactional Memory
21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Calgary, 11-13 Aug 09
Johannes Schneider, Roger Wattenhofer [SchneiderW:09] [published]
Coloring Unstructured Wireless Multi-Hop Networks
ACM Symposium on Principles of Distributed Computing (PODC), Calgary, August 10-12, 2009
Christoph Lenzen, Thomas Locher, and Roger Wattenhofer [LenzenLW:09] [published]
Tight Bounds for Clock Synchronization
28th ACM Symposium on Principles of Distributed Computing (PODC), Calgary, 10-12 Aug 09
We present a novel clock synchronization algorithm and prove tight upper and lower bounds on the worst-case clock skew that may occur between any two participants in any given distributed system. More importantly, the worst-case clock skew between neighboring nodes is (asymptotically) at most a factor of two larger than the best possible bound. While previous results solely focused on the dependency of the skew bounds on the network diameter, we prove that our techniques are optimal also with respect to the maximum clock drift, the uncertainty in message delays, and the imposed bounds on the clock rates. The presented results all hold in a general model where both the clock drifts and the message delays may vary arbitrarily within pre-specied bounds. Furthermore, our algorithm exhibits a number of other highly desirable properties. First, the algorithm ensures that the clock values remain in an ane linear envelope of real time. A better bound on the accuracy with respect to real time cannot be achieved in the absence of an external timer. Second, the algorithm minimizes the number and size of messages that need to be exchanged in a given time period. Moreover, only a small number of bits must be stored locally for each neighbor. Finally, our algorithm can easily be adapted for a variety of other prominent synchronization models. [pdf]
Magnus Halldorsson and Roger Wattenhofer [HalldorssonW:09b] [published]
Wireless Communication is in APX
36th International Colloquium on Automata, Languages and Programming (ICALP), Rhodes, 5-12 July 2009.
In this paper we address a common question in wireless communication: How long does it take to satisfy an arbitrary set of wireless communication requests? This problem is known as the wireless scheduling problem. Our main result proves that wireless scheduling is in APX. In addition we present a robustness result, showing that constant parameter and model changes will modify the result only by a constant. [pdf]
Dominic Meier, Yvonne Anne Pignolet, Stefan Schmid, and Roger Wattenhofer [MeierPSW:09] [published]
Speed Dating despite Jammers
5th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS) , Marina del Rey, 8-10 June 2009
Many wireless standards and protocols today, such as WLAN and Bluetooth, operate on similar frequency bands. While this permits an efficient usage of the limited medium capacity, transmissions of nodes running different protocols can interfere. This paper studies how to design node discovery algorithms for wireless multichannel networks which are robust against contending protocols on the shared medium. We pursue a conservative approach and consider a Byzantine adversary who prevents the communication of our protocol on t channels in a worst-case fashion. Our model also captures disruptions controlled by an adversarial jammer. This paper presents algorithms for scenarios where t is not known. The analytical findings are complemented by simulations providing evidence that the proposed protocols perform well in practice. [pdf]
Thomas Locher, Remo Meier, Roger Wattenhofer, and Stefan Schmid [LocherMWS:09] [published]
Robust Live Media Streaming in Swarms
19th International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV), Williamsburg, 3-5 June 09
Reto Grob, Michael Kuhn, Roger Wattenhofer, and Martin Wirz [GrobKWW:09] [published]
Cluestr: Mobile Social Networking for Enhanced Group Communication
International Conference on Supporting Group Work (GROUP), Sanibel Island, 11-13 May 09
Recent technological advances foster the spreading of social software in the mobile domain. Hence, future usage patterns of mobile devices will involve more group interaction. While collaboration using mobile devices is an active area of research, only limited attention has been paid to the efficient initiation of group communication from mobile terminals. In this paper we present a community-aware mechanism that allows to efficiently select contacts in order to address them as a group. We have integrated the proposed method into a proof-of-concept application, and present preliminary experiments that demonstrate the accuracy of the approach and show significant time savings in the group initialization process.
R. Flury; S. Pemmaraju; R. Wattenhofer [FluryPW:09] [published]
Greedy Routing with Bounded Stretch
IEEE Infocom 09, Rio de Janeiro, 19-25 Apr 09
Olga Goussevskaia, Magnus Halldorsson, Roger Wattenhofer, and Emo Welzl [GoussevskaiaHWW:09] [published]
Capacity of Arbitrary Wireless Networks
28th Annual IEEE Conference on Computer Communications (INFOCOM), Rio de Janeiro, 19-25 April 2009
In this work we study the problem of determining the throughput capacity of a wireless network. We propose a scheduling algorithm to achieve this capacity within an approximation factor. Our analysis is performed in the physical interference model, where nodes are arbitrarily distributed in Euclidean space. We consider the problem separately from the routing problem and the power control problem, i.e., all requests are single-hop, and all nodes transmit at a fixed power level. The existing solutions to this problem have either concentrated on special-case topologies, or presented optimality guarantees which become arbitrarily bad (linear in the number of nodes) depending on the network’s topology. We propose the first scheduling algorithm with approximation guarantee independent of the topology of the network. The algorithm has a constant approximation guarantee for the problem of maximizing the number of links scheduled in one time-slot. Furthermore, we obtain a O(log n) approximation for the problem of minimizing the number of time slots needed to schedule a given set of requests. Simulation results indicate that our algorithm does not only have an exponentially better approximation ratio in theory, but also achieves superior performance in various practical network scenarios. Furthermore, we prove that the analysis of the algorithm is extendable to higherdimensional Euclidean spaces, and to more realistic boundeddistortion spaces, induced by non-isotropic signal distortions. Finally, we show that it is NP-hard to approximate the scheduling problem to within n1􀀀" factor, for any constant " > 0, in the non-geometric SINR model, in which path-loss is independent of the Euclidean coordinates of the node [pdf]
Philipp Sommer, Roger Wattenhofer [SommerW:09] [published]
Gradient Clock Synchronization in Wireless Sensor Networks
8th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN/SPOTS 2009), San Francisco, 13-16 Apr 09
Accurately synchronized clocks are crucial for many applications in sensor networks. Existing time synchronization algorithms provide on average good synchronization between arbitrary nodes, however, as we show in this paper, close-by nodes in a network may be synchronized poorly. We propose the Gradient Time Synchronization Protocol (GTSP) which is designed to provide accurately synchronized clocks between neighbors. GTSP works in a completely decentralized fashion: Every node periodically broadcasts its time information. Synchronization messages received from direct neighbors are used to calibrate the logical clock. The algorithm requires neither a tree topology nor a reference node, which makes it robust against link and node failures. The protocol is implemented on the Mica2 platform using TinyOS. We present an evaluation of GTSP on a 20-node testbed setup and simulations on larger network topologies. [pdf]
Pascal von Rickenbach, Roger Wattenhofer, and Aaron Zollinger. [RickenbachWZ:09] [published]
Algorithmic Models of Interference in Wireless Ad Hoc and Sensor Networks
IEEE/ACM Transactions on Networking, Volume 17, Number 1, February 2009.
Among the most critical issues of wireless ad hoc and sensor networks are energy consumption in general and interference in particular. The reduction of interference is consequently considered one of the foremost goals of topology control. Almost all of the related work however considers this issue implicitly: Low interference is often claimed to be a consequence of sparseness or low degree of the constructed topologies. This paper, in contrast, studies explicit definitions of interference. Various models of interference— both from a sender-centric and a receiver-centric perspective— are proposed, compared, and analyzed with respect to their algorithmic properties and complexities. [pdf]
Shantanu Das, Matúš Mihalák, Rastislav Šrámek, Elias Vicari, Peter Widmayer [DasMSVW:08] [published]
Rendezvous of Mobile Agents when Tokens Fail Anytime
12th International Conference On Principles Of Distributed Systems (OPODIS), Luxor, 15-18 Dec 08
We consider the problem of Rendezvous or gathering of multiple autonomous entities (called mobile agents) moving in an unlabelled environment (modelled as a graph). The problem is usually solved using randomization or assuming distinct identities for the agents, such that they can execute different protocols. When the agents are all identical and deterministic, and the environment itself is symmetrical (e.g. a ring) it is difficult to break the symmetry between them unless, for example, the agents are provided with a token to mark the nodes. We consider fault-tolerant protocols for the problem where the tokens used by the agents may disappear unexpectedly. If all tokens fail, then it becomes impossible, in general, to solve the problem. However, we show that with any number of failures (less than a total collapse), we can always solve the problem if the original instance of the problem was solvable. Unlike previous solutions, we can tolerate failures occurring at arbitrary times during the execution of the algorithm. Our solution can be applied to any arbitrary network even when the topology is unknown.
Fedor V. Fomin, Petr A. Golovach, Alex Hall, Matus Mihalak, Elias Vicari, Peter Widmayer [FominGHMVW:08] [published]
How to Guard a Graph?
International Symposium on Algorithms and Computation, Gold Coast, 15-17 Dec 2008
We initiate the study of the algorithmic foundations of games in which a set of cops has to guard a region in a graph (or digraph) against a robber. The robber and the cops are placed on vertices of the graph; they take turns in moving to adjacent vertices (or staying). The goal of the robber is to enter the guarded region at a vertex with no cop on it. The problem is to find the minimum number of cops needed to prevent the robber from entering the guarded region. The problem is highly non-trivial even if the robber's or the cops' regions are restricted to very simple graphs. The computational complexity of the problem depends heavily on the chosen restriction. In particular, if the robber's region is only a path, then the problem can be solved in polynomial time. When the robber moves in a tree, then the decision version of the problem is NP-complete. Furthermore, if the robber is moving in a DAG, the problem becomes PSPACE-complete.
Shantanu Das, Beat Gfeller, Peter Widmayer [DasGW:09] [published]
Computing Best Swaps in Optimal Tree Spanners
19th International Symposium on Algorithms and Computation (ISAAC), Surfers Paradise, 15-17 Dec 2008
In a densely connected communication network, represented by a graph G with nonnegative edge-weights, it is often advantageous to route all communication on a sparse, spanning subnetwork, typically a spanning tree of G. With the communication overhead in mind, we consider a spanning tree T of G which guarantees that for any two nodes, their distance in T is at most k times their distance in G, where k, called the stretch, is as small as possible. Such a spanning tree which minimizes the stretch is called an optimal tree spanner, and it can be used for efficient routing. However, for a communication tree, the failure of an edge is catastrophic; it disconnects the tree. Functionality can be restored by connecting both parts of the tree with another edge, while leaving the two parts themselves untouched. In situations where the failure can be repaired rapidly, such a quick fix is preferred over the recomputation of an entirely new optimal tree spanner, because it is much closer to the previous solution and hence requires far fewer adjustments in the routing scheme. We are therefore interested in the problem of finding for any possibly failing edge in the spanner T a best swap edge to replace it. The objective here is naturally to minimize the stretch of the new tree. We show how all these best swap edges can be computed in total time O(m^2 log n) in graphs with arbitrary nonnegative edge weights. For graphs with unit weight edges (also called unweighted graphs), we present an O(n^3) time algorithm. Furthermore, we present a distributed algorithm for computing the best swap for each edge in the spanner. [pdf]
Olga Goussevskaia, Michael Kuhn, Michael Lorenzi, and Roger Wattenhofer. [GoussevskaiaKLW:08] [published]
From Web to Map: Exploring the World of Music
IEEE/WIC/ACM International Conference on Web Intelligence (WI), Sydney, 9-12 Dec 08
Ever growing music collections ask for novel ways of organization. The traditional browsing of folder hierarchies or search by title and album tends to be insufficient to maintain an overview of a collection of orders of thousands of tracks. Methods based on song similarity offer an alternative to keyword-based search. In this work we propose to use a high-dimensional map of the “world of music” as a data structure for music retrieval and exploration of personal collections. Our approach does not require expensive analysis of audio signals and scales to hundreds of thousands of tracks. The techniques presented in this work can be used in a variety of applications, ranging from automatic DJs to file sharing on mobile devices. As a concrete example, we have developed a web-application that allows users to visualize and navigate through their music collections and create playlists by specifying trajectories. [pdf]
Christoph Lenzen, Thomas Locher, and Roger Wattenhofer. [LenzenLW:08] [published]
Clock Synchronization with Bounded Global and Local Skew
49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Philadelphia, 26-28 Oct 08.
We present a distributed clock synchronization algorithm that guarantees an exponentially improved bound of O(logD) on the clock skew between neighboring nodes in any graph G of diameter D. In light of the lower bound of (logD= log logD), this result is almost tight. Moreover, the global clock skew between any two nodes, particularly nodes that are not directly connected, is bounded by O(D), which is optimal up to a constant factor. Our algorithm further ensures that the clock values are always within a linear envelope of real time. A better bound on the accuracy with respect to real time cannot be achieved in the absence of an external timer. These results all hold in a general model where both the clock drifts and the message delays may vary arbitrarily within pre-specified bounds. [pdf]
Marco von Arb, Matthias Bader, Michael Kuhn, and Roger Wattenhofer. [ArbBKW:08] [published]
VENETA: Serverless Friend-of-Friend Detection in Mobile Social Networking
4th IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), Avignon, 12-14 Oct 08.
Recently, mobile social software has become an active area of research and development. A multitude of systems have been proposed over the past years that try to follow the success of their Internet bound equivalents. Many mobile solutions try to augment the functionality of existing platforms with location awareness. The price for mobility, however, is typically either the lack of the popular friendship exploration features or the costs involved to access a central server required for this functionality. In this paper, we try to address this issue by introducing a decentralized method that is able to explore the social neighborhood of a user by detecting friends of friends. Rather than only exploiting information about the users of the system, the method relies on real friends, and adequately addresses the arising privacy issues. Moreover, we present VENETA, a mobile social networking platform which, among other features, implements our novel friend of friend detection algorithm. [pdf]
Remo Meier and Roger Wattenhofer. [MeierW:08] [published]
ALPS: Authenticating Live Peer-to-Peer Streams
27th Annual IEEE International Symposium on Reliable Distributed Systems (SRDS), Naples, 6-8 Oct 08.
Christoph Lenzen and Roger Wattenhofer. [LenzenW:08] [published]
Leveraging Linial's Locality Limit
22nd International Symposium on Distributed Computing (DISC), Arcachon, 22-24 Sep 08.
In this paper we extend the lower bound technique by Linial for local coloring and maximal independent sets. We show that con- stant approximations to maximum independent sets on a ring require at least log-star time. More generally, the product of approximation qual- ity and running time cannot be less than log-star. Using a generalized ring topology, we gain identical lower bounds for approximations to min- imum dominating sets. Since our generalized ring topology is contained in a number of geometric graphs such as the unit disk graph, our bounds directly apply as lower bounds for quite a few algorithmic problems in wireless networking. Having in mind these and other results about local approximations of maximum independent sets and minimum dominating sets, one might think that the former are always at least as difficult to obtain as the lat- ter. Conversely, we show that graphs exist, where a maximum indepen- dent set can be determined without any communication, while finding even an approximation to a minimum dominating set is as hard as in general graphs. [pdf]
Olga Goussevskaia, Michael Kuhn, and Roger Wattenhofer. [GoussevskaiaKW:09] [published]
Exploring Music Collections on Mobile Devices
International Conference on Human-Computer Interaction with Mobile Devices and Services (MobileHCI), Amsterdam, 22-25 Sep 08
Ever larger collections of music are stored on mobile de- vices. The process of managing these repositories therefore becomes increasingly challenging. In this work we propose to use a map of the \world of music" as a data structure for music exploration and retrieval on mobile devices. We present Mobile Music Explorer|a mobile application, which allows users to create playlists by specifying trajectories on the map and to use similarity based search methods to nav- igate through their personal music collections. Our navi- gation methods ensure that any part of the collection can quickly be reached, even for a large set of items. Moreover, we show that the map representation is a natural approach to provide ecient and distributed operation. [pdf]
Fabian Kuhn, Thomas Locher, and Roger Wattenhofer [KuhnLW:08] [published]
Distributed Selection: A Missing Piece of Data Aggregation
Communications of the ACM, Volume 51, Number 9, September 2008
In this article, we study the problem of distributed selection from a theoretical point of view. Given a general connected graph of diameter D consisting of n nodes in which each node holds a numeric element, the goal of a k-selection algorithm is to determine the kth smallest of these elements. We prove that distributed selection indeed requires more work than other aggregation functions such as, e.g., the computation of the average or the maximum of all elements. On the other hand, we show that the kth smallest element can be computed efficiently by providing both a randomized and a deterministic k-selection algorithm, dispelling the misconception that solving distributed selection through in-network aggregation is infeasible. [pdf]
Yvonne-Anne Oswald, Stefan Schmid and Roger Wattenhofer [OswaldSW:08] [published]
Tight Bounds for Delay Sensitive Aggregation
27th Annual Symposium on Principles of Distributed Computing (PODC); Toronto, Canada, 18-21 August 2008
Johannes Schneider and Roger Wattenhofer. [SchneiderW:08] [published]
A Log-Star Distributed Maximal Independent Set Algorithm for Growth-Bounded Graphs
27th ACM Symposium on Principles of Distributed Computing (PODC), Toronto, 18-21 Aug 08.
We present a novel distributed algorithm for the maximal independent set (MIS) problem. On growth-bounded graphs (GBG) our deterministic algorithm finishes in O(log* n) time, n being the number of nodes. In light of Linial’s (log* n) lower bound our algorithm is asymptotically optimal. Our algorithm answers prominent open problems in the ad hoc/sensor network domain. For instance, it solves the connected dominating set problem for unit disk graphs in O(log* n) time, exponentially faster than the state-of-the-art algorithm. With a new extension our algorithm also computes a D + 1 coloring in O(log^D n) time, where D is the maximum degree of the graph. [pdf]
Yvonne Anne Oswald, Stefan Schmid, and Roger Wattenhofer. [OswaldSW:08] [published]
Tight Bounds for Delay-Sensitive Aggregation
27th ACM Symposium on Principles of Distributed Computing (PODC), Toronto, 18-21 Aug 08.
This paper studies the fundamental trade-off between communication cost and delay cost arising in various contexts such as control message aggregation or organization theory. An optimization problem is considered where nodes are organized in a tree topology. The nodes seek to minimize the time until the root is informed about their states and to use as few transmissions as possible at the same time. We derive an upper bound on the competitive ratio of O(min(h; c)) where h is the tree’s height, and c is the transmission cost per edge. Moreover, we prove that this upper bound is tight in the sense that any oblivious algorithm has a ratio of at least (min(h; c)). For chain networks, we prove a tight competitive ratio of Theta(min(h^(1/2); c)). Furthermore, the paper introduces a new model for online event aggregation where the importance of an event depends on its difference to previous events. [pdf]
Olga Goussevskaia, Thomas Moscibroda, and Roger Wattenhofer. [GoussevskaiaMW:08] [published]
Local Broadcasting in the Physical Interference Model
ACM SIGACT-SIGOPT International Workshop on Foundations of Mobile Computing (DialM-POMC), Toronto, August 2008.
In this work we analyze the complexity of local broadcasting in the physical interference model. We present two distributed randomized algorithms: one that assumes that each node knows how many nodes there are in its geographical proximity, and another, which makes no assumptions about topology knowledge. We show that, if the transmission probability of each node meets certain characteristics, the analysis can be decoupled from the global nature of the physical interference model, and each node performs a successful local broadcast in time proportional to the number of neighbors in its physical proximity. We also provide worst-case optimality guarantees for both algorithms and demonstrate their behavior in average scenarios through simulations. [pdf]
Jan Brunner, Matus Mihalak, Subhash Suri, Elias Vicari, Peter Widmayer [BrunnerMSVW:08] [published]
Simple Robots in Polygonal Environments: A Hierarchy
Algorithmic Aspects of Wireless Sensor Networks (Algosensors 08), Reykjavik, 12 July 08
With the current progress in robot technology and related areas, sophisticated moving and sensing capabilities are at hand to design robots capable of solving seemingly complex tasks. With the aim of understanding the limitations of such capabilities, swarms of simple and cheap robots play an increasingly important role. Their advantages are, among others, the cost, reusability, and fault-tolerance. While it can be expected that for a variety of problems a wealth of robot models are proposed, it is rather unfortunate that almost all proposals fail to point out their assumptions explicitly and clearly. This is problematic because small looking changes in the models can lead to significant differences in the capabilities of the robots. Hence, a clean assessment of the "power of robot models" is dearly needed, not only in absolute terms, but also relative to each other. We make a step in this direction by explaining for a set of elementary sensing devices which of these devices (alone and in combination) enable a robot to solve which problems. This not only leads to a natural relation (and hierarchy) of power between robot models that supports a more systematic design, but also exhibits surprising connections and equivalences. For example, one of the derived relations between the robot models implies that a very simple robot (that cannot measure distances) moving inside a simple polygon can find a shortest path between two vertices by means of a sensor that detects for an angle at a vertex of the polygon whether it is convex. We give an explicit algorithm which allows the robot to find a shortest path. To do so we explore (new) structural properties of shortest paths in polygons.
Dominic Meier, Yvonne Anne Oswald, Stefan Schmid, Roger Wattenhofer [MeierOSW:08] [published]
On the Windfall of Friendship: Inoculation Strategies on Social Networks
9th ACM Conference on Electronic Commerce (EC), Chicago, 8-12 Jul 08
This paper studies a virus inoculation game on social net- works. A framework is presented which allows the mea- suring of the windfall of friendship, i.e., how much players benefit if they care about the welfare of their direct neigh- bors in the social network graph compared to purely selfish environments. We analyze the corresponding equilibria and show that the computation of the worst and best Nash equi- librium is NP-hard. Intriguingly, even though the windfall of friendship can never be negative, the social welfare does not increase monotonically with the extent to which play- ers care for each other. While these phenomena are known on an anecdotal level, our framework allows us to quantify these effects analytically. [pdf]
Beat Gfeller, Matúš Mihalák, Subhash Suri, Elias Vicari, Peter Widmayer [GfellerMSVW:08] [published]
Angle Optimization in Target Tracking
11th Scandinavian Workshop on Algorithm Theory (SWAT), pages 65-76, Gothenburg, 2-4 July 08
We consider the problem of tracking $n$ targets in the plane using $2n$ cameras, where tracking each target requires two distinct cameras. A single camera (modeled as a point) sees a target point in a certain direction, ideally with unlimited precision, and thus two cameras (not collinear with the target) unambiguously determine the position of the target. In reality, due to the inevitable imprecision in the camera equipment and construction, instead of a single viewing direction a target defines only a viewing cone, and so two cameras localize a target only within the intersection of two such cones. In general, the true localization error is a complicated function of the angle subtended by the two cameras at the target (the tracking angle), but a commonly accepted tenet is that an angle of $90^\circ$ is close to the ideal. In this paper, we consider several algorithmic problems related to this so-called ``focus of attention'' problem. In particular, we show that the problem of deciding whether each of $n$ given targets can be tracked with $90^\circ$ is NP-complete. For the special case where the cameras are placed along a single line while the targets are located anywhere in the plane, we show a 2-approximation both for the sum of tracking angles and the bottleneck tracking angle (i.e., the smallest tracking angle) maximization problems (which is a natural goal whenever targets and cameras are far from each other). Lastly, for the uniform placement of cameras along the line, we further improve the result to a PTAS. [pdf]
Bernard Mans, Stefan Schmid, and Roger Wattenhofer. [MansSW:08] [published]
Distributed Disaster Disclosure
11th Scandinavian Workshop on Algorithm Theory (SWAT), Gothenburg, 2-4 July 2008.
Assume a set of distributed nodes which are equipped with a sensor device. When nodes sense an event, they want to know (the size of) the connected component consisting of nodes which have also sensed the event, in order to raise—if necessary—a disaster alarm. This paper presents distributed algorithms for this problem. Concretely, our algorithms aim at minimizing both the response time as well as the message complexity. [pdf]
Subhash Suri, Elias Vicari, Peter Widmayer [SuriVW:08] [published]
Simple Robots with Minimal Sensing: From Local Visibility to Global Geometry
International Journal of Robotics Research, Vol. 27, No. 9, pages 1055-1067
We consider problems of geometric exploration and self-deployment for simple robots that can only sense the combinatorial (non-metric) features of their surroundings. Even with such a limited sensing, we show that robots can achieve complex geometric reasoning and perform many non-trivial tasks. Specifically, we show that one robot equipped with a single pebble can decide whether the workspace environment is a simply-connected polygon and, if not, it can also count the number of holes in the environment. Highlighting the subtleties of our sensing model, we show that a robot can decide whether the environment is a convex polygon, yet it cannot resolve whether a given vertex is convex. Finally, we show that using such local and minimal sensing, a robot can compute a proper triangulation of a polygon, and that the triangulation algorithm can be implemented collaboratively by a group of $m$ such robots, each with $\Theta (n/m)$ word memory. As a corollary of the triangulation algorithm, we derive a distributed analog of the well-known Art Gallery Theorem: a group of $\lfloor n/3 \rfloor$ (bounded memory) robots in our minimal sensing model can self-deploy to achieve visibility coverage of an $n$-vertex art gallery (polygon). This resolves an open question raised recently by Ganguli et al.
Jan Kostka, Yvonne Anne Oswald, Roger Wattenhofer [KostkaOW:08] [published]
Word of Mouth: Rumor Dissemination in Social Networks
15th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Villars-sur-Ollon, 17-20 June 08
In this paper we examine the diffusion of competing rumors in social networks. Two players select a disjoint subset of nodes as ini- tiators of the rumor propagation, seeking to maximize the number of persuaded nodes. We use concepts of game theory and location theory and model the selection of starting nodes for the rumors as a strategic game. We show that computing the optimal strategy for both the first and the second player is NP-complete, even in a most restricted model. Moreover we prove that determining an approximate solution for the first player is NP-complete as well. We analyze several heuristics and show that—counter-intuitively—being the first to decide is not always an advantage, namely there exist networks where the second player can convince more nodes than the first, regardless of the first player’s deci- sion. [pdf]
Christoph Lenzen, Yvonne Anne Oswald, Roger Wattenhofer [LenzenOW:08] [published]
What can be approximated locally?
20th ACM Symposium on Parallelism in Algorithms and Architecture (SPAA), Munich, 14-16 June 08
Whether local algorithms can compute constant approximations of NP-hard problems is of both practical and theoretical interest. So far, no algorithms achieving this goal are known, as either the approximation ratio or the running time exceed O(1), or the nodes are provided with non-trivial additional information. In this paper, we present the first distributed algorithm approximating a minimum dominating set on a planar graph within a constant factor in constant time. Moreover, the nodes do not need any additional information. [pdf]
Pascal von Rickenbach and Roger Wattenhofer [RickenbachW:08] [published]
Decoding Code on a Sensor Node
4th IEEE/ACM International Conference on Distributed Computing in Sensor Systems (DCOSS'08), Santorini, 11-14 June 08
Roland Flury, Roger Wattenhofer [FluryW:08] [published]
Randomized 3D Geographic Routing
IEEE Infocom 2008, Phoenix, 15-17 Apr 08
Philipp Sommer, Roger Wattenhofer [SommerW:08] [published]
Symmetric Clock Synchronization in Sensor Networks
3rd ACM Workshop on Real-World Wireless Sensor Networks (REALWSN'08), Glasgow, 1 Apr 08
Dorothea Wagner, Roger Wattenhofer (Eds.) [WagnerW:07] [published]
Algorithms for Sensor and Ad Hoc Networks
Lecture Notes in Computer Science , Vol. 4621, 2007
Raphael Eidenbenz, Yvonne Anne Oswald, Stefan Schmid, and Roger Wattenhofer [EidenbenzOSW:07] [published]
Manipulation in Games
18th International Symposium on Algorithms and Computation (ISAAC), Sendai, 17-19 Dec 07
This paper studies to which extent the social welfare of a game can be in uenced by an interested third party within economic rea- son, i.e., by taking the implementation cost into account. Besides consid- ering classic, benevolent mechanism designers, we also analyze malicious mechanism designers. For instance, this paper shows that a malicious mechanism designer can often corrupt games and worsen the players' situation to a larger extent than the amount of money invested. Surpris- ingly, no money is needed at all in some cases. We provide algorithms for nding the so-called leverage in games and show that for optimistic mechanism designers, computing the leverage or approximations thereof is NP-hard. [pdf]
Thomas Locher, Remo Meier, Stefan Schmid, and Roger Wattenhofer [LocherMSW:07] [published]
Push-to-Pull Peer-to-Peer Live Streaming
21st International Symposium on Distributed Computing (DISC), Lemesos, 24-26 Sep 07
In contrast to peer-to-peer file sharing, live streaming based on peer-to-peer technology is still awaiting its breakthrough. This may be due to the additional challenges live streaming faces, e.g., the need to meet real-time playback deadlines, or the increased demands on robustness under churn. This paper presents and evaluates novel neighbor selection and data distribution schemes for peer-to-peer live streaming. Concretely, in order to distribute data efficiently and with minimal delay, our algorithms combine low-latency push operations along a structured overlay with the flexibility of pull operations. The protocols ensure that all peers are able to obtain the required data blocks of a live stream in time, and that due to the loop-free dissemination paths, the overhead is low. [pdf]
Olga Goussevskaia, Yvonne Anne Oswald, and Roger Wattenhofer. [GoussevskaiaOW:07] [published]
Complexity in Geometric SINR
MobiHoc 2007, Montreal, 9-14 Sep 07
In this paper we study the problem of scheduling wireless links in the geometric SINR model, which explicitly uses the fact that nodes are distributed in the Euclidean plane. We present the first NP-completeness proofs in such a model. In particular, we prove two problems to be NP-complete: Scheduling and One-Shot Scheduling. The first problem consists in finding a minimum-length schedule for a given set of links. The second problem receives a weighted set of links as input and consists in finding a maximum-weight subset of links to be scheduled simultaneously in one shot. In addition to the complexity proofs, we devise an approximation algorithm for each problem. [pdf]
Thomas Locher, Stefan Schmid, and Roger Wattenhofer. [LocherSW:07] [published]
Rescuing Tit-for-Tat with Source Coding
7th IEEE International Conference on Peer-to-Peer Computing (P2P), Galway, 2-5 Sep 07
Tit-for-tat is widely believed to be the most effective strategy to enforce collaboration among selfish users. However, it has been shown that its usefulness for decentralized and dynamic environments such as peer-topeer networks is marginal, as peers can rapidly end up in a deadlock situation. Many proposed solutions to this problem are either less resilient to freeloading behavior or induce a computational overhead that cannot be sustained by regular peers. In contrast, we retain tit-fortat, but enhance the system with a novel form of source coding and an effective scheme to prevent peers from freeloading from seeding peers. We show that our system performs well without the risk of peer starvation and without sacrificing fairness. The proposed solution has a reasonably low overhead, and may hence be suitable for fully distributed content distribution applications in real networks. [pdf]
Raphael Eidenbenz, Yvonne Anne Oswald, Stefan Schmid, and Roger Wattenhofer [EidenbenzOSW:07] [published]
Mechanism Design by Creditability
First International Conference on Combinatorial Optimization and Applications (COCOA), Xi'an, 12-15 Aug 07
Subhash Suri, Elias Vicari, Peter Widmayer [SuriVW:07b] [published]
Simple Robots with Minimal Sensing: From Local Visibility to Global Geometry
22nd Second Conference on Artificial Intelligence (AAAI), Vancouver, 22-25 July 07
We consider problems of geometric exploration and self-deployment for simple robots that can only sense the combinatorial (non-metric) features of their surroundings. Even with such a limited sensing, we show that robots can achieve complex geometric reasoning and perform many non-trivial tasks. Specifically, we show that one robot equipped with a single pebble can decide whether the workspace environment is a simply-connected polygon and, if not, it can also count the number of holes in the environment. Highlighting the subtleties of our sensing model, we show that a robot can decide whether the environment is a convex polygon, yet it cannot resolve whether a particular vertex is convex. Finally, we show that using such local and minimal sensing, a robot can compute a proper triangulation of a polygon, and that the triangulation algorithm can be implemented collaboratively by a group of $m$ such robots, each with $\Theta (n/m)$ memory. As a corollary of the triangulation algorithm, we derive a distributed analog of the well-known Art Gallery Theorem: a group of $\lfloor n/3 \rfloor$ (bounded memory) robots in our minimal sensing model can self-deploy to achieve visibility coverage of an $n$-vertex art gallery (polygon). This resolves an open question raised recently by Ganguli et al. [pdf]
Beat Gfeller, Matus Mihalak, Subhash Suri, Elias Vicari, Peter Widmayer [GfellerMSVW:07] [published]
Counting Targets with Mobile Sensors in an Unknown Environment
3rd International Workshop on Algorithmic Aspects of Wireless Sensor Networks (AlgoSensors 2007), Wroclaw, 14 July 07
We consider the problem of counting the number of indistinguishable targets using a simple binary sensing model. Our setting includes an unknown number of point targets in a (simple or multiply-connected) polygonal workspace, and a moving point-robot whose sensory input at any location is a binary vector representing the cyclic order of the polygon vertices and targets visible to the robot. In particular, the sensing model provides no coordinates, distance or angle measurements. We investigate this problem under two natural models of environment, friendly and hostile, which differ only in whether the robot can walk up to them or not, and under three different models of motion capability. In the friendly scenario we show that the robots can count the targets, whereas in the hostile scenario no $(2-\varepsilon)$-approximation is possible, for any $\varepsilon>0$. Next we consider two, possibly minimally more powerful robots that can count the targets exactly. [pdf]
Fabian Kuhn, Thomas Locher, and Roger Wattenhofer [KuhnLW:07] [published]
Tight Bounds for Distributed Selection
19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Diego, 9-11 June 07
Thomas Moscibroda, Yvonne Anne Oswald, and Roger Wattenhofer [MoscibrodaOW:07] [published]
How Optimal are Wireless Scheduling Protocols
Infocom 2007, Anchorage, 6-12 May 07
Roland Flury and Roger Wattenhofer [FluryW:07] [published]
Routing, Anycast, and Multicast for Mesh and Sensor Networks
Infocom 2007, Anchorage, 6-12 May 07
Nicolas Burri, Pascal von Rickenbach, and Roger Wattenhofer [BurriRW:07] [published]
Dozer: Ultra-Low Power Data Gathering in Sensor Networks
International Conference on Information Processing in Sensor Networks (IPSN), Cambridge, 25-27 Apr 07
Subhash Suri, Elias Vicari, Peter Widmayer [SuriVW:07] [published]
Simple Robots with Minimal Sensing: From Local Visibility to Global Geometry
ETHZ Technical Report 547, Feb 07
We consider problems of geometric exploration and self-deployment for simple robots that can only sense the combinatorial (non-metric) features of their surroundings. Even with such a limited sensing, we show that robots can achieve complex geometric reasoning and perform many non-trivial tasks. Specifically, we show that one robot equipped with a single pebble can decide whether the workspace environment is a simply-connected polygon or not; with sufficiently many pebbles, it can also count the number of holes in the environment. Highlighting the subtleties of our sensing model, we show that a robot can decide whether the environment is a convex polygon, yet it cannot resolve whether a particular vertex is convex. Finally, we show that using such local and minimal sensing, a robot can compute a proper triangulation of a polygon, and that the triangulation algorithm can be implemented collaboratively by a group of $m$ such robots, each with $\Theta (n/m)$ memory. As a corollary of the triangulation algorithm, we derive a distributed analog of the well-known Art Gallery Theorem: a group of $\lfloor n/3 \rfloor$ (bounded memory) robots in our minimal sensing model can self-deploy to achieve visibility coverage of an $n$-vertex art gallery (polygon). This resolves an open question raised recently by Ganguli et al (2006). [pdf]
Gabor Cselle, Keno Albrecht, and Roger Wattenhofer [CselleAW:07] [published]
BuzzTrack: Topic Detection and Tracking in Email
International Conference on Intelligent User Interfaces (IUI), Honolulu, 28-31 Jan 07
Stefan Schmid and Roger Wattenhofer [SchmidW:06c] [published]
Dynamic Internet Congestion with Bursts
13th Annual IEEE International Conference on High Performance Computing (HiPC), Bangalore, 18-21 Dec 06
Nicolas Burri, Pascal von Rickenbach, Roger Wattenhofer, and Yves Weber [BurriRWW:06] [published]
Topology Control Made Practical: Increasing the Performance of Source Routing
2nd International Conference on Mobile Ad-hoc and Sensor Networks (MSN), Hong Kong, 13-15 Dec 06
Thomas Moscibroda, Roger Wattenhofer, and Yves Weber [MoscibrodaWW:06] [published]
Protocol Design Beyond Graph-Based Models
5th Workshop on Hot Topics in Networks (HotNets), Irvine, 29-30 Nov 06
Michael Kuhn and Roger Wattenhofer [KuhnW:06b] [published]
Community-Aware Mobile Networking
1st Workshop on Mobile Services and Personalized Environments (MSPE), Aachen, 16-17 Nov 06
Thomas Locher, Stefan Schmid, and Roger Wattenhofer [LocherSW:06] [published]
eQuus: A Provably Robust and Locality-Aware Peer-to-Peer System
6th IEEE International Conference on Peer-to-Peer Computing (P2P), Cambridge, 2-4 Oct 06
Dominik Grolimund, Luzius Meisser, Stefan Schmid, and Roger Wattenhofer [GrolimundMSW:06] [published]
Cryptree: A Folder Tree Structure for Cryptographic File Systems
25th IEEE Symposium on Reliable Distributed Systems (SRDS), Leeds, 2-4 Oct 06
Thomas Locher and Roger Wattenhofer [LocherW:06] [published]
Oblivious Gradient Clock Synchronization
20th International Symposium on Distributed Computing (DISC), Stockholm, 18-20 Sep 06
Stefan Schmid and Roger Wattenhofer [SchmidW:06b] [published]
A TCP with Guaranteed Performance in Networks with Dynamic Congestion and Random Wireless Losses
2nd Annual International Wireless Internet Conference (WICON), Boston, 2-5 Aug 06
Fabian Kuhn and Roger Wattenhofer [KuhnW:06] [published]
On the Complexity of Distributed Graph Coloring
25th Annual Symposium on Principles of Distributed Computing (PODC), Denver, 23-26 July 06
Thomas Moscibroda, Stefan Schmid, and Roger Wattenhofer [MoscibrodaSW:06b] [published]
When Selfish Meets Evil: Byzantine Players in a Virus Inoculation Game
25th Annual Symposium on Principles of Distributed Computing (PODC), Denver, 23-26 July 06
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer [KuhnMW:06b] [published]
Fault-Tolerant Clustering in Ad Hoc and Sensor Networks
26th International Conference on Distributed Computing Systems (ICDCS), Lisboa, 4-7 July 2006
Fabian Kuhn, Stefan Schmid, Joest Smit, and Roger Wattenhofer [KuhnSSW:06] [published]
A Blueprint for Constructing Peer-to-Peer Systems Robust to Dynamic Worst-Case Joins and Leaves
14th IEEE International Workshop on Quality of Service (IWQoS), Yale University, 19-21 June 06
Nicolas Burri, Roland Schuler, and Roger Wattenhofer [BurriSW:06] [published]
YETI: A TinyOS Plug-in for Eclipse
ACM Workshop on Real-World Wireless Sensor Networks (REALWSN), Uppsala, 19 June 06
Thomas Moscibroda, Roger Wattenhofer, Aaron Zollinger [MoscibrodaWZ:06] [published]
Topology Control Meets SINR: The Scheduling Complexity of Arbitrary Topologies
7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Florence, 22-25 May 2006
Roland Flury, Roger Wattenhofer [FluryW:06] [published]
MLS: An Efficient Location Service for Mobile Ad Hoc Networks
7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Florence, 22-25 May 2006
Stefan Schmid and Roger Wattenhofer [SchmidW:06] [published]
Algorithmic Models for Sensor Networks
14th International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS), Rhodes, 25-26 Apr 06
Developing algorithms for sensor networks—and proving their correctness and performance—, requires simplifying but still realistic models. This paper surveys various models in use today and puts them into perspective. In addition, we propose interesting models which are not widely adopted by the community so far. [pdf]
Thomas Moscibroda, Pascal von Rickenbach, Roger Wattenhofer [MoscibrodaRW:06] [published]
Analyzing the Energy-Latency Trade-off during the Deployment of Sensor Networks
IEEE Infocom 2006, Barcelona, 23-29 Apr 06
The inherent trade-off between energy-efficiency and rapidity of event dissemination is characteristic for wireless sensor networks. Scarcity of energy renders it necessary for nodes to spend a large portion of their lifetime in an energyefficient sleep mode during which they do neither receive nor send messages. On the other hand, the longer nodes stay in sleep mode, the slower will be the reaction time for disseminating an external event. The trade-off is prominently exhibited during the deployment phase of sensor networks, if some nodes are deployed earlier than others. In this paper, we study this fundamental trade-off by giving a formal model that enables us to compare the performance of different protocols and algorithms. Based on this model, we propose, analyze, and simulate two novel algorithms which significantly outperform existing solutions. [pdf]
Thomas Moscibroda, Roger Wattenhofer [MoscibrodaW:06] [published]
The Complexity of Connectivity in Wireless Networks
IEEE Infocom 2006, Barcelona, 23-29 Apr 06
We define and study the scheduling complexity in wireless networks, which expresses the theoretically achievable efficiency of MAC layer protocols. Given a set of communication requests in arbitrary networks, the scheduling complexity describes the amount of time required to successfully schedule all requests. The most basic and important network structure in wireless networks being connectivity, we study the scheduling complexity of connectivity, i.e., the minimal amount of time required until a connected structure can be scheduled. In this paper, we prove that the scheduling complexity of connectivity grows only polylogarithmically in the number of nodes. Specifically, we present a novel scheduling algorithm that successfully schedules a strongly connected set of links in time O(log4n) even in arbitrary worst-case networks. On the other hand, we prove that standard MAC layer or scheduling protocols can perform much worse. Particularly, any protocol that either employs uniform or linear (a node’s transmit power is proportional to the minimum power required to reach its intended receiver) power assignment has a (n) scheduling complexity in the worst case, even for simple communication requests. In contrast, our polylogarithmic scheduling algorithm allows many concurrent transmission by using an explicitly formulated non-linear power assignment scheme. Our results show that even in large-scale worst-case networks, there is no theoretical scalability problem when it comes to scheduling transmission requests, thus giving an interesting complement to the more pessimistic bounds for the capacity in wireless networks. All results are based on the physical model of communication, which takes into account that the signal-tonoise plus interference ratio (SINR) at a receiver must be above a certain threshold if the transmission is to be received correctly. [pdf]
Thomas Moscibroda, Stefan Schmid, and Roger Wattenhofer [MoscibrodaSW:06] [published]
On the Topologies Formed by Selfish Peers
5th International Workshop on Peer-to-Peer Systems (IPTPS), Santa Barbara, 27-28 Feb 06
Current peer-to-peer (P2P) systems often suffer from a large fraction of freeriders not contributing any resources to the network. Various mechanisms have been designed to overcome this problem. However, the selfish behavior of peers has aspects which go beyond resource sharing. This paper studies the effects on the topology of a P2P network if peers selfishly select the peers to connect to. In our model, a peer exploits locality properties in order to minimize the latency (or response times) of its lookup operations. At the same time, the peer aims at not having to maintain links to too many other peers in the system. We show that the resulting topologies can be much worse than if peers collaborated. Moreover, the network may never stabilize, even in the absence of churn. [pdf]
Cristescu, Razvan; Beferull-Lozano, Baltasar; Vetterli, Martin; Wattenhofer, R. [CristescuBVW:06] [published]
Network Correlated Data Gathering with Explicit Communication: NP-Completeness and Algorithms
IEEE/ACM Trans. on Networking, vol. 14, no 1, p. 41-54
Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer [KuhnMW:06] [published]
The Price of Being Near-Sighted
17th ACM-SIAM Symposium on Discrete Algorithms (SODA), Miami, 22-24 Jan 06
Achieving a global goal based on local information is challenging, especially in complex and large-scale networks such as the Internet or even the human brain. In this paper, we provide an almost tight classification of the possible tradeoff between the amount of local information and the quality of the global solution for general covering and packing problems. Specifically, we give a distributed algorithm using only small messages which obtains an (½¢)1/k-approximation for general covering and packing problems in time O(k2), where ½ depends on the LP’s coefficients. If message size is unbounded, we present a second algorithm that achieves an O(n1/k) approximation in O(k) rounds. Finally, we prove that these algorithms are close to optimal by giving a lower bound on the approximability of packing problems given that each node has to base its decision on information from its k-neighborhood. [pdf]
Regina O'Dell and Roger Wattenhofer [O'DellW:05b] [published]
Theoretical aspects of connectivity-based multi-hop positioning
Theoretical Computer Science 344:1, Nov 05
We investigate the theoretical limits of positioning algorithms. In particular, we study scenarios where the nodes do not receive anchors directly (multi-hop) and where no physical distance or angle information whatsoever is available (connectivity-based). Since we envision large-scale sensor networks as an application, we are interested in fast, distributed algorithms. As such, we show that plain hop algorithms are not competitive. Instead, for one-dimensional unit disk graphs we present an optimal algorithm HS. For two or more dimensions, we propose an algorithm GHOST which improves upon the basic hop algorithm in theory and in simulations. [pdf]
Fabian Kuhn, Thomas Moscibroda, Tim Nieberg, and Roger Wattenhofer [KuhnMNW:05] [published]
Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs
19th International Symposium on Distributed Computing (DISC'05), Cracow, 26-29 Sep 05
The distributed complexity of computing a maximal independent set in a graph is of both practical and theoretical importance. While there exists an elegant O(log n) time randomized algorithm for general graphs [20], no deterministic polylogarithmic algorithm is known. In this paper, we study the problem in graphs with bounded growth, an important family of graphs which includes the well-known unit disk graph and many variants thereof. Particularly, we propose a deterministic algorithm that computes a maximal independent set in time O(log¢¢log¤n) in graphs with bounded growth, where n and ¢ denote the number of nodes and the maximal degree in G, respectively. [pdf]
Regina O'Dell and Roger Wattenhofer [O'DellW:05c] [published]
Information Dissemination in Highly Dynamic Graphs
3rd ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Cologne, 2 Sep 05
We investigate to what extent flooding and routing is possible if the graph is allowed to change unpredictably at each time step. We study what minimal requirements are necessary so that a node may correctly flood or route a message in a network whose links may change arbitrarily at any given point, subject to the condition that the underlying graph is connected. We look at algorithmic constraints such as limited storage, no knowledge of an upper bound on the number of nodes, and no usage of identifiers. We look at flooding as well as routing to some existing specified destination and give algorithms. [pdf]
Thomas Moscibroda and Roger Wattenhofer [MoscibrodaW:05e] [published]
Minimizing Interference in Ad Hoc and Sensor Networks
3rd ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Cologne, 2 Sep 05
Reducing interference is one of the main challenges in wire- less communication, and particularly in ad hoc networks. The amount of interference experienced by a node v cor- responds to the number of other nodes whose transmis- sion range covers v. At the cost of communication links being dropped, interference can be reduced by decreasing the node's transmission power. In this paper, we study the problem of minimizing the average interference while still maintaining desired network properties, such as connectiv- ity, point-to-point connections, or multicast trees. In par- ticular, we present a greedy algorithm that computes an O(log n) approximation to the interference problem with connectivity requirement, where n is the number of nodes in the network. We then show the algorithm to be asymp- totically optimal by proving a corresponding (log n) lower bound that holds even in a more restricted interference model. Finally, we show how the algorithm can be generalized to- wards solving the interference problem for network proper- ties that can be formulated as a 0-1 proper function. [pdf]
Fabian Kuhn, Thomas Moscibroda, Tim Nieberg, and Roger Wattenhofer [KuhnMNW:05b] [published]
Local Approximation Schemes for Ad Hoc and Sensor Networks
3rd ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Cologne, 2 Sep 05
We present two local approaches that yield polynomial-time approximation schemes (PTAS) for the Maximum Indepen- dent Set and Minimum Dominating Set problem in unit disk graphs. The algorithms run locally in each node and com- pute a (1 + ")-approximation to the problems at hand for any given " > 0. The time complexity of both algorithms is O(TMIS + log¤n="O(1)), where TMIS is the time required to compute a maximal independent set in the graph, and n de- notes the number of nodes. We then extend these results to a more general class of graphs in which the maximum num- ber of pair-wise independent nodes in every r-neighborhood is at most polynomial in r. Such graphs of polynomially bounded growth are introduced as a more realistic model for wireless networks and they generalize existing models, such as unit disk graphs or coverage area graphs. [pdf]
Fabian Kuhn, Pascal von Rickenbach, Roger Wattenhofer, Emo Welzl, Aaron Zollinger [KuhnRWWZ:05] [published]
Interference in Cellular Networks: The Minimum Membership Set Cover Problem
11th International Computing and Combinatorics Conference (COCOON), Kunming, 16-19 August 05
The infrastructure for mobile distributed tasks is often formed by cellular networks. One of the major issues in such networks is interference. In this paper we tackle interference reduction by suitable assignment of transmission power levels to base stations. This task is formalized introducing the Minimum Membership Set Cover combinatorial optimization problem. On the one hand we prove that in polynomial time the optimal solution of the problem cannot be approximated more closely than with a factor ln n. On the other hand we present an algorithm exploiting linear programming relaxation techniques which asymptotically matches this lower bound. [pdf] [ps]
Roger Wattenhofer [Wattenhofer:05] [published]
Algorithms for ad hoc and sensor networks
Elsevier Journal on Computer Communications, Volume 28, Issue 13, August 2005
Wireless and mobiles networks are excellent playground for researchers with an algorithm background. Many research problem turn out to be variants of classic graph theory problems. In particular the rapidly growing areas for ad hoc and sensor networks demand new solutions for timeless graph theory problems, because: (i) wireless devices have lower bandwidth and (ii) wireless devices are mobile and therefore the topology of the network changes rather frequently. As a consequences, algorithms for wireless and mobile networks should have: (i) as little communication as possible and should (ii) run as fast as possible. Both goals can only be achieved by developing algorithms requiring a small number of communication rounds only (so-called local algorithm). In the work we present a few algorithmic applications in wireless networking, such as clustering, topology control and geo-routing. Each section is supplemented with an open problem. [pdf]
Fabian Kuhn, Thomas Moscibroda and Roger Wattenhofer [KuhnMW:05] [published]
On the Locality of Bounded Growth
24th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2005), Las Vegas, 17-20 July 05
Many large-scale networks such as ad hoc and sensor networks, peer-to-peer networks, or the Internet have the property that the number of independent nodes does not grow arbitrarily when looking at neighborhoods of increasing size. Due to this bounded volume growth, one could expect that distributed algorithms are able to solve many problems more e±ciently than on general graphs. The goal of this paper is to help understanding the distributed complexity of problems on bounded growth graphs. We show that on the widely used unit disk graph, covering and packing linear programs can be approximated by constant factors in constant time. For a more general network model which is based on the assumption that nodes are in a metric space of constant doubling dimension, we show that in O(log^* n) rounds it is possible to construct a (O(1),O(1))-network decomposition. This results in asymptotically optimal O(log^* n) time algorithms for many important problems. [pdf] [ps]
Thomas Moscibroda, Roger Wattenhofer [MoscibrodaW:05] [published]
Facility Location: Distributed Approximation
24th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2005), Las Vegas, 17-20 July 05
In this paper, we initiate the study of the approximability of the facility location problem in a distributed setting. In particular, we explore a trade-o® between the amount of communication and the resulting approximation ratio. We give a distributed algorithm that, for every constant k, achieves an O(sqrt(k)(m rho)^(1/sqrt(k)) log(m + n)) approximation in O(k) communication rounds where message size is bounded to O(log n) bits. The number of facilities and clients are m and n, respectively, and rho is a coefficient that depends on the cost values of the instance. Our technique is based on a distributed primal-dual approach for approximating a linear program, that does not form a covering or packing program. [pdf] [ps]
Thomas Moscibroda, Roger Wattenhofer [MoscibrodaW:05b] [published]
Maximal Independent Sets in Radio Networks
24th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2005), Las Vegas, 17-20 July 05
We study the distributed complexity of computing a maximal independent set (MIS) in radio networks with completely unknown topology, asynchronous wake-up, and no collision detection mechanism available. Specifically, we propose a novel randomized algorithm that computes a MIS in time O((log n)^2) with high probability, where n is the number of nodes in the network. This significantly improving on the best previously known solutions. A lower bound of Omega((log n)^2/(log log n)) given in [11] implies that our algorithm's running time is close to optimal. Our result shows that the harsh radio network model imposes merely an additional O(log n) factor compared to Luby's MIS algorithm in the message passing model. This has important implications in the context of ad hoc and sensor networks whose charac- teristics are closely captured by the radio network model. [pdf] [ps]
Thomas Moscibroda and Roger Wattenhofer [MoscibrodaW:05d] [published]
Coloring Unstructured Radio Networks
17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Las Vegas, 17-20 July 05
During and immediately after their deployment, ad hoc and sensor networks lack an efficient communication scheme rendering even the most basic network coordination problems difficult. Before any reasonable communication can take place, nodes must come up with an initial structure that can serve as a foundation for more sophisticated algorithms. In this paper, we consider the problem of obtaining a vertex coloring as such an initial structure. We propose an algorithm that works under the unstructured radio network model. This model captures the characteristics of newly deployed ad hoc and sensor networks, i.e. asynchronous wake-up, no collision-detection, and scarce knowledge about the network topology. Our algorithm produces a correct coloring with O(Delta) colors in time O(Delta log n) with high probability in a unit disk graph, where n and Delta are the number of nodes in the network and the maximum degree, respectively. Furthermore, the number of locally used colors depends only on the local node density. [pdf] [ps]
Nicolas Burri, Roger Wattenhofer, Yves Weber, and Aaron Zollinger [BurriWWZ:05b] [published]
SANS: A Simple Ad hoc Network Simulator
World Conference on Educational Multimedia, Hypermedia & Telecommunications (ED-MEDIA), Montreal, 27 June - 2 July 05
If all communication layers are affected by the specific properties of ad hoc networks, such as unreliability of wireless links or node mobility, both the network and transport communication layers deserve special attention in this context. In this paper we present a Simple Ad Hoc Network Simulator SANS particularly intended for the simulation of distributed programs and protocols on these two layers. This focused approach allows for easy and fast learning about the concepts and correct usage of SANS as a development, debugging, testing and presentation tool. Together with the fact that for the implementation of the simulator and for the simulated programs the Java programming language has been chosen, SANS lends itself to both rapid prototyping and educational purposes. [pdf]
Michael O'Dell, Regina O'Dell, Mirjam Wattenhofer, Roger Wattenhofer [O'DellW:05] [published]
Lost in Space Or Positioning in Sensor Networks
Workshop on Real-World Wireless Sensor Networks (REALWSN), Stockholm, 20-21 June 05
We discuss the success chances of a real-world implementation of a positioning system for a wireless sensor network. While much research has been done in the area of node localization, the method of choice to verify the results has been in theory or by simulation. To realize the visions of future sensor networks, we take very basic sensor nodes (prototyping the smart dust idea) and implement a series of experiments to determine their suitability for use in positioning algorithms. Specifically, we look at the accuracy and effectiveness of direct distance measurements based on different signal strengths. We found that even though links are stable and symmetric over time, positioning in the real world is yet in its infant stage and that current theoretical models of sensor networks do not apply well in unspecialized hardware. [pdf]
Martin Fussen, Roger Wattenhofer, and Aaron Zollinger [FussenWZ:05] [published]
Interference Arises at the Receiver
International Conference on Wireless Networks, Communications, and Mobile Computing (WirelessCom), Maui, 13-16 June 05
Energy consumption in general and interference in particular being among the most critical issues in wireless networks, this paper introduces an explicit definition of interference, based on the number of other nodes by which a given network node can be disturbed. With this definition we show that there exist instances of sensor networks in which no topology control algorithm---aiming at interference reduction by having nodes restrict their transmission power levels---can construct a valid data gathering network with interference less than logarithmic in the number of network nodes $n$. In a second part of the paper we introduce the Nearest Component Connector (NCC) algorithm, which asymptotically matches this lower bound, guaranteeing to build a valid topology with interference in O(log n) in any given sensor network. Finally the paper compares NCC to other previously proposed data gathering structures in average-case networks. [pdf] [ps]
Thomas Locher, Roger Wattenhofer, and Aaron Zollinger [LocherWZ:05] [published]
Received-Signal-Strength-Based Logical Positioning Resilient to Signal Fluctuation
1st ACIS International Workshop on Self-Assembling Wireless Sensor Networks (SAWN), Baltimore, 23-25 May 05
Positioning based on received signal strengths from base stations is highly sensitive to the effects of signal attenuation, reflection, and scattering. Moreover, experimental measurements show that received signal strengths fluctuate significantly over time due to noise and interference. Unlike most of the related work our approach does not rely on the presence of a priori information about base station positions, objects influencing radio signal propagation, and signal propagation characteristics. Instead of trying to compute the current position defined by \emph{coordinates}, the goal of our system is to infer a user's present \emph{logical} position. In addition, our system particularly differs from previous work in the chosen statistical approach, which explicitly copes with signal strength fluctuation over time and allows control over system accuracy by means of specification of confidence intervals. [pdf] [ps]
Mirjam Wattenhofer, Roger Wattenhofer and Peter Widmayer [WattenhoferWW:05] [published]
Geometric Routing without Geometry
12th Colloquium on Structural Information and Communication Complexity, Mont-St-Michel, 24-26 May 05
In this paper we propose a new routing paradigm, called pseudo-geometric routing. In pseudo-geometric routing, each node u of a network of computing elements is assigned a pseudo coordinate composed of the graph (hop) distances from u to a set of designated nodes (the anchors) in the network. On these pseudo coordinates we employ greedy geometric routing. Almost as a side effect, pseudo-geometric routing is not restricted to planar unit disk graph networks anymore, but succeeds on general networks. [pdf] [ps]
Thomas Moscibroda and Roger Wattenhofer [MoscibrodaW:05c] [published]
Maximizing the Lifetime of Dominating Sets
5th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN), Denver, 4-8 Apr 05
We investigate the problem of maximizing the lifetime of wireless ad hoc and sensor networks. Being battery powered, nodes in such networks have to perform their intended task under rigid energy restrictions that forces the designers to impose a judicious power management and scheduling. For the purpose of saving energy, dominating set based clustering has turned out to be a useful and generic concept in such networks. In data gathering applications, for example, only nodes in the dominating set must be active, while all other nodes can remain in the energy-efficient sleep mode. Prolonging the duration of such a dominating set based clustering is a key algorithmic challenge. In this paper, we define the maximum cluster-lifetime problem which asks for a schedule that maximizes the time the network is clustered by a dominating set. We give approximation algorithms with an approximation ratio of O(log n) for several variants of the maximum cluster-lifetime problem. Our approach is based on results given in a paper by Feige, Halld´orsson, Kortsarz, and Srinivasan on the domatic partition problem. [pdf]
Pascal von Rickenbach, Stefan Schmid, Roger Wattenhofer, Aaron Zollinger [RickenbachSWZ:05] [published]
A Robust Interference Model for Wireless Ad-Hoc Networks
5th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN), Denver, 4-8 Apr 05
Among the foremost goals of topology control in wireless ad-hoc networks is interference reduction. This paper presents a receiver-centric interference model featuring two main advantages over previous work. First, it reflects the fact that interference occurs at the intended receiver of a message. Second, the presented interference measure is robust with respect to addition or removal of single network nodes. Regarding both of these aspects our model intuitively corresponds to the behavior of interference in reality. Based on this interference model, we show that currently known topology control algorithms poorly reduce interference. Motivated by the observation that already onedimensional network instances display the intricacy of the considered problem, we continue to focus on the so-called highway model. Setting out to analyze the special case of the exponential node chain, we eventually describe an algorithm guaranteeing to achieve a fourth-root of Delta approximation of the optimal connectivity-preserving topology in the general highway model. [pdf] [ps]
Fabian Kuhn, Stefan Schmid, and Roger Wattenhofer [KuhnSW:05] [published]
A Self-Repairing Peer-to-Peer System Resilient to Dynamic Adversarial Churn
4th International Workshop on Peer-To-Peer Systems (IPTPS), Ithaca, 24-25 Feb 05
We present a dynamic distributed hash table where peers may join and leave at any time. Our system tolerates a powerful adversary which has complete visibility of the entire state of the system and can continuously add and remove peers. Our system provides worst-case fault-tolerance, maintaining desirable properties such as a low peer degree and a low network diameter. [pdf] [ps]
Li Li, Joseph Halpern, Victor Bahl, Yi-Min Wang, Roger Wattenhofer [LiHBWW:05] [published]
A Cone-Based Distributed Topology-Control Algorithm for Wireless Multi-Hop Networks
IEEE/ACM Transactions on Networking (TON), vol. 13, issue 1, Feb 05
The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology-control (CBTC) algorithm. This algorithm does not assume that nodes have GPS information available; rather it depends only on directional information. Roughly speaking, the basic idea of the algorithm is that a node$u$transmits with the minimum power$p_u,alpha$required to ensure that in every cone of degree$alpha$around$u$, there is some node that$u$can reach with power$p_u,alpha$. We show that taking$alpha=5pi/6$is a necessary and sufficient condition to guarantee that network connectivity is preserved. More precisely, if there is a path from$s$to$t$when every node communicates at maximum power then, if$alphaleq5pi/6$, there is still a path in the smallest symmetric graph$G_alpha$containing all edges$(u,v)$such that$u$can communicate with$v$using power$p_u,alpha$. On the other hand, if$alpha≫5pi/6$, connectivity is not necessarily preserved. We also propose a set of optimizations that further reduce power consumption and prove that they retain network connectivity. Dynamic reconfiguration in the presence of failures and mobility is also discussed. Simulation results are presented to demonstrate the effectiveness of the algorithm and the optimizations. [pdf]
Thomas Moscibroda, Roger Wattenhofer [MoscibrodaW:04] [published]
Efficient Computation of Maximal Independent Sets in Unstructured Multi-Hop Radio Networks
1st IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), Fort Lauderdale, 24-27 Oct 2004
When being deployed, ad-hoc and sensor networks are unstructured and lack an efficient and reliable communication scheme. Hence, the organization of a MAC layer is the primary goal during and immediately after the deployment of such networks. Computing a good initial clustering facilitates this task and is therefore a vital part of the initialization process. A clustering based on a maximal independent set provides several highly desirable properties. Besides yielding a dominating set of good quality, such a clustering avoids interference between clusterheads, thus allowing efficient communication. We propose a novel algorithm that works under a model capturing the characteristics of the initialization phase of unstructured radio networks, i.e., asynchronous wake-up, scarce knowledge about the topology of the network graph, no collision detection, and the hidden terminal problem. We show that even under these hard conditions, the algorithm computes a maximal independent set in polylogarithmic time. [pdf] [ps]
Hagit Attiya, Fabian Kuhn, Mirjam Wattenhofer, and Roger Wattenhofer [AttiyaKWW:04] [published]
Efficient Adaptive Collect using Randomization
18th Annual Conference on Distributed Computing (DISC), Amsterdam, 4-7 Oct 04
An adaptive algorithm, whose step complexity adjusts to the number of active processes, is attractive for distributed systems with a highly-variable number of processes. The cornerstone of many adaptive algorithms is an adaptive mechanism to collect up-to-date information from all participating processes. To date, all known collect algorithms either have non-linear step complexity or they are impractical because of unrealistic memory overhead. This paper presents new randomized collect algorithms with asymptotically optimal O(k) step complexity and polynomial memory overhead only. In addition we present a new deterministic collect algorithm which beats the best step complexity for previous polynomial-memory algorithms. [pdf] [ps]
Pascal von Rickenbach, Roger Wattenhofer [RickenbachW:04] [published]
Gathering Correlated Data in Sensor Networks
Dial M-POMC 2004, Mobicom Joint Workshop on Foundations of Mobile Computing, Philadelphia, 1 Oct 04
In this paper, we consider energy-eficient gathering of correlated data in sensor networks. We focus on single-input coding strategies in order to aggregate correlated data. For foreign coding we propose the MEGA algorithm which yields a minimum-energy data gathering topology in O(n^3) time. We also consider self-coding for which the problem of finding an optimal data gathering tree was recently shown to be NP-complete; with LEGA, we present the first approximation algorithm for this problem with approximation ratio 2(1 + sqrt(2)) and running time O(m + n log n). [pdf] [ps]
Thomas Moscibroda, Regina O'Dell, Mirjam Wattenhofer, Roger Wattenhofer [MoscibrodaOWW:04] [published]
Virtual Coordinates for Ad hoc and Sensor Networks
Dial M-POMC 2004, Mobicom Joint Workshop on Foundations of Mobile Computing, Philadelphia, 1 Oct 04
In many applications of wireless ad hoc and sensor networks, position-awareness is of great importance. Often, as in the case of geometric routing, it is sufficient to have virtual coordinates, rather than real coordinates. In this paper, we address the problem of obtaining virtual coordinates based on connectivity information. In particular, we propose the first approximation algorithm for this problem and discuss implementational aspects. [pdf] [ps]
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer [KuhnMW:04c] [published]
Unit Disk Graph Approximation
Dial M-POMC 2004, Mobicom Joint Workshop on Foundations of Mobile Computing, Philadelphia, 1 Oct 04
Finding a good embedding of a unit disk graph given by its connectivity information is a problem of practical importance in a variety of fields. In wireless ad hoc and sensor networks, such an embedding can be used to obtain virtual coordinates. In this paper, we prove a non-approximability result for the problem of embedding a given unit disk graph. Particularly, we show that if non-neighboring nodes are not allowed to be closer to each other than distance 1, then two neighbors can be as far apart as sqrt(3/2)-epsilon, where epsilon goes to 0 as n goes to infinity, unless P = NP. We further show that finding a realization of a d-quasi unit disk graph with d>=1/sqrt(2) is NP-hard. [pdf] [ps]
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer [KuhnMW:04d] [published]
Initializing Newly Deployed Ad Hoc and Sensor Networks
MOBICOM 2004, Philadelphia, 26 Sep - 1 Oct 2004
A newly deployed multi-hop radio network is unstructured and lacks a reliable and e±cient communication scheme. In this paper, we take a step towards analyzing the problems existing during the initialization phase of ad hoc and sensor networks. Particularly, we model the network as a multi-hop quasi unit disk graph and allow nodes to wake up asynchronously at any time. Further, nodes do not feature a reliable collision detection mechanism, and they have only limited knowledge about the network topology. We show that even for this restricted model, a good clustering can be computed efficiently. Our algorithm efficiently computes an asymptotically optimal clustering. Based on this algorithm, we describe a protocol for quickly establishing synchronized sleep and listen schedule between nodes within a cluster. Additionally, we provide simulation results in a variety of settings. [pdf] [ps]
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer [KuhnMW:04b] [published]
Radio Network Clustering from Scratch
12nd Annual European Symposium on Algorithms (ESA), Bergen, Norway, September 2004
We propose a novel randomized algorithm for computing a dominating set based clustering in wireless ad-hoc and sensor networks. The algorithm works under a model which captures the characteristics of the set-up phase of such multi-hop radio networks: asynchronous wake-up, the hidden terminal problem, and scarce knowledge about the topology of the network graph. When modelling the network as a unit disk graph, the algorithm computes a dominating set in polylogarithmic time and achieves a constant approximation ratio. [pdf] [ps]
Keno Albrecht, Ruedi Arnold, Michael Gähwiler, and Roger Wattenhofer [AlbrechtAGW:04] [published]
Aggregating Information in Peer-to-Peer Systems for Improved Join and Leave
4th IEEE International Conference on Peer-to-Peer Computing (P2P), Zurich, 25-27 Aug 04
In this paper, we introduce the Distributed Approximative System Information Service (DASIS) as a useful scheme to aggregate approximative information on the state of a peer-to-peer system. We present how this service can be integrated into existing peer-to-peer systems, such as Kademlia and Chord. As a sample application, we show how DASIS can be employed for establishing an effective deterministic join algorithm. Through simulation, we demonstrate that the insertion of peers using DASIS information results in a well-balanced system. Moreover, our join algorithm gracefully resolves load imbalances in the system due to unfortunate biased leaves of peers. [pdf] [ps]
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer [KuhnMW:04a] [published]
What Cannot be Computed Locally!
23rd ACM Symposium on Principles of Distributed Computing (PODC), St. John's, Canada, 25-28 July 2004
We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communication rounds, MVC and MDS can only be approximated by factors Omega(n^(c/k^2)/k) and Omega(Delta^(1/k)/k) for some constant c, where n and Delta denote the number of nodes and the largest degree in the graph. The number of rounds required in order to achieve a constant or even only a polylogarithmic approximation ratio is at least Omega(sqrt(log n/(log log n))) and Omega(sqrt(log Delta/(log log Delta))). By a simple reduction, the latter lower bounds also hold for the construction of maximal matchings and maximal independent sets. [pdf] [ps]
Fabian Kuhn and Roger Wattenhofer [KuhnW:04] [published]
Dynamic Analysis of the Arrow Distributed Protocol
16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Barcelona, 27-30 June 04
Arrow is a prominent distributed protocol which globally orders requests initiated by the nodes in a distributed system. In this paper we present a dynamic analysis of the Arrow protocol. We prove that Arrow is O(log D)-competitive, where D is the diameter of the spanning tree on which Arrow operates. In addition, we show that our analysis is almost tight by proving that for all trees the competitive ratio of Arrow is Omega(log D/(log log D)). [pdf] [ps]
Fabian Kuhn, Pascal von Rickenbach, Roger Wattenhofer, Emo Welzl, Aaron Zollinger [KuhnRWWZ:04] [published]
On Coverage in Infrastructure Networks
Technical Report ETHZ TR 437
For mobile distributed tasks, the infrastructure is often formed by cellular networks. One of the major issues in such networks is interference. In this paper we tackle interference reduction by suitable assignment of transmission power levels to base stations. This task is formalized introducing the Minimum Membership Set Cover combinatorial optimization problem. On the one hand we prove that in polynomial time the optimal solution of the problem cannot be approximated more closely than with a factor ln{n}. On the other hand we present an algorithm exploiting linear programming relaxation techniques which not only asymptotically matches the lower bound with high probability but also performs well in practical networks. [pdf]
Martin Burkhart, Pascal von Rickenbach, Roger Wattenhofer, Aaron Zollinger [BurkhartRWZ:04] [published]
Does Topology Control Reduce Interference?
ACM Mobihoc 2004, Tokyo, 24-26 May 04
Topology control in ad-hoc networks tries to lower node energy consumption by reducing transmission power and by confining interference, collisions and consequently retransmissions. Commonly low interference is claimed to be a consequence to sparseness of the resulting topology. In this paper we disprove this implication. In contrast to most of the related work---claiming to solve the interference issue by graph sparseness without providing clear argumentation or proofs---, we provide a concise and intuitive definition of interference. Based on this definition we show that most currently proposed topology control algorithms do not effectively constrain interference. Furthermore we propose connectivity-preserving and spanner constructions that are interference-minimal. [pdf]
Roger Wattenhofer, Aaron Zollinger [WattenhoferZ:04] [published]
XTC: A Practical Topology Control Algorithm for Ad-Hoc Networks
4th International IEEE Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN), Santa Fe, 26-30 April 2004
The XTC ad-hoc network topology control algorithm introduced in this paper shows three main advantages over previously proposed algorithms. First, it is extremely simple and strictly local. Second, it does not assume the network graph to be a Unit Disk Graph; XTC proves correct also on general weighted network graphs. Third, the algorithm does not require availability of node position information. Instead, XTC operates with a general notion of order over the neighbors’ link qualities. In the special case of the network graph being a Unit Disk Graph, the resulting topology proves to have bounded degree, to be a planar graph, and—on average-case graphs—to be a good spanner. [pdf]
Regina Bischoff, Roger Wattenhofer [BischoffW:04] [published]
Analyzing Connectivity-Based Multi-Hop Ad-Hoc Positioning
2nd Annual IEEE International Conference on Pervasive Computing and Communications (PerCom), Orlando, 14-17 Mar 2004
We investigate the theoretical limits of positioning algorithms. In particular, we study scenarios where the nodes do not receive anchors directly (multi-hop) and where no physical distance or angle information whatsoever is available (connectivity-based). Since we envision large-scale sensor networks as an application, we are interested in fast, distributed algorithms. As such, we show that plain hop algorithms are not competitive. Instead, for one-dimensional unit disk graphs we present an optimal algorithm HS. For two or more dimensions, we propose an algorithm GHoST which improves upon the basic hop algorithm in theory and in simulations. [pdf]
Roger Wattenhofer [Wattenhofer:04] [published]
Ad-Hoc and Sensor Networks: Worst-Case and Average-Case
Invited paper to the 18th International Zurich Seminar on Communications (IZS), Zurich, 18-20 Feb 2004
Ad-hoc and sensor networks are rapidly growing areas of research which study the problems arising when small and feeble devices build a communication infrastructure. A vast majority of researchers in the field make strong average-case assumptions about these networks, for example that the devices are distributed uniformly at random. To system builders on the other hand many of these assumptions appear suspicious. In this paper we advocate an algorithmic (worst-case) approach to adhoc and sensor networking. We survey a few also worst-case efficient algorithms for topology control, clustering, and routing. [pdf]
Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger [KuhnZW:03] [published]
Ad-Hoc Networks Beyond Unit Disk Graphs
MobiCom/DIALM-POMC 2003, 19 Sep 2003, San Diego
In this paper we study a model for ad-hoc networks close enough to reality as to represent existing networks, being at the same time concise enough to promote strong theoretical results. The Quasi Unit Disk Graph model contains all edges shorter than a parameter d between 0 and 1 and no edges longer than 1. We show that--in comparison to the cost known on Unit Disk Graphs--the complexity results in this model contain the additional factor 1/d^2. We prove that in Quasi Unit Disk Graphs flooding is an asymptotically message-optimal routing technique, provide a geometric routing algorithm being more effcient above all in dense networks, and show that classic geometric routing is possible with the same performance guarantees as for Unit Disk Graphs if d >= 1/sqrt(2). [pdf]
Fabian Kuhn, Roger Wattenhofer, Yan Zhang, Aaron Zollinger [KuhnWYZ:03a] [published]
Geometric Ad-Hoc Routing: Of Theory and Practice
Twenty-Second ACM Symposium on Principles of Distributed Computing (PODC 2003), July 13-16, 2003, Boston
All too often a seemingly insurmountable divide between theory and practice can be witnessed. In this paper we try to contribute to narrowing this gap in the field of ad-hoc routing. In particular we consider two aspects: We propose a new geometric routing algorithm which is outstandingly efficient on practical average-case networks, however is also in theory asymptotically worst-case optimal. On the other hand we are able to drop the formerly necessary assumption that the distance between network nodes may not fall below a constant value, an assumption that cannot be maintained for practical networks. Abandoning this assumption we identify from a theoretical point of view two fundamentamentally different classes of cost metrics for routing in ad-hoc networks. [pdf]
Fabian Kuhn, Roger Wattenhofer [KuhnW:03a] [published]
Constant-Time Distributed Dominating Set Approximation
Twenty-Second ACM Symposium on Principles of Distributed Computing (PODC 2003), July 13-16, 2003, Boston
Finding a small dominating set is one of the most fundamental problems of traditional graph theory. In this paper, we present a new fully distributed approximation algorithm based on LP relaxation techniques. For an arbitrary parameter k, our algorithm computes a dominating set of expected size O(k \Delta^(2/k) log \Delta |DS_{OPT}|) in O(k^2) rounds where each node has to send O(k^2 \Delta) messages of size O(log \Delta). This is the first algorithm which achieves a non-trivial approximation ratio in a constant number of rounds. [pdf]
Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger [KuhnWZ:03a] [published]
Worst-Case Optimal and Average-Case Efficient Geometric Ad-Hoc Routing
4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), Annapolis, Maryland, USA, June 1-3, 2003
In this paper we present GOAFR, a new geometric ad-hoc routing algorithm combining greedy and face routing. We evaluate this algorithm by both rigorous analysis and comprehensive simulation. GOAFR is the first ad-hoc algorithm to be both asymptotically optimal and average-case efficient. For our simulations we identify a network density range critical for any routing algorithm. We study a dozen of routing algorithms and show that GOAFR outperforms other prominent algorithms, such as GPSR or AFR. [pdf]
Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger [KuhnWZ:02a] [published]
Asymptotically Optimal Geometric Mobile Ad-Hoc Routing
Dial-M ´02, September 28, 2002, Atlanta, Georgia, USA.
In this paper we present AFR, a new geometric mobile ad-hoc routing algorithm. The algorithm is completely distributed; nodes need to communicate only with direct neighbors in their transmission range. We show that if a best route has cost $c$, AFR finds a route and terminates with cost $O(c^2)$ in the worst case. AFR is the first algorithm with cost bounded by a function of the optimal route. We also give a tight lower bound by showing that any geometric routing algorithm has worst-case cost $\Omega(c^2)$. Thus AFR is asymptotically optimal. We give a non-geometric algorithm that also matches the lower bound, but needs some memory at each node. This establishes an intriguing trade-off between geometry and memory. [pdf] [ps]
Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger [KuhnWZ:02b] [published]
Geometric Ad-hoc Routing for Unit Disk Graphs and General Cost Models
Technical Report TR 373, ETH Zurich, June 2002
What is the influence of the chosen cost metric on the performance of a mobile ad-hoc routing algorithm? In this paper we define the notion of a general cost metric and observe that all cost metrics fall into two classes, linearly bounded and super-linear. Distinguished by a natural argument, the two classes yet show a dramatic difference: On a network with linearly bounded cost metric a geometric routing algorithm will find a route whose cost is at most quadratic in the cost of the optimal route, which at the same time is asymptotically optimal. On the other hand there is no such bound on a graph with super-linear cost functions for any geometric routing algorithm. We introduce, however, the class of bounded degree unit disk graphs, on which all cost metrics are equivalent. We finally propose an asymptotically optimal distributed geometric routing algorithm based on node clustering and network backbone construction. [pdf] [ps]

The National Centers of Competence in Research are a research
instrument of the Swiss National Science Foundation.