Cette thèse est une thèse CIFRE entre le LORIA et la société MEDETIC et porte sur la conception des systèmes de télésurveillance pour le maintien à domicile des personnes âgées.Le système est conçu aux personnes âgées qui veulent passer leur vieillesse dans leur propre maison, à cause de son potentiel pour augmenter l'indépendance et la qualité de la vie. Cela profiterait non seulement aux personnes âgées qui veulent vivre dans leur propre maison, mais aussi le système de santé publique en coupant des prix de façon significative.Mis à part la conception d'une architecture de télésurveillance « Vill’Âge® »basée sur des réseaux de capteurs hétérogènes (Domotique, IEEE802.15.4/Zigbee, Wifi, Bluetooth), la thèse a contribué essentiellement sur la proposition d'un protocole de clustering et de routage dans le réseau de capteurs sans fil avec une approche de la logique floue, et d'un middleware pour la collecte et le traitement des données des capteurs avec la gestion de la qualité de service comme particularité.Une première plateforme de test à été développée à Colmar (MEDETIC) et une seconde, plus complète et fait suite de cette thèse, est en cours de développement au LORIA (http://infositu.loria.fr/).Nous avons participé dans le concours de ministère de l'Enseignement supérieur et de la recherche avec un projet intitulé MPIGate: « Multi Protocol Interface and Gateway for telecare, environment Monitoring and Control » et nous avons gagné le prix de ce concours au niveau d’émergence. / This thesis is a thesis CIFRE between LORIA and the MEDETIC Company and focuses on the design of telehomecare system for the elderly.In addition to the design of a remote surveillance architecture “Vill’Âge ®” based on networks of heterogeneous sensor (home automation, IEEE802.15.4/Zigbee, Wifi, Bluetooth), thesis has contributed essentially on the proposal of a clustering and routing protocol in the network of wireless sensors with an approach to fuzzy logic, and of a middleware for the collection and processing of data from sensors with the management of the quality of service as a special feature.A first platform was developed at Colmar (MEDETIC) and a second who is more complete is under development at LORIA (http://infositu.loria.fr/).By using this system, MEDeTIC, offers a new concept of smart homes for the senior citizens, named in French “Maisons Vill’Âge”. The first housing schemes are being built in 2 departments of France. A flat is entirely equipped to act as a demonstrator and as laboratory of research and development.The system is designed for the elderly who wish to spend their old age in their own home, because of its potential to increase independence and quality of life. This would not only benefit the elderly who want to live in their own home, but also the national health care system by cutting costs significantly. Based on this PhD thesis, MPIGate, a “Multiprotocol Interface and Gateway for for telecare, environment”, has been developed. MPIGate was awarded in the competition of the Ministry of Higher Education and Research and OSEO 2010

Les réseaux optiques à commutation de rafales (OBS) sont des candidats pour jouer un rôle important dans le cadre des réseaux optiques de nouvelle génération. Dans cette thèse, nous nous intéressons au routage adaptatif et au provisionnement de la qualité de service dans ce type de réseaux. Dans une première partie de la thèse, nous nous intéressons à la capacité du routage multi-chemins et du routage alternatif (par déflection) à améliorer les performances des réseaux OBS, pro-activement pour le premier et ré-activement pour le second. Dans ce contexte, nous proposons une approche basée sur l’apprentissage par renforcement où des agents placés dans tous les nœuds du réseau coopèrent pour apprendre, continuellement, les chemins du routage et les chemins alternatifs optimaux selon l’état actuel du réseau. Les résultats numériques montrent que cette approche améliore les performances des réseaux OBS comparativement aux solutions proposées dans la littérature. Dans la deuxième partie de cette thèse, nous nous intéressons au provisionnement absolu de la qualité de service où les performances pire-cas des classes de trafic de priorité élevée sont garanties quantitativement. Plus spécifiquement, notre objectif est de garantir la transmission sans pertes des rafales de priorité élevée à l’intérieur du réseau OBS tout en préservant le multiplexage statistique et l’utilisation efficace des ressources qui caractérisent les réseaux OBS. Aussi, nous considérons l’amélioration des performances du trafic best effort. Ainsi, nous proposons deux approches : une approche basée sur les nœuds et une approche basée sur les chemins. Dans l’approche basée sur les nœuds, un ensemble de longueurs d’onde est assigné à chaque nœud du bord du réseau OBS pour qu’il puisse envoyer son trafic garanti. Cette assignation prend en considération les distances physiques entre les nœuds du bord. En outre, nous proposons un algorithme de sélection des longueurs d’onde pour améliorer les performances des rafales best effort. Dans l’approche basée sur les chemins, le provisionnement absolu de la qualité de service est fourni au niveau des chemins entre les nœuds du bord du réseau OBS. À cette fin, nous proposons une approche de routage et d’assignation des longueurs d’onde qui a pour but la réduction du nombre requis de longueurs d’onde pour établir des chemins sans contentions. Néanmoins, si cet objectif ne peut pas être atteint à cause du nombre limité de longueurs d’onde, nous proposons de synchroniser les chemins en conflit sans le besoin pour des équipements additionnels. Là aussi, nous proposons un algorithme de sélection des longueurs d’onde pour les rafales best effort. Les résultats numériques montrent que l’approche basée sur les nœuds et l’approche basée sur les chemins fournissent le provisionnement absolu de la qualité de service pour le trafic garanti et améliorent les performances du trafic best effort. En outre, quand le nombre de longueurs d’ondes est suffisant, l’approche basée sur les chemins peut accommoder plus de trafic garanti et améliorer les performances du trafic best effort par rapport à l’approche basée sur les nœuds. / Optical Burst Switching (OBS) networks are candidates to play an important role in the context of next generation optical networks. In this thesis, we are interested in adaptive routing and quality of service provisioning for these networks. In the first part of the thesis, we study the capability of multi-path routing and alternative routing (deflection routing) to improve the performance of the OBS network proactively for the former and reactively for the latter. In this context, we propose a reinforcement learning-based approach where learning agents, placed in each OBS node, cooperate to learn, continuously, optimal routing paths and alternative paths according to the current state of the network. Numerical results show that the proposed approach improves the performance of the OBS network compared to existing solutions in the literature. In the second part of the thesis, we consider the problem of absolute quality of service provisioning for OBS networks where worst-case performance of high priority traffic is guaranteed quantitatively. Particularly, we are interested in the loss-free transmission, inside the OBS network, of high priority bursts, while preserving statistical multiplexing gain and high resources utilization of the OBS network. Also, we aim to improve the performance of best effort traffic. Hence, we propose two approaches: (a) the node-based approach; and (b) the path-based approach. In the node-based approach, we propose to assign a set of wavelengths to each OBS edge node that it can use to send its guaranteed traffic. This assignment takes into consideration physical distances between edge nodes. Furthermore, we propose a wavelength selection algorithm to improve the performance of best effort bursts. In the path-based approach, absolute quality of service provisioning is offered at end-to-end path level. To do this, we propose a routing and wavelength assignment approach which aims to reduce the number of wavelengths required to establish contention free paths. Nevertheless, if this objective cannot be reached because of the limited number of wavelengths in each fiber link, we propose an approach to synchronize overlapping paths without the need for additional equipments for synchronization. Here again, we propose a wavelength selection algorithm for best effort bursts. Numerical results show that both the node-based and the path-based approaches successfully provide absolute quality of service provisioning for guaranteed traffic and improve the performance of best effort traffic. Also, path-based approach could accommodate more guaranteed traffic and improve the performance of best effort traffic compared to node-based approach when the number of wavelengths is sufficient.

Les Réseaux de Capteurs Sans Fil (RCSFs) constituent une classe particulière des réseaux Ad hoc, faisant l'objet de recherches intensives. Ils sont considérés comme un outil très puissant pour connecter le monde physique et le monde numérique. Ils se composent d'un grand nombre de noeuds capteurs dotés de ressources limitées en termes d'énergie, de portée de capture et de communication, de vitesse de traitement et de capacité de stockage. Ils sont déployés dans un environnement intérieur ou extérieur, et ce dans de nombreux domaines d'application tels que l'armée, l'environnement, la santé, la maison et l'agriculture. La rareté des ressources des noeuds capteurs et la non fiabilité des liaisons sans fil motivent la plupart des problématiques dans le domaine des RCSFs, à savoir l'énergie, la couverture, la connectivité, le routage, la tolérance aux pannes et la sécurité. L'objectif de cette thèse est de proposer un protocole de surveillance inter-couches, à efficacité énergétique et fiable, pour la surveillance des zones sensibles clôturées, tel qu'un site pétrolier ou nucléaire, utilisant les réseaux de capteurs sans fil avec un cycle d'activité, et avec prise en compte des liens asymétriques dus au phénomène de l'irrégularité de la radio. Initialement, le protocole proposé identifie les noeuds de bordure du RCSF pour les utiliser comme nœuds sentinelles, c.-à-d., des noeuds qui sont toujours dans un état actif. Les noeuds restants sont utilisés en tant que noeuds relais avec un cycle d'activité, pendant la phase de routage des alertes vers le noeud puits. Le processus d'identification des noeuds de bordure ainsi que le routage des alertes, sont assurés par le protocole Greedy Perimeter Stateless Routing through Symmetrical Links (GPSR-SL) qui est une version améliorée du protocole GPSR, reposant sur un graphe de connectivité représenté sous forme de disques non-unité (N-UDG). Le protocole de surveillance inter-couches proposé a été implémenté et ses performances ont été évaluées en utilisant l'environnement de simulation OMNeT++/Castalia. Les résultats de performance montrent que ce protocole permet d'obtenir un ratio de livraison de paquets plus élevé d'environ 3.63%, une efficacité énergétique et une latence satisfaisante par rapport au même protocole basé sur le GPSR original. / Wireless Sensor Networks (WSNs) are a special class of Ad hoc networks, which are under intensive research.They are considered as a very powerful tool to connect the physical and the digital worlds. They consist of a largenumber of sensor nodes that are characterized with limited resources in terms of energy, range of sensing and communication, processing speed and storage capacity.They are deployed in an indoor or outdoor environment in many application domains such as army, environment, health, home and agriculture. The scarcity of sensor node resources and the unreliability of wireless links drive most of the research issues in the field of WSNs, namely energy, coverage, connectivity, routing, fault tolerance and security. The aim of this thesis is to propose an energyefficient and reliable cross-layer surveillance protocol for sensitive fenced areas, such as oil or nuclear sites, using duty-cycled WSNs with asymmetrical links due to the radio irregularity phenomenon. Initially, the proposed protocol identifies the boundary nodes of the deployedWSN, to be used as sentinel nodes, i.e., nodes that are always in an active state. The remaining nodes are usedas duty-cycled relay nodes during the routing phase to relay alerts towards the sink. The boundary nodes identification process and alert routing are both performed using an enhanced version of the Greedy Perimeter Stateless Routing (GPSR) protocol, referred to as GPSR over Symmetrical Links (GPSR-SL) and which relies on a Non Unit Disk Graph (N-UDG). The proposed cross-layer surveillance protocol has been implemented and its performance has been evaluated under the OMNeT++/Castalia simulation environment. Performance results show that this protocol achieves higher Packet Delivery Ratio by up to 3.63%, energy .efficiency and satisfactory latency when compared to the same protocol based on the original GPSR.

Les problèmes majeurs de la génération automatique du dessin des masques des circuits intégrés sont la dépendance vis-à-vis des règles de dessin et le dimensionnement correct des transistors. Les méthodes traditionnelles, telles que l'utilisation de cellules pré-caractérisées, manquent de flexibilité, car les portes des bibliothèques (en nombre limité) sont dessinées et dimensionnées (independarnment de l'application) pour une technologie donnée. Les méthodes de synthèse automatique du dessin des masques ont pour but de surmonter ces problèmes. Les techniques les plus couramment utilisées sont le "gate-matrix" et le "linear-matrix". L'indépendance vis-à-vis des règles de dessin est obtenue en utilisant la technique de description symbolique (dessin sous une grille unitaire), et les dimensions des transistors sont définies par le concepteur ou par un outil de dimensionnement. Nous proposons une méthode et un prototype logiciel pour la synthèse automatique des masques, en utilisant le style "linear-matrix multi-bander". La description d'entree du générateur est un fichier format SPICE (au niveau transistor), ce qui permet d'avoir un nombre très élevé de cellules, en particulier les portes complexes (A01), et ainsi avoir une meilleure optimisation lors de la phase d'assignation technologique. Les macro-cellules générées doivent être assemblées afin de réaliser un circuit complet. Deux contraintes supplémentaires sont ainsi imposées au générateur: malléabilité de la forme et position des broches d'entrées/sorties sur la périphérie de la macro-cellule. Les macro-cellules sont assemblées en utilisant un environnement de conception industriel. Les contributions de ce mémoire de doctorat sont d'une part le développement d'un générateur de macro-cellules flexible ayant les caracteristiques d'indépendance aux règles de dessin et d'intégration dans un environnement de macro-cellules, et d'autre part l'étude detailée des paramètres qui déterminent la surface occupée, les performances électriques et la puissance dissipée des macro-cellules générées automatiquement. / The main problems of the automatic layout synthesis are the design rules dependence and the transistor sizing. The traditional layout synthesis methods, like standard-cells, are not flexible, since the cells in the libraries are designed and sized for a specific technology. In this way, the designer must change his library at each technology improvement. The automatic layout synthesis methods overcomes these problems (design rules dependence and transistor sizing). Examples of layout styles are gate-matrix and linear-matrix. The technology independence is achieved by symbolic description (layout under an unitary grid), and the transistor sizes are defined by the designer or by a sizing tool. From these two constraints, we develop an automatic layout synthesis tool, using a linear-matrix multi-row layout style. The input description for our tool is a Spice file. This descriptions allows to define a greater number of cells (mainly AOIs gates), resulting a technology mapping with less constraints. The generated macro-cells must be assembled in order to construct a complete circuit. Two additional constraints are then imposed to the generator : variable aspect ratio and placement of the inputs/outputs pins in the macro-cell border. The macro-cells are assembled by an industrial CAD environment. The main contributions of this thesis are the development of a macro-cell generator (with the characteristics of technology independence and easy integration in a macro-cell environment) and the analysis of the parameters playing a role in the area, delay and power consumption.

