Optimization algorithms for high throughput wireless and satellite networks

Abstract

The huge increase in the demands of wireless users for very high data rate broadband services is a common realization. In addition, there is need to boost the performance of mobile backhaul networks in terms of capacity and resilience against link failure or congestion. Considering also that one of the main targets in fifth generation (5G) wireless networks is the satisfaction of high traffic demand of users, the satellite networks play a vital role on this. Specifically, High Throughput Satellite (HTS) systems are rendered as a reliable part toward this direction mainly providing communication services in rural and remote areas where the terrestrial networks have limited connectivity and also through the support of terrestrial infrastructure of 5G networks for backhauling and traffic offload. Generally, HTS systems, targeting to provide speed from hundreds of Gb/s to Tb/s, contain the communication of gateways (GWs) and user equipment (UE) beams through the satellite. The links between the GWs and the satellite are called feeder links and are using higher RF frequencies, such as the Q/V or W bands. Lower frequencies, such as the Ka band, are exploited for the links between the satellites and the UE beam, called user links (downlinks).This dissertation focuses on the design of effective optimization schemes for the appropriate pairing in HTS systems among GWs and UEs, considering their offered and requested capacities respectively and the atmospheric transmission conditions. Firstly, considering that each GW offers the same capacity to UEs, focusing on the feeder links, an allocation scheme is proposed applying the Gale–Shapley (GS) algorithm for minimizing the system’s losses. This algorithm finds a stable solution of the marriage matching problem in polynomial time. Afterwards, under the same scenario, it is proven that the optimal allocation can be achieved by an algorithm with lower complexity, based on the theory of Monge arrays. This theory is also applied to other known performance metrics. Moreover, extended numerical results for various hypothetical scenarios are presented.Furthermore, we study the case where different capacities are offered by each GW to every UE and an optimal matching scheme is presented based on Hungarian algorithm, that solves the assignment problem in polynomial time. In all the aforementioned scenarios, GWs can serve one or more UEs simultaneously, resulting in one-to-one (O2O) and one-to-many (O2M) pairings, respectively. However, in O2M cases the number of served UEs is predetermined.Finally, without predetermining the simultaneous served UEs, we show suboptimal O2M allocation schemes using a two-step heuristic approach in problems related with the satisfaction, dissatisfaction ratios and nth (positive, integer) order rate matching of UEs. Firstly, solving a relaxed continuous allocation problem, we apply approximations from fractional programming and the sequential convex optimization (SCO) and then the continuous to discrete conversion of pairing solution is made, resulting in a feasible solution for the initial problem.

Η τεράστια αύξηση των απαιτήσεων των χρηστών ασύρματων δικτύων για πολύ υψηλές ταχύτητες δεδομένων ευρυζωνικών υπηρεσιών αποτελεί κοινό τόπο. Επιπλέον, υπάρχει η ανάγκη να ενισχυθεί η απόδοση των δικτύων υποστήριξης όσον αφορά την διατήρηση της χωρητικότητάς τους σε περιπτώσεις πιθανής συμφόρησης ή παύσης λειτουργίας της ζεύξης επικοινωνίας. Λαμβάνοντας επίσης υπόψη ότι ένας από τους κύριους στόχους στα ασύρματα δίκτυα πέμπτης γενιάς (5G) είναι η ικανοποίηση των υψηλών ταχυτήτων των χρηστών, τα δορυφορικά δίκτυα αποτελούν αναπόσπαστο μέρος αυτού του δικτύου. Συγκεκριμένα, τα δορυφορικά συστήματα υψηλής ρυθμοαπόδοσης (High Throughput Satellites, HTS) αποτελούν αξιόπιστη λύση συνδεσιμότητας και επικοινωνίας. Μπορούν να παρέχουν είτε κατευθείαν τηλεπικοινωνιακές υπηρεσίες σε αγροτικές και απομονωμένες περιοχές όπου τα επίγεια δίκτυα ενδεχομένως να έχουν περιορισμένη συνδεσιμότητα ή την υποστήριξη επίγειων υποδομών σε δίκτυα 5G, ως «οπίσθια» ζεύξη (backhaul) για τη γενικότερη αποσυμφόρηση της τηλεπικοινωνικής κίνησης. Γενικά, τα συστήματα HTS, που στοχεύουν στην παροχή ταχύτητας από εκατοντάδες Gb/s έως Tb/s, παρέχουν την επικοινωνία των δορυφορικών πυλών (gateway, GW) με τους χρήστες (user equipment, UE) μέσω του δορυφόρου. Οι ζεύξεις μεταξύ GW και δορυφόρου ονομάζονται ζεύξεις τροφοδοσίας (feeder links) και χρησιμοποιούν τις υψηλότερες RF συχνότητες, όπως οι ζώνες Q/V ή W, ενώ χαμηλότερες συχνότητες, όπως η Ka ζώνη, χρησιμοποιούνται για την επικοινωνία δορυφόρου και UE, που ονομάζεται ζεύξη χρήστη (κατερχόμενη ζεύξη).Η παρούσα εργασία επικεντρώνεται στο σχεδιασμό αποδοτικών αλγορίθμων βελτιστοποίησης για την κατάλληλη σύνδεση μεταξύ των GWs και των UEs σε δορυφορικά συστήματα υψηλής ρυθμοαπόδοσης, λαμβάνοντας υπόψη τις προσφερόμενες και ζητούμενες χωρητικότητές τους, αντίστοιχα και τις ατμοσφαιρικές συνθήκες μετάδοσης. Πρώτον, λαμβάνοντας υπόψη ότι κάθε GW προσφέρει την ίδια χωρητικότητα στους UEs, δίνοντας έμφαση στις ζεύξεις τροφοδοσίας, προτείνεται ένα ταίριασμα μεταξύ τους εφαρμόζοντας τον αλγόριθμο Gale–Shapley (GS) για την ελαχιστοποίηση των απωλειών του συστήματος. Αυτός βρίσκει μια ευσταθή λύση του «προβλήματος ταιριάσματος συζύγων» (marriage matching problem) σε πολυωνυμικό χρόνο. Στη συνέχεια, στο ίδιο σενάριο, αποδεικνύεται ότι το βέλτιστο ταίριασμα μπορεί να επιτευχθεί με έναν αλγόριθμο με χαμηλότερη πολυπλοκότητα, βασισμένο στη θεωρία των πινάκων Monge. Τέλος η συγκεκριμένη θεωρία εφαρμόζεται και σε άλλες γνωστές μετρικές επίδοσης. Επιπλέον, παρουσιάζονται εκτεταμένα αριθμητικά αποτελέσματα σε διάφορα υποθετικά δορυφορικά δίκτυα.Ακόμα, μελετάται η περίπτωση όπου διαφορετικές χωρητικότητες προσφέρονται από κάθε GW σε κάθε UE και παρουσιάζεται μια βέλτιστη μέθοδος αντιστοίχισης βάσει του Ουγγρικού αλγορίθμου, που λύνει το πρόβλημα εκχώρησης σε πολυωνυμικό χρόνο. Σε όλα τα προαναφερθέντα σενάρια, οι GWs μπορούν να εξυπηρετήσουν έναν ή περισσότερους UEs ταυτόχρονα, καταλήγοντας στον σχηματισμό ζευγών ένα-προς-ένα (one-to-one, O2O) και ένα-προς-πολλά (one-to-many, O2M), αντίστοιχα. Ωστόσο, στις περιπτώσεις του O2M ο αριθμός των UE που εξυπηρετούνται είναι προκαθορισμένος.Τέλος, χωρίς τη χρήση προκαθορισμένου αριθμού ταυτόχρονα εξυπηρετούμενων χρηστών, παρουσιάζονται υποβέλτιστα O2M ταιριάσματα χρησιμοποιώντας μια ευρετική διαδικασία δύο σταδίων, για την επίλυση προβλημάτων σχετικών με το επίπεδο ικανοποίησης, δυσαρέσκειας και αντιστοίχισης χωρητικοτήτων νιοστής τάξης (θετικό και ακέραιο ν) των χρηστών. Αρχικά «χαλαρώνοντας» το πρόβλημα ταιριάσματος λύνουμε ένα συνεχές πρόβλημα χρησιμοποιώντας προσεγγίσεις από τη θεωρία κλασματικού προγραμματισμού και τη διαδοχική κυρτή βελτιστοποίηση (sequential convex optimization, SCO). Στη συνέχεια η συνεχής λύση μετατρέπεται σε διακριτή και έτσι καταλήγουμε σε μια εφικτή λύση του αρχικού προβλήματος.