DEVS - DEVS

DEVS, lyhenne Discrete Event System Specification, on modulaarinen ja hierarkinen muodollisuus yleisten järjestelmien mallintamiseen ja analysointiin, jotka voivat olla erillisiä tapahtumajärjestelmiä, jotka voidaan kuvata tilasiirtymätaulukoilla , ja jatkuvia tilajärjestelmiä, jotka voidaan kuvata differentiaaliyhtälöillä , ja hybridi jatkuva tila ja erilliset tapahtumajärjestelmät. DEVS on ajastettu tapahtumajärjestelmä .

Historia

DEVS, lyhenne Discrete Event System Specification, on modulaarinen ja hierarkkinen formalismi yleisten järjestelmien mallintamiseen ja analysointiin, jotka voivat olla erillisiä tapahtumajärjestelmiä, jotka voidaan kuvata tilasiirtymätaulukoilla, ja jatkuvia tilajärjestelmiä, jotka voidaan kuvata differentiaaliyhtälöillä, ja hybridi ... DEVS on formalismi erillisten tapahtumajärjestelmien (DES) mallintamiseen ja analysointiin. DEVS -muodon keksi Bernard P. Zeigler , joka on emeritusprofessori Arizonan yliopistossa . DEVS esiteltiin yleisölle Zeiglerin ensimmäisessä kirjassa Theory of Modeling and Simulation vuonna 1976, kun taas Zeigler oli apulaisprofessori Michiganin yliopistossa . DEVS voidaan nähdä Mooren koneformalismin jatkeena , joka on äärellinen tila -automaatti, jossa lähdöt määräytyvät pelkästään nykyisen tilan perusteella (eivätkä ne ole suoraan riippuvaisia ​​panoksesta). Laajennuksen teki

  1. jokaisen valtion elinkaaren yhdistäminen [Zeigler76] ,
  2. tarjoamalla hierarkkisen käsitteen yhdistämisellä [Zeigler84] .

Koska kunkin tilan elinkaari on reaaliluku (tarkemmin sanottuna ei-negatiivinen todellinen) tai ääretön, se erotetaan erillisistä aikajärjestelmistä, peräkkäisistä koneista ja Moore-koneista , joissa aika määräytyy rasti-ajan kerrottuna ei- negatiiviset kokonaisluvut. Lisäksi elinikä voi olla satunnaismuuttuja ; esimerkiksi tietyn tilan elinikä voidaan jakaa eksponentiaalisesti tai tasaisesti . DEVS: n tilasiirtymä- ja tulostustoiminnot voivat olla myös stokastisia .

Zeigler ehdotti hierarkkista algoritmia DEVS -mallin simulointiin vuonna 1984 [Zeigler84], joka julkaistiin Simulation -lehdessä vuonna 1987. Siitä lähtien monet DEVS: n laajennetut muodollisuudet on otettu käyttöön omilla tarkoituksillaan: DESS/DEVS yhdistetyille jatkuville ja erillisille tapahtumajärjestelmille, P-DEVS rinnakkaisille DES-laitteille, G-DEVS DES-kappaleiden jatkuvalle jatkuvalle kehityssuunnan mallinnukselle, RT-DEVS reaaliaikaisille DES-laitteille, Cell-DEVS-solukko-DES-laitteille, Fuzzy-DEVS sumeille DES-laitteille, Dynamic Structuring DEVS DES-laitteille, jotka muuttavat kytkentärakenteitaan dynaamisesti , ja niin edelleen. Laajennusten lisäksi on tutkittu joitain alaluokkia, kuten SP-DEVS ja FD-DEVS järjestelmän ominaisuuksien päätettävyyden saavuttamiseksi.

Modulaaristen ja hierarkkisten mallinnusnäkymien sekä simulaatiopohjaisen analysointikyvynsä vuoksi DEVS-muodollisuutta ja sen muunnelmia on käytetty monissa tekniikan sovelluksissa (kuten laitteistosuunnittelu, laitteiston/ohjelmiston koodimerkki, viestintäjärjestelmät , valmistusjärjestelmät ) ja tiede (kuten biologia ja sosiologia )

