Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/11936
Title: Πινακοαναλυτικές μέθοδοι ανάλυσης δυναμικών πρωτοκόλλων πρόσβασης σε ασύρματα συνεργατικά δίκτυα
Other Titles: Matrix analytic methods for analyzing dynamic access protocols in cooperative wireless network
Authors: Κατσάνου, Κωνσταντίνα Παρασκευή
Keywords: Πινακοαναλυτικές μέθοδοι
Ασύρματα συνεργατικά δίκτυα
Δυναμικό πρωτόκολλο
Keywords (translated): Martix analytics methods
Cooperative wireless networks
Dynamic protocol
Abstract: Οι πινακοαναλυτικές μέθοδοι αποτελούν πλέον ένα διαδεδομένο εργαλείο για την ανάλυση επίδοσης στοχαστικών συστημάτων που περιγράφονται από μια πολυδιάστατη στοχαστική διαδικασία. Ένα από τα σημαντικότερα προβλήματα στην μελέτη αυτής, αποτελεί ο προσδιορισμός της στάσιμης κατανομής της. Για τον λόγο αυτό υπάρχει πληθώρα θεωρητικών εργαλείων και αλγορίθμων που μπορούν να χρησιμοποιηθούν. Στόχος της παρούσας εργασίας είναι η παρουσίαση των βασικών θεωρητικών μεθόδων και η εφαρμογή αυτών στην ανάλυση δυναμικών πρωτοκόλλων πρόσβασης σε ασύρματα συνεργατικά δίκτυα. Αφού παρουσιάσουμε κάποια βασικά χαρακτηριστικά τα οποία ισχύουν στην περίπτωση που έχουμε μονοδιάστατες στοχαστικές διαδικασίες, θα τα γενικεύσουμε στην περίπτωση που έχουμε τις στοχαστικές διαδικασίες τύπου QBD (Quasi Birth-Death Processes). Θα αποδείξουμε ότι για μια στοχαστική διαδικασία τύπου QBD η στάσιμη κατανομή δίνεται από την πινακογεωμετρική σχέση π_{n-1} = π_{1}R_{n-1} ,n≥1 Ο πίνακας R εκφράζει το μέσο αριθμό των επισκέψεων στο αμέσως παραπάνω επίπεδο, πριν η διαδικασία επιστρέψει στο επίπεδο από το οποίο ξεκίνησε. Ολοκληρώνουμε παρουσιάζοντας μερικούς βασικούς αλγορίθμους για τον υπολογισμό του πίνακα R αλλά και για τον προσδιορισμό της στάσιμης κατανομής στην περίπτωση των πεπερασμένων διαδικασιών τύπου QBD. Σαν εφαρμογή του θεωρητικού πλαισίου που αναφέραμε πιο πριν θεωρούμε ένα Μαρκοβιανό σύστημα αναμονής με έναν υπάλληλο και δύο «ευφυείς» ουρές επαναλαμβανόμενων αφίξεων πεπερασμένης διάστασης. Αν οι πελάτες κατά την άφιξή τους βρουν τον υπάλληλο διαθέσιμο, τότε αρχίζουν άμεσα την εξυπηρέτηση τους. Σε αντίθετη περίπτωση τοποθετούνται στην ουρά επαναλαμβανόμενων αφίξεων με τον λιγότερο αριθμό πελατών, δηλ. εφαρμόζουμε την πολιτική join-the-shortest-orbit-queue (JSOQ), από όπου προσπαθούν να συνδεθούν με τον υπάλληλο. Συγκεκριμένα, ο ρυθμός των επαναπροσπαθειών σε μια ουρά επαναλαμβανόμενων αφίξεων εξαρτάται από τον αριθμό των πελατών στην άλλη ουρά επαναλαμβανόμενων αφίξεων (δυναμικό πρωτόκολλο). Το σύστημα περιγράφεται από μια τρισδιάστατη Μαρκοβιανή διαδικασία και με χρήση πινακοαναλυτικών τεχνικών υπολογίζουμε τα βασικά μέτρα απόδοσης, τα οποία χρησιμοποιούνται για τον προσδιορισμό χρήσιμων αριθμητικών αποτελεσμάτων . Το παρόν στοχαστικό μοντέλο χρησιμεύει στην αποτίμηση επίδοσης δυναμικών πρωτοκόλλων πρόσβασης σε ασύρματα συνεργατικά δίκτυα. Η εφαρμογή της πολιτικής JSOQ έχει αποδειχθεί ότι μειώνει δραστικά την αναμονή μετάδοσης πακέτων πληροφορίας από κάποιον χρήστη-πηγή σε μια συσκευή-προορισμό. Επιπλέον, το δυναμικό πρωτόκολλο επαναμετάδοσης, που βασίζεται στην γνώση που εξάγουν οι βοηθητικές συσκεύες σε σχέση με το περιβάλλον λειτουργίες τους, οδηγεί στην κατεύθυνση των ευφυών, αυτοπροσδιοριζόμενων (self-aware) δικτύων.
Abstract (translated): Matrix-analytic methods are now a well known tool for the performance analysis of systems that can be described as a queueing network. The reason why that happens is the existence of a large number of algorithms, that can be used for approximately compute the stationary probability. They are extensively used in modeling and performance analysis of computer systems, telecommunication systems and other stochastic systems. After we present some basic features that can be applied in cases that we have one dimensional stochastic processes, we will generalize them for Quasi Birth-Death Processes (QBD). We will prove that for a Quasi Birth-Death Process process the stationary probability has the matrix-geomertic form π_{n-1} = π_{1}R_{n-1} ,n≥1 The matrix R expresses the expected number of visits to the immediately above level before the process returns to the level from which it started. We conclude by presenting some basic algorithms for calculating the matrix R but also for determining the static distribution in the case of QBD finite processes. As an application of the theoretical framework we mentioned earlier, we consider a single server retrial system and two “smart” orbit queues of finite capacity. Arriving customers that find the server available can immediately begin service. Otherwise, they join the least loaded orbit queue, i.e., the blocked customer is routing in the shortest orbit queue according to join-the-shortest-orbit-queue (JSOQ) policy. Customers from the orbits try to access the server according to an adaptive constant retrial policy. More precisely, each orbit queue adjusts its retransmission parameters based on the knowledge of the state of the other. We consider a three-dimensional Markovian queueing model and we use matrix analysis techniques to determine basic performance metrics of the system, which are used to determine useful numerical results.
Appears in Collections:Τμήμα Μαθηματικών (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
ΔΕ Κατσάνου.pdf1.4 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons