Capitolo 2 Allocazione dinamica delle risorse

Allocazione dinamica

delle risorse

2.1 Introduzione

Il capitolo che segue introduce rapidamente le principali tecniche di allocazione dinamica delle risorse fino ad ora note, distinguendo innanzitutto tra i diversi contesti in cui tali tecniche possono essere applicate.

Nel secondo paragrafo viene trattato uno scenario in cui è presente un solo utente e l’allocazione ottima viene trovata tramite l’algoritmo di Water-Filling (2.2.1); dopo aver messo in evidenza alcuni limiti di tale algoritmo, si introduce un nuovo algoritmo, chiamato Bit & Power Loading (2.2.2), che risolve tali problemi, senza però raggiungere l’allocazione ottima.

Nel terzo paragrafo si estende il discorso ad uno scenario in cui sono presenti più utenti ed è quindi possibile sfruttare non solo la diversità di canale ma anche la diversità multiutente. Dopo avere formulato il problema dell’allocazione multiutente ed i suoi vincoli, si presenta la soluzione in selection diversity (2.3.1) che, non tenendo conto dei vincoli citati, non fornisce una soluzione al problema dell’allocazione ma solo un limite teorico alle prestazioni che si possono ottenere.

Vengono quindi presentati due diversi algoritmi di allocazione; il primo, proposto da Kim et al nel 2006 [3], è di tipo ottimo (2.3.2) e si basa sull’assegnazione congiunta del numero delle sottoportanti, del formato di modulazione e della potenza da utilizzare su ciascuna sottoportante. Il secondo algoritmo che verrà presentato (2.3.3) risolve invece il problema in modo subottimo ma con onere computazionale decisamente inferiore; l’approccio seguito da Kivanc et al. [7] nel 2003 prevede di dividere il problema dell’allocazione risorse in due sottoproblemi distinti: Resource Allocation, per determinare quante sottoportanti assegnare ad ogni utente, e Subcarrier Assignment, per determinare quali sottoportanti assegnare ad ogni utente.

Prima di addentrarci nello sviluppo degli algoritmi appena descritti, è bene sottolineare che tali algoritmi vengono implementati dalla Base Station di un sistema OFDM; agli utenti viene comunicato solo il particolare set di sottoportanti, potenza e formato di modulazioni ad essi assegnato. In un collegamento in downlink tali informazioni servono agli utenti solo per la corretta decodifica del messaggio che viene loro trasmesso; in un collegamento in uplink, invece, le informazioni riguardo le assegnazioni servono agli utenti stessi per regolare i propri parametri trasmissivi, operazione che in downlink è fatta dalla BS. Ciò che verrà trattato in seguito è un

collegamento di solo downlink e non verranno trattati gli algoritmi implementati dagli utenti per il corretto settaggio dei parametri.

2.2 Allocazione singolo utente

Consideriamo un sistema OFDM singolo-utente in cui sono presenti un unico trasmettitore ed un unico ricevitore, la cui architettura è stata presentata nel capitolo 1. All’uscita del dispositivo di FFT, il segnale y n ricevuto sulla n-esima sottoportante ( ) risulta essere:

( ) ( ) _n ( ) ( )

y n = P n a H n +n n

n=0,1,...,N−1 (2.1) dove le variabili introdotte indicano rispettivamente:

• P n la potenza allocata alla sottoportante n-esima; ( ) • a il simbolo trasmesso sulla sottoportante n-esima; n

• H n il guadagno complesso di canale sulla sottoportante n-esima; ( )

1 ₂ 0 ( ) ( ) n L _{j l} N l H n h l e π − ₋ =

=

∑

dove LT è la durata del CIR di canale;

• n n il contributo del rumore termico, modellato come una variabile aleatoria ( ) complessa gaussiana a media nulla e varianza σ2.

Sfruttando la conoscenza della matrice di canale H, il trasmettitore adatta la potenza e il formato trasmissivo da utilizzare su ciascuna sottoportante, secondo un prefissato

criterio di ottimalità. Si tratta quindi di scegliere i parametri trasmissivi, determinando la potenza ( )P n e il formato di modulazione ( )c n da utilizzare su ciascuna

sottoportante. Il problema viene formalizzato nel seguente modo: assegnata una funzione obiettivo ( , )f c P che caratterizza le prestazioni del sistema si devono trovare i

