Novel multicast protocols in ad-hoc networks

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Un protocole de diffusion des messages dans les réseaux véhiculaires

De nos jours, la voiture est devenue le mode de transport le plus utilisé, mais malheureusement, il est accompagné d’un certain nombre de problèmes (accidents, pollution, embouteillages, etc.), qui vont aller en s’aggravant avec l’augmentation prévue du nombre de voitures particulières, malgré les efforts très importants mis en œuvre pour tenter de les réduire ; le nombre de morts sur les routes demeure très important. Les réseaux sans fil de véhicules, appelés VANET, qui consistent de plusieurs véhicules mobiles sans infrastructure préexistante pour communiquer, font actuellement l’objet d'une attention accrue de la part des constructeurs et des chercheurs, afin d’améliorer la sécurité sur les routes ou encore les aides proposées aux conducteurs. Par exemple, ils peuvent avertir d’autres automobilistes que les routes sont glissantes ou qu’un accident vient de se produire. Dans VANET, les protocoles de diffusion (broadcast) jouent un rôle très important par rapport aux messages unicast, car ils sont conçus pour transmettre des messages de sécurité importants à tous les nœuds. Ces protocoles de diffusion ne sont pas fiables et ils souffrent de plusieurs problèmes, à savoir : (1) Tempête de diffusion (broadcast storm) ; (2) Nœud caché (hidden node) ; (3) Échec de la transmission. Ces problèmes doivent être résolus afin de fournir une diffusion fiable et rapide. L’objectif de notre recherche est de résoudre certains de ces problèmes, tout en assurant le meilleur compromis entre fiabilité, délai garanti, et débit garanti (Qualité de Service : QdS). Le travail de recherche de ce mémoire a porté sur le développement d’une nouvelle technique qui peut être utilisée pour gérer le droit d’accès aux médias (protocole de gestion des émissions), la gestion de grappe (cluster) et la communication. Ce protocole intègre l'approche de gestion centralisée des grappes stables et la transmission des données. Dans cette technique, le temps est divisé en cycles, chaque cycle est partagé entre les canaux de service et de contrôle, et divisé en deux parties. La première partie s’appuie sur TDMA (Time Division Multiple Access). La deuxième partie s’appuie sur CSMA/CA (Carrier Sense Multiple Access / Collision Avoidance) pour gérer l’accès au medium. En outre, notre protocole ajuste d’une manière adaptative le temps consommé dans la diffusion des messages de sécurité, ce qui permettra une amélioration de la capacité des canaux. Il est implanté dans la couche MAC (Medium Access Control), centralisé dans les têtes de grappes (CH, cluster-head) qui s’adaptent continuellement à la dynamique des véhicules. Ainsi, l’utilisation de ce protocole centralisé nous assure une consommation efficace d’intervalles de temps pour le nombre exact de véhicules actifs, y compris les nœuds/véhicules cachés; notre protocole assure également un délai limité pour les applications de sécurité, afin d’accéder au canal de communication, et il permet aussi de réduire le surplus (overhead) à l’aide d’une propagation dirigée de diffusion.

Protocole de routage basé sur des passerelles mobiles pour un accès Internet dans les réseaux véhiculaires

La rapide progression des technologies sans fil au cours de ces dernières années a vu naître de nouveaux systèmes de communication dont les réseaux véhiculaires. Ces réseaux visent à intégrer les nouvelles technologies de l’information et de la communication dans le domaine automobile en vue d’améliorer la sécurité et le confort sur le réseau routier. Offrir un accès Internet aux véhicules et à leurs occupants peut sans doute aider à anticiper certains dangers sur la route tout en rendant plus agréables les déplacements à bord des véhicules. Le déploiement de ce service nécessite que des messages soient échangés entre les véhicules. Le routage constitue un élément crucial dans un réseau, car définissant la façon dont les différentes entités échangent des messages. Le routage dans les VANETS constitue un grand défi car ces derniers sont caractérisés par une forte mobilité entraînant une topologie très dynamique. Des protocoles ont été proposés pour étendre Internet aux réseaux véhiculaires. Toutefois, la plupart d’entre eux nécessitent un coût élevé de messages de contrôle pour l’établissement et le maintien des communications. Ceci a pour conséquence la saturation de la bande passante entrainant ainsi une baisse de performance du réseau. Nous proposons dans ce mémoire, un protocole de routage qui s’appuie sur des passerelles mobiles pour étendre Internet aux réseaux véhiculaires. Le protocole prend en compte la mobilité des véhicules et la charge du réseau pour l’établissement et le maintien des routes.

