Ageing notions in the analysis of stochastic Petri nets

• Alterungseigenschaften in der Analyse stochastischer Petri-Netze

Alexin, Johann; Kamps, Udo (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2013)
Doktorarbeit

Aachen, Techn. Hochsch., Diss., 2012

Kurzfassung

In der vorliegenden Arbeit werden die stochastischen Petri-Netze mit beliebig verteilten Schaltzeiten bezüglich ihrer Alterungseigenschaften untersucht. Stochastische Alterungseigenschaften sind qualitative Eigenschaften einer Verteilungsfunktion. Ein Petri-Netz ist ein erweiterter gerichteter bipartiter Graph, mit dessen Hilfe verteilte Systeme modelliert werden. Eine Partition des Graphen enthält Stellen, die die lokalen Zustände eines Systems modellieren. Die andere Partition besteht aus Transitionen, die die Vorgänge in einem System modellieren. Eine Belegung der Stellen mit Token gibt den globalen Zustand des Petri-Netzes an und wird als Markierung bezeichnet. Jedes Petri-Netz hat eine Startmarkierung. Ist eine Transition in einer Markierung aktiv, so bewirkt das Schalten dieser Transition einen Markierungswechsel des Petri-Netzes. Wird jede Markierung höchstens einmal angenommen, so wird das Petri-Netz als azyklisch bezeichnet. In dieser Arbeit werden nur azyklische Petri-Netze untersucht. Solche Netze enthalten absorbierende Markierungen, in deren keine Transition aktiv ist. In den restlichen Markierungen ist mindestens eine Transition aktiv. Dabei ist eine Transition aktiv, wenn alle Inputstellen dieser Transition mindestens so viele Token enthalten, wie die Anzahl der gerichteten Kanten von der Inputstelle zu der Transition. Stochastische Petri-Netze stellen eine Erweiterung klassischer Petri-Netze dar. Wird eine zeitliche Transition in einem stochastischen Petri-Netz aktiviert, so verzögert sich das Schalten dieser Transition um eine zufällige Dauer. Diese zufällige Dauern werden durch stochastisch unabhängige und nicht-negative Zufallsvariablen modelliert und heißen Schaltzeiten. Azyklische stochastische Petri-Netze, die m Quellen und n Senken enthalten, werden als (m,n)-Netze bezeichnet. Dabei heißt eine Stelle Quelle, wenn von keiner Transition eine Kante zu dieser Stelle führt. Eine Stelle heißt Senke, wenn von dieser Stelle keine Kante zu einer Transition führt. Da nur (m,n)-Netze betrachtet werden, lässt sich die Zeitspanne zwischen der Startmarkierung und einer absorbierender Markierung als Zufallsvariable angeben. Dieses zufällige Zeitintervall wird als Gesamtzeit des (m,n)-Netzes bezeichnet. Die Gesamtzeit kann durch einen funktionalen Zusammenhang der Schaltzeiten aller Transitionen des (m,n)-Netzes beschrieben werden. Ausgehend von den Alterungseigenschaften der Verteilungsfunktionen einzelner Schaltzeiten, werden in der qualitativen Analyse die Alterungseigenschaften der Verteilungsfunktion von der Gesamtzeit untersucht. Um die Analysierbarkeit großer Netze zu gewährleisten wird ein modularer Zugang gewählt. Für den modularen Zugang werden erst sogenannte Bausteine festgelegt. Bausteine sind minimale (m,n)-Netze, die bestimmte Aktivitäten modellieren. Von den Bausteinen werden die Gesamtzeiten bestimmt. Anschließend wird die Übertragung der Alterungseigenschaften von der Transitionsebene auf die Bausteinebene untersucht. Nach der Untersuchung der Bausteine werden Mechanismen eingeführt, die das Verknüpfen der Bausteine zu größeren Netzen erlauben. Um diese Mechanismen systematisch einführen zu können, werden die modifizierten Bausteine eingeführt. Die Struktur dieser Bausteine unterscheidet sich leicht von den ursprünglichen Bausteinen, aber dieser Strukturunterschied wirkt sich nicht auf die Gesamtzeit aus. Dieses wird erreicht durch das Zulassen der zeitlosen Transitionen. Es werden zwei Verknüpfungsmechanismen definiert - Substitution und Expansion. Beim Verknüpfen zweier Bausteine durch Substitution wird eine zeitliche Transition in einem Baustein durch einen der Bausteine substituiert. Beim Verknüpfen zweier Bausteine durch Expansion, wird ein Baustein in eine Stelle des Anderen eingesetzt. Bei einigen Bausteinen lässt sich die Verknüpfung durch Expansion durch mehrfache Substitutionen beschreiben. Bei anderen Bausteinen bedarf es einer Einführung der Hilfskonstrukte für die konsequente Definition der Expansion. Die beiden Verknüpfungsmechanismen werden für jeden Baustein mit einem geeigneten (m,n)-Netz definiert, so dass das sukzessive Aufbauen größerer Netze möglich ist. Schließlich werden die beiden Verknüpfungsmechanismen bezüglich der Auswirkung auf die Alterungseigenschaften untersucht. In Abhängigkeit von der Struktur eines Bausteins, bleiben einige Alterungseigenschaften nach einer Verknüpfung erhalten, die Anderen werden schwächer oder gehen verloren. Letztendlich entsteht eine Klasse der (m,n)-Netze, deren Alterungseigenschaften ohne großen Aufwand ermittelbar sind. Die Verteilungsfunktion der Gesamtzeit der Netze außerhalb dieser Klasse bedarf aufwändiger Analyse.