République Algérienne Démocratique et Populaire Ministère de l’Enseignement Supérieur et de la Recherche Scientifique

Université Constantine 2-Abdelhamid Mehri Faculté des Nouvelles Technologies de l’Information et de la Communication

Département d’Informatique Fondamentale et ses Applications

N° d’ordre: N° de Série: DR-SC/NTIC/2014/008

Thèse de Doctorat en Sciences Spécialité Informatique

Par Saloua CHETTIBI

Intelligence Computationnelle pour les problèmes de Routage adaptatif efficace en énergie

et multicritère dans les Réseaux Mobiles Ad-hoc

Directeur de thèse Pr. Salim CHIKHI

Soutenue publiquement le 08/01/2015, devant le jury composé de:

Faiza BELALA, Professeure, Université Constantine 2 -Abdelhamid Mehri Présidente Salim CHIKHI, Professeur, Université Constantine 2 -Abdelhamid Mehri Rapporteur Azeddine BILAMI, Professeur, Université de Batna Examinateur Abdellah BOUKERRAM, Professeur, Université de Bejaïa Examinateur Saleh MERNIZ, Maître de Conférences A, Université Constantine 2 -Abdelhamid Mehri Examinateur

Remerciements

« ال يشكر اهلل من ال يشكر الناس »

-نبوي حديث-

Je tiens à remercier, en premier lieu, Pr. Salim CHIKHI de m’avoir proposé la

résolution de l’équation comme sujet de thèse. Les travaux présentés

dans ce manuscrit n'auront jamais pu aboutir sans les conseils et les orientations qu’il

m’a donnés mais surtout pas sans sa confiance totale en moi.

Mes remerciements vont également à ceux qui m’ont fait l’honneur d’être les

membres de jury: Pr. Faiza BELALA comme présidente de jury, Pr. Salim CHIKHI

comme rapporteur, Pr. Azeddine BILAMI, Pr. Abdellah BOUKERRAM et Dr. Saleh

MERNIZ en qualité d’examinateurs.

Je suis profondément reconnaissante à Dr. Abdasselem LAYEB, membre de l’équipe

SCAL au laboratoire MISC, pour son aide précieuse dans l’analyse statistique de mes

résultats de simulation. Merci aux reviewers anonymes qui m’ont fait vraiment

progresser par des suggestions et mêmes des critiques.

Un grand merci à mon beau-frère Samir, à Mme. Ouafia GHEBGHOUB et à son époux

pour m’avoir facilité le payement des frais des communications internationales. Sans

votre aide, je n’aurais jamais pu soutenir.

J'adresse mes chaleureux remerciements à ma très chère mère et à ma sœur Nadjwa

pour la patience dont elles ont fait preuve à mon égard et pour l’encouragement dans

les moments les plus délicats. Cette page serait loin de suffire pour vous exprimer toute

ma reconnaissance et mon affection. Merci à mon frère Taha pour tous les conseils et

toutes nos diverses discussions scientifiques. Merci à ma sœur Dounia pour

l’encouragement et le soutien.

Des remerciements spéciaux à ma nièce et mes neveux pour m'avoir forcée à changer

d’activité de temps en temps.

Ce travail n’aurait pas pu être réalisé sans le soutien de mes amies que je remercie

tout particulièrement. Merci d’être toujours présentes lorsque j’ai besoin de vous.

Last but not least, merci à toutes les personnes qui ont eu un jour une pensée, une

discussion ou une action en faveur de ma thèse. Veuillez tous et toutes trouver dans

l’accomplissement de cette thèse le témoignage de ma plus profonde et sincère

gratitude.

Dieu Merci !

Jijel, le 19 Ramadane 1435.

édicaces

À mon défunt père.

D

p.i

لخصم

انمشاساخ في دانح انغض. اتخار انمشاس انتالؤييعى يشكهتي أساسيتي أال ا اتخار انمشاس ي ح شكتذان تجي انعهيح في انشثكاخ اناليشكضيح إ

استخال. دتى ك دساب انشاخ انخهى يا يسخ تصياغتا عهى شكم يسائم تذكى، تعهى أ انتعهمح تانتجي تتع تي ظثػ تعط انعاصشيثذأ انتذعيى فك، انتعهى استغالل انطك انغايط التشدانى يجال انزكاء انذساتي. عهى ج انتذذيذ، إنجأا سائمان ز يخم جضج انذنح ي دمألا

انعايح.انثذج خاسصيياخيح يجة إجضج انمانح تعم تاسطح تطاسياخ يذذدج انسعح فألتا أ ا هطالح. انذهل انمذيح في ز ن استالك في يك فعاال أ تجي انعه

في سغثح انجاص انذل انستعهح عايم ظثػشكانيح إ اغشدفي زا انصذد، . وؤالتيالئا االتاو تخاصيح انإاألغشدح تختهف ع ساتماتا ي ديج AODVيسأنح انشاسكح في عهيح استكشاف انشاخ في انثشتكل لا تصياغح نى زا، إ إظافحيسأنح تذكى غايط. اأ عهى OLSRانثشتكل

عهى سثح انجاح يش سهثيحتأانتائج انذصم عهيا أكذخ لذسج انذهل انمتشدح عهى تذيذ يذج خذيح انشثكح د يثذأ انتذعيى. فكيح تعهى شكمعهى يشكم تذج ع تصفتانماتم، تانا يظع تجي انعهيح انتعذد انخصائص انعهياخ أ عهى يتسػ انضي انستغشق في رنك. تجيفي

تطسيحان انخاسصيياختذاث راخ انصهح انتي تشتكض عهى أللذيا صفا شايال تشكيثيا ع ا ،عذج أذاف. في زا االتجا انطشيك األيخم تاعتثاس ا انتعذدج األغشاض.تيانستداج ي يستعشاخ انم في صيغ انخاسصيياخ

يح حشكتذانانشثكاخ اناليشكضيح :كلمات مفتاحية تجي انعهيح انفعال غاليا ، انطك انغايط، ، انتالؤيي، انزكاء انذساتي، تجي انعه، خصائصانثذج انعايح، تجي انعهيح انتعذد انخصائص، يشكم انثذج ع انطشيك األيخم تاعتثاس عذج خاسصيياخيثذأ انتذعيى، فكانتعهى

انستداج ي يستعشاخ انم انتعذدج األغشاض. انخاسصيياخانتعذدج األغشاض، تطسيحان خاسصيياخان

Résumé Le routage dans les réseaux mobiles ad hoc (MANETs) couple les deux problématiques de prise de décision

adaptative et incertaine. Les décisions liées au routage vont de l’ajustement de certains paramètres au calcul de chemins optimaux et peuvent donc être formulées comme des problèmes de contrôle, d’apprentissage ou d’optimisation. Afin de doter les nœuds mobiles de mécanismes appropriés à la résolution de tels problèmes, nous faisons recourt à la discipline de l’intelligence computationnelle. En particulier, nous proposons d’utiliser la logique floue, l’apprentissage par renforcement et les métaheuristiques.

Puisque la durée de vie des nœuds mobiles est limitée, le routage dans les MANETs doit être efficace en énergie. Les solutions que nous présentons au problème de prolongation de la durée de vie du réseau, contrairement à plusieurs solutions déjà proposées dans la littérature, sont adaptatives. Dans cette optique, nous formulons le problème d’ajustement du paramètre Willingness dans le protocole proactif OLSR en tant qu’un problème de prise de décision floue. En outre, nous proposons un modèle d’apprentissage par renforcement pour le problème d’acheminement des paquets de requêtes dans le protocole réactif AODV. Les solutions proposées réussissent à prolonger la durée de vie du réseau sans dégradation importante des performances en termes du taux de délivrance et du délai bout-en-bout moyen. De plus, le routage multicritère est abordé dans cette thèse comme un problème de plus court chemin multiobjectif dynamique. En cette direction, nous présentons une vue globale et synthétique sur les travaux relatifs s’appuyant sur les algorithmes évolutionnaires et de colonies de fourmis multiobjectif.

Mots-clés: Réseau mobile ad hoc, Intelligence Computationnelle, Routage Adaptatif, Routage Efficace en Energie, Logique Floue, Apprentissage par Renforcement, Métaheuristiques, Routage Multicritère, Problème de Plus Court Chemin Multiobjectif Dynamique, Algorithmes Evolutionnaires Multiobjectif, Algorithmes de Colonies de Fourmis Multiobjectif.