Formalismi

Kuva 1. Ping-Pong-pelin DEVS-malli
Intuitiivinen esimerkki

DEVS määrittelee järjestelmän käyttäytymisen ja järjestelmän rakenteen. Järjestelmän käyttäytymistä DEVS -muodollisuudessa kuvataan syöttö- ja tulostetapahtumien sekä tilojen avulla. Esimerkiksi kuvion 1 ping-pong-soittimen tulotapahtuma on ? Vastaanottaa ja lähtötapahtuma on lähettää . Jokaisella pelaajalla A , B on tilat: Lähetä ja odota . Lähetystila vie 0,1 sekuntia lähettääkseen pallon, joka on lähtötapahtuma ! Lähetä , kun taas Odota -tila kestää, kunnes pelaaja vastaanottaa syötettävän tapahtuman vastaanottopallon .

Pöytätennispelin rakenne on yhdistää kaksi pelaajaa: Pelaajan A lähtötapahtuma ! Send lähetetään pelaajan B tulotapahtumaan ? Vastaanottaa ja päinvastoin.

Klassisessa DEVS -muodollisuudessa Atomic DEVS kuvaa järjestelmän käyttäytymistä, kun taas Coupled DEVS kuvaa järjestelmän rakennetta.

Seuraava muodollinen määritelmä koskee klassisia DEVS -laitteita [ZKP00] . Tässä artikkelissa käytämme aikapohjaa eli ei-negatiivisten reaalilukujen joukkoa; laajennettu aikaväli, eli joukko ei-negatiivisia reaalilukuja plus ääretön.

Atomic DEVS

Atomi DEVS malli on määritelty 7- monikko

missä

  • on syöttötapahtumien joukko ;
  • on tulostetapahtumien joukko ;
  • on peräkkäisten tilojen joukko (tai sitä kutsutaan myös ositilojen joukkoksi );
  • on alkutila ;
  • on ajan etenemistoiminto, jota käytetään tilan elinkaaren määrittämiseen;
  • on ulkoinen siirtofunktio , joka määrittää, kuinka tulo tapahtuma muuttuu tilaan järjestelmän, jossa on joukko koko todetaan , ja on kulunut aika , koska viime tapahtuma ;


  • on sisäinen siirtymätoiminto, joka määrittää, kuinka järjestelmän tila muuttuu sisäisesti (kun kulunut aika saavuttaa tilan käyttöiän);
  • on tulostustoiminto missä ja on hiljainen tapahtuma tai havaitsematon tapahtuma. Tämä toiminto määrittää, kuinka järjestelmän tila tuottaa lähtötapahtuman (kun kulunut aika saavuttaa tilan käyttöiän);
Atominen DEVS-malli pingispisteille

Kuvion 1 pelaajan A atomimalli DEVS on Player = sellainen

Sekä pelaaja A että pelaaja B ovat atomisia DEVS -malleja.

Atomic DEVS: n käyttäytyminen

Yksinkertaisesti sanottuna on kaksi tapausta, joissa atominen DEVS -malli voi muuttaa tilaa : (1) kun ulkoinen tulo tulee järjestelmään ; (2) kun kulunut aika saavuttaa elinkaaren, jonka määrittelee . (Samaan aikaan (2), tuottaa tuloksen, jonka määrittelee .).

Katso Atomic DEVS -mallin muodollinen käyttäytymiskuvaus sivulta DEVS -käyttäytyminen . Tietokonealgoritmit tietyn Atomic DEVS -mallin käyttäytymisen toteuttamiseksi ovat saatavilla Atomic DEVS: n simulaatioalgoritmeista .

Kytketty DEVS

Kytketty DEVS määrittää, mitkä alikomponentit kuuluvat siihen ja miten ne on kytketty toisiinsa. Kytketyn DEVS malli määritellään 8- monikko

