Graphes dynamiques et environnement mobile Hamamache Kheddouci Laboratoire PRISMa Université Claude Bernard Lyon 1

Graphes dynamiques et environnement mobile

Hamamache Kheddouci

Laboratoire PRISMa Université Claude Bernard Lyon 1

PLANPLAN

Définitions

Graphes dynamiques

Applications Conclusion

Définitions

Graphes dynamiques

ApplicationsConclusion

PLANPLAN

H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06

4

Graphe ?Graphe non-orienté

défini par G=(X,E) : X ensemble de sommets ou nœuds E ensemble d’arêtes

sommetsarêtesExemple :

- Graphes de services,- une application distribuée,- une machine parallèle- …


5

Graphe ?Graphe orienté

défini par G=(X,E) : X ensemble de sommets ou de nœuds E ensemble d’arcs

Exemple :X2

X5

X3X4

X1- Graphes Web,- Réseaux de processus- graphes de tâches- …


6

Comment utiliser les graphes ?

Efficacité de la solution dépend du :- choix du modèle le plus adapté au problème - des outils disponibles - de la façon d’utiliser les outils pour la résolution

Problème modélisé

totalement ou

partiellement

UNE solution au problème à

base degraphes

Problème

Modélisation par des graphes

Outils pour la résolution

Résolution

Graphes statiques insuffisants… !

PLANPLAN

Définitions

Graphes dynamiques

ApplicationsConclusion


8

Graphe dynamique

Définition Gt=(Xt,Et) :

Xt ensemble de sommets à l’instant t Et ensemble d’arêtes (ou d’arcs) à l’instant t

Exemples :ab

cd

ef

a

b

c

d

ef

ac

d

ef

g

Gt Gt+1Gt+2

mvt a et c, + arête (a,c), -(a,b), -(b,c) Départ de b, arrivée de g,+ arêtes (g,e),(g,c)


9

Graphe dynamique

Propriétés classiques propriétés dans le temps plus court chemin dans le temps, connexité dans le temps,…

Nouvelles propriétés spécifiques : distribution de degrés, diamètre moyen,…

Nouvelle algorithmique : algorithme dynamique, online,…

- Gt+1= Gt {sommets, arêtes}- une suite de graphes G0, G1, …, Gn :

Transformation de graphes G0 ---> G1 ---->G2 --->, …, ---> Gn01 12 23 n-1,n

Définition :

Propriétés des graphes dynamiques


10

Graphe dynamique Définition

Gt=(Xt,Et) : Xt ensemble de sommets à l’instant t Et ensemble d’arêtes (ou d’arcs) à l’instant t

Changements topologiques : - changements d’états - pannes sommets/arêtes - mobilité : départ/arrivée sommets/arêtes

Exemples : systèmes dynamiques et/ou distribués- Systèmes reconfigurables - Systèmes à pannes- Réseaux de mobiles- Graphe Web- Réseaux de véhicules- ….


11

Graphe dynamique et algorithme dynamique

Algorithmique dynamique : Algorithme qui prend en compte les changements

topologiques ajout/suppression sommets/arêtes

Etude des propriétés de la structure dynamique : Propriété P vérifiée dans Gt, est-elle vraie dans Gt+1 ?avec Gt+1= Gt {sommets, arêtes}


12

Problème : Etant donné un algorithme A sur Gt,

Comment A fonctionnera sur Gt+1 sans recalculer entièrement la solution sur Gt+1 ?

Graphe dynamique et algorithme dynamique

PLANPLAN

Définitions

Graphes dynamiques

Applications

Conclusion

- Graphe dynamique & réseaux ad hoc- Algorithme dynamique & réseau à pannes-


14

Graphes dynamiques & réseaux mobiles ad hoc

Réseau ad hoc :

• Réseau de mobiles• Sans infrastructure fixe• administration distribuée• Mobiles sont des routeurs• Energie limitée

Réseau ad hoc = graphe dynamique Gt=(Xt,Et) avec• Xt ensemble des mobiles• Et ensemble de liaisons entre les mobiles


15

Exemple de réseau ad hoc :

Isolé



16

Problèmes intéressants en algorithmique dynamique et distribuée :

• Routage : d’une source à une destination

• Découverte de services : description, publication, découverte et localisation des services

• Prédiction de la mobilité de l’utilisateur : réserver les services à l’avance,…• … s’appuyer sur les propriétés du graphe dynamique associé !



17

Construire un sous-graphe (topologie) dynamique virtuel adapté à la problématique posée !

Physical Layer

Virtual Layer

Virtual BackboneTopologie dynamique virtuel = backbone