Abstract Routing in mobile ad hoc networks (MANETs) involves adaptive and uncertain decision-making issues.

Routing related decisions range from parameter adjusting to routing paths computation and could therefore be formulated as control, learning or optimization problems. To solve such problems, we propose in this thesis to use computational intelligence techniques, namely: fuzzy logic, reinforcement learning and metaheuristics.

Since mobile nodes are battery-powered, routing in MANETs should be energy efficient. Differently from previous related-works, the proposed solutions are adaptive. In particular, Willingness parameter tuning issue in OLSR proactive routing protocol is tackled as a fuzzy decision-making problem. Moreover, nodes participation in route discovery procedure of AODV reactive protocol is formulated as a reinforcement learning task. In terms of network lifetime, good results are achieved without degrading network performances in terms of data packets delivery ratio and end to end delay. Besides, we deal with the multicriteria routing issue in MANETs as a dynamic multiobjective shortest path problem. In this area, we present a comprehensive and a synthetic view on multiobjective evolutionary algorithms and ant colony optimization based routing protocols already proposed in the literature for MANETs.

Key-words: Mobile Ad hoc Networks, Computational Intelligence, Adaptive Routing, Energy-Efficient Routing, Fuzzy Logic, Reinforcement Learning, Metaheuristics, Multicriteria Routing, Dynamic Multiobjective Shortest Path Problem, Multiobjective Evolutionary Algorithms, Multiobjective Ant Colony Algorithms.

p.ii

Table des Matières

Introduction Générale ....................................................................................................................................................................... 1

Réseaux mobiles ad hoc et la problématique de routage

Introduction .................................................................................................................................................................................. 6 Réseaux sans fil ........................................................................................................................................................................... 6

Ondes électromagnétiques ................................................................................................................................... 8 Caractéristiques des liaisons sans fil .................................................................................................................. 9 Problèmes d’accès au médium sans fil ............................................................................................................... 9 Standard IEEE 802.11 et la méthode d’accès DCF .......................................................................................... 10

1.3 Réseaux ad hoc multi-saut ....................................................................................................................................................... 12 1.3.1 Réseaux ad hoc multi saut à topologie statique ............................................................................................... 13

1.3.1.1 Réseaux de capteurs sans fil ............................................................................................................. 13 1.3.1.2 Réseaux maillés sans fil ...................................................................................................................... 14

Réseaux mobiles ad-hoc ....................................................................................................................................... 15 1.3.2.1 Réseaux véhiculaires ad hoc ............................................................................................................. 16 1.3.2.2 Réseaux de drones ad hoc ................................................................................................................. 17

............................................................................................ 18 Routage vecteur de distance ................................................................................................................................. 18 1.4.2 Routage état de lien ................................................................................................................................................. 20 1.4.3 Routage vecteur de distance Vs Routage état de lien ..................................................................................... 21

1.5 Approches de routage conventionnelles dans les MANETs .............................................................................................. 21 1.5.1 Classification des protocoles de routage pour les MANETs.......................................................................... 23

Approche proactive ........................................................................................................................... 23 Approche réactive .............................................................................................................................. 24 Approche hybride .............................................................................................................................. 25

Routage multi-chemin ........................................................................................................................................... 25 .............................................................................................................................................................. 26

Routage efficace en énergie dans les MANETs ................................................................................................................... 27 Insuffisances des approches de routage traditionnelles ............................................................................... 28 Contrôle de la puissance ........................................................................................................................................ 29 Distribution de la charge ..................................................................................................................................... 30

1.6.3.1 Routage global ..................................................................................................................................... 30 1.6.3.2 Routage local ....................................................................................................................................... 31

Contrôle de la topologie ......................................................................................................................................... 32 1.7 Routage adaptatif et Intelligence Computationnelle .......................................................................................................... 32

1.7.1 Contexte d’adaptation ............................................................................................................................................ 33 1.7.2 Intelligence computationnelle ............................................................................................................................. 33

Conclusion .................................................................................................................................................................................... 35

p.iii

FEA-OLSR : une extension floue efficace en énergie du protocole de routage proactif OLSR

Introduction .................................................................................................................................................................................. 37 Logique Floue .............................................................................................................................................................................. 37