missä

  • on syöttötapahtumien joukko ;
  • on tulostetapahtumien joukko ;
  • on alakomponenttien nimisarja ;
  • on joukko alikomponentteja, joissa kullekin voi olla joko atomi-DEVS-malli tai kytketty DEVS-malli.
  • on joukko ulkoisia tuloliittimiä ;
  • on sisäisten kytkinten sarja ;
  • on ulkoinen ulostulokytkentätoiminto ;
  • on tie-katkaisutoiminto, joka määrittää kuinka valita tapahtuma samanaikaisten tapahtumien joukosta;
Yhdistetty DEVS-malli Ping-Pong-pelille

Kuvion 1 pingpongipeli voidaan mallintaa kytketyksi DEVS-malliksi, jossa ; ; ; on kuvattu edellä; ; ; ja .

Kytkettyjen DEVS -laitteiden käyttäytyminen

Yksinkertaisesti sanottuna, kuten atomin DEVS -luokan käyttäytyminen, kytketty DEVS -malli muuttaa komponenttiensa tiloja (1) ulkoisen tapahtuman tullessa ; (2) kun yksi komponenteista , jossa suorittaa sisäisen tilasiirtymän ja tuottaa ulostulonsa . Molemmissa tapauksissa (1) ja (2) liipaisutapahtuma lähetetään kaikille vaikutuksille, jotka on määritelty kytkinsarjoilla ja .

Muodollisen määritelmän kytketyn DEVS: n käyttäytymisestä voit katsoa kytketyn DEVS: n käyttäytymisestä . Tietokonealgoritmit tietyn kytketyn DEVS -tilan käyttäytymisen toteuttamiseksi ovat saatavilla Simulointialgoritmeja kytketyille DEVS -laitteille .

Analyysimenetelmät

Simulaatio erillisille tapahtumajärjestelmille

DEVS -mallien simulointialgoritmi ottaa huomioon kaksi asiaa: ajan synkronoinnin ja viestin etenemisen. Ajan synkronointi of DEVS on hallita kaikkia malleja on sama kellonaika. Tehokkaan suorituksen saavuttamiseksi algoritmi saa kuitenkin nykyisen ajan hypätä kiireellisimpään aikaan, kun tapahtuma on ajoitettu suorittamaan sisäinen tilasiirtymänsä ja sen tuotos. Viestin eteneminen on lähettää laukaisusanoma, joka voi olla joko tulo- tai lähtötapahtuma yhdistettyjä DEVS -mallissa määriteltyjä kytkimiä pitkin. Yksityiskohtaisempia tietoja, lukija voi viitata simulointi algoritmit Atomic DEVS ja simulointi algoritmit Coupled DEVS .

Simulointi jatkuville tilajärjestelmille

Ottamalla käyttöön kvantisointimenetelmän, joka absorboi jatkuvan segmentin palasuuntaisena vakiosegmenttinä, DEVS voi simuloida jatkuvien tilajärjestelmien käyttäytymistä, jotka kuvataan differentiaalisten algebrallisten yhtälöiden verkoissa . Tämän tutkimuksen on aloittanut Zeigler 1990 -luvulla, ja prof. Kofman 2000 -luvulla ja tohtori Nutaro ovat selventäneet monia ominaisuuksia. Vuonna 2006 professori Cellier, joka on kirjoittanut jatkuvan järjestelmän mallinnuksen [Cellier91] , ja professori Kofman kirjoittivat oppikirjan Continuous System Simulation [CK06] , jossa luvut 11 ja 12 kattavat kuinka DEVS simuloi jatkuvia tilajärjestelmiä. Tohtori Nutaron kirja [Nutaro10] kattaa myös jatkuvien tilajärjestelmien erillisen tapahtumasimulaation.

Erillisten tapahtumajärjestelmien tarkistus

