Μελετη Βελτιστων Αλγοριθμων Αναζητησης Σε Δικτυα Κινητων Και Προσωπικων Επικοινωνιων

Abstract

Σκοπός αυτής της διπλωματικής εργασίας είναι η μελέτη ορισμένων αλγορίθμων για την ελαχιστοποίηση του κόστους αναζήτησης σε δίκτυα κινητών και προσωπικών επικοινωνιών. Αναζήτηση ονομάζεται η διαδικασία κατά την οποία το δίκτυο εντοπίζει ένα χρήστη, δηλαδή μαθαίνει την ταυτότητα του σταθμού βάσης που εξυπηρετεί το κινητό τερματικό του.Αφού γίνει μια αναδρομή στην πρόσφατη έρευνα γύρω από τη διαχείριση θέσης (που περιλαμβάνει όχι μόνο την αναζήτηση αλλά και τη διαδικασία ενημέρωσης θέσης), αναλύεται η βασική στρατηγική για μείωση του κόστους αναζήτησης: η αναζήτηση κατά φθίνουσα σειρά πιθανοτήτων εντοπισμού. Η γενική ιδέα είναι η εξής: να μην γίνεται ταυτόχρονη έρευνα για το ζητούμενο τερματικό σε όλες τις πιθανές θέσεις, αλλά η διαδικασία να επιτελείται σε διαδοχικά βήματα, με τρόπο ώστε θέσεις που εμφανίζουν σχετικά μεγάλη πιθανότητα εντοπισμού να ελέγχονται πριν από θέσεις με μικρότερη πιθανότητα.Πάνω σ' αυτόν τον κεντρικό άξονα σχεδιάζονται και μελετώνται τέσσερα συγκεκριμένα σχήματα αναζήτησης:1.Ένα γενικό σχήμα αναζήτησης κατά φθίνουσα πιθανότητα θέσης, όπου οι πιθανότητες εντοπισμού υπολογίζονται με στατικό τρόπο.2.Ένα σχήμα αναζήτησης με βάση την πληροφορία της κυψέλης τελευταίας αλληλεπίδρασης, δηλαδή της τελευταίας θέσης όπου το δίκτυο ήρθε σε επαφή με το ζητούμενο τερματικό. Οι πιθανότητες εντοπισμού υπολογίζονται αναλυτικά.3.Ένας αλγόριθμος μάθησης σε πραγματικό χρόνο, που χρησιμοποιεί την πληροφορία της κυψέλης τελευταίας αλληλεπίδρασης και ταυτόχρονα καταγράφει το προφίλ κίνησης των χρηστών, παρατηρώντας τις επιτυχίες και τις αποτυχίες των διαδοχικών προσπαθειών αναζήτησης. Έτσι, δημιουργεί τα απαραίτητα δεδομένα για τον υπολογισμό των πιθανοτήτων εντοπισμού.4.Ένας αλγόριθμος τοπικής αναζήτησης, που επίσης μαθαίνει το προφίλ κίνησης σε πραγματικό χρόνο, ο οποίος ερευνά διαδοχικά γεωγραφικά γειτονικές κυψέλες και ανακαλύπτει τις κύριες διαδρομές πάνω στις οποίες προτιμούν να κινούνται οι χρήστες.Η σύγκριση της επίδοσης των τεσσάρων σχημάτων γίνεται τόσο βάσει θεωρητικών υπολογισμών, όσο και μέσω προσομοίωσής με τη βοήθεια ηλεκτρονικού υπολογιστή. Χρησιμοποιούνται δύο μαθηματικά μοντέλα για την αναπαράσταση της κίνησης των χρηστών του δικτύου: ένα συμμετρικό μοντέλο τυχαίου περιπάτου και ένα μαρκοβιανό μοντέλο κίνησης με προτίμηση για μια κύρια κατεύθυνση.Η ανάλυση αποδεικνύει πόσο χρήσιμη είναι για την ελαχιστοποίηση του κόστους αναζήτησης η πληροφορία της κυψέλης τελευταίας αλληλεπίδρασης. Τα σχήματα αυξημένης «ευφυΐας», που έχουν τη δυνατότητα να εκμεταλλευτούν την πληροφορία αυτή, εμφανίζουν δραματικά καλύτερη απόδοση. Επίσης, δείχνεται πως οι δύο αλγόριθμοι μάθησης καταφέρνουν- με σχετικά χαμηλό κόστος- να ανακαλύψουν τα ιδιαίτερα χαρακτηριστικά της κίνησης που ακολουθείται και να προσαρμόσουν ανάλογα τη διαδικασία αναζήτησης. Στη συνέχεια ερευνάται διεξοδικά η επίδραση που έχει η διασπορά των χρόνων διαμονής στις κυψέλες (οι οποίοι μοντελοποιούνται με βάση τη Γάμα κατανομή) στην απόδοση των αλγορίθμων. Τέλος, μελετάται το θέμα της αυξημένης καθυστέρησης που επιβάλει η ακολουθιακή αναζήτηση. Παρουσιάζονται τρόποι περιορισμού της και αποδεικνύεται ότι μπορεί να επιτευχθεί αξιόλογη μείωση του κόστους αναζήτησης χωρίς μεγάλη επιβάρυνση ως προς την καθυστέρηση.Το γενικό συμπέρασμα είναι πως οι ακολουθιακοί αλγόριθμοι, και ιδιαίτερα τα τέσσερα σχήματα που παρουσιάζονται στα πλαίσια της εργασίας, βελτιώνουν σημαντικά την επίδοση της διαδικασίας αναζήτησης. Επιπλέον, είναι εφικτή η άμεση- και χωρίς υπέρμετρο κόστος- εφαρμογή τους στα σύγχρονα δίκτυα κινητών επικοινωνιών.