Demo Taxi Application

Εφόσον δεχτεί μία λίστα με όλους τους mappers καθένας από τους οποίους έχει τον πίνακα με τα taxi σε απόσταση εντός 10 km, κάνει ένα mapping αντιστοιχίζοντας τους mappers αυτούς στα αντίστοιχα taxi.

 Για κάθε mapper υπολογίζουμε τους 3 καλύτερους συνεπιβάτες του και όλοι μαζί σχηματίζουν ένα αντικείμενο Route για το συγκεκριμένο taxi. Το κάθε Route έχει ένα συνολικό score το οποίο υπολογίζεται με βάση τα επιμέρους score δια τον αριθμό των επιβατών. Με τον τρόπο αυτό επιβραβεύουμε τις διαδρομές με πολλούς επιβάτες. Το επιμέρους score  διαδρομής κάθε mapper-συνεπιβάτη υπολογίζεται από την ελάχιστη απόσταση που έχει το σημείο αρχής 'η τερματισμού του από την διαδρομή του αρχικού mapper (Απόσταση σημείου-συνεπιβάτης- από ευθεία- διαδρομή πρώτου επιβάτη).

Αρχικά, έχουμε φτιάξει ένα service το οποίο τρέχει κάθε κόμβο του συστήματος και είναι listener για τα broadcast πακέτα. Το service αυτό χρησιμοποιείται στην αρχή για το network discovery του συστήματος, RideShareServive αντικείμενο.

Το αντικείμενο αυτό ξεκινάει όταν ξεκινάει η εφαρμογή, στην StartScreen του συστήματος. Πιο συγκεκριμένα, ένας κόμβος ξεκινάει σαν server και μόλις δεχτεί ένα μύνημα mapper ή reducer καταχωρεί στην αντίστοιχη λίστα την IP διεύθυνση του κόμβου αυτού.

Παραδοχή: Δημιουργήσαμε ένα simulation περιβάλλον έτσι ώστε οι μέθοδοι Map και Reduce να έχουν πρακτική εφαρμογή. Θεοωρούμε ότι κάθε κόμβος (Mapper ή Reducer ) είναι σύνολο από είναι ένα σύνολο από mappers ή reducers αντίστοιχα.

Με την είσοδο καινούριου κόμβου στο σύστημα ο server στέλνει τη λίστα με αυτά τα taxi. Διακρίνουμε δύο περιπτώσεις:

• Όταν μπαίνει ένας reducer, παίρνει την IP του και την καταχωρεί στο πεδίο IP του κάθε taxi.

• Όταν μπαίνει ένας mapper, στέλνει τη λίστα με τα taxi που έχουν συνδεθεί.

Ο κόμβος mapper έχει τη λίστα με όλα τα taxi και όταν ξεκινήσει παίρνει από τη βάση λίστα με 27 mappers. Έπειτα υπολογίζει σύμφωνα με τη λίστα των taxi, τα taxi εκείνα που βρίσκονται σε απόσταση εντός 10km για κάθε mapper.

Παραδοχή: Λόγω συντεταγμένων στην βάση όλα τα taxi έβγαιναν σε κοντινή απόσταση από κάθε πελάτη, έχουμε κάνει ένα filtering στις αποστάσεις αυτές διπλασιάζοντας τες.

Γίνεται αντιστοίχιση κάθε mapper με κάποια taxi. Η κλάσση  mapper έχει ένα πεδίο πίνακα με αυτά τα taxi (TaxiArray). Αυτά τα taxi τα στελνει στον reducer και ο reducer κάνει το mapping από mapper σε taxi. Δηλ. ποιοί mappers έχουν ζητήσει το taxi.

Καλεί τη Reduce μέθοδο και αφού διαλέξει τους καλύτερους mappers στέλνει request για να τους πάρει. Εκείνοι το παίρνουν και γίνεται ένα reverse mapping και μετά οι mappers επιλέγουν ένα taxi. Η επιλογή αυτή είναι random. 

Ο reducer παίρνει τα confirmations από τους mappers και στέλνει τα confirmed και pending roots στον server. Όταν φτάσουν στον server εκείνος φτιάχνει τις αντίστοιχες λίστες, οι οποίες κατηγοριοποιούνται ως προς το ID του taxi. 

Πατώντας το κάθε στοιχείο της λίστας βλέπουμε το taxi και τους πελάτες με τις πορείες τους.  

Περιγραφή Εφαρμογής

Ο στόχος της "Taxi" εφαρμογής είναι η καλύτερη και ταχύτερη εξυπηρέτηση του κοινού. Η εφαρμογή μας φροντίζει να καλυφθούν όσο το δυνατόν περισσότεροι πελάτες. Αυτό επιτυγχάνεται γιατί βασική προϋπόθεση για την επιλογή των πελατών είναι η απόσταση τους, δηλαδή για κάθε πελάτη επιλέγεται το κοντινότερο ταξί. Σε κάθε πελάτη μπορούν να έρθουν μέχρι τρεις επιλογές ταξί και μπορεί να επιλέξει τη μία. Τα ταξί μπορούν να πάρουν μέχρι 4 πελάτες των οποίων το σημείο εκκίνησης και ο τελικός προορισμός να μην έχουν μεγάλη απόκλιση. Η εφαρμογή μας λειτουργεί με Google maps και μία βάση που παίρνουμε από εκεί τις συντεταγμένες της τοποθεσίας. Παρακάτω θα αναλύσουμε πως λειτουργεί εφαρμογή μας.

