Stratégies d'encerclement avec information

Résumé : Dans le cadre de l'algorithmique réparti dans les réseaux, l'efficacité d'un algorithme dépend très fortement de la connaissance du réseau, disponible a priori. Très souvent, cette connaissance a priori est de nature qualitative (taille du réseau, son diamètre, etc.). Fraigniaud et al. (2006) ont introduit une mesure quantitative de la complexité d'une tâche répartie dans un réseau. Etant donné un problème réparti, cette mesure, la taille d'oracle, consiste en le plus petit nombre de bits d'information dont doit disposer l'algorithme pour résoudre le problème efficacement. Nous nous intéressons à la taille d'oracle permettant de résoudre efficacement l'encerclement dans les graphes. L'encerclement dans les réseaux vise à réaliser la capture d'un fugitif invisible, arbitrairement rapide et omniscient, par une équipe d'agents mobiles, dans un réseau. La stratégie d'encerclement est calculée en temps réel, par les agents eux mêmes, et doit vérifier les trois propriétés suivantes: (1) connexité : la zone nettoyée doit toujours être connexe, (2) monotonie : la zone nettoyée ne doit jamais être recontaminée, et (3) optimalité : le nombre d'agents utilisés doit être le plus petit possible. Les deux premières contraintes assurent des communications sécurisées entre les agents, ainsi qu'un temps de nettoyage polynomial en la taille du réseau. La troisième propriété assure une taille minimum des ressources utilisées. La seule connaissance, concernant le réseau, dont les agents disposent a priori, est modélisée par un oracle qui répartit sur les noeuds du réseau une chaÎne de bits d'information. Nous prouvons que la taille d'oracle pour résoudre l'encerclement est O(n log n) bits, avec n la taille du réseau, et que cette borne est optimale. Plus précisément, nous proposons un étiquetage des sommets, de taille O(n log n) bits, et un protocole réparti utilisant cet étiquetage. Ce protocole permet à une équipe d'agents, dont la mémoire est de taille O(log n) bits, de nettoyer le réseau de façon optimale monotone et connexe. Ce protocole améliore le protocole proposé par Blin et al. (2006) qui ne dispose d'aucune information a priori et, de ce fait, nécessite un temps de nettoyage exponentiel. De plus, nous prouvons qu'il n'existe pas de protocole réparti utilisant un oracle de taille o(n log n) bits qui permette de nettoyer tous les réseaux de façon optimale monotone et connexe.
Type de document :
Communication dans un congrès
9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. 2007
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00176935
Contributeur : David Coudert <>
Soumis le : jeudi 4 octobre 2007 - 22:48:44
Dernière modification le : mardi 24 avril 2018 - 13:38:27
Document(s) archivé(s) le : jeudi 27 septembre 2012 - 12:55:50

Fichier

04-NisseSoguet.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00176935, version 1

Collections

Citation

Nicolas Nisse, David Soguet. Stratégies d'encerclement avec information. 9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. 2007. 〈inria-00176935〉

Partager

Métriques

Consultations de la notice

162

Téléchargements de fichiers

59