Capitolo III Packet scheduling e allocazione di risorse

Packet scheduling

e allocazione di risorse

In questo capitolo viene presentata una particolare architettura di sistema che utilizza congiuntamente uno scheduler di pacchetti ed un allocatore di risorse radio per un una rete wireless OFDMA, il cui obiettivo è minimizzare la potenza trasmessa verso gli utenti, garantendo allo stesso tempo un bit rate costante. Tale proposta verrà attuata nei due capitoli successivi, rispettivamente al caso di un sistema a singola cella e ad uno multicellulare. Cercheremo di concentrare la nostra attenzione principalmente su due aspetti, quali la misura dell’efficienza spettrale di ogni utente e la valutazione delle prestazioni del sistema in termini di fairness.

III.1 – Introduzione

In un qualsiasi sistema wireless esistono due fattori puramente aleatori che concorrono al problema della gestione delle risorse: il traffico (inteso come il flusso di dati che viaggia all’interno della rete) e il canale radiomobile.

La gestione del traffico in una rete dipende dal tipo di scenario in cui si trova il sistema: un tipico esempio riguarda il raggiungimento della fairness tra i vari utenti in una rete a pacchetto [1],[2]. Lo scheduler di pacchetti è l’elemento che cerca di garantire questo tipo di obiettivo, facendo in modo che ogni flusso di dati possa essere servito nella misura in cui ciascuno di essi occupa una determinata porzione di banda.

Il canale radiomobile è, in genere, tempo variante e fortemente selettivo in frequenza. In un sistema OFDMA, il problema della selettività in frequenza è superato attraverso la suddivisione della banda in piccole porzioni che permettono di considerare il canale come “piatto” e quindi non distorcente; l’unico effetto introdotto dal canale su ogni sotto-banda consiste in un’attenuazione in ampiezza ed una rotazione in fase costanti su ogni porzione di banda, che possono essere compensati al ricevitore mediante un’operazione di equalizzazione in frequenza.

Tuttavia, è necessario introdurre un opportuno meccanismo di gestione e allocazione delle risorse in modo da raggiungere un’elevata efficienza spettrale, favorendo gli utenti che sperimentano un canale migliore (in termini di guadagno) in un dato intervallo di tempo.

I due aspetti fin qui analizzati risultano però conflittuali tra di loro, in quanto l’algoritmo di gestione delle risorse radio tende a penalizzare gli utenti che

sperimentano un canale non buono, vale a dire fortemente attenuato su ogni sottoportante, indipendentemente dalla loro intensità di traffico. La ricerca di un compromesso tra lo sfruttamento delle caratteristiche del canale, nella maniera più efficiente possibile, e la condivisione di risorse tra gli utenti, porta alla risoluzione di un problema di ottimizzazione vincolato [3],[4]. Tuttavia, un approccio del genere dipende, come detto, dal tipo di contesto in cui si trova il sistema, dalla specifica strategia di gestione del traffico scelta e dal tipo di obiettivo che si vuol perseguire. Una soluzione alternativa consiste nel separare lo scheduling di pacchetti e l’allocazione di risorse radio [5], in due moduli interconnessi tra loro: ciò che verrà proposto nel seguito sarà, appunto, un algoritmo di gestione delle risorse radio che coinvolgerà due livelli dello stack, quello fisico (PHY) e quello MAC (Medium Access Control). Tale algoritmo, che ha come obiettivo sia la massimizzazione dell’efficienza del sistema in termini di potenza, sia la fairness tra gli utenti, viene formulato attraverso la definizione di un problema di ottimizzazione vincolato, in cui lo scheduling di pacchetti, l’allocazione delle sottoportanti e il controllo di potenza costituiscono i blocchi della struttura integrata.

III.1.1 – Architettura “Cross-Layer”