1η Φάση της εφαρμογής μας

Σε πρώτη φάση φτιάξαμε τον "σκελετό" της εφαρμογής μας η οποία υλοποιήθηκε με Map-Reduce. Με το πρόγραμμα Eclipse δημιουργήσαμε 2 interfaces με ονόματα Server και Worker. 

Ο server αποτελείται από τις εξής μεθόδους:

• void searchForWorkersByBroadcastingAMessage()
• ψάχνει για workers στέλνοντας μηνύματα.
• void listenForWorkerRegistrations()
• Ακούει σε μια συγκεκριμένη θύρα για τους διαθέσιμους workers. Οι workers αποφασίζουν αν θέλουν να εργαστούν ως mappers, reducers ή και τα δύο. Μόλις γίνει λήψη της αίτησης, τότε η μέθοδος handleRegistrationRequest επικαλείται.
• void handleRegistrationRequest( WorkerRegistrationRequest regRequest )
• Χειρίζεται τις εισερχόμενες {@link WorkerRegistrationRequest}s.
• void updateWorkersList()
• Αυτή η μέθοδος επικαλείται αν έχει περάσει ο καθορισμένος χρόνος από την τελευταία επίκληση της. Σκοπός της μεθόδου είναι να μαθαίνει ποιοι workers είναι διαθέσιμοι και έτοιμοι να δεχτούν εργασίες.
• void assignMapTask( MapTask mapTask, InetAddress address )
• Αναθέτει μία map εργασία στον worker.
• void assignReduceTask( MapTask mapTask, InetAddress address )
• Αναθέτει μeία reduce εργασία στον worker.
• void receiveMapResults()
• Παίρνει τα αποτελέσματα από τους mappers.
• void receiveReduceResults()
• Παίρνει τα αποτελέσματα από τους reducers.

Ο worker αποτελείται από τις εξής μεθόδους:

• void listenForMapTasks()
• όταν η μέθοδος αυτή κληθεί ο worker ξεκινάει να ακούει σε ένα συγκεκριμένο socket για map εργασίες.
• void listenForReduceTasks()
• όταν η μέθοδος αυτή κληθεί ο worker ξεκινάει να ακούει σε ένα συγκεκριμένο socket για reduce εργασίες.
• void sendMapOutputToServer( List<KeyValuePair> keyValuePairs, MapTask mapTask )
• Στέλνει τα αποτελέσματα της map συνάρτησης για μια ειδική εργασία πίσω στον server 
• void sendReduceOutputToServer( List<ReduceResult> reduceResults, ReduceTask reduceTask )
• Στέλνει τα αποτελέσματα της reduce συνάρτησης για μια ειδική εργασία πίσω στον server
• void prohibitMapTasks()
• Λέει στον server ότι η map εργασία είναι απαγορευμένη για αυτόν τον worker 
• void allowMapTasks()
• Λέει στον server ότι η map εργασία επιτρέπεται για αυτόν τον worker 
• void prohibitReduceTasks()
• Λέει στον server ότι η reduce εργασία απαγορεύεται για αυτόν τον worker
• void allowReduceTasks()
• Λέει στον server ότι η reduce εργασία επιτρέπεται για αυτόν τον worker

Η εικόνα αυτή είναι σε γενικές γραμμές ο τρόπος με τον οποίο λειτουργεί η εφαρμογή μας. 

Στη 2η φάση θα γίνει υλοποίηση της. 

2η Φάση της εφαρμογής μας

Η λειτουργία της εφαρμογής βασίζεται σε έναν αλγόριθμο που βρίσκεται στην κλάση ReducerActivity. Ο πελάτης στέλνει την αίτηση προς όλα τα ταξί, ο αλγόριθμός μας όμως ορίζει για κάθε πελάτη μόνο 3 επιλογές ταξί και αυτό για να υπάρξει ομαλή λειτουργία διαφορετικά θα μπορούσαν πολλά ταξί να πάνε σε ένα πελάτη και να υπάρξει πρόβλημα. Αυτός ο αλγόριθμος έχει ένα hashmap όπου έχει ένα μοναδικό αναγνωριστικό για κάθε πελάτη και μία λίστα των ταξί που θέλουν να τον εξυπηρετήσουν. Για τον καθορισμό του ταξί σε ένα πελάτη βασικό ρόλο παίζει η απόσταση του από το σημείο εκκίνησης των χρηστών καθώς το βασικό κριτήριο επιλογής η μικρότερη απόσταση του ταξί από τον πελάτη. Η διαδικασία αυτή είναι για τον πρώτο πελάτη του ταξί, ο οποίος καθορίζει την πορεία και την επιλογή επιπλέον πελατών αφού πρέπει το σημείο εκκίνησης και ο προορισμός τους να είναι σε μικρή απόσταση τουλάχιστον 500 μέτρα από του πρώτου για να μπορέσει να τους εξυπηρετήσει χωρίς βέβαια να έχουν μεγάλη απόκλιση οι διαδρομές τους.