Bemenet modellezése (III.), forgalommodellezés

Bemenet modellezése (III.), forgalommodellezés Vidács Attila 2007. október 31.

Hálózati szimulációs technikák, 2007/10/31

1

Modellválasztás • A modellezés kedvez® esetben leegyszer¶södik a megfelel® eloszlás kiválasztásának feladatára. • A helyzet kedvez®, ha az alábbi egyszer¶sít® feltevéseink helytállóak:

A vizsgált folyamat független, azonos (közös) eloszlású (iid) valószín¶ségi változók sorozata.

A közös eloszlás a szokásos eloszláscsaládok egyike, amelyek elérhet®k szinte minden szimulációs programcsomagban: pl. béta, Erlang, exponenciális, gamma, lognormális, normális, Poisson, egyenletes, Weibull.

Rendelkezésünkre állnak mérési eredmények, amelyre illeszthetjük az eloszlást valamilyen módszerrel, mint például: maximmum likelihood vagy momentum módszer.

A választott eloszlás jól illeszkedik az adatokra, amit valamely vizuális vizsgálattal vagy illeszkedésvizsgálattal ellen®rizhetünk.


2

Modellválasztás • A helyzet néha nem kedvez® az alábbi okok miatt:

A szokásos eloszláscsaládok nem eléggé rugalmasak ahhoz, hogy a meggyelt adatok sajátos jellegét leírják.

A folyamat elemei nem függetlenek. (Vagy az id®sor elemei valahogyan összefügg®ek, vagy a folyamat korrelált a rendszer más bemenetével.)

A folyamat paraméterei az id®ben változnak (nemstacionaritás). Nem áll rendelkezésünkre mérés, amire az illesztést elvégezhetnénk. • A továbbiakban néhány példát és megoldást adunk a fenti esetekre.


3

Egyváltozós modellek • Feladat: Olyan modellezési esetekben, amikor a változósorozat

független, azonos eloszlású (iid), amikor az eloszlásnak valamilyen szokványostól eltér® jellege van (pl. egynél több módus),

vagy nincs mért adat amire illeszteni szeretnénk, hanem az eloszlás bizonyos jellemz®it adjuk meg (pl. momentumok, percentilis).

• Modellek

Johnson eloszláscsalád Inverz eloszlás polinomiális sz¶r®vel (Bézier eloszlások)


4

Johnson eloszláscsalád • Az eloszlások egy rugalmasabb családja el®állítható a következ® (Johnson) transzformációval: F (x) = Φ {γ + δg[(x − ξ)/λ]} ,

−∞ < x < ∞,

ahol Φ a standard normális eloszlásfüggvény, γ és δ az alak (shape) paraméterek, ξ a helyzet (location) paraméter, λ a skála (scale) paraméter, g pedig a következ® transzformációk egyike:   log(x) a lognormális családnál,      sinh−1 (x) a nem korlátos családnál, g(x) =  log[x/(1 − x)] a korlátos családnál,      x a normális családnál.

• A megfelel® transzformáció kiválasztható egy véletlen minta ferdeségének és lapultságának becslésével, és ezek illesztésével.


5

Johnson eloszláscsalád (2) • A véletlen változók generálása egy Z standard normális eloszlású v.v. transzformációjával: X = ξ + λg −1 [(Z − γ)/δ], ahol

  ea      (ea − e−a )/2 −1 g (a) =  1/(1 + e−a )      a

a lognormális családnál, a nem korlátos családnál, a korlátos családnál, a normális családnál.

• Megjegyzés: Ha nem állnak rendelkezésre mért adatok, az eloszlás szubjektív információkra is illeszthet® (DeBrota et al., 1989).


6

Inverz eloszlás polinomiális sz¶r®vel • Inverse Distribution with Polinomial Filter (IDPF) • Ha a választott referencia-eloszlás illesztése után kiderül, hogy az illeszkedés nem kielégít®, akkor használható az IDPF módszer. • Ismeretlen, folytonos eloszlású v.v.-k generálásához gyakran használjuk az illesztett FX tapasztalati eloszlásfüggvény inverzét: −1 X = FX (U ),

ahol U ∼ U (0, 1) .


7

Többváltozós modellek • Ha több véletlen változóról van szó, ezek lehetnek összefügg®ek (vektorok vagy id®sorok). • Általánosan használt modellek:

Többváltozós normál eloszlás véletlen vektorokhoz, p-edrend¶ Gauss-i autoregresszív (AR(p)) modellek id®sorokhoz. • (Id®sorok modellezését ld. kés®bb.) • Adott eloszlású véletlen vektorok el®állításához használatos módszerek:

(Johnson eloszláscsalád többváltozós kiterjesztése) (Kétváltozós Bézier eloszlások) NORTA NORmal To anything


8

NORTA • NORTA NORmal To Anything (Normálist bármivé) • Ötlet: Transzformáljunk egy standard (többváltozós) normális

eloszlású véletlen vektort a kívánt eloszlásúra.

• Egy Z (k × 1) véletlen vektor standard normális várható érték vektorral és  1 ρ12 · · ·   1 ···  ρ21  Σ= . .. ..  .. . .  ρk1

ρk2

···

eloszlású µ = (0, 0, . . . , 0)0

 ρ1k ρ2k .. .

      

1

korrelációs mátrixszal, ahol az i-edik Zi elem N (0, 1) eloszlású, és ρij = Corr{Zi , Zj }.

• A Σ és µ paraméterek egyértelm¶en meghatározzák az eloszlást.


9

NORTA (2) • Legyen



−1 [Φ(Z1 )] FX 1

  −1  FX2 [Φ(Z2 )] X= ..   .  −1 FX [Φ(Zk )] k

    ,   

ahol Z = (Z1 , Z2 , . . . , Zk )0 egy standard normális eloszlású vektor Σ korrelációs mátrixszal, és FX1 , FX2 , . . . , FXk a kívánt határeloszlások.

• A feladat: Megtalálni azt a Σ mátrixot, ami X kívánt korrelációs mátrixszát eredményezi.

Ez nem túl bonyolult numerikus probléma (Cairo és Nelson, 1997). Habár az illesztés id®igényes lehet, ezt modellenként csak egyszer kell végrehajtani.


10

Forgalommodellezés


11

Érkezési folyamatok leírása Egy érkezési folyamat leírására több megadási mód is létezik:

• Pontfolyamat. Diszkrét entitások (csomagok, cellák, ...) érkezési id®pillanatainak sorozata: T0 = 0, T1 , . . . Tn , . . . • Számláló folyamat. Az {N (t)}∞ t=0 számlálófolyamat egy folytonos idej¶, nemnegatív egész érték¶ sztochasztikus folyamat, ahol N (t) az érkezések száma a (0, t] id®intervallumban: N (t) = max{n : Tn ≤ t}, • Érkezésközti id®k sorozata. {An }∞ n=1 , ahol An az n-edik és az (n − 1)-edik érkezés között eltelt id®, azaz An = Tn − Tn−1


12

Érkezési folyamatok leírása (2) • A három megadási mód ekvivalens: Tn =

n X

Ak

k=1

( {N (t) = n} = {Tn ≤ t < Tn+1 } =

n X k=1

Ak ≤ t <

n+1 X k=1

) Ak


Inhomogén Poisson folyamat • Felújítási folyamatokat el®szeretettel alkalmaznak a modellezésben, ahol az érkezések-közti id®intervallumok i.i.d. v.v.-k. • Az érkezés-közti id®k eloszlásának gyakran választják az exponenciális eloszlást 1/λ várható értékkel, így a beérkezési folyamat Poisson folyamat lesz λ intenzitás-paraméterrel. • A gyakorlati esetek többségében azonban az érkezési folyamat intenzitása az id®ben változik: λ = λ(t). • A Poisson folyamat egy általánosítása az inhomogén Poisson folyamat λ(t) intenzitás-id® függvénnyel. • Probléma: A λ(t) függvény illesztése nagyon bonyolult feladat.

13


14

Inhomogén Poisson folyamat • Legyen {N (t) : t ≥ 0} a beérkezéseket számláló, nemnegatív, egész érték¶ sztochasztikus folyamat. • Legyen egy x (0, S] intervallumban történ® n beérkezés érkezési id®pillanatainak sorozata t1 < t2 < · · · < tn . • Legyen (Kuhl, Wilson és Johnson, 1997) (m ) p X X λ(t) = exp α i ti + βk sin(ωk t + φk ) , i=0

k=1

ahol az ismeretlen paraméterek θ vektora tartalmazza a polinomiális komponens (trend) m + 1 együtthatóját, valamint a trigonometrikus komponens (periódikus komp.) p darab amplitúdó (βk ), frekvencia (ωk ) és fáziseltolás (φk ) paraméterét.

• A továbbiakban: p = 1.


15

Inhomogén Poisson folyamat (2) • A log-likelihood függvény θ meghatározásához: L(θ) =

m X i=0

ahol Ti =

αi Ti + β

n X j=1

Z

S

sin(ωtj + φ) −

λ(z) dz, 0

Pn

i j=1 tj .

• A log-likelihood függvényt dierenciálva az ismeretlenek szerint m + 4 egyenlethez jutunk, amely egyenletrendszer numerikusan megoldható. • Az m paraméter is ismeretlen, ML módszerrel nem meghatározható. • Megoldás: Különböz® x m értékekre az ML becsléseket kiszámoljuk, majd az eredményeket az ML arány teszttel összehasonlítjuk és a legjobbat választjuk.


Forgalommodellek tartalom • Felújítási folyamatok

Poisson folyamat Bernoulli folyamat • Markovi modellek

Markov-modulált forgalommodellek (MMPP) Markov modellek általánosításai • (Folyadékmodellek) • Lineáris sztochasztikus modellek

AR, MA, ARMA, ARIMA, ARFIMA DAR(p) modell • TES modellek • Önhasonló folyamatok

16


17

Felújítási folyamatok • Egy felújítási folyamatban az érkezésközti id®k független, azonos eloszlású v.v.-k, tetsz®leges eloszlásfüggvénnyel.

Poisson folyamat • Poisson folyamat esetén az érkezésközti id®k eloszlása exponenciális: P {An ≤ τ } = 1 − e−λτ , ahol λ az átlagos érkezési intenzitás.

• Egy τ hosszú intervallumon belüli érkezések száma Poisson eloszlású: (λτ )n e−λτ P {N (τ ) = n} = n!


18

Felújítási folyamatok (2) Bernoulli folyamat • A Bernoulli folyamat a Poisson folyamat diszkrét idej¶ megfelel®je. • Az érkezések száma egy adott k id®résen belül binomiális eloszlást követ:   k  pn (1 − p)k−n P {Nk = n} =  n • Két érkezés közötti id®rések száma geometriai eloszlású: P {An = j} = p(1 − p)j

Lehetséges alkalmazások • A felújítási folyamatok szigorúan független érkezések modellezésére alkalmas.

Pl. Hívásérkezések egy felhasználói csoportból. • Megjegyzés: A meggyelések szerint a hálózatok forgalma szinte mindig (er®sen) összefügg®!


19

Markov modellek • A Markov folyamatok összefügg® folyamatok modellezésére is alkalmasak.

Markov láncok • Legyen

S = {s1 , s2 , . . . , sM } egy adott állapottér, Xn egy véletlen változó, amely megadja az állapotot az n id®pontban. • Az {Xn } v.v.-k sorozata egy diszkrét idej¶ Markov lánc, ha a P {Xn+1 = sj } valószín¶ség csak a jelen állapottól (Xn ) függ, és nem függ a múltbeli (jöv®beli) állapotoktól. Azaz a folyamat emlékezetmentes. • A Markov lánc folytonos idej¶, ha az állapotátmenetek nem csak diszkrét id®pontokban következhetnek be. • Az emlékezetmentes tulajdonság következménye, hogy diszkrét esetben az adott állapotban tartózkodás id®tartama geometriai eloszlású, folytonos esetben pedig exponenciális eloszlást követ.


20

Markov láncok • Egy diszkrét idej¶ Markov lánc megadható az állapotátmenet-valószín¶ség mátrixszal és a kezdeti eloszlással.

Lehetséges alkalmazások • Markov láncok olyan folyamatok modellezésére alkalmasak, ahol egy meggyelés csak az el®z® meggyelés értékét®l függ.

Pl. A felhasználó viselkedése: A következ® akció az el®z® akciótól vagy annak eredményét®l (pl. sikeres vagy meghiúsult) függ.

Rendszer vagy hálózat állapotátmeneteinek modellezése. Hálózati forgalom modellje, ha a meggyelt forgalom csak kis mértékben összefügg®.

• Ha a forgalmat folytonos idej¶ ML írja le, minden állapotátmenet megfeleltethet® egy érkezésnek. • Diszkrét idej¶ ML esetében minden i állapot megfeleltethet® i üres id®résnek.


Markov-modulált forgalommodellek • Markov-modulált folyamatok esetén valamiféle mögöttes állapotokat deniálunk a forgalomforrás leírásához, és egy (rejtett) Markov folyamat kontrollálja az állapotátmeneteket az id®ben. Az aktuális állapot határozza meg a forgalomforrás karakterisztikáját.

Markov-modulált Poisson folyamat (MMPP) • A mögöttes Markov lánc minden k állapotához hozzárendelünk egy λk intenzitásparamétert. • Ha a rendszer a k állapotban van, a generált forgalom λk paraméter¶ Poisson folyamattal írható le. • Spec: Megszakított Poisson folyamat (IPPInterrupted Poisson Process): A ML két állapotú, az egyik állapotban (o) 0, a másik állapotban (on) λ intenzitású a generált forgalom. • Megjegyzés: Egy m + 1 állapotú MMPP el®állítható m darab független, azonos IPP szuperpozíciójával.

21


Markov-modulált Poisson folyamat MMPP illesztése • A meggyelt forgalmat (érkezéseket) az érkezési intenzitás alapján n állapotba osztjuk, ezek a ML állapotai. Az állapotátmenetek valószín¶ségei becsülhet®k az állapot-átmenetek leszámlálásával.

Alkalmazási lehet®ségek • Markov-modulált folyamatok alkalmazhatóak, ha az érkezési intenzitás változik az id®ben, de nincs szignikáns összefügg®ség a folyamatban.

22


Markov folyamatok általánosítása • Fázis típusú felújítási folyamatok (Phase-type renewal processes) A mögöttes Markov láncnak több állapotot is meglátogatva el kell jutnia egy nyel® állapotba egy érkezés generálásához. • Markov felújítási folyamatok Egy állapotban tartózkodás id®tartamának eloszlása általános, az adott állapottól függ® eloszlás. • (Kötegelt) Markov érkezési folyamatok ((Batch)Markov Arrival ProcessMAP) • (Markov-modulált folyadékmodellek)

23

Bemenet modellezése (III.), forgalommodellezés

Recommend Documents