DEVS - DEVS

A DEVS a Discrete Event System Specification rövidítése egy moduláris és hierarchikus formalizmus olyan általános rendszerek modellezésére és elemzésére, amelyek lehetnek diszkrét eseményrendszerek, amelyeket állapotátmeneti táblázatok írhatnak le , és folyamatos állapotrendszerek, amelyeket differenciálegyenletek írhatnak le , valamint hibrid folyamatos állapot és diszkrét eseményrendszerek. A DEVS egy időzített eseményrendszer .

Történelem

A DEVS a Discrete Event System Specification rövidítése egy moduláris és hierarchikus formalizmus olyan általános rendszerek modellezésére és elemzésére, amelyek lehetnek diszkrét eseményrendszerek, amelyeket állapotátmeneti táblázatok írhatnak le, és folyamatos állapotrendszerek, amelyeket differenciálegyenletek írhatnak le, és hibrid ... A DEVS formalizmus a diszkrét eseményrendszerek (DES) modellezésére és elemzésére. A DEVS formalizmusát Bernard P. Zeigler , az Arizonai Egyetem emeritus professzora találta ki . A DEVS -t Zeigler első könyvében, a Modellezés és szimuláció elmélete 1976 -ban mutatta be a nagyközönségnek , míg Zeigler a Michigani Egyetem docense volt . A DEVS a Moore -gépi formalizmus kiterjesztésének tekinthető , amely egy véges állapotú automatika, ahol a kimeneteket egyedül az aktuális állapot határozza meg (és nem közvetlenül függnek a bemenettől). A kiterjesztést elvégezte

  1. az egyes államok élettartamának társítása [Zeigler76] ,
  2. hierarchikus koncepciót biztosít egy műveletnek, az úgynevezett csatolásnak [Zeigler84] .

Mivel az egyes állapotok élettartama valós szám (pontosabban, nem negatív valós) vagy végtelen, megkülönböztethető a diszkrét időrendszerektől, a szekvenciális gépektől és a Moore-gépektől , amelyekben az időt egy kullancsidő határozza meg, megszorozva nem negatív egész számok. Ezenkívül az élettartam lehet egy véletlen változó ; például egy adott állapot élettartama exponenciálisan vagy egyenletesen oszlik meg . A DEVS állapotátmeneti és kimeneti funkciói is sztochasztikusak lehetnek .

Zeigler 1984 -ben javasolt egy hierarchikus algoritmust a DEVS modellszimulációhoz [Zeigler84], amelyet 1987 -ben publikáltak a Simulation folyóiratban. Azóta a DEVS számos kiterjesztett formalizmust vezetett be saját céljaival: DESS/DEVS kombinált folyamatos és diszkrét eseményrendszerekhez, P-DEVS a párhuzamos DES-ekhez, G-DEVS a DES-ek darabonkénti folyamatos állapotú pályamodellezéséhez, RT-DEVS a valós idejű DES-ekhez, Cell-DEVS a cellás DES-ekhez, Fuzzy-DEVS a fuzzy DES-ekhez, Dinamikus strukturáló DEVS a DES-ekhez, amelyek dinamikusan megváltoztatják a tengelykapcsoló szerkezetüket , stb. A kiterjesztéseken kívül néhány alosztályt is vizsgáltak, mint például az SP-DEVS és az FD-DEVS a rendszertulajdonságok eldönthetőségének elérése érdekében.

A moduláris és hierarchikus modellezési nézeteknek, valamint a szimuláción alapuló elemzési képességének köszönhetően a DEVS formalizmusát és annak variációit számos mérnöki alkalmazásban alkalmazták (például hardvertervezés, hardver/szoftver kódjel, kommunikációs rendszerek , gyártási rendszerek) és tudomány (például biológia és szociológia )

Formalizmus

1. ábra. A DEVS modell ping-pong játékhoz
Intuitív példa

A DEVS meghatározza a rendszer viselkedését és a rendszer felépítését. A rendszer viselkedését a DEVS formalizmusában bemeneti és kimeneti események, valamint állapotok segítségével írják le. Például az 1. ábrán látható ping-pong lejátszó esetén a bemeneti esemény ? Fogadás , a kimeneti esemény pedig küldés . Minden játékos, A , B , rendelkezik a következő állapotokkal: Küldés és Várás . A küldési állapot 0,1 másodpercet vesz igénybe, hogy visszaküldje a labdát, amely a kimeneti esemény ! Küldje el , míg a Várakozás állapot addig tart, amíg a játékos meg nem kapja a bemeneti eseményként kapott labdát ? Fogadni .

