Capitolo 3 Algoritmi di allocazione risorse

Capitolo 3

Algoritmi di allocazione risorse

3.1

Allocazione delle risorse per sistemi OFDM

3.1.1

Introduzione

La aleatoriet´a del canale multipath rappresenta uno degli elementi che pi´u limita le prestazioni dei sistemi radio di comunicazione. Sulla base di queste considerazioni lo sviluppo di tecniche di allocazione delle risorse (Resource Allocation - RA) di tipo channel-aware rappresenta uno dei campi di ricerca pi´u importanti. In tali metodi di allocazione la strategia generalmente diffusa consiste nell’ assegnare in modo dinamico potenza e formato di modulazione di un utente adattandoli alla realizzazione del canale.

Gli algoritmi di RA operano sfruttando tutte le informazioni a disposizione del trasmettitore per ottimizzare l’ utilizzo delle risorse radio, ricordando che esse, oltre ad essere limitate da vincoli fisici, devono anche essere condivisi-bili.

Per fare un esempio, nelle applicazioni OFDM la probabilit´a di errore ´e lim-itata dalle sottoportanti pi´u attenuate del canale. Su tali sottoportanti, per

limitare la probabilit´a di errore, pu´o risultare conveniente utilizzare un for-mato di modulazione ’robusto’, come ad esempio una modulazione di tipo BPSK, anche se poco efficiente dal punto di vista spettrale.

In altri casi la strategia migliore potrebbe essere quella di non utilizzare af-fatto le sottoportanti pi´u attenuate.

Nel caso in cui il canale sia invece caratterizzato da una scarsa attenuazione, il trasmettitore pu´o essere in grado scegliere un formato di modulazione con maggiore efficienza, pur rispettando un vincolo sulla probabilit´a di errore massima consentita.

Nel caso multi-utente l’ allocazione delle risorse presenta un ulteriore gra-do di libert´a, potengra-do scegliere anche quale sotto-canale assegnare ad ogni utente. In tal caso il sistema pu´o trarre vantaggio dalla cos´ı detta ’diversit´a multi-utente’.

3.1.2

Allocazione singolo-utente

Prendiamo in esame un sistema OFDM singolo-utente in cui sono presenti un unico trasmettitore ed un unico ricevitore. All’ uscita del dispositivo di FFT, il segnale y(n) ricevuto sulla n-esima sottoportante risulta essere dato da:

y(n) =qP (n)anH(n) + n(n), n = 0, 1, ..., N − 1 (3.1)

avendo indicato con P (n) la potenza allocata e con an il simbolo trasmesso.

H(n) rappresenta il guadagno complesso di canale e n(n) il contributo del

rumore termico, modellato come una variabile aleatoria complessa gaussiana a media nulla e varianza σ2_.

In notazione vettoriale si ha: y=SAH+n

avendo indicato con S e A due matrici diagonali di dimensione N che hanno sulla diagonale principale rispettivamente la radice quadrata della potenza

allocata ed i simboli di modulazione.

Utilizzando la conoscenza di H, il trasmettitore adatta la potenza e il for-mato trasmissivo su ciascuna sottoportante secondo un prefissato criterio di ottimalit´a. In pratica, la RA richiede che il sistema compia le seguenti operazioni:

• Acquisizione delle informazioni sullo stato del canale. Per ef-fettuare l’ allocazione ´e infatti necessario che il trasmettitore conosca i guadagni su tutte le sottoportanti. La disponibilit´a di questa infor-mazione dipende dal tipo di duplexing utilizzato fra uplink e downlink. In modalit´a time division duplexing (TDD) le trasmissioni in uplink e downlink avvengono in tempi diversi sulla stessa banda di frequen-za e il sistema pu´o sfruttare la reciprocit´a del canale. In particolare, assumendo che il canale vari lentamente, il trasmettitore pu´o utiliz-zare per la RA le stime di canale effettuate durante la precedente fase di ricezione. In modalit´a frequency division duplexing (FDD), invece, le trasmissioni uplink e downlink avvengono contemporaneamente su bande di frequenza distinte ed i guadagni di canale risultanto essere pertanto diversi. In questo caso ´e necessario un canale di ritorno per informare il trasmettitore sulla effettiva realizzazione del canale.

• Scelta dei parametri trasmissivi. La RA ha il compito di deter-minare la potenza P (n) e il formato di modulazione b(n) trasmesso su ciascuna sottoportante formalizzato nella seguente maniera: asseg-nata una funzione obiettivo f(b,P) che caratterizza le prestazioni del sistema si devono trovare i vettori b e P che la rendano massima rispet-tando alcuni vincoli riguardanti la potenza massima, il rate minimo o la probabilit´a di errore massima consentita.

• Segnalazione. Una volta noti i vettori b e P pu´o essere necessario comunicarli al ricevitore. Ci´o pu´o avvenire utilizzando un canale logico di segnalazione.

3.1.3

Waterfilling

Uno dei problemi di allocazione di risorse pi´u noto consiste nel distribuire la potenza sulle varie sottoportanti in modo da massimizzare la capacit´a del sistema rispettando il vincolo sulla potenza totale trasmessa. La capacit´a di informazione di un determinato canale ´e il massimo rate informativo che pu´o essere trasmesso su quel canale con probabilit´a di errore arbitrariamente bassa per un certo rapporto fissato segnale-rumore (Signal to Noise Ratio SNR). Nonostante la capacit´a di canale abbia un valore prettamente teorico in quanto raggiungibile soltanto mediante l’ utilizzo di parole di codice infini-tamente lunghe, rappresenta un valido strumento per detrminare un limite superiore alle prestazioni di un qualsiasi sistema trasmissivo.

Le N sottoportanti di un sistema OFDM posssono essere considerate come altrettanti canali AWGN (Additive White Gaussian Noise) paralleli per cui la capacit´a complessiva C si ottiene come somma delle capacit´a delle singole sottoportanti e vale C = N −1_X n=0 log à 1 + |H(n)|2P (n) σ2 ! (3.2)

L’ obiettivo che ci prefiggiamo consiste nel determinare il vettore P che mas-simizza la capacit´a rispettando il vincolo sulla potenza complessiva trasmessa

Ptot, ovvero P = arg max e P {C ³ e P´} (3.3) N −1_X n=0 e P = Ptot (3.4)

