Embed Size (px)
Citation preview
Année Universitaire : 2012/2013
UNIVERSITE D’ANTANANARIVO
----------------------- ECOLE SUPERIEURE POLYTECHNIQUE
----------------------- DEPARTEMENT TELECOMMUNICATION
MEMOIRE DE FIN D’ETUDES
En vue de l’obtention
Du DIPLOME de LICENCE ès SCIENCES TECHNIQUE
Spécialité :Télécommunication
Par : ANDRIANAVALONA Hajaniaina
ETUDE COMPARATIVE ET METHODE DE CHOIX DES PROTOCOLES DE ROUTAGE DANS UN
RESEAU MOBILE AD HOC
Soutenu le 06 février 2015 devant la commission d’Examen composée de :
Président :
Dr. RAKOTOMALALA Mamy Alain
Examinateurs :
M. ANDRIAMIASY Zidora
M. RASAMOELINA Jacques Nirina
M. BOTO ANDRIANANDRASANA Jean Espérant
Directeur de mémoire :
M. RASOLOMANANA Jean Fanomezantsoa
REMERCIEMENTS
La rédaction de cet ouvrage représente l’accomplissement de trois années de labeurs et de travail à
Vontovorona. Je tiens avant tout à remercier notre Seigneur, qui par sa grâce, a permis la
réalisation de ce mémoire. Je tiens à exprimer toute ma reconnaissance à ceux qui, de près ou de
loin ont contribué à son élaboration. Aussi, je remercie respectueusement :
Monsieur ANDRIANARY Philippe Antoine, Professeur Titulaire, Directeur de l’Ecole Supérieure
Polytechnique d’Antananarivo de m’avoir accueilli au sein de son établissement.
Monsieur RAKOTOMALALA MamyAlain, Maître de conférences, Enseignant Chercheur à
l’ESPA, Chef de Département Télécommunication, pour tous les savoirs qu’il nous a transmis et
d’avoir fait l’honneur de présider le jury de ce mémoire.
Monsieur RASOLOMANANA Jean Fanomezantsoa, Enseignant Chercheur à l’ESPA au sein du
Département Télécommunication, mon Directeur de mémoire, pour son aide, son soutien, sa
sympathie, sa pédagogie et surtout le temps qu’il a consacré pour moi tout au long de la réalisation
de ce mémoire.
Tous les membres du Jury, à savoir :
Monsieur ANDRIAMIASY Zidora, Maître de conférences, Enseignant Chercheur à l’ESPA ;
Monsieur RASAMOELINA Jacques Nirina, Enseignant Chercheur à l’ESPA ;
Monsieur BOTO ANDRIANANDRASANA Jean Espérant, Enseignant Chercheur à l’ESPA.
Qui ont eu l’amabilité d’examiner ce mémoire malgré leurs nombreuses occupations.
Mes vifs remerciements à tous les enseignants et les personnels administratifs de l’ESPA.
Je n’oublierai pas ma famille et mes amis que mes camarades de classe pour leurs encouragements
etleurs soutiens bienveillants.
Et un grand merci à ma mère, mes tantes et mes sœurs pour tous leurs aides et leurs soutiens
durant ces longues années d’étude afin que je puisse arriver à ce niveau
TABLE DES MATIERES
REMERCIEMENTS ................................................................................................................................. i
TABLE DES MATIERES .......................................................................................................................... ii
LISTE DES ABREVIATIONS ...................................................................................................................... v
INTRODUCTION GENERALE .................................................................................................................. 1
Chapitre 1 INTRODUCTION AU RESEAU MOBILE AD HOC ..................................................................... 3
1.1 Introduction ......................................................................................................................... 3
1.2 Les réseaux sans fils .............................................................................................................. 3
1.2.1 Définition d’un réseau sans fil ........................................................................................ 3
1.2.2 Les catégories de réseaux sans fils ................................................................................. 4
1.2.3 Les architectures des réseaux sans fils ............................................................................ 6
1.3 Présentation de WiFi (802.11) ............................................................................................... 7
1.3.1 Introduction .................................................................................................................. 7
1.3.2 Historique ..................................................................................................................... 7
1.3.3 Description de la norme 802.11 ...................................................................................... 8
1.3.4 Les équipements Wifi .................................................................................................... 9
1.3.5 Mode de fonctionnement du Wifi.................................................................................. 11
1.4 Les réseaux mobiles Ad hoc ................................................................................................. 12
1.4.1 Définition ..................................................................................................................... 12
1.4.2 Les applications des réseaux mobiles ad hoc ................................................................. 14
1.4.3 Les caractéristiques des réseaux ad hoc ........................................................................ 15
1.4.4 Principes de fonctionnement d’un réseau mobile ad hoc ................................................ 16
1.5 Conclusion ........................................................................................................................... 20
Chapitre 2 ROUTAGE DANS LE RESEAU AD HOC .................................................................................. 21
2.1 Introduction ........................................................................................................................ 21
2.2 Routage............................................................................................................................... 21
2.2.1 Définition ..................................................................................................................... 21
2.3 Classification des protocoles de routage ............................................................................... 22
2.3.1 Caractéristiques des algorithmes de routage : ............................................................... 23
2.3.2 Protocole proactifs ....................................................................................................... 24
2.3.3 Protocoles réactifs ........................................................................................................ 24
2.3.4 Protocole hybrides ........................................................................................................ 25
2.4 Conclusion ........................................................................................................................... 27
Chapitre 3 ETUDE COMPARATIVE DES PROTOCOLES DE ROUTAGE AODV DSR et DSDV DANS LE RESEAU
AD HOC .............................................................................................................................................. 28
3.1 Introduction ........................................................................................................................ 28
3.2 Présentation du protocole de routage AODV « Ad hoc On demand Distance Vector» ............ 28
3.2.1 Définition ..................................................................................................................... 28
3.2.2 Le type des messages dans AODV ................................................................................. 29
3.2.3 Le principe de numéro de séquence : ............................................................................. 30
3.2.4 Fonctionnement de protocole : ..................................................................................... 30
3.2.5 Avantages et Inconvénients : ........................................................................................ 33
3.3 Le protocole DSR « Dynamic Source Routing»....................................................................... 33
3.3.1 Définition ..................................................................................................................... 33
3.3.2 Principe ........................................................................................................................ 34
3.3.3 Fonctionnement de protocole ....................................................................................... 34
3.3.4 Avantages et inconvénients .......................................................................................... 37
3.4 Le protocole DSDV « Destination Sequenced Distance Vector » ............................................ 37
3.4.1 Définition ..................................................................................................................... 37
3.4.2 Fonctionnement de protocole ....................................................................................... 37
3.4.3 Avantages et inconvénients .......................................................................................... 38
3.5 Conclusion ........................................................................................................................... 39
Chapitre 4 METHODE DE CHOIX DES PROTOCOLES DE ROUTAGE DANS LE RESEAU AD HOC .................. 40
4.1 Introduction ........................................................................................................................ 40
4.2 Les applications du réseau mobiles Ad hoc ........................................................................... 40
4.3 Les contraintes de routage dans les réseaux ad hoc .............................................................. 41
4.4 La difficulté du routage dans les réseaux ad hoc ................................................................... 41
4.5 Méthode de choix de protocole de routage .......................................................................... 43
4.5.1 Les cas que l’on peut rencontrer dans un milieu ad hoc .................................................. 43
4.5.2 Les métriques d’évaluation ........................................................................................... 45
4.6 Conclusion ........................................................................................................................... 46
CHAPITRE 5 SIMULATION ET EVALUATION DES PERFORMANCES ......................................................... 47
5.1 Introduction ........................................................................................................................ 47
5.2 Environnement de simulation .............................................................................................. 47
5.3 Le simulateur NS2 ................................................................................................................ 47
5.3.1 Motivations de l’utilisation de ns2 ................................................................................ 47
5.3.2 Présentation de NS2 ..................................................................................................... 48
5.3.3 Le processus de simulation ........................................................................................... 49
5.4 Simulation ........................................................................................................................... 50
5.4.1 Métriques évaluées ...................................................................................................... 50
5.4.2 Paramètres de simulation ............................................................................................. 51
5.4.3 Les protocoles simulés .................................................................................................. 52
5.4.4 Les scénarios de simulation ........................................................................................... 53
5.5 Interprétation des résultats ................................................................................................. 56
5.5.1 Nombre des Paquets de contrôle .................................................................................. 56
5.5.2 Taux de perte des paquets ............................................................................................ 60
5.5.3 Taux de paquet délivré ................................................................................................. 63
5.5.4 Délai de bout en bout (EED End to End Delay) ................................................................ 66
5.6 Conclusion ........................................................................................................................... 69
CONCLUSION GENERALE ..................................................................................................................... 71
BIBLIOGRAPHIE .................................................................................................................................. 72
LISTE DES ABREVIATIONS
2D 2 Dimensions
3D 3 Dimensions
ABR Associativity Based Routing
ACM International Symposium on Mobile Ad Hoc Networking and Computing,
ADSL ADSL
ALOHA A Long-term Oligotrophic Habitat Assessment
AODV Ad hoc On demand Distance Vector
AP Point d’Accès
ATM Asynchronous Transfer Mode
AVG Average End to End Delay
BLR Boucle Locale Radio
BSS Basic Service Set
CBR Constant Bit Rate
CBRP Cluster Based Routing Protocol
CEDAR Core-Extraction Distributed Ad hoc Routing algorithm
CGSR Cluster-head Gateway Switch Routing
couche PHY couche PHYsique
CSMA1 Carrier Sense Multiple Access [1]
CTS Clear-To-Send
DARPA Defense Advanced Research Projects Agency
DBF Distribution de Bellman Ford
DECT Digital Enhanced Cordless Telecommunication
DP Dropped Packets
DREAM Distance Routing Effect Algorithm for Mobility
DSDV Destination Sequenced Distance Vector »
DSDV Destination Sequenced Distance Vector
DSR Dynamic Source Routing
DSR Dynamic Source Routing
DSSS Direct Sequence Spread Spectrum
EARP Energy-Aware Routing Protocol
EED End to End Delay
ESS Extended Service Set
ETSI European Telecommunications Standards Institute
FHSS Frequency Hopping Spread Spectrum
FSR Fisheye State Routing
FTP File Transfer Protocol
GPRS General Packet Radio Service
GSM Global System for Mobile Communication ou Groupe Spécial Mobile
GSR Global State Routing.
HomeRF Home Radio Frequency
HSR Hierarchical State Routing
HSR Hierarchical State Routing.
IFTE Improved Family of Test Equipment
IP Internet Protocole
IR Infra Rouge
irDA infrared data association
LLC Logical Link Control
LSR Link State Routing
MAC Media Access Control
MANET Mobile Ad hoc NETwork
NS2 Network Simulator – version 2
OLSR Optimized Link State Routing
OSI Open Systems Interconnection
PC Personnal Computer
PCI Peripheral Component Interconnect
PCMCIA Personal Computer Memory Card International Association
PDA Personal Digital Assistant
PDF Packet Delivery Fraction
PSP PlayStation Portable
RDMAR Relative Distance Microdiscovery Ad-Hoc Routing
RERR Route Error Message
RFC Request For Comment
RL Routing Load RL (ou Overhead de routage)
RREP Route Reply Message
RREQ Route Request Message.
RTS Request to Send
SI Information Sciences Institute
SN Sequence Number
TBRPF Topology dissemination Based on Reverse-Path Forwarding
TCP Transfert Control Protocol
TCP Transmission Control Protocol
UDP User Datagram Protocol
UMTS Universal Mobile Telecommunication System
USB Universal Serial Bus
VINT Virtual InterNetwork Testbed\
WECA Wireless Ethernet Compatibility Alliance
WIFI Wireless fidelity
Wimax Worldwide Interoperability for Microwave Access
WLAN Wireless Local Area Network
WMAN Wireless Metropolitan Area Network
WPAN Wireless Personal Area Network
WRP Wireless Routing Protocol
WWAN Wireless Wide Area Network
ZHLS Zone based Hierarchical Link State
ZHLS Zone Based Hierarchical
ZRP Zone Routinier Protocol
1
INTRODUCTION GENERALE
Ces dernières années, le développement de la technologie sans fil a ouvert de nouvelles
perspectives dans le domaine des télécommunications, les réseaux mobiles basés sur la
technologie sans fil connaissent aujourd'hui une forte expansion. Les réseaux mobiles offrent une
grande flexibilité d'emploi et permettent aux utilisateurs de se déplacer librement tout en
continuant normalement leurs communications et tout en accédant à des services à contraintes
temps réel en prenant en considération « la mobilité » de ces utilisateurs. Enfaite, il y a quelques
années, cette mobilité était inimaginable mais à l’heure actuelle elle est tout à fait réalisable grâce
à la technologie wifi (Wireless fidelity), une technologie standard d’accès sans fil des réseaux
locaux.
Le wifi rassemble la possibilité de rendre l’information partout, rapidement et sans contraintes
dans les réseaux mobiles. Il s’attache sur deux modes de fonctionnement : le mode infrastructure
et le mode Ad-hoc. Les réseaux mobiles avec infrastructure sont basés sur un ensemble de sites
fixes appelés stations de base, ces sites vont relier les différents nœuds mobiles pour former un
réseau interconnecté dont l'inconvénient de ce type de réseau est de requérir le déploiement d'une
importante infrastructure fixe. Les réseaux ad hoc en contrepartie n'ont besoin d'aucune
infrastructure fixe préexistante. En revanche, Un réseau ad hoc est constitué d'un ensemble
d'unités de calcul portables comme les PDA (Personal Digital Assistant) et les laptops munis d'une
interface de communications sans fil tout en déplaçant librement dans une certaine zone
géographique et forment un réseau interconnecté dynamiquement. Pour pouvoir communiquer
entre eux, chaque unité mobile doit jouer le rôle d’un routeur ou d’un terminal, et doit
retransmettre les paquets des autres unités mobiles. Face à l’autre mode de fonctionnement, les
réseaux ad hoc offrent une grande flexibilité d'emploi et une grande robustesse et peuvent se
déployer très rapidement et grâce à ces avantages nous allons consacrer notre étude sur les réseaux
ad-hoc tout au long de cet ouvrage.
Les recherches actuelles dans les réseaux ad-hoc sont dirigées vers l’algorithme de routage classé
en trois catégories : proactif, réactif et hybride. En effet à cause de la mobilité des nœuds, il est
très difficile de localiser une destination à un instant donné, les protocoles de routage conçus pour
des réseaux statiques sont donc inadaptés pour ce type de réseaux. Plusieurs protocoles de routage
pour les réseaux ad hoc ont été développés, chaque protocole essaye de maximiser les
performances du réseau en minimisant le délai de livraison des paquets, l'utilisation de la bande
2
passante et la consommation d'énergie : Les protocoles proactifs maintiennent à jour des tables de
routage qui indiquent les routes vers chaque destination du réseau, les routes sont donc calculées
même si elles ne sont pas utilisées. L'avantage de ces protocoles c'est que la connexion entre les
nœuds est immédiate puisque les routes sont calculées à l'avance, l'inconvénient c'est qu'ils
utilisent beaucoup de paquets de contrôle pour maintenir à jour les tables de routage. De son côté,
les protocoles réactifs en contrepartie calculent les routes selon les besoins, la route est calculée
quand elle est demandée, l'avantage de ces protocoles c'est qu'ils utilisent moins de paquets de
contrôle que les protocoles proactifs, l'inconvénient est qu'ils ont un délai initial avant de
commencer la transmission des données, c'est le délai nécessaire pour déterminer la route. Et
enfin, les protocoles hybrides ont pour fonction d’essayer la combinaison des deux approches
précédentes pour bénéficier de leurs avantages mais aussi de cumuler leurs inconvénients. Le
problème est donc de trouver un compromis et essayer d'avoir un délai initial court tout en
utilisant un minimum de paquets de contrôle.
Ce travail rentre donc dans le cadre de l'étude comparative des protocoles de routage dans les
réseaux mobiles ad hoc. L’analyse de cette étape conduit à un bilan des forces et faiblesses tout en
permettant de déterminer dans quelles situations chaque protocole est le plus adapté. L’algorithme
de routage consiste à assurer une stratégie qui garantit, à n’importe quel moment, la connexion
entre n’importe quelle paire de nœuds appartenant au réseau. Cette stratégie doit prendre en
considération les changements de la topologie du réseau, ainsi que d’autres caractéristiques
comme la bande passante, le nombre de liens, la limitation d’énergie, etc. Avec l’émergence de
ces dispositifs, de multiples recherches ont été menées notamment dans le domaine du routage
afin de développer plusieurs protocoles de routage.
Etant divisé en quatre chapitres, nous allons en premier lieu présenter un point de vue sur les
réseaux mobiles ad hoc, leurs caractéristiques ainsi que leurs applications.
Au deuxième chapitre, nous nous focaliserons sur la fonctionnalité du routage dans un réseau ad
hoc, les contraintes que le routage rencontre dans le réseau ad hoc et voire même les attaques et
vulnérabilité des protocoles de routage.
Aussi dans le chapitre suivant, nous allons présenter les différents protocoles de routage et leurs
avantages dans les réseaux ad hoc avec quelques inconvénients.
Et enfin, dans le dernier chapitre nous proposerons une simulation d’évaluation de performance
des protocoles implémentée sous Network Simulator 2 abrégé par NS2 tout en comparant ces
3
protocoles entre eux selon quelque paramètre en utilisant le simulateur du réseau NS2 afin de
présenter des résultats satisfaisants.
Chapitre 1
INTRODUCTION AU RESEAU MOBILE AD HOC
1.1 Introduction
Les technologies des réseaux locaux sans fil wifi se démocratisent notamment grâce aux offres
Internet grand public. De plus, ces technologies procurent un confort d’utilisation non-négligeable
aux utilisateurs et voire même les nomades en les offrant une extrême liberté d’usage et aussi en
assurant une continuité de service à la fois performante et économique via des terminaux fiables,
adaptés et relativement peu couteux. Et grâce à ces réseaux, un utilisateur aura 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 la "mobilité". Dans ce chapitre nous allons mettre
en lumière, un point de vue généralisé sur les réseaux sans fil en insistant dans la suite sur le
réseau local sans fils wifi normalisés IEEE 802.11 nous menant à s’intéresser aux réseaux mobiles
ad hoc plus particulièrement.
1.2 Les réseaux sans fils
1.2.1 Définition d’un réseau sans fil
Un réseau est dit sans fil [2], lorsque les machines participantes qui le composent ne sont pas
reliées entre elles par des câbles, mais utilisent, pour communiquer, le médium radio ou infrarouge
[3]. Ceci permet aux utilisateurs de se déplacer dans un périmètre de couverture pouvant aller
d’une dizaine de mètres à quelques kilomètres. Comme les signaux propagés sur ces médias
s’atténuent au fur et à mesure qu’ils s’éloignent de leur émetteur, un nœud ne peut pas
communiquer avec un autre s’il est situé trop loin de lui. On définit alors l’ensemble des voisins
d’un nœud comme étant l’ensemble des nœuds capables de recevoir et de comprendre les signaux
émis par celui-ci. Ces voisins sont appelés des voisins directs ou voisins à un saut. On définit de
même un voisin à deux sauts comme étant un Voisin à un saut d’un voisin direct, et ainsi de suite.
[4]
4
1.2.2 Les catégories de réseaux sans fils
On distingue habituellement plusieurs catégories de réseaux sans fils, selon le périmètre
géographique offrant une connectivité (appelé zone de couverture) : [1]
1.2.2.1 Réseaux personnels sans fils (WPAN)
Le réseau personnel sans fils (appelé également réseau individuel sans fils ou réseau domotique
sans fils et noté WPAN pour Wireless Personal Area Network) concerne les réseaux sans fils
d'une faible portée : de l'ordre de quelques dizaines mètres. Ce type de réseau sert généralement à
relier des périphériques (imprimante, téléphone portable, appareils domestiques, ...) ou un
assistant personnel (PDA) à un ordinateur sans liaison filaire ou bien à permettre la liaison sans
fils entre deux machines très peu distantes. Il existe plusieurs technologies utilisées pour les
WPAN :
� Bluetooth, lancée par Ericsson en 1994, proposant un débit théorique de 1Mbps pour une
portée maximale d'une trentaine de mètres, connue sous le nom IEEE 802.15.1, possède
l'avantage d'être très peu gourmand en énergie, ce qui le rend particulièrement adapté à une
utilisation au sein de petits périphériques.
� HomeRF (Home Radio Frequency),lancée en 1998 par le HomeRF Working Group
(formé notamment par les constructeurs Compaq, HP, Intel, Siemens, Motorola et
Microsoft) propose un débit théorique de 10 Mbps avec une portée d'environ 50 à 100
mètres sans amplificateur. La norme HomeRF soutenue notamment par Intel, a été
abandonnée en Janvier 2003
� La technologie ZigBee, aussi connue sous le nom IEEE 802.15.4 permet d'obtenir des
liaisons sans fil à très bas prix et avec une très faible consommation d'énergie, ce qui la
rend particulièrement adaptée pour être directement intégré dans de petits appareils
électroniques (appareils électroménagers, hifi, jouets, ...).
� Enfin les liaisons infrarouges permettent de créer des liaisons sans fils de quelques mètres
avec des débits pouvant monter à quelques mégabits par seconde. Cette technologie est
largement utilisée pour la domotique (télécommandes) mais souffre toutefois des
perturbations dûes aux interférences lumineuses. L'association irDA (infrared data
association) formée en 1995 regroupe plus de 150 membres.
5
1.2.2.2 Réseaux locaux sans fils (WLAN)
Le réseau local sans fils (WLAN pour Wireless Local Area Network) est un réseau permettant de
couvrir l'équivalent d'un réseau local d'entreprise, soit une portée d'environ une centaine de
mètres. Il permet de relier entre-eux les terminaux présents dans la zone de couverture. Il existe
plusieurs technologies concurrentes :
� Le WiFi (ou IEEE 802.11), soutenu par l'alliance WECA (Wireless Ethernet Compatibility
Alliance) offre des débits allant jusqu'à 54Mbps sur une distance de plusieurs centaines de
mètres.
� hiperLAN2 (HIgh Performance Radio LAN 2.0), norme européenne élaborée par l'ETSI
(European Telecommunications Standards Institute), permet d'obtenir un débit théorique
de 54 Mbps sur une zone d'une centaine de mètres dans la gamme de fréquence comprise
entre 5 150 et 5 300 MHz.
� DECT (Digital Enhanced Cordless Telecommunication), norme des téléphones sans fils
domestiques. Alcatel et Ascom développent pour les environnements industriels, telles les
centrales nucléaires, une solution basée sur cette norme qui limite les interférences. Les
points d'accès résistent à la poussière et à l'eau. Ils peuvent surveiller les systèmes de
sécurité 24/24h et se connecter directement au réseau téléphonique pour avertir le
responsable en cas de problème.
1.2.2.3 Réseaux métropolitains sans fils (WMAN)
Le réseau métropolitain sans fils (WMAN pour Wireless Metropolitan Area Network) est connu
sous le nom de Boucle Locale Radio (BLR). Les WMAN sont basés sur la norme IEEE 802.16. La
boucle locale radio offre un débit utile de 1 à 10 Mbit/s pour une portée de 4 à 10 kilomètres, ce
qui destine principalement cette technologie aux opérateurs de télécommunication.
1.2.2.4 Réseaux étendus sans fils (WWAN)
Le réseau étendu sans fils (WWAN pour Wireless Wide Area Network) est également connu sous
le nom de réseau cellulaire mobile. Il s'agit des réseaux sans fils les plus répandus puisque tous les
téléphones mobiles sont connecté à un réseau étendu sans fils. Les principales technologies sont
les suivantes :
� GSM (Global System for Mobile Communication ou Groupe Spécial Mobile)
� GPRS (General Packet Radio Service)
6
� UMTS (Universal Mobile Telecommunication System)
� Wimax(standard de réseau sans fils poussé par Intel avec Nokia, Fujitsu et Prowim). Basé
sur une bande de fréquence de 2 à 11 GHz, offrant un débit maximum de 70 Mbits/s sur
50km de portée, certains le placent en concurrent de l'UMTS, même si ce dernier est
davantage destiné aux utilisateurs itinérants.
1.2.3 Les architectures des réseaux sans fils
Selon le matériel, Les architectures les plus courantes dans les réseaux sans fil sont les
architectures avec infrastructure et l’architecture sans infrastructure appelées aussi architecture ad
hoc.
1.2.3.1 Mode avec infrastructure
Ce mode de fonctionnement est très semblable au protocole Ethernet des réseaux filaires. Les
machines se connectent à un point d’accès (AP), appelé aussi station de base, qui partage la bande
passante disponible. Les stations de base sont munies d’une interface de communication sans fil
avec les sites mobiles qui se trouvent dans sa zone géographique ou sa couverture radio. Ce mode
de fonctionnement est illustré à la figure suivante :
Figure 1.01 :Mode infrastructure
1.2.3.2 Mode sans infrastructure ou réseau ad hoc
Ce mode n’a pas besoin de point d’accès pour fonctionner, ce sont les stations elles-mêmes qui
entrent en communication sans s’appuyer sur un équipement extérieur. Tous les nœuds d’un
réseau de ce type se comportent comme des routeurs et prennent part à la découverte et à la
7
maintenance des chemins de communication entre les différentes machines. Ce type de réseau
s’organise lui-même.
Figure 1.02 :Mode sans infrastructure
1.3 Présentation de WiFi (802.11)
1.3.1 Introduction
Le Wi-Fi est une technologie connue aux Etats-Unis depuis 1997 étant un standard d’accès sans fil
à des réseaux locaux. Le principe est d’établir des liaisons radio rapides entre des équipements et
des bornes reliées aux réseaux hauts débit. Cette technologie permet en principe une
interopérabilité totale des équipements, quelle que soit la marque ou la nature du terminal. Grace
au wifi, il est possible de créer des réseaux locaux sans fils à haut débit. Il permet de relier des
ordinateurs portables, des ordinateurs de bureau, des assistants personnels ou tout type de
périphérique à une liaison haut débit 11 Mbps ou supérieur sur un rayon de plusieurs dizaines de
mètres. Avec wifi, on peut se connecter à internet d’où on veut.
1.3.2 Historique
En 1997, l'attention est accaparée par le succès d'Internet et l'euphorie boursière montante, un
événement est passé inaperçu sauf pour quelques spécialistes et observateurs : l'adoption du
standard IEEE 802.11 ou Ethernet sans fil. Exploitant la bande de fréquence de 2,4 GHz, le
802.11 plafonnent à un débit de 2 Mbits/s au maximum. Ce précurseur est suivi de plusieurs
déclinaisons dont le célèbre Wi-Fi qui connaît un franc succès, aidé par le volontarisme des
fabricants, distributeurs et fournisseurs de services. Wi-Fi, est un nom composé à la manière d’hi-
fi et signifiant Wireless Fidelity. Il désigne les différentes déclinaisons de la norme IEEE 802.11
8
qui permet à plusieurs ordinateurs de communiquer sans fil en utilisant comme support les ondes
radio. Les câbles disparaissent enfin. Avantage : le déploiement d'un réseau Wi-Fi est assez
simple, le prix plutôt modeste en comparaison d'autres technologies.
Le Wi-Fi est une technologie intéressante pour de nombreuses sociétés liées au monde des
télécoms et d'Internet. Les collectivités locales et surtout les particuliersprofitent de la facilité
d'accès à Internet haut débit liée à cette norme. Dans sa déclinaison la plus connue, 802.11 b, le
Wi-Fi utilise la bande de fréquence de 2,4 GHz et atteint un débit théorique de 11Mbits/s (contre
128, 512 Kbits/s ou 1 Mbits/s pour l'ADSL), le 802.11a culmine à 22 Mbits/s et le 802.11 g, enfin,
flirte avec les 54 Mbits/s. Le Wi-Fi peut certes servir à surfer sur Internet, mais pas seulement. Il
autorise l'organisation de réseaux pourvus ou pas d'Internet pour échanger des fichiers, des
données, et bien entendu pour jouer : Ce ne sont là que quelques exemples de ses usages possibles.
Les avantages des réseaux sans fil ne sont plus à démontrer surtout à une génération de plus en
plus habituée à la mobilité. La multiplication des appareils (PDA, PSP, PC portables, terminaux et
les téléphones portables) capables de communiquer entre eux en fait le support idéal des réseaux
modernes.
1.3.3 Description de la norme 802.11
La norme 802.11 s'attache à définir les couches basses du modèle OSI (Open Systems
Interconnection) pour une liaison sans fil utilisant des ondes électromagnétiques, c'est-à-dire :
� La couche PHY(couche physique), proposant trois types de codage de l'information. La
couche physique est chargée de transmettre les bits de l’émetteur au récepteur. Trois (3) modes
de transmission sont définies :
– DSSS (Direct Sequence Spread Spectrum) dans la bande des 2,4GHz.
– FHSS (Frequency Hopping Spread Spectrum) dans la bande des 2,4GHz
– IR (Infra Rouge) pour la communication entre les stations proches
� La couche liaison de données, constitué de deux sous-couches : le contrôle de la liaison
logique (Logical Link Control, ou LLC) et le contrôle d'accès au support (Media Access
Control, ou MAC).
– La couche LLC permet de relier un WLAN de type 802.11 à un autre réseau respectant
l’une des normes de 802.x
9
– La couche MAC 802.11 implémente l’accès, l’allocation du support, l’adressage et le
formatage des trames.
La couche physique définit la modulation des ondes radioélectriques et les caractéristiques de la
signalisation pour la transmission de données, tandis que la couche liaison de données définit
l'interface entre le bus de la machine et la couche physique, notamment une méthode d'accès
proche de celle utilisée dans le standard Ethernet et les règles de communication entre les
différentes stations. La norme 802.11 couvre les couches physiques et liaison des données du
modèle OSI [5], et propose en réalité trois couches physiques, définissant des modes de
transmission alternatifs :
-
Couche Liaison de données LLC 802.2
MAC 802.11
Couche Physique (PHY) 802.11b
11Mbps
DSSS
802.11
11Mbps
FHSS
Infrarouges
Figure 1.03 : Les couches basses du modèle OSI
Il est possible d'utiliser n'importe quel protocole de haut niveau sur un réseau sans fil Wifi au
même titre que sur un réseau Ethernet.
La norme IEEE 802.11 est en réalité la norme initiale offrant des débits de 1 ou 2 Mbps. Des
révisions ont été apportées à la norme originale afin d'optimiser le débit (c'est le cas des normes
802.11a, 802.11b et 802.11g, appelées normes 802.11 physiques) ou bien préciser des éléments
afin d'assurer une meilleure sécurité ou une meilleure interopérabilité. Les différentes normes du
Wifi sont présentées dans l’annexe 1.
1.3.4 Les équipements Wifi
Il existe différents types d'équipement pour la mise en place d'un réseau sans fil Wifi : [7]
10
� Les adaptateurs sans fil ou cartes d'accès. En anglais wireless adapters ou network interface
Controller, noté NIC. Il s'agit d'une carte réseau à la norme 802.11 permettant à une machine
de se connecter à un réseau sans fil. Les adaptateurs WiFi sont disponibles dans de nombreux
formats (carte PCI, carte PCMCIA, adaptateur USB, carte compactflash, ...). On appelle
station tout équipement possédant une telle carte. A noter que les composants Wi-Fi
deviennent des standards sur les portables (label Centrino d'Intel).
� Les points d'accès Notés AP pour Access point, parfois appelés bornes sans fil, permettant de
donner un accès au réseau filaire (auquel il est raccordé) aux différentes stations avoisinantes
équipées de cartes WiFi. Cette sorte de hub est l'élément nécessaire pour déployer un réseau
centralisé en mode infrastructure. Certains modèles proposent des fonctions de modem ADSL
et comprennent plus ou moins de fonctions comme un pare-feu.
(a) : cartes d’accès (b) : Access point (Ap)
Figure 1.04 : équipement wifi
� Les autres
– Smart Display : écrans mobiles, soutenus par Microsoft.
– Chaînes WiFi: offrant la capacité de lire les MP3 directement sur le disque dur d'un
ordinateur grâce à l'interface Ethernet sans fil intégrée. Elle préfigure toute une génération
de produits, capables de lire, outre les CD audio, les radios qui émettent en MP3 sur
Internet.
– Assistant personnel : les PDA intégrant le WiFi est parfois plus avantageux qu'un
portable pour lire ses mails, importer des documents voir surfer sur le net.
– Rétroprojecteurs : pour des présentations avec portables mobiles.
– Caméra video: transmettre des images à distance à l'ordinateur qui les enregistre.
11
Les composants Wi-Fi ne sont pas plus onéreux que ceux des réseaux filaires, bientôt toutes les
plates-formes seront vendues avec des modules Wi-Fi intégrés. C'est déjà le cas dans le monde des
PC portables, qui, sous l'impulsion d'Intel, fait sa révolution sans fil grâce au Centrino.
1.3.5 Mode de fonctionnement du Wifi
1.3.5.1 Mode infrastructure
Les ordinateurs se connectent à un point d’accès via une liaison sans fil. Les réseaux sont basés
sur des équipements d’interconnexion faisant des ponts entre un réseau radio et un réseau câblé
permettant ainsi à de nombreux clients mobiles d’accéder à des ressources informatiques [5].
L’AP donne l’accès au réseau aux machines qui le désirent. Les AP sont en général câblés entre
eux afin de créer un réseau de bornes d’accès. Chaque station se connecte à l’AP. Si une station se
déplace, elle cherche le meilleur AP accessible afin de s’y connecter.
Figure 1.05 : Mode infrastructure
En mode infrastructure BSS, le réseau est composé d’un point d’accès qui permet aux différentes
stations qui se trouvent dans la même cellule d’échanger des informations.
En mode infrastructure ESS, le réseau comporte plusieurs points d’accès reliés entre eux par un
DS.
1.3.5.2 Mode ad-hoc
Les machines se connectent les unes aux autres, c’est un réseau point à point. Chaque machine
joue en même temps le rôle de client et le rôle de point d’accès [6]. Ce mode convient pour un
réseau de petite vergence. Elle a la particularité de ne comporter aucun point d’accès. Ce sont les
stations avec cartes ou clés Wifi qui entrent elles-mêmes en communication.
12
Figure 1.06 : Mode ad-hoc
1.4 Les réseaux mobiles Ad hoc
Les systèmes de communication cellulaire sont basés essentiellement sur l'utilisation des réseaux
filaires (tel que Internet ou ATM) et la présence des stations de base qui couvrent les différentes
unités mobiles du système. Les réseaux mobiles "ad hoc" sont à l'inverse, des réseaux qui
s'organisent automatiquement de façon à être déployable rapidement, sans infrastructure fixe, et
qui doivent pouvoir s'adapter aux conditions de propagation, aux trafics et aux différents
mouvements pouvant intervenir au sein des nœuds mobiles. L'évolution récente de la technologie
dans le domaine de la communication sans fil et l'apparition des unités de calculs portables (les
laptops par exemple), [8] poussent aujourd'hui les chercheurs à faire des efforts afin de réaliser le
but des réseaux : « l'accès à l'information n'importe où et n'importe quand ».
Le concept des réseaux mobiles ad hoc essaie d'étendre les notions de la mobilité à toutes les
composantes de l'environnement. Ici, contrairement aux réseaux bases sur la communication
cellulaire, aucune administration centralisée n'est disponible, ce sont les hôtes mobiles elles-
mêmes qui forment, d'une manière ad hoc, une infrastructure du réseau. 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. Les réseaux ad hoc sont idéals pour les applications caractérisées par
l’absence (ou la non-fiabilité) d'une infrastructure préexistante, tel que les applications militaires
et les autres applications de tactique comme les opérations de secours (incendies, tremblement de
terre, etc.) et les missions d'exploration.
1.4.1 Définition
Un réseau mobile ad hoc, 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
13
quelconque et dont le seul moyen de communication est l'utilisation des interfaces sans fil, sans
l'aide d'une infrastructure préexistante ou d’administration centralisée. Un réseau ad hoc peut être
modélisé par un graphe �� � ��� � �� ou �� représente l'ensemble des nœuds (i.e. les unités ou
les hôtes mobiles) du réseau et Et modélise l'ensemble les connections qui existent entre ces
nœuds (voir la figure 2.1). Si e = (u,v) appartient à Et, cela veut dire que les nœuds u et v sont en
mesure de communiquer directement à l'instant t. [10]
Figure 1.07 : La modélisation d'un réseau ad hoc
Figure 1.08 :Exemple d’un réseau ad hoc
1 2
3
4 5
6
7
8
9
Nœuds
(ou unités mobiles)
Liens de
communication
14
La topologie du réseau peut changer à tout moment (voir la figure 2.2), elle est donc dynamique et
imprévisible, ce qui fait que la déconnexion des unités est très fréquente.
Figure 1.09 : Le changement de la topologie des réseaux ad hoc Un exemple d'un réseau ad hoc : un groupe d'unités portables reliées par des cartes HIPERLAN.
Les réseaux appelés GSM ne représentent pas des réseaux ad hoc, car la communication entre les
unités passe obligatoirement par des stations de base du réseau filaire.
1.4.2 Les applications des réseaux mobiles ad hoc
Les applications ayant recours aux réseaux ad hoc couvrent un très large spectre, incluant les
applications militaires et de tactique, les bases de données parallèles, l'enseignement à distance, les
systèmes de fichiers répartis, la simulation distribuée interactive et plus simplement les
applications de calcul distribué ou méta-computing.
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 que difficile à mettre en place,
soit parce que la durée d'installation du réseau ne justifie pas de câblage à demeure. [12]
15
1.4.3 Les caractéristiques des réseaux ad hoc
D’après (Corson et Macker, 1999), les réseaux mobiles Ad hoc sont caractérisés par des propriétés
particulières. Chaque propriété est considérée dans la littérature comme étant une problématique
en soi [16] :
Les réseaux mobiles ad hoc sont caractérisés par ce qui suit :
� Une 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. Les liens de la topologie peuvent être unis ou
bidirectionnels.
� Une bande passante limitée : La communication dans les réseaux ad hoc se base sur le
partage d’un medium sans fil (onde radio). Ce qui induit une bande passante modeste pour
chaque hôte du réseau. [11]
� Qualité des liaisons variables : à cause du bruit et des interférences entre les noeuds, la
qualité des liaisons peut varier [13]
� Une 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. Cela se justifie par les contraintes
et limitations physiques qui font que le contrôle des données transférées doit être minimisé.
� L'absence d'infrastructure : Les réseaux ad hoc se distinguent des autres réseaux mobiles
par la propriété d'absence d'infrastructures préexistante et de tout genre 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.
� Contraintes de ressources : Les nœuds disposent de ressources d’alimentation (dues aux
batteries) et de capacités de calcul et de stockage limitées. D’où une gestion efficace est
nécessaire pour avoir une longue durée de vie, le trafic de routage devrait être maintenu à
un minimum (Des contraintes d'énergie : Les hôtes mobiles sont alimentés par des
sources d'énergie autonomes comme les batteries ou les autres sources consommables. Le
paramètre d'énergie doit être pris en considération dans tout contrôle fait par le système).
� Interférences : Dans un réseau ad hoc, les liens radio ne sont pas isolés. Ceci peut
impliquer que deux transmissions simultanées sur une même fréquence ou sur des
fréquences proches peuvent interférer et provoquer des erreurs de transmission. Un grand
nombre de paquets peuvent être endommagés et perdus lors du transfert. [12]
16
� Sécurité et Vulnérabilité : Les réseaux sans fil sont par nature plus sensibles aux
problèmes de sécurité que les réseaux filaires. Pour les réseaux ad hoc, le principal
problème ne se situe pas tant au niveau du support physique mais principalement dans le
fait que tous les nœuds sont équivalents et potentiellement nécessaires au fonctionnement
du réseau. Les possibilités de s’insérer dans le réseau sont plus grandes et la détection
d’une intrusion ou d’un déni de service est plus délicate. L’absence de centralisation pose
aussi un problème de remontée de l’information de détection d’intrusions. [12]
1.4.4 Principes de fonctionnement d’un réseau mobile ad hoc
Dans ce paragraphe, nous présenterons le principe de fonctionnement du réseau Ad hoc mobile.
La Figure 1.3 représente un réseau Ad hoc à multi-sauts. Le nœud mobile A communique avec un
autre nœud B directement (simple-saut) lorsqu'un canal radio avec des caractéristiques de
propagation suffisantes est disponible entre eux. Autrement, la communication multi-sauts, dans
laquelle au moins un nœud intermédiaire doit nécessairement agir comme un routeur entre la
source et la destination. Par exemple, il n'y a pas un canal radio direct (montré par les lignes) entre
A et C ou A et E dans la Figure 1.3. Les nœuds B et D doivent servir comme des routeurs
intermédiaires à la communication entre A - C, et A - E, respectivement. En effet, les réseaux Ad
hoc se distinguent par la capacité de tous ces nœuds à fonctionner comme des routeurs sur
demande. Afin d’empêcher que les paquets traversent les chemins infiniment longs, une condition
essentielle pour choisir un chemin est que ce dernier doit être sans boucle (loop-free). Un chemin
loop-free entre une paire de nœuds s'appelle une route [13].
Figure 1.10 :Exemple simple d’un réseau Ad hoc. [15]
17
Un réseau Ad hoc commence par au moins deux nœuds annonçant leur présence (beaconing) avec
leur information d'adresses respectives. Si le nœud A peut établir une communication directe avec
le nœud B (Figure 1.3), vérifiée en échangeant les messages appropriés de commande entre eux,
les deux mettent à jour leurs tables de routage. Quand un troisième nœud C joint le réseau avec
son signal beacon, deux scénarios sont possibles. Dans le premier, A et B déterminent que la
communication simple-saut avec C est possible. Dans le deuxième, seulement un des nœuds, soit
B, identifie le signal beacon de C et établit la communication directe avec C. Ensuite, les mises à
jour distinctes de la topologie, qui sont constituées des mises à jour des adresses et des routes, sont
faites dans chacun des trois nœuds immédiatement. Dans le premier cas, toutes les routes sont
directes. Dans le deuxième scénario, tel qu’illustré dans la Figure 1.4, la mise à jour de la route se
produit d'abord entre B et C, puis entre B et A, et ensuite de nouveau entre B et C, confirmant la
connexion mutuelle entre A et C par l'intermédiaire du B.
Figure 1.11:Bringing up an Ad hoc network [15]
18
La mobilité des nœuds peut changer les connexions en temps réel, exigeant des mises à jour des
routes. Supposons que pour quelque raison, le lien entre B et C n'est plus disponible suivant la
Figure 1.4. Les nœuds A et C sont encore accessibles entre eux, bien que cette fois seulement par
l'intermédiaire des nœuds D et E (Figure 1.3). D'une manière équivalente, la route loop-free
originale [A ↔ B ↔ C] est maintenant remplacée par la nouvelle route loop- free [A ↔ D ↔ Ε ↔
C]. Tous les nœuds dans le réseau doivent mettre à jour ses tables de routage appropriées pour
refléter ce changement de la topologie, qui sera détecté d'abord par les nœuds B et C, puis
transmis à A et à E, ensuite à D.
La connexion entre les nœuds peut être encore changée pour d'autres raisons. Par exemple, un
nœud peut errer trop loin hors de la portée de transmission, sa batterie peut être épuisée, ou il peut
être susceptible au mal fonctionnement de logiciel ou de matériel. Comme plus de nœuds joignent
le réseau ou quelques nœuds existants quittent, les mises à jour de la topologie deviennent plus
nombreuses, complexes, et plus fréquentes, ce qui diminue les ressources du réseau disponibles
pour échanger l'information d'utilisateur. La découverte d'un chemin loop-free comme une route
légitime entre une source et une destination peut devenir impossible si la topologie du réseau
change trop fréquemment. Ici, « trop fréquemment » signifie qu'il n'y avait pas assez de temps
pour faire propager, à tous les nœuds pertinents, toutes les mises à jour de la topologie résultantes
des derniers changements, ou plus mauvais, avant la détermination de tous les chemins loop-free
qui s’adaptent aux derniers changements de la topologie. La capacité de la communication
dégrade avec l’accélération de la vitesse, à cause de la connaissance de la topologie du réseau qui
devient de plus en plus inconsistante.
L'environnement sans fil partagé des réseaux Ad hoc mobiles exige l'utilisation des protocoles
appropriés du MAC (Medium Access Control) pour atténuer les issues de contention de medium,
permettre l'utilisation de la largeur de bande limitée, et résoudre les problèmes des terminaux
cachés et exposés (Chakrabarti et Mishra, 2004).
1.4.4.1 Le problème des stations cachées
Il s’agit d’un problème très connu dans les protocoles basés sur la contention comme Pure
ALOHA, Slotted ALOHA, CSMA1, IEEE 802.11, etc.
Lorsque deux nœuds cachés l’un de l’autre (hors de la portée de la transmission) essaient de
transmettre de l’information au même nœud de réception, par conséquent une collision de données
19
se produit à la réception (Toh, 2002). Soit le scénario de la Figure 1.5, où une barrière empêche le
nœud B de recevoir la transmission de D, et vice versa, ou, B et D ne peuvent pas s’entendre. La «
barrière » ne doit pas être physique ; la distance assez grande séparant deux nœuds est la « barrière
» qui peut se produire fréquemment dans les réseaux Ad hoc. Le nœud C peut « entendre » B et D.
Quand B transmet à C, D qui ne peut pas « entendre » B, peut aussi transmettre à C, ce qui
entraîne une collision et expose le problème du terminal caché. Dans ce cas-ci, B et D « sont
cachés » l’un de l’autre.
Figure 1.12:Exemple du problème des stations cachées.
Pour éviter la collision, tous les nœuds voisins au récepteur doivent être informés que le canal est
occupé. Ce qui peut être atteint par un protocole simple d'échange de message. Quand D souhaite
transmettre à C, il envoie d'abord un message RTS (Request to Send) à C. Dans la réponse, C
annonce un message CTS (Clear-To-Send) qui est reçu par B et D. Puisque B a reçu le message de
CTS non sollicité, B sait que C accorde la permission d'envoyer à une borne cachée et par
conséquent s'abstient à la transmission. Lors de la réception du message CTS de C en réponse à
son message RTS, D transmet son propre message.
Notons que la méthode RTS-CTS n’est pas une solution parfaite pour le problème de nœud caché.
Parce qu’il y aura des cas où des collisions se produisent quand les messages de contrôle RTS et
CTS sont envoyés par des nœuds différents. [14]
20
1.4.4.2 Le problème des stations exposées
La transmission des données des nœuds voisins peut empêcher un nœud de transmettre aux autres
nœuds. Il s’agit d’un problème des nœuds exposés. Un nœud exposé est un nœud dans la portée de
transmission de l’émetteur mais hors de la portée du récepteur (Toh, 2002). Soit l’exemple de la
Figure 1.6, quand C transmet à D. Puisque B peut « entendre » C et B n’a aucun moyen de savoir
que la transmission qu’elle veut engager avec A n’entrainerait pas de collision, alors B ne peut pas
risquer de transmettre à A par crainte de causer une collision à C, alors B « est exposé » au C.
Figure 1.13 :Exemple du problème des stations exposées.
La solution du problème de nœud exposé est l’utilisation des canaux de contrôle et de données de
façon séparée ou l’utilisation des antennes directionnels. [14]
1.5 Conclusion
Ce chapitre nous a permis d'avoir un point de vu généraliser sur les réseaux sans fils insistant tout
particulièrement sur le wifi tout en visant un aperçu sur le réseau mobile ad hoc. D’après Corson
et Macker, 1999, chaque propriété est considérée dans la littérature comme étant une
problématique en soi. Or le comportement des nœuds comme des routeurs est l’une des propriétés
considérables dans un réseau mobile ad hoc, ce qui va nous servir l’objet du second chapitre, le
routage dans un réseau ad hoc.
21
Chapitre 2
ROUTAGE DANS LE RESEAU AD HOC
2.1 Introduction
Comme nous avons déjà vu, un réseau ad hoc est un ensemble de nœuds mobiles qui sont
dynamiquement et arbitrairement éparpillés d'une manière où l'interconnexion entre les nœuds
peut changer à tout moment. Dans la plupart des cas, l'unité destination ne se trouve pas
obligatoirement dans la portée de l'unité source ce qui implique que l'échange des données entre
deux nœuds quelconques, doit être effectué par des stations intermédiaires. La gestion de cet
acheminement de données, ou routage, implique l'établissement d'une certaine architecture globale
que l'on doit tenir compte de la mobilité des unités et de la versatilité du médium physique. Le
routage est une méthode d'acheminement des informations vers la bonne destination à travers un
réseau de connexion donnée, il consiste à assurer une stratégie qui garantit, à n'importe quel
moment, un établissement de routes qui soient correctes et efficaces entre n'importe quelle paire
de nœud appartenant au réseau, ce qui assure l'échange des messages d'une manière continue. Vu
les limitations des réseaux ad hoc, la construction des routes doit être faite avec un minimum de
contrôle et de consommation de la bande passante.
La présentation du routage dans un réseau mobile ad hoc fera l’objet de ce chapitre. En
complément, des protocoles de routage sera classifier selon leur catégorie en exposant leurs
caractéristiques et avantages, et pour finir nous allons en tirer une conclusion qui nous affirmerons
laquelle de ces catégories de protocole pourrons résoudre le problème de routage dans chacun des
topologies du réseau.
2.2 Routage
2.2.1 Définition
Le routage est une méthode d'acheminement des informations vers la bonne destination à travers
un réseau de connexion donnée. Il consiste à assurer une stratégie qui garantit, à n'importe quel
moment, un établissement de routes qui soient correctes et optimales entre n'importe quelle paire
de nœud appartenant au réseau. Ce qui assure l'échange des messages d'une manière continue.
22
Figure 2.01 : Le chemin utilisé dans le routage entre la source et la destination
Le routage est donc, la brique technologique de base des réseaux sans fil Ad Hoc. Il constitue un
sérieux problème à résoudre pour que ces réseaux puissent fonctionner dans de bonnes conditions.
[4]
2.3 Classification des protocoles de routage
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 : Proactif, réactif et Hybride.
De nombreux protocoles et algorithmes ont été proposés pour rendre la communication dans les
réseaux ad hoc plus efficace. Et leurs performances ont été analysées dans différentes situations.
Dans la section suivante nous allons présenter certains protocoles de routage du mode ad hoc
développés dans le cadre du groupe de travail MANET de l’IFTE. Ces protocoles sont
représentatifs de diverse techniques et sont les plus avancés sur la voie d’une normalisation.
1 2
3
4 5
6
7
8
9
Source
Destination
23
Figure 2.02 :Classification des protocoles de routage
La figure 2.4 présente une taxonomie des protocoles de routage pour les réseaux Ad hoc. Ces
protocoles se différencient d'abord par le niveau d'implication des nœuds dans le routage.
Type Description
Uniformes Tous les nœuds du réseau jouent le même rôle pour la
fonction de routage
Non uniformes Une structure hiérarchique est donnée au réseau et que seuls
certains nœuds assurent le routage.
Les protocoles à partitionnement Le réseau est découpé en zones dans lesquelles le routage
est assuré par un unique nœud maître
Les protocoles orientés topologie Chaque nœud utilise comme donnée l’état de ses
connexions avec ses nœuds voisins : cette information est
ensuite transmise aux autres nœuds pour leur offrir une
connaissance plus précise sur la topologie du réseau
Les protocoles orientés destinations Connus sous le nom de Distance Vector Protocoles, ils
maintiennent pour chaque nœud destination une information
sur le nombre de nœud
Tableau 2.01 :les différents types de protocole de routage
2.3.1 Caractéristiques des algorithmes de routage :
Un algorithme doit être en mesure d’optimiser les ressources du réseau, éviter les boucles de
routage, empêcher la concentration du trafic autour de certains nœuds ou liens, assurer un routage
optimal tout en prenant en compte différentes métriques de coûts (bande passante, nombre de
24
liens, ressources du réseau, délais … etc.), s’adapter aux changements de topologie rapidement en
proposant de nouvelles routes acceptables, même en cas de forte mobilité des terminaux. [17],
[18]
2.3.2 Protocole proactifs
Dans cette catégorie dite à diffusion de table, les protocoles maintiennent les meilleurs chemins
existants vers toutes les destinations possibles au niveau de chaque nœud du réseau pour le faire
ils utilisent l’échange régulier de messages de contrôle pour mettre à jour les tables de routage
vers toute destination atteignable depuis celui-ci. Cette approche permet de disposer d’une route
vers chaque destination immédiatement au moment où un paquet doit être envoyé. Les tables de
routage sont modifiées à chaque changement de la topologie du réseau.Les routes sont
sauvegardées même 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.Les deux
principales méthodes utilisées sont : la méthode Etat de Lien ("Link State") et la méthode du
Vecteur de Distance ("Distance Vector"). [9]
Les protocoles basés sur ce principe sont entre autres: DSDV, WRP, OLSR, TBRPF, GSR, FSR,
HSR, ZHLS, CGSR, DREAM, LSR et OLSR.
Les avantages et les inconvénients des protocoles proactifs :
Avec un protocole proactif, les routes sont disponibles immédiatement, ainsi l'avantage d'un tel
protocole est le gain de temps lors d'une demande de route. Le problème est que, les changements
de routes peuvent être plus fréquents que la demande de la route et le trafic induit par les messages
de contrôle et de mise à jour des tables de routage peut être important et partiellement inutile, ce
qui gaspille la capacité du réseau sans fil. De plus, la taille des tables de routage croit linéairement
en fonction du nombre de nœud.
De ce fait, un nouveau type de protocole a apparu, il s'agit des protocoles de routage réactifs.
2.3.3 Protocoles réactifs
Ces protocoles se basent sur la découverte et le maintien des routes. Suite à un besoin, une
procédure de découverte globale de routes est lancée. Ce processus s’arrête une fois la route
trouvée ou toutes les possibilités sont examinées. Dès que la communication est établie, cette route
est maintenue jusqu’à ce que la destination devienne inaccessible ou jusqu’à ce que la route ne soit
25
plus désirée. Cette technique permet de ne pas inonder le réseau par des paquets de contrôle et de
ne pas conserver les routes non utilisées. Mais elle nécessite en contrepartie un certain temps
pouvoir établir une route avant de pouvoir la transmettre.
Parmi les protocoles basés sur ce principe on cite : CBRP, DSR, AODV, TORA, ABR, SSR,
LAR, RDMAR, EARP et CEDAR [30]
Avantages et les inconvénients des protocoles réactifs:
A l'opposé des protocoles proactifs, dans le cas d'un protocole réactif, aucun message de contrôle
ne charge le réseau pour des routes inutilisées ce qui permet de ne pas gaspiller les ressources du
réseau. Mais la mise en place d'une route par inondation peut être coûteuse et provoquer des délais
importants avant l'ouverture de la route et les retards dépassent bien souvent les délais moyens
admis par les logiciels, aboutissant à une impossibilité de se connecter alors que le destinataire est
bien là.
De ce fait, un nouveau type de protocole a apparu, il s'agit des protocoles de routage hybrides.
2.3.4 Protocole hybrides
Les protocoles hybrides combinent les deux approches. Ils utilisent un protocole proactif, pour
apprendre le proche voisinage (voisinage à deux ou trois sauts) et un protocole réactif pour
atteindre les nœuds situés au-delà de cette zone prédéfinie de voisinage. Les protocoles hybrides
font appels aux techniques des protocoles réactifs pour chercher des routes. Avec ce découpage, le
réseau est partagé en plusieurs zones et la recherche de route en mode réactif peut être améliorée.
A la réception d’une requête de recherche réactive, un nœud peut indiquer immédiatement si la
destination est dans le voisinage ou non et par conséquent savoir s’il faut aiguiller ladite requête
vers les autres zones sans déranger le reste de sa zone.
Un exemple de protocoles appartenant à cette famille est DSR (Dynamic Source Routing), qui est
réactif à la base mais qui peut être optimisé s'il adopte un comportement proactif. Il y a aussi le
protocole ZRP (Zone Routinier Protocol), (ZHLS) Zone Based Hierarchical, et (HSR)
Hierarchical State Routing.
Avantages et inconvénient des protocoles hybrides :
26
Le protocole hybride est un protocole qui se veut comme une solution mettant en commun les
avantages des deux approches précédentes en utilisant une notion de découpe du réseau. Ce type
de protocole s’adapte bien aux grands réseaux, cependant, il rassemble toujours quelques
inconvénients des deux approches proactives et réactives, comme : messages de contrôle
périodique, coût de découverte d’une nouvelle route.
Pour englobé le tous, nous allons illustrer dans un tableau la description de chacun des protocoles
de routage dans le réseau ad hoc ainsi que ces avantages et inconvénients
Catégorie Protocole de routage
Type Topologie utilisé
Avantage et Inconvénient
Proactif
OLSR
Sélection des voisins
Hiérarchique
Sélection d’ un nœud spécial pour la diffusion des requêtes de demande de route appelé MPR, diffusant des messages de contrôle de la topologie TC et permettant la réduction de la charge provoqué par l’inondation des requêtes de route. Son défaut, l’inondation des messages de contôles cause une charge de contrôle importante au réseau.
DSDV
Orienté destination
à plat
fournisseur des routes valable vers toutes destinations du réseau a tout moment. Ce pendant, L’inondation des paquets de mise à jour cause une charge de contrôle importante au réseau.
FSR
Orienté topologie
à plat
Il minimise la charge des paquets de mise à jour des tables de routages du protocole GSR en utilisant la technique de l’œil de poisson. Cependant, il nécessite un délai initial avant de commencer la transmission des données.
Réactif
AODV
Orienté destination
à plat
Elle combine les avantages des deux protocoles DSVD et DSR, retient une route bidirectionnelle correspond au plus court chemin. Cependant, le délai initial avant de commencer la transmission des données est important.
CBRP
Partitionnement
Hiérarchique
Il diffuse les requêtes de route seulement aux chefs de cluster ce qui permet de réduire la charge provoqué par l’inondation des requêtes de route. Son défaut, se base sur la phase de découverte de route qui engendre un trafique considérable.
27
Hybride
DSR
Orienté topologie
à plat
Il découvre les routes à la demande en inondant le réseau avec un paquet de requête. Les paquets de données peuvent être redirigés pendant leur transmission. Son inconvénient, la taille des paquets de données très grande quand le nombre de nœud dans réseau est grand.
HSR
Partitionnement
Hiérarchique
Il combine les notions de groupes dynamiques, niveaux hiérarchiques avec une gestion efficace de localisation.
Tableau 1.1 :Les protocoles de routage dans le réseau mobile ad hoc
2.4 Conclusion
Ce chapitre nous a permis d’aborder la notion et la présentation du routage dans les réseaux Ad
hoc afin de faire une étude comparative au niveau des différents protocoles de routage dans les
environnements mobiles classés de façon proactif ou réactif et voire même hybride et qui nous
serons utile dans l’évaluation des performances de ces derniers sous un logiciel NS2.Mais dans le
chapitre suivant, nous n’allons qu’étudier les protocoles de routage qui acheminera correctement
le paquet par le meilleur chemin.
28
Chapitre 3
ETUDE COMPARATIVE DES PROTOCOLES DE ROUTAGE AODV DS R et DSDV
DANS LE RESEAU AD HOC
3.1 Introduction
Lors de la transmission d'un paquet d'une source vers une destination, il est nécessaire de faire
appel à un protocole de routage qui acheminera correctement le paquet par le « meilleur » chemin.
Plusieurs protocoles ont été proposés au niveau ad hoc. Afin de comprendre leurs comportements
dans des réseaux mobiles, nous nous sommes intéressés donc à faire une étude théorique sur
quelques protocoles, pour cela, la première étape à faire est celle du choix des protocoles sur
lesquels se baser. Notre choix s'est porté sur AODV DSR et DSDV. En effet, ces protocoles
montrent une meilleure qualification.
AODV, DSR et DSDV sont représentatifs de diverses techniques et sont les plus avancés sur la
voie d'une normalisation. Le premier utilise un mécanisme de diffusion (broadcast) dans le réseau
pour découvrir les routes valides. Le second est un protocole réactif, nommée DSR où la source
indique le chemin complet jusqu’à la destination dans l’entête du paquet. La troisième est proactif,
appelé DSDV (Destination Sequenced Distance Vector), il est basé sur l’algorithme distribué de
Bellman-Ford [20] dont chaque nœud du réseau maintient dans sa table de routage un ensemble
d’informations pour chaque destination. Ces trois protocoles (AODV DSR et OLSR) font
désormais l'objet d'une Request For Comment(RFC), tandis que les autres sont à des versions
assez stables de leurs drafts.
Dans ce chapitre, nous allons présenter ces trois protocoles, en commençant par une étude
détaillée sur le protocole de routage AODV et sa manière d'agir, puis nous décrirons les
principales caractéristique et fonctionnalité du protocole DSR et DSDV qui permettent d'assurer
l'acheminement des données entre les différentes unités mobiles. On finira par une brève
comparaison entre ces trois protocoles de routage en tenant compte des avantages et inconvénients
de chacun de ces protocoles.
3.2 Présentation du protocole de routage AODV «Ad hoc On demand Distance Vector»
3.2.1 Définition
29
AODV est un protocole de routage réactif et basé sur le principe des vecteurs de distance, capable
à la fois de routage unicast et multicast. Il représente essentiellement une amélioration de
l'algorithme proactif DSDV.
3.2.2 Le type des messages dans AODV
Le protocole AODV fonctionne à partir de trois types de messages :
– Les messages de demande de route RREQ : Route Request Message.
– Les messages de réponse de route RREP : Route Reply Message.
– Les messages d'erreur de route RERR : Route Error Message.
Message de demande de route (RREQ) : Il est sous la forme suivante :
Message Route Reply (RREP) : Ce message est sous la forme suivante :
30
Message d'erreur (RERR) : Il est sous la forme suivante :
3.2.3 Le principe de numéro de séquence :
La circulation inutile des paquets de messages, qui peut arriver avec le DBF (Distribution de
Bellman Ford), est intolérable dans les réseaux mobiles ad hoc, caractérisés par une bande
passante limitée et des ressources modestes.
L'AODV utilise les principes de numéro de séquence afin d'éviter le problème des boucles infini et
des transmissions inutiles de messages sur le réseau, en plus il permet de maintenir la consistance
des informations de routage. A cause de la mobilité des nœuds dans le réseau ad hoc, les routes
changent fréquemment ce qui fait que les routes maintenues par certains nœuds, deviennent
invalides. Les numéros de séquence permettent d'utiliser les routes les plus nouvelles ou autrement
dit les plus fraiches (fresh routes), un nœud mis à jour chaque fois qu'une nouvelle information
provenant d'un message RREQ, RREP ou RERR, il incrémente son propre numéro de séquence
dans les circonstances suivantes :
– Il est lui-même le nœud destination et offre une nouvelle route pour l'atteindre.
– Il reçoit un message AODV (RREQ, RREP, RERR) contenant de nouvelles informations
sur le numéro de séquence d'un nœud destination.
– Le chemin vers une destination n'est plus valide.
3.2.4 Fonctionnement de protocole :
Dans cette partie nous détaillerons le fonctionnement de protocole AODV, en commençant
d'abord par la manière dont il découvre les routes, nous parlerons par la suite sur la façon dont il
maintient ces routes, une fois valides.
31
3.2.4.1 Découverte de route :
Lorsqu' un nœud veut émettre un message, il cherche dans sa table de routage si une route valide
existe pour la destination qu'il souhaite atteindre, s'il n'en existe aucune, il se met à la recherche
d'une route.
Cette tâche est réalisée par la diffusion de message RREQ sur une adresse de type broadcast au
travers de réseau. Le champ numéro de séquence destination de paquet RREQ, contient la dernière
valeur connue du numéro de séquence associé au nœud destination. Cette valeur est recopiée de la
table de routage, si le numéro de séquence n'est pas connu, la valeur nulle ne sera prise par défaut.
Avant l'envoi du paquet RREQ, le nœud origine sauvegarde l'identificateur du message et l'adresse
IP de façon à ne pas traiter le message dans le cas où un voisin le lui renverrait. Une fois la
demande de route effectuée, le nœud demandeur se met en attente de réponses.
Quand un nœud de transit (intermédiaire) reçoit le paquet de la requête, il vérifie dans stable
historique si cette requête a déjà été vue et traitée. Si le paquet est doublon, le nœud doit l'ignorer
et arrêter le traitement. Dans le cas contraire le couple (@ source, ID de requête) sera inscrit dans
la table historique pour rejeter le futur doublon, et le nœud continue le traitement en cherchant la
destination dans sa table de routage : s'il possède une route récente, à noter qu'une route est
récente si le numéro de séquence de la destination dans la table est supérieur ou égal au numéro de
séquence dans le paquet RREQ. Dans ce cas, le nœud envoi un paquet de réponse (RREP) à la
source lui indiquant comment atteindre la destination. Autrement le nœud ne connait pas la route
vers la destination : il incrémente le nombre de sauts et rediffuse le paquet.
Avant de l'envoi de paquet, le nœud intermédiaire sauvegarde l'adresse du nœud précédent et celle
du nœud source à partir duquel la première copie de la requête est reçue. Cette information est
utilisée pour construire le chemin inverse, qui sera traversé par le paquet réponse de la route de
manière unicast (cela veut dire qu'AODV supporte seulement les liens symétriques).
32
Figure 3.1 : Réponse de la route
Notée dans les tables le champ hop count de message route RREP est incrémentée à chaque nœud
traversé, une fois le nœud origine atteint, la valeur du champ hop count représente la distance en
nombre de sauts pour aller du nœud source vers le nœud destination. Quand le nœud reçoit une
réponse de route, le paquet est examiné, et une entrée pour la route vers la destination est inscrite
dans la table de routage si au moins une de ces conditions est satisfaite :
– Aucune route vers la destination n'est connue.
– Le numéro de séquence pour la destination dans le paquet de réponse est supérieur à la
valeur présente dans la table de routage.
– Les numéros de séquences sont égaux mais la nouvelle route est plus courte.
Afin de limiter le coût dans le réseau, AODV propose d'étendre la recherche progressivement,
initialement, la requête RREQ est diffusée à un nombre de sauts limité. Si la source ne reçoit
aucune réponse après un délai d'attente déterminé, elle retransmet un autre message de recherche
en augmentant le nombre maximum de sauts. En cas de non réponse, Cette procédure est répétée
un nombre maximum de fois avant de déclarer que cette destination est injoignable.
A chaque nouvelle diffusion, le champ Broadcaste ID du paquet RREQ est incrémenté pour
identifier une requête de route particulière associée à une adresse source. Si la requête RREQ est
rediffusée un certain nombre de fois (RREQ.RETRIES) sans réception de réponse, un message
d'erreur est délivré à l'application.
33
3.2.4.2 Maintenance des routes :
AODV maintient les routes aussi longtemps que celles-ci sont actives, une route est considérée
active tant que des paquets des données transitent périodiquement de la source a la destination
selon ce chemin. Lorsque la source stoppe d'émettre des paquets des données, le lien expirera et
sera effacé des tables de routage des nœuds intermédiaires. Si un lien se rompt lorsqu'une route est
active, le lien est considéré défaillant. Les défaillances des liens sont, généralement, dues à la
mobilité du réseau ad hoc.
Afin de détecter cette défaillance, AODV utilise les messages de contrôle <<HELLO>> qui
permettent de vérifier la connectivité ou plutôt l'activité des routes. Un nœud détermine l'activité
d'une route en écoutant périodiquement les messages <<HELLO>> transmis par ses voisins. Si
pendant un laps de temps, trois messages <<HELLO>> ne sont pas reçus consécutivement, le
nœud considère que le lien -vers ce voisin est cassé. Il envoie un message d'erreur (RERR) à la
source et la route devient invalide16.
Gestion de la connectivité locale :
En fait, lors de la rupture d'un lien d'une route active, AODV tente de réparer la connectivité
localement en diffusant une requête de recherche de route dans le voisinage. Si cette tentative
échoue, alors la route est supprimée, et nouvelle recherche de route est lancée par la source.
3.2.5 Avantages et Inconvénients :
L'un des avantages d'AODV est l'utilisation de numéro de séquence dans les messages. Ces
numéros de séquences permettent l'éviter les problèmes de boucles infinis et sont essentiels au
processus de mise à jour de la table de routage. Un autre avantage est le rappel de l'adresse IP du
nœud origine dans chaque message. Ceci permet de ne pas perdre la trace du nœud à l'origine de
l'envoi du message lors des différents relais.
Un inconvénient d'AODV est qu'il n'existe pas de format générique des messages. Chaque
message a son propre format : RREQ, RREP, RERR.
3.3 Le protocole DSR «Dynamic Source Routing»
3.3.1 Définition
Dynamic Source Routing (DSR) [JMH01] est un protocole réactif basé sur l'utilisation de la
technique source routing (routage source). Le chemin à parcourir est contenu dans l'entête du
34
paquet de données. Ainsi lorsqu'un nœud reçoit un paquet, il le route vers le nœud suivant dont
l'adresse est indiquée dans l'entête.
3.3.2 Principe
Dynamic Source Routing (DSR) est un protocole de routage pour les réseaux maillés sans fils
(wireless mesh networks). Il est similaire à AODV dans le sens où il forme une route à la demande
quand un ordinateur veut transmettre des données. Alors que la détermination des routes sources
requiert d'accumuler les adresses de chaque routeur entre la source et la destination durant la
découverte de la route. Les informations sur les chemins sont mises en cache pendant la
découverte de la route. Les chemins appris sont utilisés pour router les paquets. Pour cela, les
paquets routés contiennent les adresses de chaque routeur que le paquet traverse.
3.3.3 Fonctionnement de protocole
Les deux opérations de base du protocole DSR sont : la découverte de routes et la maintenance de
routes. L'opération de découverte de routes permet à n'importe quel nœud du réseau de découvrir
dynamiquement un chemin vers un nœud quelconque du réseau.
Un nœud initiateur de l'opération de découverte diffuse un paquet requête de route qui identifie
l'hôte cible. Si l'opération de découverte est réussie, le nœud initiateur reçoit un paquet réponse de
route qui liste la séquence de nœud par lesquels, la destination peut être atteinte. En plus de
l'adresse de l'initiateur, le paquet requête de route contient un champ enregistrement de route, dans
lequel est stockée la séquence des nœuds visités durant la propagation de la requête de route dans
le réseau.
Au passage du paquet, chaque nœud stocke en mémoire chaque nouvelle route, pour une
utilisation postérieure éventuelle. Si le nœud ne trouve pas de route correspondant à l'entête du
paquet, alors il initialise une découverte de route. Ainsi un nœud intermédiaire n'est pas obligé de
connaître et d'avoir une table de routage à jour pour l'ensemble du réseau, mais seulement pour les
nœuds qui lui sont adjacents.
Ce protocole est simple dans sa démarche et sa mise en place. Il permet également au réseau d'être
auto structurable et configurable. Il n'y a donc aucun message de mise à jour des tables de routage
autres que ceux contenus dans les entêtes des paquets transitant dans le réseau. Le paquet requête
de route contient ainsi un identificateur unique de la requête. Dans le but de détecter les
duplications des réceptions de la requête de route, chaque nœud du réseau ad hoc maintient une
35
liste de couples <adresse de l’initiateur, identificateur de requête>des requêtes récemment
reçues.
(b) Utilisation de la route dans le DSR
Figure 2.5 : La découverte de chemins dans le DSR.
3.3.3.1 Découverte de route
Lors de la réception d'un paquet requête de route par un nœud source du réseau, le traitement
suivant est effectué :
– Dans le cas où le couple <adresse de l'initiateur, identificateur de requête du paquet
reçu>existe déjà dans la liste des requêtes récemment reçues, le paquet est ignoré.
– Dans le cas contraire, si l'adresse de nœud sourceexiste dans le champ enregistrement de
route du paquet de la requête, le paquet est ignoré.
– Sinon, si l'adresse de nœud source est la même que l'adresse de la destination, alors
l'enregistrement de route (contenu dans le paquet de la requête) contient le chemin à
36
travers lequel le paquet de la requête est passé avant d'atteindre le nœud source. Une copie
de ce chemin est envoyée dans un paquet réponse de route à l'initiateur.
– Sinon, l'adresse de nœud source est ajoutée dans l'enregistrement de route du paquet reçu,
et le paquet est rediffusé.
De cette manière, la requête de route est propagée dans le réseau jusqu'à ce qu'elle atteigne l'hôte
destination qui va répondre à la source. Le fait d'ignorer la requête dans le cas où l'adresse du
récepteur existe dans l'enregistrement de route garantit que la propagation d'une unique copie de la
requête ne peut pas se produire à travers des boucles de nœuds.
Dans le but de retourner le paquet réponse de route à l'initiateur de l'opération de découverte, le
nœud destination doit connaître un chemin vers l'initiateur. Dans le cas où la destination n'a pas
déjà gardé une telle route, le chemin spécifié dans l'enregistrement de route contenu dans le paquet
requête de route peut être inversé et utilisé. Cependant, cela exige que les liens entre les nœuds
participant à la route doivent être bidirectionnels, ce qui n'est pas vérifié dans certains
environnements.
Afin de réduire le coût et la fréquence de la découverte de routes, chaque nœud garde les chemins
appris à l'aide des paquets de réponses. Ces chemins sont utilisés jusqu'à ce qu'ils soient invalides.
3.3.3.2 Maintenance des routes
Afin d'assurer la validité des chemins utilisés, le protocole DSR exécute une procédure de
maintenance de routes. Quand un nœud détecte un problème fatal de transmission, un message
erreur de route (route error) est envoyé à l'émetteur originel du paquet. Le message d'erreur
contient l'adresse du nœud qui a détecté l'erreur et celle du nœud qui le suit dans le chemin. Lors
de la réception du paquet erreur de route par l'hôte source, le nœud concerné par l'erreur est
supprimé du chemin sauvegardé, et tous les chemins qui contiennent ce nœud sont tronqués à ce
point-là. Par la suite, une nouvelle opération de découverte de routes vers la destination est initiée
par l'émetteur.
Après la découverte de route vers la destination, pour envoyer un paquet de donnée à un autre
nœud, l'émetteur construit une route source et l'inclut en tête du paquet. La construction se fait en
spécifiant l'adresse de chaque nœud à travers lequel le paquet va passer pour atteindre la
destination. Par la suite, l'émetteur transmet le paquet au premier nœud spécifié dans la route
37
source. Un nœud qui reçoit le paquet et qui est différent de la destination supprime son adresse de
l'entête du paquet reçu, puis le transmet au nœud suivant identifié dans la route source. Ce
processus se répète jusqu'à ce que le paquet atteigne sa destination finale.
3.3.4 Avantages et inconvénients
Parmi les avantages du protocole DSR, on peut citer le fait que les nœuds de transite n'aient pas
besoin de maintenir les informations de mise à jour pour envoyer les paquets de données, puisque
ces derniers contiennent toutes les décisions de routage. En outre, dans ce protocole, il y a une
absence totale de boucle de routage, car le chemin source-destination fait partie des paquets de
données envoyés.
3.4 Le protocole DSDV « Destination Sequenced Distance Vector »
3.4.1 Définition
L'algorithme de routage appelé "Vecteur de Distance à Destination Dynamique Séquencée" ou
DSDV (Dynamic Destination-Sequenced Distance-Vector) [Per01, BMJ98] a été conçu
spécialement pour les réseaux mobiles. Il est basé sur l'idée classique de l'algorithme distribué de
Bellman-Ford, DBF, en y apportant des solutions à ses éventuels problèmes.
3.4.2 Fonctionnement de protocole
Ce protocole fonctionne de façon suivante :
Chaque nœud maintient une table de routage qui contient :
– Toutes les destinations possibles.
– Le nombre de saut nécessaire pour atteindre la destination.
– Le numéro de séquences (SN : sequence number) qui correspond à un nœud destination.
Afin de maintenir la consistance des tables de routage dans une topologie qui varie
rapidement, chaque nœud du réseau transmet périodiquement sa table de routage à ses
voisins directs. Le nœud peut aussi transmettre sa table de routage si le contenu de cette
dernière subit des changements significatifs par rapport au dernier contenu envoyé.
La mise à jour doit permettre à un nœud de pouvoir localiser, dans la plupart des cas, une autre
unité du réseau.La mise à jour de la table de routage peut se faire de deux façons:
– Une mise à jour complète.
38
– Une mise à jour incrémentale.
Dans la mise à jour complète, le nœud transmet la totalité de la table de routage aux voisins ce qui
nécessite l'envoi de plusieurs paquets de données ; alors que dans une mise à jour incrémentale,
juste les entrées qui ont subi un changement par rapport à la dernière mise à jour, sont envoyées ce
qui permet de limiter les informations échangées.
Un paquet de mise à jour contient :
1- Le nouveau numéro de séquence incrémenté, du nœud émetteur.
2- Et pour chaque nouvelle route :
3- L'adresse de la destination.
4- Le nombre de nœuds (ou de sauts) séparant le nœud de la destination.
5- Le numéro de séquence (des données reçues de la destination) tel qu'il a été estampillé par
la destination.
Les données de routage reçues par un nœud, sont comparées avec les données déjà disponibles. La
route étiquetée par la plus grande valeur du numéro de séquence (i.e. la route la plus récente), est
la route utilisée. Si deux routes ont le même numéro de séquence, alors la route qui possède la
meilleure métrique (nombre de sauts), est celle qui sera utilisée. Les modifications faites sur les
données de routage locales, sont immédiatement diffusées à l'ensemble courant des voisins. Les
routes reçues par une diffusion, seront aussi envoyées quand le récepteur procédera à l'envoi de
ses paquets de routage. Le récepteur doit incrémenter les métriques des routes reçues avant l'envoi,
car le récepteur représente un nœud en plus, qui participe dans l'acheminement des messages vers
la destination. Un lien rompu est matérialisé par une valeur infinie de sa métrique, c’est-à-dire une
valeur plus grande que la valeur maximale permise par la métrique.
3.4.3 Avantages et inconvénients
Parmi les améliorations apportées au DBF classique, Le concept de numéro de séquence, qui
Permet à tout moment de se renseigner sur la validité des routes, a permis au DSDV de résoudre le
problème de boucle de routage et du comptage à l'infini. Comme tout protocole de routage
proactif, le DSDV connaît la route, ponctuellement, au moment même où un nœud doit procéder à
une transmission, ce qui permet d'être efficace en délais de transmission. Cependant, ce protocole
ne résout pas la lenteur de la convergence des tables, qui est lui aussi hérite du DBF ; l'échange
39
périodique des tables de routage, pour maintenir les routes même si elles ne seront pas utilisées,
génère un nombre de paquet de contrôle énorme. Pour finir, les auteurs de ce protocole l'ont
renoncé aux profits de l’AODV .
3.5 Conclusion
Dans un réseau très mobile, avec de fréquent changement de topologie, AODV a un petit avantage
sur DSDV car les routes sont mises à jour plus rapidement. AODV utilise les principes de numéro
de séquence afin de permettre l'utilisation des routes les plus nouvelles ou autrement dit les plus
fraiches (fresh routes), un nœud mis à jour chaque fois qu'une nouvelle information provenant d'un
message RREQ, RREP ou RERR, ce qui permet une connaissance de route à chaque changement
de topologie. Par contre, dans un réseau plus statique, DSDV encombre moins le réseau qu'AODV
qui émet beaucoup plus de messages à chaque découverte de route. En effet dans ce cas DSDV
n'émet pas de message de mises à jour de la topologie que dans un intervalle de temps régulier.
Pour DSR, il n’est pas sensible en termes de mobilité. DSR est un protocole de routage similaire à
AODV dans le sens où il forme une route à la demande. Pour la découverte de route, un nœud
initiateur de l'opération de découverte diffuse un paquet requête de route qui identifie l'hôte cible.
Une foi réussite, le nœud initiateur reçoit un paquet réponse de route qui liste la séquence de nœud
par lesquels la destination peut être atteinte. Cette action n’est faite qu’à la demande d’une route
qu’importe la topologie du réseau. Alors on peut dire que DSR ne réagit pas selon le changement
de topologie, ce qui nous mène à dire que DSR n’est pas sensible à la mobilité des nœuds.
Dans un réseau très dense, DSR charge moins le réseau que DSDV et AODV. Par sa nature
proactive, DSDV inonde le réseau avec des paquets de contrôle pour mettre à jour la table de
routage de chacun des nœuds présents, et pour AODV, il met à jour sa table de routage à chaque
changement de topologie. Alors que DSR, n'émet presque pas des messages de contrôles qu’à
chaque demande de route. Par contre, dans des réseaux moyens, DSDV et AODV représentent
plus d’avantage que DSR. Lors de communications courtes, DSDV à un énorme avantage sur
DSR car les routes sont disponibles immédiatement. Dans la plupart des cas, les messages de
contrôles d'AODV sont légèrement plus nombreux que ceux de DSDV. AODV émets d'autant
plus de paquets que le réseau est grand.
Ce chapitre a été axé le fonctionnement et le comportement de chacun des protocoles AODV et
DSDV et DSR dans les réseaux Ad hoc et se finit par une petite comparaison entre eux, en faisant
40
face à des avantages et inconvénients. Nous présenterons dans ce qui suit une méthode de choix
des protocoles de routage afin d’aider les utilisateurs à mieux choisir le protocole adapté à leur
besoin.
Chapitre 4
METHODE DE CHOIX DES PROTOCOLES DE ROUTAGE DANS LE RESEAU AD
HOC
4.1 Introduction
A l’heure actuelle, le nombre de protocole de routage dans le réseau ad hoc augmente
considérablement grâce à l’amélioration faite par des groupes de chercheur après une longe étude
de chacun de ces protocoles bases. Nous venons de voir dans le chapitre trois, les ancêtres ou les
protocoles base aux quels nous avons fait l’étude dont nous avons énumérez les avantages et
inconvénients. C’est ainsi dans cet ouvrage que nous allons apprendre dans quelle situation ces
protocoles sont le plus adaptés, et de savoir davantage le protocole de routage envisageable pour
une amélioration (ou combinaison) selon la situation désirée.
Dans ce chapitre nous allons étudier tous cas possible que l’on peut rencontrer lors d’une
réalisation d’un réseau ad hoc, nous allons voir en premier les domaines d’application de ces
protocoles de routage, puis nous allons citer les contraintes et difficulté de routage dans les
réseaux ad hoc en proposant quelques méthodes de choix de protocoles.
4.2 Les applications du réseau mobiles Ad hoc
Les applications ayant recours aux réseaux ad hoc couvrent un très large spectre, et aussi on peut
dire qu’ils présentent une très grande importance dans plusieurs domaines. 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 que difficile à mettre en place, soit parce que la durée
d'installation du réseau ne justifie pas de câblage à demeurer. On peut ainsi mentionner qu’il y a
quelques applications de la technologie des réseaux mobiles Ad hoc pouvant inclure les
applications industrielles et commerciales, entraînant des échanges de données. En plus, des
applications à la sécurité afin de gérer les systèmes de sécurité ainsi que les mécanismes de
sécurisation et voire même pour la mise en communication d'unités de secours sur des zones
larges lors des catastrophes naturelles par exemple. Il y a aussi des applications militaires pour
assurer la liaison entre les différentes unités d'une armée. En outre, Lesréseaux peuvent être
41
utilisés au niveau local pour faire un réseau multimédia autonome instantané à l'aide des
ordinateurs portables ou des PDA (Personal Digital Assistant) dans une conférence ou une salle
de classe (par exemple) et aussi dans les domaines médicaux afin de surveiller à l’avenir les
fonctionnement vitales d'un organisme vivant. Les réseaux Ad hoc sont utilisables aussi comme
des réseaux de capteurs (sensor-networks) surtout dans les domaines environnementaux où les
nœuds détiennent des capteurs, par exemple de température, et une autre application de ces
réseaux dans les réseaux domestiques (home networks). Enfaite, le réseau de capteurs sans fil est
l'une des dix nouvelles technologies qui bouleverseront le monde et notre manière de vivre et de
travailler. Il répond à l'émergence ces dernières décennies, de l'offre et d'un besoin accru
d'observation et de contrôler des phénomènes physiques et biologiques dans différents domaines.
4.3 Les contraintes de routage dans les réseaux ad hoc
L’accomplissement de la tâche de routage pour assurer la connexion des réseaux ad hoc au sens
classique du terme (tout sommet peut atteindre tout autre), inhérente à tout réseau, est compliquée
dans les réseaux ad hoc par l’utilisation de communications par radio. La radio est en effet le
medium le plus hostile à la propagation de l’information. Du fait notamment des interférences
entre utilisateurs et de la complexité du traitement du signal. D’autre part, le routage ad hoc est
aussi compliqué par la mobilité des éléments susceptibles d’acheminer le trafic (c'est-à-dire les
utilisateurs eux-mêmes). Les nœuds mobiles sont dynamiquement et arbitrairement éparpillés
d'une manière ou l'interconnexion entre les nœuds peut changer à tout moment. N'ayant pas été
prévus pour ces dernières complications, les algorithmes de routage classiques ne peuvent donc
pas être utilisés tels quels. Ils doivent être optimisés pour être efficaces dans les réseaux ad hoc.
Le problème qui se pose dans le contexte des réseaux ad hoc est de s’adapter aux communications
radio en réduisant au maximum le trafic de contrôle nécessaire au bon fonctionnement du réseau,
et en même temps rester en mesure de suivre dynamiquement la mobilité des éléments du réseau
avec adaptation de la méthode d'acheminement utilisée avec le grand nombre d'unités existant
dans un environnement caractérisé par de modestes capacités de calcul et de sauvegarde.
Ce sont ces contraintes qui sont au fondement des algorithmes de routage ad hoc. Il semble donc
important que toute conception de protocole de routage doive étudier ces problèmes.
4.4 La difficulté du routage dans les réseaux ad hoc
Comme nous avons déjà vu, l'architecture d'un réseau mobile ad hoc est caractérisée par une
absence d'infrastructure fixe préexistante, à l'inverse des réseaux de télécommunication classiques.
42
Un réseau ad hoc doit s'organiser automatiquement de façon à être déployable rapidement et
pouvoir s'adapter aux conditions de propagation, au trafic et aux différents mouvements pouvant
intervenir au sein des unités mobiles.
Dans le but d'assurer la connectivité du réseau, malgré l'absence d'infrastructure fixe et la mobilité
des stations, chaque nœud est susceptible d'être mis à contribution pour participer au routage et
pour retransmettre les paquets d'un nœud qui n'est pas en mesure d'atteindre sa destination : tout
nœud joue ainsi le rôle de station et de routeur.
Chaque nœud participe donc à un protocole de routage qui lui permet de découvrir les chemins
existants, afin d'atteindre les autres nœuds du réseau. Le fait que la taille d'un réseau ad hoc peut
être énorme, souligne que la gestion de routage de l'environnement doit être complètement
différente des approches utilisées dans le routage classique. Le problème qui se pose dans le
contexte des réseaux ad hoc est l'adaptation de la méthode d'acheminement utilisée avec le grand
nombre d'unités existant dans un environnement caractérisé par de modestes capacités de calcul et
de sauvegarde.
Dans la pratique, il est impossible qu'un hôte puisse garder les informations de routage concernant
tous les autres nœuds, dans le cas où le réseau serait volumineux.
Certains protocoles, comme le DSR et l’AODV, utilisent la sauvegarde des données de routage
concernant une destination donnée (dans le cas où la source ne possède pas déjà de telles
informations). Cependant, ces protocoles ne spécifient pas les destinations que les nœuds doivent
garder leurs données de routage. Le problème ne se pose pas dans le cas de réseaux de petites
tailles, car l'inondation (la diffusion pure) faite dans ces réseaux n'est pas coûteuse. Par contre,
dans un réseau volumineux, le manque de données de routage concernant les destinations peut
impliquer une diffusion énorme dans le réseau, et cela si on considère seulement la phase de
découverte de routes. Le trafic causé par la diffusion, dans ce cas, est rajouté au trafic déjà existant
dans le réseau ce qui peut dégrader considérablement les performances de transmission du
système caractérisé principalement par une faible bande passante.
Dans le cas où le nœud destination se trouve dans la portée de communication du nœud source le
routage devient évident et aucun protocole de routage n'est initié. Malheureusement, ce cas est
généralement rare dans les réseaux ad hoc. Une station source peut avoir besoin de transférer des
données à une autre station qui ne se trouve pas dans sa portée de communication.
43
Par exemple dans le réseau illustré par la figure 2.4 l'unité mobile W n'est pas dans la portée de
communication de l'unité U (indiquée par le cercle d'origine U) et vice versa. Dans le cas où
l'unité U veut transférer des paquets à W, elle doit utiliser les services de l'unité V dans l'envoi des
paquets, puisque l'unité V contient dans sa portée de communication les unités U et W. Dans la
pratique, le problème de routage est plus compliqué à cause de la non-uniformité de la
transmission sans fil et de la possibilité du déplacement imprévisible de tous les nœuds concernés
par le routage.
Figure 4.01 : Un simple réseau ad hoc constitué de trois unités mobiles
4.5 Méthode de choix de protocole de routage
Plusieurs cas peuvent se produire dans un réseau ad hoc, cela due au comportement indépendant
de chaque nœud qui représente le réseau. Le principal problème que l’on rencontre dans un réseau
ad hoc c’est la capacité de routage de donnée en se servant des nœuds comme station et routeur.
Pour résoudre ce problème, nous allons tout d’abord étudier tous les cas possibles que l’on peut
rencontrer dans le réseau ad hoc, puis nous allons élaborer quelque métrique d’évaluation pour
pouvoir analyser la performance de chaque protocole dans chacun de ces cas qui se produit durant
la réalisation d’un réseau ad hoc.
4.5.1 Les cas que l’on peut rencontrer dans un milieu ad hoc
Après avoir cité les applications du réseau ad hoc, nous pouvons constater que l’on peut rencontrer
plusieurs difficultés selon certaine situation. Ainsi, des contraintes sont liées à l’interconnexion
des nœuds et surtout au routage des données.
W V U
44
Dans un réseau ad hoc, plusieurs cas peuvent se produire selon laquelle nous allons étudier et on
peut les rencontrer dans la réalisation réelle.
Parmi ces cas, on peut citer :
- La variation de nombre de nœud ; Ceci due à l’ajout d’un ou plusieurs nœud (ou terminal)
dans le réseau, et qui entraine un encombrement au milieu du réseau pour certain
protocole, et d’autre le considère comme un atout pour pouvoir router les données au plus
court chemin.
- La mobilité des nœuds ; due au déplacement des nœuds (ou terminaux mobiles) qui mène à
la coupure de liaison ou connexion entre les hôtes. Ceci définit le changement brusque de
topologie au quel certain protocole ne tienne pas compte la localisation régulière de chaque
nœud.
- L’encombrement de trafic (ici UDP et TCP) ; dû à l’augmentation de nombre de connexion
dans le réseau, ceci entraine une perte de donnée considérable et une énorme utilisation de
bande passante.
Ces trois cas fait partie des difficultés de routage de données que l’on devra résoudre.Dans le cas
où le réseau serait volumineux (ajout considérable de nœud dans le réseau), les protocoles réactifs
feront l’affaire grâce à sa nature « recherche de route à la demande » parmi lesquels on peut citer
AODV et DSR. Les protocoles de catégorie réactive inondent moins les paquets de routage par
rapport au protocole proactif, ce dernier garde les données de routage qui entraine une dégradation
considérable de la performance de transmission du système caractérisé principalement par une
faible bande passante. Le changement brusque de topologie dû à la mobilité des nœuds entraine
une coupure de liaison, ce paramètre nécessite une connaissance régulière de la localisation de
chaque nœud selon laquelle il n’est plus difficile de connaitre la topologie du réseau. Une solution
s’offre à nous en utilisant le protocole proactif qui construit les tables de routage avant que la
demande en soit effectuée. Son plus grand avantage est d’identifier chaque instant de la Topologie
du réseau. Parmi ces protocoles on présente les deux exemplaires ; DSDV et OLSR. La gestion de
trafic est la plus important dans le réseau ad hoc car on peut assister à plusieurs scènes de variation
du nombre de connexion. Mais comme désavantage, l’augmentation des nombres de nœud
entrainera un encombrement du trafic dans le réseau menant à la dégradation de la performance de
la transmission des données et pour solutionner ce problème nous avons recours à un protocole
capable de gérer le trafic.
45
4.5.2 Les métriques d’évaluation
Selon l’exigence des utilisateurs, il est nécessaire de faire une étude préalable selon laquelle nous
allons citer les métriques d’évaluation de chaque protocole de routage afin de préciserleur
performance, mais certains d’entre eux représente davantage une meilleure performance dans
certaine métrique. Ce dernier nous sert d’un paramètre pour évaluer lesquels de ces trois
protocoles seraient le plus adapter dans des cas que l’utilisateur souhaite obtenir. Parmi ces
paramètres, on peut citer :
4.5.2.1 Perte de donnée (ou Dropped packets)
Due à l’encombrement du réseau, il est normal de perdre des paquets lors d’une envoie de
données, mais ce qui nous intéresse ici c’est de savoir qui serait le protocole adapté à cette
situation du moins celui qui perd moins de paquets.
DP = Nombre de paquets perdus
4.5.2.2 Le taux de délivrance des paquets (ou Packet Delivery Fraction PDF)
Le taux de délivrance des paquets est le rapport entre le nombre de paquets reçus (par toutes les
destinations du trafic) et le nombre de paquets émis (par toutes les sources de trafic). La métrique
opposée au taux de délivrance de paquets est le taux de perte de paquets. Un taux de délivrance de
paquets élevé est équivalent à un taux de perte petit, et vice versa. Cette métrique représente la
fiabilité du protocole pour expédier tous les paquets de donnés envoyés. [2]
PDR = Nombre de paquets reçus / Nombre de paquets émis
4.5.2.3 Délai moyen de bout en bout
Le délai de bout en bout (ou Average End to End Delay AVG)est le temps qui sépare le moment
d'envoi d'un paquet de la couche transport de la source et le moment de réception de ce paquet par
la couche transport de la destination. Il inclut le temps de latence pour la découverte de routes, le
temps de passage dans les files d'attente des nœuds intermédiaires et le temps de transmission d'un
saut vers un autre. Nous mesurons le délai moyen de bout en bout par rapport à tous les paquets
reçus pendant la simulation, puis nous calculons la moyenne. Cette métrique représente l'efficacité
du protocole en termes de temps de réponse et en termes de choix des chemins optimaux.
EED = Σ Temps de livraison d’un paquet / Nombre de paquets reçus
46
4.5.2.4 Overhead de routage (ou Routing Load RL)
C’est le nombre de paquets de routage générés par le protocole en question pour la recherche,
l’établissent et le maintien des routes. Cette métrique nous permet d'évaluer pour chaque
protocole, la surcharge provoquée pour l'envoi des paquets de contrôle.
RL = Nombre de paquets de contrôle
Afin de perfectionner notre étude, il nous est nécessaire de mettre en considération les
différentes failles pour une performance favorable de la transmission des données dans le réseau et
de prendre en compte la variation de nombre de nœud, la mobilité et l’encombrement de trafic
dans le but d’en tirer un résultat satisfaisant pour les utilisateurs afin qu’ils puissent faire leur
choix au niveau de ces protocoles ainsi proposés.
4.6 Conclusion
Le problème du routage dans les réseaux sans fil en mode ad hoc est le défi le plus difficile à
réaliser, car il s'agit de trouver une route optimale multisauts qui relie deux nœuds quelconques du
réseau. Ce routage est donc un problème d'optimisation sous contraintes. Parmi ces contraintes,
nous avons cité les changements de topologies, volatilité des liens, et la capacité limitée de la
bande passante. Ces derniers sont dus à la variation des nombres de nœuds, à la mobilité des
nœuds, et à l’encombrement de trafic dont la plupart des protocoles de routage ne s’y adapte pas.
Pour remédier à cela, nous avons établi la méthode de choix de protocole basé sur l’évaluation de
performance de protocole de routage selon plusieurs métriques. Ce dernier nous sert d’un
paramètre pour évaluer lesquels des protocoles seraient le plus adapter dans des cas que
l’utilisateur souhaite obtenir. Dans ce qui suit, nous simulerons sous NS2 la méthode de choix de
protocole de routage dont notre choix s'est porté sur AODV, DSR et DSDV. En effet, ces
protocoles montrent une meilleure qualification, représentatifs de diverses techniques et sont les
plus avancés sur la voie d'une normalisation.
47
CHAPITRE 5
SIMULATION ET EVALUATION DES PERFORMANCES
5.1 Introduction
Dans ce dernier chapitre, nous avons comme objectif l’évaluation des performances des protocoles
de routage dans un réseau mobile Ad Hoc tels que l’AODV, le DSDV et le DSR, puis vient une
étape de comparaison qui nous permet de dégager les principales caractéristiques de ces
protocoles. L’analyse de cette étape conduit à un bilan des forces et faiblesses et nous permet de
déterminer dans quelles situations chaque protocole est le plus adapté. Pour ce faire, nous allons
utiliser le simulateur de réseaux NS-2 afin d’examiner de près quelques scénarios de simulation
des protocoles ainsi cités. De plus pour une meilleure interprétation des résultats de la simulation,
nous présenterons les critères d’évaluation utilisés ainsi que les paramètres adéquats.
5.2 Environnement de simulation
Pour pouvoir effectuer une étude comparative des protocoles de routage dans un réseau mobile Ad
Hoc, il n’est pas toujours possible d’accéder aux infrastructures nécessaires en raison de leurs
coûts élevés. De plus, les expérimentations réelles n’offrent souvent pas une grande souplesse.
Rappelons que les réseaux ad hoc sont des réseaux qui englobent plusieurs unités mobiles qui se
déplacent dans un territoire quelconque et dont le seul moyen de communication est l'utilisation
des interfaces radio. En effet, il serait très coûteux voire impossible de mettre en place un réseau à
des fins de tests de certains critères.
Pour remédier à ce problème, on a recours à la simulation qui met à la disposition de
l’utilisateur un environnement d’expérimentation. Parmi les simulateurs les plus utilisés dans la
communauté des réseaux mobile ad hoc, nous citons le simulateur NS2.
5.3 Le simulateur NS2
5.3.1 Motivations de l’utilisation de ns2
NS-2 (Network Simulator version 2) est un simulateur orienté objet. Il a été développé
comme partie du projet VINT (Virtual InterNetwork Testbed) à ISI (Information Sciences
Institute) et supporté par DARPA. La première version ns-1 date de 1989. L’apparition de ns-2
sous le projet VINT avait pour but d’unifier les efforts de la communauté des chercheurs pour
fournir une plateforme de simulation puissante, reconnue et permettant des simulations complexes
et proches des conditions réelles. Le résultat, ns-2 est devenu l’un des simulateurs réseau les plus
48
utilisé par la communauté des chercheurs pour expérimenter de nouvelles idées. Il permet entres
autres une simulation complète de toutes les couches réseau et la pile TCP/IP avec une variété de
protocoles et de paramètres de simulation (mobilité, rayon de transmission et densité, etc).
Ce simulateur a fait l’objet de plusieurs études et comparaisons avec d’autres simulateurs
existants. La figure 39-a ci-dessous donne les statistiques concernant la popularité de simulateurs
les plus connus et on remarque que ns-2 devance tous les simulateurs et en particulier OPNET
avec 88.8%. La figure 5.01 donne les résultats d’une étude statistique sur l’utilisation de différents
simulateurs dans 151 articles de publication acceptés dans la conférence ACM Mobil Hoc entre
2000 et 2005. On y remarque aussi que ns-2 est le simulateur de référence pour les simulations
dans les réseaux sans fil Ad-Hoc avec un pourcentage de 43.8%.
Figure 5.01 : Taux d'utilisation des simulateurs réseaux
5.3.2 Présentation de NS2
Le simulateur de réseau NS (Network Simulator) est un outil logiciel de simulation de
réseaux informatiques. C’est un simulateur à événements discrets qui permet d'exécuter tout type
de scénarios sur des topologies définies par l'utilisateur.
Le NS2 est un simulateur de réseaux orienté objet, écrit sur la base du langage C++, avec au-
devant un interpréteur OTcl1. Il fonctionne suivant deux raisonnements différents. Il intègre d’une
part, la manipulation des bits, des entêtes de paquet, l’implémentation d’algorithmes capables de
parcourir plusieurs types de données, donc la création rapide et efficace des objets et variables
manipulés lors de la simulation. Pour cette tâche, une rapidité d’exécution est requise, et est
49
importante. Ceci est offert par le C++ qui sert à décrire le fonctionnement interne des composants
de la simulation, il permet de créer les classes de base et de traiter un grand nombre de données,
tel que le calcul des tables de routage, mouvement des nœuds mobiles, protocoles, gestion des
files d’attente…etc. D’autre part, la configuration des objets, la gestion des évènements,
l’exploration d’un grand nombre de scénarios (Changement du modèle et réexécution), donc, un
temps d’itération plus important par rapport à la rapidité d’exécution. Ceci par contre est offert par
l’OTcl, qui le permet d’une manière interactive.
5.3.3 Le processus de simulation
Le processus de simulation en utilisant NS-2 est composé de trois phases principales :
� Phase de préparation : s’occupe de la génération des fichiers d’entrées. A cette étape, on
introduit des fichiers de scripts Otcl qui décrivent l’environnement avec tous ses nœuds, leurs
déplacements et leur trafic de données. Ces fichiers sont classés en deux catégories :
• Fichiers de scénario qui décrivent les nœuds, leurs positions ainsi que leurs
mouvements.
• Fichiers de communication qui décrivent le trafic dans le réseau.
� Phase de simulation : pour lancer les simulations et générer les traces. Les deux fichiers
obtenus de la phase de préparation sont introduits dans un script de lancement OTcl. Le script
de simulation consiste à indiquer la topologie du réseau, à activer des traces aux endroits
pertinents, à engendrer des événements particuliers à des instants donnés. A la fin de cette
étape on obtient deux fichiers (journaux) appelé aussi « fichiers traces ». Le premier fichier
sera traité par l’outil de visualisation NAM. Et le deuxième doit être filtré par un script awk
afin d’afficher le résultat en utilisant l’outil Xgraph.
� Phase d’analyse : pour analyser les traces et générer les courbes. L’outil de visualisation
NAM s’occupe du premier fichier trace. Deux éléments intéressants sont proposés à la
visualisation : un dessin de la topologie du réseau étudié, et une visualisation dynamique du
déroulement du programme dans le temps. Le deuxième fichier de trace sauvegarde tous les
échanges de paquets effectués. Afin de dessiner les courbes en utilisant Xgraph, le fichier doit
être filtré par un script awk pour ne garder que les informations pertinentes.
Le schéma des étapes de simulation est illustré dans la figure suivante :
50
Figure 5.02 : Le processus de simulation
5.4 Simulation
Dans cette section, nous présentons les critères d’évaluation utilisés, les paramètres de
simulation, les scénarios, puis nous interpréterons les résultats obtenus.
5.4.1 Métriques évaluées
Afin d’évaluer le comportement des protocoles de routage, plusieurs critères d’évaluation
ont été définis. Ces critères ont pour but d’évaluer les différents aspects du fonctionnement des
protocoles tels que l’efficacité des transferts, ou bien la quantité d’information supplémentaire
nécessaire au bon fonctionnement.
51
Nous avons choisi quatre métriques les plus souvent abordées pour évaluer les performances des
différents protocoles : PDF (Packet Delivery Fraction), EED (End to End Delay), DP
(Dropped packets), RL (Routing Load)
5.4.2 Paramètres de simulation
Nos simulations sont faites sur NS 2.35 sous Ubuntu 12.04. L’environnement étudié est un
réseau de taille 670 x 670 m, dans lequel se trouvent une variation de nombre de nœud de 5 à 100
nœuds, une variation de la vitesse des nœuds ainsi que le nombre de connexions dans le réseau.
Nous effectuons des simulations d’une durée de 30 secondes, pour avoir suffisamment de temps
pour étudier la mobilité des nœuds et évaluer les performances du réseau.
Les modèles utilisés dans la simulation sont standards et respectent les propriétés suivantes :
� Modèle d’antenne : il existe 2 types de modèle de simulation : l’antenne directionnelle qui
nécessite que l’antenne d’émetteur soit pointée en direction de l’antenne réceptrice, et
l’antenne omnidirectionnelle qui diffuse à 360° autour d’elle. Afin qu’un nœud puisse
communiquer avec tous ses voisins dans n’importe quelle direction, nous avons choisi le
modèle omnidirectionnel. La portée radio est fixée à 250 m. C’est une valeur réaliste pour les
cartes réseaux sans fil existantes.
� Modèle de propagation : nous avons choisi le modèle Two-ray ground comme modèle de
propagation afin de considérer la réflexion des signaux sur le sol, cela pour avoir des résultats
plus justes et plus proches du cas réel.
� Modèle de trafic : pour le trafic généré nous avons plusieurs paramètres à définir. Nous avons
choisi des sources de trafic à débit constant CBR (constant bit rate) et le protocole de transfert
de fichiers ou FTP destiné à l’échange informatique de fichiers sur un réseau TCP. CBR
fonctionne de façon plus simple : les paquets ont une taille fixe et sont envoyés à un rythme
continu. L’intervalle d’envoi entre deux paquets est constant. De plus, la source d’un message
n’essaie pas de savoir si son paquet a bien été reçu. Nous avons aussi fixé d’autres paramètres
: la taille d’un paquet est égale à 512 octets et la fréquence d’envoi est de 4 paquets/seconde.
En outre, le ftp se comporte de façon plus complexe vu qu’il suit la norme de TCP
(Transmission Control Protocol), ce dernier fonctionne en mode connecté qui établit un
processus de connexion avant l’envoie de données. TCP est un protocole de transport fiable,
qui assure l’envoi de donnée dans le réseau : à chaque envoi de données, un accusé de
réception est envoyé par le destinataire pour dire à la source que le paquet est bien délivrer et
52
qu’il est libre de recevoir le prochain paquet. Dans ce modèle, nous allons varier le nombre
de connexion de 5 à 30 pour mieux tester la performance du réseau. Ces valeurs nous
permettent d’étudier le comportement des protocoles mise à part la congestion.
� Modèle de mobilité : L’impact du mouvement des nœuds sur une simulation est bien entendu
très important. En effet, la vitesse, la direction et la fréquence du mouvement ont un impact
considérable sur la transmission d’information. Dans nos simulations, nous nous sommes
basés sur le modèle setdest. Ce modèle est utilisé pour définir le trajet de chaque nœuds du
réseau afin d’avoir la même mobilité dans les prochains simulations. La mobilité du modèle
setdest est basée par un paramètre nommé « speed » qui définit la vitesse de déplacement de
nœuds en [m/s]. En fait, en variant la vitesse de la mobilité on s'attend à ce qu’il y ait un
impact significatif sur les performances des protocoles de routage. Dans ce modèle, les nœuds
atteignent une destination définit à l’avance et s’y rendent à une vitesse comprise dans un
intervalle de temps. Dans nos simulations, nous avons varié la vitesse de nœud de 5 à 30 m/s.
� La génération d’un scénario de mobilité se fait à travers la fonction SetDest de NS2.
Ex : $ns at time "$nœud setdest x y speed"
X et Y désignent les coordonnés de destination du nœud « $nœud », « time » est le temps
d’exécution avec « speed » la vitesse de nœud en [m/s]
Le tableau suivant résume les paramètres utilisés dans nos simulations :
Paramètre Valeur
Antenne OmniAntinna : Omnidirectionnel
Type de la couche MAC IEEE 802.11
Modèle de propagation radio Two Ray Ground
Bande passante 1Mb
Trafic CBR 4 paquets/s
Taille de paquets 512 Byte
Taille du réseau 670 x 670 m
La portée radio de transmission 250 m
Temps de simulation 30 s
Modèle de mobilité SetDest
Tableau 5.01 : Paramètres de simulation
5.4.3 Les protocoles simulés
53
Depuis les protocoles implémentés dans NS, nous avons pris ceux qui entrent dans le cadre
des deux types étudiés : Réactifs et Proactifs. Les protocoles simulés étaient :
- Réactif : AODV, DSR
- Proactif : DSDV
5.4.4 Les scénarios de simulation
Les trois protocoles étudiés sont exposés au même environnement en termes de position des
nœuds, de modèle de mobilité et de type de trafic.
Afin de filtrer les résultats obtenus, nous avons développé 4 analyseurs de trace pour les 4
métriques à savoir, PDF, EDD, DP, et RL. Ces derniers sont écrits en AWK (voir ANNEXE B).
Ensuite, pour faciliter la simulation, nous avons préparés trois (3) fichiers script Shell qui permet
de lancer la simulation et d’analyser rapidement les fichiers traces en générant des courbes
représentant les performances des trois protocoles.
Pour se faire, nous allons diviser la simulation en trois scenarios, le premier sera basé sur la
variation de la vitesse de nœud, le second à la variation de nombre de connexions et le dernier au
nombre de nœuds.
5.4.4.1 Scenarios 1 : Etude de mobilité
Les nœuds mobiles utilisent le modèle de mobilité SetDest qui définit à l’avance la trajectoire du
nœud au moment données. Ce modèle est utilisé pour évaluer la performance des protocoles de
routage Ad hoc sous un même déplacement des nœuds.
Afin de décrire l'impact de la mobilité sur les performances des protocoles de routage Ad hoc,
nous avons fait varier la vitesse de nœuds entre 5 à 30 m/s. Voici un tableau qui résume les
différents critères de scenario de simulation que nous allons utiliser dans ce scenario.
Critère Valeur
Temps de simulation 30s
Type de la couche MAC IEEE 802.11
Type de mouvement SetDest (définit à l’avance)
Type de trafic cbr/UDP et ftp/TCP
Taille de paquets 512 Byte
Taille du réseau 670 x 670 m
54
La portée radio de transmission 250 m
Protocole utilisé AODV/ DSDV/ DSR
Nombre de connexion 6
Nombre de nœud 20
Speed (vitesse de nœuds) 5, 10, 15, 20, 25, 30
Le paramètre simulé Variation de la vitesse de nœud
Tableau 5.02 : Les différents critères de scenarios 1
5.4.4.2 Scenarios 2 : Modèle de trafic
Afin d’analyser le comportement des protocoles de routage Ad hoc, il est préférable de choisir des
sources de trafic tels que les sources de trafics à débit constant CBR (Constant Bit Rate) associées
au protocole UDP et FTP (File Transfer Protocol) associées au protocole TCP. En outre, il est
aussi à noter que la description de l'impact de la charge sur les performances des protocoles de
routage Ad hoc varie selon le nombre de connexions s’étendant entre 5 et 30 connexions.
Le nombre de connexions est varié de 6 à 30 dont les deux types de trafic CBR et FTP se
partagent le même nombre de connexions. Les transmissions commencent à des instants distribués
uniformément entre 1.0 et 25 secondes. La taille des paquets de données est 512 octets.Voici un
tableau qui résume les différents critères de scenario de simulation que nous allons utiliser dans ce
scenario.
Critère Valeur
Protocole utilisé AODV/ DSDV/ DSR
Speed (vitesse de nœuds) 10 m/s
Nombre de nœud 20
Nombre de connexions 2, 4, 6, 8, 10, 12
Le paramètre simulé Variation de nombre de connexion
Tableau 5.03 : Les différents critères de scenarios 2
5.4.4.3 Scénario 3 : Variation de nombre de nœuds
Afin de décrire l'impact de la densité sur les performances des protocoles de routage Ad hoc, nous
avons fait varier le nombre de nœuds entre 5 et 100 nœuds. La vitesse des nœuds est fixée à 10
55
m/s pour pouvoir étudier ces trois protocoles au même environnement en termes de densité de
nœud par espace.
Critère Valeur
Protocole utilisé AODV/ DSDV/ DSR
Speed (vitesse de nœuds) 10 m/s
Nombre de connexions 6
Nombre de nœuds 2, 4, 6, 8, 10, 12
Le paramètre simulé Variation de nombre de nœud
Tableau 5.04 : Les différents critères de scenarios 3
Nous allons voir ici un environnement de simulation de 5 nœuds sans fil qui forment un réseau ad-
hoc en se déplaçant sur un espace plat de 670 x 670 mètres pendant 30 second de temps de
simulation. Un outil d’animation nommé NAM est utilisé pour regarder cette animation.
Figure 5.03 : Scenarios de simulation des trois protocoles AODV DSDV et DSR avec 5 nœuds et 6
nombre de connexions
En augmentant les nombres de nœuds jusqu’à 50, on peut voir que le protocole proactif DSDV
envoie beaucoup plus de paquets de contrôle par rapport aux deux autres. Ces paquets de contrôles
sont représentés sous forme de cercle qui définit la portée maximale de chaque nœud.
OADV DSDV DSR
56
Figure 5.04 : Scenarios de simulation des trois protocoles AODV DSDV et DSR avec 50 nœuds
En augmentant encore plus le nombre de nœud, on remarque la nature de protocole réactif qui
envoie des paquets de contrôle, ce dernier représente une demande de route à chaque envoie de
donnée.
Figure 5.05 : Scenarios de simulation des trois protocoles AODV DSDV et DSR avec 100 nœuds
5.5 Interprétation des résultats
Dans cette étape, nous allons essayer d’interpréter tous les résultats des simulations effectuées
dans le cadre de cette étude. Ces résultats sont présentés sous formes de courbes calculées en
fonctions des quatre métriques telles que PDR, EED, DP, RL. Ces métriques sont évaluées en
fonction des nombres de nœud, de connexion ainsi qu’à la variation de la vitesse de mobilité. Dans
la suite nous allons présenter les résultats des différents scénarios successivement.
5.5.1 Nombre des Paquets de contrôle
Cette fonction peut se définir comme étant les nombres des Paquets de contrôle envoyé par les
protocoles AODV DSDV et DSR.
OADV DSDV DSR
OADV DSDV DSR
57
Visiblement, les trois figures ainsi présentées successivement représentent chacun trois courbes
bien distinctes dont la première figure représente le nombre de paquets de contrôle en fonction de
la variation de nombre de connexions, la deuxième en fonction de la vitesse de mobilité et la
troisième en fonction de nombre de nœuds. Il est à noter que pour chaque figure la courbe de
couleur rouge correspond au protocole AODV, le vert à la DSR et le bleu à la DSDV.
Figure 5.06 :Paquets de contrôle en fonction de nombre de connexions
Sur la figure ci-dessus, le protocole DSDV se stabilise dans son domaine quel que soit le nombre
de connexions. Ceci peut s’expliquer grâce à sa nature proactive que le protocole DSDV génère
périodiquement des paquets de contrôle pour mettre à jour les tables de routage de chaque nœud
ainsi présents. De son côté, le protocole DSR se progresse petit à petit selon le nombre de
connexion ; entre autres à chaque connexion, une demande de route s’intervient à chaque envoie
de donnée correspondant à quelques paquets de contrôle. Et enfin, la courbe tracée en rouge
s’accroit de façon remarquable et brusque. De nature réactive, l’AODV trouve sa similarité avec le
protocole DSR exigeant une route à la demande à chaque envoi de donné, sauf que l’AODV
inonde des paquets HELLO afin de mettre à jour sa table de routage.
58
Figure 5.07 :Paquets de contrôle en fonction de la vitesse de nœud
De même pour la variation de la vitesse de nœud, le protocole DSDV se comporte toujours de
façon stable. Cependant, AODV atteigne une valeur maximum de 320 paquets de contrôle entre
25 à 30 m/s. De ce fait, plus la vitesse est grande plus la topologie change fréquemment et surtout
cela implique dans le réseau une inondation considérable des paquets « HELLO » pour l’AODV.
Comme étant le voisin des protocoles précédents, le DSR n’a aucune réaction face à la mobilité
des nœuds car il ne cherche que des routes à la demande alors que le changement de topologie leur
rende insensible. Mais on remarque davantage une perturbation entre l’intervalle de 10 à 20 m/s,
étant due à la coupure de liaison faite par la mobilité des nœuds. Le DSR maintient une route
jusqu’à ce que celle-ci soit inutilisable, une fois coupé, une nouvelle demande de route se
déclenche à l’avenir.
59
Figure 5.08 :Paquets de routage en fonction de nombre de nœuds
Sur la figure ci-dessus, il est à remarquer que la courbe du protocole réactif DSR est positionnée
au-dessous des deux autres courbes. De ce fait, on peut en déduire que DSR génère moins de
paquets de contrôle du fait qu’il soit réactif (qui établit une route à la demande), il se comporte de
façon stable par rapport aux deux autres même avec un maximum de nombre de nœud. Nous
pouvons quasiment dire qu’il est insensible à la variation des nœuds.
Pour le protocole proactif DSDV, il se comporte de façon progressive en augmentant les nombres
des nœuds car chaque nœud du réseau maintient une table de routage fraîche en envoyant des
messages de contrôle régulier. De son côté, l’AODV reste toujours proche de DSDV et aussi le
nombre de paquets de contrôle converge vers le protocole proactif en augmentant le nombre de
nœud à cause des interruptions fréquentes des trafics de données dues au changement de topologie
du réseau et à la densité de nœud par espace. Réactif par sa nature, AODV vérifie bien la règle du
besoin de paquets de contrôle avec l’augmentation de nombre des nœuds. De plus, la corrélation
des courbes d’AODV et de DSDV est bien visible et voire même leurs courbes sont bien proches.
Par contre, DSR reste loin des autres avec un minimum de paquets de contrôle.
60
La logique théorique sollicite une augmentation du trafic de contrôle avec une augmentation de
nombre de nœuds, de nombre de connexions, ou bien une augmentation de la mobilité des nœuds.
Elle est bien exprimée pour les trois protocoles dans chacun des figures représentées ci-dessus.
En théorie, les protocoles proactifs doivent avoir une consommation régulière en matière de
paquets de contrôles. Par contre les réactifs utilisent de plus en plus ces paquets avec
l’augmentation de la demande, dans notre cas on a une augmentation au niveau du nombre de
nœuds, au niveau de connexion et au niveau de mobilité. Le proactif DSDV semble être assez
stable et pour le cas du réactif AODV, il augmente naturellement son besoin en paquets de
contrôle. Il est assez pareil pour le réactif DSR qui semble croitre son utilisation en contrôle avec
l’augmentation de nombre de nœuds mais celle-ci n’est pas remarquable et il est à mentionner
qu’aucun des trois protocoles ici ne représente donc pas une contradiction avec les théories.
Cela s’explique qu’en termes de coût, le protocole DSR est le moins couteux par rapport aux deux
autres. Elle peut donc s’adapter dans un réseau de plusieurs nœuds, de plusieurs connexions ainsi
que dans un réseau de forte mobilité en minimisant le nombre des paquets de contrôle.
5.5.2 Taux de perte des paquets
Pour ce scenario nous avons six figures côte à côte représentant chacun l’allure de perte de
paquets en utilisant les trois protocoles. La côté gauche illustre la perte de paquets en trafic cbr
d’UDP et celle de droite illustre le nombre de paquets perdus au trafic ftp du TCP, tous deux en
fonction de la variation de nombre de nœud, de nombre de connexions ainsi qu’à la vitesse de
mobilité.
61
CBR TCP
Figure 5.09 :taux de perte en fonction de nombre de connexions
La figure 5.09 montre le taux de perte des paquets en fonction de nombre de connexions. En
augmentant le nombre de connexions CBR, les trois courbes semblent voisines à partir de quatre
connexions qui augmentent petit à petit suivant l’augmentation de nombre de connexion. Les deux
protocoles réactifs perdent plus de paquets à partir de 8 connexions TCP, cependant DSDV ne
dépasse pas le 50% de perte de paquets. Il est à noter que DSDV reste en-dessous des deux
protocoles AODV et DSR tel est le trafic utilisé.Bref, pour minimiser la perte de paquets il est
préférable d’utiliser le protocole DSDV dans un réseau de plusieurs connexions quel que soit le
trafic UDP ou TCP.
62
CBR
TCP
Figure 5.10 :taux de perte en fonction de la vitesse de nœuds
En termes de mobilité, le protocole proactif DSDV se montre désavantageux par rapport aux deux
autres réactifs vu qu’il se situe au-dessus de DSR et AODV. En termes de transmission en trafic
TCP, la perte de données est presque négligeable pour DSR et AODV.
UDP TCP
Figure 5.11 :La perte des paquets en fonction de la variation de nombre de nœuds
63
La première figure présente trois courbes bien distinctes, il y a DSR et AODV qui semblent
voisines et aussi tous deux des protocoles réactifs mais le protocole proactif DSDV reste au-
dessous et prend son petit coin à lui tout seul. Ainsi, on peut dire que DSDV perd moins de
paquets CBR (UDP) par rapport aux réactifs AODV et DSR. Ici, DSDV ne dépasse pas le taux de
perte de paquets CBR de 12%, contrairement aux deux autres qui dépassent de 11.90% à 26% de
perte de paquets CBR.
Pour la deuxième figure représentant la perte de paquets de type TCP. Les deux courbes de
protocole réactifs restent voisines et plus stables, ils semblent insensibles à l’augmentation de
nombre de nœuds. Contrairement au protocole proactif DSDV, qui semble perturber au trafic de
type TCP. L’explication que nous pouvons donner à ce phénomène est que le trafic de type TCP
nécessite un établissement de connexion avant l’envoie de données et un accusé de réception pour
assurer la livraison. Alors on peut en conclure que le protocole proactif DSDV supporte moins le
trafic TCP que celui d’UDP.
Il n’y a pas de logique théorique qui prévoit la réduction de taux de perte de paquets avec
l’augmentation de nombre de nœuds. Quand il y a plusieurs nœuds à l’environ, en deux dimension
(2D) l’interférence magnétique augmente donc il est possible que les liaisons se rompent
provoquants ainsi la perte de paquets. De l’autre côté, en trois dimension (3D) l’existence de ces
nœuds rendent meilleur la transmission des paquets en se servant les autres nœuds comme des
routeurs intermédiaire.
On peut dire qu’en termes de transmission de données de type UDP, il vaut mieux utiliser le
protocole de catégorie proactif tel que le DSDV. Et pour la transmission de type TCP, il est
préférable d’utiliser les protocoles réactifs tels que AODV et DSR. Tout en fonction de la
variation de nombre de nœuds.
5.5.3 Taux de paquet délivré
Nous avons ici trois figures représentant chacun le taux de paquets livrés avec succès du trafic
CBR et du trafic TCP.
64
CBR TCP
Figure 5.12 :Taux de paquets livrés avec succès en fonction de nombre de nœuds
La figure 5.12 montre d’abord que le taux de livraison de paquets de données diminue légèrement
si le nombre de nœuds augmente de plus en plus. On peut dire qu’en termes de livraison de
paquets de type udp, le protocole DSDV est dans l'ordre plus efficace par rapport au protocole
AODV et DSR. Pour la transmission des paquets de type tcp, DSDV semble perturber, nous avons
vu précédemment que le protocole DSDV supporte moins le transfert des paquets TCP.
65
CBR
TCP
Figure 5.13 : taux de paquet délivré avec succès en fonction de nombre de connexions
Sur la figure 5.13, les trois courbes se comportent de façon régressive pouvant être déduit comme
étant l’inverse du nombre de connexions en fonction du taux de perte des paquets et décrivant le
taux de paquet délivré en fonction de nombre de connexions. Dans ce stade, à chaque fois qu’il y
ait diminution du nombre de connexions CBR, les trois courbes semblent voisines à partir de
quatre connexions qui décroissent petit à petit suivant la diminution du nombre de connexion. Les
deux protocoles réactifs perdent plus de paquets à partir de 8 connexions TCP d’après
l’interprétation de la figure 5.09 ce qui engendra une diminution de paquet à délivrer dans ce cas.
On peut dire que le protocole DSDV est plus performant en termes de livraison de paquets car elle
se situe au-dessus des deux autres protocoles ce qui signifie qu’il délivre plus de paquets même en
augmentant le nombre de trafic dans le réseau que ce soit TCP ou UDP.
66
CBR
TCP
Figure 5.14 :taux de paquet délivré avec succès en fonction de la vitesse de nœuds
La figure 5.14 montre qu’avec une faible mobilité, le protocole DSDV délivre plus de paquets de
trafic UDP que les deux autres, mais en augmentant la vitesse de nœuds à partir de 12m/s les deux
autres protocoles réactifs deviennent plus avantageux que DSDV. En termes de trafic TCP, DSDV
se montre désavantageux alors que les protocoles réactifs AODV et DSR atteigne une livraison
maximale de paquets TCP de l’ordre 90% à 100% quel que soit la mobilité des nœuds.
Donc, nous pouvons en déduire qu’il est préférable d’utiliser le protocole DSDV dans un réseau
de faible mobilité surtout au trafic UDP, mais pour celui de TCP il est nécessaire d’utiliser les
protocoles réactifs tel que AODV et DSR.
5.5.4 Délai de bout en bout (EED End to End Delay)
Nous avons ici six figures représentant le temps écoulé entre l’envoi d’un paquet par un émetteur
et sa réception par le destinataire ou délai de bout en bout. Celle-ci est représentée en fonction de
la variation de nombre de nœud, de nombre de nœuds et la vitesse de nœuds.
67
CBR
TCP
Figure 5.15 :délai de bout en bout en fonction de la vitesse de nœuds
Nous constatons dans le trafic CBR que le protocole DSDV et AODV est plus efficace en termes
de délai d’envoi de données que DSR, cela due à l’utilisation de table de routage auquel les routes
sont connues en avance. Mais en termes de trafic TCP, le délai d’envoi de données est presque
négligeable pour AODV et DSR.
CBR
TCP
Figure 5.16 :délai de bout en bout en fonction de nombre de connexions
68
Suivant la variation de nombre de connexions quel que soit le trafic TCP ou UDP, les trois
protocoles assurent le délai de bout en bout à partir de 4 connexions.
CBR TCP
Figure 5.17 : Délai moyen de bout en bout en fonction de nombre de nœuds
A partir de la figure 5.17, nous constatons la différence entre le protocole proactif DSDV) et les
deux autres protocoles réactifs AODV et DSR.
Sur la première figure, nous remarquons que le protocole proactif est plus efficace par rapport au
protocole réactif tel qu’AODV et DSR. Cela peut être dû à la nature proactive de DSDV qui lui
permet de découvrir rapidement la route optimale et par la suite le temps de transmission des
paquets prend moins de temps par rapport aux protocoles réactifs AODV et DSR ce qui explique
des meilleures performances de DSDV en termes de délai de bout en bout.
La deuxième figure nous montre que les deux protocoles réactifs AODV et DSR ont le meilleur
délai de bout en bout en termes de trafic tcp. Contrairement au protocole DSDV, comme nous
l’avons déjà vu au paravent que ce dernier ne supporte pas le transfert tcp. Cela explique son
comportement instable en temps de livraison de paquets de type tcp.
69
5.6 Conclusion
Dans ce chapitre, nous avons parlé des environnements de simulation existant sur le marché en
mettant l'accent sur le NS2. Nous avons parlé de la philosophie de NS2 en générale avant de passé
en revue les paramètres de simulation que nous avons utilisée. Parmi ces modèles, nous avons
utilisé le modèle de mobilité « setdest » avec une variation de la vitesse de nœuds, le modèle de
trafic en variant le nombre de connexions dans le réseau, et enfin la variation de nombre de nœud
par espace qui définit la densité du réseau en général. Nous n'avons pas utilisé la version du
modèle de mobilité random waitpoint pour nos tests car ceci permet une variation aléatoire de
mobilité de nœud sur lesquels on n’aura pas la même situation dans chacun des simulations.
Notre objectif était de comparer les trois protocoles de routage adapté au réseau ad hoc tels que
AODV, DSR et DSDV de manière indépendante de tous scénarios de trafic ou de toute mise en
œuvre d’un protocole dans un simulateur. Pour cela, à l’aide d’une méthode de détermination de
meilleur protocole, nous avons simulé 4 métriques d’évaluation de performance. Nous avons
caractérisé l’overhead, le nombre de messages perdu ainsi que ce de délivrer, et le délai moyen de
transmission de données par un protocole de routage réactif ainsi que par un protocole de routage
proactif. D’une part, ces métriques dépendent fortement du nombre de trafic et de la dynamique
du réseau (mobilité et densité) qui implique des changements de topologie ou de position et donc
des reroutages. Nous avons donc comparé la performance de ces trois protocoles de routage en
prenant compte le protocole de transfert UDP et TCP et comme générateur de trafic CBR et FTP.
A partir des résultats trouvés, nous constatons qu'il n'y a pas un protocole qui est favori par rapport
aux autres dans tous les scénarios et les critères d'évaluation. Mais en général, on remarque qu’il
est préférable de choisir DSDV en termes de trafic CBR, parce que quel que soit la charge du
réseau, le nombre des nœuds, la densité du réseau, la variation de la vitesse ainsi que la variation
de nombre de connexions dans le réseau, le protocole DSDV performe bien en termes de coût de
routage, de délai de bout en bout ainsi que le taux de paquets délivré avec succès. Cela est
expliqué par leurs caractéristiques proactives, pourtant il est faible en trafic TCP. De son coté,
AODV et DSR ont de meilleures performances en termes de taux de paquets délivrés d’un trafic
TCP lorsqu’on les compare avec DSDV, ce dernier représente une instabilité lors de l’envoie de
paquets de trafic TCP.
Donc nous pouvons conclure que DSR et AODV devance DSDV quand on parle de réseau Ad-
Hoc surtout pour le trafic TCP. D’où les deux protocoles réactifs feront un bon sujet pour un
70
développement de nouveau protocole pour Ad-Hoc mobile. Les futures recherches doivent être
concentrées en améliorant le protocole DSR pour faire un niveau de performance élevé pour les
réseaux de l'Ad-Hoc mobile. Il faut juste que le protocole DSR s’adapte au trafic CBR et qu’il ait
une table de routage comme le protocole DSDV.
71
CONCLUSION GENERALE
La recherche dans le domaine des réseaux mobiles Ad hoc est en pleine essor. Plusieurs protocoles
de routage ont été développés ses dernières années. Dans cet article on a passé en revu quelques
protocoles de routage, dans le but de faire une étude des performances de ces derniers ? Nous
avons jugé utile de faire un aperu sur les paramètres (métriques) utilisés dans la littérature. Nous
en avons extrait les mieux appropriés pour mesurer les performances en termes de perte de
paquets et pour décider du meilleur d’entre eux sous des conditions particulières.
Le travail que nous avons effectué (simulation sous NS2), nous a permis de voir l’impact de la
densité ou la variation de nombre de nœuds sur le taux de perte pour les protocoles (DSR, DSDV,
et l’AODV).
Les résultats obtenus par la simulation doivent être pris comme une indication pertinente sur le
comportement de ces trois protocoles de routage Ad Hoc et non comme une représentation exacte
de son comportement en environnement réel, compte tenu de plusieurs contraintes de simulation à
savoir la dimension du champ de mouvement des nœuds mobiles, modèle de mobilité, le nombre
de nœuds mobiles, le type de trafic, le temps de simulation etc. Dans les études futures nous
essaierons d’évaluer les performances des protocoles de routage Ad Hoc avec différents modèles
de mobilité notamment le random waypoint. Enfin, il nous a permis de conclure que le choix du
protocole de routage dépend de plusieurs contraintes et qu’il est intéressant de considérer et de
combiner le maximum d’entre elles pour tirer les meilleurs profits.
72
BIBLIOGRAPHIE
[1] FD Gallo, « Wifi l’essentiel », Extraits de source diverses récoltées en 2003.
[2] P. Marvel, « Sécurité dans les réseaux ad hoc mobiles », cahier de charges : sécurité dans
les réseaux ad hoc mobiles, recherchegoogle.fr, avril 2014.
[3] E. Mathieu, « Les faisceaux hertziens et numériques », Cours DNAM, Octobre 2000
[4] N. Seddikl et M. Feham, « Etude comparative entre les procoles de routage de la QoS
dans les réseaux Ad Hoc », Laboratoire STIC, Faculté des sciences de l’Ingénieur,
Université et Tlemcen, 18 novembre 2009
[5] F. Barrere, « Les réseaux sans fils », DESS MIAG Université Paul Sabatier Toulouse, 2002
[6] Mateo, « Réseau sans fil »,http://www.siteduzero.com, Avril 2005
[7] Site CommentCaMarche.net – « Les réseaux sans fils » et « Le Wifi », Dossier réalisé par
Jean-François Pillou, Mars 2014
[8] N. Daujeard et J. Carsique, « Le routage dans les réseaux mobiles Ad Hoc », Année 2002-
2003
[9] S. Maarmar et A. Lamia, « Etude des Performances des Protocoles de Routage dans les
Réseaux Mobiles Ad Hoc », Département d’informatique, Faculté des sciences de
l’ingénieur, Université El Lakhdar – Batna, 03—04 Novembre 2007
[10] P. Mühlethaler, « 802.11 et les réseaux sans fil », Eyrolles, 2002.
[11] M. Sar, « Routage sécurisé des données dans les réseaux ad hoc ». Mémoire d’ingénieur
d’état en informatique, ESI, Ecole Nationale Supérieure d’Informatique deOued-Smar,
Alger. 2008/2009
[12] A. Khadidja, « Sécurité du routage dans les réseaux ad hoc mobile », Ecole doctorale
STIC, 2011/2012
[13] N. Younes, « la qualité de service des services multimédia sur les réseaux ad hoc sans fil à
multi-sauts », Mémoire de maîtrise en réseaux de télécommunications, école de
technologie supérieure université du Québec, 7 Août 2009
73
[14] Toh, « Ad Hoc Mobile Wirless Networks Protocols and Systems »: Age of Pervasive
Networks and Computing Upper Sadde River : Prentice Hall, C K 2002.
[15] Chakrabarti, Satyabrata, et Amitabh Mishra. “Quality of servise challenges for wireless
mobile ad hoc networks”. Wireless Communications, and Mobile Computing, vol. 4,
p.129-153
[16] Corson, S. ET J. Macker.“Routing protocol performance issues and evaluation
considerations”, Mobile Ad Hoc networking (MANET), RFC 2501, 1999
[17] T. Lemlouma. “Le Routage dans les Réseaux Mobiles Ad Hoc”, Université Houari
Boumediene, Institut d’Informatiques, Mini projet, Septembre 2000.
[18] M. Conti, and J. Liu. « Mobile ad hoc networking: imperative and challenge”; Ad Hoc
Networks, 2003
[19] X. Hong and G. Pei, “Fishey State Routing protocol (FSR) for ad hoc networks”, IETF
MANET Working Group, Internet Draft, 2002.
[20] Z. J. Haas, “A new routing protocol for the reconfigurable wireless networks”, Dans Proc.
6th IEE (ICUPC’97) (San Diego, CA, USA), vol. 2, p. 562-566.
[21] S.Tamilnadu “Comparative Analysis of CBRP, AODV, DSDV Routing Protocols in Mobile
Ad-hoc Networks”, Departement of Computer Science and Engineering, Sudharsan
Engineering College.
[22] “Ad hoc on demand Distance Vector”, http://fr.wikipedia.org/wiki/Ad-hoc_On-
demand_Distance _Vector, December 2014.
[23] “IEEE Mobile Ad Hoc Network”,http://ieeexploreee.org/xpl/, Novembre 2014
74
FICHE DE RENSEIGNEMENT
Nom : ANDRIANAVALONA
Prénom : Hajaniaina
Adresse : 26 CT Bis Ambohitsilaozana Ambatondrazaka 503
Téléphone : 034 27 536 51
Email : [email protected]
Titre du mémoire :
« ETUDE COMPARATIVE ET METHODE DE CHOIX DES PROTOCOLES DE ROUTAGE
DANS UN RESEAU MOBILE AD HOC »
Nombre de pages : 74
Nombre de tableaux : 6
Nombre de figures : 40
Mots clés : Protocole, routage, MANET, comparaison, NS2, simulation
Directeur de mémoire :
Nom : RASOLOMANANA
Prénoms : Jean Fanomezantsoa
Téléphone : 034 28 956 42
Email : [email protected]
RESUME
Actuellement dans la littérature, on rencontre un nombre assez important d’algorithme
d’algorithmes de routage dont certains ont fait l’objet de normalisation. Deux grandes classes
d’algorithmes de routage sont définies, la première est la classe des algorithmes réactifs et la
seconde celle des algorithmes proactifs. L’objectif de cet article est de faire une étude comparative
entre quelques algorithmes de routage, afin de pouvoir les classer selon différentes stratégies de
routage. Vu qu’ils ne reposent pas sur des modèles analytiques, l’évaluation exacte de certains
aspects de ces protocoles est très difficile. C’est la raison qui nous amène à faire des simulations
pour étudier leurs un classement des différents algorithmes de routage étudiés selon des métriques
telles que la perte de message, le délai de transmission, la mobilité, etc.
ABSTRACT
Currently in the literature, one meets a number important enough of algorithms of sorting
and mailing of which some were the subject of normalization. Two big classes of sorting and
mailing algorithms are defined, the first is the class of the reactive algorithms and the second the
one of the algorithms tabler-driven.The objective of this article is to make a comparative survey
between some algorithms of sorting and mailing in order to be able to classify them according to
different strategies. Since they don’t rest on analytic models, the exact assessment of some aspects
of these protocols is very difficult. It is the reason that brings us to make some simulations to
study their performances. Our simulation is achieved under NS2 (Network Simulator 2). It
permitted to clear an ordering of the studied different algorithms of sorting and mailing according
to the metrics as the loss of message, the transmission delay, the mobility, etc.
