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

Abstract

Αντικείμενο της διατριβής αποτελεί η σχεδίαση κατανεμημένων αλγορίθμων για παροχή ποιότητας υπηρεσίας σε ασύρματα δίκτυα επικοινωνιών με χρήση της θεωρίας παιγνίων. Το πρώτο Κεφάλαιο της Διατριβής παρέχει μια γενική επισκόπηση της θεωρίας παιγνίων, με στόχο να επισημανθούν οι λόγοι εκείνοι που την καθιστούν κατάλληλη για την υιοθέτηση της ως εργαλείο σχεδίασης σύγχρονων ασυρμάτων δικτύων. Στη συνέχεια, γίνεται μια σύντομη ιστορική αναδρομή, ενώ, ιδιαίτερη αναφορά γίνεται στον τρόπο που η θεωρία παιγνίων μπορεί να χρησιμοποιηθεί αποτελεσματικά στην επίλυση προβλημάτων σε ασύρματα δίκτυα. Τέλος, γίνεται μια εισαγωγική παρουσίαση των προβλημάτων του ελέγχου ισχύος, της δρομολόγησης και της διαχείρισης εμπιστοσύνης.Στο δεύτερο Κεφάλαιο της Διατριβής δίνονται οι βασικές αρχές της θεωρίας λήψης αποφάσεων, αφού, άλλωστε, η θεωρία παιγνίων εξετάζει αποφάσεις που λαμβάνονται από πολλούς παίκτες. Αρχικά, γίνεται μια σύντομη εισαγωγή στην κλασική θεωρία λήψης αποφάσεων, όπως αυτή ξεκίνησε από τις εργασίες των \tl{Von Neumann} και \tl{Morgenstern}. Ιδιαίτερη έμφαση αποδίδεται στις προτιμήσεις των παικτών που μετέχουν σε ασύρματα δίκτυα επικοινωνιών. Οι προτιμήσεις μπορεί να εκτείνονται από το φυσικό στρώμα (αποφάσεις που σχετίζονται με το επίπεδο ισχύος, το σχήμα διαμόρφωσης και κωδικοποίησης) έως το επίπεδο δικτύου και το στρώμα εφαρμογής (αποφάσεις που σχετίζονται με τη μεγιστοποίηση της διάρκειας ζωής του συστήματος και τη βελτίωση της ποιότητας υπηρεσιών)Στο τρίτο Κεφάλαιο της Διατριβής παρουσιάζονται παίγνια που αναπαρίστανται σε στρατηγική μορφή. Αρχικά δίδεται ο μαθηματικός ορισμός των στρατηγικών παιγνίων. Στη συνέχεια παρουσιάζονται οι βασικές μεθοδολογίες επίλυσής τους με ιδιαίτερη έμφαση στην επαναληπτική διαγραφή \tl{iterative deletion} των κυριαρχούμενων στρατηγικών \tl{dominated strategies}. Επιπλέον, ορίζεται η πολύ γνωστή έννοια της ισορροπίας \tl{Nash}, ενώ συζητούνται και θέματα που σχετίζονται με την ύπαρξη αυτής. Ακόμη, παρουσιάζεται η έννοια των μικτών στρατηγικών, ενώ αποδεικνύεται η ύπαρξη ισορροπίας σε μικτές στρατηγικές πεπερασμένων παιγνίων. Τέλος, παρουσιάζονται παραδείγματα διατύπωσης προβλημάτων σε ασύρματα δίκτυα με χρήση θεωρία παιγνίων στρατηγικής μορφής. Έμφαση δίνεται στη διατύπωση του προβλήματος καταστολής μηνυμάτων για παροχή υπηρεσιών πολυεκπομπής σε μεγάλο πλήθος χρηστών. Στο Κεφάλαιο 4, το πρόβλημα αυτό επιλύεται για την περίπτωση που οι χρήστες έχουν ελλιπή πληροφόρηση από το δίκτυο.Τα υπόλοιπα Κεφάλαια μελετούν προβλήματα ασυρμάτων δικτύων με χρήση επαναλαμβανόμενων παιγνίων. Αρχικά, στο Κεφάλαιο 5, παρουσιάζονται βασικές αρχές των επαναλαμβανόμενων παιγνίων δίνοντας ιδιαίτερη έμφαση στην έννοια της τέλειας ισορροπίας υποπαιγνίου. Ταυτόχρονα, παρουσιάζονται παραδείγματα εφαρμογής των επαναληπτικών παιγνίων στο πρόβλημα της συνεργασίας μεταξύ των κόμβων και της εκχώρησης πόρων για παροχή υπηρεσιών με ευαισθησία στην καθυστέρηση. Τέλος, στο Κεφάλαιο 6 αφού γίνει μια σύντομη εισαγωγή στην εξελικτική θεωρία παιγνίων παρουσιάζεται ένα παράδειγμα δρομολόγηση σε ασύρματα δίκτυα κορμού πολλαπλών βημάτων.