Etude et évaluation des performances du protocole de

République Algérienne Démocratique et Populaire

Ministère de l’Enseignement Supérieure et de la Recherche Scientifique

Université Abderrahmane Mira De Bejaïa

Faculté des Sciences Exactes

Département d’Informatique

MEMOIRE DE FIN DE CYCLE

En vue de l’obtention du diplôme d’un Master en Informatique

Option : Administration et Sécurité des Réseaux

Thème

Etude et évaluation des performances du

protocole de routage OLSR dans les réseaux

sans fil ad hoc

Réalisé par :

Mr AIT OUAKLI Yacine Devant le jury composé de :

Mr MAALIOU Loucif Président : Mr DJEBARI Nabil

Examinatrice : Mme TASSOULT N

Encadreur : Mr MEHAOUED Kamal

Promotion 2016-2017

Remerciements

Il nous est spécialement agréable, d’exprimer toute

notre reconnaissance envers les personnes qui de prés ou

de loin nous ont apporté leurs soutiens dans la réalisation

de ce projet.

Au premier rang notre promoteur Monsieur

MEHAOUED Kamal, son aide, ses conseils précieux, ses

critiques constructives, ses explications et suggestions

pertinentes qui nous ont donné un coup d’aide pour réaliser

ce mémoire.

Nous remercions de même nos familles pour leurs

grandes attentions, leurs grands soutiens et

encouragement tout au long de l’évolution de ce travail, et

de l’énorme intérêt qu’ils ont montré envers ce sujet. Enfin

notre gratitude s’exprime pour les membres de jury pour

avoir accepté de juger notre travail.

Dédicaces

Nous dédions ce modeste travail à :

A nos très chers parents ;

A nos frères et sœurs ;

A nos grands parents ;

A nos cousins et cousines ;

A tous nos adorables amis (es) ;

A tous ceux qui nous sont chers ;

A tous nos enseignants.

I

Table des matières

Table des matière ……………………………………………………………………….…..….I

Liste des figures ………………………………………………………………….……..…….V

Liste des tableaux ……………………………………………………………………….......III

Liste des abréviations ………………………………………………………………………VIII

Introduction générale………………………………………………………………….….........1

Chapitre I : Généralités sur les réseaux mobiles ad hoc

1.1 Introduction…………………………………………………………………….………..…3

1.2 Environnement mobiles………………………………………………...……….…..……..3

1.3 Classification des réseaux sans fils ………………………………………………......…....3

1.3.1 Selon le domaine de couverture.…………………………...……..…..……………3

1.3.2 Selon le mode de fonctionnement ...……….………………..…...…..……………4

1.3.2.1 Réseaux avec infrastructure ...……….…………...…….........……………4

1.3.2.2 Réseaux sans infrastructure (ad hoc)………….……...…..…..……………5

1.3.3 Selon la topologie du réseau...…..………………………………..………………..6

1.3.3.1 Topologie totalement connectées...…..……………………….…………...6

1.3.3.2 Topologie à station de base...…..………………………………………….6

1.3.3.3 Topologie à routage interne...…..…………………………………………6

1.3.3.4 Topologie combinées ou encore hybrides...…..……….…………….…….7

1.4 Réseaux ad hoc...…..………………………………………………………………….……7

II

1.4.1 Historique....…..………………………………………………………………..….7

1.4.2 Définition d’un réseau ad hoc...…..……………………………………………...8

1.4.3 Modélisation d’un réseau mobile ad hoc………….……...………………………8

1.4.4 Mode de communication dans les MANETS...…..………………………………9

1.4.5 Types des réseaux ad hoc...…..………………………………………...……….10

1.4.5.1 Les réseaux de capteurs WSN (Wireless Sensor Networks) ..………..10

1.4.5.2 Les réseaux maillés WMN (Wireless Mesh Networks) ……………...10

1.4.6 Caractéristiques des réseaux ad hoc………………………………………….....10

1.4.7 Avantages et inconvénients des réseaux ad hoc ………………………....…......12

1.4.7.1 Les avantages ………………………………………...……………….12

1.4.7.2 Les inconvénients……………………..………………………………12

1.4.8 Domaines d’application des réseaux ad hoc .………….….….……..………….12

1.5 Conclusion …………………………………………………………………...……….….13

Chapitre II: Le routage dans les réseaux ad hoc

2.1 Introduction……………………………………………………………………….…..…..14

2.2 Définition du routage ……………………………………………………...…………..…14

2.3 La difficulté de routage dans les réseaux ad hoc .………….………………………….….14

2.4 Les contraintes de routage dans les réseaux ad hoc …………….……………………..…14

2.5 Techniques de routages ……………………………………………………….....………15

2.5.1 Routage hiérarchique ou plat…………………...…………………………........15

2.5.2 Le routage à la source et le routage saut par saut………………………...…….16

2.5.3 Etat de lien et Vecteur de distance………………………..……………..…..…17

III

2.5.4 L'inondation ……………………………………...………………..…..….........17

2.5.5 Le concept de groupe …………………………………………..…………..….18

2.5.6 Protocoles uniformes et non-uniformes………………………………....…..…19

2.6 Définition d’un protocole de routage……………………………………………………..19

2.7 Classification des protocoles de routage ……………………..…….…………….………19

2.7.1 Protocoles de routages proactifs …………………..……………………………20

2.7.2 Protocoles de routages réactifs …………………………….…………………...20

2.7.3 Protocoles de routage hybride.…… ………………………………..…………..21

2.8 Description de quelques protocoles de routages …………………………………………21

2.9 Conclusion ……….……………………..………………………………………………..23

Chapitre III : Le protocole de routage OLSR

3.1 Introduction ………………………………………………………………………………24

3.2 Présentation du protocole de routage OLSR..……………………...……………………..24

3.3 Le format du paquet OLSR …………...........………………………………………….....24

3.4 Principe du relais multipoint (MPRs) ……………………………………………………26

3.5 Fonctionnement du protocole OLSR …………………………………………………….28

3.5.1 Les messages échangés…………………………………………………...…….29

3.5.1.1 Le message HELLO ……………………………………………….…….29

3.5.1.2 Le message TC……………………………………………………..…….30

3.5.1.3 Le message MID (Multiple Interfaces Declaration)………….………….31

3.5.1.4 Le message HNA (Host and Network Association)……… …………….31

3.5.2 Détection de voisinage………………………………………………………….32

IV

3.5.3 Gestion de topologie…………………………………………………………….32

3.5.4 Le routage………………………………...……………………………………..34

3.6 Avantages et inconvénients d’OLSR……………………………………………………..35

3.6.1 Avantages……………………………………………………………………….35

3.6.2 Inconvénient…………………………………………………………………….35

3.7 Conclusion …...………………………………………………………………………….35

Chapitre IV : Simulation du protocole OLSR

4.1 Introduction…...…………………………………………………….…………………….36

4.2 Présentation du Network Simulator 2…...……………………….……………………….36

4.2.1 Définition…...…………………………………………….…………………….36

4.2.2 Architecture du NS2…...………………………….…………………………….36

4.3 Simulation et discussion des résultats…...……………………………………….……….37

4.3.1 Le protocole simulé…...……………………..………………………………….37

4.3.2 Paramètres de simulation choisis…..........................………….….…………….37

4.3.3 Présentation des différents scenarios de simulation …...……………………….37

4.3.3.1 Scenario 1 : Etudes par rapport au nombre de nœuds……………..….37

4.3.3.2 Scénario 2 : Etude par rapport à la mobilité…...………………..…….42

4.4 Discussion…...……………………………………………………………….……….45

4.5 Conclusion…...……………………………………………………………….……….45

Conclusion générale………………………………………………………………………......46

Annexe………………………………………………………………………..........................IX

Bibliographie………………………………………………………………………...........XXIV

V

Liste des figures

FIG 1.1 : Modèle des réseaux mobiles avec infrastructure.……….…………………………………5

FIG 1.2 : Modèle des réseaux mobiles sans infrastructure…………..………………………….…..5

FIG 1.3 : Topologie totalement connectée…………………………………………………………...6

FIG 1.4 : Topologie à station de base………………………………………………………………...6

FIG 1.5 : Topologie à routage interne………………………………………………………………..6

FIG 1.6 : Topologie hybrides………………………………………………………………….……..7

FIG 1.7 : Modélisation des réseaux ad hoc…………………………………………...…….………..8

FIG 1.8 : Changement de la topologie des réseaux ad hoc………………………….……………….9

FIG 1.9 : Différent modes de communication ad hoc…………………………………….………….9

FIG 1.10: Problème du nœud caché…………………………………………………………………11

FIG 2.1 : Routage à plat.………………………………………..…………………………….....….15

FIG 2.2 : Routage Hiérarchique……………………….……………………………………………16

FIG 2.1 : Le mécanisme d'inondation………………………………………………......…………..18

FIG 2.4 : La décomposition du réseau en group………………...………………………………….18

FIG 3.1 : Format du paquet OLSR. ………………………………………………………….……..25

FIG 3.2 : Principes de l’inondation classique et par MPR………………………...………………..27

FIG 3.3 : Format du message HELLO………………………………………………………...……29

FIG 3.4 : Format du message TC……………………………………………………………...……30

FIG 3.5 : Format de message MID………………………………………………………………….31

FIG 3.6 : Format de message HNA…………………………………………….…………….……..31

FIG 3.7 : Détection de voisinage par l’échange de messages HELLO…….………………………..32

VI

FIG 3.8 : Maintien d’une base de topologie avec les messages TC……………………………………....…33

FIG 3.9 : Format de la table de routage du protocole OLSR………………………………...……..34

FIG 4.1 : Architecture générale du NS…………………………………...………………………….37

FIG 4.2 : Cas 1 : Topologie du réseau simulé………………...…………...…………...……………38

FIG 4.3 : Cas 2 : Topologie du réseau simulé…………………...…………...…………...…………39

FIG 4.4 : Cas 1 : Débit en fonction de nombre de nœuds…………………...…………...………….40

FIG 4.5 : Cas 2 : Débit en fonction de nombre de nœuds……………………...…………...….……41

FIG 4.6 : Topologie du réseau au départ de la simulation……………………...…………...………42

FIG 4.7 : Topologie du réseau à la fin de la simulation……………………...…………...…………42

FIG 4.8 : Le débit en fonction de la mobilité des nœuds……………...…………...………….....….44

VII

TAB 1.1 : Classification des réseaux sans fil selon le domaine de couverture…………….……..3

TAB 4.1 : Modèle de simulation utilisé………………………………………………………….38

TAB 4.2 : Résultats de la simulation…………………………………………………………….39

TAB 4.3 : Modèle de simulation utilisé……………………………………………………….…40

TAB 4.4 : Résultats de la simulation………….…………………………………………………43

Liste des tableaux

VIII

Liste des abréviations

WPAN Wireless Personal Area Network

WLAN Wireless Local Area Network

WMAN Wireless Metroplitan Area Network

WWAN Wireless Wide Area Network

PRNe t Packet Radio Network

SURAN Survivable Radio Networks

IEEE Institute of Electrical and Electronics Engineers

WSN Wireless Sensor Networks

WMN Wireless Mesh Networks

l'AODV Ad hoc On Demand Distance Vector

OLSR Optimized Link State Routing

MANET Mobile Ad Hoc Networking working Groupe

IETF Internet Engineering Task Force

DSR Dynamic Source Routing

ZRP Zone Routing Protocol

DSDV Destination Sequenced Distance Vector

DBF Distributed Bellman-Ford

DSR Dynamique Source Routing

TBRPF Topology Dissemination Based on Reserve-Path Forwarding

ZRP Zone Routing Protocol

IARP Intr A zone Routing Protocol

IERP Int E zone Routing Protocol

BRP Broadcast Routing Protocol

INRIA Institut National de Recherche en Informatique et en Automatique

MPRs Principe du relais multipoint

TTL Time To Live

Vtime Temps de validité

1

Introduction générale

L’explosion de la communication téléphonique et informatique dans les dernières

années à donner naissance à une utilisation plus croissante des réseaux de communications.

L’apparition d’internet et son succès, et l’évolution des terminaux (ordinateurs, PDA,

téléphones, …) sont autant des éléments qui changeant notre vie, et la manière dont nous

utilisons ces technologies. Ce changement c’est aussi opéré dans notre relation avec les

moyens de communication. Dans un tel contexte il n’est pas surprenant de voir apparaitre des

solutions de communications sans fils de plus en plus performantes et évoluées.

La communication au sein de l’environnement mobile se base essentiellement sur la

transmission radio. Cet environnement mobile engendre de nouvelles caractéristiques propre à

lui : une fréquente déconnexion, un débit de communication et des ressources modeste et des

sources d’énergie limitées.

En 1999, l’IEEE (Institute of Electrical and Electronics Engineers) à standardisé le

protocole d’accès au medium radio 802.11 visant à assurer la communication entre

ordinateurs personnels utilisant le medium radio. Aujourd’hui, le protocole IEEE 802.11 a

subi plusieurs évolutions et est devenu un standard.

Les réseaux mobiles sans fil, peuvent être classés en deux grandes familles : Les

réseaux avec infrastructure et les réseaux sans infrastructure. La première classe aussi appelé

mode cellulaire, s’appuie sur une topologie construite autour de points d’accès fixe. Ces

derniers ont pour fonction de gérer les échanges entre les nœuds mobiles situés dans leur zone

de couverture. Par contre la deuxième classe aussi appelé mode ad hoc, ne requiert aucune

infrastructure fixe et qui font l’objet de notre étude.