Cette thèse apporte des contributions à la modélisation, compréhension ainsi qu’à la communication efficace d’information dans les réseaux dynamiques peuplant la périphérie de l’Internet. Par réseaux dynamiques, nous signifions les réseaux pouvant être modélisés par des graphes dynamiques dans lesquels noeuds et liens évoluent temporellement. Dans la première partie de la thèse, nous proposons un nouveau modèle de mobilité - STEPS - qui permet de capturer un large spectre de comportement de mobilité humains. STEPS mets en oeuvre deux principes fondamentaux de la mobilité humaine : l’attachement préférentiel à une zone de prédilection et l’attraction vers une zone de prédilection. Nous proposons une modélisation markovienne de ce modèle de mobilité. Nous montrons que ce simple modèle paramétrique est capable de capturer les caractéristiques statistiques saillantes de la mobilité humaine comme la distribution des temps d’inter-contacts et de contacts. Dans la deuxième partie, en utilisant STEPS, nous analysons les propriétés comportementales et structurelles fondamentales des réseaux opportunistes. Nous redéfinissons dans le contexte des réseaux dynamiques la notion de structure petit monde et montrons comment une telle structure peut émerger. En particulier, nous montrons que les noeuds fortement dynamiques peuvent jouer le rôle de ponts entre les composants déconnectés, aident à réduire significativement la longueur du chemin caractéristique du réseau et contribuent à l’émergence du phénomène petit-monde dans les réseaux dynamiques. Nous proposons une façon de modéliser ce phénomène sous STEPS. À partir d’un réseau dynamique régulier dans lequel les noeuds limitent leur mobilité à leurs zones préférentielles respectives. Nous recablons ce réseau en injectant progressivement des noeuds nomades se déplaçant entre plusieurs zones. Nous montrons que le pourcentage de tels nœuds nomades est de 10%, le réseau possède une structure petit monde avec un fort taux de clusterisation et un faible longueur du chemin caractéristique. La troisième contribution de cette thèse porte sur l’étude de l’impact du désordre et de l’irrégularité des contacts sur la capacité de communication d’un réseau dynamique. Nous analysons le degré de désordre de réseaux opportunistes réels et montrons que si exploité correctement, celui-ci peut améliorer significativement les performances du routage. Nous introduisons ensuite un modèle permettant de capturer le niveau de désordre d’un réseau dynamique. Nous proposons deux algorithmes simples et efficaces qui exploitent la structure temporelle d’un réseau dynamique pour délivrer les messages avec un bon compromis entre l’usage des ressources et les performances. Les résultats de simulations et analytiques montrent que ce type d’algorithme est plus performant que les approches classiques. Nous mettons également en évidence aussi la structure de réseau pour laquelle ce type d’algorithme atteint ses performances optimum. Basé sur ce résultat théorique nous proposons un nouveau protocole de routage efficace pour les réseaux opportunistes centré sur le contenu. Dans ce protocole, les noeuds maintiennent, via leurs contacts opportunistes, une fonction d’utilité qui résume leur proximité spatio-temporelle par rapport aux autres noeuds. En conséquence, router dans un tel contexte se résume à suivre le gradient de plus grande pente conduisant vers le noeud destination. Cette propriété induit un algorithme de routage simple et efficace qui peut être utilisé aussi bien dans un contexte d’adressage IP que de réseau centré sur les contenus. Les résultats de simulation montrent que ce protocole superforme les protocoles de routage classiques déjà définis pour les réseaux opportunistes. La dernière contribution de cette thèse consiste à mettre en évidence une application potentielle des réseaux dynamiques dans le contexte du « mobile cloud computing ». / This thesis contributes to the modeling, understanding and efficient communication in dynamic networks populating the periphery of the Internet. By dynamic networks, we refer to networks that can be modeled by dynamic graphs in which nodes and links change temporally. In the first part of the thesis, we propose a new mobility model - STEPS - which captures a wide spectrum of human mobility behavior. STEPS implements two fundamental principles of human mobility: preferential attachment and attractor. We show that this simple parametric model is able to capture the salient statistical properties of human mobility such as the distribution of inter-contact/contact time. In the second part, using STEPS, we analyze the fundamental behavioral and structural properties of opportunistic networks. We redefine in the context of dynamic networks the concept of small world structure and show how such a structure can emerge. In particular, we show that highly dynamic nodes can play the role of bridges between disconnected components, helping to significantly reduce the length of network path and contribute to the emergence of small-world phenomenon in dynamic networks. We propose a way to model this phenomenon in STEPS. From a regular dynamic network in which nodes limit their mobility to their respective preferential areas. We rewire this network by gradually injecting highly nomadic nodes moving between different areas. We show that when the ratio of such nomadic nodes is around 10%, the network has small world structure with a high degree of clustering and a low characteristic path length. The third contribution of this thesis is the study of the impact of disorder and contact irregularity on the communication capacity of a dynamic network. We analyze the degree of disorder of real opportunistic networks and show that if used correctly, it can significantly improve routing performances. We then introduce a model to capture the degree of disorder in a dynamic network. We propose two simple and efficient algorithms that exploit the temporal structure of a dynamic network to deliver messages with a good tradeoff between resource usage and performance. The simulation and analytical results show that this type of algorithm is more efficient than conventional approaches. We also highlight also the network structure for which this type of algorithm achieves its optimum performance. Based on this theoretical result, we propose a new efficient routing protocol for content centric opportunistic networks. In this protocol, nodes maintain, through their opportunistic contacts, an utility function that summarizes their spatio-temporal proximity to other nodes. As a result, routing in this context consists in following the steepest slopes of the gradient field leading to the destination node. This property leads to a simple and effective algorithm routing that can be used both in the context of IP networks and content centric networks. The simulation results show that this protocol outperforms traditional routing protocols already defined for opportunistic networks. The last contribution of this thesis is to highlight the potential application of dynamic networks in the context of "mobile cloud computing." Using the particle optimization techniques, we show that mobility can significantly increase the processing capacity of dynamic networks. In addition, we show that the dynamic structure of the network has a strong impact on its processing capacity.

