Εξελιγμένες τεχνικές πρόβλεψης θέσης στον κινητό υπολογισμό

Abstract

CONTEXT-AWARENESS IS VIEWED AS ONE OF THE MOST IMPORTANT ASPECTS IN THE EMERGING PERVASIVE COMPUTING PARADIGM. MOBILE CONTEXT-AWARE APPLICATIONS ARE REQUIRED TO SENSE AND REACT TO CHANGING ENVIRONMENT CONDITIONS. SUCH APPLICATIONS, USUALLY, NEED TO RECOGNIZE, CLASSIFY AND PREDICT CONTEXT IN ORDER TO ACT EFFICIENTLY, BEFOREHAND, FOR THE BENEFIT OF THE USER. FIRSTLY, WE PROPOSE AN EFFICIENT SPATIAL CONTEXT CLASSIFIER AND A SHORT-TERM PREDICTOR FOR THE FUTURE LOCATION OF A MOBILE USER IN CELLULAR NETWORKS. WE INTRODUCE DIFFERENT VARIANTS OF THE CONSIDERED LOCATION PREDICTOR DEALING WITH LOCATION (CELL) IDENTIFIERS AND DIRECTIONS. SYMBOLIC LOCATION CLASSIFICATION IS TREATED AS A SUPERVISED LEARNING PROBLEM. WE EVALUATE THE PREDICTION EFFICIENCY AND ACCURACY OF THE PROPOSED PREDICTORS THROUGH SYNTHETIC AND REAL-WORLD TRACES. SECONDLY, WE PROPOSE A NOVEL ADAPTIVE MOBILITY PREDICTION ALGORITHM, WHICH DEALS WITH LOCATION CONTEXT REPRESENTATION AND TRAJECTORY PREDICTION OF MOVING USERS. MACHINE LEARNING (ML) IS USED FOR TRAJECTORY CLASSIFICATION. OUR ALGORITHM ADOPTS SPATIAL AND TEMPORAL ON-LINE CLUSTERING, AND RELIES ON ADAPTIVE RESONANCE THEORY (ART) FOR TRAJECTORY PREDICTION. THE PROPOSED ALGORITHM APPLIES A HAUSDORFF-LIKE DISTANCE OVER THE EXTRACTED TRAJECTORIES HANDLING LOCATION PREDICTION. SINCE OUR APPROACH IS TIME-SENSITIVE, THE HAUSDORFF DISTANCE IS CONSIDERED MORE ADVANTAGEOUS THAN A SIMPLE EUCLIDEAN NORM. TWO LEARNING METHODS (NON-REINFORCEMENT AND REINFORCEMENT LEARNING) ARE PRESENTED AND EVALUATED. THIRDLY, WE PROPOSE A SHORT-MEMORY ADAPTIVE LOCATION PREDICTOR THAT REALIZES MOBILITY PREDICTION IN THE ABSENCE OF EXTENSIVE HISTORICAL MOBILITY INFORMATION. OUR PREDICTOR IS BASED ON A LOCAL LINEAR REGRESSION MODEL, WHILE ITS ADAPTATION CAPABILITY IS ACHIEVED THROUGH A FUZZY CONTROLLER. SUCH FUZZY CONTROLLER CAPITALIZES ON AN APPROPRIATE SIZE OF HISTORICAL MOBILITY INFORMATION IN ORDER TO MINIMIZE THE LOCATION PREDICTION ERROR AND PROVIDE FAST ADAPTATION TO ANY DETECTED MOVEMENT CHANGE. OUR PREDICTION EXPERIMENTS PERFORMED WITH REAL GPS DATA.FOURTHLY, WE ASSUME THE EXISTENCE OF A PATTERN BASE AND TRY TO COMPARE THE MOVEMENT PATTERN OF A CERTAIN USER WITH STORED INFORMATION IN ORDER TO PREDICT FUTURE LOCATIONS. A CONVENTIONAL PREDICTION SCHEME WOULD SUFFER FROM POTENTIAL NOISE IN MOVEMENT PATTERNS. SUCH NOISE (POSSIBLY MANIFESTED AS SMALL - RANDOM DEVIATIONS FROM PREVIOUSLY SEEN PATTERNS) (A) NEGATIVELY IMPACTS THE PREDICTION CAPABILITY OF THE CLASSIFICATION SYSTEM AND (B) DRIVES THE BASE TO STATE SPACE EXPLOSION. WE TRY TO ALLEVIATE SUCH SHORTCOMINGS THROUGH THE USE OF OPTIMAL STOPPING THEORY AND THE INTRODUCTION OF A VERY SPECIFIC MOVEMENT PREDICTION WORK–FLOW. OPTIMAL STOPPING THEORY RELAXES THE CLASSIFICATION TASK SO THAT SLIGHTLY DIFFERENT PATTERNS CAN BE TREATED AS EQUIVALENT. MOREOVER, THE UNDERLYING PATTERN BASE IS KEPT AS ‘CLEAN’ AND CONCISE AS POSSIBLE BY RETAINING THOSE PATTERNS WITH LIMITED SPATIAL VARIANCE. OUR FINDINGS, COMPARED WITH OTHER SCHEMES, ARE VERY PROMISING FOR THE LOCATION PREDICTION PROBLEM AND THE ADOPTION OF PROACTIVE CONTEXT-AWARE APPLICATIONS AND SERVICES.

