La quantité d informations et de services disponibles sur l Internet est si importante qu il est très difficile de choisir ceux qui répondent bien à nos exigences. Dans cette thèse, l auteure présente un algorithme pour le calcul de la réputation de services en proposant un modèle amélioré du comportement des utilisateurs. Cette technique se révèle bien adaptée pour bâtir des modèles de comportement. De plus elle a travaillé sur les aspects concernant les similarités de services afin d obtenir des réponses appropriées aux demandes des services pour améliorer la qualité de l expérience. Dans ce cadre, un algorithme évaluant la proximité des services a été développé. A partir de cet algorithme, une version adaptative avec des intervalles variables pour les paramètres de services également a été proposée. Ces algorithmes ont été testés et validés sur des classes de services.

Les itérations chaotiques, un outil issu des mathématiques discrètes, sont pour la première fois étudiées pour obtenir de la divergence et du désordre. Après avoir utilisé les mathématiques discrètes pour en déduire des situations de non convergence, ces itérations sont modélisées sous la forme d un système dynamique et sont étudiées topologiquement dans le cadre de la théorie mathématique du chaos. Nous prouvons que leur adjectif chaotique a été bien choisi : ces itérations sont du chaos aux sens de Devaney, Li-Yorke, l expansivité, l entropie topologique et l exposant de Lyapunov, etc. Ces propriétés ayant été établies pour une topologie autre que la topologie de l ordre, les conséquences de ce choix sont discutées. Nous montrons alors que ces itérations chaotiques peuvent être portées telles quelles sur ordinateur, sans perte de propriétés, et qu il est possible de contourner le problème de la finitude des ordinateurs pour obtenir des programmes aux comportements prouvés chaotiques selon Devaney, etc. Cette manière de faire est respectée pour générer un algorithme de tatouage numérique et une fonction de hachage chaotiques au sens le plus fort qui soit. À chaque fois, l intérêt d être dans le cadre de la théorie mathématique du chaos est justifié, les propriétés à respecter sont choisies suivant les objectifs visés, et l' objet ainsi construit est évalué. Une notion de sécurité pour la stéganographie est introduite, pour combler l absence d outil permettant d estimer la résistance d un schéma de dissimulation d information face à certaines catégories d attaques. Enfin, deux solutions au problème de l agrégation sécurisée des données dans les réseaux de capteurs sans fil sont proposées

Le problème de tournées de véhicules est l un des problèmes d optimisation combinatoire les plus étudiés car il a de multiples applications en planification industrielle. La littérature associée est très riche, en variantes de problèmes et en approches de résolution. Face à un problème réel, il est difficile d identifier la classe de problème à laquelle il appartient, de recenser les travaux correspondants, et de déterminer le type de méthode de résolution le plus approprié. Cette thèse étudie la faisabilité d un projet destinée à faciliter ces démarches, en s intéressant plus particulièrement aux approches de résolution évolutionnaires. Il repose sur trois éléments : une notation des variantes de VRP, un recensement d opérateurs évolutionnaires de la littérature, et la construction d une base de règles liant les variantes de problèmes à l efficacité des opérateurs évolutionnaires. L objectif est de guider la conception d un algorithme en fonction des caractéristiques du problème, en proposant les opérateurs qui ont la plus grande probabilité d être efficaces. Appliquer la notation proposée à plusieurs articles montre qu elle permet à chacun de classifier les travaux de manière précise, et d identifier ainsi plus facilement les approches et résultats comparables aux siens. La méthode expérimentale proposée est illustrée en considérant 3 types de croisement et 3 types de mutation. Cette étude montre qu il est possible d estimer quels éléments de l algorithme ont un impact détectable sur les performances, et d établir des relations entre les choix de conception de l algorithme ou entre l instance de problème et l efficacité des opérateurs.

