Graph filters play a key role in processing the graph spectra of signals supported on the vertices of a graph. However, despite their widespread use, graph filters have been analyzed only in the deterministic setting, ignoring the impact of stochasticity in both the graph topology and the signal itself. To bridge this gap, we examine the statistical behavior of the two key filter types, finite impulse response and autoregressive moving average graph filters, when operating on random time-varying graph signals (or random graph processes) over random time-varying graphs. Our analysis shows that 1) in expectation, the filters behave as the same deterministic filters operating on a deterministic graph, being the expected graph, having as input signal a deterministic signal, being the expected signal, and 2) there are meaningful upper bounds for the variance of the filter output. We conclude this paper by proposing two novel ways of exploiting randomness to improve (joint graph-time) noise cancellation, as well as to reduce the computational complexity of graph filtering. As demonstrated by numerical results, these methods outperform the disjoint average and denoise algorithm and yield a (up to) four times complexity reduction, with a very little difference from the optimal solution.

@en

One of the cornerstones of the field of signal processing on graphs are graph filters, direct analogs of classical filters, but intended for signals defined on graphs. This paper brings forth new insights on the distributed graph filtering problem. We design a family of autoregressive moving average (ARMA) recursions, which are able to approximate any desired graph frequency response, and give exact solutions for specific graph signal denoising and interpolation problems. The philosophy to design the ARMA coefficients independently from the underlying graph renders the ARMA graph filters suitable in static and, particularly, time-varying settings. The latter occur when the graph signal and/or graph topology are changing over time. We show that in case of a time-varying graph signal, our approach extends naturally to a two-dimensional filter, operating concurrently in the graph and regular time domain. We also derive the graph filter behavior, as well as sufficient conditions for filter stability when the graph and signal are time varying. The analytical and numerical results presented in this paper illustrate that ARMA graph filters are practically appealing for static and time-varying settings, as predicted by theoretical derivations.

@en

We present a novel implementation strategy for distributed autoregressive moving average (ARMA) graph filters. Differently from the state of the art implementation, the proposed approach has the following benefits: (i) the designed filter coefficients come with stability guarantees, (ii) the linear convergence time can now be controlled by the filter coefficients, and (iii) the stable filter coefficients that approximate a desired frequency response are optimal in a least squares sense. Numerical results show that the proposed implementation outperforms the state of the art distributed infinite impulse response (IIR) graph filters. Further, even at fixed distributed costs, compared with the popular finite impulse response (FIR) filters, at high orders our method achieves tighter low-pass responses, suggesting that it should be preferable in accuracy-demanding applications.

@en

Despite their widespread use for the analysis of graph data, current graph filters are designed for graph signals that do not change over time, and thus they cannot simultaneously process time and graph frequency content in an adequate manner. This work presents ARMA2D, an autoregressive moving average graph-temporal filter that captures jointly the signal variations over the graph and time. By its unique nature, this filter is able to achieve a separable 2-dimensional frequency response, making it possible to approximate the filtering specifications along both the graph and temporal frequency domains. Numerical results show that the proposed solution outperforms the state of the art graph filters when the graph signal is time-varying.@en

We have recently seen a surge of work on distributed graph filters, extending classical results to the graph setting. State of the art filters have however only been examined from a deterministic standpoint, ignoring the impact of stochasticity in the computation (e.g., temporal fluctuation of links) and input (e.g., the value of each node is a random process). Initiating the study of stochastic graph signal processing, this paper shows that a prominent class of graph filters, namely autoregressive moving average (ARMA) filters, are suitable for the stochastic setting. In particular, we prove that an ARMA filter that operates on a stochastic signal over a stochastic graph is equivalent, in the mean, to the same filter operating on the expected signal over the expected graph. We also characterize the variance of the output and we provide an upper bound for its average value among different nodes. Our results are validated by numerical simulations.@en

Opportunistic routing protocols tackle the problem of efficient data collection in dynamic wireless sensor networks, where the radio is duty-cycled to save energy and the topology changes unpredictably due to node mobility and/or link dynamics. Unlike protocols that maintain a routing structure, in opportunistic protocols nodes forward packets to any neighbor that wakes up first, reducing latency and energy costs and increasing the resilience to network dynamics.
We claim the performance of existing opportunistic routing protocols can be improved while retaining their resilience by harnessing the synergy between duty cycling and opportunistic forwarding. To prove this claim, we present Staffetta, the first practical duty-cycle adaptation scheme for opportunistic low-power wireless protocols. Staffetta dynamically adapts each node's wake-up frequency to its current forwarding cost, so nodes closer to the sink become more active than nodes farther away. In this way, Staffetta biases the forwarding choices toward the sink as the neighbor waking up first is also likely to offer high routing progress. Experiments on two testbeds with four different opportunistic routing mechanisms demonstrate that Staffetta achieves severalfold performance improvements compared with a fixed wake-up frequency. As a case a point, Staffetta enables ORW, the state-of-the-art opportunistic routing protocol, to reduce end-to-end packet latency by 79-452 × and energy consumption by 2.75-9× while increasing packet delivery ratio compared with ORW's default link-layer settings.
@en

