G -Network – Wikipedia wiki

In der Warteschlangentheorie eine Disziplin innerhalb der mathematischen Wahrscheinlichkeitstheorie, a G-Netzwerk ( Verallgemeinerte Warteschlangennetzwerk Anwesend ^{[Erste] [2]} oft als a genannt Gelenbe -Netzwerk ^[3] ) ist ein offenes Netzwerk von G-Queueus, das erstmals von Erol Gelenbe als Modell für Warteschlangensysteme mit spezifischen Steuerfunktionen wie Verkehrsausführung oder Verkehrszerstörung sowie als Modell für neuronale Netzwerke eingeführt wird. ^{[4] [5]} Ein G-Queue ist ein Netzwerk von Warteschlangen mit verschiedenen Arten von neuartigen und nützlichen Kunden:

• positiv Kunden, die aus anderen Warteschlangen ankommen oder als Poisson -Ankünfte extern eintreffen und den Standarddienst und die Routing -Disziplinen wie in herkömmlichen Netzwerkmodellen befolgen,
• Negativ Kunden, die aus einer anderen Warteschlange ankommen oder extern als Poisson-Ankünfte ankommen und Kunden in einer nicht leeren Warteschlange entfernen (oder „töten“). “Kunden ^{[6] [7]}
• “Trigger”, die von anderen Warteschlangen oder außerhalb des Netzwerks ankommen und die Kunden verdrängen und in andere Warteschlangen verschieben

Eine Produkt-Form-Lösung, die oberflächlich in Form von Jacksons Theorem ähnlich ist, das jedoch die Lösung eines Systems nichtlinearer Gleichungen für die Verkehrsströme erfordert, ist für die stationäre Verteilung von G-Networks vorhand In der Tat überraschend nichtlinear, und das Modell befolgt kein teilweise Gleichgewicht. Dies brach frühere Annahmen, dass eine Teilbilanz eine notwendige Bedingung für eine Produkt-Form-Lösung war. Eine leistungsstarke Eigenschaft von G-Networks ist, dass sie universelle Approximators für kontinuierliche und begrenzte Funktionen sind, damit sie verwendet werden können, um recht allgemeine Verhaltensweisen für Eingabe-Outputs zu approximieren. ^[8]

Definition [ bearbeiten ]

Ein Netzwerk von M miteinander verbundene Warteschlangen sind a G-Netzwerk Wenn

1. Jede Warteschlange hat einen Server, der mit Rate dient M _ich Anwesend
2. Externe Ankünfte positiver Kunden oder Auslöser oder Zurücksetzen bilden Poisson -Ratenprozesse
   ${displayStyle scriptstyle {lambda _ {i}}}$

   Für positive Kunden bilden Auslöser und Zurücksetzen, einschließlich negativer Kunden, einen Poisson -Prozess der Rate

   ${displayStyle scriptstyle {lambda _ {i}}}$

   Anwesend

3. Beim Abschluss des Dienstes wechselt ein Kunde aus der Warteschlange ich Schlange J Als positiver Kunde mit Wahrscheinlichkeit
   ${displayStyle scriptstyle {p_ {ij}^{+}}}$

   , als Auslöser oder Zurücksetzen mit Wahrscheinlichkeit

   ${displayStyle scriptstyle {p_ {ij}^{-}}}$

   und verlässt das Netzwerk mit Wahrscheinlichkeit

   ${displayStyle scriptstyle {d_ {i}}}$

   Anwesend

4. Bei der Ankunft in einer Warteschlange wirkt ein positiver Kunde wie gewohnt und erhöht die Warteschlangenlänge um 1.
5. Bei der Ankunft in einer Warteschlange reduziert der negative Kunde die Länge der Warteschlange um eine zufällige Zahl (falls mindestens ein positiver Kunde in der Warteschlange vorhanden ist), während ein Auslöser einen Kunden probabilistisch in eine andere Warteschlange verlegt und ein Reset den Status festlegt der Warteschlange in ihren stationären Zustand, wenn die Warteschlange beim Eintreffen des Resets leer ist. Alle Auslöser, negativen Kunden und Zurücksetzen verschwinden, nachdem sie ihre Maßnahmen ergriffen haben, so dass sie tatsächlich “Kontroll” -Signale im Netzwerk sind.

• Beachten Sie, dass normale Kunden, die eine Warteschlange verlassen, zu Triggern oder zurückgesetzt werden können, und negative Kunden, wenn sie die nächste Warteschlange besuchen.

Eine Warteschlange in einem solchen Netzwerk ist als als bekannt G-Queue .

Stationäre Verteilung [ bearbeiten ]

Definieren Sie die Nutzung an jedem Knoten,

$Oder$

bei dem die

für

erfüllen

${displaystyle lambda _{i}^{+}=sum _{j}rho _{j}mu _{j}p_{ji}^{+}+Lambda _{i},}$

( Erste )

${displaystyle lambda _{i}^{-}=sum _{j}rho _{j}mu _{j}p_{ji}^{-}+lambda _{i}.,}$

( 2 )

Dann schreiben ( N _Erste , …, N _M ) für den Zustand des Netzwerks (mit Warteschlangenlänge N _ich am Knoten ich ), wenn eine einzigartige nicht negative Lösung

existiert zu den obigen Gleichungen ( Erste ) Und ( 2 ) so dass R _ich für alle ich dann existiert die stationäre Wahrscheinlichkeitsverteilung π und wird gegeben

${displayStyle pi (n_ {1}, n_ {2}, ldots, n_ {m}) = prod _ {i = 1}^{m} (1-rho _ {i}) rho _ {i}^{n_ {ich}}.}$

Nachweisen [ bearbeiten ]

Es reicht aus, um zu zeigen

Befriedigt die globalen Balance-Gleichungen, die, ganz anders als Jackson-Netzwerke, nicht linear sind. Wir stellen fest, dass das Modell auch mehrere Klassen ermöglicht.

G-Networks wurden in einer Vielzahl von Anwendungen verwendet, einschließlich der Darstellung von Genregulierungsnetzen, der Mischung aus Kontrolle und Nutzlast in Paketnetzwerken, neuronalen Netzwerken und der Darstellung von Farbbildern und medizinischen Bildern wie Magnetresonanzbildern.

Reaktionszeitverteilung [ bearbeiten ]

Die Reaktionszeit ist die Zeitdauer, die ein Kunde im System verbringt. Die Reaktionszeitverteilung für einen einzelnen G-Queue ist bekannt ^[9] wo Kunden mit einer FCFS -Disziplin zum Preis serviert werden M , mit positiven Ankünften mit Geschwindigkeit l ⁺ und negative Ankünfte mit Rate l ^{– –} die Kunden vom Ende der Warteschlange töten. Die Laplace -Transformation der Reaktionszeitverteilung in dieser Situation ist ^{[9] [zehn]}

${displayStyle w ^ast} (s) = mfrac {mu (1-rho)} {lambada ^{+}}} {Frac {‘+lambada+mu (1-rho)-{SQRT {[S+Lampda+Mu mu mu mu mu mu mu mu . lambada +mu (1-rho)] ^{2} -4lampait ^{ +} tambda ^{-}}}}.$

Wo l = l ⁺ + l ^{– –} Und R = l ⁺ /( l ^{– –} + M ), erforderlich R <1 für Stabilität.

Die Reaktionszeit für ein Tandempaar von G-Queue (bei dem Kunden, die den Service am ersten Knoten abschließen, sofort zum zweiten und dann das Netzwerk verlassen) ist ebenfalls bekannt, und es wird angenommen, dass Erweiterungen zu größeren Netzwerken unerbittlich sein werden. ^[zehn]

Verweise [ bearbeiten ]