Προσεγγιστικοι Αλγοριθμοι Για Το Προβλημα Της Χρονοδρομολογησης Αποστολης Δεδομενων Σε Δικτυα

Abstract

Ένα πρόβλημα το οποίο προέκυψε στις ασύρματες επικοινωνίες, είναι αυτό της χρονοδρομολόγησης της αποστολής και λήψης δεδομένων (Preemptive Bipartite Scheduling problem-PBS). Στο πρόβλημα αυτό έχουμε ένα σύνολο από πομπούς, ένα σύνολο από δέκτες και ένα σύνολο από δεδομένα, τα οποία θέλουμε να στείλουμε από τους πομπούς στους δέκτες. Για κάθε δεδομένο γνωρίζουμε εκ των προτέρων τον χρόνο που χρειάζεται για να σταλεί. Ένας πομπός δεν μπορεί να στέλνει ταυτόχρονα δεδομένα σε δύο ή περισσότερους δέκτες, και αντίστοιχα ένας δέκτης δεν μπορεί να λαμβάνει ταυτόχρονα δεδομένα από δύο ή περισσότερους πομπούς. Προσπαθούμε να βρούμε μία συγκεκριμένη σειρά αποστολής των δεδομένων, έτσι ώστε να επιτύχουμε την αποστολή όλων των δεδομένων στον ελάχιστο δυνατό χρόνο. Η αποστολή αυτή γίνεται χωρίζοντας τα δεδομένα σε κατάλληλες ομάδες δεδομένων, αποτελούμενες από δεδομένα που μπορούν να αποσταλούν ταυτόχρονα. Ο καθορισμός του συστήματος, ώστε να αποσταλεί μία ομάδα αποστολής θεωρούμε ότι απαιτεί γνωστό εκ των προτέρων χρόνο. Η βέλτιστη λύση του προβλήματος, είναι εκείνη που ελαχιστοποιεί τον συνολικό χρόνο αποστολής των δεδομένων, δηλαδή το άθροισμα των χρόνων αποστολής και των χρόνων καθορισμού των ομάδων αποστολής. Επειδή η εύρεση της βέλτιστης λύσης συχνά είναι ιδιαίτερα δύσκολη και απαιτεί πολλές φορές περισσότερο χρόνο από εκείνον που διαθέτουμε, οδηγούμαστε στη χρήση προσεγγιστικών αλγορίθμων για την επίλυση του προβλήματος αυτού. Οι προσεγγιστικοί αλγόριθμοι βρίσκουν μία λύση, σε πολυωνυμικό χρόνο, η οποία εν γένει δεν είναι η βέλτιστη, αλλά μας εξασφαλίζουν πόσο «κοντά» στην βέλτιστη είναι, στην χειρότερη περίπτωση. Στην παρούσα εργασία, παρουσιάζουμε τρείς τέτοιους αλγορίθμους. Στη συνέχεια τους υλοποιούμε, και πραγματοποιούμε μια σειρά πειραμάτων , προκειμένου να βγάλουμε χρήσιμα συμπεράσματα για την απόδοσή τους.