Stackelberg Game-Based Resource Management of Edge Computing Systems

Abstract

Οι αδιάκοπες τεχνολογικές εξελίξεις και η εντυπωσιακή άνθηση του Διαδικτύου των Πραγμάτων (Internet of Things) έχουν εκτοξεύσει τον αριθμό των συσκευών που συνδέονται και επικοινωνούν μεταξύ τους στο διαδίκτυο. Παράλληλα, η ραγδαία υιοθέτηση εφαρμογών τεχνητής νοημοσύνης σε συσκευές IoT έχει προκαλέσει κατακόρυφη αύξηση των δεδομένων που χρήζουν επεξεργασίας, ενώ η παραδοσιακή λύση της μεταφοράς και επεξεργασίας δεδομένων στο cloud έχει αποδειχθεί ελλιπής. Η επικρατούσα λύση του edge computing, παρά τα πλεονεκτήματα που προσφέρει, δημιουργεί νέες προκλήσεις, με σημαντικότερη ίσως την διαχείριση των περιορισμένων υπολογιστικών πόρων που διαθέτουν οι συσκευές IoT.

Στην παρούσα διπλωματική εργασία θα ασχοληθούμε με ένα σύστημα edge computing αποτελούμενο από ένα σύνολο από συσκευές IoT και κόμβους edge. Οι συσκευές καλούνται να φέρουν εις πέρας απαιτητικές εργασίες μέσα σε αυστηρές προθεσμίες, ενώ οι κόμβοι συμβάλλουν προσφέροντας τους υπολογιστικούς τους πόρους στο σύστημα. Προκύπτει, επομένως, η ανάγκη αποδοτικής διαχείρισης των πόρων του συστήματος, προκειμένου να επιτυγχάνονται οι λειτουργικές απαιτήσεις των εργασιών και να αξιοποιούνται αποδοτικά οι περιορισμένοι πόροι των συσκευών.

Για τον σκοπό αυτό, σχεδιάζουμε τον αλγόριθμο SGRM, έναν αποκεντροποιημένο αλγόριθμο διαχείρισης πόρων σε συστήματα edge computing βασισμένο σε στοιχεία της θεωρίας παιγνίων. Πιο συγκεκριμένα, ο αλγόριθμός μας μοντελοποιεί το πρόβλημα της κατανομής εργασιών μιας συσκευής edge ως ένα παίγνιο Στάκελμπέργκ μεταξύ της συσκευής και των κόμβων edge και διεξάγει μια κλειστή δημοπρασία δεύτερης τιμής (γνωστή και ως δημοπρασία Vickrey) για την επιλογή του βέλτιστου κόμβου εκφόρτωσης.

Μετά από μια σύντομη εισαγωγή στα πρότυπα IoT, edge, και στο θεωρητικό υπόβαθρο της θεωρίας παιγνίων, παρουσιάζουμε τον αλγόριθμο SGRM, περιγράφουμε λεπτομερώς την λειτουργία του και αξιολογούμε τις επιδόσεις του, πραγματοποιώντας μια εκτενή πειραματική μελέτη και συγκρίνοντάς τον με κατάλληλα επιλεγμένους αλγορίθμους αναφοράς.