OptiPath

Εισαγωγή

Η κίνηση (traffic) και η συμφόρηση είναι δύο έννοιες που έχουν απασχολήσει τους ανθρώπους σε διάφορους τομείς της καθημερινότητάς τους. Η συμφόρηση στους δρόμους αποτελεί ένα σημαντικό πρόβλημα των μεγάλων κυρίως πόλεων. Έχουν γίνει αρκετές προσπάθειες για τον έλεγχο της ροής των οχημάτων και την αποφυγή της συμφόρησης είτε με κλασσικούς τρόπους (π.χ. δακτύλιος) είτε με τη χρήση της τεχνολογίας.

Τα κινητά τηλέφωνα έχουν ήδη εισβάλει  αρκετά χρόνια στην καθημερινότητά μας και έχουν γίνει αναπόσπαστο κομμάτι της. Την τελευταία πενταετία παρατηρείται μία σημαντική ανάπτυξη στον τομέα της βιομηχανίας κινητής τηλεφωνίας. Νέες εταιρίες προτείνουν λύσεις οι οποίες ενσωματώνουν πρωτοποριακές software αλλά και hardware καινοτομίες. Στις μέρες μας τα έξυπνα τηλέφωνα (smartphones) μας παρέχουν εκτός από τις κλασσικές λειτουργίες, υπηρεσίες όπως GPS (Global Positioning System), γρήγορο Mobile Internet, μεγάλο αποθηκευτικό χώρο, ισχυρές (πλέον και πολυπύρηνες) CPU,  multimedia (photo, video, ήχος).

Σημαντικό ρόλο σε μία συσκευή κινητής τηλεφωνίας παίζει και το λειτουργικό της σύστημα. Symbian,Windows Phone, Maemo, iOS είναι μερικά μόνο από αυτά. Πιο πρόσφατη εξέλιξη είναι το Android που δημιουργήθηκε από την Google.

Με δεδομένη την ισχύ, την αποθηκευτική ικανότητα και τις υπόλοιπες δυνατότητες των συσκευών κινητής τηλεφωνίας το ενδιαφέρον των ερευνητών στρέφεται στην προσπάθεια δημιουργίας εφαρμογών που μπορούν να χρησιμοποιήσουν παράλληλα αυτή την ισχύ για την επίλυση μεγάλων προβλημάτων.

Οι περισσότερες από τις εφαρμογές για smartphone είναι γραμμένες έτσι ώστε να χρησιμοποιούνται μόνο από έναν χρήστη και να αξιοποιούν τους πόρους μίας μόνο smartphone συσκευής. Πλέον, υπάρχει η δυνατότητα να αξιοποιηθούν συλλογικά η υπολογιστική δυνατότητα, ο αποθηκευτικός χώρος και οι αισθητήρες πολλαπλών δικτυωμένων smartphones έτσι ώστε να δημιουργήσουν ένα κατανεμημένο σύστημα που μπορεί να υποστηρίξει μια πληθώρα νέων εφαρμογών. Χρησιμοποιώντας αυτούς τους πόρους, οι εφαρμογές θα μπορούσαν να χρησιμοποιήσουν εύκολα τα συνδυασμένα δεδομένα και τις υπολογιστικές ικανότητες ενός δικτύου smartphones προκειμένου να παράγουν χρήσιμα αποτελέσματα για τους χρήστες τόσο εντός όσο και εκτός του δικτύου κινητής τηλεφωνίας.

Η χρήση των smartphones προσφέρει πλεονεκτήματα σε σχέση με τη χρήση του παραδοσιακού hardware, όπως η άμεση πρόσβαση σε πολυμέσα και άλλα δεδομένα που είναι αποθηκευμένα από τους χρήστες στις συσκευές ή που έχουν παραχθεί κατά τη χρήση τους. Αυτό επιτυγχάνεται χωρίς να γίνεται διακίνηση μεγάλου όγκου πληροφορίας στο δίκτυο με αποτέλεσμα να έχουμε πιο αποτελεσματική πρόσβαση στα δεδομένα που αποθηκεύονται σε άλλες κινητές συσκευές. Επίσης, μπορούν να δημιουργηθούν καθεστώτα συλλογικής ιδιοκτησίας και συντήρησης του υλικού.