vettori c e P che la rendano massima, rispettando alcuni vincoli riguardanti la potenza massima, il rate minimo o la probabilità di errore massima consentita.

2.2.1 Water-Filling

Uno dei problemi di allocazione risorse più noto consiste nel distribuire la potenza sulle varie sottoportanti in modo da massimizzare la capacità del sistema, rispettando il vincolo sulla potenza totale trasmessa. La capacità di informazione di un determinato canale è il massimo rate informativo che può essere trasmesso su quel canale con probabilità di errore arbitrariamente bassa per un dato rapporto segnale-rumore (Signal to Noise Ratio, SNR). Nonostante la capacità di canale abbia un valore teorico, in quanto raggiungibile soltanto mediante l'utilizzo di parole di codice infinitamente lunghe, essa rappresenta un valido strumento per determinare un limite teorico per le prestazioni di un qualsiasi sistema trasmissivo. Le N sottoportanti di un sistema OFDM possono essere considerate come altrettanti canali AWGN (Additive White Gaussian Noise) paralleli; la capacità complessiva C si ottiene quindi come somma delle capacità delle singole sottoportanti, come mostra la formula (2.2).

2 1 2 0 ( ) ( ) ( ) log 1 N n H n n C σ − = ⎛ ⎞ ⎜ ⎟ = + ⎜ ⎟ ⎝ ⎠

∑

P P   _(2.2)

L' obiettivo che ci prefiggiamo consiste nel determinare il vettore P che massimizza la capacità rispettando il vincolo sulla potenza complessiva trasmessa P , ovvero tot

( )

{ }

arg max C = P P P   _(2.3) s.t. 1 0 N tot n P − = =

∑

P (2.4) avendo indicato con P un valore di tentativo per ( )P n .

Se il trasmettitore non disponesse di alcuna informazione sullo stato del canale, la Resource Allocation (RA) ottima sarebbe quella di tipo uniforme, che consiste nel trasmettere la medesima potenza Ptot/N su tutte le sottoportanti. Quando però il ricevitore conosce lo stato del canale, il problema sopra esposto può essere risolto in forma chiusa utilizzando la tecnica dei moltiplicatori di Lagrange e la soluzione risulta essere 2 ( ) 2 ( ) P n H n σ μ + ⎛ ⎞ ⎜ ⎟ = − ⎜ ⎟ ⎝ ⎠ _(2.5)

avendo indicato con

( )x + =max(0, )x _(2.6) ' 1 2 2 0 1 ( ) ' N tot _n in P H i N σ μ − = + =

∑

(2.7)

'

N rappresenta il numero delle sottoportanti, di indici i₀, ... ,i_N'-1, per le quali risulta ( ) 0

P n > .

La soluzione proposta viene denominata “Water-Filling” [1], perché la potenza viene distribuita come acqua in un bacino il cui “fondale” dipende dal SNR sulle varie sottoportanti. La potenza complessiva determina il “livello” dell'acqua mentre i guadagni di canale determinano la quantità di potenza da allocare sulle varie sottoportanti.

Fig. 2.1 – Water-Filling per canali paralleli

P(1)

N(1)

P(2)

N(2)

N(3)

μ

Channel 1

Channel 2

Channel 3

In particolare, si può notare che la maggior parte della potenza viene allocata sui canali migliori, mentre se una sottoportante risulta essere troppo attenuata può non essere utilizzata affatto. Quando il livello dell'acqua μ è basso, e quindi quando la potenza disponibile è poca, i canali non utilizzati sono molti e tutta la potenza viene trasmessa solamente sui canali migliori. Si osserva inoltre che al crescere del SNR la soluzione Water-Filling tende asintoticamente a distribuire la potenza in maniera uniforme.

Tale tecnica massimizza la capacità ma ha due limiti fondamentali:

• la capacità per la n-esima sottoportante ( )C n , definita come

2 2 ( ) ( ) ( ) log 1 P n H n C n σ ⎛ ⎞ ⎜ ⎟ = + ⎜ ⎟ ⎝ ⎠

è un numero reale e quindi dà un’indicazione

solamente approssimativa del numero di bit per simbolo, che invece è rappresentato tramite un numero intero;