Topologie virtuelle dans les réseaux mobiles ad hoc


18

Pair (Client/Serveur)

Protocole donné

Couche MACCouche Liaison

Couche Physique

Pair (Client/Serveur)

Protocole donné

Topologie dynamique

Couche MACCouche Liaison

Couche Physique



19

Avantages des topologies virtuelles dynamiques :

Diminuer l’impact de la mobilité Optimiser la communication (diffusions, petit diamètre,

…) Passage à l’échelle Réduction des temps de réponses Possibilité d’appliquer des mécanismes d’équilibrage de

charges



20

Classification des topologies virtuelles dynamiques utilisées dans les réseaux ad hoc

k-Tree Core

MPR Sets

CDS

Topologies virtuelles

dynamiques

Ensembles de nœuds couvrants

Structures basées liens

DS / IS DAGs

Spanning trees

Rings

d-CDS

k-CDS

Clusters Cliques



21

Topologie virtuelle dynamique (backbone) choisie : Calculer un ensemble Maximal de Sommets Indépendants (MIS) - cet ensemble domine tous les autres nœuds du réseaux - distance entre toute paire de sommets est au plus 3 Connecter ce MIS avec un minimum d’arêtes Maintenir la topologie dans le temps en fonction de l’arrivée/départ sommet/arête

initial

État indépendant

État dominé

Topologie adaptée à la découverte de services

dans réseaux mobiles ad hocHaddad & Kheddouci 2005


22

Protocole de découverte de services sur le backbone : Services enregistrés au niveau des nœuds du backbone Recherche de services se fait que sur le backbone

Topologie adaptée à la découverte de services

dans réseaux mobiles ad hoc

PLANPLAN

DéfinitionsGraphes dynamiques

Applications

Conclusion



24

Etant donnés,

Un réseau en grille à 2 dimensions

Un routage à déflection

Pannes surgissent sur les liens en temps réel

(topologie dynamique Gt Gt+1)

A. Benhamdine, D. Barth, H. Kheddouci & H. Li 2001

dès qu’un message arrive à un nœud, il est «déflecté» vers un nœud voisin qui l’approche de sa destination finale

Question : un message partant d’une source arrive t-il à sa destination ?

Algorithmes dynamiques et systèmes à pannes


25

Routage à déflection Un nœud recevant un message, l’envoie sur un lien voisin libre e.

Les routeurs intermédiaires ne sont pas ‘store-and-forward’

Un nœud ne connaît que ses voisins du réseau (comportement local)

Grille à 2 dimensions processeursliens



26

Le message m ne peut pas atteindre sa destination u !!

x

y

z

tu

Situation bloquante …



27

- le message m contourne le trou- m quitte le trou par un nœud qui l’approche le plus de sa destination

x

y

z

tu

Solution naturelle … trou

panne



28

x

y

zt

u



29

x

y

zt

u

Limitation de cette idée …!

Le message m n’atteindra jamais sa destination u !!

boucle



30

- structure convexe- ne contient pas de petits cycles- le message m empreinte le périmètre de cette structure- m quitte cette structure par un nœud qui l’approche le plus de sa destination

x

y

z

tu

Solution …



31

SOLUTIONEtendre le trou à une structure convexe appelée enveloppe (covering)

Une enveloppe d’un trou est la plus petite sous-grille contenant ce trou

sachant que la bordure ne contient pas de liens en pannes



32

3 1

3

33

4

4 4

4 4 4 4 2

3

3

2 3 22

3

3

3 3

2

4 3

2

3 2

3

1

21 21 2

Ces nœuds sont sur la bordure et

l’algorithme s’arrête

32 32

Exemple



33

• Si la destination est sur l’enveloppe => trivial

• Sinon il existe un nœud U sur l’enveloppe à partir duquel le message m quitte l’enveloppe et s’approche plus de sa destination

Y=(y1,y2)

X=(x1,x2)

U=(u1,u2)


PLANPLAN

Définitions

Graphes dynamiques

Applications

Conclusion



35

Conclusion

• Modélisation des systèmes, contraintes, fonctionnements,… par des graphes (statiques et dynamiques).

• Offrir des infrastructures adaptées pour la communication, gestion des applications distribuées, ….

• les aspects algorithmiques distribués, auto-stabilisants, online,.. intéressants pour les systèmes dynamiques, reconfigurables, à pannes,…

• Optimisation des solutions d’allocation, d’ordonnancement, d’organisation, ... à l’aide des paramètres de graphes adaptés


36

Merci

Documents

Graphes dynamiques et environnement mobile Hamamache Kheddouci Laboratoire PRISMa Université Claude Bernard Lyon 1