Σκοπός της εργασίας μας είναι η ανάπτυξη ενός κατανεμημένου Client – Server συστήματος που θα επιτρέπει στο χρήστη να μπορεί χρησιμοποιώντας το smartphone του να αναζητά και να βρίσκει την συντομότερη διαδρομή από ένα σημείο σε ένα άλλο.  Για την επίτευξη του στόχου έγινε χρήση τεχνολογιών όπως GPS, βάσεις δεδομένων και πρόσβαση στο διαδίκτυο με χρήση δικτύων κινητών επικοινωνιών.

Android

Το Android είναι ένα λειτουργικό σύστημα για συσκευές κινητής τηλεφωνίας το οποίο τρέχει τον πυρήνα του λειτουργικού Linux. Αρχικά αναπτύχθηκε από την Google και αργότερα από την Open Handset Alliance. Επιτρέπει στους κατασκευαστές λογισμικού να γράφουν κώδικα με την χρήση της γλώσσας προγραμματισμού Java, ελέγχοντας την συσκευή μέσω βιβλιοθηκών λογισμικού ανεπτυγμένων από την Google.

Η πρώτη παρουσίαση της πλατφόρμας Android έγινε στις 5 Νοεμβρίου 2007, παράλληλα με την ανακοίνωση της ίδρυσης του οργανισμού Open Handset Alliance, μιας κοινοπραξίας 48 τηλεπικοινωνιακών εταιριών, εταιριών λογισμικού καθώς και κατασκευής hardware, οι οποίες είναι αφιερωμένες στην ανάπτυξη και εξέλιξη ανοιχτών προτύπων στις συσκευές κινητής τηλεφωνίας. Η Google δημοσίευσε το μεγαλύτερο μέρος του κώδικα του Android υπό τους όρους της Apache License, μιας ελεύθερης άδειας λογισμικού.

Χρησιμοποιεί το Dalvik Virtual Machine για την εκτέλεση των εφαρμογών. Το Dalvik έχει βελτιστοποιηθεί για να τρέχει σε συσκευές με περιορισμένη CPU, μνήμη και πόρους ενέργειας. Υλοποιεί ένα υποσύνολο της Java 2 Platform Standard Edition (J2SE), χρησιμοποιώντας τις βιβλιοθήκες από τον Apache Harmony Apache Java.

Το Android παρέχει μία διεπαφή για τις συσκευές συστήματος και τις υπηρεσίες, μέσα από ένα σύνολο από Java Packages, συμπεριλαμβανομένων των android.os, android.hardware, android.location, και android.media. Αυτό καθιστά εύκολη την πρόσβαση στα δεδομένα πολυμέσων, στα δεδομένα των αισθητήρων, στους πόρους του συστήματος, καθώς και σε πληροφορίες τοποθεσίας.

Περιγραφή προβλήματος

Στα πλαίσια της εργασίας, θα αντιμετωπίσουμε το πρόβλημα της εύρεσης της βέλτιστης διαδρομής από ένα σημείο σε ένα άλλο κινούμενοι με όχημα, βασιζόμενοι σε δεδομένα που έχουν καταγραφεί από χρήστες που έχουν κινηθεί στα πλαίσια αυτής της διαδρομής, και σε δεδομένα που παρέχονται από το Google Maps Api.

Κάθε χρήστης (client) θα έχει τη δυνατότητα να ρωτάει το σύστημα για μία διαδρομή από ένα σημείο σε ένα άλλο (route) και το σύστημα θα του επιστρέφει τη βέλτιστη διαδρομή, με βάση τα δεδομένα κυκλοφοριακής συμφόρησης που έχουν συλλεχθεί και το μήκος της. Το πρόβλημα αυτό είναι μια παραλλαγή εμπορικού Live Traffic που χρησιμοποιείται σε πολλές χώρες.

Στο Live Traffic τα δεδομένα για τη συμφόρηση στις οδούς δίνονται από αισθητήρες οι οποίοι βρίσκονται κυρίως στα πεζοδρόμια ή στην άσφαλτο και συνδέονται μεταξύ τους με ένα προηγμένο δίκτυο οπτικών ινών. Η πληροφορία από τους αισθητήρες συγκεντρώνεται σε ένα υπολογιστικό σύστημα το οποίο επικοινωνεί με τους δορυφόρους ώστε να αποστέλλει την κατάλληλη πληροφορία στις συσκευές των χρηστών.Στην προσέγγισή μας τα δεδομένα καταγράφονται από τους χρήστες της εφαρμογής την ώρα που κινούνται με το όχημα τους. 


