Computing Time Complexity of Population Protocols with Cover Times - The ZebraNet Example

Joffroy Beauquier 1, 2 Peva Blanchard 2 Janna Burman 1, 2 Sylvie Delaët 2
1 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : Population protocols are a communication model for large sensor networks with resource-limited mobile agents. The agents move asynchronously and communicate via pair-wise interactions. The original fairness assumption of this model involves a high level of asynchrony and prevents an evaluation of the convergence time of a protocol (via deterministic means). The introduction of some "partial synchrony" in the model, under the form of cover times, is an extension that allows evaluating the time complexities. In this paper, we take advantage of this extension and study a data collection protocol used in the ZebraNet project for the wild-life tracking of zebras in a reserve in central Kenya. In ZebraNet, sensors are attached to zebras and the sensed data is collected regularly by a mobile base station crossing the area. The data collection protocol of ZebraNet has been analyzed through simulations, but to our knowledge, this is the rst time, that a purely analytical study is presented. Our first result is that, in the original protocol, some data may never be delivered to the base station. We then propose two slightly modify ed and correct protocols and we compute their worst case time complexities. Still, in both cases, the result is far from the optimal.
Type de document :
Communication dans un congrès
Stabilization, Safety, and Security of Distributed Systems - 13th International Symposium, SSS 2011, Oct 2011, Grenoble, France. 2011, 〈10.1007/978-3-642-24550-3_6〉
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00639583
Contributeur : Janna Burman <>
Soumis le : mardi 22 novembre 2011 - 16:42:16
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : vendredi 16 novembre 2012 - 11:40:59

Fichier

paper_61.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Joffroy Beauquier, Peva Blanchard, Janna Burman, Sylvie Delaët. Computing Time Complexity of Population Protocols with Cover Times - The ZebraNet Example. Stabilization, Safety, and Security of Distributed Systems - 13th International Symposium, SSS 2011, Oct 2011, Grenoble, France. 2011, 〈10.1007/978-3-642-24550-3_6〉. 〈hal-00639583〉

Partager

Métriques

Consultations de la notice

505

Téléchargements de fichiers

136