No description available.

Les progrès dans l'architecture de réseau informatique ajoutent continuellement de nouvelles fonctionnalités aux problèmes de routage des véhicules. Dans cette thèse, le problème de tournée des véhicules avec la collecte de donnée sans fil (WT-VRP) est étudié. Il recherche un itinéraire pour le véhicule chargé de collecter des informations auprès des stations ainsi qu'un planning efficace de collecte d'informations. La nouvelle fonctionnalité ajoutée ici est la possibilité de récupérer des informations via une transmission sans fil, sans visiter physiquement les stations du réseau. Le WT-VRP a des applications dans la surveillance sous-marine et la surveillance environnementale. Nous discutons les critères pour mesurer l'efficacité d'une solution et proposons des formulations de programmation linéaire en nombre entier mixte pour résoudre le problème. Des expériences computationnelles ont été réalisées pour accéder à la complexité numérique du problème et pour comparer les solutions selon les critères proposés. Ensuite, nous avons renforcé certains modèles ainsi que considéré différentes suppositions pour le réseaux sans fils. Finalement, pour être capable de résoudre le problème dans des réseaux de grande échelle, nous avons développés des méthodes heuristiques pour le WT-VRP. / The vehicle routing problem is one of the most studied problems in Operations Research.Different variants have been treated in the past 50 years and with technologicaladvances, new challenges appear. In this thesis, we introduce a new variation of theVRP appearing in wireless networks. The new characteristic added to this well-knowproblem is the possibility of pick-up information via wireless transmissions. In the contextconsidered here, a unique base station is connected with the outside and a vehicleis responsible for collecting information via wireless connection to the vehicle when it islocated in another sufficiently close station. Simultaneous transmissions are permitted.Time of transmission depends on the distance between stations, the amount of informationtransmitted, and other physical factors (e.g obstacles along the way, installedequipment). Information to be sent outside of the network is continuously generatedin each station at a constant rate. The first contribution of this thesis is the introductionof a mixed ILP formulation for a variation in which it is only possible to send all theinformation or nothing during a wireless transmission. For this model three differentstrategies are investigated: maximizing total amount of information extracted an theend of the time horizon; maximizing the average of the information in the vehicle ateach time point; and maximizing the satisfaction of each station at the end of the timehorizon. Each strategy is translated as a different objective function for the mixed ILPformulation. The problem is then reformulated by accepting the option of sending onlypart of the information during a wireless transmission and considering only the firststrategy,(i.e. maximizing the amount of information extracted at the end of the horizontime). For this new version, we present three mixed ILP formulations, each one withadvantages and disadvantages. These mixed ILP models are compared according to theCPU time, amount of information collected, gap of unresolved instances, etc. Becausein real life we need to solve problems with a large number of stations, in this thesis,we also propose heuristics methods for the second version of the problem introduced.We build some heuristics that do not depend on the mixed ILP model (as for exampleGreedy heuristics) and also matheuristcs. In our matheuristics our best model (a vehicleevent model) is used as a base for the development of construction of Heuristics aswell as local search heuristics.

