Lightweight neighborhood cardinality estimation in dynamic wireless networks

estreme_testbed
Standard

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

SOFA: Communication in Extreme Wireless Sensor Networks

Standard

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 paper, we investigate the performance of these same resource-constrained devices, but under scenarios that present extreme conditions: high traffic rates, high densities and mobility. To cope with these stringent requirements, we propose a novel communication protocol named SOFA (Stop On First Ack). SOFA utilizes opportunistic anycast to drastically reduce the rendezvous times of asynchronous duty cycled nodes -long rendezvous times are the key limitation of protocols operating under high densities and high traffic conditions. SOFA is also stateless, which makes it resilient to mobility. We implemented SOFA in the Contiki OS and tested it both in simulation and on a 100-node testbed. Our results show that SOFA reliably communicates in mobile networks with extreme densities (hundreds of nodes) and higher traffic rates (packets per second) while maintaining a low duty cycle (~2%). Under these extreme conditions, current duty cycled protocols collapse.

In the first video, we use SOFA to run a push-pull, gossip-based protocol that computes the average of the nodes’ values. Nodes’ values are shown in red, while the averages are shown in black. In the second video, we run SLICE, a push-pull, gossip-based protocol to automatically partition the nodes’ values into “slices”. In this case the nodes’ values (in red) are partitioned in percentiles (in black). The experiment was recorded in real-time speed (1x) in the TU Delft testbed.

Download pdf | Springer Library | SlidesSource code on GitHub

AuthorsMarco Cattani and Marco A. Zuniga and Matthias Woehrle and Koen G. Langendoen
Research group: Embedded Software group, Delft University of Technology, Delft, Netherlands
Conference11th European Conference on Wireless Sensor Network (EWSN)
Year: 2014