En d’autres termes un réseau ad hoc est un réseau créé par une réunion de mobiles ne

disposant pas d’infrastructure fixe préexistante, interconnecté par une technologie sans fil

sans aucune forme d’administration ou de support fixe. Ce réseau est aussi caractérisé par sa

taille illimitée, c’est-à-dire aucune supposition ou limitation n’est faite sur la taille du réseau.

Les domaines d’applications des réseaux ad hoc sont nombreux, à titre d’exemple on peut

citer le domaine militaire et les applications tactiques comme l’opération de secours, les

missions d’exploration… etc.

Introduction générale

2

Dans ce type de réseaux chaque nœud joue le rôle d’un routeur et/ou d’un hôte, alors il

doit transmettre les paquets pour les autres nœuds du réseau, d’où la nécessité d’un protocole

de routage. Plusieurs protocoles de routages pour les réseaux ad hoc ont été développés,

suivants la manière de création et de maintenance de routes lors de l’acheminement des

données. Ces derniers peuvent être classifiés en trois catégories : les protocoles réactifs, les

protocoles proactifs et les protocoles hybrides.

Dans notre travail nous allons nous intéresser au protocole OLSR (Optimized Link

State Routing) qui est un protocole proactif appartenant à la famille des protocoles à état de

liens. Il se base sur la technique de relais multipoint, cette technique permet d’optimiser les

diffusions des messages de contrôles dans le réseau et la consommation de la bande passante.

Afin d’évaluer les performances de ce protocole et analyser son fonctionnement, nous

allons utiliser l’outil de simulation réseau NS2 (Network Simulator 2).

Ce mémoire est organisé en quatre chapitres :

Dans le premier chapitre, nous présentons les réseaux mobiles ad hoc, en commençant

par introduire les principaux concepts liés à ces environnements, par la suite nous citons

quelques applications et caractéristiques de ce type de réseau.

Dans le second chapitre, nous abordons le routage dans les réseaux ad hoc les

problématiques et les contraintes liées au routage ainsi que les techniques et différents

protocoles de routage et leurs principaux avantages et inconvénients.

Dans le troisième chapitre, nous présentons le protocole de routage OLSR, nous

expliquons le principe de fonctionnement de ce protocole, ainsi que les différents messages

échangés lors de l’établissement d’une communication entre les différents nœuds d’un réseau.

Et enfin dans le quatrième chapitre, nous présentant l’outil de simulation réseau NS2.

Nous allons analyser et discuter les résultats de simulations du protocole OLSR.

Nous terminons notre mémoire par une conclusion générale et quelques perspectives.

Chapitre I : Généralités sur les réseaux

mobiles ad hoc

Chapitre 1 : Généralités sur les réseaux mobiles ad hoc

3

1.1 Introduction

Les réseaux ad hoc sont un cas des réseaux mobiles. Ils sont le résultat de

l’interconnexion d’un grand nombre de nœud mobiles. Un réseau mobile ad hoc peut se

déployer facilement et rapidement sans aucune infrastructure fixe ou contrôle centralisé. Dans

ce premier chapitre, nous précisons les notions de base des réseaux ad hoc, l’historique, les

avantages et les inconvénients, les principales caractéristiques des réseaux ad hoc ainsi que les

domaines d’applications liés à ce type de réseaux.

1.2 Environnement mobiles

Un environnement mobile est un système composé de sites mobiles qui permet à ces

utilisateurs d’accéder à l’information indépendamment de leurs positions géographiques. Il

offre une grande flexibilité d’emploi. En particulier, il permet la mise en réseau des sites dont

le câblage serait trop onéreux à réaliser dans leur totalité, voire impossible.

1.3 Classification des réseaux sans fils

On peut classer les réseaux sans fils de plusieurs manières selon telle ou telle

caractéristiques, comme le domaine de couverture, le mode de fonctionnement, la topologie,

etc.

Dans ce qui suit nous donnons les classifications selon les paramètres cités :

1.3.1 Selon le domaine de couverture

Selon ce paramètre, on peut classer les réseaux sans fils en 4 catégories, WPAN

(Wireless Personal Area Network), WLAN (Wireless Local Area Network), WMAN

(Wireless Metroplitan Area Network), et WWAN (Wireless Wide Area Network).

(TAB 1.1) représente cette classification selon le domaine de couverture.

WPAN WLAN WMAN WWANStandard IEEE 802.15 IEEE 802.11 IEEE 802.16 IEEE 802.20

Technologies BluetoothHomeRFZifBeeLiaisons Infrarouges

WifiHiperLan2

WiMax GSMGPRSUMTS

Couverture Quelque dizaines demètres

Une centainede mètres

Quelquesdizaines dekilomètres

Une centainede kilomètres

Débit <1 Mbps 2 à 54 Mbps Jusqu’ à 70 Mbps 10 à 384 Kbps

Applications Point à pointéquipement àéquipement

Réseauxd’entreprise

Fixe, accés audernier kilomètre

GSMPDA…

TAB 1.1 – Classification des réseaux sans fil selon le domaine de couverture.


4

1.3.2 Selon le mode de fonctionnement

Selon ce paramètre nous distinguons deux classes, avec infrastructure et sans

infrastructure [1].

1.3.2.1 Réseaux avec infrastructure

Les réseaux mobiles avec infrastructure sont essentiellement des réseaux cellulaires,

qui ont été conçus comme extension des réseaux fixes afin de permettre aux utilisateurs des

réseaux classiques de se déplacer autour d’une station fixe, et ils ne sont plus encombrés par

des connexions filaires [2].

Les réseaux cellulaires intègrent deux ensembles d’entités distincts :

- Les sites mobiles (wireless network).

- Les sites fixes d’un réseau de communication filaire classique (wired network).

Certaines station fixes, appelé aussi stations de base (SB) sont munies d’une interface de

communication sans fil pour la communication directe avec les sites ou unités mobiles (UM), localisés

dans une zone géographique limitée, appelé cellule (FIG 1.1). Le concept cellulaire est introduit dans

les années 70 par les laboratoires Bell [2]. Il existe plusieurs types de cellules radio selon

l’environnement :

- Pico cellule : une zone de quelques mètres de diamètre. Elle est utilisée dans les

environnements de haute densité de population comme les bureaux, les supermarchés.

- Micro cellule : une zone de quelques dizaines de mètres de diamètre. Elle est utilisée

dans les rues entre les immeubles du quartier.

- Cellule : ce type couvre les zones urbaines. Le diamètre d’une cellule varie entre

quelque centaines de mètres et quelques kilomètres.

- Macro cellule : c’est une grande cellule dont le diamètre peut atteindre quelques

dizaines de kilomètres. Elle est utilisée sur les autoroutes et les véhicules à grande

vitesse.

- Cellule parapluie : son diamètre peut atteindre quelques centaines de kilomètre et

couvre de très larges zones comme les océans et les déserts.


5

A chaque station de base correspond une cellule à partir de laquelle des unités

mobiles peuvent émettre et recevoir des messages. Alors que les sites fixes sont

interconnectés entre eux à travers un réseau de communication filaire, généralement fiable et

d’un débit élevé, les liaisons sans fil ont une bande passante limitée qui réduit sévèrement le

volume des informations échangées [1].

Dans ce modèle, une unité mobile ne peut être, à un instant donné, directement

connectée qu’à une seule station de base. Elle peut communiquer avec les autres sites à

travers la station à laquelle elle est directement rattachée. L’autonomie réduite de sa source

d’énergie, lui occasionne de fréquentes déconnexions du réseau, sa reconnexion peut alors se

faire dans un environnement nouveau voire dans une nouvelle localisation.

1.3.2.2 Réseaux sans infrastructure (ad hoc)

Un réseau sans infrastructure ne comporte pas l’entité « site fixe », tous les sites du

réseau sont mobiles et se communiquent d’une manière directe en utilisant leurs interfaces de

communications sans fil (FIG 1.2). L’absence de l’infrastructure ou du réseau filaire composé

des stations de base, oblige les unités mobiles à se comporter comme des routeurs qui

participent à la découverte et à la maintenance des chemins pour les autres hôtes du réseau.

FIG 1.1 - Modèle des réseaux mobiles avec infrastructure.

UM

UM

UM

UM

UM

UM

UM

Portée de la communication

UM :

unités mobiles

FIG 1.2 - Modèle des réseaux mobiles sans infrastructure.

Réseau Statique

(Mbps à Gbps)

Cellules de communication sans filUM

UM

UM

UM

UM

UM

UM

UM

UM

UM

Station de base

Station de base

Station de base

Site fixe

Site fixe

Site fixe

Site fixe


6

1.3.3 Selon la topologie du réseau

Ils peuvent être catégorisés comme suite [3] :

1.3.3.1 Topologie totalement connectées

Tous les nœuds du réseau s’entendent et il n’y a donc nul besoin de protocole de

routage (FIG 1.3).

1.3.3.2 Topologie à station de base

Ce modèle met en œuvre une station de base qui centralise les communications entre

les nœuds du réseau. L’unique moyen de communication pour un nœud est de passer par cette

station de base (FIG 1.4).

1.3.3.3 Topologie à routage interne

Dans cette architecture, les nœuds ne s’entendent pas tous. Le réseau se base sur un

routage interne entre ses membres (FIG 1.5).

FIG 1.3 - Topologie totalement connectée.

Nœud

Lien sans fil

FIG 1.4 - topologie à station de base.

FIG 1.5 - Topologie à routage interne.

Nœud

Lien sans fil

Nœud

Lien sans fil

Station de base


7

1.3.3.4 Topologie combinées ou encore hybrides

Souvent on trouve un mélange de type de réseaux, combinant une architecture filaire

avec des réseaux sans fil (FIG 1.6).

1.4 Réseaux ad hoc

1.4.1 Historique

Les premières applications dans les réseaux ad hoc sont apparues en 1972 avec le

projet PRNet [4] (Packet Radio Network) dans le but d’améliorer les communications dans le

domaine militaire. Dans ce contexte il n’existe pas d’infrastructure existante pour relier les

communications, vue la nature dynamique des opérations et des champs militaires.

Le projet PRNet a été inspiré de la technologie par commutation de paquet, le partage

de la bande passante, le routage stor-and-forward, et ces applications dans l’environnement

mobile sans fil.

En suite en 1983, pour dresser les principaux problèmes du projet PRNet le

département de défense américain DARPA a développé le projet SURAN (Survivable Radio

Networks) [4] précisément les problèmes liés à la sécurité, la capacité de traitement, et gestion

d’énergie en proposant des algorithmes qui peuvent supporter une dizaine de milliers de

nœuds, toute en utilisant des mécanismes radio simple, avec une faible consommation

d’énergie, et un faible cout.

A partir des années 90 le groupe de travail MANET a lancé des recherches dans ce

domaine, il a pris son essor par l’arrivée des technologies radio, spécialement la norme IEEE

802.11 et ces différentes dérivées. Cette norme a été standardisée en 1999 par l’IEEE

(Institute of Electrical and Electronics Engineers), dans le but d’assurer la communication

entre ordinateurs utilisant le medium radio.

Nœuds

Lien sans fil

Lien filaire

Station de

base

FIG 1.6 - Topologie hybrides.


8

1.4.2 Définition d’un réseau ad hoc

L’IETF, le corps responsable de l’évolution d’internet, fournit la définition suivante :

Un réseau ad hoc mobile (aussi appelé MANET) est un système autonome de routeurs

mobiles (et d’hôtes associés) connectés par les liens sans fil. Les routeurs sont libre de se

déplacer aléatoirement et de s’organiser arbitrairement, donc la topologie du réseau peut

changer rapidement et de façon imprévisible. Un tel réseau peut opérer dans un mode

autonome, ou peut être relié à internet. Les MANET sont utiles dans beaucoup d’applications

parce qu’ils n’ont pas besoin de tout support de l’infrastructure [5].

1.4.3 Modélisation d’un réseau mobile ad hoc

Un réseau mobile ad hoc (MANET), consiste en une grande population, relativement

dense, d’unités mobiles qui se déplacent dans un territoire quelconque et dont le seul moyen

de communication est l’utilisation des interfaces sans fil, sans l’aide d’une infrastructure

préexistante ou administration centralisé. Un réseau mobile ad hoc peut être modélisé par un

graphe G(t)= (V(t), E(t)), tel que :

V(t) : est l’ensemble des nœuds (les unités ou les hôtes mobile) du réseau.

E(t) : est l’ensemble des connexions qui existent entre ces nœuds (liens de communications).

Cette présentation de topologie du réseau est dynamique, car elle peut changer sa

forme au fur et a mesure. Dans la (FIG1.7) on présente un réseau mobile sous forme d’un

graphe [1].

Nœud (ou unité

mobile)

Lien de

communication

2

1

3

4

68

9

10

7

5

FIG1.7 – Modélisation des réseaux ad hoc.


9

1.4.4 Mode de communication dans les MANETS

Les réseaux mobiles ad hoc utilisent, trois principaux modes de communication :

- Communication point à point ou unicast: on spécifie le nœud suivant sur la route

d’un paquet de données.

- Communication multipoints ou multicast: chaque nœud source va transmettre ces

paquets à un groupe de nœuds.

- Communication par la diffusion ou broadcast: dans ce mode un nœud source va

transmettre les paquets à tous les nœuds voisins, chaque nœud mobile réémet à son

tour les paquets qu’il reçoit à la première fois à ses voisins jusqu’à ce qu’ils arrivent à

la destination.

Ces trois modes de communication sont schématisées dans la figure ci-dessous :

FIG 1.8 – Changement de la topologie des réseaux ad hoc.

