20 septembre 2012, à la salle A001 à partir de 10h00

« La Prédiction de Liens dans les Réseaux Sans-fil Mobiles et Dynamiques Centrés sur l’Être Humain ».

Cette thèse a été supervisée et encadrée par Professeur Djamal ZEGHLACHE et Docteur Vincent GAUTHIER de l’Institut Mines-TELECOM SudParis (laboratoire SAMOVAR) et par Professeur Sami TABBANE et Docteur Houda KHEDHER de l’Institut Supérieur des Télécommunications (SUP’COM) de Tunis.

– Mme Hassnaa MOUTAFA – Rapporteur – Ingénieur de Recherche Sénior, Orange Labs
– M. André-Luc BEYLOT Rapporteur Professeur, IRIT/ENSEEIHT
– M. Marcelo DIAS de AMORIM – Examinateur – Chargé de Recherche, LIP6/CNRS
– Mme Pascale MINET – Examinateur – Chercheur HDR, INRIA Recquencourt
– M. Farid BENBADIS – Examinateur – Ingénieur Chercheur, Thalès Communications
– M. Djamal ZEGHLACHE – Directeur de thèse – Professeur, TELECOM SudParis
– M. Sami TABBANE – Co-directeur de thèse – Professeur, SUP’COM Tunis
– M. Vincent GAUTHIER – Encadrant – Maître de Conférences, TELECOM SudParis

Résumé:

Durant ces dernières années, nous avons observe une expansion progressive et continue des réseaux mobile sans-fil centres sur l’être humain. L’apparition de ces réseaux a encouragé les chercheurs à réfléchir à de nouvelles solutions pour assurer une évaluation efficace et une conception adéquate des protocoles de communication. En effet, ces réseaux sont sujets à de multiples contraintes telles que le manque d’infrastructure, la topologie dynamique, les ressources limitées ainsi que la qualité de service et la sécurité des informations précaires. Nous nous sommes spécialement intéressés à l’aspect dynamique du réseau et en particulier à la mobilité humaine. La mobilité humaine a été largement étudiée pour pouvoir extraire ses propriétés intrinsèques et les exploiter pour des approches plus adaptées à cette mobilité. Parmi les propriétés les plus intéressantes soulevées dans la littérature, nous nous sommes focalisés sur l’impact des interactions sociales entre les entités du réseau sur la mobilité humaine et en conséquence sur la structure du réseau. Pour recueillir des informations structurelles sur le réseau, plusieurs métriques et techniques ont été empruntées de l’analyse des réseaux sociaux (Social Network Analysis notée également SNA). Cet outil peut être assimilé à une autre alternative pour mesurer des indicateurs de performance du réseau. Plus précisément, il extrait des informations structurelles du réseau et permet aux protocoles de communication de bénéficier d’indications utiles telles que la robustesse du réseau, les nœuds centraux ou encore les communautés émergentes. Dans ce contexte, la SNA a été largement utilisée pour prédire les liens dans les réseaux sociaux en se basant notamment sur les informations structurelles.

Motivés par l’importance des liens sociaux dans les réseaux mobiles sans-fil centres sur l’être humain et par les possibilités offertes par la SNA pour prédire les liens, nous nous proposons de concevoir la première méthode capable de prédire les liens dans les réseaux sans-fil mobiles tels que les réseaux ad-hoc mobiles (Mobile Ad-Hoc Networks ou MANETs) et les réseaux tolérants aux délais (Delay/Disruption Tolerant Networks ou DTNs). Notre proposition suit l’évolution de la topologie du réseau sur T périodes à travers un tenseur (en ensemble de matrices d’adjacence et chacune des matrices correspond aux contacts observés durant une période bien spécifique). Ensuite, elle s’appuie sur le calcul de la mesure sociométrique de Katz pour chaque paire de nœuds pour mesurer l’étendue des relations sociales entre les différentes entités du réseau. Une telle quantification donne un aperçu sur les liens dont l’occurrence est fortement pressentie à la période T+1 et les nouveaux liens qui se créent dans le futur sans pour autant avoir été observés durant le temps de suivi. Pour attester l’efficacité de notre proposition, nous l’appliquons sur trois traces réelles et nous comparons sa performance à celles d’autres techniques de prédiction de liens présentées dans la littérature. Les résultats prouvent que notre méthode est capable d’atteindre le meilleur niveau d’efficacité et sa performance surpasse celles des autres techniques. L’une des majeures contributions apportées par cette proposition met en exergue la possibilité de prédire les liens d’une manière décentralisée. En d’autres termes, les nœuds sont capables de prédire leurs propres liens dans le futur en se basant seulement sur la connaissance du voisinage immédiat (voisins à un et deux sauts).

