Βελτιστοποίηση ασύρματων κυψελωτών δικτύων με υποστήριξη άμεσης επικοινωνίας
Authors: Κατσίνης Γεώργιος 
Published: September 2021

Η παρούσα διδακτορική διατριβή πραγματεύεται το πρόβλημα της βέλτιστης κατανομής ομάδων πόρων κι ισχύος εκπομπής σε ασύρματα κυψελωτά δίκτυα επικοινωνιών με υποστήριξη άμεσης επικοινωνίας των χρηστών. Οι χρήστες του δικτύου επικοινωνούν απευθείας μεταξύ τους είτε χρησιμοποιώντας διαφορετικές ομάδες πόρων από τους συμβατικούς χρήστες κυψελωτής επικοινωνίας (overlay) είτε μοιραζόμενοι κοινές ομάδες πόρων με τους χρήστες κυψελωτής επικοινωνίας (underlay). Για τον πρώτο τρόπο χρήσης των ομάδων πόρων (overlay) μελετήθηκε η διαδικασία ανάθεσης τους μέσω ενός μοντέλου ουρών αναμονής και βελτιστοποιήθηκε ως προς την ελαχιστοποίηση και την εξισορρόπηση των πιθανοτήτων μη εξυπηρέτησης των χρηστών. Για το δεύτερο τρόπο χρήσης των ομάδων πόρων, δηλαδή της κοινής χρήσης ομάδων πόρων (underlay), αρχικά μελετήθηκε το πρόβλημα της κατανομής ισχύος εκπομπής στην άνω ζεύξη ενός δικτύου με υποστήριξη άμεσης επικοινωνίας. Αποδείχθηκε η ύπαρξη ενός σημείου ισορροπίας (ΣΙ) Nash και προτάθηκε ένας κατανεμημένος αλγόριθμος βέλτιστης απόκρισης που συγκλίνει σε αυτό.Στη συνέχεια και με στόχο την ελαχιστοποίηση των συνολικών παρεμβολών στο δίκτυο μελετήθηκε το συνδυαστικό πρόβλημα κατανομής ομάδων πόρων κι ισχύος εκπομπής σε περιβάλλον μίας αλλά και περισσότερων κυψελών. Το παραπάνω πρόβλημα είναι ένα πρόβλημα μικτού ακέραιου προγραμματισμού. Λόγω της ιδιαίτερα υψηλής υπολογιστικής πολυπλοκότητας του προβλήματος αυτού, αναλύθηκε σε δύο υποπροβλήματα. Πρώτα μελετήθηκε το πρόβλημα κατανομής ομάδων πόρων για σταθερή ισχύ εκπομπής και στη συνέχεια με δεδομένο το αποτέλεσμα από την επίλυσή του, αντιμετωπίστηκε το πρόβλημα κατανομής ισχύος εκπομπής για κάθε διαθέσιμη ομάδα πόρων. Για καθένα από τα παραπάνω προβλήματα προτάθηκαν κατανεμημένες και αποδοτικές υπολογιστικά προσεγγίσεις.Για την περίπτωση της μιας κυψέλης θεωρήθηκε ότι οι χρήστες κυψελωτής επικοινωνίας έχουν επιλέξει καθένας τους μια διαφορετική ομάδα πόρων και μοντελοποιήθηκε το πρόβλημα επιλογής ομάδας πόρων για τους χρήστες άμεσης επικοινωνίας. Το πρόβλημα αυτό μοντελοποιήθηκε ως ένα ακριβές δυναμικό παίγνιο για το οποίο η συνάρτηση δυναμικού του ταυτίζεται με τις συνολικές παρεμβολές στο δίκτυο. Τα παίγνια αυτά διαθέτουν εξαιρετικά επιθυμητές ιδιότητες που αφορούν την ύπαρξη τουλάχιστον ενός ΣΙ Nash αλλά κι ενός αλγορίθμου βέλτιστης απόκρισης που συγκλίνει σε αυτό εντός πεπερασμένου πλήθους βημάτων. Για το δεύτερο πρόβλημα της κατανομής ισχύος εκπομπής προτάθηκε ένα μη συνεργατικό κοίλο παίγνιο το οποίο ωθεί τους χρήστες στην επίτευξη ενός ελάχιστα επιθυμητού επιπέδου σηματοθορυβικού λόγου με την ελάχιστη δυνατή τιμή ισχύος εκπομπής. Για το παίγνιο αυτό αποδείχθηκε η σύγκλιση του στο απαραίτητο ΣΙ Nash τόσο θεωρητικά όσο και μέσω αριθμητικών προσομοιώσεων.Στη συνέχεια η προηγούμενη προσέγγιση επεκτάθηκε προκειμένου να αντιμετωπίσει το αντίστοιχο πρόβλημα συνδυαστικής κατανομής ομάδων πόρων κι ισχύος εκπομπής σε περιβάλλον πολλαπλών κυψελών. Εδώ επεκτάθηκε η έννοια της κυψέλης για να καλύψει και την περίπτωση των χρηστών άμεσης επικοινωνίας. Έτσι διατυπώθηκε ένα παίγνιο κατανομής ομάδων πόρων με παίχτες όλους τους πιθανούς δέκτες του δικτύου είτε αυτοί εξυπηρετούν ένα χρήστη (δέκτες χρηστών άμεσης επικοινωνίας) είτε περισσότερους (σταθμοί βάσης). Στο πρώτο στάδιο της προσέγγισης το παίγνιο κατανομής ομάδων πόρων μοντελοποιείται ως ένα διμερές συμμετρικό παίγνιο το οποίο αποτελεί μια ειδική κατηγορία ακριβούς δυναμικού παιγνίου. Έτσι εκμεταλλευόμενοι τις επιθυμητές ιδιότητες των δυναμικών παιγνίων σχεδιάστηκε ένας αλγόριθμος βέλτιστης απόκρισης που συγκλίνει στο επιθυμητό ΣΙ Nash εντός πεπερασμένου πλήθους βημάτων. Επίσης προτάθηκε μια πιθανοτική αλλά πλήρως κατανεμημένη εκδοχή του παραπάνω αλγορίθμου κατανομής ομάδων πόρων η οποία υπολογίζει με ικανοποιητικό τρόπο το απαιτούμενο ΣΙ Nash αλλά με σαφώς μικρότερο αριθμό επαναλήψεων και κόστος σηματοδοσίας. Αποδείχθηκε μέσω των αριθμητικών προσομοιώσεων ότι το ΣΙ Nash μειώνει δραστικά τις συνολικές παρεμβολές στο δίκτυο. Στη συνέχεια, με δεδομένο το αποτέλεσμα της 1ης φάσης της προσέγγισης, διατυπώνεται το πρόβλημα κατανομής ισχύος εκπομπής για κάθε μοιραζόμενη ομάδα πόρων του δικτύου. Αποδεικνύεται ότι το πρόβλημα ελαχιστοποίησης παρεμβολών σε κάθε ομάδα πόρων ισοδυναμεί με ένα πρόβλημα ελαχιστοποίησης συνολικών ισχύων εκπομπής υπό τους ίδιους περιορισμούς για το σηματοθορυβικό λόγο και για τις δυνατές τιμές ισχύος εκπομπής. Έτσι εφαρμόζοντας το γνωστό αλγόριθμο των Foschini-Miljanic για την ελαχιστοποίηση της συνολικά εκπεμπόμενης ισχύος επιτυγχάνεται μείωση των συνολικών παρεμβολών. Τέλος μέσω αριθμητικών προσομοιώσεων για μεταβαλλόμενες θέσεις των χρηστών άμεσης και κυψελωτής επικοινωνίας φαίνεται ότι επιτυγχάνεται τόσο μείωση της εκπεμπόμενης ισχύος αλλά και αύξηση του αριθμού των χρηστών που εξασφαλίζουν ένα ελάχιστο επίπεδο σηματοθορυβικού λόγου στους δέκτες τους.