Cette thèse est une contribution à la conception d'une méthode de génération automatique de tests à partir de modèles (ou MBT -Model Based Testing). Le contexte de nos travaux se situe dans la continuité de ceux effectués autour de l'outil BZ- TT (BZ- Testing Tools) qui permet d'engendrer des tests fonctionnels à partir de modèles décrits en langage B. Les critères de sélection de tests implémentés dans l'outil BZ- TT reposent sur la couverture structurelle du modèle du système à valider en prenant en compte les structures de données et de contrôle de celui-ci. Cette approche ne permet pas de générer de tests à partir de propriétés liées au comportement dynamique du système, par exemple en tenant compte de propriétés basées sur des enchaînements d'opérations. Afin de répondre à cette problématique, un certain nombre de travaux proposent des méthodes où l'expertise humaine est exploitée afin de définir des critères de sélection de tests "dynamiques". De tels critères de sélection permettent, à l'ingénieur de définir des stratégies basées sur des propriétés et des aspects du système qu'il souhaite valider. Nos contributions s'inscrivent dans cette voie, tout en visant la complémentarité par rapport à la génération automatique de tests par couverture structurelle du modèle dans un objectif de valorisation des technologies et ressources déployées à cette fin. Notre première contribution est la définition d'un langage de formalisation d'objectifs de tests qui permet d'exprimer des ensembles de scénarios de tests inspirés de propriétés à valider sur le système. Ce langage permet de décrire des schémas de tests à partir d'un formalisme, basé sur celui des expressions régulières, qui permet de décrire des ensembles de scénarios principalement par des enchaînements d'appels d'opération et d'états symboliques. Nous définissons une méthode de génération de tests intégrée à l'outil BZ- TT, afin que celui-ci prenne en compte ce nouveau critère de sélection de tests. Cette méthode permet de réutiliser les technologies d'animation symbolique et de résolution de contraintes de cet outil, ainsi que de conserver les fonctionnalités d'exportation et de concrétisation des tests produits. Dans cette méthode, la seule charge supplémentaire pour l'ingénieur de validation est la définition des schémas de test utilisés comme critère de sélection. Nos dernières contributions, visent à évaluer la complémentarité de notre méthode avec celle de génération automatique de tests par couverture structurelle du modèle. Nous proposons une méthode d'évaluation de la complémentarité entre deux suites de tests. Cette méthode est basée sur le calcul de la couverture d'états et de transitions des suites de tests sur une abstraction du système. Enfin, nous appliquons cette méthode à trois études de cas (deux applications de type carte à puce et un système de gestion de fichiers Posix), et nous montrons la complémentarité qu'elle apporte.