Η επίγνωση-πλαισίου εμφανίζεται ως μία από τις πιο σημαντικές πτυχές στο αναδυόμενο περιβάλλον του διάχυτου υπολογισμού. Απαιτούνται κινητές εφαρμογές επίγνωσης πλαισίου για την αίσθηση και την αντίδραση σε συνθήκες μεταβαλλόμενου περιβάλλοντος. Τέτοιες εφαρμογές, συχνά, χρειάζεται να αναγνωρίζουν, να ταξινομούν και να προβλέπουν το πλαίσιο με σκοπό να δρουν αποδοτικά, εκ των προτέρων, προς όφελος του χρήστη. Πρώτον, προτείνουμε έναν αποδοτικό ταξινομητή χωρικού πλαισίου και έναν βραχείας-μνήμης προγνώστη για την μελλοντική θέση ενός κινητού χρήστη σε κυψελωτά δίκτυα. Εισάγουμε διαφορετικές παραλλαγές του προτεινόμενου προγνώστη θέσης που χρησιμοποιούν θέση (κυψέλη) και κατεύθυνση. Η ταξινόμηση συμβολικής θέσης αντιμετωπίζεται ως ένα πρόβλημα εποπτευόμενης μάθησης. Αξιολογούμε την απόδοση πρόβλεψης και την ακρίβεια των προτεινόμενων προγνωστών μέσω συνθετικών και πραγματικών ιχνών.Δεύτερον, προτείνουμε έναν καινοτόμο προσαρμοστικό αλγόριθμο, ο οποίος χειρίζεται το πλαίσιο αναπαράστασης θέσης και την πρόβλεψη τροχιών των κινούμενων χρηστών. Ο αλγόριθμος μας υιοθετεί χωρική και χρονική on-line ομαδοποίηση, και βασίζεται στην Θεωρία Προσαρμοστικού Συντονισμού (ART) για την πρόβλεψη τροχιάς. Ο προτεινόμενος αλγόριθμος εφαρμόζει την Hausdorff απόσταση πάνω στις τροχιές για τον χειρισμό της πρόβλεψης θέσης. Δεδομένου ότι η προσέγγιση μας είναι χρονικά-ευαίσθητη, η απόσταση Hausdorff θεωρείται πιο κατάλληλη από ότι η Ευκλείδεια απόσταση. Δύο μέθοδοι εκμάθησης παρουσιάζονται και αξιολογούνται (η μη-ενισχυτική και η ενισχυτική μάθηση).Τρίτον, προτείνουμε έναν βραχείας-μνήμης προσαρμοστικό προγνώστη θέσης που χειρίζεται την πρόβλεψη υπό την απουσία ιστορικής κινητής πληροφορίας. Ο προγνώστης μας βασίζεται σε ένα μοντέλο τοπικής γραμμικής παλινδρόμησης, ενώ η ικανότητα του να προσαρμόζεται επιτυγχάνεται μέσω ενός ασαφούς ελεγκτή. Ο ασαφής ελεγκτής αξιοποιεί το κατάλληλο μέγεθος της ιστορικής πληροφορίας κίνησης με σκοπό να ελαχιστοποιήσει το σφάλμα πρόβλεψης και να παρέχει γρήγορη προσαρμογή σε κάθε ανιχνευόμενη αλλαγή κίνησης. Τα πειράματα μας έγιναν με πραγματικά GPS ίχνη.Τέταρτον, υποθέτουμε μία βάση προτύπων και προσπαθούμε να συγκρίνουμε το πρότυπο κίνησης ενός χρήστη με την αποθηκευμένη πληροφορία με σκοπό να προβλέψουμε μελλοντικές θέσεις. Μία συμβατική μέθοδος πρόβλεψης θα είχε μειωμένη απόδοση λόγω του θορύβου. Αυτός ο θόρυβος (α) επιδρά αρνητικά στην ικανότητα πρόβλεψης και (β) οδηγεί τη βάση σε μεγάλη αύξηση χωρητικότητας. Προσπαθούμε να ξεπεράσουμε αυτά τα προβλήματα μέσω της χρήσης της Θεωρίας Βέλτιστης Παύσης. Η συγκεκριμένη θεωρία χαλαρώνει την διαδικασία της ταξινόμησης έτσι ώστε ελαφρώς διαφορετικά πρότυπα να αντιμετωπίζονται σαν όμοια. Επιπρόσθετα, η βάση γνώσης διατηρείται αρκετά «καθαρή» διατηρώντας τα πρότυπα με την ελάχιστη χωρική διακύμανση.Τα συμπεράσματά μας, συγκρινόμενα με άλλα σχήματα, είναι πολύ ελπιδοφόρα για το πρόβλημα της πρόβλεψης θέσης.