Development of large-scale optimization techniques and algorithms for use in wireless communication networks

Abstract

Wireless communication networks have evolved through successive generations, progressing from 1G to 5G and the imminent 6G. Throughout this evolution, mathematical optimization has been a fundamental tool for theoretical design and research of wireless networks. The novel characteristics and demands of each generation have led to a fundamental shif tin the structure of the underlying optimization problems, necessitating the development of novel solution techniques. Convex optimization, for instance, has been extensively utilized, and it has been proven to be adequate in addressing the majority of the challenges posed by the 3G research. Nonetheless, during the 4G research era, distributed optimization methods garnered attention due to their ability to leverage network densification and coordinate multiple base stations or network nodes, there by augmenting the available computing power. Concurrently, machine learning (ML) techniques have recently begun to complement or totally replace some traditional optimization methods which aim to address more complex problems. Finally, in the ongoin research context of 6G, quantum computing is being explored as a novel approach to address problems stemming from classical and quantum communications. In this regard, the second chapter of this thesis presents an over-the-air computing(AirComp) framework that significanlty reduces the communication latency in constrained distributed convex optimization problems. Specifically, the optimization procedure utilizesa distributed primal-dual (DPD) subgradient method. Under general assumptions, we prove that the DPD-AirComp method can asymptotically achieve zero expected constraint violation. Thus, DPD-AirComp ensures the feasibility of the original problem despite channel fading and additive noise. Furthermore, proper power control of the users’ signalscan mitigate the expected non-zero optimality gap. We present two practical applications of the proposed framework: smart grid management and wireless resource allocation. Finally, numerical results confirm the excellent performance of DPD-AirComp, which converges an order of magnitude faster than two digital orthogonal multiple access schemes: time-division multiple access (TDMA) and orthogonal frequency-division multiple access(OFDMA). In Chapter 3, we demonstrate how ML methods can serve as scalable optimization solvers, appropriate at solving the high-dimensional, non-convex design challenges that have surfaced with the 5G networks and the ongoing research for the 6G. Specifically, in the first part of this Chapter, we propose a novel peak-to-average power ratio (PAPR)-aware adaptive modulation scheme for Orthogonal Frequency Division Multiplexing (OFDM). The aim of the proposed PAPR-aware protocol is to maximize the energy efficiency ofthe OFDM transmission, where the energy efficiency is defined as the ratio of the OFDM throughput to the PA consumption, and is thus strongly affected by PAPR. For this purpose, we formulate the energy efficiency maximization problem with respect to powerand adaptive modulation constraints per subcarrier. Due to the joint optimization of power allocation, adaptive modulation, and the non-convex terms introduced by PAPR, the problem cannot be solved by using standard convex optimization methods. Therefore, a solution based on online deep learning is proposed. Numerical results showcase that the energy efficiency of the proposed PAPR-aware protocol is greater up to 3-dB compared to the conventional PAPR-unaware protocol, while the PAPR is also reduced by 3-dB. In the second part of Chapter 3, a multi-task learning approach is studied, towards a more general resource allocation paradigm. Specifically, the optimal solution to anoptimization problem depends on the problem’s objective function, constraints, and size. While deep neural networks (DNNs) have proven effective in solving optimization problems, changes in the problem’s size, objectives, or constraints often require adjustments to the DNN architecture to maintain effectiveness, or even retraining a new DNN from scratch. Given the nature of wireless networks, which involves multiple and diverse objectives that can have conflicting requirements and constraints, we propose a multi-task learning (MTL) framework to enable a single DNN to jointly solve a range of diverse optimization problems. In this framework, optimization problems with varying dimensionality values, objectives, and constraints are treated as distinct tasks. To jointly address these tasks, we propose aconditional computation-based MTL approach with routing. The multi-task DNN consists of two components, the base DNN (bDNN), which is the single DNN used to extract the solutions for all considered optimization problems, and the routing DNN (rDNN), which manages which nodes and layers of the bDNN to be used during the forward propagation of each task. The output of the rDNN is multiplied with all bDNN’s weights during the forward propagation, creating a unique computational path through the bDNN for each task. This setup allows the tasks to either share parameters or use independent ones, with the decision controlled by the rDNN. The proposed framework supports both supervised and unsupervised learning scenarios. Based on this framework, a soft modularization and a hard parameter sharing approach of lower complexity are proposed. The numerical results demonstrate the efficiency of the proposed MTL approaches compared to several multi-task benchmarks and the single-task DNN approach. Chapter 4 studies the optimal beamforming of a multiple-input multiple-output(MIMO) system, with b-bit quantized pre- and post-processing vectors. Specifically, the Chapter explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver. We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit. Notably, this work is the first to show a theoretical connection between quantum circuits and phase shifts in pre/post-coding, which could have broader applications in other fields, such as integrated sensing and communication. The analysis for the b-bit caseis presented, along with a warm-start QAOA approach to improve computational efficiency. Numerical results highlight the effectiveness of the proposed method in achieving optimal quantized beamforming and the performance gain of the proposed warm-start approach.

