Βελτιστοποίηση Ασύρματων Κυψελωτών Δικτύων Με Υποστήριξη Άμεσης Επικοινωνίας

Abstract

Η παρούσα διδακτορική διατριβή πραγματεύεται το πρόβλημα της βέλτιστης κατανομής ομάδων πόρων κι ισχύος εκπομπής σε ασύρματα κυψελωτά δίκτυα επικοινωνιών με υποστήριξη άμεσης επικοινωνίας των χρηστών. Οι χρήστες του δικτύου επικοινωνούν απευθείας μεταξύ τους είτε χρησιμοποιώντας διαφορετικές ομάδες πόρων από τους συμβατικούς χρήστες κυψελωτής επικοινωνίας (overlay) είτε μοιραζόμενοι κοινές ομάδες πόρων με τους χρήστες κυψελωτής επικοινωνίας (underlay). Για τον πρώτο τρόπο χρήσης των ομάδων πόρων (overlay) μελετήθηκε η διαδικασία ανάθεσης τους μέσω ενός μοντέλου ουρών αναμονής και βελτιστοποιήθηκε ως προς την ελαχιστοποίηση και την εξισορρόπηση των πιθανοτήτων μη εξυπηρέτησης των χρηστών. Για το δεύτερο τρόπο χρήσης των ομάδων πόρων, δηλαδή της κοινής χρήσης ομάδων πόρων (underlay), αρχικά μελετήθηκε το πρόβλημα της κατανομής ισχύος εκπομπής στην άνω ζεύξη ενός δικτύου με υποστήριξη άμεσης επικοινωνίας. Αποδείχθηκε η ύπαρξη ενός σημείου ισορροπίας (ΣΙ) Nash και προτάθηκε ένας κατανεμημένος αλγόριθμος βέλτιστης απόκρισης που συγκλίνει σε αυτό.Στη συνέχεια και με στόχο την ελαχιστοποίηση των συνολικών παρεμβολών στο δίκτυο μελετήθηκε το συνδυαστικό πρόβλημα κατανομής ομάδων πόρων κι ισχύος εκπομπής σε περιβάλλον μίας αλλά και περισσότερων κυψελών. Το παραπάνω πρόβλημα είναι ένα πρόβλημα μικτού ακέραιου προγραμματισμού. Λόγω της ιδιαίτερα υψηλής υπολογιστικής πολυπλοκότητας του προβλήματος αυτού, αναλύθηκε σε δύο υποπροβλήματα. Πρώτα μελετήθηκε το πρόβλημα κατανομής ομάδων πόρων για σταθερή ισχύ εκπομπής και στη συνέχεια με δεδομένο το αποτέλεσμα από την επίλυσή του, αντιμετωπίστηκε το πρόβλημα κατανομής ισχύος εκπομπής για κάθε διαθέσιμη ομάδα πόρων. Για καθένα από τα παραπάνω προβλήματα προτάθηκαν κατανεμημένες και αποδοτικές υπολογιστικά προσεγγίσεις.Για την περίπτωση της μιας κυψέλης θεωρήθηκε ότι οι χρήστες κυψελωτής επικοινωνίας έχουν επιλέξει καθένας τους μια διαφορετική ομάδα πόρων και μοντελοποιήθηκε το πρόβλημα επιλογής ομάδας πόρων για τους χρήστες άμεσης επικοινωνίας. Το πρόβλημα αυτό μοντελοποιήθηκε ως ένα ακριβές δυναμικό παίγνιο για το οποίο η συνάρτηση δυναμικού του ταυτίζεται με τις συνολικές παρεμβολές στο δίκτυο. Τα παίγνια αυτά διαθέτουν εξαιρετικά επιθυμητές ιδιότητες που αφορούν την ύπαρξη τουλάχιστον ενός ΣΙ Nash αλλά κι ενός αλγορίθμου βέλτιστης απόκρισης που συγκλίνει σε αυτό εντός πεπερασμένου πλήθους βημάτων. Για το δεύτερο πρόβλημα της κατανομής ισχύος εκπομπής προτάθηκε ένα μη συνεργατικό κοίλο παίγνιο το οποίο ωθεί τους χρήστες στην επίτευξη ενός ελάχιστα επιθυμητού επιπέδου σηματοθορυβικού λόγου με την ελάχιστη δυνατή τιμή ισχύος εκπομπής. Για το παίγνιο αυτό αποδείχθηκε η σύγκλιση του στο απαραίτητο ΣΙ Nash τόσο θεωρητικά όσο και μέσω αριθμητικών προσομοιώσεων.Στη συνέχεια η προηγούμενη προσέγγιση επεκτάθηκε προκειμένου να αντιμετωπίσει το αντίστοιχο πρόβλημα συνδυαστικής κατανομής ομάδων πόρων κι ισχύος εκπομπής σε περιβάλλον πολλαπλών κυψελών. Εδώ επεκτάθηκε η έννοια της κυψέλης για να καλύψει και την περίπτωση των χρηστών άμεσης επικοινωνίας. Έτσι διατυπώθηκε ένα παίγνιο κατανομής ομάδων πόρων με παίχτες όλους τους πιθανούς δέκτες του δικτύου είτε αυτοί εξυπηρετούν ένα χρήστη (δέκτες χρηστών άμεσης επικοινωνίας) είτε περισσότερους (σταθμοί βάσης). Στο πρώτο στάδιο της προσέγγισης το παίγνιο κατανομής ομάδων πόρων μοντελοποιείται ως ένα διμερές συμμετρικό παίγνιο το οποίο αποτελεί μια ειδική κατηγορία ακριβούς δυναμικού παιγνίου. Έτσι εκμεταλλευόμενοι τις επιθυμητές ιδιότητες των δυναμικών παιγνίων σχεδιάστηκε ένας αλγόριθμος βέλτιστης απόκρισης που συγκλίνει στο επιθυμητό ΣΙ Nash εντός πεπερασμένου πλήθους βημάτων. Επίσης προτάθηκε μια πιθανοτική αλλά πλήρως κατανεμημένη εκδοχή του παραπάνω αλγορίθμου κατανομής ομάδων πόρων η οποία υπολογίζει με ικανοποιητικό τρόπο το απαιτούμενο ΣΙ Nash αλλά με σαφώς μικρότερο αριθμό επαναλήψεων και κόστος σηματοδοσίας. Αποδείχθηκε μέσω των αριθμητικών προσομοιώσεων ότι το ΣΙ Nash μειώνει δραστικά τις συνολικές παρεμβολές στο δίκτυο. Στη συνέχεια, με δεδομένο το αποτέλεσμα της 1ης φάσης της προσέγγισης, διατυπώνεται το πρόβλημα κατανομής ισχύος εκπομπής για κάθε μοιραζόμενη ομάδα πόρων του δικτύου. Αποδεικνύεται ότι το πρόβλημα ελαχιστοποίησης παρεμβολών σε κάθε ομάδα πόρων ισοδυναμεί με ένα πρόβλημα ελαχιστοποίησης συνολικών ισχύων εκπομπής υπό τους ίδιους περιορισμούς για το σηματοθορυβικό λόγο και για τις δυνατές τιμές ισχύος εκπομπής. Έτσι εφαρμόζοντας το γνωστό αλγόριθμο των Foschini-Miljanic για την ελαχιστοποίηση της συνολικά εκπεμπόμενης ισχύος επιτυγχάνεται μείωση των συνολικών παρεμβολών. Τέλος μέσω αριθμητικών προσομοιώσεων για μεταβαλλόμενες θέσεις των χρηστών άμεσης και κυψελωτής επικοινωνίας φαίνεται ότι επιτυγχάνεται τόσο μείωση της εκπεμπόμενης ισχύος αλλά και αύξηση του αριθμού των χρηστών που εξασφαλίζουν ένα ελάχιστο επίπεδο σηματοθορυβικού λόγου στους δέκτες τους.This PhD thesis addresses the problem of optimal resource allocation in Device to Device (D2D) enabled cellular networks. In this type of networks users may communicate directly with each other either by using different resource blocks (RBs) or sharing common RBs with the conventional cellular users. The general perspective of the thesis is to allocate RBs and transmission power to users in order to satisfy their minimum signal to interference and noise ratio (SINR) constraints with the minimum transmitted power.For the overlay case, a queueing system is proposed in order to model the RB allocation process. Our aim is to balance and minimize the blocking probability of each type of user of the network. This model finds the optimal policy for the RB allocation and a heuristic algorithm is used in order to find the necessary parameters of the optimal policy, which is shown to be of threshold type.Then, we focus on the underlay case of RB sharing where cellular and D2D users share the same RBs. A game theoretic approach is proposed for the power control problem for a given RB. A Nash equilibrium (NE) point is proven to exist and a best response algorithm is proposed in order to converge to the NE point of the game. In this way, the users of the network find an optimal tradeoff between the amount of transmitted power and the required SINR level at their receivers.Next, we formulate the problem of interference minimization under users’ SINR constraints for a D2D underlay cellular network. We study both the single cell and the multicell case. Due to the computational intractability of the problem, it is decomposed by two separate subproblems. The first one is a RB allocation problem under fixed transmission power while the second, following the result from the first one, is a power control problem for every shared RB. For both problems, efficient algorithms are proposed. The first problem is modelled as an exact potential game where the total interference of the network coincides the opposite of the potential function of the respective game. Leveraging the desirable properties of the exact potential games a best response algorithm is proposed which converges to the NE point of the respective game. After that, the power control problem is modelled as a concave game where a distributed algorithm for the NE computation is proposed. This algorithm is proven to converge to the NE of the game after finite number of iterations.The previous approach is further extended in order to cover the case of multicell D2D underlay cellular network. In the first step, the total interference minimization problem under fixed transmission power is modelled as a bilateral symmetric game which belongs to a special category of exact potential games. Thus, following a best response algorithm, we reach a NE point of the game under finite number of iterations. Moreover, a random distributed version of the best response algorithm is proposed which achieves fair performance with significantly lower number of iterations and communication overhead. Then the problem of interference minimization for the RB allocation vector proposed by the first stage is shown to be equivalent to a total power minimization problem under the same constraints. Following the well-known Foschini Miljanic algorithm which solves the total power minimization problem a suitable solution for our problem is obtained. Finally, we demonstrate via extensive numerical simulations that the total transmitted power is reduced dramatically and the number of users who satisfy their SINR requirements increases significantly.