DEVS - DEVS - Wikipedia

DEVS kısaltma Discrete Event System Specification Genel sistemlerin modellenmesi ve analiz edilmesi için modüler ve hiyerarşik bir formalizmdir. durum geçiş tabloları ve sürekli durum sistemleri tarafından tanımlanabilecek diferansiyel denklemler ve hibrit sürekli durum ve ayrık olay sistemleri. DEVS bir zamanlanmış olay sistemi.

Tarih

Ayrık Olay Sistem Spesifikasyonunu kısaltan DEVS, durum geçiş tabloları ile tanımlanabilen ayrık olay sistemleri ve diferansiyel denklemler ile tanımlanabilecek sürekli durum sistemleri ve hibrit sistemlerin modellenmesi ve analizi için modüler ve hiyerarşik bir formalizmdir ... DEVS, ayrık olay sistemlerinin (DES'ler) modellenmesi ve analizi için bir formalizmdir. DEVS biçimciliği tarafından icat edildi Bernard P. Zeigler, fahri profesör olan Arizona Üniversitesi. DEVS, Zeigler'in ilk kitabında halka tanıtıldı, Modelleme ve Simülasyon Teorisi, 1976'da Zeigler, 1976'da doçent iken Michigan üniversitesi. DEVS, Moore makinesi biçimcilik[1] bu, çıkışların yalnızca mevcut durum tarafından belirlendiği (ve doğrudan girişe bağlı olmadığı) sonlu bir durum otomatıdır. Uzantı tarafından yapıldı

  1. her eyaletle bir ömür ilişkilendirmek [Zeigler76],
  2. adı verilen bir işlemle hiyerarşik bir kavram sağlamak bağlantı [Zeigler84].

Her durumun ömrü gerçek bir sayı (daha doğrusu, negatif olmayan gerçek) veya sonsuz olduğundan, ayrık zamanlı sistemlerden, sıralı makinelerden ve Moore makineleri, burada zaman, negatif olmayan tam sayılarla çarpılan bir tik zamanıyla belirlenir. Üstelik yaşam süresi bir rastgele değişken; örneğin, belirli bir devletin ömrü dağıtılabilir üssel olarak veya tekdüze. DEVS'in durum geçişi ve çıktı işlevleri de stokastik.

Zeigler, 1984'te DEVS model simülasyonu için hiyerarşik bir algoritma önerdi [Zeigler84] hangi yayınlandı Simülasyon O zamandan beri, DEVS'den birçok genişletilmiş biçimcilik kendi amaçları ile tanıtıldı: Birleşik sürekli ve ayrık olay sistemleri için DESS / DEVS, paralel DES'ler için P-DEVS, DES'lerin parça parça sürekli durum yörünge modellemesi için G-DEVS, Gerçek zamanlı DES'ler için RT-DEVS, hücresel DES'ler için Cell-DEVS, fuzzy DES'ler için Fuzzy-DEVS, kuplaj yapılarını dinamik olarak değiştiren DES'ler için Dinamik Yapılandırma DEVS, vb. Uzantılarına ek olarak, gibi bazı alt sınıflar da vardır. SP-DEVS ve FD-DEVS sistem özelliklerinin karar verilebilirliğini sağlamak için araştırılmıştır.

Modüler ve hiyerarşik modelleme görünümlerinin yanı sıra simülasyon tabanlı analiz yeteneği nedeniyle, DEVS formalizmi ve varyasyonları birçok mühendislik uygulamasında (donanım tasarımı, donanım / yazılım kod işareti, iletişim sistemleri, imalat sistemler) ve bilim (örneğin Biyoloji, ve sosyoloji )

Biçimcilik

Şekil 1. Ping-Pong Oyunu için DEVS Modeli
Sezgisel Örnek

DEVS, sistem yapısının yanı sıra sistem davranışını da tanımlar. DEVS biçimciliğindeki sistem davranışı, giriş ve çıkış olaylarının yanı sıra durumlar kullanılarak tanımlanır. Örneğin, Şekil 1'deki pinpon oyuncusu için giriş olayı ?teslim almakve çıktı olayı gönder. Her bir oyuncu, Bir, B, durumlarına sahiptir: Gönder ve Bekle. Gönder durum çıkış olayı olan topu geri göndermek için 0,1 saniye sürer gönderiken Bekle durumu oyuncu giriş olayı olan topu alana kadar sürer ?teslim almak.

Ping-pong oyununun yapısı iki oyuncuyu birbirine bağlamaktır: Oyuncu Bir çıkış etkinliği gönder Oyuncuya iletildi B giriş etkinliği ?teslim almakve tam tersi.

Klasik DEVS biçimciliğinde, Atomik DEVS sistem davranışını yakalarken Birleştirilmiş DEVS Sistemin yapısını açıklar.

Aşağıdaki resmi tanım Klasik DEVS içindir [ZKP00]. Bu yazıda zaman tabanını kullanacağız, bu, negatif olmayan gerçek sayılar kümesidir; genişletilmiş zaman tabanı, bu, negatif olmayan gerçek sayılar artı sonsuzdur.

Atomik DEVS

Atomik DEVS modeli, 7-demet

nerede

  • dır-dir giriş olayları kümesi;
  • dır-dir çıktı olayları kümesi;
  • dır-dir sıralı durumlar kümesi (veya aynı zamanda kısmi durumlar kümesi);
  • dır-dir ilk durum;
  • dır-dir zaman ilerletme işlevi bir devletin ömrünü belirlemek için kullanılan;
  • dır-dir dış geçiş işlevi bir giriş olayının sistemin durumunu nasıl değiştirdiğini tanımlayan ... toplam durum kümesi, ve ... geçen zaman dan beri son olay;

[2]


  • dır-dir iç geçiş işlevi sistemin bir durumunun dahili olarak nasıl değiştiğini tanımlayan (geçen süre, durumun yaşam süresine ulaştığında);
  • dır-dir çıktı işlevi nerede ve bir sessiz olay veya bir gözlenmemiş Etkinlik. Bu işlev, sistemin bir durumunun bir çıktı olayını nasıl oluşturduğunu tanımlar (geçen süre, durumun yaşam süresine ulaştığında);
Ping-Pong Oyuncuları için atomik DEVS Modeli

Şekil 1'deki A oyuncusu için atomik DEVS modeli verilmiştir. Oyuncu = öyle ki

Hem Oyuncu A hem de Oyuncu B atomik DEVS modelleridir.

Atomik DEVS Davranışı

Basitçe söylemek gerekirse, atomik bir DEVS modelinin durumunu değiştirebilir : (1) harici bir giriş sisteme gelir ; (2) geçen zaman ömrüne ulaşır tarafından tanımlanan . ((2) ile aynı zamanda, bir çıktı üretir tarafından tanımlanan .) .

Verilen bir Atomik DEVS modelinin biçimsel davranış açıklaması için, sayfaya bakın DEVS Davranışı. Belirli bir Atomik DEVS modelinin davranışını uygulamak için bilgisayar algoritmaları şu adreste mevcuttur: Atomik DEVS için Simülasyon Algoritmaları.

Birleştirilmiş DEVS

Birleştirilmiş DEVS, hangi alt bileşenlerin kendisine ait olduğunu ve birbirlerine nasıl bağlandıklarını tanımlar. Birleştirilmiş DEVS modeli, 8-demet

nerede

  • dır-dir giriş olayları kümesi;
  • dır-dir çıktı olayları kümesi;
  • dır-dir alt bileşenlerin ad grubu;
  • dır-dir alt bileşenler kümesi her biri için nerede bir atomik DEVS modeli veya bir bağlı DEVS modeli olabilir.
  • dır-dir harici giriş kaplinleri seti;
  • dır-dir iç bağlantı seti;
  • dır-dir harici çıkış bağlantı fonksiyonu;
  • dır-dir bağ bozma işlevi eşzamanlı olaylar dizisinden olayın nasıl seçileceğini tanımlayan;
Ping-Pong Oyunu için birleştirilmiş DEVS modeli

Şekil 1'deki masa tenisi oyunu, bağlı bir DEVS modeli olarak modellenebilir. nerede ;;; yukarıda anlatıldığı gibi; ; ; ve .

Birleştirilmiş DEVS Davranışı

Basitçe söylemek gerekirse, atomik DEVS sınıfının davranışı gibi, bağlı bir DEVS modeli harici bir olay olduğunda bileşenlerinin durumlarını (1) değiştirir içeri girer ; (2) bileşenlerden biri nerede dahili durum geçişini yürütür ve çıktısını üretir . Her iki durumda (1) ve (2), bir tetikleme olayı, kuplaj kümeleri tarafından tanımlanan tüm etkilere iletilir. ve .

Birleştirilmiş DEVS'nin davranışının resmi tanımı için, Birleştirilmiş DEVS Davranışı. Belirli bir bağlı DEVS modunun davranışını uygulamak için bilgisayar algoritmaları şu adreste mevcuttur: Birleştirilmiş DEVS için Simülasyon Algoritmaları.

Analiz Yöntemleri

Ayrık Olay Sistemleri için Simülasyon

DEVS modellerinin simülasyon algoritması iki konuyu ele alır: zaman senkronizasyonu ve mesaj yayılımı. Zaman senkronizasyonu DEVS, tüm modelleri aynı geçerli zamana sahip olacak şekilde kontrol etmektir. Bununla birlikte, verimli bir yürütme için, algoritma, bir olayın kendi iç durum geçişini ve çıktı üretimini yürütmek üzere programlandığı zaman, mevcut zamanın en acil zamana sıçramasını sağlar. Mesaj yayılımı bağlı bir DEVS modelinde tanımlanan ilişkili bağlantılar boyunca bir girdi veya çıktı olayı olabilen bir tetikleme mesajını iletmektir. Daha ayrıntılı bilgi için okuyucu, Atomik DEVS için Simülasyon Algoritmaları ve Birleştirilmiş DEVS için Simülasyon Algoritmaları.

Sürekli Durum Sistemleri için Simülasyon

Sürekli bir segmenti parçalı bir sabit segment olarak özetleyen bir niceleme yöntemi sunarak, DEVS, aşağıdaki ağlar tarafından tanımlanan sürekli durum sistemlerinin davranışlarını simüle edebilir. diferansiyel cebirsel denklemler. Bu araştırma 1990'larda Zeigler tarafından başlatılmıştır.[3] 2000'li yıllarda Prof. Kofman ve Dr. Nutaro tarafından birçok özellik netleştirilmiştir. 2006 yılında, yazarı Prof. Sürekli Sistem Modellemesi[Cellier91] ve Prof. Kofman bir ders kitabı yazdı, Sürekli Sistem Simülasyonu[CK06] Bölüm 11 ve 12, DEVS'in sürekli durum sistemlerini nasıl simüle ettiğini ele almaktadır. Dr. Nutaro'nun kitabı [Nutaro10], sürekli durum sistemlerinin ayrık olay simülasyonunu da kapsar.

Ayrık Olay Sistemleri için Doğrulama

Örneklemeye dayalı simülasyon yöntemine karşı alternatif bir analiz yöntemi olarak, genel olarak adlandırılan kapsamlı bir oluşturma davranışı yaklaşımı doğrulama DEVS modellerinin analizi için uygulanmıştır. Belirli bir DEVS modelinin (özellikle bağlı bir DEVS modelinin) sonsuz durumlarının, a adı verilen davranışsal olarak izomorfik sonlu yapı ile soyutlanabileceği kanıtlanmıştır. ulaşılabilirlik grafiği Verilen DEVS modeli, Zamanlama Korumalı DEVS gibi bir DEVS alt sınıfı olduğunda (SP-DEVS ), Sonlu ve Belirleyici DEVS (FD-DEVS ) [HZ09] ve Sonlu ve Gerçek Zamanlı DEVS (FRT-DEVS) [Hwang12]. Sonuç olarak, yeniden değiştirilebilirlik grafiğine göre, (1) kilitlenme ve canlı kilit serbestliği, niteliksel özellikler olarak SP-DEVS ile karar verilebilir [Hwang05], FD-DEVS [HZ06] ve FRT-DEVS [Hwang12]; ve (2) nicel bir özellik olarak min / maks işlem süresi sınırları, şu ana kadar 2012 yılına kadar SP-DEVS ile kararlaştırılabilir.

DEVS çeşitleri

Uzantılar (Süper Sınıflandırma)

Son yıllarda klasik DEVS biçimciliğinin sayısız uzantıları geliştirilmiştir ve bunlar arasında simülasyon zamanı gelişirken değişen model yapılarına sahip olmaya izin veren biçimcilikler geliştirilmiştir.

G-DEVS [Giambiasi01] [Zacharewicz08], Paralel DEVS, Dinamik Yapılandırma DEVS, Hücre-DEVS [Wainer09], dynDEVS, Fuzzy-DEVS, GK-DEVS, ml-DEVS, Symbolic DEVS, Real-Time DEVS, rho-DEVS

Kısıtlamalar (Alt Sınıflandırma)

Zamanlamayı Koruyan DEVS olarak bilinen bazı alt sınıflar vardır (SP-DEVS ) ve Sonlu ve Deterministik DEVS (FD-DEVS ) doğrulama analizini desteklemek için belirlenmiş olanlar.SP-DEVS ve FD-DEVS kimin ifadesi E(SP-DEVS ) E(FD-DEVS ) E(DEVS) nerede E(biçimcilik) ifade gücünü gösterir biçimcilik.

Ayrıca bakınız

DEVS ile İlgili Makaleler

Diğer Biçimler

Dipnotlar

  1. ^ otomata, Dr. Zeigler'in Ph.D.'nin matematiksel modelleriydi. tez [Zeigler68]
  2. ^ Dış geçiş işlevini şu şekilde de tanımlayabiliriz: nerede öyle ki bütün bir durum için , kısmi bir durumdur ömrü , ve o zamandan beri geçen süredir son Güncelleme nın-nin . Bu işlevi nasıl anlayacağınızla ilgili daha fazla bilgi için şu makaleye bakın: DEVS Davranışı.
  3. ^ sürekli sistemleri simüle etmek için nicelleştirilmiş değerlerin kullanılması ayrık olay yöntem deneysel olarak birkaç yıl önce denendi - 1990'ların başında - Fransızca mühendis . Daha sonra bir şirket için çalışıyordu. Valenciennes Üniversitesi ve şimdi bir parçası Schneider Elektrik. Bu niceleme bir özelliğidir simülasyon yazılım bu mühendisin fikir babası ve ana geliştirici, bunun için kullanılır PLC programları kontrol etme ve operatör eğitimi.

Referanslar

  • [Cellier91] Francois E. Cellier (1991). Sürekli Sistem Modellemesi (ilk baskı). Springer. ISBN  978-0-387-97502-3.
  • [CK06] Francois E. Cellier; Ernesto Kofman (2006). Sürekli Sistem Simülasyonu (ilk baskı). Springer. ISBN  978-0-387-26102-7.
  • [Giambiasi01] Giambiasi N., Escude B. Ghosh S. "Dinamik Sistemlerin Genelleştirilmiş Ayrık Olay Simülasyonu", içinde: SCS İşlemlerinin 4. Sayısı: DEVS Metodolojisindeki Son Gelişmeler-bölüm II, Cilt. 18, sayfa 216–229, aralık 2001
  • [Hwang05] M.H. Hwang, "Eğitim: Programla Korunan DEVS'e Dayalı Gerçek Zamanlı Sistemin Doğrulanması", 2005 DEVS Sempozyumu Bildirileri, San Diego, 2-8 Nisan 2005, ISBN  1-56555-293-8,
  • [HZ06] M.H. Hwang ve B. P. Zeigler, "Sonlu ve Belirleyici DEVS Kullanan Modüler Doğrulama Çerçevesi", 2006 DEVS Sempozyumu Bildirileri, pp57–65, Huntsville, Alabama, ABD,
  • [HZ09] M.H. Hwang ve B.P. Zeigler, "Sonlu ve Belirleyici DEVS Ağlarının Erişilebilirlik Grafiği", Otomasyon Bilimi ve Mühendisliğinde IEEE İşlemleri, Cilt 6, Sayı 3, 2009, s. 454–467,
  • [Hwang12] M.H. Hwang, "Sonlu ve gerçek zamanlı DEVS ağlarının nitel doğrulaması", 2012 Modelleme ve Simülasyon Teorisi Sempozyumu Bildirileri - DEVS Bütünleştirici M&S Sempozyumu43. madde,
  • [Mittal13] Saurabh Mittal; Jose L. Risco Martin (2013). DEVS Unified Process ile Netcentric Sistem Mühendisliği Sistemi (ilk baskı). CRC Basın. ISBN  978-1439827062.
  • [Nutaro10] James Nutaro (2010). Simülasyon için Yazılım Geliştirme: C ++ 'da Teori, Algoritmalar ve Uygulamalar (ilk baskı). Wiley. ISBN  0-470-41469-3.
  • [Sarjoughian09] Hessam S. Sarjoughian; Vignesh Elamvazhuthi (2009). "CoSMoS: Bileşen Tabanlı Modelleme, Deneysel Tasarım ve Simülasyon için Görsel Bir Ortam". Uluslararası Simülasyon Araçları ve Teknikleri Konferansı Bildirileri. Alıntı dergisi gerektirir | günlük = (Yardım)
  • [Wainer09] Gabriel A. Wainer (2009). Ayrık Olay Modelleme ve Simülasyon: Bir Uygulayıcının Yaklaşımı (ilk baskı). CRC Basın. ISBN  978-1-4200-5336-4.
  • [Wainer10] Gabriel A. Wainer ve Pieter Mosterman Eds. (2010). Kesikli Olay Modelleme ve Simülasyon: Teori ve Uygulamalar (ilk baskı). CRC Basın. ISBN  978-1-4200-7233-4.
  • [Zacharewicz08] Gregory Zacharewicz, Claudia Frydman ve Norbert Giambiasi (2008) İş Akışlarının Dağıtılmış Simülasyonları için G-DEVS / HLA Ortamı, SİMÜLASYON Mayıs 2008 84: 197-213, doi: 10.1177 / 0037549708092833.
  • [Zeiger68] Bernard Zeigler (1968). Otomata'nın Geri Bildirim Karmaşıklığı Üzerine (Doktora Tezi ed.). Michigan üniversitesi.
  • [Zeigler76] Bernard Zeigler (1976). Modelleme ve Simülasyon Teorisi (ilk baskı). Wiley Interscience, New York. ISBN  0-12-778455-1.
  • [Zeigler84] Bernard Zeigler (1984). Çok Yönlü Modelleme ve Kesikli Olay Simülasyonu. Academic Press, Londra; Orlando. ISBN  978-0-12-778450-2.
  • [Zeigler87] Bernard Zeigler (1987). "Nesne yönelimli bir ortamda hiyerarşik, modüler ayrık olay modelleme". Simülasyon. 49 (5): 219–230. doi:10.1177/003754978704900506.
  • [ZKP00] Bernard Zeigler; Tag Gon Kim; Herbert Praehofer (2000). Modelleme ve Simülasyon Teorisi (ikinci baskı). Academic Press, New York. ISBN  978-0-12-778455-7.