Distributed decision making frameworks for resource allocation in cyber-physical systems

Abstract

Towards realizing the fifth generation (5G) of wireless networks, the Internet of Things (IoT), and the Tactile Internet, intelligent communications and computing is key part of the technological stack. The next generation of wireless networks are expected to be characterized by limited availability of resources, thus, in this dissertation, we tackle the problem of efficient allocation of several types of communications and computing resources, while achieving high quality of service and experience for the devices or the users. Considering the interdependence of the devices while trying to access and share common resources as well as their increasing intelligence which enables them to make choices on supporting self-beneficial properties, it seems natural to adopt more user-centric approaches leading to decentralized solutions. In this PhD dissertation, we considered designing decision making frameworks where devices take advantage of the network's capabilities in order to reduce their resource consumption and more effectively perform their assigned tasks. First, the prolongation of battery life of mobile machine-to-machine (M2M) devices is considered, in order to guarantee and sustain the operation of the IoT system for a longer period of time, while taking into account the management of information of the same nature in a more efficient way, by focusing on the use of social properties and characteristics of the devices. For that reason, a joint interest, physical and energy-aware cluster formation mechanism is proposed so that devices are effectively grouped and a high energy clusterhead can be assigned for each cluster. The clusterhead is then responsible to provide to the rest of the devices enough power to send their data via wireless energy transfer (WET), collect all the information from the devices on its cluster and forward the information to the eNB for further processing. Then, a setting of Multi-access Edge Computing (MEC) is discussed, where servers offer computing resources at the edge of the network to mobile end-users. A multi user - multi MEC server environment is considered where users are willing to offload some of their computational tasks and the MEC servers are setting a price in order to process them. The user is able to chose the server to offload the data to, as well as determine the portion of the task that will be offloaded, while the server will set the price it will charge for each task. In order to achieve the best server selection, a reinforcement learning framework based on stochastic learning automata is adopted, while the amount of data offloading is determined via a non-cooperative game among users, and the optimal announced prices are determined via an optimization problem. The information exchange between the users and the MEC servers until the final offloading decision, is handled and realized by a Software Defined Network (SDN) controller. In the rest of the dissertation, we introduced the concept of users' behavioural characteristics in order to capture and reflect the fact that users do not act as neutral maximizers but instead exhibit risk-aware behaviour. A MEC setting is considered as well, where multiple user devices are willing to offload their tasks to a MEC server responsible for handling them. Under this setting, the MEC server is considered as a Fragile Common Pool Resource (CPR), meaning that the more the server is used, the higher the probability of failure to execute its assigned tasks, resulting in losses for the users. The problem is modeled as a non-cooperative game between the users, where each user should choose the portion of the tasks to be offloaded to the server by selecting the amount of data to send. Towards capturing the users' behavioral characteristics in the data offloading decision-making process, we adopt the principles of Prospect Theory in order to model the users' decisions under risk and uncertainty of outcome. Additionally, a usage based pricing policy is considered to balance the usage of the MEC server by the users, since the additional cost prohibits users to over-exploit the servers' resources and thus reduces the Probability of Failure (PoF) of the server. Finally, we extended the aforementioned concept on a multi-user multi-server environment where the additional problems of users' server selection and MEC servers' price selection arise. In order to more holistically address the users' decision-making process, we considered the server selection and the amount of offloading data selection as a joint optimization problem, allowing users to choose the combination that maximizes their perceived utility. In order to tackle the MEC servers' price selection problem we proposed two different approaches, a game-theoretic approach and a reinforcement learning one, considering different information availability scenarios on the system. The overall framework is modeled as a Stackelberg game where the servers are considered leaders, making their pricing decisions based on one of the proposed approaches, and the users are considered followers, making their data offloading decisions based on the prospect theoretic principles.

