Dissertations / Theses on the topic 'Réseaux tolérants aux perturbations'

Cette thèse s´intéresse à la conception et l´évaluation des protocoles de routage et d´accès au canal pour les réseaux sans fils. La première partie de la thèse focalise principalement sur l´évaluation de protocoles de routage pour les réseaux tolérants aux perturbations quand ces réseaux incluent des relais fixes, appelées boîtes. Dans un premier temps, nous montrons que les instants successifs de rencontre entre une boîte et un noeud mobile qui se déplace selon un modèle de mobilité aléatoire sont bien approximés par un processus de Poisson. Nous donnons une formule explicite approchée pour l´intensité de ce processus qui dépend notamment de la densité de probabilité spatiale du modèle de mobilité considérée ainsi que celle des boîtes. Dans un deuxième temps, nous étudions l´impact d´ajouter des boîtes sur les performances de deux protocoles de routage classiques, le protocole épidémique et le protocole de routage à deux sauts. Nous développons des expressions explicites pour quantifier la distribution et la moyenne du délai de livraison d´un paquet, ainsi que le nombre des copies générées lors de cette transmission. Ensuite, nous proposons cinq stratégies qui s´appuient sur la présence des boîtes pour réaliser le routage des copies. Par ailleurs, nous introduisons une plateforme basée sur un modèle markovien qui permet de calculer et de comparer analytiquement les diverses métriques de performance pour ces cinq stratégies. Dans la deuxième partie de la thèse, nous intéressons à l´algorithme de backoff du standard IEEE 802.11. Nous proposons une extension de cet algorithme dont l´objectif est d´améliorer ses performances dans le cas où le réseau possède un grand nombre d´utilisateurs.

L'objectif de cette thèse est de proposer des stratégies d'optimisation protocolaire et architecturale adaptées aux cas d'usages pour lesquels les communications entre les noeuds d'un réseau sont susceptibles d'être fortement perturbées par des conditions de déploiement défavorables, sans que les mécanismes standards de réparation de panne prévus pour ce réseau puissent convenablement traiter et résorber les effets de ces perturbations. Il peut s'agir de divers contextes applicatifs, comme celui des réseaux de communication d'urgence, mis en oeuvre suite à la survenue de désastres ou plus généralement d'incidents non planifiés capables de laisser les réseaux d'une zone affectée partiellement ou totalement endommagés. Les perturbations mentionnées peuvent être de différente nature : elles peuvent par exemple être provoquées par un dimensionnement du réseau défavorable (ex. nombre de noeuds trop faible, surface de dispersion des nœuds trop importante, portée des interfaces de communication sans fil trop réduites, . . . en regard des autres paramètres de déploiement considérés). Elles peuvent aussi être provoquées par des causes externes, comme par exemple la présence non anticipée d'obstacles ou la survenue de sources d'interférences extérieures au réseau considéré. De manière générale, on constate qu'en présence de telles perturbations, un réseau non conçu pour spécifiquement fonctionner dans de telles conditions peut voir ses performances et la qualité d'expérience de ses utilisateurs baisser significativement. Dans ce contexte, nous cherchons à comparer la perception que nous avons traditionnellement de la mobilité dans les réseaux sans fil, en particulier dans les réseaux ad hoc mobiles et les réseaux tolérants aux perturbations et aux délais, avec les principes de la mobilité contrôlée, selon lesquels un noeud est capable de participer directement à la détermination de sa trajectoire et à la réalisation de son déplacement. Nous définissons un système de forces virtuelles, comprenant diverses composantes répulsives, attractives, de frottement et d'alignement, pouvant être appliquées aux noeuds d'un réseau. Nous expliquons ensuite comment concrètement utiliser ces forces virtuelles dans un déploiement réseau, et nous spécifions une solution protocolaire utilisée selon diverses variations, que nous mettons en oeuvre à travers des stratégies de mobilité contrôlée adaptées à différents environnements réseau.Nous prenons tout d'abord appui sur un scénario applicatif relatif à la lutte contre la progression d'une espèce invasive, le frelon asiatique, et décrivons un déploiement sur un réseau ad hoc sans fil reposant sur un ensemble de véhicules mobiles aériens qui exécutent une première stratégie de mobilité contrôlée. Nous cherchons à identifier les plages de valeurs pour les paramètres-clés de notre protocole à base de forces virtuelles aboutissant aux meilleures performances du réseau constitué par l'ensemble des noeuds considérés. Par la suite, nous introduisons également un scénario de déploiement de réseau temporaire de secours en situation de désastre, toujours de type ad hoc sans fil, puis nous présentons une analyse de la performance d'une seconde stratégie de mobilité contrôlée adaptée à cet environnement. Nous montrons en particulier comment cette stratégie se comporte lorsque le nombre de noeuds du réseau augmente. Nous abordons ensuite le contexte des réseaux utilisés en conditions défavorables et des mécanismes de tolérance aux perturbations. Nous cherchons ici à concevoir un troisième type de stratégie de mobilité contrôlée utilisant conjointement des mécanismes de tolérance aux perturbations et aux délais et les principes de mobilité contrôlée afin d'augmenter significativement les performances du réseau<br>Throughout this thesis, we seek to propose and design optimized strategies that are adapted to a widespread class of use cases in which communications between network nodes may be disrupted by adverse deployment conditions, assuming that standard fault repair mechanisms are unable to address and mitigate the effects created by these disruptions. Such use cases include the applicative context of emergency communication networks, which are often met in the wake of disasters, or more generally after the occurrence of any unexpected event which may leave the existing networks of an affected area partially or even totally damaged. The aforementioned disruptions can be of different nature: they may result from a detrimental network dimensioning (e.g. low number of network nodes, excessive node scattering surface, insufficient radio communication range, . . . with respect to the other considered deployment parameter values). They may also stem from external causes, e.g. the unexpected presence of obstacles on the area of interest, or the existence of extrinsic interference sources that may disturb the considered network. In general, it can be observed that given such disruptions, a network which is not inherently designed to operate in these conditions is likely to under-perform and, as a result, to offer a significantly decreased quality of experience to its users. In this regard, we seek to compare our perception of the traditional concept of mobility as seen in common infrastructure, ad hoc or disruption- and delay-tolerant wireless networks with the principles of controlled mobility, according to which a network node may directly control its own movement and affect its trajectory accordingly. More precisely, we investigate the means to define a virtual force system which encompasses multiple repulsive, attractive, friction and alignment forces, all of which may be applied to network nodes in order to enforce this principle of controlled mobility.We then explain how virtual forces can concretely be implemented and used in a realistic network deployment, and we specify a protocol solution and its variations, which we enforce within controlled mobility strategies with the prospect that those prove best suited to the considered network environments. We first take as an applicative background a scenario aiming to fight the spread of an invasive species, the Asian hornet, and we outline a practical deployment relying on a wireless ad hoc network formed with unmanned aerial nodes which all enforce our first proposed controlled mobility strategy. We then seek to identify the best value intervals for the key parameters of our virtual force-based protocol, anticipating that configured with these values, the deployed network will yield its best performance in terms of delays and packet delivery. Later, we introduce a scenario related to the deployment of an emergency communication network, still on the basis of wireless ad hoc network principles. We then present an analysis of how a second proposed controlled mobility strategy performs in this applicative environment. In particular, we show how this strategy behaves when the number of network nodes increases. At that point, we address the context of networks deployed in challenging conditions, and of the use of disruption- and delaytolerant mechanisms. We aim here at designing a third type of strategy that jointly uses disruption- and delay-tolerant mechanisms as well as controlled mobility principles, in order to significantly increase the overall network performance. We then investigate and explain how this strategy allows transmitting a fraction of the user traffic with short delays, when an end-to-end route is available along a communication chain, while the other fraction of the traffic is delivered with longer delays, with the support of delay-tolerant routing mechanisms

Cette thèse aborde différents aspects de la conception d'un réseau de télécommunications. Un tel réseau utilise des technologies hétérogènes : liens antennes-satellites, radio, fibres optiques ou bien encore réseaux embarqués dans un satellite. Les problématiques varient en fonction de la partie du réseau considérée, du type de requêtes et de l'objectif. Le cas des requêtes de type paquets est abordé dans le cadre des réseaux en forme de grille, mais le thème principal est le routage de requêtes de type connections (unicast et multicast). Les objectifs considérés sont : la conception d'un réseau embarqué dans un satellite de télécommunication, de taille minimum et tolérant des pannes de composants; le dimensionnement des liens d'un réseau afin qu'il supporte des pannes corrélées ou qu'il offre une bonne qualité de service, ou s'il autorise des connections {\em multicast}; le dimensionnement de la taille des buffers d'un réseau d'accés radio; et l'optimisation de l'utilisation des ressources d'un réseau dynamique orienté connections. Dans tous ces cas la problématique du routage de connections est centrale. Mon approche consiste à utiliser la complémentarité de techniques algorithmique et d'optimisation combinatoire ainsi que d'outils issus de la théorie des graphes tels la pathwidth et des notions reliées -process number, jeux de captures et treewidth-, différents types de coloration -impropre et pondérée, proportionnelle, directed star colouring-, les graphes d'expansion et des techniques de partitions telle la quasi partition.

