Wireless ad hoc networks are expected to play an important role in civilian and military settings where wireless access to wired backbone is either ineffective or impossible. Wireless sensor networks are effective in remote data acquisition. Congestion control and power consumption in wireless ad hoc networks have received a lot of attention in recent research. Several algorithms have been proposed to reduce congestion and power consumption in wireless ad hoc and sensor networks. In this thesis, we focus upon two schemes, which deal with congestion control and power consumption issues. This thesis consists of two parts. In the first part, we describe a randomization scheme for congestion control in dynamic source routing protocol, which we refer to as RDSR. We also study a randomization scheme for GDSR protocol, a GPS optimized variant of DSR. We discuss RDSR and RGDSR implementations and present extensive simulation experiments to study their performance. Our results indicate that both RGDSR and RDSR protocols outperform their non-randomized counterparts by decreasing the number of route query packets. Furthermore, a probabilistic congestion control scheme based on local tuning of routing protocol parameters is shown to be feasible. In the second part we present a simulation based performance study of energy aware data centric routing protocol, EAD, proposed by X. Cheng and A. Boukerche. EAD reduces power consumption by requiring only a small percentage of the network to stay awake. Our experiments show that EAD outperforms the well-known LEACH scheme.

As mobility and computing becomes ever more pervasive in society and business, the non-optimal use of radio resources has created many new challenges for telecommunication operators. Usage patterns of modern wireless handheld devices, such as smartphones and surfboards, have indicated that the signaling traffic generated is many times larger than at a traditional laptop. Furthermore, in spite of approaching theoretical limits by, e.g., the spectral efficiency improvements brought by 4G, this is still not sufficient for many practical applications demanded by end users. Essentially, users located at the edge of a cell cannot achieve the high data throughputs promised by 4G specifications. Worst yet, the Quality of Service bottlenecks in 4G networks are expected to become a major issue over the next years given the rapid growth of mobile devices. The main problems are because of rigid mobile systems architectures with limited possibilities to reconfigure terminals and base stations depending on spectrum availability. Consequently, new solutions must be developed that coexist with legacy infrastructures and more importantly improve upon them to enable flexibility in the modes of operation. To control the intelligence required for such modes of operation, cognitive radio technology is a key concept suggested to be part of the so-called beyond 4th generation mobile networks. The basic idea is to allow unlicensed users access to licensed spectrum, under the condition that the interference perceived by the licensed users is minimal. This can be achieved with the help of devices capable of accurately sensing the spectrum occupancy, learning about temporarily unused frequency bands and able to reconfigure their transmission parameters in such a way that the spectral opportunities can be effectively exploited. Accordingly, this indicates the need for a more flexible and dynamic allocation of the spectrum resources, which requires a new approach to cognitive radio network management. Subsequently, a novel architecture designed at the application layer is suggested to manage communication in cognitive radio networks. The goal is to improve the performance in a cognitive radio network by sensing, learning, optimization and adaptation.

"This thesis explores techniques for improving the Quality of Service (QoS) driven routing of IP traffic in a Network Centric Military Communications System within an HC3 (High Capacity Communications Capability) tiered topology. In this specialized network various routing algorithms, including traditional, QoS-constrained search-based, and heuristic approaches, were evaluated. An automatic system for the probabilistic generation of appropriate networks and traffic was created for Monte Carlo simulation of the systems and testing of the various routing algorithms. A new algorithm we propose, based upon a hiercharical decomposition of routes about the minimum distance routes, is described and tested. These results provide both insight into this problem and demonstrate the possibility of highly optimized solutions without exhaustive search."

