Resource allocation, content recommendation and online learning mechanisms for mobile edge networks
Authors: Χατζηελευθερίου Λίβια-Έλενα 
Published: April 2023

Τα Mobile Edge Computing (MEC) συστήματα φέρνουν υπολογιστικούς και ενταμιευτικούς πόρους στην εγγύτητα των χρηστών. Δημιουργούν ένα νέο οικοσύστημα υπηρεσιών, όπως η παράδοση βίντεο και οι επαυξημένη πραγματικότητα (AR), ενώ μειώνουν την καθυστέρηση που αντιμετωπίζουν οι χρήστες και μειώνουν το κόστος των υπηρεσιών δικτύου. Οι κύριες προκλήσεις που αντιμετωπίζει το MEC σχετίζονται με τη σπανιότητα των πόρων στην άκρη του δικτύου, την απροβλεπτότητα σημαντικών παραμέτρων του συστήματος, όπως η κίνηση, η ζήτηση σε περιεχόμενο και υπολογιστικούς πόρους, και οι εξαιρετικά υψηλές απαιτήσεις για χαμηλή καθυστέρηση που πρέπει να ικανοποιηθούν.Σε αυτή τη διατριβή ασχολούμαστε με τις παραπάνω προκλήσεις, με σκοπό τη βελτιστοποίηση δύο στόχων για το MEC: την παράδοση περιεχομένου και την ανάλυση δεδομένων σε πραγματικό χρόνο στην άκρη του δικτύου. Παρουσιάζουμε μηχανισμούς και μεθόδους κατανομής πόρων που αυτοματοποιούν την κατανομή πόρων, για συστήματα επικοινωνίας πέμπτης γενιάς (5G), Beyond-5G (B5G) και έκτης γενιάς (6G), λαμβάνοντας υπόψη πόρους στην άκρη του δικτύου όπως κρυφές μνήμες, υπολογιστικούς πόρους κινητών συσκευών και servers στην άκρη του δικτύου, εύρος ζώνης και ενέργεια. Μελετάμε περιπτώσεις προβλημάτων βελτιστοποίησης τόσο offline όσο και Online Learning (OL) που καλύπτουν συστάσεις και ενταμίευση περιεχομένου, ανάθεση χρηστών και ανάθεση υπολογιστικών πόρων. Χρησιμοποιούμε μια ποικιλία μαθηματικών εργαλείων για την επίλυση αυτών των προβλημάτων, όπως η συνδυαστική βελτιστοποίηση, η κυρτή βελτιστοποίηση και η Online Convex Optimization (OCO), μια ειδική περίπτωση του OL. Αναλύουμε και εκμεταλλευόμαστε τις δομικές ιδιότητες των διατυπωμένων προβλημάτων βελτιστοποίησης, είτε σχεδιάζοντας ex novo αλγορίθμους είτε προσαρμόζοντας υπάρχουσες τεχνικές στα προβλήματά μας. Παρέχουμε αποδοτικές, γρήγορες και κομψές λύσεις με αποδεδειγμένες εγγυήσεις ως προς την απόδοσή τους, για μια ποικιλία σημαντικών προβλημάτων που προκύπτουν στο πλαίσιο του MEC.Ξεκινάμε μελετώντας την αλληλεπίδραση των μηχανισμών ενταμίευσης και των Συστημάτων συστάσεων περιεχομένου (Recommender Systems - RS). Οι αποφάσεις ενταμίευσης περιεχομένου συνήθως επιδιώκουν να ενταμιεύσουν περιεχόμενο που μεγιστοποιεί την αναλογία αιτημάτων που μπορούν να ικανοποιηθούν από τα ενταμιευμένα αντικείμενα (cache hit ratio). Τα συστήματα συστάσεων, αντίθετα, εστιάζουν σε μεμονωμένους χρήστες και τους προτείνουν ελκυστικό περιεχόμενο προκειμένου να προκαλέσουν περαιτέρω κατανάλωση περιεχομένου. Διερευνούμε πώς αυτοί οι, φαινομενικά αντικρουόμενοι, στόχοι μπορούν να αντιμετωπιστούν από κοινού. Πρώτον, διαμορφώνουμε ένα πρόβλημα βελτιστοποίησης για από κοινού ενταμιευτικές αποφάσεις και αποφάσεις σχετικά με το περιεχόμενο που θα προταθεί, Joint Caching and Recommendation (JCR), με στόχο τη μεγιστοποίηση του cache hit ratio υπό περιορισμούς που αφορούν στην ελεγχόμενη παραμόρφωση των εγγενών προτιμήσεων του χρήστη σε περιεχόμενο από τις εκδοθείσες συστάσεις. Στη συνέχεια, αποδεικνύουμε ότι το πρόβλημα είναι NP-πλήρες και ότι η αντικειμενική του συνάρτηση στερείται εκείνων των ιδιοτήτων μονοτονίας και submodularity που θα εγγυώνταν την προσέγγισή του. Ως εκ τούτου, προχωράμε στο σχεδιασμό ενός απλού αλγόριθμου με πολυωνυμική χρονική υπολογιστική πολυπλοκότητα, που ουσιαστικά χρησιμεύει ως μια μορφή ελαφρού ελέγχου των συστάσεων, ώστε να είναι τόσο ελκυστικές για τους τελικούς χρήστες όσο και φιλικές προς τους πόρους δικτύου. Βασιζόμαστε τόσο σε μαθηματική ανάλυση του αλγορίθμου, όσο και σε προσομοιώσεις με πραγματικά και συνθετικά σύνολα δεδομένων για να αξιολογήσουμε την απόδοσή του. Επισημαίνουμε τις θεμελιώδεις ιδιότητές του, παρέχουμε αναλυτικές εκφράσεις για τις οριακές τιμές του επιτυγχανόμενου cache hit ratio και μελετάμε την ευαισθησία του αλγορίθμου στις παραμέτρους του καθώς και σε παραμέτους του συστήματος.Στη συνέχεια, εμπλουτίζουμε το παραπάνω πρόβλημα λαμβάνοντας υπόψη την ανάθεση των χρηστών σε κελιά. Δηλαδή, κάθε χρήστης μπορεί να ανατεθεί σε ένα από ένα σύνολο διαφορετικών Σταθμών Βάσης (Base Stations - BS), BS/cache, και να κατευθύνει αιτήματα περιεχομένου στην αντίστοιχη ενταμιευτική μονάδα. Διατυπώνουμε το πρόβλημα της από κοινού ενταμίευσης περιεχομένου, της σύστασης περιεχομένου και της ανάθεσης χρηστών σε κελιά (Joint content Caching, design of Recommendations and user Association - JCRA), με στόχο τη μεγιστοποίηση του συνολικού cache hit ratio. Σχεδιάζουμε έναν αλγόριθμο που επεκτείνει τον αλγόριθμό μας για το JCR πρόβλημα. Πραγματοποιούμε μια επικύρωση απόδειξης της ιδέας (proof-of-concept) που υποδεικνύει τα σημαντικά κέρδη που μπορούν να επιτευχθούν με τον επιπλέον έλεγχο της ανάθεσης χρηστών σε κελιά, τόσο από την άποψη του επιτυγχανόμενου cache hit ratio, όσο και από την άποψη των απαιτούμενων ενταμιευτικών πόρων προκειμένου να επιτευχθεί ίδιο cache hit ratio στο JCR και στο JCRA. Αναλύουμε τις δομικές ιδιότητες ειδικών περιπτώσεων του προβλήματος JCRA, σχεδιάζουμε τη σύνδεσή τους με το Γενικευμένο Πρόβλημα Ανάθεσης (Generalized Assignment Problem - GAP) και εκθέτουμε την NP-πληρότητα του προβλήματος JCRA.Στη συνέχεια, μελετάμε το πρόβλημα της online εκμάθησης βέλτιστων δυναμικών στρατηγικών ανάθεσης χρηστών με Σημεία Πρόσβασης (Access Points - APs), όταν η ζήτηση των χρηστών είναι άγνωστη και χρονικά μεταβαλλόμενη. Στοχεύουμε στην ελαχιστοποίηση μιας ευρείας οικογένειας α-fair συναρτήσεων κόστους, που εκφράζουν διάφορους στόχους στην εκχώρηση φορτίου στην ασύρματη κατερχόμενη ζεύξη (downlink), όπως την ελαχιστοποίηση του συνολικού φορτίου ή την ελαχιστοποίηση συνολικής καθυστέρησης. Η εύρεση μιας βέλτιστης πολιτικής συσχέτισης χρηστών σε δυναμικά περιβάλλοντα είναι δύσκολη, επειδή οι διακυμάνσεις της ζήτησης των χρηστών με την πάροδο του χρόνου είναι μη στάσιμες και είναι δύσκολο να χαρακτηριστούν στατιστικά, γεγονός που εμποδίζει τον υπολογισμό των συσχετίσεων με αποδοτικό κόστος. Υποθέτοντας αυθαίρετες αλλαγές στα μοτίβα ζήτησης των χρηστών με την πάροδο του χρόνου, διατυπώνουμε το πρόβλημα της online εκμάθησης των βέλτιστων πολιτικών ανάθεσης χρηστών σε ΑΡ, χρησιμοποιώντας το πλαίσιο OCO. Εισάγουμε το Optimal Periodic Static (OPS), ένα περιοδικό σχήμα αναφοράς (benchmark) για προβλήματα OL που γενικεύει τα πιο σύγχρονα σχήματα αναφοράς (state-of-the-art). Εκμεταλλευόμαστε τις εγγενείς ιδιότητες του προβλήματός μας και προτείνουμε τον PerOnE, έναν απλό online αλγόριθμο που μαθαίνει να προσαρμόζει δυναμικά την πολιτική ανάθεσης χρηστών σε κελιά υπό αυθαίρετες αλλαγές στα μοτίβα ζήτησης των χρηστών. Συγκρίνουμε τον PerOnE με το περιοδικό μας σχήμα αναφοράς OPS και αποδεικνύουμε ότι απολαμβάνει την no-regret ιδιότητα, με επιπλέον υπογραμμική εξάρτηση στο μεγέθους του δικτύου. Από όσο γνωρίζουμε, αυτή είναι η πρώτη εργασία που εισάγει ένα περιοδικό σημείο αναφοράς για προβλήματα OL και έναν no-regret αλγόριθμο για το online πρόβλημα ανάθεσης χρηστών σε κελιά. Τα θεωρητικά ευρήματά μας επικυρώνονται μέσω αποτελεσμάτων σε ένα σύνολο πραγματικών δεδομένων.Στη συνέχεια, εστιάζουμε στα συστήματα υπολογισμών στην άκρη του δικτύου (edge computing systems) και παρουσιάζουμε ένα μοντέλο που ενσωματώνει ορισμένες πτυχές του AR, όπως η αναγνώριση και ταξινόμηση αντικειμένων μέσω επεξεργασίας εικόνας ή βίντεο. Μελετάμε μια offline περίπτωση εκφόρτωσης υπολογισμού για να μεγιστοποιήσουμε την ακρίβεια ταξινόμησης του περιβάλλοντος των χρηστών εφαρμογών AR. Θεωρούμε ένα σενάριο όπου ο προσδιορισμός περιβάλλοντος πραγματοποιείται μέσω της δημιουργίας πληροφοριών που δημιουργούνται από τον χρήστη, όπως εικόνες ή μικρά αρχεία βίντεο. Είναι η ποσότητα αυτής της πληροφορίας που καθορίζει τελικά την ακρίβεια ταξινόμησης περιβάλλοντος, την οποία μοντελοποιούμε ως μια Διωνυμική τυχαία μεταβλητή. Εισάγουμε το πρόβλημα της μεγιστοποίησης ενός κατώτερου ορίου της ακρίβειας της ταξινόμησης περιβάλλοντος μέσω της συνετής κατανομής πόρων, δηλαδή της εκφόρτωσης υπολογισμού. Λαμβάνουμε υπόψη τους περιορισμούς εύρους ζώνης και υπολογιστικής χωρητικότητας στην άκρη του ασύρματου δικτύου και τις απαιτήσεις καθυστέρησης τέτοιων συστημάτων. Συζητάμε τις δομικές ιδιότητες αυτού του συνδυαστικού προβλήματος, οι οποίες περιλαμβάνουν την έλλειψη μονοτονίας και κυρτότητας της αντικειμενικής συνάρτησης. Σχεδιάζουμε έναν γρήγορο αλγόριθμο για τη λύση του, αποδεικνύοντας το λόγο προσέγγισης του. Στη συνέχεια αποτιμούμε αριθμητικά τον αλγόριθμό μας με βάση μια ρύθμιση που προέρχεται από την υπάρχουσα βιβλιογραφία. Εκτελούμε μια ανάλυση ευαισθησίας στις παραμέτρους των συστημάτων και παρατηρούμε ότι η στεγανότητα (tightness) του λόγου προσέγγισης που αποδείξαμε για τον αλγόριθμό μας επηρεάζεται από την ποσότητα των διαθέσιμων πόρων. Ωστόσο, στην πράξη, ο αλγόριθμός μας φτάνει το 97-98% της ακρίβειας ταξινόμησης υπό πολύ περιορισμένη διαθεσιμότητα ενέργειας και ανοχή καθυστέρησης, ακόμη και όταν είναι διαθέσιμοι μόνο το 3% των πόρων εύρους ζώνης.Τέλος, μελετάμε ένα σύστημα MEC πολλαπλών χρηστών με περιορισμένη ενεργειακή αυτονομία για τις κινητές συσκευές και με περιορισμούς στην υπολογιστική ικανότητα τόσο των κινητών συσκευών όσο και σε έναν edge server όπου οι χρήστες μπορούν να εκφορτώσουν μέρος του υπολογιστικού τους φορτίου. Ορίζουμε τη συνάρτηση χρησημότητάς μας σαν συνάρτηση των "υπολείμματων πόρων" (resource residuals), που αναπαριστούν τη διαφορά μεταξύ των εκχωρημένων πόρων και εκείνων που χρειάζονται στην πραγματικότητα, και στοχεύουμε στην ελαχιστοποίηση του regret, δηλαδή της διαφοράς μεταξύ της χρησιμότητας που λαμβάνεται από το στατικό offline σχήμα αναφοράς που γνωρίζει εκ των προτέρων την εξέλιξη του συστήματος, με τον online αλγόριθμο που σχεδιάζουμε εμείς. Σχεδιάζουμε τον OJOSO, έναν αλγόριθμο που μαθαίνει από κοινού πολιτικές για την εκφόρτωση υπολογισμών και τον προγραμματισμό τους για εκτέλεσή τους στον κοινόχρηστο MEC server. Αποδεικνύουμε ότι ο αλγόριθμός μας είναι ασυμπτωτικά βέλτιστος, δηλαδή, δεν έχει regret σε σχέση με το στατικό offline σχήμα αναφοράς, καθώς και ότι η απόδοσή του είναι ανεξάρτητη από τον αριθμό των συσκευών στο σύστημα. Από την αριθμητική μας αξιολόγηση συμπεραίνουμε ότι το OJOSO προσαρμόζεται σε απρόβλεπτες αλλαγές στα μοτίβα ζήτησης υπολογιστικών πόρων, μαθαίνει να εντοπίζει συσκευές με περιορισμένους πόρους, και μαθαίνει να μοιράζει στις διάφορες υπολογιστικές εργασίες τους περιορισμένους πόρους του MEC server.Συμπερασματικά, αυτή η διδακτορική διατριβή μελετά ένα σύνολο σημαντικών προβλημάτων βελτιστοποίησης που προκύπτουν στο πλαίσιο των δικτύων άκρου (edge computing and networking). Παρουσιάζουμε διατυπώσεις νέων και πρωτότυπων προβλημάτων και αλγόριθμους που οδηγούν σε λύσεις με αποδεδειγμένες εγγυήσεις για την απόδοσή τους, φέρνοντας το Mobile Edge Computing (MEC) ένα βήμα πιο κοντά στην πρακτική υλοποίησή του.