Εξισορρόπηση Φορτίου σε Δορυφορικά Δίκτυα με Χρήση Θεωρίας Παιγνίων και Μετανοητικής Μάθησης

Abstract

Η παρούσα διπλωματική εργασία διερευνά το πρόβλημα της εξισορρόπησης φορτίου σε Δορυφορικές Υποδομές Υπολογιστικής Παρυφής (Satellite Edge Computing - SEC). Στο πλαίσιο αυτό, επίγειοι χρήστες του Διαδικτύου των Πραγμάτων (Internet of Things - IoT) αναθέτουν υπολογιστικές διεργασίες σε δορυφορικούς εξυπηρετητές για κατανεμημένη επεξεργασία. Η ετερογένεια των διεργασιών αυτών και η στοχαστικότητα της άφιξής τους οδηγεί σε ανισοκατανομή του φορτίου μεταξύ των δορυφόρων. Στόχος είναι η ανάπτυξη μηχανισμών βέλτιστης εξισορρόπησης, με σκοπό τη χρονική και ενεργειακή αποδοτικότητα, αλλά και τη δικαιοσύνη (fairness). Η προτεινόμενη στρατηγική ακολουθεί μια επαναληπτική διαδικασία που περιλαμβάνει: (i) επιλογή κατάλληλου δορυφόρου-στόχου για κάθε δορυφόρο-πηγή σε κάθε γύρο, και (ii) προσδιορισμό της βέλτιστης ποσότητας φορτίου προς εκφόρτωση. Η τελευταία βασίζεται σε ένα ντετερμινιστικό κανόνα, ενώ η επιλογή στόχου μοντελοποιείται με παιγνιο-θεωρητικούς μηχανισμούς που λαμβάνουν υπόψη πραγματικούς τηλεπικοινωνιακούς περιορισμούς. Οι μηχανισμοί αυτοί διακρίνονται σε στοχαστικά παίγνια (stochastic games), καθώς και θορυβώδη παίγνια δυναμικού (potential games) σε μη ανατροφοδοτούμενα (bandit) ή ημιανατροφοδοτούμενα (semi-bandit) περιβάλλοντα. Για την επίλυση αυτών των παιγνίων αξιοποιούνται τεχνικές της Μετανοητικής Μάθησης (No-Regret Learning), με κύριο εργαλείο την παραλλαγή ε-Hedge του Αλγορίθμου Εκθετικών Βαρών (Exponential Weights Algorithm - EWA), η οποία προσφέρει εγγυήσεις σύγκλισης σε δ-ισορροπίες και ισορροπίες Nash για τα μοντέλα που βασίζονται σε παίγνια δυναμικού. Παρουσιάζονται επίσης ενεργειακά αποδοτικές επεκτάσεις των διατυπώσεων των παιγνίων, που επιτρέπουν το συμβιβασμό μεταξύ εξισορρόπησης φορτίου και ενεργειακής κατανάλωσης. Τα αποτελέσματα προσομοιώσεων καταδεικνύουν αποτελεσματική εξισορρόπηση φορτίου, με το μη ανατροφοδοτούμενο πάιγνιο δυναμικού να ξεχωρίζει λόγω της υψηλής του απόδοσης, των εγγυήσεων σύγκλισης και της πλήρως αποκεντρωμένης, επεκτάσιμης φύσης του. Περαιτέρω αξιολογήσεις επιβεβαιώνουν την ανθεκτικότητα της προσέγγισης αυτής υπό διαφορετικά επίπεδα φόρτου συστήματος, τοπολογίες δικτύων και παραμέτρους εκμάθησης.