L’objectif de ce travail est de développer un système d’affectation des conteneurs aux véhicules autonomes intelligents (AIVs) dans un terminal à conteneurs. Dans la première phase, on a développé un système statique pour résoudre le problème multi-objectif optimisant la durée totale des opérations de déplacement des conteneurs, le temps d’attente des véhicules aux niveaux de points de chargement et de déchargement et l’équilibre de temps de travail entre les véhicules. L’approche proposée est l’algorithme génétique(AG). Une extension de cette approche a été ensuite effectuée pour corriger les limites de la précédente. Pour choisir la meilleure approche, une étude comparative a été réalisée entre trois approches : AG, AG & DIJK et AG & DIJK & HEUR. Les résultats numérique ont montré que l’approche AG & DIJK & HEUR est meilleure. Dans la deuxième phase, on a étudié la robustesse de notre système dans un environnement dynamique. Un retard de l’arrivée d’un navire au port ou un dysfonctionnement de l’un des équipements peutperturber le planning des opérations et donc influencer sur les opérations d’affectation des conteneurs. L’idée était d’ajouter les nouveaux conteneurs aux véhicules qui sont déjà non disponibles. D’autres cas de perturbation comme la congestion routière, la non disponibilité de certaines portions de la routes ont été étudiés expérimentalementEt les résultats numériques ont montré la robustesse de notre approche pour le cas dynamique.Mots-clés : Conteneurs, AIV, routage, optimisation, algorithme génetique, environnement dynamique. / The objective of our work is to develop a container assignment system for intelligent autonomous vehicles (AIVS) in a container terminal. Given the complexity of this problem, it was proposed to decompose it into three problems: The problem of dispatching containers to AIVS, the AIVS routing problem and the problem of scheduling containers to queues of AIVS. To achieve this goal, we developed in the first phase, a static system for multi-objective problem to optimize the total duration of the containers transportation, the waiting time of vehicles at loading points and the equilibrium of working time between vehicles. The approach used was the genetic algorithm (GA). This approach was applied to optimize only the assignment operation without influence on the choice of the path traveled by each AIV. An extension of this work was then made to improve the results found. For this purpose, a comparative study was carried out between three approaches: The first approach is the AG, the second approach is the GA and the Dijkstra algorithm (DIJK) that was used to find the shortest path for each vehicle and the third approach is the AG and DIJK and heuristic (HEUR) which was proposed to choose the nearest vehicle of each container. The numerical study showed the best performance of the AG & DJK & HEUR approach over the other two approaches. In the second phase of our project, the robustness of our system in a dynamic environment has been studied. A delay of the arrival of a ship at the port or malfunction of one of any equipment of the port can cause a delay of one of the operations of loading or unloading process. This will affect the container assignment operation. The idea was to add new containers to vehicles that are already unavailable. The traffic can also cause a delay in arrival of the vehicle at the position of the container or the unavailability of one of the paths crossing point. These cases were investigated experimentally, numerical results showed the robustness of our approach to dynamic case.

Ces deux dernières décennies les systèmes P2P de partage de fichiers sont devenus très populaires grâce aux accès à des ressources diverses, distribuées sur Internet. Parallèlement à l'évolution de cette catégorie de systèmes, les dispositifs mobiles (téléphones cellulaires, PDA et autres appareils portatifs) ont eu un grand succès sur le marché. Équipés d'une technologie de communication sans fil (Bluetooth, et Wifi), ils peuvent communiquer sans nécessiter une infrastructure particulière en utilisant un réseau mobile adhoc (Mobile Adhoc NETwork -MANET). De la même manière, les systèmes P2P peuvent être aussi déployés sur ce type de réseau et deviennent des systèmes P2P mobiles (Mobile 2P systems). Dans le cadre de cette thèse, nous nous intéressons essentiellement à la recherche d'information dans les systèmes P2P et plus précisément au problème de routage de requêtes. La première partie de la thèse, s'est focalisée sur le routage de requêtes dans les systèmes P2P sur Internet. Nous avons proposé (i) un modèle de routage sémantique basé sur l'historique des requêtes. Ce modèle est ensuite instancié pour définir une nouvelle méthode de routage par apprentissage. Pour pallier le problème de démarrage à froid, (ii) nous avons proposé une méthode prédictive de l'intention de l'utilisateur qui construit une base de connaissances à priori pour chaque pair. Enfin, (iii) nous avons proposé une méthode de routage hybride pour traiter le problème d'échec de sélection. Cette méthode est basée sur l'historique des requêtes et le regroupement de pairs dans des groupes sémantiques. La deuxième partie de la thèse, s'est focalisée sur le routage de requêtes dans les systèmes P2P mobiles. L'apparition des MANETs, a soulevé de nouveaux challenges de routage. Ces réseaux souffrent de plusieurs contraintes liées aux supports de transmission ou bien aux dispositifs mobiles. Dans ce cadre, nous avons proposé une méthode de routage pour les systèmes P2P non structurés mobiles basée sur le contexte de l'utilisateur. D'un point de vue technique, toutes ces propositions ont été développées, validées et évaluées grâce aux simulateurs PeerSim et NS2 / Peer-to-peer systems have emerged as platforms for users to search and share information over the Internet. In fact, thanks to these systems, user can share various resources, send queries to search and locate resources shared by other users. Nowadays, mobile and wireless technology has achieved great progress. These devices are also equipped with low radio range technology, like Bluetooth and Wi-Fi, etc. By means of the low radio range technology, they can communicate with each other without using communication infrastructure (e.g. Internet network) and form a mobile ad hoc network (MANET). Hence, P2P file sharing systems can be also deployed over MANET. A challenging problem in unstructured P2P systems is query routing. Researches' efficiency and effectiveness can be improved by making smart decisions for query routing. Our contributions, in this thesis, focus on two complementary axes. Firstly, our research work focalized on P2P systems over Internet. We introduced a novel semantic model for query routing based on past queries, thereafter we instantiated this model to define our specific routing method. In addition, we addressed two difficult challenging problems: (i) the bootstraping (ii) the unsuccessful relevant peers search. Secondly, we are focalized on P2P systems over MANET. Due the nature of MANET, mobile P2P systems suffer from several constraints of wireless medium and energy-limited. Indeed, query routing methods proposed for P2P system over Internet cannot be applied. In this context, we proposed a context-aware integrated routing method for P2P file sharing systems over MANET. The different contributions are developed, validated and evaluated with the network simulators PeerSim and NS2

