Monitoring the density of mobile crowds with a lightweight cardinality estimator, by Marco Zuniga, TU Delft
Every year, open air festivals around the world gather people in the order of millions. Due to public safety, the density of people should not cross certain (dangerous) thresholds. In these scenarios, it is necessary to monitor constantly the local densities of crowds. As part of larger project, we aim at providing coin-size devices to attendees to help in the monitoring process. In this talk we will look at the problem of estimating the neighborhood cardinality of attendees, i.e. estimating the number of neighbors of each node. 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 evaluated 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.
Marco Zuniga is an Assistant Professor at the Department of Computer Science at Delft University of Technology, the Netherlands. Before this appointment, he was a member of the research staff at Xerox Research Labs (2006-2008); an IRCSET fellow at the National University of Ireland, Galway (2008-2010); and a senior researcher at the University of Duisburg-Essen, Germany (2010-2012). He obtained his PhD and MSc in Electrical Engineering from the University of Southern California and his BSc in Electronics Engineering from the Pontificia Universidad Catolica del Peru. His research interests are on the areas of wireless networks, mobile computing and cyber physical systems.
This is joint work with Marco Cattani, Andreas Loukas and Koen Langendoen.