The Internet traffic is constantly increasing following the emergence of new network applications like social networks, peer-to-peer, IP phone or IP television. In addition, these new applications request better path availability and path quality. Indeed the efficiency of these applications is strongly related to the quality of the underlying network. In that context network operators make use of traffic engineering techniques in order to improve the quality of the routes inside their network, but also to reduce the network cost of increased traffic handling with a better utilization of existing resources. This PhD thesis covers several topics of Traffic Engineering and Fast Restoration in IP/MPLS networks. Our first contribution is related to the definition of a well-engineered network. In the literature mathematical formulation of Traffic Engineering (TE) requirements are very diverse. We have thus performed a comparative study of many objective functions, in order to differentiate them and choose in a rational way the one that best reflects Traffic Engineering goals. We have also designed a method approaching optimal TE, whereby we divide the traffic matrix in N sub-matrices and route them independently, based on the derivatives of the objective function. The second topic addressed in this work concerns link weight optimizers (LWOs). Link weight optimization is the traffic engineering {it "standard"} technique in networks running link state routing protocols (which are widely used in transit networks). These link weight optimizers suffer from several limitations due to the BGP (Border Gateway Protocol) Hot-Potato rule, which is basically not considered by such optimizers. Therefore we have proposed a BGP-aware link weight optimization method that takes problematic Hot-Potato effects into account, and even turns them into an advantage. We have also studied how LWOs behave in big networks which have to use BGP route reflectors. Finally we have studied whether forwarding loops can appear or not when traffic is split among multiple equivalent egress routers, an optional BGP feature that we did use in our Hot-Potato aware LWO. Our last contribution concerns network resilience. We have proposed a solution for a rapid recovery from a link or node failure in an MPLS network. Our solution allows a decentralized deployment combined with a minimal bandwidth usage while requiring only reduced amount of information to flood in the network. This method is the first that makes possible a decentralized deployment combined with an optimal resource consumption. To easily simulate and test the methods proposed in this work, we have also contributed to the development of TOTEM - a TOolbox for Traffic Engineering Methods.

This study discusses the routing optimization techniques and algorithms for communication networks. Preventing data loss on overloaded communication links and utilizing link bandwidths efficiently are the main problems of traffic engineering. Load balancing and routing problems are solved using both by heuristics such as genetic algorithms, and simulation techniques. These algorithms work on destination-based or flow-based routing techniques and mainly change the link weight system or try to select the best routes set upon K-routes routing table respectively to optimize network utilization. In this study, first a definition of the network routing optimization problem will be made. Then the heuristics to solve the problem will be discussed and finally an analysis of these heuristics will be made on sample network models. This thesis includes a discussion about the performance of different optimization heuristics working as a part of the centralized network load balancing systems.

Cette thèse porte sur la planification des tournées de soins pour l'hospitalisation à domicile. Sous l'impulsion des différentes politiques publiques de santé mises en place en France, la demande des patients de recevoir leur traitement dans un environnement familier et sécurisant n'a cessé de croître. Faisant apparaître de nouvelles problématiques d'organisation au sein des établissements d'hospitalisation à domicile, notre travail porte sur l'optimisation de la planification des tournées de soins en considérant des contraintes médicales, logistiques et économiques. Dans un premier temps, nous étudions la planification des tournées de soins hospitaliers à domicile en portant un intérêt particulier aux contraintes de fenêtres de temps et de synchronisation des visites. En rendant ces contraintes souples, nous apportons plus de flexibilité à la modélisation du problème en définissant individuellement les souhaits des patients pour recevoir leurs soins afin d'améliorer la qualité de la planification obtenue et la satisfaction des patients. Dans un second temps, nous intégrons à notre modélisation l'équilibrage de la charge de travail du personnel soignant. Cet aspect ne doit en effet pas être négligé afin d'obtenir une certaine équité et s'assurer de l'applicabilité de notre solution. Par la suite, nous étudions le problème sous sa forme multi-objectif. La hiérarchisation des objectifs pouvant se révéler déroutante pour les décideurs, nous proposons un algorithme mémétique multi-objectif afin d'obtenir un ensemble de solutions représentant différents compromis entre les objectifs. Enfin, la dernière partie de cette thèse s'intéresse à la planification des tournées de soins hospitaliers à domicile dans un contexte multi-centre de soins. La dispersion géographique des patients sur le territoire pouvant entraîner l'ouverture de nouveaux centres de soins, l'affectation des soignants aux centres de soins devient un nouvel aspect à optimiser. Pour chaque problématique, des expériences sont réalisées afin d'évaluer la qualité de nos méthodes de résolution sur des instances de la littérature. / This thesis deals with the planning of care routes for home health care. Under the impulse of the various public health policies put in place in France, the demand for patients to receive their treatment in a familiar and safe environment has steadily increased. Revealing new organizational problems in home health care structures, our work focuses on optimizing care routes planning by considering medical, logistical and economic constraints. As a first step, we study the planning of home health care routes with a particular focus on time window and synchronization constraints. By relaxing these constraints, we bring more flexibility to problem modeling by individually defining the wishes of patients to receive their treatment in order to improve the quality of patient planning and patient satisfaction. In a second step, we integrate in our modeling the workload balancing of the caregivers. This aspect must not be neglected in order to obtain fairness and ensure the applicability of our planning. Subsequently, we study the problem in its multi-objective form. The prioritization of objectives may be confusing for the decision makers, we propose a memetic algorithm for multi-objective optimization in order to obtain a set of solutions representing various trade-offs between the objectives. Finally, the last part of this thesis focuses on the assignment of visits and caregivers to home health care centers in a multi-center configuration. The geographical dispersion of patients on the territory may lead to the opening of new centers, the assignment of caregivers to home health care centers is becoming a new aspect to optimize. For each problem, experiments are carried out in order to evaluate the quality of our solving methods on instances of the literature.

