Sciences Pour l’Environnement

Nos tutelles

CNRS

Rechercher




Accueil > Projets de recherche > SISU (Simulation Informatique et Systèmes Ubiquitaires) > DEVSimPy > Présentation

Le Formalisme DEVS

par campana - publié le

Le formalisme DEVS vient du terme anglais Discrete Event System Specification, il s’agit d’un formalisme modulaire et hiérarchique qui permet de faire de la modélisation, de la simulation et de l’analyse de systèmes complexes, qui sont pour la plupart du temps des systèmes à événements discrets décrits par des fonctions de transitions d’états et de systèmes continus.

Introduction

Le formalisme DEVS vient du terme anglais Discrete Event System Specification, il s’agit d’un formalisme modulaire et hiérarchique qui permet de faire de la modélisation, de la simulation et de l’analyse de systèmes complexes, qui sont pour la plupart du temps des systèmes à événements discrets décrits par des fonctions de transitions d’états et de systèmes continus.

Le professeur Zeigler est le concepteur de ce formalisme, proposé vers la fin des années 70, il avait pour but de mettre en place un support mathématiques efficace et solide pour la modélisation des systèmes à événements discrets, ce dernier est un système qui représente un ensemble d’états et de règles de transition entre ces états. Ce qui nous permet de représenter des systèmes tel que des modèles ou des ensembles de modèles qui possèdent des états et des transitions.

Modèles DEVS

Zeigler définit deux types de modèles différents :
o Modèle atomique , il décrit l’aspect comportementale des systèmes. Il est indissociable et c’est un objet fondamental pour la modélisation DEVS, il est défini par un ensemble d’états et de transition entre ces états. (voir figure 1)

fig1 : Exemple de modèle atomique

Les modèles atomiques sont définis comme ci-dessous :

AM :< X ; Y ; S ; ta ; δext ; λ ; δint >

Avec :

  • X : est l’ensemble des valeurs d’entrée du modèle caractérisé par les informations suivantes port, temps, valeur). Le port dit sur qui l’évènement arrive, le temps est la date d’occurrence de l’évènement, il est vide pour des évènements internes et la valeur symbolise les données de l’évènement ;
  • Y : est l’ensemble des valeurs des évènements sortants ;
  • S : est l’ensemble des états partiels ou séquentiels incluant les variables d’états.
  • ta : S → T∞ : est la fonction d’avancement du temps qui est utilisée pour déterminer la durée de vie de l’état.
  • δext : Q → X → S : est la fonction de transition externe qui défini comment un message d’entrée X peut changer l’état du système, ou Q = (s, te) | s ∈ S, te ∈ (T ∩ [0, ta(s)] est l’ensemble des états, et te est le temps écoulé depuis le dernier évènement ;
  • λ : S → Yι : est la fonction de sortie ou Yι = Y ∪ ι et ι ∉ Y est un évènement silencieux ou non observé. Cette fonction définit comment un état du système génère des évènements de sortie quand le temps écoulé atteint la durée de vie de l’état ;
  • δint : S → S : est la fonction de transition interne qui défini comment un état du système change de façon interne quand le temps écoulé atteint la durée de vie de l’état.

o Modèle couplé , il représente l’aspect structurel. Il est possible pour un modèle couplé de comprendre un ou plusieurs modèles atomiques ou couplés. Il peut aussi être représenté par un modèle atomique unique. (voir figure 2)

fig 2 : Exemple de modèle couplé

Les modèles couplés sont définis comme ci-dessous :

CM :< XM, YM,CM,EIC,EOC, IC,L >

Avec :

  • XM : tous les ports d’entrés ;
  • YM : tous les ports de sorties ;
  • CM : la liste des modèles formant le modèle couplé ;
  • EIC : tous les couplages en entrés qui connectent le modèle couplé à ses composants ;
  • EOC : tous les couplages en sorties qui connectent le modèle couplé à ses composants ;
  • IC : tous les couplages internes qui connectent les composants entre eux ;
  • L : la liste de priorité entre les composants.

Comment ça marche ?

Les fonctions de transitions sont essentielles au formalisme DEVS. La fonction de transition interne est toujours suivie de la fonction de sortie. Le système est dans l’état S pendant un Temps « ta(s) » avant d’activer sa fonction de transition interne et de générer une sortie. La fonction de transition externe est exécutée à chaque fois qu’un évènement externe intervient. Cette fonction ne génère en aucun cas une sortie quelconque.

Arbre de simulation

Le formalisme DEVS a pour principal avantage la simulation automatique de ses modèles, donc le simulateur DEVS va à partir d’un arbre de simulation (voir figure 3), gérer les communications éventuelles entre les modèles automatiquement et exécuter leur fonction de transition. Il contrôle la simulation grâce à la représentation hiérarchique comme suit, un simulateur par modèle atomique et un coordinateur par modèle couplé grâce à une distribution réglementée des événements entre modèles.

fig 3 : Arbre de simulation

Pour finir

La simulation à événements discrets a pour atout une rapidité d’exécution due à l’évolution dirigée par événements, évitant les traitements à pas de temps continu. De plus, les notions de couplage, et la séparation entre modélisation et simulation au niveau du formalisme DEVS, permettent la réutilisation de modèles existants dans de nouveaux modèles composites. DEVS est un formalisme puissant qui permet donc la ré-utilisabilité des modèles au travers de bibliothèques de modèles pré développés, et surtout l’interconnexion de ces derniers pour composer des modèles hétérogènes basés sur différents formalismes de modélisation. Au sein de notre équipe, il est utilisé pour la simulation de systèmes continus, d’équations différentielles, de systèmes flous, de réseau de capteurs sans fil, de réseaux de neurones, et bien d’autres encore.