1

2

3

4

5

6 1

2

4

3

5

6

Déplacement des nœuds

Après mouvement

Lien de communication

FIG 1.9 – Différent modes de communication ad hoc.

MulticastUnicast Broadcast

1

S

3

2

D

4

2 D

D

D

1

S

S

DD

D

D

D


10

1.4.5 Types des réseaux ad hoc

1.4.5.1 Les réseaux de capteurs WSN (Wireless Sensor Networks)

Dans un WSN les nœuds capteurs sont statiques, la communication est initiée toujours

vers ou à partir des nœuds puits qui sont plus sensible à la panne qu’à celle des capteurs, mais

les communications capteur à capteurs sont rares.

1.4.5.2 Les réseaux maillés WMN (Wireless Mesh Networks)

C’est un réseau dans lequel deux stations de travail peuvent être mises en relation par

différents chemins. Cette mise en relation s’effectue à l’aide de commutateurs, chaque

commutateur constituant un nœud du réseau.

1.4.6 Caractéristiques des réseaux ad hoc

Le déploiement des réseaux ad hoc est d’une part simple puisqu’il suffit de disposer

d’un certain nombre de terminaux dans un espace quelconque, et d’autre part puisqu’il est

immédiatement fonctionnel dès lors que les terminaux sont présent.

Certain autres caractéristiques peuvent être dégagées pour ce type de réseaux :

L’absence d’infrastructure : Les réseaux ad hoc se distinguent des autres réseaux

mobiles par la propriété d’absence d’infrastructure préexistante et de toute administration

centralisée. Les hôtes mobiles sont responsables de l’établissement et du maintien de la

connectivité du réseau de manière continue.

Une topologie dynamique : Les unités mobiles du réseau, se déplacent d’une façon

libre et arbitraire. Elles peuvent accéder au réseau ou en sortir. De ce fait, la topologie du

réseau peut changer à tout moment, de manière rapide et aléatoire. Les liens de la topologie

peuvent être unis ou bidirectionnels.

Une bande passante limitée : Une capacité variable des liens : La bande passante est

limitée et restreinte si l’on compare à celle offerte dans les réseaux filaires, puisque le canal

de transmission sans fil est partagé. La congestion est une des conséquences du problème de

la limitation de la bande passante qui est encore alourdi par la diffusion. En effet, tout paquet

de diffusion émis vers une station en cours de communication (que ce paquet lui est destiné

ou pas) va altérer la communication de cette station.

Des contraintes d’énergie : Les hôtes mobiles sont alimentés par des sources

d’énergie autonomes comme les batteries ou d’autres sources consommables. Le paramètre

énergie semble très important car il affecte la durée de vie du réseau : les nœuds doivent

ajuster leur consommation d’énergie pour pouvoir atteindre les voisins ou la destination. De

ce fait, il doit être pris en considération dans tout contrôle fait par le système. Plusieurs

équipes de recherche se penchent sur ce point afin d’améliorer les performances énergétiques

des systèmes sans pour autant affecter les applications.


11

Une sécurité limitée : Les réseaux ad hoc sont plus touchés par le paramètre de

sécurité, que les réseaux filaires classiques. Dans ces derniers, fournir une sécurité au réseau

parait simple du fait de l’utilisation d’une administration centralisée. Cependant, les réseaux

ad hoc n’ont pas un nœud qui joue le rôle d’administrateur. De ce fait, les modèles de sécurité

des réseaux filaires sont inadaptés pour de tels réseaux. Pour pallier à ce problème, le contrôle

des données transférées doit être minimisé pour préserver à la fois les ressources et l’énergie.

Interférences : Les liens radio ne sont pas isolés, deux transmissions simultanées sur

une même fréquence ou utilisant des fréquences proches peuvent interférer [6].

Erreurs de transmission : elles sont plus fréquentes dans ce type de réseaux par

rapport aux réseaux filaires [7].

Problème du nœud caché : Ce phénomène est très particulier à l’environnement sans

fil. Une illustration très simple de ce problème est possible avec seulement trois stations A, B

et C positionnés comme dans la figure. B ne peut pas entendre C lorsqu’elle émet vers A, et

donc B considère pouvoir utiliser le canal. En cas d’émission de C, des collisions au niveau de

A seront donc causées.

FIG 1.10 – Problème du nœud caché.

B A C

Lien de communication Nœud mobile


12

1.4.7 Avantages et inconvénients des réseaux ad hoc

1.4.7.1 Les avantages

Les avantages des réseaux ad hoc sont nombreux du fait :

- Le cout d’exploitation d’un réseau ad hoc est faible : aucune infrastructure n’est à mettre

en place initialement et surtout aucun entretien n’est à prévoir.

- Simplicité et rapidité de déploiement : il suffit de disposer d’un certain nombre de

terminaux dans un espace quelconque pour créer un réseau ad hoc, et rapidité de

déploiement puisqu’il est immédiatement fonctionnel dès que les terminaux sont présents.

- Souplesse d’utilisation : les seuls éléments pouvant tomber en panne sont les terminaux

eux même, autrement dit il n’y a pas de panne pénalisante de manière globale (une station

qui sert au routage peut être remplacé par une autre si elle tombe en panne) [8].

1.4.7.2 Les inconvénients

Même si les perspectives pour les réseaux ad hoc sont prometteuses, plusieurs inconvénients

peuvent être dégagés des caractéristiques de ce type de réseaux, à savoir :

- La connectivité limite les possibilités de communication. Ainsi, deux stations ne sont

joignables que s’il existe un ensemble de stations pouvant assumer la fonction de routeur

afin de faire suivre des paquets de données échangées entre les deux stations.

- Les liens de communication ne sont pas isolés, ce qui engendre plusieurs problèmes de

congestion et d’alourdissement de bande passante (les diffusions).

- La sécurité est difficile à contrôler.

- Les contraintes d’énergie [8].

1.4.8 Domaines d’application des réseaux ad hoc

Les réseaux ad hoc sont utilisés dans toutes applications ou le déploiement d’une

infrastructure réseau filaire est trop contraignante, soit parce qu’il est difficile de le mettre en

place, soit parce que la durée d’exploitation du réseau ne justifie pas de câblage à demeure[1],

parmi ces applications :

- Application militaires : les équipements militaires peuvent prendre les avantages des

réseaux ad hoc pour maintenir la communication entre les troupes toute en se déplaçant

dans un champ de bataille.

- Opérations de secours : l’application d’un réseau ad hoc peut résoudre le problème de

difficulté d’installation d’un réseau filaire dans des régions désastreuse (incendie,

inondation, tremblement de terre …etc.).

- Les conférences : Un réseau ad hoc est efficace pour un groupe de gens qui veulent

partager des informations (connecter différente unité portables par exemple : palmtop,

PDA, notebook …etc.), lors d’une conférence.


13

- Applications commerciales : pour des paiements électroniques distants, accès mobile à

internet …etc.

- Réseaux de senseurs : des petits véhicules équipés de caméras et des détecteurs de son

pour collecter des informations dans une région donnée (climat, activités de terre, suivi

des mouvements d’animaux …etc.) et envoyer les informations via un réseau ad hoc.

- Réseaux véhiculaire : pour assurer l’échange de messages entre les véhicules routiers

(demande de secours, informations sur l’état de la route …etc.).

-

1.5 Conclusion

Dans ce chapitre nous avons présenté une description des réseaux ad hoc, les

principales caractéristiques de ce type de réseaux, ces différents domaines d’applications ainsi

que ces avantages et inconvénients. Dans le deuxième chapitre, nous allons présenter les

différents points sur le routage dans les réseaux ad hoc.

Chapitre II : Le routage dans les

réseaux ad hoc

Chapitre 2 : Le routage dans les réseaux ad hoc

14

2.1 Introduction

Le problème de routage dans les réseaux ad hoc se pose de la même façon que dans un

réseau fixe, la communication entre deux nœuds nécessite un protocole de routage pour

déterminer une route correcte pour l’acheminement des paquets. La différence réside dans

l’échelle du temps dans laquelle les changements de topologie se produisent dans l’internet et

nombres de ces changements sont d’un ordre de grandeur très inférieure au cas des réseaux ad

hoc. Dans ce chapitre nous allons aborder le routage, et nous décrirons ces différentes

contraintes, techniques, et classifications dans le cas des réseaux ad hoc.

2.2 Définition du routage

Le routage est une méthode d'acheminement des informations vers la bonne

destination à travers un réseau de connexion de 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 [9].

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.

2.3 La difficulté de routage dans les réseaux ad hoc

Cette difficulté réside dans les caractéristiques des réseaux ad hoc elles-mêmes, c’est à

dire, l’absence d’infrastructure fixe, la mobilité des nœuds, et la taille du réseau qui peut être

énorme. Plus précisément, l’absence de topologie fixe oblige les nœuds de jouer à la fois le

rôle d’hôte et de routeurs, ce qui veut dire que tous les nœuds du réseau contribuent au

routage et à la retransmission de paquets d’un nœud qui n’est pas en mesure d’attendre sa

destination. Et le fait que la taille du réseau peut être énorme, pose un problème lié à

l’adaptation de la méthode d’acheminement utilisée avec le grand nombre d’unités existantes

dans un environnement caractérisé par de modestes capacités de calcul et de sauvegarde.

D'ailleurs 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.

2.4 Les contraintes de routage dans les réseaux ad hoc

Vue les nombreuse difficultés de routage dans les réseaux ad hoc qu’on a citées

précédemment, il est nécessaire que la conception des protocoles de routages étudie les

problèmes suivant :

- La minimisation de la charge du réseau : Qui se caractérise dans l’amélioration des

ressources du réseau pour diminuer le nombre de boucles de routage et éviter la

concentration du trafic autour de certains nœuds ou liens.


15

- Offrir un support pour pouvoir effectuer des communications multipoints fiable :

Le fait que la structure des réseaux ad hoc est dynamique ne doit pas influencer le bon

acheminement des paquets vers leur destination. Ce qui veut dire que si un lien est

rompu pour cause de panne ou de mobilité devrait, idéalement, augmenter le moins

possible les temps de latence [10].

- Assurer un routage optimal : Ce qui se fait grâce à une stratégie de routage. Cette

dernière doit pouvoir prendre en compte différentes métriques (bande passante,

nombre de liens, ressources du réseau, …etc.) dans le choix et la création des chemins

optimaux, ce qui est déjà pas évident. Alors que la maintenance de ces chemins est une

tache encore plus complexe que la stratégie de routage doit assurer avec le moins de

cout possible [10].

- Le temps de latence : La qualité des temps de latence et de chemins doit augmenter

dans le cas où la connectivité de réseau augmente.

2.5 Techniques de routages

Vue la difficulté de routage dans les réseaux ad hoc, les stratégies existantes utilisent

une variété de techniques afin de résoudre ce problème. Suivant ces techniques, plusieurs

classifications sont apparues, parmi lesquelles nous allons citer :

2.5.1 Routage hiérarchique ou plat

Le premier critère utilisé pour classifier les protocoles de routage dans les réseaux ad

hoc concerne le type de vision qu'ils ont du réseau et les rôles qu'ils accordent aux différents

mobiles.

Les protocoles de routage à plat

Considèrent que tous les nœuds sont égaux (FIG2.1). La décision d'un nœud de router

des paquets pour un autre dépendra de sa position. Parmes les protocoles utilisant cette

technique, on cite l'AODV (Ad hoc On Demand Distance Vector).

N7 N10

N9

N11

N2

N3N1

N4

N5

N6

N8

FIG 2.1 -Routage à plat


16

Les protocoles de routage hiérarchique

Fonctionnent en confiant aux mobiles des rôles qui varient de l'un à l'autre. Certains

nœuds sont élus et assument des fonctions particulières qui conduisent à une vision en

plusieurs niveaux de la topologie du réseau. Par exemple, un mobile pourra servir de

passerelle pour un certain nombre de nœuds qui se seront attachés à lui. Le routage en sera

simplifié, puisqu'il se fera de passerelle à passerelle, jusqu'à celle directement attachée au

destinataire. Un exemple est donné sur la figure (FIG 2.2), où le nœud N3 passe par les

passerelles P1, P2 et P3 pour atteindre N7. Dans ce type de protocole, les passerelles

supportent la majeure partie de la charge du routage (les mobiles qui s'y rattachent savent que

si le destinataire n'est pas dans leur voisinage direct, il suffit d'envoyer à la passerelle qui se

débrouillera). Un exemple de protocole utilisant cette stratégie est l’OLSR (Optimized Link

State Routing)

2.5.2 Le routage à la source et le routage saut par saut

Le routage à la source

le routage à la source ou « source routing » consiste à indiquer dans le paquet routé

l'intégralité du chemin que devra suivre le paquet pour atteindre sa destination. L'entête de

paquet va donc contenir la liste des différents nœuds relayeur vers la destination. Le protocole

le plus connu basant sur cette classe est : DSR.

Le routage saut par saut

le routage saut par saut ou «hop by hop» consiste à donner uniquement à un paquet

l'adresse du prochain nœud vers la destination. AODV fait partie des protocoles qui utilisent

cette technique.

N2

N1N3

N5

N4 N6

N8

N7

P1

P2

P3

FIG 2.2 - Routage Hiérarchique


17

2.5.3 Etat de lien et Vecteur de distance

Autres classification, héritée du monde filaire, est possible pour les protocoles de

routage : les protocoles basés sur l'état des liens et ceux basés sur le vecteur de distance. Les

deux méthodes exigent une mise à jour périodique des données de routage qui doivent être

