Optimization algorithms for high throughput wireless and satellite networks
Authors: Ρουμελιώτης Ανάργυρος 
Published: February 2022

Η τεράστια αύξηση των απαιτήσεων των χρηστών ασύρματων δικτύων για πολύ υψηλές ταχύτητες δεδομένων ευρυζωνικών υπηρεσιών αποτελεί κοινό τόπο. Επιπλέον, υπάρχει η ανάγκη να ενισχυθεί η απόδοση των δικτύων υποστήριξης όσον αφορά την διατήρηση της χωρητικότητάς τους σε περιπτώσεις πιθανής συμφόρησης ή παύσης λειτουργίας της ζεύξης επικοινωνίας. Λαμβάνοντας επίσης υπόψη ότι ένας από τους κύριους στόχους στα ασύρματα δίκτυα πέμπτης γενιάς (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). Στη συνέχεια η συνεχής λύση μετατρέπεται σε διακριτή και έτσι καταλήγουμε σε μια εφικτή λύση του αρχικού προβλήματος.