La maggior parte degli algoritmi di allocazione di risorse, presenti in letteratura, tende a focalizzarsi su di un unico livello dello stack protocollare: questa mancanza di flessibilità risulta inefficiente nell’ambito dell’allocazione delle risorse tra più utenti. Si consideri, a titolo di esempio, l’algoritmo di allocazione adattativa congiunta (sottoportanti, bit, potenza) proposto in [6]-[8] per un sistema multiutente OFDM: tale

algoritmo, principalmente confinato al livello PHY della rete, è stato realizzato utilizzando un modello deterministico del traffico che non tiene assolutamente conto del comportamento dinamico all’interno delle code osservato a livello MAC. Il risultato è che l’allocazione di risorse risulta inadatta in una rete a pacchetto poiché il traffico, tipicamente, arriva in accordo a qualche processo stocastico. D’altronde, gli algoritmi di allocazione di risorse a livello MAC, non prendono in considerazione le caratteristiche dei canali di propagazione in ambiente wireless, come il multipath, la tempo-varianza [9]-[11]. Questi algoritmi, dunque, non sono in grado di garantire un’elevata qualità del servizio (Quality of Service, QoS) e la fairness nelle reti wireless.

Sulla base di queste considerazioni, quello che proponiamo di seguito è un meccanismo di allocazione di risorse che coinvolga in maniera “trasversale” il livello PHY e quello MAC: definiamo questa architettura cross-layer. In questo modo, lo scheduling dei pacchetti e l’assegnazione delle risorse (sottoportanti) non avviene indipendentemente l’uno dall’altra, bensì all’interno di una struttura integrata, che permette di trarre vantaggio dall’interdipendenza tra il livello PHY e quello MAC. A differenza da altri algoritmi che lavorano soltanto al livello fisico, come quelli proposti in [6]-[8], la tecnica qui analizzata sfrutta la “diversità” del sistema, dovuta alla natura tempo variante del canale di propagazione unitamente alla aleatorietà del traffico.

III.1.2 - Diversità

Nell’ambito delle telecomunicazioni, con il termine diversità si fa riferimento all’impiego di una molteplicità di canali di comunicazione aventi ciascuno diverse caratteristiche, con l’obiettivo di ridurre gli effetti distorcenti del canale di propagazione

sul segnale trasmesso. Le situazioni di maggior interesse nell’uso delle tecniche in diversità sono quelle in cui il canale di propagazione è affetto da fading, come nel nostro caso, ma anche quelle caratterizzate dalla presenza di interferenza co-canale (sistemi cellulari).

Il principio che sta alla base delle tecniche in diversità è quello secondo cui ciascuno dei canali su cui viene trasmesso e/o ricevuto il segnale originario sperimenta livelli

differenti di fading e di interferenza di questi canali e questo provoca un guadagno in diversità nel momento in cui ognuna delle repliche del segnale viene combinata al

ricevitore. Tale guadagno nasce in virtù del fatto che ciascuno dei canali su cui i segnali vengono trasmessi è caratterizzato da un rapporto segnale/rumore diverso, in particolare ci saranno canali con valori di rapporto segnale/rumore bassi e altri con valori più alti. Di conseguenza, al ricevitore, arriveranno repliche attenuate in modo diverso e così, supponendo che le attenuazioni siano indipendenti tra di loro, si può immaginare che almeno alcune di esse siano poco attenuate e, quindi, poter decidere con bassa probabilità di errore.

Esistono diversi modi di realizzare la diversità:

• Diversità di tempo: consiste nel trasmettere repliche dello stesso segnale più volte nel tempo, ad una distanza sufficientemente grande in modo che il fading sia indipendente da una trasmissione all’altra.

• Diversità di frequenza: in questo caso il segnale viene trasmesso su portanti a frequenza diversa, sufficientemente separate tra di loro. In uno scenario OFDMA, ogni utente riceve un gruppo di sottoportanti appartenenti alla banda allocata al sistema con l’obiettivo di assegnare a ciascuno di essi

