Étude de l’importance des nœuds dans la diffusion

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 nœuds 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 nœuds 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é P tr (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 nœuds connectés, le nombre de composantes connexes ou le degré moyen des nœuds 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 nœuds 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 nœuds 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 nœuds 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-9 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.

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.

Analyse des propriétés générales des jeux de données utilisés

Trois jeux de données seront présentés dans ce rapport.

Il s’agit de données déjà largement étudiées, notamment par une étudiante en thèse du LIP6 à l’UPMC, Lamia Benamara, et je me réfère à sa thèse soutenue en novembre 2011 [1] car de nombreuses analyses des propriétés générales des trois jeux de données ont déjà présentées dans son mémoire. Je redonne ici les principales caractéristiques de ces trois jeux de données de réseaux de contacts.
Les fichiers de données contiennent un nombre variables de contacts, listés sous la forme de quadruplets ( I 1, I 2, Td, T f ) où I 1 et I 2 sont les identifiants des personnes pour lesquelles un contact a été enregistré entre un temps de début Td et un temps de fin T f.
J’ai aussi recherché d’autres jeux de données de réseaux de contacts, et conduit sur ces réseaux des analyses du même type que celles qui sont présentées dans les chapitres suivants.Mais j’ai préféré mettre ici l’accent sur la méthodologie sans inclure une longue annexe avec une séries de résultats sous forme de graphiques supplémentaires. Les résultats ne seront donc présentés que pour ces trois jeux de données étant assez représentatifs des réseaux de contacts disponibles.

Rollernet

Comme indiqué en introduction, il s’agit de données recueillies lors d’une randonnée en roller organisée à Paris en 2009 [17], où 62 participants ont été équipés de capteurs iMote. Chaque capteur effectue des scans toutes les 15 secondes. La durée totale de la randonnée est d’environ 3 heures, avec deux sessions de 80 minutes et une pause de 20 minutes. Le jeu de données contient environ 60 000 contacts. Pour avoir un aperçu de l’évolution du jeu de donné, la figure 3.1a présente la moyenne du temps minimal requis pour transmettre un message dans le réseau.

Étude de l’importance des nœuds dans la diffusion

Étude détaillée pour un temps de départ fixé

Cette étude a pour but de caractériser dans le plus grand détail l’importance que peut avoir un nœud dans une transmission de message sur le réseau.
Le temps de transmission n’est pas pris en compte dans l’étude et un contact ayant une durée nulle peut servir à la transmission d’un message. De plus le protocole utilisé est le protocole dit d’inondation, ce protocole consiste à transmettre l’information dès que possible à tous les nœuds à portée qui ne connaissent pas encore l’information. Ce protocole est très coûteux en nombre de messages transmis mais est optimal en temps nécessaire pour transmettre un message. Ce protocole permet donc de repérer les chemins les plus courts pour transmettre l’information d’un nœud donné à un autre.
La méthodologie utilisée pour caractériser l’importance d’un nœud pour la diffusion d’information consiste à comparer le phénomène de diffusion dans le réseau complet et dans le réseau sans le nœud étudié. Pour cela le temps minimal nécessaire pour transmettre un message depuis chaque nœud du réseau vers l’ensemble des autres est calculé pour tous les retraits possibles d’un nœud du réseau.

Résultats globaux des phénomènes de diffusion

La figure 4.1 présente la distribution cumulative normalisée du temps de diffusion entre toutes les paires de nœuds pour le réseau complet, ainsi que les réseaux obtenus quand on enlève les nœuds 3, 29, 32 et 53 respectivement. Ces nœuds ont été sélectionnés car ils sont représentatifs des types de comportements observées et des catégories de participants. Les nœuds 29 et 32 font partie des organisateurs et se situent à l’avant de la randonnée, respectivement sur le côté gauche et le côté droit. Le nœud 53 est un ami de l’auteur, rollerman occasionnel, alors que le nœud 3 fait partie d’une association d’habitués ayant plus de chance de faire des déplacements rapides.

Résultats obtenus par isolement des différentes sources

Afin d’obtenir une compréhension plus fine de l’impact d’un nœud donné lors de la diffusion, une étude poussée a été effectuée en isolant les sources d’émission de l’information. Ceci augmente fortement le nombre de distributions obtenues étant donné que pour chaque nœud retiré, l’ensemble des sources possible a été étudiée indépendamment.
La figure 4.3 montre les distributions cumulatives obtenues pour deux nœuds de départs différents. Les distributions correspondent aux mêmes nœuds retirés que pour la figure 4.1.
On peut remarquer que pour les deux nœuds de départs sélectionnés les distributions sont très différentes. De plus les nœuds impactant de manière sensible ne se recoupent absolument pas pour les deux nœuds de départ sélectionnés.
Afin d’automatiser le procédé de comparaison des distributions et de catégoriser les différentes distributions obtenues, la même méthodologie que pour les distributions globales a été utilisée. La figure 4.4 représente les résultats obtenus dans ce cas, de manière similaire à la figure 4.2. De même une échelle logarithmique est utilisée pour catégoriser les distributions obenues, les limites étant fixées dans ce cas à moyenne + ecart-type = 0.04, 0.08, 0.16 et 0.32.
La visualisation proposée pour observer les résultats obtenus de manière claire et pertinente est d’oublier les valeurs précises obtenues pour chaque couple possible (nœud de départ, nœud retiré du réseau) pour en retenir l’essentiel, qui en est capturé par le classement en cinq catégories telles que présentées précédemment. La figure 4.5 présente sous forme matricielle les résultats obtenus. En abscisse correspond le nœud qui a été retiré du réseau et en ordonnée le nœud de départ de la diffusion. Pour chaque coordonnée correspond un symbole suivant la catégorie correspondante, la catégorie correspondant aux écarts les plus faibles étant représentée par un blanc. De plus pour l’ordonnée 70 est affichée la catégorie correspondante déterminée lors de l’étude globale.

Analyse des résultats et discussion

Résultats pour différents jeux de données

Infocom

Pour le jeu de donné Infocom, les résultats obtenus pour un temps de départ fixé étaient décevants. Peu information pouvait en être retirée, le retrait des nœuds n’impactant pas sur la diffusion de manière notable (de l’ordre de l’impact de la normalisation). En effet, l’expérience se déroule sur plusieurs jours, et les longs temps d’attente pour transmettre un message causent quelques valeurs extrêmes avec des retards de transmission dépassant plus d’un jour dans certains cas. De plus, sans doute à cause de la structure de la conférence réunissant des groupes de personnes pendant de longues périodes le jour, se créent des phénomènes de communauté dans laquelle chacun est remplaçable et des moments d’interaction forts comme aux repas permettant un échange important dans le réseau. Malheuresement, à cause d’un manque de temps face à de longues exécutions de programmes, les résultats de la valeur de l’impact au cours du temps n’est pas disponible. On ne peut pas dire grand chose et encore moins avec de bons arguments sur l’évolution de cet impact et si une information utile sur le comportement des nœuds peut en être retirée. Les résultats sont en cours de calcul mais ne seront pas disponibles prochainement, la durée importante de l’expérimentation décuplant le temps de travail.
Par ailleur les résultats pour la centralité dynamique proposée sont eux disponibles. La figure 5.1 montre l’exemple de l’évolution du nombre de messages en transit au cours de l’expérimentation pour les nœuds 3 et 32. Le nœud 32 présente la plus grande moyenne du groupe, alors que le nœud 3 a une valeur relativement faible. On observe bien les périodes de jour et de nuit, le jour montrant une grande variabilité et la nuit peu d’évolution. Pour le nœud 32 on observe que le nombre de messages en transit reste élevé sur de grande périodes, contrairement aux résultats obtenus pour Rollernet. L’observation de la moyenne du nombre de messages au cours de l’expérimentation en fonction de l’écart-type est similaire aux résultats obtenus pour Rollernet. On observe une grande variabilité avec des résultats proches de zéro, mais avec une répartition relativement homogène. De même il existe une bonne corrélation linéaire entre la moyenne et l’écart-type.

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 nœuds 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 nœuds 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