L'accès aux informations contenues en différents sites d'un réseau, nécessite la mise en place d'algorithmes de routage distribués tolérants aux fautes. Nous proposons plusieurs algorithmes permettant, la gestion des fautes transitoires, des fautes définitives, ou la gestion des fautes imputables à l'exécution de l'algorithme. Nous présentons d'abord, un algorithme d'auto-stabilisation automatique. Contrairement aux algorithmes déjà proposés, notre protocole permet, la transformation en un algorithme auto-stabilisant, de tous les algorithmes distribués écrits pour un modèle à passage de messages, et, grâce à ses performances, la possibilité d'implémentation d'un compilateur auto-stabilisant. Nous prouvons l'efficacité de notre solution en auto-stabilisant l'algorithme netchange. Dans l'objectif de proposer un algorithme de routage gérant plus efficacement les fautes, nous présentons un algorithme de calcul de tables de routage FTSS, capable, non seulement, de gérer les fautes transitoires, mais aussi, de résister aux fautes définitives. Les protocoles précédents résistent aux fautes provoquées par des causes extérieures. Certaines fautes peuvent être causées par l'exécution d'un algorithme : saturation des liens de communication, surcharge des sites. . . Nous proposons un algorithme de collecte des informations utilisant un mot circulant à déplacement aléatoire, ainsi que quatre schémas de gestion des informations collectées. Selon chacun des schémas proposés, nous présentons un algorithme de calcul de tables de routage équilibrant la charge des messages sur le réseau. Enfin, grâce à l'étude des performances des marchés aléatoires, nous donnons des perspectives de recherche permettant : soit l'évaluation des performances d'algorithmes probabilistes en fonction de la topologie, soit l'évaluation des capacités de réseaux en fonction des performances de marches aléatoires.

Les réseaux tolérants aux retards (DTN) ont été conçus pour fournir un moyen de communication durable entre terminaux mobiles dans les régions dépourvues d’infrastructure cellulaire. Dans de tels réseaux, l’ensemble des voisins de chaque nœud change au fil du temps en raison de la mobilité des nœuds, ce qui entraîne une connectivité intermittente et des routes instables dans le réseau. Nous analysons la performance d’un système d’incitation pour les DTN à deux sauts dans lequel une source en arriéré offre une récompense fixe aux relais pour délivrer un message. Un seul message à la fois est proposé par la source. Pour un message donné, seul le premier relais à le délivrer reçoit la récompense correspondant à ce message, induisant ainsi une compétition entre les relais. Les relais cherchent à maximiser la récompense attendue pour chaque message alors que l’objectif de la source est de satisfaire une contrainte donnée sur la probabilité de livraison du message. Nous considérons deux réglages différents : l’un dans lequel la source indique aux relais pendant combien de temps un message est en circulation, et l’autre dans lequel la source ne donne pas cette information. Dans le premier paramètre, nous montrons que la politique optimale d’un relais est de type seuil : il accepte un message jusqu’à un premier seuil et le conserve jusqu’à ce qu’il atteigne la destination ou le deuxième seuil. Les formules de calcul des seuils ainsi que de la probabilité de livraison des messages sont dérivées pour une source d’arriérés. Nous étudions ensuite la performance asymptotique de ce réglage dans la limite moyenne du champ. Lorsque le deuxième seuil est infini, nous donnons l’ODE du champ moyen et montrons que tous les messages ont la même probabilité de réussite. Lorsque le deuxième seuil est fini, nous ne donnons qu’une approximation ODE car dans ce cas, la dynamique n’est pas markovienne. Pour le second réglage, nous supposons que la source propose chaque message pour une période de temps fixe et qu’un relais décide d’accepter un message selon une politique randomisée lors d’une rencontre avec la source. S’il accepte le message, un relais le garde jusqu’à ce qu’il atteigne la destina- tion. Nous établissons dans quelle condition la probabilité d’acceptation des relais est strictement positive et montrons que, dans cette condition, il existe un équilibre de Nash symétrique unique, dans lequel aucun relais n’a quelque chose à gagner en changeant unilatéralement sa probabilité d’acceptation. Des expressions explicites pour la probabilité de livraison du message et le temps moyen de livraison d’un message à l’équilibre symétrique de Nash sont dérivées, ainsi qu’une expression de la valeur asymptotique de la livraison du message. Enfin, nous présentons de nombreux résultats de simulations pour com- parer les performances de la stratégie de type seuil et de la stratégie ran- domisée, afin de déterminer dans quelle condition il est rentable pour la source de donner l’information sur l’âge d’un message aux relais<br>Delay-Tolerant Networks (DTNs) were designed to provide a sustainable means of communication between mobile terminals in regions without cellular infrastructure. In such networks, the set of neighbors of every node changes over time due to the mobility of nodes, resulting in intermittent connectivity and unstable routes in the network. We analyze the performance of an incentive scheme for two-hop DTNs in which a backlogged source pro- poses a fixed reward to the relays to deliver a message. Only one message at a time is proposed by the source. For a given message, only the first relay to deliver it gets the reward corresponding to this message thereby inducing a competition between the relays. The relays seek to maximize the expected reward for each message whereas the objective of the source is to satisfy a given constraint on the probability of message delivery. We consider two different settings: one in which the source tells the relays for how long a message is in circulation, and one in which the source does not give this information. In the first setting, we show that the optimal policy of a relay is of thresh- old type: it accepts a message until a first threshold and then keeps the message until it either meets the destination or reaches the second threshold. Formulas for computing the thresholds as well as probability of message delivery are derived for a backlogged source. We then investigate the asymptotic performance of this setting in the mean field limit. When the second thresh- old in infinite, we give the mean-field ODE and show that all the messages have the same probability of successful delivery. When the second threshold is finite we only give an ODE approximation since in this case the dynamics are not Markovian. For the second setting, we assume that the source proposes each message for a fixed period of time and that a relay decides to accept a message accord- ing to a randomized policy upon encounter with the source. If it accepts the message, a relay keeps it until it reaches the destination. We establish under which condition the acceptance probability of the relays is strictly positive and show that, under this condition, there exists a unique symmetric Nash equilibrium, in which no relay has anything to gain by unilaterally changing its acceptance probability. Explicit expressions for the probability of message delivery and the mean time to deliver a message at the symmetric Nash equilibrium are derived, as well as an expression of the asymptotic value of message delivery. Finally, we present numerous simulations results to compare performances of the threshold-type strategy and the randomized strategy, in order to determine under which condition it is profitable for the source to give the information on the age of a message to the relays

Dans ce mémoire, nous nous intéressons à deux notions de coloration sous contraintes -- coloration acyclique par listes et coloration (d,1)-totale -- ainsi qu'à un problème de conception de réseaux embarqués tolérants aux pannes. Les notions de coloration acyclique par listes et de coloration (d,1)-totale sont des notions récentes (2002). Nous apportons de nouveaux résultats concernant le calcul du nombre chromatique acyclique de listes et du nombre (d,1)-total de certaines familles de graphes (graphes de degré borné, graphes de degré moyen maximum donné,. . . ) ainsi que de nouvelles perspectives de recherche. La fiabilité des réseaux embarqués dans les satellites de télécommunication, maillons essentiels dans la chaîne de la diffusion d'information, est un enjeu important. Comment concevoir des réseaux embarqués à faible coût capables de tolérer un certain nombre de pannes et de continuer à propager l'information ? Nous donnons des éléments de réponse à cette problématique posée par Alcatel Space Industries en présentant des réseaux de coût minimal supportant un nombre de pannes donné.

Nous étudions dans cette thèse des problèmes d’optimisation avec applications dans les réseaux optiques. Les problèmes étudiés sont liés à la tolérance aux pannes et à l’utilisation efficace des ressources. Les résultats obtenus portent principalement sur la complexité de calcul de ces problèmes. La première partie de cette thèse est consacrée aux problèmes de trouver des chemins et des chemins disjoints. La recherche d’un chemin est essentielle dans tout type de réseaux afin d’y établir des connexions et la recherche de chemins disjoints est souvent utilisée pour garantir un certain niveau de protection contre les pannes dans les réseaux. Nous étudions ces problèmes dans des contextes différents. Nous traitons d’abord les problèmes de trouver un chemin et des chemins lien ou nœud- disjoints dans des réseaux avec nœuds asymétriques, c’est-à-dire des nœuds avec restrictions sur leur connectivité interne. Ensuite, nous considérons les réseaux avec des groupes de liens partageant un risque (SRLG) en étoile : ensembles de liens qui peuvent tomber en panne en même temps suite à un événement local. Dans ce type de réseaux, nous examinons le problème de recherche des chemins SRLG-disjoints. La deuxième partie de cette thèse est consacrée au problème de routage et d’allocation de spectre (RSA) dans les réseaux optiques élastiques (EONs). Les EONs sont proposés comme la nouvelle génération des réseaux optiques et ils visent une utilisation plus efficace et flexible des ressources optiques. Le problème RSA est central dans les EONs. Il concerne l’allocation de ressources aux requêtes sous plusieurs contraintes<br>We study in this thesis optimization problems with application in optical networks. The problems we consider are related to fault-tolerance and efficient resource allocation and the results we obtain are mainly related to the computational complexity of these problems. The first part of this thesis is devoted to finding paths and disjoint paths. Finding a path is crucial in all types of networks in order to set up connections and finding disjoint paths is a common approach used to provide some degree of protection against failures in networks. We study these problems under different settings. We first focus on finding paths and node or link-disjoint paths in networks with asymmetric nodes, which are nodes with restrictions on their internal connectivity. Afterwards, we consider networks with star Shared Risk Link Groups (SRLGs) which are groups of links that might fail simultaneously due to a localized event. In these networks, we investigate the problem of finding SRLG-disjoint paths. The second part of this thesis focuses on the problem of Routing and Spectrum Assignment (RSA) in Elastic Optical Networks (EONs). EONs are proposed as the new generation of optical networks and they aim at an efficient and flexible use of the optical resources. RSA is the key problem in EONs and it deals with allocating resources to requests under multiple constraints. We first study the static version of RSA in tree networks. Afterwards, we examine a dynamic version of RSA in which a non-disruptive spectrum defragmentation technique is used. Finally, we present in the appendix another problem that has been studied during this thesis

