Ανάλυση και σύγκριση αλγορίθμων ευκαιριακού χρονοπρογραμματισμού σε ασύρματα δίκτυα επικοινωνιών: μεθοδολογίες ανάλυσης και αποτελέσματα συγκριτικής αξιολογήσης

Abstract

Wireless communication networks develop rapidly, featuring excessive demand for performance improvements. This thesis studies performance and fairness issues of opportunistic schedulers, widely used in modern wireless standards like HSDPA and HDR. Opportunistic schedulers take into account the condition of the wireless link in order to select a terminal for service during a timeslot, by allocating to it all the available network resources. The main attribute of this type of scheduling is that the average transmission rate does depend on the number of active terminals, in the form of a multiuser diversity gain which acts as a multiplicative factor on the average rate. The above characteristics yield to a State Dependent Processor Sharing (SDPS) model, which in its general form considered here, features separate classes of terminals and a generic form of the state space, as a result of the admission control scheme. From a mathematical point of view, we manage to provide the distribution of the sojourn time for an SDPS system, which is expressed through the exponential of an appropriate M-matrix. The form allows the characterization of the asymptotic decay rate of the sojourn time’s distribution tail and provides easily computable upper and lower bounds. Furthermore, the conducted research studies time-scale separation phenomena, by separating the classes of terminals into a slow and a fast group, according to their average transmission rate. By leveraging on the nearly completely decomposable structure of the full system, we arrive in accurate approximations that offer conceptual and computational simplicity. Additionally, we consider some special important cases of the service rate function and/or the admission control scheme, which allow to determine the effect of the presence of slow class terminals on the performance of the terminals belonging in the fast group of classes. The results and conclusions of the generalized problem have been applied in the practical case of a channel-aware wireless network. A comparison of two basic opportunistic schedulers with respect to performance and fairness issues follows. We result in several conclusions regarding the value and the suitability of each scheduler, the appropriate form of the service pool and the specification of the worst case scenario related to the fast class terminals. Moreover, a new scheduling scheme is proposed, combining the nice properties oh the previous two schedulers. The theoretical findings are compared and verified numerically.

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