Chaque année en Europe, 1.300.000 accidents de la route ont comme conséquence 1.700.000 blessés. Le coût financier d’accidents de la route est évalué à 160 milliards d’euros (approximativement le même coût aux Etats-Unis). VANET (Vehicular Ad-hoc NETwork) est une des technologies clés qui peut permettre de réduire d’une façon significative le nombre d’accidents de la route (e.g. message d’urgence signalant la présence d’un obstacle ou d’un véhicule en cas de brouillard). En plus de l’amélioration de la sécurité et du confort des conducteurs et des passagers, VANET peut contribuer à beaucoup d’applications potentielles telles que la prévision et la détection d’embouteillages, la gestion d’infrastructure de système de transport urbain (e.g. système de transport intelligent multimodal) etc. Dans cette thèse, je présenterai un système embarqué dédié à la communication inter-véhicule particulièrement pour les applications sécuritaires de passagers et de conducteurs. Nos efforts de recherche et de développement sont centrés sur deux principaux objectifs : minimiser le temps de latence intra-noeud et le délai de communication inter-véhicule en prenant en compte le changement dynamique du VANET. De ce fait pour atteindre ces objectifs, des nouvelles approches (e.g. inter-couche ‘Cross-layering’) ont été explorées pour respecter les contraintes de ressource (QoS, mémoire, CPU et énergie de la communication inter-véhicule) d’un système embarqué à faible coût. Le système de communication embarqué proposé comporte deux composants logiciels principaux : un protocole de communication dénommé CIVIC (Communication Inter Véhicule Intelligente et Coopérative) et un système d’exploitation temps réel appelé HEROS (Hybrid Event-driven and Real-time multitasking Operating System). CIVIC est un protocole de communication géographique à faible consommation énergétique et à faible temps de latence (délai de communication). HEROS gère contextuellement l’ensemble du système (matériel et logiciel) en minimisant le temps de latence et la consommation des ressources (CPU et mémoire). En outre, le protocole de communication CIVIC est équipé d’un système de localisation LCD-GPS (Low Cost Differential GPS). Pour tester et valider les différentes techniques et théories, la plateforme matérielle LiveNode (LImos Versatile Embedded wireless sensor NODE) a été utilisée. En effet, la plateforme LiveNode permet de développer et de prototyper rapidement des applications dans différents domaines. Le protocole de communication CIVIC est basé sur la technique de ‘broadcast’ à un saut ; de ce fait il est indépendant de la spécificité du réseau. Pour les expérimentations, seule la norme d’IEEE 802.15.4 (ZigBee) a été choisie comme médium d’accès sans fil. Il est à noter que le médium d’accès sans fil ZigBee a été adopté comme le médium standard pour les réseaux de capteurs sans fil (RCSFs) et le standard 6LoWPAN ; car il est peu coûteux et peu gourmand en énergie. Bien que le protocole de communication à l’origine soit conçu pour répondre aux exigences de VANET, ses domaines d’application ne sont pas limités à VANET. Par exemple il a été utilisé dans différents projets tels que MOBI+ (système de transport urbain intelligent) et NeT-ADDED (projet européen FP6 : agriculture de précision). Les VANETs et les RCSFs sont les réseaux fortement dynamiques, mais les causes de changement topologique de réseau sont différentes : dans le réseau VANET, il est dû à la mobilité des véhicules, et dans le RCSF, il est dû aux pannes des noeuds sans fil. Il est à noter que le VANET et le RCSF sont généralement considérés comme un sous-ensemble du réseau MANET (réseau ad-hoc mobile). Cependant, ils sont réellement tout à fait différents du MANET classique, et leurs similitudes et différences seront expliquées en détail dans la thèse. La contribution principale de mes travaux est le protocole CIVIC, qui échange des messages en basant sur l’information géographique des noeuds (position). (...) / Each year in Europe, 1,300,000 vehicle accidents result in 1,700,000 personal injuries. The financial cost of vehicle accidents is evaluated at 160 billion Euros (approximately the same cost in the USA). VANET (Vehicular Ad-Hoc NETwork) is a key technology that can enable hazard alarming applications to reduce the accident number. In addition to improve the safety for drivers and passengers, VANET can contribute to many potential applications such as detecting and predicting traffic jams, auto-optimizing the traffic flow, and helping disabled passengers to access public transports.This thesis will present an embedded communication system dedicated to VANET especially for the safety-related applications. Our design mainly tries to achieve two requirements: as one can imagine, the embedded communication system for VANET requires extra effort to deal with the highly dynamic network topology caused by moving vehicles, thus to shorten the intra-node system latency and inter-node network delay is essential requirement for such embedded communication system. Besides, a fundamental requirement for any practical embedded system is resource-awareness. Although the embedded communication system on vehicles may gain better hardware supports, the characteristics of embedded hardware still have to cope with resource constraints in terms of QoS, memory, CPU and energy. The embedded communication system involves two major software components: a routing protocol called CIVIC (Communication Inter Véhicule Intelligente et Coopérative) and an embedded operating system called HEROS (Hybrid Event-driven and Real-time multitasking Operating System). The former is a quick reaction and low resource consumption geographic protocol for inter-vehicle message transmissions; and the latter controls the whole system and assures intra-node resource awareness. In addition, the system can use a localization software solution called LCD-GPS (Low Cost Differential GPS) to improve the accuracy of locations. The hardware platform is LiveNode (LImos Versatile Embedded wireless sensor NODE), which is a versatile wireless sensor node enabling to implement rapidly a prototype for different application domains. The communication system is based on the one-hop broadcast, thus it does not have a strict limitation on network specification. For the experiments only, the IEEE 802.15.4 standard is chosen as the underlying wireless access medium. The standard is well known as a low-power consumption standard requiring low-cost devices. Notice that the IEEE 802.15.4 standard is also the wireless access medium of 6LoWPAN. Although the embedded communication system is originally designed to meet the requirements of VANET, but its application domains are not limited to VANET. For example, another network which can use the embedded communication system is WSN (Wireless Sensor Network). CIVIC was used to implement different real-world projects such MOBI+ (intelligent urban transportation system) and EU-FP6 NeT-ADDED (precision agriculture). Both VANET and WSN are highly dynamic networks, but the causes of changing network topology are different: the former is because of the high-mobility feature of vehicles, and the latter is because of the fault of wireless sensors. Note that, although VANET and WSN are both commonly considered as the subset of MANET (Mobile Ad-hoc NETwork), they are actually quite different from the classical MANET, and the similarities and differences will be further explained in the thesis. The major contribution of my works relates to the CIVIC protocol, which routes messages based on the geographic information. The related works of the thesis will focus on the geographic routing techniques, problems and solutions, but other related techniques will also be addressed. Note that, although some related projects were investigated but their implementation and experiment aspects were not detailed. (...)

