Soutenance mémoire
Généralités sur les réseaux de Petri
Les réseaux de Petri sont définis comme étant un formalisme qui permet la description et l’analyse du comportement des systèmes concurrents, introduit par Carl Adem Petri en 1962. Carl Adam Petri est un mathématicien allemand qui a défini un outil mathématique très général permettant de décrire des relations existantes entre des conditions et des événements, de modéliser le comportement de systèmes dynamiques à événements discrets. C’est un outil de modélisation utilisé généralement en phase préliminaire de conception de système pour leur spécification fonctionnelle, modélisation et évaluation Les principaux utilisateurs de ces réseaux sont les informaticiens et les automaticiens. Cependant c’est un outil assez général pour modéliser des phénomènes très variés. Il permet notamment [3].:
– la modélisation des systèmes informatiques,
– l’évaluation des performances des systèmes discrets, des interfaces homme machine,
– la commande des ateliers de fabrication,
– la conception de systèmes temps réel
– la modélisation des protocoles de communication,
– la modélisation des chaines de production (de fabrication),
en fait, tout système dans lequel circule objets et information.
Les définitions concernant les réseaux de Petri portées sur deux aspects [4] :
▪ Un aspect structurel : Quelles sont les actions, quels sont les sites, quelles sont les conditions pour qu’une action soit possible et quelles sont les conséquences d’une action?
▪ Un aspect comportemental : Comment représenter le fonctionnement d’un réseau de Petri? c.-à-d. ce qui se passe quand une action ou plusieurs actions sont exécutées.
Représentation d’un réseau de Petri
Représentation graphique
L’un des aspects les plus agréables des réseaux de Petri est qu’il est extrêmement aisé de les visualiser ; c.-à-d., donner une interprétation graphique à sa structure qui peut être représentée à travers un graphe bipartie fait de deux types de sommets: les places et les transitions reliées alternativement par des arcs orientés qui portent des poids entier positifs, si un poids n’est pas porté alors il est égal à 1 (RdP ordinaire). Généralement, les places sont représentées par des cercles et les transitions par des rectangles, le marquage d’un RdP est représenté par la distribution de jetons dans l’ensemble de ses places telle que chaque place peut contenir un ou plusieurs jetons représentés par des points dans le cercle représentant la place.
Représentation matricielle
Une représentation matricielle d’un RdP est offerte afin de simplifier les tâches d’analyse et de vérification effectuée sur un modèle RdP. Agir sur une représentation graphique d’un modèle RdP est une Tâche délicate en comparant avec une représentation matricielle.
Il est possible de représenter la fonction W (fonction de poids) par des matrices. Soit un réseau de Petri , R = (P, T, W) Avec P = {p1, p2, …,pm} et T={t1, t2, …,tn}
On appelle matrice des pré conditions pré la matrice m × n à coefficients dans N tel que pré(i,j) = W(pi,tj), elle indique le nombre de marque que doit contenir la place pi pour que la transition tj devienne franchissable, de la même manière on définit la matrice des post conditions post la matrice n ×m tel que post(i,j)= W(tj, pi) contient le nombre de marques déposées dans pi lors du franchissement de la transition tj. La matrice C= post -pré est appelée matrice d’incidence du réseau (m représente le nombre de places d’un réseau de Petri et n le nombre de transitions.) La représentation Graphique d’un marquage dans un RdP marquée et présenté par des marques dans la place ces marques sont dites jetons. Le marquage d’un réseau de Petri est représenté par un vecteur de dimension m à coefficients dans N. La règle de franchissement d’un réseau de Petri est définie par
M’(p) = M(p) + C(p,t)
Représentation d’un RdP marqué [8] Un réseau de Petri marqué est le couple N =<R, M> où :
▪ R est un réseau de Petri
▪ M est une application de marquage
▪ M : P→ N
M(p) est le nombre de marques (jetons) contenus dans la place p. Le marquage d’un réseau de Petri est une opération qui consiste à assigner des jetons dans les places. On appelle marquage M d’un Réseau de Petri le vecteur du nombre de marques dans chaque place : la Ième composante correspond au nombre de marques dans la Ième place. Il indique à un instant donné l ́état du RdP.
L’aspect comportemental
Le comportement d’un réseau de Petri est déterminé par sa structure et par son état. Pour exprimer l’état d’un réseau de Petri, les places peuvent contenir des jetons qui ne sont que de simples marqueurs.
Franchissement d’une transition
Une règle de franchissement est une simple relation de transition qui définit le changement d’état dans un réseau marqué lors de l’exécution d’une action. Afin de définir une règle de franchissement, il est nécessaire de formaliser quand le réseau peut exécuter une action : on dit qu’une transition t peut être franchie à partir d’un marquage M (qui représente l’état du system à un instant donné) si et seulement si chaque place d’entrée p∈*t de la transition t contient au moins un nombre de jetons qui est supérieur ou égal au poids de l’arc reliant cette place d’entrée p avec la transition t .
L’exécution d’un réseau de Petri
Exécution séquentielle
Séquence de franchissement
[10] Une séquence de franchissement « s » est une suite de transitions (t1, t2, …, tn) qui permet, à partir d’un marquage « M », de passer au marquage « M’ » par le franchissement successif des transitions définissant la séquence.
Marquage accessible
Le marquage d’un Réseau de Petri à un instant donné est une vectrice colonne dont la valeur de la Ième composante est le nombre de marques dans la place Pi à cet instant. Le franchissement d’une transition conduit à un changement du marquage. Le passage du marquage Mk au marquage Ml par franchissement de la transition Tj est noté : Mk (Tj>Ml. Le nombre de marques dans la place Pi pour le marquage Mk est noté Mk (Pi). A partir d’un même marquage, il peut être possible de franchir plusieurs transitions, menant ainsi à des marquages différents. L’ensemble des marquages accessibles à partir du marquage M0 est l’ensemble des marquages obtenus à partir de M0 par franchissements successifs d’une ou plusieurs transition(s). Cet ensemble est noté A(R ; M0) .
Graphe de marquage
On peut représenter l’ensemble de marquage accessible par un graphe si ce dernier et fini. Le graphe de marquage a comme sommet l’ensemble de marquage accessible A(R,M0).Un arc orienté relie deux sommet Mi et Mj s’il existe une transition t franchissable permettant de passer d’un marquage à un autre Mi [t>Mj. Les arcs du graphe sont étiqueté par les transitions correspondantes.
|
Table des matières
INTRODUCTION GENERALE
CHAPITRE 1 LES RESEAUX DE PETRI
1.1 Introduction
1.2 Généralités sur les réseaux de Petri
1.3 L’aspect structurel
1.3.1 Définition d’un réseau de Petri
1.3.2 Représentation d’un réseau de Petri
1.3.2.1 Représentation graphique
1.3.2.2 Représentation matricielle
1.3.2.3 Représentation d’un RdP marqué
1.4 L’aspect comportemental
1.4.1 L’état dans un réseau de Petri
1.4.2 Franchissement d’une transition
1.4.3 L’exécution d’un réseau de Petri
1.4.3.1 Exécution séquentielle
1.4.3.2 Exécution concurrente
1.5 Réseaux particuliers
1.5.1 Graphe d’états
1.5.2 Les réseaux sans conflits
1.5.3 Les réseaux purs
1.6 Propriétés des RdP
1.6.1 Réseau K-borné
1.6.2 Réseau vivant
1.6.3 Réseau réinitialisable
1.7 Les invariants
1.7.1 Invariants de places
1.7.2 Invariants de transition
1.8 Les méthodes d’analyse des RdP
1.8.1 Méthode d’arbre de couverture
1.8.2 Approche d’équations matricielles
1.8.3 Technique de réduction et de décomposition
1.9 Qualités et faiblesses des réseaux de Petri
1.10 Extension des réseaux de Petri
1.10.1 Réseau de Petri temporisés
1.10.2 Réseau de Petri stochastiques
1.10.2.1 Réseau de Petri stochastiques généralisé
1.10.2.2 Réseau de Petri stochastiques et déterministes
1.10.2.3 Réseaux de Petri stochastiques étendus
1.10.3 Réseau de Petri colorés
1.10.4 Réseau de Petri continus et hybrides
1.10.5 Les réseaux de Petri hiérarchiques
1.10.6 Les réseaux de Petri à Objet
1.11 Conclusion
CHAPITRE 2 LA TECHNOLOGIE MPLS
2.1 Introduction
2.2 MPLS
2.2.1 Principe du MPLS
2.2.2 Labels
2.2.3 Commutation des labels
2.2.4 Distribution des labels
2.3 Description des routeurs MPLS
2.3.1 LSR
2.3.2 ELSR (LER)
2.3.3 LSP ,FEC, LDP
2.4 Agrégation
2.5 Les applications de la technologie MPLS
2.5.1 VPN/MPLS
2.5.2 Quality Of Service
2.5.3 Traffic Engineering
2.6 Conclusion
CHAPITRE 3 LES RESEAUX DE PETRI HAUT NIVEAU
3.1 Introduction
3.2 Les réseaux colorés
3.2.1 Notations
3.2.2 Le formalisme
3.3 Les réseaux bien formés
3.3.1 Domaines de couleur
3.3.2 Fonction de couleur
3.3.3 Les gardes
3.3.4 Le formalisme des réseaux bien formés
3.3.5 Les réseaux réguliers et les réseaux ordonnés
3.3.5.1 Réseau régulier
3.3.5.2 Réseaux ordonnés
3.4 Réductions structurelles
3.4.1 Principe d’extension aux réseaux colorés
3.4.2 Pré et post-agglomérations de transitions
3.4.2.1 Transition ordinaire pré-agglomerables
3.4.2.2 Réseau pré-aggloméré
3.4.2.3 Transition pré-agglomerables
3.4.2.4 Réseau pré-aggloméré
3.4.2.5 Transitions ordinaires post-agglomerables
3.4.2.6 Réseau post-aggloméré
3.4.2.7 Transitions post-agglomerables
3.4.2.8 Réseau post-aggloméré
3.4.3 Suppression de place implicite
3.5 Conclusion
CONCLUSION GENERALE
