Lightweight Neighborhood Cardinality Estimation in Dynamic Wireless Networks

Marco Cattani, Marco Zuniga , Andrea Loukas, Koen Langendoen

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

17 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationIPSN'14
Subtitle of host publicationProceedings of the 13th international symposium on Information processing in sensor networks
Number of pages11
ISBN (Print)978-1-4799-3146-0
Publication statusPublished - 2014
Event13th IEEE/ACM International Conference on Information Processing in Sensor Networks, IPSN 2014 - Berlin, Germany
Duration: 15 Apr 201417 Apr 2014


Conference13th IEEE/ACM International Conference on Information Processing in Sensor Networks, IPSN 2014


  • Wireless Communications
  • Modeling
  • performance evaluation


Dive into the research topics of 'Lightweight Neighborhood Cardinality Estimation in Dynamic Wireless Networks'. Together they form a unique fingerprint.

Cite this