This paper reports our experience with crowd monitoring technologies in the challenging real-world conditions of a modern, open-space museum. We seized the opportunity to use the NEMO science center as a testbed, and studied the effectiveness of neighborhood discovery and density estimation algorithms in a network formed by visitors wearing bracelets emitting RF beacons. The diverse set of conditions (flash crowds in open spaces vs. single person booths) revealed three interesting findings: (i) state-of-the-art density estimation fails in 80% of the cases, (ii) RSS-based classifiers fail too, because their underlying assumptions do not hold in many scenarios, and (iii) neighborhood discovery can obtain exact information in an energy-efficient way, provided that static and mobile nodes are differentiated to filter out “passers by” clobbering the true popularity of an exhibit. The overall lesson from the experiment is that today’s algorithms are quite far from the ideal of monitoring popularity in a privacy-preserving and energy-efficient way with minimal infrastructure across the set of heterogeneous conditions encountered in practice.@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

Sensor networks can nowadays deliver 99.9% of their data with duty cycles below 1%. This remarkable performance is, however, dependent on some important underlying assumptions: low traffic rates, medium size densities and static nodes. In this thesis, we investigate the performance of these same resource-constrained devices, but under scenarios that present extreme conditions: high traffic rates, high densities and mobility: the so-called ExtremeWireless Sensor Networks (EWSNs). From a networking perspective, communicating in these extreme scenarios is very challenging. The combined effect of high network densities and dynamics makes the network’s characteristics fluctuate drastically both in space and time. Traditional mechanisms struggle to cope with these sudden changes, resulting in a continuous exchange of information that saturates the bandwidth and increases the energy consumption. Once this saturation threshold is reached, mechanisms take decisions based on wrong, outdated information and soon stop working. Even flexible mechanisms have difficulties adapting their settings to the fickly conditions of EWSNs and result in poor performance. To efficiently communicate in EWSNs, mechanisms must therefore comply to a set of requirements i. e., design principles, which are explained next. First, they need to be resilient to local and remote failures and operate as independent as possible from the status of other nodes (state-less principle). Second, because in EWSNs bandwidth is a scarce resource, it should be mainly used for the transmission of the actual data. Mechanisms should not be artificially orchestrated and should exploit each other in a cross-layer fashion to reduce as much as possible their communication overhead (opportunistic principle). Third, mechanisms should support extreme network conditions from their inception. Adapting traditional mechanisms, which are designed for milder conditions, would otherwise result in complex and fragile mechanisms (anti-fragile principle). Fourth, in the case the resources saturate, mechanisms should operate in a conservative fashion, so that performance degrades gracefully without drastic disruptions (robustness principle). Inspired by these four principles, this thesis detaches from traditional communication primitives – which are deterministic and based on rigid structures – and proposes a novel communication stack based on opportunistic anycast. According to this primitive, nodes communicate with the first available neighbor, independently of its location and identity. The more neighbors, themore efficient the communication. At the foundation of this communication stack lays SOFA, a medium access control (MAC) protocol that exploits opportunistic anycast to handle extreme densities in an efficient manner. Its implementation details are presented in Chapter 2. On top of the SOFA layer, this thesis builds two essential network services: neighborhood cardinality (density) estimation and data collection. The former service is provided by Estreme, a mechanism presented in Chapter 3, which exploits the rendezvous time of SOFA to estimate the number of neighbors with almost zero overhead. The latter service is provided by Staffetta in Chapter 4, a mechanism that adapts the wake-up frequency of nodes to bias the opportunistic neighbor-selection of SOFA towards the desired direction e. g., towards the sink node collecting all data. Finally, this thesis presents an extensive evaluation of a complete opportunistic stack on simulations, testbeds and a challenging real-world deployment in the formof the NEMO science museumin Amsterdam. Results showthat opportunistic behavior can lead to mechanisms that are both lightweight and robust and, thus, are able to scale to EWSNs.@en

When deploying a testbed infrastructure for Wireless Sensor Networks (WSNs), one of the most challenging features is to provide repeatable mobility. Wheeled robots, usually employed for such tasks, strive to adapt to the wide range of environments where WSNs are deployed, from chaotic office spaces to neatly raked potato elds. For this reason, wheeled robots often require an expensive customization step in order to adapt, for example, their localization and navigation systems to the specific environment. To avoid this issue, we present Gondola, a parametric robot infrastructure based on pulling wires, rather than wheels. Gondola avoids the most common problems of wheeled robots and easily adapts to many WSNs' scenarios. Different from existing solutions, Gondola can easily move in 3-dimensional space, with no need of a complex localization system and with an accuracy that is comparable to o-the-shelf traditional robots.@en

Face-to-face proximity has been successfully leveraged to study the relationships between individuals in various contexts, from a working place, to a conference, a museum, a fair, and a date. We spend time facing the individuals with whom we chat, discuss, work, and play. However, face-to-face proximity is not the realm of solely person-to-person relationships, but it can be used as a proxy to study person-to-object relationships as well. We face the objects with which we interact on a daily basis, like a television, the kitchen appliances, a book, including more complex objects like a stage where a concert is taking place. In this paper, we focus on the relationship between the visitors of an art exhibition and its exhibits. We design, implement, and deploy a sensing infrastructure based on inexpensive mobile proximity sensors and a filtering pipeline that we use to measure face-to-face proximity between individuals and exhibits. Our pipeline produces an improvement in measurement accuracy of up to 64% relative to raw data. We use this data to mine the behavior of the visitors and show that group behavior can be recognized by means of data clustering and visualization.@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 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

In spite of using unreliable resource-constrained devices, sensor networks can nowadays deliver 99.9% of their data with duty cycles well below 1%. This remarkable performance is, however, dependent on one or more of the following assumptions: low traffic rates, medium size densities and static nodes.

@en