Rpublique Algrienne Dmocratique et Populaire Ministre de lEnseignement Suprieur et de la Recherche Scientifique Universit de constantine Facult des sciences et science de l'ingnieur Dpartement d'informatique N d'ordre : Srie : Mmoire Prsent en vue de lobtention du diplme de Magister en informatique Option : GL & IA.

ROUTAGE DANS LES RESEAUX MOBILES AD HOC PAR UNE APPROCHE A BASE D'AGENTSPrsent par : Mr BOUKHECHEM Nadhir

Soutenue-le : 25 / 06 / 2008 devant le jury compos de : Prsident :Mr BENMOHAMED Mohamed (Prof. Universit Mentouri de Constantine)

Rapporteur :Mr SAHNOUN Zaidi (Prof. Universit Mentouri de Constantine) (M.C. Universit Mentouri de Constantine) (M.C. Universit Mentouri de Constantine) Promotion 2007-2008

Examinateurs :Mr MAAMRI Ramdane Mme BELALA Faiza

1

Table des matiresTable des matires List des Figures Liste des Tableaux Remerciements viii Rsum Abstract Introduction gnrale 1. Les rseaux mobiles Ad Hoc iii vi vii

ix x 1 4

1.1. Introduction......................................................................................................................... 4 1.2. Les rseaux Mobiles ............................................................................................................ 4 1.2.1. Les rseaux mobiles avec infrastructure ....................................................................... 6 1.2.2. Les rseaux Ad Hoc ..........................................................................................................6 1.2.2.1. Les caractristiques des rseaux Ad Hoc................................................................... 7 1.2.2.2. Les applications des rseaux Ad Hoc ........................................................................ 8 1.3. La communication dans les rseaux Ad Hoc ........................................................................ 9 1.3.1. Le routage dans les rseaux Ad Hoc ............................................................................... 11 1.4. Le routage dans le modle OSI .......................................................................................... 11 1.5. Conclusion ....................................................................................................................... 12

2. Les protocoles de routage dans les rseaux ad hoc

13

2.1. Introduction....................................................................................................................... 13 2.2. Classification des protocole de routage Ad Hoc ................................................................. 13 2.2.1. Les protocoles Table-driven ............................................................................................ 14 2.2.2. Les protocoles On-demand ........................................................................................15 2.2.3. Les protocoles Hybrides ............................................................................................15 2.3. Quelques protocoles de routage pour les rseau ad hoc ...................................................... 16 2.3.1. Le protocole DSDV................................................................................................... 16 2.3.2. Le protocole GSR .....................................................................................................17 2.3.3. Le protocole FSR ......................................................................................................18 3.3.4. Le protocole AODV ..................................................................................................19 2.3.4.1 La dcouverte de route de route .............................................................................. 20 2.3.4.2 La maintenance de route .......................................................................................... 22 2.3.5. Le protocole DSR........................................................................................................... 23

2

2.3.6. Le protocole CBRP ...................................................................................................25 2.3.7. Le protocole ARA.....................................................................................................27 2.3.7.1. La dcouverte de route dans ARA........................................................................... 28 2.3.7.2. La maintenance de routes ....................................................................................... 30 2.3.7.3. Traitement des coupure de routes............................................................................ 30 2.3.8. Le protocole Ant-AODV............................................................................................31 2.4. Tableaux rcapitulatifs....................................................................................................... 32 2.5. Conclusion ........................................................................................................................ 34

3. Le routage a base d'agents dans les rseaux Ad Hoc 353.1. Introduction....................................................................................................................... 35 3.2. L'agent et les systmes multiagents.................................................................................... 35 3.2.1 Les SMA et le routage dans les rseaux ad hoc............................................................ 37 3.3. L'agent mobile .................................................................................................................. 37 3.3.1. L'environnement d'excution d'agents mobiles ................................................................ 38 3.3.2. Avantages des agents mobiles .................................................................................... 38 3.3.3. Les agents mobiles et le routage dans les rseaux Ad hoc ................................................ 38 3.4. Quelques Travaux relatives................................................................................................ 41 3.4.1 Le protocole MARP ........................................................................................................ 41 3.4.2 Un modle gnrique a base d'agents ............................................................................... 45 3.4.3 Le protocole MWAC....................................................................................................... 46 3.5. Conclusion ........................................................................................................................ 51

3. Proposition d'un protocole de routage base d'agents pour les rseaux Ad Hoc 524.1. Introduction....................................................................................................................... 52 4.2. Description du protocole propos ...................................................................................... 53 4.2.1. Le rle de chaque agents ........................................................................................... 53 4.2.1.1. Les agents mobiles ................................................................................................. 53 4.2.1.2. Les agents Statiques................................................................................................ 54 4.2.2. Le modle du systme ..................................................................................................... 54 4.2.3. Architecture de l'agent statique................................................................................... 55 4.2.4. Architecture de l'agent mobile .................................................................................... 56 4.2.5. Les interactions des agents .............................................................................................. 57 4.2.5.1. Interactions entre agents statiques et agents mobiles .............................................. 58 4.2.5.2. Interactions entre agents statiques ........................................................................... 61 4.3. Simulation ....................................................................................................................... 62 4.3.1. Le simulateur NS2 .......................................................................................................... 62 4.3.2. Le scnario utilis ........................................................................................................... 63 4.3.3. Rsultats obtenus ............................................................................................................ 64 4.3.3.1. La latence ............................................................................................................... 65

3

4.3.3.2. Le ratio .................................................................................................................. 65 4.3.4.3. La taille des paquets de contrle utiliss.................................................................. 66 4.4. Conclusion......................................................................................................................... 70

Conclusion gnrale Annexe Bibliographie

71 73 81

Liste des FiguresFigure 1.1 : Rseau mobile avec infrastructure ........................................................................... 3 Figure 1.2 : Un rseaux ad hoc compos de quatre noeuds ....................................................... 4 Figure 1.3 : Changement de la topologie d'un rseau ad hoc ..................................................... 5 Figure 1.4 : Communication entre deux noeuds dans un rseau ad hoc ...................................... 7 Figure 1.5 : Le modle OSI ........................................................................................................ 9 Figure 2.1 : Topologie du rseau et table de routage dans le protocole DSDV. ........................ 15 Figure 2.2 : Prcision des informations d'un noeud dans FSR .................................................. 17 Figure 2.3 : (a) Inondation de RREQ, (b) revoie du RREP dans AODV.................................. 19 Figure 2.4 : Coupure de route et envoie du RERR dans AODV ............................................... 20 Figure 2.5 : Dcouverte de route dans DSR ............................................................................. 22 Figure 2.6 : Assemblage en clusters dans CBRP ...................................................................... 23 Figure 2.7 : Recherche de nourriture par une colonie de fourmis .............................................. 26 Figure 2.8 : Dcouverte de route dans ARA ............................................................................. 27 Figure 2.9 : Dcouverte de route dans Ant-AODV ................................................................... 31 Figure 3.1 : Le modle d'agents pour le routage ....................................................................... 45 Figure 3.2 : Organisation des agents dans MWAC ................................................................... 47 Figure 3.3 : Interaction entre un agent et ses voisin pour dterminer son rle............................ 48 Figure 3.4 : Protocole dlection du meilleur reprsentant ....................................................... 50 Figure 4.1: Le modle du systme .......................................................................................... 54 Figure 4.2 : Architecture de l'agent statiques ............................................................................ 55 Figure 4.3 : Protocole d'change d'informations entre l'agent mobile et l'agent statique ............ 59 Figure 4.4 : Protocole de demande de migration de l'agent mobile ........................................... 60 Figure 4.5 : Protocole de recherche de route par l'agent statique .............................................. 61 Figure 4.6 : Simulation avec NS2 ............................................................................................. 63 Figure 4.7 : Les noeuds du rseau ad hoc utiliss a un instant donnes...................................... 64 Figure 4.8 : Histogrames dcrivant la Latence de notre protocole et du protocole AODV ..... 67

4

Figure 4.9 : Histogrames dcrivant le pourcentage de paquets reu ........................................ 68 Figure 4.10 : Histogrames dcrivant la taille des paquets de contrle utiliss .......................... 69

Liste des TableauxTableau 2.1 : Les classes des protocoles de routage pour les rseaux. ...................................... 32 Tableau 2.2 : Les protocoles de routage pour les rseaux. ........................................................ 34

5

RemerciementsSi ce mmoire a pu voir le jour, cest certainement grce au soutien et laide de plusieurs personnes qui mont permis daccomplir ce travail dans des conditions idales. Je profite de cet espace pour les remercier tous. Je voudrais tout dabord exprimer mes profonds remerciements a ma famille pour leur soutien inconditionnel, merci pour mavoir encourag, support et pour avoir accept tant de sacrifices durant cette priode. Je tiens remercier Mr SAHNOUN Zaidi Professeur lUniversit Mentouri de constantine pour son encadrement. Son exprience et ses qualits scientifiques ont toujours t sources denrichissement me permettant de mener bien ce travail. Enfin, je remerci Mr MAAMRI Ramdane , M.C. A l'Universit Mentouri de Constantine, et Mme BELALA Faiza , M.C. A l'Universit Mentouri de Constantine pour avoir accpt dtre les examinateurs de ce mmoire et Mr BENMOHAMED Mohamed Professeur A l'Universit Mentouri de Constantine pour avoir accpt dtre le prsident.

6

RsumLes rseaux mobiles ad hoc appels gnralement MANET (Mobile Ad hoc NETwork) sont un nouveau type de rseaux bass sur la technologie sans fil. Un rseau ad hoc est constitu d'un ensemble d'units de calcul portables comme les PDA (Personal Digital Assistant) et les laptops qui se dplacent librement et forment ensemble d'une manire dynamique un rseau interconnect. Les rseaux ad hoc ne dpendent d'aucune infrastructure prtablie, les noeuds mobiles doivent cooprer ensemble pour pouvoir grer leurs communications. Le routage est le problme le plus important dans les rseaux ad hoc en effet cause de la mobilit des noeuds il est trs difficile de localiser une destination un instant donn. Plusieurs protocoles de routage pour les rseaux ad hoc on t proposs ces protocoles essayent de maximiser les performances en minimisant le dlai de livraison des paquets, l'utilisation de la bande passante et la consommation d'nergie. Les systmes multiagents sont une nouvelle technologie issue du domaine de l'intelligence artificielle cette technologie est particulirement intrssante utiliser dans des environnements de nature distribu et dynamique comme les rseaux ad hoc. Dans ce mmoire on propose un protocole de routage pour les rseaux mobiles ad hoc bas sur les agents. Mots cls : Rseaux Mobiles Ad Hoc, Protocoles de routages Ad Hoc, Systmes Multiagents.