diffusées par les différents nœuds de routage du réseau. Les algorithmes de routage basés sur

ces deux méthodes, utilisent la même technique qui est la technique des plus courts chemins,

et permettent à un hôte donné, de trouver le prochain hôte pour atteindre la destination en

utilisant le trajet le plus court existant dans le réseau.

Les protocoles basés sur l'état de lien

La famille des protocoles à état de liens se base sur les informations rassemblées sur

l'état des liens dans le réseau. Ces informations sont disséminées dans le réseau

périodiquement ce qui permet ainsi aux nœuds de construire une carte complète du réseau. Un

nœud qui reçoit les informations concernant l'état des liens, met à jour sa vision de la

topologie du réseau et applique un algorithme de calcul des chemins optimaux afin de choisir

le nœud suivant pour une destination donnée. En générale ces algorithmes se basent sur le

principe de l'algorithme de « Djikstra » pour calculer les chemins plus courts entre un nœud

source et les autres nœuds du réseau. Les principaux protocoles de routage dans les réseaux ad

hoc qui appartiennent à cette classe sont les suivants : TORA, OLSR et TBRPF

Les protocoles basés sur le vecteur de distance

Les protocoles à vecteur de distance se basent sur un échange, entre voisins, des

informations de distances des destinations connues. Chaque nœud envoie à ses voisins la liste

des destinations qui lui sont accessibles et le coût correspondant. Le nœud récepteur met à

jour sa liste locale des destinations avec les coûts minimums. Le processus de calcul se répète,

s'il y a un changement de la distance minimale séparant deux nœuds, et cela jusqu'à ce que le

réseau atteigne un état stable. Les calculs des routes se base sur le principe de l'algorithme

distribué de Bellman-Ford (DBF). Les protocoles de routage basés sur le vecteur de distance

les plus connus pour les réseaux ad hoc sont : DSR, DSDV et AODV.

2.5.4 L'inondation

L'inondation ou la diffusion pure, consiste à répéter un message dans tous les réseaux

.Un nœud qui initie l'inondation envoie le paquet à tous ses voisins directe, de même si un

nœud quelconque de réseau reçoit le paquet pour la première fois, il le rediffuse à tous les

voisins, Ainsi de proche en proche le paquet inonde le réseau (FIG 2.3) [11].


18

