Università degli studi di Pisa
Corso di laurea specialistica in Ingegneria delle telecomunicazioni
ALGORITMI DI ALLOCAZIONE DI
RISORSE IN SISTEMI OFDMA
1°Relatore: Moretti Marco
2°Relatore: Prof. Morelli Michele
Candidato: Emanuel Siragusa
CAPITOLO 1 – Introduzione
1.1 Principi generali dell’OFDM 5
1.2 Struttura di un sistema OFDM 7
1.3 La modulazione OFDMA 12
1.4 Channel State Information 13
1.5 Feedback Information 14 1.6 Applicazioni 14 1.6.1 ADSL 15 1.6.2 WiLan 16 1.6.3 WiMax 19 1.6.4 Osservazioni 20
CAPITOLO 2 - Architettura di sistema 2.1 Il sistema multicellulare 22
2.2 Il problema d’allocazione 24
2.3 Algoritmo ottimo 30
2.4 Algoritmo LP 33
2.5 Problema del controllo del carico in sistemi centralizzati 36
CAPITOLO 3 - Algoritmi sub-ottimi 3.1 Problema del controllo del carico in sistemi distribuiti 37
3
3.2 Algoritmo iterativo parzialmente distribuito 38
3.2.1 Modello 39
3.2.2 Funzionamento generale 40
3.2.3 Controllo di convergenza 43
3.2.4 Procedura di riduzione del rate 45
3.3 Algoritmo Multi – Assign 48
3.3.1 Modello 49
3.3.2 Funzionamento generale 51
3.3.3 Calcolo delle potenze effettive 53
3.3.4 Analisi della consistenza della soluzione 57
3.3.5 Allocazione soft 59
3.3.6 Allocazione hard 63
3.3.7 Qualità della soluzione 64
3.4 Algoritmo NF 65
3.4.1 Modello 66
3.4.2 Funzionamento generale 67
3.4.3 Suddivisione degli utenti per categoria 70
3.4.4 Controllo di convergenza e riduzione del rate 71
3.4.5 Difetti dell’algoritmo 71
CAPITOLO 4 – Risultati
4.1 Confronto tra ID ed MA 75
CAPITOLO 5 – Conclusioni 84 Bibliografia 86
5
Capitolo 1 Introduzione
1.1 Principi generali dell’OFDM
L’acronimo OFDM (Orthogonal Frequency Division Multiplexing ) indica una modulazione a divisione di frequenza in cui le sottoportanti utilizzate per trasmettere il segnale sono tra loro ortogonali.
Le trasmissioni ad alta velocità sono limitate nelle prestazioni non tanto dal rumore ma dall’ISI1, fenomeno dovuto principalmente alla diversa attenuazione di canale sui diversi percorsi che il segnale può seguire (multipath fading); poiché i diversi percorsi di propagazione tra trasmettitore e ricevitore hanno diversa lunghezza e diversa attenuazione di canale, al ricevitore arriverà una sequenza di segnali con ritardo di propagazione ed attenuazione tra loro differenti.
Questo effetto si ha non solo nella comunicazione wireless ma anche su tutti i tipi di guida d’onda; nei sistemi di comunicazione wireless, tuttavia, esso è molto più accentuato, a causa del fatto che i ritardi sono relativamente lunghi (fino a qualche decina di μs).
Generalmente l’effetto dell’ISI si considera trascurabile se il ritardo di propagazione è significativamente più piccolo della durata di un simbolo trasmesso.
Questo significa che la velocità di simbolo dei sistemi di comunicazione è limitata dalla memoria di canale.
Se la velocità di simbolo supera tale limite, le performance del sistema in termini di probabilità d’errore vengono notevolmente deteriorate e quindi, diventa necessario utilizzare tecniche di equalizzazione di canale che riducano l’effetto dell’ISI.
Anziché usare questo metodo, è possibile sruttare una modulazione diversa, intrinsecamente resistente al multipath fading.
Si tratta appunto della tecnica OFDM, che si basa sul principio di suddividere il flusso dati proveniente dalla sorgente in N sottoflussi, ciascuno dei quali modula una diversa sottoportante; i simboli di informazione vengono così trasmessi in parallelo2 su sottoportanti tra
loro ortogonali.
Poiché il flusso dati è la somma del flusso delle varie sottoportanti in parallelo, la velocità su ogni sottoportante è solo una frazione della velocità che si avrebbe con una trasmissione convenzionale a singola sottoportante.
Oltre all’alta resistenza al multipath fading anche nei casi in cui il ritardo di propagazione del canale sia significativamente maggiore del tempo di simbolo, l’OFDM è diventata una tecnica di trasmissione molto utilizzata anche per l’elevata efficienza spettrale che è possibile raggiungere, mediante allocazione adattativi delle risorse.
L’implementazione tramite FFT3 riduce la complessità della DFT4 necessaria per le tecniche OFDM.
2 Simultaneamente.
3 FFT: Fast Fourier Transformed.
Capitolo 1 – Introduzione
7
1.2 Struttura di un sistema OFDM
Come sappiamo, la questione della selettività in frequenza risiede nella (larga) banda del segnale che risulta confrontabile con l’inverso dei ritardi relativi tra i vari cammini multipli (o con la banda di coerenza del canale5).
Figura 1.1 - Esempio di selettività in frequenza
Nella modulazione OFDM si cerca di risolvere la situazione illustrata in fig. 1.1 suddividendo la trasmissione di un unico flusso dati ad alta
5 Si definisce banda di coerenza del canale il massimo intervallo in cui la funzione di trasferimento
velocità di segnalazione 1/T e quindi larga banda, in una molteplicità di sotto-flussi paralleli ottenuti suddividendo il flusso originario.
Figura 1.2 - Risoluzione selettività tramite OFDM
Quello che abbiamo nella situazione descritta in figura 1.2 è l’assenza di ISI ma la presenza della sola attenuazione di canale (il canale agisce su ciascuna sottobanda come un fattore moltiplicativo complesso, senza generare interferenza tra i simboli trasmessi).
Un obiettivo fondamentale è il raggiungimento dell’ortogonalità tra le portanti, la condizione fondamentale per ottenerla è che la durata
Capitolo 1 – Introduzione
9
Ts=N/R dei simboli trasmessi sulle sottoportanti sia legata alla spaziatura
in frequenza6 dalla relazione B =1/T.
Questo metodo di trasmissione su più sottoportanti anziché su un’unica portante è particolarmente utile su canali di trasmissione molto distorcenti; se infatti si trasmette l’intero flusso R su un’unica portante, si occuperebbe una banda W e si avrebbe forte ISI e, quindi, necessità di una completa equalizzazione di canale.
Figura 1.3 - Suddivisione della banda in sistemi OFDMA
Trasmettendo invece N flussi, ciascuno a velocità N/R, su N sottobande di larghezza B=W/N (Fig.1.3), si può assumere in prima approssimazione che la funzione di trasferimento di canale su ciascuna sottobanda sia non distorcente (se B è sufficientemente piccola) e, quindi, che la funzione di equalizzazione non sia necessaria o venga comunque notevolmente semplificata.
In altre parole, scegliendo opportunamente N, si può garantire che B sia più piccolo della banda di coerenza del canale.
Durante l’intervallo di simbolo OFDM di durata Ts, l’inviluppo
complesso del segnale trasmesso è: 2
( )
j f tn,
0
,
1
n s
n
g t
=
∑
a e
π≤ ≤
t T
0 ≤ ≤ −
n
N
(1.1)Si modulano in ampiezza N sottoportanti a frequenza fn con i simboli di
informazione a0, a1, …, aN-1.
Poiché le sottoportanti sono ortogonali sull’intervallo Ts, i simboli an
possono essere estratti senza interferenza mutua tra gli N canali in parallelo .
Il segnale g(t) costruito con le N sottoportanti andrà poi traslato in frequenza sulla banda del canale trasmissivo, mediante conversione (modulazione) su un’opportuna portante di trasmissione f0.
Un aspetto essenziale che rende spesso vantaggioso questo tipo di trasmissione è che può essere realizzato in modo molto efficiente ricorrendo a tecniche di elaborazione numerica dei segnali, come la FFT7, che consentono notevoli riduzioni di complessità.
Siano g0, g1,…,gN-1 i campioni nel tempo del segnale g(t) presi ad
intervalli Ts/N; si hanno quindi i campioni complessi:
2 1 0
,
0
1
j nk N s N n k ng
g
k
T
a e
k
N
N
π − ==
⎛
⎜
⎞ =
⎟
∑
⋅
≤ ≤ −
⎝
⎠
(1.2)Capitolo 1 – Introduzione
11
Pertanto, dal blocco degli N simboli da trasmettere a0, a1, …, aN-1 si generano mediante trasformazione inversa di Fourier IFFT gli N valori complessi g0, g1,…,gN-1; da questi, disposti in flusso seriale con
intervallo Ts/N tra i campioni, si generano, mediante conversione da
digitale ad analogico delle parti reali ed immaginarie rispettivamente, due segnali analogici x(t) ed y(t) da inviare sul canale trasmissivo mediante modulazione della portante di canale f0.
Il funzionamento del processo appena descritto è illustrato in figura 1.4; in questa immagine si possono vedere i blocchi logici che compongono un modulatore OFDM.
Figura 1.4 - Schema del modulatore OFDM
In ricezione la demodulazione avviene secondo i passo seguenti: *) Si demodula la portante f0 estrendo i segnali x(t) ed y(t).
*) Si prelevano campioni con periodo Ts/N, questi determinano i valori
complessi {gk} a meno dei disturbi.
*) Si calcola la FFT del blocco {gk} in modo da ricostruire i valori dei
simboli di informazione {an}.
*) Vista la presenza di rumore si utilizza un decisore per ottenere i valori più probabili dei simboli an.
In figura 1.5 si può vedere uno schema a blocchi di un demodulatore OFDM che funziona nel modo appena illustrato.
Figura 1.5 - Schema del demodulatore OFDM
La tecnica OFDM consente quindi, in breve, di frazionare un canale distorcente in un insieme di sottocanali paralleli non distorcenti.
1.3 La modulazione OFDMA
La modulazione presa in esame per lo svolgimento della tesi è in realtà l’OFDMA; come si può intuire dal nome OFDM ed OFDMA hanno molto in comune.
Nell’OFDM nelle sottobande ottenute dalla suddivisione dell’intera banda disponibile, vengono trasmessi simboli che provengono da un unico flusso che, a questo scopo, viene smembrato in un certo numero di sottoflussi.
Nell’OFDMA le risorse disponibili vengono invece suddivise con opportuno criterio tra un certo numero di utenti; avremo quindi che verranno trasmessi simboli provenienti da sorgenti diverse.
Capitolo 1 – Introduzione
13
Alla luce di quanto appena detto è evidente che tra i due sistemi sussistono delle differenze, si è comunque scelto di presentare in maniera dettagliata l’OFDM perché questa sta comunque alla base della modulazione OFDMA; infatti, l’OFDMA non è altro che una OFDM ad accesso multiplo.
Nel nostro caso si parla di OFDMA/RA dove la sigla RA8 indica
l’allocazione adattativi delle sottoportanti tra i vari utenti e della modulazione sulle varie sottoportanti.
Questo significa che, a seconda dell’utente considerato, viene scelta una sottoportante od un set di sottoportanti su cui si svolgerà la trasmissione; in alcuni casi9 viene inoltre scelto il numero di bit da trasmettere su ciascuna sottoportante.
Tali scelte vengono fatte in base alla conoscenza della risposta in frequenza del canale per ogni utente.
Vedremo come vengono sfruttate in ambito multi utente le peculiarità di questa modulazione nel capitolo successivo.
1.4 Channel State Information
Quanto detto fino ad ora si basa sulla perfetta conoscenza del canale visto da ogni utente.
Supponiamo che il sistema in considerazione sia formato da una BS10 dove vengono implementati gli algoritmi di allocazione adattativi e da più utenti mobili; per semplicità si può pensare ad un sistema di telefonia cellulare.
8 RA: Resource Allocation.
9 Ci si riferisce a sistemi in cui si utilizza un formato multiplo, approfondiremo questo aspetto nel
prossimo capitolo.
Sarà necessario un link a parte su cui BS e singoli utenti si scambiano informazioni sul canale visto istantaneamente da ciascun utente.
Nell’implementazione dei nostri algoritmi di allocazione di risorse si da per scontato una perfetta conoscenza del canale per ogni utente.
1.5 Feedback information
Al fine di comunicare all’utente quali sottoportanti sono state ad esso assegnate e qual è, eventualmente, la modulazione utilizzata su ogni sottoportante, la BS trasmette una certa quantità di overhead, contenente appunto le informazioni necessarie alla successiva demodulazione del segnale.
Tale overhead può comunque essere relativamente corto, specialmente nel caso in cui il canale vari molto lentamente e l’assegnazione non sia fatta per ogni simbolo OFDM ma dopo alcuni di essi.
Per ridurre ulteriormente l’overhead si può assegnare una banda contigua di sottoportanti con caratteristiche di attenuazione simili come se fosse un gruppo, anziché assegnare ogni sottoportante in maniera indipendente dalle altre.
Nel seguito, però, non verrà trattato come le informazioni di allocazione vengono tramesse dalla BS agli utenti.
1.6 Applicazioni
Le tecniche OFDM vengono largamente utilizzate in molti sistemi wireless moderni.
Capitolo 1 – Introduzione
15
Facciamo una panoramica di queste attuali tecnologie per capire in che modo le tecniche OFDM incidono nella vita quotidiana.
1.6.1 ADSL
I sistemi ADSL11 vengono sfruttati per l’accesso a larga banda all’attuale rete fissa di telecomunicazioni attrverso doppini telefonici in rame; i sistemi ADSL fanno uso della modulazione OFDM multiportante.
La trasmissione duplex (in upstream ed in downstream) è effettuata in divisione di frequenza, con bande diverse per le due direzioni e coesiste con la trasmissione del tradizionale segnale fonico.
Nella banda al di sopra di quella riservata alla telefonia analogica tradizionale (4KHz) si dispongono una serie di sottoportanti equispaziate di circa 4.3KHz: da 25 a 125 KHz circa per la direzione utente – centrale, da 160 a 1100 KHz circa per la direzione opposta.
I flussi digitali previsti arrivano fino a circa 600 Kbit/s in upstream ed 8 Mbit/s in downstream; i valori effettivi dipendono dalle caratteristiche specifiche del canale (lunghezza, incidenza della diafonia, ecc.).
La gestione dello spettro nella tratta su doppino nei sistemi ADSL appena descritta è illustrata in figura 1.6.
Figura 1.6 – Spettro su doppino telefonico in sistemi ADSL
Durante la fase di trining, il modem ADSL testa quali sono i canali con un miglior rapposto segnale-rumore e sceglie di effettuare la trasmissione sui canali selezionalti, implementando tecniche dette di bit loading.
Si noti che sul canale telefonico analogico classico si riescono a trasmettere flussi dati fino alla velocità di 33 Kbit/s.
D’altra parte, su lunghezze di doppino sufficientemente ridotte ( inferiori al Km ), si può spingere la velocità di trasmissione a valori superiori, dell’ordine dei 20 Mbit/s ( sistemi VDSL).
1.6.2 WiLan
Il termine WiLan12indica una rete locale senza fili che sfrutta la tecnologia wireless; con tale sigla si indicano genericamente tutte le reti
Capitolo 1 – Introduzione
17
locali di computer che non utilizzano collegamenti via cavo per connettere fra loro gli host della rete.
Rispetto alle reti cablate le WiLan presentano alcuni vantaggi: *) Raggio di azione di un centinaio di metri.
*) Consentono la mobilità dei terminali. *) Rendono il sistema molto scalabile.
*) Consentono di avere reti locali anche in luoghi dove risulta molto difficile cablare.
ma anche degli svantaggi:
*) Sono sistemi che lavorano con maggiore interferenza.
*) I canali di propagazione visti dgli utenti in una WiLan sono più svantaggiosi rispetto a quelli che vengono visti in una rete cablata.
*) Gli utenti del sistema hanno a disposizione rate inferiori.
*) Le comunicazioni sono meno sicure perché più facilmente intercettabili.
Lo standard più famoso per le WiLan è l’802.11, cioè il Wi – Fi.
La prima versione13prevedeva rate di 1-2 Mbit/s facendo uso di bande posizionate nello spettro intorno ai 2.4 GHz14.
Con il passare del tempo sono state create nuove versioni dello standard: *) 802.11a, rate fino a 54 Mbit/s, fa uso dell’OFDM su bande intorno ai 5 GHz.
*) 802.11b, rate massimo di 11 Mbit/s, fa uso della banda ISM.
13 Anni ’90.
*) 802.11g, rate fino a 54 Mbit/s, lavora nella banda ISM.
*) 802.11n, enstensione dell’ 802.11g con l’uso di antenne multiple. A prescindere dalla versione dello standard preso in esame due o più terminali che comunicano costituiscono una BSS15.
Si possono avere due tipi di BSS:
*) IBSS16: non prevede la presenza di un access point, per cui i terminali comunicano direttamente tra di loro.
*) Structurated BSS: prevedono la presenza di un’AP che farà da intermediario tra tutte le comunicazioni tra due terminali, questo tipo di sistema richiede il doppio della banda di IBSS.
L’approccio più interessante è il secondo, infatti, presenta molti vantaggi rispetto ad un sistema senza AP:
*) BSS strutturate possono essere collegate tra di loro tramite gli AP. *) Unendo più BSS si forma una ESS17.
*) Tramite AP, oltre ad altre BSS, ci si può collegare anche a Lan cablate od addirittura su Internet.
*) La mobilità è permessa all’interno di una ESS, avremo autenticazione e associazione/dissociazione di un terminale ad un’AP.
15 BSS: Basic Service Set.
16 IBSS: Independent Basic Service Set. 17 ESS: Extended Basic Service Set.
Capitolo 1 – Introduzione
19
1.6.3 WiMax
Lo standard IEEE 802.16, conosciuto anche come WiMax18, viene
utilizzato per sistemi fissi punto-multipunto a banda larga con accesso wireless (BWA) che offrono servizi multipli tra cui voce, trasferimento dati ad alta velocità per usi come video conferenza, video on demand, ecc.
L’architettura di riferimento è costituita da una BS19 che interconnette un certo numero di SS20 in modalità infrastrutturata point to multipoint, oppure da due BS che comunicano in modalità point to point per realizzare una rete dorsale di tipo wireless.
Lo standard prevede l’utilizzo di frequenze che appartengono alla banda che va dai 10 ai 66 GHz. L’utilizzo di questa banda richiede una licenza e prevede un ambiente fisico in cui, a causa della lunghezza d’onda ridotta, è necessario un cammino diretto ed il mulitpath è trascurabile. I canali usati in questo ambiente fisico sono a banda larga; ad esempio, i canali tipici sono larghi 25 o 28MHz.
Il successivo aggiornamento, finalizzato alla ratifica dello standard 802.16a, prevede l’uso della banda tra i 2 e gli 11 GHz e, quindi, un ambiente fisico in cui, poiché la lunghezza d’onda è maggiore, non è necessario il LOS21 path ma diviene significativo il multipath.
L’abilità nel supportare scenari sia near LOS che non, richiede funzionalità di livello fisico (PHY) supplementari, quali avanzate tecniche di gestione della potenza, la mitigazione/coesistenza dell’interferenza e le antenne mutiple.
18 WiMax: Worldwide Interoperability for Microwave Access Forum. 19 BS: Base Station.
20 SS: Subscriber Station. 21 LOS: Line Of Sight.
Il livello fisico di questo standard può essere scelto tra cinque possibili alternative, a seconda di diversi fattori tra cui gli specifici campi di applicazione, le bande frequenziali di lavoro, i regolamenti ambientali, ecc.
Le opzioni di nostro interesse sono due:
*) WirelessMAN-OFDM PHY: fa uso della modulazione OFDM ed è progettato per lavorare in NLOS nella banda di frequenza 2-11 GHz per sistemi wireless broadband.
*) WirelessMAN-OFDMA PHY: fa uso della modulazione OFDMA, con una FFT a 2048 punti ed un accesso fornito indirizzando un sottoinsieme delle sottoportanti verso uno specifico ricevitore; è progettato per applicazioni NLOS in bande di frequenza sotto gli 11 GHz.
1.6.4 Osservazioni
Rispetto a ciò che si è visto nell’introduzione il lavoro svolto per la stesura di questo elaborato si trova ad un livello più alto.
Il nostro obiettivo era infatti quello di trovare e simulare algoritmi che permettessero di risolvere in maniera efficiente il problema di allocazione di risorse.
Per raggiungere il nostro scopo abbiamo fatto diverse ipotesi ed utilizzati molti concetti dati per scontati astraendoci spesso dalla realtà fisica della situazione.
Nel secondo capitolo viene illustrata l’architettura delle situazioni in cui gli algoritmi progettati trovano applicazione ed una descrizione dettagliata del problema che gli stessi tentano i risolvere.
Capitolo 1 – Introduzione
21
Nel capitolo tre vengono esposti ed analizzati gli algoritmi che si sono studiati.
Nel quarto capitolo sono presentate le prestazioni delle soluzioni studiate.
Il capitolo cinque è dedicato alle conclusioni che si possono derivare dal lavoro svolto riguardo alle tecniche studiate ed implementate per risolvere il problema di allocazione di risorse.
