Αλγόριθμοι Δρομολόγησης Σε Ασύρματα Δίκτυα Πλέγματος Με Χρήση Της Μαρκοβιανής Θεωρίας Αποφάσεων

Abstract

Σκοπός της παρούσας διπλωματικής εργασίας είναι η σχεδίαση ενός αλγορίθμου δρομολόγησης δεδομένων σε ασύρματα δίκτυα πλέγματος που λειτουργούν υπό συνθήκες διαλείψεων με χρήση μαρκοβιανών διαδικασιών λήψης αποφάσεων. Τα δεδομένα στο δίκτυο θεωρείται ότι μεταφέρονται με τη βοήθεια IP πακέτων τα οποία επιθυμούν να φτάσουν από τον κόμβο-πηγή στον κόμβο-προορισμό με την ελάχιστη από-άκρο-σε-άκρο καθυστέρηση και ταυτόχρονα τη μέγιστη αξιοπιστία. Όταν ένα IP πακέτο φθάσει σε έναν κόμβο του δικτύου πρέπει να επιλεγεί σε ποιον από τους γειτονικούς του κόμβους θα δρομολογηθεί. Το βασικό κριτήριο για την απόφαση αυτή είναι η πιθανότητα επιτυχημένης μετάδοσης η οποία επηρεάζεται από την ισχύ εκπομπής των κόμβων. Με χρήση των εξισώσεων Bellman υπολογίζεται η βέλτιστη πολιτική δρομολόγησης για κάθε πακέτο και, ταυτόχρονα, διερευνάται η σχέση μεταξύ καθυστέρησης μετάδοσης και ισχύος εκπομπής. Στο Κεφάλαιο 1 γίνεται γενική αναφορά στα βασικά χαρακτηριστικά των ασυρμάτων δικτύων πλέγματος και θίγεται το θέμα της δρομολόγησης σε δίκτυα αυτού του τύπου. Στο Κεφάλαιο 2 δίδονται τα βασικά στοιχεία της μαρκοβιανής θεωρίας και παρουσιάζονται οι βασικοί αλγόριθμοι επίλυσης μαρκοβιανών διαδικασιών απόφασης. Στο Κεφάλαιο 3 αναφέρονται ορισμένες εφαρμογές της μαρκοβιανής θεωρίας στην επίλυση προβλημάτων που ανακύπτουν σε δίκτυα επικοινωνιών. Στο Κεφάλαιο 4 παρουσιάζεται η μαρκοβιανή διαδικασία που περιγράφει τον αλγόριθμο δρομολόγησης σε ένα ασύρματο δίκτυο πλέγματος. Τέλος, στο Κεφάλαιο 5 μελετάται η επίδοση του προτεινόμενου αλγορίθμου δρομολόγησης ως προς την ταχύτητα σύγκλισης, την ενεργειακή κατανάλωση, την καθυστέρηση και την κλιμάκωση αυτού με χρήση κατάλληλου μοντέλου προσομοίωσης.