O κώδικας της εφαρμογής JoConDus

Πηγαίος Κώδικας

Απόκλιση από προδιαγραφές και μελλοντικές προεκτάσεις

Διαφορές με το πρώτο παραδοτέο

Η λειτουργία της εφαρμογής είναι ίδια με το πρώτο παραδοτέο. Ωστόσο η μεγάλη διαφορά έγκειται στην αρχιτεκτονική του συστήματος η οποία καθορίστηκε από τους περιορισμούς του android emulator. Πιο συγκεκριμένα κάθε emulator είναι πίσω από ένα εικονικό NAT. Το γεγονός αυτό σε συνδυασμό με το γεγονός πως ο emulator δεν υλοποιεί το πρωτόκολλο UPnP κάνει πολύ δύσκολη την σύναψη tcp σύνδεσης από τον master στον worker. Συνεπώς στην αρχιτεκτονική επιλέχτηκε να υπάρχει μια server socket στον master και μια socket στον worker μέσω της οποίας ξεκινάει μια παραμένουσα tcp σύνδεση.

Μελλοντικές προεκτάσεις

Η εφαρμογή αυτή αποτελεί το προσχέδιο μια μελλοντική εφαρμογής η οποία θα συνδυάζεται με τις λειτουργίες ενός GPS. Κατά συνέπεια είναι αναγκαίες οι παρακάτω προεκτάσεις:

Πλήρης ενσωμάτωση της εφαρμογής στο API ενός συγκεκριμένου GPS.

Προσθήκη πρωτοκόλλου UPnP και χρήση μη παραμενουσών συνδέσεων tcp.

Προσθήκη φιλτραρίσματος στο ποιοι worker θα λάβουν ένα query ανάλογα με την περιοχή στην οποία βρίσκονται.

Περιγραφή της λειτουργίας της εφαρμογής

Αρχικά από την πλευρά του worker , με την εκκίνηση του επιλέγει μία τυχαία διαδρομή στον δοθέντα γράφο που αντιπροσωπεύει την προσομοίωση ενός χάρτη και συνδέεται με τον server. Έπειτα φορτώνει το γραφικό του περιβάλλον που αποτελείται από τον γράφο και ένα κουμπί , το οποίο προτρέπει τον χρήστη να το επιλέξει αν επιθυμεί να βρει την «κίνηση» μέσα στον χώρο του γράφου. Για λόγους απλοποίησης τα δεδομένα του γράφου είναι στατικά.

Στην περίπτωση που ο χρήστης πατήσει το κουμπί Compute traffic αποστέλλεται ένα μήνυμα στον server τύπου QUERY , το οποίο προκαλεί την εξής αλληλουχία βημάτων :

1. Ο server δημιουργεί ένα μήνυμα ερώτησης ( QUERY )
2. Αποστέλλει το μήνυμα αυτό σε όλους τους υπόλοιπους κόμβους τύπου worke, προκαλώντας τους να ελέγξουν αν έχουν περάσει από τους κόμβους του υπογράφου του αρχικού γράφου, που περιέχονται στο μήνυμα
3. Αν έχει περάσει από κάποια ακμή, ο κάθε worker υπολογίζει την ταχύτητα και την χρονική στιγμή του γεγονότος αυτού για κάθε ερωτώμενο «δρόμο».
4. Οι workers αποστέλλουν τα αποτελέσματα τους στον server μέσω μηνύματος REPLY
5. O server κάνει την διαδικασία reduce στα δεδομένα που λαμβάνει υπολογίζοντας τα βάρη των ακμών σύμφωνα με την ταχύτητα κίνησης των workers και την χρονική στιγμή που ατή έλαβα χώρα.   
6. Και τελικά αποστέλλει στον αρχικό worker το αποτέλεσμα του υπολογισμού της κίνησης στον γράφο μέσω ενός μηνύματος REPLY
7. Ο worker αυτός λαμβάνοντας τα δεδομένα , χρωματίζει κατάλληλα τον γράφο ώστε να γίνει η οπτική αναπαράσταση για τον χρήστη. Οι χρωματισμοί αυτοί είναι κοντά στο πράσινο για δρόμους με χαμηλή κίνηση , κίτρινο για μέτρια και κόκκινο και πορτοκαλί για υψηλή κίνηση
8. Η διαδικασία μπορεί να επαναληφθεί

Ακολουθούν τρία παραδείγματα εκτέλεσης του προγράμματος : 

