Απόρριψη Φόρτου Από Ρεύματα Τροχιάς Κινούμενων Αντικειμένων

Abstract

Τα τελευταία χρόνια, παρατηρείται ραγδαία αύξηση του όγκου των δεδομένων που παράγονται και πρέπει να εξυπηρετήσουν διάφορες εφαρμογές. Μία κατηγορία είναι οι εφαρμογές παρακολούθησης κινούμενων αντικειμένων, στις οποίες το σύστημα οφείλει να επεξεργάζεται τον όγκο των δεδομένων που του δίνεται και να απαντάει έγκαιρα και αξιόπιστα σε διαφόρων τύπων ερωτήματα. Οι πληροφορίες για την κίνηση των αντικειμένων καταφθάνουν στο σύστημα με τη μορφή ρευμάτων δεδομένων, για την επεξεργασία των οποίων, διατυπώνονται ερωτήματα διαρκείας που παραμένουν ενεργά για μεγάλο χρονικό διάστημα. Τα κινούμενα αντικείμενα θεωρούνται σημειακά και η θέση τους μεταβάλλεται δυναμικά. Κάθε αντικείμενο αποστέλλει ανά τακτά χρονικά διαστήματα την καινούργια θέση του σε έναν κεντρικό επεξεργαστή που καλείται να δίνει απάντηση στα ερωτήματα διαρκείας. Όμως, υπάρχει ενδεχόμενο το στίγμα των αντικειμένων να καταγράφεται με πολύ μεγάλη συχνότητα (λ.χ. κάθε 10 δευτερόλεπτα), οπότε ο όγκος της πληροφορίας γίνεται υπερβολικά μεγάλος και να καθυστερεί η επεξεργασία ποικίλων ερωτημάτων διαρκείας, τα οποία πρέπει να παρέχουν συνεχώς επίκαιρες απαντήσεις. Για το λόγο αυτό, και με δεδομένο ότι υπάρχουν πεπερασμένη μνήμη και επεξεργαστική ισχύς, μία ιδέα είναι το σύστημα να επεξεργάζεται ένα μόνο μέρος της εισόδου έτσι ώστε να δίνονται έγκαιρα απαντήσεις στα τρέχοντα ερωτήματα, με αντίκτυπο βέβαια στην ποιότητα των αποτελεσμάτων. Αντικείμενο της διπλωματικής εργασίας είναι η ανάπτυξη και υλοποίηση αλγορίθμου απόρριψης φόρτου, που αφορά την επιλογή με σημασιολογικό τρόπο, ποιές και πόσες από τις διαθέσιμες τροχιές θα εξετάζει πλήρως το σύστημα με σκοπό να ικανοποιεί τις απαιτήσεις. Από την άλλη μεριά, ο αλγόριθμος που προτείνουμε είναι προσαρμοστικός, δηλαδή ο αριθμός τροχιών που εξετάζονται σε κάθε κύκλο εκτέλεσης αναπροσαρμόζεται ανάλογα με τον φόρτο του συστήματος έτσι ώστε να αξιοποιούνται πλήρως οι διαθέσιμοι πόροι του. Με εφαρμογή του ευριστικού αλγορίθμου που κατασκευάστηκε, πραγματοποιήθηκαν πειράματα σε συνθετικά δεδομένα πάνω στο χάρτη της Αττικής, από τα οποία προέκυψαν θετικά αποτελέσματα. Επίσης, επιβεβαιώθηκαν οι αναμενόμενες επιδόσεις τους σχετικά με τους χρόνους εκτέλεσης και την ακρίβεια των απαντήσεων.