7

AbstractThe ad hoc mobile networks generally called MANET (Mobile Ad hoc NETwork) are a new type of networks based on wireless technology. An ad hoc network consists of a set of portable computing units such as PDA (Personal Digital Assistant) and laptops who move freely and form together in a dynamic way an interconnected network. The ad hoc networks not depend on any predetermined infrastructure, mobile nodes must cooperate together to be able to manage their communications.

The routing is the most important problem in ad hoc networks in effect because of the mobility of nodes it is very difficult to locate a destination at a given moment. Several routing protocols for ad hoc networks have been proposed these protocols are trying to maximize performance and minimize the time for delivery of packets, bandwidth usage and consumption of energy.

The multiagents systems are a new technology resulting from the field of the artificial intelligence this technology is particularly interesting to use in environments of nature distributed and dynamic like the ad hoc networks. In this report proposes a routing protocol for mobile ad hoc networks based agents.

Keywords: Mobile Ad Hoc Networks, Ad Hoc Routing Protocols, Multiagents Systems.

8

Introduction gnraleCes dernires annes le dveloppement de la technologie sans fil a ouvert de nouvelles perspectives dans le domaine des tlcommunications, les rseaux mobiles bass sur la technologie sans fil connaissent aujourd'hui une forte expansion. Les rseaux mobiles offrent une grande flexibilit d'emploi, ils permettent aux utilisateurs de se dplacer librement tout en continuant normalement leurs communications. Il existe deux types de rseaux mobiles, les rseaux mobiles avec infrastructure et les rseaux mobiles ad hoc. Les rseaux mobiles avec infrastructure sont bass sur un ensemble de sites fixes appels stations de base, ces sites vont relier les diffrents noeuds mobiles pour former un rseau interconnect. L'inconvnient de ce type de rseau c'est qu'il require le dploiement d'une importante infrastructure fixe. Les rseaux ad hoc en contrepartie n'ont besoin d'aucune infrastructure fixe prexistante. Un rseau ad hoc est constitu d'un ensemble d'units de calcul portables comme les PDA (Personal Digital Assistant) et les laptops qui sont munis d'une interface de communications sans fil. Ces units se dplacent librement dans une certaine zone gographique et forment ensemble d'une manire dynamique un rseau interconnect. Pour pouvoir communiquer entre eux chaque unit mobile doit jouer le rle dun routeur et dun terminal, et doit retransmettre les paquets des autres units mobiles. Les rseaux ad hoc offrent une grande flexibilit d'emploi et une grande robustesse et peuvent se dployer trs rapidement. Les recherches actuelles dans les rseaux ad-hoc sont diriges vers les algorithmes de routage. En effet cause de la mobilit des noeuds il est trs difficile de localiser une 9

destination un instant donn, les protocoles de routage conus pour des rseaux statiques sont donc inadapts pour ce type de rseaux. Plusieurs protocoles de routage pour les rseaux ad hoc ont t dvelopps, chaque protocole essaye de maximiser les performances du rseau en minimisant le dlai de livraison des paquets, l'utilisation de la bande passante et la consommation d'nergie. Les algorithmes de routage pour les rseux ad hoc peuvent se classer en trois catgories, les protocoles Table-Driven, les protocoles On-Demande et les protocoles Hybrides. Les protocole Tables-Driven maintiennent jour des tables de routage qui indiquent les routes vers chaque destination du rseau, les routes sont donc calcules mme si elles ne sont pas utilises. L'avantage de ces protocoles c'est que la connexion entre les noeuds est immdiate puisque les routes sont calcules l'avance, l'inconvnient c'est qu'ils utilisent beaucoups de paquets de contrle pour maintenir jour les tables de routage. Les protocoles On-Demand en contrepartie calculent les routes selon les besoins, la route est calcule quand elle est demande, l'avantage de ces protocoles c'est qu'ils utilisent moins de paquets de contrle que les protocoles Table-Driven, l'inconvnient est qu'ils ont un dlai inital avant de commencer la transmition des donnes, c'est le dlai ncssaire pour dterminer la route. Les protocoles hybrides essaient de combiner les deux approches prcdentes pour bnficier de leurs avantages mais ils cumulent aussi leurs inconvnients. Le probllme est donc de trouver un compromis et essayer d'avoir un dlai initial court tout en utilisant un minimum de paquets de controle. L'agent et les systmes multiagents sont une nouvelle technologie issus du domaine de l'intelligence artificielle. Les systmes multiagents sont appliqus dans beaucoup de domaines tels que les systmes distribus, les interfaces homme machine et les rseaux. Les systmes multiagents prennent en compte les aspects de coopration, d'autonomie, de distribution et d'intelligence, ils sont particulirement intrssants utiliser dans des environnements de nature distribu et dynamique comme les rseaux ad hoc. Un systme bas sur cette technologie semble donc appropri pour grer le routage dans les rseaux ad hoc et obtenir de meilleurs performances. Ce travail rentre dans le cadre de l'tude du problme de routage dans les rseaux mobiles ad hoc. Son objectif principal est de proposer un protocole de routage pour les rseaux ad hoc bas sur la technologie agent pour minimiser le dlai initial de transmissions des paquets de donnes et minimiser l'utilisation des paquets de contrle. Le protocole propos se base sur la coopration d'agents statiques et d'agents mobiles pour dcouvrir la topologie du rseau et calculer les routes entre les noeuds. Les agents mobiles sont

10

responsables de la collecte des informations de routage et de la dcouverte des routes, les agents statiques utilisent les informations fournies par les agents mobiles pour dterminer les meilleurs routes pour transmettre les paquets de donnes. Ce mmoire se divise en quatre chapitres : Dans le premier chapitre on prsente les rseaux mobiles ad hoc, leurs caractristiques, leurs applications et le problme de routage. Au deuxime chapitre on prsente une classification des diffrents protocoles de routage pour les rseaux ad hoc et on decrit en dtail quelques protocoles tout en indiquant leurs avantages et leurs inconvnients. Dans le troisime chapitre est prsent l'agent et les systmes multiagents et leurs avantages dans les rseaux ad hoc, ainsi que quelques protocoles de routage bass sur les agents. Au quatrime chapitre on propose un protocole de routage pour les rseaux ad hoc bas sur les agents, on donne le modle du systme, le role des diffrents agents et leurs intractions possibles, on compare notre protocole au protocole de routage AODV en utilisant le simulateur de rseau NS2 et on prsente les rsultats obtenus. Enfin on termine ce mmoire par une conclusion gnrale.

11

Chapitre 1 Les rseaux mobiles Ad Hoc1.1. IntroductionCes dernires annes le dveloppement de la technologie de transmission sans fil a offert de nouvelles perspectives dans le domaine des tlcommunications. Les rseaux mobiles ad hoc appels gnralement MANET (Mobile Ad hoc Network) constituent un 12

nouveau type de rseaux bass sur cette technologie. Un rseau mobile ad hoc permet ses utilisateurs de se dplacer librement tout en continuant normalement leurs communications, il peut se dployer rapidement et n'a besoin d'aucune infrastructure fixe prexistante. Dans se chapitre nous allons prsent les rseaux mobiles ad hoc leurs caractristiques, leurs applications et le problme de routage qui est le plus important dans ce type de rseaux.

1.2. Les rseaux MobilesUn rseau est dit mobile s' il permet ses utilisateurs daccder linformation indpendamment de leurs position gographique. Pour communiquer entre eux les noeuds du rseau mobile utilisent une interface de communication sans fil ( mdium radio ou infrarouge) qui permet de propager les signaux sur une certaine distance. Les rseaux mobiles offrent une plus grande flexibilit d'emplois et un plus grand confort par rapport au rseaux statiques. Nous pouvons distinguer deux classes de rseaux mobiles, les rseaux mobiles avec infrastructure de communication, et les rseaux mobiles sans infrastructure de communication ou les rseaux Ad Hoc.

1.2.1. Les rseaux mobiles avec infrastructureUn rseau mobile avec infrastructure est bas sur un ensemble de sites fixes appels stations de base qui sont interconnects entre eux travers un rseau de communication filaire, chaque station de base peut communiquer directement en utilisant une interface sans fil avec les noeuds mobiles se trouvant dans une zone gographique limite comme le montre la figure suivante :

13

UM UM UM UM UM

Station de base

Station de base

Rseau StatiqueUnit mobile UM UM

UM UM UM UM

Station de base

Station de base

Figure 1.1 : Rseau mobile avec infrastructure Un noeud dans les rseaux mobiles avec infrastructures se connecte et communique avec les autres noeuds du rseau a travers la station de base la plus proche dans sa port de communication, si le noeud mobile sort de la port de cette station il doit trouver une autre station de base pour continuer la communication. Les rseaux mobiles avec infrastructures cotent chre car ils demandent le dploiement d'une importante infrastructure fixe.

1.2.2. Les rseaux Ad HocUn rseaux Ad Hoc appel gnralement MANET (Mobile Ad hoc Network), est compos d'un ensemble relativement danse de noeuds mobiles qui se dplacent librement dans une certaine zone gographique sans aucune infrastructure fixe prexistante. Un noeud dans le rseau ad hoc communique avec un autre noeud directement (en utilisant son interface sans file), si ce dernier est dans sa port de transmission, ou indirectement par l'intermdiaire d'autres noeuds du rseau dans le cas contraire. Chaque noeud dans le rseau ad hoc doit se comporter comme un terminal, et aussi comme un routeur, et participer la dcouverte et la maintenance des routes entre les noeuds du rseau. Il y a aucune limitation de taille dans un rseau ad hoc , il peut contenir des dizaines ou

14

