Le coût de la monotonie dans les stratégies d'encerclement réparti

Résumé : L'encerclement dans les réseaux vise à réaliser le nettoyage, par une équipe d'agents mobiles, d'un réseau contaminé. 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 de façon à assurer des communications sécurisées entre les agents, (2) monotonie : la zone nettoyée ne doit jamais être recontaminée, ce qui permet un temps de nettoyage polynomial en la taille du réseau, et (3) optimalité : le nombre d'agents utilisés doit être le plus petit possible afin de minimiser la taille des ressources utilisées. Etant donné un graphe G, le plus petit nombre d'agents nécessaire pour nettoyer G de façon monotone connexe dans un contexte centralisé est noté mcs(G). Plusieurs protocoles répartis ont été proposés pour résoudre le problème de l'encerclement dans les réseaux. Blin et al. ont proposé un algorithme distribué permettant à mcs(G) agents de déterminer et de réaliser une stratégie d'encerclement dans tout graphe inconnu G (inconnu signifie que les agents n'ont aucune connaissance a priori concernant le graphe) [AlgoTel'06]. Cependant, la stratégie réalisée n'est pas monotone et peut prendre un temps exponentiel. Nisse et Soguet ont prouvé que, pour résoudre le problème de l'encerclement dans les réseaux, il est nécessaire et suffisant de fournir $\Theta(n\log{n})$ bits d'information aux agents par le biais d'un étiquetage des sommets du graphe [AlgoTel'07]. Ainsi, pour nettoyer un graphe inconnu de façon monotone et connexe, il est nécessaire d'utiliser plus d'agents que l'optimal. Dans cet article, nous étudions la proportion d'agents supplémentaires qui sont nécessaires et suffisants pour nettoyer de façon monotone connexe répartie tout graphe inconnu. Nous montrons que la contrainte de monotonie implique une augmentation drastique de ce nombre d'agents. Nous prouvons que tout protocole distribué ayant pour but de nettoyer tout graphe inconnu de n sommets de façon monotone connexe répartie a un ratio compétitif de $\Theta(n/\log{ n})$. Plus précisément, nous prouvons que pour tout protocole distribué P, il existe une constante c tel que pour tout n suffisamment grand, il existe un graphe G de n sommets tel que P requiert au moins $c.n/\log{ n}$ mcs(G) agents pour nettoyer G. De plus, nous proposons un protocole distribué qui permet à $O(n/\log{ n})$ mcs(G) agents de nettoyer tout graphe inconnu G de n sommets, de façon monotone connexe répartie.
Type de document :
Communication dans un congrès
David and Sebastien Tixeuil. 10ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'08), 2008, Saint-Malo, France. pp.33-36, 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00374451
Contributeur : David Coudert <>
Soumis le : mercredi 8 avril 2009 - 17:02:07
Dernière modification le : jeudi 11 janvier 2018 - 06:20:36
Document(s) archivé(s) le : jeudi 10 juin 2010 - 20:06:02

Fichier

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

Identifiants

  • HAL Id : inria-00374451, version 1

Citation

David Ilcinkas, Nicolas Nisse, David Soguet. Le coût de la monotonie dans les stratégies d'encerclement réparti. David and Sebastien Tixeuil. 10ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'08), 2008, Saint-Malo, France. pp.33-36, 2008. 〈inria-00374451〉

Partager

Métriques

Consultations de la notice

183

Téléchargements de fichiers

34