Διαστρωματική σχεδίαση και βελτιστοποίηση ασύρματων πολυβηματικών δικτύων

Abstract

This dissertation focuses on the improvement of the communication provided by wireless multihop networks following a holistic approach with respect to the protocol stack. Specifically, the focus of this dissertation lies in the development of two cross-layer frameworks that contribute either combinatorially, or each one independently in the improvement of Quality of Service (QoS) metrics. The first framework is denoted as Inverse Topology Control Framework (iTC Framework), as being based on topology control, and functions on Physical and Network layers while leveraging information and features from the social layer. The iTC Framework enhances the topology of the wireless multihop network with features from social graphs/Social Network Analysis (SNA), following the paradigm of the efficient and fast communication over social networks. We propose the probabilistic operation of the iTC Framework, we develop an optimization methodology of its parameters and we describe the prospects of its distributed implementation. The analytical study of the iTC Framework is based on Continuum Theory. Furthermore, we present the implementation of the iTC Framework in special cases and applications such as trust and traffic management which show its effectiveness in improving several QoS metrics e.g., delay, throughput, trust and cost of packet transfer.The second framework is denoted as TNUM/Backpressure Framework as it is founded on the Theory of Network Utility Maximization (TNUM) and functions on MAC, Network and Transport layers. The optimal solution of a NUM problem is computed based on the Backpressure (BP) cross-layer algorithm for scheduling and routing along with an appropriately defined congestion controller for the determination of the optimal arrival rates' values at the sources. The BP algorithm is optimal with respect to the capacity region (throughput optimal, i.e., it leads to stable network queues for all arrival rates lying inside the capacity region) but leads to high delay values and does not provide the possibility of considering other Quality of Service metrics. In this work, the TNUM/Backpressure Framework introduces appropriate weights in the network graph and the greedy embedding of the network graph in hyperbolic space. The BP algorithm is adapted for taking into consideration the weights' values, denoted as weighted BP, and via introducing suitable routing constraints for static and dynamic networks. More specifically, with respect to delay reduction, we apply greedy routing constraints in hyperbolic space. We examine the stability of the proposed weighted BP algorithm and the convergence and stability of the proposed algorithm for solving the NUM problem, which is based on the weighted BP, using primal-dual decomposition and Lyapunov drift techniques. The simulation results evaluate the possibility of delay reductions and other QoS metrics' improvements (e.g., cost, trust, etc.). Furthermore, we examine via simulations the effect of weights on QoS, on the convergence and stability of the NUM problem's algorithmic solution, while also studying sophisticated choices for the weight values for each QoS metric. In addition, the greedy routing in hyperbolic space is improved by applying coalitional game theory aiming to further boost the performance of the proposed algorithms by cooperatively deciding for the greedy embedding in hyperbolic space. In the sequel, the NUM problem is formulated and solved so that the trade-off between the sources' arrival rates (long-term throughput) and delay becomes users' controlled. Then, social layer's information is used for the utility function design targeting at a more efficient resources' distribution among users according to their needs.Finally, the two proposed frameworks are applied together so as to study, via examples and simulations, the possible combinatorial improvement in QoS. At the end of the dissertation we summarize this research's basic conclusions and we pinpoint and discuss the current research along with possible future steps.

