Capitolo 2 Architettura di sistema

2.1 Sistema multicellulare

Con sistema multicellulare ci si riferisce ad un contesto in cui una determinata superficie geografica è suddivisa in un certo numero di aree dette celle e nel quale gli utenti appartenenti ad ognuna di esse sono serviti da diverse entità.

In un sistema di comunicazione si ha a disposizione una certa banda; questa risorsa nell’ambito dell’OFDMA è suddivisa in un certo numero di sottobande tra loro ortogonali ognuna delle quali sufficientemente piccola da fare in modo che ogni utente sperimenti su ciascuna di esse un fading piatto in frequenza.

In un sistema a singola cella (Fig.2.1) tutte queste sottobande, o sottoportanti, sono assegnate in maniera ortogonale agli utenti del sistema e non sussistono quindi problemi d’interferenza dato che queste non si sovrappongono.

In un sistema composto da un numero maggiore di celle la situazione è più complessa; infatti, in ogni cella, si vuole sfruttare a pieno la banda che si ha a disposizione o meglio tutte le sottobande.

Nascono quindi inevitabilmente problemi d’interferenza da accesso multiplo dovuti al fatto che una determinata sottobanda sarà utilizzata da una quantità di utenti pari al numero di celle del sistema.

E’ perciò evidente che in questa tipologia di sistemi la gestione di utenti e risorse risulta particolarmente complicata ed è quindi argomento di grande interesse l’ideazione di strategie che gestiscano in maniera intelligente i rapporti tra le varie entità in gioco.

L’OFDMA è una tecnica di accesso multiplo che si è dimostrata in grado di affrontare i problemi inerenti i sistemi multicella22 e per questo motivo in questi contesti il suo impiego è largamente diffuso.

Nei sistemi multicellulari i canali di propagazione tra le varie BS e gli utenti sono tra loro indipendenti; di conseguenza questi ultimi sperimenteranno su una stessa sottoportante guadagni tra loro incorrelati che potranno quindi anche essere di entità molto diversa (fino a più ordini di grandezza).

Si potrà così verificare il caso che una sottobanda particolarmente vantaggiosa per un utente risulti particolarmente svantaggiosa per un altro.

Affiancando all’OFDMA un’allocazione di risorse dinamica eseguita sulla base della conoscenza dei canali sperimentati da tutti gli utenti è possibile sfruttare, per ottimizzare la gestione delle risorse del sistema, il fenomeno appena illustrato noto come diversità di canale.

2.2 Problema dell’allocazione

Il problema dell’allocazione consiste nel derivare una corrispondenza tra utenti e risorse a disposizione.

Questo obiettivo può essere raggiunto in diversi modi a seconda dei requisiti di sistema.

Gli approcci fondamentali sono due:

i) Allocazione che massimizza il rate complessivo detto approccio RA, cioè rate adaptive.

ii) Allocazione che minimizza la potenza totale impegnata nel sistema detto approccio MA, cioè margine adaptive.

Quelli appena visti sono problemi rispettivamente di massimo e minimo vincolato, applicati su una certa funzione obiettivo.

Entrambi questi approcci si scontrano con un concetto di essenziale importanza, ovvero la fairness.

Nell’esecuzione di un’allocazione dobbiamo infatti, a meno di requisiti di sistema diversi, cercare di trattare con la massima equità ogni utente del sistema; questo significa fare in modo che ogni utente abbia a disposizione lo stesso rate.

Utilizzando più formati di trasmissione avremo che, definendo N come numero di risorse disponibili, K come numero di utenti del sistema, Ω = {1,2,……,F} come l’insieme dei formati in uso, bk,f(n) come indicatore che assume valore 1 se l’n-esima risorsa è assegnata al k-esimo utente con formato di trasmissione f e 0 altrimenti:

_, 1

( )

( )

f b

n

r k

⋅

=

∑

∑

Utilizzando invece lo stesso formato di trasmissione per tutti gli utenti:

1

( )

( )

b n

r k

=

∑

Dove r(k) è il rate assegnato all’utente k che coincide nel caso della (2.2.2) con il numero di sottoportanti assegnate allo stesso.

Per avere la massima fairness dovremmo avere:

r k

( )

= =1,..., Κ

r

,

k

Per motivi che verranno illustrati nei paragrafi successivi questo non sarà sempre possibile.

