Assegnamento Assegnamento Canali/Frequenze in Reti Canali/Frequenze in Reti

Wireless MAN e WANWireless MAN e WAN

UNIVERSITA’ DEGLI STUDI DI UNIVERSITA’ DEGLI STUDI DI PERUGIAPERUGIA

Corso di Laurea Specialistica in Informatica

Studente:

Valentino Santucci

Simone Cordidonne

“Laboratorio Reti di Computer 2”

Docente:

Prof. Antonio Riganelli

22

Perché è importantePerché è importante

Le reti wireless su aree medio/grandi Le reti wireless su aree medio/grandi (MAN/WAN) sono in parte realtà (reti (MAN/WAN) sono in parte realtà (reti di fonia cellulare: di fonia cellulare: GSMGSM,UMTS) ed in ,UMTS) ed in parte in fase di sperimentazione (reti parte in fase di sperimentazione (reti a banda larga: a banda larga: WiMaxWiMax,Hyperman).,Hyperman).

33

Rete di fonia cellulare: GSM (1/2)Rete di fonia cellulare: GSM (1/2)

Il Il Global System for Mobile Global System for Mobile Communications (GSM)Communications (GSM) è è attualmente lo standard di telefonia attualmente lo standard di telefonia mobile più diffuso del mondo.mobile più diffuso del mondo.

ll servizio principale della rete GSM e' ll servizio principale della rete GSM e' chiaramente la comunicazione chiaramente la comunicazione vocale. Con il tempo però sono stati vocale. Con il tempo però sono stati implementati altri servizi importanti implementati altri servizi importanti quali gli SMS e la comunicazione dati. quali gli SMS e la comunicazione dati.

44

Rete di fonia cellulare: GSM (2/2)Rete di fonia cellulare: GSM (2/2)

Le frequenze usate dalla rete GSM Le frequenze usate dalla rete GSM sono 850, 900, 1800, 1900 MHz e sono 850, 900, 1800, 1900 MHz e variano a seconda degli stati in cui la variano a seconda degli stati in cui la rete stessa e' installata.rete stessa e' installata.

Tipicamente nelle nazioni europee si Tipicamente nelle nazioni europee si utilizza l’intervallo di frequenze utilizza l’intervallo di frequenze 900-900-1800 MHz1800 MHz, mentre negli Stati Uniti le , mentre negli Stati Uniti le frequenze usate sono 850-1900 MHz. frequenze usate sono 850-1900 MHz.

55

Rete di fonia cellulare: UMTS (1/2)Rete di fonia cellulare: UMTS (1/2)

Universal Mobile Telecommunications Universal Mobile Telecommunications System (UMTS)System (UMTS) è la tecnologia di è la tecnologia di telefonia mobile di terza generazione telefonia mobile di terza generazione (3G) successore del GSM.(3G) successore del GSM.

Le applicazioni tipiche attualmente Le applicazioni tipiche attualmente implementate, usate dalla reti UMTS implementate, usate dalla reti UMTS in Italia, sono tre: voce (in Italia, sono tre: voce (12,2 Kbit/s)12,2 Kbit/s), , videoconferenza (videoconferenza (64 Kbit/s) 64 Kbit/s) e e trasmissione dati a pacchetto (trasmissione dati a pacchetto (384 384 Kbit/s)Kbit/s)..

66

Rete di fonia cellulare: UMTS (2/2)Rete di fonia cellulare: UMTS (2/2)

Le bande di frequenza originariamente Le bande di frequenza originariamente previste per lo standard UMTS sono previste per lo standard UMTS sono 1885-2025 MHz e 2110-2200 MHz1885-2025 MHz e 2110-2200 MHz, , rispettivamente per la trasmissione e rispettivamente per la trasmissione e la ricezione. la ricezione.

77

Reti wireless a banda larga: WiMax Reti wireless a banda larga: WiMax (1/2)(1/2)

WiMAX (IEEE 802.16)WiMAX (IEEE 802.16) è una tecnologia è una tecnologia di rete MAN senza fili che connetterà di rete MAN senza fili che connetterà ad Internet gli hotspot Wi-Fi e ad Internet gli hotspot Wi-Fi e fornirà fornirà una estensione wireless alle una estensione wireless alle connessioni a cavo e DSL per l'accesso connessioni a cavo e DSL per l'accesso in banda larga dell’ultimo miglioin banda larga dell’ultimo miglio..

IEEE 802.16 consente una estensione IEEE 802.16 consente una estensione di area di servizio lineare fino a 50 km di area di servizio lineare fino a 50 km e consente agli utenti una connettività e consente agli utenti una connettività ad una stazione base verso la quale ad una stazione base verso la quale manca una linea diretta di vista. manca una linea diretta di vista.

88

Reti wireless a banda larga: WiMax Reti wireless a banda larga: WiMax (2/2)(2/2)

Il più recente standard pubblicato Il più recente standard pubblicato 802.16a802.16a contempla ambienti per contempla ambienti per sistemi che operano in bande tra sistemi che operano in bande tra 2 e 2 e 11 GHz11 GHz con la possibilità di gestire con la possibilità di gestire trasmissioni in ambiente Non-Line-of-trasmissioni in ambiente Non-Line-of-Sight, "Non A Vista“. Sight, "Non A Vista“.

99

Reti wireless a banda larga: Reti wireless a banda larga: HIPERMANHIPERMAN

HIPERMAN (High Performance Radio HIPERMAN (High Performance Radio Metropolitan Area Network)Metropolitan Area Network) è uno è uno standard creato dall’ETSI (European standard creato dall’ETSI (European Telecommunications Standards Telecommunications Standards Institute) per reti wireless per sistemi Institute) per reti wireless per sistemi che operano in bande tra che operano in bande tra 2 e 11 GHz2 e 11 GHz in Europa e costituisce un’alternativa in Europa e costituisce un’alternativa allo standard 802.16 del WiMax.allo standard 802.16 del WiMax.

1010

Digital Divide (1/2)Digital Divide (1/2)

Con Digital Divide (divario digitale) si Con Digital Divide (divario digitale) si intende il intende il divario esistente divario esistente nell'accesso alle telecomunicazioni a nell'accesso alle telecomunicazioni a banda largabanda larga..

Causato da una inadeguata presenze Causato da una inadeguata presenze di infrastrutture di rete sul territorio.di infrastrutture di rete sul territorio.

1111

Digital Divide (2/2)Digital Divide (2/2)

Il problema del Digital Divide non è Il problema del Digital Divide non è presente soltanto all’interno di paesi presente soltanto all’interno di paesi sottosviluppati, ma anche nelle sottosviluppati, ma anche nelle nazioni più tecnologicamente nazioni più tecnologicamente evolute.evolute.

Dovuto principalmente alla Dovuto principalmente alla difficoltà difficoltà di piazzare infrastrutture di retedi piazzare infrastrutture di rete in in zone montuose o impervie in zone montuose o impervie in generale.generale.

1212

Es. Copertura ADSLEs. Copertura ADSL

La copertura del territorio italiano La copertura del territorio italiano con accessi a Internet a velocità con accessi a Internet a velocità superiori a 1 Mb/sec (quindi a banda superiori a 1 Mb/sec (quindi a banda larga) è larga) è intorno al 50%intorno al 50% nel quale nel quale rientrano i 20 maggiori centri (Roma, rientrano i 20 maggiori centri (Roma, Milano, Torino, Genova, Napoli, etc.).Milano, Torino, Genova, Napoli, etc.).

Ben al di sotto della media europea Ben al di sotto della media europea ((95% di Regno Unito, oltre il 90% in 95% di Regno Unito, oltre il 90% in FranciaFrancia) e di stati con un territorio ) e di stati con un territorio più vasto dell'Italia e una più bassa più vasto dell'Italia e una più bassa densità abitativa e quindi più piccoli densità abitativa e quindi più piccoli centri da coprire.centri da coprire.

