Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Avec les progrès réalisés dans les réseaux sans fil et mobiles, chercheurs et industriels ont déjà commencé le développement des futurs réseaux mobiles de 4ème génération (4G). Dans cette génération, l'équipement terminal, de l'utilisateur recherchera en permanence le meilleur réseau d'accès en fonction des besoins de l'utilisateur. Ce dernier aura plusieurs technologies d'accès sans fil à sa disposition et souhaitera être connecté au mieux, n'importe où, n'importe quand et avec n'importe quel réseau d'accès. Pour cela, les différentes technologies sans fil qui seront présentes dans la 4g (UMTS, WLAN, WMAN, etc), doivent coexister. Notre travail dans cet axe de recherche consiste à proposer une structure hiérarchique des réseaux sans fil et des protocoles de handovers entre les différents systemes. Le changement de réseau doit être rapide et sans perte de données afin de garantir la transparence vis-à-vis des utilisateurs mobiles. Les réseaux ad hoc sont considérés comme généralisation ultime des réseaux sans fil car ils limitent au maximum le rôle de l'infrastructure fixe. Ces dernières années, on observe des progrès significatifs pour étudier la QoS dans les réseaux ad hoc mobiles. Cette thèse présente une vision critique des travaux intéressants dans le domaine de la QoS dans les réseaux ad hoc. Les points forts et faibles de chaque proposition sont exploités pour réaliser un modèle complet de QoS. Ce modèle possède un protocole de routage avec QoS qui trouve la meilleure route pour chaque type de flux selon la demande. Il limite l'apparition des congestions et la surutilisation de la bande passante par un mécanisme de contro^le d'admission et de réservation.

Avec le déploiement de la technologie WiFi ces dernières années, les réseaux locaux sans fil connaissent un grand succès auprès des institutions et les réseaux ad hoc suscitent un réel intérêt auprès de la communauté de R&D. Parallèlement, avec l'émergence des services multimédias dans les réseaux mobiles, des travaux pour l'introduction de la qualité de service dans les réseaux ad hoc ont été proposés. Les études existantes sont souvent basées sur des hypothèses limitées et inadaptées aux propriétés des réseaux ad hoc. Dans cette thèse, nous proposons d'abord un protocole de routage avec différenciation de terminaux qui maximise les liens sans fil de haute qualité. Le but d'une telle approche est de prendre en compte l'hétérogénéité des nœuds dans les réseaux ad hoc et de supporter les situations où des terminaux mobiles peuvent accepter ou refuser la fonction de routage. Notre proposition apporte une solution aux variations des capacités des liens sans fil en routant les paquets de préférence à travers les routeurs collaboratifs ayant une grande capacité de transmission dans le but de maintenir une meilleure qualité de lien (grand débit) des routes dans le réseau. Nous prouvons ensuite la nécessité d'une gestion multicouches de la qualité de service dans un tel environnement. Cela permet de définir une stratégie de QoS en plusieurs couches de communication dans le but de prendre en considération les contraintes liées aux spécificités des réseaux mobiles ad hoc. Une combinaison des mécanismes de qualité de service au niveau IP et MAC (IEEE 802.11) est étudiée. De plus le principe de routage avec différenciation de terminaux décrit ci-dessus a été combiné avec la gestion de la qualité de service IP et MAC. Un autre volet de la thèse traite l'aspect de contrôle de topologie dans les réseaux ad hoc. Il consiste à contrôler la morphologie du réseau en utilisant la mobilité d'un ensemble de routeurs dédiés. Le principe est d'utiliser positivement la mobilité, qui est habituellement subie dans le réseau, afin d'améliorer les performances de ce dernier. Ainsi, des stratégies de déploiement des routeurs dédiés sont étudiées (dans un réseau ad hoc autonome ou interconnecté à une infrastructure) dans le but d'offrir une meilleure connectivité ou pour assurer un meilleur support de la qualité de service des applications temps réel. Pour les deux stratégies, le problème a été formulé comme un problème de programmation linéaire entière mixte. Cette thèse a été réalisée dans le cadre du projet ITEA Ambience. Dans ce contexte, nous avons entre autres contribué à la réalisation d'une plate-forme, qui illustre un exemple d'applications des réseaux ad hoc où des mécanismes décrits dans les parties précédentes sont utilisés afin d'améliorer les performances du système et répondre aux besoins des utilisateurs mobiles, dans un contexte hétérogène sécurisé. Mots-clés : Qualité de service, IEEE 802.11, Différenciation de services, Hétérogénéité des nœuds, Routage ad hoc, Contrôle de topologie, Routeurs dédiés, Connectivité.