This thesis considers the Two-Stage Vehicle Routing Problem (VRP) with Profits and Buffers, which generalizes various optimization problems that are relevant for practical applications, such as the Two-Machine Flow Shop with Buffers and the Orienteering Problem. Two optimization problems are considered for the Two-Stage VRP with Profits and Buffers, namely the minimization of total time while respecting a profit constraint and the maximization of total profit under a budget constraint. The former generalizes the makespan minimization problem for the Two-Machine Flow Shop with Buffers, whereas the latter is comparable to the problem of maximizing score in the Orienteering Problem. For the three problems, a theoretical analysis is performed regarding computational complexity, existence of optimal permutation schedules (where all vehicles traverse the same nodes in the same order) and potential gaps in attainable solution quality between permutation schedules and non-permutation schedules. The obtained theoretical results are visualized in a table that gives an overview of various subproblems belonging to the Two-Stage VRP with Profits and Buffers, their theoretical properties and how they are connected. For the Two-Machine Flow Shop with Buffers and the Orienteering Problem, two metaheuristics 2BF-ILS and VNSOP are presented that obtain favorable results in computational experiments when compared to other state-of-the-art algorithms. For the Two-Stage VRP with Profits and Buffers, an algorithmic framework for Iterative Search Algorithms with Variable Neighborhoods (ISAVaN) is proposed that generalizes aspects from 2BF-ILS as well as VNSOP. Various algorithms derived from that framework are evaluated in an experimental study. The evaluation methodology used for all computational experiments in this thesis takes the performance during the run time into account and demonstrates that algorithms for structurally different problems, which are encompassed by the Two-Stage VRP with Profits and Buffers, can be evaluated with similar methods. The results show that the most suitable choice for the components in these algorithms is dependent on the properties of the problem and the considered evaluation criteria. However, a number of similarities to algorithms that perform well for the Two-Machine Flow Shop with Buffers and the Orienteering Problem can be identified. The framework unifies these characteristics, providing a spectrum of algorithms that can be adapted to the specifics of the considered Vehicle Routing Problem.:1 Introduction 2 Background 2.1 Problem Motivation 2.2 Formal Definition of the Two-Stage VRP with Profits and Buffers 2.3 Review of Literature on Related Vehicle Routing Problems 2.3.1 Two-Stage Vehicle Routing Problems 2.3.2 Vehicle Routing Problems with Profits 2.3.3 Vehicle Routing Problems with Capacity- or Resource-based Restrictions 2.4 Preliminary Remarks on Subsequent Chapters 3 The Two-Machine Flow Shop Problem with Buffers 3.1 Review of Literature on Flow Shop Problems with Buffers 3.1.1 Algorithms and Metaheuristics for Flow Shops with Buffers 3.1.2 Two-Machine Flow Shop Problems with Buffers 3.1.3 Blocking Flow Shops 3.1.4 Non-Permutation Schedules 3.1.5 Other Extensions and Variations of Flow Shop Problems 3.2 Theoretical Properties 3.2.1 Computational Complexity 3.2.2 The Existence of Optimal Permutation Schedules 3.2.3 The Gap Between Permutation Schedules an Non-Permutation 3.3 A Modification of the NEH Heuristic 3.4 An Iterated Local Search for the Two-Machine Flow Shop Problem with Buffers 3.5 Computational Evaluation 3.5.1 Algorithms for Comparison 3.5.2 Generation of Problem Instances 3.5.3 Parameter Values 3.5.4 Comparison of 2BF-ILS with other Metaheuristics 3.5.5 Comparison of 2BF-OPT with NEH 3.6 Summary 4 The Orienteering Problem 4.1 Review of Literature on Orienteering Problems 4.2 Theoretical Properties 4.3 A Variable Neighborhood Search for the Orienteering Problem 4.4 Computational Evaluation 4.4.1 Measurement of Algorithm Performance 4.4.2 Choice of Algorithms for Comparison 4.4.3 Problem Instances 4.4.4 Parameter Values 4.4.5 Experimental Setup 4.4.6 Comparison of VNSOP with other Metaheuristics 4.5 Summary 5 The Two-Stage Vehicle Routing Problem with Profits and Buffers 5.1 Theoretical Properties of the Two-Stage VRP with Profits and Buffers 5.1.1 Computational Complexity of the General Problem 5.1.2 Existence of Permutation Schedules in the Set of Optimal Solutions 5.1.3 The Gap Between Permutation Schedules an Non-Permutation Schedules 5.1.4 Remarks on Restricted Cases 5.1.5 Overview of Theoretical Results 5.2 A Metaheuristic Framework for the Two-Stage VRP with Profits and Buffers 5.3 Experimental Results 5.3.1 Problem Instances 5.3.2 Experimental Results for O_{max R, Cmax≤B} 5.3.3 Experimental Results for O_{min Cmax, R≥Q} 5.4 Summary Bibliography List of Figures List of Tables List of Algorithms

