Διαστρωματικές Τεχνικές Ελέγχου Τοπολογίας Για Αποδοτική Ανάθεση Πόρων Σε Ασύρματα Αυτοργανούμενα Δίκτυα

Abstract

Τα ασύρματα αυτοργανούμενα δίκτυα, ή αλλιώς Ad Hoc δίκτυα, αποτελούν μία από τις πιο δραστήριες ερευνητικές περιοχές δικτύων τα τελευταία χρόνια. Παρά το γεγονός ότι η ανάπτυξη τους ξεκίνησε τη δεκαετία του 1970, σήμερα υπάρχουν πολλά ακόμα ανοικτά ζητήματα, τόσο θεωρητικά όσο και πρακτικά, που απαιτούν λύση ώστε τα Ad Hoc δίκτυα να αποτελέσουν μία ώριμη τεχνολογία και να αξιοποιηθούν σε ευρεία εμπορική κλίμακα.Στο μεγαλύτερο μέρος αυτής της εργασίας περιοριζόμαστε στη μελέτη και κατανόηση της έννοιας του Ελεγχου Τοπολογίας (Topology Control) στα αυτοργανούμενα δίκτυα μέσα στο πλαίσιο της Διαστρωματικής Σχεδίασης Δικτύων (Cross-Layer Design). Αναλυτικότερα, ο Έλεγχος Τοπολογίας έχει προταθεί από πολλές ερευνητικές ομάδες ως ένας αποδοτικός τρόπος ανάθεσης πόρων σε Ad Hoc δίκτυα, καθώς έχει ως στόχο να προσδώσει στην τοπολογία του δικτύου διάφορες επιθυμητές ιδιότητες, με απώτερο σκοπό την αύξηση της χωρητικότητας του δικτύου και τη μείωση των ενεργειακών αναγκών του.Στα πλαίσια της παρούσας εργασίας, προτείνονται δύο διαφορετικοί διαστρωματικοί αλγόριθμοι Ελέγχου Τοπολογίας, ο Nearest Random Neighbors (NRN) και ο Physical Topology Control (PTC) αλγόριθμος, η λειτουργία των οποίων διαφοροποιείται σημαντικά τόσο στις πληροφορίες που απαιτούν για την εκτέλεσή τους και στη θέση τους στη στοίβα πρωτοκόλλων, όσο και στο μαθηματικό τους υπόβαθρο.Από τη μία ο NRN αλγόριθμος είναι ένας υπολογιστικά ελαφρύς, αποκεντρωμένος και ασύγχρονος μηχανισμός Ελέγχου Τοπολογίας που λειτουργεί ανάμεσα στο Επίπεδο Δικτύου και στο Επίπεδο Ζεύξης Δεδομένων της στοίβας πρωτοκόλλων. Παρά το γεγονός ότι δεν εγγυάται τη συνδεσιμότητα στη γενική περίπτωση, σχεδιαστηκε με στόχο την αύξηση των ποσοστών συνδεσιμότητας αυτοργανούμενων δικτύων στα οποία οι κόμβοι δεν είναι ομοιόμορφα κατανεμημένοι.Από την άλλη ο PTC αλγόριθμος αποτελεί ένα παιχνίδι, με την έννοια που δίνεται στη Θεωρία παιγνίων, και αξιοποιεί ένα σύνολο από πληροφορίες που είναι πιθανώς διαθέσιμες σε ένα κόμβο ενός αυτοργανούμενου δικτύου. Αυτές οι πληοοφορίες είναι η ποιότητα των ζεύξεων, η στάθμη της ισχύος εκπομπής και η μερική γνώση της τοπολογίας δικτύου σε απόσταση λίγων βημάτων. Συνεπώς ο PTC είναι ένας διαστρωματικός αλγόριθμος Ελέγχου Τοπολογίας ο οποίος συνδέει τα τρία κατώτερα επίπεδα της στοίβας πρωτοκόλλων. Μέσα από τη μελέτη και ανάλυση αυτού του παιχνιδιού γίνονται εμφανείς ορισμένες μεγάλες προκλήσεις των αυτοργανούμενων δικτύων, όπως η πολυπλοκότητα μηνυμάτων, η σημασία της τοπικής δικτυακής γνώσης και η πολυπλοκότητα του Φυσικού Επιπέδου της στοίβας πρωτοκόλλων στη σχεδίαση των επιθυμητών μηχανισμών και αλγόριθμων. Τέλος, στο τελευταίο κεφάλαιο της εργασίας, επιχειρούνται οι πρώτες προεκτάσεις των προηγούμενων ιδεών, στις οποίες βασίστηκε ο PTC λαγόριθμος, στα γνωστικά δίκτυα (Cognitive Radios).Ad Hoc networks have emerged lately as one of the most vivid research areas in computer and communication networks. Even though their study started in the $1970$s, today several problems of theoretical or nature remain open. These problems require solution, in order to realize commercially efficient and robust Ad Hoc networks that allowoffering real-time services and increased end-to-end performance.In this diploma thesis we focus our analysis on the study of Topology Control in Ad Hoc networks under the notion of Cross-Layer Network Design. Topology Control has been repeatedly proposed, by several research groups, as a highly efficient technique for resource allocationin Ad Hoc networks. Topology Control aspires to create a network topology with several desirable characteristics, so as to increase network capacity and decrease energy consumption.In this work we propose two Cross-Layer Topology Control algorithms, namely Nearest Random Neighbors (NRN) and Physical Topology Control (PTC), whose functionality differs significantly, not only on the information that they require and their position in theprotocol stack of Ad Hoc networks, but also on their mathematical treatment.On the one hand, the NRN algorithm is a light, simple, asynchronous and decentralized Topology Control algorithm that works between the Network Layer and the Media Access Control Layer in the protocol stack. Even though it does not guarantee connectivity of the induced Ad Hoc network in the general case, it is designed to increase the percentagesof connectivity when the nodes of the Ad Hoc Network are not distributed uniformly.On the other hand, the PTC algorithm is a game, formally defined in the Game Theory framework. It uses information obtained from the three lower Layers of the Protocol Stack. More precisely, the PTC algorithm uses the quality of the links, from the Physical Layer, the one-hop neighbors, from the $MAC$ Layer , and the $k-$hop neighborhood information of each node from the Network Layer. Therefore, the PTCalgorithm is a Cross-Layer Topology Control algorithm which requires only local knowledge. Through the study and the analysis of this algorithm, it becomes evident that Ad Hoc networks face some very important challenges, such as message complexity, local versus global information and the complexity of the Physical Layer in the design of desirable mechanisms and algorithms.In the final section of this thesis, we present directions for future work. Based on the ideas previously mentioned, we mainly focus on and offer guidelines for the extension of the proposed approaches in Cognitive Radios.