1313

SoluzioneSoluzione

In Francia e Inghilterra tale livello di In Francia e Inghilterra tale livello di copertura è in buona parte dovuto copertura è in buona parte dovuto all'all'utilizzo diffuso di tecnologie utilizzo diffuso di tecnologie wirelesswireless, liberalizzate da alcuni anni, , liberalizzate da alcuni anni, per servire territori in cui non è per servire territori in cui non è conveniente un servizio DSL oppure conveniente un servizio DSL oppure la posa della Fibra ottica. la posa della Fibra ottica.

1414

WLLWLL

II II Wireless Local LoopWireless Local Loop rappresenta rappresenta una via per fornire servizi voce e dati una via per fornire servizi voce e dati a case e uffici senza dover passare a case e uffici senza dover passare per l'ultimo miglio tradizionale, per l'ultimo miglio tradizionale, ovvero quello che lega le abitazioni ovvero quello che lega le abitazioni alla rete telefonica.alla rete telefonica.

I sistemi basati su WLL impiegano lo I sistemi basati su WLL impiegano lo spettro di frequenze a 26 Ghz e spettro di frequenze a 26 Ghz e consentono di "irradiare" le città con consentono di "irradiare" le città con un numero limitato di antenne. un numero limitato di antenne.

1515

Internet a banda larga senza filiInternet a banda larga senza fili

Nella telefonia senza fili fissa, una Nella telefonia senza fili fissa, una "wireless local loop" puo' sostituire "wireless local loop" puo' sostituire l'ultima connessione (last mile) di l'ultima connessione (last mile) di una rete telefonica cablata fissa, una rete telefonica cablata fissa, qualora tale rete cablata non sia qualora tale rete cablata non sia realizzabile a costi ragionevoli, come realizzabile a costi ragionevoli, come avviene nei paesi desertici o in via di avviene nei paesi desertici o in via di sviluppo.sviluppo.

In tal caso In tal caso è richiesto di assegnare è richiesto di assegnare una frequenza ad ogni stazioneuna frequenza ad ogni stazione. .

1616

Telefonia CellulareTelefonia Cellulare

Nella telefonia cellulare mobile, un Nella telefonia cellulare mobile, un utente mobile all'interno di una cella utente mobile all'interno di una cella si connette con la stazione base della si connette con la stazione base della cella medesima.cella medesima.

Poiché si richiede una connessione Poiché si richiede una connessione individuale per ogni utente nella individuale per ogni utente nella stessa cella, stessa cella, è necessario assegnare è necessario assegnare molti canali alla stessa stazionemolti canali alla stessa stazione. .

1717

Limiti dello spettro radioLimiti dello spettro radio

ProblemaProblema: sono presenti in genere : sono presenti in genere molte cellemolte celle ma ci sono ma ci sono poche poche frequenze disponibilifrequenze disponibili così che per così che per utilizzare al massimo lo spettro radio utilizzare al massimo lo spettro radio è necessario un efficiente algoritmo è necessario un efficiente algoritmo di assegnamento delle frequenzedi assegnamento delle frequenze. .

1818

InterferenzeInterferenze La maggior difficoltà verso un utilizzo La maggior difficoltà verso un utilizzo

efficiente dello spettro radio è dato efficiente dello spettro radio è dato dalle interferenze.dalle interferenze.

Causano una bassa qualità del Causano una bassa qualità del segnale radio e quindi la necessità di segnale radio e quindi la necessità di ritrasmissione dei messaggi.ritrasmissione dei messaggi.

Tuttavia possono essere Tuttavia possono essere eliminate (o eliminate (o per lo meno ridotte) con accurati per lo meno ridotte) con accurati tecniche di assegnamento dei canalitecniche di assegnamento dei canali..

Si distinguono 2 tipi di interferenze... Si distinguono 2 tipi di interferenze...

1919