• la capacità rappresenta il massimo rate che garantisce una probabilità di errore asintoticamente nulla. Nei sistemi pratici, invece, la probabilità di errore necessaria a garantire una certa QoS è diversa da zero e costituisce un ulteriore vincolo nella formulazione del problema.

2.2.2 Bit & Power Loading

L’algoritmo di Water-Filling, sebbene dia una soluzione ottima al problema dell’allocazione delle risorse per lo scenario singolo-utente, viene utilizzato solo in pochi casi, a causa dei due forti limiti espressi alla fine del paragrafo precedente. Per risolvere tali problemi intrinseci all’algoritmo di Water-Filling sono stati studiati molti altri algoritmi. In questo contesto viene presentato l’algoritmo proposto da Wong et al. nel 1999 [2] in quanto esso non solo risolve brillantemente il problema dell’allocazione in un contesto singolo utente ma permette anche di chiarire la successiva estensione dell’algoritmo ad un contesto multi-utente.

Definiamo:

• K = il numero di utenti; 1

• R_k = il rate per simbolo OFDM; R

• N il numero delle sottoportanti disponibili;

• ck n, = il numero di bit assegnato alla sottoportante n-esima; cn c può n assumere solo valori nell’insieme D=

{

0,1, 2,..., M

}

, dove M è il massimo

numero di bit/simboli OFDM che può essere trasmesso su ogni sottoportante.

• 2

, ( )

k n n H n

α =α = l’ampiezza del guadagno di canale della n-esima sottoportante.

• 2

0 1

N =σ = la densità spettrale di rumore per tutte le sottoportanti.

• f c_k( )= f c( ) la potenza necessaria (energia per simbolo) per la ricezione del bit/simbolo c quando il guadagno di canale è uguale a 1; tale valore è

correlato alla qualità del servizio (QoS) richiesta dall’utente (probabilità d’errore).

Per comprendere al meglio il funzionamento dell’algoritmo che stiamo presentando, riprendiamo velocemente l’architettura del sistema OFDM già ampiamente descritta nel primo capitolo.

In trasmissione il flusso di dati seriale dell’unico utente considerato viene inviato ad un blocco di allocazione che, basandosi sulle informazioni di canale, decide quali sottoportanti e quanti bit/simboli OFDM assegnare all’utente in questione; sulla base del numero di bit assegnato ad ogni sottoportante, il modulatore adattativo deciderà quale modulazione utilizzare e quale livello di potenza trasmettere.

Per mantenere al ricevitore la QoS richiesta, è necessario che la potenza trasmessa dall’utente sulla sottoportante n sia

2 ( )_n n n f c P α = (2.8)

Usando questo livello di potenza trasmessa, il ricevitore può demodulare il segnale ricevuto e raggiungere la QoS desiderata.

L’obiettivo dell’algoritmo di allocazione combinata di sottoportanti, bit e potenza è trovare l’assegnazione migliore, in modo tale che la somma di P su tutte le _n

sottoportanti sia minima, mantenendo i vincoli sul rate e sul QoS specificati attraverso la funzione ( )f c . Si assume che ( )f c sia una funzione convessa crescente e che

(0) 0

F = ; ciò significa che non è richiesta alcuna potenza se non è trasmesso alcun bit e

che per trasmettere un ulteriore bit è necessario aggiungere potenza; la maggior parte degli schemi di codifica e modulazione soddisfa tale condizione.

In termini matematici il problema appena descritto si formula nel seguente modo: * 2 1 1 min ( ) n N T _c n n n P f c α ∈ ₌ =

∑

D (2.9) e la condizione riguardante il rate che deve essere rispettata è:

1 N n n R c = =

∑

(2.10) Se vi fosse più di un utente, sarebbe necessaria una ulteriore condizione che esprima il fatto che ogni sottoportante può essere utilizzata al massimo da un utente.

Ricordiamo che D=

{

0,1, 2,..., M

}

è l’insieme di tutti i possibili valori di c e che _n

0 n

c = significa che l’utente non usa la sottoportante n-esima per trasmettere alcuna

informazione.

Per la risoluzione di un problema soggetto a vincoli come quello appena esposto si può utilizzare un algoritmo di tipo greedy; esso assegna alla sottoportante un bit alla volta e per l’assegnazione sceglie la sottoportante per cui la potenza da aggiungere è minore. Il processo di allocazione dei bit si conclude quando tutti gli R bit sono assegnati.

