UNIVERSITA’ DEGLI STUDI DI
PERUGIA
Corso di Laurea Specialistica in
Informatica
“Laboratorio Reti di Computer 2”
Assegnamento
Canali/Frequenze in
Reti Wireless MAN e
WAN
Studente:
Valentino Santucci
Simone Cordidonne
Docente:
Prof. Antonio Riganelli
Perché è importante

Le reti wireless su aree medio/grandi
(MAN/WAN) sono in parte realtà (reti
di fonia cellulare: GSM,UMTS) ed in
parte in fase di sperimentazione (reti
a banda larga: WiMax,Hyperman).
2
Rete di fonia cellulare: GSM (1/2)
Il Global System for Mobile
Communications (GSM) è
attualmente lo standard di telefonia
mobile più diffuso del mondo.
 ll servizio principale della rete GSM e'
chiaramente la comunicazione
vocale. Con il tempo però sono stati
implementati altri servizi importanti
quali gli SMS e la comunicazione
dati.

3
Rete di fonia cellulare: GSM (2/2)
Le frequenze usate dalla rete GSM
sono 850, 900, 1800, 1900 MHz e
variano a seconda degli stati in cui la
rete stessa e' installata.
 Tipicamente nelle nazioni europee si
utilizza l’intervallo di frequenze 9001800 MHz, mentre negli Stati Uniti le
frequenze usate sono 850-1900 MHz.

4
Rete di fonia cellulare: UMTS (1/2)
Universal Mobile Telecommunications
System (UMTS) è la tecnologia di
telefonia mobile di terza generazione
(3G) successore del GSM.
 Le applicazioni tipiche attualmente
implementate, usate dalla reti UMTS
in Italia, sono tre: voce (12,2 Kbit/s),
videoconferenza (64 Kbit/s) e
trasmissione dati a pacchetto (384
Kbit/s).

5
Rete di fonia cellulare: UMTS (2/2)

Le bande di frequenza originariamente
previste per lo standard UMTS sono
1885-2025 MHz e 2110-2200 MHz,
rispettivamente per la trasmissione e
la ricezione.
6
Reti wireless a banda larga: WiMax
(1/2)
WiMAX (IEEE 802.16) è una tecnologia
di rete MAN senza fili che connetterà
ad Internet gli hotspot Wi-Fi e fornirà
una estensione wireless alle
connessioni a cavo e DSL per l'accesso
in banda larga dell’ultimo miglio.
 IEEE 802.16 consente una estensione
di area di servizio lineare fino a 50 km
e consente agli utenti una connettività
ad una stazione base verso la quale
manca una linea diretta di vista.

7
Reti wireless a banda larga: WiMax
(2/2)

Il più recente standard pubblicato
802.16a contempla ambienti per
sistemi che operano in bande tra 2 e
11 GHz con la possibilità di gestire
trasmissioni in ambiente Non-Lineof-Sight, "Non A Vista“.
8
Reti wireless a banda larga:
HIPERMAN

HIPERMAN (High Performance Radio
Metropolitan Area Network) è uno
standard creato dall’ETSI (European
Telecommunications Standards
Institute) per reti wireless per
sistemi che operano in bande tra 2 e
11 GHz in Europa e costituisce
un’alternativa allo standard 802.16
del WiMax.
9
Digital Divide (1/2)
Con Digital Divide (divario digitale) si
intende il divario esistente
nell'accesso alle telecomunicazioni a
banda larga.
 Causato da una inadeguata presenze
di infrastrutture di rete sul territorio.

10
Digital Divide (2/2)
Il problema del Digital Divide non è
presente soltanto all’interno di paesi
sottosviluppati, ma anche nelle
nazioni più tecnologicamente
evolute.
 Dovuto principalmente alla difficoltà
di piazzare infrastrutture di rete in
zone montuose o impervie in
generale.

11
Es. Copertura ADSL
La copertura del territorio italiano
con accessi a Internet a velocità
superiori a 1 Mb/sec (quindi a banda
larga) è intorno al 50% nel quale
rientrano i 20 maggiori centri (Roma,
Milano, Torino, Genova, Napoli, etc.).
 Ben al di sotto della media europea
(95% di Regno Unito, oltre il 90% in
Francia) e di stati con un territorio
più vasto dell'Italia e una più bassa
densità abitativa e quindi più piccoli
centri da coprire.

12
Soluzione

In Francia e Inghilterra tale livello di
copertura è in buona parte dovuto
all'utilizzo diffuso di tecnologie
wireless, liberalizzate da alcuni anni,
per servire territori in cui non è
conveniente un servizio DSL oppure
la posa della Fibra ottica.
13
WLL
II Wireless Local Loop rappresenta
una via per fornire servizi voce e dati
a case e uffici senza dover passare
per l'ultimo miglio tradizionale,
ovvero quello che lega le abitazioni
alla rete telefonica.
 I sistemi basati su WLL impiegano lo
spettro di frequenze a 26 Ghz e
consentono di "irradiare" le città con
un numero limitato di antenne.