Parmi les évolutions majeures de l'informatique, nous distinguons l'émergence des technologies mobiles sans fil. Le développement actuel de ces technologies permet de réaliser des communications ad-hoc directes entre de nombreux types d'entités mobiles, comme des véhicules, des robots terrestres ou des drones. Dans un réseau de tels équipements, l'ensemble des liens de communication qui existe à un instant donné dépend des distances entre les entités et la topologie du réseau change continuellement lorsque les entités se déplacent. Les hypothèses habituelles sur la connexité du réseau n'ont pas leur place ici, néanmoins, une autre forme de connexité appelée connexité temporelle est souvent disponible à travers le temps et l'espace. L'objectif de cette thèse a été de développer des algorithmes pour les flottes d'appareils dans le cas des réseaux tolérant aux délais (DTN). De manière simplifiée, les réseaux tolérants aux délais sont des réseaux pour lesquels certaines parties peuvent se retrouver isolées pendant un moment sans que cela pose problème. Nous nous intéressons, en particulier, au cas où ces appareils sont organisés sous la forme de groupes, et où la notion de groupe elle même survit à ces déconnexions transitoires. Ainsi, une grande partie de la thèse s'articule autour de la notion des groupes tolérant aux délais (groupe DTN). Dans notre cas cet éloignement est limité dans le temps et nous parlons alors de "diamètre temporel borné" au sein du groupe. Le fait de borner le diamètre temporel du groupe lui permet de distinguer entre l'éloignement temporaire d'un noeud et sa perte définitive (crash ou autre)<br>Among the major developments in computer science, we distinguish the emergence of mobile wireless technologies. The current development of these technologies allows for direct ad-hoc communications between many types of mobile entities, such as vehicles, land robots or drones. In a network of such devices, the set of communication links that exists at a given instant depends upon the distances between the entities. As a result, the topology of the network changes continuously as the entities move. The common assumption on connectivity may not be relevant in this case, but another kind of connectivity called temporal connectivity is often alvailable over time and space. The goal of this thesis has been the development of algorithms for fleets of mobile devices in the case of delay-tolerant networks. In a simpler way, the delay-tolerant networks are networks where some parts can be isolated during a certain time without problems. We are interested, in particular, in the case where the devices are organised as groups, and where the notion of group itself survives to these deconnections. Hence, a big part of this thesis relates to the notion of delay-tolerant groups (DTN groups). In our case, these deconnections are limited in time and we speak of a "bounded temporal diameter" within the group. The fact of limiting the temporal diameter of the group enables it to distinguish between temporary deconnections and final loss (crash or other) of some nodes

Grâce à une réduction considérable dans les dimensions des transistors, les systèmes informatiques sont aujourd'hui capables d'intégrer un très grand nombre de cœurs de calcul en une seule puce (System-on-Chip, SoC). Faire communiquer les composants au sein d'une puce est aujourd'hui assuré par un réseau de commutation de paquet intégré, communément appelé Network-on-Chip (NoC). Cependant, le passage à des technologies de plus en plus réduites rend les circuits plus vulnérables aux fautes et aux défauts de fabrication. Le réseau sur puce peut donc se retrouver avec des routeurs ou des liens non-opérationnels, qui ne peuvent plus être utilisés pour le routage de paquets. Par conséquent, le niveau de flexibilité offert par l'algorithme de routage n'a jamais été aussi important. La première partie de cette thèse consiste à proposer une méthodologie généralisée, permettant de concevoir des algorithmes de routage hautement flexibles, combinant tolérance aux fautes et hautes performances, et ce pour n'importe quelle topologie réseau. Cette méthodologie est basée sur une nouvelle condition suffisante pour l'absence d'interblocages (deadlocks) qui, contrairement aux méthodes existantes qui imposent des restrictions importantes sur l'utilisation des buffers, s'évalue de manière dynamique en fonction de chaque paquet et ne requiert pas un partitionnement stricte des canaux virtuels (virtual channels). Il est montré que ce degré élevé de liberté dans l'utilisation des buffers a un impact positif à la fois sur les performances et sur la robustesse du NoC, sans pour autant augmenter la complexité en termes d'implémentation matérielle. La seconde partie de la thèse s'intéresse à une problématique plus spécifique, qui est celle du routage dans des topologies tri-dimensionnelles partiellement connectées, qui vont vraisemblablement être en vigueur à cause du coût important des connexions verticales, réalisées en utilisant la technologie TSV (Through-Silicon Via). Cette thèse introduit un nouvel algorithme de routage pour ce type d'architectures nommé "First-Last". Grâce à un placement original des canaux virtuels, cet algorithme est le seul capable de garantir la connectivité totale du réseau en présence d'un seul pilier de TSVs de coordonnées arbitraires, tout en ne requérant de canaux virtuels que sur deux des ports du routeur. Contrairement à d'autres algorithmes qui utilisent le même nombre total de canaux virtuels, First-Last n'impose aucune règle sur la position des piliers, ni sur les piliers à sélectionner durant l'exécution. De plus, l'algorithme proposé ayant été construit en utilisant la méthode décrite dans la première partie de la thèse, il offre une utilisation optimisée des canaux virtuels ajoutés. L'implémentation d'un nouvel algorithme de routage implique souvent des changements considérables au niveau de la microarchitecture des routeurs. L'évaluation de ces nouvelles solutions requiert donc une plateforme capable de simuler précisément l'architecture matérielle du réseau au cycle près. De plus, il est essentiel de tester les nouvelles architectures sur des tailles de réseau significativement grandes, pour s'assurer de leur scalabilité et leur applicabilité aux technologies émergentes (e.g. intégration 3D). Malheureusement, les simulateurs de réseaux sur puce existants ne sont pas capables d'effectuer des simulations sur de grands réseaux (milliers de cœurs) assez vite, et souvent, la précision des simulations doit être sacrifiée afin d'obtenir des temps de simulation raisonnables. En réponse à ce problème, la troisième et dernière partie de cette thèse est consacrée à la conception et au développement d'un modèle de simulation générique, extensible et parallélisable, exploitant la puissance des processeurs graphiques modernes (GPU). L'outil développé modélise l'architecture d'un routeur de manière très précise et peut simuler de très grands réseaux en des temps record<br>Networks-on-Chip (NoCs) have proven to be a fast and scalable replacement for buses in current and emerging many-core systems. They are today an actively researched topic and various solutions are being explored to meet the needs of emerging applications in terms of performance, quality of service, power consumption, and fault-tolerance. This thesis presents contributions in two important areas of Network-on-Chip research:- The design of ultra-flexible high-performance deadlock-free routing algorithms for any topology.- The design and implementation of parallel cycle-accurate Network-on-Chip simulators for a fast evaluation of new NoC architectures.While aggressive technology scaling has its benefits in terms of delay, area and power, it is also known to increase the vulnerability of circuits, suggesting the need for fault-tolerant designs. Fault-tolerance in NoCs is directly tied to the degree of flexibility of the routing algorithm. High routing flexibility is also required in some irregular topologies, as is the case for TSV-based 3D Network-on-Chips, wherein only a subset of the routers are connected using vertical connections. Unfortunately, routing freedom is often limited by the deadlock-avoidance method, which statically restricts the set of virtual channels that can be acquired by each packet.The first part of this thesis tackles this issue at the source and introduces a new topology-agnostic methodology for designing ultra-flexible routing algorithms for Networks-on-Chips. The theory relies on a novel low-restrictive sufficient condition of deadlock-freedom that is expressed using the local information available at each router during runtime, making it possible to verify the condition dynamically in a distributed manner.A significant gain in both performance and fault-tolerance when using our methodology compared to the existing static channel partitioning methods is reported. Moreover, hardware synthesis results show that the newly introduced mechanisms have a negligible impact on the overall router area.In the second part, a novel routing algorithm for vertically-partially-connected 3D Networks-on-Chips called First-Last is constructed using the previously presented methodology.Thanks to a unique distribution of virtual channels, our algorithm is the only one capable of guaranteeing full connectivity in the presence of one TSV pillar in an arbitrary position, while requiring a low number of extra buffers (1 extra VC in the East and North directions). This makes First-Last a highly appealing cost-effective alternative to the state-of-the-art Elevator-First algorithm.Finally, the third and last part of this work presents the first detailed and modular parallel NoC simulator design targeting Graphics Processing Units (GPUs). First, a flexible task decomposition approach, specifically geared towards high parallelization is proposed. Our approach makes it easy to adapt the granularity of parallelism to match the capabilities of the host GPU. Second, all the GPU-specific implementation issues are addressed and several optimizations are proposed. Our design is evaluated through a reference implementation, which is tested on an NVidia GTX980Ti graphics card and shown to speed up 4K-node NoC simulations by almost 280x