La struttura base di un algoritmo di questo tipo è la seguente:

Inizializzazione: 0 n

c = e Δ =P_n

[

f(1)− f(0) /

]

α_n2 per ogni n Iterazioni per l’assegnazione dei bit:

Ripetere R volte le seguenti istruzioni:

ˆ arg min _n n

ˆ ˆ 1 n n c = +c

[

ˆ ˆ

]

ˆ 2 ˆ ( n 1) ( )n n n f c f c P α + − Δ = end; Conclusione:

{ }

cn è l’allocazione finale dei bit

Lo stadio di inizializzazione calcola, per ogni sottoportante, la potenza necessaria per trasmettere un bit in più. Ad ogni iterazione il bit viene assegnato alla sottoportante che necessita una aggiunta di potenza minore. Dopo R iterazioni, l’ultimo bit dà la miglior

allocazione per ogni sottoportante.

Bisogna notare che l’allocazione dei bit è ottima solo per la funzione ( )f c che si sta

considerando e che dipende dallo schema di modulazione scelto; schemi di modulazione diversi porterebbero a diverse funzioni ( )f c e, quindi, ad una diversa allocazione dei

2.3 Allocazione multi-utente

Prendiamo in esame un sistema OFDM ad accesso multiplo, generalmente indicato con la sigla OFDMA. In un sistema OFDMA la banda disponibile viene suddivisa fra i vari utenti ed a ciascun utente viene assegnato un certo numero di sottoportanti. In questo caso anche le sottoportanti rappresentano una risorsa da allocare al pari della potenza e del formato di modulazione. Se il sistema conosce i guadagni di canale di ogni utente, può assegnare ad ognuno di essi le sottoportanti meno attenuate.

Poiché i guadagni di canale dei vari utenti sono indipendenti tra loro, una sottoportante che risulta essere molto attenuata per un dato utente può risultare particolarmente vantaggiosa per un altro, garantendo così al sistema un certo guadagno di diversità, che in questo caso prende il nome di “diversità multi-utente”.

Come nel caso singolo-utente, l'allocazione può essere formulata con l'obiettivo di ottimizzare grandezze diverse come potenza, probabilità d’errore o rate informativo. Per valutare l' impatto complessivo degli algoritmi di allocazione multi-utente bisogna anche tenere conto della loro complessità e della quantità di informazioni di cui hanno bisogno. A causa del gran numero di variabili da gestire, la complessità di questi algoritmi è di qualche ordine di grandezza superiore a quella degli algoritmi di allocazione singolo-utente. Si deve inoltre considerare che l'allocatore e gli utenti devono scambiarsi una grande mole di informazioni.

In uno scenario in cui vi sono K utenti e N sottoportanti disponibili, l'allocatore deve conoscere a priori gli N guadagni di canale di tutti i K utenti; tali informazioni devono

ancora necessario comunicare a tutti gli utenti quali sono i canali ad essi assegnati. Si può dimostrare che la distribuzione delle potenze che massimizza la somma delle capacità di tutti gli utenti rispettando i vincoli di potenza per ciascun utente, si ottiene con l'algoritmo “Water-Filling iterativo” ([11], [15]). Tale tecnica assegna la potenza a ciascun utente applicando in maniera iterativa la soluzione Water-Filling trovata per il caso singolo-utente e considerando i segnali di tutti gli altri utenti come se fossero rumore.

La tecnica del Water-Filling iterativo richiede un numero di operazioni molto grande e la sua applicazione può essere impraticabile già per valori di K ed N relativamente piccoli.

Dopo aver escluso, quindi, l’algoritmo Water-Filling iterativo, passiamo ad analizzare altri possibili modi di risolvere il problema dell’allocazione risorse. Solitamente esso viene formulato in una delle due forme duali:

• Minimizzare la potenza totale trasmessa, sotto la condizione di rate costante; • Massimizzare il rate totale trasmesso, sotto la condizione di potenza costante. Il primo approccio è preferibile per applicazioni che necessitano un rate fisso garantito, mentre il secondo è più indicato per un traffico dati di tipo best-effort.