Le passage à l’échelle des protocoles de routage est un des problèmes les plus critiques pour les réseauxmobiles sans fil à grande envergure. Dans ce cadre, le concept de clusterisation peut être mis à profit dans lafonction de routage afin d’améliorer les performances de ces réseaux. En premier lieu, cette thèse présentenotre algorithme de clusterisation à 1-saut alpha-SSCA (α-Stability Structure Clustering Algorithm) qui apour objectif d’améliorer la stabilité de la structure des clusters. Un algorithme générique de clusterisationà K-sauts est également proposé en ayant le même but de stabilité visé par alpha-SSCA tout en réduisant lenombre de clusters générés et en étant indépendant de la métrique d’élection des cluster-heads. Ensuite, nousprésentons notre proposition d’un protocole de routage à état des liens des clusters qui exploite les apports denotre mécanisme de clusterisation α-SSCA. Ce protocole, appelé CLSR (Cluster-based Link State Routing),vise à réduire le trafic de contrôle afin d’améliorer les performances du réseau à large échelle. Nous avonsproposé aussi une version hiérarchique du protocole CLSR. Ce protocole de routage introduit une hiérarchiedans la structure des clusters qui permet de réduire le nombre de clusters en groupement des clusters prochesdans un même cluster. L’objectif principal de ce protocole hiérarchique est d’améliorer la scalabilité de CLSRquand le nombre de noeuds dans le réseau augmente considérablement. / Scalability is one of critical challenges for routing protocols in large scale mobile wireless networks. In thiscontext, clustering technique seems a promising approach to overcome the scalability problem. First, we proposea one hop clustering algorithm, alpha-SSCA (alpha-Stability Structure Clustering Algorithm), whichaims to improve the stability of the clusters structure. Second, we present a proposal of a generic K-hopsclustering algorithm which is independent of the metrics used to elect cluster-heads. The main contributionof this last algorithm is to enhance the stability of the clusters structure while reducing the number of clusters.Clustering mechanism is introduced in our proposed routing protocol CLSR (Cluster-based Link StateRouting) in order to reduce the control overhead. The main objective of CLSR is to take profit of the stablestructure of clusters to enhance the network scalability.We propose also a second proactive link-state protocolwhich is based on hierarchical clustering. This protocol makes use of hierarchical clustering to more reducethe routing overhead.