Les problèmes majeurs de la génération automatique du dessin des masques des circuits intégrés sont la dépendance vis-à-vis des règles de dessin et le dimensionnement correct des transistors. Les méthodes traditionnelles, telles que l'utilisation de cellules pré-caractérisées, manquent de flexibilité, car les portes des bibliothèques (en nombre limité) sont dessinées et dimensionnées (independarnment de l'application) pour une technologie donnée. Les méthodes de synthèse automatique du dessin des masques ont pour but de surmonter ces problèmes. Les techniques les plus couramment utilisées sont le "gate-matrix" et le "linear-matrix". L'indépendance vis-à-vis des règles de dessin est obtenue en utilisant la technique de description symbolique (dessin sous une grille unitaire), et les dimensions des transistors sont définies par le concepteur ou par un outil de dimensionnement. Nous proposons une méthode et un prototype logiciel pour la synthèse automatique des masques, en utilisant le style "linear-matrix multi-bander". La description d'entree du générateur est un fichier format SPICE (au niveau transistor), ce qui permet d'avoir un nombre très élevé de cellules, en particulier les portes complexes (A01), et ainsi avoir une meilleure optimisation lors de la phase d'assignation technologique. Les macro-cellules générées doivent être assemblées afin de réaliser un circuit complet. Deux contraintes supplémentaires sont ainsi imposées au générateur: malléabilité de la forme et position des broches d'entrées/sorties sur la périphérie de la macro-cellule. Les macro-cellules sont assemblées en utilisant un environnement de conception industriel. Les contributions de ce mémoire de doctorat sont d'une part le développement d'un générateur de macro-cellules flexible ayant les caracteristiques d'indépendance aux règles de dessin et d'intégration dans un environnement de macro-cellules, et d'autre part l'étude detailée des paramètres qui déterminent la surface occupée, les performances électriques et la puissance dissipée des macro-cellules générées automatiquement. / The main problems of the automatic layout synthesis are the design rules dependence and the transistor sizing. The traditional layout synthesis methods, like standard-cells, are not flexible, since the cells in the libraries are designed and sized for a specific technology. In this way, the designer must change his library at each technology improvement. The automatic layout synthesis methods overcomes these problems (design rules dependence and transistor sizing). Examples of layout styles are gate-matrix and linear-matrix. The technology independence is achieved by symbolic description (layout under an unitary grid), and the transistor sizes are defined by the designer or by a sizing tool. From these two constraints, we develop an automatic layout synthesis tool, using a linear-matrix multi-row layout style. The input description for our tool is a Spice file. This descriptions allows to define a greater number of cells (mainly AOIs gates), resulting a technology mapping with less constraints. The generated macro-cells must be assembled in order to construct a complete circuit. Two additional constraints are then imposed to the generator : variable aspect ratio and placement of the inputs/outputs pins in the macro-cell border. The macro-cells are assembled by an industrial CAD environment. The main contributions of this thesis are the development of a macro-cell generator (with the characteristics of technology independence and easy integration in a macro-cell environment) and the analysis of the parameters playing a role in the area, delay and power consumption.

