Εφαρμογή κυκλοφοριακής αποσυμφόρησης στο σύστημα Android μέσω της τεχνικής Map/Reduce
Σκοπός της εφαρμογής αυτής είναι η απόδοση μιας εκτίμησης για την βέλτιστη διαδρομή που θα πρέπει να ακολουθήσει ένας οδηγός αυτοκινήτου και χρήστης κινητού με σύστημα Android, για την αποφυγή της κυκλοφοριακής συμφόρησης μεταξύ δύο σημείων, που θέλει να επισκεφθεί. Φιλοδοξία του προγράμματος είναι η παροχή μίας προτεινόμενης διαδρομής στον χρήστη με την καλύτερη σχέση μεταξύ κίνησης στους δρόμους και απόστασης μεταξύ της αφετηρίας και του προορισμού του. Έτσι μέσω αυτής της προσέγγισης να εφαρμόζεται μία τεχνική αποσυμφόρησης των δρόμων μέσω της καλύτερης κατανομής των οχημάτων ανά οδό.
Η τεχνική, που θα χρησιμοποιηθεί, είναι η Map/Reduce και θα υλοποιηθεί σε περιβάλλον Android.
Οι συσκευές, που συνδέονται στο σύστημα, χωρίζονται σε δύο κατηγορίες τους εργάτες (workers ) και τον υπεύθυνο (Master).Κάθε κινητό που τρέχει την εφαρμογή είναι worker και είναι υπεύθυνος για την map function. Τέλος υπάρχει ένας Master κόμβος, κατά προτίμηση σταθερός υπολογιστής server , o οποίος είναι υπεύθυνος για την reduce function.
Ο κάθε worker περιέχει μια δομή δεδομένων που αποθηκεύει τις πρόσφατες διαδρομές από όπου πέρασε ο χρήστης , την μέση ταχύτητα που είχε σε κάθε δρόμο και το ακριβές χρονικό διάστημα που πέρασε από το δρόμο. Η δομή αυτή ανανεώνεται συχνά ώστε τα δεδομένα να αποτελούν την τελευταία εικόνα της κίνησης στον δρόμο. Οποιαδήποτε στιγμή, ένας worker μπορεί να στείλει ένα αίτημα (request) στον master το οποίο περιέχει τον προορισμό και τις πιθανές διαδρομές με τη μορφή γράφου. Υποθέτουμε ότι το πρόγραμμα GPS, του οποίο τμήμα αποτελεί το πρόγραμμα μας, παρέχει τις πιθανές διαδρομές με τη μορφή γράφου, η συνεργασία του προγράμματος με υπάρχον σύστημα GPS ή με ήδη υπάρχον σύστημα χαρτογράφησης όπως το Google Maps ανατίθεται στην μελλοντική δουλειά που πρέπει να γίνει, ίσως στο τέλος του εξαμήνου ή και αργότερα.
Στη συνέχεια ο master στέλνει τον γράφο σε όλους τους workers, εκτός από αυτόν που έκανε το request και περιμένει να του απαντήσουν. Ο κάθε worker ο οποίος δέχτηκε την εντολή για εργασία αναζητά την τομή του γράφου, που δέχτηκε σαν είσοδο, με τον γράφο των πρόσφατων μετακινήσεών του. Η διαδικασία αυτή αποτελεί την map function της τεχνικής Map/Reduce. Ακολούθως ο worker επιστρέφει το αποτέλεσμα της map function στον Master έχοντας συμπεριλάβει για την κάθε κοινή ακμή την μέση ταχύτητα και το χρονικό διάστημα στο οποίο επιτεύχθηκε. Ο master συνδυάζει όλα τα δεδομένα που έφτασαν έγκαιρα από τους workers και υπολογίζει μια εκτίμηση για την κίνηση στις πιθανές διαδρομές καθώς και τη βέλτιστη διαδρομή σύμφωνα με την εκτίμηση αυτή, εκτελώντας την reduce function. Λόγω της προσεγγιστικής φύσης της μεθόδου, πολλές παράμετροι, όπως η αξιολόγηση των δρόμων όπου δεν καλύφθηκαν από κάποιον χρήστη, η δυνατότητα συνδυασμού δύο ή περισσότερων προτεινόμενων αρχικών διαδρομών ή ακόμη και η χάραξη μιας νέας διαδρομής με βάση τα παρεχόμενα δεδομένα, επαφίεται στην υλοποίηση του προγράμματος GPS που θα περιλαμβάνει η κινητή συσκευή και πάνω από την οποία θα τρέχει ο παρουσιαζόμενος κώδικας.
Σύντομη παρουσίαση της εφαρμογής:
Κόμβος Worker
Ο κάθε worker εκτελεί τρεις εργασίες που περιγράφονται με τις ακόλουθες ενότητες κώδικα :
· Κλάση GraphHandler
Η κλάση GraphHandler περιέχει τη δομή καταγραφής των απαραίτητων δεδομένων καθώς και τις μεθόδους ανάγνωσης και τροποποίησης της. Η δομή αυτή αντιπροσωπεύει την εσωτερική αναπαράσταση του κάθε worker για τους δρόμους που πέρασε την τελευταία ώρα, ποιά ήταν η μέση ταχύτητα του και σε ποιο χρονικό διάστημα.
· Κλάση WorkerRunnable
Η κλάση αυτή υλοποιεί την διεπαφή runnable της Java και περιμένει να δεχτεί μια κλήση από τον master. Μόλις δεχτεί την κλήση τρέχει την map function η οποία υπολογίζει την τομή του γράφου που στέλνει ο master με τον γράφο της κλάσης GraphHandler. Μόλις υπολογίσει την τομή, την επιστρέφει στον master και περιμένει για νέα κλήση.
· Κλάση GraphRenewRunnable
Η κλάση αυτή υλοποιεί την διεπαφή runnable της Java και στόχος της είναι η φροντίδα της δυναμικής ανανέωσης της δομής δεδομένων της κλάσης GraphHandler. Πρακτικά θα εκτελείται σε τακτικά χρονικά διαστήματα και θα τροφοδοτεί το υπόλοιπο πρόγραμμα με πληροφορίες που αντλούνται από το GPS-Destinator που το φιλοξενεί, κρατώντας έτσι τα δεδομένα που χρησιμοποιούνται όσο πιο πρόσφατα είναι δυνατόν για την παροχή ακριβέστερης εκτίμησης στον Master.
· Κλάση RequestRunnable
Η κλάση αυτή υλοποιεί την διεπαφή runnable και εκτελείται όταν ο χρήστης ζητήσει κάποια εκτίμηση για την κίνηση από το υπόλοιπο σύστημα. Η κλάση αυτή λαμβάνει από το GPS-Destinator το σύνολο των πιθανών διαδρομών, το αποστέλλει στον master και περιμένει την απάντηση. Όταν ο master επιστρέψει την απάντηση τα αποτελέσματα παρουσιάζονται στον χρήστη.
Κόμβος Master
· Κλάση IPtableHandler
Η κλάση IPtableHandler περιέχει τη δομή δεδομένων καθώς και τις μεθόδους ανάγνωσης και τροποποίησης της. Η δομή αυτή αποθηκεύει τις IP και τα Ports των κινητών που είναι συνδεδεμένα στο σύστημα και περιέχει όλες τις συναρτήσεις, οι οποίες χρησιμοποιώντας αυτόν τον πίνακα εκτελούν τις απαραίτητες λειτουργίες, όπως η συνάρτηση reduce, η sendEstimationToUser() , receiveFromWorker() και άλλες
· Κλάση WelcomeListener
Η κλάση αυτή υλοποιεί την διεπαφή runnable και αναλαμβάνει την σύνδεση νέων χρηστών τύπου worker στο σύστημα.
· Κλάση RequestListener
Η κλάση αυτή υλοποιεί την διεπαφή runnable και ακούει σε μία πόρτα, αναμένοντας νέες αιτήσεις από τους workers για την εκκίνηση παροχής κάποιας εκτίμησης για την κίνηση.
· Κλάση SendData
Η κλάση αυτή υλοποιεί την διεπαφή runnable και στόχος της είναι η παροχή στους χρήστες-workers την εντολή εκκίνησης εργασίας και την τροφοδοσία τους με τα κατάλληλα δεδομένα ώστε να εργαστούν , όπως είναι ο γράφος του αιτούντα χρήστη.
· Κλάση ReceiveAndReduce
Η κλάση αυτή υλοποιεί την διεπαφή runnable και αποτελεί τον κορμό λειτουργίας του Master, καθώς σκοπός της είναι η υποδοχή των επεξεργασμένων δεδομένων και η διαδικασία reduce αυτών, ώστε να επιτευχτεί η ανασυγκρότηση του αρχικού γράφου με την παροχή επιπροσθέτως της εκτίμησης που παρέχουν οι workers για την κίνηση στο οδικό δίκτυο. Τελικά , η κλάση αυτή αναλαμβάνει την αποστολή των δεδομένων πίσω στον αιτούντα , ολοκληρώνοντας την διαδικασία Map/Reduce
Πιθανές συναρτήσεις που θα χρησιμοποιηθούν:
reduce(), sendEstimationToUser(), receiveFromWorkers()
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου