Les réseaux ad hoc mobiles sont des réseaux qui se forment spontanément grâce à la présence de terminaux mobiles. Ces réseaux sans fil sont de faible capacité. Les nœuds se déplacent librement et de manière imprévisible et ils se déchargent très rapidement. En conséquence, un réseau MANET est très enclin à subir des partitionnements fréquents. Les applications déployées sur de tels réseaux, souffrent de problèmes de disponibilité des données induits par ces partitionnements. La réplication des données constitue un mécanisme prometteur pour pallier ce problème. Cependant, la mise en œuvre d'un tel mécanisme dans un environnement aussi contraint en ressources constitue un réel défi. L'objectif principal est donc de réaliser un mécanisme peu consommateur en ressources. Le second objectif de la réplication est de permettre le rééquilibrage de la charge induite par les requêtes de données. Le choix des données à répliquer ainsi que celui des nœuds optimaux pour le placement des futurs réplicas est donc crucial, spécialement dans le contexte du MANET. Dans cette thèse, nous proposons CReaM (Community-Centric and Resource-Aware Replication Model") un modèle de réplication adapté à un réseau MANET. CReaM fonctionne en mode autonomique : les prises de décisions se basent sur des informations collectées dans le voisinage du nœud plutôt que sur des données globalement impliquant tous les nœuds, ce qui permet de réduire le trafic réseau lié à la réplication. Pour réduire l'usage des ressources induit par la réplication sur un nœud, les niveaux de consommation des ressources sont contrôlés par un moniteur. Toute consommation excédant un seuil prédéfini lié à cette ressource déclenche le processus de réplication. Pour permettre le choix de la donnée à répliquer, une classification multi critères a été proposée (rareté de la donnée, sémantique, niveau de demande); et un moteur d'inférence qui prend en compte l'état de consommation des ressources du nœud pour désigner la catégorie la plus adaptée pour choisir la donnée à répliquer. Pour permettre de placer les réplicas au plus près des nœuds intéressés, CReaM propose un mécanisme pour l'identification et le maintien à jour des centres d'intérêt des nœuds. Les utilisateurs intéressés par un même sujet constituent une communauté. Par ailleurs, chaque donnée à répliquer est estampillée par le ou les sujets au(x)quel(s) elle s'apparente. Un nœud désirant placer un réplica apparenté à un sujet choisira le nœud ayant la plus grande communauté sur ce sujet. Les résultats d'expérimentations confirment la capacité de CReaM à améliorer la disponibilité des données au même niveau que les solutions concurrentes, tout en réduisant la charge liée à la réplication. D'autre part, CReaM permet de respecter l'état de consommation des ressources sur les nœuds.

Un réseau mobile ad hoc (Mobile Ad hoc Network, MANET) est un réseau sans fil, formé dynamiquement par un ensemble d'utilisateurs équipés de terminaux mobiles, sans l'utilisation d'une infrastructure préexistante, ou d'une administration centralisée. Les équipements utilisés dans les MANETs sont limités par la capacité de la batterie, la puissance de calcul et la bande passante. Les utilisateurs des MANETs sont libres de se déplacer, ce qui induit à des topologies dynamiques dans le temps. Toutes ces contraintes ajoutent plus de challenges aux protocoles et services de communications afin de fonctionner dans les MANETs. L'évolution des réseaux de 4ème génération (4G) est appelée à intégrer les MANETs avec les autres types de réseaux afin d'étendre leurs portées. Nous nous sommes intéressés dans la première partie de cette thèse à quelques challenges connus dans les MANETs en proposant des solutions novatrices utilisant des propriétés intéressantes des topologies de graphes. Dans un premier temps, nous avons effectué une étude sur la prédiction de la mobilité afin de maintenir une topologie d'ensemble dominant connecté dans les MANETs. Nous avons proposé dans un autre travail comment construire des topologies de graphes ayant des propriétés globales en se basant seulement sur des informations locales des nœuds mobiles. Ces topologies servent comme overlay aux MANETs. Nous avons proposé des algorithmes distribués pour construire des alliances offensives et défensives globales minimales. Nous avons aussi défini des heuristiques pour ces algorithmes afin de réduire les tailles des alliances obtenues. La première partie de cette thèse est achevée par la proposition d'un framework pour la conception et l'analyse des protocoles de contrôle de topologie dans les MANETs. Nous avons identifié les points communs des algorithmes de contrôle de topologie conçus pour les réseaux mobiles ad hoc et nous avons enrichi le simulateur NS-2 avec un ensemble d'extensions pour supporter le contrôle de topologie / We are interested in this thesis to graph-based approaches to deal with some challenges in networking, namely, graph topologies of mobile ad hoc networks (MANETs) and process model matchmaking in large scale web service. We propose in the first part: (1) a generic mechanism using mobility information of nodes to maintain a graph topology of the network. We show particularly, how to use the prediction of future emplacements of nodes to maintain a connected dominating set of a given MANET. (2) distributed algorithms to construct minimal global offensive alliance and global defensive alliance sets in MANETs. We also introduce several heuristics to get a better approximation of the cardinality of the alliance sets which is a desirable property for practical considerations. (3) a framework to facilitate the design and evaluation of topology control protocols in MANETs. We propose in the framework, a common schema for topology control based on NS-2 simulator and inspired from the commonalities between the components of the topology control algorithms in MANETs. In the second part, we focus on process model matchmaking. We propose two graph-based solutions for process model inexact matching to deal with high computational time of existing work in the literature. In the first solution, we decompose the process models into their possible execution sequences. After, we propose generic graph techniques using string comparator metrics for process model matchmaking based on this decomposition. In order to get better optimization of the execution time and to deal with process model matching in large scale web services, the second solution combines a spectral graph matching with structural and semantic proposed approaches. This solution uses an eigen-decomposition projection technique that makes the runtime faster

Les réseaux ad hoc mobiles sont des réseaux qui se forment spontanément grâce à la présence de terminaux mobiles. Ces réseaux sans fil sont de faible capacité. Les nœuds se déplacent librement et de manière imprévisible et ils se déchargent très rapidement. En conséquence, un réseau MANET est très enclin à subir des partitionnements fréquents. Les applications déployées sur de tels réseaux, souffrent de problèmes de disponibilité des données induits par ces partitionnements. La réplication des données constitue un mécanisme prometteur pour pallier ce problème. Cependant, la mise en œuvre d’un tel mécanisme dans un environnement aussi contraint en ressources constitue un réel défi. L’objectif principal est donc de réaliser un mécanisme peu consommateur en ressources. Le second objectif de la réplication est de permettre le rééquilibrage de la charge induite par les requêtes de données. Le choix des données à répliquer ainsi que celui des nœuds optimaux pour le placement des futurs réplicas est donc crucial, spécialement dans le contexte du MANET. Dans cette thèse, nous proposons CReaM (Community-Centric and Resource-Aware Replication Model”) un modèle de réplication adapté à un réseau MANET. CReaM fonctionne en mode autonomique : les prises de décisions se basent sur des informations collectées dans le voisinage du nœud plutôt que sur des données globalement impliquant tous les nœuds, ce qui permet de réduire le trafic réseau lié à la réplication. Pour réduire l’usage des ressources induit par la réplication sur un nœud, les niveaux de consommation des ressources sont contrôlés par un moniteur. Toute consommation excédant un seuil prédéfini lié à cette ressource déclenche le processus de réplication. Pour permettre le choix de la donnée à répliquer, une classification multi critères a été proposée (rareté de la donnée, sémantique, niveau de demande); et un moteur d’inférence qui prend en compte l’état de consommation des ressources du nœud pour désigner la catégorie la plus adaptée pour choisir la donnée à répliquer. Pour permettre de placer les réplicas au plus près des nœuds intéressés, CReaM propose un mécanisme pour l’identification et le maintien à jour des centres d’intérêt des nœuds. Les utilisateurs intéressés par un même sujet constituent une communauté. Par ailleurs, chaque donnée à répliquer est estampillée par le ou les sujets au(x)quel(s) elle s’apparente. Un nœud désirant placer un réplica apparenté à un sujet choisira le nœud ayant la plus grande communauté sur ce sujet. Les résultats d’expérimentations confirment la capacité de CReaM à améliorer la disponibilité des données au même niveau que les solutions concurrentes, tout en réduisant la charge liée à la réplication. D’autre part, CReaM permet de respecter l’état de consommation des ressources sur les nœuds. / A Mobile Ad-hoc Network is a self-configured infrastructure-less network. It consists of autonomous mobile nodes that communicate over bandwidth-constrained wireless links. Nodes in a MANET are free to move randomly and organize themselves arbitrarily. They can join/quit the network in an unpredictable way; such rapid and untimely disconnections may cause network partitioning. In such cases, the network faces multiple difficulties. One major problem is data availability. Data replication is a possible solution to increase data availability. However, implementing replication in MANET is not a trivial task due to two major issues: the resource-constrained environment and the dynamicity of the environment makes making replication decisions a very tough problem. In this thesis, we propose a fully decentralized replication model for MANETs. This model is called CReaM: “Community-Centric and Resource-Aware Replication Model”. It is designed to cause as little additional network traffic as possible. To preserve device resources, a monitoring mechanism are proposed. When the consumption of one resource exceeds a predefined threshold, replication is initiated with the goal of balancing the load caused by requests over other nodes. The data item to replicate is selected depending on the type of resource that triggered the replication process. The best data item to replicate in case of high CPU consumption is the one that can better alleviate the load of the node, i.e. a highly requested data item. Oppositely, in case of low battery, rare data items are to be replicated (a data item is considered as rare when it is tagged as a hot topic (a topic with a large community of interested users) but has not been disseminated yet to other nodes). To this end, we introduce a data item classification based on multiple criteria e.g., data rarity, level of demand, semantics of the content. To select the replica holder, we propose a lightweight solution to collect information about the interests of participating users. Users interested in the same topic form a so-called “community of interest”. Through a tags analysis, a data item is assigned to one or more communities of interest. Based on this framework of analysis of the social usage of the data, replicas are placed close to the centers of the communities of interest, i.e. on the nodes with the highest connectivity with the members of the community. The results of evaluating CReaM show that CReaM has positive effects on its main objectives. In particular, it imposes a dramatically lower overhead than that of traditional periodical replication systems (less than 50% on average), while it maintains the data availability at a level comparable to those of its adversaries.