Les réseaux ad hoc sont des réseaux sans fil et mobile sans aucune infrastructure, et le routage ad hoc est très différent de celui des réseaux traditionnels. Pour la sécurisation du routage ad hoc, il faut contrer non seulement les attaques actives, mais aussi des comportements égoïstes. De plus, il faut éviter la dégradation de performance causée par les mécanismes de sécurité. Dans cette thèse, nous présentons d'abord une classification de vulnérabilités du routage ad hoc, avec laquelle le modèle 'l'arbre des attaques' est utilisé. La séparation des objectives et des mécanismes d'attaques va nous permettre de repérer facilement quelles sont les attaques à contrer pour un objectif de sécurité donné. Ensuite, nous avons proposé quelques mécanismes de sécurité pour le routage des réseaux ad hoc, tout en limitant la dégradation de QoS due à ces mécanismes. Premièrement, un schéma de watchdog sécurisé appelé SWAN a été proposé. Il garantit l'authentification dans la supervision de watchdog et réduit le besoin de stockage du watchdog. Deuxièmement, nous proposons TRP qui est un protocole de routage réactif sécurisé intégrant un modèle de confiance. Troisièmement, deux mécanismes de sécurité appelé respectivement HPLS et TCSec ont été proposés pour sécuriser le protocole de routage proactive OLSR. Les simulations sur les mécanismes de sécurité que nous proposons dans cette thèse montrent qu'ils sont robustes et performants. Finalement, nous décrivons nos considérations pour concevoir un nouveau protocole de routage ad hoc sécurisé dès le départ, et quelques perspectives dégagées par les travaux de cette thèse.

Les Réseaux mobiles ad hoc (MANETs) appartiennent à une catégorie de réseaux sans fils qui n'a pas besoin d'infrastructure, chaque nœud jouant le rôle de l'hôte ainsi que du routeur. Les équipements mobiles dans ces réseaux sont généralement de petites tailles (PC portable, PDA...) d'où les contraintes de ressources en terme de mémoire et de batteries. Ces réseaux sont caractérisés par la faible bande passante qui diminue également en raison des interférences des signaux ainsi que la déplétion sur le canal (channel fading). Par conséquence, un nouveau type de routage est nécessaire pour améliorer la fiabilité de transmission. Certain protocoles de routage doivent être adoptés en prenant en compte la mobilité des nœuds ainsi que le manque des ressources. Puisque plusieurs applications de ces réseaux nécessitent la collaboration et la communication parmi les groupes de nœuds, les protocoles de routage multicast jouent un rôle très important. Les communication multicast sont plus efficaces que les communications unicast dans un environnement radio car elles profitent de la propriété de diffusion dans le canal radio et donc économisent l'utilisation de la bande passante ainsi que la consommation d'énergie. Le but de cette thèse est de proposer de nouveaux mécanismes et protocoles unicast et multicast pouvant répondre à plusieurs exigences comme la fiabilité, l'efficacité, l'adaptabilité, et la consommation d'énergie. Nous présentons trois contributions. La première contribution dans cette thèse concerne le routage unicast. Nous proposons un mécanisme de routage qui s'adapte aux changements fréquents de topologie ainsi que la faible puissance des batteries. Ce mécanisme, appelé Energy Conserving Dynamic Source Routing (EC-DSR), modifie le protocole de routage Dynamic Source Routing (DSR) en considérant la stabilité des nœuds voisins ainsi que la consommation d'énergie pendant la construction des chemins. Dans un deuxième temps, nous étudions le problème du routage multicast dans les réseaux ad hoc. Nous avons étudié les limitations des protocoles de routage multicast classiques ainsi que les problèmes dans les protocoles de routage multicast existants dans les réseaux ad hoc. Notre but étant de fournir un routage multicast efficace qui consomme moins de ressources. Un nouveau protocole de routage multicast, appelé Source Routing-based Multicast Protocol (SRMP), est proposé. Ce protocole utilise le concept de "source routing" pour minimiser la charge sur le réseau. SRMP permet une forte connectivité ainsi qu'une stabilité des liens entre les nœuds tout en minimisant la consommation d'énergie. A fin d'évaluer nos deux propositions, nous les avons implémenté sous le simulateur ns-2. Une étude comparative est aussi menée pour évaluer EC-DSR vis à vis DSR et montrer l'amélioration attendue de EC-DSR. De plus, une étude comparative est menée dans le cadre du multicast qui compare SRMP vis à vis On-demand Multicast Routing Protocol (ODMRP) et Adaptive Demand-driven Multicast Routing (ADMR). Les résultats obtenus sont favorables pour SRMP dans plusieurs points. Un environnement de simulations réaliste est fourni et permet d'étudier plusieurs modèles de mobilité dans nos expériences. L'effet de changement du modèle de mobilité sur la performance de chaque protocole est étudié. Dans un troisième temps, Nous étudions SRMP d'un point de vue analytique. Un modèle analytique basé sur la théorie des graphes aléatoires est dérivé. Les résultats numériques de ce modèle montrent le comportement de transition de phase pour certaines propriétés de SRMP, particulièrement ceux concernées par la connectivité.

