Αναλυση Και Συγκριση Αλγοριθμων Ευκαιριακου Χρονοπρογραμματισμου Σε Ασυρματα Δικτυα Επικοινωνιων: Μεθοδολογιες Αναλυσης Και Αποτελεσματα Συγκριτικης Αξιολογησης

Abstract

Τα δίκτυα ασύρματων επικοινωνιών γνωρίζουν ιδιαίτερη ανάπτυξη και χαρακτηρίζονται από τη συνεχώς αυξανόμενη ανάγκη για βελτιωμένες επιδόσεις και υψηλούς ρυθμούς μετάδοσης. Η διατριβή ασχολείται με τη μελέτη της επίδοσης σε συστήματα τηλεπικοινωνιών όπως το HSDPA και το HDR που βασίζονται σε αλγορίθμους ευκαιριακού χρονοπρογραμματισμού για την επιλογή του τερματικού που θα εξυπηρετηθεί σε κάθε χρονοσχισμή, λαμβάνοντας υπόψη την κατάσταση της ασύρματης ζεύξης. Βασικό γνώρισμα αυτού του τύπου χρονοπρογραμματισμού αποτελεί το γεγονός ότι ο μέσος ρυθμός εξυπηρέτησης δεν παραμένει σταθερός αλλά μεταβάλλεται ανάλογα με το πλήθος των ενεργών τερματικών. Ένα δίκτυο με τα παραπάνω χαρακτηριστικά αντιστοιχείται στο μοντέλο μερισμού του εξυπηρετητή με εξάρτηση από την κατάσταση, το οποίο στην πιο γενική μορφή που θεωρούμε εδώ, διαθέτει ξεχωριστές κλάσεις τερματικών ανάλογα με το μέσο επιτεύξιμο ρυθμό εξυπηρέτησης και γενική μορφή χώρου καταστάσεων ως αποτέλεσμα του ελέγχου αποδοχής κλήσεων. Στα πλαίσια της διδακτορικής διατριβής, για το συγκεκριμένο σύστημα υπολογίζεται η κατανομή του χρόνου απόκρισης κάποιου τερματικού δεδομένης κλάσης, η οποία εκφράζεται μέσω του εκθετικού ενός κατάλληλου πίνακα τύπου M. Η μορφή αυτή επιτρέπει τον χαρακτηρισμό του ασυμπτωτικού ρυθμού φθίσης ουράς της κατανομής με τη βοήθεια της ελάχιστης ιδιοτιμής του συγκεκριμένου πίνακα και ταυτόχρονα παρέχει εύκολα υπολογίσιμα άνω και κάτω φράγματα για την τιμή της. Επίσης, η διατριβή ασχολείται με τα φαινόμενα που προκύπτουν σε περιβάλλον διαχωρισμού χρονικής κλίμακας, διαχωρίζοντας τα τερματικά σε αργές και γρήγορες κλάσεις σύμφωνα με το μέσο ρυθμό μετάδοσης. Με εκμετάλλευση της σχεδόν πλήρως αποσυζεύξιμης δομής του πλήρους συστήματος, λαμβάνουμε ικανοποιητικές προσεγγίσεις για την επίδοση των αργών και των γρήγορων κλάσεων, οι οποίες προσφέρουν μεγαλύτερη ευκολία στην κατανόηση και υπολογιστική απλότητα. Παράλληλα, θεωρώντας ειδικότερες περιπτώσεις για τους ρυθμούς μετάδοσης των κλάσεων ή/και της μορφής του ελέγχου αποδοχής κλήσεων, καταλήγουμε σε χρήσιμα συμπεράσματα σχετικά με την επίδραση των αργών τερματικών στην κατανομή του χρόνου απόκρισης των γρήγορων τερματικών. Τα παραπάνω αποτελέσματα του γενικότερου προβλήματος εφαρμόζονται για την περίπτωση των υπό μελέτη συστημάτων τηλεπικοινωνιών και ακολουθεί η σύγκριση δύο βασικών αλγορίθμων ευκαιριακού χρονοπρογραμματισμού, όσον άφορα θέματα επίδοσης και δικαιοσύνης. Παρατίθενται χρήσιμα συμπεράσματα σχετικά με την αξία και την καταλληλότητα του καθενός, την επίδραση της μορφής του ελέγχου αποδοχής κλήσεων και τον προσδιορισμό της χειρότερης δυνατής περίπτωσης για τα τερματικά των γρήγορων κλάσεων. Επιπρόσθετα, προτείνεται ένας νέος αλγόριθμος ευκαιριακού χρονοπρογραμματισμού που συνδυάζει τα ευνοϊκά χαρακτηριστικά από τα ήδη μελετηθέντα σχήματα. Η διατριβή ολοκληρώνεται με την αριθμητική σύγκριση των θεωρητικών ευρημάτων.