DEV - DEVS

DEVS abbreviazione Discrete Event System Specification è un formalismo modulare e gerarchico per la modellazione e l'analisi di sistemi generali che possono essere sistemi a eventi discreti che potrebbero essere descritti da tabelle di transizione di stato e sistemi a stati continui che potrebbero essere descritti da equazioni differenziali e stati continui ibridi e sistemi a eventi discreti. DEVS è un sistema di eventi a tempo .

Storia

DEVS che abbrevia la specifica del sistema di eventi discreti è un formalismo modulare e gerarchico per la modellazione e l'analisi di sistemi generali che possono essere sistemi di eventi discreti che potrebbero essere descritti da tabelle di transizione di stato e sistemi di stato continui che potrebbero essere descritti da equazioni differenziali e sistemi ibridi ... DEVS è un formalismo per la modellazione e l'analisi di sistemi a eventi discreti (DES). Il formalismo DEVS è stato inventato da Bernard P. Zeigler , professore emerito all'Università dell'Arizona . DEVS è stato presentato al pubblico nel primo libro di Zeigler, Theory of Modeling and Simulation , nel 1976, mentre Zeigler era professore associato presso l' Università del Michigan . DEVS può essere visto come un'estensione del formalismo della macchina di Moore , che è un automa a stati finiti in cui gli output sono determinati solo dallo stato corrente (e non dipendono direttamente dall'input). L'estensione è stata fatta da

  1. associando una durata di vita ad ogni stato [Zeigler76] ,
  2. fornendo un concetto gerarchico con un'operazione, chiamata accoppiamento [Zeigler84] .

Poiché la durata di ogni stato è un numero reale (più precisamente, reale non negativo) o infinito, si distingue dai sistemi a tempo discreto, dalle macchine sequenziali e dalle macchine di Moore , in cui il tempo è determinato da un tempo di tick moltiplicato per non- interi negativi. Inoltre, la durata della vita può essere una variabile casuale ; ad esempio la durata di un dato stato può essere distribuita in modo esponenziale o uniforme . La transizione di stato e le funzioni di uscita di DEVS possono anche essere stocastiche .

Zeigler ha proposto un algoritmo gerarchico per la simulazione del modello DEVS nel 1984 [Zeigler84] che è stato pubblicato sulla rivista Simulation nel 1987. Da allora, molti formalismi estesi da DEVS sono stati introdotti con i propri scopi: DESS/DEVS per sistemi combinati di eventi continui e discreti, P-DEVS per DES paralleli, G-DEVS per la modellazione di traiettorie di stato continue a tratti di DES, RT-DEVS per DES in tempo reale, Cell-DEVS per DES cellulari, Fuzzy-DEVS per DES fuzzy, DEVS di strutturazione dinamica per DES che cambiano dinamicamente le loro strutture di accoppiamento , e così via. Oltre alle sue estensioni, sono state studiate alcune sottoclassi come SP-DEVS e FD-DEVS per ottenere la decidibilità delle proprietà del sistema.

A causa delle viste di modellazione modulare e gerarchica, nonché della sua capacità di analisi basata sulla simulazione, il formalismo DEVS e le sue variazioni sono state utilizzate in molte applicazioni dell'ingegneria (come progettazione hardware, codesign hardware/software, sistemi di comunicazione , sistemi di produzione ) e la scienza (come la biologia e la sociologia )

Formalismo

Fig. 1. Un modello DEVS per il gioco del ping-pong
Esempio intuitivo

DEVS definisce il comportamento del sistema e la struttura del sistema. Il comportamento del sistema nel formalismo DEVS è descritto utilizzando eventi di input e output e stati. Ad esempio, per il giocatore di ping-pong della Fig. 1, l'evento di input è ?receive e l'evento di output è !send . Ogni giocatore, A , B , ha i suoi stati: Send e Wait . Lo stato di invio impiega 0,1 secondi per rispedire indietro la palla che è l'evento di output !send , mentre lo stato di attesa dura fino a quando il giocatore non riceve la palla che è l'evento di input ?receive .

La struttura del gioco del ping-pong è quella di connettere due giocatori: l' evento di output del giocatore A !send viene trasmesso all'evento di input del giocatore B ?receive e viceversa.

Nel classico formalismo DEVS, Atomic DEVS cattura il comportamento del sistema, mentre Coupled DEVS descrive la struttura del sistema.

La seguente definizione formale è per Classic DEVS [ZKP00] . In questo articolo utilizzeremo la base dei tempi, ovvero l'insieme dei numeri reali non negativi; la base dei tempi estesa, cioè l'insieme dei numeri reali non negativi più infinito.

Atomic DEVS

Un modello DEVS atomico è definito come una tupla 7

dove

  • è l'insieme degli eventi di input ;
  • è l'insieme degli eventi di output ;
  • è l'insieme degli stati sequenziali (o anche detto insieme degli stati parziali );
  • è lo stato iniziale ;
  • è la funzione di anticipo temporale che viene utilizzata per determinare la durata della vita di uno stato;
  • è la funzione di transizione esterna che definisce come un evento ingresso cambia lo stato del sistema, in cui è l' insieme degli stati totali , ed è il tempo trascorso da quando l'ultimo evento ;


  • è la funzione di transizione interna che definisce come uno stato del sistema cambia internamente (quando il tempo trascorso raggiunge la durata dello stato);
  • è la funzione di output dove e è un evento silenzioso o un evento non osservato . Questa funzione definisce come uno stato del sistema genera un evento di uscita (quando il tempo trascorso raggiunge la durata dello stato);
Il modello atomico DEVS per i giocatori di ping-pong

Il modello atomico DEVS per il giocatore A di Fig. 1 è dato Player= tale che

Sia il giocatore A che il giocatore B sono modelli DEVS atomici.

Comportamento di Atomic DEVS

In parole povere, ci sono due casi in cui un modello DEVS atomico può cambiare il suo stato : (1) quando un input esterno entra nel sistema ; (2) quando il tempo trascorso raggiunge la durata della vita definita da . (Allo stesso tempo di (2), genera un output che è definito da .) .

Per la descrizione formale del comportamento di un dato modello DEVS atomico, fare riferimento alla pagina Comportamento di DEVS . Algoritmi informatici per implementare il comportamento di un dato modello Atomic DEVS sono disponibili in Algoritmi di simulazione per Atomic DEVS .

DEVS . accoppiati

Il DEVS accoppiato definisce quali sottocomponenti gli appartengono e come sono collegati tra loro. Un modello DEVS accoppiato è definito come una tupla 8

dove

  • è l'insieme degli eventi di input ;
  • è l'insieme degli eventi di output ;
  • è l'insieme dei nomi dei sottocomponenti ;
  • è l'insieme dei sottocomponenti dove per ciascuno può essere un modello DEVS atomico o un modello DEVS accoppiato.
  • è l'insieme degli accoppiamenti di ingresso esterni ;
  • è l'insieme degli accoppiamenti interni ;
  • è la funzione di accoppiamento dell'uscita esterna ;
  • è la funzione di tie-breaking che definisce come selezionare l'evento dall'insieme degli eventi simultanei;
Il modello DEVS accoppiato per il gioco del ping-pong

Il gioco del ping-pong di Fig. 1 può essere modellato come un modello DEVS accoppiato dove ; ; ; è descritto come sopra; ; ; e .

Comportamento di DEVS . accoppiati

In parole povere, come il comportamento della classe DEVS atomica, un modello DEVS accoppiato cambia gli stati dei suoi componenti (1) quando un evento esterno entra in ; (2) quando uno dei componenti in cui esegue la sua transizione di stato interna e genera il suo output . In entrambi i casi (1) e (2), un evento di attivazione viene trasmesso a tutte le influenze che sono definite dai set di accoppiamento e .

Per la definizione formale del comportamento dei DEVS accoppiati, è possibile fare riferimento a Comportamento dei DEVS accoppiati . Algoritmi informatici per implementare il comportamento di una data modalità DEVS accoppiata sono disponibili in Algoritmi di simulazione per DEVS accoppiati .

Metodi di analisi

Simulazione per sistemi a eventi discreti

L'algoritmo di simulazione dei modelli DEVS considera due questioni: la sincronizzazione temporale e la propagazione dei messaggi. La sincronizzazione dell'ora di DEVS consiste nel controllare tutti i modelli in modo che abbiano l'ora corrente identica. Tuttavia, per un'esecuzione efficiente, l'algoritmo fa passare l'ora corrente all'ora più urgente in cui un evento è pianificato per eseguire la sua transizione di stato interno e la sua generazione di output. La propagazione del messaggio consiste nel trasmettere un messaggio di attivazione che può essere un evento di ingresso o di uscita lungo gli accoppiamenti associati definiti in un modello DEVS accoppiato. Per informazioni più dettagliate, il lettore può fare riferimento a Algoritmi di simulazione per DEVS atomici e Algoritmi di simulazione per DEVS accoppiati .

Simulazione per sistemi a stati continui

Introducendo un metodo di quantizzazione che astrae un segmento continuo come un segmento const a tratti, DEVS può simulare comportamenti di sistemi di stati continui descritti da reti di equazioni algebriche differenziali . Questa ricerca è stata avviata da Zeigler negli anni '90 e molte proprietà sono state chiarite dal Prof. Kofman negli anni 2000 e dal Dr. Nutaro. Nel 2006, il prof. Cellier, autore di Continuous System Modeling [Cellier91] , e il prof. Kofman hanno scritto un libro di testo, Continuous System Simulation [CK06] in cui i capitoli 11 e 12 illustrano come DEVS simula i sistemi a stati continui. Il libro del Dr. Nutaro [Nutaro10] , copre anche la simulazione ad eventi discreti di sistemi a stati continui.

Verifica per sistemi a eventi discreti

Come metodo di analisi alternativo rispetto al metodo di simulazione basato sul campionamento, per l'analisi dei modelli DEVS è stato applicato un approccio esaustivo del comportamento generativo, generalmente chiamato verifica . È dimostrato che gli stati infiniti di un dato modello DEVS (specialmente un modello DEVS accoppiato) possono essere astratti da una struttura finita isomorfa comportamentale, chiamata grafico di raggiungibilità quando il modello DEVS dato è una sottoclasse di DEVS come Schedule-Preserving DEVS ( SP-DEVS ), DEVS finiti e deterministici ( FD-DEVS ) [HZ09] e DEVS finiti e in tempo reale (FRT-DEVS) [Hwang12] . Di conseguenza, in base al grafico della ricercabilità, (1) deadlock e live-lock freeness come proprietà qualitative sono decidibili con SP-DEVS [Hwang05] , FD-DEVS [HZ06] e FRT-DEVS [Hwang12] ; e (2) i limiti del tempo di elaborazione min/max come proprietà quantitativa sono determinabili con SP-DEVS finora entro il 2012.

Varianti di DEVS

Estensioni (superclasse)

Negli ultimi decenni sono state sviluppate numerose estensioni del formalismo classico DEVS. Tra questi i formalismi che consentono di avere strutture del modello mutevoli mentre il tempo di simulazione evolve.

G-DEVS [Giambiasi01][Zacharewicz08] , Parallel DEVS, Dynamic Structuring DEVS, Cell-DEVS [Wainer09] , dynDEVS, Fuzzy-DEVS, GK-DEVS, ml-DEVS, DEVS simbolici, Real-Time DEVS, rho-DEVS

Restrizioni (sottoclassi)

Esistono alcune sottoclassi note come DEVS a conservazione della pianificazione ( SP-DEVS ) e DEVS finite e deterministiche ( FD-DEVS ) che sono state designate per supportare l'analisi di verifica. SP-DEVS e FD-DEVS le cui espressività sono E ( SP-DEVS ) E ( FD-DEVS ) E (DEVS) dove E ( formalismo ) denota l'espressività del formalismo .

Guarda anche

Articoli correlati a DEVS

Altri formalismi

Note a piè di pagina

  1. ^ Gli automi erano i modelli matematici del dottorato di ricerca del Dr. Zeigler. tesi [Zeigler68]
  2. ^ Possiamo anche definire la funzione di transizione esterno comedovetale che per uno stato totale,è uno stato parziale,è la durata della vita, edè il tempo trascorso aggiornamento di. Per ulteriori informazioni su come comprendere questa funzione, fare riferimento all'articolo Comportamento di DEVS .
  3. ^ l'uso di valori quantizzati per simulare sistemi continui mediante unmetodo ad eventi discreti fu sperimentato empiricamente qualche anno prima - all'inizio degli anni '90 - da un ingegnere francese <Abbiamo bisogno di qualsiasi riferimento per questo argomento>. All'epoca lavorava per una società scorporata dall'Università di Valenciennes , e ora parte della Schneider Electric . Questa quantizzazione è una caratteristica di un software di simulazione di cui questo ingegnere è l'ideatore e lo sviluppatore principale, che viene utilizzato per ilcontrollo dei programmi PLC e la formazione degli operatori.

Riferimenti

  • [Cellier91] Francois E. Cellier (1991). Modellazione continua del sistema (prima ed.). Springer. ISBN 978-0-387-97502-3.
  • [CK06] Francois E. Cellier; Ernesto Kofman (2006). Simulazione continua del sistema (prima ed.). Springer. ISBN 978-0-387-26102-7.
  • [Giambiasi01] Giambiasi N., Escude B. Ghosh S. “Generalized Discrete Event Simulation of Dynamic Systems”, in: Issue 4 of SCS Transactions: Recent Advances in DEVS Methodology-part II, Vol. 18, pp. 216-229, dic 2001
  • [Hwang05] MH Hwang, "Tutorial: Verification of Real-time System Based on Schedule-Preserved DEVS", Atti del simposio DEVS 2005 , San Diego, 2-8 aprile 2005, ISBN  1-56555-293-8 ,
  • [HZ06] MH Hwang e BP Zeigler, "A Modular Verification Framework using Finite and Deterministic DEVS", Atti del simposio DEVS 2006 , pp57-65, Huntsville, Alabama, USA,
  • [HZ09] MH Hwang e BP Zeigler, "Grafico di raggiungibilità di reti DEVS finite e deterministiche", IEEE Transactions on Automation Science and Engineering , Volume 6, Issue 3, 2009, pp. 454–467,
  • [Hwang12] MH Hwang, "Verifica qualitativa di reti DEVS finite e in tempo reale", Atti del Simposio 2012 sulla teoria della modellizzazione e simulazione - Simposio DEVS Integrativo M&S , Articolo n. 43,
  • [Mittal13] Saurabh Mittal; Jose L. Risco Martin (2013). Sistema Netcentrico di Ingegneria dei Sistemi con DEVS Unified Process (prima ed.). CRC Press. ISBN 978-1439827062.
  • [Nutaro10] James Nutaro (2010). Costruire software per la simulazione: teoria, algoritmi e applicazioni in C++ (prima ed.). Wiley. ISBN 0-470-41469-3.
  • [Sarjoughian09] Hessam S. Sarjoughian; Vignesh Elamvazhuthi (2009). "CoSMoS: un ambiente visivo per la modellazione basata su componenti, la progettazione sperimentale e la simulazione". Atti del Convegno Internazionale su Strumenti e Tecniche di Simulazione. Citare il diario richiede |journal=( aiuto )
  • [Wainer09] Gabriel A. Wainer (2009). Modellazione e simulazione a eventi discreti: l'approccio di un professionista (prima ed.). CRC Press. ISBN 978-1-4200-5336-4.
  • [Wainer10] Gabriel A. Wainer e Pieter Mosterman Eds. (2010). Modellazione e simulazione ad eventi discreti: teoria e applicazioni (prima ed.). CRC Press. ISBN 978-1-4200-7233-4.
  • [Zacharewicz08] Gregory Zacharewicz, Claudia Frydman e Norbert Giambiasi (2008) G-DEVS/HLA Environment for Distributed Simulations of Workflows, SIMULATION May 2008 84: 197-213, doi : 10.1177/0037549708092833 .
  • [Zeiger68] Bernard Zeigler (1968). Sulla complessità del feedback degli automi (tesi di dottorato ed.). Università del Michigan.
  • [Zeigler76] Bernard Zeigler (1976). Teoria della modellazione e simulazione (prima ed.). Wiley Interscience, New York. ISBN 0-12-778455-1.
  • [Zeigler84] Bernard Zeigler (1984). Modellazione multiforme e simulazione di eventi discreti . Academic Press, Londra; Orlando. ISBN 978-0-12-778450-2.
  • [Zeigler87] Bernard Zeigler (1987). "Modellazione gerarchica e modulare ad eventi discreti in un ambiente orientato agli oggetti". Simulazione . 49 (5): 219-230. doi : 10.1177/003754978704900506 .
  • [ZKP00] Bernard Zeigler; Tag Gon Kim; Herbert Praehofer (2000). Teoria della modellazione e simulazione (seconda ed.). Stampa accademica, New York. ISBN 978-0-12-778455-7.