Markov Synexoys

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΕΙΡΑΙΑ – ΤΜΗΜΑ ∆Ι∆ΑΚΤΙΚΗΣ ΤΗΣ ΤΕΧΝΟΛΟΓΙΑΣ ΚΑΙ ΨΗΦΙΑΚΩΝ ΣΥΣΤΗΜΑΤΩΝ

ΣΥΣΤΗΜΑΤΑ ΑΝΑΜΟΝΗΣ - ΠΡΟΣΟΜΟΙΩΣΗ ∆Ι∆ΑΣΚΩΝ: Π. ∆ΕΜΕΣΤΙΧΑΣ ΕΝΟΤΗΤΑ ΣΥΣΤΗΜΑΤΑ ΑΝΑΜΟΝΗΣ 6 (ΣΑ6): ΜΑΡΚΟΒΙΑΝΕΣ ΑΛΥΣΙ∆ΕΣ ΣΥΝΕΧΟΥΣ ΧΡΟΝΟΥ

Ακαδηµαϊκό Έτος 2004 - 2005

Συστήµατα Αναµονής – Προσοµοίωση: Ενότητα ΣΑ6

1

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΕΙΡΑΙΑ – ΤΜΗΜΑ ∆Ι∆ΑΚΤΙΚΗΣ ΤΗΣ ΤΕΧΝΟΛΟΓΙΑΣ ΚΑΙ ΨΗΦΙΑΚΩΝ ΣΥΣΤΗΜΑΤΩΝ

Πίνακας Περιεχοµένων 1.

ΕΙΣΑΓΩΓΗ ........................................................................................................................ 3

2.

ΟΡΙΣΜΟΣ ΜΑΣΧ ............................................................................................................. 3

3.

∆Ε∆ΟΜΕΝΑ ΚΑΙ ΖΗΤΟΥΜΕΝΑ ΣΕ ΜΑΣΧ....................................................................... 3

4.

ΜΕΘΟ∆ΟΛΟΓΙΑ ΑΝΑΛΥΣΗΣ ΜΙΑΣ ΜΑΣΧ..................................................................... 4

5.

ΠΑΡΑ∆ΕΙΓΜΑ ................................................................................................................... 4

6.

ΣΥΝΟΨΗ ........................................................................................................................... 5

7.

ΒΙΒΛΙΟΓΡΑΦΙΑ ................................................................................................................. 6

Συστήµατα Αναµονής – Προσοµοίωση: Ενότητα ΣΑ6

2

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΕΙΡΑΙΑ – ΤΜΗΜΑ ∆Ι∆ΑΚΤΙΚΗΣ ΤΗΣ ΤΕΧΝΟΛΟΓΙΑΣ ΚΑΙ ΨΗΦΙΑΚΩΝ ΣΥΣΤΗΜΑΤΩΝ

1. ΕΙΣΑΓΩΓΗ Στην ενότητα αυτή µελετάµε Μαρκοβιανές Αλυσίδες Συνεχούς Χρόνου (ΜΑΣΧ). Επιπλέον πληροφορίες σχετικά µε το περιεχόµενο της ενότητας µπορούν να βρεθούν στα [1,2,3,4,5,6]. 2. ΟΡΙΣΜΟΣ ΜΑΣΧ Οι ΜΑΣΧ έχουν διακριτό χώρο κατάστασης. Οι διαδικασίες Markov συνεχούς χρόνου είναι ένα σύνολο τυχαίων µεταβλητών, X (t n ) , όπου n = 0, 1, 2, … . Η τιµή της τυχαίας µεταβλητής, X (t n ) , της διαδικασίας Markov δείχνει την κατάσταση του συστήµατος στη συγκεκριµένη χρονική στιγµή t n . Η βασική ιδιότητα των διαδικασιών Markov, στην περίπτωση αλυσίδων διακριτού χρόνου, µπορεί να εκφρασθεί ως εξής: P[X (t n +1 ) = j X (t n ) = in ,..., X (t1 ) = i1 ] = P[X (t n +1 ) = j X (t n ) = in ]