Vaihtoehtoisena analyysimenetelmänä näytteenottoon perustuvaa simulointimenetelmää vastaan DEVS-mallien analysoinnissa on käytetty kattavaa luovan käyttäytymisen lähestymistapaa, jota yleisesti kutsutaan todentamiseksi . On osoitettu, että tietyn DEVS-mallin äärettömät tilat (erityisesti kytketty DEVS-malli) voidaan abstraktoida käyttäytymis-isomorfisella äärellisellä rakenteella, jota kutsutaan saavutettavuuden kuvaajaksi, kun annettu DEVS-malli on DEVS: n alaluokka, kuten Schedule-Preserving DEVS ( SP-DEVS ), Finite & Deterministic DEVS ( FD-DEVS ) [HZ09] ja Finite & Real-time DEVS (FRT-DEVS) [Hwang12] . Tämän seurauksena palautettavuuskaavion perusteella (1) kuolleen lukituksen ja live-lukituksen vapaus laadullisina ominaisuuksina ovat ratkaistavissa SP-DEVS: llä [Hwang05] , FD-DEVS [HZ06] ja FRT-DEVS [Hwang12] ; ja (2) min/max käsittelyajan rajat kvantitatiivisena ominaisuutena ovat ratkaistavissa SP-DEVS: llä toistaiseksi vuoteen 2012 mennessä.

DEVS: n muunnelmia

Laajennukset (Superclassing)

Viime vuosikymmeninä on kehitetty lukuisia klassisen DEVS -muodon laajennuksia. Niistä muodollisuuksia, jotka mahdollistavat muuttuvan mallirakenteen simulaatioajan kehittyessä.

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

Rajoitukset (alaluokka)

Jotkin alaluokat tunnetaan nimellä Schedule-Preserving DEVS ( SP-DEVS ) ja Finite and Deterministic DEVS ( FD-DEVS ), jotka on nimetty tukemaan vahvistusanalyysiä. SP-DEVS ja FD-DEVS, joiden ekspressiivisyys on E ( SP-DEVS ) E ( FD-DEVS ) E (DEVS), jossa E ( formalismi ) tarkoittaa muodollisuuden ilmeikkyyttä .

Katso myös

DEVS -aiheiset artikkelit

Muut formalismit

Alaviitteet

  1. ^ automaatit olivat tohtori Zeiglerin tohtorin matemaattisia malleja. opinnäytetyö [Zeigler68]
  2. ^ Voimme myös määrittää ulkoisen siirtofunktio kuin, jossellainen, että yhteensä tilassa,on osittainen tila,on elinikä, jaon kulunut aika, koska viime päivitys on. Lisätietoja tämän toiminnon ymmärtämisestä on artikkelissa DEVS -käyttäytyminen .
  3. ^ ranskalainen insinööri kokeilikvantitettujen arvojen käyttöä jatkuvien järjestelmien simuloimiseksi erillisen tapahtumamenetelmän avulla empiirisesti muutama vuosi aikaisemmin - 1990 -luvun alussa<tarvitsemme viittauksia tähän väitteeseen>. Hän työskenteli silloin Valenciennesin yliopistosta irrotetussa yrityksessä , joka on nyt osa Schneider Electriciä . Tämä kvantisointi on ominaisuus simulaation ohjelmisto josta tämä insinööri on conceptor ja tärkein kehittäjä , jota käytetään PLC ohjelmien tarkistamiseen ja käyttökoulutus.