L'essor considérable de la technologie CMOS a permis l'accroissement de la densité d'intégration selon la loi de Moore. Cependant, la poursuite de cette évolution est en voie de ralentissement dû aux contraintes physiques et économiques. Le défi devient alors de pouvoir utiliser un maximum de circuits tout en tolérant des défauts physiques présents en leur sein. Les circuits reconfigurables de type FPGA (Field Programmable Gate Array) connaissent un succès croissant car leurs performances et leurs capacités d'intégrer des applications très complexes ont directement bénéficié de l'évolution technologique. Le but de cette thèse est de proposer une architecture de FPGA contenant des mécanismes permettant de tolérer plus de 20% d'éléments défectueux après fabrication. La première partie du manuscrit étudie les différentes architectures de FPGA (matricielles et arborescentes) ainsi que les différentes techniques de contournement des défauts. Dans la seconde partie de cette thèse, nous présentons l'architecture cible matricielle (matrice de grappes ou groupes). Cette architecture combine les avantages des architectures matricielles (sa généricité) et arborescentes (réduction du taux d'utilisation de l'interconnexion. La troisième partie de cette thèse présente le développement d'une méthode d'identification des blocs les plus critiques contenus dans le FPGA ainsi que l'impact des différentes techniques de contournement retenues et proposées sur l'architecture et sur la criticité des blocs de base du FPGA. Pour finir, nous définissons les performances des différentes techniques de contournements en termes de tolérance aux défauts, de performances temporelles et de surface<br>The increasing integration density according to Moore’s law is being slowed due to economic and physical limits. However, this technological evolution involves an higher number of physical defects after manufacturing circuit. As yield goes down, one of the future challenges is to find a way to use a maximum of fabricated circuits while tolerating physical defects spread all over the chip. Fiel Programmable Gate Array (FPGA) are integrated circuits that contain logic blocks and reconfigurable interconnect. Their ability to integrate more complex applications, their flexibility and good performance make FPGAs the perfect target architecture. The aim of this thesis is to propose an FPGA architecture containing mechanisms to tolerate more than 20% of defective resources after manufacture. The first part of the manuscript studies the different FPGA architectures (mesh and tree) and different defects bypass techniques. In the second part of this thesis, we present the target architecture called Mesh of Clusters (MoC). This architecture combines the advantages of mesh architectures (genericity) and tree (reduction of the interconnect). The third contribution of this thesis is the development of a method to identify the most critical blocks in the FPGA and the impact of all bypass techniques on the architecture and on the criticality. Finally, we define the performance of all bypass techniques in terms of defect tolerance, timing and area overhead. Finally, thanks to these local redundancy techniques, we are able to tolerate more than 20% of defect on the FPGA architecture. In addition, the designer can fix his own metric in terms of area, timing and defect tolerance

Dans les systèmes répartis asynchrones, l'horloge logique et le vecteur d'horloges sont deux outils fondamentaux pour gérer la communication et le partage de données entre les entités constitutives de ces systèmes. L'objectif de cette thèse est d'exploiter ces outils avec une perspective d'implantation. Dans une première partie, nous nous concentrons sur la communication de données et contribuons au domaine de la diffusion uniforme à ordre total. Nous proposons le protocole des trains : des jetons (appelés trains) circulent en parallèle entre les processus participants répartis sur un anneau virtuel. Chaque train est équipé d'une horloge logique utilisée pour retrouver les train(s) perdu(s) en cas de défaillance de processus. Nous prouvons que le protocole des trains est un protocole de diffusion uniforme à ordre total. Puis, nous créons une nouvelle métrique : le rendement en termes de débit. Cette métrique nous permet de montrer que le protocole des trains a un rendement supérieur au meilleur, en termes de débit, des protocoles présentés dans la littérature. Par ailleurs, cette métrique fournit une limite théorique du débit maximum atteignable en implantant un protocole de diffusion donné. Il est ainsi possible d'évaluer la qualité d'une implantation de protocole. Les performances en termes de débit du protocole des trains, notamment pour les messages de petites tailles, en font un candidat remarquable pour le partage de données entre coeurs d'un même processeur. De plus, sa sobriété en termes de surcoût réseau en font un candidat privilégié pour la réplication de données entre serveurs dans le cloud. Une partie de ces travaux a été implantée dans un système de contrôle-commande et de supervision déployé sur plusieurs dizaines de sites industriels. Dans une seconde partie, nous nous concentrons sur le partage de données et contribuons au domaine de la RFID. Nous proposons une mémoire répartie partagée basée sur des étiquettes RFID. Cette mémoire permet de s'affranchir d'un réseau informatique global. Pour ce faire, elle s'appuie sur des vecteurs d'horloges et exploite le réseau formé par les utilisateurs mobiles de l'application répartie. Ainsi, ces derniers peuvent lire le contenu d'étiquettes RFID distantes. Notre mémoire répartie partagée à base de RFID apporte une alternative aux trois architectures à base de RFID disponibles dans la littérature. Notre mémoire répartie partagée a été implantée dans un jeu pervasif qui a été expérimenté par un millier de personnes.

Les ressources cellulaires sont précieuses et doivent être préservées dès que possible. Dans cette thèse, nous abordons le problème de la dissémination de contenus dans un réseau cellulaire surchargé. La première partie présente SCoD (Scheduled Content Delivery), une stratégie de dissémination purement cellulaire qui exploite la mobilité des utilisateurs ainsi que leur tolérance aux délais afin d’effectuer des transmissions différées. SCoD attend que les utilisateurs se rassemblent autour d’un minimum de points d’accès afin que le nombre total de transmissions soit réduit. Pour déclencher des transmissions, SCoD repose sur différentes fonctions de décision qui déclenchent aux instants opportuns une transmission en multicast. La deuxième partie de cette thèse traite également le problème d’économie de ressources cellulaires, mais en l’attaquant sous un autre angle. Nous exploitons des communications D2D que nous associons au multicast pour réduire la charge sur l’infrastructure. Nous analysons les avantages des communications opportunistes dans le contexte d’un service de diffusion de contenus basé sur les abonnements des utilisateurs. Nous présentons nos résultats pour deux cas de figure. Tout d’abord, nous illustrons le bénéfice des communications D2D dans le cadre d’un processus de diffusion, où le coût d’une transmission opportuniste est négligeable par rapport à celui d’une transmission cellulaire. Nous considérons ensuite le cas où les utilisateurs doivent être indemnisés pour leur participation au processus de diffusion, et où il y a donc un compromis à trouver. Nous fournissons des lignes directrices dans ce sens et nous montrons la variation d’un tel compromis en fonction de plusieurs paramètres du réseau<br>Cellular resources are valuable and must be saved whenever possible. In this thesis, we address the problem of content dissemination within an overloaded cellular network. Firstly, we propose SCoD (Scheduled Content Delivery), a purely cellular dissemination strategy that exploits the mobility of users and their delay tolerance in order to postpone transmissions. SCoD waits for users to gather around a minimum number of access points so that the total number of transmissions is reduced. To trigger transmissions, SCoD relies on different decision functions which launch, if necessary, a multicast transmission. The second part of this thesis deals with the same problem of saving cellular resources, but from another angle. We use D2D (Device-to-Device) communications with multicast to mitigate the traffic load on the infrastructure. We study the benefits of opportunistic communications in the context of a content distribution service based on user subscriptions. We present our results in two ways. First, we illustrate the benefits of D2D communications in a content dissemination process where the cost of opportunistic transmission is negligible compared to that of cellular transmission. Then, we consider the case where users must be compensated for their participation in the dissemination process. Therefore, there is a tradeoff to be found, we thus provide guidelines in this direction and show the variation of such a tradeoff as a function of several network parameters

Dans cette thèse, nous présentons plusieurs contributions pour le routage dans les réseaux tolérants aux délais (DTN). D'abord, nous démontrons, à l'aide d'une analyse de traces réelles, la présence d'hétérogénéité dans les interactions entre les noeuds et que celle-ci peut être prise en compte pour proposer le routage. Deuxièmement, nous proposons l'utilisation d'un formalisme générique basé sur un espace virtuel euclidien, appelé MobySpace, construit à partir d'informations sur les habitudes de mobilité des noeuds. Nous démontrons, avec le rejeux de traces de mobilité réelles, que ce formalisme peut s'appliquer au routage DTN et qu'il permet de créer des stratégies performantes en terme de taux de livraison et de coût de communication. Enfin, nous étudions une architecture de distribution de contenu en environnement urbain à l'aide de bornes courte portée Bluetooth. Nous étudions plusieurs stratégies de distribution en rejouant des traces collectées lors d'une expérience inédite.

