Fronta tekutin - Fluid queue

v teorie front, disciplína v rámci matematické teorie pravděpodobnosti, a fronta tekutin (tekutý model,^[1] model proudění tekutiny^[2] nebo stochastický tekutinový model^[3]) je matematický model používaný k popisu hladiny kapaliny v nádrži podléhající náhodně určeným periodám plnění a vyprazdňování. Termín teorie přehrady byl použit v dřívější literatuře pro tyto modely. Tento model byl použit k aproximaci diskrétních modelů, modelování šíření požáry,^[4] v teorie ruin^[5] a modelovat vysokorychlostní datové sítě.^[6] Model použije algoritmus děravého kbelíku na stochastický zdroj.

Model byl poprvé představen Pat Moran v roce 1954, kdy se uvažovalo o diskrétním modelu.^[7][8][9] Tekuté fronty umožňují, aby příjezdy byly spíše spojité než diskrétní, jako v modelech jako M / M / 1 a Fronty M / G / 1.

Fluidní fronty byly použity k modelování výkonu a síťový přepínač,^[10] A router,^[11] the IEEE 802.11 protokol,^[12] Asynchronní režim přenosu (zamýšlená technologie pro B-ISDN ),^[13][14] sdílení souborů peer-to-peer,^[15] přepínání optických dávek,^[16] a má aplikace ve stavebnictví při navrhování přehrady.^[17] Proces je úzce spojen s procesy kvazi-narození-smrt, pro které jsou známy účinné metody řešení.^[18][19]

Popis modelu

Na frontu tekutin lze pohlížet jako na velkou nádrž, o které se obvykle předpokládá, že má nekonečnou kapacitu, připojenou k řadě trubek, které nalévají tekutinu do nádrže, a sérii čerpadel, která odstraňují tekutinu z nádrže. Obsluha ovládá potrubí a čerpadla a řídí rychlost, kterou tekutina proudí do vyrovnávací paměti, a rychlost, kterou kapalina opouští. Když operátor uvede systém do stavu i píšeme r_i pro rychlost přívodu čisté tekutiny v tomto stavu (vstup menší výstup). Když vyrovnávací paměť obsahuje tekutinu, pokud píšeme X(t) pro hladinu kapaliny v čase t,^[20]

${ displaystyle { frac { mathrm {d} X (t)} { mathrm {d} t}} = { begin {cases} r_ {i} & { text {if}} X (t)> 0 max (r_ {i}, 0) & { text {if}} X (t) = 0. End {cases}}}$

Provozovatel je a Markovův řetězec nepřetržitého času a obvykle se nazývá proces prostředí, proces na pozadí^[21] nebo proces řízení.^[6] Jako proces X představuje hladinu tekutiny ve vyrovnávací paměti, může nabývat pouze nezáporné hodnoty.

Tento model je konkrétním typem po částech deterministický Markovův proces a lze je také zobrazit jako Markovův model odměny s okrajovými podmínkami.

Stacionární distribuce

Stacionární rozvod je a distribuce fázového typu^[2] jak poprvé ukázal Asmussen^[22] a lze jej vypočítat pomocí maticově analytické metody.^[10]

Metoda aditivního rozkladu je numericky stabilní a odděluje vlastní čísla nezbytná pro výpočet pomocí Schurův rozklad.^[23][24]

Model zapnuto / vypnuto

Pro jednoduchý systém, kde služba má konstantní rychlost μ a přílet kolísá mezi rychlostmi λ a 0 (ve stavech 1 a 2) podle Markovův řetězec nepřetržitého času s generátorovou maticí

${ displaystyle Q = { begin {pmatrix} - alpha & alpha beta & - beta end {pmatrix}}}$

stacionární distribuci lze vypočítat explicitně a je dána vztahem^[6]

${ displaystyle F (x, 1) = { frac { beta} { alpha + beta}} left (1-e ^ { left ({ frac { beta} { mu}} - { frac { alpha} { lambda - mu}} vpravo) x} vpravo)}$

${ displaystyle F (x, 2) = { frac { alpha} { alpha + beta}} - { frac { beta left ( lambda - mu right)} { alpha + beta }} e ^ { left ({ frac { beta} { mu}} - { frac { alpha} { lambda - mu}} right) x}}$

a průměrná hladina kapaliny^[25]

