SINGLE ARTICLE VIEW

Παρουσίαση διατριβής - Ματσκάνη Ευ.

Θέμα διδακτορικής διατριβής: "Από κοινού δρομολόγηση και κατανομή πόρων σε ασύρματα δίκτυα με τεχνικές κυρτής προσέγγισης"

Παρουσίαση: Παρασκευή 15 Ιουνίου 2012, 10:30 π.μ. Αμφιθέατρο Κτηρίου Επιστημών, Πολυτεχνειούπολη.

Εξεταστική επιτροπή:
Καθηγητής Νικόλαος Σιδηρόπουλος, Τμήμα Ηλεκτρονικών Μηχανικών & Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης.
Καθηγητής Αθανάσιος Λιάβας, Τμήμα Ηλεκτρονικών Μηχανικών & Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης.
Καθηγητής Luo Zhi-Quan, Πανεπιστήμιο της Μινεσότα, Η.Π.Α.
Καθηγητής Λέανδρος Τασσιούλας, Πανεπιστήμιο Θεσσαλίας.
Καθηγητής Μιχαήλ Πατεράκης, Τμήμα Ηλεκτρονικών Μηχανικών & Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης.
Επίκουρος Καθηγητής Άγγελος Μπλέτσας, Τμήμα Ηλεκτρονικών Μηχανικών & Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης.
Επίκουρος ΚαθηγητήςΠολυχρόνης Κουτσάκης, Τμήμα Ηλεκτρονικών Μηχανικών & Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης.

Συνεργάτης καθηγητής: Λέανδρος Τασιούλας