Dans cette thèse, nous étudions certains points techniques clé sur ce sujet et proposons une résolution pratique et efficace des aspects suivants: Dans un cadre de design inter-couche, nous avons d'abord réglé le problème du contrôle de débit et du routage. Nous étudions la combinaison de l'acheminement et le contrôle du taux avec une formulation optimisation convexe afin de proposer une solution distribuée commune basée sur la conception des inter-couche. Nous avons d'abord développé un modèle de distorsion qui couvre à la fois l'impact de la quantification du codeur et la perte de paquets en raison de la congestion du réseau sur la qualité vidéo globale. Ensuite, le contrôle du taux d'émission optimal commun et le choix du routage sont réalisés en adaptant la vitesse variable d'émission au cours du temps et en minimisant la congestion du réseau global. Ensuite, nous abordons le problème du mécanisme d'authentification du codage conjoint. Dans cette partie, nous proposons un cadre pour une collaboration entre authentification et codage multimédia transmis sur des réseaux sans fil. Premièrement, nous fournissons un système d'authentification basé sur des méthodes graphiques qui peut non seulement construire une authentification flexible, mais aussi un compromis parmi certaines exigences pratiques telles que la robustesse et le retard. Puis, un taux de distorsion conjoint Source-Canal (JSCC) est optimisé ; une approche résistante aux erreurs vidéo encodée adpatative est présentée, dans laquelle la vidéo est encodée en plusieurs flux indépendants et à chaque flux est attribué une correction (Forward Error Correction-FEC) afin d'éviter la propagation des erreurs. En outre, nous considérons l'authentification avec le régime spécifique JSCC afin de parvenir à un résultat satisfaisant en termes de qualité de reconstruction de bout en bout. Ensuite, nous proposons d'appliquer conjointement la résilience aux erreurs (ER) et la super-résolution (SR) afin d'améliorer glabalement la résolution des flux d'images transmises sur les réseaux sans fil. Afin de lutter contre la propagation d'erreurs, une description multiple, méthode flexible de codage basée sur SPIHT-3-D (partitionnement 3-D dans des arbres hiérarchiques) est présentée pour générer des descriptions variables indépendantes en fonction de l'état du réseau. Puis, une stratégie originale de protection inégale contre les erreurs suivant le niveau de priorité est prévu afin d'attribuer un niveau supérieur de protection contre les erreurs des parties les plus importantes des flux. En outre, un algorithme robuste SR est proposé, en présence de différents types de taux de perte de paquets pour améliorer la résolution de l'image. Enfin, nous décrivons le problème du contrôle du taux pour le multimédia sur des réseaux hétérogènes. Dans cette partie, nous développons et évaluons un cadre d'allocation des taux optimaux sur plusieurs réseaux hétérogènes toujours basés sur le cadre de la conception inter-couches. Au début, nous développons et évaluons un modèle de distorsion en fonction de taux disponibles observés (ABR) et du temps d'aller-retour (RTT) dans chaque réseau d'accès, ainsi que des caractéristiques de chaque application. Ensuite, la répartition du taux est formulée comme un problème d'optimisation convexe qui minimise la somme de la distorsion attendue sur tous les flux applicatifs. Afin d'obtenir une résolution satisfaisante et simple à ce problème, nous proposons un théorème d'approximation par morceaux afin de simplifier le problème convexe et de prouver la validité de la théorie. En outre, la réalisation de l'algorithme rapide heuristique pour parvenir à une répartition optimale de qualité de service ou quasi-optimale de bout en bout dans le cadre du budget global des ressources limitées est le point le plus important de cette partie de thèse. En fin de compte, un bref résumé de tous les sujets abordés dans cette thèse est donné. Les principales contributions de cette thèse sont alors rappelés.

