Data collection in population protocols with non-uniformly random scheduler
Résumé
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., sensor readings) should be eventually delivered to a predefined sink node without loss or duplication. Following an idea of the known deterministic protocol 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 important issue of energy consumption. The goal is to improve TTF in terms of energy complexity, while still keeping good time complexities (in expectation and w.h.p.). Namely, we propose a new parameterized protocol for data collection, called lazy TTF, and present a study showing that an appropriate choice of the protocol parameters can considerably improve energy performances (compared to TTF), at a slight expense of time performance.