Grâce aux avancées conjointes des systèmes microélectroniques, des technologies sans fil et de la microélectronique embarquée, les réseaux de capteurs sans fil (RCsF) ont récemment pu voir le jour. Très sophistiqués et en interaction directe avec leur environnement, ces systèmes informatiques et électroniques communiquent principalement à travers des réseaux radio qui en font des objets communicants autonomes. Ils offrent l'opportunité de prendre en compte les évolutions temporelles et spatiales du monde physique environnant. Les RCsF se retrouvent donc au cœur de nombreuses applications couvrant des domaines aussi variés que la santé, la domotique, l'intelligence ambiante, les transports, la sécurité, l'agronomie et l'environnement. Ils connaissent un véritable essor et ce dans divers domaines des STIC : hardware, système d'exploitation, conception d'antenne, système d'information, protocoles réseaux, théorie des graphes, algorithmique distribuée, sécurité, etc. L’intérêt des communautés issues de la recherche et de l’industrie pour ces RCsF s’est accru par la potentielle fiabilité, précision, flexibilité, faible coût ainsi que la facilité de déploiement de ces systèmes. La spontanéité, l’adaptabilité du réseau et la dynamicité de sa topologie dans le déploiement des RCsF soulèvent néanmoins de nombreuses questions encore ouvertes. Dans le cadre de cette thèse, nous nous sommes intéressés aux aspects liés à la problématique du routage dans un RCsF, l’objectif étant de proposer des approches algorithmiques permettant de faire du routage adaptatif multi critères dans un RCsF. Nous nous sommes concentrés sur deux critères principaux : la consommation d’énergie dans les capteurs et le délai d’acheminement des informations collectées par les capteurs. Nous avons proposé ainsi un nouveau protocole de routage, appelé EDEAR (Energy and Delay Efficient Adaptive Routing), qui se base sur un mécanisme d’apprentissage continu et distribué permettant de prendre en compte la dynamicité du réseau. Celui-ci utilise deux types d’agents explorateurs chargés de la collecte de l’information pour la mise à jour des tables de routage. Afin de réduire la consommation d’énergie et la surcharge du réseau, nous proposons également un processus d’exploration des routes basé sur une diffusion optimisée des messages de contrôle. Le protocole EDEAR calcule les routes qui minimisent simultanément l’énergie consommée et le délai d’acheminement des informations de bout en bout permettant ainsi de maximiser la durée de vie du réseau. L’apprentissage se faisant de manière continue, le routage se fait donc de façon évolutive et permet ainsi une réactivité aux différents évènements qui peuvent intervenir sur le réseau. Le protocole proposé est validé et comparé aux approches traditionnelles, son efficacité au niveau du routage adaptatif est mise particulièrement en évidence aussi bien dans le cas de capteurs fixes que de capteurs mobiles. En effet, celui-ci permet une meilleure prise en compte de l'état du réseau contrairement aux approches classiques / Through the joint advanced microelectronic systems, wireless technologies and embedded microelectronics, wireless sensor networks have recently been possible. Given the convergence of communications and the emergence of ubiquitous networks, sensor networks can be used in several applications and have a great impact on our everyday life. There is currently a real interest of research in wireless sensor networks; however, most of the existing routing protocols propose an optimization of energy consumption without taking into account other metrics of quality of service. In this thesis, we propose an adaptive routing protocol called "EDEAR" which takes into account both necessary criteria to the context of communications in sensor networks, which are energy and delay of data delivery. We are looking the routes for optimizing a nodes’ lifetime in the network, these paths are based on joint optimization of energy consumption and delay through a multi criteria cost function. The proposed algorithm is based on the use of the dynamic state-dependent policies which is implemented with a bio-inspired approach based on iterative trial/error paradigm. Our proposal is considered as a hybrid protocol: it combines on demand searching routes concept and proactive exploration concept. It uses also a multipoint relay mechanism for energy consumption in order to reduce the overhead generated by the exploration packets. Numerical results obtained with NS simulator for different static and mobility scenario show the efficiency of the adaptive approaches compared to traditional approaches and proves that such adaptive algorithms are very useful in tracking a phenomenon that evolves over time

