Μέθοδοι δρομολόγησης σε ασύρματα δίκτυα αυθαίρετης τοπολογίας

• Κύριος συγγραφέας: Κρομμύδας, Ιωάννης
• Άλλοι συγγραφείς: Ζαρολιάγκης, Χρήστος
• Μορφή: Βιβλίο
• Γλώσσα: Greek
• Έκδοση: 2007
• Θέματα: Δρομολόγηση; Αδόμητα Δίκτυα; Επικαλύπτον Υπογράφημα; Routing; Ad Hoc Networks; Spanner; 004.65

Το βασικό χαρακτηριστικό των ασύρματων δικτύων αυθαίρετης τοπολογίας (wireless ad hoc networks) είναι πως δεν απαιτούν την ύπαρξη σταθερής υποδομής (σε αντίθεση π.χ. με τα κυψελωτά δίκτυα). Ένα ιδιαίτερα σημαντικό παράδειγμα τέτοιων δικτύων αποτελούν τα λεγόμενα δίκτυα αισθητήρων (sensor networks), τα οποία μπορούν να χρησιμοποιηθούν σε τομείς όπως η παρακολούθηση και καταγραφή φυσικών φαινομένων, ή η προσωρινή δημιουργία δικτύου επικοινωνίας σε περιοχές που έχουν πληγεί από κάποια καταστροφή, κλπ., και επομένως αποτελούν μια ερευνητική περιοχή μεγάλου ενδιαφέροντος. Στα δίκτυα αυτά, όταν ένας κόμβος πρέπει να στείλει ένα πακέτο σε κόμβο που βρίσκεται εκτός της ακτίνας μετάδοσης του, τότε η μετάδοση γίνεται μέσω κόμβων που βρίσκονται πάνω σε μια διαδρομή μεταξύ αυτών των δύο κόμβων. Επειδή, όμως, οι κόμβοι αυτοί συνήθως έχουν περιορισμένη ενέργεια, ο τρόπος δρομολόγησης είναι καθοριστικός για τη λειτουργία του δικτύου. Τα πρωτόκολλα δρομολόγησης βασίζονται σε διάφορες μεθόδους όπως: κάθε κόμβος να επικοινωνεί μόνο με ορισμένους από τους γείτονες του, ή κάθε κόμβος να επιλέγει κόμβους στους οποίους θα μεταδώσει πακέτα με βάση τη γεωμετρική θέση τους. Μια άλλη μέθοδος δρομολόγησης είναι η κατασκευή ενός εικονικού δικτύου υποδομής, οι κόμβοι του οποίου είναι κόμβοι του ασύρματου δικτύου και οι ακμές του οποίου χρησιμοποιούνται για τη μεταφορά των πακέτων. Η κατασκευή του δικτύου υποδομής πρέπει να πραγματοποιηθεί με κατανεμημένο τρόπο και το μέγεθος και η δομή του πρέπει να είναι τέτοια ώστε η δρομολόγηση να απαιτεί όσο το δυνατόν λιγότερη κατανάλωση ενέργειας από τους κόμβους. Στα πλαίσια της διπλωματικής αυτής εργασίας: 1) Αναπτύχθηκαν δύο νέες μέθοδοι δρομολόγησης σε ασύρματα δίκτυα αυθαίρετης τοπολογίας μέσω κατασκευής εικονικών δικτύων υποδομής. Οι μέθοδοι αυτοί βασίζονται σε αντίστοιχους αλγόριθμους κατασκευής επικαλυπτόντων υπογραφημάτων και έχουν την ιδιότητα ότι τα εικονικά δίκτυα που παράγονται έχουν σχετικά μικρό αριθμό ακμών, ενώ παράλληλα η απόσταση μεταξύ δύο κόμβων στο εικονικό δίκτυο είναι το πολύ t φορές μεγαλύτερη από την ελάχιστη απόσταση τους στο αρχικό δίκτυο (όπου t είναι παράμετρος που εξαρτάται από τον αλγόριθμο). 2) Υλοποιήθηκαν οι δύο αυτές νέες μέθοδοι δρομολόγησης σε κατάλληλο περιβάλλον εξομοίωσης και έγινε εκτενής πειραματική αξιολόγηση τους.