14
Internet a banda larga senza fili
Nella telefonia senza fili fissa, una
"wireless local loop" puo' sostituire
l'ultima connessione (last mile) di
una rete telefonica cablata fissa,
qualora tale rete cablata non sia
realizzabile a costi ragionevoli, come
avviene nei paesi desertici o in via di
sviluppo.
 In tal caso è richiesto di assegnare
una frequenza ad ogni stazione.

15
Telefonia Cellulare
Nella telefonia cellulare mobile, un
utente mobile all'interno di una cella
si connette con la stazione base della
cella medesima.
 Poiché si richiede una connessione
individuale per ogni utente nella
stessa cella, è necessario assegnare
molti canali alla stessa stazione.

16
Limiti dello spettro radio

Problema: sono presenti in genere
molte celle ma ci sono poche
frequenze disponibili così che per
utilizzare al massimo lo spettro radio
è necessario un efficiente algoritmo
di assegnamento delle frequenze.
17
Interferenze
La maggior difficoltà verso un utilizzo
efficiente dello spettro radio è dato
dalle interferenze.
 Causano una bassa qualità del
segnale radio e quindi la necessità di
ritrasmissione dei messaggi.
 Tuttavia possono essere eliminate (o
per lo meno ridotte) con accurati
tecniche di assegnamento dei canali.
 Si distinguono 2 tipi di interferenze...

18
Interferenza Co-canale




Interferenza co-canale: si verifica quando
due utenti siti in celle adiacenti (o vicine)
utilizzano lo stesso canale.
Interferenza molto critica che dipende
fortemente dal traffico cellulare.
La possibilità che si verifichi è maggiore
nelle ore in cui il sistema cellulare è più
indaffarato.
Lo stesso canale può essere riutilizzato da
due stazioni contemporaneamente senza
interferenza se e solo se le due stazioni
sono sufficientemente lontane.
19
Interferenza Adiacente




Interferenza da canale adiacente: si verifica
quando due utenti siti nella stessa cella o in celle
adiacenti utilizzano due canali adiacenti.
I fenomeni di interferenza possono essere così
forti che anche canali distinti utilizzati in stazioni
vicine possono interferire se i canali sono troppo
vicini.
Canali assegnati a stazioni vicine devono essere
separati da un intervallo che è inversamente
proporzionale alla distanza tra le stazioni.
Dipende da limitazioni di equipaggiamento dei vari
client (p.e. filtri passabanda dei ricevitori non
20
ideali).
Assegnamento Canali

Allocare canali radio ad una base
station (e quindi ad una cella) in
modo da ottenere:
• Utilizzo efficiente dello spettro di
frequenze a disposizione.
• Ridurre al minimo le interferenze.
• Buona qualità del servizio.

Problema NP-Completo per topologie
di rete generiche (e quindi grafi
generici).
21
Classificazione Algoritmi (1/2)

FCA (Fixed Channel Assignment)
• Assegnamento statico, cioè effettuato
una volta per tutte in base ad una stima
delle richieste di connessioni simultanee
per ciascuna stazione.

DCA (Dynamic Channel Assignment)
• Assegnamento dinamico, cioè effettuato
in linea all'atto della effettiva necessità
di utilizzare un canale libero per una
comunicazione.
22
Classificazione Algoritmi (2/2)

HCA (Hybrid Channel Assignment)
• Assegnamento misto, dove un
sottoinsieme di canali per ciascuna
stazione è assegnato in modo statico ed
il resto in modo dinamico,
eventualmente prendendo a prestito da
una stazione vicina un canale
momentaneamente non utilizzato.
23
FCA (1/2)




FCA ha il vantaggio di non richiedere alti
costi computazionali al momento
dell’assegnazione della frequenza.
Gode di performance migliori rispetto a
DCA ed HCA, soprattutto in situazioni di
traffico elevato ed uniforme.
E’ spesso usato nella pratica (reti
cellulari di 1° e 2° generazione).
Il problema FCA rappresenta comunque
un bound ai problemi DCA ed HCA.
24
FCA (2/2)
FCA è in genere testato con
opportune istanze di benchmark.
 Usualmente è utilizzato il benchmark
Philadelphia:

• 21 esagoni che denotano le celle della
rete cellulare.
• I trasmettitori sono localizzati al centro
della cella.
• La distanza tra celle adiacenti è sempre
fissa e considerata 1.
25
Modello matematico

Un sistema cellulare è rappresentato
come un grafo dove:
• I nodi rappresentano le base-station.
• Gli archi collegano due base-station che
hanno un’intersezione nella loro area di
copertura.
26
Distanza di riuso del canale (1/2)


La distanza tra due nodi è il minimo
numero di archi da attraversare per
andare da un nodo all’altro.
L’eliminazione delle interferenze
cochannel è modellata introducendo il
vincolo della distanza di riuso del
canale (σ); ovvero un canale può
essere utilizzato contemporaneamente
in due nodi se e solo se tali nodi si
trovano a distanza maggiore o uguale
di σ.
27
Distanza di riuso del canale (2/2)
• Distanza di riuso σ=2.
28
Vettore di separazione dei canali
(1/2)
L’eliminazione delle interferenze
cosite e adjacent è modellata
introducendo il vettore di separazione
dei canali (δ1, δ2,…,δi,…,δσ-1).
 Tale vettore rappresenta il gap
(contato in numero di canali) che
deve separare due canali assegnati a
nodi distanti i.

29
Vettore di separazione dei canali
(2/2)
0
1
SPETTRO DI
2
FREQUENZE
3
4
5
30
CAPS (Channel Assignment
Problem with Separation)
I canali radio possono essere
modellati come colori (interi non
negativi).
 CAPS può essere definito come il
problema di trovare una L(δ1,
δ2,…,δσ-1)-colorazione del grafo che
modella la rete.

31
Colorazione grafi


Una L(δ1, δ2,…,δσ-1)-colorazione di un
grafo G=(V,E) è una funzione f:VΛ
dove Λ={0,…,λ} è un insieme di colori
ed f verifica il vincolo:
|f(u)-f(v)|≥ δi se d(u,v)=i per i=1,…,σ1
Una colorazione ottimale di questo tipo
è data da una funzione f che minimizzi il
valore λ, e quindi il numero di colori
(canali) richiesti (λ+1).
32
Limitazioni al numero di colori
Escludendo il vincolo della
separazione dei canali il problema
si riduce a L(1,…,1).
 Un limite inferiore per L(1,…,1) lo
è anche per L(δ1,…,δσ-1).
 L(1,…,1) per il grafo Gn può essere
ridotto al classico problema di
colorazione dei grafi (L(1)) per il
grafo (aumentato) Gn,σ.

33
Il grafo Gn,σ

Gn,σ=(V,E’) è ottenuto da Gn=(V,E)
aggiungendo un arco per ogni coppia
di vertici a distanza minore di σ
(ovvero {u,v}E’  d(u,v)≤σ-1 in
Gn).
σ=3
34
Limitazioni al numero di colori



Per colorare Gn,σ occorre un numero
di colori almeno pari alla dimensione
della massima cricca di Gn,σ.
Una cricca è un sottoinsieme di
vertici del grafo totalmente connessi
(proprio per questo servono colori
diversi).
La dimensione di una cricca è data
dal numero di vertici che la
compongono.
35
Cenni sulla complessità
CAPS è NP-Completo per grafi
generici.
 Infatti, già L(2,1) è intrattabile.
 Esistono, comunque, efficienti
algoritmi per colorazioni ottimali
da applicare a specifiche topologie
di grafi.

36
Topologia cellulare (o esagonale)

Utilizzata nella pratica perché copre
l’intero piano euclideo minimizzando il
numero di base-station necessarie.
37
Algoritmo per L(2,1,1)-colorazione
per griglie cellulari (1/3)
Algoritmo ottimale per griglie
cellulari di dimensione r x c con r≥4
e c≥4.
 Lemma: Esiste una colorazione
ottimale solo se λ≥11 (perché in tali
grafi la massima cricca ha
dimensione 12).

38
Algoritmo per L(2,1,1)-colorazione per
griglie cellulari (2/3)
39
Algoritmo per L(2,1,1)-colorazione
per griglie cellulari (3/3)
40
Complessità
L’algoritmo opera in tempo costante
O(1) se ogni stazione (vertice)
conosce la propria posizione logica
all’interno del grafo.
 Se così non fosse basterebbe dotare
ogni stazione di un sistema GPS
cosicché conosca la propria
posizione assoluta e far girare poi
un semplice algoritmo distribuito e
polinomiale.

41
Position Discovering su griglia
cellulare (1/2)



La computazione inizia dal nodo in alto
a sinistra che è l’unico che conosce la
sua posizione logica (0,0).
Viene inviato un messaggio di controllo
del tipo CM(v,gv,i,j) dove gv è la
posizione geografica di v ed i,j è la
posizione logica.
Quando un vertice u riceve il messaggio
confronta la sua posizione geografica
con gv e calcola la sua posizione logica
inviando poi lui stesso un messaggio.
42
Position Discovering su griglia
cellulare (2/2)
(0,0)
(0,1)
(0,2)
(0,3)
(1,0)
(1,1)
(1,2)
(1,3)
(2,0)
(2,1)
(2,2)
(2,3)
(3,0)
(3,1)
(3,2)
(3,3)
Tempo: O(max(r,c))
Numero Messaggi Scambiati: O(rc)
43
Perchè non si usano Frequenze
Guardia (1/2)
SPETTRO DI
FREQUENZE
44
Perchè non si usano Frequenze
Guardia (2/2)




Nei vari algoritmi FCA per grafi
regolari (incluso quello visto) non
occorrono canali extra per evitare
l’interferenza dovuta a frequenze
adiacenti.
Banda per frequenze guardia:
Wguard=(λ+1)β+λγ
Banda per separazione dei canali:
Wseparation=(λ’+1)β
λ = λ’  Wseparation<Wguard
45
FINE