${ displaystyle { frac {( lambda - mu) beta} {( mu ( alpha + beta) - beta lambda) ( alpha + beta)}} ( mu, lambda - mu).}$

Rušné období

Rušné období je časové období měřené od okamžiku, kdy tekutina poprvé dorazí do vyrovnávací paměti (X(t) se stane nenulovou), dokud není vyrovnávací paměť opět prázdná (X(t) se vrátí na nulu). V dřívější literatuře se někdy označuje jako období dešťů (přehrady).^[26] The Laplaceova-Stieltjesova transformace distribuce rušného období je známá pro frontu tekutin s nekonečným bufferem^[27][28][29] a očekávaný rušné období v případě omezené vyrovnávací paměti a přílety jako okamžité skoky.^[26]

Pro nekonečný buffer s konstantní rychlostí služby μ a příchodem rychlostí λ a 0, modulovaný Markovovým řetězcem s kontinuálním časem s parametry

${ displaystyle Q = { begin {pmatrix} - alpha & alpha beta & - beta end {pmatrix}}}$

psát si Ž*(s) pro Laplace-Stieltjesovu transformaci distribuce rušného období^[29]

${ displaystyle W ^ { ast} (s) = { frac { beta lambda + s lambda - beta mu + alpha mu - { sqrt {4 beta alpha mu ( mu - lambda) + (s lambda + beta ( lambda - mu) + alpha mu) ^ {2}}}} {2 beta ( lambda - mu)}}}$

což dává znamenat rušné období^[30]

${ displaystyle mathbb {E} (W) = { frac { lambda} { alpha mu + beta ( lambda - mu)}}.}$

V tomto případě je u jednoho zdroje zapnutí / vypnutí známo, že distribuce rušného období je a klesající poruchovost funkce, která znamená, že rušná období, což znamená, že čím déle rušná doba trvala, tím déle je pravděpodobné, že bude trvat.^[31]

Obecně existují dva hlavní přístupy k řešení rušného období, a to buď pomocí spektrálního rozkladu, nebo pomocí iterativní rekurentní metody.^[32]A kvadraticky konvergentní Algoritmus pro výpočet bodů transformace publikovali Ahn a Ramaswami.^[33]

Příklad

Například pokud fronta tekutin se sazbou služby μ = 2 je napájen zdrojem zapnutí / vypnutí s parametry α = 2, β = 1 a λ = 3, fronta tekutin má obsazeno s průměrem 1 a rozptylem 5/3.

Míra ztráty

V konečném pufru lze pomocí Laplace-Stieltjesových transformací vypočítat rychlost ztráty kapaliny (vyřazené ze systému kvůli plnému pufru).^[34]

Horský proces

Termín horský proces byl vytvořen k popisu maximální hodnoty procesu obsahu vyrovnávací paměti dosažené během rušného období a lze jej vypočítat pomocí výsledků z Fronta G / M / 1.^[35][36]

Sítě fronty tekutin

Bylo vypočítáno stacionární rozdělení dvou front tandemových tekutin a bylo prokázáno, že nevykazují a produktová forma stacionární distribuce v netriviálních případech.^{[25][30][37][38][39]}

Fronty zpětné vazby

Fronta zpětnovazebních tekutin je model, kde jsou parametry modelu (matice přechodové rychlosti a vektor driftu) do určité míry povoleny v závislosti na obsahu vyrovnávací paměti. Obsah vyrovnávací paměti je obvykle rozdělen na oddíly a parametry závisí na tom, ve kterém oddílu se proces obsahu vyrovnávací paměti nachází.^[40] Nařízeno Schurova faktorizace lze použít k efektivnímu výpočtu stacionární distribuce takového modelu.^[41]

Tekuté fronty druhého řádu

Fluidní fronty druhého řádu (někdy nazývané Markovovy modulované difúzní procesy nebo fluidní fronty s Brownovým šumem)^[42]) zvážit a odráží Brownův pohyb s parametry řízenými Markovovým procesem.^[22][43] Běžně se uvažuje o dvou různých typech okrajových podmínek: pohlcování a odrážení.^[44]

externí odkazy

• BuTools, a MATLAB, Krajta a Mathematica implementace některých z výše uvedených výsledků.
• PevaNástroje, MATLAB kód pro modely s více režimy
• Výukový program pro modely proudění tekutin od V. Ramaswamiho na MAM8

Reference