Una volta deciso come lavorare sulla funzione obiettivo rimane da scegliere se utilizzare in trasmissione un unico formato (SF) o più formati (MF).

Questa scelta risulta essere critica per il funzionamento del sistema poiché condiziona in modo significativo l’implementazione e la dinamica di un algoritmo; infatti, nel caso che si decida di utilizzare più formati trasmissivi, un solver, nell’eseguire un’allocazione per una determinata istanza, disporrà di un numero maggiore di gradi di libertà. Chiaramente questo comporterà una maggiore complessità, dato che, mentre nel caso di utilizzo di un singolo formato l’algoritmo si deve solamente occupare di quali sottoportanti assegnare ad ogni utente, nel caso di un approccio a formato multiplo oltre a questo il solver dovrà

decidere quante sottoportanti assegnare ad ogni utente e che tipo di costellazione dei simboli utilizzare su ognuna di queste.

Con un approccio SF il sistema non è in grado di adattare il suo formato alla qualità del canale assegnato e di conseguenza non riesce a sfruttare a pieno la diversità.

In questo modo si assegna, per avere fairness, la medesima quantità di risorse a tutti gli utenti (Fig.2.2); avremo quindi che gli utenti in generale più svantaggiati, ossia gli utenti al bordo della cella, o edge user, creeranno interferenza su un numero limitato di sottoportanti.

Figura 2.2 - Esempio d’allocazione di risorse in una cella usando SF con N=16

e K=4

D’altro canto gli edge user dovranno raggiungere su ogni sottobanda a loro allocata l’SNR necessario per poter utilizzare il formato scelto e di conseguenza su subcarrier particolarmente sfavorevoli saranno costretti a trasmettere con elevati livelli di potenza.

L’ultima nota d’interesse per quanto riguarda l’utilizzo di un singolo formato è che con questa scelta si hanno un numero minore di variabili nel problema d’allocazione rispetto a quelle che avremmo utilizzando

più formati trasmessivi; in questo modo l’onere computazionale risulta sostanziosamente ridotto.

Usando invece un approccio MF si tende in una cella ad assegnare più risorse usando costellazioni più piccole agli utenti con path gain più critico, ovvero agli edge user, e poche risorse usando però costellazioni più grandi agli utenti con i canali migliori ossia quelli vicini alla BS (Fig.2.3).

Figura 2.3 - Esempio d’allocazione di risorse usando MF con N=16 e K=4

In un sistema a singola cella l’utilizzo di più formati risulta essere l’approccio ottimo ma in un sistema multicella, con il rispetto del trend prima illustrato, avremo che le sottoportanti critiche saranno in numero maggiore rispetto a quelle che si hanno utilizzando un solo formato. A prescindere dalle scelte effettuate una costante nei moderni algoritmi è l’utilizzo di una formulazione LP, cioè mediante il linear programming, del problema d’allocazione di risorse della quale parleremo in dettaglio nei paragrafi seguenti.

Una cosa di fondamentale importanza parlando di allocazione di risorse è il calcolo delle potenze impegnate nel sistema

Per poter arrivare a determinarle vanno fatte alcune ipotesi preliminari sullo stesso:

*) Utilizziamo la capacità di Shannon come misura del rate raggiungibile da un certo utente su una determinata sottoportante.

*) Prendiamo in considerazione il tratto di downlink.

*) Ipotizziamo la conoscenza del CSI, cioè del channel state

information.

*) Ipotizziamo la conoscenza dell’ammontare d’interferenza all’interno del sistema su ogni sottoportante da parte di ciascun utente.

*) Ipotizziamo di utilizzare un formato unico per tutti gli utenti.

Dato un certo SINR, cioè un certo signal to noise and interference ratio, la capacità di canale (efficienza spettrale) raggiungibile in bit/s/Hz è:

2

log (1

SINR

)

η

=

+

R

= ⋅

η

B

Sotto le ipotesi fatte, il SINR visto dall’utente k posizionato nella cella j sulla sottoportante n è: 2 ( ) , 0 ,

( )

( )

( , )

( )

P

n G

n

SINR k n

B N

I

n

⋅

=

⋅

+

Dove Pkj(n) è la potenza trasmessa dalla BS nella cella j sulla

