Βέλτιστες διαδρομές σε κινητές συσκευές εκτός δικτύου
Loading...
Date
Authors
Μαντάς, Δημήτριος
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Είναι κοινώς αποδεκτό πως η ανάγκη για άμεσα διαθέσιμες υπηρεσίες δρομολόγησης είναι στενά συνυφασμένη με τη σύγχρονη ανθρώπινη δραστηριότητα. Παρόλα αυτά, ακόμα και στις μέρες μας, υπάρχουν πολλές περιπτώσεις όπου η ασύρματη διασυνδεσιμότητα δεν είναι δεδομένη. Για αυτόν το λόγο, η παροχή υπηρεσιών δρομολόγησης κάνοντας χρήση μόνο των περιορισμένων υπολογιστικών πόρων μίας κινητής συσκευής είναι ένα φλέγον ζήτημα που εκτιμάται πως θα απασχολήσει την επιστημονική κοινότητα όλα και περισσότερο στο άμεσο μέλλον. Λαμβάνοντας υπόψη τα παραπάνω, η παρούσα διπλωματική εργασία πραγματεύεται την υλοποίηση του αλγορίθμου Α* για χρήση σε κινητές συσκευές, καθώς και στην ενσωμάτωση αυτού σε μία πρότυπη εφαρμογή δρομολόγησης ανοικτού κώδικα για το λειτουργικό σύστημα Android ονόματι Torch.
Αυτό το έργο αποτελεί μία εκτενή προσέγγιση και προσπάθεια επίλυσης του προαναφερθέντος προβλήματος, από τη σφαιρική του μελέτη, στην κριτική επισκόπηση μερικών από τις ήδη υπάρχουσες εμπορικές λύσεις και στη μετέπειτα σύντηξη των σχετικών νεοαποκτηθέντων γνώσεων γύρω από το θέμα με ήδη υπάρχουσες, με τελικό σκοπό την παραγωγή ενός τεχνικά αξιόλογου προϊόντος. Έτσι, το κυρίως μέρος της παρούσας διπλωματικής εργασίας αγγίζει διάφορες θεματικές περιοχές, από την ανάπτυξη του βασικού θεωρητικού της υποβάθρου ανά γνωστικό πεδίο, στη διατύπωση βασικών γνώσεων γύρω από την ανάπτυξη εφαρμογών Android με τη γλώσσα προγραμματισμού Java. Ακόμα, ιδιαίτερη έμφαση δίνεται στην εκτενή ανάλυση της φιλοσοφίας τόσο του αλγορίθμου Α* όσο και αυτού του Dijkstra, τον οποίο αυτός επεκτείνει, σε θεωρητικό και πρακτικό επίπεδο. Λαμβάνοντας υπόψη τα παραπάνω, στη συνέχεια παρουσιάζεται λεπτομερώς το Torch από τη σκοπιά τόσο ενός μηχανικού λογισμικού όσο και του τελικού του χρήστη. Τέλος, παρουσιάζεται η πειραματική αξιολόγηση της εφαρμογής, η οποία πραγματοποιήθηκε μετρώντας τη χρόνο εκτέλεσης των αλγορίθμων Dijkstra και Α* για διάφορα κριτήρια βελτιστοποίησης. Τα αποτελέσματα αυτής της διαδικασίας έδειξαν πως, γενικά, ο αλγόριθμος Α* γενικά είναι κατά μέσο όρο περίπου μιάμιση φορά γρηγορότερος από αυτόν του Dijkstra για την εύρεση συντομότερων διαδρομών βάσει μήκους, με κατά βάση ανάλογα αποτελέσματα για δρομολόγηση βάσει χρονικής διάρκειας.
Το βασικό συμπέρασμα της παρούσας διπλωματικής εργασίας είναι ότι το Torch θα μπορούσε να χρησιμοποιηθεί ως ένα αξιόπιστο περιβάλλον δοκιμής τόσο νέων όσο και ήδη καθιερωμένων αλγορίθμων και δομών δεδομένων σε κινητές συσκευές.
Description
Keywords
Αλγόριθμος A*, Αλγόριθμος του Dijkstra, Βέλτιστες διαδρομές, Κινητές συσκευές εκτός σύνδεσης