Upload
pearl-jensen
View
28
Download
1
Embed Size (px)
DESCRIPTION
Graphes dynamiques et environnement mobile Hamamache Kheddouci Laboratoire PRISMa Université Claude Bernard Lyon 1. PLAN. Définitions Graphes dynamiques Applications Conclusion. PLAN. Définitions Graphes dynamiques Applications Conclusion. arêtes. sommets. Graphe ?. - PowerPoint PPT Presentation
Citation preview
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- …
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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- …
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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)
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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- ….
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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}
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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-
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
15
Exemple de réseau ad hoc :
Isolé
Graphes dynamiques & réseaux mobiles ad hoc
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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é !
Graphes dynamiques & réseaux mobiles ad hoc
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
18
Pair (Client/Serveur)
Protocole donné
Couche MACCouche Liaison
Couche Physique
Pair (Client/Serveur)
Protocole donné
Topologie dynamique
Couche MACCouche Liaison
Couche Physique
Topologie virtuelle dans les réseaux mobiles ad hoc
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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
Topologie virtuelle dans les réseaux mobiles ad hoc
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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
Topologie virtuelle dans les réseaux mobiles ad hoc
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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
- Graphe dynamique & réseaux ad hoc- Algorithme dynamique & réseau à pannes-
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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
Algorithmes dynamiques et systèmes à pannes
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
26
Le message m ne peut pas atteindre sa destination u !!
x
y
z
tu
Situation bloquante …
Algorithmes dynamiques et systèmes à pannes
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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
Algorithmes dynamiques et systèmes à pannes
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
28
x
y
zt
u
Algorithmes dynamiques et systèmes à pannes
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
29
x
y
zt
u
Limitation de cette idée …!
Le message m n’atteindra jamais sa destination u !!
boucle
Algorithmes dynamiques et systèmes à pannes
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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 …
Algorithmes dynamiques et systèmes à pannes
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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
Algorithmes dynamiques et systèmes à pannes
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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
Algorithmes dynamiques et systèmes à pannes
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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)
Algorithmes dynamiques et systèmes à pannes
PLANPLAN
Définitions
Graphes dynamiques
Applications
Conclusion
- Graphe dynamique & réseaux ad hoc- Algorithme dynamique & réseau à pannes-
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
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
H. Kheddouci Graphes dyn. et env. mobile - ANR Forum - Montpellier 23/03/06
36
Merci