avendo indicato con P un valore di tentativo per P(n). Se il trasmettitoree non disponesse di alcuna informazione sullo stato del canale, la RA ottima sarebbe quella di tipo uniforme, che consiste nel trasmettere con la medesima potenza Ptot/N su tutte le sottoportanti.

Quando per´o il ricevitore conosce lo stato del canale, il problema sopra espos-to pu´o essere risolespos-to in forma chiusa utilizzando la tecnica dei moltiplicaespos-tori di Lagrange, e la soluzione risulta

P (n) = Ã µ − σ 2 |H(n)|2 !₊ (3.5)

avendo indicato con

(x)+ _{= max(0, x) (3.6)}

µ = Ptot+ σ

2PN0−1

n=0 |H(i1in)|2

N0 (3.7)

N0 rappresenta il numero delle sottoportanti, di indici i0, ..., iN0−1per le quali

risulta P (n) > 0.

La soluzione proposta viene denominata ’waterfilling’, perch´e 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 la quantit´a di potenza da allocare sulle varie sottoportanti.

In particolare, si pu´o notare che la maggior parte della potenza viene allo-cata sui canali migliori, mentre se una sottoportante risulta essere troppo attenuata pu´o non essere utilizzata affatto. Quando il livello dell’ acqua µ ´e basso, e quindi quando SNR ´e piccolo, 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 waterfilling tende a distribuire asintoticamente la potenza in maniera uniforme.

• la capacit´a per la n-esima sottoportante C(n), definita come C(n) = log(1 + P (n)|H(n)|_σ2 2) ´e un numero reale e quindi d´a una indicazione so-lamente approssimativa del numero di bit per simbolo, che invece ´e rappresentato tramite un numero intero;

• la capacit´a rappresenta il massimo rate che garantisce una probabilit´a di errore asintoticamente nulla. Nei sistemi pratici, invece, la proba-bilit´a di errore necessaria a garantire una certa QoS ´e diversa da ze-ro e cosituisce anch’ essa un ulteriore vincolo nella formulazione del problema.

In questi casi la RA ottima pu´o essere ottenuta tramite tecniche di program-mazione lineare o convessa.

3.1.4

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´o assegnare ad ognuno di essi le sottoportanti meno attenueate.

Poich´e i guadagni di canale dei vari utenti sono indipendenti tra di loro, una sottoportante che risulta essere molto attenuata per un dato utente pu´o risultare particolarmente vantaggiosa per un altro, garantendo cos´ı al sistema un certo guadagno di diversit´a, che in questo caso prende il nome di ’diversit´a multi-utente’.

obi-ettivo di ottimizzare grandezza diverse come potenza, probabilit´a di errore o rate informativo.

Per valutare l’ impatto complessivo degli algoritmi di allocazione multi-utente bisogna anche tenere conto della loro complessit´a e della quantit´a di infor-mazioni di cui hanno bisogno. A causa del gran numero di variabili da gestire, la complessit´a di questi algoritmi ´e di qualche ordine di grandezza superiore a quella degli algoritmi di allocazione singolo-utente. Si deve inoltre con-siderare che l’ allocatore e gli utenti devono scambiarsi una grande mole di informazioni.

In uno scenario in cui vi siano K utenti ed N sottoportanti disponibili, l’ al-locatore deve conoscere a priori gli N guadagni di canale di tutti i K utenti, e tali informazioni devono essere scambiate su un canale di controllo ausil-iario. In tal caso, infatti, la reciprocit´a del canale garantita dalla modalit´a TDD non si rivela utile in quanto ´e necessario che l’ allocatore conosca il canale su tutta la banda disponibile e non solo sulle sottoportanti su cui ´e stata effettuata l’ ultima ricezione. Infine, compiuta l’ allocazione, ´e ancora necessario comunicare a tutti gli utenti quali siano i canali loro assegnati. Si pu´o dimostrare che la distribuzione delle potenze che massimizza la somma delle capacit´a di tutti gli utenti rispettando i vincoli di potenza per ciascun utente, si ottiene con l’ algoritmo ’waterfilling iterativo’. Tale tecnica asseg-na la potenza a ciascun utente applicando in maniera iterativa la soluzione waterfilling trovata per il caso singolo-utente e considerando i segnali di tutti gli altri utenti come se fossero rumore. A titolo di esempio consideriamo una fase di uplink in cui ciascun utente ´e in grado di trasmettere su tutte le sottoportanti e in cui ogni altro utente viene considerato come interfer-ente. Ad ogni interazione, il j-esimo utente calcola la potenza Pj(n) che deve

trasmettere sulla portante n nel seguente modo: Pj(n) = Ã µ(j) − σ 2 ₊P_{k 6= jP} k(n)|Hk(n)| |Hj(n)|2 !₊ (3.8)

avendo calcolato µ(j) in modo analogo al caso singolo-utente ed avendo in-dicato con Hj(n) il guadagno di canale del j-esimo utente sulla n-esima

sot-toportante. L’ algoritmo viene ripetuto fino a quando la potenza di tutti gli utenti converge ad una soluzione stabile.

Risultati sperimentali mostrano che la distribuzione della potenza dipende dalla distanza fra gli utenti: utenti vicini tendono a disporsi su sottoportanti distinte, mentre utenti lontani tendono ad utilizzare le stesse sottoportanti in quanto inferiscono poco gli uni con gli altri. La tecnica del waterfilling iterativo richiede un numero di operazioni molto grande e la sua applicazione pu´o essere impraticabile gi´a per valori di K ed N relativamente piccoli. Per i motivi gi´a citati a proposito dell’ allocazione singolo utente, la massimiz-zazione della capacit´a in molti casi pratici pu´o non essere il miglior criterio da utilizzare.

Recentemente Letaief [letaief e altri] ha proposto un algoritmo per l’ asseg-nazione congiunta di potenza, sottoportanti e formato di modulazione con l’ obiettivo di minimizzare la potenza complessiva trasmessa rispettando:

• un vincolo sulla probabilit´a di errore, che per ciascu utente deve risultare inferiore ad un dato valore di soglia;

• un vincolo sul rate assegnato a ciascun utente, che deve essere uguale ad un valore prefissato;

• un vincolo sul fatto che una data sottoportante pu´o essere allocata esclusivamente ad un solo utente.