des milliers de noeuds, la figure suivante illustre un rseau ad hoc compos de quatre noeuds mobiles. Figure 1.2 : Un rseaux ad hoc compos de quatre noeuds Les rseaux Ad Hoc ont en thorie une trs grande robustesse puisque pour que le rseau cesse de fonctionner, il faudrait quun nombre important de noeuds qui le compose soit hors service. En effet si un des noeuds du rseau devient indisponible pour cause de dfaillance ou de manque d'nergie, cela ne change rien ou presque pour les autres noeuds qui vont se rorganiser et continuer leurs communications. Contrairement aux rseaux mobiles sans infrastructure o tout dpend de ltat des stations de base pour communiquer.

1.2.2.1. Les caractristiques des rseaux Ad HocLes rseaux ad hoc sont caractriss principalement par :

Une topologie dynamique : La topologie des rseaux ah hoc changent rapidement, et alatoirement , ceci est cause par la mobilit arbitraire des noeuds du rseau. Le changement de la topologie change les routes entre les noeuds et provoque la perte de paquets. La (figure 1.3) dplacement d'un noeud. illustre la topologie d'un rseau ad hoc avant et aprs le

4 1 2 5 3Dplacement

6 5 4

(Topologie avant le dplacement du noeud 5)

1 2

3 5

6

(Topologie aprs le dplacement du noeud 5)

Figure 1.3 : Changement de la topologie d'un rseau ad hoc. 1. Une Bande passante limite : Les noeuds dans les rseaux ad hoc utilisent une 15

technologie de communication sans fil, malgr des progrs trs importants la bande passante reste modeste compare aux technologies des rseaux filaires.

2. Des contraintes d'nergie : Les noeuds mobiles dans les rseaux ad hoc sont aliments par des sources d'nergie autonomes comme les batteries ou les autres sources consommables, la consommation dnergie devient alors un problme important.

3. Absence d'infrastructure : Les rseaux ad hoc ne dpendent d'aucune infrastructure prtablie, ceci rend la gestion du rseau plus complexe.

1.2.2.2. Les applications des rseaux Ad HocLes rseaux ad hoc sont rapides et faciles dployer, ils sont particulirement intressants pour les applications militaires ou l'installation d'infrastructure fixe est souvent impossible, ils peuvent tre aussi utilises dans :

Les oprations de recherche et de secours : en cas de tremblement de terre, de feux ou d'inondation, dans le but de remplacer rapidement linfrastructure dtruite. L'informatique embarque : dans des vhicules communiquant par exemple. Les entreprises : dans le cadre dune runion ou dune confrence. Les gares et aroports : pour la communication et la collaboration entre les membres du personnel.

D'une faon gnrale, les rseaux ad hoc sont utiliss dans toute application o le dploiement d'une infrastructure rseau fixe est trop contraignant, soit parce qu'il est difficile mettre en place, soit parce que la dure d'installation du rseau ne le justifie pas. [14].

1.3. La communication dans les rseaux Ad HocLes signaux envoys par les interfaces sans fil sattnuent au fur et mesure quils sloignent de leur metteur, un noeud dans les rseaux ad hoc ne peut donc pas communiquer avec un autre sil est situ trop loin de lui, il doit alors passer par des noeuds intermdiaires 16

pour atteindre la destination dsir . La figure 1.4 illustre la topologie d'un rseau ad hoc compos de cinq noeuds (A,B,C,D,E) , si le noeud A veut communiquer avec le noeud D qui n'est pas dans sa port de transmission, il doit passer par les noeuds intermdiaires B et E, on parle alors de communication Multi-saut ou Multi-hop .

F igure 1.4 : Com muni catio n entre deux noeuds dans un rseau ad hoc

Dans la figure (1.4) le noeud B peut communiquer directement avec les noeuds A, C et E, ces noeuds sont dit : Voisins . En gnrale un paquet dans le rseau ad hoc doit travers plusieurs noeuds avant d'atteindre sa destination.

La technique la plus basique pour raliser une communication entre un noeud source et un noeud destination dans les rseaux ad hoc est linondation, ou le noeud source va transmettre les paquets tous les noeuds voisins, chaque noeud mobile r-met a son tour les paquets quil reoit ses voisins jusqu' ce qu'ils arrivent la destination. Linondation consomme beaucoup de ressources (bande passante et nergie) et nest pas adapt pour les rseaux ad hoc.

1.3.1. Le routage dans les rseaux Ad HocGnralement, le routage est une mthode d'acheminement des informations la bonne destination travers un rseau de connexion donn [14]. Dans les rseaux ad hoc il existe aucune infrastructure fixe ou lment centrale qui peut grer le routage. Chaque noeud doit donc participer un protocole de routage qui lui permet de communiquer avec les autres noeuds du rseau.

17

La stratgie ( ou le protocole ) de routage est utilise dans le but de dcouvrir les chemins qui existent entre les noeuds d'un rseau. Le but principal d'une telle stratgie est l'tablissement de routes qui soient correctes et efficaces entre une paire quelconque d'units, ce qui assure l'change des messages d'une manire continue. [15].

A cause de la mobilit des noeuds dans les rseaux ad hoc il est trs difficile de localiser une destination un instant donn, les protocoles de routage conus pour des rseaux statiques sont inadapts pour ce type de rseaux. Un protocole de routage pour les rseaux ad hoc doit organis le rseau et prendre en compte les limitations existantes, il doit construire et maintenir les routes entre les diffrents noeuds et s'adapter la topologie changeante et imprvisible.

Un protocole de routage conu pour les rseaux ad hoc :

Doit offrir un support de communication fiable : le protocole doit permettre d'effectuer des change de donnes fiables entre les diffrents noeuds du rseau, Ncessite une distribution des oprations : le protocole doit tre entirement distribu,

Doit avoir un minimum de paquets de contrle : les paquets de contrles doivent tre garder le minimum possible car elles consomment une prcieuse bande passante et causent des collisions avec les paquets de donnes, Doit offrir de bonne performance : en terme de dlai de livraison des paquets de donnes, Doit Conserver les ressources : le protocole doit optimiser lutilisation des ressources comme la bande passante, lnergie et le processeur.

1.4. Le routage dans le modle OSILe modle de rfrence de connexion entre systmes ouverts OSI [9] ( reference model of Open Systems Interconnection) a pour objectif de permettre la cration de logiciel rseau modulaires et rutilisables indpendamment des techniques mises en oeuvre. Le modle OSI propose une architecture compose de sept couches (figure 1.5). Chaque couche propose un service aux couches qui lui sont adjacentes. 18

Figure1.5 : Le modle OSI.

La couche physique sert transmettre les donnes via un canal de communication et comprend le matriel ncessaire la ralisation de cette fonction, La couche liaison a pour fonction initiale la dtection derreurs dans la couche physique, La couche rseau permet lchange de donnes entre les noeuds du rseau, La couche transport permet de faire parvenir les donnes aux applications excutes par les noeuds, La couche session est linterface utilisateur du rseau, La couche prsentation soccupe des dtails relatifs aux interfaces comme, par exemple, les imprimantes, les formats de fichiers et les crans, La couche application contient les informations sur les applications rparties sur le rseau.

Les protocoles de routage sont associs a la couche rseau du modle OSI car c'est dans cette couche qu'on dtermine les routes qui doivent tre emprunter par les paquets de donnes.

1.5. ConclusionOn a prsent dans ce chapitre les rseaux mobiles ad hoc. Ils se distinguent des autres rseaux par leur grande flexibilit d'emploi et leur grande robustesse mais aussi par des 19

contraintes supplmentaires tel que la limitation d'nergie et l'absence d'lment central pour grer le rseau. On a aussi prsent le problme de routage qui est le plus important dans ce type de rseau, et les difficults poses par la mobilit des noeuds. Dans le chapitre suivant nous allons prsenter en dtail quelques protocoles de routage dvelopps pour les rseaux ad hoc.

Chapitre 2 Les protocoles de routage dans les rseaux Ad Hoc2.1. IntroductionCes dernires annes plusieurs protocoles de routage pour les rseaux ad hoc on t dvelopps, ces protocoles essayent de maximiser les performances en minimisant le dlai de livraison des paquets, l'utilisation de la bande passante et la consommation d'nergie. Dans ce chapitre nous allons prsenter une classification des protocoles de rouage existants et prsenter en dtail le fonctionnement de quelques protocoles toute en indiquant leurs avantages et leurs inconvnients.

2.2. Classification des protocole de routage Ad HocSelon la manire de cration et de maintenance des routes on peut les classer les protocoles de routage pour les rseaux ad hoc comme suit : protocoles Table-driven, protocoles On-demand et protocoles hybrides.

2.2.1. Les protocoles Table-drivenLe principe des protocoles Tabledriven est de maintenir jour des tables de routage qui 20

indiquent les routes vers chaque destination du rseau. Les protocoles de routage Tabledriven sont bases sur deux mthodes utilises dans les rseaux filaires, la mthode tat de Lien (Link State) et la mthode Vecteur de Distance (Distance Vector). La mthode Link State : Dans la mthode Link State chaque noeud diffuse priodiquement (par inondation) l'tat des liens avec ses voisins a tous les noeuds du rseau, chaque noeud maintien alors une vue globale de la topologie du rseau ce qui lui permet de calculer les routes pour atteindre chaque destination. On inonde aussi le rseau quand il y a un changement dans l'tat des liens. Cette mthode permet de trouver rapidement des alternatives pour transmettre les paquets en cas de coupure d'une route, on peut aussi utiliser simultanment plusieurs routes pour atteindre la mme destination. Le problme avec cette mthode est que la quantit dinformations stocker et diffuser peut devenir considrable si le rseau contient un grand nombre de noeuds. La mthode Distance Vector : Dans la mthode Distance Vector chaque noeud transmet ses voisins la distance (nombre de noeuds) qui le spare de chaque destination dans le rseau et le noeud voisin utiliser pour atteindre cette destination. En se basant sur les informations reues depuis tous ses voisins, chaque noeud calcul le chemin le plus court vers n'importe quel destination dans le rseau. Si la distance sparant deux noeuds change on rpte le processus de calcul. La mthode Distance Vector vite l'inondation, mais elles est moins prcise que la mthode Link State il est aussi difficile de trouver des routes alternatives en cas de coupure d'une route. Les liens entre les noeuds dans les rseaux ad hoc changent rapidement. Les deux mthodes prcdentes vont engendrer normment de paquets de contrle (inondation des tats des liens, et transmission des vecteurs de distance) ce qui les rend inadapts pour les rseaux ad hoc. Les protocoles Table-driven calculent les routes l'avance ils disposent donc des routes immdiatement vers les destinations du rseau. Le problme avec ces protocoles c'est qu'ils chargent le rseau avec les paquets de mise jour des tables de routage mme si le rseau n'est pas utilis. Parmi les protocoles Table-driven les plus connus on peut cit : DSDV, GSR et FSR.

21

2.2.2. Les protocoles on-demandA loppos des protocoles Table-driven les protocoles On-demand crent et maintiennent les routes selon les besoins, si un noeud veut envoyer un paquet une destination la quelle il ne connat aucune route, il lance un procdure de dcouverte de route globale qui va inonder le rseau avec un paquet de requtes et lui fournir les informations ncessaires pour atteindre cette destination. Si la route devient invalide une autre procdure de dcouverte de route est lance. Les protocoles On-demand rduise la charge des paquets de contrle compars aux protocoles Table-driven, surtout si le rseau est trs dynamique. Le problme avec ces protocoles c'est qu'ils ont un dlai initial avant de commencer la transmission des paquets provoquer par la procdure de dcouverte de route, aussi la redcouverte de route en cas de coupure gnre une charge supplmentaire. Parmi les protocoles On-demand on peut cit : DSR et AODV .

2.2.3. Les protocoles HybridesLes protocoles hybrides essaient de combiner les deux approches prcdentes pour bnficier de leurs avantages, ils utilisent un protocole Table-driven, pour connatre les voisins les plus proches, dans le but de rduire le dlai et un protocole On-demand au- del de cette zone prdfinie dans le bute de rduire la charge des paquets de contrle. Les protocoles hybrides cumulent aussi les inconvnients des protocoles Table-driven et des protocoles On-demand savoir les paquets de contrle priodique, et le dlai de dcouverte de route. Parmi les protocole hybrides on peut cit le protocole CBRP .

2.3. Quelques protocoles de routage pour les rseau ad hoc 2.3.1. Le protocole DSDVDSDV (Destination-Sequenced Distance-Vector) est un protocole de routage Tabledriven. Chaque noeud dans DSDV garde une table de routage qui donne pour chaque destination accessible dans le rseau :

Le noeud voisin utilis pour atteindre cette destination, Un numro de squence qui est envoy par le noeud destinataire et qui permet de distinguer les nouvelles routes des anciennes, 22

Le nombre de sauts (noeuds intermdiaires) pour atteindre cette destination.

Priodiquement chaque noeud dans le rseau diffuse par inondation un paquet de mise jour des tables de routage qui inclue les destinations accessibles et le nombre de sauts exigs pour atteindre chaque destination avec le numro de squence li chaque route. Des paquets de mise jour sont aussi diffuss immdiatement si il y a un changement dans la topologie du rseau afin de propager les informations de routage aussi rapidement que possible.

A la rception dun paquet de mise jour, chaque noeud le compare avec les informations existantes dans sa table de routage. les routes les plus rcentes (qui ont le plus grand numro de squence) avec la distance la plus courte sont gardes, les autres sont simplement ignores. La figure (2.1) illustre la topologie d'un rseau ad hoc a un instant donn et la table de routage correspondant au noeud (1) dans le protocole DSDV.Destination Prochain Distance Numro de saut squence

4 3 6 5 2 7

4 2 2 4 2 4

1 2 2 3 1 2

10 32 88 19 12 57

23

Figure 2.1 : A gauche topologie du rseau, a droite table de routage du noeud (1) protocole DSDV.

dans le

DSDV fourni a tout moment des routes valables vers toutes les destinations du rseau, mais l'inondation des paquets de mise jour (priodique et en cas de changement de topologie) cause une charge de contrle importante au rseau.

2.3.2. Le protocole GSRDans le protocole Table-driven GSR (Global State Routing) chaque noeud maintient une table de la topologie qui l'informe sur la topologie globale du rseau et lui permet de calculer les routes pour atteindre chaque destination. GSR utilise la mthode Link State des rseaux filaires et l'amliore en supprimant le mcanisme d'inondation des paquets de contrle. Un noeud dans GSR maintient :

Une liste de voisins, Une table de topologie qui contient les informations sur les liens du rseau, Une table des noeuds suivants qui indique le noeud utiliser pour atteindre chaque destination, Une table de distance qui contient la plus courte distance pour chaque destination.

Comme dans la mthode Link State chaque noeud dans GSR construit sa table de topologie bas sur les informations de liens reus, et l'utilise pour calculer les distances minimales qui le spare des autre noeuds du rseau. Dans GSR la table de topologie entire de chaque noeud est chang priodiquement uniquement avec les voisins au lieu de la diffus par inondation dans tout le rseau. GSR rduit la charge des paquets de contrle en vitant l'inondation et assure plus de prcision, concernant les donnes de routage. Le problme de GSR est la taille des ses paquets de mise jour (Table de topologie) qui peut devenir considrable si le rseau contient un grand nombre de noeuds.

2.3.3. Le protocole FSRUne caractristique observ dans l'oeil de poisson (Fish eye) est qu'il distingue les choses en dtail au centre, et que sa prcision se dgrade en s'loignant du point central.

24

FSR (Fisheye State Routing) est un protocole Table-diriven, il minimise la charge des paquets de mise jour des tables de routage du protocole GSR en utilisant la technique de l'oeil de poisson. Les paquets de mise jour dans FSR, ne contiennent pas linformation sur tous les noeuds du rseau, il change les informations sur les noeuds les plus proches plus frquemment qu'il le fait sur les noeuds les plus lointains, il rduit ainsi la taille des paquets de mise jour. Un noeud dans FSR a donc des informations prcises sur les noeuds proches (figure 2.2 : Zone 1), la prcision des informations diminue quand la distance augmente (Figure 1.5: Zone 2 et 3).

Zone 1 Zone 2 Zone 3

Figure 2.2 : Prcision des informations d'un noeud dans FSR en utilisant la technique oeil de poisson. Malgr qu'un noeud dans le rseau n'a pas des informations prcises sur les noeuds loigns (surtout si le rseau est trs dynamique), les paquets peuvent tre transmis correctement car l'information sur les routes devient de plus en plus prcise quand les paquets se rapprochent de leurs destinations.

2.3.4. Le protocole AODVLe protocole AODV (Ad hoc On-demand Distance Vector) appartient a la famille des protocoles On-Demand, il est bas sur deux mcanismes, la dcouverte de route et la

25

maintenance de route. La dcouverte de route permet de trouver une route pour atteindre une destination et cela en inondant un paquet de requte dans tout le rseau. La maintenance de route permet de dtecter et signaler les coupures de routes provoques ventuellement par la mobilit des noeuds. AODV n'utilise pas des mises jour priodique, les routes sont dcouvertes et maintenues selon les besoins. Chaque noeud intermdiaire qui se trouve dans la route entre un noeud source et un noeud destination doit garder une table de routage qui contient :

Ladresse de la destination. Le noeud suivant utiliser pour atteindre la destination. La distance en nombre de noeud : C'est le nombre de noeud ncessaire pour atteindre la destination. Le numro de squence destination : Il permet de distinguer les nouvelles routes des anciennes. Le temps dexpiration de lentre de la table : C'est le temps au bout du quel lentre est valide.

AODV utilise trois types de messages pour crer et maintenir les routes, le RREQ (Route Request) pour demander une route, le RREP (Route Reply) pour rpondre une requte de demande de route, et le RERR (Route Error) pour signaler une coupure de route.

2.3.4.1 La dcouverte de route de routeSi un noeud dans AODV veut communiquer avec une destination la quelle il ne possde pas de route valide, il inonde le rseau avec une requte de demande route (RREQ : Route REQuest) qui contient : son adresse, son numro de squence, l'adresse de la destination, la dernire valeur connue du numro de squence de la destination, et le numro de la requte. La rponse la requte (RREP) est retourne par la destination ou par un autre noeud qui possde une route la destination. La RREP contient l'adresse du noeud source, l'adresse de la destination, le numro de squence de la destination et le nombre de sauts pour atteindre la destination. La figure suivante illustre l'inondation de la requte de demande de route par le noeud source et le renvoie de la rponse par le noeud destination dans AODV. 26

(a)

(b) Figure 2.3 : (a) Inondation de RREQ, (b) revoie du RREP dans AODV. Si le noeud metteur de la requtte ne reoit pas de rponse RREP pendant une certaine priode (appel RREP_WAIT_TIME) il rediffuse une nouvelle requtte. Si la requte RREQ est rediffuse un certain nombre de fois (RREQ_RETRIES) sans recevoir de rponse une erreur est dclenche. Un noeud intermdiaire (se trouvant entre un noeud source et un noeud destination) qui rediffuse une requte de route (figure 2.3 (a) ), sauvegarde l'adresse du noeud source qui a envoy la requtte la premire fois et l'adresse du noeud voisin qui lui a transmit la requtte, cette information est utilise pour reconstruire la route inverse qui sera traverse par la rponse de route (RREP) (figure 2.3 (b) ).

2.3.4.2 La maintenance de route27

