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

Abstract

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