Les applications multimédias, dans les réseaux de capteurs sans fil, véhiculent des données volumineuses, qui nécessitent un taux de transmission élevé et un traitement intensif et par conséquent une consommation d'énergie importante. Transmettre efficacement ces flux hétérogènes, tout en assurant leur fiabilité et garantir les exigences de QoS, avec les ressources limitées disponibles, en particulier dans les contextes critiques, demeure un verrou scientifique ouvert. C’est pourquoi, dans le cadre de cette thèse, nous nous sommes intéressés aux aspects liés : au routage, à la tolérance aux pannes et à la gestion des interférences dans les RCMSF.Compte tenu, du très faible nombre de protocoles de routage, qui ont approché la phase expérimentale et encore moins ceux qui l’ont abordé pendant la transmission des données en temps réel, nous avons développé dans ce contexte, un protocole routage géographique baptisé GNMFT (Geographic Non-interfering Multipath Fault-tolerant),En premier lieu, nous avons amélioré le mode de sélection des nœuds, utilisé par le transfert glouton, pour faire face au problème du Minimum-local, où une fonction objective multicritères (distance, énergie et puissance de réception) relative au choix du prochain saut a été définie. Puis, nous avons introduit une phase d’optimisation des chemins construits afin d’éliminer les boucles et une approche adaptative gérant les transmissions simultanées des différents trafics.Par la suite, nous nous sommes orientés vers la tolérance aux pannes, pour assurer la fiabilité des données transmises ainsi que la connectivité du réseau. A cet effet, nous avons modélisé le nombre des paquets perdus durant la livraison des paquets et proposé deux mécanismes : un curatif pour réparer les défaillances soudaines et un préventif afin d’anticiper l’épuisement des batteries. Les deux mécanismes sont combinés avec une stratégie de basculement dynamique lors de la construction des chemins alternatives.En dernier lieu, nous avons présenté un modèle d’interférence et un troisième mécanisme qui limite les interactions entre les liens adjacents. De plus, nous avons défini également un modèle de perte de chemins dans un environnement multi-paires (source,sink) et nous avons calculé le coefficient de probabilité d’erreurs basée sur une fonction de distance qui sépare les flux de données. Une nouvelle métrique a été ajouté dans la fonction objective, relative à la somme des bruits des nœuds actifs qui interférent sur les nœuds du ForwardingSet du nœud courant.Les résultats obtenus montrent l’efficacité des approches proposées qui ont été étudiées et validées à la fois par simulation et sur un banc d’essai expérimental. / Multimedia applications in WSNs convey large data (image, audio and video) that requires high transmission rate and intensive treatment and therefore high energy consumption. Effectively transmit these heterogeneous flows, while ensuring their reliability and guaranteeing QoS requirements, with the limited resources available, especially in critical contexts, remains an open scientific problem. That is why, in this thesis, we are interested in aspects related to : routing, fault tolerance and interference management in WMSNs.Given the very low number of routing protocols, that have approached the experimental phase and still less those who approached it during data transmission in real time, we developed in this context, a geographic routing protocol baptised GNMF (Geographic Non-interfering Multipath Fault-tolerant),First, we improved node's selection mode used by the greedy-forwarding, to deal with local minimum problem, where a multi-criteria objective function (distance, energy and reception power) related to next-hop choice has been defined. Then, we introduced an optimization phase of built paths to eliminate loops and an adaptive approach to manage simultaneous traffic transmissions.After that, we oriented towards fault tolerance, to ensure transmitted data reliability and network connectivity. To this end, we modeled the number of lost packets during package delivery and proposed two mechanisms. The curative is used when sudden failures occurs and the preventive to anticipate batteries depletion. Both are combined with a dynamic failover strategy during alternative paths construction.Finally, we presented an interference model and a third mechanism that limits interactions between adjacent links. In addition, we also defined a path loss model in a multipairs environment (source, sink) and computed the error probability coefficient based on a distance function that separates the data flows. A new metric has been added in the objective function, related to noise sum of the active nodes that interferes on forwarding set nodes of the current node.Obtained results show the effectiveness of the proposed approaches that have been studied and validated both by simulation and on an experimental testbed.