Chaque noeud dans AODV maintient une liste des ses voisins. Avec une cadence d'une fois par seconde chaque noeud va transmettre un message HELLO, Si un noeud ne reoit pas d'un voisin trois messages HELLO conscutifs (pas de messages pendant trois secondes) le lien avec le voisin est considr invalide. Si un lien entre deux noeuds est invalide ( cause de la mobilit ou la dfaillance d'un noeud), les noeuds utilisant se lien sont prvenus par un message d'erreur (RERR) , ils vont alors diffuss une autre requtte. La figure suivante illustre la coupure d'un lient entre deux noeuds et l'envoi du RERR dans AODV.

Figure 2.4 : Coupure de route et envoie du RERR dans AODV. Le protocole AODV utilise l'inondation pour dcouvrir les routes, si le rseau est trs utilis il peut gnrer un trafic de contrle norme. Aussi AODV tant un protocole OnDemand il a un dlai initial avant de commencer la transmission des paquets.

2.3.5. Le protocole DSRDSR (Dynamic Source Routing) est un protocole On-demand semblable au protocole AODV, il utilise une technique appel Source Routing dans laquelle l'metteur (la source) indique la route complte par lequelle un paquet doit passer pour atteindre sa destination, cette route est insre dans l'entte du paquet. Les noeuds intermdiaires entre le noeud source et le noeud destination n'ont pas besoins de maintenir jour les informations sur la route travers puisque la route complte est insre dans l'entte du paquet. Si un noeud dans DSR veut communiquer avec une destination laquelle il ne possde pas de route, il inonde le rseau avec un paquet de requte (RREQ) similaire a celui de AODV. Chaque noeud qui reoit la requte et qui ne possde pas de route la destination demande insre son adresse dans le paquet RREQ et le diffuse ses voisins. La rponse la

28

requte (RREP) est retourne par la destination ou par un autre noeud qui possde une route la destination (figure 2.5). (Inondation de la requte)

(Renvoie de la rponse) Figure 2.5 : Dcouverte de route dans DSR. Les routes dans AODV sont construites en traversant la route inverse ver la source (de la destination la source), dans DSR les routes sont construites quand la requte traverse le rseau vers la destination (de la source la destination). Si un noeud reoit un paquet de donnes, et le lien a utiliser pour retransmettre ce paquet est coup (coupure de route) le noeud envoie un message d'erreur de route (RERR) semblable celui de AODV au noeud source. Le noeud source va lancer une autre requte de dcouverte de route pour atteindre la destination. Le protocole DSR comme le protocole AODV utilise l'inondation pour dcouvrir les routes ce qui gnr un trafic de contrle norme quand le rseau est trs utilis. Aussi la taille des paquets de donnes dans DSR devient trs grande quand le nombre de noeuds dans rseau est grand, puisque les paquets doivent porter les adresses de chaque noeud dans la route traverse. DSR a aussi un dlai avant de commencer la transmission des paquets provoqus par la procdure de dcouverte de route.

2.3.6. Le protocole CBRPLe protocole de routage CBRP (Cluster Based Routing Protocol) est un protocole Hybride. Il utilise deux niveaux hirarchiques pour effectuer le routage. Les noeuds dans 29

CBRP sont rassembls en groupes appels Clusters , avec un chef au centre de chaque groupe appel Clusterhead . Les clusters sont reli entre eux par des noeuds passerelles qui se trouvent l'extrmit des clusters. CBRP utilise un protocole Table-driven pour maintenir les membres du cluster, et un protocole On-demand pour dcouvrir les noeuds en dehors du cluster. Le diamtre d'un cluster dans CBRP est de deux sauts, un exemple d'assemblage en cluster est illustr dans la figure suivante :

M M C P C M

P C M

C : Chef M : Membre P : Passerelle. Figure 2.6 : Assemblage en clusters dans CBRP. Le principe de formation des clusters dans CBRP est le suivant : 1. 2. 3. 4. Les noeuds schangent des messages Hellos pour connatre leurs voisinages. Les noeuds vont lire le noeud avec le plus petit identifiant chef de cluster. Un noeud qui n'a pas de chef de cluster comme voisin devient chef de cluster. Le chef de cluster prend tous ses voisins comme membres de son cluster.

Pour viter des changements frquents dans les structures des clusters, les chefs sont maintenus le plus longtemps possible. Un chef de cluster n'est pas chang mme si un nouveau membre (non chef) de sont cluster a un identifiant plus petit. Si par la suite d'un changement de topologie deux chefs de clusters ont un lien direct entre eux, il faut reconstruire les clusters et le noeud possdant l'identifiant le plus faible est lu comme chef.

30

Chaque noeud dans CBRP maintient une table de voisinage qui indique le statut (membre, ou chef) de ses voisins. Un chef de cluster maintient aussi une liste des noeuds membres de son cluster, et une liste des chefs de clusters voisins avec les adresses des noeuds passerelles pour les atteindre. Quand un noeud source dans CBRP veut envoyer un paquet de donnes un noeud destination, il transmet au chef de son cluster un paquet de requte qui contient l'adresse de la destination dsire, le chef de cluster va insrer son adresse dans le paquet et le diffuse aux chefs de clusters voisins. Quand un chef de cluster reoit un paquet de requte de route, il vrifie dans sa liste des noeuds membre si le noeud destination appartient a son cluster. Si c'est le cas il rpond au noeud source en inversant la route enregistr dans le paquet de requte, si non il enregistre son adresse dans le paquet de requte et le diffuse aux chefs de clusters voisins. Si le noeud source ne reoit pas de rponse au cours d'une certaine priode de temps, il envoi une autre requte son chef. CBR utilise la technique Source Routing . Comme dans DSR la route complte vers la destination est insre dans l'entte du paquet . Le routage par source permet CBRP de faire des des raccourcissements de routes s' il y a un changement de topologie. Quand un noeud reoit un paquet il essaye de l'envoyer au noeud voisin le plus lointain dans la route, ce qui raccourci la route utilise. Si un noeud dans CBRP reoit un paquet de donnes et le lien ver le noeud suivant est coup (coupure de route) il envoie un message d'erreur la source et essaye de rparer la route localement. Il vrifie s' il peut atteindre le noeud suivant dans la route, ou le noeud qui vient aprs le noeud suivant par un autre voisin, si c'est le cas le paquet est envoy sur la route rpare. CBRP diffuse les requtes de route seulement au chefs de cluster. il rduit ainsi la charge provoque par l'inondation des requtes de route. Mais la formation et la maintenance des clusters engendrent une charge supplmentaire au rseau. Aussi les chef de clusters sont responsables de l'acheminement des donnes se qui peut provoquer des goulets d'tranglement.

2.3.7. Le protocole ARAARA ( Ant-Colony-Based Routing Algorithm) est un protocole On-demand. Il se base sur les techniques d'optimisation par colonie de fourmis (ACO). ARA utilise des agents

31

fourmis pour dcouvrir et maintenir les routes entre les noeuds du rseau. L'ide de base des algorithme d'optimisation par colonie de fourmis est inspir du comportement des fourmis rel quand elles recherchent la nourriture. Les fourmis russissent toujours trouver le chemin le plus court pour atteindre la nourriture. La figure 2.7 illustre un scnario avec deux chemins possibles pour atteindre la nourriture. Quant les premires fourmis arrivent a l'intersection des deux chemins il vont choisir alatoirement le chemin prendre. Les fourmis en parcourant le chemin vont dpos une matire appele phromone, cette matire indique aux autres fourmis le chemin utiliser. Le phromone s'vapore avec le temps. la quantit de phromone dpose sur le deuxime chemin va devenir plus importante que celle dpose sur le premier chemin puisque les fourmis parcourent le deuxime chemin plus vite. Avec le temps toutes les fourmis vont utiliser le deuxime chemin qui est le chemin le plus court.

Figure 2.7 : Recherche de nourriture par une colonie de fourmis Ce comportement est utilis dans ARA pour trouver la route la plus courte entre un noeud source et un noeud destination dans le rseau. ARA se compose de trois phases la dcouverte de routes, la maintenance de routes et le traitement des coupure de routes.

2.3.7.1. La dcouverte de route dans ARADans la phase de dcouverte de routes de nouvelles routes sont cres. Dans cette phase deux types de fourmis sont utilises, les forward ant (FANT) pour maintenir le phromone vers le noeud destination et a backward ant (BANT) pour maintenir le phromone vers le 32

noeud source. Les fourmis sont en ralit de simples paquets avec un numro de squences uniques qui permet de les distinguer. Un noeuds source qui cherche une route pour atteindre un noeud destination va diffuser un forward ant (FANT) ses voisins. Un noeud qui reoit un FANT pour la premire fois cre un enregistrement dans sa table de routage, qui contient les champs suivant :

Destination address : C'est l'adresse du noeud source. Next hop : C'es l'adresse du voisin par lequel il a reu le FANT. Pheromone value : C'est la valeur du phromone, qui dpend du nombre de noeuds que le FANT a travers. Elle reprsente la trace du phromone laiss par les fourmis.

Aprs avoir cr l'enregistrement, le noeud transmet le FANT ses voisins (figure 2.8 (a) ). Les FANT dupliqus sont identifis et dtruits grasse leurs numros de squences uniques. Quand le FANT atteint la destination un backward ant (BANT) est cr et envoy au noeud source (figure 2.8 (b) ), le BANT effectue les mmes taches que le FANT. Quand le noeud source reoit le BANT de la destination, la route est tablie et les paquets de donnes peuvent tre envoyer. (a) Envoi du backward ant par le noeud source.

(b) Envoi du forward ant par le noeud destination. Figure 2.8 : Dcouverte de route dans ARA. Les deux figures prcdentes illustrent la phase de dcouverte de route dans ARA, le noeud source a une seule trace de phromone pour atteindre la destination (en utilisant le noeud 1), mais le noeud destination a deux traces de phromone pour atteindre la source (en utilisant les noeuds 5 et 6). ARA peut donc crer plusieurs routes dans une seule phase de dcouverte de route (multi-path routing).

33

2.3.7.2. La maintenance de routesLes routes dans ARA sont maintenues durant la communication. Aprs que les fourmis FANT et BANT ont tabli les traces de phromones entre la source et la destination, les paquets de donnes transmis sont utiliss pour maintenir ces traces. Quand un noeud intermdiaire Ni retransmet un paquet de donnes pour une destination D, en passant par le voisin Nj, il augmente la quantit de phromone dans l'enregistrement (D, Nj, Ph), la route vers la destination est donc renforce par les paquets de donnes. Aussi le voisin Nj augmente la quantit de phromone dans l'enregistrement (S, Ni, ph), Donc la route vers la source est aussi renforce. L'vaporation du phromone est simule en diminuant rgulirement la quantit de phromone dans tous les enregistrements. Avec le temps le chemin le plus court entre la source et la destination va tre utilis.

2.3.7.3. Traitement des coupure de routes.Les coupures de route sont provoques par la mobilit des noeuds dans le rseau, Si un noeud ne peut pas retransmettre un paquet vers sa destination ( cause d'une coupure d'un lien) , le paquet est retourn vers le noeud source avec un message d'erreurs de route (ROUTE ERROR). Le voisin en recevant le message d'erreurs va dsactiver ce lien en donnant la valeur 0 a la quantit de phromone dans la table de routage. Il cherche ensuite dans sa table de routage une autre alternative pour retransmettre le paquet. Si le paquet ne peut pas atteindre sa destination, le noeud source lance une autre phase de dcouverte de route. Le protocole ARA permet la dcouverte de plusieurs routes pour la mme destination, s'a permet de trouver rapidement des alternatives en cas des coupures d'une route. Aussi le protocole s'adapte au changement de topologie puisque la route la plus courte entre la source et la destination va merger progressivement. Mais la phase de dcouverte de route engendre un trafique considrable puisque les FANT sont inonde dans le rseau pour chercher les routes vers la destination, en plus ARA a un dlai avant de comancer la transmission des paquets provoqus par la phase de dcouverte de route.

2.3.8. Le protocole Ant-AODVLe protocole Ant-AODV est une combinaison du protocole AODV et des capacits de dcouverte de routes des agents fourmis. chaque noeud dans ce protocole maintient une table de routage qui indique pour chaque destination le noeud voisin utiliser pour atteindre la

34

destination. Cette table est maintenu par les agents fourmis qui se dplacent dans le rseau et dcouvre les routes entre les noeuds (figure 2.9). Les agents fourmis sont de simples paquets avec un numro de squence unique qui permet de les distinguer.

Figure 2.9 : Dcouverte de route dans Ant-AODV. Si un noeud veut envoyer des paquets a une destination pour la quelle ils n'a pas de routes rcentes dans sa table de routage, il lance une dcouverte de route en utilisant le protocole AODV. Le noeud inonde le rseau avec la requte de demande route RREQ qui contient son adresse et l'adresse de la destination. La rponse la requte (RREP) est retourne par la destination ou par un autre noeuds qui possde une route la destination. L'utilisation des agents fourmis avec AODV permet de fournir plus de routes aux noeuds ce qui par la suite rduit le coup de la dcouverte de routes, mme si un noeud lance une requte pour une destination pour laquelle il n'a pas de routes rcentes la probabilit de recevoir une rponse rapidement de ses voisins est grande ce qui a pour rsultat la rduction du dlai de dcouverte de routes.

2.4. Tableaux rcapitulatifsNous dcrivons dans les deux tableux suivants les diffrentes classes de protocoles de routage pour les rseaux ad hoc ainsi que les protocoles de routage prsents dans ce chapitre.

35

ClassesTable-Driven

Caractristiques

Avantages

Inconvnientsde

- Calculer les routes a - Transmission immdiate - Utiliser beaucoup l'avance. des donnes. paquets de contrles.

On-Demand

- Dlai initial avant de - Calculer les route a la - Utiliser moins de paquets commencer la transmission demande. de contrles. des donnes. - Bnficier des avantages - Cumuler les inconvnients - Combinaison des deux des deux approches des deux approches approches prcdentes. prcdentes. prcdentes.

Hybride

Tableau 2.1 : Les classes des protocoles de routage pour les rseaux ad hoc.

Protocoles

Classe

Avantages

Inconvnients

DSDV

- Fournit a tout moment des routes - L'inondation des paquets de Table-Driven valables ver toutes les destinations mise a jour cause une charge de du rseau. contrle importante au rseau. vite l'inondation en - Taille considrable Table-Driven transmttant les paquets de mise a paquets de mise a jour. jour seulement aux voisins. - Minimise la charge des paquets - Taille considrable de mise a jour des table de paquets de mise a jour. Table-Driven routages du protocole GSR en utilisant la technique de l'oeil de poisson. On-Demand des

GSR

des

FSR

AODV

- Dcouvre les route a la demande - Dlai initial avant de en inondant le rseau avec un commencer la transmission des paquets de requte. donnes.

36

Protocoles

Classe

Avantages

Inconvnients

- Dcouvre les route a la demande - Dlai initial avant de en inondant le rseau avec un commencer la transmission des paquets de requte. donnes. DSR On-Demand - Les paquets de donnes peuvent - La taille des paquets de tre redirig pendant leurs donnes trs grande quand le transmission. nombre de noeud dans rseau est grand. - Diffuse les requte de route - La formation et la maintenance seulement au chefs de cluster se des cluster engendre une charge qui permet de rduire la charge supplmentaire. provoqu par l'inondation des requte de route. - Dcouvre les route a la demande - La phase de dcouverte de en utilisant les techniques route engendre un trafique d'optimisation par colonie de considrable. fourmis. - Permet de trouver rapidement des alternative en cas des coupure d'une route. Ant-AODV - Rduit le coup de la dcouverte - Les fourmis peuvent engendrer Table-Driven de routes en combinant les fourmis un trafic considrable. et AODV.

CBRP

Hybride

ARA

On-Demand

Tableau 2.2 : Les protocoles de routage pour les rseaux ad hoc.

2.5. ConclusionNous avons prsent dans ce chapitre une classification des protocoles de routage pour les rseaux ad hoc. Ces protocoles peuvent se classer en trois grandes catgories. Les protocoles Tables-Driven qui rduisent le dlai de livraison de paquets mais utilisent beaucoup de paquets de contrle, les protocoles On-Demend qui rduisent l'utilisation des paquets de contrle mais qui ont un dlai de livraison des paquets lev, et les protocoles Hybrides qui essayent de combiner les deux approches prcdentes pour avoir de meilleurs

37

performances. Le problme est donc de trouv un compromis entre le dlai de livraison des paquets de donnes et l'utilisation des paquets de contrle. Dans le chapitre suivant nous allons prsenter la technologie agent ainsi que quelques protocoles de routage bas sur cette technologie.

38

Chapitre 3 Le routage base d'agents dans les rseaux Ad Hoc3.1. IntroductionL'agent et les systmes multiagent sont une nouvelle technologie issue du domaine de l'intelligence artificielle, cette technologie est applique dans beaucoup de domaine tel que les systmes distribus, les interfaces homme machine et les rseaux. Cette technologie est particulirement intrssante utiliser dans des environnements de nature distribu et dynamique comme les rseaux ad hoc. Dans ce chapitre nous allons prsenter la technologie des agents et des systmes multiagent ainsi que quelques protocoles de routage pour les rseaux ad hoc bass sur les agents.

3.2. L'agent et les systmes multiagentsPour Jennings et Wooldridge [11],[18] un agent est une entit informatique situe dans un environnement, qui est capable dagir de manire autonome et flexible de faon remplir ses objectifs, cest dire ceux qui lui ont t assigns lors de sa conception. Laspect situ signifie que lagent peroit son environnement et quil est capable de le modifier.

Lautonomie, signifie que lagent est capable dagir sans lintervention directe dtres humains ou dautres agents et quil est capable de contrler ses propres actions et son tat interne. La flexibilit caractrise un agent intelligent. tre flexible signifie que lagent est capable :

39

de percevoir son environnement et rpondre en temps voulu aux changements qui sy produisent (ractivit); davoir un comportement dirig par son but, dtre opportuniste et capable dinitiative quand cest appropri (proactivit); et dinteragir, quand cest appropri, avec dautres agents artificiels ou humains de manire complter leur rsolution de problme et daider les autres par leurs activits (sociabilit). Un Systme multiagent (SMA) est une application o les agents travaillent ensemble pour rsoudre un problme commun, les possibilits de chaque agent prises sparment ne permet pas de le rsoudre. Chaque agent possde donc des connaissances et savoir-faire limits, ce qui loblige interagir avec dautres pour mener bien le projet commun. Les SMA mettent en oeuvre des interactions complexes, comme la coopration, la coordination et la ngociation [12]:

Il y a coopration lorsque les agents travaillent ensemble vers un but commun. La coordination consiste organiser les activits lies la rsolution dun problme de manire viter les interactions nfastes et exploiter les interactions bnfiques. La ngociation a pour objectif la gestion des conflits entre agents, cest dire quelle consiste aboutir un accord acceptable par lensemble des agents impliqus.

3.2.1 Les SMA et le routage dans les rseaux ad hocLe systme de gestion de routage dans les rseaux ad hoc ncessite une distribution des oprations, car il n'existe aucun lment central fixe qui peut organis le rseau, il ncessite la coopration entre les diffrents noeuds mobiles car un noeud mobile ne peut communiquer qu'avec les noeuds proches de lui , il a donc besoin de cooprer avec les autres noeuds mobiles qui vont l'aider transmettre les informations. Le systme de gestion de routage dans les rseaux ad hoc doit aussi tre robuste, il doit pouvoir continuer a fonctinner normalement en cas de dfaillance d'un ou plusieurs noeuds, il doit tre intelligent, il doit choisir les meilleures routes pour transmettre les paquets et ragir rapidement au vnements qui peuvent intervenir. Les systmes multiagent prennent en compte les aspects de coopration, d'autonomie, de distribution et d'intelligence ils nous semblent donc appropris pour grer le routage dans les rseaux ad hoc.

3.3. L'agent mobile40

Un agent mobile est un agent possdant la capacit de se dplacer entre les machines du rseau. Un agent mobile qui s'excute sur une machine du rseau peut suspendre sont excution sur cette machine , se transfrer une autre machine du rseau et continuer son excution. A un instant donnes un agent mobile est constitu de son code, de son contexte d'excution et de ses donnes. Les agents mobiles hritent de deux technologies, la technologie des agents, et la technologie du code mobile qui consiste dfinir un code tel que le programme compil dans ce code puissent tre porter et excuter sur n'importe quelle machine.

3.3.1. L'environnement d'excution d'agents mobilesUn environnement d'excution d'agents mobiles fournit des primitives pour crer, lancer et excuter un agent mobile [25]. Cet environnement est constitu d'un ensemble de programmes statiques qui s'excutent sur les sites du systme susceptibles d'accueillir des agents. Les environnements d'excution d'agents mobiles offrent plusieurs services de base permettant l'excution d'un agent mobile sur un site, tel que :

La cration d'un agent mobile : Un agent mobile peut tre cr localement sur la machine locale ou sur une machine distante. A sa cration, un nom globalement unique doit tre attribu l'agent ce qui va permettre de localiser l'agent et de communiquer avec lui.

La migration d'un agent mobile : La migration permet le transfert d'un agent en cours d'excution d'un site un autre travers le rseau. Il existe deux types de migration, la migration forte permet un agent de se dplacer quelque soit l'tat d'excution dans lequel il se trouve, dans ce type de migration l'agent se dplace avec son code, son contexte d'excution et ses donnes, dans ce cas, l'agent reprend son excution aprs la migration exactement l o elle tait avant son dplacement. Et la migration faible qui ne fait que transfrer avec l'agent son code et ses donnes, sur le site de destination, l'agent redmarre son excution depuis le dbut en appelant la mthode qui reprsente le point d'entre de l'excution de l'agent, et le contexte d'excution de l'agent est rinitialise.

L'accs aux ressources locales : L'agent mobile doit pouvoir accder aux ressources de la 41

machine ou il se trouve. cela pose le problme du piratage des sites visits par les agents mobiles.

La communication entre les agents mobiles : Un agent mobile doit pouvoir communiquer avec dautres agents rsidents dans la mme machine ou avec des agents rsidents dans dautres machine distante.

3.3.2. Avantages des agents mobilesDans [10] on donne un ensembles de raisons qui justifient le choix dutiliser les agents mobiles :

Rduire la charge du rseau : les agents mobiles sont envoys sur la machine o rsident les donnes. Ainsi, c'est le calcul qui va aux donnes et non les donnes au calcul. Cela va permettre de rduire significativement, voir supprimer, les communications distantes et se contenter des interactions locales, ce qui rduit la charge du rseau. Surmonter le temps de latence sur le rseau : Les agents mobiles sont envoys dans la zone d'activit, afin d'entreprendre des actions sur place. Cela leur permet de rpondre immdiatement des changements dans leur environnement et de surmonter le temps de latence du rseau. Sexcuter de manire asynchrone et autonome : Les agents mobiles sexcutent indpendamment de leur plate-forme d'origine, cest dire un agent peut continuer parcourir le rseau mme sans interaction avec l'utilisateur qui la envoyer, cela permet a l'utilisateur qui a envoy l'agent de dconnecter sa machine et prserv les ressources pendant le travail de lagent. Cette caractristique rend les agents mobiles trs intressants pour les rseaux ad hoc, ou la connexion entre les machines du rseau est trs fragile et les ressource en bande passante et nergie sont limites. Sadapter dynamiquement aux environnements dexcution : Les agents mobiles ont la capacit de percevoir et de s'adapter dynamiquement a leur environnement. Htrognes : la multiplicit des systmes augmente lincompatibilit des langages de commandes et des formats de donnes. Les agents mobiles peuvent rsoudre ce problme sous contrainte que les primitives du langage de lagent soit excutable sur tout systme. 42

Robustes et tolrants : Un agent mobile peut se dplacer pour viter une erreur matrielle ou logicielle, ou tout simplement un arrt de la machine. Contrairement a un programme classique qui est li une machine.

3.3.3. Les agents mobiles et le routage dans les rseaux Ad hocLes protocoles de routage Table-Driven exigent de connatre la topologie du rseau entier. Pour que les noeuds restent au courant des changements dans la topologie des informations de mis jour doivent tre frquemment propager dans tout le rseau. Les protocoles Table-Driven utilisent donc en permanence une grande partie de la capacit du rseau pour garder les informations de routage jour ce qui les rend inadapts pour les rseaux ad hoc. Dans l'autre cot les protocole de routage On-demand utilisent une procdure de dcouverte de route qui gnre un grand volume de trafic et produit la congestion du rseau et provoque la perte de paquets, ce qui les rend aussi ces protocoles inadapts pour les rseaux ad hoc. Les agents mobiles sont une solution pour dcouvrir la topologie du rseau et mettre en oeuvre un protocole de routage sans gnrer trop de trafic dans le rseau [1]. les agents mobiles se dplacent dans le rseau et recueillent les informations ncessaires pour le routage, arrivent un noeud il vont mettre jour sa table de routage par les dernires informations recueillies. Un noeud dans le rseau reoit des agents des informations sur la topologie du rseau ce qui lui permet de calculer des routes correctes pour communiquer avec les autres noeuds.

3.4. Travaux relativesL'ide d'utiliser les agents pour le routage dans les rseau ad hoc a t explorer rcemment dans quelques travaux. Nous allons prsenter dans la suite de ce chapitre quelques protocoles de routage ad hoc bas sur les agents.

3.4.1 Le protocole MARPMARP (Multi-Agent Routing Protocol) [1] est un protocole de routage pour les rseaux ad hoc bas sur les agents. Les routes dans MARP sont dcouvertes l'avance en utilisant des agents mobiles. Les agent mobiles explorent le rseau et recueillent les informations de topologie. Les noeuds dans le rseau reoivent les informations de topologie des agents et peuvent calculer les routes ver les diffrentes destinations. 43

Dans son article l'auteur dfinit quelques notions qui serons utilises dans le protocole :

L'affinit : L'affinit Anm d'un lien entre un noeud n et un noeud m dans le rseau est la dure de vie prvue de ce lien. Pour calculer le Anm le noeud n envoie priodiquement un signale au noeud m, le noeud m va calculer priodiquement la force de ce signal et peut dterminer la distance qui le spare du noeud m. Il peut aussi savoir s' il s'loigne ou se rapproche de lui et faire des prvisions sur la dure de vie du lien. La stabilit : La stabilit d'une route R entre un noeud source et un noeud destination un instant donn est dfinit comme l'affinit la plus basse des liens entre le noeud de cette route. La Recency: La topologie des rseaux ad hoc change rapidement , les informations concernant la topologie deviennent rapidement incorrectes. Ceci signifie que n'importe quelle information qu'un noeud A reoit concernant un autre noeud B est seulement partiellement correcte puisque il y a une diffrence de topologie entre l'instant ou les informations concernant le noeud B on t recueillis , et l'instant ou ces informations ont t livres au noeud A. Si un noeud reoit des agents des informations diffrentes concernant un autre noeud dans le rseau, il doit garder celles qui soient plus correctes; qui sont les informations les plus rcentes. Pour pouvoir dterminer degr d'exactitude d'une information ( La recency), chaque noeud dans le rseau maintient un compteur de rcency qui est initialis 0. Quand un agent arrive un noeud il incrmente son compteur et enregistre sa nouvelle valeur avec les informations recueillis partir du noeud. La valeur de rcency d'un noeud reprsente le nombre de fois que le noeud a t visit par des agents. Si deux agents ont des information diffrentes au sujet du mme noeud alors, l'agent portant la plus grande valeur de receny a des informations plus rcentes. Le Temps de Migration des agents : On ne permet pas un agent visitant un noeud d'migrer immdiatement un autre noeud. Un agent sera forc de rester dans un noeud pendant une priode prspcifie appele Time-to-Migrate (TtM), avant de pouvoir migrer. Le temps de migration TtM permet de contrler la congestion du rseau due au trafic des agents. Par exemple, si TtM = 100 millisecondes, ca veut dire que la mdium sans fil transmettra l'agent toutes les 100 millisecondes, Si on suppose qu'un agent prendrait

44

approximativement 3 millisecondes. pour migrer physiquement d'un noeud l'autre, alors le mdium sans fil serait libre du trafic d'agent 97 pour cent du temps. La rduction du trafic d'agent (en augmentant TtM) rduit la frquence laquelle les agents peuvent visiter les noeuds du rseau. Ceci peut s'avrer peu convenable si le rseau est fortement mobile et la topologie change rapidement car les informations de topologie deviennent rapidement incorrectes. Le compromis est ainsi entre la congestion et la prcision des informations. Un agent comprend les trois composants suivants :

L'identifiant de l'agent. Le programme de l'agent. La mmoire de l'agent.

La mmoire de l'agent contient un ensemble de variables d'tat du rseau telle que l'affinit et la recency, elle contient aussi des informations concernant l'tat des liens entre les noeuds. La taille de la mmoire est un paramtre important qui affecte le performances du protocole, une taille de mmoire plus grande permet aux agents de fournir plus d'informations aux noeuds, mais en mme temps elle augmente les frais de migration des agents. Le nombre d'agents utilis est aussi un paramtre important , plus il y a d'agents pour le routage plus les frais augmentent. La taille de la mmoire et le nombre d'agents doivent tre choisis afin d'avoir un quilibre entre les frais et l'efficacit du routage. Quand un agent arrive un noeud N il excute les tapes suivantes : 1. Il enregistre dans le noeud les dernires informations recueillis qui se trouvent dans sa mmoire. 2. l'agent dtermine tous les noeuds qui sont des voisins de N. 3. Il dtermine en suite le noeud voisin qui a la plus petite valeur de rcency, c'est le noeud qui a t le moins rendu visite comme peru par le noeud N. La rcency d'un noeud est le nombre de visites d'agents que le noeud a reu. 4. Si ce voisin de N n'a pas t visit dans les 3 visites prcdentes par d'autres agents partir du noeud N, l'agent choisit ce voisin comme prochaine destination, Si non l'agent choisit le deuxime voisin le moins visit. Ceci assurera que les agents arrivant un mme noeud ne choisissent pas la mme destination conscutivement. 5. Aprs le choix de la bonne destination l'agent Incrments la valeur du recency du noeud N et l'enregistre dans sa mmoire, il enregistre aussi les informations d'tats des liens du

45

noeud. L'agent migre ensuite vers sa prochaine destination. L'information qu'un noeud a obtenu d'un agent devient de plus en plus imprcise avec le temps, ceci est due la mobilit des noeuds, cependant le noeud obtient chaque fois des agents une mise jour de ces informations. Chaque noeud a donc une vue plus ou moins prcise sur l'affinit des liens dans le rseau. MARP rduit les valeurs d'affinit de chaque lien avec le temps. ceci suppose que l'affinit des liens est toujours en diminution. Aprs certain temps, si un noeud constate qu'une route utilise a atteint une basse stabilit (indiquant qu'une erreur d'itinraire est imminente), le noeud calcul une nouvelle route plus stable en utilisant les informations de topologie reu des agents et l'utilise la place de la premire. En rduisant l'affinit un noeud fait en quelque sorte des prvisions pessimistes sur l'affinit des liens, ce qui permet d'viter les coupures de routes et d'avoir des communications continuent entres les noeuds. Il est probable qu'un lien du rseau existe en ralit, mais que le noeud l'a supprim, mais il est peu probable, qu'un noeud considre qu'un lien existe alors qu'il n'existe pas en ralit. Les agents mobiles dans MARP sont utiliss pour recueillir et diffuser les informations de routage dans le rseau, un agent mobile se dplace seulement un noeud la fois au lieu d'inonder le rseau avec les paquets de mise jour. Le nombre d'agents peut aussi tre utiliser pour contrler le trafic dans le rseau. L'tablissement des routes dans MARP est dpendant des agents qui visitent les noeuds et fournissent les informations, si un noeud veut envoyer des paquets de donnes une destination pour la quelle il n'a pas de routes assez rcentes, il doit enregistrer les paquets dans son buffer et attendre jusqu' ce qu'un agent lui fournissent les routes ncessaires, ce qui augmente le dlai initial, en plus dans certains cas un noeud transportant des agents se dconnecte du rseau ce qui diminue le nombre d'agents participant au routage ce qui a son tour diminue les performances.

3.4.2 Un modle gnrique a base d'agentsDans [2] un modle gnrique a base d'agent pour effectuer le routage des donnes dans les rseaux ad hoc a t propos. Dans ce modle on utilise des agents mobiles et des agents statiques pour dterminer les routes entres les diffrents noeuds. Chaque noeud dans le rseau

46

contient un agent statique qui est charg de la gestion des ressources locales tel que l'nergie et capacit mmoire. Les agents mobiles explorent le rseau et fournissent les informations de routage au agents statiques, les agents statiques vont utiliser ces informations pour calculer la meilleure route pour transmettre les paquets. Figure 3.1 : Le modle d'agents pour le routage.

Chaque noeud dans le modle excute un agent serveur qui fournit les fonctionnalits ncessaires aux agents statiques et aux agents mobiles tel que la migration et la communication. Chaque noeud contient un agent statique. La tache de l'agent statique est de maintenir la table de routage, de dcider quelles routes utilises pour le routage et de grer les ressources locales. De l'autre cot les agents mobiles sont responsables de la collecte des informations a partir des agents statiques, de mettre jour les tables de routage et de dcouvrir de nouvelles routes. Ils informent aussi les agents statiques et les autres agents mobiles des changements dans le rseau.

3.4.3 Protocole MWACDans [9] on propose un protocole de routage base d'agent pour les rseaux mobiles ad hoc, appel MWAC ( Multi-Wireless-Agent Communication ) dans ce protocole on associe chaque noeud un agent. Les agents vont s'organiser d'une manire dynamique en groupes ayant une structure hirarchique afin de localiser au mieux linondation et ainsi

47

obtenir un gain en ressources. L'organisation des agents va merg de leurs interactions et de lvolution de leurs tats. Un groupe dans ce protocole contient :

Un agent reprsentant qui va grer les communications au sein de son groupe, Un ou plusieurs agents de liaison : ils appartiennent plusieurs groupes et permettent aux diffrents reprsentants de communiquer entre eux, Aucun ou plusieurs simples membres qui nont aucun rle particulier dans le groupe si ce nest recevoir et traiter les paquets qui leurs sont destins et transmettre leurs propres paquets.

La figure suivante est un exemple de l'organisation des agents en groupes, un agent est soit un reprsentant (R), soit un agent liaison (L), soit un simple membre (S).

Figure 3.2. : Organisation des agents dans MWAC Un agent reprsentant devra traiter toutes les requtes denvois de paquets des membres de son groupe, quand le destinataire dun paquet nest pas voisin de lmetteur, cest lui que revient le rle de trouver une route et de vrifier le bon acheminement du paquet. Cest aussi lui qui est inond par les requtes de recherche de route des autres reprsentants. Il est donc plus sollicit que les autres agents de son groupe. Un agent de liaison est charg dassurer la communication entre les groupes cest--dire ses voisins qui sont reprsentants. Ce sont eux qui distribuent les requtes de recherche de route aux reprsentants. Les agents simples 48

membres nont aucun rle particulier dans la gestion des paquets. Les donnes que doivent contenir les agents sont variables. Elles dpendent du statut de lagent dans le groupe :

Donnes sur soi : Tout agent connat son identifiant et son statut dans le groupe reprsentant (R), agent liaison (L) ou simple membre (S). - Donnes sur les autres : Les donnes qu'un agent possde sur les autres dpendent du rle de lagent. Chaque agent possde une table de voisins. Cette table contient pour chaque voisin un triplet auquel il appartient. Si lagent est un reprsentant il aura en plus une liste des groupes adjacents qui lui permet de connatre lidentifiant des groupes et donc de leur reprsentant voisin. Si lagent est un simple membre (agent SM) alors il ne contient que la table des voisins dfinie prcdemment. Si lagent est un agent de liaison il ne possde, tout comme lagent simple membre, quune seule table, celle des voisins. Il sait qui sont les groupes voisins grce lidentifiant des reprsentants quil peroit. Au dbut un agent va envoyer le message QuiSontMesVoisins pour connatre ses voisins et leur demander de se prsenter. ses voisins rpondent avec le message JeSuisUnDeTesVoisins prcisant le triplet qui leur est associ. L'agent dtermine, en fonction de son voisinage, le rle quil doit prendre. Il le signalera ses voisins via le message JeChangeDeRle. Le protocole d'interaction entre un agent et ses voisin pour dtermin son rle est illustr dans la figure suivante.

49

Figure 3.4 : Interaction entre un agent et ses voisin pour dterminer son rle. Chaque agent calcul une fonction score qui va permettre d'lire les reprsentants dterminer le rle de chaque agent. La fonction sore est calcule en multipliant le nombre de voisins par le niveau dnergie de lagent. L'algorithme suivant est ensuite utilis : SI monNombreDeVoisin= 0 ALORS// On a des voisins

SI nbRepresentantsVoisin = 0 ALORS// Aucun de nos voisins nest reprsentant : on dcide de le devenir. Ce cas intervient quand on vient // juste de crer lagent ou quand il vient de se dplacer.

monRle = ; SINON SI nbRepresentantsVoisin = 1 ET monRle=REPRESNTANT ALORSR PR ES N N E TA T

// Un de nos voisins est reprsentant : on se soumet son autorit et ce mme sil est moins efficace // que nous : on privilgie (pour le moment) la stabilit dans lorganisation sa performance.

MonRle = SINON

SI M PLEM EM BR E

;

//Il existe, dans notre voisinage, plusieurs reprsentants.

SI monRle = R ALORSEP R N AN ES T T

// Je suis moi-mme reprsentant : jentre en conflit avec les autres prtendants ce rle. Une // lection va avoir lieu et lagent au meilleur score restera en place

ProcedureElectionRepresentant() SIN// On nest pas reprsentant : on devient agent de liaison pour ces reprsentants

50

monRle = FINSI FINSI SINON

LI ASO N

// On na pas de voisin : on na plus aucun rle

monRle = FINSI Dans l'algorithme prcdant une procdure d'lection du reprsentant est lance quand au moins deux agents voisins sont reprsentants. Le protocole d'lection du reprsentant estAU C N

illustr dans la figure suivante :

Figure 3.5 : Protocole dlection du meilleur reprsentant. Le message ResolutionConflitRepresntant est un message utilis par un reprsentant en conflit avec un ou plusieurs autres reprsentants pour communiquer son score, Le message 51

JeChangeDeRole est utilis par l'agent qui a chang de rle pour en avertir ses voisins. Ce message contient comme information lidentifiant de lagent, son rle et son groupe. Dans ce protocole on diffuse les requtes de recherche de route aux agents reprsentants, ce qui permet de mieux localis linondation et ainsi de rduire le trafic engendr par l'inondation. Mai la formation et la maintenance de la structure des groupes engendrent un trafic supplmentaire dans le rseau. Aussi les agents reprsentants sont responsables de la transmission des paquets de donnes il sont donc plus sollicit que les autres agents.

3.5. ConclusionDans ce chapitre on a prsent la technologie des agents et des systmes multiagents. Nous avons vu que l'agent intgre des aspects qui sont ncessaires pour grer les rseaux ad hoc comme la coopration l'autonomie et l'intelligence. Nous avons aussi prsent la technologie des agents mobiles, nous avons vu que les agents mobiles sont une alternative pour dcouvrir la topologie du rseau et viter d'utiliser l'inondation. Nous avons aussi prsent quelques protocoles de routage a base d'agents. Dans le chapitre suivant nous allons propos un protocole de routage pour les rseaux mobiles ad hoc bas sur les agents.

52

Chapitre 3 Le routage base d'agents dans les rseaux Ad Hoc3.1. IntroductionL'agent et les systmes multiagent sont une nouvelle technologie issue du domaine de l'intelligence artificielle, cette technologie est applique dans beaucoup de domaine tel que les systmes distribus, les interfaces homme machine et les rseaux. Cette technologie est particulirement intrssante utiliser dans des environnements de nature distribu et dynamique comme les rseaux ad hoc. Dans ce chapitre nous allons prsenter la technologie 53

des agents et des systmes multiagent ainsi que quelques protocoles de routage pour les rseaux ad hoc bass sur les agents.

3.2. L'agent et les systmes multiagentsPour Jennings et Wooldridge [11],[18] un agent est une entit informatique situe dans un environnement, qui est capable dagir de manire autonome et flexible de faon remplir ses objectifs, cest dire ceux qui lui ont t assigns lors de sa conception. Laspect situ signifie que lagent peroit son environnement et quil est capable de le modifier.

Lautonomie, signifie que lagent est capable dagir sans lintervention directe dtres humains ou dautres agents et quil est capable de contrler ses propres actions et son tat interne. La flexibilit caractrise un agent intelligent. tre flexible signifie que lagent est capable : de percevoir son environnement et rpondre en temps voulu aux changements qui sy produisent (ractivit); davoir un comportement dirig par son but, dtre opportuniste et capable dinitiative quand cest appropri (proactivit); et dinteragir, quand cest appropri, avec dautres agents artificiels ou humains de manire complter leur rsolution de problme et daider les autres par leurs activits (sociabilit).

Un Systme mu