Au cours des quinze dernières années, le développement de plateformes embarquées intelligentes et les progrès des protocoles de communication radio ont permis l'émergence de réseaux de capteurs sans-fils (WSN). D'autre part, la démocratisation d'Internet et du Web, ainsi que l'augmentation des débits ont contribué à l'essor d'un nouveau paradigme : le Cloud computing. L'Internet des Objets, (IoT) ou Internet des Objets réalise la convergence entre les réseaux de capteurs et le Cloud computing. De nombreux travaux adressant les problématiques de l'IoT ont étés menés ces dix dernières années, cependant ces propositions manquent ne tiennent pas suffisamment compte des problématiques de sécurité et de protection des données. D'après Gartner, 70 % des plateformes déployées ne disposent pas d'une solution de sécurité efficace, les rendant vulnérables aux attaques. Dans le domaine des monnaies numériques, Bitcoin propose en son sein une nouvelle structure de données authentifiée et trustless permettant la décentralisation de l'enregistrement de transactions en s'appuyant sur un protocole permettant d'obtenir un consensus : la blockchain. Cette thèse se focalise sur l'utilisation de cette nouvelle structure de données dans les WSN dans un contexte IoT, comme base pour la définition d'une architecture sécurisée et adaptative basée sur la blockchain. Le but de cette architecture est d'intégrer les solutions existantes pour l'organisation du réseau et l'accès aux services de manière innovante afin de réaliser l'intégration des WSN avec l'infrastructure web; mais aussi d'y adjoindre une solution répondant aux nouveaux besoins de sécurités et contraintes spécifiques des réseaux de capteurs. Nous proposons pour cela un framework nommé Network Service Loader (NSL) en charge de la gestion de services et d'agents mobiles, auquel s'adjoint notre solution Blockchain Authentication and Trust Module (BATM) en charge de l'authentification, du contrôle d'accès, ainsi que des évaluations de confiance via l'algorithme Maximum Likelihood Trust Estimator (MLTE). / During the last fifteen years, the rise of smart and wireless enabled embedded devices lead to the development of wireless sensor networks (WSN). In the same time, the emerging of Cloud computing with the development of the Internet and the Web as an everyday technology thanks to the rise of bandwidth and processing power leads to new network paradigms. The Internet of Things (IoT) primary goal is to bridge the gap between these technologies and bring WSN sensing and actuating abilities to Cloud applications. We count a significant amount of work targetting the IoT in the last decade, however they lack proper solutions to ensure data privacy and security. Gartner investigations shows that 70 % of connected and smart devices provide little or no security policies and solutions, making both user and devices vulnerable to attackers. In the field of digital currencies, Bitcoin proposed a new authenticated and trustless data structure dedicated to transactions logging in a decentralized network with the help of a consensus protocol : the blockchain. This thesis is focused on bringing the blockchain technology as a new solutions for security in decentralized WSN in the IoT, providing the basis for a secure and adaptative agent-based middleware and execution framework. This framework attempt to federate existing work regarding the architecture of the IoT, but also to tackle security issues regarding network access, agent execution and trust evaluation. To achieve this goal, we propose Network Service Loader (NSL), an agent-based middleware constructed of existing protocols in a new way, along with a new solution called Blockchain Authentication and Trust Module (BATM) dedicated to node and users authentication, access control policies, and trust evaluation through our new Maximum Likelihood Trust Estimator (MLTE) algorithm.