Το smartphone του χρήστη κάνοντας χρήση του GPS sensor καταγράφει τη διαδρομή που διανύθηκε και το χρόνο που χρειάστηκε για να τη διανύσει. Η διαδρομή αυτή αποτελείται από μικρότερα κομμάτια τα οποία από εδώ και στο εξής θα τα ονομάζουμε tokens. Έτσι ο κάθε χρήστης της εφαρμογής ενημερώνει το σύστημα με την πληροφορία για τα tokens που έχει διανύσει. Η πληροφορία αυτή διατηρείται για ένα συγκεκριμένο χρονικό διάστημα αφού π.χ. δεν θα είχε νόημα να προσπαθήσουμε να εξάγουμε συμπεράσματα για την κίνηση του οδικού δικτύου του κέντρου της Αθήνας στις 11:00 μ.μ. με δεδομένα που λήφθησαν στις 3:00 μ.μ

Αρχιτεκτονική – Περιγραφή συστήματος

Η υλοποίησή μας βασίζεται στην αρχιτεκτονική  Client- Server. Οι clients είναι κινητές συσκευές με λειτουργικό σύστημα Android που εκτελούν την εφαρμογή OptiPath, ενώ ο server έχει υλοποιηθεί σε java και μπορεί να εκτελεστεί σε οποιοδήποτε μηχάνημα.

Ο client, με τη χρήση της εφαρμογής OptiPath, καθώς ο χρήστης κινείται, παρέχει σε τακτά χρονικά διαστήματα στον server tokens για τη διαδρομή την οποία ακολουθεί, ακόμη και αν ο χρήστης χρησιμοποιεί κάποια άλλη εφαρμογή στο προσκήνιο. Επίσης, μέσω της εφαρμογής OptiPath ο χρήστης μπορεί να επιλέξει μία διαδρομή, μέσω αγγίγματος στον χάρτη ή με τη χρήση αναζήτησης που παρέχεται. Η εφαρμογή δημιουργεί ένα αίτημα προς τον server, με τα δεδομένα της διαδρομής και λαμβάνει ως απάντηση την βέλτιστη διαδρομή, την οποία και παρουσιάζει στον χάρτη.

Ο server, είναι υπεύθυνος για τη συλλογή δεδομένων από τους clients και την αποθήκευσή τους σε μία βάση δεδομένων. Επίσης, είναι υπεύθυνος για την λήψη και επεξεργασία των αιτημάτων από τους clients για εύρεση βέλτιστης διαδρομής. Έτσι, όταν λάβει ένα ερώτημα, δημιουργεί και εκτελεί επερωτήσεις (queries) προς το Google Maps προκειμένου να αποκτήσει εναλλακτικές διαδρομές για αυτό το ερώτημα. Στη συνεχεία αξιολογεί την διαδρομή με βάση τα αποθηκευμένα δεδομένα και την απόστασή της και επιστρέφει στον client την βέλτιστη.

Common Classes

Πριν ξεκινήσουμε την περιγραφή των διαφόρων συστατικών της αρχιτεκτονικής του συστήματος θα αναφερθούμε σε κλάσεις οι οποίες είναι κοινές στον client – server και συμβάλουν στην μεταξύ τους επικοινωνία.