Concept d’ensemble flou ....................................................................................................................................... 38 Fonctions d’appartenance ..................................................................................................................................... 39 Variable linguistique .............................................................................................................................................. 40 Opérations de la logique Floue ............................................................................................................................ 41 Système de logique floue ...................................................................................................................................... 41 Modèle de Takagi, Sugeno et Kang ..................................................................................................................... 45

Protocole de routage OLSR........................................................................................................................................................ 47 Relai Multipoint ....................................................................................................................................................... 47 Diffusion via les nœuds MPRs dans OLSR ........................................................................................................ 47 Construction de la liste des voisins ..................................................................................................................... 48 Sélection des MPRs .................................................................................................................................................. 49 Construction de la table de topologie................................................................................................................. 49 Calcul de la table de routage ............................................................................................................................... 50

Etat de l’art sur les extensions efficaces en énergie du protocole OLSR ...................................................................... 50 Aperçu sur le routage efficace en énergie dans les MANETs en utilisant la logique floue ...................................... 52 Protocol FEA-OLSR .................................................................................................................................................................... 54

Entrées du SLF-Will ................................................................................................................................................ 55 Sortie du SLF-Will ................................................................................................................................................... 56 Base des règles .......................................................................................................................................................... 57 2.6.4 Contribution des fonctions d’appartenance dynamiques à l’adaptativité de SLF-Will......................... 57

Etude de performances .............................................................................................................................................................. 57 Implémentation et paramètres de simulation ................................................................................................. 59 Métriques de performances mesurées ............................................................................................................. 60 Comparaison des Performances des protocoles FEA-OLSR et EE-OLSR ................................................. 61

Conclusion ................................................................................................................................................................................... 64

Routage réactif local efficace en énergie à base d’apprentissage par renforcement avec extension floue

Introduction .................................................................................................................................................................................. 65 Apprentissage par renforcement ............................................................................................................................................ 65

Définition ................................................................................................................................................................. 66 Processus de Décision Markovien ...................................................................................................................... 66 Notions élémentaires .............................................................................................................................................. 67 Equation de Bellman ............................................................................................................................................... 68 Programmation Dynamique ................................................................................................................................. 69 Approches de résolution d’AR directes .............................................................................................................. 70

Méthodes de Monte Carlo ................................................................................................................. 70 Apprentissage de Différence Temporelle ...................................................................................... 71

Algorithme Q-Learning ................................................................................................. 72

p.iv

Algorithme SARSA .......................................................................................................... 73 SARSA( ) et Q( ) ............................................................................................................ 73

Apprentissage par Renforcement Collaboratif (ARC) .................................................................................... 74 Recherche de politique par la méthode du gradient ...................................................................................... 76

Etat de l’art sur le Routage adaptatif dans les MANETs en utilisant l’AR...................................................................... 77 Q-Routing ................................................................................................................................................................. 78 Protocoles MQ-Routing et LQ-Routing ............................................................................................................. 78 Recherche des chemins avec qualité de service .............................................................................................. 79 Routage sécurisé ..................................................................................................................................................... 80 Routage à base d’apprentissage par renforcement collaboratif .................................................................. 80 Recherche de politique de routage via la descente de gradient ................................................................. 81 Routage efficace en énergie .................................................................................................................................. 82

Routage réactif local efficace en énergie à base d’AR ........................................................................................................ 83 3.4.1 Modèle proposé et algorithmes d’apprentissage par renforcement utilisés ............................................ 83 3.4.2 Choix des approches appropriées pour la comparaison de performances .............................................. 84 3.4.3 Implémentation au-dessus du protocole AODV ............................................................................................. 85

3.5 Simulations et étude de performances ................................................................................................................................... 89 Etude de l’impact du paramètre sur les Performances de P-AODV ............................................... 90 Etude de l’impact du facteur sur les Performances de Q-AODV ........................................................... 90 Résultats des simulations sous les différents scénarios de trafic ............................................................... 91

Scénario d’un trafic faible ................................................................................................................. 91 Scénario d’un trafic moyen ............................................................................................................... 92 Scénario d’un trafic élevé .................................................................................................................. 94

Discussion des résultats ......................................................................................................................................... 95 Efficacité énergétique et performance globale des protocoles étudiés ...................................................... 96

Résultat d’évaluation de la métrique EE ....................................................................................... 97 Résultat d’évaluation de la métrique PG ...................................................................................... 98