quelle che hanno valore di rapporto segnale/rumore più alto; supponendo, infatti, che ogni utente sperimenti guadagni diversi su ogni sottoportante (tale ipotesi è lecita in quanto si immagina che i guadagni siano tra loro indipendenti), l’insieme di sottoportanti allocate sarà diverso da utente a utente.

• Diversità di spazio: si tratta di trasmettere il segnale su cammini di propagazione (path) distinti, mediante l’utilizzo di antenne multiple in trasmissione (diversità in trasmissione) e/o in ricezione (diversità in

ricezione). Nel primo caso, si effettua una combinazione dei vari segnali

prima che vengano inviati al ricevitore; nel secondo, invece, i segnali vengono combinati tra di loro al ricevitore.

• Diversità multi-utente: è il principio alla base dei sistemi OFDMA. Ciascun utente, infatti, ha in generale guadagni diversi sulle varie sottoportanti in cui è suddivisa la banda assegnata al sistema; se il trasmettitore è a conoscenza degli andamenti di canale per ogni utente (channel state information, CSI), sarà in grado di assegnare le sottoportanti in accordo alle caratteristiche di guadagno di ciascun utente.

I concetti di diversità saranno alla base del sistema che verrà discusso nel prosieguo di questo capitolo e dei prossimi due, in particolare i concetti di diversità frequenziale e multi-utente giocheranno un ruolo fondamentale nello sviluppo del problema. L’allocatore di risorse radio, che analizzeremo nel seguito, dovrà effettuare le proprie decisioni basandosi sulle diverse caratteristiche di canale per ogni utente, assegnando a ognuno di loro un sottoinsieme diverso di sottoportanti, sfruttando proprio la diversità

frequenziale e multi-utente; d’altra parte, lo scheduler dovrà cercare di servire anche quegli utenti che, a causa di condizioni meno favorevoli di cabale di propagazione, sono penalizzati dalle scelte dell’allocatore.

III.2 – Modello del sistema

Quello che presentiamo qui di seguito è il modello che sta alla base del sistema che verrà trattato nei prossimi capitoli, rispettivamente nel caso di un sistema singola cella (capitolo IV) e di uno multicellulare (capitolo V). La banda disponibile assegnata al sistema viene suddivisa in N sottoportanti ortogonali, ciascuna delle quali può essere assegnata ad uno soltanto degli utenti appartenenti ad una determinata cella. L’asse temporale è anch’esso suddiviso in sottointervalli di durata Ts, detti slot, che vengono

poi raggruppati in trame (o frame), ciascuna delle quali ne contiene S. Lo scheduler crea una lista di C_max pacchetti che possono essere trasmessi, sulla base di un determinato

algoritmo di scheduling analizzato nel seguito. A questo punto l’allocatore di risorse sceglie un sottoinsieme di pacchetti della lista, la cui dimensione è individuata dal parametro Creq, dove Creq ≤Cmax, con il vincolo di minimizzare la potenza trasmessa.

Tali pacchetti sono quelli che vengono effettivamente inviati dal trasmettitore, la cui struttura è già stata analizzata nel capitolo precedente. Infine, lo scheduler riceve la lista di pacchetti effettivamente selezionati per la trasmissione e può così aggiornare il proprio stato avendo a disposizione le informazioni relative a ciascun flusso nella coda. La procedura completa è illustrata nello pseudocodice seguente (Algoritmo 1).

Algoritmo 1 Scheduling e Allocazione

1: SchedList←schedule(Cmax)

2: AllocationList←allocate(SchedList, Creq)

3: updateCredits(AllocationList)

Il punto chiave del problema è che l’ottimizzazione è condizionata alla particolare lista di pacchetti determinata dallo scheduler. L’allocatore tende a privilegiare i flussi che presentano i maggiori guadagni di canale, tenendo sempre conto, però, della politica di scheduling adottata.