sottoportante n verso l’utente k, Gk,j(n) è il guadagno di canale tra l’utente k e la BS nella cella j sulla sottoportante n e N0 è la densità spettrale di potenza del rumore bianco.

Per quanto riguarda l’interferenza avremo invece:

2 ( ) , , 1

( )

( )

( )

I

n

P

n G

n

=

_∑

⋅

Dove J è il numero di celle e quindi il numero di BS del sistema.

A questo punto sfruttando le ipotesi di sistema ed invertendo la (2.2.8), si è in grado di calcolare quali sono i minimi valori di Pk(j)(n) richiesti per supportare l’efficienza spettrale η:

( ) 0 , 2 ,

( )

( )

( , )

( )

B N

I

n

P

n

SINR k n

G

n

⋅

+

=

⋅

Una volta calcolate queste variabili per ogni valore di k e di n, si ha in mano uno strumento molto importante ai fini della determinazione dell’allocazione che ottimizza la nostra funzione obiettivo; infatti, le

potenze sono inserite in una matrice, detta matrice dei costi, che utilizzata come parametro permetterà alla funzione di LP di determinare l’allocazione ottima cioè, nel nostro caso, l’allocazione che minimizza la potenza totale impegnata nel sistema.

2.3 Algoritmo ottimo

L’algoritmo ottimo, cioè quello che permette la migliore ottimizzazione possibile della funzione obiettivo, ha bisogno di avere informazioni sullo stato di tutto il sistema.

Un solver di questo tipo dovrà quindi essere di tipo centralizzato, dato che, algoritmi distribuiti, che lavorano in maniera indipendente a livello di singola cella, non possono disporre di tali informazioni.

Nonostante il fatto che le sue prestazioni in termini di risultati siano ineguagliabili, il suo onere computazionale lo rende inutilizzabile ai fini pratici; questo metodo rimane comunque uno strumento molto utile come benchmark per algoritmi sub-ottimi.

Descriviamo formalmente il problema in uno scenario multicella facendo uso di un singolo formato trasmissivo.

Abbiamo un set di subcarrier {1, 2, …, N}, un set di celle {1, 2, …, J} e per ogni cella j un set di utenti Uj = {1, 2, …,ij} con U =

1 J j j

U

∪

Chiamiamo bk(n) una variabile binaria intera che assume valore 1 se l’utente k è assegnato alla sottoportante n (0 altrimenti) ed usiamo

Pk(j)(n) in riferimento alla (2.2.10).

{ }

1) min

( )

2)

( ) 1,

,

3)

( )

( )

4)

( )

0,

,

5)

( )

0,1

,

,

P n

b n

j n

b n

r k

P n

k n

b n

k n

∑

≤ ∀

∑

=

∑

≥ ∀

∈

∀

⎧

⎪

⎪

⎪

⎪

⎨

⎪

⎪

⎪

⎪

⎩

Dove l’indice j in Pk(j)(n) è omesso per semplicità di notazione in quanto non aggiungerebbe informazioni alla (2.3.1).

Per capire il funzionamento dell’algoritmo analizziamo il significato di tutte le espressioni all’interno del sistema:

1) Espressione fondamentale del sistema, rappresenta la minimizzazione della funzione obiettivo.

2) Impone che al più un utente per cella sia assegnato ad una determinata sottoportante.

3) Impone che esattamente r(k) sottoportanti siano assegnate ad ogni utente k; volendo fairness ed usando un singolo formato r(k) = r per ogni k.

4) Questa è una condizione ovvia, potenze negative sarebbero risultati inconsistenti.

In realtà quella appena vista è una formulazione ILP23 del problema, ma una soluzione percorribile è quella di riportarsi ad una forma LP tramite rilassamento delle condizioni del problema originale.

Più precisamente si opera sul vincolo numero cinque del sistema (2.3.1) permettendo alla variabile bk(n) di assumere qualsiasi valore compreso tra 0 ed 1 estremi inclusi; il nuovo vincolo si può riscrivere:

b n

( ) [0,1]

∈

Dall’osservazione del sistema (2.3.1) si può intuire la ragione dell’ottimalità dell’algoritmo.

Osservando l’espressione numero 1) del sistema, si vede che si lavora sulla minimizzazione della potenza complessiva impegnata in tutto il sistema tenendo in considerazione tutte le celle.