Les problèmes majeurs de la génération automatique du dessin des masques des circuits intégrés sont la dépendance vis-à-vis des règles de dessin et le dimensionnement correct des transistors. Les méthodes traditionnelles, telles que l'utilisation de cellules pré-caractérisées, manquent de flexibilité, car les portes des bibliothèques (en nombre limité) sont dessinées et dimensionnées (independarnment de l'application) pour une technologie donnée. Les méthodes de synthèse automatique du dessin des masques ont pour but de surmonter ces problèmes. Les techniques les plus couramment utilisées sont le "gate-matrix" et le "linear-matrix". L'indépendance vis-à-vis des règles de dessin est obtenue en utilisant la technique de description symbolique (dessin sous une grille unitaire), et les dimensions des transistors sont définies par le concepteur ou par un outil de dimensionnement. Nous proposons une méthode et un prototype logiciel pour la synthèse automatique des masques, en utilisant le style "linear-matrix multi-bander". La description d'entree du générateur est un fichier format SPICE (au niveau transistor), ce qui permet d'avoir un nombre très élevé de cellules, en particulier les portes complexes (A01), et ainsi avoir une meilleure optimisation lors de la phase d'assignation technologique. Les macro-cellules générées doivent être assemblées afin de réaliser un circuit complet. Deux contraintes supplémentaires sont ainsi imposées au générateur: malléabilité de la forme et position des broches d'entrées/sorties sur la périphérie de la macro-cellule. Les macro-cellules sont assemblées en utilisant un environnement de conception industriel. Les contributions de ce mémoire de doctorat sont d'une part le développement d'un générateur de macro-cellules flexible ayant les caracteristiques d'indépendance aux règles de dessin et d'intégration dans un environnement de macro-cellules, et d'autre part l'étude detailée des paramètres qui déterminent la surface occupée, les performances électriques et la puissance dissipée des macro-cellules générées automatiquement. / The main problems of the automatic layout synthesis are the design rules dependence and the transistor sizing. The traditional layout synthesis methods, like standard-cells, are not flexible, since the cells in the libraries are designed and sized for a specific technology. In this way, the designer must change his library at each technology improvement. The automatic layout synthesis methods overcomes these problems (design rules dependence and transistor sizing). Examples of layout styles are gate-matrix and linear-matrix. The technology independence is achieved by symbolic description (layout under an unitary grid), and the transistor sizes are defined by the designer or by a sizing tool. From these two constraints, we develop an automatic layout synthesis tool, using a linear-matrix multi-row layout style. The input description for our tool is a Spice file. This descriptions allows to define a greater number of cells (mainly AOIs gates), resulting a technology mapping with less constraints. The generated macro-cells must be assembled in order to construct a complete circuit. Two additional constraints are then imposed to the generator : variable aspect ratio and placement of the inputs/outputs pins in the macro-cell border. The macro-cells are assembled by an industrial CAD environment. The main contributions of this thesis are the development of a macro-cell generator (with the characteristics of technology independence and easy integration in a macro-cell environment) and the analysis of the parameters playing a role in the area, delay and power consumption.

