ECTS - University of Pisa
| Modules | Area | Type | Hours | Teacher(s) | |
| INTELLIGENT WIRELESS TECHNOLOGIES | ING-INF/03 | LEZIONI | 60 |
|
Il corso Intelligent wireless technologies è pensato per fornire allo studente conoscenze nel campo dell'ottimizzazione per le comunicazioni wireless.
Al termine del corso lo studente avrà acquisito conoscenze relative a come formulare un problema di ottimizzazione per un sistema wireless e ai principali metodi di soluzione, ottimi ed euristici.
The Intelligent wireless technologies course is designed to provide the student with knowledge in the field of optimization for wireless communications. At the end of the course: the student will have acquired knowledge about how to formulate an optimization problem for a wireless system and the main methods for its solution, optimal and heuristic.
L'accertamento delle conoscenze sarà effettuato
The knowledge assessment will be carried out:
Al termine del corso, lo studente saprà
By the end of the course, students will be able
Le capacità degli studenti vengono testate valutando la loro partecipazione alle lezioni e affrontando insieme la risoluzionie di alcuni problemi di ottimizzazione verificando la comprensione dell'impattto sulle prestazioni di un sistema di telecomunicazioni.
The students' skills are evaluated by assessing their participation to the lessons and addresssing together the solution of different optimization problems, verifying the understanding of the impact on the performance of a telecommunications system.
Lo studente potrà acquisire e sviluppare sensibilità alle problematiche relative all'ottimizzazione di sistemi complessi anche in ambiti diversi dalle comunicazioni wireless.
The student will be able to acquire and develop awareness to issues relating to the optimization of complex systems even in areas other than wireless communications.
GLi studenti verranno organizzati in gruppi e ciascun gruppo dovrà affrontare la soluzione di uno specifico problema, appositamente disegnato per mettere alla prova il livello di maturità raggiunto.
Students will be organized into groups and each group will have to tackle the solution of a specific problem, specially designed to test the level of maturity achieved.
Per potere seguire con successo questo corso è necessario possedere una buona conoscenza dei sistemi di comunicazione wireless e solide basi di matematica e signal processsing. Conoscenze che comunque fanno parte del bagaglio culturale di uno studente di Ingegneria delle TLC al secondo anno della Laurea Magistrale.
To successfully follow this course it is necessary to have a good knowledge of wireless communication systems and a solid foundation in mathematics and signal processing. Knowledge that is in any case part of the cultural background of a TLC engineering student in the second year of the Master's Degree.
Le lezioni sono tenute con l'utilizzo di lucidi che vengono distribuiti agli studenti utilizzando l'applicativo MS onenote. Il materiale didattico (lucidi e programmi MATLAB) è messo a disposizione sul sito del corso.
The lessons are held with the use of slides that are distributed to the students using the MS onenote application. The teaching material (slides and MATLAB programs) is made available on the course website.
Introduzione al corso. Principali argomenti che verranno trattati. Modalità di esame. Evoluzione delle comunicazioni wireless attraverso le varie generazioni di telefonia mobile.
Modellizazione del canale di propagazione: large e small scale fading. Attenuazione di canale dovuta alla distanza, path-loss exponent. Attenuazione in funzione della frequenza e dimensionamento della cella in base a capacità e copertura. Small-scale fading: multipath fading e canali selettivi in frequenza. Dispersione del canale nel tempo: delay spread. Prestazioni di un sistema numerico su canale multipath.
Modulazione OFDM come risposta al multipath. Canale di propagazione modellato come tapped delay line. Convoluzione rappresentata come un prodotto matriciale con una matrice di Toepliz. Estensione ciclica del segnale tramite l'utilizzo di prefisso ciclico. Convoluzione circolare rappresentata con l'uso di una matrice circolante. Proprietà delle matrici circolanti. Architettura di trasmettitore e ricevitore OFDM.
Definizione di insieme convessi e funzioni convesse. Condizioni di convessità per funzioni differenziabili. Definizione di problema di ottimizzazione in forma standard. Problemi di ottimizzazione convessa. Lagrangiano e moltiplicatori di Lagrange. Funzione duale di Lagrange e dimostrazione della proprietà di Lower bound della Lagrangian dual function. Problema duale di Lagrange. Complementary slackness per problemi di ottimizzazione strongly dual. KKT conditions.
Problema di massimizzare il rate di un sistema OFDM in presenza d un vincolo sulla potenza complessiva. Utilizzo delle condizioni KKT per trovare la soluzone waterfilling. Methodi per calcolare il water level per l' algoritmo di waterfilling. Metodo 1: spengendo progressivamente i canali dove si trasmette con potenza negativa. Metodo 2: algoritmo della bisettrice. Realizzazione in Matlab dell'algoritmo di waterfilling. Problema di otttimizzazione duale rispetto al waterfilling classico: minimizzazione della potenza necessaria per soddisfare un vincolo sul rate. Studio della relazione tra le soluzioni del problema di massimizzazione del rate con un vincolo sulla potenza e del problema di minimizzazione della potenza con un vincolo sul rate. Soluzione in MATLAB di un problema di minimizzazione convessa vincolato.
Introduzione al problema dell'allocazione risorse in scenari multi-utente. Principali assunzioni e vincoli. Ortogonalità in frequenza dell'allocazione. Problema di allocazione max sum rate e max min rate. Soluzioni euristiche e algoritmi greedy. Metodo del gradiente per la minimizzazione di una funzione non vincolata. Utilizzo del metodo del gradiente per trovare il massimo della lagrangian dual function.Problema di allocazione risorse con proportional rate constraints. Soluzione euristica per l'allocazione delle sottoportanti. Formulazione dell'allocazione della potenza come problema convesso. Lagrangiano e gradiente del problema dell'allocazione della potenza con proportional rate constraints. Derivazione del calcolo della potenza su ciascuna sottoportante. Formulazioe del problema come un sistema di K incognite in K equazioni non-lineari. Metodo di Newton-Raphson per la soluzione di un sistema non lineare. Metodo di Newton per trovare il minimo di una funzione. Formulazione alternativa per il problema dell'allocazione con proportional rate constraints. Schema di soluzione nel dominio duale. Analisi delle prestazioni dei vari algoritmi rate adaptive al variare del numero degli utenti.
Algoritmi margin adaptive. Formulazione del problema di ottimizzazione. Rilassamento della condizione di integralità della variabile di allocazione. Dimostrazione della convessità del problema di minimizzazione della potenza con vincoli sul rate. Calcolo del Lagrangian e del gradiente. Soluzione nel dominio duale. Discussione. Algoritmo iterativo per risolver il problema WCLM. Effetto della scelta del moltiplicatore di lagrange lambda sul rate e l'allocazione di sottoportanti di un utente. Algoritmo di allocazione congiunta di rate e sottoportanti. Approccio che vede la soluzione nel dominio duale per il problema non convesso. Studio del Lagrangiano. Optimal rate allocation nel dominio duale. Definizione di problema separabile. Calcolo della Lagrangian dual function come soluzione di un problema separabile. Definizionedel subgradient for una funzione convessa (concava). Dimostrazione che il vincolo calcolato rispetto al valore delle variabili duali rappresenta un subgradiente per la Lagrangian dual function. Solutzionedel problema duale utilizzando il sub-gradiente. Realizzazione in Matlab di alcuni algoritmi di ottimizzazione. Metodo dell'ellissoide per risolvere il Lagrangian dual problem. Come inizializzare l'elissoide. Allocazione di risorse formulata come problema di linear integer programming. Allocazione risorse basata sull'utilizzo di un unico formato di modulazione con linear programming. Bipartite weighted matching. Risultati e confronti per i vari schemi di allocazione margin adaptive. Soluzione nel dominio duale del knapsack problem e implementazione in MATLAB.
Allocazione risorse nei sistemi MIMO. Allocazione ottima nel caso singolo utente. Allocazione risorse per sistemi MIMO multi-user. Allocazione margin adaptive per sistemi MIMO. Block diagonalization precoding: matrice dell'interferenza, decomposizione a valori singolari e matrice equivalente di canale. Distribuzione ottima della potenza. Soluzione del problema MIMO margine adaptive nel dominio duale. Implementazione in Matlab del problema di allocazione singolo utente con precoder zero-forcing e con SVD e waterfilling. Algoritmo semplificato per sistemi MIMO broadcast: assegnazione sequenziale di canale. Sbiancamento della matrice dell'interferenza. Allocazione ottima in presenza di interferenza. Riformulazione del proble SCA con linear programming. Risultati e confronto tra i vari algoritmi.
MIMO intereference channel. Formulazione del problema sum-rate. Ricevitore MIMO MSE. Pre-codifica e filtraggio MSE. Coordinate descent method. Algoritmo iterativo BCDper la minimizzazione del MSE in un sistema MIMO. Definizione del problema di ottimizzazione WMMSE. Gradiente del determinante e della traccia. Formule aggiornate al caso WMMSE dei filtri di ricezione e pre-codifica. Soluzione alla convergenza del problema WMMSE. Equivalenza tra problema WMMSE e sum-rate maximization.
Comunicazioni D2D: canale sidelink. Potenziali applicazioni di D2D in una rete 5G. Modalità di utilizzo D2D: trasmissioni underlay e overlay. Allocazione di potenza in modalità overlay. Introduzione alla teoria dei giochi e ai giochi potenziali. Best e better response dynamics. Allocazione di potenza formulata come gioco potenziale. Allocazion best response. Allocazione better response. Linearizzazione di parte della funzione obiettivo. Dimostrazione che la soluzione del problema di allocazione di potenza linearizzato è una better response per il problema originale della massimizzazione del rate in un sistema D2D. Soluzione del problema di massimizzazione del rate globale linearizzato nella funzione convessa. Interpretazione del significato dei termini lineari rispeto al problema di ottiizzazione rilassato. Allocazione di potenza in 'reuse mode'. Definizione dei vincoli addizionali. Studio di un bound per il problema dell'allocazione D2D in 'reuse mode'. Studio del problema rilassato nel dominio duale. Formulazione del Lagrangian dual problem e algoritmo iterativo su due livelli risolto col metodo dell'ellissoide. Risultati per un sistema D2D. Confronto delle prestazioni di D2D in 'dedicated mode' e in 'reuse mode'.
Introduction to the course. Main topics that will be treated.
Evolution of wireless communications through the various generations of mobile telephony. Modeling of the propagation channel: large and small scale fading. Channel attenuation due to distance, path-loss. Attenuation as a function of frequency and cell sizing. Small-scale fading: multipath fading and frequency selective channels. Channel dispersion over time: delay spread. Performance of a numerical system on multipath channel. OFDM modulation as a response to multipath. Propagation channel modeled as a tapped delay line. Convolution represented as a matrix product with a Toepliz matrix. Cyclical extension of the signal through the use of a cyclic prefix. Circular convolution represented with the use of a circulating matrix. Properties of circulating matrices. OFDM transmitter and receiver architecture. Definition of convex sets and convex functions. Convexity conditions for differentiable functions. Definition of optimization problem in standard form. Convex optimization problems. Lagrangian and Lagrange multipliers. Dual Lagrange function and proof of the lower bound property of the Lagrangian dual function. Dual Lagrange problem. Complementary slackness for strongly dual optimization problems. KKT conditions. Problem of maximizing the rate of an OFDM system in the presence of a constraint on the overall power. Use of KKT conditions to find the waterfilling solution. Methods to calculate the water level for the waterfilling algorithm. Method 1: progressively turning off the channels where it is transmitted with negative power. Method 2: bisection algorithm. Implementation of the waterfilling algorithm in Matlab. Dual optimization problem compared to classic waterfilling: minimization of the power necessary to satisfy a constraint on the rate. Study of the relationship between the solutions of the rate maximization problem with a constraint on the power and of the power minimization problem with a constraint on the rate. MATLAB solution of a constrained convex minimization problem. Introduction to the problem of resource allocation in multi-user scenarios. Main assumptions and constraints. Frequency orthogonality of the allocation. Max sum rate and max min rate allocation problems. Heuristic solutions and greedy algorithms. Gradient method for minimizing an unconstrained function. Using the gradient method to find the maximum of the lagrangian dual function. Resource allocation problem with proportional rate constraints. Heuristic solution for the allocation of sub-carriers. Formulation of power allocation as a convex problem. Lagrangian and gradient of the power allocation problem with proportional rate constraints. Formulation of the problem as a system of K unknowns in K non-linear equations. Newton-Raphson method for the solution of a non-linear system. Newton's method for finding the minimum of a function. Alternative formulation for the allocation problem with proportional rate constraints. Solution scheme in the dual domain. Performance analysis of the various rate adaptive algorithms as the number of users varies. Margin adaptive algorithms. Formulation of the optimization problem. Relaxation of the integral condition of the allocation variable. Proof of the convexity of the power minimization problem with rate constraints. Calculation of the Lagrangian and the gradient. Dual domain solution. Iterative algorithm to solve the WCLM problem. Effect of the choice of the lambda lagrange multiplier on the rate and allocation of sub-carriers of a user. Joint allocation algorithm of installments and sub-carriers. Approach that sees the solution in the dual domain for the non-convex problem. Study of the Lagrangian. Optimal rate allocation in the dual domain. Definition of separable problem. Computation of the Lagrangian dual function as a solution of a separable problem. Definition of the subgradient for a convex (concave) function. Proof that the constraints computed with respect to the value of the dual variables represent a subgradient for the Lagrangian dual function. Solution of the dual problem using the sub-gradient. Realization in Matlab of some optimization algorithms. Ellipsoid method to solve the Lagrangian dual problem. How to initialize the ellipsoid. Resource allocation formulated as a linear integer programming problem. Resource allocation based on the use of a single modulation format with linear programming. Bipartite weighted matching. Results and comparisons for the various schemes. Dual domain solution of the knapsack problem and implementation in MATLAB. Resource allocation in MIMO systems. Optimal allocation in the single user case. Resource allocation for multi-user MIMO systems. Margin adaptive allocation for MIMO systems. Block diagonalization precoding: interference matrix, singular value decomposition and equivalent channel matrix. Optimal power distribution. Solution of the MIMO adaptive margin problem in the dual domain. Implementation in Matlab of the single user allocation problem with zero-forcing precoder and with SVD and waterfilling. Simplified algorithm for broadcast MIMO systems: sequential channel assignment. Interference matrix whitening. Optimal allocation in the presence of interference. Reformulation of the SCA problem with linear programming. Results and comparison between the various algorithms. MIMO intereference channel. Formulation of the sum-rate problem. MSE MIMO Receiver. MSE pre-coding and filtering. Coordinate descent method. BCD iterative algorithm for minimizing the MSE in a MIMO system. Definition of the WMMSE optimization problem. Gradient of the determinant and of the trace. Formulas updated to the WMMSE case of reception and pre-encoding filters. Solution to the convergence of the WMMSE problem. Equivalence between WMMSE problem and sum-rate maximization. D2D communications: sidelink channel. Potential applications of D2D in a 5G network. How to use D2D: underlay and overlay broadcasts. Power allocation in overlay mode. Introduction to game theory and potential games. Best and better response dynamics. Power allocation formulated as potential game. Best response allocation. Better response allocation. Linearization of part of the objective function. Proof that the solution of the linearized power allocation problem is a better response to the original problem of rate maximization in a D2D system. Solution of the maximization problem of the linearized global rate in the convex function. Interpretation of the meaning of linear terms with respect to the relaxed optimization problem. Power allocation in 'reuse mode'. Definition of additional constraints. Study of a bound for the D2D allocation problem in 'reuse mode'. Study of the relaxed problem in the dual domain. Formulation of the Lagrangian dual problem and iterative algorithm on two levels solved with the ellipsoid method. Results for a D2D system. Performance comparison of D2D in 'dedicated mode' and in 'reuse mode'.
Dimitri P. Bertsekas. Nonlinear Programming, Athena Scientific, 2016.
Stephen P. Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004.
Dimitri P. Bertsekas. Nonlinear Programming, Athena Scientific, 2016.
Stephen P. Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004.
L'esame è composto da una prova orale che richiede la consegna di un eleaborato. Il voto finale terrà conto del livello di partecipazione alle lezioni.
The exam consists of an oral test that requires the delivery of an eleaborate. The final grade will take into account the level of participation in the lessons.
