Capitolo 1 Introduzione
4
suddividono generalmente la cella in tre settori di 120° , tramite tre antenne direttive. Il fatto che ci
siano solo tre settori è piuttosto limitante per la multiplazione spaziale, ma se il loro numero fosse
alto esploderebbe il numero di handover dovuti al passaggio di un terminale da un settore a un
altro. Le antenne phased array invece sono quelle che configurano il proprio diagramma di
radiazione per la ricezione del segnale desiderato, tramite una tecnica di beam forming, per cui la
massima potenza di radiazione sarà indirizzata verso il segnale di interesse. Infine le antenne
adaptive array oltre che al beam forming, attuano anche un procedimento di null forming; ciò
significa che non solo il lobo principale del diagramma di radiazione viene puntato verso il segnale
di interesse, ma anche i lobi laterali vengono configurati così che si abbiano degli zeri di radiazione
in corrispondenza dei segnali interferenti. Vedremo che le antenne phased array sono le più
indicate per sistemi cellulari.
I sistemi SDMA generalmente sono sovrapposti ad altri sistemi ad accesso multiplo, come per
esempio quello a divisione di tempo (TDMA). In questo caso ogni time slot può essere diviso in un
certo numero di canali spaziali, in modo che il numero totale di canali non interferenti sia
incrementato. Un difetto di questo schema è che i canali spaziali sono in pratica raramente
ortogonali. Se più terminali sono serviti in uno stesso time slot senza considerare le loro
caratteristiche spaziali, quello con una sfavorevole configurazione spaziale subirà notevoli
svantaggi in termini di throughput. Se infatti due terminali sono angolarmente molto vicini, i fasci
dell’array di antenne che li ricevono non possono separare bene le due trasmissioni, e si genererà
una componente non trascurabile di interferenza. Una soluzione fondamentale a questo problema è
quella di avere un MAC che controlla il traffico basandosi sulle caratteristiche spaziali dei
terminali. Per questo sono stati studiati degli algoritmi per schedulare le trasmissioni in trame
SDMA/TDMA. Se si volesse ulteriormente aumentare la capacità del sistema, si potrebbe anche fare
ricorso all’accesso a divisione di codice (CDMA), che multipla più trasmissioni nello stesso canale
spaziale; in pratica ogni fascio dell’array di antenne può servire più sessioni a divisione di codice.
Analizzeremo quindi i principali algoritmi di scheduling trovati in letteratura e vedremo come essi
siano accomunati dalla finalità di schedulare le trasmissioni cercando di ottimizzare una funzione
di costo, sia essa il throughput del sistema, o la capacità o la potenza di trasmissione nella tratta
downlink. Si vedrà che in tutti i casi un algoritmo esatto avrebbe una complessità computazionale
molto elevata e non potrebbe essere utilizzato realmente in una stazione base. Per questo gli
algoritmi proposti sono delle euristiche più o meno performanti che danno una soluzione sub-
ottima ai problemi di ottimizzazione.
L’obiettivo di questa tesi consiste nel progettare degli algoritmi di scheduling alternativi a quelli
proposti in letteratura. Innanzitutto bisogna puntualizzare che il nostro approccio al problema è di
diverso tipo. Infatti ci proponiamo di risolvere il problema dello scheduling come un problema di
Capitolo 1 Introduzione
5
ottimizzazione combinatoria in funzione delle caratteristiche geometriche che contraddistinguono i
terminali nella cella. In pratica si vuole effettuare lo scheduling passando dal rispetto di vincoli
legati alla qualità delle trasmissioni, al rispetto di vincoli di natura geometrica. Per fare questo si è
adottato un modello semplificativo per il sistema. Ci occupiamo della trasmissione nella tratta
uplink e consideriamo una singola stazione base; assumiamo che la cella servita dalla stazione base
sia circolare e che ogni fascio abbia un disegno semplificato con un guadagno costante nel lobo
principale e una forte attenuazione al di fuori di esso. Consideriamo un meccanismo ideale di
controllo di potenza che regoli le potenze in trasmissione in modo che ogni segnale ricevuto abbia
la medesima potenza.
Come parametro di qualità delle trasmissioni si considera il rapporto segnale-interferenza (SIR)
legato alla ricezione, da parte di una generica antenna dell’array, del segnale trasmesso da un
utente. Affinchè i segnali trasmessi dai terminali nella cella siano ricevuti correttamente, il SIR per
ognuno di essi deve essere superiore a un SIR minimo. Con il modello considerato, come vedremo
nel capitolo 4, questo vincolo sul SIR per ogni utente si tramuta in un vincolo sul numero dei
terminali che possono essere al più serviti da un fascio. Indichiamo con N
max
il numero massimo di
terminali servibili da un fascio.
Il compito dello scheduler sarà così quello di ripartire tutti gli utenti della cella in un numero
minimo di sottoinsiemi disgiunti. Ogni sottoinsieme dovrà essere formato da terminali con
caratteristiche spaziali tali da poter trasmettere nel medesimo slot; in pratica a ogni terminale
mobile del sottoinsieme sarà associato un fascio per la sua ricezione, e ogni fascio non dovrà
sottendere un numero di utenti superiore a N
max
. A ogni sottoinsieme sarà fatto corrispondere un
time slot della trama TDMA.
E’ importante notare che se diventa possibile affrontare il problema dello scheduling come un
problema di ottimizzazione combinatoria guardando alle sole caratteristiche geometriche dei
terminali e della cella e al valore N
max
, questo è dovuto al modello semplificativo che prevede un
lobo principale a guadagno costante e dei lobi laterali a guadagno trascurabile. Se infatti i lobi
laterali avessero un guadagno non nullo, anche costante nella più semplice delle ipotesi, non si
potrebbero più trascurare i termini di interferenza derivanti dai segnali di terminali attivi ricevuti
dai lobi laterali.
Dopo aver descritto in dettaglio il modello considerato e formulato il problema di ottimizzazione,
passeremo alla progettazione degli algoritmi. Verranno così proposti due algoritmi di tipo greedy,
che costruiranno la soluzione per passi successivi selezionando ad ogni passo il sottoinsieme di
utenti a peso massimo tra quelli non ancora scelti. Premesso che a ogni utente viene assegnato un
peso che riflette la tipologia di servizio richiesto, i due algoritmi si differenziano per come viene
affrontato il sottoproblema della scelta del sottoinsieme a peso massimo. Mentre uno, chiamato
Capitolo 1 Introduzione
6
algoritmo greedy con i grafi, risolve il sottoproblema in modo esatto utilizzando un algoritmo che
cerca un cammino a peso massimo in un grafo opportuno, l’altro, denominato greedy senza grafi,
trova una soluzione sub-ottima per il sottoproblema, ma in compenso fa registrare tempi di calcolo
molto più bassi. Inoltre verrà proposto per confronto un algoritmo euristico di tipo aleatorio.
Poichè tutti questi algoritmi non garantiscono di trovare la soluzione ottima al problema della
minimizzazione del numero di slot, saranno presentate due diverse strategie per cercare se possibile
una soluzione migliore. La prima si basa su una tecnica di ricerca locale che si propone, partendo
dalla soluzione di uno degli algoritmi prima citati, di modificare parzialmente l’assegnamento degli
utenti agli slot con l’obiettivo di ridurre complessivamente il numero degli slot temporali di
assegnazione. La seconda è invece una strategia di greedy randomizzato che lancia ad ogni sua
iterazione uno dei due greedy prima citati, modificati con l’aggiunta di un fattore di variabilità che,
scelto casualmente ad ogni iterazione, consente di ottenere soluzioni diversificate; si terrà poi
memoria della soluzione migliore. Inoltre verrà presentato un criterio per il calcolo di un limite
inferiore, utile per valutare la qualità delle soluzioni ottenute.
In seguito analizzeremo in ambiente off-line le prestazioni degli algoritmi studiati, lavorando con
popolazioni prefissate di terminali distribuiti casualmente nella cella e confrontando in termini di
numero di slot temporali occupati e di percentuale dell’occorrenza del limite inferiore le diverse
strategie di scheduling individuate.
Infine, passeremo all’ambiente on-line ricorrendo alla simulazione per vedere l’impatto degli
algoritmi di scheduling in un contesto tempo-variante.
La tesi è organizzata nel modo seguente: nel capitolo 2 verranno analizzate brevemente le
caratteristiche delle antenne intelligenti ed i vantaggi derivanti dal loro impiego; nel capitolo 3
passeremo in rassegna alcuni algoritmi di scheduling delle trasmissioni presenti in letteratura per
sistemi SDMA/TDMA. Nel capitolo 4 definiremo il problema e presenteremo i modelli di
ottimizzazione; nel capitolo 5 si guarderà agli algoritmi di scheduling. Nel capitolo 6 e nel capitolo
7 si analizzeranno le prestazioni degli algoritmi rispettivamente in ambiente off-line e on-line.
Infine le conclusioni nel capitolo 8.
2 Le antenne intelligenti
Per un sistema di comunicazione cellulare un aspetto sicuramente critico è rappresentato dalla
tipologia di antenne presenti alla stazione base che devono ricevere i segnali provenienti dai
terminali mobili; infatti dalle antenne dipende la capacità del sistema e lo sfruttamento della
limitata banda radio disponibile. Per potenziare le prestazioni del sistema, un primo passo è stato
quello di abbandonare le semplici antenne omnidirezionali, caratterizzate da un uguale guadagno in
tutte le direzioni, per passare ad antenne direzionali, caratterizzate da un diagramma di radiazione
con un lobo principale ad alto guadagno, affiancato da lobi laterali a basso guadagno;
un’applicazione immediata di queste antenne è stato il cosiddetto cell sectoring, per cui vengono
utilizzate più antenne direzionali, ognuna delle quali permette di coprire una porzione limitata
dell’area della cella. Tipicamente vengono utilizzate tre antenne ruotate tra loro di 120°. In questo
modo si è potuto ridurre un termine di interferenza tipico nelle comunicazioni cellulari, cioè
l’interferenza co-canale, dovuta alle comunicazioni nelle celle vicine a cui il fattore di riuso del
cluster ha assegnato la medesima frequenza di lavoro.
Si è parlato fino ad ora di antenne con diagramma di radiazione fisso, che non risolvono i problemi
legati alla mobilità degli utenti o ai cammini multipli, ma si limitano a ridurli concentrando
l’energia trasmessa in un settore della cella. L’antenna ideale è invece un’antenna in grado di
inseguire gli utenti durante i loro spostamenti, dirigendo il fascio principale del diagramma di
radiazione verso il segnale da ricevere e cancellando ogni forma di interferenza dovuta allo
scattering e alla riflessione causati da oggetti che si frappongono tra il terminale e l’antenna o alle
altre trasmissioni attive nella cella. Si tratta quindi di avere a disposizione un’antenna intelligente
che cambi il suo diagramma di radiazione in tempo reale per inseguire i terminali mobili, grazie ad
Capitolo 2 Le antenne intelligenti
8
adeguati algoritmi di digital signal processing, che tengano conto dello stato del canale radio verso
ogni destinazione raggiungibile e della direzione di arrivo (DOA) dei segnali ricevuti.
Seguendo la trattazione proposta in [3] e in [7], le antenne in generale possono essere classificate
come omnidirezionali, direzionali, phased array e adattative.
Come già visto precedentemente, un’antenna omnidirezionale ha un uguale guadagno in tutte le
direzioni ed è conosciuta anche come antenna isotropa; le antenne direzionali invece hanno un
guadagno maggiore in una certa direzione e minore nelle altre direzioni. Il guadagno nella
direzione di massimo guadagno è maggiore del guadagno delle antenne omnidirezionali. Si è già
parlato dell’utilizzo di un insieme di antenne direzionali per il cell sectoring, che consente la
riduzione dell’interferenza co-canale. Un evoluzione della tecnica di settorizzazione della cella è
rappresentata dai cosiddetti sistemi Switched Beam.
Capitolo 2 Le antenne intelligenti
9
2.1 Sistemi Switched Beam
Il sistema switched beam è stato proposto come una estensione della settorizzazione delle celle, in
cui ciascuno dei tre settori di 120° individuati da tre antenne direzionali viene suddiviso in
microsettori, ognuno coperto con una antenna direzionale fissa avente il massimo guadagno al
centro del lobo principale di radiazione. Questa soluzione prevede una funzione di commutazione
capace di scegliere per ogni segnale ricevuto l’antenna che garantisce il maggiore rapporto segnale-
rumore. La stazione base può essere vista come un array di antenne gestite con una matrice di
Butler, a cui spetta il compito di analizzare i segnali ricevuti da ogni antenna, valutando il livello di
potenza per ciascuna sessione trasmissiva attiva e l’interferenza complessiva che vi si sovrappone,
determinando per ogni segnale quale è l’antenna per cui è massimo il rapporto segnale ricevuto-
interferenza.
Dal punto di vista del guadagno, si può dire che utilizzando un sistema di M antenne per
macrosettore, l’aumento di guadagno rispetto alla settorizzazione della cella con tre antenne a 120°,
è dato da G = 10 Log ( M ), con conseguenti miglioramenti dal punto di vista della copertura della
cella e dell’aumento della capacità di ricezione. Questo aumento di guadagno non è però ottenibile
in tutti i punti del settore, per via della diminuzione della direttività delle antenne allo spostarsi dal
centro del lobo principale di radiazione.
In conclusione si può dire che i sistemi switched beam portano ad un aumento di guadagno che
consente ai terminali mobili di utilizzare una potenza minore in trasmissione e consentono una
riduzione dell’interferenza co-canale. D’altronde poiché i fasci delle antenne sono fissi e
predeterminati la potenza del segnale ricevuto varia con la posizione dell’utente nel microsettore.
Quindi, quando un terminale è prossimo al bordo del fascio, prima di essere commutato su un
nuovo fascio, il suo segnale ricevuto dall’antenna si può rapidamente degradare, influenzando
soprattutto le classi di servizio con i parametri di qualità più stringenti. Un altro limite di questi
sistemi è che all’aumentare dei micro-settori devono necessariamente aumentare le operazioni alla
base station per gestire lo sfruttamento delle risorse radio, a causa dei numerosi handover
conseguenti alla mobilità degli utenti.
Capitolo 2 Le antenne intelligenti
10
2.2 Sistemi Phased Array
Il sistema phased array presenta un livello maggiore di intelligenza rispetto al sistema switched
beam presentato nel paragrafo precedente.
Un’antenna phased array è costituita da un insieme di semplici antenne, per esempio
omnidirezionali, e combina il segnale ricevuto da ciascuna di esse per aumentare il rapporto
segnale-rumore delle sessioni trasmissive attive. La direzione di puntamento dell’array, cioè quella
di massimo guadagno, viene determinata regolando lo sfasamento relativo dell’alimentazione degli
elementi che lo compongono. In pratica il DSP stima le direzioni di arrivo dei segnali, sfruttando lo
sfasamento tra le repliche ricevute dai diversi elementi del vettore, e regola dinamicamente
l’alimentazione dell’array in modo che il lobo principale del diagramma di radiazione dell’array
punti verso l’utente di interesse. Questo procedimento viene chiamato beam forming e il grande
vantaggio rispetto al sistema a commutazione di fascio consiste nel fatto che ora il segnale
desiderato viene ricevuto con il massimo livello di potenza possibile, associando al terminale un
fascio che lo serve durante tutta la durata della connessione, a prescindere dai movimenti entro la
cella. Inoltre si risolve uno dei limiti della settorizzazione della cella: se da una parte utilizzare
antenne con fascio sempre più stretto consente di migliorare le prestazioni del sistema cellulare,
dall’altra fa esplodere il numero di handover durante una connessione.
Nelle antenne phased array si ha quindi la possibilità di scegliere il puntamento del lobo principale,
mentre non è previsto un controllo sui lobi laterali a guadagno minore, che restano solidali con il
main lobe; in questo modo non si può controllare l’interferenza che essi captano. In altre parole non
è previsto per questa tipologia di antenne il null forming, cioè la possibilità di eliminare i segnali
indesiderati modificando il diagramma di radiazione con il posizionamento degli zeri nella loro
direzione.
Capitolo 2 Le antenne intelligenti
11
2.3 Sistemi Adaptive Array
Questo sistema presenta la massima forma di intelligenza per le antenne dislocate alla stazione
base.
Con il termine antenne adattive ci si riferisce ad un sistema phased array in cui non solo la fase ma
anche i guadagni di ciascun elemento del vettore possono essere modificati prima di sommare i
segnali ricevuti sulle singole antenne in modo da massimizzare il guadagno complessivo dell’array.
In altre parole ad ogni elemento può essere associato un peso complesso variabile che permette di
focalizzare l’array sul segnale di interesse limitando il più possibile l’interferenza da parte degli
altri segnali. A questo proposito si può vedere la Figura 2.1.
Antenne
dell’array
Segnali
ricevuti
Schema adattativo di
controllo dei pesi
+
Pesi adattativi
Segnale di uscita
Figura 2.1
Capitolo 2 Le antenne intelligenti
12
I sistemi adattativi consentono una forte riduzione dell’interferenza co-canale attraverso la
determinazione della direzione di puntamento sia del lobo principale del diagramma di radiazione,
sia degli zeri mediante una scelta opportuna dei pesi complessi
i
w da associare ad ogni elemento
dell’antenna. Si possono distinguere tre diversi algoritmi in grado di calcolare i pesi
i
w
minimizzando differenti funzioni di costo:
ξ massimo rapporto segnale-interferenza (MSIR)
ξ minimo errore quadratico medio (MMSE)
ξ minima varianza (MV)
Nel caso della massimizzazione del SIR si rende necessaria, attraverso l’analisi degli sfasamenti
delle repliche dello stesso segnale ricevute sui diversi elementi del vettore, l’individuazione delle
direzioni di arrivo dei segnali trasmessi dalle mobile stations e quindi la loro posizione angolare
entro la cella. Note le DOA, si è in grado di raggruppare i terminali in clusters e modificare il
diagramma di radiazione modo da dirigere il lobo principale verso uno specifico gruppo di utenti,
puntando gli zeri verso gli altri clusters. Le operazioni che il DSP deve realizzare sono quindi
essenzialmente due: stimare la direzione di arrivo per ciascuno dei terminali mobili attivi entro la
cella e regolare i pesi complessi associati ad ogni elemento d’antenna per limitare al massimo
l’interferenza co-canale sui segnali di interesse, massimizzando il SIR.
L’algoritmo MMSE, invece, punta alla minimizzazione dell’errore quadratico medio tra il segnale
di uscita dell’array ed un segnale di riferimento appositamente inviato dalla mobile station di
interesse. Si tratta di un meccanismo di controllo ad anello chiuso che fornisce prestazioni migliori
rispetto alla soluzione precedente nel caso in cui il segnale da ricevere sia di debole intensità; al
crescere della potenza utile ricevuta, i due algoritmi si comportano più o meno allo stesso modo.
Va notato che il segnale di riferimento può essere generato in molti modi, a seconda
dell’applicazione che si sta supportando. Si può pensare di utilizzare, all’inizio della connessione,
una speciale sequenza di sincronizzazione per stabilire una prima stima dei pesi da assegnare agli
elementi del vettore, per poi basarsi sul segnale reale trasmesso dalla stazione base per il seguito
della comunicazione. In sistemi TDMA è possibile associare ad ogni frame una sequenza
dipendente dall’utente che si vuole servire, semplificando le operazioni che deve svolgere il DSP.
Infine, l’algoritmo MV prevede la minimizzazione della varianza del segnale complessivo in uscita
dall’array. Poiché esso è dato dalla somma del segnale utile e dell’interferenza, questo criterio
rende necessaria la determinazione della matrice di autocorrelazione dell’interferenza stessa, cosa
non sempre semplice ed immediata.
Capitolo 2 Le antenne intelligenti
13
Malgrado i sistemi adattativi abbiano in generale delle prestazioni superiori rispetto agli altri, sono
da preferirsi per i problemi di copertura cellulare i sistemi phased array; infatti in un sistema
CDMA i vantaggi introdotti dalle antenne adattative sono molto ridotti, a fronte di un notevole
aumento di complessità per le operazioni che il DSP deve compiere. Innanzitutto occorre fare
presente che un array di L elementi ha in generale L-1 gradi di libertà che tipicamente sono la
direzione di massimo guadagno e L-2 nulli nella direzione dei segnali interferenti. Inoltre in un
sistema ad accesso multiplo a divisione di codice le parole di codice utilizzate hanno una bassa
correlazione; il sistema quindi gode già di una interferenza sufficientemente bassa e permette a
molti utenti di essere contemporaneamente attivi sulla stessa banda di frequenze. Quindi il ricorso
ad antenne con null forming non da grandi vantaggi, sia perché non tutti gli interferenti potrebbero
essere soppressi in quanto i gradi di libertà dell’array sono limitati dall’esigenza di ridurre
l’occupazione spaziale delle antenne stesse, sia perché gli zeri sarebbero diretti verso segnali che
subirebbero una già forte attenuazione per via della correlazione in ricezione con la parola di
codice.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