A szerkezet a ping-pong játék lényege, hogy csatlakoztassa a két játékos: Player A „s kimeneti esemény ! Send továbbítjuk Player B ” s bemeneti esemény ? Kap , és fordítva.

A klasszikus DEVS formalizmusban az Atomic DEVS rögzíti a rendszer viselkedését, míg a Coupled DEVS a rendszer felépítését írja le.

A következő formális meghatározás a Classic DEVS [ZKP00] . Ebben a cikkben az időalapot fogjuk használni, vagyis a nem negatív valós számok halmazát; a meghosszabbított bázis, azaz a nem negatív valós számok és a végtelen halmaza.

Atomi DEVS

Az atomi DEVS modell 7-es tuple- ként van definiálva

ahol

  • van a beállított bemeneti eseményeket ;
  • van a beállított kimeneti események ;
  • van a készlet szekvenciális Államok (vagy más néven a beállított részleges Államok );
  • van a kezdeti állapotban ;
  • az az idő előre funkció , amely segítségével meghatározható az élettartama egy állam;
  • a külső átmeneti függvény , amely meghatározza, hogy egy bemeneti esemény megváltoztatja a rendszer állapotát, ahol a készlet teljes állapotok , és az eltelt idő óta az utolsó esemény ;


  • a belső átalakulás funkció , amely meghatározza, hogy az állam a rendszer megváltoztatja belül (ha az eltelt idő eléri a élettartama az állam);
  • a kimeneti függvény , ahol és egy csendes esemény vagy egy észrevétlen esemény. Ez a funkció határozza meg, hogy a rendszer állapota hogyan generál kimeneti eseményt (amikor az eltelt idő eléri az állapot élettartamát);
Atomi DEVS modell ping-pong játékosok számára

Az 1. ábra A játékos atomi DEVS modellje a Player = olyan, hogy

Mind az A, mind a B játékos atomi DEVS modellek.

Az Atomic DEVS viselkedése

Egyszerűen szólva két eset áll fenn, amikor egy atomi DEVS modell megváltoztathatja állapotát : (1) amikor egy külső bemenet érkezik a rendszerbe ; (2) amikor az eltelt idő eléri annak élettartamát, amelyet a . (A (2) ponttal egy időben egy kimenetet generál, amelyet a. Definiál .).

Az Atomic DEVS modell hivatalos viselkedésleírását a DEVS viselkedése oldalon találja . Számítógépes algoritmusok az adott Atomic DEVS modell viselkedésének megvalósításához állnak rendelkezésre az Atomic DEVS szimulációs algoritmusainál .

Csatolt DEVS

A csatolt DEVS határozza meg, hogy mely részkomponensek tartoznak hozzá, és hogyan kapcsolódnak egymáshoz. A kapcsolt DEVS modellt úgy definiáljuk, mint egy 8- tuple

ahol

  • van a beállított bemeneti eseményeket ;
  • van a beállított kimeneti események ;
  • az a neve készlet szubkomponenseket ;
  • a részkomponensek halmaza, ahol mindegyik lehet egy atomi DEVS-modell vagy egy csatolt DEVS-modell.
  • van a készlet külső bemeneti csatlakozók ;
  • van a sor belső tengelykapcsolók ;
  • van a külső kimeneti kapcsoló funkció ;
  • van a tie-breaking funkció , amely meghatározza, hogy hogyan válasszuk ki az eseményt a beállított kísérőesemények;
A csatolt DEVS modell ping-pong játékhoz

Ábra ping-pongjátéka modellezhető egy csatolt DEVS modellként, ahol ; ; ; a fentiek szerint van leírva; ; ; és .

A párosított DEVS viselkedése

Egyszerűen szólva, mint a viselkedése az atomi DEVS osztály, a kapcsolt DEVS modell megváltozik komponensek államok (1) ha egy külső esemény kerül ; (2), amikor az egyik komponens , ahol végrehajtja a belső állapotát átmenet és generál annak kimenete . Mindkét (1) és (2) esetben egy kiváltó eseményt továbbítanak minden befolyásolónak, amelyeket csatoló készletek és .

Az összekapcsolt DEVS viselkedésének hivatalos meghatározásához olvassa el a Coupled DEVS viselkedése című részt . Számítógépes algoritmusok az adott csatolt DEVS mód viselkedésének megvalósítására állnak rendelkezésre a Simulált algoritmusok a csatolt DEVS -hez oldalon .

Elemzési módszerek

Szimuláció diszkrét eseményrendszerekhez