Interferenza Co-canaleInterferenza Co-canale

Interferenza co-canale:Interferenza co-canale: si verifica quando si verifica quando due utenti siti in celle adiacenti (o vicine) due utenti siti in celle adiacenti (o vicine) utilizzano lo stesso canaleutilizzano lo stesso canale..

Interferenza molto critica che dipende Interferenza molto critica che dipende fortemente dal traffico cellulare. fortemente dal traffico cellulare.

La possibilità che si verifichi è maggiore La possibilità che si verifichi è maggiore nelle ore in cui il sistema cellulare è più nelle ore in cui il sistema cellulare è più indaffarato.indaffarato.

Lo stesso canale può essere riutilizzato da Lo stesso canale può essere riutilizzato da due stazioni contemporaneamente senza due stazioni contemporaneamente senza interferenza se e solo se le due stazioni interferenza se e solo se le due stazioni sono sufficientemente lontane.sono sufficientemente lontane.

2020

Interferenza AdiacenteInterferenza Adiacente Interferenza da canale adiacente:Interferenza da canale adiacente: si verifica quando si verifica quando

due utenti siti nella stessa cella o in celle adiacenti due utenti siti nella stessa cella o in celle adiacenti utilizzano due canali adiacenti.utilizzano due canali adiacenti.

I fenomeni di interferenza possono essere così forti I fenomeni di interferenza possono essere così forti che anche canali distinti utilizzati in stazioni vicine che anche canali distinti utilizzati in stazioni vicine possono interferire se i canali sono troppo vicini.possono interferire se i canali sono troppo vicini.

Canali assegnati a stazioni vicine devono essere Canali assegnati a stazioni vicine devono essere separati da un intervallo che è inversamente separati da un intervallo che è inversamente proporzionale alla distanza tra le stazioni.proporzionale alla distanza tra le stazioni.

Dipende da limitazioni di equipaggiamento dei vari Dipende da limitazioni di equipaggiamento dei vari client (p.e. filtri passabanda dei ricevitori non client (p.e. filtri passabanda dei ricevitori non ideali).ideali).

2121

Assegnamento CanaliAssegnamento Canali

Allocare canali radio ad una base Allocare canali radio ad una base station (e quindi ad una cella) in station (e quindi ad una cella) in modo da ottenere:modo da ottenere:• Utilizzo efficiente dello spettro di Utilizzo efficiente dello spettro di

frequenze a disposizione.frequenze a disposizione.• Ridurre al minimo le interferenzeRidurre al minimo le interferenze..• Buona qualità del servizio.Buona qualità del servizio.

Problema Problema NP-CompletoNP-Completo per topologie per topologie di rete generiche (e quindi grafi di rete generiche (e quindi grafi generici).generici).

2222

Classificazione Algoritmi (1/2)Classificazione Algoritmi (1/2)

FCA (Fixed Channel Assignment)FCA (Fixed Channel Assignment)• Assegnamento staticoAssegnamento statico, cioè effettuato , cioè effettuato

una volta per tutte in base ad una stima una volta per tutte in base ad una stima delle richieste di connessioni simultanee delle richieste di connessioni simultanee per ciascuna stazione.per ciascuna stazione.

DCA (Dynamic Channel Assignment)DCA (Dynamic Channel Assignment)• Assegnamento dinamicoAssegnamento dinamico, cioè effettuato , cioè effettuato

in linea all'atto della effettiva necessità in linea all'atto della effettiva necessità di utilizzare un canale libero per una di utilizzare un canale libero per una comunicazione.comunicazione.

2323

Classificazione Algoritmi (2/2)Classificazione Algoritmi (2/2)

HCA (Hybrid Channel Assignment)HCA (Hybrid Channel Assignment)• Assegnamento mistoAssegnamento misto, dove un , dove un

sottoinsieme di canali per ciascuna sottoinsieme di canali per ciascuna stazione è assegnato in modo statico ed stazione è assegnato in modo statico ed il resto in modo dinamico, il resto in modo dinamico, eventualmente prendendo a prestito da eventualmente prendendo a prestito da una stazione vicina un canale una stazione vicina un canale momentaneamente non utilizzato. momentaneamente non utilizzato.

2424

FCA (1/2)FCA (1/2)

FCA ha il vantaggio di non richiedere alti FCA ha il vantaggio di non richiedere alti costi computazionali al momento costi computazionali al momento dell’assegnazione della frequenza.dell’assegnazione della frequenza.

Gode di Gode di performance migliori rispetto a performance migliori rispetto a DCA ed HCADCA ed HCA, soprattutto in situazioni di , soprattutto in situazioni di traffico elevato ed uniforme.traffico elevato ed uniforme.

E’ spesso usato nella pratica (reti E’ spesso usato nella pratica (reti cellulari di 1° e 2° generazione).cellulari di 1° e 2° generazione).

Il problema FCA rappresenta comunque Il problema FCA rappresenta comunque un bound ai problemi DCA ed HCA.un bound ai problemi DCA ed HCA.

2525

FCA (2/2)FCA (2/2)

FCA è in genere testato con FCA è in genere testato con opportune istanze di opportune istanze di benchmarkbenchmark..

Usualmente è utilizzato il benchmark Usualmente è utilizzato il benchmark PhiladelphiaPhiladelphia::• 21 esagoni che denotano le celle della 21 esagoni che denotano le celle della

rete cellulare.rete cellulare.• I trasmettitori sono localizzati al centro I trasmettitori sono localizzati al centro

della cella.della cella.• La distanza tra celle adiacenti è sempre La distanza tra celle adiacenti è sempre

fissa e considerata 1.fissa e considerata 1.

2626

Modello matematicoModello matematico

Un sistema cellulare è rappresentato Un sistema cellulare è rappresentato come un come un grafografo dove: dove:• I nodi rappresentano le base-station.I nodi rappresentano le base-station.• Gli archi collegano due base-station che Gli archi collegano due base-station che

hanno un’intersezione nella loro area di hanno un’intersezione nella loro area di copertura.copertura.

2727

Distanza di riuso del canale (1/2)Distanza di riuso del canale (1/2) La distanza tra due nodi è il minimo La distanza tra due nodi è il minimo

numero di archi da attraversare per numero di archi da attraversare per andare da un nodo all’altro.andare da un nodo all’altro.

L’L’eliminazione delle interferenze eliminazione delle interferenze cochannelcochannel è modellata introducendo il è modellata introducendo il vincolo della distanza di riuso del canale vincolo della distanza di riuso del canale ((σσ)); ovvero un canale può essere ; ovvero un canale può essere utilizzato contemporaneamente in due utilizzato contemporaneamente in due nodi se e solo se tali nodi si trovano a nodi se e solo se tali nodi si trovano a distanza maggiore o uguale di distanza maggiore o uguale di σσ..

2828

Distanza di riuso del canale (2/2)Distanza di riuso del canale (2/2)

• Distanza di riuso σ=2.

2929

Vettore di separazione dei canali Vettore di separazione dei canali (1/2)(1/2)

L’L’eliminazione delle interferenze eliminazione delle interferenze cosite e adjacentcosite e adjacent è modellata è modellata introducendo il introducendo il vettore di separazione vettore di separazione dei canali (dei canali (δδ11, , δδ22,…,,…,δδii,…,,…,δδσσ-1-1))..

Tale vettore rappresenta il gap Tale vettore rappresenta il gap (contato in numero di canali) che (contato in numero di canali) che deve separare due canali assegnati a deve separare due canali assegnati a nodi distanti nodi distanti ii..

3030

Vettore di separazione dei canali Vettore di separazione dei canali (2/2)(2/2)

SPETTRO DI

FREQUENZE

0

1

2

3

4

5

3131

CAPS (Channel Assignment CAPS (Channel Assignment Problem with Separation)Problem with Separation)