Cette thèse a pour but d'évaluer la performance théorique des approches coopératives pour la fiabilisation des transmissions dans les réseaux autour du corps humain. Ces réseaux sont formés d'un nombre limité de capteurs communicants disposés sur et dans le corps. Les techniques de coopération dans les réseaux de cette taille sont extrêmement dépendantes de l'information disponible quand à la qualité des canaux de communication au moment de la transmission. Sous une hypothèse de connaissance de la valeur moyenne à moyen et long terme de l'affaiblissement de ces canaux, nous dérivons une approximation du taux d'erreur paquet de bout en bout pour des techniques de relayage. Nous présentons également, pour certains de ces modèles, une allocation de puissance asymptotiquement optimale, fournissant un gain sur une large plage des puissances d'émission. En supposant ensuite que les noeuds ont une connaissance parfaite de l'état du réseau, nous étudions la capacité de Shannon sur des canaux à relais, et des canaux comprenant deux émetteurs coopérant entre eux. Pour ces deux modèles, nous montrons que lorsque l'on cherche à optimiser la répartition de puissance totale disponible à l'émission, l'étude se réduit à celle d'un modèle de canal équivalent simplifiant grandement l'analyse de la capacité et fournissant des solutions analytiques aux problèmes d'allocation de ressources. Nous présentons enfin une plate-forme de mesures pour les réseaux autour du corps humain, permettant de relever de manière quasi-simultanée l'intégralité des affaiblissements des liens entre les nœuds du réseau. Cette plateforme nous permet de traiter de la stabilité de ces liens et de la validité de l'hypothèse de réciprocité. Nous évaluons également la corrélation spatiale de l'affaiblissement des liens et nous montrons en particulier que celle-ci varie fortement au cours du mouvement, mais de façon suffisamment lente pour être estimée au fil de l'eau. / This thesis aimed at studying the theoretical performance bounds of cooperative techniques in Body Area Networks (BAN). These networks are sensor networks, with a small number of nodes located on and inside the human body. Cooperative techniques are extremely dependent on the channel side information available at the time of transmission. Considering statistical information about the channel fading and the short-term mean of the signal, we derive an asymptotic approximation of the packet error rate under the so-called block fading channel model. Using this approximation, we can express in closed-form asymptotically optimal power allocation among transmitting nodesfor various models of relay channels. Under a complete channel knowledge hypothesis, we then study the Shannon capacity of small-scale cooperative networks, namely relay channels and cooperative multiple access channels. We show that for these networks, when you aim at optimizing the global power allocation of the whole network, the problem is equivalent to a simpler problem on an equivalent channel model. Using this equivalence, we are able to derive a number of closed-form resource allocation for relay channels and cooperative multiple access channels. In the last part of the manuscript, we present a measurement platform for BAN where the quality of every link in the network is gathered in a quasi-simultaneous manner. This platform allows us to discuss results and assess hypotheses on the stability and reciprocity of BAN links. We also evaluate the variation of the spatial correlation of the links during a walking scenario, and show that although the correlation matrix may vary a lot during the movement, it does so sufficiently slowly to be estimated on-line by an adequate protocole, paving the way to more precise resource allocation techniques and relay selection protocols.