Στην προσπάθεια υλοποίησης της πέμπτης γενιάς (5G) ασυρμάτων δικτύων, του Διαδικτύου των Πραγμάτων (Internet of Things) και του Απτού Διαδικτύου (Tactile Internet), η ανάπτυξη έξυπνων μεθόδων επικοινωνίας και υπολογισμού είναι κομβικής σημασίας. Η επόμενη γενιά ασύρματων δικτύων θα χαρακτηρίζεται από περιορισμένη διαθεσιμότητα πόρων, και έτσι στην παρούσα διατριβή προσπαθούμε να αντιμετωπίσουμε το πρόβλημα της αποτελεσματικής διάθεσης αυτών των υπολογιστικών και επικοινωνιακών πόρων, επιτυγχάνοντας παράλληλα υψηλή ποιότητα υπηρεσιών και εμπειρίας για τις συσκευές και τους χρήστες. Λαμβάνοντας υπόψιν την αλληλεξάρτηση των συσκευών, καθώς έχουν πρόσβαση και μοιράζονται κοινούς πόρους, αλλά και λόγω της αυξανόμενης νοημοσύνης που διαθέτουν, η οποία τους επιτρέπει να κάνουν οι ίδιες επιλογές με στόχο το προσωπικό τους όφελος, φαίνεται φυσική η υιοθέτηση μιας πιο ατομοκεντρικής προσέγγισης, η οποία οδηγεί σε πιο αποκεντρωμένες λύσεις. Στην παρούσα διδακτορική διατριβή εξετάσαμε τη δημιουργία πλαισίων λήψης αποφάσεων, όπου οι συσκευές εκμεταλλεύονται τις δυνατότητες του δικτύου προκειμένου να μειώσουν την κατανάλωση πόρων τους και να εκτελέσουν αποτελεσματικότερα τις εργασίες τους. Αρχικά, εξετάσαμε την επέκταση της διάρκειας ζωής της μπαταρίας κινητών συσκευών σε περιβάλλοντα επικοινωνίας μηχανή με μηχανή, προκειμένου να διασφαλιστεί η λειτουργία του συστήματος Διαδικτύου των Πραγμάτων (IoT) για μεγαλύτερο χρονικό διάστημα, λαμβάνοντας υπόψη τη διαχείριση πληροφοριών παρόμοιου περιεχομένου και εστιάζοντας στη χρήση κοινωνικών ιδιοτήτων και χαρακτηριστικών των συσκευών. Για το λόγο αυτό, προτείναμε έναν μηχανισμό συσταδοποίησης που λαμβάνει υπόψη τόσο την φυσική απόσταση και την ενεργειακή διαθεσιμότητα, όσο και το περιεχόμενο των δεδομένων που διαθέτουν, έτσι ώστε να πετύχουμε αποδοτική ομαδοποίηση των συσκευών, καθώς και να ορίσουμε έναν υψηλής ενεργειακής διαθεσιμότητας εκπρόσωπο για κάθε ομάδα. Ο εκπρόσωπος αυτός είναι υπεύθυνος για να παρέχει στις υπόλοιπες συσκευές αρκετή ισχύ για την αποστολή των δεδομένων τους μέσω ασύρματης μεταφοράς ενέργειας (Wireless Energy Transfer), τη συλλογή όλων των πληροφοριών από τις συσκευές της ομάδας του και την προώθησή τους στον σταθμό βάσης για περαιτέρω επεξεργασία. Στη συνέχεια επικυρωθήκαμε στα περιβάλλοντα Υπολογισμού στα Άκρα Πολλαπλής Πρόσβασης (Multi-access Edge Computing), όπου οι διακομιστές προσφέρουν υπολογιστικούς πόρους στους τελικούς κινητούς χρήστες. Μελετήθηκε ένα σενάριο πολλαπλών χρηστών και πολλαπλών διακομιστών στο οποίο οι χρήστες επιθυμούν να αποφορτίσουν μέρος των υπολογιστικών τους εργασιών και οι διακομιστές ορίζουν μια τιμή για την παροχή της υπηρεσίας τους. Ο χρήστης είναι σε θέση να επιλέξει τον διακομιστή στον οποίο θα στείλει τα δεδομένα του, καθώς και τον όγκο των δεδομένων που θα στείλει, ενώ ο διακομιστής θα επιλέξει την τιμή που θα χρεώσει για κάθε εργασία. Για να πετύχουμε την βέλτιστη επιλογή διακομιστή, υιοθετούμε ένα πλαίσιο ενισχυτικής μάθησης βασισμένο στα στοχαστικά αυτόματα, ενώ ο όγκος των δεδομένων καθορίζεται μέσω ενός μη-συνεργατικού παιγνίου μεταξύ των χρηστών, και η βέλτιστη τιμολόγηση καθορίζεται μέσω ενός προβλήματος βελτιστοποίησης. Η ανταλλαγή πληροφοριών μεταξύ χρηστών και διακομιστών διευκολύνεται από έναν ελεγκτή Δικτύωσης Καθορισμένης από Λογισμικό (Software Defined Networking). Στην υπόλοιπη διατριβή, εισάγαμε την έννοια των συμπεριφορικών χαρακτηριστικών των χρηστών, προκειμένου να αποτυπώσουμε το γεγονός ότι οι χρήστες δε λειτουργούν ως ουδέτεροι μεγιστοποιητές, αλλά αντίθετα επιδεικνύουν πιο περίπλοκη συμπεριφορά σε συνθήκες αβεβαιότητας. Μελετάμε ένα περιβάλλον Υπολογισμού στα Άκρα Πολλαπλής Πρόσβασης με πολλούς χρήστες και έναν διακομιστή, ο οποίος θεωρείται ως εύθραυστη πηγή κοινόχρηστων πόρων, και έτσι με βάση τη χρήση του ορίζεται και η πιθανότητα αποτυχίας εκτέλεσης των εργασιών που έχει αναλάβει, με αντίστοιχες απώλειες για τους χρήστες. Το πρόβλημα διαμορφώνεται ως ένα μη-συνεργατικό παίγνιο μεταξύ των χρηστών, με το οποίο οι χρήστες επιλέγουν τον όγκο δεδομένων που θα αποφορτώσουν στον διακομιστή. Προκειμένου να μοντελοποιηθούν αυτά τα συμπεριφορικά χαρακτηριστικά, υιοθετήσαμε τις αρχές της Θεωρίας Προοπτικής και επιλέχθηκε μια πολιτική τιμολόγησης που βασίζεται στη χρήση του διακομιστή από τους χρήστες, με σκοπό να αποτρέπεται η αλόγιστη χρήση του και να μειωθεί η πιθανότητα αποτυχίας του. Τέλος επεκτείναμε την παραπάνω ιδέα σε ένα περιβάλλον πολλαπλών χρηστών και πολλαπλών διακομιστών, όπου εμφανίζονται δυο επιπλέον προβλήματα, το πρόβλημα της επιλογής διακομιστή από τους χρήστες και την επιλογή τιμών από τους διακομιστές. Προκειμένου να αντιμετωπιστεί πιο ολιστικά το πρόβλημα, ορίσαμε την επιλογή διακομιστή και την επιλογή όγκου εκφόρτωσης ως ένα κοινό πρόβλημα βελτιστοποίησης, επιτρέποντας στους χρήστες να επιλέξουν τον συνδυασμό που μεγιστοποιεί την αντιλαμβανόμενη ωφελιμότητά τους. Για να αντιμετωπιστεί το πρόβλημα της επιλογής τιμολόγησης των υπηρεσιών, προτείναμε δύο διαφορετικές προσεγγίσεις, μια βασισμένη στη Θεωρία Παιγνίων, και μια στην ενισχυτική μάθηση, ανάλογα με τη διαθεσιμότητα πληροφορίας στο σύστημα. Το συνολικό πρόβλημα διαμορφώθηκε ως ένα παίγνιο Stackelberg όπου οι διακομιστές έχουν τον ρόλο του ηγέτη, παίρνοντας αποφάσεις για την τιμολόγηση, και οι χρήστες θεωρούνται ως ακόλουθοι, λαμβάνοντας τις αποφάσεις εκφόρτωσης των δεδομένων τους με βάση τη Θεωρία Προοπτικής.