Viitteet

  • [Cellier91] Francois E. Cellier (1991). Jatkuva järjestelmän mallinnus (ensimmäinen ed.). Springer. ISBN 978-0-387-97502-3.
  • [CK06] Francois E. Cellier; Ernesto Kofman (2006). Jatkuva järjestelmän simulointi (ensimmäinen ed.). Springer. ISBN 978-0-387-26102-7.
  • [Giambiasi01] Giambiasi N., Escude B. Ghosh S. “Generalized Discrete Event Simulation of Dynamic Systems”, julkaisussa: Issue 4 of SCS Transactions: Recent Advances in DEVS Methodology-part II, Vol. 18, s. 216–229, joulukuu 2001
  • [Hwang05] MH Hwang, "Tutorial: Verification of Real-Time System based on Schedule-Preserved DEVS", Proceedings of 2005 DEVS Symposium , San Diego, 2.-8.4.2005, ISBN  1-56555-293-8 ,
  • [HZ06] MH Hwang ja BP Zeigler, "A Modular Verification Framework using Finite and Deterministic DEVS", Proceedings of 2006 DEVS Symposium , s. 57–65, Huntsville, Alabama, USA,
  • [HZ09] MH Hwang ja BP Zeigler, "Reachability Graph of Finite and Deterministic DEVS Networks", IEEE Transactions on Automation Science and Engineering , Volume 6, Issue 3, 2009, s.454–467,
  • [Hwang12] MH Hwang, "Quaitatiivinen tarkistus äärellisistä ja reaaliaikaisista DEVS -verkoista", Proceedings of the 2012 Symposium on Theory of Modeling and Simulation - DEVS Integrative M&S Symposium , Artikkeli 43,
  • [Mittal13] Saurabh Mittal; Jose L.Risco Martin (2013). Netcentric System of Systems Engineering ja DEVS Unified Process (ensimmäinen toim.). CRC Paina. ISBN 978-1439827062.
  • [Nutaro10] James Nutaro (2010). Rakennusohjelmisto simulointia varten: teoria, algoritmit ja sovellukset C ++: ssa (ensimmäinen toim.). Wiley. ISBN 0-470-41469-3.
  • [Sarjoughian09] Hessam S. Sarjoughian; Vignesh Elamvazhuthi (2009). "CoSMoS: Visuaalinen ympäristö komponenttipohjaiseen mallinnukseen, kokeelliseen suunnitteluun ja simulointiin". Simulaatiotyökaluja ja -tekniikoita käsittelevän kansainvälisen konferenssin artikkelit. Cite journal vaatii |journal=( apua )
  • [Wainer09] Gabriel A. Wainer (2009). Erillisten tapahtumien mallinnus ja simulointi: harjoittajan lähestymistapa (ensimmäinen toim.). CRC Paina. ISBN 978-1-4200-5336-4.
  • [Wainer10] Gabriel A. Wainer ja Pieter Mosterman Eds. (2010). Erillisten tapahtumien mallinnus ja simulointi: teoria ja sovellukset (ensimmäinen toim.). CRC Paina. ISBN 978-1-4200-7233-4.
  • [Zacharewicz08] Gregory Zacharewicz, Claudia Frydman ja Norbert Giambiasi (2008) G-DEVS/HLA Environment for Distributed Simulation of Workflows, SIMULATION Toukokuu 2008 84: 197-213, doi : 10.1177/0037549708092833 .
  • [Zeiger68] Bernard Zeigler (1968). Automaattien palautteen monimutkaisuudesta (väitöskirja toim.). Michiganin yliopisto.
  • [Zeigler76] Bernard Zeigler (1976). Mallintamisen ja simuloinnin teoria (ensimmäinen toim.). Wiley Interscience, New York. ISBN 0-12-778455-1.
  • [Zeigler84] Bernard Zeigler (1984). Monipuolinen mallinnus ja erillinen tapahtumasimulaatio . Academic Press, Lontoo; Orlando. ISBN 978-0-12-778450-2.
  • [Zeigler87] Bernard Zeigler (1987). "Hierarkkinen, modulaarinen erillinen tapahtumamallinnus olio-ympäristössä". Simulaatio . 49 (5): 219–230. doi : 10.1177/003754978704900506 .
  • [ZKP00] Bernard Zeigler; Tag Gon Kim; Herbert Praehofer (2000). Mallintamisen ja simuloinnin teoria (toinen painos). Academic Press, New York. ISBN 978-0-12-778455-7.