Essendo entrambi gli approcci sostanzialmente simili, parleremo genericamente di allocazione risorse, specificando quale criterio viene seguito solo nel caso in cui ciò sia necessario per la formulazione del problema in termini matematici.

Intuitivamente, la soluzione ottima al problema dell’allocazione risorse può essere trovata col calcolo esaustivo di tutte le possibili allocazioni e con la comparazione dei loro costi; ovviamente tale soluzione ha un onere computazionale troppo elevato poiché

vi sono q=KNM possibili allocazioni tra cui scegliere (si indica con K il numero degli

utenti, con N il numero delle sottoportanti e con M il numero dei formati di

modulazione).

Per evitare il calcolo esaustivo di tutte le possibili allocazioni e raggiungere comunque l’allocazione a costo minimo, vengono proposti algoritmi di allocazione ottima nel 1999 da Wong et al. [2] e nel 2006 da Kim et al. [3]; entrambi formulano un algoritmo per l’assegnazione congiunta di potenza, sottoportanti e formati di modulazione con l’obiettivo di minimizzare la potenza di trasmissione rispettando il vincolo che ogni sottoportante può essere assegnata al massimo ad un utente.

Tuttavia anche questo tipo di algoritmi mantiene un onere computazionale molto elevato che nelle applicazioni pratiche ne impedisce l’utilizzo.

Per ridurre la complessità di calcolo si può scindere il problema dell’allocazione risorse in due sottoproblemi distinti, procedendo per step nella ricerca dell’allocazione migliore (che però in questo caso non sarà più ottima).

STEP 1: RESOURCE ALLOCATION

Sulla base del rapporto segnale-rumore (SNR) di ogni utente, si determina il numero di sottoportanti che deve essere assegnato ad ogni utente.

STEP 2: SUBCARRIER ASSIGNMENT

Sulla base del canale visto da ciascun utente, si determina il set di sottoportanti da assegnare ad ogni utente.

2.3.1 Selection diversity

Prima di analizzare la soluzione ottima al problema dell’allocazione risorse in un sistema multiutente, cerchiamo un bound superiore alle prestazioni degli algoritmi che si occupano di questo problema; tale limite superiore si ottiene eliminando uno dei vincoli caratteristici del problema di allocazione, cioè il fatto che una sottoportante possa essere assegnata ad un solo utente.

In questo modo è possibile sfruttare al massimo la channel diversity, cioè il fatto che utenti diversi abbiano guadagni di canale diversi sulle varie sottoportanti disponibili. Il problema si riduce quindi ad allocare ad ogni utente la sottoportante, il set di sottoportanti o una parte della capacità delle sottoportanti, in modo che si abbia il miglior rapporto segnale-rumore (SNR), senza considerare se le sottoportanti interessate sono già state assegnate ad altri utenti.

2.3.2 Soluzione ottima

Wong et al. [2] nel 1999 per la prima volta propongono un algoritmo ottimo per l’assegnazione congiunta di potenza, sottoportanti e formati di modulazione, con l’obiettivo di minimizzare la potenza di trasmissione rispettando il vincolo che ogni sottoportante può essere assegnata al massimo ad un utente.

Il punto di partenza per lo sviluppo dell’algoritmo è l’osservazione che in uno scenario singolo-utente l’allocazione ottima, cioè che minimizza la potenza complessiva, si può ottenere con un algoritmo di tipo greedy in cui viene assegnata una sottopotante all’utente che richiede la minima aggiunta di potenza. Tuttavia il problema diviene molto più complesso in uno scenario multiutente; poiché gli utenti non possono condividere le sottoportanti, se si alloca una sottoportante ad un utente si impedisce che altri utenti possano usare quella sottoportante. Ne consegue che la soluzione ottima potrebbe non assegnare ad un utente la sottoportante che esso vede migliore, in termini di guadagno di canale; ciò può accadere quando la miglior sottoportante per un utente è anche la miglior sottoportante per un altro utente che, però, non ha altre sottoportanti con un buon guadagno di canale. Per questi motivi il problema multi-utente è molto più complesso di quello singolo-utente; mantenendo la notazione introdotta nel caso singolo-utente, possiamo così formulare il problema di ottimizzazione ed i suoi vincoli:

, * , 2 1 1 , 1 min ( ) k n N K T k k n c n k k n P f c α ∈ _{= =} =