Un des problemes majeurs dans le domaine des telecommunications est de construire des réseaux robustes qui puissent faire face a l'incertitude de la demande. Ayant l'architecture d'un réseau et un budget donne pour le problème d'allocation de la capacité, le but est d'identifier une capacité faisable, qui minimise le pire cas de demande insatisfaite. Premièrement, nous formulons l'incertitude de la demande comme un polytope engendre par un nombre fini de scénarios de la demande. Nous montrons que le problème peut se ramener a la minimisation d'une fonction convexe sur un polyèdre. Nous calculons alors une solution optimale par trois méthodes de plans sécants : Kelley, Elzinga & Moore et faisceaux. Ensuite, nous formulons l'incertitude comme un polyèdre décrit par un nombre fini d'inégalités linéaires, ce qui résulte en un problème considérablement plus difficile. Par conséquent, nous cherchons uniquement des bornes supérieures et inférieures. Quelques idées novatrices sont présentées et l'algorithme de type \Branch & Bound" de Falk & Soland est utilise afin de calculer le maximum d'une fonction convexe additive ; de plus, nous défifinissons une variante de cet algorithme, adaptée a notre situation particulière. Après avoir défini la capacité d'un réseau, l'étape suivante est de calculer le routage optimal dans ce réseau. Nous minimisons la congestion en utilisant comme objectif la fonction moyenne de retard de Kleinrock. Le problème résultant est convexe mais non-linaire et la fonction duale est la somme d'un terme polyédral et d'un terme différentiable. Afin de résoudre ce problème, nous implémentons un algorithme hybride base sur la relaxation Lagrangienne.

Cette thèse constitue une contribution à l'élaboration d'un nouveau système de conception de circuits intégrés, nautile. Elle comporte une étude des différents systèmes existants et a partir de leur synthèse établit la définition d'un nouveau système. Celui-ci doit réaliser un environnement complet de conception de circuits v.l.s.i. Permettant d'être facilement interfaçables avec différents systèmes déjà existants, d'être indépendant de la technologie et de gérer différentes représentations (dessin des masques, schéma électrique, schéma logique) d'un même circuit en assurant la cohérence entre elles. Enfin cette thèse donne une description du prototype réalisé du système nautile, consistant en une structure de donnée orientée objet, en les primitives de gestion de la structure, ainsi qu'en un certain nombre d'outils (routeurs, générateurs divers) ayant ete mis en œuvre

Cette thèse a deux parties. La première traite des jeux stratégiques non-atomiques, la seconde propose des applications de la théorie des jeux aux réseaux de télécommunications. Dans la première partie, les modèles de jeux non-atomiques proposés par Schmeidler (1973) et par Mas-Colell (1984) sont décrits et comparés. Nous montrons alors que ces jeux non-atomiques sont de bonnes approximations de jeux avec un nombre finis de joueurs et dans lesquels l'influence de chacun sur le paiement des autres joueurs est évanescente. Nous proposons ensuite une extension et des variations du modèle de Mas-Colell afin d'obtenir un cadre unificateur pour diverses applications des jeux non-atomiques, telles les jeux de routage, les jeux de foule et les jeux évolutionnaires. Ces trois types de jeu sont étudiés. Enfin nous étendons le concept de stratégie évolutionnairement stable au modèle de Schmeidler, ce qui donne un critère de sélection des équilibres. La deuxième partie traite de problèmes de routage dans les réseaux. Tout d'abord nous modélisons des situations où deux types de joueur partagent un réseau, des joueurs ayant une influence certaine sur la répartition des paquets dans le réseau et des joueurs n'en ayant pas. Puis, nous étudions la convergence de dynamiques de meilleures réponses dans des réseaux d'architecture simple. Finalement, nous modélisons le problème du routage mutipoint-à-multipoint.

Dans ce mémoire, nous présentons une méthode de résolution du problème de tournées de véhicules grâce à une approche polyèdrale. Un état de l'art est fait sur la connaissance du polyèdre correspondant aux solutions de ce probleme et de nouvelles inégalités valides (et induisant des facettes) sont présentées pour ce polyèdre. Nous décrivons ensuite des heuristiques pour la séparation des contraintes les plus importantes ainsi qu'un algorithme de "Branchement et Coupe" qui nous permet d'améliorer les résultats connus pour la résolution exacte du problème de tournées.