A DEVS modellek szimulációs algoritmusa két kérdést vesz figyelembe: az időszinkronizálást és az üzenetterjesztést. A DEVS időszinkronizálása azt jelenti, hogy minden modell azonos időzítéssel rendelkezik. A hatékony végrehajtás érdekében azonban az algoritmus a jelenlegi időt a legsürgősebb időpontra ugrja, amikor egy esemény a belső állapotátmenet és a kimeneti generálás végrehajtására van ütemezve. Az üzenetterjesztés egy kiváltó üzenetet továbbít, amely lehet bemeneti vagy kimeneti esemény a kapcsolódó csatolások mentén, amelyek egy csatolt DEVS modellben vannak definiálva. További részletes információkat az olvasó utalhat szimulációs algoritmusok Atomic DEVS és szimulációs algoritmusok Áthajtott DEVS .

Szimuláció folyamatos állapotrendszerekhez

Egy olyan kvantálási módszer bevezetésével, amely egy folyamatos szegmenst darabonkénti konstans szegmensként von el, a DEVS szimulálni tudja a folytonos állapotú rendszerek viselkedését, amelyeket differenciális algebrai egyenletek hálózata ír le . Ezt a kutatást Zeigler kezdeményezte az 1990 -es években, és számos tulajdonságot tisztázott Kofman professzor a 2000 -es években és Dr. Nutaro. 2006 -ban Cellier professzor, aki a Folyamatos rendszermodellezés [Cellier91] szerzője , és Kofman professzor írt egy tankönyvet, a Folyamatos rendszerszimuláció [CK06] , amelyben a 11. és 12. fejezet foglalkozik azzal, hogy a DEVS hogyan szimulálja a folyamatos állapotrendszereket. Dr. Nutaro könyve [Nutaro10] kiterjed a folyamatos állapotrendszerek diszkrét eseményszimulációjára is.

Ellenőrzés diszkrét eseményrendszerekhez

A mintavételezésen alapuló szimulációs módszerrel szemben alternatív elemzési módszerként a DEVS modellek elemzéséhez kimerítő generáló viselkedési megközelítést alkalmaztak, amelyet általában verifikációnak neveznek . Bebizonyosodott, hogy egy adott DEVS-modell végtelen állapotai (különösen a kapcsolt DEVS-modell) elviselhetők viselkedési izomorf véges struktúrával, amelyet elérhetőségi gráfnak neveznek, ha az adott DEVS-modell a DEVS egyik alosztálya, például a menetrend-megőrző DEVS ( SP-DEVS ), véges és determinisztikus DEVS ( FD-DEVS ) [HZ09] és véges és valós idejű DEVS (FRT-DEVS) [Hwang12] . Ennek eredményeképpen a visszanyerhetőségi grafikon alapján (1) a holt- és az élő zárolás szabadsága, mint minőségi tulajdonságok eldönthetők az SP-DEVS [Hwang05] , az FD-DEVS [HZ06] és az FRT-DEVS [Hwang12] segítségével ; és (2) a min/max feldolgozási időkeret mennyiségi tulajdonságként 2012-ig eldönthető az SP-DEVS segítségével.

A DEVS variációi

Bővítmények (szuperosztályozás)

A klasszikus DEVS formalizmus számos kiterjesztését fejlesztették ki az elmúlt évtizedekben. Közöttük formalizmusok, amelyek lehetővé teszik a modellstruktúrák változását, miközben a szimulációs idő alakul.

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

Korlátozások (alosztályozás)

Vannak olyan alosztályok, amelyeket ütemtervmegőrző DEVS ( SP-DEVS ) és véges és determinisztikus DEVS ( FD-DEVS ) néven ismernek, amelyeket a hitelesítési elemzés támogatására jelöltek ki. SP-DEVS és FD-DEVS, amelyek kifejezőképessége E ( SP-DEVS ) E ( FD-DEVS ) E (DEVS), ahol E ( formalizmus ) a formalizmus kifejezőképességét jelöli .

Lásd még

DEVS kapcsolódó cikkek

Egyéb formalizmusok

Lábjegyzetek

  1. ^ automaták voltak Dr. Zeigler Ph.D. matematikai modelljei. tézis [Zeigler68]
  2. ^ Azt is meghatározza a külső átmeneti függvény, ahololyan, hogy egy teljes állami,egy részleges állapotban,a élettartama, ésaz eltelt idő óta Utolsó frissítés a. Ha többet szeretne megtudni erről a funkcióról, olvassa el a DEVS viselkedése című cikket.
  3. ^ a kvantált értékek használatát a folyamatos rendszerek szimulációjához diszkrét esemény módszerrel néhány évvel hamarabb - a kilencvenes évek elején - empirikusan kipróbálta egy francia mérnök <Bármilyen hivatkozásra van szükségünk ehhez az érvhez>. Ekkor a Valenciennes -i Egyetemről leválasztott cégnél dolgozott, és jelenleg a Schneider Electric része. Ez a kvantálás egy olyan szimulációs szoftver jellemzője , amelynek ez a mérnöke a tervezője és fő fejlesztője , és amelyet a PLC programok ellenőrzésére ésa kezelőképzésrehasználnak.