Cette thèse comporte des résultats théoriques et pratiques sur deux métaheuristiques, la Recherche Dispersée et la Recherche Voisinage variable (RVV), ainsi que sur des Matheuristiques. Au niveau théorique, la contribution principale de cette thèse est la proposition d’un algorithme de recherche dispersée avec l’arrondi directionnel convergent pour les programmes en nombres entiers mixtes (0-1 MIP), avec une preuve de cette convergence en un nombre fini d’itérations. En se basant sur cet algorithme convergeant, deux implémentations et plusieurs heuristiques sont proposées et testées sur des instances de 0-1 MIP. Les versions testées reposent sur des implémentations non optimisées pour mettre en évidence la puissance des approches dans une forme simplifiée. Nos résultats démontrent l’efficacité de ces approches initiales, ce qui les rend attractives lorsque des solutions de très haute qualité sont recherchées avec un investissement approprié en termes d’effort de calcul. Cette thèse inclut également quelques nouvelles variantes de la métaheuristique Recherche Voisinage Variable telles qu’une recherche voisinage variable deux niveaux, une recherche voisinage variable imbriquée, une descente voisinage variable cyclique et une heuristique de plongée voisinage variable. En outre, plusieurs implémentations efficaces de ces algorithmes basés sur la recherche voisinage variable ont été appliquées avec succès à des problèmes NP-Difficiles apparaissant en transport, logistique, production d’énergie, ordonnancement, et segmentation. Les heuristiques proposées se sont avérées être les nouvelles heuristiques de référence sur tous les problèmes considérés. La dernière contribution de cette thèse repose sur la proposition de plusieurs matheuristiques pour résoudre le problème de Conception de Réseau Multi-flots avec Coût fixe (CRMC). Les performances de ces matheuristiques ont été évaluées sur un ensemble d’instances de référence du CRMC. Les résultats obtenus démontrent la compétitivité des approches proposées par rapport aux approches existantes de la littérature. / This thesis consists of results obtained studying Scatter Search, Variable Neighbourhood Search (VNS), and Matheuristics in both theoretical and practical context. Regarding theoretical results, one of the main contribution of this thesis is a convergent scatter search with directional rounding algorithm for 0-1 Mixed Integer Programs (MIP) with the proof of its finite convergence. Besides this, a convergent scatter search algorithm is accompanied by two variants of its implementation. Additionally, several scatter search based heuristics, stemming from a convergent scatter search algorithm have been proposed and tested on some instances of 0-1 MIP. The versions of the methods tested are first stage implementations to establish the power of the methods in a simplified form. Our findings demonstrate the efficacy of these first stage methods, which makes them attractive for use in situations where very high quality solutions are sought with an efficient investment of computational effort.This thesis also includes new variants of Variable Neighborhood Search metaheuristic such as a two-level variable neighborhood search, a nested variable neighborhood search, a cyclic variable neighborhood descent and a variable neighborhood diving. Additionally, several efficient implementation of those variable neighborhood search algorithms have been successfully applied for solving NP-Hard problems appearing in transportation, logistics, power generation, scheduling and clustering. On all tested problems, the proposed VNS heuristics turned out to be a new state-of-the art heuristics. The last contribution of this thesis consists of proposing several matheuristics for solving Fixed-Charge Multicommodity Network Design (MCND) problem. The performances of these matheuristics have been disclosed on benchmark instances for MCND. The obtained results demonstrate the competitiveness of the proposed matheuristics with other existing approaches in the literature.