Graph Scale-Space Theory for Distributed Peak and Pit Identification


Graph filters are a recent and powerful tool to process in- formation in graphs. Yet despite their advantages, graph filters are limited. The limitation is exposed in a filtering task that is common, but not fully solved in sensor networks: the identification of a signal’s peaks and pits. Choosing the correct filter necessitates a-priori information about the sig- nal and the network topology. Furthermore, in sparse and irregular networks graph filters introduce distortion, effectively rendering identification inaccurate, even when signal-specific information is available. Motivated by the need for a multi-scale approach, this paper extends classical results on scale-space analysis to graphs. We derive the family of scale-space kernels (or filters) that are suitable for graphs and show how these can be used to observe a signal at all possible scales: from fine to coarse. The gathered information is then used to distributedly identify the signal’s peaks and pits. Our graph scale-space approach diminishes the need for a-priori knowledge, and reduces the effects caused by noise, sparse and irregular topologies, exhibiting: (i) superior resilience to noise than the state-of-the-art, and (ii) at least 20% higher precision than the best graph filter, when evaluated on our testbed.

ACM Digital Library | Paper

AuthorsAndreas Loukas and Marco Cattani and Marco A. Zuniga and Jie Gao
Research group: Embedded Software group, Delft University of Technology, Delft, Netherlands and Stony Brook University, Stony Brook, New York
Conference14th Int. Conf. on Information Processing in Sensor Networks (IPSN)
Year: 2015

Lightweight neighborhood cardinality estimation in dynamic wireless networks


We address the problem of estimating the neighborhood cardinality of nodes in dynamic wireless networks. Different from previous studies, we consider networks with high densities (a hundred neighbors per node) and where all nodes estimate cardinality concurrently. Performing concurrent estimations on dense mobile networks is hard; we need estimators that are not only accurate, but also fast, asynchronous (due to mobility) and lightweight (due to concurrency and high density). To cope with these requirements, we propose Estreme, a neighborhood cardinality estimator with extremely low overhead that leverages the rendezvous time of low- power medium access control (MAC) protocols. We implemented Estreme on the Contiki OS and show a significant improvement over the state-of-the-art. With Estreme, 100 nodes can concurrently estimate their neighborhood cardinality with an error of ≈10%. State-of- the-art solutions provide a similar accuracy, but on net- works consisting of a few tens of nodes and where only a fraction of nodes estimate the cardinality concurrently.

ACM Digital LibraryPaper | Presentation | Video

AuthorsMarco Cattani and Marco A. Zuniga and Andreas Loukas and Koen G. Langendoen
Research group: Embedded Software group, Delft University of Technology, Delft, Netherlands
Conference13th Int. Conf. on Information Processing in Sensor Networks (IPSN)
Year: 2014

Think Globally, Act Locally: On the Reshaping of Information Landscapes


In large-scale resource-constrained systems, such as wireless sensor networks, global objectives should be ideally achieved through inexpensive local interactions. A technique satisfying these requirements is information potentials, in which distributed functions disseminate information about the process monitored by the network. Information potentials are usually computed through local aggregation or gossiping. These methods however, do not consider the topological properties of the network, such as node density, which could be exploited to enhance the performance of the system. This paper proposes a novel aggregation method with which a potential becomes sensitive to the network topology. Our method introduces the notion of affinity spaces, which allow us to uncover the deep connections between the aggregation scope (the radius of the extended neighborhood whose information is aggregated) and the network’s Laplacian (which captures the topology of the connectivity graph). Our study provides two additional contributions: (i) It characterizes the convergence of information potentials for static and dynamic networks. Our analysis captures the impact of key parameters, such as node density, time-varying information, as well as of the addition (or removal) of links and nodes. (ii) It shows that information potentials are decomposed into wave-like eigenfunctions that depend on the aggregation scope. This result has important implications, for example it prevents greedy routing techniques from getting stuck by eliminating local-maxima. Simulations and experimental evaluation show that our main findings hold under realistic conditions, with unstable links and message loss.

ACM Digital Library | Paper | Video

AuthorsAndreas Loukas and Marco A. Zuniga and Matthias Woehrle and Marco Cattani and Koen G. Langendoen
Research group: Embedded Software group, Delft University of Technology, Delft, Netherlands
Conference12th Int. Conf. on Information Processing in Sensor Networks (IPSN)
Year: 2013