Les lipides des microalgues et les glucides de cyanobactéries peuvent être transformés en biodiesel et en bioéthanol, respectivement. L'amélioration de la production de ces molécules doit prendre en compte les entrées périodiques (principalement la lumière) forçant le réseau métabolique de ces organismes photosynthétiques. Il est donc nécessaire de tenir compte de la dynamique du réseau métabolique en réduisant sa dimension pour assurer la maniabilité mathématique. Le but de ce travail est de concevoir une approche originale pour réduire les réseaux métaboliques dynamiques tout en conservant la dynamique de base. Cette méthode est basée sur une séparation en échelles de temps. Pour une classe de modèles de réseaux métaboliques décrits par des ODE, la dynamique des systèmes réduits est calculée à l'aide du théorème de Tikhonov pour les systèmes singulièrement perturbés. Cette approximation quasi-stationnaire coïncide avec la dynamique du réseau d'origine, avec une erreur bornée. L'approche est d'abord développée pour les systèmes de réaction pouvant être linéarisés autour d'un point de travail et forcés par des entrées continues. Ensuite, une généralisation de cette méthode est donnée pour les réseaux à réactions rapides de cinétiques de Michaelis-Menten et tout type de cinétiques lentes, prenant également en compte un nombre fini d'entrées continues externes. La méthode de réduction met en évidence une relation entre la grandeur de la concentration des métabolites et la gamme des vitesses de réaction : les métabolites consommés par les réactions rapides ont une concentration inférieure d'un ordre de grandeur à celle des métabolites consommés à faible vitesse. Cette propriété est satisfaite pour les métabolites à dynamique rapide ne se trouvant pas dans un piège de flux, concept introduit dans ce travail. Le système réduit peut être calibré avec des données expérimentales à l'aide d'une procédure d'identification dédiée basée sur la minimisation. L'approche est illustrée par un réseau métabolique de microalgues autotrophes, comprenant le métabolisme central et représentant la dynamique des glucides et des lipides. Cette approche permet de bien ajuster les données expérimentales de Lacour et al. (2012) avec la microalgue Tisochrysis lutea. Enfin, un schéma visant à optimiser la production de molécules cibles est proposé en utilisant le système réduit<br>Lipids from microalgae and carbohydrates from cyanobacteria can be transformed into biodiesel and bioethanol, respectively. Enhancing the production of these molecules must account for the periodic inputs (mainly light) forcing the metabolic network of these photosynthetic organisms. It is therefore necessary to account for the dynamics of the metabolic network, while reducing its dimension to ensure mathematical tractability. The aim of this work is to design an original approach to reduce dynamic metabolic networks while keeping the core dynamics. This method is based on time-scale separation. For a class of metabolic network models described by ODE, the dynamics of the reduced systems are computed using the theorem of Tikhonov for singularly perturbed systems. This Quasi Steady State Approximation accurately coincides with the original network dynamics, with a bounded error. The approach is first developed for reaction systems that can be linearized around a working point and that are forced by external continuous inputs. Then, a generalization of this method is given for networks with fast reactions of Michaelis-Menten kinetics and any type of slow kinetics, also considering a finite number of external continuous inputs. The reduction method highlights a relation between the concentration magnitude of the metabolites and the range of the reaction rates: the metabolites that are consumed by fast reactions have concentration one order of magnitude lower than metabolites consumed at slow rates. This property is satisfied for metabolites with fast dynamics that are not in a flux trap, a concept introduced in this work. The reduced system can be calibrated with experimental data using a dedicated identification procedure based on minimization. The approach is illustrated with an autotrophic microalgae metabolic network, including the core metabolism and representing the carbohydrates and lipids dynamics. The approach efficiently fits the experimental data from Lacour et al. (2012) with the microalgae Tisochrysis lutea. Finally, a scheme to optimize the production of target molecules is proposed using the reduced system

Le travail présenté dans ce mémoire porte sur l’étude de la susceptibilité conduite des circuits intégrés. La première partie du travail concerne la mise en place de deux bancs de mesure basés notamment sur les techniques de caractérisation usuelles adoptées par les standards d’immunité. Dans un premier temps, le document propose un nouveau système d’injection qui constitue une solution alternative et originale aux systèmes d’injections classiques recommandés par la norme IEC 62132-4 connue également sous l’appellation courante DPI (méthode d’injection directe de puissance). Par la suite, le document présente une nouvelle technique d’injection pour caractériser la susceptibilité des circuits intégrés vis-à-vis des décharges électrostatiques. La deuxième partie du travail consiste à établir un modèle de susceptibilité facilement exploitable et qui permet de reproduire fidèlement les mesures. Ce modèle a été construit à partir d’une approche mathématique basée sur les réseaux de neurones. L’expression mathématique résultante de la simulation du réseau de neurone exprime la susceptibilité du circuit et elle est facilement intégrable dans des logiciels de simulation électrique de type ADS ou Pspice pour alimenter les plateformes de simulation<br>The aim of this work is the characterization and modelling of integrated circuits susceptibility to conducted electromagnetic disturbances. The work has been carried out into main parts: the first part dealt with the re-use of immunity standards in order to characterize the integrated circuits susceptibility to continuous wave or electrostatic discharge disturbances. In this part, we present an alternative solution for typical injection setups usually recommended by the IEC 62132-4 standard. This solution aims to couple a radiofrequency disturbance to a DC or a low frequency signal. Also in this part, we introduce a new methodology for better characterizing the immunity of complex digital circuits to electrostatic discharge. The second part discussed a new methodology for modelling the susceptibility of integrated circuits to continuous wave disturbance such as a sinewave by using a neural network approach. The model is extracted as a mathematical expression and can be implemented in software tools such as ADS or Pspice

Avec le développement des techniques d'accès telles que le xDSL ou le FTTH, la plupart des opérateurs de télécommunications proposent de nouveaux services à très haut débit, tels que l'Internet, la téléphonie ou la télévision sur IP. En prolongement du réseau d'accès, l'utilisation de systèmes à courants porteurs domestiques permet d'accéder à l'ensemble de ces services au niveau de chaque prise de l'habitation. Cependant, le réseau électrique n'est pas adapté pour la transmission d'un signal numérique et les autres dispositifs électriques connectés risquent de perturber la communication. Ce travail de thèse consiste à analyser le fonctionnement des systèmes à courants porteurs face à ces perturbations et propose plusieurs solutions d'optimisation complémentaires. D'une part, nous nous sommes intéressés à la détection et la mitigation des perturbations impulsives, en exposant des techniques qui ont permis d'améliorer les performances et la qualité de service des systèmes. D'autre part, nous développons des algorithmes de diminution du bruit introduit par les convertisseurs analogiques/numériques, ce qui permet de résoudre de fortes contraintes d'implémentation. Enfin, l'étude s'attache à définir une meilleure gestion du spectre de puissance, afin d'augmenter les débits et la qualité de service tout en respectant les contraintes de la réglementation<br>With the emergence of broadband network technologies like ADSL or FTTH, most telecommunication service providers offer new high data rate services, such as broadband Internet, voice over IP and IP television. The use of indoor powerline systems allows the user to have access to each of these services via any socket in the house. However, the electrical network is not designed for the transmission of digital signals. Moreover, other electrical devices may generate some interference degrading the communication link. This Ph. D. Analyses the powerline systems performance in the presence of these limitations and suggests several optimization solutions according to different complementary axes. Firstly, we study the detection and mitigation of impulsive noise, in order to improve the system performance in the presence of physical disruption. Secondly, we develop algorithms liable to reduce the analog to digital converter noise which can solve implementation limitations. Finally, the study explores a better power spectrum, management, in order to increase data rates while respecting regulation constraints

Que ce soit dans l’automobile avec des contraintes thermiques ou dans l’aérospatial et lenucléaire soumis à des rayonnements ionisants, l’environnement entraîne l’apparition de fautesdans les systèmes électroniques. Ces fautes peuvent être transitoires ou permanentes et vontinduire des résultats erronés inacceptables dans certains contextes applicatifs. L’utilisation decomposants dits « rad-hard » est parfois compromise par leurs coûts élevés ou les difficultésd’approvisionnement liés aux règles d’exportation.Cette thèse propose une approche conjointe matérielle et logicielle indépendante de la technologied’intégration permettant d’utiliser des composants numériques programmables dans desenvironnements susceptibles de générer des fautes. Notre proposition comporte la définitiond’une Architecture Reconfigurable à Gros Grains (CGRA) capable d’exécuter des codes applicatifscomplets mais aussi l’ensemble des mécanismes matériels et logiciels permettant de rendrecette architecture tolérante aux fautes. Ce résultat est obtenu par l’association de redondance etde reconfiguration dynamique du CGRA en s’appuyant sur une banque de configurations généréepar une chaîne de programmation complète. Cette chaîne outillée repose sur un flot permettantde porter un code sous forme de Control and Data Flow Graph (CDFG) sur l’architecture enobtenant un grand nombre de configurations différentes et qui permet d’exploiter au mieux lepotentiel de l’architecture.Les travaux, qui ont été validés aux travers d’expériences sur des applications du domaine dutraitement du signal et de l’image, ont fait l’objet de publications en conférences internationaleset de dépôts de brevets<br>Whether in automotive with heat stress or in aerospace and nuclear field subjected to cosmic,neutron and gamma radiation, the environment can lead to the development of faults in electronicsystems. These faults, which can be transient or permanent, will lead to erroneous results thatare unacceptable in some application contexts. The use of so-called rad-hard components issometimes compromised due to their high costs and supply problems associated with exportrules.This thesis proposes a joint hardware and software approach independent of integrationtechnology for using digital programmable devices in environments that generate faults. Ourapproach includes the definition of a Coarse Grained Reconfigurable Architecture (CGRA) ableto execute entire application code but also all the hardware and software mechanisms to make ittolerant to transient and permanent faults. This is achieved by the combination of redundancyand dynamic reconfiguration of the CGRA based on a library of configurations generated by acomplete conception flow. This implemented flow relies on a flow to map a code represented as aControl and Data Flow Graph (CDFG) on the CGRA architecture by obtaining directly a largenumber of different configurations and allows to exploit the full potential of architecture.This work, which has been validated through experiments with applications in the field ofsignal and image processing, has been the subject of two publications in international conferencesand of two patents

