Soutenance mémoire
État de l’art
Les graphes sont utilisés pour représenter bien des problèmes, et il s’agit d’un domaine bien étudié en informatique. Pour représenter ces réseaux de contacts un graphe dynamique est souvent utilisé, dans lequel les personnes sont représentées par des noeuds et leurs interactions par des arêtes bidirectionnelles entre les noeuds, associées au moment où a lieu le contact.
Mais l’évolution de tels graphes est longtemps restée peu étudiée. La question se pose de savoir quelles propriétés des graphes statiques restent valides pour ces graphes dynamiques. À l’heure actuelle, nous manquons encore d’outils et de notions permettant de décrire la dynamique de tels graphes. Ceci est cependant crucial et pas uniquement pour des applications de communication ad hoc mais aussi dans un contexte bien plus large comme l’analyse de la topologie de l’internet, les graphes du web ou encore certains réseaux sociaux.
Dans un premier temps nous explorerons les différentes expérimentations en environnement réel qui ont été menées ces dernières années. Puis nous étudierons les différentes représentations utilisés dans la littérature pour les réseaux de contacts ainsi que les analyses qui ont été faites sur les données expérimentales. Dans la partie 2.3 les problématiques de modélisation de ces graphes seront discutées. Enfin une revue des propositions de protocoles de routage adaptés aux scénarios étudiés ainsi que des techniques d’évaluations de protocoles de routages sera présentée.
Expériences en environnement réel
Pour être capable de représenter des cas réels d’application, l’étude et l’obtention de données réelles par de larges expérimentations est nécessaire. Dans cette optique de nombreux travaux ont étés réalisés, où un ensemble de personnes étaient suivies pendant des durées très variables. Au MIT un groupe d’élèves et de professeurs d’informatique a été équipé de capteurs communicants traçant l’historique de leurs contacts pendant 9 mois. Pendant plusieurs années une expérience similaire à été effectuée à l’université Cambridge. D’autres expériences ont été menées dans des environnements plus restreints, montrant des comportements parfois bien spécifiques.
Pour la réalisation de ces expériences des petits systèmes embarqués capables de communiquer entre eux et de stocker l’historique des contacts aperçus au cours du temps sont nécessaires.
Dans les deux études détaillées dans [7] et [17] des Intel Imotes sont utilisés. Il s’agir d’un système embarqué sur puce possédant la technologie Bluetooth, une mémoire et un processeur capable de traiter les contacts recensés au cours du temps. En plus de ces appareils distribués à quelques personnes du groupe, les téléphones portables possédant la technologie Bluetooth sont aussi recensés par les Imotes afin d’élargir l’ensemble des observations. Les Imotes listent les appareils périodiquement et repèrent les nouveaux arrivants et les disparitions et archivent des dates de début et fin du contact. Les traces fournies par l’ensemble des Imotes sont regroupées à la fin de l’expérience afin de modéliser un graphe dynamique de l’expérience pour l’analyser et faire des simulations sur ce scénario.
Analyse de l’expérience Infocom
Dans l’article [7], une expérience est présentée et commentée. Quelques dizaines de personnes assistant à la conférence Infocom 2005 ont été suivies pendant 3 jours. Les auteurs étudient plusieurs aspects de l’expérience.
En premier lieu, une étude approfondie est faite sur les durées des contacts et les durées entre des contacts successifs. L’observation essentielle qui en résulte est que ces distributions suivent des lois de puissance que ce soit pour les contacts entre Imotes ou avec les téléphones portables. De plus il est montré que la distribution du nombre de contacts parmi les membres de l’expérience n’est pas uniforme, certains participants sont repérés de manière bien plus fréquente que d’autres. Or, bien que les simulateurs existants prennent en compte la distribution en loi de puissance des durées de contact et inter-contact, ils font l’hypothèse en général d’un comportement uniforme parmi les agents.
Un autre point intéressant est discuté dans l’article. Lors de l’expérience, des communautés plus ou moins restrictives ont étés observées, dans lesquelles la fréquence des contacts des membres est plus élevée que la moyenne. Ceci est un point clef à prendre en compte pour créer des algorithmes de routage efficaces, car en effet transmettre l’information à un membre de la même communauté que le destinataire de manière privilégiée permet d’obtenir une plus grande efficacité que lors d’un choix aléatoire de l’intermédiaire.
Enfin, une dernière étude est faite sur l’évolution quotidienne des contacts. Elle montre la présence d’une forte corrélation entre la dynamique des différents jours vis à vis des différentes périodes de la journée. Ce dernier point n’est en général pas modélisé dans l’étude des réseaux de contacts, pourtant il est important de prendre en compte ces aspects pour la mise au point d’algorithmes de routage adaptés à des usages réalistes.
L’expérience fut réitérée l’année suivante à la conférence Infocom 2006 [15]. Pour cette seconde édition, le nombre d’Imotes distribués à presque doublé et en plus une vingtaine d’Imotes ont été installés à des positions fixes dans les principaux lieux de passage de l’hôtel accueillant la conférence.
RollerNet
L’article [17] présente l’expérience RollerNet où quelques dizaines de participants d’une randonnée roller se passant à Paris un dimanche après-midi sont équipés d’Imotes.
Un phénomène très spécifique au scénario est observé, le phénomène dit d’accordéon. Au cours de la randonnée des phases d’accélération et de ralentissement de la tête de la randonnée provoquent des étirements et rétrécissements du groupe des randonneurs. Ce phénomène s’observe bien par la variation du nombre de contacts recensés au cours de ces différentes phases ainsi que par l’augmentation du nombre de composantes connexes. Une étude plus détaillée du phénomène montre qu’il est bien plus marqué dans les randonneurs proches de la tête de la randonnée alors qu’il est bien moins prononcé pour ceux à l’arrière. Ceci s’explique facilement par l’effet d’accordéon du fait des pauses et des accélérations successives effectuées par le front de tête de la randonnée pour respecter les contraintes de circulation.
Une brève étude des distributions des temps de contacts et d’inter-contacts viennent confirmer que ces distributions respectent une loi de puissance comme précédemment observé dans l’expérience faite à la conférence Infocom 2005 avec cependant des coefficients différents.
Représentation et propriétés des réseaux de contacts
Avant tout travail d’analyse et de modélisation, la question de la structure de données à utiliser afin de proposer une représentation adéquate de réseaux de contacts est nécessaire.
Plusieurs approches différentes sont étudiées dans la littérature. Un graphe dynamique, où les arêtes sont étiquetées par les temps discrets ou intervalles des moments d’activité du contact associé, permet de représenter sans pertes d’information ces réseaux. D’autres représentations plus proches des données expérimentales sont aussi étudiées, consistant généralement en une liste des contacts observés, soit de manière centralisée, soit distribuée relativement à chaque agent. Cette dernière représentation étant généralement peu adaptée à l’analyse des dynamiques et propriétés du réseau, mais pouvant être notamment utilisée pour effectuer des simulations.
Résultats sur les graphes dynamiques
Quelques rares travaux proposent des résultats théoriques sur des graphes dynamiques.
Dans [8], la validité dans le cas dynamique de propriétés des graphes statiques est étudiée.
Plus précisément les auteurs démontrent que le théorème de Menger, qui stipule que le nombre maximum de chemins qui ne se recoupent pas entre deux noeuds s et t est strictement égal au nombre minimal de noeuds à retirer du graphe pour déconnecter s et t, n’est plus valable. Les auteurs montrent que le nombre de chemins respectant l’ordre temporel entre deux noeuds, utilisant une séquence d’arêtes existant à des temps croissants, peut être strictement inférieur au nombre de noeuds à retirer pour les déconnecter. Un exemple est présenté dans la figure 2.1.
Les auteurs vont plus loin dans l’étude de la propriété et ils arrivent à prouver qu’un graphe ne respecte pas le théorème de Menger si et seulement si il possède une sous division du graphe Z de la figure 2.1, c’est à dire s’il ne possède pas un sous graphe qui peut s’obtenir en rajoutant des noeuds sur les arêtes du graphe Z.
Dans le même article est proposé un algorithme résolvant un problème d’inférence sur un graphe dynamique à information partielle. Plus précisément le problème résolu est de savoir si dans un graphe dynamique où le moment précis des contacts est méconnu (allant d’une date quelconque à une date restreinte à un intervalle), on peut déterminer si pour deux partitions données un scénario est possible dans lequel une source fixe peut joindre par un chemin respectant l’ordre causal l’ensemble des noeuds d’une partition mais aucun de l’autre. Ce problème de connectivité n’est pas posé dans les expériences décrites dans la section suivante. Ce problème est pertinent lors de cas de données avec des observations à information partielles afin de déterminer si un scénario précis de dissémination est possible. Des données de ce type sont fréquemment trouvées aussi bien pour des raisons techniques d’acquisition que dues à la représentation sous forme de séquence de graphes statiques, où une partie de l’information est perdue.
Représentation sous forme de séquence de graphes statiques
Dans de nombreux travaux, les réseaux de contacts sont représentés comme une séquence de graphes statiques. La dynamique étant représentée par cette série de graphes statiques.
Chaque graphe représente une période de temps où sont agglomérés tous les contacts qui ont eu lieu. Cette représentation présente l’avantage de transformer l’analyse de graphes dynamique en une séquence d’analyse de graphes statiques, ce qui est bien documenté dans la littérature. Un des points épineux de cette représentation est le choix de la durée entre deux graphes successifs. En effet, un temps trop court et le graphe se retrouve presque sans observations de contacts, sans apporter d’informations pertinentes, et un temps trop long implique que la dynamique du réseau de contact est totalement perdue.
Une étude autour de la sélection appropriée de ce temps est proposée dans l’article [4] afin de limiter la perte d’informations pertinentes sur la dynamique de graphe. Les auteurs se servent des données produites par une expérience réalisée au sein du MIT pour effectuer leur analyse. Ils analysent les rythmes d’évolution des communautés au sein du réseau de contacts pour déterminer un temps caractéristique d’évolution du graphe. Afin de mesurer l’évolution du graphe trois mesures sont utilisées :
– le degré moyen des noeuds du graphe représentant la densité ;
– la valeur moyenne du coefficient de clustering mesurant l’importance des communautés au sein du graphe ;
– une mesure de corrélation des voisinages des noeuds mesurant les ressemblances des contacts actifs des différents noeuds.
Grâce à l’étude extensive des auto-corrélations de ces valeurs pour différents intervalles de temps entre deux états considérés du graphe, les auteurs arrivent à repérer des motifs de ressemblance de l’état du graphe tous les 8, 16 et 24 heures. Le motif journalier étant largement le plus évident. Ils proposent donc en conséquence une valeur d’environ 4 heures comme temps caractéristique de l’évolution du graphe à utiliser pour séquencer le graphe. Cette valeur permet de bien capturer les différentes phases d’évolutions et motifs journaliers.
Analyse simultanée poussée de deux expérimentations
A. Scherrer et Coll. présentent dans l’article [14] une analyse poussée prenant en compte de nombreux paramètres et propriétés des réseaux de contacts étudiés. Leur analyse est effectuée conjointement sur deux ensembles de données d’expériences, ceux de la conférence Infocom 2005 détaillée précédemment et sur du MIT Realty Mining [5] mentionné précédemment et résultant des traces des contacts d’une centaine de membres du département d’informatique de l’université pendant 9 mois.
Lors de leur étude un très large spectre de propriétés est étudié ; les distributions des durées des contacts et inter-contacts ainsi que des coefficients de clustering mais aussi de manière originale des taux de suppression et d’apparition d’arêtes dans le réseaux ainsi que le nombre de triangles dans le graphe (trois personnes en contact simultané). Leur étude utilise une représentation sous forme de séquence de graphes statiques, mais pour être sûr de ne pas perdre d’information le temps d’échantillonnage est fixé à 1s afin de capturer de manière certaine toute évolution. L’étude sur les distributions des durées des contacts et inter-contacts vient confirmer les résultats existants stipulant que ces distributions suivent bien une loi de puissance.
Analyse statistique des propriétés structurelles
De manière similaire à l’étude effectuée dans [4], les auto-corrélations temporelles des différentes propriétés des graphes statiques sont calculées pour estimer leur temps moyen d’évolution.
Des résultats similaires sont trouvés pour l’ensemble des mesures sauf en ce qui concerne la création et suppression d’arêtes qui évoluent de manière bien plus rapide. Ensuite des calculs des moyennes des corrélations croisées des différentes propriétés sont effectués et il en ressort une très forte corrélation des différentes propriétés avec des valeurs allant de 0.5 à 0.9, hors ajout et suppression d’arêtes qui sont totalement dé-corrélés. Cette étude montre que les ajouts et suppressions d’arêtes peuvent être considérés comme indépendants, mais qu’une telle hypothèse pour les autres propriétés serait fortement dommageable notamment pour effectuer une simulation. Les résultats obtenus relativement aux ajouts et suppressions d’arêtes montrent des temps caractéristiques d’évolution et des taux de corrélation tellement faibles qu’ils peuvent être considérés comme des processus aléatoires sans mémoire, et donc Markovien, sans perte significative d’information sur le réseau.
Enfin, une analyse sur l’évolution de différents paramètres de la structure du graphe représentant le réseau de contacts est effectuée. Dans un premier temps les auteurs caractérisent la stabilité temporelle des composantes connexes. Globalement, ils montrent que les trois quarts des ajouts et suppressions d’arêtes correspondent à des modifications de composantes connexes existantes. Le quart restant correspondant à une disparition d’une composante connexe ou à l’apparition d’une nouvelle composante connexe ; une autre possibilité étant aussi la séparation en deux d’une composante connexe ou la fusion de deux composantes connexes.
Dans un second temps, la densité de triangles dans le graphe est étudiée. Les auteurs montrent que pour les réseaux de contacts étudiés l’ajout d’une arête a quatre fois plus de chances d’ajouter un triangle dans le graphe que pour un graphe aléatoire. Ce résultat caractérise bien le fait que deux personnes en contact, et donc à proximité d’une troisième, ont de fortes chances d’être en contact entre elles.
Émergence de communautés
Les auteurs s’intéressent aussi aux communautés présentes dans le graphe, une communauté étant un ensemble de personnes ayant plus d’interactions entre elles que la moyenne.
Ces communautés ne sont pas capturées par l’étude des composantes connexes, bien que les membres d’une même communauté se retrouveront en général régulièrement au sein d’une même composante connexe. Trouver les communautés au sein du réseau de contacts n’est pas facile, trouver les communautés d’un graphe étant NP-difficile. Bien que la plupart des approches dans la littérature utilisent des heuristiques, une résolution exacte est privilégiée dans cet article. La méthode utilisée consiste à trier les couples de noeuds communiquant plus qu’une limite fixée et ensuite de les regrouper par composantes connexes, les composantes connexes n’ayant pas suffisamment d’interconnexions étant retirées ainsi que les composantes connexes qui ne sont pas assez denses. Ces communautés sont repérées pour de petits intervalles de temps, les résultats des différents intervalles étant ensuite réunis en regroupant les communautés qui diffèrent pour peu d’individus et plages temporelles. Les communautés trop peu représentées dans le temps ne sont pas retenues. Les résultats obtenus sur les expériences de réseaux de contacts étudiées repèrent une dizaine de communautés, certains individus pouvant faire partie de plusieurs communautés à la fois.
Modélisations de réseaux de contacts
CTG : Générateur de traces de contacts
Une autre modélisation est proposée dans [3]. Le but est de simuler un réseau de contact des propriétés choisies et de générer des traces ressemblant à celles d’une expérience qui est donnée en entrée au simulateur. La modélisation du réseau de contacts est relativement simple, un graphe de taille et de distribution de degrés de noeuds données est généré aléatoirement.
Ce graphe représente le réseau de contacts sans informations sur les moments où les contacts sont actifs. Ensuite la simulation du réseau de contact est effectuée à partir d’un état initial sans contact actif et pour chaque contact la durée avant commutation de actif vers inactif et inversement est choisie aléatoirement en respectant les distributions des temps de contacts et inter-contacts fournies. Une modélisation en loi de puissance est utilisée pour ces distributions dans le simulateur.
En utilisant des paramètres extraits d’une expérience réelle, les auteurs montrent que les paramètres extraits du résultat de la simulation correspondent bien à ceux de l’expérience réelle utilisée. Cette comparaison est uniquement effectuée sur les distributions fournies en entrée au simulateur et sans utiliser aucune autre propriété des deux réseaux de contacts. Les variables aléatoires étant choisies pour respecter ces distributions, le résultat n’est pas très pertinent en soi car il est imposé par la simulation. Aucune autre validation du modèle présenté n’est proposée.
Le générateur de traces ainsi présenté permet d’effectuer de nombreuses simulations répliquant des scénarios d’expériences réelles. De plus le simulateur permet de faire varier indépendamment les ordres de grandeur des durées de contact et inter-contact en faisant varier le coefficient de la loi de puissance utilisée. Enfin le nombre de participants à la simulation peut aussi être modifié à souhait. Pour que la distribution des degrés des noeuds du graphe reste cohérente, il est proposé d’appliquer une homothétie sur la distribution utilisée. Une étude sur le passage à l’échelle des applications utilisant des réseaux de contacts peut donc être menée avec ce simulateur et cela indépendamment pour les trois propriétés traitées.
Dans le papier [14], dont l’analyse des réseaux de contacts a déjà été discutée en section 2.2.3, les résultats de l’analyse sont utilisés dans le but de proposer et d’évaluer des modélisations de réseaux de contacts similaires à ceux des expériences étudiées.
Description des modèles proposés
Tous les modèles qui sont proposés possèdent le même squelette. Leur approche se base en tout premier sur un résultat très utile de leur analyse ; l’ajout et la suppression d’arêtes peuvent être considérés comme un processus markovien. Ceci implique pour la simulation de la dynamique du graphe que les changements d’état des arêtes sont indépendants entre eux pour chaque pas de temps. La modélisation consiste à calculer une probabilité Ptr(e, Gt) à chaque pas de temps et pour chaque arête, l’état de l’arête étant permuté si cette valeur dépasse un seuil. Dans un premier temps, cette probabilité est calculée de manière à respecter les distributions des durées de contacts et d’inter-contacts.
Dans un second temps, des pondérations sont rajoutées au calcul de la probabilité de transition pour forcer le graphe simulé à respecter les distributions des propriétés structurelles telles que le nombre d’arêtes, le nombre de noeuds connectés, le nombre de composantes connexes ou le degré moyen des noeuds connectés. Ceci étant fait en multipliant par un poids inférieur ou égal à 1 le précédent calcul de la probabilité de changement d’état. Ce poids est déterminé par le ratio entre les mesures du respect des propriétés structurelles à imposer avec ou sans changement de l’arête. Enfin un second poids est ajouté pour favoriser la création d’arête en ajoutant un triangle au graphe, en fonction des résultats mesurés dans l’analyse sur les expérimentations.
Évaluation des modèles proposés
Au total six modélisations différentes sont évaluées. Les propriétés structurelles étant fortement corrélées, il n’est pas très pertinent de chercher à toutes les imposer en même temps.
Sont étudiées les modélisations sans propriétés structurelles, avec la propriété du nombre de noeuds connectés et avec la propriété du nombre de composantes connexes. Les modèles imposant le nombre d’arêtes ou le degré moyen des noeuds connectés ne sont pas évalués, ces propriétés étant très fortement corrélées avec l’une des deux propriétés structurelles déjà évaluées.
Enfin pour les trois cas décrits, les mêmes modélisations, avec en plus une pondération afin de respecter le taux de création d’arêtes créant de nouveaux triangles dans le graphe, sont aussi évaluées.
La première observation faite sur les résultats des simulations est la disparition des phénomènes de variance de la densité du graphe causés par des événements propres à l’expérimentation tels que les pauses repas ou les déplacements du groupe suivi. Ensuite lorsque l’on s’intéresse au respect des distributions des différentes mesures structurelles du graphe, le modèle prenant en compte uniquement le respect des durées de contacts et inter-contacts montre des limitations. Le nombre total de noeuds connectés est surévalué, alors que le nombre de composantes connexes et le nombre de triangles sont sous évalués. Ensuite, et cela est valable pour les trois modèles, les distributions des différentes mesures structurelles sont bien moins variables. Cette observation s’explique aisément par la non stationnarité des données de l’ex- périence pour des raisons identiques à celles expliquant la première observation. Un dernier
point en faveur des modèles pondérés est le non-respect total de la distribution de la densité parmi les composantes connexes fréquentes dans le premier modèle alors que les autres modèles fournissent eux un très bon respect de la distribution observée expérimentalement. Dans l’ensemble aucune observation ne permet de privilégier l’un des deux modèles pondérés.
Des observations sur la structure des graphe graphes modélisés montrent certaines limitations des trois modèles proposés. Le nombre de triangles dans le graphe est fortement sous évalué et la densité des arêtes au sein des composantes connexes est relativement constante alors qu’elle devrait croître avec la taille de la composante connexe, les densités observées représentant uniquement les cas minimaux observés dans les expériences. Lorsque les modèles avec prise en compte du nombre de triangles sont testés, la sous-évaluation disparaît presque totalement. D’un autre côté, ces modèles surévaluent légèrement le nombre total de composantes connexes.
Évaluation de protocoles de routage pour réseaux de contacts
Evaluation à l’aide de CTG
Dans le papier [3] décrivant CTG (Connectivity Trace Generator), une analyse de différents protocoles de routage est effectuée sur les simulations générées par l’outil à partir des traces de l’expérience menée à l’université de Dartmouth [11]. Quatre protocoles sont testés : les protocoles de références d’inondation et de diffusion épidémique ainsi que le protocole de Context-Aware Adaptive Routing (CAR) [12]. Ce dernier sélectionne le porteur ayant la plus grande probabilité de délivrer le message au destinataire parmi les contacts à portée. Enfin une version simplifiée où le porteur est choisi aléatoirement est également étudiée pour fournir une référence.
Grâce aux possibilités fournies par le simulateur CTG, l’efficacité en termes de délais, taux de livraison et nombre de messages transmis est calculée en faisant varier différentes caractéristiques du réseau. Les résultats sont fournis pour des variations du coefficient de la loi de puissance utilisée pour les distributions des durées moyennes des contacts et inter-contacts, ainsi que pour la distribution de la densité des contacts simultanés.
Les résultats obtenus pour les variations de durée moyennes des contacts et inter-contacts sont symétriques. Le protocole de dissémination épidémique donne les meilleurs résultats quelles que soient les distributions des durées des contacts et inter-contacts, avec un taux de délivrance autour de 60% dans tous les cas testés. Cependant le nombre de messages envoyés est de l’ordre de cinq fois supérieur aux protocoles utilisant un porteur. Les délais de livraisons augmentent logiquement pour tous les protocoles (sauf inondation) lorsque les durées moyennes de contacts et inter-contacts augmentent et que pour ces protocoles l’on observe dans tous les cas testés l’ordre croissant aléatoire-épidémique-CAR pour le taux de délivrance.
En termes de taux de délivrance les protocoles utilisant un porteur deviennent de moins en moins efficaces, de 50% à 40% pour CAR et de 40% à moins de 10% pour la version aléatoire.
Cette décroissance résulte de la difficulté à prédire le bon porteur pour des évolutions lentes du réseau. Le protocole d’inondation de son côté utilise un nombre extrêmement grand de messages et un taux de délivrance extrêmement faible dans tous les cas à cause de la petite taille des composantes connexes, montrant son inadaptation à de tels réseaux de type DTN ne possédant pas de composante majoritaire connexe. Enfin les résultats sur les différentes distri- butions de densité montrent uniquement une amélioration des performances quand la densité du réseau augmente, sans différencier davantage les comportements des différents protocoles.
Cette évaluation de protocoles sur de nombreux paramètres à l’aide de CTG montre l’efficacité et la robustesse du protocole épidémique dans de tels réseaux bien qu’elle montre qu’un nombre important de messages redondants est transmis. Le protocole CAR se démarque bien aussi car il a l’avantage d’être économe en messages envoyés et d’impliquer de faibles baisses du taux de délivrance, cependant une augmentation significative du délai est observée. Les résultats de CAR sont bien meilleurs que ceux d’un protocole similaire avec un choix aléatoire du porteur utilisé. Le choix d’utiliser plutôt le protocole épidémique que le protocole CAR doit donc se baser sur l’importance des différentes caractéristiques, à savoir les performances en termes de délai et taux de délivrance ou l’utilisation économique des ressources de communication respectivement.
Analyse de protocoles pour RollerNet
Le comportement de quatre protocoles est étudié dans l’article [17] sur le scénario de l’expérience RollerNet. Le cas étudié est celui de la transmission d’une information depuis l’arrière de la randonnée vers un destinataire en tête.
Le premier protocole est le protocole épidémique qui consiste en une transmission instantanée de l’information à tous ses contacts. Ce protocole est mal adapté au scénario : lors des phases d’étirement du groupe l’information ne se répand pas à travers l’ensemble des randonneurs et n’atteint pas le devant de la randonnée. De plus, notamment lors des phases denses de la randonnée, de nombreux messages redondants sont envoyés. Ce protocole sert avant tout de base de comparaison avec des protocoles plus complexes.
Ensuite le protocole de Spay-and-Wait est testé. Ce protocole consiste en la création d’un nombre limité de copies de l’information. Tant que plusieurs copies sont détenues, l’information est transmise périodiquement à ses contacts en partageant les copies. Si une seule copie est détenue, l’information est transmise uniquement au destinataire du message. Différents nombres de copies sont testés avec le scénario. Suivant les différentes phases du phénomène d’accordéon le délai de transmission du message est très variable. Plus le nombre de copies est élevé et plus le délai de transmission est faible, avec en contrepartie un nombre de redondances bien plus élevé dans les messages transmis.
Enfin, ce dernier protocole est modifié afin de s’adapter dynamiquement au scénario de RollerNet. Pour cela l’algorithme de Spay-and-Wait est modifié pour choisir en fonction de la densité de son voisinage le nombre de copies à diffuser pour avoir un délai constant. Le nombre copies à envoyer étant choisi en fonction. Cette correspondance entre nombre de copies à transmettre et densité du voisinage est calibrée grâce aux traces de l’expérience. Ce protocole permet une bonne adaptation au phénomène d’accordéon observé, les tests effectués montrent que l’information est transmise en temps presque constant et que la redondance est bien limitée dans les phases de rétrécissement de la randonnée.
L’étude des protocoles de transmission d’information effectuée dans l’article [17] montre l’importance de la prise en compte du scénario caractérisant le réseau de contacts pour le choix d’un protocole adapté. Il propose une adaptation de protocoles existant pour les besoins spécifiques du scénario de RollerNet montrant des performances bien meilleures que les autres protocoles qui ne prennent pas en compte le phénomène d’accordéon.
|
Table des matières
1 Introduction
2 État de l’art
2.1 Expériences en environnement réel
2.2 Représentation et propriétés des réseaux de contacts
2.2.1 Résultats sur les graphes dynamiques
2.2.2 Représentation sous forme de séquence de graphes statiques
2.2.3 Analyse simultanée poussée de deux expérimentations
2.3 Modélisations de réseaux de contacts
2.4 Évaluation de protocoles de routage pour réseaux de contacts
3 Analyse des propriétés générales des jeux de données utilisés
3.1 Rollernet
3.2 Infocom
3.3 Pnas
4 Étude de l’importance des noeuds dans la diffusion
4.1 Étude détaillée pour un temps de départ fixé
4.1.1 Résultats globaux des phénomènes de diffusion
4.1.2 Résultats obtenus par isolement des différentes sources
4.1.3 Résultats obtenus par isolement des différents destinataires
4.2 Étude généralisée à tous temps de départ
4.2.1 Algorithme développé
4.2.2 Évolution de l’importance des noeuds au cours du temps
4.3 Calcul du nombre de messages en transit au cours du temps
5 Analyse des résultats et discussion
5.1 Résultats pour différents jeux de données
5.1.1 Infocom
5.1.2 Pnas
5.2 Comparaison entre différentes mesures de centralités dynamiques
6 Conclusion et perspectives
Télécharger le rapport complet
