Modélisation des Réseaux de Télécommunication à l’aide des Systèmes Multi-Agents et les Réseaux de Pétri.
Thème:
Présenté par: Elie FUTE T.
L’expansion des technologies de
l'information et des télécommunications
rencontre des limites dans les domaines
suivant:
Ubiquité
Mobilité Temps-réel
Introduction (Contexte d’étude)
Introduction (Contexte d’étude)
Développement (anarchique) dans le domaine des télécommunications constaté dans nos pays du Sud
Qualité des services
Facteur d'échelle….
Suite et fin
Introduction (Problématique)
On rencontre des équipements (les routeurs, les commutateurs, … ) donc les comportements changent en fonction des circonstances et du temps. L’allocation des bandes passantes a pour effet de faire modifier l’état des équipements. L’occupation des surfaces terriennes (régions) se veut dynamique et dépend de la situation géographique et/ou des intempéries environnementales de la dite région.
Dans le contexte des télécommunications
Introduction (Problématique)
Suite
Les travaux doivent se valoir une illustration de l’apport d’une méthodologie très récente en informatique : l’approche multi-agent, à l’étude du développement des réseaux de télécommunications.
Elle devra être en même temps une contribution à l’étude formelle des systèmes multi-agents par les réseaux de Pétri, l’objectif ici étant la preuve formelle de certaines propriétés observées lors des simulations multi-agents.
Il s’agira donc:
De la mise en œuvre d’un environnement de simulation multi-agents.
La modélisation et la simulation multi-agent d’un phénomène complexe : le développement des réseaux de télécommunications.
La formalisation de modèles multi-agents par les réseaux de Pétri en vue de valider les résultats des simulations multi-agents.
Introduction (Problématique)
Suite et Fin
Le développement d’un environnement de simulation multi-agents.
La mise en œuvre d’un environnement de simulation des réseaux de Pétri.
La formalisation de modèles multi-agents par les réseaux de Pétri en vue de valider les résultats des simulations multi-agents.
Introduction (Objectifs et résultats attendus)
Fin
Exemple de système de télécommunications
C ellu le
liais
on fib
re
optiq
ue
Ethernet
Token-ring
TelephoneTelephone
Peer-to-peer
W orkstation
IBM Com patibleMac C lassic
Laptop com puter
IBM Com patible
IBM Com patible
Cloud
Cloud
Telephone
W orkstation
W orkstation
W orkstationW orkstation
Hub
Laptop com puter
IBM Com patible
IBM Com patible
Satellite
Satellite dish
Radio tower
Public switch
Satellite
Radio tower
FDDI R ing
IBM Com patible
W orkstation
W orkstation
IBM Com patible
Router
Laptop com puter
IBM Com patibleW orkstation
Cloud
Public switch
Modem
Fax
IBM Com patible
M icrowave T ower
lia ison fibre optique
Satellite dish
Reflecteurd'onde
Recepteur
Recepteur
Recepteur
Chapitre 1(Système de télécommunication)
Approche Multi-agents
L’approche multi-agents est fondée sur un principe général d’individualisation des systèmes cibles (« Intelligence Artificielle Distribuée ») en un ensemble d’entités élémentaires en interaction
Elle consiste donc pour un système complexe, à :
•le décrire,•le modéliser, •l’analyser.
Chapitre 1(Agent & Système Multi-Agents)
Suite
Suite
Plusieurs arguments vont en faveur des systèmes multi-agents, à savoir :
L’efficacité des traitementsLa robustesse et la sûreté de fonctionnementLa flexibilité et le traitement à grande échelleUn coût de fonctionnement faibleUn coût de développement et de réutilisation intéressant
Chapitre 1(Agent & Système Multi-Agents)
Pour étudier la dynamique des systèmes complexes, l’approche multi-agent est aujourd’hui utilisée comme une alternative aux modèles mathématiques classiques.
Cette approche consiste à représenter le système non pas en termes de variables et d’équations, mais plutôt en termes d’entités et d’interactions.
L’approche multi-agent permet également de prendre en compte dans les modèles, des comportements qualitatifs et individuels.
Chapitre 1(Agent & Système Multi-Agents)
Suite
Chapitre 1(Agent & Système Multi-Agents)
Suite
un agent est une entité logicielle ou physique à qui est attribuée une certaine mission qu’elle est capable d’accomplir de manière autonome et en coopération avec d’autres agents.
Qu’est-ce qu’un agent ?
Qu’est-ce qu’un système multi-agent (SMA ou MAS )?Un système multi-agent est un ensemble organisé d’agents.
Liens
CartesContraintes
Nœuds
Usagers Equipements
Gestionnaire
Suite
Agent CARTE
Agent NOEUDS
Agent GESTIONNAIRE
Cartesindexcarte
Nœudsindex
Liensnatureliens
Usagersidentificateur
Contraintesnaturec
Equipementsidentificateq
Gestionnairenature
Agent Ligne COMMUNICATION
Chapitre 1(Modélisation par Système Multi-Agents)
Chapitre 1(Modélisation par Système Multi-Agents)
Suite Inter-action entre agents
Agent CarteAgent Nœud
Agent Coordonnateur
Agent LigneCommunication
Une étude du problème à résoudre nous amène à la modélisation suivante:
Chapitre 1(Simulation du Système Multi-Agents)
SuiteExécution de l’agent Carte
Chapitre 1(Simulation du Système Multi-Agents)
SuiteExécution de l’agent Noeud
Agent 1X=30Y=30
Agent 2X=50
Y=140
Suite
Les simulations multi-agents permettent d’étudier le comportement d’un modèle sur un temps fini. Au moment où on arrête une simulation, rien ne permet d’affirmer que la tendance qui s’affiche sera maintenue si on poursuivait la simulation.
Il s’agira donc de s’interroger sur la validité des résultats dans le cas où on prolongerait le temps de simulation.
Chapitre 1(Système Multi-Agents)
Bien que les équations différentielles nous offrent d’énormes possibilités d’analyse formelle, il est très difficile de traduire le modèle multi-agent dans ce formalisme sans le dénaturer totalement.
Comme formalisme de validation du modèle multi-agent, nous étudierons les réseaux de Pétri
Chapitre 1(Système Multi-Agents)
Suite et Fin
Chapitre 2 (Les réseaux de Pétri )
Les réseaux de Pétri sont à la fois un formalisme mathématique et un langage graphique pour modéliser les systèmes complexes.
Un réseau de Pétri est un graphe biparti comprenant deux sortes de nœuds : les places et les transitions.
Un graphe biparti se définit comme un graphe G=(S,A) dans lequel S est l’ensemble des sommets (places et transitions) et A l’ensemble des arcs
Suite
On représente généralement les places par des cercles et les transitions par des barres ou des rectangles. Les arcs d’un réseau de Pétri relient donc les transitions aux places ou les places aux transitions. Les places contiennent des jetons ou marques qui se déplacent de place en place en franchissant les transitions suivant une règle dite de franchissement.
Chapitre 2 (Les réseaux de Pétri )
Suite
Exemple de réseau de Pétri
Suite
Chapitre 2 (Les réseaux de Pétri )
La figure suivante présente un exemple de réseau de Pétri.
Définition formelle
Un réseau de Pétri est défini par R = (P,T,W) où P est un ensemble fini {p1,…, pm} de places
T est un ensemble fini {t1,…, tm } de transitions
W : (P x T) (T x P) N est la fonction de valuation, N représente l’ensemble des entiers naturels.
Un marquage est une fonction de P dans N qui définit la distribution des marques dans les places. A toute place pi de P est associé le nombre de jetons
qu’elle contient.
Chapitre 2 (Les réseaux de Pétri )
Suite
Suite
Chapitre 2 (Les réseaux de Pétri )
Franchissement de transition
Le franchissement d’une transition ne peut s’effectuer que si chacune des places en amont de cette transition contient au moins une marque. On dit alors que la transition est franchissable, ou validée.
Le franchissement d’une transition Tj consiste à
retirer une marque dans chacune des places en amont de la transition Tj et à ajouter une marque dans
chacune des places en aval de la transition Tj
Chapitre 2 (Les réseaux de Pétri )
Théorème fondamental (Condition nécessaire d’accessibilité)
Si le marquage Md est accessible à partir du
marquage M0 après le franchissement de la séquence
de transition s = (s1, s2,…, sd), alors
Md = M0 + CS
où S est le vecteur de taille n x 1 dans lequel chaque Sj représente le nombre de fois où la transition
tj est franchie dans la séquence s.
C est la matrice de connexion de taille m x n.M0 : P N est le marquage initial. Suite
Chapitre 2 (Modélisation par Les réseaux de Pétri )
Suite
A1 A2
Chapitre 2 (Modélisation par Les réseaux de Pétri )
p6
t4
p1
t1
p5
p4
p3
p2
t5
t3
t2
t6
p7
Envoi et réception de message par un réseau de Pétri
Suite
Suite
Positionnement des composants sur la carte par un réseau de Pétri
t2
t1
t3
p3
p1
p2
p4
Chapitre 2 (Modélisation par les réseaux de Pétri )
Suite
Considérons le premier modèle celui de l’envoi et réception de message.
Il peut être défini mathématiquement par les ensemblesP={p1, p2, p3, p4, p5, p6, p7}
T={ t1, t2, t3, t4, t5, t6}
et
la matrice de connexion suivante
Chapitre 2 (Modélisation par les réseaux de Pétri )
Suite
M0 =
100000110000
011110001110000011000001000001
Un élément Ai,j de la matrice représente la variation
du nombre de jetons de la place pi après le
franchissement de la transition tj.
Matrice de connexion
Chapitre 2 (Modélisation par les réseaux de Pétri )
M0 =
0001011
qui correspond à la présence d’un jeton dans les places p1,
p2, et p4 pendant que les autres places restent vides ( voir
figure suivante). Suite
Chapitre 2 (Modélisation par les réseaux de Pétri )
Considérons le marquage initial suivant
Marquage initial d’envoi et réception de message
p6
t4
p1
t1
p5
p4
p3
p2
t5
t3
t2
t6
p7Chapitre 2 (Modélisation par les réseaux de Pétri )
Suite
Suite
Les transitions t1 et t3 sont franchissables. Cette
séquence de transition est représentée par le vecteur
S =
En simulant le réseau de Pétri ci-dessus, nous obtenons la matrice de marquage suivante :
000101
Chapitre 2 (Simulation par les réseaux de Pétri )
Suite
Chapitre 2 (Simulation par les réseaux de Pétri )
M =
0010100
qui correspond à la présence d’un jeton dans les places p3
et p5 pendant que les autres places restent vides.
La figure suivante illustre cela.
On obtient le marquage suivant
Marquage après franchissement des transitions de t1 et t3.
p6
t4
p1
t1
p5
p4
p3
p2
t5
t3
t2
t6
p7Chapitre 2 (Simulation par les réseaux de Pétri )
Suite
Suite et fin
Chapitre 2 (Simulation par les réseaux de Pétri )
Nous avons:
Propos modèle multi-agents pour un système de télécommunication
Modélisation par les réseaux de Pétri
Simulation du modèle de Pétri
Conclusion (Synthèse des travaux)
Perspectives
Développer la plateforme de simulation multi-agents. Développer la communication entre agents. Mettre sur pied une passerelle de transmission des données de la plate-forme Multi-agents à la plateforme des Réseaux de Pétri.