Il comportamento appena citato è al contempo la ragione delle eccellenti prestazioni dell’algoritmo e la causa della sua elevata complessità computazionale.

Per far fronte a questo ostacolo di solito si tende a far riferimento a soluzioni distribuite o solamente semi-centralizzate, che saranno prese in esame nel dettaglio nei capitoli successivi.

2.4 Algoritmo LP:

Come si può intuire dal nome un algoritmo LP risolve un problema di programmazione lineare:

min

⋅

f b

2)

3)

A b c

A b c

l

b u

1)

⋅ ≤

⎧

⎪

_{⋅ =}

⎨

⎪

_{≤ ≤}

⎩

Dove f, b, c, ceq, lb ed ub sono vettori, mentre A ed Aeq sono matrici. Osservando la (2.3.1) si può capire in che modo una formulazione come quella rappresentata dalla (2.4.1) e dalla (2.4.2) può essere utilizzata per risolvere un problema di allocazione di risorse.

Concentriamoci sui parametri di maggiore interesse:

*) Con la (2.4.1) si rappresenta il vincolo 1) della (2.3.1) con f pari al vettore dei costi ottenuto tramite reshaping su un’unica riga della matrice dei costi (figura 2.4) e b pari al vettore, delle stesse dimensioni e struttura di f, contenente le assegnazioni restituite dall’algoritmo LP.

Figura 2.4 – Struttura del vettore dei costi f

*) Con il vincolo 1) della (2.4.2) si rappresenta il vincolo 2) della (2.3.1) (in realtà sono N vincoli, uno per ogni sottoportante); questo è possibile utilizzando un’opportuna matrice A (figura 2.5) ed un vettore c di N elementi tutti uguali e pari ad uno.

Figura 2.5 – Costruzione della matrice A

*) Con il vincolo 2) della (2.4.2) si rappresenta il vincolo 3) della (2.3.1); Aeq è una matrice costruita come in figura 2.6, mentre ceq è un vettore contenente i rate assegnati agli utenti (r(1), r(2),…, r(K)) .

Figura 2.6 – Costruzione della matrice Aeq

*) Con il vincolo 3) della (2.4.2) si rappresenta il vincolo 5) della (2.3.1); in realtà ciò che si implementa è il vincolo rilassato illustrato nella (2.3.2) con lb ed ub vettori rispettivamente composti da tutti 0 e tutti 1.

Questo dimostra intuitivamente come è possibile utilizzare la formulazione LP per risolvere i problemi di allocazione di risorse; la (2.4.2) rappresenta una struttura generica della formulazione, infatti il numero di vincoli dipende dal tipo di strategia d’allocazione che si intende utilizzare.

Il vettore fornito dall’algoritmo LP, cioè il vettore b, combinato con la matrice dei costi (Fig.2.7), permette di capire quale sia la potenza impegnata complessivamente nel sistema.

In figura 2.7 si può vedere una parte di una matrice dei costi, sulle righe abbiamo gli utenti, mentre sulle colonne abbiamo le sottoportanti, nella casella è riportato il costo dell’associazione utente-risorsa relativa.

La dimensione della matrice dei costi e quindi l’onere computazionale della funzione di programmazione lineare, dipendono sia dal numero di vincoli sia dalla tipologia d’algoritmo d’allocazione usata24.

2.5 Problema del controllo del carico in sistemi

centralizzati

In generale, una volta ottenuta un’allocazione da un opportuno algoritmo, non è detto che questa sia una soluzione consistente del problema.

Potremmo infatti verificare che il sistema lineare da risolvere, con i vincoli da noi imposti, risulti unfeasible; solitamente questa situazione si verifica, nei sistemi centralizzati, per alte efficienze spettrali e per basse efficienze spettrali ma solo in alcuni casi particolarmente complessi. Mentre nei sistemi distribuiti si fa uso di tecniche di rilassamento dei vincoli che permettano di arrivare alla convergenza dell’allocazione, nei sistemi puramente centralizzati se il sistema risulta unfeasible si rinuncia al tentativo di trovare un’allocazione per quella particolare istanza.

Questo procedimento non risulta problematico al fine dell’analisi prestazionale di un algoritmo dato che in generale per ogni valore di efficienza spettrale si generano un gran numero di istanze su cui mediare.