Ce memoire presente des travaux et resultats concernant la caracterisation, la formalisation et la modelisation des interactions entre composants materiels et logiciels de systemes tolerants aux fautes, aussi bien sur le plan theorique que sur le plan pratique. Chaque composant materiel ou logiciel est modelise par un reseau de petri stochastique generalise appele reseau de composant. Les interactions entre ces composants sont modelisees par des reseaux de petri stochastiques generalises appeles reseaux de dependances, construits a partir de regles de constructions rigoureuses definies de facon formelle. Une methode efficace et rapide de construction des modeles de plusieurs architectures d'un systeme tolerant aux fautes est ensuite proposee. Cette methode basee sur la reutilisation consiste a representer chaque architecture par un modele de haut-niveau, appele modele-bloc, compose de blocs de composants et de blocs de dependances. Les blocs sont generiques et reutilisables d'une architecture a l'autre. Chaque bloc est ensuite remplace par un reseau de composant ou de dependance construit d'apres le formalisme defini lors de la formalisation des interactions. Cette methode de modelisation est appliquee a l'evaluation comparative de la surete de fonctionnement de dix-sept architectures possibles pour le systeme de controle de la navigation aerienne. Ces evaluations permettent de choisir une architecture optimale pour la disponibilite de la future version de ce systeme

Cette thèse propose une série de techniques dont l'objectif est l'amélioration de la couverture et de l'organisation des réseaux mobiles sans fil dans le contexte des Réseaux de Sécurité Publique (RSPs). Ces derniers sont des réseaux établis par les autorités pour d'une part, avertir la population d'une catastrophe imminente, et d'autre part pour coordonner les équipes de secours durant les phases de crise et de normalisation suite à une catastrophe. Une catastrophe peut être définie comme un événement extrême causant des dégâts extrêmes ou une perte profonde pour les populations affectées. Les RSPs ont le rôle fondamental d'assurer la communication et la coordination au cours des opérations d'urgence. Les contributions de cette thèse se concentrent principalement dans les phases d'alerte et de gestion de la crise. La solution proposée dans cette thèse pour aider durant la phase d'alerte est basée sur les réseaux opportunistes et utilise les moyens de communication disponibles sur les personnes sur place, et qui bientôt seront également disponibles dans les véhicules, pour pallier le problème de l'absence de couverture de réseau suite aux dégâts causés. Cette technique, que nous appelons Virtual Access Points (VAP), crée un 'cache' coopératif et distribué entre les nœuds mobiles dans la zone touchée par la catastrophe. Les problèmes que nous adressons relatifs à la phase de gestion de crise sont ceux du contrôle de la topologie et d'admission au réseau. Nous fournissons des solutions pour fournir des structures stables et fiables, qui sont essentiels à la coordination des équipes de secours pendant les situations les plus difficiles et défavorables.

Depuis une vingtaine d’années, les grands réseaux électriques se trouvent obligés de fonctionner à pleine puissance et souvent aux limites de la stabilité. L’amélioration de la stabilité aux petites perturbations, en particulier l’amortissement des oscillations interrégionales, est donc devenue un objectif prioritaire. Les interactions entre les générateurs de différentes régions et les régulateurs utilisés nécessitent une optimisation globale de leurs performances : c’est le meilleur moyen pour assurer le comportement optimal de l’ensemble. L’objectif de notre travail est d’assurer un amortissement maximum, aussi bien des modes interrégionaux que des modes locaux, à l’aide des stabilisateurs de puissance (PSS) généralement utilisés pour l’amortissement des modes électromécaniques locaux. Pour ce faire, nous avons développé une méthode d’optimisation globale basée sur les algorithmes génétiques et une fonction multiobjectif utilisant les paramètres de stabilité relative et de stabilité absolue déterminés à partir de l’analyse des valeurs propres du système. Nous avons analysé l’influence de l’augmentation progressive du nombre de variables à optimiser simultanément (paramètres des PSSs, emplacement et nombre de ces derniers). La méthode que nous proposons permet un réglage optimal des PSSs avec la meilleure localisation possible et un nombre réduit de PSSs. Nous avons proposé en outre une nouvelle méthode d’optimisation utilisant des contraintes dynamiques adaptatives de l’espace de recherche afin d’améliorer les performances et la rapidité de convergence de cet algorithme. Les performances de ces méthodes d’optimisation ont été évaluées sur le réseau multimachines interconnecté New England/New York par analyse des valeurs propres du système et simulations temporelles tant sur le modèle linéarisé que sur le modèle nonlinéaire originel<br>Over the past twenty years, electric utilities are being operated their power systems at full power and often closer to their stability limits. The improvement of small signal stability, in particular the damping of inter-area oscillations, has become therefore a priority. Interactions between the generators of different regions and the used regulators require a global optimization of their performances: this is the best way to ensure the whole optimal behaviour. Our work objective is to ensure a maximum damping of the inter-area modes as well as of the local modes, using power system stabilizer (PSS) that is habitually used in the damping of electromechanical local modes. So, we have developed a global optimization method based on genetic algorithms and a multi-objective function using relative and absolute stability parameters that are obtained of the system eigenvalue analysis. We have analyzed the influence of the gradual increase of the variable number that to be optimized simultaneously (PSS parameters, their location and number). The proposed method allows an optimal setting of PSSs with the best possible location and a reduced number. We have also proposed a new optimization method using dynamic adaptive space research. This can improve the optimization performance and the convergence acceleration of this algorithm. The performance of these optimizations methods has been evaluated on the New England/ New York multi-machine network via system eigenvalue analysis, linear and nonlinear time domain simulations

Dans cette thèse, nous exploitons la mobilité des véhicules pour créer un médium de communication ad hoc utile pour déployer des services connectés. Notre objectif est de tirer partie des trajets quotidiens effectués en voiture ou en transport en commun pour surmonter les limitations des réseaux de données tels que l’Internet. Dans une première partie, nous profitons de la bande passante que génèrent les déplacements de véhicules équipés de capacités de stockage pour délester en masse l’Internet d’une partie de son trafic. Les données sont détournées vers des équipements de stockage appelés points de délestage installés aux abords de zones où les véhicules s’arrêtent habituellement, permettant ainsi de relayer les données entre véhicules jusqu'au point de délestage suivant où elles pourront éventuellement être déchargées. Nous proposons ensuite deux extensions étendant le concept de point de délestage selon deux directions dans le contexte de services reposant toujours la mobilité des véhicules. Dans la première extension, nous exploitons les capacités de stockage des points de délestage pour concevoir un service de stockage et partage de fichiers offert aux passagers de véhicules. Dans la seconde extension, nous dématérialisons les points de délestage en zones géographiques pré-définies où un grand nombre de véhicules se rencontrent suffisamment longtemps pour transférer de grandes quantités de données. L’évaluation des performances des différents travaux menés au cours de cette thèse montrent que la mobilité inhérente aux entités du quotidien permet la fourniture de services innovants avec une dépendance limitée vis-à-vis des réseaux de données traditionnels<br>In this thesis, we exploit the daily mobility of vehicles to create an alternative transmission medium. Our objective is to draw on the many vehicular trips taken by cars or public transports to overcome the limitations of conventional data networks such as the Internet. In the first part, we take advantage of the bandwidth resulting from the mobility of vehicles equipped with storage capabilities to offload large amounts of delay-tolerant traffic from the Internet. Data is transloaded to data storage devices we refer to as offloading spots, located where vehicles stop often and long enough to transfer large amounts of data. Those devices act as data relays, i.e., they store data it is until loaded on and carried by a vehicle to the next offloading spot where it can be dropped off for later pick-up and delivery by another vehicle. We further extend the concept of offloading spots according to two directions in the context of vehicular cloud services. In the first extension, we exploit the storage capabilities of the offloading spots to design a cloud-like storage and sharing system for vehicle passengers. In the second extension, we dematerialize the offloading spots into pre-defined areas with high densities of vehicles that meet long enough to transfer large amounts of data. The performance evaluation of the various works conducted in this thesis shows that everyday mobility of entities surrounding us enables innovative services with limited reliance on conventional data networks

Depuis une vingtaine d'années, les grands réseaux électriques se trouvent obligés de fonctionner à pleine puissance et souvent aux limites de la stabilité. L'amélioration de la stabilité aux petites perturbations, en particulier l'amortissement des oscillations interrégionales, est donc devenue un objectif prioritaire. Les interactions entre les générateurs de différentes régions et les régulateurs utilisés nécessitent une optimisation globale de leurs performances : c'est le meilleur moyen pour assurer le comportement optimal de l'ensemble. L'objectif de ce travail est d'assurer un amortissement maximum, aussi bien des modes interrégionaux que des modes locaux, à l'aide des stabilisateurs de puissance (PSS) généralement utilisés pour l'amortissement des modes électromécaniques locaux. Pour ce faire, nous avons développé une méthode d'optimisation globale basée sur les algorithmes génétiques et une fonction multiobjectif déterminée à partir de l'analyse des valeurs propres du système. Nous avons analysé l'influence de l'augmentation progressive du nombre de variables à optimiser simultanément (paramètres, emplacement et nombre des PSSs). La méthode que nous proposons permet un réglage optimal des PSSs avec le meilleur emplacement possible et un nombre réduit de PSSs. Nous avons proposé en outre une nouvelle méthode d'optimisation utilisant des contraintes dynamiques adaptatives de l'espace de recherche afin d'améliorer les performances et la rapidité de convergence de cet algorithme. Les performances de ces méthodes d'optimisation ont été évaluées sur le réseau multimachines interconnecté New England / New York par analyse des valeurs propres du modèle linéaire du système et simulations temporelles du modèle non-linéaire originel.