∑∑

D (2.11) C1: per tutti k∈

{

1,...,K

}

_, 1 N k k n n R c = =

∑

(2.12)

Ricordiamo che K è il numero di utenti, R è il rate per simbolo OFDM, N è il numero _k

delle sottoportanti disponibili, c_{k n,} è il numero di bit che l’utente k assegna alla

sottoportante n-esima (c_{k n,} può assumere solo valori nell’insieme D=

{

0,1, 2,..., M

}

, dove M è il massimo numero di bit/simboli OFDM che può essere trasmesso su ogni

sottoportante), α_{k n,} = H n_k( )2è l’ampiezza del guadagno di canale dell’utente k sulla n-esima sottoportante, f c è la potenza necessaria (energia per simbolo) per la _k( ) ricezione del bit/simbolo c quando il guadagno di canale è uguale a 1; tale valore è

correlato alla qualità di servizio (QoS) richiesta dall’utente (probabilità d’errore).

Per risolvere il problema di minimizzazione appena definito, Wong et al. [2] considerano una formulazione simile:

[ ] [ ] , , , , 2 0, 1 1 , 0,1 min ( ) k n k n N K k n T k k n c M n k k n P f c ρ ρ α ∈ _{= =} ∈ =

∑∑

(2.14) Si nota che la condizione per cui ck n, può assumere solo valori interi nell’insieme

{

0,1, 2,..., M

}

=

D viene rilassata in modo che ora c_{k n,} possa assumere qualsiasi valore reale tra 0 ed M. Inoltre viene introdotta la variabile ρk n, che indica se vi è

assegnazione (allora vale 1) oppure no (allora vale 0):

, , 1 se =0 0 altrimenti k n k n c ρ _{= ⎨}⎧ ⎩ (2.15)

Anche questa condizione viene rilassata e si ha che ρ_{k n,} può assumere qualsiasi valore tra 0 e 1.

C1: , , 1 N k k n k n n R ρ c = =

∑

per tutti k∈

{

1,...,K

}

(2.16) C2: _, 1 1 K k n k ρ = =

∑

per tutti n∈

{

1,...,N

}

(2.17) Il problema così formulato è di trattazione relativamente più semplice e, introducendo alcune nuove variabili, è possibile ricondurre il problema di ottimizzazione ad un problema di minimizzazione convessa, risolvibile con tecniche di ottimizzazione standard utilizzando i moltiplicatori di Lagrange [18].

2.3.3 Soluzione subottima

L’algoritmo presentato da Wong et al. [2] nel 1999 ha un elevato onere computazionale ed è di difficile implementazione. Per risolvere questi problemi, nel 2003 Kivanc et al. [7] propongono un metodo che raggiunge prestazioni comparabili ma senza un’elevata complessità di calcolo.

Viene considerata una singola cella con una Base Station (BS) al centro e più stazioni mobili (MS). L’algoritmo assume la perfetta conoscenza del canale (CSI, Channel State Information) e la presenza di un link su cui BS e MS si scambiano informazioni riguardanti il canale, le sottoportanti allocate e il formato di modulazione utilizzato. Anziché affrontare direttamente il complesso problema dell’allocazione congiunta di potenza, sottoportanti e formato di modulazione, vengono proposti due algoritmi distinti che utilizzano informazioni sul canale e sul rate dei vari utenti per trovare una soluzione

prossima a quella ottima. Il problema viene quindi diviso in due step: STEP 1: RESOURCE ALLOCATION

Sulla base del rapporto segnale-rumore (SNR) di ogni utente, si determina il numero di sottoportanti che deve essere assegnato ad ogni utente.

STEP 2: SUBCARRIER ASSIGNMENT

Sulla base del canale visto da ciascun utente, si determina il set di sottoportanti da assegnare ad ogni utente.

Risolvendo questi due problemi separatamente, si trova una soluzione buona, ma necessariamente non ottima, che garantisce un certo livello del servizio per ciascun utente.

L’analisi nello specifico degli algoritmi di Allocazione Risorse e di Assegnazione Sottoportanti viene rimandata al capitolo successivo, in cui verrà illustrato l’algoritmo che è stato studiato e implementato; esso si basa, appunto, su un approccio di tipo subottimo e sulla divisione del problema nei due step appena esposti.