TH3193
TH3193
TH3193
MEMOIRE
Présenté par
FELLAH So uma ya
Pour obtenir
Spécialité Informatique
Intitulé :
Remerciements
Il est important ensuite de remercier ardemment toutes les personnes ayant contribué de près
ou de loin à la réalisation de cette thèse. Mes sincères remerciements s’adressent à monsieur
Y. LEBBAH. Je souhaite remercier mon co-directeur de recherche monsieur M. KADDOUR
pour sa patience et ses encouragements, ses compétences scientifiques et qui a toujours su me
guider et me conseiller.
Je remercie tout particulièrement les membres de mon jury de thèse monsieur M. KHELFI,
monsieur H. HAFFAF et monsieur M. GEZZOURI pour avoir bien voulu consacrer une partie
de leurs temps à examiner et à évaluer ce travail.
Résumé iii
Résumé
ODMRP (On-Demand Multicast Routing Protocol) est un protocole de multicast très répandu
pour les réseaux ad hoc sans fil. Les forces d'ODMRP sont sa simplicité, son taux élevé
d’acheminement de paquet, et sa non-dépendance sur un protocole spécifique d'unicast.
Cette thèse propose un protocole sans fil de multicast basé sur ODMRP nommé OODMRP
(Optimized On-Demand Multicast Routing Protocol) qui minimise le nombre des nœuds
relayeurs et optimise la consommation des ressources radio et des ressources énergétique dans
le réseau.
Avant de choisir un nœud relayeur, chaque nœud cherche dans son voisinage l'existence
préalable d'un nœud relayeur. Dans le cas où ce nœud relayeur existe il selecte ce nœud
comme un ascendant.
Mots clé: Multicast, Routage, Réseau Maillé Sans fil, ODMRP, OODMRP
Abstract iv
Abstract
Indeed, before selecting a forwarding node, each node searches in its neighborhood the
existence of a forwarding node. In this case, it selects this node as an ascending one.
Our simulation results show that OODMRP reduces dramatically the number of forwarding
nodes and forwarded packets, compared to original ODMRP.
Remerciements………………………………………………………………. ii
Résumé……………………………………………………………………….. iii
Abstract……………………………………………………………………….. iv
Introduction générale………………………………………………………… 14
Chapitre I : Les réseaux sans fil………………………………………….… 16
I.1 Introduction…………………………………………………………………….......... 16
I.2 Les réseaux sans fil ……….…………………………………………………........... 17
I.2.1 La fiabilité de la communication sans fil ………………….…….…….…… 18
I.2.2 Les classes des réseaux mobiles……………….…………………………….. 18
I.2.2.1 Les réseaux avec infrastructure (cellulaires)………......................... 18
I.2.2.2 Les réseaux sans infrastructure (AD HOC)………….…………….… 19
I.2.3 Les réseaux maillés sans fil (Wireless Mesh Network -WMN)……………. 22
I.2.3.1 Architecture des réseaux maillés sans fil………….…………………. 24
I.2.3.2 Topologies des réseaux maillés sans fil……………………….……… 25
I.2.3.3 Caractéristiques des réseaux maillés sans fil…………………..……. 26
I.2.3.4 Les Scénarios d'application………………………...………………… 27
I.2.3.5 Problématique et défis dans WMN………………………………..….. 30
I.3 Conclusion…………………………………………………………………………… 32
II.1 Introduction…………………………………………………………………………. 33
II.2 Le multicast ………………………………………………………………………… 34
II.2.1 Groupes de Multicast………………………….……………………………. 35
II.2.2 Adressage multicast ……………….………………………………………. 35
II.3 Protocole de gestion de groupe d'Internet (IGMP)…………………………………. 36
II.4 Protocoles de routage multicast…………………………………………………..… 38
II.4.1 Définition du routage…………………………………................................ 38
II.4.2 Classification des protocoles de routage …………………………………... 38
Table des matières vi
Chapitre IV : Conception…………………………………………………..... 67
IV.1 Introduction……………………………………………..…………………………. 67
IV.2 Problématique du routage dans les réseaux sans fil ………………………………. 68
IV.3 Présentation du protocole ODMRP………………………………………………… 69
IV.3.1 Principe de fonctionnement………………………………………………… 69
IV.3.2 Format des paquets ODMRP…………………………………………..….. 70
IV.3.3 Structures de données du protocole………….……………………………. 71
IV.3.4 Inconvénient majeure d'ODMRP……………..…………………………… 72
IV.4 Principe de fonctionnement d’OODMRP………………………………………….. 72
IV.5 Différence entre ODMRP et OODMRP………………………………………….... 76
IV.5.1 Fonctionnement d’ODMRP……………………………………………….. 76
IV.5.2 Fonctionnement d’OODMRP…………………….……………………….. 77
IV.6 Consommation d’énergie ……….………………...……………….......................... 78
IV.7 Conclusion………………………………………………..………………………… 80
V.1 Introduction………………………………………………………………………….. 81
V.2 Description de la simulation……………………………………….……………….. 82
Table des matières vii
Bibliographie…………………………………………………………………. 95
Introduction générale
Malgré l’émergence de plusieurs applications dans les réseaux sans fil qui nécessitent des
communications multicast, tel que la visioconférence, le travail de collaboration, et les jeux
distribués, le multicast dans les réseaux sans fil demeure toujours un sujet de recherche où de
nombreuses problématiques restent à résoudre.
Le multicast est une technologie clé qui fournit une communication efficace entre les nœuds
d’un réseau et dont le but est d’acheminer le même flux de données à plusieurs récepteurs. Ce
type de communication est largement utilisé pour les applications temps réel.
Actuellement, les protocoles de routage des réseaux fixes ne sont pas appropriés aux réseaux
sans fil et de nouveaux protocoles pouvant s’adapter aux caractéristiques particulières (la
bande passante, l’énergie, temps de traitement) et aux diverses contraintes des réseaux sans fil
sont nécessaires. De nombreuses approches ont été explorées et analysées dans le cadre du
routage unicast. En revanche, peu de travaux se sont attelés à la problématique du routage
multicast et plus particulièrement dans la nouvelle génération des réseaux sans fil : les réseaux
maillés sans fil.
Une nouvelle génération de réseaux sans fil a vue le jour, appelés les réseaux maillés sans fil
(Wireless Mesh Network -WMN). Le succès des WMNs réside en leur capacité à couvrir de
larges zones géographiques à moindre coût avec de meilleures performances que les réseaux
ad hoc traditionnels.
Un réseau maillé sans fil fournit un accès aux différents réseaux tel que Internet, capteur,
cellulaire, IEEE 802.11, IEEE 802.15et IEEE 802.16, et prend en charge une large variété
d’applications temps réel (ex. visioconférence, voix sur IP, vidéo à la demande…). Les nœuds
routeurs sont généralement stationnaires ou avec un minimum de mobilité.
En conséquence, une nouvelle approche de routage s’avère nécessaire à travers une nouvelle
architecture décentralisée qui aura comme but de réduire la charge du réseau et faciliter la
gestion du routage en diminuant la consommation de ressources du réseau.
Ce travail entre dans le cadre de l'étude du problème de routage multicast dans les réseaux
maillés sans fil. Notre étude fournit principalement une étude synthétique des travaux de
recherche qui ont été fait, et qui se font à l'heure actuelle, dans le but de résoudre le problème
d'acheminement de données entre les nœuds du réseau. En particulier, nous exposons les défis
que pose le multicast dans les réseaux sans fil.
Notre contribution principale dans ce travail est l’extension et l’enrichissement d’un des
protocoles de communication multicast dédié aux réseaux sans fil les plus utilisé
actuellement. Nous répondons aux exigences de ce mode de réseaux en assurant un routage de
données avec une intervention d’un nombre minimal de nœuds intermédiaires.
Le premier chapitre présente les réseaux sans fil en générale et ses deux catégories “avec et
sans infrastructure”, afin d’en comprendre le principe de fonctionnement, les caractéristiques
et les facteurs qui influencent la conception de ces réseaux. La deuxième partie du chapitre est
consacrée à la description du réseau maillé sans fil (WMN), sa topologie, ses propres
caractéristiques et avantages par rapport aux autres réseaux sans fil.
Le deuxième chapitre se focalise sur le routage multicast en général : les concepts de base, la
notion de groupe de multicast, adressage multicast, le protocole de gestion des adhésions ainsi
que les protocoles de routage multicast en générale.
Le troisième chapitre est consacré à la description des protocoles de routage multicast dans les
réseaux sans fil et leur principe de fonctionnement. La deuxième partie du chapitre, se
focalise sur le routage multicast dans les réseaux maillés sans fil, nous allons présenter
certains travaux de recherche réalisés dans ce domaine.
Finalement, nous terminons se mémoire par une brève conclusion qui résume notre travail de
recherche et quelques perspectives.
15
Chapitre I: Les réseaux sans fil
Chapitre I
I.1 Introduction
Les environnements mobiles offrent aujourd'hui une grande flexibilité d'emploi. En
particulier, ils permettent la mise en réseau des sites dont le câblage serait trop onéreux à
réaliser dans sa totalité, voire même impossible.
Pratiquement inconnu, il y a encore quelques années, les réseaux sans fil (Wireless LAN ou
WLAN ou IEEE 802.11), sont, aujourd’hui, omniprésents dans notre société. Utilisant des
ondes radio, les WLAN existent pourtant depuis des années, mais l’augmentation de la bande
passante et la baisse des coûts a fait exploser leur croissance [1].
Les réseaux sans fil offrent aujourd'hui de nouvelles perspectives dans le domaine des
télécommunications. C’est des systèmes de transmission des données, conçus pour assurer
une liaison indépendante de l'emplacement des périphériques informatiques qui composent le
réseau. Les réseaux sans fil sont principalement employés lorsqu'il s'agit d'interconnecter des
utilisateurs nomades, munis de terminaux mobiles, entre eux.
Ce système ne pose aucune restriction sur la localisation des usagers. Il utilise des ondes radio
plutôt qu'une infrastructure câblée pour communiquer. Ce nouveau mode de communication
engendre des nouvelles caractéristiques, propres à l’environnement mobile : des déconnexions
fréquentes, un débit de communication et des ressources modestes, et des sources d’énergie
limitées.
16
Chapitre I: Les réseaux sans fil
Un réseau sans fil (wireless network) est, comme son nom l'indique, un réseau dans lequel au
moins deux terminaux (ordinateur portable, PDA, etc.) peuvent communiquer sans liaison
filaire [2].
Un réseau sans fil est un ensemble d’appareils connectés entre eux et qui peuvent s’envoyer et
recevoir des données sans qu’aucune connexion « filaire » physique reliant ces différents
composants entre eux ne soit nécessaire.
Grâce aux réseaux sans fil, un utilisateur a la possibilité de rester connecté tout en se
déplaçant dans un périmètre géographique plus ou moins étendu, c'est la raison pour laquelle
on entend parfois parler de mobilité.
Un environnement mobile est un système composé de sites mobiles et qui permet à ses
utilisateurs d'accéder à l'information indépendamment de leur position géographique.
Les réseaux sans fil permettent de relier très facilement des équipements distants d'une
dizaine de mètres à quelques kilomètres. De plus l'installation de tels réseaux ne demande pas
de lourds aménagements des infrastructures existantes comme c'est le cas avec les réseaux
filaires (creusement de tranchées pour acheminer les câbles, équipements des bâtiments en
câblage, goulottes et connecteurs), ce qui a valu un développement rapide de ce type de
technologies.
La norme la plus utilisée actuellement pour les réseaux sans fil est la norme IEEE 802.11,
mieux connue sous le nom de Wi-Fi. Les caractéristiques des normes principales sont
résumées dans le tableau I.1:
Un réseau local sans fil véhicule les informations soit par infrarouge, soit par onde radio
(utilisant généralement la bande de fréquence 2.4 GHz). La transmission par onde radio est la
méthode la plus répandue en raison de sa plus large couverture géographique et de son débit
plus important.
17
Chapitre I: Les réseaux sans fil
Les réseaux sans fils constituent avant tout une alternative aux réseaux câblés. Leur
compatibilité avec les réseaux câblés permet également de les y ajouter comme extensions.
La communication sans fil est moins fiable que la communication dans les réseaux filaires. La
propagation du signal subit des perturbations (erreurs de transfert, microcoupure, timeout…)
dues à l'environnement, qui altèrent l'information transférée et engendrent un accroissement
du délai de transit de messages à cause de l'augmentation du nombre de retransmissions. La
connexion peut aussi être rompue ou altérée par la mobilité des sites.
Un usager peut sortir de la zone de réception ou entrer dans une zone de haute interférence.
Le nombre d'unités mobiles dans une même cellule, par exemple dans le cas des réseaux
cellulaires lors d'un rassemblement populaire, peut entraîner une surcharge du réseau.
L'une des limites aussi de la communication sans fil vient de la relative faiblesse de la bande
passante des technologies utilisées [3].
Les réseaux mobiles ou sans fil, peuvent être classés en deux grandes classes :
• Réseau sans fil avec infrastructure de communication (modèle cellulaire).
• Réseau sans fil sans infrastructure (modèle ad hoc).
Dans ce mode, le réseau sans fil est composé de deux ensembles d'entités distinctes :
1- Les sites fixes d'un réseau de communication filaire classique (wired network).
2- Les sites mobiles (wireless network) [3].
Certains sites fixes, appelés stations de base (SB), sont munis d'une interface de
communication sans fil pour la communication directe avec les sites ou les unités mobiles
(UM) localisés dans une zone géographique limitée, appelée cellule. Comme le montre la
figure suivante I.1:
18
Chapitre I: Les réseaux sans fil
A chaque station de base correspond une cellule à partir de laquelle des unités mobiles
peuvent émettre et recevoir des messages. Alors que les sites fixes sont interconnectés entre
eux à travers un réseau de communication filaire.
Une unité mobile ne peut être, à un instant donné, directement connectée qu'à une seule
station de base. Elle peut communiquer avec les autres sites à travers la station à laquelle elle
est directement rattachée.
Dans le modèle de réseau sans infrastructure préexistante l'entité site fixe n’existe pas, tous
les sites du réseau sont mobiles et communiquent entre eux d'une manière directe en utilisant
leurs interfaces de communication sans fil [3].
Un réseau mobile Ad Hoc (fig. I.2), appelé généralement MANET (Mobile Ad hoc Network),
consiste en une grande population, relativement dense, d'unités mobiles qui se déplacent dans
un territoire quelconque. Le seul moyen de communication est l'utilisation «des ondes radio»
qui se propagent entre les différents nœuds mobiles, sans l'aide d'une infrastructure
préexistante ou d’une administration centralisée.
19
Chapitre I: Les réseaux sans fil
L'absence de l'infrastructure ou du réseau filaire composé des stations de base, oblige les
unités mobiles à se comporter comme des routeurs qui participent à la découverte et la
maintenance des chemins pour les autres hôtes du réseau.
Le concept des réseaux mobiles ad hoc a pour objectif d'étendre les notions de la mobilité à
toutes les composantes de l'environnement. Ici, contrairement aux réseaux basés sur la
communication cellulaire, aucune administration centralisée n'est disponible, ce sont les hôtes
mobiles eux-mêmes qui forment, d'une manière ad hoc, une infrastructure du réseau.
La topologie du réseau peut changer à tout moment, elle est donc dynamique et imprévisible
ce qui fait que la déconnexion des unités soit très fréquente (fig. I.3).
Aucune supposition ou limitation n'est faite sur la taille du réseau ad hoc, le réseau peut
contenir des centaines ou des milliers d'unités mobiles.
20
Chapitre I: Les réseaux sans fil
Les applications ayant recours aux réseaux ad hoc couvrent un très large spectre, telles que :
• réaliser des réseaux temporaires, ou à mettre en place très rapidement (conférence, réunion) ;
• permettre d'éviter de gros travaux de câblages dans des endroits où c'est difficile ou même
prohibé ;
• donner la possibilité de transmettre des données dans le cas d'applications mobiles (capteurs
d'entreprises...).
D'une façon générale, les réseaux ad hoc sont utilisés dans toute application où le déploiement
d'une infrastructure réseau filaire est trop contraignant, soit parce qu’il est difficile le mettre
en place, soit parce que la durée d'exploitation du réseau ne justifie pas de câblage à demeure.
• bande passante limitée : une des caractéristiques primordiales des réseaux basés sur la
communication sans fil est l'utilisation d'un médium de communication partagé (ondes radio).
Ce partage fait que la bande passante réservée à un hôte soit modeste.
• contraintes d'énergie : les hôtes mobiles sont alimentés par des sources d'énergie
autonomes comme les batteries.
• sécurité physique limitée : les réseaux mobiles ad hoc sont plus touchés par le paramètre de
sécurité que les réseaux filaires classiques.
21
Chapitre I: Les réseaux sans fil
• erreur de transmission : les erreurs de transmission radio sont plus fréquentes que dans les
réseaux filaires.
• interférences : les liens radios ne sont pas isolés, deux transmissions simultanées sur une
même fréquence ou utilisant des fréquences proches peuvent interférer.
• absence d'infrastructure : les réseaux ad hoc se distinguent des autres réseaux mobiles par
la propriété d'absence d'infrastructure préexistante et de tout type d'administration centralisée.
Les hôtes mobiles sont responsables d'établir et de maintenir la connectivité du réseau d'une
manière continue.
• topologie dynamique : les unités mobiles du réseau se déplacent d'une façon libre et
arbitraire. Par conséquent, la topologie du réseau peut changer à des instants imprévisibles,
d'une manière rapide et aléatoire.
• nœuds cachés : ce phénomène est très particulier à l’environnement sans fil. Un exemple est
illustré par fig. I.5. Dans cet exemple, les nœuds B et C ne s’entendent pas, à cause d’un
obstacle qui empêche la propagation des ondes. Les mécanismes d’accès au canal vont
permettre alors à ces nœuds de commencer leurs émissions simultanément provoquant ainsi
des collisions au niveau du nœud A.
La robustesse d’un réseau de ce type est en théorie beaucoup plus grande, puisque pour que le
réseau s’effondre, il faudrait qu’un très grand nombre d’éléments qui le compose cessent de
fonctionner. Et si l’un des éléments du réseau ne fonctionne plus, ceci ne change rien ou
presque pour les autres éléments : de nouvelles routes sont empruntées par les informations,
comme si l’élément manquant n’avait jamais existé.
I.2.3 Les réseaux maillés sans fil (Wireless Mesh Network -WMN)
La technologie mesh (terme anglais signifiant ‘maille’ ou ‘filet’), permet aux équipements
sans fil de se connecter de proche en proche, d’une façon instantanée, sans hiérarchie
centrale, formant ainsi une structure en forme de filet d’où son nom mesh. Cela permet
22
Chapitre I: Les réseaux sans fil
d’éviter d’avoir des points sensibles, qui en cas de panne, coupent la connexion d’une partie
du réseau. Si un hôte est hors service, ses voisins passeront par une autre route.
L’implémentation d’une telle topologie est appelée réseau maillé.
Les réseaux maillés sans fil (WMN : Wireless Mesh Networks) constituent une technologie
émergente, principalement présentée comme un moyen de construire des réseaux de
communauté (campus, entreprises, villes) à bas coût. Ce type de réseaux présente plusieurs
défis notamment le routage des données avec qualité de service (QoS).
La topologie maillée réduit le câblage, tout en fournissant de manière inhérente une forte
tolérance aux pannes et une grande évolutivité. Les réseaux maillés sans fil promettent de
repousser les limites physiques des réseaux Wifi, tout en apportant une souplesse inégalée.
L’architecture mesh a ainsi pu montrer qu’elle apportait des améliorations notables au WiFi
(fiabilité, couverture). A l'inverse des réseaux Wifi classiques, nul besoin d'un réseau filaire
reliant les points d'accès, il suffira de relier un ou deux nœuds du réseau sans fil maillé à
l'accès Internet. Avec, à la clé, deux avantages immédiats : des coûts de déploiement réduits et
une architecture plus flexible. Mais, surtout, de cette architecture résulte une forte tolérance
aux pannes, en raison de la redondance inhérente à la topologie maillée : les communications
peuvent être déroutées vers un autre chemin si l'un des éléments du réseau tombe en panne.
23
Chapitre I: Les réseaux sans fil
Les réseaux WMN adoptent le principe d’un réseau sans fil basé sur la transmission multi-
sauts. Leur architecture à deux niveaux concentre le routage sur une partie sans fil stable (le
premier niveau - backbone), composée de WMRs qui offrent une connectivité à des clients
mobiles (le deuxième niveau).
L’architecture peut être classifiée en 3 groupes selon la fonctionnalité des nœuds [5]:
a) WMN Infrastructure/Backbone
Ce type d’architecture inclut des routeurs maillés qui forment une infrastructure pour les
clients connectés à eux (fig. I.7), où les liens discontinus représentent les liens sans fil et les
liens pleins représentent les liens filaires. Avec la fonction ‘gateway’ les routeurs maillés
peuvent se connecter à Internet.
L’intégration de WMN avec les autres réseaux tels que Internet, cellulaire, IEEE 802.11,
IEEE 802.15, IEEE 802.16, réseau de capteurs, etc., peut être accompli à travers les fonctions
de gateway et bridging dans les routeurs.
Des clients conventionnels avec une interface Ethernet peuvent être connectés aux routeurs
maillés via des liens Ethernet. Pour des clients conventionnels avec les mêmes technologies
radio que les routeurs maillés, ils peuvent communiquer directement avec les routeurs maillés.
24
Chapitre I: Les réseaux sans fil
b) WMN Client
Ce type d’architecture est composé des nœuds clients et fournit un réseau P2P. Dans ce type,
un paquet recherche la destination par de multiples sauts entre les nœuds.
c) WMN Hybride
Ce type d’architecture est une combinaison des deux types précédents (fig. I.9).
L’architecture de réseau dite mesh est connue depuis longtemps : il s’agit d’une topologie où
chaque nœud du réseau est relié à tous les autres (mesh total) ou à certains de ses voisins
(mesh partiel), comme le montre la figure I.10.
25
Chapitre I: Les réseaux sans fil
Dans les réseaux maillés, l’administrateur déploie un grand nombre de points d’accès dont
seulement une sous‐partie est connectée à Internet et constitue les passerelles du réseau. Ainsi,
les autres points d’accès doivent relayer les paquets de leurs clients via leurs liaisons radio
afin qu’ils atteignent une passerelle Internet. Les réseaux maillés apparaissent comme une
approche prometteuse dans la réduction du coût où seuls quelques points d’accès sont reliés à
une interface filaire, les autres servant à étendre la couverture à moindre coût.
La gestion du réseau maillé est une manière de router les données, la voix et des instructions
entre les nœuds. Elle tient compte des connections et de la reconfiguration continues autour
des chemins coupés par “saut” du nœud au nœud jusqu'à ce que la destination soit atteinte. Un
réseau maillé dont tous les nœuds sont connectés entre eux est un réseau entièrement
connecté. Les réseaux maillés diffèrent d'autres réseaux parce que tous les éléments peuvent
se connecter entre eux par l'intermédiaire des sauts multiples.
Les réseaux maillés sont auto-curatif: le réseau peut toujours fonctionner même lorsqu'un
nœud tombe en panne ou une mauvaise connexion. En conséquence, un réseau très fiable est
formé.
Les caractéristiques principales des WMNs sont expliquées comme suit [5]:
L’objectif de développer les WMNs est de prolonger la couverture des réseaux sans fil
courants. Un autre objectif des WMNs est d’assurer la connectivité entre les utilisateurs qui
n’ont pas un lien directe à travers des sauts multiples.
26
Chapitre I: Les réseaux sans fil
Un WMN est compatible avec les standards IEEE 802,11 dans le sens de supporter les clients
maillés et les clients conventionnels Wi-Fi. De tels WMNs sont également interopérables avec
d'autres réseaux sans fil tels que le WiMAX ou les réseaux cellulaires.
Comme discuté avant, les WMNs se composent d'un ‘backbone’ sans fil avec des routeurs
maillés. Un ‘backbone’ sans fil fournit une large couverture, connectivité, et robustesse dans
le domaine sans fil. Cependant, la connectivité dans les réseaux ad hoc dépend des
contributions individuelles des utilisateurs qui ne peuvent pas être fiables.
• intégration
Un WMN supporte les clients conventionnels qui utilisent les mêmes technologies radio que
les routeurs maillés. Les WMNs permettent également l'intégration de divers réseaux existants
tels que le WiFi, l’Internet, les réseaux cellulaires et les réseaux de capteurs par des
fonctionnalités de gateway/bridge dans les routeurs maillés.
Par conséquent, les utilisateurs dans un réseau accèdent à des services fournis dans les autres
réseaux, à travers l'utilisation de l'infrastructure sans fil.
Un routeur peut être équipé par de multiples radios pour améliorer les fonctionnalités d’accès
et de routage, qui améliorent la capacité du réseau.
Les avantages des réseaux maillés sans fil sont nombreux, tels que le faible coût, facilité
d’installation, élimination du câblage, modèle économique simple, robustesse d’infrastructure.
La recherche et développement des WMNs est impulsée par plusieurs applications qui
démontrent clairement le marché prometteur alors qu'en même temps ces applications ne
peuvent pas être directement supportées par d'autres réseaux sans fil tels que les réseaux
27
Chapitre I: Les réseaux sans fil
cellulaires, les réseaux ad hoc, les réseaux de capteurs sans fil, etc. Dans cette section, nous
présentons certaines de ces applications [5].
Réseau domestique: la communication dans les réseaux à la maison peut être réalisée par la
gestion de réseau maillé. Par conséquent, la communication entre ces nœuds devient
beaucoup plus flexible et plus robuste aux défauts du réseau et aux coupures des liens, comme
c’est illustré dans fig. I.11.
Réseau communautaire : dans une communauté, l'architecture commune pour l'accès réseau
est basée sur le câble relié à l'Interne. Ce type d'accès réseau a plusieurs inconvénients:
· Même si l'information doit être partagée dans une communauté ou un voisinage, tout le
trafic doit traverser l’Internet. Ceci réduit de manière significative l'utilisation de
ressource du réseau. WMNs atténuent les inconvénients ci-dessus par des connectivités
flexibles maillés entre les maisons, comme montré dans fig. I.12.
Réseaux de zone métropolitaine: le déploiement des WMNs dans les zones métropolitaines
apporte plusieurs avantages :
· la communication entre les nœuds dans WMN ne se base pas sur une infrastructure câblée.
Comparé aux réseaux câblés, un MAN (Metropolitan Area Network) maillé sans fil est
une alternative économique pour les réseaux à grande échelle, particulièrement dans des
régions sous-développées.
· un MAN maillé sans fil couvre une zone potentiellement beaucoup plus grande qu'une
maison, entreprise, bâtiment, ou les réseaux communautaires, comme représenté dans fig.
I.14.
29
Chapitre I: Les réseaux sans fil
Systèmes de transport : la technologie du réseau maillé peut offrir un accès Internet dans des
autobus et des trains.
Systèmes de surveillance : comme la sécurité s'avère être un très grand souci, les systèmes
de surveillance de sécurité deviennent une nécessité pour des bâtiments d'entreprise, des
centres commerciaux, des grand magasins, etc. Afin de déployer de tels systèmes aux endroits
nécessaires, les WMNs sont une solution beaucoup plus viable que les réseaux câblés pour
relier tous les dispositifs.
Un réseau WMN a plusieurs caractéristiques différentes des autres réseaux sans fil. Pour
améliorer les performances de tel réseau, il faut chercher à tirer profit de ses spécificités. Il
existe plusieurs pistes de recherche dans les WMNs.
La conception Cross-layer entre le routage et les protocoles de la couche MAC (2) est une
piste intéressante de recherche. Auparavant, la recherche sur le protocole de routage a été
concentrée seulement sur la fonctionnalité de la couche réseau (3). Cependant, il a été
démontré que les performances d'un protocole de routage ne sont pas satisfaisantes dans ce
cas. L’adoption de multiple métrique de performances de la couche 2 dans des protocoles de
routage est un exemple. Cependant, l'interaction entre la couche MAC et le routage est étroite.
En second lieu, la conception de Cross-layer devient une nécessité parce que le changement
d'un chemin de routage implique le changement de canal ou de radio dans un nœud maillé.
Sans considérer la conception de Cross-layer, le processus de changement peut être trop lent
pour dégrader la performance de WMN.
30
Chapitre I: Les réseaux sans fil
Comment appliquer une solution innovatrice de canal unique à un système multi radio ou
multi canal est un autre problème de recherche.
La qualité de service
La plupart des efforts existants de recherches dans la couche MAC se focalisent sur la
capacité, le débit, et l'équité.
Les métriques existantes incorporées aux protocoles de routage doivent être augmentées.
D'ailleurs, comment intégrer de multiples métriques de performance dans un protocole de
routage de sorte que la performance globale optimale soit réalisée est un défi.
Le routage pour des applications multicast est une autre piste importante de recherche.
Beaucoup d'applications de WMNs ont besoin des possibilités du multicast. Par exemple,
dans une communauté, vidéo distribuée, etc.
Les protocoles de routage existants traitent tous les nœuds du réseau de la même manière.
Cependant, de telles solutions peuvent ne pas être efficaces pour les WMNs, parce que les
routeurs maillés dans un backbone WMN et les clients maillés ont des différences
significatives dans la contrainte d'énergie et la mobilité. Des protocoles de routage plus
efficaces qui tiennent compte de ces différences sont désirés pour les WMNs.
Dans les WMNs un routeur peut avoir plus d’une interface, qui peuvent être tuner aux
différents canaux. Un processus d’allocation de canal est une piste de recherche intéressante
pour améliorer les performances des WMNs.
31
Chapitre I: Les réseaux sans fil
I.3 Conclusion
Différent types de réseaux ont vu le jour, parmi eux, nous avons présenté les réseaux maillés
sans fil qui ont un avenir prometteur grâce à leurs divers atouts tel que la connectivité, la
couverture et par leur maillage, une forte tolérance aux pannes est garantie. La facilité
d’installation et de configuration des réseaux WMNs a favorisé leur utilisation dans plusieurs
domaines d’applications pour assurer une connectivité robuste à moindre coût.
Les environnements sans fil sont caractérisés par les déconnexions et les restrictions sur les
ressources utilisées. Ces limitations transforment certains problèmes, ayant des solutions
évidentes dans l'environnement classique, en des problèmes complexes et difficiles à
résoudre. Parmi ces problèmes figure le problème de routage et particulièrement le routage
multicast que nous allons discuter dans le chapitre suivant.
32
Chapitre II: Le Routage Multicast
Chapitre II
Le Routage Multicast
II.1 Introduction
Dans le réseau Internet actuel, des services tels que la télévision sur IP ou certains jeux
nécessitent de transmettre simultanément une quantité importante de données à de nombreux
récepteurs. Les méthodes de diffusion classiques des réseaux IP, le broadcast et l’unicast, ne
sont pas efficaces du fait qu’elles imposent un flux par récepteur et donc une multiplication
des données. C’est en 1991 que Steve Deering propose une technique appelée routage
multicast. Cette technique consiste à confier au réseau la tâche de duplication des données.
Après une introduction globale plus approfondie du concept de routage multicast, nous
étudions les techniques nécessaires à mettre en œuvre l’adressage multicast, le protocole de
gestion des adhésions et ainsi que les protocoles de routage.
33
Chapitre II: Le Routage Multicast
II.2 Le multicast
Comme le terme indique, le multicast IP a été développé pour prendre en charge une
communication efficace entre une source et de multiples destinations à distance [9]. Dans le
multicast, un système communique avec un groupe d'autres systèmes. L’information est
transmise à une seule adresse multicast et reçue par tout dispositif qui souhaite l’obtenir.
Dans les réseaux IP traditionnels, un paquet est typiquement envoyé par une source à une
seule destination (unicast). Alternativement, le paquet peut être envoyé à tous les dispositifs
sur le réseau (broadcast).
Avantages du multicast
Comme le montre la figure II.1, sans la prise en charge du multicast au niveau de la couche
réseau, de multiples copies d’un même message sont envoyées sur un même lien [7].
Avec la prise en charge du multicast au niveau de la couche réseau on constate les avantage
suivants :
34
Chapitre II: Le Routage Multicast
L’ensemble des récepteurs d’une transmission multicast est appelé Groupe Multicast, chaque
groupe multicast est identifié par une adresse multicast. Un utilisateur qui souhaite recevoir
des transmissions multicast doit rejoindre le groupe multicast correspondant, et devenir ainsi
un membre de ce groupe. Chaque nœud peut rejoindre et quitter un groupe multicast de
manière dynamique.
Quand un utilisateur rejoint un groupe, le réseau met en place les chemins de routage
nécessaires pour que cet utilisateur puisse recevoir les données envoyées au groupe multicast.
Chaque groupe de récepteurs est identifié par une adresse multicast, la classe D des adresses
IPv4 est utilisée pour le multicast, comme le montre la figure II.2.
Ø Toutes les adresses des groupes multicast IP appartiennent à l’intervalle :
224.0.0.0 – 239.255.255.255
35
Chapitre II: Le Routage Multicast
Adresses réservées
Parmi les adresses de le classe D, certaines sont réservées pour des fonctionnalités de routage
multicast telles que :
Pour passer de la couche réseau à la couche MAC, il faut traduire l’adresse multicast IP en
adresse MAC. Les 3 octets de l’adresse multicast de niveau MAC sont en hexadécimal 01 00
5E auxquels on ajoute les 23 bits de l’adresse multicast.
IGMP (Internet group management Protocol) [7] est un protocole simple pour la prise en
charge du multicast IP. Le protocole IGMP est un mécanisme qui informe le réseau qu’un
récepteur est membre d'un groupe particulier.
36
Chapitre II: Le Routage Multicast
Plusieurs versions du protocole IGMP ont vu le jour, chaque version a ses propres messages :
Un récepteur intéressé pour joindre un groupe multicast particulier génère un MR qui contient
la référence à cette adresse multicast (groupe). Le routeur construit une entrée dans la table de
transition et transmit les paquets multicast aux interfaces qui supportent des sous réseaux où
résident les hôtes enregistrés. Le routeur envoie périodiquement un MQ IGMP pour vérifier
qu’au moins un hôte sur le sous réseau est toujours intéressé à recevoir le trafic dirigé vers ce
groupe. Quand il n'y a aucune réponse à trois MQs IGMP consécutifs, le routeur arrête le
transfert du trafic destiné à ce groupe.
• LG (Leave Group) : envoyé par le récepteur au routeur local pour quitter un groupe.
L'utilisation des LGs réduit le trafic sur les sous-réseaux, lors de la réception d’un message
LG, le routeur génère une requête spécifique au groupe pour déterminer s'il reste des
récepteurs sur ce sous-réseau.
Un routeur peut également envoyer un MQ pour s’informer des groupes possédant des
membres sur le réseau attaché (également connu comme general MQ) ou pour apprendre si un
groupe particulier a encore des membres sur un réseau (group-specific MQ).
c) La version 3 : elle ajoute un nouveau concept appelé le source filtering qui permet au
récepteur de sélectionner ou d’exclure un ensemble spécifique de sources dans un groupe
multicast.
Le source filtering permet à un récepteur de signaler au routeur les groupes qu’il veut joindre
et de quel source(s) ce trafic est exclu. Cette information peut être utilisée par le protocole de
routage multicast pour éviter de livrer des paquets multicast provenant de sources spécifiques
à des sous-réseaux où il n'y a aucun récepteur intéressé. Les récepteurs signalent l'adhérence à
un groupe multicast en deux modes:
37
Chapitre II: Le Routage Multicast
· general query: pour apprendre l'état complet de réception multicast des interfaces
voisines.
· group-specific query: est envoyé par un routeur multicast pour apprendre l'état de
réception, concernant une seule adresse multicast, des interfaces voisines.
En raison de sa complexité plus élevée, IGMPv3 n'est pas pris en charge universellement par
tous les hôtes récepteurs.
Le routage est une méthode à travers laquelle on fait transiter une information donnée depuis
un certain émetteur vers un destinataire bien précis. Le problème du routage ne se résume pas
seulement à trouver un chemin entre les deux nœuds du réseau, mais encore à trouver un
acheminement optimal et de qualité. Il s'agit de trouver l'investissement au moindre coût en
capacité et réserve.
L’objectif d’un protocole de routage multicast est de construire un arbre recouvrant entre tous
les membres d’un groupe multicast. Autrement dit, il doit insérer un arbre de manière à ce que
tous les membres du groupe soient traversés par l’arbre.
Le principal but de toute stratégie de routage est de mettre en œuvre une bonne gestion
d’acheminement qui est robuste et efficace. Suivant la manière de création et de maintenance
de routes lors de l'acheminement des données, les protocoles de routage peuvent être séparés
en trois grandes classes (fig. II.3) [3]: les protocoles de routage proactifs, les protocoles de
routage réactifs et les protocoles de routage hybrides. Les protocoles proactifs établissent les
routes à l'avance en se basant sur l'échange périodique des tables de routage, alors que les
protocoles réactifs cherchent les routes à la demande.
38
Chapitre II: Le Routage Multicast
Un protocole de routage est dit proactif si les procédures de création et de maintenance des
routes, durant la transmission des paquets de données, sont contrôlées périodiquement. Cette
maintenance reste toujours active même s’il n’y a pas de trafic circulant dans le réseau. Deux
principales méthodes sont utilisées dans cette classe de protocoles proactifs : la méthode “Etat
des Liens” (Link State) et la méthode “Vecteur de Distance” (Distance Vector). Les deux
méthodes exigent une mise à jour périodique des données de routage qui doit être diffusée par
les différents nœuds de routage du réseau.
Les algorithmes de routage basés sur ces deux méthodes [3], utilisent la même technique qui
est la technique des plus courts chemins, et permettent à un nœud donné, de trouver le
prochain nœud pour atteindre la destination en utilisant le trajet le plus court existant dans le
réseau. Généralement le calcul du plus court chemin entre deux stations est basé sur le
nombre de nœuds (on dit aussi le nombre de sauts) que comportent les différents chemins qui
existent entre les deux stations.
Dans cette méthode, chaque nœud garde une vision de toute la topologie du réseau et ce par
l’intermédiaire des requêtes périodiques portant sur l’état des liaisons avec les nœuds voisins.
Pour que cette vision soit à jour, chaque nœud diffuse (par inondation) périodiquement l'état
des liens de ses voisins à tous les nœuds du réseau. Cela est fait aussi quand il y a un
changement d'état de liens.
Un nœud qui reçoit les informations concernant l'état des liens, met à jour sa vision de la
topologie du réseau et applique un algorithme de calcul des chemins optimaux afin de choisir
le nœud suivant pour une destination donnée. Un exemple des algorithmes les plus connus
appliqué dans le calcul des plus courts chemins, est celui de Dijkstra. Notons que le nœud de
routage calcule la plus courte distance qui le sépare d'une destination donnée, en se basant sur
l'image complète du réseau formée des liens les plus récents de tous les nœuds de routage.
39
Chapitre II: Le Routage Multicast
Le protocole OSPF (Open Shoretest Path First), est l'un des protocoles les plus populaires
basé sur le principe d’Etat des liens.
Dans cette méthode par contre, chaque nœud diffuse à ses nœuds voisins sa vision des
distances qui le séparent de tous les hôtes du réseau. En se basant sur les informations reçues
par tous ses voisins, chaque nœud de routage cherche le chemin le plus court vers n'importe
quelle destination. Le processus de calcul se répète, s'il y a un changement de la distance
minimale séparant deux nœuds, et cela jusqu'à ce que le réseau atteigne un état stable. Cette
technique est basée sur l'algorithme distribué de Bellman Ford (DBF).
L'algorithme DBF est basé sur l'utilisation des messages de mise à jour. Un message de mise à
jour contient un vecteur d'une ou plusieurs entrées dont chaque entrée contient, au minimum,
la distance vers une destination donnée. Le principe du DBF est utilisé par une grande partie
des protocoles de routage des réseaux filaires.
Dans les algorithmes de routage basés sur le principe d’état des liens, la convergence d'un
nœud de routage, est moins lente par rapport au DBF, ce qui a fait que état des liens est plus
préféré et utilisé dans beaucoup de réseaux modernes, tel que Internet. Cependant, l'approche
de l’état des liens exige que chaque nœud doit maintenir une version mise à jour de la
topologie complète du réseau, ce qui nécessite un grand espace de stockage et implique une
surcharge d'échange de paquets de contrôle dans le cas des réseaux dynamiques.
Comme décrit précédemment, les protocoles de routage proactifs tâchent de maintenir les
meilleurs chemins existants vers toutes les destinations possibles (qui peuvent représenter
l'ensemble de tous les nœuds du réseau) au niveau de chaque nœud du réseau. Les routes sont
sauvegardées mêmes si elles ne sont pas utilisées. La sauvegarde permanente des chemins de
routage est assurée par un échange continu des messages de mise à jour des chemins, ce qui
induit un contrôle excessif surtout dans le cas des réseaux de grande taille.
Les protocoles de routage réactifs, créent et maintiennent les routes selon les besoins. Lorsque
le réseau à besoin d'une route, une procédure de découverte globale de routes est lancée, et
cela dans le but d'obtenir une information spécifique, inconnue au préalable.
40
Chapitre II: Le Routage Multicast
Les protocoles hybrides combinent les deux idées : celle des protocoles proactifs et celle des
protocoles réactifs. Ils utilisent un protocole proactif pour avoir des informations sur les
voisins les plus proches (au maximum les voisins à deux sauts). Au-delà de cette zone
prédéfinie, le protocole hybride fait appel aux techniques des protocoles réactifs pour chercher
des routes.
Ce type de protocoles s’adapte bien aux grands réseaux, cependant, il cumule aussi les
inconvénients des protocoles réactifs et proactifs en même temps (messages de contrôle
périodique, le coût d’ouverture d’une nouvelle route).
Comme expliqué précédemment les protocoles de routages proactifs ont des avantages et des
inconvénients nous citons :
De même pour les protocoles de routages réactifs qui ont aussi des avantages et des
inconvénients :
Avant d’entamer les protocoles de routage en général pour Internet, nous commençons
d’abord par quelques définitions des concepts de base utilisés dans le routage multicast.
1. La notion d'inondation
41
Chapitre II: Le Routage Multicast
Ce comportement se répète jusqu'à ce que le paquet atteigne tous les nœuds du réseau (voir
fig. II.4). Notons que les nœuds peuvent être amenés à appliquer durant l'inondation certains
traitements de contrôle dans le but d'éviter certains problèmes, tel que le bouclage et la
duplication des messages.
Le mécanisme d'inondation est utilisé généralement dans la première phase du routage, plus
exactement dans la procédure de découverte des routes, et cela dans le cas où le nœud source
ne connaît pas la localisation exacte de la destination. Un paquet de requête de route est
inondé par la source afin qu'il atteigne la station destination. Il faut noter que l'inondation est
très coûteuse surtout dans le cas ou le réseau est étendu (latence, surcharge des
messages…etc.) [3]. C'est pour cette raison que les protocoles de routage essayent de
minimiser au maximum la propagation des paquets inondés en rajoutant d'autres paramètres
de diffusion.
Etant donnée l’adresse de la racine de l’arbre (ex : source), un routeur sélectionne comme son
ascendant (appelé voisin RPF) le routeur qui représente lui-même le prochain saut lors de
l’envoi de paquets unicast vers la racine. Le concept RPF permet d’éviter les boucles.
3. Un point de rendez-vous
Un RP (Rendez-vous Point) est un point dans le réseau où les sources multicast se relient aux
récepteurs multicast. Quand un relayeur souhaite envoyer des données, il les envoie d'abord
au RP, et quand un récepteur souhaite recevoir des données, il s'inscrit au RP.
Dans cette partie nous allons présenter quelques protocoles de routage multicast en général,
tel que les protocoles PIM et DVMRP. Il existe deux modes de fonctionnement pour les
protocoles de routage multicast :
42
Chapitre II: Le Routage Multicast
Le protocole PIM a deux modes de fonctionnement: PIM-DM, spécifié dans le RFC 3973, et
PIM-SM spécifié dans le RFC 2362. PIM-DM construit des arbres basés sur la source en
utilisant l’inondation et l’élagage. PIM-SM construit des arbres basés sur le noyau et
également des arbres basés sur la source avec des join explicites.
Dans le contexte de PIM-SM, cet arbre de diffusion est enraciné en un point particulier appelé
point de rendez-vous ou RP (Rendez-vous Point).
43
Chapitre II: Le Routage Multicast
Lorsqu’une source veut diffuser un paquet de données vers un groupe, le routeur d’extrémité,
responsable de la source, envoie en unicast un message d’enregistrement register message
dans lequel il encapsule le paquet de données.
44
Chapitre II: Le Routage Multicast
Le chemin suivi par les données n’est pas le plus court, donc, le routeur terminal peut décider
d’utiliser le meilleur chemin pour recevoir les paquets multicast d’un groupe.
Ce protocole est basé sur les mécanismes d’inondation, élagage et de greffage. La source
commence par inonder le réseau et chaque nœud élagage ses voisins non RPF.
Elagage :
Un routeur multicast qui n’a plus de récepteurs locaux ni de routeurs multicast en aval envoie
un message prune à la (aux) source(s) émettrice(s) pour ce groupe multicast via les interfaces
RPF et arme un timeout.
45
Chapitre II: Le Routage Multicast
Greffe :
A la réception d’une nouvelle demande d’un récepteur local ou d’un routeur en aval pour un
nouveau groupe (ou un groupe précédemment élagué), il envoie un message graft (message
envoyé pour se greffé directement un arbre multicast) vers le routeur RPF pour éviter
d’attendre l’expiration du timeout d’élagage.
Exemple :
Le protocole DVMRP (Distance vector multicast routing protocol) décrit dans le RFC 1075,
agit en mode dense : basé sur les mécanismes d’inondation et d’élagage, on inonde tout le
réseau et ceux qui ne sont pas intéressés ils sont élagués de l’arbre.
Principe de fonctionnement
Un routeur transmet un paquet multicast si le datagramme est reçu sur l’interface utilisée pour
envoyer un paquet unicast vers la source (reverse path). Un paquet est retransmis vers toutes
les interfaces non élaguées du routeur sauf l’interface RPF.
46
Chapitre II: Le Routage Multicast
Routage DVMRP
DVMRP utilise son propre routage unicast. Les routeurs échangent avec leurs voisins des
messages de mise à jour du vecteur de distance (liste de couples <destination, distance> où
destination désigne l’adresse unicast de l’émetteur multicast, et distance désigne le nombre de
routeurs intermédiaires entre la destination et le routeur local).
A l’issue de l’algorithme, chaque routeur connait pour chaque destination l’interface qui
donne accès au plus court chemin vers cette destination (c’est à dire l’émetteur multicast).
Poison Reverse
Le routeur B va décider que le routeur voisin A est en amont vers la source S, il envoie à A
une information de routage vers S dont la métrique est dite empoisonnée (fig. II.13). Par
conséquent, B attend le flux multicast de A pour la source S et A ne doit pas compter sur B
pour ce même flux.
47
Chapitre II: Le Routage Multicast
II.4.5 Synthèse
Les protocoles PIM-DM et DVMRP fonctionnent en mode dense et constituent des arbres
d’expédition basés source qui sont mieux adaptés pour ce mode. Contrairement au protocole
PIM-SM qui fonctionne en mode épars et constitue un arbre de distribution basé sur un point
de rendez vous. Le mode épars est adapté au réseau de taille importante par rapport au mode
dense.
Chacun de ces trois protocoles de routage, appartient à la classe des protocoles proactifs, il
produit la table de routage au préalable et rafraichit son contenu périodiquement.
48
Chapitre II: Le Routage Multicast
II.5 Conclusion
Actuellement, une demande croissante provient des applications faisant appel à des protocoles
de communication multipoints (Multicast) au sein desquelles un flot de données doit être
distribué vers diverses destinations de façon efficace. Ce type de communication met en jeu
plus de deux participants qui désirent échanger des informations.
Afin de prendre en charge ce genre d'applications, les réseaux offrent généralement le concept
de groupe de multidiffusion, de sorte qu'un émetteur puisse considérer l'ensemble de ses
destinations comme une seule entité (groupe multicast identifié par une seule adresse). Il
incombe alors au protocole multicast de distribuer les données à tous les membres du groupe
considéré.
Dans l’étude des protocoles de routage, nous avons commencé par présenter les trois classes
de protocoles de routages : proactifs, réactifs et hybrides, ainsi que les politiques et les
méthodes d’acheminement sur lesquelles ils reposent. Nous montrons comment fonctionne le
protocole de gestion d’hôtes IGMP et nous avons expliqué les fondements des protocoles de
routage PIM-SM, PIM-DM et le protocole DVMRP et nous avons montré leur
fonctionnement de base.
Dans le chapitre suivant nous détaillons le fonctionnement des protocoles de routage multicast
dans les réseaux sans fil en général et les réseaux maillés en particulier.
49
Chapitre III: Protocoles de routage multicast dans les réseaux sans fil
Chapitre III
III.1 Introduction
La plupart des applications utilisent du routage unicast, mais le multicast est en train
d’évoluer régulièrement, son utilité ne cesse de se justifier, par exemple dans des applications
de téléconférence ou de jeux en réseaux.
Les choix des structures dans les réseaux sans fil sont différents des choix effectués dans le
cadre des réseaux filaires dû aux difficultés propres aux réseaux sans fil.
Dans ce chapitre nous étudions des protocoles de routage multicast dans les réseaux sans fil
en générales, puis dans les réseaux maillés sans fil.
50
Chapitre III: Protocoles de routage multicast dans les réseaux sans fil
Un réseau multicast peut être représenté par un arbre, où le nœud source sera la racine et
l’ensemble des nœuds mobiles du réseau représente les feuilles et les nœuds de chaque
branche de cet arbre (fig. III.1). L’utilité de cette schématisation et que chaque nœud du
réseau aura un lien unique vers son nœud voisin. MAODV [10] et AMRIS [11] sont deux
protocoles de routage multicast de type arbre [12].
51
Chapitre III: Protocoles de routage multicast dans les réseaux sans fil
Contrairement à une architecture de type arbre, l’architecture maillée est un graphe fortement
connexe où pour chaque source il doit exister plus qu’un chemin vers une destination (fig.
III.2). Cette approche bénéficie de l’avantage de la connectivité du réseau pour procurer
plusieurs chemins entre les nœuds, il existe plusieurs protocole de routage adoptant ce schéma
de représentation comme : CAMP [13], ODMRP [14] qui est la base de notre projet, nous
allons l’étudier en détaille dans le prochain chapitre.
- Fournir une multitude de chemins entre une source et une destination afin de diminuer le
risque d’échecs des liens et, en conséquence, faire face aux problèmes de la mobilité.
- Dans les scénarios de multicast en multiples sources, les structures maillées fournissent des
chemins plus optimaux que des architectures en arbres.
- Employez plusieurs copies par paquet (une prodigalité relative à la consommation de bande
passante).
- Risque de congestion du réseau pour chaque paquet transmis.
- Très forte consommation énergétique au niveau des nœuds mobiles (exigeante en terme de
calcul).
52
Chapitre III: Protocoles de routage multicast dans les réseaux sans fil
Multiple chemins de routage => faire face Utilisation de plusieurs copies du même
Maillée aux cassures de liens et à la mobilité des paquet durant la transmission
nœuds => congestion de la bande passante
III.3 Les protocoles de routage multicast dans les réseaux sans fil
L'étude des protocoles de communication multicast est intéressante tant du point de vue
théorique que pratique.
Plusieurs travaux se sont penchés sur divers aspects et approches pour le multicast dans les
réseaux filaires en général, et dans les réseaux ad hoc en particulier.
Dans cette section nous décrivons les protocoles multicast de niveau IP comme MOLSR,
MAODV et CAMP. Ils exploitent une des propriétés fondamentales des réseaux ad hoc, en
l’occurrence le fait que les nœuds agissent en routeurs.
53
Chapitre III: Protocoles de routage multicast dans les réseaux sans fil
1. Informations locales
Un nœud conserve localement l’identifiant des groupes multicast dont il fait parti. La table
des arbres multicast maintient en chaque nœud les informations sur les différents groupes
multicast auxquels ce nœud participe. Chaque entrée de la table contient des renseignements
sur l’arbre défini par (source, groupe) : l’adresse de la source, l’adresse du groupe multicast,
l’adresse du père du nœud dans l’arbre, et la liste des fils de ce nœud. A chaque nœud dans la
table, on associe également une durée de vie.
Un nœud peut ne pas être membre d’un groupe, mais faire parti de l’arbre pour router les
messages vers les abonnés.
La table de routage multicast indique les plus court chemins vers tous les nœuds multicast
(identique à la table de routage unicast, mais n’utilise que les nœuds gérant le multicast, ces
nœuds étant connus sur le réseau car l’information est diffusée). Cette table est recalculée à
chaque fois que la table de routage OLSR est mise à jour, ou bien lorsqu’un nouveau nœud
multicast est découvert.
Les routeurs multicast diffusent dans le réseau le message MC-Claim (en utilisant la diffusion
optimisée d’OLSR par l’intermédiaire des MPR). Chaque nœud effectuant des opérations
multicast connait ainsi les autres membres du réseau multicast.
Lorsqu’une source désire émettre des données multicast vers un groupe spécifique G, elle
diffuse un message Source-Claim pour que les membres du groupe détectent sa présence et se
rattachent à l’arbre associé à cette source. L’invitation de la source est diffusée par MPR.
Les branches de l’arbre sont construites en partant des feuilles. Lorsqu’un membre du groupe
reçoit le message Source-Claim, et s’il ne fait pas partie de l’arbre définit par (source, G),
alors il se rattache automatiquement à l’arbre :
- Il regarde dans sa table de routage multicast pour choisir le prochain saut qui lui permet
d’atteindre la source en un nombre minimal de sauts. Ce nœud devient son parent dans cet
arbre multicast.
- Il envoie un message pour confirmer à son parent qu’il devient son fils.
- Le nœud parent qui reçoit un tel message se rattache à son tour à l’arbre (source, G) s’il
n’appartient pas à ce dernier, en suivant la même procédure. De plus, il actualise sa liste de
fils.
54
Chapitre III: Protocoles de routage multicast dans les réseaux sans fil
Les arbres sont rafraichis périodiquement par l’intermédiaire des messages de confirmation de
parents et par les Source-Claim. Lorsqu’un nœud reçoit un Source-Claim et qu’il appartient
déjà à l’arbre multicast, il se contente de mettre à jour les informations de durée de vie.
Les modifications de topologie sont détectées par l’échange de messages de contrôle d’OLSR.
Chaque nœud répercute alors ces modifications également sur les structures multicast qu’il
gère. Lors d’un changement dans le voisinage ou dans la topologie du réseau, la table de
routage multicast doit être recalculée.
Ces changements dans la table de routage peuvent amener à devoir changer un parent dans
l’arbre (route vers la source). Pour cela, les tables sont mises à jour.
Les relations de parenté sont également mises à jour régulièrement grâce aux messages que
chaque participant à l’arbre envoie régulièrement à son père.
Un nœud peut quitter un groupe multicast, ou bien seulement une branche d’un arbre. Dans
tous les cas, il est amené à détruire différentes branches de l’arbre et des liaisons entre les
nœuds appartenant à l’arbre.
Un nœud quitte une branche spécifique s’il découvre une meilleure route vers la source,
comme indiqué dans la maintenance de tables.
Lorsqu’un nœud quitte un groupe, il doit quitter tous les arbres multicast concernant ce
groupe. Pour cela, il doit détruire toutes les branches de ces arbres. Un nœud qui est une
feuille peut quitter l’arbre multicast par un simple message à son père (message Leave). Si le
55
Chapitre III: Protocoles de routage multicast dans les réseaux sans fil
père devient une feuille et s’il n’est pas abonné au groupe, il effectue la même opération de
destruction de branche.
Sinon, s’il est sur la route pour atteindre d’autres membres du groupe pour certaines sources,
il doit rester dans l’arbre pour effectuer le routage.
Lorsqu’il quitte un groupe, un nœud peut envoyer un message Leave à tous ses parents pour
tous les arbres auxquels il appartient, en une seule diffusion.
Pour rendre plus fiable OLSR, on peut introduire de la redondance et de la diffusion multiple.
On peut rendre les chemins multicast plus robustes et plus fiables en dédoublant les branches
de l’arbre. On possède ainsi un chemin de secours en cas d’erreur sur un lien.
Ainsi, en plus de choisir son père, un nœud choisit également un oncle dans l’arbre, voisin de
son père si possible. L’oncle est également à portée de communication du grand père (le nœud
connait son voisinage à deux sauts), et ainsi le grand père peut transmettre les données au
nœud en passant soit par le père soit par l’oncle.
MAODV, Multicast AODV (Ad hoc On-Demand Distance-Vector Routing Protocol) est basé
sur AODV, et fonctionne de manière réactive également, à la demande. Il utilise le même
principe qu’AODV, et les mêmes formats de requêtes de recherche de routes [15].
Dans AODV, les tables de routage de chaque nœud sont mises à jour lorsque ceux-ci désirent
connaitre le chemin vers une destination non répertoriée (ou pour laquelle l’information
correspondante est périmée) ou lorsqu’ils participent à une recherche de route lancée par un
autre nœud.
Le protocole MAODV construit un arbre partagé centré sur un noyau (le leader du groupe)
pour chaque groupe multicast du réseau. Le nœud leader est le premier participant au groupe,
il est chargé de le gérer et de le maintenir en place. L’arbre peut contenir des nœuds qui ne
font pas partie du groupe. Un numéro de séquence est associé à chaque groupe.
56
Chapitre III: Protocoles de routage multicast dans les réseaux sans fil
Non-Tree Node
Un nœud MAODV maintient une table de routage comme dans AODV pour le routage
unicast (l’algorithme AODV maintient une table sur chaque nœud, indexée par destination et
notamment le voisin auquel envoyer le paquet pour atteindre cette destination. Si la
destination recherchée n’est pas dans la table, on doit donc découvrir une route jusqu’au
destinataire. L’algorithme agit à la demande : recherche d’une route uniquement lorsque c’est
nécessaire), mais aussi une table de routage pour la structure en arbre du groupe. Cette table
contient l’adresse du groupe multicast (identifiant du groupe), le numéro de séquence,
l’adresse du leader du groupe, le nombre de sauts jusqu’au leader, et les informations sur le
saut suivant, qui correspondent aux voisins qui sont dans l’arbre. Les voisins peuvent être fils
ou père, chaque nœud possède au plus un père, et le leader ne peut posséder des fils que s’il y
a d’autres membres dans le groupe.
1. Message de requête
Les messages de demande de routes et de réponse sont ceux de AODV, adaptés pour le
multicast. Une requête est envoyée lorsqu’un nœud source désire envoyer un message
multicast. Le même type de message de requête REQ est utilisé lorsqu’un nœud désire joindre
un groupe multicast. Dans les deux cas, il s’agit donc de trouver une route vers l’arbre
multicast.
Si le nœud source connait le leader du groupe, il peut envoyer son message directement au
leader en mode unicast. Sinon, le message REQ est relayé saut par saut jusqu’à trouver un
nœud qui appartient déjà à l’arbre multicast. Le nœud récepteur de la requête répond alors en
mode unicast au nœud demandeur, par un message de réponse REP.
Les requêtes sont envoyées avec des TTLs de plus en plus grands, et si le nœud n’obtient pas
de réponse après plusieurs tentatives de connexion à un arbre multicast, il se considère comme
étant le premier membre de ce groupe, et il initialise le numéro de séquence du groupe.
57
Chapitre III: Protocoles de routage multicast dans les réseaux sans fil
Dans AODV, le message de réponse à une demande de route active directement la route, alors
que dans MAODV, la réponse indique seulement une route possible jusqu’à l’arbre, sans
l’activer.
Le nœud qui a émis la requête attend une certaine période, puis choisit la meilleure route à
utiliser pour atteindre l’arbre parmi les réponses qu’il a reçues. Il envoie alors un message
MACT (Multicast Activation) pour activer la route jusqu’à l’arbre, ou activer une nouvelle
branche de l’arbre multicast. La meilleure route est la plus récente (en regardant le numéro de
séquence), et la plus courte parmi ces dernières (en terme de nombre de sauts jusqu’à l’arbre).
3. Opérations de maintenance
Les opérations de maintenance lors de départ de nœuds sont plus complexes en multicast que
pour le protocole AODV unicast.
Pour un départ d’un membre du groupe, si le nœud n’est pas une feuille de l’arbre, il doit
rester dans l’arbre et faire office de routeur pour le groupe multicast. Sinon, il faut enlever la
branche de l’arbre désormais inutilisée, cela se fait par l’envoi d’un message MACT avec un
flag spécial. Les nœuds servant de routeur pour le nœud qui quitte le groupe sont également
supprimés de l’arbre, et ce jusqu’à ce qu’un membre du groupe soit rencontré.
Les problèmes propres à l’ad hoc sont bien sur les ruptures de lien dues à la mobilité, et cela
peut entrainer des envois à une partie seulement du groupe multicast. Les ruptures de lien
peuvent être détectées de la même façon que dans AODV, mais AODV se contente d’effacer
la route des tables de routage et de rechercher une nouvelle route, alors que dans MAODV la
procédure à lieu localement, seul le nœud fils du lien cassé peut initier la procédure de
réparation. Le nœud fils envoie en mode broadcast un message de requête REQ en demandant
à joindre l’arbre, indiquant également son nombre de sauts jusqu’au leader (pour éviter qu’un
de ses descendants renvoie une réponse).
Lorsqu’une réponse est obtenue, le nœud envoie un MACT pour raccorder sa branche à
l’arbre, et il envoie également un MACT avec un flag de mise à jour à ses descendants pour
qu’ils puissent changer leur compteur de sauts jusqu’au leader du groupe.
58
Chapitre III: Protocoles de routage multicast dans les réseaux sans fil
Exemple :
Si aucune réponse n’est reçue après une tentative de reconnexion de la branche (après
plusieurs essais), la source suppose alors que l’arbre est partitionné, et il faut sélectionner un
nouveau leader pour l’arbre partitionné. Si le nœud source est un membre du groupe, il
devient le leader. Sinon, il oblige un de ses descendants à devenir le leader.
Le protocole CAMP (Core-Assisted Mesh Protocol) utilise les nœuds noyaux dans le maillage
pour éliminer l'approche d’inondation utilisée dans d’autre protocole pendant la création et la
maintenance du maillage. Ainsi, elle est plus efficace dans l'utilisation de la bande passante.
Le protocole CAMP assume l'existence d'un protocole de routage unicast sous-jacent dans
l'environnement du réseau, qui fournit l’identificateur du prochain nœud [16].
59
Chapitre III: Protocoles de routage multicast dans les réseaux sans fil
Les pannes de lien ne sont pas très critiques dans le CAMP. Chaque récepteur perdant un
chemin sur le maillage utilise le message Push Join pour établir un nouveau chemin.
Nous notons que, en évitant l'approche d’inondation, le protocole CAMP laisse une charge de
contrôle inférieur. Toujours, les pannes du nœud noyau causent des pertes significatives de
paquet. Un autre inconvénient de ce protocole est qu'il n'est pas autonome, car il a besoin de
l'appui d'un protocole existant de routage unicast qui devrait fonctionner correctement en
présence des pannes du noyau. De ce fait, non pas tous les protocoles de routage peuvent être
compatibles avec le CAMP.
III.3.4 Synthèse
Le tableau ci-dessous présente un comparatif entre les trois protocoles de routage multicast
étudiés précédemment. MOLSR est un protocole qui construit un arbre multicast par source et
MAODV réalise un arbre partagé. Or Le protocole CAMP utilise un maillage pour
l’acheminement des données multicast. Le protocole MOLSR est dépendant d’un protocole de
routage unicast proactif. Les routes sont immédiatement disponibles à la demande. Les deux
protocoles MAODV et CAMP calculent les routes à la demande. Par conséquent, Les routes
ne sont pas immédiatement disponibles à la demande ce qui élimine le trafic de contrôle
continu pour les routes non utilisées.
60
Chapitre III: Protocoles de routage multicast dans les réseaux sans fil
III.4 Des nouveaux protocoles de routage multicast pour les réseaux maillés
sans fil
Les réseaux maillés sans fil sont une technologie émergente, principalement présentée comme
un moyen de construire des réseaux de communautés (campus, entreprises, villes) à bas coût.
Ce type de réseaux présente plusieurs défis notamment le routage des données. De ce fait,
plusieurs travaux de recherche se focalisent sur la réalisation des protocoles de routage
performant et adéquat aux particularités de ce type de réseau. Dans ce qui suit, nous nous
intéressons au routage multicast dans les réseaux maillés sans fil, et nous présentons certains
travaux réalisés dans ce domaine.
Dans les WMNs, les clients sont reliés à Internet par l'intermédiaire des passerelles qui agit en
tant qu’un nœud de relais dans l'arbre multicast ce qui rend la charge du trafic lourde pendant
des périodes particulières (paquets multicast et unicast) qui peut générer des conséquences
désastreuses sur la performance globale du réseau.
La solution est de réaliser un algorithme qui contrôle l’enregistrement des clients auprès des
passerelles et l’équilibrage de la charge des passerelles. Le protocole GAMP (gateway
associated multicast protocol) a investi le problème d'équilibrage de charge multicast dans les
WMNs [17]. Cet algorithme réalise l'enregistrement des clients aux passerelles et la
construction d'arbre multicast.
Un client doit d'abord s'inscrire à une passerelle qui est connectée à Internet. Il envoie la
requête GRDR (gateway route discovery request) aux passerelles. Chaque passerelle répond
par GRDP (gateway route discovery Reply) qui contient l’index de sa charge et après un
certain temps, il envoie la requête GRR (gateway register request) à la passerelle avec la
meilleure bande passante disponible qui répond a son tour par GRP (gateway reply) si
l’utilisation courante de sa bande passante est inférieure à un certain seuil, sinon elle répond
par (GRP-E) pour choisir une autre.
La figure. III.6 dépeint les procédures d'enregistrement de la façon dont un nœud client maillé
s'enregistre au prés d’une passerelle. G est un nœud de passage (passerelle) et C1, C2 et C3
sont les clients enregistrés au prés de G. C4 est un nœud souhaitant s'inscrire à G. 1, 2, 3, 4
sont GRDR, GRDP, GRR, GRP respectivement. C4 envoie d'abord GRDR à la passerelle G.
Après réception de GRDP, C4 envoie alors GRR encore. La passerelle G reçoit finalement
GRR, met à jour sa table de routage et envoie un GRP à C4. Cependant, la passerelle G crée
61
Chapitre III: Protocoles de routage multicast dans les réseaux sans fil
une table de routage de passage et enregistre C4 dans la première entrée si C4 est son premier
nœud.
Quand une passerelle trouve sa largeur de bande passante inférieure à un certain seuil ou que
la charge d’une passerelle voisine est meilleure que son seuil, elle envoie une (GRP-B) à la
passerelle voisine avec le meilleur index de charge, qui prendra sa charge en main après un
échange de requête/réponse. Lors de recevoir GHR (gateway handover request), GA transfère
toute la responsabilité de routage du nœud client pris en main au GB. GA vérifie sa charge si
sa bande passante est importante, il aura un déclanchement du processus d’équilibrage pour
récupérer ses responsabilités préalables.
Chaque passerelle enregistre l’adresse de la source dans sa table de routage multicast suite
aux messages Hello multicast.
Quand un nœud client voudrait joindre un groupe multicast, il envoie la requête (MRQ)
(multicast route request) à la passerelle enregistrée, si cette dernière a un lien avec la source,
donc elle envoie une (MRP) a la source sinon, elle envoie une (MSQ) (multicast source
request) vers les autre passerelles pour chercher la source. La passerelle qui a un lien avec la
source répond par (MSP).
62
Chapitre III: Protocoles de routage multicast dans les réseaux sans fil
Internet
3 1 3
1
G1 G1
2 3
1
C3 C2 C1 C0
C4
Le protocole GAMP permet d’alléger la charge des passerelles et réalise une coopération
entre elles.
Deux algorithmes ont été proposés pour optimiser le débit dans les WMNs multi-canal et
multi-interface: LCA (Level Channel Assignment) et MCM (Multi-Channel Multicast) [18].
Les deux algorithmes utilisent l’arbre comme une structure multicast puisque les routeurs
dans les WMNs ont un minimum de mobilité ou statiques (pas de changement de topologie).
Avant la construction de l’arbre multicast, les nœuds du réseau sont partitionnés en plusieurs
niveaux.
63
Chapitre III: Protocoles de routage multicast dans les réseaux sans fil
Pour chaque récepteur, si un de ses parents est un nœud d'arbre, alors il se connecte à ce
parent, sinon il choisie aléatoirement un de ses parents et l’intégrer à l’arbre et ainsi de suite
jusqu’à atteindre la source.
Le niveau 0 : réservé à la source qui utilise une interface sur le canal 0 pour envoyer les
paquets aux nœuds du niveau 1.
Le niveau i : utilise deux interfaces, une sur le canal i-1 pour la réception des paquets (a partir
du niveau i-1) et l’autre sur le canal i pour les transférés au niveau i+1ou au récepteur (client).
Ce protocole vise deux buts, le premier est de réduire au minimum le nombre de nœuds relais
a chaque niveau et le second, réduire les interférences (utiliser les canaux partiellement
chevauchés) [18].
Commence par la division des nœuds du réseau en plusieurs niveaux. En suite élimine les
liens entre les nœuds du même niveau (si 2 nœuds ne sont pas dans le même niveau ni dans
des niveaux adjacent, ils peuvent avoir le même canal). Après ces étapes, il faut identifier le
nombre min de nœud relais dans chaque niveau i qui couvre le maximum des nœuds dans le
niveau i+1 (assurer que chaque nœud a un seul parent). L’identification est d’une façon
ascendante (du récepteur ver la source).
64
Chapitre III: Protocoles de routage multicast dans les réseaux sans fil
Chaque interface de réception d’un nœud est associée à l’interface d’envoi de son nœud de
relais (utilisent le même canal). Chaque nœud relais dans un niveau a un canal différent des
autres nœuds.
Utilise tous les canaux. Choisir le canal qui minimise la somme des interférences avec les
nœuds voisins.
65
Chapitre III: Protocoles de routage multicast dans les réseaux sans fil
III.5 Conclusion
Dans ce chapitre nous avons présenté plusieurs protocoles de routage qui ont été proposé pour
assurer le service de routage multicast dans les réseaux sans fil. Nous avons décri leurs
principales caractéristiques et fonctionnalités afin de comprendre les stratégies utilisées dans
l'acheminement des données entre les différentes unités.
Nous avons vu ensuite quelque proposition de routage multicast pour les réseaux maillés qui
traitent des problèmes propre aux réseaux maillés tel que l’équilibrage de la charge des
passerelles sur lesquelles passe tout le trafic d’Internet et l’allocation des canaux pour les
réseaux multi-canal.
Parmi les caractéristiques principales des réseaux sans fil, nous citons les ressources et la
bande passante limités et la contrainte d’énergie. Pour la réalisation d’un protocole de routage
optimale, il faut prendre en considération ses contraintes. Dans le prochain chapitre nous
détaillons ce problème et nous proposons un protocole qui optimise l’utilisation des
ressources.
66
Chapitre IV: Conception
Chapitre IV
Conception
IV.1 Introduction
Dans les réseaux sans fil, les ressources sont très importantes d’où la nécessité de les préserver.
Donc, un protocole de routage qui minimise le nombre de ressources réseau employées est un
besoin critique.
Notre projet consiste à proposer une version optimisée OODMRP (Optimized On-Demand
Multicast Routing Protocol) du protocole de routage multicast le plus réputé ODMRP de telle
sorte qu’il minimise le nombre de nœud transférant les paquets multicast afin d’optimiser
l’utilisation des ressources et de réduire le trafic sur le réseau.
Nous commençons par une description détaillée du protocole de routage multicast ODMRP
(On-Demand Multicast Routing Protocol) et ses caractéristiques. Ensuite, nous présentons
notre protocole OODMRP.
Chapitre IV: Conception
La grande majorité des algorithmes de multicast au sein des réseaux filaires met en œuvre une
structure d’arbre (partagé ou non). L’arbre est le moyen le plus efficace en termes de ressources
pour connecter n nœuds et garantit la non duplication des données. De plus, les décisions de
routage sont très simples et se limitent à retransmettre les données sur les autres interfaces,
exceptée celle par laquelle le message est arrivé. Vouloir transposer directement ces principes
aux réseaux sans fil peut se révéler très inefficace.
Il ne faut pas perdre de vue que l’emploi d’un protocole de multicast pour envoyer une donnée
à un ensemble de destinataires doit permettre de réduire le nombre de ressources réseau
employées. De plus, la mise en œuvre d’un protocole de multicast peut s’avérer utile car elle
offre aussi un moyen robuste pour joindre des destinataires dont l’adresse n’est pas connue a
priori ou qui change régulièrement. Comme nous l’avons souligné plus haut, il est important de
réduire le nombre de transmissions (et la consommation d’énergie au sein des mobiles) dans un
réseau sans fil car la bande passante est limitée. Le multicast doit permettre d’optimiser la
gestion du médium radio en évitant les retransmissions superflues de messages et en tirant parti
de la caractéristique de diffusion inhérente au médium radio [12].
Récemment, plusieurs protocoles de multicast dans les réseaux sans fil ont été proposés telle
que MAODV [20], ODMRP [21] [22] [23] [14], ADMR [24] et CAMP [25]. ODMRP, est l’un
des protocoles de routage multicast les plus utilisés actuellement. En outre, des caractéristiques
d'exécution d'ODMRP ont été intensivement étudiées. Les raisons pour lesquelles nous avons
choisi le protocole ODMRP sont nombreuses:
68
Chapitre IV: Conception
· simplicité ;
· utilisation des mises à jour des routes ;
· maintenance et exploitation des multiples chemins redondants ;
· exploitation de la nature broadcast des environnements des réseaux sans fil ;
· capacité de routage unicast.
ODMRP est basé sur une structure maillée (mesh-based), plutôt que le conventionnel basé-
arbre, il utilise le concept du groupe d’expédition ‘forwarding group’ (seulement le sous-
ensemble de nœuds qui transmettent les parquets multicast). Il applique les procédures à la
demande pour construire les routes dynamiquement et maintenir les membres du groupe
multicast.
Définitions
• Join Query : est un paquet de contrôle envoyé par l'émetteur du multicast pour lancer une
session multicast. En outre, la source multicast envoie des paquets Join Query périodiquement
pour rafraichir le chemin d'expédition.
• Join Reply : est un paquet de contrôle envoyé par les abonnés du multicast. Les paquets Join
Reply sont expédiés en amont vers la source multicast pour renforcer le chemin d'expédition
pour les données de multicast.
• Nœuds relayeurs (Forwarding nodes) : ce sont des nœuds intermédiaires, qui transmettent des
données multicast au nom de la source multicast. Les nœuds intermédiaires indiquent leur
volonté de participer à la transmission des données multicast par l'expédition des paquets Join
Query, qui permettent aux nœuds descendants de choisir ces nœuds comme des nœuds
relayeurs. A travers l'expédition des paquets Join Reply les nœuds intermédiaires
s'autoproclament comme des nœuds relayeurs et forment ainsi le chemin d'expédition. L'état
d'expédition est maintenu par le rafraichissement périodique des chemins de routage par les
paquets Join Query, qui permettent à des abonnés de multicast de découvrir de meilleurs
chemins d'expédition.
69
Chapitre IV: Conception
Chaque nœud intermédiaire qui reçoit le paquet Join Query, enregistre l’adresse de son
ascendant ainsi que le numéro de séquence et retransmet le paquet. Les paquets Join Query
dupliqués sont détectés par l'intermédiaire du numéro de séquence.
Quand un récepteur multicast reçoit le paquet Join Query, il choisit le meilleur chemin, crée et
broadcaste un paquet Join Reply à ses voisins. Ce Join Reply contient la source et le dernier
saut de la source à lui-même.
Quand un nœud reçoit un Join Reply, il vérifie si son adresse figure dans le paquet. Si c’est le
cas, il réalise qu’il est sur le chemin ver la source et met son flag FG_FLAG (Forwarding
Group Flag) et broadcaste son propre Join Reply. De cette façon le Join Reply est propagé par
chaque membre du group d’expédition jusqu'à ce qu'il atteigne la source de multicast via le
chemin choisi [26].
70
Chapitre IV: Conception
- Next Hop IP Address: adresse IP du prochain saut parent vers la source multicast
71
Chapitre IV: Conception
Les nœuds exécutants ODMRP doivent maintenir les tables suivantes [14] :
1. Table de routage
La table de routage est créée à la demande et maintenue par chaque nœud. Une entrée est
insérée ou mise à jour quand un Join Query non-dupliqué est reçue. Le nœud stocke la
destination (c.-à-d., la source de Join Query) et le prochain saut à la destination (c.-à-d., le
dernier nœud qui a propagé le Join Query). La table de routage fournit les informations
concernant les prochains sauts en transmettant les réponses Join Replies.
3. Cache du message
Le cache du message est maintenu par chaque nœud pour détecter les duplications. Quand un
nœud reçoit un nouveau Join Query ou une donnée, il stocke l'adresse de source et
l’identificateur unique du paquet. Notez que les entrées dans le cache de message n'ont pas
besoin d'être maintenues de manière permanente. Des arrangements tels que LRU (Least
Recently Used) ou FIFO (First In First Out) peuvent être utilisés pour expirer et enlever les
anciennes entrées et pour empêcher la taille du cache de message d’être étendue.
72
Chapitre IV: Conception
ODMRP forme des chemins multiples de transmission avec énormément de nœuds relayeurs,
ce qui inonde le réseau par du trafic constitué de paquets redondants.
Notre démarche, concrétisée par le protocole OODMRP, consiste à réduire ce trafic inutile qui
épuise les ressources du réseau par l’optimisation du nombre de nœuds relayeurs. Notre
contribution se situe à deux niveaux :
Si un nœud a déjà un nœud relayeur en amont il ne choisira pas un autre nœud qui n’est pas
relayeur. En outre, il ne change pas un nœud relayeur par un autre non relayeur à la réception
de nouveau Join Query.
2. Si un nœud veut joindre le groupe pour la première fois et que l’un de ses voisins est déjà un
nœud relayeur, il s’attache directement à ce nœud.
A la réception d’un paquet Join Query, chaque nœud vérifie si le nœud transmetteur de ce
paquet est un relayeur. Si c’est le cas il le choisit comme ascendant ver la source.
Si un nœud reçoit un Join Query d’un relayeur, il vérifie si l’ascendant enregistré dans sa table
de routage n’est pas un relayeur. Si c’est le cas, il le remplace avec celui qui a transité ce Join
Query.
Cette vérification permet de minimiser le nombre des nœuds relayeurs de flux et ainsi réduire
la consommation des ressources et le nombre de paquets transmis sur le réseau.
Si un nœud devient relayeur pour la première fois, il envoie un paquet Session Exist aux voisins
pour les informer qu’il est devenu un relayeur.
Pour expliquer les démarches du protocole nous présentons les deux algorithmes principaux ci-
dessous :
Algorithme 1 : montre le traitement réalisé à la réception d’un paquet Join Query ainsi que les
vérifications à faire et à quel moment il faux modifier le contenu de la table de routage.
A la réception du premier Join Query, le nœud rafraichit la table de routage, modifie le champ
Session et retransmet le paquet. Si le nœud est un membre du groupe multicast et il envoie un
JoinReply.
Si le nœud reçoit un autre Join Query d’un nœud relayeur, il vérifie si son ascendant n’est pas
un nœud relayeur, si c’est le cas, il rafraichit sa table de routage. Si le nœud est un membre du
groupe multicast, il envoie un JoinReply.
73
Chapitre IV: Conception
Algorithme1 handleJoinQueryReceipt
2: jq_table.enterInTable;
3: jr_table.lookupsession;
5: retransmettre le JoinQuery;
6: si (mcast_membership_table.lookup) alors
7: sendJoinReply;
8: fin si
9: sinon
12: jq_table.enterInTable;
14: sendJoinReply;
15: fin si
16: fin si
17: fin si
21: jq_table.enterInTable ;
23: sendJoinReply;
24: fin si
25: fin si
26: fin si
74
Chapitre IV: Conception
29: fin si
4: si (mcast_membership_table.lookup) alors
5: jq_table.enterInTable2;
6: sendJoinReply;
7: fin si
8: fin si
9: fin si
de routage.
75
Chapitre IV: Conception
2. Le paquet Join Query est modifié par l’insertion d’un nouveau champ Session. La valeur de
Session est égale à 1 si le nœud transmetteur de ce paquet est déjà un nœud relayeur et à 0 dans
le cas contraire.
3. Le paquet Session Exist, c’est le paquet que nous avons ajouté, ce paquet est envoyé par un
nœud dés qu’il devient un relayeur, il comprend les champs suivants :
76
Chapitre IV: Conception
Après un certain temps, Le récepteur R2 joint le groupe et choisit N3 comme un nœud relayeur
vers la source. Cet exemple montre que pour le même flux de donnée, on a plusieurs relayeurs
pour un seul descendant. Dans la totalité on a 5 nœuds relayeurs générés par le protocole
ODMRP transmettant le flux de données.
Après un certain temps, Le récepteur R2 joint le groupe et choisit N4 comme un nœud suivant
vers la source puisqu’il est déjà un relayeur pour ce flux (fig. IV.9). Dans la totalité on a 2
nœuds intermédiaires transmettant le flux, donc on a une différence de 3 nœuds entre
77
Chapitre IV: Conception
OODMRP et ODMRP. Cet exemple montre la manière dont OODMRP optimise le nombre de
nœuds relayeurs.
Dans la section suivante nous abordons le critère de la consommation d’énergie dans les
réseaux sans fil munies des sources d’énergie autonomes. Dans ce type d’alimentation limitée,
la consommation d’énergie doit être prise en compte au niveau du routage afin de préserver les
ressources énergétiques et augmenter la durée de vie du réseau.
La fonction d’énergie
L’énergie consommée pour émettre un message de k bits sur une distance d est donnée par la
formule suivante :
ETx (k , d ) = ETx (k ) + ETx amp (k , d ) [27](I.1)
L’énergie consommée pour recevoir un message de k bits est donnée par la formule suivante :
ERx (k ) = k ´ Eelec [27](I.2)
Avec :
Eelec énergie électrique de transmission/réception
78
Chapitre IV: Conception
Par conséquent, l’énergie consommée pour la transmission d’un message de k bits entre deux
nœuds avec une distance d est égale à :
E Total = E Tx (k , d ) + E Rx (k )
E Total = E Tx (k ) + E Tx amp (k , d ) + E Rx (k ) [27](I.3)
( )
E Total = (E elec ´ k ) + E Tx amp ´ k ´ d 2 + ( E elec ´ k )
On remarque que la transmission est l’opération qui consomme le plus d’énergie à cause du
facteur d’amplification.
79
Chapitre IV: Conception
IV.7 Conclusion
La communication multicast est un domaine de recherche très actif, où l’objectif principal
demeure la réalisation des mécanismes de routage tout en préservant les ressources limitées
du réseau joue un rôle important dans les prochains réseaux de communication.
Notre étude repose essentiellement sur ce problème où le but de notre travail est de réduire les
ressources utilisées ainsi que le trafic total sur le réseau.
La conclusion générale que nous pouvons tirer de l'étude des différentes stratégies, est que la
conception d'un protocole de routage pour les réseaux sans fil doit tenir compte de tous les
facteurs et limitations physiques imposés par l'environnement afin que la stratégie de routage
ne dégrade pas les performances du système.
Le protocole que nous avons proposé OODMRP est implémenté dans le simulateur réseaux
NS2, connu par son efficacité et ses résultats proches de ceux obtenus dans un environnement
réel.
80
Chapitre V: Simulations et résultats
Chapitre V
Simulations et résultats
V.1 Introduction
Les protocoles de routage doivent être évalués afin de mesurer les performances de la
stratégie utilisée et de tester sa fiabilité. L'utilisation d'un réseau sans fil réel dans une
évaluation est difficile et coûteuse, en outre de telles évaluations ne donnent généralement pas
des résultats significatifs. Le réseau réel n'offre pas la souplesse de varier les différents
paramètres de l'environnement et pose en plus le problème d'extraction de résultats, c'est pour
cela que la majorité des travaux d'évaluation de performances utilisent le principe de
simulation vu les avantages qu'il offre.
En effet, la simulation permet de tester les protocoles sous une variété de conditions. Durant
ces simulations on doit varier les différents facteurs de l'environnement tels que le nombre
d'unités, le nombre de nœuds récepteurs, le territoire du réseau et la distribution des unités
dans ce territoire.
Après l’implémentation d’OODMRP sous le simulateur NS2, nous avons modélisé quelques
scénarios pour évaluer le fonctionnement de notre protocole OODMRP par rapport au
protocole d’origine ODMRP.
81
Chapitre V: Simulations et résultats
- On peut simuler pour comprendre le fonctionnement d'un système afin d'en formuler et d'en
mettre au point les lois d'évolutions, c'est toute la problématique de la simulation des
phénomènes physiques, le simulateur dans ce cas à pour rôle de permettre la mise au point
d'un modèle.
L'approche simulation trouve toute sa justification dans l'ingénierie des systèmes complexes
pour lesquels il est difficile d'avoir une vision globale, même si l'on est capable d'appréhender
chacun des composants pris individuellement [12].
NS2 utilise des scriptes en TCL pour simuler des scénarios. TCL est un langage de commande
comme le shell UNIX. Son nom signifie Tool Command Language. TCL offre des structures
de programmation telles que les boucles, les procédures ou les notions de variables.
82
Chapitre V: Simulations et résultats
Après avoir exécuté une simulation à partir d’un fichier TCL décrivant le scénario, NS génère
un fichier texte (appelé fichier trace) décrivant précisément l’avancement des paquets au sein
du réseau de la simulation. En effet, chaque ligne représente un paquet envoyé, éliminé,
retransmit ou reçu par un nœud du réseau.
Le plus important dans une étude telle que la notre est l’analyse des résultats recueillis. Nous
avons utilisé le langage awk1 pour extraire les résultats à partir du fichier trace [32].
Les fichiers suivants définissent les classes correspondantes pour l'exécution d'ODMRP
(figure V.1).
1
http://www.gnu.org/software/gawk/manuel/gawk.html
83
Chapitre V: Simulations et résultats
Dans le simulateur ns2, les points finaux où des paquets du réseau sont consommés ou
construits s'appellent agents. Par conséquent la classe ODMRPAgent définit les points finaux
du réseau pour le protocole ODMRP. La classe ODMRPAgent hérite de la classe générique
d'agent et ODMRPAgent maintient sa table de routage comme un ensemble de tables (hash
tables), qui sont définies dans les classes JQTable et JRTable. Les classes JoinQueryTimer et
JoinReplyTimer définissent les temporisateurs du rafraichissement des routes et les
temporisateurs d'expiration des routes. Dans ns2, chaque nœud est lié à un agent. L'agent peut
manipuler des événements et envoyez/recevez des paquets [33].
L'en-tête du paquet ODMRP est défini comme un emballage pour les deux paquets Join
Query et Join Reply. Ce concept suit la convention de programmation de ns2, où chaque
protocole est défini avec un en-tête simple du paquet. L'en-tête du paquet ODMRP est défini
dans la classe hdr odmrp.
class hdr_odmrp {
private:
int valid_ack_;
odmrpaddr_t mcastgroup_addr_;
odmrpaddr_t prev_hop_addr_;
84
Chapitre V: Simulations et résultats
Métriques de performance
Les paramètres mesurés dans une évaluation dépendent de la stratégie de routage appliquée,
notre simulation doit être en mesure d'évaluer :
- Le nombre de nœuds relayeurs: le nombre total des nœuds relayeurs dans le réseau.
- Le délai moyen du transfert d’un paquet de données: c’est le délai moyen pris par un
paquet de donnée pour transiter d’une application à une autre. Il permet de nous renseigner
sur la durée moyenne nécessaire pour transmettre un paquet de donnée de bout en bout.
- La perte des paquets: le nombre des paquets émis par la source et non reçus par le
destinataire.
Paramètre Valeur
Temps de simulation 100 s
Taille de la topologie 1200x800 m
Nombre de nœuds 7,15, 20,50,70 et 100
Nombre de sources 1 et 2
Taille du paquet 64 et 512 octet
Type du trafic CBR
Intervalle de transmission 0.25 et 0.05
Avec : CBR : Le trafic UDP est de type CBR (Constant Bit Rate).
85
Chapitre V: Simulations et résultats
La figure V.2 montre le nombre des nœuds relayeurs générés par le protocole ODMRP et
OODMRP, nous observons qu’OODMRP a réduit significativement le nombre des nœuds
relayeurs de 66% pour un réseau de 7 nœuds jusqu’à 78% pour un réseau de 100 nœuds par
rapport à ODMRP. Nous remarquons que la réduction augmente avec la croissance de la taille
du réseau.
60
Le nombre de nœuds
50
40
relayeurs
30
20 ODMRP
10 OODMRP
0
0 20 40 60 80 100 120
Taille du réseau
Nous avons vu précédemment qu’OODMRP réduit le nombre des nœuds relayeurs. Par
conséquent, il génère moins de paquets retransmis sur le réseau et moins de traitement au
niveau des nœuds (fig. V.3).
4000
Le nombre de paquets
3000
expédiés
2000
ODMRP
1000
OODMRP
0
0 20 40 60 80 100 120
Taille du réseau
86
Chapitre V: Simulations et résultats
La figure V.4 montre les résultats des simulations dans le cas de plusieurs récepteurs, nous
observons qu’OODMRP a réduit également le nombre des nœuds relayeurs de 66% pour un
réseau de 7 nœuds jusqu’à 76% pour un réseau de 100 nœuds par rapport à ODMRP. Dans le
cas de plusieurs récepteurs le nombre de nœuds relayeurs augmente légèrement par rapport à
un seul récepteur, par exemple pour un réseau de 20 nœuds avec un seul récepteur nous avons
9 nœuds relayeurs pour ODMRP et 4 pour OODMRP, dans le cas de plusieurs récepteurs
nous avons 13 nœuds relayeurs pour ODMRP et 6 pour OODMRP, cette augmentation est
relative au nombre croissant des récepteurs sur le réseau.
100
Le nombre de nœuds
80
60
relayeurs
40 ODMRP
20
OODMRP
0
0 20 40 60 80 100 120
Taille du réseau
La figure V.5 montre qu’OODMRP réduit le nombre de paquets transmis sur le réseau dans le
cas de plusieurs récepteurs suite à la réduction du nombre de nœuds relayeurs.
8000
Le nombre de paquets
6000
expédiés
4000
ODMRP
2000
OODMRP
0
0 20 40 60 80 100 120
Taille du réseau
3. Le délai moyen
La figure V.6, montre qu’il n’y a pas une grande différence entre le délai du protocole
ODMRP et OODMRP, malgré que le but principal d’ODMRP est de réduire le délai par tous
les moyens, ce qui génère un grand nombre de nœuds relayeurs.
87
Chapitre V: Simulations et résultats
0,015000
0,005000 ODMRP
OODMRP
0,000000
0 20 40 60 80 100 120
Taille du réseau
Dans cette section nous allons présenter le comportement du délai dans le cas de deux sources
émettrices sous différents scénarios.
La figure suivante illustre le délai moyen généré dans le cas de deux sources transmettant des
paquets de 64 octets. Nous constatons qu’il y a une légère différance entre le délai moyen
généré par le protocole ODMRP et celui généré par OODMRP.
0,015000
Le délai moyen (sec)
0,010000 ODMRP
OODMRP
0,005000
0,000000
Dans cette section nous allons présenter le comportement du délai dans le cas de deux sources
émettrices et en augmentant la charge du trafic, avec un intervalle de transmission de 0.25 et
de 0.05.
La figure V.8, montre que le délai moyen généré par notre protocole OODMRP réalise une
diminution de 14% par rapport au délai généré par ODMRP en transmettant des paquets de
512 octets.
88
Chapitre V: Simulations et résultats
0,025
0,08
Le délai moyen (sec)
0,06
ODMRP
0,04 OODMRP
0,02
La charge du réseau est donc partagée sur les nœuds ce qui préserve la bande passante et
réduit la congestion du réseau et ainsi la perte des paquets.
Dans cette section nous allons calculer l’énergie totale consommée sur le réseau, l’énergie
moyenne et l’écart type.
89
Chapitre V: Simulations et résultats
a) Energie totale
Nous remarquons dans la figure suivante la diminution des la consommation d’énergie sur le
réseau pour le protocole OODMRP. Cela peut être expliqué par la réduction du nombre de
nœuds relayeurs et ainsi le nombre de paquets expédiés. OODMRP réalise une réduction de
24% à 32% par rapport à ODMRP.
4E+10
Énergie totale
3E+10
( nj/bit)
2E+10
ODMRP
1E+10
OODMRP
0
0 20 40 60 80 100 120
Taille du réseau
b) Énergie moyenne
La figure suivante illustre la différence d’énergie moyenne entre OODMRP et ODMRP, nous
remarquons que l’énergie moyenne d’OODMRP est inférieure à celle d’ODMRP dans les 6
cas.
8,00E+08
Énergie moyenne(nj/bit)
6,00E+08
4,00E+08
ODMRP
2,00E+08
OODMRP
0,00E+00
0 20 40 60 80 100 120
Taille du réseau
c) Ecart type
Comme c’est montré dans (fig. V.12), l’écart type de l’énergie consommée d’OODMRP est
supérieur à celui d’ODMRP. OODMRP sollicite les mêmes nœuds plus souvent, ODMRP
répartit plus la charge du trafic sur plus de nœuds.
90
Chapitre V: Simulations et résultats
8,00E+08
6,00E+08
Ecart type
4,00E+08
2,00E+08 ODMRP
0,00E+00 OODMRP
0 20 40 60 80 100 120
Taille du réseau
La perte moyenne des paquets avec OODMRP est inférieure à celle d’ODMRP. OODMRP
réalise une réduction de 4% jusqu' à 14% qu'ODMRP. Cette réduction de perte des paquets
augmente avec l’accroissement de la charge du trafic. Ce la peut être expliqué par le fait
qu’OODMRP minimise le nombre des paquets expédiés ce qui réduit la congestion du réseau
et ainsi la perte des paquets.
800
La perte moyenne des
600
400
paquets
200 ODMRP
0 OODMRP
4096 32768 163840
6. Le débit moyen
Nous remarquons qu’il n’y a pas une différence importante entre le débit moyen d’OODMRP
et celui d’ODMRP (fig. V.14). L’amélioration des performances vue précédemment n’a pas
dégradé le débit moyen.
2500
Le débit moyen
2000
(bit/sec)
1500
1000
ODMRP
500
0 OODMRP
0 20 40 60 80 100 120
Taille du réseau
V.6 Conclusion
Nous avons présenté dans un premier lieu la conception et le développement du protocole
ODMRP, un protocole multicast pour les réseaux sans fil. Dans un second lieu, nous avons
présenté notre protocole proposé OODMRP, vise à préserver les ressources limitées du réseau
en réduisant le nombre des nœuds relayeurs et ainsi la charge du réseau.
Les résultats de simulation indiquent que notre protocole OODMRP réduit d’une façon
considérable le nombre des nœuds relayeurs, ainsi que le nombre des paquets expédiés sur le
réseau tout en construisant un arbre efficace de multicast. Nous avons constaté aussi que le
délai moyen d’OODMRP résiste à l’augmentation de la charge du réseau contrairement à
ODMRP.
92
Conclusion générale et perspectives
Le routage multicast dans les réseaux sans fil est une thématique complexe étant donné les
propriétés particulières de ce type de réseaux et ses ressources limitées. Les protocoles de
routage proactifs ou réactifs essaient de s'adapter aux contraintes imposées par ce type de
réseaux, et cela en proposant une méthode qui soit de moindre coût en capacités et ressources.
Le multicast constitue une application parmi le spectre d’applications que peut prendre en
charge un réseau sans fil. Par conséquent, la stratégie de conception d’un nouveau protocole
de routage doit tenir compte de tous les facteurs et limitations physiques imposés par
l'environnement afin que la fonctionnalité «routage» ne dégrade pas les performances du
système.
La conception d’un protocole de routage, qui fait l’objet de ce présent travail, a été guidée par
une nécessité d’économiser le nombre de nœuds relayeurs et par conséquent le nombre de
paquets expédiés afin de garantir une meilleure utilisation des ressources.
La solution proposée a été entièrement simulée sous NS2 afin d’évaluer les performances de
notre protocole par une confrontation des résultats obtenus avec celles du protocole d’origine
sous les mêmes conditions de simulation.
Les résultats obtenus démontrent globalement que notre protocole parvient à faire diminuer de
manière considérable le nombre de nœuds relayeurs et le nombre de paquets transférés, ce qui
permet de réduire la charge du réseau et contribue à la diminution du délai de bout en bout.
Notre travail offre plusieurs vois d’exploration pour des travaux futurs. En ce qui concerne
l’amélioration de notre protocole, nous proposons :
Un deuxième aspect qui peut être amélioré consiste à prendre en considération l’interaction
entre la couche MAC et la couche réseau et son effet sur la performance du protocole de
routage. En effet, une connaissance précise et actualisée de l’environnement contexte dans
lequel évoluent les terminaux mobiles permet d’utiliser de manière plus rationnelle les
ressources disponibles. Nous pouvons proposer également comme perspective, l’équilibrage
de la charge sur les différents chemins que peut emprunter un paquet de multicast dans un
réseau sans fil.
93
Conclusion générale et perspectives
Enfin, le présent travail peut être enrichi par l’ajout de la fonctionnalité de sécurité. Cet aspect
très important représente la méthode employée pour la gestion des clés de cryptage de
données entre la source et les nœuds du groupe multicast. Sa mise en place devrait se faire en
parallèle du processus de gestion de routage au sein du réseau. L’idée est donc, d’implémenter
un algorithme de calcul de ces clés dans la table de routage multicast de chaque nœud de
façon a attribué pour chacun une clé unique de cryptage de données transmis par la source.
94
Bibliographie
Bibliographie
[1] J. Anzevui. Les réseaux sans fil. Projet de semestre. Université de Genève, 2006-2007.
[2] F. Di Gallo. Wifi l’essentiel qu’il faut savoir…. Extraits de source diverses récoltées en
2003.
[3] T. Lemlouma. Le Routage dans les Réseaux Mobiles Ad Hoc. Thèse de magister,
Université des Sciences et de la Technologie Houari Boumèdiene, Institut
d'Informatique, 2000.
[4] M. Bezahaf, P. E. Le Roux, M. Dias de Amorim, S. Fdida, L. Iannone. Open Issues in
Wireless Mesh Networks. Université Pierre et Marie Curie, Laboratoire LIP6 /CNRS
– France, IP Networking Lab (INL) – Belgium.
[5] I. F. Akyildiz, X. Wang, W. Wang. Wireless mesh networks: a survey. Broadband and
Wireless Networking (BWN) Lab, School of Electrical and Computer Engineering,
Georgia Institute of Technology, Atlanta, GA 30332, USA, Kiyon, Inc, 4225 Executive
Square, Suite 290, La Jolla, CA 92037, USA, 2005.
[6] B. Hilt, A. Kaiser. Le routage multicast. Rapport de recherche. Université de Haute
Alsace, Département R&T et MIPS Colmar, France.
[7] D. Minoli. Ip multicast with applications to IPTV and mobile dvb-h. Copyright 2008
John Wiley & Sons, Inc. Pages 26–60.
[8] B. Cousin. Le multicast. IFSIC - Université Rennes I, 2007.
[9] B. Cousin. Les protocoles de routage multicast. IFSIC - Université de Rennes I, 2007.
[10] E. Royer, C. E. Perkins. Multicast operation of the ad-hoc on-demand distance Vector
routing protocol. Proc. Of the 5th ACM/IEEE Annual Conf. On Mobile Computing and
Networking, 1999.
[11] E. Cheng. On-demand multicast routing in mobile ad hoc networks, M.Eng. Thèse,
Carleton University, Département des systèmes informatiques, 2001.
[12] A. Zebdi. DZ-MAODV : nouveau protocole de routage multicast pour les réseaux ad
hoc mobiles basé sur les zones denses. L’université du Québec à Trois- Rivières, 2006.
[13] J. Garcia-Luna-Aceves, E. Madruga. The core assisted mesh protocol. IEEE Journal on
Selected Areas in Communications, 1999.
[14] S. J. Lee, W. Su, and M. Gerla. On-Demand Multicast Routing Protocol (ODMRP) for
Ad Hoc Network. IETF Internet Draft. July 2000.
[15] Anne Benoit. Réseaux sans fil. Notes de cours (ENS Lyon, M1), 2006.
[16] H. Moustafa. Routage unicast et multicast dans les réseaux mobiles ad hoc. Thèse de
doctorat de l’Ecole Nationale Supérieure des Télécommunications, Informatique et
Réseaux, 2004.
[17] L. Zhao, A. Al-Dubai , X. Liu. A new multicast routing algorithm for the Wireless Mesh
Networks. School of Computing, Napier University10 Clinton Road, Edinburgh EH10
5DT, UK, 2008.
95
Bibliographie
[18] G. Zeng, B. Wang, Y. Ding, L. Xiao, M. Mutka. Multicast Algorithms for Multi-
Channel Wireless Mesh Networks. Department of Computer Science and Engineering
Michigan State University, in Network Protocols, ICNP 2007, pp. 1-10.
[19] G. Chelius, E. Fleury. Critères d’évaluation d’arbres multicast ad hoc. Rapport de
recherche. CITI INSA de Lyon – ARES INRIA Rhône-Alpes.
[20] E. M. Royer, C. E. Perkins. Multicast Operation of the Ad-hoc On-Demand Distance
Vector Routing Protocol. Proceeding of ACM MOBICOM 1999, pp. 207-218, August,
1999.
[21] S. Ho Bae, S. Lee, W. Su, M. Gerla. The Design, Implementation, and Performance
Evaluation of the On-Demand Multicast Routing Protocol in Multihop Wireless
Networks. In IEEE Network Magazine, volume 14, pages 70–77, January 2000.
[22] S. Lee, M. Gerla, and C. Chain. On-Demand Multicast Routing Protocol - (ODMRP). In
Proc. Of the IEEE Wireless Communication and Networking Conference (WCNC),
September 1999.
[23] Monarch Research Group. Rice Monarch Project Software Distributions. Retrieved
March 01, 2006, from http://www.monarch.cs.cmu.edu/software.html.
[24] J.G. Jetcheva, D. B. Johnson. Adaptive Demand-Driven Multicast Routing in Multi-
hop Wireless Ad Hoc Networks. ACM mobihoc 2001, Long Beach, CA, USA, 2001.
[25] J. J. Garcia-Luna-Aceve, E. L. Madruga. The Core Assisted Mesh Protocol. IEEE
Journal on Selected Areas in Communications, Special Issue on Ad-Hoc Networks,vol.
17, no. 8, pages 1380 - 1394, August 1999.
[26] S. Roy, D. Koutsonikolas, S. Das, Y. C. Hu. High- throughput multicast routing metrics
in wireless mesh networks. School of Electrical and Computer Engineering, Purdue
University, West Lafayette, IN 47907, United States, 22 July 2007.
[27] K. Fellah. Techniques d’optimisation pour l’économie d’énergie dans les réseaux de
capteurs sans fil, thèse de magister, Université d’Oran, 2008.
[28] K. Fall, K. Vradhan, Oct. 1998.
Http://www-mash.cs.berkeley.edu/ns/nsdoc.ps.gz.
NS Notes and Documentation.
[29] M. Greis. Oct. 1998.
Http://titan.cs.uni-bonn.de/~greis/ns/ns.html
NS Tutorial.
[30] P. Anelli et E. Horlait. NS-2: Principes de conception et d'utilisation. UPMC - LIP6, 15
Septembre 1999.
[31] K. Fall, K. Varadhan. The ns Manual (formerly ns Notes and Documentation). The
VINT Project A Collaboration between researchers at UC Berkeley, LBL, USC/ISI, and
Xerox PARC, January 6, 2009.
[32] The VINT project. The network simulator (ns-2). Retrieved December 12, 2005, from
Http://www.isi.edu/nsnam/ns.
[33] L. Cheng. Lightweight Service Advertisement and Discovery in Mobile Ad hoc
Networks. Director, Laboratory Of Networking Group, Department of Computer
Science and Engineering, P.C. Rossin College of Engineering & Applied Science,
Lehigh University,April 22, 2005.
96
Annexe A : Exemple de scripte TCL
Annexe A
Exemple de scripte TCL
# ======================================================================
# Default Script Options
# ======================================================================
# ======================================================================
set AgentTrace ON
Simulator set AgentTrace_ ON
set RouterTrace ON
Simulator set RouterTrace_ ON
set MacTrace OFF
97
Annexe A : Exemple de scripte TCL
# ported: start
#LL set mindelay_ 25us
#LL set maxdelay_ 50us
# ported: end
# ported: start
# These binary variables indicate whether or not DROP CMU Trace
# objects will log all 'drop' events or not. If they are configured
# not to log all drops, then the only events that are logged are
# DROP_END_OF_SIMULATION events. This option is provide so that,
# for example, when "MacTrace" is turned OFF (see above), end
# of simluation drops still get written to the trace file.
#
# ======================================================================
# Parameters for the "Managers" to determine what gets logged when...
# ======================================================================
98
Annexe A : Exemple de scripte TCL
# ======================================================================
# ======================================================================
# ported: end
# jj: not sure how this physical model compares to the one used in the
original
# monarch extensions -- need to check the code...
# Initialize the SharedMedia interface with parameters to make
# it work like the 914MHz Lucent WaveLAN DSSS radio interface
Phy/WirelessPhy set CPThresh_ 10.0
Phy/WirelessPhy set CSThresh_ 1.559e-11
Phy/WirelessPhy set RXThresh_ 3.652e-10
Phy/WirelessPhy set Rb_ 2*1e6
Phy/WirelessPhy set Pt_ 0.2818
Phy/WirelessPhy set freq_ 914e+6
Phy/WirelessPhy set L_ 1.0
# ======================================================================
99
Annexe A : Exemple de scripte TCL
if { $tracefd == "" } {
return ""
}
set T [new CMUTrace/$ttype $atype]
$T target [$ns_ set nullAgent_]
$T attach $tracefd
$T set src_ [$node id]
$T node $node
return $T
}
proc stop {} {
global ns_ f nf
$ns_ flush-trace
close $f
close $nf
}
100
Annexe A : Exemple de scripte TCL
proc log-movement {} {
global logtimer ns_ ns
set ns $ns_
source ../mobility/timer.tcl
Class LogTimer -superclass Timer
LogTimer instproc timeout {} {
global opt node_;
for {set i 0} {$i < $opt(nn)} {incr i} {
$node_($i) log-movement
}
$self sched 0.1
}
# ======================================================================
# Main Program
# ======================================================================
getopt $argc $argv
# ported: start
if { $opt(em) == "" } {
puts "*** no errormodel specified."
set opt(errmodel) "none"
} else {
source $opt(em)
}
# ported: end
#
# Source External TCL Scripts
#
source tcl/lib/ns-mobilenode.tcl
# ported: start
if { $opt(rp) != "" } {
source $opt(rp)/$opt(rp).tcl
} elseif { [catch { set env(NS_PROTO_SCRIPT) } ] == 1 } {
puts "\nenvironment variable NS_PROTO_SCRIPT not set AND"
puts "no -rp option provided!\n"
usage $argv0
exit 1
} else {
puts "\n*** using script $env(NS_PROTO_SCRIPT)\n\n";
source $env(NS_PROTO_SCRIPT)
}
101
Annexe A : Exemple de scripte TCL
source tcl/lib/ns-cmutrace.tcl
if { $opt(is) != "" } {
source interference_agent/interference.tcl
}
# if { $configured_bitrate > 0 } {
# puts "*** adjusting configured bitrate ==> $configured_bitrate"
# puts "THIS WILL ONLY WORK FOR NetIf/SharedMedia!!!\n\n"
# NetIf/SharedMedia set Rb_ $configured_bitrate
# }
# if { $configured_range > 0 } {
# puts "*** adjusting configured range ==> $configured_range"
# puts "THIS WILL ONLY WORK FOR NetIf/SharedMedia!!!\n\n"
# NetIf/SharedMedia set range_rx_ $configured_range
# NetIf/SharedMedia set range_cs_ [expr 2 * $configured_range + 10]
# }
# ported: end
# do the get opt again incase the routing protocol file added some more
# options to look for
getopt $argc $argv
if { $opt(x) == 0 || $opt(y) == 0 } {
usage $argv0
exit 1
}
if {$opt(seed) > 0} {
puts "Seeding Random number generator with $opt(seed)\n"
ns-random $opt(seed)
}
# ported: start
#
# Don't overwrite existing trace files
#
if { $opt(noclobber) != 0 && [file exists $opt(tr)] == 1 } {
puts "Trace file $opt(tr) already exists. EXITING...\n"
exit 1
}
# ported: end
#
# Initialize Global Variables
#
set ns_ [new Simulator]
102
Annexe A : Exemple de scripte TCL
# ported: start
#set macmgr_ [new Manager/Mac]
#set prqmgr_ [new Manager/PriQueue]
#set chnlmgr_ [new Manager/Channel]
#set netifmgr_ [new Manager/NetIf]
#set nodemgr_ [new Manager/Node]
# ported: end
#
# Create God
#
create-god $opt(nn)
#
# log the mobile nodes movements if desired
#
if { $opt(lm) == "on" } {
log-movement
}
#
# Create the specified number of nodes $opt(nn) and "attach" them
# the channel.
# Each routing protocol script is expected to have defined a proc
# create-mobile-node that builds a mobile node and inserts it into the
# array global $node_($i)
#
# 1 or 0???
}
}
if { $opt(uni) == "" } {
puts "*** NOTE: no power scaling scenario specified."
103
Annexe A : Exemple de scripte TCL
#
# Source the Connection and Movement scripts
#
if { $opt(cp) == "" } {
puts "*** NOTE: no connection pattern specified."
set opt(cp) "none"
} else {
puts "Loading connection pattern..."
source $opt(cp)
}
#
# Tell all the nodes when the simulation ends
#
for {set i 0} {$i < $opt(nn) } {incr i} {
$ns_ at $opt(stop).000000001 "$node_($i) reset";
}
$ns_ at $opt(stop).1 "puts \"NS EXITING...\" ; $ns_ halt"
$ns_ at $opt(stop) "stop"
if { $opt(sc) == "" } {
puts "*** NOTE: no scenario file specified."
set opt(sc) "none"
} else {
puts "Loading scenario file..."
source $opt(sc)
puts "Load complete..."
}
104
Annexe A : Exemple de scripte TCL
# ported: start
# ======================================================================
# Start the Managers
# ======================================================================
#$ns_ at 0.001 "$macmgr_ start"
#$ns_ at $opt(stop).000000001 "$macmgr_ reset"
if { $opt(mg) == "" } {
puts "*** NOTE: no multicast group scenario specified"
set opt(mg) "none"
} else {
puts "Loading multicast info file..."
source $opt(mg)
puts "Loading multicast info file... done."
}
if { $opt(is) == "" } {
puts "*** NOTE: no interference scenario specified"
set opt(is) "none"
} else {
puts "Loading interference info file..."
source $opt(is)
# ======================================================================
# Schedule status/information events
# ======================================================================
#
# Have the simulator display periodic progress messages
#
for {set i 1} {$i <= $opt(progress)} {incr i} {
set t [expr $i * $opt(stop) / ($opt(progress) + 1)]
$ns_ at $t "puts \"completed through $t secs...\""
}
# ported: end
105
Annexe A : Exemple de scripte TCL
106
Annexe B : Exemple de scripte AWK
Annexe B
Exemple de script AWK
Le langage AWK
Awk2 est un langage de programmation qui tire son nom des trois programmeurs qui l'ont
développé : Alfred V. Aho, Peter J. Weinberger et Brian W. Kernighan. Le langage awk est
très efficace dans la gestion de fichiers avec récupération d'informations et transformation des
données. Il permet :
- la manipulation de fichiers texte en tous genres
- le support de petites bases de données au format personnel
- la génération de rapports
- la validation/les tests de données
- la production d'index et la conversion de documents
#! /bin/awk -f
BEGIN {
idHighestPacket = 0 ; idLowestPacket = 10000 ;
nSentPackets = 0 ;
nReceivedPackets36 = 0 ;
nReceivedPackets11 = 0 ;
nReceivedPackets37 = 0 ;
nReceivedPackets21 = 0 ;
join36 = 0;
join11 = 0;
join37 = 0;
join21 = 0;
{
strEvent = $1 ; rTime = $2 ; node = $3;
strAgt = $4 ; idPacket = $6 ;
strType = $7 ; nBytes = $8 ;
2
http://www.faqs.org/faqs/computer-lang/awk/faq /index.html
107
Annexe B : Exemple de scripte AWK
}
if (strEvent == "r" && node == "_36_") {
nReceivedPackets36 += 1 ;
nReceivedBytes36 += nBytes ;
rReceivedTime36[ idPacket ] = rTime ;
if(rSentTime[ idPacket ]!=0){
rDelay36[ idPacket ] = rReceivedTime36[ idPacket ] - rSentTime[
idPacket ] ;}
}
108
Annexe B : Exemple de scripte AWK
}
}
}
END {
109
Résumé : ODMRP (On-Demand Multicast Routing Protocol) est un protocole de multicast très
répandu pour les réseaux ad hoc sans fil. Les forces d'ODMRP sont sa simplicité, son taux
élevé d’acheminement réussi de paquet, et sa non-dépendance sur un protocole spécifique
d'unicast.
Cette thèse propose un protocole sans fil de multicast basé sur ODMRP nommé OODMRP
(Optimized On-Demand Multicast Routing Protocol) qui minimise le nombre des nœuds
relayeurs et optimise la consommation des ressources radio et des ressources énergétique dans
le réseau.
Avant de choisir un nœud relayeurs, chaque nœud cherche dans son voisinage l'existence
préalable d'un nœud relayeur. Dans le cas où ce nœud relayeur existe il selecte ce nœud comme
un ascendant.
Mots clé : Multicast, Routage, Réseau Maillé Sans fil, ODMRP, OODMRP
Indeed, before selecting a forwarding node, each node searches in its neighborhood the
existence of a forwarding node. In this case, it selects this node as an ascending one.
Our simulation results show that OODMRP reduces dramatically the number of forwarding
nodes and forwarded packets, compared to original ODMRP.