La réponse aux situations de crise routière hivernale est gérée en France au niveau zonal par les Centres Régionaux d'Information et de Coordination Routière (CRICR). Le pilotage de ces crises est réalisé à une échelle multi départementale et fait intervenir de multiples parties prenantes (gestionnaires routiers, préfectures, forces de l'ordre...). La coordination de ces acteurs hétérogènes apparaît donc comme indispensable pour assurer une réponse efficace à la situation de crise. C'est le rôle de la cellule de crise, de garantir cette coordination afin de permettre une bonne exécution de la réponse. C'est surtout son rôle d'assurer la qualité de la réponse quelque soient les aléas et les perturbations rencontrées. Malheureusement, force est de constater que les acteurs en présence ne disposent pas des outils adéquats pour atteindre ces objectifs. Les présents travaux de thèse ambitionnent d'améliorer cette situation par la mise en place d'un système d'information de médiation agile. Celui-ci repose sur la constitution d'une base de connaissances (ontologie), alimentée à partir de la collecte de données issues de systèmes d'information hétérogènes, pour permettre la définition tactique d'une solution adaptée de réponse allant jusqu'à la formalisation des processus collaboratifs à mettre en œuvre. La réalisation de la collaboration s'assoit alors sur une orchestration informatique de ces processus. Dans notre proposition, la détection "à chaud" de problèmes et les recommandations d'adaptation générées soutiennent le pilotage « réactif » de la réponse dans un environnement complexe et particulièrement instable. Cette fonctionnalité est complétée par un système capable de détecter a priori les problèmes, en établissant une projection de la situation courante (crise et réponse) à partir des éléments dont la cellule de crise dispose. Cette projection donne lieu à une évaluation de la situation future et contribue à la conception d'une nouvelle réponse. Ces mécanismes permettent un pilotage « anticipatif » de la gestion de crise. Les résultats de cette thèse ont été principalement développés et validés dans le cadre du projet PREDIT SIM-PeTra sur l'amélioration de la coordination dans la gestion des crises par la mise en place d'un Système d'Information de Médiation dans le cadre de Perturbations dans les Transports<br>In France, the response to winter road emergencies are managed by Regional Centres for Information and Road Coordination (CRICR). The management of these crises is performed at a multi county level and involves multiple stakeholders (road operator, local representative of national authority, police…). Therefore, the coordination of such heterogeneous actors must be assumed by the crisis cell to ensure an effective response. The crisis cell has also to provide a good response facing hazards and disturbances encountered. Unfortunately, it is clear that the involved actors do not have a relevant and adequate set of ICT tools to achieve these goals. This thesis aims at improving this situation by setting up an agile mediation information system. This is based on the creation of a knowledge base (structured as an ontology), fed from the gathering of data from all the available heterogeneous information systems, to enable the tactical definition of a suitable response. The final goal is to formalize this response as collaborative processes to implement and to orchestrate through a computer system. In our proposal, detecting "hot" issues (such as disruptions or unexpected events) and making recommended adaptation support the "reactive" control of the response in a complex and highly unstable environment. This feature is completed by a system able to detect a priori problems, by establishing a projection of the current situation (crisis response), based on the collected forecasts owned by the crisis manager (traffic, weather, etc.). This projection leads to an assessment of the future situation and contributes to the design of a new response. This mechanism allows a " proactive " oversight of crisis management. The results of this PhD have mainly been developed and validated in the SIM Petra project (funded by PREDIT) regarding the establishment of a Mediation Information System to improve the coordination of the management of crisis concerning disruptions in transport

Le transport est devenu fondamental dans les villes pour le bon fonctionnement de l'économie et le bien-être de la population urbaine. Depuis plusieurs années, le transport est confronté à de nombreux problèmes tels que l'embouteillage, le taux élevé d'accidents, la vie malsaine due à la fumée et à la poussière, la pollution atmosphérique due aux émissions de carbone, etc. Pour faire face à ces problèmes, les recherches intègrent les technologies numériques au transport terrestre, connu sous le nom de système de transport intelligent (ITS). Les ITS peuvent détecter, analyser, collecter, contrôler et communiquer différentes données. Cette thèse étudie et propose un nouveau protocole pour les applications de collecte de données dans un environnement urbain. Nous faisons trois contributions principales. Tout d'abord, nous proposons un nouveau protocole dénommé le protocole "Internet of Bikes" IoB-DTN qui applique le paradigme DTN (Réseau tolérant aux délais) aux applications de l'Internet des objets (IoT) exécutant une application de collecte de données sur un système de partage de vélo urbain basé sur un réseau de capteurs. Le protocole est évalué sur un scénario réaliste en évaluant les politiques de gestion des buffers, le nombre de copies pulvérisé dans le réseau ainsi que le nombre des vélos utilisés. Deuxiément, une évaluation comparative des performances du protocole IoB-DTN multi-sauts avec une technologie de réseau étendu à basse consommation (LPWAN), de type LoRa/LoRaWAN est étudiée. LPWAN a été conçu pour fournir une connectivité à grande distance et rentable pour les applications IoT à faible débit: durée de vie de plusieurs années et une portée de multikilomètres pour les appareils mobiles alimentés par des batteries. Cette partie de notre travail vise à fournir aux concepteurs et aux managers de réseaux des idées sur la technologie la plus pertinente pour leurs applications urbaines pouvant fonctionner sur des systèmes de partage de vélos. Enfin, nous proposons un protocole efficace, IoB-DTN basé sur un mécanisme d’agrégation de données. Nous proposons trois variantes de IoB-DTN: IoB basé sur l'agrégation spatiale (IoB-SA), IoB basé sur l'agrégation temporelle (IoB-TA) et IoB basé sur l'agrégation spatio-temporelle (IoB-STA). Nous comparons les trois variantes avec le protocole multi-saut IoB-DTN sans agrégation et la technologie à faible puissance et longue portée, de type LoRa. Les résultats de la comparaison permettent de vérifier que les trois variantes de l’IoB-DTN basées sur l’agrégation de données améliorent plusieurs paramètres tels que le taux de livraison, la consommation d’énergie et le débit<br>Transport has become fundamental in the cities to the well functioning of the economy and the welfare of the city population. For several years, transportation faces many issues such as traffic jamming, high accidents rate, unhealthy life due to smoke and dust, air pollution as a result of carbon emission, etc. To deal with these matters, researches integrate digital technologies to ground transportation which is known as Intelligent Transport System (ITS). ITS can sense, analyze, collect, control and communicate different data. This thesis investigates and proposes a new protocol for data collection applications in an urban environment. We make three main contributions: firstly, we propose a new protocol denoted the "Internet of Bikes" IoB-DTN protocol which applies Delay/Disruption Tolerant Network (DTN) paradigm to the Internet of Things (IoT) applications running a data collection application on urban bike sharing system based sensor network. The protocol is evaluated on a realistic scenario by assessing the buffer management policies, the number of copies sprayed in the network as well as the number of bicycles used. Secondly, a comparative evaluation of the performance of the multi-hop IoB-DTN protocol with a low-power wide-area network (LPWAN) technology, LoRa/LoRaWAN type is investigated. LPWAN have been designed to provide cost-effective wide area connectivity for small throughput IoT applications: multiyear lifetime and multikilometer range for battery-operated mobile devices. This part of our work aims at providing network designers and managers insights on the most relevant technology for their urban applications that could run on bike sharing systems. Finally, we propose an efficient IoB-DTN protocol based on data aggregation mechanism. We propose three variants of IoB-DTN: IoB based on spatial aggregation (IoB-SA), IoB based on temporal aggregation (IoB-TA) and IoB based on spatio-temporal aggregation (IoB-STA). We compare the three variants with the multi-hop IoB-DTN protocol without aggregation and the low-power long-range technology, LoRa type. Comparison results verify that the three variants of IoB-DTN based on data aggregation improve several metrics such as the delivery rate, energy consumption and throughput

Le domaine des protocoles tolérants aux pannes étudie quelles tâches concurrentes sont résolubles dans différents modèles de calcul avec pannes. Des outils mathématiques basés sur la topologie combinatoire ont été développés depuis les années 1990 pour aborder ces questions. Dans ce cadre, la tâche que l’on veut résoudre, et le protocole auquel on fait appel, sont modélisés par des complexes simpliciaux chromatiques. On définit qu’un protocole résout une tâche lorsqu’il existe une certaine application simpliciale entre ces complexes.Dans cette thèse, on étudie ces méthodes géométriques du point de vue de la sémantique. Le premier objectif est de fonder cette définition abstraite de résolution d’une tâche sur une autre plus concrète, basée sur des entrelacements de traces d’exécution. On examine diverses notions de spécifications pour les objets concurrents, afin de définir un cadre général pour la résolution de tâches par des objets partagés. On montre ensuite comment extraire de ce cadre la définition topologique de résolubilité de tâches.Dans la deuxième partie de la thèse, on prouve que les complexes simpliciaux chromatiques peuvent être utilisés pour évaluer des formules de logique épistémique. Cela permet d’interpréter les preuves topologiques d’impossibilité en fonction de la quantité de connaissances à acquérir pour résoudre une tâche.Enfin, on présente quelques liens préliminaires avec la sémantique dirigée pour les programmes concurrents. On montre comment la subdivision chromatique d’un simplexe peut être retrouvée en considérant des notions combinatoires de chemins dirigés<br>The field of fault-tolerant protocols studies which concurrent tasks are solvable in various computational models where processes may crash. To answer these questions, powerful mathematical tools based on combinatorial topology have been developed since the 1990’s. In this approach, the task that we want to solve, and the protocol that we use to solve it, are both modeled using chromatic simplicial complexes. By definition, a protocol solves a task when there exists a particular simplicial map between those complexes.In this thesis we study these geometric methods from the point of view of semantics. Our first goal is to ground this abstract definition of task solvability on a more concrete one, based on interleavings of execution traces. We investigate various notions of specification for concurrent objects, in order to define a general setting for solving concurrent tasks using shared objects. We then show how the topological definition of task solvability can be derived from it.In the second part of the thesis, we show that chromatic simplicial complexes can actually be used to interpret epistemic logic formulas. This allows us to understand the topological proofs of task unsolvability in terms of the amount of knowledge that the processes should acquire in order to solve a task.Finally, we present a few preliminary links with the directed space semantics for concurrent programs. We show how chromatic subdivisions of a simplex can be recovered by considering combinatorial notions of directed paths

