Analyse de la dynamique de réseaux de contacts

Ces dernières années, avec la prolifération de systèmes embarqués communicants, de nouveaux types de réseaux distribués ont émergé. Parmi eux on peut retrouver les réseaux de communications de véhicules, les réseaux de capteurs ou encore les réseaux de contacts. Chacun de ces réseaux présente une forme nouvelle de topologie où les agents communiquant se déplacent en changeant d’environnement et d’interlocuteurs, ces types de réseaux sont dénommés Delay Tolerant Networks (DTN). Dans ces réseaux, l’existence d’un canal de communication entre deux nœuds donnés est rarement disponible. La nature dynamique de ces réseaux apporte de nouvelles perspectives encore peu explorées comme l’utilisation de la mobilité des agents pour transporter de l’information sans dépendre d’une infrastructure de communication, mais cela complexifie grandement les problématiques associées. Une des principales difficultés de l’étude de ces réseaux provient de la nécessité de comprendre au mieux l’évolution du réseau afin de proposer des algorithmes de routages efficaces. La modélisation et la caractérisation de paramètres pertinents est pour cela primordial.

Un réseau de contacts est l’un des principaux exemples dans le domaine des DTNs. Grâce à des capteurs transportés par des personnes, il est possible de mesurer à quels moments deux personnes sont physiquement proches. Ces capteurs explorent leur entourage en envoyant périodiquement des paquets et en écoutant les paquets envoyés par les autres capteurs, ils peuvent ainsi repérer d’autres capteurs à proximité. Ce type de méthode permet de mesurer les contacts à l’intérieur d’un groupe de personnes. Grâce à de tels réseaux, des protocoles de communications dits ad hoc peuvent être créés afin de transmettre de l’information entre les agents sans passer par une infrastructure existante. Mais comme le montrent les expérimentations, les réseaux de contacts présentent de nombreuses spécificités vis à vis d’autres DTNs ou même vis à vis de différents scénarios de dynamiques de contacts, et les études montrent l’importance de les prendre en compte lors de la création d’algorithmes de routage.

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.

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.

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.