Η παρούσα διδακτορική διατριβή στοχεύει στη βελτίωση της παρεχόμενης επικοινωνίας από τα ασύρματα πολυβηματικά δίκτυα ακολουθώντας μία ολιστική προσέγγιση όσον αφορά στη στοίβα πρωτοκόλλων. Συγκεκριμένα, επίκεντρο της διατριβής αποτελεί η ανάπτυξη δύο διαστρωματικών πλαισίων, τα οποία συνεισφέρουν συνδυαστικά αλλά και καθένα αυτοτελώς στη βελτίωση των μετρικών Ποιότητας Υπηρεσίας. Το πρώτο πλαίσιο ονομάζεται Πλαίσιο Αντίστροφου Ελέγχου Τοπολογίας (Πλαίσιο ΑΕΤ) καθώς στηρίζεται στον Έλεγχο Τοπολογίας και δρα στο φυσικό επίπεδο (Physical Layer) και στο επίπεδο δικτύου (Network Layer) χρησιμοποιώντας πληροφορία και στοιχεία του κοινωνικού επιπέδου. Το Πλαίσιο ΑΕΤ εμπλουτίζει την τοπολογία του ασύρματου πολυβηματικού δικτύου με στοιχεία των κοινωνικών γράφων, ακολουθώντας το παράδειγμα της αποτελεσματικής και γρήγορης επικοινωνίας διαμέσου των κοινωνικών δικτύων. Προτείνεται η πιθανοτική λειτουργία του Πλαισίου ΑΕΤ, αναπτύσσεται η μεθοδολογία βελτιστοποίησης των παραμέτρων του και περιγράφεται η δυνατότητα της κατανεμημένης εφαρμογής του. Η αναλυτική μελέτη του Πλαισίου ΑΕΤ στηρίζεται στη θεωρία συνέχειας (Continuum Theory). Επιπρόσθετα, μία ειδική περίπτωση και δύο εφαρμογές του Πλαισίου ΑΕΤ επιβεβαιώνουν τη βελτίωση της τοπολογίας και της επικοινωνίας, όπως η βελτίωση αυτή ποσοτικοποιείται μέσω χρήσης μετρικών της Ανάλυσης Κοινωνικών Δικτύων και συγκεκριμένων μετρικών Ποιότητας Υπηρεσίας.Το δεύτερο πλαίσιο ονομάζεται Πλαίσιο ΘΜΧΔ/Backpressure καθώς θεμελιώνεται στη Θεωρία Μεγιστοποίησης Χρησιμότητας Δικτύου (ΘΜΧΔ) και δρα στα επίπεδα πρόσβασης στο μέσο (MAC), δικτύου (Network) και μεταφοράς (Transport), χρησιμοποιώντας πληροφορία από το κοινωνικό επίπεδο. H βέλτιστη επίλυση ενός προβλήματος ΜΧΔ βασίζεται στο διαστρωματικό αλγόριθμο δρομολόγησης πακέτων και χρονοπρογραμματισμού των μεταδόσεων των πακέτων Backpressure σε συνδυασμό με κατάλληλο αλγόριθμο ελέγχου συμφόρησης για τον προσδιορισμό των βέλτιστων ρυθμών άφιξης πακέτων στις πηγές των ροών. Ο αλγόριθμος Backpressure είναι βέλτιστος ως προς το θεωρητικό ρυθμό επιτυχημένης αποστολής πακέτων (δηλαδή σταθεροποιεί τις ουρές του δικτύου για όλους τους ρυθμούς άφιξης πακέτων στις πηγές του δικτύου που ανήκουν στην περιοχή χωρητικότητας του) αλλά οδηγεί σε μεγάλες καθυστερήσεις στην αποστολή τους και δεν λαμβάνει άλλες μετρικές Ποιότητας Υπηρεσίας υπόψη. Στην παρούσα διατριβή, το Πλαίσιο ΘΜΧΔ/Backpressure χρησιμοποιεί την εισαγωγή κατάλληλων βαρών στο γράφο του δικτύου και την άπληστη ενσωμάτωση του γράφου του δικτύου στο χώρο της υπερβολικής γεωμετρίας. Ο αλγόριθμος Backpressure προσαρμόζεται ώστε να λαμβάνει υπόψη τα βάρη καθώς και με την εισαγωγή κατάλληλων περιορισμών στη δρομολόγηση των πακέτων για στατικά και δυναμικά δίκτυα. Ειδικότερα για τη μείωση της καθυστέρησης αποστολής πακέτων, έμφαση προσάπτεται στους περιορισμούς άπληστης δρομολόγησης στην υπερβολική γεωμετρία. Εξετάζεται η σταθερότητα του προτεινομένου αλγορίθμου Backpressure ως προς τις ουρές του δικτύου καθώς και η σύγκλιση του ΜΧΔ προβλήματος υπό τον προτεινόμενο αλγόριθμο Backpressure με βάρη, με χρήση δυϊκής αποσύμπλεξης και τεχνικών Lyapunov drift. Τα αποτελέσματα προσομοιώσεων επιβεβαιώνουν τη δυνατότητα μείωσης της καθυστέρησης αποστολής πακέτου και τη βελτίωση επιπλέον μετρικών Ποιότητας Υπηρεσίας (π.χ., κόστος, εμπιστοσύνη, κλπ.). Επιπλέον, εξετάζεται μέσω προσομοιώσεων η επίδραση των βαρών στην Ποιότητα Υπηρεσίας και στη σύγκλιση του αλγορίθμου επίλυσης του προβλήματος ΜΧΔ και μελετάται η επιλογή κατάλληλων βαρών για κάθε μετρική Ποιότητας Υπηρεσίας. Ακόμη, η άπληστη ενσωμάτωση στην υπερβολική γεωμετρία βελτιώνεται περαιτέρω με εφαρμογή της συνεργατικής θεωρίας παιγνίων. Στη συνέχεια, πληροφορία από το κοινωνικό επίπεδο χρησιμοποιείται για το σχεδιασμό των συναρτήσεων χρησιμότητας του προβλήματος ΜΧΔ για την αποτελεσματικότερη κατανομή των πόρων μεταξύ των χρηστών ανάλογα με τις ανάγκες τους. Ακολούθως, το πρόβλημα ΜΧΔ διατυπώνεται και επιλύεται εις τρόπον ώστε ο συμβιβασμός (trade-off) μεταξύ των ρυθμών άφιξης πακέτων στις πηγές των ροών και της καθυστέρησης αποστολής πακέτου να ελέγχεται από τους χρήστες του δικτύου.Τέλος, τα δύο προτεινόμενα πλαίσια συνδυάζονται ώστε να μελετηθεί μέσω παραδειγμάτων και προσομοιώσεων η ολική δυνατή βελτίωση στην Ποιότητα Υπηρεσίας. Εν κατακλείδι, συνοψίζονται τα συμπεράσματα της παρούσας διατριβής και περιγράφεται η τρέχουσα έρευνα και τα επόμενα ερευνητικά βήματα.