Antonio Sassano (Università di Roma “La Sapienza”)
Progetto di reti digitali terrestri e cammini minimi
Seminario 1 – Il Problema
The technology: OFDM
• Decomposes a bitstream into slower parallel bitstreams
1 Megabit/s T streams of 1/T Megabit/s
• Modulates T orthogonal carriers
• One Symbol q bits (64QAM 6 bits)
Stream 1
Stream 2
Stream 3
Stream T
….
Symbols
“Frequency hopping”
Symbols
Features of OFDM• Orthogonal carriers overlap Spectral Efficiency = More bits per hertz
• “Frequency hopping” reduces the “fading” effect• But … orthogonality needs care
Multi-path effect
Same stream…Same symbol …… but delayed
Time
Inter Symbol Interference
• Delays destroy orthogonality• “Longer” symbols (low rate) help• .. But OFDM does even better
The Guard Interval
And here comes …. the magic
• OFDM adds a prefix to every symbol• If the guard interval is “longer” than delays Orthogonality can be restored
Inter Symbol Interference is avoided Service is improved
GUARD INTERVAL SYMBOL
GUARD INTERVAL SYMBOL
GUARD INTERVAL SYMBOL
GUARD INTERVAL SYMBOL
The Magic … of OFDM
• Two transmitters located in different sites• … using the same frequency (same carrier)• … transmitting the same content (same symbols)
ANALOG THECNOLOGY Interference No service
DIGITAL TECHNOLOGY Delayed symbols
If delays are smaller than Guard Interval ….. ….. OFDM guarantees a better service
“artificial multipath”GUARD INTERVAL SYMBOL
GUARD INTERVAL SYMBOL
6
Coverage of service area
C1
C5
C1C3
C7
C9
C11
C1
C9
C5
C3
C3
Border of service area
C3
Border of coverage
area for an
individual
transmitter
Classical Re-use Schema of the Analog Era Each transmitter uses a different frequency channel (Cx), acting
independently and having its own coverage area Re-use of channels is possible given sufficient geographical separation
Multi Frequency Networks (MFNs)
Source ITU: Nigel Laflin 2003
7
Coverage of service area
Border of service area
C1
C1
C1
C1
C1
C1
C1
C1
C1
C1
Border of coverage area
All transmitters of the network use the same frequency channel
The transmitters provide a common coverage area and can’t be operated independently – they must carry identical multiplex content
Single Frequency Network (SFN)
Source ITU: Nigel Laflin 2003
OFDM: Conclusions • Better spectral efficiency (more bits per Hz)• Better use of spectrum (SFN)• Resilience to “selective frequency fading”• Turns Multipath from “bad” to “good”
And in fact …. It will be the basic technology for:
• Digital Broadcasting• Wimax (WiBro)• LTE (Long Term Evolution of 3G)• … 4th generation (Anytime, Anywhere … )• Short Range (UltraWideBand)
…. No Jokes (I)
…. No Jokes (II)
Il Problema da Risolvere
Progetto di una (semplice) Rete OFDM(rete digitale terrestre SFN)
Si vuole servire in tecnologia digitale terrestre una specifica area geografica
L’area geografica viene rappresentata come una griglia di rettangoli di lato 96 secondi (di grado)
Ogni rettangolo della griglia è rappresentato dal suo baricentro: il testpoint
I siti di trasmissione sono anch’essi posizionati sulla “griglia”: ad esempio Roma Monte Mario
Ogni rettangolo della griglia è rappresentato dal suo baricentro: il testpoint
Sito candidato di Roma Monte Mario
Problema: Progetto di rete OFDMINPUT• Digital Terrain Model (milioni di testpoint in Europa)• Informazioni su posizione, quota e tipo di vegetazione• Siti Candidati (35.000 in Italia e Paesi confinanti)
Siti di trasmissione nel sud della Francia
SRTM DTM (Nasa)• 1 tp = 6x6 secondi• 1 tp ≈ 180x180 mt
• In ciascun testpoint la qualità del servizio è una funzione della:– Potenza ricevuta dai segnali serventi– Potenza ricevuta dai segnali interferenti
• La potenza ricevuta in un testpoint è una funzione dei seguenti fattori:– distanza– terreno (orografia, palazzi, vegetazione…)– guadagno dell’antenna del settore “visto” dall’antenna ricevente
Come verificare se un tespoint è “servito”
La propagazione elettromagnetica
• In ogni testpoint possiamo calcolare la potenza del segnale ricevutoda uno specifico trasmettitore (Monte Mario nell’esempio)
• Il calcolo viene effettuato utilizzando modelli di simulazione certificati dalla International Telecommunication Union (ITU)
• Il modello di simulazione tiene conto della distanza e dell’orografia• La potenza ricevuta dipende alla potenza emessa
15.024, ig
• Guadagno nominale
– per ogni trasmettitore i
– per ciascun settore j1,…,36
ijN
-50
-40
-30
-20
-10
01
2 34
56
7
8
9
10
11
12
1314
1516
171819
202122
2324
25
26
27
28
29
30
3132
3334
35 36
Serie1
124, iN
-50
-40
-30
-20
-10
01
2 34
56
7
8
9
10
11
12
13
1415
161718
192021
2223
24
25
26
27
28
29
30
31
3233
3435 36
15.024,24, ii gN
Potenza di emissione e diagramma di antenna
Massimizzare l’estensione del servizio ottenibile daisiti candidati sagomando opportunamente i diagrammi (modificando il guadagno)
La funzione obiettivo
Come verificare se un tespoint è “servito”
La Qualità del Servizio dipende dal rapporto tra:1. potenza del segnale utile 2. potenza del segnale interferente
Calcolo della qualità del servizio OFDM
Condizione di Copertura
QoSss
sPsPErf
IW
IW
)()(
)()(22
Detection window 224msec
0
10
20
30
40
50
60
70
80
90
100
Time (microsec)
Power
(dBW/m2)
PI(s), I2(s)
PW(s), W2(s)
• log-normal power-sum di segnali utili e interferenti
GUARD INTERVAL SYMBOL
GUARD INTERVAL SYMBOL
GUARD INTERVAL SYMBOL
47 113 155 203 333 393 450 515
Intervallo di guardia
PREDIZIONE DEL CAMPOELETTROMAGNETICO
• Potenza nominale Fit ricevuta– in ciascun testpoint t– da ciascun trasmettitore i
ALGORITMO DI PREDIZIONE DEL SERVIZIO OFDM
MODELLO DIGITALETERRITORIO
DATI NOMINALIDEI TRASMETTITORI
OTTIMIZZA IL GUADAGNO
• Potenza Pit ricevuta (effettiva)– in ciascun testpoint t– da ciascun trasmettitore i
git
Simulazione del Servizio
d(i,t)=7
Testpoint t
Come ottimizzare il guadagno? Definizioni …
,,, 3621 iiiid gggg Modifica del guadagno trasmettitore i
,,, 3621 iiiid NNNN Guadagno nominale (costante ) per il trasmettitore i (nelle 36 direzioni)
idid Ng Guadagno effettivo
itF Potenza nominale ricevuta nel testpoint t (costante)
),( tiiditit gFP Potenza nel testpoint t
Condizione di copertura
QoSss
sPsPErf
IW
IW
)()(
)()(22
Settore “visto” da t),( tid
tit
tsIi
ijit
tsWi
it gsbgsa ),(),(
)()(
Linearizzazione della condizione di copertura
Segnali utili e frequenze utili
• Ciascun segnale utile definisce una “finestra utile”• Ciascuna finestra definisce i segnali utili e interferenti (trasmettitori)• Due differenti finestre (segnali) possono coprire lo stesso testpoint
100
0102030405060708090
47 113 155 203 333 393 450 515 msec
Power
(dBW/m2)
S(t) = segnali utili ricevuti nel tespoint t
tit
tsIi
ijit
tsWi
it gsbgsa ),(
1
),(
1
11
)()(
1s 2s
tit
tsIi
ijit
tsWi
it gsbgsa ),(
2
),(
2
22
)()(
• IPOTESI SEMPLIFICATIVA #1 |S(t)|=1
“In ogni testpoint consideriamo un solo segnale utile (ad esempio: il più potente)”
Il modello combinatorio
TPt
TPtMgsbgsa
pp
t
ttit
tsIi
ijit
tsWi
it
TPt
tt
T
1,0
)1()()(
max
),(),(
• Evento elementare : testpoint coperto oppure no
• Vantaggio: popolazione del testpoint TPp
S = vetttori di incidenza degli insiemi di testpoint coperti
1,0 TP
S Formulazione Naturale
TRg 36,,1• Nota : il vettore è una variabile di decisione
• Il problema è di PL01 mista
0° 1
30° 4
60° 7
90° 10
120° 13
150°
14180° 19
210° 22
240° 25
270° 26
300° 31
330° 34
-10dB
-20dB
-40dB
0° 1
30° 4
60° 7
90° 10
120° 13
150°
14180° 19
210° 22
240° 25
270° 26
300° 31
330° 34
-10dB
-20dB
-40dB
NON AMMISSIBILE AMMISSIBILE
ANTENNE AMMISSIBILI VINCOLI sul GUADAGNO
Tutte le g sono ammissibili? NO!!
Discretizzazione in 36 setori d = {1, …, 36}
Limiti sul guadagno
Vincoli da settore adiacente
Il rapporto tra due settori adiacenti
non può superare un valore specificato
Vincoli di attenuazione globale
Il rapporto tra ogni coppia di settori
non può superare un valore (più grande)
UB
t
LB
ttd ggg ,
0)1( idadi gg
0° 1
30° 4
60° 7
90° 10
120° 13
150°
14180° 19
210° 22
240° 25
270° 26
300° 31
330° 34
-10dB
-20dB
-40dB
Diagrammi di antenna realistici (vincoli)
0' idbid gg
Il modello “nazionale” (di PL01 Mista)
Modello nazionale
TPt
dTRiggg
ddTRigg
dTRigg
TPtMgsbgsa
p
t
UB
idid
LB
id
idbid
diaid
ttit
tsIi
itit
tsWi
it
TPt
tt
1,0
36,,1,
36,,1',, 0
36,,1, 0
)1()()(
max
1'
)1(
),(),(
Perchè Nazionale?
Perchè non consideriamo l’effetto sui paesi confinanti
99.9% in Sardegna ma forte interferenza in Tunisia e Francia
A European Plan must be implemented!
90’s - DVB-T (Digital Video Broadcasting – Terrestrial) …. a new Technology for a European Standard OFDM-based
o 6817 carriers - 8k system [1705 carriers - 2k system]o 24 Megabit/s “payload” in 8MHz channelo 5 HQ TV programs use the band of 1 analog program
Chester Conference (1995) … Stockholm ‘61 last update Geneva Conference (June 2006) THE NEW PLAN (!) 2015 Analog TV “Switch off” (All Digital Scenario) “Switch off 2012” - European Common Proposal
NEED TO UPDATE THE OLD ANALOG PLAN - STOCKHOLM 1961
GE06: Digital (SFN) changes the rules
36
Two types of planning objects: Assignments and Allotments
Assignment is a “fully specified transmitter”
Allotment is a geographic area where:
• Site• Frequency• Antenna Diagram• ……
• A SFN using frequency f can be designed• The actual structure of the SFN is left open
• STOCKHOLM ‘61 had only assignments• Allotments ease a “flexible” approach to digital coverage
21
21
ITALIA
FRANCIA
Eint≤ Thrt
Allotment e Assignment definiscono aree protette(somma in potenza degli interferenti minore di una soglia )
Assignment alzano la soglia (nelle nazioni vicine)
Un canale può essere usato dalle due amministrazioni-Le reti digitali sono protette da allotment e assignment nazionali
- … e sono limitate da allotments/assignment stranieri
L’ “approccio a soglia”
Soglie per il Canale 8
38
Modello completo di OFDM Network Design
TPt
dtTRiggg
ddtTRigg
dtTRigg
TPtMgsbgsa
p
t
UB
idid
LB
id
idbid
diaid
ttit
tsIi
itit
tsWi
it
TPt
tt
1,0
36,,1),(
36,,1',),( 0
36,,1),( 0
)1()()(
max
1'
)1(
),(),(
ExTPtThrga t
tTRi
idit
)(
+
TP National testpoint set
Foreign testpoint setExTPExTPTPttsItsWtTR ),,(),()( Transmitters received in a testpoint
Maximize National Coverage
Power Sum below GE06 threshold
(Coordinated) Network Design Model
+
)(, 1,0
1,0
)(,
36,,1),(
36,,1',),( 0
36,,1),( 0
)(, )1()()(
max
1'
)1(
),(),(
tSsTPtw
TPt
tSsTPtw
dtTRiggg
ddtTRigg
dtTRigg
tSsTPtwMgsbgsa
p
st
t
stt
LB
idid
LB
id
idbid
diaid
tstit
tsIi
itit
tsWi
it
TPt
tt
ExTPtThrga t
tTRi
idit
)(
Large Scale (0,1) ProblemExample: Channel 8 VHF
a critical channel for Italy
145 Candidate Sites
5220 Variables
154.114 Coverage Constraints
41.034 Testpoints
14.007Active Foreign Testpoints
10.440 Feasibility Constraints
CPLEX does not even find a solution for the linear relaxation! Numerically instable (coefficients ait and bit have a huge range)
We find the optimal solution by massive pre-processingand …. row generation
Is the national Solution: (“ .. let’s forget about neighbors”)
Remove the power-sum constraints: a non-solution
But we do care about neighbors ….
and we use Optimization ….
Italy (total power sum) must arrive below 30 dB microvolt/m in the yellow areas
Step 1: Preprocessing and First Relaxation
ExTPtThrga t
tTRi
idit
)(
ExTPtThrg tid
Replace Power-Sum constraints by individual upper bounds
909 (out of 14.007) Power-sum constraints are violated
Step i: Generic “Row Generation”
Add the most violated power-sum constraints and solve …
Down to 540 violations
0
1
2
3
4
5
6
7
8
9
10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0
100
200
300
400
500
600
700
800
900
1000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Algorithm Progression
# of violated Power-Sum Costraints
Maximum Power-Sum Violation
Final Step: Optimal Solution
81% of national population served … GE06 constraints met!