Hivatkozások

  • [Cellier91] Francois E. Cellier (1991). Folyamatos rendszermodellezés (első szerk.). Springer. ISBN 978-0-387-97502-3.
  • [CK06] Francois E. Cellier; Ernesto Kofman (2006). Folyamatos rendszerszimuláció (első szerk.). Springer. ISBN 978-0-387-26102-7.
  • [Giambiasi01] Giambiasi N., Escude B. Ghosh S. „Generalized Discrete Event Simulation of Dynamic Systems”, in: SCS Transactions 4. Issue: Recent Advances in DEVS Methodology-part II, Vol. 18, 216–229, 2001. dec
  • [Hwang05] MH Hwang, "Tutorial: Verification of Real-time System based on Schedule-Preserved DEVS", Proceedings of 2005 DEVS Symposium , San Diego, 2005. április 2-8., ISBN  1-56555-293-8 ,
  • [HZ06] MH Hwang és BP Zeigler, "A Modular Verification Framework using Finite and Deterministic DEVS", Proceedings of 2006 DEVS Symposium , pp57-65, Huntsville, Alabama, USA,
  • [HZ09] MH Hwang és BP Zeigler, "Reachability Graph of Finite and Deterministic DEVS Networks", IEEE Transactions on Automation Science and Engineering , 6. kötet, 3. szám, 2009., 454–467.
  • [Hwang12] MH Hwang, "A véges és valós idejű DEVS hálózatok minőségi ellenőrzése", A modellezés és szimuláció elméletéről szóló 2012 -es szimpózium folyóirata - DEVS Integrative M&S Symposium , 43. cikk,
  • [Mittal13] Saurabh Mittal; Jose L. Risco Martin (2013). Netcentrikus rendszermérnöki rendszer DEVS Unified Process -el (első szerk.). CRC Press. ISBN 978-1439827062.
  • [Nutaro10] James Nutaro (2010). Szoftverépítés szimulációhoz: elmélet, algoritmusok és alkalmazások C ++ nyelven (első szerk.). Wiley. ISBN 0-470-41469-3.
  • [Sarjoughian09] Hessam S. Sarjoughian; Vignesh Elamvazhuthi (2009). "CoSMoS: vizuális környezet komponens alapú modellezéshez, kísérleti tervezéshez és szimulációhoz". Szimulációs eszközök és technikák nemzetközi konferenciájának előadásai. Az idézetnapló igényel |journal=( segítséget )
  • [Wainer09] Gabriel A. Wainer (2009). Diszkrét események modellezése és szimulációja: Gyakorló megközelítése (első szerk.). CRC Press. ISBN 978-1-4200-5336-4.
  • [Wainer10] Gabriel A. Wainer és Pieter Mosterman Eds. (2010). Diszkrét események modellezése és szimulációja: elmélet és alkalmazások (első szerk.). CRC Press. ISBN 978-1-4200-7233-4.
  • [Zacharewicz08] Gregory Zacharewicz, Claudia Frydman és Norbert Giambiasi (2008) G-DEVS/HLA Environment for Distributed Simulations of Workflows, SIMULATION 2008. május 84: 197-213, doi : 10.1177/0037549708092833 .
  • [Zeiger68] Bernard Zeigler (1968). Az automaták visszacsatolási komplexitásáról (Ph.D. Thesis szerk.). Michigani Egyetem.
  • [Zeigler76] Bernard Zeigler (1976). A modellezés és szimuláció elmélete (első szerk.). Wiley Interscience, New York. ISBN 0-12-778455-1.
  • [Zeigler84] Bernard Zeigler (1984). Többoldalú modellezés és diszkrét eseményszimuláció . Academic Press, London; Orlando. ISBN 978-0-12-778450-2.
  • [Zeigler87] Bernard Zeigler (1987). "Hierarchikus, moduláris diszkrét eseménymodellezés objektum-orientált környezetben". Szimuláció . 49. (5): 219–230. doi : 10.1177/003754978704900506 .
  • [ZKP00] Bernard Zeigler; Címke Gon Kim; Herbert Praehofer (2000). Modellezés és szimuláció elmélete (második szerk.). Academic Press, New York. ISBN 978-0-12-778455-7.