Durant ces dernières années, de nombreux travaux de recherches ont été menés dans le domaine des réseaux multi-sauts sans fil à contraintes (MWNs: Multihop Wireless Networks). Grâce à l'évolution de la technologie des systèmes mico-electro-méchaniques (MEMS) et, depuis peu, les nanotechnologies, les MWNs sont une solution de choix pour une variété de problèmes. Le principal avantage de ces réseaux est leur faible coût de production qui permet de développer des applications ayant un unique cycle de vie. Cependant, si le coût de fabrication des nœuds constituant ce type de réseaux est assez faible, ces nœuds sont aussi limités en capacité en termes de: rayon de transmission radio, bande passante, puissance de calcul, mémoire, énergie, etc. Ainsi, les applications qui visent l'utilisation des MWNs doivent être conçues avec une grande précaution, et plus spécialement la conception de la fonction de routage, vu que les communications radio constituent la tâche la plus consommatrice d'énergie.Le but de cette thèse est d'analyser les différents défis et contraintes qui régissent la conception d'applications utilisant les MWNs. Ces contraintes se répartissent tout le long de la pile protocolaire. On trouve au niveau application des contraintes comme: la qualité de service, la tolérance aux pannes, le modèle de livraison de données au niveau application, etc. Au niveau réseau, on peut citer les problèmes de la dynamicité de la topologie réseau, la présence de trous, la mobilité, etc. Nos contributions dans cette thèse sont centrées sur l'optimisation de la fonction de routage en considérant les besoins de l'application et les contraintes du réseau. Premièrement, nous avons proposé un protocole de routage multi-chemin "en ligne" pour les applications orientées QoS utilisant des réseaux de capteurs multimédia. Ce protocole repose sur la construction de multiples chemins durant la transmission des paquets vers leur destination, c'est-à-dire sans découverte et construction des routes préalables. En permettant des transmissions parallèles, ce protocole améliore la transmission de bout-en-bout en maximisant la bande passante du chemin agrégé et en minimisant les délais. Ainsi, il permet de répondre aux exigences des applications orientées QoS.Deuxièmement, nous avons traité le problème du routage dans les réseaux mobiles tolérants aux délais. Nous avons commencé par étudier la connectivité intermittente entre les différents et nous avons extrait un modèle pour les contacts dans le but pouvoir prédire les future contacts entre les nœuds. En se basant sur ce modèle, nous avons proposé un protocole de routage, qui met à profit la position géographique des nœuds, leurs trajectoires, et la prédiction des futurs contacts dans le but d'améliorer les décisions de routage. Le protocole proposé permet la réduction des délais de bout-en-bout tout en utilisant d'une manière efficace les ressources limitées des nœuds que ce soit en termes de mémoire (pour le stockage des messages dans les files d'attentes) ou la puissance de calcul (pour l'exécution de l'algorithme de prédiction).Finalement, nous avons proposé un mécanisme de contrôle de la topologie avec un algorithme de routage des paquets pour les applications orientés évènement et qui utilisent des réseaux de capteurs sans fil statiques. Le contrôle de la topologie est réalisé à travers l'utilisation d'un algorithme distribué pour l'ordonnancement du cycle de service (sleep/awake). Les paramètres de l'algorithme proposé peuvent être réglés et ajustés en fonction de la taille du voisinage actif désiré (le nombre moyen de voisin actifs pour chaque nœud). Le mécanisme proposé assure un compromis entre le délai pour la notification d'un événement et la consommation d'énergie globale dans le réseau<br>Great research efforts have been carried out in the field of challenged multihop wireless networks (MWNs). Thanks to the evolution of the Micro-Electro-Mechanical Systems (MEMS) technology and nanotechnologies, multihop wireless networks have been the solution of choice for a plethora of problems. The main advantage of these networks is their low manufacturing cost that permits one-time application lifecycle. However, if nodes are low-costly to produce, they are also less capable in terms of radio range, bandwidth, processing power, memory, energy, etc. Thus, applications need to be carefully designed and especially the routing task because radio communication is the most energy-consuming functionality and energy is the main issue for challenged multihop wireless networks.The aim of this thesis is to analyse the different challenges that govern the design of challenged multihop wireless networks such as applications challenges in terms of quality of service (QoS), fault-tolerance, data delivery model, etc., but also networking challenges in terms of dynamic network topology, topology voids, etc. Our contributions in this thesis focus on the optimization of routing under different application requirements and network constraints. First, we propose an online multipath routing protocol for QoS-based applications using wireless multimedia sensor networks. The proposed protocol relies on the construction of multiple paths while transmitting data packets to their destination, i.e. without prior topology discovery and path establishment. This protocol achieves parallel transmissions and enhances the end-to-end transmission by maximizing path bandwidth and minimizing the delays, and thus meets the requirements of QoS-based applications. Second, we tackle the problem of routing in mobile delay-tolerant networks by studying the intermittent connectivity of nodes and deriving a contact model in order to forecast future nodes' contacts. Based upon this contact model, we propose a routing protocol that makes use of nodes' locations, nodes' trajectories, and inter-node contact prediction in order to perform forwarding decisions. The proposed routing protocol achieves low end-to-end delays while using efficiently constrained nodes' resources in terms of memory (packet queue occupancy) and processing power (forecasting algorithm). Finally, we present a topology control mechanism along a packet forwarding algorithm for event-driven applications using stationary wireless sensor networks. Topology control is achieved by using a distributed duty-cycle scheduling algorithm. Algorithm parameters can be tuned according to the desired node's awake neighbourhood size. The proposed topology control mechanism ensures trade-off between event-reporting delay and energy consumption

Deux situations de comportement égoïste des agents dans les réseaux de communication sont considérées dans le cadre de la théorie des jeux.La première situation concerne les réseaux de communication utilisant un routage décentralisé basé sur des agents autonomes. Nous étudions les propriétés de convergence des dynamiques de meilleures réponses dans un jeu de routage sur des liens parallèles. Le jeu implique un nombre fini d'agents, chacun décidant comment son trafic est routé sur les liens de manière à minimiser son propre coût. Nous proposons l'utilisation du rayon spectral généralisé des matrices Jacobiennes de l'opérateur de meilleure réponse pour démontrer la convergence.La seconde situation apparaît dans les réseaux tolérants aux délais dont l'objectif est de permettre la communication dans des environnements où la connectivité n'est qu'intermittente et où les délais de communication peuvent être très longs. Nous proposons tout d'abord un mécanisme d'incitation basé sur une récompense pour convaincre les noeuds mobiles de relayer les messages, et analysons l'influence de l'information donnée par la source (nombre de copies du message, âge de ces copies) aux relais sur le prix à payer pour transmettre le message. Nous considérons ensuite un modèle dans lequel la source propose une récompense fixe. Les noeuds mobiles peuvent alors décider d'accepter ou non le message, et s'ils l'acceptent, peuvent ensuite à tout moment décider de l'abandonner. Nous modélisons l'interaction entre les noeuds mobiles sous la forme d'un jeu stochastique partiellement observable et analysons les politiques optimales pour les relais<br>This thesis focuses on the issues related to the selfish behavior of the agents in the communication networks. We are particularly interested in two situations in which these issues arise and we address game-theoretical framework to study them.The first situation relates to communication networks using a distributed routing based on autonomous agents. Compared to a centralized routing, this type of routing offers significant advantages in terms of scalability, ease of deployment or robustness to failures and environmental disturbances. We investigate the convergence properties of the sequential best-response dynamics in a routing game over parallel links. The game involves a finite number of routing agents each of which decides how much flow to route on each of the links with the objective of minimizing its own costs. For some particular cases (e.g., two players), the convergence of the best-response dynamics can be proved by showing that this game has a potential function. For other cases, a potential function has remained elusive. We propose the use of non-linear spectral radius of the Jacobian of the best-response dynamics as an alternative approach to proving its convergence.The second situation occurs in Delay Tolerant Networks (DTNs) that have been the subject of intensive research over the past decade. DTN has an idea to support communication in environments where connectivity is intermittent and where communication delays can be very long. We focus on game-theoretic models for DTNs. First, we propose an incentive mechanism to persuade selfish mobile nodes to participate in relaying messages, and investigate the influence of the information given by the source (number of existing copies of the message, age of these copies) to the relays on the rewards proposed. For static information polices, that is the same type of information given to all the relays, it is shown that the expected reward paid by the source is independent of the policy. However, the source can reduce the reward by dynamically adapting the type of information based on the meeting times with the relays. For the particular cases, we give some structural results of the optimal adaptive policy. Next, we consider the model where the source proposes a fixed reward. The mobile relays can decide to accept or not the packet and then to drop the packet in the future. This game can be modelled as a partially-observable stochastic game. For two relays, we have shown that the optimal policies for the relays relates to the threshold type