Resource allocation and incentive mechanism design in next generation wireless communication and mobile computing networks

Abstract

In light of the broader vision for digitalization and smart-X vertical industries (e.g., smart city, healthcare, manufacturing), an unprecedented increase of data-hungry and compute-intensive applications takes place, imposing stringent communication and computing requirements on the network. As a means of extending connectivity, increasing spectral and energy efficiency, and reducing latency, several prominent technologies and architectural paradigms emerge as key enablers of the Next Generation (NextG) 5G wireless networks. In this context, the simplistic adoption of existing solutions to traditional resource management problems is inefficient in exploring and exploiting the network’s capabilities. On the contrary, several degrees of freedom should be concurrently determined about the nature and type of the resources to be allocated while accounting for the multifaceted competition between different stakeholders. In this thesis, we tackle the problem of efficient resource allocation in heterogeneous and multi-tier wireless communication and mobile computing networks in a holistic, though distributed, manner. In the direction of self-organizing networks, where each network entity makes autonomous decisions regarding its resource utilization and allocation, we develop novel frameworks that capture the interdependencies between different network entities’ behaviors, interactions, and decisions by accounting for their different and/or conflicting objectives and the existence of incompleteness of information between them. To provide such a real-life spirit in modeling the resource management problems, we resort to Game Theory and Contract Theory, which result in low-complexity methodologies and algorithms for solving the formulated problems. First, multi-variable resource allocation problems are studied in heterogeneous and multi-tier wireless communication networks. Targeting to address the problem of incomplete/partial Channel State Information (CSI) from the Base Stations’ (BSs’) behalf, as well as the user-BS conflict regarding the users’ uplink transmission power investment, a synergistic approach based on the principles of Contract Theory is initially introduced. The BSs design a menu of contracts based on their statistical knowledge about the users’ CSI, which comprise indicative power levels along with a corresponding reward, such that the designed power levels enable the decoding of the users’ transmitted signals at the BSs’ receivers via the combination of Non-Orthogonal Multiple Access (NOMA) and Successive Interference Cancellation (SIC). The users autonomously select the one contract out of the menu that best fits their experienced channel conditions while employing a Reinforcement Learning (RL) algorithm to distributively determine the most beneficial BS association. Taking one step further to the underlying network architecture and employed technologies, we aim to concurrently account for and properly configure the resources across the wireless access and backhaul network parts of an Unmanned Aerial Vehicle (UAV)-assisted and Reconfigurable Intelligent Surface (RIS)-aided communication network. By capitalizing on the structural hierarchy between the UAV-mounted BS and the users, a Stackelberg game is formulated to distributively deal with a highly combinatorial resource management problem. The UAV, acting as leader, determines the RIS’s phase shifts such that the sum users’ signal strength is maximized in the uplink and, in a second phase, jointly calculates the bandwidth and uplink transmission power allocation in the backhaul link to the core network. In the third phase, the users, acting as the followers, optimize their uplink transmission powers to the UAV in a distributed manner. The second and third phases are iteratively repeated to conclude with the game’s Stackelberg equilibrium point, at which the end-to-end energy efficiency is maximized. Respecting the need for converged radio and computing resource allocation frameworks within the context of NextG 5G networks, a multi-tier mobile computing topology is considered, and the joint problem of computation task offloading and uplink transmission/offloading power allocation is studied. In contrast to the existing literature, where single-tier computing networks are modeled, consisting of an edge, a fog, or a cloud service layer, concurrently utilizing a wide range of computing capabilities and options is pursued. Given the users’ selfish behavior towards offloading to the edge due to the latter’s proximity, an incentivization mechanism based on Contract Theory is designed to motivate them to allow a percentage of their initially offloaded tasks to the edge to be further forwarded and processed at the fog. Having determined this percentage, the ultimate users’ computation task offloading and uplink transmission power to edge are jointly derived in a distributed manner by playing a game among them. By utilizing multiple computing service layers, an energy-efficient solution is derived while extending the edge service layer’s computing capacity. Finally, aiming to further study the distribution of computation tasks horizontally, i.e., within the same computing tier, while considering multiple servers, a multi-server Multi-Access Edge Computing (MEC) network is modeled. The users leverage the different available Radio Access Networks (RANs) nearby to offload their compute-intensive and latency-critical applications to multiple MEC servers simultaneously. To address the critical interference management problem under the resulting multi-user multi-server network topology while being motivated by the advancements in the non-orthogonal multiple access techniques, the application of Rate-Splitting Multiple Access (RSMA) is scrutinized. In this context, the minimization of the sum of the users’ maximum experienced delay among the different MEC servers is pursued by jointly optimizing their computation task offloading ratios, rate, uplink transmission power, and computing resource allocation across the offloading MEC servers. The formulated joint optimization problem is analytically solved using conventional optimization techniques based on the Karush-Kuhn-Tucker (KKT) conditions. This complements the ultimate purpose of this thesis to provide a holistic approach and view to the converged wireless communication and mobile computing networks. The considered resource management problems are thoroughly evaluated via modeling and simulation. The proposed frameworks’ pure operational characteristics and the designed algorithms’ convergence behavior are examined under different scenarios and values, while comparative results against other benchmarking and state-of-the-art solutions are provided to demonstrate the proposed frameworks’ effectiveness and efficiency.

