Resource allocation, content recommendation and online learning mechanisms for mobile edge networks

Abstract

The Mobile Edge Computing (MEC) paradigm brings computing and cache capacity resources in the proximity of users. It gives rise to a new ecosystem of services, such as video delivery and Augmented Reality (AR) ones, while reducing the latency that is experienced by users and lowering network service costs. The main challenges that MEC faces are related to the scarcity of resources at the network edge, the unpredictability of important system parameters, such as traffic, content and computation demand, and the ultra-low latency requirements that must be satisfied. In this thesis we deal with the challenges above, towards the optimization of two MEC goals: content delivery and real-time analytics at the edge of the network. We present resource allocation mechanisms and methods that automate the resource allocation, for fifth-generation (5G), Beyond-5G (B5G) and sixth-generation (6G) communication systems, accounting for edge resources such as caches, computational resources of mobile devices and edge servers, bandwidth and energy. We tackle both offline and Online Learning (OL) instances of optimization problems that span content recommendations and caching, user association and allocation of computing resources. We use a variety of mathematical tools to solve these problems, such as combinatorial optimization, convex optimization and Online Convex Optimization (OCO), a special case of OL. We analyse and we exploit the structural properties of the formulated optimization problems, either by designing algorithms ex novo, or by adapting existing techniques to our settings. We provide cost-efficient, fast and elegant solutions with provable performance guarantees, for a variety of important problems that arise within the MEC context. We start by studying the interplay of caching and Recommender Systems (RSs) mechanisms. Caching decisions typically seek to cache content that maximizes cache hit ratio. Recommendation systems, on the contrary, focus on individual users and recommend to them appealing content in order to elicit further content consumption. We explore how these, phenomenally conflicting, objectives can be jointly addressed. First, we formulate an optimization problem for the Joint Caching and Recommendation (JCR) decisions, aiming to maximize the cache hit ratio under minimal controllable distortion of the in- herent user content preferences by the issued recommendations. Then, we prove that the problem is NP-complete and that its objective function lacks those monotonicity and submodularity properties that would guarantee its approximability. Hence, we proceed to introduce a simple algorithm with polynomial time complexity, that essentially serves as a form of lightweight control over recommendations so that they are both appealing to end-users and friendly to network resources. We draw on both analysis and simula- tions with real and synthetic datasets to evaluate the performance of the algorithm. We point out its fundamental properties, provide analytical bounds for the achieved cache hit ratio, and study its sensitivity to its own as well as system-level parameters. We then enhance the problem setting above by considering user association control, i.e., each user may be associated to one out of a set of different BSs/caches, and direct content requests to that cache. We formulate the problem of Joint content Caching, design of Recommendations and user Association (JCRA), aiming at the maximization of the total cache hit ratio. We design an algorithm that extends our JCR algorithm. We perform a proof-of-concept validation that indicates that significant gains, both in terms of the achieved cache hit ratio, and in terms of the cache resources that are needed in order to obtain the same cache hit ratio in JCR and JCRA, can be obtained by controlling user association. We analyse the structural properties of special cases of the JCRA problem, we draw their connection with the Generalized Assignment Problem (GAP), and we expose the NP-completeness of the JCRA problem. Next, we study the problem of online learning optimal user association policies to Access Points (APs), in the presence of unknown and time-varying traffic demand. We aim at minimizing a broad family of α-fair cost functions that express various objectives in load assignment in the wireless downlink, such as total load or total delay minimization. Finding an optimal user association policy in dynamic environments is challenging, because traffic demand fluctuations over time are non-stationary and difficult to char- acterize statistically, which obstructs the computation of cost-efficient associations. As- suming arbitrary traffic patterns over time, we formulate the problem of online learning of optimal user association policies using the OCO framework. We introduce a periodic benchmark for OL problems that generalizes state-of-the-art benchmarks. We exploit inherent properties of the online user association problem and propose PerOnE, a simple online learning scheme that dynamically adapts the association policy to arbitrary traf- fic demand variations. We compare PerOnE against our periodic benchmark and prove that it enjoys the no-regret property, with additional sublinear dependence of the net- work size. To the best of our knowledge, this is the first work that introduces a periodic benchmark for OL problems, and a no-regret algorithm for the online user association problem. Our theoretical findings are validated through results on a real-trace dataset. Afterwards, we focus on edge computing systems, and we present a model that incorporates some aspects of AR, such as object recognition and classification through image or video processing. We study an offline instance of computation offloading to maximize the classification precision of the context of users of AR applications. We consider a scenario where context identification is performed through elicitation of user-generated information, such as images or small video files. It is the quantity of this information that ultimately determines the context classification precision, which we model as a Binomial random variable. We introduce the problem of maximizing a lower bound of the precision of context classification through prudent resource allocation, namely computation offloading. We consider bandwidth and computational capacity limita- tions at the wireless network edge, and the latency requirements of such systems. We discuss the structural properties of this combinatorial problem, which include the lack of monotonicity and convexity of the objective function. We design a fast algorithm for its solution, proving an approximation ratio for it. We then numerically evaluate our algorithm based on a setting that is derived from existing literature. We perform a sensitivity analysis over the systems’ parameters and observe that the tightness of the approximation ratio we proved for our algorithm is affected by the amount of available resources. However, in practice, our algorithm reaches 97-98% classification accuracy under very limited energy availability and delay tolerance, even when only 3% of the bandwidth resources are available. Finally, we study a multi-user MEC system with limited energy autonomy for the mobile devices and with limitations on the computing capability of both mobile devices and at an edge server where users can offload part of their computation load. We define a utility over “resource residuals”, that capture the difference between the assigned resources, and those needed, and we aim at the minimization of regret, i.e., of the difference between the utility obtained by the static offline benchmark that knows the system evolution in hindsight, and our online decision policy. We design OJOSO, an algorithm that jointly learns policies for offloading computations and scheduling them for execution at the shared MEC server. We prove that our algorithm is asymptotically optimal, i.e., it has no regret over the static benchmark, and that its performance is independent of the number of devices in the system. From our numerical evaluation we conclude that OJOSO adapts to unpredictable demand changes, it learns to identify resource-limited devices, and it learns to share the server’s resources. Overall, this Ph.D. thesis tackles a set of important optimization problems that arise in the context of edge computing and networking. We present novel problem formulations and algorithms that lead to solutions with provable performance guarantees, bringing the Mobile Edge Computing (MEC) paradigm a step closer to its practical realization.

Τα 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) ένα βήμα πιο κοντά στην πρακτική υλοποίησή του.