Performance analysis of distributed control algorithms in queueing systems
Authors: Παπαφράγκος Σπυρίδων 
Published: September 2021

Στην διατριβή αυτή μελετάμε την ανάλυση επίδοσης κατανεμημένων αλγορίθμων ελέγχου σε δυο διαφορετικές περιοχές όπου προκύπτουν ουρές αναμονής: α) ασύρματα δίκτυα και β) πλατφόρμες κοινής χρήσης ιδιωτικών αυτοκινήτων. Στο πρώτο μέρος μελετάμε την από κοινού ελαχιστοποίηση του κόστους αναμονής και της κατανάλωσης ενέργειας σε ένα ασύρματο δίκτυο, πάνω από όλες τις πολιτικές ελέγχου ισχύος στους πομπούς. Προκύπτουν σχεδόν βέλτιστες πολιτικές μέσω μιας σύγκρισης με ένα ενιαίο σύστημα ζεύξης. Οι πολιτικές αυτές είναι της μορφής: η συνολική ισχύς που καταναλώνεται σε οποιαδήποτε στιγμή είναι μια μονότονη συνάρτηση ενός γραμμικού συνδυασμού του μεγέθους των ουρών εκείνη την στιγμή, ενώ ο διαμοιρασμός της ισχύος σε κάθε πομπό είναι τέτοιος ώστε οι ταχύτητες σύνδεσης που προκύπτουν να είναι ανάλογες του μεγέθους των ουρών. Αυτό που επιτρέπει αυτό το είδος αποσύνθεσης είναι ο συγκεκριμένος τύπος κόστους αναμονής που εξετάζεται καθώς και το γεγονός ότι κάτω από την πολιτική όπου ελαχιστοποιεί αυτό το κόστος (κάτω από ένα συγκεκριμένο προυπολογισμό ισχύος), το σύστημα γίνεται ουσιαστικά μονοδιάστατο. Καθώς η δομή του βέλτιστου ελέγχου είναι γνωστή για την περίπτωση αυτή, μπορεί κανείς να την εφαρμόσει για την βελτιστοποίηση της επίδοσης του μονοδίαστατου αυτού συστήματος. Προσομοιώσεις δείχνουν ότι προτεινόμενες πολιτικές προσφέρουν σημαντικά οφέλη επίδοσης καθώς η μέση ισχύς πλησιάζει την χαμηλότερη τιμή για την οποία διατηρείται η σταθερότητα. Επιπλέον, οι πολιτικές αυτές φαίνεται ότι αποδίδουν καλύτερα από σχήματα ελέγχου ισχύος με βάση την προβολή κλίσης, όπως εκείνες που προκύπτουν από την μεγιστοποίηση της χρησιμότητας του δικτύου. Εφαρμόζουμε αυτές τις ιδέες σε ένα κυψελωτό ασύρματο δίκτυο CDMA (διαίρεσης κώδικα πολλαπλής πρόσβασης) και προτείνουμε ένα συγκεκριμένο σχήμα ελέγχου ισχύος ανερχόμενης ζεύξης για πακέτα δεδομένων με μικρή καθυστέρηση στις ουρές αναμονής. Το σχήμα αυτό μπορεί να θεωρηθεί σαν μια επέκταση του αλγορίθμου των Foschini-Miljanic ο οποίος λαμβανει υπόψη τα μεγέθη των ουρών στις κινητές συσκευές. Το προτεινόμενο αυτό σχήμα ελαχιστοποιεί τον χρόνο αποστράγγισης συγκριτικά με οποιαδήποτε άλλη πολιτική με την ίδια κατανάλωση ενέργειας. Αυτό συμβαίνει εξαιτίας επίδρασης ενός φαινομένου που ονομάζεται συγκέντρωση πόρων που προκύπτει όταν όλες οι ουρές αδειάζουν την ίδια χρονική στιγμή. Στην τυποποιημένη μορφή του το προτεινόμενο σχήμα εκμεταλλεύεται την συγκέντρωση πόρων μέσα σε μια κυψέλη και δεν χρειάζεται περεταίρω επικοινωνία μεταξύ κυψελών. Σε μια επέκταση του αλγορίθμου η συγκέντρωση πόρων –και ακόμα καλύτερη επίδοση- επιτυγχάνεται για ολόκληρο το δίκτυο επιτρέποντας περιορισμένη επικοινωνία μέσω μηνυμάτων μεταξύ των σταθμών βάσης διαφορετικών κυψελών. Προσομοιώσεις παρουσιάζουν σημαντικές μειώσεις στην καθυστέρηση των ουρών αναμονής σε σύγκριση με άλλα σχήματα ελέγχου ισχύος που έχουν προταθεί στην βιβλιογραφία και ειδικά υπό την παρουσία αργής εξασθένησης σήματος. Στο δεύτερο μέρος της διατριβής, μελετάμε πλατφόρμες κοινής χρήσης ιδιωτικών αυτοκινήτων όπως για παράδειγμα η Uber και η Lyft. Τέοιες πλατφόρμες δίνουν οικονομικά κίνητρα στους οδηγούς που συμμετέχουν, για να μοιραστούν μια διαδρομή με πελάτες που κι εκείνοι με την σειρά τους συμμετέχουν στην πλατφόρμα. Όταν η προσφορά των διαθέσιμων οδηγών σε μια συγκεκριμένη τοποθεσία υπολείπεται της ζήτησης για μεταφορά πελατών στην ίδια τοποθεσία, οι πλατφόρμες αυξάνουν την τιμή για μεταφορά έτσι ώστε να αντιμετωμιστεί η ανισορροπία προσελκύοντας περισσότερους διαθέσιμους οδηγούς και ταυτόχρονα αποτρέποντας επιπλέον αιτήματα επιβατών. Κάτω από αυτές τις ρυθμίσεις, μελετάμε την επίδραση των τύπων της πληροφορίας επί των οποίων βασίζονται αυτές οι δυναμικές τιμές, που έχουν στα μοτίβα κινητικότητας των διαθέσιμων οδηγών και στη μέση καθυστέρηση του χρόνου που μεσολαβεί μέχρι ένας οδηγός να παραλάβει κάποιον πελάτη. Με βάση ένα βαθμωτό διακριτού-χρόνου Μαρκοβιανό μοντέλο για την κινητικότητα των οδηγών και την συσσώρευση των επιβατών σε ουρές αναμονής, συγκρίνουμε τις επιδόσεις διαφόρων πολιτικών που λαμβάνουν υπόψη μετρικές όπως ο αριθμός των πελατών που περιμένουν σε μια περιοχή να εξυπηρετηθούν ή η αναλογία των πελατών προς τους οδηγούς σε μια περιοχή. Πειράματα δείχνουν ότι η πληροφορία των πελατών σε μια ουρά και η αναλογία τους προς τους οδηγούς, οδηγούν σε ανώτερες επίδοσεις σε σύγκριση με τιμές που υπολογίζονται μέσω μηχανισμού δοκιμής και λάθους (tatonnement) ή συμεριφοράς των οδηγών οι οποίες δεν λαμβάνουν υπόψη βραχυπρόθεσμες διακυμάνσεις της ζήτησης. Επιπλέον, βρίσκουμε ότι ότι η δυναμική πληροφορία μειώνει σημαντικά την καθυστέρηση, ένα αποτέλεσμα που έρχεται σε αντίθεση με πρόσφατα ευρήματα στην βιβλιογραφία, όπου βρίσκουν πως η δυναμική πληροφορία δεν αυξάνει τα κέρδη της πλατφόρμας.