Il problema ´e stato risolto utilizzando tecniche standard di programmazione convessa. La soluzione ottima non risulta per´o applicabile nella pratica a

causa dell’ elevato onere computazionale richiesto. Inoltre, i rate allocati su ogni sottoportante non sono in generale rappresentati da numeri interi. La complessit´a dell’ algortimo proposto da Letaief pu´o essere notevolmente ridotta imponendo che il formato di modulazione utilizzato per la trasmi-sisone sia lo stesso su tutte le sottoportanti, mantenendo comunque i vincoli sul rate globale di ciascun utente.

In questo caso, il problema consiste nell’ assegnare soltanto le sottoportanti ai vari utenti con le rispettive potenze di trasmissione. La soluzione del prob-lema pu´o essere trovata mediane tecniche di programmazione lineare basate sull’ algoritmo del simplesso.

Risultati sperimentali mostrano che nella maggior parte dei casi la perdita di prestazioni risulta essere trascurabile rispetto alla soluzione del problema originale. Intuitivamente, ci´o pu´o essere spiegato considerando che l’ algorit-mo di Letaief, sia nella sua versione originale che nella versione semplificata, beneficia enormemente della diversit´a multi-utente mentre il guadagno che viene ottenuto adattando anche il formato di modulazione ´e trascurabile.

3.2

Allocazione delle risorse nel progetto

PRI-MO

Il livello fisico sviluppato nel progetto PRIMO, si basa su una tecnica di trasmissione multiportante di tipo TDD, una tecnica di tipo OFDM con al-locazione di canale adattiva e con una tecnica di codifica e di modulazione anch’esse di tipo adattivo. In questo scenario, la potenza trasmessa da ogni utente dovrebbe essere allocata sul miglior canale possibile in modo da ot-timizzare le prestazioni dell’ intero sistema. In uno scenario singolo-utente, il miglior canale possibile corrisponde al canale che massimizza il rapporto

Segnale-Rumore (SNR) relativo all’ utente in esame, mentre in uno scenario multi-utente la scelta della miglior allocazione possibile risulta essere meno diretta, dal momento che un utente pu´o avere necessit´a di usare un determi-nato canale. Per questo motivo, ´e necessario definire un criterio globale. Le strategie di allocazione generalmente adottate[10] sono di due tipi:

• margin adaptive

• rate adaptive

L’ ottimizzazione secondo una metodologia di tipo ’margin adaptive’ ha lo scopo di minimizzare la potenza totale trasmessa, dato un certo vinco-lo sul rate per ogni utente nel sistema, mentre l’ ottimizzazione basata su una metodologia di tipo ’rate adaptive’ cerca di massimizzare il rate totale trasmesso dato un certo vincolo di potenza sulla potenza utilizzata da ogni utente.

Molte opere presenti in letteratura [11],[12] cercano di trovare una soluzione ottima al problema dell’ allocazione adattiva delle risorse radio prendendo in considerazione solo le esigenze del livello fisico. In [13] viene presentato un approccio basato sulla programmazione lineare (LP) per la metodologia di allocazione delle risorse di canale disponibili.

I sistemi di Quarta Generazione necessitano della possibilit´a di servire si-multaneamente diverse sorgenti di traffico, ognuna con la proprie specifiche esigenze di QoS. Per questo motivo, risulta necessario e di primaria impor-tanza sviluppare strategie di allocazione delle risorse disponibili in grado di integrare anche le informazioni fornite dal livello MAC. In [14] viene propos-to un algoritmo di allocazione delle risorse di tipo cross-layer, implementapropos-to tramite LP.

attraverso un approccio di ottimizzazione lineare, di cui questa tesi propone una analisi dettagliata.

3.3

Specifiche dell’ algoritmo

Molti algoritmi possono esser definiti per risolvere il problema dell’ allo-cazione delle risorse scegliendo [allocation algorithms for primo system] di-verse funzioni oggetto da ottimizzare e adottando didi-verse tecniche di risoluzione riguardo al problema di ottimizzazione.

Nel progetto PRIMO vengono presentati tre diversi approcci al problema del-l’ allocazione delle risorse che partono da una stessa considerazione iniziale che di seguito andremo ad esporre.

Sia ck,s,t la capacit´a di Shannon associata alla PBU individuata dalle

coordi-nate(s,t) tale che:

1 ≤ s ≤ Ms (3.9)

1 ≤ t ≤ Mt (3.10)

quando il k-esimo utente, o, per meglio dire, l’ utente che ha generato la k-esima richiesta, trasmette con un valore di potenza pari a pk,s,t.

Considerando una trasmissione da BS a MS, la capacit´a ck,s,t pu´o essere

espressa come: c(k, s, t) = FP BUlog2 Ã 1 + pk,s,tGk,s,t pn+ pIk,s,t ! (3.11)

avendo espresso con :

• FP BU un fattore scalare che dipende dalla banda e dalla durata di una

PBU;

• Gk,s,t il guadagno di canale dell’ utentee k-esimo sulla PBU individuata

• pn la potenza di rumore;

• pIk,s,t l’ interferenza dell’ utente k-esimo sulla PBU individuata dalle

coordinate (s,t).

Avendo indicato con Is,t l’insieme degli intereferenti sulla PBU individuata

dalle coordinate(s,t), e per ogni BS interferente i ∈ Is,t , con pi,s,t il valore

della potenza trasmessa e con Gi,k,s,t il guadagno di canale fra l’ interferente

e la MS ricevente.

Sulla base di queste considerazione il valore della potenza totale legata all’ interferenza risulta essere pari a :

pIk,s,t = X i∈Is,t

pi,s,tGi,k,s,t (3.12)

Avendo indicato con bk,s,t il bitload sulla PBU individuata dalle coordinate

(s,t) per la k-esima richiesta, dal momento che ck,s,t rappresenta il limite

teorico per il numero di bit di informazione che pu´o essere trasmesso sulla PBU individuata dalle coordinate (s,t) si ha:

bk,s,t ≤ αck,s,t (3.13)

dove il fattore α < 1 prende in considerazione i limiti dell’ attuale livello di implementazione.

Indicando con χk,s,t la funzione adottata per allocare alla k-esima richiesta

la PBU individuata dalle coordinate (s,t) si ottiene:

χk,s,t =     

1 nel caso in cui la PBU(s,t) venga assegnata all’ utente k

0 altrimenti.

(3.14)

Per questo motivo il suddetto vincolo sul rate pu´o essere formalizzato nel modo seguente: rk,min≤ 1 Tf Ms X s=1 Mt X t=1 bk,s,tχk,s,t ≤ rk,max, (3.15)

oppure, in altri termini, il bit rate allocato ad ogni richiesta deve trovarsi all’ interno dei limiti imposti e deve inoltre essere verificata la condizione

1 Tf K X k=1 Ms X s=1 Mt X t=1 bk,s,tχk,s,t = rtot , (3.16)

Tale vincolo indica che il rate allocato totale deve essere uguale a quello richiesto dallo scheduler. Un ulteriore vincolo sull’ allocazione delle risorse consiste nel fatto che in ogni cella ogni PBU pu´o essere allocata solamente ad un singolo utente. Tale vincolo pu´o essere espresso come

K X k=1

χk,s,t ≤ 1 ∀(s, t) . (3.17)

Con le premesse sopra esposte, l’ allocazione delle risorse pu´o essere formula-ta come un problema di ricerca congiunformula-ta dei valori di χk,s,t,che rappresenta

l’ allocazione del canale, di bk,s,t, che rappresenta il bit loading e di pk,s,t, che

rappresenta il power loading, in grado di verificare i vincoli sopra riportati e di ottimizzare una opportuna funzione oggetto, generalmente basata sul valore della potenza totale trasmessa.

In fig.3.1 viene riportata la griglia tempo-frequenza utilizzata per l’ allo-cazione delle risorse nel sistema PRIMO. Le 256 sottoportanti occupano una banda di 20 MHz, mentre la durata del frame viene considerata pari a 10ms. Le risorse disponibili vengono raggruppate in Physical Base Unit (PBU). Ogni PBU ´e composta da 16 sottoportanti e 20 slot OFDM. La banda e la durata della PBU vengono scelte in modo da essere inclusi sia nella banda di coerenza sia nel tempo di coerenza.

3.4

Algoritmo Efficiency Maximization - EM

L’ algoritmo di tipo Efficiency Maximization(EM) si basa su un approccio al problema dell’ allocazione delle risorse proposto da [5 Pd]. Rispetto ad

Fig. 3.1: Griglia delle risorse tempo-frequenza

esso[Pd] per´o rappresenta una approssimazione in modo da poter passare da una risoluzione del problema di tipo non lineare ad una risoluzione di un problema di tipo lineare fissando a priori[Primo alg.] il valore della potenza totale di trasmissione pk,s,t. In questo modo viene fissato anche il bit load

bk,s,t per ogni PBU e per ogni richiesta.

Il processo di allocazione consiste nell’ assegnare una o pi´u PBU ad ogni flusso k e nel fissare il corrispettivo valore della potenza di trasmissione e del bit load. L’algoritmo di allocazione deve garantire il rate richiesto rk da ogni

k-esimo flusso. A questo scopo, i rate delle richieste vengono raggruppati in due insiemi, denominati rispettivamente ’OLD’ e ’NEW’.

L’ insieme ’OLD’ contiene i flussi che risultano gi´a essere stati allocati in alcuni frame precedenti e che sono ancora attivi. Le PBU allocateai flussi in questo insiemne vengono mantenute anche nei frame successivi. Comunque,

la potenza di ogni PBU allocata ´e indipendentemente adattata in modo da seguire le variazioni del canale e della interferenza. Se il valore della potenza media totale necessario alla soddisfazione del requisito di rate minimo del flusso in esame risulta essere pi´u grande di una determinata soglia, tutte le PBU ad essa associata vengono deallocate ed i rispettivi flussi vengono inseriti nell’ insieme ’NEW’.

L’ insieme ’NEW’ contiene i corrispondenti rate delle richieste dai nuovi flussi originati all’ interno del frame precedente o dei flussi che devono essere riallocati. I rate delle richieste che fanno parte dell’ insieme ’NEW’ vengono allocati seguendo la procedura sotto riportata. Diseguito viene riportato l’ algoritmo utilizzato:

User removal algorithm [1] count ← 0 stableAll ← 1 i ← 1, Ncells

NewAll(i) ← allocate(i) count ← count+1 NewAll(i) 6= OldAll(i) stableAll ←

0 count > Nout removeUser(i) count ← 0 OldAll(i) ← NewAll(i) stableAll removeUseri Osc(i) ← {j ∈ U(i)|NewAll(i, j) 6= OldAll(i, j)} Switch off the user in Osc(i) transmitting at the highest power level

Considearndo un livello comune di potenza pi

tx, la BS calcola il valore

della capacit´a associata ad ogni PBU per ogni utente. Si suppone che ogni PBU possa essere caricata col pi´u alto bit load possibile, che, in questa prima formulazione analitica, viene preso uguale alla capacit´a espressa in termini di Shannon.

Si definisce con Ck il vettore contenente i valori delle capacit´a associate al

k-esimo utente, o per meglio dire, l’ utente che ha generato la k-esima richiesta e con ck,s,t l’ elemento di Ck che rappresenta la capacit´a di Shannon associata

alla PBU individuata dalle coordinate (s,t) per il k-esimo utente, con il dato valore della potenza di trasmissione pi

tx.

Effi-cienza Ek per la k-esima richiesta di dimensione (MsxMt) i cui elementi ek,s,t

sono dati da:

ek,s,t =

bk,s,t P_K

k=1bk,s,t

. (3.18)

Si deve notare come il valore di ek,s,t sia in grado di fornire una

indi-cazione riguardo all’ efficienza dell’ alloindi-cazione della PBU individuata dalle coordinate(s,t) per l’ utente k-esimo prendendo in considerazione tutti gli altri utenti appartenenti alla cella in esame.

Indichiamo con Ak la matrice di dimensione (MsxMt) delle allocazioni delle

risorse per la k-esima richiesta, i cui elementi ak,s,t risultano:

ak,s,t =     

1 nel caso in cui la PBU(s,t) venga assegnata all’ utente k

0 altrimenti.

(3.19)

dal momento che una singola PBU pu´o essere allocata ad un singolo utente, deve essere verificata la condizione:

K X k=1

ak,s,t ≤ 1 (3.20)

Il problema di ottimizzazione pu´o quindi essere formulato nel modo seguente. Funzione oggetto: min K X k=1 Ms X s=1 Mt X t=1 ak,s,t(1 − ek,s,t) (3.21)

con i vincoli rappresentati da: 1 Tf Ms X s=1 Mt X t=1 ak,s,tck,s,t ≥ rk (3.22) K X k=1 ak,s,t ≤ 1, ∀(s, t) (3.23)

dove con Tf abbiamo indicato il valore della durata del frame. Se non viene

ripetuto utilizzando un pi´u alto livello di potenza dato dalla seguente formula iterativa:

pi+1

tx = pitx+ δp (3.24)

per ogni PBU.

Tale procedura inizia settando il valore pi

tx= pmintx e ripetendo tale algoritmo

fino a quando tutte le richieste sul rate non risultano soddisfatte o fino a quando non viene raggiunto il valore massimo della potenza trasmessa pos-sibile, pari a pmax

tx .

La soluzione esatta di questo problema di minimizzazione risulta di diffi-cile attuazione, per questo motivo ´e stato sviluppato un algoritmo ’greedy heuristic’. Dalle simulazioni effettuate si evince che il comportamento di tale algoritmo ´e molto simile a quello che porta alla soluzione ottima, ottenuta tramite programmazione lineare.

Viene di seguito descritto il metodo euristico adottato nell’ algoritmo di al-locazione EM.

Questo algoritmo seleziona una richiesta k-esima e poi alloca ad essa una PBU. Quindi aggiorna di conseguenza le richieste di rate ed il valore delle risorse disponibili. Il criterio di selezione della richiesta e della relativa PBU ´e il seguente.

Per prima cosa, viene calcolata la matrice delle capacit´a per ogni utente assumendo una potenza di trasmissione pi

tx, uguale per tutte le PBU. Ad

ogni passaggio dell’ algoritmo tutte le richieste degli utenti vengono ordinate secondo la metrica:

ηk=

ck,av

rk,rem

(3.25)

Dove con rk,rem abbiamo indicato il bit rate del flusso k-esimo necessario al

conseguimento del minimo rate richiesto rk per il frame corrente, mentre con

nel caso in cui le PBU rimanenti vengano assegnate a tale flusso:

ck,av = X

n,s

ck,n,s(1 − ak,n,s) (3.26)

L’ utente che presenta il minimo valore di ηk viene selezionato per l’

allo-cazione della PBU.

Questa politica ha come scopo quello di servire per primi gli utenti che pre-sentano una pi´u alta richiesta di rate, in rispetto alle risorse disponibili. Una volta selezionato il flusso da servire, questo viene assegnato alla PBU che presenta il pi´u alto valore di efficienza ek,s,t fra quelle non ancora allocate.

La quantizzazione dei bit load ammissibili viene presa in considerazione as-sociando alla PBU selezionata il pi´u alto valore di bj che risulta essere pi´u

piccolo della capacit´a di Shannon. La potenza, infine, viene ricalcolata sulla base del bit load allocato, aggiungendo un valore ulteriore di potenza neces-sario per superare l’errore nella stima dell’ interferenza.

Alla fine di questo step, i valori di ck,av e di rk,rem vengono ricalcolati ed il

processo viene ripetuto fino a quando tutte le richieste di rate degli utenti risultano sodisfatte o fino a quando tutte le PBU risultano essere allocate. Nel caso in cui alcune richieste non vengano soddisfatte, l’intera procedura viene ripetuta partendo da un valore di potenza pari a pi+1tx . L’ incremento

della potenza viene limitato dal valore massimo possibile che viene definito tramite pmax

tx . Oltre questo limite la potenza non pu´o essere ulteriormente

incrementata e l’ algoritmo non ´e in grado di allocare tutti i flussi richiesti. Un aspetto fondamentale di questo algoritmo consiste nella scelta del val-ore iniziale della potenza p0

tx. Un caso particolare viene rappresentato dalla

scelta p0

tx= pmaxtx .

Di seguito viene riportato il diagramma a blocchi dell’ algoritmo di allo-cazione EM:

Request Selection

Allocation and

Constraints check

Max power

selection

Start

PBU Selection

Bitload Selection

Power adaptation

End

3.5

Algoritmo Power minimization by a greedy

heuristic - GH

Seguendo un approccio di ’Power minimization by a greedy heuristic’ (GH), il problema di allocazione delle risorse pu´o essere visto come una scelta di un determinato insieme un un opportuno spazio degli eventi; un evento rappre-senta l’ assegnazione di una determinata PBU ad una data richiesta, a cui viene associato un certo bit load. Definiamo tali eventi Ipotesi di Trasmis-sione(TxHp). Perci´o una TxHp risulta essere determinata una volta noti 4 valori, che in dettaglio sono:

• k, che rappresenta l’ identificatore della richiesta;

• (s,t), che rappresentano le coordinate della PBU in esame;

• b, che rappresenta il bitload.

L’ intero spazio degli eventi risulta quindi essere composto da tutte le TxHp corrispondenti alle PBU inutilizzate. Se K rappresenta il numero delle richi-este pendenti e NB il numero di bit load disponibili, lo spazio degli eventi

risulta pari a K × NB TxHp per ogni PBU non utilizzata.

L’ allocatore determina il valore della potenza totale di trasmissione richiesta corrispondente alla TxHp sulla base del valore di bitload dato e sulla misura dell ’interferenza. Indicando con χk,s,t,b la funzione utilizzata per la selezione

delle TxHp(k,s,t,b) e con pk,s,t,b il corrispondente valore della potenza totale

di trasmissione richiesta, dal momento che in tale algoritmo viene supposto di utiolizzare un unico formato di modulazione su una singola PBU si ha:

X b∈B

Il compito dell’ allocatore consiste quindi nel selezionare una opportuna TxHp in modo da soddisfare i vincoli sul rate e sulla potenza e in modo da minimizzare il valore della potenza totale trasmessa.

Il problema di allocazione pu´o quindi essere formulato come segue:

χ = arg min χ K X k=1 X s,t pk,s,t,bχk,s,t,b (3.28) rk,min≤ b Tf Ms X s=1 Ms X s=1 χk,s,t ≤ rk,min (3.29) b Tf K X k=1 Ms X s=1 Ms X s=1 χk,s,t = rT OT (3.30)

Il problema di minimizzazione pu´o essere risolto tramite una tecnica iter-ativa di tipo ’greedy heuristic’: ad ogni interazione l’ allocatore incrementa il carico trasmesso scegliendo una nuova TxHp fino a quando tutti i vincoli sono rispettati. Ad ogni interazione i quattro valori necessari all’ individu-azione della TxHp, (k,s,t,b), vengono selezionati applicando il seguente cri-terio: si scelgono i parametri (k,s,t,b) che richiedono il minimo incremento della potenza totale trasmessa.

Di seguito viene riportato il diagramma a blocchi dell’ algoritmo GH:

3.6

Algoritmo Power minimization by linear

programming - LO

Il problema dell’ allocazione delle risorse disponibili formulato nel modo:

X b∈B

Fig. 3.3: Diagramma a blocchi algoritmo di allocazione GH

´e rappresentata da una funzione costo e da un insieme di vincoli entrambi lineari. Sulla base di questa considerazione si evince che la funzione obiettivo pu´o essere risolta tramite metodi risolutivi basati sulla programmazione di tipo lineare, che risultano essere molto veloci ed ampiamente utilizzati, come riportato in [14-Primo].

Nel caso particolare in cui venga utilizzato un unico formato di trasmissione (NB) = 1, ´e possibile modellare il problema dell’ allocazione delle risorse

ra-dio come un problema di tipo ’network flow’. Il vantaggio di questo approccio consiste nel fatto che il problema dell ’allocazione pu´o essere risolto tramite il metodo del simplesso, o per meglio dire il ’Network Simplex Metod’ (NSM). Tale metodo rappresenta un adattamento di tale metodo a flussi di rete.

NSM rappresenta il pi´u efficiente metodo di risoluzione per il problema di reti caratterizzate dalla necessit´a di ottenere il minimo costo contemporanea-mente al massimo flusso, come riportato in [15- Primo], e surclassa le altre tecniche esistenti, come ad esempio le relazioni di tipo lineare riportate in [6-primo].

Dopo aver risolto il problema in (3.31) con (NB) = 1, la potenza trasmessa

pu´o essere ulteriormente ridotta rimovendo le condizioni riguardo al fatto che il formato di modulazione trasmesso su ogni sottoportante deve essere esattamente pari ad uno. Infatti, le N(k) PBU allocate alla k-esima richiesta possono essere viste come molti canali gaussiani in parallelo e la distribuzione di potenza ottima pu´o essere trovata formulando l’ algoritmo di tipo ’water-filling’, come mostrato in [primo-4] con rate costante. Partendo dalla figura (3.1) ed adottando il modello sopra esposto possiamo descrivere la formu-lazione dell’ algoritmo come segue.

Indicando il bit rate R(k, i) trasmesso dall’ utente i-esimo sulla k-esima PBU con

R(k, i) = B × C(k, i)

α (3.32)

dove B rappresenta la banda della PBU, C(k, i) la capacit´a, secondo il criterio di Shannon, dell’ utente i-esimo sulla k-esima PBU e il fattore α = Tf rame

TP BU il

rapporto fra la durata del frame e la durata della PBU. La capacit´a C(k, i) viene definita come:

C(k, i) = log₂ Ã 1 + Ptx(k, i)|H(k, i)| 2 BN0 ! (3.33)

dove N0rappresenta la densit´a spettrale di potenza di rumore, mentre H(k, i)

e Ptx(k, i) rispettivamente indicano il guadagno di canale la potenza

trasmes-sa dall’ utente i-esimo sulla k-esima PBU.

Si assume che tuti gli utenti usino lo stesso schema di modulazione e di cod-ifica, e perci´o che trasmettano lo stesso rate R0 su diverse PBU. Quindi, la

potenza che l’ utente i-esimo trasmette sulla k-esima PBU dipende solo dalla qualit´a del canale e assume la seguente forma:

Ptx(k, i) =

BN0

|H(k, i)|2(2

αR0_B−1_{) (3.34)}

L’ allocazione delle risorse disponibili viene conseguita cercando di minimiz-zare la potenza totale trasmessa. Lo scheduler deve passare all’ allocatore le seguenti informazioni:

• Il rate totale da trasmettere nella cella;

• Il rate R0;

• Il rate massimo Rmax e il rate minimo Rmin per ogni pacchetto.

Sotto l’ ipotesi di utilizzare un unico valore del bit rate, i vincoli su Rmax e

Rmin possono essere espressi, in modo equivalente, su Nmax e Nmin, dove

N = dR

R0

e (3.35)

avendo indicato con N il numero di PBU corrispondenti ad un certo rate. Per questo motivo, il problema dell’ allocazione delle risorse radio pu´o essere formulato come un problema di ’network flow’. In questo caso la complessit´a della soluzione ´e di tipo polinomiale e, apparentemente, permette una imple-mentazione di tipo real-time.

In particolare, possiamo adottare il modello del flusso di minimo costo. Il problema di allocazione quindi pu´o esser formalmente esposto come di segui-to riportasegui-to.

Sia

G = (N, A) (3.36)

una rete orientata, definita da un insieme N di n nodi e da un insieme A di m archi orientati. Ad ogni arco (i, j) ∈ A viene associato un costo cij non

negativo che denota il costo per unit´a di flusso sull’ arco in esame. Associamo inoltre ad ogni arco (i, j) ∈ A ad una capacit´a uij, che denota la massima

quantit´a che fluire sull’ arco in esame, denominato anche Upper Bounf (Ub) e lij, che denota la minima quantit´a che fluire sull’ arco in esame, denominato

anche Lower Bounf (Lb).

Associamo inoltre ad ogni nodi i ∈ N un parametro intero b(i) che rappre-senta la tipologie ti flusso associata al nodo in esame:

• b(i) > 0 → i nodo fornitore

• b(i) = 0 → i nodo di transito

• b(i) < 0 → i nodo richiedente

Nel problema di flusso di minimo costole variabili di decisione sono rappre-sentate dai flussi xij, che indicano il flusso su un arco (i, j) ∈ A.

La funzione

f (x) = X

(i,j)∈A

cijxij (3.37)

´e la funzione oggetto da minimizzare.

Il flusso di minimo costo risulta quindi essere un problema di ottimizzazione formulato come: x ← arg min f (x) (3.38) X {j:(i:j)∈A} xij− X {j:(j:i)∈A} xji = b(i), ∀i ∈ N (3.39)

che rappresenta il vincolo sul bilanciamento della massa. La prima somma-toria nella parte sinistra di tale formula rappresenta la quantit´a totale del flusso uscente dal nodo i-esimo, mentre la seconda rappresenta la quantit´a totale di flusso entrante. Il vincolo sul bilanciamento della massa afferma che

sottraendo il flusso totale entrante dal flusso totale uscente si deve ottenere il valore di b(i), che rappresenta la tipologie di flusso associata al nodo in esame secondo la metodologia sopra indicata.

Un ulteriore vincolo viene fissato per i limiti di flusso. In particolare deve risultare:

ij ≤ xij ≤ uij, (i, j) ∈ A

(3.40)

avendo indicato con lij il ’lower bound’ e con uij l’ ’upper bound’, ossia la

quantit´a minima e massima di flusso dati richiesta rispettivamente. Il vettore delle variabili di decisione x che soddisfa tutti i vincoli prende il nome di ’soluzione possibile’.

3.7

Diagrammi a blocchi algoritmo LO

Nel progetto PRIMO sono presenti due diversi algoritmi di scheduling, uno BE ed uno IAS.

Entrambi trasmettono all’ allocatore una opportuna lista di richieste, ad ognuna delle quali viene associato un rate minimo, individuato da Rmin, e

un rate massimo, individuato da Rmax. L’allocatore, una volta ispezionata la

mappa delle allocazioni, determina il numero di risorse disponibili e quindi il rate totale allocabile, espresso da Rtot.

L’ algoritmo di allocazione deve quindi verificare la condizione

K X k=0 Rmin ≤ Rtot ≤ K X k=0 Rmax (3.41)

oppure, essendo unico il formato di modulazione e quindi il numero di bit per PBU, possiamo esprimere tale relazione in termini di risorse fisiche:

K X k=0 Nmin ≤ Ntot ≤ K X k=0 Nmax (3.42)

avendo indicato con K il numero delle richieste che giungono all’ alloca-tore, con Nmin e Nmax rispettivamente il numero minimo e massimo di PBU

richiesto e con Nmin il numero di PBU disponibili.

Il problema di allocazione consiste quindi in una ottimizzazione delle richi-este, in funzione dei vincoli:

• PK

k=0Rmin ≤ Rtot

• Rtot ≤ P_K

k=0Rmax

Il ’primo vincolo’, che riguarda il rate minimo, porta all’ eliminazione delle richieste nel caso in cui le richieste ’minime’ eccedano il valore massimo di capacit´a disponibile, o, in modo equivalente, le PBU richieste eccedano le PBU disponibili. Il criterio di selezione con cui vengono eliminate le richi-este ’in eccesso’ viene determinato semplicemente dall’ ordine con cui tali richieste si presentano nella lista passata all’ allocatore. Viene seguito tale criterio per rendere la scelta fair. In fase di simulazione sono stati proposti altri approcci di selezione, come ad esempio quello basato sull’ ordinamento preventivo delle richieste in base al valore della distanza fra MS che ha gen-erato la richiesta in esame e BS, in modo quindi da avere una lista ordinata per valori crescenti di potenza necessaria alla trasmissione. Pi´u una MS ´e vicina ad una BS e minore sar´a il valore dell’ interferenza percepita. Tale approccio, chiaramente unfair, risulta essere molto pi`u vantaggioso solamente con simulazioni a basso numero di frame (circa 50), mentre aumentando il numero dei frame le prestazioni calano notevolmente. La spiegazione a tale fenomeno ´e da trovarsi nel fatto che dopo aver allocato le richieste ’vicine’, e quindi pi`u vantaggiose in termini di potenza di trasmissione richiesta, riman-gono solamente le richieste ’peggiori’. Tali richieste presentano alti valori di interferenza e quindi portano a picchi non tollerabili della potenza necessaria

alla trasmissione. In questo modo solo gli utenti ’vicini’ possono essere allo-cati.

Il ’secondo vincolo’, che riguarda ilrate massimo, invece porta ad una se-lezione sul limite superiore di risorse richieste alla trasmissione. Il principio generale seguito per il controllo di tale vincolo, consiste nel fatto che non possono essere allocate pi´u risorse di quelle effettivamente disponibili. Analizzando i due algoritmi di scheduling proposti, dobbiamo evidenziare una notevole differenza fra essi.

Lo scheduler BE associa ad ogni richiesta un rate minimo ed un rate massimo pari rispettivamente alla richiesta minima e massima di risorse necessarie per la trasmissione ’completa’ della richiesta in esame, mentre lo scheduler IAS scompone le richieste in arrivo in modo tale che ogni richiesta inviata all’ allocatore risulti avere Rmin = 0 e Rmax = 1, o equivalentemente Nmin = 0 e

Nmax = 1.

Si deduce facilmente che il check sul ’primo vincolo’ risulta essere privo di utilit´a nel caso in cui l’ algoritmo di allocazione sia interfacciato con un al-goritmo di scheduler come quello di IAS.

Una ulteriore differenziazione fra i due scheduler proposti consiste nella strate-gia di allocazione proposta.

Le richieste inviate dallo scheduler BE che giungono all’ allocatore necessi-tano generalmente alcuni frame prima di poter essere completamente servite. Questo porta ad avere quindi due tipologie di richieste che giungono all’ allocatore:

• ’nuove’

Il criterio proposto segue una diversa strategia di allocazione in funzione della tipologia di richiesta, e viene riportato in fig3.4 Nel caso in cui si presenti una richiesta ’persistente’ vengono ad essa allocate le PBU che le erano state assegnate nel ’frame precedente’. Tale strategia non sempre risulta essere la migliore e le simulazioni hanno portato alla definizione di due problematiche riguardo ad essa.