I canali radio possono essere I canali radio possono essere modellati come colori (interi non modellati come colori (interi non negativi).negativi).

CAPS può essere definito come il CAPS può essere definito come il problema di trovare una Lproblema di trovare una L((δδ11, , δδ22,,…,…,δδσσ-1-1)-colorazione del grafo che )-colorazione del grafo che modella la rete.modella la rete.

3232

Colorazione grafiColorazione grafi

Una LUna L((δδ11, , δδ22,…,,…,δδσσ-1-1)-colorazione di un )-colorazione di un grafo G=(V,E) grafo G=(V,E) è una funzione f:Vè una funzione f:VΛΛ dove dove ΛΛ={0,…,={0,…,λλ} è un insieme di colori } è un insieme di colori ed f verifica il vincolo:ed f verifica il vincolo:

|f(u)-f(v)|≥ |f(u)-f(v)|≥ δδii se d(u,v)=i per i=1,…, se d(u,v)=i per i=1,…,σσ-1-1 Una colorazione ottimale di questo tipo Una colorazione ottimale di questo tipo

è data da una funzione f che è data da una funzione f che minimizzi il minimizzi il valore valore λλ, e quindi il numero di colori , e quindi il numero di colori (canali) richiesti ((canali) richiesti (λλ+1).+1).

3333

Limitazioni al numero di coloriLimitazioni al numero di colori

Escludendo il vincolo della Escludendo il vincolo della separazione dei canali il problema separazione dei canali il problema si riduce a L(1,…,1).si riduce a L(1,…,1).

Un limite inferiore per L(1,…,1) lo è Un limite inferiore per L(1,…,1) lo è anche per L(anche per L(δδ11,…,,…,δδσσ-1-1).).

L(1,…,1) per il grafo GL(1,…,1) per il grafo Gnn può essere può essere ridotto al classico problema di ridotto al classico problema di colorazione dei graficolorazione dei grafi (L(1)) per il (L(1)) per il grafo (aumentato) Ggrafo (aumentato) Gn,n,σσ..

3434

Il grafo GIl grafo Gn,n,σσ

GGn,n,σσ=(V,E’) è ottenuto da =(V,E’) è ottenuto da GGnn=(V,E) =(V,E) aggiungendo un arco per ogni coppia aggiungendo un arco per ogni coppia di vertici a distanza minore di di vertici a distanza minore di σσ (ovvero {u,v}(ovvero {u,v}E’ E’ d(u,v)≤d(u,v)≤σσ-1 in G-1 in Gnn).).

σ = 3

3535

Limitazioni al numero di coloriLimitazioni al numero di colori

Per colorare Per colorare GGn,n,σσ occorre occorre un numero di un numero di colori almeno pari alla dimensione colori almeno pari alla dimensione della massima cricca di della massima cricca di GGn,n,σσ..

Una cricca è un sottoinsieme di Una cricca è un sottoinsieme di vertici del grafo totalmente connessi vertici del grafo totalmente connessi (proprio per questo servono colori (proprio per questo servono colori diversi).diversi).

La dimensione di una cricca è data La dimensione di una cricca è data dal numero di vertici che la dal numero di vertici che la compongono.compongono.

3636

Cenni sulla complessitàCenni sulla complessità CAPS è CAPS è NP-CompletoNP-Completo per grafi per grafi

generici.generici. Infatti, già L(2,1) è intrattabile.Infatti, già L(2,1) è intrattabile. Esistono, comunque, Esistono, comunque, efficienti efficienti

algoritmi per colorazioni ottimali algoritmi per colorazioni ottimali da applicare a specifiche topologie da applicare a specifiche topologie di grafidi grafi..

3737

Topologia cellulare (o esagonale)Topologia cellulare (o esagonale)

Utilizzata nella pratica perché Utilizzata nella pratica perché copre copre l’intero piano euclideo minimizzando il l’intero piano euclideo minimizzando il numero di base-station necessarienumero di base-station necessarie..