En outre, nous sommes désireux d’améliorer encore plus la performance de notre méthode de prédiction de liens. Pour quantifier la force des relations sociales entre les entités du réseau, nous considérons deux aspects dans les relations : la récence des interactions et leur fréquence. À partir de là, nous nous demandons s’il est possible de prendre en compte un troisième critère pour améliorer la précision des prédictions. En soutenant l’heuristique qui stipule que les liens persistants sont fortement prédictibles, nous considérons la stabilité des relations (lien ou proximité à deux sauts). Pour mesurer cette stabilité, nous optons pour l’estimation d’entropie d’un phénomène évoluant dans le temps proposée dans l’algorithme de compression de Lempel-Ziv. Nous considérons que les mesures fournies par notre méthode et les mesures de stabilité se complètent et nous proposons en conséquence différentes combinaisons pour la conception de nouvelles métriques de prédiction de liens. Les résultats de simulation confirment le fondement de notre intuition.

La proposition d’une méthode de prédiction de liens basée sur les tenseurs et la dérivation de nouvelles métriques liées à la stabilité des relations pour l’amélioration de cette méthode représentent les contributions majeures de cette thèse. Le long de cette thèse, notre souci a été de réfléchir sur des mécanismes et des métriques capables d’améliorer l’évaluation ou la conception des protocoles de communication. Néanmoins, nos efforts ne ce sont pas limités aux travaux de prédiction de liens et nous avons eu l’opportunité de proposer deux autres contributions. D’une part, nous proposons un modèle commun pour les couches physique et liaison de données pour le standard IEEE 802.15.4. D’autre part, nous avançons un mécanisme d’apprentissage basé sur un jeu répétitif, inspiré du célèbre jeu télévisé « Le Maillon Faible », pour stimuler la coopération dans un réseau ad-hoc non coopératif.
Mots-Clés : Réseau sans-fil mobile centrés sur l’être humain, prédiction de liens, tenseur, liens sociaux, mesure de Katz, stabilités de lien et de proximité, entropie.

Abstract:

During the last years, we have observed a progressive and continuous expansion of human-centered mobile wireless networks. The advent of these networks has encouraged the researchers to think about new solutions in order to ensure efficient evaluation and design of communication protocols. In fact, these networks are faced to several constraints as the lack of infrastructure, the dynamic topology, the limited resources and the deficient quality of service and security. We have been interested in the dynamicity of the network and in particular in human mobility. The human mobility has been widely studied in order to extract its intrinsic properties and to harness them to propose more accurate approaches. Among the prominent properties depicted in the literature, we have been specially attracted by the impact of the social interactions on the human mobility and consequently on the structure of the network. To grasp structural information of such networks, many metrics and techniques have been borrowed from the Social Network Analysis (SNA). The SNA can be seen as another network measurement task which extracts structural information of the network and provides useful feedback for communication protocols. In this context, the SNA has been extensively used to perform link prediction in social networks relying on their structural properties.

Motivated by the importance of social ties in human-centered mobile wireless networks and by the possibilities that are brought by SNA to perform link prediction, we are interested by designing the first link prediction framework adapted for mobile wireless networks as Mobile Ad-hoc Networks (MANETs) and Delay/Disruption Tolerant Networks (DTN). Our proposal tracks the evolution of the network through a third-order tensor over T periods and computes the sociometric Katz measure for each pair of nodes to quantify the strength of the social ties between the network entities. Such quantification gives insights about the links that are expected to occur in the period T+1 and the new links that are created in the future without being observed during the tracking time. To attest the efficiency of our framework, we apply our link prediction technique on three real traces and we compare its performance to the ones of other well-known link prediction approaches. The results prove that our method reaches the highest level of accuracy and outperforms the other techniques. One of the major contributions behind our proposal highlights that the link prediction in such networks can be made in a distributed way. In other words, the nodes can predict their future links relying on the local information (one-hop and two-hop neighbors) instead of a full knowledge about the topology of the network.

Furthermore, we are keen to improve the link prediction performance of our tensor-based framework. To quantify the social closeness between the users, we take into consideration two aspects of the relationships: the recentness of the interactions and their frequency. From this perspective, we wonder if we can consider a third criterion to improve the link prediction precision. Asserting the heuristic that stipulates that persistent links are highly predictable, we take into account the stability of the relationships (link and proximity stabilities). To measure it, we opt for the entropy estimation of a time series proposed in the Lempel-Ziv data compression algorithm. As we think that our framework measurements and the stability estimations complement each other, we combine them in order to provide new link prediction metrics. The simulation results emphasize the pertinence of our intuition.

Providing a tensor-based link prediction framework and proposing relative enhancements tied to stability considerations represent the main contributions of this thesis. Along the thesis, our concern was also focused on mechanisms and metrics that contribute towards improving communication protocols in these mobile networks. Nevertheless, our efforts were not limited to the major contributions previously mentioned and we had the opportunity to
propose two other approaches that can be useful to improve the design and the evaluation of protocols in mobile multi-hop networks. Firstly, we propose a joint model for the IEEE 802.15.4 physical and medium access control layers. Secondly, we advance a self-learning repeated game framework, inspired by « The Weakest Link » TV game, to enforce cooperation in non-cooperative ad-hoc networks.

Keywords: Human-centered mobile wireless networks, link prediction, tensor, social ties, Katz measure, link and proximity stabilities, entropy.