Υπό το πρίσμα του ευρύτερου οράματος για ψηφιοποίηση και μετασχηματισμό των κάθετων βιομηχανιών (π.χ. έξυπνες πόλεις, έξυπνο σύστημα υγείας, έξυπνα εργοστάσια), σημειώνεται μια άνευ προηγουμένου αύξηση των εφαρμογών με εντατικές απαιτήσεις ως προς τον όγκο των δεδομένων που διαχειρίζονται και την αναγκαία υπολογιστική ισχύ για την επεξεργασία αυτών. Αυτό έχει ως αποτέλεσμα την επιβολή αυστηρών απαιτήσεων που αφορούν το ασύρματο δίκτυο επικοινωνιών και υπολογισμών. Ως μέσο επέκτασης της συνδεσιμότητας, αύξησης της φασματικής και ενεργειακής απόδοσης και μείωσης του λανθάνοντος χρόνου, μια πληθώρα τεχνολογιών και αρχιτεκτονικών παραδειγμάτων αναδεικνύονται ως βασικά μέσα ενεργοποίησης και ενδυνάμωσης των ασύρματων δικτύων 5G επόμενης γενιάς. Σε αυτό το πλαίσιο, η απλοϊκή υιοθέτηση υφιστάμενων λύσεων σε παραδοσιακά προβλήματα κατανομής πόρων είναι αναποτελεσματική για την εξερεύνηση και την εκμετάλλευση των δυνατοτήτων του δικτύου. Αντίθετα, αρκετοί βαθμοί ελευθερίας πρέπει να καθορίζονται ταυτόχρονα σχετικά με τη φύση και το είδος των πόρων που κατανέμονται στο δίκτυο, λαμβάνοντας ταυτόχρονα υπόψιν τον πολύπλευρο ανταγωνισμό μεταξύ των διαφορετικών ενδιαφερόμενων μερών (π.χ. συνδρομητές, πάροχοι). Σε αυτή τη διατριβή, αντιμετωπίζουμε το πρόβλημα της αποτελεσματικής κατανομής πόρων σε ετερογενή και πολυεπίπεδα ασύρματα δίκτυα επικοινωνιών και κινητών υπολογισμών με έναν ολιστικό, αλλά κατανεμημένο, τρόπο. Προς την κατεύθυνση των αυτο-οργανωμένων δικτύων, όπου κάθε δικτυακή οντότητα λαμβάνει αυτόνομες αποφάσεις σχετικά με τη χρήση και την κατανομή των πόρων της, αναπτύσσουμε νέα πλαίσια τα οποία αντικατοπτρίζουν τις αλληλεξαρτήσεις μεταξύ των συμπεριφορών, των αλληλεπιδράσεων και των αποφάσεων των διαφορετικών διακτυακών οντοτήτων, λαμβάνοντας υπόψιν τους διαφορετικούς ή/και αντικρουόμενους στόχους τους, καθώς και την ύπαρξη ελλιπούς πληροφόρησης μεταξύ τους. Προκειμένου να προσδοθεί μια τέτοια ρεαλιστική χρειά στη μοντελοποίηση των προβλημάτων κατανομής πόρων, καταφεύγουμε στη Θεωρία Παιγνίων (Game Theory) και στη Θεωρία Συμβολαίων (Contract Theory), οι οποίες με τη σειρά τους οδηγούν σε μεθοδολογίες και αλγόριθμους χαμηλής πολυπλοκότητας για την επίλυση των αντίστοιχων προβλημάτων.Αρχικά, μελετώνται προβλήματα κατανομής πόρων πολλαπλών μεταβλητών σε ετερογενή και πολυεπίπεδα ασύρματα δίκτυα επικοινωνιών. Με στόχο την αντιμετώπιση του προβλήματος της ελλιπούς/μερικής πληροφόρησης των σταθμών βάσης σχετικά με την κατάσταση καναλιού (Channel State Information - CSI), καθώς και της αντίφασης μεταξύ των χρηστών και των σταθμών βάσης σχετικά με το επίπεδο ισχύος μετάδοσης στη ζεύξη ανόδου, εισάγεται μια συνεργατική προσέγγιση μεταξύ των δύο αυτών μερών, η οποία βασίζεται στις αρχές της Θεωρίας Συμβολαίων. Οι σταθμοί βάσης σχεδιάζουν ένα σύνολο συμβολαίων που αποτελούνται από ενδεικτικά επίπεδα ισχύος για τη ζεύξη ανόδου μαζί με μια αντίστοιχη ανταμοιβή προς τους χρήστες, κάνοντας χρήση της στατιστικής τους γνώσης σχετικά με την κατάσταση του καναλιού των χρηστών. Τα επίπεδα ισχύος των συμβολαίων επιλέγονται με τέτοιο τρόπο ώστε να επιτρέπουν την αποκωδικοποίηση των μεταδιδόμενων σημάτων των χρηστών από τους δέκτες των σταθμών βάσης, κάνοντας χρήση των τεχνικών μη ορθογωνικής πολλαπλής πρόσβασης (Non-Orthogonal Multiple Access - NOMA) και διαδοχικής ακύρωσης παρεμβολών (Successive Interference Cancellation - SIC). Οι χρήστες επιλέγουν αυτόνομα ένα συμβόλαιο από το σύνολο των συμβολαίων, το οποίο ταιριάζει καλύτερα στις συνθήκες καναλιού τους. Επιπλέον των παραπάνω, αναπτύσσεται ένας αλγόριθμος ενισχυτικής μάθησης (Reinforcement Learning - RL) προκειμένου κάθε χρήστης να προσδιορίζει αυτόνομα και κατανεμημένα την περισσότερο ωφέλιμη για αυτόν συσχέτισή του με έναν από τους διαθέσιμους σταθμούς βάσης. Πηγαίνοντας ένα βήμα παραπέρα όσον αφορά την υποκείμενη αρχιτεκτονική δικτύου και τις χρησιμοποιούμενες τεχνολογίες, στοχεύουμε να συνυπολογίσουμε και να κατανείμουμε βέλτιστα τους πόρους στα τμήματα ασύρματης πρόσβασης (access network) και οπισθόζευξης (backhaul network) ενός δικτύου υποβούμενου από ένα μη επανδρωμένο εναέριο όχημα (Unmanned Aerial Vehicle - UAV) και μια αναδιαμορφώσιμη έξυπνη επιφάνεια (Reconfigurable Intelligent Surface - RIS). Αξιοποιώντας τη δομική ιεραρχία του δικτύου, διαμορφώνεται ένα παίγνιο Stackelberg μεταξύ του σταθμού βάσης που φέρει το UAV και των χρηστών για την κατανεμημένη επίλυση του ακόλουθου συνδυαστικού προβλήματος κατανομής πόρων. Το UAV, ενεργώντας ως ηγέτης, καθορίζει τις μετατοπίσεις φάσης του RIS έτσι ώστε η ισχύς του σήματος του συνόλου των χρηστών στη ζεύξη ανόδου να μεγιστοποιείται. Επίσης, το UAV, σε δεύτερη φάση, υπολογίζει την από κοινού κατανομή εύρους ζώνης συχνοτήτων και ισχύος στη ζεύξη ανόδου του οπισθοζευκτικού δικτύου προς το δίκτυο κορμού (core network). Σε τρίτη φάση, οι χρήστες, ενεργώντας ως ακόλουθοι, βελτιστοποιούν την προσωπική τους ισχύ στη ζεύξη ανόδου του δικτύου πρόσβασης προς το UAV, επίσης με κατανεμημένο τρόπο. Η δεύτερη και τρίτη φάση επαναλαμβάνονται έως ότου βρεθεί το σημείο ισορροπίας του παιγνίου Stackelberg, στο οποίο επιτυγχάνεται η μεγιστοποίηση της ενεργειακής απόδοσης του δικτύου πρόσβασης και οπισθόζευξης από άκρο σε άκρο. Σεβόμενοι την ανάγκη για από κοινού μηχανισμούς κατανομής πόρων σε ασύρματα δίκτυα επικοινωνιών και δίκτυα κινητών υπολογισμών, εξετάζεται μια πολυεπίπεδη τοπολογία κινητών υπολογισμών και μελετάται το από κοινού πρόβλημα της εκφόρτωσης εργασιών υπολογισμού και κατανομής ισχύος μετάδοσης/εκφόρτωσης. Σε αντίθεση με την υπάρχουσα βιβλιογραφία, όπου μοντελοποιούνται δίκτυα υπολογισμών ενός επιπέδου, δηλαδή αποτελούμενα είτε από ένα επίπεδο υπολογιστικής άκρης (edge), ομίχλης (fog) ή νέφους (cloud), επιδιώκεται ταυτόχρονα η χρήση ενός ευρέος φάσματος υπολογιστικών δυνατοτήτων και επιλογών. Δεδομένης της εγωιστικής συμπεριφοράς των χρηστών προς την εκφόρτωση στην άκρη του δικτύου λόγω της εγγύτητας του τελευταίου, σχεδιάζεται ένας μηχανισμός κινήτρων που βασίζεται στη Θεωρία Συμβολαίων για να παρακινήσει τους χρήστες να επιτρέψουν ένα ποσοστό των αρχικών εκφορτωμένων εργασιών τους στο επίπεδο της άκρης να προωθηθούν περαιτέρω και να επεξεργαστούν στο επίπεδο της ομίχλης. Έχοντας καθορίσει αυτό το ποσοστό, το τελικό ποσοστό εκφόρτωσης υπολογιστικών εργασιών των χρηστών στην άκρη του δικτύου, καθώς και το επίπεδο ισχύος στη ζεύξη ανόδου κατά την εκφόρτωση, υπολογίζονται με κατανεμημένο τρόπο, διαμορφώνοντας ένα μη συνεργατικό παίγνιο μεταξύ των χρηστών. Με τη χρήση πολλαπλών επιπέδων υπολογισμών, προκύπτει μια ενεργειακά αποδοτική λύση, ενώ επεκτείνεται η υπολογιστική ικανότητα του επιπέδου υπολογισμών άκρης.Τέλος, με στόχο την περαιτέρω μελέτη της κατανομής των εργασιών υπολογισμού οριζόντια, δηλαδή εντός του ίδιου επιπέδου υπολογισμών θεωρώντας πολλαπλούς διακομιστές, μοντελοποιείται ένα δίκτυο υπολογιστικών συστημάτων στην άκρη του δικτύου (Multi-access Edge Computing - MEC) πολλαπλών διακομιστών. Οι χρήστες αξιοποιούν τα διαφορετικά διαθέσιμα δίκτυα ραδιοπρόσβασης (Radio Access Networks - RAN) για να εκφορτώσουν τις υπολογιστικά απαιτητικές και χρονικά κρίσιμες εφαρμογές τους σε πολλαπλούς διακομιστές MEC ταυτόχρονα. Για την αντιμετώπιση του κρίσιμου προβλήματος διαχείρισης παρεμβολών υπό την προκύπτουσα τοπολογία δικτύου πολλαπλών διακομιστών πολλαπλών χρηστών, καθώς και υποκινούμενοι από τις εξελίξεις στις τεχνικές μη ορθογωνικής πολλαπλής πρόσβασης, εξετάζεται η εφαρμογή της τεχνικής πολλαπλής πρόσβασης διαίρεσης ρυθμού (Rate-Splitting Multiple Access - RSMA). Υπό αυτό το πλαίσιο, επιδιώκεται η ελαχιστοποίηση του αθροίσματος της μέγιστης μετρούμενης καθυστέρησης από την πλευρά των χρηστών μεταξύ των διαφορετικών διακομιστών MEC μέσω της από κοινού βελτιστοποίησης των ποσοστών εκφόρτωσης υπολογιστικών εργασιών, του ρυθμού και της ισχύος μετάδοσης/εκφόρτωσης στη ζεύξη ανόδου από τους χρήστες, καθώς και της κατανομής υπολογιστικών πόρων από τους διάφορους διακομιστές MEC προς τους χρήστες. Το παραπάνω από κοινού πρόβλημα βελτιστοποίησης επιλύεται αναλυτικά, χρησιμοποιώντας κλασσικές μεθόδους βελτιστοποίησης που βασίζονται στις συνθήκες Karush-Kuhn-Tucker (KKT). Η μελέτη και επίλυση του προβλήματος αυτού συμπληρώνει τον απώτερο σκοπό της παρούσας διατριβής να παράσχει μια ολιστική προσέγγιση και άποψη ως προς την κατανομή πόρων σε συγκλίνοντα ασύρματα δίκτυα επικοινωνιών και κινητών υπολογισμών. Τα εξεταζόμενα προβλήματα διαχείρισης πόρων αξιολογούνται αναλυτικά μέσω μοντελοποίησης και προσομοίωσης. Τα λειτουργικά χαρακτηριστικά των προτεινόμενων πλαισίων κατανομής πόρων και η συμπεριφορά σύγκλισης των σχεδιαζόμενων αλγορίθμων εξετάζονται κάτω από διαφορετικά σενάρια και τιμές, ενώ παρέχονται συγκριτικά αποτελέσματα έναντι άλλων λύσεων από την υπάρχουσα πρόσφατη βιβλιογραφία για να καταδειχθεί η αποτελεσματικότητα και αποδοτικότητά τους.