Βέλτιστη κατανομή πόρων για την ελαχιστοποίηση της απόκρισης και της ενέργειας σε σενάρια μεταφόρτωσης εφαρμογών

Abstract

Οι κινητές συσκευές στις μέρες μας χρησιμοποιούν σε καθημερινή βάση πολλαπλές εφαρμογές με σύνθετες απαιτήσεις. Επομένως, δημιουργείται η ανάγκη για τη βέλτιστη κατανομή των πόρων της κινητής συσκευής για την εκτέλεση των εργασιών της, μεταφορτώνοντας κάποιες από αυτές και σε άλλες υπολογιστικές μονάδες. Σε αυτή τη διπλωματική εργασία εξετάζουμε ένα σύστημα με μία κινητή συσκευή, η οποία μπορεί να εκτελεί τις εργασίες της τοπικά ή να τις μεταφορτώνει σε ορισμένα σημεία πρόσβασης, τα οποία εκτελούν τις εργασίες που λαμβάνουν. Σκοπός είναι να βρεθεί ο βέλτιστος συνδυασμός για την ανάθεση των εργασιών στα σημεία πρόσβασης, ώστε να ελαχιστοποιούνται η συνολική ενέργεια που δαπανείται για την εκτέλεση των εργασιών και ο συνολικός χρόνος εκτέλεσης των εργασιών. Η μοντελοποίηση του συστήματος καταλήγει σε ένα quadratic πρόβλημα βελτιστοποίησης με quadratic περιορισμούς(QCQP), το οποίο είναι NP-hard και προτείνουμε μια τεχνική προσέγγισης της λύσης με τη χρήση του αλγορίθμου SDR(semi-definite relaxation), λόγω της ταχύτητας της εκτέλεσης του και της ακρίβειας της προσέγγισης του στην βέλτιστη λύση. Αφαιρώντας ορισμένους περιορισμούς, ο αλγόριθμος SDR μετατρέπει το πρόβλημα σε ένα SDP(semi-definite programming), το οποίο είναι ένα κυρτό(convex) πρόβλημα ελαχιστοποίησης και μπορεί να λυθεί σε πολυωνυμικό χρόνο. Οι προσομοιώσεις μας τονίζουν ότι η τεχνική SDR επιτυγχάνει σχεδόν βέλτιστη απόδοση. Επιπλέον, παρατηρούμε αύξηση της απόδοσης σχετικά με τον χρόνο εκτέλεσης και την εξοικονόμηση ενέργειας, με την αύξηση των σημείων πρόσβασης. Τέλος, σημειώνουμε τη σημασία της μεταφόρτωσης των εργασιών για την κινητή συσκευή.