Métriques de routage dans les réseaux maillés sans fil

Ces dernières années, les technologies sans fil ont connu un essor fulgurant. Elles ont permis la mise en place de réseaux sans fil à hautes performances. Les réseaux maillées sans fil (RMSF) sont une nouvelle génération de réseaux sans fil qui offrent des débits élevés par rapport aux réseaux Wi-Fi (Wireless Fidelity) classiques et aux réseaux ad-hoc. Ils présentent de nombreux avantages telles que leur forte tolérance aux pannes, leur robustesse, leur faible coût etc. Les routeurs des RMSF peuvent disposer de plusieurs interfaces radio et chaque interface peut opérer sur plusieurs canaux distincts, c’est des RMSF multiples-radios, multiples-canaux. Ce type de réseau peut accroître de manière considérable les performances des RMSF. Cependant plusieurs problèmes subsistent et doivent être résolus notamment celui du routage. Le routage dans les RMSF demeure un défi majeur. Le but des protocoles de routage est de trouver les meilleures routes i.e. des routes qui maximisent les débits et minimisent les délais, lors de l’acheminement du trafic. La qualité des routes dans les RMSF peut être fortement affectée par les interférences, les collisions, les congestions etc. Alors les protocoles doivent être en mesure de détecter ces problèmes pour pouvoir en tenir compte lors de la sélection des routes. Plusieurs études ont été dédiées aux métriques et aux protocoles de routage dans les RMSF afin de maximiser les performances de celles ci. Mais la plupart ne prennent pas en considération toutes les contraintes telles que les interférences, le problème des stations cachées etc. Ce mémoire propose une nouvelle métrique de routage pour RMSF. Nous avons mis en place une nouvelle métrique de routage pour RMSF appelée MBP (Metric Based on Probabilities). Cette métrique est destinée aux RMSF mono-radio ou multiples-radios. Elle permet d’éviter les routes à forte ii interférence. Les résultats des simulations ont montré que MBP présente des améliorations par rapport à certaines métriques : ETT, WCETT et iAWARE qui sont connues dans le domaine.

Domain/Multi-Domain Protection and Provisioning in Optical Networks