Avec l'émergence de nouvelles architectures distribuées, comme les grappes de calcul distantes et les architectures de calcul volontaire, il apparaît important de définir des algorithmes et des intergiciels bien adaptés à ces architectures. En effet, l'utilisation de ces plate-formes introduit plusieurs nouvelles contraintes par rapport à un contexte de grappes locales homogènes : hétérogénéité des machines, hétérogénéité des réseaux, volatilité des noeuds de calcul, etc. Dans ce contexte, plusieurs travaux montrent que pour les algorithmes itératifs il peut être préférable d'utiliser les algorithmes IACA (Itérations Asynchrones avec Communications Asynchrones) pour lesquels les communications sont recouvertes par du calcul et la perte des messages de données est tolérée. Les travaux présentés dans cette thèse concernent la conception et la mise en oeuvre d'une plate-forme dédiée à l'exécution d'algorithmes IACA sur des architectures distribuées, hétérogènes et volatiles. Cette plate-forme, JACEP2P-V2, est tolérante aux pannes et décentralisée. Elle offre un mécanisme de communications asynchrones et un mécanisme de détection de la convergence globale adapté aux caractéristiques des algorithmes IACA. De plus, nous reportons des expérimentations sur grappes hétérogènes volatiles et distantes afin de tester l'efficacité et la robustesse de notre plate-forme. Les résultats obtenus, avec plus de 1000 coeurs de calculs, sont très encourageants et montrent que JACEP2P-V2 est extensible et performante. Nous terminons ce document par la présentation d'une étude comparative de plusieurs méthodes de résolutions de systèmes non linéaires (comme la multi-décomposition et la relaxation d'ondes) implémentées avec JACEP2P-V2.

Au cours de ces dernières années, la technologie des réseaux sans fil n'a cessé de croître grâce aux développements technologiques dans divers domaines liés à la micro-électronique et à l'informatique. La mise en réseaux des capteurs sans fil permet d'étendre la couverture de la zone et la diffusion pour couvrir un territoire plus important, obtenir des résultats plus rapidement, plus fiables et permettre la tolérance aux fautes. Au niveau de la diffusion, nous avons proposé un algorithme pour la diffusion dans un environnement réaliste basé sur l'approche MPR (Multi Points Relais) puis un algorithme d'auto-organisation appelé CSOS basé sur le concept de clustering. Ce dernier permet d'organiser les capteurs en 2-clusters homogènes en taille et de confier aux cluster-heads la responsabilité de communiquer et de transmettre les données collectées par les capteurs à la station de base. L'élection des cluster-heads se fait périodiquement selon leur poids qui est fonction de leur capacité à supporter cette tâche. Le poids d'un noeud est calculé grâce aux métriques suivantes: k-densité, énergie restante et mobilité. Nous avons impliqué ces facteurs dans le calcul des poids des capteurs afin de générer des clusters stables. Au niveau de la couverture de zone, nous avons proposé un algorithme pour assurer la couverture totale de la zone d'intérêt à des degrés différents. Ce protocole se base sur le même concept que CSOS mais il implique plus de capteurs actifs pour la couverture de zone. En effet, le nombre de capteurs actifs augmente en fonction du degré de couverture de zone appelé k-couverture ou couverture multiple. Pour tester les performances de nos contributions, nous avons réalisé plusieurs simulations et nous avons comparé 1es résultats obtenus relativement aux résultats d'autres protocoles. Afin de tester notre protocole de couverture de zone nous avons développé une application de surveillance dans un parc d'une maison de retraite pour les personnes dépendantes.

Deux problématiques principales ont guidé les travaux de cette thèse: (a) comment supporter efficacement les interactions (navigation) dans les présentations multimédias streamées et (b) comment améliorer la disponibilité des données dans un système de streaming P2P ? Afin de permettre une navigation rapide au sein d une présentation multimédia, diffusée en continu, nous avons proposé une approche exploitant les informations disponibles sur son contenu (les objets la constituant). Ces informations permettent, entre autres, de préserver la cohérence sémantique de la présentation lors des interactions utilisateurs. Dans un deuxième temps, nous avons étudié les performances de notre approche en proposant une stratégie de pré-chargement, nommé CPS (Content-Based Prefetching Strategy), qui a permis de réduire considérablement les temps de latence des interactions utilisateurs. La disponibilité des données dans les systèmes de streaming P2P diffère fondamentalement de celle observée dans les systèmes PSP classiques, dans le sens où les données consommées sont dépendantes du temps. Ainsi, cette problématique se pose en terme de possibilité au pair destinataire (consommateur) de pouvoir terminer le visionnage du contenu vidéo dans sa totalité i.e., durant toute la durée de la vidéo. Or, les systèmes P2P spontanés sont essentiellement caractérisés par leur volatilité fréquente, ce qui pose le problème de la disponibilité des pairs sources pendant le streaming. Nous avons étudié cette problématique en mettant en oeuvre, dans un premier temps, un mécanisme de cache centralisé permettant de réduire les effets de la volatilité des pairs et en préservant uniquement les suffixes des vidéos en cours d accès. Dans un deuxième temps, nous avons étendu notre approche vers un cache virtuel distribué. Les résultats des simulations ont montré la pertinence des approches proposées. Enfin, nous avons décrit la conception et la mis en œuvre d un prototype qui démontre la faisabilité d un système de streaming P2P spontané.

Le contrôle de la congestion dans les réseaux mobiles dépend de la répartition spatiale et temporelle du trafic. Lorsque la congestion est localisée dans le temps, la tarification est un moyen incitatif efficace pour la redistribution temporelle de la demande. L’objectif est de proposer un modèle de tarification planifiée pour l’optimisation de l’utilisation des ressources du réseau. Le calcul des nouvelles grilles tarifaires se base sur un modèle de comportement des clients. En plus de la modélisation du comportement, l’étude prend en compte la diversité des propriétés de la demande et au dimensionnement non homogène des cellules. Un enjeu de cette étude est alors de montrer dans quelle mesure une grille peut s appliquer à tout ou une partie du réseau et l influence de ce choix sur la décongestion des ressources. Les travaux fondamentaux effectués s appuient d abord sur des probabilités pour modéliser le comportement du client, puis sur des méthodes statistiques, d’analyse de données et de classification automatique pour identifier les propriétés pertinentes des cellules du réseau, et enfin sur des méthodes de partitionnement de graphe pour formaliser le problème de découpage spatial du réseau. Un travail sur les méthodes d’optimisation approchée basées sur la recherche locale et les algorithmes génétiques est réalisé pour l optimisation de l’utilisation des ressources et pour le découpage spatial du réseau. Une étude a été menée sur l’optimisation robuste où l’incertitude sur les données d’entrée du problème est appréhendée par l’examen de la stabilité du modèle vis-à-vis de perturbations sur les données.

Un objectif de cette thèse est de fournir des outils d analyse, de conception et d implantation des approches métaheuristiques pour l optimisation combinatoire en les formulant dans le cadre des systèmes multi-agents. L accent est mis sur la potentialité de mise en oeuvre distribuée des approches et sur l utilisation de techniques d apprentissage permettant d adapter dynamiquement des méthodes de recherche. Dans le cadre de cette thèse nous proposons tout d abord, un framework organisationnel et multi-agent pour la modélisation de l implantation de métaheuristiques. Ce framework nommée AMF (Agent Metaheuristic Framework), introduit un modèle organisationnel de métaheuristiques qui donne un cadre d analyse de comparaison et de conception de différentes métaheuristiques. Ensuite, nous présentons une métaheuristique fondée sur la métaphore de la coalition, CMB (Coalition Based Metaheuristic), mettant en avant l intérêt d utiliser les systèmes multi-agents pour la conception de métaheuristiques. Dans cette métaheuristique, la recherche de solution est effectuée par un ensemble d agents regroupés dans une coalition. La structure de coalition permet d intégrer naturellement au système de résolution des aspects de distribution et de décentralisation du contrôle, de même que des procédés d apprentissage individuels et collectifs. L efficacité de notre approche est évaluée expérimentalement en traitant deux problèmes d optimisation combinatoire : un problème de tournées de véhicules et un problème de positionnement.

Le problème de planification de réseaux WLAN consiste d'une part à positionner et à paramétrer des antennes dans un bâtiment et d'autre part à leur affecter une fréquence afin d'offrir aux clients un accès sans fil au réseau local. Le réseau ainsi construit doit répondre à des critères de couverture et de qualité de service, tout en minimisant le coût financier. Notre modélisation est basée sur le calcul du débit réel offert en chaque point de demande de service du réseau. Nous montrons que ce critère de débit réel permet une modélisation complète de la qualité de service car il unifie les critères habituels de couverture, de gestion des interférences et de capacité. Notre optimisation traite simultanément le problème de placement des points d'accès et le problème d'affectation de fréquences par un algorithme Voisinages Variables Aléatoires VVA : à chaque itération de cette recherche locale le type de voisinage est tiré au hasard. Cet algorithme est très modulaire et permet facilement de combiner les deux sous problèmes (placement et affection). Ces travaux ont donné lieu à des collaborations et partenariats industriels : logiciel de planification globale des WLAN avec Orange Labs et solutions de planification séquentielle avec la start-up Trinaps. Enfin nous approfondissons la modélisation du problème en explicitant les liens entre le calcul du débit réel et les SINR. Dans une première étape, nous montrons que les contraintes de seuil sur les SINR induisent un problème de T-coloration de graphe (condition nécessaire). Pour obtenir une équivalence rendant compte des interférences multiples, une généralisation du problème de T-coloration pour les hypergraphes est introduite. Dans une seconde étape, nous définissons un algorithme déduisant les seuils de SINR à partir des contraintes sur les débits réels. Cette nouvelle modélisation est la base de nos développements futurs.