N° d'ordre:

Farid Jaddi

Description

Niveau: Supérieur, Doctorat, Bac+8
N° d'ordre: 2381 THESE présentée pour obtenir LE TITRE DE DOCTEUR DE L'INSTITUT NATIONAL POLYTECHNIQUE DE TOULOUSE Titre de la thèse École doctorale: Ecole Doctorale d'Informatique et Télécommunications Spécialité: RTSA Par M. Farid JADDI CSR : une extension hiérarchique adaptative du protocole de routage ad hoc DSR Soutenue le 2511 0/06 devant le jury composé de : DIAZ Michel Président Mme. PAILLASSA Béatrice Mme. MINET Pascale Directeur de thèse Rapporteur Rapporteur Membre Mme. KANCHANASUT Kanchana M. FRABOUL Christian

• hoc


• mesures internes de l'efficacité


• introduction au routage dans les réseaux ad


• membre de jury


• frères youssef aka


• ecole doctorale d'informatique


• protocole de routage ad hoc


• ton indéboulonnable

Sujets

• Hélène
• Institut national polytechnique de Toulouse

Informations

• Publié par: profil-feym-2012
• Nombre de lectures: 26
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

N° d'ordre: 2381
THESE
présentée
pour obtenir
LE TITRE DE DOCTEUR DE L'INSTITUT NATIONAL POLYTECHIQUE DE TOULOUSE
École doctorale: Ecole Doctorale d'Informatique et Télécommunications
Spécialité : RTSA
Par JADDI Farid
Titre de la thèse
CSR : une extension hiérarchique adaptative
du protocole de routage ad hoc DSR
Soutenue le 2511 0/06 devant le jury composé de :
M. DIAZ Michel Président
Mme. PAILLASSA Béatrice Directeur de thèse
Mme. MINET Pascale Rapporteur
Mme. KANCHANASUT Kanchana
M. FRABOUL Christian Membre CSR: une extension hiérarchique adaptative du
protocole de routage ad hoc DSR
Farid JADDI
Thèse dirigée par Béatrice PAILLASSARemerciements
Je tiens à remercier tout d’abord Kanchana Kanchanasut et Pascale Minet
pour avoir accepté d’examiner mon manuscrit. Je vous suis notamment recon-
naissantpour l’intérêtquevousavezmanifesté àl’égardde montravail.D’autre
part, les remarques de Pascale Minet m’ont particulièrement aidé à prendre du
recul sur mon travail et à améliorer la qualité et la clarté du mémoire et de la
soutenance. Je tiens aussi à remercier Michel Diaz pour avoir assuré la charge
de président du jury. Je suis conscient de son emploi du temps très chargé et
l’attentionqu’ilaportée àmonmanuscritetma soutenanceme touched’autant
plus. Un grand merci à Christian Fraboul pour la considération qu’il a portée à
ma thèse dès le début, pour sa présence à la soutenance et pour sa relecture du
manuscrit. Pour en terminer avec les membres du jury, last but not the least,
je remercie très chaleureusement Béatrice Paillassa tant pour ses qualités hu-
maines et professionnellesque j’ai pu appréciées tout au long de ma thèse. Je te
sais gré d’avoir accepter ma manière de fonctionner et de m’avoir fait voir du
pays! Je te suis très reconnaissant pour tout ce que tu m’as appris et pour ton
encadrement hors pair.
Passons maintenant au labo dont les membres ont largement contribué à
faire de ma thèse un moment mémorable (pour moi!). Après trois ans à l’N7, je
suispassédel’autrecôtédumiroirtelleAliceetlesenseignantssesontmétamor-
phosésencollègues.UngrandmerciàJuliendontj’aipuapprécierlafulgurante
ascension,à Manule beau blondqui finira sûrementpatronde karaoké,à Riadh
poursesjudicieuxconseilsenNSetàJéromepoursabonnehumeur.Jeremercie
aussi André-Luquiñoh pour son euro parler, pour sa verve, pour son historique
du regretté Shanghaï et pour sa capacité (j’allais presque dire son don ...) à
transformer toute anecdote ou parole anodines en événement! Le labo ne serait
pas ce qu’il est sans Sylvie à la fois pierre angulaire et piment de ce notable
établissement : efficace, attentionnée, pimpante et marrante! J’essaierai de te
débaucher dès que je gagnerai plus d’un keuro ...
Le labo ne serait pas aussi vivant sans le sang neuf qui l’irrigue, sans son
armada de thésards. Je remercie pêle-mêle Alex et Rahim (l’alliance du feu et
de la glace), Hussein et son sang-froid, Nico le spécialiste du Latex, Cholatip et
son abnégation, pour tous les bons moments passés ensemble. Merci à l’équipe
du petit london toujours prête à tout tourner en dérision : JP et son désormais
mythique “esprit critique”, Vincent M. avec lequel la fusion est plus qu’immi-
nente, Vincent H. le poussin qui est devenu top gun, Florent l’homme animal
iii
tour à tour glouton, puma et chauda-dog, Wil le papounet et le leader de la
black-basse cour. Je n’oublie pas Garmy la princesse peul, toujours en manque
dedessert,quiprendlavieducôtébonainsiqueMathieumonpetitcanard(qui
adeshongroisdanssabaignoire)etdontl’immensegénérositéetintelligenceme
laissent souvent pantois mais toujours avec le sourire. Avec Sakuna’tchan, mon
acolyte de bureau, l’échange culturel France-Thaïlande a été plus que positif et
enrichissant, surtout ne perd jamais ton indéboulonnable sourire!
Lathèseneseseraitpassibienpasséesansl’appuidemafamilleetjeremer-
cie pour raisons diplomatiques mes parents et mes frères Youssef aka Chucky
et Samir alias frite à l’huile d’olive. Un petit coucou aux amis : Sue Hélène la
danseuse invétérée, Mel B spécialiste en thé et chocolat chaud, Eldridge qui re-
présente la gwadada,Franky aka Lock Ho le roi du jeu de mots, Laurent l’oncle
Bives des amériques dont le départ a traumatisé Toulouse et le chti nécureuil
volant qui m’a fait planer pour un vol malheureusement trop court.
Un grand merci à vous tous!Table des matières
Introduction 1
1 Introduction au routage dans les réseaux Ad hoc 5
1.1 Notions de réseaux ad hoc . . . . . . . . . . . . . . . . . . . . . . 6
1.1.1 Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.2 Technologies radio . . . . . . . . . . . . . . . . . . . . . . 7
1.1.2.1 802.11 . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.2.2 Bluetooth . . . . . . . . . . . . . . . . . . . . . . 8
1.1.2.3 HiperLAN . . . . . . . . . . . . . . . . . . . . . 8
1.1.2.4 Déploiement . . . . . . . . . . . . . . . . . . . . 9
1.1.3 Caractéristiques et contraintes . . . . . . . . . . . . . . . 9
1.2 Principe du routage . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.1 Problématique du routage . . . . . . . . . . . . . . . . . . 11
1.2.2 Classification des protocoles de routage . . . . . . . . . . 11
ère1.2.3 Exemples de protocoles de 1 génération . . . . . . . . . 13
1.2.3.1 DSDV . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.3.2 TORA . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.3.3 AODV . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.1 Procédures DSR . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.1.1 Découverte de routes . . . . . . . . . . . . . . . 16
1.3.1.2 Maintenance de routes. . . . . . . . . . . . . . . 16
1.3.2 Optimisations . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3.2.1 Découverte de routes . . . . . . . . . . . . . . . 17
1.3.2.2 Maintenance de routes. . . . . . . . . . . . . . . 18
1.3.2.3 Option Flow State . . . . . . . . . . . . . . . . . 18
1.3.2.4 Gestion du cache . . . . . . . . . . . . . . . . . . 18
1.4 Axes de recherche sur le routage ad hoc . . . . . . . . . . . . . . 20
1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2 Evaluation de performances 22
2.1 Notions de performances du routage . . . . . . . . . . . . . . . . 23
2.1.1 Mesures externes de l’efficacité . . . . . . . . . . . . . . . 23
2.1.2 Mesures internes de l’efficacité . . . . . . . . . . . . . . . 23
iiiTABLE DES MATIÈRES iv
2.1.3 Paramètres d’évaluation . . . . . . . . . . . . . . . . . . . 24
2.1.4 Environnements de simulation . . . . . . . . . . . . . . . 24
2.2 Modèles de mobilité . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.1 Modèle Random Waypoint . . . . . . . . . . . . . . . . . 27
2.2.2 Modèle RPGM . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.3 Influence du modèle de simulation . . . . . . . . . . . . . 29
2.2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3 Résultats d’évaluation des protocoles de routage . . . . . . . . . 31
2.3.1 Etude de l’équipe Monarch . . . . . . . . . . . . . . . . . 31
2.3.2 Etude de l’équipe Ericsson . . . . . . . . . . . . . . . . . 32
2.3.3 Problèmes de performances de DSR et AODV . . . . . . . 33
2.4 Problématique du passage à l’échelle . . . . . . . . . . . . . . . . 37
2.4.1 Limitations de la diffusion . . . . . . . . . . . . . . . . . . 37
2.4.2 Etudes du passage à l’échelle . . . . . . . . . . . . . . . . 38
2.4.2.1 Définitions du groupe ANS . . . . . . . . . . . . 38
2.4.2.2 Travaux analytiques sur le passage à l’échelle . . 40
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3 Méthodes d’adaptation dans les réseaux ad hoc 43
3.1 Notions d’adaptation . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2 Adaptation à la mobilité . . . . . . . . . . . . . . . . . . . . . . 45
3.2.1 Métriques de mobilité . . . . . . . . . . . . . . . . . . . . 45
3.2.2 Choix d’une métrique de mobilité . . . . . . . . . . . . . . 48
3.3 Routage adapté à la taille du réseau . . . . . . . . . . . . . . . . 49
3.3.1 C-DSR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.3.2 Protocoles de routage hybrides . . . . . . . . . . . . . . . 51
3.3.2.1 ZRP . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.3.2.2 IZR . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.3 Routage basé sur la position . . . . . . . . . . . . . . . . 53
3.3.3.1 Servi