L’évolution récente des commutateurs de sélection de longueurs d’onde (WSS -Wavelength Selective Switch) favorise le développement du multiplexeur optique d’insertionextraction reconfigurable (ROADM - Reconfigurable Optical Add/Drop Multiplexers) à plusieurs degrés sans orientation ni coloration, considéré comme un équipement fort prometteur pour les réseaux maillés du futur relativement au multiplexage en longueur d’onde (WDM -Wavelength Division Multiplexing ). Cependant, leur propriété de commutation asymétrique complique la question de l’acheminement et de l’attribution des longueur d’ondes (RWA - Routing andWavelength Assignment). Or la plupart des algorithmes de RWA existants ne tiennent pas compte de cette propriété d’asymétrie. L’interruption des services causée par des défauts d’équipements sur les chemins optiques (résultat provenant de la résolution du problème RWA) a pour conséquence la perte d’une grande quantité de données. Les recherches deviennent ainsi incontournables afin d’assurer la survie fonctionnelle des réseaux optiques, à savoir, le maintien des services, en particulier en cas de pannes d’équipement. La plupart des publications antérieures portaient particulièrement sur l’utilisation d’un système de protection permettant de garantir le reroutage du trafic en cas d’un défaut d’un lien. Cependant, la conception de la protection contre le défaut d’un lien ne s’avère pas toujours suffisante en termes de survie des réseaux WDM à partir de nombreux cas des autres types de pannes devenant courant de nos jours, tels que les bris d’équipements, les pannes de deux ou trois liens, etc. En outre, il y a des défis considérables pour protéger les grands réseaux optiques multidomaines composés de réseaux associés à un domaine simple, interconnectés par des liens interdomaines, où les détails topologiques internes d’un domaine ne sont généralement pas partagés à l’extérieur. La présente thèse a pour objectif de proposer des modèles d’optimisation de grande taille et des solutions aux problèmes mentionnés ci-dessus. Ces modèles-ci permettent de générer des solutions optimales ou quasi-optimales avec des écarts d’optimalité mathématiquement prouvée. Pour ce faire, nous avons recours à la technique de génération de colonnes afin de résoudre les problèmes inhérents à la programmation linéaire de grande envergure. Concernant la question de l’approvisionnement dans les réseaux optiques, nous proposons un nouveau modèle de programmation linéaire en nombres entiers (ILP - Integer Linear Programming) au problème RWA afin de maximiser le nombre de requêtes acceptées (GoS - Grade of Service). Le modèle résultant constitue celui de l’optimisation d’un ILP de grande taille, ce qui permet d’obtenir la solution exacte des instances RWA assez grandes, en supposant que tous les noeuds soient asymétriques et accompagnés d’une matrice de connectivité de commutation donnée. Ensuite, nous modifions le modèle et proposons une solution au problème RWA afin de trouver la meilleure matrice de commutation pour un nombre donné de ports et de connexions de commutation, tout en satisfaisant/maximisant la qualité d’écoulement du trafic GoS. Relativement à la protection des réseaux d’un domaine simple, nous proposons des solutions favorisant la protection contre les pannes multiples. En effet, nous développons la protection d’un réseau d’un domaine simple contre des pannes multiples, en utilisant les p-cycles de protection avec un chemin indépendant des pannes (FIPP - Failure Independent Path Protecting) et de la protection avec un chemin dépendant des pannes (FDPP - Failure Dependent Path-Protecting). Nous proposons ensuite une nouvelle formulation en termes de modèles de flots pour les p-cycles FDPP soumis à des pannes multiples. Le nouveau modèle soulève un problème de taille, qui a un nombre exponentiel de contraintes en raison de certaines contraintes d’élimination de sous-tour. Par conséquent, afin de résoudre efficacement ce problème, on examine : (i) une décomposition hiérarchique du problème auxiliaire dans le modèle de décomposition, (ii) des heuristiques pour gérer efficacement le grand nombre de contraintes. À propos de la protection dans les réseaux multidomaines, nous proposons des systèmes de protection contre les pannes d’un lien. Tout d’abord, un modèle d’optimisation est proposé pour un système de protection centralisée, en supposant que la gestion du réseau soit au courant de tous les détails des topologies physiques des domaines. Nous proposons ensuite un modèle distribué de l’optimisation de la protection dans les réseaux optiques multidomaines, une formulation beaucoup plus réaliste car elle est basée sur l’hypothèse d’une gestion de réseau distribué. Ensuite, nous ajoutons une bande pasiv sante partagée afin de réduire le coût de la protection. Plus précisément, la bande passante de chaque lien intra-domaine est partagée entre les p-cycles FIPP et les p-cycles dans une première étude, puis entre les chemins pour lien/chemin de protection dans une deuxième étude. Enfin, nous recommandons des stratégies parallèles aux solutions de grands réseaux optiques multidomaines. Les résultats de l’étude permettent d’élaborer une conception efficace d’un système de protection pour un très large réseau multidomaine (45 domaines), le plus large examiné dans la littérature, avec un système à la fois centralisé et distribué.

An enforced cooperation : understanding scientific assessments in adversarial polities through Quebec shale gas policymaking, 2010-2014

Les biotechnologies, le réchauffement climatique, les ressources naturelles et la gestion des écosystèmes sont tous représentatifs de la “nouvelle politique de la nature” (Hajer 2003), un terme englobant les enjeux marqués par une grande incertitude scientifique et un encadrement réglementaire inadapté aux nouvelles réalités, suscitant de fait un conflit politique hors du commun. Dans l'espoir de diminuer ces tensions et de générer un savoir consensuel, de nombreux gouvernements se tournent vers des institutions scientifiques ad hoc pour documenter l'élaboration des politiques et répondre aux préoccupations des partie-prenantes. Mais ces évaluations scientifiques permettent-elles réellement de créer une compréhension commune partagée par ces acteurs politiques polarisés? Alors que l'on pourrait croire que celles-ci génèrent un climat d'apprentissage collectif rassembleur, un environnement politique conflictuel rend l'apprentissage entre opposant extrêmement improbable. Ainsi, cette recherche documente le potentiel conciliateur des évaluation scientifique en utilisant le cas des gaz de schiste québécois (2010-2014). Ce faisant, elle mobilise la littérature sur les dimensions politiques du savoir et de la science afin de conceptualiser le rôle des évaluations scientifiques au sein d'une théorie de la médiation scientifique (scientific brokerage). Une analyse de réseau (SNA) des 5751 références contenues dans les documents déposés par 268 organisations participant aux consultations publiques de 2010 et 2014 constitue le corps de la démonstration empirique. Précisément, il y est démontré comment un médiateur scientifique peut rediriger le flux d'information afin de contrer l'incompatibilité entre apprentissage collectif et conflit politique. L'argument mobilise les mécanismes cognitifs traditionnellement présents dans la théorie des médiateurs de politique (policy broker), mais introduit aussi les jeux de pouvoir fondamentaux à la circulation de la connaissance entre acteurs politiques.