Universit`a degli Studi di Pisa
Dipartimento di Ingegneria dell’Informazione Corso di Laurea Magistrale in Ingegneria delle Telecomunicazioni
Algoritmi di allocazione di potenza per
sistemi full duplex in reti 5G
Candidato: Fabio Saggese
Matricola 491685
Relatori:
Ing. Marco Moretti Prof. Andrea Abrardo
Ai miei genitori, che sempre mi hanno supportato, nei miei percorsi, lineari o tortuosi, nelle mie scelte, giuste o sbagliate.
Abstract
Le trasmissioni full-duplex wireless sono una delle tecnologie di maggiore interesse per un possibile utilizzo nelle reti di nuova generazione 5G. Il lavoro di tesi si è concentrato sullo sviluppo di due algoritmi di allocazione risorse per comunicazioni full-duplex wireless in femtocelle poste all’interno di reti etero-genee (HetNets). Il primo algoritmo ha come obiettivo la massimizzazione del throughput totale della cella, con un vincolo sulla massima potenza trasmessa, mentre il secondo algoritmo ha come scopo la minimizzazione della potenza complessiva trasmessa, vincolata al raggiungimento di una minima efficienza spettrale per ogni utente nella cella. L’allocazione delle risorse è effettuata in modo congiunto per dispositivi uplink e downlink in entrambi gli algoritmi. I problemi di ottimizzazione sono stati risolti tramite la formalizzazione del problema duale Lagrangiano e l’utilizzo della concave-convex procedure che permette, attraverso un algoritmo iterativo, l’approssimazione di particolari problemi non-convessi in problemi convessi. I risultati ottenuti dimostrano l’effettivo miglioramento dell’efficienza spettrale ed energetica rispetto ai sistemi di trasmissione half-duplex classici.
Indice
1 Introduzione 1
2 Tecnologia Full-Duplex 3
2.1 Introduzione al Full-Duplex . . . 4
2.2 Cancellazione della self-interference . . . 5
2.3 Reti cellulari e scenari di utilizzo . . . 8
3 Allocazione risorse 13 3.1 Problemi di ottimizzazione . . . 14
3.1.1 Ottimizzazione in forma canonica . . . 14
3.1.2 Insiemi e funzioni convesse . . . 15
3.1.3 Ottimizzazione convessa . . . 17
3.1.4 Lagrangiana e problema duale . . . 18
3.2 Allocazione di potenza . . . 21
3.2.1 Formalizzazione dei problemi . . . 21
3.2.2 Metodi di risoluzione . . . 23
3.2.3 Duality gap . . . 24
4 Algoritmi di allocazione sviluppati 27 4.1 Scenario . . . 27
4.2 Algoritmo a massimo rate . . . 29
4.2.1 Problema di ottimizzazione . . . 29
4.2.2 Risoluzione del primale . . . 31
4.2.3 Risoluzione del duale . . . 38
4.3 Algoritmo a minima potenza . . . 39
4.3.1 Problema di ottimizzazione . . . 39
4.3.2 Risoluzione del primale . . . 41
4.3.3 Risoluzione del duale . . . 46
5 Simulazioni e Risultati 49 5.1 Generazione scenario di simulazione . . . 49
vi INDICE 5.2 Algoritmo a massimo rate . . . 50 5.3 Algoritmo a minima potenza . . . 56
Capitolo 1
Introduzione
Negli ultimi anni, l’aumento esponenziale dei dispositivi connessi alla rete ha portato alla necessità di sviluppare tecnologie per le trasmissioni dei dati sempre più efficienti. Come se non bastasse, l’avvento del 5G e dell’Internet of Things (IoT), con la conseguente connessione di ogni dispositivo a internet, genererà un una crescita ancora maggiore dell’utilizzo della rete e delle risorse radio a disposizione, ad ora molto limitate.
Allo stesso tempo, un problema presente è la riduzione della potenza spesa per la trasmissione di informazioni. Questo è particolarmente importante per le comunicazioni wireless, poiché un basso consumo energetico è fondamentale per l’autonomia dei dispositivi mobili.
Per rispondere a queste esigenze, limitando inoltre grossi investimenti infrastrutturali, è stato introdotto il concetto di reti eterogenee (HetNets). Queste reti sono composte da celle di piccole dimensioni, con relativi access-point, inserite all’interno delle attuali reti cellulari, ribattezzate macrocelle. In questo modo le distanze dei dispositivi mobili rispetto all’access-point sono minori, permettendo di sfruttare più efficientemente le risorse frequenziali disponibili.
L’adozione di celle di piccole dimensioni, dette pico e femtocelle, rende possibile l’utilizzo di tecniche di trasmissione full-duplex, che permettono l’utilizzo simultaneo della stessa risorsa frequenziale in trasmissione e ricezione. Il funzionamento di questa tecnologia è subordinato all’utilizzo di metodi di cancellazione dell’interferenza, non attuabili in celle di grandi dimensioni a causa di attenuazioni di canale troppo elevate, e ad una corretta allocazione della potenza trasmessa dai terminali su porzioni della banda disponibile, in modo da limitare l’interferenza generata dalla coesistenza di più segnali utili sulla stessa banda e garantire un aumento della capacità di canale rispetto ai sistemi convenzionali. L’introduzione di tecnologie full-duplex può portare a un guadagno tale da raddoppiare la capacità di canale, a parità di banda
2 CAPITOLO 1. INTRODUZIONE disponibile. Per questo il full-duplex viene indicato da molti come una delle tecnologie strategiche per le reti 5G.
Il lavoro di tesi svolto si è concentrato sulla risoluzione dei problemi di massimizzazione della capacità di canale e della minimizzazione della potenza spesa tramite la creazione di algoritmi di allocazione di potenza in femtocelle con sistemi di trasmissione full-duplex.
Questa tesi è organizzato nel seguente modo. Nel capitolo 2 viene descritto il funzionamento dei sistemi di trasmissione full-duplex, ponendo particolare attenzione ai vantaggi, rispetto ai convenzionali sistemi half-duplex in termini di velocità di trasmissione ed efficienza energetica, e ai limiti tecnologici esistenti. Nel del capitolo 3 vengono dapprima descritte le basi per la risolu-zione di problemi di ottimizzarisolu-zione, necessari per lo sviluppo di tecniche di allocazione di potenza, e in seguito vengono presentati i problemi di alloca-zione di potenza per sistemi multiutente. Il capitolo 4 presenta la descrialloca-zione dettagliata dei due algoritmi di allocazione di potenza proposti per sistemi full-duplex: la prima parte del capitolo sarà concentrata sulla risoluzione del problema di massimo rate, mentre la seconda parte sarà sulla risoluzione del problema di minima potenza spesa. Il capitolo 5 presenta i risultati ottenuti per i due algoritmi mettendo in luce le potenzialità e i limiti degli stessi, tramite un confronto con le trasmissioni half-duplex e con altri algoritmi full-duplex presenti in letteratura. Infine, le conclusioni addotte sono inserite nel capitolo 6.
Capitolo 2
Tecnologia Full-Duplex
“It is generally not possible for radios to receive and transmit on the same frequency band because of the interference that results.” - Andrea Goldsmith, Wireless Communications, 2005.
La tecnologia full-duplex viola questo principio che da anni domina nelle comunicazioni wireless. Il full-duplex si basa infatti sulla trasmissione e ricezione sulla stessa risorsa in modo da aumentare l’efficienza spettrale. Con questa tecnologia, in teoria, è possibile raddoppiare la capacità di canale a parità di banda occupata. Il concetto deriva direttamente dalla definizione di duplex, collegamento bidirezionale tra due parti o dispositivi, definito istantaneo nel caso di presenza del prefisso full. Questo tipo di comunicazione può essere normalmente adoperata nel caso di collegamenti cablati tra i due dispositivi, che possono scambiarsi dati nelle due direzioni senza che l’interferenza sia talmente elevata da limitare la capacità dei dati trasmessi. Maggiore difficoltà di implementazione è data dal full-duplex wireless, che intrinsecamente è soggetto a forte interferenza per la coesistenza temporale nello stesso mezzo di comunicazione dei due segnali trasmessi, non ortogonali in frequenza. Per questo è fondamentale attuare tecniche di cancellazione dell’interferenza e di allocazione di potenza dei dispositivi in trasmissione, razionalizzando le potenze in gioco. Le successive sezioni descriveranno il funzionamento generale del full-duplex con particolare riferimento alle tecniche che permettono un effettivo aumento della capacità trasmissiva. In seguito verrà presentata una panoramica sulle tecniche di riduzione dell’interferenza e infine verrà descritta la topologia di utilizzo per le reti cellulari, utilizzata in seguito per gli algoritmi descritti al capitolo 4.
4 CAPITOLO 2. TECNOLOGIA FULL-DUPLEX
2.1
Introduzione al Full-Duplex
Come già detto, il concetto di base della comunicazione full-duplex (FD) è quello di utilizzare un nodo di un sistema wireless contemporaneamente in trasmissione e in ricezione nello stesso tempo (in time full-duplex) e/o nella stessa banda (in band full-duplex) permettendo, in teoria, un raddoppio della capacità di canale a parità di banda rispetto a un sistema half-duplex (HD) classico, cioè un sistema in cui le risorse sono allocate in modo ortogonale.
La teoria dell’informazione e in particolare il teorema di Shannon-Hartley, mostrano che la capacità di canale ottenibile in un sistema è funzione del rapporto segnale rumore interferente. In un sistema full-duplex, l’interferenza generata dalla co-presenza di segnale trasmesso e ricevuto alla stessa frequenza influisce molto sul valore di questo rapporto.
Figura 2.1: Schema di principio di due dispositivi SISO in comunicazione tra loro. Il canale è considerato stazionario per la durata della comunicazione e piatto in frequenza sulla banda d’interesse.
Per capire il concetto consideriamo una coppia di dispositivi SISO, visua-lizzabili in figura 2.1, immersi in un canale stazionario e piatto in frequenza. Nel caso in cui si utilizzino tecnologie half-duplex e supponendo di poter allocare tutta la banda disponibile a un solo dispositivo, si otterrà un sistema con multiplazione a divisione di tempo. Immaginiamo che all’istante t = 0 e per tutta la durata della trasmissione dei dati, il dispositivo A trasmetta e il dispositivo B riceva. Il rapporto segnale rumore interferente al dispositivo B risulta:
SINRHDB = |c(f )|
2p
A
σ2 (2.1)
dove c(f ) ∈ C è il coefficiente di canale nella banda allocata comprensivo di path loss, pA è la potenza trasmessa dal dispositivo A e σ2 è la potenza di
rumore in banda.
Nel caso in cui vengano utilizzate tecnologie full-duplex, i due dispositivi, a cui verrà allocata interamente la banda, trasmetteranno simultaneamente. In questo caso il rapporto segnale rumore interferente al dispositivo B sarà
2.2. CANCELLAZIONE DELLA SELF-INTERFERENCE 5 pari a [2]: SINRF DB = |c(f )| 2p A hsipB+ σ2 (2.2) dove i termini aggiunti rispetto all’equazione 2.1 sono: pB, potenza trasmessa
dal dispositivo B e hsi, guadagno di canale, in modulo quadro, generato tra il
trasmettitore del dispositivo B e il ricevitore dello stesso. Quest’ultimo canale è denominato self-interference, o auto-interferenza.
A parità di banda occupata, di guadagno di canale e di potenza di rumore si ottiene:
SINRHD ≥ SINRF D (2.3)
che vale con il segno di uguaglianza nel caso in cui pB = 0, riportando
il sistema a lavorare in modalità HD, o se hsi = 0, che prevederebbe una
cancellazione totale del canale interferente, tecnologicamente non realizzabile. Consideriamo ora le capacità di canale ottenute. Per il sistema half-duplex la capacità per la trasmissione dei dati risulta:
CHD = log2(1 + SINR
HD
B ). (2.4)
La capacità di canale del sistema full-duplex, che trasmette simultaneamente nelle due direzioni, risulta invece:
CFD = log2(1 + SINR
F D
A ) + log2(1 + SINR
F D
B ), (2.5)
dove SINRF DA è il rapporto segnale rumore interferente al dispositivo A, di forma analoga alla 2.2.
Dalla trattazione precedente si intuisce che, a seconda dei valori coinvolti, non sempre si ottiene un guadagno tale da preferire la comunicazione FD a quella HD. Sono quindi necessarie, da una parte tecniche di riduzione dell’interferenza in ogni nodo full-duplex, i cui metodi sono presentati in sezione 2.2, e dall’altra tecniche di allocazione di potenza per limitare l’impatto dell’interferenza residua. Infine, è importante notare che anche il valore di path loss influisce fortemente al corretto funzionamento del sistema. Per questo motivo è necessario l’utilizzo di topologie che prevedano brevi distanze tra dispositivi che operano il modalità full-duplex, come dimostrato in sezione 2.3.
2.2
Cancellazione della self-interference
Uno dei processi fondamentali per il funzionamento della tecnologia full-duplex è l’utilizzo di tecniche per la riduzione della self-interference, interferenza generate dal terminale full-duplex verso sé stesso nel momento in cui si trasmette e riceve sullo stesso canale.
6 CAPITOLO 2. TECNOLOGIA FULL-DUPLEX Per i limiti tecnologici dei ricevitori, la maggior parte del processo di cancellazione deve essere effettuato a monte del convertitore analogico-digitale (ADC ). La causa principale, è data dal range dinamico effettivo dell’ADC, collo di bottiglia del sistema. Possiamo giustificare tale affermazione tramite l’Effective number of bits (ENOB), parametro che dà una misura del range dinamico effettivo. Tramite la regola dei 6dB, e considerando che sono neces-sari almeno 2 bit di guardia per evitare saturazioni dell’ADC [3], l’effettivo range dinamico di un convertitore risulta:
DRdB ' 6, 02 (ENOB − 2). (2.6)
Per cui, anche ipotizzando una perfetta cancellazione dell’interferenza nel dominio digitale, il rumore di quantizzazione residuo sarà inferiore di DRdB
al segnale interferente ricevuto. A questo punto è importante considerare che la potenza ricevuta dal segnale interferente è a un livello molto più elevato rispetto alla potenza ricevuta da un altro terminale, poiché trasmettitore e ricevitore si trovano all’interno dello stesso dispositivo. Quindi, al contrario di un segnale ricevuto a bassa potenza, il segnale interferente convertito in digitale contribuisce all’aumento dell’errore di quantizzazione che, supe-rando la soglia di rumore, non permette al sistema ricevente di funzionare correttamente.
Per dare un’idea del valore di rumore risultante, consideriamo un con-vertitore commerciale con 14 bit di risoluzione e con EN OB@20MHz ' 11 bit [4]. Tramite la 2.6 si ottiene un range dinamico di circa 54 dB. Quindi, per un segnale interferente ricevuto con potenza pari a 0 dBm si ha un livello di rumore residuo a monte della cancellazione di -54 dBm, ben oltre la soglia di rumore di dispositivi wireless odierni, che per una banda di lavoro di 20 MHz, si attesta a circa -100 dBm1.
La tecnologia attuale non permette un grande miglioramento del range dei convertitori analogici-digitali rispetto ai valori sopra riportati e quindi la maggior parte della riduzione della self-interference viene effettuata con tecniche attuate a monte dell’ADC [3], [5].
La prima parte della riduzione viene effettuata nel dominio di propagazione (Propagation-Domain), cioè si limita l’interferenza a livello elettromagnetico. Tramite l’aumento di path loss, diversa polarizzazione e direttività delle antenne per un sistema separed-antenna, o con l’utilizzo di un circolatore per sistemi shared-antenna, è possibile limitare la potenza interferente [5]. La debolezza di questa tecnica è l’impossibilità di riduzione della reflect-path self-interference, cioè dell’auto-interferenza dovuta alle riflessione del segnale
1Calcolo effettuato tenendo conto di una temperatura ambiente a cui è sottoposto il
2.2. CANCELLAZIONE DELLA SELF-INTERFERENCE 7 trasmesso su ostacoli, che rientra in parte nel ricevitore. Infatti, in questo dominio non è possibile discriminare il contributo dell’interferenza diretta da quello dell’interferenza riflessa.
Figura 2.2: Esempio di tecniche di posizionamento delle antenne per la riduzione dell’interferenza nel dominio di propagazione, proposta nell’articolo [5].
La seconda parte di soppressione dell’interferenza può essere effettuata nel dominio analogico (Analog Circuit Domain). L’idea è quella di cancellare l’interferenza prendendo una porzione di segnale trasmesso per poi sottrarlo al segnale ricevuto nel punto più vicino possibile all’antenna. È possibile applicare questa tecnica completamente in analogico ottenendo una minore influenza da eventuali distorsioni non lineari dovute agli amplificatori di potenza e dal rumore di fase, ma che richiede una complicata elaborazione del segnale analogico che per alcuni sistemi, soprattutto a larga banda, è proibitiva. Un altro approccio è quello di elaborare il segnale da sottrarre nel dominio digitale, così da poter considerare anche l’eliminazione dell’interferenza riflessa, per poi convertire il segnale in analogico e quindi sottrarlo al segnale ricevuto. In questo caso l’elaborazione del segnale risulta molto più semplice a costo di una minore precisione della soppressione limitata dalla conversione digitale-analogico [6].
L’ultima parte della soppressione può adesso essere effettuata nel dominio digitale (Digital Domain), a valle dell’ADC. La potenza interferente residua è adesso sufficientemente bassa da non generare aumenti della soglia di rumore, dovuti all’errore di quantizzazione. La soppressione avviene tramite la formalizzazione di un sistema digitale in banda base equivalente che comprenda tutta la catena del segnale tra il DAC e l’ADC e modelli le trasformazioni dello stesso, così da poter ricavare l’interferenza residua da eliminare. Il tipo di modello dipende dalla tipologia del sistema [7].
Lo stato dell’arte attuale sulla riduzione dell’interferenza porta a una attenuazione della stessa di circa 110 dB rispetto al segnale ricevuto. Questa è una buona soppressione per celle di piccolo raggio, dove l’interferenza risulta abbattuta fino al livello di rumore [3].
8 CAPITOLO 2. TECNOLOGIA FULL-DUPLEX
Figura 2.3: Schema di principio dei tre domini di cancellazione per una corretta cancellazione dell’auto-interferenza, presentata in [3].
2.3
Reti cellulari e scenari di utilizzo
La cancellazione dell’interferenza è necessaria al funzionamento corretto del full-duplex, come descritto in sezione 2.1. Inoltre, come presentato nella sezione precedente, si evince la complessità tecnologica necessaria per l’attuazione dei processi di riduzione della self-interference, rendendo solo alcune tipologie di dispositivi in grado di essere equipaggiati con transceiver full-duplex. Il compito di utilizzare il paradigma full-duplex viene quindi demandato a dispositivi centrali in un sistema radiomobile, che abbiano spazio fisico per la struttura hardware e siano dotati di maggiori capacità di elaborazione dei dati rispetto ad altri dispositivi.
La topologia di nostro interesse è quella che impiega l’utilizzo di reti cellulari, di cui uno schema di principio è visibile in figura 2.4. In questa particolare topologia l’unico elemento full-duplex è la stazione base (BS) mentre i dispositivi mobili hanno sistemi di trasmissione half-duplex. Per i nostri scopi è stata considerata la tecnica OFDMA come tecnica di accesso multiplo.
Consideriamo la cella in un singolo istante, nel quale saranno presenti M utenti uplink (UU ) e N utenti downlink (DU ). Supponiamo inoltre che la cella abbia a disposizione K sottoportanti disponibili da allocare.
Consideriamo che il canale sia piatto in frequenza, su ogni sottoportante, e stazionario, ottenendo quindi, per ogni k, M guadagni di canale in uplink, N guadagni di canale in downlink, un unico guadagno di canale dovuto alla cancellazione dell’interferenza, N × M guadagni di canale interferenti tra
2.3. RETI CELLULARI E SCENARI DI UTILIZZO 9
Figura 2.4: Schema di principio per una rete cellulare che utilizza il paradigma full-duplex per la comunicazione tra utenti [12].
gli utenti in uplink e gli utenti in downlink. La visualizzazione grafica di questi canali è visibile in figura 2.4. Per semplicità di notazione consideriamo i valori in modulo quadro dei singoli guadagni di canale definendo hUm,k, hD
n,k, hsik, hm,n,k, rispettivamente, i moduli quadri dei guadagni in uplink,
downlink, cancellazione della self-interference e l’interferenza mutua tra utenti uplink e utenti downlink. Definiamo inoltre la potenze trasmessa dall’m-esimo utente uplink verso la BS sulla sottoportante k come pU
m,k, mentre la potenze
trasmessa dalla BS verso l’n-esimo utente in downlink sulla sottoportante k come pDn,k.
I rapporti segnale rumore interferente in uplink, calcolati alla BS per ogni sottoportante, risultano:
SINRUm,k = h
U m,kpUm,k
σ2+P
i6=mhUi,kpUi,k + hsik
P
npDn,k
, m = 1, . . . , M,
k = 1, . . . , K, (2.7)
dove σ2 rappresenta la potenza di rumore. Si noti come l’SINR per
m-esimo utente sulla k-esima sottoportante diminuisca all’aumentare del numero di utenti uplink e del numero di utenti downlink a cui è stata allocata la sottoportante k.
In downlink, il rapporto segnale rumore interferente all’n-esimo utente downlink sulla sottoportante k risulta:
SINRDn,k = h
U n,kpDn,k
σ2+P
i6=nhUi,kpDi,k+
P
mhm,n,kpUm,k
, m = 1, . . . , M,
k = 1, . . . , K, (2.8)
dove σ2 rappresenta la potenza di rumore. Similmente al caso precedente,
all’aumentare di utenti a cui è allocata la k-esima sottoportante il valore dell’SINR diminuisce.
10 CAPITOLO 2. TECNOLOGIA FULL-DUPLEX Dalle equazioni 2.7 e 2.8 si nota come una corretta allocazione delle sotto-portanti sia necessaria all’ottenimento di rapporti segnali rumore interferente tali da consentire un sostanziale aumento della capacità di canale. Parallela-mente alla allocazione delle risorse spettrali, deve essere correttaParallela-mente gestita la potenza trasmessa per ogni utente e su ogni sottoportante. Senza entrare in ulteriori dettagli sull’allocazione di potenza, che verranno descritti nel capitolo 3, è importante notare che un metodo per allocare correttamente le risorse è quello di creare coppie di utenti uplink-downlink che condividano la stessa sottoportante, facendo in modo che ogni sottoportante venga assegnata al più a una sola coppia. In questo modo i rapporti segnali rumore interferente diventano, rispettivamente per uplink e downlink:
SINRUm,k = h U m,kpUm,k σ2+ hsi k pDn,k , (2.9) SINRDn,k = h D n,kpDn,k σ2+ h m,n,kpUm,k . (2.10)
Valutando numericamente i termini delle precedenti espressioni è possibi-le determinare delpossibi-le caratteristiche fisiche della cella necessarie al corretto funzionamento del full-duplex.
Consideriamo l’equazione 2.9 e trascuriamo il termine di rumore. Come già detto in sezione 2.2, lo stato dell’arte sulla cancellazione dell’interferenza permette una riduzione della stessa di 110 dB. A parità di potenza trasmessa dall’m-esimo utente e dalla BS, per ottenere un rapporto segnale rumore interferente maggiore di 1 è necessario che il valore del guadagno di canale uplink sia almeno maggiore di −110 dB. Questo si traduce su un vincolo sulla distanza massima tra i due terminali. Considerando un fading di Rayleigh, il guadagno di canale vale:
hUm,k = |w + jz|
2
2PLm,k
, con w, z ∈ N (0, 1) i.i.d. (2.11)
dove la path loss lineare tra m-esimo utente e BS è definita come: PLm,k = Dηm−BS GmGBS 4π λk 2 (2.12) dove Dm−BS è la distanza tra l’m-esimo utente uplink e la BS, η è il path loss
exponent relativo all’ambiente di propagazione del segnale, Gm è il guadagno
d’antenna del dispositivo uplink, GBS è il guadagno d’antenna della BS, λk è
2.3. RETI CELLULARI E SCENARI DI UTILIZZO 11 Considerando il valor medio statistico del guadagno di canale uplink la relazione da rispettare è la seguente:
E{hUm,k} = 1 PLm,k = GmGBS Dηm−BS λ k 4π 2 ≤ 10−11 = E{hsik} (2.13)
che risolta rispetto alla distanza porta alla relazione
Dm−BS ≤ η s GmGBS 10−11 λ k 4π 2 . (2.14)
Considerando delle semplici antenne a bipolo con guadagno G = 2.15 dB, una sottoportante alla frequenza di 2 GHz e un path loss exponent η = 4 si ottiene che, in media, la minima distanza che porta ad ottenere un SINR maggiore di 1 è pari a circa 80 metri. Questo risultato mette alla luce la necessità di utilizzare celle di piccole dimensioni affinché la tecnologia duplex possa funzionare correttamente. Per questo, l’utilizzo del full-duplex è confinato all’interno di pico o femtocelle, celle di piccole dimensioni inserite all’interno delle celle cellulari classiche, chiamate macrocelle, di cui condividono le risorse disponibili. Le reti di questo tipo vengono chiamate reti eterogenee (Heterogeneous Networks) e sono una delle tecnologie pensate per essere utilizzate per la prossima generazione di reti radiomobili 5G [8].
Capitolo 3
Allocazione risorse
L’allocazione, da dizionario il “sistemare ordinatamente più cose in un certo ambito disponibile, spaziale o temporale o di altra natura”, è, per i nostri scopi, la distribuzione di risorse limitate all’interno di un sistema. A seconda delle necessità e degli obiettivi si potrà definire una allocazione ottima, cioè quella che si avvicina di più agli obiettivi, tenuto conto delle risorse disponibili. Già nelle prime righe di questo capitolo emerge quindi il concetto di ottimizzazione dell’allocazione, concetto fondamentale in molte branche di studio e anche per la risoluzione dei problemi presentati.
Come è già stato più volte affermato, un corretto metodo di allocazione delle risorse è necessario affinché i sistemi full-duplex funzionino e ci sia quel tanto agognato raddoppio della capacità di trasmissione. In particolare per sistemi di nostro interesse si parla di allocazione di potenza, visto che è proprio la potenza da trasmettere a venire distribuita tra i dispositivi. L’obiettivo è scelto da chi formalizza il problema a seconda delle necessità e dell’utilizzo del sistema. Come sarà più chiaro in seguito, per uno stesso sistema è possibile formalizzare più problemi di allocazione con diversi obiettivi, come ad esempio il raggiungimento della massima capacità di trasmissione o il minimo utilizzo di potenza.
In questo capitolo viene discussa la teoria dei problemi di allocazione risorse. La prossima sezione presenta la descrizione formale dei problemi di ottimizzazione. Le basi teoriche presentate verranno poi utilizzate per la descrizione del problema di allocazione di potenza per comunicazioni multi utente.
14 CAPITOLO 3. ALLOCAZIONE RISORSE
3.1
Problemi di ottimizzazione
Ogni problema di allocazione è in sostanza un particolare problema di otti-mizzazione, per cui si cerca una soluzione che renda minima o massima una funzione tenendo conto dei vincoli strutturali delle risorse.
L’intera sezione è dedicata alla teoria matematica dei problemi di otti-mizzazione, di cui verrà presentata una panoramica delle definizioni e delle proprietà fondamentali. Questa sezione contiene tutte le basi necessarie alla comprensione di tutte le sezioni successive in questo lavoro.
3.1.1
Ottimizzazione in forma canonica
Iniziamo con la definizione formale di un problema di ottimizzazione. Data una funzione da ottimizzare nota f0 : Rn → R dipendente dalla varibile x ∈ Rn,
date m funzioni fi : Rn→ R con i = 1, . . . , m e date p funzioni hi : Rn → R
con i = 1, . . . , p, un problema di ottimizzazione in forma canonica è: min f0(x), fi(x) ≤ 0, i = 1, . . . , m, hi(x) = 0, i = 1, . . . , p, (3.1)
dove f0 è detta funzione obiettivo o di costo, le fi sono le funzioni di vincolo
di disuguaglianza, mentre le hi sono le funzioni di vincolo di uguaglianza. Se
p = m = 0 il problema è non vincolato. Il vettore x ∈ Rn è detto variabile di ottimizzazione.
Possiamo definire il dominio del problema di ottimizzazione come l’insieme dei punti per i quali la funzione obiettivo e le funzioni di vincolo sono definite, e cioè: D = m \ i=0 dom fi∩ p \ i=1 dom hi. (3.2)
Una qualsiasi variabile x ∈ D è detta ammissibile (feasible) se soddisfa tutti i vincoli del problema. È possibile definire l’insieme dei vincoli come feasible set, la cui espressione è la seguente:
F = {x ∈ D | fi(x) ≤ 0, i = 1, . . . , m; hi(x) = 0, i = 1, . . . , p}, (3.3)
che può essere anche visto come intersezione tra D e gli m + p insiemi definiti dalle funzioni di vincolo. Il problema è risolvibile solo se F è non nullo.
Si definisce p∗ il valore ottimo della funzione obiettivo, definito come: p∗ = inf
3.1. PROBLEMI DI OTTIMIZZAZIONE 15 che è pari a p∗ = ∞ nel caso in cui il feasible set sia nullo.
Si definisce x∗ ∈ Rn come variabile ottima se x∗ appartiene al feasible set
e se è la variabile che minimizza la funzione obiettivo, cioè la variabile per cui f0(x∗) = p∗. L’insieme di tutte le variabili ottime è detto insieme ottimo
ed è definito come:
Xopt = {x | x ∈ F , f (x) = p∗}. (3.5)
Se Xopt è vuoto si dice che il valore ottimo non è ottenibile, altrimenti il
problema è risolvibile. Tutte le variabili che appartengono a Xopt sono dette
ottimi globali.
Non sempre è possibile ottenere un ottimo globale e per questo è possibile definire le variabili ottime locali, cioè quelle variabili x ∈ F per cui vale:
f0(x) = infy {f0(y) | y ∈ F , ||y − x||2 ≤ }, > 0. (3.6)
3.1.2
Insiemi e funzioni convesse
Per i problemi di interesse in questa tesi è importante considerare i problemi di ottimizzazione convessa. Prima di descrivere i formalismi matematici sull’ottimizzazione convessa è necessario presentare le basi matematiche su convessità di insiemi e funzioni, dando inoltre una panoramica delle proprietà e dei teoremi utilizzati da qui in avanti.
Partiamo dal definire formalmente un insieme convesso. L’insieme D ⊆ Rn è detto insieme convesso se per ogni coppia di punti x1, x2 ∈ D vale:
θx1+ (1 − θ)x2 ∈ D, (3.7)
con 0 ≤ θ ≤ 1. In pratica, se per ogni coppia di punti il segmento che li unisce è contenuto all’interno dell’insieme allora l’insieme è convesso.
Un particolare insieme convesso di nostro interesse è il poliedro convesso. Questo oggetto è definito come una zona limitata dello spazio ottenuta come intersezione di un numero finito di semispazi. In formule si ottiene:
P = {x | Ax b, Cx = d} (3.8)
dove il simbolo denota la diseguaglianza componente per componente. Quindi con u v, u, v ∈ Rn, si intende u
i ≤ vi, i = 1, . . . , n. Per i nostri
scopi possiamo quindi vedere come il poliedro convesso (per brevità d’ora in poi poliedro) sia dato dall’insieme delle soluzioni di un numero finito di vincoli di uguaglianza e diseguaglianza affini.
16 CAPITOLO 3. ALLOCAZIONE RISORSE Passiamo quindi alla definizione di funzione convessa. Una funzione f : D → R è detta convessa se D è un insieme convesso e se vale:
fθ x + (1 − θ) y≤ θ f (x) + (1 − θ) f (y), ∀x, y ∈ D (3.9) con 0 ≤ θ ≤ 1. La precedente equazione definisce che qualsiasi segmento che collega due punti qualsiasi appartenenti alla funzione, cioè la corda, deve giacere al di sopra della la funzione stessa, come visibile in figura 3.1. Si dice che una funzione è strettamente convessa se la disuguaglianza vale in modo stretto nella 3.9. Similmente è possibile definire f funzione concava se la corda giace al di sotto della funzione stessa o più formalmente se −f è convessa. Similmente alla convessità, se la diseguaglianza è stretta si dice che la funzione è strettamente concava.
Figura 3.1: Esempio di funzione convessa. Si noti come qualsiasi corda (nell’esempio in rosso) giaccia sopra la funzione, a prescindere dai punti scelti.
D’ora in poi si daranno dei risultati e proprietà utili per le funzioni convesse per brevità di trattazione. Queste proprietà possono essere utilizzate anche per funzioni concave, con le dovute accortezze, ricordandosi sempre che se f è concava −f sarà convessa e viceversa.
Per la natura della definizione non è sempre facile provare la convessità di una funzione tramite la 3.9. Esistono però le condizione di primo e secondo ordine che possono rendere la prova di convessità più semplice in alcuni casi. Per la condizione al primo ordine la funzione f in esame deve essere differenziabile. In questo caso f è convessa se e solo se il suo dominio D è un insieme convesso e se vale:
f (y) ≥ f (x) + ∇f (x)T(y − x), ∀x, y ∈ D, (3.10) la cui dimostrazione deriva dalla definizione di convessità e di differenziabilità di una funzione [9]. La disuguaglianza definisce che la funzione affine tangente alla funzione d’interesse e passante per il punto (x, f (x)) giace sempre al di sotto della curva, se essa è convessa. La condizione è illustrata graficamente in figura 3.2.
3.1. PROBLEMI DI OTTIMIZZAZIONE 17
(x, f (x)) f (y)
f (x) + ∇f (x)T(y − x)
Figura 3.2: Visualizzazione grafica della condizione di convessità al primo ordine.
La condizione al secondo ordine è applicabile se la funzione sotto esame è differenziabile due volte. Nel caso lo sia, la funzione f è convessa se e solo se il suo dominio D è convesso e se la matrice Hessiana della funzione è semidefinita positiva, in formule:
zTHf (x)z ≥ 0, ∀x ∈ D, ∀z 6= 0 ∈ Rn (3.11) Per una funzione f : R → R questo vuol dire semplicemente che la derivata seconda è non negativa in ogni punto, giustificando la convessità della funzione.
3.1.3
Ottimizzazione convessa
Un problema di ottimizzazione convessa in forma canonica è: min f0(x), fi(x) ≤ 0, i = 1, . . . , m, Ax = b, A ∈ Rp×n, b ∈ Rp (3.12)
con f0, . . . , fm funzioni convesse. Rispetto a un problema di ottimizzazione
generale descritto dalla 3.1, questo tipo di problema richiede delle particolare specifiche sulla funzione obiettivo, che deve essere convessa, sulle funzioni di vincolo di disuguaglianza, anch’esse convesse, e sulle funzioni di vincolo di uguaglianza, che devono essere affini. Da queste specifiche possiamo risalire alle proprietà del feasible set, che dovrà necessariamente essere convesso. Il dominio del problema è infatti:
D =
m
\
i=0
domfi, (3.13)
che è un insieme convesso per definizione di funzione convessa. Il feasible set F sarà l’intersezione tra D, m insiemi convessi {x | fi(x) ≤ 0, i = 1, . . . , m}
18 CAPITOLO 3. ALLOCAZIONE RISORSE e p iperpiani {x | aT
i x = bi, i = 1, . . . , p}, dove con aTi e bi sono stati indicati
rispettivamente la riga i-esima della matrice A e l’elemento i-esimo del vettore b. L’intersezione di questi m + p + 1 insiemi è sempre un insieme convesso e quindi è possibile definire alternativamente un problema di ottimizzazione convessa, come la minimizzazione di una funzione obiettivo convessa su un insieme convesso.
Per tutti i problemi convessi, si può dimostrare che ogni ottimo locale è anche ottimo globale [9].
Esiste una particolare condizione di ottimalità per i problemi convessi. Dato un problema di ottimizzazione convessa si può dimostrare che x ∈ F è ottimo se [9]
∇f0(x)T(y − x) ≥ 0, ∀y ∈ F . (3.14)
3.1.4
Lagrangiana e problema duale
L’idea generale della funzione lagrangiana è quella di inserire i vincoli del problema di ottimizzazione all’interno della funzione obiettivo, generando un nuovo problema di ottimizzazione. In relazione al problema generale 3.1, la lagrangiana associata è una funzione L : Rn
× Rm × Rp → R la cui espressione è data da: L(x, λ, ν) = f0(x) + m X i=1 λifi(x) + p X i=1 νihi(x) (3.15)
dove λ è il vettore dei moltiplicatori di Lagrange associato ai vincoli di disuguaglianza, mentre ν è il vettore dei moltiplicatori di Lagrange associato ai vincoli di uguaglianza. Si noti che nella formalizzazione del problema non tutti i vincoli devono essere obbligatoriamente inseriti nella lagrangiana, ma è possibile considerarne solo alcuni.
Definiamo ora la funzione duale al problema di ottimizzazione, che è l’estremo inferiore della lagrangiana per ogni variabile x, e cioè:
g(λ, ν) = inf
x∈DL(x, λ, ν). (3.16)
La funzione duale è quindi l’estremo inferiore di una somma di funzioni affini in λ e ν. Questa funzione è quindi una funzione concava, qualsiasi siano le funzioni obiettivo e di vincolo del problema di ottimizzazione [9]. Si noti che nel caso in cui la variabile x non è limitata inferiormente, g(λ, ν) assume valore −∞.
La funzione duale dà un bound inferiore rispetto all’ottimo del problema di ottimizzazione 3.1, valendo:
3.1. PROBLEMI DI OTTIMIZZAZIONE 19 che deriva direttamente dalla definizione di funzione duale. Infatti per un qualsiasi punto ammissibile ˆx ∈ F la combinazione lineare tra variabili duali e funzioni di vincolo risulta ∀λ ≥ 0, ∀ν:
fi(ˆx) ≤ 0, hi(ˆx) = 0 =⇒ m X i=1 λifi(ˆx) + p X i=1 νihi(ˆx) ≤ 0 =⇒ f0(ˆx) + m X i=1 λifi(ˆx) + p X i=1 νihi(ˆx) ≤ f0(ˆx) (3.18) ottenendo in definitiva: g(λ, ν) = inf x∈DL(x, λ, ν) ≤ L(ˆx, λ, ν) ≤ f0(ˆx) ≤ p ∗ . (3.19)
Il limite inferiore dato da questa funzione è utile solo se g(λ, ν) > −∞, altrimenti quest’ultima non dà nessuna informazione sul problema di ottimiz-zazione.
Dati i vincoli sui moltiplicatori di Lagrange la funzione duale può essere utilizzata per ottenere il miglior limite inferiore per p∗, risolvendo il seguente problema di ottimizzazione: max g(λ, ν), λ 0, (3.20)
che è quindi il massimo limite inferiore ottenibile. Questo è detto problema lagrangiano duale associato al problema 3.1, quest’ultimo chiamato anche problema primale. Si noti che il duale è un problema di ottimizzazione convessa, anche se il primale non è convesso, poiché la funzione obiettivo è concava e il problema è effettuato su un insieme convesso.
Le variabili duali (λ, ν) sono dette ammissibili se λ 0 e se g(λ, ν) > −∞. Nel caso in cui esistano variabili duali ammissibili che risolvano il problema 3.20, queste vengono chiamate variabili ottime duali e sono indicate con (λ∗, ν∗). Il valore duale ottimo ottenuto viene indicato con d∗ = g(λ∗, ν∗).
Riprendendo l’equazione 3.17 ed estendendola al valore ottimo si ottiene la proprietà chiamata dualità debole (weak duality), definita come:
d∗ ≤ p∗ (3.21)
che vale qualsiasi sia il problema primale e il duale associato. La differenza tra i due valori ottimi p∗− d∗ è sempre non negativa ed è detta duality gap.
Nel caso in cui il duality gap sia nullo, e cioè l’ottimo del duale equivale all’ottimo del primale, si parla di dualità forte (strong duality), in formule:
20 CAPITOLO 3. ALLOCAZIONE RISORSE che molto spesso (ma non sempre) vale se il problema primale è conves-so. Le condizioni che fanno valere la dualità forte sono chiamate costraint qualification.
Una semplice condizione per la dualità forte è la condizione di Slater, definita per ogni problema di ottimizzazione convessa. Considerando il problema 3.12 e il suo dominio D (3.13), la dualità forte vale se:
∃x ∈ relint D : fi(x) < 0, i = 1, . . . , m; Ax = b, (3.23)
dove relint D è l’interno relativo del dominio D definito come {x ∈ D | {y | {||y − x|| ≤ r} ∩ aff D, ∀r > 0} [9]. I punti che soddisfano la condizione 3.23 sono detti anche fortemente ammissibili (strictly feasibles). La condizione di Slater implica inoltre che ∃(λ∗, ν∗) tali che g(λ∗, ν∗) = d∗ = p∗.
Nel caso in cui valga la dualità forte in un qualsiasi problema di ottimiz-zazione, per cui si ha p∗ = d∗, deve valere:
f0(x∗) = g(λ∗, ν∗) = inf x∈D f0(x) + m X i=1 λ∗ifi(x) + m X i=1 νi∗hi(x) ≤ f0(x∗) + m X i=1 λ∗ifi(x∗) + m X i=1 νi∗hi(x∗) ≤ f0(x∗). (3.24)
La prima disuguaglianza vale poiché l’estremo inferiore rispetto a x è sempre minore uguale di ogni punto appartenente al dominio come x∗, la seconda disuguaglianza vale per l’equazione 3.18 che vale per x∗ essendo anch’esso un punto ammissibile. La relazione appena trovata definisce che la funzione lagrangiana calcolata nei punti ottimi (x∗, λ∗, ν∗) assume valore uguale all’ot-timo della funzione obiettivo, essendo maggiorata e minorata dalla stessa. La relazione 3.24 porta quindi a una ulteriore proprietà, e cioè:
m
X
i=1
λ∗ifi(x∗) = 0 =⇒ λ∗ifi(x∗) = 0, i = 1, . . . , m, (3.25)
poiché tutti i termini della somma sono non positivi. Questa condizione è detta complementary slackness. Quindi, per il vincolo λ 0, deve valere che i moltiplicatori ottimi associati ai vincoli di diseguaglianza devono essere nulli, a meno che la funzione di vincolo in x∗ sia nulla. In formule:
fi(x∗) < 0 =⇒ λ∗i = 0,
λ∗i > 0 =⇒ fi(x∗) = 0,
3.2. ALLOCAZIONE DI POTENZA 21 Consideriamo adesso il caso particolare di funzione obiettivo e di vincolo differenziabili. Per variabile primale e varibili duali ottime (x∗, λ∗, ν∗), con duality gap nullo, si ha che la funzione lagrangiana sarà minimizzata, portando all’annullamento del gradiente:
∇f0(x∗) + m X i=1 λ∗i∇fi(x∗) + p X i=1 νi∗∇hi(x∗) = 0. (3.27)
Consideriamo quindi un problema con duality gap nullo e tutte le funzioni differenziabili. Per la variabile primale e le variabili duali ottime (x∗, λ∗, ν∗) devono quindi valere tutte le condizioni fin’ora elencate, riassunte di seguito:
fi(x∗) ≤ 0, i = 1, . . . , m, hi(x∗) = 0, i = 1, . . . , p, λ∗i ≥ 0, i = 1, . . . , m, λ∗ifi(x∗) = 0, i = 1, . . . , m, ∇f0(x∗) + m X i=1 λ∗i∇fi(x∗) + p X i=1 νi∗∇hi(x∗) = 0 (3.28)
che sono dette le condizioni di Karush-Kuhn-Tucker (KKT). Queste condizioni sono in generale necessarie ma non sufficienti. È possibile dimostrare che per un problema convesso queste condizioni sono anche condizioni sufficienti per l’ottimalità delle variabili [9].
3.2
Allocazione di potenza
Nella prima parte di questo capitolo sono state presentate le basi sui problemi di ottimizzazione. In questa sezione, la teoria matematica già presentata verrà utilizzata per descrivere le metodologie di risoluzione dei problemi di allocazione di potenza per sistemi multi utente.
In particolare le prossime sezioni descriveranno in forma generale due problemi tipici: la massimizzazione della capacità di canale e la minimizzazione della potenza. La modellazione dei problemi servirà per la presentazione di proprietà utili per la risoluzione di problemi non convessi, necessarie per la trattazione degli algoritmi proposti nel lavoro di tesi, effettuata nel capitolo 4.
3.2.1
Formalizzazione dei problemi
Consideriamo un sistema di comunicazione che utilizza una qualsiasi tecnica di accesso multiplo e consideriamo che ad ogni ricevitore si possa descrivere il
22 CAPITOLO 3. ALLOCAZIONE RISORSE canale come stazionario e piatto in frequenza. Immaginiamo che il sistema presenti K risorse frequenziali ortogonali e N utenti.
Senza entrare nel dettaglio dei vincoli e della specificità del sistema, è pos-sibile dare una forma generale dei problemi di ottimizzazione per l’allocazione risorse.
Per un problema di massimizzazione della capacità la forma sarà la seguente: max xk K X k=1 fkM(xk) (3.29a) subject to K X k=1 hMk (xn) P , (3.29b) xk 0, (3.29c)
dove xk ∈ RN, fkM : RN → R non necessariamente convesse, hMk : Rm → RN
non necessariamente convesse, P ∈ RN, rappresentante il vettore delle potenze massime che ogni dispositivo può trasmettere. Il feasible set associato al problema è definito come FM = {x ∈ D
x| PKk=1hMk (xn) P , xk 0}. Si
noti i vincoli presentati sono i minimi per un problema di allocazione risorse, ma è possibile aggiungere altri vincoli a seconda delle necessità.
Dato il problema 3.29a è possibile definire la funzione lagrangiana associata come: L(xk, λ) = K X k=1 fkM(xk) + λT P − K X k=1 hMk (xn) , (3.30)
e quindi il problema duale come: min
λ g(λ) = minλ maxxk
L(xk, λ) (3.31a)
subject to λ 0 (3.31b)
con λ ∈ RN vettore dei moltiplicatori di Lagrange associati al problema.
Similmente, per un problema di minimizzazione della potenza si avrà la forma: min xk K X k=1 fkm(xk) (3.32a) subject to K X k=1 hmk(xn) r, (3.32b) xk 0, (3.32c)
3.2. ALLOCAZIONE DI POTENZA 23 dove xk ∈ RN, fkm : RN → R non necessariamente convesse, hmk : Rm →
RN non necessariamente convesse, r ∈ RN, rappresentante il vettore delle capacità di canale che ogni utente deve raggiungere al fine di una corretta allocazione. Il feasible set associato al problema è definito come Fm = {x ∈
Dx| PKk=1hmk(xn) r, xk 0}.
La funzione lagrangiana associata al problema 3.32a risulta: L(xk, λ) = K X k=1 fkm(xk) + λT r − K X k=1 hmk(xn) , (3.33)
e il problema duale è formalizzabile nel seguente modo: max
λ g(λ) = maxλ minxk
L(xk, λ) (3.34a)
subject to λ 0 (3.34b)
con λ ∈ RN vettore dei moltiplicatori di Lagrange associati al problema.
3.2.2
Metodi di risoluzione
I problemi formalizzati precedentemente sono risolvibili in maniera iterativa calcolando successivamente la soluzione ottima del primale con le variabili duali date e la soluzione ottima del duale con variabili primali date.
La risoluzione del primale dipende dalla forma della funzione obiettivo e dalle funzioni di vincolo. Un metodo generale di soluzione è l’utilizzo di procedure che portino alla risoluzione di un problema convesso, rendendo possibile l’utilizzo delle condizioni KKT (3.28) per il calcolo delle variabile ottime. Una trattazione di questi metodi non può essere effettuata con generalità, ma deve essere applicata a seconda della formalizzazione del problema all’interno dello scenario d’interesse. Per sistemi di trasmissione half-duplex sono state define negli anni molte metodologie di risoluzione, al di fuori degli scopi di questa tesi. Una possibile risoluzione per sistemi di trasmissione full-duplex è trattata nel capitolo 4.
Consideriamo ora la soluzione del duale. Un possibile soluzione ottima è ottenibile tramite di un aggiornamento iterativo delle variabili di Lagrange nella direzione di interesse, simultaneamente per le N variabili.
Definiamo quindi il subgradiente di una funzione, come generalizzazione del gradiente per una funzione non differenziabile. Il vettore d è definito subgradiente di g(λ) in λ, se soddisfa la relazione:
g(λ0) ≥ g(λ) + dT(λ0− λ), ∀λ0. (3.35) Intuitivamente d è subgradiente se la funzione lineare con pendenza d, passante per il punto (λ, g(λ)), giace interamente al di sotto della funzione in oggetto.
24 CAPITOLO 3. ALLOCAZIONE RISORSE Tramite questo strumento matematico è possibile definire il subgradient method, metodo iterativo che prevede l’aggiornamento delle variabili tramite la seguente formula:
λi+1 =λi− sid+, (3.36) dove i è l’iterazione attuale, (x)+ = max(0, x) e si è una sequenza detta
step size, necessaria per la convergenza [15]. La convergenza dell’algoritmo è assicurata per si sufficientemente piccolo [17]. Intuitivamente, ad ogni
iterazione, si porta la funzione duale verso il suo minimo, muovendosi di un passo proporzionale al subgradiente. La scelta dello step size dipende dall’applicazione e dalla velocità di convergenza cercata.
Adesso è necessario calcolare un possibile subgradiente delle funzioni duali sopra descritte. Si può dimostrare che, per il problema a massima capacità, il subgradiente di g(λ) vale [15]: dM = P − K X k=1 hMk (x∗n). (3.37)
Per il problema a minima potenza è necessario considerare che la funzione duale è una funzione concava, poiché limite inferiore di somma di funzioni affini. In questo caso, il subgradiente cercato è opposto rispetto alla forma precedente e cioé: dm = K X k=1 hmk(x∗n) − r. (3.38)
Si noti adesso che in questa sezione è stato ipotizzato che il duality gap tra il problema primale e quello duale sia nullo per ogni problema di allocazione risorse. Questo, in generale, non è vero e la prossima sezione presenta delle condizioni per da soddisfare per verificare questa ipotesi.
3.2.3
Duality gap
Come è stato definito in sezione 3.1.4, le soluzioni di un problema convesso che soddisfano la condizione di Slater (3.23) portano all’annullamento del duality gap. Lo stesso risultato non è verificato per problemi non convessi, per cui la condizione di Slater non è sufficiente all’ottenimento della dualità forte. Per questo, è necessaria una condizione valida per problemi non convessi che implichi l’ottenimento della dualità forte.
3.2. ALLOCAZIONE DI POTENZA 25 Per fare ciò riformuliamo i due problemi primali in una forma generale come la seguente: min xk K X k=1 fk(xk) (3.39a) subject to K X k=1 hk(xn) X, (3.39b)
dove xk ∈ RN, fk : RN → R non necessariamente convesse, hk : RN → RN
non necessariamente convesse, X ∈ RN.
Definiamo adesso la condizione di time-sharing. Siano x∗k e y∗k soluzioni ottime del problema 3.39a formulato rispettivamente con i vincoli Xx e
Xy. Un problema di ottimizzazione si dice che rispetta la condizione di
time-sharing se, ∀Xx, Xy, ∃zk∈ F tale che: K X k=1 hk(zk) θXx+ (1 − θ)Xy, K X k=1 fk(zk) θ K X k=1 fk(xk) + (1 − θ) K X k=1 fk(yk), 0 < θ < 1. (3.40)
È possibile dimostrare che un qualsiasi problema di ottimizzazione, della forma del problema 3.39a, che soddisfa la condizione di Slater (3.23) e la condizione di time-sharing (3.40) ha duality gap nullo, e quindi la soluzione ottima del duale è pari alla ottima del primale [15], [16].
La condizione di Slater, per i problemi di allocazione risorse multi utente, è nella pratica sempre verificata, poiché dipende dalla presenza di soluzioni fortemente ammissibili all’interno del dominio del problema [16].
La condizione di time-sharing è verificata, senza approssimazioni, nel caso di una distribuzione continua di risorse spettrali. Infatti è possibile dimostrare che la condizione è sempre verificata per K → ∞, ma con le dovute approssimazioni la condizione vale con K sufficiente grande [15].
Capitolo 4
Algoritmi di allocazione
sviluppati
In questo capitolo vengono presentati gli algoritmi proposti per la risoluzione dei problemi di allocazione risorse per sistemi full-duplex in celle cellulari. I due algoritmi proposti sono rispettivamente la ricerca del massimo rate totale nella cella, descritto in sezione 4.2, e la ricerca per la minima potenza totale spesa, descritto in sezione 4.3. Dati i risultati ottenuti nel capitolo 2, in particolare i vincoli sulla dimensione della cella, i due algoritmi sono stati sviluppati per essere utilizzati all’interno di una femtocella con un numero limitato di utenti connessi simultaneamente. In questo contesto è importante ricordare che solo stazione base della femtocella, in breve femto-BS, è equipaggiata con sistema di trasmissione full-duplex mentre i terminali mobili sono equipaggiati con sistemi half-duplex. Prima di descrivere i due algoritmi verrà descritto nel dettaglio lo scenario di funzionamento degli stessi, con particolare riferimento alla notazione utilizzata per la risoluzione dei problemi di ottimizzazione.
4.1
Scenario
Come scenario, viene considerata una singola femtocella con tecnica di ac-cesso multiplo OFDMA, che presenta K sottoportanti disponibili, fornite dalla macrocella. L’allocazione delle sottoportanti della macrocella verso la femtocella, è effettuata tramite l’underlay paradigm, cioè la femtocella può accedere alle risorse frequenziali occupate dalla macrocella, in particolare le frequenze uplink, tenendo conto che l’interferenza generata verso la macro-BS non deve portare a una riduzione della Quality-of-Service (QoS) all’interno della macrocella.
28 CAPITOLO 4. ALGORITMI DI ALLOCAZIONE SVILUPPATI All’interno della femtocella sono presenti simultaneamente M uplink users (UU) e N downlink users (DU). Le potenze per ogni utente e per ogni sottoportante sono definite come pUm,k, pDn,k, rispettivamente per uplink e downlink. Si definiscono i moduli quadri dei guadagni di canale come hU
m,k,
hU
n,k, hsik, hm,n,k, rispettivamente tra m-esimo UU e femto-BS, tra femto-BS
e n-esimo DU, self-interference e infine cross-interference tra m-esimo UU e n-esimo DU, sulla k-esima sottoportante. Uno schema di principio dello scenario è visibile in figura 4.1.
Figura 4.1: Scenario in cui sono stati formalizzati i due algoritmi di allocazione di potenza [13].
Come presentato in sezione 2.1, la capacità di canale è una funzione del rapporto segnale rumore interferente ad ogni ricevitore della cella. Nel nostro caso è necessario calcolare questo rapporto alla femto-BS e ad ogni DU. Gli algoritmi formulati si basano dall’idea che la k-esima sottoportante venga allocata solo a un’unica coppia di utenti uplink-downlink. Per questo motivo, il rapporto segnale rumore interferente alla femto-BS, per m-esimo utente e k-esima sottoportante risulta:
SINRUm,k = h U m,kpUm,k hsi k pDn,k+ σ2+ Ik (4.1) mentre il rapporto segnale rumore interferente, all’n-esimo DU e k-esima sottoportante risulta: SINRDn,k = h D n,kpDn,k hm,n,kpUm,k+ σ2+ Ik (4.2)
4.2. ALGORITMO A MASSIMO RATE 29 dove σ2 è la potenza di rumore in banda mentre I
k è l’interferenza data dalle
femtocelle adiacenti sulla k-esima sottoportante. Affinché questa interferenza possa venire considerata statica si suppone l’utilizzo di tecniche di allocazione ottima delle risorse della macrocella verso le varie femtocelle, come quelli presentati in [10] e [11]. Per semplicità di notazione d’ora in poi verrà considerata direttamente la somma dei due parametri, come σ2
k = σ2+ Ik.
4.2
Algoritmo a massimo rate
Di seguito verrà descritto l’algoritmo di allocazione risorse per il raggiungi-mento del massimo rate disponibile con l’utilizzo della tecnologia full-duplex, all’interno dello scenario descritto in sezione 4.1.
4.2.1
Problema di ottimizzazione
Come già detto, lo scopo di questo algoritmo è massimizzare il rate nella cella, allocando ogni risorsa spettrale alla coppia di utenti uplink-downlink che massimizza la capacità per quella data risorsa.
Il valore della capacità totale nella cella risulterà quindi una somma delle capacità per ogni coppia e per ogni sottoportante, pesati per una variabile di allocazione che permetta che la sottoportante k-esima venga assegnata ad un’unica coppia. Si ottiene cioè l’espressione:
C = K X k=1 N X n=1 M X m=1
x(k)m,nhlog2(1 + SINRUm,k) + log2(1 + SINRDn,k)i, (4.3) con x(k)m,n ∈ {0, 1}. Affinché la variabile di allocazione sia non nulla per una sola coppia deve valere il seguente vincolo:
M X m=1 N X n=1 x(k)m,n ≤ 1, ∀k. (4.4)
Altri vincoli necessari sono quelli rispetto alla potenza trasmissibile dai vari utenti e dalla femto-BS. Infatti definendo Pmax
m la potenza massima
tra-smissibile dall’m-esimo utente uplink e Pmax
BS la potenza massima trasmissibile
dalla femto-BS si ottengono i vincoli:
K X k=1 pUm,k ≤ Pmmax, ∀m, (4.5) N X n=1 K X k=1 pDn,k ≤ Pmax BS . (4.6)
30 CAPITOLO 4. ALGORITMI DI ALLOCAZIONE SVILUPPATI Inoltre le potenze non possono fisicamente essere negative ed è buona norma imporle a zero se l’utente non è allocato alla determinata sottoportante, ottenendo: pUm,k ≥ 0, pU m,k = 0 se x (k) m,n = 0, ∀m, k, (4.7) pDn,k ≥ 0, pD n,k = 0 se x (k) m,n = 0, ∀n, k. (4.8)
Oltre alle grandezze sopra riportate, è necessario vincolare l’interferenza generata dalla femtocella verso la macrocella. Per mantenere un certo livello di QoS, l’interferenza ricevuta dalla macro-BS, su ogni sottoportante utilizzata con l’underlay paradigm, non dovrà superare una certa soglia, definita come Qk. Ogni elemento trasmittente della femtocella avrà un canale verso la
macro-BS. Per la k-esima sottoportante, i moduli quadri dei coefficienti di guadagno di canale vengono definiti come:
gk = [g1,k, . . . , gM,k, gM +1,k]T, ∀k, (4.9)
dove le posizioni da 1 a M sono i canali tra i vari UU e la macro-BS, mentre il canale M + 1-esimo è tra la femto-BS e la macro-BS. È possibile organizzare le potenze trasmesse dagli elementi della femtocella nel seguente vettore:
pk = [pU1,k, . . . , p U M,k, N X n=1 pDn,k]T. (4.10)
Date le precedenti relazioni, il vincolo di interferenza da rispettare su ogni sottoportante risulta semplicemente:
gTkpk ≤ Qk, ∀k. (4.11)
Alcuni articoli entrano nel dettaglio del problema di stima del canale tra femtocella e macrocella, considerando anche l’incertezza della conoscenza del canale da parte della macro-BS [13]. In ogni caso la stima dei canali è fuori dagli scopi di questo lavoro.
4.2. ALGORITMO A MASSIMO RATE 31 formalizzare il problema di ottimizzazione come:
max x(k)m,n,pUm,k,p D n,k K X k=1 N X n=1 M X m=1
x(k)m,nhlog2(1 + SINRm,kU ) + log2(1 + SINRDn,k)i, (4.12a) s.t. M X m=1 N X n=1 x(k)m,n ≤ 1, ∀k, (4.12b) K X k=1 pUm,k ≤ Pmax m , ∀m, (4.12c) N X n=1 K X k=1 pDn,k ≤ Pmax BS , (4.12d) pUm,k ≥ 0, pU m,k = 0 se x (k) m,n = 0, ∀m, k, (4.12e) pDn,k ≥ 0, pD n,k = 0 se x (k) m,n = 0, ∀n, k, (4.12f) gTkpk ≤ Qk. (4.12g)
Questo è un problema misto intero e non convesso. Il problema duale lagrangiano risulta:
min
γ,λ g(γ, λ), (4.13a)
subject to γm ≥ 0, ∀m, λ ≥ 0, (4.13b)
che è un problema convesso per costruzione, in cui è stata definita:
g(γ, λ) = max x(k)m,n,pUm,k,pDn,k K X k=1 N X n=1 M X m=1
x(k)m,nhlog2(1+SINRUm,k)+log2(1+SINRDn,k)i − M X m=1 γm( K X k=1 pUm,k− Pmmax) − λ( N X n=1 K X k=1 pDn,k− PBSmax), (4.14) soggetta ai vincoli 4.12b, 4.12e, 4.12f e 4.12g.
4.2.2
Risoluzione del primale
Consideriamo adesso moltiplicatori di Lagrange γ, λ dati e calcoliamo l’ot-timo del problema primale. Tenendo conto della equazione 4.14 è possibile rielaborare il primale nel seguente modo:
max x(k)m,n,pUm,k,pDn,k K X k=1 N X n=1 M X m=1 x(k)m,nL(k)m,npUm,k, pDn,k, (4.15)
32 CAPITOLO 4. ALGORITMI DI ALLOCAZIONE SVILUPPATI dove è stato definito:
L(k)m,npUm,k, pDn,k= log21 + SINRUm,k− γmpUm,k+
+ log21 + SINRDn,k− λ pD
n,k, (4.16)
che è stata ottenuta trascurando tutti i termini costanti rispetto alle variabili da massimizzare.
L’espressione 4.15 mette in luce i due strati del problema primale. Infatti è possibile massimizzare L(k)m,n, calcolando le potenze ottime per ogni possibile coppia (m, n) ottenendo M × N valori di L(k)
m,n, per la k-esima sottoportante.
La sottoportante viene in seguito allocata alla coppia che massimizza L(k)
m,n,
ottimizzando quindi la variabile di allocazione intera.
Ottimizzazione di L. Considerando la singola sottoportante k e la singola
coppia (m, n), possiamo definire il vettore delle potenze da calcolare come p = [pU
m,k, pDn,k]T = [p1, p2]T. Definiamo inoltre il feasible set di interesse come
Fp = {p | p 0, p1 ≤ Pmmax, p2 ≤ PBSmax, gm,kp1 + gM +1,kp2 − Qk ≤ 0}. Il
problema di ottimizzazione risulta: max
p ∈Fp
L(k)m,n (4.17)
che è un problema non convesso su un set convesso.
Questo problema ha un forma particolare, detta Difference of Convex, poiché è scrivibile come somma di funzione strettamente concava e funzione strettamente convessa, per cui:
L(k)m,n(p) = fcav(p) + fvex(p). (4.18)
Per semplicità di notazione normalizziamo i canali di interesse rispetto alla varianza di rumore, ottenendo h1 =
hUm,k σ2 k , h2 = hDn,k σ2 k , h3 = hsi k σ2 k , h4 = hm,n,k σ2 k . Le funzioni che compongono L(k)m,n risultano adesso:
fcav(p) = log2(p2h2+ p1h4+ 1) + log2(p1h1+ p2h3+ 1), (4.19)
fvex(p) = − log2(p2h3 + 1) − log2(p1h4+ 1) − λ p2− γmp1, (4.20)
È possibile risolvere questo problema usando la Concave-Convex Procedure (CCCP), algoritmo iterativo che ad ogni passo linearizza la funzione convessa in un punto fisso e calcola il massimo della funzione ottenuta per ricavare le potenze ottime. Considerando il punto fisso p(l) dell’l-esima iterazione e
4.2. ALGORITMO A MASSIMO RATE 33 linearizzando fvex nel punto p(l) = [p
(l) 1 , p
(l)
2 ]T, si ottiene la funzione concava:
F (p) = fcav(p) + pT∇fvex(p(l)) = log2(p1h1+ p2h3 + 1) + log2(p2h2+ p1h4+ 1) − γ0p1 ln 2 − λ0p2 ln 2 , (4.21) dove sono stati definiti
γ0 = h4 h4p (l) 1 + 1 + γmln 2, (4.22) λ0 = h3 h3p (l) 2 + 1 + λ ln 2. (4.23)
Definiamo il dominio di F (p) come DF, formato da tutti i punti in cui gli
argomenti dei logaritmi sono positivi. Per come è definito il feasible set, vale che l’intersezione tra esso e il dominio è pari a Fp ∩ DF = Fp. Quindi una
soluzione ammissibile appartiene anche al dominio della funzione in esame. Ad ogni iterazione il problema diventa:
p(l+1)= argmax
p F (p) (4.24a)
subject to 0 ≤ p1 ≤ Pmmax (4.24b)
0 ≤ p2 ≤ PBSmax (4.24c)
gm,kp1+ gM +1,kp2− Qk≤ 0 (4.24d)
che è un problema di ottimizzazione convessa poiché la funzione obiettivo è concava e le funzioni di vincolo sono funzioni affini.
È possibile calcolare una soluzione analitica del problema tramite il sistema ottenuto dall’imposizione delle derivate parziali a zero. La soluzione ottima risultante è la seguente: ∂F (p) ∂p1 = 0, ∂F (p) ∂p1 = 0, =⇒ p∗1 = h2 h2γ0−h4λ0 − h3 h1λ0−h3γ0 − h2−h3 h1h2−h3h4, p∗2 = h1 h1λ0−h3γ0 − h4 h2γ0−h4λ0 − h1−h4 h1h2−h3h4. (4.25)
Nel caso in cui p∗ ∈ Fp la soluzione alla 4.24a si ottiene ponendo p(l+1) = p∗.
Nel caso in cui p∗ ∈ F/ p il massimo della funzione si troverà sui confini di
Fp. In questo caso il problema viene risolto calcolando le coppie di potenze
che massimizzano la F (p) su ogni confine del poliedro e scegliendo quindi la coppia che genera il massimo valore della funzione obiettivo.
Riassumendo, si può scrivere: p(l+1) = p∗, p∗ ∈ F p p(l+1) = argmax ¯ p F (p), p ∗ ∈ F/ p (4.26)
34 CAPITOLO 4. ALGORITMI DI ALLOCAZIONE SVILUPPATI con ¯p qualsiasi coppia di potenze appartenenti ai confini del set convesso.
Si può dimostrare che la procedura iterativa converge con un numero sufficiente di iterazioni [14] e che il valore raggiunto è un ottimo locale [13]. Nella pratica, un metodo di stop della procedura è quello di considerare la differenza dei due vettori successivi in norma euclidea e confrontarla con una soglia di tolleranza. Cioè si impone la convergenza della procedura se:
||p(l+1)− p(l)||
2 ≤ , > 0. (4.27)
È possibile dimostrare che i confini che contengono la soluzione ottima ammissibile sono quelli per cui vale [13]:
(1 − θ) p∗+ θ ¯p /∈ Fp, 0 < θ < 1 (4.28)
e cioè, i confini per i quali il segmento che collega l’ottimo globale della funzione concava F (p) a qualsiasi punto del bordo non appartiene al feasible set. Tramite questo teorema è possibile ridurre notevolmente la quantità di operazioni algebriche da effettuare, al costo di un maggior numero di confronti per considerare solo i confini che verificano la 4.28.
Fp O A B C D p2 p1 PBSmax Pmax m
Figura 4.2: Generalizzazione della regione delle soluzioni ammissibili del proble-ma 4.24a. Questa forproble-ma comprende tutte le altre possibili, che variano a seconda dei valori di Qk e g.
Il calcolo analitico del massimo del problema 4.24a sui bordi del feasible set viene effettuato imponendo una delle due potenze a priori a seconda del confine scelto. La soluzione per ogni confine viene illustrata nei seguenti paragrafi che fanno riferimento alla figura 4.2.
