Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Data Collection in Population Protocols with Non-uniformly Random Scheduler
verfasst von : Joffroy Beauquier, Janna Burman, Shay Kutten, Thomas Nowak, Chuan Xu
Erschienen in: Algorithms for Sensor Systems
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Contrary to many previous studies on population protocols using the uniformly random scheduler, we consider a more general non-uniform case. Here, pair-wise interactions between agents (moving and communicating devices) are assumed to be drawn non-uniformly at random. While such a scheduler is known to be relevant for modeling many practical networks, it is also known to make the formal analysis more difficult.
This study concerns data collection, a fundamental problem in mobile sensor networks (one of the target networks of population protocols). In this problem, pieces of information given to the agents (e.g., sensed values) should be delivered eventually to a predefined sink node without loss or duplication. Following an idea of the known deterministic protocol \({\mathrm {TTF}}\) solving this problem, we propose an adapted version of it and perform a complete formal analysis of execution times in expectation and with high probability (w.h.p.).
We further investigate the non-uniform model and address the important issue of energy consumption. The goal is to improve \({\mathrm {TTF}}\) in terms of energy complexity, while still keeping good time complexities (in expectation and w.h.p.). Namely, we propose a new parametrized protocol for data collection, called lazy \({\mathrm {TTF}}\), and present a study showing that a good choice of the protocol parameters can improve energy performances (compared to \({\mathrm {TTF}}\)), at a slight expense of time performance.