.............................................................................................................................................................. 99 Extension floue du modèle d’apprentissage par renforcement proposé ...................................................................... 99 Apprentissage par renforcement Vs logique floue : une étude préliminaire de performances.............................. 101 Conclusion ................................................................................................................................................................................... 102

Optimisation multiobjectif des routes dans les MANETs : une revue critique de littérature 4.1 Introduction ................................................................................................................................................................................. 104 4.2 Optimisation multiobjectif et dynamique ............................................................................................................................ 104

4.2.1 Optimisation ............................................................................................................................................................. 104 4.2.2 Problème d’optimisation multiobjectif............................................................................................................... 106 4.2.3 Optimisation dynamique ....................................................................................................................................... 107 4.2.4 Optimisation multiobjectif dynamique ............................................................................................................ 107

4.3 Métaheuristiques pour l’optimisation multiobjectif et dynamique ............................................................................ 107 4.3.1 Métaheuristiques .................................................................................................................................................... 108

4.3.1.1 Calcul évolutionnaire ......................................................................................................................... 108 4.3.1.1.1 Algorithme évolutionnaire générique ........................................................................ 109

4.3.1.2 Intelligence en essaim ........................................................................................................................ 110 4.3.1.2.1 Optimisation par Colonie de Fourmis ....................................................................... 110

p.v

4.3.1.2.2 L’algorithme Ant System ............................................................................................... 111 4.3.2 Résolution des problèmes de l’optimisation multiobjectif ........................................................................... 112

4.3.2.1 Algorithmes évolutionnaires multiobjectif ................................................................................ 113 4.3.2.2 Algorithmes de colonie de fourmis multiobjectif ....................................................................... 114 4.3.2.3 Analyse de performance des méthodes de Pareto ....................................................................... 115

4.3.3 Résolution des problèmes de l’optimisation dynamique .............................................................................. 116 4.4 Problème de Plus Court Chemin MultiObjectif ................................................................................................................ 117

4.4.1 Définition du problème ...................................................................................................................................... 117 4.4.2 Description formelle ............................................................................................................................................. 118 4.4.3 Résolution du PPCCMO en utilisant les AEMOs et les ACFMOs ................................................................. 118

4.4.3.1 Adaptation de l’algorithme SPEAII pour la résolution du PPCCMO ...................................... 118 4.4.3.1.1 Algorithme SPEAII .......................................................................................................... 119 4.4.3.1.2 Adaptation de SPEAII au PPCCMO .............................................................................. 120

4.4.3.2 Extension multiobjectif de l’algorithme ACS ............................................................................. 121 4.5 Routage multicritère dans les MANETs ............................................................................................................................... 122

4.5.1 Routage avec qualité de service dans les MANETs ......................................................................................... 123 4.5.2 Métriques de routage ............................................................................................................................................. 123 4.5.3 Classification des problèmes de routage multicritère .................................................................................. 124

4.6 Aperçu sur l’application des ACFs et des AEs pour le routage monocritère dans les MANETs ............................. 125 4.6.1 Routage à base des ACFs dans les MANETs ....................................................................................................... 125 4.6.2 Routage à base des AEs dans les MANETs ......................................................................................................... 126

4.7 Routage multicritère dans les MANETs en utilisant les ACFMOs et les AEMOs ....................................................... 127 4.7.1 Algorithmes de routage à base des ACFMOs .................................................................................................... 127

4.7.1.1 Algorithmes de Constantinou .......................................................................................................... 127 4.7.1.2 Algorithme de Prasad et al. ............................................................................................................... 129

4.7.2 Algorithmes et protocoles de routage à base des AEMOs ............................................................................ 129 4.7.2.1 Protocole de Kotecha et Popat ......................................................................................................... 130 4.7.2.2 Protocole de Huang et Liu ................................................................................................................. 131 4.7.2.3 Protocole de Barolli et al. ................................................................................................................... 132 4.7.2.4 Algorithmes de Yetgin et al. . ............................................................................................................ 132

4.7.3 Synthèse ..................................................................................................................................................................... 133 Conclusion ................................................................................................................................................................................... 136 Conclusion Générale et perspectives............................................................................................................................................. 137 Annexe ............................................................................................................................................................................... 140 Références Bibliographiques ........................................................................................................................................................... 145