Τεχνικές δρομολόγησης μηνυμάτων μη δομημένων δικτύων

Abstract

The main subject of this thesis is the routing problem in wireless local area networks, and in particular in wireless multihop ad hoc networks (or MANETs) and wireless sensor networks. The issue of routing in multihop ad hoc networks is crucial, as the routing techniques ensure the uncorrupted flow of data traffic towards their destination nodes, and therefore it is an attractive topic in the global research community. In the current thesis we initially propose two routing algorithms for such networks. The first one (AFHSLS) is a proactive routing algorithm based on the HSLS protocol that achieves less routing overhead and mean delay values. The second algorithm is based on the recently proposed DYMO algorithm, but uses multiple paths towards the destination and it is proven to achieve low delay and reduced routing overhead. What is more, the latter algorithm's performance is investigated in a real ad-hoc networks, while a theoretical comparison of routing overhead rates between single-hop and multihop algorithms is also provided. Next, the problem of clustering in wireless UWB sensor networks is investigated and three novel clustering algorithms are proposed towards the maximization of network lifetime and the minimization of the induced interference. Finally, we investigate the clustering problem in wireless sensor networks of selfish sensors using non-cooperative game theory. We define and analyze the clustering game and then we propose a clustering algorithm, named CROSS, that performs at least as good as the popular LEACH algorithm.

Το αντικείμενο της παρούσης διδακτορικής διατριβής συνίσταται στη μελέτη τεχνικών δρομολόγησης σε ασύρματα τοπικά δίκτυα πολλαπλών αλμάτων, και συγκεκριμένα σε ασύρματα μη δομημένα δίκτυα πολλαπλών αλμάτων (wireless multihop ad hoc networks) καθώς επίσης και σε ασύρματα δίκτυα αισθητήρων (wireless sensor networks). Το πρόβλημα της δρομολόγησης των μηνυμάτων σε μεταβαλλόμενης τοπολογίας δίκτυα πολλαπλών αλμάτων κρίνεται υψίστης σημασίας καθώς οι τεχνικές αυτές εξασφαλίζουν τις απαραίτητες διαδρομές που πρέπει να ακολουθήσουν τα πακέτα δεδομένων από τον κόμβο-πηγή στον κόμβο-προορισμό, και για το λόγο αυτό αποτελεί ένα από τα σημεία υψηλού ενδιαφέροντος παγκοσμίως. Στην παρούσα διατριβή προτείνονται αρχικά δύο αλγόριθμοι δρομολόγησης για μη δομημένα δίκτυα. Ο πρώτος (AFHSLS) ανήκει στην κατηγορία των τεχνικών προληπτικής δρομολόγησης, βασίζεται στο πρωτόκολλο HSLS και επιτυγχάνει μείωση του επίφορτου δρομολόγησης και της καθυστέρησης των πακέτων δεδομένων. Ο δεύτερος αλγόριθμος δημιουργεί τις απαιτούμενες διαδρομές μόνον όταν αυτές χρειαστούν (κατ' αίτηση δρομολόγηση) και χρησιμοποιεί πολλαπλές διαδρομές, εξασφαλίζοντας μειωμένη καθυστέρηση και μικρό επίφορτο δρομολόγησης, βασίζεται δε στον αλγόριθμο DYMO. Ο τελευταίος δε αλγόριθμος εξετάζεται σε πραγματικό ασύρματο μη δομημένο δίκτυο, ενώ παρέχεται και μία θεωρητική συγκριτική μελέτη των αλγορίθμων μίας και πολλαπλών διαδρομών αναφορικά με το ρυθμό του επίφορτου δρομολόγησης. Στη συνέχεια, εξετάζεται η περίπτωση των ασύρματων δικτύων αισθητήρων υπερδιευρυμένου φάσματος, στα οποία ο πρωταρχικός στόχος είναι η κατά το δυνατόν μικρότερη κατανάλωση ενέργειας αλλά και η κατά το δυνατόν μικρότερη δυνατή παρεμβολή σε γειτονικά συστήματα. Έτσι, προτείνονται τρεις αλγόριθμοι συσταδοποίησης, που είναι μία βασική τεχνική δρομολόγησης για περιπτώσεις δικτύων με πολύ μεγάλο αριθμό κόμβων. Τέλος, παρατίθεται μία θεωρητική μελέτη της συσταδοποίησης επικεντρωμένη σε ασύρματα δίκτυα αισθητήρων, βασισμένη στη μη-συνεργατική Θεωρία Παιγνίων. Αφού οριστεί και αναλυθεί το Παίγνιο Συσταδοποίησης για εγωιστικά συμπεριφερόμενους αισθητήρες, στη συνέχεια παρατίθεται ένας αλγόριθμος συσταδοποίησης βασισμένος ακριβώς στη μελέτη αυτή, ο αλγόριθμος CROSS. Ο αλγόριθμος αυτός συγκρίνεται με έναν από τους πιο γνωστούς αλγορίθμους συσταδοποίησης σε δίκτυα αισθητήρων, αποδεικνύοντας έτσι ότι έχει την ίδια ή καλύτερη απόδοση από αυτόν.