Graph filters are a recent and powerful tool to process information 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 signal 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.@en

We have recently seen a surge of research focusing on the processing of graph data. The emerging field of signal processing on graphs focuses on the extension of classical discrete signal processing techniques to the graph setting. Arguably, the greatest breakthrough of the field has been the extension of the Fourier transform from time signals and images to graph signals, i. e., signals defined on the nodes of irregular graphs. Analogously to how the Fourier transform allows us to decompose complex signals in terms of their fundamental frequencies, the spectral transform describes signals in terms of their relation to the underlying graph. The rigorous examination of the relation between signal and graph has lead to the design of distributed graph filters, graph analogues of classical filters. Graph filters enable us to observe graph data at different scales, effectively separating fine details from inherent signal trends. For instance, a low-pass graph filter controls the size of observable signal structures, attenuating structures of small size, such as those attributed to noise. Beyond noise removal, graph filters are useful for revealing communities (low-pass), identifying event-regions (band-pass), and detecting anomalies (high-pass). Yet, despite their interesting properties, current distributed graph filters have so far been limited. To begin with, it is currently assumed that all data remain static for the duration of computation. When the signal is time-varying and the graph topology dynamic, the computation becomes challenging. Even further, filtering efficiency depends on the correct choice of scale—roughly the number of hops a filter takes into account. To choose the scale correctly however, one must have a-priori information about the observed phenomenon, as well as of the instrument of observation—in our case, the graph topology; information which is rarely available and often changes over time. The main contribution of this thesis is tackling the above limitations. First, we relax the computational assumptions posed by current graph filters. We propose distributed graph filters that converge fast, even in the presence of dynamics. Our filters are shown robust to message loss, and able to track time-varying signals and graphs. Second, we set the foundations of distributed scale-invariant analysis of graph signals. According to classical scale-space theory, if no a-priori information about a signal is known, one must observe it at all possible scales. In an analogous way, we show that the scale-invariant observation of a graph signal entails filtering it with a small family of graph filters. Scale-space analysis is therefore possible on graphs, and incurs an overhead equivalent to that of a distributed graph filter. We demonstrate the usefulness of our algorithms by applying them to a number of important information processing problems in sensor networks. Among others, our filters are shown to expand the scope of potential-field search methods, to enhance the detection accuracy of spatial event regions and boundaries, and to improve the identification of signal peaks and pits. Simulations and experiments, demonstrate that our algorithms are robust to the difficult conditions posed by wireless communications (such as asymmetric links, phantom effects, message loss, and asynchrony), and that they scale to very large networks.@en

We introduce the concept of autoregressive moving average (ARMA) filters on a graph and show how they can be implemented in a distributed fashion. Our graph filter design philosophy is independent of the particular graph, meaning that the filter coefficients are derived irrespective of the graph. In contrast to finite-impulse response (FIR) graph filters, ARMA graph filters are robust against changes in the signal and/or graph. In addition, when time-varying signals are considered, we prove that the proposed graph filters behave as ARMA filters in the graph domain and, depending on the implementation, as first or higher order ARMA filters in the time domain.@en

Cooperation is the foundation of wireless ad hoc networks with nodes forwarding their neighbors' packets for the common good. However, energy and bandwidth constraints combined with selfish behaviour lead to collapsed networks where all nodes defect. Researchers have tried to incentivize or enforce the nodes for cooperation in various ways. However, these techniques do not consider the heterogeneous networks in which a diverse set of nodes with different cognitive capabilities exist. Furthermore, in ad hoc networks identity is a fuzzy concept. It is easy to forge multiple identities and hide defective behaviour. Moreover, the nature of the wireless medium is always ambiguous due to collisions, interference and asymmetric links. In all this uncertainty, having complete information about the intentions of the nodes and acting on it is not straightforward. Backed by evolutionary game theory and multi-agent systems research, we adapt and modify two meta strategies to embrace this uncertainty. These modified meta strategies, Win Stay Loose Shift and Stochastic Imitate Best Strategy, do not require strict identity information and only depend on nodes' own capabilities. Nodes monitor the traffic in their neighbourhood by using a two-hop overhearing method, and decide whether they should be cooperative or defective. We show that nodes are able to discover and use the best strategy in their locality and protect themselves against the exploitation by free riders who devise Sybil attacks by changing their identities.@en

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 networks consisting of a few tens of nodes and where only a fraction of nodes estimate the cardinality concurrently.@en