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 αιτώντας εναλλακτικές διαδρομές μεταξύ των δύο σημείων (εκκίνηση , προορισμός) του χρήστη και καλεί τις συναρτήσεις της βάσης για την αξιολόγηση αυτών των διαδρομών και την επιλογή της βέλτιστης από αυτές . Η διαδρομή αυτή αποστέλλεται πίσω στον χρήστη που την ζήτησε.