·         Η κλάση PointΤ περιγράφει ένα σημείο στο παγκόσμοιο σύστημα συντεταγμένων. Αποτελείται από δύο μεταβλητές τύπου double  οι οποίες απεικονίζουν το γεωγραφικό μήκος και πλάτος του αντικειμένου (latitude και longitude). Επίσης περιέχει μεθόδους για τον υπολογισμό της απόστασης μεταξύ του ιδίου του αντικειμένου και ενός άλλου σημείου (getDistance(PointT p), όπως και τον έλεγχο για την ομοιότητα δύο σημείων (isSamePoint(PointT p).

·         Η κλάση Token αντιπροσωπεύει ένα μέρος της διαδρομής απεικονιζόμενο με δύο σημεία του παγκόσμιου συστήματος συντεταγμένων, δηλαδή δύο αντικείμενα PointΤ. Επίσης περιέχει δεδομένα: για την χρονική στιγμή την οποία κάποιος χρήστης βρέθηκε στο αρχικό σημείο του Token (startingTime), την χρονική διάρκεια σε millisecond που χρειάστηκε ο χρήστης για να διανύσει το Token (duration) καθώς και την απόσταση του Token εκφρασμένη σε μέτρα (distance). Η κλάση αυτή περιέχει τρεις διαφορετικούς constructors που εφαρμόζονται ανάλογα με την πολιτική που ακολουθείται (αν το αντικείμενο δημιουργείται την χρονική στιγμή που βρίσκεται στην αρχή του Token ο χρήστης ή την χρονική στιγμή που βρίσκεται στο τέλος του Token,  ή αν δημιουργηθεί ένα Token με ελειπής πληροφορίες). Τέλος περιέχει πλήθος μεθόδων για τον υπολογισμό γεωμετρικών και μή στοιχείων. Αναλυτικότερα, Η μέθοδος isSameToken(Token t) ελέγχει αν τα σημεία αρχής και τέλους του Token συμπίπτουν με τα σημεία αρχής και τέλους ενός διαφορετικού δεδομένου Token. Η μέθοδος isSameToken(Token t, int meters) έχει την ίδια λειτουργία με την παραπάνω μέθοδο, με την μόνη διαφορά ότι για τον έλεγχο των δύο Tokens μπορεί να υπάρξει μια απόκλιση εκφρασμένη σε μέτρα μεταξύ των δύο Tokens. Η μέθοδος isOnTheLine(PointT p, double div) επιστρέφει true αν το δεδομένο σημείο PointT βρίσκεται στην νοητή γραμμή του Token που εκφράζει το συγκεκριμένο αντικείμενο (δίνεται ως όρισμα επίσης παράγοντας απόκλισης του σημείο από την γραμμή). Η μέθοδος isPartOfLine(PointT p, double div) επιστρέφει true αν το δεδομένο σημείο PointT ανήκει στο ευθύγραμμο τμήμα του Token που εκφράζει το συγκεκριμένο αντικείμενο (και εδώ δίνεται παράγοντας απόκλισης). Η μέθοδος estimateTime(Token tok) υπολογίζει προσσεγγιστικά τον χρόνο που χρειάζεται για να διανιστεί το Token δεδομένου ενός άλλου Token χρησιμοποιώντας την απλή μέθοδο των τριών.

·         Η κλάση TokenList περιγράφει μια διαδρομή. Η διαδρομή αυτή αποτελείται από μικρότερα τμήματα διαδρομών οι οποίες αποτελούνται από Tokens. Επίσης η κλάση αυτή υλοποιεί λειτουργίες αποθήκευσης και ανάκτησης του αντικειμένου σε αρχείο και λειτουργία συντήρησης της λίστας. Συγκεκριμένα η κλάση TokenList περιλαμβάνει: μια λίστα από Tokens (ArrayList<Token> list), καθώς και μεταβλητές για την αποθήκευση υπολογισμένου χρόνου διαδρομής από το σύστημα  (estimatedTime) και υπολογισμένου χρόνου διαδρομής από το Google Maps (approximateTime), μεταβλητή για την αποθήκευση του μήκους της διαδρομής σε μέτρα (distance),  μεταβλητή για το όνομα του αρχείου αποθήκευσης της λίστας (storeList), χρόνο ζωής των Tokens στην λίστα (ttl) , λίστα για τις οδηγίες της διαδρομής που επιστρέφονται από το Google Maps (instructions) και οι παρακάτω σταθερές που δηλώνουν τον τύπο της διαδρομής

o   OTHERTLIST: Λίστα άγνωστου τύπου

o   CLIENTLIST:   Λίστα με πληροφορίες και Tokens που σύλλεξε ένας χρήστης για αποστολή στον server

o   GOOGLELIST: Λίστα η οποία περιέχει Tokens που επέστρεψε το Google Maps για μια συγκεκριμένη διαδρομή

o   SERVERLIST: Λίστα που παράγει ο server για την απάντηση σε ερωτήματα της βέλτιστης διαδρομής από τους clients.

Η κλάση TokenList περιλαμβάνει μεθόδους για την εκκαθάριση παλιών εγγραφών – Tokens από την λίστα, όπου ένα διαφορετικό thread από το κύριο thread της εφαρμογής αναστέλλεται και σε σταθερή χρονική περίοδο αφυπνίζεται και καλεί την μέθοδο cleanList() η οποία διαγράφει παλιές εγγραφές από την λίστα. Επίσης, η κλάση TokenList περιλαμβάνει μεθόδους για την αποθήκευση των Tokens της λίστας σε αρχείο saveList(String file), μεθόδους για την ανάκτηση μια λίστας από αρχείο loadList(String file). Για την αποθήκευση των Tokens σε αρχείο χρησιμοποιείται η κλάση Reader η οποία θεωρείται βοηθητική κλάση και δεν θα περιγραφεί.

Ορισμένες από τις παραπάνω λειτουργίες των κλάσεων δεν χρησιμοποιούνται στην τελική παραδοτέα έκδοση του συστήματος. Οι λειτουργίες αυτές υλοποιήθηκαν για την βοήθεια στην ανάπτυξη του συστήματος, για λόγους debugging, ή επειδή η υλοποίησή τους κατά τα αρχικά στάδια ανάπτυξης του συστήματος είχε κριθεί αναγκαία.

Server

Η λειτουργία του server έγκειται στην συνεχή ακρόαση των socket επικοινωνίας με τους χρήστες. Αν ο server δεχτεί νέα δείγματα με πληροφορίες κίνησης τα καταχωρεί στη βάση δεδομένων.

Αν  ο server δεχτεί αίτημα επιλογή μίας διαδρομής , τότε σε πρώτη φάση κάνει μία επερώτηση στην Google αιτώντας εναλλακτικές διαδρομές μεταξύ των δύο σημείων (εκκίνηση , προορισμός) του χρήστη και καλεί τις συναρτήσεις της βάσης για την αξιολόγηση αυτών των διαδρομών και την επιλογή της βέλτιστης από αυτές . Η διαδρομή αυτή αποστέλλεται πίσω στον χρήστη που την ζήτησε. 

Google Maps

Η διεπαφή και οι λειτουργίες επικοινωνίας με το Google Maps βρίσκονται στην κλάση Routes η οποία υλοποιείται στον Server. Η κλάση Routes εκτός των άλλων περιέχει μια λίστα από διαδρομές (googleRoutes) και είναι υπεύθυνη για την ανάκτηση βασικής και εναλλακτικών διαδρομών από το Google Maps και την παράδοση αυτών στον server του συστήματος. Αναλυτικότερα κατά την δημιουργία ενός αντικειμένου Routes δίνονται το γεωγραφικό μήκος και πλάτος του σημείου εκκίνησης και του σημείου τερματισμού μιας διαδρομής. Ο constructor καλεί την μέθοδο createFirstUrl(String sLat, String sLng, String dLat, String dLng, String type) η οποία δημιουργεί ένα url της μορφής:

http://maps.google.com/maps?f=d&source=s_d&saddr=startLatitude,startlongitude&saddr=destinationLatitude,destinationlongitude&hl=en&mra=ls&ie=UTF8&z=13&output=kml

όπου τα startLatitude, startlongitude, destinationLatitude και destinationlongitude είναι γεωγραφικά μήκη και πλάτη με την μορφή δεκαδικών αριθμών. Στην συνέχεια, με τη χρήση HTTP Request,  επιστρέφεται η απάντηση σε αρχείο kml, το οποίο δίνεται ως είσοδος στην μέθοδο getRoute(String kml) όπου με τη χρήση Regular Expressions γίνεται parsing και αντλούνται τα Tokens τις διαδρομής. Η διαδρομή αποθηκεύεται στην λίστα googleRoutes.

Στη συνέχεια δημιουργείται ένα νέο url της μορφής:

http://maps.google.com/maps?f=d&source=s_d&saddr=startLatitude,startlongitude&saddr=destinationLatitude,destinationlongitude&hl=en&mra=ls&ie=UTF8&z=13&output=js

όπου τα startLatitude, startlongitude, destinationLatitude και destinationlongitude είναι γεωγραφικά μήκη και πλάτη με την μορφή δεκαδικών αριθμών. Στην συνέχεια, με τη χρήση HTTP Request,  επιστρέφεται η απάντηση η οποία δίνεται ως είσοδος στην μέθοδο getAltPoints(String temp) όπου με τη χρήση Regular Expressions γίνεται parsing και αντλούνται τα Alternative Points τα οποία χρησιμοποιούνται για την δημιουργία ερωτημάτων για εναλλακτικές διαδρομές. 

Για κάθε Alternative Point δημιουργείται ένα νέο url της μορφής:

http://maps.google.com/maps?via=1&saddr=startLatitude,startlongitude&daddr=destinationLatitude,destinationlongitude+to:alternativeLatitude,alternativelongitude&output=kml

όπου τα startLatitude, startlongitude, destinationLatitude, destinationlongitude, alternativeLatitude και alternativelongitude είναι γεωγραφικά μήκη και πλάτη με την μορφή δεκαδικών αριθμών και τα alternativeLatitude και alternativelongitude απεικονίζουν το εναλλακτικό σημείο απ’ το οποίο πρέπει να περνάει η διαδρομή που θα επιστραφεί. Για κάθε ένα από αυτά τα urls επιστρέφεται ένα αρχείο απάντησης τύπου kml για το οποίο καλείται η μέθοδος getRoute(String kml) όπως προηγουμένως, και αποθηκεύεται η νέα διαδρομή στην λίστα googleRoutes. Τέλος, να σημειωθεί πως για κάθε διαδρομή καλούνται οι μέθοδοι getDistance(String temp), getTime(String temp) και getDirections(String temp) οι οποίες μέσω parsing επιστρέφουν το μήκος, τον χρόνο της διαδρομής και τις οδηγίες πλοήγησης αντίστοιχα.

Επικοινωνία Client – Server

     Η επικοινωνία μεταξύ server – client πραγματοποιείται για δύο λόγους. Είτε για την υποβολή νέων πληροφοριών (Tokens) από τον client, είτε για την απάντηση της βέλτιστης διαδρομής σε ερώτημα ενός client. Και στις δύο περιπτώσεις, οι δύο οντότητες επικοινωνούν στέλνοντας ένα αντικείμενο TokenList με διαφορετικό τύπο κάθε φορά. Αναλυτικότερα ο server ανοίγει ένα ServerSocket και μέσα σε ένα ατέρμονα βρόγχο περιμένει για τις αιτήσεις των clients. Μόλις δεχθεί μια νέα αίτηση, την δέχεται, εκκινεί ένα νέο thread το οποίο ανοίγει τα ρεύματα εισόδου και εξόδου (με την χρήση των αντικειμένων ObjectInputStream και ObjectOutputStream). Στην συνέχεια το νέο thread λαμβάνει από το ρεύμα εισόδου το εισερχόμενο μήνυμα το οποίο το μετατρέπει (Casting) σε ένα αντικείμενο TokenList και εξετάζει τον τύπο του, δηλαδή αν είναι CLIENTLIST όπου πρόκειται για παραλαβή νέων δεδομένων ή GOOGLELIST όπου πρόκειται για ερώτημα βέλτιστης διαδρομής.

·                   Στην περίπτωση παραλαβής νέων δεδομένων, για κάθε Token της λίστας καλείται η μέθοδος insertIntoTokenDB(int AndroidDeviceID,double PointStartLong, double PointStartLat, double PointEndLong, double PointEndLat, float Speed, long Time, float Distance), όπου και αποθηκεύεται το νέο Token στην βάση δεδομένων

·                  Στην περίπτωση της απόκρισης για βέλτιστη διαδρομή το αντικείμενο TokenList περιέχει ένα Token το οποίο περιλαμβάνει το σημείο εκκίνησης και το σημείο τερματισμού της διαδρομής που θέλει να διανύσει ο χρήστης. Τα σημεία αυτά δίνονται στον constructor της κλάσης Routes όπου και ανακτούνται οι διαδρομές τις Google για την διαδρομή που επιθυμεί να διανύσει ο χρήστης. Στην συνέχεια για κάθε μια από αυτές τις διαδρομές καλείται η μέθοδος estimateRouteTime(TokenList route,  int minutes) της κλάσης GoogleMapsDB όπου και βαθμολογείται η διαδρομή με βάση το μήκος της και τον χρόνο που χρειάζεται για να διανυθεί. Τέλος, εγγράφεται στο ρεύμα εξόδου που έχει ανοιχτεί για επικοινωνία με τον client το αντικείμενο TokenList με τον μεγαλύτερο score. 

Database

Η βάση δεδομένων για την καταγραφή των δεδομένων κίνησης στον Server περιγράφεται από την κλάση GoogleMapsDB. Στην κλάση αυτήν περιλαμβάνονται όλες οι σχετικές συναρτήσεις με την δημιουργία , την διαχείριση της βάσης και την εισαγωγή σε αυτήν των tokens . Αναλύοντας τις συναρτήσεις της κλάσης έχουμε :

public GoogleMapsDB

Κατά την εκτέλεση του constructor της κλάσης , επιτυγχάνεται η σύνδεση στον server και η δημιουργία ,αν δεν υπάρχει ήδη, της βάσης που αποτελείται από ένα πίνακα(table) token_db στον οποίο θα καταχωρηθούν τα tokens που αποστέλλονται από τους χρήστες της εφαρμογής .

Ο πίνακας που δημιουργείται περιλαμβάνει εγγραφές, που περιέχουν τις πληροφορίες για κάθε token. Τέτοιες πληροφορίες είναι ο εσωτερικός κωδικός, που αντιστοιχεί στην συνδεδεμένη συσκευή Android που απέστειλε τα δεδομένα, ο κωδικός του ίδιου του token μέσα στην βάση, τα στοιχεία που περιγράφουν το token, όπως το σημείο αρχής και τέλους του, η μέση ταχύτητα του οχήματος σε αυτό το token και τέλος το μήκος του.

Για γρηγορότερη αναζήτηση μέσα στην βάση, έχουν δημιουργηθεί ευρετήρια στα δεδομένα θέσης του token.

void insertIntoTokenDB

Η συνάρτηση αυτή εισάγει ένα token μέσα στην βάση και καλείται απευθείας από την εφαρμογή  του server επαναληπτικά, κάθε φορά που κάποιος χρήστης προσφέρει στο σύστημα τα δεδομένα για την κίνηση, που αντιμετώπισε.

void deleteOlderThan(int minutes)

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

double estimateRouteTime(TokenList route,  int minutes)

Η συνάρτηση αυτή είναι η σημαντικότερη στην κλάση, και σκοπός της είναι, δεδομένης μίας διαδρομής να της αποδώσει μία εκτίμηση κυκλοφοριακής συμφόρησης χρησιμοποιώντας συνδυαστικά τα  συγκεντρωμένα δεδομένα και  την εκτίμηση που δίνει η ίδια η Google .

Η διαδικασία περιλαμβάνει την επιλογή των token της βάσης, που αντιστοιχούν στην διαδρομή. Στην επιλογή αυτή για να υπολογίσουμε και την πιθανή έλλειψη ακρίβειας του δέκτη GPS της συσκευής, έχει εισαχθεί και ένας παράγοντας ακρίβειας ως προς την πραγματική θέση. Η βελτιστοποίηση της τιμής του ανάλογα με την βαθμό ακρίβειας εύρεσης της τοποθεσίας (πχ. μεγαλύτερος αριθμός συνδεδεμένων δορυφόρων επιφέρει καλύτερη ακρίβεια ) απομένει να ρυθμιστεί με περαιτέρω μετρήσεις σε πραγματικό περιβάλλον.

Σχετικά με τα δεδομένα, που ανακτήσαμε από την βάση, αυτά καθορίζουν την τελική αξιολόγηση της διαδρομής με διαφορετικές βαρύτητες. Όσο πλησιέστερο χρονικά είναι το token στην χρονική στιγμή της επερώτησης του χρήστη, τόσο μεγαλύτερη βαρύτητα θα έχει στο τελικό αποτέλεσμα. Τα tokens χωρίζονται σε τρεις κλάσεις με την βαρύτητα, που λαμβάνουν  να αντιστοιχεί στην χρονική κλάση στην οποία ανήκουν. Τα tokens της πρώτης κλάσης αντιστοιχούν στα πιο πρόσφατα δείγματα και απέχουν χρονικά λιγότερο από το ένα τρίτο του χρονικού παραθύρου minutes (στο παράδειγμά μας είναι minutes = 30 λεπτά ) και λαμβάνουν βαρύτητα 60%, αυτά της δεύτερης κλάσης  (1/3 minutes < t <2/3 minutes)  25% και τα υπόλοιπα δείγματα μέχρι την λήξη του χρονικού παραθύρου βαρύτητα 15%.

Στην περίπτωση που κάποια tokens της διαδρομής δεν αντιστοιχούν σε δείγματα μέσα στην βάση δεδομένων, τότε λαμβάνεται η προϋπολογισμένη προσεγγιστική  τιμή της Google για τα token αυτά.