1

Une architecture de contrôle de mobilité pour le routage de messages

dans un réseau ad hoc de grande taille

Pirro BRACKA

Directeurs:Jacques DÉSARMÉNIEN

Llukan PUKA

Encadré par:Gilles ROUSSEL

2

Plan

• Introduction du problème

• Présentation de l’approche

• Modélisation et propriétés

• Améliorations de la solution

• Simulations et implantations

• Routage et mobilité

• Conclusions et perspectives

3

Introduction

• Réseaux ad hoc– Ensemble de nœuds mobiles organisés en réseau

sans l'aide d'infrastructure fixe

– Communication pair-à-pair

– Offre de services dépendants du lieu

• Réseaux ad hoc de grande taille– Très grand nombre de nœuds

– Topologie très étendue géographiquement

4

Introduction

• Problèmes dans les réseaux ad hoc– Chemins longs entre source et destination de

message• Chemins vulnérables aux ruptures de liens• Information obsolète à l'arrivée

– Connectivité• Variable à cause de l'étendue du réseau et de la

mobilité des nœuds

– Surcoût des protocoles de routage• Bande passante, énergie et calcul de chemins

5

Introduction

• Résoudre ces problèmes:– Augmenter la zone de transmission radio (difficile

voire impossible dans certains cas)

– Utiliser la mobilité

6

Routage et mobilité

• Protocoles de routage

• Modèles de mobilité pour l'évaluation des protocoles

• La plupart des travaux sur le routage n'utilisent pas la mobilité des nœuds

• Routage et mobilité très liés

• Comment contrôler efficacement la mobilité et la mettre au service du routage?

7

Routage et mobilité

Les algos de contrôle de mobilité doivent aborder les problématiques suivantes (Goldenberg et al.)

– Nature du contrôle dépendante des applications

– Pas d'entité centrale calculant les mouvements des nœuds

– Schéma distribué capable d'optimiser les performances en satisfaisant d’autres contraintes

8

Notre solution

• Mettre en place un mécanisme de rendez-vous pour assurer une communication fiable

• Mécanisme utilisé pour communiquer

9

Environnement

• Réseaux de grande taille avec topologie divisée en zones

• Zones = polygones du diagramme de Voronoï

• Dans chaque zone un seul nœud

• Communication seulement avec les nœuds des zones adjacentes

10

Exemple

11

Modélisation

• Points de rendez-vous entre zones

• Déplacement entre les points de rendez-vous

• Communication asynchrone dans les points de rendez-vous

• Graphe non-orienté des points de rendez-vous

– sommets = nœuds

– arêtes = points de rendez-vous

12

Contrainte

Le premier nœud qui arrive sur un point de rendez-vous, attend son voisin avant de continuer son déplacement

13

Exemple

14

Ordonnancement

• Ordonnancer les mouvements

– numéroter aléatoirement des points de rendez-vous

– initialiser les nœuds à leur point de rendez-vous minimum

– parcourir les points rendez-vous dans l'ordre croissant

– attendre le voisin et communiquer avant de quitter le point de rendez-vous

• Un premier algorithme d'ordonnancement des mouvements

15

Modélisation

16

Modélisation• Associer à chaque nœud un automate fini

– état = point de rendez-vous

– transition = déplacement entre 2 points rdv

– état initial = point rdv avec le plus petit numéro

17

Propriétés

• Prouver l'absence de blocage

– non-blocage global

– non-blocage local

– transmission en temps borné des messages

• Preuve des propriétés:

– par la construction de l'automate produit

18

Propriétés

L'automate produit possède 24 x 32 x 4 = 576 états mais seulement 9 états sont accessibles

19

Propriétés

Autre numérotation

39 états

20

Routage

Source Dest. Rdv. Longueur du chemin

a.1 b a.1 1

a.1 e a.1 5

... ... ... ...

a.9 b a.1 2

a.9 e a.9 4

... ... ... ...

21

Améliorations• Augmenter le degré du parallélisme

– rencontres et déplacements en parallèle de plusieurs couples de nœuds

• Réduction de la consommation d'énergie

– amélioration de la numérotation pour réduire les déplacements

• Tolérance aux défaillances

– gestion des pannes

– gestion du rétablissement d'un nœud après une panne

22

Améliorations

• Réduction de consommation de l'énergie