Mobile Ad hoc networks are a step closer to the vision of pervasive computing where all devices dynamically discover each other, organize communication networks between themselves and share resources/information to provide seamless service to the end-user. But providing any reliable service over such a network requires a secure and well-functioning network. Lack of infrastructure, energy-constrained nature of devices and high dynamism in the network makes the task of securing such networks quite challenging. In this thesis we propose cryptographic protocols, which are a stepping stone to a secure ad hoc network. In particular, we contribute to the areas of key establishment and secure routing in ad hoc networks. Key establishment is concerned with making available cryptographic keys to the devices, necessary for participating in the security services of the network. On the other hand routing needs to be secured in such networks as almost all nodes need to participate in the routing process (for eciency reasons) and presence of one malicious node could easily have drastic consequences on the routing performance of the whole network. Thus security checks are required to prevent such malicious nodes from hampering the routing process and to recover from it in case they do succeed. Our rst result is a new group key agreement protocol which is especially suitable for ad hoc networks but also outperforms most known protocols for traditional networks as well. The protocol adapts well to the dynamics of the network and is robust enough to deal with message losses and link failures. It requires little self-organization by the nodes in the network. We present some modied versions of the same and vii tel-00469429, version 1 - 1 Apr 2010 security proofs showing that the security of these protocols is tightly related to the security of the Decisional Die-Hellman problem. We also discuss issues related to implementation of this protocol in real scenarios. Our second result is the introduction of the notion of an Aggregate Designated Verier Signature (ADVS) scheme. An ADVS scheme allows ecient aggregation of multiple signatures on dierent messages designated to the same verier. We show how this primitive can be eciently utilized to secure reactive routing protocols in ad hoc networks. We provide a security model to analyze such schemes and propose an ADVS scheme which aggregates signatures more eciently than existing schemes.

Le nombre croissant des terminaux (PDAs, ordinateurs portables, téléphones) et l'expansion des réseaux sans fil (GSM, GPRS, UMTS, WLAN, Bluetooth) témoignent de la demande croissante des utilisateurs pour un accès à des ressources telles que des données ou des services applicatifs, à tout moment, et, n'importe où. Dans ce contexte, les réseaux ad hoc peuvent jouer un rôle important puisqu'ils ne nécessitent pas d'infrastructures pour communiquer, ils peuvent également être utilisés lorsque le déploiement d'infrastructures est coûteux ou sans objet, ou encore pour accroître la portée des réseaux à base d'infrastructure. De plus ces réseaux ad hoc peuvent opérer de façon autonome ou être connectés à d'autres types de réseaux afin de fournir à l'utilisateur un accès vers un ensemble plus important de ressources. Dans les réseaux filaires ou sans fil basés sur des infrastructures, les solutions proposées afin de localiser les ressources se basent majoritairement sur un répertoire centralisant les informations relatives aux ressources du réseau. Ces solutions sont inexploitables dans les réseaux ad hoc en raison du manque de connectivité induit notamment par les changements de topologie du réseau, et par l'épuisement des réserves énergétiques des batteries. Les solutions proposées pour les réseaux ad hoc se basent quant à elle sur des techniques de diffusion coûteuses, en terme de bande passante, et conduisent à surcharger le réseau. Cette inefficacité des solutions existantes demeure l'un des freins majeurs au développement d'applications pour les réseaux sans fil intégrant des réseaux ad hoc. L'objectif de cette thèse est d'offrir une localisation efficace des ressources afin de garantir un accès transparent aux ressources disponibles dans un environnement intégrant des réseaux ad hoc. Tout d'abord, cette thèse présente les travaux de recherche portant sur la localisation des terminaux et des ressources dans un réseau ad hoc. Nous introduisons ensuite les techniques que nous proposons pour effectuer une localisation des ressources adaptée aux caractéristiques des réseaux ad hoc (e.g., densité des nœuds, surface du réseau), et cela afin de limiter le trafic généré par cette localisation. Ceci nous conduit notamment à aborder distinctement la localisation de ressources dans les réseaux ad hoc à petite et large échelle. La première approche que nous proposons est entièrement distribuée. Les terminaux coopèrent ensemble afin de localiser des ressources sur le réseau. De plus, ce protocole inclut des techniques de caching et de préchargement afin d'améliorer les performances lors de la localisation et lors de l'accès aux ressources. Afin d'effectuer une localisation efficace des ressources dans un réseau ad hoc à grande échelle, nous introduisons une solution semi-distribuée basée sur un ensemble de répertoire déployés dynamiquement sur le réseau ad hoc (ou possiblement hybride). Ces contributions sont complétées par une évaluation des performances incluant une étude théorique et pratique basée sur des simulations et des expérimentations. Enfin, nous présentons une mise en œuvre de notre protocole de localisation de ressources dans le contexte des services Web. Cet intergiciel supporte un accès ubiquitaire à des services Web mobiles en se basant sur une découverte dynamique des instances de services Web présentes dans l'environement.

