Capitolo 3 Algoritmo di allocazione dinamica delle risorse a complessità ridotta

(1)

Algoritmo di allocazione dinamica

delle risorse a complessità ridotta

3.1 Introduzione

Dopo aver analizzato alcuni degli algoritmi noti in letteratura per l’allocazione dinamica delle risorse in un sistema OFDMA, viene proposto un nuovo algoritmo che è stato studiato e implementato.

Tale algoritmo si basa principalmente su considerazioni sul tipo di canale visto da ogni utente e sfrutta la diversità multiutente. Come già accennato, la Multiuser Diversity è dovuta principalmente a due fattori:

(2)

più utenti mobili in una cella che ha per centro la BS stessa; è intuitivo che le prestazioni del sistema saranno migliori (in termini di dispendio di potenza e di probabilità d’errore) per un utente vicino alla BS mentre degradano notevolmente per un utente ai limiti della cella. L’attenuazione dovuta al cammino di propagazione (pathloss) è infatti proporzionale alla quarta potenza della distanza ed è la principale causa dell’attenuazione del segnale durante la trasmissione.

• Channel Diversity

Per diversità di canale s’intende il fatto che ogni utente vede un diverso guadagno di canale su ogni sottoportante e, sfruttando ciò, è possibile scegliere di trasmettere solo sulle sottoportanti che hanno un guadagno di canale migliore. Il limite alle prestazioni di un sistema OFDMA è dato dagli utenti che sono ai limiti della cella e che, quindi, a causa di una pathloss maggiore, vedono un canale molto attenuato e necessitano di più potenza per trasmettere.

Sarà allora importante dare a questi utenti le sottoportanti su cui essi vedono un canale migliore, ignorando il fatto che tali sottoportanti possono essere molto buone anche per un altro utente; se questo secondo utente vede un canale mediamente buono, perdere la sottoportante assegnata al primo utente e utilizzarne una con guadagno di canale di poco inferiore non porterà una perdita di prestazioni significativa; viceversa, se il primo utente non potesse utilizzare quella sottoportante, sarebbe costretto ad usarne un’altra con guadagno di canale decisamente inferiore, deteriorando così notevolmente le prestazioni dell’intero sistema.

(3)

3.2 Struttura dell’algoritmo

L’algoritmo di allocazione dinamica delle risorse lavora su una matrice di canale H, di dimensione N x K, dove N è il numero delle sottoportanti disponibili e K è il numero degli utenti attivi. La matrice H è perfettamente nota e contiene i guadagni di canale di tutti gli utenti su tutte le sottoportanti.

( )

2 2 1 2 2 1 1 K 1 K H H H N H N ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ H … (3.1)

Sulla base di tale matrice vengono svolte due operazioni distinte: • RESOURCE ALLOCATION

Scelta di quante sottoportanti assegnare ad ogni utente: m è il numero di k sottoportanti assegnate all’utente k.

• SUBCARRIER ASSIGNMENT

Scelta di quali sottoportanti assegnare dinamicamente ad ogni utente.

Vi sono anche alcuni vincoli da rispettare:

• Ogni sottopotante può essere assegnata ad un solo utente. • Le sottoportanti totali richieste non possono essere più di N:

k k

m <N

(4)

Le possibili assegnazioni utente-sottoportante sono in numero ! ! k k N J N m = ⎛ ₋ ⎞ ⎜ ⎟ ⎝

∑

⎠ (3.3)

La particolare assegnazione j è caratterizzata da una matrice di assegnazione ( )C j di dimensione N x K definita come

1,1 1, ,1 , ( ) ( ) ( ) ( ) ( ) K N N K c j c j j c j c j ⎛ ⎞ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ C … j=1,...,J (3.4) dove ,

1 se la sottoportante è assegnata all'utente 0 in caso contrario

n k

n k

c = ⎨⎧

⎩ (3.5)

Siamo ora in grado di formulare il problema dell’allocazione risorse come un problema di tipo max-min; la matrice di allocazione ( )C j cercata è quella per cui il minimo del guadagno di canale è il più elevato possibile.

In termini matematici si definisce la matrice A( )j =C( )j H , dove il simbolo

indica il prodotto elemento per elemento dei valori delle matrici C ed H; in tal modo la matrice A è formata solo dai valori di canale delle coppie utente-sottoportante considerate (per cui cioè c_{n k}_, ( )j = ) oppure da zeri. Si definisce poi il vettore ( )1 V j , formato dai soli valori diversi da zero dalla matrice A( )j , cioè dai guadagni di canale delle coppie utente-sottoportante che si stanno considerando, e lo si ordina in modo crescente.

(5)

Ciò che stiamo cercando è la particolare assegnazione j tra le J possibili che massimizza il vettore V( )j :

{

}

arg max min ( ) j J

j j

∈

= V (3.6)

A questa formulazione del problema vanno aggiunte le condizioni • n k, 1

k

c =

∑

n=1,...,N (3.7) una sottoportante non può essere assegnata a più di un utente.

• _{n k}_, _k n

c =m

∑

k =1,...,K (3.8) il numero di sottoportanti assegnate all’utente k è m . k

3.3 Allocazione dinamica delle sottoportanti con N=K

Abbiamo visto che l’algoritmo di allocazione dinamica delle risorse viene diviso in due step:

• RESOURCE ALLOCATION: ricerca del numero delle sottoportanti da assegnare ad ogni utente (m per _k k=1,...,K);

• SUBCARRIER ASSIGNMENT: ricerca di quali sottoportanti assegnare ad ogni utente.

Per ridurre la complessità del problema e facilitarne la comprensione, consideriamo inizialmente il caso semplificato in cui il numero degli utenti è uguale al numero delle

(6)

Allocation, in quanto l’unica possibile distribuzione delle risorse è quella per cui ad ogni utente è assegnata una sola sottoportante.

La matrice di canale H e quella di assegnazione C sono quadrate e m_k =1∀k. Inoltre le condizioni (3.7) e (3.8) sono soddisfatte se ogni sottoportante è assegnata ad un solo utente e se ad ogni utente è assegnata una sola sottoportante, in relazione uno a uno. Sulla base di tali condizioni, è stato studiato un algoritmo che procede in modo iterativo e termina quando sono state formate tutte le coppie utente-sottoportante; tale algoritmo è illustrato con un esempio nel paragrafo seguente.

3.3.1 Esempio numerico con N=K=3

Per maggior comprensione del principio che sta alla base dell’algoritmo di allocazione dinamica delle sottoportanti che si sta presentando, consideriamo un caso con soli 3 utenti e 3 sottoportanti (N=K=3). Come matrice di canale prendiamo una matrice 3x3 in cui i guadagni di canale sono rappresentati da numeri da 1 a 9 (1 è il guadagno di canale più basso, 9 il più alto):

1 3 7 4 2 8 6 5 9 ⎛ ⎞ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ H (3.9)

Per rendere più chiaro il funzionamento dell’algoritmo, rappresentiamo la matrice dei guadagni di canale H come una tabella composta da 3 righe (che indicano le sottoportanti) e 3 colonne (che indicano gli utenti).

(7)

L’algoritmo procede nel seguente modo:

1. Controlla che non vi sia nessuna assegnazione obbligata (inizialmente non ve ne sono perché ad ogni utente può essere assegnata una qualsiasi delle 3 sottoportanti). Poiché non vi sono assegnazioni obbligate, viene cancellato il valore di canale più basso (in questo caso il valore 1); tale cancellazione viene indicata con una X.

Utente 1 Utente 2 Utente 3

Sottop A 1 3 7

Sottop B 4 2 8

(8)

2. Come al punto 1; viene cancellato il valore 2.

3. Come al punto 1; viene cancellato il valore 3.

Sottop A 1 3 7

Sottop B 4 2 8

Sottop C 6 5 9

Sottop A 1 3 7

Sottop B 4 2 8

(9)

4. Quando viene nuovamente effettuato il controllo, si trova che l’assegnazione della sottoportante A all’utente 3 è obbligata, in quanto non sono rimaste altre possibili assegnazioni per la sottoportante A. Per indicare l’avvenuta assegnazione si utilizza un cerchio (O).

5. Dopo tale assegnazione è necessario aggiornare la matrice, in quanto l’utente 3 non potrà avere altre assegnazioni oltre a quella già avvenuta con la sottoportante A; si cancellano allora tutti i restanti valori della colonna 3.

Sottop A 1 3 7

Sottop B 4 2 8

(10)

6. Si procede al controllo e si nota che è necessario assegnare la sottoportante B all’utente 1 e la sottoportante C all’utente 2.

7. Poiché tutte le 3 assegnazioni utente-sottoportante sono state trovate, l’algoritmo termina.

Sottop A 1 3 7

Sottop B 4 2 8

Sottop C 6 5 9

Sottop A 1 3 7

Sottop B 4 2 8

(11)

Il risultato dell’algoritmo è quindi la matrice di assegnazione ( )C j .

dove 1 indica che quella sottoportante è assegnata a quell’utente e 0 il contrario. Tornando alla notazione usuale per le matrici, abbiamo

0 0 1 ( ) 1 0 0 0 1 0 j ⎛ ⎞ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ C (3.10) 0 0 1 1 3 7 0 0 7 ( ) ( ) 1 0 0 4 2 8 4 0 0 0 1 0 6 5 9 0 5 0 j j ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ = =_⎜ _{⎟ ⎜} _{⎟ ⎜}= _⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ A C H (3.11)

Quindi la particolare assegnazione trovata porta ad utilizzare per la trasmissione OFDMA sottoportanti che hanno guadagno di canale 4, 5 e 7.

Sottop A 0 0 1

Sottop B 1 0 0

(12)

3.3.2 Una verifica importante

Fino ad ora è stato spiegato che l’approccio seguito per risolvere il problema dell’allocazione delle risorse in un sistema OFDMA è di tipo min-max; si vuole cioè trovare la matrice di allocazione che massimizza il minimo dei guadagni di canale. Si è poi fatto un esempio illustrando l’algoritmo effettivamente utilizzato per risolvere il problema dell’allocazione dinamica delle sottoportanti.

Si vuole ora verificare che il risultato trovato utilizzando l’algoritmo coincida col risultato che ci aspetteremo dalla teoria.

Ricordiamo che la teoria si basava sulla ricerca della particolare allocazione j tale che

{

}

arg max min ( ) j J

j j

∈

= V

Nell’esempio illustrato si utilizzava una matrice dei guadagni di canale

1 3 7 4 2 8 6 5 9 ⎛ ⎞ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ H

e l’allocazione trovata era

0 0 1 ( ) 1 0 0 0 1 0 j ⎛ ⎞ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ C per cui 0 0 7 ( ) ( ) 4 0 0 0 5 0 j j ⎛ ⎞ ⎜ ⎟ = _{= ⎜} _⎟ ⎜ ⎟ ⎝ ⎠ A C H e ( )j =(4, 5, 7) V

(13)

Quindi la terna dei guadagni di canale delle sottoportanti utilizzate era

Consideriamo ora tutte le possibili assegnazioni e verifichiamo che l’assegnazione che massimizza il minimo dei guadagni di canale sia esattamente quella appena trovata. Le possibili assegnazioni sono in numero pari a

! ! k k N J N m = ⎛ ₋ ⎞ ⎜ ⎟ ⎝

∑

⎠ ed essendo N =K =3 e m_k = per 1 k =1, 2, 3 si ha

(

3 3 !3!

)

3! 6 J = = = −

Abbiamo quindi 6 possibili terne di valori dei guadagni di canale; precisamente, rispettando la condizione che una sottoportante sia assegnata ad uno ed un solo utente, si hanno le seguenti terne:

1

2

9

1

5

8

3

4

9

3

6

8

7

2

6

7

4

5

4

5

7

(14)

Ordinando le terne in modo che il primo valore sia il più piccolo e permutando opportunamente i restanti, si ottiene

1

2

9

1

5

8

2

6

7

3

4

9

3

6

8

4

5

7

Come evidenziato, il risultato teorico e quello sperimentale coincidono e l’algoritmo implementato converge esattamente al massimo del minimo del guadagno di canale.

3.3.3 Generalizzazione per N=K

Dopo aver analizzato e verificato il caso con N=K=3 e con una specifica matrice di canale, generalizziamo il ragionamento mantenendo la condizione N=K e, quindi, assegnando ad ogni utente una sola sottoportante (m_k =1k =1,...,K ).

L’algoritmo può essere così descritto:

Finché non sono state assegnate tutte le N coppie utente-sottoportante, controlla se vi sono assegnazioni obbligate e agisce diversamente nei due casi:

• Se non vi sono assegnazioni obbligate, cancella l’elemento della matrice di canale che ha valore minimo;

(15)

• Se vi sono assegnazioni obbligate, considera tale assegnazione e cancella tutte le possibili altre allocazioni per quell’utente e quella sottoportante.

Nello specifico, questa operazione di cancellazione e di controllo viene fatta sfruttando una matrice ausiliaria B, di dimensione NxK e avente inizialmente tutti i valori settati a 1. Cancellare un valore della matrice di canale equivale a mettere a 0 il corrispondente valore della matrice B. L’assegnazione si verifica in due diversi casi:

• Se sulla riga n è rimasta con valore 1 solo la colonna k, mentre tutte le altre colonne hanno valore 0, allora la sottoportante indicata dalla riga n può essere allocata solo all’utente corrispondente alla colonna k. Inoltre, dopo che all’utente

k è stata assegnata la sottoportante n, tutti gli altri valori della colonna k devono

essere settati a 0, ad indicare che le altre sottoportanti non possono essere più allocate all’utente k.

• Se sulla colonna k è rimasta con valore 1 solo la riga n, mentre tutte le altre righe hanno valore 0, allora la sottoportante n viene assegnata all’utente k e tutti gli altri valori della riga n devono essere settati a 0, ad indicare che quella sottoportante non può essere assegnata a nessun altro utente.

(16)

3.3.4 Problemi al crescere della dimensione

L’algoritmo presentato è applicabile senza generare errori o casi impossibili solo a matrici di dimensioni non superiori ad una 4x4. Già con N=K=5 è possibile che si verifichino casi in cui l’algoritmo non è in grado di trovare la soluzione corretta in quanto, dopo alcune interazioni, si riconduce ad una matrice dei valori “residui” incompatibile con le condizioni che devono essere rispettate (una sottoportante per ogni utente e un utente per ogni sottoportante).

Per capire com’è possibile che si verifichi ciò, consideriamo una matrice di canale opportunamente costruita e svolgiamo alcune interazioni dell’algoritmo; per la rappresentazione grafica utilizziamo le regole illustrate nel paragrafo 3.3.1 per il caso

N=K=3.

La matrice di canale scelta è nella pagina successiva; su di essa sono già stati cancellati i valori più bassi di canale, sempre verificando le condizioni di assegnazione obbligata. Si è poi assegnata la sottoportante A all’utente 5 e, di conseguenza, si è cancellata tutta la colonna relativa all’utente 5, non potendo essere ad esso assegnata nessun’altra sottoportante.

Il passo successivo sarebbe assegnare la sottoportante B all’utente 4 e cancellare tutta la colonna relativa all’utente 4 ma è evidente che, procedendo in tal modo, si arriverebbe ad un assurdo; infatti la sottoportante C risulterebbe non assegnata ad alcun utente. E’ quindi necessario rivedere l’algoritmo di allocazione e trovare opportune condizioni che evitino di arrivare ad un caso simile a quello appena descritto.

(17)

Utente 1 Utente 2

Utente 3

Utente 4 Utente 5

Sottop A

1

4

8

10

21 Sottop B

3

7

9

11

16 Sottop C

6

5

2

20

14 Sottop

D

15 22 18 13 25

Sottop

E

23 12 17 24 19

(18)

3.3.5 Regole per l’estensione dell’algoritmo a N=K>4

Abbiamo visto che l’algoritmo originale funziona senza errori fino ad una dimensione massima di 4 utenti per 4 sottoportanti. 4 è un numero chiave in quanto ci permette di discriminare tra quanto siamo in grado di controllare e risolvere senza errori e quanto ancora non siamo in grado di gestire. Il problema diviene allora trovare un metodo che ci permetta di proseguire lo sviluppo dell’algoritmo e di estenderlo a dimensioni superiori a 4.

L’idea che sta alla base di tale estensione è quella di gestire al massimo 4 utenti alla volta, cioè di considerare “sotto-matrici” composte da solo 4 colonne; il numero di righe di tali sotto-matrici rimane pari al numero delle sottoportanti disponibili.

Come esempio consideriamo una matrice 16x16, cioè in cui N=K=16 (dimensioni superiori sono difficili da gestire graficamente ma sono perfettamente implementabili con l’algoritmo che si sta presentando). Evidenziamo le prime 4 colonne, ottenendo una sotto-matrice di 4 colonne x N righe.

(19)

Quello che viene fatto nella prima parte dell’algoritmo è procedere iterativamente cancellando i valori più piccoli della sotto-matrice di canale finché non si ha una assegnazione obbligata; è necessario effettuare un’assegnazione solo quando la colonna (utente) k rimane con la sola riga (sottoportante) n non cancellata; bisogna allora allocare la sottoportante n all’utente k.

Come conseguenza di questa assegnazione bisogna fare altre due operazioni:

• Cancellare tutta la riga n-esima, per indicare che la sottoportante n non può più essere assegnata ad alcun altro utente.

(20)

colonne, includendo così la colonna successiva; questo indica che l’utente k è già stato assegnato e può quindi essere escluso dai calcoli successivi.

Bisogna notare che la condizione da verificare per l’assegnazione obbligata è solo quella sulle colonne (si assegna quando ad un utente rimane una sola sottoportante non cancellata) mentre non viene considerata alcuna condizione sulle righe. Infatti una sottoportante può non essere assegnata a nessuno dei 4 utenti presi in esame, in quanto vi sono altri utenti, che verranno considerati in seguito, a cui tale sottoportante potrà essere assegnata.

Tornando al nostro esempio, dopo l’allocazione utente-sottoportante si dovrà considerare una nuova sotto-matrice formata da 4 colonne e (N-1) righe.

(21)

Dopo aver effettuato N-4 assegnazioni, la matrice restante è formata da 4 righe e 4 colonne; su di essa è ora possibile utilizzare l’algoritmo descritto nel capitolo 3.3.2; tale algoritmo verifica sia la condizione sulle colonne (controlla se in una colonna è rimasta una sola possibile assegnazione), sia quella sulle righe (controlla se in una riga è rimasta una sola possibile assegnazione), in modo tale che l’algoritmo converga all’assegnazione finale delle ultime 4 coppie utente-sottoportante.

3.3.6 Problematiche e loro soluzione

L’algoritmo descritto non è del tutto esente da problematiche sia sul piano concettuale, sia su quello implementativo.

A. Multiuser Diversity

Il primo e più importante concetto su cui è necessario riflettere è la diversità; abbiamo detto infatti che la multiuser diversity è ciò su cui si basano le tecniche di allocazione adattativi delle risorse. Ci chiediamo ora se l’approccio seguito, cioè quello di considerare sotto-matrici formate da solo 4 colonne, sia effettivamente in grado di sfruttare al meglio questa diversità multiutente.

La risposta è no; l’algoritmo non gestisce in modo “fair” (giusto, equo) la diversità; è evidente infatti che la diversità è totalmente sfruttata solo dai primi 4 utenti che vanno a formare la prima sotto-matrice, mentre per i successivi la diversità si riduce, fino a

(22)

diventare quasi ininfluente per gli ultimi 4 utenti considerati.

Sarà allora necessario fare in modo che gli utenti più svantaggiati, cioè quelli ai limiti della cella, siano i primi a cui vengono allocate le sottoportanti, in modo che per essi la scelta tra le sottoportanti sia la più vasta possibile (diversità elevata). Se così non fosse, se cioè agli utenti più “lontani” non fossero assegnate le poche sottoportanti su cui essi vedono un canale migliore, allora le prestazioni dell’intero sistema sarebbero notevolmente deteriorate. Gli utenti più vicini alla Base Station, invece, non necessitano di una elevata diversità, in quanto per essi tutte le sottoportanti hanno una bassa attenuazione di canale (la pathloss è bassa in quanto proporzionale alla quarta potenza della distanza).

Sulla base di queste osservazioni, cerchiamo ora un indice che dia indicazioni sulla vicinanza o lontananza di ogni utente dalla BS e, quindi, sul fatto che l’utente sia più o meno svantaggiato rispetto agli altri. Tale indice può essere il valor medio del canale visto dai vari utenti; infatti utenti vicini alla BS avranno un media di canale elevata (bassa pathloss) mentre utenti lontani e quindi svantaggiati avranno una media di canale molto più bassa (pathloss più elevata perché cresce secondo la quarta potenza della distanza).

Si può allora calcolare il valor medio del canale visto dai vari utenti e ordinare le colonne (utenti) in modo che la prima sia quella con valor medio di canale più basso. In questo modo verranno considerati per primi gli utenti più svantaggiati e, per essi, la diversità sarà massima; gli utenti che invece vedono un canale mediamente buono avranno meno necessità di diversità e potranno essere considerati per ultimi senza alterare significativamente le prestazioni del sistema.

(23)

B. Implementazione: caso di righe o colonne completamente cancellate

Il secondo problema è di tipo implementativo; svolgendo alcune simulazioni sono stati evidenziati alcuni casi in cui cancellazioni, assegnazioni e successive necessarie cancellazioni portano a situazioni impossibili; si può arrivare ad un caso in cui un utente vede tutte le sue sottoportanti cancellate (colonna di tutte X), non avendo quindi più alcuna possibilità che ad esso venga assegnata alcuna sottoportante; oppure al caso in cui una sottoportante vede tutti gli utenti cancellati (riga di tutte X) e non può quindi essere assegnata ad alcun utente.

Tali casi vengono risolti annullando tutte la cancellazioni effettuate sulla matrice e recuperando i valori dei guadagni di canale relativi ad ogni cella, per iniziare poi nuovi calcoli di minimi e nuove cancellazioni. Poiché questi casi di errate implementazioni dei codice sono rari, la velocità di calcolo e le prestazioni non ne sono praticamente influenzate.

(24)

C. Implementazione: come velocizzare l’algoritmo

Per migliorare le prestazioni dell’algoritmo è possibile svolgere alcuni controlli quando, spostando la maschera, si aggiunge una nuova colonna (utente) alla sotto-matrice in esame. Si nota che, dopo l’inserimento di tale nuova colonna, i cicli (che hanno come unico scopo quello di cancellare i minimi e controllare le condizioni di assegnazione obbligata) agiscono sui valori della nuova colonna e cancellano quelli che sono inferiori al minimo della sotto-matrice precedente (prima dell’inserimento della nuova colonna). Anziché sprecare tempo in cicli prevedibili, possiamo concentrarli in un unico set di istruzioni che, prima di aggiungere una nuova colonna, ne cancella i valori inferiori al minimo della sotto-matrice precedente, sempre verificando che queste cancellazioni non portino ad assegnazioni obbligate.

(25)

3.3.7 Descrizione finale dell’algoritmo per N=K>4

Per ricapitolare tutto quello che è stato fino ad ora introdotto nell’algoritmo che stiamo considerando, descriviamone brevemente gli aspetti principali.

INIZIALIZZAZIONE:

1. Inizializzazione delle variabili usate nel codice.

2. Calcolo del valor medio delle colonne della matrice di canale.

3. Disposizione delle colonne secondo l’ordine crescente del loro valor medio calcolato.

4. Creazione di una maschera che consideri solo le prime 4 colonne della matrice di canale e inizializzazione della sotto-matrice formata da tutte le righe e dalle prime 4 colonne.

CORPO DEL PROGRAMMA: fino alla formazione di tutte le coppie utente-sottoportante.

CASO A: vi sono altre colonne oltre a quelle considerate dalla maschera; ciò significa che il numero di utenti a cui ancora devono essere assegnate delle sottoportanti è maggiore di 4 (che è appunto la dimensione della maschera).

1. Calcolo dei valori più piccoli della sotto-matrice e loro cancellazione fino a quando non vi è un’assegnazione obbligata (se in una colonna è rimasta una sola assegnazione possibile).

(26)

3. Cancellazione della riga assegnata.

4. Cancellazione della colonna assegnata e spostamento della maschera per considerare la colonna successiva.

5. Cancellazione dei valori della nuova colonna che sono inferiori al minimo della sotto-matrice precedente.

6. Nel caso di situazioni conflittuali (righe o colonne completamente cancellate), recupero dei valori di canale cancellati e nuova serie di cancellazioni fino ad arrivare ad un’assegnazione obbligata.

CASO B: la maschera considera tutte le colonne rimaste; ciò significa che il numero di utenti a cui ancora devono essere assegnate delle sottoportanti è minore o uguale a 4 (che è appunto la dimensione della maschera).

1. Calcolo dei valori più piccoli della sotto-matrice e loro cancellazione fino a quando non vi è un’assegnazione obbligata (se in una colonna o in una riga è rimasta una sola assegnazione possibile).

2. Assegnazione.

3. Cancellazione della riga e della colonna assegnata.

CONCLUSIONE:

Dopo aver trovato tutte le coppie utente-sottoportante e aver memorizzato tali risultati in una matrice (in cui il valore 1 indica l’assegnazione e 0 la non assegnazione), è necessario permutare opportunamente le colonne di tale matrice per compensare lo spostamento delle colonne della matrice di canale effettuato nell’inizializzazione per tener conto dei valori medi di canale.

(27)

3.3.8 Esempio numerico con N=K=6

Consideriamo un caso in cui siano presenti 6 utenti e 6 sottoportanti e rappresentiamo la matrice dei guadagni di canale con la simbologia già utilizzata.

Utente 1 Utente 2 Utente 3 Utente 4 Utente 5 Utente 6

Sottop A 1 13 19 34 15 6 Sottop B 22 17 9 24 18 26 Sottop C 12 2 25 20 11 31 Sottop D 10 4 33 35 29 3 Sottop E 21 14 5 8 28 16 Sottop F 30 36 32 23 7 27

L’algoritmo procede nel seguente modo:

1. Viene calcolata la media del guadagno di canale per ogni utente (media dei valori di canale sulle 6 sottoportanti associate ad ogni utente).

Utente 1 Utente 2 Utente 3 Utente 4 Utente 5 Utente 6 16 14,3 20,5 24 18 18,2

2. Gli utenti vengono ordinati secondo valori crescenti della media calcolata.

(28)

3. Si ricostruisce la matrice ordinando le colonne in modo corrispondente agli utenti.

4. Si utilizza una maschera per considerare solo le prime 4 colonne della matrice così ordinata e si cancellano i valori di canale più piccoli finché non vi è un’assegnazione obbligata (nel caso in cui in una colonna rimanga una sola assegnazione possibile).

Utente 2 Utente 1 Utente 5 Utente 6

Sottop A 13 1 15 6 Sottop B 17 22 18 26 Sottop C 2 12 11 31 Sottop D 4 10 29 3 Sottop E 14 21 28 16 Sottop F 36 30 7 27

(29)

5. Poiché l’assegnazione della sottoportante F all’utente 2 è obbligata, tale assegnazione viene indicata con un cerchio e tutta la sottoportante F viene cancellata (tale cancellazione dovuta alle condizioni intrinseche del problema viene indicata con un +).

Sottop A 13 1 15 6 Sottop B 17 22 18 26 Sottop C 2 12 11 31 Sottop D 4 10 29 3 Sottop E 14 21 28 16 Sottop F 36 30 7 27

6. La maschera viene ora spostata includendo anche la colonna successiva, cioè l’utente 3; in questa nuova matrice non vi è la sottoportante F già assegnata. Si riportano i valori già cancellati e si cancellano i valori della nuova colonna che sono più piccoli del minimo della matrice precedente (in questo caso si cancellano 5 e 9, in quanto minori di 18, minimo della matrice precedente).

Sottop A 1 15 6 19

Sottop B 22 18 26 9

Sottop C 12 11 31 25

Sottop D 10 29 3 33

(30)

7. Si proseguono le cancellazioni dei valori più piccoli fino all’assegnazione obbligata della sottoportante B all’utente 1 e la successiva necessaria cancellazione di tutta la sottoportante B.

Sottop A 1 15 6 19

Sottop B 22 18 26 9

Sottop C 12 11 31 25

Sottop D 10 29 3 33

Sottop E 21 28 16 5

8. La maschera viene spostata includendo anche l’ultima colonna (l’utente 4) e, con le stesse regole già viste, se ne cancellano alcuni valori. Essendo ora arrivati ad una matrice 4x4, l’algoritmo si modifica e le assegnazioni obbligate si possono verificare sia sulle colonne che sulle righe. In questo caso è necessario allocare la sottoportante A all’utente 4 e eliminare di conseguenza tali righe e colonne.

Sottop A 15 6 19 34

Sottop C 11 31 25 20

Sottop D 29 3 33 35

(31)

9. La matrice successiva è una 3x3 e si assegna la sottoportante C all’utente 6.

Sottop C 11 31 25

Sottop D 29 3 33

Sottop E 28 16 5

10. Infine una matrice 2x2 e l’assegnazione della sottoportante D all’utente 3 e della sottoportante E all’utente 5.

Utente 5 Utente 3

Sottop D 29 33

Sottop E 28 5

11. Si evidenziano nella matrice le coppie utente-sottoportante trovate. Utente 2 Utente 1 Utente 5 Utente 6 Utente 3 Utente 4

(32)

12. Si permutano le colonne per tornare all’ordine originario.

3.4 Allocazione dinamica delle sottoportanti con N≠K

Estendere il ragionamento appena esposto a casi in cui il numero degli utenti è diverso dal numero delle sottoportanti è relativamente semplice, in quanto è solamente necessario modificare alcune condizioni sulle colonne della matrice di canale che abbiamo fino ad ora analizzato.

Prima di spiegare come ciò avvenga, è però necessario specificare che i casi che si possono trattare sono solamente quelli per cui N≥K, cioè i casi in cui il numero delle sottoportanti disponibili è maggiore del numero degli utenti o al più uguale ad esso (riconducendosi così al caso semplificato già analizzato); sarà quindi possibile allocare ad un utente una o più sottoportanti. Viceversa, se il numero di utenti fosse superiore a quello delle sottoportanti, si avrebbe una situazione in cui alcuni utenti non disporrebbero neanche di una sottoportante su cui trasmettere.

(33)

Dopo aver imposto che N sia maggiore o uguale a K, è necessario verificare che la somma del numero delle sottoportanti richieste dai vari utenti non superi il numero delle

N sottoportanti disponibili. Indicando con m k=1,…,K il numero di sottoportanti che _k

si vuole assegnare all’utente k, possiamo scrivere la condizione appena esposta nella forma

k k

m ≤N

∑

(3.12) Il numero m delle sottoportati assegnate ad ogni utente viene calcolato con l’algoritmo _k

di Resource Allocation illustrato nel prossimo paragrafo, che sfrutta la conoscenza della pathloss e dei guadagni di canale di ogni utente.

Per proseguire lo sviluppo di questo algoritmo che calcola quali sottoportanti assegnare ai vari utenti (Subcarrier Allocation), assumiamo che sia noto il vettore M composto dai

valori m con k=1,…,K che indicano quante sottoportanti sono richieste da ogni utente. _k

Utilizzando la notazione introdotta nel paragrafo precedente, le condizioni che devono essere rispettate sono:

• _{n k}_, 1 k

c =

∑

n=1,...,N (3.7) una sottoportante può essere assegnata ad un solo utente.

• _{n k}_, _k n

c =m

∑

k =1,...,K (3.8) il numero di sottoportanti assegnate all’utente k è m . k

Di conseguenza, poiché all’utente k devono essere assegnate esattamente m _k

(34)

assegnazioni utente-sottoportante pari a m ; inoltre, se all’utente k sono già state _k

assegnate m sottoportanti, è necessario “cancellare” tale utente, poiché esso ha già _k

soddisfatto la sua richiesta di sottoportanti.

Le condizioni sulle righe non vengono invece modificate: poiché una sottoportante può essere assegnata ad un solo utente, allora sulla riga n-esima si ha assegnazione obbligata quando rimane una sola possibile assegnazione tra la sottoportante n e un qualsiasi utente k.

Apportando quindi queste piccole variazioni all’algoritmo descritto nel paragrafo 3.3.7 è possibile estenderlo a casi in cui il numero di sottoportanti è diverso dal numero di utenti e, quindi, le matrici trattate non sono più quadrate.

3.4.1 Ulteriori condizioni che devono essere rispettate

In questa situazione in cui ad un utente possano essere assegnate più sottoportanti, si possono verificare più frequentemente casi in cui alcune righe o colonne non hanno più possibilità di essere assegnate in quanto assegnazioni precedenti hanno portato alla loro completa cancellazione. Come già detto, questi conflitti tra le condizioni da rispettare vengono risolti trascurando tutte le cancellazioni già effettuate e ricominciando il ciclo delle cancellazioni sulla matrice di canale originaria.

Vi è tuttavia un caso specifico in cui il conflitto può essere previsto ed evitato, limitando così notevolmente il numero di operazioni inutili che devono essere svolte dal codice prima che sia evidente la situazione di errata implementazione.

(35)

Consideriamo, a titolo d’esempio, un sistema formato da 5 utenti e 7 sottoportanti; al primo e al secondo utente si devono assegnare 2 sottoportati, mentre ai restanti 3 se ne deve assegnare una sola (la somma delle sottoportanti richieste da tutti gli utenti è appunto 7).

Ci si può trovare in un caso simile a quello rappresentato nella figura sotto, dove la colonna 5 non viene considerata per effetto della maschera che seleziona solo le prime 4 colonne; inoltre nella riga inferiore è indicato il numero di sottoportanti richieste da ogni utente.

Utente 1 Utente 2 Utente 3 Utente 4 Utente 5 Sottop A Sottop B Sottop C Sottop D Sottop E Sottop F Sottop G 2 2 1 1 1

Il passo successivo è assegnare all’utente 1 le sottoportanti D e F, cancellare le due righe corrispondenti alle sottoportanti D e F ed aggiungere la colonna 5.

(36)

Utente 2 Utente 3 Utente 4 Utente 5 Sottop A Sottop B Sottop C Sottop E Sottop G 2 1 1 1

Da una prima osservazione si potrebbe pensare di assegnare all’utente 2 le sottoportanti C e G ma, così facendo, all’utente 3 non potrebbe più essere assegnata alcuna sottoportante e all’utente 5 dovrebbero essere assegnate le sottoportanti A, B ed E, in quanto per tali sottoportanti l’utente 5 è l’unico non ancora cancellato.

Evidentemente dopo alcune iterazioni si arriva ad un assurdo; evitando tale dispendio di tempo e di potenzialità di calcolo, si può bloccare l’algoritmo alcuni cicli prima cha si verifichi il problema e modificare la matrice e le cancellazioni in modo da evitare conflitti. La condizione che ci permette di identificare i problemi prima che si verifichino è la seguente: prima dell’inserimento di una nuova colonna, il numero delle sottoportanti completamente cancellate è superiore al numero delle sottoportanti richieste dagli utenti che ancora devono essere considerati; nel caso in esame vi sono 3 sottoportanti completamente cancellate (A, B, E) ed una sola sottoportante richiesta dall’utente ancora da inserire (5); è infatti impossibile che il solo utente 5 possa essere

(37)

accoppiato con le 3 sottoportanti rimaste.

Quando si verifica la condizione appena esposta, si ha la certezza che procedendo con le normali iterazioni si arriverebbe ad un assurdo; è allora opportuno evitare tutto ciò, annullare tutte le cancellazioni, caricare la matrice con i valori di canale originari e procedere con una nuova serie di cancellazioni, continuando a rispettare le condizioni di assegnazione obbligata.

Un ulteriore esempio numerico può chiarire quanto appena spiegato.

3.4.2 Esempio numerico con N=7 e K=5

Con la simbologia e le regole di assegnazione già note, studiamo l’esempio proposto.

Utente 1 Utente 2 Utente 3 Utente 4 Utente 5

Sottop A 11 10 1 30 2 Sottop B 14 27 8 29 18 Sottop C 31 22 19 33 9 Sottop D 15 6 3 26 4 Sottop E 24 12 21 32 16 Sottop F 28 7 5 25 35 Sottop G 23 20 17 34 13 2 1 2 1 1

(38)

Utente 1 Utente 2 Utente 3 Utente 4 Utente 5 20,9 14,9 10,6 29,9 13,9

Utente 3 Utente 5 Utente 2 Utente 1 Utente 4 10,6 13,9 14,9 20,9 29,9

Si considerano le prime 4 colonne e si procede con le cancellazioni fino all’assegnazione obbligata delle sottoportanti C ed E all’utente 3.

Sottop A 1 2 10 11 Sottop B 8 18 27 14 Sottop C 19 9 22 31 Sottop D 3 4 6 15 Sottop E 21 16 12 24 Sottop F 5 35 7 28 Sottop G 17 13 20 23 2 1 1 2

(39)

E’ ora necessario cancellare la colonna 3 e le righe C ed E; il passo successivo sarebbe inserire la colonna 4 e considerare la nuova matrice così ottenuta; si nota tuttavia che vi sono 2 sottoportanti completamente cancellate (la A e la D) e che tale numero è maggiore dell’unica sottoportante richiesta dall’utente 4 che verrà inserito. E’ allora opportuno evitare il resto dei calcoli e resettare la matrice rimanente (cioè senza la righe e colonne già assegnate).

Si procede quindi come segue, considerando che questa è la matrice finale (non vi sono cioè altri utenti da aggiungere) e che, quindi, le assegnazioni vengono fatte verificando sia la condizione sulle colonne che quella sulle righe.

Sottop A 2 10 11 30 Sottop B 18 27 14 29 Sottop D 4 6 15 26 Sottop F 35 7 28 25 Sottop G 13 20 23 34 1 1 2 1

Assegnazione della sottoportante A all’utente 4.

Sottop B 18 27 14

Sottop D 4 6 15

Sottop F 35 7 28

(40)

Assegnazione della sottoportante D all’utente 1; nella matrice successiva viene cancellata la riga D; la colonna 1 non viene cancellata ma viene decrementato il numero delle sottoportanti che ad essa deve ancora essere assegnato (in quanto l’utente 1 necessita di un’altra sottoportante).

Sottop B 18 27 14

Sottop F 35 7 28

Sottop G 13 20 23

1 1 1

Si hanno le assegnazioni utente5–sottoportanteF, utente2–sottoportanteB, utente1-sottoportanteG e l’algoritmo termina.

Il risultato trovato è quindi:

(41)

E ordinando opportunamente le colonne:

(42)

3.5 Scelta del numero delle sottoportanti da allocare ad ogni

utente

Nell’algoritmo fino ad ora descritto il numero delle sottoportanti da allocare ad ogni utente era scelto a priori, senza alcuna valutazione sulle caratteristiche dell’utente a cui tali sottoportanti venivano assegnate. Ci occupiamo ora della Resource Allocation, cioè di decidere il numero di sottoportanti da allocare ad ogni utente, sulla base delle informazioni sul Rate richiesto da ogni utente e sul valor medio del canale visto da ogni utente (le informazioni complete sul canale sono invece sfruttate dall’algoritmo di Subcarrier Assignment già presentato).

L’algoritmo che viene ora descritto è il BABS (Bandwidth Assignment Based on SNR), presentato nel 2003 da Kivanc et al. [7]. Esso si basa sull’osservazione che alcuni utenti vedono un canale peggiore (in termini di media dei guadagni di canale) di altri; saranno tali utenti ad essere “svantaggiati” e, quindi, tenderanno a richiedere più potenza per la loro trasmissione. Per minimizzare la potenza totale necessaria per la trasmissione è allora necessario allocare un numero maggiore di sottoportanti agli utenti che vedono un canale peggiore; la potenza trasmessa è infatti una funzione monotona decrescente e, quindi, diminuisce all’aumentare del numero delle sottoportanti utilizzate per la trasmissione.

In termini matematici, il problema si riconduce a trovare il numero di sottoportanti m _k

che devono essere assegnate all’utente k (k=1, 2,...,K) in modo tale che sia soddisfatto il suo vincolo sul Rate (R ) e la potenza totale utilizzata per la trasmissione sia minima. _k

(43)

La potenza che l’utente k utilizza per la trasmissione (con rate R ) su un numero _k m di _k sottoportanti è 1 ( 1) ( ) k k n R m B k k k k e P m m H − = (3.13) dove B_n =B N/ (3.14) è la banda di ciascuna sottoportante (essendo B la banda complessiva a disposizione per la trasmissione) e 2 1 ( ) N k n k H n H N = =

∑

(3.15) è il valor medio del canale visto da ogni utente (essendo H n_k( )2 il guadagno di canale dell’utente k sulla sottoportante n).

k k

R

m è il rate trasmesso su ciascuna delle m sottoportanti assegnate all’utente k. k

Da quanto appena esposto ne consegue che la potenza totale necessaria per la trasmissione di tutti i K utenti è

1 1 ( 1) k k n R m B K T k k k e P m H = − =

∑

(3.16) L’obiettivo dell’algoritmo BABS è dunque trovare il set delle m sottoportanti _k

1, 2,...,

k= K per cui la potenza totale trasmessa è minima:

1 1 ( 1) min k k n R m B K k k k e m H = −

∑

(3.17)

(44)

Sotto le condizioni 1 K k k m N = =

∑

(3.18)

{

1,...,

}

, k m = N ∀k (3.19) Esse indicano rispettivamente che la somma del numero delle sottoportanti assegnate ai

K utenti deve essere pari al numero totale N delle sottoportanti disponibili (3.18) e che ad ogni utente k può essere assegnato un numero m_k di sottoportanti che va da un minimo di 1 ad un massimo di N (3.19).

3.5.1 Algoritmo BABS

La soluzione del problema di minimizzazione appena formulato può essere trovata con l’algoritmo iterativo che segue:

INIZIALIZZAZIONE:

1. m_k = 1 k∈ =Κ

{

1, 2,...,K

}

; ad ogni utente viene assegnata una sottoportante.

2. (1) ( 1) k n R B k k e P H −

= k∈ =Κ

{

1, 2,...,K

}

; per ogni utente viene calcolata la potenza necessaria per la trasmissione utilizzando la sola sottoportante ad esso assegnata.

(45)

3. 2 ( 1) (2) 2 k n R B k k e P H −

= k∈ =Κ

{

1, 2,...,K

}

; per ogni utente viene calcolata la potenza che sarebbe necessaria per la trasmissione su una sottoportante in più (cioè su due sottoportanti).

4. Δ =Pk Pk(1)−Pk(2) k∈ =Κ

{

1, 2,...,K

}

; per ogni utente viene calcolata la differenza tra la potenza necessaria per la trasmissione su una e su due sottoportanti.

CORPO DEL PROGRAMMA: (fino all’assegnazione di tutte le N sottoportanti) 1. arg max

{ }

k

k P

∈

= Δ

K ; si individua l’utente k per cui la differenza di potenza è

massima.

2. m_k =m_k+ ; all’utente 1 k individuato viene assegnata un’ulteriore sottoportante.

3. 1 ( 1) ( ) k k n R m B k k k k e P m m H −

= ∀k; per ogni utente viene calcolata potenza necessaria

per la trasmissione utilizzando il numero m delle sottoportanti ad esso _k

assegnate. 4. 1 1 ( 1) ( 1) ( 1) k k n R m B k k k k e P m m H + ₋

+ = + ∀k; per ogni utente viene calcolata la potenza

che sarebbe necessaria se esso trasmettesse su un numero di sottoportanti pari a quello ad esso assegnato più uno.

(46)

5. Δ =P_k P m_k( _k)−P m_k( _k+ 1) ∀k; per ogni utente viene calcolata la differenza tra le potenze sopra calcolate.

CONCLUSIONE:

L’algoritmo termina quando tutte le N sottoportanti sono state assegnate ai vari utenti.

1 K k k m N = =

∑

3.5.2 Considerazioni sull’algoritmo BABS

Riassumendo, possiamo affermare che l’algoritmo assegna iterativamente una nuova sottoportante all’utente che ne trae maggior beneficio in termini di risparmio di potenza utilizzata per la trasmissione; si cerca infatti quell’utente per cui, aggiungendo una sottoportante al suo set, si ha una maggior differenza di potenza.

Analizzando i risultati ottenuti applicando l’algoritmo BABS, si nota che gli utenti a cui viene assegnato il maggior numero di sottoportanti sono quelli per cui la media dei guadagni di canale è minore; ciò si spiega analizzando la formula della differenza di potenza utilizzata dall’utente k per la trasmissione su un numero di sottoportanti m _k

oppure 1m_k + : 1 1 1 ( 1) ( 1) ( ) ( 1) ( 1) k k k n k n R R m B m B k k k k k k k k k e e P P m P m m m H H + − − Δ = − + = − + (3.20)

(47)

La differenza tra il primo e il secondo termine è tanto maggiore quanto minore è la

media dei guadagni di canale H (ricordiamo che _k

2 1 ( ) N k n k H n H N = =

∑

).

Quindi l’utente k per cui la tale differenza è massima è anche l’utente che vede il canale peggiore in termini di valor medio dei guadagni di canale.

Consideriamo un contesto in cui è presente una Base Station e gli utenti sono sparsi all’interno di una cella che ha per centro la BS stessa; gli utenti ai limiti della cella vedono un canale molto degradato e, quindi, ad essi viene assegnato un maggior numero di sottoportanti; gli utenti più vicini alla Base Station vedono invece un canale migliore e, per questo, necessitano di un numero di sottoportanti inferiore.

3.5.3 Variazioni nella matrice dei costi

Valutiamo ora se, a causa della scelta del numero di sottoportanti da assegnare ai vari utenti, sia necessario apportare alcune modifiche all’algoritmo di allocazione dinamica delle sottoportanti già presentato.

In esso l’allocazione migliore viene scelta in base a considerazioni sulla matrice dei guadagni di canale H n_k( )2; poiché ogni utente ha a sua disposizione un ugual numero di sottoportanti e trasmette su ogni sottoportante un ugual numero di bit, allora il particolare valore H n_k( )2 non rappresenta solo il guadagno di canale che l’utente k ha sulla sottoportante n ma indica anche il costo della sottoportante n per l’utente k. Di conseguenza lavorare sulla matrice dei guadagni di canale equivale a lavorare sulla

(48)

massimizza i guadagni di canale equivale a cercare quella che minimizza il costo totale della trasmissione in termini di potenza utilizzata.

Si inserisce ora l’algoritmo BABS che calcola il numero di sottoportanti da assegnare ad ogni utente sulla base di considerazioni sul guadagno medio di canale; variando il numero di sottoportanti che ogni utente ha a sua disposizione per la trasmissione, si ha anche una variazione dell’efficienza spettrale assegnata ai vari utenti; di conseguenza varia il “costo delle sottoportanti”, cioè la quantità di potenza che verrà utilizzata trasmettendo sulle diverse sottoportanti.

Per tener conto di questa diversità nei costi delle varie sottoportanti è necessario pesare la matrice dei guadagni di canale con un termine che tenga conto dell’efficienza spettrale assegnata ai vari utenti k :

1 ( ) k n k R k B m η = (3.21)

dove Rk è il rate richiesto per la trasmissione, Bn =B N/ è la banda di ciascuna sottoportante (calcolata come rapporto tra la banda totale B e il numero di sottoportanti N) e m è il numero di sottoportanti assegnate all’utente k. k

Di conseguenza sarà necessario che l’algoritmo di allocazione dinamica delle sottoportanti riceva in ingresso una nuova matrice dei costi, con i termini opportunamente pesati: ( ) 2 2 1 ( ) k k H n η ₋ (3.22)

(49)

3.6 Allocazione ottima

Come già accennato nel secondo capitolo, la soluzione ottima al problema di allocazione dinamica delle risorse è stata studiata per la prima volta da Wong et al. [2] nel 1999 ma risulta molto complessa e di difficile implementazione, in quanto prevede l’allocazione congiunta di potenza, sottoportanti e formati di modulazione.

Poiché, come già visto, la funzione da minimizzare e i vincoli sono lineari e la variabile di allocazione è intera (può infatti assumere solo valore 1 in caso di assegnazione o 0 in caso contrario), il problema di allocazione ottima appartiene alla classe di problemi denominati linear integer programming (LIP); tuttavia, poiché la soluzione di tale

problema è molto complessa, si ricorre ad un rilassamento della variabile di allocazione, che può così assumere qualsiasi valore tra 0 e 1. Il problema così semplificato è di

linear programming (LP) e può essere risolto utilizzando algoritmi standard.

Il maggior problema di quest’approccio è che la variabile di allocazione trovata ha valore frazionario, fatto incompatibile col vincolo che una sottoportante sia assegnata ad uno ed un solo utente; è allora necessario usare un algoritmo di branch-and-bound [19]

per trovare la soluzione intera più prossima al risultato trovato.

Poiché in questa sede siamo interessati a trovare un termine di paragone per le prestazioni dell’algoritmo presentato (BABS + allocazione delle sottoportanti), ci è sufficiente implementare un algoritmo di allocazione ottima vincolato ad un numero noto di sottoportanti assegnate ad ogni utente (calcolato con l’algoritmo BABS). Avendo fissato il numero di sottoportanti che ogni utente utilizza per la trasmissione, risulta fissato anche il formato di modulazione utilizzato. In questo modo si toglie un

(50)

grado di libertà al problema dell’allocazione dinamica delle risorse che risulta così meno complesso. Inoltre, fissando a priori il formato di modulazione utilizzato da ciascun utente, si ha che la soluzione trovata con il linear programming è intera.

3.6.1 Descrizione dell’algoritmo di allocazione ottima

Come appena spiegato, ciò che si sta cercando è la soluzione ottima al solo problema dell’allocazione delle sottoportanti, in quanto il numero delle sottoportanti per ogni utente viene dato come vincolo del problema stesso. Tale soluzione si ottiene risolvendo un problema di programmazione lineare.

La formulazione standard [20] di un problema LP è la seguente:

arg min T x x= f x (3.23) sotto le condizioni x b ⋅ ≤ A (3.24) eq⋅ =x beq A (3.25) b b l ≤ ≤ (3.26) x u

Dove f , x, b, b , _eq l , _b u sono vettori e A , _b A sono matrici. _eq

Risolvendo il problema di programmazione lineare si trova il vettore x che minimizza la funzione di costo f , mantenendo verificate le condizioni imposte.

Per adattare questa formulazione del problema lineare al nostro caso di allocazione risorse è necessario impostare correttamente tutte le variabili e i vincoli; vediamo nello specifico come:

(51)

• min T

x f x x è il vettore dell’allocazione ottima che si sta cercando e il vettore dei costi f deve essere ottenuto trasformando

opportunamente la matrice dei costi

2 ( ) ( ) 2 1 k k H n η ₋ .

• A⋅ ≤x b questa condizione deve esprimere il vincolo per cui ogni sottoportante è assegnata al massimo ad un utente.

• A_eq⋅ =x b_eq questa condizione deve esprimere il vincolo per cui ad ogni utente è assegnato un numero di sottoportanti pari a quello calcolato con l’algoritmo BABS.

• l_b ≤ ≤ questa condizione deve esprimere il limite minimo (lower bound) x u_b

e massimo (upper bound) per i valori del vettore di allocazione x; nel nostro caso x deve assumere solo valore 1

(assegnazione) o 0 (non assegnazione); tuttavia, a causa del rilassamento, esso assume tutti i valori compresi tra 0 e 1; si ha quindi 0l_b = e u_b = . 1

Per chiarire come bisogna costruite le matrici A e A ed i vettori _eq b e b necessari ad _eq

implementare i vincoli dell’allocazione dinamica delle risorse, si propone un esempio numerico.

(52)

3.6.2 Esempio numerico con N=5 e K=3

Consideriamo un caso con 5 sottoportanti disponibili e 3 utenti attivi; per impostare un problema di programmazione lineare è necessario che siano noti la matrice dei guadagni di canale e il vettore indicante il numero di sottoportanti da assegnare ad ogni utente; essi sono stati calcolati con l’algoritmo BABS e sono rispettivamente:

utente 1 utente 2 utente 3

sottop. A 11 14 6 sottop. B 7 9 8 sottop. C 12 13 15 sottop. D 1 2 4 sottop. E 5 10 3 2 1 2

Il primo passo da fare è trasformare la matrice dei costi in un vettore f ; ciò si può

ottenere “leggendo” una di seguito all’altra tutte le righe della matrice dei costi.

Il risultato dell’algoritmo di programmazione lineare è il vettore x che indica

l’assegnazione ottima; sarà poi necessario disporre in modo opportuno righe e colonne in modo da avere la matrice di assegnazione ottima che si sta cercando.

Nel nostro esempio è

f =

x =

11 14 6 7 9 8 12 13 15 1 2 4 5 10 3

(53)

Il vettore x conterrà solo valori 1 o 0 ad indicare l’avvenuta o la mancata assegnazione.

Bisogna ora costruire opportunamente la matrice A e il vettore b in modo che la

condizione A⋅ ≤x b esprima il vincolo per cui una sottoportante può essere assegnata ad un solo utente.

Si scelgono la matrice A e il vettore b nel modo sotto indicato:

⋅ ≤

Scegliendo la matrice A diagonale a blocchi, è possibile contare il numero di 1 che sono presenti in ognuno dei 5 blocchi da 3 caselle del vettore x. Scegliendo il vettore b di soli

valori 1, si impone la condizione per cui ogni sottoportante è assegnata ad un solo utente; infatti, affinché la disequazione sia verificata, in ogni blocco da 3 caselle di x

deve essere presente un solo 1, ad indicare che quella sottoportante è assegnata ad uno solo dei 3 utenti.

Allo stesso modo, è necessario scegliere opportunamente i valori della matrice A e _eq del vettore b in modo che la condizione _eq A_eq⋅ =x b_eq indichi il vincolo per cui ad ogni

1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

(54)

utente deve essere assegnato il numero di sottoportanti precedentemente calcolato con l’algoritmo BABS.

Si scelgono la matrice A e il vettore _eq b nel modo sotto indicato: _eq

⋅ =

Scegliendo la matrice A formata da più matrici diagonali è possibile contare gli _eq elementi presenti nella prima cella di ciascun blocco da 3 caselle del vettore x. Si riesce

così a contare il numero delle sottoportanti assegnate a ciascun utente e ad imporlo uguale al valore individuato con l’algoritmo BABS (b ). _eq

Dopo aver così impostato i parametri del problema di programmazione lineare, si trova che la sua soluzione ottima è data dai valori evidenziati nella matrice riportata nella pagina seguente: 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 2 1 2

(55)

utente 1 utente 2 utente 3 sottop. A 11 14 6 sottop. B 7 9 8 sottop. C 12 13 15 sottop. D 1 2 4 sottop. E 5 10 3

Se invece avessimo applicato l’algoritmo di allocazione dinamica delle risorse precedentemente esposto, avremmo trovato un risultato diverso:

utente 1 utente 2 utente 3

sottop. A 11 14 6

sottop. B 7 9 8

sottop. C 12 13 15

sottop. D 1 2 4

sottop. E 5 10 3

Da un rapido confronto si nota che l’assegnazione trovata col metodo di programmazione lineare è migliore, in quanto utilizza per la trasmissione sottoportanti che hanno un maggior guadagno di canale.