Η βασική ιδιότητα µιας διαδικασίας Markov είναι ότι η κατάσταση τη χρονική στιγµή t n +1 εξαρτάται µόνο από την κατάσταση τη χρονική στιγµή t n , και όχι από τις καταστάσεις στις προηγούµενες χρονικές στιγµές. Λόγω της βασικής ιδιότητας των διαδικασιών Markov, η κατανοµή του χρόνου παραµονής σε µια κατάσταση χαρακτηρίζεται από έλλειψη µνήµης. Στο συνεχή χρόνο η µόνη κατανοµή που έχει την ιδιότητα αυτή είναι η εκθετική. 3. ∆Ε∆ΟΜΕΝΑ ΚΑΙ ΖΗΤΟΥΜΕΝΑ ΣΕ ΜΑΣΧ Μια ΜΑ∆Χ δίνεται υπό τη µορφή κατευθυντικού γράφου G (V , E ) και ενός πίνακα ρυθµών µετάβασης Qˆ .

Οι κόµβοι του γράφου, V , είναι οι δυνατές καταστάσεις της ΜΑΣΧ. Οι ακµές δίνουν τις δυνατές µεταβάσεις µεταξύ των καταστάσεων. Κάθε ακµή ( i , j )∈ E σηµαίνει ότι είναι δυνατή η άµεση µετάβαση από την κατάσταση i στην j . Οι µεταβάσεις σε µια ΜΑΣΧ µπορούν να γίνουν σε οποιαδήποτε χρονική στιγµή. Σηµασία έχει ο µέσος χρόνος παραµονής σε µια κατάσταση i , ο οποίος συµβολίζεται µε Το πόσο πιθανές είναι οι µεταβάσεις καθορίζεται από τον πίνακα ρυθµών µετάβασης Qˆ . Οι διαστάσεις του πίνακα είναι V × V ( V είναι το πλήθος των καταστάσεων). Κάθε στοιχείο του πίνακα, qij , λέγεται ρυθµός µετάβασης, και καθορίζει το πόσο πιθανή είναι η άµεση µετάβαση από την κατάσταση i στην j ( i ≠ j ). Ο συνολικός ρυθµό εξόδου, λi , από την κατάσταση i δίνεται από τη σχέση λi = ∑ qij (∀ i ∈ V ). j∈V

Ο µέσος χρόνος παραµονής στην κατάσταση i είναι 1 λi .

Συστήµατα Αναµονής – Προσοµοίωση: Ενότητα ΣΑ6

3

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΕΙΡΑΙΑ – ΤΜΗΜΑ ∆Ι∆ΑΚΤΙΚΗΣ ΤΗΣ ΤΕΧΝΟΛΟΓΙΑΣ ΚΑΙ ΨΗΦΙΑΚΩΝ ΣΥΣΤΗΜΑΤΩΝ

Γίνεται η σύµβαση ότι στον πίνακα των ρυθµών µετάβασης, Qˆ , το κάθε στοιχείο qii

είναι ίσο µε (- λi ). Έτσι qii = (- λ i ) = (- ∑ qij ) j∈V

Το πρώτο ζητούµενο όταν αναλύουµε µια ΜΑΣΧ είναι ένα διάνυσµα πιθανοτήτων pˆ = [ p1 , ... , p V ], το οποίο ονοµάζεται στατική κατανοµή πιθανότητας, ή κατανοµή µόνιµης κατάστασης (steady state distribution), ή κατανοµή κατάστασης ισορροπίας (equilibrium state distribution). Η κάθε πιθανότητα pi (∀ i ∈ V ) εκφράζει το πόσο πιθανή είναι η κάθε κατάσταση i , ή µε άλλα λόγια, το ποσοστό του χρόνου που η ΜΑΣΧ θα βρίσκεται στην κατάσταση i . Το δεύτερο σύνηθες ζητούµενο όταν αναλύουµε µια ΜΑΣΧ είναι οι πιθανότητες µετάβασης, pij , µεταξύ των καταστάσεων i και j . Αυτές δίνονται από τον τύπο pij = qij / λi . 4. ΜΕΘΟ∆ΟΛΟΓΙΑ ΑΝΑΛΥΣΗΣ ΜΙΑΣ ΜΑΣΧ

Το διάνυσµα πιθανοτήτων pˆ δίνεται από το σύστηµα εξισώσεων:

pˆ Qˆ =0

(1α)

∑p

(2)

i∈V

i

=1

Το σύστηµα pˆ Qˆ =0 αναλυτικότερα γράφεται: ⎡ q11 ⎢q [ p1 , ... , p V ] ⎢ 21 ⎢ . ⎢ ⎣qV 1

q12 q 22 . qV 2

... q1V ⎤ ... q 2V ⎥⎥ =0 ... . ⎥ ⎥ ... qVV ⎦

(1β)

Το σύστηµα (1β) µπορεί επίσης να γραφεί:

∑p j∈V

j

⋅ q ji =0

∀ i ∈V

(1γ)

Από το παραπάνω σύστηµα παίρνουµε V εξισώσεις, οπότε σε συνδυασµό µε τη σχέση (2) έχουµε ένα σύστηµα V +1 εξισώσεων µε V αγνώστους. Αγνοούµε µια εξίσωση από αυτές που προκύπτουν από το σύστηµα (1β) (ή 1(γ)), οπότε σε συνδυασµό µε τη σχέση (2) έχουµε ένα σύστηµα V εξισώσεων µε V αγνώστους, το οποίο µπορεί να λυθεί µε αντικατάσταση. 5. ΠΑΡΑ∆ΕΙΓΜΑ

∆ίνεται η ΜΑΣΧ του παρακάτω σχήµατος και ζητείται η στατική κατανοµή πιθανότητας.

Συστήµατα Αναµονής – Προσοµοίωση: Ενότητα ΣΑ6

4

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΕΙΡΑΙΑ – ΤΜΗΜΑ ∆Ι∆ΑΚΤΙΚΗΣ ΤΗΣ ΤΕΧΝΟΛΟΓΙΑΣ ΚΑΙ ΨΗΦΙΑΚΩΝ ΣΥΣΤΗΜΑΤΩΝ

1 µ

µ

λ

λ r

2

r

3

Σχήµα 1. Παράδειγµα ΜΑΣΧ

Έχουµε ότι Qˆ

⎡− 2µ = ⎢ λ ⎢ ⎢⎣ λ

µ − (λ + r ) r

µ

⎤ ⎥ r ⎥ − (λ + r )⎥⎦

Επίσης pˆ Qˆ =0 ⇒ ⎡− 2µ [ p1 , p 2 , p3 ] ⎢ λ ⎢ ⎣⎢ λ

µ − (λ + r ) r

µ

⎤ ⎥ =0 r ⎥ − (λ + r )⎦⎥

Πραγµατοποιώντας τον πολλαπλασιασµό πινάκων παίρνουµε το σύστηµα: (-2) µ p1 + λ p 2 + λ p3 =0

(1)

µ p1 - ( λ + r ) p 2 + r p3 =0

(2)

µ p1 + r p 2 - ( λ + r ) p3 =0

(3)

Επίσης έχουµε την ακόλουθη εξίσωση: p1 + p 2 + p3 = 1

(4)

Από τις σχέσεις (1), (2), (4), και λύνοντας το σύστηµα µε αντικατάσταση, παίρνουµε p1 = λ /( λ +2 µ ), p 2 = µ /( λ +2 µ ), p3 = µ /( λ +2 µ ). 6. ΣΥΝΟΨΗ

Στην ενότητα αυτή µελετήσαµε Μαρκοβιανές Αλυσίδες Συνεχούς Χρόνου.

Συστήµατα Αναµονής – Προσοµοίωση: Ενότητα ΣΑ6

5

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΕΙΡΑΙΑ – ΤΜΗΜΑ ∆Ι∆ΑΚΤΙΚΗΣ ΤΗΣ ΤΕΧΝΟΛΟΓΙΑΣ ΚΑΙ ΨΗΦΙΑΚΩΝ ΣΥΣΤΗΜΑΤΩΝ

7. ΒΙΒΛΙΟΓΡΑΦΙΑ

[1]

Ν. Ασηµακόπουλος, «Ουρές αναµονής Πανεπιστήµιο Πειραιά, Πειραιάς, 2001

[2]

L.Kleinrock, “Queueing systems; volume 1: theory”, J. Wiley & Sons, New York, 1975

[3]

S.Haykin, “Communication systems”, J. Wiley & Sons, New York, 1983

[4]

R.Wolf, “Stochastic modelling and the theory of queues”, Prentice-Hall, Englewood Cliffs, NJ, 1989

[5]

Γ. Κοκολάκης, Ι. Σπηλιώτης, “Θεωρία πιθανοτήτων και εφαρµογές”, Εκδόσεις Συµεών, Αθήνα, 1987

[6]

R.Yates, D.Goodman, “Probability and stochastic processes: A friendly introduction for electrical and computer engineers”, J. Wiley & Sons, New York, 1999

Συστήµατα Αναµονής – Προσοµοίωση: Ενότητα ΣΑ6

–

Θεωρία

και

εφαρµογές»,

6