La croissance explosive des réseaux sans fil et l’augmentation du nombre de dispositifs sans fil ont soulevé de nombreuses difficultés techniques dans la planification et l’analyse de ces réseaux. Nous utilisons la modélisation continue, utile pour la phase initiale de déploiement et l’analyse à grande échelle des études régionales du réseau. Nous étudions le problème de routage dans les réseaux ad hoc, nous définissons deux principes d’optimisation du réseau: le problème de l’utilisateur et du système. Nous montrons que les conditions d’optimalité d’un problème d’optimisation construit d’une manière appropriée coïncide avec le principe de l’optimisation de l’utilisateur. Pour fonctions de coût différentes, nous résolvons le problème de routage pour les antennes directionnelles et omnidirectionnelles. Nous trouvons également une caractérisation des voies du coût minimum par l’utilisation extensive du Théorème de Green dans le cas d’antennes directionnelles. Dans de nombreux cas, la solution se caractérise par une équation aux dérivés partielles. Nous proposons l’analyse numérique par éléments finis qui donne les limites de la variation de la solution par rapport aux données. Lorsque nous permettons la mobilité des origines et destinations, on trouve la quantité optimale de relais actif. Dans les réseaux MIMO, nous montrons que, même lorsque la chaîne offre un nombre infini de degrés de liberté, la capacité est limitée par le rapport entre la taille du réseau d’antennes, la station de base, la position des mobiles et la longueur d’onde du signal. Nous constatons également l’association optimale mobile pour différentes politiques et distributions des utilisateurs. / The growing number of wireless devices and wireless systems present many challenges on the design and operation of these networks. We focus on massively dense ad hoc networks and cellular systems. We use the continuum modeling approach, useful for the initial phase of deployment and to analyze broad-scale regional studies of the network. We study the routing problem in massively dense ad hoc networks, and similar to the work of Nash, and Wardrop, we define two principles of network optimization: user- and system-optimization. We show that the optimality conditions of an appropriately constructed optimization problem coincides with the user-optimization principle. For different cost functions, we solve the routing problem for directional and omnidirectional antennas. We also find a characterization of the minimum cost paths by extensive use of Green’s theorem in directional antennas. In many cases, the solution is characterized by a partial differential equation. We propose its numerical analysis by finite elements method which gives bounds in the variation of the solution with respect to the data. When we allow mobility of the origin and destination nodes, we find the optimal quantity of active relay nodes. In Network MIMO systems and MIMO broadcast channels, we show that, even when the channel offers an infinite number of degrees of freedom, the capacity is limited by the ratio between the size of the antenna array at the base station and the mobile terminals position and the wavelength of the signal. We also find the optimal mobile association for the user- and system-optimization problem under different policies and distributions of the users.

La technologie des réseaux ad hoc a fait l'objet d'une attention particulière de par les propriétés qu'elle possède en termes d'auto-organisation et d'auto-adaptation. Une application importante est la mise en place rapide d'un réseau de communications, dans le cas d'une catastrophe sur des zones dépourvues d'infrastructure ou dans le cas où l'infrastructure existante est saturée, voire complètement détruite. Mais des changements topologiques résultant de la mobilité des n¿uds du réseau peuvent engendrer l'indisponibilité du service de communication. Une telle interruption est intolérable car elle peut mettre en péril la vie des équipes de secours. L'objectif de cette thèse est de traiter le problème de restauration de la connexité dans un réseau ad hoc déployé dans des situations d'urgence. Nous avons considéré dans un premier temps un scénario de lutte contre les feux de forêt, où les unités d'intervention forment un réseau ad hoc mobile. Dans un tel environnement, une des principales causes de la défaillance du système est le partitionnement du réseau. Le satellite a été donc proposé pour assurer l'interconnexion entre les différentes parties du réseau. Pour ce scénario, nous avons traité plusieurs problématiques, notamment la modélisation mathématique des déplacements des n¿uds sur la surface de simulation, la structuration du réseau grâce à la recherche d'un ensemble dominant indépendant et la réduction du surcoût en signalisation. Ensuite, nous avons considéré un deuxième scénario où les n¿uds forment cette fois-ci un réseau ad hoc maillé. Déployés sur une zone dépourvue de toute infrastructure de communications, les n n¿uds passent par un relais satellite pour se connecter à l'épine dorsale. Nous nous sommes intéressés particulièrement au choix des passerelles qui vont offrir un accès satellite un prenant en compte la minimisation du nombre de ces passerelles et le respect de contraintes portant sur la charge de ces passerelles ainsi que la distance maximale aux n¿uds terminaux. Nous avons appliqué un algorithme génétique dont les performances sont supérieures à des algorithmes basés sur la théorie des graphes.