Δομή και αρχιτεκτονική της εφαρμογής

Μηνύματα

Στην εφαρμογή Jocondus υπάρχουν τέσσερα διαφορετικά μηνύματα:

Query από τον worker στον master

Το μήνυμα αυτό σηματοδοτεί την έναρξη μιας νέας διαδικασίας map reduce.

Query από τον master στον worker

Το μήνυμα αυτό δίνει εντολή στον worker να ψάξει στον πίνακα με τους δρόμους από τους οποίους έχει περάσει και να στείλει την ταχύτητά και την ώρα που πέρασε από τον κάθε δρόμο.

Reply από τον worker στον master

Το μήνυμα αυτό περιέχει τους δρόμους που πέρασε ο worker κατά τη διάρκεια της τελευταίας ώρας μαζί με την ταχύτητα που είχε σε κάθε δρόμο.

Reply από τον master στον worker

Το μήνυμα αυτό περιέχει την τελική απάντηση του master στον worker.

Αρχιτεκτονική του Jocondus Master

Κλάση ServerRunnable

Η κλάση ServerRunnable είναι υπεύθυνη να περιμένει για νέους worker να κάνουν αίτηση tcp σύνδεσης. Όταν γίνει μια αίτηση την δέχεται και ξεκινάει ένα νέο thread με runnable το WorkerRunnable.

Κλάση WorkerRunnable

Η κλάση WorkerRunnable είναι υπεύθυνη να ακούει για μηνύματα που στέλνει ο worker. Σε περίπτωση που λάβει ένα νέο query, τότε ξεκινάει ένα νέο thread με runnable το MapReduceRunnable. Σε περίπτωση που λάβει reply για κάποιο query τότε το προσθέτει στo reduceTable του query στο οποίο αναφέρεται.

Κλάση MapReduceRunnable

Η κλάση MapReduceRunnable φτιάχνει ένα νέο query, το στέλνει σε όλους τους workers, περιμένει να ληφθούν όλα τα replies, κάνει reduce τα δεδομένα και τέλος στέλνει reply στον worker που έκανε το query.

Αρχιτεκτονική του Jocondus Worker

Κλάση JocondusMainActivity

Η κλάση JocondusMainActivity ξεκιναει μια tcp σύνδεση με τον master, καθώς και ένα thread με το runnable ConnectionRunnable. Στη συνέχεια είναι υπεύθυνη για τον χειρισμό του GUI και την αποστολή του query μηνύματος στον master.

Κλάση ConnectionRunnable

Η κλάση ConnectionRunnable είναι υπεύθυνη για να ακούει τα μηνύματα που στέλνει ο master. Σε περίπτωση που λάβει reply τότε το προωθεί στο JocondusMainActivity. Στην περίπτωση που λάβει query τότε ξεκινάει ένα νέο thread με runnable το MapSearchAndReply.

Κλάση MapSearchAndReply

Η κλάση MapSearchAndReply ψάχνει τη λίστα με τους δρόμους από τους οποίους έχει περάσει ο worker και στέλνει το reply μήνυμα στον master.

Παραδοτέο 1ο - Αρχικές προδιαγραφές και περιγραφή της ιδέας

Εφαρμογή κυκλοφοριακής αποσυμφόρησης στο σύστημα 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()

Εισαγωγικά

Ο σκοπός αυτού του blog είναι η παρουσίαση της εργασίας μας , που εκπονήθηκε στα πλαίσια του μαθήματος "Κατανεμημένα Συστήματα" του πρώτου εξαμήνου του μεταπτυχιακού προγράμματος "Επιστήμη των υπολογιστών " του Τμήματος Πληροφορικής του Οικονομικού Πανεπιστημίου Αθηνών.

Η εργασία περιέχει την εφαρμογή Jocondus που κάνει χρήση του προγραμματιστικού μοντέλου Map Reduce σε περιβάλλον Android ! Στόχος της εφαρμογής είναι η παρουσίαση μιας προσομοίωσης εύρεσης της κίνησης σε δρόμους της πόλης ,πιθανώς σε πλήρη υλοποίηση της ιδέας ως υποστηρικτική εφαρμογή σε προγράμματα GPS.

Οι φοιτητές :

Παναγιωτίδης Ιωνάθαν-Γιάννης με Α.Μ. ΕΥ1003 και
Καλαμπόκης Κωνσταντίνος       με Α.Μ. ΕΥ1018