Gestion de la mobilité dans les réseaux Ad Hoc par anticipation des métriques de routage Sabrine Naimi To cite this version: Sabrine Naimi. Gestion de la mobilité dans les réseaux Ad Hoc par anticipation des métriques de routage. Physique des Hautes Energies - Réseau [hep-lat]. Université Paris Sud - Paris XI; École nationale d’ingénieurs de Tunis (Tunisie), 2015. Français. ￿NNT: 2015PA112145￿. ￿tel-01208152￿ HAL Id: tel-01208152 https://theses.hal.science/tel-01208152 Submitted on 2 Oct 2015 HAL is a multi-disciplinary open access L’archive ouverte pluridisciplinaire HAL, est archive for the deposit and dissemination of sci- destinée au dépôt et à la diffusion de documents entific research documents, whether they are pub- scientifiques de niveau recherche, publiés ou non, lished or not. The documents may come from émanant des établissements d’enseignement et de teaching and research institutions in France or recherche français ou étrangers, des laboratoires abroad, or from public or private research centers. publics ou privés. U P -S NIVERSITÉ ARIS UD ÉCOLE DOCTORALE STITS LABORATOIRE DES SIGNAUX ET SYSTÈMES (L2S) DISCIPLINE : PHYSIQUE T HÈSE DE DOCTORAT Soutenuele22juillet2015par Sabrine NAIMI Gestion de la mobilité dans les réseaux Ad Hoc par anticipation des métriques de routage Directeurdethèse: MmeVéroniqueVÈQUE Professeur(UniversitéParis-Sud) Directeurdethèse: MrRidhaBOUALLEGUE Professeur(UniversitédeCarthage) Co-directeurdethèse: MrAnthonyBUSSON Professeur(UniversitéLyon1) Compositiondujury: Présidentdujury: MrAnisLAOUITI Professeur(TélécomSudParis) Rapporteurs: MmeBéatricePAILLASSA Professeur(UniversitédeToulouse) MmeKaoutherSETHOM Maîtresdeconférences(UniversitédeCarthage) Examinateurs: MmeAnneFLADENMULLER Maîtresdeconférences(UniversitéPierre etMarieCurie) UNIVERSITÉPARIS-SUD Résumé LABORATOIREDESSIGNAUXETSYSTEMES Supelec DocteurenPhilosophie GestiondelamobilitédanslesréseauxAdHocparanticipationdesmétriquesderoutage parSabrineNAIMI Avec le succès des communications sans fil, il devient possible d’accéder au réseau partout et à tout moment sans avoir recours à connecter physiquement les appareils communicants à une infrastructure. Les noeuds (ordinateurs portables, smartphones, etc.) peuvent analyser les différentscanauxradioafindepouvoirs’associeràunréseausansfildisponible(stationdebase, point d’accès, etc.). Un avantageindéniable de ses technologies sans fil est la possibilité d’être mobile tout en restant connecté. Cependant, la mobilité est une tâche difficile à gérer car elle doitêtreabordéeàdifférentescouchespourêtretransparenteauxutilisateurs.DanslesMANET (Mobile Ad hoc Network), les protocoles de routage utilisent des métriques pour sélectionner les meilleures routes. Les métriques peuvent refléter la qualité de la liaison sans fil et aider à gérer la mobilité. Mais, un retard important entre l’estimation des métriques et leur inclusion dansleprocessusderoutagerendcetteapprocheinefficace. Lestravauxdecettethèses’intéressentàlapropositiondenouvellesméthodesdecalculdesmé- triquesderoutagepourgérerleproblèmedelamobilitédanslesréseauxadhoc.Lesnouvelles métriquesdoiventrefléterlaqualitédulienetêtresensiblesàlamobilitéenmêmetemps.Nous considéronslesmétriquesclassiques,enparticulierETX(ExpectedTransmissionCount)etETT (ExpectedTransmissionTime).Nousintroduisonsdenouvellesméthodespouranticiperlesva- leurs de ces métriques en utilisant des algorithmes de prédiction. Nous utilisons une approche CrossLayer,quipermetl’utilisationconjointedel’informationàpartirdescouches1,2et3.La validation de nouvelles méthodes de calcul des métriques de routage nécessite une évaluation autraversd’unvéritablebancd’essai.Nousavonsdoncégalementmisenoeuvrelesnouvelles métriquesderoutagedansuntestbedafind’évalueretdecomparerleursperformancesavecles métriquesclassiques. Dédicace JedédiecetravailàmachèrefilleMARAM(MIMI) J’espèrequetuserasfièredemoi Jet’aimeénormémentmaMIMI♡ iii Remerciements Jetiensàadresserenpremierlieumespluschaleureuxremerciementsàmadirectricedethèse, Véronique VEQUE, pour m’avoir confié ce travail de recherche, ainsi que pour son aide et ses précieuxconseilsaucoursdecesannées.Jesuistrèshonoréedel’avoireupourdirectrice. Je tiens à exprimer mes plus vifs remerciements à mon directeur de thèse, Ridha BOUAL- LEGUE,pourm’avoirapprisàêtreplusautonometoutaulongdecetravail.Jesuisravied’avoir travailléensacompagnieaucoursdecettethèse. Jesouhaiteraisexprimermagratitudeàmonco-encadrant,AnthonyBUSSON,pourlaconfiance qu’il m’a témoigné du début à la fin du travail, pour sa grande disponibilité à comprendre et à communiquer,sansoubliersesprécieusesintuitions.Jesuisravied’avoirtravailléensacompa- gnie car, outre son appui scientifique, il a toujours été là pour me soutenir et me conseiller au coursdel’élaborationdecettethèse.Enfin,j’aiétéextrêmementsensibleàsesqualitéshumaines d’écouteetdecompréhensiontoutaulongdecetravaildoctoral.Sincèrement,grâceàluij’aipu apprendre beaucoup de choses dont certaines fortes utiles pour mes travaux académiques bien sûr,maisaussideschosesimportantespourmondéveloppementpersonnel. Je voudrais remercier vivement Madame Béatrice PAILLASSA, Professeur à l’Université de ToulouseetMadameKaoutherSETHOM,Maîtresdeconférencesdel’UniversitédeTunisCar- thagepouravoirconsacrédutempsàlalecturedecedocumententantquerapporteurs. J’associe à ces remerciements Madame Anne FLADENMULLER, Maîtres de conférences de l’UniversitéPierreetMarieCurie,etMonsieurAnisLAOUITI,ProfesseurdeTélécomSudPa- ris,pouravoiracceptéd’examinermontravail. Aucoursdecesannéesetdanslecadredemathèseencotutelle,j’aieulachanced’êtremembre dupôleTelecomsetRéseauxdulaboratoiredesSignauxetSystèmes(LSS)deSupélecetaussi membre du laboratoire des Systèmes de Communications (SYS’COM) de l’École Nationale d’IngénieursdeTunis(ENIT).J’aipupartagerdesbonsmomentsavecdenombreusespersonnes attachantes. Je pense notamment de Supélec à : Assia, Boutheina, Sarra, Iyad, Lynda, Safaa, Mohamed,Mahmoud,Zeina,Alietdel’ENITà:Hafewa,Ihsen,Marwa,Walid,Zied,Mohamed Bedoui,Mohamed,Meriem,Mourad,Houssem,Dorsaf,Zeineb,etc. Je témoigne toute ma reconnaissance amicale à Racha Sellami et Ines Hassoumi pour leurs soutiens et leurs bonnes humeurs pendant mes stages à Paris. Elles ont rendu mes séjours plus agréablesàvivreenleurscompagnies. Ces remerciements ne peuvent s’achever, sans une pensée pour ma chère mère. Ses sacrifices, saprésenceetsesencouragementssontpourmoilespiliersfondateursdecequejesuisetdece que je fais. Un très grand merci aussi à mon cher papa pour son amour, ses encouragements et iv ses sacrifices. Ma grande gratitude va également à ma chère tata Zohra, pour son soutien infini pendant tous mes états de morale. Je vous aime énormément maman, papa et tata. Que Dieu vous protège et vous garde pour nous. Vient le moment de remercier mon frère Dali et mes deux soeurs Abir et Rania. Je les remercie énormément pour leur soutien sans failles et tout ce qu’ilsontpum’apporterpourfranchirlesobstacleslesplusdifficiles.Jevousaime.Jeremercie aussi mes chères tatas Saliha et Jamila et mon oncle Abdel Waheb pour leurs soutiens et leurs confiances en moi. Ils ont toujours cru en mon potentiel et n’ont jamais cessé de m’encoura- ger. Mes chères cousines Islem, Omayma, Asma, mes nièces Malak et Yasmine, et mon neveu Yasine,mercipourvotreprésencedansmavie.Jeremercietoutemafamillesansexception. J’aichoisideleslaisseràlafin,mesgrosbébés,mestrésors:moncherépouxZied,mesdeux fillesMimietKinzy.JeteremercieZaydounypouravoirsubimesmomentsdestressd’angoisse et de fatigue durant ces années de thèse. Il a su m’écouter, supporter ma mauvaise humeur et mon caractère insupportable. Je le remercie pour son soutien quotidien indéfectible et son enthousiasme contagieux à l’égard de mes travaux comme de la vie en général. Je te remercie chéripourtapatience,pourtonsoutien,pourtatendresseetc.toussimplementpourtonamour qui ne cesse pas de grandir. Je remercie mes deux anges Mimi et Kinzy : je suis désolée de ne pasêtretoujoursdisponible.Vousêtesmon«beausoleil»quim’aapportédelalumièredansma viepastrèsgaieàcettephasecauchemardesquequ’estlafindethèse.Notrefamilleagrandien mêmetempsquemonprojetscientifique,lepremierservantdesoclesolideàl’épanouissement dusecond. Je tiens à remercier aussi ma belle-mère Fatim Rebhi, mes belles soeurs Afra et Sondess, et MohamedNaimiquim’ontaidéetsoutenuaucoursdecettethèse. Enfin,jeprésentemesexcusesauxpersonnesquej’aipeut-êtreoubliéesdeciter,etquipourtant ontétéprésenteslorsdecettethèse,etj’adresseencoreunefoismesremerciementsàtousceux qui,deloinoudeprès,ontcontribuéàlaréussitedeceprésenttravail. Une pensée pour terminer ces remerciements pour toi qui n’a pas vu l’aboutissement de mon travailmaisjesaisquetuenauraisététrèsfierdetapetitefille!!! Table des matières Résumé ii Remerciements iv ListedesFigures ix Listedestableaux xi Introductiongénérale 1 0.1 Contextedelathèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 0.2 Organisationdumémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 0.3 Listedespublications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1 Lesréseauxmobilesadhoc 5 1.1 Lesréseauxmobilesadhoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.1 Définitiondesréseauxmobilesadhoc . . . . . . . . . . . . . . . . . . 7 1.1.2 Applicationsdesréseauxmobilesadhoc . . . . . . . . . . . . . . . . 8 1.2 Mobilitédanslesréseauxadhoc . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.2 Modèlesdemobilitépourlesréseauxadhoc . . . . . . . . . . . . . . 11 1.3 Protocolesderoutagedanslesréseauxadhoc . . . . . . . . . . . . . . . . . . 15 1.3.1 Problèmeduroutagedanslesréseauxadhoc . . . . . . . . . . . . . . 15 1.3.2 Classificationdesprotocolesderoutage . . . . . . . . . . . . . . . . . 15 1.4 LeprotocolederoutageOLSR . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.4.1 Découvertedesvoisins . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.4.2 Découvertedelatopologie . . . . . . . . . . . . . . . . . . . . . . . . 26 1.4.3 ChoixduprotocolederoutageOLSR . . . . . . . . . . . . . . . . . . 27 1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2 Classificationdesmétriquesdanslesréseauxadhoc 29 2.1 Métriquesderoutage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2 Métriquebaséesurlatopologieduréseau . . . . . . . . . . . . . . . . . . . . 32 2.2.1 LamétriqueHopCount . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3 Métriquesbaséessurlamesuredelapuissancedusignal . . . . . . . . . . . . 34 2.4 Métriquesdelaqualitédelien . . . . . . . . . . . . . . . . . . . . . . . . . . 35 vi 2.4.1 LamétriqueETX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.4.2 LamétriqueETT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.4.3 LamétriqueMTM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.5 Métriquesdechargedutrafic . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.5.1 LamétriqueEAB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.5.2 LamétriqueMF-TransmissionFailure . . . . . . . . . . . . . . . . . . 40 2.5.3 LamétriqueC2WB . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.5.4 LamétriqueMIND . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.6 Lesmétriquesmuti-canaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.6.1 LamétriqueWCETT . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.6.2 LamétriqueMIC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.6.3 LamétriqueMCR . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.6.4 LamétriqueiAWARE . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.6.5 LesmétriquesmETX&ENT . . . . . . . . . . . . . . . . . . . . . . 48 2.6.6 LamétriqueDBETX . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.6.7 LesmétriquesBATD&iBATD . . . . . . . . . . . . . . . . . . . . . 50 2.7 Métriquessensiblesàlamobilité . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.7.1 Les métriques Link Associativity Ticks & Path Aaverage degree of as- sociationstability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.7.2 LesmétriquesLinkAffinity&PathStability . . . . . . . . . . . . . . 53 2.7.3 LesmétriquesLinkAvailibity&PathAvailability . . . . . . . . . . . . 54 2.7.4 LamétriqueLD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.7.5 LamétriqueLinkChangeRate,LinkStateChangesl . . . . . . . . . 57 lc 2.7.6 LamétriqueLinkStabilityL . . . . . . . . . . . . . . . . . . . . . . 57 s 2.8 Taxonomiedesmétriquesderoutage . . . . . . . . . . . . . . . . . . . . . . . 58 2.9 Choixdesmétriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3 Implémentation&ÉvaluationdesmétriquesETX,ETTetLD 66 3.1 Calcul&implémentationdesmétriquesETX&ETT . . . . . . . . . . . . . . 67 3.1.1 ETX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.1.2 ETT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.2 Calcul&implémentationdelamétriqueLD . . . . . . . . . . . . . . . . . . . 73 3.3 Topologiesderéférence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.3.1 Topologiechaîne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.3.2 Topologiemesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.3.3 Topologieadhoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.4 Évaluationdesperformances . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.4.1 Configurationdelasimulation . . . . . . . . . . . . . . . . . . . . . . 77 3.4.2 Résultatspourlachaînedenoeud . . . . . . . . . . . . . . . . . . . . 78 3.4.3 Résultatspourleréseaumesh . . . . . . . . . . . . . . . . . . . . . . 81 3.4.4 Résultatspourlatopologiealéatoire . . . . . . . . . . . . . . . . . . . 84 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4 Algorithmesd’anticipationdesmétriquesderoutage 89 4.1 Algorithmesd’anticipationdesmétriquesderoutage . . . . . . . . . . . . . . 90 4.1.1 AnticipationbaséesurledéveloppementdeTaylor . . . . . . . . . . . 91 4.1.2 Anticipationbaséesurlaprédictiondelapuissancedusignalreçu . . . 94 4.2 ÉvaluationdesPerformances . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 4.2.1 Topologiechaîne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.2.2 Topologiemesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 4.2.3 Topologiealéatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 5 MiseenOeuvreduTESTBED 122 5.1 Testbedpourlesréseauxadhoc . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.1.1 Testbed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.2 Descriptiondenotretestbed . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.2.1 Paramètresdutestbed . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.2.2 Descriptionduscénario. . . . . . . . . . . . . . . . . . . . . . . . . . 130 5.3 Résultatsetdiscussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 Conclusion 137 A ANNEXEA 139 A.1 ConfigurationenmodeadhocenutilisantNetworkManager . . . . . . . . . . 139 A.2 Installationd’OLSRD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 A.3 Iperf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 Bibliographie 143