• Parallélisme- Coloration des arêtes du graphe des points de rendez-vous selon l'algorithme de Vizing

23

Améliorations

• Tolérance aux défaillances

– état stable permet de prévoir :

• premier nœud à atteindre un point de rendez-vous

• temps d’attente avant l’arrivée de son voisin

– conception d'un nouvel algorithme tolérant aux pannes

• Que faire lorsqu'un nœud tombe en panne?

• Comment se rétablir après une panne?

24

Améliorations• Que faire lorsqu'un nœud tombe en panne?

– Routage dynamique

– Utilisation d'un protocole à état de liens

– Un seul message annonce la panne de tous les liens du noeud

• Comment se rétablir après une panne?

– Se diriger vers le point de rdv le plus proche

– Annoncer le rétablissement par un message

– Apprendre dans quel état se trouve son voisin

– Déduire le temps d'attente avant de commencer à exécuter l'algo. d'ordonnancement

25

Simulations

Validation de la solution par simulation

– conception d'une plate-forme de simulation

– 2 paquetages Java

– environnement 2500m x 2500m

– vitesse de noeuds constante à 5m/s

– comparaison de l'algo. des points de rdv avec une diffusion

26

Longueur des chemins

Chemins plus courts pour l'algorithme des points de rendez-vous

27

Les déplacements des noeuds

Le nombre de déplacements pour aller dans un point de rdv et prendre un message

Le nombre de déplacements pour aller dans le point de rdv approprié et transmettre un message

28

Le délai de bout en bout

Le délai par rapport au nombre de nœuds Le délai par rapport à la vitesse des nœuds

29

L'efficacité

Efficacité = 1 – temps perdu en attente

délai de bout en bout

30

Anomalie

Le nombre moyen de points de rendez-vous par nœud

31

Implantation

Validation de la solution par implantation

– Robots Lego Mindstorm

– leJOS, une JVM pour les programmer• Prog. Orientée Objet

• Threads préemptives

• Tableaux multidimensionnels

• Récursivité

• Synchronisation

• Opération sur les flottants

• Classe java.lang.Math

32

Robots

33

Conclusion• Une solution basée sur le contrôle de la mobilité

– Algorithme tolérant aux pannes

– Mécanisme de rendez-vous

– Schéma des mouvements distribué– Communication en temps borné avec contraintes

• Développement d'une plate-forme de simulation– Tests faits pour valider notre solution

• Implantation dans des robots– Preuve de la faisabilité de la solution

34

Perspectives

• Problème de transmission multicast

• Évaluation comparative des protocoles de routage ad hoc en utilisant le mécanisme des rendez-vous

• Modélisation à base de files d'attente

• Applications dans les VANET (Vehicular Ad hoc NETworks)

35

36

Algorithme d'un noeud nk

initialiser nk dans son point de rendez-vous avec le plus petit numéro

For chaque point de rendez-vous de nk dans l'ordre et en boucle do

If (un noeud est en attente dans ce point de rendez-vous)

echanger des messages s'il y en a;

notify(); // déclenche le mouvement vers le point de rendez-vous suivant

If (un message m est reçu)

If (la destination de m est nk)

traiter m;

else

conserver m pour le routage;

EndifEndif

continuer le mouvement vers le point de rendez-vous suivant;

Elsewait(); // reste en attente de l'autre noeud dans ce point de rendez-vous

Endif

EndFor

37

Algorithme d'un noeud nk

initialiser nk dans son point de rendez-vous avec le plus petit numéro

For chaque point de rendez-vous de nk dans l'ordre et en boucle do

If (un nœud est en attente dans ce point de rendez-vous)

échanger des messages s'il y en a;

notify(); // déclenche le mouvement vers le point de rendez-vous suivant

If (un message m est reçu)

If (la destination de m est nk)

traiter m;

else

conserver m pour le routage;

Endif

Endif

ajouter le reste du temps d'attente à la tâche suivante;

continuer le mouvement vers le point de rendez-vous suivant;

Else

while (temps d'attente de nk pas expiré) do

wait(); // reste en attente de l'autre nœud dans ce point de rendez-vous

endwhile

ajouter le reste du temps d'attente à la tâche suivante;

continuer le mouvement vers le point de rendez-vous suivant;

Endif

EndFor