Περίληψη
Βασικό αντικείμενο του μεγαλύτερου μέρους της διδακτορικής αυτής διατριβής αποτελεί το πρόβλημα της από κοινού δρομολόγησης και ελέγχου ισχύος με τακτική αντιπίεσης, με στόχο τη μέγιστη δυνατή χωρητικότητα μεταφοράς σε ασύρματα multi-hop δίκτυα. Η βέλτιστη από πλευράς χωρητικότητας μεταφοράς λειτοργία ασύρματων multi-hop δικτύων συνεπάγεται ένα βασικό πρόβλημα βελτιστοποίησης στο φυσικό επίπεδο: τη μεγιστοποίηση ενός ζυγισμένου αθροίσματος των χωρητικοτήτων των επιμέρους συνδέσμων, με συντελεστές ζύγισης που καθορίζονται από τις διαφορές των ουρών αναμονής στα άκρα κάθε συνδέσμου (differential queue backlogs). Αυτό προκύπτει στο πρόβλημα της από κοινού δρομολόγησης και ελέγχου ισχύος, που αποτελεί κεντρικό πρόβλημα στη διαστρωματική σχεδίαση ασύρματων δικτύων. Στο πρώτο κεφάλαιο της διατριβής δείχνουμε ότι το βασικό αυτό πρόβλημα όχι απλώς ανήκει στην κατηγορία των μη κυρτών προβλημάτων, αλλά είναι επίσης απαγορευτικής πολυπλοκότητας. Αυτό ωστόσο το αρνητικό αποτέλεσμα έχει και θετική πλευρά: αντλώντας από τις σχετικές εξελίξεις στην περιοχή των ψηφιακών συνδρομητικών γραμμών, προτείνουμε ευεργετικούς τρόπους προσέγγισης του προβλήματος. Εκμεταλλευόμενοι την περιοδικότητα της κατανομής ισχύος σε ευσταθή συστήματα, που οφείλεται στη φύση της λύσης με χαρακτηριστικό την διαδοχική έλξη και ώθηση των δεδομένων, που ρέουν στο δίκτυο, από τους κόμβους του, αναπτύσσουμε δύο συνήθεις αλγορίθμους, που έχουν εξαιρετική απόδοση από πλευράς χωρητικότητας μεταφοράς, σε λογική, στη χειρότερη περίπτωση, πολυωνυμική πολυπλοκότητα. Εκτεταμένα πειράματα προσομοιώσεων αναδεικνύουν τις αξίες των προτεινόμενων αλγορίθμων.
Το πρόβλημα της από κοινού δρομολόγησης και ελέγχου ισχύος (BPPC) επιδέχεται στρατηγικές διαδοχικών κυρτών προσεγγίσεων που αποφέρουν πολλαπλές βελτιώσεις στην από άκρη σε άκρη χωρητικότητα μεταφοράς ασύρματων δικτύων, σε σχέση με τις προγενέστερες επικρατέστερες τεχνικές στο σχεδιασμό ασύρματων δικτύων, σύμφωνα με τα ευρήματά μας στο πρώτο κεφάλαιο. Ένα μειονέκτημα ωστόσο είναι ότι οι υπάρχουσες υλοποιήσεις είναι κεντρικές, ενώ πρακτικοί λόγοι επιβάλλουν την κατανεμημένη υλοποίηση του ελέγχου ισχύος στο δίκτυο. Η δουλειά που παρουσιάζεται στο δεύτερο κεφάλαιο συμπληρώνει αυτό το κενό αναπτύσσοντας κατανεμημένες υλοποιήσεις των προσεγγίσεων του BPPC προβλήματος. Δύο διαφορετικές τεχνικές προσέγγισης του απαγορευτικής πολυπλοκότητας BPPC προβλήματος αξιοποιούνται, ενώ απαιτήσεις σηματοδοσίας και θέματα που αφορούν στη σύγκλιση των κατανεμημένων αλγορίθμων επίσης διευθύνονται, ώστε να καταλήξουμε σε τελείως κατανεμημένα πρωτόκολλα, τα οποία επιτρέπουν την κοντινή προσέγγιση του BPPC προβλήματος σε όλες τις περιοχές επιπέδου παρεμβολών. Ο πρώτος κατανεμημένος προτεινόμενος αλγόριθμος βασίζεται στην τεχνική των διαδοχικών κυρτών προσεγγίσεων. Σε αυτόν τον αλγόριθμο η μέθοδος Alternating Direction Method of Multipliers χρησιμοποιείται για την κατανεμημένη υλοποίηση του κορμού του αλγορίθμου, που είναι η κυρτή από κάτω προσέγγιση του BPPC, σε οποιοδήποτε σημείο λειτουργίας. Πειράματα προσομοιώσεων επιβεβαιώνουν ότι ο κατανεμημένος αυτός αλγόριθμος έχει την ίδια απόδοση με τον αντίστοιχό του κεντρικό αλγόριθμο.
Η μέθοδος ελαχιστοποίησης του επαναληπτικά ζυγισμένου μέσου τετραγωνικού σφάλματος χρησιμοποιείται κατά τη δεύτερη προσέγγιση του BPPC προβλήματος, η οποία αρχικά αναπτύχθηκε για την προσέγγιση του προβλήματος της μεγιστοποίησης του ζυγισμένου αθροίσματος χωρητικοτήτων στο πολλαπλών εισόδων-εξόδων κανάλι παρεμβολών. Αναπτύσσουμε έτσι ένα δεύτερο αλγόριθμο κατανεμημένης υλοποίησης, ο οποίος παρέχει μία απευθείας προσεγγιστική λύση του BPPC προβλήματος. Επιπλέον, εκμεταλλευόμενοι την περιοδικότητα της λύσης που προκύπτει σε ευσταθή συστήματα, λόγω της εξέλιξης του δικτύου που χαρακτηρίζεται από τη διαδοχική έλξη και ώθηση των δεδομένων από τους κόμβους του, και μετά από επεξεργασία για την επίτευξη της κατανεμημένης ευνοϊκής αρχικοποίησης των αλγορίθμων, αναπτύσσουμε τους αντίστοιχους προσαρμοστικούς αλγορίθμους των κατανεμημένων υλοποιήσεών μας, που χαίρονται χαμηλής πολυπλοκότητας, χωρίς απώλειες από πλευράς απόδοσης. Εκτεταμένα πειράματα προσομοιώσεων αποκαλύπτουν τις δυναμικές των προτεινόμενων αλγορίθμων, και επιτρέπουν τη σύγκριση μεταξύ των δύο προσεγγίσεων στο BPPC πρόβλημα.     
Τέλος, στο τρίτο κεφάλαιο διαπραγματευόμαστε το πρόβλημα της από κοινού μορφοποίησης λοβών και ελέγχου πρόσβασης σε πολλαπλές μεταδόσεις κοινού καναλιού (co-channel wireless multicasting). Τεχνικές wireless multicasting στο φυσικό επίπεδο αποκτούν όλο και μεγαλύτερη σημασία για την αποτελεσματική διανομή περιεχομένου και την υποστήριξη υπηρεσιών σε κυψελωτά δίκτυα (π.χ. UMTS-LTE) και ασύρματα δίκτυα εξωτερικού χώρου (π.χ. 802.16). Μέθοδοι μορφοποίησης πολλαπλών λοβών εκπομπής έχουν πρόσφατα προταθεί ως μέσο για την καλύτερη αξιοποίηση του διαθέσιμου φάσματος και για την υποστήριξη απαιτήσεων ποιότητας υπηρεσίας (QoS), υπό το πρίσμα σχετικών εξελίξεων στη διαδικασία τυποποίησης του UMTS-LTE. Ένα βασικό ζήτημα που τίθεται είναι αν είναι δυνατό να ικανοποιηθούν ταυτόχρονα οι απαιτήσεις όλων των χρηστών, λόγω περιορισμών ισχύος ή αμοιβαίας παρεμβολής. Για το λόγο αυτό, μελετήσαμε το πρόβλημα της από κοινού μορφοποίησης λοβών και ελέγχου πρόσβασης με στόχο τη μεγιστοποίηση του αριθμού των συνδρομητών που εξυπηρετούνται και την ελαχιστοποίηση της ισχύος εκπομπής που απαιτείται για την εξυπηρέτησή τους. Το πρόβλημα είναι απαγορευτικής πολυπλοκότητας ακόμη και για μία μεμονωμένη ομάδα συνδρομητών και χωρίς έλεγχο πρόσβασης, αλλά αντλώντας από προγενέστερη έρευνά μας για το SDMA πολλαπλών χρηστών αναπτύσσουμε έναν αποτελεσματικό προσεγγιστικό αλγόριθμο που αποφέρει πολύ καλές λύσεις με ανεκτή μέγιστη πολυπλοκότητα. Για την ειδική περίπτωση μετάδοσης σε μία μεμονωμένη ομάδα συνδρομητών, ο Lozano πρότεινε έναν ιδιαίτερα απλό προσαρμοστικό αλγόριθμο συμπεριλαμβανομένου στην τρέχουσα έκδοση του προτύπου UMTS-LTE. Εντοπίζουμε πλεονεκτήματα και μειονεκτήματα του αλγορίθμου του Lozano και προτείνουμε δύο απλές, αλλά ιδιαίτερα αποτελεσματικές βελτιώσεις του. Όλοι οι αλγόριθμοι δοκιμάστηκαν με δεδομένα που προέκυψαν από μετρήσεις πραγματικών καναλιών και τα αποτελέσματα έδειξαν ότι η βελτιωμένη έκδοση του αλγορίθμου του Lozano που προτείνουμε είναι πολύ καλύτερη από την προγενέστερη και επιπλέον, προσφέρεται για πρακτική εφαρμογή.

Παρουσίαση Διατριβής

Μπορείτε να παρακολουθήσετε την παρουσίαση της διατριβής από το παρακάτω βίντεο.

 

<iframe width="420" height="315" src="https://www.youtube.com/embed/Wmv0v1cs81U" frameborder="0" allowfullscreen=""></iframe>

 

Αρχεία

Κείμενο  διδακτορικής διατριβής (Ιδρυματικό Αποθετήριο Πολυτεχνείου Κρήτης)

Παρουσίαση διδακτορικής διατριβής (pdf)