3838

Algoritmo per L(Algoritmo per L(2,1,1)-colorazione 2,1,1)-colorazione per griglie cellulari (1/3)per griglie cellulari (1/3)

Algoritmo ottimale per griglie cellulari Algoritmo ottimale per griglie cellulari di dimensione r x c con rdi dimensione r x c con r≥4 e c≥4.≥4 e c≥4.

LemmaLemma: Esiste una colorazione : Esiste una colorazione ottimale solo se ottimale solo se λ≥λ≥11 (perché in tali 11 (perché in tali grafi la massima cricca ha dimensione grafi la massima cricca ha dimensione 12).12).

3939

Algoritmo per L(Algoritmo per L(2,1,1)-colorazione per 2,1,1)-colorazione per griglie cellulari (2/3)griglie cellulari (2/3)

4040

Algoritmo per L(Algoritmo per L(2,1,1)-colorazione 2,1,1)-colorazione per griglie cellulari (3/3)per griglie cellulari (3/3)

4141

ComplessitàComplessità L’algoritmo L’algoritmo opera in tempo costante opera in tempo costante

O(1)O(1) se ogni stazione (vertice) se ogni stazione (vertice) conosce la propria posizione logica conosce la propria posizione logica all’interno del grafo.all’interno del grafo.

Se così non fosse basterebbe dotare Se così non fosse basterebbe dotare ogni stazione di un sistema GPS ogni stazione di un sistema GPS cosicché conosca la propria cosicché conosca la propria posizione assoluta e far girare poi posizione assoluta e far girare poi un semplice algoritmo distribuito e un semplice algoritmo distribuito e polinomiale.polinomiale.

4242

Position Discovering su griglia Position Discovering su griglia cellulare (1/2)cellulare (1/2)

La computazione inizia dal nodo in alto a La computazione inizia dal nodo in alto a sinistra che è l’unico che conosce la sua sinistra che è l’unico che conosce la sua posizione logica (0,0).posizione logica (0,0).

Viene inviato un Viene inviato un messaggio di controllomessaggio di controllo del tipo del tipo CM(v,gCM(v,gvv,i,j),i,j) dove dove ggvv è la posizione è la posizione geografica di geografica di vv ed ed i,ji,j è la posizione logica. è la posizione logica.

Quando un vertice Quando un vertice uu riceve il messaggio riceve il messaggio confronta la sua posizione geografica con confronta la sua posizione geografica con ggvv e calcola la sua posizione logica e calcola la sua posizione logica inviando poi lui stesso un messaggio.inviando poi lui stesso un messaggio.

4343

Position Discovering su griglia Position Discovering su griglia cellulare (2/2)cellulare (2/2)

(0,0)

(1,0)

(0,1)

(1,1)

(0,2)

(1,2)

(2,0) (2,1) (2,2)

(3,0) (3,1) (3,2) (3,3)

(0,3)

(1,3)

(2,3)

Tempo: O(max(r,c))

Numero Messaggi Scambiati: O(rc)

4444

Perchè non si usano Frequenze Perchè non si usano Frequenze Guardia (1/2)Guardia (1/2)

SPETTRO DI

FREQUENZE

4545

Perchè non si usano Frequenze Perchè non si usano Frequenze Guardia (2/2)Guardia (2/2)

Nei vari algoritmi FCA per grafi regolari Nei vari algoritmi FCA per grafi regolari (incluso quello visto) (incluso quello visto) non occorrono non occorrono canali extra per evitare l’interferenza canali extra per evitare l’interferenza dovuta a frequenze adiacentidovuta a frequenze adiacenti..

Banda per frequenze guardia:Banda per frequenze guardia:

WWguardguard=(=(λλ+1)+1)ββ++λγλγ Banda per separazione dei canali:Banda per separazione dei canali:

WWseparationseparation==((λλ’+1)’+1)ββ λλ = = λλ’ ’ W Wseparationseparation<W<Wguardguard

F I N EF I N E