Il risultato è un compromesso tra i due obiettivi perseguiti, ovvero la fairness (che è compito dello scheduler) e l’efficienza (di interesse dell’allocatore di risorse): maggiore è il grado di libertà lasciato all’allocatore e più è alta l’efficienza in termini di capacità, che però si paga con una maggiore lentezza di convergenza verso i prestabiliti obiettivi di fairness da parte della scheduler.

III.3 – Packet Scheduling

Si consideri una rete costituita da terminali liberi di muoversi e una stazione base (base station, BS), collegati tra loro tramite una connessione di tipo wireless. È stato osservato che l’obiettivo di massimizzare la fairness non è realistico se pensato sul breve periodo, a causa della natura tempo variante del canale su cui avviene il collegamento [12]: una possibile soluzione consiste nell’accettare una certa unfairness tra i vari flussi di dati sul breve periodo, tenendo traccia dell’ammontare di traffico che ciascun utente deve ancora trasmettere, compensando questo gap nel più breve tempo possibile [13]. La fairness viene raggiunta su una scala temporale più grande e tutto ciò

può essere realizzato in diverse modalità: in particolare, gli algoritmi basati sui crediti [14],[2] sono semplici ed efficienti dal punto di vista computazionale.

Ciascun utente partecipa al processo di scheduling con l’obiettivo di ottenere il massimo delle risorse (sottoportanti) possibili, sulla base di quelle che sono le proprie capacità in termini di diversità frequenziale. Lo scheduler, infatti, assegna un rate

massimo per utente, per effetto dei crediti che ciascun utente possiede e che ha

accumulato a seguito dell’allocazione di risorse: il valore dei crediti aumenta all’aumentare del tempo in cui un utente non viene “schedulato”, mentre viene decrementato quando gli viene assegnata una sottoportante. I valori di rate massimo sono, infatti, un bound superiore che l’allocatore deve rispettare, assegnando a ciascun utente le sottoportanti su cui riceve i dati ad una velocità trasmissiva minore o uguale a quella indicata nella procedura di scheduling. Se un utente si trova in una situazione di canale non buona (forte attenuazione su tutte le sottoportanti), l’allocatore tende ad assegnargli un numero di risorse inferiore rispetto a un utente che, invece, ha una risposta in frequenza del canale migliore: lo scheduler cerca, appunto, di compensare questo gap, mediante la propria strategia di gestione del traffico, dando un numero di risorse (in termini di rate massimi) maggiore agli utenti più svantaggiati rispetto a quelli con canale migliore. In questo modo, si riesce a raggiungere la fairness tra gli utenti, sebbene su una scala temporale più lunga di quella su cui avviene l’allocazione.

III.3.1 – Descrizione dell’algoritmo di scheduling

L’algoritmo di scheduling (Algoritmo 2) che descriviamo di seguito si basa sull’uso di crediti: lo stato di ciascun flusso è riassunto da un unico valore, che è

appunto il credit counter Ki. Il generico flusso guadagna crediti se non viene

“schedulato”, e usa tali crediti nel momento in cui è servito dallo scheduler.

Per ogni flusso si definisce un valore fissato, che rappresenta il peso che tale flusso possiede e che viene indicato con

φ

_i e, come già detto, un contatore K_i, che

incrementa quando il flusso non trasmette. Nella fase di scheduling, si assegna a ciascun flusso un contatore temporaneo *

i

K , che viene utilizzato al posto di quello originale; al

termine della procedura di scheduling avviene quella di allocazione delle risorse, che provvede all’assegnazione delle risorse radio, e successivamente si va ad aggiornare il valore dei contatori Ki con quelli dei contatori temporanei.

Il blocco di istruzioni 5-21 viene eseguito una volta per time slot, e il suo scopo è quello di creare una vera e propria lista di al più Cmax pacchetti da poter inviare

all’alllocatore, il quale provvederà ad assegnare le risorse radio nella maniera più fair possibile.

Lo scheduler associa a ciascun flusso una priorità, individuata dal proprio coefficiente peso e dal valore attuale del contatore: la priorità più elevata viene selezionata per la trasmissione il suo contatore temporaneo viene decrementato, mentre quelli degli altri utenti sono incrementati.

Dopo che l’allocatore ha selezionato dalla lista i Creq pacchetti, lo scheduler è in

grado di aggiornare i crediti di ciascun flusso, attraverso l’esecuzione delle istruzioni 8-19 di Algoritmo 2, sostituendo *

i

Algoritmo 2 schedule(C_max) 1: for i = 1 to K do 2: K_i*←K_i 3: c( ←i) 0 4: end for 5: while

∑

_iK₁c(i)<C_max = 6: i i i K f φ * 1 min arg − ← 7: c(f)←c(f)+1 8: for i = 1 to K do 9: if i≠f then 10: K_i*←K_i + _i f f K φ φ ⋅ − ) 0 , 1 max( * 11: end if 12: end for 13: * _max(0, * ₁₎ − ← f f K K 13: SchedList.insert(pf) 14: end while 15: return SchedList

III.4 – Allocazione di risorse

Il principale obiettivo degli algoritmi di allocazione di risorse è lo sfruttamento della selettività in frequenza del canale di propagazione unitamente alla diversità multi-utente: molti degli algoritmi presenti in letteratura seguono un approccio denominato

margin adaptive (MA), il cui scopo è quello di minimizzare la potenza consumata, sotto

il vincolo di un bit rate costante per ciascun utente [15]-[17], oppure un approccio rate

mantenere la potenza costante [18]-[19]. In quest’ultimo caso, la soluzione ottima per un collegamento downlink è da ritrovarsi nell’applicazione dell’algoritmo water-filling [20]. In particolare, in [19] e in [21] si mostra come l’OFDMA sia la migliore tecnica di accesso multiplo in un collegamento downlink multi-utente multi-portante: la capacità viene massimizzata assegnando le sottoportanti agli utenti con il guadagno più grande, distribuendo poi la potenza su tali sottoportanti mediante la tecnica dello water-filling, in accordo all’allocazione effettuata.

Tutte queste proposte sono state fatte per sistemi a singola cella, mentre il nostro obiettivo è quello di realizzare un algoritmo di allocazione di risorse che sia valido anche nel caso multi-cellulare: lo scenario verrà affrontato nel capitolo V e sarà quello di un sistema con riuso universale di frequenza, in cui l’allocazione di risorse e lo scheduling dei pacchetti vengono realizzati in maniera distribuita, dove però entrerà in gioco un meccanismo di riduzione del carico delle celle centralizzato. La presenza di una forte interferenza tra le celle, infatti, provocherà una forte instabilità del sistema, per cui sarà necessario diminuire il numero di risorse complessivo di quelle celle che danneggiano maggiormente la rete.

III.4.1 – Efficienza spettrale

Si supponga che sia assegnato un certo rapporto segnale interferenza

(signal-to-intereference ratio, SIR) e quindi la capacità di canale in bit/s/Hz è data da: ) 1 ( log₂ +SIR =

η

(III.4.1)

la quantità in (III.4.1) prende il nome di efficienza spettrale e rappresenta la velocità di informazione per unità di banda, infatti può anche essere espressa come

B R/

=

η (III.4.2)

Di conseguenza, il massimo rate raggiungibile su di un canale di banda B è

η B

R= (III.4.3)

Considerando un collegamento in downlink, per un sistema OFDMA, il SIR ricevuto sulla sottoportante n per l’utente k (che si trova nella cella i) è pari a:

) ( ) ( ) ( ) , ( , 0 2 , n I BN n G n P n k SIR i k k i k + = (III.4.4)

dove P_k(n) rappresenta la potenza trasmessa dalla BS i sulla sottoportante n, G_i,k(n)

indica il guadagno tra l’utente k e la BS i sulla sottoportante n, mentre N₀ individua la

densità spettrale di potenza monolatera del rumore termico a media nulla e B è la banda di ogni sottoportante. La quantità Ik_,i(n) indica invece l’interferenza sperimentata dall’utente k nella cella i su quella sottoportante e vale

∑

≠ =

=

cells i j N j k j j BS i k

n

P

n

G

n

I

1 2 , ) ( ,

(

)

(

)

(

)

(III.4.5)

Nella (III.4.5) P_BS(j)(n) rappresenta la potenza con cui la BS j trasmette sulla sottoportante n-esima, mentre Gj_,k(n) è il guadagno tra l’utente k (appartenente alla cella i) e la BS j sulla sottoportante n.

Supponendo sia assegnata, per un determinato utente, l’efficienza spettrale η, il SIR

necessario a raggiungere la quantità suddetta è data da

1

2 −

=

η

SIR

(III.4.6)

la potenza Pk(n), quindi, si ricava dalla seguente relazione

2 , , 0 ) ( ) ( ) ( n G n I BN SIR n P k i i k k + = (III.4.7)

si noti che la quantità Ik_,i(n) rappresenta l’interferenza misurata nello slot temporale precedente.

III.4.2 – Allocatore di risorse radio: algoritmo linear programming (LP)

L’allocatore di risorse radio (Radio Resource Allocator, RRA) ha il compito di minimizzare la potenza trasmessa, sotto un determinato vincolo in termini di bit rate

b

R . Lo scheduler passa una lista di Cmax pacchetti all’allocatore, il quale sceglie tra

questi un numero di pacchetti pari ad una certa capacità prefissata, denominata Creq

Consideriamo l’utente k, lo scheduler assegna a quest’ultimo un rate massimo )

(k

R , cui corrisponde un numero massimo di pacchetti r(k) che possono essere

ricevuti. La relazione che lega le due quantità è

η

B

k

r

k

R

(

)

=

(

)

(III.4.8)

Sia inoltre b_k(n) la variabile binaria che vale 1 quando al k -esimo flusso è consentito trasmettere sulla sottoportante n-esima, e 0 altrimenti, mentre P_k (n) è data dalla

(III.4.7). Si assume poi il fattore di carico C_req costante.

Il problema di allocazione di risorse può essere così formulato

∑∑

= = = N n K k k k b n b n P b 1 1 ) ( ) (

min

arg

(III.4.9)

con i seguenti vincoli da rispettare

∑

= ≤ K k k n b 1 1 ) ( n=1,...,N (III.4.10)

∑

= ≤ N n k n r k b 1 ) ( ) ( k =1,...K (III.4.11)

∑ ∑

= = = K k N n req k n C b 1 1 ) ( b_k( ∈n)

{ }

0,1 n=1,...,N k =1,...K (III.4.12)

Nella (III.4.9) si esprime il problema di minimizzazione della potenza, che può essere risolto mediante algoritmi di programmazione lineare (linear programming, LP): si cerca, infatti, il vettore b che rappresenta l’allocazione ottima per il sistema in esame. Il

problema deve rispettare anche alcuni vincoli, che sono espressi nelle (III.4.10)- (III.4.12): in particolare, nella (III.4.10) si impone che ciascuna sottoportante venga assegnata ad uno soltanto degli utenti presenti nel sistema, mentre nella (III.4.11) si fa in modo che ciascun utente trasmetta numero di pacchetti minore o uguale a quello indicato dallo scheduler, sulle sottoportanti allocate.

Nella (III.4.12), infine, si impone che la somma totale dei pacchetti trasmessi da ciascun utente deve essere pari al fattore di carico del sistema C_req: ogni utente, infatti, riceve

dallo scheduler il rate massimo R(k) cui corrisponde il numero massimo di pacchetti )

(k

r , ma è l’allocatore a decidere su quali sottoportanti e con quale velocità ogni utente

lavora. A tale velocità trasmissiva corrisponde un determinato numero di pacchetti che viene distribuito sulle varie sottoportanti per effetto dell’allocazione. La somma di tutti questi pacchetti dà, appunto, il fattore di carico C_req.