Από τις πρώιμες ημέρες των αναλογικών επικοινωνιών και του 1G, μέχρι το 5G του σήμερα,τα ασύρματα δίκτυα τηλεπικοινιών έχουν εξελιχθεί πέρα από κάθε πρόβλεψη, ενώ ήδη ερευνάται η επικείμενη έλευση του 6G. Καθ’ όλη αυτή την εξέλιξη, η μαθηματική βελτιστοποίηση έχει αποτελέσει βασικό εργαλείο για τη θεωρητική μελέτη και τον σχεδιασμό των τηλεπικοινωνιακών συστημάτων. Τα χαρακτηριστικά και οι απαιτήσεις κάθε γενιάς έχουν επιφέρει ουσιώδεις αλλαγές στη δομή των σχετικών προβλημάτων βελτιστοποίησης, οδηγώντας στην ανάγκη ανάπτυξης καινοτόμων μεθόδων επίλυσης. Για παράδειγμα, η κυρτή βελτιστοποίηση έχει αξιοποιηθεί ευρέως και έχει αποδειχθεί επαρκής για την αντιμετώπιση των περισσότερων ερευνητικών προκλήσεων γύρω από το 3G. Παρ’ όλα αυτά, κατά τη διάρκεια της έρευνας για το 4G αυξήθηκε το ενδιαφέρον για τις κατανεμημένες μεθόδους βελτιστοποίησης, λόγω της ικανότητάς τους να αξιοποιούν την αυξημένη πυκνότητα των δικτύων συντονίζοντας πολλαπλούς σταθμούς βάσης ή κόμβους, ενισχύοντας έτσι τη διαθέσιμη υπολογιστική ισχύ. Παράλληλα, οι τεχνικές μηχανικής μάθησης έχουν αρχίσει να επικουρούν ή ακόμη και να αντικαθιστούν πλήρως ορισμένες από τις παραδοσιακές προσεγγίσεις βελτιστοποίησης που στοχεύουν στην επίλυση πιο σύνθετων σεναρίων, όπως αυτά που απορρέουν από το 5G. Τέλος, στο ερευνητικό πλαίσιο του 6G εξετάζεται η χρήση της κβαντικής υπολογιστικής ως δυνητική προσέγγιση για την αντιμετώπιση προβλημάτων που προκύπτουν τόσο από τις κλασικές όσο και από τις κβαντικές επικοινωνίες. Σε αυτό το πλαίσιο, το δεύτερο κεφάλαιο της παρούσας διατριβής παρουσιάζει ένα ασύρματο υπολογιστικό σχήμα (over-the-air computing – AirComp), το οποίο μειώνει σημαντικά τη χρονική καθυστέρηση επικοινωνίας κατά την επίλυση κατανεμημένων προβλημάτων κυρτής βελτιστοποίησης με περιορισμούς. Συγκεκριμένα, η διαδικασία βασίζεται σε μια κατανεμημένη εκδοχή της διαδοχικής επίλυσης του πρωτεύοντος και του δυαδικού προβλήματος βελτιστοποίησης με χρήση υποδιαφορικών (distributed primal-dual (DPD) subgradient). Υπό γενικές θεωρητικές παραδοχές, αποδεικνύεται ότι η μέθοδος DPD-AirComp επιτυγχάνει, ασυμπτωτικά, μηδενική μέση παραβίαση των περιορισμών. Συνεπώς, η DPDAirComp διασφαλίζει τη υλοποιησιμότητα του αρχικού προβλήματος, παρά τις επιπτώσεις λόγω της εξασθένησης του καναλιού και του προσθετικού θορύβου. Επιπλέον, η κατάλληλη διαχείριση της ισχύος των σημάτων των χρηστών μπορεί να περιορίσει το μέσο, μη μηδενικό σφάλμα στην εύρεση της βέλτιστης τιμής της αντικειμενικής συνάρτησης. Παρουσιάζονται δύο πρακτικές εφαρμογές του προτεινόμενου πλαισίου: η διαχείριση ενός έξυπνου δικτύου ενέργειας (smart grid) και η κατανομή πόρων σε ένα ασύρματο δίκτυο. Τέλος, τα αριθμητικά αποτελέσματα επιβεβαιώνουν την επίδοση της DPD-AirComp, η οποία συγκλίνει κατά μία τάξη μεγέθους ταχύτερα σε σχέση με δύο ψηφιακά σχήματα ορθογωνικής πολλαπλής πρόσβασης: την πρόσβαση με διαίρεση χρόνου (TDMA) και την πρόσβαση με ορθογώνια πολυπλεξία διαίρεσης συχνότητας (OFDM). Στο Κεφάλαιο 3, παρουσιάζεται πώς οι μέθοδοι μηχανικής μάθησης μπορούν να λειτουργήσουν ως ευέλικτοι επιλυτές προβλημάτων βελτιστοποίησης, κατάλληλοι για μη κυρτά προβλήματα μεγάλων διαστάσεων, που έχουν προκύψει με την ανάπτυξη των δικτύων 5G αλλά και τη τρέχουσα έρευνα πάνω στα δίκτυα 6G. Ειδικότερα, στο πρώτο μέρος του κεφαλαίου προτείνουμε ένα νέο σχήμα προσαρμοστικής διαμόρφωσης που λαμβάνει υπόψιν τον λόγο μέγιστης προς μέσης ισχύος (Peak-to-Average Power Ratio – PAPR) για συστήματα OFDM. Στόχος του προτεινόμενου πρωτοκόλλου είναι η μεγιστοποίηση της ενεργειακής απόδοσης της μετάδοσης OFDM, όπου η ενεργειακή απόδοση ορίζεται ως ο λόγος του ρυθμού μετάδοσης του OFDM προς την κατανάλωση ισχύος του ενισχυτή, και συνεπώς επηρεάζεται σημαντικά από το PAPR. Συνεπώς, διατυπώνουμε το πρόβλημα μεγιστοποίησης της ενεργειακής απόδοσης υπό τους κατάλληλους περιορισμούς ισχύος και προσαρμοστικής διαμόρφωσης ανά υποφέρον. Λόγω της ταυτόχρονης βελτιστοποίησης της κατανομής ισχύος, της διαμόρφωσης και των μη κυρτών όρων που εισάγονται από το PAPR, το πρόβλημα δεν μπορεί να επιλυθεί με χρήση συμβατικών κυρτών μεθόδων βελτιστοποίησης. Ως εκ τούτου, προτείνεται μια λύση βασισμένη σε βαθιά μάθηση. Τα αριθμητικά αποτελέσματα καταδεικνύουν ότι η ενεργειακή απόδοση του προτεινόμενου πρωτοκόλλου που λαμβάνει υπόψιν το PAPR υπερβαίνει έως και 3 dB εκείνη ενός συμβατικού πρωτοκόλλου χωρίς επίγνωση του PAPR, ενώ παράλληλα το ίδιο το PAPR μειώνεται επίσης έως 3 dB. Στο δεύτερο μέρος του Κεφαλαίου 3, μελετάται μια προσέγγιση μάθησης πολλαπλών στόχων (multi-task learning - MTL), ως ένα πρώτο βήμα για την δημιουργία ενός γενικότερου παραδείγματος κατανομής πόρων. Συγκεκριμένα, η βέλτιστη λύση σε ένα πρόβλημα βελτιστοποίησης εξαρτάται από την αντικειμενική του συνάρτηση, τους περιορισμούς του, αλλά και το μέγεθος του προβλήματος. Παρότι τα βαθιά νευρωνικά δίκτυα (DNN) έχουν αποδειχθεί αποτελεσματικά στην επίλυση προβλημάτων βελτιστοποίησης, οι αλλαγές στο μέγεθος ενός προβλήματος, στην αντικειμενική του συνάρτηση ή στους περιορισμούς του συχνά επιφέρουν προσαρμογές στην αρχιτεκτονική του DNN, ή ακόμη και την επανεκπαίδευση του από την αρχή. ΄Ετσι, λαμβάνοντας υπόψιν την φύση των ασύρματων δικτύων, η οποία περιλαμβάνει πολλαπλούς και διαφορετικούς στόχους που μπορεί να έχουν αντικρουόμενες απαιτήσεις και περιορισμούς, προτείνουμε μια προσέγγιση βασισμένη στοMTL, ώστε ένα μόνο DNN να μπορεί να επιλύει από κοινού μια σειρά διαφορετικών προβλημάτων βελτιστοποίησης. Σε αυτό το πλαίσιο, τα προβλήματα βελτιστοποίησης με διαφορετικές διαστάσεις, αντικειμενικές συναρτήσεις ή/και περιορισμούς αντιμετωπίζονται ως ξεχωριστοί στόχοι. Για την ταυτόχρονη επίλυση τους, προτείνουμε μια MTL προσέγγισημε βάση την υπό συνθήκη υπολογιστική και τη δρομολόγηση. Το DNN πολλαπλών στόχων αποτελείται από δύο επιμέρους DNNs, το βασικό DNN (bDNN), το οποίο είναι το ενιαίο DNN που χρησιμοποιείται για την εύρεση λύσεων για όλα τα εξεταζόμενα προβλήματα βελτιστοποίησης, και το DNN δρομολόγησης (rDNN), το οποίο διαχειρίζεται ποιοι κόμβοι και επίπεδα του bDNN θα χρησιμοποιηθούν κατά τη διάρκεια της ευθείας προώθησης κάθε στόχου. Η έξοδος του rDNN πολλαπλασιάζεται με τα βάρη όλων των bDNN κατά την ευθεία διάδοση, δημιουργώντας μια μοναδική υπολογιστική διαδρομή μέσω του bDNN για κάθε στόχο. Αυτή η δρομολόγηση επιτρέπει στους διαφορετικούς στόχους να μοιράζονται ή όχι παραμέτρους, με την απόφαση να ελέγχεται από το rDNN. Τα αριθμητικά μας αποτελέσματα καταδεικνύουν την αποτελεσματικότητα της προτεινόμενης προσέγγισης έναντι της χρήσης ενός διαφορετικού DNN για κάθε στόχο και δύο MTL μεθόδων της βιβλιογραφίας. Τέλος, το Κεφάλαιο 4 μελετά τον βέλτιστο σχηματισμό δέσμης (beamforming) ενός συστήματος πολλαπλών εισόδων-πολλαπλών εξόδων (MIMO) με κβαντισμένα διανύσματα προ/μετα-επεξεργασίας με χρήση b bit. Συγκεκριμένα, διερευνάται η χρήση του Κβαντικού Προσεγγιστικού Αλγορίθμου Bελτιστοποίησης (QAOA) καθώς και της εναλλασσόμενης βελτιστοποίησης (alternating optimization) για την επίλυση του προβλήματος βελτιστοποίησης των b-bit κβαντισμένων μετατοπιστών φάσης τόσο στον πομπό όσο και στον δέκτη. Δείχνουμε ότι η δομή αυτού του κβαντισμένου προβλήματος σχηματισμού δέσμης εναρμονίζεται φυσικά με την τεχνική QAOA, αφού τα διανύσματα προ/μετά-επεξεργασίας αντιστοιχίζονται άμεσα σε πύλες περιστροφής ενός κβαντικού κυκλώματος. Η παρούσα εργασία είναι η πρώτη που αναδυκνείει αυτή την θεωρητική σύνδεση ανάμεσα σε κβαντικά κυκλώματα και τα διανύσματα προ/μετά-επεξεργασίας, ανοίγοντας προοπτικές για εφαρμογή και σε άλλα πεδία των τηλεπικοινωνιών. Εκτός από την ανάλυση για την βελτιστοποίησης των b-bitδιανυσμάτων προ/μετά-επεξεργασίας, παρουσιάζεται και μία προσέγγιση QAOA με θερμή εκκίνηση (warm-start) για την βελτίωση της υπολογιστικής αποδοτικότητας του QAOA. Τα αριθμητικά αποτελέσματα επιβεβαιώνουν την αποτελεσματικότητα της προτεινόμενης μεθόδου στην επίτευξη βέλτιστης κβαντισμένης διαμόρφωσης δέσμης και αναδεικνύουν το κέρδος επίδοσης που προσφέρει η θερμή εκκίνηση.