Notons que les nœuds peuvent appliqués (durant l'inondation) certain traitement de

contrôle dans le but d'éviter certains problèmes, tel que le bouclage et la duplication des

messages, Le mécanisme d'inondation est utilisé généralement dans la première phase du

routage plus exactement dans la procédure de découverte des routes, et cela dans le cas où le

nœud source ne connaît pas la localisation exacte de la destination.

2.5.5 Le concept de groupe

Dans la communication de groupe, les messages sont transmis à des entités abstraites

ou groupes, les émetteurs n'ont pas besoin de connaître les membres du groupe destinataire.

La gestion des membres d'un groupe permet à un élément de se joindre à un groupe, de quitter

ce groupe, se déplacer ailleurs puis rejoindre le même groupe. C'est en ce sens que la

communication de groupe assure une indépendance de la localisation, ce qui la rend

parfaitement basées sur les groupe. Le concept de groupe facilite les taches de la gestion du

routage (telles que les transmissions des paquets, l'allocation de la bande passante etc.) et cela

en décomposant le réseau en un ensemble de groupes connecté.

2.5.6 Protocoles uniformes et non-uniformes

Certains protocoles de routage n'utilisent pas tous les nœuds d'un réseau pour faire

transiter les messages, au contraire ils en sélectionnent certains, en fonction du voisinage ou

pour former des cellules. Ces protocoles sont dits non-uniformes. Ceux qui utilisent tous les

nœuds du réseau capables de router sont appelés protocoles uniformes.

FIG 2.3: -Le mécanisme d'inondation

L’utilisateur

FIG 2.4 -La décomposition du réseau en groupe


19

2.6 Définition d’un protocole de routage

C’est un ensemble de règles appliquées au format et à la signification des trames,

paquet ou message échangées entre les nœuds. Il doit être capable de suivre la nature

dynamique des réseaux ad hoc qui emmène à un changement dans la topologie [12].

2.7 Classification des protocoles de routage

La plupart des protocoles de routage prennent en compte trois phases :

La découverte de l’information de routage

Cette phase a pour rôle d’informer les nœuds communiquant des éléments essentiels sur la

topologie du réseau pour pouvoir choisir le chemin par lequel ils peuvent atteindre le nœud de

destination. Autrement dit, permettre aux nœuds d’avoir une vue précise sur la topologie du

réseau.

Le choix du chemin

Dans cette phase certaine critères doivent être respectés dans le choix du chemin :

- le nombre minimum de sauts dans la route (choisir le chemin le plus court vers la

destination).

- L’économie d’énergie.

- L’absence des boucles dans les routes.

Maintenance des routes

Les protocoles de routage doivent prendre en considération les changements de

topologies fréquents dans ce type de réseau, ce qui les obliges à une mise à jours permanente

des tables de routage pour éviter qu’un chemin reste invalide après un changement de

topologie du à la mobilité des nœuds.

Généralement dans les réseaux ad hoc on trouve trois types de protocoles de routage,

les protocoles de routage proactifs qui prévoient la demande de routage de paquet, les

protocoles de routage réactifs qui réagissent à la demande, et un mélange des deux types

précédant appelé protocole de routage hybrides qui utilisent à la fois les protocoles proactifs

et réactifs.


20

2.7.1 Protocoles de routages proactifs

Les protocoles de routage proactifs essaient de maintenir les meilleurs chemins

existants vers toutes les destinations possibles (qui peuvent représenter l'ensemble de tous les

nœuds du réseau) au niveau de chaque nœud du réseau, Les routes sont sauvegardées mê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, Le plus abouti de ces protocoles

est OLSR.

Avantages et inconvénient des protocoles de routage 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 changement 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 nouvel type de protocole a apparu, il s'agit des protocoles de routage

réactifs.

2.7.2 Protocoles de routages réactifs

Les protocoles de routage réactifs (dits aussi: protocoles de routage à la demande),

représentent les protocoles les plus récents proposés dans le but d'assurer le service du routage

dans les réseaux sans fils.

Des solutions proposée pour résoudre le problème de routage dans les réseaux ad hoc,

et qui sont évaluées actuellement par le groupe de travail MANET (Mobile Ad Hoc

Networking working Groupe) de l'IETF (Internet Engineering Task Force), appartiennent à

cette classe de protocoles de routage.

Les protocoles de routage appartenant à cette catégorie, créent et maintiennent les

routes selon les besoins. Lorsque le réseau a besoin d'une route, une procédure de découverte

globale de routes est lancée, et cela dans le but d'obtenir une information. Actuellement, le

plus connu de ces protocoles est AODV.

Avantages et inconvénients des protocoles de routage 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à.


21

De ce fait, un nouvel type de protocole a apparu, il s'agit des protocoles de routage

hybrides.

2.7.3 Protocoles de routage hybride

Dans ce type de protocole, on peut garder la connaissance locale de la topologie

jusqu'à un nombre prédéfini- a priori petit- de sauts par un échange périodique de trame de

contrôle, autrement dit par une technique proactive. Les routes vers des nœuds plus lointains

sont obtenues par schéma réactif, c'est-à-dire par l'utilisation de paquets de requête en

diffusion. Un exemple de protocoles appartenant à cette famille est le protocole ZRP (Zone

Routinier Protocol).

Avantages et inconvénient des protocoles hybrides

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.

Cependant, il rassemble toujours quelques inconvénients des deux approches

proactives et réactives.

2.8 Description de quelques protocoles de routages

Les protocoles décrits par la suite sont issues du groupe de travail MANET. Ces

protocoles sont représentatifs de diverses techniques et sont les plus avancés sur la voie d’une

normalisation, sachant qu’il a normalisé les protocoles de routages proactifs : OLSR (RFC

3626, octobre 2003) et TBRPF (RFC 3684, février 2004) ainsi que les protocoles réactifs :

AODV (RFC 3561, juillet 2003) et DSR (RFC 4728, février 2007).

DSDV (Destination Sequenced Distance Vector)

Il est principalement inspiré de l’algorithme distribué de Bellman Ford (DBF :

Distributed Bellman-Ford) [6]. Toutefois, chaque station mobile se voit contenir une table de

routage contenant, pour chaque destination, le voisin à joindre pour y parvenir, ainsi que le

nombre de sauts et un numéro de séquence. Une route R1 est considérée meilleur qu’une

route R2 si R1 à un numéro de séquence plus important (la route est plus récente donc les

informations ont plus de chances d’être correctes) ou si le numéro de séquence est le même

mais que la distance estimée vers la destination en empruntant la route R1 est plus faible.

Chaque station émet sa table de routage régulièrement en incrémentant le numéro de séquence

correspondant à la route menant à lui (le nœud qui est a émit ca table de routage). Quand une

station estime que sa route vers une autre est coupée, elle met à jour sa table de routage avec

une distance infinie. Afin de diffuser les mises à jour de la table, la station peut émettre deux

types de paquets : la table complète (full dump) ou uniquement les parties de la table qui ont

été modifiées (incrémental) afin de réduire l’utilisation du médium [13].


22

DSR (Dynamique Source Routing)

Le protocole DSR [14] utilise un routage par source, il utilise sur le principe de

diffusion à la demande pour calculer une route vers la destination. Il est basé sur deux

mécanismes coopératifs, la découverte de route et la maintenance de route. A partir des

informations de routage incluses dans les paquets de données, les nœuds appartenant à la

route, ainsi que les nœuds voisins, peuvent les collecter et les mettre dans leurs caches pour

une utilisation ultérieure.

Chaque nœud dans le réseau envoyant ou relayant un paquet est responsable de

confirmer son acheminement vers le prochain nœud en recevant un acquittement. Si un nœud

détecte une cassure de route, un message d’erreur de route est retourné à la source. Lors de la

réception d’un message d’erreur de route, la source supprime la route défaillante de son

cache. Si un chemin alternatif est disponible, il peut être employé pour les données restantes à

la destination, autrement, une nouvelle découverte de route est lancée. DSR bufférise les

paquets IP dans le nœud de source quand la découverte de route est effectuée.

TBRPF (Topology Dissemination Based on Reserve-Path Forwarding)

Il appartient à la famille des protocoles proactifs à état de liens. Les nœuds TBRPF

s’échangent périodiquement la liste de leurs voisins, et chacun construit un arbre de la

topologie offrant des routes vers les autres nœuds avec le nombre de sauts minimum. Les

arbres de topologies sont ensuite échangés à leurs tours entre voisins. Ceci permet de propager

les informations de la topologie dans tout le réseau.

Afin de détecter le voisinage, les nœuds TBRPF échanges périodiquement des

messages HELLO. Il en existe deux sortes : des HELLO contenant toute la liste des voisins et

des HELLO intermédiaires appelés HELLO différentiels, contenant les changements par

rapport au dernier HELLO envoyé. Chaque nœud calcule son arbre de topologie en utilisant

un algorithme Dijkstra modifié. En réalité, le nœud diffuse ensuite une partie de son arbre à

son voisinage.

Un nœud i sélectionne la partie de l’arbre à diffuser composé d’un ensemble de liens

(v, u) de la façon suivantes : s’il estime qu’un nœud voisin j choisit i comme prochain saut

pour atteindre une destination u avec un nombre de sauts minimum, alors (v, u) est inclus

dans ce sous arbre.

Les informations de topologie dans TBRPF sont disséminées principalement via un

échange périodique de son arbre de topologie. De plus, les nœuds envoient des messages de

topologie intermédiaires diffusant des informations supplémentaires sur les liens jugés

nécessaires pour atteindre certaines nœuds. TBRBF utilise la diffusion de topologie partielle,

mais ne s’interdit pas la possibilité de diffuser la topologie totale comme c’est le cas avec

STAR. La table de routage est calculée à chaque nœud et le routage des données s’effectue

saut par saut sans l’intervention directe de TBRPF.


23

ZRP (Zone Routing Protocole)

Il utilise deux approche (proactif et réactif), il limite la procédure proactif uniquement

aux nœuds voisins (les changements de topologie doivent avoir un impact local), et bien que

de nature global, offre une recherche rapide et efficace dans le réseau. Une zone de routage

est alors définie pour chaque nœud, elle inclut les nœuds qui sont à une distance minimale (en

termes de nombre de sauts), du nœud en question, inférieure ou égale au rayon ɤ de la

zone[6].

ZRP définit donc deux types de protocoles : l’un fonctionnant localement et le

deuxième fonctionnant entre zones. Ces deux protocoles sont cite :

IARP (IntrAzoneRouting Protocol)

Offrant les routes optimales vers les destinations qui se trouvent à l’intérieur de la

zone à une distance déterminée, et tout changement est répercuté uniquement à l’intérieur de

la zone.

IERP (IntEzoneRouting Protocol)

Quant à lui s’occupe de rechercher les routes à la demande pour les destinations en

dehors d’une zone.

En plus de ces deux protocoles, le ZRP utilise le protocole BRP (Broadcast Routing

Protocol) [6]. Ce dernier utilise les données de la topologie fournies par le protocole IARP

afin de construire sa liste des nœuds de périphérie et la façon de les atteindre. Il est utilisé

pour guider la propagation des requêtes de recherche de route de l’IERP dans le réseau.

2.9 Conclusion

Dans ce chapitre nous avons présenté le routage dans les réseaux ad hoc avec les

notions, problèmes, classification, et les différentes techniques utilisés. Ensuite, on a décrit

quelque protocoles de routage et expliquer leurs fonctionnement. Dans le chapitre suivant

nous allons détailler le protocole de routage OLSR.

Chapitre III :Le protocole de routageOLSR

Chapitre 3 : Le protocole de routage OLSR

24

3.1 Introduction

Lors de la transmission d'un paquet d'une source vers une destination, il est nécessairede 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 decomprendre leurs comportement dans des réseaux mobiles, nous nous sommes intéressés doncà faire une étude théorique sur le protocole OLSR.

OLSR représente diverses techniques, Il utilise un mécanisme qui permet de designerun sous-ensemble de son voisinage responsable de la dissémination des informations decontrôle de topologie dans les réseaux à moindre coût.

Ce protocole (OLSR) fait désormais l'objet d'une Request For Comment(RFC), tandisque les autres sont à des versions assez stabilités de leurs drafts.

Dans ce chapitre, nous allons présenter ce protocole, en commençant par une étude

détaillée de son principe de fonctionnement, ainsi que ses avantages et inconvénient.

3.2 Présentation du protocole de routage OLSR

OLSR a été proposé par l’INRIA (Institut National de Recherche en Informatique et en

Automatique) dans le cadre du projet HIPERCOM [16]. C’est un protocole de routage

proactif appartenant à la famille des protocoles à état de liens, il fonctionne dans des

environnements sans infrastructure et sans aucune entité centrale gérant et réagissant sur la

mobilité (réseaux ad hoc), il est utilisé dans des réseaux denses et peut mobile. Sa particularité

est l’utilisation de topologie partielle, les nœuds ne diffusent pas tous les liens qu’ils ont avec

leur voisins, mais seulement un sous ensemble de ces liens qui permettent de les joindre. Ceci

implique une réduction de la taille des paquets de contrôle diffusé dans le réseau. OLSR se

base sur la technique des relais multipoints (MPRs), ce qui permet une optimisation des

diffusions des messages de contrôle et de la bande passante.

3.3 Le format du paquet OLSR

Le protocole OLSR définit un format général du paquet pour tous les messages

circulant sur le réseau.

OLSR utilise un adressage IP comme un identifiant unique des nœuds du réseau. Il estcapable de fonctionner sur multiples interfaces de communications. De ce fait, chaque nœuddu réseau choisit l’une des adresses de ses interfaces comme son adresse principale.

OLSR est opérationnels dur les deux versions de IP (IPv4 et IPv6). La différenceréside dans la taille des adresses IP transmises dans les messages de contrôle ainsi que lataille minimale des messages. Dans la suite nous utiliserons un format d’adresses IPv4 et unformat de message compatible avec cette version.


25

Dans cette figure, nous allons présenter le format d’un tel paquet :

Il est constitué par :

-Taille du message (Packetlength) : la taille du paquet en octet.

-Numéro de séquence du paquet (Packetsequencenumber) : chaque paquet transmis à unnuméro de séquence.

-Type du message (Message type) : 1 Hello, 2 TC, 3 MID, 4 HNA.

-Temps de validité (Vtime) : indique pour combien de temps après la réception, un nœud doitconsidérer l’information contenue dans ce message comme valide, à moins qu’une mise à jourrécente de l’information ne soit reçue. Le temps de validité est calculé comme suite :

C*(1+(a/16))*2b en second, avec ‘a’ l’entier représenté par les quatre bits du poids le plus fort,‘b’ est l’entier représenté par les quatre bits du poids le plus faible, ‘C’est un facteurmultiplicatif (sa valeur dépend de l’implémentation).

-Taille du message (Message size) : la taille en octets, depuis le début de champ type demessage jusqu’ au début du message suivant (si il n’y a pas de message suivant, jusqu’à la findu paquet).

-Adresse de l’expéditeur (Originatoraddress) : contient l’adresse principale du nœud qui àgénérer le message.

-TTL (Time To Live) : entre 0 et 255, contient le nombre maximal de sauts qu’effectuera lemessage avant qu’un message ne soit retransmis, le TTL doit être décrémenter de 1. Quand unnœud reçoit un message avec un TTL égale à 1, le message n’est pas retransmis.

0 1 2 30 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9

Longueur du paquet N° de séquence du paquet Entête dupaquet

Entête dumessage

Type de message Temps se validité Taille du messageAdresse de l’expéditeur

TTL : nbremaximal de sauts

Nombre de sautsatteints

Numéro de séquence du message

MessageType de message Temp de validité Taille du message

Adresse de l’expéditeurTTL : nbre

maximal de sautsNombre de sauts

atteintsNuméro de séquence du message

Message:

FIG 3.1 -Format du paquet OLSR.


26

-Nombre de sauts atteint (Hop count) : contient le nombre de sauts a effectuer avant qu’unmessage ne soit retransmis, ce numéro doit être incrémenté de 1. Initialement, le hop count estmis à 0 par la source du message.

-Numéro de séquence du message (Message séquencenumber) : le nœud source assigne àchaque message un numéro de séquence qui est un identificateur unique. A chaque fois qu’unnœud génère un message, il incrémente le numéro de séquence de 1. Ces numéros deséquence sont utilisés pour s’assurer qu’un message donné n’est pas retransmis plus d’unefois par un nœud.

-Message (Data) : contient le message proprement dit que ce soit un HELLO, TC, MID, ouHNA ou un paquet de données.

3.4 Principe du relais multipoint (MPRs)

Cette technique vise à réduire le nombre de transmission inutiles, lors de la diffusiongénéralisée d’un message. En particulier, les MPR permettent l’acheminement des messagesde contrôle sur le réseau d’où une optimisation du mécanisme de diffusion classique.

Chaque nœud du réseau va sélectionner, indépendamment des autres nœuds, sonpropre ensemble de relais multipoints en se basant sur la connaissance de son voisinage àdeux sauts. Le nœud doit, par la suite informer ces voisins de leur nouveau rôle. Cet ensemblede MPR doit être recalculé à chaque fois que l’on détecte une modification dans le voisinage àdeux sauts. C’est pour cela que le statut des relais multipoints est conditionné par le voisinagepour une durée limitée.

La sélection des relayeurs doit se faire rapidement vu le contexte des réseaux ad hoc etavec un minimum nombre de calcule possible.

La manière dont un nœud sélectionne un voisin direct comme MPRS est la suivante:

-Chaque nœud doit connaitre l’ensemble de ces voisins ainsi que l’ensemble de ces voisins deniveau 2 (se situant à deux sauts).

-Un nœud sélectionne un voisin avec lui comme son MPRs, si ce dernier lui permetd’atteindre le maximum de nœuds voisins à deux sauts ou s’il est le seul qui lui permetd’atteindre un voisin donné au deuxième niveau.

Nous allons illustrer dans cette figure l’amélioration au niveau de la diffusion marqué par latechnique des relais multipoints par rapport à l’inondation classique.


27

(a) Réseaux maillé

(b) Principe de l’inondation classique

(c) Principe de l’inondation par MPR

A

Nœud OLSR

A

Nœud voisin direct affecté par l’inondation

Nœud à deux sauts couvert par les MPR

Nœud ne participe pas à l’inondation

Nœud MPR

FIG 3.2-Principes de l’inondation classique et par MPR.

A


28

Le choix des relais multipoint se fait suivant l’algorithme suivant :

On définit les notations suivantes :

N : ensemble des voisins directe d’un nœud x à travers l’interface I.

N2 : ensemble des voisins de niveau 2 accessibles à travers l’interface I excluant :

-Les nœuds accessible à travers un membre de N(x) avec <<Willingness = WILL_NEVER>>

-Le nœud en question x.

- Tous les nœuds voisins ayant un lien symétrique à travers l’une des interfaces.

D(y) : le degré d’un nœud de niveau 1 (y étant un élément de N(x)) est défini comme étant lenombre de voisins à liens symétrique en excluant tous les éléments de N(x) et le nœud x.

L’algorithme de cette heuristique se présente comme suit :

1. On commence par un ensemble de relais contenant tous les éléments de N(x) dontl’habilité à acheminer un trafic égal à WILL_ALWAYS.

2. Par la suite, on calcule D(y) pour tout y de N(x).3. Ajouter à MPR(x), les nœuds de N(x) qui sont les seuls à pouvoir acheminer le trafic à

un élément de N2(x). Par exemple, si un nœud b, élément de N2(x) est accessibleuniquement à travers un lien symétrique vers un nœud a, Alor ce dernier (nœud a) estajouté à MPR(x). On élimine par la suite les nœuds de niveau 2 couverts del’ensemble N2.

4. Tant qu’il existe encore un nœud dans N2 qui n’a pas été couvert, par au moins unMPR, c’est-à-dire que N2(x) ≠ {}, dans ce cas on procède de la sorte :a. Pour chaque nœud de N, on calcule le degré (ou reachability) c’est-à-dire le

nombre de nœuds de N2(x) non couverts mais accessible par celui-ci.b. Sélectionner le nœud ayant la plus grande valeur de N_WILLINGNESS parmi

l’ensemble des nœuds de N avec un degré non nul comme MPR et l’ajouter àMPR(x) et enlever tous les nœuds couverts par celui-ci de N2(x).

5. L’ensemble des MPR d’un nœud (MPRset) est constitué par la réunion des différentsMPR pour les différentes interfaces.

3.5 Fonctionnement du protocole OLSR

Dans ce qui suit, nous allons détailler le fonctionnement de protocole OLSR encommençant d'abord par présenter les quatre types de message de contrôle à savoir, HELLO,TC, MID, HNA, ensuite nous expliquons les deux mécanismes principaux sur lesquels reposeOLSR et qui sont, la détection de voisinage et la gestion de topologie.


29

3.5.1 Les messages échangés

3.5.1.1 Le message HELLO

Le message HELLO joue trois rôles dans le protocole OLSR. En fait, les messagesHELLO sont envoyés vers tous les voisins à un seul saut pour la détection des liens(linksensing), des voisins (neighborsensing), voisins à deux sauts (two hop sensing) et ladéclaration des nœuds sélecteurs de relais (MPR selctorsensing).

Le format du message HELLO est donné dans la figure (FIG 3.3). Ce messageconstitue le corps du message OLSR, ce paquet est envoyé dans le champ message (data) dupaquet OLSR avec type de message égal à 1 et un TTL mis à 1.

FIG 3.3 – Format du message HELLO.

Les champs du message HELLO sont définis comme suite :

- Reserved : ce champ doit être mis à « 0000000000000 » pour être conforme à cettespécification.

- HTime : ce champ spécifie l’intervalle d’émission des messages HELLO utilisés parcette interface. Si « a » représente les quatre bits du poids fort et « b » représente lesquatre bits du poids faible, l’intervalle d’émission sera calculé de la sorte :

Hello emissioninterval = C*(1+a/16)*2b (en secondes),

Ou C est une valeur qui dépend de l’implémentation.

0 1 2 3

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9

Reserved Htime Willingness

Link code Reserved Link message size

Neighbor interface address


……..

Link code Reserved Link message size




30

- Willingness : ce champ traduit la volonté du nœud à transmettre le trafic des autresnœuds. Un nœud avec « Willingness=WILL_NEVER » ne doit jamais être sélectionnécomme MPR. Par défaut un nœud doit avoir « Willingness=WILL_DEFAULT».

- Link Code : ce champ contient des informations à propos du lien entre l’interfaceémettrice et laliste qui suit des interfaces voisines. Il contient aussi des informations àpropos du statut de ces voisins.

- Neighbor Type : ce champ prend les valeurs {0, 1, 2, 3} pour indiquer respectivementle manque d’informations sur le lien en question, ou il est symétrique, asymétrique oudéfaillant.

- Link Type : ce champ indique si le lien relie le nœud vers son voisin directsymétrique, un MPR ou non disponible.

- Link Message Size : compté en octets et mesuré à partir du début du champ Link Codejusqu’au suivant champ Link Code (ou si il n’y a plus, jusqu’à la fin du message).

- Neighbor Interface Address : l’adresse de l’interface d’un nœud voisin.

3.5.1.2 Le message TC

Ce message est diffusé périodiquement par chaque MPR. Il contient la liste des voisinsl’ayant choisi comme MPR. Cette information est importante, vu que les chemins sont faits àbase de MPR, et donc si l’on veut accéder à un nœud on doit connaitre les MPR quipermettent de l’atteindre.

L’analyse des TC permet à chaque nœud de maintenir une base de topologie pourchaque destination. Les messages TC sont diffusés dans tout le réseau en utilisant la diffusionoptimisée d’OLSR par l’intermédiaire des relais multipoints.

Le format des messages TC sont illustrés dans la figure (FIG 3.4)

FIG 3.4 – Format du message TC.

0 1 2 3

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9

ANSN Reserved

Advertised Neighbor interface Main address



……..


31

Selon le RFC 3626, les champs du message TC sont définis comme suite :

- ANSN (AdvertisedNeighborSequenceNumber) : c’est un numéro de séquence associéavec l’ensemble des voisins avertis de ce message indiquant la fraicheur del’information.

- Reserved : ce champ est réservé et doit être maintenu à « 0000000000000000 ».- AdvertisedNeighbor Main Address : ce champ contient l’adresse du nœud voisin

averti par les changements topologique.

3.5.1.3 Le message MID (Multiple Interfaces Declaration)

Le rôle des messages MID est d’obtenir une meilleure fiabilité et un meilleur débit, ilsservent à sélectionner plusieurs interfaces comme principales et ainsi établir des cheminsmultiples entre deux nœuds voisins. Le MID contient la liste d’adresses des interfacesassociées à son adresse principale.

Le format du message MID est illustré dans la figure (FIG 3.5)

Longueur de paquet Num de séquence du paquet

MID – MESSAGE MID – HOLD – TIME Taille de message

@ d’expéditeur

TTL = 255 Nbr de sauts atteints Num de séquence de message

@ interface

FIG 3.5 – Format de message MID.

3.5.1.4 Le message HNA (Host and Network Association)

Utilisés pour déclarer les sous-réseaux et hôtes (hors MANET) joignable par un nœudjouant le rôle de passerelle. Le format d’un message HNA est illustré dans la figure (FIG 3.6)

Longueur de paquet Num de séquence du paquet

HNA – MESSAGE HNA – HOLD – TIME Taille de message

@ d’expéditeur

TTL = 255 Nbr de sauts atteints Num de séquence de message

@ réseaux

Masque réseaux

...

FIG3.6 – Format de message HNA.


32

3.5.2 Détection de voisinage

La détection de voisinage se fait par l’échange des messages HELLO, afin dedéterminer pour chaque nœud ces voisins symétriques directs, mais vue la mobilité desréseaux ad hoc certaines liens peuvent devenir asymétriques, ce qui oblige le nœud à testertous les liens dans les deux sens avant de les considérer valides.

La figure (FIG 3.7) illustre un exemple simple de la découverte de voisinage.

A envoie un HELLO vide, à sa réception par B, ce dernier enregistre A comme étant unvoisin asymétrique du fait qu’il ne trouve pas sa propre adresse dans ce message. Par la suite,il va envoyer après deux secondes un message HELLO en y incluant l’adresse de A. Lorsquecelui-ci le reçoit, il va y trouver sa propre adresse, donc déclarer B comme étant un voisinsymétrique. A va inclure dans la suite l’adresse de B dans le message HELLO et B vaenregistrer A comme un voisin symétrique, à la réception de ce message.

3.5.3Gestion de topologie

Les MPR ont la responsabilité de contrôler à chaque instant la topologie du réseau, vu

que cette dernière change fréquemment dans les réseaux ad hoc (les nœuds se déplacentautomatiquement). Le travail des MPR consiste à diffuser périodiquement des messages decontrôle TC. C’est à travers ces messages (TC) que chaque nœud maintien une base detopologie.

HELLO (Asym = A, Sym= B)

HELLO (Asym = A, Sym= ∅)

HELLO (vide)

HELLO (Asym = B, Sym= A)

A B

FIG 3.7– Détection de voisinage par l’échange de messages HELLO.

3

1

2

46

5 7

MPR (1) = { 4 }MPR (2) = { 3 }MPR (3) = { 4 }MPR (4) = { 3,6 }MPR (5) = { 3,4,6 }MPR (6) = { 4 }

MPR (7) = { 6 }

MPR set (1) = { }MPR set (2) = { }MPR set (3) = { 2,4,5}MPR set (4) = { 1,3,5,6 }MPR set (5) = { }MPR set (6) = { 4,5,7 }

MPR set (7) = { }


33

Dest Next Hops

1 4 2

2 2 1

4 4 1

5 5 1

6 4 (5) 2

7 4 (5) 3

3

1

2

46

5 7

TC(3) = <2,4,5>

3

1

2

4

6

5 7

TC(4) = <1,3,5,6>

3

1

2

46

5 7

TC(6) = <4,5,7>

3

1

2

46

5 7

TC(6) = <4,5,7>TC(4) = <1,3,5,6>

Comme pour le nœud 3 tous les autres nœudsforment une table de topologie grâce auxmessages TC.

Une table de routage sera calculée depuiscette table de topologie.

On note que le lien 1-2 n’est visible que pour

les nœuds 2 et 3.

FIG 3.8 – Maintien d’une base de topologie avec les messages TC.


34

3.5.4Le routage

Le routage de données se fait saut par saut sur la base des informations collectées àpartir des paquets de contrôle. Quant à ces derniers, ils sont diffusés dans le réseau via lesrelais multipoints (MPR). Un nœud retransmet un message quand celui-ci est reçu d’un nœudprécédent dont il est relais multipoints avec une durée de vie supérieur à 1, après avoir vérifiéque ce paquet n’est pas déjà été reçu.

Chaque nœud maintient une table de routage qui permet de router les données verstoutes les destinations présentes dans le réseau. Le calcul de ces tables de routage est basé surles informations contenues dans la base d’information de voisinage ainsi que celui de la basede topologie tout en les combinant avec les associations des interfaces. De ce fait, à chaquefois que l’une de ces adresses change, la table de routage est mise à jour et recalculée.

Le format de la table de routage est illustré dans la figure (FIG 3.8).

R_dest_addr R_next_addr R_dist R_iface_id

R_dest_addr R_next_addr R_dist R_iface_id

R_next_addr est l’adresse identifiant du nœud à un saut à prendre pour atteindre lenœud identifié par son adresse R_dest_addr. T_iface_addr est l’identifiant de l’interfacelocale par laquelle le nœud peut atteindre R_det_addr.R_dist est la distance estimée ennombre de sauts séparant R_dest_addr du nœud local. Les entrées de la table de routagecorrespondent à tous les nœuds dont le nœud local peut calculer une route valide. Les autresdestinations dont la route est partiellement connue, ou possédant un lien cassé, ne sont pasenregistrées dans la tablede routage.

La table de routage est mise à jour à chaque fois que l’on détecte un changementtopologique dans la base d’information topologiques et plus précisément lorsque l’on détectéune disparition ou apparition d’un tuple dans la base de topologie. Cette mise à journ’engendre aucune génération de message dans le réseau ; il s’agit, en fait, d’un simplerecalcule local.

Le calcul de la table de routage se fait conformément à la procédure suivante :

1. détruire toutes les entrées ultérieures de la table ;2. insérer dans la table tous les voisins directs qui sont symétriques à un saut. Ces

informations sont extraites de la base de voisinage. Pour chaque entrée, on ajoute :R_dest_addr correspondant à l’adresse principale du correspondant à l’adresseprincipale du voisin L_neighbor_iface_addr, dans la base de voisinage, R_next_addrcorrespondant à l’interface voisine L_neighbor_iface_addr, et R_iface_addrcorrespondant à L_Local_iface_addr. R_dist est naturellement initialisée à 1 ;

3. insérer les destinations à plus d’un saut (h + 1). La procédure suivante est exécutéepour chaque valeur de h, en commencant par h = 1 et en incrémentant h par 1, à

FIG 3.9–Format de la table de routage du protocole OLSR


35

chaque itération. Cette boucle s’arrête lorsqu’il n’ya pas de nouvelles entrées dans latable de routage.

4. pour chaque tuple dans la base d’informations de topologie, si T_dest_addr necorrespond à aucun R_dest_addr des entrée de la table de routage, et T_dest_addr,correspond à l’un des R_dest_addr avec R_dist égale à h, alors, on insère unenouvelle entrée dans la table de routage tel que :

- R_dest_addr = T_dest_addr,- R_next_addr = R_next_addr de l’entrée dont R_dest_addr est égale à T_last,- R_dist = h+1 ;5. La table de routage est complétée par l’ensemble des associations des interfaces en

ajoutant des rentrées pour : toutes les interfaces non présentes dans la table de routage.Finalement, on termine par l’insertion des routes vers l’ensemble des associations desréseaux et les hôtes rattachés. Bien évidemment, l’adresse du next hop et ladistancesont les mêmes que celles de l’adresse principale qui permet de joindre cesinterfaces et sous-réseaux.

3.6 Avantages et inconvénients d’OLSR

D’après la présentation du protocole de routage OLSR, nous remarquons qu’il a lesavantages et les inconvénients suivant :

3.6.1 Avantages

- L’optimisation des diffusions des messages de contrôle grâce à la technique des relaismultipoints.

- Les messages HNA qui permettent la communication entre un réseau MANET et unréseau filaire.

- Il offre des fonctionnalités intéressantes tout en recherchant des routes optimales entermes de nombre de sauts.

- Il gère correctement la topologie du réseau, en expédiant régulièrement des messagesTC.

- Il peut contrôler l’utilisation multiple des interfaces (messages MID).

3.6.2 Inconvénient

Il pose un problème de sécurité, il reste toujours vulnérable malgré les recherchesfaites pour améliorer sa protection contre les attaques.

3.7 Conclusion

Dans ce chapitre, nous nous sommes focalisés sur le protocole OLSR qui fait l’objetde notre étude. Ce chapitre est axé sur le fonctionnement et le comportement du protocoleOLSR dans les réseaux ad hoc. Dans le chapitre suivant on va montrer la simulation duprotocole OLSR.

Chapitre IV: Simulation du protocoleOLSR

Chapitre 4 : Simulation du protocole OLSR

36

4.1 Introduction

Dans les chapitres précédents on a présentés les réseaux ad hoc, le routage dans ce

type de réseau ainsi que le protocole OLSR. Afin d’évaluer les performances de ce dernier,

nous allons effectuer des simulations sur OLSR.

Dans ce chapitre, nous allons d’abord présenter l’outil de simulation NS2. Ensuite,

dans le but d’évaluer les performances d’OLSR, nous allons effectuer une comparaison avec

le protocole AODV, vers la fin nous discutons les résultats de ces simulations.

4.2 Présentation du Network Simulator 2

4.2.1 Définition

NS2 (Network Simulator 2) est un simulateur à évènements discrets développé dans

un but de recherche. Il fournit un environnement assez détaillé permettant entre autres de

réaliser des simulations d’IP, TCP, du routage et des protocoles multicast aussi bien sur des

liens filaires que sans fil [17]. Dans notre travail nous avons utilisé la version NS-2.35.

4.2.2 Architecture du NS2

L’architecture générale du NS2 (voir figure 4.1) consiste en deux types de Langage de

programmation : le C++ et l’OTcl (Object-orientedToolComandLanguage). LE C++ est

utilisé pour programmer les entités internes des systèmes simulé, alors que l’OTcl est utilisé

pour définir les scenarios des simulations et les paramètres de configuration. Ces deux types

de langages sont ensuite liés via le TclCL qui permet le passage des codes C++ vers les codes

en OTcl et vice versa.

Une fois la simulation terminée. NS génère des fichiers particuliers dits fichiers de

traces contenant un ensemble d’informations sur le déroulement de la simulation. Ces fichiers

permettent d’évaluer les performances de réseau étudier selon des critères précis. Ils peuvent

être interprétés en utilisant les outils : NAM(Network AniMator)et Xgraph[17].

On distingue deux types de fichiers de trace :

- Les fichiers trace « .NAM » : ces fichiers contiennent des inforamtions utiles pour la

visualisation des nœuds et leurs déplacements ainsi que le parcours des paquets enter

les nœuds.

- Les fichiers trace « .tr » : ces fichier contiennent un ensemble de lignes tel que

chaque ligne correspond à un évènement daté concernant soit un nœud ou un paquet,

ils servent à calculer les différents critères et taux utiles pour évaluer les performances

du réseau étudié.


37

4.3 Simulation et discussion des résultats

4.3.1 Le protocole simulé

Afin d’évaluer les performances du protocole OLSR nous allons nous appuyer sur unecomparaison avec le protocole AODV qui est appartient à la famille des protocoles réactifs.

4.3.2 Paramètres de simulation choisis

Bande passante

LA bande passante est le débit en bit par seconde. Il est mesuré par la différence entrela fréquence de transmission la plus haute et la fréquence de transmission la plus basse. Cesfréquences sont mesurées en Hertz, l’unité fondamentale de ce paramètre est bit par seconde(bit/s) [19].

4.3.3 Présentation des différents scenarios de simulation

Dans notre étude, on va traiter deux scenarios : l’impact de nombre de nœuds duréseau et l’impact de la mobilité.

4.3.3.1 Scenario 1 : Etudes par rapport au nombre de nœuds

Nous varions le nombre de nœuds et nous gardon les autres paramètres fixent

Cas 1 : nombre de nœuds = 10

Cas 2 : nombre de nœuds = 25

NS 2 Shell Executable Command (ns)

SimulationObjects

SimulationObjects

TclCL

C++ OTcl

TclSimulation

Script

SimulationTraceFile

Aitouakliyacinemaaliouloucifthachouithvgitinidkanaklinthinaamakihlimacv bienakkithtiliiwacheakkak

Aitouakliyacinemaaliouloucifthachouithvgitinidkanaklinthinaamakihlimacv bienakkithtiliiwacheakkak

NAM(Animatio

n)

Xgraph(plotting)

FIG 4.1 -Architecture générale du NS.


38

Les paramètres de simulation constituant cette simulation sont illustrés dans le tableau(TAB 4.1).

Paramètre Valeur

Temps de simulation 100s

Protocole OLSR et AODV

Taille de paquet de données 50

Modèle de mouvement OFF

Nombre de nœuds 10 / 25

Nombre de scenario pour un même contexte 2

Propagation Two Ray Ground

Type d’interface de réseau Wirelessephy

Couche Mac 802.11

Topologie de réseaux 1000 x 1000

Trafic d’application CBR (Continous Bit Rate)

Paramètre simulé Débit

Les topologies du réseau simulé

TAB 4.1 – Modèle de simulation utilisé.

Emetteur

Récepteur

FIG 4.2– Cas 1 : Topologie du réseau simulé.


39

10 NŒUDS 25 NŒUDS

OLSR AODV OLSR AODV

0 0 0 0 0

10.0000 360.0000 390.0000 240.0000 230.0000

20.0000 360.0000 390.0000 240.0000 190.0000

30.0000 380.0000 390.0000 380.0000 200.0000

40.0000 400.0000 385.0000 250.0000 210.0000

50.0000 360.0000 370.0000 280.0000 220.0000

60.0000 370.0000 360.000 2600000 180.0000

70.0000 400.0000 390.0000 230.0000 160.0000

80.0000 360.0000 370.0000 280.0000 150.0000

90.0000 360.0000 380.0000 280.0000 200.0000

100.0000 380.0000 370.0000 180.0000 170.0000

Le tableau [TAB 4.2] montre les résultats de la simulation des protocoles AODV et

OLSR dans deux cas (10 et 25 nœuds), on remarque que, dans le premier scénario le débit

moyen est presque le même pour les deux protocoles, par contre dans le deuxième (25

nœuds), on voit bien que le débit avec OLSR est plus élevé. Ces résultats sont illustrés dans

les figures [FIG 4.4] et [FIG 4.4] avec l’outils xgraphe.

FIG 4.3– Cas 2 : Topologie du réseau simulé.

Emetteur

Récepteur

TAB 4.2 – Résultats de la simulation.


40

FIG

4.4–

Cas

1:

Débit

enfonction

denom

brede

nœuds.

OL

SR

AO

DV


41

FIG

4.5–

Cas

2:

Débit

enfonction

denom

brede

nœuds.

OL

SR

AO

DV


42

4.3.3.2 Scénario 2 : Etude par rapport à la mobilité

Nous comparons le débit dans une une topologie mobile pour les deux protocoles.Les

paramètres de simulation constituant cette simulation sont illustrés dans le tableau (TAB 4.2).

Paramètre Valeur

Temps de simulation 95s

Protocole OLSR et AODV

Taille de paquet de données 50

Modèle de mouvement RandomWaypoint

Nombre de nœuds 7

Nombre de scenario pour un même contexte 1

Propagation Two Ray Ground

Type d’interface de réseau Wirelessephy

Couche Mac 802.11

Topologie de réseaux 1000 x 1000

Trafic d’application CBR (Continous Bit Rate)

Paramètre simulé Débit

Les topologies du réseau simulé

TAB 4.3 – Modèle de simulation utilisé.

Emetteur

Récepteur

FIG 4.6–Topologie du réseau audépart de la simulation.

FIG 4.7 – Topologie du réseau à la finde la simulation.


43

OLSR AODV

0 0 0

20.0000 240.0000 220.0000

22.0000 320.0000 240.0000

30.0000 260.0000 220.0000

40.0000 310.0000 240.0000

60.0000 350.0000 260.000

68.0000 220.0000 250.0000

70.0000 0 240.0000

80.0000 0 160.0000

90.0000 0 130.0000

95.0000 0 0

Le tableau [TAB 4.4] illustre les résultats de la simulation des deux protocoles OLSR etAODV dans une topologie mobile. On remarque qu’avant l’instant 50 le débit moyen estpresque le même pour les deux protocoles, mais à partir de cette instant (50 second) le débitmoyen avec OLSR à chuté et devenu nul à partir de l’instant 70s, par contre avec AODV ledébit moyen à juste diminué légèrement. La figure [FIG 4.8 ] montre les résultats de cettesimulation sous forme d’un graphe réalisé avec l’outil xgraph.

TAB 4.4 – Résultats de la simulation.


44

FIG

4.8–L

edébit

enfonction

dela

mobilité

desnœ

uds.

OL

SR

AO

DV


45

4.4 Discussion

D’après les résultats présentés dans les graphes obtenus précédemment, nous avons vu

pour chaque scénario et pour chaque protocole une mesure retenue qui est le débit par rapport

à la densité du réseau (nombre de nœuds) et à sa mobilité.

Les graphes présentés dans les FIG 4.4 et FIG 4.5 montrent que le débit par rapport

au nombre de nœuds changent dans les deux cas et pour les deux protocoles OLSR et AODV,

le débit augmente à chaque fois que le nombre de nouds diminue, mais on remarque que

OLSR est plus tolèrent à la densité du réseau grâce à la connaissance ultérieure de la

topologie, obtenu avec les messages d’information diffusé de manière partielle sur le réseau (à

travers les relais multipoints qui optimise les diffusions de ces messages). Contrairement à

AODV qui n’a aucune connaissance ultérieure sur la topologie et la découverte de route se

fait au moment de l’envoi d’un paquet avec une diffusion d’une route requeste(RREQ).

Les graphes présentés dans la FIG 4.6 présente la variation du débit avec la mobilité

du réseau. On remarque que le protocole AODV est plus tolèrent à la mobilité par rapport à

OLSR. De l’instant 0 jusqu’à 60 la topologie n’a pas changé ce qui explique que le débit

moyen pour les deux protocoles était presque le même, mais à partir de l’instant 60 les nœuds

commencèrent à se déplacer et la topologie du réseau changeait fréquemment, c’est là qu’on

voit que le débit moyen avec OLSR diminuait considérablement par rapport à AODV. Ceci

revient aux mises à jour fréquentes des tables de routages dans le cas d’OLSR, à chaque fois

que les nœuds détectent un changement de topologie, ce trafic de contrôle diffusé à chaque

mise à jour pénalise le débit de transmission. Par contre, dans le cas d’AODV la découverte

du chemin se fait sans connaissance globale de la topologie, ce qui veut dire une quantité de

trafic de contrôle inférieur à celui du protocole OLSR, ce qui implique un meilleur débit.

4.6 Conclusion

Dans ce chapitre, nous avons essayé d’évaluer le protocole de routage OLSR en

utilisant une comparaison avec le protocole AODV en variant certain paramètres (densité et

mobilité du réseau).

D’après les résultats des simulations nous pouvons conclure que le protocole OLSR

est plus performant dans les réseaux denses et peu mobiles.

46

Conclusion générale

A travers ce modeste travail, nous avons approfondit nos connaissances sur les réseaux

sans fils ad hoc avec leurs différentes caractéristiques (absence d’infrastructure, topologie

dynamique, bande passante limitées, sécurité physique limitée, contraintes d’énergie, …Etc.),

et on a constaté que malgré les avantages de ce type de réseau (à savoir la minimisation du

cout d’installation, la rapidité de déploiement, réseau local mobile …etc.), il reste un nombre

important de problèmes à résoudre dont celui du routage. Pour ça, plusieurs protocoles de

routages ont été développés ces dernières années. Dans ce travail, on à étudier et évaluer les

performances de l’un de ces algorithmes de routage qui est le protocole OLSR, et on à citer

au passage quelque autres comme AODV, DSDV, TBRPF, DSR, ZRP.

Pour atteindre l’objectif de notre travail, qui été l’étude du comportement du protocole

de routage OLSR dans les réseaux sans fils ad hoc, nous avons présenté aux premiers lieux le

concept de ces réseaux. Par la suite, nous avons étudié le routage dans un tel environnement,

et nous avons décrit ces différentes contraintes, techniques et classifications, ensuite nous

avons détaillé sur le protocole OLSR avec ces différentes caractéristiques et mode de

fonctionnement.

Notre étude est suivie par des simulations, ou on a effectué une comparaison sur les

deux protocoles OLSR et AODV sous l’outil de simulation NS-2. Les résultats de simulation

ont été présentés et sur des graphes et interprétés. Ces simulations nous ont permis de voir la

variation du débit de chaque protocole par rapport à l’impact de la densité et de la mobilité du

réseau.

A partir des résultats trouvés, nous constatons que la densité d’un réseau n’affecte pas

le débit moyen de transmission avec le protocole OLSR, contrairement à la mobilité qui

diminue considérablement ce paramètre.

47

Comme perspectives nous pouvons citer :

Perfectionner nos simulations en considérant d’autres métriques comme le taux de

délivrance de paquets (PDR), le délai de bout en bout et le niveau d’énergie de chaque

nœud.

L’extension de nos simulations aux autres protocoles de routages du groupe MANET

surtout les protocoles hybrides (tel que ZRP) afin de pouvoir comparer les trois classes

de protocole de routage.

Annexe

.

Annexe

IX

A.1 Script TCL-OTCL

TCL est un langage conçu pour une utilisation par un développeur de l'application

quipeut être participéà travers une demande ou pourrait être utilisé par une application

dediverses manières, par exemple, pour permettre à un utilisateur de fournir une

initialisationpersonnalisée pour l'application. L'OTCL est un TCL avec les extensions orientée

objet.NS2 utilise otcl pour le programmeur de simulation pour créer les objets de réseau dans

la mémoire et d’insérer des événements initiaux dans la file d'attente de l'événement.

A.2 NAM

NAM est un outil d'animation basé sur tcl pour les traces de simulation de réseaux

d'observation et des traces de paquets du monde réel. Il prend en charge la topologie mise en

page,l'animation au niveau du paquet, et divers outils de contrôle de données. Cette

visualisation fournit une représentation du graphe du réseau sur laquelle on peut voir les

paquets circuler, suivre le niveau des files d'attente et observer le débit courant des liaisons.

A.3 Xgraphe

Xgraph est une application X-Windows qui inclut le traçage interactif et graphique,

deportabilité et de corrections de bugs. Donc, pour tracer les caractéristiques des paramètres

NS2 comme le débit, la fin d'un retard de la fin, les paquets d'informations, etc peut êtretracée

en utilisant xgraph. Le fichier xgraph affiche les informations à propos de la surchargeavec la

taille du réseau, Overheadest comparé avec quatre protocoles de routage comme

AODV, DSR, DSDV et NEAODV. Les valeurs sont prises à partir des divers fichiers detrace.

A.4 Implémentation d’OLSR sur NS2

Puisque le protocole OLSR n’est pas intégrer dans le simulateur NS2 nous devons

installer le patch um-olsr qui est une implémentation du protocole dans NS2. Pour installer le

patch, nous avons suivi les étapes suivantes :

1. Télécharger le fichier « umolsr-ns235_v1.0-2014.patch » depuis le lien :

https://drive.google.com/file/d/0B7S255p3kFXNeVZhWFVVZlJnUEU/view?usp=sha

ring

2. Copier le fichier « umolsr-ns235_v1.0-2014.patch » dans le répertoire « ns-allinone-

2.35 ».

3. Executer les commande suivante dans un terminal :

Annexe

X

A.5 Script des simulations

A.5.1 Topologie fixe à 25 nœuds OLSR

#===================================

# Simulation parameters setup

#===================================

setval(chan) Channel/WirelessChannel ;# channel type

setval(prop) Propagation/TwoRayGround ;# radio-propagation model

setval(netif) Phy/WirelessPhy ;# network interface type

setval(mac) Mac/802_11 ;# MAC type

set val(ifq) Queue/DropTail/PriQueue ;# interface queue type

setval(ll) LL ;# link layer type

setval(ant) Antenna/OmniAntenna ;# antenna model

setval(ifqlen) 50 ;# max packet in ifq

setval(rp) OLSR ;# routing protocol

setval(x) 1000 ;# X dimension of topography

setval(y) 600 ;# Y dimension of topography

setval(stop) 100.0 ;# time of simulation end

#===================================

# Initialization

#===================================

#Create a ns simulator

set ns [new Simulator]

$ns color 0 red

#Setup topography object

set topo [new Topography]

$topo load_flatgrid $val(x) $val(y)

#set wireless_tracefile [open YourTraceFileName.trace w]

#$ns trace-all $wireless_tracefile

$ cd ns-allinone-2.35/

$ patch -p0 < umolsr-ns235_v1.0-2014.patch

$ ./install

$ cd ns-2.35/

$ cp ns ns-olsr

$ sudocp ns-olsr /usr/local/bin/

Annexe

XI

# *** Initialize Trace file ***

settracefd [open trace2.tr w]

$ns trace-all $tracefd

#Open the NS trace file

set f1 [open OLSR.tr w]

#Open the NAM trace file

setnamfile [open out.nam w]

$ns namtrace-all $namfile

$ns namtrace-all-wireless $namfile $val(x) $val(y)

#Create wireless channel

setchan [new $val(chan)];

#number of node

global TN

set TN 25

set god_ [create-god $TN]

#===================================

# Mobile node parameter setup

#===================================

$ns node-config -adhocRouting $val(rp) \

-llType $val(ll) \

-macType $val(mac) \

-ifqType $val(ifq) \

-ifqLen $val(ifqlen) \

-antType $val(ant) \

-propType $val(prop) \

-phyType $val(netif) \

-channel $chan \

-topoInstance $topo \

-agentTrace ON \

-routerTrace ON \

-macTrace OFF \

-movementTrace OFF

#===================================

# Nodes Definition

#===================================

#Create 25 nodes

set n0 [$ns node]

$n0 set X_ 663

$n0 set Y_ 484

$n0 set Z_ 0.0

$ns initial_node_pos $n0 40

$n0 start

$ns at 0.0 "$n0 label \"source\""

set n1 [$ns node]

Annexe

XII

$n1 set X_ 466

$n1 set Y_ 407

$n1 set Z_ 0.0


set n2 [$ns node]

$n2 set X_ 791

$n2 set Y_ 406

$n2 set Z_ 0.0


set n3 [$ns node]

$n3 set X_ 668

$n3 set Y_ 393

$n3 set Z_ 0.0


set n4 [$ns node]

$n4 set X_ 558

$n4 set Y_ 320

$n4 set Z_ 0.0


set n5 [$ns node]

$n5 set X_ 781

$n5 set Y_ 317

$n5 set Z_ 0.0


set n6 [$ns node]

$n6 set X_ 650

$n6 set Y_ 40.0

$n6 set Z_ 0.0


set n7 [$ns node]

$n7 set X_ 350

$n7 set Y_ 120

$n7 set Z_ 0.0


set n8 [$ns node]

$n8 set X_ 761

$n8 set Y_ 234

$n8 set Z_ 0.0


set n9 [$ns node]

$n9 set X_ 476

$n9 set Y_ 117

$n9 set Z_ 0.0


Annexe

XIII

set n10 [$ns node]

$n10 set X_ 714

$n10 set Y_ 121

$n10 set Z_ 0.0


set n11 [$ns node]

$n11 set X_ 825

$n11 set Y_ 140

$n11 set Z_ 0.0


set n12 [$ns node]

$n12 set X_ 509

$n12 set Y_ 34

$n12 set Z_ 0.0


set n13 [$ns node]

$n13 set X_ 687

$n13 set Y_ 36

$n13 set Z_ 0.0


set n14 [$ns node]

$n14 set X_ 822

$n14 set Y_ 51

$n14 set Z_ 0.0


set n15 [$ns node]

$n15 set X_ 373

$n15 set Y_ 271

$n15 set Z_ 0.0


set n16 [$ns node]

$n16 set X_ 903

$n16 set Y_ 255

$n16 set Z_ 0.0


set n17 [$ns node]

$n17 set X_ 908

$n17 set Y_ 344

$n17 set Z_ 0.0


set n18 [$ns node]

$n18 set X_ 600

$n18 set Y_ 180

$n18 set Z_ 0.0

Annexe

XIV


set n19 [$ns node]

$n19 set X_ 455

$n19 set Y_ 479

$n19 set Z_ 0.0


set n20 [$ns node]

$n20 set X_ 350

$n20 set Y_ 434

$n20 set Z_ 0.0


set n21 [$ns node]

$n21 set X_ 263

$n21 set Y_ 306

$n21 set Z_ 0.0


set n22 [$ns node]

$n22 set X_ 261

$n22 set Y_ 209

$n22 set Z_ 0.0


set n23 [$ns node]

$n23 set X_ 240

$n23 set Y_ 115

$n23 set Z_ 0.0


set n24 [$ns node]

$n24 set X_ 313

$n24 set Y_ 29

$n24 set Z_ 0.0


$ns at 0.0 "$n24 label \"destination\""

#===================================

# Agents Definition

#===================================

#Setup a UDP connection

set udp0 [new Agent/UDP]

$ns attach-agent $n0 $udp0

set null1 [new Agent/LossMonitor]

$ns attach-agent $n24 $null1

$ns connect $udp0 $null1

#$udp0 set packetSize_ 1500

#Setup a CBR Application over UDP connection

set cbr0 [new Application/Traffic/CBR]

Annexe

XV

$cbr0 attach-agent $udp0

$cbr0 set packetSize_ 1500

$cbr0 set rate_ 0.4Mb

$cbr0 set random_ null

$ns at 1.0 "$cbr0 start"

$ns at 999.95 "$cbr0 stop"

$ns at 0.0 "$ns trace-annotate \"BandePassante \""

$ns at 0.0 " $n0 add-mark m red box "

$ns at 0.2 "$n0 delete-mark m"

$ns at 0.0 " $n24 add-mark m red box "

$ns at 0.0 "$n24 delete-mark m"

#===================================

# Applications Definition

#===================================

proc record {} {

global null1 f1

#Get an instance of the simulator

set ns [Simulator instance]

#Set the time after which the procedure should be called again

set time 0.5

#How many bytes have been received by the traffic sinks?

set bw0 [$null1 set bytes_]

#Get the current time

set now [$ns now]

#Calculate the bandwidth (in MBit/s) and write it to the files

puts $f1 "$now [expr $bw0/$time*8/1000000]"

#Reset the bytes_ values on the traffic sinks

$null1 set bytes_ 0

#Re-schedule the procedure

$ns at [expr $now+$time] "record"

}

#===================================

# Termination

#===================================

#Define a 'finish' procedure

proc finish {} {

global ns tracefd f1 namfile

close $f1

close $namfile

$ns flush-trace

Annexe

XVI

close $tracefd

execnamout.nam&

#Call xgraph to display the results

execxgraph OLSR.tr aodv.tr -geometry 800x400 &

exit 0

}

for {set i 0} {$i< $TN } { incri } {

$ns at $val(stop) "\$n$i reset"

}

#$ns at $val(stop) "$ns nam-end-wireless $val(stop)"

$ns at 0.0 "record"

$ns at $val(stop) "finish"

$ns at $val(stop) "puts \"done\" ; $ns halt"

$ns run

A.5.2 Topologie mobile OLSR:

# Addingnam trace

# simple-wireless.tcl

# A simple example for wireless simulation

===============================================================

# Define options

===============================================================

setval(chan) Channel/WirelessChannel ;# channel type

setval(prop) Propagation/TwoRayGround ;# radio-propagation model

setval(netif) Phy/WirelessPhy ;# network interface type

setval(mac) Mac/802_11 ;# MAC type

set val(ifq) Queue/DropTail/PriQueue ;# interface queue type

setval(ll) LL ;# link layer type

setval(ant) Antenna/OmniAntenna ;# antenna model

setval(ifqlen) 50 ;# max packet in ifq

setval(nn) 7 ;# number of mobilenodes

setval(rp) OLSR ;# routing protocol

Annexe

XVII

===============================================================

# Main Program

===============================================================

# Initialize Global Variables

set ns_ [new Simulator]

settracefd [open olsr.tr w]

setnamfd [open olsr.nam w]

$ns_ trace-all $tracefd

$ns_ namtrace-all-wireless $namfd 500 500

# set up topography object

set topo [new Topography]

$topo load_flatgrid 500 500

# Create God

create-god $val(nn)

# Create the specified number of mobilenodes [$val(nn)] and "attach" them

# to the channel.

# Here two node0s are created : node(0) and node(1)

# configure node

$ns_ node-config -adhocRouting $val(rp) \

-llType $val(ll) \

-macType $val(mac) \

-ifqType $val(ifq) \

-ifqLen $val(ifqlen) \

-antType $val(ant) \

-propType $val(prop) \

Annexe

XVIII

-phyType $val(netif) \

-channelType $val(chan) \

-topoInstance $topo \

-agentTrace ON \

-routerTrace ON \

-macTrace OFF \

-movementTrace OFF

for {set i 0} {$i< $val(nn) } {incri} {

set node_($i) [$ns_ node]

$node_($i) random-motion 0 ;# disable random motion

}

#

# Provide initial (X,Y, for now Z=0) co-ordinates for mobilenodes

#

$node_(0) set X_ 5.0

$node_(0) set Y_ 2.0

$node_(0) set Z_ 0.0

$ns_ initial_node_pos $node_(0) 40

$node_(1) set X_ 390.0

$node_(1) set Y_ 385.0



Annexe

XIX

$node_(2) set X_ 250

$node_(2) set Y_ 121




$node_(3) set Y_ 140




$node_(4) set Y_ 34




$node_(5) set Y_ 36



$node_(6) set X_ 390.0

$node_(6) set Y_ 385.0



# Now produce some simple node movements

# Node_(1) starts to move towards node_(0)

$ns_ at 0.0 "$node_(0) setdest 5.0 2.0 0.0"

Annexe

XX












#$ns_ at 50.0 "$node_(5) setdest 13.0 20.0 7.0"


# Node_(1) then starts to move away from node_(0)


# Setup traffic flow between nodes

# TCP connections between node_(0) and node_(1)

settcp [new Agent/TCP]

$tcp set class_ 2

set sink [new Agent/TCPSink]

$ns_ attach-agent $node_(0) $tcp

Annexe

XXI

$ns_ attach-agent $node_(5) $sink

$ns_ connect $tcp $sink

set ftp [new Application/FTP]

$ftp attach-agent $tcp

$ns_ at 10.0 "$ftp start"

set f0 [open olsr.out w]

proc record {} {

global sink f0

#Get an instance of the simulator

set ns [Simulator instance]

#Set the time after which the procedure should be called again

set time 0.5

#How many bytes have been received by the traffic sinks?

set bytes [$sink set bytes_]

#Get the current time

set now [$ns now]

#Calculate the bandwidth (in MBit/s) and write it to the files

puts $f0 "$now [expr $bytes/$time*8/1000000]"

#Reset the bytes_ values on the traffic sinks

$sink set bytes_ 0

#Re-schedule the procedure

$ns at [expr $now+$time] "record"

# puts "getting out of record()"

Annexe

XXII

# puts "$now"

}

# Tell nodes when the simulation ends

for {set i 0} {$i< $val(nn) } {incri} {

$ns_ at 95.0 "$node_($i) reset";

}

$ns_ at 95.0 "stop"

$ns_ at 95.01 "puts \"NS EXITING...\" ; $ns_ halt"

proc stop {} {

global ns_ tracefdnamfd f0

$ns_ flush-trace

close $namfd

close $tracefd

execxgrapholsr.outaodv.out -geometry 800x400 &

execnamolsr.nam&

}

puts "Starting Simulation..."

$ns_ at 0.0 "record"

$ns_ run

XXIV

Bibliographie

[1] Shan Gong,Quality of Service Aware Routing Protocols for Mobile Ad hoc Network

these, Finlande (Espoo), 2006, http:/lib.tkk.fi/Dipl/2006/urn007361.pdf

[2] PUJOLLE, les réseaux édition 2003, livre, Edition EYROLLES, juin 2002.

[3] Anis LAOUITI, Unicast et multicast dans les réseaux ad hoc sans fil, thèse de doctorat,

université de Versailles-saint Quentin, juillet 2002.

[4] Rabah MERAIHI, Gestion de la qualité de service et contrôle de topologie dans les

réseaux ad hoc, thèse de doctorat, l’école Télécom Paris-Tech, 2005.

[5] Jean-Marc Percher et Bernard Jouga, Détection d’intrusions dans les réseaux ad hoc, Ecole

Supérieure d’Electronique de l’Ouest (ESEO), livre, Mars 2004.

[6] BEDOUHENE Rafik, Protocole de connexion des réseaux ad hoc à Internet, mémoire de

magistère, 2004.

[7] N. BOUKHECHEM , routage dans les réseaux mobiles ad hoc par une approche à base

d’agents, Mémoire de Magister, Faculté des sciences et science de l’ingénieur, Université de

Constantine, 2008.

[8] TAHAR ABBAS Mounir, Proposition d’un protocole à économie d’énergie dans un

réseaux hybride GSM et ad hoc, Mémoire de doctorat, université d’Oran, 2011-2012.

[9] M. BOUZAHER Abdelaziz, Approche agent mobile pour l’adaptation des réseaux

mobiles ad hoc, Mémoire de Magister en Informatique, Faculté des sciences et des sciences

de l’ingénieur Département d’informatique Ecole Doctorat, Université Mohamed Khider

Biskra

XXV

[10] Abdelmajid HAJAMI, sécurité du routage dans les réseaux sans fil spontanés : cas du

protocole OLSR, thèse doctorat, Ecole Nationale Supérieure d’informatique et d’analyse des

Systèmes (ENSIAS) - Rabat, Université Mohammed V, 2011.

[11] Daniel MABELE MONDONGA, étude sur les protocoles de routage d’un réseau sans fil

en mode ad hoc et leurs impacts "Cas de protocoles OLSR et AODV", Institut supérieur

d’informatique, programmation et analyse de Kinshasa, Ingénieur informaticien 2010.

[12] M. Mohammed, routage dans les réseaux maillés sans fil, mémoire de magister

Université M’Hamed Bougrra-Boumerdés, 2012.

[13] Claude CHAUDET, Influence des interférences sur les problèmes de réservation de

bande passante dans les réseaux ad hoc, juin, 2001.

[14] Bournane ABBACHE et Zahir FENOUCHE , Proposition d’intégration de la réservation

de ressources dans les réseaux ad hoc , mémoire de magister , septembre 2006.

[15] C . Perkins et al, Ad hoc on-Demand Distance Vector (AODV) Routing, RFC juillet

2003

[16] Anis Laouiti et Cédrie Ajih, Mesure des performances du protocole OLSR. Projet

Hipercom , INRIA, Janvier 2003.

[17] http://www.isi.edu/nsnam/ns.

Résumé

Les réseaux mobiles ad hoc (MANETs) sont des réseaux sans infrastructures,

fonctionnant sans station de base et sans administration centralisée. Tel que tous les nœuds

dans ces réseaux peuvent être reliés de manière arbitraire et formant un réseau temporaire à

topologie variable (dynamique).

Notre mémoire à pour objectif d’étudier et d’évaluer le protocole de routage OLSR

(Optimized Link Routing State), qui est un protocole proactif appartenant à la famille des

protocoles à état de liens. Afin d’évaluer les performances de ce dernier on à fait recours à

une simulation à l’aide de l’outil de simulation NS2 (network simulator).

Mots clés : Réseaux ad hoc, mobilité, routage, protocole de routage, OLSR, débit, simulateur

NS-2.

Abstract

Ad hoc mobile networks (MANETs) are networks without infrastructure, operating

without a base station and without centralized administration. Such that all the nodes in these

networks can be arbitrarily connected and form a temporary network with variable (dynamic)

topology.

Our objective is to study and evaluate the Optimized Link Routing State (OLSR)

protocol, which is a proactive protocol belonging to the family of link state protocols. In order

to evaluate the performance of the latter, a simulation is used using the simulation tool NS2

(network simulator).

Key words: Ad hoc networks, Mobility, routing, routing protocol, OLSR, simulator NS-2.

Documents

Etude et évaluation des performances du protocole de