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

Το βασικό χαρακτηριστικό των ασύρματων δικτύων αυθαίρετης τοπολογίας (wireless ad hoc networks) είναι πως δεν απαιτούν την ύπαρξη σταθερής υποδομής (σε αντίθεση π.χ. με τα κυψελωτά δίκτυα). Ένα ιδιαίτερα σημαντικό παράδειγμα τέτοιων δικτύων αποτελούν τα λεγόμενα δίκτυα αισθητήρων (sensor networks),...

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής
Κύριος συγγραφέας: Κρομμύδας, Ιωάννης
Άλλοι συγγραφείς: Ζαρολιάγκης, Χρήστος
Μορφή: Βιβλίο
Γλώσσα:Greek
Έκδοση: 2007
Θέματα:
Διαθέσιμο Online:http://nemertes.lis.upatras.gr/jspui/handle/10889/472
id nemertes-10889-472
record_format dspace
institution UPatras
collection Nemertes
language Greek
topic Δρομολόγηση
Αδόμητα Δίκτυα
Επικαλύπτον Υπογράφημα
Routing
Ad Hoc Networks
Spanner
004.65
spellingShingle Δρομολόγηση
Αδόμητα Δίκτυα
Επικαλύπτον Υπογράφημα
Routing
Ad Hoc Networks
Spanner
004.65
Κρομμύδας, Ιωάννης
Μέθοδοι δρομολόγησης σε ασύρματα δίκτυα αυθαίρετης τοπολογίας
description Το βασικό χαρακτηριστικό των ασύρματων δικτύων αυθαίρετης τοπολογίας (wireless ad hoc networks) είναι πως δεν απαιτούν την ύπαρξη σταθερής υποδομής (σε αντίθεση π.χ. με τα κυψελωτά δίκτυα). Ένα ιδιαίτερα σημαντικό παράδειγμα τέτοιων δικτύων αποτελούν τα λεγόμενα δίκτυα αισθητήρων (sensor networks), τα οποία μπορούν να χρησιμοποιηθούν σε τομείς όπως η παρακολούθηση και καταγραφή φυσικών φαινομένων, ή η προσωρινή δημιουργία δικτύου επικοινωνίας σε περιοχές που έχουν πληγεί από κάποια καταστροφή, κλπ., και επομένως αποτελούν μια ερευνητική περιοχή μεγάλου ενδιαφέροντος. Στα δίκτυα αυτά, όταν ένας κόμβος πρέπει να στείλει ένα πακέτο σε κόμβο που βρίσκεται εκτός της ακτίνας μετάδοσης του, τότε η μετάδοση γίνεται μέσω κόμβων που βρίσκονται πάνω σε μια διαδρομή μεταξύ αυτών των δύο κόμβων. Επειδή, όμως, οι κόμβοι αυτοί συνήθως έχουν περιορισμένη ενέργεια, ο τρόπος δρομολόγησης είναι καθοριστικός για τη λειτουργία του δικτύου. Τα πρωτόκολλα δρομολόγησης βασίζονται σε διάφορες μεθόδους όπως: κάθε κόμβος να επικοινωνεί μόνο με ορισμένους από τους γείτονες του, ή κάθε κόμβος να επιλέγει κόμβους στους οποίους θα μεταδώσει πακέτα με βάση τη γεωμετρική θέση τους. Μια άλλη μέθοδος δρομολόγησης είναι η κατασκευή ενός εικονικού δικτύου υποδομής, οι κόμβοι του οποίου είναι κόμβοι του ασύρματου δικτύου και οι ακμές του οποίου χρησιμοποιούνται για τη μεταφορά των πακέτων. Η κατασκευή του δικτύου υποδομής πρέπει να πραγματοποιηθεί με κατανεμημένο τρόπο και το μέγεθος και η δομή του πρέπει να είναι τέτοια ώστε η δρομολόγηση να απαιτεί όσο το δυνατόν λιγότερη κατανάλωση ενέργειας από τους κόμβους. Στα πλαίσια της διπλωματικής αυτής εργασίας: 1) Αναπτύχθηκαν δύο νέες μέθοδοι δρομολόγησης σε ασύρματα δίκτυα αυθαίρετης τοπολογίας μέσω κατασκευής εικονικών δικτύων υποδομής. Οι μέθοδοι αυτοί βασίζονται σε αντίστοιχους αλγόριθμους κατασκευής επικαλυπτόντων υπογραφημάτων και έχουν την ιδιότητα ότι τα εικονικά δίκτυα που παράγονται έχουν σχετικά μικρό αριθμό ακμών, ενώ παράλληλα η απόσταση μεταξύ δύο κόμβων στο εικονικό δίκτυο είναι το πολύ t φορές μεγαλύτερη από την ελάχιστη απόσταση τους στο αρχικό δίκτυο (όπου t είναι παράμετρος που εξαρτάται από τον αλγόριθμο). 2) Υλοποιήθηκαν οι δύο αυτές νέες μέθοδοι δρομολόγησης σε κατάλληλο περιβάλλον εξομοίωσης και έγινε εκτενής πειραματική αξιολόγηση τους.
author2 Ζαρολιάγκης, Χρήστος
author_facet Ζαρολιάγκης, Χρήστος
Κρομμύδας, Ιωάννης
format Book
author Κρομμύδας, Ιωάννης
author_sort Κρομμύδας, Ιωάννης
title Μέθοδοι δρομολόγησης σε ασύρματα δίκτυα αυθαίρετης τοπολογίας
title_short Μέθοδοι δρομολόγησης σε ασύρματα δίκτυα αυθαίρετης τοπολογίας
title_full Μέθοδοι δρομολόγησης σε ασύρματα δίκτυα αυθαίρετης τοπολογίας
title_fullStr Μέθοδοι δρομολόγησης σε ασύρματα δίκτυα αυθαίρετης τοπολογίας
title_full_unstemmed Μέθοδοι δρομολόγησης σε ασύρματα δίκτυα αυθαίρετης τοπολογίας
title_sort μέθοδοι δρομολόγησης σε ασύρματα δίκτυα αυθαίρετης τοπολογίας
publishDate 2007
url http://nemertes.lis.upatras.gr/jspui/handle/10889/472
work_keys_str_mv AT krommydasiōannēs methodoidromologēsēsseasyrmatadiktyaauthairetēstopologias
_version_ 1771297136855482368
spelling nemertes-10889-4722022-09-05T04:59:14Z Μέθοδοι δρομολόγησης σε ασύρματα δίκτυα αυθαίρετης τοπολογίας Κρομμύδας, Ιωάννης Ζαρολιάγκης, Χρήστος Ζαρολιάγκης, Χρήστος Μπερμπερίδης, Κωνσταντίνος Νικολετσέας, Σωτήριος Krommidas, Ioannis Δρομολόγηση Αδόμητα Δίκτυα Επικαλύπτον Υπογράφημα Routing Ad Hoc Networks Spanner 004.65 Το βασικό χαρακτηριστικό των ασύρματων δικτύων αυθαίρετης τοπολογίας (wireless ad hoc networks) είναι πως δεν απαιτούν την ύπαρξη σταθερής υποδομής (σε αντίθεση π.χ. με τα κυψελωτά δίκτυα). Ένα ιδιαίτερα σημαντικό παράδειγμα τέτοιων δικτύων αποτελούν τα λεγόμενα δίκτυα αισθητήρων (sensor networks), τα οποία μπορούν να χρησιμοποιηθούν σε τομείς όπως η παρακολούθηση και καταγραφή φυσικών φαινομένων, ή η προσωρινή δημιουργία δικτύου επικοινωνίας σε περιοχές που έχουν πληγεί από κάποια καταστροφή, κλπ., και επομένως αποτελούν μια ερευνητική περιοχή μεγάλου ενδιαφέροντος. Στα δίκτυα αυτά, όταν ένας κόμβος πρέπει να στείλει ένα πακέτο σε κόμβο που βρίσκεται εκτός της ακτίνας μετάδοσης του, τότε η μετάδοση γίνεται μέσω κόμβων που βρίσκονται πάνω σε μια διαδρομή μεταξύ αυτών των δύο κόμβων. Επειδή, όμως, οι κόμβοι αυτοί συνήθως έχουν περιορισμένη ενέργεια, ο τρόπος δρομολόγησης είναι καθοριστικός για τη λειτουργία του δικτύου. Τα πρωτόκολλα δρομολόγησης βασίζονται σε διάφορες μεθόδους όπως: κάθε κόμβος να επικοινωνεί μόνο με ορισμένους από τους γείτονες του, ή κάθε κόμβος να επιλέγει κόμβους στους οποίους θα μεταδώσει πακέτα με βάση τη γεωμετρική θέση τους. Μια άλλη μέθοδος δρομολόγησης είναι η κατασκευή ενός εικονικού δικτύου υποδομής, οι κόμβοι του οποίου είναι κόμβοι του ασύρματου δικτύου και οι ακμές του οποίου χρησιμοποιούνται για τη μεταφορά των πακέτων. Η κατασκευή του δικτύου υποδομής πρέπει να πραγματοποιηθεί με κατανεμημένο τρόπο και το μέγεθος και η δομή του πρέπει να είναι τέτοια ώστε η δρομολόγηση να απαιτεί όσο το δυνατόν λιγότερη κατανάλωση ενέργειας από τους κόμβους. Στα πλαίσια της διπλωματικής αυτής εργασίας: 1) Αναπτύχθηκαν δύο νέες μέθοδοι δρομολόγησης σε ασύρματα δίκτυα αυθαίρετης τοπολογίας μέσω κατασκευής εικονικών δικτύων υποδομής. Οι μέθοδοι αυτοί βασίζονται σε αντίστοιχους αλγόριθμους κατασκευής επικαλυπτόντων υπογραφημάτων και έχουν την ιδιότητα ότι τα εικονικά δίκτυα που παράγονται έχουν σχετικά μικρό αριθμό ακμών, ενώ παράλληλα η απόσταση μεταξύ δύο κόμβων στο εικονικό δίκτυο είναι το πολύ t φορές μεγαλύτερη από την ελάχιστη απόσταση τους στο αρχικό δίκτυο (όπου t είναι παράμετρος που εξαρτάται από τον αλγόριθμο). 2) Υλοποιήθηκαν οι δύο αυτές νέες μέθοδοι δρομολόγησης σε κατάλληλο περιβάλλον εξομοίωσης και έγινε εκτενής πειραματική αξιολόγηση τους. The characteristic feature of wireless ad hoc networks is that there is no fixed infastructure (in constrast with cellular networks). One considerabe example of such networks is sensor networks, which can be used to monitor a natural phenomenon, or to construct a temporary communication network in areas where a disaster has occurred, etc, therefore wireless ad hoc networks is a research area of great interest. In wireless ad hoc networks when a node needs to send a message to a node which relies outside of its transmission range, then the transmission takes place through the nodes which rely on a path which connects these two nodes. The wireless nodes, however, have limited energy, therefore routing method is crusial for the operation of the network. Routing protocols are based on several methods, such as: each node is allowed to communicate with only a selected subset of its neighbors, or each node chooses to transmits a message to one of its neighbors based on its geometrical position. Another routing method is to construct a virtual backbone network. The virtual network has the same nodes as the ad hoc network, but only its links are used for the routing of messages. The construction of the virtual network must be executed in a distributed way and its size and structure must be suitable to allow the nodes to consume as less energy as possible in order to support the routing protocol. In this work 1) we have developed two new routing methods for wireless ad hoc networks by constructing virtual networks. These two methods are based on corresponding algorithms for maintaining spanners. The virtual networks constructed have relatively small number of links, while having the ability that for every pair of nodes their distance in the virtual network is at most t times their distance in the ad hoc network (parameter t depends on the algorithm). 2) we have implemented these two algorithms in a simulation environment, and we have conducted an extensive study on them. 2007-07-31T06:55:16Z 2007-07-31T06:55:16Z 2007-07-05 2007-07-31T06:55:16Z Book http://nemertes.lis.upatras.gr/jspui/handle/10889/472 gr Η ΒΥΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. application/pdf