Dynamic resource allocation and computational offloading at the network edge for internet of things applications

Abstract

In the Internet of Things (IoT) era, mobile devices possess powerful hardware and networking capabilities, however they still fall short when it comes to executing compute-intensive applications. Computation Offloading, i.e., delegating resource consuming tasks to servers located at the Network Edge, contributes towards moving to a Mobile Cloud Computing paradigm, which will potentially assist towards alleviating the computational strain from the mobile devices. The motivation for this thesis is to deal with the inherent challenges of computational offloading, the most important of which is resource allocation under constraints, while guaranteeing the Quality of Service (QoS) and Quality of Experience (QoE) delivered to the users. Throughout this thesis, Control Theory concepts are leveraged as this domain offers a plethora of tools that can be utilised to tackle the emerging challenges. Additionally, concepts from Probability Theory are exploited as well. Specifically, in this work, an effort is made to address the following crucial research challenges in resource allocation and computational offloading: i) modeling the heterogeneous entities of the system (i.e., the infrastructure, users, applications resources and the interactions among them), ii) estimating the workload that will be offloaded during a future time window (by predicting the mobile devices' positions), iii) optimizing resource allocation by dynamically allocating (scaling) the available resources at the network edge while respecting the given constraints, e.g., guaranteed execution of the estimated workload, delivering the expected QoS/QoE and minimizing energy consumption of the edge infrastructure and, finally, iv) optimizing computational offloading strategies. The aim of this thesis is to offer solutions to the above-mentioned challenges, which can be combined into frameworks applicable to real-world edge infrastructures that will allow IoT devices and applications to reach their full potential. To this end, a two-level dynamic resource allocation and admission control mechanism for a cluster of edge servers is developed, to offer an alternative choice to mobile users for executing their tasks. At the lower level, the dynamic behavior of edge servers is modeled by a set of linear systems, and linear controllers are designed to meet the system's constraints and QoS metrics, while at the upper level, an optimizer tackles the problems of load balancing and application placement (bundled in Virtual Machines, VMs) towards maximizing of the number the offloaded requests. The evaluation illustrates the effectiveness of the proposed offloading mechanism regarding the performance indicators (e.g., the application's average response time) and the optimal utilization of the computational resources of the edge servers. Then, the main mechanism of this framework is put to a test; a three-level Cyber-Physical Social System (CPSS) for early fire detection is presented, with an aim to assist public authorities to promptly identify and act on emergency situations. In general, a CPSS tightly integrates computer systems with the physical world and human activities. Specifically, at the bottom level, the system’s architecture involves IoT nodes enabled with sensing and forest monitoring capabilities. Additionally, in this level, the crowd sensing paradigm is exploited to aggregate environmental information collected by end user devices present in the area of interest. Since the IoT nodes suffer from limited computational and energy resources, the resource allocation and admission control mechanism, at the middle level, facilitates the offloaded data processing, regarding possible fire incidents. At the top level, a decision-making service deployed on Cloud nodes, integrates data from various sources, including users’ information on social media, and evaluates the situation's criticality. In this part, the dynamic resource scaling mechanism is designed to address the demanding QoS requirements of this IoT-enabled time and mission critical application. The experimental results indicate that the vertical and horizontal scaling on the Edge Computing layer is beneficial for both the performance and the energy consumption of the IoT nodes. Additionally, a switching computational offloading mechanism for Industry 4.0 applications is discussed. These applications rely on mobile robotic agents that execute many complex tasks that have strict safety and time requirements. Under this setting, the Edge Computing service delivery model allows the robotic agents to offload their computationally intensive tasks to a powerful computing infrastructure in their vicinity. In this part, a novel switching offloading mechanism for such robotic applications is proposed. In particular, opportunistic offloading strategies for the path planning and localization services of mobile robots are designed. The offloading decision is based on the uncertainty of the robot's pose, the resource availability at the Edge of the network and the difficulty of the path planning. The proposed switching offloading framework is implemented and evaluated using a robot in a real Edge Computing testbed, where the trade-off between execution time and the successful completion of the robot trajectory is highlighted. Finally, a Markovian Random Field (MRF)-based computational offloading and resource allocation mechanism is developed. The proposed mechanism leverages switching systems for modeling the computational resources at the network edge and allocating them dynamically, while minimizing energy consumption. This mechanism consists of two repeated stages; during the first, a Markov Chain-based technique is used to predict the mobile users' movements and subsequently to estimate the offloaded workload demand. During the second, a novel MRF-based technique undertakes the balancing of the offloaded tasks to the available computational resources. These tasks cannot be executed locally, i.e., on the user devices, under the given energy constraints and for a specific QoS. The proposed framework manages to improve energy consumption in the edge infrastructure, while taking into consideration the additional network delays induced by the MRF-based load balancing. Moreover, the efficiency of the proposed scheme is evaluated via modeling and simulation and is shown to outperform a well-known task offloading solution. Summarizing, in this thesis, dynamic resource allocation mechanisms for computational offloading are proposed, based on workload prediction, horizontal scaling, vertical scaling and workload balancing. Research is conducted, also, on formulating offloading strategies that work in harmony with these mechanisms, in order to guarantee a level of QoS and QoE, and minimize energy consumption, while the frameworks emerging from combining these techniques, are evaluated in the realistic, demanding environments of Industry 4.0, Natural Disaster Management and Smart Environments, with successful results.

Στην εποχή του Διαδικτύου των Αντικειμένων (ΔτΑ, Internet of Things), οι κινητές συσκευές είναι εφοδιασμένες με ισχυρές υλικές και διαδικτυακές δυνατότητες. Παρ' όλα αυτά, συνεχίζουν να μην μπορούν να ανταπεξέλθουν στην εκτέλεση υπολογιστικά επίπονων διεργασιών. Η Μεταφόρτωση Υπολογιστικών Διεργασιών (Computational Offloading), δηλαδή η ανάθεση των διεργασιών που καταναλώνουν πολλούς πόρους σε εξυπηρετητές τοποθετημένους στα Άκρα του Δικτύου (Network Edge), συνεισφέρει στην κατεύθυνση της υιοθέτησης του προτύπου του Κινητού Υπολογιστικού Νέφους (Mobile Cloud Computing) το οποίο δυνητικά θα βοηθήσει στην ελάφρυνση του υπολογιστικού φόρτου των κινητών συσκευών. Κίνητρο για τη συγγραφή αυτής της διατριβής αποτελεί η αντιμετώπιση των εγγενών προκλήσεων της μεταφόρτωσης υπολογιστικών διεργασιών, η σημαντικότερη από τις οποίες είναι η κατανομή πόρων υπό περιορισμούς, προσφέροντας ταυτόχρονα εγγυήσεις σχετικά με το επίπεδο ποιότητας υπηρεσιών (Quality of Service – QoS) και το επίπεδο ποιότητας εμπειρίας (Quality of Experience, QoE) που παρέχεται στους χρήστες. Στο πέρας αυτής της διατριβής γίνεται χρήση εννοιών από την Θεωρία Ελέγχου καθώς πρόκειται για ένα πεδίο το οποίο προσφέρει πληθώρα εργαλείων προς αντιμετώπιση των παραπάνω προκλήσεων. Επιπλέον, γίνεται χρήση εννοιών από την Θεωρία των Πιθανοτήτων. Πιο συγκεκριμένα, η παρούσα διατριβή εστιάζει σε τέσσερις σημαντικές ερευνητικές περιοχές που αφορούν στην ανάπτυξη των παραπάνω τεχνικών, οι οποίες είναι: α) η μοντελοποίηση των ετερογενών οντοτήτων του εξεταζόμενου συστήματος (τύπος υποδομής-χρηστών-εφαρμογών-δικτυακών/υπολογιστικών πόρων), β) ο υπολογισμός του όγκου των διεργασιών που αναμένεται να εκτελεστούν στα άκρα του δικτύου (μέσω της πρόβλεψης των θέσεων των κινητών συσκευών), γ) η δυναμική κατανομή των διαθέσιμων πόρων της υποδομής, καθοδηγούμενη από κριτήρια όπως είναι η διατήρηση ενός συμφωνημένου επιπέδου ποιότητας υπηρεσιών και εμπειρίας, η παράλληλη φιλοξενία πολλαπλών εφαρμογών στους ίδιους διαθέσιμους πόρους, καθώς και η ελαχιστοποίηση της ενεργειακής κατανάλωσης του συστήματος και δ) η βελτιστοποίηση των στρατηγικών μεταφόρτωσης των διεργασιών στους κατανεμημένους πόρους. Στόχος αυτής της διατριβής είναι ο εντοπισμός των σημαντικότερων ζητημάτων σε αυτές τις ερευνητικές περιοχές και η ανάπτυξη κατάλληλων λύσεων για την βελτιστοποίηση των επιμέρους διαδικασιών, δεδομένων των υφιστάμενων περιορισμών. Οι λύσεις αυτές στη συνέχεια συνδυάζονται δημιουργώντας πλαίσια τα οποία μπορούν να εγκατασταθούν σε υποδομές στα άκρα του δικτύου και να ελαφρύνουν την υπολογιστική καταπόνηση των -υπολογιστικά περιορισμένων- φορητών συσκευών, βελτιώνοντας ταυτόχρονα την ποιότητα εμπειρίας που αποκομίζουν οι χρήστες. Για το σκοπό αυτό, αναπτύσσεται ένας διεπίπεδος μηχανισμός δυναμικής κατανομής πόρων και ελέγχου μεταφόρτωσης διεργασιών για συστάδες εξυπηρετητών στα άκρα του δικτύου. Στο χαμηλότερο επίπεδο, η δυναμική συμπεριφορά των εξυπηρετητών μοντελοποιείται με χρήση γραμμικών συστημάτων, ενώ γραμμικοί ελεγκτές σχεδιάζονται για να διατηρούν το σύστημα εντός των δοθέντων περιορισμών (π.χ. συμφωνημένο επίπεδο ποιότητας υπηρεσιών). Στο υψηλότερο επίπεδο, ένας μηχανισμός βελτιστοποίησης αναλαμβάνει την τοποθέτηση των εφαρμογών/υπηρεσιών στους διαθέσιμους εξυπηρετητές (οι οποίες βρίσκονται σε μορφή εικονικών μηχανών, Virtual Machines – VMs) και τον καταμερισμό του φόρτου εργασίας μεταξύ τους, με σκοπό την μεγιστοποίηση του αριθμού των διεργασιών που θα εκτελεστούν επιτυχώς σε αυτούς. Η αποτίμηση του εν λόγω μηχανισμού αποδεικνύει την αποτελεσματικότητά του, τόσο όσον αφορά στην προσφερόμενη ποιότητα υπηρεσιών, όσο και στην βέλτιστη διαχείριση των υπολογιστικών πόρων στα άκρα του δικτύου. Στη συνέχεια, ο παραπάνω μηχανισμός εντάσσεται στο πλαίσιο ενός Κυβερνο-Φυσικού Κοινωνικού Συστήματος – ΚΦΚΣ (Cyber-Physical Social System – CPSS) τριών επιπέδων, το οποίο προορίζεται για τον έγκαιρο εντοπισμό πυρκαγιών. Γενικά, ένα ΚΦΚΣ αφομοιώνει τα υπολογιστικά συστήματα με τον φυσικό κόσμο και τις ανθρώπινες δραστηριότητες. Εν προκειμένω, στο χαμηλότερο επίπεδο, η αρχιτεκτονική του ΚΦΚΣ περιλαμβάνει συσκευές ΔτΑ με αισθητήρες ανίχνευσης και παρακολούθησης δασών. Επιπλέον, σε αυτό το επίπεδο, γίνεται χρήση του προτύπου της αίσθησης πλήθους (crowd sensing), κατά το οποίο συλλέγονται πληροφορίες σχετικά με το περιβάλλον από συσκευές χρηστών οι οποίοι βρίσκονται στην περιοχή ενδιαφέροντος. Δεδομένου ότι οι συσκευές ΔτΑ χαρακτηρίζονται από περιορισμένους υπολογιστικούς και ενεργειακούς πόρους, ο βασικός μηχανισμός εγκαθίσταται στο μεσαίο επίπεδο του ΚΦΚΣ και αναλαμβάνει την μεταφόρτωση των υπολογιστικά ακριβών διεργασιών των συσκευών ΔτΑ σε μια υποδομή στα άκρα του δικτύου. Σε αυτό το επίπεδο, ο μηχανισμός δυναμικής κατανομής πόρων επιτυγχάνει την τήρηση των χρονικών απαιτήσεων απόκρισης των εφαρμογών ανίχνευσης και παρακολούθησης. Στο υψηλότερο επίπεδο, ένας μηχανισμός λήψης αποφάσεων εγκατεστημένος σε εξυπηρετητές Υπολογιστικού Νέφους (Cloud), συλλέγει δεδομένα από τις διάφορες πηγές (συσκευές ΔτΑ, κοινωνικά δίκτυα χρηστών) και αποτιμά την κρισιμότητα της κατάστασης. Τα πειραματικά αποτελέσματα υποδεικνύουν τη σημασία του μηχανισμού δυναμικής κατανομής πόρων, τόσο στην εγγύηση της έγκαιρης εκτέλεσης των σημαντικών διεργασιών, όσο και στη μείωση της ενεργειακής κατανάλωσης των συσκευών ΔτΑ. Επιπροσθέτως, αναπτύσσεται ένας εναλλακτικός διακοπτικός (Switching Systems -based) μηχανισμός μεταφόρτωσης διεργασιών για εφαρμογές της Βιομηχανίας 4.0. Οι εφαρμογές αυτές απευθύνονται σε ρομπότ τα οποία εκτελούν περίπλοκες διεργασίες, οι οποίες παρουσιάζουν αυστηρές απαιτήσεις τόσο σε χρονική απόκριση όσο και σε ασφάλεια. Σε αυτό το πλαίσιο, η μεταφόρτωση των διεργασιών στα άκρα του δικτύου επιτρέπει στα ρομπότ να ελαφρύνουν τον υπολογιστικό τους φόρτο, αναθέτοντας την εκτέλεση των παραπάνω διεργασιών σε μία ισχυρή υπολογιστική υποδομή σε κοντινή απόσταση. Σε αυτό το κεφάλαιο, λοιπόν, προτείνεται ένας διακοπτικός μηχανισμός μεταφόρτωσης διεργασιών, ενώ σχεδιάζονται ευκαιριακές στρατηγικές μεταφόρτωσης για εφαρμογές που αφορούν στον προγραμματισμό της πορείας και τον εντοπισμό της θέσης των ρομπότ. Η απόφαση για την μεταφόρτωση λαμβάνεται βάσει της αβεβαιότητας ως προς την τρέχουσα θέση του ρομπότ και την διαθεσιμότητα υπολογιστικών και δικτυακών πόρων στα άκρα του δικτύου την δεδομένη στιγμή. Το διακοπτικό αυτό σύστημα υλοποιείται και αξιολογείται χρησιμοποιώντας ένα πραγματικό ρομπότ σε μια πραγματική υποδομή στα άκρα του δικτύου· κατά την αξιολόγηση τονίζεται το αντιστάθμισμα ανάμεσα στο χρόνο ολοκλήρωσης των διεργασιών και την επιτυχή έκβαση της αποστολής τους. Τέλος, μελετάται η μεταφόρτωση και ο διαμοιρασμός των διεργασιών με χρήση Μαρκοβιανών τυχαίων πεδίων. Συγκεκριμένα, στον προτεινόμενο μηχανισμό γίνεται χρήση διακοπτικών συστημάτων για την μοντελοποίηση των υπολογιστικών πόρων στα άκρα του δικτύου και την δυναμική κατανομή τους, βάσει κριτηρίων ενεργειακής κατανάλωσης. Ο μηχανισμός αποτελείται από δύο επαναλαμβανόμενα στάδια. Κατά το πρώτο, γίνεται χρήση μιας τεχνικής βασισμένης σε Μαρκοβιανές αλυσίδες, η οποία προβλέπει τις κινήσεις των χρηστών στο χώρο για την υπολογισμό του όγκου των διεργασιών που αναμένεται να μεταφορτωθούν στα άκρα του δικτύου. Κατά το δεύτερο, μια καινοτόμα τεχνική βασισμένη σε Μαρκοβιανά τυχαία πεδία αναλαμβάνει τον διαμοιρασμό των υπολογιστικών διεργασιών στους διαθέσιμους πόρους. Οι διεργασίες αυτές δεν δύνανται να εκτελεστούν τοπικά στις συσκευές τον χρηστών υπό συγκεκριμένους ενεργειακούς περιορισμούς και για συγκεκριμένο επίπεδο ποιότητας υπηρεσιών. Ο προτεινόμενος μηχανισμός επιτυγχάνει βελτιωμένη ενεργειακή κατανάλωση, λαμβάνοντας υπόψιν τις επιπρόσθετες δικτυακές καθυστερήσεις που επιφέρει ο διαμοιρασμός των εργασιών στην υποδομή. Ακόμη, συγκρίνοντας τον προτεινόμενο μηχανισμό με μια γνωστή αντίστοιχη δουλειά στη βιβλιογραφία, επιδεικνύεται η αποτελεσματικότητά του τόσο στη βελτιστοποίηση της κατανάλωσης ενέργειας, όσο και στην ποιότητα των παρεχόμενων υπηρεσιών. Συνοψίζοντας, στη διατριβή αυτή προτείνονται μηχανισμοί δυναμικής κατανομής πόρων για μεταφόρτωση υπολογιστικών διεργασιών, βασισμένοι στην πρόβλεψη του φόρτου εργασίας, στην οριζόντια και κατακόρυφη κλιμάκωση, καθώς και στην εξισορρόπηση φόρτου. Μελετάται, επίσης, ο σχεδιασμός στρατηγικών μεταφόρτωσης οι οποίες δουλεύουν σε αρμονία με τους παραπάνω μηχανισμούς, με σκοπό να εγγυηθούν ένα επίπεδο ποιότητας υπηρεσιών, ποιότητας εμπειρίας και να ελαχιστοποιηθεί η κατανάλωση ενέργειας, ενώ, οι ολοκληρωμένες λύσεις που προκύπτουν από τον συνδυασμό των παραπάνω τεχνικών, αξιολογούνται στα ρεαλιστικά και απαιτητικά περιβάλλοντα της Βιομηχανίας 4.0, της Διαχείρισης Φυσικών Καταστροφών και των Έξυπνων Περιβαλλόντων, με επιτυχία.