DEVS, que abreuja Discrete Event System Specification, és un formalisme modular i jeràrquic per modelar i analitzar sistemes generals que poden ser sistemes d'esdeveniments discrets que es podrien descriure per taules de transició d'estats, i sistemes d'estat continu que es podrien descriure per equacions diferencials i sistemes híbrids d'estat continu i esdeveniments discrets. DEVS és un sistema d'esdeveniments cronometrats.
Història DEVS és un formalisme per a la modelització i anàlisi de sistemes d'esdeveniments discrets (DES). El formalisme DEVS va ser inventat per Bernard P. Zeigler, que és professor emèrit a la Universitat d'Arizona. DEVS es va presentar al públic en el primer llibre de Zeigler, Theory of Modeling and Simulation , el 1976, mentre Zeigler era professor associat a la Universitat de Michigan. DEVS es pot veure com una extensió del formalisme de la màquina de Moore, que és un autòmat d'estat finit on les sortides estan determinades només per l'estat actual (i no depenen directament de l'entrada). L'ampliació la va fer
associant una vida útil a cada estat [Zeigler76] , proporcionant un concepte jeràrquic amb una operació, anomenada acoblament [Zeigler84].
Atès que la vida útil de cada estat és un nombre real (més precisament, real no negatiu) o infinit, es distingeix dels sistemes de temps discrets, les màquines seqüencials i les màquines de Moore, en què el temps està determinat per un temps de tick multiplicat per nombres enters no negatius. A més, la vida útil pot ser una variable aleatòria; per exemple, la vida útil d'un estat determinat es pot distribuir de manera exponencial o uniforme. La transició d'estat i les funcions de sortida de DEVS també poden ser estocàstiques.
Zeigler va proposar un algorisme jeràrquic per a la simulació del model DEVS el 1984 [Zeigler84] que es va publicar a la revista Simulation el 1987. Des d'aleshores, s'han introduït molts formalismes estès de DEVS amb els seus propis propòsits: DESS/DEVS per a sistemes d'esdeveniments continus i discrets combinats, P-DEVS per a DES paral·lels, G-DEVS per a la modelització de trajectòries d'estat continu a trossos de DES, RT-DEVS per a DES en temps real, Cell-DEVS per a DES cel·lulars, Fuzzy-DEVS per a DESsturling Fuzzy-DEVS, DEVS per a l'acoblament dinàmic de la seva estructura. estructures dinàmicament, etc. A més de les seves extensions, hi ha algunes subclasses com SP-DEVS i FD-DEVS que s'han investigat per aconseguir la decidibilitat de les propietats del sistema.
A causa de les vistes de modelització modular i jeràrquica, així com de la seva capacitat d'anàlisi basada en simulació, el formalisme DEVS i les seves variacions s'han utilitzat en moltes aplicacions d'enginyeria (com ara disseny de maquinari, codisseny de maquinari/programari, sistemes de comunicacions, sistemes de fabricació) i ciència (com biologia i sociologia).
Formalisme miniatura|400x400px|Fig. 1. Un model DEVS per al joc de ping-pong Exemple intuïtiu
DEVS defineix el comportament del sistema així com l'estructura del sistema. El comportament del sistema en el formalisme DEVS es descriu mitjançant esdeveniments d'entrada i sortida, així com estats. Per exemple, per al jugador de ping-pong de la figura 1, l'esdeveniment d'entrada és ?receive, i l'esdeveniment de sortida és !send. Cada jugador, A, B, té els seus estats: Envia i Espera. L'estat d'enviament triga 0,1 segons a enviar de tornada la pilota que és l'esdeveniment de sortida !send, mentre que l'estat d'espera dura fins que el jugador rep la pilota que és l'esdeveniment d'entrada ?rebre.
L'estructura del joc de ping-pong és connectar dos jugadors: l'esdeveniment de sortida ' jugador A !l'enviament es transmet a l'esdeveniment d'entrada ' jugador B ?rebre, i viceversa.
En el formalisme DEVS clàssic, el DEVS atòmic captura el comportament del sistema, mentre que el DEVS acoblat descriu l'estructura del sistema.
La definició formal següent és per a DEVS clàssic [ZKP00]. En aquest article, utilitzarem la base de temps, és a dir el conjunt de nombres reals no negatius; la base de temps ampliada, és a dir el conjunt de nombres reals no negatius més infinit.
DEVS atòmic Un model DEVS atòmic es defineix com una tupla de 7on
és el conjunt d'esdeveniments d'entrada; és el conjunt d'esdeveniments de sortida; és el conjunt d'estats seqüencials (o també anomenat conjunt d'estats parcials); és l'estat inicial; és la funció d'avançament de temps que s'utilitza per determinar la vida útil d'un estat; és la funció de transició externa que defineix com un esdeveniment d'entrada canvia un estat del sistema, on és el conjunt d'estats totals, i és el temps transcorregut des de l'últim esdeveniment;
és la funció de transició interna que defineix com canvia internament un estat del sistema (quan el temps transcorregut arriba a la vida útil de l'estat); és la funció de sortida on i és un esdeveniment silenciós o no observat. Aquesta funció defineix com un estat del sistema genera un esdeveniment de sortida (quan el temps transcorregut arriba a la vida útil de l'estat);
El model DEVS atòmic per a jugadors de ping-pong
El model DEVS atòmic per al jugador A de la figura 1 es dona Player= tal que
Tant el jugador A com el jugador B són models DEVS atòmics.
DEVS acoblat El DEVS acoblat defineix quins subcomponents hi pertanyen i com estan connectats entre si. Un model DEVS acoblat es defineix com una tupla de 8on
és el conjunt d'esdeveniments d'entrada; és el conjunt d'esdeveniments de sortida; és el nom del conjunt de subcomponents; és el conjunt de subcomponents on per a cadascun pot ser un model DEVS atòmic o un model DEVS acoblat. és el conjunt d'acoblaments d'entrada externa; és el conjunt d'acoblaments interns; és la funció d'acoblament de sortida externa; és la funció de desempat que defineix com seleccionar l'esdeveniment del conjunt d'esdeveniments simultanis;
El model DEVS acoblat per al joc de ping-pong
El joc de ping-pong de la figura 1 es pot modelar com un model DEVS acoblat on ; ; ; es descriu com a anterior; ; ; i .
Mètodes d'anàlisi Simulació per a sistemes d'esdeveniments discrets L'algoritme de simulació dels models DEVS considera dues qüestions: la sincronització del temps i la propagació del missatge. La sincronització horària de DEVS consisteix a controlar tots els models per tenir la mateixa hora actual. Tanmateix, per a una execució eficient, l'algoritme fa que el temps actual salti al moment més urgent quan un esdeveniment està programat per executar la seva transició d'estat intern així com la seva generació de sortida. La propagació del missatge és transmetre un missatge activador que pot ser un esdeveniment d'entrada o de sortida al llarg dels acoblaments associats que es defineixen en un model DEVS acoblat. Per obtenir informació més detallada, el lector pot consultar Algoritmes de simulació per a DEVS atòmics i Algoritmes de simulació per a DEVS acoblats.
Simulació per a sistemes d'estat continu Mitjançant la introducció d'un mètode de quantificació que abstra un segment continu com un segment constant a trossos, DEVS pot simular comportaments de sistemes d'estat continu que es descriuen per xarxes d'equacions algebraiques diferencials. Aquesta investigació ha estat iniciada per Zeigler a la dècada de 1990 i moltes propietats han estat aclarides pel professor Kofman a la dècada de 2000 i pel doctor Nutaro. El 2006, el Prof. Cellier, que és l'autor de Continuous System Modeling [Cellier91], i el Prof. Kofman, van escriure un llibre de text, Continuous System Simulation [CK06] en el qual els capítols 11 i 12 tracten com DEVS simula sistemes d'estat continu. El llibre del Dr. Nutaro [Nutaro10] també cobreix la simulació d'esdeveniments discrets dels sistemes d'estat continu.
Verificació per a sistemes d'esdeveniments discrets Com a mètode d'anàlisi alternatiu enfront del mètode de simulació basat en el mostreig, s'ha aplicat un enfocament exhaustiu del comportament generador, generalment anomenat verificació, per a l'anàlisi dels models DEVS. S'ha demostrat que els estats infinits d'un model DEVS determinat (especialment un model DEVS acoblat) es poden abstraure mitjançant una estructura finita isomòrfica conductualment, anomenada gràfic d'accessibilitat quan el model DEVS donat és una subclasse de DEVS com ara DEVS de preservació de l'horari (SP-DEVS), DEVS finit i determinista (FD-DEVS) [temps real i DEVS] (FRT-DEVS) [Hwang12]. Com a resultat, basant-se en el gràfic d'accessibilitat, la llibertat de bloqueig i de bloqueig en directe com a propietats qualitatives es poden decidir amb SP-DEVS [Hwang05], FD-DEVS [HZ06] i FRT-DEVS [Hwang12]; i els límits de temps de processament min/max com a propietat quantitativa es poden decidir amb SP-DEVS fins al 2012.
Referències
Categoria:Teoria de control