• Problema di Interferenza. Il valore della potenza necessaria per la trasmissione ´e fortemente influenzata dalla interferenza percepita dall’ utente a cui si riferisce la richiesta in esame, che risulta a sua volta determinata dalla trasmissione su celle vicine. Essendo indipendente l’ algoritmo di allocazione delle risorse per ogni BS, non ´e sempre verifica-to che una trasmissione sulle PBU assegnate al frame precedente possa portare ai valori migliori di potenza totale trasmessa. In molti casi, so-prattutto in condizione di saturazione, in cui ogni utente ha richieste da allocare, assegnare le stesse PBU a richieste ’persistenti’ porta a valori di potenza eccessiva. Per risolvere tale problema la strategia proposta consiste, come mostrato in fig PA2, nell’ analizzare le richieste inviate dallo scheduler e selezionare la tipologia di esse. Invece di separare l’ algoritmo di allocazione su due flussi distinti, in questo caso andi-amo a modificare l’ ordine con cui si presentano le richieste nella lista, anteponendo le ’persistenti’ alle ’nuove’, mantenendo il loro ordine di presentazione della lista originale. Fatto ci’øle richieste seguono tutte un unico percorso di allocazione.

• Problema di allocazione di risorse non necessarie. Allocare ad una richiesta ’persistente’ le stesse PBU del frame precedente pu´o portare ad una allocazione di risorse non necessarie. per meglio chiarire questo concetto si pu´o riportare il seguente esempio: ipotizziamo di avere una

richiesta che necessita di 10 PBU per la sua completa trasmissione e di avere allocato ad essa la prima volta 4 PBU. Nel secondo frame, essendo una allocazione ’persistente’ allocherei le stesse PBU, e quindi altre 4, cos´ı come ne dovrei allocare altre 4 nel frame successivo. Il numero totale di PBU allocate risulterebbe quindi essere uguale a 12 PBU, contro le 10 effettivamente richieste.

fig3.5 Nel caso di ’nuova’ richiesta viene eseguito l’ intero algoritmo di allo-cazione, che pu´o essere riuassunto nelle seguenti fasi:

• analisi delle richieste, con individuazione del numero minimo e massimo di PBU richieste e calcolo della potenza necessaria per la trasmissione;

• calcolo delle risorse disponibili;

• controllo sui vincoli delle risorse minime e massime;

• fase di programmazione lineare.In questa fase viene mandato in ese-cuzione l’algoritmo di ottimizzazione lineare utilizzando come funzione costo i valori della potenza necessaria alla trasmissione ;

• aggiornamento della mappa di allocazione;

Una volta effettuate queste procedure abbiamo a disposizione una mappa di allocazione che memorizza le scelte fatte dall’ allocatore. A questo punto deve essere verificato un ulteriore vincolo riguardante la potenza trasmessa. In particolare si deve verificare che il valore della potenza trasmessa non superi il limite massimo consentito. Nel caso in cui tale check sui sia verificato, devono essere eliminate le richieste che presentano il valore pi´u alto di potenza richiesta, o deallocate alcune PBU loro assegnate. La strategia di selezione consiste quindi nelle seguenti fasi:

• calcolo potenza totale richiesta per la trasmissione. Nel caso in cui tale valore risulti inferiore al valore massimo della potenza ammissibile i successivi step sono inutili;

• ordinamento richieste per valori;

• inserimento in lista delle richieste trasmissibili per tutte quelle richieste che concorrono ad valore totale di potenza minore del valore massimo di potenza ammissibile;

• eliminazione delle richieste che eccedono il valore massimo di potenza ammissibile e deallocazione delle risorse precedentemente allocate;

• aggiornamento della mappa di allocazione;

Le richieste inviate dallo scheduler IAS che giungono all’ allocatore non possono essere di tipo ’persistenti’e quindi le strategie precedentemente adot-tate non risultano applicabili.

La particolarit´a dell’ algoritmo di allocazione consiste nella doppia allo-cazione richiesta dallo scheduler.

Nella prima fase, denominata ’fase di test’, lo scheduler invia all’ alloca-tore una lista di test contenente Cmax richieste, delle quali l’ algoritmo di

allocazione deve allocarne Creq In Per la selezione delle richieste idonee

al-la trasmissione vengono utilizzati non i valori delle potenze necessarie alal-la trasmissione, ma le ’potenze pesate’, rappresentate dai valori della potenza rispetto al guadagno medio di canale. In questa fase non viene modificata la mappa delle allocazioni, e l’ allocatore, una volta effettuate le scelte op-portune, invia allo scheduler una versione aggiornata della lista di test. In questa lista vengono riassunte le scelte che l’ allocatore avrebbe seguito nel caso in cui la lista fosse stata ’reale’. Eventuali richieste che vengono scartate

in questa fase vengono sostituite dallo scheduler con altre che si trovano nella sua coda interna di accumulazione.

Nella seconda fase lo scheduler invia una lista ’reale’ di Cmax elementi di cui

l’ allocatore deve allocarne Creq. Le richieste che compongono questa lista

sono quelle che risultavano essere idonee alla trasmissione nella ’fase di test’. Come funzione costo per l’ esecuzione dell’ algoritmo di ottimizzazione lin-eare viene considerata la potenza richiesta e non pi´u il suo valore ’pesato’. In fig.3.6 viene riportato il diagramma a blocchi dell’ algoritmo di allocazione interfacciato allo scheduler IAS.

Inizializzo Mappe di Allocazione Analyse Requests Lista Richieste Calculate Free Resources Controllo Bounds Elimino utenti Modifico limiti superiori in LP Calcolo funzione costo Linear Programming Aggiorno Mappa Controllo potenza trasmessa Outcome State Mantengo stesse allocazioni SCHEDULER (4,1) (3,0) SCHEDULER

Inizializzo Mappe di Allocazione Analyse Requests Lista Richieste Controllo Bounds Elimino utenti Modifico limiti superiori in LP

Calcolo funzione costo

Linear Programming Aggiorno Mappa Controllo potenza trasmessa Outcome State Ordino Lista Richieste SCHEDULER (4,1) (3,0) SCHEDULER Fig. 3.5:

Inizializzo Mappe di Allocazione

Analyse Requests Lista Richieste Test

Calculate Free

Resources Controllo Bounds

Modifico limiti superiori in LP Calcolo funzione costo ‘pesato’ Linear Programming Controllo potenza trasmessa SCHEDULER SCHEDULER Calculate Free

Resources Controllo Bounds

Calcolo funzione costo Linear Programming Controllo potenza trasmessa SCHEDULER Lista Richieste Reale Analyse Requests Modifico limiti superiori in LP Fig. 3.6: